Coding Theory 2022-2023 Coursework Instructions
In this note you will find:
- Descriptions of the coursework tasks.
- Marking scheme.
- Notes and suggestions how to write the technical report.
- Frequently Asked Questions.
Introduction
In this coursework you will implement in MATLAB or Python various error correcting codes. In what follows references are made w.r.t. MATLAB, however you can submit all your coursework in Python. If you do so, you should use the NumPy library as the base of your code. You will be asked to generate simulation results assuming: Binary Symmetric Channel (BSC), Binary Erasure Channel (BEC), and BPSK modulation with Additive White Gaussian Noise (AWGN).
Although the MATLAB communications toolbox contains several functions for error control coding, you should not use them for these exercises (to be awarded maximum marks). The toolbox functions are intended to provide an efficient and simple to use implementation, without requiring detailed understanding of the algorithms. Instead, we will deliberately take a direct implementation approach which, will enhance understanding of the concepts and algorithms covered in lectures. You are required to write .m files for all the steps.
The coursework consists of 2 main tasks. You are required to submit an individual technical report containing discussions of your results and implementation choices and all MATLAB/Python codes. You should also include any relevant introduction and description of your algorithms in your report.
Task 1: (15,11) Hamming code: error correcting performance on BSC and AWGN channels
Task 1.1 BSC
Write a MATLAB function which constructs the generator matrix, the parity check matrix, encoding and decoding functions (syndrome look-up table) for the Hamming (15,11) code.
Investigate the performance of the Hamming code in the Binary Symmetric Channel. The plot should show the BER statistics as a function of the cross-over probability “p” of the BSC channel.
The BSC parameter should be in the interval p∈[0,0.2] – use at least 20 points in this interval. In your figure, add the theoretical prediction of BER as a function of p for this code.
You will need to perform Monte Carlo (MC) simulations to obtain the experimental BER performance curve. You may need many MC repetitions to obtain smooth curves.
In your report comment on your results: Does the theoretical BER approximation predict well the experimental performance? (15 marks).
Task 1.2 AWGN
Investigate the performance of your Hamming (15,11) code when used in an AWGN channel. To do so, assume that BPSK modulation is used to represent the binary code. At the receiver assume that hard-decision decoding is used. You can reuse the look up table from the Task 1.1. Plot your results on BER vs SNR curve and investigate the coding gain – an example of such curve is depicted in Figure 1. (15 marks).
10-1 10-2 10-3 10-4 10-5 10-6
3 4 5 6 7 8 9 10
Eb/No (dB)
Figure 1: Example of error correction statistics for some code (NOT THE ONE FROM task1).
Task 2: Empirical investigation of the error correcting performance of a binary convolutional code
In this task you need to write a script which performs Monte Carlo simulations to obtain BER curves in noisy and erasure channels.
For this task you will use a convolutional code and the probability of error will be estimated empirically i.e. in the form of BER via Monte Carlo simulations.
The rate 1/2 code for this task is given in Figure 2. Draw a state diagram and include it in your report. Assume that the input data sequence k=100 Bytes (800 bits, also allow for terminating bits). As the decoder you should implement the Viterbi decoder.
Assume the encoded signal is modulated by BPSK and is subjected to additive white Gaussian noise (AWGN), which can be simulated by adding Gaussian noise with a variance:
Note that this assumes that symbols are transmitted as ± 1 (BPSK) (suitably scaled to adjust for the code rate)
Task 2.1
Plot on the same figure: the curve for uncoded BPSK transmission, uncoded BPSK transmission with Eb/N0 adjusted for the code rate, and the BER plot for your code – Figure 1 shows how your results should be represented. Discuss our results.
1. What is the coding gain at BER=0.1, 0.01 and 0.001?
(15 marks), and
(20 marks for own implementation of the Viterbi Decoder)
Task 2.2
Investigate the performance of the convolutional code in erasure channels. Assume memoryless BEC with the probability of erasure in the interval α∈[0,0.3]. Produce a curve that describes the performance of the code (BER) as a function of the erasure probability.
(15 marks)
Marking scheme: a total of 100 marks are possible.
Task 1: 30 marks
Task 2: 50 marks
Overall quality of the technical report 20 marks.
Details of the marking scheme:
Task 1.1: 15 marks
Task 1.2: 15 marks
Task 2.1: 15 marks
Task 2.2: 15 marks
Implementation of the Viterbi decoder in Task 2: 20 marks Technical report quality 20 marks
– see marking scheme at the end of this note.
Notes and suggestions how to write the Technical Report.
The technical report should be no less than between 5 pages in length (including figures). This is guidance, the report can be longer if additional commentary/ results are included. It should include a brief review of the relevant theory in the introduction section and detailed discussions of the results, and implementation choices.
Do not include MATLAB/Python listing (verbatim copy of the section from m-file) in the technical report. You can however include “pseudo code” and the block diagram describing the algorithm that was used.
A description of what “pseudo code” is can be found: https://www.sciencedirect.com/topics/engineering/pseudocode
Both the technical report and the MATLAB codes will be automatically checked for originality (plagiarism checks).