full adder (or better bit counter!)
- (a,b,c) → (r1, r0) i.e. a+b+c = 2r1 + r0 which is r1 = (a and (b or c)) or b and c), r0 = a xor b xor c
- yields depth and size O(n), size to add two n-bit numbers
recursive adder
- (l, r) => (l+r, l+r+1)
- addR(l, r) {let j = (int) bitSize(l, r) / 2;
- (c1, d1) = addR(l div 2j, r div 2j)
- (c0, d0) = addR(l mod 2j, r mod 2j)
- return (if c0 >= 2j then d1 else c1 fi * 2j + c0, if d0 >= 2j then d1 else c1 fi * 2j + d0)
- iterative implementation ==> php
- 4 int variables, split in windows of 2k bits
- a = (l+r) mod 22**k for each window
- b = (l+r+1) mod 22**k for each window
- c = (l+r) div 22**k for previous window (so each carry is at the bit of the correct value)
- d = (l+r+1) div 22**k for previous window (so each carry is at the bit of the correct value)
- thus, we have the loop invariants a + c = l+r, b+d = l+r + sum(i=0..., 2i * 2**k)
- depth O(log(w)) but size O(w * log(w))
- 4 int variables, split in windows of 2k bits
carry look ahead
for 2 j bit numbers we have 3 exclusive possibilities
- r+l, r+l+1 < 2j
- r+l+1, r+l >= 2j
- r+l = 2j-1, r+l+1 = 2j, this is equivalent with r xor l = not 0 = all 1
thus, using again doubling windows of 2k bits we get
- carry[i] = (l[i-1] and r[i-1])
- xor ((l[i-1] xor r[i-1]) and (l[i-2] + r[i-2] >= 2)
- xor ((l[i-2, i-1] xor r[i-2, i-1] = 11) and (l[i-4, i-3] + r[i-4, i-3] >= 4)
- xor ((l[i-2k, i-1] xor r[i-2k, i-1] = 2*2k-1) and (l[i-2*2k, i-2k-1] + r[i-2*2k, i-2k-1] >= 2*2k)
phases
- forward: doubling windowsize compute for 2k windows: all1 and carry at i*2k
- backward: halfing windowsize compute carry at at 2k-1 + i*2k
implementation Inf:php/e11bit.php?addC
reversible logic adder with log 2 depth
php symols: ^ = xor, ~ bitwise not we use a reversible circuit rlAddCary, that computes the carry (i.e (l, r) ==> (l, l^r, l^r^(l+r)
| 0 | op | left | right | carry |
|---|---|---|---|---|
| 1 | rlAddCarry | l | r | 0 |
| 2 | ^ | l | l ^ r | l ^ r ^ (l+r) |
| 3 | ^ ~ | l | ~l ^ (l + r) | l ^ r ^ (l+r) |
| 4 | rlAddCarry backward | l | ~l ^ (l + r) | l ^ r ^ (l+r) |
| 5 | ~ | l | ~ (l+r) | 0 |
| 6 | l | l+r | 0 | |
| 4 -> 5 because backward yields | ||||
| 7 | -->5 rlAddCarry | l | ~ (l+r) | 0 |
| 8 | === | l | l ^ ~(l+r) | l ^ ~(l+r) ^ (l + ~(l+r) |
| 9 | === | l | ~l ^ (l+r) | l ^ ~(l+r) ^ (l + (1 - l - r)) |
| 10 | === | l | ~l ^ (l+r) | l ^ ~(l+r) ^ (1 - r) |
| 11 | === | l | ~l ^ (l+r) | l ^ ~(l+r) ^ ~r |
| 12 | -->4 | l | ~l ^ (l+r) | l ^ r ^ (l+r) |
rlAddCarry is implemented as follows
function rlAddCarry($cE) { # reversible carry lookahead: (l, r) ==> (l, l^r, l^r^(l+r))
$cW = 1<<$cE;
$c = ['e' => $cE, 'return' => 'r',
#['out', 'l', 'r', 'c', "d1", "rlAddCarry $cE begin"],
['ccNot', 'c', '', 'l<<1', 'r<<1'],
['xor' , 'r', '', 'l']];
# compute carry and all1 for increasing windows sizes
$c[] = ['ccNot', "d1", "A1", 'r<<1', "r<<2"]; # all1 for e=1
$c[] = ['ccNot', 'c' , "A1", 'r<<1', "c<<1"]; # fix carry for e=1
for ($e=2; $e < $cE; $e++) {
$v = 1<<($e1 = $e-1);
$c[] = ['ccNot', "d$e", "A$e", "d$e1", "d$e1<<$v"]; # all1
$c[] = ['ccNot', 'c' , "A$e", "d$e1", "c<<$v"]; # fix carry
#$c[] = ['out', 'l', 'r', 'c', "d$e", "after carry up $e $v"];
}
for ($e=$cE-1; $e >1; $e--) {
$v = 1<<($e1=$e-1);
$c[] = ['ccNot', "d$e", "A$e", "d$e1", "d$e1<<$v"]; #uncompute all1
$c[] = ['ccNot', 'c' , "A$e<<$v","d$e1", "c<<$v"]; #fix carry in the middle
#$c[] = ['out', 'l', 'r', 'c', "d$e", "after carry down $e $v"];
}
$c[] = ['ccNot', "d$e", "A1", "r<<1", "r<<2"]; #uncompute all1 for e=1
$c[] = ['ccNot', 'c' , "A1<<1", "r<<1", "c<<1"]; #fix carry in the middle for e=1
#$c[] = ['out', 'l', 'r', 'c', "d1", "rlAddCarry $cE end"];
return $c;
}
- we use integers as array of 64 (or 32) bits
- gates are described by an array: [name of gate, dest, mask, src1, src2]
- e.g. the last ccNot above will conditionally invert wire c iff r and c
- but only the bits in maskA[1]
- the mask and both sources are shifted one bit to the leftt