Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
Online Alternative Assessments MTH6108 / MTH6108P: Coding Theory
You should attempt ALL questions.
Marks available are shown next to the ques- tions. In completing this assessment, you may use books, notes, and the internet. You may use calculators and computers, but you should show your working for any calculations you do. You must not seek or obtain help from anyone else. At the start of your work, please copy out and sign the following declaration: I declare that my submission is entirely my own, and I have not sought or obtained help from anyone else. All work should be handwritten, and should include your student number. You have 24 hours in which to complete and submit this assessment. When you have finished your work: • scan your work, convert it to a single PDF file and upload this using the upload tool on the QMplus page for the module; • e-mail a copy to [email protected] with your student number and the module code in the subject line; • with your e-mail, include a photograph of the first page of your work together with either yourself or your student ID card. You are not expected to spend a long time working on this assessment. We expect you to spend about 2 hours to complete the assessment, plus the time taken to scan and upload your work. Please try to upload your work well before the end of the assessment period, in case you experience computer problems. Only one attempt is allowed – once you have submitted your work, it is final. Examiners: S. Sasaki, I. Tomasˇic´ c
Continue to next page MTH6108 / MTH6108P (2020) Page 2 Question 1 [25 marks]. (a) What is the minimum distance of the code {LONDON, BERLIN, DUBLIN, LISBON} over the alphabetA = {A, B, . . . , Z}? [3] (b) Find a 4-ary code that is 3-error-detecting but not 2-error-correcting. [4] (c) Compute the following numbers and justify your answers. State clearly any results you use from the lectures without proofs. (i) A2(4, 3) [5] (ii) A3(4, 3) [5] (d) Prove that A3(7, 4) ≤ 57. State clearly any results you use from the lectures without proofs. [8] Question 2 [10 marks]. Let C be the code {000, 010, 101} of length 3 over A = {0, 1}. (a) Find a nearest-neighbour decoding process for C. [5] (b) If the symbol error probability is 13 , what is the word error probability for the word 010? Justify your answer. [5] c© Queen Mary University of London (2020) Continue to next page MTH6108 / MTH6108P (2020) Page 3 Question 3 [25 marks]. (a) Prove that {x1x2x3x4 ∈ F4q | x1 + x2 + x3 = x2 + x3 + x4 = 0} is a linear [4, 2, 2]-code over Fq (where q is a prime power). [9] (b) Find a generator matrix and a parity-check matrix for the code {0000, 1010, 1001, 0011} over F2 = {0, 1}. [8] (c) Let C be the parity-check code of length 3 over F3 = {0, 1, 2}.
(i) Find a generator matrix for C. [4] (ii) Find a generator matrix for a code equivalent,
but not equal, to C. [4] Question 4 [20 marks]. Let C be the binary code {0000, 0110, 1101, 1011} of
length 4 over F2 = {0, 1}. (a) Write down a Slepian array for C. [7] (b) Write down a syndrome look-up table for C.
[7] (c) Using the syndrome look-up table, find a nearest-neighbour decoding process. [6] MTH6108 / MTH6108P (2020) Page 4 Question 5 [20 marks].
(a) Find a basis for the Reed-Muller codeR(1, 3) over F2 = {0, 1} and write down all the words of weight 1 in the code. [8]
(b) Write down all the words in the Hamming code Ham(2, 3) over F3 = {0, 1, 2}. [5] (c) In each of the following cases,
give an example of an MDS code of length n and redundancy r over Fq that works for every prime power q.
Justify your answer concisely. (i) n = 2020 and r = 1, [3] (ii) n = q+ 1 and r = 2. [4] End of Paper. c