Carleton University
Technical Report TR-224
June 1993
A consistent model for noisy channels permitting arbitrarily distributed substitutions, insertions and deletions
Abstract
In this paper we present a new model for noisy channels which permit arbitrarily distributed substitution, deletion and insertion errors. Apart from its straightforward applications in string generation and recognition, the model also has potential applications in speech and uni-dimensional signal processing. The model is specified in terms of a noisy string generation technique. Let A be any finite alphabet and A* be the set of words over A. Given any arbitrary string U e A*, we specify a stochastically consistent scheme by which this word can be transformed into any Y e A*. This is achieved by specifying the process by which U is transformed by performing substitution, deletion and insertion operations. The scheme is shown to be Functionally Complete and stochastically consistent. The probability distributions for these respective operations can be completely arbitrary. Apart from presenting the channel in which all the possible strings in A* can be potentially generated, we also specify a technique by which Pr[YIU], the probability of receiving Y given that U was transmitted, can be computed in cubic time. This procedure involves dynamic programming, and is to our knowledge, among the few non-trivial applications of dynamic programming which evaluate quantities involving relatively complex combinatorial expressions and which simultaneously maintain rigid probability consistency constraints.