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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

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

Принцип действия[править | править код]

Вместо суммирования произведений цифр на весовые коэффициенты Верхуфф предложил использовать групповую операцию, известную как диэдральная группа D5[1].

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), где 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, ni)), где i — порядковый номер цифры, а ni — значение цифры.
  3. Если c = 0, контрольная цифра верна.

Алгоритм вычисления[править | править код]

  1. Взять исходное значение c = 0.
  2. Для каждой цифры исходного числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i + 1, ni)), где i — порядковый номер цифры, а ni — значение цифры.
  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. Дмитрий Максимов. Коды, распознающие ошибку // Наука и жизнь. — 2018. — № 1. — С. 90-95.

Ссылки[править | править код]