投稿日時：2024/03/01 08:04

最終更新日時：2024/03/07 18:59

チェックディジットについて考える

はじめに

　何かしらのコード（例えばJANコードなど）では末尾に1桁のチェックディジットを付加して誤り検出を行うことがしばしば見られる。チェックディジットの目的としては、手入力などによる入力ミスによる誤り検出である。最も起きる確率の大きい誤りは1文字の誤りであるため、一般に1文字の誤り検出は必要だろう。チェックディジットな存在しない場合、他の入力ミスのパターンとしては、連番で付番されるようなコードであれば次の入力値の入力してしまう（コードが199であれば次のコードである200を入力するなど）ことや、入力値の入れ替え、入力値を連続して入力してしまい特定の桁の入力をスキップする（コードが1234のところを1224と入力してしまうなど）、キーボードの配列による入力ミスなどが挙げられる。
　あらゆる誤り検出を行おうとすると十分な冗長性が必要になるが、そこまで高性能なものを求めてはいないのか、よく見られるチェックディジットは1桁のものである。今回はそのような1桁のチェックディジットについて、多分こんなものだろうという程度の理解のために色々と考えてみる。

チェックディジットの理論

　 $n$ 進数列 $d_{m}\cdots d_{1}$ を与える。これをにチェックディジット $x$ を加えて表現される列 $d=d_{m}\cdots d_{1}0+x$ で誤り検出を行うことを考える。なお、この列を10進数で表現したときは以下のようになる。

d=\sum_{k=1}^{m}d_{k}n^{k}+x

　このモデルを基に、今回はメインとして剰余に基づくチェックディジットについて考えてみる。この節の最後には剰余を利用しない別のアプローチによるチェックディジットの理論について簡単に展開をしてみる。

1桁の誤り検出

　まずは、1桁の誤り検出について考えてみる。1桁の誤りが検出できるとは、誤りが生じた桁を $i$ で0ではない雑音 $e(0\leq d_{i}+e<n)$ として、各桁の組 $(Z_{n})^{m+1}=\{0,\cdots,n-1\}^{m+1}$ から判定用の集合 $A$ への写像 $f:(Z_{n})^{m+1}\to A$ で

f(d)\neq f(d+en^{i})

が任意の $d$ および $i$ 、 $0\leq d_{i}+e<n$ を満たす $e$ について成り立つというものである。
　これの構成の1つはパリティ符号の考え方を拡張すれば容易に構築することができる。パリティ符号では、ビットの各桁の和が偶数であるときに0をパリティビットとして付与するというものであるが、これを $n=2$ の場合と考え、一般の $n$ について構成しなおせば、

[x]=-\sum_{k=1}^{m}[d_{k}]\in {\mathbb Z}/s{\mathbb Z}

により与えられる $0\leq x<s$ を満たす $x$ をチェックディジットとして採用するというものである( $[x]$ は代表元 $x$ をもつ ${\mathbb Z}$ 上での $s$ による剰余による同値類)。なお、 $s\geq n$ を満たすものとする。 $n=s=2$ の場合を考えればパリティ符号と同値になることがわかるだろう。
　では、実際に1桁の誤り検出が可能であることを示そう。 $f$ を単純に各桁の和を取り、 $s$ による剰余を取ることを考えると、 $x$ の構成より以下を満たす。

f(d)=[0]\in{\mathbb Z}/s{\mathbb Z}

　 $f$ は明らかに準同型のため、

f(d+en^{i})=[e]\in{\mathbb Z}/s{\mathbb Z}

となり、仮定より $e\neq 0$ かつ $-d_{i}\leq e<n$ 、すなわち $e\neq 0$ かつ $|e|<s$ を満たすため、常に $f(d)\neq f(d+en^{i})$ を満たす。 $s$ は $n\leq s$ を満たせば十分であるが、 $n<s$ のときはチェックディジットだけ $s$ 進数となる。

1桁の誤り検出の一般化

　1桁のチェックディジットにより1桁の誤りを検出できることを示したが、これではこれ以外の誤りの検出ができないため、多少の自由が欲しい。そこで、 $f$ を準同型と仮定して拡張をしてみる。まず、 $f$ が準同型のため、 $[w_{k}]=f(n^{k})\in A={\mathbb Z}/s{\mathbb Z}$ とすれば

f(d-x)=\sum_{k=1}^{m}d_{k}f(n^{k})=\sum_{k=1}^{m}d_{k}[w_{k}]

と記述できる。ここから、自然に $w_{k}\in{\mathbb Z}$ として

[x]=-\sum_{k=1}^{m}[d_{k}w_{k}]\in {\mathbb Z}/s{\mathbb Z}

と与えたとすると、上記の議論と同様にチェックディジット $x$ が得られる。ただし、

f(d+en^{i})=[e][w_{i}]=[ew_{i}]

を考えると、 $[ew_{i}]\neq[0]$ である必要があるため、任意の $0<e<n$ について $ew_{i}$ が0または $s$ の倍数ではない、すなわち $w_{i}$ は0でないかつ $w_{i}$ と $s$ が互いに素であることが必要十分である。
　また、議論においては $f$ は準同型としたが、例えばコードの整数表現 ${d\in{\mathbb Z}}$ で考えれば、事前に $d$ について可逆な写像 $g:{\mathbb Z}\to(Z_{n})^{m+1}$ を用いてコードを変換(例えばコードの各桁を並べ替えるなど)をして、 $f\circ g$ を用いてもいいだろう。

2桁の誤りの検出

　誤りが生じた桁をそれぞれ $i,j$ 、それぞれの桁に対応する0でない雑音 $e_{i}(0\leq d_{i}+e<n),e_{j}(0\leq d_{j}+e<n)$ を考えると、1桁の誤り検出の場合と同様にして

f(d+e_{i}n^{i}++e_{j}n^{j})=[e_{i}w_{i}+e_{j}w_{j}]

が得られるが、一般に $e_{i}w_{i}+e_{j}w_{j}\neq 0$ にすることはできない。しかしながら、ある一定の条件を設けることで検出可能な場合もある。

同じ誤りの検出

　この誤りは、例えば $11$ と連続した同じ2桁を $22$ のように同じ2桁で誤った場合などのものである。この検出においては、 $e_{i}=e_{j}$ となるため、 $w_{i}+w_{j}$ が $s$ と互いに素となるように $w_{k}$ を選べばよいことがわかる。
　しかしながら、この制約は意外にも厳しい。例えば、1桁の誤り検出が可能かつ10進数値を扱う場合、 $s=10$ として考えると1桁の誤り検出が可能な条件下では $w_{k}$ は $1,3,7,9$ が有効である。これらはすべて奇数であるため、 $w_{i}+w_{j}$ は偶数となり、常に $s$ と互いに素ではない。つまり、どのように $w_{k}$ を選択しても $i,j$ に対して $e_{i}=e_{j}=5$ のときに誤りを検知することができない(つまり、10%の確率で検出不可)。これの大きな原因としては10は2を素因数にもつことにある。

桁の入れ替わりの検出

　まずは桁の入れ替わりを定式化する。入れ替わる桁をそれぞれ $i,j$ としたとき、 $d$ の $i$ 桁目と $j$ 桁目を入れ替えたものを $d_{i,j}$ とする。このとき、 $d_{i,j}$ は以下のように表現される。

d_{i,j}=\sum_{k=1,k\neq i,k\neq j}^{m}d_{k}n^{k}+d_{i}n^{j}+d_{j}n^{i}+x

　これを基に、1桁の誤りの検出の可能な $f$ を適用することを考えると

\begin{aligned}f(d_{i,j})=&f(d-(d_{i}n^{i}+d_{j}n^{j})+(d_{i}n^{j}+d_{j}n^{i})) \\=&-(d_{i}[w_{i}]+d_{j}[w_{j}])+(d_{i}[w_{j}]+d_{j}[w_{i}]) \\=&[(d_{j}-d_{i})(w_{i}-w_{j})]\end{aligned}

となり、桁の入れ替わりの仮定より $d_{i}\neq d_{j}$ としてもよいため、 $w_{i}\neq w_{j}$ かつ $w_{i}-w_{j}$ が $s$ と互いに素となるように $w_{1},\cdots,w_{m}$ を選択すれば、任意の位置の桁の入れ替わりの検出が可能である。しかし、 $0\leq w_{k}<s$ を満たす必要があるため、任意の桁の入れ替えの検出は現実的には利用されない( $s$ に素数を選択して可能な限り検出できるようにするというのはある)。
　しかしながら、この制約は上記でも述べたように意外にも厳しい。1桁の誤り検出が可能かつ10進数値を扱う場合、 $s=10$ として考えると1桁の誤り検出が可能な条件下では $w_{i}+w_{j}$ は偶数となり、常に $s$ と互いに素ではない。つまり、どのように $w_{k}$ を選択しても $i,j$ に対する桁の入れ替わりにおいて検出不可な $d_{i},d_{j}$ の組み合わせ( $[d_{j}-d_{i}]=[5]$ を満たす組み合わせ)が存在することとなる(つまり、約10%の確率で検出不可)。

剰余を利用しない検出手法(おまけ)

　これまででは、剰余に基づくチェックディジットの与え方を示したが、ほかの与え方も存在する。基本となるのはパリティ符号ではあるが、ビットの各桁の和を考えるのではなく、ビットの状態を保持しておいて逐次的に検査対象のビットを走査して、1のビットが出現したら保持しているビットを反転するという操作を繰り返した結果をパリティビットとして付与するというものがある。つまるところ、ビット列に対してであれば全ての検査対象のビットについてxorすればいい。

\bigoplus_{k=1}^{m}d_{k}=x \ \Rightarrow\ \bigoplus_{k=1}^{m}d_{k}\oplus x=0

　これを漸化式により記述すると以下のようになり、 $c(x_{k-1},d_{k})=x_{k-1}\oplus d_{k}$ のため $x=x_{m}$ のようにチェックディジットも得られる。

\begin{dcases}x_{0}=0 & (k=0) \\x_{k}=c(x_{k-1},d_{k}) & (k\neq m) \\x_{m+1}=c(x_{m},x)=0 & (k=m)\end{dcases}

　これを任意の $n$ 進数列 $d_{m}\cdots d_{1}$ に対して適用するときは、 $c$ についての $c:Z_{n}\times Z_{n}\to Z_{s}$ な対応表を定義することでチェックディジットを計算できる。最初の1桁の誤り検出の時に示したチェックディジットの計算式

\sum_{k=1}^{m}[d_{k}]+[x]=[0] \in {\mathbb Z}/s{\mathbb Z}

に対応する $c$ は以下のような巡回置換により与えられる。

c(a,b)=\begin{pmatrix}0 & \cdots & s-1\end{pmatrix}^{a}(b)

　この巡回置換に着目して、整数だけでなく、もう少し代数的に扱ってみる。まず、 $c$ を2項演算とした単準同型写像 $h:(Z_{n},c)^{m+1}\to (G,\cdot)^{m+1}$ を与え、 $G$ の元をそれぞれ $g_{1},\cdots g_{s}$ とする。このとき、 $G$ は明らかに群である。チェックディジットの計算式は、 $h_{k}=h(d_{k})$ 、 $G$ 上の単位元を $g_{0}$ としたとき以下を満たす $x$ で与えられる。

\prod_{k=1}^{m}h_{k}h(x)=g_{0}

　これを $x$ について解くと

x=h^{-1}\left(\left(\prod_{k=1}^{m}h_{k}\right)^{-1}g_{0}\right)

となるため、 $G$ 上で考えたとしても $x$ の存在と一意性は保証される。
　 $G$ 上で1桁の誤りの検出を考えると $(Z_{n},c)$ における演算は単一の巡回置換の作用のため、1桁の誤りは巡回置換の長さの範囲、すなわち任意の $Z_{n}$ の元で誤りの検出が可能であることが直ちにわかる。逆に、 $(Z_{n},c)$ における演算を仮定せず、 $G$ が群であることのみを仮定して考えてみる。 $h_{m+1}=h(x)$ として、 $h_{t}$ を $h'_{t}$ へ誤ったとする。 $h_{\rm left}=\prod_{k=1}^{t-1}h_{k}$ 、 $h_{\rm right}=\prod_{k=t+1}^{m+1}h_{k}$ のようにおくと、

\begin{dcases}h_{\rm left}h'_{t}h_{\rm right}=g'_{0} \\h_{\rm left}h_{t}h_{\rm right}=g_{0}\end{dcases}

のような2つの関係式(2つ目は単なるチェックディジットの定義式)が与えられる。このとき、常に $g_{0}\neq g_{0}'$ となれば常に1桁の誤りの検出が可能といえる。これらの式を整理すると、以下の2つの関係式が得られ、 $h'_{t}h_{t}^{-1}$ および $h_{t}^{-1}h'_{t}$ 、 $g'_{0}$ は共役であることがわかる。

\begin{dcases}h_{\rm left}(h'_{t}h_{t}^{-1})h_{\rm left}^{-1}=g'_{0} \\h_{\rm right}^{-1}(h_{t}^{-1}h'_{t})h_{\rm right}=g'_{0}\end{dcases}

　以上より、1桁の誤りが検出であるということを言い換えると、以下が成り立つことであるが、これは対偶を取ることで真であることが直ちに分かる。

h'_{t}h_{t}^{-1}\neq g_{0}\ \Leftrightarrow\ g'_{0}\neq g_{0}

　つまり、 $(Z_{n})^{m}$ の各桁に対して単射 $(Z_{n})^{m}\to G^{m}$ を与え、 $G$ が群を成すならば $G$ 上の演算により生成されたチェックディジットでは1桁の誤りの検出が可能といえる。
　最後に隣接する2桁の入れ替えを検出する群について示そう。桁の入れ替えが $t$ 桁目と $t+1$ 桁目で発生したと考えると、上記と同様の議論により、誤りの検出が可能であることは

h_{t}h_{t+1}(h_{t+1}h_{t})^{-1}\neq g_{0}\ \Leftrightarrow\ g'_{0}\neq g_{0}

を満たすことであるが、これを満たすには $G$ の元で $h_{t}h_{t+1}\neq h_{t+1}h_{t}$ を満たす必要がある。つまり、群 $G$ が中心を持たないならば、 $G$ 上の演算により生成されたチェックディジットでは隣接する2桁の入れ替えの検出が可能といえる。

具体例

　ここからは社会で用いられているいくつかのチェックディジットを紹介してみる。

JANコード

　JANコードのチェックディジットの計算方法は以下で紹介されている。

チェックデジットの計算方法 | GS1事業者コード・GTIN（JANコード） | 各種コード登録・概要 | GS1 Japan 一般財団法人流通システム開発センター

　この検査で用いているチェックディジットの計算は、12桁の10進数数値から剰余に基づく方法で $s=10$ 、

\{w_{1},\cdots,w_{12}\}=\{1,3,1,3,1,3,1,3,1,3,1,3\}

を用いて計算をしているものである。つまり、JANコードのチェックディジットの特性としては、1桁の誤りを検出可能であり、隣接する桁の同じ誤りと桁の入れ替わりそれぞれを90%程度で検出可能というものである。オーソドックスの見本ともいえる手法だろう。

法人番号

　法人番号のチェックディジットの計算方法は以下で紹介されている。

法人番号の指定等に関する省令 | e-Gov法令検索

　この検査で用いているチェックディジットの計算は、12桁の10進数数値から剰余に基づく方法で $s=9$ 、

\{w_{1},\cdots,w_{12}\}=\{2,3,4,5,6,7,2,3,4,5,6\}

を用いて計算をしているものである。つまり、法人番号のチェックディジットの特性としては、1桁の誤りと隣接する桁の入れ替わりをそれぞれを90%程度で検出可能というものである。隣接する桁の同じ誤りについては特に設計はされていない。~~設計ミスしているのでは。~~

個人番号

　個人番号(マイナンバー)のチェックディジットの計算方法は以下で紹介されている。

行政手続における特定の個人を識別するための番号の利用等に関する法律に規定する個人番号、個人番号カード、特定個人情報の提供等に関する命令 | e-Gov法令検索

　この検査で用いているチェックディジットの計算は、11桁の10進数数値から剰余に基づく方法で $s=11$ 、

\{w_{1},\cdots,w_{11}\}=\{2,3,4,5,6,7,2,3,4,5,6\}

を用いて計算をしているものである。ただし、チェックディジットが10となった場合は0として扱う。つまり、個人番号のチェックディジットの特性としては、1桁の誤りと隣接する桁の同じ誤り、桁の入れ替わりそれぞれを90%程度で検出可能というものである。~~設計ミスしているのでは。~~
　同様の手法は、桁数が異なるだけで以下のチェックディジットでも用いられている。

住民票コード
全国地方公共団体コード
運転免許証番号

おわりに

　チェックディジットをなんとなく理解するために理論を展開してみたが、実運用ではかなり雑にチェックディジットが利用されているように感じた(法人番号など)。もっと世界に目を広げればそうではないかもしれないが、興味があるのは実運用ではなくアルゴリズムの方であるため、特に気にしないでおく。
　今回雑に展開をしてみたチェックディジットの理論については、あくまでも基本的なものであり、実用を考えると1桁ではなく2桁以上のチェックディジットを利用することの検討であったり、様々な誤りパターンへの対応などと考えるべき事柄はたくさんある。しかしながら、今回の記事で基本的な考え方は展開できたと思うので、別にいいだろう。