Page 311 - Discrete Mathematics and Its Applications

290 4 / Number Theory and Cryptography

EXAMPLE 4 Parity Check Bits Digital information is represented by bit string, split into blocks of a
specified size. Before each block is stored or transmitted, an extra bit, called a parity check bit,
can be appended to each block. The parity check bit x n+1 for the bit string x 1 x 2 ...x n is defined
by

x n+1 = x 1 + x 2 + ··· + x n mod 2.

It follows that x n+1 is 0 if there are an even number of 1 bits in the block of n bits and it is 1 if
there are an odd number of 1 bits in the block of n bits. When we examine a string that includes
a parity check bit, we know that there is an error in it if the parity check bit is wrong. However,
when the parity check bit is correct, there still may be an error. A parity check can detect an odd
number of errors in the previous bits, but not an even number of errors. (See Exercise 14.)
Suppose we receive in a transmission the bit strings 01100101 and 11010110, each ending
with a parity check bit. Should we accept these bit strings as correct?

Solution: Before accepting these strings as correct, we examine their parity check bits. The
parity check bit of the first string is 1. Because 0 + 1 + 1 + 0 + 0 + 1 + 0 ≡ 1 (mod 2), the
parity check bit is correct. The parity check bit of the second string is 0. We find that 1 + 1 +
0 + 1 + 0 + 1 + 1 ≡ 1 (mod 2), so the parity check is incorrect. We conclude that the first
string may have been transmitted correctly and we know for certain that the second string was
transmitted incorrectly. We accept the first string as correct (even though it still may contain an
even number of errors), but we reject the second string. ▲

Check bits computed using congruences are used extensively to verify the correctness of
various kinds of identification numbers. Examples 5 and 6 show how check bits are computed
for codes that identify products (Universal Product Codes) and books (International Standard
Book Numbers). The preambles to Exercises 18, 28, and 32 introduce the use of congruences
to find and use check digits in money order numbers, airline ticket numbers, and identification
numbers for periodicals, respectively. Note that congruences are also used to compute check
digits for bank account numbers, drivers license numbers, credit card numbers, and many other
types of identification numbers.

EXAMPLE 5 UPCs Retail products are identified by their Universal Product Codes (UPCs). The most
common form of a UPC has 12 decimal digits: the first digit identifies the product category, the
next five digits identify the manufacturer, the following five identify the particular product, and
the last digit is a check digit. The check digit is determined by the congruence

3x 1 + x 2 + 3x 3 + x 4 + 3x 5 + x 6 + 3x 7 + x 8 + 3x 9 + x 10 + 3x 11 + x 12 ≡ 0 (mod 10).

Answer these questions:

(a) Suppose that the first 11 digits of a UPC are 79357343104. What is the check digit?
(b) Is 041331021641 a valid UPC?

Solution: (a) We insert the digits of 79357343104 into the congruence for UPC
check digits. This gives 3 · 7 + 9 + 3 · 3 + 5 + 3 · 7 + 3 + 3 · 4 + 3 + 3 · 1 + 0 + 3 · 4 +
x 12 ≡ 0 (mod 10). Simplifying, we have 21 + 9 + 9 + 5 + 21 + 3 + 12 + 3 + 3 + 0 + 12 +
x 12 ≡ 0 (mod 10). Hence, 98 + x 12 ≡ 0 (mod 10). It follows that x 12 ≡ 2 (mod 10), so the
check digit is 2.

(b) To check whether 041331021641 is valid, we insert the digits into the congruence these digits
must satisfy. This gives 3 · 0 + 4 + 3 · 1 + 3 + 3 · 3 + 1 + 3 · 0 + 2 + 3 · 1 + 6 + 3 · 4 + 1 ≡
0 + 4 + 3 + 3 + 9 + 1 + 0 + 2 + 3 + 6 + 12 + 1 ≡ 4 ≡ 0 (mod 10). Hence, 041331021641
is not a valid UPC. ▲