HSC welcomes all external visitors to this site, especially students and members of the academic community. Please use the comments box at the bottom of each page to record any comments or suggestions for improvement.
Introduction
Forward Error Correction (FEC) or 'coding' involves adding of redundant data to a digital data stream to be increase its resilience to channel induced errors. The importance of FEC as an integral part of wireless communication was hinted at by many authors, but cemented by Shannon's seminal paper on digital communication, which started the entire field of Information Theory. Shannon's paper has been followed by seminal contributions on coding techniques, decoding algorithms, etc. and coding theory remains one of the most actively researched areas of digital communication.
This article does not intend to cover the different forms of coding (Turbo, LDPC) or the different types of decoding. We will review the basic theory of coding and then cover the theory of how and why it works
All schemes for coding and decoding of data can be divided in to the following two categories
- Block Codes
- Convolution codes
All coding schemes are capable of performing at least one or more of the tasks mentioned below
- Detect if any bit in the message has been flipped.
- Detect the particular bit in the message which has been flipped.
- Correct the bit which has been flipped.
It may be noted that depending on the coding scheme used, it may be possible to detect if more than one bit has been flipped simultaneously. However it may /may not be possible to select the correct permutation of the bits as were present in the original message (soft decoding).
Block Code
A block code is defined as a set of rules for converting a set of source bits s_1, s_2, s_3, s_4 of length K into a set of transmitted bits s_1, s_2, s_3, s_4 , p_1, p_2, p_3 of length N where p_1, p_2, p_3 are the parity bits (length of parity bits is = N-K).
Block codes encode each bit in the given sequence of source bits separately and the output of a block code is always fixed.
For example, the (N,K) Hamming Code is a block code where
- N Total number of bits in the message
- K Number of Source bits.
- (N-K) Parity check bits.
The source and the parity can have the following values {0,1}.
The parity bits are used to keep track of the number of {1} in the sequence of source bits. The value of the parity bit is assigned in the following manner
P_k = 0 if the number of {1s} is even.
P_k = 1 if the number of {1s} is odd.
The value of the parity bits is set as follows :
\begin{eqnarray}
p_1 = (s_1 + s_2 + s_3) \% 2 \\
p_2 = (s_1 + s_3 + s_4) \% 2 \\
p_3 = (s_1 + s_2 + s_4) \% 2
\end{eqnarray}
This encoding scheme has the follwing capabilities :
- Single bit errors can be detected and corrected.
- Double bit errors can be detected but not corrected.
Effectiveness of channel coding
In channel coding, we have a discrete set of input data, which is mapped to one of a set of ``codes'' in a one-to-one and invertible
fashion. A code is transmitted by the transmitter and received by the receiver, which does a maximum likelihood estimation to map it to the
original transmitted code. After recovering what it believes is the original transmitted code, it maps it back to the original data symbol
which would have triggered the code.
Assume that we have a transmitter-receiver pair. There is a set of N length codes \mathcal{X}_N which can be transmitted over this
channel and will map uniquely to a set \mathcal{Y}_N which can be received. A FEC scheme picks a sub-set of these of size M, such that
each code of the selected set maps to one input data point m \rightarrow x_m. For the mth input data, the corresponding code x_m is
transmitted and received as y. The maximum likelihood detection algorithm maps y to y_m such that the ML condition
Pr {y \vert x_m } > Pr{y \vert x_{\acute{m}} }\ \forall \acute{m} \ne m.
If we cannot get a m to satisfy this condition, we have
an error in decoding. P_{em} denotes the probability that there was a decoding error when the mth code was transmitted; obviously this
covers both the cases where no decision is possible as well as the case that some \acute{m} \ne m is output by the decoder.
A lot of results have been published for the results of the error correction coding in different environments using simulation. However,
simulation has some enormous disadvantages {benedettojsac} when trying to measure the general performance of a coding technique in
different conditions. First, the size of the block N leads to an enormous number of different input vectors to consider. On top of that,
in high SNR conditions, the bit-error rates are very low, so a very large number of runs are required to get stable results. Thus, it would
be very convenient if the performance of error-correction coding could be measured using an analytical technique. As it turns out, while an
exact estimate is still not available, relatively ``tight'' upper bounds are indeed possible.
Analytical methods for estimating coding performance
The simplest and oldest approach to estimate the performance of generic block codes is by using the union bound. The union bound aims to determine the word error probability of a
given code by summing the individual bit-error probabilities i.e. P(y \vert x) = \sum_i P(y_i \vert x_i), where y and x are two
code-words, y being that which the decoder outputs and x being that which was original transmitted. Obviously, if y \ne x, we have a
word error event.
In general, if we have a code which takes in k input points, and n output points, we can characterize the code by its input output
weight enumerating function A(w,h),\ 0 \le w \le k,\ 0 \le h \le n, where A(w,h) denotes the number of possible code words with input
weight w and output weight h [ The weight of a code-word is the number of 1s in it ]. Then the union bound of a the word error
probability of this code over a binary memory-less channel is given by
p_n \le \sum_{h=1}^n \left( \sum_{w=1}^k A(w,h) \right) z^h
where z^h denotes the pairwise error probability (PEP) of any two code-words which are separated by a hamming distance of h. For
example, in an AWGN channel, the PEP between two code words of hamming distance $h$ is the probability of $h$ bits between incorrectly
decoded and is thus \equiv \frac{w}{N} \frac{1}{2} erfc \left( \sqrt{d \frac{k E_b}{N N_0}} \right).
There has been much research on the efficacy of the union bound; in general, it is a very loose bound for low SNR values and turbo codes. In 1965, Gallagher published a more sophisticated bounding technique, which laid the foundation for modern research in this area. Since then sophisticated bounds for turbo codes have been published by Duman-Salehi, Divsalar and other authors.
For more details on analytical estimates of channel coding performance (including the DS2 and Divsalar bounds) and its application to channel quality estimation, see lte_linkadaptation.pdf
Categories: Wireless Software
Comments
