Abstract

Fully parallel modified signed-digit arithmetic operations are realized based on redundant bit representation of the digits proposed. A new truth-table minimizing technique is presented based on redundant-bit-representation coding. It is shown that only 34 minterms are enough for implementing one-step modified signed-digit addition and subtraction with this new representation. Two optical implementation schemes, correlation and matrix multiplication, are described. Experimental demonstrations of the correlation architecture are presented. Both architectures use fixed minterm masks for arbitrary-length operands, taking full advantage of the parallelism of the modified signed-digit number system and optics.

© 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. Comput. 10, 389–400 (1961).
    [CrossRef]
  2. 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).
  3. K. H. Hwang, A. Louri, “Optical multiplication and division using modified signed-digit symbolic substitution,” Opt. Eng. 28, 364–372 (1989).
  4. 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–2457 (1986).
    [CrossRef] [PubMed]
  5. K.-H. Brenner, A. Huang, N. Streibl, “Digital optical computing with symbolic substitution,” Appl. Opt. 25, 3054–3060 (1986).
    [CrossRef] [PubMed]
  6. T. K. Gaylord, M. M. Mirsalehi, “Truth table look up processing: number representation, multilevel coding, and logical minimization,” Opt. Eng. 25, 22–28 (1986).
  7. M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
    [CrossRef] [PubMed]
  8. 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]
  9. E. Botha, D. Casasent, E. Barard, “Optical symbolic substitution using multichannel correlator,” Appl. Opt. 27, 817–818 (1988).
    [CrossRef] [PubMed]
  10. A. Louri, “Efficient optical implementation methods for symbolic substitution logic based on shadow casting,” Appl. Opt. 28, 3264–3267 (1989).
  11. R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 28, 2126–2134 (1990).
    [CrossRef]
  12. H. Jeon, M. A. G. Abushagur, A. A. Sawchuk, B. K. Jenkins, “Digital opticalk processor based on symbolic substitution using holographic matched filtering,” Appl. Opt. 29, 2113–2125 (1990).
    [CrossRef] [PubMed]
  13. H. M. Gibbs, Optical Bistability: Controlling Light with Light (Academic, Orlando, Fla., 1985), pp. 93–188.
  14. D. Sanger, E. Wihardjo, “Parallel optical logic gates using one-dimensional spatial encoding,” Opt. Eng. 29, 690–695 (1990).
    [CrossRef]
  15. A. A. S. Awwal, M. A. Karim, A. K. Cherri, “Polarization-encoded optical shadow-casting scheme: design of multioutput trinary combinational logic units,” Appl. Opt. 26, 4814–4818 (1987).
    [CrossRef] [PubMed]
  16. H. Huang, M. Itoh, T. Yatagai, “One-step modified signed-digit addition/subtraction based on redundant bit representation,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp. 200–203.
  17. 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]
  18. A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of Tenth International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.
  19. S. Barua, “Single-stage optical adder/subtractor,” Opt. Eng. 30, 265–270 (1991).
    [CrossRef]
  20. See, for example, M. S. Alam, M. A. Karim, A. A. S. Awwal, J. J. Westerkamp, “Optical processing based on conditional higher-order trinary modified signed-digit symbolic substitution,” Appl. Opt. 31, 5614–5621 (1992).
    [CrossRef] [PubMed]
  21. M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
    [CrossRef]
  22. H. Huang, L. Liu, Z. Wang, “Parallel multiple matrix multiplication using orthogonal shadow-casting and imaging system,” Opt. Lett. 15, 1085–1087 (1990).
    [CrossRef] [PubMed]
  23. C. Gu, S. Campbell, J. Hong, Q. B. He, D. Zhang, P. Yeh, “Optical thresholding and maximum operations,” Appl. Opt. 31, 5661–5665 (1992).
    [CrossRef] [PubMed]
  24. M. T. Fatehi, K. C. Wasmundt, S. A. Collins, “Optical logic gates using a liquid crystal light valve: implementation and application example,” Appl. Opt. 20, 2250–2256 (1981).
    [CrossRef] [PubMed]
  25. H.-K. Liu, T.-T. Chao, “Liquid crystal television spatial light modulator,” Appl. Opt. 28, 4722–4780 (1989).
    [CrossRef]
  26. K. Akiyama, A. Takimoto, M. Ogawa, “Photoaddressed spatial light modulator using transmissive and highly photosensitive amorphous-silicon carbide film.” Appl. Opt. 32, 6493–6500 (1993).
    [CrossRef] [PubMed]

1993 (1)

1992 (2)

1991 (1)

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

1990 (4)

1989 (3)

H.-K. Liu, T.-T. Chao, “Liquid crystal television spatial light modulator,” Appl. Opt. 28, 4722–4780 (1989).
[CrossRef]

A. Louri, “Efficient optical implementation methods for symbolic substitution logic based on shadow casting,” Appl. Opt. 28, 3264–3267 (1989).

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

1988 (1)

1987 (2)

1986 (5)

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).

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

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

T. K. Gaylord, M. M. Mirsalehi, “Truth table look up processing: number representation, multilevel coding, and logical minimization,” Opt. Eng. 25, 22–28 (1986).

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

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]

1981 (1)

1977 (1)

M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
[CrossRef]

1961 (1)

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

Abushagur, M. A. G.

Akiyama, K.

Alam, M. S.

Avizienis, A.

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

Awwal, A. A. S.

Barard, E.

Barua, S.

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

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).

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

M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
[CrossRef]

Botha, E.

Brenner, K.-H.

Bronley, K.

M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
[CrossRef]

Campbell, S.

Casasent, D.

Chao, T.-T.

Cherri, A. K.

Collins, S. A.

Drake, B. L.

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

Eichmann, G.

Fatehi, M. T.

Gaylord, T. K.

T. K. Gaylord, M. M. Mirsalehi, “Truth table look up processing: number representation, multilevel coding, and logical minimization,” Opt. Eng. 25, 22–28 (1986).

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

Gibbs, H. M.

H. M. Gibbs, Optical Bistability: Controlling Light with Light (Academic, Orlando, Fla., 1985), pp. 93–188.

Gu, C.

He, Q. B.

Henderson, T. B.

Hong, J.

Huang, A.

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

A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of Tenth International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.

Huang, H.

H. Huang, L. Liu, Z. Wang, “Parallel multiple matrix multiplication using orthogonal shadow-casting and imaging system,” Opt. Lett. 15, 1085–1087 (1990).
[CrossRef] [PubMed]

H. Huang, M. Itoh, T. Yatagai, “One-step modified signed-digit addition/subtraction based on redundant bit representation,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp. 200–203.

Hwang, K. H.

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

Itoh, M.

H. Huang, M. Itoh, T. Yatagai, “One-step modified signed-digit addition/subtraction based on redundant bit representation,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp. 200–203.

Jenkins, B. K.

Jeon, H.

Karim, M. A.

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

Li, Y.

Liu, H.-K.

Liu, L.

Louri, A.

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

A. Louri, “Efficient optical implementation methods for symbolic substitution logic based on shadow casting,” Appl. Opt. 28, 3264–3267 (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.

T. K. Gaylord, M. M. Mirsalehi, “Truth table look up processing: number representation, multilevel coding, and logical minimization,” Opt. Eng. 25, 22–28 (1986).

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

Monahan, M. A.

M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
[CrossRef]

Ogawa, 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).

Pedrini, G.

R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 28, 2126–2134 (1990).
[CrossRef]

Sanger, D.

D. Sanger, E. Wihardjo, “Parallel optical logic gates using one-dimensional spatial encoding,” Opt. Eng. 29, 690–695 (1990).
[CrossRef]

Sawchuk, A. A.

Streibl, N.

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]

Takimoto, A.

Thalmann, R.

R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 28, 2126–2134 (1990).
[CrossRef]

Wang, Z.

Wasmundt, K. C.

Weible, K. J.

R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 28, 2126–2134 (1990).
[CrossRef]

Westerkamp, J. J.

Wihardjo, E.

D. Sanger, E. Wihardjo, “Parallel optical logic gates using one-dimensional spatial encoding,” Opt. Eng. 29, 690–695 (1990).
[CrossRef]

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]

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]

Yatagai, T.

H. Huang, M. Itoh, T. Yatagai, “One-step modified signed-digit addition/subtraction based on redundant bit representation,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp. 200–203.

Yeh, P.

Zhang, D.

Appl. Opt. (14)

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

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

M. M. Mirsalehi, T. K. Gaylord, “Logical minimization of multilevel coded function,” Appl. Opt. 25, 3078–3088 (1986).
[CrossRef] [PubMed]

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]

E. Botha, D. Casasent, E. Barard, “Optical symbolic substitution using multichannel correlator,” Appl. Opt. 27, 817–818 (1988).
[CrossRef] [PubMed]

A. Louri, “Efficient optical implementation methods for symbolic substitution logic based on shadow casting,” Appl. Opt. 28, 3264–3267 (1989).

R. Thalmann, G. Pedrini, K. J. Weible, “Optical symbolic substitution using diffraction gratings,” Appl. Opt. 28, 2126–2134 (1990).
[CrossRef]

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

A. A. S. Awwal, M. A. Karim, A. K. Cherri, “Polarization-encoded optical shadow-casting scheme: design of multioutput trinary combinational logic units,” Appl. Opt. 26, 4814–4818 (1987).
[CrossRef] [PubMed]

See, for example, M. S. Alam, M. A. Karim, A. A. S. Awwal, J. J. Westerkamp, “Optical processing based on conditional higher-order trinary modified signed-digit symbolic substitution,” Appl. Opt. 31, 5614–5621 (1992).
[CrossRef] [PubMed]

C. Gu, S. Campbell, J. Hong, Q. B. He, D. Zhang, P. Yeh, “Optical thresholding and maximum operations,” Appl. Opt. 31, 5661–5665 (1992).
[CrossRef] [PubMed]

M. T. Fatehi, K. C. Wasmundt, S. A. Collins, “Optical logic gates using a liquid crystal light valve: implementation and application example,” Appl. Opt. 20, 2250–2256 (1981).
[CrossRef] [PubMed]

H.-K. Liu, T.-T. Chao, “Liquid crystal television spatial light modulator,” Appl. Opt. 28, 4722–4780 (1989).
[CrossRef]

K. Akiyama, A. Takimoto, M. Ogawa, “Photoaddressed spatial light modulator using transmissive and highly photosensitive amorphous-silicon carbide film.” Appl. Opt. 32, 6493–6500 (1993).
[CrossRef] [PubMed]

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. Comput. (1)

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

Opt. Eng. (5)

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).

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

T. K. Gaylord, M. M. Mirsalehi, “Truth table look up processing: number representation, multilevel coding, and logical minimization,” Opt. Eng. 25, 22–28 (1986).

D. Sanger, E. Wihardjo, “Parallel optical logic gates using one-dimensional spatial encoding,” Opt. Eng. 29, 690–695 (1990).
[CrossRef]

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

Opt. Lett. (1)

Proc. IEEE (1)

M. A. Monahan, K. Bronley, R. P. Bocker, “Incoherent optical correlator,” Proc. IEEE 65, 121–129 (1977).
[CrossRef]

Other (3)

A. Huang, “Parallel algorithms for optical digital computers,” in Proceedings of Tenth International Optical Computing Conference (Institute of Electrical and Electronics Engineers, New York, 1983), pp. 13–17.

H. Huang, M. Itoh, T. Yatagai, “One-step modified signed-digit addition/subtraction based on redundant bit representation,” in Optical Computing, Vol. 7 of 1993 OSA Technical Digest Series (Optical Society of America, Washington, D.C., 1993), pp. 200–203.

H. M. Gibbs, Optical Bistability: Controlling Light with Light (Academic, Orlando, Fla., 1985), pp. 93–188.

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

Fig. 1
Fig. 1

(a) Diagram for a three-step MSD adder and subtracter, (b) one functional block. FB, functional block; X, input port X; Y, input port Y; W, weight output port; T, transfer output port.

Fig. 2
Fig. 2

Examples of redundant bit representation (RBR): (a) two-for-one RBR coding of binary digits, (b) three-for-one RBR coding of MSD digits.

Fig. 3
Fig. 3

Schemes for classifying digit pairs: (a) the SLOP digit pair, (b) the CP digit pair.

Fig. 4
Fig. 4

Optical encoding for MSD arithmetic operations with a column vector: (a) encoding of independent elements of the minterms; (b) arrangement of three pair digits for encoding a minterm; (c), (d), (e) encoded computational rules for output digits 1, 0, and 1 ¯ of MSD addition, which show the minterms [522166], [524266], and [551177], respectively; (f) the minterm mask for the recorded 34 minterms.

Fig. 5
Fig. 5

Same as Fig. 4 but with a row vector.

Fig. 6
Fig. 6

Encoding of 34 minterms for implementation with a matrix multiplication scheme: (a) arrangement for encoding a minterm, (b) partitions of a minterm mask for encoding minterms that produce output digits 1 and 1 ¯ , (c) encoded minterm mask.

Fig. 7
Fig. 7

Optical encoding of input operands for correlation implementation with a column vector. Here Ø denotes padded zero. Two n-bit operands are encoded into a 6 × (n + 3) binary pattern.

Fig. 8
Fig. 8

Simulation for MSD addition based on correlation: (a) two input operands and the theoretical result; (b) the encoded input matrix; (c) part of the correlation matrix; (d) the sampled matrix; (e) the thresholding matrix of (d); (f) the final result after postprocessing; the upper (lower) row corresponds to output digit 1 ( 1 ¯ ) , and thus the sum is 01 1 ¯ 1 1 ¯ .

Fig. 9
Fig. 9

Sketch of implementing MSD addition (subtraction) based on optical correlation. NTA, nonlinear threshold device array; PDA, photodiode array.

Fig. 10
Fig. 10

Photograph of the correlation between the encoded input operands shown in Fig. 8(b) and the first two minterms of the minterm mask shown in Fig. 6(a). The theoretical prediction is shown in Fig. 8(c).

Fig. 11
Fig. 11

Compacted minterm mask of 34 minterms for performing MSD addition with correlation.

Fig. 12
Fig. 12

Experimental demonstration of implementation with optical correlation: (a) encoded input mask, (b) photograph of the correlation between the minterm mask shown in Fig. 11 and the encoded input mask, (c) sampling result of (b), and (d) final result.

Fig. 13
Fig. 13

Optical encoding of input operands for matrix multiplication implementation. Two n-bit operands are encoded into an 18 × (n + 1) pattern.

Fig. 14
Fig. 14

Simulation for MSD addition based on matrix multiplication: (a) two input operands and the theoretical result; (b) the encoded input matrix; (c) the product matrix of the minterm matrix, shown in Fig. 6(c), with the input matrix; (d) the thresholding matrix of (c); (e) the final result after postprocessing; the upper (lower) row corresponds to output digit 1 ( 1 ¯ ) , and thus the sum is 101 1 ¯ 1 1 ¯ 0 1 ¯ 0 1 ¯ .

Fig. 15
Fig. 15

Comparison of several MSD addition schemes.

Tables (6)

Tables Icon

Table 1 Truth Table of Functional Blocks A, B, and A′ for a Three-Step Modified Signed-Digit Adder and Subtractor

Tables Icon

Table 2 Truth Table for One-Step Modified Signed-Digit Addition a

Tables Icon

Table 3 Reduced Minterms for One-Step Modified Signed-Digit Addition

Tables Icon

Table 4 Reduced Minterme for Modified Signed-Digit Subtraction

Tables Icon

Table 5 Reduced Minterms for Binary Input One-Step Modified Signed-Digit Addition

Tables Icon

Table 6 Reduced Minterms for Binary Input One-Step Modified Signed-Digit Subtraction

Equations (6)

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

A = i a i 2 i ,
[ x i y i x i 1 y i 1 x i 2 y i 2 ] z i ,
[ 5 5 4 4 7 7 ] 1 , [ 2 2 4 4 7 7 ] 1 , [ 2 5 4 4 7 7 ] 0 , [ 5 2 4 4 7 7 ] 0 .
[ 5 5 2 4 6 6 ] 1 , [ 2 2 2 4 6 6 ] 1 , [ 2 5 2 4 1 7 ] 1 ¯ , [ 5 2 2 4 1 7 ] 1 ¯ , [ 2 5 2 4 6 1 ] 1 ¯ , [ 5 2 2 4 6 1 ] 1 ¯ , [ 2 5 2 4 6 6 ] 0 , [ 5 2 2 4 6 6 ] 0 , [ 5 5 2 4 1 7 ] 0 , [ 2 2 2 4 1 7 ] 0 , [ 5 5 2 4 6 1 ] 0 , [ 2 2 2 4 6 1 ] 0 .
k l 6 ( n + 4 ) ,
X i X i 1 Y i Y i 1 Z i ( Z i ) .

Metrics