A Generalized Tree Circuit

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

A Generalized Tree Circuit

Full text

Pdf (453 KB)

Source

Journal of the ACM (JACM) archive
Volume 8 , Issue 4 (October 1961) table of contents

Pages: 484 - 496

Year of Publication: 1961

ISSN:0004-5411

Author

H. Allen Curtis

Lewis Research Center, N.A.S.A., Cleveland, Ohio

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 1, Downloads (12 Months): 28, Citation Count: 14

Additional Information:

abstract references cited by index terms

Tools and Actions:	Request Permissions Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/321088.321091 What is a DOI?

ABSTRACT

From the very founding of switching theory by Claude E. Shannon, the tree circuit has been a useful instrument in the design of logic networks. Besides being a valuable practical addition to the designer's “tool kit”, it has been a theoretical asset in the study of circuit complexity and the establishment of general bounds on the relative costs of switching networks. The object of this paper is to expand the practical and theoretical scope of the tree circuit. The expansion is effected by the formulation of a generalized tree circuit, which in actuality is a set of circuits having basic tree circuit characteristics.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	SHANNON, C.E. A symbolic analysis of relay and switching circuits. Trans. A. 1. E. E. 7 (1938).
	2	ASH~NHUaST, R.L. The decomposition of switching functions. Proceedings of an International ~ymposium on the Theory of Switching (1959).
	3	H. Allen Curtis, A Functional Canonical Form, Journal of the ACM (JACM), v.6 n.2, p.245-258, April 1959 [doi>10.1145/320964.320982]

CITED BY 14

	C. Scholl, Multi-output functional decomposition with exploitation of don't cares, Proceedings of the conference on Design, automation and test in Europe, p.743-748, February 23-26, 1998, Le Palais des Congrés de Paris, France
	Jian Qiao , Makoto Ikeda , Kunihiro Asada, Finding an optimal functional decomposition for LUT-based FPGA synthesis, Proceedings of the 2001 conference on Asia South Pacific design automation, p.225-230, January 2001, Yokohama, Japan
	Jason Cong , Yean-Yow Hwang, Partially-dependent functional decomposition with applications in FPGA synthesis and mapping, Proceedings of the 1997 ACM fifth international symposium on Field-programmable gate arrays, p.35-42, February 09-11, 1997, Monterey, California, United States
	H. Allen Curtis, Use of Decomposition Theory in the Solution of the State Assignment Problem of Sequential Machines, Journal of the ACM (JACM), v.10 n.3, p.386-411, July 1963
	Christian Legl , Bernd Wurth , Klaus Eckl, A Boolean approach to performance-directed technology mapping for LUT-based FPGA designs, Proceedings of the 33rd annual conference on Design automation, p.730-733, June 03-07, 1996, Las Vegas, Nevada, United States
	Jason Cong , Yuzheng Ding, Combinational logic synthesis for LUT based field programmable gate arrays, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.1 n.2, p.145-204, April 1996
	H. Allen Curtis, Generalized Tree Circuit—The Basic Building Block of an Extended Decomposition Theory, Journal of the ACM (JACM), v.10 n.4, p.562-581, Oct. 1963
	Jason Cong , Yean-Yow Hwang, Structural gate decomposition for depth-optimal technology mapping in LUT-based FPGA designs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.5 n.2, p.193-225, April 2000
	L. Józwiak , A. Chojnacki, High-quality sub-function construction in functional decomposition based on information relationship measures, Proceedings of the conference on Design, automation and test in Europe, p.383-390, March 2001, Munich, Germany
	Jason Cong , Yean-Yow Hwang, Boolean matching for complex PLBs in LUT-based FPGAs with application to architecture evaluation, Proceedings of the 1998 ACM/SIGDA sixth international symposium on Field programmable gate arrays, p.27-34, February 22-25, 1998, Monterey, California, United States
	Bernd Wurth , Ulf Schlichtmann , Klaus Eckl , Kurt J. Antreich, Functional multiple-output decomposition with application to technology mapping for lookup table-based FPGAs, ACM Transactions on Design Automation of Electronic Systems (TODAES), v.4 n.3, p.313-350, July 1999
	Lech Jóźwiak , Aleksander S´lusarczyk, General decomposition of incompletely specified sequential machines with multi-state behavior realization, Journal of Systems Architecture: the EUROMICRO Journal, v.50 n.8, p.445-492, August 2004
	L. JóŹwiak , A. Chojnacki, Effective and efficient FPGA synthesis through general functional decomposition, Journal of Systems Architecture: the EUROMICRO Journal, v.49 n.4-6, p.247-265, September 2003
	L. Jóźwiak , S. Biegański , A. Chojnacki, Information-driven circuit synthesis with the pre-characterized gate libraries, Journal of Systems Architecture: the EUROMICRO Journal, v.51 n.6-7, p.405-423, June-July 2005

INDEX TERMS

Primary Classification:
G. Mathematics of Computing
G.2 DISCRETE MATHEMATICS

Additional Classification:
F. Theory of Computation
F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
F.2.2 Nonnumerical Algorithms and Problems
Subjects: Computations on discrete structures

General Terms:
Measurement, Performance, Theory, Verification

Adobe Acrobat

QuickTime

Windows Media Player

Real Player