Question

Does the check digit of a UPC code detect all single errors? Prove your answer or find a counterexample.

Short answer

Proven the check digit of a UPC code detects all single errors.

Step-by-step solution

Step 1

For aUPC code ${\mathit{x}}_{\mathbf{1}}{\mathit{x}}_{\mathbf{2}}\mathbf{\dots }{\mathit{x}}_{\mathbf{11}}{\mathit{x}}_{\mathbf{12}}$the following congruence holds:

$\mathbf{3}{\mathit{x}}_{\mathbf{1}}\mathbf{+}{\mathit{x}}_{\mathbf{2}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{3}}\mathbf{+}{\mathit{x}}_{\mathbf{4}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{5}}\mathbf{+}{\mathit{x}}_{\mathbf{6}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{7}}\mathbf{+}{\mathit{x}}_{\mathbf{8}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{9}}\mathbf{+}{\mathit{x}}_{\mathbf{10}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{11}}\mathbf{+}{\mathit{x}}_{\mathbf{12}}^{\mathbf{\circ }}\mathbf{0}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$

Digit ${\mathit{x}}_{\mathbf{12}}$is the check digit.

Step 2

To proof: the check digit of a UPC code detects all single errors,

PROOF

We assume that a single error implies that the value of a single digit changes.

When exactly one of ${\mathbf{x}}_{\mathbf{2}}\mathbf{,}{\mathbf{x}}_{\mathbf{4}}\mathbf{,}{\mathbf{x}}_{\mathbf{6}}\mathbf{,}{\mathbf{x}}_{\mathbf{8}}\mathbf{,}{\mathbf{x}}_{\mathbf{10}}\mathbf{,}{\mathbf{\text{orx}}}_{\mathbf{12}}$changes in its values (while the other all remain the same), then this digit will make a change of $\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{8}\mathbf{,}\mathbf{\text{or}}\mathbf{9}$. However, this then implies that $\mathbf{3}{\mathit{x}}_{\mathbf{1}}\mathbf{+}{\mathit{x}}_{\mathbf{2}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{3}}\mathbf{+}{\mathit{x}}_{\mathbf{4}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{5}}\mathbf{+}{\mathit{x}}_{\mathbf{6}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{7}}\mathbf{+}{\mathit{x}}_{\mathbf{8}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{9}}\mathbf{+}{\mathit{x}}_{\mathbf{10}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{11}}\mathbf{+}{{\mathit{x}}_{\mathbf{12}}}^{\mathbf{\circ }}\mathit{i}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$for some $\mathit{i}\mathbf{=}\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{9}$and thus the check digit will then detect the error (as the congruence$\mathbf{3}{\mathit{x}}_{\mathbf{1}}\mathbf{+}{\mathit{x}}_{\mathbf{2}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{3}}\mathbf{+}{\mathit{x}}_{\mathbf{4}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{5}}\mathbf{+}{\mathit{x}}_{\mathbf{6}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{7}}\mathbf{+}{\mathit{x}}_{\mathbf{8}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{9}}\mathbf{+}{\mathit{x}}_{\mathbf{10}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{11}}\mathbf{+}{\mathit{x}}_{\mathbf{12}}^{\mathbf{\circ }}\mathbf{0}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$then no longer holds).

When exactly one of ${\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{1}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{3}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{5}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{7}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{9}\mathbf{\right\}}\mathbf{,}\mathbf{\text{or}}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{11}\mathbf{\right\}}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{1}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{3}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{5}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{7}\mathbf{\right\}}\mathbf{,}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{9}\mathbf{\right\}}\mathbf{,}\mathbf{\text{or}}{\mathit{x}}_{\mathbf{-}}\mathbf{\left\{}\mathbf{11}\mathbf{\right\}}$changes in its values (while the other all remain the same), then this digit will make a change of $\mathbf{1}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{3}\mathbf{,}\mathbf{\dots }\mathbf{,}\mathbf{8}\mathbf{,}\mathbf{\text{or}}\mathbf{9}$, and thus $\mathbf{}\mathbf{3}\mathit{x}$will then change by $\mathbf{3}\mathbf{,}\mathbf{6}\mathbf{,}\mathbf{9}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{5}\mathbf{,}\mathbf{8}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{\text{or}}\mathbf{7}$. Taking modulo 10 of these 9 changes in $\mathbf{3}\mathit{x}$, we obtain $\mathbf{3}\mathbf{,}\mathbf{6}\mathbf{,}\mathbf{9}\mathbf{,}\mathbf{2}\mathbf{,}\mathbf{5}\mathbf{,}\mathbf{8}\mathbf{,}\mathbf{1}\mathbf{,}\mathbf{4}\mathbf{,}\mathbf{\text{or}}\mathbf{7}$. Since the 9 possible changes all result in a distinct change modulo 10 different from 0, the check digit will detect the error (as the congruence $\mathbf{3}{\mathit{x}}_{\mathbf{1}}\mathbf{+}{\mathit{x}}_{\mathbf{2}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{3}}\mathbf{+}{\mathit{x}}_{\mathbf{4}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{5}}\mathbf{+}{\mathit{x}}_{\mathbf{6}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{7}}\mathbf{+}{\mathit{x}}_{\mathbf{8}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{9}}\mathbf{+}{\mathit{x}}_{\mathbf{10}}\mathbf{+}\mathbf{3}{\mathit{x}}_{\mathbf{11}}\mathbf{+}{\mathit{x}}_{\mathbf{12}}^{\mathbf{0}}\mathbf{0}\mathbf{(}\mathbf{mod}\mathbf{10}\mathbf{)}$then no longer holds).

Thus we can then conclude that the check digit of a UPC code detects all single errors.