Алгоритм Верхуффа () — алгоритм расчёта контрольной цифры для обнаружения ошибок при ручном вводе длинных цифровых последовательностей. Впервые опубликован в 1969 году нидерландским математиком Якобом Верхуффом. Алгоритм позволяет выявить такое же число ошибок, как аналогичный алгоритм Луна, но ошибки, выявляемые только первым, совершаются людьми обычно чаще, чем ошибки, выявляемые только вторым.
Принцип действия Вместо суммирования произведений цифр на весовые коэффициенты Верхуфф предложил использовать групповую операцию, известную как диэдральная группа D5.
d(j, k)kj 012345678900123456789112340678952234017895633401289567440123956785598760432166598710432776598210438876593210499876543210
Результат операции 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)yx 01234567890012345678911576283094258037961423891604352749453126870542865739016279380641577046913258
Алгоритм проверки Взять исходное значение c = 0. Для каждой цифры проверяемого числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i, ni)), где i — порядковый номер цифры, а ni — значение цифры. Если c = 0, контрольная цифра верна.
Алгоритм вычисления Взять исходное значение c = 0. Для каждой цифры исходного числа, начиная с наименее значимой (справа), вычислить c = d(c, p(i + 1, ni)), где i — порядковый номер цифры, а ni — значение цифры. Добавить справа к исходному числу результат операции inv(c), определяемый по ещё одной таблице:
j0123456789inv(j)0432156789
Примечания
Ссылки
Описание алгоритма Верхуффа и некоторых других алгоритмов вычисления контрольной цифры. Замечания к алгоритму Верхуффа. Detailed description of the Verhoeff algorithm
Категория:Теория групп Категория:Алгоритмы Категория:Обнаружение и устранение ошибок