m
inistry
of transport and telecommunications of the Ukraine
State Administration of Communication
Odessa national academy of telecommunication named after A.S. Popov
department of the Telecommunication theory named after A.G. Zuko
Bases of the error-control codes theory
Module №4
Education manual
on telecommunication theory
Odessa 2010
УДК 621.391 Plane of Education Materials Publication in 2010
Bases of the error-control codes theory: [education manual] / V. Banket, P. Ivaschenko, L. Borschova, D. Rozenvasser. – Odessa: ONAT named after A.S. Popov, 2010. – 96 p.
Editor of English language Ocheretnaya O.Yu.
This education manual contains main theoretical positions of Telecommunication Theory, chapter «Bases of the error-control codes theory», questions and tasks for examination of knowledge, methodical instructions and input data for course work, methodical guidelines for fulfilling laboratory works, short English-Russian and Russian-English dictionaries.
The manual is intended for students training on the direction 050903 – telecommunications studying the module 4 of Telecommunication theory
APPROVED on Chair of Telecommunication theory
named after A.G. Zuko meeting.
Protocol № 9, March 25, 2010
Contents
P.
1 Purpose, structure and classification of error-control codes 5
1.1 Error-control codes in transmission systems 5
1.2 Classification of error-control codes 6
2 Parameters of block error-control codes 7
3 Error detection and correction capability of block codes 10
4 Algebraic description of block codes 13
5 Coding and decoding of block codes 17
5.1 coding and decoding of block code 17
5.2 syndrome decoding of the block codes 19
5.3 majority decoding of block codes 21
6 Boundaries of block codes parameters 23
6.1 Hamming upper bound 23
6.2 Varshamov-Gilbert lower bound 24
6.3 Complexity of coding and decoding algorithms 25
7 Important classes of block codes 25
7.1 Hamming codes 25
7.2 Cyclic codes 26
8 Decoding noise immunity of block codes 31
8.1 Decoding noise immunity of block codes 31
8.2 Energy coding gain 32
9 Structure and characteristics of convolutional codes 36
9.1 Description methods of convolutional codes 36
9.2 Key parameters and classification of convolutional codes 38
10 Decoding algorithms of convolutional codes 42
10.1 Classification of decoding algorithms 42
10.2 Viterbi algorithm for decoding of convolutional codes 43
11 Noise immunity of convolutional code decoding 47
11.1 decoding error probability of convolutional code 47
11.2 Energy coding gain 48
12 Increasing of digital transmission systems efficiency 51
12.1 Information, energy and frequency efficiency 51
12.2 Limiting efficiency of transmission systems and Shannon bound 52
12.3 Perspective ways of further increasing efficiency 54
Attachment А. Performances of error-correcting codes 56
А.1 Performances and generator polynomials of cyclic codes 56
А.2 Energy coding gain by using of the cyclic codes 57
А.3 Performances of binary convolution codes 57
Attachment B. Methodical manual for the course work 59
Attachment C. Education manual for laboratory works 64
LW 4.1 Studying of block error-control Hamming code codecs structure 64
LW 4.2 Cyclic codes coding and decoding studying 66
LW 4.3 Noise immunity of block error-control codes researching 73
LW 4.4 Studying of coding and decoding by error-control convolution codes 80
Attachment D. Dictionaries 88
D.1 English-Russian dictionary 88
D.2 Russian-English dictionary 91
References 94
1 Purpose, structure and classification of error-control codes
1.1 Error-control codes in transmission systems
In theory of modern transmission systems the considerable attention to coding methods of information is given.
Coding – the operation of an identification of the symbols or groups of symbols from one code by symbols or groups of symbols to other code. Necessity of coding arises, first of all, from requirement to adapt a message form to the given communication channel or to any other device intended for transformation or storage of the information. The typical block diagram of digital telecommunication system is resulted on figure 1.1. The source produces messages which it is necessary to transfer through the channel of a telecommunication systems. It can be discrete messages (data, cable messages etc.) or continuous messages (speech, audio, TV, etc.), transformed to the digital signals. The real messages contain redundancy and for matching of the information source with a transmitting channel usually the source encoder is used. Together with decoder they form source codec. The source coding methods were studied in Module №2. The primary goal of any telecommunication system is the information transmitting with given fidelity and rate. These requirements are in contradict and increasing of information rate leads to decreasing of the noise immunity and transmitting fidelity. In agree with well known Shannon theorems, as is wished considerable increase of fidelity of information transfer if a transmitting rate through channel Rch does not exceed the channel capacity Cch basically is possible. It is reached by using of the enough long error-correcting codes.
error-control code is the code which allow to detect and correct errors arising from messages transition in the communication channels. With this purpose the redundancy is entered into structure of an error-correcting codes. Codec of error-control code (channel encoder and decoder) is shown on figure 1.1.
In real conditions the length of a code is limited by admissible complexity of coding/decoding devices. Therefore the result from using of error-control codes depends on the code parameters and restrictions on realization of the channel codec.
The modern theory offers a wide set of error-control codes, various on structure, construction principles and error detection and correction capability. In the subsequent chapters the important classes of the codes with effective coding/decoding algorithms are considered.
1.2 Classification of error-control codes
The error-control codes can be classified to various signs. The structure of codes classification is resulted on figure 1.2. On a way of formation the error-control codes are subdivided on block and continuous codes. Formation of the block codes provides splitting of transferred digital sequences into separate blocks which move to encoder input. To each such block on an encoder output there corresponds the block of code symbols which work is defined by a rule named as the coding algorithm. Formation of the continuous codes is carried out continuously in time, without division into blocks as defines the name of this code class.
Block codes historically have been discovered and studied earlier, at beginning of coding theory development. In a class of continuous codes it is necessary to note the convolutional codes which exceed on characteristics of the block codes, and, for this reason, find wide application in a transmission systems.
Many codes carry names of scientists which have discovered and investigated them. Such example is the continuous Fink-Hagelbarger’s code offered by Soviet scientist L. Fink and German expert R. Hagelbarger. Long time this code was in the literature as indicative example of a continuous code with simple encoding/decoding algorithms, but after elaborating the convolutional code has given way to them. For the description of procedures of coding/decoding both block and convolutional codes usually use an adequate mathematical apparatus. For the description of linear codes the well developed linear algebra is used. Formation of nonlinear codes is made with application of nonlinear procedures. Such approach allows to construct in some cases nonlinear codes with a number of special properties. In the error-control coding theory the problem of realisation complexity of encoding/decoding procedure and in particular decoding procedure is important. Therefore some classes of codes (Hamming codes, Bose-chaudhuri-Hochquenghem codes, Reed-Solomon codes etc.) have been developed together with the decoding algorithms connected with structural properties of these codes. And on contrary the elaborating of a new decoding algorithms for convolutional codes (Viterbi algorithm, sequential decoding, threshold decoding) initiated searches of corresponding codes. Distinctive advantages of error-control codes induced searches of new approaches to realization of ways to increase of noise immunity and efficiency of transmission systems. On figure 1.2 new methods of encoding/decoding (coded modulation, turbo-codes, time-space coding) are noted accordingly.