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

Code used

Rate 1/2, 4-state convolutional code (K = 3) with generators g1 = 111, g2 = 101. State = (s1 s2): a = 00, b = 10, c = 01, d = 11. Next state is (b, s1).

Transmitted data

Message 1 0 1 1 0 plus tail 0 0 (7 steps, return to state a): transmitted: 11 10 00 01 01 11 00

Received, with 3 bit errors (one each in steps 2, 4 and 6): received: 11 00 00 00 01 01 00

Trellis and Viterbi decoding (hard decision)

Branch metric = Hamming distance between received pair and branch output. At each state keep only the survivor with the lowest accumulated metric. Accumulated metrics:

(Rows show the best metric reaching each state after each received pair; ties are broken arbitrarily.)

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

Traceback

Start at state a at t7 (metric 3 = number of errors corrected) and follow the survivors backwards: a(t7) ← a(t6) ← c(t5) ← d(t4) ← b(t3) ← c(t2) ← b(t1) ← a(t0).

Path: a → b → c → b → d → c → a → a with inputs 1, 0, 1, 1, 0, 0, 0 and outputs 11 10 00 01 01 11 00.

Decoded message = 1 0 1 1 0 (tail 00), identical to the transmitted one. The path differs from the received sequence in exactly 3 bits, which are the 3 errors corrected.

Because d_free = 5, any 2 errors are always corrected; 3 errors are corrected when they are spread apart as here (more than a constraint length apart). Three errors packed close together could cause a wrong decision.