Longitudinal Redundancy Check
In this technique, a block of bits is organized in the form of rows and columns. For example, suppose the sender wants to send a block of 32 bits. Before transmitting, we organize the 32 bits in a table form, which consists of four rows and eight columns. We then calculate the parity bit for each column and create a new row of eight bits which are the parity bits for the whole block. Remember that the first parity bit in the fifth row is calculated based on all first bits. The second parity bits in the fifth row is calculated based on all second bits, and so on. We then attach the fifth row which consists of eight parity bits to the original data (i.e. 32 bits) and send them to the receiver (Figure 3.7 illustrates longitudinal redundancy check).

The receiver checks the LRC block, 10101010 and follows the even-parity rule. After this, the block of data unit is accepted.  illustrates actual data unit plus LRC, received by the receiver when data is corrupted during transmission.

When the receiver checks the LRC, some of the bits do not follow the even-parity rule and the whole block is discarded (the non-matching bits are shown in bold).

Cyclic Redundancy Check (CRC)
One of the most common, and one of the most powerful of the redundancy checking technique is the Cyclic Redundancy Check (CRC). Parity check and Longitudinal redundancy check are based on addition, while CRC is based on binary division. CRC can be described as follows. Given a data or message (k-bit block of bits), the transmitter generates an n-bit sequence, so that the sender can transmit the k + n bits, which is exactly divisible by some predetermined number. The receiver checks the data unit (k + n bits). The data unit is divided by a predetermined number, and if there is no remainder, then there is no error.

Step 1:  A string of n Os is appended to the data unit. The number n is less than the number of bits in the predetermined divisior, which is n + 1 bits. Step 2: The newly elongated data unit is divided by the divisor using a process called binary division. The remainder resulting from this division is the CRC.
Step 3: The CRC of n bits derived in Step 2 replaces the appended Os at the end of the data unit. Note that the CRC may consist of all Os.
Step 4: The data unit arrives at the receiver data first, followed by the CRC. The receiver treats the whole string as a unit and divides it by the same divisor that was used to find the CRC remainder.
Step 5:  If the string arrives without error, the CRC checker yields a remainder of zero and the data unit passes. If the string has been changed in transit, the division yields a non-zero remainder and the data unit does not pass. In the first step, the four-bit divisior (1101) is subtracted from the first four bits of the dividend (1001), yielding 100 (the leading 0 of the remainder is dropped off). The next unused bit from the dividend is then pulled down to make the number of bits in the remainder equal to the bits in the divisor. The next step, 1000 - 1101, yields 101, and so on.

In this process, the divisor can only be subtracted from a dividend/remainder whose leftmost bit is one. Anytime the leftmost bit of the dividend/remainder is 0, we must use 0000 instead of the original divisor. This restriction implies that at any step, the leftmost subtraction will be either 0 - 0 or 1 - 1 both of which equal 0. This process repeats until the entire dividend has been used. Here, the CRC is 001. Figure 3.13 illustrates the CRC checker like CRC generator. The sender sends the data plus CRC to the receiver, after receiving the data appended with CRC (see Figure 3.11). Here, the bit-divisor (1101) is the same as in CRC generator. If the remainder is all Os, the CRC is dropped and the data accepted; otherwise the data will be rejected.

Checksum
The error detection method used by the higher-layer protocols is called checksum. Checksum is based on the concept of redundancy. Here, the sender uses checksum generator and the receiver uses checksum checker.
The checksum generator subdivides the data unit into equal segments of n bits (usually 16). These segments are added together. The complement of the result obtained by adding the segments, called the checksum field, is added to the end of the original data unit as the redundancy bit. The sender transmits the data unit plus checksum. The example data unit consists of 16 bits as: 10101001 00111001. The data unit is divided into two segments of S bits as: 10101001 and 00111001. Both segments are added (using one's complement arithmetic) as: 10101001 00111001 11100010 (sum)Checksum is the complement of the sum, that is, it is 00011101. The checksum is added to the data unit. The pattern sent is: 10101001 00111001 00011101The receiver receives the above pattern. The receiver then adds the three sections together, and will get all is, which, after complementing, is all Os. This show that there is no error in transmission.
To summarize,
10101001      (data segment)
00111001      (data segment)
00011101 (checksum)
11111111 (sum)
 00000000 (complement)

BACK