Sauter au contenu
Logo image

Algèbre abstraite Théorie et applications

Thomas W. Judson

Exercices 3.6 Exercices supplémentaires : Détection d’erreurs

1. Codes UPC.

Les symboles du code universel des produits (UPC) se trouvent sur la plupart des produits dans les épiceries et les commerces de détail. Le symbole UPC est un code à 12 chiffres identifiant le fabricant d’un produit et le produit lui-même (Figure 3.6.1). Les 11 premiers chiffres contiennent des informations sur le produit ; le douzième chiffre est utilisé pour la détection d’erreurs. Si \(d_1 d_2 \cdots d_{12}\) est un numéro UPC valide, alors
\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}\text{.} \end{equation*}
  1. Montrez que le numéro UPC 0-50000-30042-6, qui apparaît dans la Figure 3.6.1, est un numéro UPC valide.
    🔗
    🔗
  2. Montrez que le numéro 0-50000-30043-6 n’est pas un numéro UPC valide.
    🔗
    🔗
  3. Écrivez une formule pour calculer le chiffre de contrôle, \(d_{12}\text{,}\) dans un numéro UPC.
    🔗
    🔗
  4. Le système de détection d’erreurs UPC peut détecter la plupart des erreurs de transposition ; c’est-à-dire qu’il peut déterminer si deux chiffres ont été interchangés. Montrez que l’erreur de transposition 0-05000-30042-6 n’est pas détectée. Trouvez une erreur de transposition qui est détectée. Pouvez-vous trouver une règle générale pour les types d’erreurs de transposition qui peuvent être détectées ?
    🔗
    🔗
  5. Écrivez un programme qui déterminera si un numéro UPC est valide ou non.
    🔗
    🔗
🔗
Les lignes verticales d’un code-barres UPC pour 0-05000-30042-6
Figure 3.6.1. Un code UPC
🔗
🔗

2.

Il est souvent utile d’utiliser une notation de produit scalaire pour ce type de système de détection d’erreurs ; nous utiliserons donc la notation
\begin{equation*} (d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n } \end{equation*}
pour signifier
\begin{equation*} d_1 w_1 + d_2 w_2 + \cdots + d_k w_k \equiv 0 \pmod{ n}\text{.} \end{equation*}
🔗
Supposons que \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) soit un système de détection d’erreurs pour le numéro d’identification à \(k\) chiffres \(d_1 d_2 \cdots d_k\text{,}\) où \(0 \leq d_i \lt n\text{.}\) Montrez que toutes les erreurs sur un seul chiffre sont détectées si et seulement si \(\gcd( w_i, n ) = 1\) pour \(1 \leq i \leq k\text{.}\)
🔗
🔗

3.

Soit \((d_1, d_2, \ldots, d_k ) \cdot (w_1, w_2, \ldots, w_k ) \equiv 0 \pmod{ n}\) un système de détection d’erreurs pour le numéro d’identification à \(k\) chiffres \(d_1 d_2 \cdots d_k\text{,}\) où \(0 \leq d_i \lt n\text{.}\) Montrez que toutes les erreurs de transposition de deux chiffres \(d_i\) et \(d_j\) sont détectées si et seulement si \(\gcd( w_i - w_j, n ) = 1\) pour \(i\) et \(j\) entre \(1\) et \(k\text{.}\)
🔗
🔗

4. Codes ISBN.

Chaque livre possède un code ISBN (numéro international normalisé du livre). C’est un code à 10 chiffres indiquant l’éditeur et le titre du livre. Le dixième chiffre est un chiffre de contrôle satisfaisant
\begin{equation*} (d_1, d_2, \ldots, d_{10} ) \cdot (10, 9, \ldots, 1 ) \equiv 0 \pmod{11}\text{.} \end{equation*}
Un problème est que \(d_{10}\) pourrait devoir valoir 10 pour que le produit scalaire soit nul ; dans ce cas, 11 chiffres seraient nécessaires pour que ce système fonctionne. C’est pourquoi le caractère X est utilisé pour le onzième chiffre. Ainsi, l’ISBN 3-540-96035-X est un code ISBN valide.
  1. L’ISBN 0-534-91500-0 est-il un code ISBN valide ? Et l’ISBN 0-534-91700-0 et l’ISBN 0-534-19500-0 ?
    🔗
    🔗
  2. Cette méthode détecte-t-elle toutes les erreurs sur un seul chiffre ? Et toutes les erreurs de transposition ?
    🔗
    🔗
  3. Combien de codes ISBN différents existe-t-il ?
    🔗
    🔗
  4. Écrivez un programme informatique qui calculera le chiffre de contrôle pour les neuf premiers chiffres d’un code ISBN.
    🔗
    🔗
  5. Un éditeur a des maisons en Allemagne et aux États-Unis. Son préfixe allemand est 3-540. Si son préfixe américain sera 0-abc, trouvez abc de sorte que le reste du code ISBN soit le même pour un livre imprimé en Allemagne et aux États-Unis. Dans le système de codage ISBN, le premier chiffre identifie la langue ; l’allemand est 3 et l’anglais est 0. Le groupe de chiffres suivant identifie l’éditeur, et le dernier groupe identifie le livre spécifique.
    🔗
    🔗
🔗
🔗
🔗
PrécédentTopSuivant