Department of the Telecommunication theory named after A.G. Zuko

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 datafor 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. 18

5.1 coding and decoding of block code. 18

5.2 syndrome decoding of the block codes. 20

5.3 majority decoding of block codes. 21

6 Boundaries of block codes parameters. 24

6.1 Hamming upper bound. 24

6.2 Varshamov-Gilbert lower bound. 25

6.3 Complexity of coding and decoding algorithms. 26

7 Important classes of block codes. 26

7.1 Hamming codes. 26

7.2 Cyclic codes. 27

8 Decoding noise immunity of block codes. 32

8.1 Decoding noise immunity of block codes. 32

8.2 Energy coding gain. 34

9 Structure and characteristics of convolutional codes. 37

9.1 Description methods of convolutional codes. 37

9.2 Key parameters and classification of convolutional codes. 40

10 Decoding algorithms of convolutional codes. 43

10.1 Classification of decoding algorithms. 43

10.2 Viterbi algorithm for decoding of convolutional codes. 45

11 Noise immunity of convolutional code decoding. 49

11.1 decoding error probability of convolutional code. 49

11.2 Energy coding gain. 50

12 Increasing of digital transmission systems efficiency. 52

12.1 Information, energy and frequency efficiency. 52

12.2 Limiting efficiency of transmission systems and Shannon bound. 53

12.3 Perspective ways of further increasing efficiency. 55

Attachment А. Performances of error-correcting codes. 57

А.1 Performances and generator polynomials of cyclic codes. 57

А.2 Energy coding gain by using of the cyclic codes. 58

А.3 Performances of binary convolution codes. 58

Attachment B. Methodical manual for the course work. 60

Attachment C. Education manual for laboratory works. 65

LW 4.1 Studying of block error-control Hamming code codecs structure. 65

LW 4.2 Cyclic codes coding and decoding studying. 67

LW 4.3 Noise immunity of block error-control codes researching. 74

LW 4.4 Studying of coding and decoding by error-control convolution codes. 81

Attachment D. Dictionaries. 89

D.1 English-Russian dictionary. 89

D.2 Russian-English dictionary. 92

References. 95

1 Purpose, structure and classification
of error-control codes