Error Detection Hamming Codes 1 - Virginia Tech

Error Detection

Hamming Codes 1

Error detecting codes enable the detection of errors in data, but do not determine the

precise location of the error.

- store a few extra state bits per data word to indicate a necessary condition for the

data to be correct

- if data state does not conform to the state bits, then something is wrong

- e.g., represent the correct parity (# of 1¡¯s) of the data word

- 1-bit parity codes fail if 2 bits are wrong¡­

1011 1101

0001 0000

1101 0000

1111 0010

1

parity bit is 1:

data should

have an odd

number of 1's

A 1-bit parity code is a distance-2 code, in the sense that at least 2 bits must be changed

(among the data and parity bits) produce an incorrect but legal pattern. In other words,

any two legal patterns are separated by a distance of at least 2.

CS@VT

Computer Organization II

?2005-2013 McQuain

Parity Bits

Hamming Codes 2

Two common schemes (for single parity bits):

- even parity

0 parity bit if data contains an even number of 1's

- odd parity

0 parity bit if data contains an odd number of 1's

We will apply an even-parity scheme.

1011 1101

0001 0000

1101 0000

1111 0010

1

The parity bit could be stored at any fixed location with respect to the corresponding data

bits.

Upon receipt of data and parity bit(s), a check is made to see whether or not they

correspond.

Cannot detect errors involving two bit-flips (or any even number of bit-flips).

CS@VT

Computer Organization II

?2005-2013 McQuain

Hamming (7,4) Code

Hamming Codes 3

Richard Hamming (1950) described a method for generating minimum-length errordetecting codes. Here is the (7,4) Hamming code for 4-bit words:

Say we receive the data word 0100 and parity bits 011.

Those do not match (see the table).

Therefore, we know an error has occurred. But where?

CS@VT

Computer Organization II

Data bits

d4d3d2d1

Parity bits

P3p2p1

0000

000

0001

011

0010

101

0011

110

0100

110

0101

101

0110

011

0111

000

1000

111

1001

100

1010

010

1011

001

1100

001

1101

010

1110

100

1111

111

?2005-2013 McQuain

Hamming (7,4) Code

Hamming Codes 4

Suppose the parity bits are correct (011) and the data bits (0100) contain an error:

The received parity bits 011 suggest the data bits should

have been 0001 or 0110.

The first case would mean two data bits flipped.

The second would mean that one data bit flipped.

CS@VT

Computer Organization II

Data bits

d4d3d2d1

Parity bits

p3p2p1

0000

000

0001

011

0010

101

0011

110

0100

110

0101

101

0110

011

0111

000

1000

111

1001

100

1010

010

1011

001

1100

001

1101

010

1110

100

1111

111

?2005-2013 McQuain

Hamming (7,4) Code

Hamming Codes 5

Suppose the data bits (0100) are correct and the parity bits (011) contain an error:

The received data bits 0100 would match parity bits 110.

That would mean two parity bits flipped.

If we assume that only one bit flipped, we can conclude the

correction is that the data bits should have been 0110.

If we assume that two bits flipped, we have two equally

likely candidates for a correction, and no way to determine

which would have been the correct choice.

CS@VT

Computer Organization II

Data bits

d4d3d2d1

Parity bits

p3p2p1

0000

000

0001

011

0010

101

0011

110

0100

110

0101

101

0110

011

0111

000

1000

111

1001

100

1010

010

1011

001

1100

001

1101

010

1110

100

1111

111

?2005-2013 McQuain

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download