クリプキクローネ日記帳

ある種の音楽と数学とランニングはミニマルなところが似ていると思う。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。
  1. --/--/--(--) --:--:--|
  2. スポンサー広告

情報理論 [今井秀樹(著)]

情報理論の教科書を読みました。
知識が虫食い状態だったので整理できてよかったです。



ざっくり言えば、zip圧縮みたいな話を情報源符号化、
パリティみたいな話を通信路符号化、という。

任意の状態から任意の状態に遷移をたどることのできる状態の集合を閉じた状態集合といい、
閉じた状態集合だけからなるマルコフ情報源を既約マルコフ情報源という。
特に非周期な既約マルコフ情報源を正規マルコフ情報源という。
正規マルコフ情報源は初期分布に関わらず定常的な確率分布である定常状態に達する。
マルコフモデル美しい。

{0,1}から{0,1}への通信路で、0→1の誤りも1→0の誤りも同じ確率pなものを
BSC(BinarySymmetric Channel)という。
あまりにもシンプルなモデルだけど重要。

BSCのように誤り源が入力と独立であれば、
Y = X XOR E
の形で誤り源Eを用いて表現することもできる。

一定の区間に集中的に発生する誤りをバースト誤りという。
特に一定の区間で誤りが連続するものをソリッドバースト誤りという。
ソリッドバースト誤りの誤り源はマルコフモデルで表せる。
一定の区間で正誤が混ざるようなバースト誤りはギルバートモデルやフリッチマンモデルで表せる。
バースト誤りは実際には多そうだけど、その外側がフォローされないのは不安。

符号系列の復号にその先の情報を使わないものを瞬時符号、使うものを非瞬時符号という。
符号語の区切りが分かるものをコンマ符号という。
瞬時符号はクラフトの不等式を満たす。
瞬時符号はリアルタイムシステムでは特に大事ですね。

平均符号長を最小とする符号をコンパクト符号という。
ハフマン符号もコンパクト符号である。
コンパクト性定理を連想してしまう。
似てるような似てないような。

情報源Sの記号をn回並べたものを1単位とする拡大情報源S^nを定義し、
S^nにおける1情報源記号あたりのエントロピーをn次エントロピーという。
nを増やすと効率的な符号化ができるので、エントロピーが下がる。
n→∞の極限をエントロピーと呼ぶ。
1情報源記号あたりの平均符号長はエントロピーに限りなく近づけることができる。
こういうイプシロンデルタ系の話好きです。
読むのが。
実現するのがではなく。

S^nに対するハフマン符号化(ブロックハフマン符号)は、エントロピーを下げようとすると
2^n個のパターンに対して符号を割り振らなければならないので負荷が大きい。
非等長のハフマン符号化はテーブルは少なくて済むが、ツリーの形状や生成法が複雑。
ランレングスをハフマン符号化するとシンプルな方法で効率よく符号化できる。
累積確率で符号化する算術符号もある。

平均情報量はすなわちエントロピー。
I(X;Y) = H(X) - H(Y|X)
をXとYの相互情報量という。
XとYの情報に関する関係の強さ。
共分散みたいなもんか。
エントロピーという単語は汎用性が高すぎます。
どの分野でもちゃんと共通概念なのがすごい。
ノイマンがシャノンにエントロピーという単語を使うことを勧めたとどこかで読んだけど、
それは嘘だという情報もネット上にある。
情報理論を持ってしてもどっちの情報が正しいのか分からない。

非可逆な符号化を許す場合、平均ひずみをD以下に抑えるときの平均符号長LはR(D)に限りなく近づけることができる。
R(D) = min{I(X;Y)} (d <= D)

以上が情報源符号化の限界。
次は通信路符号化の限界。

入力の確率分布pに対し、
C = max{I(X;Y)} (p)
を通信路容量という。

nビットの符号語をM個用いる通信路の情報伝送速度は
R = (logM)/n
と書ける。
符号語をr^n個すべて使用したときに
Rmax = logr
となって、
R/Rmax
をCの効率という。
1 - (R/Rmax)
をCの冗長度という。
日常的な単語が厳密に定義されているのに、
日常的な意味をそのまま表しているところがいいと思う。

R < C であれば、任意の復号誤り率の符号化を達成できる。

符号語の復号領域が大きければより多くの誤りを復号できるけど、
間違って別の符号語に復号してしまう確率も高くなる。
最尤復号法は一番それらしいものへ必ず復号するので
正しく復号できる確率が高いが、間違った復号の確率も高く、また、計算量が多い。

ここから具体的な符号化の方法。
パリティは情報ビットkに対して符号長がk+1なので、(k+1, k)符号である。
検査記号が線形の式で与えられる符号を線形符号という。

1つの誤りを訂正できる水平垂直パリティは((j+1)(k+1), jk)符号である。

ハミング符号は0以外のm次元のベクトルをすべて列として並べた検査行列で
(2^m - 1, 2^m - 1 - m)符号の単一誤り訂正符号がつくれる。

ハミング距離(最小距離)dminは符号語同士で異なる成分の数の最小値。
符号の復号領域の半径t1の最大値t0は
t0=rounddown((dmin - 1)/2)
で与えられる。
さらに、誤り訂正能力t2は
t2 - 1 = dmin - 2t1
で与えられる。

バースト誤りの誤り訂正には巡回符号を用いる。
生成多項式G(x)に任意の多項式A(x)をかけて得られる多項式W(x)の係数列の集合を広義の巡回符号という。
特に、符号長nに対する x^n - 1 がG(x)で割りきれる場合、
任意の符号語の係数を巡回させたものもまた符号語になる。
これを狭義の巡回符号という。
巡回符号の符号化はシフトレジスタで実現できる。

巡回符号は受信語Y(x)がG(x)で割り切れるかどうかで誤り検出できる。
この誤り検出方式がCRC。

さらに誤り訂正能力の高い符号化の汎用的な設計方法の1つがBCH符号。
巡回ハミング符号はBCH符号の特別な場合。
有限体(ガロア体)の素体GF(p)と素体の拡大体GF(p^m)上で定義される。

アナログ信号に対しても情報理論を拡張できる。
ただし、エントロピーをそのまま連続にすると∞になってしまうので、
通常は第一項目を無視して定義する。
AD変換では、量子化の変換曲線を工夫したり、
2次元のXとYをセットにして扱ったり(ハニカム構造みたいな)することで、
量子化雑音を小さくすることができる。
すごい発想だな。



  1. 2017/05/18(木) 23:37:41|
  2. | トラックバック:0
  3. | コメント:0
<<モダンC言語プログラミング [花井志生(著)] | ホーム | make 改訂版 [Andrew Oram, Steve Talbott (著), 矢吹 道郎(監訳), 菊池 彰 (訳)]>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://myumbrella.blog42.fc2.com/tb.php/375-8a45403c
この記事にトラックバックする(FC2ブログユーザー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。