Wallace Tree - Example

Example

, multiplying by :

1. First we multiply every bit by every bit:
   • weight 1 -
   • weight 2 -,
   • weight 4 -,
   • weight 8 -,
   • weight 16 -,
   • weight 32 -,
   • weight 64 -
2. Reduction layer 1:
   • Pass the only weight-1 wire through, output: 1 weight-1 wire
   • Add a half adder for weight 2, outputs: 1 weight-2 wire, 1 weight-4 wire
   • Add a full adder for weight 4, outputs: 1 weight-4 wire, 1 weight-8 wire
   • Add a full adder for weight 8, and pass the remaining wire through, outputs: 2 weight-8 wires, 1 weight-16 wire
   • Add a full adder for weight 16, outputs: 1 weight-16 wire, 1 weight-32 wire
   • Add a half adder for weight 32, outputs: 1 weight-32 wire, 1 weight-64 wire
   • Pass the only weight-64 wire through, output: 1 weight-64 wire
3. Wires at the output of reduction layer 1:
   • weight 1 - 1
   • weight 2 - 1
   • weight 4 - 2
   • weight 8 - 3
   • weight 16 - 2
   • weight 32 - 2
   • weight 64 - 2
4. Reduction layer 2:
   • Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64
5. Outputs:
   • weight 1 - 1
   • weight 2 - 1
   • weight 4 - 1
   • weight 8 - 2
   • weight 16 - 2
   • weight 32 - 2
   • weight 64 - 2
   • weight 128 - 1
6. Group the wires into a pair integers and an adder to add them.