A description of channel coding, in particular linear block codes.
Channel coding is a viable method to reduce information rate
through the channel and increase reliability. This goal isachieved by adding redundancy to the information symbol vector
resulting in a longer coded vector of symbols that aredistinguishable at the output of the channel. Another brief
explanation of channel coding is offered in
Channel Coding and the Repetition Code .
We consider only two classes of codes,
block
codes and
convolutional
codes .
Block codes
The information sequence is divided into blocks of length
$k$ . Each block is mapped into
channel inputs of length
$n$ .
The mapping is independent from previous blocks, that is,there is no memory from one block to another.
$k=2$ and
$n=5$
$$\mathrm{00}\to \mathrm{00000}$$
$$\mathrm{01}\to \mathrm{10100}$$
$$\mathrm{10}\to \mathrm{01111}$$
$$\mathrm{11}\to \mathrm{11011}$$
information sequencecodeword (channel input)
Got questions? Get instant answers now!
A binary block code is completely defined by
$2^{k}$ binary sequences of length
$n$ called codewords.
$$C=\{{c}_{1}, {c}_{2}, , {c}_{{2}^{k}}\}$$
$${c}_{i}\in \{0, 1\}^{n}$$
There are three key questions,
- How can one find "good" codewords?
- How can one systematically map information sequences
into codewords?
- How can one systematically find the corresponding
information sequences from a codeword,
i.e. , how can we decode?
These can be done if we concentrate on linear codes and utilize finite
field algebra.
A block code is linear if
$c_{i}\in C$ and
$c_{j}\in C$ implies
$c_{i}\mathop{\mathrm{xor}}c_{j}\in C$ where
$$ is an elementwise modulo 2 addition.
Hamming distance is a useful measure of codeword properties
$${d}_{H}(c_{i}, c_{j})=\text{\# of places that they are different}$$
Denote the codeword for information sequence
${e}_{1}=\left(\begin{array}{c}1\\ 0\\ 0\\ 0\\ \\ 0\\ 0\end{array}\right)$ by
${g}_{1}$ and
${e}_{2}=\left(\begin{array}{c}0\\ 1\\ 0\\ 0\\ \\ 0\\ 0\end{array}\right)$ by
${g}_{2}$ ,,
and
${e}_{k}=\left(\begin{array}{c}0\\ 0\\ 0\\ 0\\ \\ 0\\ 1\end{array}\right)$ by
${g}_{k}$ .
Then any information sequence can be expressed as
$u=\left(\begin{array}{c}{u}_{1}\\ \\ {u}_{k}\end{array}\right)=\sum_{i=1}^{k} {u}_{i}{e}_{i}$
and the corresponding codeword could be
$c=\sum_{i=1}^{k} {u}_{i}{g}_{i}$
Therefore
$c=uG$
with
$c=\{0, 1\}^{n}$ and
$u\in \{0, 1\}^{k}$ where
$G=\left(\begin{array}{c}{g}_{1}\\ {g}_{2}\\ \\ {g}_{k}\end{array}\right)$ ,
a
$k$ x
$n$ matrix and all operations are modulo 2.
In
with
$$\mathrm{00}\to \mathrm{00000}$$
$$\mathrm{01}\to \mathrm{10100}$$
$$\mathrm{10}\to \mathrm{01111}$$
$$\mathrm{11}\to \mathrm{11011}$$
${g}_{1}=\left(\begin{array}{c}0\\ 1\\ 1\\ 1\\ 1\end{array}\right)$ and
${g}_{2}=\left(\begin{array}{c}1\\ 0\\ 1\\ 0\\ 0\end{array}\right)$ and
$G=\begin{pmatrix}0 & 1 & 1 & 1 & 1\\ 1 & 0 & 1 & 0 & 0\\ \end{pmatrix}$ Got questions? Get instant answers now!
Additional information about coding efficiency and error are provided
in
Block Channel Coding .
Examples of good linear codes include Hamming codes, BCH codes,
Reed-Solomon codes, and many more. The rate of these codes is defined as
$\frac{k}{n}$ and these codes have different error correction and error detection
properties.