Course: Teacher: Group: Information Theory and Coding Piotr Chołda Electronics and Telecommunications, M.Sc. studies, 1st sem., Spring 2015 .............................................................................. Draft of a lecture with exercises April 22, 2015 1 Lecture VII (April 24, 2015): Hamming coding and operations on linear codes 1.1 Binary Hamming codes 1. Basic parameters: n = 2c − 1, k = 2c − 1 − c, where c is the number of parity-check symbols. 2. Hamming codes are the perfect codes (we attain the equality in the Hamming bound) with dmin = 3, thus they correct only single errors. 3. Parity-check matrix for Hamming code (2c − 1, 2c − 1 − c) is always constructed from columns that form the binary representations of consecutive numbers from 1 to 2c − 1. Thus, Hamming code is not a systematic code (H is not in a canonical form). 4. Syndrome decoding of Hamming codes: due to the specific form of paritycheck matrices for Hamming codes, the decoding of these codes consists in correcting the selected single position of the obtained word. This position number is represented in a binary form by the calculated syndrome (if only s 6= 0). 1.2 Operations on linear codes 1. Modifications on a single linear code (n, k): ? Lengthening (wydłużanie) of a code: – idea: an information symbol is added; – if G is in the canonical form: column and row of the same number are added, and a column is added to H; – kLe = k + 1; – nLe = n + 1; – dminLe ≤ dmin ; – the inverse operation: shortening (skracanie) — for saving transmission resources. ? Extending (rozszerzanie) of a code: – idea: a parity-check symbol is added (to improve reliability); Page 1 Course: Teacher: Group: Information Theory and Coding Piotr Chołda Electronics and Telecommunications, M.Sc. studies, 1st sem., Spring 2015 .............................................................................. Table 1: Changes related to linear code modifications Modification Lengthening Shortening Extending Puncturing Augmenting Expurgating nmod nLe ↑ nSh ↓ nEt ↑ nP u ↓ nAu nEp kmod kLe ↑ kSh ↓ kEt kPu kAu ↑ kEp ↓ dminmod dminLe ↓ dminSh ↑ dminEt ↑ dminP u ↓ dminAu ↓ dminEp ↑ – a new column is added in G and both new row and column are added in H; – nEt = n + 1; – kEt = k; – dminEt ≥ dmin ; – the inverse operation: puncturing (przebijanie). ? Augmenting (powiększanie) of a code: – idea: new codewords are added in a structured way (to spare the transmission resources — at a price of reduced reliability) — after the operation there are twice as many codewords as before; – a new row is added to G and row i is removed from H with the modification of column i in H (i.e. a parity check position starts to be used as an information-carrying position); – nAu = n. – kAu = k + 1. – dminAu ≤ dmin . – the inverse operation: expurgating (okrajanie). ? Summary on the modifications of a single linear code is given in Table 1. 2. Creation of linear codes on the basis of various linear codes: ? Joined codes (kody łączone): – we must have m codes with the same parameter k — (ni , k) for code i (non necessarily systematic); – a codeword of the joined code is made up by joining bit-by-bit m codewords (each from different code (ni , k)) encoding the same information sequence u; – parameters of joined codes: P ∗ n = i ni ; ∗ k = ki , because k1 = k2 = . . . ; P ∗ dmin = i dmini . Example: – m = 2, Page 2 Course: Teacher: Group: Information Theory and Coding Piotr Chołda Electronics and Telecommunications, M.Sc. studies, 1st sem., Spring 2015 .............................................................................. – code A — (5, 2), code B — (6, 2), – n = 11, k = 2. We ask: what is the codeword encoding u = 11 in a joined code obtained from codes A and B? Answer: – in code 1 information u = 11 is encoded as e.g. |{z} 11 |000, u – in code 2 information u = 11 is encoded as e.g. 101| |{z} 11 |0, u – thus, in the joined code u = 11 will be encoded as 11000101110. ? Iterated (product) codes (kody iterowane): – we must have m codes with not necessarily identical parameters (ni , ki ) for code i (the codes are systematic); – a codeword of the iterated code is made up by constructing a matrix for m = 2, a cube for m = 3, or a hypercube of dimension m ≥ 4; – information symbols in the codeword are determined by the information to be sent u (of length k1 × k2 × . . . ); the paritycheck symbols are generated according to the rule of constructing parity-check symbols of code i on the basis of the information symbols subset ui related only to dimension i of the matrix, cube or hypercube; – parameters: Q ∗ n = i ni , Q ∗ k = i ki , Q ∗ dmin = i dmini . Example: – m = 2, – code A — (3, 2) and code B — (4, 3) ⇒ n = 12, k = 6. We ask: what is the codeword encoding u = 000110 in an iterated code obtained from codes A and B? Answer: – in code 1 information 00 is encoded as e.g. 00|0, 01 as e.g. 01|1, 10 as e.g. 10|1, and 11 as e.g. 11|0; – in code 2 information 001 is encoded as e.g. 001|1, and 010 as e.g. 010|1; – thus, in the iterated code u = 000110 will be encoded as: 0 0 0 0 1 1 1 0 1 ⇒ 000|011|101|110 1 1 0 1.3 Exercises 1. Hamming codes: (a) Which of the following sequences are codewords of a Hamming code: Page 3 Course: Teacher: Group: Information Theory and Coding Piotr Chołda Electronics and Telecommunications, M.Sc. studies, 1st sem., Spring 2015 .............................................................................. 01101011011000 011010110110000 10000010000011 100000100000011 11010110111111 110010110111111 (b) Find the probability of the wrong decoding decision for a decoder of the Hamming code (7, 4), if single bit errors are independent and their probabilities are equal to 10−3 . What is the ratio of the probability of the occurrence of errors correctable by the decoder to the probability of the occurrence of a codeword error? (c) Let a be a binary representation of the last digit of your student’s book ID. Let b = 0 . . . 0a and c = 1 . . . 1a be different binary information sequences of lengths selected accordingly (i.e., it is necessary to find the number of zeros/ones added at the beginning), so that they can be encoded with a binary Hamming code. Find the Hamming distance between the codewords representing information sequences b and c. (d) A binary Hamming code (n, k) with five parity-check symbols is given. Find the following sequences: ? x1 i x2 : two codewords, so that the Hamming distance between them is equal to five. ? y1 i y2 : two errored codewords, so that the Hamming distance between them is equal to nine. (e) Find the maximum Hamming distance dmax of a Hamming code that contains seven redundant positions. dmax is defined analogously to dmin , that is, for code C: dmax (C) = max {d (xi , xj ) : xi , xj ∈ C ∧ xi 6= xj } , where d (xi , xj ) is a Hamming distance between two codewords of code C. 2. Modifications of linear codes: (a) Find the syndrome related to the binary sequence: y = 1011110101, obtained by a decoder of a shortened Hamming code. What will be the decoder decision? (b) Show that the shortened Hamming code (6, 3) is not a perfect code. 3. Operation on two (or more) linear codes: (a) Determine the minimum number of repetitions of non-redundant binary code, that allows for correction of all single and double errors. (b) Determine the improvement of correction properties of parity-check code (4, 3), if it is replaced with the double iterated code. Find the rate of this code and analyze the operation of the decoder when the transmission is: ? not disturbed by errors, ? disturbed by a single error, Page 4 Course: Teacher: Group: Information Theory and Coding Piotr Chołda Electronics and Telecommunications, M.Sc. studies, 1st sem., Spring 2015 .............................................................................. ? disturbed by two errors, ? disturbed by more errors. (c) Find the generator matrix of the double iterated code, in which columns and rows are encoded with the codes of the following generator matrices: 1 0 1 G1 = G2 = . 0 1 1 Moreover, find the minimum Hamming distance on the basis of the parity-check matrix for this iterated code. 4. Others (*): (a) Find a number of codewords of weight three in a Hamming code containing six redundant positions. 1.4 Bibliography The contents of this lecture is based on the following books: ? Dominic Welsh. Codes and Cryptography. Clarendon Press, Oxford, UK, 1988: chapters 4.6, 4.8. ? Todd K. Moon. Error Correction Coding. John Wiley & Sons, Inc., Hoboken, NJ, 2005: chapters 1.9, 8. ? Stefan M. Moser and Po-Ning Chen. A Student’s Guide to Coding and Information Theory. Cambridge University Press, Cambridge, UK, 2012: chapters 3.3, 8.1-8.2. Page 5

© Copyright 2017