В обнаружении ошибок алгоритм Damm представляет собой контрольную цифру алгоритм, который обнаруживает все однозначные ошибки и все смежные ошибки транспонирования. Его представил Х. Майкл Дамм в 2004 году.
Алгоритм Дамма похож на алгоритм Верхоффа. Он также обнаружит все вхождения двух наиболее часто встречающихся типов ошибок транскрипции, а именно изменение одной отдельной цифры и транспонирование двух соседних цифр (включая транспонирование конечной контрольной цифры и предыдущей цифры). Но алгоритм Дамма имеет то преимущество, что он обходится без специально сконструированных перестановок и его позиционных зависимостей степеней, присущих схеме Верхоффа. Кроме того, можно обойтись без таблицы инверсий при условии, что все основные диагональные записи в таблице операций равны нулю.
Алгоритм Дамма не страдает от превышения числа 10 возможных значений, что приводит к необходимости использования нецифрового символа (как X в 10-значном ISBN контрольная цифра схема).
Добавление начальных нулей не влияет на контрольную цифру.
Существуют полностью антисимметричные квазигруппы, обнаруживающие все фонетические ошибки, связанные с английским языком (13 ↔ 30, 14 ↔ 40,..., 19 ↔ 90). Таблица, использованная в иллюстративном примере, основана на экземпляре такого типа.
Поскольку добавление начальных нулей не влияет на контрольную цифру, коды переменной длины не должны проверяться вместе, поскольку, например, 0, 01, 001 и т. Д. Создают одну и ту же контрольную цифру.. Однако все алгоритмы контрольной суммы уязвимы для этого.
Его существенной частью является квазигруппа порядка 10 (т.е. имеющая 10 × 10 латинский квадрат в качестве тело его операционной таблицы ) с той особенностью, что является слабо полностью антисимметричным. Дамм раскрыл несколько методов создания полностью антисимметричных квазигрупп порядка 10 и привел несколько примеров в своей докторской диссертации. Этим Дамм также опроверг старую гипотезу о том, что вполне антисимметричных квазигрупп порядка 10.
Квазигруппа (Q, ∗) называется полностью антисимметричной, если для всех c, x, y ∈ Q имеют место следующие импликации:
и он называется слабым полностью антисимметричным, если выполняется только первая импликация. Дамм доказал, что существование вполне антисимметричной квазигруппы порядка n эквивалентно существованию слабой вполне антисимметричной квазигруппы порядка n. Для алгоритма Дамма с проверочным уравнением (... ((0 ∗ x m) ∗ x m − 1) ∗...) ∗ x 0 = 0 нужна слабая вполне антисимметрическая квазигруппа со свойством x ∗ x = 0. Такую квазигруппу можно построить из любой полностью антисимметричной квазигруппы, переставив столбцы таким образом, чтобы все нули лежали на диагонали. И, с другой стороны, из любой слабой полностью антисимметричной квазигруппы можно построить полностью антисимметричную квазигруппу, переставив столбцы таким образом, чтобы первая строка была в естественном порядке.
Допустимость последовательности цифр, содержащей контрольную цифру, определяется над квазигруппой. Готовую к использованию таблицу квазигрупп можно взять из диссертации Дамма (стр. 98, 106, 111). Это полезно, если каждая запись по главной диагонали равна 0, поскольку это упрощает расчет контрольной цифры.
Предварительное условие: Основные диагональные записи в таблице - 0.
Будет использоваться следующая таблица операций. Его можно получить из полностью антисимметричной квазигруппы x ∗ y на странице 111 докторской диссертации Дамма, переставив строки и изменив записи с перестановкой φ = (1 2 9 5 4 8 6 7 3) и определив x ⋅ y = φ (φ (x) ∗ y).
⋅ | 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 |
Предположим, мы выбираем число (последовательность цифр) 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, следовательно, число является действительным .
Это пример выше, показывающий детали алгоритма, генерирующего проверку цифру (прерывистая синяя стрелка) и сверив число 572 с контрольной цифрой.
В Викиучебниках есть книга по темам: Реализация алгоритма / Контрольные суммы / Алгоритм Damm |