Thumbnail
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

   Open content in new tab
Source: ACM Digital Library