チェックディジット

ウィキペディアから、無料の百科事典
ナビゲーションにジャンプ 検索にジャンプ

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

チェックディジットを使用すると、1つのタイプミスした数字や、2つの連続する数字の順列など、一連の文字（通常は数字）の入力で単純なエラーを検出できます。

デザイン

チェックディジットアルゴリズムは、通常、人間の 文字起こしエラーをキャプチャするように設計されています。複雑な順に、これらには次のものが含まれます。 [1]

  • l→1またはO→0などの文字/数字のエラー
  • 1→2などの1桁のエラー
  • 12→21などの転置エラー
  • 11→22などのツインエラー
  • 132→231などのジャンプ転置エラー
  • 131→232などのジャンプツインエラー
  • 60→16（「60」から「16」）などの音声エラー

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

望ましい機能は、ゼロを左パディングしてもチェックディジットが変更されないことです。これにより、可変長の数値を使用したり、長さを変更したりできます。元の番号に1つのチェックディジットが追加されている場合、システムは2つの置換エラー（12→34）などの複数のエラーを常にキャプチャするとは限りませんが、通常、2つのエラーは90％の確率でキャッチされます（両方の変更は金額を相殺して出力を変更する必要があります）。

非常に単純なチェックディジットの方法は、10を法とするすべての桁の合計（デジタル合計）を取得することです。これにより、1桁のエラーがキャッチされます。このようなエラーは常に合計を変更しますが、転置エラー（スイッチング）はキャッチしません。 2桁）並べ替えても合計は変わりません。

もう少し複雑な方法は、数字の位置ごとに異なる重みを使用して、10を法とする数字 の重み付き合計を取得することです。

これを説明するために、たとえば、4桁の数字の重みが5、3、2、7で、コード化される数字が4871の場合、5×4 + 3×8 + 2×7 + 7×1が必要になります。 = 65、つまり10を法として65であり、チェックディジットは5であり、48715になります。

重みが1、3、7、または9で、隣接する数値の重みが異なるシステムが広く使用されています。たとえば、UPCコードでは31 31の重み、 EAN番号では13 13の重み（GS1アルゴリズム）、371米国の銀行ルーティングトランジット番号で使用される371371ウェイト。このシステムは、すべての1桁のエラーと、転置エラーの約90％を検出します。1、3、7 、および9は互いに素であるため、使用されます10の場合、任意の桁を変更するとチェックディジットが変更されます。2または5で割り切れる係数を使用すると、情報が失われ（5×0 = 5×2 = 5×4 = 5×6 = 5×8 = 0を法として10であるため）、1桁のエラーをキャッチできません。隣接する数値に異なる重みを使用することは、ほとんどの転置がチェックディジットを変更することを意味します。ただし、すべての重みが偶数で異なるため、2と9であるため、5（0と5、1と6、2と7、3と8、4と9）だけ異なる2桁の転置はキャッチされません。 5を掛けると10になります。

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

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

例

UPC

Universal Product Codeの最後の桁は、次のように計算されるチェックディジットです。[2]

  1. 右から奇数の桁（1、3、5など-チェックディジットを除く）を足し合わせ、3を掛けます。
  2. 結果に偶数の位置（2番目、4番目、6番目など）の数字（チェックディジットまで）を追加します。
  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. 2つの結果を合計します：42 + 11 = 53。
  5. チェックディジットを計算するには、（53 modulo 10）とも呼ばれる（53/10）の余りを取り、0でない場合は、10から減算します。したがって、チェックディジットの値は7です。つまり（53/10） ）= 5剰余3; 10-3 = 7。

別の例：次の食品「01010101010x」のチェックディジットを計算します。

  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 modulo 10）とも呼ばれ、0でない場合は、10から減算します。つまり（5/10）= 0余り5; （10-5）= 5。したがって、チェックディジットのx値は5です。

ISBN 10

10桁の国際標準図書番号の最後の文字は、各桁に数値の位置（右から数えて）を掛けて、11を法とするこれらの積の合計が0になるように計算されたチェックディジットです。最も遠い桁右側（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（ 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年1月に使用）は、本のバーコードの下にあるEAN-13コードと同じです。そのチェックディジットは、偶数桁が奇数桁ではなく3倍されることを除いて、UPCと同じ方法で生成されます。[3]

EAN（GLN、GTIN、GS1が管理するEAN番号）

EAN（European Article Number）チェックディジット（GS1によって管理される）は、奇数の位置番号のそれぞれに3を掛けたものを合計し、次に偶数の位置番号の合計を加算することによって計算されます。数字は右から左に向かって調べられるので、最初の奇数の位置はコードの最後の桁です。結果の最後の桁を10から減算して、チェックディジットを計算します（または、すでにゼロの場合はそのままにします）。GS1チェックディジット計算機と詳細なドキュメントはGS1のWebサイトでオンラインになっています。[4] 別の公式計算機ページは、GTIN-13のメカニズムがグローバルロケーション番号/ GLNでも同じであることを示しています。[5]

NCDA

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

チェックディジットの他の例

インターナショナル

アメリカでは

中央アメリカでは

  • モジュロ11に基づくグアテマラ税番号（NIT-NúmerodeIdentificaciónTributaria） 。

ユーラシアでは

オセアニアで

アルゴリズム

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

も参照してください

参考文献

  1. ^ カートランド、ジョセフ（2001）。識別番号とチェックディジットスキーム。教室のリソース資料。アメリカ数学協会。pp。4–6。ISBN 978-0-88385-720-5。
  2. ^ 「GS1チェックディジット計算機」。GS1米国。2006年。2008年5月9日のオリジナルからアーカイブ。2008年5月21日取得。
  3. ^ 「ISBNユーザーズマニュアル」。国際ISBNエージェンシー。2005 。2008年5月21日取得。
  4. ^ 「チェックディジット計算機」。GS1。2005 。2008年5月21日取得。
  5. ^ 「GS1US公式サイトのチェックディジット計算機」。GS1US 。2012年8月9日取得。
  6. ^ https://metacpan.org/pod/distribution/Noid/noid#NOID-CHECK-DIGIT-ALGORITHM
  7. ^ David Bressoud、Stan Wagon、「計算数論」、2000年、Key College Publishing
  8. ^ http://openfigi.com
  9. ^ 「ユニークな身分証明書」。オタクガゼット。IEEE Student Branch（2011年秋）：16。2012-10-24のオリジナルからアーカイブ。 {{cite journal}}：（ヘルプ）の外部リンク|issue=
  10. ^ Chong-Yee Khoo博士（2014年1月20日）。「IPOSでのシンガポールIPアプリケーション番号の新しいフォーマット」。シンガポール特許ブログ。CantabIP 。2014年7月6日取得。

外部リンク

  • 識別番号とチェックディジットスキーム（さまざまなチェックディジットスキームの数学的説明）
  • UPC、EAN、およびSCC-14チェックディジット計算機
  • GS1チェックディジット計算機
Retrieved from "https://en.wikipedia.org/w/index.php?title=Check_digit&oldid=1070862792"
0.057374000549316