Hardware Reference
In-Depth Information
the transmission has reversed the order of the characters in a word, as it should, but
it has also reversed the bytes in an integer, which it should not.
An obvious solution is to have the software reverse the bytes within a word
after the copy has been made. Doing this leads to Fig. 2-12(d) which makes the
two integers fine but turns the string into ''MIJTIMS'' with the ''H'' hanging in the
middle of nowhere. This reversal of the string occurs because when reading it, the
computer first reads byte 0 (a space), then byte 1 (M), and so on.
There is no simple solution. One way that works, but is inefficient, is to in-
clude a header in front of each data item telling what kind of data follows (string,
integer, or other) and how long it is. This allows the receiver to perform only the
necessary conversions. In any event, it should be clear that the lack of a standard
for byte ordering is a big nuisance when moving data between different machines.
2.2.4 Error-Correcting Codes
Computer memories occasionally make errors due to voltage spikes on the
power line, cosmic rays, or other causes. To guard against such errors, some mem-
ories use error-detecting or error-correcting codes. When these codes are used,
extra bits are added to each memory word in a special way. When a word is read
out of memory, the extra bits are checked to see if an error has occurred.
To understand how errors can be handled, it is necessary to look closely at
what an error really is. Suppose that a memory word consists of m data bits to
which we will add r redundant, or check, bits. Let the total length be n (i.e.,
n
r ). An n -bit unit containing m data and r check bits is often referred to as
an n -bit codeword .
Given any two codewords, say, 10001001 and 10110001, it is possible to deter-
mine how many corresponding bits differ. In this case, 3 bits differ. To determine
how many bits differ, just compute the bitwise Boolean EXCLUSIVE OR of the
two codewords and count the number of 1 bits in the result. The number of bit
positions in which two codewords differ is called the Hamming distance (Ham-
ming, 1950). Its main significance is that if two codewords are a Hamming dis-
tance d apart, it will require d single-bit errors to convert one into the other. For
example, the codewords 11110001 and 00110000 are a Hamming distance 3 apart
because it takes 3 single-bit errors to convert one into the other.
With an m -bit memory word, all 2 m bit patterns are legal, but due to the way
the check bits are computed, only 2 m of the 2 n codewords are valid. If a memory
read turns up an invalid codeword, the computer knows that a memory error has
occurred. Given the algorithm for computing the check bits, it is possible to con-
struct a complete list of the legal codewords, and from this list find the two code-
words whose Hamming distance is minimum. This distance is the Hamming dis-
tance of the complete code.
The error-detecting and error-correcting properties of a code depend on its
Hamming distance. To detect d single-bit errors, you need a distance d
=
m
+
+
1 code
 
 
Search WWH ::




Custom Search