Finite state codes and generalized De Bruijn sequences

Citation

Popovic, Lada (1991) Finite state codes and generalized De Bruijn sequences. Engineer's thesis, California Institute of Technology. doi:10.7907/21wf-wa45. https://resolver.caltech.edu/CaltechETD:etd-07092007-131600

Abstract

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.

Thesis Files