Abstract:
The invention describes a simple and efficient codeword degrouping algorithm which can be applied in an MPEG audio decoder, in which a codeword is degrouped into three samples. According to the proposed algorithm, the division and modulo computations applied in the original degrouping method can be fully substituted into the addition and subtraction computations by using the mode selection and iterative decompositions, and thus largely reduces the overhead and complexity for the decoder. Also, an efficient architecture for the proposed algorithm includes one special adder, two subtractors, and two adders. The architecture generates the quotient and remainder simultaneously with fix-rate throughput.

Description:
FIELD OF THE INVENTION 
     The present invention is related to an algorithm and architecture for degrouping a codeword in MPEG-II audio decoding, and in particular to an algorithm and architecture for degrouping a codeword in MPEG-II audio decoding which rely on just only using the addition and subtraction instead of the traditional division and modulo arithmetic operations without loss of accuracy. 
     BACKGROUND OF THE INVENTION 
     The MPEG audio coding standard is the international standard for the compression of digital audio signals. It can be applied both for audiovisual and audio-only applications to significantly reduce the requirements of transmission bandwidth and data storage with low distortion. The second phase of MPEG, labeled as MPEG-II, aims to support all the normative feature listed in MPEG-I audio and provide extension capabilities of multi-channel and multilingual audio and on an extension of standard to lower sampling frequencies and lower bit rates. No matter what is MPEG-I or MPEG-II standard, the MPEG audio compression standard defines threes layers of compression, named as Layer I, II, and III. Each successive layer offers better compression performance, but at a higher complexity and computation cost. Layer I and II are basically similar and based on subband coding. The difference between them mainly lies in formatting side information and a finer quantization is provided in Layer II. Layer III adopts more complex schemes such as hybrid filterbank, Huffman coding and non-linear quantization. From the viewpoint of hardware complexity and achieved quality, Layer II might be a reasonable compromise for general usage. In the official ISO/MPEG subject tests, Layer II coding shows an excellent performance of CD quality at a 128 Kbps per monophonic channel. 
     Within the Layer II decoding, degrouping is the key component which can recover the samples from a more compressed codeword. As will be described in more detail below, the arithmetic operations for degrouping mainly contain division and modulo. As the conventional methods, there have been executed the arithmetic operations by a general purpose DSP or ASP (audio signal processor) which have some division or modulo instructions. These designs basically implied either a divider directly, or a multiplier by finding the inverse of the divisor and multiplying the inverse by the dividend. These approaches increased the hardware complexity of the processor and the chip area. Several techniques used a ROM-based table lookup to replace the multiplier. Nevertheless, ROM circuit grows exponentially with the dimension of the finite field. Although many fast algorithms for computing the division and modulo arithmetic operations have been presented throughout the years, these techniques cannot be fully adopted in the MPEG degrouping algorithm. So far no dedicated degrouping algorithm and architecture is known. 
     The overall MPEG decoding flow chart is described in FIG.  1 . FIG. 2 shows a further decomposition of inverse quantization of samples in Layer II application. In MPEG audio encoder, given the number of steps from bit allocation, the samples will be quantized. If grouping is required, three consecutive samples are coded as one codeword. For 3-, 5-, and 9-level quantization, a triplet is coded using a 5-, 7-, or 10-bit codeword, respectively. Only one value Vj is transmitted for this triplet. The relations between the coded value Vj and the three consecutive subband samples x, y, z are listed in Table 1. 
     
       
         
               
             
               
               
               
               
               
             
               
               
               
               
               
             
           
               
                 TABLE 1 
               
             
             
               
                   
               
               
                 The relations between the codeword and the three consecutive samples 
               
             
          
           
               
                   
                 Quant- 
                   
                   
                   
               
               
                   
                 ization 
                   
                 Number of bits of 
               
               
                 Equation 
                 level 
                 Range of V 
                 V 
                 Mode 
               
               
                   
               
             
          
           
               
                 V a  = 9z + 3y + x 
                 3 
                 0 . . . 26  
                 5 
                 1 
               
               
                 V b  = 25z + 5y + x 
                 5 
                 0 . . . 124 
                 7 
                 2 
               
               
                 V c  = 81z + 9y + x 
                 9 
                 0 . . . 728 
                 10 
                 3 
               
               
                   
               
             
          
         
       
     
     If the grouping is used in encoder, it is necessary to separate the combined sample codeword to the individual samples by degrouping in decoder. According to the grouping equations in Table 1, the degrouping have to perform the division and modulo operations to separate the three individual samples. This process is supplied by MPEG standard algorithm and depicted as follows: 
     
       
         
               
               
               
             
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 Algorithm 
                 Degrouping 
               
             
          
           
               
                   
                 for(i = 0;i &lt; 3;i++) 
               
               
                   
                 { 
               
               
                   
                 s[i] = c%nlevels; 
               
               
                   
                 c = (int)c/nlevels; 
               
               
                   
                 } 
               
               
                   
                   
               
             
          
         
       
     
     wherein s[i] the reconstructed sample 
     
       
         
               
               
               
             
           
               
                   
                   
               
             
             
               
                   
                 c 
                 the codeword 
               
               
                   
                 nlevels 
                 the number of quantization level. 
               
               
                   
                   
               
             
          
         
       
     
     Within the degrouping algorithm, the nlevels can be 3, 5, and 9 as shown in Table 1. 
     Table 2 summarizes the total arithmetic operations in MPEG Layer II audio decoding. A similar analysis of the arithmetic operations in decoding algorithm shows that multiplication and addition are the most common operations which mainly focus on synthesis subband filter. Especially in MPEG-II decoding, degrouping only occupies about 1% computation power of the whole decoding process. More specifically, these arithmetic operations are fully different and generally can&#39;t be shared with other resource of decoding functions. Thus, a low cost and high performance degrouping algorithm and architecture are necessary to reduce the circuit overhead and complexity. 
     
       
         
               
             
               
               
               
               
             
           
               
                 TABLE 2 
               
             
             
               
                   
               
               
                 Arithmetic operations in MPEG Layer II audio decoding 
               
             
          
           
               
                   
                 Classification 
                 Function 
                 Operations 
               
               
                   
                   
               
               
                   
                 IQ 
                 Degrouping 
                 y = c % a,c = c/d 
               
               
                   
                   
                 Requatization 
                 y = (x + a)b 
               
               
                   
                   
                 Rescalization 
                 y = ax 
               
               
                   
                 Syn. Subband 
                 IMDCT 
                 y = ax + b,y = Σ i C i x i   
               
               
                   
                   
                 IPQMF 
                 y = ax,y = Σ i w I   
               
               
                   
                   
               
             
          
         
       
     
     SUMMARY OF THE INVENTION 
     A primary objective of the present invention is to provide an efficient algorithm for degrouping a codeword in MPEG-II audio decoding, in which the arithmetic operations involved are only addition and subtraction instead of the division and modulo used in the conventional algorithm. Another objective of the present invention is to provide an architecture for degrouping a codeword in MPEG-II audio decoding, which not only have a simple and low cost design, but can generate a fixed throughput, i.e. one sample is decoded per clock number independent from the value of the input codeword. 
    
    
     BRIEF DESCRIPTION OF THE DRAWINGS 
     FIG. 1 shows a MPEG decoding flow chart. 
     FIG. 2 shows a flow chart of the inverse quantization in FIG. 1 MPEG decoding. 
     FIG. 3 is a graphical representation of proposed algorithm for the fast calculations of q′ and r′ in all three modes. 
     FIG. 4 shows an overall flow chart for the proposed algorithm shown in FIG.  3 . 
     FIG. 5 is a block diagram showing a degrouping architecture suitable for carrying out the proposed algorithm according to the overall flow chart shown in FIG.  4 . 
     FIG. 6 is a graphical representation of a data reordering scheme for the fast calculations of q′ and r′ in all three modes. 
     FIG. 7 is a block diagram showing a degrouping architecture suitable for carrying out the data reordering scheme shown in FIG.  6 . 
     FIG. 8 is a block diagram showing the internal architecture of SPADD in FIG.  7 . 
     FIGS. 9 a  and  9   b  are plots showing experimental results of mode 1 for the deviation values of: a) q′ with respect to q, and b) r′ with respect to r. 
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
     In the present invention, we propose a novel MPEG degrouping process algorithm and its architecture design. They will be built by using quite different design concept than all the prior art works. Our approach relies on just only using the addition and subtraction instead of the traditional division and modulo arithmetic operations without loss of accuracy. Not any multiplier, divider and ROM table are needed in our design. It is further objective of the proposed design to provide the circuit which avoids the need for iterative division techniques involving multiple clocked registers, the clocked registers being used only to store initial input. The design takes the advantages of simple and low cost, but high efficient requirement with fixed throughput. 
     Proposed Algorithm 
     Let A, m are any two positive integers and A, m&gt;0. Then we can express: 
     
       
         
           A=m·q+r 
         
       
     
     wherein q is the quotient, and r is the remainder. 
     Besides, A can be represented as an n-digit tuple:                      A   =       ∑     i   =   0       n   -   1                         a   i     ·     2   i                     =       a   0     +       a   1     ·   2     +       a   2     ·     2   2       +   …   +       a     n   -   1       ·     2     n   -   1                       =     (       a     n   -   1       ,     a     n   -   2       ,     a     n   -   3       ,   …              ,     a   1     ,     a   0       )                  
            whrein                   a   0       ,       a   1        …                     a       n   -   1     ∈                  [     0   ,   1     ]       ,     n   =       ⌈       log   2          (     A   +   1     )       ⌉     .                 (   2   )                                
     Case 1: m=2 p    
     From (1) and (2), A can be represented as given below when m=2 p :                    A   =                    2   p     ·   q     +   r                 =                    ∑     i   =   0       p   -   1                         a   i     ·     2   i         +       2   p     ·     [       a   p     +       a     p   +   1       ·   2     +       a     p   +   2       ·     2   2       +   …   +       a     n   -   1       ·     2     n   -   1           ]                       (   3   )                                
     Comparing between (1) and (3), thus q and r can be expressed:                    q   =       a   p     +       a     p   +   1       ·   2     +       a     p   +   2       ·     2   2       +   …   +       a     n   -   1       ·     2     n   -   1                       =     (       a     n   -   1       ,     a     n   -   2       ,     a     n   -   3       ,   …              ,     a     p   +   1       ,     a   p       )                   (   4   )                     r   =       ∑     i   =   0       p   -   1                         a   i     ·     2   i                     =     (       a     p   -   1       ,     a     p   -   2       ,     a     p   -   3       ,   …              ,     a   1     ,     a   0       )                   (   5   )                                
     Case 2: m=2 p +1: 
     From (1), A can be represented as given below when m=2 p +1:                    A   =                    (       2   p     +   1     )     ·   q     +   r                               =                  3   ·   q     +   r       ,                        p   =   1                   =                  5   ·   q     +   r       ,                        p   =   2                   =                  9   ·   q     +   r       ,                        p   =   3                   (   6   )                                
     wherein p=1, 2, and 3 are mapping to the three modes for degrouping algorithm, respectively. 
     The equation (6) can be rewritten according to equation (3) as follows:              A   =         (       2   p     +   1     )     ·   q     +   r                 =         2   p     ·     q   1       +     r   1                   =     (         (       2   p     +   1     )     ·     q   1       -     q   1     +     r   1       )                                  
     Again q 1  can be expressed as:                q   1     =         2   p     ·     q   2       +     r   2                   =         (       2   p     +   1     )     ·     q   2       -     q   2     +     r   2                                    
     Similarly, q 2  and so on can be expressed as:                      q   2     =         2   p     ·     q   3       +     r   3                   =         (       2   p     +   1     )     ·     q   3       -     q   3     +     r   3                 ⋮               q     k   -   1       =         2   p     ·     q   k       +     r   k                   =         (       2   p     +   1     )     ·     q   k       -     q   k     +     r   k                     q   k     =         2   p     ·     q     k   +   1         +     r     k   +   1                     =         (       2   p     +   1     )     ·     q     k   +   1         -     q     k   +   1       +     r     k   +   1                       (   7   )                                
     Because q k &lt;2 p , q k+1 =0, thus: 
     
       
           q   k   =r   k+1   (8) 
       
     
     From the iterative decomposition of (7) and using (8), we can proceed as follows:                    A   =                    (       2   p     +   1     )     ·     q   1       -     q   1     +     r   1                   =                        (       2   p     +   1     )     ·     q   1       -     {     (         (       2   p     +   1     )     ·     q   2       -     q   2     +     r   2       )         ]     +     r   1                   =                    (       2   p     +   1     )     ·     (       q   1     -     q   2       )       +     q   2     +     r   1     -     r   2                   =                    (       2   p     +   1     )     ·     (       q   1     -     q   2       )       +     [     (         (       2   p     +   1     )     ·     q   3       -     q   3     +     r   3       )     ]     +     r   1     -     r   2                   =                    (       2   p     +   1     )     ·     (       q   1     -     q   2     +     q   3       )       +     (       r   1     -     r   2     +     r   3     -     q   3       )                              ⋮               =                    (       2   p     +   1     )     ·     [       q   1     -     q   2     +     q   3     -   …   +         (     -   1     )       k   +   1       ·     q   k         ]       +                              [       r   1     -     r   2     +     r   3     -   …   +         (     -   1     )       k   +   2       ·     r     k   +   1           ]                   (   9   )                                
     Comparing between (1) and (9), let 
     
       
           q′=q   1   −q   2   +q   3  . . . +(−1) k+1   ·q   k , 
       
     
     and 
     
       
           r′=r   1   −r   2   +r   3  . . . +(−1) k+2   ·r   k+1 ,  (10) 
       
     
     From (10), because 0≦r j ≦2 p −1, for j=1,2,3 . . . k+1, the range of q′ and r′ can be expressed as follows:                -     [       (       2     n   -     k   ·   p         -   1     )     +       (       ⌈       k   +   1     2     ⌉     -   1     )     ·     (       2   p     -   1     )         ]       ≤     r   ′     ≤       ⌈       k   +   1     2     ⌉     ·     (       2   p     -   1     )               (   11   )                                
     Substituting (11) into (9), we can obtain the range of q′ as follows:                q   -     ⌈         (       2     n   -     k   ·   p         -   1     )     +       (       ⌈       k   +   1     2     ⌉     -   1     )     ·     (       2   p     -   1     )           2   p       ⌉       ≤     q   ′     ≤     q   +     ⌊         ⌈       k   +   1     2     ⌉     ·     (       2   p     -   1     )         2   p       ⌋               (   12   )                                
     Arithmetic operations for mode 1, 2 and 3: 
     Mode 1 (p=1): 
     As shown in Table 1, A is 5. Comparing between (4) and (7), we can obtain k=4. From (4), (5) and (10), q′ and r′ can be expressed as follows:                q   ′     =                  q   1     -     q   2     +     q   3     -     q   4                     =                  (       a   4     ,     a   3     ,     a   2     ,     a   1       )     -     (       a   4     ,     a   3     ,     a   2       )     +     (       a   4     ,     a   3       )     -     (     a   4     )         ,   and                 r   ′     =                  r   1     -     r   2     +     r   3     -     r   4     +     r   5                     =                  a   0     -     a   1     +     a   2     -     a   3     +     a   4         ,                                
     Further, q′ and r′ can be calculated from (11) and (12) after knowing p, k and n. The results are shown as follows: 
     
       
         −2 ≦r′≦ 3  (13) 
       
     
     
       
           q− 1 ≦q′≦q+ 1  (14) 
       
     
     Mode 2 (p=2): 
     As shown in Table 1, A is 7. Comparing between (4) and (7), we can obtain k=3. From (4), (5) and (10), q′ and r′ can be expressed as follows:                q   ′     =       q   1     -     q   2     +     q   3                     =       (       a   6     ,     a   5     ,     a   4     ,     a   3     ,     a   2       )     -     (       a   6     ,     a   5     ,     a   4       )     +     (     a   6     )         ,   and                 r   ′     =       r   1     -     r   2     +     r   3     -     r   4                     =       (       a   1     ,     a   0       )     -     (       a   3     ,     a   2       )     +     (       a   5     ,     a   4       )     -     a   6         ,                                
     Further, q′ and r′ can be calculated from (11) and (12) after knowing p, k and n. The results are shown as follows: 
     
       
         −4 ≦r′≦ 6  (15) 
       
     
     
       
           q− 1 ≦q′≦q+ 1  (16) 
       
     
     Mode 3 (p=3): 
     As shown in Table 1, A is 10. Comparing between (4) and (7), we can obtain k=3. From (4), (5) and (10), q′ and r′ can be expressed as follows:                q   ′     =       q   1     -     q   2     +     q   3                     =       (       a   9     ,     a   8     ,     a   7     ,     a   6     ,     a   5     ,     a   4     ,     a   3       )     -     (       a   9     ,     a   8     ,     a   7     ,     a   6       )     +     (     a   9     )         ,   and                 r   ′     =       r   1     -     r   2     +     r   3     -     r   4                     =       (       a   2     ,     a   1     ,     a   0       )     -     (       a   5     ,     a   4     ,     a   3       )     +     (       a   8     ,     a   7     ,     a   6       )     -     a   9         ,                                
     Further, q′ and r′ can be calculated from (11) and (12) after knowing p, k and n. The results are shown as follows: 
     
       
         −8 ≦r′≦ 14  (17) 
       
     
     
       
           q− 1 ≦q′≦q+ 1  (18) 
       
     
     Based on the arithmetic operations discussed in the above three modes, the algorithm proposed in the present invention accomplishes the division and modulo by only processing the codeword A, which can be viewed as a 2-tuple representation of q k  and r k . Each intermediate operand, denoted as A&gt;&gt;p for convenience, is obtained by shifting right p bits and dropping rightmost p bits of A after each shift. FIG. 3 describes a graphical representation of the proposed algorithm for the fast calculating of q′ and r′ in the three modes. In Mode 1 (k=4), five operands A, A&gt;&gt;1, A&gt;&gt;2, A&gt;&gt;3, and A&gt;&gt;4 are generated by shifting right 1 bit. These operands take interlace computations of two subtractions and two additions to obtain a sum S. We can then obtain r′ and q′ from S as r′=LSB+(1,0)·co 0 , and q′=MSB−(co 0 ), wherein LSB is the value of the lowest one bit of S, MSB is the value of the upper four bits of S, and co 0  is the one-bit carry of addition for one-bit LSB of S. 
     In Mode 2 (k=3), four operands A, A&gt;&gt;2, A&gt;&gt;4, and A&gt;&gt;6 are generated by shifting right 2 bits. These operands take the interlace computations of two subtractions and one addition to obtain a sum S. We can then obtain r′ and q′ from S as r′=LSB+(1,0,0)·co 0 , and q′=MSB−(co 0 ), wherein LSB is the value of the lowest two bit of S, MSB is the value of the upper five bits of S, and co 0  is the one-bit carry of addition for two-bit LSB of S. 
     In Mode 3 (k=3), four operands A, A&gt;&gt;3, A&gt;&gt;6, and A&gt;&gt;9 are generated by shifting right 3 bits. These operands take the interlace computations of two subtractions and one addition to obtain a sum S. We can then obtain r′ and q′ from S as r′=LSB+(1,0,0,0)·co 0 , and q′=MSB−(co 0 ), wherein LSB is the value of the lowest three bits of S, MSB is the value of the upper seven bits of S, and co 0  is the one-bit carry of addition for the three-bit LSB of S. 
     In addition to the fast calculation, the exactly correct results of q and r must need future process form q′ and r′ according to (13) to (18). The correct result of r is obtained by getting the r′ plus or minus with a value of a divisor in each associated mode. The correct result of q is obtained by getting the q′ plus or minus with a value of one in all three modes. This implies just a little and regular correction have to be performed to get the exactly right value of q and r from q′ and r′ respectively. The detailed flow chart of the proposed algorithm for the arithmetic operations in the above three modes shown in FIG. 3 is depicted in FIG.  4 . 
     A method of degrouping a codeword according to the flow chart shown in FIG. 4 will be described hereinafter. A codeword to be degrouped has n bits and is grouped by: 
     
       
           A =(2 p +1) 2   z +(2 p +1) y+x   
       
     
     wherein A is the codeword; x, y and z are three consecutive samples; and p is 1, 2 or 3, provided that n=5 and k=4, when p=1; n=7, k=3, when p=2; and n=10, k=3, when p=3. The method of degrouping A to obtain x, y and z comprises carrying out the following steps in an processor: 
     I) feeding p to said processor, and deciding values of n and k; 
     II) feeding A to said processor; 
     III) setting i=1; 
     IV) obtaining 
     q′=q 1 −q 2 +q 3  . . . +(−1) k+1 ·q k , and 
     r′=r 1 −r 2 +r 3  . . . +(−1) k+2 ·r k+1 , 
      wherein 
     q j =(a n−1 , a n−2 , a n−3 , . . . , a jp+1 , a jp ); 
     r j =(a jp−1 , a jp−2 , a jp−3 , . . . , a (j−1)p ); 
     r k+1 =(a kp ) 
     wherein j is an integer of 1 to k; and 
     (a n−1 , a n−2 , a n−3 , . . . , a 1 , a 0 ) is 2-tuple representation of A; 
     V) letting 
     A=q′ and r=r′, when 2 p +1&gt;r′≧0; 
     A=q′−1 and r=r′+(2 p +1), when 0&gt;r′; and 
     A=q′+1 and r=r′−(2 p +1), when 2 p +1≧r′ 
     VI) outputting x=r, when i=1; y=r, when i=2; and z=r, when i=3; 
     VII) setting i=i+1; and 
     VIII) returning to step I), when i=4; and returning to step IV), when i&lt;4. 
     Architecture Design 
     It can be seen from FIG. 3 that four operands are generated by shifting in mode 2 and mode 3. These operands take the interlace computations of two subtractions and one addition. Although five operands are generated and need one extra addition in mode 1, the addition for the last operand of A&gt;&gt;4, a one digit number, can be viewed as an additional carry for the adder. This approach takes the advantage of reducing one addition in mode 1. More specifically, it has been compatible for the computation and architecture design in all three modes. 
     A suitable architecture design is shown in FIG. 5, wherein 10-bit width is given to the codeword A to accommodate mode 3, and the codeword A is shifted right p, 2p and 3p bits by three shifters &gt;&gt;p, &gt;&gt;2p and &gt;&gt;3p respectively to generate three operands A&gt;&gt;p, A&gt;&gt;2p, and A&gt;&gt;3p. The codeword A and A &gt;&gt;p  are fed to a first subtractor SpADD− to yield a first difference S″=A−A &gt;&gt;p , the first difference S″ and A &gt;&gt;2p  are fed to a first adder SpADD+ to yield a first sum S′=(A−A &gt;&gt;p )+A &gt;&gt;p , and the first sum S′ and A &gt;&gt;3p  are then fed to a second subtractor SpADD− to render a total sum S, wherein S=A−A &gt;&gt;p +A &gt;&gt;2p −A &gt;&gt;3p . A first carry co 0 ″ of subtraction for the lowest p bits of S″ (p-bit LSB) is also fed the first adder SpADD+ to yield a second carry co 0 ′ which is a sum of co 0 ″ and a carry of addition for the p-bit LSB of S′, and then the second carry co 0 ′ is fed to the second subtractor SpADD− to yield a final carry co 0  which is the sum of co 0 ′ and a carry of subtraction for the p-bit LSB of S. The final carry co 0  and S are demultiplexed by a de-multiplexer into a quotient q′ and remainder r′. A regular correction have to be performed to get the exactly right value of q and r from q′ and r′ respectively, wherein q=q′ and r=r′, when 2 p +1&gt;r′≧0; q=q′−1 and r=r′+(2 p +1), when 0&gt;r′; and q=q′+1 and r=r′−(2 p +1), when 2 p +1≧r′. Prior to the correction, a 4  is added to r′ if p=1, wherein a 4  is obtained by shifting the codeword A four bits right. Then r is output as a degrouped sample. The corrected quotient q is feedback and latched in the input register (reg) for use in the next degrouping cycle. This approach makes the design with the fixed throughput of one clock number per sample. 
     Based on the previous discussions, the proposed algorithm can be implemented by two subtractions and one addition for four operands A, A &gt;&gt;p , A &gt;&gt;2p , and A &gt;&gt;3p , in all three modes p=1, 2 and 3. In order to reduce the hardware cost, we use the concept of data reordering to change the computation data flow. We compute the operands of A and A &gt;&gt;2p  and the associated arithmetic operation first, then compute the operands of A &gt;&gt;p  and A &gt;&gt;3p  and associated arithmetic operation. In fact the result for A &gt;&gt;p  plus A &gt;&gt;3p  is equal to the result for A plus A &gt;&gt;2p  by only shifting right p bits. This means the arithmetic operation for A &gt;&gt;p  plus A &gt;&gt;3p  is trivial and can be removed. The data reordering scheme can reduce the arithmetic operations in saving of one subtractor chip area and be described in FIG.  6 . 
     For the architecture design, the proposed algorithm with data reordering scheme is adopted. FIG. 7 shows the key components of this design include one special adder (SPADD), two subtractors (−) and two adders (+). Based on the maximum number ranges of codeword A in mode 3, 10-bit width bus is assigned for A. The shifter &gt;&gt;2p takes the right shift of 2p bits to obtain another operand A′ from A. The SPADD generates a 10-bit sum of S, and three one-bit carries of co 0 , co 1  and co 2  . The co 0  is the carry of addition for p-bit LSB, co 2  is the carry of addition for 2p-bit LSB and the co 1  is the carry for all-bit addition. The signals of S, co 0 , and co 1  can be demultiplexed into the partial quotients of q_+ and q_−, and partial remainders r − + and r − −. These partial quotients and partial remainders are fed into the two subtractors (−) to generate the quotient q′ and the remainder r′. The following two adders (+) take the roles of correcting the quotient q′ and the remainder r′ into the real quotient q and the real remainder r. Finally, the real quotient q is treated as an operand for the next degrouping cycle and is feedback and latched in the input register. This approach makes the design with the fixed throughput of one clock number per sample. The detailed correcting steps for generating the real quotient q and the real remainder r from the quotient q′ and the remainder r′ are listed as follows: 
     I) 
     r=r′, when 2 p +1&gt;r′≧0; 
     r=r′+(2 p +1), when 0&gt;r′; 
     r=r′−(2 p +1), when 2 p +1≧r′; and 
     II) 
     q=q′+1, when comprst or co 2  is 1, and co 0  is 0, otherwise 
     q=q′−1, when co 0  is 1 and co 2  is 0, otherwise 
     q=q′, 
     wherein comprst is 1, if r′≧2 p +1 and co 0  is 0, otherwise comprst is 0. Prior to step I), a 4  is added to r′ if p=1, wherein a 4  is obtained by shifting the codeword A four bits right. 
     The internal architecture of the SPADD in FIG. 7 is illustrated in FIG.  8 . It basically consists of four full adders (FA) at the 4-bit LSB and six half adders (HA) at the 6-bit MSB with a ripple-carry architecture. The four full adders carry out the addition of A, A′ and c_ 0  which is the carry represented as the additional operand in mode 1. The carries of addition from the first three full adders are fed to a logic unit so that the carry co 0  of addition for p-bit LSB can be generated therefrom with the help of p (value representing the mode). The carries of addition from the second full adder, the fourth full adder and the second half adder are fed to another logic unit so that the carry co 2  of addition for 2p-bit LSB can be generated therefrom with the help of p (value representing the mode). Each of the six half adders adds A and the carry from its preceding stage so that the carry col for all-bit addition from the last half adder. 
     A degrouping method for use in conjunction with the algorithm and architecture shown in FIGS. 7 and 8 comprises carrying out the following steps in an processor: 
     I) feeding p to said processor, and deciding values of n and k; 
     II) inputting the codeword A to said processor; 
     III) setting i=1; 
     IV) calculating a sum S=A+A &gt;&gt;2p , wherein A &gt;&gt;2p  is obtained by taking a right shift of 2p bits of 2-tuple representation of A, (a n−1 , a n−2 , a n−3 , . . . , a 1 , a 0 ), or calculating a sum S=A+A &gt;&gt;2p +a 4 , when p=1; 
     V) obtaining r —   + , q —   + , co 0 , co 1  , and co 2  , wherein r —   +  is the value of the lowest p bits of S, q —   +  is the value of the upper (n−p) bits of S, co 0  is the carry of addition for the lowest p bits of S, co 2  is the carry of addition for the lowest 2p bits of S, and co 1  I is the carry for all-bit addition of S; 
     VI) obtaining an operand S &gt;p  having (n−p) bits by taking a right shift of p bits of S, and obtaining r —   − , q —   − , wherein r —   −  is the value of the lowest p bits of S &gt;p , q —   −  is the value of the upper (n−2p) bits of S &gt;p ; 
     VII) calculating 
     q′=q —   + −q —   − , 
     r′=r —   + −r —   − , 
     VIII) 
     r=r′, when 2 p +1&gt;r′≧0; 
     r=r′+(2 p +1), when 0&gt;r′; 
     r=r′−(2 p +1), when 2 p +1≧r′; 
     IX) 
     A=q′+1, when comprst or co 2  is 1, and co 0  is 0, otherwise 
     A=q′−1, when co 0  is 1 and co 2  is 0, otherwise 
     A=q′, 
     wherein comprst is 1, if r′≧2 p +1 and co 0  is 0, otherwise comprst is 0; 
     X) outputting x=r, when i=1; y=r, when i=2; and z=r, when i=3; 
     XI) setting i=i+1; and 
     XII) returning to step I), when i=4; and returning to step IV), when i&lt;4. 
     EXPERIMENTAL RESULTS 
     In this section, we describe the experimental results performed by the algorithms proposed in the present invention. For the sake of brevity, we only present experimental data for mode 1 as shown in FIGS. 9 a  and  9   b . It graphically shows the deviation of q′ with respect to q, and r′ with respect to r. Most of the values q′ and r′ are equal to q and r, respectively. Specifically, it shows each point with the value of r which is greater than 2 has the value of q′ which is less than q. The point with the value r which is less than 0 has the value of q′ which is greater than q. All the differences between the q′ and q are equal to one, zero or minus one. 
     Besides, the proposed degrouping architecture is implemented as a processor with some related technical details summarized in Table 3. In addition to regularity and modularity, this architecture have significant advantages in term of small area and high speed based on the applied technology. 
     
       
         
               
             
               
               
               
             
           
               
                 TABLE 3 
               
               
                   
               
               
                 Statistical result of implemented degrouping processor 
               
               
                   
               
             
             
               
                   
               
             
          
           
               
                   
                 Technology 
                 0.6μ CMOS SPDM 
               
               
                   
                 Gate count 
                 576 
               
               
                   
                 Area 
                 510 × 454 μ 2 m 
               
               
                   
                 Measured propagation delay 
                 21.05 ns