各種符号の作り方復習（詳細解説）
1. ハフマン符号の作り方
ハフマン符号は、情報源の各記号の出現確率に基づいて最適なプレフィックス符号を作る手法です。
- 各記号の確率を降順に並べる。確率が高い記号ほど短い符号語になる。
- 確率の小さいもの同士を合成し、2分木を構築。合成した確率を新しいノードとして再度並べる。
- 木の根から葉まで、左枝に0、右枝に1を割り当てて符号語を決定。
- 例：A(0.5), B(0.25), C(0.25) → A:0, B:10, C:11
【具体例1】情報源 $S=\{A,B,C\}$, $P(A)=0.5$, $P(B)=0.3$, $P(C)=0.2$ の場合
符号語： A:0, B:10, C:11
符号化例： S = ABAC → 0 10 0 11
【具体例2】符号語が長くなる場合（4記号・確率が小さい記号）
例： S = \{A,B,C,D\}, P(A)=0.2, P(B)=0.2, P(C)=0.4, P(D)=0.2
符号語： A:00, B:01, C:10, D:11
符号化例： S = DAB → 11 00 01（Dが最長）
ポイント： 確率が小さい記号ほど符号語が長くなる。記号数が増えるほど、最長符号語の長さも増加。
2. 算術符号の作り方
算術符号は、記号列全体を区間 [0,1) の中の1つの値で表現する手法です。
- 記号ごとに区間 [0,1) を確率に応じて分割。
- 符号化する記号列に従い、区間を細分化していく。
- 最終的な区間内の任意の値（小数）を符号語とする。復号時はこの値から元の記号列を再現。
- 例：A(0.5), B(0.3), C(0.2) の場合、A→[0,0.5)、B→[0.5,0.8)、C→[0.8,1)
【具体例】情報源 $S=\{A,B,C\}$, $P(A)=0.5$, $P(B)=0.3$, $P(C)=0.2$ の場合
区間分割：
A: [0, 0.5), B: [0.5, 0.8), C: [0.8, 1)
符号化例： S = ABAC の場合
1. 最初A → [0,0.5)
2. 次B → [0,0.5)の中をBの確率で分割 → [0.25,0.4)
3. 次A → [0.25,0.4)の中をAの確率で分割 → [0.25,0.325)
4. 次C → [0.25,0.325)の中をCの確率で分割 → [0.31,0.325)
最終区間： [0.31, 0.325) の任意の値（例：0.32）を符号語とする。
ポイント： 小数確率でも理論限界に近い平均符号長が得られる。
3. ランレングス符号の作り方
ランレングス符号は、連続する同じ記号の回数をまとめて符号化する手法です。
- 連続する同じ記号の回数（ラン）を数える。
- 記号と回数のペアで符号化。例：AAAAABBB → (A,5),(B,3)
- 復号時はペア情報から元の記号列を再現。
【具体例】情報源 $S=\{A,B,C\}$ の場合
符号化例： S = AAABBBCCAA → (A,3), (B,3), (C,2), (A,2)
符号語： 各ペアをバイナリや可変長符号で表現。
ポイント： 繰り返しの多いデータで特に有効。画像圧縮やFAXなどで利用される。
4. LZ符号（辞書型符号）の作り方
LZ符号は、既出のパターンを辞書に登録し、繰り返し部分を効率的に符号化する手法です。
- 新しいパターンが現れたら辞書に追加。
- 既出パターンは辞書のインデックスと新記号で符号化。
- 例：ABABAB → (0,A),(0,B),(1,2)（LZ78の場合）
【具体例】情報源 $S=\{A,B,C\}$ の場合
符号化例： S = ABABACAB
1. (0,A) → 辞書にA追加
2. (0,B) → 辞書にB追加
3. (1,A) → AB（辞書1番目＋A）追加
4. (2,C) → BA＋C追加
5. (3,A) → AB＋A追加
符号語： (0,A),(0,B),(1,A),(2,C),(3,A)
ポイント： テキストやバイナリデータの圧縮で広く使われる。ZIPやPNGの基礎技術。
5. 拡大情報源記号の符号化
拡大情報源記号は、複数記号をまとめて新しい記号集合を作り、最適符号化を行う手法です。
- 元の情報源の記号を2個、3個…とまとめて新しい記号集合を作る。
- 新しい記号集合に対してハフマン符号などを適用。
- 例：A,Bの2記号拡大 → AA,AB,BA,BB
【具体例】情報源 $S=\{A,B,C\}$ の2記号拡大
拡大記号集合： AA, AB, AC, BA, BB, BC, CA, CB, CC
符号化例： S = ABAC → AB, AC
符号語： 拡大記号集合にハフマン符号などを適用して符号語を割り当てる。
ポイント： 拡大するほど平均符号長がエントロピーに近づく。マルコフ情報源など依存関係のある場合にも有効。
6. 線形符号・ハミング符号の作り方
線形符号・ハミング符号は、生成行列や検査行列を使って誤り検出・訂正ができる符号です。
- 生成行列 $G$ を使って情報ブロックから符号語を作る。$w = uG$
- 検査行列 $H$ で受信語の誤りを検出。シンドローム $s = yH^T$ を計算。
- シンドロームの値から誤り位置を特定し、訂正する。
- 例：ハミング(7,4)符号では、3ビット誤り検出・1ビット訂正が可能。
【具体例】情報源 $S=\{A,B,C\}$ を2ビットで表現し、ハミング(7,4)符号で符号化
情報ブロック： 例：A=00, B=01, C=10
生成行列 $G$： $G = \begin{pmatrix}1&0&0&0&1&1&0\\0&1&0&0&1&0&1\\0&0&1&0&0&1&1\\0&0&0&1&1&1&1\end{pmatrix}$
符号語： $w = uG$
例：A(00) → $w = 0000000$, B(01) → $w = 0101011$, C(10) → $w = 1001101$
誤り検出： 受信語 $y$ に対し $s = yH^T$ を計算。$s$ から誤り位置を特定し訂正。
ポイント： 通信路の誤り検出・訂正に不可欠。生成行列・検査行列の設計が重要。