Hardware Reference
In-Depth Information
because with such a code there is no way that
d
single-bit errors can change a valid
codeword into another valid codeword. Similarly, to correct
d
single-bit errors,
you need a distance 2
d
1 code because that way the legal codewords are so far
apart that even with
d
changes, the original codeword is still closer than any other
codeword, so it can be uniquely determined.
As a simple example of an error-detecting code, consider a code in which a
single
parity bit
is appended to the data. The parity bit is chosen so that the num-
ber of 1 bits in the codeword is even (or odd). Such a code has a distance 2, since
any single-bit error produces a codeword with the wrong parity. In other words, it
takes two single-bit errors to go from a valid codeword to another valid codeword.
It can be used to detect single errors. Whenever a word containing the wrong par-
ity is read from memory, an error condition is signaled. The program cannot con-
tinue, but at least no incorrect results are computed.
As a simple example of an error-correcting code, consider a code with only
four valid codewords:
+
0000000000,
0000011111,
1111100000,
and 1111111111
This code has a distance 5, which means that it can correct double errors. If the
codeword 0000000111 arrives, the receiver knows that the original must have been
0000011111 (if there was no more than a double error). If, however, a triple error
changes 0000000000 into 0000000111, the error cannot be corrected.
Imagine that we want to design a code with
m
data bits and
r
check bits that
will allow all single-bit errors to be corrected. Each of the 2
m
legal memory words
has
n
illegal codewords at a distance 1 from it. These are formed by systematically
inverting each of the
n
bits in the
n
-bit codeword formed from it. Thus each of the
2
m
legal memory words requires
n
1 bit patterns dedicated to it (for the
n
pos-
sible errors and correct pattern). Since the total number of bit patterns is 2
n
,we
must have
+
1)2
m
2
n
. Using
(
n
+
≤
n
=
m
+
r
,
this
requirement becomes
2
r
.Given
m
, this puts a lower limit on the number of check bits
needed to correct single errors. Figure 2-13 shows the number of check bits re-
quired for various memory word sizes.
(
m
+
r
+
1)
≤
Word size Check bits Total size Percent overhead
8
4
12
50
16
5
21
31
32
6
38
19
64
7
71
11
128
8
136
6
256
9
265
4
512
10
522
2
Figure 2-13.
Number of check bits for a code that can correct a single error.
