# 辅导MTH6108、辅导Python/C++程序

- 首页 >> Web 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)

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)