Iterative Viterbi decoding: Difference between revisions

Revision as of 22:05, 13 April 2006

Latest revision as of 13:00, 1 December 2020

(15 intermediate revisions by 11 users not shown)

Line 1:

'''Iterative Viterbi Decodingdecoding''' is an [[algorithm]] that spots the subsequence ''S'' of an observation ''O'' = {''o''₁, ..., ''o''_''n''} having the highest average probability (i.e., probability scaled by the length of ''S'') of being generated by a given [[hidden Markov model]] ''M'' with ''m'' states. The algorithm uses a modified [[Viterbi algorithm]] as an internal step.

The scaled probability measure was first proposed by [[John S. Bridle]]. An early algorithm to solve this problem, [[sliding window]], was proposed by [[Jay G. Wilpon]] et al., 1989, with constant cost ''T'' = ''mn''²/2.

A faster algorithm consists of an iteration of calls to the [[Viterbi algorithm]], reestimating a filler score until convergence.

Line 7:

== The algorithm ==

A basic (non-optimized) version, finding the sequence ''s'' with the smallest normalized distance from some subsequence of ''t'' is:

<pre>

// input is placed in observation s[1..n], template t[1..m],

// and [[distance matrix]] d[1..n,1..m]

// remaining elements in matrices are solely for internal computations

(int, int, int) AverageSubmatchDistance(char s[0..(n+1)], char t[0..(m+1)], int d[1..n,0..(m+1)]) {

Line 20:

e := random()

do

e' := e

for i := 1 to n do d'[i,0] := d'[i,m+1] := e

(e, B, E) := ViterbiDistance(s', t', d')

e := e/(E-B+1)

until (e == e')

Line 30:

</pre>

The ViterbiDistance() procedure returns the tuple (''e'', ''B'', ''E''), i.e., the Viterbi score "''e''" for the match of ''t'' and the selected entry (''B'') and exit (''E'') points from it. "''B''" and "''E''" have to be recorded using a simple modification to Viterbi.

A modification that can be applied to CYK tables, proposed by Antoine Rozenknop, consists in subtracting ''e'' from all elements of the initial matrix ''d''.

== References ==

* Silaghi, M., "Spotting Subsequences matching a HMM using the Average Observation Probability Criteria with application to Keyword Spotting", AAAI, 2005.

* Rozenknop, Antoine, and Silaghi, Marius; "Algorithme de decodagedécodage de treillis selon le criterecritère de coutcoût moyen pour la reconnaissance de la parole", TALN 2001.

==Further reading==

*{{cite conference |title=An Efficient Code Structure of Block Coded Modulations with Iterative Viterbi Decoding Algorithm |last1=Li |first1=Huan-Bang |last2=Kohno |first2=Ryuji |date=2006 |publisher=IEEE |___location=Valencia, Spain |conference=3rd International Symposium on Wireless Communication Systems |isbn=978-1-4244-0397-4 |doi=10.1109/ISWCS.2006.4362391}}

*{{cite journal|last1=Wang |first1=Qi |last2=Wei |first2=Lei |last3=Kennedy |first3=R.A. |title=Iterative Viterbi decoding, trellis shaping, and multilevel structure for high-rate parity-concatenated TCM |journal=IEEE Transactions on Communications |volume=50 |number=1 |date=January 2002 |pages=48–55 |issn=0090-6778 |doi=10.1109/26.975743 }}

[[Category:Error detection and correction]]

[[Category:Markov models]]