ExcelEx
Perform Viterbi algorithm by Excel without using a VBA macro.†
Takashi Yamanoue, Fukuyama University, 9 Feb. 2016.†
- Finding out the most probable sequence of hidden states / Error correction of transmitted code using dynamic programming.
Abstract†
- 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.
Input†
- The automaton which transform the input sequence to the series of codes.
- The input sequence, a series of 0 or 1, at the transmitter side. This input needs for comparing this input and the result of this table. So this input is not used for finding out
the most probable input.
- The received series of codes which is received by the receiver.
Format of the Input†
- The area B16:F21 represents the automaton which perform the combolutional coding. In the example of Fig.1, the automaton represents the followings.
- When the current state was 00 and there was input 0, then output 00 and the next state is 00.
- When the current state was 00 and there was input 1, then output 11 and the next state is 01.
- when the current state was 01 and there was input 0, then output 01 and the next state is 10.
- when the current state was 01 and there was input 1, then output 10 and the next state is 11.
- when the current state was 10 and there was input 0, then output 11 and the next state is 00.
- when the current state was 10 and there was input 1, then output 00 and the next state is 01.
- when the current state was 11 and there was input 0, then output 10 and the next state is 10.
- when the current state was 11 and there was input 1, then output 01 and the next state is 11.
- The area C28:C36 represents the input, a binary sequence. In the example of Fig.1, the input is 0,1,0,0,0,1,0. There should be corresponding stage at column A.
- The area E28:E36 represents the sequence of code which represents the received codes by the receiver.
- The sequence may have errors.
- In the example of Fig.1, the sequence of code is 00,11,01,11,00,11,01,11,00. --- It is the copy of D28:D36. The sequence in the area of D28:D36 shows the sequence of output codes by the automaton.
- If the values in the area of E28:E36 are same as the values in the area of D28:D36, there was no error at the receiver side.
Output†
- The area BT28:BT36 shows the most probable input at the transmitter, estimated by Viterbi algorithm using the received codes and the automaton. In the example of Fig.1, the most probable input sequence is 0,1,0,0,0,1,0,0. It is the same as the input sequence at the transmitter.
- If change the received code 00 at the state 5 (E32) to 01, this means there was a error, the most probalbe input does not change.
Key expressions†
A27, A28 ... Stages†
- A27
0
- A28
=A27+1
- Copy A28 to A29:A36
B27, B28 ... State of the automaton at the stage.†
- B27
'00
- B28
=VLOOKUP(B27,$B$18:$D$21,IF(C27=0,2,3))
- Copy B28 to B29:B36
D27 ... output code†
=VLOOKUP(B27,$B$18:$F$21,IF(C27=0,4,5))
F28:U28 ...†
=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.
N13†
=IF(A13=1,0,MIN(J13:M13))
- Find out the minimal value from the previous nodes to this node.
- Copy this expression to the area of N13:N21.
O13†
=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
P13†
=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
Q13†
=IF(P13=0,"",IF(P13=1,"1-"&TEXT(A13,"#####"),VLOOKUP(P13,$A$13:$Q$21,17)&"-"&TEXT(A13,"#####")))
- Construct the minimal path from the start node to this node.
- Copy this expression to the area of Q13:Q21
References†
- Wikipedia Dynamic programming
- Dynamic programming from an excel perspective.
- Writing a program by Excel
- Writing codes for a programming contest by excel
Counter: 3449,
today: 2,
yesterday: 0
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
viterbi-2.xlsx
