An algebra of discrete channels that involve combinations of three basic error types
Recently, the author introduced a nonprobabilistic mathematical model of discrete channels, thc BEE channels, that involve the error-types substitution, insertion, and deletion. This paper defines an important class of BEE channels, the SID channels, which include channels that permit a bounded number of scattered errors and, possibly at the same time, a bounded burst of errors in any segment of predefined length of a message. A formal syntax is defined fur generating channel expressions. and appropriate semantics is provided fur interpreting a given channel expression as a communication channel (SID channel) that permits combinations of substitutions, insertions, and deletions of symbols. Our framework permits one to generalize notions such as error correction and unique decodability. and express statements of the form "The code K can correct all errors of type xi" and "it is decidable whether the code K is uniquely decodable for the channel described by xi," where xi is any SID channel expression. (C) 2001 Academic Press.
channel error substitution insertion deletion error correction unique decodability code decidable