Алгоритм Дамма

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

Алгоритм Дамма (англ. Damm algorithm) — алгоритм расчёта контрольной цифры для обнаружения ошибок. Впервые был предложен в 2004 году М. Даммом.

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

Дамм предложил использовать групповую операцию, известную как квазигруппа Дамма[1].

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

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

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

Алгоритм Дамма позволяет обнаруживать две распространённые ошибки при вводе цифр: замену одной цифры на другую и перестановку двух соседних цифр.

Пример[править | править код]

Предположим, что передается последовательность цифр 572.

Вычисление контрольной цифры[править | править код]

обрабатываемая цифра → индекс колонки 5 7 2
старая промежуточная цифра → индекс строки 0 9 7
вход таблицы → новая промежуточная цифра 9 7 4

Итоговая промежуточная цифра 4. Она является контрольной суммой. Добавляя её к числу, получаем 5724.

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

обрабатываемая цифра → индекс колонки 5 7 2 4
старая промежуточная цифра → индекс строки 0 9 7 4
вход таблицы → новая промежуточная цифра 9 7 4 0

Итоговая промежуточная цифра 0, следовательно передаваемая последовательность цифр действительна.

Примечания[править | править код]

  1. Дмитрий Максимов. Коды, распознающие ошибку // Наука и жизнь. — 2018. — № 1. — С. 90-95.

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