Error detection & correction.

AIM:
Program for Error detection & correction.

THEORY:
Cyclic Redundancy Check
The cyclic redundancy check, or CRC, is a technique for detecting errors in digital data, but not for making corrections when errors are detected. It is used primarily in data transmission. In the CRC method, a certain number of check bits, often called a checksum, are appended to the message being transmitted. The receiver can determine whether or not the check bits agree with the data, to ascertain with a certain degree of probability whether or not an error occurred in transmission. If an error occurred, the receiver sends a “negative acknowledgement” (NAK) back to the sender, requesting that the message be retransmitted.
The technique is also sometimes applied to data storage devices, such as a disk drive. In this situation each block on the disk would have check bits, and the hardware might automatically initiate a reread of the block when an error is detected, or it might report the error to software. The material that follows speaks in terms of a “sender” and a “receiver” of a “message,” but it should be understood that it applies to storage writing and reading as well.
Take a binary message and convert it to a polynomial then divide it by another predefined polynomial called the key. The remainder from this division is the CRC. Now transmit both the message and the CRC. The recipient of the transmission does the same operation (divides the message by the same key) and compares his CRC with yours. If they differ, the message must have been mangled. If, on the other hand, they are equal, the odds are pretty good that the message went through uncorrupted. Most localized corruptions (burst of errors) will be caught using this scheme.
Not all keys are equally good. The longer the key, the better error checking. On the other hand, the calculations with long keys can get pretty involved. Ethernet packets use a 32-bit CRC corresponding to degree-31 remainder (remember, you need d + 1 coefficients for a degree-d polynomial). Since the degree of the remainder is always less than the degree of the divisor, the Ethernet key must be a polynomial of degree 32. A polynomial of degree 32 has 33 coefficients requiring a 33-bit number to store it. However, since we know that the highest coefficient (in front of x32) is 1, we don't have to store it. The key used by the Ethernet is 0x04c11db7. It corresponds to the polynomial:
x32 + x26 + ... + x2 + x + 1
There is one more trick used in packaging CRCs. First calculate the CRC for a message to which you have appended 32 zero bits. Suppose that the message had N bits, thus corresponding to degree N-1 polynomial. After appending 32 bits, it will correspond to a degree N + 31 polynomial. The top-level bit that was multiplying xN-1 will be now multiplying xN+31 and so on. In all, this operation is equivalent to multiplying the message polynomial by x32. If we denote the original message polynomial by M (x), the key polynomial by K (x) and the CRC by R (x) (remainder) we have:
M * x32 = Q (x) * K (x) + R (x)
Now add the CRC to the augmented message and send it away. When the recipient calculates the CRC for this sum, and there was no transmission error, he will get zero. That's because:
M * x32 + R (x) = Q (x) * K (x) (no remainder!)
You might think I made a sign mistake--it should be -R (x) on the left. Remember, however, that in arithmetic modulo 2 addition and subtraction are the same!

Hamming code
In telecommunication, Hamming codes are a family oflinear error-correcting codes that generalise theHamming(7,4)-code invented by Richard Hamming in 1950. Hamming codes can detect up to two and correct up to one bit errors. By contrast, the simple parity code cannot correct errors, and can detect only an odd number of errors. Hamming codes are special in that they are perfect codes, that is, they achieve the highest possible rate for codes with their block length and minimum distance 3.[1]
In mathematical terms, Hamming codes are a class of binary linear codes. For each integer   there is a code with block length n = 2r − 1 and message length k = 2r − r − 1. Hence the rate of Hamming codes is R = k / n = 1 − r / (2r − 1), which is highest possible for codes with distance 3 and block length 2r − 1. The parity-check matrix of a Hamming code is constructed by listing all columns of length r that are pairwise linearly independent.
Because of the simplicity of Hamming codes, they are widely used in computer memory (RAM). In this context, one often uses an extended Hamming code with one extra parity bit. Extended Hamming codes achieve a distance of 4, which allows the decoder to distinguish between the situation in which at most one bit error occurred and the situation in which two bit errors occurred. In this sense, extended Hamming codes are single-error correcting and double-error detecting, and often referred to as SECDED.

General algorithm
The following general algorithm generates a single-error correcting (SEC) code for any number of bits.
1. Number the bits starting from 1: bit 1, 2, 3, 4, 5, etc.
2. Write the bit numbers in binary. 1, 10, 11, 100, 101, etc.
3. All bit positions that are powers of two (have only one 1 bit in the binary form of their position) are parity bits.
4. All other bit positions, with two or more 1 bits in the binary form of their position, are data bits.
5. Each data bit is included in a unique set of 2 or more parity bits, as determined by the binary form of its bit position.
1. Parity bit 1 covers all bit positions which have the least significant bit set: bit 1 (the parity bit itself), 3, 5, 7, 9, etc.
2. Parity bit 2 covers all bit positions which have the second least significant bit set: bit 2 (the parity bit itself), 3, 6, 7, 10, 11, etc.
3. Parity bit 4 covers all bit positions which have the third least significant bit set: bits 4–7, 12–15, 20–23, etc.
4. Parity bit 8 covers all bit positions which have the fourth least significant bit set: bits 8–15, 24–31, 40–47, etc.
5. In general each parity bit covers all bits where the binary AND of the parity position and the bit position is non-zero.
CONCLUSION :
CRC, is a technique for detecting errors in digital data, but not for making corrections when errors are detected.
Hamming codes can detect up to two and correct up to one bit errors.






PROGRAM:
Cyclic Redundancy Check

import java.util.*;
class CRC2
{
public static void main(String S[])
{
Scanner K=new Scanner(System.in);
int m,n,T[],G[],i,j;
System.out.println("Enter length of message and GP");
m=K.nextInt();
n=K.nextInt();
if(n>m)
System.out.println("Length of GP shud be > than message");
else
{
T=new int[m+n-1];
System.out.println("Enter the message ");
for(i=0;i<m;i++)
T[i]=K.nextInt();
System.out.println();
for(i=m;i<m+n-1;i++)
T[i]=0;
System.out.println("Enter the G(P)");
G=new int[n];
for(i=0;i<n;i++)
G[i]=K.nextInt();
System.out.println("\n");

RM A=new RM();
int R[]=A.Remain(T,G,m,n); /*R is Remainder Array*/
for(i=0;i<n;i++)
System.out.println(R[i]);
System.out.println();
for(i=m,j=1;i<m+n-1;i++)
T[i]=R[j++];
R=A.Remain(T,G,m,n);

boolean f=true;
for(i=0;i<n;i++)
{
System.out.println(R[i]);
 if(R[i]==1) f=false;
}
if(f)
System.out.println("No Error is found");
else
System.out.println("Error is found");
}/*end else*/
}/*end main*/
}/*end class*/
class RM
{
int[] Remain(int T1[],int GP[],int m1,int n1)
{
int TP[]=new int[n1];
int j,i;
j=n1;
for(i=0;i<n1;i++)
TP[i]=T1[i];

while(j<m1+n1-1)
{
for(i=0;i<n1;i++)
if(TP[i]==GP[i])
TP[i]=0;
else TP[i]=1;
while(TP[0]!=1&&j<m1+n1-1)
{
for(i=0;i<(n1-1);i++)
TP[i]=TP[i+1];
TP[i]=T1[j];
j++;
}
}
return TP;
}
}




























Ouput:



























Program For Hamming Code

import java.util.*;
class Hamming
{
public static void main(String S[])
{
Scanner K=new Scanner(System.in);
int H[],P[],count,i,j,k,l,n,m;
P=new int[30];
System.out.println(" Enter Length of message");
n=K.nextInt();
H=new int[n+1];
System.out.println("Enter the message");
for(i=1;i<=n;i++)
H[i]=K.nextInt();
k=0;j=1;
for(i=1;i<=n;i++)
{
if(j==Math.pow(2,k))
{ P[j]=5;j++; k++;i--; }
else
{ P[j]=H[i];  j=j+1;  }
}
/*Filling the Parity Bits*/
k=0;count=0;
for(i=1;i<j;i++)
{
count=0;
if(i==Math.pow(2,k))
{
k++;
l=i;
while(l<j)
{
m=0;    /* 'm' is counter variable*/
while(m<i)
{
if(P[l]==1)
count++; m++; l++;
}
l=l+m;
}
if(count%2==0)
P[i]=0;
else
P[i]=1;
}
}
System.out.println("\n");
for(i=1;i<j;i++)
System.out.println(P[i]);
}
}

Output: