Two Extensions of the Viterbi Algorithm

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