Citation
Popovic, Lada (1991) Finite state codes and generalized De Bruijn sequences. Engineer's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd07092007131600
Abstract
This thesis is divided into two selfcontained 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 machinepart 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 shiftregister sequences which generalize the wellknown de Bruijn sequences. A (q, v) de Bruijn sequence is a periodic sequence of letters from a qary alphabet such that any given vtuple 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:  Restricted to Caltech community only 
Research Advisor(s): 

Thesis Committee: 

Defense Date:  28 September 1990 
Record Number:  CaltechETD:etd07092007131600 
Persistent URL:  http://resolver.caltech.edu/CaltechETD:etd07092007131600 
Default Usage Policy:  No commercial reproduction, distribution, display or performance rights in this work are provided. 
ID Code:  2841 
Collection:  CaltechTHESIS 
Deposited By:  Imported from ETDdb 
Deposited On:  23 Jul 2007 
Last Modified:  26 Dec 2012 02:54 
Thesis Files
PDF (Popovic_l_1991.pdf)
 Final Version
Restricted to Caltech community only See Usage Policy. 1618Kb 
Repository Staff Only: item control page