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

Way to detect errors in decimal codes

ヴェルホフアルゴリズム^[1]は、1969年にオランダの数学者ヤコブス・ヴェルホフによって初めて発表されたエラー検出のためのチェックサムです。 ^{[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 は次のようなエラーの分類を報告しました。

数字が間違っています	分類	カウント	頻度
1	転写	9,574	79.05%
2	転置	1,237	10.21%
	双子	67	0.55%
	音声	59	0.49%
	その他の隣接	232	1.92%
	ジャンプ転置	99	0.82%
	ジャンプツインズ	35	0.29%
	その他のジャンプエラー	43	0.36%
	他の	98	0.81%
3		169	1.40%
4		118	0.97%
5		219	1.81%
6		162	1.34%
合計		12,112

説明

このアルゴリズムの基本的な考え方は、各数字（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}$

たとえば、コード 942 の場合、は 3 および です。 ${\displaystyle k}$ ${\displaystyle a_{3}=m(2)=r^{2}}$

順列を定義する ${\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^{0}(c)\cdot f^{1}(a_{k})\cdot \ldots \cdot f^{k-1}(a_{2})\cdot f^{k}(a_{1})=e}$

${\displaystyle c}$は乗法逆数によって明示的に与えられる：

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

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

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

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

${\displaystyle f^{3}(r^{4}s)=f^{2}(r^{4})=f^{1}(r^{2})=f^{0}(r^{2}s)=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 つの表を使用して実装できます。

⁠ ⁠ ${\displaystyle d(j,k)}$[9] け 0 1 2 3 4 5 6 7 8 9 j 0 0 1 2 3 4 5 6 7 8 9 1 1 2 3 4 0 6 7 8 9 5 2 2 3 4 0 1 7 8 9 5 6 3 3 4 0 1 2 8 9 5 6 7 4 4 0 1 2 3 9 5 6 7 8 5 5 9 8 7 6 0 4 3 2 1 6 6 5 9 8 7 1 0 4 3 2 7 7 6 5 9 8 2 1 0 4 3 8 8 7 6 5 9 3 2 1 0 4 9 9 8 7 6 5 4 3 2 1 0

j ⁠ ⁠ ${\displaystyle inv(j)}$ 0 0 1 4 2 3 3 2 4 1 5 5 6 6 7 7 8 8 9 9

⁠ ⁠ ${\displaystyle p(pos,num)}$ 番号 0 1 2 3 4 5 6 7 8 9 正（8を法とする） 0 0 1 2 3 4 5 6 7 8 9 1 1 5 7 6 2 8 3 0 9 4 2 5 8 0 3 7 9 6 1 4 2 3 8 9 1 6 0 4 3 5 2 7 4 9 4 5 3 1 2 6 8 7 0 5 4 2 8 6 5 7 3 9 0 1 6 2 7 9 3 8 0 6 4 1 5 7 7 0 4 6 9 1 3 2 5 8

最初の表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)}$ .. です。

例

236のチェックディジットを生成します: 私 に私 p ( i,n i ) c 0 0 0 0 1 6 3 3 2 3 3 1 3 2 1 2 cは2なので、チェックディジットはinv（2）で3になります。

チェックディジット2363を検証します。 私 に私 p ( i,n i ) c 0 3 3 3 1 6 3 1 2 3 3 4 3 2 1 0 cはゼロなので、チェックは正しいです。

用途

Verhoeff アルゴリズムは、次のようなさまざまなシステムで使用されます。

• ドイツの ドイツマルク紙幣^[10]
• インドの Aadhaar番号^[11]
• アイルランドメーター登録システムオペレーター^[12]
• SNOMED臨床用語辞書^[13]

参照

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

参考文献

1. Verhoeff、J. (1969)。 「10 進数コードのエラー検出 (Tract 29)」。数学と機械に関する知識。51 (3)。アムステルダム数学センター: 240。ビブコード:1971ZaMM...51..240N。土井：10.1002/zamm.19710510323。
2. カートランド、ジョセフ(2001). 「5. 群論とヴェルホエフ・チェックディジット・スキーム」.識別番号とチェックディジット・スキーム. アメリカ数学会. p. 153. ISBN 0-88385-720-0。
3. サロモン、デイビッド (2005). 「§2.11 Verhoeff チェックディジット法」.データとコンピュータ通信の符号化. シュプリンガー. pp.  56– 58. ISBN 0-387-21245-0。
4. ハウンスパーガー、ディアナ、ケネディ、スティーブン編 (2006). 『宇宙の果て：Math Horizo​​ns 10周年記念』アメリカ数学会. p. 38. ISBN 978-0-88385-555-3。LCCN  2005937266。
5. Gumm, H. (1985年1月). 「任意数システムのための新しいチェックディジット法（対応）」. IEEE Transactions on Information Theory . 31 (1): 102– 105. doi :10.1109/TIT.1985.1056991.
6. シッソン、ロジャー・L. (1958年5月). 「改良された10進冗長検査」. Communications of the ACM . 1 (5): 10–12 . doi : 10.1145/368819.368854 .
7. ガリアン、ジョセフ A. (2010)。現代抽象代数(第 7 版)。ブルックス/コール。 p. 111.ISBN​ 978-0-547-16509-7. LCCN  2008940386 . 2011年8月26日閲覧. verhoeffチェックディジット。
8. ヴェルホエフ 1969, 95ページ
9. ヴェルホエフ 1969, 83ページ
10. 「EIMI 2010 Proceedings」（PDF） .フロイデンタール研究所、ユトレヒト大学. リスボン、ポルトガル：数学と産業の教育インターフェース. 2010. p. 128. doi :10.1007/978-3-319-02270-3. 2024年5月16日時点のオリジナル（PDF）からアーカイブ。 2025年9月13日閲覧。
11. Surelia, Vipin. 「Aadhaar関連アプリケーションのための銀行によるVerhoeffアルゴリズムの実装」（PDF）npci.org.in . National Payments Corporation of India. p. 1. 2025年9月10日時点のオリジナル（Official Circular）からのアーカイブ。 2025年9月10日閲覧。
12. “Meter Point Reference Number (MPRN)”. mrso.ie . アイルランドのメーター登録システムオペレーター。2025年9月13日時点のオリジナルよりアーカイブ。 2025年9月13日閲覧。
13. 「チェックディジット計算」. docs.snomed.org . SNOMED International. オリジナル（公式文書）から2025年9月13日時点のアーカイブ。 2025年9月13日閲覧。

外部リンク

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

Retrieved from "https://en.wikipedia.org/w/index.php?title=Verhoeff_algorithm&oldid=1312266324"