3.6: Ejercicios adicionales: detección de errores

Última actualización
Guardar como PDF

Page ID: 111283

$ \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } $ $ \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} $$\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$ $\newcommand{\id}{\mathrm{id}}$ $ \newcommand{\Span}{\mathrm{span}}$ $ \newcommand{\kernel}{\mathrm{null}\,}$ $ \newcommand{\range}{\mathrm{range}\,}$ $ \newcommand{\RealPart}{\mathrm{Re}}$ $ \newcommand{\ImaginaryPart}{\mathrm{Im}}$ $ \newcommand{\Argument}{\mathrm{Arg}}$ $ \newcommand{\norm}[1]{\| #1 \|}$ $ \newcommand{\inner}[2]{\langle #1, #2 \rangle}$ $ \newcommand{\Span}{\mathrm{span}}$$\newcommand{\AA}{\unicode[.8,0]{x212B}}$

1. Símbolos UPC

Los símbolos del Código Universal de Producto (UPC) se encuentran en la mayoría de los productos en tiendas de abarrotes y minoristas El símbolo UPC es un código de 12 dígitos que identifica al fabricante de un producto y al propio producto (Figura 3.32). Los primeros 11 dígitos contienen información sobre el producto; el duodécimo dígito se utiliza para la detección de errores. Si$d_1 d_2 \cdots d_{12}$ es un número UPC válido, entonces

\[ 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}\text{.} \nonumber \]

Mostrar que el número UPC 0-50000-30042-6, que aparece en la Figura 3.32, es un número UPC válido.
Mostrar que el número 0-50000-30043-6 no es un número UPC válido.
Escribe una fórmula para calcular el dígito del cheque,$d_{12}\text{,}$ en el número UPC.
El esquema de detección de errores UPC puede detectar la mayoría de los errores de transposición; es decir, puede determinar si se han intercambiado dos dígitos. Mostrar que no se detecta el error de transposición 0-05000-30042-6. Encuentra un error de transposición que se detecte. ¿Se puede encontrar una regla general para los tipos de errores de transposición que se pueden detectar?
Escribir un programa que determine si un número UPC es válido o no.

$clipboard_e8c58136ecccf22b7837cb7356010ac61.png$

Figura 3.32: Un código UPC

2.

A menudo es útil usar una notación interna de producto para este tipo de esquema de detección de errores; por lo tanto, usaremos la noción

\[ (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \nonumber \]

para significar

\[ d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}\text{.} \nonumber \]

Supongamos que$(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}$ es un esquema de detección de errores para el número de identificación$k$ -digit$d_1 d_2 \cdots d_k\text{,}$ donde$0 \leq d_i \lt n\text{.}$ Demostrar que todos los errores de un solo dígito se detectan si$\gcd( w_i, n ) = 1$ y solo$1 \leq i \leq k\text{.}$

3.

Dejar$(d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}$ ser un esquema de detección de errores para el número de identificación$k$ -dígito$d_1 d_2 \cdots d_k\text{,}$ donde$0 \leq d_i \lt n\text{.}$ Demostrar que todos los errores de transposición de dos dígitos$d_i$ y se$d_j$ detectan si y sólo si$\gcd( w_i - w_j, n ) = 1$ para$i$ y$j$ entre$1$ y$k\text{.}$

4. Códigos ISBN

Cada libro tiene un código de número de libro estándar internacional (ISBN). Se trata de 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 de verificación satisfactorio

\[ (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 ) \equiv 0 \pmod{11}\text{.}\nonumber \]

Un problema es que$d_{10}$ podría tener que ser un 10 para que el producto interno sea cero; en este caso, se necesitarían 11 dígitos para que este esquema funcione. Por lo tanto, se utiliza el carácter X para el undécimo dígito. Por lo que ISBN 3-540-96035-X es un código ISBN válido.

¿El ISBN 0-534-91500-0 es un código ISBN válido? ¿Qué pasa con el ISBN 0-534-91700-0 y el ISBN 0-534-19500-0?
¿Este método detecta todos los errores de un solo dígito? ¿Qué pasa con todos los errores de transposición?
¿Cuántos códigos ISBN diferentes hay?
Escriba un programa de computadora que calculará el dígito de verificación para los primeros nueve dígitos de un código ISBN.
Una editorial tiene casas en Alemania y Estados Unidos. Su prefijo alemán es 3-540. Si su prefijo de Estados Unidos será 0- abc, encuentra abc tal que el resto del código ISBN será el mismo para un libro impreso en Alemania y en Estados Unidos. Bajo el método de codificación ISBN el primer dígito identifica el idioma; el alemán es 3 y el inglés es 0. El siguiente grupo de números identifica al editor, y el último grupo identifica el libro específico.