For the calculation of the sum of integers
First, the integers
-
$A_{i-1:j}+B_{i-1:j} \lt N^{i-j}-1$ ;None
-
$A_{i-1:j}+B_{i-1:j} = N^{i-j}-1$ ;Propagate
-
$A_{i-1:j}+B_{i-1:j} \gt N^{i-j}-1$ ;Generate
Example for a decimal number:
-
$12345 + 12345 = 24690 \lt 99999$ ;None
-
$12345 + 87654 = 99999 = 99999$ ;Propagate
-
$12345 + 99999 = 112344 \gt 99999$ ;Generate
Consider the same for the
(Upper) |
(Lower) |
(Combined) |
---|---|---|
None | None | None |
None | Propagate | None |
None | Generate | None |
Propagate | None | None |
Propagate | Propagate | Propagate |
Propagate | Generate | Generate |
Generate | None | Generate |
Generate | Propagate | Generate |
Generate | Generate | Generate |
Example: Propagate
-
$A_{i-1:j} + B_{i-1:j} = N^{i-j}-1$ ;Propagate
-
$A_{j-1:k} + B_{j-1:k} = N^{j-k}-1$ ;Propagate
-
$A_{i-1:k} + B_{i-1:k} = (N^{i-j}-1)\cdot N^{j-k} + (N^{j-k}-1) = N^{i-k} - 1$ ;Propagate
To represent these states, we introduce the signals
status | ||
---|---|---|
0 | 0 | None |
0 | 1 | Propagate |
1 | 0 | Generate |
1 | 1 | Generate |
If we are interested in the state of the integer
$G_{r:r} = G_r = A_r \land B_r$
The signal
$P_{r:r} = P_r = A_r \lor B_r$ $P_{r:r} = P_r = A_r \oplus B_r$
Note:
-
$\land$ :and
-
$\lor$ :or
-
$\oplus$ :xor
The process of combining the signal
$G_{i-1:k} = G_{i-1:j} \lor (P_{i-1:j} \land G_{j-1:k})$
The process of synthesizing the signal
$P_{i-1:k} = G_{i-1:j} \lor (P_{i-1:j} \land P_{j-1:k})$ $P_{i-1:k} = P_{i-1:j} \land P_{j-1:k}$