Error Correction Codes

Abstract'This report is on Error Correction Codes mainly
focusing on Reed Muller Correcting Codes. These techniques
are widely used in various computer applications which send
data from one system to another over reliable/unreliable channel.
In section 2 we described various other techniques like Parity
Check, Checksum to detect and correct errors in the message
send by the sender over reliable/unreliable channel. In the next
section we described Reed Muller technique for encoding and
decoding messages and how it used to recover correct message
from erroneous message.

I.
INTRODUCTION
In Computer Networks course, we studied some of the
techniques used to detect and correct errors caused during the
transmission of packets from sender to receiver and we want to
study other techniques than studied in the course so, we chose
this topic for our report. Basic idea behind recovering actual
data from erroneous data is to introduce some redundant bits
to the data to be send to the receiver. We studied Parity Check,
Checksum and Cycle Redundancy Check in our Computer
Network course and for this topic we mainly focused and
studied Reed Muller Codes and using it to recover correct
data. Reed Muller Codes were introduced in 1954 by D. E.
Muller and I. S. Reed.
In section 2 we explained Parity Check and Checksum.
In section 3 we explained the complete technique of Reed
Muller Codes.
II.
Problem with this technique is that it fails when number of bits
flipped are even. Solution to this problem was to break the D
bits of data into 2-d matrix(M) and maintain parity bit for each
row and column. This improvement solves the problem of even
bits flipped and also helps to correct the detected error unlike
previous case. Error is corrected using ith row and jth column
of matrix.
Example:
Suppose, D = 110001001
Senders side, matrix will be:
'
'
1 1 0 0
'0 0 1 1'
'0 0 1 1'
1 1 0 0
In the above matrix, last row and last column contains parity
bits only. Each row and column has its own parity bit.

Receiver side, matrix will be:
'
'
1 1 0 0
'0 0 1 1'
'1 0 1 1'
1 1 0 0
At receiver's side,row 3 has its 1st bit flipped. This can be
easily detected. sum of 1 bits in column 1 and row 3 is odd,
and both of them intersect at index (3,1), which is the flipped
bit. Similarly, we can detect and correct errors for other bits
also. (1 based indexing)
E RROR D ETECTION T ECHNIQUES
Some techniques for detecting and correcting errors are
Parity Check and Checksum.
A. Parity Check
In Parity Check technique, we introduce a bit to the data
which is known as parity bit and we denote it by P.Suppose,
D bits of data need to be sent from sender's side, then this
new parity bit is added to the data. Finally, D+1 bits are send
from sender's side. P is set to 1 or 0 depending on number of
1 bits present in D bits of data to be sent. If number of 1 bits
are even then P is set to 0 else 1. At receiver's side, number
of 1 bits are calculated. If the number of bits are even then its
fine else error is detected.
Example:
Suppose, D = 11000100
Since, number of 1 bits are odd so, P = 1
D + 1 bits send by the sender = 110001001
Suppose, now receiver received message as 110101001
Error is detected as number of 1 bits are 5 which is odd.
B. Checksum
In Checksum technique, segment is treated as 16 bits inte-
gers.Add 16 bits numbers, carry is wraparound and resulting 16
bits are put in UDP checksum field. At receivers side, check
is recalculated from received data, it matches the calculated
checksum with UDP checksum. If both are same then no error
occurred else error is detected.
Example:
I1 = 1000000000101011
I2 = 0000000000010101
sum = 1000000001000000
Checksum = 0111111110111111
III.
R EED M ULLER C ORRECTING C ODES
In Reed Muller Correcting codes technique, extra redun-
dant bits are added to the message to be sent for error
correction and detection. Data can be successfully recovered
from erroneous data.
Some basics rules used to detect and correct errors are Addition
(bit by bit addition and overflow is ignored), Multiplication (bit
by bit multiplication) and Dot product (bit by bit multiplication
and then addition with overflow ignored).
Example: Suppose A = 1111, B = 1010
Addition: A + B = 1111 + 1010 = 0101
Multiplication: A ' B = 1111 ' 1010 = 1010
Dot Product: A.B = 1111.1010 = 1 + 0 + 1 + 0 = 0
A. Reed Muller Matrices
Reed Muller Matrices are defined as R(r,m) where r is rth
order Reed Muller Code and each row is associated with set
of binary strings of length 2m .
To form the Reed Muller Matrix R(r,m), we introduce m
variables X1 , X2 , ...., Xm . Number of rows in the matrix are:
m
C0 + m C1 + ..... + m Cr .
For example let us construct R(1,3).
In this matrix, no. of rows will be 3 C0 + 3 C1 = 1 + 3 = 4 and
binary string length will be 23 = 8.
Binary string for row0 = 23-0 =8 1's = 11111111
Binary string for row1 = 23-1 = 4 1's followed by 4 0's =
11110000.
Binary string for row2 = 23-2 = 2 1's followed by 2 0's and
so-on = 11001100.
Binary string for row3 = 23-3 = 1 1's followed by 1 0's and
so-on = 10101010.
Lets introduce 3 variables X1 , X2 , X3 for the matrix.
Matrix will be :
'
'

1 1 1 1 1 1 1 1 1
'X 1 1 1 1 0 0 0 0'
R(1, 3) = ' 1
X2 1 1 0 0 1 1 0 0'
X3 1 0 1 0 1 0 1 0
Similarly for R2 , R3 we will have 7 rows. For row 4, 5 and
6 we can make combinations of variables X1 , X2 , X3 like
X1 X2 , X2 X3 , X3 X1 , X1 X2 X3 .
B. Encoding message using Reed Muller Matrices
To encode a message we choose such a Reed Muller matrix
that has no. of rows equal to no. of bits in the message.
Suppose we have a message of 4 bits, than we will choose
R(1,3) matrix. We encode message by multiplication of 1st bit
with 1st row, 2nd bit with 2st row and so-on. Then we add all
the strings we get from multiplication and we send that to the
receiver.
Example:
Suppose message to be send is 1110. Since, it has 4 bits, we
will choose R(1,3) matrix. So, the encoded message will be:
Me = 1 ' row1 + 1 ' row2 + 1 ' row3 + 0 ' row4
Me = 11111111 + 11110000 + 11001100 + 10101010
Me = 11000011
Finally, the encoded message Me will be send to the receiver.
C. Decoding Messages
Steps involved in decoding are:
a) Find characteristic vectors for each row in bottom up
approach.
b) Take the dot product of each rows characteristic vectors
with the received erroneous message.
c) Follow the majority logic and assign the most frequently
occurring value to coefficient of that row.
d) Multiply the coefficient of each row with the associated
binary string of that row and add all of these to form the
resulting vector string My .
e) Add vectors My and Mr and decide the first rows
coefficient by observing the most frequent bit. (0 or 1).
To find the characteristic vectors for each row, take the
monomial associated with the row of encoding matrix. Then,
take rest of the variables that are not in the monomial
associated with that row. For example: for row4 in R(1, 3),
it have X3 as the monomial associated to it. Now, rest of
the variables are X1 and X2 . So, the characteristic vectors
?? ??
??
??
of row4 will be X1 ' X2 , X1 ' X2 , X1 ' X2 and X1 ' X2 .

??
(where X denotes the complement of vector associated with
the row of X).
Example:
Suppose message to be send by sender was 1110. The
encoded message send by the sender was 11000011. Suppose
receiver receives an erroneous message Mr as 11010011. We
will follow previous steps to recover the correct message.
Finding coefficient of X3 :
Characteristic vectors for row4 are:
X1 ' X2 = 11000000
??
X1 ' X2 = 00110000
??
X1 ' X2 = 00001100
??
??
X1 ' X2 = 00000011
Taking the dot product with erroneous message Mr :
(11000000).(11010011) = 1 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 0
(00110000).(11010011) = 0 + 0 + 0 + 1 + 0 + 0 + 0 + 0 = 1
(00001100).(11010011) = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 0
(00000011).(11010011) = 0 + 0 + 0 + 0 + 0 + 0 + 1 + 1 = 0
So, by majority logic we conclude that coefficient of X3 is
C4 = 0.
Finding coefficient of X2 :
Characteristic vectors for row3 are:
X1 ' X3 = 10100000
??
X1 ' X3 = 01010000
??1 ' X3 = 00001010
X
??
??
X1 ' X3 = 00000101
Taking the dot product with erroneous message Mr :
(10100000).(11010011) = 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 1
(01010000).(11010011) = 0 + 1 + 0 + 1 + 0 + 0 + 0 + 0 = 0
(00001010).(11010011) = 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1
(00000101).(11010011) = 0 + 0 + 0 + 0 + 0 + 0 + 0 + 1 = 1
So, by majority logic we conclude that coefficient of X2 is
C3 = 1.
Finding coefficient of X1 :
Characteristic vectors for row2 are:
X2 ' X3 = 10001000
??
X2 ' X3 = 01000100
??
X2 ' X3 = 00100010
??
??
X2 ' X3 = 00010001
Taking the dot product with erroneous message Mr :
(10001000).(11010011) = 1 + 0 + 0 + 0 + 0 + 0 + 0 + 0 = 1
(01000100).(11010011) = 0 + 1 + 0 + 0 + 0 + 0 + 0 + 0 = 1
(00100010).(11010011) = 0 + 0 + 0 + 0 + 0 + 0 + 1 + 0 = 1
(00010001).(11010011) = 0 + 0 + 0 + 1 + 0 + 0 + 0 + 1 = 0
So, by majority logic we conclude that coefficient of X1 is
C2 = 1.
Finding coefficient of row1 :
Now, we will multiply each row with their corresponding
coefficient and will add them up.
My = 1 ' (11110000) + 1 ' (11001100) + 0 ' (10101010)
My = 11110000 + 11001100 + 00000000
My = 00111100
Now, adding this with erroneous message Mr .
My + Mr = 00111100 + 11010011
My + Mr = 11101111
So, by majority logic we conclude that coefficient of row1 is
C1 = 1.
Now, to recover the final message we will concatenate
the coefficient of each row i.e
Mf = C1 C2 C3 C4 .
So, the final message recovered is Mf = 1110 which was
indeed the message sent by the sender.
D. Drawbacks
This technique is really efficient in finding and correcting
errors but it also have some drawbacks. If during majority logic
no.of 1 bits and no.of 0 bits are equal, then it can't decide what
should be the coefficient of that row and so it halts. Another
draw back is that it can only recover specific bit flips.
No. of bits Br that it can recover are:
Suppose no.of bits in message are d
Br = 2m-r /d
IV.
CONCLUSION
From this report one can conclude that there is no guaran-
teed delivery of data over network(no matter whether sender
chooses reliable or unreliable service).Once the sender has
send data from his side in the network then there is a possibility
that receiver may receive erroneous message.
To overcome this problem, there are some error detecting
techniques which helps the receiver to correct the erroneous
message.To implement this, developer need's to work on
both side(sender and receiver).Some redundant bits are in-
troduce at senders side and data is send with this redundant
bit(s).Receiver use some techniques to recover actual data with
the help of these redundant bit(s).
REFERENCES
[1]
[2]
[3]
Cooke, Ben. 'Reed Muller error correcting codes.' MII Undergraduate
J. Math 1 (1999): 21-27.
Gupta, Vikas, and Chanderkant Verma. 'Error Detection and Correction:
An Introduction.' International Journal 2.11 (2012).
Raaphorst, Sebastian. 'Reed-muller codes.' Carleton University, May 9
(2003).

Source: Essay UK - http://doghouse.net/free-essays/information-technology/error-correction-codes.php


Not what you're looking for?

Search:


About this resource

This Information Technology essay was submitted to us by a student in order to help you with your studies.


Rating:

Rating  
No ratings yet!


Word count:

This page has approximately words.


Share:


Cite:

If you use part of this page in your own work, you need to provide a citation, as follows:

Essay UK, Error Correction Codes. Available from: <http://doghouse.net/free-essays/information-technology/error-correction-codes.php> [22-02-19].


More information:

If you are the original author of this content and no longer wish to have it published on our website then please click on the link below to request removal:


Essay and dissertation help

badges