Patent Publication Number: US-6985919-B2

Title: Time-recursive lattice structure for IFFT in DMT application

Description:
FIELD OF THE INVENTION 
   The present invention relates to the Discrete Multitone (DMT) technology and, more particularly, to the Inverse Fast Fourier Transform (IFFT), the modulation kernel. By exploiting the symmetric/anti-symmetric properties of the input sequences, we add a new pre-processing scheme to further reduce the computational and the hardware complexity of the IFFT. 
   BACKGROUND OF THE INVENTION 
   Orthogonal transforms and transformation properties are extraordinarily useful in solving new technological problems. Such transforms permit analysis of most signals given some knowledge of its constituent parts. The Fourier transformation in particular has become a powerful tool in increasingly diverse fields including linear systems, communications systems, image processing applications, etc. 
   The discrete Fourier transformation (DFT) is the counterpart of the Fourier transformation in the discrete time domain. In general, the DFT may be defined as follows: 
                 X   ⁡     (   k   )       =       ∑     n   =   0       N   -   1       ⁢           ⁢       x   ⁡     (   n   )       ⁢     W   N   kn           ,           ⁢     k   =   0     ,   1   ,   …   ⁢           ,     N   -   1             (   1   )             
 
   and the inverse DFT (IDFT) is expressed as: 
                 x   ⁡     (   n   )       =         1   N     ⁢       ∑     k   =   0       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W   N     -   kn       ⁢           ⁢   n         =   0       ,   1   ,   …   ⁢           ,     N   -   1             (   2   )                 where   ⁢           ⁢     W   n       =     ⅇ       -   j     ⁢           ⁢   2   ⁢           ⁢     π   /   N                 (   3   )             
 
   In equations (1) and (2), N is the amount of the sample, x(n) is the sample value in the time domain, and X(k) is the sample value in the frequency domain. 
   Direct calculation of the DFT and the IDFT is complex. It requires N 2  multiplications and N(N−1) additions. Such computational may reduce signal processing speed, increased power consumption, and higher expense. One important tool in modern digital signal processing applications that helps to reduce that overhead is the Fast Fourier Transformation (FFT). By introducing the concept of divide-and-conquer, both the numbers of multiplication and addition are reduced to Nlog 2 N 
   In Discrete Multitone (DMT)-based ADSL system, a 512-point IFFT/FFT module is required to perform the modulation/demodulation kernel. At the transmitter side of the DMT system, to ensure the IFFT generates only real-valued outputs, the inputs of the IFFT have the constraint
 
 X ( k )= X *(2 N−k ) for  k= 0, 1 , . . . , N− 1  (4)
 
where N=256 and
 
 X ( k )≡ X   r ( k )+ j·X   i ( k )  (5)
 
are encoded complex symbols with X(0)=X(N)=0. Here, X r (k) and X i (k) indicate the real part and imaginary part of X(k) respectively. As defined 
                 x   ⁡     (   n   )       =         1     2   ⁢   N       ⁢       ∑     k   =   0         2   ⁢   N     -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   kn       ⁢           ⁢   for   ⁢           ⁢   n         =   0       ,   1   ,   …   ⁢           ,     N   -   1             (   6   )             
 
in equation (2), the IDFT of a 2N samples sequence is where, in accordance with the equation (3) 
                 W     2   ⁢   N       -   nk       ≡     ⅇ     j   ⁢           ⁢   2   ⁢   π   ⁢           ⁢     nk   /   2     ⁢   N         =       cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         +     j   ⁢           ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                   (   7   )             
 
   In accordance with U.S. Pat. No. 6,157,938, the equation (6) is decomposed by the first half and the second half by decomposing the index k, and using the facts that X(0)=X(N)=0. Therefore, the equation (6) becomes 
               x   ⁡     (   n   )       =       1     2   ⁢   N       ⁡     [         ∑     k   =   0       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   kn           +       ∑     k   =   N         2   ⁢   N     -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   nk             ]               (   8   )             
 
   Next, by applying the constraint of equation (4) and substituting equations (5) and (7) into (8), we can simplify equation (9) as follows: 
                       x   ⁡     (   n   )       ⁢       =       1     2   ⁢   N       ·     2   ⁡     [         ∑     k   =   0       N   -   1       ⁢           ⁢         X   r     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N           -       ∑     k   =   0       N   -   1       ⁢           ⁢         X   i     ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N             ]                         ⁢     =       1   N     ⁡     [         MDCT   r     ⁡     (   n   )       -       MDST   i     ⁡     (   n   )         ]                 ⁢     
     ⁢         for   ⁢           ⁢   n     =   0     ,   1   ,   …   ⁢           ,       2   ⁢   N     -   1               (   9   )               Where   ,                                 MDCT   r     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢           ⁢         X   r     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N             ⁢     
     ⁢         MDST   i     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢           ⁢         X   i     ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                     (   10   )             
 
   The equation (9) Fourier Transformation calculation includes two parts, the first term is Modified Discrete Cosine Transformation (MDCT) and the second term is Modified Discrete Sine Transformation (MDST). We use subscripts r and i to indicate that the operations are performed on the real and imaginary parts of input symbol X(k), respectively. Note that the MDCT r (n) and MDST i (n) involve only real-valued operators. Furthermore, from equation (10) it can be shown that 
                   MDCT   r     ⁡     (   n   )       =       MDCT   r     ⁡     (       2   ⁢   N     -   n     )         ⁢     
     ⁢           MDST   i     ⁡     (   n   )       =         -       MDST   i     ⁡     (       2   ⁢   N     -   n     )         ⁢           ⁢   for   ⁢           ⁢   n     =   0       ,   1   ,   …   ⁢           ,       2   ⁢   N     -   1               (   11   )             
 
   Consequently, calculation of equation (9) can be focused on the calculations of MDCT r (n) function and MDST i (n) function for n=0, 1, . . . , N−1. Then the calculations of the MDCT r (n) function and the MDST i (n) function for n=N+1, . . . , 2N−1 are expanded based upon equation (11). In this manner, this simple relationship can save an additional 50% hardware/software complexity. 
   In U.S. Pat. No. 6,157,938, a time-recursive FFT architecture is provided. The modulation kernels of equation (9) are mapped to the VLSI architectures based on time-recursive lattice structure as shown in  FIG. 1 . As the shown of the  FIG. 1 , the input data are separated into two phases, the real parts X r (k) and the imaginary parts X i (k) where k=0, 1, . . . , N−1. The real parts X r (k), first phase, are first fed to the module. After N iterations, the MDCT r (n) is obtained at upper output. The imaginary parts X i (k), second phase, are then fed to the lattice. Similarly, after N iterations, the MDST i (n) is obtained at lower output. Then, the MDCT r (n) and the MDST i (n) are combined together to obtain the IFFT answer of a 2N samples sequence by the accumulators in post-processing circuit. The overall architecture disclosed by U.S. Pat. No. 6,157,938 is illustrated in the  FIG. 2 . 
   However, in  FIG. 2 , the input data are decomposed into real part X r (k) and imaginary part X i (k) and they are fed into the modules in two different phases. The real part X r (k) and imaginary part X i (k) respectively require N iterations to get the MDCT r (n) and the MDST i (n). Namely, 2N iterations are required to obtain the final results x(n), which results in extra N-cycle latency in practical implementations. Thus, there is an ongoing need to reduce the number of IFFT computations, and in particular the number of complex multiplications, that must be performed in order to more efficiently compute the IFFT. 
   SUMMARY OF THE INVENTION 
   The present invention meets this need and significantly reduces the number of complex computations that must be performed in computing the IFFT of real value sequences. The computational reduction increases signal processing speed and decreases power consumption, both of which are highly desirable in virtually every IFFT application. The present invention achieves these goals by taking advantage of various symmetries and regularities of processed data sequences. 
   The main purpose of the present invention is to provide a novel pre-processing scheme to modify the IFFT structure. By exploiting the symmetric and anti-symmetric properties of the input sequences, it can eliminate the redundant output from the lattice modules, and the required iteration number can be halved. The present invention may reduce the computational complexity and save the total hardware complexity. 
   In accordance with the present invention, an input data sequence is modified by exploiting the symmetric and anti-symmetric properties in order to eliminate the redundant output from the lattice modules. Then, an IFFT is performed on the modified input data sequence to generate a transformed sequence. 
   To achieve the foregoing objects, reducing the total iteration number of the IFFT structure, first using the symmetric and anti-symmetric properties to modify the real and imaginary part of the input signal and then mixing them together by an adder and feeding the results into the lattice module. Through the symmetric and anti-symmetric properties, the redundant terms may be eliminated. Because the real and imaginary part are mixed together for feeding into the lattice modules, only N iterations are required to obtain the final result, which reduces power consumption. On the other hand, the expanding circuit of the present invention does not include the multiplexers; therefore, it may reduce the complexity of the circuit design. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The objects, features and advantages of this invention will be more clearly understood from the following detailed description taken in conjunction with the accompanying drawings in which: 
       FIG. 1  is a detailed circuit diagram showing a detailed circuit diagram of the lattice modules for generation of the MDCT r (n) and the MDST i (n) of the prior art; 
       FIG. 2  is a diagram showing the overall structure of an IFFT module of the prior art; 
       FIG. 3  shows a cos(2πnk/2N) diagram when n is odd in accordance with the present invention and the transverse axle represents the k value; 
       FIG. 4  shows a cos(2πnk/2N) diagram when n is even in accordance with the present invention and the transverse axle represents the k value; 
       FIG. 5  shows a sin(2πnk/2N) diagram when n is odd in accordance with the present invention and the transverse axle represents the k value; 
       FIG. 6  shows a sin(2πnk/2N) diagram when n is even in accordance with the present invention and the transverse axle represents the k value; 
       FIG. 7  is a detailed circuit diagram showing a detailed circuit diagram of the lattice modules for generation of the 2MDCT r (n) and the 2MDST i (n) in accordance with the present invention; 
       FIG. 8  is a diagram showing the overall structure of an IFFT module in accordance with the present invention; 
       FIG. 9  is the SQNR performances of the prior art structure shown in  FIG. 1 ; 
       FIG. 10  is the SQNR performances of the present invention structure shown in  FIG. 7 ; and 
       FIG. 11  is the internal wordlength of the lattice module. 
   

   DESCRIPTION OF THE PREFERRED EMBODIMENT 
   Without limiting the spirit and scope of the present invention, the method proposed in the present invention is illustrated with one preferred embodiment to provide a novel pre-processing scheme to modify the input sequences. By exploiting the symmetric and anti-symmetric properties of the input sequences, it can eliminate the redundant output from the lattice modules, and the required iteration number can be halved. Skilled artisans, upon acknowledging the embodiments, can apply the method according to the present invention to time-recursive IFFT structure to reduce the operation frequency. Realizing the present invention method in a circuit may reduce the power consumption and the complexity of the circuit. The application of the present invention is not limited by the following embodiment. 
   A preferred embodiment of the present invention provides efficient or simplified IFFT/FFT computations by taking advantage of Hermitian symmetry. In the formal definition of the IFFT/FFT, both x(n) and X(k) are assumed to be complex. If X(k) is an N-point Hermitian symmetric series, the Fourier transformation of X(k) is a real sequence, x(n). Regarding subscripts, the index for frequency sequences is k, sequences in the time domain are indexed by n. 
   In accordance with the preferred embodiment of the present invention, an assumption is made that a 512-point IFFT/FFT module is required to perform the modulation/demodulation kernel. If X(k) is a 2N (N=256) point Hermitian symmetric series, the inputs of the IFFT have the constraint
 
 X ( k )= X *(2 N−k ) for  k= 0, 1 , . . . , N− 1
 
where N=256 and
 
 X ( k )≡ X   r ( k )+ j·X   i ( k )
 
wherein X(0)=X(N)=0. Here, X r (k) and X i (k) indicate the real part and imaginary part of X(k) respectively. As defined in equation (2), the IDFT of a 2N samples sequence is 
           x   ⁡     (   n   )       =         1     2   ⁢   N       ⁢       ∑     k   =   0         2   ⁢   N     -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   kn       ⁢           ⁢   for   ⁢           ⁢   n         =   0       ,   1   ,   …   ⁢           ,       2   ⁢   N     -   1         
     wherein     
           W     2   ⁢   N       -   nk       ≡     ⅇ     j   ⁢           ⁢   2   ⁢   π   ⁢           ⁢     nk   /   2     ⁢   N         =       cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         +     j   ⁢           ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N               
 
By decomposing k into the first half and the second half and using the facts that X(0)=X(N)=0, 
                     x   ⁡     (   n   )       ⁢       =       1     2   ⁢   N       ⁡     [         ∑     k   =   1       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   nk           +       ∑     k   =   1         2   ⁢   N     -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   nk             ]                       ⁢     =       1     2   ⁢   N       ⁡     [         ∑     k   =   1       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   nk           +       ∑     k   =   1       N   -   1       ⁢           ⁢       X   ⁡     (       2   ⁢   N     -   k     )       ⁢     W     2   ⁢   N       -     n   ⁡     (       2   ⁢   N     -   k     )                 ]                         Wherein                       W     2   ⁢   N       -     n   ⁡     (       2   ⁢   N     -   k     )           ⁢       ≡       W     2   ⁢   N       -     n   ⁡     (     2   ⁢   N     )           ·     W     2   ⁢   N     nk       ≡       ⅇ     j   ⁢           ⁢   2   ⁢   π   ⁢           ⁢     n2N   /   2     ⁢   N       ·     W     2   ⁢   N     nk                       ⁢     =     1   ·     W     2   ⁢   N     nk                         ⁢     =     W     2   ⁢   N     nk               ⁢     
     ⁢           ⁢       and   ⁢           ⁢     X   (       2   ⁢   N     -   k     )       =     X   *     (   k   )                     Therefore   ,                 x   ⁡     (   n   )       ⁢       =       1     2   ⁢   N       ⁡     [         ∑     k   =   1       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   kn           +       ∑     k   =   1       N   -   1       ⁢           ⁢     X   *     (   k   )     ⁢     W     2   ⁢   N     nk           ]                   Accordingly   ,                       X   ⁡     (   k   )       ≡         X   r     ⁡     (   k   )       +     j   ·       X   i     ⁡     (   k   )                         X   *     (   k   )       ≡         X   r     ⁡     (   k   )       -     j   ·       X   i     ⁡     (   k   )                             Therefore   ,                       x   ⁡     (   n   )       ⁢       =       1     2   ⁢   N       ⁡     [         ∑     k   =   1       N   -   1       ⁢           ⁢       X   ⁡     (   k   )       ⁢     W     2   ⁢   N       -   kn           +       ∑     k   =   1       N   -   1       ⁢           ⁢     X   *     (   k   )     ⁢     W     2   ⁢   N     nk           ]                       ⁢     =       1   N     ⁢       ∑     k   =   1       N   -   1       ⁢     [           ⁢           X   r     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         -       ∑     k   =   1       N   -   1       ⁢           ⁢         X   i     ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N             ]                           ⁢       =         1   N     ⁢       ∑     k   =   1       N   -   1       ⁢       [         MDCT   r     ⁡     (   n   )       -       MDST   i     ⁡     (   n   )         ]     ⁢           ⁢   for   ⁢           ⁢   n         =   0       ,   1   ,   …   ⁢           ,       2   ⁢   N     -   1                       wherein                       MDCT   r     ⁡     (   n   )       =       ∑     k   =   1       N   -   1       ⁢           ⁢         X   r     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                           MDST   i     ⁡     (   n   )       =       ∑     k   =   1       N   -   1       ⁢           ⁢         X   i     ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                           
 
   From the above equation, it can be determined that inverse Fast Fourier Transformation calculations include two-part operations of real numbers, where the first part is a discrete cosine transform-like operation with X r (k) (wherein k=0, 1, . . . , N−1) as input, whereas the second part is a discrete sine transform-like operation with X i (k) (wherein k=0, 1, . . . , N−1) as input. The subscripts r and i indicate that the operations are performed on the real and imaginary parts of input symbol X(k), respectively. For simplicity, the first part of above equation is defined as a modified discrete cosine transformation (MDCT r ) function and the second part as a modified sine transformation (MDST i ) function. 
   However, in accordance with the prior art, the inverse Fast Fourier Transformation calculations may be determined by calculating the MDCT r (n) function and MDST i (n) function where n=0, 1, . . . , N−1. Namely, 2N iterations are required to obtain the final inverse Fast Fourier Transformation calculations results, which result in extra N-cycle latency in practical implementations. 
   Therefore, to reduce the total iteration number of the inverse Fast Fourier Transformation calculations, the X r (k) and X i (k) are mixed together to be fed into the lattice module. Since the lattice module is a linear system, based on superposition theory, the superposition input obtains the superposition outputs after N iterations. Because the imaginary parts are input together, the upper output of the lattice module includes the desired value MDCT r (n) and the additional value MDCT i (n). Similarly, because the real parts are input together, the lower output of the lattice module includes the desired value MDST i (n) and the additional value named MDST r (n). 
   In other words, the upper output is as follows:
 
the upper output= MDCT   r ( n )+ MDCT   i ( n )
 
And the lower output is as follows:
 
the lowwer output= MDST   r ( n )+ MDST   i ( n )
 
   Note that the terms MDCT i (n), and MDST r (n) are not the desired results. They are mixed with the desired part. 
   The considered reduction in the number of the iterations is achieved by deleting the undesired part, MDCT i (n) and MDST r (n). First, in accordance with the relationship is shown in the follows. 
                 MDCT   r     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢           ⁢         X   r     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                           MDST   i     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢           ⁢         X   i     ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                     
 
   The sequence cos(2πnk/2N and the sequence sin(2πnk/2N) exhibits symmetric and anti-symmetric characteristics in accordance with the “n” value, which is odd or even. 
   When n is odd, assuming N=64, n=1
         cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         =     cos   ⁢       π   ·   1   ·   k     64           
 
     FIG. 3  shows the diagram of the above equation, wherein the transverse axle represents the k value.  FIG. 3  shows an anti-symmetrical diagram relative to the k=32 point. Namely, the cos(2πnκ/2N) will be an anti-symmetrical sequence when n is odd. 
   On the other hand, when n is even, assuming N=64, n=2
         cos   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         =     cos   ⁢       π   ·   2   ·   k     64           
 
     FIG. 4  shows the diagram of the above equation, wherein the transverse axle represents the k value.  FIG. 4  shows a symmetrical diagram relative to the k=32 point. Namely, the cos(2πnk/2N) will be a symmetrical sequence when n is even. 
   Consider a symmetric sequence; Y s (k), the product Y s (k) with the anti-symmetrical sequence cos(2πnk/2N) will form a new anti-symmetric sequence, Y s (k)cos(2πnk/2N). The summation of the product will be zero when n is odd. 
         ∑         Y   s     ⁡     (   K   )       ·     cos   ⁡     (       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N       )           =       0   ⁢           ⁢   n     =   odd         
 
   On the other hand, consider an anti-symmetric sequence, Y a (k); the product Y a (k) with the symmetries sequence cos(2πnk/2N) will form a new anti-symmetric sequence, Y a (k)cos(2πnk/2N). The summation of the product will be zero when n is even. 
         ∑         Y   a     ⁡     (   K   )       ·     cos   ⁡     (       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N       )           =       0   ⁢           ⁢   n     =   even         
 
   Similarly, the sequence sin(2πnk/2N) also exhibits the symmetric and anti-symmetric characteristic in accordance with the “n” value, which is odd or even. 
   When n is odd, assuming N=64, n=1
         sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         =     sin   ⁢       π   ·   1   ·   k     64           
 
     FIG. 5  shows the diagram of the above equation, wherein the transverse axle representing the k value.  FIG. 5  shows a symmetrical diagram relative to the k=32 point. Namely, the sin(2πnk/2N) will be a symmetrical sequence when n is odd. 
   On the other hand, when n is even, assuming N=64, n=2
         sin   ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N         =     sin   ⁢       π   ·   2   ·   k     64           
 
     FIG. 6  shows the diagram of the above equation, wherein the transverse axle representing the k value.  FIG. 6  shows an anti-symmetric diagram relative to the k=32 point. Namely, the sin(2πnk/2N) will be an anti-symmetric sequence when n is even. 
   Consider an anti-symmetric sequence, Y a (k), the product Y a (k) with the symmetrical sequence sin(2πnk/2N) forms a new anti-symmetric sequence, Y a (k)sin(2πnk/2N). The summation of the product is zero when n is odd. 
         ∑           Y   a     ⁡     (   k   )       ·   sin     ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N           =       0   ⁢           ⁢   n     =   odd         
 
   On the other hand, consider a symmetric sequence; Y s (k), the product Y s (k) with the anti-symmetrical sequence sin(2πnκ/2N) forms a new anti-symmetric sequence, Y s (k)sin(2πnk/2N). The summation of the product is zero when n is even. 
         ∑           Y   s     ⁡     (   k   )       ·   sin     ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N           =       0   ⁢           ⁢   n     =   even         
 
   Now, consider the upper output, namely, if the X r (k) and X i (k) are mixed together to be fed into the lattice module, the upper output is as follows: 
         the   ⁢           ⁢   upper   ⁢           ⁢   output     =         MDCT   r     ⁡     (   n   )       +       MDCT   i     ⁡     (   n   )             
     and     
                 MDCT   r     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X   r     ⁡     (   k   )       ⁢           ⁢   cos   ⁢           ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                           MDCT   i     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X   i     ⁡     (   k   )       ⁢           ⁢   cos   ⁢           ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                     
 
   the lower output is as follows: 
         the   ⁢           ⁢   lower   ⁢           ⁢   output     =       MD   ⁢           ⁢   S   ⁢           ⁢       T   r     ⁡     (   n   )         +     MD   ⁢           ⁢       ST   i     ⁡     (   n   )               
     and     
                 MDST   r     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X   r     ⁡     (   k   )       ⁢           ⁢   sin   ⁢           ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                           MDST   i     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X   i     ⁡     (   k   )       ⁢           ⁢   sin   ⁢           ⁢       2   ⁢   π   ⁢           ⁢   nk       2   ⁢   N                     
 
   The MDCT r (n) and MDST i (n) are the desired parts and the MDCT i (n) and MDST r (n) should be deleted. Therefore, by changing the X i (k) to an even function or odd function, the MDCT i (n) may be deleted. 
   Accordingly, if the input sequence X(k), k=0, 1, . . . N−1, is a random sequence and X r (k) and X i (k) indicate the real part and imaginary parts of X(k). Since any sequence can be decomposed into a symmetric part and anti-symmetric part, we decompose the imaginary part X i (k) according to an identified modification pattern into the following equations:
 
symmetric signal:  X   is ( k )= X   i ( k )+ X   i ( N−k )  (i)
 
anti-symmetric signal:  X   ia ( k )= X   i ( k )− X   i ( N−k )  (ii)
 
   Therefore, for eliminating the redundant term, MDCT i (n), from the upper output, when n is odd, the cos(2πnk/2N) will be an anti-symmetrical sequence. Therefore, the symmetries sequence X is (k) is sent into the module to make the MDCT i (n) zero. On the other hand, when n is even, the cos(2πnk/2N) will be a symmetries sequence. Therefore, the anti-symmetrical sequence X ia (k) is sent into the module to make the MDCT i (n) be zero. However, because the input signal X i (k) is changed, the lower output MDST i (n) will be as follows: 
               ⁢     When   ⁢           ⁢   n   ⁢           ⁢   is   ⁢           ⁢   odd         
                 ∑     k   =   0       N   -   1       ⁢           ⁢         X     i   ⁢           ⁢   s       ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           =       ∑     k   =   0       N   -   1       ⁢         [           ⁢         X     i   ⁢               ⁡     (   k   )       +       X   i     ⁡     (     N   -   k     )         ]     ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                       =         ∑     k   =   0       N   -   1       ⁢           X     i   ⁢               ⁡     (   k   )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   i     ⁡     (     N   -   k     )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                         =         ∑     k   =   0       N   -   1       ⁢           X     i   ⁢               ⁡     (   k   )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   i     ⁡     (     N   -   k     )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢     n   ⁡     (     N   -   k     )           2   ⁢           ⁢   N                         =     2   ⁢           ⁢       MDST   i     ⁡     (   n   )                   
               ⁢     When   ⁢           ⁢   n   ⁢           ⁢   is   ⁢           ⁢   even         
                 ∑     k   =   0       N   -   1       ⁢           ⁢         X     i   ⁢           ⁢   a       ⁡     (   k   )       ⁢   sin   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           =       ∑     k   =   0       N   -   1       ⁢         [           ⁢         X     i   ⁢               ⁡     (   k   )       -       X   i     ⁡     (     N   -   k     )         ]     ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                       =         ∑     k   =   0       N   -   1       ⁢           X     i   ⁢               ⁡     (   k   )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           -       ∑     k   =   0       N   -   1       ⁢           X   i     ⁡     (     N   -   k     )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                         =         ∑     k   =   0       N   -   1       ⁢           X     i   ⁢               ⁡     (   k   )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   i     ⁡     (     N   -   k     )       ·   sin     ⁢       2   ⁢           ⁢   π   ⁢           ⁢     n   ⁡     (     N   -   k     )           2   ⁢           ⁢   N                         =     2   ⁢           ⁢       MDST   i     ⁡     (   n   )                   
 
   The desired result, MDST i (n), is kept. At the same time, the redundant term MDCT i (n) may also be eliminated. Therefore, in accordance with the foregoing description, the input imaginary sequence, X i ′(k), is modified according to an identified modification pattern as follows:
 
 X   i ′( k )= X   i ( k )+(−1) n+1   ·X   i ( N−k )
 
   On the other hand, considering the lower output. 
         the   ⁢           ⁢   lower   ⁢           ⁢   output     =         MDST   r     ⁡     (   n   )       +       MDST   i     ⁡     (   n   )             
     And     
           MDST   r     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X     r   ⁢               ⁡     (   k   )       ⁢           ⁢   sin   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N               
           MDST   i     ⁡     (   n   )       =       ∑     k   =   0       N   -   1       ⁢         X     i   ⁢               ⁡     (   k   )       ⁢           ⁢   sin   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N               
 
   The MDST i (n) are the desired parts and the MDST r (n) should be deleted. Therefore, by changing the X r (k) to an even function or an odd function, the MDST r (n) may be deleted. 
   Similarly, since any sequence can be decomposed into a symmetric part and an anti-symmetric part, we decompose the real X r (k) according to a modification identified pattern into the following:
 
symmetric signal:  X   rs ( k )= X   r ( k )+ X   r ( N−k )  (i)
 
anti-symmetric signal:  X   ra ( k )= X   r ( k )− X   r ( N−k )  (ii)
 
   Therefore, for eliminating the redundant term, MDST r (n), from the lower output, when n is odd, the sin(2πnk/2N) will be a symmetrical sequence. Therefore, the anti-symmetrical sequence X ra (k) is sent into the module to make the MDST r (n) zero. On the other hand, when n is even, the sin(2πnk/2N) will be an anti-symmetrical sequence. Therefore, the symmetrical sequence X rs (k) is sent into the module to make the MDST r (n) zero. However, because the input signal X r (k) is changed, the upper output MDCT r (n) is as follows: 
               ⁢     When   ⁢           ⁢   n   ⁢           ⁢   is   ⁢           ⁢   odd         
                 ∑     k   =   0       N   -   1       ⁢           ⁢         X   ra     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           =       ∑     k   =   0       N   -   1       ⁢         [           ⁢         X   r     ⁡     (   k   )       -       X   r     ⁡     (     N   -   k     )         ]     ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                       =         ∑     k   =   0       N   -   1       ⁢           X     r   ⁢               ⁡     (   k   )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           -       ∑     k   =   0       N   -   1       ⁢           X   r     ⁡     (     N   -   k     )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                         =         ∑     k   =   0       N   -   1       ⁢           X     r   ⁢               ⁡     (   k   )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   r     ⁡     (     N   -   k     )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢     n   ⁡     (     N   -   k     )           2   ⁢           ⁢   N                         =     2   ⁢           ⁢       MDCT   r     ⁡     (   n   )                   
               ⁢     When   ⁢           ⁢   n   ⁢           ⁢   is   ⁢           ⁢   even         
                 ∑     k   =   0       N   -   1       ⁢           ⁢         X   rs     ⁡     (   k   )       ⁢   cos   ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           =       ∑     k   =   0       N   -   1       ⁢         [           ⁢         X     r   ⁢               ⁡     (   k   )       +       X   r     ⁡     (     N   -   k     )         ]     ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                       =         ∑     k   =   0       N   -   1       ⁢           X     r   ⁢               ⁡     (   k   )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   r     ⁡     (     N   -   k     )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N                         =         ∑     k   =   0       N   -   1       ⁢           X     r   ⁢               ⁡     (   k   )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢   nk       2   ⁢           ⁢   N           +       ∑     k   =   0       N   -   1       ⁢           X   r     ⁡     (     N   -   k     )       ·   cos     ⁢       2   ⁢           ⁢   π   ⁢           ⁢     n   ⁡     (     N   -   k     )           2   ⁢           ⁢   N                         =     2   ⁢           ⁢       MDCT   r     ⁡     (   n   )                   
 
   The desired result, MDCT r (n) is kept. At the same time, the redundant term MDST r (n) may also be eliminated. Therefore, in accordance with the foregoing description, the input real sequence X r ′(k), is modified according to the identified modification pattern as follows:
 
 X   r ′( k )= X   r ( k )+(−1) n   ·X   r ( N−k )
 
   As a result, the real sequence with the imaginary sequence may be added together to feed into the lattice module simultaneously to obtain the correct result. In summary, the generalized input sequence X 
                 X   ′     ⁡     (   k   )       =       ⁢         X   r   ′     ⁡     (   k   )       +       X   i   ′     ⁡     (   k   )                     =       ⁢       [         X   r     ⁡     (   k   )       +         (     -   1     )     n     ·       X   r     ⁡     (     N   -   k     )           ]     +     [         X   i     ⁡     (   k   )       +           (     -   1     )       n   +   1       ·     X   i       ⁢     (     N   -   k     )         ]                 
 
(k), can be expressed as follows:
 
   The symmetric/anti-symmetric sequences of input data can be easily generated by a pre-processing module, which consists of some buffers and adders as shown in  FIG. 7 . In general, this pre-processing module may be moved to previous functional block of DMT system, i.e., the constellation encoder. Usually, the encoder is implemented by a DSP processor that is very efficient for data movement and addition operations. Hence, we can implement the pre-processing module in DSP, which helps to further reduce the hardware complexity. 
   The overall inverse Fast Fourier Transformation lattice structure is drawn in  FIG. 8  and should be compared with  FIG. 2 , proposed by U.S. Pat. No. 6,157,938, where the N−1 multiplexers and 2N−2 accumulators are in an expanding circuit and the multiplexers MUX 1  to MUX N−1  are for receiving the output data from lattice module IM 1  to IM N−1 , respectively. For example, the multiplexer MUX 1  receives the output data MDCT( 1 ) and MDST( 1 ) of the lattice module IM 1 . Similarly, the multiplexer MUX N−1  receives the output data MDCT(N−1) and MDST(N−1) of the lattice module IM N−1 . 
   However, in accordance with the present invention, it is not necessary to use the multiplexers in the expanding circuit because the present invention provides a modified input sequence that can eliminate the redundant output. Reference is again made to  FIG. 8 , where the expanding circuit only includes 2N−2 adders. The adders A 1  to A 2N−2  are for receiving the output data from lattice module IM 1  to IM N−1 , respectively. For example, the adder A 1  receives the output data 2MDCT( 1 ) and 2MDST( 1 ) of the lattice module IM 1 . Similarly, the adder A 2N−1  receives the output data 2MDCT r (N−1) and 2MDST i (N−1) of the lattice module IM N−1 . In accordance the following equation: 
         x   ⁡     (   1   )       =       1     2   ⁢   N       ⁡     [       2   ⁢           ⁢       MDCT   r     ⁡     (   1   )         -     2   ⁢           ⁢       MDST   i     ⁡     (   1   )           ]           
 
   Therefore, the output 2MDST i (1) is multiplied by (−1). Furthermore, since the output of the lattice module further includes a multiplication of 2, the data output from the expanding circuit is shifted right by log 2 (2N) bits by the corresponding hard-wiring right shifters for outputting data x(0), x(1), x(2), . . . , x(2N−1). 
   On the other hand, the MDCT function and MDST function demonstrate the following characteristic:
 
 MDCT ( k )= MDCT (2 N−k )
 
 MDST ( k )=− MDST (2 N−k )
 
   Therefore, the expanding circuit may extend the calculations of MDCT(k) and MDST(k) in k=N, N+1, . . . , 2N−1. The following is an example. 
               x   ⁡     (       2   ⁢   N     -   1     )       =       ⁢       MDCT   ⁡     (       2   ⁢   N     -   1     )       -     MDST   ⁡     (       2   ⁢   N     -   1     )                     =       ⁢       MDCT   ⁡     (   1   )       +     MDST   ⁡     (   1   )                   
 
   The two outputs of lattice module IM 1  may also get the x(2N−1) result. In other words, the adder A 2  receives the output data 2MDCT( 1 ) and 2MDST( 1 ) of the lattice module IM 1  and connects to the corresponding hard-wiring right shifter to get the output x(2N−1). 
   Moreover, in accordance with the following equation:
 
 x (0)= MDCT (0)− MDST (0)= MDCT (0)
 
 x ( N )= MDCT ( N )− MDST ( N )=(−1) n   MDCT ( N )
 
   Therefore, x(0) and x(N) may be outputted respectively from the two terminals of the special module SC1. 
   In the following, the present invention architecture of Fast Fourier Transformation is compared with the prior art of U.S. Pat. No. 6,157,938. The hardware complexity of hardware is shown in Table 1, where the halved iteration number is the major improvement in this present invention. Under the same symbol rate, the power consumption of the IFFT can be reduced due to the halved processing speed. Besides, the numbers of multiplexer and register are also reduced after the modification. 
   
     
       
         
             
             
             
           
             
                 
               TABLE 1 
             
             
                 
                 
             
             
                 
               Original structure 
               Proposed 
             
             
                 
               (US 6157938) 
               structure 
             
             
                 
                 
             
           
          
             
                 
             
          
         
         
             
             
             
          
             
               Multiplier 
               4N-4 
               4N-4 
             
             
               Adder 
               5N-3 
               5N-3 
             
             
               Register 
               4N-4 
               2N-2 
             
             
               Others 
               N-1 MUXs 
               — 
             
             
               Iteration 
               2N 
               N 
             
             
                 
             
          
         
       
     
   
   A 2N-point Fast Fourier Transformation realized with a prior art structure includes one special module (SC1) and the (N−1) lattice modules IM 1  to IM N−1 . The special module SC1 includes two adders and each of the (N−1) lattice modules includes four real multipliers, three real adders and two registers. Therefore, the total (3N−1) adders, (4N−4) multipliers and (2N−2) registers are required for the (N−1) lattice modules and SC1. Besides, the expanding circuit includes additional 2(N−1) adders, (N−1) multiplexers and 2(N−1) registers. That is, the original structure requires 4(N−1) real multipliers and [5(N−1)+2] real adders in total. 
   On the other hand, the structure of the present invention also includes one special module (SC1) and the (N−1) lattice modules IM 1  to IM N−1 . The main different between the prior art and the present invention is the expanding circuit. It only requires (2N−2) adders. The multiplexers and the registers are not necessary. Therefore, the present invention may reduce the hardware complexity of the expanding circuit. More importantly, the iteration may also be reduced from 2N to N. 
     FIG. 9  and  FIG. 10  are the SQNR performances of the prior art structure (U.S. Pat. No. 6,157,938) and the present invention structure, respectively. The internal wordlength was chosen as shown in  FIG. 11 . Two 16-bit adders and four 16-bit multipliers were adopted in the simulation. From the two drawings,  FIG. 9  and  FIG. 10 , under the same wordlength assignment, the present invention architecture performs as well as the prior art structure. Most channels result in a SQNR more than 40 dB, and the overall averaged SQNR value is 51.25 dB, which is almost identical to the value of the prior art structure (51.07 dB). 
   By utilizing the symmetric/anti-symmetric property of the data sequence, a more effective lattice structure for an IFFT module in a DMT transmitter is proposed. The iteration number has been halved such that the lattice module can work at a half clock rate. Hence, the power consumption can be reduced. On the other hand, the hardware in the expanding circuit has also been reduced. The sampling decimator is saved and routing becomes even simpler, too. These features make the proposed scheme a good candidate for cost-efficient IFFT implementation in the DMT-based ADSL system. 
   Although the present invention has been described in its preferred embodiment, it is not intended to limit the invention to the precise embodiment disclosed herein. Those who are skilled in this technology can still make various alterations and modifications without departing from the scope and spirit of this invention. Therefore, the scope of the present invention shall be defined and protected by the following claims and their equivalents.