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

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

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

Дизайн

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

  • однозначные ошибки, такие как 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) и 371371371 весов, используемых в банках США. маршрутные транзитные номера. Эта система обнаруживает все однозначные ошибки и около 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, упомянутая ниже, которая использует две контрольные цифры - алгоритм см. Номер международного банковского счета ) и / или использовать более широкий диапазон символов в контрольной цифре, например буквы плюс цифры.

Примеры

UPC

Последняя цифра Универсальный код продукта контрольная цифра, вычисляемая следующим образом:[2]

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

Например, штрих-код 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Икс".

  1. Сложите нечетные цифры числа: 0 + 0 + 0 + 0 + 0 + 0 = 0.
  2. Умножьте результат на 3: 0 x 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. Следовательно, контрольная цифра Икс значение 5.

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 (используется с января 2007 г.) приравнивается к EAN-13 код, находящийся под штрих-кодом книги. Его контрольная цифра генерируется так же, как и UPC, за исключением того, что четные цифры умножаются на 3 вместо нечетных цифр.[3]

EAN (номера GLN, GTIN, EAN, администрируемые GS1)

EAN (Европейский номер артикула ) контрольные цифры (администрируются GS1 ) вычисляются путем суммирования каждого из нечетных номеров позиций, умноженных на 3, а затем путем сложения суммы четных номеров позиций. Числа проверяются справа налево, поэтому первая нечетная позиция - это последняя цифра в коде. Последняя цифра результата вычитается из 10 для расчета контрольной цифры (или остается как есть, если она уже равна нулю). Калькулятор контрольных цифр GS1 и подробная документация доступны онлайн по адресу GS1 веб-сайт.[4]Другая официальная страница калькулятора показывает, что механизм выдачи GTIN-13 одинаков для Глобальный номер местоположения / GLN.[5]

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

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

В США

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

  • Налоговый номер Гватемалы (NIT - Número de Identificación Tributaria) основан на по модулю 11.

В евразии

В Океании

Алгоритмы

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

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

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

  1. ^ Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Учебные материалы. Математическая ассоциация Америки. С. 4–6. ISBN  978-0-88385-720-5.
  2. ^ «Калькулятор контрольных цифр GS1». GS1 США. 2006. Архивировано с оригинал на 2008-05-09. Получено 2008-05-21.
  3. ^ "Руководство пользователя ISBN". Международное агентство ISBN. 2005 г.. Получено 2008-05-21.
  4. ^ «Калькулятор контрольной цифры». GS1. 2005 г.. Получено 2008-05-21.
  5. ^ «Калькулятор контрольных цифр на официальном сайте GS1 в США». GS1 США. Получено 2012-08-09.
  6. ^ http://openfigi.com
  7. ^ «Уникальная идентификационная карта». Geek Gazette. Студенческое отделение IEEE (Осень 2011 г. ): 16. Архивировано из оригинал 2012-10-24.
  8. ^ Д-р Чонг-Йи Кху (20 января 2014 г.). «Новый формат номеров сингапурских IP-заявок в IPOS». Патентный блог Сингапура. Кантаб IP. Получено 6 июля 2014.

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