Table 1
Truth Table for TSD Addition: First-Step Rules
Group Number | Addend X
i
| Augend Y
i
| Intermediate
|
---|
Carry c
i+1
|
Sum s
i
|
---|
1 | 0 | 0 | 0 | 0 |
| 1 | 1̅ | 0 | 0 |
| 1̅ | 1 | 0 | 0 |
| 2 | 2̅ | 0 | 0 |
| 2̅ | 2 | 0 | 0 |
2 | 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 2 | 1̅ | 0 | 1 |
| 1̅ | 2 | 0 | 1 |
3 | 0 | 1̅ | 0 | 1̅ |
| 1̅ | 0 | 0 | 1̅ |
| 2̅ | 1 | 0 | 1̅ |
| 1 | 2̅ | 0 | 1 |
4 | 1 | 1 | 1 | 1̅ |
| 0 | 2 | 1 | 1̅ |
| 2 | 0 | 1 | 1̅ |
5 | 1̅ | 1̅ | 1̅ | 1 |
| 0 | 2̅ | 1̅ | 1 |
| 2̅ | 0 | 1̅ | 1 |
6 | 2 | 1 | 1 | 0 |
| 1 | 2 | 1 | 0 |
7 | 1̅ | 2̅ | 1̅ | 0 |
| 2̅ | 1̅ | 1̅ | 0 |
8 | 2 | 2 | 1 | 1 |
9 | 2̅ | 2̅ | 1̅ | 1̅ |
Table 2
Truth Table for TSD Addition: Second-Step Rules
Group Number | Intermediate
| Final Sum S
i
|
---|
Carry c
i
| Sum s
i
|
---|
1 | 0 | 0 | 0 |
| 1 | 1̅ | 0 |
| 1̅ | 1 | 0 |
2 | 0 | 1 | |
| 1 | 0 | 1 |
3 | 0 | 1̅ | |
| 1̅ | 0 | 1̅ |
4 | 1 | 1 | 2 |
5 | 1̅ | 1̅ | 2̅ |
Table 3
Truth Table for Second-Step TSD
Subtraction: Intermediate Difference and Borrow
Group Number | Minuend X
i
| Subtrahend Y
i
| Intermediate
|
---|
Borrow B
i+1
| Difference D
i
|
---|
1 | 0 | 0 | 0 | 0 |
| 1 | 1 | 0 | 0 |
| 1̅ | 1̅ | 0 | 0 |
| 2 | 2 | 0 | 0 |
| 2̅ | 2̅ | 0 | 0 |
2 | 0 | 1̅ | 0 | 1 |
| 1 | 0 | 0 | 1 |
| 2 | 1 | 0 | 1 |
| 1̅ | 2̅ | 0 | 1 |
3 | 0 | 1 | 0 | 1̅ |
| 1̅ | 0 | 0 | 1̅ |
| 2̅ | 1̅ | 0 | 1̅ |
| 1 | 2 | 0 | 1̅ |
4 | 1 | 1̅ | 1 | 1̅ |
| 0 | 2̅ | 1 | 1̅ |
| 2 | 0 | 1 | 1̅ |
5 | 1̅ | 1 | 1̅ | 1 |
| 0 | 2 | 1̅ | 1 |
| 2̅ | 0 | 1̅ | 1 |
6 | 2 | 1̅ | 1 | 0 |
| 1 | 2̅ | 1 | 0 |
7 | 1̅ | 2 | 1̅ | 0 |
| 2̅ | 1 | 1̅ | 0 |
8 | 2 | 2̅ | 1 | 1 |
9 | 2̅ | 2 | 1̅ | 1̅ |
Table 4
Truth Table for Recoding TSD Numbers
Groups for Di-2Di-3 Digits
|
N
1
Values
|
N
2
Values
|
N
3
Values
|
---|
Groups for D
i
D
i-1
Digits | 00, 10, 01, 01̅, 1̅0, 02, 02̅, 12̅, 1̅1, 1̅1̅, 11̅, 11, 22̅, 2̅2, 1̅2 | 21̅, 20, 12, 21, 22 | 2̅1, 2̅0, 1̅2̅, 2̅1̅, 2̅2̅ |
---|
|
---|
Output Z
i
|
---|
C
1
= 2̅2̅, 01, 12̅
| 0 | 1 | 0 |
C
2
= 11̅, 02, 2̅1̅
| 1 | 1 | 0 |
C
3
= 2̅1, 1̅2̅, 11, 22̅
| 1 | 1̅ | 1 |
C
4
= 2̅0, 10
| 1 | 1 | 1 |
C
5
= 00
| 0 | 0 | 0 |
C
6
= 20, 1̅0
| 1̅ | 1̅ | 1̅ |
C
7
= 21̅, 12, 1̅1̅, 2̅2
| 1̅ | 1̅ | 1 |
C
8
= 1̅1, 02̅, 21
| 1̅ | 0 | 1̅ |
C
9
= 22, 01̅, 1̅2
| 0
| 0
| 1̅
|
Table 5
Truth Table for Recoded TSD Addition
Group Number | Addend A
i
| Augend Bi | Final Sum S
i
|
---|
1 | 1 | 1 | 2 |
2 | 0 | 1 | 1 |
| 1 | 0 | 1 |
3 | 0 | 0 | 0 |
| 1 | 1̅ | 0 |
| 1̅ | 1 | 0 |
4 | 0 | 1̅ | 1̅ |
| 1̅ | 0 | 1̅ |
5 | 1̅ | 1̅ | 2̅ |
Table 6
Truth Table for One-Step Nonrecoded TSD Addition
Groups for X i-1Yi-1 Digits
|
N
1
Values
|
N
2
Values
|
N
3
Values
|
---|
Groups for X
i
Y
i
Digits | 00, 10, 01, 01̅, 1̅0, 12̅, 2̅1, 1̅1, 11̅, 22̅, 2̅2, 21̅, 1̅2 | 02, 20, 11, 12, 21, 22 | 02̅, 2̅0, 1̅1̅, 1̅2̅, 2̅1̅, 2̅2̅ |
---|
|
---|
Output Sum S
i
|
---|
C
1
= 00, 1̅1, 11̅, 22̅, 2̅2, 12, 21, 1̅2̅, 2̅1̅
| 0 | 1 | 1̅ |
C
2
= 10, 01, 21̅, 1̅2, 02̅, 2̅0, 1̅1̅, 22
| 1 | 2 | 0 |
C
3
= 01̅, 1̅0, 12̅, 2̅1, 02, 20, 11, 2̅2̅
| 1̅
| 0
| 2̅
|
Table 7
Five-for-One RBR Coding for the Prime and the Fuzzy
TSD Digits
TSD Digit
| RBR Code
| Denotation
|
---|
2̅ | 10000 | [16] |
1̅ | 01000 | [8] |
0 | 00100 | [4] |
1 | 00010 | [2] |
2 | 00001 | [1] |
Either 1 or 2 | 00011 | [3] |
Either 2 or 0 | 00101 | [5] |
Either 1 or 0 or 2 | 00111 | [7] |
Either 2 or 1̅ | 01001 | [9] |
Either 1̅ or 1 | 01010 | [10] |
Either 1̅ or 0 | 01100 | [12] |
Either 1̅ or 0 or 1 | 01110 | [14] |
Either 2̅ or 1 | 10010 | [18] |
Either 2̅ or 0 | 10100 | [20] |
Either 2̅ or 1̅ | 11000 | [24] |
Either 0 or 1̅ or 2̅
| 11100
| [28]
|
Table 8
Reduced Minterms for the Recoding TSD Algorithm Based on
RBR Coding
1
| 1̅
| 0
|
---|
[18 16 2 1] | [18 2 8 16] | [ 9 2 2 1] |
[18 16 1 15] | [18 2 16 30] | [ 9 2 1 15] |
[ 4 2 2 1] | [ 9 16 8 16] | [ 4 16 2 1] |
[ 4 2 1 15] | [ 9 16 16 30] | [ 4 16 1 15] |
[18 8 7 31] | [ 9 8 7 31] | [ 9 1 7 31] |
[18 8 8 15] | [ 9 8 8 15] | [ 9 1 8 15] |
[18 8 14 14] | [ 9 8 14 14] | [ 9 1 16 1] |
[ 4 1 7 31] | [18 1 7 31] | [ 4 8 7 31] |
[ 4 1 8 15] | [18 1 8 15] | [ 4 8 8 15] |
[ 4 1 16 1] | [18 1 16 1] | [ 4 8 16 1] |
[18 2 28 1] | [ 9 2 28 11] | [18 16 28 11] |
[18 2 7 16] | [ 9 2 7 16] | [18 16 7 16] |
[18 2 14 14] | [ 9 2 14 14] | [18 16 14 14] |
[ 9 16 28 1] | [ 4 16 28 1] | [ 4 2 28 1] |
[ 9 16 7 16] | [ 4 16 7 16] | [ 4 2 7 16] |
[ 9 16 14 14] | [ 4 16 14 14] | [ 4 2 14 14] |
[18 4 31 31] | [ 9 4 31 31] | [ 4 4 31 31] |
[ 9 8 8 16] | [ 9 1 8 16] | [18 8 8 16] |
[ 9 8 16 30] | [ 9 1 16 30] | [18 8 16 30] |
[18 1 8 16] | [ 4 8 8 16] | [ 4 1 8 16] |
[18 1 16 30]
| [ 4 8 16 30]
| [ 4 1 16 30]
|
Table 9
Reduced Minterms for the Addition of Recoded TSD Numbers
Based on RBR Coding
1
| 1̅
| 0
| 2
| 2̅
|
---|
[4 2] | [4 8] | [4 4] | [2 2] | [8 8] |
[2 4] | [8 4] | [2 8] | | |
| | [8 2]
| | |
Table 10
Reduced Minterms for One-Step Nonrecoded TSD Addition
Based on RBR Coding
1
| 1̅
| 0
| 2
| 2̅
|
---|
[ 4 18 4 14] | [ 4 9 4 14] | [ 4 4 4 14] | [ 4 18 7 1] | [ 4 9 28 16] |
[ 4 18 14 4] | [ 4 9 14 4] | [ 4 4 14 4] | [ 4 18 1 7] | [ 4 9 16 28] |
[ 4 18 3 24] | [ 4 9 3 24] | [ 4 4 3 24] | [ 4 18 2 2] | [ 4 9 8 8] |
[ 4 18 24 3] | [ 4 9 24 3] | [ 4 4 24 3] | | |
[18 4 4 14] | [ 9 4 4 14] | [ 9 18 4 14] | [18 4 7 1] | [ 9 4 28 16] |
[18 4 14 4] | [ 9 4 14 4] | [ 9 18 14 4] | [18 4 1 7] | [ 9 4 16 28] |
[18 4 3 24] | [ 9 4 3 24] | [ 9 18 3 24] | [18 4 2 2] | [ 9 4 8 8] |
[18 4 24 3] | [ 9 4 24 3] | [ 9 18 24 3] | | |
[ 9 9 4 14] | [18 18 4 14] | [18 9 4 14] | [ 9 9 7 1] | [18 18 28 16] |
[ 9 9 14 4] | [18 18 14 4] | [18 9 14 4] | [ 9 9 1 7] | [18 18 16 28] |
[ 9 9 3 24] | [18 18 3 24] | [18 9 3 24] | [ 9 9 2 2] | [18 18 8 8] |
[ 9 9 24 3] | [18 18 24 3] | [18 9 24 3] | | |
[ 4 4 7 1] | [ 4 4 28 16] | [ 4 4 28 16] | | |
[ 4 4 1 7] | [ 4 4 16 28] | [ 4 4 16 28] | | |
[ 4 4 2 2] | [ 4 4 8 8] | [ 4 4 8 8] | | |
[ 9 18 7 1] | [ 9 18 28 16] | [18 4 28 16] | | |
[ 9 18 1 7] | [ 9 18 16 28] | [18 4 16 28] | | |
[ 9 18 2 2] | [ 9 18 8 8] | [18 4 8 8] | | |
[18 9 7 1] | [18 9 28 16] | [ 9 9 28 16] | | |
[18 9 1 7] | [18 9 16 28] | [ 9 9 16 28] | | |
[18 9 2 2] | [18 9 8 8] | [ 9 9 8 8] | | |
| | [ 4 9 7 1] | | |
| | [ 4 9 1 7] | | |
| | [ 4 9 2 2] | | |
| | [ 9 4 7 1] | | |
| | [ 9 4 1 7] | | |
| | [ 9 4 2 2] | | |
| | [18 18 7 1] | | |
| | [18 18 1 7] | | |
| | [18 18 2 2]
| | |
Table 11
Truth Table for Recoded TSD Multiplication
Group | Multiplicand a
i
| Multiplier B
i
| Product P
1
|
---|
1 | 1 | 1 | 1 |
| 1̅ | 1̅ | 1 |
2 | 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1̅ | 0 |
| 1̅ | 0 | 0 |
3 | 1 | 1̅ | 1̅ |
| 1̅ | 1 | 1̅ |
Table 12
Reduced Minterms for Generating Partial Products when
Both the Multiplicand and the Multiplier are Recoded
Output Digits
| Reduced Minterms
|
---|
1 | [ 2 2] |
| [ 8 8] |
1̅ | [ 2 8] |
| [ 8 2] |
0 | [ 4 14] |
| [14 4]
|
Table 13
Truth Table for TSD Multiplication when Only the
Multiplier is Recoded
Group | Multiplicand a
i
| Multiplier b
i
| Product P
i
|
---|
1 | 2 | 1 | 2 |
| 2̅ | 1̅ | 2 |
2 | 1 | 1 | 1 |
| 1̅ | 1̅ | 1 |
3 | 2 | 0 | 0 |
| 2̅ | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 0 | 0 | 0 |
| 0 | 1̅ | 0 |
| 1̅ | 0 | 0 |
4 | 1 | 1̅ | 1̅ |
| 1̅ | 1 | 1̅ |
5 | 2 | 1̅ | 2̅ |
| 2̅ | 1 | 2̅ |
Table 14
Reduced Minterms for Generating Partial Products when
Only the Multiplier is Recoded
Output Digits
| Reduced Minterms
|
---|
1 | [ 2 2] |
| [ 8 8] |
1̅ | [ 2 8] |
| [ 8 2] |
0 | [ 4 14] |
| [31 4] |
2 | [ 1 2] |
| [16 8] |
2̅ | [ 1 8] |
| [16 2]
|
Table 15
Truth Table for the Nonrecoded TSD Multiplication with
Carries
Group | Multiplicand a
i
| Multiplier b
i
| Product c
i+1
P
i
|
---|
1 | 2 | 2 | 1 | 1 |
| 2̅ | 2̅ | 1 | 1 |
2 | 1 | 1 | 0 | 1 |
| 1̅ | 1̅ | 0 | 1 |
3 | 2 | 1̅ | 1̅ | 1 |
| 1̅ | 2 | or |
| 2̅ | 1 | 0 | 2̅ |
| 1 | 2̅ | | |
4 | 0 | 2 | 0 | 0 |
| 2 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 |
| 1 | 0 | 0 | 0 |
| 0 | 0 | 0 | 0 |
| 0 | 1̅ | 0 | 0 |
| 1̅ | 0 | 0 | 0 |
| 0 | 2̅ | 0 | 0 |
| 2̅ | 0 | 0 | 0 |
5 | 2 | 1 | 1 | 1̅ |
| 1 | 2 | or |
| 1̅ | 2̅ | 0 | 2 |
| 2̅ | 1̅ | | |
6 | 1 | 1̅ | 0 | 1̅ |
| 1̅ | 1 | 0 | 1̅ |
7 | 2 | 2̅ | 1̅ | 1̅ |
| 2̅ | 2 | 1̅ | 1̅ |
Table 16
Reduced Minterms for Generating Partial-Product and
Partial-Carry Digits for Nonrecoded TSD Multiplication
Reduced Minterms
|
---|
Partial Carries
| Partial Products
|
---|
1
| 1̅
| 1
| 1̅
|
---|
[ 1 3] | [ 1 24] | [18 18] | [18 9] |
[ 3 1] | [24 1] | [ 9 9] | [ 9 18] |
[16 24] | [16 3] | | |
[24 16]
| [ 3 16]
| | |
Table 17
Truth Table for Nonrecoded TSD Multiplication without
Carries
a
i
a
i-1
|
b
j
|
---|
2̅
| 1̅
| 2
| 1
| 0
|
---|
22̅, 1̅2̅ | 0 | 2 | 0 | 2̅ | 0 |
12, 2̅2 | 0 | 2̅ | 0 | 2 | 0 |
11, 2̅1 | 0 | 1̅ | 0 | 1 | 0 |
21̅, 1̅1̅ | 0 | 1 | 0 | 1̅ | 0 |
20, 1̅0 | 1̅ | 1 | 1 | 1̅ | 0 |
21, 1̅1 | 2̅ | 1 | 2 | 1̅ | 0 |
22, 1̅2 | 2̅ | 0 | 2 | 0 | 0 |
10, 2̅0 | 1 | 1̅ | 1̅ | 1 | 0 |
11̅, 2̅1̅ | 2 | 1̅ | 2̅ | 1 | 0 |
12̅, 2̅2̅ | 2 | 0 | 2̅ | 0 | 0 |
02̅ | 1 | 1 | 1̅ | 1̅ | 0 |
01̅ | 1 | 0 | 1̅ | 0 | 0 |
01 | 1̅ | 0 | 1 | 0 | 0 |
02 | 1̅ | 1̅ | 1 | 1 | 0 |
00
| 0
| 0
| 0
| 0
| 0
|
Table 18
Reduced Minterms for Generating Partial Products without
Carries for Nonrecoded TSD Multiplication
Reduced Minterms for Generating Partial-Product Digits
|
---|
1
| 1̅
| 2
| 2̅
|
---|
[18 14 2] | [18 14 16] | [ 9 16 8] | [ 9 16 2] |
[18 4 16] | [18 4 1] | [ 9 3 1] | [ 9 24 16] |
[ 9 14 8] | [ 9 14 2] | [18 1 2] | [18 1 8] |
[ 9 4 1] | [ 9 4 16] | [18 24 16] | [18 24 1] |
[ 4 8 16] | [ 4 2 16] | | |
[ 4 2 1] | [ 4 8 1] | | |
[ 4 16 24] | [ 4 1 24] | | |
[ 4 1 3]
| [ 4 16 3]
| | |
Table 19
Comparison of the Four Multiplication Designs
Type of Multiplicand and Multiplier | Number of Reduced Minterms Needed for
| Number of Accumulation Steps | Number of Adders |
---|
Recoding
| Addition
| Partial-Product Generation
|
---|
Recoded multiplicand and multiplier | 21 | 3 | 2 | log2(n + 1)+ (n+ 1)/2 recoding steps | (n+ 1)/2
|
Only recoded multiplier | | 30 | 4 | log2(n+ 1) | (n+ 1)/2
|
Nonrecoded multiplicand and multiplier with carries | | 30 | 6 | log2(2
n+ 1) | (2
n+ 1)/2
|
Nonrecoded multiplicand and multiplier without carries
| | 30
| 12
| log2(n+ 1)
| (n+ 1)/2
|