REDUCED COMPLEXITY FAST HADAMARD TRANSFORM AND FIND-MAXIMUM MECHANISM ASSOCIATED THEREWITH

摘要

A method and apparatus for performing a radix-4 fast Hadamard transform (FHT) with reduced complexity that utilizes only seven operations and for directly determining the maximum output of a fast Hadamard transform using either a radix-4 transform or radix-2 transform without actually generating the outputs. To find the maximum value of the output of a fast Hadamard transform and its corresponding index, the N-1 stages of a conventional N stage fast Hadamard transform are computed while a find-maximum stage is inserted in place of the Nth stage. The invention also provides a methodology for constructing fast Hadamard transforms of the form H2N using radix-4 FHTs and permuting the results to achieve the correct outputs.