Block Coding Techniques in Error Detection and Correction

In block coding, we divide our message into blocks, each of k bits, called data words. We add r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks are called code words.

For example, we have a set of data words, each of size k, and a set of code words, each of size of n. With k bits, we can create a combination of 2k data words, with n bits; we can create a combination of 2n code words. Since n > k, the number of possible code words is larger than the number of possible data words.

Read more ...

Hamming Distance in Error Control

The central concepts in coding for error control are the idea of the Hamming distance. The Hamming distance between two words (of the same size) is the number of differences between the corresponding bits. We show the Hamming distance between two words x and y as d(x, y).

The Hamming distance can easily be found if we apply the XOR operation on the two words and count the number of 1s in the result. Note that the Hamming distance is a value greater than zero.

1. The Hamming distance d(000, 011) is 2 because 000 ⊕  011 is 011 (two 1s).

2. The Hamming distance d(10101, 11110) is 3 because 10101 ⊕ 11110 is 01011 (three 1s).

Read more ...

Simple Parity Check Code

Linear Block Codes:

A linear block code is a code in which the exclusive OR (addition modulo-2) of two valid code words creates another valid code word.

The scheme in the above table is a linear block code because the result of XORing any code word with any other code word is a valid code word. For example, the XORing of the second and third code words creates the fourth one.

Read more ...

Hamming Codes:

The Hamming codes were originally designed with d_min = 3, which means that they can detect up to two errors or correct one single error. But there are some Hamming codes that can correct more than one error.

First let us find the relationship between n and k in a Hamming code. We need to choose an integer m >= 3. The values of n and k are then calculated from mas n = 2m – 1 and k= n-m. The number of check bits r =m.

For example, if m=3, then n= 7 and k= 4. This is a Hamming code C(7, 4) with d_min =3. The following Table shows the data words and code words for this code.

Read more ...

Cyclic codes in Error Detection and Correction

Cyclic codes are special linear block codes with one extra property. In a cyclic code, if a code word is cyclically shifted (rotated), the result is another code word. For example, if 1011000 is a code word and we cyclically left-shift, then 0110001 is also a code word.

In this case, if we call the bits in the first word a0 to a6 and the bits in the second word b0 to b6, we can shift the bits by using the following:

b1=a0  b2=a1  b3=a2  b4=a3  b5=a4  b6=a5   b0=a6

Cyclic Redundancy Check:

Read more ...

Checksum 

The checksum is used in the Internet by several protocols although not at the data link layer. Like linear and cyclic codes, the checksum is based on the concept of redundancy. Several protocols still use the checksum for error detection.

Consider the following example:

Our data is a list of five 4-bit numbers that we want to send to a destination. In addition to sending these numbers, we send the sum of the numbers. For example, if the set of numbers is (7, 11, 12, 0, 6), we send (7, 11, 12, 0, 6, 36), where 36 is the sum of the original numbers. The receiver adds the five numbers and compares the result with the sum. If the two are the same, the receiver assumes no error, accepts the five numbers, and discards the sum. Otherwise, there is an error somewhere and the data are not accepted.

Read more ...

Framing and Framing Protocols 

The data link layer, on the other hand, needs to pack bits into frames, so that each frame is distinguishable from another. Framing in the data link layer separates a message from one source to a destination, or from other messages to other destinations, by adding a sender address and a destination address. The destination address defines where the packet is to go; the sender address helps the recipient acknowledge the receipt.

Although the whole message could be packed in one frame, that is not normally done. One reason is that a frame can be very large, making flow and error control very inefficient. When a message is carried in one very large frame, even a single-bit error would require the retransmission of the whole message. When a message is divided into smaller frames, a single-bit error affects only that small frame.

Read more ...

Flow Control and Error Control

Flow Control:

Flow control coordinates the amount of data that can be sent before receiving an acknowledgment and is one of the most important duties of the data link layer. In most protocols, flow control is a set of procedures that tells the sender how much data it can transmit before it must wait for an acknowledgment from the receiver.

Any receiving device has a limited speed at which it can process incoming data and a limited amount of memory in which to store incoming data. The receiving device must be able to inform the sending device before those limits are reached and to request that the transmitting device send fewer frames or stop temporarily. Incoming data must be checked and processed before they can be used. The rate of such processing is often slower than the rate of transmission. For this reason, each receiving device has a block of memory, called a buffer, reserved for storing incoming data until they are processed. If the buffer begins to fill up, the receiver must be able to tell the sender to halt transmission until it is once again able to receive.

Read more ...