infoTech - 41semicolon/41semicolon.github.io GitHub Wiki
コロナ社の入門書『情報理論』の読書メモ
1. 序論
通信のモデルは以下。ポイントは二種類の目的のことなる符号化（復号）が存在する点:
情報源→情報源符号化→通信路符号化→ディジタル通信路（雑音混入）→通信路復号→情報源復号→受信者
通信する情報はデジタルなので、情報源がアナログの場合はADコンバートが必要。t軸方向にはサンプリング、x軸方向には量子化する。サンプリングをどうするかに関しては標本化定理に従ってナイキスト間隔でサンプリングすればよいという知見がある。
2. 確率論の基礎
確率の用語整理: / 事象 / 試行 / 確率変数 / 確率 / 平均 / 分散 / 互いに排反 / 互いに独立 / 条件付き確率 / ベイズの定理 / 事前確率 / 事後確率
確率過程の用語整理: / M重マルコフ過程 / 単純マルコフ過程 / シャノン線図（状態遷移図） / 遷移確率
3. 情報源符号化
情報源が無記憶で定常で離散的な場合、情報源を確率分布に従った試行を繰り返す装置とみなせる。ある事象が起きた際、その事象の生成確率に応じて情報量を対数を使って定義する。すると情報源全体で見た際の情報量の期待値＝情報源のエントロピーが定義できる。エントロピーはあいまいさを表す指標として使える。なおエントロピーは、情報源の事象数 M で決められる上限がある。この上限値でエントロピーを規格化した冗長度という概念を使うこともある。
情報源の確率変数を符号化する方法について。符号化方法を特徴づけるいくつかの概念: 一意復号可能性, 瞬時性, 平均符号長。瞬時性や一意復号可能性を調べるためには符号の木を用いる。符号化には いくつかの試行をまとめたような拡大情報源という拡張した情報源も考える。N個の連続する確率変数を一つの確率変数として捉えなおすと、平均符号長を短くでき、これをブロック符号という。
平均符号長に関する上限と下限に関して定理が存在する。特に、確率分布が特殊な形になっている時にのみ下限値にできる。一般の場合には情報源符号化定理を使うと、（ブロック符号を用いることも含め）平均符号長の下限があること、そして平均符号長の下限値が情報源のエントロピーによって規定されることが示される。
4. 情報源符号
圧縮技術について。情報源の確率分布がわかっている場合には、ハフマン符号という（非ブロック化という条件下での）オプティマルな符号化が存在する。これを応用して、情報源を拡大してからハフマン符号を生成するブロック化ハフマン符号がある。ブロック数を大きくしていくとブロック化ハフマン符号で理論的な最大圧縮が可能となる。なお、別の方法で圧縮効率を上げる試みがランレングス符号や算術符号。
ランレングス符号。まず適当に連の最大値 N を決める。そして 事象列を生成確率の低い事象で区切る（N個連続で出てこない場合には強制的に区切る）。この処方で作られた新たな事象列に対して符号化する。もちろんハフマン符号化がオプティマルであるのでその処方をランレングスハフマン符号という。
算術符号。情報源をn次に拡大する。この拡大情報源の各事象を[0,1)の区間に割り当てる。具体的には各事象の生成確率に比例した区間をそれぞれの事象に割り当て、区間の代表値として最短に符号化できる値を選ぶ。算術符号においてn→∞で理論的最大圧縮が可能となるので、ブロック化ハフマン符号のライバルであるといえる。復号の計算量が少ないのが強み。
上記のブロック化（ハフマン符号・ランレングスハフマン符号・算術符号）はいずれも情報源の確率分布が既知であることを前提としている。この前提を無くしてできるだけ圧縮効率を高めるユニバーサル符号のひとつにZL符号がある。確率分布を前提としない代わりに、バッファと呼ばれる作業用のメモリ領域を用意する。FIFOの要領で事象列をバッファに突っ込むのだが、突っ込む際にその時点でのバッファ内に似たパターンがあるかをチェックしそれに基づいて(バッファ内位置, そこからの長さ, 付加符号)という圧縮された符号語を作成する。
5. 各種情報量
生成確率が情報量として定義されたように、各種確率の概念を情報量/エントロピーとして再定義する。独立性をはかるための結合エントロピー 、条件付き確率の再定義としての条件つき情報量、その期待値として条件付きエントロピー。片方の事象からもう片方の事象について得られる情報としての相互情報量。
話をぐぐっと変えて、マルコフ過程について。マルコフ過程では各事象が独立に生成されず、そのうえ状態を持つ（今どの状態にいるのかによって事象の生成確率が変わる）。初期状態の影響がみられなくなるような定常状態が存在するとすれば、これまでと同様に確率分布とした情報源と粗視化できる場合がある。その時の対応する無記憶定常情報源を随伴情報源という。一般に随伴情報源のエントロピーはマルコフ情報源のエントロピーよりも大きい（マルコフ過程の情報の曖昧さは定常状態になると増大する）。
6. 通信路の符号化
離散的で無記憶な通信路は通信路行列で表現できる。通信路行列の各成分は、各送信記号（入力, s種類）と各受信記号（出力, r種類）の遷移確率である。特定の通信行列に対応する通信路には、BSC（二元対称通信路）やBEC（二元消失通信路）がある。
通信路を特徴づける指標として通信路容量がある。通信路容量とは（実務上はその自由はないが）各入力記号の生成確率分布を任意に指定できると仮定した際の（入力と出力の間の）相互エントロピーの最大値である。相互エントロピーは情報伝送量と意味付けできるので、通信路容量とは理論的な情報伝送量の上限値と意味付けできる。
通信符号を特徴づける指標として復号誤り率がある。復号誤り率とは受信側で誤って復号してしまう確率であり、通信路と符号方式（例えば同じ信号をN回送信する等）に依存する。復号誤り率が小さい程よい符号といえる。
通信符号化定理は、特定の条件下では、復号誤り率をいくらでも0に近づける通信符号が存在することを示す。存在定理なので具体的な符号方式は示さない。「特定の条件」とは、「情報速度が通信路容量を超えない」という場合である。情報速度とは一つの送信記号を用いて通信路に送り出すことができる情報量。
7. 符号理論
誤り検出符号、誤り訂正符号について。符号語間の距離（ハミング距離）が符号作成時の目安になる（例: できるだけ互いに距離の遠い符号語を用いるというポリシーを立てるなど）。一つの情報記号に対して一つの符号語を割り当てるのは自然な考え方であるが効率が悪いので、N個の情報記号をまとめて符号化するというブロック化符号が一般的。つまりブロックに検査記号を付加して、誤りを検出したり訂正したりする。
k個の情報記号をブロック化したものに1つの検査符号を付与してk+1の符号語長にして誤り検出をする手法がパリティ検査符号。これを l 個集めて二次元に情報記号を配置し（つまり行数l, 列数k)行方向と列方向に検査符号を付加する(つまり l+k 個の検査符号）ことで、「1箇所の誤りを訂正、2箇所の誤りを検出する」符号を実現できる。これを垂直水平パリティ検査符号という。
上記を一般化・抽象化。入力となる k個の情報記号のブロックを u 、u の符号語を w と置く（ただし w は n つの記号のブロックからなるとする)。符号は u → w の写像とみなせる。符号に線形性を要請すると、符号（に対応する写像）は k行n列の行列 Gを用いて w = uGと書ける（注意すべきは、行列の成分計算に出てくる和や積は2を法とする演算である点）。この G に対して、GH' = Oとなるような H' があったとすると、任意の符号語 w に対して wH' = 0という性質を持つ。そこで wH' という計測値をシンドロームと呼び、これがゼロベクトルであるかどうかを検査となる。シンドロームの次元（＝検査符号の数） m に対して、ブロック長を 2**m -m -1、 符号長を 2**m -1とする単一誤り訂正符号のことをハミング符号という。(例：３回繰り返し符号は、m=2のハミング符号の一例)
行列よりも、ビット演算≒多項式表現で上記を再議論するとハミング符号の構成が楽になる。まず種となる多項式 G を用意する。入力の多項式 U に x**m をかけた多項式(つまりmビットシフト)に、それを G で割った余りの多項式（これが m個の検査ビットに対応）を加えた多項式 X で符号化する。つまり、X = Ux^m + C ただし C := Ux^m mod G。さて、G(x)=0 に解があるとして、それを α とおくと、受信多項式 Y に対して、 Y(α) = X(α) + E(α) = E(α) となる。一方、E = Σ a_n x^n であるが単一誤りの場合には誤り箇所を k として、x^k となり、Y(α) = α^k となる。それゆえ、以下の処方で誤り訂正が可能である
- 通信路からビット列を受信し、対応する多項式 Y(x)を作る
- Y(α)を計算してその値を計算する
- それが 0 なら誤りが無い
- それが α^k の値に一致したなら、k番目の符号が誤っていたと判別。該当箇所をビット反転する
上記の手順で、ややこしいのが a). Y(α) の具体的な計算手順, b). α^k (k = 0, 1, 2, ...) との一致確認。どちらも α の代数的な性質によって確かめられる。 m = 2 の場合（検査ビットが2つ）は、{1, 0, α, α+1} が四則演算で体となる（演算が閉じる）。つまり 1 と α を基底とした二成分ベクトルで、任意の数（したがって Y(α), α^k もそう)が表現される。つまり、 任意の数は、A+Bα の形で書け、それを(A, B)と表現できる。成分表示したら、四則演算は簡単。 m = 3 の場合も同様に、任意の数は A+Bα+Cα^2 とかけるので (A, B, C) という三成分のベクトルで表現できる。以下同様。