[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección3.5Ejercicios Adicionales: Detectando Errores

1Códigos UPC

El Código Universal de Productos (UPC por su sigla en inglés) se encuentra en la mayoría de los productos de supermercados y tiendas del retail. El UPC es un código de 12 dígitos que identifica al fabricante de un producto y al producto mismo (Figura 3.32). Los primeros 11 dígitos contienen información sobre el producto; el último dígito se usa para la detección de errores. Si \(d_1 d_2 \cdots d_{12}\) es un número UPC válido, entonces

\begin{equation*} 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}. \end{equation*}

  1. Muestre que el número UPC 0-50000-30042-6, que aparece en la Figura 3.32, es un número UPC válido.

  2. Muestre que el número 0-50000-30043-6 no es un número UPC válido.

  3. Escriba una fórmula para calcular el dígito verificador, \(d_{12}\text{,}\) de un número UPC.

  4. El método de detección de errores del UPC puede detectar la mayor parte de los errores de transposición; es decir, puede tereminar si dos dígitos fueron intercambiados. Muestre que el error de transposición 0-05000-30042-6 no es detectado. Encuentre un error de transposición que sí sea detectado. ¿Puede encontrar una regla general sobre cuáles son los errores de transposición que son detectados?

  5. Escriba un programa que determina si un número UPC es válido.

Figura3.32Un código UPC
2

Con frecuencia es útil usar la notación de producto interno para este método de detección de errores; de manera que usaremos la notación

\begin{equation*} (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \end{equation*}

para decir que

\begin{equation*} d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}. \end{equation*}

Supongamos que \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) es un método de detección de errores para el número de identificación de \(k\) dígitos \(d_1 d_2 \cdots d_k\text{,}\) donde \(0 \leq d_i \lt n\text{.}\) Demuestre que todos los errores en un solo dígito son detectados si y solo si \(\gcd( w_i, n ) = 1\) para \(1 \leq i \leq k\text{.}\)

3

Sea \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) un método de detección de errores para el número de identificación de \(k\) dígitos \(d_1 d_2 \cdots d_k\text{,}\) donde \(0 \leq d_i \lt n\text{.}\) Demuestre que todas las transposiciones de dos dígitos \(d_i\) y \(d_j\) son detectadas si y solo si \(\gcd( w_i - w_j, n ) = 1\) para \(i\) y \(j\) entre 1 y \(k\text{.}\)

4Códigos ISBN

Todo libro tiene un International Standard Book Number (ISBN). Este es un código de 10 dígitos que indica la editorial y el título del libro. El décimo dígito es un dígito verificador que satisface

\begin{equation*} (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 ) \equiv 0 \pmod{11}. \end{equation*}

Un problema es que \(d_{10}\) puede tener que ser 10 para que el producto interno sea cero; en ese caso, se requieren 11 dígitos para que funcione el método. Por lo tanto se usa una X como undécimo dígito para representar el 10. Así el ISBN 3-540-96035-X es un código ISBN válido.

  1. ¿Es el ISBN 0-534-91500-0 un código ISBN válido? ¿Y el ISBN 0-534-91700-0 o el ISBN 0-534-19500-0?

  2. ¿Sirve este método para detectar todos los errores en un solo dígito? ¿y todos los errores de transposición?

  3. ¿Cuántos códigos ISBN diferentes hay?

  4. Escriba un programa que permita calcular el dígito verificador para los primeros nueve dígitos de un código ISBN.

  5. Una editorial tiene sedes en Alemania y Estados Unidos. Su prefijo alemán es 3-540. Si su prefijo en Estados Unidos es 0-abc, encuentre abc tal que el resto del código ISBN sea el mismo para un libro impreso en Alemania y los Estados Unidos. Bajo el método de codificación ISBN el primer dígito identifica el idioma; alemán es 3 y e inglés es 0. El siguiente grupo de número identifica a la editorial, y el último grupo identifica el libro específico.