INTRODUCTION

THE DISCRETE FOURIER TRANSFORM (DFT) is one of the most funtamental operations in digital signal processing. Because of the efficiency of the convolutional property, the DFT is often used in linear filtering found in many applications such as quantum mechanics, noise reduction and image re-construction. However, the computational requirements for completing the DFT of a finite length signal are relatively intensive. In particular, if the input signal has length N, directly calculating its DFT requires N 2 complex multiplications (4N 2 real multiplications) and some additional additions. In 1965, Cooley and Tukey introduced the fast Fourier transform (FFT), which efficiently and significantly reduces the computational cost of calculating N-point DFT from N 2 to Nlog 2 N . Since then, there have been numerous further developments that extended Cooley and Tukeyâ„¢s original contribution. Many efficient structures for

computing DFT have been discovered by taking advantage of the symmetry and periodicity properties of the roots of unity such as the radix-2 FFT, radix-4 FFT,and split-radix FFT.

The order of the multiplicative complexity is commonly used to measure and compare the efficiency of the algorithms since multiplications are intrinsically more complicated among all operations.It is well-known in the field of VLSI that among the digital arithmetic operations (addition, multiplication, shiftingand addressing, etc.), multiplication is the operation that consumes most of the time and power required for the entire computation and, therefore, causes the resulting devices to be large and expensive. Therefore, reducing the number of multiplications in digital chip design is usually a desirable task. In this paper, utilizing the existing efficient structures, a novel structure for approximating the DFT is presented. This proposed structure is shown to be a reversible integer-to-integer mapping called Integer FFT (IntFFT). All coefficients can be represented by finite-length binary numbers. The complexity of the proposed IntFFT

will be compared with the conventional fixed-pointimplementation of the FFT (FxpFFT). Moreover, the performances of the new transforms are also tested in noise reduction problem.

The invertibility of the DFT is guaranteed by orthogonality.The inverse (the IDFT) is just the conjugate transpose. Inpractice, fixed-point arithmetic is often used to implement the DFT in hardware since it is impossible to retain infinite resolution of the coefficients and operations. The complex coefficients of the transform are normally quantized to a certain number of bits depending on the tradeoff between the cost (or power) and the accuracy of the transform. However, direct quantization of the coefficients used in the conventional structures, including both direct and reduced-complexity (e.g., radix-2, radix-4, etc.) methods, destroys the invertibility of the transform. The novel approach presented in this paper guarantees the invertibility property of the transform while keeping the coefficients of the forward and inverse transforms to be finite-length binary numbers. Previous Works: Recently, there has been a reasonable amount of attention in trying to approximate the existing floating-point orthogonal transforms such as the DCT or DFT with invertibility property preserved. In, the eight-point DCT used in the image and video coding standards is approximated by a brute-force technique, i.e., the transform coefficients are optimized over the set of real integers1 by having the orthogonality property (a system of nonlinear equations) as a constraint. The same approach is extended to the case of the eight -point DFT whose coefficients are selected from the set of complex integers. Although this approach is simple and straight forward, it is very difficult to extend the approach to the case of large N . It would involve solving a big system of nonlinear equations. In addition, once a set of coefficients is obtained, it is not trivial as to how to adjust them for different transform accuracy unless one reoptimizes the coefficients.

Lifting factorization is proposed to replace the orthogonal matrices appearing in the eight-point DCT using, respectively, the fast structure and the Hadamard structure . The resulting transforms are shown to be simple and invertible, even though the lifting coefficients are quantized and are power-adaptable, i.e., different quantization step sizes can be used to quantize the lifting coefficients without destroying the invertibility. In this

paper, lifting factorization is proposed to be used in the fast structures of the DFT where complex multiplications are expressed in terms of liftings. The approach can be used in many existing structures such as radix-2, radix-4, and split-radix with arbitrary sizes. However, the split-radix structure will be used to illustrate the proposed method, which canalso be extended to other existing FFT structures as well.

PREFACE

The DSP world today is ruled by different transforms. Discrete Fourier transforms are most used. So is the fast Fourier transform, which is the faster version of DFT.

Suppose we take FFT of a signal. On taking the inverse fast Fourier transform,we except the output to be the same as the input.This is called the invertibility property.But on most occasions, dissapointment is the result. This is due to the finite word length of the registers used to store the samples and the coefficients.

This seminars introduces a method called integer fast Fourier transforms to give the invertibility property to FFT, without in any way destroying its accuracy and speed.

It first reviews the necessary backgrounds to understand the concept including the discrete Fourier transform and split-radix FFT,its fixed point implimentation,and lifting scheme. Then the basics are applied to split radix FFT to describe the integer fast Fourier transforms.The accuracy and complexity of the proposed approach is then discussed.The final section gives the use of the IntFFT in noise reduction application and compares its performance with the FxpFFT.

ABSTRACT

Fourier transform for approximating the discrete Fourier transform, which is one of the most fundamental operations in digital signal processing, is introduced.

Unlike fixed- point fast Fourier transform, the new transform has the properties that it is an integer-to-integer mapping, is power adaptable and is reversible. In this paper, a concept of integer fast Fourier transform for approximating the discrete Fourier transform is introduced .

The transform can be implemented by using only bit shifts and additions and no multiplication. A method for minimizing the no of additions required is presented. While preserving the reversibility, the integer FFT is shown experimentally to yield same accuracy as the fixed-point FFT when their coefficients are quantised to a certain number of bits.

Complexity of the integer FFT is shown to be much lower than that of fixed point FFT in terms of the no of additions and shifts. Finally, the are applied to noise reduction applications, where the integer FFT provides significantly improvement over the fixed-point FFT at low power and maintains similar results at high power.

CONTENTS

Page No.

1. Introduction 4

2. Backgrounds 6

3. Converting complex numbers to real lifting steps 10

4. Resolution of the internal nodes 14

5. Performances and complexities 16

6. Application in noise reduction 22

7. Conclusion 23

8. References 24

INTRODUCTION

THE DISCRETE FOURIER TRANSFORM (DFT) is one of the most funtamental operations in digital signal processing. Because of the efficiency of the convolutional property, the DFT is often used in linear filtering found in many applications such as quantum mechanics, noise reduction and image re-construction. However, the computational requirements for completing the DFT of a finite length signal are relatively intensive. In particular, if the input signal has length N, directly calculating its DFT requires N 2 complex multiplications (4N 2 real multiplications) and some additional additions. In 1965, Cooley and Tukey introduced the fast Fourier transform (FFT), which efficiently and significantly reduces the computational cost of calculating N-point DFT from N 2 to Nlog 2 N . Since then, there have been numerous further developments that extended Cooley and Tukeyâ„¢s original contribution. Many efficient structures for

computing DFT have been discovered by taking advantage of the symmetry and periodicity properties of the roots of unity such as the radix-2 FFT, radix-4 FFT,and split-radix FFT.

The order of the multiplicative complexity is commonly used to measure and compare the efficiency of the algorithms since multiplications are intrinsically more complicated among all operations.It is well-known in the field of VLSI that among the digital arithmetic operations (addition, multiplication, shiftingand addressing, etc.), multiplication is the operation that consumes most of the time and power required for the entire computation and, therefore, causes the resulting devices to be large and expensive. Therefore, reducing the number of multiplications in digital chip design is usually a desirable task. In this paper, utilizing the existing efficient structures, a novel structure for approximating the DFT is presented. This proposed structure is shown to be a reversible integer-to-integer mapping called Integer FFT (IntFFT). All coefficients can be represented by finite-length binary numbers. The complexity of the proposed IntFFT

will be compared with the conventional fixed-pointimplementation of the FFT (FxpFFT). Moreover, the performances of the new transforms are also tested in noise reduction problem.

The invertibility of the DFT is guaranteed by orthogonality.The inverse (the IDFT) is just the conjugate transpose. Inpractice, fixed-point arithmetic is often used to implement the DFT in hardware since it is impossible to retain infinite resolution of the coefficients and operations. The complex coefficients of the transform are normally quantized to a certain number of bits depending on the tradeoff between the cost (or power) and the accuracy of the transform. However, direct quantization of the coefficients used in the conventional structures, including both direct and reduced-complexity (e.g., radix-2, radix-4, etc.) methods, destroys the invertibility of the transform. The novel approach presented in this paper guarantees the invertibility property of the transform while keeping the coefficients of the forward and inverse transforms to be finite-length binary numbers. Previous Works: Recently, there has been a reasonable amount of attention in trying to approximate the existing floating-point orthogonal transforms such as the DCT or DFT with invertibility property preserved. In, the eight-point DCT used in the image and video coding standards is approximated by a brute-force technique, i.e., the transform coefficients are optimized over the set of real integers1 by having the orthogonality property (a system of nonlinear equations) as a constraint. The same approach is extended to the case of the eight -point DFT whose coefficients are selected from the set of complex integers. Although this approach is simple and straight forward, it is very difficult to extend the approach to the case of large N . It would involve solving a big system of nonlinear equations. In addition, once a set of coefficients is obtained, it is not trivial as to how to adjust them for different transform accuracy unless one reoptimizes the coefficients.

Lifting factorization is proposed to replace the orthogonal matrices appearing in the eight-point DCT using, respectively, the fast structure and the Hadamard structure . The resulting transforms are shown to be simple and invertible, even though the lifting coefficients are quantized and are power-adaptable, i.e., different quantization step sizes can be used to quantize the lifting coefficients without destroying the invertibility. In this

paper, lifting factorization is proposed to be used in the fast structures of the DFT where complex multiplications are expressed in terms of liftings. The approach can be used in many existing structures such as radix-2, radix-4, and split-radix with arbitrary sizes. However, the split-radix structure will be used to illustrate the proposed method, which canalso be extended to other existing FFT structures as well.

APPLICATION IN NOISE REDUCTION

The performances of the IntFFT and the FxpFFT are tested and compared in noise reduction problem. In Fig. 13(a), the signal of interest s(k) with a known power spectral

density (PSD) ?s is corrupted by an additive independent Gaussian noise with a PSD

?n , resulting in a noisy signal. The received signal is then optimally filtered by a filter h(k) . Fig. 13(b) shows an equivalent block diagram of the noise reduction system processed in frequency domain. The Fourier transform of the received signal X(w) is calculated and multiplied by the filter frequency response H(w). The signal estimate is then obtained by calculating the inverse Fourier transform of the product. shows the mean square error

between the signal estimate S (k) and the original signal S(k) over the range of Nc .The solid line is obtained by using the FxpFFT and its inverse, whereas the dash line is obtained by using the IntFFT and its inverse. As increases, the mean square errors of both cases decrease, approaching the dash-dot line, which is when the exact FFT and IFFT are used. It is evident that when the coefficients are severely quantized (2 ? Nc ? 7 ), the mean square error in the case of IntFFT is lower than that in the case of FxpFFT by up to 18%. This is because when is small, the reconstruction error of the FxpFFT and its inverse tends to dominate the reconstruction signal. On the other hand, at high resolution ( Nc>7), both IntFFT and FxpFFT yield similar results, which are very close to the case of the exact FFT as indicated in the enlarged portion of the curves in.

CONCLUSION

In this paper, we have presented a concept of IntFFT, which can be used to construct FFT with integer coefficients. It provides a new method for approximating the DFT without using any multiplication and can simply be applied to the case of large-size DFT. Unlike the FxpFFT, which is the fixed-point arithmetic version of FFT, the IntFFT is reversible when the coefficients are quantized. Its inverse IntIFFT can be computed with the same computational cost as that of the forward transform. The new transform is suitable for mobile computing and any handheld devices that run on batteries since it is adaptable to available power resources. Specifically, the coefficients appearing in the proposed structures can be quantized directly for different resolutions, i.e., different computational costs, while preserving the reversibility property. Although a large class of FFT structures such as radix-2, radix-4, and split-radix can be approximated by this approach, the split-radix structure is used to illustrate the technique. An analysis of the dynamic range of the internal nodes is presented. Using an appropriate choice of lifting factorizations, it is proven that lifting approximation of a complex multiplier can increase the resolution of the input by at most one bit. An upper bound of the dynamic range of the internal nodes is estimated and confirmed by a simulation for the case of the split-radix FFT. The computational complexity of the resulting transform is calculated by the numbers of real additions and shifts. A method for minimizing the number of additions is presented and used to compare the computational costs of IntFFT and FxpFFT. According to the simulation, the complexity of IntFFT is lower than that of FxpFFT by a significant margin. The accuracy of the transforms is compared experimentally. It is evident from the simulations that both IntFFT and FxpFFT have approximately the same distortion from ideal FFT when the resolution of the input Ni is greater than Nc . When Nc ? Ni ,

the FxpFFT yields 3 dB higher accuracy. The results are different when testing with the convolutional rule, where the IntFFT and the FxpFFT provide essentially the same accuracy for any value of Nc . When the inverse transform is performed after the forward transform, fixed-point arithmetic approach results in reconstruction error, whereas the proposed approach can reconstruct the input perfectly for any fixed resolution of the coefficients. Finally, these two implementations are tested in noise reduction application. At low power, i.e., the coefficients are quantized to low resolution, the IntFFT yields significantly better results than the FxpFFT, and they yield similar results at high power.

REFERENCES

(1). Soontorn Oriantara, Ying-Jui Chen and Troung Q. Nguyen , Integer Fast Fourier Transform, IEEE transactions on signal processing , Vol.50, No.3, pp 607-618, March 2002.

(2). A. V. Oppenheim and R.W. Schaffer, Discrete-time Signal Processing, Pearson Education (P) Ltd.

(3). J. G. Proakis and D. G. Manolakis, Digital Signal Processing : Principles, Algorithms and Applications, Pearson Education (P) Ltd.

Download the Full Seminar Reprt

Download
Mirror