Date of Award
1996
Degree Type
Dissertation
Degree Name
Doctor of Philosophy
Abstract
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.
Recommended Citation
Konstantinidis, Stavros, "Error Correction And Decodability" (1996). Digitized Theses. 2617.
https://ir.lib.uwo.ca/digitizedtheses/2617