Convolutional codes and their uses

Uses

Convolutional codes are forward error-correcting (FEC) codes used where retransmission is not possible or costly: deep-space and satellite links, GSM and 3G mobile (channel coding), Wi-Fi (802.11a/g), digital TV broadcasting (DVB), and as the inner code with Reed-Solomon. They are decoded with the Viterbi algorithm.

Concept

Unlike a block code, a convolutional code encodes the data continuously: each output depends on the present input bit and the previous K−1 bits stored in a shift register (memory). A code of rate k/n produces n output bits for every k input bits. Constraint length K = number of register stages + 1.

Example: rate 1/2, K = 3, with generators g1 = 111 and g2 = 101:

• Output 1 = b ⊕ s1 ⊕ s2
• Output 2 = b ⊕ s2

where b is the current bit and s1 s2 are the previous two bits.

 input b --+--->[s1]--->[s2]
           |     |       |
           +--(+)<-------+---> out1 = b+s1+s2
           +-------(+)<-+---> out2 = b+s2

State transition table

State = (s1 s2). Input b moves to state (b s1). Label: input / output.

State diagram (transitions, input/output)

 a --0/00--> a      a --1/11--> b
 b --0/10--> c      b --1/01--> d
 c --0/11--> a      c --1/00--> b
 d --0/01--> c      d --1/10--> d

Every state has exactly two outgoing arrows (one per input bit), and the number of states is 2^(K−1) = 4.

Example encoding

Input 1 0 1 1 followed by two flushing zeros (start 00):

Coded output: 11 10 00 01 01 11. The free distance of this code is 5, so Viterbi decoding can correct up to 2 errors in a short span of the stream.