Viterbi の履歴(No.2)

Perform Viterbi algorithm by Excel without using a VBA macro.†

Finding out the most probable sequence of hidden states / Error correction of transmitted code using dynamic programming.

In a communication system, which consists of a transmitter and a receiver, the transmitter sends coded signals to the receiver.
Coded signals are transformed from the input at the area of C28:C36, into a series of codes at the area of D28:D36.
This transformation is performed by the automaton at the area of B16:F21.
The receiver receives the signal as the series of codes at the area of E28:E36.
The received codes may have errors.
The following table find out the most probable input as the area at BT28:BT36, from the series of received codes and the automaton, using the Viterbi algorithm.

Node IDs. Each node ID is represented by a number. The start node ID should be 1. Node IDs should be sorted.
- Each line represent one node.
Previous nodes for each node. The maximum number of previous nodes should be 4.
Arc values from the previous nodes*. 1000 (represents infinite) is assigned when there is no corresponding arc.

The cell A13 represents a node ID. The ID is one. So this node is the start node.
The cell A19 represents the node, the ID of which is 7. Previous nodes of this node (7) are 4 and 5. They are shown by the cell B19 and C19. The arc value from the node 4 to this node(7) is 10, which is shown by the cell F19. The arc value from the node 5 to this node is 4, which is shown by the cell G19.

=IF(B13<>0,VLOOKUP(B13,$A$13:$N$21,14)+F13,1000)

Calculate the sum of, the arc value (this value) between this node and the previous node, and the value of the previous node which shows the minimal value from the start node to the previous node.
Copy this expression to the area of J13:M21.

=IF(A13=1,0,MIN(J13:M13))

=IF(N13=0,0,MATCH(N13,J13:M13))

Find out the previous arc which minimize the value. It is the selected arc. The arc is identified by the place between J*:M*. When the arc is in the column of J*, it is the 1st arc. When the arc is in the column M*, it is the 4th arc.
Copy this expression to the area of O13:O21

=IF(O13=0,0,INDEX(B13:E13,1,O13))

Find out the previous node (selected node) which minimizes the total value from the start node to this node.
Copy this expression to the area of P13:P21

=IF(P13=0,"",IF(P13=1,"1-"&TEXT(A13,"#####"),VLOOKUP(P13,$A$13:$Q$21,17)&"-"&TEXT(A13,"#####")))

Counter: 2885, today: 2, yesterday: 0