Viterbi

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.

• 
  Fig. 1.
• The sheet... viterbi-2.xlsx

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 probable 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. [#tac67499]
  • 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))

• Copy D27 to D28:D36

F28:U28 †

• Previous states at each stage for cartesian product of current states and input. These show the Trellis Diagram.

  '00, '10, '-, '-, '-, '-, '00, '10, '01, '11, '-, '-, '-, '-, '01, '11,

• In the example of Fig. 1, 00 of F28 shows the previous state of the state 00 when there was input of 0, and 10 of G29 shows the previous state of the state 00 when there was input of 1.
• Copy F28:U28 to F29:U36
• Currently, these values are filled manually. I hope some one shows the expression which computes the values of this area from the automaton.

V28 †

• Output which is corresponding to the previous state at F28.

  =IF(F28="-","-",VLOOKUP(F28,$B$18:$F$21,IF(V$26=0,4,5)))

• In the example of Fig. 1, '00 of V28 shows the output which is corresponding to the previous state of F28, and '11 of W28 shows the output which is correspinding to the previous state of G28.
• Copy this expression to V28:AK36.

AL28 †

• Hamming distance between the received code and the output code of the V28.

  =IF(V28="-",100,IF(V28=$E28,0,IF(LEFT(V28,1)=LEFT($E28,1),1,IF(RIGHT(V28,1)=RIGHT($E28,1),1,2))))

• Copy this expression to AL28:BA36
• Value 100 means infinite.

BB28, BC28, BD28, BE28 †

• Minimal distance for each state.

  =MIN(AL28:AO28), =MIN(AP28:AS28), =MIN(AT28:AW28), =MIN(AX28:BA28)

• Copy BB28:BE28 to BB29:BE36

BF28, BG28, BH28, BI28 †

• Place of the presumed output in the previous states.

  =MATCH(BB28,AL28:AO28,0), =MATCH(BC28,AP28:AS28,0), =MATCH(BD28,AT28:AW28,0), =MATCH(BE28,AX28:BA28,0) 

• Copy BF28:BI28 to BF29:BI36

BJ28, BK28, BL28, BM28 †

• Minimal distance from the previous state.

  =INDEX(F28:I28,BF28), =INDEX(J28:M28,BG28), =INDEX(N28:Q28,BH28), =INDEX(R28:U28,BI28)

• Copy BJ28:BM28 to BJ29:BM36

BS28, BS36 †

• Estimated previous state. Backward chaining minimal distance states from the last stage. The state at the last stage must be 00.
  • BS28

    =HLOOKUP(BS29,$BJ$25:$BM$36,A28+3,FALSE)

  • Copy BS28 to BS29:BS35
  • BS36

    '00

References †

• http://www.hazymoon.jp/convolution/index.html
• Wikipedia Viterbi Algorithm
  • https://en.wikipedia.org/wiki/Viterbi_algorithm
• Wikipedia Dynamic programming
  • https://en.wikipedia.org/wiki/Dynamic_programming
• Dynamic programming from an excel perspective.
  • https://www.researchgate.net/publication/262281816_Dynamic_programming_from_an_excel_perspective
• Writing a program by Excel
  • http://lecture.ecc.u-tokyo.ac.jp/~shagiya/excel.pdf
• Writing codes for a programming contest by excel
  • http://d.hatena.ne.jp/kita_yuta/20111220/1324405195

address: http://www.yama-lab.org/~yamanoue/wiki/