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

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

This page has approximately ** words.**

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].

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: