Removing Redundancies of Fast Fourier Transform Computations

Abstract

The Fast Fourier Transform (FFT) is widely used in various digital signal processing (DSP) applications. In this thesis, we are exploring this problem from a fundamental arithmetic stance: maintain the degree of freedom at all stages to be the minimum by completely eliminating arithmetic redundancies. The proposed approach is canonic with respect to the number of signals (i.e., data-canonic) at the each stage. First, we present novel decimation-in-time (DIT) and decimation-in-frequency (DIF) structures for computing RFFT that are canonic with respect to the number signal values computed at each FFT stage. In the proposed structure, in an N-point RFFT, exactly N signal values are computed at the output of each FFT stage and at the output. One of our contribution is in showing that the twiddle factors can be transformed to reduce the computational complexity. Next, we present a novel algorithm to compute real-valued fast Fourier transform (RFFT) that is canonic with respect to the number of signal values. A signal value can correspond to a purely real or purely imaginary value, while a complex signal consists of 2 signal values. In order to reduce the redundant samples, a sample removal lemma, and two types of twiddle factor transformations are proposed: pushing and modulation. We consider 4 different cases for an N = P x Q point canonic RFFT: 1) P is odd, Q is odd; 2) P is odd, Q is even; 3) P is even, Q is odd; and 4) P is even, Q is even. No twiddle factor transformation is required when P is odd. It is shown that the number of twiddle factors can be reduced by performing modulation transformation when P is even and Q is odd, while 2 real twiddle factor operations are pushed to 1 complex twiddle factor operation when P and Q are both even. Canonic RFFT for any composite length can be computed by applying the proposed algorithm recursively. The major advantage of the canonic RFFTs is that they require the least butterfly operations and only involve real datapath when mapped to architectures. Furthermore, we consider the FFT computation whose inputs are not only real but also even/odd symmetric. Novel algorithms for generating the flow-graphs of canonic RFFTs with even/odd symmetric signals are proposed. It is shown that by performing the proposed algorithms, the resulted canonic structure will have N/2 + 1 signal values at each stage for an N-point RFFT with even symmetric signals (REFFT), or N/2 - 1 signal values at each stage for an N-point RFFT with odd symmetric signals (ROFFT). In order to remove butterfly operations, twiddle factor operation may also be needed to pull the twiddle factors to previous stages. We also discuss the design of canonic REFFT for any composite length. Performances of the canonic REFFT/ROFFT are also discussed. It is shown that the flow-graph of canonic REFFT/ROFFT has less number of interconnections, less butterfly operations, and less twiddle factor operations, compared to prior works. Finally, we present a novel scalable architecture for in-place FFT/IFFT computation for real-valued signals. The proposed computation is based on a modified radix-2 algorithm, which removes the redundant operations from the flow-graph. A new processing element is proposed using two radix-2 butterflies which can process four inputs in parallel. A novel conflict-free memory addressing scheme is proposed to ensure the continuous operation of the FFT processor. Furthermore, the addressing scheme is extended to support multiple parallel processing elements (PEs). The proposed real-valued FFT processor simultaneously requires fewer computation cycles and lower hardware cost compared to prior work. For example, the proposed design with 2 PEs reduces the computation cycles by a factor of 2 for a 256-point RFFT compared to a prior work, while maintaining a lower hardware complexity. The number of computation cycles is reduced proportionately with increase in the number of PEs.