走る作曲家のAIカフェ

「北海道大学大学院情報科学院修士課程入学試験」（令和6年8月実施）の情報理工学コース「情報理論」対策ページです。

分野別対策

• 院試対策 ～はじめに～
• 院試対策 ～基礎数学編～
• 院試対策 ～情報数学編～
• 院試対策 ～確率・統計編～
• 院試対策 ～情報理論編～
• 院試対策 ～アルゴリズムとデータ構造編～
• 院試対策 ～人工知能編～
• 院試対策 ～コンピュータシステム編～
• 院試対策 ～最終チェック～

情報理論

参考にしたサイトは以下のとおり。

情報理論 (Information Theory).html

情報理論とは

情報理論が取り組む4つの課題

• できるだけよい情報源符号化法を見出すこと
• 情報源符号化の限界を知ること
• できるだけよい通信路符号化法を見出すこと
• 通信路符号化の限界を知ること

条件付き確率

条件付き確率

事象\(B\)の条件のもとで事象\(A\)が起こる条件付き確率は

乗法定理

情報量とエントロピー(1)

情報量

確率\(p\)の事象の生起を知った時に得られる情報量を\(I(p)\)とする。

\(I(p)\)は次のような性質を満たすべき。

• \(I(p)\)は\( 0 < p \leq 1 \)で単調現象な関数である
• 確率\(p_1, p_2\)で起こる二つの互いに独立な事象が同時に起こる確率\(p_1, p_2\)について\(I(p_1 p_2) = I(p_1) + I(p_2)\)
• \(I(p)\)は\( 0 < p \leq 1 \)で連続な関数である

これらを満たす関数\(I(p)\)は\(I(p) = - \log_a p\)という形しかありえない（\(a > 1\)）

確率\(p\)で生起する事象が起きたことを知ったときに得られる情報量\(I(p)\)を自己情報量と呼び、\(I(p) = - \log_a p\)と定義する。ただし、\(a > 1\)である。

\(a = 2\)のとき、単位はビットという。つまり、確率\(\frac{1}{2}\)で生じる結果を知った時の情報量は1 [bit]である。

平均情報量

\(M\)個の互いに排反な事象\(a_1, a_2, \cdots, a_M\)が起こる確率を\(p_1, p_2, \cdots, p_M\)とする（ただし、\(p_1 + p_2 + \cdots + p_M = 1\)）。

このうち１つの事象が起こったことを知ったときに得る情報量は\(- \log_2 p_i\)であるから、これを平均した期待値\(\overline{I}\)は、

となる。これを平均情報量（単位はビット）という。

エントロピー

確率変数\(X\)が取り得る値が\(x_1, x_2, \cdots, p_M\)（ただし、\(p_1 + p_2 + \cdots + p_M = 1\)）であるとき、確率変数\(X\)のエントロピーを

ビットと定義する。

一般に、確率分布の偏りが非常に大きいときは平均情報量が小さく、確率分布が均一の時に平均情報量が最大になる。

エントロピーと平均情報量は、完全に同じ形をしている。

情報を受け取ると曖昧さが減るので、受け取った量だけエントロピーは減って、0に近づく（受け取った情報量 = エントロピーの変化）

エントロピーの性質

\(M\)個の値を取る確率変数\(X\)のエントロピー\(H(X)\)は次の性質を満たす。

1. \(0 \leq H(X) \leq \log_2 M\)
2. \(H(X)\)が最小値0となるのは、ある値を取る確率が1で、他のM-1個の値を取る確率がすべて0の時に限る。すなわち、\(X\)の取る値がはじめから確定している場合のみである。
3. \(H(X)\)が最大値\(\log_2 M\)となるのは、\(M\)個の値がすべて\(\frac{1}{M}\)で等しい場合に限る。

エントロピーは「答えのあてにくさ」を表す数値ともいえる。

2つ以上の確率変数を扱う場合

２つの確率変数\(X, Y\)を考える。\(X\)は\(x_1, x_2, \cdots, x_{M_X}\)の値をとり、\(Y\)は\(y_1, y_2, \cdots, y_{M_Y}\)の値を取るものとする。

確率変数の組\((X, Y)\)の値が\((x, y)\)となる結合確率分布を\(P(x, y)\)と書く。

組\((X, Y)\)をまとめて考えると、４つの値を取る確率変数\(Z\)のエントロピー\(H(Z)\)として考えることができる。

確率変数\(X\)と\(Y\)の結合エントロピー\(H(X, Y)\)は、

により定義される。これを結合エントロピーと呼ぶ。ただし、\({x_1, x_2, \cdots, x_{M_X}}\)および\({y_1, y_2, \cdots, y_{M_Y}}\)は、それぞれ\(X\)と\(Y\)が取り得る値の集合とする。

結合エントロピーの性質

確率変数\(X\)と\(Y\)の結合エントロピー\(H(X, Y)\)に対し、

が成り立つ。また、\(H(X, Y) = H(X) + H(Y)\)となるのは、\(X\)と\(Y\)が独立のときのみである。

ベイズの定理

情報量とエントロピー(2)

条件付きエントロピー

確率変数\(Y\)で条件を付けた\(X\)の条件付きエントロピー\(H(X|Y)\)は、

により定義される。ただし、\({x_1, x_2, \cdots, x_{M_X}}\)および\({y_1, y_2, \cdots, y_{M_Y}}\)は、それぞれ\(X\)と\(Y\)が取り得る値の集合とする。

条件付きエントロピーの性質

\({x_1, x_2, \cdots, x_{M_X}}\)および\({y_1, y_2, \cdots, y_{M_Y}}\)を取り得る値の集合とする確率変数\(X\)と\(Y\)に関し、以下が成り立つ。

1. \begin{align} H(X|Y) = - \sum_{j = 1}^{M_Y} \sum_{i = 1}^{M_X} P(x_i, y_j) \log_2 P(x_i|y_j) \end{align}
2. \begin{align} H(X, Y) = H(X) + H(Y|X) = H(Y) + H(X|Y) \end{align}
   （この式は、\(H(X)\)と\(H(Y)\)に関するベン図を描くと分かりやすい。）
3. \(0 \leq H(X|Y) \leq H(X)\)（\(H(X|Y) = H(X)\)は、\(X\)と\(Y\)が独立の時のみ成立。）
4. \(0 \leq H(Y|X) \leq H(Y)\)（\(H(Y|X) = H(Y)\)は、\(X\)と\(Y\)が独立の時のみ成立。）

相互情報量と、その性質

確率変数\(X\)と\(Y\)の相互情報量\(I(X;Y)\)は、

によって定義される。

確率変数\(X\)と\(Y\)と相互情報量\(I(X;Y)\)に関して以下が成り立つ。

1. \begin{align} I(X;Y) &= H(X) - H(X|Y) \\ &= H(Y) - H(Y|X) \\ &= H(X) + H(Y) - H(X, Y) \end{align}
2. \(0 \leq I(X;Y) \leq \min {H(X), H(Y)}\)（\(I(X;Y)=0\)は、\(X\)と\(Y\)が独立の時のみ成立。）

シャノンの補助定理

\(p_1, p_2, \cdots, p_M\)および\(q_1, q_2, \cdots, q_M\)を

を満たす任意の非負の数とする（ただし、\(p_i \neq 0\)のときは\(q_i \neq 0\)とする）。このとき、

が成立する。等号は\(q_i = p_i (i = 1, 2, \cdots, M)\)のとき、またそのときに限って成立する。

つまり、確率分布\(P = {p_i}_{i = 1}^{M}\)とちょっと違う分布\(q_i\)（ただし総和が1以下）を持ってきて、\(\log_2\)の内側の\(p_i\)と置き換えると、元より少し大きくなる。

情報源のモデル(1)

離散的\(M\)元情報源

\(M\)個の元からなる記号の有限集合\(A = {a_1, a_2, \cdots, a_M}\)を考える。

\(A\)を情報源アルファベット、各元\(a_i \in A\)を情報源記号と呼ぶ。

時点0より毎時点（時点は整数値）で、\(A\)上の情報源記号を、ある確率に従って１個ずつ出力する。

情報源から出力されるデータ = 情報源記号が並んだ記号列（情報源系列と呼ぶ。）

情報源系列の確率分布

時点0から時点\(n-1\)まで（長さ\(n\)）の情報源系列について、

• 時点\(i\)での情報源の出力を、確率変数\(X_i\)で表す。つまり、\(X_i\)は\(a_1, a_2, \cdots, a_M\)のいずれか
• 情報源系列は\(X_0 X_1 \cdots X_{n-1}\)

\(X_0, X_1, \cdots, X_{n-1}\)の結合確率分布:

\(p(x_0, x_1, \cdots, x_{n-1})\)とも書く。

結合確率分布から、統計的性質は完全に定まる。

情報源の各種モデル

どんなに大きい\(n\)についても、\(X_0, X_1, \cdots, X_{n-1}\)の結合確率分布を与えることができれば、この情報源の統計的性質は完全に記述できる。しかし、一般には困難。

議論を進めるためには、情報源に何らかの扱いやすい性質を仮定する必要がある。

記憶のない情報源

各時点における情報源記号の発生が、他の時点と独立である情報源

記憶のない定常情報源

記憶のない情報源において、各時点における情報源記号の発生が同一の確率分布\(P_X (x)\)に従う情報源

記憶のない定常情報源における長さ\(n\)の系列の結合確率分布は、以下の式で表される。

定常情報源の定義

時間をずらしても、統計的性質の変わらない情報源

定常情報源の出力は、各時点において同一の確率分布に従う。この確率分布を定常分布と呼ぶ。

エルゴード情報源

十分長い任意の出力系列に、その情報源の統計的性質が完全に現れている定常情報源。

エルゴード的であれば、十分に長い任意の系列は必ず一定の統計的性質を満たす。

情報源の各種モデル

記憶のない定常情報源は必ずエルゴード情報源になる。

記憶のある定常情報源でエルゴード的なものはある（例：正規マルコフ情報源）

定常情報源であってもエルゴード的でないものもある。

例：確率\(\frac{1}{2}\)で0だけからなる系列か、1だけからなる系列を発生する情報源

情報理論では、ほとんどの場合、エルゴード情報源を扱う。

マルコフ情報源

マルコフ情報源：記憶のある情報源の基本的なモデル。

\(m\)重マルコフ情報源

系列中の過去\(m\)文字の並びにしたがって、次の文字の生起確率が決まるモデル。

\(m\)重マルコフ情報源の状態遷移図

離散的\(q\)元情報源を考える。これが\(m\)重マルコフ情報源だとする。

\(q^m\)個の状態を持ち、各状態において記号の出力確率が定まっていると見なせる。

出力を一つ発生する度に\(q^m\)個の状態の中を遷移していく。

一般化されたマルコフ情報源

単に、マルコフ情報源と呼ぶ。

「直前の\(m\)個の出力に対応する」という条件をなくし、より抽象的に（自由な状態図で）情報源を定義できる。

マルコフ連鎖モデルともいう。

状態の分類

過渡状態：十分時間が経過すれば抜け出てしまい、戻ることのない状態。

閉じた状態集合：任意の状態から任意の状態へ遷移可能な（矢印でたどっていくことのできる）状態の集合。

既約マルコフ情報源：任意の状態から任意の状態へ遷移可能なマルコフ情報源。

非周期的状態集合：閉じた状態集合で、ある時間が経過した後の任意の時点において、どの状態にある確率も0でないようなもの。

周期的状態集合：閉じた状態集合がいくつかの部分集合に分割され、その各々が周期的な時点においてのみ現れ得るもの。

正規マルコフ情報源：非周期的状態集合のモデルで定義されるマルコフ情報源。十分な時間が経過した後に、定常情報源として扱えて有益。

情報源のモデル(2)

遷移確率行列

\(N\)個の状態\(s_0, s_1, \cdots, s_{N-1}\)を持つ正規マルコフ情報源を考える。

状態遷移の仕方は、状態\(s_i\)にあるとき、次の時点で状態\(s_j\)に遷移する確率\(p_{i,j}=P(s_j|s_i)\)により決まる。これを遷移確率という。

遷移確率\(p_{i, j}\)を\((i, j)\)要素とする\(N \times N\)行列を遷移確率行列と呼ぶ。

行が\(i\)側（現在状態）で、列が\(j\)側（次状態）である。

行ごとに総和が1である。

正規マルコフ情報源の極限分布

正規マルコフ情報源の定義より、\(t > t_0\)となる任意の\(t\)について

が成り立つようなある正定数\(t_0\)が存在する。

正規マルコフ情報源では、\(t \rightarrow \infty\)とするとき、\(p_{i, j}^{(t)}\)は\(i\)には無関係な値に収束する。すなわち、

となる\(u_j\)が存在する。

遷移行列を用いて上式を書き直すと、

となる。ここで、\(U\)はすべての行が\(\mathbf{u} = (u_0, u_1, \cdots, u_{N-1})\)となる\(N \times N\)行列である。

時点\(t\)において状態\(s_j\)にいる確率\(P(s^{(t)} = s_j)\)を\(w_{j}^{(t)}\)で表し、

という\(N\)次元ベクトルを定義する。

時点\(t-1\)で状態\(s_i\)にいる確率が\(w_{i}^{t-1}\)で、状態\(s_i\)にいるときに次の時点で状態\(s_j\)へと遷移する確率が\(p_{i, j}\)であるから、

これを繰り返せば\(\mathbf{w}_{t} = \mathbf{w}_{0} \Pi^{t}\)を得る。ここで、\(\mathbf{w}_0\)は時点0における状態分布（初期分布）である。

\(mathbf{w}_t\)の\(t \rightarrow \infty\)とした極限を極限分布と呼ぶ。

正規マルコフ情報源では、次式が成り立つ。

十分時間が経過すれば、初期分布がどうであれ、状態分布は定常的な確率分布（定常分布）に落ち着く

正規マルコフ情報源が落ち着く定常分布を

とする。\(w_i\)は確率なので、当然ながら

が成り立つ。

ある時点の状態分布が定常的で\(\mathbf{w}\)であるとすれば、次の時点の状態分布も\(\mathbf{w}\)でなければならないので、\(\mathbf{w}\)は

を満たさなければならない。

正規マルコフ情報源の遷移確率行列\(\Pi\)に対しては、この式を満たす\(\mathbf{w}\)が唯一存在し、極限分布と一致する。

情報源の1次エントロピー

次のような\(M\)元定常情報源\(S\)を考える。

• 情報源アルファベット\(A = {a_1, a_2, \cdots, a_M}\)
• 記号\(a_k\)の生起確率\(p_k\)

このとき、

を情報源\(S\)の1次エントロピーと呼ぶ。

記憶のない定常情報源の場合、その1次エントロピーは、情報源からの出力を1個受け取ったときに得られる平均的な情報量と考えることができる。

情報源の\(n\)次エントロピー

長さ\(n\)の系列を考え、その系列全体のエントロピーから1記号あたりのエントロピーを算出することを考える。

\(M\)元情報源の\(n\)個の出力をまとめて1個の記号とみなすと、\(M^n\)元の情報源とみなせる。

これを\(n\)次拡大情報源といい、\(S^n\)で表す。

このとき、

を情報源\(S\)の\(n\)次エントロピーと呼ぶ。

記憶のない定常情報源の場合、その\(n\)次エントロピーは、1次エントロピーと一致する。

情報源のエントロピー

情報源\(S\)の\(n\)次エントロピーの極限

を情報源\(S\)のエントロピーと呼ぶ。

これは、十分長い時間をかけて系列を観測した時の1記号当たりの平均情報量と考えることができる。

記憶のない定常情報源の場合、そのエントロピーは1次エントロピーと一致する。

正規マルコフ情報源のエントロピー

次のような正規マルコフ情報源\(S\)を考える。

• 情報源アルファベット \(a_1, a_2, \cdots, a_M\)
• \(N\)個の状態\(s_0, s_1, \cdots, s_{N-1}\)
• 定常分布\((w_0, w_1, \cdots, w_{N-1})\)
• 状態\(s_i\)にあるときに記号\(a_k\)を発生する確率\(P(a_k | s_i)\)

この情報源\(S\)に対するエントロピー\(H(S)\)は

である。

結局、正規マルコフ情報源\(S\)のエントロピー\(H(S)\)の求め方は以下の通りである。

1. 定常分布を求める
2. 各状態\(s_i\)において、記憶のない情報源とみなし、その場合のエントロピー\(H_{s_i} (S)\)を求める
3. 上で求めたエントロピー\(H_{s_i} (S)\)を、定常分布にしたがった割合で合算する

情報源符号化とその限界

平均符号長とは

情報源符号化の目的の1つは、できるだけ「良い」情報源符号化法を設計することである。

われわれの目的は、通信路をできるだけ効率よく圧縮することであるから、同じ情報系列を平均として短い符号列系に符号化できれば、「良い」符号化となる。

そこで、言い換えると、1情報源あたり符号系列の長さの平均値をできるだけ小さくしたい。これを平均符号長と呼ぶ。

平均符号長の定義

情報源アルファベットが\(\Sigma = {a_1, a_2, \cdots, a_M}\)で、発生確率が\(P(a_i) = p_i (i = 1, 2, \cdots, M)\)で与えられる記憶のない情報源\(S\)を考える。

符号\(C\)によって、情報源記号\(a_1, a_2, \cdots, a_M\)のそれぞれに対応付けられた符号語の長さを\(l_1, l_2, \cdots, l_M\)とする。このとき、1情報源記号当たりの平均符号長は、

で与えられる。

瞬時符号とは

符号化は、一意に復号できても、前から読んで戻せるとは限らない。そこで、符号化は、一意復号可能かどうかだけでなく、前から読んだときに、そのまま後戻りせずに復号可能だと便利である。

符号\(C\)が瞬時符号であるとは、符号化を前から読んでいったときに、ある符号語のパターンが現れたら、それを直ちに復号できるときをいう。そうでない符号を非瞬時符号という。

瞬時符号の条件

ある符号語\(x\)が別の符号語\(y\)の頭の部分のパターンと一致するとき、\(x\)は\(y\)の語頭という。

瞬時符号であるためには、どの符号語も他の符号語の語頭であってはならない。これを語頭条件と呼ぶ。

符号の木と瞬時符号の関係

瞬時符号は、符号語がすべて葉に対応付けられている。非瞬時符号は、葉以外の節点にも対応付けられている。

クラフトの不等式

長さが\(l_1, l_2, \cdots, l_M\)となる\(M\)個の符号語を持つ\(q\)元符号で瞬時符号となるものが存在するための必要十分条件は、

が満たされることである。

※「存在する」としか言っていないことに注意。「この不等式を満たすから瞬時符号」とは言えない。

※実は、一意復号可能である必要十分条件も、この式を満たすことであり、マクラミンの不等式と呼ぶ。

平均符号長\(L\)の限界に関する定理その１

定常分布を持つ情報源\(S\)の各情報源記号を一意復号可能な\(r\)元符号に符号化したとき、その平均符号長\(L\)は

を満たす。また、平均符号長\(L\)が

となる\(r\)元瞬時符号を作ることができる。

平均符号長\(L\)の限界に関する定理その２

情報源\(S\)は、任意の一意復号可能な\(r\)元符号で符号化する場合、その平均符号長\(L\)は、

を満たす。また、任意の正数\(\epsilon > 0\)について平均符号長\(L\)が

となる\(r\)元瞬時符号を作ることができる。

つまり、どんなに工夫しても、平均符号長\(L\)はエントロピー\(H(S)\)までしか改善できない。（2元符号の場合、\(\log_2 r = 1\)）

情報源符号化法(1)

ハフマン符号はなぜ大事か？

ハフマン符号はコンパクト符号である。

コンパクト符号とは、1記号ずつ符号化する際、その平均符号長を最小とする効率の良い符号のこと。

ハフマン符号の作り方

基本アイディア：最も確率が低い2つの情報源記号を繰り返し選んでまとめながら、下から順に符号木を作る。

具体的な手順は以下のとおり。

1. まず、確率の高い順に記号を並び替える。
2. 各記号に対応する符号木の葉を作る。葉には確率を添えてかいておく。
3. 最も確率が小さい葉を2つ選び、それを集約するためのノードを新たに作って枝で結ぶ。そのノードを新しい葉として扱い、元の二つの葉の確率を足し合わせたものを添える。
4. 3. を繰り返して符号木を作る。
5. 各ノードから葉へ向かう方向の2本の枝に、0と1のラベルを割り当てる（割り当て方は任意で良い）。

あとは、構成した符号木を用いて、根から各々の葉へ至るパスをなぞりながら、ラベルの列を符号語として記号に割り当てればよい。

ハフマン符号は数通り作成できる。

符号語が符号の木の葉にだけ割り当てられているハフマン符号は瞬時符号である。

ブロック符号化

1,0をそれぞれ確率0.2, 0.8で発生する記憶のない2元定常情報源からの系列を圧縮したい（確率に偏りがあるので圧縮できるはず）。

情報源の一記号ごとに符号化すると、

（2元情報源）0, 1 → 0, 1（2元符号化）

となって、全く効率が上がらない。

この解決方法として、連続する何個かの情報源符号をまとめて符号化する、というのがある。

一定個数の情報源記号ごとにまとめて符号化する方法をブロック符号化と呼ぶ。

特に、元の情報源\(S\)に対し、\(n\)次拡大情報源\(S^n\)を考え、その上の記号に対してハフマン符号化を行う方法を、ブロックハフマン符号化と呼ぶ。

情報源符号化法(2)

ブロックハフマン符号化の問題点

ブロックハフマン符号化におけるブロック長\(n\)を十分大きくすれば、1情報源記号あたりの平均符号長をいくらでも下限に近づけられる。

しかし、\(n\)を大きくすると、記号の数が急増する。

\(M\)元情報源の場合、符号化すべき長さ\(n\)の情報源系列の数が\(M^n\)個に増大する（ハフマン符号化が困難になる）。

非等長情報系列に対する符号化

符号化すべき情報源系列を非等長にすることを考える。

すなわち、長い情報源系列と短い情報源系列を組み合わせ、長いがよく発生する系列に、より短い符号語を割り当てる。

利点：符号化する情報源系列の数を減らして、符号化のために記憶すべき表を削減できる。

情報源から出力される任意の系列が、一意に分解できなければならない。

分節木を用いた情報源系列の分割

分節木とよばれる木構造を用いて、情報源系列を長さの異なる系列（ブロック）に分割し、各ブロックに対して符号化を行う。分節木の各葉ノードはある1つの系列に対応している。

1記号あたりの平均符号長は、分節木を用いて算出した各ブロックの平均長で、符号木を用いて算出した平均符号長を割ることによって求められる。

ランレングス・ハフマン符号化

系列中に同じ記号が連続するとき、その連続する長さを符号化して送る方法を一般に、ランレングス符号化と呼ぶ。

ランでブロック化してからハフマン符号化する方法を、ランレングス・ハフマン符号化と呼ぶ。

例として、1,0の出現確率が、それぞれ\(p, 1-p\)の無記憶定常情報源\(S\)について、\(N-1\)個までの0のランを符号化することを考える。

つまり、1, 10, 100, 1000, ... という系列を考える。

これら\(N\)個の系列の平均長\(\overline{n}\)は、

これらの系列をハフマン符号化したときの平均符号長\(L_N\)は次を満たす。

よって1記号あたりの平均符号長\(L_r\)は

となる。ブロックハフマン符号化の場合は

である。

ひずみを入れた情報源符号化

通信路でひずみが入るのではなく、符号化時に（わざと）ひずみを入れる。

元の情報量を削って通信することに相当し、そうすることで圧縮率を向上させられる。

どのくらい平均符号長の限界を下げられるか？

1情報源記号あたりの平均符号長の下限 = エントロピー \(H(S)\)だが、ひずみを許した場合、出力\(Y\)の値を知っても、元の入力\(X\)に関してなお平均して\(H(X|Y)\)のあいまいさが残る。

そのため、伝えられる情報の量は\(H(X) - H(X|Y) = I(X;Y)\)となって、ひずみを許した場合の限界は相互情報量で表されることがわかる。

ひずみ測度

ひずみ測度とは、\(x\)と\(y\)の相違を評価する関数\(d(x, y)\)のことである。この関数の値が大きいほど、ひずみが大きい。次の性質を持つ。

ひずみ測度の平均値を平均ひずみと呼び、\(\overline{d}\)で表す。

ひずみ測度の例

例１）情報源アルファベットを\(\Sigma = {0,1}\)とし、ひずみ測度を

とする。このとき、平均ひずみは

となる。これは要するに、符号器の出力が元の情報源の出力と異なる確率であり、通常ビット誤り率と呼ばれる。

例２）情報源アルファベットを有限個の整数または実数の集合とする。このとき、ひずみ測度を\(d(x, y) = |x- y|^2\)とすれば、平均ひずみは2乗平均誤差と呼ばれる量になる。

平均ひずみと相互情報量の関係

相互情報量\(I(X;Y)\)が同じでも、平均ひずみ\(\overline{d}\)は同じとは限らない。

つまり、平均ひずみ\(overline{d}\)が同じでも、\(I(X;Y)\)は符号の仕方で異なる。

ある与えられた値\(D\)に対し、平均ひずみ\(\overline{d}\)が\(\overline{d} \leq D\)を満たす条件下で、あらゆる情報源符号化法を考えたときの相互情報量\(I(X;Y)\)の最小値を考え、これを\(R(D)\)と表す。

すなわち、

これを情報源\(S\)の測度・ひずみ関数と呼ぶ。つまり、これが平均符号長の下限になる。

ひずみが許される場合の情報源符号化定理

平均ひずみ\(\overline{d}\)を\(D\)以下に抑えるという条件の下で、任意の正数\(\epsilon\)に対して、情報源\(S\)を1情報源記号あたりの平均符号長\(L\)が

となるような2元符号へ符号化できる。しかし、どのような符号化を行っても、\(\overline{d} \leq D\)である限り、\(L\)をこの式の左辺より小さくすることはできない。

つまり、1情報源記号当たりの平均符号長が、測度・ひずみ関数\(R(D)\)にいくらでも近づく符号化法が存在する。

通信路のモデル

通信路符号化の考え方

今、自分が、ある通信路を通じて、0と1のビット列で表した情報を相手に送るとする。

しかし、通信路は誤りを起こす可能性がある。

もし送った情報に誤りが入ると、元のデータに戻せなくて、正しくない情報が相手に伝わってしまう。

次のことは可能か？

1. 受け取ったデータを見るだけで、誤りが入っているかどうかがわかる（誤り検出）
2. データに誤りがあるとわかったら、その誤りを除いて、元のデータを復元できる（誤り訂正）

これらは、元のデータに少し「ムダ」を入れて符号化して、少しくらい誤りが入ってもわかるようにすることで、可能となる。

通信路の統計的表現

雑音のある離散的通信路の定義：時点ごとに一つの記号が入力され、一つの記号が出力される。出力は入力から一意に定まるのではなく、確率的に決まる。

つまり、以下のようなイメージ。

\(|A| = |B| = r\)のときは、\(r\)元通信路という。

記憶のない定常通信路

各時点の出力の現れ方が、その時点の入力には関係するが、それ以外の時点の入力と出力とは独立であるような通信路を、記憶のない通信路という。

さらに、時間をずらしても統計的性質が変わらないとき、これを記憶のない定常通信路と呼ぶ。

記憶のない定常通信路では、入力\(X\)が通信路に投入されたときに出力\(Y\)が出る条件付き確率\(P_{Y|X} (y|x)\)が、すべての時点において同一である。したがって、

通信路行列

\(r\)元入力アルファベット\(A = {a_1, a_2, \cdots, a_r}\)、\(s\)元出力アルファベット\(B = {b_1, b_2, \cdots, b_s}\)、入出力の関係が条件付き確率\(p_{ij} = P_{Y|X} (b_j |a_i)\)で与えられる記憶のない定常通信路を考える。

つまり、以下のようなイメージ。

このとき、通信路行列は以下のようにかける。行が入力で、列が出力である。

加法的2元通信路

入力と出力のアルファベットが共に{0,1}であるような2元通信路は、誤りの有無を用いて表すことができる。

\(t\)時点での誤りを確率変数\(E_t \in {0,1}\)で表すと、出力\(Y_t\)は入力\(X_t\)に誤り\(E_t\)を加えたものとみなせる。

• 入力0　→　出力0
• 入力0　→　出力1
• 入力1　→　出力0
• 入力1　→　出力1

誤りの発生は入力と統計的に独立であると仮定される。

ランダム誤り通信路

加法的2元通信路の誤り源\(S_E\)が、1,0をそれぞれ確率\(p, 1-p\)で発生させる記憶のない定常2元情報源とする。このとき、0から1への誤りも、その逆も、他の時点の入出力とは無関係に確率\(p\)で発生する。これは2元対称通信路に他ならない。

このような誤りをランダム誤りといい、誤りの発生確率\(p\)をビット誤り率という。

バースト誤り通信路

誤りが一度生じると、その後しばらくの間は連続して誤りが発生すると考えるモデル（誤り源に記憶がある代表的なモデル）。

密集して生じる誤りをバースト誤りと呼ぶ。

ソリッドバースト誤りの平均長

誤り系列における1の連続（ラン）を任意に一つ取り出し、その長さが\(l\)となる確率\(P_L (l)\)を求めると、

となる。

バースト誤りの長さ（バースト長）の平均値\(\overline{l}\)は次のようになる。

その他のバースト誤りモデル

ギルバートモデル：正誤が混在するバースト誤り

フリッチマンモデル：ギルバートモデルの良状態を増やしたもの

通信路符号化の限界(1)

通信路符号の基礎概念

通信路符号化の目的：信頼性の向上　→　そのために冗長性を付加

長さ\(k\)のブロック\(\mathbf{x} \in \Sigma^k\)を長さ\(n\)の符号語\(\mathbf{w_x} \in A^n\)に符号化（\(A\)は\(r\)元アルファベット）

\(q^k < r^n\)：符号語として\(A^n\)の一部のみ使用（冗長性の付加）

通信路符号：\(A^n\)の中から選ばれた系列の集合\(C\)

情報速度と冗長度

符号\(C\)に含まれる符号語の数を\(M\)とする。

符号\(C\)の情報（伝送）速度\(R\):

• 符号\(C\)を用いて伝達可能な1記号あたりの最大平均情報量
• \(R = \frac{\log_2 M}{n}\)　（ビット/記号）
• 符号語を受け取ることにより得られる最大平均情報量\(\log_2 M\)を符号語の長さ\(n\)で割った値

\(A^n\)に含まれる\(r^n\)個の系列すべてを符号語とすれば、情報速度は最大値

となる。\(R < R_{max}\)とすることで、誤りの訂正や検出が可能となる（すべての系列を使うと、誤りを検知できない）。

情報速度\(R\)の符号\(C\)の効率（符号化率）\(\eta\)と冗長度\(\rho\):

（ただし、\(0 \leq \eta \leq 1, \quad 0 \leq \rho \leq 1\)）が成り立つ。

最尤復号法(1)

\(\mathbf{\Omega_1}, \mathbf{\Omega_2}, \cdots, \mathbf{\Omega_M},\): 符号語\(\mathbf{w_1}, \mathbf{w_2}, \cdots, \mathbf{w_M}\)の復号領域

正しく復号される確率を最大にする復号領域の求め方は、（符号語の発生確率が等確率の場合は）最尤復号法

\(P(\mathbf{y}|\mathbf{w_i})\): \(\mathbf{w_i}\)を送ったとき\(\mathbf{y}\)が受信される確率

最尤復号法：\(\mathbf{y}\)が受信されたとき、\(P(\mathbf{y}|\mathbf{w_i})\)が最大の\(\mathbf{w_i}\)に復号

最尤復号法の復号領域：\(\mathbf{\Omega_i} = \{\mathbf{y} | i = \max_j P(\mathbf{y} | \mathbf{w_j})\}\)

\(P_C(\mathbf{w_i}) = \sum_{\mathbf{y} \in \mathbf{\Omega_i}}\):符号語\(\mathbf{w_i}\)を送った場合に正しく復号される確率

どの符号語が送られてくる確率も等しく\(\frac{1}{M}\)であると仮定すると、正しく復号される確率\(P_C\)は

とかける。\(\mathbf{\Omega_i} = \{\mathbf{y} | i = \max_j P(\mathbf{y} | \mathbf{w_i})\}\)とすれば\(P_C\)が最大になる。

\(\mathbf{w_i}\)を\(\mathbf{y}\)のパラメータだとみなせば、\(P(\mathbf{y} | \mathbf{w_i})\)は\(\mathbf{w_i}\)の尤度である。

尤度を最大化する復号法　→　最尤復号法

最尤復号法は、各符号語が等確率で送られるとき、正しく復号される確率\(P_C\)を最大とするという意味で、最良の復号法である。しかし、すべての符号語\(\mathbf{w_i}\)に対し、\(P(\mathbf{y} | \mathbf{w_i})\)を計算し比較しなければならず、符号語数\(M\)が大きい場合には実用的ではない。

通信路容量

通信路の通信路容量：通信路ごとに定まる、その通信路を介して伝送できる情報速度の限界値。

つまり、その通信路を介して、送ることができる1記号あたりの平均情報量の上限。

\(P_{Y|X}\):定常通信路の定常条件付き確率分布

• 1記号\(X\)を送ると1記号\(Y\)が受信される。→　平均的には1記号あたり相互情報量\(I(X;Y)\)だけ情報が送られる。
• 入力\(X\)の分布は自由に変えることができるが、\(X\)の分布\(P_X\)が定まれば\(Y\)の分布は\(P_X\)と\(P_{Y|X}\)から定まる。

この通信路を介して送ることができる1記号当たりの平均情報量の上限は

以上の考察から、通信路容量\(C\)の定義は\(\max_{P_X} I(X;Y)\)？

• 無記憶通信路の場合はYES。記憶のある通信路の場合はNO。
• 記憶のある通信路の場合、\(n\)（nは1より大きい）記号ごとにみるともっと多くの情報を送れる。

\(P_{Y_n | X_n}\)：定常通信路の定常条件付き確率分布

• \(n\)記号\(X_n\)を送ると\(n\)記号\(Y_n\)が受信される。→　平均的には1記号あたり相互情報量\(\frac{I(X_n;Y_n)}{n}\)だけ情報が送られる。
• 入力\(X_n\)の分布は自由に変えることができるが、\(X_n\)の分布\(P_{X_n}\)が定まれば\(Y_n\)の分布は\(P_{X_n}\)と\(P_{Y_n | X_n}\)から定まる。

この通信路を介して送ることができる1記号当たりの平均情報量の上限は

長さ\(n\)の入力系列\(X_n\)に対する通信路の出力系列\(Y_n\)に対し、

で定義される\(C\)を通信路容量と呼ぶ。

通信路容量の単位：ビットあるいはビット/通信路記号

入力記号\(X\)に対し記号\(Y\)が出力される記憶のない通信路の通信路容量は\(C=\max_{P_X} I(X;Y)\)で計算できる。

通信路符号化の限界(2)

記憶のない一様通信路の通信路容量

各時刻に\(r\)元アルファベットに属する記号\(X\)を入力し、\(s\)元アルファベットに属する記号\(Y\)を出力する、入力について一様な記憶のない定常通信路容量を\(C\)とする。

この通信路の通信路行列の各行の要素の集合を{\(p_1, p_2, \cdots, p_s\)}とすれば、

が成り立つ。通信路が2重に一様であれば、

が成り立つ。

記憶のない定常通信路が入力（出力）について一様 \(\overset{\mathrm{def}}{\iff}\) 通信と行列のどの行（列）も同じ要素を並び替えたものになっている。

記憶のない定常通信路が2重に一様 \(\overset{\mathrm{def}}{\iff}\) 通信路が入力について一様かつ出力について一様。

例：2元対称通信路

加法的2元通信路の通信路容量

誤り源\(S_E\)により定義される加法的2元通信路の通信路容量\(C\)は

である。

誤り源\(S_E\)により定義される加法的2元通信路

• 通信路内の誤り源\(S_E\)が各時刻に\(E \in {0,1}\)を発生。
• 通信路の各時刻の入力\(X \in {0,1}\)に対し出力\(Y \in {0,1}\)は\(Y = X \oplus E\)により定まる。
• \(X\)と\(E\)は独立
• 誤り源\(S_E\)が記憶のある定常情報源のとき加法的2元通信路は記憶のある定常通信路となる。

誤り源が無記憶定常情報源の場合

このとき、加法的2元通信路は2元対称通信路になる。

\(P(E = 1) = p, P(E = 0) = 1-p\)とすれば、

よって、\(C = 1 - H(S_E)\)を用いて、

通信路容量と情報速度の関係についての考察

情報速度\(R \overset{\mathrm{def}}{\iff}\)通信路符号系列に埋め込まれた1通信路記号あたりの平均情報量（ビット/記号）

通信路容量\(C \overset{\mathrm{def}}{\iff}\)通信路を介して伝送できる1通信路記号あたり平均情報量（ビット/記号）

情報速度\(R\) \(<\) 通信路容量\(C\)であれば情報をすべて送ることができるのでは？　→　復号誤り率を0にできるということ？

通信路符号化定理

通信路容量は\(C\)である通信路に対し、\(R < C\)であれば、情報速度\(R\)の符号で復号誤り率がいくらでも小さいものが存在する。\(R>C\)であれば、そのような符号は存在しない。

通信の限界

エントロピーが\(H(S)\)（ビット/情報源記号）情報源と通信路容量は\(C\)（ビット/情報源記号）の通信路の通信システムは全体としてどれだけ効率的に信頼性高く情報が伝送できるか？

情報源から情報源記号が毎秒α個発生し、通信路では毎秒β個の通信路記号が伝送されているとする。

このとき、情報源からは\(\mathcal{R} = \alpha H(S)\)（ビット/秒）の速度で情報が発生する。

また、通信路容量は1秒あたり\(\mathcal{C} = \beta C\)（ビット/秒）となる。

もし、\(\mathcal{R} < \mathcal{C}\)ならば、任意に小さい誤り率で情報を宛先まで送ることができる。

しかし、\(\mathcal{R} > \mathcal{C}\)の場合は、ひずみが生じる。

情報源\(S\)の速度・ひずみ関数を\(R(D)\)（ビット/情報源記号）とし、\(\alpha R(D*) = \mathcal{C}\)を満たす\(D^*\)を考える。

このとき、任意の\(\epsilon > 0\)に対し、\(\alpha R(D^* + \epsilon) < \alpha R(D^*) = \mathcal{C}\)が成り立つ。

このとき、通信路符号化定理より、情報速度\(R(D* + \epsilon)\)の符号でいくらでも復号誤り率が小さな符号が存在するので、\(D^* + \epsilon\)にいくらでも近い平均ひずみで情報を送ることができる。

これは、任意の\(\epsilon > 0\)について成り立つので、\(D^*\)にいくらでも近い平均ひずみで情報を送ることができる。

情報速度\(\mathcal{R}\)（ビット/秒）で発生する情報を、通信路容量（\(\mathcal{C}\)ビット/秒）の通信路を介して送るとき、\(\mathcal{R} < \mathcal{C}\)であれば、任意に小さい誤り率で情報を伝送できる。

また、\(\mathcal{R} > \mathcal{C}\)であれば、情報源の速度・ひずみ関数の値が\(\mathcal{R}(D^*) = \mathcal{C}\)（ビット/秒）を満たす\(D^*\)に対し、\(D^*\)に任意に近い平均ひずみで情報を伝送できるが、\(D^*\)より小さい平均ひずみでは伝送できない。

通信路符号化法

単一パリティ検査符号の定義

問題：0,1からなる長さ\(k\)の系列\(x_1, x_2, \cdots, x_k\)を2元通信路を介して伝送したい。1個の誤りが生じた場合、それを検出するにはどうすればよいか？

単一パリティ検査符号：系列\(x_1, x_2, \cdots, x_k\)を、含まれる1の個数が偶数になるように、もう一つ記号\(c\)を付け加えた符号語\(\mathbf{w} = x_1 x_2 \cdots x_k c\)に対応させる符号化

このとき、加える符号\(c\)は、\(c = x_1 + x_2 + \cdots + x_k\)とかける。ただし、+ は排他的論理和\(\oplus\)である。

符号語\(\mathbf{w} = x_1 x_2 \cdots x_k c\)について、\(x_1 x_2 \cdots x_k\)の部分は情報記号、\(c\)は（パリティ）検査記号という。

符号語は\(\mathbf{w} = (x_1, x_2, \cdots, x_k, c)\)とベクトルの形で表すこともある。

単一パリティ検査符号の性質

• 長さ\(k\)の系列を入力とする単一パリティ検査符号
• 符号長\(n = k + 1\)、符号語数\(M = 2^k\)→情報速度\(R = \frac{k}{k+1}\)
• 一つの誤りの検出が可能な誤り検出符号
• \((k+1, k)\)組織符号
• 線形符号

組織符号

組織符号：\(k\)個の情報記号から、\(n - k\)個の検査記号を一定の方法で求め、付加することにより符号化される符号長\(n\)の符号

\(n, k\)符号：符号長\(n\)、情報記号数\(k\)の組織符号

\((n, k)\)符号の効率は、

である。

単一パリティ検査符号は\((k + 1, k)\)符号であり、効率は\(\eta = \frac{k}{k+1}\)である。

線形符号

\(c = x_1 + x_2 + \cdots + x_k\)のように、検査記号が情報記号の線形な式で与えられる符号

線形符号の最も基本的な性質：「任意の2つの符号語について、その成分ごとの和をとると、それがまた符号語になる。」（線形符号となるための必要十分条件）

パリティ検査方程式

= 0 という形で線形符号の符号語となるための必要十分条件を与える式（または式の組）

単一パリティ検査符号のパリティ検査方程式：長さ\(n\)の系列\(\mathbf{w} = (w_1, w_2, \cdots, w_n)\)が単一パリティ検査符号の符号語となるための必要十分条件は以下のパリティ検査方程式を満たすことである。

（符号語に含まれる1の個数が偶数）

シンドローム

誤りパターン：送信した符号語\(\mathbf{w} = (w_1, w_2, \cdots, w_n)\)と受信語\(\mathbf{y} = (y_1, y_2, \cdots, y_n)\)との差

誤りパターン\(\mathbf{e} = (e_1, e_2, \cdots, e_n)\)の各ビットは以下のような値になる。

誤りパターン\(\mathbf{e}\)を用いると\(\mathbf{y} = \mathbf{w} + \mathbf{e}\)と表現できる。

シンドローム：受信語\(\mathbf{y}\)をパリティ検査方程式の左辺に代入した結果\(\mathbf{s} = y_1 + y_2 + \cdots + y_n\)

符号語\(\mathbf{w}\)はパリティ検査方程式を満たすので、

\(2 \times 2\)水平垂直パリティ検査符号

与えられた長さ4の系列\(x_1 x_2 x_3 x_4\)に対し、長さ9の符号語\((x_1, x_2, x_3, x_4, c_1, c_2, c_3, c_4, c_5)\)を、以下のように生成する符号。

下の表のように4個の情報ビットを\(2 \times 2\)の配列に並べ、各行各列に一つずつ検査ビットを付け加える。

すなわち、

さらに、検査ビットの行の1の数が偶数になるように、検査ビットの検査ビットを右隅におく。

\(2 \times 2\)水平垂直パリティ検査符号の性質

符号長\(n = 9\)、情報記号長4の\((9, 4)\)組織符号である。

符号語数\(M = 2^4\)であるから、情報速度\(R = \frac{\log_2 M}{n} = \frac{4}{9}\)、効率\(\eta = \frac{4}{9}\)

検査符号が情報記号の線形式で計算できるので線形符号である。

パリティ検査方程式：長さ9の系列\(\mathbf{w} = (w_1, w_2, \cdots, w_9)\)に対し

シンドローム：受信語\(\mathbf{y} = (y_1, y_2, \cdots, y_9)\)に対するシンドローム\(\mathbf{s} = (s_1, s_2, \cdots, s_5)\)

\(2 \times 2\)水平垂直パリティ検査符号の誤り訂正能力

誤り訂正まで行える誤り（検出）訂正符号

1個の誤りが訂正でき、同時に2個の誤りを検出することができる（検出のみに徹すれば、3個の誤りまで検出することが可能）。

一般の水平垂直パリティ検査符号

符号長\(n = (m_1 + 1)(m_2 + 1)\)、情報記号長\(k = m_1 m_2\)の\(((m_1 + 1)(m_2 + 1), m_1 m_2)\)組織記号

符号語数\(M = 2^{m_1 m_2}\)、情報速度\(R = \frac{\log_2 M}{n} = \frac{m_1 m_2}{(m_1 + 1)(m_2 + 1)}\)、効率\(\eta = \frac{m_1 m_2}{(m_1 + 1)(m_2 + 1)}\)

誤り（検出）訂正符号

訂正をする場合：1個の誤り訂正ができ、同時に2個の誤りまで検出可能。

訂正しない場合：3個の誤りまで検出可能

通信路符号化法

ハミング符号(1)

水平垂直パリティ検査符号の問題点：(9,4)符号であり、情報ビットよりも検査ビットが多く、効率がよくない。

(7,4)ハミング符号：4個の情報ビット\(x_1, x_2, x_3, x_4\)に対し、

により、検査ビット\(c_1, c_2, c_3\)を作り、\(w = (x_1, x_2, x_3, x_4, c_1, c_2, c_3)\)という符号語に符号化する符号。

情報ビットが4個であるから、符号語は\(2^4 = 16個\)

符号を\(\mathbf{w} = (w_1, w_2, \cdots, w_7)\)とする。

(7,4)ハミング符号のパリティ検査方程式

受信語\(\mathbf{y} = (y_1, y_2, \cdots, y_7)\)に対するシンドローム

誤りパターンを\(e = (e_1, e_2, \cdots, e_7)\)とすると、

生成行列

(7,4)のハミング符号の符号語\(\mathbf{w}\)は情報記号のみで表すと

という形でかける。ここで、

という行列を考えれば、符号語\(w\)を\(\mathbf{w} = \mathbf{x} G\)と書くことができる。ただし、\(\mathbf{x} = (x_1, x_2, x_3, x_4)\)である。

生成行列：\(k\)個の情報記号からなるベクトル\(\mathbf{x}\)をかけたとき、対応する符号語が生成されるような行列。

\((n, k)\)線形符号の生成行列は\(k \times n\)行列となる。

検査行列

(7,4)ハミング符号のパリティ検査方程式の係数行列\(\mathbf{H}\)

これを用いれば、パリティ検査方程式は\(\mathbf{w} \mathbf{H}^T = 0\)とかける。

\((n, k)\)線形符号のパリティ検査行列は\((n-k) \times n\)行列

検査行列\(\mathbf{H}\)を用いれば、(7,4)ハミング符号のシンドロームの計算式は\(\mathbf{s} = \mathbf{y} \mathbf{H}^T\)とかける。

ここで、\(\mathbf{s} = (s_1, s_2, s_3)\)であり、シンドロームパターンまたは単にシンドロームと呼ばれる。

ハミング距離とハミング重み

2つの\(n\)次元ベクトル\(\mathbf{u} = (u_1, u_2, \cdots, u_n), \mathbf{v} = (v_1, v_2, \cdots, v_n)\)間のハミング距離\(d_H (\mathbf{u} ,\mathbf{v})\)

\(d_H (\mathbf{u}, \mathbf{v})\)は\(\mathbf{u}\)と\(\mathbf{v}\)の対応する位置にある成分の対のうち、互いに異なるものの数。

ハミング距離は距離の3公理を満たす。

距離の3公理：任意の\(n\)次元ベクトル\(\mathbf{v_1, v_2, v_3}\)に対して以下のことが成り立つ。

1. \(d_H (\mathbf{v_1, v_2}) \geq 0\)であり、等号が成立するのは\(\mathbf{v_1} = \mathbf{v_2}\)のときに限る。
2. \(d_H (\mathbf{v_1, v_2}) = d_H (\mathbf{v_2, v_1})\)
3. \(d_H (\mathbf{v_1, v_2}) + d_H (\mathbf{v_2, v_3}) \geq d_H (\mathbf{v_1, v_3})\)（三角不等式）

\(n\)次元ベクトル\(v\)のハミング重み\(w_H (\mathbf{v}) \overset{\mathrm{def}}{\iff} w_H (\mathbf{v}) = d_H (\mathbf{v, 0})\)

\(w_H (\mathbf{v})\)は\(\mathbf{v}\)の0でない成分の数

ハミング距離はハミング重みを用いて次のように表せる。

最小距離と誤り訂正能力

符号\(C\)の最小ハミング距離または最小距離\(d_{min} \overset{\mathrm{def}}{\iff} d_{min} = \min_{u \neq v} d_H (\mathbf{u, v})\)

限界距離復号法：式\(d_{min} \geq 2t_1 + 1\)を満たす整数\(t_1\)を定め、\(t_1\)以下の誤り訂正を行う復号法。

\(t_1\)の最大値\(t_0 = \lfloor (d_{min}- 1)/2 \rfloor\)を誤り訂正能力という。

\(t_2 = d_{min} - 2t_1 - 1\)とおけば\(t_1 + 1 \leq t \leq t_1 + t_2\)個の誤りは訂正できないが検出は可能。

\(0 \leq t_1 \leq t_0\)をどのように選ぶかは重要な問題。

\(t_1\)を大きくする　→　正しく復号される確率は増大するが、誤って復号される確率も増大

検出さえできれば、再送要求などの救済措置が可能

例）\(d_{min} = 5\)の符号による誤りの訂正と検出

線形符号の最小距離 = 最小ハミング重み（0でない符号語のハミング重みの最小値）

例）(7,4)ハミング符号の場合：最小距離\(d_{min} =\)最小ハミング重み\(= 3\)

通信路符号化法(3)

巡回符号の特徴

• 組織符号・線形符号
• 符号化・シンドローム計算の装置化が容易
• 誤り検出能力に優れる

最も実用的な線形符号

巡回符号の定義

符号多項式：符号語の多項式表現

0,1からなる長さ\(n\)の符号語\(\mathbf{v} = (v_{n-1}, v_{n-2}, \cdots, v_1, v_0)\)を

で表す（係数は0か1しか取らない）。

符号長\(n\)の符号は、\(n-1\)次以下の多項式の集合として表せる。

巡回符号：定数項が1の\(m\)次の多項式

の\(n-1\)次以下の倍多項式（\(W(x) = A(x) G(x)\)という形の符号多項式）すべての集合\(C\)

巡回符号の例

\(G(x) = x^4 + x^3 + x^2 + 1\)によって作られる長さ7の符号\(C\)

符号多項式\(W(x) = w_6 x^6 + \cdots + w_1 x + w_0\)

および符号語\(\mathbf{w} = (w_6, \cdots, w_1, w_0)\)

\(A(x)\)と\(G(x)\)の乗算：ひっ算して足し算するときに、項が偶数個だと消える（繰り上がらない）ことに注意。

巡回符号\(C\)は\(G(x)\)によって生成される　→　\(G(x)\)：\(C\)の生成多項式

巡回符号は線形符号

線形符号となるための必要十分条件：任意の二つの符号語の和が符号語

巡回符号\(C\)が線形符号かどうか

1. \(W_1 (x)\)と\(W_2 (x)\)は\(C\)の符号多項式
2. \(W_1 (x) = A_1 (x) G(x), \quad W_2 (x) = A_2 (x) G(x)\)とかける
3. \(W_1 (x) + W_2 (x) = [A_1 (x) + A_2 (x)] G(x)\)
4. \(W_1 (x) + W_2 (x)\)は\(C\)の符号多項式

線形符号である　→　検査符号が情報記号の線形式でかける　→　組織符号の形で符号語を作ることができる

巡回符号の組織符号化法

\(n-m\)個の情報ビット列\(x_{n-m-1}, \cdots, x_1, x_0\)を\(C\)の符号語に組織符号化する方法

1. 情報ビット列を係数とする多項式
   \begin{align} X(x) = x_{n-m-1} x^{n-m-1} + \cdots + x_1 x + x_0 \end{align}
   に\(x^m\)をかけ、それを\(m\)次の\(G(x)\)で割った剰余多項式
   \begin{align} C(x) = c_{m-1} x^{m-1} + \cdots + c_1 x + c_0 \end{align}
   を計算。\(C(x)\)は
   \begin{align} X(x) x^m = A(x) G(x) + C(x) \quad \text{(1)} \end{align}
   となる\(m-1\)次以下の多項式。
2. \begin{align} W(x) = X(x) x^m - C(x) = X(x) x^m + C(x) \end{align}
   により\(W(x)\)を計算。 式(1)から\(W(x) = A(x) G(x) \Rightarrow W(x)\)は\(C\)の符号多項式
   \(W(x)\)のベクトル表現：
   \begin{align} \mathbf{w} = (x_{n-m-1}, \cdots, x_1, x_0, c_{m-1}, \cdots, c_1, c_0) \end{align}

符号化の例

生成多項式：\(G(x) = x^4 + x^3 + x^2 + 1\)、符号長：\(n = 7\)、情報ビット数：\(k = 3\)（生成多項式は4次なので、\(7-4=3\)）

情報ビット101の符号化

1. 情報ビットを係数とする多項式：\(X(x) = x^2 + 1\)
2. \(x^{n-k} = x^4\)をかける：\(X(x) x^4 = x^6 + x^4\)
3. \(G(x)\)で割った剰余：\(C(x) = x + 1\)
4. 符号多項式：
   \(W(x) = X(x) x^4 + C(x) = x^6 + x^4 + x + 1\)
5. 符号語：1010011

なぜ「巡回」なのか？

符号長\(n\)、生成多項式\(G(x)\)の巡回符号において、\(G(x)\)が\(x^n - 1\)を割りきれば符号語\(\mathbf{w}\)の成分を巡回置換して得られる\(\mathbf{w'}\)も符号語となる。

\(G(x)\)が\(x^n - 1\)を割り切れば

が符号多項式。

という多項式もまた符号多項式。

本来、長さ\(n\)の巡回符号の生成多項式\(G(x)\)は\(x^n -1\)を割り切らなければならない（厳密には、成立しないものを擬巡回符号と呼ぶ）。

\(G(x)\)で生成される符号は、\(G(x)\)が\(x^n -1\)を割り切らなくても、ほとんど同様に扱えるため、ここでは擬巡回符号も含めて、単に巡回符号と呼ぶ。

\(G(x)\)の周期

多項式\(G(x)\)の周期：\(G(x)\)が\(x^n - 1\)を割り切る最小の正整数\(n\)

\(G(x)\)で生成される巡回符号\(C\)の符号長\(n\)は、通常、\(G(x)\)の周期\(p\)以下に選ばれる。

\(n > p\)であると、誤り訂正できない。

例）\(G(x) = x^4 + x^3 + x^2 + 1\)を生成多項式とする長さ7の巡回符号：\(G(x)\)の周期は7（∵\(G(x)\)は\(x^7 - 1\)を割り切るが、\(x^l - 1 \quad (l = 1,2,\cdots,6)\)は割り切らない）。

巡回符号の最小距離

定理：周期\(p\)の生成多項式\(G(x)\)による符号長\(n\)の巡回符号の最小ハミング距離\(d_{min}\)は、\(n \leq p\)であれば3以上である。

巡回符号による誤りの検出

誤りの検出：受信語\(\mathbf{y}\)が符号語になるかどうか調べる。

\(n - 1\)次以下の多項式\(Y(x)\)が長さ\(n\)、生成多項式\(G(x)\)の巡回符号の符号多項式　⇔　\(Y(x)\)が\(G(x)\)で割り切れる

巡回冗長検査方式：受信語\(\mathbf{y} = (y_{n-1}, \cdots, y_1, y_0)\)を表す多項式

が\(G(x)\)で割り切れない（受信語を\(G(x)\)で割る割り算回路に読み込ませて、剰余が0にならない）　→　誤りがある

巡回ハミング符号

0,1を係数とする\(m\)次の多項式の周期\(\leq 2^m -1\)

原始多項式：周期がちょうど\(2^m - 1\)となる\(m\)次の多項式

巡回ハミング符号：\(m\)次の原始多項式を生成多項式とする符号長\(n = 2^m - 1\)の符号

• 符号長：\(n = 2^m - 1\)
• 情報ビット数：\(k = 2^m - 1 - m\)
• 検査ビット数：\(m\)
• 最小距離：\(d_{min} = 3\)　→　単一誤り訂正符号

（これらの特徴はハミング符号と同じ）

巡回ハミング符号の例

\(G(x) = x^3 + x + 1\)を生成多項式とする長さ7の巡回ハミング符号

この符号の検査行列を求める。

\(R_i (x) : x^i (i = 0, 1, \cdots, 6)\)を\(G(x)\)で割った剰余多項式

これを実際に計算すると表のようになる。

\(W(x) = w_6 x^6 + \cdots + w_1 x + w_0\)が\(G(x)\)で割り切れる　⇔　\(w_i x^i\)を\(G(x)\)で割った剰余多項式の和が0　⇔　\(\sum_{i = 0}^{6} w_i R_i (x) = 0\)

この式の左辺を\(x\)の\(2, 1, 0\)次の項の係数ごとに書けば、

となる。この係数行列は

となって、\(H\)は(7,4)ハミング符号の検査行列になる。

演習