Алгоритм Дамма () — алгоритм расчёта контрольной цифры для обнаружения ошибок. Впервые был предложен в 2004 году М. Даммом.
Принцип действия Дамм предложил использовать бинарную операцию, известную как квазигруппа Дамма.
d(j, k)kj 012345678900317598642170921548632420687135931750983426461230459785367420958165869720134789453620178943861720592581436790
Результат операции d(j, k) проще всего определить по таблице, где он располагается на пересечении j-й строки и k-го столбца таблицы. Выбранная Даммом операция не является коммутативной, то есть для неё условие выполняется не для всех и .
Последовательно выполняя операцию d(j, k), где j — результат предыдущей итерации (0 для первой итерации), а k — очередная цифра числа, можно получить алгоритм вычисления контрольной цифры, лучший (в среднем для наиболее распространённых ошибок), чем обычное сложение по модулю 10.
Алгоритм Дамма позволяет обнаруживать две распространённые ошибки при вводе цифр: замену одной цифры на другую и перестановку двух соседних цифр.
Пример
Предположим, что передается последовательность цифр 572.
Вычисление контрольной цифры обрабатываемая цифра → индекс колонки 5 7 2 старая промежуточная цифра → индекс строки097 вход таблицы → новая промежуточная цифра974 Итоговая промежуточная цифра 4. Она является контрольной суммой. Добавляя её к числу, получаем 5724.
Проверка числа по контрольной цифре обрабатываемая цифра → индекс колонки 5 7 2 4 старая промежуточная цифра → индекс строки0974 вход таблицы → новая промежуточная цифра9740 Итоговая промежуточная цифра 0, следовательно передаваемая последовательность цифр действительна.
Примечания
Ссылки
Категория:Теория групп Категория:Алгоритмы