情報源符号化

1. 情報源の記号は、
   二進数
   に符号化する必要があります。
2. 平均符号長を最小化する必要があります。
3. 冗長性の除去$\rightarrow$ビットレートの削減につながります。

• アルファベット$S = \{s_0, s_1, \ldots, s_k\}$に基づく離散無記憶情報源を考えます。
• $s_i$の確率は$p_{i}$です。
• $s_i$の符号長は$l_i$です。
• 平均符号長、つまり一記号当たりの平均ビット数は$L = \sum_{k=0}^{K-1} p_k \cdot l_k$です。

• $L$が取り得る最小値は$L_{min}$です。
• 情報源の符号化効率は$\eta=\frac{L_{min}}{L}$です。

• データ圧縮
  1. 送信前に、冗長な情報を取り除きます。
  2. 可逆的なデータ圧縮です。
  3. 離散無記憶情報源（discrete memoryless source）の出力を表す情報源符号は、一意に復号できます。

ほかの符号の接頭辞にならない

可変長の情報源符号です。

• 接頭符号の性質
  1. 接頭符号は、一意に復号できます。
  2. 逆は必ずしも成り立ちません。一意に復号できる符号が、すべて接頭符号であるとは限りません。

• 確率の総和：$1 = \sum_{k=0}^{K-1} p_k = \sum_{k=0}^{K-1} 2^{-l_k}$
• 平均符号長：$L = \sum_{k=0}^{K-1} p_k \cdot l_k = \sum_{k=0}^{K-1} 2^{-l_k} \cdot l_k$

1. 記号の確率を大きい順に並べ、木の葉ノードとみなします。
2. ノードをまとめていく間、次の処理を繰り返します。
   • 最も確率の低い二つのノードを選び、低いほうに0、高いほうに1を割り当てます。逆でも構いませんが、一貫している必要があります。
   • 二つを統合して新しいノードを作ります。その確率は、元の二つの確率の和です。
   • 手順1へ戻ります。
3. 各記号について、葉から根までの経路をたどり、二進符号を作ります。
   • 葉ノードのビットは、符号語（codeword）の最後のビットになります。

• 分散は、符号語の長さのばらつきを表します。
  $\sigma^2 = \sum_{k=0}^{K-1} p_k (l_k - \overline{L})^2$
• 誤りを避けるため、
  分散の大きい
  ハフマン木を選びます。
  → 分散が大きい木では符号長がより多様になるため、誤りに対応しやすくなります。

• 分散の大きい木は、誤りに対応しやすいという特徴があります。