EENGM2011 - Coding Theory 4

EENGM2011 - Coding Theory 4

EENGM2010 - Coding Theory (M)

Supplementary assessment

Coursework, Summer 2021

Introduction

You are required to implement (in Matlab) the encoders and decoders for some simple linear block and convolutional codes. The implementation will then be used to generate simulation results assuming binary symmetric channel (BSC) and BPSK with additive white Gaussian noise (AWGN).

Although the Matlab communications toolbox contains several functions for error control coding, you will not use them for these exercises. The toolbox functions are intended to provide an efficient and simple to use implementation, without requiring detailed understanding. Instead, we will deliberately take a direct implementation approach which, although less efficient, will enhance understanding of the concepts covered in lectures. You are required to write simple .m files for the various steps.

The coursework consists of 3 main tasks. You are required to submit an individual technical note containing answers to all of them and all Matlab codes. You should also include any relevant comments and discussions of your results.

Task 1: (15,11) Hamming code

1.1 Construction of G and H matrices for the Hamming code

Write a Matlab function which constructs the generator matrix and the parity check matrix for the Hamming (15,11) code. You will need to select a portion of the matrix, transpose it and recompose the final matrix. The following Matlab syntax will be useful: A(rows,columns) will select the appropriate portion of A matrix. You can use : for all rows (or columns) or a simple vector of row or column indicies: ie. A(:,3:7) will select columns 3 to 7 of matrix A. A new matrix can be composed as C = [A,B]; where A and B must both have the same number of rows. (Alternatively C = [A;B] can be used to put B below A. The Matlab function 'eye(a)' will create an a by a identity matrix.

1.2 Encoding of the Hamming code

Write a Matlab function which encodes the data using the G matrix constructed in Task 1.1. As the input sequence use your UoB number as follows: Obtain your input sequence as a binary representation of your UoB number (take 11 rightmost bits). For example if your UoB number is 1145506, the binary representation is 100010111101010100010, the rightmost 11 bits are 01010100010.

(use dec2bin” Matlab functions).

1.3 Decoding of the Hamming code

Write a code that corrects a single error using G and H matrices of the Hamming code. To start with, construct the syndrome look-up table. As the input sequence use a modified codeword obtained in task 1.2. The modification consists of flipping one bit in this codeword. The position of the flip should be determined by your UoB number as “rem(UoB,15)+1”. For example if your UoB number is 0805547, the position of the flip (counting from the right) is rem(0805547,15)+1 =3.

1.4 Hamming code performance in the BSC channel

Write a Matlab function which will plot the performance of (15,11) 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?

Task 2: Cyclic Redundancy Check (CRC) code

In this task you will need to write a Matlab function for an error detection code using cyclic codes.

Specifically, you will use CRC-5-USB code (as used in USB) given by the generator polynomial:g(x) = x⁵ + x² +1.Verify that this generator polynomial is a valid (31,26) cyclic code.

2.1 Syndrome calculation

Write a Matlab function which constructs the error pattern using 31 bit representation of your UoB number. For this error pattern compute the syndrome. Is the binary representation of your UoB number a detectable error?

2.2 Numerical instigation of error detecting capabilities of the CRC-5-USB code

In this task you need to write a Matlab function which plots error detecting capabilities of the CRC-5-USB code. The plot should show the probability of error detection as a function of the Hamming weight of the error sequence. The question we are answering is: what is the probability that a randomly chosen error pattern with a given hamming weight is detectable? We want to have those statistics for all possible hamming weights i.e. {1,2,3, … ,30,31}. The results figure should be plotted in the form of a Matlab bar – below is an example figure how the results should be represented (do not be influenced by the height of those bars – you should expect different results!).

In your report answer the following questions:

a) Judging by the results: what do you think is the Minimum hamming distance of this code? Motivate your answer.

b) What is the proportion of weight 5,10 and 15 error sequences which are detectable by this code?

c) Is the sequence composed of all “1”s a valid codeword for this code? Motivate your answer.

Task 3: 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 a noisy channel (AWGN). This task is very similar to Q8 from problems sheet 3 (familiarise yourself with this question).

However, 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 code for this task is given in Figure 2. Assume that the input data sequence k=100 bits (plus terminating bits). As the decoder you should implement the soft 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).

In your report plot in 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 3 shows how your results should be represented

1. What is the coding gain at BER=0.01 , 0.001 and 0.0001?

Marking scheme:

Task 1: 20 marks

Task 2: 25 marks

Task 3: 30 marks

Overall quality of the written report: 25 marks

(100 marks total)

Report and codes submission

You need to submit your report and all Matlab codes via Blackboard as per instructions.

Useful Matlab “tricks”

1. You will need to use GF2 arithmetic. This can be easily performed by realising that GF2 arithmetic is the same as integer arithmetic modulo 2. Thus in Matlab, we can use rem(A*B,2) to multiply two matrices together (using GF2). This approach will work for any finite field with a prime number.

2. Command (rand(N,M) < p) produces Matlab variable class logical. Add “+” in front of the brackets to change from logical to double. i.e. +(rand(N,M) < p).

3. Command “dec2bin” produces class string. You can use “str2num” to convert string to number – note you need to make the conversion element wise e.g. via the loop “for”.