Teoria informacji i kodowania

Block codes Basic concepts and definitions A source information is processed, first, in a channel encoder, next, in a discrete memoryless channel and finally, in a channel decoder, as presented in Fig.5.1.1. The output sequence ; , is the result of mod-2 addition of a codeword ; , and error patter...

Channel capacity Channel capacity of DMC is defined as the largest mutual information that can be transmitted over the channel in one use, maximized over all input probability assignments . It is worth to observe that, whereas is a function of both the channel and the input probability assignment,...

Construction of the generator matrix of a RM( r , p ) code Step 0. The first row of G is the all-1 codeword: . Step 1. The next rows, the 1 st order codewords, form submatrix 0 1 n 1 The l -th column is the integer l in the binary code: . Step 2. The next rows, the 2 nd order codewords, fo...

Decoding cyclic codes Following the Conclusion to check whether the received sequence is a code word of an cyclic code, is divided by , a reminder is designated. This reminder can be considered as syndrome polynomial of , and it determines a decoder decision, following the strategy of (5.2.25) for...

Extended linear code Error control capability of an linear code can be improved by adding an overall parity-check bit. An extended code is obtained. The addition of such bit increases a code minimum distance by one. For the Hamming extended code: , what enables single-error correction and also doub...

General description Encoding and decoding An linear code is called a cyclic code if a cyclic shift of any codeword is also a codeword. The shift may be leftwards or rightwards, by any number of bits. The cyclic code nature can be utilized when encoding and decoding, using linear-feedback shift reg...

Generator matrix and parity check matrix of cyclic codes Generator matrix consists of algebraically independent subset of k codewords. These words can be words with weight of information part equal 1, i.e. words with information bits encoding integers: , in polynomial notation: . Then, following st...

Generator matrix Any algebraically independent subset of k nonzero codewords uniquely defines an ( n , k ) linear code. Such subset consists a code-base, that can be considered as rows of the so called generator matrix: To obtain all possible combinations of generator matrix rows, matrix G has to ...

Generator polynomial Consider nonzero codeword of a cyclic code having the smallest degree of its polynomial, i.e. having the longest all-zero sequence at first (leftmost) bits: . For the considered cyclic code (7,4), defined by parity-check matrix (7.1.1), : . Each cyclic shift of this word is als...

Hamming code 7 4 is the first code in the class of Hamming codes. Error syndromes, corresponding to single-error patterns, are written as binary words: that encode a position of nonzero bit in z , as presented in Table i 1 1 001 2 01 010 3 001 011 4 0001000 100 5 100 101 6 10 110...