CHAPTER 2: Linear codes ABSTRACT Most of the important codes are special types of so-called linear codes. Linear codes are of importance because they have very concise description, very nice properties, very easy encoding And, in principle, quite easy decoding. Linear codes Exercise Basic properties of linear codes Basic properties of linear codes Advantages and disadvantages of linear codes I. Advantages - big. 1. Minimal distance h(C) is easy to compute if C is a linear code. 2. Linear codes have simple specifications. • To specify a non-linear code usually all codewords have to be listed. • To specify a linear [n,k] -code it is enough to list k codewords. Definition A k ´ n matrix whose rows form a basis of a linear [n,k] -code (subspace) C is said to be the generator matrix of C. Example The generator matrix of the code and of the code 3. There are simple encoding/decoding procedures for linear codes. Advantages and disadvantages of linear codes II. Disadvantages of linear codes are small: 1. Linear q -codes are not defined unless q is a prime power. 2. The restriction to linear codes might be a restriction to weaker codes than sometimes desired. Equivalence of linear codes Equivalence of linear codes Encoding with a linear code Uniqueness of encodings with linear codes Theorem If G={w[i]}[i=1]^k is a generator matrix of a binary linear code C of length n and dimension k, then v = uG ranges over all 2^k codewords of C as u ranges over all 2^k words of length k. Therefore C = { uG | u Î {0,1}^k } Moreover u[1]G = u[2]G if and only if u[1] = u[2]. Proof If then, since w[i] are linearly independent, u[1] = u[2]. Decoding of linear codes Nearest neighbour decoding scheme: Probability of good error correction Probability of good error detection Dual codes Inner product of two vectors (words) u = u[1] … u[n], v = v[1] … v[n ]in V(n,q) is an element of GF(q) defined by u × v = u[1]v[1] + … + u[n]v[n]. Example In V(4,2): 1001 × 1001 = 0 In V(4,3): 2001 × 1210 = 2 1212 × 2121 = 2 If u × v = 0 then words (vectors) u and v are called orthogonal. Properties If u, v, w Î V(n,q), l, m Î GF(q), then u × v = v × u, ( lu + mv) × w = l (u × w) + m (v × w). Given a linear [n,k] -code C, then dual code of C, denoted by C^^, is defined by C^^ = {v Î V(n,q) | v × u = 0 if u Î C}. Lemma Suppose C is an [n,k] -code having a generator matrix G. Then for v Î V(n,q) v Î C^^ <=> vG^T = 0, where G^T denotes the transpose of the matrix G. Proof Easy. PARITE CHECKS versus ORTHOGONALITY For understanding of the role the parity checks play for linear codes, it is important to understand relation between orthogonality and parity checks. If words x and y are orthogonal, then the word y has even number of ones in the positions determined by ones in the word x. This implies that if words x and y are orthogonal, then x is a parity check word for y and y is a parity check word for x. Exercise: Let the word 100001 be orthogonal to a set S of binary words of length 6. What can we say about words in S? EXAMPLE For the [n,1] -repetition code C, with the generator matrix G = (1,1, … ,1) the dual code C^^ is [n,n - 1] -code with the generator matrix G^^, described by ^ ^ Parity check matrices Parity check matrices Syndrome decoding Theorem If G = [I[k] | A] is the standard form generator matrix of an [n,k] -code C, then a parity check matrix for C is H = [-A^T | I[n-k]]. Example Definition Suppose H is a parity-check matrix of an [n,k] -code C. Then for any y Î V(n,q) the following word is called the syndrome of y: S(y) = yH^T. Lemma Two words have the same syndrom iff they are in the same coset. Syndrom decoding Assume that a standard array of a code C is given and, in addition, let in the last two columns the syndrom for each coset be given. When a word y is received, compute S(y) = yH^T, locate S(y) in the “syndrom column”, and then locate y in the same row and decode y as the codeword in the same column and in the first row. KEY OBSERVATION for SYNDROM COMPUTATION Hamming codes Hamming codes - decoding Decoding algorithm for the case the columns of H are arranged in the order of increasing binary numbers the columns represent. • Step 1 Given y compute syndrome S(y) = yH^T. • Step 2 If S(y) = 0, then y is assumed to be the codeword sent. • Step 3 If S(y) ą 0, then assuming a single error, S(y) gives the binary position of the error. Example For the Hamming code given by the parity-check matrix and the received word y = 110 1011, we get syndrome S(y) = 110 and therefore the error is in the sixth position. Hamming code was discovered by Hamming (1950), Golay (1950). 1 It was conjectured for some time that Hamming codes and two so called Golay codes are the only non-trivial perfect codes. Comment Hamming codes were originally used to deal with errors in long-distance telephon calls. ADVANTAGES of HAMMING CODES Let a binary symmetric channel is used which with probability q correctly transfers a binary symbol. If a 4-bit message is transmitted through such a channel, then correct transmission of the message occurs with probability q^4. If Hamming (7,4,3) code is used to transmit a 4-bit message, then probability of correct decoding is q^7 + 7(1 - q)q^6. In case q = 0.9 the probability of correct transmission is 0.651 in the case no error correction is used and 0.8503 in the case Hamming code is used - an essential improvement. IMPORTANT CODES GOLAY CODES - DESCRIPTION Golay codes G[24] and G[23] were used by Voyager I and Voyager II to transmit color pictures of Jupiter and Saturn. Generation matrix for G[24] has the form G[24] is (24,12,8) –code and the weights of all codewords are multiples of 4. G[23] is obtained from G[24] by deleting last symbols of each codeword of G[24]. G[23] is (23,12,7) –code. GOLAY CODES - CONSTRUCTION Matrix G for Golay code G[24] has actually a simple and regular construction. The first 12 columns are formed by a unitary matrix I[12], next column has all 1’s. Rows of the last 11 columns are cyclic permutations of the first row which has 1 at those positions that are squares modulo 11, that is 0, 1, 3, 4, 5, 9. SINGLETON BOUND REED-MULLER CODES Reed-Muller codes form a family of codes defined recursively with interesting properties and easy decoding. If D[1] is a binary [n,k[1],d[1]] -code and D[2] is a binary [n,k[2],d[2]] -code, a binary code C of length 2n is defined as follows C = { | u | u + v |, where u Î D[1], v Î D[2]}. Lemma C is [2n,k[1] + k[2], min{2d[1],d[2]}] -code and if G[i] is a generator matrix for D[i], i = 1, 2, then is a generator matrix for C. Reed-Muller codes R(r,m), with 0 Ł r Ł m are binary codes of length n = 2^m. R(m,m) is the whole set of words of length n, R(0,m) is the repetition code. If 0 < r < m, then R(r + 1,m + 1) is obtained from codes R(r + 1,m) and R(r,m) by the above construction. Theorem The dimension of R(r,m) equals The minimum weight of R(r,m) equals 2^m ^- ^r. Codes R(m - r - 1,m) and R(r,m) are dual codes. Singleton Bound Singleton bound: Let C be a q-ary (n, M, d)-code. Then M Ł q ^n-d+1 . Proof Take some d − 1 coordinates and project all codewords to the resulting coordinates. The resulting codewords are all different and therefore M cannot be larger than the number of q-ary words of length n−d−1. Codes for which M = q ^n−d−1 are called MDS-codes (Maximum Distance Separable). Corollary: If C is a q-ary linear [n, k, d]-code, then k + d Ł n + 1. Shortening and puncturing of linear codes Let C be a q-ary linear [n, k, d]-code. Let D = {(x[1], ... , x[n-1]) | (x[1], ... , x[n-1], 0)ÎC}. Then D is a linear [n-1, k-1, d]-code – a shortening of the code C. Corollary: If there is a q-ary [n, k, d]-code, then shortening yields a q-ary [n−1, k−1, d]-code. Let C be a q-ary [n, k, d]-code. Let E = {(x[1], ... , x[n-1]) | (x[1], ... , x[n-1], x)ÎC, for some x Ł q}, then E is a linear [n-1, k, d-1]-code – a puncturing of the code C. Corollary: If there is a q-ary [n, k, d]-code with d >1, then there is a q-ary [n−1, k, d-1]-code. Lengthening of Codes – Constructions X and XX Construction X Let C ⊃ D be q-nary linear codes with parameters [n, K, d] and [n, k, D], where D > d, and K > k. Assume also that there exists a q-nary code E with parameters [l, K − k, δ ]. Then there is a ”longer” q-nary code with parameters [n + l, K, min(d + δ, D)]. The lengthening of C is constructed by appending φ(x) to each word x ∈ C, where φ : C/D → E is a bijection – a well known application of this construction is the addition of the parity bit in binary codes. Construction XX Let the following q-ary codes be given: a code C with parameters [n, k, d]; its sub-codes C[i] , i = 1,2 with parameters [n, k − k[i] , d[i]] and with C[1] ∩ C[2] of minimum distance ≥ D; auxiliary q-nary codes E[i] , i = 1,2 with parameters [l[i] , k[i] , δ[i]]. Then there is a q-ary code with parameters [n + l[1] + l[2] , k, min{D, d[2] + δ[1], d[1] + δ[2] , d + δ[1] + δ[2]}]. Strength of Codes • Strength of codes is another important parameter of codes. It is defined through the concept of the strength of so-called orthogonal arrays - an important concepts of combinatorics. • An orthogonal array QA[λ](t, n, q) is an array of n columns, λq ^t rows with elements from F[q] and the property that in the projection onto any set of t columns each possible t-tuple occurs the same number λ of times. t is called strength of such an orthogonal array. • For a code C, let t(C) be the strength of C - if C is taken as an orthogonal array. • Importance of the concept of strength follows also from the following Principle of duality: For any code C its minimum distance and the strength of C^⊥ are closely related. Namely d(C) = t(C^⊥) + 1. Dimension of Dual Linear Codes If C is an [n, k]-code, then its dual code C^⊥ is [n, n − k] code. A binary linear [n, 1] repetition code with codewords of length n has two codewords: all-0 codeword and all-1 codeword. Dual code to [n, 1] repetition code is so-called sum zero code of all binary n-bit words whose entries sum to zero (modulo 2). It is a code of dimension n − 1 and it is a linear [n, n − 1, 2] code Reed-Solomon Codes An important example of MDS-codes are q-ary Reed-Solomon codes RSC(k, q), for k ≤ q. They are codes generator matrix of which has rows labeled by polynomials X ^i, 0 ≤ i ≤ k − 1, columns by elements 0, 1, . . . , q − 1 and the element in a row labeled by a polynomial p and in a column labeled by an element u is p(u). RSC(k, q) code is [q, k, q − k + 1] code. Example Generator matrix for RSC(3, 5) code is Interesting property of Reed-Solomon codes: RSC(k, q)^⊥ = RSC(q − k, q). Reed-Solomon codes are used in digital television, satellite communication, wireless communication, barcodes, compact discs, DVD,... They are very good to correct burst errors - such as ones caused by solar energy. Trace and Subfield Codes • Let p be a prime and r an integer. A trace tr is mapping from F[p]r into F[p] defined by tr(x) = • Trace is additive (tr(x[1] + x[2]) = tr(x[1]) + tr(x[2])) and F[p]-linear (tr(λx) = λtr(x)). • If C is a linear code over F[p]r and tr is a trace mapping from F[p]r to F[p], then trace code tr(C) is a code over F[p] defined by (tr(x[1]), tr(x[2]), . . . , tr(x[n])) where (x[1], x[2], . . . , x[n]) ∈ C. • If C ⊂ F^n[p]r is a linear code of strength t, then strength of tr(C) is at least t. • Let C ⊂ F^n[p]r be a linear code. The subfield code C[F]p consists of those codewords of C all of whose entries are in F[p]. • Delsarte theorem If C ⊂ F^n[p]r is a linear code. Then tr(C)^⊥ = (C^⊥)[F]p . Soccer Games Betting System Ternary Golay code with parameters (11, 729, 5) can be used to bet for results of 11 soccer games with potential outcomes 1 (if home team wins), 2 (if guests win) and 3 (in case of a draw). If 729 bets are made, then at least one bet has at least 9 results correctly guessed. In case one has to bet for 13 games, then one can usually have two games with pretty sure outcomes and for the rest one can use the above ternary Golay code.