Patent Publication Number: US-8126950-B2

Title: Method for performing a domain transformation of a digital signal from the time domain into the frequency domain and vice versa

Description:
CROSS REFERENCE TO RELATED APPLICATIONS 
     This application claims the benefit of priority of U.S. Provisional Application No. 60/507,210, filed 29 Sep. 2003, and U.S. Provisional Application No. 60/507,440, filed 29 Sep. 2003, the contents of each being hereby incorporated by reference in its entirety for all purposes. 
     Further, the following commonly-owned applications are concurrently-filed herewith, and herein incorporated in its entirety:
         “Method for Transforming a Digital Signal form the Time Domain into the Frequency Domain and Vice Versa,” Ser. No. 10/573,953, and   “Process and Device for Determining a Transforming Element for a Given Transformation Function, Method and Device for Transforming a Digital Signal from the Time Domain into the Frequency Domain and vice versa and Computer Readable Medium,” Ser. No. 10/573,955.       

    
    
     BACKGROUND 
     This invention relates generally to digital signal processing, and in particular to systems and methods for performing domain transformations of digitally-formatted signals. 
     Domain transformations, for example the discrete cosine transform (DCT), are widely used in modern signal processing industry. Recently, a variant of the DCT, called integer DCT, has attracted a lot of re-search interests because of its important role in lossless coding applications. The term “lossless” means that the decoder can generate an exact copy of the source signal from the encoded bit-stream. 
     The DCT is a real-valued block transform. Even if the input block consists only of integers, the output block of the DCT can comprise non-integer components. For convenience, the input block is referred to as input vector and the output block as output vector. If a vector comprises only integer components, it is called an integer vector. In contrast to the DCT, the integer DCT generates an integer output vector from an integer input vector. For the same integer input vector, the integer output vector of integer DCT closely approximates the real output vector of DCT. Thus the integer DCT keeps all the good properties of the DCT in spectrum analysis. 
     An important property of the integer DCT is reversibility. Reversibility means that there exists an integer inverse DCT (IDCT) so that if the integer DCT generates an output vector y from an input vector x, the integer IDCT can recover the vector x from the vector y. Sometimes the integer DCT is also referred to as the forward transform, and the integer IDCT as the backward or inverse transform. 
     A transform called integer modified discrete cosine transform (IntMDCT) is recently proposed and used in the ISO/IEC MPEG-4 audio compression. The IntMDCT can be derived from its prototype—the modified discrete cosine transform (MDCT). The disclosure by H. S. Malvar in “Signal Processing with Lapped Transforms”  Artech House,  1992 provides an efficient realization of MDCT by cascading a bank of Givens rotations with a DCT-IV block. It is well known that Givens rotation can be factorised into three lifting steps for mapping integers to integers. See e.g., R. Geiger, T. Sporer, J. Koller, K. Brandenburg, “Audio Coding based on Integer Transforms” AES 111 th  Convention, New York, USA, September 2001. Integer transforms can be directly converted from their prototypes by replacing each Givens rotation with three lifting steps. Because in each lifting step there is one rounding operation, the total rounding number of an integer transform is three times the Givens rotation number of the prototype transform. For discrete trigonometric transforms (for example the Discrete Fourier Transform (DFT) or the Discrete Cosine Transform (DCT)), the number of Givens rotations involved is usually at N log 2 N level, where N is the size of the blocks, i.e. the amount of data symbols included in each block, the digital signal is divided into. Accordingly, the total rounding number is also at N log 2 N level for the family of directly converted integer transforms. Because of the roundings, an integer transform only approximates its floating-point prototype. The approximation error increases with the number of roundings. 
     What is therefore needed is a method and system implementation for performing domain transformations using fewer rounding operations, thereby resulting in more accurate and less computationally intensive transformations. 
     SUMMARY OF THE INVENTION 
     The invention solves the problem of providing a method for performing a domain transformation of a digital signal from the time domain into the frequency domain and vice versa which comprises a significantly reduced number of rounding operations. 
     In one embodiment of the invention, a method for performing a domain transformation of a digital signal from the time domain into the frequency domain and vice versa includes performing the transformation by a transforming element which includes a plurality of lifting stages, wherein the transformation corresponds to a transformation matrix. At least one lifting stage includes at least one auxiliary transformation matrix, which is the transformation matrix itself or the respective transformation matrix of lower dimension. Further, each lifting stage includes a rounding unit. The method further includes processing the signal by the respective rounding unit after the transformation by the respective auxiliary transformation matrix. 
     In the technique as described below, a computer readable medium having a program recorded thereon is used, wherein the program is adapted to make a computer perform the method of the embodiments. The computer readable medium may be any data storage device that can store data as a program which can be thereafter read by a computer system. Examples of the computer readable medium include read-only memory, random access memory, CD-ROMs, magnetic tapes, floppy disks and optical data storage devices. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  shows the architecture of an audio encoder according to an embodiment of the invention; 
         FIG. 2  shows the architecture of an audio decoder according to an embodiment of the invention, which corresponds to the audio coder shown in  FIG. 1 ; 
         FIG. 3  shows a flow chart of an embodiment of the method according to the invention; 
         FIG. 4  illustrates an embodiment of the method according to the invention using DCT-IV as the transformation function; 
         FIG. 5  illustrates the algorithm for the reverse transformation according to the embodiment of the method according to the invention illustrated in  FIG. 4 ; 
         FIG. 6  shows a flow chart of an embodiment of the method according to the invention; 
         FIG. 7  illustrates an embodiment of the method according to the invention using DCT-IV as the transformation function; 
         FIG. 8  illustrates the algorithm for the reverse transformation according to the embodiment of the method according to the invention illustrated in  FIG. 7 ; 
         FIG. 9  shows the architecture for an image archiving system according to an embodiment of the invention; 
         FIG. 10  illustrates an embodiment of the method according to the invention using DWT-IV as the transformation function; 
         FIG. 11  illustrates the algorithm for the reverse transformation according to the embodiment of the method according to the invention illustrated in  FIG. 10 ; 
         FIG. 12  illustrates a method for performing a domain transformation of a digital signal in accordance with one embodiment of the invention; 
         FIG. 13  shows forward and reverse transform coders used to assess the transform accuracy of presented DCT and FFT transformation methods in accordance with the present invention. 
     
    
    
     DETAILED DESCRIPTION OF SPECIFIC EMBODIMENTS 
       FIG. 12  illustrates a method for performing a domain transformation of a digital signal in accordance with one embodiment of the present invention. Initially at  1210 , a transformation of the digital signal is performed by a transforming element comprising a plurality of lifting stages. The transformation corresponds to a transformation matrix wherein at least one of the lifting stages comprises an auxiliary transformation matrix and a rounding unit, the auxiliary matrix comprising the transformation matrix itself of the corresponding transformation matrix of lower dimension. Exemplary embodiments of the process  1210  and domain transformation which can be used in the domain transformation are further described below. 
     Next at  1220 , a rounding operation of the signal is performed by the rounding unit after the transformation by the auxiliary matrix. 
     According to preferred embodiments of the method according to the invention, the data symbols of the digital signal are provided to the transforming element as a data vector. In each lifting stage, the data vector or a part of the data vector is transformed by a domain transformer, and the result of the transformation is rounded subsequently to an integer vector. This is in contrast to any method according to the state of the art, wherein the rounding process is performed within the transformation process for the individual element or data symbol in each block of the digital signal. Thus, the number of rounding operations in the method according to the invention is greatly reduced. Due to the reduced number of rounding operations, the method according to the invention does not require large computation time and computer resource. Further, the approximation error of integer domain transformations can be significantly reduced. 
     In a preferred embodiment, the invention provides a method for realizing the integer type-IV DCT transformation. The method according to the invention requires a significantly reduced number of rounding operations compared to prior art methods. As a result, the approximation error is greatly reduced, in the case of DCT-IV it can be reduced from the usual N log 2 N level to be as low as 1.5N in one embodiment and as low as 2.5N in another embodiment, where N denotes the block size of the digital signal. The method according to the invention is low in computational complexity and modular in structure. 
     The method and the device according to the invention can be used for any types of digital signals, such as audio, image or video signals. The digital signal, which is a digitised signal, corresponds to a physical measured signal, may be generated by scanning at least one characteristic feature of a corresponding analog signal (for example, the luminance and chrominance values of a video signal, the amplitude of an analog sound signal, or the analog sensing signal from a sensor). The digital signal comprises a plurality of data symbols. The data symbols of the digital signal are grouped into blocks, with each block having the same predefined number of data symbols based on the sampling rate of the corresponding analog signal. 
     The method according to the invention can be used for transforming an input digital signal which represents integer values to an output signal which also represents integer values. The transformation method according to the invention is reversible. The output signal may be transformed back to the original input signal by performing the transformation method according to the invention. Such a reversibility property of the transformation according to the method of the invention can be used in lossless coding in which the output signal should be identical to the original input signal. 
     Such an integer transformation of signals according to the invention can be used in many applications and systems such as MPEG audio, image and video compression, JPEG2000 or spectral analyzers (for analyzing Infrared, Ultra-violet or Nuclear Magnetic Radiation signals). It can also be easily implemented in hardware systems such as in a fixed-point Digital Signal Processor (DSP), without having to consider factors such as overflow in the case of a real-value signal transformation. 
     A preferred embodiment of the invention described below is suitable for both mono and stereo applications. In mono applications, two consecutive blocks of samples are grouped and processed together. This introduces signal delay of one block length when compared to single-block processing. However, in stereo applications, this extra block delay can be prevented, if simultaneous sample blocks from the left and the right channel are grouped and processed together. 
     According to the method according to the invention, the digital signal is transformed to the frequency domain by a transforming element. 
     Preferably, the transforming element comprises a plurality of lifting stages. 
     The transforming element can be illustrated based on the model of a lifting ladder. The lifting ladder model has two side pieces, each for receiving one of two groups of data symbols. Two or more cascading lifting stages are provided between the two side pieces. Each lifting stage receives a signal at one end (input end), and outputs a signal at the other end (output end) via a summation unit. A rounding unit is arranged at the output end. The lifting stages are arranged between the side pieces in an alternating manner, such that the output (or input) ends of adjacent lifting stages are connected to the different side pieces. 
     It should be noted that although the transforming element is described in the form of the lifting ladder model, it is only to illustrate the transformation paths of the transforming element. However, the invention shall not be limited to said ladder model. 
     Discrete cosine transforms, discrete sine transforms, discrete Fourier transforms or discrete W transforms are examples of transformations that may be performed by the method according to the invention. 
     In one aspect of the invention, each lifting stage corresponds to a lifting matrix which is a block-triangular matrix comprising four sub-matrices, with two invertible integer matrices in one diagonal. An example of a lifting matrix is: 
                   [             P   ⁢           ⁢     2   N       _         0               C   N   IV     _             P   ⁢           ⁢     1   N       _           ]           (   1   )               
wherein C N   IV  is the transformation function matrix, in this case the DCT-IV transformation matrix, and P1 N  and P2 N  are permutation matrices. A permutation matrix is a matrix which changes the position of the elements in another matrix. The permutation matrices may also be identical. The invertible integer matrices may also be arranged in the lifting matrix in another way, for example as
 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           
                             
                               P 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 1 
                                 N 
                               
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               P 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 2 
                                 N 
                               
                             
                             _ 
                           
                         
                         
                           
                             
                               C 
                               N 
                               IV 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   . 
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
     Preferably, the invertible integer matrices are diagonal matrices which comprise only components which are one or minus one. 
       FIG. 1  shows the architecture of an audio encoder  100  according to an embodiment of the invention. The audio encoder  100  comprises a conventional perceptual base layer coder based on the modified discrete cosine transform (MDCT) and a lossless enhancement coder based on the integer modified discrete cosine transform (IntMDCT). 
     An audio signal  109  which, for instance, is provided by a microphone  110  and which is digitalized by a analog-to-digital converter  111  is provided to the audio encoder  100 . The audio signal  109  comprises a plurality of data symbols. The audio signal  109  is divided into a plurality of blocks, wherein each block comprises a plurality of data symbols of the digital signal and each block is transformed by a modified discrete cosine transform (MDCT) device  101 . The MDCT coefficients are quantized by a quantizer  103  with the help of a perceptual model  102 . The perceptual model controls the quantizer  103  in such a way that the audible distortions resulting from the quantization error are low. The quantized MDCT coefficients are subsequently encoded by a bitstream encoder  104  which produces the lossy perceptually coded output bitstream  112 . 
     The bitstream encoder  104  losslessly compresses its input to produce an output which has a lower average bit-rate than its input by standard methods such as Huffman-Coding or Run-Length-Coding. The input audio signal  109  is also fed into an IntMDCT device  105  which produces IntMDCT coefficients. The quantized MDCT coefficients, which are the output of the quantizer  103 , are used to predict the IntMDCT coefficients. The quantized MDCT coefficients are fed into an inverse quantizer  106  and the output (restored or non-quantized MDCT coefficients) is fed into a rounding unit  107 . 
     The rounding unit rounds to an integer value MDCT coefficients, and the residual IntMDCT coefficients, which are the difference between the integer value MDCT and the IntMDCT coefficients, are entropy coded by an entropy coder  108 . The entropy encoder, analogous to the bitstream encoder  104 , losslessly reduces the average bit-rate of its input and produces a lossless enhancement bitstream  113 . The lossless enhancement bit stream  113  together with the perceptually coded bitstream  112 , carries the necessary information to reconstruct the input audio signal  109  with minimal error. 
       FIG. 2  shows the architecture of an audio decoder  200  comprising an embodiment of the invention, which corresponds to the audio coder  100  shown in  FIG. 1 . The perceptually coded bitstream  207  is supplied to a bitstream decoder  201 , which performs the inverse operations to the operations of the bitstream encoder  104  of  FIG. 1 , producing a decoded bitstream. The decoded bitstream is supplied to an inverse quantizer  202 , the output of which (restored MDCT coefficients) is supplied to the inverse MDCT device  203 . Thus, the reconstructed perceptually coded audio signal  209  is obtained. 
     The lossless enhancement bitstream  208  is supplied to an entropy decoder  204 , which performs the inverse operations to the operations of the entropy encoder  108  of  FIG. 1  and which produces the corresponding residual IntMDCT coefficients. The output of the inverse quantizer  202  is rounded by a rounding device  205  to produce integer value MDCT coefficients. The integer value MDCT coefficients are added to the residual IntMDCT coefficients, thus producing the IntMDCT coefficients. Finally, the inverse IntMDCT is applied to the IntMDCT coefficients by an inverse IntMDCT device  206  to produce the reconstructed losslessly coded audio signal  210 . 
       FIG. 3  shows a flow chart  300  of an embodiment of the method according to the invention using the DCT-IV as a transformation and using three lifting stages, a first lifting stage  301 , a second lifting stage  302  and a third lifting stage  303 . This method is preferably used in the IntMDCT device  105  of  FIG. 1  and the inverse IntMDCT device  206  of  FIG. 2  to implement IntMDCT and inverse IntMDCT, respectively. In  FIG. 3 , x 1  and x 2  are first and second blocks of the digital signal, respectively. z is an intermediate signal, and y 1  and y 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
     As explained above, the DCT-IV-algorithm plays an important role in lossless audio coding. 
     The transformation function of the DCT-IV comprises the transformation matrix C N   IV . According to this embodiment of the invention, the transforming element corresponds to a block-diagonal matrix comprising two blocks, wherein each block comprises the transformation matrix C N   IV . 
     So, in this embodiment, the matrix corresponding to the transforming element is: 
     
       
         
           
             
               
                 
                   [ 
                   
                     
                       
                         
                             
                         
                       
                       
                         
                           
                             C 
                             N 
                             IV 
                           
                           _ 
                         
                       
                     
                     
                       
                         
                           
                             C 
                             N 
                             IV 
                           
                           _ 
                         
                       
                       
                         
                             
                         
                       
                     
                   
                   ] 
                 
               
               
                 
                   ( 
                   3 
                   ) 
                 
               
             
           
         
       
     
     C N   IV  shall in the context of this embodiment be referred to as the transformation matrix henceforth. 
     The number of lifting matrices, and hence the number of lifting stages in the transformation element, in this embodiment of the invention, wherein DCT-IV is the transformation function, is three. 
     The DCT-IV of an N-point real input sequence x(n) is defined as follows: 
     
       
         
           
             
               
                 
                   
                     
                       y 
                       ⁡ 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           2 
                           N 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             x 
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             cos 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   
                                     ( 
                                     
                                       m 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       n 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 N 
                               
                               ) 
                             
                           
                           ⁢ 
                           m 
                         
                       
                     
                   
                   , 
                   
                     n 
                     = 
                     0 
                   
                   , 
                   1 
                   , 
                   ⋯ 
                   , 
                   
                     N 
                     - 
                     1 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
     Let C N   IV  be the transformation matrix of DCT-IV, that is 
     
       
         
           
             
               
                 
                   
                     
                       C 
                       N 
                       IV 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         
                           2 
                           N 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           cos 
                           ⁡ 
                           
                             ( 
                             
                               
                                 
                                   ( 
                                   
                                     m 
                                     + 
                                     
                                       1 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     n 
                                     + 
                                     
                                       1 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 π 
                               
                               N 
                             
                             ) 
                           
                         
                         ] 
                       
                     
                     
                       m 
                       , 
                       
                         n 
                         = 
                         0 
                       
                       , 
                       1 
                       , 
                       ⋯ 
                       , 
                       
                         N 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   5 
                   ) 
                 
               
             
           
         
       
     
     The following relation holds for the inverse DCT-IV matrix: 
     
       
         
           
             
               
                 
                   
                     
                       ( 
                       
                         
                           C 
                           N 
                           IV 
                         
                         _ 
                       
                       ) 
                     
                     
                       - 
                       1 
                     
                   
                   = 
                   
                     
                       C 
                       N 
                       IV 
                     
                     _ 
                   
                 
               
               
                 
                   ( 
                   6 
                   ) 
                 
               
             
           
         
       
     
     With x=[x(n)] n=0, 1, . . . , N−1  and y=[y(m)] m=0, 1, . . . , N−1 , equation (4) can be expressed as
 
y=C N   IV x  (7)
 
     Now, let x 1 , x 2  be two integer N×1 column vectors. The column vectors x 1 , x 2  correspond to two blocks of the digital signal which, according to the invention, are transformed by one transforming element. The DCT-IV transforms of x 1 , x 2  are y 1 , y 2 , respectively.
 
y 1 =C N   IV x 1   (8)
 
y 2 =C N   IV x 2   (9)
 
     Combining (8) and (9): 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               y 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               y 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               
                                 C 
                                 N 
                                 IV 
                               
                               _ 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                               
                                 C 
                                 N 
                                 IV 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
           
         
       
     
     The above diagonal matrix is the block-diagonal matrix that the transforming element corresponds to. 
     It is within the scope of the invention if the above equation is changed by simple algebraic modifications like the one leading to 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               y 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               y 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                                 
                             
                           
                           
                             
                               
                                 C 
                                 N 
                                 IV 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 C 
                                 N 
                                 IV 
                               
                               _ 
                             
                           
                           
                             
                                 
                             
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
     Let T 2N  be the counter diagonal matrix in (11), that is 
     
       
         
           
             
               
                 
                   
                     
                       T 
                       
                         2 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         N 
                       
                     
                     _ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                               
                           
                         
                         
                           
                             
                               C 
                               N 
                               IV 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               C 
                               N 
                               IV 
                             
                             _ 
                           
                         
                         
                           
                               
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
     The matrix T 2N  can be factorised as follows: 
                       T     2   ⁢   N       _     =       [                         C   N   IV     _                 C   N   IV     _                       ]     =         [             I   N     _                           -       C   N   IV     _               I   N     _           ]     ⁡     [           -       I   N     _               C   N   IV     _                             I   N     _           ]       ⁡     [             I   N     _                             C   N   IV     _             I   N     _           ]                 (   13   )               
where I N  is the N×N identity matrix.
 
     Equation (13) can be easily verified using the DCT-IV property in (7). Using (13), Equation (11) can be expressed as 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               y 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               y 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     I 
                                     N 
                                   
                                   _ 
                                 
                               
                               
                                 
                                     
                                 
                               
                             
                             
                               
                                 
                                   - 
                                   
                                     
                                       C 
                                       N 
                                       IV 
                                     
                                     _ 
                                   
                                 
                               
                               
                                 
                                   
                                     I 
                                     N 
                                   
                                   _ 
                                 
                               
                             
                           
                           ] 
                         
                         ⁡ 
                         
                           [ 
                           
                             
                               
                                 
                                   - 
                                   
                                     
                                       I 
                                       N 
                                     
                                     _ 
                                   
                                 
                               
                               
                                 
                                   
                                     C 
                                     N 
                                     IV 
                                   
                                   _ 
                                 
                               
                             
                             
                               
                                 
                                     
                                 
                               
                               
                                 
                                   
                                     I 
                                     N 
                                   
                                   _ 
                                 
                               
                             
                           
                           ] 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   N 
                                 
                                 _ 
                               
                             
                             
                               
                                   
                               
                             
                           
                           
                             
                               
                                 
                                   C 
                                   N 
                                   IV 
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   I 
                                   N 
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
     The three lifting matrices in equation (14) correspond to the three lifting stages shown in  FIG. 3 . Each lifting matrix in (14) comprises the auxiliary matrix C N   IV , which is the transformation matrix itself. 
     From (14), the following integer DCT-IV algorithm that computes two integer DCT-IVs with one transforming element is derived. 
       FIG. 4  illustrates the embodiment of the method according to the invention using DCT-IV as the transformation function. This embodiment is used in the audio coder  100  shown in  FIG. 1  for implementing IntMDCT. Like in  FIG. 3 , x 1  and x 2  are two blocks of the input digital signal, z is an intermediate signal, and y 1  and y 2  are corresponding blocks of the output signal. 
     The three lifting stages illustrated in  FIG. 4  correspond to the three lifting matrices in equation (14). 
     As illustrated by  FIG. 4 , the time to frequency domain integer transform is determined by the following: 
     In the first stage  401 , x 2  is transformed by a DCT-IV transformation  402  and the DCT-IV coefficients are rounded  403 . The rounded DCT-IV coefficients are then added to x 1    404 . Thus, the intermediate signal z is generated. So, the intermediate signal z fulfils the equation:
 
 z=└C   N   IV   x   2   ┘+x   1   (15a)
 
     In the second stage  405 , z is transformed by a DCT-IV transformation  406  and the DCT-IV coefficients are rounded  407 . From the rounded DCT-IV coefficients X 2  is then subtracted. Thus, the output signal y 1  is generated. So, the output signal y 1  fulfils the equation:
 
 y   1   =└C   N   IV   z┘−x   2   (15b)
 
     In the third stage  409 , y 1  is transformed by a DCT-IV transformation  410  and the DCT-IV coefficients are rounded  411 . The rounded DCT-IV coefficients are then subtracted from z. Thus, the output signal y 2  is generated. So, the output signal y 2  fulfils the equation:
 
 y   2   =−└C   N   IV   y   1   ┘+z   (15c)
 
where └*┘ denotes rounding operation.
 
       FIG. 5  illustrates the algorithm for the reverse transformation according to an embodiment of the method according to the invention using DCT-IV as the transformation function. This embodiment is used in the audio decoder  200  shown in  FIG. 2  for implementing inverse IntMDCT. The algorithm illustrated in  FIG. 5  is the inverse of the algorithm illustrated in  FIG. 4 . The denotations for the different signals y 1 , y 2 , x 1 , x 2  and z are chosen corresponding to the denotations of  FIG. 4 . 
     As illustrated by  FIG. 5 , the frequency to time domain integer transform is determined by the following: 
     In the first stage  501 , y 1  is transformed by a DCT-IV transformation  502  and the DCT-IV coefficients are rounded  503 . The rounded DCT-IV coefficients are then added to y 2    504 . Thus, the intermediate signal z is generated. So, the intermediate signal z fulfils the equation:
 
 z=└C   N   IV   y   1   ┘+y   2   (16a)
 
     In the second stage  505 , z is transformed by a DCT-IV transformation  506  and the DCT-IV coefficients are rounded  507 . From the rounded DCT-IV coefficients y 1  is then subtracted. Thus, the signal x 2  is generated. So, the signal x 2  fulfils the equation:
 
 x   2   =└C   N   IV   z┘−y   1   (16b)
 
     In the third stage  509 , x 2  is transformed by a DCT-IV transformation  510  and the DCT-IV coefficients are rounded  511 . The rounded DCT-IV coefficients are then subtracted from z. Thus, the signal x 1  is generated. So, the signal x 1  fulfils the equation:
 
 x   1   =−└C   N   IV   x   2   ┘+z   (16c)
 
     It can be seen that the algorithm according to the equations (16a) to (16c) is inverse to the algorithm according to the equations (15a) to (15c). Thus, if used in the encoder and decoder illustrated in  FIGS. 1 and 2 , the algorithms provide a method and an apparatus for lossless audio coding. 
     The equations (15a) to (15c) and (16a) to (16c) further show that to compute two N×N integer DCT-IVs, three N×N DCT-IVs, three N×1 roundings, and three N×1 additions are needed. Therefore, for one N×N integer DCT-IV, the average is:
 
 RC ( N )=1.5 N   (17)
 
 AC ( N )=1.5 AC ( C   N   IV )+1.5 N   (18)
 
where RC(.) is the total rounding number, and AC(.) is the total number of arithmetic operations. Compared to the directly converted integer DCT-IV algorithms, the proposed integer DCT-IV algorithm reduces RC from level N log 2 N to N.
 
     As indicated by (18), the arithmetic complexity of the proposed integer DCT-IV algorithm is about 50 percent more than that of a DCT-IV algorithm. However, if RC is also considered, the combined complexity (AC+RC) of the proposed algorithm does not much exceed that of the directly converted integer algorithms. Exact analysis of the algorithm complexity depends on the DCT-IV algorithm used. 
     As shown in  FIGS. 4 and 5 , the proposed integer DCT-IV algorithm is simple and modular in structure. It can use any existing DCT-IV algorithms in its DCT-IV computation block. The proposed algorithm is suitable for applications that require IntMDCT, e.g. in the MPEG-4 audio extension 3 reference model 0. 
       FIG. 6  shows a flow chart  600  of an embodiment of the method according to the invention using five lifting stages, a first lifting stage  601 , a second lifting stage  602 , a third lifting stage  603 , a fourth lifting stage  604  and a fifth lifting stage  605 . This method can be used in the IntMDCT device  105  of  FIG. 1  and the inverse IntMDCT device  206  of  FIG. 2  to implement IntMDCT and inverse IntMDCT, respectively. In  FIG. 6 , x 1  and x 2  are first and second blocks of the digital signal, respectively. z 1 , Z 2 , z 3  are intermediate signals, and y 1  and y 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
       FIG. 7  shows a flow chart of an embodiment of the method according to the invention, wherein the transformation function is a DCT-IV transformation function. 
     The DCT-IV matrix C N   IV  (see equation (5)) can be factorised as
 
C N   IV =R po TP eo   (20)
 
where P eo  is an even-odd matrix, i.e., a permutation matrix reordering the components of the vector
 
               x   _     =     [           x   ⁡     (   0   )               ⋮             x   ⁡     (     N   -   1     )             ]           
by separating the components which correspond to even indices from the components which correspond to odd indices, i.e., such that
 
                     [             x   1     ⁡     (   0   )               ⋮               x   1     ⁡     (       N   2     -   1     )                   x   2     ⁡     (   0   )               ⋮               x   2     ⁡     (       N   2     -   1     )             ]     =         P   eo     _     ⁡     [           x   ⁡     (   0   )               ⋮             x   ⁡     (     N   -   1     )             ]               (   21   )               
where further
 
     
       
         
           
             
               
                 
                   
                     T 
                     _ 
                   
                   = 
                   
                     
                       
                         
                           T 
                           1 
                         
                         _ 
                       
                       ⁢ 
                       
                         
                           T 
                           2 
                         
                         _ 
                       
                       ⁢ 
                       
                         
                           T 
                           3 
                         
                         _ 
                       
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                             
                               
                                   
                               
                             
                           
                           
                             
                               
                                 
                                   K 
                                   1 
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                       · 
                       
                         [ 
                         
                           
                             
                               
                                 - 
                                 
                                   
                                     D 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                             
                             
                               
                                 
                                   K 
                                   2 
                                 
                                 _ 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                       · 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                             
                               
                                   
                               
                             
                           
                           
                             
                               
                                 
                                   K 
                                   3 
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   22 
                   ) 
                 
               
             
             
               
                 with 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       K 
                       1 
                     
                     _ 
                   
                   = 
                   
                     
                       - 
                       
                         ( 
                         
                           
                             
                               
                                 C 
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 IV 
                               
                               ⁢ 
                               
                                 D 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                             
                             _ 
                           
                           + 
                           
                             
                               2 
                             
                             ⁢ 
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                         ) 
                       
                     
                     ⁢ 
                     
                       
                         C 
                         
                           N 
                           / 
                           2 
                         
                         IV 
                       
                       _ 
                     
                   
                 
               
               
                 
                   ( 
                   23 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       K 
                       2 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         C 
                         
                           N 
                           / 
                           2 
                         
                         IV 
                       
                       _ 
                     
                     
                       2 
                     
                   
                 
               
               
                 
                   ( 
                   24 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       K 
                       3 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         2 
                       
                       ⁢ 
                       
                         
                           
                             C 
                             
                               N 
                               / 
                               2 
                             
                             IV 
                           
                           ⁢ 
                           
                             D 
                             
                               N 
                               / 
                               2 
                             
                           
                         
                         _ 
                       
                     
                     + 
                     
                       
                         I 
                         
                           N 
                           / 
                           2 
                         
                       
                       _ 
                     
                   
                 
               
               
                 
                   ( 
                   25 
                   ) 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       R 
                       po 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         
                           R 
                           1 
                         
                         _ 
                       
                       ⁢ 
                       
                         
                           R 
                           2 
                         
                         _ 
                       
                       ⁢ 
                       
                         
                           R 
                           3 
                         
                         _ 
                       
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                             
                               
                                   
                               
                             
                           
                           
                             
                               
                                 
                                   H 
                                   1 
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                       · 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   H 
                                   2 
                                 
                                 _ 
                               
                             
                           
                           
                             
                               
                                   
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                       · 
                       
                         [ 
                         
                           
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                             
                               
                                   
                               
                             
                           
                           
                             
                               
                                 
                                   H 
                                   3 
                                 
                                 _ 
                               
                             
                             
                               
                                 
                                   I 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   26 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       1 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         H 
                         3 
                       
                       _ 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               
                                 - 
                                 tan 
                               
                               ⁢ 
                               
                                 
                                   
                                     ( 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 
                                   8 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             ⋰ 
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                               
                                 - 
                                 tan 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   3 
                                   ⁢ 
                                   π 
                                 
                                 
                                   8 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 - 
                                 tan 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 π 
                                 
                                   8 
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   27 
                   ) 
                 
               
             
             
               
                 and 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       H 
                       2 
                     
                     _ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                             sin 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               π 
                               
                                 4 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 N 
                               
                             
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                             sin 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               
                                 3 
                                 ⁢ 
                                 π 
                               
                               
                                 4 
                                 ⁢ 
                                 N 
                               
                             
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           ⋰ 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                             sin 
                             ⁢ 
                             
                               
                                 
                                   ( 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   ) 
                                 
                                 ⁢ 
                                 π 
                               
                               
                                 4 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 N 
                               
                             
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   28 
                   ) 
                 
               
             
           
         
       
     
     Equation (20) can be further written as 
     
       
         
           
             
               
                 
                   
                     
                       C 
                       N 
                       IV 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         
                           R 
                           1 
                         
                         ⁢ 
                         
                           R 
                           2 
                         
                       
                       _ 
                     
                     ⁢ 
                     
                       S 
                       _ 
                     
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       
                         
                           T 
                           2 
                         
                         ⁢ 
                         
                           T 
                           3 
                         
                         ⁢ 
                         
                           P 
                           eo 
                         
                       
                       _ 
                     
                   
                 
               
               
                 
                   ( 
                   29 
                   ) 
                 
               
             
             
               
                 where 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     S 
                     _ 
                   
                   = 
                   
                     
                       
                         
                           R 
                           3 
                         
                         ⁢ 
                         
                           T 
                           1 
                         
                       
                       _ 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   H 
                                   3 
                                 
                                 _ 
                               
                               + 
                               
                                 
                                   K 
                                   1 
                                 
                                 _ 
                               
                             
                           
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   30 
                   ) 
                 
               
             
           
         
       
     
     The transforming element used in the embodiment illustrated in  FIG. 7  corresponds to the equation (29). Each lifting matrix S, T 2  and T 3  in (29) comprises the auxiliary matrix C N/2   IV , which is the transformation matrix itself. 
     The transforming element comprises five lifting stages which correspond to the five lifting matrices of equation (29). 
     Further, the transforming element comprises a data shuffling stage corresponding to the permutation matrix P eo . 
     In  FIG. 7 , the input of the first lifting stage are the two blocks of the digital signal x 1  and x 2 , z 1 , Z 2  and z 3  are intermediate signals and y 1  and y 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
     The input of the transforming element x and the two input blocks of the first lifting stage of the transforming element x 1  and x 2  fulfil the equation 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               x 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               x 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         P 
                         eo 
                       
                       _ 
                     
                     ⁢ 
                     
                       x 
                       _ 
                     
                   
                 
               
               
                 
                   ( 
                   31 
                   ) 
                 
               
             
           
         
       
     
     In the following, the first lifting stage  701  is explained, which is the lifting stage corresponding to the lifting matrix T 3 . 
     Let 
                   [             v   1     _                 v   2     _           ]           
be the output vector of the first lifting stage, for the time being without rounding to integer values, i.e.
 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               v 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               v 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         3 
                       
                       _ 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   32 
                   ) 
                 
               
             
           
         
       
     
     Using the definition of T 3  provided by equation (22), equation (29) is re-written as 
                     [             v   1     _                 v   2     _           ]     =       [           I     N   2                               K   3     _             I     N   2       _           ]     ⁡     [             x   1     _                 x   2     _           ]               (   33   )               
where
 
               I     N   2       _         
denotes the identity matrix of dimension N/2.
 
     Since in this embodiment, a reversible algorithm for integer DCT-IV in this provided, there is included a rounding to integer values. So, according to equation (30), in the first step  706  of the first lifting stage  701 , x 1  is multiplied by K 3 . The result of this multiplication is rounded to integer values in step  707 . The rounded values are then added to x 2  in step  708 . Thus, the intermediate signal z 1  fulfils the equation
 
 z   1   =└K   3   ·x   1   ┘+x   2   (34)
 
where └*┘ denotes rounding operation.
 
     Since the other four lifting stages  702 ,  703 ,  704 ,  705  of the transforming element illustrated in  FIG. 7 , which correspond to the matrices T 2 , S, R 2  and R 1  respectively, have identical structures as the first lifting stage  701 , their explanation is omitted. It only has to be noted that in the adding step  709  of the second lifting step  702 , x 1  is, according to the definition of T 2 , multiplied with −D N/2 . 
     In the following, the lifting stages of the transforming element of the reverse transformation are explained with reference to  FIG. 8 . 
       FIG. 8  illustrates the lifting stages of the transforming element for the reverse transformation of the transformation illustrated in  FIG. 7 . 
     In  FIG. 8 , the input of the first lifting stage are the two blocks of the digital signal y 1  and y 2 , z 1 , z 2  and z 3  are intermediate signals and x 1  and x 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
     The last lifting stage  805  illustrated in  FIG. 8  is inverse to the first lifting stage  701  illustrated in  FIG. 7 . So, in the first step  806  of the last lifting stage  805 , x 1  is multiplied by K 3 . The result of this multiplication is rounded to integer values in step  807 . The rounded values are then subtracted from z 1  in step  808 . Thus, the signal x 2  fulfils the equation
 
 x   2   =z   1   −└K   3   ·x   1 ┘  (35)
 
where └*┘ denotes rounding operation.
 
     Since the other four lifting stages  801 ,  802 ,  803 ,  804  of the transforming element illustrated in  FIG. 8 , which are inverse to the lifting stages  705 ,  704 ,  703  and  702  of the transforming element illustrated in  FIG. 7  respectively, have identical structures as the last lifting stage  805 , their explanation is omitted. It only has to be noted that after-the-adding step  809  of the fourth lifting step  804 , the result of the adding step  809  is multiplied with −D N/2  to produce x 1 . 
     It can be seen that the lifting stages  805 ,  804 ,  803 ,  802  and  801  of  FIG. 8  are inverse to the lifting stages  701  to  705  of  FIG. 7 , respectively. Since also the permutation of the input signal corresponding to the matrix P eo  can be reversed and an according data shuffling stage is comprised by the inverse transforming element, the provided method is reversible, thus, if used in the audio encoder  100  and the audio decoder  200  illustrated in  FIGS. 1 and 2 , providing a method and an apparatus for lossless audio coding. 
     An analysis of the number of roundings used in this embodiment is given at the end of the description of the invention. 
       FIG. 9  shows the architecture for an image archiving system according to an embodiment of the invention. 
     In  FIG. 9  an image source  901 , for instance a camera, provides an analog image signal. The image signal is processed by a analog-to-digital converter  902  to provide a corresponding digital image signal. The digital image signal is losslessy encoded by a lossless image encoder  903  which includes a transformation from the time domain to the frequency domain. In this embodiment, the time domain corresponds to the coordinate space of the image. The lossless coded image signal is stored in a storage device  904 , for example a hard disk or a DVD. When the image is needed, the losslessly coded image signal is fetched from the storage device  904  and provided to a lossless image decoder  905  which decodes the losslessly coded image signal and reconstructs the original image signal without any data loss. 
     Such lossless archiving of image signals is important, for example, in the case that the images are error maps of semiconductor wafers and have to be stored for later analysis. 
     In the following, a further embodiment of the method for the transformation of a digital signal from the time domain to the frequency domain and vice versa according to the invention is explained. This embodiment is preferably used in the lossless image encoder  903  and the lossless image decoder  905  of the image archiving system illustrated in  FIG. 9 . 
       FIG. 10  illustrates an embodiment of the method according to the invention using DWT-IV as the transformation function. 
     The DWT-IV of a N-point real input sequence x(n) is defined as follows: 
     
       
         
           
             
               
                 
                   
                     
                       y 
                       ⁡ 
                       
                         ( 
                         m 
                         ) 
                       
                     
                     = 
                     
                       
                         
                           2 
                           N 
                         
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             n 
                             = 
                             0 
                           
                           
                             N 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         
                           
                             x 
                             ⁡ 
                             
                               ( 
                               n 
                               ) 
                             
                           
                           ⁢ 
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   π 
                                   4 
                                 
                                 + 
                                 
                                   
                                     
                                       ( 
                                       
                                         m 
                                         + 
                                         
                                           1 
                                           / 
                                           2 
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                       ( 
                                       
                                         n 
                                         + 
                                         
                                           1 
                                           / 
                                           2 
                                         
                                       
                                       ) 
                                     
                                     ⁢ 
                                     2 
                                     ⁢ 
                                     π 
                                   
                                   N 
                                 
                               
                               ) 
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                       
                   
                   ⁢ 
                   
                     m 
                     , 
                     
                       n 
                       = 
                       0 
                     
                     , 
                     1 
                     , 
                     … 
                     ⁢ 
                     
                         
                     
                     , 
                     
                       N 
                       - 
                       1 
                     
                   
                 
               
               
                 
                   ( 
                   36 
                   ) 
                 
               
             
           
         
       
     
     The transformation matrix W N   IV  of DWT-IV is given by 
     
       
         
           
             
               
                 
                   
                     
                       W 
                       N 
                       IV 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         
                           2 
                           N 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           sin 
                           ⁡ 
                           
                             ( 
                             
                               
                                 π 
                                 4 
                               
                               + 
                               
                                 
                                   
                                     ( 
                                     
                                       m 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       n 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   2 
                                   ⁢ 
                                   π 
                                 
                                 N 
                               
                             
                             ) 
                           
                         
                         ] 
                       
                     
                     
                       m 
                       , 
                       
                         n 
                         = 
                         0 
                       
                       , 
                       1 
                       , 
                       … 
                       ⁢ 
                       
                           
                       
                       , 
                       
                         N 
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   37 
                   ) 
                 
               
             
           
         
       
     
     The DWT-IV matrix is factorised into the following form:
 
W N   IV =R N T N P N   (38)
 
     R N  is a N×N rotation matrix defined as 
     
       
         
           
             
               
                 
                   
                     
                       R 
                       N 
                     
                     _ 
                   
                   = 
                   
                     
                       1 
                       
                         2 
                       
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                           
                             
                               
                                 J 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               - 
                               
                                 
                                   J 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                 
                                 _ 
                               
                             
                           
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   39 
                   ) 
                 
               
             
           
         
       
     
     I N/2  is the identity matrix of order N/2. J N/2  is the counter identity matrix of order N/2, i.e., 
     
       
         
           
             
               
                 
                   
                     
                       J 
                       
                         N 
                         2 
                       
                     
                     _ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           ⋰ 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   40 
                   ) 
                 
               
             
           
         
       
     
     P N  is a N×N permutation matrix 
     
       
         
           
             
               
                 
                   
                     
                       P 
                       N 
                     
                     _ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             
                               I 
                               
                                 N 
                                 / 
                                 2 
                               
                             
                             _ 
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                             
                               J 
                               
                                 N 
                                 / 
                                 2 
                               
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   41 
                   ) 
                 
               
             
           
         
       
     
     T is a N×N matrix given by 
                     T   _     =       1     2       ⁡     [             C     N   /   2     IV     _           -       C     N   /   2     IV     _                     C     N   /   2     IV     ⁢     D     N   /   2         _               C     N   /   2     IV     ⁢     D     N   /   2         _           ]               (   42   )               
where C N/2   IV  is the DCT-IV matrix of order N/2, i.e., a corresponding transformation matrix of lower dimension.
 
     
       
         
           
             
               
                 
                   
                     
                       C 
                       
                         N 
                         / 
                         2 
                       
                       IV 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         
                           2 
                           
                             ( 
                             
                               N 
                               / 
                               2 
                             
                             ) 
                           
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           cos 
                           ⁡ 
                           
                             ( 
                             
                               
                                 
                                   ( 
                                   
                                     m 
                                     + 
                                     
                                       1 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   ( 
                                   
                                     n 
                                     + 
                                     
                                       1 
                                       / 
                                       2 
                                     
                                   
                                   ) 
                                 
                                 ⁢ 
                                 π 
                               
                               
                                 ( 
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 ) 
                               
                             
                             ) 
                           
                         
                         ] 
                       
                     
                     
                       m 
                       , 
                       
                         n 
                         = 
                         0 
                       
                       , 
                       1 
                       , 
                       
                           
                       
                       ⁢ 
                       … 
                       , 
                       
                         
                           N 
                           / 
                           2 
                         
                         - 
                         1 
                       
                     
                   
                 
               
               
                 
                   ( 
                   43 
                   ) 
                 
               
             
           
         
       
     
     D N/2  is an order N/2 diagonal matrix given by 
     
       
         
           
             
               
                 
                   
                     
                       D 
                       
                         N 
                         / 
                         2 
                       
                     
                     _ 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           ⋱ 
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   44 
                   ) 
                 
               
             
           
         
       
     
     R N  and T can further be factorised into a product of lifting matrices: 
     
       
         
           
             
               
                 
                   
                     
                       
                         T 
                         _ 
                       
                       = 
                       
                         
                           
                             
                               T 
                               1 
                             
                             ⁢ 
                             
                               T 
                               2 
                             
                             ⁢ 
                             
                               T 
                               3 
                             
                           
                           _ 
                         
                         = 
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       I 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                                 
                                   
                                       
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       K 
                                       1 
                                     
                                     _ 
                                   
                                 
                                 
                                   
                                     
                                       I 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                               
                             
                             ] 
                           
                           · 
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       D 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                                 
                                   
                                     
                                       K 
                                       2 
                                     
                                     _ 
                                   
                                 
                               
                               
                                 
                                   
                                       
                                   
                                 
                                 
                                   
                                     
                                       I 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                               
                             
                             ] 
                           
                           · 
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       I 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                                 
                                   
                                       
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       K 
                                       3 
                                     
                                     _ 
                                   
                                 
                                 
                                   
                                     
                                       I 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                     ⁢ 
                     
                       
 
                     
                     ⁢ 
                     where 
                   
                   ⁢ 
                   
                       
                   
                 
               
               
                 
                   ( 
                   45 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         K 
                         1 
                       
                       _ 
                     
                     = 
                     
                       
                         ( 
                         
                           
                             
                               2 
                             
                             ⁢ 
                             
                               I 
                               
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 _ 
                               
                             
                           
                           - 
                           
                             
                               
                                 C 
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 IV 
                               
                               ⁢ 
                               
                                 D 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                             
                             _ 
                           
                         
                         ) 
                       
                       ⁢ 
                       
                         
                           C 
                           
                             N 
                             / 
                             2 
                           
                           IV 
                         
                         _ 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         K 
                         2 
                       
                       _ 
                     
                     = 
                     
                       
                         - 
                         
                           
                             C 
                             
                               N 
                               / 
                               2 
                             
                             IV 
                           
                           _ 
                         
                       
                       
                         2 
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         
                           K 
                           3 
                         
                         _ 
                       
                       = 
                       
                         
                           
                             2 
                           
                           ⁢ 
                           
                             
                               
                                 C 
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 IV 
                               
                               ⁢ 
                               
                                 D 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                             
                             _ 
                           
                         
                         - 
                         
                           
                             I 
                             
                               N 
                               / 
                               2 
                             
                           
                           _ 
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     and 
                   
                 
               
               
                 
                     
                 
               
             
             
               
                 
                   
                     
                       
                         R 
                         N 
                       
                       _ 
                     
                     = 
                     
                       
                         
                           
                             R 
                             1 
                           
                           ⁢ 
                           
                             R 
                             2 
                           
                           ⁢ 
                           
                             R 
                             3 
                           
                         
                         _ 
                       
                       = 
                       
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                               
                                 
                                     
                                 
                               
                             
                             
                               
                                 
                                   
                                     H 
                                     1 
                                   
                                   _ 
                                 
                               
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                             
                           
                           ] 
                         
                         · 
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                               
                                 
                                   
                                     H 
                                     2 
                                   
                                   _ 
                                 
                               
                             
                             
                               
                                 
                                     
                                 
                               
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                             
                           
                           ] 
                         
                         · 
                         
                           [ 
                           
                             
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                               
                                 
                                     
                                 
                               
                             
                             
                               
                                 
                                   
                                     H 
                                     3 
                                   
                                   _ 
                                 
                               
                               
                                 
                                   
                                     I 
                                     
                                       N 
                                       / 
                                       2 
                                     
                                   
                                   _ 
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   where 
                 
               
               
                 
                   ( 
                   46 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         H 
                         1 
                       
                       _ 
                     
                     = 
                     
                       
                         
                           H 
                           3 
                         
                         _ 
                       
                       ⁢ 
                       
                         
                           
                             
                               = 
                               
                                 
                                   - 
                                   tan 
                                 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     ( 
                                     
                                       π 
                                       / 
                                       8 
                                     
                                     ) 
                                   
                                   · 
                                   
                                     
                                       J 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                     
                                     _ 
                                   
                                 
                               
                             
                           
                         
                         
                           
                             
                               = 
                               
                                 [ 
                                 
                                   
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                         - 
                                         0.414 
                                       
                                     
                                   
                                   
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                         - 
                                         0.414 
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                   
                                   
                                     
                                       
                                           
                                       
                                     
                                     
                                       ⋰ 
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                   
                                   
                                     
                                       
                                         - 
                                         0.414 
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                   
                                 
                                 ] 
                               
                             
                           
                         
                       
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   and 
                 
               
               
                 
                   ( 
                   47 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       H 
                       2 
                     
                     _ 
                   
                   = 
                   
                     
                       
                         sin 
                         ⁡ 
                         
                           ( 
                           
                             π 
                             / 
                             4 
                           
                           ) 
                         
                       
                       · 
                       
                         
                           J 
                           
                             N 
                             / 
                             2 
                           
                         
                         _ 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             0.707 
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             0.707 
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             ⋰ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             0.707 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   48 
                   ) 
                 
               
             
           
         
       
     
     Thus, equation (38) can be written in the form
 
C N   IV =R 1 R 2 R 3 T 1 T 2 T 3 P N   (49)
 
     The lifting matrices R 3  and T 1  can be aggregated to the lifting matrix S: 
     
       
         
           
             
               
                 
                   
                     S 
                     _ 
                   
                   = 
                   
                     
                       
                         
                           R 
                           3 
                         
                         ⁢ 
                         
                           T 
                           1 
                         
                       
                       _ 
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 
                                   H 
                                   3 
                                 
                                 _ 
                               
                               + 
                               
                                 
                                   K 
                                   1 
                                 
                                 _ 
                               
                             
                           
                           
                             
                               
                                 I 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   50 
                   ) 
                 
               
             
           
         
       
     
     From (49) and (50), the following factorisation formula for the DWT-IV matrix can be obtained:
 
C N   IV =R 1 R 2 S T 2 T 3 P N   (51)
 
     Equation (51) indicates that a transforming element for the integer DWT-IV transform can be used which comprises five lifting stages. Each lifting matrix S, T 2  and T 3  in (51) comprises the auxiliary matrix C N/2   IV  which is the transformation matrix itself. 
     Further, the transforming element comprises a data shuffling stage corresponding to the permutation matrix P N . The data shuffling stage rearranges the components order in each input data block. According to P N , the input data vector is rearranged in the following way: the first half of vector remains unchanged; the second half of vector is flipped, i.e.: 
     
       
         
           
             
               
                 
                   
                     
                       
                         P 
                         N 
                       
                       _ 
                     
                     ⁢ 
                     
                       x 
                       _ 
                     
                   
                   = 
                   
                     
                       
                         
                           P 
                           N 
                         
                         _ 
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               
                                 x 
                                 1 
                               
                             
                           
                           
                             
                               
                                 x 
                                 2 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 x 
                                 
                                   N 
                                   / 
                                   2 
                                 
                               
                             
                           
                           
                             
                               
                                 x 
                                 
                                   
                                     N 
                                     / 
                                     2 
                                   
                                   + 
                                   1 
                                 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 x 
                                 
                                   N 
                                   - 
                                   1 
                                 
                               
                             
                           
                           
                             
                               
                                 x 
                                 N 
                               
                             
                           
                         
                         ] 
                       
                     
                     = 
                     
                       [ 
                       
                         
                           
                             
                               x 
                               1 
                             
                           
                         
                         
                           
                             
                               x 
                               2 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               x 
                               
                                 N 
                                 / 
                                 2 
                               
                             
                           
                         
                         
                           
                             
                               x 
                               N 
                             
                           
                         
                         
                           
                             
                               x 
                               
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   N 
                                   ⁢ 
                                   
                                       
                                   
                                   - 
                                   
                                       
                                   
                                   ⁢ 
                                   1 
                                 
                               
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               x 
                               
                                 
                                   N 
                                   / 
                                   2 
                                 
                                 + 
                                 1 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   52 
                   ) 
                 
               
             
           
         
       
     
     In  FIG. 10 , the input of the first lifting stage are the two blocks of the digital signal x 1  and x 2 , z 1 , Z 2  and Z 3  are intermediate signals and y 1  and y 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
     The input of the transforming element x and the two input blocks of the first lifting stage of the transforming element x 1  and x 2  fulfil the equation 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               x 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               x 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         P 
                         N 
                       
                       _ 
                     
                     ⁢ 
                     
                       x 
                       _ 
                     
                   
                 
               
               
                 
                   ( 
                   53 
                   ) 
                 
               
             
           
         
       
     
     In the following, the first lifting stage  1001  is explained, which is the lifting stage corresponding to the lifting matrix T 3 . 
     Let 
               [             v   1     _                 v   2     _                 ]         
be the output vector of the first lifting stage, for the time being without rounding to integer values, i.e.
 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               v 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               v 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       
                         T 
                         3 
                       
                       _ 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   54 
                   ) 
                 
               
             
           
         
       
     
     Using the definition of T 3  provided by equation (45), equation (51) is re-written as 
     
       
         
           
             
               
                 
                   
                     [ 
                     
                       
                         
                           
                             
                               v 
                               1 
                             
                             _ 
                           
                         
                       
                       
                         
                           
                             
                               v 
                               2 
                             
                             _ 
                           
                         
                       
                     
                     ] 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               I 
                               
                                 N 
                                 2 
                               
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 K 
                                 3 
                               
                               _ 
                             
                           
                           
                             
                               
                                 I 
                                 
                                   N 
                                   2 
                                 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                     ⁡ 
                     
                       [ 
                       
                         
                           
                             
                               
                                 x 
                                 1 
                               
                               _ 
                             
                           
                         
                         
                           
                             
                               
                                 x 
                                 2 
                               
                               _ 
                             
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   55 
                   ) 
                 
               
             
           
         
       
     
     Since in this embodiment, a reversible algorithm for integer DWT-IV in this provided, there is included a rounding to integer values. So, according to equation (55), in the first step  1006  of the first lifting stage  1001 , x 1  is multiplied by K 3 . The result of this multiplication is rounded to integer values in step  1007 . The rounded values are then added to x 2  in step  1008 . Thus, the intermediate signal z 1  fulfils the equation
 
 z   1   =└K   3   ·x   1   ┘+x   2   (56)
 
where └e┘ denotes rounding operation.
 
     Since the other four lifting stages  1002 ,  1003 ,  1004 ,  1005  of the transforming element illustrated in  FIG. 10 , which correspond to the matrices T 2 , S, R 2  and R 1  respectively, have identical structures as the first lifting stage  1001 , their explanation is omitted. It only has to be noted that in the adding step  1009  of the second lifting step  1002 , x 1  is, according to the definition of T 2 , multiplied with D N/2 . 
     In the following, the lifting stages of the transforming element of the reverse transformation are explained with reference to  FIG. 11 . 
       FIG. 11  illustrates the lifting stages of the transforming element for the reverse transformation of the transformation illustrated in  FIG. 10 . 
     In  FIG. 11 , the input of the first lifting stage are the two blocks of the digital signal y 1  and y 2 , z 1 , z 2  and z 3  are intermediate signals and x 1  and x 2  are output signals corresponding to the first and second block of the digital signal, respectively. 
     The last lifting stage  1105  illustrated in  FIG. 11  is inverse to the first lifting stage  1001  illustrated in  FIG. 10 . So, in the first step  1106  of the last lifting stage  1105 , x 1  is multiplied by K 3 . The result of this multiplication is rounded to integer values in step  1107 . The rounded values are then subtracted from z 1  in step  1108 . Thus, the signal x 2  fulfils the equation
 
 x   2   =z   1   −└K   3   ·x   1 ┘  (57)
 
where └*┘ denotes rounding operation.
 
     Since the other four lifting stages  1101 ,  1102 ,  1103 ,  1104  of the transforming element illustrated in  FIG. 11 , which are inverse to the lifting stages  1005 ,  1004 ,  1003  and  1002  respectively, have identical structures as the last lifting stage  1105 , their explanation is omitted. It only has to be noted that after the adding step  1109  of the fourth lifting step  1104 , the result of the adding step  1109  is multiplied with D N/2  to produce x 1 . 
     It can be seen that the lifting stages  1105 ,  1104 ,  1103 ,  1102  and  1101  of  FIG. 11  are inverse to the lifting stages  1001  to  1005  of  FIG. 10 , respectively. Since also the permutation of the input signal corresponding to the matrix P N  can be reversed and an according data shuffling stage is comprised by the inverse transforming element, the whole provided method is reversible, thus, if used in the lossless image encoder  903  and the lossless image decoder  905  illustrated in  FIG. 9 , providing a method and an apparatus for lossless image coding. 
     Although in the explained embodiments, the embodiments of the method according to the invention for DCT-IV were used for audio coding and the embodiment of the method according to the invention for DWT-IV was used for image coding, the embodiments of the method according to the invention for DCT-IV can as well be used for image coding, the embodiment of the method according to the invention for DWT-IV can as well be used audio coding and all can be used as well for the coding of other digital signals, such as video signals. 
     Considering the equations (34) and (35) one sees that there are N/2 roundings in each lifting stage. Therefore, considering equation (26), one sees that the total rounding number for the transforming element for the embodiment of the DCT-IV algorithm illustrated in  FIGS. 7 and 8  according to the invention is five times N/2, that is 2.5N, which is significantly lower than N log 2 N according to the state of the art. 
     Again considering equation (29), one sees that the majority of computation power is used in the four N/2 point DCT-IV subroutines corresponding to a multiplication with C N/2   IV , when N is a large value, e.g. N=1024. Because the floating-point DCT-IV can be calculated using two half-length DCT-IV plus pre- and post-rotations, the arithmetic complexity of the proposed integer DCT-IV is roughly estimated to be twice that of the floating-point DCT-IV. 
     A similar conclusion can be drawn for the integer DWT-IV transformation function. 
     In the following, a further embodiment of the method for the transformation of a digital signal from the time domain to the frequency domain and vice versa according to the invention is explained. 
     In this embodiment of the present invention, the domain transformation is a DCT transform, whereby the block size N is some integer and where the input vector comprises two sub-vectors. 
     Let C N   II  be the N×N transform matrix of DCT (also called Type-II DCT): 
                           C   N   II     =         2   /   N       ⁡     [       k   m     ⁢     cos   ⁡     (       m   ⁡     (     n   +     1   /   2       )       ⁢     π   /   N       )         ]                   m   ,     n   =   0     ,   1   ,   ⋯   ⁢           ,     N   -   1                   (   58   )               where   ⁢     :                               k   m     =     {           1   /     2           if         m   =   0             1       if         m   ≠   0                     (   59   )               
and N is the transform size which can be a power of two, N=2 i  in one embodiment and i is an integer greater than zero. m and n are matrix indices.
 
     Let C N   IV  be the N×N transform matrix of type-IV DCT, as already defined above: 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           C 
                           N 
                           IV 
                         
                         = 
                         
                           
                             
                               2 
                               / 
                               N 
                             
                           
                           ⁡ 
                           
                             [ 
                             
                               cos 
                               ⁡ 
                               
                                 ( 
                                 
                                   
                                     ( 
                                     
                                       m 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     ( 
                                     
                                       n 
                                       + 
                                       
                                         1 
                                         / 
                                         2 
                                       
                                     
                                     ) 
                                   
                                   ⁢ 
                                   
                                     π 
                                     / 
                                     N 
                                   
                                 
                                 ) 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         m 
                         , 
                         
                           n 
                           = 
                           0 
                         
                         , 
                         1 
                         , 
                         ⋯ 
                         ⁢ 
                         
                             
                         
                         , 
                         
                           N 
                           - 
                           1 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   60 
                   ) 
                 
               
             
           
         
       
     
     As above, a plurality of lifting matrices will be used, which lifting matrices are in this embodiment 2N×2N matrices of the following form: 
                     L     2   ⁢           ⁢   N       =     [           ±     I   N             A   N               O   N           ±     I   N             ]             (   61   )               
where I N  is the N×N identity matrix, O N  is the N×N zero matrix, A N  is an arbitrary N×N matrix.
 
     For each lifting matrix L 2N , a lifting stage reversible integer to integer mapping is realized in the same way as the 2×2 lifting step described in the incorporated reference “Factoring Wavlet Transforms into Lifting Steps,”  Tech. Report , I. Daubechies and W. Sweldens, Bell Laboratories, Lucent Technologies, 1996. The only difference is that rounding is applied to a vector instead of a single variable. 
     In the above description of the other embodiments, it was already detailed how a lifting stage is realized for a lifting matrix, so the explanation of the lifting stages corresponding to the lifting matrices will be omitted in the following. 
     One sees that the transposition of L 2N , L 2N   T  is also a lifting matrix. 
     In this embodiment, the transforming element corresponds to a matrix, T 2N  which is defined as a 2N×2N matrix in the following way: 
     
       
         
           
             
               
                 
                   
                     T 
                     
                       2 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       N 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           
                             C 
                             N 
                             IV 
                           
                         
                         
                           
                             O 
                             N 
                           
                         
                       
                       
                         
                           
                             O 
                             N 
                           
                         
                         
                           
                             C 
                             N 
                             IV 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   62 
                   ) 
                 
               
             
           
         
       
     
     The decomposition of the matrix T 2N  into lifting matrices has the following form:
 
 T   2N   =P 3· L 8· L 7· L 6· P 2· L 5· L 4· L 3· L 2· L 1· P 1  (63)
 
     The matrices constituting the right hand side of the above equation will be explained in the following. 
     P1 is a first permutation matrix given by the equation 
                     P   ⁢           ⁢   1     =     [           O   N           D   N               J   N           O   N           ]             (   64   )               
where J N  is the N×N counter index matrix given by
 
                     J   N     =     [         0       0       0       1           0       0       1       0           0       ⋰       0       0           1       0       0       0         ]             (   65   )               
and D N  is a N×N diagonal matrix with diagonal element being 1 and −1 alternatively:
 
     
       
         
           
             
               
                 
                   
                     D 
                     N 
                   
                   = 
                   
                     [ 
                     
                       
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           
                             - 
                             1 
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           1 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           ⋱ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             - 
                             1 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   66 
                   ) 
                 
               
             
           
         
       
     
     P2 is a second permutation matrix, an example of which is generated by the following MATLAB script: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 Pd = eye(2*N); 
               
               
                   
                 for i = 2:2:N, 
               
               
                   
                   Pd(i,i) = 0; Pd(N+i,N+i) = 0; 
               
               
                   
                   Pd(i,N+i) = 1; Pd(N+i,i) = 1; 
               
               
                   
                 end 
               
               
                   
                 Peo = zeros(2*N); 
               
               
                   
                 for i = 1:N, 
               
               
                   
                   Peo(i,2*i−1) = 1; 
               
               
                   
                   Peo(i+N,2*i) = 1; 
               
               
                   
                 end 
               
               
                   
                 P2 = (Pd*Peo)′; 
               
               
                   
                   
               
            
           
         
       
     
     As an example, when N is 4, P2 is a 8×8 matrix given as 
     
       
         
           
             
               
                 
                   
                     P 
                     2 
                   
                   = 
                   
                     
                       
                         [ 
                         
                           
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       for 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       N 
                     
                     = 
                     4 
                   
                 
               
               
                 
                   ( 
                   67 
                   ) 
                 
               
             
           
         
       
     
     P3 is a third permutation matrix, an example of which is generated by the following MATLAB script: 
     
       
         
           
               
               
             
               
                   
                   
               
             
            
               
                   
                 P3 = zeros(2*N); 
               
               
                   
                 for i = 1:N, 
               
               
                   
                   P3(i,2*i−1) = 1; 
               
               
                   
                   P3(N2−i+1,2*i) = 1; 
               
               
                   
                 end 
               
               
                   
                   
               
            
           
         
       
     
     As an example, when N is 4, P3 is a 8×8 matrix given as 
     
       
         
           
             
               
                 
                   
                     P 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     3 
                   
                   = 
                   
                       
                   
                   ⁢ 
                   
                     
                       
                         [ 
                         
                           
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                           
                             
                               0 
                             
                             
                               1 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                             
                               0 
                             
                           
                         
                         ] 
                       
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       for 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       N 
                     
                     = 
                     4 
                   
                 
               
               
                 
                   ( 
                   68 
                   ) 
                 
               
             
           
         
       
     
     L1 is a first lifting matrix 
                     L   ⁢           ⁢   1     =     [           I   N           O   N               Z   ⁢           ⁢     1   N             I   N           ]             (   69   )               
where Z1 N  is a N×N counter diagonal matrix given as:
 
     
       
         
           
             
               
                 
                     
                   
                     
                       Z 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       
                         1 
                         N 
                       
                     
                     = 
                       
                     ⁢ 
                     
                       [ 
                       
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               - 
                               
                                 tan 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       π 
                                       / 
                                       8 
                                     
                                     ⁢ 
                                     N 
                                   
                                   ) 
                                 
                               
                             
                           
                         
                         
                           
                             0 
                           
                           
                             0 
                           
                           
                             
                               
                                 - 
                                 tan 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 ( 
                                 
                                   3 
                                   ⁢ 
                                   
                                     π 
                                     / 
                                     8 
                                   
                                   ⁢ 
                                   N 
                                 
                                 ) 
                               
                             
                           
                           
                             0 
                           
                         
                         
                           
                             0 
                           
                           
                             ⋰ 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                         
                           
                             
                               - 
                               
                                 tan 
                                 ⁡ 
                                 
                                   ( 
                                   
                                     
                                       ( 
                                       
                                         
                                           2 
                                           ⁢ 
                                           
                                               
                                           
                                           ⁢ 
                                           N 
                                         
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                     ⁢ 
                                     
                                       π 
                                       / 
                                       8 
                                     
                                     ⁢ 
                                     N 
                                   
                                   ) 
                                 
                               
                             
                           
                           
                             0 
                           
                           
                             0 
                           
                           
                             0 
                           
                         
                       
                       ] 
                     
                   
                 
               
               
                 
                   ( 
                   70 
                   ) 
                 
               
             
           
         
       
     
     L2 is a second lifting matrix: 
                     L   ⁢           ⁢   2     =     [           I   N           Z   ⁢           ⁢     2   N                 O   N           I   N           ]             (   71   )               
where Z2 N  is a N×N counter diagonal matrix given as:
 
     
       
         
           
             
               
                 
                   
                     Z 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       2 
                       N 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 
                                   ( 
                                   
                                     
                                       2 
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       N 
                                     
                                     - 
                                     1 
                                   
                                   ) 
                                 
                                 ⁢ 
                                 
                                   π 
                                   / 
                                   4 
                                 
                                 ⁢ 
                                 N 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           ⋰ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           
                             sin 
                             ⁡ 
                             
                               ( 
                               
                                 3 
                                 ⁢ 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   π 
                                   / 
                                   4 
                                 
                                 ⁢ 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             sin 
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 
                                   π 
                                   / 
                                   4 
                                 
                                 ⁢ 
                                 N 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   72 
                   ) 
                 
               
             
           
         
       
     
     L3 is a third lifting matrix: 
                     L   ⁢           ⁢   3     =     [           I   N           O   N               Z   ⁢           ⁢     3   N             I   N           ]             (   73   )               
where:
 
 Z 3 N =√{square root over (2)} C   N   IV   +I   N   +Z 1 N   (74)
 
     L4 is a fourth lifting matrix: 
                     L   ⁢           ⁢   4     =     [           -     I   N             Z   ⁢           ⁢     4   N                 O   N           I   N           ]             (   75   )               
where:
 
 Z 4 N   =C   N   IV /√{square root over (2)}  (76)
 
     L5 is a fifth lifting matrix: 
                     L   ⁢           ⁢   5     =     [           I   N           O   N               Z   ⁢           ⁢     5   N             I   N           ]             (   77   )               
where:
 
 Z 5 N =−(√{square root over (2)} C   N   IV   +I   N )  (78)
 
     L6 is a sixth lifting matrix: 
                     L   ⁢           ⁢   6     =     [           I   N           O   N               Z   ⁢           ⁢     6   N             I   N           ]             (   79   )               
where Z6 N  is a N×N counter diagonal matrix given as:
 
     
       
         
           
             
               
                 
                   
                     Z 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       6 
                       N 
                     
                   
                   = 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             tan 
                             ⁡ 
                             
                               ( 
                               
                                 π 
                                 / 
                                 8 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             tan 
                             ⁡ 
                             
                               ( 
                               
                                 π 
                                 / 
                                 8 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           ⋰ 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             tan 
                             ⁡ 
                             
                               ( 
                               
                                 π 
                                 / 
                                 8 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   80 
                   ) 
                 
               
             
           
         
       
     
     L7 is a seventh lifting matrix: 
                     L   ⁢           ⁢   7     =     [           I   N           Z   ⁢           ⁢     7   N                 O   N           I   N           ]             (   81   )               
where Z7 N  is a N×N counter diagonal matrix given as:
 
     
       
         
           
             
               
                 
                   
                     Z 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     
                       7 
                       N 
                     
                   
                   = 
                     
                   ⁢ 
                   
                     [ 
                     
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           
                             
                               - 
                               sin 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 π 
                                 / 
                                 4 
                               
                               ) 
                             
                           
                         
                       
                       
                         
                           0 
                         
                         
                           0 
                         
                         
                           ⋰ 
                         
                         
                           0 
                         
                       
                       
                         
                           0 
                         
                         
                           
                             - 
                             
                               sin 
                               ⁡ 
                               
                                 ( 
                                 
                                   π 
                                   / 
                                   4 
                                 
                                 ) 
                               
                             
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                       
                         
                           
                             
                               - 
                               sin 
                             
                             ⁢ 
                             
                                 
                             
                             ⁢ 
                             
                               ( 
                               
                                 π 
                                 / 
                                 4 
                               
                               ) 
                             
                           
                         
                         
                           0 
                         
                         
                           0 
                         
                         
                           0 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   82 
                   ) 
                 
               
             
           
         
       
     
     L8 is an eighth lifting matrix:
 
L8=L6  (83)
 
thus, resulting in the factorization as shown in (x):
 
 T   2N   =P 3· L 8· L 7· L 6· P 2· L 5· L 4· L 3· L 2· L 1· P 1  (84)
 
where P1, P2, and P3 are three permutation matrices. Lj, j from 1 to 8, are eight lifting matrices.
 
     The lifting matrices L3, L4 and L5 comprise an auxiliary transformation matrix, which is, in this case, the transformation matrix C N   IV  itself. 
     From Eq. (84), it is possible to compute the integer DCT for two input signals of dimension N×1. 
     As Eq. (84) provides a lifting matrix factorization which describes the DCT-IV transformation domain, its lifting matrices can be used in the manner shown herein to compute the domain transformation of an applied input signal. 
     The equation (84) can be derived in the following way. 
     The following decomposition can be derived using the disclosure from Wang, Zhongde, “On Computing the Discrete Fourier and Cosine Transforms”, IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-33, No. 4 October 1985: 
                                 C   N     I   ⁢           ⁢   V       =         (     B   N     )     T     ·       (     P   N     )     T     ·     [           C     N   /   2       I   ⁢           ⁢   I                                             S     N   /   2       I   ⁢           ⁢   I       _     _           ]     ·     T   N                   =         (     B   N     )     T     ·       (     P   N     )     T     ·     [           C     N   /   2       I   ⁢           ⁢   I                                         C     N   /   2       I   ⁢           ⁢   I             ]     ·     P     D   ⁢           ⁢   J       ·     T   N                       (   85   )               
is known, wherein S N/2   II  denotes the transformation matrix of the discrete sine transform of type 2,
 
               P     D   ⁢           ⁢   J       =     [         I                                     D   ·   J           ]           
P N  is a N×N permutation matrix given by
 
     
       
         
           
             
               
                 
                   
                     
                       
                           
                       
                       ⁢ 
                       
                         ( 
                         86 
                         ) 
                       
                     
                     ⁢ 
                     
                       
                           
                         
                           
 
                         
                         ⁢ 
                         
                           
                             
                               P 
                               N 
                             
                             _ 
                           
                           = 
                           
                             
                               
                                 [ 
                                 
                                   
                                     
                                       
                                         
                                           I 
                                           
                                             N 
                                             / 
                                             2 
                                           
                                         
                                         _ 
                                       
                                     
                                     
                                       
                                           
                                       
                                     
                                   
                                   
                                     
                                       
                                           
                                       
                                     
                                     
                                       
                                         
                                           J 
                                           
                                             N 
                                             / 
                                             2 
                                           
                                         
                                         _ 
                                       
                                     
                                   
                                 
                                 ] 
                               
                               ⁢ 
                               
                                 
 
                               
                               ⁢ 
                               
                                 
                                   T 
                                   N 
                                 
                                 _ 
                               
                             
                             = 
                           
                         
                           
                       
                       [ 
                       
                           
                       
                       ⁢ 
                       
                         
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 π 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               sin 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 π 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   3 
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               sin 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   3 
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             ⋰ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     ( 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                               sin 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     ( 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               
                                 - 
                                 sin 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     ( 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   
                                     ( 
                                     
                                       N 
                                       - 
                                       1 
                                     
                                     ) 
                                   
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             ⋰ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             ⋱ 
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                                 
                             
                           
                           
                             
                               
                                 - 
                                 sin 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   3 
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 
                                   3 
                                   ⁢ 
                                   π 
                                 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                         
                         
                           
                             
                               
                                 - 
                                 sin 
                               
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 π 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                                 
                             
                           
                           
                             
                               cos 
                               ⁢ 
                               
                                   
                               
                               ⁢ 
                               
                                 π 
                                 
                                   4 
                                   ⁢ 
                                   
                                       
                                   
                                   ⁢ 
                                   N 
                                 
                               
                             
                           
                         
                       
                       ] 
                     
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       
                         and 
                       
                     
                     
                       
                         
                           
                             B 
                             N 
                           
                           = 
                           
                             
                               1 
                               
                                 2 
                               
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   
                                     
                                       2 
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     1 
                                   
                                   
                                     
                                       - 
                                       1 
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     1 
                                   
                                   
                                     1 
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     ⋱ 
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     1 
                                   
                                   
                                     
                                       - 
                                       1 
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     1 
                                   
                                   
                                     1 
                                   
                                   
                                     
                                         
                                     
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                         
                                     
                                   
                                   
                                     
                                       2 
                                     
                                   
                                 
                               
                               ] 
                             
                           
                         
                       
                     
                   
                 
               
               
                 
                     
                 
               
             
           
         
       
     
     Equation (85) can be combined with the equation 
                     C   N     I   ⁢           ⁢   V       =       R     P   ⁢           ⁢   O       ·     [           C     N   /   2       I   ⁢           ⁢   V                                         C     N   /   2       I   ⁢           ⁢   V             ]     ·     R     P   ⁢           ⁢   R       ·     P   D     ·     P     E   ⁢           ⁢   O                 (   87   )               
wherein P EO  is an even-odd permutation matrix,
 
     
       
         
           
             
               
                 R 
                 pr 
               
               _ 
             
             = 
             
               
                 1 
                 
                   2 
                 
               
               ⁡ 
               
                 [ 
                 
                   
                     
                       
                         
                           I 
                           
                             N 
                             / 
                             2 
                           
                         
                         _ 
                       
                     
                     
                       
                         
                           I 
                           
                             N 
                             / 
                             2 
                           
                         
                         _ 
                       
                     
                   
                   
                     
                       
                         
                           I 
                           
                             N 
                             / 
                             2 
                           
                         
                         _ 
                       
                     
                     
                       
                         - 
                         
                           
                             I 
                             
                               N 
                               / 
                               2 
                             
                           
                           _ 
                         
                       
                     
                   
                 
                 ] 
               
             
           
         
       
     
     R PO  equals T N , 
     
       
         
           
             
               
                 P 
                 _ 
               
               D 
             
             = 
             
               [ 
               
                 
                   
                     
                       
                         I 
                         
                           N 
                           2 
                         
                       
                       _ 
                     
                   
                   
                     
                         
                     
                   
                 
                 
                   
                     
                         
                     
                   
                   
                     
                       
                         D 
                         
                           N 
                           2 
                         
                       
                       _ 
                     
                   
                 
               
               ] 
             
           
         
       
     
     After transposition equation (87) converts to 
     
       
         
           
             
               
                 
                   
                     
                       
                         
                           C 
                           
                             
                                 
                             
                             ⁢ 
                             N 
                           
                           
                             
                                 
                             
                             ⁢ 
                             IV 
                           
                         
                         = 
                         
                           
                             
                               ( 
                               
                                   
                               
                               ⁢ 
                               
                                 P 
                                 
                                   
                                       
                                   
                                   ⁢ 
                                   EO 
                                 
                               
                               ) 
                             
                             T 
                           
                           · 
                           
                             
                               ( 
                               
                                   
                               
                               ⁢ 
                               
                                 P 
                                 
                                   
                                       
                                   
                                   ⁢ 
                                   D 
                                 
                               
                               ) 
                             
                             T 
                           
                           · 
                           
                             R 
                             
                               
                                   
                               
                               ⁢ 
                               PR 
                             
                           
                           · 
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       C 
                                       
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           N 
                                           / 
                                           2 
                                         
                                       
                                       
                                         
                                             
                                         
                                         ⁢ 
                                         IV 
                                       
                                     
                                   
                                 
                                 
                                   
                                       
                                   
                                 
                               
                               
                                 
                                   
                                       
                                   
                                 
                                 
                                   
                                     
                                         
                                     
                                     ⁢ 
                                     
                                       C 
                                       
                                         
                                             
                                         
                                         ⁢ 
                                         
                                           N 
                                           / 
                                           2 
                                         
                                       
                                       
                                         
                                             
                                         
                                         ⁢ 
                                         IV 
                                       
                                     
                                   
                                 
                               
                             
                             ] 
                           
                           · 
                           
                             
                               ( 
                               
                                   
                               
                               ⁢ 
                               
                                 R 
                                 
                                   
                                       
                                   
                                   ⁢ 
                                   PO 
                                 
                               
                               ) 
                             
                             T 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                         
                           
                             
                               ( 
                               
                                 P 
                                 EO 
                               
                               ) 
                             
                             T 
                           
                           · 
                           
                             
                               ( 
                               
                                 P 
                                 D 
                               
                               ) 
                             
                             T 
                           
                           · 
                           
                             
                               1 
                               
                                 2 
                               
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   
                                     
                                       C 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                       IV 
                                     
                                   
                                   
                                     
                                       C 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                       IV 
                                     
                                   
                                 
                                 
                                   
                                     
                                       C 
                                       
                                         N 
                                         / 
                                         2 
                                       
                                       IV 
                                     
                                   
                                   
                                     
                                       - 
                                       
                                         C 
                                         
                                           N 
                                           / 
                                           2 
                                         
                                         IV 
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           · 
                           
                             
                               ( 
                               
                                 R 
                                 PO 
                               
                               ) 
                             
                             T 
                           
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   88 
                   ) 
                 
               
             
           
         
       
     
     The combination of (85) and (88) yields 
                                 [           C     N   /   2     II                                       C     N   /   2     II           ]     =             P   N     ·           ⁢     B   N     ·           ⁢       (     P   EO     )     T     ·           ⁢       1             ⁢     2         ⁡     [           C     N   /   2     IV           C     N   /   2     IV               C     N   /   2     IV           -     C     N   /   2     IV             ]       ·                   (     R   PO     )     T     ·           ⁢     T   N     ·           ⁢       (     P   DJ     )     T                         =       P   3     ·           ⁢     R   2     ·           ⁢     P   2     ·           ⁢       1             ⁢     2         ⁡     [           C     N   /   2     IV           C     N   /   2     IV               C     N   /   2     IV           -     C     N   /   2     IV             ]       ·           ⁢     R   1     ·           ⁢     P   1                     (   89   )                 
where
 
 P   1 =( P   DJ ) T  
 
 P   2 =( P   EO ) T ·( P   D ) T =( P   D   ·P   EO ) T  
 
P 3 =P N  
 
 R   1 =( R   PO ) T   ·T   N  
 
R 2 =B N  
 
from (89), equation (84) can be easily derived.
 
     In this embodiment, the computation of the domain transformation requires only 4N rounding operations, as will now be explained: 
     Let α(*) be the number of real additions, μ(*) be the number of real multiplications, and γ(*) be the number of real roundings, respectively. For the proposed IntDCT algorithm, one gets:
 
α(IntDCT)=11 N+ 3α(DCT-IV)
 
μ(IntDCT)=9 N+ 3μ(DCT-IV)
 
γ(IntDCT)=8 N  
 
     The above results are for two blocks of data samples, because the proposed IntDCT algorithm processes them together. Thus for one block of data samples, the numbers of calculations are halved, which are 
                             α   1     ⁡     (   IntDCT   )       =       5.5   ⁢   N     +     1.5   ⁢     α   ⁡     (     DCT   -   IV     )                           μ   1     ⁡     (   IntDCT   )       =       4.5   ⁢   N     +     1.5   ⁢     μ   ⁡     (     DCT   -   IV     )                           γ   1     ⁡     (   IntDCT   )       =     4   ⁢   N                   
where α 1 , μ 1 , and γ 1  are the number of real additions, number of real multiplications, and number of real roundings, for one block of samples, respectively.
 
     For DCT-IV calculation, the FFT-based algorithm described in the incorporated reference “Signal Processing with lapped Transforms,” H. S. Malvar, Norwood, Mass. Artech House, 1992, pp. 199-201 can be used, for which
 
α(DCT-IV)=1.5 N  log 2   N  
 
μ(DCT-IV)=0.5 N  log 2   N+N  
 
Consequently:
 
α 1 (IntDCT)=2.25 N  log 2   N+ 5.5 N  
 
μ 1 (IntDCT)=0.75 N  log 2   N+ 6 N  
 
     In the following, a further embodiment of the method for the transformation of a digital signal from the time domain to the frequency domain and vice versa according to the invention is explained. 
     In this embodiment a discrete fast fourier transform (FFT) is used as the domain transformation. 
     Let F be the N×N transform matrix of the normalized FFT 
                           F   =                 ⁢     1             ⁢   N           ⁡     [     exp   ⁢     (         -   j2π     ⁢           ⁢   mn               ⁢   N       )       ]         ⁢     
     ⁢   m   ,     n   =   0     ,   1   ,   …   ⁢           ,     N   -   1             (   91   )                 
where N is the transform size which is some positive integer and, in one embodiment, can be a power of two, N=2 i  and i is an integer greater than zero. m and n are matrix indices.
 
     Under this embodiment, a permutation matrix P of dimension N×N is a matrix which includes indices 0 or 1. After multiplying it with a N×1 vector (the matrix representation of the input signal), the order of elements in the vector are changed. 
     In this embodiment, lifting matrices are defined as 2N×2N matrices of the following form: 
                   L   =     [           P   1         A           O         P   2           ]             (   92   )               
where P 1  and P 2  are two permutation matrices, O is the N×N zero matrix, A is an arbitrary N×N matrix. For lifting matrix L, reversible integer to integer mapping is realized in the same way as the 2×2 lifting step in the aforementioned incorporated reference of I. Daubechies. As above, however, rounding is applied to a vector instead of a single variable. It is apparent that the transposition of L, L T  is also a lifting matrix.
 
     Further, let T be a 2N×2N transform matrix: 
     
       
         
           
             
               
                 
                   T 
                   = 
                   
                     [ 
                     
                       
                         
                           O 
                         
                         
                           F 
                         
                       
                       
                         
                           F 
                         
                         
                           O 
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   93 
                   ) 
                 
               
             
           
         
       
     
     Accordingly, the modified transform matrix T (and accordingly the domain transformation itself) can be expressed as the lifting matrix factorization: 
                   T   =       [         I       O               -   Q     ·   F         I         ]     ⁢               ⁢     ·     [           -   Q         F           O       I         ]         ·     [         I       O           F       I         ]                 (   94   )               
where I is the N×N identity matrix, and Q is a N×N permutation matrix given as:
 
                   Q   =     [         1         O       1   ×   N     -   1                 O     N   -     1   ×   1             J         ]             (   95   )               
and O 1×N-1  and O N-1×1  are row and column vectors of N−1 zeros respectively.
 
     J is the (N−1)×(N−1) counter index matrix given by 
     
       
         
           
             
               
                 
                   J 
                   = 
                   
                     [ 
                     
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           1 
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           
                               
                           
                         
                         
                           ⋰ 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                       
                         
                           1 
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                         
                           
                               
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   96 
                   ) 
                 
               
             
           
         
       
     
     In Eq. (96), blank space in the square bracket represents all zeros matrix elements. 
     The lifting matrices on the right hand side of equation (94) comprise an auxiliary transformation matrix, which is, in this case, the transformation matrix F itself. 
     A can be seen from Eq. (94), the lifting matrix factorization can be use to compute the integer FFT for two N×1 complex vectors using the methods as described herein. 
     Under this embodiment, the computation of the domain transformation requires only 3N rounding operations, as will now be explained: 
     Let:
         α(*) be the number of real additions,   μ(*) be the number of real multiplications, and   γ(*) be the number of real rounding operations,       

     respectively. 
     For the proposed IntFFT algorithm, we have
 
α(IntFFT)=6 N+ 3α(FFT)
 
μ(IntFFT)=3μ(FFT)
 
γ(IntFFT)=6 N  
 
     The above results are for two blocks of data samples, because the proposed IntFFT algorithm processes them together. Thus for one block of data samples, the numbers of calculations are halved, which are
 
α 1 (IntFFT)=3 N+ 1.5α(FFT)
 
μ 1 (IntFFT)=1.5μ(FFT)
 
γ 1 (IntFFT)=3 N  
 
where α 1 , μ 1 , and γ 1  are the number of real additions, number of real multiplications, and number of real rounding operations for one block of samples, respectively.
 
     For FFT calculation, the split-radix FFT (SRFFT) algorithm can be used, for which:
 
α(SRFFT)=3 N  log 2   N− 3 N+ 4
 
μ(SRFFT)= N  log 2   N− 3 N+ 4
 
Consequently, we have:
 
α 1 (IntFFT)=4.5 N  log 2   N− 1.5 N+ 6
 
μ 1 (IntFFT)=1.5 N  log 2   N− 4.5 N+ 6
 
       FIG. 13  shows forward and reverse transform coders used to assess the transform accuracy of the DCT transformation technique described above and the FFT domain transformation above. The test involved measuring the mean squared error (MSE) of the transform in accordance with the evaluation standards proposed by the MPEG-4 lossless audio coding group as described in “Coding of Moving Pictures and Audio: Work plan for Evaluation of Integer MDCT for FGS to Lossless Experimentation Framework,” ISO/IEC JTC 1/SC 29/WG 11 N5578 Pattaya, Thailand, March 2003 incorporated herein. 
     Specifically, the MSEs for IntDCT and integer inverse DCT (IntIDCT) are given as: 
                   MSE   =       1   K     ⁢       ∑     j   =   0       K   -   1       ⁢       1   N     ⁢       ∑     i   =   0       N   -   1       ⁢     e   i   2                     (   97   )               
where the error signal e is e f  for IntDCT, and e t  for IntIDCT as in  FIG. 1 . K is the total number of sample blocks used in the evaluation.
 
     The MSEs for IntFFT and integer inverse FFT (IntIFFT) are given as 
                   MSE   =       1   K     ⁢       ∑     j   =   0       K   -   1       ⁢       1   N     ⁢       ∑     i   =   0       N   -   1       ⁢            e   i          2                     (   98   )               
where the error signal e is e f  for IntFFT, and e t  for IntIFFT as in  FIG. 1 . ∥*∥ represents norm of a complex value. K is the total number of sample blocks used in the evaluation.
 
     For both domain transformations, a total of 450 seconds with 15 different types of music files are used in the 48 kHz/16-bit test set. Table I shows the test results. 
     As can be seen from Table 1, the MSE generated using the systems and methods of the present invention is very minimal, and unlike conventional systems, is substantially independent of the processing block size. Referring to the DCT-IV domain transformation, the MSE only slightly increases with increasing block size N up to 4096 bits. The MSEs of the FFT are even better, exhibiting a constant MSE of 0.4 for block sizes up to 4096 bits. When the demonstrated performance of the present invention is viewed in light of the present capabilities and increasing need for longer block sizes, the advantages of the present invention become clear. 
     
       
         
           
               
               
               
               
               
             
               
                 TABLE I 
               
               
                   
               
               
                 N 
                 IntDCT-IV 
                 IntIDCT-IV 
                 IntFFT 
                 IntIFFT 
               
               
                   
               
             
            
               
                   
               
            
           
           
               
               
               
               
               
            
               
                 8 
                 0.537 
                 0.537 
                 0.456 
                 0.371 
               
               
                 16 
                 0.546 
                 0.546 
                 0.480 
                 0.412 
               
               
                 32 
                 0.549 
                 0.548 
                 0.461 
                 0.391 
               
               
                 64 
                 0.550 
                 0.550 
                 0.462 
                 0.393 
               
               
                 128 
                 0.551 
                 0.551 
                 0.461 
                 0.391 
               
               
                 256 
                 0.552 
                 0.552 
                 0.461 
                 0.391 
               
               
                 512 
                 0.552 
                 0.552 
                 0.461 
                 0.391 
               
               
                 1024 
                 0.552 
                 0.552 
                 0.460 
                 0.391 
               
               
                 2048 
                 0.552 
                 0.552 
                 0.461 
                 0.391 
               
               
                 4096 
                 0.553 
                 0.552 
                 0.461 
                 0.391 
               
               
                   
               
            
           
         
       
     
     INCORPORATED REFERENCES 
     The following documents are herein incorporated by reference:
         H. S. Malvar, “Signal Processing with Lapped Transforms” Artech House, 1992;   R. Geiger, T. Sporer, J. Koller, K. Brandenburg, “Audio Coding based on Integer Transforms” AES 111 th  Convention, New York, USA, September 2001;   Wang, Zhongde, “On Computing the Discrete Fourier and Cosine Transforms”, IEEE Transactions on Acoustics, Speech and Signal Processing, Vol. ASSP-33, No. 4 October 1985;   I. Daubechies and W. Sweldens, “Factoring wavelet transforms into lifting steps”,  Tech. Report , Bell Laboratories, Lucent Technologies, 1996;   S. Oraintara, Y. J. Chen and T. Q. Nguyen, “Integer fast Fourier transform”,  IEEE Trans. Signal Processing , vol. 50, no. 3, March 2002, pp. 607-618;   P. Hao and Q. Shi, “Matrix factorizations for reversible integer mapping,”  IEEE Trans. Signal Processing , vol. 49, no. 10, October 2001, pp. 2314-2324;   G. Plonka and M. Tasche, “Invertible integer DCT algorithms”,  Appl. Comput. Harmon. Anal.  15:70-88, 2003;   Y. H. Zeng, L. Z. Cheng, G. A. Bi, and Alex C. Kot, “Integer DCTs and fast algorithms”,  IEEE Trans. Signal Processing , vol. 49, no. 11, November 2001, pp. 2774-2782;   J. Wang, J. Sun and S. Yu, “1-D and 2-D transforms from integers to integers”, in  Proc. Int. Conf. Acoustics, Speech and Signal Processing , Hong Kong, 2003, vol. II, pp. 549-552;   “Coding of Moving Pictures and Audio: Work plan for Evaluation of Integer MDCT for FGS to Lossless Experimentation Framework”, ISO/IEC JTC 1/SC 29/WG 11N5578, Pattaya, Thailand, March 2003.