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. https://resolver.caltech.edu/CaltechAUTHORS:20120328-130309049
![]()
|
PDF
- Published Version
See Usage Policy. 320kB |
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20120328-130309049
Abstract
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 | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| |||||||||
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. | |||||||||
Funders: |
| |||||||||
Other Numbering System: |
| |||||||||
DOI: | 10.1109/ISCAS.1992.230451 | |||||||||
Record Number: | CaltechAUTHORS:20120328-130309049 | |||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20120328-130309049 | |||||||||
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. | |||||||||
ID Code: | 29881 | |||||||||
Collection: | CaltechAUTHORS | |||||||||
Deposited By: | Tony Diaz | |||||||||
Deposited On: | 17 Apr 2012 21:31 | |||||||||
Last Modified: | 09 Nov 2021 19:31 |
Repository Staff Only: item control page