Convolutional codes are linear. Therefore, the Hamming distance between any pair of code sequences corresponds to the Hamming distance between the allzero code sequence and some nonzero code sequence. The nonzero sequence of minimum Hamming weight diverges from the allzero path at some point and remerges with the allzero path at some later point | Illustration of the TSP algorithm st 1 st 2 IEM UNI st 3 st 4 survivor Key idea Best path from A to C = best of - the path A-F-C - best path A to B + best path from B to C - the path via D does not influence the best way from B to C A B C D E F Viterbi algorithm the Viterbi algorithm is a standard component of tens of millions of high-speed modems. It is a key building block of modern information infrastructure The symbol "VA" is ubiquitous in the block diagrams of modern receivers. Essentially: the VA finds a path through any Markov graph, which is a sequence of states governed by a Markov chain. many practical applications: convolutional decoding and channel trellis decoding. fading communication channels, partial response channels in recording systems, optical character recognition, voice recognition. DNA sequence analysis etc. Application to convolutional code encoder VD channel Info code code + noise estimate binary noise sequences P(n1=1)=P(n2=1) = p I delay c1 c2 n1 n2 c1 n1 c2 n2 VITERBI DECODER: find sequence I‘ that corresponds to code sequence ( c1, c2 ) at minimum distance from (r1,r2) = (c1 n1, c2 n2) Use encoder state space (Trellis Diagram) I delay c2 00 01 11 10 State 0 State 1 Time 0 1 2 3 00 01 11 10 00 01 11 10 00 01 11 10 ••• 00 11 State 0 State 1 00 01 11 10 00 01 11 10 00 01 11 10 ••• 00 11 State 0 State 1 00 01 11 10 00 01 11 10 00 01 11 10 ••• Encoder output 00 11 10 00 channel output 00 10 10 00 0 2 1 1 1 2 1 3 best Viterbi Decoder action VITERBI DECODER: find sequence I‘ that corresponds to code sequence ( c1, c2 ) at minimum distance from ( r1, r2 ) = ( c1 n1, c2 n2 ) Maximum Likelihood receiver: find ( c1, c2 ) that maximizes Probability ( r1, r2 | c1, c2 ) = Prob ( c1 n1, c2 n2 | c1, c2 ) = = Prob ( n1, n2 ) = minimum # noise digits equal to 1 Distance Properties of Conv. Codes Def: The free distance, dfree, is the minimum Hamming . | Illustration of the TSP algorithm st 1 st 2 IEM UNI st 3 st 4 survivor Key idea Best path from A to C = best of - the path A-F-C - best path A to B + best path from B to C - the path via D does not influence the best way from B to C A B C D E F Viterbi algorithm the Viterbi algorithm is a standard component of tens of millions of high-speed modems. It is a key building block of modern information infrastructure The symbol "VA" is ubiquitous in the block diagrams of modern receivers. Essentially: the VA finds a path through any Markov graph, which is a sequence of states governed by a Markov chain. many practical applications: convolutional decoding and channel trellis decoding. fading communication channels, partial response channels in recording systems, optical character recognition, voice recognition. DNA sequence analysis etc. Application to convolutional code encoder VD channel Info code code + noise .
