# Patent

## Title
Fast modified discrete cosine transform method

## Abstract

A technique for computationally efficient evaluation of the Modified Discrete Cosine Transform (MDCT) using the Fast Fourier Transform (FFT) method is presented in which the input of the FFT block consists of a sequence of N complex numbers, and this complex data is evaluated using an N/2-Point FFT only, thereby descreasing computation burden almost by two.

## Background
FIELD OF THE INVENTION
This invention is applicable in the field of multi-channel audio coders which use a modified discrete cosine transform as a step in the compression of audio signals.
BACKGROUND OF THE INVENTION
Recent years witnessed an unprecedented advancement in audio coding technology. This has led to high compression ratios while keeping audible degradation in the compressed signal to a minimum. These coders are intended for a variety of applications, including 5.1 channel film soundtracks, HDTV, laser discs and multimedia. Description of a compression method used in such coders can be found in the ATSC Standard, “Digital Audio Compression (AC-3) Standard”, Document A/52, 20 Dec. 1995.
In the basic approach, at the encoder the time domain signal is sectioned into frames, each frame comprising of a number of blocks. The time domain signal in each block is first converted to the frequency domain using a bank of filters. The frequency domain coefficients, thus generated, are next converted to floating point representation. In floating point syntax, each coefficient is represented as a mantissa and an exponent. The bulk of the compressed bitstream transmitted to the decoder comprises these exponents and mantissas.
The coders are expected to operated in real time. Therefore it is important that the processing at both the encoders and decoders be highly optimised. The ATSC standard outlines a method for conversion of the inverse cosine transform to Fast Fourier Transform to obtain remarkable speed gain.
Frequency transformation presents one of the greatest computation requirements in any transform coder. Therefore, an efficient implementation of this phase can decrease the computation requirement of the system significantly and make real time operation of encoder an easily attainable possibility.
In some encoders such as the AC-3, the frequency domain transformation of signals is performed by the modified discrete cosine transform (MDCT). If directly implemented, the MDCT requires O(N2) additions and multiplications.
However it is possible to reduce the number of required operations significantly if one is able to express the MDCT equation into a form that is amenable to the use of the well known Fast Fourier Transform (FFT) method of J. W. Cooley and J. W. Tukey (1960).
To compute the MDCT of a sequence of N real data, conventional methods use a system comprising of a pre-processing block, an N-point FFT block and finally a post-processing block.
SUMMARY OF THE INVENTION
In accordance with the disclosed embodiments of the invention, there is provided a method of evaluating a modified discrete cosine transform (MDCT) of an input sequence of complex data using a Fast Fourier Transform (FFT), wherein the FFT is a N/2-Point FFT.
Preferably, the MDCT is of the form:



  
    
      X
      k
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          x
          ⁡
          
            [
            n
            ]
          
        
        *
        
          cos
          ⁡
          
            (
            
              
                2
                ⁢
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      n
                    
                    +
                    1
                  
                  )
                
                *
                
                  (
                  
                    
                      2
                      ⁢
                      k
                    
                    +
                    1
                  
                  )
                
                ⁢
                
                  /
                
                ⁢
                4
                ⁢
                N
              
              +
              
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      k
                    
                    +
                    1
                  
                  )
                
                ⁢
                
                  /
                
                ⁢
                4
              
            
            )
          
        
      
    
  




  
    k
    =
    
      0
      ⁢
      
        ...
        ⁡
        
          (
          
            
              N
              ⁢
              
                /
              
              ⁢
              2
            
            -
            1
          
          )
        
      
    
  



where x[n] represents the input sequence and N is the number of data samples in the sequence.

Preferably, a transform coefficient sequence of the MDCT is derived using the N/2-Point FFT of a complex function (z[n], where




  
    G
    k
  
  =
  
    
      
        1
        2
      
      ⁡
      
        [
        
          
            Z
            k
          
          +
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
            n
          
        
        ]
      
    
    +
    
      
        
          e
          
            j
            ⁢
            
              
                n
                ⁡
                
                  (
                  
                    
                      2
                      ⁢
                      k
                    
                    +
                    1
                  
                  )
                
              
              N
            
          
        
        
          2
          ⁢
          j
        
      
      ⁡
      
        [
        
          
            Z
            k
          
          -
          
            Z
            
              
                N
                1
              
              -
              k
              -
              1
            
            n
          
        
        ]
      
    
  




Preferably, a transform Zk and the complex conjugate of the transform ZN/2-k-1 are derived from z[n] for the expression




  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        (
        
          
            x
            ⁡
            
              [
              
                2
                ⁢
                n
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  2
                  ⁢
                  n
                
                +
                1
              
              ]
            
          
        
        )
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              π
              ⁢
              
                
              
              ⁢
              n
            
            N
          
        
      
    
  
  ,
  
    0
    ≤
    n
    ≤
    
      (
      
        
          N
          ⁢
          
            /
          
          ⁢
          2
        
        -
        1
      
      )
    
  




where Gk is a transform coefficient sequence which allows the MDCT to be evaluated, in that




  
    G
    k
  
  =
  
    
      
        g
        
          k
          ,
          r
        
      
      +
      
        jg
        
          k
          ,
          j
        
      
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              e
              
                jπ
                ⁢
                
                  
                
                ⁢
                n
                ⁢
                
                  /
                
                ⁢
                N
              
            
          
          )
        
        *
        
          e
          
            j2π
            ⁢
            
              
            
            ⁢
            nk
            ⁢
            
              /
            
            ⁢
            N
          
        
      
    
  




which can be used to solve the MDCT when rewritten as




  
    X
    k
  
  =
  
    
      
        cos
        ⁢
        
          
        
        ⁢
        
          γ
          ⁡
          
            (
            k
            )
          
        
        ⁢
        
          
            1
            ⁢
            
              /
            
            ⁢
            2
            ⁢
            
              (
              
                
                  
                    e
                    
                      
                        jπ
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                  
                  ⁢
                  
                    G
                    k
                  
                
                +
                
                  
                    e
                    
                      
                        -
                        
                          jπ
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                  
                  ⁢
                  
                    G
                    k
                    *
                  
                
              
              )
            
          
          
            }
            
              T
              1
            
          
        
      
      -
      
        sin
        ⁢
        
          
        
        ⁢
        
          γ
          ⁡
          
            (
            k
            )
          
        
        ⁢
        
          
            1
            ⁢
            
              /
            
            ⁢
            2
            ⁢
            
              j
              ⁡
              
                (
                
                  
                    
                      e
                      
                        
                          jπ
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        ⁢
                        
                          /
                        
                        ⁢
                        N
                      
                    
                    ⁢
                    
                      G
                      k
                    
                  
                  -
                  
                    
                      e
                      
                        
                          -
                          
                            jπ
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  ⁢
                                  
                                    /
                                  
                                  ⁢
                                  2
                                
                              
                              )
                            
                          
                        
                        ⁢
                        
                          /
                        
                        ⁢
                        N
                      
                    
                    ⁢
                    
                      G
                      k
                      *
                    
                  
                
                )
              
            
          
          }
        
      
    
    =
    
      
        cos
        ⁢
        
          
        
        ⁢
        γ
        *
        
          
            (
            
              
                
                  g
                  
                    k
                    ,
                    r
                  
                
                ⁢
                
                  cos
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                    )
                  
                
              
              -
              
                
                  g
                  
                    k
                    ,
                    i
                  
                
                ⁢
                
                  sin
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                    )
                  
                
              
            
            )
          
          
            }
            
              T
              1
            
          
        
      
      -
      
        sin
        ⁢
        
          
        
        ⁢
        γ
        *
        
          
            (
            
              
                
                  g
                  
                    k
                    ,
                    r
                  
                
                ⁢
                
                  sin
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                    )
                  
                
              
              +
              
                
                  g
                  
                    k
                    ,
                    i
                  
                
                ⁢
                
                  cos
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                    )
                  
                
              
            
            )
          
          
            }
            
              T
              
                
                  
                
                11
              
            
          
        
      
    
  







BRIEF DESCRIPTION OF THE DRAWINGS
The invention is more fully described, by way of non-limiting example only, with reference to the drawings, in which:
FIG. 1 is a representation of an audio input sequence;
FIG. 2 is a diagrammatic representation of an encoder; and
FIG. 3 illustrates evaluation of the input sequence into a coefficient set.



DETAILED DESCRIPTION OF A PREFERRED EMBODIMENT
The input to an audio coder comprises a stream of digitized samples of a time domain analog signal. For a multi-channel encoder the stream consists of interleaved samples for each channel, the input stream is sectioned into blocks, each block containing N consecutive samples of each channel (see FIG. 1). Thus within a block the N samples of a channel form a sequence {x[0],x[1],x[2], . . . , x[N-1]}. The time domain samples are next converted to the frequency domain using an analysis filter bank (see FIG. 2).
The frequency domain coefficients, thus generated, form a coefficient set which can be identified as (X0,X1,X2, . . . , XN/2-1). Since the signal is real only the first N/2 frequency components are considered. Here X0 is the lowest frequency (DC) component while XN/2-1 is the highest frequency component of the signal.
Audio compression essentially entails finding how much of the information in the set (X0,X1,X2, . . . , XN/2-1) is necessary to reproduce the original analog signal at the decoder with minimal audible distortion.
The coefficient set is normally converted into floating point format, where each coefficient is represented by an exponent and mantissa.
The exponent set is usually transmitted in its original form. However, the mantissa is truncated to a fixed or variable number of decimal places. The value of the number of bits fro coding a mantissa is usually obtained from a bit allocation algorithm, which for advanced psychoacoustic coders may be based on the making property of the human auditory system. A low number of bits results in higher compression ratio because less space is required to transmit the coefficients. However this causes a very high quantization error leading to audible distortion. A good distribution of available bits to each mantissa forms the core of the most advanced encoders.
In some encoders such as the AC-3, the frequency domain transformation of signals is performed by the (MDCT) modified discrete cosine transform (Eq. 1).




  
    
      
        
          
            X
            k
          
          =
          
            
              ∑
              
                n
                =
                0
              
              
                n
                =
                
                  N
                  -
                  1
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                x
                ⁡
                
                  [
                  n
                  ]
                
              
              *
              
                cos
                ⁡
                
                  (
                  
                    
                      2
                      ⁢
                      π
                      *
                      
                        (
                        
                          
                            2
                            ⁢
                            n
                          
                          -
                          1
                        
                        )
                      
                      *
                      
                        (
                        
                          
                            2
                            ⁢
                            k
                          
                          -
                          1
                        
                        )
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      4
                      ⁢
                      N
                    
                    -
                    
                      π
                      *
                      
                        (
                        
                          
                            2
                            ⁢
                            k
                          
                          +
                          1
                        
                        )
                      
                      ⁢
                      
                        /
                      
                      ⁢
                      4
                    
                  
                  )
                
              
            
          
        
        ⁢
        
          

        
        ⁢
        
          k
          =
          
            0
            ⁢
            
              ...
              ⁡
              
                (
                
                  
                    N
                    ⁢
                    
                      /
                    
                    ⁢
                    2
                  
                  -
                  1
                
                )
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        1
      
    
  




If directly implemented in the form given above, the MDCT requires O(N2) additions and multiplications.
However it is possible to reduce the number of required operations significantly if one is able to evaluate Eq. 1 using the well known Fast Fourier Transform method of J. W. Cooley and J. W. Tukey (1960). The general Discrete Fourier Transform (DFT) is given below (Eq. 2). It requires O(N2) complex additions and multiplications. But by using the Fast Fourier Transform method the DFT in Eq. 2 can be computed with O(Nlog2N) operations only. Eq. 2.



  
    
      F
      k
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
      
      ⁢
      
        (
        
          
            x
            ⁡
            
              [
              n
              ]
            
          
          *
          
            e
            
              2
              ⁢
              π
              ⁢
              
                
              
              ⁢
              j
              ⁢
              
                
              
              ⁢
              nk
              ⁢
              
                /
              
              ⁢
              N
            
          
        
        )
      
    
  




  
    k
    =
    
      
        0
        ⁢
        ...
        ⁢
        
          
        
        ⁢
        N
      
      -
      1
    
  



Here j is the symbol for imaginary number, i.e. J−√{square root over (−)}1.
Although it may not be immediately apparent how Eq. 1 can be transformed to Eq. 2, a careful analysis shows that this is indeed possible. To simplify Eq. 1, let us define two functions

α(n,κ)=2π(2n+1)(2κ+1)/4N  Eq.3

and

γ(κ)=π(2κ+1)/4  Eq. 4

Then, using functions, Eq. 1 can be rewritten as



bbb



In Eq. 6 the trigonometric equality, cos(a+b)=cos a cos b-sinasinb is used for simplification. Furthermore, since the function γ(κ) is only dependent on variable n, it can be brought outside the summation expression to give




  
    
      
        
          X
          k
        
        =
        
          
            cos
            ⁢
            
              
            
            ⁢
            
              γ
              ⁡
              
                (
                k
                )
              
            
            ⁢
            
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    n
                    =
                    
                      N
                      -
                      1
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    x
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  *
                  cos
                  ⁢
                  
                    
                  
                  ⁢
                  
                    α
                    ⁡
                    
                      (
                      
                        n
                        ,
                        k
                      
                      )
                    
                  
                
              
              
                }
                
                  T
                  1
                
              
            
          
          -
          
            sin
            ⁢
            
              
            
            ⁢
            
              γ
              ⁡
              
                (
                k
                )
              
            
            ⁢
            
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    n
                    =
                    
                      N
                      -
                      1
                    
                  
                
                ⁢
                
                  
                
                ⁢
                
                  
                    x
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  *
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  
                    α
                    ⁡
                    
                      (
                      
                        n
                        ,
                        k
                      
                      )
                    
                  
                
              
              
                }
                
                  T
                  2
                
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        7
      
    
  




The two terms, T1 and T2, in Eq.7 can now be evaluated separately. From Euler's identity eiθ=cos θ+j sin θ, we know that cos α(n,κ)=(eja(n,κ)+e−ja(n,κ))/2 and sin α(n,κ)=(eja(n,κ)−e−ja(n,κ)2j. Therefore we can rewrite the terms T1 and T2 as




  
    
      
        
          
            T
            1
          
          =
          
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  n
                  =
                  
                    N
                    -
                    1
                  
                
              
              ⁢
              
                
              
              ⁢
              
                
                  x
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                *
                
                  (
                  
                    
                      e
                      jα
                    
                    -
                    
                      e
                      
                        -
                        jα
                      
                    
                  
                  )
                
                ⁢
                
                  /
                
                ⁢
                2
              
            
            =
            
              1
              ⁢
              
                /
              
              ⁢
              2
              ⁢
              
                {
                
                  
                    
                      
                        ∑
                        
                          n
                          =
                          0
                        
                        
                          n
                          =
                          
                            N
                            -
                            1
                          
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        *
                        
                          e
                          jα
                        
                      
                    
                    
                      }
                      
                        A
                        1
                      
                    
                  
                  +
                  
                    
                      
                        ∑
                        
                          n
                          =
                          0
                        
                        
                          n
                          =
                          
                            N
                            -
                            1
                          
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          x
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        *
                        
                          e
                          
                            -
                            jα
                          
                        
                      
                    
                    
                      }
                      
                        A
                        2
                      
                    
                  
                
                }
              
            
          
        
        ⁢
        
          

        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        8
      
    
  
  
    
      
        
          T
          2
        
        =
        
          
            
              ∑
              
                n
                =
                0
              
              
                n
                =
                
                  N
                  -
                  1
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                x
                ⁡
                
                  [
                  n
                  ]
                
              
              *
              
                (
                
                  
                    e
                    jα
                  
                  -
                  
                    e
                    
                      -
                      jα
                    
                  
                
                )
              
              ⁢
              
                /
              
              ⁢
              2
              ⁢
              j
            
          
          =
          
            1
            ⁢
            
              /
            
            ⁢
            2
            ⁢
            j
            ⁢
            
              {
              
                
                  
                    
                      ∑
                      
                        n
                        =
                        0
                      
                      
                        n
                        =
                        
                          N
                          -
                          1
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        x
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      *
                      
                        e
                        jα
                      
                    
                  
                  
                    }
                    
                      A
                      1
                    
                  
                
                +
                
                  
                    
                      ∑
                      
                        n
                        =
                        0
                      
                      
                        n
                        =
                        
                          N
                          -
                          1
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        x
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      *
                      
                        e
                        
                          -
                          jα
                        
                      
                    
                  
                  
                    }
                    
                      A
                      2
                    
                  
                
              
              }
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        9
      
    
  




We evaluate the term A1. From Eq. 8 and Eq. 9 note that




  
    
      
        
          A
          1
        
        =
        
          
            ∑
            
              n
              =
              0
            
            
              n
              =
              
                N
                -
                1
              
            
          
          ⁢
          
            
          
          ⁢
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            *
            
              e
              jα
            
          
        
      
    
    
      
        
      
    
  
  
    
      
        =
        
          
            ∑
            
              n
              =
              0
            
            
              n
              =
              
                N
                -
                1
              
            
          
          ⁢
          
            
          
          ⁢
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            *
            
              e
              
                j
                (
                
                  2
                  ⁢
                  
                    π
                    ⁡
                    
                      (
                      
                        
                          2
                          ⁢
                          n
                        
                        +
                        1
                      
                      )
                    
                  
                  ⁢
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  ⁢
                  
                    /
                  
                  ⁢
                  4
                  ⁢
                  N
                
              
            
          
        
      
    
    
      
        
      
    
  
  
    
      
        =
        
          
            e
            
              
                jπ
                ⁡
                
                  (
                  
                    k
                    +
                    
                      1
                      ⁢
                      
                        /
                      
                      ⁢
                      2
                    
                  
                  )
                
              
              ⁢
              
                /
              
              ⁢
              N
            
          
          *
          
            
              ∑
              
                n
                =
                0
              
              
                n
                =
                
                  N
                  -
                  1
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                (
                
                  
                    x
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  *
                  
                    e
                    
                      jπ
                      ⁢
                      
                        
                      
                      ⁢
                      n
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                  
                
                )
              
              *
              
                e
                
                  j2π
                  ⁢
                  
                    
                  
                  ⁢
                  nk
                  ⁢
                  
                    /
                  
                  ⁢
                  N
                
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        10
      
    
  




If we define a complex variable

χ1[n]=χ[n]*eJκnlN  Eq. 11

then the Eq. 10 is simply




  
    
      
        
          A
          1
        
        =
        
          
            e
            
              
                jπ
                ⁡
                
                  (
                  
                    k
                    +
                    
                      1
                      ⁢
                      
                        /
                      
                      ⁢
                      2
                    
                  
                  )
                
              
              ⁢
              
                /
              
              ⁢
              N
            
          
          *
          
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  n
                  =
                  
                    N
                    -
                    1
                  
                
              
              ⁢
              
                
              
              ⁢
              
                
                  
                    x
                    ′
                  
                  ⁡
                  
                    [
                    n
                    ]
                  
                
                *
                
                  e
                  
                    j2π
                    ⁢
                    
                      
                    
                    ⁢
                    nk
                    ⁢
                    
                      /
                    
                    ⁢
                    N
                  
                
              
            
            
              }
              
                G
                k
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        12
      
    
  




The complex term Gκ=gκr+jgκ,l, where gκ,l and gk,i ε (set of real numbers) in Eq. 12 is essentially the same as F78 in Eq. 2. Therefore the FFT approach can be used to evaluate G78. This brings down the computation from O/N2 to O(Nlog2N). We can now, similarly, evaluate the second term A2 in Eq. 8 and Eq. 9.




  
    
      
        
          A
          2
        
        =
        
          
            
              ∑
              
                n
                =
                0
              
              
                n
                =
                
                  N
                  -
                  1
                
              
            
            ⁢
            
              
            
            ⁢
            
              
                x
                ⁡
                
                  [
                  n
                  ]
                
              
              *
              
                e
                
                  -
                  
                    jα
                    ⁡
                    
                      (
                      
                        n
                        ,
                        k
                      
                      )
                    
                  
                
              
            
          
          =
          
            
              e
              
                
                  -
                  
                    jπ
                    ⁡
                    
                      (
                      
                        k
                        +
                        
                          1
                          ⁢
                          
                            /
                          
                          ⁢
                          2
                        
                      
                      )
                    
                  
                
                ⁢
                
                  /
                
                ⁢
                N
              
            
            *
            
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    n
                    =
                    
                      N
                      -
                      1
                    
                  
                
                ⁢
                
                  
                    (
                    
                      
                        x
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      *
                      
                        e
                        
                          
                            -
                            jπn
                          
                          ⁢
                          
                            /
                          
                          ⁢
                          N
                        
                      
                    
                    )
                  
                  *
                  
                    e
                    
                      
                        -
                        j2π
                      
                      ⁢
                      
                        
                      
                      ⁢
                      nk
                      ⁢
                      
                        /
                      
                      ⁢
                      N
                    
                  
                
              
              
                }
                
                  G
                  i
                
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        13
      
    
  




Note that Gκ* is actually the complex conjugate of Gκwhich was obtained earlier by Eq. 12. That is, if Gκ=gκ,r+jgk,i, where gκ,i ε  as defined earlier then Gκ*=κ,rjgκ,i. Therefore, Gκ* in Eq. 12 does not need to computed again and result from Eq. 12 can be reused. That is only one FFT needs to be computed for the evaluation of T1. Using Eq. 8 to 13 we obtain

T1=1⁄2(eiπ(κ+1/2)YNGκ+e−kπ(κ+1/2)lNGκ*)  Eq. 14

Next, we analyse the term T2.




  
    
      
         
        
          
            
              
                 
                
                  
                    T
                    2
                  
                  =
                  
                  ⁢
                  
                    
                      ∑
                      
                        n
                        =
                        0
                      
                      
                        n
                        =
                        
                          N
                          -
                          1
                        
                      
                    
                    ⁢
                    
                      
                    
                    ⁢
                    
                      
                        x
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      *
                      
                        
                          (
                          
                            
                              e
                              jα
                            
                            -
                            
                              e
                              
                                -
                                jα
                              
                            
                          
                          )
                        
                        /
                        2
                      
                      ⁢
                      j
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    /
                    2
                  
                  ⁢
                  
                    j
                    ⁡
                    
                      (
                      
                        
                          A
                          1
                        
                        -
                        
                          A
                          2
                        
                      
                      )
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    1
                    /
                    2
                  
                  ⁢
                  
                    j
                    ⁡
                    
                      (
                      
                        
                          
                            e
                            
                              
                                jπ
                                ⁡
                                
                                  (
                                  
                                    k
                                    +
                                    
                                      1
                                      /
                                      2
                                    
                                  
                                  )
                                
                              
                              /
                              N
                            
                          
                          ⁢
                          
                            G
                            k
                          
                        
                        -
                        
                          
                            e
                            
                              
                                -
                                
                                  jπ
                                  ⁡
                                  
                                    (
                                    
                                      k
                                      +
                                      
                                        1
                                        /
                                        2
                                      
                                    
                                    )
                                  
                                
                              
                              /
                              N
                            
                          
                          ⁢
                          
                            G
                            k
                            *
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        15
      
    
  




Finally after simplifications of Eq. 7,14 and 15 we obtain




  
    
      
         
        
          
            
              
                
                  X
                  k
                
                =
                
                ⁢
                
                  
                    cos
                    ⁢
                    
                      
                    
                    ⁢
                    
                      γ
                      ⁡
                      
                        (
                        k
                        )
                      
                    
                    ⁢
                    
                      
                        
                          1
                          /
                          2
                        
                        ⁢
                        
                          (
                          
                            
                              
                                e
                                
                                  
                                    jπ
                                    ⁡
                                    
                                      (
                                      
                                        k
                                        +
                                        
                                          1
                                          /
                                          2
                                        
                                      
                                      )
                                    
                                  
                                  /
                                  N
                                
                              
                              ⁢
                              
                                G
                                k
                              
                            
                            +
                            
                              
                                e
                                
                                  
                                    -
                                    
                                      jπ
                                      ⁡
                                      
                                        (
                                        
                                          k
                                          +
                                          
                                            1
                                            /
                                            2
                                          
                                        
                                        )
                                      
                                    
                                  
                                  /
                                  N
                                
                              
                              ⁢
                              
                                G
                                k
                                *
                              
                            
                          
                          )
                        
                      
                      
                        }
                        
                          T
                          1
                        
                      
                    
                  
                  -
                
              
            
          
          
            
              
                
                ⁢
                
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  
                    γ
                    ⁡
                    
                      (
                      k
                      )
                    
                  
                  ⁢
                  
                    
                      
                        1
                        /
                        2
                      
                      ⁢
                      
                        j
                        ⁡
                        
                          (
                          
                            
                              
                                e
                                
                                  
                                    jπ
                                    ⁡
                                    
                                      (
                                      
                                        k
                                        +
                                        
                                          1
                                          /
                                          2
                                        
                                      
                                      )
                                    
                                  
                                  /
                                  N
                                
                              
                              ⁢
                              
                                G
                                k
                              
                            
                            -
                            
                              
                                e
                                
                                  
                                    -
                                    
                                      jπ
                                      ⁡
                                      
                                        (
                                        
                                          k
                                          +
                                          
                                            1
                                            /
                                            2
                                          
                                        
                                        )
                                      
                                    
                                  
                                  /
                                  N
                                
                              
                              ⁢
                              
                                G
                                k
                                *
                              
                            
                          
                          )
                        
                      
                    
                    
                      }
                      
                        T
                        2
                      
                    
                  
                
              
            
          
          
            
              
                =
                
                ⁢
                
                  
                    cos
                    ⁢
                    
                      
                    
                    ⁢
                    γ
                    *
                    
                      
                        (
                        
                          
                            
                              g
                              
                                k
                                ,
                                r
                              
                            
                            ⁢
                            
                              cos
                              ⁡
                              
                                (
                                
                                  
                                    π
                                    ⁡
                                    
                                      (
                                      
                                        k
                                        +
                                        
                                          1
                                          /
                                          2
                                        
                                      
                                      )
                                    
                                  
                                  /
                                  N
                                
                                )
                              
                            
                          
                          -
                          
                            
                              g
                              
                                k
                                ,
                                i
                              
                            
                            ⁢
                            
                              sin
                              ⁡
                              
                                (
                                
                                  
                                    π
                                    ⁡
                                    
                                      (
                                      
                                        k
                                        +
                                        
                                          1
                                          /
                                          2
                                        
                                      
                                      )
                                    
                                  
                                  /
                                  N
                                
                                )
                              
                            
                          
                        
                      
                      
                        }
                        
                          T
                          1
                        
                      
                    
                  
                  -
                
              
            
          
          
            
              
                
                ⁢
                
                  sin
                  ⁢
                  
                    
                  
                  ⁢
                  γ
                  *
                  
                    
                      (
                      
                        
                          
                            g
                            
                              k
                              ,
                              r
                            
                          
                          ⁢
                          
                            sin
                            ⁡
                            
                              (
                              
                                
                                  π
                                  ⁡
                                  
                                    (
                                    
                                      k
                                      +
                                      
                                        1
                                        /
                                        2
                                      
                                    
                                    )
                                  
                                
                                /
                                N
                              
                              )
                            
                          
                        
                        +
                        
                          
                            g
                            
                              k
                              ,
                              i
                            
                          
                          ⁢
                          
                            cos
                            ⁡
                            
                              (
                              
                                
                                  π
                                  ⁡
                                  
                                    (
                                    
                                      k
                                      +
                                      
                                        1
                                        /
                                        2
                                      
                                    
                                    )
                                  
                                
                                /
                                N
                              
                              )
                            
                          
                        
                      
                    
                    
                      }
                      
                        T
                        2
                      
                    
                  
                
              
            
          
        
      
    
    
      
        Eq
        .
        
          
        
        ⁢
        16
      
    
  




The term Gκ=gκr+jgκ,l may be computed in O(NlogN) operation using FT algorithms. The additional operation outlined in Eq. 16 to extract the final Xκis only of order O(N). Therefore the MDCT can now be computed in O(Nlog2N) time. The operations required to obtain the MDCT is illustrated in FIG. 3.
N-Point MDCT Using N/2-Point FFT
Since the most computationally intensive part is the FFT, we shall focus on it in order to decrease computation even further. The values of




  
    G
    k
  
  =
  
    
      ∑
      
        n
        =
        0
      
      
        N
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      [
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    n
                  
                  N
                
              
            
          
          )
        
        ⁢
        
          e
          
            j
            ⁢
            
              
                2
                ⁢
                x
                ⁢
                
                  
                
                ⁢
                nk
              
              N
            
          
        
      
      ]
    
  




required in Eq. 16 may be obtained through an N/2-Point FFT.

It is well known that an N-Point FFT of a sequence of N real data can be easily obtained by using a N/2-Point FFT only, provided the FFT is preceded by a pre-processing and followed by a post-processing which formats the inputs so that the final result is mathematically identical in both cases.
In our present case, the input to the FFT block is a sequence of N complex data. To evaluate the FFT of N arbitrary complex numbers, an N-Point FFT is definitely required. A M-Point FFT, M<N will not do. In the present cas however, the input sequence is not completely an arbitrary complex sequence but is of the form




  
    
      x
      ⁡
      
        [
        n
        ]
      
    
    ⁢
    
      e
      
        j
        ⁢
        
          
            x
            ⁢
            
              
            
            ⁢
            n
          
          N
        
      
    
  
  ,




where x[n] is real.





  
    G
    k
  
  =
  
    
      ∑
      
        n
        =
        0
      
      
        N
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      [
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            *
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁢
                    
                      
                    
                    ⁢
                    n
                  
                  N
                
              
            
          
          )
        
        ⁢
        
          e
          
            j
            ⁢
            
              
                2
                ⁢
                x
                ⁢
                
                  
                
                ⁢
                nk
              
              N
            
          
        
      
      ]
    
  




Let us define




  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        (
        
          
            x
            ⁡
            
              [
              
                2
                ⁢
                n
              
              ]
            
          
          +
          
            j
            ⁢
            
              
            
            ⁢
            
              x
              ⁡
              
                [
                
                  
                    2
                    ⁢
                    n
                  
                  +
                  1
                
                ]
              
            
          
        
        )
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              x
              ⁢
              
                
              
              ⁢
              n
            
            N
          
        
      
    
  
  ,




0≦n≦(N/2−1). Then, taking a N/2-Point FFT of z[n].





  
    
      Z
      k
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          
            N
            /
            2
          
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        [
        
          
            z
            ⁡
            
              [
              n
              ]
            
          
          ⁢
          
            e
            
              j
              ⁢
              
                
                  2
                  ⁢
                  x
                  ⁢
                  
                    
                  
                  ⁢
                  nk
                
                
                  N
                  /
                  2
                
              
            
          
        
        ]
      
    
  
  ,
  
    0
    ≤
    k
    ≤
    
      
        N
        /
        2
      
      -
      1
    
  




Therefore,




  
    Z
    
      
        N
        2
      
      -
      k
      -
      1
    
  
  =
  
    
      ∑
      
        n
        =
        0
      
      
        
          N
          /
          2
        
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      
        [
        
          
            z
            ⁡
            
              [
              n
              ]
            
          
          ⁢
          
            e
            
              
                -
                j
              
              ⁢
              
                
                  2
                  ⁢
                  x
                  ⁢
                  
                    
                  
                  ⁢
                  nk
                
                
                  N
                  /
                  2
                
              
            
          
          ⁢
          
            e
            
              
                -
                j
              
              ⁢
              
                
                  2
                  ⁢
                  x
                  ⁢
                  
                    
                  
                  ⁢
                  n
                
                
                  N
                  /
                  2
                
              
            
          
        
        ]
      
      .
    
  




Taking the complex conjugate of





  Z
  
    
      N
      2
    
    -
    k
    -
    1
  




gives us





  
    Z
    
      
        N
        2
      
      -
      k
      -
      1
    
    *
  
  =
  
    
      ∑
      
        n
        =
        0
      
      
        
          N
          /
          2
        
        -
        1
      
    
    ⁢
    
      
    
    ⁢
    
      
        [
        
          
            
              z
              *
            
            ⁡
            
              [
              n
              ]
            
          
          ⁢
          
            e
            
              j
              ⁢
              
                
                  2
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  nk
                
                
                  N
                  /
                  2
                
              
            
          
          ⁢
          
            e
            
              j
              ⁢
              
                
                  2
                  ⁢
                  π
                  ⁢
                  
                    
                  
                  ⁢
                  n
                
                
                  N
                  /
                  2
                
              
            
          
        
        ]
      
      .
    
  




Also, note that with some simplifications we obtain





  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    +
    
      
        
          z
          *
        
        ⁡
        
          [
          n
          ]
        
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              x
              ⁢
              
                
              
              ⁢
              n
            
            
              N
              /
              2
            
          
        
      
    
  
  =
  
    
      
        2
        ⁢
        
          x
          ⁡
          
            [
            
              2
              ⁢
              n
            
            ]
          
        
        ⁢
        
          e
          
            j
            ⁢
            
              
                x
                ⁡
                
                  (
                  
                    2
                    ⁢
                    n
                  
                  )
                
              
              N
            
          
        
        ⁢
        
          
        
        ⁢
        and
        ⁢
        
          
        
        ⁢
        
          z
          ⁡
          
            [
            n
            ]
          
        
      
      -
      
        
          
            z
            *
          
          ⁡
          
            [
            n
            ]
          
        
        ⁢
        
          e
          
            j
            ⁢
            
              
                2
                ⁢
                x
                ⁢
                
                  
                
                ⁢
                n
              
              N
            
          
        
      
    
    =
    
      2
      ⁢
      
        x
        ⁡
        
          [
          
            2
            ⁢
            n
          
          ]
        
      
      ⁢
      
        
          e
          
            j
            ⁢
            
              
                x
                ⁡
                
                  (
                  
                    2
                    ⁢
                    n
                  
                  )
                
              
              N
            
          
        
        .
      
    
  




We now have all the essential derivations for us to obtain Gκfrom Zκ.





  
    
      
        
          
            1
            2
          
          ⁡
          
            [
            
              
                Z
                k
              
              +
              
                Z
                
                  
                    N
                    2
                  
                  -
                  k
                  -
                  1
                
              
            
            ]
          
        
        =
        
        ⁢
        
          
            1
            2
          
          ⁡
          
            [
            
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    
                      N
                      /
                      2
                    
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  [
                  
                    
                      z
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    ⁢
                    
                      e
                      
                        j
                        ⁢
                        
                          
                            2
                            ⁢
                            xnk
                          
                          
                            N
                            /
                            2
                          
                        
                      
                    
                  
                  ]
                
              
              +
              
                
                  ∑
                  
                    n
                    =
                    0
                  
                  
                    
                      N
                      /
                      2
                    
                    -
                    1
                  
                
                ⁢
                
                  
                
                ⁢
                
                  [
                  
                    
                      
                        z
                        *
                      
                      ⁡
                      
                        [
                        n
                        ]
                      
                    
                    ⁢
                    
                      e
                      
                        j
                        ⁢
                        
                          
                            2
                            ⁢
                            xnk
                          
                          
                            N
                            /
                            2
                          
                        
                      
                    
                    ⁢
                    
                      e
                      
                        j
                        ⁢
                        
                          
                            2
                            ⁢
                            xn
                          
                          
                            N
                            /
                            2
                          
                        
                      
                    
                  
                  ]
                
              
            
            ]
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            1
            2
          
          ⁡
          
            [
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  
                    N
                    /
                    2
                  
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                [
                
                  
                    (
                    
                      
                        z
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      +
                      
                        
                          
                            z
                            *
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        ⁢
                        
                          e
                          
                            j
                            ⁢
                            
                              
                                2
                                ⁢
                                x
                                ⁢
                                
                                  
                                
                                ⁢
                                n
                              
                              
                                N
                                /
                                2
                              
                            
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    e
                    
                      j
                      ⁢
                      
                        
                          2
                          ⁢
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          nk
                        
                        
                          N
                          /
                          2
                        
                      
                    
                  
                
                ]
              
            
            ]
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            1
            2
          
          ⁢
          
            
              ∑
              
                n
                =
                0
              
              
                
                  N
                  /
                  2
                
                -
                1
              
            
            ⁢
            
              
            
            ⁢
            
              [
              
                
                  (
                  
                    2
                    ⁢
                    
                      x
                      ⁡
                      
                        [
                        
                          2
                          ⁢
                          n
                        
                        ]
                      
                    
                    ⁢
                    
                      e
                      
                        j
                        ⁢
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                2
                                ⁢
                                n
                              
                              )
                            
                          
                          N
                        
                      
                    
                  
                  )
                
                ⁢
                
                  e
                  
                    j
                    ⁢
                    
                      
                        2
                        ⁢
                        
                          x
                          ⁡
                          
                            (
                            
                              2
                              ⁢
                              x
                            
                            )
                          
                        
                        ⁢
                        k
                      
                      N
                    
                  
                
              
              ]
            
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                /
                2
              
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            [
            
              
                (
                
                  
                    x
                    ⁡
                    
                      [
                      
                        2
                        ⁢
                        n
                      
                      ]
                    
                  
                  ⁢
                  
                    e
                    
                      j
                      ⁢
                      
                        
                          x
                          ⁡
                          
                            (
                            
                              2
                              ⁢
                              n
                            
                            )
                          
                        
                        N
                      
                    
                  
                
                )
              
              ⁢
              
                e
                
                  j
                  ⁢
                  
                    
                      2
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          
                            2
                            ⁢
                            n
                          
                          )
                        
                      
                      ⁢
                      k
                    
                    N
                  
                
              
            
            ]
          
        
      
    
  
  
    
      
        
          
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁡
                    
                      (
                      
                        
                          2
                          ⁢
                          k
                        
                        +
                        1
                      
                      )
                    
                  
                  N
                
              
            
            
              2
              ⁢
              j
            
          
          ⁡
          
            [
            
              
                Z
                k
              
              -
              
                Z
                
                  
                    N
                    2
                  
                  -
                  k
                  -
                  1
                
                *
              
            
            ]
          
        
        =
        
        ⁢
        
          
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁡
                    
                      (
                      
                        
                          2
                          ⁢
                          k
                        
                        +
                        1
                      
                      )
                    
                  
                  N
                
              
            
            
              2
              ⁢
              j
            
          
          [
          
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  
                    N
                    /
                    2
                  
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                [
                
                  
                    z
                    ⁡
                    
                      [
                      n
                      ]
                    
                  
                  ⁢
                  
                    e
                    
                      j
                      ⁢
                      
                        
                          2
                          ⁢
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          nk
                        
                        
                          N
                          /
                          2
                        
                      
                    
                  
                
                ]
              
            
            -
          
        
      
    
  
  
    
      
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                /
                2
              
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            [
            
              
                
                  z
                  *
                
                ⁡
                
                  [
                  n
                  ]
                
              
              ⁢
              
                e
                
                  j
                  ⁢
                  
                    
                      2
                      ⁢
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      nk
                    
                    
                      N
                      /
                      2
                    
                  
                
              
              ⁢
              
                e
                
                  j
                  ⁢
                  
                    
                      2
                      ⁢
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    
                      N
                      /
                      2
                    
                  
                
              
            
            ]
          
        
        ]
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁡
                    
                      (
                      
                        
                          2
                          ⁢
                          k
                        
                        +
                        1
                      
                      )
                    
                  
                  N
                
              
            
            
              2
              ⁢
              j
            
          
          ⁡
          
            [
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  
                    N
                    /
                    2
                  
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                [
                
                  
                    (
                    
                      
                        z
                        ⁡
                        
                          [
                          n
                          ]
                        
                      
                      -
                      
                        
                          
                            z
                            *
                          
                          ⁡
                          
                            [
                            n
                            ]
                          
                        
                        ⁢
                        
                          e
                          
                            j
                            ⁢
                            
                              
                                2
                                ⁢
                                x
                                ⁢
                                
                                  
                                
                                ⁢
                                n
                              
                              
                                N
                                /
                                2
                              
                            
                          
                        
                      
                    
                    )
                  
                  ⁢
                  
                    e
                    
                      j
                      ⁢
                      
                        
                          2
                          ⁢
                          x
                          ⁢
                          
                            
                          
                          ⁢
                          nk
                        
                        
                          N
                          /
                          2
                        
                      
                    
                  
                
                ]
              
            
            ]
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            
              e
              
                j
                ⁢
                
                  
                    x
                    ⁡
                    
                      (
                      
                        
                          2
                          ⁢
                          k
                        
                        +
                        1
                      
                      )
                    
                  
                  N
                
              
            
            
              2
              ⁢
              j
            
          
          ⁡
          
            [
            
              
                ∑
                
                  n
                  =
                  0
                
                
                  
                    N
                    /
                    2
                  
                  -
                  1
                
              
              ⁢
              
                
              
              ⁢
              
                
                  (
                  
                    2
                    ⁢
                    j
                    ⁢
                    
                      
                    
                    ⁢
                    
                      x
                      ⁡
                      
                        [
                        
                          
                            2
                            ⁢
                            n
                          
                          +
                          1
                        
                        ]
                      
                    
                    ⁢
                    
                      e
                      
                        j
                        ⁢
                        
                          
                            x
                            ⁡
                            
                              (
                              
                                2
                                ⁢
                                n
                              
                              )
                            
                          
                          N
                        
                      
                    
                  
                  )
                
                ⁢
                
                  e
                  
                    j
                    ⁢
                    
                      
                        2
                        ⁢
                        x
                        ⁢
                        
                          
                        
                        ⁢
                        
                          (
                          
                            2
                            ⁢
                            n
                          
                          )
                        
                        ⁢
                        k
                      
                      N
                    
                  
                
              
            
            ]
          
        
      
    
  
  
    
      
        =
        
        ⁢
        
          
            ∑
            
              n
              =
              0
            
            
              
                N
                /
                2
              
              -
              1
            
          
          ⁢
          
            
          
          ⁢
          
            [
            
              
                (
                
                  
                    x
                    ⁡
                    
                      [
                      
                        
                          2
                          ⁢
                          n
                        
                        +
                        1
                      
                      ]
                    
                  
                  ⁢
                  
                    e
                    
                      j
                      ⁢
                      
                        
                          x
                          ⁡
                          
                            (
                            
                              
                                2
                                ⁢
                                n
                              
                              +
                              1
                            
                            )
                          
                        
                        N
                      
                    
                  
                
                )
              
              ⁢
              
                e
                
                  j
                  ⁢
                  
                    
                      2
                      ⁢
                      
                        x
                        ⁡
                        
                          (
                          
                            
                              2
                              ⁢
                              n
                            
                            +
                            1
                          
                          )
                        
                      
                      ⁢
                      k
                    
                    N
                  
                
              
            
            ]
          
        
      
    
  




Now it is straight forward to get Gκfrom Zκ.




  
    
      
        1
        2
      
      ⁡
      
        [
        
          
            Z
            k
          
          +
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
            *
          
        
        ]
      
    
    +
    
      
        
          e
          
            j
            ⁢
            
              
                x
                ⁡
                
                  (
                  
                    
                      2
                      ⁢
                      k
                    
                    +
                    1
                  
                  )
                
              
              N
            
          
        
        
          2
          ⁢
          j
        
      
      ⁡
      
        [
        
          
            Z
            k
          
          -
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
            *
          
        
        ]
      
    
  
  =
  
    
      
        
          ∑
          
            n
            =
            0
          
          
            
              N
              /
              2
            
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          [
          
            
              (
              
                
                  x
                  ⁡
                  
                    [
                    
                      2
                      ⁢
                      n
                    
                    ]
                  
                
                ⁢
                
                  e
                  
                    j
                    ⁢
                    
                      
                        x
                        ⁡
                        
                          (
                          
                            2
                            ⁢
                            n
                          
                          )
                        
                      
                      N
                    
                  
                
              
              )
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                    2
                    ⁢
                    
                      x
                      ⁡
                      
                        (
                        
                          2
                          ⁢
                          n
                        
                        )
                      
                    
                    ⁢
                    k
                  
                  N
                
              
            
          
          ]
        
      
      +
      
        
          ∑
          
            n
            =
            0
          
          
            
              N
              /
              2
            
            -
            1
          
        
        ⁢
        
          
        
        ⁢
        
          [
          
            
              (
              
                
                  x
                  ⁡
                  
                    [
                    
                      
                        2
                        ⁢
                        n
                      
                      +
                      1
                    
                    ]
                  
                
                ⁢
                
                  e
                  
                    j
                    ⁢
                    
                      
                        x
                        ⁡
                        
                          (
                          
                            
                              2
                              ⁢
                              n
                            
                            +
                            1
                          
                          )
                        
                      
                      N
                    
                  
                
              
              )
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                    2
                    ⁢
                    
                      x
                      ⁡
                      
                        (
                        
                          
                            2
                            ⁢
                            n
                          
                          +
                          1
                        
                        )
                      
                    
                    ⁢
                    k
                  
                  N
                
              
            
          
          ]
        
      
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          N
          -
          1
        
      
      ⁢
      
        
      
      ⁢
      
        [
        
          
            (
            
              
                x
                ⁡
                
                  [
                  n
                  ]
                
              
              *
              
                e
                
                  j
                  ⁢
                  
                    
                      x
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    N
                  
                
              
            
            )
          
          ⁢
          
            e
            
              j
              ⁢
              
                
                  2
                  ⁢
                  x
                  ⁢
                  
                    
                  
                  ⁢
                  nk
                
                N
              
            
          
        
        ]
      
    
  




Accordingly, use of an N/2-Point FFT allows Gκ to be derived, which inturn allows the MDCT of the complex input signal to be evaluated, with reduced computational requirements.

## Claims

1. A method of evaluating a modified discrete cosine transform (MDCT) of an input sequence of complex signal data in an audio signal processor, comprising:
using a Fast Fourier Transform (FFT), wherein the FFT is a N/2-Point FFT, to evaluate, the complex data, from audio signals and wherein the MDCT is




  
    
      X
      k
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
      
      ⁢
      
        
          x
          ⁡
          
            [
            n
            ]
          
        
        *
        
          cos
          ⁡
          
            (
            
              
                2
                ⁢
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      n
                    
                    +
                    1
                  
                  )
                
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
                ⁢
                N
              
              +
              
                π
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
              
            
            )
          
        
      
    
  




  
    k
    =
    
      0
      ⁢
      
        
      
      ⁢
      ...
      ⁢
      
        
      
      ⁢
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
    
  



where x[n] represents the input sequence and N is the number of data samples in the sequence.

2. The method of claim 1, wherein a transform coefficient sequence of the MDCT is derived using the N/2-Point FFT of a complex function z[n], where




  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        (
        
          
            x
            ⁡
            
              [
              
                2
                ⁢
                n
              
              ]
            
          
          +
          
            j
            ⁢
            
              
            
            ⁢
            
              x
              ⁡
              
                [
                
                  
                    2
                    ⁢
                    n
                  
                  +
                  1
                
                ]
              
            
          
        
        )
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              xn
            
            N
          
        
      
    
  
  ,
  
    0
    ≤
    n
    ≤
    
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
      .

3. The method of claim 2, wherein a transform Zk and the complex conjugate of the transform ZN/2-k-1 are derived from z[n] for the expression




  
    G
    k
  
  =
  
    
      
        1
        2
      
      ⁡
      
        [
        
          
            Z
            k
          
          +
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
    +
    
      
        
          e
          
            
              x
              ⁡
              
                (
                
                  
                    2
                    ⁢
                    k
                  
                  +
                  1
                
                )
              
            
            N
          
        
        
          2
          ⁢
          j
        
      
      ⁡
      
        [
        
          
            Z
            k
          
          -
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
  




where Gk is a transform coefficient sequence which allows the MDCT to be evaluated, in that




  
    G
    k
  
  =
  
    
      
        g
        
          k
          ,
          r
        
      
      +
      
        jg
        
          k
          ,
          i
        
      
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                
                ⁢
                
                  xn
                  /
                  N
                
              
            
          
          )
        
        *
        
          e
          
            j
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              xnk
              /
              N
            
          
        
      
    
  




which can be used to solve the MDCT when rewritten as




   
  
    
      X
      k
    
    =
    
      
        
          cos
          ⁢
          
            
          
          ⁢
          
            γ
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            
              
                1
                /
                2
              
              ⁢
              
                (
                
                  
                    
                      e
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                    
                  
                  +
                  
                    
                      e
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                      *
                    
                  
                
                )
              
            
            
              }
              
                T
                1
              
            
          
        
        -
        
          sin
          ⁢
          
            
          
          ⁢
          
            γ
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            
              
                1
                /
                2
              
              ⁢
              
                j
                ⁡
                
                  (
                  
                    
                      
                        e
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              π
                              ⁡
                              
                                (
                                
                                  k
                                  +
                                  
                                    1
                                    /
                                    2
                                  
                                
                                )
                              
                            
                            /
                            N
                          
                        
                      
                      ⁢
                      
                        G
                        k
                      
                    
                    -
                    
                      
                        e
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              π
                              ⁡
                              
                                (
                                
                                  k
                                  +
                                  
                                    1
                                    /
                                    2
                                  
                                
                                )
                              
                            
                            /
                            N
                          
                        
                      
                      ⁢
                      
                        G
                        k
                        *
                      
                    
                  
                  )
                
              
            
            }
          
        
      
      =
      
        
          cos
          ⁢
          
            
          
          ⁢
          γ
          *
          
            
              (
              
                
                  
                    g
                    
                      k
                      ,
                      r
                    
                  
                  ⁢
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
                -
                
                  
                    g
                    
                      k
                      ,
                      i
                    
                  
                  ⁢
                  
                    sin
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
              
            
            
              }
              
                T
                1
              
            
          
        
        -
        
          sin
          ⁢
          
            
          
          ⁢
          γ
          *
          
            
              
                (
                
                  
                    
                      g
                      
                        k
                        .
                        r
                      
                    
                    ⁢
                    
                      sin
                      ⁡
                      
                        (
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  ⁢
                                  
                                    /
                                  
                                  ⁢
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                        )
                      
                    
                  
                  +
                  
                    
                      g
                      
                        k
                        ,
                        i
                      
                    
                    ⁢
                    
                      cos
                      ⁡
                      
                        (
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  ⁢
                                  
                                    /
                                  
                                  ⁢
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                        )
                      
                    
                  
                
              
              
                }
                
                  T
                  w
                
              
            
            .

4. A multi-channel audio coder, comprising:
an encoder configured to receive a time domain signal and to convert the time domain signal into a frequency domain signal by evaluating a modified discrete cosine transform (MDCT) using a Fast Fourier Transform (FFT) that is a N/2-Point FFT where N is the number of data samples and the MDCT is of the form





  
    X
    k
  
  =
  
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          x
          ⁡
          
            [
            n
            ]
          
        
        *
        
          cos
          ⁡
          
            (
            
              
                2
                ⁢
                
                  
                
                ⁢
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      n
                    
                    +
                    1
                  
                  )
                
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
                ⁢
                N
              
              +
              
                π
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        k
      
    
    =
    
      0
      ⁢
      ...
      ⁢
      
        
      
      ⁢
      
        (
        
          
            N
            /
            2
          
          -
        
        )
      
    
  




where x[n] represents an input sequence and N is the number of data samples of the sequence.

5. The method of claim 4, wherein a transform coefficient sequence of the MDCT is derived using the N/2-Point FFT of a complex function z[n], where




  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        (
        
          
            x
            ⁡
            
              [
              
                2
                ⁢
                n
              
              ]
            
          
          +
          
            jx
            ⁡
            
              [
              
                
                  2
                  ⁢
                  n
                
                +
                1
              
              ]
            
          
        
        )
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              xn
            
            N
          
        
      
    
  
  ,
  
    0
    ≤
    n
    ≤
    
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
      .

6. A multi-channel audio coder, comprising:
an encoder configured to receive a time domain signal and to convert the time domain signal into a frequency domain signal by evaluating a modified discrete cosine transform (MDCT) using a Fast Fourier Transform (FFT) that is a N/2-Point FFT where N is the number of data samples and the MDCT is of the form





  
    X
    k
  
  =
  
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          x
          ⁡
          
            [
            n
            ]
          
        
        *
        
          cos
          ⁡
          
            (
            
              
                2
                ⁢
                
                  
                
                ⁢
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      n
                    
                    +
                    1
                  
                  )
                
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
                ⁢
                N
              
              +
              
                π
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        k
      
    
    =
    
      0
      ⁢
      ...
      ⁢
      
        
      
      ⁢
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
    
  




where x[n] represents an input sequence and N is the number of data samples of the sequence, and wherein a transform coefficient sequence of the MDCT is derived using the N/2-Point FFT of a complex function z[n], where




  
    z
    ⁡
    
      [
      n
      ]
    
  
  =
  
    (
    
      
        
          x
          ⁡
          
            [
            
              2
              ⁢
              n
            
            ]
          
        
        +
        
          j
          ⁢
          
            
          
          ⁢
          
            x
            ⁡
            
              [
              
                
                  2
                  ⁢
                  n
                
                +
                1
              
              ]
            
          
          ⁢
          
            e
            
              j
              ⁢
              
                
                  2
                  ⁢
                  xn
                
                N
              
            
          
        
      
      ,
      
        
      
      ⁢
      
        0
        ≤
        n
        ≤
        
          (
          
            
              N
              /
              2
            
            -
            1
          
          )
        
      
    
  




and wherein a transform Zk and the complex conjugate of the transform ZN/2-k-1 are derived from z[n] for the expression




  
    G
    k
  
  =
  
    
      
        1
        2
      
      ⁡
      
        [
        
          
            Z
            k
          
          +
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
    +
    
      
        
          e
          ⁢
          
            
              x
              ⁡
              
                (
                
                  
                    2
                    ⁢
                    k
                  
                  +
                  1
                
                )
              
            
            N
          
        
        
          2
          ⁢
          
            
          
          ⁢
          j
        
      
      ⁡
      
        [
        
          
            Z
            k
          
          -
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
  




where Gk is a transform coefficient sequence which allows the MDCT to be evaluated, in the




  
    G
    k
  
  =
  
    
      
        g
        
          k
          ,
          r
        
      
      +
      
        j
        ⁢
        
          
        
        ⁢
        
          g
          
            k
            ,
            i
          
        
      
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                
                ⁢
                
                  xn
                  /
                  N
                
              
            
          
          )
        
        *
        
          e
          
            j
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              xnk
              /
              N
            
          
        
      
    
  




which can be used to solve the MDCT when rewritten as




   
  
    
      X
      k
    
    =
    
      
        
          cos
          ⁢
          
            
          
          ⁢
          
            γ
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            
              
                1
                /
                2
              
              ⁢
              
                (
                
                  
                    
                      e
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                    
                  
                  +
                  
                    
                      e
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                      *
                    
                  
                
                )
              
            
            
              }
              
                T
                1
              
            
          
        
        -
        
          sin
          ⁢
          
            
          
          ⁢
          
            γ
            ⁡
            
              (
              k
              )
            
          
          ⁢
          
            
              
                1
                /
                2
              
              ⁢
              
                j
                ⁡
                
                  (
                  
                    
                      
                        e
                        
                          j
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              π
                              ⁡
                              
                                (
                                
                                  k
                                  +
                                  
                                    1
                                    /
                                    2
                                  
                                
                                )
                              
                            
                            /
                            N
                          
                        
                      
                      ⁢
                      
                        G
                        k
                      
                    
                    -
                    
                      
                        e
                        
                          
                            -
                            j
                          
                          ⁢
                          
                            
                          
                          ⁢
                          
                            
                              π
                              ⁡
                              
                                (
                                
                                  k
                                  +
                                  
                                    1
                                    /
                                    2
                                  
                                
                                )
                              
                            
                            /
                            N
                          
                        
                      
                      ⁢
                      
                        G
                        k
                        *
                      
                    
                  
                  )
                
              
            
            }
          
        
      
      =
      
        
          cos
          ⁢
          
            
          
          ⁢
          γ
          *
          
            
              (
              
                
                  
                    g
                    
                      k
                      ,
                      r
                    
                  
                  ⁢
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
                -
                
                  
                    g
                    
                      k
                      ,
                      i
                    
                  
                  ⁢
                  
                    sin
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
              
            
            
              }
              
                T
                1
              
            
          
        
        -
        
          sin
          ⁢
          
            
          
          ⁢
          γ
          *
          
            
              
                (
                
                  
                    
                      g
                      
                        k
                        .
                        r
                      
                    
                    ⁢
                    
                      sin
                      ⁡
                      
                        (
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  ⁢
                                  
                                    /
                                  
                                  ⁢
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                        )
                      
                    
                  
                  +
                  
                    
                      g
                      
                        k
                        ,
                        i
                      
                    
                    ⁢
                    
                      cos
                      ⁡
                      
                        (
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  ⁢
                                  
                                    /
                                  
                                  ⁢
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                        )
                      
                    
                  
                
              
              
                }
                
                  T
                  w
                
              
            
            .

7. A method of coding a multi-channel time domain audio signal, comprising:
receiving multiple time domain audio signals at an encoder and converting the time domain audio signals into complex frequency domain data by evaluating a modified discrete cosine transform (MDCT) using a Fast Fourier Transform (FFT) that is a N/2-Point FFT, where N is the number of data samples, wherein the MDCT is of the form:





  
    X
    k
  
  =
  
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          x
          ⁡
          
            [
            n
            ]
          
        
        *
        
          cos
          ⁡
          
            (
            
              
                2
                ⁢
                π
                *
                
                  (
                  
                    
                      2
                      ⁢
                      n
                    
                    +
                    1
                  
                  )
                
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
                ⁢
                N
              
              +
              
                π
                *
                
                  
                    (
                    
                      
                        2
                        ⁢
                        k
                      
                      +
                      1
                    
                    )
                  
                  /
                  4
                
              
            
            )
          
        
        ⁢
        
          
        
        ⁢
        k
      
    
    =
    
      0
      ⁢
      ...
      ⁢
      
        
      
      ⁢
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
    
  




where x[n] represents an input sequence and N is the number of data samples of the sequence.

8. The method of claim 7 wherein a transform coefficient sequence of the MDCT is derived using the N/2-Point FFT of a complex function z[n], where




  
    
      z
      ⁡
      
        [
        n
        ]
      
    
    =
    
      
        (
        
          
            x
            ⁡
            
              [
              
                2
                ⁢
                n
              
              ]
            
          
          +
          
            j
            ⁢
            
              
            
            ⁢
            
              x
              ⁡
              
                [
                
                  
                    2
                    ⁢
                    n
                  
                  +
                  1
                
                ]
              
            
          
        
        )
      
      ⁢
      
        e
        
          j
          ⁢
          
            
              2
              ⁢
              xn
            
            N
          
        
      
    
  
  ,
  
    
  
  ⁢
  
    0
    ≤
    n
    ≤
    
      
        (
        
          
            N
            /
            2
          
          -
          1
        
        )
      
      .

9. The method of claim 8 wherein a transform Zk and the complex conjugate of the transform ZN/2-k-1 are derived from z[n] for the expression




  
    G
    k
  
  =
  
    
      
        1
        2
      
      ⁡
      
        [
        
          
            Z
            k
          
          +
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
    +
    
      
        
          e
          ⁢
          
            
              x
              ⁡
              
                (
                
                  
                    2
                    ⁢
                    k
                  
                  +
                  1
                
                )
              
            
            N
          
        
        
          2
          ⁢
          
            
          
          ⁢
          j
        
      
      ⁡
      
        [
        
          
            Z
            k
          
          -
          
            Z
            
              
                N
                2
              
              -
              k
              -
              1
            
          
        
        ]
      
    
  




where Gk is a transform coefficient sequence which allows the MDCT to be evaluated, in that




  
    G
    k
  
  =
  
    
      
        g
        
          k
          ,
          r
        
      
      +
      
        j
        ⁢
        
          
        
        ⁢
        
          g
          
            k
            ,
            i
          
        
      
    
    =
    
      
        ∑
        
          n
          =
          0
        
        
          n
          =
          
            N
            -
            1
          
        
      
      ⁢
      
        
          (
          
            
              x
              ⁡
              
                [
                n
                ]
              
            
            ⁢
            
              e
              
                j
                ⁢
                
                  
                
                ⁢
                
                  xn
                  /
                  N
                
              
            
          
          )
        
        *
        
          e
          
            j
            ⁢
            
              
            
            ⁢
            2
            ⁢
            
              xnk
              /
              N
            
          
        
      
    
  




which can be used to solve the MDCT when rewritten as




  
    X
    k
  
  =
  
    
      
        cos
        ⁢
        
          
        
        ⁢
        
          γ
          ⁡
          
            (
            k
            )
          
        
        ⁢
        
          
            
              1
              /
              2
            
            ⁢
            
              (
              
                
                  
                    e
                    
                      j
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                /
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                    
                  
                  ⁢
                  
                    G
                    k
                  
                
                +
                
                  
                    e
                    
                      
                        -
                        j
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                /
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                    
                  
                  ⁢
                  
                    G
                    k
                    *
                  
                
              
              )
            
          
          
            }
            
              T
              1
            
          
        
      
      -
      
        sin
        ⁢
        
          
        
        ⁢
        
          γ
          ⁡
          
            (
            k
            )
          
        
        ⁢
        
          
            
              1
              /
              2
            
            ⁢
            
              j
              ⁡
              
                (
                
                  
                    
                      e
                      
                        j
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                    
                  
                  -
                  
                    
                      e
                      
                        
                          -
                          j
                        
                        ⁢
                        
                          
                        
                        ⁢
                        
                          
                            π
                            ⁡
                            
                              (
                              
                                k
                                +
                                
                                  1
                                  /
                                  2
                                
                              
                              )
                            
                          
                          /
                          N
                        
                      
                    
                    ⁢
                    
                      G
                      k
                      *
                    
                  
                
                )
              
            
          
          }
        
      
    
    =
    
      
        cos
        ⁢
        
          
        
        ⁢
        γ
        *
        
          
            (
            
              
                
                  g
                  
                    k
                    ,
                    r
                  
                
                ⁢
                
                  cos
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      /
                      N
                    
                    )
                  
                
              
              -
              
                
                  g
                  
                    k
                    ,
                    i
                  
                
                ⁢
                
                  sin
                  ⁡
                  
                    (
                    
                      
                        π
                        ⁡
                        
                          (
                          
                            k
                            +
                            
                              1
                              ⁢
                              
                                /
                              
                              ⁢
                              2
                            
                          
                          )
                        
                      
                      /
                      N
                    
                    )
                  
                
              
            
          
          
            }
            
              T
              1
            
          
        
      
      -
      
        sin
        ⁢
        
          
        
        ⁢
        γ
        *
        
          
            
              (
              
                
                  
                    g
                    
                      k
                      .
                      r
                    
                  
                  ⁢
                  
                    sin
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
                +
                
                  
                    g
                    
                      k
                      ,
                      i
                    
                  
                  ⁢
                  
                    cos
                    ⁡
                    
                      (
                      
                        
                          π
                          ⁡
                          
                            (
                            
                              k
                              +
                              
                                1
                                ⁢
                                
                                  /
                                
                                ⁢
                                2
                              
                            
                            )
                          
                        
                        /
                        N
                      
                      )
                    
                  
                
              
            
            
              }
              
                T
                w
              
            
          
          .