Clever Geek Handbook

桁ダム

KDPV 多くの場合、チェックディジットは、後でエラーを検出できるように、エラーを記録または送信できる識別子に追加されます。



例には、 クレジットカード番号の最後の桁、米国で販売された車のVINの 9番目の桁、またはISBNの最後の桁が含まれます。



Van Dammeのチェックディジットアルゴリズムは比較的新しいため、ほとんど知られていません。 2004年に公開されました。



このアルゴリズムは、1桁のすべてのエラーと、隣接する数字のすべての単一の順列を検出します。 これは、Verhuffアルゴリズムよりも著しく単純で、機能が同等であり、特殊文字（10桁のISBNのXなど）を使用する必要がありません。




このアルゴリズムは、完全に反対称な準グループに基づいています。 以下は順序10の1つの例です。Dammの論文[1]の前は、そのような準グループは存在しないと考えられていました。



準グループは、とりわけ、英語特有の音声エラーの最大数（30ではなく13など）を決定するように選択されます。

中間桁 入力桁
0 1 2 3 4 5 6 7 8 9
0 0 3 1 7 5 9 8 6 4 2
1 7 0 9 2 1 5 4 8 6 3
2 4 2 0 6 8 7 1 3 5 9
3 1 7 5 0 9 8 3 4 2 6
4 6 1 2 3 0 4 5 9 7 8
5 3 6 7 4 2 0 9 5 8 1
6 5 8 6 9 7 2 0 1 3 4
7 8 9 4 5 3 6 2 0 1 7
8 9 4 3 8 6 1 7 2 0 5
9 2 5 8 1 4 3 6 7 9 0


アルゴリズムは、準グループに加えて、ゼロに初期化された1つの中間桁を使用し、基本的に1つの割り当て操作interim_digit_ = quasigroup[interim_digit_][digit]



のみで構成されます。



チェックディジットの例



572のシーケンスのチェックディジットを計算する必要があるとします。



  1. 中間桁を値0で初期化します。
  2. 列5（これは入力シーケンスの最初の桁）と行0（これは中間桁の値）に番号があります。 そこで9.この値を中間の数字に割り当てます。
  3. 列7（これは入力シーケンスの2桁目）と行9（これは中間桁の値です）に番号があります。 そこで7.この値を中間の数字に割り当てます。
  4. 列2（これは入力シーケンスの3桁目）と行7（これは中間桁の値）に番号があります。 そこで4.この値を中間桁に割り当てます。
  5. 入力シーケンスが終了しました。 中間桁の最後の値（4）は制御桁です。 シーケンスの最後に追加して5724を取得します。




チェックディジットの例



番号5724のシーケンスを確認します。 エラーがない場合、チェックディジットは0である必要があります。



  1. 中間桁を値0で初期化します。
  2. 列5（これは入力シーケンスの最初の桁）と行0（これは中間桁の値）に番号があります。 そこで9.この値を中間の数字に割り当てます。
  3. 列7（これは入力シーケンスの2桁目）と行9（これは中間桁の値です）に番号があります。 そこで7.この値を中間の数字に割り当てます。
  4. 列2（これは入力シーケンスの3桁目）と行7（これは中間桁の値）に番号があります。 そこで4.この値を中間桁に割り当てます。
  5. 列4（これは入力シーケンスの4番目の桁）と行4（これは中間桁の値です）に番号があります。 0。この値を中間桁に割り当てます。
  6. 入力シーケンスが終了しました。 中間桁の最後の値は、予想どおり0です。


完全なソースコード 



 #include <iostream> #include <cassert> class Damm { public: Damm() : interim_digit_(0) {} void push(int digit) { static const int quasigroup[10][10] = { {0, 3, 1, 7, 5, 9, 8, 6, 4, 2}, {7, 0, 9, 2, 1, 5, 4, 8, 6, 3}, {4, 2, 0, 6, 8, 7, 1, 3, 5, 9}, {1, 7, 5, 0, 9, 8, 3, 4, 2, 6}, {6, 1, 2, 3, 0, 4, 5, 9, 7, 8}, {3, 6, 7, 4, 2, 0, 9, 5, 8, 1}, {5, 8, 6, 9, 7, 2, 0, 1, 3, 4}, {8, 9, 4, 5, 3, 6, 2, 0, 1, 7}, {9, 4, 3, 8, 6, 1, 7, 2, 0, 5}, {2, 5, 8, 1, 4, 3, 6, 7, 9, 0} }; assert(digit >= 0); assert(digit <= 9); interim_digit_ = quasigroup[interim_digit_][digit]; } int check_digit(void) const { return interim_digit_; } void clear(void) { interim_digit_ = 0; } private: int interim_digit_; }; int main(void) { Damm d; d.push(5); d.push(7); d.push(2); int check_digit = d.check_digit(); std::cout << "Check digit (572) = " << check_digit << ", expected 4\n"; d.clear(); d.push(5); d.push(7); d.push(2); d.push(4); check_digit = d.check_digit(); std::cout << "Check digit (5724) = " << check_digit << ", expected 0\n"; return 0; }


ソースへのリンク



[1] Damm、H. Michael Total反対称的準集団 PDF


More articles:


All Articles