7. Write a program
for error detecting
code using CRC-CCITT (16- bits).
Whenever digital data is stored or interfaced, data corruption might occur. Since the beginning of computer
science, developers have been thinking
of ways to deal with this type of problem. For serial data they came up with the solution to attach a parity bit to each sent byte. This simple detection
mechanism works if an odd number of bits in a byte changes, but an even number of false bits in one byte will not be detected
by the parity check. To overcome this problem developers have searched for mathematical sound mechanisms to detect
multiple false bits. The CRC calculation or cyclic redundancy check was the result of this. Nowadays CRC calculations are used in all types of communications. All packets
sent over a network
connection are checked
with a CRC. Also each data block on your hard
disk has a CRC
value attached to it. Modern computer world cannot do without these CRC
calculations. So let's see why they are so widely used. The answer is simple; they are powerful, detect many types of errors and are extremely fast to calculate
especially when dedicated hardware chips are used.
The idea behind CRC calculation is to look at the data as one large binary number. This number is divided by a certain value and the remainder
of the calculation is called the CRC. Dividing in the CRC calculation at first looks to cost a lot of computing power, but it can be performed very quickly if we use
a method similar to the one learned at school. We will
as an example calculate
the remainder for the character 'm'—which is 1101101 in binary notation— by dividing
it by 19 or 10011. Please note that 19 is an odd number.
This is necessary as we will see further on. Please refer to your schoolbooks as the binary calculation method here is not very different from the decimal method you learned when you were young. It might only look a little bit strange.
Also notations differ between countries, but the method
is similar.
With decimal calculations
you can quickly check that 109 divided
by 19 gives a quotient of 5 with 14 as the remainder. But what we also see in the scheme is that every bit extra to check only costs one binary comparison and in 50% of the cases one binary
subtraction. You can easilyincrease the number of bits of the test data string—for example to 56 bits if we use our example
value "Lammert"—and the result can be calculated with 56 binary
comparisons and an average of 28 binary
subtractions. This can be implemented in hardware directly with only very few transistors involved. Also software algorithms can be very efficient.
All of the CRC formulas you will encounter are simply checksum algorithms based on modulo-2
binary division
where we ignore carry bits and in effect the subtraction will be equal to an exclusive or operation. Though some differences exist in the specifics
across different
CRC formulas, the basic mathematical process is always
the same:
·
The
message bits are appended
with c zero bits; this augmented message is the dividend
·
A
predetermined c+1-bit binary
sequence, called
the
generator polynomial, is the divisor
·
The checksum
is the c-bit remainder
that results from the division operation
Table 1
lists some of the most commonly used generator polynomials
for 16- and 32-bit CRCs. Remember
that the width of
the divisor is always one bit wider than
the remainder. So, for example, you’d
use a 17-bit generator polynomial whenever
a 16-bit checksum is required.
CRC-CCITT
|
CRC-16
|
CRC-32
|
|
Checksum Width
|
16 bits
|
16 bits
|
32 bits
|
Generator Polynomial
|
10001000000100001
|
11000000000000101
|
100000100110000010001110110110111
|
International Standard CRC Polynomials
SOURCE CODE:
package crc;
import
java.util.Scanner;
public class
CRC {
public static void main(String[] args) {
Scanner scan = new Scanner(System.in);
int n;
//Accept the input
System.out.println("Enter the size
of the data:");
n = scan.nextInt();
int data[] = new int[n];
System.out.println("Enter the
data, bit by bit:");
for (int i = 0; i < n; i++) {
data[i] = scan.nextInt();
}
// Accept the divisor
System.out.println("Enter the size
of the divisor:");
n = scan.nextInt();
int divisor[] = new int[n];
System.out.println("Enter the
divisor, bit by bit:");
for (int i = 0; i < n; i++) {
divisor[i] = scan.nextInt();
}
// Divide the
input data by the input divisor
// Store the remainder that is returned
by the method
int remainder[] = divide(data,
divisor);
/*System.out.print("Remainder
is:");
for(int i=0 ; i <
remainder.length-1 ; i++) {
System.out.print(remainder[i]);
}
System.out.println();
*/
System.out.println("\nThe CRC code
generated is:");
for (int i = 0; i < data.length;
i++) {
System.out.print(data[i]);
}
for (int i = 0; i < remainder.length
- 1; i++) {
System.out.print(remainder[i]);
}
System.out.println();
// Create a new
array
// It will have the remainder generated
by the above method appended
// to the input data
int sent_data[] = new int[data.length +
remainder.length - 1];
System.out.println("Enter the data
to be sent, bit by bit:");
for (int i = 0; i <
sent_data.length; i++) {
sent_data[i] = scan.nextInt();
}
receive(sent_data, divisor);
}
static int[] divide(int old_data[], int
divisor[]) {
int remainder[], i;
int data[] = new int[old_data.length +
divisor.length];
System.arraycopy(old_data, 0, data, 0,
old_data.length);
// Remainder array stores the remainder
remainder = new int[divisor.length];
// Initially, remainder's bits will be
set to the data bits
System.arraycopy(data, 0, remainder, 0,
divisor.length);
// Loop runs for
same number of times as number of bits of data
//
This loop will continuously xor the bits of the remainder and divisor
for (i = 0; i < old_data.length;
i++) {
if
(remainder[0] == 1) {
// We have to xor the remainder
bits with divisor bits
for (int j = 1; j <
divisor.length; j++) {
remainder[j - 1] =
remainder[j] ^ divisor[j];
}
} else {
// We have to xor the remainder
bits with 0
for (int j = 1; j <
divisor.length; j++) {
remainder[j - 1] =
remainder[j] ^ 0;
}
}
//
The last bit of the remainder will be taken from the data
// This is the 'carry' taken from
the dividend after every step of division
remainder[divisor.length - 1] = data[i +
divisor.length];
}
return remainder;
}
static void receive(int data[], int
divisor[]) {
// This is the
receiver method
// It accepts the data and divisor
(although the receiver already has
// the divisor value stored, with no
need for the sender to resend it)
int remainder[] = divide(data,
divisor);
// Division is done
for (int i = 0; i <
remainder.length; i++) {
if (remainder[i] != 0) {
// If remainder is not zero
then there is an error
System.out.println("There
is an error in received data...");
return;
}
}
//Otherwise there is no error in the
received data
System.out.println("Data was
received without any error.");
}
}
/*NOTE:
System.arraycopy()
method copies a source array from a specific beginning position
to the
destination array from the mentioned position.
No. of
arguments to be copied are decided by len argument.
public
static void arraycopy(Object source_arr, int sourcePos,
Object dest_arr,
int destPos, int len)
Parameters :
source_arr :
array to be copied from
sourcePos :
starting position in source array from where to copy
dest_arr :
array to be copied in
destPos :
starting position in destination array, where to copy in
len : total
no. of components to be copied.
*/
No comments:
Post a Comment