Main Examination period 2020 – May/June – Semester B
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 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? Queen Mary University of London (2020) 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]
c? Queen Mary University of London (2020) Continue to next page
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? Queen Mary University of London (2020)