stringtranslate.com

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

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

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

Дизайн

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

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

Желательная особенность заключается в том, что заполнение нулями слева не должно изменять контрольную цифру. Это позволяет использовать числа переменной длины и изменять длину. Если к исходному номеру добавлена ​​одна контрольная цифра, система не всегда фиксирует несколько ошибок, например две ошибки замены (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, EAN, GLN, GTIN, номера, администрируемые GS1.

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

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

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

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

Последний символ десятизначного международного стандартного номера книги — это контрольная цифра, вычисляемая таким образом, что умножение каждой цифры на ее позицию в номере (считая справа) и взятие суммы этих произведений по модулю 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. [7]

NCDA

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

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

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

В США

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

В Евразии

В Океании

Алгоритмы

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

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

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

  1. ^ «Что такое контрольная цифра? - Определение из Techopedia» . Techopedia.com . Проверено 16 марта 2022 г.
  2. ^ Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Ресурсы для классных комнат. Математическая ассоциация Америки. стр. 4–6. ISBN 978-0-88385-720-5.
  3. ^ «Калькулятор контрольных цифр GS1» . GS1 США. 2006. Архивировано из оригинала 9 мая 2008 г. Проверено 21 мая 2008 г.
  4. ^ «Как вычислить контрольную цифру вручную» . ГС1.
  5. ^ «Проверьте калькулятор цифр» . ГС1. 2005 . Проверено 21 мая 2008 г.
  6. ^ «Проверьте калькулятор цифр на официальном сайте GS1 в США» . GS1 США. Архивировано из оригинала 21 ноября 2016 г. Проверено 9 августа 2012 г.
  7. ^ «Руководство пользователя ISBN» . Международное агентство ISBN. 2005. Архивировано из оригинала 29 апреля 2014 г. Проверено 21 мая 2008 г.
  8. ^ Джон, А. Кунце. «noid — команды генератора хороших непрозрачных идентификаторов». Metacpan.org . Архивировано из оригинала 22 мая 2022 г. Проверено 15 октября 2022 г.
  9. ^ Дэвид Брессуд, Стэн Вагон, «Вычислительная теория чисел», 2000, Key College Publishing
  10. ^ «OpenFIGI: раскройте потенциал эффективности с помощью открытой символики» . ОткрытьФИГИ . Архивировано из оригинала 9 августа 2022 г. Проверено 15 октября 2022 г.
  11. ^ «Уникальное удостоверение личности» (PDF) . Компьютерная газета . Осень 2011. с. 16. Архивировано из оригинала (PDF) 26 июня 2014 г.
    • альтернативный URL
  12. ↑ Чонг-Йи Ху (20 января 2014 г.). «Новый формат номеров заявок на IP в Сингапуре в IPOS». Патентный блог Сингапура . Кантаб ИП. Архивировано из оригинала 14 июля 2014 года . Проверено 6 июля 2014 г.

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