Theory and Implementation of Fast Fourier and Hadamard Transforms.
Abstract
The purpose of this report is to develop general algorithms for the Fast Fourier Transform (FFT) and Hadamard transform from which optimum computer programs can be written as a signal analysis tool. The need for such discrete transforms is obvious from the introductory treatment of integral transforms, Fourier series, and the sampling theorem. First, the radix-2 algorithm is treated in detail for N = 8 and then extended to N = 2(M). A general transformation algorithm is derived next to accommodate arbitrary factors. This very useful general algorithm is also used to implement and optimize various FFT algorithms. A general unscrambling formula is derived to optimize the unscrambling process for radix-2 and radix-4 algorithms. Techniques are given but not yet optimized for unscrambling with respect to odd factors. All FFT programs discussed in this report are evaluated in terms of number of operations and computer time. The Hadamard transform is defined and computer programs developed. Finally, the properties of the FFT and the Hadamard transform are discussed in light of their application to radar processing. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- Apr 01, 1973
- Accession Number
- AD0762437
Entities
People
- B. K. Bhagavan
- Edward R. Mckee Jr
- James M. Carswell
- Robert J. Polge
Organizations
- University of Alabama in Huntsville