Dammアルゴリズム
ウィキペディアから無料の百科事典
Dammアルゴリズムは、誤り検出の一種であるチェックディジットのアルゴリズムであり、全ての1桁入力誤りと全ての隣り合う2桁の入れ替え誤りを検出することができる。2004年にH. Michael Dammによって発表された[1]。
利点と欠点[編集]
Dammアルゴリズムは、Verhoeffアルゴリズムと同様に、最も頻繁に起こる2種類の誤り、すなわち1桁の入力誤りと、（末尾に付け足されたチェックディジットとその直前の数字の入れ値替えを含む）隣り合う2桁の入れ違えの、2種類の誤りを検出できる[1][2]。しかしDammアルゴリズムは、Verhoeffアルゴリズムと異なり、実行に際し、専用に構成された置換表と位置に応じた冪乗表を必要としない。さらに、逆元の表も演算表の主対角成分が0の時は必要ない。
Dammアルゴリズムは10種を超えるチェックディジットを出力しないため、（ISBN10のチェックディジットにおける'X'のような）数字以外の文字をチェックディジットとして用意する必要がない。
チェック対象の数字列の先頭に0をいくつ付け加えても、チェックディジットには影響しない[1]。
英語の聞き取り間違いによる入力間違い (13←→30, 14←→40, …, 19←→90) を全て検出できる全反対称準群 (totally anti-symmetric quasigroups) が存在する。後述の例においてはそのような性質を満たす表のうちの1つを用いている。
このように、類似のチェックディジットアルゴリズムが利用される場面においてより優れた特徴があるにもかかわらず、Dammアルゴリズムは広く知られてはおらず、また利用例もほとんどない。
デザイン[編集]
Dammアルゴリズムの根幹をなすものは位数10の準群 (quasigroup)（例: 10×10のラテン方格を乗積表として用いる）である。この準群は弱い全反対称性 (weakly totally anti-symmetric) という特徴を持つ[3][4][i][ii][iii]。Dammは位数10の全反対称性準群を作成するいくつかの方法を発見し、いくつかの作成例を彼の博士論文に示した[3][i]。また、これにより位数10の全反対称準群は存在しないとする論に対する反例を示した[5]。
準群 (Q, *) は全ての c, x, y ∈ Q において、以下の2つの性質を満たす時全反対称と呼ばれる[4]。
- (c ∗ x) ∗ y = (c ∗ y) ∗ x ⇒ x = y
- x ∗ y = y ∗ x ⇒ x = y,
また、上記の内1.だけの性質を満たす時は弱い全反対称と呼ばれる。Dammは位数nにおいて弱い全反対称準群が存在することと、同じ位数nに全反対称準群が存在することが同値であることを証明した。Dammアルゴリズムの検査式 (…((0 ∗ xm) ∗ xm−1) ∗ …) ∗ x0 = 0 を満たすために、使用する弱い全反対称準群は x * x = 0 の性質を満たす必要がある。このような準群は任意の全反対称準群から、0が主対角線上に並ぶように列を入れ替えることで作成できる。また逆に、任意の弱い全反対称準群から、最初の行が自然順になるように列を入れ替える事で全反対称準群を作成できる[3]。
アルゴリズム[編集]
チェックディジットを含む数字列の正当性は準群の上で定義される。Dammの博士論文（98, 106, 111ページ）に、利用可能な準群の表が用意されている[3]。チェックディジットの計算を簡潔にするため、主対角線に位置する要素が0であると良い[1]。
チェックディジットを含む場合の正当性検査[編集]
- 仮変数を用意し、0で初期化する。
- 数字列を順に1桁ずつ処理していく: 処理中の数字を列番号、仮変数を行番号とした時の表の要素を新しい仮変数の値として置き換える。
- 数字列を全て処理し終えた時、仮変数が0である時のみ数字列は正当である[1]。
チェックディジットの計算方法[編集]
前提条件: 表の主対角要素のエントリは全て0である
- 仮変数を用意し、0で初期化する。
- 数字列を順に1桁ずつ処理していく: 処理中の数字を列番号、仮変数を行番号とした時の表の要素を新しい仮変数の値として置き換える。
- 数字列を全て処理し終えた時の仮変数の値がチェックディジットなので、数字列の最後に付け加える[1]。
例[編集]
以下に示す表を使用する[1]。これはDammの博士論文の111ページにある全反対称準群[3]の列を入れ替え、対応する要素を変更したものである。
| 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 |
数字列として 572 を例に取る。
チェックディジットの計算[編集]
| 処理される数字 → 列番号 | 5 | 7 | 2 |
|---|---|---|---|
| 元の仮変数 → 行番号 | 0 | 9 | 7 |
| 表の要素 → 新しい仮変数 | 9 | 7 | 4 |
結果として仮変数の値 4 が得られる。これが計算されたチェックディジットである。これを最後に付け加えて数字列 5724 を得る。
チェックディジットを含む数字列の正当性を検査する[編集]
| 処理される数字 → 列番号 | 5 | 7 | 2 | 4 |
|---|---|---|---|---|
| 元の仮変数 → 行番号 | 0 | 9 | 7 | 4 |
| 表の要素 → 新しい仮変数 | 9 | 7 | 4 | 0 |
結果、仮変数値は 0 となった。よってこの数字列は正当である。
図解[編集]
以下は上記のチェックディジット（青い破線）を計算する方法の詳細と、数字列 572 にチェックディジットを加えた数列の正当性検査を図解したものである。
参考文献[編集]
- ^ a b c d e f g Fenwick, Peter (2014). “Checksums and Error Control”. Introduction to Computer Data Representation. Bentham Science Publishers. pp. 191–218. doi:10.2174/9781608058822114010013. ISBN 978-1-60805-883-9
- ^ For the types of common errors and their frequencies, see Salomon, David (2005). Coding for Data and Computer Communications. Springer Science+Business Media, Inc.. pp. 36. ISBN 978-0387-21245-6
- ^ a b c d e Damm, H. Michael (2004) (ドイツ語). Total anti-symmetrische Quasigruppen (Dr. rer. nat.). Philipps-Universität Marburg. urn:nbn:de:hebis:04-z2004-05162
- ^ a b Damm, H. Michael (2007). “Totally anti-symmetric quasigroups for all orders n≠2,6”. Discrete Mathematics 307 (6): 715–729. doi:10.1016/j.disc.2006.05.033. ISSN 0012-365X.
- ^ Damm, H. Michael (2003). “On the Existence of Totally Anti-Symmetric Quasigroups of Order 4k + 2”. Computing 70 (4): 349–357. doi:10.1007/s00607-003-0017-3. ISSN 0010-485X.
- ^ a b Beliavscaia Galina; Izbaş Vladimir; Şcerbacov Victor (2003). “Check character systems over quasigroups and loops”. Quasigroups and Related Systems 10 (1): 1–28. ISSN 1561-2848. See page 23.
- ^ Chen Jiannan (2009). “The NP-completeness of Completing Partial anti-symmetric Latin squares”. Proceedings of 2009 International Workshop on Information Security and Application (IWISA 2009). Academy Publisher. pp. 322–324. ISBN 978-952-5726-06-0 See page 324.
- ^ Mileva, A.; Dimitrova, V. (2009). “Quasigroups constructed from complete mappings of a group (Z2n,⊕)”. Contributions, Sec. Math. Tech. Sci., MANU/MASA (Skopje: Macedonian Academy of Sciences and Arts) XXX (1-2): 75–93. ISSN 0351-3246. See page 78.
