1. Field of the Invention
The present invention relates to the FFT (Fast Fourier Transform) used in an OFDM (Orthogonal Frequency Division Multiplexing) system, and more particularly to an FFT method for processing input signals in parallel in order to quickly process the input signals.
2. Description of the Related Art
The basic principle of the OFDM (Orthogonal Frequency Division Multiplexing) system is to convert input data having a high data rate into parallel data which have a low data rate, where the number of parallel data is equal to the number of sub-carriers, and to carry the parallel data on the sub-carriers, respectively, to transmit the data in parallel. The OFDM can reduce relative distortions in the time domain by a multi-path delay spread since the symbol duration of the sub-carrier having the low data rate is increased, and can remove an inter-symbol interference by inserting a protection section that is longer than the delay spread of the channel between OFDM symbols.
Since the OFDM modulation/demodulation is performed using a plurality of sub-carriers, it is quite difficult to work out its hardware design as the number of sub-carriers is increased. Also, due to the difficulty in keeping the orthogonality between the sub-carriers, it becomes difficult to actually implement the system. Although this problem can be solved by adopting a DFT (Discrete Fourier Transform), the DFT has a drawback in that it requires a large amount of computation. In order to reduce the large amount of computation that is the drawback of the DFT, an FFT (Fast Fourier Transform) has been proposed. Specifically, in the OFDM system, an N-point DFT is required. However, as N increases, the amount of DFT computation also increases in proportion to N2. Accordingly, it is required to provide an algorithm that can efficiently compute the DFT even if N is large. The FFT is an algorithm that remarkably reduces the amount of DFT computation by successively dividing a sequence having a length of N into sequences having a length shorter than N.
The FFT of the OFDM performs a computation of a complex number that is composed of a real part and an imaginary part. Accordingly, the real part and the imaginary part are separately inputted by hardware, and in designing a processor that performs the FFT, an inverse FFT (IFFT) can be performed by changing the positions of the real part and the imaginary part with each other. The FFT may be implemented in an array type or in a pipeline type. The array FFT structure is very complicated and enlarged by hardware, and thus its implementation is almost impossible if the number of FFT computation points is large. By contrast, the pipeline FFT structure is regular, is relatively easy to control and makes a serial input/output possible, and thus it is most frequently used in application fields that require a high performance.
Hereinafter, the DFT and the FFT will be explained in order. Signals having a predetermined period which are expressed by the DFT are defined by Equation (1):
                              X          ⁡                      (            k            )                          =                              ∑                          n              =              O                                      N              -              1                                ⁢                                          ⁢                                    x              ⁡                              (                n                )                                      ⁢                          ⅇ                              j                ⁢                                                      2                    ⁢                                                                                  ⁢                    π                                    N                                ⁢                nk                                                                        (        1        )            
wherein N denotes the number of signals, k denotes 0 to N−1, x(n) denotes an input signal and X(k) denotes an output signal. As described in Equation (1), the amount of DFT computation is increased as the value of N is increased.
FIG. 1 is a view exemplifying a process of performing a conventional FFT. Hereinafter, an algorithm that performs the conventional FFT will be explained in detail with reference to FIG. 1.
In particular, FIG. 1 describes a case in which the point (N) of the FFT is 16. Signals inputted to the FFT are x[0] to x[15]. Hereinafter, for the convenience in explanation, horizontal lines from x[n] to X[n] are called computation lines. Referring to FIG. 1, the FFT is composed of first to 16th computation lines. x[0] is divided at point a and transferred to the first computation line and the ninth computation line at point b. x[1] is divided at the point a and transferred to the second computation line and the tenth computation line at the point b. x[14] is divided at the point a and transferred to the seventh computation line and the 15th computation line at the point b. x[15] is divided at the point a and transferred to the eighth computation line and the 16th computation line at the point b.
The first to eighth computation lines at the point b add the transferred signals and output the added signals, and the ninth to 16th computation lines at the point b subtract the transferred signals and output the subtracted signals. The signals outputted from the point b are transferred to point c. The computation lines at the point c perform the same operations as the computation lines at the point a.
The first to fourth computation lines and the ninth to 12th computation lines at point d add the transferred signals and output the added signals, and the fifth to eighth computation lines and the 13th to 16th computation lines at the point d subtract the transferred signals and output the subtracted signals. The signals outputted from the point d are transferred to point e. The computation lines at the point e perform the same operations as the computation lines at the point a. The first to second computation lines, the fifth to sixth computation lines, the ninth to tenth computation lines and the 13th to 14th computation lines at point f add the transferred signals and output the added signals. The third to fourth computation lines, the seventh to eighth computation lines, the 11th to 12th computation lines and the 15th to 16th computation lines at the point f subtract the transferred signals and output the subtracted signals. The signals outputted from the point d are transferred to the point e.
The signals outputted from the point f are transferred to point g. The computation lines at the point g perform the same operations as the computation lines at the point a. The odd-numbered computation lines at point h add the transferred signals and output the added signals, and the even-numbered computation lines at the point h subtract the transferred signals and output the subtracted signals. Through the above-described process, the FFT is performed with respect to the input signals.
However, the FFT has the problems in that as the computation points N are increased, it takes a lot of time to process the input signals. This is because the FFT as illustrated in FIG. 1 does not process all the signals in parallel, but processes only a part of the signals in parallel. Accordingly, the necessity of an FFT that can quickly process the input signals is on the rise.