Abstract

Techniques for higher-order modified signed-digit trinary arithmetic by using optical symbolic substitution are presented. This method provides fast multibit computation by adopting a two-step symbolic-substitution scheme. Since more information is represented in fewer digits, this technique leads to a compact design. A content-addressable memory-based and a joint transform correlator-based optical implemention for the proposed technique are also presented.

© 1992 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).
  2. T. K. Gaylord, M. M. Mirsalehi, C. C. Guest, “Optical digital truth-table look-up processing,” Opt. Eng. 24, 48–58 (1985).
  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. A. Hwang, Y. Tsunida, J. W. Goodman, S. Ishihara, “Optical computation using residue arithmetic,” Appl. Opt. 18, 149–162 (1979).
    [CrossRef]
  5. 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]
  6. A. Avizienis, “Signed-digit number representation for fast parallel arithmetic,” IRE Trans. Electron. Comput. EC-10, 389–400 (1961).
    [CrossRef]
  7. B. L. Drake, R. P. Bocker, M. E. Lasher, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).
  8. A. K. Cherri, M. A. Karim, “Modified signed-digit arithmetic using an efficient symbolic substitution,” Appl. Opt. 27, 3824–3827 (1988).
    [CrossRef] [PubMed]
  9. M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
    [CrossRef] [PubMed]
  10. T. K. Gaylord, M. M. Mirsalehi, “Truth-table look-up processing: number representation, multilevel coding and logical minimization,” Opt. Eng. 25, 22–28 (1986).
  11. A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of the IEEE Tenth International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.
    [CrossRef]
  12. K. H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
    [CrossRef] [PubMed]
  13. 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]
  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. S. P. Kozaitis, “Higher-ordered rules for symbolic substitution,” Opt. Commun. 65, 339–342 (1988).
    [CrossRef]
  16. G. Eichmann, A. Kostrzewski, D. H. Kim, Y. Li, “Optical higher-order symbolic recognition,” Appl. Opt. 29, pp. 2135–2147 (1990).
    [CrossRef] [PubMed]
  17. K. H. Brenner, A. W. Lohmann, T. K. Merklein, “Symbolic substitution implemented by spatial filtering logic,” Opt. Eng. 28, 390–395 (1989).
  18. E. Botha, D. Casasent, E. Barnhard, “Optical symbolic substitution using multichannel correlators,” Appl. Opt. 27, 817–818 (1987).
    [CrossRef]
  19. J. N. Mait, K. H. Brenner, “Optical symbolic substitution: system design using phase-only holograms,” Appl. Opt. 27, 1692–1700 (1988).
    [CrossRef] [PubMed]
  20. R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 29, 2126–2134 (1990).
    [CrossRef] [PubMed]
  21. M. A. Karim, A. A. S. Awwal, Optical Computing An Introduction (Wiley, New York, 1992).
  22. A. K. Cherri, M. A. Karim, “Symbolic substitution based operations using holograms: multiplication and histogram equilization,” Opt. Eng. 28, 638–642 (1989).
  23. B. Javidi, C. Kuo, “Joint transform image correlation using a binary spatial light modulator at the Fourier plane,” Appl. Opt. 27, 663–665 (1988).
    [CrossRef] [PubMed]
  24. F. T. S. Yu, F. Cheng, T. Nagata, D. A. Gregory, “Effect of fringe binarization of multiobject joint transform correlation,” Appl. Opt. 28, 2988–2990 (1989).
    [CrossRef] [PubMed]
  25. M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
    [CrossRef]
  26. A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: design of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
    [CrossRef] [PubMed]
  27. A. K. Cherri, M. A. Karim, “Symbolic substitution based flagged arithmetic using polarization-encoded optical shadow-casting,” Opt. Commun. 70, 455–461 (1989).
    [CrossRef]

1991

M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
[CrossRef]

1990

1989

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

K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).

A. K. Cherri, M. A. Karim, “Symbolic substitution based operations using holograms: multiplication and histogram equilization,” Opt. Eng. 28, 638–642 (1989).

A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: design of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
[CrossRef] [PubMed]

A. K. Cherri, M. A. Karim, “Symbolic substitution based flagged arithmetic using polarization-encoded optical shadow-casting,” Opt. Commun. 70, 455–461 (1989).
[CrossRef]

F. T. S. Yu, F. Cheng, T. Nagata, D. A. Gregory, “Effect of fringe binarization of multiobject joint transform correlation,” Appl. Opt. 28, 2988–2990 (1989).
[CrossRef] [PubMed]

1988

1987

1986

1985

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

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]

1979

1961

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

Alam, M. S.

M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
[CrossRef]

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.

M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
[CrossRef]

A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: design of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
[CrossRef] [PubMed]

M. A. Karim, A. A. S. Awwal, Optical Computing An Introduction (Wiley, New York, 1992).

Barnhard, E.

Bocker, R. P.

B. L. Drake, R. P. Bocker, M. E. Lasher, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).

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]

Botha, E.

Brenner, K. H.

Casasent, D.

Cheng, F.

Cherri, A. K.

A. K. Cherri, M. A. Karim, “Symbolic substitution based flagged arithmetic using polarization-encoded optical shadow-casting,” Opt. Commun. 70, 455–461 (1989).
[CrossRef]

A. K. Cherri, M. A. Karim, “Symbolic substitution based operations using holograms: multiplication and histogram equilization,” Opt. Eng. 28, 638–642 (1989).

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

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, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).

Eichmann, G.

Gaylord, T. K.

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

T. K. Gaylord, M. M. Mirsalehi, “Truth-table look-up processing: number representation, multilevel coding and logical minimization,” Opt. Eng. 25, 22–28 (1986).

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).

Goodman, J. W.

Gregory, D. A.

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.

B. L. Drake, R. P. Bocker, M. E. Lasher, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).

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]

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 IEEE Tenth International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.
[CrossRef]

Hwang, A.

Hwang, K.

K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).

Ishihara, S.

Javidi, B.

Karim, M. A.

M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
[CrossRef]

A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: design of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
[CrossRef] [PubMed]

A. K. Cherri, M. A. Karim, “Symbolic substitution based flagged arithmetic using polarization-encoded optical shadow-casting,” Opt. Commun. 70, 455–461 (1989).
[CrossRef]

A. K. Cherri, M. A. Karim, “Symbolic substitution based operations using holograms: multiplication and histogram equilization,” Opt. Eng. 28, 638–642 (1989).

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

M. A. Karim, A. A. S. Awwal, Optical Computing An Introduction (Wiley, New York, 1992).

Kim, D. H.

Kostrzewski, A.

Kozaitis, S. P.

S. P. Kozaitis, “Higher-ordered rules for symbolic substitution,” Opt. Commun. 65, 339–342 (1988).
[CrossRef]

Kuo, C.

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, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).

Li, Y.

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.

K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).

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).

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]

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

T. K. Gaylord, M. M. Mirsalehi, “Truth-table look-up processing: number representation, multilevel coding and logical minimization,” Opt. Eng. 25, 22–28 (1986).

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

Nagata, T.

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.

Tsunida, Y.

Weible, K. 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]

Yu, F. T. S.

Appl. Opt.

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. Hwang, Y. Tsunida, J. W. Goodman, S. Ishihara, “Optical computation using residue arithmetic,” Appl. Opt. 18, 149–162 (1979).
[CrossRef]

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

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[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]

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]

G. Eichmann, A. Kostrzewski, D. H. Kim, Y. Li, “Optical higher-order symbolic recognition,” Appl. Opt. 29, pp. 2135–2147 (1990).
[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]

B. Javidi, C. Kuo, “Joint transform image correlation using a binary spatial light modulator at the Fourier plane,” Appl. Opt. 27, 663–665 (1988).
[CrossRef] [PubMed]

F. T. S. Yu, F. Cheng, T. Nagata, D. A. Gregory, “Effect of fringe binarization of multiobject joint transform correlation,” Appl. Opt. 28, 2988–2990 (1989).
[CrossRef] [PubMed]

A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: design of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
[CrossRef] [PubMed]

IEEE Trans. Comput.

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.

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

Microwave Opt. Tech. Lett.

M. S. Alam, M. A. Karim, A. A. S. Awwal, “Improved correlation discrimination using joint Fourier transform optical correlator,” Microwave Opt. Tech. Lett. 4, 103–106 (1991).
[CrossRef]

Opt. Commun.

A. K. Cherri, M. A. Karim, “Symbolic substitution based flagged arithmetic using polarization-encoded optical shadow-casting,” Opt. Commun. 70, 455–461 (1989).
[CrossRef]

S. P. Kozaitis, “Higher-ordered rules for symbolic substitution,” Opt. Commun. 65, 339–342 (1988).
[CrossRef]

Opt. Eng.

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

K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).

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

B. L. Drake, R. P. Bocker, M. E. Lasher, T. B. Henderson, “Photonic computing using modified signed-digit number representation,” Opt. Eng. 25, 38–43 (1986).

T. K. Gaylord, M. M. Mirsalehi, “Truth-table look-up processing: number representation, multilevel coding and logical minimization,” Opt. Eng. 25, 22–28 (1986).

A. K. Cherri, M. A. Karim, “Symbolic substitution based operations using holograms: multiplication and histogram equilization,” Opt. Eng. 28, 638–642 (1989).

Other

M. A. Karim, A. A. S. Awwal, Optical Computing An Introduction (Wiley, New York, 1992).

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

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

Fig. 1
Fig. 1

(a) Triple rail encoding scheme suitable for optical implementation; (b) coded SS rule for group 1 of Table 2; (c) coded SS rule for group 2 of Table 2.

Fig. 2
Fig. 2

Addition of two trinary MSD numbers by using higher-order MSD SS rules of Table 2.

Fig. 3
Fig. 3

Optical implementation of CAM recording and reconstruction scheme for higher-order trinary MSD arithmetic.

Fig. 4
Fig. 4

Optical implementation of the higher-order MSD scheme by using a JTC. LCTV, liquid-crystal television.

Fig. 5
Fig. 5

(a) Input joint image with the same minterm as the reference and the object (for the group 2 SS rule of Table 2); (b) correlation output corresponding to Fig. 5(a).

Fig. 6
Fig. 6

(a) Input joint image with different minterms for the reference and the object; (b) correlation output corresponding to Fig. 6(a).

Tables (2)

Tables Icon

Table 1 Trinary MSD Representations of the Sums of Two 2-Bit Numbers

Tables Icon

Table 2 Higher-Order Trinary MSD SS Rule Truth Table for Addition

Equations (4)

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

D = i = 1 n d i r i ,
( 22 ) 3 = ( 1000 ) 2 = ( 8 ) 10 . ( 222222222222222 ) 3 = ( 1101 1010 1111 0010 0110 1010 ) 2 = ( 14348906 ) 10 .
N = 4 r n - 3 ,
P i P i - 1 - Q i Q i - 1 = P i P i - 1 + Q i ¯ Q i - 1 ¯ .

Metrics