Computer Networks (BCS502)
➔ In error detection, we are looking only to see if any error has occurred.
➔ In error correction, we need to know the exact number of bits that are corrupted and more
importantly, their location in the message.
Coding
Redundancy is achieved through various coding schemes. Coding schemes can be divided into two
broad categories: block coding and convolution coding.
BLOCK CODING
➔ In block coding, message is divided into blocks, each of k bits, called datawords.
➔ Add r redundant bits to each block to make the length n = k + r. The resulting n-bit blocks
are called codewords.
➔ With k bits, 2kdatawords can be created; with n bits, 2n codewords can be created.
➔ Since n >k, the number of possible codewords is larger than the number of possible
datawords.
Error Detection
If the following two conditions are met, the receiver can detect a change in the original codeword.
1. The receiver has (or can find) a list of valid codewords.
2. The original codeword has changed to an invalid one.
Hamming Distance
➔ The Hamming distance between two words (of the same size) is the number of
differences between the corresponding bits.
Department of CSE, CEC 2
Computer Networks (BCS502)
➔ The Hamming distance between two words x and y is shown as d(x, y).
➔ The Hamming distance can easily be found by applying the XOR operation on the two
words and count the number of 1s in the result.
Ex The Hamming distance d(10101, 11110) is 3 because
Minimum Hamming Distance
➔ It is the measurement that is used for designing a code is the minimum Hamming
distance of two.
➔ It is the smallest Hamming distance (dmin) between all possible pairs.
dmin in this case is 3
Hamming Distance and Error
When a codeword is corrupted during transmission, the Hamming distance between the sent and
received codewords is the number of bits affected by the error.
For example, if the codeword 00000 is sent and 01101 is received, 3 bits are in error and the
Hamming distance between the two is d(OOOOO, 01101) =3.
Minimum Distance for Error Detection
If s errors occur during transmission, the Hamming distance between the sent codeword and received
codeword is s. If the code is to detect up to s errors, the minimum distance between the valid codes
must be s + 1, so that the received codeword does not match a valid codeword.
We can look at this geometrically.
➔ Let us assume that the sent codeword x is at the center of a circle with radius s. All other
received codewords that are created by 1 to s are points inside the circle or on the perimeter
of the circle
➔ All other valid codewords must be outside the circle, as shown in Figure
Department of CSE, CEC 3
Computer Networks (BCS502)
4. The syndrome is passed to the decision logic analyzer. If the syndrome is 0, there is no
error in the received codeword; the data portion of the received codeword is accepted as
the dataword;
5. If the syndrome is 1, the data portion of the received codeword is discarded. The
dataword is not created.
CYCLIC CODES
➔ Cyclic codes are special linear block codes with one extra property.
➔ In a cyclic code, if a codeword is cyclically shifted (rotated), the result is another codeword.
For example, if 1011000 is a codeword and we cyclically left-shift, then 0110001 is also a
codeword.
➔ In this case, if we call the bits in the first word aoto a6 and the bits in the second word botob6,
we can shift the bits by using the following:
Cyclic Redundancy Check
It is a subset of cyclic codes called the cyclic redundancy check (CRC), which is used in
networks such as LANs and WANs.
Department of CSE, CEC 5
Computer Networks (BCS502)
In the encoder,
1. The dataword has k bits (4 here); the codeword has n bits (7 here).
2. The size of the dataword is augmented by adding n - k (3 here) 0s to the right-hand sideof
the word. The n-bit result is fed into the generator.
3. The generator uses a divisor of size n - k + I (4 here), predefined and agreed upon. The
generator divides the augmented dataword by the divisor (modulo-2 division).
4. The quotient of the division is discarded; the remainder (r2rlro) is appended to the
dataword to create the codeword.
The decoder,
1. Receives the possibly corrupted codeword.
2. A copy of all n bits is fed to the checker which is a replica of the generator.
3. The remainder produced by the checker is a syndrome of n - k (3 here) bits, which is fed
to the decision logic analyzer.
4. The analyzer has a simple function. If the syndrome bits are all as, the 4 leftmost bits of
the codeword are accepted as the dataword (interpreted as no error); otherwise, the 4 bits
are discarded (error).
Department of CSE, CEC 6