Алгоритм Дамма (англ. 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, следовательно передаваемая последовательность цифр действительна.
Данная страница на сайте WikiSort.ru содержит текст со страницы сайта "Википедия".
Если Вы хотите её отредактировать, то можете сделать это на странице редактирования в Википедии.
Если сделанные Вами правки не будут кем-нибудь удалены, то через несколько дней они появятся на сайте WikiSort.ru .