Date of Award


Degree Type


Degree Name

Doctor of Philosophy


The classical theory of error correcting codes investigates methods for correcting substitution errors in information messages and uses mainly block codes, that is, codes all the words of which have the same length. This thesis introduces a general framework for studying the notions of error correction and decodability for arbitrary channels and for variable length codes.;First, a general definition of channel is given and a large class of channels, the SID channels, is defined for modeling substitutions, insertions, and deletions of symbols in information messages. The algebraic properties of SID channels are investigated which lead to the notion of normal form for SID channels. Next, for a general channel, the definition of (variable length) error correcting code is given. Several examples are provided and the decidability of error correction is shown for any given SID channel and finite code. Finally, the behaviour of a certain class of codes with the deletion channel is analysed which leads to the construction of deletion-correcting codes of variable length.



To view the content in your browser, please download Adobe Reader or, alternately,
you may Download the file to your hard drive.

NOTE: The latest versions of Adobe Reader do not support viewing PDF files within Firefox on Mac OS and if you are using a modern (Intel) Mac, there is no official plugin for viewing PDF files within the browser window.