チェックデジット

チェックデジットは、銀行口座番号などの識別番号のエラー検出に使用される冗長性チェックの一種で、手動で入力されるアプリケーションで使用されます。これは、コンピューターで生成されたデータのエラーをチェックするために使用されるバイナリパリティビットに似ています。これは、シーケンス入力内の他の数字（または文字）からアルゴリズムによって計算された1つ以上の数字（または文字）で構成されます。^[1]

チェック ディジットを使用すると、1 つの数字の誤入力や連続する 2 つの数字の順列など、一連の文字 (通常は数字) の入力における単純なエラーを検出できます。

チェックディジットアルゴリズムは、一般的に人間の 転記ミスを捕捉するために設計されている。複雑さの順に並べると、以下のようになる。 ^[2]

• l → 1 や O → 0 などの文字/数字の誤り
• 1 → 2 などの 1 桁の間違い
• 転置エラー（12 → 21など）
• 11 → 22 のような二重エラー
• 132 → 231 などのジャンプ転置エラー
• 131 → 232 のようなジャンプツインエラー
• 60 → 16（「sixty」から「sixteen」）などの発音の誤り

システムを選択する際には、エラーを検出する可能性の高さと実装の難しさのトレードオフになります。単純なチェック ディジット システムは人間が簡単に理解して実装できますが、実装に高度なプログラムを必要とする複雑なシステムほど多くのエラーを検出できません。

望ましい機能は、左にゼロを埋め込んでもチェック ディジットが変更されないことです。これにより、可変長の数値を使用して長さを変更できます。元の数値に 1 つのチェック ディジットが追加された場合、システムは2 つの置換エラー (12 → 34) などの複数のエラーを常に検出できるわけではありませんが、通常、二重エラーは 90% の確率で検出されます (両方の変更で、オフセット量によって出力を変更する必要があります)。

非常に単純なチェック ディジットの方法は、すべての桁の合計 (デジタル合計)を 10で割った値を取ることです。この方法では、1 桁のエラーは常に合計を変えるため、このようなエラーは検出されます。ただし、順序を変更しても合計は変わらないため、転置エラー (2 つの桁の入れ替え) は検出されません。

もう少し複雑な方法は、数字の位置ごとに異なる重みを付けて、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 31 の重み、EAN番号 (GS1 アルゴリズム) の 13 13 の重み、および米国の銀行ルーティングトランジット番号で使用される 371 371 371 の重みです。このシステムは、すべての 1 桁のエラーと、転置エラーの約 90% ^{[引用が必要]}を検出します。1、3、7、および 9 が使用されるのは、これらが10 と互いに素であるため、どの数字を変更するとチェック ディジットも変更されるためです。2 または 5 で割り切れる係数を使用すると、情報が失われ (5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0 を 10 で割った値であるため)、一部の 1 桁のエラーを検出できません。隣接する数字に異なる重みを使用するということは、ほとんどの転置でチェック ディジットが変更ただし、すべての重みは偶数だけ異なるため、2 と 5 を掛けると 10 になるため、5 だけ異なる 2 つの数字 (0 と 5、1 と 6、2 と 7、3 と 8、4 と 9) の転置は検出されません。

ISBN-10 コードでは、代わりに素数であるモジュロ 11 を使用し、すべての数字位置に 1、2、... 10 の異なる重みが与えられます。このシステムでは、1 桁の置換エラーと転置エラー (ジャンプ転置を含む) をすべて検出しますが、チェック ディジットが 10 になる可能性があり、これは「X」で表されます。(代替案としては、単に「X」チェック ディジットになるシリアル番号を使用しないようにする方法があります。) ISBN-13 では、代わりに EAN 番号で使用される GS1 アルゴリズムを使用します。

より複雑なアルゴリズムには、1 桁の転置エラーの 98% を検出する (90 ↔ 09 は検出しない) Luhn アルゴリズム(1954) や、さらに洗練されたVerhoeff アルゴリズム(1969) などがあり、1 桁の置換エラーと転置エラーのすべて、および多くの (ただしすべてではない) より複雑なエラーを検出します。別の抽象代数ベースの方法であるDamm アルゴリズム(2004) も同様に、すべての 1 桁エラーとすべての隣接する転置エラーを検出します。これら 3 つの方法は、単一のチェック ディジットを使用するため、より複雑なエラーの約 10% ^{[引用が必要]}を検出できません。この失敗率を下げるには、複数のチェック ディジットを使用するか (たとえば、以下で説明するモジュロ 97 チェックでは 2 つのチェック ディジットを使用します。アルゴリズムについては、国際銀行口座番号を参照してください)、チェック ディジットに文字と数字など、より広範囲の文字を使用する必要があります。

ユニバーサル商品コード、国際商品番号、グローバルロケーション番号、またはグローバルトレードアイテム番号の最後の桁は、次のように計算されるチェックディジットです。^{[3] [4]}

1. 左から奇数番目の数字（1 番目、3 番目、5 番目など、チェック ディジットは含みません）を合計し、3 を掛けます。
2. 偶数位置（2 番目、4 番目、6 番目など）の数字（チェック ディジットまでの数字）を結果に追加します。
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. 2 つの結果を合計すると、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. 2 つの結果を合計します: 0 + 5 = 5。
5. チェック ディジットを計算するには、(5 / 10) の余り (5 を 10 で割った余りとも呼ばれます) を計算し、0 でない場合は 10 から引きます。つまり、(5 / 10) = 0 余り 5、(10 - 5) = 5 です。したがって、チェック ディジットx の値は 5 です。

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（2007年1月から使用）は、書籍のバーコードの下にあるEAN-13コードと同じです。チェックデジットはUPCと同じ方法で生成されます。^[7]

2004年から使用されているNOIDチェック数字アルゴリズム（NCDA）^[8]は、永続的な識別子への応用を目的として設計されており、拡張数字と呼ばれる文字と数字の可変長文字列で機能します。ARK識別子スキームで広く使用されており、ハンドルシステムやDOIなどのスキームでも多少使用されています。拡張数字は、母音と文字「l」（エル）を除いた英数字であるベータ数字に制限されています。この制限は、偶然に単語を形成する可能性が低く、Oと0、またはlと1の両方を含まない不透明な文字列を生成する場合に役立ちます。ベータ数字のレパートリーはR=29の素数基数であるため、アルゴリズムはR=29文字未満の文字列に対して単一文字エラーと転置エラーの検出を保証できます^[9]（それを超えると、チェックがわずかに弱くなります）。このアルゴリズムは、素数基数 R を持つ任意の文字レパートリーと、長さが R 文字未満の文字列に一般化されます。

• 国際SEDOL番号。
• ISSNコードまたはIMO 番号の最後の桁。
• 国際証券識別番号(ISIN)。
• オブジェクト管理グループFIGI標準の最終桁。^[10]
• 国際CAS 登録番号の最後の桁。
• クレジットカード口座番号のチェックディジットを10で割った値。Luhnアルゴリズムで計算されます。
  • ノルウェーの銀行振込（口座振替）で使用されるKID（顧客識別番号）番号にも使用されます。
  • 携帯電話のIMEIに使用されます。
• 国際取引識別番号 ( GTIN ) の EAN/UPC シリアル番号の最後のチェック ディジット。GTIN-8、GTIN-12、GTIN-13、GTIN-14 に適用されます。
• DUNS番号の最後の桁(ただし、最後の桁はチェック ディジットではなく、新しい割り当てで自由に選択されるなど、変更される予定です)。
• 国際銀行口座番号(モジュロ 97 チェック)の 3 桁目と 4 桁目。
• 国際標準テキストコードの最後の桁。
• 磁気ストライプ カードにエンコードされる最後の文字は、計算された縦方向冗長性チェックです。

• 米国の医療業界のNational Provider Identifierの 10 桁目。
• POSTNETコードの最後の桁。
• 北米のCUSIP番号。
• 米国で使用される銀行コードであるABA ルーティングトランジット番号の最終 (9 番目) の桁。
• 車両識別番号(VIN)の 9 桁目。
• アリゾナ州とフロリダ州で使用されているメイヨークリニックの患者識別番号には、末尾のチェックディジットが含まれています^{[引用が必要]}。
• 税関・国境警備局入国番号の 11 桁目。

• モジュロ11に基づくグアテマラ納税番号 (NIT – Número de Identificación Tributaria) 。

• 英国のNHS 番号はモジュロ 11 アルゴリズムを使用します。
• スペインの会計識別番号 (número de identificación Financial、NIF) (モジュロ 23 に基づく)。
• オランダの Burgerservicenummer (BSN) (国民識別子) は、モジュロ 11 アルゴリズムを使用します。
• イスラエルの Teudat Zehut (身分証明書) 番号の 9 桁目。
• セルビアおよび旧ユーゴスラビアの 固有マスター市民番号(JMBG)の 13 桁目。(ただし、エラーや非居住のため、すべてではありません)
• 11 桁のトルコ識別番号(トルコ語: TC Kimlik Numarası ) の最後の 2 桁。
• 14 文字のEU牛パスポート番号の 9 番目の文字 (1 から 7 まで順番に: British Cattle Movement Serviceを参照)。
• アイスランドの ケニタラ（国民ID番号）の9番目の数字。
• ベルギーとセルビアの銀行口座番号のチェック ディジットは 97 を法とします。セルビアでは参照番号に 11 を法とすることもあります。
• ハンガリーのTAJ 番号 (社会保険番号)の 9 桁目。
• インドの住民の場合、 Aadhaarと呼ばれる固有のID番号には、 Verhoeffアルゴリズムで計算された末尾の12桁目があります。^[11]
• シンガポール知的財産庁（ IPOS）は、登録可能な知的財産（商標、特許、登録意匠など）の出願番号の新しい形式を確認しました。この新しい形式には、ダムアルゴリズムで計算されたチェック文字が含まれます。^[12]
• 中国国民 ID 番号 (第 2 世代) の最後の桁は、ISO 7064:1983 を採用した中国国標 (別名国家標準) GB11643-1999 で指定されているように、11-2 を法として計算されます。計算されたチェック ディジットが 10 の場合は、「X」が使用されます。
• エストニアの Isikukood (個人識別コード)の 11 桁目。
• シンガポールの車両登録プレートの最後の文字。

• オーストラリアの納税者番号（モジュロ11に基づく）。
• ニュージーランド NHI 番号の 7 番目の文字。
• ニュージーランドの機関車の交通監視システム (TMS) 番号の最後の桁。

注目すべきアルゴリズムは次のとおりです。

• ルーンアルゴリズム(1954)
• ヴェルホフアルゴリズム(1969)
• ダムアルゴリズム(2004)

• チェックサム
• 9 を捨てる– 類似のモジュラー和チェック
• チェックビット– 2進数相当

• 識別番号とチェック ディジット方式 (さまざまなチェック ディジット方式の数学的説明)
• UPC、EAN、SCC-14 チェックディジット計算機
• GS1 チェックデジット計算機