23-06-2012, 11:10 AM
Fourier transformation
[attachment=25182]
INTRODUCTION
The Fourier transform is a mathematical operation with many applications in physics and engineering that expresses a mathematical function of time as a function of frequency, known as its frequency spectrum; Fourier's theorem guarantees that this can always be done. For instance, the transform of a musical chord made up of pure notes (without overtones) expressed as amplitude as a function of time, is a mathematical representation of the amplitudes and phases of the individual notes that make it up. The function of times often called the time domain representation, and the frequency spectrum the frequency domain representation. The inverse Fourier transform expresses a frequency domain function in the time domain. Each value of the function is usually expressed as a complex number (called complex amplitude) that can be interpreted as a magnitude and a phase component. The term "Fourier transform" refers to both the transform operation and to the complex-valued function it produces.
Fast Fourier transformation
A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and it’s inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex to group theory and number theory.
A DFT decomposes a sequence of values into components of different frequencies. This operation is useful in many fields (see discrete Fourier transform for properties and applications of the transform) but computing it directly from the definition is often too slow to be practical. An FFT is a way to compute the same result more quickly: computing a DFT of N points in the naive way, using the definition, takes O(N2) arithmetical operations, while an FFT can compute the same result in only O(N log N) operations. The difference in speed can be substantial, especially for long data sets where N may be in the thousands or millions—in practice, the computation time can be reduced by several orders of magnitude in such cases, and the improvement is roughly proportional to N / log(N). This huge improvement made many DFT-based algorithms practical; FFTs are of great importance to a wide variety of applications, from digital signal processing and solving partial differential equations to algorithms for quick multiplication of large integers.
Point Fourier Transformation Chip
FOURTH-GENERATION wireless and mobile systems are currently the focus of research and development. Broadband wireless systems based on orthogonal frequency division multiplexing (OFDM) will allow packet-based high-data-rate communication suitable for video transmission and mobile Internet applications. The IEEE 802.11a standard defines the principal functions and architecture of such a high-data-rate communication system. Apart from the high speed of operation, the system demands low power consumption since it is primarily aimed at portable and mobile applications. A general purpose DSP with associated software is not beneficial for this application since on average, the power consumption of a software solution is an order of magnitude higher compared to a functionally equivalent dedicated hardware solution. Considering this fact we proposed a data path architecture using dedicated hardware for the baseband processor of the above-mentioned standard.
FAST FOURIER TRANSFORMATION
The FFT is a class of efficient DFT implementations that produce results identical to the DFT in far fewer cycles. The Cooley-Tukey algorithm is a widely used FFT algorithm that exploits a divide-and-conquer approach to recursively decomposes the DFT computation into smaller and smaller DFT computations until the simplest computation remains. One subset of this algorithm called Radix-2 Decimation-in-Time (DIT) breaks each DFT computation into the combination of two DFTs, one for even-indexed inputs and another for odd-indexed inputs. The decomposition continues until a DFT of just two inputs remains. The 2-point DFT is called a butterfly, and it is the simplest computational kernel of Radix-2 FFT algorithms.
[attachment=25182]
INTRODUCTION
The Fourier transform is a mathematical operation with many applications in physics and engineering that expresses a mathematical function of time as a function of frequency, known as its frequency spectrum; Fourier's theorem guarantees that this can always be done. For instance, the transform of a musical chord made up of pure notes (without overtones) expressed as amplitude as a function of time, is a mathematical representation of the amplitudes and phases of the individual notes that make it up. The function of times often called the time domain representation, and the frequency spectrum the frequency domain representation. The inverse Fourier transform expresses a frequency domain function in the time domain. Each value of the function is usually expressed as a complex number (called complex amplitude) that can be interpreted as a magnitude and a phase component. The term "Fourier transform" refers to both the transform operation and to the complex-valued function it produces.
Fast Fourier transformation
A fast Fourier transform (FFT) is an efficient algorithm to compute the discrete Fourier transform (DFT) and it’s inverse. There are many distinct FFT algorithms involving a wide range of mathematics, from simple complex to group theory and number theory.
A DFT decomposes a sequence of values into components of different frequencies. This operation is useful in many fields (see discrete Fourier transform for properties and applications of the transform) but computing it directly from the definition is often too slow to be practical. An FFT is a way to compute the same result more quickly: computing a DFT of N points in the naive way, using the definition, takes O(N2) arithmetical operations, while an FFT can compute the same result in only O(N log N) operations. The difference in speed can be substantial, especially for long data sets where N may be in the thousands or millions—in practice, the computation time can be reduced by several orders of magnitude in such cases, and the improvement is roughly proportional to N / log(N). This huge improvement made many DFT-based algorithms practical; FFTs are of great importance to a wide variety of applications, from digital signal processing and solving partial differential equations to algorithms for quick multiplication of large integers.
Point Fourier Transformation Chip
FOURTH-GENERATION wireless and mobile systems are currently the focus of research and development. Broadband wireless systems based on orthogonal frequency division multiplexing (OFDM) will allow packet-based high-data-rate communication suitable for video transmission and mobile Internet applications. The IEEE 802.11a standard defines the principal functions and architecture of such a high-data-rate communication system. Apart from the high speed of operation, the system demands low power consumption since it is primarily aimed at portable and mobile applications. A general purpose DSP with associated software is not beneficial for this application since on average, the power consumption of a software solution is an order of magnitude higher compared to a functionally equivalent dedicated hardware solution. Considering this fact we proposed a data path architecture using dedicated hardware for the baseband processor of the above-mentioned standard.
FAST FOURIER TRANSFORMATION
The FFT is a class of efficient DFT implementations that produce results identical to the DFT in far fewer cycles. The Cooley-Tukey algorithm is a widely used FFT algorithm that exploits a divide-and-conquer approach to recursively decomposes the DFT computation into smaller and smaller DFT computations until the simplest computation remains. One subset of this algorithm called Radix-2 Decimation-in-Time (DIT) breaks each DFT computation into the combination of two DFTs, one for even-indexed inputs and another for odd-indexed inputs. The decomposition continues until a DFT of just two inputs remains. The 2-point DFT is called a butterfly, and it is the simplest computational kernel of Radix-2 FFT algorithms.