Error Detection and Correction - Chapter 10

Chapter 10
Error Detection
and
Correction
10.1 Copyright © The McGraw-Hill Companies, Inc. Permission required for reproduction or display.
• Data can be corrupted during transmission.
• Some applications require that errors be

detected and corrected.
Types of Errors:
1.Single bit error
2.Burst error
Figure 10.1 Single-bit error

Figure 10.2 Burst error of length 8
Error occurs in 2 or more bits

To detect or correct errors, we need to
send extra (redundant) bits with data.
Methods to error detection and correction:
Simple parity check

2D parity check
Hamming code
Cyclic Redandency Check
A simple parity-check code is a
single-bit error-detecting
code.
Even parity: a codeword has an even

number of 1’s
odd parity: there are an odd number of 1’s

in the codeword
Table 10.3 Simple parity-check code C(5, 4)
Figure 10.10 Encoder and decoder for simple parity-check code
Example 10.12
Let us look at some transmission scenarios. Assume the

sender sends the dataword 1011. The codeword created
from this dataword is 10111, which is sent to the receiver.
We examine five cases:
1. No error occurs; the received codeword is 10111. The

syndrome is 0. The dataword 1011 is created.
2. One single-bit error changes a1 . The received
codeword is 10011. The syndrome is 1. No dataword
is created.
3. One single-bit error changes r0 . The received codeword
is 10110. The syndrome is 1. No dataword is created.
Example 10.12 (continued)
4. An error changes r0 and a second error changes a3 .

The received codeword is 00110. The syndrome is 0.
The dataword 0011 is created at the receiver.
dataword is wrongly created due to the syndrome value.
5. Three bits—a3, a2, and a1—are changed by errors.

The received codeword is 01011. The syndrome is 1.
The dataword is not created.
simple parity check, guaranteed to detect one single error,
can also find any odd number of errors.

Figure 10.11 Two-dimensional parity-check code
All Hamming codes discussed in this
book have dmin = 3 (2 bit error detection
and single bit error correction).
A codeword consists:
n bits
k are data bits
r are check bits.
Let m = r, then we have: n = 2m -1
and k = n-m
Example: r=3, n=8-1=7 and k=n-3=8
Hamming Code- Error Detection
Codewords:
[Data bits(Datawords) parity bits]
Codeword
D4 D3 D2 P3 D1 P2 P1
7 6 5 4 3 2 1
C7 C6 C5 C4 C3 C2 C1
Position of parity bits: 2n th position of codeword

Where n=0,1,2,3……
Codeword formation:
Codeword
D4 D3 D2 P3 D1 P2 P1
7 6 5 4 3 2 1
C7 C6 C5 C4 C3 C2 C1
P1 depends on = { D1 D2 D4} or {C3 C5 C7}

Example: Assume your dataword ‘1011’. Form the

codeword using hamming code at the transmitter side.
Consider even parity state.
Solution:
P1 ={ D1 D2 D4} = {1 1 1}=Total no. of 1s is odd, thus P1=1
P2 = { D1 D3 D4}={1 0 1 }= total no of 1s is even, thus p2=0
P3 = { D2 D3 D4} = {1 0 1}= total no. of 1s is even , thus p 3=0
Codeword
D4 D3 D2 P3 D1 P2 P1
1 0 1 0 1 0 1
The structure of the encoder and decoder for a Hamming code
Dataword Dataword
Parities
Codeword Codeword
Assume we have received: codeword as
‘1110101’ at the receiver.
Codeword
1 1 1 0 1 0 1
7 6 5 4 3 2 1
C7 C6 C5 C4 C3 C2 C1
P1 = { P1 C3 C5 C7}={1 1 1 1}=total no. of 1s is even, thus p1=0
P2 = {P2 C3 C6 C7} ={0 1 1 1}=total no. of 1s is odd thus p2=1
P3 = {P3 C5 C6 C7}= {0 1 1 1} =total no. of 1s is odd, thus p3=1
Position of error: p3p2p1= {110}2 = {6}10

Correct data word:
10-4 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.
Topics discussed in this section:
Cyclic Redundancy Check (CRC)
Polynomials
Cyclic Code Analysis
Advantages of Cyclic Codes
Other Cyclic Codes
10.
Table 10.6 A CRC code with C(7, 4)
Divisor: 1011
Figure 10.14 CRC encoder and decoder
 The remainder produced by the checker is a syndrome

 when no error has occurred; the syndrome is 000
 When there is one single error, the syndrome is not all 0’s
Figure 10.15 Division in CRC encoder
Figure 10.16 Division in the CRC decoder for two cases
Generate
codeword using
CRC method.
Assume dataword
is ‘100100’ and
divisor is ‘1101’.
Transmitted
codeword:
100100001
Using Polynomials
 We can use a polynomial to represent a
binary word.
 Each bit from right to left is mapped onto a
power term.
 The rightmost bit represents the “0” power
term. The bit next to it the “1” power term,
etc.
 If the bit is of value zero, the power term is
deleted from the expression.
Figure 10.21 A polynomial to represent a binary word
Figure 10.22 CRC division using polynomials
Note
The divisor in a cyclic code is normally

called the generator polynomial
or simply the generator.
10.
Note
In a cyclic code,
If s(x) ≠ 0, one or more bits is corrupted.
If s(x) = 0, either
a. No bit is corrupted. or
b. Some bits are corrupted, but the
decoder failed to detect them.
10.

Error Detection and Correction - Chapter 10

Uploaded by

Copyright:

Available Formats

Error Detection and Correction - Chapter 10

Uploaded by

Document Information

Original Description:

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Error Detection and Correction - Chapter 10

Uploaded by

Copyright:

Available Formats

Chapter 10

• Some applications require that errors be

Figure 10.1 Single-bit error

Error occurs in 2 or more bits

Methods to error detection and correction:

Simple parity check

Even parity: a codeword has an even

odd parity: there are an odd number of 1’s

Let us look at some transmission scenarios. Assume the

1. No error occurs; the received codeword is 10111. The

4. An error changes r0 and a second error changes a3 .

dataword is wrongly created due to the syndrome value.

5. Three bits—a3, a2, and a1—are changed by errors.

simple parity check, guaranteed to detect one single error,

can also find any odd number of errors.

Position of parity bits: 2n th position of codeword

P1 depends on = { D1 D2 D4} or {C3 C5 C7}

Example: Assume your dataword ‘1011’. Form the

P2 = { D1 D3 D4}={1 0 1 }= total no of 1s is even, thus p2=0

P3 = { D2 D3 D4} = {1 0 1}= total no. of 1s is even , thus p 3=0

P1 = { P1 C3 C5 C7}={1 1 1 1}=total no. of 1s is even, thus p1=0

P2 = {P2 C3 C6 C7} ={0 1 1 1}=total no. of 1s is odd thus p2=1

P3 = {P3 C5 C6 C7}= {0 1 1 1} =total no. of 1s is odd, thus p3=1

Position of error: p3p2p1= {110}2 = {6}10

Cyclic codes are special linear block codes with one

 The remainder produced by the checker is a syndrome

The divisor in a cyclic code is normally

You might also like