ダムアルゴリズム

エラー検出において、Dammアルゴリズムは、すべての1桁のエラーとすべての隣接転置エラーを検出するチェックデジットアルゴリズムです。これは、H. Michael Dammが2004年に発表したもので、 ^{[ 1 ]}彼の博士論文「完全反対称準群」の一部として発表されました。

その本質的な部分は、弱完全反対称であるという特別な特徴を持つ位数10の準群(すなわち、演算表の本体として10 × 10ラテン方陣を持つ) である。^{[ 3 ] [ 4 ] [ i ] [ ii ] [ iii ]}ダムは、位数 10 の完全反対称準群を作成するいくつかの方法を明らかにし、博士論文でいくつかの例を示した。^{[ 3 ] [ i ]}これにより、ダムは位数 10 の完全反対称準群は存在しないという古い予想も否定した。^{[ 5 ]}

準群( Q , ∗)は、すべてのc , x , y ∈ Qに対して次の含意が成り立つ場合、完全に反対称であると呼ばれる。 ^{[ 4 ]}

1. ( c ∗ x ) ∗ y = ( c ∗ y ) ∗ x ⇒ x = y
2. x ∗ y = y ∗ x ⇒ x = y、

そして、最初の含意のみが成り立つ場合、それは弱完全反対称と呼ばれます。Damm は、n位の完全反対称準群の存在は、 n位の弱完全反対称準群の存在と同等であることを証明しました。チェック方程式 (...((0 ∗ x _m ) ∗ x _{m −1} ) ∗ ...) ∗ x ₀ = 0を用いた Damm アルゴリズムでは、 x ∗ x = 0の性質を持つ弱完全反対称準群が 必要です。このような準群は、すべてのゼロが対角線上に位置するように列を並べ替えることによって、任意の完全反対称準群から構築できます。また、一方で、最初の行が自然な順序になるように列を並べ替えることによって、任意の弱完全反対称準群から完全反対称準群を構築できます。^{[ 3 ]}

チェックデジットを含む数字列の有効性は準群上で定義されます。すぐに使用できる準群表は、Damm の博士論文 (98、106、111 ページ) から入手できます。^{[ 3 ]}各主対角要素が0 である場合、^{[ 1 ]}チェックデジットの計算が簡略化されるため便利です。

以下の演算表を使用します。^{[ 1 ]}これは、Dammの博士論文111ページ^{[ 3 ]}にある完全反対称準群x ∗ yから、行を並べ替え、エントリを置換φ = (1 2 9 5 4 8 6 7 3)に変更し、 x ⋅ y = φ ^{− 1} ( φ ( x ) ∗ y )と定義することによって得られます。        

572という数字（数字列）を選んだとしましょう。

• 複数のプログラミング言語で記述されたDAMM検証および生成コード
• シンガポールにおける実用的応用
• ダムアルゴリズムの準群（64次まで）
• RosettaCode.orgでは、Dammアルゴリズムの多くのプログラミング言語での実装が提供されています。