ERROR CONTROL CODING – A NEVER ENDING STORY

Error control coding is based on the Shannon Second Theorem. Taking into account the bandwidth and the signal-to-noise ratio it gives the limits for reliable transmission of information. Of course, transmission without errors is impossible, but the error probability can be kept at the corresponding (low) level.
 
In this lecture, after the suitable introduction, “classic” error control codes (block codes, especially cyclic codes, convolutional codes) will be shortly considered. More attention will be dedicated to some new codes that emerged at the moment when it seemed that the further improvements cannot be made. It was conceived that the better performance can be achieved by joined coding and modulation (trellis coded modulation). The next step was iterative decoding allowing at last coming into “the land of promise”. In fact, there is no need to make the difference between block codes and convolutional codes, because the last ones can be terminated (by adding non information bits) and considered as block codes. Further, in 1993 turbo codes were proposed where the feedback between the decoders is used to obtain a better estimation of every bit a posteriori probability during the iterations. Here, the feedback between decoders is used. Besides the turbo codes, there is one more class of linear block codes that makes possible to approach to the Shannon bound. These are Low Density Parity Check (LDPC) codes. In principle they have a sparse parity-check matrix. In such a way the corresponding parity-check equations have a small number of terms providing significantly smaller complexity compared to standard linear block codes. They provide the iterative decoding with a linear complexity. Iterative decoding of LDPC codes based on hard decision consists of complementing some syndrome bits, performed in iterations. The procedure to find which bits should be complemented is usually called bit-flipping (BF) algorithm. Tanner proposed an alternative way for considering control matrix of LDPC code by using the bipartite graphs.