Trellis decoding of 1/2 rate conv. code (2-bit errors)

Code used

Rate 1/2, 4-state (K = 3) convolutional code, g1 = 111, g2 = 101. States: a = 00, b = 10, c = 01, d = 11 (state = s1 s2; next state = (input, s1)).

Transmitted and received data

Message 1 0 1 1 plus tail 0 0:

• transmitted: 11 10 00 01 01 11
• received (2 bit errors, in steps 2 and 5): 11 00 00 01 11 11

Viterbi decoding on the trellis

Each branch gets a metric equal to the Hamming distance between the received pair and the branch output. The decoder adds metrics along each path and keeps only the lowest metric (survivor) at every state.

 time :  t0   t1   t2   t3   t4   t5   t6
 rx   :       11   00   00   01   11   11
 a    :  0*    2    2    2    3    2    2*
 b    :   -    0*   4    1*   3    3    2
 c    :   -    -    1*   2    2    2*   3
 d    :   -    -    1    2    1*   2    3
 (number = accumulated error count, * = survivor path)

Example (t2): state c is reached from b by input 0 (output 10, received 00, distance 1) with total 0 + 1 = 1.

Traceback

The code ends in state a with total metric 2, which means two bit errors. Following survivors backwards:

a ← c ← d ← b ← c ← b ← a

The path is a → b → c → b → d → c → a with inputs 1, 0, 1, 1, 0, 0, and outputs 11 10 00 01 01 11, which is the transmitted sequence.

Decoded message = 1 0 1 1 (tail 00). Both errors (step 2: 00 received instead of 10; step 5: 11 received instead of 01) are corrected.

Since d_free = 5, any pattern of 2 bit errors in the stream is corrected.