В обнаружении ошибок , то Даммы алгоритм является контрольной цифрой алгоритма , который обнаруживает все ошибки однозначных и все смежные ошибки транспозиции . Его представил Х. Майкл Дамм в 2004 году. [1]
Сильные и слабые стороны
Сильные стороны
Алгоритм Дамма похож на алгоритм Верхоффа . Он также обнаружит все вхождения двух наиболее часто встречающихся типов ошибок транскрипции , а именно изменение одной единственной цифры и транспонирование двух соседних цифр (включая транспонирование конечной контрольной цифры и предыдущей цифры). [1] [2] Но алгоритм Дамма имеет то преимущество, что он позволяет обходиться без специально сконструированных перестановок и его позиционно-зависимых степеней , присущих схеме Верхоффа . Кроме того, можно обойтись без таблицы инверсий при условии, что все главные диагональные записи в таблице операций равны нулю.
Алгоритм Damm не страдает от превышения числа 10 возможных значений, что приводит к необходимости использования нецифрового символа (как X в схеме 10-значных контрольных цифр ISBN ).
Добавление начальных нулей не влияет на контрольную цифру. [1]
Существуют полностью антисимметричные квазигруппы, которые обнаруживают все фонетические ошибки, связанные с английским языком (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). Таблица, использованная в иллюстративном примере, основана на экземпляре такого типа.
Слабые стороны
Поскольку добавление начальных нулей не влияет на контрольную цифру, коды переменной длины [1] не должны проверяться вместе, поскольку, например, 0, 01, 001 и т. Д. Создают одну и ту же контрольную цифру. Однако все алгоритмы контрольной суммы уязвимы для этого.
Дизайн
Его неотъемлемой частью является квазигруппой из порядка 10 (т.е. имеющие 10 × 10 латинский квадрат , как тело его операционного стола ) со специальной особенностью является слабо полностью анти-симметричны . [3] [4] [i] [ii] [iii] Дамм раскрыл несколько методов создания полностью антисимметричных квазигрупп порядка 10 и привел несколько примеров в своей докторской диссертации. [3] [i] Этим Дамм также опроверг старую гипотезу о том, что полностью антисимметричных квазигрупп порядка 10 не существует. [5]
Квазигруппа ( Q , ∗) называется вполне антисимметричной, если для всех c , x , y ∈ Q имеют место следующие импликации: [4]
- ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
- х * у = у * х ⇒ х = у ,
и он называется слабым полностью антисимметричным, если выполняется только первая импликация. Дамм доказал, что существование вполне антисимметричной квазигруппы порядка n эквивалентно существованию слабой вполне антисимметричной квазигруппы порядка n . Для алгоритма Дамма с проверочным уравнением (... ((0 ∗ x m ) ∗ x m −1 ) ∗ ...) ∗ x 0 = 0 слабая вполне антисимметричная квазигруппа со свойством x ∗ x = 0 необходим. Такую квазигруппу можно построить из любой полностью антисимметричной квазигруппы, переставив столбцы таким образом, чтобы все нули лежали на диагонали. И, с другой стороны, из любой слабой полностью антисимметричной квазигруппы можно построить полностью антисимметричную квазигруппу, переставив столбцы таким образом, чтобы первая строка была в естественном порядке. [3]
Алгоритм
Достоверность последовательности цифр, содержащей контрольную цифру, определяется над квазигруппой. Готовую к использованию таблицу квазигрупп можно взять из диссертации Дамма (стр. 98, 106, 111). [3] Это полезно, если каждая запись по главной диагонали равна 0, [1], поскольку это упрощает вычисление контрольной цифры.
Проверка числа по включенной контрольной цифре
- Установите промежуточную цифру и инициализируйте ее до 0.
- Обработка числа цифра за цифрой: используйте цифру числа как индекс столбца, а промежуточную цифру как индекс строки, возьмите запись в таблице и замените ею промежуточную цифру.
- Номер действителен тогда и только тогда, когда результирующая промежуточная цифра имеет значение 0. [1]
Расчет контрольной цифры
Предпосылка: основные диагональные записи в таблице равны 0.
- Установите промежуточную цифру и инициализируйте ее до 0.
- Обработка числа цифра за цифрой: используйте цифру числа как индекс столбца, а промежуточную цифру как индекс строки, возьмите запись в таблице и замените ею промежуточную цифру.
- Получившаяся промежуточная цифра дает контрольную цифру и будет добавлена в качестве конечной цифры к номеру. [1]
Пример
Будет использована следующая операционная таблица. [1] Его можно получить из полностью антисимметричной квазигруппы x ∗ y в докторской диссертации Дамма, стр. 111 [3] , переставив строки и изменив записи с перестановкой φ = (1 2 9 5 4 8 6 7 3) и определяя x ⋅ y = φ −1 ( φ ( 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 контрольной цифрой.
Рекомендации
- ^ Б с д е е г ч Fenwick, Питер (2014). «Контрольные суммы и контроль ошибок». Введение в представление компьютерных данных . Издательство Bentham Science. С. 191–218 . DOI : 10.2174 / 9781608058822114010013 . ISBN 978-1-60805-883-9.
- ^ Информацию о типах распространенных ошибок и их частоте см. Саломон, Дэвид (2005). Кодирование данных и компьютерных коммуникаций . Springer Science + Business Media, Inc. стр. 36. ISBN 978-0387-21245-6.
- ^ а б в г д Дамм, Х. Майкл (2004). Total anti-simrische Quasigruppen (PDF) (Dr. rer. Nat.) (На немецком языке). Philipps-Universität Marburg. урна: nbn: de: hebis: 04-z2004-05162 .
- ^ а б Дамм, Х. Майкл (2007). «Полностью антисимметрические квазигруппы для всех порядков n ≠ 2,6» . Дискретная математика . 307 (6): 715–729. DOI : 10.1016 / j.disc.2006.05.033 . ISSN 0012-365X .
- ^ Дамм, Х. Майкл (2003). «О существовании тотально антисимметричных квазигрупп порядка 4 k + 2». Вычислительная техника . 70 (4): 349–357. DOI : 10.1007 / s00607-003-0017-3 . ISSN 0010-485X .
- ^ а б Белявская Галина ; Избаш Владимир ; Щербаков Виктор (2003). «Проверьте системы символов над квазигруппами и циклами» (PDF) . Квазигруппы и родственные системы . 10 ( 1 ): 1-28 . ISSN 1561-2848 . См. Страницу 23.
- ^ Чен Цзяннань (2009). «NP-полнота завершения частичных антисимметричных латинских квадратов» (PDF) . Материалы международного семинара по информационной безопасности и приложениям 2009 г. (IWISA 2009) . Издатель Академии. С. 322–324 . ISBN 978-952-5726-06-0. См. Страницу 324.
- ^ Милева А .; Димитрова, В. (2009). «Квазигруппы, построенные из полных отображений группы (Z 2 n ,)» (PDF) . Вклады, разд. Математика. Tech. Наук, MANU / MASA . XXX (1–2): 75–93. ISSN 0351-3246 . См. Страницу 78.
Внешние ссылки
- Проверка и генерация кода Damm на нескольких языках программирования
- Практическое применение в Сингапуре
- Квазигруппы для алгоритма Дамма до порядка 64