Алгоритм Дамма - Википедия - Damm algorithm

В обнаружение ошибок, то Алгоритм дамма это контрольная цифра алгоритм это обнаруживает все однозначные ошибки и все смежные ошибки транспонирования. Его представил Х. Майкл Дамм в 2004 году.[1]

Сильные и слабые стороны

Сильные стороны

Алгоритм Дамма аналогичен алгоритму Алгоритм Верхоффа. Он тоже обнаружит все появления двух наиболее часто встречающихся типов ошибки транскрипции, а именно изменение одной отдельной цифры и транспонирование двух соседних цифр (включая транспонирование последней контрольной цифры и предыдущей цифры).[1][2] Но алгоритм Дамма имеет то преимущество, что он обходится без специально сконструированных перестановки и его позиция полномочия присуще Схема Верхёффа. Кроме того, таблица обратное можно обойтись при условии, что все основные диагональные записи в таблице операций равны нулю.

Алгоритм Damm не страдает от превышения числа 10 возможных значений, что приводит к необходимости использования нецифровых символов (в качестве Икс в 10-значный ISBN контрольная цифра схема).

Добавление начальных нулей не влияет на контрольную цифру.[1]

Существуют полностью антисимметричные квазигруппы, которые обнаруживают все фонетические ошибки, связанные с английским языком (13 ↔ 30, 14 ↔ 40, ..., 19 ↔ 90). Таблица, использованная в иллюстративном примере, основана на экземпляре такого типа.

Недостатки

Поскольку добавление начальных нулей не влияет на контрольную цифру,[1] Коды переменной длины не должны проверяться вместе, поскольку, например, 0, 01, 001 и т. д. создают одну и ту же контрольную цифру. Однако все алгоритмы контрольной суммы уязвимы для этого.

Дизайн

Его существенная часть - это квазигруппа из порядок 10 (т.е. имеющий 10 × 10 Латинский квадрат как тело его операционный стол ) с особенностью бытия слабо полностью антисимметричный.[3][4][я][ii][iii] Дамм раскрыл несколько методов создания полностью антисимметричных квазигрупп порядка 10 и привел несколько примеров в своей докторской диссертации.[3][я] Этим Дамм также опроверг старую гипотезу о том, что полностью антисимметричных квазигрупп порядка 10 не существует.[5]

Квазигруппа (Q, ∗) называется полностью антисимметричным, если для всех c, Икс, уQ, имеют место следующие импликации:[4]

  1. (cИкс) ∗ у = (cу) ∗ ИксИкс = у
  2. Иксу = уИксИкс = у,

и он называется слабым полностью антисимметричным, если выполняется только первая импликация. Дамм доказал, что существование вполне антисимметрической квазигруппы порядка п эквивалентно существованию слабой вполне антисимметрической квазигруппы порядка п. Для алгоритма Дамма с проверочным уравнением(...((0 ∗ Иксм) ∗ Иксм−1) ∗ ...) ∗ Икс0 = 0слабая вполне антисимметрическая квазигруппа со свойством ИксИкс = 0необходим. Такую квазигруппу можно построить из любой полностью антисимметричной квазигруппы, переставив столбцы таким образом, чтобы все нули лежали на диагонали. И, с другой стороны, из любой слабой полностью антисимметричной квазигруппы можно построить полностью антисимметричную квазигруппу, переставив столбцы таким образом, чтобы первая строка была в естественном порядке.[3]

Алгоритм

Допустимость последовательности цифр, содержащей контрольную цифру, определяется над квазигруппой. Готовую к использованию таблицу квазигрупп можно взять из диссертации Дамма (стр. 98, 106, 111).[3] Это полезно, если каждая запись по главной диагонали равна 0,[1] потому что это упрощает расчет контрольной цифры.

Проверка числа по включенной контрольной цифре

  1. Установите промежуточную цифру и инициализируйте ее до 0.
  2. Обработка номера цифра за цифрой: используйте цифру номера как индекс столбца, а промежуточную цифру как индекс строки, возьмите запись в таблице и замените ею промежуточную цифру.
  3. Номер действителен тогда и только тогда, когда результирующая промежуточная цифра имеет значение 0.[1]

Расчет контрольной цифры

Предпосылка: Значения главной диагонали таблицы равны 0.

  1. Установите промежуточную цифру и инициализируйте ее до 0.
  2. Обработка числа цифра за цифрой: используйте цифру числа как индекс столбца, а промежуточную цифру как индекс строки, возьмите запись в таблице и замените ею промежуточную цифру.
  3. Получившаяся промежуточная цифра представляет собой контрольную цифру и будет добавлена ​​в качестве конечной цифры к номеру.[1]

Пример

Будет использована следующая операционная таблица.[1] Его можно получить из полностью антисимметричной квазигруппы Иксу в докторской диссертации Дамма стр. 111[3] переставив строки и изменив записи с перестановкой φ = (1 2 9 5 4 8 6 7 3) и определение Иксу = φ−1(φ(Икс) ∗ у).

0123456789
00317598642
17092154863
24206871359
31750983426
46123045978
53674209581
65869720134
78945362017
89438617205
92581436790

Допустим, мы выбираем число (последовательность цифр) 572.

Расчет контрольной цифры

цифра для обработки → индекс столбца572
Старый промежуточная цифра → индекс строки097
запись в таблице → новый промежуточная цифра974

Результирующая промежуточная цифра 4. Это расчетная контрольная цифра. Добавляем его к числу и получаем 5724.

Проверка числа по включенной контрольной цифре

цифра для обработки → индекс столбца5724
Старый промежуточная цифра → индекс строки0974
запись в таблице → новый промежуточная цифра9740

Результирующая промежуточная цифра 0, следовательно, число действительный.

Графическая иллюстрация

Это пример выше, показывающий детали алгоритма, генерирующего контрольную цифру (пунктирная синяя стрелка) и проверки числа. 572 с контрольной цифрой.

Контрольная цифра TA quasigroup dhmd111rr illustration eg5724.svg

Рекомендации

  1. ^ а б c d е ж грамм час Фенвик, Питер (2014). «Контрольные суммы и контроль ошибок». Введение в представление компьютерных данных. Издательство Bentham Science. стр.191–218. Дои:10.2174/9781608058822114010013. ISBN  978-1-60805-883-9.
  2. ^ Типы распространенных ошибок и их частота см. Саломон, Дэвид (2005). Кодирование для данных и компьютерных коммуникаций. Springer Science + Business Media, Inc. стр. 36. ISBN  978-0387-21245-6.
  3. ^ а б c d е Дамм, Х. Майкл (2004). Полная антисимметричная квазигруппа (PDF) (Dr. rer. Nat.) (На немецком языке). Philipps-Universität Marburg. урна: nbn: de: hebis: 04-z2004-05162.
  4. ^ а б Дамм, Х. Майкл (2007). «Абсолютно антисимметричные квазигруппы для всех порядков. п≠2,6". Дискретная математика. 307 (6): 715–729. Дои:10.1016 / j.disc.2006.05.033. ISSN  0012-365X.
  5. ^ Дамм, Х. Майкл (2003). «О существовании тотально антисимметричных квазигрупп порядка 4».k + 2". Вычисление. 70 (4): 349–357. Дои:10.1007 / s00607-003-0017-3. ISSN  0010-485X.

внешняя ссылка