Discrete numerical values in digital processing systems may be encoded in two-level (binary) or higher-level (multilevel) representations. Multilevel coding can produce smaller and more efficient processors. In truth-table lookup processing, the number of entries (reference patterns) can be reduced using multilevel coding. Since parallel-input/parallel-output optical truth-table lookup processors can be constructed based on holographic content-addressable memories, it is essential to know the minimum storage required to implement various functions. A new simple method for reducing multivalued functions is presented. This method is based on an extension of the Quine-McCluskey minimization method used for binary logic functions. This minimization method is then applied to the truth tables representing (1) modified signed-digit addition, (2) residue addition, and (3) residue multiplication. A programmable logic array gate configuration for the modified signed-digit adder is presented.
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.
Truth Tables Corresponding to the Transfer (T and T1) and Weight (Wand W1) Functions Used In the MSD Adder
X
Y
T
W
T1
W1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
1
0
Table II
Reduced Reference Patterns that Produce a 1 In the Output Digit zn (n ≠ 0, 1, N) of the MSD Addera
1
X
1
X
0
1
X
0
1
X
X01
1
1
X
0
X01
X01
0
1
X01
X
0
1
X
0
X01
1
0
1
X
1
X
X01
1
X01
0
0
1
0
X
0
0
X
0
1
X
0
X
1
0
1
X01
0
X01
X01
1
0
0
X01
1
X
0
X
0
1
1
0
X01
X
0
X01
0
1
0
X01
0
1
0
X
1
X
0
X01
X
0
1
1
0
1
0
X01
0
1
0
X01
0
1
X
X
1
1
X01
X
0
0
X01
1
X01
X01
1
X01
0
0
X
0
X
X01
X
1
1
0
0
1
X01
1
X01
X01
X01
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as YnYn−1Yn−2XnXn−1Xn−2. The digit number of the output starts with n = 0 for the least significant digit and ends with n = N for the most significant digit
Table III
Reduced Reference Patterns that Produce a 1 in the Output Digit z1 of the MSD Addera
0
1
0
1
0
0
0
0
X01
0
1
0
1
0
1
0
X01
0
0
0
X01
1
1
0
1
X01
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as y1y0x1x0.
Table IV
Reduced Reference Patterns that Produce a 1 in the Last Output Digit zN of the MSD Addera
0
X
1
X
1
1
X01
X
X01
X
1
1
X01
X01
1
X01
X01
1
1
X
1
X01
X01
X01
1
X
X01
1
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as YN−1YN−2XN−1XN−2
Table V
Optimum Sets of Moduli and Number of Required Reference Patterns Nr for Implementing Some Practical Operations with a Content-Addressable Memory with Two-Level, Three-Level, and Five-Level Coding Alloweda
Operation
Required Range
Moduli
Corresponding Coding Levels
Covered Range
Nr
16-bit fixed-point addition
0–65,535
3, 5, 7, 8, 11, 13
2 or 3 or 5, 3, 2, 2, 3, 5
0–120,119
286
32-bit fixed-point addition
0–4,294,967,295
5, 7, 9, 11, 13, 16, 17, 19, 23
3, 2, 3, 3, 5, 2, 3, 3, 2
0–5,354,228,879
1001
16-bit fixed-point multiplication
0–65,535
3, 5, 7, 8, 11, 13
2 or 3 or 5, 2 or 3, 2, 2, 5, 3
0–120,119
234
32-bit fixed-point multiplication
0–4,294,967,295
5, 7, 9, 11, 13, 16, 17, 19, 23
2 or 3, 2, 3, 5, 3, 2, 3, 5, 3
0–5,354,228,879
1067
The corresponding coding level(s) shown for each modulus is (are) determined such that the number of reference patterns is minimized. For each operation, the required range of numbers and the range of numbers covered by the selected moduli are given.
Table VI
Comparison of Number of Required Reference Patterns to Perform 16-Bit Full-Precision Addition Using Various Encoding Schemes
Without Logical Reduction:
Binary
3.65 × 1010
Binary–coded residue
694
Multilevel–coded residue
568
Modified–signed digit
5212
With Logical Reduction:
With Logical Reduction:
Binary
3.28 × 105
Binary–coded residue
327
Multilevel–coded residue
300
Modified–signed digit
822
Tables (6)
Table I
Truth Tables Corresponding to the Transfer (T and T1) and Weight (Wand W1) Functions Used In the MSD Adder
X
Y
T
W
T1
W1
0
0
0
1
0
1
0
0
0
0
0
1
0
0
0
0
0
0
0
0
1
1
0
1
1
0
0
0
0
1
0
1
0
1
1
1
1
0
1
0
Table II
Reduced Reference Patterns that Produce a 1 In the Output Digit zn (n ≠ 0, 1, N) of the MSD Addera
1
X
1
X
0
1
X
0
1
X
X01
1
1
X
0
X01
X01
0
1
X01
X
0
1
X
0
X01
1
0
1
X
1
X
X01
1
X01
0
0
1
0
X
0
0
X
0
1
X
0
X
1
0
1
X01
0
X01
X01
1
0
0
X01
1
X
0
X
0
1
1
0
X01
X
0
X01
0
1
0
X01
0
1
0
X
1
X
0
X01
X
0
1
1
0
1
0
X01
0
1
0
X01
0
1
X
X
1
1
X01
X
0
0
X01
1
X01
X01
1
X01
0
0
X
0
X
X01
X
1
1
0
0
1
X01
1
X01
X01
X01
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as YnYn−1Yn−2XnXn−1Xn−2. The digit number of the output starts with n = 0 for the least significant digit and ends with n = N for the most significant digit
Table III
Reduced Reference Patterns that Produce a 1 in the Output Digit z1 of the MSD Addera
0
1
0
1
0
0
0
0
X01
0
1
0
1
0
1
0
X01
0
0
0
X01
1
1
0
1
X01
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as y1y0x1x0.
Table IV
Reduced Reference Patterns that Produce a 1 in the Last Output Digit zN of the MSD Addera
0
X
1
X
1
1
X01
X
X01
X
1
1
X01
X01
1
X01
X01
1
1
X
1
X01
X01
X01
1
X
X01
1
Each pattern consists of the effective digits of the two input numbers (X and Y) and is expressible as YN−1YN−2XN−1XN−2
Table V
Optimum Sets of Moduli and Number of Required Reference Patterns Nr for Implementing Some Practical Operations with a Content-Addressable Memory with Two-Level, Three-Level, and Five-Level Coding Alloweda
Operation
Required Range
Moduli
Corresponding Coding Levels
Covered Range
Nr
16-bit fixed-point addition
0–65,535
3, 5, 7, 8, 11, 13
2 or 3 or 5, 3, 2, 2, 3, 5
0–120,119
286
32-bit fixed-point addition
0–4,294,967,295
5, 7, 9, 11, 13, 16, 17, 19, 23
3, 2, 3, 3, 5, 2, 3, 3, 2
0–5,354,228,879
1001
16-bit fixed-point multiplication
0–65,535
3, 5, 7, 8, 11, 13
2 or 3 or 5, 2 or 3, 2, 2, 5, 3
0–120,119
234
32-bit fixed-point multiplication
0–4,294,967,295
5, 7, 9, 11, 13, 16, 17, 19, 23
2 or 3, 2, 3, 5, 3, 2, 3, 5, 3
0–5,354,228,879
1067
The corresponding coding level(s) shown for each modulus is (are) determined such that the number of reference patterns is minimized. For each operation, the required range of numbers and the range of numbers covered by the selected moduli are given.
Table VI
Comparison of Number of Required Reference Patterns to Perform 16-Bit Full-Precision Addition Using Various Encoding Schemes