Menu
Home
People
Places
Arts
History
Plants & Animals
Science
Life & Culture
Technology
Reference.org
Iterative Viterbi decoding
open-in-new
<p>Iterative Viterbi decoding is an <a href="/facts/Algorithm/fnl5NmRt">algorithm</a> that spots the subsequence <i>S</i> of an observation <i>O</i> = {<i>o</i>1, ..., <i>o</i><i>n</i>} having the highest average probability (i.e., probability scaled by the length of <i>S</i>) of being generated by a given <a href="/facts/Hidden_Markov_model/ur1zTAhP">hidden Markov model</a> <i>M</i> with <i>m</i> states. The algorithm uses a modified <a href="/facts/Viterbi_algorithm/FYoyJ6YY">Viterbi algorithm</a> as an internal step. </p><p>The scaled probability measure was first proposed by John S. Bridle. An early algorithm to solve this problem, <a href="/facts/Sliding_window/TvkveH2L">sliding window</a>, was proposed by Jay G. Wilpon et al., 1989, with constant cost <i>T</i> = <i>mn</i>2/2. </p><p>A faster algorithm consists of an iteration of calls to the <a href="/facts/Viterbi_algorithm/FYoyJ6YY">Viterbi algorithm</a>, reestimating a filler score until convergence. </p>