체크 디지트

Check digit

체크 디지트는 은행 계좌 번호와 같은 식별 번호의 오류 검지에 사용되는 중복 검사의 한 형태로서, 적어도 때때로 수동으로 입력될 애플리케이션에 사용된다. 컴퓨터 생성 데이터의 오류를 확인하는 데 사용되는 이진 패리티 비트와 유사하다. 시퀀스 입력의 다른 자리(또는 문자)에서 알고리즘에 의해 계산된 하나 이상의 숫자(또는 문자)로 구성된다.

체크 디지트로, 한 개의 잘못 입력된 숫자 또는 두 개의 연속된 숫자의 일부 순열과 같은 일련의 문자(보통 숫자)의 입력에서 간단한 오류를 감지할 수 있다.

디자인

체크 디지트 알고리즘은 일반적으로 인간의 전사 오류를 포착하도록 설계된다. 복잡도 순서는 다음과 같다.

  • l → 1 또는 O → 0과 같은 문자/자리 오류
  • 1 → 2와 같은 한자릿수 오류
  • 12 → 21과 같은 전이 오류
  • 11 → 22와 같은 쌍둥이 오류
  • 132 → 231과 같은 점프 전이 오류
  • 131 → 232와 같은 점프 트윈 에러
  • 60 → 16 ("반복" ~ "반복")과 같은 음성 오류

시스템을 선택할 때, 오류 포착의 높은 확률은 구현의 어려움에 맞선다; 간단한 체크 디지트 시스템은 인간에 의해 쉽게 이해되고 구현되지만 복잡한 시스템만큼 많은 오류를 포착하지 못하기 때문에 구현하기 위해서는 정교한 프로그램이 필요하다.

0이 있는 왼쪽 패딩은 체크 디지트를 변경하지 않아야 한다는 것이 바람직한 특징이다. 이를 통해 가변 길이 번호를 사용하고 길이를 변경할 수 있다. 원래 번호에 체크 디지트가 한 개 추가되는 경우, 시스템은 두 개의 교체 오류(12 → 34)와 같이 항상 여러 개의 오류를 캡처하지는 않지만, 일반적으로 이중 오류는 90%의 시간에 포착된다(두 변경 모두 금액을 상쇄하여 출력을 변경해야 함).

매우 간단한 체크 디지트 방법은 모든 숫자(디지털 합계) 모듈로 10의 합을 취하는 것이다. 이러한 오류는 항상 합계를 변경하지만, 재순서가 합계를 변경하지 않기 때문에 전환 오류(두 자리 전환)는 포착되지 않기 때문에 한 자릿수 오류가 발생할 수 있다.

약간 더 복잡한 방법은 각 숫자 위치에 대해 서로 다른 가중치를 사용하여 숫자 10의 가중치 합계를 취하는 것이다.

예를 들어, 4자리 숫자의 가중치가 5, 3, 2, 7이고 코드화할 숫자가 4871인 경우, 5×4 + 3×8 + 2×7 + 7×1 = 65, 즉 65모듈로 10을 사용하고 체크 디지트는 5가 되어 48715를 준다.

인접한 숫자에 대한 가중치가 서로 다른 1, 3, 7 또는 9의 가중치를 가진 시스템은 널리 사용된다. 예를 들어 UPC 코드의 가중치 31개, EAN 번호(GS1 알고리즘)의 가중치 13개, 그리고 미국 은행 송금 번호에 사용되는 371 371 371개 가중치 등이다. 이 시스템은 모든 한 자릿수 오류와 약 90%의 전이 오류를 감지한다. 1, 3, 7, 9는 10과 동시 발생하므로 임의의 자릿수를 변경하면 체크 디지트가 변경된다. 2 또는 5로 구분되는 계수를 사용하면 정보가 손실된다(5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0 modulo 10). 따라서 일부 한 자릿수를 잡지 못한다. 오류. 인접한 숫자에 다른 가중치를 사용하는 것은 대부분의 전이가 체크 숫자를 변경한다는 것을 의미하지만, 모든 가중치가 짝수로 다르기 때문에 2와 5 곱하기 때문에 5(0과 5, 1, 6, 2, 2, 7, 3, 8, 4, 9), 5가 10을 곱하기 때문에 5(0과 5, 7, 3, 8, 9)만큼 다른 두 자리 수의 전이는 포착되지 않는다.

ISBN-10 코드는 대신 prime인 modulo 11을 사용하며, 모든 숫자 위치는 1, 2, ... 10의 가중치를 가진다. 따라서 이 시스템은 모든 한 자리 치환 및 전치 오류(점프 전이를 포함)를 감지하지만, 체크 디지트의 원가는 10일 수 있으며, 이는 "X"로 표시된다. (대안은 단순히 "X" 체크 디지트가 되는 일련 번호를 사용하지 않는 것이다.) 대신 ISBN-13은 EAN 번호에 사용되는 GS1 알고리즘을 사용한다.

보다 복잡한 알고리즘에는 한 자릿수 전이 오류를 98% 포착(90파운드 09를 검출하지 못함)하는 Luhn 알고리즘(1954년)과 한 자릿수 대체 및 전이 오류를 모두 포착하는 훨씬 정교한 Verhoeff 알고리즘(1969년), 그리고 (전부는 아니지만) 더 복잡한 오류가 많다. 유사한 것은 추상 대수 기반 방법인 Damm 알고리즘(2004)도 모든 한 자릿수 오류와 모든 인접 전이 오류를 감지한다. 이 세 가지 방법은 하나의 체크 숫자를 사용하므로 더 복잡한 오류의 약 10%를 캡처하지 못할 것이다. 이 고장률을 줄이려면 둘 이상의 체크 디지트(예를 들어, 알고리즘의 경우 국제 은행 계좌 번호 참조)를 사용하거나 체크 디지트의 더 넓은 범위의 문자(예: 문자와 숫자)를 사용해야 한다.

예

UPC

유니버설 제품 코드의 마지막 자릿수는 다음과 같이 계산된 체크 디짓이다.[2]

  1. 오른쪽의 홀수 위치(첫 번째, 세 번째, 다섯 번째 등 - 체크 디지트를 포함하지 않음)에 숫자를 함께 더하고 3을 곱한다.
  2. 짝수 위치(두 번째, 네 번째, 여섯 번째 등)에 있는 숫자(체크 디지트를 포함하지 않음)를 결과에 추가한다.
  3. 결과의 나머지를 10으로 나눈다(즉). modulo 10 작동). 나머지가 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 modulo 10)라고도 하는 (53 / 10)의 나머지를 취하고, 0이 아니면 10에서 뺀다. 따라서 체크 디지트 값은 7이다. 즉, (53 / 10) = 5 나머지 3; 10 - 3 = 7.

다른 예: 다음 식품 항목 "010101010101010x"의 체크 디짓 계산.

  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. 체크 디짓(check digit)을 계산하려면 (5 modulo 10)이라고도 하는 (5 / 10)의 나머지를 취하며, 0이 아니면 10: (5 / 10) = 0 나머지 5; (10 - 5) = 5. 따라서 체크 디짓 x 값은 5이다.

ISBN 10

추가 정보: International_Standard_Book_Number § ISBN-10_check_digits

10자리 국제표준서적번호의 최종 문자는 각 자릿수에 숫자(오른쪽에서 계산)의 위치를 곱하고 이들 제품 모듈로 11의 합을 취하도록 계산한 체크 디지트다. 오른쪽에서 가장 먼 자리(숫자 1을 곱함)는 체크 디지트로 합을 정확하게 하기 위해 선택된다. 문자 X로 표현되는 값 10이 필요할 수 있다. 예를 들어, ISBN0-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 + 1×4 + 5×5 + 3×6 + 8×7 + 2×9 + 1×10 = 143 ≡ 0(모드 11).

ISBN 13

추가 정보: 국제_표준_Book_Number § ISBN-13_check_digit_calculation

ISBN 13(2007년 1월 사용)은 책의 바코드 아래에 있는 EAN-13 코드와 동일하다. 체크 디지트는 홀수 대신 짝수 자리에 3을 곱한 것을 제외하고 UPC와 같은 방식으로 생성된다.[3]

EAN(GS1에서 관리하는 GLN, GTIN, EAN 번호)

EAN(유럽 기사 번호) 체크 숫자(GS1 관리)는 홀수 위치 번호 각각에 3을 곱한 다음 짝수 위치 번호의 합을 더하여 계산한다. 숫자는 오른쪽에서 왼쪽으로 검사되므로 첫 번째 홀수 위치는 코드에서 마지막 자리 숫자다. 결과의 최종 자릿수를 10에서 빼서 체크 디지트를 계산한다(또는 이미 0인 경우 그대로 남겨둔다). GS1 체크 디지트 계산기와 자세한 설명서는 GS1의 웹사이트에서 온라인으로 볼 수 있다.[4] 다른 공식 계산기 페이지는 GTIN-13의 메커니즘이 Global Location Number/GLN과 동일하다는 것을 보여준다.[5]

엔씨다

2004년부터 사용되고 있는 [6]NOID Check Digit Algorithm(NCDA)은 영구 식별자에 적용되도록 설계되었으며, 확장 자릿수라고 하는 문자와 숫자의 가변 길이 문자열로 동작한다. ARK 식별자 체계와 함께 널리 사용되며 핸들 시스템 및 DOI와 같은 체계와 함께 다소 사용된다. 확장된 자릿수는 영숫자에서 모음을 뺀 숫자 및 문자 'l'(엘)로 제한된다. 이 제한사항은 우연히 단어를 형성할 가능성이 낮고 O와 0 또는 l와 1을 모두 포함하지 않는 불투명 문자열을 생성할 때 도움이 된다. R=29의 주요 라디스를 갖는 베타수 레퍼토리는 알고리즘을 통해 R=29자 미만의 문자열(이상의 경우 약간 약한 체크 표시)에 대해 단일 문자 및 전이 오류를[7] 검출할 수 있도록 보장한다. 알고리즘은 R자 미만의 문자열을 가진 프라임 라디ix R과 문자열을 가진 모든 문자 레퍼토리로 일반화된다.

기타 체크 디지트의 예

국제

미국에서

중앙아메리카에서

  • modulo 11에 근거한 과테말라 세금 번호(NIT - Numero de Identificacion Granquaria)

유라시아에서

오세아니아에서

알고리즘

주목할 만한 알고리즘은 다음과 같다.

참고 항목

참조

  1. ^ Kirtland, Joseph (2001). Identification Numbers and Check Digit Schemes. Classroom Resource Materials. Mathematical Association of America. pp. 4–6. ISBN 978-0-88385-720-5.
  2. ^ "GS1 Check Digit Calculator". GS1 US. 2006. Archived from the original on 2008-05-09. Retrieved 2008-05-21.
  3. ^ "ISBN Users Manual". International ISBN Agency. 2005. Retrieved 2008-05-21.
  4. ^ "Check Digit Calculator". GS1. 2005. Retrieved 2008-05-21.
  5. ^ "Check Digit Calculator, at GS1 US official site". GS1 US. Retrieved 2012-08-09.
  6. ^ https://metacpan.org/pod/distribution/Noid/noid#NOID-CHECK-DIGIT-ALGORITHM
  7. ^ 데이비드 브레수드, 스탠 웨건, "계산 번호 이론", 2000년, 주요 대학 출판
  8. ^ http://openfigi.com
  9. ^ "Unique Identification Card". Geek Gazette. IEEE Student Branch (Autumn 2011): 16. Archived from the original on 2012-10-24.
  10. ^ Dr. Chong-Yee Khoo (20 January 2014). "New Format for Singapore IP Application Numbers at IPOS". Singapore Patent Blog. Cantab IP. Retrieved 6 July 2014.

외부 링크

  • 식별 번호 및 체크 디지트 구성표(다양한 체크 디지트 구성표의 수학적 설명)
  • UPC, EAN 및 SCC-14 체크 디지트 계산기
  • GS1 체크 디지트 계산기