Iterative Viterbi decoding: Difference between revisions

Revision as of 04:44, 3 December 2004

Revision as of 20:19, 3 December 2004

Line 3:

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

A faster algorithm was developed by Silaghi in 19891998 (published 1999). It consists of an iteration of calls to the [[Viterbi algorithm]], reestimating a filler score until convergence.

== The Algorithm ==

Line 11:

<pre>

(int, int, int) SilaghiBridleDistance(char s[1..n], char t[1..m], int d[1..n,1..m]) {

declare int s'[0..(n+1)] // thesethe following structures replicate the parameters and

declare int d'[1..n,0..(m+1)] //

// are not normally needed in an optimized implementation

declare int s'[0..(n+1)] // these structures replicate the parameters and

declare int td'[1..n,0..(m+1)] // are not normally needed as such

declare int e,s'[0..(n+1)] B, E // score, subsequence start, subsequence end

declare int dt'[1..n,0..(m+1)] //

for j := 1 to m // initialize data structure (can be optimized out)

// score, subsequence start, subsequence end

declare int e, B, E

for j := 1 to m // initialize datacopies of structureparameters (can be optimized out)

for j := 1 to m

t'[j] := t[j]

for i := 1 to n

d'[i,j] := d[i,j]

for i := 1 to n do s'[i] := s'[i] := e

t'[0] := t'[m+1] := s'[0] := s'[n+1] := 'e'

// now the algorithm

e := random()

do

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

(e, B, E) := ViterbiDistance(s', t', d')/(E-B+1)

until (convergence)

return (e, B, E)