AATA Additional Exercises: Detecting Errors

Exercises 3.6 Additional Exercises: Detecting Errors

1. UPC Symbols.

Universal Product Code (UPC) symbols are found on most products in grocery and retail stores. The UPC symbol is a 12-digit code identifying the manufacturer of a product and the product itself (Figure 3.32). The first 11 digits contain information about the product; the twelfth digit is used for error detection. If

d_{1} d_{2} \dots d_{12}

is a valid UPC number, then

3 \cdot d_{1} + 1 \cdot d_{2} + 3 \cdot d_{3} + \dots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 (\mod 10) .

Show that the UPC number 0-50000-30042-6, which appears in Figure 3.32, is a valid UPC number.
Show that the number 0-50000-30043-6 is not a valid UPC number.
Write a formula to calculate the check digit, $d_{12},$ in the UPC number.
The UPC error detection scheme can detect most transposition errors; that is, it can determine if two digits have been interchanged. Show that the transposition error 0-05000-30042-6 is not detected. Find a transposition error that is detected. Can you find a general rule for the types of transposition errors that can be detected?
Write a program that will determine whether or not a UPC number is valid.

The vertical lines of a UPC bar scan code for 0-05000-30042-6 — Figure 3.32. A UPC code

🔗

2.

🔗

It is often useful to use an inner product notation for this type of error detection scheme; hence, we will use the notion

(d_{1}, d_{2}, \dots, d_{k}) \cdot (w_{1}, w_{2}, \dots, w_{k}) \equiv 0 (\mod n)

🔗

to mean

d_{1} w_{1} + d_{2} w_{2} + \dots + d_{k} w_{k} \equiv 0 (\mod n) .

🔗

Suppose that

(d_{1}, d_{2}, \dots, d_{k}) \cdot (w_{1}, w_{2}, \dots, w_{k}) \equiv 0 (\mod n)

is an error detection scheme for the

k

-digit identification number

d_{1} d_{2} \dots d_{k},

where

0 \leq d_{i} < n .

Prove that all single-digit errors are detected if and only if

gcd (w_{i}, n) = 1

for

1 \leq i \leq k .

🔗

3.

🔗

Let

(d_{1}, d_{2}, \dots, d_{k}) \cdot (w_{1}, w_{2}, \dots, w_{k}) \equiv 0 (\mod n)

be an error detection scheme for the

k

-digit identification number

d_{1} d_{2} \dots d_{k},

where

0 \leq d_{i} < n .

Prove that all transposition errors of two digits

d_{i}

and

d_{j}

are detected if and only if

gcd (w_{i} - w_{j}, n) = 1

for

i

and

j

between

1

and

k .

🔗

4. ISBN Codes.

🔗

Every book has an International Standard Book Number (ISBN) code. This is a 10-digit code indicating the book’s publisher and title. The tenth digit is a check digit satisfying

(d_{1}, d_{2}, \dots, d_{10}) \cdot (10, 9, \dots, 1) \equiv 0 (\mod 11) .

🔗

One problem is that

d_{10}

might have to be a 10 to make the inner product zero; in this case, 11 digits would be needed to make this scheme work. Therefore, the character X is used for the eleventh digit. So ISBN 3-540-96035-X is a valid ISBN code.

Is ISBN 0-534-91500-0 a valid ISBN code? What about ISBN 0-534-91700-0 and ISBN 0-534-19500-0?
Does this method detect all single-digit errors? What about all transposition errors?
How many different ISBN codes are there?
Write a computer program that will calculate the check digit for the first nine digits of an ISBN code.
A publisher has houses in Germany and the United States. Its German prefix is 3-540. If its United States prefix will be 0-abc, find abc such that the rest of the ISBN code will be the same for a book printed in Germany and in the United States. Under the ISBN coding method the first digit identifies the language; German is 3 and English is 0. The next group of numbers identifies the publisher, and the last group identifies the specific book.

Prev Top Next