Logo der Uni Stuttgart
Introduction
Practical transmission channels are subject to noise. Therefore, they cannot transmit an arbitrary high amount of information reliable. As most applications however require error-free transmissions, channel codes must be used to enable error-detection and -correction in such noisy scenarios. The basic idea of a channel code is to add redundancy to the information that is transmitted. In other words, instead of transmitting $K$ message symbols in $K$ channel symbols, we spread the information over $N$ channel symbols, with $N>K$. If the symbols are bits, we call such a code a binary code. $N$ is called the block length of the code, and $K$ the message length. The code rate of the code is given by $$ R_c = \frac{K}{N}. $$

A binary code is defined by a one-to-one (i.e. invertible) encoding rule between $K$-bit message vectors $\mathbf{u}$ to $N$-bit codewords $\mathbf{c}$. The codebook or codeword table (CWT) is given by listing all $2^K$ possible codewords. We call a code linear, if any linear combination of codewords (under modulo-2 addition, XOR) is again a valid codeword (i.e. found in the codebook). For linear codes, the encoding rule is given for each codeword bit $c_i$ as a XOR-combination of several message bits $u_i$.


Example ($N=6, K=3$):
Let the encoding rule be $\mathbf{c}=(u_1, u_2, u_3, u_1 \oplus u_2, u_1 \oplus u_3, u_2 \oplus u_3$). Thus the code rate is $R_c = \frac{3}{6} = \frac{1}{2}$. By listing all $2^3=8$ codewords, we have the codeword table \begin{align*} CWT_{6,3}= \left(\begin{array}{ccc|ccc} 0&0&0&0&0&0\\ 0&0&1&0&1&1\\ 0&1&0&1&0&1\\ 0&1&1&1&1&0\\ 1&0&0&1&1&0\\ 1&0&1&1&0&1\\ 1&1&0&0&1&1\\ 1&1&1&0&0&0 \end{array}\right). \end{align*} Furthermore, linear codes can be represented by a $K \times N$ generator matrix $\mathbf{G}$ with the encoding rule as the vector-matrix multiplication $\mathbf{c}=\mathbf{u}\cdot\mathbf{G}$ (modulo 2). We find the rows of the generator matrix as the codewords corresponding to unit vector messages, i.e. rows 2, 3 and 5 in the example: $$ \mathbf{G}_{6,3}= \left[\begin{array}{cccccc} 1&0&0&1&1&0\\ 0&1&0&1&0&1\\ 0&0&1&0&1&1\\ \end{array}\right] $$ You can verify that $\mathbf{G}$ indeed generates all codewords as linear combinations of its rows.