Part One


Complete Viterbi Table (including last column)

end     0.0000  0.0000  0.0000  0.0000
H       0.0000  0.3200  0.0448  0.0125
C       0.0000  0.0200  0.0480  0.0029
start   1.0000  0.0000  0.0000  0.0000

 t=       0       1        2      3

v3(2)  = .0125
since
max { path-prob2(1,2), path-prob2(2,2) } = max { 0.0480 * .4 * .4, 0.0448 * .7 * .4 } = .0125

Last state visited on best path: state 2 (H).  Add a backtrace link (dashed
line) to the backtrace figure going from H at time t=3 to H at time
t = 2.

v3(1) = .0029
since
max { path-prob2(1,1), path-prob2(2,1) } = max { 0.0480 * .6 * .1 , 0.0448 * .3 *.1 } = .0029

Last state visited on best path: state 1 (C)

So the best path overall ends at H at t=3 (0.125 > .0029), and that
was reached on a path that visited H at t=2.  Looking at our back
trace diagram to complete the best path, we see that the best way to
reach H at t=2 also goes through H, so we get as our best oath:

Best path: start H H H

Part Two

Explaining the tables will require referring to them
by numerical indices.  Rows come first, then columns.
Rows correspond to states, columns to input observations.
So the state (row) indices are s = 0, t = 1, h =2 , e =3.
The observation (column) indices are times of observations,
so at t=0 we are observing nothing, at t=1 T, at t=2, H,
at t=3 T, and T=4, end.  The viterbi value at cell [1,2]
is 0.02560; that means the path probability of the best
path that reach state 1 (t) at time 2 is 0.02560.

Viterbi Table

s         1.00000  0.00000  0.00000  0.00000  0.00000
t         0.00000  0.32000  0.02560  0.02765  0.00000
h         0.00000  0.06000  0.08640  0.00432  0.00000
e         0.00000  0.00000  0.00000  0.00000  0.00829
                         T        H        T      end

Backtrace Table

s              -1       -1       -1       -1       -1
t              -1        0        1        2       -1
h              -1        0        1        2       -1
e              -1       -1       -1       -1        1
                         T        H        T      end

Backtrace table interpretation: A positive value in cell i,t is the
index of the next-to-last state on the best path that ends at cell
i at time t. For example, the 2 at cell 1,3 [state 1 (= state t), time
t=3, ] means the best path arriving at state t at time t=3 went
through state 2 (= h) at time t=2.  The two 0's in the t = 1 column
mean that the best paths to states 1 and 2 at time t = 1 both went
through state 0 (= start state "s") at t = 0.  A negative value in the
backtrace table in cell i, t indicates no path at time t-1
could be extended to a path ending in state i at time t with a positive
Viterbi value.  Since no path can arrive at "s" at any time,
the entire top row has negative values. Since there are no paths at
time t = -1 to extend, the entire t=0 column has negative values.

We assume the last state visited is e, so we start with a best path
that ends:

e

We construct our best path working backward from there. 
At time t = 4, state = e (cell [3,4] in the backtrace table),
our backtrace value is 1 (=state t).  So our best path now ends

t e

We continue constructing th ebacktrace backward until we have the
complete best path:

s  t  h  t  e 

Here are the Viterbi calculations:


V1(1) = max(0.80000 * 1.00000 * 0.40000,0.80000 * 0.00000 * 0.40000,0.80000 * 0.00000 * 0.40000,0.80000 * 0.00000 * 0.00000)
V1(1) = max(0.32000,0.00000,0.00000,0.00000)
V1(1) = 0.32

V1(2) = max(0.10000 * 1.00000 * 0.60000,0.10000 * 0.00000 * 0.30000,0.10000 * 0.00000 * 0.50000,0.10000 * 0.00000 * 0.00000)
V1(2) = max(0.06000,0.00000,0.00000,0.00000)
V1(2) = 0.06

V2(1) = max(0.20000 * 0.00000 * 0.40000,0.20000 * 0.32000 * 0.40000,0.20000 * 0.06000 * 0.40000,0.20000 * 0.00000 * 0.00000)
V2(1) = max(0.00000,0.02560,0.00480,0.00000)
V2(1) = 0.0256

V2(2) = max(0.90000 * 0.00000 * 0.60000,0.90000 * 0.32000 * 0.30000,0.90000 * 0.06000 * 0.50000,0.90000 * 0.00000 * 0.00000)
V2(2) = max(0.00000,0.08640,0.02700,0.00000)
V2(2) = 0.0864

V3(1) = max(0.80000 * 0.00000 * 0.40000,0.80000 * 0.02560 * 0.40000,0.80000 * 0.08640 * 0.40000,0.80000 * 0.00000 * 0.00000)
V3(1) = max(0.00000,0.00819,0.02765,0.00000)
V3(1) = 0.027648

V3(2) = max(0.10000 * 0.00000 * 0.60000,0.10000 * 0.02560 * 0.30000,0.10000 * 0.08640 * 0.50000,0.10000 * 0.00000 * 0.00000)
V3(2) = max(0.00000,0.00077,0.00432,0.00000)
V3(2) = 0.00432

V4(3) = max(1.00000 * 0.00000 * 0.00000,1.00000 * 0.02765 * 0.30000,1.00000 * 0.00432 * 0.10000,1.00000 * 0.00000 * 0.00000)
V4(3) = max(0.00000,0.00830,0.00043,0.00000)
V4(3) = 0.008295

>>>