Abstract

We propose a simple recoded trinary signed-digit number representation for parallel optical computing. This technique performs multidigit carry-free addition and borrow-free subtraction in constant time, using only 50% of the minterme required in the most recently reported trinary signed-digit arithmetic technique. One may use a single-step optoelectronic or a two step all-optical architecture to implement the proposed technique.

© 1994 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).
  2. A. Louri, “Parallel implementation of optical symbolic substitution logic using shadowcasting and polarization,” Appl. Opt. 30, 540–548 (1991).
    [CrossRef] [PubMed]
  3. M. M. Mirsalehi, T. K. Gaylord, “Truth-table look-up parallel processing using an optical content-addressable memory,” Appl. Opt. 25, 2277–2283 (1986).
    [CrossRef] [PubMed]
  4. N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
    [CrossRef]
  5. M. S. Alam, M. A. Karim, A. A. S. Awwal, J. J. Westerkamp, “Optical processing based on conditional higher-order trinary modified signed-digit symbolic substitution,” Appl. Opt. 31, 5614–5621 (1992).
    [CrossRef] [PubMed]
  6. A. Avizienis, “Signed-digit number representation for fast parallel arithmetic,” IRE Trans. Electron. Comput. EC-10, 389–400 (1961).
    [CrossRef]
  7. K. Hwang, D. K. Panda, “High-radix symbolic substitution and superposition techniques for optical matrix algebraic computations,” Opt. Eng. 31, 2422–2433 (1992).
    [CrossRef]
  8. B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).
  9. A. A. S. Awwal, M. N. Islam, M. A. Karim, “Modified signed-digit trinary arithmetic by using optical symbolic substitution,” Appl. Opt. 31, 1687–1694 (1992).
    [CrossRef] [PubMed]
  10. R. Arrathoon, S. P. Kozaitis, “Shadow casting for multiple-valued associated logic,” Opt. Eng. 25, 29–37 (1986).
  11. K. H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
    [CrossRef] [PubMed]
  12. R. P. Bocker, B. L. Drake, M. E. Lasher, T. B. Henderson, “Modified signed-digit addition and subtraction using optical symbolic substitution,” Appl. Opt. 25, 2456–2457 (1986).
    [CrossRef] [PubMed]
  13. A. K. Cherri, M. A. Karim, “Modified signed-digit arithmetic using an efficient symbolic substitution,” Appl. Opt. 27, 3824–3827 (1988).
    [CrossRef] [PubMed]
  14. Y. Li, G. Eichmann, “Conditional symbolic modified signed-digit arithmetic using optical content-addressable memory logic elements,” Appl. Opt. 26, 2328–2333 (1987).
    [CrossRef] [PubMed]
  15. Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
    [CrossRef] [PubMed]
  16. S. Barua, “High-speed multiplier for digital signal processing,” Opt. Eng. 30, 1997–2002 (1991).
    [CrossRef]
  17. A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of the 10th International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.
  18. B. Parhami, “Carry-free addition of binary signed-digit numbers,” IEEE Trans. Comput. 37, 1470–1476 (1988).
    [CrossRef]
  19. A. A. S. Awwal, “Recoded signed-digit binary addition-subtraction using opto-electronic symbolic substitution,” Appl. Opt. 31, 3205–3208 (1992).
    [CrossRef] [PubMed]
  20. K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).
  21. E. Botha, D. Casasent, E. Barnhard, “Optical symbolic substitution using multichannel correlators,” Appl. Opt. 27, 817–818 (1987).
    [CrossRef]
  22. J. N. Mait, K. H. Brenner, “Optical symbolic substitution: system design using phase-only holograms,” Appl. Opt. 27, 1692–1700 (1988).
    [CrossRef] [PubMed]
  23. R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 29, 2126–2134 (1990).
    [CrossRef] [PubMed]
  24. S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified signed-digit optical computing using fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
    [CrossRef] [PubMed]

1992 (5)

1991 (2)

1990 (1)

1989 (2)

K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

1988 (3)

1987 (2)

1986 (5)

1985 (2)

N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
[CrossRef]

T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).

1961 (1)

A. Avizienis, “Signed-digit number representation for fast parallel arithmetic,” IRE Trans. Electron. Comput. EC-10, 389–400 (1961).
[CrossRef]

Alam, M. S.

Arrathoon, R.

R. Arrathoon, S. P. Kozaitis, “Shadow casting for multiple-valued associated logic,” Opt. Eng. 25, 29–37 (1986).

Avizienis, A.

A. Avizienis, “Signed-digit number representation for fast parallel arithmetic,” IRE Trans. Electron. Comput. EC-10, 389–400 (1961).
[CrossRef]

Awwal, A. A. S.

Barnhard, E.

Barua, S.

S. Barua, “High-speed multiplier for digital signal processing,” Opt. Eng. 30, 1997–2002 (1991).
[CrossRef]

Bocker, R. P.

R. P. Bocker, B. L. Drake, M. E. Lasher, T. B. Henderson, “Modified signed-digit addition and subtraction using optical symbolic substitution,” Appl. Opt. 25, 2456–2457 (1986).
[CrossRef] [PubMed]

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

Botha, E.

Brenner, K. H.

Campbell, S.

Casasent, D.

Cherri, A. K.

Drake, B. L.

R. P. Bocker, B. L. Drake, M. E. Lasher, T. B. Henderson, “Modified signed-digit addition and subtraction using optical symbolic substitution,” Appl. Opt. 25, 2456–2457 (1986).
[CrossRef] [PubMed]

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

Eichmann, G.

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

Y. Li, G. Eichmann, “Conditional symbolic modified signed-digit arithmetic using optical content-addressable memory logic elements,” Appl. Opt. 26, 2328–2333 (1987).
[CrossRef] [PubMed]

Gaylord, T. K.

M. M. Mirsalehi, T. K. Gaylord, “Truth-table look-up parallel processing using an optical content-addressable memory,” Appl. Opt. 25, 2277–2283 (1986).
[CrossRef] [PubMed]

T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).

Guest, C. C.

T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).

Henderson, T. B.

Huang, A.

K. H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
[CrossRef] [PubMed]

A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of the 10th International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.

Hwang, K.

K. Hwang, D. K. Panda, “High-radix symbolic substitution and superposition techniques for optical matrix algebraic computations,” Opt. Eng. 31, 2422–2433 (1992).
[CrossRef]

Islam, M. N.

Karim, M. A.

Kim, D. H.

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

Kostrzewski, A.

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

Kozaitis, S. P.

R. Arrathoon, S. P. Kozaitis, “Shadow casting for multiple-valued associated logic,” Opt. Eng. 25, 29–37 (1986).

Lasher, M. E.

R. P. Bocker, B. L. Drake, M. E. Lasher, T. B. Henderson, “Modified signed-digit addition and subtraction using optical symbolic substitution,” Appl. Opt. 25, 2456–2457 (1986).
[CrossRef] [PubMed]

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

Li, Y.

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

Y. Li, G. Eichmann, “Conditional symbolic modified signed-digit arithmetic using optical content-addressable memory logic elements,” Appl. Opt. 26, 2328–2333 (1987).
[CrossRef] [PubMed]

Liu, H. K.

Lohmann, A. W.

K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).

Louri, A.

Mait, J. N.

Merklein, T. K.

K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).

Miceli, W. J.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

Mirsalehi, M. M.

M. M. Mirsalehi, T. K. Gaylord, “Truth-table look-up parallel processing using an optical content-addressable memory,” Appl. Opt. 25, 2277–2283 (1986).
[CrossRef] [PubMed]

T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).

Panda, D. K.

K. Hwang, D. K. Panda, “High-radix symbolic substitution and superposition techniques for optical matrix algebraic computations,” Opt. Eng. 31, 2422–2433 (1992).
[CrossRef]

Parhami, B.

B. Parhami, “Carry-free addition of binary signed-digit numbers,” IEEE Trans. Comput. 37, 1470–1476 (1988).
[CrossRef]

Patterson, R. H.

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

Pedrini, G.

Streibl, N.

Takagi, N.

N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
[CrossRef]

Thalmann, R.

Weible, K. J.

Westerkamp, J. J.

Yajima, S.

N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
[CrossRef]

Yasura, H.

N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
[CrossRef]

Yeh, P.

Zhou, S.

Appl. Opt. (12)

M. S. Alam, M. A. Karim, A. A. S. Awwal, J. J. Westerkamp, “Optical processing based on conditional higher-order trinary modified signed-digit symbolic substitution,” Appl. Opt. 31, 5614–5621 (1992).
[CrossRef] [PubMed]

A. Louri, “Parallel implementation of optical symbolic substitution logic using shadowcasting and polarization,” Appl. Opt. 30, 540–548 (1991).
[CrossRef] [PubMed]

M. M. Mirsalehi, T. K. Gaylord, “Truth-table look-up parallel processing using an optical content-addressable memory,” Appl. Opt. 25, 2277–2283 (1986).
[CrossRef] [PubMed]

A. A. S. Awwal, M. N. Islam, M. A. Karim, “Modified signed-digit trinary arithmetic by using optical symbolic substitution,” Appl. Opt. 31, 1687–1694 (1992).
[CrossRef] [PubMed]

K. H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
[CrossRef] [PubMed]

R. P. Bocker, B. L. Drake, M. E. Lasher, T. B. Henderson, “Modified signed-digit addition and subtraction using optical symbolic substitution,” Appl. Opt. 25, 2456–2457 (1986).
[CrossRef] [PubMed]

A. K. Cherri, M. A. Karim, “Modified signed-digit arithmetic using an efficient symbolic substitution,” Appl. Opt. 27, 3824–3827 (1988).
[CrossRef] [PubMed]

Y. Li, G. Eichmann, “Conditional symbolic modified signed-digit arithmetic using optical content-addressable memory logic elements,” Appl. Opt. 26, 2328–2333 (1987).
[CrossRef] [PubMed]

E. Botha, D. Casasent, E. Barnhard, “Optical symbolic substitution using multichannel correlators,” Appl. Opt. 27, 817–818 (1987).
[CrossRef]

J. N. Mait, K. H. Brenner, “Optical symbolic substitution: system design using phase-only holograms,” Appl. Opt. 27, 1692–1700 (1988).
[CrossRef] [PubMed]

R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 29, 2126–2134 (1990).
[CrossRef] [PubMed]

A. A. S. Awwal, “Recoded signed-digit binary addition-subtraction using opto-electronic symbolic substitution,” Appl. Opt. 31, 3205–3208 (1992).
[CrossRef] [PubMed]

IEEE Trans. Comput. (2)

B. Parhami, “Carry-free addition of binary signed-digit numbers,” IEEE Trans. Comput. 37, 1470–1476 (1988).
[CrossRef]

N. Takagi, H. Yasura, S. Yajima, “High speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–795 (1985).
[CrossRef]

IRE Trans. Electron. Comput. (1)

A. Avizienis, “Signed-digit number representation for fast parallel arithmetic,” IRE Trans. Electron. Comput. EC-10, 389–400 (1961).
[CrossRef]

Opt. Eng. (6)

K. Hwang, D. K. Panda, “High-radix symbolic substitution and superposition techniques for optical matrix algebraic computations,” Opt. Eng. 31, 2422–2433 (1992).
[CrossRef]

B. L. Drake, R. P. Bocker, M. E. Lasher, R. H. Patterson, W. J. Miceli, “Photonic computing using modified signed-digit numbers representation,” Opt. Eng. 25, 38–43 (1986).

R. Arrathoon, S. P. Kozaitis, “Shadow casting for multiple-valued associated logic,” Opt. Eng. 25, 29–37 (1986).

T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).

S. Barua, “High-speed multiplier for digital signal processing,” Opt. Eng. 30, 1997–2002 (1991).
[CrossRef]

K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).

Opt. Lett (1)

Y. Li, D. H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-state optical modified signed-digit arithmetic,” Opt. Lett 14, pp 1254–1256 (1989).
[CrossRef] [PubMed]

Opt. Lett. (1)

Other (1)

A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of the 10th International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.

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 (4)

Fig. 1
Fig. 1

Optical implementation for the recoded trinary signed-digit arithmetic using CAM.

Fig. 2
Fig. 2

Quadrail coding scheme.

Fig. 3
Fig. 3

Nonholographic CAM for generating the 1 output of the recoding truth table.

Fig. 4
Fig. 4

Nonholographic CAM’s for generating the (a) 1 and (b) 2 outputs of the addition truth table.

Tables (3)

Tables Icon

Table 1 Recoding Truth Table for Trinary Signed-Digit Numbers

Tables Icon

Table 2 Addition Truth Table for Recoded Trinary Signed-Digit Numbers

Tables Icon

Table 3 Reduced Minterms for the Recoding Truth Table

Equations (4)

Equations on this page are rendered with MathJax. Learn more.

D = i = 1 n x i r i ,
( 22 ) 3 = ( 1000 ) 2 = ( 8 ) 10 ( 222222222222222 ) 3 = ( 1101 1010 1111 0010 0110 1010 ) 2 = ( 14348906 ) 10 .
C i × C i 1 { 2 , 4 } , 0 < i ( n + 1 ) .
Operand Trinary signed - digit Recoded trinary signed - Decimal type representation digit representation representation Addend = ( 0 221 2 ¯ 2 ¯ 1 ¯ 2 0 0 0 ) 3 = ( 10 1 ¯ 0010 1 ¯ ) 3 = ( 1952 ) 10 Augend = ( 0 1 ¯ 121 2 ¯ 2 ¯ 2 0 0 0 ) 3 = ( 00 1 ¯ 1 ¯ 01 1 ¯ 1 ¯ ) 3 = ( 319 ) 10 Final   sum = = ( 10 2 ¯ 1 ¯ 02 1 ¯ 2 ¯ ) 3 = ( 1633 ) 10

Metrics