Abstract

A new conditional symbolic substitution rule for modified signed-digit arithmetic computation is introduced. Using this substitution rule, the numbers to be added or subtracted are first replaced by a pair of new equivalent strings, which in a second step are then subject to another substitution to generate both the addition or subtraction result and its complement. For an optical implementation, a holographic content-addressable memory is used. Correspondingly, the input encoding, the logic reduction, and the optical processing techniques are described.

© 1987 Optical Society of America

Full Article  |  PDF Article

References

  • View by:
  • |
  • |
  • |

  1. S. L. Hurst, “Multiple Valued Logic—its Status and its Future,” IEEE Trans. Comput. C-33, 1160 (1984).
    [CrossRef]
  2. T. T. Dao, D. M. Campbell, “Multiple-Valued Logic: an Implementation,” Opt. Eng. 25, 14 (1986).
    [CrossRef]
  3. G. Eichmann, Y. Li, R. R. Alfano, “Optical Binary Coded Ternary Arithmetic and Logic,” Appl. Opt. 25, 3113 (1986).
    [CrossRef] [PubMed]
  4. N. S. Szabo, R. I. Tanada, Residue Arithmetic and Its Applications to Computer Technology (McGraw-Hill, New York, 1967).
  5. A. Huang, Y. Tsunida, J. W. Goodman, S. Ishihara, “Optical Computation Using Residue Arithmetic,” Appl. Opt. 18, 149 (1979).
    [CrossRef] [PubMed]
  6. D. Psaltis, D. Casasent, “Optical Residue Arithmetic: a Correlation Approach,” Appl. Opt. 18, 163 (1979).
    [CrossRef] [PubMed]
  7. A. Tai, I. Cindrich, J. R. Fienup, C. C. Aleksoff, “Optical Residue Arithmetic Computer with Programmable Computation Modules,” Appl. Opt. 18, 2812 (1979).
    [CrossRef] [PubMed]
  8. A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
    [CrossRef]
  9. N. Takagi, H. Yasuura, S. Yajima, “High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree,” IEEE Trans. Comput. C-34, 789 (1985).
    [CrossRef]
  10. 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 (1986).
    [CrossRef]
  11. 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 (1986).
    [CrossRef] [PubMed]
  12. M. M. Mirsalehi, T. K. Gaylord, “Logical Minimization of Multilevel Coded Function,” Appl. Opt. 25, 3078 (1986).
    [CrossRef] [PubMed]
  13. C. C. Guest, T. K. Gaylord, “Truth-Table Look-up Optical Processing Utilizing Binary and Residue Arithmetic,” Appl. Opt. 19, 1201 (1980).
    [CrossRef] [PubMed]
  14. M. M. Mirsalehi, C. C. Guest, T. K. Gaylord, “Residue Number System Holographic Truth-Table Look-up Processing: Detector Threshold Setting and Probability of Error due to Amplitude and Phase Variations,” Appl. Opt. 22, 3583 (1983).
    [CrossRef] [PubMed]
  15. M. M. Mirsalehi, T. K. Gaylord, “Truth-Table Look-up Parallel Data Processing Using an Optical Content-Addressable Memory,” Appl. Opt. 25, 2277 (1986).
    [CrossRef] [PubMed]

1986

1985

N. Takagi, H. Yasuura, S. Yajima, “High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree,” IEEE Trans. Comput. C-34, 789 (1985).
[CrossRef]

1984

S. L. Hurst, “Multiple Valued Logic—its Status and its Future,” IEEE Trans. Comput. C-33, 1160 (1984).
[CrossRef]

1983

1980

1979

1961

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Aleksoff, C. C.

Alfano, R. R.

Avizienis, A.

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Bocker, R. P.

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 (1986).
[CrossRef] [PubMed]

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 (1986).
[CrossRef]

Campbell, D. M.

T. T. Dao, D. M. Campbell, “Multiple-Valued Logic: an Implementation,” Opt. Eng. 25, 14 (1986).
[CrossRef]

Casasent, D.

Cindrich, I.

Dao, T. T.

T. T. Dao, D. M. Campbell, “Multiple-Valued Logic: an Implementation,” Opt. Eng. 25, 14 (1986).
[CrossRef]

Drake, B. L.

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 (1986).
[CrossRef]

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 (1986).
[CrossRef] [PubMed]

Eichmann, G.

Fienup, J. R.

Gaylord, T. K.

Goodman, J. W.

Guest, C. C.

Henderson, T. B.

Huang, A.

Hurst, S. L.

S. L. Hurst, “Multiple Valued Logic—its Status and its Future,” IEEE Trans. Comput. C-33, 1160 (1984).
[CrossRef]

Ishihara, S.

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 (1986).
[CrossRef] [PubMed]

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 (1986).
[CrossRef]

Li, Y.

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 (1986).
[CrossRef]

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 (1986).
[CrossRef]

Psaltis, D.

Szabo, N. S.

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

Tai, A.

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 (1985).
[CrossRef]

Tanada, R. I.

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

Tsunida, Y.

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 (1985).
[CrossRef]

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 (1985).
[CrossRef]

Appl. Opt.

G. Eichmann, Y. Li, R. R. Alfano, “Optical Binary Coded Ternary Arithmetic and Logic,” Appl. Opt. 25, 3113 (1986).
[CrossRef] [PubMed]

A. Huang, Y. Tsunida, J. W. Goodman, S. Ishihara, “Optical Computation Using Residue Arithmetic,” Appl. Opt. 18, 149 (1979).
[CrossRef] [PubMed]

D. Psaltis, D. Casasent, “Optical Residue Arithmetic: a Correlation Approach,” Appl. Opt. 18, 163 (1979).
[CrossRef] [PubMed]

A. Tai, I. Cindrich, J. R. Fienup, C. C. Aleksoff, “Optical Residue Arithmetic Computer with Programmable Computation Modules,” Appl. Opt. 18, 2812 (1979).
[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 (1986).
[CrossRef] [PubMed]

M. M. Mirsalehi, T. K. Gaylord, “Logical Minimization of Multilevel Coded Function,” Appl. Opt. 25, 3078 (1986).
[CrossRef] [PubMed]

C. C. Guest, T. K. Gaylord, “Truth-Table Look-up Optical Processing Utilizing Binary and Residue Arithmetic,” Appl. Opt. 19, 1201 (1980).
[CrossRef] [PubMed]

M. M. Mirsalehi, C. C. Guest, T. K. Gaylord, “Residue Number System Holographic Truth-Table Look-up Processing: Detector Threshold Setting and Probability of Error due to Amplitude and Phase Variations,” Appl. Opt. 22, 3583 (1983).
[CrossRef] [PubMed]

M. M. Mirsalehi, T. K. Gaylord, “Truth-Table Look-up Parallel Data Processing Using an Optical Content-Addressable Memory,” Appl. Opt. 25, 2277 (1986).
[CrossRef] [PubMed]

IEEE Trans. Comput.

N. Takagi, H. Yasuura, S. Yajima, “High-Speed VLSI Multiplication Algorithm with a Redundant Binary Addition Tree,” IEEE Trans. Comput. C-34, 789 (1985).
[CrossRef]

S. L. Hurst, “Multiple Valued Logic—its Status and its Future,” IEEE Trans. Comput. C-33, 1160 (1984).
[CrossRef]

IRE Trans. Electron. Comput.

A. Avizienis, “Signed-Digit Number Representations for Fast Parallel Arithmetic,” IRE Trans. Electron. Comput. EC-10, 389 (1961).
[CrossRef]

Opt. Eng.

T. T. Dao, D. M. Campbell, “Multiple-Valued Logic: an Implementation,” Opt. Eng. 25, 14 (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 (1986).
[CrossRef]

Other

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

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

Fig. 1
Fig. 1

Four-digit MSD addition (subtraction) network. X(Y), input strings; T(W), transfer (weight) operators for addition or subtraction; A(C), operators to obtain the final addition (subtraction) result R and its complement C. The operators indicated within the dashed boxes may be deleted.

Fig. 2
Fig. 2

Holographic CAM recording and logic processing unit. X(Y), the input variables; Rt(w) and RT(W), the general reference and the reference for the transfer (weight) operations, respectively; DT(W), detector array for logic T(W) operation.

Fig. 3
Fig. 3

Holographic CAM-based MSD processing for the pattern 1 1 ¯ 1 ¯ X. Three recording steps are used.

Fig. 4
Fig. 4

Schematic setup for implementing the MSD T and W logic operations using a holographic CAM-based system.

Tables (7)

Tables Icon

Table I MSD Addition Six Possible Bit-Pair Carries and Sums

Tables Icon

Table II First MSD Addition Conditional Symbolic Substitution Rule Truth Table for Rearranging Data: T+(W+), the Corresponding Transfer (Weight) Operator

Tables Icon

Table III Second MSD Addition Bit-wise Symbolic Substitution Rule Truth Table: A (C), the Sum (Complement of the Sum) Operator

Tables Icon

Table IV First MSD Subtraction Conditional Symbolic Substitution Rule Truth Table [Converting the Subtraction to Addition Operation and Rearranging the Addition Data: T(W), the Corresponding Transfer (Weight) Operator]

Tables Icon

Table V Reduced Logic Minterm Expressions for the Implementation of the MSD Addition and Subtraction Operations. The × Denotes a Do Not Care as Specified in Table VII. The Four Variable Minterm is Grouped as [ x i x i - 1 y i y i - 1 ]

Tables Icon

Table VI Comparison Among the One-, Two- and Three-Step N-bit CAM MSD Addition Schemes. In Terms of Processing Speed, the One-Step Method is the Fastest, While in Terms of the Product of the Speed and Total Number of References, the Two-Step Method is the Optimum.

Tables Icon

Table VII Various MSD Do Not Care Types and Their Corresponding Spatial Encoding: m, n, and E Denote the Number of Nonzero, the Number of Do Not Care Bits, and the Single General Reference Bit Exposure, Respectively.

Equations (13)

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

A = i a i 2 i ,
A = 1 1 ¯ 1 1 ¯ 1 MSD ,
B = 1 ¯ 1 1 ¯ 1 1 ¯ MSD ,
0 + 1 = 1 + 0 = 01 MSD and 0 + 1 ¯ = 1 ¯ + 0 = 0 1 ¯ MSD
0 + 1 = 1 + 0 = 1 1 ¯ MSD and 0 + 1 ¯ = 1 ¯ + 0 = 1 ¯ 1 MSD .
10 1 ¯ 1 ¯ 1010 1 ¯ 01 1 ¯ + 1 1 ¯ 1 ¯ 100 1 ¯ 10110.
1 1 ¯ 1 ¯ 01000011 1 ¯ ϕ + ϕ 0100 1 ¯ 001 1 ¯ 1 ¯ 01 ,
1 1 ¯ 001 1 ¯ 00100 1 ¯ 1 for the addition result ,
1 ¯ 100 1 ¯ 100 1 ¯ 001 1 ¯ for the complement of addition .
10 1 ¯ 1 ¯ 1010 1 ¯ 01 1 ¯ - 1 1 ¯ 1 ¯ 100 1 ¯ 10110.
000 1 ¯ 101 1 ¯ 1 ¯ 00 1 ¯ ϕ + ϕ 0100 1 ¯ 0011 1 ¯ 01 ,
001 1 ¯ 1 1 ¯ 1 1 ¯ 01 1 ¯ 1 ¯ 1 for the subtraction result ,
00 1 ¯ 1 1 ¯ 1 1 ¯ 10 1 ¯ 11 1 ¯ for the complement of subtraction .

Metrics