Abstract

Image logic algebra (ILA) is a comprehensive language for single-instruction stream multidata stream-type parallel processing, particularly for processing that is based on pattern matching. To demonstrate the usefulness of ILA for application to the computer-aided design of very-large-scale-integrated circuits, we describe a mostly parallel wire-routing algorithm based on Lee’s maze algorithm by using ILA; our computer simulation verifies its validity. Another application to numerical data processing algorithms (including addition and multiplication) that is based on Booth’s algorithm is also described by using ILA. Furthermore, the computational complexity of the proposed algorithms is evaluated.

© 1992 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. J. Tanida, Y. Ichioka, “OPALS: optical parallel array logic system,” Appl. Opt. 25, 1565–1570 (1986).
    [CrossRef] [PubMed]
  2. K.-S. Huang, B. K. Jenkins, A. A. Sawchuk, “Image algebra representation of parallel optical binary arithmetic,” Appl. Opt. 28, 1263–1278 (1989).
    [CrossRef] [PubMed]
  3. K.-H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
    [CrossRef] [PubMed]
  4. G. Eichmann, J. Zhu, Y. Li, “Optical parallel image skeletonization using content-addressable memory-based symbolic substitution,” Appl. Opt. 27, 2905–2911 (1988).
    [CrossRef] [PubMed]
  5. S. D. Goodman, W. T. Rhodes, “Symbolic substitution applications to image processing,” Appl. Opt. 27, 1708–1714 (1988).
    [CrossRef] [PubMed]
  6. J. Tanida, Y. Ichioka, “Programming of optical array logic. 1: Image data processing,” Appl. Opt. 27, 2926–2930 (1988).
    [CrossRef] [PubMed]
  7. J. Tanida, M. Fukui, Y. Ichioka, “Programming of optical array logic. 2: numerical data processing based on pattern logic,” Appl. Opt. 27, 2931–2939 (1988).
    [CrossRef] [PubMed]
  8. J. Tanida, J. Nakagawa, E. Yagyu, M. Fukui, Y. Ichioka, “Experimental verification of parallel processing on a hybrid optical parallel array logic system,” Appl. Opt. 29, 2510–2521 (1990).
    [CrossRef] [PubMed]
  9. M. Fukui, J. Tanida, Y. Ichioka, “Flexible-structured computation based on optical array logic,” Appl. Opt. 29, 1604–1609 (1990).
    [CrossRef] [PubMed]
  10. H.-I. Jeon, M. A. G. Abushagur, A. A. Sawchuk, B. K. Jenkins, “Digital optical processor based on symbolic substitution using holographic matched filtering,” Appl. Opt. 29, 2113–2125 (1990).
    [CrossRef] [PubMed]
  11. M. Fukui, K. Kitayama, “Image logic algebra (ILA) and its optical implementations,” Appl. Opt. 31, 581–591 (1992).
    [CrossRef] [PubMed]
  12. C. Lee, “An algorithm for path connections and its applications.” IRE Trans. Electron. Comput. EC-10, 346–365 (1961).
    [CrossRef]
  13. A. D. Booth, “A signed binary multiplication technique,” Q. J. Mech. Appl. Math. 4, 236 (1951).
    [CrossRef]
  14. R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
    [CrossRef]
  15. T. Yatagai, “Optical cellular logic computers and space-variant logic gate array,” in Optical and Hybrid Computing, H. H. Szu, ed., Proc. Soc. Photo-Opt. Instrum. Eng.634, 157–164 (1986).
    [CrossRef]
  16. J. Tanida, Y. Ichioka, “Optical-logic-array processor using shadowgrams. III. Parallel neighborhood operatons and an architecture of an optical digital-computing system,” J. Opt. Soc. Am. A 2, 1245–1253 (1985).
    [CrossRef]
  17. K.-S. Huang, A Digital Optical Cellular Image Processor (World Scientific, Singapore, 1990), Chap. 8, pp. 163–181.
  18. E. Swartzlander, “Digital optical arithmetic,” Appl. Opt. 25, 3021–3032 (1986).
    [CrossRef] [PubMed]
  19. J. Tanida, J. Nakagawa, Y. Ichioka, “Birefringent encoding and multichannel reflective correlator for optical array logic,” Appl. Opt. 27, 3819–3823 (1988).
    [CrossRef] [PubMed]
  20. M. Hashimoto, K. Kitayama, N. Mukohzaka, “Programmable optical parallel processor based upon polarization modulation: cascade operations,” Appl. Opt. 28, 4305–4312 (1989).
    [CrossRef] [PubMed]

1992

1990

1989

1988

1987

R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
[CrossRef]

1986

1985

1961

C. Lee, “An algorithm for path connections and its applications.” IRE Trans. Electron. Comput. EC-10, 346–365 (1961).
[CrossRef]

1951

A. D. Booth, “A signed binary multiplication technique,” Q. J. Mech. Appl. Math. 4, 236 (1951).
[CrossRef]

Abushagur, M. A. G.

Booth, A. D.

A. D. Booth, “A signed binary multiplication technique,” Q. J. Mech. Appl. Math. 4, 236 (1951).
[CrossRef]

Brenner, K.-H.

Eichmann, G.

Fukui, M.

Goodman, S. D.

Haralick, R. M.

R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
[CrossRef]

Hashimoto, M.

Huang, A.

Huang, K.-S.

K.-S. Huang, B. K. Jenkins, A. A. Sawchuk, “Image algebra representation of parallel optical binary arithmetic,” Appl. Opt. 28, 1263–1278 (1989).
[CrossRef] [PubMed]

K.-S. Huang, A Digital Optical Cellular Image Processor (World Scientific, Singapore, 1990), Chap. 8, pp. 163–181.

Ichioka, Y.

Jenkins, B. K.

Jeon, H.-I.

Kitayama, K.

Lee, C.

C. Lee, “An algorithm for path connections and its applications.” IRE Trans. Electron. Comput. EC-10, 346–365 (1961).
[CrossRef]

Li, Y.

Mukohzaka, N.

Nakagawa, J.

Rhodes, W. T.

Sawchuk, A. A.

Sternberg, S. R.

R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
[CrossRef]

Streibl, N.

Swartzlander, E.

Tanida, J.

Yagyu, E.

Yatagai, T.

T. Yatagai, “Optical cellular logic computers and space-variant logic gate array,” in Optical and Hybrid Computing, H. H. Szu, ed., Proc. Soc. Photo-Opt. Instrum. Eng.634, 157–164 (1986).
[CrossRef]

Zhu, J.

Zhuang, X.

R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
[CrossRef]

Appl. Opt.

J. Tanida, Y. Ichioka, “OPALS: optical parallel array logic system,” Appl. Opt. 25, 1565–1570 (1986).
[CrossRef] [PubMed]

E. Swartzlander, “Digital optical arithmetic,” Appl. Opt. 25, 3021–3032 (1986).
[CrossRef] [PubMed]

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

S. D. Goodman, W. T. Rhodes, “Symbolic substitution applications to image processing,” Appl. Opt. 27, 1708–1714 (1988).
[CrossRef] [PubMed]

G. Eichmann, J. Zhu, Y. Li, “Optical parallel image skeletonization using content-addressable memory-based symbolic substitution,” Appl. Opt. 27, 2905–2911 (1988).
[CrossRef] [PubMed]

J. Tanida, Y. Ichioka, “Programming of optical array logic. 1: Image data processing,” Appl. Opt. 27, 2926–2930 (1988).
[CrossRef] [PubMed]

J. Tanida, M. Fukui, Y. Ichioka, “Programming of optical array logic. 2: numerical data processing based on pattern logic,” Appl. Opt. 27, 2931–2939 (1988).
[CrossRef] [PubMed]

J. Tanida, J. Nakagawa, Y. Ichioka, “Birefringent encoding and multichannel reflective correlator for optical array logic,” Appl. Opt. 27, 3819–3823 (1988).
[CrossRef] [PubMed]

K.-S. Huang, B. K. Jenkins, A. A. Sawchuk, “Image algebra representation of parallel optical binary arithmetic,” Appl. Opt. 28, 1263–1278 (1989).
[CrossRef] [PubMed]

M. Hashimoto, K. Kitayama, N. Mukohzaka, “Programmable optical parallel processor based upon polarization modulation: cascade operations,” Appl. Opt. 28, 4305–4312 (1989).
[CrossRef] [PubMed]

M. Fukui, J. Tanida, Y. Ichioka, “Flexible-structured computation based on optical array logic,” Appl. Opt. 29, 1604–1609 (1990).
[CrossRef] [PubMed]

H.-I. Jeon, M. A. G. Abushagur, A. A. Sawchuk, B. K. Jenkins, “Digital optical processor based on symbolic substitution using holographic matched filtering,” Appl. Opt. 29, 2113–2125 (1990).
[CrossRef] [PubMed]

J. Tanida, J. Nakagawa, E. Yagyu, M. Fukui, Y. Ichioka, “Experimental verification of parallel processing on a hybrid optical parallel array logic system,” Appl. Opt. 29, 2510–2521 (1990).
[CrossRef] [PubMed]

M. Fukui, K. Kitayama, “Image logic algebra (ILA) and its optical implementations,” Appl. Opt. 31, 581–591 (1992).
[CrossRef] [PubMed]

IEEE Trans. Pattern Anal. Machine Intell.

R. M. Haralick, S. R. Sternberg, X. Zhuang, “Image analysis using mathematical morphology,” IEEE Trans. Pattern Anal. Machine Intell. PAMI-9, 532–550 (1987).
[CrossRef]

IRE Trans. Electron. Comput.

C. Lee, “An algorithm for path connections and its applications.” IRE Trans. Electron. Comput. EC-10, 346–365 (1961).
[CrossRef]

J. Opt. Soc. Am. A

Q. J. Mech. Appl. Math.

A. D. Booth, “A signed binary multiplication technique,” Q. J. Mech. Appl. Math. 4, 236 (1951).
[CrossRef]

Other

T. Yatagai, “Optical cellular logic computers and space-variant logic gate array,” in Optical and Hybrid Computing, H. H. Szu, ed., Proc. Soc. Photo-Opt. Instrum. Eng.634, 157–164 (1986).
[CrossRef]

K.-S. Huang, A Digital Optical Cellular Image Processor (World Scientific, Singapore, 1990), Chap. 8, pp. 163–181.

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

Fig. 1
Fig. 1

Example of the extended erosion. B[12; 12] is the result of the extended erosion of image A[12; 12].

Fig. 2
Fig. 2

Example of the dilation. B[12; 12] is the result of the dilatation of image A[12; 12].

Fig. 3
Fig. 3

Wire-routing problem.

Fig. 4
Fig. 4

Lee’s maze-routing algorithm.

Fig. 5
Fig. 5

Modified Lee’s maze-routing algorithm for (a) wave-front expansion phase and (b) trace-back phase.

Fig. 6
Fig. 6

Initial data for modified Lee’s algorithm.

Fig. 7
Fig. 7

Simulation-result images of the proposed routing algorithm.

Fig. 8
Fig. 8

Example of a coding rule for two binary images.

Fig. 9
Fig. 9

Example of a coding rule for three binary images.

Fig. 10
Fig. 10

Procedure of the space-variant logic gate array.

Fig. 11
Fig. 11

Procedure of the optical array logic in the specific case that is one operation kernel.

Fig. 12
Fig. 12

Binary row-coded numbers.

Fig. 13
Fig. 13

Binary stack-coded numbers.

Fig. 14
Fig. 14

Processing flow chart of an addition algorithm based on the space-variant logic gate array.

Fig. 15
Fig. 15

Processing flow chart of an addition algorithm based on the optical array logic.

Fig. 16
Fig. 16

Processing flow chart of a multiplication algorithm.

Tables (3)

Tables Icon

Table 1 Operations and Transformations of ILA

Tables Icon

Table 2 The Definition of ‖rm‖(k,l)

Tables Icon

Table 3 Number of Operations in Newly Derived Algorithms

Equations (43)

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

B [ M ; N ] i j = { A [ M ; N ] i + k , j + l l i + k M 0 l i + k N otherwise
B [ R ; S ] m n = { A [ M ; N ] i j m = k i , n = l j , 0 otherwise ,
B [ R ; S ] i j = A [ M ; N ] k i , l j ,
B [ R ; S ] i + m M , j + n N = A [ M ; N ] i j m = 1 , 2 , k , n = 1 , 2 , l .
B [ 1 ; 1 ] 1 , 1 = i = 1 M j = 1 N A [ M ; N ] i j ¯ .
B [ M ; N ] i j = m k , l [ x k l m ( 1 ) A [ M ; N ] i + k , j + l + x k l m ( 0 ) A [ M ; N ] i + k , j + l ¯ ] .
B [ M ; N ] = m k , l ( A [ M ; N ] r m ( k , l ) ) .
A [ M ; N ] [ r ( k , l ) r ( p , q ) ] A [ M ; N ] r ( k , l ) + A [ M ; N ] r l ( p , q ) .
A [ M ; N ] [ r ( k , l ) r ( p , q ) ] ( A [ M ; N ] r ( k , l ) ) · ( A [ M ; N ] r ( p , q ) ) .
A [ M ; N ] r ( k , l ) ¯ A [ M ; N ] r ( k , l ) ¯ .
B [ M ; N ] = A [ M ; N ] [ m k , l r m ( k , l ) ] ,
i = 1 n a i = a 1 a 2 a n ,
i = 1 n a i = a 1 a 2 a n .
S = m k , l r m ( k , l ) ,
B [ M ; N ] = A [ M ; N ] S .
P = k , l r ( k , l )
P = r m - 1 , n + 1 r m , n + 1 r m + 1. n + 1 r m - 1 , n r m , n _ r m + 1 , n r m - 1 , n - 1 r m , n - 1 r m + 1 , n - 1 ( m , n ) ,
B [ 12 ; 12 ] = A [ 12 ; 12 ] { [ 0 ( 0 , 0 ) 1 ( - 1 , 0 ) 1 ( 0 , 1 ) ] [ 0 ( 0 , 0 ) 1 ( 0 , 1 ) 1 ( 0 , - 1 ) ] [ 0 ( 0 , 0 ) 1 ( 0 , - 1 ) 1 ( - 1 , - 1 ) ] } = A [ 12 ; 12 ] ( 1 0 _ * 1 ) ( 1 0 _ 1 ) ( 1 1 * 0 _ ) .
A [ M ; N ] k , l r ( k , l ) ] ) A [ M ; N ] [ k , l r ( - k , - l ) ] ¯ .
B [ M ; N ] = A [ M ; N ] Q ,
Q = k , l r ( k , l )
B [ 12 ; 12 ] = A [ 12 ; 12 ] 1 1 1 * _ 1 1 .
D 1 [ M ; N ] = B [ M ; N ] , s = 1 , t = 2.
if s = 3 then t = 1 else t = s + 1 D t [ M ; N ] = A [ M ; N ] ¯ · D s [ M ; N ] * 0 * 0 * _ 0 * 0 * s = t
E [ M ; N ] = C [ M ; N ] F [ M ; N ] = 0 [ M ; N ]
if t = 1 then t = 3 else t = t - 1 E [ M ; N ] = D t [ M ; N ] · E [ M ; N ] * 0 * 0 * _ 0 * 0 * F [ M ; N ] = F [ M ; N ] + E [ M ; N ]
A [ 2 M ; 2 N ] = I C ( A [ M ; N ] ) B [ 2 M ; 2 N ] = I C ( B [ M ; N ] ) A [ 2 M ; 2 N ] = A [ 2 M ; 2 N ] * _ 1 * 1 + A [ 2 M ; 2 N ] ¯ 1 _ 1 B [ 2 M ; 2 N ] = B [ 2 M ; 2 N ] * _ * 1 1 + B [ 2 M ; 2 N ] ¯ 1 _ 1 E [ 2 M ; 2 N ] = A [ 2 M ; 2 N ] · B [ 2 M ; 2 N ]
E [ 2 M ; 2 N ] = encode ( A [ M ; N ] , B [ M ; N ] ) .
A [ 2 M ; 2 N ] = IC ( A [ M ; N ] ) B [ 2 M ; 2 N ] = IC ( B [ M ; N ] ) C [ 2 M ; 2 N ] = IC ( C [ M ; N ] ) A [ 4 M ; 2 N ] = A [ 4 M ; 2 N ] * _ 1 * 1 * 1 * 1 + A [ 4 M ; 2 N ] ¯ 1 _ * 1 1 * 1 B [ 4 M ; 2 N ] = B [ 4 M ; 2 N ] * _ * 1 1 * * 1 1 + B [ 4 M ; 2 N ] ¯ 1 _ 1 1 1 C [ 4 M ; 2 N ] = C [ 4 M ; 2 N ] * _ * * * 1 1 1 1 + C [ 4 M ; 2 N ] ¯ 1 _ 1 1 1 E [ 2 M ; 2 N ] = A [ 2 M ; 2 N ] · B [ 2 M ; 2 N ] · C [ 2 M ; 2 N ]
E [ 2 M ; 2 N ] = encode ( A [ M ; N ] , B [ M , N ] , C [ M ; N ] ) .
C [ M ; N ] = IC [ E [ 2 M ; 2 N ] ( 1 + * _ 1 + * _ 1 + * _ * * 1 ) ] .
A [ M ; N ] P = A [ M ; N ] P ¯ ¯ .
C [ M ; N ] = IC ( E [ 2 M ; 2 N ] 0 _ 0 0 0 ) ¯ .
E [ 2 M ; 2 N ] = encode ( A [ M ; N ] , B [ M ; N ] ) E [ 2 M ; 2 N ] = e [ 2 M ; 2 N ] · MSK [ 2 M ; 2 N ] C [ M ; N ] = IC ( E [ 2 M ; 2 N ] 0 _ 0 0 0 ) ¯
E [ 2 M ; 2 N ] = encode ( A [ M ; N ] , B [ M ; N ] ) C [ M ; N ] = IC ( E [ 2 M ; 2 N ] 0 _ * * 0 ) ¯
S [ 4 N ; 2 N ] = MI ( 0 1 1 0 1 0 0 1 )             g e n e r a t i o n o f m a s k i m a g e f o r s u m , C [ 4 N ; 2 N ] = MI ( 0 0 0 1 0 1 1 1 )             g e n e r a t i o n o f m a s k i m a g e f o r c a r r y ,
E i [ 4 N ; 2 N ] = encode ( A i [ N ; N ] , B i [ N ; N ] , C i [ N ; N ] ) S i [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] · S [ 4 N ; 2 N ]             m a s k i n g o p e r a t i o n f o r s u m C i + 1 [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] · C [ 4 N ; 2 N ]             m a s k i n g o p e r a t i o n f o r c a r r y
S i [ 4 N ; 2 N ] = S i [ 4 N ; 2 N ] 0 _ 0 0 0 0 0 0 0 ¯ C i + 1 [ 4 N ; 2 N ] = C i + 1 [ 4 N ; 2 N ] 0 _ 0 0 0 0 0 0 0 ¯ S i [ N ; N ] = IC ( S i [ 4 N ; 2 N ] ) C i + 1 [ N ; N ] = IC ( C i + 1 [ 4 N ; 2 N ] )
E i [ 4 N ; 2 N ] = encode ( A i [ N ; N ] , B i [ N ; N ] , C i [ N ; N ] ) S i [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] * _ 0 0 * 0 * * 0 ¯             c o r r e l a t i o n f o r s u m C i + 1 [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] * _ * * 0 * 0 0 0             c o r r e l a t i o n f o r c a r r y S i [ N ; N ] = IC ( S i [ 4 N ; 2 N ] )             s a m p l i n g f o r s u m C i + 1 [ N ; N ] = IC ( C i + 1 [ 4 N ; 2 N ] )             s a m p l i n g f o r c a r r y
Y j [ 4 N ; 2 N ] = I C ( Y j [ N ; N ] ) Y j - 1 [ 4 N ; 2 N ] = I C ( Y j - 1 [ N ; N ] ) S [ 4 N ; 2 N ] = ( Y j [ 4 N ; 2 N ] · Y j - 1 [ 4 N ; 2 N ] + Y i [ 4 N ; 2 N ] · Y j - 1 [ 4 N ; 2 N ] ¯ ) * _ * 1 1 * * 1 1 + ( Y j [ 4 N ; 2 N ] ¯ · Y j - 1 [ 4 N ; 2 N ] + Y j [ 4 N ; 2 N ] · Y j - 1 [ 4 N ; 2 N ] ¯ ) * _ 1 1 * 1 * * 1 C [ 4 N ; 2 N ] = ( Y j [ 4 N ; 2 N ] ¯ · Y j - 1 [ 4 N ; 2 N ] * _ * * 1 * 1 1 1 + ( Y j [ 4 N ; 2 N ] · Y j - 1 [ 4 N ; 2 N ] ¯ ) * _ 1 * * 1 1 * 1
E i [ 4 N ; 2 N ] = encode ( X i [ N ; N ] , S i [ N ; N ] , C i [ N ; N ] ) S i [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] · S [ 4 N ; 2 N ]             m a s k i n g f o r s u m C i + 1 [ 4 N ; 2 N ] = E i [ 4 N ; 2 N ] · C [ 4 N ; 2 N ]             m a s k i n g f o r c a r r y
S i [ 4 N ; 2 N ] = S i [ 4 N ; 2 N ] 0 _ 0 0 0 0 0 0 0 ¯ C i + 1 [ 4 N ; 2 N ] = C i + 1 [ 4 N ; 2 N ] 0 _ 0 0 0 0 0 0 0 ¯ S i [ N ; N ] = IC ( S i [ 4 N ; 2 N ] ) C i + 1 [ N ; N ] = IC ( C i + 1 [ 4 N ; 2 N ] )
S j [ N ; N ] = S j + 1 [ N ; N ]             r i g h t s h i f t f o r p a r t i a l p r o d u c t

Metrics