Алгоритм Верхоффа - Verhoeff algorithm

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

Цели

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

Его цели также были практическими, и он основывал оценку различных кодов на оперативных данных голландской почтовой системы, используя систему взвешенных баллов для различных видов ошибок. Анализ разбил ошибки на несколько категорий: во-первых, по количеству ошибочных цифр; для тех, у кого две цифры ошибочны, есть транспозиции (ab → ба), двойняшки (аа â † ’'bb'), прыжковые транспозиции (abc → cba), фонетический (1а → а0), и прыгать близнецы (аба → 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

Описание

Верхофф разработал свой алгоритм, используя свойства группа диэдра порядка 10 (некоммутативная система операций над десятью элементами, что соответствует повороту и отражению правильного пятиугольника) в сочетании с перестановкой. Он утверждал, что это было первое практическое использование двугранной группы, и подтвердил принцип, что в конце концов вся прекрасная математика найдет себе применение.^[6] хотя на практике алгоритм будет реализован с использованием простых таблицы поиска без необходимости понимать, как создавать эти таблицы из базовой теории групп и перестановок.

Это более правильно рассматривать как семейство алгоритмов, поскольку возможны и другие перестановки, и это обсуждается в трактовке Верхоффа. Он отмечает, что эта конкретная перестановка,

{displaystyle {egin {pmatrix} 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 1 & 5 & 7 & 6 & 2 & 8 & 3 & 0 & 9 & 4end {pmatrix}} = {egin {pmatrix} 1 & 5 & 8 & 9 & 4 & 2 & 7 & 0end {pmatrix}} {egin {pmatrix}}} {egin {pmatrix}}

является особенным, так как имеет свойство обнаруживать 95,3% фонетических ошибок.^[7]

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

Основная слабость алгоритма Верхоффа - его сложность. Требуемые расчеты нелегко выразить в виде формулы. Таблицы подстановки необходимы для упрощения вычислений. Аналогичный код - это Алгоритм дамма, обладающий схожими качествами.

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

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

${displaystyle d (j, k)}$ ^[8]		k
${displaystyle d (j, k)}$ ^[8]		0	1	2	3	4	5	6	7	8	9
j	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

${displaystyle inv (j)}$

j	0	0
	1	4
	2	3
	3	2
	4	1
	5	5
	6	6
	7	7
	8	8
	9	9

${displaystyle p (pos, num)}$		число
${displaystyle 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₅.^[9] и это просто Стол Кэли группы. Обратите внимание, что эта группа не коммутативный, то есть для некоторых значений j и k, d(j,k) ≠ d(k, j).

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

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

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

Создать массив п из отдельных цифр номера, взятых справа налево (крайняя правая цифра п₀, так далее.).
Инициализировать контрольную сумму c до нуля.
Для каждого индекса я массива п, начиная с нуля, заменить c с d (c, p (i mod 8, n_я)).

Исходный номер действителен тогда и только тогда, когда с = 0.

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

Примеры

Генерировать контрольная цифра для 236:

я	п_я	п(в_я)	c
0	0	0	0
1	6	3	3
2	3	3	1
3	2	1	2

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

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

я	п_я	п(в_я)	c
0	3	3	3
1	6	3	1
2	3	3	4
3	2	1	0

c равен нулю, значит, проверка верна.

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

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

[Verhoeff_1969-1] Verhoeff, J. (1969). Ошибка при обнаружении десятичных кодов (тракт 29). Математический центр, Амстердам. Дои:10.1002 / zamm.19710510323.

[Kirtland_2001-2] Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Математическая ассоциация Америки. п. 153. ISBN 0-88385-720-0. Получено 26 августа, 2011.

[Salomon_2005-3] Саломон, Дэвид (2005). Кодирование для данных и компьютерных коммуникаций. Springer. п. 56. ISBN 0-387-21245-0. Получено 26 августа, 2011.

[Haunsperger_2006-4] Хаунспергер, Дина; Кеннеди, Стивен, ред. (2006). Край Вселенной: празднование десятилетия математических горизонтов. Математическая ассоциация Америки. п. 38. ISBN 978-0-88385-555-3. LCCN 2005937266. Получено 26 августа, 2011.

[Sisson_1958-5] Сиссон, Роджер Л., Улучшенная проверка десятичным избыточным кодом, Связь ACM Vol. 1, вып. 5, May 1958, pp10-12, стр. Дои:10.1145/368819.368854.

[Verhoeff_1975-6] Верхофф, Дж. (1975). Ошибка обнаружения десятичных кодов (тракт 29), вторая печать. Математический центр, Амстердам.

[7] Verhoeff 1969, стр. 95

[8] Verhoeff 1969, стр. 83

[Gallian_2010-9] Галлиан, Джозеф А. (2010). Современная абстрактная алгебра (7-е изд.). Брукс / Коул. п.111. ISBN 978-0-547-16509-7. LCCN 2008940386. Получено 26 августа, 2011. контрольная цифра verhoeff.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]