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 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 (mod 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 (mod 11).

ISBN 13

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

NCDA

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

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

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

В США

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

В Евразии

В Океании

Алгоритмы

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

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

Ссылки

  1. ^ "Что такое контрольная цифра? - Определение из Techopedia". Techopedia.com . Получено 2022-03-16 .
  2. ^ Киртланд, Джозеф (2001). Идентификационные номера и схемы контрольных цифр. Материалы для учебных занятий. Математическая ассоциация Америки. С. 4–6. ISBN 978-0-88385-720-5.
  3. ^ "GS1 Check Digit Calculator". GS1 US. 2006. Архивировано из оригинала 2008-05-09 . Получено 2008-05-21 .
  4. ^ «Как вручную рассчитать контрольную цифру». GS1.
  5. ^ "Калькулятор контрольных цифр". GS1. 2005. Получено 21.05.2008 .
  6. ^ "Check Digit Calculator, на официальном сайте GS1 US". GS1 US. Архивировано из оригинала 21.11.2016 . Получено 09.08.2012 .
  7. ^ "Руководство пользователя ISBN". Международное агентство ISBN. 2005. Архивировано из оригинала 29-04-2014 . Получено 21-05-2008 .
  8. ^ Кунце, Джон А. "noid - Nice Opaque Identifier Generator commands". metacpan.org . Архивировано из оригинала 2022-05-22 . Получено 2022-10-15 .
  9. ^ Дэвид Брессо, Стэн Вагон, «Вычислительная теория чисел», 2000, Key College Publishing
  10. ^ "OpenFIGI: Раскройте силу эффективности с помощью открытой символики". OpenFIGI . Архивировано из оригинала 2022-08-09 . Получено 2022-10-15 .
  11. ^ "Уникальная идентификационная карта" (PDF) . Geek Gazette . Осень 2011. стр. 16. Архивировано из оригинала (PDF) 2014-06-26.
    • альтернативный URL-адрес
  12. ^ Чонг-Йи Ху (20 января 2014 г.). «Новый формат номеров заявок на интеллектуальную собственность в Сингапуре на IPOS». Патентный блог Сингапура . Cantab IP. Архивировано из оригинала 14 июля 2014 г. Получено 6 июля 2014 г.

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