ヴェルホエフアルゴリズム

Verhoeffアルゴリズム[ ^1]は、 1969年にオランダの数学者Jacobus Verhoeffによって初めて発表されたエラー検出のためのチェックサムです。 ^{[2] [3]} これは、すべての単一桁エラーと、隣接する2桁を含むすべての転置エラーを検出する最初の10進チェックディジットアルゴリズムであり、^[4]当時はそのようなコードでは不可能であると考えられていました。

この方法は1985年にH.ピーター・ガムによって独立に発見され、この時には正式な証明と任意の基数への拡張が含まれていました。^[5]

ヴェルホフは、チェック数字が1桁の10進コードを見つけることを目標としていました。このコードでは、1桁のエラーと隣接する数字の入れ替わりがすべて検出されます。当時、このようなコードは存在しないという証明^{[6]があったため、} ISBNチェック数字などの11進コードが普及しました。

彼の目標は実際的なものでもあり、オランダの郵便システムのライブデータを基にして、さまざまな種類のエラーに加重ポイントシステムを使用して、さまざまなコードの評価を行いました。分析では、エラーをいくつかのカテゴリに分類しました。まず、エラーのある桁の数です。2桁のエラーがある場合、転置( ab → ba )、双子( aa → 'bb' )、ジャンプ転置( abc → cba )、表音( 1a → a0 )、ジャンプ双子( aba → cbc ) があります。さらに、数字の省略と追加があります。これらの種類のエラーの一部は頻度が低いかもしれませんが、すべてのシングルと転置を検出するという主な目標に加えて、一部のコードはそれらのエラーの影響を受けない可能性があります。

特に音声上の誤りは言語的影響を示しており、オランダ語では数字は通常ペアで読まれるため、またオランダ語では50は15に似ているが、80は18のようには聞こえない。

6桁の数字を例にとり、Verhoeff は次のようなエラーの分類を報告しました。

アルゴリズムの一般的な考え方は、各数字（0から9）を二面体群 の要素として表すことです。つまり、数字を にマッピングし、これを操作してから、数字にマッピングし直します。このマッピングを次のようにします。${\displaystyle D_{5}}$${\displaystyle D_{5}}$${\displaystyle m:[0,9]\to D_{5}}$

${\displaystyle m={\begin{pmatrix}0&1&2&3&4&5&6&7&8&9\\e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\end{pmatrix}}}$

n 番目の桁を とし、桁数を とします。 ${\displaystyle a_{n}}$${\displaystyle k}$

たとえば、コード 248 の場合、 は3 です。 ${\displaystyle k}$${\displaystyle a_{3}=m(8)=r^{3}s}$

順列を定義する${\displaystyle f:D_{5}\to D_{5}}$

${\displaystyle f={\begin{pmatrix}e&r&r^{2}&r^{3}&r^{4}&s&rs&r^{2}s&r^{3}s&r^{4}s\\r&s&r^{2}s&rs&r^{2}&r^{3}s&r^{3}&e&r^{4}s&r^{4}\end{pmatrix}}}$

例えば、もう一つの例は、${\displaystyle f(r^{3})=rs}$${\displaystyle f^{2}(r^{3})=r^{3}}$${\displaystyle f(f(r^{3}))=f(rs)=r^{3}}$

のグループ演算に乗法表記法を使用すると、チェックデジットは単純に次のような値になります。 ${\displaystyle D_{5}}$${\displaystyle c}$

${\displaystyle f(a_{1})\cdot f^{2}(a_{2})\cdot \ldots \cdot f^{k}(a_{k})\cdot f^{k+1}(c)=e}$

${\displaystyle c}$逆置換によって明示的に与えられる

${\displaystyle c=f^{-1-k}\left(\prod _{n=1}^{k}f^{n}(a_{n})^{-1}\right)}$

例えば、248のチェックデジットは5です。これを確認するには、マッピングを使用して、前の式のLHSに挿入します。 ${\displaystyle D_{5}}$

${\displaystyle f(r^{2})\cdot f^{2}(r^{4})\cdot f^{3}(r^{3}s)\cdot f^{4}(s)=e}$

この順列を素早く評価するには、

${\displaystyle f^{4}(s)=f^{3}(r^{3}s)=f^{2}(r^{4})=f(r^{2})=r^{2}s}$

それを得るために

${\displaystyle r^{2}s\cdot r^{2}s\cdot r^{2}s\cdot r^{2}s=e}$

これは同じ反射が繰り返して乗算されたものです。反射はそれ自体の逆数であることを利用してください。^[7]

${\displaystyle (r^{2}s\cdot r^{2}s)\cdot (r^{2}s\cdot r^{2}s)=e^{2}=e}$

実際には、このアルゴリズムは、基礎となるグループと順列理論からそれらのテーブルを生成する方法を理解する必要なしに、単純なルックアップテーブルを使用して実装されます。他の順列も機能するため、これはアルゴリズムのファミリーと見なされるのがより適切です。Verhoeff は、上記の特定の順列は、音声エラーの 95.3% を検出するという特性があるため、特別であると述べています。^[8]

このアルゴリズムの強みは、すべての翻字および転置エラーを検出し、さらにほとんどのツイン、ツインジャンプ、ジャンプ転置および音声エラーも検出できることです。

Verhoeff アルゴリズムの主な弱点は、その複雑さです。必要な計算は、たとえば の式として簡単に表現できません。計算を簡単にするには、ルックアップ テーブルが必要です。同様のコードにDamm アルゴリズムがあり、同様の性質を持っています。 ${\displaystyle {\displaystyle \mathbb {Z} /10\mathbb {Z} }}$

Verhoeff アルゴリズムは、乗算表d、逆表inv、順列表pの 3 つの表を使用して実装できます。

最初の表dは、二面体群D ₅ . ^[7]の乗法に基づいており、単に群のケイリー表です。この群は可換ではないことに注意してください。つまり、 jとkの値によっては、d ( j , k ) ≠ d ( k , j )となります。

逆数表inv は数字の逆数、つまりd ( j , inv ( j )) = 0 を満たす値を表します。

順列表pは、数字の位置に基づいて各桁に順列を適用します。これは実際には、単一の順列(1 5 8 9 4 2 7 0)(3 6)が繰り返し適用されたものです。つまり、p ( i + j , n ) = p ( i , p ( j , n ))です。

Verhoeff チェックサム計算は次のように実行されます。

1. 右から左に取得した数値の個々の桁から配列nを作成します (右端の桁はn ₀など)。
2. チェックサムc をゼロに初期化します。
3. 配列 n の各インデックスiについて、 0 から始めて、c を⁠ ⁠${\displaystyle d(c,p(i{\bmod {8}},n_{i}))}$に置き換えます。

元の番号は、 ⁠ ⁠${\displaystyle c=0}$の場合にのみ有効です。

チェックデジットを生成するには、0 の場合、計算を実行します。正しいチェック ディジットは⁠ ⁠${\displaystyle inv(c)}$です。

• Luhnアルゴリズム、以前の（1960年）チェックディジットアルゴリズム

Wikibooks には、次のトピックに関する書籍があります: Algorithm_Implementation/Checksums/Verhoeff_Algorithm

• Verhoeffアルゴリズムの詳細な説明