A VLSI decomposition of the deBruijn graphA VLSI decomposition of the deBruijn graph

Access Restriction
Subscribed

 Author Collins, Oliver ♦ Dolinar, Sam ♦ McEliece, Robert ♦ Pollara, Fabrizio Source ACM Digital Library Content type Text Publisher Association for Computing Machinery (ACM) File Format PDF Copyright Year ©1992 Language English
 Subject Domain (in DDC) Computer science, information & general works ♦ Data processing & computer science Subject Keyword DeBruijn graphs ♦ Graph decomposition Abstract The deBruijn graph $\textit{Bn}$ is the state diagram for an $\textit{n}-stage$ binary shift register. It has $2\textit{n}$ vertices and $2\textit{n}$ + 1 edges. In this papers, it is shown that $\textit{Bn}$ can be built by appropriately “wiring together“ (i.e., connecting together with extra edges) many isomorphic copies of a fixed graph, which is called a building block for $\textit{Bn}.$ The efficiency of such a building block is refined as the fraction of the edges of $\textit{Bn}$ which are present in the copies of the building block. It is then shown, among other things, that for any α < 1, there exists a graph $\textit{G}$ which is a building block for $\textit{Bn}$ of efficiency > α for all sufficiently large $\textit{n}.$ These results are illustrated by describing how a special hierarchical family of building blocks has been used to construct a very large Viterbi decoder (whose floorplan is the graph $\textit{B13})$ which will be used on NASA's $\textit{Galileo}$ mission. ISSN 00045411 Age Range 18 to 22 years ♦ above 22 year Educational Use Research Education Level UG and PG Learning Resource Type Article Publisher Date 1992-10-01 Publisher Place New York e-ISSN 1557735X Journal Journal of the ACM (JACM) Volume Number 39 Issue Number 4 Page Count 18 Starting Page 931 Ending Page 948

Open content in new tab

Source: ACM Digital Library