About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
IEEE Trans. Inf. Theory
Paper
Two Extensions of the Viterbi Algorithm
Abstract
The problem of minimum cost correction of a corrupted set of data that has been generated by a known finite state machine is examined. The Viterbi algorithm is modified to correct insertions and deletions as well as errors, still using a trellis diagram that has the same number of states as the FSM that generated the uncorrupted data. Two problems are examined. In the first problem the data is given in the traditional form of a string so the novel aspect is that insertions and deletions are now corrected. In the second problem, a unique string need not be given, but a regular language is given, and any string belonging to the regular language is a possible data string. Again, deletion of symbols, addition of symbols, and changes of symbols are corrected. A direct generalization of the Viterbi decoding algorithm is thus proved to be an efficient technique for solving a much wider class of problems. © 1991 IEEE