A Caltech Library Service

Finite state codes and generalized De Bruijn sequences


Popovic, Lada (1991) Finite state codes and generalized De Bruijn sequences. Engineer's thesis, California Institute of Technology. doi:10.7907/21wf-wa45.


This thesis is divided into two self-contained chapters. The first chapter is a study of Finite State Codes. We address the question of unique decodability (UD) of the labelled state diagram which defines the finite state machine-part of the encoder for these codes. Bounds on the number of labels and resolving length are given for regular state diagrams. We show that minimal convolutional encoders can be used as finite state machines to produce UD labellings which are often optimal with respect to number of labels and resolving length. We finish with some constructions which demonstrate how block and convolutional codes can be integrated to obtain finite state codes of high rate and large free distance.

The second chapter introduces and analyzes a family of shift-register sequences which generalize the well-known de Bruijn sequences. A (q, v) de Bruijn sequence is a periodic sequence of letters from a q-ary alphabet such that any given v-tuple appears exactly once as a 'window' in a period. We introduce Generalized de Bruijn Sequences, which involve several sequences in parallel and an irregularly shaped window, plus the requirement that every possible window content should appear n times per period. The existence of such sequences is proved by construction, and a formula for their number is derived. The classical de Bruijn sequences can then be regarded as a special case of this new family.

Item Type:Thesis (Engineer's thesis)
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)
  • Kechris, Alexander S.
  • Posner, Edward C.
Defense Date:28 September 1990
Record Number:CaltechETD:etd-07092007-131600
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:2841
Deposited By: Imported from ETD-db
Deposited On:23 Jul 2007
Last Modified:16 Apr 2021 22:09

Thesis Files

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


Repository Staff Only: item control page