Mir M. Mirsalehi, Thomas K. Gaylord, Daniel C. Fielder, and Clark C. Guest, "Number representation effects in truth-table look-up processing: 8-bit addition example," Appl. Opt. 28, 1931-1939 (1989)
The parallelism and interconnectivity of optical systems may provide important advantages for these systems in massively parallel processing applications. Electronic systems, however, retain all the advantages of a highly developed technology that has been widely applied with excellent success. In both of these technologies, the methods of direct truth-table look-up processing are becoming increasingly important as the need grows for increased speed and throughput. A major issue in truth-table look-up processing is the number representation used for data. In this paper, the effects of number representation are investigated for the important case of 8-bit addition as a specific example. The inputs are two 8-bit binary numbers together with an input carry. The output is a full precision 9-bit binary sum. For the intermediate processing three number representations are treated: binary, residue, and modified signed-digit. The numbers in all three representations are in binary-coded form throughout the processing. The critically important steps of encoding the numbers into the residue and modified signed-digit systems and then decoding the results back into direct binary are also performed using truth-table look-up methods. For the direct binary representation, a total of 2545 gates (2519 holograms) are required. For the residue representation, a total of 1764 gates (1686 holograms) are required. For the modified signed-digit representation, a total of 4142 gates (4052 holograms) are required.
You do not have subscription access to this journal. Cited by links are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Figure files are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Article tables are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
You do not have subscription access to this journal. Equations are available to subscribers only. You may subscribe either as an Optica member, or as an authorized user of your institution.
Direct Binary 8-Bit Addition by Truth-Table Look-Up Processing: Problem Formulation, Logical Reduction, and Truth-Table Representation
INPUT:
Two 8-bit numbers and an input carry bit.
Total number of input bits − (2 × 8) + 1 − 17.
REFERENCE PATTERNS:
Number of reference patterns is equal to the number of input combinations.
Number of input combinations − 217 − 131,072.
CONSTRUCTION OF TRUTH
Express each bit of answer as sum-of-products logical expression.
TABLE:
Number of input combinations to produce a “one” for each output bit − 216 − 65,536 (number of terms in each sum-of-products expression).
Total number of input combinations for all output bits − 9 × 216 − 589,824 (total number of terms in all sum-of-products expressions).
LOGICAL REDUCTION:
For each output bit:
Determine prime implicants.
Construct table-of-choice.
Obtain minimal sum.
Determine essential prime implicants.
Eliminate dominated rows.
Eliminate dominating columns.
Construct new table of choice.
Repeat above steps.
REDUCED REFERENCE
Number of reference patterns (number of and gates in PAL or number of holograms in optical CAM) after logical minimization.
PATTERNS:
Output
Reference
Bit
Patterns
0 (LSB)
4
1
12
2
28
3
60
4
124
5
252
6
508
7 (MSB)
1020
8 (carry)
511
Total No. Reference Patterns − 2,519
OUTPUT:
One 8-bit number and an output carry bit.
Number of output bits − 8 + 1 − 9.
Number of possible outputs − 29 − 512.
Table II
Reduced Reference Patterns that Need to be Stored in a Content-Addressable Memory to Convert an 8-Bit Binary Number to a Binary-Coded Modulo 5 Residue Number; These 8-Bit Binary Numbers Produce a 1 in the b2, b1, and b0 Bit Positions of the Binary-Coded Modulo 5 Residue Number as Listed
b2 = 1
b1 = 1
b0 = 1
00000100
10010101
000X0010
10010011
00X00001
10011001
01000000
10011010
0X001000
10110001
X0001000
10101001
001X0000
11000110
00X10000
0001X111
00001001
10111000
1X000000
11100100
1000X000
X0010111
00011000
11001100
X0101011
00100010
11010001
00010001
0X010111
0000X011
X0111010
10000001
01000100
00101X11
X0000011
01X00111
10010000
00111011
0X101011
00X00110
0101X011
01001111
00000X11
0X110101
0001X010
X1010011
00001110
01011110
0X000011
010X1101
X0010010
01X10110
00010011
01101101
0000110X
0110011X
001001X0
011001X1
00101100
01111100
000X1100
011X0110
01X00010
011101X0
00110001
10101110
00100X01
1000111X
X1000100
100011X1
01000101
10110011
0X100001
100X1110
011000X0
10X01101
01001010
11000111
1000010X
10011X01
100010X0
100111X0
01010100
11010110
100X0100
1X011001
10X01000
10X11100
01101000
11100101
10100X11
1100X110
10000110
11101010
0001011X
1X100011
X0001101
110010X1
10100100
11110100
0X100110
1010110X
00X10101
11X01001
11000010
001X1010
101X1100
X0011100
110110X0
11100000
01110111
0011010X
110X0101
0010X110
11X11000
10011111
01001X01
X0100110
1110X100
00011101
10111101
0101001X
0011111X
001010X1
00100111
11011011
01011X00
0111101X
001110X0
001111X1
00110110
11111001
01100X10
1011011X
X1001001
X1011101
01011001
0111000X
11001X11
010011X0
0110X111
01100011
11101111
100X1001
11011X10
01X01100
X1100111
01110010
11111110
1X001010
11101X01
01X10001
0111X110
10001011
1001100X
1111001X
X1011000
X1110110
101X0010
11111X00
0110X010
011110X1
1X101000
X1100010
101101X1
11000X01
10111011
1000X101
11X01110
11010X00
11101110
1001X100
1101X101
101000X1
111100X1
00011011
0X111111
101100X0
00111001
1X110111
1100X001
X0111111
01001110
110X1111
1101X000
X1111011
01101100
111X1101
110111X1
00110011
11X11101
Notes: (1) The bit number, n. starts at zero for the least significant bit, b0. and increases for more significant bits.
Table III
Reduced Reference Patterns that Need to be Stored in a Content-Addressable Memory to Implement Addition of Two Binary-Coded Modulo 5 Residue Numbers and an Input Carry; These Input Patterns Produce a 1 in the b2, b1, and b0 Bit Positions of the Binary-Coded Modulo 5 Sum as Listed
b2 = 1
b1 = 1
b0 = 1
0001000
0010110
00X0100
00100X1
0000X01
1001000
1000000
0100011
01000X0
001001X
0X00001
0010011
0100100
0110001
1001000
010x001
0000X10
0110010
011X000
0X00010
0X11001
0000111
1001001
00X0011
011100X
0010X00
1000X11
0010101
X000101
100011X
0X10000
X000110
0110111
0100111
0101000
0110101
1000100
0110110
Notes: (1) Each pattern consists of two three-bit input numbers followed by an input carry.
Table IV
Truth Table Corresponding to W2 Function Used in the MSD Addera
c1
x0
y0
W2
0
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
The quantity c1 is the input carry, x0 and y0 are the least significant bits of the two input numbers, and W2 provides the least significant bit of the output z0.
Table V
Number of Gates Required to Perform 8-Bit Addition by Truth-Table Look-Up Processing Using Direct Binary, Residue, and Modified Signed-Digit Number Systems including Encoding and Decoding
Number System
Direct Binary
Residue
Modified Signed-Digit
Encoder
NOT
0
16
0
AND
0
722
0
OR
0
12
0
Adder
NOT
17
21
17
AND
2519
215
374
OR
9
10
18
NOR
0
0
9
Decoder
NOT
0
10
0
AND
0
749
3678
OR
0
9
45
NOR
0
0
1
Total Gates
2545
1764
4142
Number of Holograms (AND gates)
2519
1686
4052
Tables (5)
Table I
Direct Binary 8-Bit Addition by Truth-Table Look-Up Processing: Problem Formulation, Logical Reduction, and Truth-Table Representation
INPUT:
Two 8-bit numbers and an input carry bit.
Total number of input bits − (2 × 8) + 1 − 17.
REFERENCE PATTERNS:
Number of reference patterns is equal to the number of input combinations.
Number of input combinations − 217 − 131,072.
CONSTRUCTION OF TRUTH
Express each bit of answer as sum-of-products logical expression.
TABLE:
Number of input combinations to produce a “one” for each output bit − 216 − 65,536 (number of terms in each sum-of-products expression).
Total number of input combinations for all output bits − 9 × 216 − 589,824 (total number of terms in all sum-of-products expressions).
LOGICAL REDUCTION:
For each output bit:
Determine prime implicants.
Construct table-of-choice.
Obtain minimal sum.
Determine essential prime implicants.
Eliminate dominated rows.
Eliminate dominating columns.
Construct new table of choice.
Repeat above steps.
REDUCED REFERENCE
Number of reference patterns (number of and gates in PAL or number of holograms in optical CAM) after logical minimization.
PATTERNS:
Output
Reference
Bit
Patterns
0 (LSB)
4
1
12
2
28
3
60
4
124
5
252
6
508
7 (MSB)
1020
8 (carry)
511
Total No. Reference Patterns − 2,519
OUTPUT:
One 8-bit number and an output carry bit.
Number of output bits − 8 + 1 − 9.
Number of possible outputs − 29 − 512.
Table II
Reduced Reference Patterns that Need to be Stored in a Content-Addressable Memory to Convert an 8-Bit Binary Number to a Binary-Coded Modulo 5 Residue Number; These 8-Bit Binary Numbers Produce a 1 in the b2, b1, and b0 Bit Positions of the Binary-Coded Modulo 5 Residue Number as Listed
b2 = 1
b1 = 1
b0 = 1
00000100
10010101
000X0010
10010011
00X00001
10011001
01000000
10011010
0X001000
10110001
X0001000
10101001
001X0000
11000110
00X10000
0001X111
00001001
10111000
1X000000
11100100
1000X000
X0010111
00011000
11001100
X0101011
00100010
11010001
00010001
0X010111
0000X011
X0111010
10000001
01000100
00101X11
X0000011
01X00111
10010000
00111011
0X101011
00X00110
0101X011
01001111
00000X11
0X110101
0001X010
X1010011
00001110
01011110
0X000011
010X1101
X0010010
01X10110
00010011
01101101
0000110X
0110011X
001001X0
011001X1
00101100
01111100
000X1100
011X0110
01X00010
011101X0
00110001
10101110
00100X01
1000111X
X1000100
100011X1
01000101
10110011
0X100001
100X1110
011000X0
10X01101
01001010
11000111
1000010X
10011X01
100010X0
100111X0
01010100
11010110
100X0100
1X011001
10X01000
10X11100
01101000
11100101
10100X11
1100X110
10000110
11101010
0001011X
1X100011
X0001101
110010X1
10100100
11110100
0X100110
1010110X
00X10101
11X01001
11000010
001X1010
101X1100
X0011100
110110X0
11100000
01110111
0011010X
110X0101
0010X110
11X11000
10011111
01001X01
X0100110
1110X100
00011101
10111101
0101001X
0011111X
001010X1
00100111
11011011
01011X00
0111101X
001110X0
001111X1
00110110
11111001
01100X10
1011011X
X1001001
X1011101
01011001
0111000X
11001X11
010011X0
0110X111
01100011
11101111
100X1001
11011X10
01X01100
X1100111
01110010
11111110
1X001010
11101X01
01X10001
0111X110
10001011
1001100X
1111001X
X1011000
X1110110
101X0010
11111X00
0110X010
011110X1
1X101000
X1100010
101101X1
11000X01
10111011
1000X101
11X01110
11010X00
11101110
1001X100
1101X101
101000X1
111100X1
00011011
0X111111
101100X0
00111001
1X110111
1100X001
X0111111
01001110
110X1111
1101X000
X1111011
01101100
111X1101
110111X1
00110011
11X11101
Notes: (1) The bit number, n. starts at zero for the least significant bit, b0. and increases for more significant bits.
Table III
Reduced Reference Patterns that Need to be Stored in a Content-Addressable Memory to Implement Addition of Two Binary-Coded Modulo 5 Residue Numbers and an Input Carry; These Input Patterns Produce a 1 in the b2, b1, and b0 Bit Positions of the Binary-Coded Modulo 5 Sum as Listed
b2 = 1
b1 = 1
b0 = 1
0001000
0010110
00X0100
00100X1
0000X01
1001000
1000000
0100011
01000X0
001001X
0X00001
0010011
0100100
0110001
1001000
010x001
0000X10
0110010
011X000
0X00010
0X11001
0000111
1001001
00X0011
011100X
0010X00
1000X11
0010101
X000101
100011X
0X10000
X000110
0110111
0100111
0101000
0110101
1000100
0110110
Notes: (1) Each pattern consists of two three-bit input numbers followed by an input carry.
Table IV
Truth Table Corresponding to W2 Function Used in the MSD Addera
c1
x0
y0
W2
0
0
0
0
0
0
1
0
1
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
1
The quantity c1 is the input carry, x0 and y0 are the least significant bits of the two input numbers, and W2 provides the least significant bit of the output z0.
Table V
Number of Gates Required to Perform 8-Bit Addition by Truth-Table Look-Up Processing Using Direct Binary, Residue, and Modified Signed-Digit Number Systems including Encoding and Decoding