Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MATH32032
SECTION A Answer ALL questions in this section (40 marks in total) A1. (a) Define what is meant by: —
a word x of length n in a finite alphabet F ; — a code C of length n in a finite alphabet F ; —
the Hamming distance d(x, y) between two words x, y of length n; — a nearest neighbour of a word x in a code C.
(b) Let C be the binary repetition code of length 6. List the codewords of C. Write down words x, y ∈ F62
such that x has exactly one nearest neighbour in C, and y has more than one nearest neighbour in C. [10 marks] A2.
(a) Explain what is meant by a standard array for a linear [n, k, d]q-code C. State the number of rows and the number
of columns in a standard array for C. Explain how to decode a received vector using the standard array. You are now
given that D = {0000, 0111, v, 1110} is a binary linear code. (b) Prove that the vector v is 1001. Assuming that a codevector of D is sent via BSC(p), show that, with probability p2 − p4, the received vector will contain an error which is not detected. (c) Construct a standard array for D. Use the standard array you have constructed to give an example where one bit error occurs in a codevector c of D and is not corrected by the standard array decoder. (d) Assume that y, z ∈ F42, y 6= z, and that H is a parity check matrix for the code D such that yHT = zHT . Can y and z occur in the same column of the standard array that you constructed in part (c)? Justify your answer briefly. [20 marks] A3. (a) Define what is meant by a line in the vector space Frq. Explain how to construct a check matrix H for a Hamming Ham(r, q)-code. State without proof the number of rows and the number of columns of H. (b) Write down a check matrix of a ternary Ham(2, 3)-code. (c) Write down a check matrix of a Ham(2, 5)-code C ⊆ F65 such that C contains the vector 111111. [10 marks] Page 2 of 3 P.T.O. MATH32032 SECTION B Answer TWO of the three questions in this section (40 marks in total). If more than TWO questions from this section are attempted, then credit will be given for the best TWO answers. B4. In this question, F is a finite alphabet of cardinality q, and C ⊆ F n is a code of cardinality M > 1. (a) Define what is meant by the minimum distance, d(C), of the code C. (b) Prove the Singleton bound which says that M 6 qn−d(C)+1. (c) Let r be an integer between 0 and n. Define the Hamming sphere Sr(u) of radius r centred at u ∈ F n. State and prove the formula for the cardinality of Sr(u) in terms of r, n and q. (d) State without proof the Hamming bound on M in terms of n, q and d(C). Define what is meant by saying that C is a perfect code. (e) Show that if n = q = 60 and C is perfect, then d(C) 6= 7. Hint: you may use the Singleton bound. [20 marks] B5. In this question, C ⊆ Fnq is a linear code of dimension k. (a) Define what is meant by the inner product x · y of two vectors x, y ∈ Fnq , and what is meant by the dual code C⊥. State without proof the length and the dimension of C⊥. (b) Recall that C is self-orthogonal if C ⊆ C⊥. Prove that if C has a generator matrix G such that GGT is a zero matrix, then C is self-orthogonal. (c) A self-orthogonal code D ⊆ F4q has generator matrix [ 1 2 −1 2 2 1 2 −1 ] . Find a prime number q > 2 for which this is possible. Then write down a check matrix for D, explaining how it is obtained. (d) Assume that q = 2 and C ⊆ C⊥. Let WC(x, y) = ∑n i=0Aix n−iyi be the weight enumerator of C. Prove that A2 6 k and that A2(A2 − 1)/2 6 A4. [20 marks] B6. In this question, we assume that vectors in Fnq are identified with polynomials, in Fq[x], of degree less than n in the usual way. (a) Let C ⊆ Fnq be a cyclic code. Explain what is meant by a generator polynomial of C. Show that there exists at most one generator polynomial of C. (b) Let Z ⊆ F87 be the cyclic code with generator polynomial x − 1. Write down a generator matrix for Z. Prove that Z = {(v1, v2, v3, v4, v5, v6, v7, v8) ∈ F87 : ∑8 i=1 vi = 0 in F7}. You may use the factorisation (x− 1)(x+1)(x2+1)(x2− 3x+1)(x2+3x+1) of x8− 1 into irreducible monic polynomials in F7[x] to answer the following questions. (c) Determine: (i) the total number of cyclic codes C ⊆ F87; (ii) the number of cyclic codes C ⊆ F87 such that C ⊆ Z where Z is the code from part (b). Justify your answers briefly. (d) Prove that none of the cyclic codes in F87 is a Hamming code. Any facts from the course can be freely used. [20 marks] END OF EXAMINATION PAPER