CYCLIC REDUNDANCY CHECK (CRC)

CYCLIC REDUNDANCY CHECK (CRC)

In synchronous communications, CRC is used to verify the integrity of the entire packet or block of data. Integrity of the packet means whether the complete packet of data received in its correct form as it was sent from the sending end. In synchronous communications, parity checking is sufficient to ensure data integrity. In high-speed asynchronous communications, single bit corrections are not enough. As each packet is created, a CRC check is placed somewhere in the packet and is verified at the receiving end.

            CRC is a calculation method used to check the accuracy of a digital transmission over a communication link. The sending computer uses one of several formulas to calculate a value from the information contained in the data, and this value is appended to the message block before it is sent. The receiving computer performs the same calculation on the same data and should drive the same number. If the two CRCs  do not match, indicating that a transmission error has occurred, the receiving computer asks the sending computer to retransmit the data.

            This procedure is known as redundancy check because each transmission includes extra or redundant error-checking values as well as the data itself. A CRC is generated by dividing the total number of bits in the block of data being sent by a predetermined binary number. The reminder is then added to the packet and the packet is transmitted. On the receiving end, the reverse mathematical operation is performed to verify the packet contents. If the computation is successful, the packet is passed to the next step. If it fails, the issuing node is notified and the entire packet is re-transmitted.

            Common CRC patterns are 12-bit (CRC 12), 16-bit (CRC 16), and 32-bit (CRC 32).

One of the most common and widely used error detection methods for synchronous data transmission is Cyclic Redundancy Check (CRC), developed by IBM. IBM uses CRC-16 as the specific application of the CRC method. This process uses a constant "divisor" which is in binary form as ::

                          1000 1000 0001 0000 1

The steps are follows :

(a) Add 16 zeros (1 less bit than the number of bits in the "divisor") after the Least Significant Bit of the message to be sent. The message is then written down as it would be transmitted, with the extra bits sent first ( i.e. most significant bits).

(b) The divisor is exclusive ORed with the 16 most significant bits of the message are appended to the result of this to from another 16 bits of data headed by a 1.

(c) The exclusive ORing is repeated along with the rest of the process until all bits in the message are exhausted.

(d) The final exclusive OR result is the CRC characters. Enough leading zeros are appended to the CRC character to from a total of 16 bits.

           We shall try to understand the CRC character calculation using the following CRC-4 method with the modified divisor constant of 10011:

          Let the message be 1100 0110 1011 01 (The LSB is on the right)

          There is one less zero than the total number of bits in the divisor which is 10011. To use the shortened CRC-4 divisor, four zeros are

first appended to the message. The extended message becomes:

      

       110001101011010000

       Now we set up the problem:

       10011)110001101011010000

       

       Exclusive OR the first five bits with the "divisor" we have:

       10011)110001101011010000

             10011

             -----------

               1011

By bringing down the next bit from the message and repeating the process until all the bits in the appended message are used.

     We do this as shown below:

     10011)110001101011010000

           10011

           ----------

            10111

            10011

            ----------

             10010

             10011

             ----------

              11011

              10011

              ----------

               10000

               10011

               ----------

                 11100

                 10011

                 ----------

                  11110

                  10011

                  ----------

                   11010

                   10011

                   ----------

                     1001 = CRC

The original message followed by the CRC-16 bytes is sent to a receiving station. At the receiving station, the data are shifted in and a CRC is computed using the entire message plus the CRC bytes. If the same constant "divisor" is used, the result of the receiver's CRC computation is all zeros when there are no errors.

             To detect the correct communication errors, a sender must provide a receiver with information that enables the receiver to verify proper receipt of information or data. The sender could simply send an entire set of information twice and let the receiver compare the two sets of information for error detection, but because of the time and computer resources, it takes to perform this type of comparison. It is more popular to detect the error based on mathematical calculations that are hardware or software execute at high speed.

              The sender must use a mathematical technique to calculate error-checking data. The sender generates this redundancy data from the bit stream of information data from the bit stream of information data it sends and then appends the redundancy data to the end of the bit stream. The receiver must generate its own redundancy data from the information data it receives and compare the results with the redundancy data it receives from the sender. A favourable comparison indicates the absence of errors. An unfavourable comparison indicates the presence of errors.

CHECKSUM ERROR DETECTION

CHECKSUM ERROR DETECTION

Checksum is a calculated value that is used to test data integrity. Errors can occur when data is transmitted or when it is written to disk. One means of detecting such errors is use of a checksum. Checksum is a value calculated for a given chunk of data by sequentially combining all the bytes of data with a series of arithmetic or logical operations. After the data is transmitted or stored, a new checksum can be calculated (using the possibly faulty transmitted or stored data) and compared with the original one. If the checksum do not match, an error occurred, and the data should be transmitted or stored again. If they do match, the transmission or storage was probably error-free. Checksums are simple validation mechanism. They cannot detect all errors and they cannot be used to correct errors.

            The parity and LRC methods are not very reliable, when more than error occurs within a character or message. One major advantage of the CRC method is its ability to detect multiple errors within any length of message.

             Another major advantage of checksum is that it is simple to implement. In this method, each character being transmitted is exclusive ORed with an accumulated total of all previous characters. The final accumulated total is the checksum character sent with the message. Once again, at the receiver exclusive ORing all the characters and the transmitted checksum should produce a result of zero. Any other result indicates that an error has occurred.

             In comparison with CRC, checksum is more likely to experience similar values for different messages. While the odds that enough errors would cause a duplicate checksum to the one originally sent are reasonable high, that possibility is still far more likely than a similar occurrence using the CRC method.

See More -- 

                Cyclic Redundancy check 

HAMMING CODING TECHNIQUE

HAMMING CODING TECHNIQUE FOR ERROR CORRECTION

Hamming is a code is used to detect and correct errors in individual bits of transmitted data. Most land-based communications are satisfied by relying on checksum or CRC methods to detect errors. CRC correction requires re-transmission of faulty messages. But let us take the case of a satellite transmitting visual data as binary streams of information around another planet say Jupiter. The time it takes those messages to arrive at an Earth station from the satellite is measured in hours. During this time the satellite has adjusted its orbit and is going across new territory and sending additional data. Correcting errors in these messages cannot be done by re-transmission. A request for that re-transmission takes as long to get to the satellite as the original message took to get to Earth. Then consider the time it would take to resent the message. First satellite would have to be found. During the time it looks to send the original message and get the request to resent it, the satellite has gathered billions of additional data. The memory needed to hold data long enough to assure that were sent properly is staggering. Instead, an error-correction method such as the Hamming code is used so that errors can be corrected as they are detected.

             Hamming code provide a method for error correction. Error bits called Hamming bits, are inserted into the message at the random locations. It is believed that the randomness of their locations reduces the odds that these Hamming bits themselves would be in error. This is based on a mathematical assumption that because there are so many more message bits compared with hamming bits, there is a greater chance for a message bit to be in error than for a Hamming bit to be wrong. Determining the placement and binary value of the Hamming bits can be implemented using hardware, but it is often more practical to implement them using software. The number of bits in a message (M) are counted and used to solve the following equation to determine the number of Hamming bits (H) to be used.

 2^H ≥ H + M + 1

Once the number of hamming bits is determined, the actual placements of bits into the message are performed. It is important to note that despite the random nature of the hamming bit placements, exact placements must be known and used by both the transmitter and receiver.

This is necessary so that the receiver can remove the Hamming bits from the message and compare them with a similar set of bits generated at the receiver. Once the hamming bits are inserted into their positions, the numerical values of the bit positions of the logic 1 in the original message are listed. The equivalent binary numbers of these values are added and the sum produced is used as the sets of the Hamming bits in the message. The numerical difference between the Hamming values transmitted and that produced at the receiver indicates the bit position that contains a bad bit which is then inverted to correct it.

        We shall see the following example for sending the message Help!

        When sending the message Help! using synchronous data, start and stop bits as well as parity are not used. Each ASCII character contains 7 bits, for a total of 35 bits. The number of hamming bits is computed using equation

                     2^H ≥ H + M + 1

     H = 6 is the smallest value that satisfies the equation.

                    64 > 35 + 6 + 1 > 42

    For simplicity we will insert the Hamming bits, less randomly, at every other bit position, starting with the least significant bit:

                   H  e  l  p  !

100100011001011101100111000001H0H0H0H0H1H

To begin the process of determining the states of each of the Hamming bits, list of numerical value of each bit position whose state is a 1. Start with the least significant bit as 1 and increase the count by 1 for each succeeding bit position. H bit must be included in the counting (but not the listing) process. In our example, the first bit position with a 1 in it is position 2. The following are all the bit positions containing a 1 that is the positions 2, 12, 18, 19, 20, 23, 24, 26, 27, 28, 30, 33, 34, 38, and 41.

      The next step is to list the number of vertically along with the binary equivalent of each one. The value of the Hamming bits (H) is created by adding each binary bit column in the list, ignoring any carry condition.

2     0 0 0 0 1 0

12   0 0 1 1 0 0

18   0 1 0 0 1 0

19   0 1 0 0 1 1

20   0 1 0 1 0 0

23   0 1 0 1 1 1

24   0 1 1 0 0 0

26   0 1 1 0 1 0

27   0 1 1 0 1 1

28   0 1 1 1 0 0

30   0 1 1 1 1 0

33   1 0 0 0 0 1

34   1 0 0 0 1 0

38   1 0 0 1 1 0

41   1 0 1 0 0 1

----------------------------------------------------------------

H = 0 1 1 0 1 1

These values are submitted for the "H" bits in the message in the order shown. The receiver repeats the process, again ignoring the Hamming bit positions in the list. If everything is all right, a comparison of the H values sent and those generated by the receiver produces zero. When the receiver does the Hamming process, number 23 is omitted from the list. This causes the Hamming bits to have a value of 0 0 1 1 0 0 instead of 0 1 1 0 1 1. When the H bits computed at the receiver are compared with the transmitted H bits the result is as follows :

 H sent                             0 1 1 0 1 1     as shown above

 H computed at receiver  0 0 1 1  0 0 *

                                    -------------------------------

comparison results:          0 1 0 1 1 1 = 23 decimal

* because 23rd 1 will be changed to zero so the sum !

To correct the message the receiver would invert bit 23.

The reason why the Hamming code works is as follows:

     The originally transmitted codes are formulated by adding binary bits together, ignoring carries. The process of this addition is nothing more than exclusive ORing these bits together. A similar process occurs at the receiver. If a bit has changed state between being sent and  received , it either will not be included in the process or , in the case of changing from a 0 to a 1, will be added to the process. By exclusive ORing the two Hamming codes, the process is reversed. The errant bit appears as the difference between the transmitted and received Hamming bit values.

ASYNCHRONOUS DATA ERROR DETECTION ( PARITY BIT)

Asynchronous communication means the communication between two units operating independently. In this form of data transmission, information is sent one character at a time, with variable time intervals between characters.
       Because asynchronous does not reply on a shared timer that would enable the sending and receiving units to separate characters by specific time periods, each transmitted character consists of a number of data bits ( the character itself) preceded by a " begin character" signal, called start bit and ending in an optional parity bit followed by a stop bit.

" Parity bit is an added error-detection bit included with each character of the asynchronous data stream. Thus, it adds an additional bit to be transmitted with each character, reducing the efficiency of the data transfer because it takes more time to transmit a data character with a parity bit than to send one without a parity bit."



Parity has been used for detecting errors in asynchronous data streams where brust-type problems either do not exist or are extremely rare. Both the Telex and Teletype networks employ this method.
                   To correct error's detected using parity, the receiving station can only request that the message containing the error be re-transmitted. A system that is set to request re-transmission automatically in response to detecting an error includes Automatic Repeat Request (ARQ) processing within its communications software.
                    Not all systems using parity have ARQ. Some systems cause a parity error flag to be set in a status register, which, when read using applicable software, causes a message to be sent to a terminal to inform the user that a data error has occurred. It is then up to the user to request a message to be re-sent or not. The advantage of doing this is that some errors are less crucial. A user can easily figure what  the correct character should have been. For example, if the word "today" has an error in the last character, so that  the word read as "todaz", it can be readily understood and corrected without the need to re-transmit the message containing the word as it is obvious that the word is "today".

Data Correction Using Parity

An error correction process used with asynchronous data stream called Longitudinal Redundancy Check (LRC), makes use of the parity process. A method to detect the parity error to create the LRC character. This character is formed by summing the character bits and discarding the framing. Carries produced by the additions are ignored.
                 For example, suppose we have sent the word Help! For this we use the addition of the bits ignoring the last bit and the carry overs as seen 

below:
                           0001001 H
                           1010011 e
                           0011011 l
                           0000111 p
                           1000010 !
                       _____________
                           0000100 LRC

         The LRC error character is framed with start and stop bits and a parity bit is generated for it. It is then appended to the end of the message and sent to the receiver as (00000100111). The last two bits are as stop bits. The other bit is for parity.
         The receiver shifts each character and checking for parity errors, detects the error in the middle character. The receiver then computers the LRC for the received message and compares the two characters. The bit position that does not compare is the one that is incorrect  in the bad character. For example, if the said message is received as follows:

                        0001001 H
                        1010011 e
                        0001011 h
                        0000111 p
                        1000010 !
                     _____________
                        0010100   Receiver generated LRC
                        0000100   received LRC with message
                    _____________
                       0010000  comparison results because a 1 indicates the bad bit position.

     The detection of a bad parity bit in the "l" character designated the location of an error in that character. As a result of the comparison of the LRC, bit 3 of that character is detected as incorrect  and would be inverted  to yield the corrected character.

         Another method to show the detection of the bad bit is by using a matrix is shown in Figure. This is the matrix for the example word Help!. The character codes are arranged so that they are stacked vertically. Each individual parity bit is shown on the right of each character. These are not used as these are the redundancy bits. Longitudinal redundancy bits are shown at bottom of the matrix. Note that the longitudinal parity bits from the LCR character, which includes its own parity (VCR) bit. In part (b) of the Figure, the matrix is shown with the error. The comparison of the LCR bits from the transmitter and receiver is accomplished by adding the LRC character received to the entire message (including transmitted LRC). This works because adding binary numbers and comparing them is the same process of using exclusive ORs. Note that the circled parity (VCR) and LRC bits point to the bad bit.
     These methods of error correction are known as Forward Error Correction (FEC) because errors are corrected as the message is received.

" A brust type of interference destroying several bits and cannot be corrected by any of these methods."