Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

Дизайн [ править ]

Алгоритмы контрольной цифры обычно предназначены для выявления человеческих ошибок транскрипции . В порядке сложности они включают следующее: [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) и 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, упомянутая ниже, которая использует две контрольные цифры - для алгоритма см. Международный номер банковского счета ) и / или использовать более широкий диапазон символов в контрольной цифре, например буквы плюс цифры.

Примеры [ править ]

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 x ».

  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. Следовательно, значение контрольной цифры x равно 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 такой же, как и для Global Location Number / GLN. [5]

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

Международный [ править ]

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

В США [ править ]

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

В Центральной Америке [ править ]

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

В Евразии [ править ]

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

В Океании [ править ]

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

Алгоритмы [ править ]

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

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

См. Также [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

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