Error Detection and Correction Coding

A convolutional code is an error-correcting code in which the encoder has memory: each group of output bits depends on the current input bit and on the previous $K-1$ input bits stored in a shift register. The code is described by $(n,k,K)$: $k$ input bits produce $n$ output bits, giving code rate $r=k/n$, and $K$ is the constraint length.

Encoder

A rate-1/2, $K=3$ encoder with generators $g^{(1)}=(1,1,1)$ and $g^{(2)}=(1,0,1)$:

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |  \        |         /  |
        |   \--(+)--+--------/   |   c1 = mi+mi-1+mi-2
        |                        |
        +---------(+)------------+   c2 = mi+mi-2
                 output: c1 c2 c1 c2 ...

Each output is the modulo-2 convolution of the input with a generator sequence: $c_i^{(j)}=\sum_l g_l^{(j)}m_{i-l}$.

Example: input 1 0 0 1 1 (plus two flushing 0s) gives 11 10 11 11 01 01 11.

Representations

• Code tree: branches up for 0, down for 1, labelled with output bits.
• Trellis diagram: states (contents of memory) against time; repeats after $K-1$ steps.
• State diagram: $2^{K-1}$ states with transitions labelled input/output.

Decoding

The Viterbi algorithm (maximum-likelihood) finds the trellis path with minimum Hamming distance from the received sequence; sequential decoding is used for large $K$.

Features

• Works on a continuous bit stream, no block division.
• Strong error correction with soft-decision decoding; free distance $d_{free}$ measures power.
• Used in GSM, satellite and deep-space links, Wi-Fi (often with interleaving).

Binary cyclic code

A binary cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. If $(c_0,c_1,\dots,c_{n-1})$ is a codeword, so is $(c_{n-1},c_0,\dots,c_{n-2})$.

Code vectors are treated as polynomials $c(x)=c_0+c_1x+\dots+c_{n-1}x^{n-1}$. An $(n,k)$ cyclic code is defined by a generator polynomial $g(x)$ of degree $n-k$ that divides $x^n+1$. Every codeword is a multiple of $g(x)$. Cyclic codes are easy to encode and decode with shift registers (used in CRC).

Given

$(n,k)=(7,4)$, $n-k=3$, $g(x)=x^3+x^2+1$. It is a valid generator since $x^7+1=(x+1)(x^3+x+1)(x^3+x^2+1)$.

Convention: the leftmost data bit is the highest power. Data $1011$:

$$d(x)=x^3+x+1$$

All arithmetic is modulo 2 ($1+1=0$).

(a) Non-systematic codeword

$$\begin{aligned} c(x)&=d(x)\,g(x)=(x^3+x+1)(x^3+x^2+1)\\ &=x^6+x^5+x^3+x^4+x^3+x+x^3+x^2+1\\ &=x^6+x^5+x^4+x^3+x^2+x+1 \end{aligned}$$

(three $x^3$ terms leave one $x^3$.)

Non-systematic code vector: 1 1 1 1 1 1 1

(b) Systematic codeword

Steps: multiply by $x^{n-k}=x^3$, divide by $g(x)$, append the remainder as parity bits.

$$x^3d(x)=x^6+x^4+x^3$$

Long division by $g(x)=x^3+x^2+1$:

              x^3 + x^2            <- quotient
          ---------------------------
x^3+x^2+1 ) x^6 +     x^4 + x^3
            x^6 + x^5 +       x^3
            -----------------------
                  x^5 + x^4
                  x^5 + x^4 +       x^2
                  -------------------
                                    x^2   <- remainder

Remainder $p(x)=x^2$, i.e. parity bits $(x^2,x^1,x^0)=1\,0\,0$.

$$c(x)=x^3d(x)+p(x)=x^6+x^4+x^3+x^2$$

Check: $c(x)=(x^3+x^2)\,g(x)$, a multiple of $g(x)$, so it is a valid codeword.

Systematic code vector: 1 0 1 1 | 1 0 0 (data bits followed by parity bits).

Shift-register encoder check

The remainder can be produced by a 3-stage feedback shift register (taps at the non-zero coefficients of $g(x)=1+x^2+x^3$). With feedback $f=\text{input}\oplus r_2$, the update is $r_0\leftarrow f$, $r_1\leftarrow r_0$, $r_2\leftarrow r_1\oplus f$.

After 4 shifts the register holds $(r_0,r_1,r_2)=(0,0,1)$, i.e. remainder $x^2$; read out $r_2r_1r_0=100$, the same parity bits as the long division. The 4 data bits are sent first, then the gate opens and the 3 parity bits follow.

Hamming weight

The Hamming weight $w(\mathbf{c})$ of a code vector is the number of non-zero (1) elements in it.

Example: $w(1011100)=4$, $w(0000000)=0$.

Hamming distance

The Hamming distance $d(\mathbf{c}_1,\mathbf{c}_2)$ between two code vectors of equal length is the number of positions in which they differ. It equals the weight of their modulo-2 sum: $d(\mathbf{c}_1,\mathbf{c}_2)=w(\mathbf{c}_1\oplus\mathbf{c}_2)$.

Example: $\mathbf{c}_1=1011100$, $\mathbf{c}_2=1111111$; $\mathbf{c}_1\oplus\mathbf{c}_2=0100011$, so $d=3$.

The smallest distance between any two codewords is the minimum distance $d_{min}$; for a linear code it equals the smallest non-zero weight. A code detects up to $d_{min}-1$ errors and corrects up to $\lfloor (d_{min}-1)/2\rfloor$. For the (7,4) cyclic Hamming code $d_{min}=3$: it detects 2 and corrects 1 error.

(7,4) cyclic code for data 1011

Given $g(x)=x^3+x^2+1$, $n-k=3$. Convention: leftmost bit = highest power, so $d(x)=x^3+x+1$. Modulo-2 arithmetic.

Non-systematic form: $c(x)=d(x)g(x)$

$$\begin{aligned} c(x)&=(x^3+x+1)(x^3+x^2+1)\\ &=x^6+x^5+x^3\;+\;x^4+x^3+x\;+\;x^3+x^2+1\\ &=x^6+x^5+x^4+x^3+x^2+x+1 \end{aligned}$$

Non-systematic code vector: 1111111.

Systematic form:

1. $x^3d(x)=x^6+x^4+x^3$
2. Divide by $g(x)$:

              x^3 + x^2
          -------------------------
x^3+x^2+1 ) x^6 +     x^4 + x^3
            x^6 + x^5 +       x^3
            -----------------------
                  x^5 + x^4
                  x^5 + x^4 +       x^2
                  -------------------
                                    x^2

3. Remainder $p(x)=x^2$, parity bits $= 100$.
4. $c(x)=x^6+x^4+x^3+x^2$.

Systematic code vector: 1011 100 (message, then parity).

Check: $c(x)=(x^3+x^2)g(x)$, so $c(x)$ is divisible by $g(x)$ and is a valid codeword.

Hamming weight

The Hamming weight $w(\mathbf{x})$ of a code vector is the number of 1s in it. For $\mathbf{x}=(0111000)$:

$$w(\mathbf{x})=0+1+1+1+0+0+0=3$$

Hamming distance

The Hamming distance between two code vectors is the number of positions in which they differ, $d(\mathbf{x},\mathbf{y})=w(\mathbf{x}\oplus\mathbf{y})$. For example, distance of $\mathbf{x}$ from the all-zero codeword is $d(0111000,0000000)=3$, and from $\mathbf{y}=1111111$ it is $w(1000111)=4$.

Proof that x is a valid codeword

A vector is a valid codeword of the code if and only if its syndrome is zero:

$$\mathbf{s}=H\mathbf{x}^T=\mathbf{0}\quad(\text{equivalently } \mathbf{x}H^T=\mathbf{0})$$ $$H=\begin{bmatrix}1&1&1&0&1&0&0\\1&1&0&1&0&1&1\\1&0&1&1&0&0&1\end{bmatrix},\qquad \mathbf{x}^T=\begin{bmatrix}0\\1\\1\\1\\0\\0\\0\end{bmatrix}$$

Only positions 2, 3 and 4 of $\mathbf{x}$ are 1, so $H\mathbf{x}^T$ is the modulo-2 sum of columns 2, 3 and 4 of $H$:

$$\mathbf{s}=H\mathbf{x}^T=\begin{bmatrix}0\\0\\0\end{bmatrix}$$

Since the syndrome is the zero vector, $\mathbf{x}=(0111000)$ satisfies all three parity-check equations. Hence the given code vector is valid.

For a systematic $(n,k)$ linear block code, $G=[I_k\mid P]$ and $H=[P^T\mid I_{n-k}]$, with $GH^T=0$. A codeword is $\mathbf{c}=\mathbf{m}G$, and for a received vector $\mathbf{r}$ the syndrome is $\mathbf{s}=\mathbf{r}H^T$. All arithmetic is modulo 2.

a) Generator matrix

$$H=\begin{bmatrix}1&0&1&1&0&0\\1&1&0&0&1&0\\0&1&1&0&0&1\end{bmatrix}=[P^T\mid I_3],\qquad P^T=\begin{bmatrix}1&0&1\\1&1&0\\0&1&1\end{bmatrix}$$

Transposing:

$$P=\begin{bmatrix}1&1&0\\0&1&1\\1&0&1\end{bmatrix},\qquad G=[I_3\mid P]=\begin{bmatrix}1&0&0&1&1&0\\0&1&0&0&1&1\\0&0&1&1&0&1\end{bmatrix}$$

b) Codeword for message 110

$$\mathbf{c}=\mathbf{m}G=1\cdot(100110)\oplus1\cdot(010011)\oplus0\cdot(001101)=110101$$

Parity bits directly: $p_1=m_1\oplus m_3=1\oplus0=1$, $p_2=m_1\oplus m_2=1\oplus1=0$, $p_3=m_2\oplus m_3=1\oplus0=1$.

Codeword = 110 101

Check: $\mathbf{c}H^T$: row 1: $1+0+0+1=0$, row 2: $1+1+0+0=0$, row 3: $1+0+0+1=0$. Syndrome $000$, so it is valid.

All codewords (for reference; $d_{min}=3$, corrects 1 error):

c) Check received word 110111

$$\mathbf{s}=\mathbf{r}H^T,\quad \mathbf{r}=(1\,1\,0\,1\,1\,1)$$

Each syndrome bit is one row of $H$ dotted with $\mathbf{r}$:

$$\mathbf{s}=(0\ 1\ 0)\neq\mathbf{0}$$

The syndrome is non-zero, so the received word has an error.

Locating it: $\mathbf{s}=010$ equals the 5th column of $H$ $(0,1,0)^T$, so assuming a single error, bit 5 is wrong: $\mathbf{e}=000010$.

$$\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}=110111\oplus000010=110101$$

Answer: $G$ as above; codeword for 110 is 110101; received 110111 is in error (syndrome 010), corrected codeword 110101, message 110.

A trellis diagram is a time-expanded state diagram of a convolutional encoder. The encoder states (contents of the memory) are drawn as rows of nodes, time runs left to right, and each branch shows the transition caused by one input bit, labelled with the output bits. Each message traces one path through the trellis; the Viterbi decoder searches the trellis for the closest path.

Assumed encoder ("3-stage register" read as constraint length $K=3$: present bit plus 2 memory flip-flops, so $2^2=4$ states), rate 1/2, generators $g^{(1)}=111$, $g^{(2)}=101$:

$$c_1=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_2=m_i\oplus m_{i-2}$$

States $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11.

Encoding 1010 (with two 0s to flush)

Encoded sequence: 11 10 00 10 11 00.

Trellis with the message path

      t0     t1     t2     t3     t4     t5     t6
a 00  *      o      o      o      o      *======*
        \                               /
           \                           /
b 10  o      *      o      *      o   /  o      o
               \         /   \      /
                  \   /         \  /
c 01  o      o      *      o      *      o      o


d 11  o      o      o      o      o      o      o
in:      1      0      1      0      0      0
out:    11     10     00     10     11     00

In the full trellis every state has two branches leaving it (input 0 and input 1). After $K-1=2$ steps the pattern of branches repeats at every stage. The path marked with * (= for a horizontal branch) is the unique path for 1010; any received sequence is decoded by finding the path with minimum Hamming distance.

Assumption: the encoder is the standard rate-1/2 encoder with a three-stage shift register (present bit and two delay flip-flops, constraint length $K=3$) and generator sequences $g^{(1)}=(1,1,1)$, $g^{(2)}=(1,0,1)$.

 Encoder: g1 = 111, g2 = 101 (K = 3, rate 1/2)

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |          |           |
        +---(+)----+-----------+---> c1 = mi+mi-1+mi-2
        |                      |
        +---(+)----------------+---> c2 = mi+mi-2
            output per bit: c1 c2

$$c_i^{(1)}=m_i\oplus m_{i-1}\oplus m_{i-2},\qquad c_i^{(2)}=m_i\oplus m_{i-2}$$

Encoded sequence

Message $(m_0\dots m_4)=10011$, followed by two 0s to return the register to 00.

By polynomials: $c^{(1)}(D)=(1+D^3+D^4)(1+D+D^2)=1+D+D^2+D^3+D^6$ and $c^{(2)}(D)=(1+D^3+D^4)(1+D^2)=1+D^2+D^3+D^4+D^5+D^6$, which give the same bits.

Encoded sequence: 11 10 11 11 01 01 11

State diagram

State = previous two inputs $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11.

            +--0/00--+
            v        |
          [ a 00 ]---+
           ^     \
      0/11 |      \ 1/11
           |       v
        [ c 01 ]<--0/10--[ b 10 ]
           |  ----1/00--->   |
           ^                 | 1/01
      0/01 |                 v
           +-------------[ d 11 ]--+
                            ^      | 1/10
                            +------+
 label = input/output bits

Trellis diagram

      t0     t1     t2     t3     t4     t5     t6     t7
a 00  *      o      o      *      o      o      o      *
        \                 /  \                        /
           \             /      \                    /
b 10  o      *      o   /  o      *      o      o   /  o
               \      /            \              /
                  \  /              \            /
c 01  o      o      *      o      o   \  o      *      o
                                       \      /
                                        \  /
d 11  o      o      o      o      o      *      o      o
in:      1      0      0      1      1      0      0
out:    11     10     11     11     01     01     11

At each stage every state has two branches (input 0 and 1) as in the table; the path for 10011 is marked with *. The output read along the path is 11 10 11 11 01 01 11.

Error detection vs error correction

Rate-1/2 convolutional encoder (design)

Choose $k=1$ input bit, $n=2$ output bits ($r=1/2$), constraint length $K=3$ (two memory flip-flops, 4 states) and generators $g^{(1)}=111$, $g^{(2)}=101$.

 Encoder: g1 = 111, g2 = 101 (K = 3, rate 1/2)

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |          |           |
        +---(+)----+-----------+---> c1 = mi+mi-1+mi-2
        |                      |
        +---(+)----------------+---> c2 = mi+mi-2
            output per bit: c1 c2

A commutator samples $c_1$ then $c_2$ for each input bit, so two bits go out for every bit in.

State = previous two inputs $(m_{i-1}m_{i-2})$: a = 00, b = 10, c = 01, d = 11.

Code tree (three-bit input)

Upper branch = input 0, lower branch = input 1; labels are outputs.

                              00 a  (000)
                    00 a ---<
                   /          11 b  (001)
          00 a ---<
         /         \          10 c  (010)
        /           11 b ---<
       /                      01 d  (011)
 start<
       \                      11 a  (100)
        \           10 c ---<
         \         /          00 b  (101)
          11 b ---<
                   \          01 c  (110)
                    01 d ---<
                              10 d  (111)
   bit:    1          2          3

Read along a path: input 101 gives 11, 10, 00, i.e. root (down 11) to b, (up 10) to c, (down 00) to b.

Trellis diagram, input 101 (plus 00 to flush)

      t0     t1     t2     t3     t4     t5
a 00  *      o      o      o      o      *
        \                               /
           \                           /
b 10  o      *      o      *      o   /  o
               \         /   \      /
                  \   /         \  /
c 01  o      o      *      o      *      o


d 11  o      o      o      o      o      o
in:      1      0      1      0      0
out:    11     10     00     10     11

Encoded output for 101: 11 10 00 10 11. Every state in the full trellis has two outgoing branches; after the first two stages the trellis structure repeats.

Why a convolutional coder is better than a block coder

• It works on a continuous stream, so no need to wait for a full block; encoding delay and buffering are small.
• It has memory: each output depends on several past bits, so redundancy is spread over many bits and burst-like noise is handled better with interleaving.
• Soft-decision Viterbi decoding is easy, giving 2 to 3 dB more coding gain than hard-decision block decoding at the same rate.
• Simple shift-register encoder and good performance at low rates (used in GSM, satellite, Wi-Fi).

(7,4) cyclic Hamming code, $g(x)=1+x+x^3$, message 1011

Convention (Haykin): message $(m_0m_1m_2m_3)=1011$ in ascending powers, so

$$m(x)=1+x^2+x^3$$

Modulo-2 arithmetic.

Non-systematic: $c(x)=m(x)g(x)$

$$\begin{aligned} c(x)&=(1+x^2+x^3)(1+x+x^3)\\ &=1+x+x^3\;+\;x^2+x^3+x^5\;+\;x^3+x^4+x^6\\ &=1+x+x^2+x^3+x^4+x^5+x^6 \end{aligned}$$

Non-systematic code vector $(c_0\dots c_6)$ = 1111111.

Systematic: $c(x)=b(x)+x^{n-k}m(x)$, with $b(x)$ = remainder of $x^3m(x)/g(x)$.

$$x^3m(x)=x^3+x^5+x^6$$

              x^3 + x^2 + x + 1
          ---------------------------
x^3+x+1 ) x^6 + x^5 +       x^3
          x^6 +       x^4 + x^3
          -------------------------
                x^5 + x^4
                x^5 +       x^3 + x^2
                -----------------------
                      x^4 + x^3 + x^2
                      x^4 +       x^2 + x
                      -------------------
                            x^3 +       x
                            x^3 +       x + 1
                            -----------------
                                          1

$b(x)=1$, so parity bits $(b_0b_1b_2)=100$.

$$c(x)=1+x^3+x^5+x^6$$

Systematic code vector $(b_0b_1b_2\,m_0m_1m_2m_3)$ = 100 1011.

Check: $c(x)=(1+x+x^2+x^3)g(x)$, which expands to $1+x^3+x^5+x^6$, so it is a valid codeword.

Significance of $d_{min}$

The minimum Hamming distance $d_{min}$ is the smallest number of positions in which any two codewords differ (for a linear code, the smallest non-zero codeword weight). It fixes the power of the code:

• Detects up to $s$ errors if $d_{min}\ge s+1$.
• Corrects up to $t$ errors if $d_{min}\ge 2t+1$, i.e. $t=\lfloor(d_{min}-1)/2\rfloor$.

For a (7,4) Hamming code $d_{min}=3$: detects 2, corrects 1 error.

Note on the generator polynomial

A generator for a (7,4) cyclic code must have degree $n-k=3$ and divide $x^7+1=(1+x)(1+x+x^3)(1+x^2+x^3)$. The printed $g(x)=1+x+x^2$ has degree 2 and does not divide $x^7+1$, so it is taken as a misprint of the standard $g(x)=1+x+x^3$.

Message $(m_0m_1m_2m_3)=1101$, ascending powers:

$$m(x)=1+x+x^3$$

Non-systematic code vector

$$\begin{aligned} c(x)&=m(x)g(x)=(1+x+x^3)(1+x+x^3)\\ &=1+x^2+x^6\quad(\text{cross terms cancel in mod 2: }(a+b+c)^2=a^2+b^2+c^2) \end{aligned}$$

$(c_0c_1\dots c_6)$ = 1010001

Systematic code vector

$$x^3m(x)=x^3+x^4+x^6$$

Divide by $g(x)=1+x+x^3$:

              x^3
          -----------------------
x^3+x+1 ) x^6 + x^4 + x^3
          x^6 + x^4 + x^3
          ---------------
                          0

Remainder $b(x)=0$, parity bits $(b_0b_1b_2)=000$.

$$c(x)=b(x)+x^3m(x)=x^3+x^4+x^6$$

$(b_0b_1b_2\,m_0m_1m_2m_3)$ = 000 1101

This happens because $m(x)$ itself equals $g(x)$, so $x^3m(x)$ is already a multiple of $g(x)$.

Both have weight 3, equal to $d_{min}$ of the code.

The error detection and correction capability of a block code depends on its minimum Hamming distance $d_{min}$, the smallest number of bit positions in which any two codewords differ. For a linear code, $d_{min}$ equals the smallest weight of a non-zero codeword.

Detection

If fewer than $d_{min}$ bits are changed, a codeword cannot turn into another valid codeword, so the error is noticed:

$$s\le d_{min}-1$$

Correction

The decoder chooses the nearest codeword. This is always right if the received word is closer to the sent codeword than to any other, which needs

$$t\le\left\lfloor\frac{d_{min}-1}{2}\right\rfloor\quad(d_{min}\ge 2t+1)$$

To correct $t$ and also detect $s>t$ errors: $d_{min}\ge t+s+1$.

  c1 o----x----x----o c2     d_min = 3
       radius t = 1 spheres do not overlap

Larger $d_{min}$ needs more redundancy (lower code rate $k/n$).

A block code is linear if (1) the all-zero word is a codeword and (2) the modulo-2 sum of any two codewords is also a codeword (closure). For binary codes, (2) implies (1) since $\mathbf{c}\oplus\mathbf{c}=\mathbf{0}$.

A (4,3) parity code takes 3 message bits $m_1m_2m_3$ and adds one parity bit $p$.

Even parity code is linear

$p=m_1\oplus m_2\oplus m_3$, so every codeword has an even number of 1s:

General proof: let $\mathbf{c}_1,\mathbf{c}_2$ be codewords, with weights $w_1,w_2$ both even. Then

$$w(\mathbf{c}_1\oplus\mathbf{c}_2)=w_1+w_2-2\,w(\mathbf{c}_1\cdot\mathbf{c}_2)$$

where $\mathbf{c}_1\cdot\mathbf{c}_2$ counts positions where both are 1. Even + even − even = even, so the sum is again an even-weight 4-bit word, i.e. a codeword. Also $0000$ is a codeword.

Equivalently, the code can be generated by a matrix:

$$G=\begin{bmatrix}1&0&0&1\\0&1&0&1\\0&0&1&1\end{bmatrix},\qquad \mathbf{c}=\mathbf{m}G$$

and $\mathbf{m}_1G\oplus\mathbf{m}_2G=(\mathbf{m}_1\oplus\mathbf{m}_2)G$, which is a codeword.

Example: $0011\oplus0101=0110$ (codeword), $1001\oplus1111=0110$ (codeword). Hence the (4,3) even parity code is a linear block code.

Odd parity code is not linear

$p=m_1\oplus m_2\oplus m_3\oplus1$, so every codeword has an odd number of 1s:

1. The all-zero word $0000$ has even weight, so it is not a codeword.
2. Closure fails: for odd $w_1,w_2$, $w_1+w_2-2(\cdot)$ is even, so the sum of two codewords always has even weight and is never a codeword. Example: $0001\oplus0010=0011$, weight 2, not in the code.

Hence the (4,3) odd parity code is not a linear block code.

Rate $1/3$: each input bit gives 3 output bits. Constraint length $K=3$, so the register holds $m_i,m_{i-1},m_{i-2}$. Each output is the modulo-2 convolution of the input with its generator:

$$c_i^{(j)}=\sum_{l=0}^{2}g_l^{(j)}m_{i-l}\pmod 2$$

With the given generators:

$$\begin{aligned} c_i^{(1)}&=0\cdot m_i+m_{i-1}+m_{i-2}=m_{i-1}\oplus m_{i-2}\\ c_i^{(2)}&=m_i\oplus m_{i-2}\\ c_i^{(3)}&=m_i\oplus m_{i-1} \end{aligned}$$

 m -->[ m_i ]-->[ m_i-1 ]-->[ m_i-2 ]
        |           |           |
        |           +----(+)----+------> c1 = mi-1+mi-2
        +----------(+)----------+------> c2 = mi+mi-2
        +----(+)----+------------------> c3 = mi+mi-1
     commutator: c1 c2 c3 per input bit

Encoding

Message $(m_0\dots m_4)=10011$, then two 0s ($K-1$) to flush the register. Register starts at 00.

Check by polynomial (transform-domain) method

$m(D)=1+D^3+D^4$; $g^{(1)}(D)=D+D^2$, $g^{(2)}(D)=1+D^2$, $g^{(3)}(D)=1+D$.

$$\begin{aligned} c^{(1)}(D)&=(1+D^3+D^4)(D+D^2)=D+D^2+D^4+D^6\ \Rightarrow 0110101\\ c^{(2)}(D)&=(1+D^3+D^4)(1+D^2)=1+D^2+D^3+D^4+D^5+D^6\ \Rightarrow 1011111\\ c^{(3)}(D)&=(1+D^3+D^4)(1+D)=1+D+D^3+D^5\ \Rightarrow 1101010 \end{aligned}$$

Interleaving the three sequences bit by bit gives the same result.

Encoded sequence: 011 101 110 011 110 011 110 (21 bits; the first 15 bits, 011 101 110 011 110, correspond to the message itself and the last 6 come from flushing.)

Hamming weight

The Hamming weight of a code vector is the number of 1s in it. Example: $w(100101)=3$.

Hamming distance

The Hamming distance between two vectors is the number of positions where they differ, $d(\mathbf{x},\mathbf{y})=w(\mathbf{x}\oplus\mathbf{y})$. Example: $d(100101,101011)=w(001110)=3$.

Checking the received vector

The printed $H$ has a blank column; it is taken as the standard systematic form $H=[P^T\mid I_3]$:

$$H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix}$$

A received vector $\mathbf{r}$ is error-free (a valid codeword) if its syndrome $\mathbf{s}=\mathbf{r}H^T$ is zero.

$\mathbf{r}=(1\,0\,0\,1\,0\,1)$: the 1s are in positions 1, 4 and 6, so $\mathbf{s}$ is the mod-2 sum of columns 1, 4 and 6 of $H$:

$$\mathbf{s}=\mathbf{r}H^T=(0\ 0\ 0)$$

The syndrome is zero, so 100101 is a valid codeword (not erroneous), assuming no undetectable error pattern.

Check with the generator matrix $G=[I_3\mid P]$:

$$G=\begin{bmatrix}1&0&0&1&0&1\\0&1&0&0&1&1\\0&0&1&1&1&0\end{bmatrix}$$

Message 100 gives $\mathbf{c}=100\,101$, exactly the received vector. Message = 100.

(If a syndrome were non-zero, matching it to a column of $H$ would locate a single-bit error; this code has $d_{min}=3$.)

A cyclic code is a linear block code in which every cyclic shift of a codeword is also a codeword. An $(n,k)$ cyclic code is generated by a polynomial $G(p)$ of degree $n-k$ that divides $p^n+1$:

• Non-systematic encoding: $X(p)=M(p)\,G(p)$; message bits are not visible directly in the codeword.
• Systematic encoding: $X(p)=p^{n-k}M(p)+\text{rem}\left[\dfrac{p^{n-k}M(p)}{G(p)}\right]$; the message appears unchanged and the remainder gives the $n-k$ parity bits.

Given $(n,k)=(7,4)$, $G(p)=p^3+p+1$, $n-k=3$. Convention: leftmost message bit is the highest power. Message $0101$:

$$M(p)=0\cdot p^3+1\cdot p^2+0\cdot p+1=p^2+1$$

All additions are modulo 2.

Non-systematic form

$$\begin{aligned} X(p)&=M(p)\,G(p)=(p^2+1)(p^3+p+1)\\ &=p^5+p^3+p^2+p^3+p+1\\ &=p^5+p^2+p+1 \end{aligned}$$

Coefficients from $p^6$ down to $p^0$:

Non-systematic code vector: 0100111

Systematic form

1. Multiply by $p^{n-k}=p^3$: $p^3M(p)=p^5+p^3$.
2. Divide by $G(p)$:

              p^2
            -----------------
 p^3+p+1 )  p^5 +       p^3
            p^5 +       p^3 + p^2
            ---------------------
                              p^2   <- remainder

3. Remainder $C(p)=p^2$, so parity bits $(p^2,p^1,p^0)=100$.
4. $X(p)=p^3M(p)+C(p)=p^5+p^3+p^2$.

Check: $X(p)=p^2\,G(p)=p^5+p^3+p^2$, a multiple of $G(p)$.

Systematic code vector: 0101 100 (message bits, then check bits)

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 decides that it detects $d_{min}-1$ and corrects $\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.

Hamming weight

The Hamming weight $w(\mathbf{c})$ is the number of non-zero elements in a code vector.

Example: $w(101011)=4$, $w(100011)=3$.

Hamming distance

The Hamming distance $d(\mathbf{c}_1,\mathbf{c}_2)$ is the number of positions in which two code vectors differ, $d=w(\mathbf{c}_1\oplus\mathbf{c}_2)$.

Example: $\mathbf{c}_1=101011$, $\mathbf{c}_2=100011$, $\mathbf{c}_1\oplus\mathbf{c}_2=001000$, so $d=1$.

Validating the received vector

A received vector is a valid codeword only if the syndrome $\mathbf{s}=\mathbf{r}H^T=\mathbf{0}$.

$$H=\begin{bmatrix}1&0&1&1&0&0\\0&1&1&0&1&0\\1&1&0&0&0&1\end{bmatrix},\qquad \mathbf{r}=(1\,0\,0\,0\,1\,1)$$

The 1s of $\mathbf{r}$ are at positions 1, 5, 6, so add columns 1, 5 and 6 of $H$:

$$\mathbf{s}=(1\ 1\ 0)\neq\mathbf{0}$$

The received vector 100011 is not a valid codeword; it contains an error.

Correction (single error)

The syndrome $110$ matches column 3 of $H$ $(1,1,0)^T$, so the 3rd bit is in error: $\mathbf{e}=001000$.

$$\hat{\mathbf{c}}=\mathbf{r}\oplus\mathbf{e}=100011\oplus001000=101011$$

Check: columns 1, 3, 5, 6 sum to $(1+1+0+0,\ 0+1+1+0,\ 1+0+0+1)=(0,0,0)$, so 101011 is valid. Corrected message (first 3 bits): 101.