A Caltech Library Service

On the VLSI decompositions for complete graphs, DeBruijn graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs


Ko, Tsz-Mei (1993) On the VLSI decompositions for complete graphs, DeBruijn graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/s7w7-a995.


A C-chip VLSI decomposition of a graph G is a collection of C vertex-disjoint subgraphs of G which together contain all of G's vertices and a subset of its edges. If the vertex-disjoint subgraphs are isomorphic to each other, we call one of these isomorphic subgraphs a building block. The efficiency of a VLSI decomposition is defined to be the fraction of edges of G that are in the subgraphs. In this thesis, motivated by the need to construct large Viterbi decoders, we study VLSI decompositions for deBruijn graphs. We 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 us to construct some efficient building blocks for deBruijn graphs. By using the methods described in this thesis, we have found a 64-chip VLSI decomposition of the deBruijn graph B13 with efficiency 0.754. This decomposition is being used by JPL design engineers to build a single-board Viterbi decoder for the K = 15, rate 1/4 convolutional code which will be used on NASA's Galileo mission.

Furthermore, we study VLSI decompositions for the families of complete graphs, hypercubes, hyperplanes, meshes, and shuffle-exchange graphs. In each of these cases, we obtain very efficient or even optimal decompositions. We also prove several general theorems that can be applied to obtain bounds on the efficiencies for VLSI decompositions of other complex graphs. In general, the results presented in this thesis are useful for implementing massively parallel computers.

Item Type:Thesis (Dissertation (Ph.D.))
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Electrical Engineering
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • McEliece, Robert J.
Thesis Committee:
  • McEliece, Robert J. (chair)
  • Martin, Alain J.
  • Seitz, Charles L.
  • Posner, Edward C.
  • Abu-Mostafa, Yaser S.
Defense Date:3 August 1992
Record Number:CaltechETD:etd-08302007-094049
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3284
Deposited By: Imported from ETD-db
Deposited On:31 Aug 2007
Last Modified:16 Apr 2021 22:57

Thesis Files

PDF (Ko_tm_1993.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page