「誤り訂正可能符号を理解しよう！〜ハミング距離の応用〜」【幾何学の基礎シリーズ】グラフ理論編 その11

本記事の内容

本記事は誤り訂正可能符号について解説する記事です。
本記事を読むにあたり、ハミンググラフ、ハミング距離について知っている必要があるため、以下の記事も合わせてご覧ください。

「ハミンググラフとハミング距離」【幾何学の基礎シリーズ】グラフ理論編 その10

...

for-spring.com

2022.10.01

本記事で言いたいこと

ハミング距離が情報理論で果たす役割が本記事で言いたいことです。

アスキー・コード

ある人$A$が、離れた場所に居る$B$に何らかのメッセージを伝えるとき、よく使われる手段は、電話、無線、あるいはメールなどの通信装置です。
これらの通信装置は、一旦$A$から送られるメッセージを符号化(信号化)して、電話線や電波などの信号を運ぶ媒体(チャンネル)を通して、受信装置に贈り、それをもとに戻して(復号化して)受信者$B$がメッセージを受け取る、という方法です。

誠に平たく言えば、$A$からのメッセージを機械の言葉に一度翻訳して$B$に送り、$B$が機械の言葉を人間の言葉に翻訳し直すことで$A$と$B$は意思疎通を図っている、というわけです。

この機構は

と表現されます。

符号の文字(先程の説明で言うと、機械の言葉)が$0$と$1$のみから成る場合を考えます。
英語の平文で書かれたメッセージを符号化するのに使われるのがアスキー・コード(ASCII)です。
これはAmerican Standard Code for Information Interchangeの略で、英語の各アルファベットや「！」、「＃」、「＆」などの記号にも7桁の2進数(0と1を使って表す数)を対応させています。
文字列はこれらの2進数を並べて表します。

A	1000001	N	1001110
B	1000010	O	1001111
C	1000011	P	1010000
D	1000100	Q	1010001
E	1000101	R	1010010
F	1000110	S	1010011
G	1000111	T	1010100
H	1001000	U	1010101
I	1001001	V	1010110
J	1001010	W	1010111
K	1001011	X	1011000
L	1001100	Y	1011001
M	1001101	Z	1011010

例えば、「CAT」なら「(C)1000011」と「(A)1000001」と「(T)1010100」を並べて「100001110000011010100」と表現します。

符号化と復号化は暗号の理論に関連しますが、ここでは扱いません。
ここでは、チャンネル(電波や電話線などの信号を運ぶ媒体)で起こり得る問題を扱います。

ノイズ

もし、チャンネル(信号を伝える媒体)を通して、符号がそのまま伝われば問題有りませんが、実際には送信の途中で雑音(ノイズ)が加わり、受信したときの符号が送信したときの符号と異なることがあります。

身近で言うと、Bluetoothイヤホンを電子レンジの近くで稼働させたときがイメージが湧きやすいのではないでしょうか。
Bluetoothイヤホンを電子レンジの近くで使うと、音が途切れたり音質が落ちたりしますよね。
これはBluetoothの周波数と電子レンジの周波数が近いため、互いに干渉することが原因です。

もっと身近で言えば、お祭りやらライブやらの最中に話そうとすると、周りの音が大きいがゆえに、意味が通らない言葉に聞き間違いをしたりと意思疎通がしにくかったりしますよね。
そんなイメージです。
広く言えば、世の中は電波で溢れていて、しかも電波は”波”なので互いに干渉してしまいます。
それがノイズの例です。

このような雑音が激しく、符号で使われている文字の入れ替わりが多ければ、復号することは難しくなります。
しかし、雑音による文字の変動があまり多くないときには、次のような符号のアイディアで正しく復号することが出来ます。

ノイズによる信号の変動が少ないときは正しく復号出来ます。

予め送られるメッセージの符号が決められていて(例えばASCII2進数を採用したとして)、その種類を\(A\)と$B$の両人が知っているとします。
例えば、4種類の長さが8の符号
$$\begin{eqnarray} \boldsymbol{a}_1&=&\left( 1,1,1,0,1,0,0,0\right)\\ \boldsymbol{a}_2&=&\left( 1,1,0,1,0,1,0,0\right)\\ \boldsymbol{a}_3&=&\left( 1,0,1,1,0,0,1,0\right)\\ \boldsymbol{a}_4&=&\left( 1,1,1,1,1,1,1,1\right) \end{eqnarray}$$
が決められていたとしましょう。
つまり、先のASCII2進数の表に対応するのが$\boldsymbol{a}_1$、$\boldsymbol{a}_2$、$\boldsymbol{a}_3$、$\boldsymbol{a}_4$です。
$A$はこの中の符号を$B$に送ります。

例えば$A$が送信した符号が
$$\boldsymbol{a}=\left( 1,1,1,0,1,0,0,0\right)=\boldsymbol{a}_1$$
だったとします。
ところが、雑音により$B$が受信した符号が
$$\boldsymbol{a}^\prime=\left( 1,1,1,0,1,1,0,0\right)$$
のようになってしまうこともあり得るわけです(6番目の$0$が$1$に変わっています)。
このとき、元の符号を復元しようとするとき、どのようにすれば良いでしょうか。

上で与えた符号のリストの中で、$B$が受信した$\boldsymbol{a}^\prime$に「最も近い」符号が、$A$が送った符号と(断定は出来ないけれど)判断して良いでしょう。
この「符号の近さ」を定量的に定式化したものがハミング距離なのです。

ハミング距離をサラッと復習します。

詳しくは【幾何学の基礎シリーズ】グラフ理論編 その10を御覧ください。

要するに、長さが同じ文字列$\boldsymbol{a}$と$\boldsymbol{b}$が何文字異なるか、ということを表しているのが関数$d$です。

このハミング距離で$\boldsymbol{a}^\prime$に最も近いのは$\boldsymbol{a}_1=\left( 1,1,1,0,1,0,0,0\right)$だから、$B$は、$A$が送った符号は$\boldsymbol{a}_1$だ、と判断できるわけです。

要するに何が言いたいかと言うと、

ということです。
少々粗をつくことを言えば、ノイズで変わってしまった符号とハミング距離が同じ符号が複数ある場合は判断しかねます。

今の話を一般化します。

先程述べたことを一般化してみます。

以下、前節の設定を用いて、符号で使われる文字の集合を$W$として、符号の長さは$n\in\mathbb{N}$で固定されているとします。

※以下で定めることは、後でまとめます。

符号全体の集合は$W$の$n$個の直積集合$V=W\times \cdots\times W\ $($n$個の直積)です。さらに、$\left|W\right|=q$とします。
故に$\left|V\right|=q^n$です。
例えば、先の$\boldsymbol{a}_1$、$\boldsymbol{a}_2$、$\boldsymbol{a}_3$、$\boldsymbol{a}_4$については$W=\left\{0,1\right\}$、$q=2$、$n=8$です。

$M$(MessageのM)を送りたいメッセージの集合とすると、$M$の符号化というのは、$M$から$V$への単射$\varphi:M\to V$のことです。
「全単射じゃないの？」と思うかもしれませんが、もし全単射であれば、メッセージが1つ１つ重複なく対応しているわけですので、ノイズが乗っていない、ということになってしまいます。

また、$\psi\circ\varphi=I_M$、すなわち全てのメッセージ$m\in M$に対して、$\psi\left( \varphi(m)=m\right)$を満たすような写像$\psi:V\to M$を復号化と言います。

では、ノイズ(雑音)はどのように定めたら良いでしょうか。
雑音の原因は様々ですし、完全な記述というのは困難を極めます。
そこで、雑音がもたらす結果のみに着目することにしましょう。
つまり、雑音がもたらす符号の変化に焦点を当てる、というわけです。

これを$V$から$V$への”ある特別な”性質を満たす写像$\omega:V\to V$から成る集合$\Omega$のことを雑音と呼びましょう。

もし、全ての$\omega\in\Omega$に対して、$\psi\circ\omega\circ\varphi=I_M$となるような復号化$\psi$を持つとき、符号化$\varphi$は雑音$\Omega$による誤りを訂正できる(error-correcting)と呼ぶことにします。

以上のことをまとめて書くと、次です。

雑音の程度

雑音の程度$e\left( \varphi,\Omega\right)$を定めます。

要するに、どういうことかというと

ということです。

訂正可能な符号化を求めるには？

一般化する前の例のお話を思い出すと、訂正可能な符号化を求めるには、雑音の程度と比較して
$$d(\varphi)=\min_{m_1\neq m_2\in M}d\left(\varphi(m_1),\varphi(m_2) \right)$$
を大きくすれば良いわけですが、正確には次の定理が成り立ちます。

定理1.の証明

符号化$\varphi:M\to V$は単射なので、メッセージの集合$M$を符号化による像$\varphi(M)\subset V$と同一視することで、$M$は$V$の部分集合と思っても良いです。
このとき、符号化は包含写像$\iota:M\to V$と一致します。

①$d(\varphi)\geq 2e\left(\varphi,\Omega\right)+1$が成り立てば、符号化$\varphi$の誤りを訂正できることの証明

$e=e\left(\varphi,\Omega\right)$として、$M=\left\{\boldsymbol{a}_1,\boldsymbol{a}_2,\dots, \boldsymbol{a}_k\right\}\subset V$とします。
ただし、$k$はメッセージの数です。
ここで、$\varphi(\boldsymbol{a}_i)=\boldsymbol{a}_i$に注意しましょう。
$$B_i(e)=\left\{\boldsymbol{a}\in V\middle|d(\boldsymbol{a},\boldsymbol{a}_i)\leq e\right\}\ (i=1,2,\dots,k)$$
とおくと、任意の$\omega\in \Omega$に対して$\omega(\boldsymbol{a}_i)\in B_i(e)$であり、さらに
$$B_i(e)\cap B_j(e)=\emptyset\ (i\neq j)$$
となります。
実際、仮に$\boldsymbol{a}\in B_i(e)\cap B_j(e)$とすると、$d$は距離関数なので、三角不等式が成り立つから
$$d(\boldsymbol{a}_i, \boldsymbol{a}_j)\leq d(\boldsymbol{a}_i,\boldsymbol{a})+d(\boldsymbol{a},\boldsymbol{a}_j)\leq 2e$$
となって、$d\left( \varphi\right)\geq 2e+1$に反します。

さて、今示したことを使って復号化$\psi:V\to M$を、
$$\psi(\boldsymbol{a})= \begin{cases} \boldsymbol{a}_i&(\boldsymbol{a}\in B_i(e))\\ Vから任意に選んだ値&\displaystyle\left(\boldsymbol{a}\in\bigcup_{i=1}^k B_i(e) \right) \end{cases}$$
で定めます。
$\psi(\boldsymbol{a}_i)=\boldsymbol{a}_i$だから、これを符号化$\varphi$を用いて書き直すと、$\psi\circ\varphi=I_M$が得られるので、$\psi$は復号化です。
さらに、$\omega(\boldsymbol{a}_i)\in B_i(e)$であることから、$\psi\left( \varphi(\boldsymbol{a}_i)\right)=\boldsymbol{a}_i$も成り立ち、これも書き直せば、$\psi\circ\omega\circ\varphi=I_M$となり、$\varphi$は誤り訂正可能です。

②$e\left(\varphi,\Omega\right)\leq e$となる全ての雑音$\Omega$について、$\varphi$が誤り訂正可能であれば、$d(\varphi)\geq 2e+1$であることの証明

$$d\left( \boldsymbol{a}_i,\omega(\boldsymbol{a}_i)\right)\leq e\quad (i=1,2,\dots,k)$$
を満たす$\omega:V\to V$を任意に取ります。
$\Omega=\left\{\omega\right\}$とすると、
$$e\left(\varphi,\Omega\right)=\max\left\{d\left( \boldsymbol{a}_i,\omega(\boldsymbol{a}_i)\right)\middle|i=1,\dots, k\right\}\leq e$$
だから、仮定により$\varphi$は誤り訂正可能です。
すなわち、$\psi\left( \omega(\boldsymbol{a}_i)\right)=\boldsymbol{a}_i\ (i=1,\dots,k)$を満たす復号化$\psi:V\to M$が存在します。

任意の番号$s\neq t\ (1\leq s,t\leq k)$について$B_s(e)\cap B_t(e)=\emptyset$であることを示しましょう。
背理法により示します。
仮に$B_s(e)\cap B_t(e)$に属する符号$\boldsymbol{x}$が存在するとしましょう。
これを用いて$\omega:V\to V$を
$$\begin{eqnarray} \omega(\boldsymbol{a}_s)&=&\omega(\boldsymbol{a}_t)=\boldsymbol{x},\\ \omega(\boldsymbol{a}_u)&=&\boldsymbol{a}_u\quad (u\neq s,t) \end{eqnarray}$$
で定めます。
これは、$d\left( \boldsymbol{a}_i,\omega(\boldsymbol{a}_i)\right)\leq e\ (i=1,\dots,k)$を満たします。
実際、
$$\begin{eqnarray} &&d\left(\boldsymbol{a}_s,\omega(\boldsymbol{a}_s) \right)\leq e\\ &&d\left(\boldsymbol{a}_t,\omega(\boldsymbol{a}_t) \right)\leq e\\ &&d\left(\boldsymbol{a}_u,\omega(\boldsymbol{a}_u) \right)\leq e\quad(i=1,\dots,k) \end{eqnarray}$$
です。
しかし、上で述べたことから$\psi\left( \omega(\boldsymbol{a}_i)\right)＝\boldsymbol{a}_i\ (i=1,\dots,k)$を満たす復号化$\psi:V\to M$が存在するので、
$$\boldsymbol{a}_s=\psi\left( \omega(\boldsymbol{a}_s)\right)=\psi(\boldsymbol{x})=\psi\left(\omega(\boldsymbol{a}_t) \right)=\boldsymbol{a}_t$$
となって矛盾です。
故に$B_s(e)\cap B_t(e)=\emptyset$です。

さて、定理の結論を否定してみます(背理法)。
$d(\varphi)\geq 2e+1$の否定は$d(\varphi)\leq 2e$となるから、$d(\boldsymbol{a}_i,\boldsymbol{a}_j)\leq 2e$を満たす$\boldsymbol{a}_i,\boldsymbol{a}_j\ (i\neq j)$が存在することになります。
$\boldsymbol{z}\in V$を
$$\begin{eqnarray} &&d\left( \boldsymbol{a}_i,\boldsymbol{a}_j\right)=d\left( \boldsymbol{a}_i,\boldsymbol{z}\right)+d\left( \boldsymbol{z},\boldsymbol{a}_j\right),\\ &&d\left( \boldsymbol{a}_i,\boldsymbol{z}\right)\leq e,\quad d\left( \boldsymbol{z},\boldsymbol{a}_j\right)\leq e \end{eqnarray}$$
を満たすように取ることが出来るから、$\boldsymbol{z}\in B_s(e)\cap B_t(e)$となって、$B_s(e)\cap B_t(e)=\emptyset$に矛盾します。
従って証明完了です。

定理1.の証明終わり

文字の数、符号の長さ、雑音の程度を固定したときは？

文字の数$q=\left|W\right|$と符号の長さ$n$、及び雑音の程度(の上限)$e$を固定したとき、どの程度の数のメッセージを、誤り訂正できるような符号に直すことが出来るかを考えます。
つまり、メッセージ数$\left|M\right|$の上限を求めたいわけです。
これに答えるのが次の定理です。

定理2.の証明

定理1.の証明と同様に、$M=\left\{\boldsymbol{a}_1,\dots,\boldsymbol{a}_k\right\}$とします($k=\left|M\right|$)。
仮定から、定理1.の後半を用いて、$d(\varphi)\geq 2e+1$です。
さらに、定理1.の証明から$\displaystyle\left\{B_i(e)\right\}_{i=1}^k$は互いに交わりません。

$$B_i(e)=\bigcup_{h=0}^e\left\{\boldsymbol{x}\middle|d(\boldsymbol{x},\boldsymbol{a}_i)=h\right\}$$
となることに注意しましょう。
ここで、次の事実を使います。

補題3.の証明

$d(\boldsymbol{x},\boldsymbol{a})=0$となる$\boldsymbol{x}$は$\boldsymbol{a}$のみであることと、任意の$\boldsymbol{x}$に対して$d(\boldsymbol{x},\boldsymbol{a})\leq n$であることに注意すると、$1\leq h\leq n$の場合についてのみ証明すれば良い事がわかります。

$d(\boldsymbol{x},\boldsymbol{a})=h$ということは、文字列$\boldsymbol{x}$と$\boldsymbol{a}$の中で異なる文字を持つ場所の個数が$h$個ということです。
$h$個の場所$i_1,\dots,i_h$の選び方の総数は${}_nC_h$個であり、$h$個の場所$i_1,\dots,i_h$を選べば、それぞれの$i_s\ (1\leq s\leq h)$で$\boldsymbol{a}$の中の文字と異なる文字の個数は$\left|W\right|-1$であるため、場所$i_1,\dots,i_h$で$\boldsymbol{a}$と異なる文字を選ぶ選び方は$\left( \left|W\right|-1\right)^h$通りあります。
従って、証明完了です。

補題3.の証明終わり

定理2.の証明に戻りましょう。

補題3.から、
$$\left|\left\{\boldsymbol{x}\middle|d(\boldsymbol{x},\boldsymbol{a}_i)=h\right\}\right|={}_nC_h(q-1)^h$$
だから、
$$\left|B_i(e)\right|=\sum_{h=0}^e{}_nC_h(q-1)^h\tag{\(\ast\)}$$
となり、特に、$\left|B_i(e)\right|$は$i$には依存しません。
$\displaystyle\left\{B_i(e)\right\}_{i=1}^k$が互いに交わらないことから
$$\sum_{i=1}^k\left|B_i(e)\right|\leq \left|V\right|$$
となり、これに$(\ast)$を代入すると、
$$k\left(\sum_{h=0}^e{}_nC_h(q-1)^h \right)\leq q^n$$
が得られます。
従って証明完了です。

定理2.の証明終わり

情報理論における重要な問題の1つは、できるだけ多くのメッセージを誤り訂正可能なように符号化する方法を見出すことです。
この問題では、整数論や代数幾何学などが用いられています。

皆様のコメントを下さい！

今回のジョークはこれです。

地表のような球面に円を置いたとき、円によって分けられる2つの領域のどちらが囲まれた内側か、ということはそれだけでは数学者にとっては明らかなことではありません。
普通は物理学者のように発想します。
極端に言えば、赤道の周長と同じ長さのロープで囲むものとして読めば、何らおかしなことを言ってないはずです。
面をロープで囲むという簡単な問題ですら数学者にとっては単純ではない問題ということを示しているのがこのジョークです。

他にご存知のジョークをコメント欄で教えて下さい！

結

今回は、ハミング距離との応用として、誤り訂正可能符号について解説しました。
これはグラフ理論の情報理論での応用例です。

我々が普段何気なく使っているツールの根幹には数学が隠れている、という良い例だと思います。

次回は誤り産業連関について解説します。

乞うご期待！
質問、コメントなどお待ちしております！
どんな些細なことでも構いませんし、「定理〇〇の△△が分からない！」などいただければ全てお答えします！
お問い合わせの内容にもよりますが、ご質問はおおよそ３日以内にお答えします。
もし直ちに回答が欲しければその旨もコメントでお知らせください。直ちに対応いたします。