Exercises 3.6 Additional Exercises: Detecting Errors

    <exercises>
        <title>Additional Exercises: Detecting Errors</title>

<!--EXERCISE GROUP

        <introduction>
            <p>Credit card companies, banks, book publishers, and supermarkets all take advantage of the properties of integer arithmetic modulo <m>n</m> and group theory to obtain error detection schemes for the identification codes that they use.</p>
        </introduction>
    -->

        <!-- % TWJ, 2010/03/31 -->
        <!-- % Fixed figure reference -->

        <!-- % TWJ, 2012/10/21 -->
        <!-- % Deleted the word "now" in the description of UPC symbols.  Suggested by R. Beezer. -->

        <exercise>
            <title>UPC Symbols</title>

            <statement>
                <p>Universal Product Code<idx><h>Universal Product Code</h></idx> (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 (<xref ref="figure-upc-codes"/>). The first 11 digits contain information about the product; the twelfth digit is used for error detection. If <m>d_1 d_2 \cdots d_{12}</m> is a valid UPC number, then 
                <md>3 \cdot d_1 + 1 \cdot d_2 + 3 \cdot d_3 + \cdots + 3 \cdot d_{11} + 1 \cdot d_{12} \equiv 0 \pmod{10}</md>.</p>

                <ol>
                    <li><p>Show that the UPC number  0-50000-30042-6, which appears in <xref ref="figure-upc-codes"/>, is a valid UPC number.</p></li>
                    <li><p>Show that the number 0-50000-30043-6 is not a valid UPC number.</p></li>
                    <li><p>Write a  formula to calculate the check digit, <m>d_{12}</m>, in the UPC number.</p></li>
                    <li><p>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? </p></li>
                    <!-- % Corrected exercise. Suggested by John Watterlond. TWJ 8/24/2011 -->
                    <li><p>Write a program that will determine whether or not a UPC number is valid.</p></li>
                </ol>

                <figure xml:id="figure-upc-codes">
                    <caption>A UPC code</caption>
                    <image width="30%" source="UPCcode.png"/>
                </figure>
            </statement>
        </exercise>

        <exercise>
            <statement>
                <p>It is often useful to use an inner product notation for this type of error detection scheme; hence, we will use the notion
                    <md>(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n }</md>
                to mean
                    <md>d_1 w_1 +  d_2 w_2 + \cdots +  d_k w_k  \equiv 0  \pmod{ n}</md>.</p>

                <p>Suppose that <m>(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}</m> is an error detection scheme for the <m>k</m>-digit identification number <m>d_1 d_2 \cdots d_k</m>, where <m>0 \leq d_i \lt n</m>.  Prove that all single-digit errors are detected if and only if <m>\gcd( w_i, n ) = 1</m> for  <m>1 \leq i \leq k</m>.</p>
            </statement>
        </exercise>

        <exercise>
            <statement>
                <p>Let <m>(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}</m> be an error detection scheme for the <m>k</m>-digit identification number <m>d_1 d_2 \cdots d_k</m>, where <m>0 \leq d_i \lt n</m>.  Prove that all transposition errors of two digits <m>d_i</m> and <m>d_j</m> are detected if and only if <m>\gcd( w_i - w_j, n ) = 1</m> for <m>i</m> and  <m>j</m> between 1 and <m>k</m>.</p>
            </statement>
        </exercise>

        <exercise>
            <title>ISBN Codes</title>

            <statement>
                <p>Every book has an International Standard Book Number<idx><h>International standard book number</h></idx> (ISBN) code.  This is a 10-digit code indicating the book's publisher and title.  The tenth digit is a check digit satisfying 
                    <md>(d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 )  \equiv 0 \pmod{11}</md>.
                One problem is that <m>d_{10}</m> 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.</p>

                <ol>
                    <li><p>Is ISBN 0-534-91500-0 a valid ISBN code?  What about ISBN 0-534-91700-0 and ISBN 0-534-19500-0?</p></li>
                    <li><p>Does this method detect all single-digit errors?  What about all transposition errors?</p></li>
                    <li><p>How many different ISBN codes are there?</p></li>
                    <li><p>Write a computer program that will calculate the check digit for the first nine digits of an ISBN code.</p></li>
                    <li><p>A publisher has houses in Germany and the United States.  Its German prefix is <c>3-540</c>.  If its United States prefix will be <c>0-abc</c>, find <c>abc</c> 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 <c>3</c> and English is <c>0</c>.  The next group of numbers identifies the publisher, and the last group identifies the specific book.</p></li>
                </ol>
            </statement>
        </exercise>

    </exercises>