Correcting Dependent Errors in Sequences Generated by Finite-State Processes

Abstract

A new channel model and “channel inversion algorithm” are presented for correcting symbol sequences that have been corrupted by an unknown combination of known fault mechanisms. The algorithm is similar to the Viterbi algorithm in that it is suitable for situations where the uncorrupted data string is generated by a known finite-state process, but it is more versatile in that it can correct a much broader class of errors. Of particular importance is the fact that our algorithm corrects common context-sensitive errors, such as symbol changes, transpositions, mergers, splits, insertions, and deletions, which may be assigned different probabilities depending on the context of preceeding and/or subsequent symbols. As many communication channels can be modeled in this way, this new algorithm is a significant extension over the Viterbi algorithm and previous decoding techniques. It may have many applications in such diverse fields as channel coding, pattern recognition, and estimation for discrete-event systems, whenever one has finite-state models and noisy data. This channel inversion algorithm can be understood in terms of a “quasi-trellis,” related to the trellis of the Viterbi Algorithm; it contains the same number of states, with a quasi-regular collection of arcs corresponding to user specified types of context-dependent errors. The notion of “channel rules” is introduced to provide a framework for the user to specify the channel operation. The algorithm is given in both an “off-line” form and a “recursive” form suitable for sequentially presented data streams. In most applications, the recursive form has computational complexity only a constant times that of the Viterbi Algorithm. © 1993, IEEE. All rights reserved.