Контрольная цифра

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

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

Дизайн

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

• ошибки букв/цифр, например l → 1 или O → 0
• однозначные ошибки, например 1 → 2
• ошибки транспонирования, например 12 → 21
• двойные ошибки, например 11 → 22
• ошибки транспозиции перехода, например 132 → 231
• перейти к ошибкам-двойникам, например 131 → 232
• фонетические ошибки, например 60 → 16 («от шестидесяти» до «шестнадцати»)

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

Желательная особенность заключается в том, что заполнение нулями слева не должно изменять контрольную цифру. Это позволяет использовать числа переменной длины и изменять длину.Если к исходному номеру добавлена ​​одна контрольная цифра, система не всегда фиксирует несколько ошибок, например две ошибки замены (12 → 34), хотя, как правило, двойные ошибки обнаруживаются в 90% случаев (оба изменения будут обнаружены). необходимо изменить выпуск путем компенсации сумм).

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

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

Чтобы проиллюстрировать это, например, если веса четырехзначного числа были 5, 3, 2, 7, а число, которое нужно закодировать, было 4871, то нужно было бы взять 5×4 + 3×8 + 2×7 + 7×1. = 65, т. е. 65 по модулю 10, а контрольная цифра будет 5, что дает 48715.

Широко используются системы с весами 1, 3, 7 или 9, при этом веса соседних чисел различны: например, веса 31 31 в кодах UPC , веса 13 13 в номерах EAN (алгоритм GS1), 371 банковских маршрутов США 371 371 вес, используемый в транзитных номерах . Эта система обнаруживает все однозначные ошибки и около 90% ошибок транспозиции. 1, 3, 7 и 9 используются, потому что они взаимно просты с 10, поэтому изменение любой цифры меняет контрольную цифру; использование коэффициента, делящегося на 2 или 5, приведет к потере информации (поскольку 5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0 по модулю 10) и, следовательно, не позволит обнаружить некоторые однозначные ошибки. Использование разных весов соседних чисел означает, что большинство транспозиций меняют контрольную цифру; однако, поскольку все веса различаются на четное число, это не учитывает перестановки двух цифр, которые отличаются на 5 (0 и 5, 1 и 6, 2 и 7, 3 и 8, 4 и 9), поскольку 2 и 5 умножьте, чтобы получить 10.

Вместо этого в коде ISBN-10 используется модуль 11, который является простым, и все числовые позиции имеют разные веса 1, 2, ... 10. Таким образом, эта система обнаруживает все однозначные ошибки замены и транспонирования (включая скачкообразные транспозиции), но ценой того, что контрольная цифра может быть равна 10, обозначенной буквой «X». (Альтернатива состоит в том, чтобы просто избегать использования серийных номеров, которые приводят к контрольной цифре «X».) Вместо этого ISBN-13 использует алгоритм GS1, используемый в номерах EAN.

Более сложные алгоритмы включают алгоритм Луна (1954), который улавливает 98% однозначных ошибок транспонирования (он не обнаруживает 90 ↔ 09), и еще более сложный алгоритм Верхуффа (1969), который улавливает все однозначные замены и транспонирования. ошибки и многие (но не все) более сложные ошибки. Аналогичным является другой абстрактной алгебре метод, основанный на , алгоритм Дамма (2004), который также обнаруживает все однозначные ошибки и все соседние ошибки транспонирования. Эти три метода используют одну контрольную цифру и, следовательно, не смогут охватить около 10 %. более сложных ошибок. Чтобы снизить частоту отказов, необходимо использовать более одной контрольной цифры (например, проверка по модулю 97, упомянутая ниже, в которой используются две контрольные цифры — алгоритм см. в разделе « Номер международного банковского счета ») и/или использовать более широкий диапазон символов в контрольной цифре, например буквы и цифры.

Примеры

GTIN, номера, администрируемые

Последняя цифра универсального кода продукта , международного номера товара , глобального номера местоположения или глобального номера предмета торговли — это контрольная цифра, вычисляемая следующим образом:

1. Сложите цифры в нечетных позициях слева (первую, третью, пятую и т. д., не считая контрольной цифры) вместе и умножьте на три.
2. Добавьте к результату цифры (до, но не включая контрольную цифру) в четных позициях (вторая, четвертая, шестая и т. д.).
3. Возьмите остаток результата, разделенный на 10 (т.е. операция по модулю 10). Если остаток равен 0, используйте 0 в качестве контрольной цифры, а если не 0, вычтите остаток из 10, чтобы получить контрольную цифру.

Калькулятор контрольных цифр GS1 и подробная документация доступны на веб-сайте GS1. Другая официальная страница калькулятора показывает, что механизм GTIN-13 тот же, что и для глобального номера местоположения /GLN.

Например, штрих-код UPC-A для коробки салфеток — «036000241457». Последняя цифра является контрольной цифрой «7», и если остальные цифры верны, то вычисление контрольной цифры должно дать 7.

1. Сложите цифры нечетного числа: 0+6+0+2+1+5 = 14.
2. Умножьте результат на 3: 14×3 = 42.
3. Сложите четные цифры: 3+0+0+4+4 = 11.
4. Сложите два результата вместе: 42 + 11 = 53.
5. Чтобы вычислить контрольную цифру, возьмите остаток от (53/10), который также известен как (53 по модулю 10), и если не 0, вычтите из 10. Следовательно, значение контрольной цифры равно 7. т.е. (53/10 ) = 5 остаток 3; 10 – 3 = 7.

Другой пример: вычислить контрольную цифру для следующего продукта питания «01010101010 x ».

1. Сложите цифры нечетного числа: 0+0+0+0+0+0 = 0.
2. Умножьте результат на 3: 0 х 3 = 0.
3. Сложите четные цифры: 1+1+1+1+1=5.
4. Сложите два результата вместе: 0 + 5 = 5.
5. Чтобы вычислить контрольную цифру, возьмите остаток от (5/10), который также известен как (5 по модулю 10), и если не 0, вычтите из 10: т.е. (5/10) = 0 остаток 5; (10 - 5) = 5. Следовательно, значение контрольной цифры x равно 5.

ISBN 10

Дополнительная информация: Международный стандартный номер книги § Контрольные цифры ISBN-10.

Последний символ десятизначного международного стандартного номера книги — это контрольная цифра, вычисляемая таким образом, что умножение каждой цифры на ее позицию в номере (считая справа) и взятие суммы этих произведений по модулю 11 равно 0. Самая дальняя цифра справа (которая умножается на 1) находится контрольная цифра, выбранная для того, чтобы сумма была правильной. Возможно, ему потребуется значение 10, которое обозначается буквой X. Например, возьмем ISBN   0-201-53082-1 : Сумма произведений равна 0×10 + 2×9 + 0×8 + 1×7 + 5×6 + 3×5 + 0×4 + 8×3 + 2×2 + 1×1 = 99 ≡ 0 (по модулю 11). Таким образом, ISBN действителен. Позиции также можно считать слева, и в этом случае контрольная цифра умножается на 10 для проверки достоверности: 0×1 + 2×2 + 0×3 + 1×4 + 5×5 + 3×6 + 0×7. + 8×8 + 2×9 + 1×10 = 143 ≡ 0 (по модулю 11).

ISBN 13

Дополнительная информация: Международный стандартный номер книги § Расчет контрольной цифры ISBN-13.

ISBN 13 (используется с января 2007 г.) равен коду EAN-13, который находится под штрих-кодом книги. Его контрольная цифра генерируется так же, как и UPC.

НКДА

Алгоритм контрольных цифр NOID (NCDA), используется с 2004 года, предназначен для применения в постоянных идентификаторах и работает со строками букв и цифр переменной длины, называемыми расширенными цифрами. Он широко используется со схемой идентификатора ARK и в некоторой степени используется с такими схемами, как Handle System и DOI . Расширенная цифра ограничена бета-цифровыми символами, которые представляют собой буквенно-цифровые символы без гласных и букву «l» (элль). Это ограничение помогает при создании непрозрачных строк, которые вряд ли случайно образуют слова и не будут содержать одновременно O и 0 или l и 1. Имея простое основание системы счисления R = 29, бета-числовой репертуар позволяет алгоритму гарантировать обнаружение одиночных чисел. ошибки символов и транспонирования для строк длиной менее R=29 символов (более этого обеспечивает немного более слабая проверка). Алгоритм распространяется на любой репертуар символов с простым основанием R и строками длиной менее R символов.

Другие примеры контрольных цифр

Международный

• Международный номер SEDOL.
• Последняя цифра кода ISSN или номера IMO .
• Международный идентификационный номер ценной бумаги (ISIN).
• Группа управления объектами, Фиг.1 . стандартная последняя цифра
• международного регистрационного номера CAS . Последняя цифра
• Контрольные цифры по модулю 10 в номерах счетов кредитных карт , рассчитанные по алгоритму Луна .
  • Также используется в норвежских номерах KID (идентификационный номер клиента), используемых в банковских гиросах (кредитовых переводах),
  • Используется в IMEI мобильных телефонов.
• Последняя контрольная цифра в сериализации EAN/UPC глобального торгового идентификационного номера ( GTIN ). Это относится к GTIN-8, GTIN-12, GTIN-13 и GTIN-14.
• Последняя цифра номера DUNS (хотя это планируется изменить, например, последняя цифра будет выбираться свободно в новых распределениях, а не быть контрольной цифрой).
• Третья и четвертая цифры международного номера банковского счета (проверка по модулю 97).
• Последняя цифра международного стандартного текстового кода .
• Последний символ, закодированный на карте с магнитной полосой, представляет собой вычисляемую проверку продольного избыточного кода .

В США

• Десятая цифра национального идентификатора поставщика услуг здравоохранения США.
• Последняя цифра кода POSTNET .
• Североамериканский номер CUSIP .
• Последняя (девятая) цифра транзитного номера маршрутизации ABA , — банковского кода используемого в США.
• Девятая цифра идентификационного номера транспортного средства (VIN).
• Идентификационные номера пациентов клиники Мэйо, используемые в Аризоне и Флориде, включают конечную контрольную цифру. .
• Одиннадцатая цифра номера записи Таможенного и пограничного контроля .

В Центральной Америке

• Налоговый номер Гватемалы (NIT – идентификационный номер налогоплательщика) на основе модуля 11.

В Евразии

• Великобритании Номер Национальной службы здравоохранения использует алгоритм по модулю 11.
• Испанский налоговый идентификационный номер (NIF) (на основе модуля 23).
• Голландский Burgerservicenummer ( BSN ) (национальный идентификатор) использует алгоритм по модулю 11.
• Девятая цифра израильского номера Теудат Зеут (удостоверение личности).
• 13-я цифра Сербии и бывшей Югославии уникального номера главного гражданина (JMBG). (но не все, из-за ошибок или нерезидентности)
• Последние две цифры 11-значного турецкого идентификационного номера ( турецкий : TC Kimlik Numarası ).
• Девятый символ в 14-значном номере паспорта крупного рогатого скота ЕС (циклы от 1 до 7: см. Британскую службу перемещения скота ).
• Девятая цифра исландского Kennitala (национального идентификационного номера).
• Контрольные цифры по модулю 97 в номерах банковских счетов Бельгии и Сербии . Сербия иногда также использует модуль 11 для ссылочного номера.
• Девятая цифра венгерского номера TAJ (номер социального страхования).
• Для жителей Индии уникальный идентификационный номер под названием Aadhaar имеет завершающую 12-ю цифру, которая рассчитывается с помощью алгоритма Верхуффа .
• Ведомство интеллектуальной собственности Сингапура (IPOS) утвердило новый формат номеров заявок на регистрируемую интеллектуальную собственность (ИС, например, товарные знаки , патенты , зарегистрированные образцы ). Он будет включать в себя контрольный символ, рассчитанный с помощью алгоритма Дамма .
• Последняя цифра идентификационного номера гражданина Китая (второе поколение) рассчитывается по модулю 11-2, как указано в китайском GuoBiao (также известном как национальный стандарт) GB11643-1999, который принимает ISO 7064:1983. «X» используется, если вычисленная контрольная цифра равна 10.
• 11-я цифра эстонского Isikukood (персональный идентификационный код).
• Последняя буква на номерных знаках транспортных средств Сингапура .

В Океании

• Австралии Номер налоговой декларации (по модулю 11).
• Седьмой символ Новой Зеландии номера NHI .
• Последняя цифра в номере системы мониторинга движения новозеландского локомотива (TMS).

Алгоритмы

Известные алгоритмы включают в себя:

• Алгоритм Луна (1954)
• Алгоритм Верховева (1969)
• Алгоритм Дамма (2004 г.)

См. также

• Контрольная сумма
• Выбрасывание девяток – аналогичная модульная проверка суммы
• Контрольный бит – двоичный эквивалент

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

• Идентификационные номера и схемы контрольных цифр (математическое объяснение различных схем контрольных цифр)
• Калькулятор контрольных цифр UPC, EAN и SCC-14
• Калькулятор контрольных цифр GS1