Published May 1992
| Published
Book Section - Chapter
Open
VLSI decompositions for deBruijn graphs
- Creators
- Dolinar, Sam
- Ko, Tsz-Mei
- McEliece, Robert J.
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.
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.Attached Files
Published - DOLiscas92.pdf
Files
DOLiscas92.pdf
Files
(320.3 kB)
| Name | Size | Download all |
|---|---|---|
|
md5:5d9bddbbd240e2d4b0b3f9609638f6af
|
320.3 kB | Preview Download |
Additional details
- Eprint ID
- 29881
- Resolver ID
- CaltechAUTHORS:20120328-130309049
- MDA904-90-H-1007
- National Security Agency
- 91-0037
- Air Force Office of Scientific Research (AFOSR)
- Pacific Bell
- Created
-
2012-04-17Created from EPrint's datestamp field
- Updated
-
2021-11-09Created from EPrint's last_modified field
- Other Numbering System Name
- INSPEC Accession Number
- Other Numbering System Identifier
- 4407484