© 2023 meatfighter.com
This work is licensed under CC BY-SA 4.0
The add function operates on a 2-byte array. It sets the first byte to the sum of both bytes:
f( [ A, B ] ) = [ Q, B ], where A,B,Q ∈ ℤ
Q = A + B, where the plus sign denotes arithmetic add.
B passes through, unchanged.
Its circuit consists of a chain of full adders, devices capable of single-digit addition. Each full adder accepts three 1-bit addends, X, Y, and Z, and it outputs their sum, a 2-bit value composed of the twos bit, C, and the ones bit, S. The table below shows the outputs for all possible inputs.
| X | Y | Z | C | S | Meaning |
|---|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 | 0 + 0 + 0 = 0 |
| 0 | 0 | 1 | 0 | 1 | 0 + 0 + 1 = 1 |
| 0 | 1 | 0 | 0 | 1 | 0 + 1 + 0 = 1 |
| 0 | 1 | 1 | 1 | 0 | 0 + 1 + 1 = 2 |
| 1 | 0 | 0 | 0 | 1 | 1 + 0 + 0 = 1 |
| 1 | 0 | 1 | 1 | 0 | 1 + 0 + 1 = 2 |
| 1 | 1 | 0 | 1 | 0 | 1 + 1 + 0 = 2 |
| 1 | 1 | 1 | 1 | 1 | 1 + 1 + 1 = 3 |
Per the table rows where S is 1:
S = X Y Z + X Y Z + X Y Z + X Y Z
= X (Y Z + Y Z) + X (Y Z + Y Z)
= X (Y ⊕ Z) + X (Y ⊕ Z)
= X ⊕ Y ⊕ Z
= X ⊕ Y ⊕ 1 ⊕ Z
= (X ⊕ Y ⊕ 1) ⊕ Z
= (X ⊕ Y) ⊕ Z
Per the table rows where C is 1:
C = X Y Z + X Y Z + X Y Z + X Y Z
= Z (X Y + X Y) + X Y (Z + Z)
= Z (X X + X Y + X Y + Y Y) + X Y
= Z (X + Y) (X + Y) + X Y
= Z (X + Y) (X Y) + (X Y)
= Z (X + Y) + (X Y)
= Z (X + Y) + (X Y) + (X Y)
= Z (X + Y) + (X X Y) + (Y X Y)
= Z (X + Y) + (X X Y + X X Y) + (Y X Y + Y X Y)
= Z (X + Y) + X (X Y + X Y) + Y (X Y + X Y)
= Z (X + Y) + X (X ⊕ Y) + Y (X ⊕ Y)
= Z (X + Y) + (X ⊕ Y) (X + Y)
= (X + Y) (Z + X ⊕ Y)
The expressions for S and C are combined:
T = X ⊕ Y
S = T ⊕ Z
C = (X + Y) (Z + T) = X + Y + Z + T
The resultant expressions suggest the following circuit, where the XNORs (the gray rectangles) are composed from four NORs.
The Tetris realization is based on a slight modification that forwards input X through and out between C and S. It consists of nine NORs and three crosses, as shown below.
Here are the results for X = 0 and all possible values of Y and Z:
Here are the results for X = 1 and all possible values of Y and Z:
The complete circuit consists of full adders chained in the arrangement below. Each full adder accepts a pair of addend digits, Ai and Bi, and it outputs their sum digit, Qi, along with one of the input digits, Bi, unmodified.
The circuit evaluates right-to-left. For each full adder, if the sum of the carry-in, Z, and the addend digits, Ai and Bi, is not a single-digit number, then the high digit, C, is carried out to the full adder on its left. The initial carry-in is 0 (far right) and the final carry-out is lost.
Crisscrossing wires are required to interlace the inputs and to disentangle the outputs:
The Tetris realization retains the triangular patterns from all the cross overs:
The full adders are stacked diagonally to enable the carries to ripple in the expected order.
© 2023 meatfighter.com |