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

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

Принцип действия

Вместо суммирования произведений цифр на весовые коэффициенты Верхуфф предложил использовать групповую операцию, известную как диэдральная группа 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)$ выполняется не для всех $j$ и $k$.

Последовательно выполняя операцию 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

Ссылки

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