Abstract

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.

© 1986 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. e.g., F. J. Hill, G. R. Peterson, Digital Systems: Hardware Organization and Design (Wiley, New York, 1978).
  2. e.g., J. R. Jump, S. R. Ahuja, “Effective Pipelining of Digital Systems,” IEEE Trans. Comput. C-27, 855 (1978).
    [CrossRef]
  3. C. C. Guest, T. K. Gaylord, “Truth-Table Look-Up Optical Processing Utilizing Binary and Residue Arithmetic,” Appl. Opt. 19, 1201 (1980).
    [CrossRef] [PubMed]
  4. T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
    [CrossRef]
  5. C. C. Guest, M. M. Mirsalehi, T. K. Gaylord, “Residue Number System Truth-Table Look-Up Processing—Moduli Selection and Logical Minimization,” IEEE Trans. Comput. C-33, 927 (1984).
    [CrossRef]
  6. T. K. Gaylord, M. M. Mirsalehi, “Truth-Table Look-Up Processing: Number Representation, Multilevel Coding, and Logical Minimization,” Opt. Eng. 25, 22 (1986).
    [CrossRef]
  7. M. M. Mirsalehi, T. K. Gaylord, “Truth-Table Look-Up Parallel Data Processing Using an Optical Content-Addressable Memory,” Appl. Opt. 25, 2277 (1986).
    [CrossRef] [PubMed]
  8. e.g., S. Muroga, Logical Design and Switching Theory (Wiley, New York, 1979).
  9. E. I. Post, “Introduction to a General Theory of Elementary Propositions,” Am. J. Math. 43, 163 (1921).
    [CrossRef]
  10. D. C. Rine, Ed., Computer Science and Multiple-Valued Logic (North-Holland, Amsterdam, 1977).
  11. See the annual issues of Proceedings, International Symposium on Multiple-Valued Logic (IEEE, New York, 1971–1986).
  12. S. L. Hurst, “Multiple-Valued Logic—Its Status and Its Future,” IEEE Trans. Comput. C-33, 1160(1984).
    [CrossRef]
  13. Special issue on Digital Optical Computing, Multiple-Valued Logic/Digital Logic, Opt. Eng. 25, (1986).
  14. C. M. Allen, D. D. Givone, “A Minimization Technique for Multiple-Valued Logic System,” IEEE Trans. Comput. C-17, 182 (1968).
    [CrossRef]
  15. C. M. Allen, D. D. Givone, “The Allen-Givone Implementation Oriented Algebra,” in Ref. 10, Chap. 9.
  16. S. Y. H. Su, P. T. Cheung, “Computer Minimization of Multi-Valued Switching Functions,” IEEE Trans. Comput. C-21, 995 (1972).
    [CrossRef]
  17. S. Y. H. Su, P. T. Cheung, “Computer Simplification of Multi-Valued Switching Functions,” in Ref. 10, Chap. 7.
  18. W. R. Smith, “Minimization of Multivalued Functions,” in Ref. 10, Chap. 8.
  19. e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
    [CrossRef]
  20. H. J. Gallagher, T. K. Gaylord, M. G. Moharam, C. C. Guest, “Reconstruction of Binary-Data-Page Thick Holograms for an Arbitrarily Oriented Reference Beam,” Appl. Opt. 20, 300 (1981).
    [CrossRef] [PubMed]
  21. B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
    [CrossRef]
  22. H. L. Garner, “The Residue Number System,” IRE Trans. Electron. Comput. EC-8, 140 (1959).
    [CrossRef]
  23. N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

1986 (4)

T. K. Gaylord, M. M. Mirsalehi, “Truth-Table Look-Up Processing: Number Representation, Multilevel Coding, and Logical Minimization,” Opt. Eng. 25, 22 (1986).
[CrossRef]

Special issue on Digital Optical Computing, Multiple-Valued Logic/Digital Logic, Opt. Eng. 25, (1986).

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

M. M. Mirsalehi, T. K. Gaylord, “Truth-Table Look-Up Parallel Data Processing Using an Optical Content-Addressable Memory,” Appl. Opt. 25, 2277 (1986).
[CrossRef] [PubMed]

1985 (1)

T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
[CrossRef]

1984 (2)

C. C. Guest, M. M. Mirsalehi, T. K. Gaylord, “Residue Number System Truth-Table Look-Up Processing—Moduli Selection and Logical Minimization,” IEEE Trans. Comput. C-33, 927 (1984).
[CrossRef]

S. L. Hurst, “Multiple-Valued Logic—Its Status and Its Future,” IEEE Trans. Comput. C-33, 1160(1984).
[CrossRef]

1981 (1)

1980 (1)

1978 (1)

e.g., J. R. Jump, S. R. Ahuja, “Effective Pipelining of Digital Systems,” IEEE Trans. Comput. C-27, 855 (1978).
[CrossRef]

1972 (1)

S. Y. H. Su, P. T. Cheung, “Computer Minimization of Multi-Valued Switching Functions,” IEEE Trans. Comput. C-21, 995 (1972).
[CrossRef]

1971 (1)

e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
[CrossRef]

1968 (1)

C. M. Allen, D. D. Givone, “A Minimization Technique for Multiple-Valued Logic System,” IEEE Trans. Comput. C-17, 182 (1968).
[CrossRef]

1959 (1)

H. L. Garner, “The Residue Number System,” IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

1921 (1)

E. I. Post, “Introduction to a General Theory of Elementary Propositions,” Am. J. Math. 43, 163 (1921).
[CrossRef]

Ahuja, S. R.

e.g., J. R. Jump, S. R. Ahuja, “Effective Pipelining of Digital Systems,” IEEE Trans. Comput. C-27, 855 (1978).
[CrossRef]

Allen, C. M.

C. M. Allen, D. D. Givone, “A Minimization Technique for Multiple-Valued Logic System,” IEEE Trans. Comput. C-17, 182 (1968).
[CrossRef]

C. M. Allen, D. D. Givone, “The Allen-Givone Implementation Oriented Algebra,” in Ref. 10, Chap. 9.

Bocker, R. P.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Cheung, P. T.

S. Y. H. Su, P. T. Cheung, “Computer Minimization of Multi-Valued Switching Functions,” IEEE Trans. Comput. C-21, 995 (1972).
[CrossRef]

S. Y. H. Su, P. T. Cheung, “Computer Simplification of Multi-Valued Switching Functions,” in Ref. 10, Chap. 7.

Drake, B. L.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Gallagher, H. J.

Garner, H. L.

H. L. Garner, “The Residue Number System,” IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

Gaylord, T. K.

Givone, D. D.

C. M. Allen, D. D. Givone, “A Minimization Technique for Multiple-Valued Logic System,” IEEE Trans. Comput. C-17, 182 (1968).
[CrossRef]

C. M. Allen, D. D. Givone, “The Allen-Givone Implementation Oriented Algebra,” in Ref. 10, Chap. 9.

Guest, C. C.

Hill, F. J.

e.g., F. J. Hill, G. R. Peterson, Digital Systems: Hardware Organization and Design (Wiley, New York, 1978).

Hurst, S. L.

S. L. Hurst, “Multiple-Valued Logic—Its Status and Its Future,” IEEE Trans. Comput. C-33, 1160(1984).
[CrossRef]

Jump, J. R.

e.g., J. R. Jump, S. R. Ahuja, “Effective Pipelining of Digital Systems,” IEEE Trans. Comput. C-27, 855 (1978).
[CrossRef]

Lasher, M. E.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Lemke, C. E.

e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
[CrossRef]

Miceli, W. J.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Mirsalehi, M. M.

T. K. Gaylord, M. M. Mirsalehi, “Truth-Table Look-Up Processing: Number Representation, Multilevel Coding, and Logical Minimization,” Opt. Eng. 25, 22 (1986).
[CrossRef]

M. M. Mirsalehi, T. K. Gaylord, “Truth-Table Look-Up Parallel Data Processing Using an Optical Content-Addressable Memory,” Appl. Opt. 25, 2277 (1986).
[CrossRef] [PubMed]

C. C. Guest, M. M. Mirsalehi, T. K. Gaylord, “Residue Number System Truth-Table Look-Up Processing—Moduli Selection and Logical Minimization,” IEEE Trans. Comput. C-33, 927 (1984).
[CrossRef]

Moharam, M. G.

Muroga, S.

e.g., S. Muroga, Logical Design and Switching Theory (Wiley, New York, 1979).

Nikaido, T.

T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
[CrossRef]

Ogura, T.

T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
[CrossRef]

Patterson, R. H.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

Peterson, G. R.

e.g., F. J. Hill, G. R. Peterson, Digital Systems: Hardware Organization and Design (Wiley, New York, 1978).

Post, E. I.

E. I. Post, “Introduction to a General Theory of Elementary Propositions,” Am. J. Math. 43, 163 (1921).
[CrossRef]

Salkin, H. M.

e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
[CrossRef]

Smith, W. R.

W. R. Smith, “Minimization of Multivalued Functions,” in Ref. 10, Chap. 8.

Spielberg, K.

e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
[CrossRef]

Su, S. Y. H.

S. Y. H. Su, P. T. Cheung, “Computer Minimization of Multi-Valued Switching Functions,” IEEE Trans. Comput. C-21, 995 (1972).
[CrossRef]

S. Y. H. Su, P. T. Cheung, “Computer Simplification of Multi-Valued Switching Functions,” in Ref. 10, Chap. 7.

Szabo, N. S.

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

Tanaka, R. I.

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

Yamada, S-I.

T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
[CrossRef]

Am. J. Math. (1)

E. I. Post, “Introduction to a General Theory of Elementary Propositions,” Am. J. Math. 43, 163 (1921).
[CrossRef]

Appl. Opt. (3)

IEEE J. Solid-State Circuits (1)

T. Ogura, S-I. Yamada, T. Nikaido, “A 4-kbit Associative Memory LSI,” IEEE J. Solid-State Circuits SC-20, 1277 (1985).
[CrossRef]

IEEE Trans. Comput. (5)

C. C. Guest, M. M. Mirsalehi, T. K. Gaylord, “Residue Number System Truth-Table Look-Up Processing—Moduli Selection and Logical Minimization,” IEEE Trans. Comput. C-33, 927 (1984).
[CrossRef]

e.g., J. R. Jump, S. R. Ahuja, “Effective Pipelining of Digital Systems,” IEEE Trans. Comput. C-27, 855 (1978).
[CrossRef]

S. L. Hurst, “Multiple-Valued Logic—Its Status and Its Future,” IEEE Trans. Comput. C-33, 1160(1984).
[CrossRef]

C. M. Allen, D. D. Givone, “A Minimization Technique for Multiple-Valued Logic System,” IEEE Trans. Comput. C-17, 182 (1968).
[CrossRef]

S. Y. H. Su, P. T. Cheung, “Computer Minimization of Multi-Valued Switching Functions,” IEEE Trans. Comput. C-21, 995 (1972).
[CrossRef]

IRE Trans. Electron. Comput. (1)

H. L. Garner, “The Residue Number System,” IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

Oper. Res. (1)

e.g., C. E. Lemke, H. M. Salkin, K. Spielberg, “Set Covering by Single Branch Enumeration with Linear Programming Subproblems,” Oper. Res. 19, 988 (1971).
[CrossRef]

Opt. Eng. (3)

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic Computing Using the Modified Signed-Digit Number Representation,” Opt. Eng. 25, 38 (1986).
[CrossRef]

T. K. Gaylord, M. M. Mirsalehi, “Truth-Table Look-Up Processing: Number Representation, Multilevel Coding, and Logical Minimization,” Opt. Eng. 25, 22 (1986).
[CrossRef]

Special issue on Digital Optical Computing, Multiple-Valued Logic/Digital Logic, Opt. Eng. 25, (1986).

Other (8)

D. C. Rine, Ed., Computer Science and Multiple-Valued Logic (North-Holland, Amsterdam, 1977).

See the annual issues of Proceedings, International Symposium on Multiple-Valued Logic (IEEE, New York, 1971–1986).

S. Y. H. Su, P. T. Cheung, “Computer Simplification of Multi-Valued Switching Functions,” in Ref. 10, Chap. 7.

W. R. Smith, “Minimization of Multivalued Functions,” in Ref. 10, Chap. 8.

C. M. Allen, D. D. Givone, “The Allen-Givone Implementation Oriented Algebra,” in Ref. 10, Chap. 9.

e.g., F. J. Hill, G. R. Peterson, Digital Systems: Hardware Organization and Design (Wiley, New York, 1978).

e.g., S. Muroga, Logical Design and Switching Theory (Wiley, New York, 1979).

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

Cited By

OSA participates in CrossRef's Cited-By Linking service. Citing articles from OSA journals and other participating publishers are listed here.

Alert me when this article is cited.


Figures (9)

Fig. 1
Fig. 1

Flow chart of procedure for obtaining the prime implicants of a multivalued function. The steps labeled on the chart refer to the steps as listed in Sec. II.C.1.

Fig. 2
Fig. 2

Example of determining all prime implicants in the extended Quine-McCluskey method.

Fig. 3
Fig. 3

Example of deriving a minimal sum for the truth table provided in Fig. 2: (a) constructing the table of choice; (b) table reduced by removing essential rows; (c) table reduced by eliminating dominated rows; (d) table reduced by eliminating dominating columns; (e) table reduced by removing essential rows; (f) table reduced by eliminating dominated rows; (g) table reduced by eliminating dominating columns; (h) table reduced by removing essential rows; (i) table reduced by removing dominated row; (j) absolute minimal sum set obtained.

Fig. 4
Fig. 4

Examples of realizing the reference patterns by logic gates: (a) binary coded pattern (10X1); (b) ternary coded pattern (2X1X02). The digit numbers start from the least significant digit a0.

Fig. 5
Fig. 5

Modified signed-digit (MSD) adder array for two five-digit ternary numbers (from Ref. 21).

Fig. 6
Fig. 6

Logical gate implementation of the truth table corresponding to the output digit zn (n ≠ 0, 1, N) in the MSD adder.

Fig. 7
Fig. 7

Logical gate implementation of the truth table corresponding to the output digit z0 in the MSD adder.

Fig. 8
Fig. 8

Logical gate implementation of the truth table corresponding to the output digit z1 in the MSD adder.

Fig. 9
Fig. 9

Logical gate implementation of the truth table corresponding to the last digit of the output zN in the MSD adder.

Tables (6)

Tables Icon

Table I Truth Tables Corresponding to the Transfer (T and T1) and Weight (Wand W1) Functions Used In the MSD Adder

Tables Icon

Table II Reduced Reference Patterns that Produce a 1 In the Output Digit zn (n ≠ 0, 1, N) of the MSD Addera

Tables Icon

Table III Reduced Reference Patterns that Produce a 1 in the Output Digit z1 of the MSD Addera

Tables Icon

Table IV Reduced Reference Patterns that Produce a 1 in the Last Output Digit zN of the MSD Addera

Tables Icon

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

Tables Icon

Table VI Comparison of Number of Required Reference Patterns to Perform 16-Bit Full-Precision Addition Using Various Encoding Schemes

Metrics