A 3:2 counter is a full adder used as a compressor. It takes three bits of one weight and returns a sum of the same weight plus a carry of the next weight.
Three inputs become two outputs, hence the name. The sum is odd parity and the carry is the majority.
x y z | Sum (odd parity) | Carry (majority) |
|---|---|---|
0 0 0 | 0 | 0 |
0 0 1 | 1 | 0 |
0 1 0 | 1 | 0 |
0 1 1 | 0 | 1 |
1 0 0 | 1 | 0 |
1 0 1 | 0 | 1 |
1 1 0 | 0 | 1 |
1 1 1 | 1 | 1 |
Wallace reduction compresses every column at once. Groups of three take a full adder, pairs take a half adder, and all carries enter the next column of the next stage.
For the 4 by 4 array this finishes in one pass: 4 full adders and 4 half adders leave two rows. The model below pins those counts.
Dadda reduction targets exact column heights instead of compressing everything. Heights follow doubling by three halves, rounded down: 2, 3, 4, 6, 9, 13, 19.
Rows pick the first height that covers them, and each step down is one stage. Eight rows need four stages: 8 to 6 to 4 to 3 to 2.
Dadda heights: d1 = 2, d(k+1) = floor(3 x dk / 2)
2, 3, 4, 6, 9, 13, 19
floor(3x2/2) = 3, floor(3x3/2) = 4, floor(3x4/2) = 6
floor(3x6/2) = 9, floor(3x9/2) = 13, floor(3x13/2) = 19
rows -> stages (reduce to 2 rows):
3 -> 1 (3 -> 2), 4 -> 2 (4 -> 3 -> 2)
8 -> 4 (8 -> 6 -> 4 -> 3 -> 2), 16 -> 6 (16 -> 13 -> 9 -> 6 -> 4 -> 3 -> 2)The program reduces a 4 by 4 product Wallace-style and checks all 256 pairs. It pins 4 full and 4 half adders plus the Dadda stage counts above.
import sys
def wallace44(aa, bb):
cols = [[] for _ in range(10)]
for i in range(4):
for j in range(4):
cols[i + j].append(((aa >> j) & 1) & ((bb >> i) & 1))
fa = 0
ha = 0
nxt = [[] for _ in range(10)]
carry = []
for c in range(10):
bits = carry + cols[c]
carry = []
while len(bits) >= 3:
x = bits.pop()
y = bits.pop()
z = bits.pop()
fa += 1
nxt[c].append(x ^ y ^ z)
carry.append((x + y + z) // 2)
if len(bits) == 2:
x = bits.pop()
y = bits.pop()
ha += 1
nxt[c].append(x ^ y)
carry.append(x & y)
elif len(bits) == 1:
nxt[c].append(bits.pop())
for c in range(10):
if len(nxt[c]) > 2:
return (0, fa, ha)
value = 0
for c in range(10):
for bit in nxt[c]:
value += bit << c
return (value, fa, ha)
def dadda_stages(rows):
d = 2
s = 0
while d < rows:
d = (3 * d) // 2
s += 1
return s
bad = 0
got_fa = 0
got_ha = 0
for aa in range(16):
for bb in range(16):
v, fa, ha = wallace44(aa, bb)
if v != aa * bb:
bad += 1
got_fa = fa
got_ha = ha
if bad != 0:
print("FAIL: " + str(bad) + " Wallace products differ")
sys.exit(1)
if got_fa != 4 or got_ha != 4:
print("FAIL: counter tally differs")
sys.exit(1)
if dadda_stages(3) != 1 or dadda_stages(4) != 2:
print("FAIL: Dadda stage count differs")
sys.exit(1)
if dadda_stages(8) != 4 or dadda_stages(16) != 6:
print("FAIL: Dadda stage count differs")
sys.exit(1)
print("PASS: Wallace 4x4 uses 4 full and 4 half adders on all 256 pairs; Dadda needs 4 stages for 8 rows")One full adder takes 3 bits, leaving 2. The pair takes one half adder, so the column yields 2 bits plus carries out.
Six stages: 16 to 13 to 9 to 6 to 4 to 3 to 2.