Popovic, Lada (1991) Finite state codes and generalized De Bruijn sequences. Engineer's thesis, California Institute of Technology. http://resolver.caltech.edu/CaltechETD:etd-07092007-131600
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:||Restricted to Caltech community only|
|Defense Date:||28 September 1990|
|Default Usage Policy:||No commercial reproduction, distribution, display or performance rights in this work are provided.|
|Deposited By:||Imported from ETD-db|
|Deposited On:||23 Jul 2007|
|Last Modified:||26 Dec 2012 02:54|
- Final Version
Restricted to Caltech community only
See Usage Policy.
Repository Staff Only: item control page