Статистика

Участников проекта 105
Опубликовано статей 78
Отчет по карме. Топ 20

Новости блога

1 29.11.2013  Сегодня самым активным участникам newblog'а был выплачен доход с sape.
7 02.11.2012  Ура! Свешилось, нашему сайту дали тИЦ 10. Спасибо всем кто принимает участие в развитии нашего блога.
8 21.08.2012  Интеграция с sape.ru. Теперь каждый автор статей на newblog автоматически зарабатывает на рекламе.
Все новости

Топ 5 категорий

Программирование 46
Операционные системы 9
Базы данных 4
Туризм 2
Заметки 2

Последние 5 заметок (90)

gullyar - Закладки gullyar
gullyar - Ваша первая закладка
osadchaya - Закладки osadchaya
Ira0231188 - Закладки Ira0231188
Ira0231188 - Закладки Ira0231188

Ссылки

www.freedev.asia
пенсию отменят к 2018

Контрольное число, сравнение алгоритмов

06.10.2012 17:42 | Просмотров: 3345 | Доход: 117.11 руб. | Комментариев: 0
[Программирование] 
Рейтинг: 0/0

Контрольное число - это разновидность контрольной суммы, как правило добавляется в качестве последнего разряда к длинным номерам и позволяет провести первичную проверку их корректности. Позволяет сильно снизить вероятность ошибки. Часто используется при машинном считывании штрихкодов с упаковки товара, записи в документы(например ИИН, БИН), для проверки корректности номера пластиковой карты и т.д. В общем область применения очень обширная.

1) Алгоритм на основе целочисленного остатка от деления.

Когда я искал подходящий алгоритм, то первым делом я наткнулся на тот, который используется при формировании ИИН. Он очень простой и подходит для большинства задач. Чтобы вычислить контрольное число, которое указывается 12тым си, складываются произведения каждого разряда и его веса.

digit=(i1*c1+i2*c2+i3*c3+i4*c4+i5*c5+i6*c6+i7*c7+i8*c8+i9*c9+i10*c10+i11*c11) mod 11

где i - значение разряда, а c - вес разряда. На первом этапе вес разряда соответствует позиции цифры(от 1 до 11). Если результат равен 10, то вес каждого элемента сдвигается влево на 2 позиции и контрольное число вычисляется заново. На первый взгляд отличное решение, но алгоритм почти не защищает от парных ошибок.

 2) Алгоритм Луна.

Был разработан сотрудником фирмы IBM Гансом Питером Луном. Алгоритм известен тем, что используется для вычисления контрольной цифры номера пластиковых карт. Позволяет лишь с некоторой степенью достоверности судить об отсутствии ошибок в блоке цифр и не даёт возможности коррекции обнаруженной неточности. Алгоритм, описанный разработчиком следующий:

Цифры проверяемой последовательности нумеруются справа налево.
Цифры, оказавшиеся на нечётных местах, остаются без изменений.
Цифры, стоящие на чётных местах, умножаются на 2.
Если в результате число б> 9, оно заменяется суммой цифр произведения — однозначным числом, т. е. цифрой.
Все полученные в результате преобразования цифры складываются. Если сумма кратна 10, то исходные данные верны.

 

 3) Алгоритм Верхоффа

Самым удобным и эффективным на мой взгляд оказался именно этот алгоритм. Во-первых он позволяет выявить большее число ошибок, нежели аналогичный алгоритм Луна. И его при этом достаточно просто запрограммировать. Поэтому я остановил выбор именно на этом алгоритме.

Результат операции d(j, k) определяется по таблице(обратите внимание что блоки выделенные зеленым не являются коммутативными):

d(j,k) k
j   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

где j — результат предыдущей итерации (0 для первой итерации). А k -  результат ещё одной операции — p(x, y), где y - цифра, x - позиция этой цифры по модулю 8. Результат этой операции также удобно определять по таблице.

p(x,y)
y
x
  0 1 2 3 4 5 6 7 8 9
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


Таким образом алгоритм сводится к следующим действиям:

Взять исходное значение c = 0.
Для каждой цифры исходного числа, начиная с наименее значимой (справа),
вычислить c = d(c, p(i + 1, ni)), где i — порядковый номер цифры, а ni — значение цифры.
Добавить справа к исходному числу результат операции inv(c), определяемый по ещё одной таблице:
j 0 1 2 3 4 5 6 7 8 9
inv(j) 0 4 3 2 1 5 6 7 8 9

 Метод эффективен и если верить википедии, то контрольное число позволяет выявить:

  • Одиночные ошибки (6 вместо 7) — 100 % ошибок;
  • Перестановки соседних цифр (67 вместо 76) — 100 % ошибок;
  • Двойные ошибки (66 вместо 77) — 95,5 % ошибок;
  • Перестановки несоседних цифр (637 вместо 736) — 94,2 % ошибок;
  • Двойные ошибки в несоседних цифрах (636 вместо 737) — 94,2 % ошибок.

Пример:

Для последовательности "1234567" контрольное число будет 9. Заменив одну цифру, например "1234568", контрольное число уже изменится на 0. Таким образом код "12345679" - корректный, а код "12345689" - не корректный.

 На википедии есть готовые реализации на различных языках программирования.


© GM
| Комментировать статью |