Page 136 - Classification Parameter Estimation & State Estimation An Engg Approach Using MATLAB

DISCRETE STATE VARIABLES 125

The value of x(i) that maximizes P(x(0), .. . , x(i), x(i þ 1), Z(i þ 1)) is a
function of x(i þ 1):

^ x xðijxði þ 1ÞÞ ¼ arg max P t ðxði þ 1ÞjxðiÞÞ
xðiÞ

max fPðxð0Þ; ;:xði 1Þ; xðiÞ; ZðiÞÞg
xð0Þ; ; xði 1Þ
ð4:70Þ
The so-called Viterbi algorithm uses the recursive equation in (4.69) and
the corresponding optimal state dependency expressed in (4.70) to find
the optimal path. For that, we define the array Q(i, x(i)) ¼
max x(0),..., x(i 1) fP(x(0), ... , x(i 1), x(i), Z(i))g.

Algorithm 4.3: The Viterbi algorithm

1. Initialization:

for xð0Þ¼ 1; ; K
Qð0; xð0ÞÞ ¼ P 0 ðxð0ÞÞP z zð0Þjxð0Þð Þ
Rð0; xð0ÞÞ ¼ 0

2. Recursion:

for i ¼ 2; ; I and xðiÞ¼ 1; ; K
ð
f
ð
Qi; xðiÞÞ ¼ max Qi 1; xði 1ÞP t xðiÞjxði 1Þðð ÞÞgP z zðiÞjxðiÞÞ
xði 1Þ
f
Ri; xðiÞÞ ¼ max Qi 1; xði 1ÞP t xðiÞjxði 1Þðð ÞÞg
ð
xði 1Þ
3. Termination:
P ¼ max QðI; xðIÞÞg
f
xðIÞ

x
f
^ xðI IÞ¼ arg max QðI; xðIÞÞg

xðIÞ
4. Backtracking:
for i ¼ I 1; I 2; ; 0
x
x
^ xðijIÞ¼ Ri þ 1; ^ xði þ 1; IÞÞ
ð