Abstract

Using residue arithmetic it is possible to perform additions, subtractions, multiplications, and polynomial evaluation without the necessity for carry operations. Calculations can, therefore, be performed in a fully parallel manner. Several different optical methods for performing residue arithmetic operations are described. A possible combination of such methods to form a matrix vector multiplier is considered. The potential advantages of optics in performing these kinds of operations are discussed.

© 1979 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
    [CrossRef]
  2. A. Vander Lugt, Proc. IEEE 62, 1300 (1974).
    [CrossRef]
  3. J. W. Goodman, Proc. IEEE 65, 29 (1977).
    [CrossRef]
  4. V. N. Morozov, in Digest of Technical Papers, CLEA (1977), p. 81, IEEE Cat. No. 78 CH1281-5QEA.
  5. K. Preston, Coherent Optical Computers (McGraw-Hill, New York, 1972), p. 232.
  6. D. H. Schaefer, J. P. Strong, Proc. IEEE 65, 129 (1977).
    [CrossRef]
  7. N. G. Basov, W. H. Culver, B. Shah, in Laser Handbook, F. T. Arecchi, E. O. Schulz-DuBois, Eds. (North-Holland, Amsterdam, 1972), p. 1651.
  8. H. F. Taylor, Appl. Opt. 17, 1493 (1978).
    [CrossRef] [PubMed]
  9. P. W. Cheney, “An Investigation of Residue Number Theory for Digital Systems,” Ph.D. Dissertation, Stanford University, September (1961).
  10. J. W. Bond, Naval Undersea Center report AD-780-805-D1 (1974).
  11. A. Huang, “The Implementation of a Residue Arithmetic Unit Via Optical and Other Physical Phenomena,” in Proceedings of the International Optical Computing Conference, April1975, Washington, D.C., IEEE Cat. No. 75 CH0941-5 C.
  12. H. L. Garner, IRE Trans. Electron. Comput. EC-8, 140 (1959).
    [CrossRef]
  13. N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).
  14. A. Svoboda, M. Valach, “Rational System of Residue Classes,” in Stroje na Zpraccovani Informaci, Sbornik V, Nakl. CSZV. Prha, 1957 (in English), pp. 9–37.
  15. A. Svoboda, M. Valach, “Computer Progress in Czechoslovakia II, The Numerical Systems of Residue Classes,” in Digital Information Processor, W. Hoffman, Ed. (Wiley, New York, 1962).
  16. D. E. Knuth, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 248–256.
  17. N. S. Szabo, R. I. Tanaka, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 160–162.
  18. S. A. Collins, Proc. Soc. Photo Opt. Instrum. Eng. 128, 313 (1977).
  19. W. Stoner, Systems Applications, Inc., Bedford, Mass.; private communication.
  20. A convenient property of cyclic maps is that they can be built from smaller cyclic maps. A cyclic shift of 7 can be constructed by cascading cyclic shifts of 1, 2 and 4. This binary decomposition technique reduces the number of types of cyclic maps that are needed.
  21. S. K. Sheem, C. S. Tsai, Appl. Opt. 17, 892 (1978).
    [CrossRef] [PubMed]
  22. B. Chen, M. K. Barnoski, C. M. Beijer, “Thin Film Bragg Switch,” in Digest of Topical Meeting on Integrated and Fiber Optics, Salt Lake City (Optical Society of America, Washington, D.C., 1978).
  23. R. V. Schmidt, H. Kogelnik, Appl. Phys. Lett. 28, 503 (1976).
    [CrossRef]
  24. A. Huang, Y. Tsunoda, J. W. Goodman, “Optical Computation Using Residue Arithmetic,” Technical Report 6422-1, Stanford Electronics Laboratories, Stanford, Calif. 94305 (1978).

1978 (2)

1977 (5)

J. W. Goodman, Proc. IEEE 65, 29 (1977).
[CrossRef]

V. N. Morozov, in Digest of Technical Papers, CLEA (1977), p. 81, IEEE Cat. No. 78 CH1281-5QEA.

D. H. Schaefer, J. P. Strong, Proc. IEEE 65, 129 (1977).
[CrossRef]

M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
[CrossRef]

S. A. Collins, Proc. Soc. Photo Opt. Instrum. Eng. 128, 313 (1977).

1976 (1)

R. V. Schmidt, H. Kogelnik, Appl. Phys. Lett. 28, 503 (1976).
[CrossRef]

1974 (1)

A. Vander Lugt, Proc. IEEE 62, 1300 (1974).
[CrossRef]

1959 (1)

H. L. Garner, IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

1957 (1)

A. Svoboda, M. Valach, “Rational System of Residue Classes,” in Stroje na Zpraccovani Informaci, Sbornik V, Nakl. CSZV. Prha, 1957 (in English), pp. 9–37.

Barnoski, M. K.

B. Chen, M. K. Barnoski, C. M. Beijer, “Thin Film Bragg Switch,” in Digest of Topical Meeting on Integrated and Fiber Optics, Salt Lake City (Optical Society of America, Washington, D.C., 1978).

Basov, N. G.

N. G. Basov, W. H. Culver, B. Shah, in Laser Handbook, F. T. Arecchi, E. O. Schulz-DuBois, Eds. (North-Holland, Amsterdam, 1972), p. 1651.

Beijer, C. M.

B. Chen, M. K. Barnoski, C. M. Beijer, “Thin Film Bragg Switch,” in Digest of Topical Meeting on Integrated and Fiber Optics, Salt Lake City (Optical Society of America, Washington, D.C., 1978).

Bond, J. W.

J. W. Bond, Naval Undersea Center report AD-780-805-D1 (1974).

Booker, R. P.

M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
[CrossRef]

Bromley, K.

M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
[CrossRef]

Chen, B.

B. Chen, M. K. Barnoski, C. M. Beijer, “Thin Film Bragg Switch,” in Digest of Topical Meeting on Integrated and Fiber Optics, Salt Lake City (Optical Society of America, Washington, D.C., 1978).

Cheney, P. W.

P. W. Cheney, “An Investigation of Residue Number Theory for Digital Systems,” Ph.D. Dissertation, Stanford University, September (1961).

Collins, S. A.

S. A. Collins, Proc. Soc. Photo Opt. Instrum. Eng. 128, 313 (1977).

Culver, W. H.

N. G. Basov, W. H. Culver, B. Shah, in Laser Handbook, F. T. Arecchi, E. O. Schulz-DuBois, Eds. (North-Holland, Amsterdam, 1972), p. 1651.

Garner, H. L.

H. L. Garner, IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

Goodman, J. W.

J. W. Goodman, Proc. IEEE 65, 29 (1977).
[CrossRef]

A. Huang, Y. Tsunoda, J. W. Goodman, “Optical Computation Using Residue Arithmetic,” Technical Report 6422-1, Stanford Electronics Laboratories, Stanford, Calif. 94305 (1978).

Huang, A.

A. Huang, “The Implementation of a Residue Arithmetic Unit Via Optical and Other Physical Phenomena,” in Proceedings of the International Optical Computing Conference, April1975, Washington, D.C., IEEE Cat. No. 75 CH0941-5 C.

A. Huang, Y. Tsunoda, J. W. Goodman, “Optical Computation Using Residue Arithmetic,” Technical Report 6422-1, Stanford Electronics Laboratories, Stanford, Calif. 94305 (1978).

Knuth, D. E.

D. E. Knuth, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 248–256.

Kogelnik, H.

R. V. Schmidt, H. Kogelnik, Appl. Phys. Lett. 28, 503 (1976).
[CrossRef]

Monahan, M. A.

M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
[CrossRef]

Morozov, V. N.

V. N. Morozov, in Digest of Technical Papers, CLEA (1977), p. 81, IEEE Cat. No. 78 CH1281-5QEA.

Preston, K.

K. Preston, Coherent Optical Computers (McGraw-Hill, New York, 1972), p. 232.

Schaefer, D. H.

D. H. Schaefer, J. P. Strong, Proc. IEEE 65, 129 (1977).
[CrossRef]

Schmidt, R. V.

R. V. Schmidt, H. Kogelnik, Appl. Phys. Lett. 28, 503 (1976).
[CrossRef]

Shah, B.

N. G. Basov, W. H. Culver, B. Shah, in Laser Handbook, F. T. Arecchi, E. O. Schulz-DuBois, Eds. (North-Holland, Amsterdam, 1972), p. 1651.

Sheem, S. K.

Stoner, W.

W. Stoner, Systems Applications, Inc., Bedford, Mass.; private communication.

Strong, J. P.

D. H. Schaefer, J. P. Strong, Proc. IEEE 65, 129 (1977).
[CrossRef]

Svoboda, A.

A. Svoboda, M. Valach, “Rational System of Residue Classes,” in Stroje na Zpraccovani Informaci, Sbornik V, Nakl. CSZV. Prha, 1957 (in English), pp. 9–37.

A. Svoboda, M. Valach, “Computer Progress in Czechoslovakia II, The Numerical Systems of Residue Classes,” in Digital Information Processor, W. Hoffman, Ed. (Wiley, New York, 1962).

Szabo, N. S.

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

N. S. Szabo, R. I. Tanaka, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 160–162.

Tanaka, R. I.

N. S. Szabo, R. I. Tanaka, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 160–162.

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

Taylor, H. F.

Tsai, C. S.

Tsunoda, Y.

A. Huang, Y. Tsunoda, J. W. Goodman, “Optical Computation Using Residue Arithmetic,” Technical Report 6422-1, Stanford Electronics Laboratories, Stanford, Calif. 94305 (1978).

Valach, M.

A. Svoboda, M. Valach, “Rational System of Residue Classes,” in Stroje na Zpraccovani Informaci, Sbornik V, Nakl. CSZV. Prha, 1957 (in English), pp. 9–37.

A. Svoboda, M. Valach, “Computer Progress in Czechoslovakia II, The Numerical Systems of Residue Classes,” in Digital Information Processor, W. Hoffman, Ed. (Wiley, New York, 1962).

Vander Lugt, A.

A. Vander Lugt, Proc. IEEE 62, 1300 (1974).
[CrossRef]

Appl. Opt. (2)

Appl. Phys. Lett. (1)

R. V. Schmidt, H. Kogelnik, Appl. Phys. Lett. 28, 503 (1976).
[CrossRef]

Digest of Technical Papers, CLEA (1)

V. N. Morozov, in Digest of Technical Papers, CLEA (1977), p. 81, IEEE Cat. No. 78 CH1281-5QEA.

IRE Trans. Electron. Comput. (1)

H. L. Garner, IRE Trans. Electron. Comput. EC-8, 140 (1959).
[CrossRef]

Proc. IEEE (4)

M. A. Monahan, K. Bromley, R. P. Booker, Proc. IEEE 65, 121 (1977).
[CrossRef]

A. Vander Lugt, Proc. IEEE 62, 1300 (1974).
[CrossRef]

J. W. Goodman, Proc. IEEE 65, 29 (1977).
[CrossRef]

D. H. Schaefer, J. P. Strong, Proc. IEEE 65, 129 (1977).
[CrossRef]

Proc. Soc. Photo Opt. Instrum. Eng. (1)

S. A. Collins, Proc. Soc. Photo Opt. Instrum. Eng. 128, 313 (1977).

Stroje na Zpraccovani Informaci, Sbornik V (1)

A. Svoboda, M. Valach, “Rational System of Residue Classes,” in Stroje na Zpraccovani Informaci, Sbornik V, Nakl. CSZV. Prha, 1957 (in English), pp. 9–37.

Other (13)

A. Svoboda, M. Valach, “Computer Progress in Czechoslovakia II, The Numerical Systems of Residue Classes,” in Digital Information Processor, W. Hoffman, Ed. (Wiley, New York, 1962).

D. E. Knuth, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 248–256.

N. S. Szabo, R. I. Tanaka, in Seminumerical Algorithms (Addison-Wesley, Reading, Mass., 1969), pp. 160–162.

W. Stoner, Systems Applications, Inc., Bedford, Mass.; private communication.

A convenient property of cyclic maps is that they can be built from smaller cyclic maps. A cyclic shift of 7 can be constructed by cascading cyclic shifts of 1, 2 and 4. This binary decomposition technique reduces the number of types of cyclic maps that are needed.

B. Chen, M. K. Barnoski, C. M. Beijer, “Thin Film Bragg Switch,” in Digest of Topical Meeting on Integrated and Fiber Optics, Salt Lake City (Optical Society of America, Washington, D.C., 1978).

N. G. Basov, W. H. Culver, B. Shah, in Laser Handbook, F. T. Arecchi, E. O. Schulz-DuBois, Eds. (North-Holland, Amsterdam, 1972), p. 1651.

P. W. Cheney, “An Investigation of Residue Number Theory for Digital Systems,” Ph.D. Dissertation, Stanford University, September (1961).

J. W. Bond, Naval Undersea Center report AD-780-805-D1 (1974).

A. Huang, “The Implementation of a Residue Arithmetic Unit Via Optical and Other Physical Phenomena,” in Proceedings of the International Optical Computing Conference, April1975, Washington, D.C., IEEE Cat. No. 75 CH0941-5 C.

K. Preston, Coherent Optical Computers (McGraw-Hill, New York, 1972), p. 232.

N. S. Szabo, R. I. Tanaka, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).

A. Huang, Y. Tsunoda, J. W. Goodman, “Optical Computation Using Residue Arithmetic,” Technical Report 6422-1, Stanford Electronics Laboratories, Stanford, Calif. 94305 (1978).

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

Fig. 1
Fig. 1

Maps illustrating (a) residue addition by 3 and (b) residue multiplication by 3.

Fig. 2
Fig. 2

Possible approaches to constructing fixed maps using (a) mirrors, (b) prisms, (c) optical waveguides or fibers, and (d) gratings.

Fig. 3
Fig. 3

(a) Spatial permutations by means of a permutation matrix and (b) residue multiplication with a binary output.

Fig. 4
Fig. 4

Optical realization of a changeable map by means of (a) a single deflector addressing many maps and (b) multiple deflectors addressing only two maps each.

Fig. 5
Fig. 5

Changeable map realized by a series of integrated optic switches.

Fig. 6
Fig. 6

Cascade of noncyclic, cyclic, and noncyclic maps to perform residue multiplication.

Fig. 7
Fig. 7

Integrated optic switching device.

Fig. 8
Fig. 8

Elongation of the switching unit due to the small angle of incidence required.

Fig. 9
Fig. 9

Integrated optic waveguide couplers for performing permutations.

Fig. 10
Fig. 10

Block diagram of residue matrix multiplier.

Fig. 11
Fig. 11

Masks for performing residue multiplication: (a) a pair of products obtained in parallel and (b) many products obtained in parallel.

Fig. 12
Fig. 12

Over-all structure of proposed residue matrix vector multiplier (for a single modulus).

Tables (7)

Tables Icon

Table I Residue Addition

Tables Icon

Table II Residue Subtraction

Tables Icon

Table III Residue Multiplication

Tables Icon

Table IV Residue Division

Tables Icon

Table V Polynomial Evaluation by Table Lookup

Tables Icon

Table VI Construction of a Lookup Table

Tables Icon

Table VII Conversion from Residue to Mixed Radix

Equations (28)

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

R m i ,
( R m i , R m 2 , , R m N )
M = i = 1 N m i .
mod ( b × c , m i ) = 1 ,
b = | 1 = c | m i .
R m i
mod { [ P ( R m i ) , m i ] } .
P ( X ) = X + mod ( d × w , m i ) ,
P ( X ) = m i - mod ( X + mod ( d × w , m i ) , m i )
X = mod ( 756 × R 5 + 540 × R 7 + 280 × R 9 + 945 × R 4 , 1260 ) .
mod ( 756 × 1 + 540 × 1 + 280 × 7 + 945 × 2 , 1260 = mod ( 5146 , 1260 ) = 106.
X = a n 2 n + a n - 1 2 n - 1 + + a 1 2 1 + a 0 .
X = a n 2 n - 1 + a n - 1 2 n - 2 + + a 2 2 1 + a 1 .
X = [ a 3 × ( 5 × 7 × 9 ) ] + [ a 2 × ( 5 × 7 ) ] + ( a 1 × 5 ) + a 0 .
R m n
P ( X ) = ( X - R m n ) × Z ,
R m n ,
f = [ f 0 f 1 f P - 1 ] ,
H = [ h 0 , 0 h 0 , 1 h 0 , P - 1 · · · · · h Q - 1 , 0 h Q - 1 , 1 h Q - 1 , P - 1 ] ,
g = H f .
g k = p = 0 P - 1 h k , p f p .
N = P × Q × m i
S q = p = 0 P - 1 k p q 2 × 2 2 + k p q 1 × 2 1 + k p q 0 × 2 0 = 2 2 × p = 0 P - 1 k p q 2 + 2 1 × p = 0 P - 1 k p q 1 + 2 0 × p = 0 P - 1 k p q 0 .
S q = 2 2 × mod ( p = 0 P - 1 k p q 2 , 5 ) + 2 1 × mod ( p = 0 P - 1 k p q 1 , 5 ) + 2 0 × mod ( p = 0 P - 1 k p q 0 , 5 ) .
| 1 = m 1 | m i .
| 1 = m 2 | m i .
= [ T s + 12 T p encoding + T m + T d + T s + 5 P T p sum products + 7 ( T p + 5 T p ) + T d ] - 1 mixed radix conversion
= ( T s + 12 T p encoding + T m + P × T clock CCD scan + T s + 5 T p sum of binary sub products + T s elecronic mapping + 7 ( T p + 5 T p ) + T d ) - 1 mixed radix conversion , ,

Metrics