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
![[img]](https://authors.library.caltech.edu/style/images/fileicons/application_pdf.png)
|
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
