Viterbi
をテンプレートにして作成
[
トップ
] [
新規
|
一覧
|
検索
|
最終更新
|
ヘルプ
]
開始行:
[[ExcelEx]]
* Perform Viterbi algorithm by Excel without using a VBA ...
** Takashi Yamanoue, Fukuyama University, 9 Feb. 2016. [#...
- Finding out the most probable sequence of hidden states...
** Abstract [#n6db9015]
- In a communication system, which consists of a transmit...
the transmitter sends coded signals to the receiver.
- Coded signals are transformed from the input at the are...
into a series of codes at the area of D28:D36.
- This transformation is performed by the automaton at th...
- The receiver receives the signal as the series of codes...
- The received codes may have errors.
- The following table find out the most probable input as...
from the series of received codes and the automaton,
using the Viterbi algorithm.
- &ref(Viterbi/viterbi-2-img.jpg,50%); &br; Fig. 1.
- The sheet... &ref(Viterbi/viterbi-2.xlsx);
** Input [#f6744253]
- The automaton which transform the input sequence to the...
- The input sequence, a series of 0 or 1, at the transmit...
the most probable input.
- The received series of codes which is received by the r...
*** Format of the Input [#id6a75c1]
- The area B16:F21 represents the automaton which perform...
-- When the current state was 00 and there was input 0, t...
-- When the current state was 00 and there was input 1, t...
-- when the current state was 01 and there was input 0, t...
-- when the current state was 01 and there was input 1, t...
-- when the current state was 10 and there was input 0, t...
-- when the current state was 10 and there was input 1, t...
-- when the current state was 11 and there was input 0, t...
-- when the current state was 11 and there was input 1, t...
- The area C28:C36 represents the input, a binary sequenc...
- The area E28:E36 represents the sequence of code which ...
-- The sequence may have errors.
-- In the example of Fig.1, the sequence of code is 00,11...
-- If the values in the area of E28:E36 are same as the v...
** Output [#g3e710b2]
- The area BT28:BT36 shows the most probable input at the...
-- If change the received code 00 at the state 5 (E32) to...
** Key expressions [#s5d8268b]
*** A27, A28 [#ka2c47c5]
- Stages
-- A27
0
-- A28
=A27+1
- Copy A28 to A29:A36
*** B27, B28 [#bf13a672]
- 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 [#g65bcc06]
- output code
=VLOOKUP(B27,$B$18:$F$21,IF(C27=0,4,5))
- Copy D27 to D28:D36
*** F28:U28 [#fb7588a3]
- Previous states at each stage for cartesian product of ...
'00, '10, '-, '-, '-, '-, '00, '10, '01, '11, '-, '-, '-...
- In the example of Fig. 1, 00 of F28 shows the previous ...
- Copy F28:U28 to F29:U36
- Currently, these values are filled manually. I hope som...
*** V28 [#s1ba840e]
- Output which is corresponding to the previous state at...
=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 w...
- Copy this expression to V28:AK36.
*** AL28 [#z947b54c]
- Hamming distance between the received code and the outp...
=IF(V28="-",100,IF(V28=$E28,0,IF(LEFT(V28,1)=LEFT($E28,1...
- Copy this expression to AL28:BA36
- Value 100 means infinite.
*** BB28, BC28, BD28, BE28 [#f80fec5c]
- Minimal distance for each state.
=MIN(AL28:AO28), =MIN(AP28:AS28), =MIN(AT28:AW28), =MIN(...
- Copy BB28:BE28 to BB29:BE36
*** BF28, BG28, BH28, BI28 [#ff6da91e]
- Place of the presumed output in the previous states.
=MATCH(BB28,AL28:AO28,0), =MATCH(BC28,AP28:AS28,0), =MAT...
- Copy BF28:BI28 to BF29:BI36
*** BJ28, BK28, BL28, BM28 [#ie9854d7]
- Minimal distance from the previous state.
=INDEX(F28:I28,BF28), =INDEX(J28:M28,BG28), =INDEX(N28:Q...
- Copy BJ28:BM28 to BJ29:BM36
*** BS28, BS36 [#yb136996]
- Estimated previous state. Backward chaining minimal dis...
-- BS28
=HLOOKUP(BS29,$BJ$25:$BM$36,A28+3,FALSE)
-- Copy BS28 to BS29:BS35
-- BS36
'00
** References [#lfb15418]
- 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_Dyn...
- 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
----
#counter
----
address: https://www2.yama-lab.org/~yamanoue/wiki/
終了行:
[[ExcelEx]]
* Perform Viterbi algorithm by Excel without using a VBA ...
** Takashi Yamanoue, Fukuyama University, 9 Feb. 2016. [#...
- Finding out the most probable sequence of hidden states...
** Abstract [#n6db9015]
- In a communication system, which consists of a transmit...
the transmitter sends coded signals to the receiver.
- Coded signals are transformed from the input at the are...
into a series of codes at the area of D28:D36.
- This transformation is performed by the automaton at th...
- The receiver receives the signal as the series of codes...
- The received codes may have errors.
- The following table find out the most probable input as...
from the series of received codes and the automaton,
using the Viterbi algorithm.
- &ref(Viterbi/viterbi-2-img.jpg,50%); &br; Fig. 1.
- The sheet... &ref(Viterbi/viterbi-2.xlsx);
** Input [#f6744253]
- The automaton which transform the input sequence to the...
- The input sequence, a series of 0 or 1, at the transmit...
the most probable input.
- The received series of codes which is received by the r...
*** Format of the Input [#id6a75c1]
- The area B16:F21 represents the automaton which perform...
-- When the current state was 00 and there was input 0, t...
-- When the current state was 00 and there was input 1, t...
-- when the current state was 01 and there was input 0, t...
-- when the current state was 01 and there was input 1, t...
-- when the current state was 10 and there was input 0, t...
-- when the current state was 10 and there was input 1, t...
-- when the current state was 11 and there was input 0, t...
-- when the current state was 11 and there was input 1, t...
- The area C28:C36 represents the input, a binary sequenc...
- The area E28:E36 represents the sequence of code which ...
-- The sequence may have errors.
-- In the example of Fig.1, the sequence of code is 00,11...
-- If the values in the area of E28:E36 are same as the v...
** Output [#g3e710b2]
- The area BT28:BT36 shows the most probable input at the...
-- If change the received code 00 at the state 5 (E32) to...
** Key expressions [#s5d8268b]
*** A27, A28 [#ka2c47c5]
- Stages
-- A27
0
-- A28
=A27+1
- Copy A28 to A29:A36
*** B27, B28 [#bf13a672]
- 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 [#g65bcc06]
- output code
=VLOOKUP(B27,$B$18:$F$21,IF(C27=0,4,5))
- Copy D27 to D28:D36
*** F28:U28 [#fb7588a3]
- Previous states at each stage for cartesian product of ...
'00, '10, '-, '-, '-, '-, '00, '10, '01, '11, '-, '-, '-...
- In the example of Fig. 1, 00 of F28 shows the previous ...
- Copy F28:U28 to F29:U36
- Currently, these values are filled manually. I hope som...
*** V28 [#s1ba840e]
- Output which is corresponding to the previous state at...
=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 w...
- Copy this expression to V28:AK36.
*** AL28 [#z947b54c]
- Hamming distance between the received code and the outp...
=IF(V28="-",100,IF(V28=$E28,0,IF(LEFT(V28,1)=LEFT($E28,1...
- Copy this expression to AL28:BA36
- Value 100 means infinite.
*** BB28, BC28, BD28, BE28 [#f80fec5c]
- Minimal distance for each state.
=MIN(AL28:AO28), =MIN(AP28:AS28), =MIN(AT28:AW28), =MIN(...
- Copy BB28:BE28 to BB29:BE36
*** BF28, BG28, BH28, BI28 [#ff6da91e]
- Place of the presumed output in the previous states.
=MATCH(BB28,AL28:AO28,0), =MATCH(BC28,AP28:AS28,0), =MAT...
- Copy BF28:BI28 to BF29:BI36
*** BJ28, BK28, BL28, BM28 [#ie9854d7]
- Minimal distance from the previous state.
=INDEX(F28:I28,BF28), =INDEX(J28:M28,BG28), =INDEX(N28:Q...
- Copy BJ28:BM28 to BJ29:BM36
*** BS28, BS36 [#yb136996]
- Estimated previous state. Backward chaining minimal dis...
-- BS28
=HLOOKUP(BS29,$BJ$25:$BM$36,A28+3,FALSE)
-- Copy BS28 to BS29:BS35
-- BS36
'00
** References [#lfb15418]
- 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_Dyn...
- 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
----
#counter
----
address: https://www2.yama-lab.org/~yamanoue/wiki/
ページ名:
![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
