# Patent

## Title
Digital circuit

## Abstract

Disclosed is a digital circuit which comprises input signals A[n−1:0], SH[log2n−1:0], and DAT[n−1:0], a barrel shifter for outputting data B[n−1:0] obtained by shifting the signal DAT by the bits of the signal SH, a group G·P·SUM computation stage for dividing each of the digits of the input signals A and B into groups of m bits, and computing Gs, Ps, and addition results SUM0 when carry inputs are high and addition results SUM1 when the carry inputs are low, a carry computation circuit for computing a carry for each of the groups, and a SUM selection stage for selecting a SUM0 or a SUM1 computed for each of the groups according to each carry output by the carry computation circuit.

## Background
FIELD OF THE INVENTION
The present invention relates to a digital circuit.
BACKGROUND OF THE INVENTION
In recent years, with development of portable terminals, speeding up of data processing has become essential, so that speeding up of computation processing of RISC CPUs mounted on portable terminals is also required. When compression and expansion of a photograph image (in JPEG format) is performed in the portable terminal, for example, a DCT (Discrete Cosine Transform)/quantitization/inverse-quantitization techniques are employed. Speeding up of multiplication is then required.
Generally, for the multiplication by the RISC CPU, there are provided a method of using a barrel shifter and an adder and a method of using a multiplier. A program compiler makes a decision as to which method is faster according to a multiplier, and determines the method. The case where the multiplication is executed using the barrel shifter and the adder is the case where a multiplier factor 2m+1 (m≧1) is applied on a certain number A, for example. In this case, the certain number A is shifted in the left by m bits by the barrel shifter to produce 2m·A. Then, 2m·A+A is executed by the adder to obtain the solution. Since the latencies of the barrel shifter and the adder of the RISC CPU are generally one clock cycle, respectively, the latency of this multiplication becomes two clock cycles. The latency of the multiplier is three clock cycles. Thus, if the barrel shifter and the adder are used, the multiplication can be performed faster by one clock cycle than in the case where the multiplier is used.
In ARM CPUs, the barrel shifter and the adder are connected in series so that the multiplication is executed in one clock cycle. Then, the latency in the method of using the barrel shifter and the adder is thereby reduced to achieve speeding up of the multiplication. The multiplication described before can be thereby implemented in one clock cycle. Further, the multiplication in which the multiplier factor applied on the certain number A is 2m+n+2m+2n+1 =(2m+1)(2n+1) can also be implemented in two clock cycles.
[Patent Document 1]
JP Patent Kokai Publication No. JP-P2000-163251A
SUMMARY OF THE DISCLOSURE
However, since the delays of the barrel shifter and the adder are large, this path often becomes critical (refer to FIG. 5).
The present invention has been made in view of the circumstances described above.
A digital circuit according to the present invention includes:
a computation unit for receiving a signal a of two of the signal a and a signal b both with a number of bits therein being m, wherein the signals a and b range from zero to 2m−1, and calculating for the signal a and each of 2m values of zero to 2m−1 a carry generate term Gi, a carry propagate term Pi, and a sum Si, wherein i ranges from zero to 2m−1, for output; and
a selection unit for receiving the carry generate term Gi, the carry propagate term Pi, and the sum Si computed by the computation unit and the signal b, and selecting the carry generate term Gb, the carry propagate term Pb, and the sum Sb when i is equal to the signal b, for output.
In the digital circuit according to the present invention, the computation unit performs computation between the signal a and all of the possible values of the signal b, irrespective of the values of the signal b. Then, the correct one of the results of the computation is selected by the selection unit. For this reason, when this digital circuit is employed for part of the adder and the signal b is connected to the output of the barrel shifter, part of an addition operation and the operation of the barrel shifter can be performed simultaneously. Accordingly, the digital circuit that can speed up a multiplication operation is implemented.
On contrast therewith, a conventional circuit in which the barrel shifter is connected to the adder in series has no choice but to perform the addition operation after waiting for the output of the barrel shifter. Thus, the conventional circuit is insufficient in terms of speeding up of the multiplication operation.
In the present invention, the selection unit may output a sum S0b, which is the sum Sb when a carry input is zero and a sum S1b, which is the sum Sb when the carry input is one, respectively. In this case, the circuit can perform computation in regard to the result of the addition (the sum S0b or the sum S1b) without waiting for computation of a carry input. Accordingly, the digital circuit that can further speed up the multiplication operation is implemented.
The digital circuit according to the present invention may further include:
a carry computation unit for receiving the carry generate term Gb and the carry propagate term Pb to compute the carry input, for output; and
a second selection unit for selecting either of the sum S0b and the sum S1b according to the carry input computed by the carry computation unit, for output.
In this case, an addition circuit that can speed up the multiplication operation is implemented.
The digital circuit according to the present invention may further include a barrel shifter for outputting the signal b to be input to the selection unit. In this case, a multiplication circuit that can perform the multiplication operation at a faster speed is implemented.
The meritorious effects of the present invention are summarized as follows.
According to the present invention, the digital circuit that can speed up the multiplication operation is implemented.
Still other advantages of the present invention will become readily apparent to those skilled in this art from the following detailed description in conjunction with the accompanying drawings wherein only the preferred embodiments of the invention are shown and described, simply by way of illustration of the best mode contemplated of carrying out this invention. As will be realized, the invention is capable of other and different embodiments, and its several details are capable of modifications in various obvious respects, all without departing from the invention. Accordingly, the drawing and description are to be regarded as illustrative in nature, and not as restrictive.



BRIEF DESCRIPTION OF THE DRAWINGS
FIG. 1 is a diagram showing a configuration of a digital circuit according to an embodiment of the present invention;
FIG. 2 is a diagram showing a configuration of a group G·P·Sum computation circuit according to the embodiment of the present invention;
FIG. 3 is a diagram showing a detailed configuration of a G·P·Sum computation element according to the embodiment of the present invention;
FIG. 4 is a diagram showing a critical path in the circuit in FIG. 1;
FIG. 5 is a diagram showing a digital circuit according to a prior art;
FIG. 6 is a diagram showing an n-bit barrel shifter;
FIG. 7 is a diagram showing a shift circuit for each bit used in the barrel shifter;
FIG. 8 is a diagram showing an eight-bit carry computation circuit according to the prior art; and
FIG. 9 is a diagram showing a critical path in the circuit in FIG. 5.



PREFERRED EMBODIMENTS OF THE INVENTION
A preferred embodiment of a digital circuit according to the present invention will be described in detail with reference to drawings. For description of the drawings, the same reference characters are assigned to the same elements, and a repetitive description will be omitted.
FIG. 1 is a diagram showing an embodiment of the digital circuit according to the present invention. This circuit comprises input signals A[n−1:0], SH[log2n−1:0], and DAT[n−1:0] a barrel shifter for outputting data B[n-1:0] obtained by shifting the signal DAT by the bits represented by the signal SH, a group G·P·SUM computation stage for dividing each of the digits of the signal A and the data B into groups of m bits and computing Gs, Ps, addition results SUM0 when carry inputs are low and addition results SUM1 when the carry inputs are high, a carry computation circuit for computing a carry for each of the groups, and an SUM selection stage for selecting a SUM0 or a SUM1 calculated for each of the groups according to each carry output by the carry computation circuit.
Since the configuration of the group G·P·SUM computation stage is complex, a description will be first given to (k+1) group G·P·SUM computation circuits constituting the group G·P·SUM computation stage, in which k is the quotient of n divided by m. Then, a description will be next directed to the detailed configurations of the group G·P·SUM computation stage, carry computation circuit, and SUM selection stage, in this stated order.
Each group G·P·SUM computation circuit has input terminals a and b for inputting respective m bits of the A and the B, and output terminals Gb, Pb, SUM0 and SUM1 for outputting a group carry generate term, a group carry propagate term, the result of addition when an input of a carry from a lower bit is low and the result of addition when the input of the carry from the lower bit is high, respectively. As shown in FIG. 2, this group G·P·SUM computation circuit is constituted from 2m modules each constituted from a G·P computation circuit (refer to FIG. 8) and an adder (which will be referred to as G·P·SUM computation elements) and four selectors.
A first G·P·SUM computation element outputs results of computation of G, P, and SUM with respect to the input terminal a and zero as a G0, a P0 and an SUM0. A second G·P·SUM computation element outputs results of computation of G, P, and SUM with respect to the input terminal a and one as a G1, a P1 and an SUM1. A third G·P·SUM computation element outputs results of computation of G, P, and SUM with respect to the input terminal a and two as a G2, a P2 and an SUM2. An ith G·P·SUM computation element (in which 1≦i≦2m) outputs results of computation G, P, and SUM with respect to the input terminal a and i−1 as a Gi−1, a Pi−1, and an SUMi−1. Then, a 2m G·P·SUM is output as follows:

G2m−1, P2m−1, SUM2m−1

Four selectors select the values based on Table 1, according to an input signal b.











TABLE 1





b
Gb
Pb
Sum0
Sum1







0
G0
P0
S0
S1


1
G1
P1
S1
S2


2
G2
P2
S2
S3


3
G3
P3
S3
S4


.
.
.
.
.


.
.
.
.
.


.
.
.
.
.


2m − 2
G2m−2
P2m−2
S2m−2
S2m−1


2m − 1
G2m−1
P2m−1
S2m−1
S0









The detailed configurations of respective units constituting the circuit in FIG. 1 will be described below.
The G·P·SUM computation stage comprises a group G·P·SUM computation circuit 0, a second group G·P·Sum computation circuit 1, a group G·P·Sum computation circuit i, and a group G·P·Sum computation circuit k. The group G·P·SUM computation circuit 0 receives an A[m−1:0] of the input signal A (m≦n) and a B[m−1:0] of the shifted data B at the input terminals a and b thereof, respectively, and outputs a group carry generate term G0,m−1, a group carry propagate term P0,m−1, an addition result SUM00 when the input of a carry from a lower bit is low and an addition result SUM10 when the input of the carry from the lower bit is high. The second group G·P·SUM computation circuit 1 outputs a group carry generate term Gm,2m−1, a group carry propagate term Pm,2m−1, an addition result SUM01 when the input of a carry from a lower bit is low, and an addition result SUM11 when the input of the carry from the lower bit is high, for an A[2m−1:m] and a B[2m−1:m]. The group G·P·SUM computation circuit i outputs a group carry generate term Gim,(i+1)m−1, a group carry propagate term Pim,(i+1)m−1, an addition result SUM01 when the input of a carry from a lower bit is low, and an addition result SUM11 when the input of the carry from the lower bit is high, for an A[im−1:(i−1)m] and a B[im−1:(i−1)m], (in which 0≦i≦k) (and in which k is the quotient of n divided by m). The group G·P·SUM computation circuit k outputs a group carry generate term Gkm,n−1, a group carry propagate term Pkm,n−1, an addition result SUM0k when the input of a carry from a lower bit is low, and an addition result of SUM1k when the input of the carry from the lower bit is high, for an A[n−1:km] and a B[n−1:km].
As the carry computation circuit, a CLA (Carry Look Ahead) circuit, for example, is used, as in the prior art. The carry computation circuit receives the G0,m−1, the P0,m−1, and a carry input c0 from the adder, and outputs a carry input Cm for the mth digit according to the following equation (9). The carry computation circuit receives the Gim,(i+1)m−1, Pim,(i+1)m−1, c0 and outputs a carry input cim for the 2mth digit, and receives Gkm,n−1, Pkm,n−1, and c0 for output of a carry output ckm of the adder.
The SUM computation stage comprises a selector SEL 0, a selector SEL 1, a SEL i, and a selector SEL k. The selector SEL 0 receives SUM00, SUM10, and c0 and outputs the SUM00 when the c0 is low, and outputs the SUM10 when the c0 is high. The selector SEL 1 receives the SUM01, SUM11, and cm, and outputs the SUM01 when the cm is low and outputs the SUM11, when the cm is high. The SEL i receives the SUM0i, SUM1i, and cim, and outputs the SUM0i when the cim is low and outputs the SUM1i when the cim is high, (in which 0≦i≦k). The selector SEL k receives the SUM0k, the SUM1k, and a Ck, and outputs the SUM0k when the ckm is low, and outputs the SUM1k when the ckm is high.
In the embodiment described above, a configuration is shown in which four selectors are provided for each group G·P·SUM computation circuit, and among those, two selectors output the result of addition when the input of a carry is low and the result of addition when the input of the carry is high, respectively. It may also be configured that the outputs of the respective G·P·SUM calculating elements are output without alteration. More specifically, it may be so configured that one of the selectors selects a SUMb corresponding to the input signal b among the values of SUMi computed on all i (in which 0≦i≦2m−1) by the G·P·SUM calculating elements, for output.
A difference between delay times of the circuit in FIG. 1 and a circuit according to the prior art will be determined below. For this purpose, the delay of a critical path when the barrel shifter is connected in series with the adder in the prior art (refer to FIG. 5) will be discussed.
(Delay of Barrel Shifter)
When an input data signal is indicated by a, an input shift data signal is indicated by sh, a left/right shift selection signal is indicated by sel, and an output signal is indicated by b in an n-bit shifter, b is expressed by the following logic equation:




  
    
      
        b
        =
        
          {
          
            
              
                
                  a
                  ⪡
                  sh
                
              
              
                
                  (
                  
                    sel
                    =
                    1
                  
                  )
                
              
            
            
              
                
                  a
                  ⪢
                  sh
                
              
              
                
                  (
                  
                    sel
                    =
                    0
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        1
        )
      
    
  




Herein, << indicates a left shift, while >> indicates a right shift. When the sh is assumed to be an n-bit signal, and shi is assumed to be the sh in the ith digit, the sh can be expanded as follows:

sh=shn−l·2n−1+shn−2·2n−2+ . . . +sh2·22+sh1·21+sh0·20  (2)

Based on the above equations (1) and (2), the b can be expanded as follows:




  
    
      
        b
        =
        
          {
          
            
              
                
                  a
                  ⪡
                  
                    (
                    
                      
                        sh
                        0
                      
                      ·
                      
                        2
                        0
                      
                    
                    )
                  
                  ⪡
                  
                    (
                    
                      
                        sh
                        1
                      
                      ·
                      
                        2
                        1
                      
                    
                    )
                  
                  ⪡
                  
                    (
                    
                      
                        sh
                        2
                      
                      ·
                      
                        2
                        2
                      
                    
                    )
                  
                  ⪡
                  ⋯
                  ⪡
                  
                    (
                    
                      
                        sh
                        
                          n
                          -
                          1
                        
                      
                      ·
                      
                        2
                        
                          n
                          -
                          1
                        
                      
                    
                    )
                  
                
              
              
                
                  (
                  
                    sel
                    =
                    1
                  
                  )
                
              
            
            
              
                
                  a
                  ⪢
                  
                    (
                    
                      
                        sh
                        0
                      
                      ·
                      
                        2
                        0
                      
                    
                    )
                  
                  ⪢
                  
                    (
                    
                      
                        sh
                        1
                      
                      ·
                      
                        2
                        1
                      
                    
                    )
                  
                  ⪢
                  
                    (
                    
                      
                        sh
                        2
                      
                      ·
                      
                        2
                        2
                      
                    
                    )
                  
                  ⪢
                  ⋯
                  ⪢
                  
                    (
                    
                      
                        sh
                        
                          n
                          -
                          1
                        
                      
                      ·
                      
                        2
                        
                          n
                          -
                          1
                        
                      
                    
                    )
                  
                
              
              
                
                  (
                  
                    sel
                    =
                    0
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        3
        )
      
    
  




The barrel shifter constitutes a circuit which determines the amount of a shift for each bit of the sh, based on the equation (3).
A configuration of a left shifting n-bit barrel shifter (as shown in FIG. 6) and its operation will be shown. The n-bit barrel shifter comprises an n-bit input data signal A[n−1:0] to the barrel shifter, m-bit shift amount input data SH[m−1:0](m=log2n), a shifted output data signal B[n−1], a first shift circuit, a second shift circuit, and an mth shift circuit. The first shift circuit outputs the one-bit shifted value of an A[m−1:0] to an output signal dat1[n−1:0] when SH[0] is high, and outputs the value of the A[m−1:0] without alteration to the output signal dat1[n−1:0] when the SH[0] is low. The second shift circuit outputs the two-bit shifted value to an output signal dat2[n−1:0] when SH[1] is high, and the value without alteration to the output signal dat2[n−1:0] when the SH[1] is low. The mth shift circuit outputs the m-bit shifted value of input data datm−1[n−1:0] when SH[m−1] is high, and outputs the value of the input data datam−1[n−1:0] without alteration to an output signal datm[n−1:0] when the SH[m−1] is low.
Each shift circuit is constituted using a circuit in FIG. 7, for each bit. The circuit in FIG. 7 constitutes a logic expressed as follows, by using the input signals a and b, an input signal c and an output signal d.

d=a c−+bc

The first shift circuit is constituted by connecting the signals to the circuit in FIG. 7 as follows:




  
    
      
        
          
            
              a
              =
              
                A
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
        
          
            
              b
              =
              
                {
                
                  
                    
                      
                        A
                        ⁡
                        
                          [
                          
                            i
                            +
                            1
                          
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          0
                          ≤
                          i
                          ≤
                          
                            n
                            -
                            2
                          
                        
                        )
                      
                    
                  
                  
                    
                      
                        A
                        ⁡
                        
                          [
                          0
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          i
                          =
                          
                            n
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
        
          
            
              c
              =
              
                SH
                ⁡
                
                  [
                  0
                  ]
                
              
            
          
        
        
          
            
              d
              =
              
                
                  dat
                  1
                
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
      
    
    
      
        (
        4
        )
      
    
  




The second shift circuit is constituted by connecting the signals to the circuit in FIG. 7 as follows:




  
    
      
        
          
            
              a
              =
              
                
                  dat
                  1
                
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
        
          
            
              b
              =
              
                {
                
                  
                    
                      
                        
                          dat
                          1
                        
                        ⁡
                        
                          [
                          
                            i
                            +
                            2
                          
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          0
                          ≤
                          i
                          ≤
                          
                            n
                            -
                            3
                          
                        
                        )
                      
                    
                  
                  
                    
                      
                        
                          dat
                          1
                        
                        ⁡
                        
                          [
                          
                            i
                            -
                            n
                            +
                            2
                          
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          
                            n
                            -
                            2
                          
                          ≤
                          i
                          ≤
                          
                            n
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
        
          
            
              c
              =
              
                SH
                ⁡
                
                  [
                  1
                  ]
                
              
            
          
        
        
          
            
              d
              =
              
                
                  dat
                  2
                
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
      
    
    
      
        (
        5
        )
      
    
  




The mth shift circuit is constituted by connecting the signals to the circuit in FIG. 7 as follows:




  
    
      
        
          
            
              a
              =
              
                
                  dat
                  
                    m
                    -
                    1
                  
                
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
        
          
            
              b
              =
              
                {
                
                  
                    
                      
                        
                          dat
                          
                            m
                            -
                            1
                          
                        
                        ⁡
                        
                          [
                          
                            i
                            +
                            m
                          
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          0
                          ≤
                          i
                          ≤
                          
                            n
                            -
                            m
                          
                        
                        )
                      
                    
                  
                  
                    
                      
                        
                          dat
                          
                            m
                            -
                            1
                          
                        
                        ⁡
                        
                          [
                          
                            i
                            -
                            n
                            +
                            m
                          
                          ]
                        
                      
                    
                    
                      
                        (
                        
                          
                            n
                            -
                            m
                            +
                            1
                          
                          ≤
                          i
                          ≤
                          
                            n
                            -
                            1
                          
                        
                        )
                      
                    
                  
                
              
            
          
        
        
          
            
              c
              =
              
                SH
                ⁡
                
                  [
                  
                    m
                    -
                    1
                  
                  ]
                
              
            
          
        
        
          
            
              d
              =
              
                
                  dat
                  m
                
                ⁡
                
                  [
                  i
                  ]
                
              
            
          
        
      
    
    
      
        (
        6
        )
      
    
  




The circuit configuration of a right shift circuit is the same just except that the orientation of a shift in the right shift circuit is changed.
Since the paths of each shift circuit are the same, the delay time of each shift circuit is uniquely determined. Herein, the delay time of the barrel shifter in FIG. 6 is indicated by Tbarrel, while the delay of the shift circuit in FIG. 7 is indicated by a. When the number of bits of input data to the barrel shifter is indicated by n, the number of the shift circuits connected in series becomes log2n, so that the delay time of the barrel shifter can be expressed as follows:

Tbarrel=α·log2n  (7)

(Delay of Adder)
When the ith digits of the input signals to an n-bit carry look ahead adder are indicated by ai, bi, respectively, an ith digit carry propagate term pi, an ith digit carry generate term gi, a carry output ci+1 for an (i+1)th digit, and a sum output sumi for the ith digit can be defined using the following logic equations:

pi=ai+bi

gi=ai·bi

sumi=ai⊕bi⊕ci

ci+1=gi+pi·ci  (8)

where + indicates a logical sum, · indicates a logical product, and ⊕ indicates an exclusive logical sum. If ci is expanded with respect to a group from the hth digit to the ith digit (in which h≦i, and h and i are arbitrary numbers, respectively)




  
    
      
        
          
            
              
                c
                
                  i
                  +
                  1
                
              
              =
              
              ⁢
              
                
                  g
                  i
                
                +
                
                  
                    p
                    i
                  
                  ⁡
                  
                    (
                    
                      
                        g
                        i
                      
                      +
                      
                        
                          p
                          i
                        
                        ⁢
                        
                          c
                          i
                        
                      
                    
                    )
                  
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  g
                  i
                
                +
                
                  
                    p
                    i
                  
                  ⁢
                  
                    g
                    
                      i
                      -
                      1
                    
                  
                
                +
                
                  
                    p
                    i
                  
                  ⁢
                  
                    
                      p
                      
                        i
                        -
                        1
                      
                    
                    ·
                    
                      (
                      
                        
                          g
                          
                            i
                            -
                            1
                          
                        
                        +
                        
                          
                            p
                            
                              i
                              -
                              1
                            
                          
                          ·
                          
                            c
                            
                              i
                              -
                              1
                            
                          
                        
                      
                      )
                    
                  
                
              
            
          
        
        
          
            
              
              ⁢
              ⋮
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  g
                  i
                
                +
                
                  
                    p
                    i
                  
                  ⁢
                  
                    g
                    
                      i
                      -
                      1
                    
                  
                
                +
                
                  
                    p
                    i
                  
                  ⁢
                  
                    p
                    
                      i
                      -
                      1
                    
                  
                  ⁢
                  
                    g
                    
                      i
                      -
                      2
                    
                  
                
                +
                ⋯
                +
                
                  
                    p
                    i
                  
                  ⁢
                  
                    p
                    
                      i
                      -
                      1
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  ⋯
                  ⁢
                  
                    
                  
                  ⁢
                  
                    p
                    
                      h
                      +
                      1
                    
                  
                  ⁢
                  
                    g
                    h
                  
                
                +
              
            
          
        
        
          
            
              
              ⁢
              
                
                  p
                  i
                
                ⁢
                
                  p
                  
                    i
                    -
                    1
                  
                
                ⁢
                
                  p
                  
                    i
                    -
                    2
                  
                
                ⁢
                
                  
                
                ⁢
                ⋯
                ⁢
                
                  
                
                ⁢
                
                  p
                  
                    h
                    +
                    1
                  
                
                ⁢
                
                  p
                  h
                
                ⁢
                
                  c
                  h
                
              
            
          
        
        
          
            
              =
              
              ⁢
              
                
                  G
                  
                    h
                    ,
                    i
                  
                
                +
                
                  
                    P
                    
                      h
                      ,
                      i
                    
                  
                  ⁢
                  
                    c
                    h
                  
                
              
            
          
        
      
    
    
      
        (
        9
        )
      
    
  




in which Gh,i, Ph,i are expressed as follows:

Gh,i=gi+pigi−1+pipi−1gi−1+ . . . +pipi−1pi−2 . . . ph+1gh

Ph,i=pipi−1pi−2 . . . pk+1pk  (10)

in which Gi,i=gi, and Pi,i=pi.
In this case, Gh,i denotes the group carry generate term from the hth digit to the ith digit, while Ph,i denotes the group carry propagate term from the hth digit to the ith digit. The Gh,i will be hereinafter referred to as the group carry generate term, and the Ph,i will be hereinafter referred to as the group carry propagate term.
The above equation (10) can be rewritten as the following equation (in which j is an arbitrary integer, and h≦j<i))

Gh,i=Gj+1,i+Pj+1,iGh−j

Ph,i=Ph,jPj+1,i  (11)

The equation (11) indicate that “when a carry is output from the group from the hth digit to the ith digit, the carry is generated in the upper portion (j+1, i) of the group, or the carry from the lower portion (h, j) is propagated to the upper portion”. Accordingly, it can be found that by appropriately selecting the bit lengths of a certain group and the group of bits lower than those of the certain group, generation of the carry generate term and the carry propagate term for the upper group and the carry generation for the lower group can be processed in parallel. Further, by adopting hierarchization of the above mentioned configuration, addition of multi-bit lengths can be sped up. The common adder which has adopted the carry look ahead method as described above appropriately selects the bit length, thereby processing carry generation and generation of the carry generate term and the carry propagate term in parallel.
The configuration and the operation of the n-bit carry look ahead adder in FIG. 5, will be described in the below as a comparative example. Referring to FIG. 5, the n-bit carry look ahead adder (CLA) is constituted from a pg generation circuit 0, a pg generation circuit 1, a pg generation circuit i, a pg generation circuit n−1, a carry computation circuit, and an exclusive OR circuit. The pg generation circuit 0 receives the respective 0th (least significant) digits A0 and B0 of the input signals A and B and outputs a carry generate term G0,0 and a carry propagate term P0,0. The pg generation circuit 1 receives the respective first digits A1 and B1 of the input signals A and B and outputs a carry generate term G1,1 and a carry propagate term P1,1. The pg generation circuit i receives the respective ith digits Ai and Bi of the input signals A and B, in which 0≦i≦n−1, and outputs a carry generate term Gi,i and a carry propagate term Pi,i. The pg generation circuit n−1 receives the respective n−1th digits An−1 and Bn−1 of the input signals A and B and outputs a carry generate term Gn−1, n−1 and a carry propagate term Pn−1, n−1. The carry computation circuit receives the Gi,i and the Pi,i, and outputs the i+1th carry Ci+1 (refer to the equation (8)). The exclusive OR circuit receives the Ai, Bi, and Ci and outputs the addition result sums (refer to the equation (8)).
The carry computation circuit calculates the output of the carry Ci+1 using the formulas of the group carry generate term G and the group carry propagate term P shown in the equations (9) and (11). FIG. 8 shows an eight-bit carry computation circuit in which a group is constituted from two digits (j−h=i−j=2). This carry computation circuit is constituted from second-stage G·P combinational circuits, each for receiving the two Gs and the two Ps outputted from G·P combinational circuits in the first stage and outputting combined outputs of the G and the P, third-stage G·P combinational circuits, each for receiving the two Gs and the two Ps in the second stage, and outputting combined outputs of the G and the P, and carry output circuits, each for receiving the G, P, and c0 in the third stage and outputting a carry. In the case of an n-bit carry computation circuit for respective M groups (in which M and n are arbitrary integers), the G·P combinational circuits compute respective M combined results of the G and the P, so that the number of stages becomes logMn. Meanwhile, when the G·P computation circuit is constituted from a CMOS circuit, the number of fan-ins is often limited to four or less for a higher-speed operation, in most instances.
Next, the delay of the adder in the prior art will be determined. The delays of the pg generation circuits and the exclusive OR circuits can be defined irrespective of the number of bits for the adder. Thus, when the delay of the G·P combinational circuits is indicated by β and a combination of the delays of the pg generation circuits and the exclusive OR circuits is indicated by γ, a delay Tadder of the adder can be expressed as follows:

Tadder=β·logMn+γ  (12)

(Overall Delay)
Based on the foregoing description, in the prior art, in which the barrel shifter and the adder are connected in series, the critical path becomes a portion indicated by an arrow line in FIG. 9, so that the delay Told is defined as follows, based on the equations (7) and (12).

Told=Tbarrel+Tadder+α·log2n+β·logMn+γ  (13)

Next, the delay of the critical path of the circuit according to the present embodiment shown in FIG. 1 will be considered. Referring to FIG. 1, it is assumed that preceding stages for the input signals SH and DAT supplied to the barrel shifter and the input signal A supplied to the adders are flip-flops. When data is input from the input signal A, an (i+1)th group G·P·SUM computation circuit (in which 0≦i≦k) outputs a Gbi, a Pbi, the Sum0i, and the Sum1i. A maximum delay Tpat from the input signal A to the output signal of the G·P·SUM computation circuit is defined as follows based on the equation (12), since the delays of the G·P computation circuits are the largest.

Tpat=β·logMm+γ  (14)

Next, a maximum delay Tbar from the input signals SH and DAT to the barrel shifter to the output signal of the circuit according to the present embodiment is defined as follows based on the equation (7).

Tbar=α·log2n  (15)

Since the size of the configuration of the carry computation circuit is smaller than that of the prior art by m bits, a maximum delay Tcarry is defined as follows based on the equation (12).




  
    
      
        
          T
          carry
        
        =
        
          
            β
            ·
            
              log
              M
            
          
          ⁢
          
            n
            m
          
        
      
    
    
      
        (
        16
        )
      
    
  




Based on the foregoing description, when the circuit is constituted from the circuit according to the present invention, the delay of the critical path is defined as follows:




  
    
      
        
          T
          all
        
        =
        
          {
          
            
              
                
                  
                    
                      T
                      pat
                    
                    +
                    
                      T
                      carry
                    
                  
                  =
                  
                    
                      
                        β
                        ·
                        
                          log
                          M
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      m
                    
                    +
                    γ
                    +
                    
                      
                        β
                        ·
                        
                          log
                          M
                        
                      
                      ⁢
                      
                        n
                        m
                      
                    
                  
                
              
              
                
                  (
                  
                    
                      T
                      pat
                    
                    ≥
                    
                      T
                      bar
                    
                  
                  )
                
              
            
            
              
                
                  
                    
                      T
                      bar
                    
                    +
                    
                      T
                      carry
                    
                  
                  =
                  
                    
                      
                        α
                        ·
                        
                          log
                          2
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    +
                    
                      
                        β
                        ·
                        
                          log
                          M
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        n
                        m
                      
                    
                  
                
              
              
                
                  (
                  
                    
                      T
                      pat
                    
                    <
                    
                      T
                      bar
                    
                  
                  )
                
              
            
          
        
      
    
    
      
        (
        17
        )
      
    
  




In the above equation (17), m≧2, and m<n and hence Tpat<Tbar holds. Thus, the following equation is obtained (refer to FIG. 4).




  
    
      
        
          T
          new
        
        =
        
          
            
              T
              bar
            
            +
            
              T
              carry
            
          
          =
          
            
              
                α
                ·
                
                  log
                  2
                
              
              ⁢
              
                
              
              ⁢
              n
            
            +
            
              
                β
                ·
                
                  log
                  M
                
              
              ⁢
              
                
              
              ⁢
              
                n
                m
              
            
          
        
      
    
    
      
        (
        18
        )
      
    
  




A delay difference Tdif between a critical path delay Told of a conventional circuit shown in FIG. 9 and a critical path delay Tnew of a circuit in the above embodiment shown in FIG. 4 is obtained as follows, based on the equations (13) and (18).




  
    
      
        
          
            
              
                T
                dif
              
              =
              
                
                  T
                  new
                
                -
                
                  T
                  old
                
              
            
          
        
        
          
            
              =
              
                
                  (
                  
                    
                      
                        α
                        ·
                        
                          log
                          2
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    +
                    
                      
                        β
                        ·
                        
                          log
                          M
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    +
                    γ
                  
                  )
                
                -
                
                  (
                  
                    
                      
                        α
                        ·
                        
                          log
                          2
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      n
                    
                    +
                    
                      
                        β
                        ·
                        
                          log
                          M
                        
                      
                      ⁢
                      
                        
                      
                      ⁢
                      
                        n
                        m
                      
                    
                  
                  )
                
              
            
          
        
        
          
            
              =
              
                
                  
                    β
                    ·
                    
                      log
                      M
                    
                  
                  ⁢
                  
                    
                  
                  ⁢
                  m
                
                +
                γ
              
            
          
        
      
    
    
      
        (
        19
        )
      
    
  




Since m>1, logMm is a positive value. Accordingly, the operation can be performed faster than that of the conventional circuit just by Tdif.
As described above, according to the circuit in FIG. 1, by using the output signal of the barrel shifter as a selection signal in the combinational circuit in which the barrel shifter and the adders are connected in series, the effect of enabling the faster operations of the adders can be brought about.
It should be noted that other objects, features and aspects of the present invention will become apparent in the entire disclosure and that modifications may be done without departing the gist and scope of the present invention as disclosed herein and claimed as appended herewith.
Also it should be noted that any combination of the disclosed and/or claimed elements, matters and/or items may fall under the modifications aforementioned.

## Claims

1. A digital circuit comprising:
a computation unit for receiving a signal a out of the signal a and a signal b both with a number of bits being m, wherein the signals a and b range from zero to 2m−1, and calculating and outputting for the signal a and each of 2m values of zero to 2m−1, a carry generate term Gi, a carry propagate term Pi, and a sum Si, where an index i ranges from zero to 2m−1; and
a selection unit for receiving the carry generate term Gi, the carry propagate term Pi, and the sum Si calculated by said computation unit and the signal b, and selecting the carry generate term Gb, the carry propagate term Pb, and the sum Sb when i is equal to the signal b, for output.

2. The digital circuit according to claim 1, wherein said selection unit outputs a sum S0b and a sum S1b, respectively, the sum S0b being the sum Sb when a carry input is zero and the sum S1b being the sum Sb when the carry input is one.

3. The digital circuit according to claim 2, further comprising:
a carry computation unit for receiving the carry generate term Gb and the carry propagate term Pb to calculate the carry input to output the calculated carry input; and
a second selection unit for selecting either of the sum S0b and the sum S1b according to the carry input computed by said carry computation unit to output the selected sum.

4. The digital circuit according to claim 1, further comprising:
a barrel shifter for outputting the signal b to be supplied to said selection unit.

5. A digital circuit comprising:
a computation unit for receiving a first signal out of first and second signals both having a predetermined number of bits, and calculating and outputting for the first signal and each of values which the second signal can take, a carry generate term, a carry propagate term, and a sum;
a selection unit for receiving a plurality of carry generate terms, a plurality of carry propagate terms, and a plurality of the sums, calculated by said computation unit for respective values which the second signal can take, and the second signal, and selecting, for output, the i-th carry generate term, the i-th carry propagate term, and the i-th sum, wherein the index i is equal to the value of the second signal.

6. The digital circuit according to claim 5, wherein said selection unit outputs two kinds of i-th sums in association with respective cases of a carry input being zero and one, with the index i being equal to the value of the second signal.

7. The digital circuit according to claim 5, further comprising a barrel shifter for receiving a data signal and shift signal and for shifting the data signal by a bit number specified by the shift signal to output the shifted data signal as the second signal supplied to said selection unit.