Abstract

We propose and demonstrate a modified-signed-digit (MSP) arithmetic to achieve multi-input digital optical computing. Our approach utilizes hybrid addition–subtraction transformation (or weight operation) rules among multiple inputs. This results in operation speeds that exceed those of two-input MSD arithmetic for multi-input computing. Optical implementation of the proposed multi-input MSD arithmetic by utilizing spatial data encoding and an optical fan-out element is also presented and experimentally demonstrated.

© 1994 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Avizienis, “ Signed-digit number representations for fast parallel arithmetic,” IRE Trans. Electron. Comp. EC-10, 389–400 (1961).
    [CrossRef]
  2. N. Takagi, H. Yasuura, S. Yajima, “High-speed VLSI multiplication algorithm with a redundant binary addition tree,” IEEE Trans. Comput. C-34, 789–796 (1985).
    [CrossRef]
  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–43 (1986).
  4. M. M. Mirsalehi, T. K. Gaylord, “Operation minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
    [CrossRef] [PubMed]
  5. 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]
  6. S. Barua, “Single-stage optical adder/subtractor,” Opt. Eng. 30, 265 (1991).
    [CrossRef]
  7. A. K. Cherri, M. A. Karim, “Modified signed-digit arithmetic using an effective symbolic substitution,” Appl. Opt. 27, 3824–3827 (1988).
    [CrossRef] [PubMed]
  8. Y. Li, H. Kim, A. Kostrzewski, G. Eichmann, “Content-addressable-memory-based single-stage optical modified signed-digit arithmetic,” Opt. Lett. 14, 1254–1256 (1989).
    [CrossRef] [PubMed]
  9. A. A. S. Awwal, M. A. Karim, “Polarization-encoded optical shadow-casting: direct implementation of a carry-free adder,” Appl. Opt. 28, 785–790 (1989).
    [CrossRef] [PubMed]
  10. R. P. Blocker, 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]
  11. P. A. Ramanoothy, S. Anthony, “Optical modified signed digit adder using polarization-coded symbolic substitution,” Opt. Eng. 26, 821–825 (1987).
  12. K. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).
  13. S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified-signed-digit optical computing by using optical fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
    [CrossRef] [PubMed]
  14. S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.
  15. R. A. Athale, J. N. Lee, “Optical processing using outer-product concepts,” Proc. IEEE 72, 931–941 (1984).
    [CrossRef]
  16. S. Zhou, X. Yang, M. Wu, C. Chin, “Triple-in double-out optical parallel logic processing system,” Opt. Lett. 12, 968–970(1987).
    [CrossRef] [PubMed]

1992 (1)

1991 (1)

S. Barua, “Single-stage optical adder/subtractor,” Opt. Eng. 30, 265 (1991).
[CrossRef]

1989 (3)

1988 (1)

1987 (3)

1986 (3)

1985 (1)

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

1984 (1)

R. A. Athale, J. N. Lee, “Optical processing using outer-product concepts,” Proc. IEEE 72, 931–941 (1984).
[CrossRef]

1961 (1)

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

Anthony, S.

P. A. Ramanoothy, S. Anthony, “Optical modified signed digit adder using polarization-coded symbolic substitution,” Opt. Eng. 26, 821–825 (1987).

Athale, R. A.

R. A. Athale, J. N. Lee, “Optical processing using outer-product concepts,” Proc. IEEE 72, 931–941 (1984).
[CrossRef]

Avizienis, A.

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

Awwal, A. A. S.

Barua, S.

S. Barua, “Single-stage optical adder/subtractor,” Opt. Eng. 30, 265 (1991).
[CrossRef]

Blocker, R. P.

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–43 (1986).

Campbell, S.

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified-signed-digit optical computing by using optical fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
[CrossRef] [PubMed]

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.

Cherri, A. K.

Chin, C.

Drake, B. L.

R. P. Blocker, 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]

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–43 (1986).

Eichmann, G.

Gaylord, T. K.

Henderson, T. B.

Hwang, K.

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

Karim, M. A.

Kim, H.

Kostrzewski, A.

Lasher, M. E.

R. P. Blocker, 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]

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–43 (1986).

Lee, J. N.

R. A. Athale, J. N. Lee, “Optical processing using outer-product concepts,” Proc. IEEE 72, 931–941 (1984).
[CrossRef]

Li, Y.

Liu, H. K.

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified-signed-digit optical computing by using optical fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
[CrossRef] [PubMed]

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.

Louri, A.

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

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–43 (1986).

Mirsalehi, M. M.

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–43 (1986).

Ramanoothy, P. A.

P. A. Ramanoothy, S. Anthony, “Optical modified signed digit adder using polarization-coded symbolic substitution,” Opt. Eng. 26, 821–825 (1987).

Takagi, N.

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

Wu, M.

Yajima, S.

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

Yang, X.

Yasuura, H.

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

Yeh, P.

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified-signed-digit optical computing by using optical fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
[CrossRef] [PubMed]

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.

Zhou, S.

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Modified-signed-digit optical computing by using optical fan-out elements,” Opt. Lett. 17, 1697–1699 (1992).
[CrossRef] [PubMed]

S. Zhou, X. Yang, M. Wu, C. Chin, “Triple-in double-out optical parallel logic processing system,” Opt. Lett. 12, 968–970(1987).
[CrossRef] [PubMed]

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.

Appl. Opt. (5)

IEEE Trans. Comput. (1)

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

IRE Trans. Electron. Comp. (1)

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

Opt. Eng. (4)

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–43 (1986).

S. Barua, “Single-stage optical adder/subtractor,” Opt. Eng. 30, 265 (1991).
[CrossRef]

P. A. Ramanoothy, S. Anthony, “Optical modified signed digit adder using polarization-coded symbolic substitution,” Opt. Eng. 26, 821–825 (1987).

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

Opt. Lett. (3)

Proc. IEEE (1)

R. A. Athale, J. N. Lee, “Optical processing using outer-product concepts,” Proc. IEEE 72, 931–941 (1984).
[CrossRef]

Other (1)

S. Zhou, S. Campbell, P. Yeh, H. K. Liu, “Optical implementations of the modified signed-digit algorithm,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp.313–316.

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

Fig. 1
Fig. 1

Operation truth table of basic three-stage MSD arithmetic.

Fig. 2
Fig. 2

Operation truth table for the first stage of the three-input MSD hybrid addition–subtraction operation. The operation truth tables in the last two stages are exactly the same as those in the basic MSD arithmetic.

Fig. 3
Fig. 3

Operation tree of the proposed multi-input MSD hybrid addition–subtraction for obtaining the ith output digit: (a) for three inputs, (b) for four inputs.

Fig. 4
Fig. 4

Operation truth table of a four-input MSD hybrid addition–subtraction operation in the first stage. The operation truth tables in the second stage and the third stage are then exactly the same as the case of + + in the first stage of three-input MSD arithmetic and the last stage of the basic three-stage MSD arithmetic, respectively.

Fig. 5
Fig. 5

Data encoding schemes of multi-input MSD hybrid addition–subtraction operations: (a) three inputs, (b) four inputs.

Fig. 6
Fig. 6

Operation kernels in the first stage for performing the operation formation D = A + BC, which is the same as example 1 in Section 3.

Fig. 7
Fig. 7

Experimental setup that is utilized to demonstrate three-input MSD arithmetic: L1–L4, lenses; BS1–BS4, beam splitters; M1–M3, mirrors; OFE, 7 × 7 Dammann grating; A and B, two inputs; K1, K0, K 1 ¯ , three operation kernels; D1, D0 D 1 ¯ , three image-plane decoding masks; f, focal length of L1; d 0, d i , conjugate distances of lens L1; q, distance between OFE and L1.

Fig. 8
Fig. 8

Experimental results for the addition of three inputs. (a) Encoded patterns of (top) A, (middle) B, (bottom) C; (b) overlapping pattern ABC; (c) theoretical results of (top) T1, (bottom) W1; (d) coded patterns for the shifted (top) T1, (bottom) W1; (e) overlapping patterned of the shifted T1 and W1; (f) theoretical results of (top) T2, (bottom) W2; (g) coded patterns for the shifted (top) T2, (bottom) W2; (h) overlapping pattern of the shifted T2 and W2; (i) theoretical result of T3; (j) experimental results of T1, W1, T2, W2, and T3. The spatial data encoding in stage 1 is taken in the format of Fig. 5, and that of the last two stages and the output of the first stage are taken in the triple-rail coding, in which the T’s are encoded in the vertical direction and the W’s are encoded in the horizontal direction.

Equations (18)

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

D d = i c i 2 i ,
A = w d = 3 m ( m - 1 ) 2 ( m - 1 ) .
D = A + B - C = 12.25 + 10.75 - 4.50 = 18.50.
A = 1 1 0 0.1 1 ¯ , B = 1 1 1 ¯ 0.1 1 , C = 0 1 1 1 ¯ . 1 ¯ 0.
T 1 = 1 1 1 ¯ 1.1 0 1 1 1 ¯ 1.1 0 0 , W 1 = 0 1 ¯ 0 1 ¯ .1 0 0 0 1 ¯ 0 1 ¯ .1 0.
T 2 = 0 0 1 ¯ 0 0.0 0 0 0 1 ¯ 0 0.0 0 0 , W 2 = 1 1 0 1 0.1 0 0 1 1 0 1 0.1 0.
D = T 3 = 0     1     0     0     1     0.1     0.
E = A + B - C + D = 12.25 + 10.75 - 4.5 + 9.25 = 27.75.
A = 1 1 0 0.1 1 ¯ , B = 1 1 1 ¯ 0.1 1 , C = 0 1 1 1 ¯ . 1 ¯ 0 , D = 1 0 0 1.0 1 ,
T 11 = 1 1 1 ¯ 1.1 1 1 1 1 ¯ 1.1 1 0 , T 12 = 1 0 0 0.1 0 1 0 0 0.1 0 0 , W 1 = 1 ¯ 1 ¯ 0 0. 1 ¯ 1 ¯ 0 1 ¯ 1 ¯ 0 0. 1 ¯ 1 ¯ .
T 2 = 1 0 1 ¯ 1 1.0 1 ¯ 1 0 1 ¯ 1 1.0 1 ¯ 0 , W 2 = 0 0 0 1 ¯ 0.0 1 0 0 0 0 1 ¯ 0.0 1.
E = T 3 = 0     1     0     1 ¯     1     0     0. 1 ¯     1.
D V = { 0.5 N = q = 3 , g { log 3 N } g { log 2 N } N > 3 , q = 3 [ 1 + g { log 2 ( q - 1 ) } ] ( g { log q N } ) 3 ( g { log 2 N } ) N , q > 3 ,
C ^ = A ^ · B ^ = [ 11 5 - 14 2 ] · [ - 4 - 8 12 10 ] = [ - 44 - 88 56 112 ] + [ 60 50 24 20 ] = [ 16 - 38 80 132 ] .
A ^ = [ 1011 0101 1 ¯ 1 ¯ 1 ¯ 0 0010 ] ,             B ^ = [ 0 1 ¯ 00 1 ¯ 000 1100 1010 ] .
C ^ 1 = [ 1 0 1 1 - - 1 ¯ 1 ¯ 1 ¯ 0 ] ·     [ 0 1 ¯ 0 0 1 ¯ 0 0 0 ] = [ 0 1 ¯ 0 0 1 ¯ 0 0 0 0 0 0 0 0 0 0 0 0 1 ¯ 0 0 1 ¯ 0 0 0 0 1 ¯ 0 0 1 ¯ 0 0 0 - - - - - - - - - 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 0 0 0 0 ] .
C ^ 2 = [ 0 1 0 1 - - 0 0 1 0 ] ·     [ 1 1 0 0 1 0 1 0 ] =     [ 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 - - - - - - - - - 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 0 1 0 0 0 0 0 0 0 0 0 ] , C ^ = C ^ 1 + C ^ 2 = [ 0 1 ¯ 1 0 0 1 ¯ 1 0 0 0 1 0 1 ¯ 0 0 1 1 ¯ 1 1 ¯ 0 0 1 ¯ 1 0 0 1 ¯ 1 0 0 0 1 1 ¯ 0 0 0 0 0 1 1 ¯ 0 - - - - - - - - - - 0 1 1 ¯ 0 0 1 1 ¯ 0 0 0 0 1 1 ¯ 0 0 1 1 ¯ 0 0 0 1 0 0 0 0 1 0 1 1 ¯ 0 0 0 0 0 0 0 0 0 0 ] = [ 0 1 1 ¯ 0 0 0 1 0 0 0 0 1 ¯ 1 0 1 ¯ 1 1 ¯ 0 1 1 ¯ 1 ¯ 1 1 ¯ 0 0 0 0 0 1 0 0 0 1 1 ¯ 0 0 ] = [ 16 - 38 80 132 ] .
D M { 0.67 n ( or N ) = 2 , N ( or n ) = q = 3 , 0.5 n = N = q = 3 , g { log 3 n } + g { log 3 N } g { log 2 n } + g { log 2 N } n ( or N ) > 3 , N ( or n ) = q = 3 , [ 1 + g { log 2 ( q - 1 ) } ] ( g { log q n } + g { log q N } ) 3 ( g { log 2 n } + g { log 2 N } ) n , N , q > 3 ,

Metrics