CHAPTER 3: Cyclic and convolution codes Cyclic codes are of interest and importance because • They posses a rich algebraic structure that can be utilized in a variety of ways. • They have extremely concise specifications. • They can be efficiently implemented using simple shift registers. • Many practically important codes are cyclic. Convolution codes allow to encode streams od data (bits). IMPORTANT NOTE In order to specify a binary code with 2^k codewords of length n one may need to write down 2^k codewords of length n. In order to specify a linear binary code with 2^k codewords of length n it is sufficient to write down k codewords of length n. In order to specify a binary cyclic code with 2^k codewords of length n it is sufficient to write down 1 codeword of length n. BASIC DEFINITION AND EXAMPLES FREQUENCY of CYCLIC CODES Comparing with linear codes, the cyclic codes are quite scarce. For, example there are 11 811 linear (7,3) linear binary codes, but only two of them are cyclic. Trivial cyclic codes. For any field F and any integer n >= 3 there are always the following cyclic codes of length n over F: • No-information code - code consisting of just one all-zero codeword. • Repetition code - code consisting of codewords (a, a, …,a) for a Î F. • Single-parity-check code - code consisting of all codewords with parity 0. • No-parity code - code consisting of all codewords of length n For some cases, for example for n = 19 and F = GF(2), the above four trivial cyclic codes are the only cyclic codes. EXAMPLE of a CYCLIC CODE The code with the generator matrix has codewords c[1 ] = 1011100 c[2] = 0101110 c[3] =0010111 c[1] + c[2] = 1110010 c[1] + c[3] = 1001011 c[2] + c[3] = 0111001 c[1] + c[2] + c[3] = 1100101 and it is cyclic because the right shifts have the following impacts c[1] ® c[2], c[2] ® c[3], c[3] ® c[1] + c[3 ] c[1] + c[2] ® c[2] + c[3], c[1] + c[3] ® c[1] + c[2] + c[3], c[2] + c[3] ® c[1 ]c[1] + c[2] + c[3] ® c[1] + c[2 ]POLYNOMIALS over GF(q) RING of POLYNOMIALS FIELD R[n], R[n] = F[q][x] / (x^n - 1) Computation modulo x^n – 1 Since x^n -o 1 (mod x^n -1) we can compute f(x) mod x^n -1 as follow: In f(x) replace x^n by 1, x^n +1 by x, x^n +2 by x^2, x^n +3 by x^3, … Identification of words with polynomials a[0] a[1]… a[n -1] « a[0] + a[1] x + a[2] x^2 + … + a[n -1] x^n -1 Multiplication by x in R[n] corresponds to a single cyclic shift x (a[0] + a[1] x + … a[n -1] x^n -1) = a[n -1] + a[0] x + a[1] x^2 + … + a[n -2] x^n -1 Algebraic characterization of cyclic codes Theorem A code C is cyclic if C satisfies two conditions (i) a(x), b(x) Î C TH a(x) + b(x) Î C (ii) a(x) Î C, r(x) Î R[n] TH[ ] r(x)a(x) Î C Proof (1) Let C be a cyclic code. C is linear TH (i) holds. (ii) Let a(x) Î C, r(x) = r[0] + r[1]x + … + r[n -1]x^n -1 r(x)a(x) = r[0]a(x) + r[1]xa(x) + … + r[n -1]x^n -1a(x) is in C by (i) because summands are cyclic shifts of a(x). (2) Let (i) and (ii) hold · Taking r(x) to be a scalar the conditions imply linearity of C. · Taking r(x) = x the conditions imply cyclicity of C. CONSTRUCTION of CYCLIC CODES Characterization theorem for cyclic codes Characterization theorem for cyclic codes HOW TO DESIGN CYCLIC CODES? The last claim of the previous theorem gives a recipe how to get all cyclic codes of the given length n. Indeed, all we need to do is to find all factors of x^n -1. Problem: Find all binary cyclic codes of length 3. Solution: Since x^3 – 1 = (x + 1)(x^2 + x + 1) both factors are irreducible in GF(2) we have the following generator polynomials and codes. Generator polynomials Code in R[3] Code in V(3,2) 1 R[3] V(3,2) x + 1 {0, 1 + x, x + x^2, 1 + x^2} {000, 110, 011, 101} x^2 + x + 1 {0, 1 + x + x^2} {000, 111} x^3 – 1 ( = 0) {0} {000} Design of generator matrices for cyclic codes EXAMPLE The task is to determine all ternary codes of length 4 and generators for them. Factorization of x^4 - 1 over GF(3) has the form x^4 - 1 = (x - 1)(x^3 + x^2 + x + 1) = (x - 1)(x + 1)(x^2 + 1) Therefore there are 2^3 = 8 divisors of x^4 - 1 and each generates a cyclic code. Generator polynomial Generator matrix 1 I[4 ] x-1 x + 1 x^2 + 1 (x - 1)(x + 1) = x^2 - 1 (x - 1)(x^2 + 1) = x^3 - x^2 + x - 1 [ -1 1 -1 1 ] (x + 1)(x^2 + 1) [ 1 1 1 1 ] x^4 - 1 = 0 [ 0 0 0 0 ] Check polynomials and parity check matrices for cyclic codes POLYNOMIAL REPRESENTATION of DUAL CODES Since dim (áh(x)n) = n - k = dim (C^^) we might easily be fooled to think that the check polynomial h(x) of the code C generates the dual code C^^. Reality is “slightly different'': Theorem Suppose C is a cyclic [n,k]-code with the check polynomial h(x) = h[0] + h[1]x + … + h[k]x^k, then (i) a parity-check matrix for C is (ii) C^^ is the cyclic code generated by the polynomial i.e. the reciprocal polynomial of h(x). POLYNOMIAL REPRESENTATION of DUAL CODES Proof A polynomial c(x) = c[0] + c[1]x + … + c[n -1]x^n –1 represents a code from C if c(x)h(x) = 0. For c(x)h(x) to be 0 the coefficients at x^k,…, x^n -1 must be zero, i.e. Therefore, any codeword c[0] c[1]… c[n -1] Î C is orthogonal to the word h[k] h[k -1]…h[0]00…0 and to its cyclic shifts. Rows of the matrix H are therefore in C^^. Moreover, since h[k] = 1, these row-vectors are linearly independent. Their number is n - k = dim (C^^). Hence H is a generator matrix for C^^, i.e. a parity-check matrix for C. In order to show that C^^ is a cyclic code generated by the polynomial it is sufficient to show that is a factor of x^n -1. Observe that and since h(x ^-1)g(x ^-1) = (x ^-1)^n -1 we have that x^kh(x ^-1)x^n -kg(x ^-1) = x^n(x ^–n -1) = 1 – x^n and therefore is indeed a factor of x^n -1. ENCODING with CYCLIC CODES I Encoding using a cyclic code can be done by a multiplication of two polynomials - a message polynomial and the generating polynomial for the cyclic code. Let C be an (n,k)-code over an field F with the generator polynomial g(x) = g[0] + g[1] x + … + g[r –1] x ^r -1 of degree r = n - k. If a message vector m is represented by a polynomial m(x) of degree k and m is encoded by m TH c = mG, then the following relation between m(x) and c(x) holds c(x) = m(x)g(x). Such an encoding can be realized by the shift register shown in Figure below, where input is the k-bit message to be encoded followed by n - k 0' and the output will be the encoded message. Shift-register encodings of cyclic codes. Small circles represent multiplication by the corresponding constant, AA nodes represent modular addition, squares are delay elements Hamming codes as cyclic codes Hamming codes as cyclic codes Example Polynomial x^3 + x + 1 is irreducible over GF(2) and x is primitive element of the field F[2][x] / (x^3 + x + 1). F[2][x] / (x^3 + x + 1) = {0, x, x^2, x^3 = x + 1, x^4 = x^2 + x, x^5 = x^2 + x + 1, x^6 = x^2 + 1} The parity-check matrix for a cyclic version of Ham (3,2) PROOF of THEOREM The binary Hamming code Ham (r,2) is equivalent to a cyclic code. It is known from algebra that if p(x) is an irreducible polynomial of degree r, then the ring F[2][x] / p(x) is a field of order 2^r. In addition, every finite field has a primitive element. Therefore, there exists an element a of F[2][x] / p(x) such that F[2][x] / p(x) = {0, 1, a, a^2,…, a^2r ^–2}. Let us identify an element a[0] + a[1] + … a[r -1]x^r -1 of F[2][x] / p(x) with the column vector (a[0], a[1],…, a[r -1])^T and consider the binary r * (2^r -1) matrix H = [ 1 a a^2 … a^2^r –2 ]. Let now C be the binary linear code having H as a parity check matrix. Since the columns of H are all distinct non-zero vectors of V(r,2), C = Ham (r,2). Putting n = 2^r -1 we get C = {f[0] f[1] … f[n -1] Î V(n, 2) | f[0] + f[1] a + … + f[n -1] a^n –1 = 0 (2) = {f(x) Î R[n] | f(a) = 0 in F[2][x] / p(x)} (3) If f(x) Î C and r(x) Î R[n], then r(x)f(x) Î C because r(a)f(a) = r(a) · 0 = 0 and therefore, by one of the previous theorems, this version of Ham (r,2) is cyclic. BCH codes and Reed-Solomon codes CONVOLUTION CODES ENCODING of FINITE POLYNOMIALS An (n,k) convolution code with a k x n generator matrix G can be used to encode a k-tuple of plain-polynomials (polynomial input information) I=(I[0](x), I[1](x),…,I[k-1](x)) to get an n-tuple of crypto-polynomials C=(C[0](x), C[1](x),…,C[n-1](x)) As follows C= I . G EXAMPLES ENCODING of INFINITE INPUT STREAMS The way infinite streams are encoded using convolution codes will be Illustrated on the code CC[1]. An input stream I = (I[0], I[1], I[2],…) is mapped into the output stream C= (C[00], C[10], C[01], C[11]…) defined by C[0](x) = C[00] + C[01]x + … = (x^2 + 1) I(x) and C[1](x) = C[10] + C[11]x + … = (x^2 + x + 1) I(x). The first multiplication can be done by the first shift register from the next figure; second multiplication can be performed by the second shift register on the next slide and it holds C[0i] = I[i] + I[i+2], C[1i] = I[i] + I[i-1] + I[i-2]. That is the output streams C[0] and C[1] are obtained by convolving the input stream with polynomials of G[1’ ] [ ]ENCODING ENCODING and DECODING