Abstract:
A digital signal processor (DSP) including two multipliers and two three-input arithmetic logic units is able to perform a sequence of Fast Fourier Transform butterfly calculations such that results of a butterfly calculation in said sequence are available two cycles after results of an immediately previous butterfly calculation in said sequence are available.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS  
       [0001]    This application is a continuation of U.S. patent application Ser. No. 09/587,617, filed Jun. 5, 2000, which is hereby incorporated by reference. 
     
    
     
       BACKGROUND OF THE INVENTION  
         [0002]    A digital signal processor (DSP) is a computer that is designed to optimize digital signal processing tasks. A non-exhaustive list of examples of such processing tasks includes Fast Fourier Transform (FFT) calculations, digital filters, image processing, and speech recognition.  
       
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS  
       [0003]    Embodiments of the invention are illustrated by way of example and not limitation in the figures of the accompanying drawings, in which like reference numerals indicate corresponding, analogous or similar elements, and in which:  
         [0004]    [0004]FIG. 1 is a simplified block diagram illustration of an exemplary digital signal processor (DSP) to perform Fast Fourier Transform (FFT) calculations, according to an embodiment of the invention;  
         [0005]    [0005]FIG. 2 is a tabular illustration of the contents of registers of the exemplary DSP of FIG. 1 over several cycles; and  
         [0006]    [0006]FIG. 3 is another tabular illustration of the contents of registers of the exemplary DSP of FIG. 1 over several cycles. 
     
    
       [0007]    It will be appreciated that for simplicity and clarity of illustration, elements shown in the figures have not necessarily been drawn to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity.  
       DETAILED DESCRIPTION OF THE INVENTION  
       [0008]    In the following detailed description, numerous specific details are set forth in order to provide a thorough understanding of embodiments of the invention. However it will be understood by those of ordinary skill in the art that the embodiments of the invention may be practiced without these specific details. In other instances, well-known methods, procedures, components and circuits have not been described in detail so as not to obscure the embodiments of the invention.  
         [0009]    [0009]FIG. 1 is a simplified block diagram illustration of an exemplary digital signal processor (DSP)  2  to perform Fast Fourier Transform (FFT) calculations, according to an embodiment of the invention. DSP  2  may perform other calculations, but these are not described so as not to obscure the description of the embodiments of the invention. DSP  2  may include two three-input arithmetic logic units (ALU)  10  and  12 , each capable of receiving three inputs and performing any combination of addition and subtraction on the three inputs in response to program instructions to yield a combined result. DSP  2  may also include multipliers  14  and  16 , labeled MUL 1  and MUL 2 , to perform multiplication on real and imaginary sinusoidal data inputs B R  and B I  and coefficients W R  and W I  using conventional techniques. Results from multipliers  14  and  16  may be stored in registers  18  and  20  respectively, labeled P 0  and P 1 , from which the results may then be input to ALUs  10  and  12 .  
         [0010]    DSP  2  may also include two registers  22  and  24 , labeled Zr 0  and Zr 1 , to receive real cosinusoidal data input A R , and two registers  26  and  28 , labeled Zi 0  and Zi 1 , to receive imaginary cosinusoidal data input A I . DSP  2  may also include a multiplexer  30  to selectably provide data from registers Zr 0 , ZrI and Zi 1  to ALUs  10  and  12 . DSP  2  may optionally concatenate a rounding constant C to the multiplexed data, shown at reference numeral  35 , to form a low-ordered portion of the concatenated input to ALUs  10  and  12 .  
         [0011]    DSP  2  may also include two registers  34  and  36 , labeled A 0  and A 1 , to receive output from ALU  10 , and two registers  38  and  40 , labeled A 2  and A 3 , to receive output from ALU  12 . DSP  2  may also include a register  42 , labeled A 0   hp,  to receive a high-ordered portion of the data stored in A 0 , and a register  44 , labeled A 2   hp,  to receive a high-ordered portion of the data stored in A 2 .  
         [0012]    DSP  2  may also include a multiplexer  46  to selectably provide data from A 0   hp  or A 2   hp.  DSP  2  may also include a multiplexer  48  to selectably provide data from A 1  or A 3 .  
         [0013]    DSP  2  may include additional components that are not shown in FIG. 1 so as not to obscure the description of embodiments of the invention.  
         [0014]    An exemplary FFT butterfly calculation will now be described with respect to FIG. 1 and FIG. 2, which is a tabular illustration of the contents of registers of DSP  2  over several cycles.  
         [0015]    Each FFT butterfly calculation, indexed by k, is to result in four outputs:  
         OUT 0 [ k]=A   R   [k]+B   R   [k]*W   R   [k]−B   I   [k]*W   I   [k]   
         OUT 1 [ k]=A   I   [k]+B   R   [k]*W   I   [k]+B   I   [k]*W   R   [k]   
         OUT 2 [ k]=A   R   [k]−B   R   [k]*W   R   [k]+B   I   [k]*W   I   [k]   
         OUT 3 [ k]=A   I   [k]−B   R   [k]*W   I   [k]−B   I   [k]*W   R   [k]   
         [0016]    where, if the optional rounding constant is used, then A R  [k] (A I  [k]) is replaced by A R  [k]* C (A I  [k]*C) in the equations above, and the following description will demonstrate one example of how these four outputs for a particular butterfly calculation may be calculated in two cycles.  
         [0017]    In an exemplary initial state, registers Zr 0  and Zi 0 , and registers Zr 1  and Zi 1  may store the first real cosinusoidal data input (A R  [1]) and the first imaginary cosinusoidal data input (A I  [1]), respectively, register P 0  may store the product of the first real sinusoidal data input (B R  [1]) and the first real coefficient (W R  [1]), and register P 1  may store the product of the first imaginary sinusoidal data input (B I  [1]) and the first imaginary coefficient (W I  [1]).  
         [0018]    CYCLE #1  
         [0019]    During a first cycle, labeled CYCLE #1, the following actions may occur:  
         [0020]    a) multiplexer  30  may retrieve the contents of Zr 1  (A R  [1]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [1]*W R  [1]) and subtract therefrom the contents of register P 1  (B I  [1]*W I  [1]) and store the result (OUT 0  [1]) in register A 0 ; ALU  12  may add the possibly concatenated output to the contents of register P 1  and subtract therefrom the contents of register P 0  and store the result (OUT  2  [1]) in register A 2 ;  
         [0021]    b) registers Zr 0  and Zi 0  may receive the real and imaginary cosinusoidal data inputs for the second FFT butterfly (A R  [2] and A I  [2], respectively); and  
         [0022]    c) multiplier MUL 1  may multiply the first real sinusoidal data input (B R  [1]) with the first imaginary coefficient (W I  [1]) and store the product in register P 0 , and multiplier MUL 2  may multiply the first imaginary sinusoida data input (B I  [1]) with the first real coefficient (W R  [1]) and store the product in register P 1 .  
         [0023]    CYCLE #2  
         [0024]    During a second cycle, labeled CYCLE #2, the following actions may occur:  
         [0025]    a) a high-ordered portion of registers A 0  and A 2  (containing outputs of the first FFT butterfly calculation) may be copied to registers A 0   hp  and A 2   hp,  respectively;  
         [0026]    b) multiplexer  30  may retrieve the contents of Zi 1  (A I  [1]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [1]*W I  [1]) and the contents of register P 1  (B I  [1]*W R  [1]) and store the result (OUT 1  [1]) in register A 1 ; ALU  12  may subtract both the contents of register P 0  and the contents of register P 1  from the possibly concatenated output and store the result (OUT 3  [1]) in register A 3 ; and  
         [0027]    c) multiplier MUL 1  may multiply the second real sinusoidal data input (B R  [2]) with the second real coefficient (W R  [2]) and store the product in register P 0 , and multiplier MUL 2  may multiply the second imaginary sinusoidal data input (B I  [2]) with the second imaginary coefficient (W I  [2]) and store the product in register P 1 ; and  
         [0028]    d) the contents of registers Zr 0  (A R  [2]) and Zi 0  (A I  [2]) may be input to registers Zr 1  and Zi 1 .  
         [0029]    It should be noted that at the end of CYCLE #2, the four outputs of the first FFT butterfly calculation, (OUT 0  [1], OUT 1  [1], OUT 2  [1], OUT 3  [1]) have been calculated and are stored in registers A 0  (and A 0   hp ), A 1 , A 2  (and A 2   hp ) and A 3 , respectively.  
         [0030]    CYCLE #3  
         [0031]    During a third cycle, labeled CYCLE #3, the following actions may occur:  
         [0032]    a) multiplexer  30  may retrieve the contents of Zr 1  (A R  [2]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [2]*W R  [2]) and subtract therefrom the contents of register P 1  (B I  [2]*W I  [2]) and store the result (OUT 0  [2]) in register A 0 ; ALU  12  may add the possibly concatenated output to the contents of register P 1  and subtract therefrom the contents of register P 0  and store the result (OUT 2  [2] ) in register A 2 ;  
         [0033]    b) registers Zr 0  and Zi 0  may receive the real and imaginary cosinusoidal data inputs for the third FFT butterfly (A R  [3] and A I  [3], respectively); and  
         [0034]    c) multiplier MUL 1  may multiply the second real sinusoidal data input (B R  [2]) with the second imaginary coefficient (W I  [2]) and store the product in register P 0 , and multiplier MUL 2  may multiply the second imaginary sinusoidal data input (B I  [2]) with the second real coefficient (W R  [2]) and store the product in register P 1 .  
         [0035]    CYCLE #4  
         [0036]    During a fourth cycle, labeled CYCLE #4, the following actions may occur:  
         [0037]    a) a high-ordered portion of registers A 0  and A 2  (containing outputs of the second FFT butterfly calculation) may be copied to registers A 0   hp  and A 2   hp,  respectively;  
         [0038]    b) multiplexer  30  may retrieve the contents of Zi 1  (A I  [2]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [2]*W I  [2]) and the contents of register P 1  (B I  [2]*W R  [2]) and store the result (OUT 1  [2]) in register A 1 ; ALU  12  may subtract both the contents of register P 0  and the contents of register P 1  from the possibly concatenated output and store the result (OUT 3  [2]) in register A 3 ; and  
         [0039]    c) multiplier MUL 1  may multiply the third real sinusoidal data input (B R  [3]) with the third real coefficient (W R  [3]) and store the product in register P 0 , and multiplier MUL 2  may multiply the third imaginary sinusoidal data input (B I  [3]) with the third imaginary coefficient (W I  [3]) and store the product in register P 1 ; and  
         [0040]    d) the contents of registers Zr 0  (A R  [3]) and Zi 0  (A I  [3]) may be input to registers Zr 1  and Zi 1 , respectively.  
         [0041]    It should be noted that at the end of CYCLE #4, the four outputs of the second FFT butterfly calculation, (OUT 0  [2], OUT 1 [2], OUT 2  [2], OUT 3  [2]) have been calculated and are stored in registers A 0  (and A 0   hp ), A 1 , A 2  (and A 2   hp ) and A 3 , respectively.  
         [0042]    CYCLE #5  
         [0043]    During a fifth cycle, labeled CYCLE #5, the following actions may occur:  
         [0044]    a) multiplexer  30  may retrieve the contents of Zr 1  (A R  [3]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [3]*W R  [3]) and subtract therefrom the contents of register P 1  (B I  [3]*W I  [3]) and store the result (OUT 0  [3]) in register A 0 ; ALU  12  may add the possibly concatenated output to the contents of register P 1  and subtract therefrom the contents of register P 0  and store the result (OUT 2  [3]) in register A 2 ;  
         [0045]    b) registers Zr 0  and Zi 0  may receive the real and imaginary cosinusoidal data inputs for the fourth FFT butterfly (A R  [4] and A I  [4], respectively); and  
         [0046]    c) multiplier MUL 1  may multiply the third real sinusoidal data input (B R  [3]) with the third imaginary coefficient (W I  [3]) and store the product in register P 0 , and multiplier MUL 2  may multiply the third imaginary sinusoidal data input (B I  [3]) with the third real coefficient (W R  [3]) and store the productin register P 1 .  
         [0047]    CYCLE #6  
         [0048]    During a sixth cycle, labeled CYCLE #6, the following actions may occur:  
         [0049]    a) a high-ordered portion of registers A 0  and A 2  (containing outputs of the third FFT butterfly calculation) may be copied to registers A 0   hp  and A 2   hp,  respectively;  
         [0050]    b) multiplexer  30  may retrieve the contents of Zi 1  (A I  [3]), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R  [3]*W I  [3]) and the contents of register P 1  (B I  [3]*W R  [3]) and store the result (OUT 1  [3]) in register A 1 ; ALU  12  may subtract both the contents of register P 0  and the contents of register P 1  from the possibly concatenated output and store the result (OUT 3  [3]) in register A 3 ; and  
         [0051]    c) multiplier MUL 1  may multiply the fourth real sinusoidal data input (B R  [4]) with the fourth real coefficient (W R  [4]) and store the product in register P 0 , and multiplier MUL 2  may multiply the fourth imaginary sinusoidal data input (B I  [4]) with the fourth imaginary coefficient (W I  [4]) and store the product in register P 1 ; and  
         [0052]    d) the contents of registers Zr 0  (A R  [4]) and Zi 0  (A I  [4]) may be input to registers Zr 1  and Zi 1 , respectively.  
         [0053]    It should be noted that at the end of CYCLE #6, the four outputs of the third FFT butterfly calculation, (OUT 0  [3], OUT 1  [3], OUT 2  [3], OUT 3  [3]) have been calculated and are stored in registers A 0  (and A 0   hp ), A 1 , A 2  (and A 2   hp ) and A 3 , respectively.  
         [0054]    Subsequent Cycles  
         [0055]    The actions of CYCLES #7 and #9 are similar to those of CYCLES #1, #3, and #5, while the actions of CYCLE #8 are similar to those of CYCLES #2, #4 and #6. Subsequent cycles are performed until all the input data has been fully processed.  
         [0056]    Data Propagation  
         [0057]    Consequently, the data propagation in the structure shown in FIG. 1 may be considered as follows:  
         [0058]    a) Registers Zr 0  and Zi 0  receive the real and imaginary cosinusoidal data inputs for the FFT butterfly (A R  and A I , respectively) in each “first cycle” (CYCLE #1, CYCLE #3, etc.), and maintain their values in each “second cycle” (CYCLE #2, CYCLE #4, etc.).  
         [0059]    b) Registers Zr 1  and Zi 1  receive the contents of registers Zr 0  and Zi 0  respectively in each “second cycle” and maintain their values in each “first cycle”.  
         [0060]    c) In each “first cycle”, multiplier MUL 1  multiplies the real sinusoidal data input (B R ) with the imaginary coefficient (W I ) and stores the product in register P 0 , and multiplier MUL 2  multiplies the imaginary sinusoidal data input (B I ) with the real coefficient (W R ) and stores the product in register P 1 . In each “second cycle”, multiplier MUL 1  multiplies the real sinusoidal data input (B R ) with the real coefficient (W R ) and stores the product in register P 0 , and multiplier MUL 2  multiplies the imaginary sinusoidal data input (B I ) with the imaginary coefficient (W I ) and stores the product in register P 1 .  
         [0061]    d) In each “first cycle” multiplexer  30  may retrieve the contents of Zr 1  (A R ), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R *W R ) and subtract therefrom the contents of register P 1  (B I *W I ) and store the result (OUT 0 ) in register A 0 . ALU  12  may add the possibly concatenated output to the contents of register P 1  and subtract therefrom the contents of register P 0  and store the result (OUT 2 ) in register A 2 . Registers A 0  and A 2  maintain their values in each “second cycle”.  
         [0062]    e) In each “second cycle”, a high-ordered portion of registers A 0  and A 2  may be copied to registers A 0   hp  and A 2   hp,  respectively. Registers A 0   hp  and A 2   hp  maintain their values in each “first cycle”.  
         [0063]    f) In each “second cycle” multiplexer  30  may retrieve the contents of Zi 1  (A I ), the rounding constant C may optionally be concatenated to that value, and the possibly concatenated output of multiplexer  30  may be provided to ALUs  10  and  12 ; ALU  10  may add the possibly concatenated output to the contents of register P 0  (B R *W I ) and the contents of register P 1  (B I *W R ) and store the result (OUT 1 ) in register A 1 . ALU  12  may subtract both the contents of register P 0  and the contents of register P 1  from the possibly concatenated output and store the result (OUT 3 ) in register A 3 . Registers A 1  and A 3  maintain their values in each “first cycle”.  
         [0064]    Reading FFT Calculation Results to Memory  
         [0065]    As mentioned hereinabove, DSP  2  may include multiplexer  46  to selectably provide data from registers A 0   hp  or A 2   hp,  and multiplexer  48  to selectably provide data from registers A 1  or A 3 . Therefore, in any given cycle, data may be read from A 0   hp  and A 1 , or from A 0   hp  and A 3 , or from A 2   hp  and A 1 , or from A 2   hp  and A 3 . In the following examples, data is read from registers A 0   hp  and A 1  in one cycle and from registers A 2   hp  and A 3  in the next cycle.  
         [0066]    The reading of the FFT calculation results OUT 0  [k] and OUT 1  [k] during a “first cycle”](CYCLE #3, #5, #7, #9, etc.) is indicated in FIG. 2 by diagonal lines, where the values read are the values in registers A 0   hp  and A 1  at the end of the previous “first cycle” (CYCLE #2, #4, #6, #8, etc., respectively).  
         [0067]    The reading of the FFT calculation results OUT 2  [k] and OUT 3  [k] during a “second cycle” (CYCLE #4, #6, #8, etc.) is indicated in FIG. 2 by diagonal lines, where the values read are the values in registers A 2   hp  and A 3  at the end of the previous “first cycle” (CYCLE #3, #5, #7, etc., respectively).  
         [0068]    Consequently, it should be noted that all four FFT calculation results from a single butterfly may be read in two cycles.  
         [0069]    [0069]FIG. 3 is another tabular illustration of the contents of registers of the exemplary DSP of FIG. 1 over several cycles. FIG. 3 is identical to FIG. 2, except that FIG. 3 shows an alternate manner for reading the FFT calculation results.  
         [0070]    The reading of the FFT calculation results OUT 2  [k] and OUT 3  [k] during a “first cycle” (CYCLE #3, #5, #7, etc.) is indicated in FIG. 3 by diagonal lines, where the values read are the values in registers A 2   hp  and A 3  at the end of the previous “second cycle” (CYCLE #2, #4, #6, etc., respectively).  
         [0071]    The reading of the FFT calculation results OUT 0  [k] and OUT 1  [k] during a “second cycle” (CYCLE #4, #6, #8, etc.) is indicated in FIG. 3 by diagonal lines, where the values read are the values in registers A 0   hp  and A 1  at the end of the previous “first cycle” (CYCLE #3, #5, #7, etc., respectively).  
         [0072]    Consequently, it should be noted that all four FFT calculation results from a single butterfly may be read in two cycles.  
         [0073]    It should also be noted that other manners for reading the FFT calculation results in two or more cycles are also applicable to the embodiments of the present invention. For example, the manner shown in FIG. 2 may be used for some pairs of consecutive cycles and the manner shown in FIG. 3 may be used for other pairs of consecutive cycles.  
         [0074]    While certain features of the invention have been illustrated and described herein, many modifications, substitutions, changes, and equivalents will now occur to those of ordinary skill in the art. It is, therefore, to be understood that the appended claims are intended to cover all such modifications and changes as fall within the true spirit of the invention.