• 締切済み

情報源符号化

情報源符号化定理で， M元情報源において 　　H(S^k) = kH(S) が成り立つなら 　　H(S^k+1) = (k+1)H(S) が成り立つことを証明せよ． という問題なのですが・・・ これを証明する場合 M元の情報を例えば2元として S^k+1のi番目の情報源記号をS_iとしてそのときの 生起確率をP(S_i)として H(S^k+1) = -Σ^(2^k+1)_i=1P(S_i)log_2P(S_i) を解いて証明するのでしょうか？ それともこの証明方法が根本的におかしいのでしょうか？（ M元のままで証明するべき？ ）

みんなの回答

noname#21330
noname#21330
回答No.1

仮定にS^kの発生確率がS^k+1の発生確率のサブセットであるというようなことが必要と思いますが、次のようになると思います。 Piを各元の発生確率とする。 H(S)=-ΣPi*log(Pi) 　(i=1,---,M) Qkを拡大した各元の発生確率とする。 H(S^k)=-ΣQk*log(Qk)=-kΣPi*log(Pi) (k=1,--,M^k) S^k+1は、S^kよりさらに情報拡大されますので、 各元の発生確率は、 Pi*Qk (i=1,---,M)&(k=1,--,M^k)となり、 H(S^k+1)=-ΣΣPi*Qk*log(Pi*Qk) =-ΣΣPi*Qk*(log(Pi)+log(Qk)) =-ΣΣPi*Qk*log(Pi)-ΣΣPi*Qk*log(Qk) ΣQk=1,ΣPi=1なので、 　　　　=-ΣPi*log(Pi)-ΣQk*log(Qk) =-(k+1)ΣPi*log(Pi)

hecaton
質問者

お礼

ありがとうございました． 何とか解決することができました．

  1. カテゴリ
  2. 学問・教育
  3. 数学・算数

関連するQ&A

  • ２元消失通信路(BEC)の伝送情報量

    記号0の生起確率を p 、判定不能率を u とした時の２元消失通信路の伝送情報量が I (A;B) = (1-u)H(p) で表されることを証明してください。お願いします。

  • 情報理論でのハフマン符号・・・？

    　学校で情報理論を習っていて、 ハフマン符号化のやり方は、習いました。 　２元情報源を非等長でハフマン符号化は、 たとえば、0,1を確率0.8,0.2で発生する 記憶のない情報源ｓでは、確率の大きい0の ランレングスを利用すれば、２元情報源を ランレングスハフマン符号化すればできる らしいのですが、 ４元情報源を非等長でハフマン符号化をす るのには、どうすれば分かりません。 ２元と同じようにランレングスでできる らしいのですが・・・。 　どなたかアドバイスお願いします。

  • ハフマン符号　情報源記号と符号語の対応表

    Ｓ＝(a1 0.15 , a2 0.3 , a3 0.05 , a4 0.2 a5 0.25 , a6 0.05) この情報源Ｓに対するハフマン符号をハフマン符号の木を構成することにより、情報源記号と符号語の対応表を示せ。 という問題があるのですが、これについて質問です。 符号の木は、これらのa1~a6が二進数でどうなるのかがわからないと書けないと思うのですが、この問題にはその二進数の割り当てがしてありません。 これは最初からa1ならば0やa2ならば01という風に決まっていたり、また、勝手に割り当ててもいいのでしょうか？ どなたかご教授お願いします。

  • フェルマの小定理の証明方法について

    フェルマの小定理の証明は、ふつうは、二項定理と数学的帰納法、または、オイラーの定理を使うようです。以下の証明で、（式ａ）から（式ｂ）に移るのは妥当なのか、よくわかりません。 [蛇足] フェルマの小定理より、オイラーの定理の証明のほうが簡単なのは違和感を感じるのですが・・・。フェルマの小定理の簡明な証明方法があったら、それも教えてほしいです。 ●オイラーの定理 (a,m)=1のとき　　　 a^(φ(m))≡1 (mod m) 【フェルマの小定理】 a^(p-1)≡1 (mod p) 　ただし、aは正の整数（←条件を、少し制約しました。）、pは素数、ａとｐは互いに素（(a,p)=1） とする。 ■証明 数学的帰納法を用いる。 (1)a=1 のときは明らか。 (2)a=k のとき成り立つと仮定して、a=k+1のとき成り立つことを証明する。 言い換えると、mod p において、 k^p≡k ⇒　(k+1)^p≡k+1 を証明すればよい。 以下、合同式は mod p の場合のことを指す。 仮定より、 (k)^p≡k (k)^p-1≡k-1 F(k)=k^(p-1)+k^(p-1)…+1 とおくと、 (k-1)・F(k)≡k-1 よって、 F(k)≡1 ところで、F(k)はp個の元から構成されており、 p-1 Σ(k^m)≡1　　　　　　　　　　（式ａ） m=0 と書き直せる。ここで、kをk+1に置き換えるが、加法+と乗法・を交換則、結合則、分配則をみたす演算子*とすると、 p-1 Σ((k)^m*(1)^m)≡1　　　　　（式ｂ） m=0 と書ける。これより、 　p-1 k・Σ((k)^m*(1)^m)≡k 　m=0 　　　　　p-1 (k*1-1)・Σ((k)^m*(1)^m)≡k 　　　　　m=0 よって、 (k*1)^p-1≡k 書き直して、 (k+1)^p≡k+1 　　　　<証明終>

  • ｐ＝２ｋ＋３ の必要十分条件！（書き直し）

    ｐを任意の奇素数とします．つまり， ｐ∈｛３，５，７，１１，１３，１７，・・・｝です． Ｈを非負整数の集合とします．つまり， Ｈ :＝｛０，１，２，３，４，５，６，・・・｝です． Ｓ を Ｈ の真部分集合とします．つまり，Ｓ ⊂≠ Ｈ です． 記号 ⊂≠ は，⊂ の下に ≠ を書く，真部分集合を表す記号です． ｋ を Ｓ の元とします．つまり，ｋ∈Ｓ です． ここからが質問です． ｐ＝２ｋ＋３ を満たすための必要十分条件は，どう表現すれば， 完全と言えるでしょうか？ 解答例（１）：　ｐ＝２ｋ＋３ を満たすための必要十分条件は， ｋ∈Ｓ が ｋ＝(ｐ－３)/２ で与えられることである． この例（１）の表現で完全と言えるでしょうか？ 何か，落とし穴が潜んでいないでしょうか？？ 必要十分条件を記述するための定義に不備は無いでしょうか？？ 教えて下さい．おねがいいたします． （証明を書いていただけると，有り難いのですが・・・？） 念のため，ｐ＝２ｋ＋３ を満たす ｐ と ｋ の部分的な表を載せておきます． 　ｐ　｜　　ｋ ―――――――― 　３　｜　　０ 　５　｜　　１ 　７　｜　　２ １１　｜　　４ １３　｜　　５ １７　｜　　７ １９　｜　　８ ２３　｜　１０ ２９　｜　１３ ３１　｜　１４ ３７　｜　１７ 　・　　　　・ 　・　　　　・ 　・　　　　・

  • 大学の情報理論の課題でわからないところがあります。

    大学の情報理論の課題でわからないところがあります。 誰か解説をお願いします。 (問題1） ｛0,1｝の二元符号の通信路で、ビット誤り率0.25 の通信路がある。 ｛0.1｝のシンボル生起確率がそれぞれ ｐ, １－ｐ の時、 (a)通信路行列を書け (b)相互情報量を式で書け (c)通信路容量を求めよ (問題2) 0101 を生成多項式 G(x) = x^3＋x+1 の CRC符号 により符号化し、送信符号のビット列を書け 教科書や配布された資料に載ってる解説や公式を見ても どう当てはめていけばよいかわからず困っています。 よろしくお願いします。

  • 単純マフコフ情報源のエントロピー

    単純マフコフ情報源のエントロピーの式のイメージがいまいちつかめません。 H(Xt) = H(Xt|Xt-1) ということで、一つ前の生起した記号がわかっている条件下でのXt、ということだと思うのですが、なぜ条件付きエントロピーにするのでしょうか？ よろしくお願いします。

  • チェビシェフの定理と大数の法則

    平均をm、標準偏差をs、サイズN、値をx_k、度数をf_kとしたとき チェビシェフの定理は m-ks<x<m+ks (k>=1) なる範囲にあるデータは(1-1/k^2)*N以上である と本にあり、それの証明で s^2=Σ(k=1からn)(x_k-m)^2*f_k >=Σ(|x_k-m|>=ksなるkの和)(x_k-m)^2*f_k/N >=Σ(|x_k-m|>=ksなるkの和)(ks)^2*f_k/N・・(1) =(ks)^2/NΣ(|x_k-m|>=ksなるkの和)f_k・・(2) より Σ(|x_k-m|>=ksなるkの和)f_k<=N/k^2 よって Σ(|x_k-m|<ksなるkの和)f_k>=(1-1/k^2)*N と証明しているのですが(1)から(2)にするときΣはkの和をとっているのになぜ(ks)^2のkをΣから勝手に出せるのでしょうか？ また大数の定理 同一期待値μ、同一分散σ^2を持つ互いに独立な確立変数の平均を X~=(X_1+X_2+・・・+X_m)/n とおけば任意のεについて n→∞のとき、P(|X~-μ|<ε)→1 が成り立つ。 とありますがそもそもP(|X~-μ|<ε)というのが非常に理解しがたいのです この定理を理解するためになにか簡単な具体例とかをできれば教えてください。 またこの定理の証明でチェビシェフの定理で k=ε/s,s=σ/√nとおいて証明していますが このようにおく根拠or理由というのが全く想像がつきません。 長い文章になってしまい申し訳ありませんがぜひぜひ教えてくださいお願いします。

  • 2元ハフマン符号化プログラムが作れなくて困っています。

    以下のC言語のプログラムを作成出来る方、いらっしゃいましたらソースファイルを載せて下さい。 2元ハフマン符号化プログラム：具体的な無記憶情報源が入力されたときに、そのハフマン記号を出力される ご教授よろしくおねがいします

  • 素因数分解と分数

    以下の問題を解いていて、解答に納得がいかないので教えてください。 問）a_1,...,a_n(n>1)を0でない整数とする。ある整数pと正の整数hとが存在して、 a_1,...,a_nのうちの一つのa_iだけがp^hで割り切れ、他のa_jはどれもp^hでは割り切れないとする。そのとき、 S=1/a_1+1/a_2+...+1/a_n （＊） は整数でないことを証明せよ 解）「a_iを割り切る最大のべきをp^k」とし、mをa_1,a_2,...,a_i/p^k,...,a_nの最小公倍数とする。（＊）の両辺をm倍すると、右辺のm/a_i以外の項は整数だが、mはp^hで割り切れないのでm/a_iは整数でない。 ここで不思議に思ったのは、「」の部分でなぜ最大のべきを置いたかです。 m'として、a_1,a_2,...,a_i/p^h,...,a_nの最小公倍数としても問題ないと思います。 a_iにp^hで割っていること、p^hの素因数をa_i以外がもたないこと、この二つから、 m'のpの指数はa_iのpの指数（p^k)を超えることはないのではないかと思います。 これで、m'/a_iが整数でないことが示せると思います。 大変長く、わかりにくくなってすみません 何か自分が勘違いしているのか、他に見逃しているところがあるのか教えてください。

注目のQ&A

カテゴリ

専門家に質問してみよう

職業から探して質問する

あなたにピッタリな商品が見つかる！ OKWAVEセレクト

質問する