Abstract:
A memory-based Fast Fourier Transform device is provided, which adopts single-port random access memory (RAM), rather than dual-port RAM, as a storage, and the circuit area of the FFT device is therefore reduced. In order to enhance the access efficiency of the memory and the use efficiency of a processor, the transformer adopts a modified in-place conflict-free addressing to achieve similar performance of a traditional Fast Fourier Transform device.

Description:
BACKGROUND OF THE INVENTION  
       [0001]     1. Field of the Invention  
         [0002]     The invention relates to a Fast Fourier Transform (FFT) device and, more particularly, to a single-port RAM-based FFT device.  
         [0003]     2. Description of Related Art  
         [0004]     FFT is a demodulating method commonly used in high-speed communication systems, and its corresponding modulating method is typically known as Inverse Fast Fourier Transform (IFFT). FFT is evolved from Discrete Fourier Transform (DFT). An N-point DFT can be represented by the following equation:  
                 X   ⁡     (   k   )       =       ∑     n   =   0       N   -   1       ⁢       x   ⁡     (   n   )       ⁢     W   n   nk           ,     
     ⁢       for   ⁢           ⁢   k     =   0     ,   1   ,   …   ⁢           ,     N   -   1     ,     
     ⁢       W   N   nk     =       ⅇ       -   j     ⁢       2   ⁢   π   ⁢           ⁢   nk     N         .               (   1   )             
 
         [0005]     However, equation (1) obviously implies the problem of high computational complexity to thus be replaced by FFT, which has a merit of lower computational complexity. FFT is widely used in high-speed communication systems. Here, a wide marketing broadband access technology, i.e., Asymmetric Digital Subscriber Line (ADSL), is given as a description of a high-speed communication system. The ADSL technology adopts a Discrete Multi-Tone (DMT) method to perform data modulation/demodulation. The DMT method traditionally divides a communication band into multiple orthogonal sub-channels. A downstream/upstream bandwidth is determined according to the communication quality of each sub-channel. DMT provides the good capability of adaptive data transmission so as to provide a better efficiency on the communication band. DMT adopts IFFT/FFT to perform data modulation/demodulation.  
         [0006]     A traditional circuit structure adapted to perform a traditional FFT is similar to that for a traditional IFFT. In this case, the traditional IFFT circuit can be obtained by inversely arranging the traditional FFT circuit appropriately. Since the traditional IFFT circuit is easily obtained by one skilled in the art, the following description focuses on the traditional FFT circuit only.  
         [0007]     Various methods have been used to implement the traditional FFT circuit. For example,  FIG. 1  shows a block diagram of a memory-based FFT device  10 . The device  10  essentially includes a traditional memory  14  and processor  18 . The data processing is completed by using a traditional address controller  20  to generate address of memory  14 , to control the functions of the barrel shifters  12  and  16  according to a sequence value q generated by a sequence value generator  22 , and to further control original data to be processed and then output result data. The original data is preferably a complex word containing a real number and an imaginary number.  
         [0008]     To simplify the circuit complexity of the traditional FFT device  10 , a recursive structure is traditionally used and therefore just one processor  18  needs to be adopted to repeatedly perform the data processing. As a result, the circuit area of the traditional FFT device  10  can be relatively reduced. In addition, the number of data input and output ports of the processor  18  is traditionally a power of 2, i.e., 2, 4, 8 . . . etc., denoted by r. The whole profile of the processor  18  looks like a butterfly and therefore is named the butterfly structure. Such a memory-based structure can enhance the flexibility of the memory  14  because the memory  14  concurrently plays two roles, one is a data buffer as data is input or output, and the other is a data register while the FFT device  10  is in computation status. Because the memory  14  is a RAM and can be accessed randomly, a user can appropriately design an addressing controller  20  to write the data to an appropriate address. Similarly, when the data is output, the addressing controller  20  can sequentially output the data stored in the memory  14 .  
         [0009]     To minimize the area of the memory  14  and increase the efficiency, the FFT device  10  adapts an “in-place conflict-free” addressing to extend the utility of the memory  14  to 100%. The term “in-place” indicates that data before and after being processed are stored in a same memory address. Accordingly, the capacity of the memory  14  is reduced to the minimum. The term “conflict-free” indicates that when the processor  18  accesses data in the memory  14 , one bank of the memory  14  will not be asked to provide two or more data at each time.  
         [0010]     Because of using the dual-port RAM devices to form the memory  14 , data can be read from and written to the memory  14  concurrently. In addition, the memory  14  can operate with a data shifting function of the barrel shifter  12  to appropriately shift the sequence of data. For example, the sequence of data output from the processor  18  can be shifted by one word so as to be written to the memory  14  correctly. The serial number of data can be assigned by the user, and is preferably sorted by natural order. Based on the foregoing explanation, the abovementioned shifting can provide a similar function to sort the data in natural order.  
         [0011]     According to the equation of the in-place conflict-free addressing, an index n of data to be processed is represented by the following equation: 
 
 n=n   0   ·r   R-1   +n   1   ·r   R-2   + . . . +n   R-1   ·r   0 ,   (2) 
 
         [0012]     A bank index B(n) of the memory  14  is represented by the following equation: 
 
 B ( n )=( n   0   +n   1   + . . . +n   R-1 )  mod r,    (3) 
 
 wherein R is represented by the following equation: 
 
R=log r  N,   (4) 
 
 In addition, an address value A(n) of a cell of a memory bank is represented by the following equation. 
 
 A ( n )= n   1   ·r   0   +n   2   ·r   1   + . . . +n   R-1   ·r   R-2 ,   (5) 
 
         [0013]     For example, if N=64, r=4, R=3, the 41th data has the index n=( 221)   4  at the input terminal, the bank index B(n)=1, and the address value A(n)=6. Accordingly, when the bank index B(n) and the address value A(n) are known, the data can be correctly read from the memory  14  to the input ports of the processor  18  to perform the FFT process, and then the processor  18  can write the processed data to the same memory address in the same memory bank. As shown in  FIG. 2 , if the amount of data is 64 (N=64), and sorted in natural order, because a dual-port RAM has a feature of random access, the data can be stored in the memory bank randomly upon the principle of the in-place conflict-free addressing. In addition, the processor  18  has four data input ports (n=r=4), and divides the memory  14  into four memory banks, denoted as bank 0 , bank 1 , bank 2  and bank 3 . The cells of each bank can output or input data before or after being processed. No matter before or after being processed, the data is stored in the same memory address. Further, no conflict occurs in concurrently storing and fetching r data as a result of using the in-place conflict-free addressing. In the figure, a circle pattern (O) indicates a processor  18 , and the number near the circle pattern indicates the sequence of data processing. The  48  times of data processing are divided into three stages (R=3), stage 0 , stage 1  and stage 2 . Each stage performs  16  times of data processing in a random sequence, but on the purpose of simplifying the design complexity of the address controller  20 , a natural sequence is preferable. Next, the address controller  20  outputs a respective address to the memory  14 , and outputs read and write shift amounts to the barrel shifters  12  and  16  respectively so as to control the operations thereof. Thus, the shifter  12  and  16  can correctly provide data from the correct memory bank or write data to the correct memory bank. The relation between the sequence value q and the shift amount is shown in the following equations. 
 
 q=q   R-2   ·r   R-2   +q   R-3   ·r   R-3   + . . . +q   0 ,   (6) 
 
Shift Amount=( q   R-2   +q   R-3   + . . . +q   0 )  mod r.    (7) 
 
         [0014]     As shown in  FIG. 3 , the read shift amount is the same as the write shift amount, and difference is that the write shift amount is delayed m clocks from the read shift amount, wherein the m clocks preferably equal to the time for performing one data processing. For simplifying the following description, the address value A(n) of the bank index B(n) is denoted as Bn[A(n)]. And, in this case, m=4. When q=0, the butterfly structure reads data at memory addresses B 0 [0], B 1 [0], B 2 [0] and B 3 [0]. Next, when q=1, the butterfly structure reads data at memory addresses B 0 [1], B 1 [1], B 2 [1] and B 3 [1] that are shifted by one complex word. Next, when q=2, the butterfly structure reads data at memory addresses B 0 [2], B 1 [2], B 2 [2] and B 3 [2] that are shifted by two complex words. Next, when q=3, the butterfly structure reads data at memory addresses B 0 [3], B 1 [3], B 2 [3] and B 3 [3] that are shifted by three complex words. Next, when q=4, the butterfly structure starts to write the processed data back to the memory  14 . Accordingly, the time required by the FFT device  10  to complete the whole FFT is represented by the following equation:  
               (         N   r     ·     log   r       ⁢   N     )     +     m   .             (   8   )             
 
         [0015]     However, due to the dual-port RAM, the circuit area of the FFT device  10  is still large and needs to be further reduced to meet with the miniaturization requirement. Therefore, it is desirable to provide an improved device to mitigate and/or obviate the aforementioned problems.  
       SUMMARY OF THE INVENTION  
       [0016]     The object of the invention is to provide a memory-based FFT device, which can reduce a required circuit area of the prior FFT device.  
         [0017]     To achieve the object of the invention, a memory-based Fast Fourier Transform device is provided. The device includes a processor, multiple single port random access memory (RAM) units, a sequence value generator, a sequence value modifier, an address controller and multiple switches. The switches consist of multiple barrel shifters and multiple multiplexers. The sequence value modifier adjusts an output of the sequence value generator to generate an adjusted sequence value to the address controller for generating a write shift amount, a read shift amount, and a bank address. The switches are based on the read shift amount to read data to be processed from a single port RAM to the processor in order to perform an FFT, and on the write shift amount to write the data from the processor to a different single port RAM.  
         [0018]     Other objects, advantages, and novel features of the invention will become more apparent from the following detailed description when taken in conjunction with the accompanying drawings. 
     
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0019]      FIG. 1  is a block diagram of a traditional FFT device;  
         [0020]      FIG. 2  is a data flow graph of FFT with a processing sequence and operation of  FIG. 1 ;  
         [0021]      FIG. 3  is a timing diagram of corresponding sequence values, shift amount and memory addresses in the prior art;  
         [0022]      FIG. 4  is a block diagram of FFT device according to the invention;  
         [0023]      FIG. 5A  is a timing diagram of a traditional access sequence of  FIG. 1 ;  
         [0024]      FIG. 5B  is a timing diagram of an access sequence of  FIG. 4  according to the invention;  
         [0025]      FIG. 6  is a block diagram of switches and a process according to the invention;  
         [0026]      FIG. 7  is a data flow graph of FFT with a processing sequence and operation of  FIG. 4  according to the invention;  
         [0027]      FIG. 8  is a schematic diagram of a read and write operation with collisions  1  and  2  according to the invention;  
         [0028]      FIG. 9  is a schematic diagram of  FIG. 8  after collisions  1  and  2  are eliminated according to the invention; and  
         [0029]      FIG. 10  is a schematic diagram of a sequence value modifier according to the invention. 
     
    
     DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENT  
       [0030]     Since a traditional memory  14  of an N-point FFT device  10  is implemented by dual port RAM banks, and a cell of each dual port RAM bank typically contains  16  transistors, in order to achieve the purpose of reducing the circuit area of the device  10 , the invention replaces the dual port RAM banks with single port RAM banks, a cell of each single port RAM bank containing just about ten transistors. Thus, the circuit area is significantly reduced.  
         [0031]     In this embodiment, the configuration of the present invention is the same with the traditional device  10  (N=64, r=4, R=3). However, the values of the configuration can be adjusted based on the demand of users.  
         [0032]     As shown in  FIG. 4 , the FFT device  30  includes the processor  18 , switches  32  and  34 , memory units  36  and  38 , an address controller  40 , a sequence value modifier  42  and the sequence value generator  22 , wherein the processor  18  and the sequence value generator  22  are identical to the prior processor and the sequence value generator  22  respectively and thus not repeated. The memory units  36  and  38  are each a single port RAM and alternately accessed by the processor  18 . An operation of the dual port RAM banks of the traditional memory  14  is shown in  FIG. 5A , which illustrates that the traditional memory  14  can concurrently perform write and read operations. Conversely, since the memory units  36  and  38  are each a single port RAM, in order to achieve the performance the same as that of the traditional memory  14  and avoid concurrently reading and writing in the same memory address, the memory units  36  and  38  are operated as shown in  FIG. 5B . Namely, the memory units  36  and  38  respectively perform the alternate write and read operations. The processor  18  can read data from one of the memory unit  36  or  38  and write the processed data to the same memory unit. Since the FFT device  30  includes the memory units  36  and  38 , a new addressing for the FFT device  30  is required so that the processed data can be stored in the appropriate memory addresses to thus provide the in-place and conflict-free features.  
         [0033]     The addressing can directly divide the data into multiple groups. In this embodiment, to meet with the number of the adopted single port RAM, two groups are preferred, which are denoted as G 0  and G 1  and respectively stored in the memory units  36  and  38 . The memory units  36  and  38  have four memory banks respectively numbered 0-3 and 4-7 as bank indexes. In this embodiment, it is preferred to equally divide the data from top to bottom. In this case, equation (3) can be rewritten as: 
 
if ( n   R-1   &lt;r/ 2) 
 
 B ( n )=( n   0   +n   1   + . . . +n   R-1 )  mod r;  
 
else 
 
 B ( n )=( n   0   +n   1   + . . . +n   R-1 )  mod r+r;    (9) 
 
         [0034]     Equation (5) can be rewritten as:  
               if   ⁢           ⁢     (       n     R   -   1       &lt;     r   /   2       )       ⁢     
     ⁢         A   ⁡     (   n   )       =         n   1     ·     r   0       +       n   2     ·     r   1       +   …   +       n     R   -   1       ·     r     R   -   2             ;     ⁢     
     ⁢   else   ⁢     
     ⁢       A   ⁡     (   n   )       =         n   1     ·     r   0       +       n   2     ·     r   1       +   …   +       n     R   -   1       ·     r     R   -   2         -       N     2   ⁢   r       .                 (   10   )             
 
         [0035]     According to memory bank indexes B(n) obtained in equation (9) and address values A(n) of memory cells obtained in equation (10), the address controller  40  can control the operation of store and write of the processed data.  
         [0036]     The sequence value modifier  42  can adjust a sequence value q output by the sequence value generator  22  and generate a new sequence value q′. The address controller  40  controls operations of the switches  32  and  34  according to the new sequence value q′ and further controls a processing flow of data to be processed.  
         [0037]     As shown in  FIG. 6 , the switch  32  includes barrel shifters  321  and  322 , and multiplexers  323 - 326 . The processor  18  has four output terminals, two, op 0  and op 1 , connected directly to two input terminals of the barrel shifter  321  and the other two, op  2  and op  3 , connected directly to two input terminals of the barrel shifter  322 . In addition, the two output terminals of the processor  18 , op 0  and op 1 , are also connected to the other two input terminals respectively of the barrel shifters  322  through the multiplexers  325  and  326  respectively, and the other two, op 2  and op 3 , are also connected to the other two input terminals respectively of the barrel shifters  321  through the multiplexers  323  and  324  respectively. The four output terminals of the barrel shifters  321  and  322  are connected to four input terminals of the memory units  36  and  38  respectively, one to one. The switch  34  includes barrel shifters  341  and  342 , and multiplexers  343 - 347 . The barrel shifters  341  and  342  have four input terminals connected to output terminals of the memory units  36  and  38  respectively, one to one. The multiplexer  347  has eight input terminals, two connected to two output terminals of the barrel shifter  341 , two connected to the other two output terminals of the barrel shifter  341  through the multiplexers  343  and  344  respectively, two connected to two output terminals of the barrel shifter  342 , and two connected to the other two output terminals of the barrel shifter  342  through the multiplexers  345  and  346  respectively. The multiplexers  343  and  344  each have a different input terminal connected to the other two output terminals of the barrel shifter  342  respectively. The multiplexers  345  and  346  each have a different input terminal connected to the other two output terminals of the barrel shifter  341  respectively. The processor  18  has four input terminals connected to four output terminals of the multiplexer  347 , one to one.  
         [0038]     The barrel shifters  341 ,  342  and  321 ,  322  can shift data to be processed according to a read shift amount and write shift amount respectively. The processor  18  reads or writes data to be processed from or to the memory units  36  and  38  at operation. Thus, the switches  32  and  34  internally require the multiplexers  323 - 326  and  343 - 346  to provide the processor  18  with appropriate data to be processed. The operations of the multiplexers  323 - 326  and  343 - 346  are controlled by the address controller  40 . The multiplexer  347  selects input data for processor  18  from upper or lower four input terminals.  
         [0039]      FIG. 5B  also indicates that the processing sequence of the processor  18  will be different from the prior art. As shown in  FIG. 7 , a butterfly symbol indicates a processor  18 , and numbers on or near the butterflies indicate the operation sequence of the process  18 . Because the memory units  36  and  38  are alternately accessed by the processor  18 , the operation sequence can be counted separately. Similarly, the  48  operations can be divided into three stages (stage 0 , stage 1 , stage 2 ), each having the  16  operations. Because the processor  18  requires m clocks for the operations, an m clock interval between the operations is preferred, thereby reading from or writing to the memory units  36  and  38  alternately.  
         [0040]     After the addressing method is established completely, the processor  18  is further checked for accessing appropriate data to be processed according to the addressing method. At stage 0  and stage 1 , because the processor  18  reads and stores data to be processed in different memory groups, memory  36  and  38 , data to be processed in a same memory bank are not read and written concurrently. Thus, no data access conflict occurs. However, at stage 2 , the processor  18  reads and writes data to be processed in a same memory bank and therefore data access conflicts occur. As shown in  FIG. 8 , based on the condition of conflict, the data access conflict can have two types, referred to as conflict 1  and conflict 2 . Conflict 1  is caused when the processor  18  needs to read a data to be processed from the memory  38  while the data is written to the memory  38 . Conflict 1  can be eliminated by inserting a wait state before the last operation at stage 1  and the delay time preferably equals to a period of m clocks. The result is shown in  FIG. 9  and the conflict 1  is avoided.  
         [0041]     Conflict  2  is to be eliminated after conflict 1  is eliminated. However, conflict  2  could not be eliminated by the same way, but if the write shift amount equals to the read shift amount, the processor  18  can conveniently read and write data to be processed so as to eliminate conflict 2 . Accordingly, the sequence values q are adjusted to generate adjusted sequence values q′ such that the write shift number equals to the read shift amount, thereby eliminating conflict 2 . First, every four adjacent sequence values q generated by the sequence value generator  22  are grouped into a natural sequence. In this case, for q=0 to 15, four natural sequences {0, 1, 2, 3}, {4, 5, 6, 7}, {8, 9, 10, 11} and {12, 13, 14, 15} are grouped, as shown in Table 1. For the natural sequence {0, 1, 2, 3}, its shift amount is equal to {0, 1, 2, 3} and thus no adjustment is performed. For the natural sequence {4, 5, 6, 7}, its shift amount sequence is equal to {1, 2, 3, 0} and thus the natural sequence {4, 5, 6, 7} needs an adjustment in order to conform to {0, 1, 2, 3}. Accordingly, “7” is sent out first and then {4, 5, 6} is sent out, thereby forming an adjusted sequence {s3, s0, s1, s2} and an adjusted natural sequence {7, 4, 5, 6}. Similarly, for the shift amount sequences {2,3,0,1} and {1,2,3,0}, the adjusted sequences are {s2, s3, s0, s1} and {s1, s2, s3, s0} respectively. At this point, the shift amount sequences corresponding to the four natural sequences are {0, 1, 2, 3}, {1, 2, 3, 0}, {2, 3, 0, 1} and {3, 0, 1, 2} respectively. A relation between the shift amount and the bank index is shown in Table 2, and one of the barrel shifters corresponds to the barrel shifter  341  or  321  while the other corresponds to the barrel shifter  342  or  322 .  
                           TABLE 1                                   Adjusted natural       Natural sequence   Shift amount   Adjusted   Sequence       s0, s1, s2, s3   j0, j1, j2, j3   sequence   s0′, s1′, s2′, s3′                   0, 1, 2, 3   0, 1, 2, 3   s0, s1, s2, s3   0, 1, 2, 3       4, 5, 6, 7   1, 2, 3, 0   s3, s0, s1, s2   7, 4, 5, 6       8, 9, 10, 11   2, 3, 0, 1   s2, s3, s0, s1   10, 11, 8, 9       12, 13, 14, 15   3, 0, 1, 2   s1, s2, s3, s0   13, 14, 15, 12                  
 
         [0042]    
       
         
               
               
               
               
               
               
             
               
             
               
               
               
               
               
               
             
               
             
               
               
               
               
               
               
             
           
               
                   
                 TABLE 2 
               
               
                   
                   
               
               
                   
                   
               
               
                   
                 Shift amount 
                 0 
                 1 
                 2 
                 3 
               
               
                   
                   
               
             
             
               
                   
               
             
          
           
               
                 One barrel shifter 341/321 
               
             
          
           
               
                   
                 0th input/output ports 
                 B0 
                 B1 
                 B2 
                 B3 
               
               
                   
                 1st input/output ports 
                 B1 
                 B2 
                 B3 
                 B0 
               
               
                   
                 2nd input/output ports 
                 B6 
                 B7 
                 B4 
                 B5 
               
               
                   
                 3rd input/output ports 
                 B7 
                 B4 
                 B5 
                 B6 
               
             
          
           
               
                 The other barrel shifter 342/322 
               
             
          
           
               
                   
                 0th input/output ports 
                 B2 
                 B3 
                 B0 
                 B1 
               
               
                   
                 1st input/output ports 
                 B3 
                 B0 
                 B1 
                 B2 
               
               
                   
                 2nd input/output ports 
                 B4 
                 B5 
                 B6 
                 B7 
               
               
                   
                 3rd input/output ports 
                 B5 
                 B6 
                 B7 
                 B4 
               
               
                   
                   
               
             
          
         
       
     
         [0043]     There are only four possibilities, and thus a user needs to detect a value of the first element j 0  of a shift amount sequence to accordingly obtain all values of the shift amount sequence. The value of the first element j 0  can be obtained from the following equation. 
 
 j   0 =( q   R-2i +q   R-3   + . . . +q   1 )  mod r.    (11) 
 
         [0044]     When the value of the first element j 0  is obtained, the respective adjusted natural sequence can be obtained from the following function. 
 
if (( j   0 ==0) or ( j   0 ==2)) 
 
s i ′=s j     i   ; 
 
else 
 
 s   i   ′=s   (j     i     +2) mod 4 ;   (12) 
 
         [0045]     As shown in  FIG. 10 , the sequence value modifier  42  is a physical circuit corresponding to equation (11) and function (12). Accordingly, the write and read shift amounts corresponding to an adjusted natural sequence are the same, thereby eliminating conflict 2 . Because of no conflict at stage 0  and stage 1 , when the way of eliminating conflict 2  is submitted to stage 0  and stage 1 , the operation of the processor  18  is affected. In order to eliminate conflict  1 , the time required by the FFT device  30  to complete an FFT is m clocks more than that by the traditional FFT device  10 , but no additional time is required by the FFT device  30  in eliminating conflict 2 . Accordingly, the time required by the FFT device  30  to complete the FFT can be represented by the following equation.  
               (         N   r     ·     log   r       ⁢   N     )     +     2   ⁢   m             (   13   )             
 
         [0046]     As shown in Table 3, although the FFT device  30  needs additional electronic components, it can save almost a half of memory space of the traditional FFT device  10  with a dual port RAM, and accordingly the effect of area reduction is achieved. The FFT device  30  requires additional m clock for operation, but with N becoming greater and greater, the m clock delay can be relatively small and be ignored to thus have the performance similar to that of the traditional FFT device  10 .  
                                         TABLE 3                                   Traditional   FFT device of the           FFT device   present invention                                    Processor number   1   1       Memory size   N-cword* dual-port   N-cword* single port RAM           RAM       Switch structure   Two barrel shifters   Four barrel shifters and               eight multiplexers       Sequence value   Sequence value   Sequence value generator and       provider   generator   sequence value modifier               Time for operation             (         N   r     ·           ⁢     log   r       ⁢           ⁢   N     )     +   m                     (         N   r     ·           ⁢     log   r       ⁢           ⁢   N     )     +     2   ⁢   m                           (*: cword means a complex word)             
 
         [0047]     Although the present invention has been explained in relation to its preferred embodiment, it is to be understood that many other possible modifications and variations can be made without departing from the spirit and scope of the invention as hereinafter claimed.