情報理論のキーワード

方針

重要な知識は簡単に記述する．

調べたらでてくることは単語だけ書いておく．

本編

第1章 情報伝送の基礎知識

情報理論におけるビットとは実質的な価値としての情報の量を数値化したもの．

符号化において，固定長だと分かりやすいが高能率化できない．可変長だと発生頻度の高い記号に短い符号，発生頻度の低い記号に長い符号を割り当てることで高能率化できるようになる．

情報源符号化は，別名高能率符号化やデータ圧縮と呼ばれる．符号を短くする．

通信路符号化は，別名高信頼符号化や誤り検出・訂正符号化と呼ばれる．符号は長くなる．

伝送路符号化は，デバイスに適した電気信号へ変換すること．

情報源符号化と通信路符号化はバランスが重要．

符号誤りの程度は次の式で表せられる．

ビット誤り率$BER=\frac{誤って受信されたビット数}{送信した全ビット数}$

伝送速度bpsは1秒間に送れるビット数．

通信路容量は1秒間に伝送できる情報量もbpsで表す．

第2章 情報量の数値化

情報量は，ある事柄に関して事前にもっている確率に関係し，事前の確率が小さいほど，それが生じた場合の情報量が大きい．確率が1のときは情報量0．確率が0のときは情報量$\infty$．

情報量の加法性とは，2つの独立した事象から得られる情報量は，おのおのから単独に得られる情報量の和になるという考え．

この条件を満たす定義式は以下のようになる．この定義式は自己情報量という．ただし$p$は事前確率とする．

$I(p)=-\log_2{p}$[bit]

また，以下のように定義してもよい．

$I(p)=-\log_2{\frac{事後確率}{事前確率}}$[bit]

平均情報量，別名エントロピーは以下の式で表せられる．単に情報量ということもできる．

$H=-\sum_{i=1}^{N}p_i\log_{2}p_i$[ビット/シンボル]

エントロピーは情報に関する価値の尺度になっている．$N$種類の記号あり，全記号が等確率の場合にエントロピーが最大になる．

$H_{max}=-\sum_{i=1}^{N}p_i\log_{2}p_i=-N*\frac{1}{N}log_2\frac{1}{N}=log_2N$[ビット/シンボル]

エントロピー値と最大エントロピーとの差は，情報量をもたない無駄な部分であり，その割合と冗長度という．

$r=1-\frac{H}{H_{max}}$

以下の式を相対エントロピーといい，意味のある情報量の割合である．

$h=\frac{H}{H_{max}}$

第3章 情報源符号化

符号化の条件は以下の3つである．

1. 一意的に復元可能であること
2. 瞬時符号であること : 1記号分の長さの符号を受信すれば，あとの符号によらず直ちに復号できること
3. 平均の符号長が短いこと

瞬時符号であるかどうかは符号の木を作ればよい．瞬時符号の必要十分条件は，すべての符号が葉に割り当てられることである．

一意に復号可能で瞬時符号であるかどうかはクラフトの不等式を満たすか調べればよい．
クラフト不等式は各記号に対応する符号長を$L_i$ビットとしたとき，$\sum_{i=1}^{N}2^{-L_i} \leq 1$

平均符号長は，各記号の発生確率$p_i$，符号長を$L_i$ビットとしたとき，$L=\sum_{i=1}^{N}p_iL_i$[bit/symbol]

平均符号長の限界定理はエントロピー$H$と平均符号長$L$を使って，$H \leq L < H+1$と表せられる．

符号化の効率は，$e=H/L$

記号をm個ずつまとめることをブロック化と言い，拡大情報源はブロック化された記号列のことである．

ブロック化により，情報源符号化定理が示される．

$H \leq L < H + \epsilon$

符号化の例とし，ハフマン符号化やハフマンブロック符号化がある．

第4章 データ圧縮

受信側で完全に復元できる符号化を可逆圧縮もしくはロスレス圧縮という．

受信側で完全に復元できない符号化を不可逆圧縮という．

ファックスや静止画の符号化には，ランレングス符号化・MH符号化・MR符号化がある．

テキストのデータ圧縮には，スライド辞書法・動的辞書法がある．

記号の発生確率を求めないで，通信文の最初から符号化する方法をユニバーサル符号化という．

第5章 通信路符号化

誤り制御には送信側に再送要求するのか，受信側で誤り訂正をする．

誤り検出のための符号を誤り検出符号，訂正のための符号を誤り訂正符号という．

全てのビットを$n$ビット，情報ビットを$k$ビット，検査ビットを$n-k$ビットと置くことができる．

符号化率$\eta = k/n$，冗長度$\rho = 1 - \eta$

冗長が0ビットの場合，誤り検出は不可能．

冗長が1ビットの場合，誤り検出は可能，訂正は不可能．

冗長が2ビットの場合，誤り検出・訂正が可能．

ハミング距離 $d_H=d_H(\textbf{a},\textbf{b})=\sum_{i=1}^{n}(a_i \oplus b_i)$で符号間の距離を測れる．

最小ハミング距離によって，誤り検出・訂正能力が分かる．

ハミング距離$d_H$に対して，

$(d_H-1)$ビットまでの誤りを検出可能．

$\lbrack \frac{d_H-1}{2} \rbrack$ビットまでの誤りを訂正可能．

送信符号$x_i$の事前確率$P(x_i)$と，受信符号$y_i$を受信したときの送信符号$x_i$の事後確率$P(x_i|y_i)$を用いて，送信符号$x_i$と受信符号$y_i$を送受信したときの個々の情報量は$log_2{\frac{P(x_i|y_i)}{P(x_i)}}$と表せられる．

すべての送信符号$x_i$と受信符号$y_i$の情報量を相互情報量といい，$I(X ; Y)$と表す．

$I(X ; Y)=H(X)-H(X|Y)$と計算できる．

通信路だけの特性で決まる情報の伝送量として通信路容量$C=max_{P(X)}I(X;Y)$がある．

伝送速度$R$[bps]，通信路容量$C$[bps]としたとき，$RC$であれば，誤り率を任意に小さくできる符号化は存在しない．という通信路符号化定理がある．

第6章 基礎的な誤り検出・訂正符号

基礎的な誤り検出・訂正符号は以下の2つである．

1. パリティ検査符号
2. ハミング符号

以下の2つの性質をもつ符号はかなり実用的な性質である．

1. 線形符号 : パリティ検査方程式が各ビットの線形和で与えられる．線形符号には，「線形符号の中の任意の2つの符号の和（各ビットのXOR）からできる符号は，やはり元の符号に含まれる．
2. 巡回符号 : 符号の集合の中の1つの符号語を左に1ビットだけシフト（巡回）した符号が元の集合に含まれる符号を巡回符号という．

第7章 実用的な誤り検出・訂正符号

• 多元符号 : 複数ビットまとめた単位[シンボル]ごとに符号化を行う．

• CRC符号 : 別名巡回検査符号．検査ビットが$m$ビットであれば，$m$ビット以下のバースト誤りを検出できる．

• BCH符号 : 符号長と誤り訂正能力の選択範囲が広い．

• リード・ソロモン符号 : バイト誤りの訂正が可能．最大距離分離符号であり，訂正能力が高い．

• イレージャによる訂正 : 最もハミング距離が近い符号語に訂正すること．

• 組み合わせ符号 : 2つの符号化を組み合わせて2重に符号化する方法．積符号と連接符号がある．

• 畳み込み符号 : ブロックごとではなく，連続したビット列に対して符号化する符号を非ブロック符号と呼ぶ．これは非ブロック符号の1つ．

• ビタビ復号 : 確率的に最も確からしいパスを通ってきた符号系列を送信符号と考えて復号する最尤復号アルゴリズム．

• ターボ符号 : シャノン限界に迫る高い誤り訂正能力を持っている．送受信側で2組の符号器を利用する．

• LDPC符号 : 低密度パリティ検査符号．

• ハイブリッドARQ : 誤り制御技術の1つ．ARQとFECの組み合わせ．

第8章 伝送路符号化

波形の制限要因は以下の2つ．

• 周波数帯域 : 高い周波数成分は減衰や波形のひずみが大きい．
• クロックの再生 : 受信側で正しくパルスを受け取る必要がある．

ベース信号とは，0，1の符号を電気信号に変えたもの．よく使用されるものは次のものがある．

• ユニポーラNRZ
• AMI
• マンチェスタ符号

ディジタル記録用信号がある．EFMというものを用いる．

ディジタル変調によって，アナログ信号で0，1を表現する．主に以下の3つがある．

• ASK : 雑音に弱い
• FSK : スペクトラムの広がり大
• PSK : スペクトラムの広がり小

1回の変調で多ビットのデータを変換することを多値変調という．

• QPSK : 別名4PSK
• QAM : 位相だけでなく振幅変化も組み合わせた変調

第9章 アナログ信号の情報量

アナログ信号をデジタル信号に変えるとき，標本化と量子化を行う．
最高周波数が$W$[Hz]のとき，標本化周波数を$2W$[Hz]以上でサンプリングすれば完全に復元できる．

アナログ信号の最高周波数$W$[Hz]，量子化ビット数$b$[bit]，チャンネル数$N$とすると，サンプリング周波数$f_s=2W$であり，ビットレート$R=f_s * b * N$となる．

通信路容量定理は以下の式で表される．

$C=2B\log_2{\sqrt{\frac{S+N}{N}}}=B\log_2(1+\sqrt{}\frac{S}{N})$[bps]

ただし，周波数帯域を$B$[Hz]，信号および雑音の平均電力をそれぞれ$S$[W]，$N$[W]とおく．

通信路容量定理は雑音があるときの通信路容量である．
情報源符号化定理は雑音がないときの通信路容量である．

第10章 音声・映像の圧縮

音声の圧縮にはADPCMやCELP，CS-ACELPがある．20msごとにRTPでパケットを送るという手もある．

オーディオ圧縮にはMP3やAAC，ALSがある．

静止画圧縮には，JPEG，PNG，GIFがある．

映像圧縮には，MPEGがある．

感想

たまに情報量の話がでてくるため，こういうメモは大事かもしれない．

参考文献
小川 英一，改訂 マルチメディア時代の情報理論，コロナ社，2019，ISBN978-4-339-02893-5