stringtranslate.com

Алгоритм Дамма

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

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

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

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

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

Добавление ведущих нулей не влияет на контрольную цифру (слабость кодов переменной длины). [1]

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

Недостатки

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

Дизайн

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

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

  1. ( c * Икс ) * y знак равно ( c * y ) * Икс ⇒ Икс знак равно y
  2. Икс * у знак равно у * Икс ⇒ Икс знак равно у ,

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

Алгоритм

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

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

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

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

Предварительное условие: основные диагональные записи таблицы равны 0 .

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

Пример

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

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

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

Полученная промежуточная цифра — 4 . Это вычисленная контрольная цифра. Добавляем его к числу и получаем 5724 .

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

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

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

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

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

  1. ^ abcdefgh Фенвик, Питер (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. ^ abcde Damm, Х. Майкл (2004). Total antisymmetrische Quasigruppen (PDF) (Dr. rer. nat.) (на немецком языке). Филиппс-Университет Марбурга. urn:nbn:de:hebis:04-z2004-05162.
  4. ^ Аб Дамм, Х. Майкл (2007). «Тотально антисимметричные квазигруппы для всех порядков n ≠ 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. S2CID  31659430.
  1. ^ аб Белявская, Галина; Избаш, Владимир; Щербаков, Виктор (2003). «Проверьте системы символов по квазигруппам и циклам» (PDF) . Квазигруппы и родственные системы . 10 (1): 1–28. ISSN  1561-2848.См. стр. 23.
  2. ^ Чэнь Цзяннан (2009). «NP-полнота завершения частичных антисимметричных латинских квадратов» (PDF) . Материалы Международного семинара по информационной безопасности и приложениям 2009 г. (IWISA 2009). Издательство Академии. стр. 322–324. ISBN 978-952-5726-06-0.См. стр. 324.
  3. ^ Милева, А.; Димитрова, В. (2009). «Квазигруппы, построенные из полных отображений группы (Z2n, ⊕)» (PDF) . Взносы, разд. Математика. Тех. наук, MANU/MASA . ХХХ (1–2): 75–93. ISSN  0351-3246.См. стр. 78.

Внешние ссылки

В Wikibooks есть книга на тему: Реализация алгоритма/Контрольные суммы/Алгоритм Дамма.