Алгоритм Верхуффа

Алгоритм Верхоффа

Довольно часто приходится слышать утверждения о том, что невозможно с помощью контрольной цифры определить все возможные ошибки перестановки или одиночные ошибки. Действительно, если для вычисления контрольной цифры использовать сумму произведений отдельных цифр на определенные весовые коэффициенты, то выявить все подобные ошибки математически невозможно. Однако при использовании других алгоритмов вычисления контрольной суммы такая проверка оказалась вполне реальной.

Диэдрическая группа D₅

Вместо суммирования произведений цифр на весовые коэффициенты Верхофф решил использовать операцию над группой, известной как диэдрическая группа D₅.

d(j,k)	k
j		0	1	2	3	4	5	6	7	8	9
	0	0	1	2	3	4	5	6	7	8	9
	1	1	2	3	4	0	6	7	8	9	5
	2	2	3	4	0	1	7	8	9	5	6
	3	3	4	0	1	2	8	9	5	6	7
	4	4	0	1	2	3	9	5	6	7	8
	5	5	9	8	7	6	0	4	3	2	1
	6	6	5	9	8	7	1	0	4	3	2
	7	7	6	5	9	8	2	1	0	4	3
	8	8	7	6	5	9	3	2	1	0	4
	9	9	8	7	6	5	4	3	2	1	0

Результат операции d(i, k) проще всего определить по таблице, где он располагается на пересечении j-й строки и k-того столбца таблицы. Выбранная Верхоффом операция не является коммутативной, то есть для нее не всегда выполняется условие d(i, k) = d(k, j).

Последовательно выполняя операцию d(j, k), где j – результат предыдущей итерации (0 для первой итерации), а k – очередная цифра числа, можно получить алгоритм вычисления контрольной цифры, превосходящий обычное сложение по модулю 10. Действительно, несмотря на то, что оба алгоритма и выявляют одиночные ошибки, приведенный выше способ позволяет, в отличие от сложения по модулю 10, определить 60 из 90 возможных ошибок перестановки соседних цифр.

Однако Верхофф пошел дальше. Он предложил использовать в качестве второго параметра d(j, k) не саму цифру, а результат еще одной операции – p(x, y). Результат этой операции также удобно определять по таблице.

p(x,y)	y
x		0	1	2	3	4	5	6	7	8	9
	0	0	1	2	3	4	5	6	7	8	9
	1	1	5	7	6	2	8	3	0	9	4
	2	5	8	0	3	7	9	6	1	4	2
	3	8	9	1	6	0	4	3	5	2	7
	4	9	4	5	3	1	2	6	8	7	0
	5	4	2	8	6	5	7	3	9	0	1
	6	2	7	9	3	8	0	6	4	1	5
	7	7	0	4	6	9	1	3	2	5	8

Как видим, в таблице только 8 строк. Поэтому значение x берется по модулю 8.

Алгоритм проверки

1. Взять исходное значение c = 0.
2. Для каждой цифры проверяемого числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i, n_i)), где i — порядковый номер цифры, а n_i — значение цифры.
3. Если c = 0, контрольная цифра верна.

Алгоритм вычисления

1. Взять исходное значение c = 0.
2. Для каждой цифры исходного числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i, n_i)), где i — порядковый номер цифры, а n_i — значение цифры.
3. Добавить справа к исходному числу результат операции inv(c), определяемый по еще одной таблице:

j	0	1	2	3	4	5	6	7	8	9
inv(j)	0	4	3	2	1	5	6	7	8	9

Достоинства и недостатки

Процент ошибок, выявляемый при помощи алгоритма Верхоффа:

1. Одиночные ошибки (6 вместо 7) — 100% ошибок;
2. Перестановки соседних цифр (67 вместо 76) — 100% ошибок;
3. Двойные ошибки (66 вместо 77) — 95,5% ошибок;
4. Перестановки несоседних цифр (637 вместо 736) — 94,2% ошибок;
5. Двойные ошибки в несоседних цифрах (636 вместо 737) — 94,2% ошибок.

К недостаткам алгоритма традиционно относили его высокую, по сравнению с другими алгоритмами, сложность. Достаточно сложно произвести все вычисления вручную, особенно для длинных последовательностей. Однако при машинной проверке сложность вычислений не играет решающей роли, что позволяет использовать алгоритм Верхоффа при проверке введенных значений в различных устройствах.

Ссылки

• Detailed description of the Verhoeff algorithm
• Алгоритм Верхоффа — еще один интересный алгоритм вычисления контрольной цифры.
• Алгоритм Верхоффа в викиучебние (исходные коды)