Cited By
View all- Kallman R(1983)A Faster 8-Bit Carry CircuitIEEE Transactions on Computers10.1109/TC.1983.167618832:12(1209-1211)Online publication date: 1-Dec-1983
Combinational Circuit Synthesis with Time and Component Bounds
Pages 712 - 726
Abstract
New results are given concerning the design of combinational logic circuits. We give time and component bounds for combinational circuits specified in several ways. For any sequential machine defined by linear recurrence relations, we discuss an algorithm for the synthesis of equivalent combinational logic. The procedure includes upper bounds on the time and components involved. We also discuss the transformation of nonlinear recurrences into combinational circuits. Examples are given using gates as well as IC's as components. These include binary addition, multiplication, and ones' position counting. The time and component bounds our procedure yields compare favorably with traditional results.
References
[1]
S. Winograd, "On the time required to perform addition," J. Ass. Comput. Mach., vol. 12, pp. 277-285, Apr. 1965.
[2]
R. Brent, "On the addition of binary numbers," IEEE Trans. Comput., vol. C-19, pp. 758-759, Aug. 1970.
[3]
S. Winograd, "On the time required to perform multiplication," J. Assoc. Comput. Mach., vol. 14, pp. 793-802, Oct. 1967.
[4]
E. Bloch, "The central processing unit," in Planning a Computer System, W. Buchholz, Ed. New York: McGraw-Hill, 1962.
[5]
O. L. Mac Sorley, "High speed arithmetic in binary computers," Proc. IRE, pp. 67-91, 1961.
[6]
R. Brent, D. J. Kuck, and K. Maruyama, "The parallel evaluation of arithmetic expressions without division," IEEE Trans. Comput., vol. C-22, pp. 532-534, May 1973.
[7]
S. C. Chen and D. J. Kuck, "Time and parallel processor bounds for linear recurrence systems," IEEE Trans. Comput., vol. C-24, pp. 701-717, July 1975.
[8]
D. J. Kuck and Y. Muraoka, "Bounds on the parallel evaluation of arithmetic expressions using associativity and commutativity," Acta Informatica, vol. 3, fasc. 3, pp. 203-216, 1974.
[9]
R. P. Brent, "The parallel evaluation of arithmetic expressions in logarithmic time," in Complexity of Sequential and Parallel Numerical Algorithms, J. F. Traub, Ed. New York: Academic Press, 1973.
[10]
F. P. Preparata, D. E. Muller, and A. B. Barak, "Reduction of depth of Boolean networks with a fan-in constraint," IEEE Trans. Comput., to be published.
[11]
A. H. Sameh and R. P. Brent, "Solving triangular systems on a parallel computer," SIAM J. of Numer. Analysis; also Dep. Comput. Sci., Univ. of Illinois, Urbana-Champaign, Rep. 75-766, Nov. 1975; (NSF -OCA-DCR73-07980 A02 000014).
[12]
S. C. Chen, "Speedup of iterative programs in multiprocessor systems," Ph.D. dissertation, Dep. Comput. Sci., Univ. of Illinois at Urbana-Champaign, 75-694, Jan. 1975; (NSF-OCA-GJ-36936- 000004).
[13]
A. Habibi and P. A. Wintz, "Fast multipliers," IEEE Trans. Comput., vol. C-19, pp. 153-157, Feb. 1970.
[14]
C. S. Wallace, "'A suggestion for a fast multiplier," IEEE Trans. Electron. Comput., vol. EC-13, pp. 14-17, Feb. 1964.
[15]
L. Dadda, "Some schemes for parallel multipliers," Alta Frequenza, vol. 31, pp. 319-356, Mar. 1965.
[16]
W. D. Little, "An algorithm for high-speed digital filters," IEEE Trans. Comput., vol. C-23, pp. 466-469, May 1974.
[17]
L. B. Jackson, Jr. F. Kaiser, and H. S. McDonald, "An approach to the implementation of digital filters," IEEE Trans. Audio Electroacoust., vol. AU-16, Sept. 1968.
Recommendations
Towards ultra-efficient QCA reversible circuits
Nanotechnologies, remarkably Quantum-dot Cellular Automata (QCA), offer an attractive perspective for future computing technologies. In this paper, QCA is investigated as an implementation method for reversible logic. A novel XOR gate and also a new ...
Optimization of combinational and sequential logic circuits for low power using precomputation
ARVLSI '95: Proceedings of the 16th Conference on Advanced Research in VLSI (ARVLSI'95)Precomputation is a recently proposed logic optimization technique which selectively disables the inputs of a sequential logic circuit, thereby reducing switching activity and power dissipation, without changing logic functionality. In this paper, we ...
Time-Component Complexity of Two Approaches to Multioperand Binary Addition
Component and time complexity measures in terms of number of gates and gate delays, respectively, are derived for two multioperand adder structures: a tree of carry-save adders and a tree of carry-lookahead adders. The parameters of the complexity ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 1977.
Publisher
IEEE Computer Society
United States
Publication History
Published: 01 August 1977
Author Tags
Qualifiers
- Research-article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- View Citations1Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 22 Dec 2024
Other Metrics
Citations
Cited By
View all- Kallman R(1983)A Faster 8-Bit Carry CircuitIEEE Transactions on Computers10.1109/TC.1983.167618832:12(1209-1211)Online publication date: 1-Dec-1983