Patent Publication Number: US-2004059766-A1

Title: Pipelined low complexity FFT/IFFT processor

Description:
BACKGROUND OF INVENTION  
       [0001] 1. Field of the Invention  
       [0002] The present invention relates to signal processors. More specifically, a radix-2 3  Inverse Fast Fourier Transform (IFFT) processor is disclosed.  
       [0003] 2. Description of the Prior Art  
       [0004] For Orthogonal Frequency Division Multiplexing (OFDM) systems, Inverse Fast Fourier Transform/Fast Fourier Transform (IFFT/FFT) processors are generally in the modulation/demodulation process to achieve effective multi-carrier transmissions. Many OFDM systems, such as the OFDM system used by the WLAN 802.11a standard, require IFFT/FFT processors that provide high speed, real-time throughput in combination with a low complexity implementation to obtain high data rates. Meeting these criteria is an on-going objective.  
       [0005] E. H. Worl and A. M. Despain in their article “Pipeline and Parallel-pipeline FFT Processors for VLSI Implementation” from IEEE Trans. Comput., C-33(5): 414-426 of May 1984, included herein by reference, describe a radix-2 pipelined Single-path Delay Feedback (R2SDF) FFT that is capable of providing high-speed, real-time processing. However, such a design requires (log 2 N−1) complex multipliers for an N-point FFT, which implies a relatively complex implementation.  
       [0006] Shousheng He and Mats Torkelsson disclose in their U.S. Pat. No. 6,098,088, which is included herein by reference, a radix-2 2  Decimation-in-Frequency (DIF) FFT algorithm and associated architecture that lowers the required complexity by bringing the number of required complex multipliers down to (log 4 N−1) for an N-point FFT. Additionally, Shousheng He and Torkelson, M. also disclose in their article, “A new approach to pipeline FFT processor” in Parallel Processing Symposium, 1996, Proceedings of IPPS ″96, The 10 th  International, 1996, included herein by reference, a radix-2 3  DIF FFT algorithm that requires only (log 8 N−1) complex multipliers. However, no architecture related to this algorithm is disclosed.  
       [0007] Beyond the demands of low complexity and high speeds, IFFT/FFT processors suffer from disorder in the output or input streams. DIF FFT processors and DIT (Decimation in Time) IFFT processors provide ordered inputs, but disordered outputs. DIT FFT processors and DIF IFFT processors, on the other hand, provide unordered inputs and ordered outputs. For example, a 16-point DIF processor, as disclosed in U.S. Pat. No. 6,098,088, sequentially clocks in as input points x[0] to x[15]. These points are input in order. The output frequency values X[0] to X[15], however, are not clocked out in order. Instead, they are presented in sequence as: X[0], X[8], X[4], X [12], X[2], X[10], X[6], X[14], X[1], X[9], X[5], X[13], X[3], X[11], X[7] and finally X[15]. A DIT FFT processor simply accepts disordered inputs to provide ordered outputs. In either case, the lack of order on either of the input or output sides imposes additional burdens on circuitry that utilizes the IFFT/FFT processor.  
       SUMMARY OF INVENTION  
       [0008] It is therefore a primary objective of this invention to provide an architecture that implements a radix-2 3  algorithm for an IFFT/FFT N-point processor. The architecture requires only (log 8 N−1) complex multipliers, 2×log 8 Nπ/2 complex rotators, and log 8 Nπ/4 complex rotators.  
       [0009] It is a further objective to provide a real-time architecture that utilizes a triplet butterfly circuit that includes a butterfly I circuit, a butterfly II circuit and a butterfly III circuit. Each of these butterfly circuits has a relatively simple architecture that is controlled according to a pipeline step-count of the processor control circuitry.  
       [0010] It is yet another objective to provide an IFFT/FFT processor with a reordering circuit so that both the inputs and the outputs of the IFFT/FFT processor are ordered in time.  
       [0011] Briefly summarized, the preferred embodiment of the present invention discloses a real-time pipelined N-point transform processor that contains a first butterfly triplet multiplicatively connected to an output portion by way of a complex multiplier. The butterfly triplet contains a first butterfly I unit (BFI), a butterfly II unit (BFII) and a butterfly III unit (BFIII), which are connected together in series. An input port of the first BFI serves as an input port of the triplet to accept complex numbers, and an output port of the BFIII serves as an output port of the triplet. The complex multiplier accepts a complex result from the output port of the first triplet, and a coefficient provided by a control unit to generate a complex product. The output portion contains at least a second BFI, an input port of the second BFI accepting the complex product from the complex multiplier, and the output portion then provides the transformed complex numbers. The control unit contains a pipeline step-count register, and the ability to provide the coefficients to the complex multiplier. The control unit controls each BFI, each BFII, each BFIII, and provides each coefficient, according to a value held in the pipeline step-count register. A reordering circuit is provided to insure that the time domain order of the transformed complex numbers matches the frequency domain order of the input complex numbers.  
       [0012] It is an advantage of the present invention that the butterfly units BFI, BFII and BFIII that make up the butterfly triplet and output portion are easy to implement. Further, the present invention reduces the number of complex multipliers down to an order of (log 8 N−1). Yet another advantage is that the reordering circuit ensures that the output transformed complex numbers occur in the order as provided by the input complex numbers. Hence, circuitry utilizing the present invention processor does not need to reorder the time or frequency domain, thus reducing implementation burdens on external circuitry.  
       [0013] These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment, which is illustrated in the various figures and drawings. 
     
    
    
     BRIEF DESCRIPTION OF DRAWINGS  
     [0014]FIG. 1 illustrates a process diagram for a general butterfly circuit.  
     [0015]FIG. 2 is a process diagram for a 16-point radix-2 3  Decimation in Time Inverse Fast Fourier Transform (DIT IFFT) process according to the present invention.  
     [0016]FIG. 3 is a schematic design for the 16-point radix-2 3  DIT IFFT process of FIG. 2.  
     [0017]FIG. 4 is a schematic diagram of a general butterfly unit BFI according to the present invention.  
     [0018]FIG. 5 is a schematic drawing of a general butterfly unit BFII according to the present invention.  
     [0019]FIG. 6 is a schematic drawing of a general butterfly unit BFIII according to the present invention.  
     [0020]FIG. 7 is a schematic drawing of a π/2 complex rotator  400  according to the present invention.  
     [0021]FIG. 8 is a schematic drawing of a π/4 complex rotator according to the present invention.  
     [0022]FIG. 9 is a process diagram for a 32-point radix-2 3  DIT IFFT process according to the present invention.  
     [0023]FIG. 10 is a schematic design for the 32-point radix-2 3  DIT IFFT process of FIG. 9.  
     [0024]FIGS. 11A and 11B are process diagrams for a 64-point radix-2 3  DIT IFFT process according to the present invention.  
     [0025]FIG. 12 is a schematic design for the 64-point radix-2 3  DIT IFFT process of FIGS. 11A and 11B.  
     [0026]FIG. 13 is a schematic design for a 128-point radix-2 3  DIT IFFT processor according to the present invention.  
     [0027]FIG. 14 is a simple block diagram of an IFFT/FFT processor according to the present invention.  
     [0028]FIG. 15 is a block diagram of a 16-point radix-2 3  DIT IFFT processor supporting ordered outputs according to the present invention.  
     [0029]FIG. 16 is a block diagram of a 16-point radix-2 3  DIF IFFT processor supporting ordered inputs according to the present invention. 
    
    
     DETAILED DESCRIPTION  
     [0030] In the following detailed description of the preferred embodiment design, a Decimation in Time (DIT) Inverse Fast Fourier Transform (IFFT) circuit is disclosed, as such a circuit utilizes (j) mathematical coefficients rather than (−j) coefficients, and thus reduces the overall complexity of the circuit. However, those skilled in the art will realize that it is a trivial matter to utilize the teachings of the present invention to build other types of related circuits, such as a Decimation in Frequency (DIF) FFT design, as the transformation from a DIF design to a DIT design, and from an IFFT to an FFT, involves little more than a change of mathematical coefficients and conjugation of the inputs/outputs, respectively. An overview of the mathematical basis of the present invention is beneficial, as it aids in the understanding of the related butterfly circuits and determination of the various coefficients that are provided by the processor control circuitry to the complex multiplier(s). An N-point Inverse Discrete Fourier Transform (IDFT) has the general formula of:  
               x        [   n   ]       =       ∑     k   =   0       N   -   1              X        [   k   ]            W   N     ′                 nk                   (       Eqn   .              1        a     )                       
 
     [0031] In Eqn. 1a, x[n] are position outputs, X[n] are frequency inputs, 0≦n≦N, 0≦k≦N, and;  
               W   N     ′                 nk       =     exp        (     j   ×   2      π                   nk   /   N       )               (       Eqn   .              1        b     )                       
 
     [0032] By recursively applying a radix-8 followed by a radix-2 index map, the DIT version is obtained when substituting the indices of Eqns. 1a and 1b with:  
       k   =         N   2          k   1       +       N   4          k   2       +       N   8          k   3       +     k   4                     
 
     [0033] and  
       n=n   1 +2 n   2 +4 n   3 +8 n   4    
     [0034] where:  
     [0035] 0≦k 4 ≦(N/8−1),  
     [0036] 0≦k 3 ≦1,  
     [0037] 0≦k 2 ≦1,  
     [0038] 0≦k 1 ≦1,  
     [0039] 0≦n 4 ≦(N/8−1),  
     [0040] 0≦n 3 ≦1,  
     [0041] 0≦n 2 ≦1, and  
     [0042] 0≦n 1 ≦1  
     [0043] The resulting expression is then given by:  
                 x        [       n   1     +     2        n   2       +     4        n   3       +     8        n   4         ]       =       ∑       k   4     =   0         N   8     -   1              ∑       k   3     =   0     1            ∑       k   2     =   0     1            ∑       k   1     =   0     1            X        [         N   2          k   1       +       N   4          k   2       +       N   8          k   3       +     k   4       ]            W   N     ′                 nk                        
            where          :            
                  W   N     ′                 nk       =     W   N     ′                   (         N   2          k   1       +       N   4          k   2       +       N   8          k   3       +     k   4       )          (       n   1     +     2        n   2       +     4        n   3       +     8        n   4         )                     =       W   N     ′                   N   2          k   1          n   1              W   N     ′                   N   2            k   2          (       n   1     +     2        n   2         )                W   N     ′                   N   8            k   3          (       n   1     +     2        n   2       +     4        n   3         )                W   N     ′                     k   4          (       n   1     +     2        n   2       +     4        n   3       +     8        n   4         )                         =         (     -   1     )         k   1          n   1                (   j   )         n   1     +     2        n   2                W   N     ′                   N   8            k   3          (       n   1     +     2        n   2       +     4        n   3         )                W   N     ′                     k   4          (       n   1     +     2        n   2       +     4        n   3         )                W   N     ′                 8        k   4          n   4                        
          If                 we                 set        :            
                  C   1     =       (   j   )         n   1     +     2        n   2                         C   2     =     W   N     ′                   N   8            k   3          (       n   1     +     2        n   2       +     4        n   3         )                         C   3     =     W   N     ′                     k   4          (       n   1     +     2        n   2       +     4        n   3         )                         C   4     =     W   N     ′                 8        k   4          n   4                         (     Eqn   .              2     )                       
 
     [0044] Then Eqn. 2 can be rewritten as:  
         x        [       n   1     +     2        n   2       +     4        n   3       +     8        n   4         ]       =       ∑       k   4     =   0         N   8     -   1              ∑       k   3     =   0     1            ∑       k   2     =   0     1            [       X        (         N   4          k   2       +       N   8          k   3       +     k   4       )       +         (     -   1     )       n   1            X        (       N   2     +       N   4          k   2       +       N   8          k   3       +     k   4       )           ]          C   1          C   2          C   3          C   4                           
 
     [0045] Butterfly BFI is identified in the above as:  
         BFI        (           N   4          k   2       +       N   8          k   3       +     k   4       ,     n   1       )       =       X        (         N   4          k   2       +       N   8          k   3       +     k   4       )       +         (     -   1     )       n   1            X        (       N   2     +       N   4          k   2       +       N   8          k   3       +     k   4       )                         
 
     [0046] With this, Eqn. 2 is then rewritten as:  
         x        [       n   1     +     2        n   2       +     4        n   3       +     8        n   4         ]       =       ∑       k   4     =   0         N   8     -   1              ∑       k   3     =   0     1            [       BFI        (           N   8          k   3       +     k   4       ,     n   1       )       +         (   j   )       (       n   1     +     2        n   2         )            BFI        (         N   4     +       N   8          k   3       +     k   4       ,     n   1       )           ]          C   2          C   3          C   4                         
 
     [0047] Butterfly BFII is identified in the above as:  
         BFII        (           N   8          k   3       +     k   4       ,     n   1     ,     n   2       )       =     [       BFI        (           N   8          k   3       +     k   4       ,     n   1       )       +         (   j   )       (       n   1     +     2        n   2         )            BFI        (         N   4     +       N   8          k   3       +     k   4       ,     n   1       )           ]                   
 
     [0048] Eqn. 2 can then be further rewritten as:  
         x        [       n   1     +     2        n   2       +     4        n   3       +     8        n   4         ]       =       ∑       k   4     =   0         N   8     -   1              [       BFII        (       k   4     ,     n   1     ,     n   2       )       +       W   8     ′                   (       n   1     +     2        n   2       +     4        n   3         )              BFII        (         N   4     +       N   8          k   3       +     k   4       ,     n   1     ,     n   2       )           ]          C   3          C   4                       
 
     [0049] Finally, butterfly BFIII is identified above as:  
         BFIII        (       k   4     ,     n   1     ,     n   2     ,     n   3       )       =     [       BFII        (       k   4     ,     n   1     ,     n   2       )       +       W   8     ′                   (       n   1     +     2        n   2       +     4        n   3         )              BFII        (         N   4     +       N   8          k   3       +     k   4       ,     n   1     ,     n   2       )           ]                   
 
     [0050] By further identifying a term:  
     
       G 
       n 
       
         1 
       
       ,n 
       
         2 
       
       ,n 
       
         3 
       
       =BFIII×C 
       3  
     
     [0051] Eqn. 2 can finally be rewritten as:  
               x        [       n   1     +     2        n   2       +     4        n   3       +     8        n   4         ]       =       ∑       k   4     =   0         N   8     -   1                           G       n   1     ,     n   2     ,     n   3              [     k   4     ]       ×     W     N   8       ′                   n   4          k   4                     (     Eqn   .              3     )                       
 
     [0052] It is noted that Eqn. 3 is simply an (N/8)-point IFFT calculation. Hence, the above steps can be recursively applied until (N/8 p )≦8, where “p” is the depth of the recursion (i.e., how many times the steps are recursively performed). The above equations indicate that BFI, BFII and BFIII are serially linked together in order to form a butterfly triplet, and that butterfly triplets are multiplicatively linked together by way of the appropriate coefficients. The number of such complete butterfly triplets is “p”, and is finally determined by the number “N”, i.e., the number of points handled by the IFFT processor. The output portion of the IFFT will contain at least a portion of a butterfly triplet, which is multiplicatively connected to the last complete butterfly triplet via appropriate coefficients. That is, the output portion may not contain a full set of the constituent butterfly parts BFI, BFII, BFIII. Where N=2 n , if the value “n mod 3” is one, then the output portion will contain only BFI, which will be the output port of the IFFT. If “n mod 3” is two, then the output portion will contain BFI and BFII in series, with BFII being the output port. If “n mod 3” is zero, then the output portion will contain the full complement of the butterfly constituent parts BFI, BFII and BFIII, with BFIII being the output port.  
     [0053] With regards to the above equations, the following is noted. Butterfly BFII contains the coefficient (j) n     1     +2   n     2     ) , which is a π/2 complex rotator. Butterfly BFIII contains the coefficient:  
               W   8     ′        (       n   1     +     2        n   2       +     4        n   3         )         =         W   8     ′                   n   1         ×     W   8     ′2        (       n   2     +     2        n   3         )                
                =         (         2     2          (     1   +   j     )       )       n   1       ×       (   j   )       (       n   2     +     2        n   3         )                   (     Eqn   .              4     )                       
 
     [0054] Eqn. 4 can be realized by the cascading of a π/2 complex rotator and a π/4 complex rotator. However, the π/4 complex rotator, as it appears in Eqn. 4, can be closely approximated by:  
                 (         2     2          (     1   +   j     )       )       n   1       ≈       [       (       2     -   1       +     2     -   3       +     2     -   4       +     2     -   6       +     2     -   8         )     ×     (     1   +   j     )       ]       n   1               (     Eqn   .              5     )                       
 
     [0055] Eqn. 5 can be quite easily implemented by way of five right shifters, one π/2 complex rotator, one 2-to-1 complex adder and one 5-to-1 complex adder.  
     [0056] In the following, the concept of a butterfly circuit is used extensively. FIG. 1 illustrates a process diagram for a general butterfly circuit  10 . From an algorithmic point of view, the butter  10  has two inputs  11   a  and  11   b , and two outputs  12   a  and  12   b . Both inputs and outputs are for complex numbers, and thus may represent many signal lines depending upon the bit-size of the complex numbers. If input  11   a  a complex number “A”, and input  11   b  accepts a complex number “B”, then output  12   a  represents the complex number “A+B”, and output  12   b  represents the complex number “A−B”. A butterfly circuit will thus require a complex adder circuit and a complex subtractor circuit.  
     [0057] Please refer to FIG. 2. FIG. 2 is a process diagram  20  for a 16-point radix-2 3  DIT IFFT according to the present invention, as derived from the above equations. The butterfly units BFI, BFII and BFIII are indicated, serially linked together in order to form a single complete butterfly triplet. An output portion contains a single BFI unit, multiplicatively linked to the butterfly triplet. The output of the butterfly triplet, i.e. the output from BFIII, is fed into a complex multiplier, indicated by the “{circle over (×)}” symbol. Coefficients W&#39;n are also fed into the complex multiplier, and the resulting complex product is passed into the output portion BFI. The value of W′n that is fed into the complex multiplier will depend upon pipeline step-count, and is generally given by:  
       W′n=exp ( j× 2π× n/ 16)  
     [0058] In particular, it should be noted that the term W′2, which appears intermittently in BFIII, is the π/4 complex rotator that is approximated by:  
       W′ 2≈0.7071+0.7071 j    
     [0059] Please refer to FIG. 3 in conjunction with FIG. 2. FIG. 3 is a schematic design  30  for the 16-point radix-2 3  DIT IFFT process of FIG. 2. The circuit  30  includes a complete butterfly triplet  37  multiplicatively connected to an output portion  39  by way of a complex multiplier  38 . The butterfly triplet  37  includes a first butterfly I unit (BFI)  31   a , a butterfly II unit (BFII)  32 , and a butterfly III unit (BFIII)  33 . The output portion  39  contains a single, second, BFI unit  31   b  (as 16=2 4 , and 4 mod 3=1). A control unit  36  controls the operations of the BFIs  31   a ,  31   b ; the BFII  32 , the BFIII  33 , and provides appropriate coefficients to the multiplier  38 . The control unit  36  includes a pipeline step-count register  36   a , which keeps track of the current pipeline step-count, which runs from zero to N−1 for an N-point IFFT processor. The control unit  36  controls the butterfly triplet  37 , the multiplier  38  and the output portion  39  according to the step-count register  36   a.    
     [0060] Please refer to FIG. 4 with reference to FIGS. 2 and 3. FIG. 4 is a schematic diagram of a general butterfly unit BFI  100  according to the present invention. The general butterfly BFI  100  contains a single complex input X I (k)  101 , and a single complex output X O (k)  102 . The process diagram of FIG. 1 would seem to indicate that BFI  100  should have two inputs and two outputs, however the actual implementation is not so restricted. On the contrary, the IFFT  30  has a pipelined architecture, and so inputs are not necessarily simultaneously available. However, two inputs  110  can be clocked in at two respective times, as indicated by the pipeline step-count value “k” in X I (k)  101 , the value of which is in the step-count register  36   a , and at some time later, two corresponding outputs  102  can be clocked out at their respective times, as indicated by the “k” in X O (k)  102 . Hence, there exists no actual conflict between the process algorithm, as depicted in FIG. 1, and the physical implementation, as depicted in FIG. 4. BFI  100  includes a delay feedback loop implemented with a buffer  103 . The buffer  103 , a first in first out (FIFO) buffer, holds storage for a predetermined number “L 1 ” of complex values. The value of “L 1 ” is given by:  
       L   1   =N /(2×8 p )  
     [0061] The value “p” corresponds to the recursion number described above with respect to the mathematical background, and indicates the butterfly triplet grouping number within which BF1  100  serves as a butterfly unit, with the first butterfly triplet (that accepting the input points) beginning with p=0, the next (sequentially after the first triplet) with p=1, etc. The output portion  39  is also given a value for “p”, which is one greater than the sequentially last butterfly triplet. For example, in BFI  31   a  of FIG. 3, the value of “p” is zero (BFI  31   a  being within the first triplet), whereas the value of “p” for BFI  31   b  is one (which is one greater than the value of “p” for the last, and only, triplet). N is the number of points for which the IFFT circuit is designed. In the IFFT  30  of FIG. 3, N=16. Hence, BFI  31   a  has a buffer size “L 1 ” of 8, and BF1  31   b  has a buffer “L 1 ” of 1. The general BFI  100  includes a subtractor  104  and an adder  105 . Control lines  106   a  and  106   b  are controlled by the control unit  36 , and respectively control the selection output of two multiplexers  107   a  and  107   b . Multiplexer  107   a  accepts as input the complex result  105   a  generated by the adder  105  and the data  103   a  output by the FIFO buffer  103 , and selects either value  103   a ,  105   a  as the output X O (k)  102  according to the control line  106   a . Multiplexer  107   b  accepts as input the complex result  104   a  generated by the subtractor  104  and the input data X I (k)  101 , and selects either value  101 ,  104   a  as output  103   i  according to the control line  106   b , which output  103   i  is then fed as input into the FIFO  103 . Hence, FIFO  103  stores either results  104   a  from the subtractor  104 , or input data X I (k)  101 . The output X O  (k)  102  is either the output  103   a  from the FIFO  103 , or the result  105   a  from the adder  105 .  
     [0062] Please refer to FIG. 5 with reference to FIGS. 2 and 3. FIG. 5 is a schematic drawing of a general butterfly unit BFII  200  according to the present invention. The general butterfly BFII  200  is used as the butterfly unit BFII  32 . The principle of operation of the general BFII unit  200  is very similar to that of the general BFI unit  100 . However, the general BFII  200  further includes a π/2 complex rotator  208 , and related control circuitry. The BFII  200  accepts a complex input  201  with each clock cycle, as determined by step-count register  36   a , and generates a complex output  202 . Input  201  is received from the output  102  of a general BFI  100 . For example, BFII  32  accepts as input the output of BFI  31   a  in the processor circuit  30 . FIFO buffer  203  is used to implement a delay feedback loop, with a buffer size “L 2 ” given as:  
       L   2   =N /(4×8 p )  
     [0063] Again, “p” indicates the butterfly triplet number in which the general BFII  200  is located, and “N” is the point size of the IFFT processor. For the example circuit  30 , the size “L 2 ” of FIFO  203  in BFII unit  32  is four (16/4×8 0 =4). The general BFII  200  also includes a subtractor  204 , an adder  205 , the π/2 complex rotator  208 , and muliplexers  207   a ,  207   b  and  207   c . Control lines  206   a ,  206   b  and  206   c , which control the selection outputs of their respective MUXes  207   a ,  207   b  and  207   c , are set by the control unit  36  according to the value held within the step-count register  36   a . Exactly how the control lines  206   a ,  206   b  and  206   c  should be held for the circuit  30  is clearly shown in FIG. 2.  
     [0064] Please refer to FIG. 6 with reference to FIGS. 2 and 3. FIG. 6 is a schematic drawing of a general butterfly unit BFIII  300  according to the present invention. The general butterfly BFIII  300  is used as the butterfly unit BFIII  33 . The principle of operation of the general butterfly unit BFIII  300  is very similar to that of the general butterfly unit BFII  200 . However, the general BFIII  300  further includes a π/4 complex rotator  308 , and related control circuitry. The BFIII  300  accepts a complex input  301  with each clock cycle, as determined by step-count register  36   a , and generates a complex output  302 . Input  301  is received from the output  202  of a general BFII  200 . For example, BFIII  33  accepts as input the output of BFII  32  in the processor circuit  30 . FIFO buffer  303  is used to implement a delay feedback loop, with a buffer size “L 3 ” given by:  
       L   3   =N /(8×8 p )  
     [0065] Again, “p” indicates the butterfly triplet number in which the general BFIII  300  is located, and “N” is the point size of the IFFT processor. For the example circuit  30 , the size “L 3 ” of FIFO  303  in BFIII unit  33  is two (16/8×8 0 =2). The general BFIII  300  also includes a subtractor  304 , an adder  305 , a π/2 complex rotator  308 , the π/4 complex rotator  309 , and four muliplexers  307   a ,  307   b ,  307   c , and  307   d . Control lines  306   a ,  306   b ,  306   c  and  306   d , which control the selection outputs of their respective MUXes  307   a ,  307   b ,  307   c  and  307   d , are set by the control unit  36  according to the value held within the step-count register  36   a . Exactly how the control lines  306   a ,  306   b ,  306   c  and  306   d  should be held for the circuit  30  is clearly shown in FIG. 2.  
     [0066] Output  302  from BFIII  33  is fed into the complex multiplier  38 , along with a coefficient W″[k] provided by the control unit  36  from a coefficient table  36   b . As with the butterfly control lines, the coefficient W″[k] is determined by the value held within the step-count register  36   a  (that is, “k” is the step-count value  36   a ), and is indicated in FIG. 2.  
     [0067] Finally the complex product output by the complex multiplier  38  is fed as input  101  into BFI  31   b . The FIFO  103  of BFI  31   b  is simply one unit in size, and control of the selectors is quite straightforward.  
     [0068] Taking all of the delays incurred by the feedback loops into account, for the 16-point DIT IFFT circuit  30 , 16 clock cycles after the first input X[0] is provided, the first result x[0] is provided as the output. Note, however, that the outputs x[n], which are the respective inverse fast Fourier transform of the inputs X[n], are not ordered in time, but instead appear sequentially as x[0], x[8], x[4], x[12], x[2], x[10], x[6], x[14], x[1], x[9], x[5], x[13], x[3], x[11], x[7] and finally x[15].  
     [0069] Please refer to FIG. 7. FIG. 7 is a schematic drawing of a π/2 complex rotator  400  according to the present invention. The π/2 complex rotator  400  is to implement the π/2 complex rotator  308  in the general butterfly unit BFIII  300 , and to implement the π/2 complex rotator  208  in the general butterfly unit BFII  200 . Any complex number X I (k) input into the π/2 complex rotator  400  will have a real part X IR (k)  401   a  and an imaginary part X II (k)  401   b . Similarly, the output X O (k) from the π/2 complex rotator  400  will have a real part X OR (k)  402   a  and an imaginary part X OI (k)  402   b . The output X O (k) is given by: X O (k)=X I (k)×(j), “j” being the square root of negative one. To perform a π/2 complex rotation, the π/2 complex rotator  400  simply provides the input real part  401   a  as the output imaginary part  402   b , and multiplies the input imaginary part  401   b  by (−1) and provides the resulting product as the output real part  402   a . Multiplying by (−1) is easily performed by the well-known twos-complement procedure. Consequently, the π/2 complex rotator  400  is very easy to implement.  
     [0070] Please refer to FIG. 8. FIG. 8 is a schematic drawing of a π/4 complex rotator  500  according to the present invention. The π/4 complex rotator  500  is used to implement the π/4 complex rotator  309  in the general butterfly unit BFIII  300 . The π/4 complex rotator  500  is used to implement Eqn. 5, accepting an input complex number X I (k)  501  and generating a corresponding output complex number X O (k)  502  that is given by:  
       X   O ( k )=(2 −1 +2 −3 +2 −4 +2 −6 +2 −8 )×(1 +j )× X   I ( k )  
     [0071] The π/4 complex rotator  500  includes a π/2 complex rotator  503 , the structure of which is indicated in FIG. 7 as the π/2 complex rotator  400 ; a 2-to-1 complex adder  504 ; five right shifters  505   a - 505   e , and a 5-to-1 complex adder  506 . For an input number X I (k)  501 , the π/2 complex rotator  503  generates as output  503   o  the value X I (k)×j. As input, the complex adder  504  accepts the output  503   o  and the original input X I (k)  501 , and thus generates as output  504   o  the value (1+j)×X I (k). Shifter  505   a  right shifts output  504   o  by 1, essentially multiplying output  504   o  by 2 −1 , and presents this result as output  507   a . Shifter  505   b  right shifts output  504   o  by 3, which is the same as multiplying output  504   o  by 2 −3 , and presents this result as output  507   b . Shifter  505   c  right shifts output  504   o  by 4, thereby multiplying output  504   o  by 2 −4 , and presents this result as output  507   c . Shifter  505   d  right shifts output  504   o  by 6, multiplying output  504   o  by 2 −6 , with the result as output  507   d . Finally, shifter  505   e  right shifts output  504   o  by 8, generating as output  507   e  the value of  504   o  multiplied by 2 −8 . The adder  506  accepts as input the complex values on lines  507   a - 507   e , adding them together to generate the output value X O (k)  502 . The π/4 complex rotator  500  is thus shown to be relatively easy to implement, requiring only a π/2 complex rotator  503  (which is also easy to implement), two complex adders  504  and  506 , and five right shifters  505   a  to  505   e.    
     [0072] The methodology used to implement the present invention 16-point DIT IFFT  30  of FIGS. 2 and 3 can be scaled up to higher values N, as may be required, and the manner of doing so should be clear to one skilled in the art from the preceding discussion, utilizing the BFI  100 , BFII  200  and BFIII  300  units with appropriate FIFO sizes. For example, refer to FIG. 9. FIG. 9 is a process diagram for a 32-point radix-2 3  DIT IFFT process according to the present invention, as derived from the equations previously discussed. Butterfly units BFI, BFII and BFII consistent with the general butterfly units BFI  100 , BFII  200  and BFIII  300  of FIGS. 4, 5 and  6 , respectively, are indicated. In FIG. 9, the term W″4 is identified as the π/4 complex rotator. The general coefficients W′n are given by W′n=exp(j×2π×n/32).  
     [0073] Please refer to FIG. 10. FIG. 10 is a schematic design  600  for the 32-point radix-2 3  DIT IFFT process of FIG. 9. The IFFT  600  clocks in as input  601  32 frequency values X [k], where “k” ranges from zero to 31 and is determined by the pipeline step-count register  606   a  within the control unit  606 , and generates unordered output points x[n]  602 . The IFFT  600  includes a butterfly triplet  607  multiplicatively connected to an output portion  609  by a complex multiplier  608 . In this case, however, the output portion  609  includes a butterfly unit BFI  601   b  serially connected to a butterfly unit BFII  602   b , as 32=3 5 , and 5 mod 3=2. The butterfly unit BFII  602   b  serves as the output terminal of the IFFT circuit  600 . All butterfly units BFI  601   a ,  601   b ; BFII  602   a ,  602   b ; and BFIII  603  are implemented by the general butterfly units BFI  100 , BFII  200  and BFIII  300 , with appropriate value substitutions for “p” and “N” to determine the respective FIFO buffer sizes. For example, BFI  601   a  has a FIFO buffer size “L 1 ” of 16; BFII  602   a  has a FIFO buffer size “L 2 ” of 8, and BFIII has a buffer size “L 3 ” of 4. In the output portion  609 , with “p” equal to one, BFI  601   b  has a FIFO buffer size “L 1 ” of 2, and BFII  602   b  has a buffer size “L 2 ” of 1.  
     [0074] States of the controls  605  for the various MUXes within the butterfly units BFI  601   a ,  601   b ; BFII  602   a ,  602   b ; and BFIII  603  are determined by the value held within the pipeline step-count register  606   a . These states can be determined from the process algorithm shown in FIG. 9, taking into account the various delays imposed by the butterfly units. General coefficients W′n are stored within a coefficient table  606   b  of the control unit  606 , and are provided to the complex multiplier  608  based upon the value held within the step-count register  606   a . In effect, as with the circuit  30 , the outputs  605  of the control unit  606 , which control the butterfly units  601   a ,  601   b ,  602   a ,  602   b ,  603 , and which provides complex values to the multiplier  608 , are determined by a state machine as implemented by the control unit  606 , with the current state indicated by the step-count register  606   a.    
     [0075]FIGS. 11A and 11B are process diagrams for a 64-point radix-2 3  DIT IFFT process according to the present invention. The associated DIT IFFT circuit  700  is shown in FIG. 12. Butterfly units BFI, BFII and BFII consistent with the general butterfly units BFI  100 , BFII  200  and BFIII  300  of FIGS. 4, 5 and  6 , respectively, are indicated. In FIGS. 11A and 11B, the term W″8 is identified as the π/4 complex rotator. The general coefficients  706   b  W′n are given by W′n =exp(j×2π×n/64). The control unit  706  can be thought of as a state machine, the state of which is determined by the step-count register  706   a . Control outputs  705  are determined by the state  706   a , and are consistent with the process algorithm depicted in FIGS. 11A and 11B. Note that output portion  709 , with “p” equal to 1, is actually a complete butterfly triplet, as 64=2 6 , and 6 mod 3=0.  
     [0076] As a final example, a 128-point radix-2 3  DIT IFFT processor  800  according to the present invention is depicted in FIG. 13. The output portion  809  includes a single BFI unit  801 , as 128=2 7 , and 7 mod 3=1. The circuit  800  further includes two butterfly triplets  807   a  and  807   b , with “p” values of zero and one, respectively. Output portion  809  thus has a “p” value of two. Butterfly triplet  807   a  is multiplicatively connected to butterfly triplet  807   b  by way of complex multiplier  808   a . Butterfly triplet  807   b  is multiplicatively connected to output portion  809  by way of complex multiplier  808   b . Coefficients W″1[k] and W″2[k] are respectively provided to the complex multipliers  808   a  and  808   b  from a coefficient table  806   b  according to the value held in the pipeline step-count register  806   a . Determining the coefficients  806   b , and the outputs  805  provided by the control unit  806  according to the step-count register  806   a , should be clear from the above disclosure to one skilled in the art.  
     [0077]FIG. 14 is a simple block diagram of an IFFT/FFT processor  900  according to the present invention. When switches  901  are set to select complex conjugate circuitry  902 , the processor  900  serves as a DIT FFT processor, accepting position inputs I[x] and generating corresponding (but unordered) frequency outputs O[x]. When switches  901  are set to bypass the complex conjugate circuits  902 , the processor  900  serves as a DIT IFFT, accepting frequency inputs I[x] and generating corresponding (but unordered) position outputs O[x]. Each complex conjugate circuit  902  simply accepts an input complex value and outputs the complex conjugate of that input value.  
     [0078] Regardless of the type of processor implemented, be it IFFT or FFT, the processor suffers from the fact that the output sequencing does not correspond to the input sequencing. This is true of both DIT and DIF processors. To correlate an input sequence with its corresponding output sequence, a reordering procedure must be performed. It would be desirable to have the sequencing of the inputs match that of the outputs, and this is typically done by way of additional buffer memory. For an N-point real-time processor, two buffers each containing N complex number slots of memory is typically thought to be required: one buffer to store the data streaming out of the processor, and another buffer used to stream out ordered data that has been completely received and buffered. However, it is, in fact, possible to use a memory that requires only N data slots, while simultaneously supporting and reordering a continuous stream of output that exceeds N complex numbers in length. We call this “two-phase memory address control”. In the following discussion, for the sake of consistency with the above disclosure, DIT IFFT processors are considered. However, it will be appreciated that the disclosure is equally applicable to DIF FFT, DIF IFFT, or DIT FFT processors.  
     [0079] Please refer to FIG. 15. FIG. 15 is a block diagram of a 16-point radix-2 3  DIT IFFT processor  1000  that supports ordered outputs according to the present invention. The processor  1000  contains the 16-point radix-2 3  DIT IFFT unit  30  of FIG. 3, with the addition of a reordering circuit  1100  connected to the output portion  1002  of the IFFT unit  30 . The 16-point radix-2 3  DIT IFFT unit  30  is used for the sake of convenience for a specific example of the present invention N-point reordering circuit. The reordering circuit  1100  comprises as a buffering means a dual-port random access memory (RAM)  1101  that can simultaneously support read and write operations in the same clock cycle, as indicated by the pipeline step count register  1004 . The RAM  1110  holds space, i.e., memory slots, for N complex numbers, addressable from zero to N−1. As the processor  1000  is a 16-point processor, N is 16. The RAM  1101  thus has 16 complex number memory address slots, which may be addressed from zero to  115 . The reordering circuit  1100  also contains as an address staggering means a latch  1101 , such as a D-type flip-flop, for buffering a single memory address of the RAM  1101 . Finally, the reordering circuit  1100  requires some additions to the control unit  1006 , an address generating means in the form of an address look-up table  1103 , a cycle bit  1104 , and any associated circuitry to support the functionality described in the following. Designing such additional support circuitry should be clear and obvious to one reasonably skilled in the art, and so is not elaborated upon here.  
     [0080] As part of an addressing means, the RAM  1101  has a read address line  1101   r  and a write address line  1101   w . A complex number on the output portion  1002  of the IFFT unit  30  is written into the RAM  1101  at the memory address slot indicated by the write address line  1101   w . Similarly, the RAM  1101  generates as output  1003  the value contained in the memory address slot indicated by the read address lines  1101   r . Such operations of the RAM  1101  are familiar to those skilled in the art. The latch  1102  is placed across the read address lines  1101   r  and the write address lines  1101   w , so that the latch  1102  obtains an address from the read address lines  1101   r , and a next clock cycle later (as determined by the pipeline step-count register  1004 ), provides that address to the write address lines  1101   w . The purpose of the latch  1102  is simply to stagger the read and write addresses by one clock cycle, as measured by the pipeline step-count register  1004 . This will be illustrated in more detail below. It is the control unit  1006  that provides the read addresses  1101   r  (and by extension the write addresses  1101   w ) to the RAM  1101 , by way of the address look-up table  1103  and the cycle bit  1104 . The address look-up table  1103  contains a list of addresses for addressing the RAM  1101  in the form of entries  1103   i  I 0  to I N−1 , and the cycle bit  1104  is used to determine the phase for memory addressing. After a complete cycle of N clock ticks (determined by the step-count register  1004 , and 16 in the present example), the cycle bit  1104  is toggled. When the cycle bit  1104  is set, the control unit  1006  provides addresses  1101   r  according to values obtained from the entries  1103   i  in the address look-up table  1103 , indexed according the step-count register  1004 . When the cycle bit  1104  is cleared, the control unit  1006  provides addresses  1101   r  according to the step-count register  1004 . In both phases, the determining value used for indexing or addressing is simply one greater than the value held within the step-count register  1004 . The cycle bit  1104  toggles (by way of cycle bit toggling means, such as a comparator, bit wise logic, or the like) when the pipeline step-count register  1004  reaches a value of N−1, in this case, a value of 15.  
     [0081] For the IFFT  30 ,  16  inputs X[0] to X[15] are clocked into the circuit  30  sequentially, at times T 0  to T 15 , respectively, with corresponding pipeline step-count values of 0 to 15, respectively. Output values x[0] to x[15] first begin appearing at output port  1002  at time T 16 , as indicated by Table 1 below:  
                       TABLE 1                           Pipeline           Time   step-count value   Output Value                                            T 16     0   x1[0]        T 17     1   x1[8]        T 18     2   x1[4]        T 19     3   x1[12]       T 20     4   x1[2]        T 21     5   x1[10]       T 22     6   x1[6]        T 23     7   x1[14]       T 24     8   x1[1]        T 25     9   x1[9]        T 26     10   x1[5]        T 27     11   x1[13]       T 28     12   x1[3]        T 29     13   x1[11]       T 30     14   x1[7]        T 31     15   x1[15]                  
 
     [0082] To support the present invention as regards the IFFT processor  30 , the address look-up table  1103  has N entries, zero to N−1, that simply follow the sequential ordering of the outputs x[n] as they occur in the time domain as given by the pipeline step-count register  1004 . These entries provide ordering decoding information, as shown in Table 2 below:  
                           TABLE 2                                   Look-up table entry               I 0     RAM Address value                                                    I 0      0           I 1      8           I 2      4           I 3      12           I 4      2           I 5      10           I 6      6           I 7      14           I 8      1           I 9      9           I 10     5           I 11     13           I 12     3           I 13     11           I 14     7           I 15     15                      
 
     [0083] To understand the operation of the reordering circuit  1100 , please refer to the following Table 3. Output IFFT output values  1002  x1 [n] correspond to IFFT input values  1001  from T 0  to T 15 . Output values  1002  x2[n] correspond to input values  1001  from T 16  to T 31 . Output values  1002  x3[n] correspond to input values  1001  from T 32  to T 47 ,  
                                       TABLE 3                           Pipeline                               step-count   Cycle   IFFT   Read   Write       Time   value   bit   output   address   address   Output                                                            T 16     0   1   x1[0]    8   0   Undefined       T 17     1   1   x1[8]    4   8   Undefined       T 18     2   1   x1[4]    12   4   Undefined       T 19     3   1   x1[12]   2   12   Undefined       T 20     4   1   x1[2]    10   2   Undefined       T 21     5   1   x1[10]   6   10   Undefined       T 22     6   1   x1[6]    14   6   Undefined       T 23     7   1   x1[14]   1   14   Undefined       T 24     6   1   x1[1]    9   1   Undefined       T 25     9   1   x1[9]    5   9   Undefined       T 26     10   1   x1[5]    13   5   Undefined       T 27     11   1   x1[13]   3   13   Undefined       T 28     12   1   x1[3]    11   3   Undefined       T 29     13   1   x1[11]   7   11   Undefined       T 30     14   1   x1[7]    15   7   Undefined       T 31     15   0   x1[15]   0   15   x1[0]        T 32     0   0   x2[0]    1   0   x1[1]        T 33     1   0   x2[8]    2   1   x1[2]        T 34     2   0   x2[4]    3   2   x1[3]        T 35     3   0   x2[12]   4   3   x1[4]        T 36     4   0   x2[2]    5   4   x1[5]        T 37     5   0   x2[10]   6   5   x1[6]        T 38     6   0   x2[6]    7   6   x1[7]        T 39     7   0   x2[14]   8   7   x1[8]        T 40     8   0   x2[1]    9   8   x1[9]        T 41     19   0   x2[9]    10   9   x1[10]       T 42     10   0   x2[5]    11   10   x1[11]       T 43     11   0   x2[13]   12   11   x1[12]       T 44     12   0   x2[3]    13   12   x1[13]       T 45     13   0   x2[11]   14   13   x1[14]       T 46     14   0   x2[7]    15   14   x1[15]       T 47     15   1   x2[15]   0   15   x2[0]        T 48     0   1   x3[0]    8   0   x2[1]        T 49     1   1   x3[8]    4   8   x2[2]        T 50     2   1   x3[4]    12   4   x2[3]        T 51     3   1   x3[12]   2   12   x2[4]        T 52     4   1   x3[2]    10   2   x2[5]        T 53     5   1   x3[10]   6   10   x2[6]        T 54     6   1   x3[6]    14   6   x2[7]        T 55     7   1   x3[14]   1   14   x2[8]        T 56     8   1   x3[1]    9   1   x2[9]        T 57     19   1   x3[9]    5   9   x2[10]       T 58     10   1   x3[5]    13   5   x2[11]       T 59     11   1   x3[13]   3   13   x2[12]       T 60     12   1   x3[3]    11   3   x2[13]       T 61     13   1   x3[11]   7   11   x2[14]       T 62     14   1   x3[7]    15   7   x2[15]       T 63     15   0   x3[15]   0   15   x3[0]        T 64     0   0   x4[0]    1   0   x3[1]                   
 
     [0084] When the cycle bit  1104  is set to one, the control unit  1006  adds one to the value held in the step-count register  1004 , and utilizes the result to index into the address look-up table  1103  to obtain a read address. This read address is then provided on read address lines  1101   r . The means for performing this action, the generation of a first phase address, should be trivial to implement for one of reasonable skill in the art. For example, at time T 16  the cycle bit  1104  is a one; the pipeline step-count register  1004  holds a value of 0; incrementing this value by one obtains an address look-up table  1103  index of one; entry  1103   i  I 1  of the address look-up table  1103  contains the RAM memory address value of 8, as shown in Table 2. Hence, the RAM read address  1101   r  is 8-at time T 16 . When the cycle bit  1104  is cleared, the control unit  1006  sets the read address lines  1101   r  to be equal to one greater than the value held in the step-count register  1004 . Again, the means for generating this second type of address, a second phase address, should be trivial to one in the art. In either case (i.e., either phase), one clock cycle later, as measured by the step-count register  1004 , the same address provided to the read address lines  1101   r  will be present upon write address lines  1101   w , due to the latch  1102 . Data  1002  is written into the RAM  1101  at the write address  1101   w , and read from the RAM  1101  as output  1003  from the read address  1002 . When the pipeline step-count register  1004  reaches a value of N−1, which in this case is 15, the cycle bit  1104  is toggled from zero to one, or one to zero, by the cycle bit toggling circuitry. Although an additional delay of N clock cycles is incurred, the end result is that a real-time stream of ordered output values  1002  appears at the output  1003 .  
     [0085] The above concept of output reordering is actually quite general in nature. A stream of input data X[k] in a first local time domain T1 is transformed into a corresponding stream of data x[n] in a second local time domain T2 by a processor. Each local time domain, in the above example, is marked by a complete cycle of the pipeline step-count register  1004 , running from zero to N−1, i.e., 15. Ordering, as applied here, means that each data point X[k] and x[n] satisfies the condition that if input data X[p] occurs at time T1 j  within the first local time domain T1, where p is a number between zero to N−1, i.e., 15, then the corresponding output data x[p] occurs at time T2 j  within the second local time domain T2. Hence, although in the above example the inputs were sorted in ascending sequential order from X[0] to X[15], this is not a necessary condition for the present invention reordering scheme. It would be possible, for example, in a suitably designed circuit to provide X[15] to X[0] sorted in descending sequential order, and obtain at the output of the reordering circuit x[i  5 ] to x[0], again in descending sequential order. The present invention reordering circuit simply matches up the local time domains of the inputs with those of the outputs.  
     [0086] Generalizing the above reordering circuit  1100  for N points should be clear from the above description. That is, the above can easily be implemented for any value of N, so long as the following condition holds: for unordered data {X 0 , X 1 , . . . , X n } dispersed over a local time interval T defined by {T 0 , T 1 , . . . , T n }, for each X k  occurring at time T j , there occurs at time T k  an X j . A quick reference shows this to hold true for Table 1. For example, x1[8] occurs at pipeline step-count value  1004  of 1, and x1[1] occurs at pipeline step-count value  1004  of 8. A quick perusal of the process diagrams of FIGS. 9 and 11A,  11 B will also show these conditions to hold true.  
     [0087] It certainly isn&#39;t necessary to restrict the reordering unit of the present invention to reordering outputs for a DIT processor; that the present invention can be also applied to a DIF FFT processor. Moreover, the reordering circuit can be used on DIT FFT and DIF IFFT processors, which require unordered inputs and generate ordered outputs. Such an arrangement is shown in FIG. 16.  
     [0088] The memory used in the above reordering circuits for buffering data should be capable of performing both a read and a write operation for each cycle of the pipeline, as indicated by the pipeline step-count register (i.e., for each increment of the value held within the pipeline step-count register). This does not mean that a dual-ported RAM module is required. Such a design is only the preferred embodiment. It is fully possible for other designs that support a standard single-port RAM module. In this case, each pipeline operation would require at least two RAM bus cycles, so that read write operations could be performed during the same pipeline operation. The read and write address ports would also be the same. In one RAM bus cycle, the read address as obtained from the control unit would be used. In another write cycle the address as obtained from the address latch would be used.  
     [0089] Finally, it should be appreciated that many means may be used to generate an address for the first phase of the present invention reordering circuit. That is, an address look-up table is not the only means that may be used to generate a first phase address. Such addresses may, for example, be calculated. Consider, the following table:  
                                   TABLE 4                                   Look-up                       table entry       RAM           I 0         Address value                                                            I 0      0000   0   0000           I 1      0001   8   1000           I 2      0010   4   0100           I 3      0011   12   1100           I 4      0100   2   0010           I 5      0101   10   1010           I 6      0110   6   0110           I 7      0111   14   1110           I 8      1000   1   0001           I 9      1001   9   1001           I 10     1010   5   0101           I 11     1011   13   1101           I 12     1100   3   0011           I 13     1101   11   1011           I 14     1110   7   0111           I 15     1111   15   1111                      
 
     [0090] Table 4 is basically identical to Table 2, but shows entries in binary as well as decimal. A look at the right hand column of Table 4 clearly shows that the entries in the look-up table are actually nothing more than the “reflection” of their corresponding indices. By “reflection”, it is meant that the most significant bit (MSB) in the original becomes the least significant bit (LSB) in the reflection, the second MSB in the original becomes the second LSB in the reflection, and so on. For example, the entry at index (0001) has a value of (1000). The entry at index (1010) has a value of (0101). Such simple bit-wise reflections are easily performed by appropriate logic, and can so eliminate the need for a look-up table. For example, in FIG. 15, the address generating means in the IFFT control unit  1006  would include logic to add one to the step count register value  1004  to generate an intermediate result. Another set of logic would include circuitry to perform a bit-wise reflection of this intermediate result to generate a first phase address. Finally, a last set of logic would provide the first phase address to the read address lines  1101   r  when the cycle bit  1104  is a one, and simply provide the intermediate result as the second phase address to the read address lines  1101   r  when the cycle bit  1104  is a zero. Further, it should be appreciated that addresses, whether first phase or second phase, can be shifted by a base value (that is, offset from zero) while still keeping to the spirit of the present invention.  
     [0091] In contrast to the prior art, the present invention provides a butterfly triplet, which is composed of a BFI unit, a BFII unit and a BFIII unit, and an output portion that contains at least a BFI unit, and which is connected to the butterfly triplet by way of a complex multiplier. The BFII unit includes a π/2 complex rotator, and the BFIII includes both a π/2 and a π/4 complex rotator. All of the BFI, BFII and BFIII units are controlled by control circuitry according to a pipeline step-count value, as are the coefficients provided to the complex multiplier. In addition, the present invention provides a reordering circuit that ensures that the sequence ordering of the inputs matches that of the outputs in the time domain. For an N-point real-time processor, the reordering circuit requires a buffer memory having only N slots for storing N complex numbers. This memory is sufficient to provide real-time streaming ordered inputs and outputs that exceeds N points in length, and that is, in fact, of unlimited and unbroken length. Read and write access to the reordering buffer memory is staggered so that a read at an address in the reordering buffer memory is immediately followed by a write to the same address, but one pipeline cycle later. Utilization of an address look-up table controls the read address used to fetch from (and hence write to) the reordering buffer. The address table is indexed according to a value obtained from a pipeline step-count register.  
     [0092] Those skilled in the art will readily observe that numerous modifications and alterations of the device may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.