Dolinar, Sam and Ko, Tsz-Mei and McEliece, Robert J. (1992) VLSI decompositions for deBruijn graphs. In: Proceedings 1992 IEEE International Symposium on Circuits and Systems. IEEE , Piscataway, NJ, pp. 1855-1858. ISBN 0-7803-0593-0 http://resolver.caltech.edu/CaltechAUTHORS:20120328-130309049
- Published Version
See Usage Policy.
Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120328-130309049
A C-chip VLSI decomposition of a graph G is a collection of C isomorphic disjoint subgraphs of G (the building blocks), which together contain all of G's vertices. The efficiency of such a decomposition is defined to be the fraction of edges of G that are in the building block. Motivated by the need to construct large Viterbi decoders, the authors study VLSI decompositions of deBruijn graphs. They obtain some strong necessary conditions for a graph to be a building block for a deBruijn graph, and some slightly more restrictive sufficient conditions which allow the construction of some efficient building blocks for deBruijn graphs.
|Item Type:||Book Section|
|Additional Information:||© 1992 IEEE. The research described in this paper was partially carried out at the Jet Propulsion Laboratory, California Institute of Technology, under a contract with the National Aeronautics and Space Administration. Tsz-Mei Ko's contribution was also supported by National Security Agency Grant No. MDA904-90-H-1007. Robert McEliece's contribution was also supported by AFOSR grant 91-0037 and a grant from Pacific Bell.|
|Other Numbering System:|
|Official Citation:||Dolinar, S.; Ko, T.-M.; McEliece, R.; , "VLSI decompositions for deBruijn graphs," Circuits and Systems, 1992. ISCAS '92. Proceedings., 1992 IEEE International Symposium on , vol.4, no., pp.1855-1858 vol.4, 3-6 May 1992 doi: 10.1109/ISCAS.1992.230451 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=230451&isnumber=5938|
|Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Tony Diaz|
|Deposited On:||17 Apr 2012 21:31|
|Last Modified:||26 Dec 2012 15:00|
Repository Staff Only: item control page