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

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

Post by James Sh » Fri, 17 Oct 2003 02:32:53



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?

Thank you very much in advance.

James Shay

 
 
 

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

Post by Vic Catterso » Fri, 17 Oct 2003 19:19:27



Quote:>  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


 
 
 

1. Wallace Tree and 4-2 Compressor

Hello,

Can anyone tell me generally how does the wallace tree works and also the
4-2 compressor?
From what I know..the 4-2 compressor is made up from two 3-2 compressor.
Anyone with a nice URL site to read up on this topic? Easy to understand too
!

Thanks.

Rgds
KEv

2. OK, what are 64-bit PCI slots for?

3. 4-2 Compressor

4. Contract for Prog/Analyst in Lawrenceville, NJ

5. "implementation of mplrs using wallace trees,counters,compressors

6. Fix for SB16 - Mitsumi 4x sound problems

7. An Improvement for the Booth multiplier

8. locking dwgs

9. question about booth multipliers

10. Hi-Speed Booth multipliers

11. test algorithm/patterns for booth multiplier

12. Q: multiplier decoding with Wallace tree?

13. An Improvement for the Booth multiplier