情報理論

基本

あるデータがあった時にそのデータの情報量を定量的に評価できるようになることが情報理論の柱である。これによって情報技術をサイエンスとして扱える

chapter1 情報源符号化

どれだけ効率的に符号化できるのかを考えるのがこの章の内容

離散数学的な証明は図で書くとわかるが、定式化で解こうとすると難しい

D元情報源符号化とは写像 C: X→D*のこと

C(x)をxに対する符号語

Cが単射のとき正則であるという

Cの拡張C*を定める

w1がw2の語頭であるとは、あるvについてw2 = w1 || vとなること

語頭符号＝接頭符号＝瞬時符号

Cについて語頭符号→一意復号可能→正則

Cが一意復号可能であれば、クラフトの不等式が成り立つ

Cを一意復号可能とすると語頭符号　Cで、大きさが同じとなるものが存在する

Xに対する符号Cの平均符号語長を定める L(C)

L(C)を最小化したい

D元ハフマン符号を以下で構成する

定理1.5

(1)C1,C2をXに対するハフマン符号とするとC1,C2は語頭符号で、L(C1) = L(C2)

(2)CをXのD元一意復号可能符号、ChをXのハフマン符号とするとL(Ch)<=L(C)

Xの情報エントロピー（シャノンエントロピー）を H(X) = - Σp(xi)log2p(xi)で定義

Iを実線型空間の凸集合とすると、f:I→Rが下に凸であるとは、f(λx + (1-λ)y) <= λf(x) + (1-λ)f(y)

定理 Jensenの定理

補題1.7

命題1.8

(1)エントロピー関数は真に上に凸である

(2)H(p1,…,pn) <= log2nで等号成立

定義

X上のX,Yのカルバック・ライブラー情報量

定理1.9

D(p||q) >= 0で等号 ⇄ p=q

エントロピー関数を使えば、ハフマン符号長の評価ができる

通信路符号化

AカラBに情報を送るとき、ある形にエンコードして情報を送れば少しぐらいノイズが混じっても復元できるように

通信路について数学的に表現していく

定理1.10

r.v. Xに対する一意復号可能なD元符号Cについて、L(C) >= (1/log2D) * H(X)

定理1.11

r.v. X上のD元ハフマン符号Cについて、

chapter2 通信路符号化定理

定義

離散無記憶通信路とは、x∈Xごとに定まるY上の条件付き確率関数の族のことと定める

定義

・メッセージ集合

・符号化関数 Enc

・復号関数 Dec

の組Cを通信路符号という

Cのレートを R = log2M/n

復号誤り確率を err(w) = Σ p(y | Enc(w))で定める

定義

達成可能なレートRの上限をこの通信路の容量という

定義

条件付きエントロピー

相互情報量

定理2.2 通信路符号化定理

離散無記憶通信路を一つ固定する

I = supI(X;Y)とすると、この通信路の容量はIである

マルコフの不等式

大数の弱法則

通信路符号化定理

命題2.3

(1)I(X, Y)はp(y | x)を固定するとpxについて連続で上に凸

(2)I(X;Y)は、p(y|x)を固定するとpxについて連続、上に凸

(3)I(X;Y)はpxを固定するとp(y|x)について連続、下に凸

補題2.4 マルコフの不等式

定理2.5 大数の弱法則

通信路符号化定理(1)

補題2.6

定義 条件付き相互情報量

補題2.7 連鎖律

定義 マルコフ連鎖

X1 → X2 → X3(M.C.)

X2の値が決まっているとき、X1とX3は独立

補題2.8 マルコフ連鎖の拡張

命題2.9

マルコフ連鎖のときの相互情報量

定理2.10 ファノの不等式

通信路符号化定理(2)

chapter3 具体的な通信路符号化方式

離散無記憶通信路を仮定する。メッセージMに対する平均復号誤り確率をなるべく小さくしたい

定義

Enc:μ → C と M上のr.v. Mについて、受診後yに対する最尤復号を定義する

命題3.1

最尤復号と別の復号関数の関係

定義

q元線型符号

符号集合 C = Enc(μ)がF

定義

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

命題3.2

ハミング距離の性質

定義

最小距離復号:d(w,y)が最小となるw∈Cに復号する方法

定理3.3

一様なメッセージ分布について最小距離復号は最尤復号である

定義

t重誤り訂正符号

定理3.4

Cを線型符号とし、dmin = dmin(C) = min

補題3.5 チェルノフの不等式

定義

パリティ検査行列

シンドローム

補題3.6

シンドローム復号

定義

生成行列

リード・ソロモン符号

定義

リードソロモン符号を定める

命題3.7

リードソロモン復号について

ユークリッド復号

定理3.9

ユークリッド復号はt個以下の誤りを訂正できる

補題3.8

chapter4 有歪み情報源符号化

歪み関数 d(x,x_hat) = 1/n(Σd(xi, xi_hat))

定義

(2^nR, n)レート歪み符号とは、

・符号化関数 fn: X → μ

・再生関数 gn: μ → X_hat

の組C

定義

R = レート歪み関数

定義

情報レート歪み関数

上のinfを実現するp(x_hat|x)が存在する

定理（レート歪み定理）

(1)

(2)

補題4.2

式？

定理4.1 Rについて

命題4.3

系4.4

計算と情報

チューリングマシン

δ:{内部状態}✖️{文字}　→ {内部状態} ✖️ {文字} ✖️ {移動}

事実

この計算モデルは他の自然な計算モデルと等価

定義

万能チューリング機械とは、組(<M>, x)を入力とする TM Uで、

・M(x)が停止するときU(<M>, x)も停止してM(x)を出力

・しないとき、出力しない

事実

万能チューリング機械は存在する

定義

TM Mに関するビット列 s のコルモゴロフ複雑度Km(s)を

Km(s) = min{|x| : M(x) = s}で定める

命題5.1

Uを万能TM、MをTMとすると、定数cで「どのsについてもKu(s) <= Km(s) + c」なるものが存在する

系5.2

Uが万能TMのとき、「sについて常にKu(s) <= |s| + c」となる定数cが存在する

定義

万能TM Uを決めたとき、sがアルゴリズム的にランダムであるとは、Ku(s) >= |s|であることと定める

命題5.3

万能TM Uについてアルゴリズム的にランダムなビット列が存在する

定理5.5

各ビットをベルヌーイ分布で独立に選んだnビットの分布をX<n>とかく

このとき

補題5.4

不等式の関係

定理5.6

Uを万能TMとするとき、Ku(s)を計算するTMは存在しない

系5.7 停止問題の計算不可能性

TM Mとxを与えたときにM(x)が停止するかどうかを判定するTMは存在しない

chapter 情報理論的に安全な暗号技術

・暗号技術には、共通鍵暗号、公開鍵暗号などがあり、共通鍵暗号の中にも情報理論的安全や計算量的安全がある

定義

共通鍵暗号化方式とは以下の仕様を満たすアルゴリズムの組と定める（Π）

・Gen（鍵生成）：鍵空間Kから鍵kを選んで出力する

・Enc（暗号化）：鍵kと平文mを入力として、暗号文c = Enck(m)を出力する

・Dec（復号）：鍵kと暗号文cを入力として、Deck(c)は平文または失敗を出力する

定義

Πが正当であるとは、どの鍵とどの平文mについていも常にDeck(Enck(m)) = mを満たすことと定める

例 ワンタイムパッド

定義

Πがperfect secrecyを持つとは、鍵の分布Kと平文のどの分布Mについても暗号文の分布 C = Enck(M)がI(M;C) = 0を満たすことと定める

補題6.1

Πについて以下は同値

(1) ΠはPerfect Secrecyを持つ

(2)m1, m2とcについて常に、確率？

定理6.2

ワンタイムパッドはPerfect Secrecyを持つ

定理6.3

ΠがPerfect Secrecyを持つとき|K| >= |μ|

定義

(t,n)-しきい値型秘密分散方式(secret sharing)とは、以下のようなアルゴリズムShare, Reconstの組みをなす

・Share：秘密情報mを入力としてn個のシェアを出力する

・Reconst：t個のシェアを入力としてμの元を出力する

正当性：Share(m) = (s1, s2, ,,,)のときどのt個についても常にreconst() = m

安全性：μ上のr.v. M、対応するsiのsiについてどのt-1個についても

命題6.4

これは正当かつ安全である

補題6.5 ラグランジュ補完

Fを体、nを自然数として、f(ai) = biとなるn-1次多項式がただ１つ存在する

定義

シャミアの(t,n)：方式

定理6.6

この方式は正当かつ安全

量子情報理論

・量子計算

・量子通信

・dense coding

・量子暗号

・量子エントロピー

量子状態はヒルベルト空間上の線型演算子

純粋状態はHの単位ベクトル

定義

二次元ヒルベくと空間に対応する量子系を量子ビットといい

|0>、|1>を計算基底という

定義

Hの正規直交基底をb0,,,とすると、この基底に関する状態の測定とは

・測定結果は{0,1,・・・,n-1}の元

・結果iが得られたとき状態は|bi>に変化する

定義

量子ビット系H1とH2とそれらの計算基底をとる、このとき以下の性質を持つ有限次元ヒルベルト空間h1✖️h2が存在する

これをH1とH2のテンソル積といい、対応する量子系を２量子ビット系という

定義

量子系Hにおける閉じた操作はH上のユニタリ演算子で表される

特にこの操作は可逆である

量子テレポーテーション

量子鍵配達

定理7.1 複製不可能定理

Hをc2とc2の2量子ビット系とする

H上のユニたり演算子Uで、どの単位ベクトルについてもU(|Ψ>)　(ry を満たすものは存在しない

BB84プロトコル