Re: Unit Adder (4-2 compressor) in Booth-Wallace multiplier

On 2003-10-15, James Shay <[EMAIL PROTECTED]> wrote:
>  Could anyone tell me a little more detail of the unit adder (4-2
>  compress)? The logic in M Nagamatsu's paper is different than some
>  articles on the website. The Cout should only depends on 4 input bit,
>  rather on Cin. From Nagamatsu's paper,
> 
>  Cout = (x0 or x1) and (x3 or x3). 
> 
>  This means if input X = (1100), then Cout is '0', while if the input
>  is (1010), then Cout is 1. Shouldn't all input bits have basic
>  property of commutative, ie. a+b = b+a?

The 4:2 compressor actually takes 5 inputs and gives 3 outputs, where
one input is the "horizontal input" and one output is the "horizontal
output". The three output bits taken as a whole are commutative, as
indeed they need to be. However, the most significant bit (MSB) of
the output has the same weighting as the horizontal output bit. 

          A  B  C  D
          |  |  |  |
        --------------
HO <----|            |<---- HI
        |            |
        --------------
           |     |
          MSB   LSB

In this diagram, the inputs are A, B, C, D, and HI; and the outputs
are LSB (least significant bit), MSB, and HO. The MSB has
significance equal to that of the HO, and both have significance
greater than the LSB.

In order to get a "normal" binary sum from a (4:2) compressor, the
MSB and HO can be added. 

Examples

Outputs are:

     MSB   LSB
      0     0
     
      HO
      1

Actual sum of inputs is:
          010

Outputs are:

     MSB   LSB
      1     0
     
      HO
      1

Actual sum of inputs is:
          100

Outputs are:

     MSB   LSB
      1     0
     
      HO
      0

Actual sum of inputs is:
          010

So (a+b) might not give the same MSB as (b+a), but the LSBs will be
the same, and the MSB and HO will be interchangeable (eg a+b gives
MSB=1, HO=0; b+a gives MSB=0, HO=1). 

Hope this helps,           
-- 
Vic Catterson
[EMAIL PROTECTED]