Parallel pipeline fast fourier transformer

The advantages of using digital convolution to implement a particular pulse compression radar filter are outlined. Using the bandwidth of the given filter, a simple calculation of the required computation rate indicates that considerable parallel computation would be necessary using existing integrated circuits. Some methods of computing the DFT are given and the FFT algorithm is chosen since its regular structure and in-place computation facilitate parallel computation. A description of the parallelism in the radix-2 pipeline FFT is presented, and it is shown that to obtain the required processing rate further parallel processing is necessary. By computing n butterflies in parallel at each stage of the FFT a family of parallel pipeline FFT processors are developed. Using the new architectures allows an increase in the processing speed while retaining the simple structure of the pipeline FFT. It is shown that for each value of N and n there are four canonic forms of equivalent computational complexity, but with different structures. The four forms arise from the two types of DIT FFT algorithm and the two methods of selecting the order in which the butterflies are computed. The connection between the FFT algorithm and the binary m-cube array is given, and is used to show by an example how the architectures presented fit between the normal pipeline FFT and the array processor in the amount of parallel computation involved. The radix-4 pipeline FFT is described and it is shown that this structure can also be paralleled in a similar way to the radix-2 pipeline FFT. The amount of hardware required to implement digital convolution using these architectures is discussed and examples are given. The balance between logic speed and integration density and the problems of interconnecting the computational elements are also discussed.