Ch6 Error Detection and Correction
Ch6 Error Detection and Correction
Ch6 Error Detection and Correction
Chapter 6
Error Detection and
Correction
8.3
8.4
8.5
8.6
8.7
8.8
8.9
8.10
8.11
TYPES OF ERROR
Single-Bit Error
• Only 1 bit in the data unit has changed from 1
to 0 or from 0 to 1.
8.12
Burst Error
DETECTION VS CORRECTION
• In error detection, just to see if any error has
occurred. Numbers of error is not important
• While in error correction, need to know the
exact number of bits that are corrupted.
Number of the errors are important
8.14
MODULAR-2 ARITHMETIC
• Use XOR (exclusive OR) operation for both
addition and subtraction.
Adding : 0+0=0 0+1=1 1+0=1 1+1=0
Subtracting : 0 – 0 = 0 0–1=1 1–0=1 1–1=0
8.18
ERROR DETECTION
8.20
8-3 LINEAR BLOCK CODES
8.21
8.22
8.23
Figure 8.10 Encoder and decoder for simple parity-check code
8.24
TYPES OF LINEAR BLOCK CODES
8.25
• Example 8.2
Let us assume that k = 2 and n = 3. Table 8.1 shows the list of datawords and
codewords. Later, we will see how to derive a codeword from a dataword
Datawords Codewords
00 000
01 011 Table 8.1 A code C(3,2)
10 101 for error detection
11 110
Assume the sender encodes the dataword 01 as 011 and sends it to the
receiver. Consider the following cases:
1.The receiver receives 011. It is a valid codeword. The syndrome is 0. The
8.28
• A better approach is the two-dimensional parity check
• A block of bits is organized in a table (rows and columns).
• At first, the parity bit is calculated for each data unit.
• Second, the parity bit is organized into a table.
• This method increases the likelihood of detecting burst errors.
8.29
8.30 Figure 8.11 Two-dimensional parity-check code
Hamming Codes
• Originally designed with dmin = 3, which means that they can detect
up to two errors or correct one single error
• The relationship between m and n in these codes is 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 Hamming code C(7,4) with dmin = 3
8.32
Table 8.5 Logical decision made by the correction logic analyzer
• Example 8.13
Let us trace the path of three datawords from the sender to the
destination:
1. The dataword 0100 becomes the codeword 0100011. The codeword
0100011 is received. The syndrome is 000, the final dataword is 0100.
2. The dataword 0111 becomes the codeword 0011001. The syndrome is
011. After flipping b2 (changing the 1 to 0), the final dataword is 0111.
3. The dataword 1101 becomes the codeword 1101000. The syndrome is
101. After flipping b0, we get 0000, the wrong dataword. This shows
that our code cannot correct two errors
8.33
8-4 CYCLIC CODES
8.34
CYCLIC REDUNDANCY CHECK
• Used in networks such as LANs and WANs
8.35
8.36
Figure 8.14 CRC encoder and decoder
8.37
Encoder
CRC
8.39
Decoder
8.41
8-5 CHECKSUM
8.42
8.43
8.44
8.45
8.46
8.47
8.48
Original Data Transmitted Data
CRC
8.49
8.50
8.51
Figure 8.24 Example 8.22
8.52
INTERNET CHECKSUM
• Sender site:
1. The message is divided into 16-bit words.
2. The value of the checksum word is set to 0.
3. All words including the checksum are added using one’s complement
addition.
4. The sum is complemented and becomes the checksum.
5. The checksum is sent with the data.
• Receiver site:
1. The message (including checksum) is divided into 16-bit words.
2. All words are added using one’s complement addition.
3. The sum is complemented and becomes the new checksum.
4. If the value of checksum is 0, the message is accepted; otherwise, it is
rejected.
8.53
• Example 8.23
Let us calculate the checksum for a text of 8 characters (“Forouzan”). The
text needs to be divided into 2-byte (16-bit) words. We use ASCII (see
Appendix A) to change each byte to a 2-digit hexadecimal number. For
example, F is represented as 0x46 and o is represented as 0x6F. Figure 8.25
shows how the checksum is calculated at the sender and receiver sites. In
part a of the figure, the value of partial sum for the first column is 0x36. We
keep the rightmost digit (6) and insert the leftmost digit (3) as the carry in the
second column. The process is repeated for each column. Note that if there is
any corruption, the checksum recalculated by the receiver is not all 0s. We
leave this an exercise.
8.54
Figure 8.25 Example 8.23
8.55
Advantages Vs Disadvantage
Advantages
• Checksum can detects all errors involving an
odd number of bits as well as most errors
involving an even number of bits
Disadvantages
• The checksum cannot detect errors when one or
more bits of a segment are damaged and the
corresponding bit or bits of opposite value in a
second segment are also damaged
8.56