符号の信頼度をあげよう
このページはマス旅の一部です。
今回は、符号の信頼度にかかわる数・量・式について探ってみよう。
１．ウォーミングアップ
ここまで学んだことのまとめにもなる内容です。
だから、学んだことを手短に確認しておこう。
＜エントロピー＞
# 情報量は珍しいほど大きいから確率の逆数で定義する。直観理解と2進数との連携のために、
log_2(確率pの逆数）とする。つまり、（自己）情報量I＝-log_2(p)。
p=2^(-q)ならpを2進小数に直したときの小数点q位に1が立つ。情報量I=q（ビット）
#エントロピーH（X）確率変数X＝pの期待値(平均情報量）で、-pΣlog_2(p)。
特に2元事象のとき、エントロピー関数H(p)=-plog_2(p)-(1-p)log_2(1-p)
#同時エントロピーは条件付きエントロピーの分増える。
つまり、H(AB)=H(A)+H(B|A)（チェーンルール）
#相互情報量は条件付きエントロピーになって不確かさが減った分。
つまり、I(A;B)=H(A)-H(A|B)
相互情報量は対称性がある。I(A;B)=I(B;A)
同時エントロピーと相互情報量の和＝AとBのエントロピーの和
つまり、H(AB)=H(A)+H(B)-I(A;B)
＜情報源モデル＞
#記憶のない情報源は条件付き確率は不要で、同時確率は同じ確率の積
p(x1,x2,x3,x4,x5)=p(x1)p(x2)p(x3)p(x4)p(x5)=(1/2)^5
#記憶のある情報源（マルコフ情報源）では前の記号の確率に条件付き確率をかけた積和
例えば、p(X2=0)=p(X1X2=00)+p(X1X2=10)=p(0)p(0|0)+p(1)p(0|1)
#エントロピーレート
１つ前だけに依存する定常マルコフ情報源 ではH（X)=H(X2|X1)
S={0,1}のコイン投げでは、H(X)=[H(a)b+H(b)a]/(a+b)
a=0.5,b=0.5で完全無記憶ランダム状態でエントロピーが最大の１になる。
＜情報源符号化＞
#符号は0，1を使う。効率よい信号を作るには1語の長さの平均を短くする。
Hが情報量、Lが平均語長とするとき、2元符号では符号化効率e=H/L
#確率分布が事前にわかる場合は符号化効率は、ハフマン符号が最良だ。
#シャノンの第一定理(無雑音限界）
r元符号化の場合、平均語長Lは下限のH/log_2(r)に近づけることができる。
＜通信路モデル＞
#通信路容量Cは相互情報量I(X;Y)の最大値。
無記憶で雑音がないとC=1。
雑音があっても出力から入力が逆算できるとC=1。
#相互情報量は受信エントロピーから
取り違えのエントロピー(環境ノイズ）h(ε)がけずられる。
I(X;Y)=H(Y)-h(ε)
#BSC(2元対称通信路）の通信路容量C＝１－h(ε)
誤り率ε=0.5ならh(ε)は完全なノイズになるのでCは最小値の０。
ε=0または１だとCは正解か正解の反転だから、最大値１となったね。
どうでしょうか。思い出しましたか？
あやふやなところがあれば、前のページに目を通しておこう。
２．「符号語の距離」と「誤りの検出・訂正」の関係
雑音のないときの符号化は、効率優先でよかったですね。
でも、雑音がある場合の符号化は、効率も大切ですが、正確さ、信頼性が重要になります。
「騒音の中での会話」をイメージしてください。
1回言ってもちゃんと聞こえないかもしれないからもう1回言ったり、ゆっくり大声で音を伸ばして発音したり、いろいろ冗長な伝え方をしますよね。
それは符号化でも同じことです。
雑音がある環境での通信は、誤りを検出したり訂正したりできるように、
冗長な部分を付け足す必要があるのです。
＜シャノンの第２定理＞
通信路容量Cの通信路ではC未満の伝送速度Rで情報を伝えるとき、ある正数δがあって、
RがC－δ未満の速さならば、誤りの確率をいくらでも小さくできる。
つまり、「雑音があっても信頼性100％にできる」という驚異的な定理です。
「誤り」とは、符号{0,1}が反転して伝わることをいいます。
「誤り検出」とは、誤りの発生がわかることであり、どこに誤りがあるかまではわかりません。だから、再送信が必要になります。
「誤り訂正」とは、どこに誤りがあるかまでわかるので、再送信なしに訂正できます。
この検出と訂正を可能にする、符号の幾何学的構造化があります。
＜ハミング重みとハミング距離＞
たとえば、長さ3の2元符号系列を３つ考えます。
0=[000],
x=[101],
y=[111]
#xは0と比べて1が2つ立っているので「xの重み」w(x)=2としましょう。
yは0と比べて1が3つ立っているのでyの重みw(y)=3とします。
#次はxとyを同じ順番どうしを比べます。一致しているときは0、不一致なら1としましょう。
[010]ですね。これはx⊕y（排他的論理和）そのものです。
ｘが送信語、ｙが受信語だとする「2番目のビットにエラー発生！」というイメージになります。
この「x⊕yの重み」w(x⊕y)を「（ハミング）距離」dとします。
d(x,y)=w(x⊕y)=w([010])=1です。
これで、ハミング距離が「２語の不一致数」であり、計算できるようになりました。
d(x,y)=w(x⊕y)の代わりにd(x,y)=Σδ(x,y)ともかけます。δ(x,y)=if(x==y,0,1)とif式の関数でかけますね。
＜立方体で見るハミング距離＞
ハミング距離を始めて見聞きすると、記号だらけで複雑に見えますが、
長さ3の2元符号系列を3次元の8点（立方体の頂点）座標に対応させるとイメージがわきます。
原点Oでは、xy平面(z=0),yz平面(x=0),zx平面(y=0)が交わってますね。この空間で、x=1平面、y=1平面、z=1平面の3つの面を追加しましょう。
そうすると、6つの面で囲まれた立方体ができます。
その頂点の座標は8個あります。
#z=0平面には
P000=(0,0,0),P010=(0,1,0),P100=(1,0,0),P110=(1,1,0)
#z=1平面には
P001=(0,0,1),P011=(0,1,1),P101=(1,0,1),P110=(1,1,1)
があります。
この任意の2点の距離は3通りありますね。
#１ :「１辺」の長さ
#√2 : 「正方形の対角線」の長さ
#√3 : 「立方体の一番長い対角線」の長さ
これが座標までみるとハミング距離に対応することがわかりますよ。
#距離１の2点は同じ辺の両端にあります。辺は２つの面の共通集合です。
どの辺を見ても２平面にあるので、２つの座標が一致して1つ不一致なので、ハミング距離は１ですね。
#距離√2の2点は同じ平面にあるけれど同じ辺にはありません。
だから１つだけ座標が一致します。２つの符号が別だから、ハミング距離は２です。
#距離√3は一致する平面が１つもない、つまり3符号がすべて別々ですからハミング距離は３です。
つまり、点から点までつなぐ最小の辺数が１，２，３ならハミング距離はそのまま１，２，３です。
ハミング距離がグッと身近になりましたね。
課題：ハミング距離の視覚化をgeogebraでやってみよう。
タイトル「ハミング距離」
# 8つの頂点（符号語）の作成
# Pxyzの見出しをxyzにする。
P000 = (0, 0, 0)
P100 = (1, 0, 0)
P010 = (0, 1, 0)
P110 = (1, 1, 0)
P001 = (0, 0, 1)
P101 = (1, 0, 1)
P011 = (0, 1, 1)
P111 = (1, 1, 1)
♯ 立方体はCubeコマンドがあるが、数式に表れない従属オブジェクトとしての頂点が作られるため
手間ですが、6面をPolygon(４つの点の名前のカンマ区切り）で入力します。
座標軸は設定のグリッドをオフ、軸をx,y,z軸の数値を非表示にして、正の部分だけをオンにします。
＜ハミング距離の符号語の設計＞
さて、ハミング距離は「語の不一致数」を表していましたから、誤り検出や訂正のための符号語のルールに使えそうですね。
たとえば、距離2の語群W0={000,011,101,110}を送信し、W1={111,100,010,001}は
送信しないルールにします。
#誤り数が１ならW1が受信されるので誤り検出はできます。
#誤り数が２だとW0の別の物が検出されるので、誤り検出できません。
距離２の誤り検出は１ビット、誤り訂正は0ビットですね。
次は、使う語群を限定してみよう。
距離3の語群Wr={000,111}を符号語として送信し、We={011,101,110,100,010,001}は送信しないルール。
#誤り数が１ならば、000の送信では{100,010,001}が受信され、111の送信では{011,101,110}が受信されるので、どちらの受信語から送信語を復元できます。訂正できるわけです。重みの多数決で送信語がわかるので、「多数決符号」なんて呼ばれたりします。
#誤りが2だと誤りは検出できますが、多数決がきなないので訂正まではできません。
距離３の誤り検出は2ビット、誤り訂正は１ビットです。
＜符号語の距離の下限＞
「多数決符号」の流れで、検出と訂正が可能なビット数と距離の関係を一般化してみよう。
長さｎの2元系列(2^n)個から、符号語群Wr={w1,….wi,…,wj,…,wm}を厳選して残りをWeとするルール。
符号語はn次元空間の中の点です。まあ、3次元空間のイメージでも大丈夫です。
Wrの各語から半径cの距離にあるWeは誤り訂正できて、
さらに距離dだけ遠くのWeは検出できるとしましょう。
このとき、Wrの任意の2つの符号語をwi、wj,Weの要素をweとします。
wiを中心にする訂正可能な半径ｃの白球が半径c+dのグレー球に入ってます。
wjを中心にする訂正可能な半径ｃの白球が半径c+dのグレー球に入ってます。
中心wiの白球と中心wjの白球のグレー球どうしが離れている場合は問題ありません。
グレーゾーン自体が多少かぶるのも問題ありません。
でも、wiからc+dの距離で、wjからcの距離の語weはどうなるでしょう。
weはwiからもwjからも検出できますが、wjだけからだけ訂正すべきと出ます。
アルゴリズムによりますが、距離の意味が多義的になってしまいます。
だから、グレーのキワが他の白球にかからないようにします。
つまり、wiから(c+d)の距離で、wjからは(c+1)の距離だったら、
どちらもグレーでエラー発見という共通の結論になるので、問題ないですね。
dmin = d(wi,wj)≧(c+d)+(c+1)=2c+d+1
これを、符号語の距離の下限とすればよいですね。
たとえば、dmin=5なら、(c,d)=(2,0),(1,2),(0,4)のように3通りの設定が可能となる。
dminにゆとりがあれば検出ビットと訂正ビットの設定に自由度があることもわかりました。
ハミング距離
３.誤り訂正のできる符号化法
単一誤り訂正符号（Single Error Correcting Code:略してSEC)は
1個の誤り訂正ができる符号化法です。
＜長方形符号（水平垂直パリティ検査符号）＞
SECの１つに長方形符号があります。
もとの情報Xがn行m列の{xij}行列とするとき、
Xをそのまま送信せずにm+1列目にn個のpiを追加し、n+1行目にm＋1個のqjを追加します。
その追加したビット(パリティビット）が「検査ビット」です。
情報に検査ビットが付加された行列が「符号行列」Yです。
p,qは水平垂直パリティーというビットです。
pi=⊕xij(水平方向の排他的論理和)
qj=⊕xij(垂直方向の排他的論理和)
合計列と合計行を追加するのですね。
排他的論理和は偶数の１が合わさると0に消えます。だから、
1が偶数個なら０、奇数個なら１になります。
１が奇数個ならときpi=1,１が偶数個ならpi=0と定めているため、どの行も和が０（偶数パリティー）になるように、パリティービットが設定されているのです。
Yに1個の誤りがあると、その位置がi行j列だとすれば、そのビットだけ01が反転することで、偶数パリティが狂い、エラー（１）が検出されます。
それは、i行とj列だけです。そのため、誤り訂正ができるのですね。
＜線形符号（行列による符号化と検査）＞
長方形符号の考え方を一般化して扱いやすく代数化したものが線形符号です。
検査すべきn要素の送信語（符号語）aをn列のベクトルとすると、
送信語は２つの部分に分割できる。
もとの情報が入ったベクトルi=[i_k](k列）、
誤りチェック用の検査ベクトルp＝[p_{n-k}](n-k列）。
これを（n,k)線形符号といいます。
線形符号とは検査ベクトルpが情報ベクトルiの各要素の
1次結合（排他的論理和の組み合わせ）で表すことができる符号です。
pの要素は0,1からできいて、結合のときの演算は0,1で完結する加法と乗法なので2を法とする剰余演算とします。１＋１＝０(mod 2)です。
#（n,k)線形符号では、「^t」が転置行列や列ベクトルにする操作としてかくことにすると、
p^t={pij}i^tという
「情報と検査とつなぐ行列」P={pij}(n-k行k列）
で表現できます。
言い換えるとp=iP^t（P^tは(k行n-k列）)です。
だから、送信ベクトルは、
a=[i,p]=[i,iP^t]=i[E_k,P^t]です。（E_kはk行k列の単位行列とします）
#「生成行列」G＝[E,P^t] (k行(k+(n-k))=n列）
とおくだけで、送信ベクトルが、情報ベクトルにGをかけるだけでできます。
a=iG
#さらに、p^t=Pi^tから、Pi^t-p^t=0^t 。
剰余演算と同じなので、－を＋にしても同じだから、
Pi^t+p^t=Pi^t+E_{n-k}p^t
=[P,E_{n-k}][i,p]^t=0^t。
[i,p]^t=a^tだから、
「検査行列」H=[P,E]
(n-k行で(k+(n-k))=nだからn列）
とおけば、Ha^t=0^t。言い換えると
aH^t=0
となる。
#これはとても便利な式だ。
正しい送信ベクトルaならばH^tをかけると0ベクトルになるということだ。そこで、言い換えると誤ったベクトルeをH^tにかけると、eH^tは０にならない。これをまとめると、正誤のわからないベクトルｂにH^tをかけた結果
ｓ＝bH^t
を症候（シンドローム）として、
０なら「正しい」、０でないなら「誤りあり」と判断できる。
だから、sをシンドロームというだね。
＜ハミング符号＞
(n,k)線形符号で単一誤りだけ発生するときは誤りパターンは
e={0,0,..0,1,0,..,0}j番目だけ誤りで、jは１からn。
s=eH^t=(H^tの第ｊ行）
＝(Hの第ｊ列)^t。
でも、Hの列に０ベクトルがあると誤りが発見できません。
(n,k)符号の検査行列は(n-k行n列）で、検査ベクトルの要素数はn-k
です。だから、可能な系列は2^(n-k)通りで0ベクトルを引くと2^(n-k)-1 通りある。
一方で誤りパターンはn通りあるから、
n≦2^(n-k)-1
ならば、シンドロームｓで誤りパターンeを網羅できるから訂正が可能になる。
この不等式で「等号が成り立つ場合」を特に、「ハミング符号」といい、SECの１つです。
符号の無駄がまったくないですね。
＜（7,4)ハミング符号の確認＞
(n,k)=(7,4)線形符号場合は2^(7-4)-1=8-1=7だから、
ハミング符号になります。
情報ベクトルi={i1,i2,i3,i4},
検査ベクトルp={p1,p2,p3}
この関係が線形結合で設定しましょう。
p1=i1 +i3 +i4
p2=i1 +i2 +i3
p3= i2 +i3 +i4
とすると、
情報と検査とつなぐ行列P（3×4)は{
{1,0,1,1},
{1,1,1,0},
{0,1,1,1}}
P^t={
{1,1,0},
{0,1,1},
{1,1,1},
{1,0,1}}
となるので、
送信を生成する行列G=[E_4,P^t](4×7)は{
{1,0,0,0,1,1,0},
{0,1,0,0,0,1,1},
{0,0,1,0,1,1,1},
{0,0,0,1,1,0,1}}
検査行列H＝[P,E7-4](3×7)は{
{1,0,1,1,1,0,0},
{1,1,1,0.0,1,0},
{0,1,1,1,0,0,1}}
誤りパターンe={j番目だけ1}にH^tをかけると、
ｊ番目が誤りだと、ｓ=eH^tはHのj列の転置になる。
たとえば、
1番目が誤りだと、s=(Hの1列目)^t={1,1,0}
2番目が誤りだと、s=(Hの2列目)^t={0,1,1}
3番目が誤りだと、s=(Hの3列目)^t={1,1,1}
..................
7番目が誤りだと、s=(Hの2列目)^t={0,0,1}
７シンドロームが７つの誤りパターンに1対1に対応するので、ハミング符号になることがわかるね。
符号語がベクトルになり、ベクトル計算だから行列で解決できるという流れが面白いですね。