Error Detection and Correction

Objectives:

To become familiarized with error detection and correction techniques in data communication.

Theory:

Part 1: Error Detection

Error detection uses the concept of redundancy, which means adding extra bits for detecting errors at the destination. Redundancy bits are added to the message block which is known as data word and code word is generated.

 1 0 1 0 1 1 0 0 1 0 0 0 Data word Redundancy

Some error detection techniques are parity check, cyclic redundancy check and checksum.

1. Parity Check
2. Simple parity check

In simple Parity check single redundancy bit is added. In even-parity redundant bit is added such that total number of 1s’ in the code word is an even number. In odd-parity redundant bit is added such that total number of 1s’ in the code word is an odd number.

 1 0 1 1 1 1 0 0 1 Data word Redundancy
1. Two dimensional parity

In two dimensional parity several data units are considered. First they are organized in a table where each data unit is a separate row. Parity bit for each row is calculated and added as a separate column. Then parity bit for each column is calculated and added as a separate row at the bottom as shown below. Each row of the final matrix is transmitted as separate data units.

1. Cyclic Redundancy Check (CRC)

In CRC generation n (less than the number of bits in the divisor) ‘0’s are appended to the data unit. Then the data word plus appended zeros are divided by the divisor using module-2 binary division which means addition and subtraction is done using XOR operation. The remainder of the division replaces the appended ‘0’s at the end of the data unit.

At the receiver CRC checker uses module-2 binary division to the received data. If the remainder is 0 there is no error. If the remainder is not equal to 0 it has some error.

1. Checksum

Checksum is a network layer error correction method. At the sender the unit is divided into k sections each of n bits. Then all sections are added using one’s complement to get the sum. The sum is complemented ad becomes the checksum. The checksum is sent with the data.

At the receiver the unit is divided into k sections, each of n bits. Then all sections are added using one’s complement to get the sum. The sum is complemented. If the result is zero, the data are accepted: otherwise, rejected.

Part 1: Error Correction

Error Correction can be done using retransmission, forward error correction and burst error correction. Error correction need more bits than error detection. Forward error correction is a mostly used method for single bit error correction. In forward error correction exact position of the single bit error is identified by the use of additional redundancy bits. One of the commonly used forward bit correction method if hamming code. The number of redundancy bits r to correct a given number of data bits m is given by,

2r >= m + r + 1

1. Hamming Code

Hamming code use all bit positions that are powers of two as parity bits (positions 1,2,4,8,16,32,64, etc.). All other positions are for the data to be encoded. As shown in below r1 redundancy bit is calculated using bits 3,5,7,9,11 where LSB is ‘1’ .

Position1 (r1): check 1 bit, skip 1 bit (1,3,5,7,9,11,……………)

Position2 (r2): check 2 bit, skip 2 bit (2,3,6,7,10,11,………..)

Position4 (r4): check 4 bit, skip 4 bit (4,5,6,7,12,13,14,15….)

Position8 (r8): check 8 bit, skip 8 bit (8-15,24-31,40-47……)

Parity bit is set to make number of 1s’ to an even number. At the receiver above r1,r2,r4 and r8 bits are compared with corresponding bits to identify errors. r1,r2,r4,r8 will be set to 1 or 0 depending on having or not having an error. Then r8 r4 r2 r1 binary value indicate the position of the bit error. For error correction corresponding bit is complemented.

Procedure:

Part 1: Error Detection

1. Single Parity Check
2. Express the last 4 digits of your registration number in binary representation of 8 bits as follows.

Registration Number : BSC-EE-2016-01-0020

Binary Representation : 00010100

Data word : 00010100

1. Create a MATLAB function odd_parity_generator as shown below to generate a code word using odd parity.

function codeword = odd_parity_generator(msg)

num_of_ones = sum(msg); % number of ones

m = mod(num_of_ones,2);

%generating odd parity bit

if(m == 0)

odd_parity = 1;

else

odd_parity = 0;

end

codeword = [msg odd_parity]; % code word

end

1. Create a MATLAB function even_parity_generator to generate a code word using even parity.
2. Create a MATLAB function even_parity_checker to check a code word for errors using even parity and give data word and error as output (error is ‘1’ for having errors and ‘0’ for not having errors).

function [dataword,error] = even_parity_checker(msg)

1. Generate code word for your registration number using even_parity_generator. What is the output?
2. Use the even_parity_checker function to check for errors. What is the output?
3. Introduce a single bit error to your data word (registration number) and use even_parity_checker to check for errors. What is the output?
4. Introduce a two bit error to your data word (registration number) and use even_parity_checker to check for errors. What is the output?
5. Two Dimensional Parity Check
6. Consider the following data units for the following processes.

Data word: 10101010 11111111 11110000 0001111

1. Create a MATLAB function even_two_parity_generator as shown below to generate a code word using two dimensional even parity. ‘msg’ matrix is made with arranging data units as rows (code word is a matrix which contains the output of two dimension parity).

function codeword = even_two_parity_generator(msg)

[M N] = size(msg); % size of the msg matrix which contains data

codeword = [];

for i = 1:M

% generation of row parity

codeword = [codeword; even_parity_generator(msg(i,:))];

end

%generation of column parity

column_parity = mod(sum(codeword),2);

codeword = [codeword; column_parity];

end

1. Create a MATLAB function even_two_parity_checker to check a code word for errors using even parity and give data word and error as output (error is ‘1’ for having errors and ‘0’ for not having errors).

function [dataword,error] = even_parity_checker(msg)

1. Use the function even_two_parity_generator to generate two-dimension parity code word for given data word. What is the output?
2. Use the even_two_parity_checker function to check for errors of the above code word. What is the output?
3. Create a MATLAB function single_bit_error as follows to introduce 1 bit error to the received code word. Use the even_two_parity_checker to check for errors. What is the output?

function codeword = single_bit_error(msg)

[M N] = size(msg); % Size of the msg matrix which conntains data

i = ceil(M/2); % Center of rows

j = ceil(N/2); % Center of columns

msg(i,j) = 1-msg(i,j); % Bitwise complement

codeword = msg;

end

1. Create a MATLAB function four_bit_error as follows to introduce 4 bit error to the received code word. Use the even_two_parity_checker to check for errors. What is the output?

function codeword = four_bit_error(msg)

[M N] = size(msg); % Size of the msg matrix which conntains data

i = ceil(M/2); % Center of rows

j = ceil(N/2 % Center of columns

msg(i,j) = bitcomp(msg(i,j)); % Bitwise complement

msg(i+1,j) = bitcomp(msg(i+1,j)); % Bitwise complement

msg(i,j+1) = bitcomp(msg(i,j+1)); % Bitwise complement

msg(i+1,j+1) = bitcomp(msg(i+1,j+1)); % Bitwise complement

codeword = msg;

end

1. Cyclic Redundancy Check (CRC)
2. What are the conditions for selecting a CRC polynomial?
3. Create a MATLAB function CRC_generator as shown below to generate a code word using Cyclic Redundancy Check.

function codeword = CRC_generate(msg,poly)

[M N] = size(poly);

msg_0 = [msg zeros(1,(N-1))];

[q r] = deconv(msg_0,poly);

r = abs(r);

for i = 1:length(r)

a = r(i);

if (mod(a,2) == 0)

r(i) = 0;

else

r(i) = 1;

end

end

crc = r(length(msg)+1:end);

codeword = bitor(msg_0,r);

end

1. Create a MATLAB function CRC_check as shown below to a CRC code word for errors.

function [data, error] = CRC_check(msg,poly)

[q r] = deconv(msg,poly);

r = abs(r);

for i = 1:length(r)

a = r(i);

if (mod(a,2) == 0)

r(i) = 0;

else

r(i) = 1;

end

end

data = msg;

if(r == zeros(1,length(r)))

error = 0;

else

error = 1;

end

end

1. Select a suitable Polynomial to detect all burst errors up to 4 bit in your registration number. Use the CRC_generate function to generate CRC code word for your registration number (8 bits). What is the output? Then use CRC_check function to detect errors in the code word. What is the output?
2. Checksum
3. Create a MATLAB function Checksum_gen as follows to generate a check sum for a given data set msg. k is the number of sections in msg.

function [checksum,data] = Checksum_gen(msg,k)

n = size(msg,2);

data=vec2mat(msg,(n/k));

s = mod(sum(data,1),2);

checksum = 1-s;

data = msg;

end

1. Create a MATLAB function Checksum_check to check a code word for errors (Inputs are dataword and checksum. Outputs are data and a variable called error to indicate errors).
2. Use the following data set to generate a checksum. Use k as 8. Then using Checksum_check function detect errors. What is the output? Introduce a single bit error to the received data set at the receiver. Using Checksum_check check errors. What is the output?

Data Set : 01010101 11110000 00001111 10101010

1. If the received data at the receiver is as follows using the above generated checksum check for errors.

Received Data : 01010101 11111000 00000111 10101010

Part 1: Error Correction

Hamming Code

1. Create a MATLAB function hamming_gen to generate 11 bit hamming code word hamming_codeword from 7 bit data word given as a array.

function hamming_codeword = hamming_gen(dataword)

1. Use the above function to generate the codeword for ‘1010101’. What is the output?

Conclusion

1. Write down the procedure to generate code word and check for errors using parity check, CRC, checksum, and hamming code.
2. Compare advantages and disadvantages parity check, CRC, and checksum, and hamming code.
3. Explain the difference at the output values for question 7 and 8 under parity check for single and two bit errors.
4. Explain the difference at the output values for question 14 and 15 under two dimensional parity check for single and four bit errors.
5. Explain the output for question 23 under checksum.