Exam January 2017, questions PDF

Preview

Summary

Download Exam January 2017, questions PDF

Description

CANDIDATE NUMBER:

THE UNIVERSITY OF SUSSEX

G1155

BSc/MMath EXAMINATIONS 2017 MATHEMATICS: CODING THEORY

Assessment Period: May-June 2017 (A2) You may attempt as many questions as you wish, but marks will be given for the best THREE answers only. Time allowed: TWO hours. Each question carries THIRTY marks. The numbers beside the questions indicate the approximate marks that can be gained from the corresponding parts of the questions. No calculators are allowed. DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE CHIEF INVIGILATOR. At the end of the examination the question paper and/or answer book, used or unused, will be collected from you before you leave the examination room.

Turn over/

G1155

MATHEMATICS: CODING THEORY

1.

(a) Define what is meant by the following: (i) a q-ary code C of length n; (ii) the distance d(x, y) between two elements x, y of C; (iii) the minimum distance d(C) of C.

[2 marks] [2 marks] [2 marks]

(b) Let C = {0000, 1111, 2222, 3333}. (i) Find the probability Pc of a word being correctly received if each symbol has the probability t of being incorrectly received and each wrong symbol is equally likely. [4 marks] 2 (ii) Show that Pc may be written in the form (1 − t) Q(t), where Q(t) is a quadratic function of t, and find Q(t) explicitly. [2 marks] (iii) Hence find the probability Pe of a word being wrongly received. [4 marks] (c) Prove the Sphere Packing Bound for a q-ary (n, M, 2e + 1) code: ! ! ) ( n n e (q − 1) + · · · + (q − 1) ≤ qn . M 1+ e 1 (d) Hence show, for a q-ary (q + 1, M, 3) code, that M ≤ qq−1 . 2.

(a)

[10 marks] [4 marks]

(i) What is meant by saying that an irreducible polynomial f (X) in F p [X] of degree n is primitive, where F p is the field of prime order p? [3 marks] (ii) For p = 3, list the monic quadratics, explain briefly why there are precisely three irreducible polynomials, and write them down. [6 marks] (iii) For each of the irreducible polynomials in the previous part, decide which are primitive, and give your reasons. [8 marks]

(b) Calculate the check digit s in the following ISBN-13: 978 1 4471 6788 s. [5 marks] (c) Calculate the digit w in the following Codabar number: 4539 7851 5390 w171. [8 marks]

2

MATHEMATICS: CODING THEORY 3.

G1155

(a) For a linear [n, k, d] code, define what is meant by the following: (i) a generator matrix; (ii) a parity-check matrix.

[2 marks] [2 marks]

(b) Let H be a parity-check matrix for the binary [n, k, d] code C, where    1 1 1 0 0 0 1    H =  0 1 1 1 1 0 0  .   1 0 1 0 1 1 0 (i) Find n, k, d, |C|. (ii) Find a generator matrix for C. What is d⊥ = d(C⊥ )? (iii) Show that C⊥ ⊂ C.

(c)

(i) For the code C in part (b), find coset leaders and their syndromes using the given matrix H. What special virtue does this code have? [6 marks] (ii) Decode the following received vectors: y = 1111001,

4.

[6 marks] [5 marks] [5 marks]

y′ = 0011111.

[4 marks]

(a) Describe the construction of the q−ary (n, M, d) Hamming code Ham(r, q). Find n, k, d for this code. [8 marks] (b) Construct a parity-check matrix for Ham(3, 3) with the columns in lexicographical order. [5 marks] (c) Given the fact that all non-zero words of Ham(3, 3)⊥ have the same weight, what is the weight distribution of Ham(3, 3)⊥ ? [3 marks] (d) Write down the homogeneous weight enumerator of Ham(3, 3)⊥ and use the MacWilliams identity for an [n, k]q code C, W C ⊥ (X, Y) = q−k W C (X + (q − 1)Y, X − Y), to find the homogeneous weight enumerator of Ham(3, 3).

[5 marks]

(e) Verify that the number of words of weight 2 in Ham(3, 3) is what you expect by looking at the first few terms in the resulting polynomial. (There is no need to expand the polynomial completely.) [9 marks]

3

Turn over/

G1155

MATHEMATICS: CODING THEORY

G1155 Coding Theory Answers Question 1

(a)

(i) A q-ary code of length n is a subset of (Fq )n , where Fq is a set of cardinality q. (ii) With x = (x1 , x2 , . . . , xn ),

y = (y1 , y2 , . . . , yn ), d(x, y) = |{i | xi , yi }| .

(iii) The minimum distance of a q-ary code C of length n is d(C) = min{d(x, y) | x, y ∈ C; x , y}. (b)

(i) The code C = {0000, 1111, 2222, 3333}. Hence C corrects ⌊(4 − 1)/2⌋ = 1 arbitrary error. However, some words at distance 2 from a codeword are also corrected. The received words decoded as 0000 are as follows: 0000 1; 1000, 2000, 3000 12; 1200, 2100, 1300, 3100, 2300, 3200 36. First, note that P(0 being received) = 1 − t and P(1, 2, 3 being received) = t; so P(1 being received) = P(2 being received) = P(3 being received) = 31t. Hence, the probability of correct decoding of the word 0000 is Pc = (1 − t)4 + 12(31t)(1 − t)3 + 36( 31 t)2 (1 − t)2 (ii) Hence Pc = (1 − t )2 {(1 − t )2 + 4t (1 − t) + 4t 2 } = (1 − t)2 (1 + t)2 . (iii) Hence the probability of a word being incorrectly decoded is Pe = 1 − (1 − t)2 (1 + t )2 = 1 − (1 − t 2 )2 = 2t 2 − t 4 .

4

MATHEMATICS: CODING THEORY

G1155

(c) Let S (x, r) is the ball with centre x and radius r; that is, S (x, r) = {y ∈ (Fq )n | d( x, y) ≤ r}. Also, let si = |{y ∈ (Fq )n | d(x, y) = i}|. If precisely i given positions in the word x are changed, this can be done in (q −1)i ways, since each symbol can be changed in q − 1 ways. The i positions can be chosen in ni ways. Hence ! n si = (q − 1)i . i Then |S (x, r)| =

r X i=0

! ! ! n n n + (q − 1) + · · · + (q − 1)r . si = 0 r 1

Consider each codeword x in C and a ball S (x, e) of radius e. If two balls with centres x, x′ in C had a common element y, then d(x, x′ ) ≤ d( x, y) + d(y, x′ ) ≤ e + e = 2e, contradicting that d(x, x′ ) ≥ 2e + 1. So there are M disjoint balls of radius e in (Fq )n , which has qn elements. Hence M |S (x, e)| ≤ qn , ! e X n (q − 1)i ≤ qn . M i i=0 (d) For a (q + 1, M, 3)q code, ! q+1 (q − 1)} ≤ qq+1 , M{1 + 1 M(1 + q2 − 1) ≤ qq+1 , M ≤ qq−1 .

5

Turn over/

G1155

MATHEMATICS: CODING THEORY

Question 2

(a)

(i) The polynomial f of degree n is primitive if a zero α of f in F pn has order q−1 = pn −1; that is, the smallest m ≥ 1 such that αm = 1 is m = q − 1. (ii) X 2 + bX + c over F3 = {0, 1, −1 | 3 = 0} has 9 possibilities. The reducible ones are X 2 , (X − 1)2 = X 2 + X + 1, (X + 1)2 = X 2 − X + 1, X (X − 1) = X 2 − X, X(X + 1) = X 2 + X, (X − 1)(X + 1) = X 2 − 1. This leaves the 9 − 6 = 3 irreducibles: X 2 + 1, X 2 − X − 1, X 2 + X − 1. (iii) Take X 2 + 1 and let τ2 + 1 = 0; then τ2 = −1, and τ4 = 1. So X 2 + 1 is not primitive since the order of τ is not 8. Take X 2 − X − 1 and let σ2 − σ − 1 = 0. Then σ2 = σ + 1,

σ4 = (σ + 1)2 = σ2 − σ + 1 = 1 + 1 = −1,

σ8 = 1.

So X 2 − X − 1 is primitive. If X 2 + X − 1 has a root α, then α = −σ and so also has order 8. Hence X 2 + X − 1 is primitive. (b) If x = x1 x2 · · · x13 is an ISBN-13, it satisfies x1 + 3x2 + x3 + 3 x4 + · · · + 3x12 + x13 = 0 in Z10. So 9 7 8 1 4 4 7 1 6 7 8 8 s 1 3 1 3 1 3 1 3 1 3 1 3 1 9 1 8 3 4 2 7 3 6 1 8 4 s = 56 + s Hence s = 4. (c) A Codabar number x = x1 x2 · · · x16 satisfies 2 x1 + x2 + 2 x3 + x4 + · · · + 2x15 + x16 + t = 0 in Z10, where t is the number of xi ≥ 5 for i odd. 4 5 3 9 7 8 5 1 5 3 9 0 w 1 7 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 2 1 8 5 6 9 4 8 0 1 0 3 8 0 2w 1 4 1 Positions 5, 7, 9, 11, 15 have digits at least 5. There are two possibilities. (1) The 13th digit is at least 5; in this case, 58 + 2w + 6 ≡ 0

(mod 10) ⇒ w = 8.

(2) The 13th digit is at most 4; in this case, 58 + 2w + 5 ≡ 0

(mod 10),

So the codabar number is 4539 7851 5390 8171. 6

impossible.

MATHEMATICS: CODING THEORY

G1155

Question 3

(a)

(i) A generator matrix G of an [n, k]-code C is a k × n matrix whose rows form a basis for C. (ii) A parity-check matrix H for an [n, k]-code C is an (n−k)×n matrix which is a generator matrix for C⊥ ; here, C⊥ = {y ∈ V(n, q) | y · x = 0 all x ∈ C}.

(b)

(i) Since   1  H =  0  1

1 1 0

1 1 1

0 1 0

0 1 1

0 0 1

1 0 0

    , 

so n = 7, n − k = 3 ⇒ k = 4, |C| = 16, d = 3, since some three columns are linearly dependent, such as c1 , c6 , c7 , but no two are. (ii) By row operations,   1 1   0 1 H =  1 0 h1 → h2 h3

Hence

  0   1  1

1 1 1 1 1 1

0 1 0 1 0 1

0 1 1 1 1 0

0 0 1 1 0 0

0 1 0

 1   0   0 0 0 1

    

  0  →  1  1 =

1 0 1

1 1 1

1 0 0

1 1 0

0 1 0

0 0 1

    

H′.

   1 0 0 0 0 1 1     0 1 0 0 1 1 1    = G′ .  0 0 1 0 1 0 1    0 0 0 1 1 1 0 So d⊥ = 4, since every three columns of G′ are linearly independent, but some four are dependent, such as c2 , c3 , c4 , c5 . g1 g2 g3 g4

(iii) Here h 1 = g2 + g3 + g4 ,

h 2 = g1 + g2 + g4 ,

h 3 = g1 + g2 + g3 .

Hence C⊥ ⊂ C. Alternatively, hi · h j = 0 for all i, j. (c)

(i) As n = 7 and k = 4, so C has 27−4 = 8 cosets. ℓ1 ℓ2 ℓ3 ℓ4 ℓ5 ℓ6 ℓ7 ℓ8

Coset leader ℓ 0000000 1000000 0100000 0010000 0001000 0000100 0000010 0000001

Syndrome ℓH T 000 101 110 111 010 011 001 100

As d = 3, so e = 1. As every coset leader has weight 0 or 1, this code is perfect; that is, every vector in V(7, 2) is at distance at most 1 from a unique codeword. 7

Turn over/

G1155

MATHEMATICS: CODING THEORY

(ii) y = 1111001 → yH ⊥ = 010 → x = y + ℓ5 = 1110001 ∈ C; y′ = 0011111 → yH ⊥ = 011 → x′ = y′ + ℓ6 = 0011011 ∈ C.

8

MATHEMATICS: CODING THEORY

G1155

Question 4

(a) V(r, q) is r-dimensional space over F q. Let PG(r − 1, q) be the corresponding projective space; that is, the set of equivalence classes of V(r, q)\{0} under the relation x ∼ y if y = λx for some non-zero λ ∈ F q. Pick one vector for each element of PG(r − 1, q) and let H be a matrix with these vectors as columns. Then H is a parity-check matrix for Ham(r, q); that is, Ham(r, q) = {x ∈ V(n, q) | HxT = 0}, where n= (b) Here n =

33 −1 3−1

= 13,

qr − 1 = |PG(r − 1, q)|, q−1

d = 3.

k = n − r,

k = 13 − 3 = 10.

  0 H =  0  1

0 1 0

0 1 1

0 1 2

1 0 0

1 0 1

1 0 2

1 1 0

1 1 1

1 1 2

1 2 0

1 2 1

1 2 2

Hence H is 3 × 13 with the columns in lexicographical order.

    .

(c) If Ai is the number of words of weight i in Ham(3, 3)⊥ , then A0 = 1,

A9 = 33 − 1 = 26,

Ai = 0

for i , 0, 9.

(d) With C = Ham(3, 3)⊥ , ¯ C (X, Y) = X 13 + 26X 4 Y 9 . W As W C ⊥ (X, Y) = q−k W C (X + (q − 1)Y, X − Y), so f (X, Y) = W Ham(3,3)(X, Y) 1 {(X + 2Y)13 + 26(X + 2Y )4 (X − Y )9 } = 27 (e)

f (X, Y) =

1 n 13 (X + 13X 12(2Y) + 78X 11 (2Y)2 + · · · ) 27 +26(X 4 + 4X 3 (2Y) + 6X 2 (2Y )2 + · · · ) o (X 9 − 9X 8 Y + 36X 7 Y 2 − · · · ) .

So the coefficient of X 11Y 2 in f (X, Y) is 1 1 {4 × 78 + 26(36 − 72 + 24)} = {4 × 78 − 26 × 12} = 0; 27 27 this is as expected, since d(Ham(3, 3)) = 3, whence there are no words of weight 1 or 2.

9

End of paper...