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

Алгоритм Верхоффа (Verhoeff) — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 г. голландским математиком Якобом Верхоффом. Алгоритм позволяет выявить большее число ошибок, нежели аналогичный алгоритм Луна.

Диэдрическая группа 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(j, k) проще всего определить по таблице, где он располагается на пересечении j-й строки и k-того столбца таблицы. Выбранная Верхоффом операция не является коммутативной, то есть для неё не всегда выполняется условие d(j, k) = d(k, j).

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

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

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

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

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 + 1, 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

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

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

Описание ошибки	Алгоритм Верхоффа	Алгоритм Луна	Алгоримт SHA1 (равномерный)	ИНН остаток от деления на 11	ОПКО двойной остаток от деления на 11	EAN13
Одиночные ошибки (6 вместо 7)	100%	100%	94.5%	98.1%	100%	100%
Перестановки соседних цифр (67 вместо 76)	100%	97.7%	94.5%	98.1%	100%	88.8%
Двойные ошибки (66 вместо 77)	95.5%	93.3%	94.5%	98.1%	81.8%	88.8%
Перестановки четных\нечетных позиций цифр (637 вместо 736)	94.2%	0%	94.5%	98.1%	100%	0%
Перестановки любых позиций цифр (6327 вместо 7326)	94.9%	58.6%	94.5%	98.1%	100%	53.3%
Двойные ошибки в несоседних цифрах (636 вместо 737)	94.2%	100%	94.5%	98.1%	100%	88.8%
Вставка любой цифры - (67 вместо 6)	90%	94%	94.5%	90.6%	93.0%	91.4%
Дублирование любой цифры (66 вместо 6)	90%	93.8%	94.5%	89.2%	93.5%	90%

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

Ссылки

Имеется викиучебник по теме
«Алгоритм Верхоффа»

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

Для улучшения этой статьи желательно?: Викифицировать статью. Исправить статью согласно стилистическим правилам Википедии. Переработать оформление в соответствии с правилами написания статей.