Coding Theory 2022-2023
Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit
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.
DEADLINES
Report and codes submission
You need to submit your technical report and all MATLAB (or Python/NumPy) codes via Blackboard (online). The deadline is Monday 12th December 2022, 16:00.
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 pe[0,0.2] – use at least 20 points in this interval. In your figure, add the theoretical prediction of BER as a function ofp 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 statisticsfor 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.
v1i
v2i
Figure 2: Convolutional encoderfor Task 2.
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:
N
= 2Eb
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 marksfor 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 αe[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
A good guide how to write technical reports is given here:
https://www.monash.edu/rlo/assignment-samples/engineering/eng-writing-technical-reports
Both the technical report and the MATLAB codes will be automatically checked for originality (plagiarism checks).
Each point in the table below is worth 2 marks, i.e. the total for the report quality is 20 marks.
|
Points |
Overall report quality |
|
1.0 – 2.0 |
|
|
2.0 – 3.0 |
Although the report has been delivered/submitted, there is no communication taking place. |
|
3.0-4.0 |
Although the report has been delivered/submitted, there is little or no communication taking place. Inadequate understanding and knowledge of fundamentals. Poor quality of critical judgement. |
|
4.0-5.0 |
Little effort made with software tools (editing / presentation). Little or no structure. Poor grammar and spelling. Knowledge of some fundamentals, but major gaps in understanding. Little critical judgement. |
|
5.0-6.0 |
Rather unimaginative use of editing tools. Some deficiencies in structure. Some spelling or grammatical inadequacies. Basic understanding and knowledge of most of the fundamentals, but perhaps with some misconceptions. Possibly limited critical judgement. |
|
6.0-7.0 |
Competent use of editing tools. Few, if any, spelling or grammatical errors. Good choice of result figures with good critical judgement but lacking some focus. Evidence of intelligent exploration of the subject. |
|
7.0-8.0 |
Creative use of software tools. No spelling or grammatical errors. Grabs the reader’s attention. Excellent structure and expression and critical judgement; well-chosen illustrations and results. Thorough understanding and knowledge of subject in breadth and depth. |
|
8.0-9.0 |
Flair and originality in tackling open-ended tasks. Authoritative grasp of the concepts, methodology and issues. Some review of background material. Design is viable and elegant; strengths are identified and weaknesses addressed. Some evidence of research ability. |
|
9.0-10 |
As 8-9 but seen perhaps only once every year or two in a typical class. |
Frequently Asked Questions
1. Can I re-submit my coursework? I submitted my coursework but later I realised that I made a mistake - can I submit it again?
Yes, you can re-submit your coursework (the system will accept up to 5 re-submissions). Only the last submission will be marked.
2. I think that the convolutional encoder in task 1 may be bad (e.g. it could lead to a catastrophic error propagation).
If you think that the proposed encoder is not good, you can modify it. However, you need to argue the case, i.e. you have to provide evidence that the encoder is not good. You can then modify the encoder, by adding or removing connections in the shift register (the encoder). the constraint length needs to stay as 3.
3. Can I use Viterbi decoder from Matlab’s Communications Toolbox?
Yes, you can use the Viterbi decoder from MATLAB toolbox. However, if you implement it yourself you can be awarded up to 20 marks.
4. Should I copy coder from MATLAB m.files into the report?
No, do not include MATLAB 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.
5. In the BEC channels how do I know locations of the erasures.
In the binary erasure channel model we assume that the receiver knows when the erasures have happened (the receiver knows the locations after it receives the signal) - this is modelled by the additional symbol “?” or “E” at the output of the model.
6. In task 2, Should I implement hard or soft decisions Viterbi decoder?
You can implement either of the two (hard or soft)- you can choose it. Make it clear in your report which one you have chosen. Tip: think of task 2.2 - performance over the erasure channels. Plan ahead how you are going to implement the Viterbi decoder for the erasure channels. Implemented in such a way so that you can reuse much of the code (with minimal modifications if needed) to implement both subtasks: 2.1 and 2.2.
7. Can I use Python instead of MATLAB?
Yes you can use Python. However, you should use the NumPy library of Python. You can also use Galois extension to NumPy https://pypi.org/project/galois/. Preferably you should use Jupiter Notebook, and submit *.ipynb files.
2022-11-30