Алгоритм Верховева

Способ обнаружения ошибок в десятичных кодах

Алгоритм Верхуффа ^[1] представляет собой контрольную сумму для обнаружения ошибок, впервые опубликованную голландским математиком Якобусом Верхоффом в 1969 году. ^{[2] [3]} Это был первый алгоритм десятичных контрольных цифр , который обнаруживает все однозначные ошибки и все ошибки транспонирования, включающие две цифры. соседние цифры, ^[4] что в то время считалось невозможным для такого кода.

Метод был независимо открыт Х. Питером Гаммом в 1985 году, на этот раз включая формальное доказательство и расширение на любую базу. ^[5]

Цели

Целью Верхуффа было найти десятичный код — такой, в котором контрольная цифра представляет собой одну десятичную цифру, — который обнаруживал бы все однозначные ошибки и все перестановки соседних цифр. В то время предполагаемые доказательства несуществования ^[6] этих кодов сделали популярными коды с основанием 11, например, в контрольной цифре ISBN .

Его цели также были практическими: он основывал оценку различных кодов на реальных данных голландской почтовой системы, используя систему взвешенных баллов для различных видов ошибок. Анализ разбил ошибки на несколько категорий: во-первых, по количеству ошибочных цифр; для тех, у кого есть ошибка в две цифры, есть транспозиции ( ab → ba ), близнецы ( aa → 'bb'), скачкообразные транспозиции ( abc → cba ), фонетические ( 1a → a0 ) и скачкообразные близнецы ( aba → cbc ). Кроме того, есть пропущенные и добавленные цифры. Хотя частота некоторых из этих ошибок может быть небольшой, некоторые коды могут быть невосприимчивы к ним в дополнение к основной цели обнаружения всех одиночных ошибок и транспозиций.

Фонетические ошибки, в частности, проявили лингвистический эффект, поскольку в голландском языке числа обычно читаются парами; а также, хотя на голландском языке 50 звучит похоже на 15, 80 не звучит как 18.

На примере шестизначных чисел Верховев предложил следующую классификацию ошибок:

Описание

Общая идея алгоритма состоит в том, чтобы представить каждую из цифр (от 0 до 9) как элементы группы диэдра . То есть сопоставить цифры с , манипулировать ими, а затем снова сопоставить их с цифрами. Пусть это отображение будет ${\displaystyle D_{5}}$ ${\displaystyle D_{5}}$ ${\displaystyle m:[0,9]\to D_{5}}$

${\displaystyle m={\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmatrix}}}$

Пусть n-я цифра равна , а количество цифр равно . ${\displaystyle a_{n}}$ ${\displaystyle k}$

Например, учитывая код 248, это 3 и . ${\displaystyle k}$ ${\displaystyle a_{3}=m(8)=r^{3}s}$

Теперь определим перестановку ${\displaystyle f:D_{5}\to D_{5}}$

${\displaystyle f={\begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^{3}s&r^{3}&e&r^{4}s&r^{4}\end{pmatrix}}}$

Например . Другой пример: поскольку ${\displaystyle f(r^{3})=rs}$ ${\displaystyle f^{2}(r^{3})=r^{3}}$ ${\displaystyle f(f(r^{3}))=f(rs)=r^{3}}$

Используя мультипликативную запись для групповой операции , контрольная цифра тогда является просто значением, таким, что ${\displaystyle D_{5}}$ ${\displaystyle c}$

${\displaystyle f(a_{1})\cdot f^{2}(a_{2})\cdot \ldots \cdot f^{k}(a_{k})\cdot f^{k+1}(c)=e}$

${\displaystyle c}$явно задается обратной перестановкой

${\displaystyle c=f^{-1-k}\left(\prod _{n=1}^{k}f^{n}(a_{n})^{-1}\right)}$

Например, контрольная цифра для 248 равна 5. Чтобы проверить это, используйте сопоставление и вставьте в левую часть предыдущего уравнения. ${\displaystyle D_{5}}$

${\displaystyle f(r^{2})\cdot f^{2}(r^{4})\cdot f^{3}(r^{3}s)\cdot f^{4}(s)=e}$

Чтобы быстро оценить эту перестановку, используйте это

${\displaystyle f^{4}(s)=f^{3}(r^{3}s)=f^{2}(r^{4})=f(r^{2})=r^{2}s}$

чтобы получить это

${\displaystyle r^{2}s\cdot r^{2}s\cdot r^{2}s\cdot r^{2}s=e}$

Это то же отражение, которое итеративно умножается. Используйте тот факт, что отражения являются их собственными обратными сторонами. ^[7]

${\displaystyle (r^{2}s\cdot r^{2}s)\cdot (r^{2}s\cdot r^{2}s)=e^{2}=e}$

На практике алгоритм реализуется с использованием простых справочных таблиц без необходимости понимать, как генерировать эти таблицы на основе базовой группы и теории перестановок. Правильнее считать это семейством алгоритмов, поскольку другие варианты тоже работают. Верховев отмечает, что конкретная перестановка, приведенная выше, является особенной, поскольку она обладает свойством обнаруживать 95,3% фонетических ошибок. ^[8]

Сильные стороны алгоритма заключаются в том, что он обнаруживает все ошибки транслитерации и транспозиции, а также большинство ошибок двойника, двойного перехода, транспозиции скачка и фонетических ошибок.

Основной слабостью алгоритма Верхуффа является его сложность. Требуемые расчеты не могут быть легко выражены в виде формулы, например . Справочные таблицы необходимы для облегчения вычислений. Аналогичным кодом является алгоритм Дамма , обладающий схожими качествами. ${\displaystyle {\displaystyle \mathbb {Z} /10\mathbb {Z} }}$

Табличный алгоритм

Алгоритм Верхуффа может быть реализован с использованием трех таблиц: таблицы умножения d , обратной таблицы inv и таблицы перестановок p .

Первая таблица d основана на умножении в группе диэдра D ₅ . ^[7] и представляет собой просто таблицу Кэли группы. Обратите внимание, что эта группа не является коммутативной , то есть для некоторых значений j и k d ( j , k ) ≠ d ( k , j ).

Обратная таблица inv представляет собой мультипликативную обратную цифру, то есть значение, которое удовлетворяет условию d ( j , inv ( j )) = 0.

Таблица перестановок p применяет перестановку к каждой цифре в зависимости от ее положения в числе. На самом деле это одна перестановка (1 5 8 9 4 2 7 0)(3 6), применяемая итеративно; т.е. п ( я + j , п ) = п ( я , п ( j , п )).

Расчет контрольной суммы Верхуффа выполняется следующим образом:

1. Создайте массив n из отдельных цифр числа, взятых справа налево (самая правая цифра — n ₀ и т. д.).
2. Инициализируйте контрольную сумму c равным нулю.
3. Для каждого индекса i массива n, начиная с нуля, замените c на . ${\displaystyle d(c,p(i{\bmod {8}},n_{i}))}$

Исходное число действительно тогда и только тогда, когда . ${\displaystyle c=0}$

Чтобы сгенерировать контрольную цифру, добавьте0 , выполните расчет: правильная контрольная цифра — . ${\displaystyle inv(c)}$

Примеры

Смотрите также

• Алгоритм Луна , ранее (1960) алгоритм контрольной цифры

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

1. Верховев, Дж. (1969). Обнаружение ошибок десятичных кодов (тракт 29) . Математический центр, Амстердам. Бибкод :1971ЗаММ...51..240Н. дои : 10.1002/zamm.19710510323.
2. Киртланд, Джозеф (2001). «5. Теория групп и схема контрольных цифр Верхуффа». Идентификационные номера и схемы контрольных цифр . Математическая ассоциация Америки. п. 153. ИСБН 0-88385-720-0.
3. Саломон, Дэвид (2005). «§2.11 Метод контрольной цифры Верхуффа». Кодирование данных и компьютерных коммуникаций . Спрингер. стр. 56–58. ISBN 0-387-21245-0.
4. Хаунспергер, Дина; Кеннеди, Стивен, ред. (2006). Край Вселенной: празднование десяти лет математических горизонтов. Математическая ассоциация Америки. п. 38. ISBN 978-0-88385-555-3. LCCN  2005937266.
5. Гамм, Х. (январь 1985 г.). «Новый класс методов контрольных цифр для произвольных систем счисления (Корресп.)». Транзакции IEEE по теории информации . 31 (1): 102–105. дои : 10.1109/TIT.1985.1056991.
6. Сиссон, Роджер Л. (май 1958 г.). «Улучшенная проверка десятичной избыточности». Коммуникации АКМ . 1 (5): 10–12. дои : 10.1145/368819.368854 .
7. Галлиан, Джозеф А. (2010). Современная абстрактная алгебра (7-е изд.). Брукс/Коул. п. 111. ИСБН 978-0-547-16509-7. LCCN  2008940386 . Проверено 26 августа 2011 г. Контрольная цифра Верховева.
8. Верховев 1969, с. 95
9. Верховев 1969, с. 83

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

• Подробное описание алгоритма Верхуффа