10/14 集合 集合は元(要素)の集まり.A={a,b,c,d}とかA={a|C(a)}みたいに書く.∅={} …empty set.//記号はオーにスラッシュ. ギリシア文字のファイではない 註) aと{a}は違う. {}と{{}}も違う 元が一つだけの{a}は単元集合(singleton set)という 基数(濃度) |A|とは集合Aの元の数. 無限集合だったら無限. 無限にもいろいろあるけど, ここではコンピュータが扱う集合 なので無限はあんまり考えない.A⊂B⇔「a∈A⇒a∈B」//真部分集合とか昔あったけど考えない. 今は上の定義で行く. //つまりA=Bも可能性として含める. 註)∀A:∅⊂A, A⊂A a∈A⇔{a}⊂Aベキ集合 Aの全ての部分集合からなる集合2A={B|B⊂A}例) A={1,2,3}に対するベキ集合は2A={{},{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}}//Aが右肩に乗ってるこの2とは{0,1}という集合のコトらしいけど //今は関係ない. 註) |2A|=2|A| ∅⊂2A, A∈2A 直積 A×B={(a,b)|a∈A,a∈B} |A×B|=|A|･|B| //A×B≠B×A カップ A∪B={a|a∈A or b∈B} 以下が成り立つ べき等律… A∪A=A 交換律… A∪B=B∪A 結合律… (A∪B)∪C=A∪(B∪C) キャップ A∩B={a|a∈A and a∈B} イカが成り立つ べき等律… A∩A=A 交換律… A∩B=B∩A 結合律… (A∩B)∩C=A∩(B∩C) また A⊂B ⇔ A∩B=A ⇔ A∪B=B 吸収律 A∩(B∪C)=A A∪(B∩C)=A 分配律 A∪(B∩C)=(A∪B)∩(A∪C) A∩(B∪C)=(A∩B)∪(A∩C) 相補性 以上見てきたように C(∪)が成り立つようなことはC(∩)も成り立つし, D(∪,∩)⇔D(∪,∩) である. これを相補性という. 差集合 A-B={a|a∈A and not a∈B} //「A＼B」って書く人いる 補集合 X⊂Aの時に, Aを全体集合とすると X=A-X 相補律 X∪X=A X∩X=∅ 互いに素である, とは, 交わりが空である二つの集合のこと. A∩B=∅ de Morgenの法則X∪Y=X∩Y X∩Y=X∪Yベン図を書いて分かった気になる. 束<ソク>(lattice) 一つの集合と二つの演算子の組(L,∨,∧). Lはエル. latticeの頭文字. 集合 ∨は結び. ∪を一般化したものを想定してる. ∧は交わり. ∩を一般化したものを想定してる. (L,∨,∧)が束である, とは次を満たすこと. 演算∨及び∧はLで閉じてる. つまり,∀x,y∈L: x∨y∈L, x∧y∈L. べき等律: ry 交換律: ry 結合律: ry 吸収律: x∧(x∨y)=x, x∨(x∧y)=xこれらを満たす組(L,∨,∧)を束という. 例として(2A,∪,∩)は束である. 分配束分配律: x∨(y∧z)=ｒｙ, x∧(y∨z)=ｒｙこれは上の束の条件からは導かれない. 分配律を満たさない束はいくらでもあるから. 分配律を満たす束を分配束という. 最大元・最小元 Lの元Mが∀x∈L:x∨M=M and x∧M=xを満たす時, MをLの最大元という. 最小元m(∈L)とは∀x∈L:x∨m=x and x∧m=mとなるmのこと. お察しの通り、Mとmは存在するかは分からない。 補元 束(L,∨,∧)が最大元M、最小元mを持つとして xの補元がyであるとはx∨y=M, x∧y=mとなること。 --- 10/21 二項関係 集合A,Bに対してA×B上の二項関係とはA×Bの部分集合Rであり(a,b)∈R ⇔ aRbと書く。 「A×A上の二項関係」を単に「A上の二項関係」とも呼ぶ。 例) Nの上の二項関係≦≦ = {(0,0), (0,1), (0,2), ... (1,1), (1,2), .. ....} (n,m)∈≦ ⇔ n≦mN上の|n|m ⇔ 「nがmを割り切る」Rの考えられる性質反射律: aRa 対称律: aRb⇒bRa 推移律: aRb,bRc⇒aRc 反対称律: aRb,bRa⇒a=b恒等関係II={(a,a)|a∈A}合成 R⊂A*B, S⊂B*C に対してR・S = {(a,c)∈A*C|∃b:aRbかつbRc}:cd R0=I, R1=R, R2=R・R R3=(R・R)・R=R・(R・R)=R・R・R 推移的閉包R*=R0+R1+R2+…推移的閉包は反射律と推移律を満たす。 なぜならI=R0⊂R*, R*・R*=R* であるから。 例) R={(n,n')|n'=n+1}⊂N×NnRn+1, n+1Rn+2 ⇒ n(R・R)n+2のように R2={(n,n")|n"=n+2} 再帰的にRm={(n,n(m))|n(m)=n+m} ∴ R* = R0+R1+… = {(n,m)|n≦m}同値関係 A上の二項関係で、反射的で対照的で推移的なものを同値関係という。 例) 直線の平行関係、整数のmで割った余り、など。 同値関係Rに対して、同値類[a]とは[a]={b∈A|aRb}aを代表元という。aRbならbRaだから[a]=[b]であり、代表元は別にaでなくても 良いのだ。 (i) 反射律: a∈[a] (ii) 対称律: b∈[a]⇒[a]=[b] //対称律 (ω) 推移律: c∉[a]⇒[a]∩[c]=∅ //推移律による背反 A=[a1]+[a2]+…+[an] ;但し、i≠jは[ai]∩[aj]=∅ とAを分割することができる。 Ai=[ai] と書きなおす。 商集合 A/R = {A1, A2, .. , An} 半順序≤ A上の二項関係で反射的で反対称的で推移的なもの。 「yがxの直上(immediate upper)である」または「yがxを覆う(cover)」はたまた 「yがxのsuccessorである」とは、「x≠y で x≤y で xとyの間に何もない」 ということ。何もないとはつまり、x≤z≤y⇒z=xまたはz=yということ。 Hasse図 直上にあるものを線分でつないで上に書く。 たとえば集合2x,y,zの包含関係⊂のHasse図 Wikipedia svg画像 例えば、{x,y}は{y}の直上にある。 ∅が{x,y,z}の部分集合であるかどうかは、∅からただ上に向かって 辿れば良い。 最大元 U⊂Aについて、Uの最大元(max U)とはi) b∈U ii)∀x∈U: x≤bとなるbのこと。 最大元はいつも存在するとは限らない例えばU={a,b,c}でb≤a, c≤a となっているが、 半順序はaとcの比較可能性を保証しない。 つまりa≤cでもc≤aでも無いというこのUについて 最大元は存在しない。 最小元 最大元の逆 極大元 i) b∈U ii)∀x∈U: b≤x⇒x=b //bより直上になるものは無い 最大元の時にいったようなUで言えばa,cが極大元 極小元 極大元の逆 上界 {b∈A| ∀x∈U: x≤b}をUの上界と言う。
A={a,b,c,e,d,f}とするこの図でいうと {d,e}が上界である。fはa≤fとなっていないので上界ではない。 下界 上界の逆 上限 上界の最小元をsup Uとする 下限 上限の逆。inf U. Thm. 半順序集合Aの任意の二元x,yに対してsup{x,y}、inf{x,y}が いつも存在する時、x∨y=sup{x,y}、x∧y=inf{x,y} とすると (A,∨,∧)は束になっている。 逆に、「x∨y=y⇔x≤y」として≤を定義すると(A,≤)は 半順序である。 --- 10/28 一演算の代数。 Gを集合、・を演算とする。 演算は閉じているものを考える。即ち、
∀a,b∈G: x・y∈Gである。 註) x・yをxy、x・xをx2とか書く。i) 結合律: ∀a,b,c ∈ G, (ab)c = a(bc) u) 単位元: ∃e ∈ G: ∀x ∈ G, ex = xe = e w) 逆 元 : ∀x ∈ G, ∃y ∈ G: xy = yx = e m) 交換律: ∀a,b ∈ G, ab = ba(i)が成り立つ(G,・)を半群という。 (i,u)が成り立つGをモノイドという。(集合と演算の組み(G,・)と書くのが正確だけど文脈によって明らかならば単にGと書く) (i,u,w)が成り立つGを群(Group)という。 (i,u,w,m)が成り立つGを可換群という。 群(G,・)が|G|≤∞の時、Gを有限群という。 ・単位元は唯一である。eとe'が単位元の時、e = ee' = e'・逆元は一意である。xの逆元をx-1と表記する。xの逆元がx-1とx'-1とがあるとすると x-1 = x-1e = x-1xx'-1 = ex'-1 = x'-1・(xy)の逆元は(y-1x-1)である。証明略部分群 群(G,・)に対してH ⊂ G ∀x,y∈H ⇒ xy∈H ∀x∈H ⇒ x-1∈Hが成り立つ時、(H,・)を部分群という。 註) 単位元e∈Hはこの定義から明らか。 例) Z={整数全体}; mZ={mz|z∈Z} (mは自然数) (mZ,+)は(Z,+)の部分群である。 註) 演算・を+と書く時、大抵、可換群であることを想定している。 そして逆元を-aと書き、a+(-b)をa-bと表記する。 HがGの部分群であるとき、G上の二項関係～をx～y ⇔def x・y-1 ∈ Hで定義する。これは同値関係である。即ち、反射律、対称律、推移律が成り立つ。 この同値関係～を右剰余類という。 対してx～y ⇔ x-1y∈Hで定義する同値関係～を左剰余類という。 xを含む右剰余類(x～yとなるy全体)はyx-1=h∈H ⇔ y=hxより、H・x = {h・x | h ∈ H}である。 ～で定義される商集合を「G/H」と書く。 例) Z/6Z = {0+6Z, 1+6Z, .., 5+6Z} ∀x∈G: xH = Hx となる時、Hを正規部分群という。 左右の剰余類は一致し、単に剰余類と呼べば良い。G/Hは群をなし、剰余群という。 剰余類をHxと書くことにする。 --- 11/4 環(Ring)とは加法と乗法が整備された集合Rのこと。 Rの任意元について二つの演算＋および・は閉じていて (R, +)は可換群（アーベル群）であり、単位元を0、逆元を-aと書く。 (R,・)はモノイド(逆元があるとは限らない)で、単位元を1と書く。 分配律はa(b+c) = ab+ac (a+b)c = ac+bcが成り立つ(乗法の交換律は保証しない)。 この(R,+,・)という組みを環という。 例えば整数Zや多項式R[x]は環である。 元が0だけである集合Rも環であり、これを零環という。 零環の乗法の単位元は1=0となる。1=0 ⇒ 1・a = 0・a ⇔ a=0 ⇔ R={0}逆に、零環でない環ならば、1≠0 である。 単元(または"可逆元")とは左右の逆元を持つ元のこと。//単位元ではない 零因子とは0でないa,bについて「a・b=0」となるa,bのこと。 単元は零因子には成り得ない。 単元aが零因子ならば、∃b≠0:ab=0. b=1b=a-1ab=a-1(ab)=0 と矛盾する。 対偶として、零因子ならば、単元ではない。 乗法が可換である時、(R,+,・)を可換環という。 零環ではなく、0以外の全ての元が単元(乗法の逆元の存在)である環を斜体という。 斜体でありかつ、可換環であるものを体という。 イデアル 環(R,+,・)に対してI⊂R IはRの加法に関するアーベル環 ∀r∈R, ∀a∈I: ra∈I (左にRを掛けてもIに戻る)となるIを左イデアルという。 右イデアルとは、上が「ar∈I」となるもの。 Rがアーベル環なら「ra=ar」だが、そうでなくても左イデアルでありかつ 右イデアルである時、それを両側イデアルという。アーベル環なら両側 イデアルなのは当然なので単に"イデアル"とだけ言う。 両側イデアルは「∀r,r'∈R, ∀a∈I: rar'∈I」と表せる。 整数全体Zに対して、mZ = {mi | i∈Z}はイデアル。 多項式全体R[x]に対して、(f) = {f(x)g(x) | g∈R[x]}はイデアル。 環Rに対してRの元aを生成元として、Ra = {ra|r∈R} aR = {ar|r∈R}として、それぞれ左イデアル、右イデアルを実際に作ることができる。 (Rが環なので、r'(Ra)の任意元r'raはr'r∈Rより、Raの元である。) 両側イデアルはちょっと技巧的でRaR = {Σ[i=0;N]riari' | ri,ri'∈R}として作るらしい。 このようにして作ったイデアルを単項イデアルという。 それのイデアルがいつも単項イデアルであるような環を単項イデアル環という。 剰余環 環Rとそれの両側イデアルについて∀a,b∈R a≡b (mod I) ⇔ a-b∈Iと≡を定義する。≡という二項関係は同値関係である。 これで出来る剰余系(商集合)をR/Iと表すが、これは環であり、剰余環とよぶ。 イデアルmZに対してa≡b (mod mZ) //「a≡b (mod m)」みたいだ。 同値類: [a] = a+mZ 商集合: Z/mZ = {[0], [1], .. , [m-1]}[a]+[b] = [a+b] [a]･[b] = [ab]と加法と乗法を定義していいだろう。 加法について単位元は[0]、逆元は[-a] (=[m-a])。 乗法について単位元は[1]である。 Zm={0,1, .. ,m-1}～Z/Zm (同型) mが素数ならZ/mZは体になる(乗法が可換なのは当然で、[0]以外の元は全部乗法 の逆元を持つ⇒「∀a≠0, ∃b: ab=nm+1 (mは素数)」) 可換群でありかつ0以外に零因子が存在しない環を整域という。ZとかRは整域。 既約元とは、単元ではないaについて「a=b・c」と書けるならば、b or cが 単元であること。 全ての元は一つの単元と有限個の既約元の積で表せる。∀r: r = u・p1・p2・...・pn整数Zを例として調べてみる。 単元は1,-1だけ。2-1なんかはZに属さない。 既約元とは0と素数のことである。 故に「一つの単元と有限個の既約元の積」とは、符号付きの素因数分解を表す。 Euclid整域。整域Rを自然数Nに写すμを考える。但しμは次の二つの性質を満たす。 (i) x≠0ならμ(0)<μ(x) (u) x≠0なら∀y∈Rに対して y = qx+r μ(r)<μ(x) となるq,r∈Rが存在する。このようなμを考えれるならRをEuclid整域という。 整数Zはμ(x)=abs(x)としてEuclid整域である。//絶対値abs. 定理。Euclid整域は単項イデアル整域である。 [証明] IをRのイデアルとする。 I-{0}の元でμを最小にする元をx0とする。∀x∈I-{0}: x = qx0+r ⇔ r = x-qx0 ∈Iそしてμ(r)<μ(x0)であるが、x0の取り方から、r = 0に限られる。これを代入すれば∀x∈I-{0}: x=qx0 (q∈R)よってIは単項イデアルであり、Rは単項イデアル環である。 単項イデアル環であるEuclid整域だから単項イデアル整域。 --- 11/11 aがbを割り切る：a|b 最大公約元: d = gcd(a1, a2, .. , an) …1≤i≤に対し、d|ai であり、d'|ai⇒d'|d というdである。 Euclidの互除法a,bに対し、r0=a, r1=bとする。 n≥2に対し、 rn-1≠0なら、rn-2 = qn-1rn-1rn (qn-1∈ℕ) によってr2以降を伸ばす。rn=0で終了。 rn-1がgcd(a,b)である。このアルゴリズムの停止性は|rn|<|rn-1|により保証される。 これによれば、a=qb+rの時、gcd(a,b)=gcd(b,r)である。 これは当然で、d=gcd(a,b)とするとd|a, d|b ∴d|(a-qb)⇔d|r d|a,d|rからd|(gcd(b,r)). d'=gcd(b,r)とすると d|d'. 逆にd'|(a+qb)でd'|d. 故にd=d'. 定理。 I = {ax+by | x,y∈Z}はZのイデアルである。Zは単項イデアル環であったから Iは単項イデアルであり、I = d・Z ( d = gcd(a, b) )と表せる。つまり、∃x,y∈Z: ax+by = d (d=gcd(a,b))が言えて、これは拡張ユークリッドの互除法で解ける。 既約剰余類Z/mZ～{0,1,..,m-1}=Zmに対してZm* = {a∈Zm | gcd(a,m)=1}これを規約剰余類という。 規約剰余類は乗法について群である。 まず、乗法は閉じていること。 a,b∈Zm*なら、gcd(a,m)=gcd(b,m)=1ゆえに、gcd(ab,m)=1 よってab∈Zm*である。 gcd(1,1)=1より、1∈Zm*なので乗法の単位元を持つ。 // ちなみに、いつも0∉Zm*であるから加法については半群まででしかぬ。 先の定理によりa∈Zm*に対して、ab+my = 1 , gcd(a,m)=1とするb,yがZmに存在する。 d=gcd(b,m)は d|ab+my ⇔ d|1 故にd=1 よってb∈Zm*である。 例としてm=5とすると Z5* = {1,2,3,4} 1・1≡1 mod 5 2・3≡1 mod 5 4・4≡1 mod 5 と逆数がちゃんと存在する。 ちなみにm=8とすると aの逆数はaである。 Fermatの小定理 素数pに対し、1≤a<p ⇒ ap-1 ≡ 1 mod p[証明] Zp = {0,1,..,p-1} に対して Zp* = {1,2,..p-1}であるが、 ところで1以上p未満の整数aを用意して 「a・i ≡ a・j mod p ならば、i≡j」である。 なぜならaの逆数は存在して左から掛けてやればよいから。 っていうか、まあ。a|pはありえないし、当然だ。 これにより、「i→a・i」という写像は全単射ということになる。 即ち、a・Zp* = Zp*両辺の要素の積は一致するはずで ap-1・(p-1)! ≡ (p-1)! mod p (p-1)!の逆数も存在するので、 ap-1 ≡ 1 mod p (/証明終) 暗号 送信者アリスが平文xを送る。xは手元の暗号化器によって暗号文yとなる。 yは通信路を通って受信者ボブの元に届くが、その直前に復号化器によって 平文xに復号化される。この時、第三者に傍受されうるのは暗号文yである。 秘密鍵。これは従来の方式で、暗号化も復号化も同じ鍵によってなされる。 だから鍵はヒミツにしておかないといけない。 公開鍵。暗号化と復号化は別々の鍵で行う。暗号化は公開鍵によってなされる。 だから誰でも暗号化はできる一方向性の暗号化であり、復号化は困難である 落とし穴式。秘密鍵によって容易に復号化ができる。暗号化: y = ek(x) ;e is public.このekを用いることで、yを受けて元のxに復号化しようと思ったら、あらゆる xに対してek(x)を計算し、yと一致するか確かめることによってしか復号化 できず、それはひどい計算量である。公開鍵は計算量的安全なのである。 RSA暗号異なる大きな素数p,qを用意し、n = p・q とする。 φ(n) = (p-1)・(q-1) またφ(n)と互いに素な数cを一つ用意する。 「cd≡1 mod φ(n)」となるようなdを用意する。 //群Zφでの c の逆数である。 公開鍵: n, c 秘密鍵: p, q, d平文を数値にエンコードしたものをxとして、 暗号化: y = xc mod n 復号化: x = yd mod n によって通信する。 これはちゃんと復号化できているのか。つまり、x≡yd≡xc・dであるのか。cd ≡1 mod φ より、cd = a(p-1)(q-1)+1 (a∈Z) と表せる。 フェルマーの小定理より、xp-1≡1 mod p 故に xcd = xa(p-1)(q-1)+1 ≡ x mod p 同様に、xcd ≡ x mod q よって、xcd ≡ x mod n; n=pqと、復号化される。 離散対数問題 Gをaを生成元とする巡回群とする。つまり、G = {an | n∈Z}このGに対して∀β∈G, ∃n∈Z: an = βである。そこで、logaβ = nと書く。 --- 11/18 多項式 可換環Rの元を係数とし、不定元Xを用いてf(X) = anXn + ... + a1X + a0 (ai ∈ R)とする時、f(X)をR上の一変数多項式という。 an≠0 の時、f(X)の次数をnとし、def(f)で表す。(deg(f)=n) また最高次係数anが1のf(X)をモニックと云う。 このようなf(X)全体の集合をR[X]と表す。 加法、乗法はよく知っていて、それによりR[X]は可換環である。 Rが整域(零因子が0のみ)の環ならdeg(f・g) = deg(f) + deg(g)が成り立つ。 f(X)のXにRのある元bを代入した時f(b) = anbn + ... + a0 = 0が成り立つならば、bをf(X)の根と呼ぶ。 f(X)を0でないg(X)で割り算する。f(X) = q(X)・g(X) + r(X) deg(r) < deg(f)q(X)が商で、r(X)が剰余である。f(X) = g(X)・h(X) deg(g)≥1, deg(h)≥1となるg,hが存在しない時、fは既約多項式と言える。 体K上の多項式を考える。 K[X]/f(X) (商集合)は{g(X)|deg(g)<deg(f)}と同型であるが f(X)が既約多項式である時、それは体になる。 // 体とはつまり可換環であり整域であり零環ではない。 ユークリッドの互除法を多項式にも適用できて、 fが既約だからgcd(f, g) = 1。f・a + g・b = 1となるa(X), b(X)が存在する。g・b ≡ 1 mod fとも書ける。 有限体 素数pに対して、Z/pZ ～ Zp = {0, 1, .. , (p-1)} これをFpと書くことにしてFp[X]を考える。 Fp[X]のn次既約多項式をf(X)とする。Fp/f ～ { g | deg(g)<n}はさっきも言ったとおり体である。証明はしてないけど。g(X) = an-1Xn-1 + ... + a0という多項式をvector: pn = (an-1, .., a0)で表してみる。このn次ベクトルpnとした。 ai は 0 から (p-1) までのpコの整数を取りうるから 体Fp/f の元は pn コである。 Fp/f を Fpn とか GF(pn) とか書いたりする。 拡大体 K⊂L でKもLも体の時、LをKの拡大体と云い、逆にKをLの部分体という。 「（体の）拡大L/K」と書く。 例えば Q(√2) = { a+b√2 | a,b∈Q } とすると拡大Q(√2)/Q である。 拡大L/Kに就いて、LはKのベクトル空間である。 Q(√2)の例だと、{1, √2}が基底である。 そのLの次元をL/Kの拡大次数と云い、[L:K]と表す。 拡大L/Kに於いて、α∈Lに対して、0でなく、αを根とするf(X)∈K[X]が 存在する時、αをK上代数的だという。そのようなf(X)が存在しない時、超越的 という。 例えば、拡大R/Q で√2はX2-1の根になってる。eとかπとかは超越数。 α∈L に対して、f(α)=0となる最小次数でモニックであるfを、 αの最小多項式という。 // αがKの元ならf(X)=X-α と簡単だけど // さっきの例のR/Q を想定すると良いと思う。 // つまり有理数は係数でXの変域は実数。つまり実数のハンイで解を求める // 方程式である。 // C/Z でもたぶん良いと思う。 最小多項式は既約である。 α&inin;Lに対し、 αの最小多項式をf(X)とする。 次数が1以上のg,hによって f=g・h と表されるならf(α) = g(α)・h(α) = 0 ∴g(α) = 0 or h(α) = 0となり、gもしくはhを改めて最小多項式にしなければならない。 であるからfは既約である。 このfに対してK[X]/f(X)は体である。K[α] = {g(α) | g(x) ∈ K[x] }とすると, K[α]はLの部分環である。K[X] = {g(X)} K[X]/f(X) = {r(X)} i.e. g(X) = h(X)f(X) + r(X) thus, g(α) = r(α) (because f(α) = 0) finally, K[α] = {g(α) | deg(g) < deg(f)}α (∈ L) の最小多項式fがあって、n = deg(f) とする。 次元がn未満の二つの多項式g, h を用意する。 この差(g - h)を表す多項式をdとしよう。 gとhが異なる多項式であれば、dは定数ではない多項式だ。 dの次元はn未満であり、fがαの最小多項式であるのだからd(α) ≠ 0である。すなわちg(X) ≠ h(X) ⇒ g(α) ≠ h(α)K[α] = { g(α) | g(X) ∈ K[X] }であった。 多項式gによってXとg(X)が対応付けられてるのだからcard K[α] = card{ g(X) | deg(g) < deg(f) }であるだろう。 --- 12/2 情報理論 確率変数とは、確率的に決まる値のこと。 事象とは確率変数の集合。E = {x}事象Eが起こる確率をPr(X∈E)と書く。 Eがsingleton setで、例えばE = {a}ならばPr(X=a)とも書く。 情報量。 確率pで生じる事象の発生を伝えるのに必要な情報量I(p)を考える。 例えばサイコロの出た目について。 偶数か奇数かを伝えるのはI(1/2)偶数か奇数かが分かった後に出た目を伝える、即ち、 ３つの内１つを伝えるのはI(1/3)この二つによって、６つから１つを伝えたことになってI(1/6) = I(1/2) + I(1/3)と、情報量の和であると考える。 一般にI(p1・p2) = I(p1) + I(p2)また確率１の事象については、必ず起こるのだからその情報量はゼロI(1) = 0として考えることにすると、 このような関数Iについて次のように解ける。I(p(1+ε)) = I(p) + I(1+ε) ⇔ I(p+εp) - I(p) = I(1+ε) - I(1) ⇔ εp・I'(p) = ε・I'(1) ∴ I'(p) = c/p ; c is Const. ∴ I(p) = c・log(p)この定数cが、情報量のスケールを決め、c = -1/log(2)としたI(p) = -log2(p)これを「自己情報量」と定め、また単位をbitとする。実際は無次元だけど。 以下このスケールを用いる。 logの底は2が基本であるので、いちいち書かないことにする。Pr(X = ai) = pi ; ∑pi = 1に対してH(X) = -∑pi・log(pi) = ∑pi・I(pi)これは自己情報量の重み付き平均、即ち期待値であり、「エントロピー」と呼ぶ。 // 物理学におけるエントロピーと似てるので、その言葉を用いたというだけ。 そしてこれはXが伝える情報量であり、Xを知る前と知った後の曖昧さの差である。 当然知った後のほうが曖昧さは減る。 Xが{a1, a2}の二通りだけ生じる時p1 + p2 = 1 p1 = p と置くと p2 = 1 - p で H(X) = -p log(p) - (1-p) log(1-p)これを特に「二元エントロピー」と言う。 また「0・log(0)」は情報量の議論の上では「0」と読む。 // それはε→+0 の極限というよりも、 // 例えば二元エントロピーで「p1 = 1」とした時に // エントロピーがp1だけの自己情報量と一致するようにしたいから。 結合確率 A上の確率変数X, B上の確率変数Y に対して 結合確率（同時確率）とはp(x, y) = Pr{X=x, Y=y)のこと。 Yを気にしないXだけの確率を周辺確率と言ってp(x) = Pr{X=x, ∀y) = ∑y p(x, y)のことである。 またXとYが独立ならば、或いは独立であることの定義はp(x, y) = p(x)p(y)と表せること。 条件付き確率 Y=yが分かっている前提で、X=xとなる確率は、次のように表して ベイズ則とは次のように書けること。p(x|y) = Pr{X=x | Y=y} = p(x, y) / p(y)条件付きエントロピー まず、Y=yが分かってる時のXのエントロピーH(X|Y=y) = -∑x p(x|y) log(p(x|y))そして次が「条件付きエントロピー」で、 H(X|Y=y)についてyを全通り動かした時の期待値H(X|Y) = ∑x p(y) H(X|Y=y) = -∑x∑y p(x|y)p(y) log(p(x|y)) = -∑x∑y p(x, y) log(p(x|y))結合エントロピーH(X, Y) = -∑x, y p(x,y)log(p(x,y))相互情報量 Xのエントロピーと、Yを知った上でのXの(条件付き)エントロピーの差I(X;Y) = H(X) - H(X|Y) ≥ 0I(X;Y) = I(Y;X)が確かめられて、相互的なので「相互情報量」と呼ぶ。 相対エントロピー (ダイバージェンス) Aの上の確率分布p(x), q(x) について、D(p||q) = ∑x p(x) log[ p(x)/q(x) ]これをダイバージェンスという。 ||は気持ち、非対称を表していてD(p||q) ≠ D(q||p)である。 定理。D(p||q) ≥ 0 であり、等号成立は p=q の時に限る。 まず実数xに対して loge(x) ≤ (x-1) であるということ。y = loge(x) y = x - 1という二つのグラフは x = 1 において唯一接する。D(p||q) = ∑p log(p/q) -D = ∑ p log(q/p) ≤ ∑ p (q/p - 1) = ∑ (q-p) = ∑q - ∑ p = 1-1 = 0 ∴ D ≥ 0(以上) --- 12/9 情報源符号化 情報源であるアルファベットの列から符号アルファベットの列を作る。 復号化は逆に符号アルファベットの列から情報源アルファベット列を再現すること。 当然、一意的である必要がある。 語頭符号。語頭がユニークであるような符号のこと。瞬時、復号が可能だ。 符号の木。 二分木を考え、その末節の葉っぱに情報を対応させる。 ルートからその情報への行き方、例えば枝は常に二本以下だから左を0、 右を1とすれば、「0100」みたいにその情報を指定できて、そしてこれは その語頭符号として使える。 符号x、その集合Xについて符号の木を作る。 その節pが深さdであったとして、その節をルートとする部分木に含まれる 符号語の集合をXpとすると∑[x∈Xp] 2-|x| ≤ 2-d但し|x|は符号語xの符号長 →Kraftの不等式∑x 2-|x| ≤ 1H = -∑pi log(pi) L = ∑pi |xi|一意符号可能なら、 H ≤ L である。H - L ≤ ∑ pi((2-|xi|)/pi - 1) log2e = ∑ (2-xi - pi) log(e) ≤ 0 (Kraft)Kraft's inequalityは符号が一意復号可能であるための必要条件である。 1/13 --- ここからは加算と乗算についてニ元体(GF(2))で考える。つまり 数は0,1しかなくて、0 + 0 = 0 0 + 1 = 1 + 0 = 1 1 + 1 = 0 0・0 = 0 0・1 = 1・0 = 0 1・1 = 11+1以外は初等代数だ。 つまり、1より大きな数が存在しないので繰り上げが無い、と考えることにした。 また、「1を足し算する」とはその数を反転することと等価だ。 単一パリティ 0,1のkコの列、u = (u1, u2, .. uk) ∈ {0, 1}kを入力として、これに対しx = (u, p) ; p = ∑ uiとする。 pはGF(2)上の和であるから、結局p = 0 (when u contains even 1s) 1 (odd 1s)そしてそれをuに付加したものがyであるから、xは常に1を偶数コ含む。 このxを符号として送信する。 受信データをyとする。 yの中に1が奇数コだけ含まれた時、 それは通信路でエラーが起こったコトを意味する。 符号とはそのような機能を持つモノのコトであり、 そして今の場合の符号、これを単一パリティと呼ぶことにするが、 これは1bitの誤りに対してエラーを検出する、つまり 「1bit誤り検出」の能力を持つ。 2bitの誤りが起こった時には検出することはできない。 // 3bitではまた誤りを検出することが可能であるが、 // エラーのbit数は確率的に、0が最も多くて、単調減少であることが期待される。 // であるから、「2bit以上は検出がムリ」で切って考える。 水平、垂直パリティ。 単一パリティの拡張。 例えば6bitの入力uがあった時、それを2*3に並べて次のように パリティpを付加して符号xを作るx1 x2 x3 p1 x4 x5 x6 p2 p3 p4 p5 p6p1とは(x1, x2, x3)に対する単一パリティで水平パリティと呼ぶ。 p4は(x2, x5)に対する単一パリティ（垂直パリティ）。 p6は(p1,p2)に対する垂直パリティもしくは(p3, p4, p5)に対する水平パリティ であり、これはx1～x6の総和であるから当然一致する。 これは1bitの誤りを検出する上に、エラーを検出した水平パリティと垂直パリティ の二つを確認することでその交点にあるbitがエラーである、と突き止められるので 「1bit誤り訂正」の能力を持つ。 2bitの誤りに対しては、検出までは可能である。訂正はムリ。 したがって再送信を要求することが普通である。 入力: u ↓ [符号化] 送信語: x ↓ [通信路] 受信語: y = x + e (;e is error) ↓ [復号化] (eを取り除く必要) 出力: u ブロック符号入力 u ∈ {0, 1}k に対して 符号 x ∈ {0, 1}n (n > k)符号の集合は入力の集合を完全に包含し、入力の各点と一対一対応する 点の集合Cが、符号の中に存在する。 受信したデータがCから外れていたならば、誤りを検出したとして どうにか復号する。言葉の説明。 Hamming距離 二つのbit vectorの違うbit数のことで x, yに対してd(x, y)などと書く。 例えば
x = (0110011) y = (1100111) ⇒ d(x, y) = 3Hamming重み bit vectorの中の1の数のことであり、xに対してw(x)などと書く。 例えばw(0110011) = 4またGF(2)に注意するとd(x, 0) = w(x) d(x, y) = w(x-y)であるから、距離と重みは実際、同意義なのである。 2元対称通信路 (Binary Symmetric Channel, BSC) 0,1を送信すると確率的に0は0か1、1も0か1として受信される。 xを送信した時に(x+e)として受信される確率はp(x+e |x) = pt (1 - p)n-t ; t = w(e)最尤復号 (さいゆうふくごう) 受信語yに対して p(y |x) を最大とするようなx に復号するやりかた。 BSCである時、Hamming距離が最短の符号語を出力すればいい。 その為にも予め符号語同士のキョリを空けておくコトが重要。 符号語の間のキョリの中での最小キョリをd とする。 // Hammingキョリは当然いつも非負整数を取る。t = floor((t-1)/2)というt が重要で、それぞれの符号について、その符号を中心として 半径をt とする球はギリギリどれも衝突しない。 そして受信語がどれかの球の中に入っていたら、その球の中心に 復号スレば良いことになる。従って「t-bit誤り訂正」である。 線形符号 {0, 1}nの部分空間Cが∀ x, y ∈ C: x+y ∈ Cを満たす時、そのCを線形符号という。 // GF(2)の上ではスカラー倍も線形合成も // 上の一式だけで十分表現できてしまう。 またx + x = x - x = 0より、0 ∈ C0でない符号の内でHamming重みの最小値を最小重みと言い、 線形符号ならば、これは最小距離と一致する。 つまり、最小のキョリをとる(x, y)についてx - y = zとなるzが存在して、d(x, y) = w(z)であるから。 また、入力がk-bit、符号がn-bitである線形符号を「(n, k)線形符号」という。 線形ならば入力→符号は行列の掛け算で表せるだろう。 生成行列: G ∈ {0, 1}k * n を用いてx = uG//x, u は行ベクトルなのに注意 符号の集合は C = { uG | u ∈ {0,1}k } これからずっと線形符号の場合を考えるよ。 組織符号 生成行列G がG = (Ik, Gr) ; Ikはk行k列単位行列。Grは何か残りという形を取る時x = uG = (u, u・Gr)として復号するべきデータをそのまま含む。 このＧによって生成される符号を組織符号と言い、 (u, u・Gr) のu を情報ビット、u・Gr をパリティ検出ビットという。 内積。(x, y) = x・yt ∈ {0, 1}として定義できる。0なら直交してる。 パリティ検査行列入力 u ∈ {0, 1}k 符号 x ∈ {0, 1}n (n > k) x = uG (G ∈ {0, 1}k * nに対して「x ∈ C」⇔ 「Hxt = 0t」となるようなHをパリティ検査行列という。 なんかしらんけどH・Gt = G・Ht = 0となりゃあいいらしい。 --- 1/20 線形符号続き 入力u から、x = uG とするのが符号化であり、Gが生成行列。 符号語の集合を符号と言いC = { uG |u ∈ {0,1}k }であるがパリティ検査行列Hを用いるとC = { x |x ∈ {0,1}n, Hxt = 0t}// HはあるGに対して存在しているが、実際には // Hを先に作ってからそれに合うGを作る。 受信語y = x + e から送信語x を作るのが復号化。 そしてx はCの中でy とのキョリが最小である符号。e = y - x Het = Hyt - Hxt = Hyt (∵ xは符号であるからパリティ検査に通る) = s (シンドロームという)最尤信号とは「Het = s」となるようなeの中でHamming重みが最小と なるようなもののこと。そしてその最尤信号をエラーとしてx = y - eとする. この復号化のことをシンドローム復号という。 全てのシンドロームに対するeを予め計算しておくことができる。一般の線形符号についてパリティ検出行列とは、符号語xに対して「のみ」Hxt = 0tとなるもののことだった。 行列Hを列ベクトルのベクトル[h1, h2, .., hm}と考えればHxt = ∑ hi xi = 0xiの0でないトコだけ考えると、そこのhiは一次従属である。 よって次のような定理。 Thm. 符号Cの最小距離 d = d(C) に就いて Hの任意の(d-1)コの列ベクトルは一次独立であり、上手く選んだ dコの列ベクトルは一次従属となれる。巡回符号符号語 X = (x1, ..., xn) に対してf(z) = ∑xi zn-iという多項式表現と対応させる。 今、線形符号Cで、任意のCの元XについてX = (x1,x2, ..., xn)と書いた時、次のようなXを「シフト」した符号shift(X) = (x2, ..., xn, x1)というベクトルもまた、Cに属するような、そういう符号Cを「巡回符号」という。 巡回符号について多項式表現を考えると面白い。 X ～ f(z) = x1zn-1 + ... + xn shift(X) ～ x2zn-1 + ... + xnz + x1 ≡ x1zn + ... + xnz (mod (zn - 1)) = z・f(z) 即ち、K[z]/(zn - 1) の上で、符号のシフトは多項式表現のz陪に相当する。 線形符号であるから、i個シフトしたものの線形結合もまた符号であり、 符号に対するf(z)があった時、∑ ai zi f(z) = a(z)f(z)これもまた符号である。 符号CはK[z]/(zn-1)上でのイデアルと考えられる。 よって、任意の符号の多項式表現f(z)は、適当な多項式u(z)を用意することでf(z) = u(z)g(z) ;u(z) ∈ K[z]/(zn-1)と表されるような生成元g(z)が存在する。 (zn - 1)をg(z)で割るとh(z)g(z) + r(z) = (zn - 1) ≡ 0 mod (zn - 1) ∴ r ≡ -h・g deg(r) < deg(g) であるから(?)、r ≡ 0 即ち、g(z)・h(z) ≡ 0x∈C ならば、 x = a(z)g(z)と表せて xh = agh = a0 = 0 x∉C ならば、 x = qg + r (r ≠ 0) と表せて xh = qgh + rh = rh 次数の比較からrh ≢ 0よって「x(z)h(z) =0」⇔「x(z)∈C」このhはパリティ検査行列Hの多項式バージョンであり、 「パリティ検査多項式」という。
コメ(0) | トラ(0)