# UT Arlington EE 5355 - Integer Fast Fourier Transform (18 pages)

Previewing pages*1, 2, 3, 4, 5, 6*of 18 page document

**View the full content.**## Integer Fast Fourier Transform

Previewing pages
*1, 2, 3, 4, 5, 6*
of
actual document.

**View the full content.**View Full Document

## Integer Fast Fourier Transform

0 0 50 views

- Pages:
- 18
- School:
- University of Texas at Arlington
- Course:
- Ee 5355 - Discrete Transforms and Their Applications

**Unformatted text preview:**

4 4 1 Integer Fast Fourier Transform 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 Lifting factorization can replace the 2 2 orthogonal matrices appearing in fast structures to compute the DFT of input with length of N 2 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 79 x0 A0 x1 y0 A0 A1 A1 x0 y1 x1 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 A0 and called dual lifting whereas the second branch is operated by A1 and is called lifting We can see that the system is PR for any choices of A0 and A1 It should be noted that A0 and A1 can be nonlinear operations like rounding or flooring operations etc x xr jxi a c js Re y ax y yr jyi s s Re x 1 y a c x Im 1 c js a xr xi c yr c s y s Im yi c Figure 4 2 Butterfly structure for implementing a complex multiplication where s sin and c cos I 4 80 y j x j a c js x Re y ax x c 1 s Im y 1 c js a s c 1 s j c 1 s j y Re x 1 x a c 1 s y s Im x Figure 4 3 Lifting structure for implementing a complex multiplication where s sin and c cos I 4 4 3 Algorithms Integer fast Fourier transform algorithm approximates the twiddle factor multiplication I 4 5 Let x xr jxi be a complex number The multiplication of x with a twiddle factor a e j cos j sin is the complex number y ax and can be represented as y 1 cos j sin sin xr 1 cos xi x j R r xi 4 1 where cos R sin sin cos 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 81 1 R 1 2 2 4 4 As and are SOPOT coefficients the term 2 2 cannot in general be represented as SOPOT coefficients The basic idea of the integer or multiplier less transform is to decompose R into three lifting steps If det A 1 and c 0 I 6 A a b 1 c d 0 a 1 c 1 1 0 1 c 1 0 d 1 c 1 4 5 From 4 5 we can decompose R as cos 1 1 0 1 cos 1 1 R sin sin R1 R 2 R 3 sin 1 0 1 1 0 cos 1 1 0 1 cos 1 1 1 1 1 1 R R 3 R 2 R1 sin sin 0 sin 1 0 1 1 4 6 4 7 The coefficients in the factorization of 4 6 can be quantized to SOPOT coefficients to form 1 1 R S 0 1 0 1 1 0 1 4 8 where and are respectively SOPOT approximations to cos 1 sin and sin having the form in 4 9 t a k 2 b 4 9 k k 1 where ak 1 1 bk r 1 0 1 r r is the range of the coefficients and t 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 t increases 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 for 82 quantization 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 s 1 c are quantized and therefore the inversion also consists of three lifting steps with the same lifting coefficients but with opposite signs Example 4 1 In case of the twiddle factor W81 4 cos 1 sin 2 1 and sin 1 2 If we round these numbers respectively to the right hand one digit of the decimal point then 0 4 and 0 7 0 1 0 4 1 0 4 1 S 0 1 0 7 1 0 1 S 1 1 0 4 1 0 1 0 4 1 0 7 1 0 1 0 1 For any real numbers of and in the lattice structure S S I 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 inverse even if we round coefficients Once the coefficients are rounded in the lifting structure the twiddle factor may have either structure for perfect inverse but the lifting structure has one less multiplication An eight point integer FFT based on the split radix structure is constructed in I 4 Figure 4 5 shows the lattice structure of the integer FFT where the twiddle factors W81 and W83 are implemented using the factorization Another integer FFT based on the radix 2 decimation in frequency is covered in I 5 At the expense of precision we …

View Full Document