4 Integer Fast Fourier Transform 4.1 Introduction 4.2 The Lifting Scheme 4.3 Algorithms 4.4 Performances and Complexities 4.5 Integer Discrete Fourier Transform [I-5] 4.6 Summary4 Integer Fast Fourier Transform 4.1 Introduction Integer fast Fourier transform (IntFFT) is an integer approximation of the DFT [I-4]. The transform can be implemented by using only bit shifts and additions but no multiplications. Unlike the fixed-point FFT (FxpFFT), IntFFT is power adaptable and reversible. IntFFT has the same accuracy as the FxpFFT when the transform coefficients are quantized to a certain number of bits. Complexity of IntFFT is much lower than that of FxpFFT, as the former requires only integer arithmetic. Since the DFT has the orthogonality property, the DFT is invertible. The inverse is just the complex conjugate transpose. Fixed-point arithmetic is often used to implement the DFT in hardware. Direct quantization of the coefficients destroys the invertibility of the transform. The IntFFT keeps the invertibility property of the DFT while the coefficients can be quantized to finite-length binary numbers. 7922×n2= Lifting factorization can replace the orthogonal matrices appearing in fast structures to compute the DFT of input with length of N for n an integer such as split-radix, radix-2 and radix-4. The resulting transforms or IntFFTs are invertible, even though the lifting coefficients are quantized and power-adaptable, that is, different quantization step sizes can be used to quantize the lifting coefficients.0x1x 800A1A0A1AA1A Figure 4.1 The lifting scheme [I-5]. 4.2 The Lifting Scheme The lifting scheme is used to construct wavelets and perfect reconstruction (PR) filter banks [I-1,2,3,4,6]. Biorthogonal filter banks having integer coefficients can be easily implemented and can be used as integer-to-integer transform. The two-channel system in Fig. 4.1 shows the lifting scheme. The first branch is operated by and called dual lifting whereas the second branch is operated by and is called lifting. We can see that the system is PR for any choices of and . It should be noted that and can be nonlinear operations like rounding or flooring operations, etc. 0 Figure 4.2 Butterfly structure for implementing a complex multiplication where θsin=s and θcos=c [I-4]. 0A 1A 0y1y ++ 0xx 1A 0A 1rxx c{}Re ⋅i {}⋅Im xy js+irjxxx +=axy =ca = c−ssj ryiy {}⋅Re {}⋅Im ccx yjsca−=irjyyy +=1 yax1= s−sj81 Figure 4.3 Lifting structure for implementing a complex multiplication where θsin=s and θcos=c [I-4]. 4.3 Algorithms Integer fast Fourier transform algorithm approximates the twiddle factor multiplication [I-4,5]. Let x be a complex number. The multiplication of irjxx +=x with a twiddle factor , is the complex number, θθθsincos jeaj+==axy= and can be represented as ()jy 1=⎜⎜⎛−θθθθcossinsincos()jxxr1=⎟⎟⎞⎜⎜⎛⎟⎟⎠⎞⎝i⎠⎝θR⎟⎟⎠⎞⎜⎜⎝⎛irxx (4.1) where ⎥⎦⎤−θθcossin⎢⎣⎡=θθθsincosR (4.2) The main difficulty in constructing a multiplier-less or integer transform by using the sum-of-powers-of-two (SOPOT) representation of θR is that the coefficients of the inverse matrix of θR cannot in general be represented in terms of SOPOT coefficients. If θcos and θsin in (1) are quantized and represented as α and β in terms of SOPOT coefficients, then an approximation of θR is in (4.3). ⎥⎦⎤⎢⎣⎡−=αββαθR~ (4.3) and its inverse is in (4.4). {} Re⋅{}⋅Im x y jsca += x axy = sc 1− s+c 1−+js +{}⋅Re {}⋅Im y x y xax1= sc 1− sjsc 1− jsca−=1⎥⎦⎤⎢⎣⎡−+=−αββαβα2211θ~R (4.4) 82As α and β are SOPOT coefficients, the term 22βα+ cannot in general be represented as SOPOT coefficients. The basic idea of the integer or multiplier-less transform is to decompose θR1det 0≠ into three lifting steps. If and c [I-6], []()=A []()()⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡⎦⎢⎣⎡=⎥⎦⎤⎢⎣⎡=1011101101 cdcdcbaA⎥⎤−1 ca (4.5) θRFrom (4.5), we can decompose as 3210111sin0110sin1cos1RRRR =⎥⎥⎦⎤⎢⎢⎣⎡−⎥⎦⎤⎢⎣⎡⎥⎥⎦⎤⎢⎢⎣⎡−=θθθθθ1sincosθ (4.6) ⎥⎥⎦⎤⎢⎢⎣⎡−−⎥⎦⎤⎢⎣⎡−⎥⎥⎦⎤⎢⎢⎣⎡−−==−−−−10sin1cos11sin0110sin1cos11112131θθθθθRRRθR (4.7) The coefficients in the factorization of (4.6) can be quantized to SOPOT coefficients to form ⎥⎦⎢⎣⎥⎦⎢⎣⎥⎦⎢⎣=≈10110θθθβSRθαθβ⎤⎡⎤⎡⎤⎡1011θθαα (4.8) where and are respectively SOPOT approximations to ()θθsin1cos−θ and sink1=θαk}{r− 1} having the form in (4.9). kbtka 2∑= (4.9) where a, 1, , …, −, 0, 1, …, r, {1−∈ bk∈r is the range of the coefficients and is the number of terms used in each coefficients. The variable t is usually limited so that the multiplication can be implemented with limited number of addition and shift operations. The integer FFT converges to the DFT when increases. tt The lifting structure has two advantages over butterfly structure. First, the number of real multiplications is reduced from four to three, although the number of additions is increased from two to three (see Fig. 4.2 and Fig 4.3). Second, the structure allows forquantization of the lifting coefficients and the quantization does not destroy the PR property. To be specific, instead of quantizing the elements of []θR in (4.2) directly, the lifting coefficients, s and ()cs 1−18 are quantized and therefore, the inversion also consists of three lifting steps with the same lifting coefficients but with opposite signs. Example 4.1 () 83In case of the twiddle factor, W, 4θ=−π, and 12sin1cos −=−θθ21sin −=θ4.0=θ7.0=θβ. If we round these numbers respectively to the right-hand one digit of the decimal point, then and . α ⎥⎤⎢⎡104.01⎦⎣⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡=17.001104.01θS ⎥⎦⎤⎢⎣⎡−⎥⎦⎤⎢⎣⎡⎥⎦⎤⎢⎣⎡−=−104.0117.001104.011θSθβ For any real numbers of and in the lattice structure, θαIS =−θθ11838WS. In summery, in implementing a complex number multiplication a twiddle factor in matrix form has a butterfly structure and if we round coefficients, its inverse is computationally complex, but if we decompose the twiddle factor into a lifting structure, the twiddle factor has a perfect