Abstract:
A Fast Fourier Transform (FFT) processor is provided. It comprises a multiplexer, a first angle rotator, a second angle rotation and multiplexing unit, an adder, a twiddle factor storage, a multiplier, and a data storage. The FFT processor analyzes the input/output order of the Fast Fourier Transformation, separates the portions requiring complex computations, simplifies the hardware thereof, and adjusts the output order. It not only effectively saves the hardware area, but also reduces the computations and memory access count. Thereby, the power consumption is reduced.

Description:
FIELD OF THE INVENTION  
       [0001]     The present invention generally relates to Fast Fourier transform (FFT), and more specifically to a Fast Fourier Transform processor.  
       BACKGROUND OF THE INVENTION  
       [0002]     As the mobile communication becomes more ubiquitous, the bandwidth demands of wireless local area network (WLAN) also increases. In the IEEE802.11a specification, proposed to meet the demands, the Fast Fourier Transform (FFT) computation unit is an important role of modulation. The FFT computation unit is able to transform the data on the frequency domain into corresponding data on the time domain. This feature allows improvement of the signal attenuation and multi-path interference problems often faced in the wireless communication. Therefore, the present and future communication specifications will continue to utilize FFT computation. However, the wireless communication hardware must be able to support the large amount of computation.  
         [0003]     The structures of conventional FFT circuitry are categorized into three types: single-memory, dual-memory, and pipeline. The single-memory structure uses only one computation unit and utilizes the in-place computation feature of the FFT; therefore, it uses the smallest circuitry area. However, this type of structure has the disadvantage of high computational latency. The dual-memory structure uses a memory to store input and the other to store output; therefore, it provides a higher throughput than the single-memory structure. Nevertheless, it takes Log r N computation units (r, N are positive integers), and requires the largest circuitry area.  
         [0004]     Discrete Fourier Transform (DFT) is defined as follows:  
         X   ⁡     [   k   ]       =       ∑     n   =   0       N   -   1       ⁢           ⁢       x   ⁡     [   n   ]       ⁢     w   N   kn             
 
         [0005]     Where k=0,1, . . . ,N-1, n=0,1, . . . , N-1, and W N =e −j2 π/N  is a twiddle factor.  
         [0006]      FIG. 1  shows a schematic view of a conventional FFT processor structure. In 2002, Lenart proposed, in “A Pipelined FFT Processor Using Data Scaling with Reduced Memory Requirements” (Proc. Of Norchip, Nov. 11-12, 2002, Copenhagen, Denmark), a pipeline structure using a base of four for FFT processor. The proposed structure takes three stages to process 64 points, and requires three multipliers and accesses the rotation factors three times. There are up to six first-in-first-out (FIFO) buffers to access in each clock.  
         [0007]      FIG. 2  shows a schematic view of another conventional FFT processor structure. In 2003, Maharatna proposed, in “A Novel 64-Point FFT/IFFT Processor for IEEE802.11a Standard” (ICASSP 2003), FFT processor structure using a base of 8. As shown in  FIG. 2 , the structure processes the 64-point FFT computation by expanding two 8-based butterflytype computation units and eight output units with specialized hardware connection. Although this structure reduced the latency, it requires more hardware computation units.  
         [0008]      FIG. 3  shows a schematic view of yet another conventional FFT processor structure. In 2002, Guo proposed, in “A New Hardware-Efficient Design Approach for the 1D Discrete Fourier Transform” (Pattern Recognition and Image Analysis, Vol. 12, No. 3, 2002, pp. 299-307), a one-dimensional structure for a DFT processor. As shown in  FIG. 3 , the structure separates the computation of odd part and the even part, and requires a larger hardware circuitry area.  
         [0009]     There are numerous structures for conventional FFT processors. The objects of an FFT processor are to use the least hardware area and cost, have the least time delay, and consume least energy. The aforementioned structures have the disadvantages of frequent accesses to memory, large amount of multiplication computations, and requiring a large number of computational units.  
       SUMMARY OF THE INVENTION  
       [0010]     The present invention has been made to overcome the aforementioned drawback of conventional FFT processors. The primary object of the present invention is to provide an FFT processor, comprising a multiplexer, a first angle rotator, a second angle rotation and multiplexing unit, an adder, a twiddle factor storage, a multiplier, and a data storage. The processor reduces the hardware circuitry area, cost, as well as the technical complexity.  
         [0011]     According to the present invention, the multiplexer is to select an input set of N data items from a plurality of N-item sets, and outputs a set of N data items. N is an M-th power of 2, and M is an integer greater than or equal to 3. The first angle rotator receives the N/2 data items from the N-item set, rotates the received N/2 data items for a first angle, and outputs the N/2 rotated data items sequentially. The second angle rotation and multiplexing unit receives a set of N data items and N/2 rotated data items. The second angle rotation and multiplexing unit must either select the N data items within a first preset duration or select N/2 data items from the N data items to combine with the rotated N/2 data items within the second preset duration, and rotates them for a second angle. Finally, the second angle rotation and multiplexing unit outputs the rotated N data items sequentially.  
         [0012]     The adder adds the N rotated data items sequentially, and outputs a sum in frequency domain of the N rotated data items. The twiddle factor storage stores all the twiddle factors of an N-point FFT. The multiplier multiplies the sum in frequency domain with the corresponding twiddle factor sequentially, and outputs a mean data. The storage receives and stores the mean data sequentially, and outputs N data items to the multiplexer for the next stage computation.  
         [0013]     The FFT processor of the present invention further includes a first register array and a second register array. The first register array is located between the multiplexer and the second angle rotation and multiplexing unit. The second register array is located between the first angle rotator and the second angle rotation and multiplexing unit.  
         [0014]     The present invention is to analyze the input/output order of the computations in the FFT, extract the part that requires complex computation for simplifying hardware, and adjust the output order. This not only reduces the hardware circuitry area, cost, and technical complexity, but also reduces the computation, memory accesses and energy consumption.  
         [0015]     The foregoing and other objects, features, aspects and advantages of the present invention will become better understood from a careful reading of a detailed description provided herein below with appropriate reference to the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0016]      FIG. 1  shows a schematic view of the structure of a conventional FFT processor.  
         [0017]      FIG. 2  shows a schematic view of the structure of another conventional FFT processor.  
         [0018]      FIG. 3  shows a schematic view of the structure of yet another conventional FFT processor.  
         [0019]      FIG. 4  shows a schematic view of the structure of a FFT processor according to the invention.  
         [0020]      FIG. 5  shows a table of the relation between the input and the output of the DFT.  
         [0021]      FIG. 6  shows the re-arranged computation order of the DFT.  
         [0022]      FIG. 7  shows a table of the relation between the input and the output of the DFT after extracting W( 1 , 8 ) and re-arranging the order.  
         [0023]      FIG. 8A  shows the addition of a register array in  FIG. 4  for temporary storage of input and output.  
         [0024]      FIG. 8B  shows the storing and the sequence arrangement of the data flow within the first preset duration according to the present invention.  
         [0025]      FIG. 8C  shows the storing and the sequence arrangement of the data flow within the second preset duration according to the present invention.  
         [0026]      FIG. 9  shows a table of the twiddle factors in a 64-point FFT.  
         [0027]      FIG. 10  shows a hardware structure of the first angle rotator of the present invention using N=8 as an embodiment.  
         [0028]      FIG. 11  shows the functional comparison between the FFT processor of the present invention and conventional FFT processors. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS  
       [0029]      FIG. 4  shows a schematic view of the structure of a FFT processor of the present invention. Referring to  FIG. 4 , FFT processor  400  comprises a multiplexer  41 , a first angle rotator  42 , a second angle rotation and multiplexing unit  43 ; an adder  44 , a twiddle factor storage  45 , a multiplier  46  and a storage  47 . Multiplexer  41  selects an input set of N data items from a plurality of N-item sets, and outputs a set of N data items. N is an M-th power of 2, and M is an integer greater than or equal to 3. First angle rotator  42  receives N/2 data items from the N-item set, rotates the received N/2 data items for a first angle, and outputs the N/2 rotated data items sequentially. Second angle rotation and multiplexing unit  43  receives a set of N data items and the N/2 rotated data items. Second angle rotation and multiplexing unit  43  must either select the N data items within a first preset duration or select N/2 data items from the N data items to combine with the rotated N/2 data items within the second preset duration, and rotates them for a second angle. Finally, second angle rotation and multiplexing unit  43  outputs the rotated N data items sequentially.  
         [0030]     Adder  44  adds the N rotated data items sequentially, and outputs a sum in frequency domain of the N rotated data items. Twiddle factor storage  45  stores all the twiddle factors of an N-point FFT. Multiplier  46  multiplies the sum in frequency domain of the rotated data with the corresponding twiddle factor sequentially, and outputs a mean data. Storage  47  receives and stores the mean data sequentially, and outputs N data items to multiplexer  41  for the next stage computation.  
         [0031]     Without the loss of generality, the following description uses N=8 to explain the structure and the operation of the present invention.  
         [0032]      FIG. 5  shows a table of the relation between the input and the output of the Discrete Fourier Transform (DFT), and  FIG. 6  shows the re-arranged computation order of the DFT. As shown in  FIG. 5 , the corresponding input will require the complex multiplication W( 1 , 8 )=e −j2π/8  only when the sequence order is 1, 3, 5 and 7. Therefore, by re-arranging the sequence order as shown in  FIG. 6 , the original outputs for sequence order 1, 3, 5, and 7 which require rotation become the outputs for sequence order 4, 5, 6, and 7. By postponing the output of the four data items, the multiplication computation of the complex number W( 1 , 8 ) of the four data items can be performed and the results can be stored in the registers at the same time when the first four data items are being outputted. When computing the fifth output, the stored data items can be used as input because the multiplication has been completed.  
         [0033]      FIG. 7  shows the relation between the input and the output of the DFT after extracting W( 1 , 8 ) and re-arranging the order. The table shown in  FIG. 7  can be obtained by separating the W( 1 , 8 ) complex multiplication with a butterfly-type FFT processor having a base of 8. The remaining computation can be completed with a butterfly-type FFT processor having a base of 4. The present invention does not use the algorithm with root value 2 2  to realize the butterfly-FFT because the memory arrange is not compatible and the butterfly-FFT having a base 4 can reduce the computation delay with a carry save adder (CSA) structure.  
         [0034]     Therefore, the actual computation can be divided into two categories. The first category includes the four outputs (X( 1 ),X( 3 ),X( 5 ),X( 7 )) which must past the W( 1 , 8 )=2π/8 angle rotator and a butterfly-type FFT processor having a base  4 . The second category includes the four outputs (X( 0 ),X( 2 ),X( 4 ),X( 6 )) which only requires passing a butterfly-type FFT processor having a base  4  without passing an angle rotator. By re-arrangement of the time sequence, the time for computing the FFT for the second category can be used to compute the rotation W( 1 , 8 ) for the first category. In this way, the efficiency of the computation units, such as for twiddle factor multiplication and the adder for butterfly-type FFT having a base of 8, is improved.  
         [0035]      FIG. 8A  adds register arrays to the structure shown in  FIG. 4  for providing the storage of input and the output. As shown in  FIG. 8A , an FFT processor  800  uses a storage  47 , a first register array  88 , and a second register array  89  to provide the bandwidth required by the input and the storage required by the output. First angle rotator  42  is realized with a shifter and an adder (will be discussed in  FIG. 10 ). By utilizing the concept of time-sharing, the hardware circuitry is reduced by two-third. Second angle rotator  43  is realized with the cross-line and part of an inverter. The compensation items required in the 2-based complimentary computation are left to adder  44  for finishing the computation. This will greatly reduce the power consumption caused by the carry item.  
         [0036]      FIG. 8B  and  FIG. 8C  show the storing and the sequence arrangement of the data flow within the first and the second preset durations according to the present invention, respectively.  
         [0037]      FIG. 8B  shows the storing and the sequence arrangement of the data flow within the first preset duration according to the present invention. Multiplexer  41  selects a set from two 8-item sets for input, and outputs an 8-item set. As shown in  FIG. 8B , second rotating and multiplexing unit  43  receives an 8-item set from first register array  88  (shown as solid line) within the first preset duration. When second rotating and multiplexing unit  43  and adder  44  are computing frequency domain data X( 0 ), X( 2 ), X( 4 ), and X( 6 ), first angle rotator  42  receives (shown as dash line) the other four items X( 1 ), X( 3 ), X( 5 ), and X( 7 ) for rotating 2π/8, and then stores the 2π/8-rotated items into second register array  89 .  
         [0038]      FIG. 8C  shows the storing and the sequence arrangement of the data flow within the second preset duration according to the present invention. As shown in  FIG. 8C , second rotating and multiplexing unit  43  selects the remaining four items (X( 0 ), X( 2 ), X( 4 ), and X( 6 )) to combine with the four rotated items (shown as solid line) to form the input within the second preset duration. The rotation of 2π/4 is performed on the input  8  items, and the results are outputted in a sequential order. Adder  44  sequentially adds the 8 rotated items and outputs the frequency domain data X( 1 ), X( 3 ), X( 5 ), and X( 7 ).  
         [0039]     Take N=8 as an example. The present invention uses an FFT having a base of 8. As pointed out by Yeo (Low Power Implementation of FFT/IFFT Processor for IEEE 802.11a Wireless LAN Transceiver), the design using the base  8  consumes the least amount of power. In applications, IEEE 802.11a specification demands a 64-point FFT structure. Therefore, the present invention uses two cycles of computation to implement the 64-point FFT, that is, two stages of computation. This not only saves the computation, but also saves the memory access (twiddle factor storage  45  and storage  47 ); therefore, the power consumption is reduced.  
         [0040]     The output of adder  44  is the end of the first stage. To implement the 64-point FFT, the corresponding twiddle factors must be read from twiddle factor storage  45 .  FIG. 9  shows a table for the twiddle factors for 64-point FFT. The frequency domain data X( 0 )-X( 8 ) are required to be multiplied by the twiddle factor W( 0 , 64 )=e −(j2π/64))*0 =1, and X( 9 ) must be multiplied by the twiddle factor W( 1 , 64 )=e −(j2π/64)*1 , X( 63 ) must be multiplied by the twiddle factor W( 49 , 64 )=e −(j2π/64)*49 , and so on.  
         [0041]     In the 64-point FFT, the first batch of frequency domain data X( 0 ), X( 8 ), X( 16 ), X( 24 ), X( 32 ), X( 40 ), X( 48 ), and X( 56 ) outputted by adder  44  of the first stage are multiplied by the corresponding twiddle factors in the multipliers, and stored in storage  47 . After the entire  64  points finish the first stage computation, the second stage computation will start.  
         [0042]     In general, one of the major difficulties in implementing an 8-based FFT circuitry is the rotation of the 2π/8 angle. This rotation requires two real-number multipliers and a real-number adder. The rotation can be expressed with the twiddle factor in the FFT and become the complex-number multiplication  
         W   ⁡     (     1   ,   8     )       =       ⅇ     -     (     j   ⁢       2   ⁢           ⁢   π     8       )         .         
 
 However, in the structure of the present invention, the simplification of the W( 1 , 8 ) becomes:  
         a   ×     ⅇ     -     (     j   ⁢       2   ⁢           ⁢   π     8       )           =       a   ×     (       2     2     )     ×     (     1   +   j     )       ≅     a   ×     (       2     -   1       +     2     -   3       +     2     -   4       +     2     -   6       +     2     -   8       +     2     -   9         )     ×     (     1   +   j     )             
 
 which can be further re-arranged as:  
           a   ×     ⅇ     -     (     j   ⁢       2   ⁢           ⁢   π     8       )           ≅     a   ×     (       2     -   1       +     2     -   3       +     2     -   4       +     2     -   6       +     2     -   8       +     2     -   9         )         =       (     a   ×     (       2     -   1       +     2     -   3       +     2     -   4         )       )     ×     (     1   +     2     -   5         )     ×     (     1   +   j     )           
 
 By doing this, the complex-number multiplication is simplified as computation that can be performed by a shift adder; thus, this improves the hardware circuitry area and the computation delay. 
 
         [0043]      FIG. 10  is the hardware structure of the first angle rotator of the present invention, with N=8 as an example. As shown in  FIG. 10 , the first angle rotator of the present invention implements the last stage of summation with the carry save adder (CSA) structure so as to avoid the delay and the power consumption caused by the carry operation. Because the delay caused by the carry ripple adder (CRA) is proportional to the number of bits of the input, and the delay of each stage in the CSA is a fixed amount of time, the structure can accomplish the computation faster.  
         [0044]      FIG. 11  shows the hardware structure and functionality comparison between the FFT processor of the present invention and conventional techniques. As shown in the table, the FFT processor of the present invention has the advantages of simple control mechanism, efficient computation, requiring less computation units and requiring less memory.  
         [0045]     In summary, the FFT processor of the present invention uses the temporary register storage for the intermediate computation results and re-arranges the sequence order of each operand so that the required operands can be pre-loaded into the registers. Therefore, the higher bandwidth of the registers can be achieved.  
         [0046]     Although the present invention has been described with reference to the preferred embodiments, it will be understood that the invention is not limited to the details described thereof. Various substitutions and modifications have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. Therefore, all such substitutions and modifications are intended to be embraced within the scope of the invention as defined in the appended claims.