Abstract:
Apparatus, systems and techniques based on an integer transform for encoding and decoding video or image signals, including transform of encoding and decoding of image and video signals and generation of an order-2N transform W from an order-N transform T in the field of image and video coding. For example, a retrieving unit is configured to retrieve an order-N transform T, where N is an integer; a deriving unit is configured to derive an order-2N transform W from the retrieved order-N transform T, and a transforming unit configured to generate an order-2N data Z using the derived transform W.

Description:
CROSS-REFERENCE TO RELATED APPLICATION 
       [0001]    This application is a divisional and claims priority under 35 U.S.C. §120 to U.S. patent application Ser. No. 12/103,678, filed on Apr. 15, 2008, the entire contents of which are incorporated herein by reference. 
     
    
     BACKGROUND 
       [0002]    This application relates to digital image and video processing. 
         [0003]    Various coding processes, such as standards MPEG-2, MPEG-4 Part 2, and H.263 standards, divide a picture into 16×16 non-overlapping blocks called macro blocks and then use a 2 dimensional (2D) order-8 discrete cosine transform (DCT) in digital video compression algorithms used in the coding standards. Such processing can be used to achieve low bit rate communications. Recently, new video coding standards, such as H.264/AVC, AVS and SMPTE 421M etc, have been proposed that use 2D (two dimensions) order-4 or order-8 integer cosine transforms to provide a better compressibility than the video standards based on the 2D order-8 DCT. In those standards, order-4 or order-8 integer transforms are used so as to seek a trade-off between computational efficiency and coding efficiency. 
         [0004]    An order-N transform achieves data compression by exploiting the redundancy within N data elements. Generally, an order-2N transform exploits the redundancy within more data elements and so can achieve higher data compression than an order-N transform. Therefore, a system or method for generating an order-2N transform from an order-N transform in video or image coding is highly demanded. 
       SUMMARY 
       [0005]    This application describes examples and implementations of apparatus, systems and techniques based on an integer transform for encoding and decoding video or image signals, including transform of encoding and decoding of image and video signals and generation of an order-2N transform W from an order-N transform T in the field of image and video coding. 
         [0006]    In one aspect, a system of generation of an order-2N transform W from an order-N transform T includes: 
         [0007]    a retrieving unit configured to retrieve the order-N transform T, where N is an integer; and 
         [0008]    a generating unit configured to generate the order-2N transform W from the retrieved order-N transform T by rules of 
         [0000]        w   u,2i =(1/√2) t   u,i  and  w   u,2i+1 =(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1; and  1)
 
         [0000]        w   2N−u−2i =(1/√2) t   u,i  and  w   2N−u−1,2i+1 =−(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1;  2)
 
         [0000]    where t u,j  is the (u, i)th element of the transform T; w u,2i  and w u,2i+1  are elements of the first N rows of the transform W; and w 2N−u−1,2i  and w 2N−u−1,2i−1  are elements of the last N rows of the transform W for u=0, 1, . . . , N−1. 
         [0009]    Alternatively, an deriving unit may be configured to derive the order-2N transform W from the retrieved order-N transform T by rules of 
         [0000]        w   u,2i =(1/√2) t   u,i  and  w   u,2i+1 =(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1; and  1)
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       
                         
                           u 
                           + 
                           8 
                         
                         , 
                         j 
                       
                     
                     = 
                     
                       
                         
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   
                                     j 
                                     + 
                                     1 
                                   
                                   2 
                                 
                                 ) 
                               
                             
                           
                           
                             2 
                           
                         
                          
                         
                           t 
                           
                             
                               u 
                               + 
                               8 
                             
                             , 
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   j 
                                   / 
                                   2 
                                 
                                 ) 
                               
                             
                           
                         
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         j 
                       
                       = 
                       0 
                     
                   
                   , 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     
                       2 
                        
                       N 
                     
                     - 
                     1 
                   
                 
               
               
                 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where t u,i  is the (u, i)th element of the transform T; 
         [0000]    
       
         
           
             Int 
              
             
               ( 
               
                 
                   j 
                   + 
                   1 
                 
                 2 
               
               ) 
             
           
         
       
     
         [0000]    represents the integral part of 
         [0000]    
       
         
           
             
               
                 j 
                 + 
                 1 
               
               2 
             
             ; 
           
         
       
     
         [0000]    and w u,2i  and w u,2i+1  are elements of the first N rows of the transform W; and w u+8,j  are elements of the last N rows of the transform W for u=0, 1, . . . , N−1. 
         [0010]    In another aspect, a method of generating an order-2N transform W from an order-N transform T includes:
       retrieving the order-N transform T, where N is an integer; and   generating the order-2N transform W from the retrieved order-N transform T by a rule of       
 
         [0000]        w   u,2i =(1/√2) t   u,i  and  w   u,2i+1 =(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1; and  1)
 
         [0000]        w   2N−u−2i =(1/√2) t   u,i  and  w   2N−u−1,2i+1 =−(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1;
 
         [0000]    where t u,i  is the (u, i)th element of the transform T; w u,2i  and w u,2i+1  are elements of the first N rows of the transform W; and w 2N−u−1,2i  and w 2N−u−1,2i+1  are elements of the last N rows of the transform W for u=0, 1, . . . , N−1. 
         [0013]    Alternately, the step of deriving can be carried out by rule of 
         [0000]        w   u,2i =(1/√2) t   u,i  and  w   u,2i+1 =(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1; and  1)
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       
                         
                           u 
                           + 
                           8 
                         
                         , 
                         j 
                       
                     
                     = 
                     
                       
                         
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   
                                     j 
                                     + 
                                     1 
                                   
                                   2 
                                 
                                 ) 
                               
                             
                           
                           
                             2 
                           
                         
                          
                         
                           t 
                           
                             
                               u 
                               + 
                               8 
                             
                             , 
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   j 
                                   / 
                                   2 
                                 
                                 ) 
                               
                             
                           
                         
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         j 
                       
                       = 
                       0 
                     
                   
                   , 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     
                       2 
                        
                       N 
                     
                     - 
                     1 
                   
                 
               
               
                 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0000]    where t u,i  is the (u, i)th element of the transform T; 
         [0000]    
       
         
           
             Int 
              
             
               ( 
               
                 
                   j 
                   + 
                   1 
                 
                 2 
               
               ) 
             
           
         
       
     
         [0000]    represents the integral part of 
         [0000]    
       
         
           
             
               
                 j 
                 + 
                 1 
               
               2 
             
             ; 
           
         
       
     
         [0000]    and w u,2i  and w u,2i+1  are elements of the first N rows of the transform W; and w u+8,j  are elements of the last N rows of the transform W for u=0, 1, . . . , N−1. 
         [0014]    The order-2N transform W obtained based the present techniques can be used to achieve one or more of advantages. For example, if the transform T has a high energy-packing ability, the resultant transform W also has a high energy-packing ability. If the transform T is an orthogonal one, the resultant transform W is an orthogonal one, too. If the transform T is an integer transform, the resultant transform W is also an integer transform. The order-2N transform W can be computed using a fast algorithm based on a fast algorithm for the order-N transform T as well as N additions and N subtractions. 
         [0015]    The details of the above and other aspects of the described apparatus, systems and techniques are set forth in the accompanying drawings, the description and claims below. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0016]      FIG. 1  is an example of a block diagram of a system of generation an order-2N integer transform from an order-N transform; and 
           [0017]      FIG. 2  illustrates exemplarily a method of generating an order-2N integer transform. 
       
    
    
     DETAILED DESCRIPTION 
       [0018]      FIG. 1  shows an example of a system  100  of generation of an order-2N integer transform W. The system  100  includes a retrieving unit  10 , a generating unit  20  and a transforming unit  30 . 
         [0019]    Let T be an order-N transform which can convert a data vector X N  into a coefficient vector C N . Let the i th element of the vector X N  be x i , the u th element of the vector C N  be C u , and the (u, i)th element of the transform T be where u and i=0, 1, . . . , N−1. The conversion from the data vector X N  to the coefficient vector C N  by the transform T is given by (1). 
         [0000]    
       
         
           
             
               
                 
                   
                     C 
                     N 
                   
                   = 
                   
                     
                       TX 
                       N 
                     
                     = 
                     
                       
                         [ 
                         
                           
                             
                               
                                 t 
                                 
                                   0 
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   0 
                                   , 
                                   1 
                                 
                               
                             
                             
                               … 
                             
                             
                               
                                 t 
                                 
                                   0 
                                   , 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           
                             
                               
                                 t 
                                 
                                   1 
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   1 
                                   , 
                                   1 
                                 
                               
                             
                             
                               
                                   
                               
                             
                             
                               
                                 t 
                                 
                                   1 
                                   , 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                             
                               
                                   
                               
                             
                             
                               ⋱ 
                             
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 t 
                                 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   , 
                                   0 
                                 
                               
                             
                             
                               
                                 t 
                                 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   , 
                                   1 
                                 
                               
                             
                             
                               … 
                             
                             
                               
                                 t 
                                 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                   , 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                         
                         ] 
                       
                        
                       
                         [ 
                         
                           
                             
                               
                                 x 
                                 0 
                               
                             
                           
                           
                             
                               
                                 x 
                                 1 
                               
                             
                           
                           
                             
                               ⋮ 
                             
                           
                           
                             
                               
                                 x 
                                 
                                   N 
                                   - 
                                   1 
                                 
                               
                             
                           
                         
                         ] 
                       
                     
                   
                 
               
               
                 
                   ( 
                   1 
                   ) 
                 
               
             
           
         
       
     
         [0020]    Let the u th row of the transform T be an row vector T (u)   T =(t u,0  t u,1  t u,2  . . . t u,N−1 ) where u=0, 1, . . . , N−1, so the transform T could be shown in the form of below: 
         [0000]    
       
         
           
             
               
                 
                   T 
                   = 
                   
                     [ 
                     
                       
                         
                           
                             T 
                             
                               ( 
                               0 
                               ) 
                             
                             T 
                           
                         
                       
                       
                         
                           
                             T 
                             
                               ( 
                               1 
                               ) 
                             
                             T 
                           
                         
                       
                       
                         
                           
                             T 
                             
                               ( 
                               2 
                               ) 
                             
                             T 
                           
                         
                       
                       
                         
                           ⋮ 
                         
                       
                       
                         
                           
                             T 
                             
                               ( 
                               
                                 N 
                                 - 
                                 1 
                               
                               ) 
                             
                             T 
                           
                         
                       
                     
                     ] 
                   
                 
               
               
                 
                   ( 
                   2 
                   ) 
                 
               
             
           
         
       
     
         [0021]    As is well known in the art, the u th row of a transform has u zero crossings. Hence, the number of zero crossings in the vector T (u)   T  is u. 
         [0022]    The retrieving unit  10  is utilized to retrieve the order-N transform T, which may be stored in a memory (not shown) in the system  100  or any storage means external to the system  100 . The order-N transform is input into the retrieving unit  10  via a graphical user interfaces or the like. 
         [0023]    The generating unit  20  receives the retrieved order-N transform T from the unit  10 , and generates an order-2N transform W by computing the transform T, which will be detailed later. 
         [0024]    The transforming unit  30  has two inputs, W (u)  for u=0, 1, . . . , 2N−1 output from the generating unit  20  and a data matrix X to be transformed. The transforming unit  30  transforms the data matrix X into a data matrix Z by a rule of 
         [0000]        Z=WX   (3)
 
         [0025]    Then, the data matrix Z output from the transforming unit  30  is, for example, input into other processing unit, such as a quantization unit (not shown) used in an image or video coding system. 
         [0026]    Hereafter, two examples are given to illustrate the generating unit  20  which generates the order-2N transform W by computing the transform T. 
       Example 1 
       [0027]    In this example, W A  denotes the order-2N transform to be generated by the generating unit  20  from the order-N transform T. Let the u th row of the order-2N transform W A  be a vector W A(u)   T =(w u,0  w u,1  w u,2N−1 ) where u=0, 1, . . . , 2N−1, 
         [0000]    
       
         
           
             
               
                 
                   
                     W 
                     A 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               W 
                               
                                 A 
                                  
                                 
                                   ( 
                                   0 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             
                               W 
                               
                                 A 
                                  
                                 
                                   ( 
                                   1 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             
                               W 
                               
                                 A 
                                  
                                 
                                   ( 
                                   2 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               W 
                               
                                 A 
                                  
                                 
                                   ( 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   4 
                   ) 
                 
               
             
           
         
       
     
         [0028]    The generating unit  20  operates to generate the transform W A  from the vector T (u)   T  according to the following rules:
       (1) the first N rows of the transform W A  is obtained from the vector T u)   T  by a rule of       
 
         [0000]        w   u,2i =(1/√2) and  w   u,2i+1 =(1/√2) t   u,i , for i=0, 1, . . . , N−1  (5)
       and   (2) the last N rows of the transform W A  is obtained from T (u)   T  by a rule of       
 
         [0000]        w   2N−u−1,2i =(1/√2) t   u,i  and  w   2N−u−1,2i+1 =−(1/√2) t   u,i  for  i= 0, 1 , . . . , N− 1  (6)
 
         [0000]    where t u,i  is the (i) th element of the vector T (u)   T  for u=0, 1, . . . , N−1. 
         [0032]    The u th row of the transform W A  has u zero crossings as mentioned above. Hence, the number of zero crossings in the vector W A(u)   T  is u. 
         [0033]    Let N=8. 16 elements of the first and last N rows of the transform W A  are generated from 8 elements of the vector T (u)   T  by rules of equations (5) and (6) as given in tables 1 and 2, respectively. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 Generation of the first 8 rows of W A  from t u, i  where u = 0, 1, . . . , 7. 
               
             
          
           
               
                 i 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
               
                 t u, i   
                 t u, 0   
                 t u, 1   
                 t u, 2   
                 t u, 3   
                 t u, 4   
                 t u, 5   
                 t u, 6   
                 t u, 7   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 √2 w u, i   
                 t u, 0   
                 t u, 0   
                 t u, 1   
                 t u, 1   
                 t u, 2   
                 t u, 2   
                 t u, 3   
                 t u, 3   
                 t u, 4   
                 t u, 4   
                 t u, 5   
                 t u, 5   
                 t u, 6   
                 t u, 6   
                 t u, 7   
                 t u, 7   
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 2 
               
               
                   
               
               
                 Generation of the last 8 rows of W A  from t u, i  where u = 0, 1, . . . , 7. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 i 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
               
               
                   
               
               
                 t u, i   
                 t u, 0   
                 t u, 1   
                 t u, 2   
                 t u, 3   
                 t u, 4   
                 t u, 5   
                 t u, 6   
                 t u, 7   
               
               
                 √2 w 15−u, i   
                 t 15−u, 0   
                 −t 15−u, 0   
                 t 15−u, 1   
                 −t 15−u, 1   
                 t 15−u, 2   
                 −t 15−u, 2   
                 t 15−u, 3   
                 −t 15−u, 3   
               
               
                   
               
               
                 i 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
               
                 √2 w 15−u, i   
                 t 15−u, 4   
                 t 15−u, 4   
                 t 15−u, 5   
                 −t 15−u, 5   
                 t 15−u, 6   
                 −t 15−u, 6   
                 t 15−u, 7   
                 −t 15−u, 7   .   
               
               
                   
               
             
          
         
       
     
         [0034]    It can be seen from the above that both the first N rows and the last N rows of W A  are generated from T (u)   T . For N=8, the relation between u and 2N−u−1 (i.e. 15-u) is given in table 3. 
         [0000]    
       
         
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                 TABLE 3 
               
               
                   
                   
               
               
                   
                 u 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
               
               
                   
                   
               
             
             
               
                   
                 15 − u 
                 15 
                 14 
                 13 
                 12 
                 11 
                 10 
                 9 
                 8 
               
               
                   
                   
               
             
          
         
       
     
         [0035]    Specifically, if the transform T is the order- 8  transform adopted by Standard H.264 and u=1, i.e. T (u)   T =T (1)   T =k 1  [12 10 6 3 −3 −6 −10 −12] where k 1  is a constant such that the magnitude of T (1)  equals unity, then the second row vector W A(1)   T  of the transform W A  is generated from T (1)   T  as W A(1)   T =(k 1 /√2) [12 12 10 10 6 6 3 3 3 3 6 6 10 −10 −12 −12]. And the fifteenth row vector W A(14)   T  of the transform W A  is generated from T (1)   T  as W A(14)   T =(k 1 /√2) [12 −12 10 −10 6 −6 3 −3 −3 3 −6 6 −10 10 −12 12]. 
       Example 2 
       [0036]    In this example, W B  denotes the order-2N transform to be generated by the generating unit  20  from the order-N transform T. Let the u th row of the transform W B  be a vector W B(u)   T =(w u,0  w u,1  w u,2  . . . w u,2N−1 ), where u=0, 1, . . . , 2N−1, 
         [0000]    
       
         
           
             
               
                 
                   
                     W 
                     B 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               W 
                               
                                 B 
                                  
                                 
                                   ( 
                                   0 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             
                               W 
                               
                                 B 
                                  
                                 
                                   ( 
                                   1 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             
                               W 
                               
                                 B 
                                  
                                 
                                   ( 
                                   2 
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               W 
                               
                                 B 
                                  
                                 
                                   ( 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     1 
                                   
                                   ) 
                                 
                               
                               T 
                             
                           
                         
                       
                       ] 
                     
                     . 
                   
                 
               
               
                 
                   ( 
                   7 
                   ) 
                 
               
             
           
         
       
     
         [0037]    The generating unit  20  operates to generate the transform W B  from the vector T (u)   T  according to the following rules:
       (1) the first N rows of the transform W B  is obtained from the vector T (u)   T  by a rule of       
 
         [0000]        w   u,2i =(1/√2)t u,i  and  w   u,2i+1 =(1/√2)t u,i   (7)
           where i=0, 1, . . . , N−1, and u=0, 1, . . . , N−1; and       (2) the last N rows of the transform W B  is obtained from the vector T (u)   T  by a rule of:       
 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       w 
                       
                         
                           u 
                           + 
                           8 
                         
                         , 
                         j 
                       
                     
                     = 
                     
                       
                         
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   
                                     j 
                                     + 
                                     1 
                                   
                                   2 
                                 
                                 ) 
                               
                             
                           
                           
                             2 
                           
                         
                          
                         
                           t 
                           
                             
                               u 
                               + 
                               8 
                             
                             , 
                             
                               Int 
                                
                               
                                 ( 
                                 
                                   j 
                                   / 
                                   2 
                                 
                                 ) 
                               
                             
                           
                         
                          
                         
                             
                         
                          
                         for 
                          
                         
                             
                         
                          
                         j 
                       
                       = 
                       0 
                     
                   
                   , 
                   1 
                   , 
                   … 
                    
                   
                       
                   
                   , 
                   
                     
                       2 
                        
                       N 
                     
                     - 
                     1 
                   
                 
               
               
                 
                   ( 
                   8 
                   ) 
                 
               
             
           
         
       
       
         
           
             where 
           
         
       
     
         [0000]    
       
         
           
             Int 
              
             
               ( 
               
                 
                   j 
                   + 
                   1 
                 
                 2 
               
               ) 
             
           
         
       
     
         [0000]    represents the integral part of 
         [0000]    
       
         
           
             
               
                 j 
                 + 
                 1 
               
               2 
             
             , 
           
         
       
     
         [0000]    and t u,i  is the (u,i)th element of the transform T for u=0, 1, . . . , N−1. 
         [0042]    Let N=8. 16 elements of the first and last N rows of the transform W B  are generated from 8 elements of the vector T (u)   T  by rules of equations (7) and (8) as given in tables 4 and 5, respectively. 
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 4 
               
             
             
               
                   
               
               
                 Generation of the first 8 rows of W B  from t u, i  where u = 0, 1, . . . , 7. 
               
             
          
           
               
                 i 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
               
                 t u, i   
                 t u, 0   
                 t u, 1   
                 t u, 2   
                 t u, 3   
                 t u, 4   
                 t u, 5   
                 t u, 6   
                 t u, 7   
                   
                   
                   
                   
                   
                   
                   
                   
               
               
                 √2 w u, i   
                 t u, 0   
                 t u, 0   
                 t u, 1   
                 t u, 1   
                 t u, 2   
                 t u, 2   
                 t u, 3   
                 t u, 3   
                 t u, 4   
                 t u, 4   
                 t u, 5   
                 t u, 5   
                 t u, 6   
                 t u, 6   
                 t u, 7   
                 t u, 7   
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
             
               
               
               
               
               
               
               
               
               
             
           
               
                 TABLE 5 
               
               
                   
               
               
                 Generation of the last 8 rows of W A  from t u,i  where u = 0, 1, . . . , 7. 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                 j 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
               
               
                   
               
               
                 
                   
                     
                       
                         Int 
                          
                         
                           ( 
                           
                             
                               j 
                               + 
                               1 
                             
                             2 
                           
                           ) 
                         
                       
                     
                   
                 
                 0 
                 1 
                 1 
                 2 
                 2 
                 3 
                 3 
                 4 
               
               
                 √2 w u+8,j   
                 t u,0   
                 −t u,0   
                 −t u,1   
                 t u,1   
                 t u,2   
                 −t u,2   
                 −t u,3   
                 t u,3   
               
               
                   
               
               
                 j 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
               
               
                 
                   
                     
                       
                         Int 
                          
                         
                           ( 
                           
                             
                               j 
                               + 
                               1 
                             
                             2 
                           
                           ) 
                         
                       
                     
                   
                 
                 4 
                 5 
                 5 
                 6 
                 6 
                 7 
                 7 
                 8 
               
               
                 √2 w u+8,j   
                 t u,4   
                 −t u,4   
                 −t u,5   
                 t u,6   
                 t u,6   
                 −t u,6   
                 −t u,7   
                 t u,7   
               
               
                   
               
             
          
         
       
     
         [0043]    It can be seen from the above that both the first N rows and the last N rows of the transform W B  are generated from T (u)   T . For N=8, the relation between u and u+8 is given in table 6. 
         [0000]    
       
         
               
               
               
               
               
               
               
               
               
               
             
           
               
                   
                 TABLE 6 
               
               
                   
                   
               
               
                   
                 u 
                 0 
                 1 
                 2 
                 3 
                 4 
                 5 
                 6 
                 7 
               
               
                   
                   
               
             
             
               
                   
                 u + 8 
                 8 
                 9 
                 10 
                 11 
                 12 
                 13 
                 14 
                 15 
               
               
                   
                   
               
             
          
         
       
     
         [0044]    Specifically, if the transform T is the order-8 transform adopted by Standard H.264 and u=1, i.e. T (u)   T =T (1)   T =k 1  [12 10 6 3 −3 −6 −10 −12] where k 1  is a constant such that the magnitude of T (1)  equals unity, then the second row vector W B(1)   T  of the transform W B  is generated from T (1)   T  as W B(1)   T =(k 1 /√2) [12 12 10 10 6 6 3 3 3 3 6 6 10 −10 −12 −12] and the tenth row vector W B(9)   T  of the transform W B  is generated from T (1)   T  as W B(9)   T =(k 1 /√2) [ 12   12  − 10   10   6  − 6  − 3   3  − 3   3   6  − 6  − 10   10   12  − 12 ]. 
         [0045]    Though the above two examples are given by using the order- 8  transform provided by Standard H.264. It will be appreciated that various order-N transforms provided by coding schemes such as standards AVS, SMPTE 421M may be used in implementations. For example, the number of N is not limited to 8. 
         [0046]    It is desirable to have a lesser computational requirement for a transform. The order-2N transform W can be computed using a fast algorithm based on: 
         [0047]    (a) a fast algorithm for the order-N transform T; and 
         [0048]    (b) N addition and N subtraction operations. 
         [0049]    Again, the fast algorithm, which can be applied to the order-2N transform W, will be exemplarily described in referring to the transform W A  and W B  as follows. 
         [0000]    A fast Algorithm for the Order-2N Transform W A . 
         [0050]    Let X u  be a vector containing input data x 0  to x 2N−1 , Z u  be a transformed vector containing data z 0  to z 2N−1  from X u  by a rule of Z u =W A  X u , i.e. 
         [0000]    
       
         
           
             
               
                 
                   
                     Z 
                     u 
                   
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               z 
                               0 
                             
                           
                         
                         
                           
                             
                               z 
                               1 
                             
                           
                         
                         
                           
                             
                               z 
                               2 
                             
                           
                         
                         
                           
                             
                               z 
                               3 
                             
                           
                         
                         
                           
                             
                               z 
                               4 
                             
                           
                         
                         
                           
                             
                               z 
                               5 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 5 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 3 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 2 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       
                         
                           W 
                           A 
                         
                          
                         X 
                       
                       = 
                       
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     W 
                                     
                                       A 
                                        
                                       
                                         ( 
                                         0 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       A 
                                        
                                       
                                         ( 
                                         1 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       A 
                                        
                                       
                                         ( 
                                         2 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       A 
                                        
                                       
                                         ( 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     x 
                                     0 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     1 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     2 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     3 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     4 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     5 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       4 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       3 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   9 
                   ) 
                 
               
             
           
         
       
     
         [0051]    Then, Z u  can be divided into two parts Z 1  and Z 2  as follows. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           Z 
                           1 
                         
                         = 
                           
                          
                         
                           [ 
                           
                             
                               
                                 
                                   z 
                                   0 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   2 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   3 
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   z 
                                   
                                     N 
                                     - 
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       0 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       2 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       
                                         N 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       x 
                                       0 
                                     
                                     + 
                                     
                                       x 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       2 
                                     
                                     + 
                                     
                                       x 
                                       3 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       4 
                                     
                                     + 
                                     
                                       x 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         4 
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         3 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         2 
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             T 
                              
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         x 
                                         0 
                                       
                                       + 
                                       
                                         x 
                                         1 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         2 
                                       
                                       + 
                                       
                                         x 
                                         3 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         4 
                                       
                                       + 
                                       
                                         x 
                                         5 
                                       
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           4 
                                         
                                       
                                       + 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           3 
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           2 
                                         
                                       
                                       + 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   10 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           Z 
                           2 
                         
                         = 
                           
                          
                         
                           [ 
                           
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     1 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     3 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     4 
                                   
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     N 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   N 
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       0 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       2 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       
                                         N 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       x 
                                       0 
                                     
                                     - 
                                     
                                       x 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       2 
                                     
                                     - 
                                     
                                       x 
                                       3 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       4 
                                     
                                     - 
                                     
                                       x 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         4 
                                       
                                     
                                     - 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         3 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         2 
                                       
                                     
                                     - 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             T 
                              
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         x 
                                         0 
                                       
                                       - 
                                       
                                         x 
                                         1 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         2 
                                       
                                       - 
                                       
                                         x 
                                         3 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         4 
                                       
                                       - 
                                       
                                         x 
                                         5 
                                       
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           4 
                                         
                                       
                                       - 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           3 
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           2 
                                         
                                       
                                       - 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   11 
                   ) 
                 
               
             
           
         
       
     
         [0052]    Hence, the fast algorithm for W A  requires 
         [0053]    a) N additions and a fast algorithm for the order-N transform T as given in (10) and 
         [0054]    b) N subtractions and a fast algorithm for the order-N transform T as given in (11). 
       An Fast Algorithm for the Order-2N Transform W B    
       [0055]    Again, let X u  be a vector containing input data x 0  to x 2N−1 , Z u  be a transformed vector containing data z o  to z 2N−1  from X u  by a rule of Z u =W B X u , i.e. 
         [0000]    
       
         
           
             
               
                 
                   Zu 
                   = 
                   
                     
                       [ 
                       
                         
                           
                             
                               z 
                               0 
                             
                           
                         
                         
                           
                             
                               z 
                               1 
                             
                           
                         
                         
                           
                             
                               z 
                               2 
                             
                           
                         
                         
                           
                             
                               z 
                               3 
                             
                           
                         
                         
                           
                             
                               z 
                               4 
                             
                           
                         
                         
                           
                             
                               z 
                               5 
                             
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             ⋮ 
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 5 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 4 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 3 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 2 
                               
                             
                           
                         
                         
                           
                             
                               z 
                               
                                 
                                   2 
                                    
                                   N 
                                 
                                 - 
                                 1 
                               
                             
                           
                         
                       
                       ] 
                     
                     = 
                     
                       
                         
                           W 
                           B 
                         
                          
                         X 
                       
                       = 
                       
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     W 
                                     
                                       B 
                                        
                                       
                                         ( 
                                         0 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       B 
                                        
                                       
                                         ( 
                                         1 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       B 
                                        
                                       
                                         ( 
                                         2 
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     W 
                                     
                                       B 
                                        
                                       
                                         ( 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                         ) 
                                       
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     x 
                                     0 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     1 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     2 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     3 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     4 
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     5 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       4 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       3 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     x 
                                     
                                       
                                         2 
                                          
                                         N 
                                       
                                       - 
                                       1 
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                         . 
                       
                     
                   
                 
               
               
                 
                   ( 
                   12 
                   ) 
                 
               
             
           
         
       
     
         [0056]    Then, Z u  can be divided into two parts Z′ 1  and Z′ 2  as follows. 
         [0000]    
       
         
           
             
               
                 
                   
                     
                       
                         
                           Z 
                           1 
                           ′ 
                         
                         = 
                           
                          
                         
                           [ 
                           
                             
                               
                                 
                                   z 
                                   0 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   1 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   2 
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   3 
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   z 
                                   
                                     N 
                                     - 
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   z 
                                   
                                     N 
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       0 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       2 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       
                                         N 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       x 
                                       0 
                                     
                                     + 
                                     
                                       x 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       2 
                                     
                                     + 
                                     
                                       x 
                                       3 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       4 
                                     
                                     + 
                                     
                                       x 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         4 
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         3 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         2 
                                       
                                     
                                     + 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             T 
                              
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         x 
                                         0 
                                       
                                       + 
                                       
                                         x 
                                         1 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         2 
                                       
                                       + 
                                       
                                         x 
                                         3 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         4 
                                       
                                       + 
                                       
                                         x 
                                         5 
                                       
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           4 
                                         
                                       
                                       + 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           3 
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           2 
                                         
                                       
                                       + 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   13 
                   ) 
                 
               
             
             
               
                 
                   
                     
                       
                         
                           Z 
                           2 
                           ′ 
                         
                         = 
                           
                          
                         
                           [ 
                           
                             
                               
                                 
                                   Z 
                                   N 
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     N 
                                     + 
                                     1 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     N 
                                     + 
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     + 
                                     3 
                                   
                                 
                               
                             
                             
                               
                                 ⋮ 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     2 
                                   
                                 
                               
                             
                             
                               
                                 
                                   Z 
                                   
                                     
                                       2 
                                        
                                       N 
                                     
                                     - 
                                     1 
                                   
                                 
                               
                             
                           
                           ] 
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             [ 
                             
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       0 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       1 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       2 
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     T 
                                     
                                       ( 
                                       
                                         N 
                                         - 
                                         1 
                                       
                                       ) 
                                     
                                     T 
                                   
                                 
                               
                             
                             ] 
                           
                            
                           
                             [ 
                             
                               
                                 
                                   
                                     
                                       x 
                                       0 
                                     
                                     - 
                                     
                                       x 
                                       1 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       3 
                                     
                                     - 
                                     
                                       x 
                                       2 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       4 
                                     
                                     - 
                                     
                                       x 
                                       5 
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       7 
                                     
                                     - 
                                     
                                       x 
                                       6 
                                     
                                   
                                 
                               
                               
                                 
                                   ⋮ 
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         4 
                                       
                                     
                                     - 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         3 
                                       
                                     
                                   
                                 
                               
                               
                                 
                                   
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         2 
                                       
                                     
                                     - 
                                     
                                       x 
                                       
                                         
                                           2 
                                            
                                           N 
                                         
                                         - 
                                         1 
                                       
                                     
                                   
                                 
                               
                             
                             ] 
                           
                         
                       
                     
                   
                   
                     
                       
                         = 
                           
                          
                         
                           
                             T 
                              
                             
                               [ 
                               
                                 
                                   
                                     
                                       
                                         x 
                                         0 
                                       
                                       - 
                                       
                                         x 
                                         1 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         3 
                                       
                                       - 
                                       
                                         x 
                                         2 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         4 
                                       
                                       - 
                                       
                                         x 
                                         5 
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         7 
                                       
                                       - 
                                       
                                         x 
                                         6 
                                       
                                     
                                   
                                 
                                 
                                   
                                     ⋮ 
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           4 
                                         
                                       
                                       - 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           3 
                                         
                                       
                                     
                                   
                                 
                                 
                                   
                                     
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           2 
                                         
                                       
                                       - 
                                       
                                         x 
                                         
                                           
                                             2 
                                              
                                             N 
                                           
                                           - 
                                           1 
                                         
                                       
                                     
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
               
               
                 
                   ( 
                   14 
                   ) 
                 
               
             
           
         
       
     
         [0057]    Similar to the fast algorithm for W A , the fast algorithm for W B  requires 
         [0058]    a) N additions and a fast algorithm for the order-N transform T as given in (13) and 
         [0059]    b) N subtractions and a fast algorithm for the order-N transform T as given in (14). 
         [0060]    While the retrieving unit  10 , the generating unit  20  and the transforming unit  30  are shown in  FIG. 1  and described herein as three separate units, other implementations are possible. For example, the units  10 ,  20  and  30  may be integrated into one chip or arranged into multiple units separately, and may be implemented either by software or hardware, or the combination of software and hardware. 
         [0061]      FIG. 2  illustrates an example of a process  100  of generating an order-2N integer transform from an order-N transform. 
         [0062]    The process  1000  begins at step  101 , where an order-N transform T is retrieved. At step  102 , the order-2N transform W is generated by computing the transform T by rules set forth in equations (5)-(6), or equations (7)-(8). 
         [0063]    Then, the process  1000  proceeds to step  103 , where, the data X to be transformed are received and transformed by a rule of Z=WX. 
         [0064]    The disclosed and other embodiments and the functional operations described in this specification can be implemented in digital electronic circuitry, or in computer software, firmware, or hardware, including the structures disclosed in this specification and their structural equivalents, or in combinations of one or more of them. The disclosed and other embodiments can be implemented as one or more computer program products, i.e., one or more modules of computer program instructions encoded on a computer readable medium for execution by, or to control the operation of, data processing apparatus. The computer readable medium can be a machine-readable storage device, a machine-readable storage substrate, a memory device, a composition of matter effecting a machine-readable propagated signal, or a combination of one or more them. The term “data processing apparatus” encompasses all apparatus, devices, and machines for processing data, including by way of example a programmable processor, a computer, or multiple processors or computers. The apparatus can include, in addition to hardware, code that creates an execution environment for the computer program in question, e.g., code that constitutes processor firmware, a protocol stack, a database management system, an operating system, or a combination of one or more of them. A propagated signal is an artificially generated signal, e.g., a machine-generated electrical, optical, or electromagnetic signal, that is generated to encode information for transmission to suitable receiver apparatus. 
         [0065]    A computer program (also known as a program, software, software application, script, or code) can be written in any form of programming language, including compiled or interpreted languages, and it can be deployed in any form, including as a stand alone program or as a module, component, subroutine, or other unit suitable for use in a computing environment. A computer program does not necessarily correspond to a file in a file system. A program can be stored in a portion of a file that holds other programs or data (e.g., one or more scripts stored in a markup language document), in a single file dedicated to the program in question, or in multiple coordinated files (e.g., files that store one or more modules, sub programs, or portions of code). A computer program can be deployed to be executed on one computer or on multiple computers that are located at one site or distributed across multiple sites and interconnected by a communication network. 
         [0066]    The processes and logic flows described in this specification can be performed by one or more programmable processors executing one or more computer programs to perform functions by operating on input data and generating output. The processes and logic flows can also be performed by, and apparatus can also be implemented as, special purpose logic circuitry, e.g., an FPGA (field programmable gate array) or an ASIC (application specific integrated circuit). 
         [0067]    Processors suitable for the execution of a computer program include, by way of example, both general and special purpose microprocessors, and any one or more processors of any kind of digital computer. Generally, a processor will receive instructions and data from a read only memory or a random access memory or both. The essential elements of a computer are a processor for performing instructions and one or more memory devices for storing instructions and data. Generally, a computer will also include, or be operatively coupled to receive data from or transfer data to, or both, one or more mass storage devices for storing data, e.g., magnetic, magneto optical disks, or optical disks. However, a computer need not have such devices. Computer readable media suitable for storing computer program instructions and data include all forms of non volatile memory, media and memory devices, including by way of example semiconductor memory devices, e.g., EPROM, EEPROM, and flash memory devices; magnetic disks, e.g., internal hard disks or removable disks; magneto optical disks; and CD ROM and DVD-ROM disks. The processor and the memory can be supplemented by, or incorporated in, special purpose logic circuitry. 
         [0068]    The disclosed embodiments can be implemented in a computing system that includes a back end component, e.g., as a data server, or that includes a middleware component, e.g., an application server, or that includes a front end component, e.g., a client computer having a graphical user interface or a Web browser through which a user can interact with an implementation of what is disclosed here, or any combination of one or more such back end, middleware, or front end components. The components of the system can be interconnected by any form or medium of digital data communication, e.g., a communication network. Examples of communication networks include a local area network (“LAN”) and a wide area network (“WAN”), e.g., the Internet. 
         [0069]    A computer system for implementing the disclosed embodiments can include client computers (clients) and server computers (servers). A client and a server are generally remote from each other and typically interact through a communication network. The relationship of client and server can arise by virtue of computer programs running on the respective computers and having a client-server relationship to each other. 
         [0070]    While this specification contains many specifics, these should not be construed as limitations on the scope of any invention or of what may be claimed, but rather as descriptions of features specific to particular embodiments. Certain features that are described in this specification in the context of separate embodiments can also be implemented in combination in a single embodiment. Conversely, various features that are described in the context of a single embodiment can also be implemented in multiple embodiments separately or in any suitable subcombination. Moreover, although features may be described above as acting in certain combinations and even initially claimed as such, one or more features from a claimed combination can in some cases be excised from the combination, and the claimed combination may be directed to a subcombination or variation of a subcombination. 
         [0071]    Similarly, operations are depicted in the drawings in a particular order, and such operations should be performed in the particular order shown or in sequential order, and that all illustrated operations be performed, to achieve desirable results. In certain circumstances, multitasking and parallel processing may be advantageous. Moreover, the separation of various system components in the embodiments described above should not be understood as requiring such separation in all embodiments, and it should be understood that the described program components and systems can generally be integrated together in a single software product or packaged into multiple software products. 
         [0072]    Thus, particular embodiments have been described. Other embodiments are within the scope of the following claims.