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

Алгоритм Верховева — контрольная сумма для обнаружения ошибок, впервые опубликованная голландским математиком Якобусом Верхуффом в 1969 году. Это был первый алгоритм десятичных контрольных цифр , который обнаруживает все однозначные ошибки и все ошибки транспонирования, связанные с двумя соседними цифрами. что в то время считалось невозможным при наличии такого кода.

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

Цели

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

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

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

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

Цифры с ошибкой	Классификация	Считать	Частота
1	Транскрипция	9,574	79.05%
2	Транспозиции	1,237	10.21%
	Двойняшки	67	0.55%
	Фонетический	59	0.49%
	Прочие смежные	232	1.92%
	Прыжковые транспозиции	99	0.82%
	Прыжок близнецов	35	0.29%
	Другие ошибки прыжка	43	0.36%
	Другой	98	0.81%
3		169	1.40%
4		118	0.97%
5		219	1.81%
6		162	1.34%
Общий		12,112

Описание

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

$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-я цифра будет $a_{n}$ и пусть количество цифр будет $k$.

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

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

$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}}$

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⁠ $d(j,k)$⁠		к
		0	1	2	3	4	5	6	7	8	9
дж	0	0	1	2	3	4	5	6	7	8	9
	1	1	2	3	4	0	6	7	8	9	5
	2	2	3	4	0	1	7	8	9	5	6
	3	3	4	0	1	2	8	9	5	6	7
	4	4	0	1	2	3	9	5	6	7	8
	5	5	9	8	7	6	0	4	3	2	1
	6	6	5	9	8	7	1	0	4	3	2
	7	7	6	5	9	8	2	1	0	4	3
	8	8	7	6	5	9	3	2	1	0	4
	9	9	8	7	6	5	4	3	2	1	0

дж	⁠ $inv(j)$⁠
0	0
1	4
2	3
3	2
4	1
5	5
6	6
7	7
8	8
9	9

⁠ $p(pos,num)$⁠		в
		0	1	2	3	4	5	6	7	8	9
поз (мод 8)	0	0	1	2	3	4	5	6	7	8	9
	1	1	5	7	6	2	8	3	0	9	4
	2	5	8	0	3	7	9	6	1	4	2
	3	8	9	1	6	0	4	3	5	2	7
	4	9	4	5	3	1	2	6	8	7	0
	5	4	2	8	6	5	7	3	9	0	1
	6	2	7	9	3	8	0	6	4	1	5
	7	7	0	4	6	9	1	3	2	5	8

Первая таблица d основана на умножении в группе диэдра D ₅ . и представляет собой просто таблицу Кэли группы. Обратите внимание, что эта группа не является коммутативной то есть для некоторых значений 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 на ⁠ $d(c,p(i{\bmod {8}},n_{i}))$⁠ .

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

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

Примеры

Создайте контрольную цифру для 236 :

я	н я	п ( я, п я )	с
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

c равен 2, поэтому контрольная цифра — inv (2), то есть 3.

Подтвердите контрольную цифру 2363 :

я	н я	п ( я, п я )	с
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c равен нулю, поэтому проверка верна.

См. также

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

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

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