Decoding for Channels with Insertions, Deletions, and Substitutions with Applications to Speech Recognition

Abstract

A model for channels in which an input sequence can produce output sequences of varying length is described. An efficient computational procedure for calculating Pr {Y|X} is devised, where X = Xt, X2,” • ‘,XM and Y = Yt, Y2,” • ·’YN are the input and output of the channel. A stack decoding algorithm for decoding on such channels is presented. The appropriate likelihood function is derived. Channels with memory are considered. Some applications to speech and character recognition are discussed. © 1975, IEEE. All rights reserved.