Алгоритм Damm

редактировать

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

Содержание

  • 1 Сильные и слабые стороны
    • 1.1 Сильные стороны
    • 1.2 Слабые стороны
  • 2 Дизайн
  • 3 Алгоритм
    • 3.1 Проверка числа по сравнению с включенная контрольная цифра
    • 3.2 Расчет контрольной цифры
  • 4 Пример
    • 4.1 Расчет контрольной цифры
    • 4.2 Проверка числа по включенной контрольной цифре
    • 4.3 Графическая иллюстрация
  • 5 Ссылки
  • 6 Внешние ссылки

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

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

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

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

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

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

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

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

Дизайн

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

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

  1. (c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y
  2. x ∗ y = y ∗ x ⇒ x = y,

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

Алгоритм

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

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

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

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

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

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

Пример

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

0123456789
00317598642
17092154863
24206871359
31750983426
46123045978
53674209581
65869720134
78945362017
89438617205
92581436790

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

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

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

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

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

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

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

Графическое изображение

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

Контрольная цифра TA квазигруппа dhmd111rr иллюстрация eg5724.svg

Ссылки

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

В Викиучебниках есть книга по темам: Реализация алгоритма / Контрольные суммы / Алгоритм Damm
Последняя правка сделана 2021-05-16 11:16:21
Содержание доступно по лицензии CC BY-SA 3.0 (если не указано иное).
Обратная связь: support@alphapedia.ru
Соглашение
О проекте