A VLSI decomposition of the deBruijn graph

Abstract

The deBruijn graph B n is the state diagram for an n -stage binary shift register. It has 2 n vertices and 2 n + 1 edges. In this papers, it is shown that B n 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 B n . The efficiency of such a building block is refined as the fraction of the edges of B n 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 G which is a building block for B n of efficiency > α for all sufficiently large 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 B 13 ) which will be used on NASA's Galileo mission.