Error-Detecting Codes - Checksums

 

KARTHICKRAJA S

1st MCA - B

KGiSL Institute of Information Management

Errors and Error Detection

When bits are transmitted over the computer network, they are subject to get corrupted due to interference and network problems. The corrupted bits leads to spurious data being received by the receiver and are called errors.

Error detection techniques are responsible for checking whether any error has occurred or not in the frame that has been transmitted via network. It does not take into account the number of error bits and the type of error.

For error detection, the sender needs to send some additional bits along with the data bits. The receiver performs necessary checks based upon the additional redundant bits. If it finds that the data is free from errors, it removes the redundant bits before passing the message to the upper layers.

There are three main techniques for detecting errors in frames: Parity Check, Checksum and Cyclic Redundancy Check (CRC).

Checksums

This is a block code method where a checksum is created based on the data values in the data blocks to be transmitted using some algorithm and appended to the data. When the receiver gets this data, a new checksum is calculated and compared with the existing checksum. A non-match indicates an error.

Error Detection by Checksums

For error detection by checksums, data is divided into fixed sized frames or segments.

• Sender’s End − The sender adds the segments using 1’s complement arithmetic to get the sum. It then complements the sum to get the checksum and sends it along with the data frames.

• Receiver’s End − The receiver adds the incoming segments along with the checksum using 1’s complement arithmetic to get the sum and then complements it.

If the result is zero, the received frames are accepted; otherwise they are discarded.

Example

Suppose that the sender wants to send 4 frames each of 8 bits, where the frames are 11001100, 10101010, 11110000 and 11000011.

The sender adds the bits using 1s complement arithmetic. While adding two numbers using 1s complement arithmetic, if there is a carry over, it is added to the sum.

After adding all the 4 frames, the sender complements the sum to get the checksum, 11010011, and sends it along with the data frames.

The receiver performs 1s complement arithmetic sum of all the frames including the checksum. The result is complemented and found to be 0. Hence, the receiver assumes that no error has occurred.

Implementing Checksum Using Java

At the Sender Side : 

1. First, ask for the length of data to send, in order to ascertain the number of segments.
2. Then perform one complement of each data being entered simultaneously adding them. This means the sum would not be required to be complimented again.
3. Then send the data along with the computed checksum to the server.
4. Then report the successful transference of the message or otherwise depending on the feedback received from the server.

// Java code for Checksum_Sender package checksum_sender;   import java.io.*; import java.net.*; import java.util.*;   public class Checksum_Sender {     // Setting maximum data length     private int MAX = 100;           // initialize socket and I/O streams     private Socket socket = null;     private ServerSocket servsock = null;     private DataInputStream dis = null;     private DataOutputStream dos = null;           public Checksum_Sender(int port) throws IOException     {         servsock = new ServerSocket(port);                   // Used to block until a client connects to the server         socket = servsock.accept();                   dis = new DataInputStream(socket.getInputStream());         dos = new DataOutputStream(socket.getOutputStream());                   while (true)         {             int i, l, sum = 0, nob;             Scanner sc = new Scanner(System.in);             System.out.println("Enter data length");             l = sc.nextInt();                           // Array to hold the data being entered             int data[] = new int[MAX];                           // Array to hold the complement of each data             int c_data[] = new int[MAX];                           System.out.println("Enter data to send");                           for (i = 0; i < l; i++)             {                 data[i] = sc.nextInt();                                   // Complementing the entered data                 // Here we find the number of bits required to represent                 // the data, like say 8 requires 1000, i.e 4 bits                 nob = (int)(Math.floor(Math.log(data[i]) / Math.log(2))) + 1;                                   // Here we do a XOR of the data with the number 2^n -1,                 // where n is the nob calculated in previous step                 c_data[i] = ((1 << nob) - 1) ^ data[i];                                   // Adding the complemented data and storing in sum                 sum += c_data[i];             }                           // The sum(i.e checksum) is also sent along with the data             data[i] = sum;             l += 1;                           System.out.println("Checksum Calculated is : " + sum);             System.out.println("Data being sent along with Checksum.....");                           // Sends the data length to receiver             dos.writeInt(l);                           // Sends the data one by one to receiver             for (int j = 0; j < l; j++)                 dos.writeInt(data[j]);                           // Displaying appropriate message depending on feedback received             if (dis.readUTF().equals("success"))             {                   System.out.println("Thanks for the feedback!! Message received                                    Successfully!");                 break;             }                           else if (dis.readUTF().equals("failure"))             {                 System.out.println("Message was not received successfully!");                 break;             }         }                   // Closing all connections         dis.close();         dos.close();         socket.close();     }       // Driver Method     public static void main(String args[]) throws IOException     {         Checksum_Sender cs = new Checksum_Sender(45678);     } }

At the Receiver Side :

1. The receiver waits for data to arrive from the sender.
2. Once the data along with checksum is received from the sender, the receiver complements what is received and simultaneously keeps on adding them.
3. Finally, the receiver complements the above sum and checks whether the result is a zero or not, and reports the same to the sender. A zero would indicate a successful data transfer and anything else would indicate an error in the data that is received.

// Java code for Checksum_Receiver package checksum_sender;   import java.net.*; import java.io.*; import java.util.*;    public class Checksum_Receiver {           // Initialize socket and I/O streams     private Socket s = null;     private DataInputStream dis = null;     private DataOutputStream dos = null;           // Constructor to put ip address and port     public Checksum_Receiver(InetAddress ip,int port)throws IOException     {                   // Opens a socket for connection         s = new Socket(ip,port);                   dis = new DataInputStream(s.getInputStream());         dos = new DataOutputStream(s.getOutputStream());                   while (true)         {   Scanner sc = new Scanner(System.in);             int i, l, nob, sum = 0, chk_sum;                           // Reads the data length sent by sender             l = dis.readInt();                           // Initializes the arrays based on data length received             int c_data[] = new int[l];             int data[] = new int[l];                           System.out.println("Data received (along with checksum) is");                           for(i = 0; i< data.length; i++)             {                   // Reading the data being sent one by one                 data[i] = dis.readInt();                 System.out.println(data[i]);                                   // Complementing the data being received                 nob = (int)(Math.floor(Math.log(data[i]) / Math.log(2))) + 1;                 c_data[i] = ((1 << nob) - 1) ^ data[i];                                   // Adding the complemented data                 sum += c_data[i];             }             System.out.println("Sum(in ones complement) is : "+sum);                           // Complementing the sum             nob = (int)(Math.floor(Math.log(sum) / Math.log(2))) + 1;             sum = ((1 << nob) - 1) ^ sum;             System.out.println("Calculated Checksum is : "+sum);                           // Checking whether final result is 0 or something else             // and sending feedback accordingly             if(sum == 0)             {                   dos.writeUTF("success");                 break;             }                 else             {                   dos.writeUTF("failure");                 break;             }         }                   // Closing all connections         dis.close();         dos.close();         s.close();     }           // Driver Method     public static void main(String args[])throws IOException     {           // Getting ip address on which the receiver is running         // Here, it is "localhost"         InetAddress ip = InetAddress.getLocalHost();         Checksum_Receiver cr = new Checksum_Receiver(ip,5000);     }    }