Digital Communications

(UESTC 4004)

Lab 3: Channel Coding

The objective of this lab is to encode a message (e.g. first letter of your first name) with a given linear block code for forward error correction. The coded message is decoded using appropriate decoding scheme to recover the original message. The effectiveness of channel coding is to be demonstrated by recovering the original message accurately even in the presence of error producing noise.

Introduction

Linear code is an important type of block code used in error correction and detection schemes. Linear codes are applied in methods of transmitting symbols (e.g., bits) on communications channel so that, if errors occur in the communication, some errors can be detected by the recipient of the message block. A linear code of length n transmits blocks containing n bits or symbols. For example, the (7, 4) linear code is a binary linear code which represents 4 original message bits with 7 coded bits.

In linear block codes, the input is a k bit block (k message bits) and output is n bit block (n coded bits) with r=n-k check bits. With a k bit message block:

No of code words = 2k

Block length = n

Code rate = k/n

The check bits are determined by some predetermined rule.

U = m G

where:

U = code vector

m = message vector

G = Generator matrix which is defined as [ P | Ik ]; Ik is identity matrix of order k and P is the predefined encoding rule.

Matlab Syntax:

The encode function is used for encoding. The syntax is as follows.

code = encode(msg,n,k,'linear/fmt',genmat)

where, the codeword length is n and the message length is k.

msg represents data or message. It can be in decimal or binary format. The default value for this parameter is binary. We will use binary format in this lab session.

For example:

Format of msg can be a binary column vector as given below.

msg = [0 1 1 0 0 1 0 1 1 0 0 1]'. The ' symbol indicates matrix transpose.

Format of msg can also be binary matrix with k columns. In this case format of code will be binary matrix with n columns.

msg = [0 1 1 0; 0 1 0 1; 1 0 0 1]. Here k = 4.

For Linear Block codes, encode function encodes msg using genmat as the generator matrix.

genmat, a k-by-n matrix, is required as input.

Example:

The example below illustrates two different information formats (binary vector and binary matrix) for linear block code. The two messages have identical content in different formats. As a result, the two codes created by encode function have identical content in correspondingly different formats.

Here k = 11. And let r = 4 

r = 4; % r is the number of check bits.

k = 11;   % Message length

n = k + r % Codeword length = 15 using formula n-k=r

% Create 100 messages, k bits each.

msg1 = randi([0,1], 100*k,1); % As a column vector

msg2 = vec2mat(msg1,k);          % As a k-column matrix

% Create 100 codewords, n bits each.

genmat=[P eye(11)]; % concatenate P submatrix or predefined rule with Identity matrix.

code1 = encode(msg1,n,k,'linear/binary',genmat); code2 = encode(msg2,n,k,'linear/binary',genmat); if ( vec2mat(code1,n)==code2 )

disp('All two formats produced the same content.') end

Instead of randomly generating data words, you can create a data matrix of your own containing the data words that you want to encode.

Exercise 1 [6+6+2+2+2+2]: Given (6,3) linear block code generated by the predefined matrix P=[0 1 1; 1 0 1; 1 1 0].

a) Encode the messages [1 1 1] and [1 0 1] through MATLAB.

b) Encode all the possible messages in MATLAB and write the encoded words.

c) The minimum hamming distance = . (see lecture for reference)

d) The no. of errors this code can detect is (see lecture for reference)

e) The no. of errors this code can correct is (see lecture for reference)

f) The code rate = . (see lecture for reference)

Exercise 2 [30]: Given below is the MATLAB code to create 8x8 matrix representing letter ‘S’.

image = [ 1, 1, 1, 0, 0, 1, 1, 1;

               1, 1, 0, 1, 1, 0, 1, 1;

               1, 1, 0, 1, 1, 1, 1, 1;

               1, 1, 1, 0, 1, 1, 1, 1;

              1, 1, 1, 1, 0, 1, 1, 1;

               1, 1, 1, 1, 1, 0, 1, 1;

               1, 1, 0, 1, 1, 0, 1, 1;

               1, 1, 1, 0, 0, 1, 1, 1];

imshow(image);

Then using

P = [1 1 1 1;

0 1 1 1;

1 1 1 0;

1 1 0 1;

0 0 1 1;

0 1 0 1;

0 1 1 0;

1 0 0 1]

and encode function, encode your generated 8x8 matrix. You’ll have 8 coded words of 12 bits each. Remember the size of P is k x (n-k). This information will be helpful in calculating n and k.

3) Decoding linear block codes: Let Z stands for the received vector when a particular code vector U has been transmitted. Any transmission errors will result in Z ≠ U. The decoder detects or corrects errors in Z using stored information about the code.

A direct way of performing error detection would be to compare U with every vector in the code. This method requires storing all 2k code vectors at the receiver and performing up to 2k comparisons. But efficient codes generally have large values of k, which implies rather extensive and expensive decoding hardware.

More practical decoding methods for codes with large k involve parity check information derived from the code’s P submatrix. Associated with any systematic linear (n,k) block code is a(n-k)×n matrix called the parity check matrix H. This matrix is defined by

H = [Ir | P’]

Where Ir is the r × r identity matrix and n - k = r. The parity check matrix has a crucial property for error detection which is

ZHT = (0 0 0 0 …… 0)

provided that Z belongs to the set of code vectors. However, when Z is not a code vector, the product ZHT contains at least one nonzero element.

Therefore, given HT and a received vector Z, error detection can be based on

S = Z HT

an r-bit vector called the syndrome. If all elements of S equal zero, then either Z equals the transmitted vector U and there are no transmission errors, or Z equals some other code vector and the transmission errors are undetectable. Otherwise, errors are indicated by the presence of nonzero elements in S. Thus a decoder for error detection simply takes the form. of a syndrome calculator.

We develop the decoding method by introducing an n-bit error vector E whose non zero elements mark the positions of transmission errors in Z. For instance, if U = (1 0 1 1 0) and   Z = (1 0 0 1   1) then E = (0 0 1 0 1). In general,

Z = U Å E

And conversely,

U = Z Å E

Substituting Z = U + E into S = ZHT, we obtain

S = (U Å E)HT

S =UHT  Å EHT

S = EHT

which reveals that the syndrome depends entirely on the error pattern, not the specific transmitted vector.

Syndrome decoding example

An (8, 4) binary linear block code U is defined by systematic matrices:

0 1 1 1 | 1 0 0 0  1 0 0 0 | 0 1 1 1

G = 1 0 1 1 | 0 1 0 0  H = 0 1 0 0 | 1 0 1 1

1 1 0 1 | 0 0 1 0  0 0 1 0 | 1 1 0 1

1 1 1 0 | 0 0 0 1  0 0 0 1 | 1 1 1 0

Consider two possible messages:

m1 = [0 1 1 0] m2 = [1 0 1 1]

                          u1 = [0 1 1 0 0 1 1 0]                          u2 = [0 1 0 0 1 0 1 1]

Suppose error pattern e = [0 0 0 0 0 1 0 0] is added to both code words.

z1 = [0 1 1 0 0 0 1 0] z2 = [0 1 0 0 1 1 1 1]

Calculating the syndrome using S = ZHT. Here Z is the received erroneous code word. s1 = [1 0 1 1] s2 = [1 0 1 1]

The syndromes are the same and equal column 6 of H, so decoder corrects bit 6.

Exercise 3 [20+20+10]: Write MATLAB code to create a syndrome table that shows all the possible errors that the coder in above example could correct. You may seek help from the built-in MATLAB function(s). Once you know the error patterns, generate the syndrome vector corresponding to each error pattern.

If z = [ 0 1 1 1 0 1 1 0] is the received vector, what is the corresponding syndrome and at which position is the error, if any? Also, write the vector after correcting the error.

MATLAB Help:

1) DECODE:

Function: Block decoder

Syntax

msg = decode(code,n,k,'linear/fmt',genmat,trt) [msg,err] = decode(...)

[msg,err,ccode] = decode(...)

[msg,err,ccode,cerr] = decode(...)

Description: See MATLAB help

2) SYNDTABLE:

Function: Produces syndrome decoding table

Syntax:

t = syndtable(h)

Description: See MATLAB help

3) gen2par

Function: Convert between parity-check and generator matrices

Syntax

parmat = gen2par(genmat) genmat = gen2par(parmat)

Description: See MATLAB help