Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
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
Matthias Kaiserswerth
IEEE/ACM Transactions on Networking
Yvonne Anne Pignolet, Stefan Schmid, et al.
Discrete Mathematics and Theoretical Computer Science
N.K. Ratha, A.K. Jain, et al.
Workshop CAMP 2000
M.J. Slattery, Joan L. Mitchell
IBM J. Res. Dev