Cryptography Reference
In-Depth Information
is attached to each character before sending. The receiver removes the parity
bit, and executes the same computation as the sender to verify that the com-
putation agrees with the value of the parity bit. For instance, if
odd
parity is
chosen and agreed upon by receiver and sender, then the sender selects a parity
bit that will make the total number 1-bits odd. For each character, the receiver
computes the parity to ensure it is the same as the sender's computation. If
not, an error has been detected. However, if an even number of bits have been
altered, then the parity check cannot detect the errors since the total number
of 1-bits remains the same. This and other error detection methods, which we
will discuss, are subject to some such disadvantage. The need is to reduce the
probability
of the receiver's acceptance of transmission errors.
On pages 320 and 542, we made reference to the notion of a checksum, which
helps to detect errors in transmission. The means by which this is accomplished
is for the sender to view the data as a sequence of binary integers and compute
their sum. This may be a 16- or 32-bit checksum, often built into many networks.
Thus, there is ease of computation. However, checksums do not detect all
common errors such as simple bit reversal in some packets. For instance, if the
last bit in every packet is reversed, then the checksum will remain the same.
One mechanism for error detection that is superior to each of the above is the
cyclic redundancy check
(CRC), which we mentioned on page 541 in Appendix
D. The mechanism for computing a CRC is a shift register, which we discussed
on page 155, together with addition modulo 2. First, all values in the shift
registers are initialized to 0. Then the bits of the message are shifted one at a
time until the entire message has been processed into the shift register unit. The
receiver uses exactly the same shift register unit to calculate the CRC for the
message and to verify its agreement with the CRC transmitted by the sender.
A typical CRC is 16-bit, called CRC-16, where the sender appends an addi-
tional sixteen zeros to the message. Then the receiver computes a CRC over the
transmitted message together with the transmitted CRC. If there are no errors,
the computed value will be zero. As seen in Chapter 11, a mathematical means
for representing a message is the use of a binary polynomial. For example,
f
(
x
)=1+
x
5
+
x
12
+
x
16
might be used in CRC-16. Then an
n
-bit message would be represented by a
binary polynomial
d
(
x
) of degree
n
1, and the CRC value corresponding to
d
(
x
) is the 16-bit word represented by the polynomial,
r
(
x
)=
x
16
−
d
(
x
)
/f
(
x
)
.
It is a provable fact that CRCs detect more errors than checksums. For
instance, errors involving alterations to a small number of bits near one location
are called
burst errors
. Such errors are often caused by lightning for instance,
so detecting these is an important exercise. It can be shown that CRC-16 can
detect all burst errors of bitlength no more than 16, and more than 99% of
burst errors of greater bitlength. The downside is that CRCs are more diGcult
to compute than checksums or parity checks. Yet, a CRC can be implemented
with minimal cost, so it remains the error detection mechanism of choice.
·
Search WWH ::
Custom Search