Hamming distance and weight; rate 1/3 convolutional encoder

Hamming weight and distance

• Hamming weight $w(\mathbf{c})$: number of 1s in a code vector. $w(1101001)=4$.
• Hamming distance $d(\mathbf{c}_1,\mathbf{c}_2)$: number of positions in which two vectors differ, $=w(\mathbf{c}_1\oplus\mathbf{c}_2)$. $d(1101001,1001011)=w(0100010)=2$.

The minimum distance $d_{min}$ of a code sets its error-control power: it detects up to $d_{min}-1$ errors and corrects up to $\lfloor(d_{min}-1)/2\rfloor$ errors.

Rate-1/3 convolutional encoder

A rate-1/3 convolutional encoder produces 3 output bits for every input bit. It uses a shift register of length $K$ (constraint length), three modulo-2 adders and a commutator. Example with $K=3$ and generators $g^{(1)}=100$, $g^{(2)}=101$, $g^{(3)}=111$:

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |           |           |
        +-----------------------------> c1 = mi
        +----(+)----------------+-----> c2 = mi+mi-2
        +----(+)----+----(+)----+-----> c3 = mi+mi-1+mi-2
           commutator reads c1, c2, c3 in turn

Operation:

1. The register starts cleared (00).
2. A message bit enters stage 1; older bits shift right.
3. Each adder forms the mod-2 sum of the stages connected to it (taps given by its generator).
4. The commutator sends $c_1c_2c_3$, so the output rate is three times the input rate ($r=1/3$).
5. After the message, $K-1=2$ zeros flush the register back to 00.

Example: input 101

Output: 111 001 100 001 011.

The encoder has $2^{K-1}=4$ states; its behaviour can be shown by a code tree, state diagram or trellis, and it is decoded with the Viterbi algorithm. The low rate gives a large free distance and strong error correction, at the cost of three times the bandwidth.