Abstract

Symbolic substitution logic is based on optical pattern transformations. This space-invariant mechanism is shown to be capable of supporting space-variant operations. An optical implementation is proposed. It is based on splitting an image, shifting the split images, superimposing the results, regenerating the superimposed image with an optical logic array, splitting the regenerated image, shifting the resulting images, and superimposing the shifted images. Experimental results are presented. Examples demonstrate how symbolic substitution logic can be used to implement Boolean logic, binary arithmetic, cellular logic, and Turing machines.

© 1986 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference, (1983), pp. 13–17.
  2. J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).
  3. D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).
  4. J. von Neumann, The Computer and the Brain (Yale U.P., New Haven, 1958).
  5. J. Tanida, Y. Ichioka, “Optical Parallel Array Logic System,” in Optics in Modern Science and Technology, ICO—13 Conference Digest, Sapporo, 1984, p. 294.
  6. M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master’s Thesis, Rutgers U., New Brunswick, NJ (1984).
  7. K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).
  8. S. Wolfram, “Universality and Complexity in Cellular Automata,” in Cellular Automata, Proceedings, Interdisciplinary Workshop, Los Alamos, NM, 7–11 Mar. 1983, D. Farmer, T. Toffoli, S. Wolfram, Eds. (North-Holland, Amsterdam, 1984), p. 1.
  9. M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, NJ, 1967).

1985

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

1984

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

1983

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference, (1983), pp. 13–17.

1979

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Burrus, C.

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Chemla, D. S.

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Damen, A. C.

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Duff, M. J. B.

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Gibbs, H. M.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

Gossard, A. C.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Huang, A.

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference, (1983), pp. 13–17.

Ichioka, Y.

J. Tanida, Y. Ichioka, “Optical Parallel Array Logic System,” in Optics in Modern Science and Technology, ICO—13 Conference Digest, Sapporo, 1984, p. 294.

Jewell, J. L.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

Lee, Y. H.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

Levialdi, S.

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Miller, D. A. B.

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Minsky, M.

M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, NJ, 1967).

Murdocca, M. J.

M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master’s Thesis, Rutgers U., New Brunswick, NJ (1984).

Norgren, P. E.

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Peyghambarian, N.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

Preston, K.

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Tanida, J.

J. Tanida, Y. Ichioka, “Optical Parallel Array Logic System,” in Optics in Modern Science and Technology, ICO—13 Conference Digest, Sapporo, 1984, p. 294.

Toriwaki, J.

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

von Neumann, J.

J. von Neumann, The Computer and the Brain (Yale U.P., New Haven, 1958).

Warren, M.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

Wiegmann, W.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Wolfram, S.

S. Wolfram, “Universality and Complexity in Cellular Automata,” in Cellular Automata, Proceedings, Interdisciplinary Workshop, Los Alamos, NM, 7–11 Mar. 1983, D. Farmer, T. Toffoli, S. Wolfram, Eds. (North-Holland, Amsterdam, 1984), p. 1.

Wood, T.

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Appl. Phys. Lett.

J. L. Jewell, Y. H. Lee, M. Warren, H. M. Gibbs, N. Peyghambarian, A. C. Gossard, W. Wiegmann, “3-pJ, 82 MHz Optical Logic Gates in a Room Temperature GaAs-AlGaAs Multiple-Quantum-Well Etalon,” Appl. Phys. Lett. 46, 918 (1985).

D. A. B. Miller, D. S. Chemla, A. C. Damen, A. C. Gossard, W. Wiegmann, T. Wood, C. Burrus, Appl. Phys. Lett. 45, 13 (1984).

Proc. IEEE

K. Preston, M. J. B. Duff, S. Levialdi, P. E. Norgren, J. Toriwaki, “Basics of Cellular Logic with some Applications in Medical Image Processing,” Proc. IEEE 67, 826 (1979).

Technical Digest, IEEE Tenth International Optical Computing Conference

A. Huang, “Parallel Algorithms for Optical Digital Computers,” in Technical Digest, IEEE Tenth International Optical Computing Conference, (1983), pp. 13–17.

Other

S. Wolfram, “Universality and Complexity in Cellular Automata,” in Cellular Automata, Proceedings, Interdisciplinary Workshop, Los Alamos, NM, 7–11 Mar. 1983, D. Farmer, T. Toffoli, S. Wolfram, Eds. (North-Holland, Amsterdam, 1984), p. 1.

M. Minsky, Computation: Finite and Infinite Machines (Prentice-Hall, Englewood Cliffs, NJ, 1967).

J. von Neumann, The Computer and the Brain (Yale U.P., New Haven, 1958).

J. Tanida, Y. Ichioka, “Optical Parallel Array Logic System,” in Optics in Modern Science and Technology, ICO—13 Conference Digest, Sapporo, 1984, p. 294.

M. J. Murdocca, “Techniques for Parallel Numeric and Non-Numeric Algorithm Design in Digital Optics,” Master’s Thesis, Rutgers U., New Brunswick, NJ (1984).

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

Fig. 1
Fig. 1

Comparison of Boolean logic with symbolic substitution.

Fig. 2
Fig. 2

Recognition of the search pattern. The output is a superposition of two shifted copies of the input pattern. The shift is determined so that for a search pattern the dark spots superpose on the lower left cell.

Fig. 3
Fig. 3

Inversion and masking. The nor gate transforms dark spots into bright spots, and the mask selects only those that are in the lower left cell. The two search patterns contained in the input pattern are recognized at the correct locations.

Fig. 4
Fig. 4

Substitution of the scribing pattern. The output is a superposition of two shifted copies of the input pattern. The shift is selected to scribe the new pattern.

Fig. 5
Fig. 5

Architecture for an optical symbolic substitution processor. The pattern splitter provides four copies of the input plane. Every pattern recognizer–pattern substituter pair is implementing a different rule. The pattern combiner recombines the partial outputs of the pattern substituters in the output plane.

Fig. 6
Fig. 6

Optical superposition of shifted images in a Michelson interferometer. The output plane is an image of the input plane. The tilt of the mirrors determines the shifts.

Fig. 7
Fig. 7

Optical superposition of shifted images in a Sagnac interferometer. The output plane is an image of the input plane. The tilt of the mirrors determines the shifts.

Fig. 8
Fig. 8

Optical superposition of shifted images without tilting the image plane. The shift is determined by the position of the movable lens–mirror combination.

Fig. 9
Fig. 9

Input pattern and result of the recognizer. The search pattern is the same as in Fig. 2.

Fig. 10
Fig. 10

Exclusive-or operation expressed by substitution rules. The logic values 0 and 1 are coded in dual rail as shown above.

Fig. 11
Fig. 11

Rules for binary addition.

Fig. 12
Fig. 12

Rules for a Turing machine. Rules 3..6 are modeled to be the state machine of a counter. The other rules maintain the tape information and activity bits.

Fig. 13
Fig. 13

Initial condition for the Turing machine. The top row is alignment markers. The next two rows are the tape in dual rail coding. All positions are zero. The following three rows contain the state information of the head. It is inactive on most locations and zero at the location of the head.

Equations (5)

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

Δ [ f k m , d ( r + s k m ) ]
Λ k = 1 M ( a k ) = a 1 Λ a 2 Λ a M .
Δ ( a , b ) = { 1 if a = b , 0 else ,
d ( r ) = Λ k = 1 M Δ [ f k m , d ( r + s k m ) ] .
d ( r ) = Ω k = 1 N Λ [ f k n , d ( r - s k n ) ] .

Metrics