情報エレクトロニクス学科共通科目・２年次・第１学期〔必修科目〕 講義「情報理論」 情報エレクトロニクス学科共通科目・２年次・第１学期〔必修科目〕 講義「情報理論」 第9回 第5章 情報源符号化法 5.4 ひずみが許される場合の情報源符号化 2016/07/08 情報理論 講義資料

ひずみが許される場合とは？ ある程度ひずみを許しても、1情報源記号あたりの平均符号長を小さくしたい！（つまり、より小さくデータを圧縮したい） テキストの場合 ひずみを許す符号化 復号 001101011101110001・・・ ６時にスタバでね。ちゃんと来いよ。 ６時にスタバでねーちゃんと来いよ。 非常にまずい！ 画像の場合 ほとんど問題ない ひずみを許す符号 ビットマップファイル （.bmp; 288 KB) jpegファイル （.jpg; 17.5 KB） 2016/07/08 情報理論 講義資料

Communication channel 情報源符号化におけるひずみ 通信路でひずみが入るのではなく、符号化時にひずみを入れるることを許す 情報源 S 符号化 coding 復号 decoding あて先 destination ひずみ 理想的に伝達されると仮定 x y 図： 情報源出力 x と情報源復号結果 y 情報源 S 符号化 coding 通信路 Communication channel 復号 decoding あて先 destination ひずみ ひずみ測度： x と y の相違を評価する関数 d(x, y) 関数 d(x, y) が大きいほど、ひずみが大きい。また次の性質を持つ。 d(x, y)≧0 x＝y のとき d(x, y)＝0 ひずみ測度の平均値を平均ひずみと呼び、d で表す。 d＝∑∑d(x, y)P(x, y) x y 2016/07/08 情報理論 講義資料

ひずみ測度の例 例1 情報源アルファベットを A＝{0, 1} とし、ひずみ測度を d(x, y) ＝ 0 ; x＝y とする。このとき、平均ひずみは d ＝∑∑d(x, y)P(x, y)＝P(1, 0)＋P(0, 1) となる。これは、要するに、符号器の出力が元の情報源出力 と異なる確率であり、通常ビット誤り率と呼ばれる。 例2　情報源アルファベットを有限個の整数または実数の集合 としよう。このとき、ひずみ測度を d(x, y) ＝ | x－y |2 とすれば、平均ひずみは2乗平均誤差（mean square error）と 呼ばれる量となる。ひずみの評価量として非常によく用いられる。 d(x, y) ＝ 0 ; x＝y 1 ; x≠y P(1, 0)：入力 1 → 出力 0 P(0, 1)：入力 0 → 出力 1 x y 2016/07/08 情報理論 講義資料

ひずみが許される場合、情報源符号化定理はどうなるか？ ［情報源符号化定理］ 情報源S は、任意の正数εに対して、1情報源記号あたりの平均符号長Lが H(S) ≦ L ＜ H(S) +ε となるような2元瞬時符号に符号化できる。 しかし、どのような一意復号可能な2元符号を用いても、 平均符号長がH(S)より小さくなるような符号化はできない。 H(S)が限界！ ひずみを許せば、どのくらい平均符号長の限界を下げられるか？ S：記憶の無い定常情報源、X:任意の時点においてSから出力される情報源記号 1情報源記号あたりの平均符号長の下限 ＝ 情報量H(S)=H(X) ひずみを許した場合、出力Yの値を知っても、元の入力Xに関して、 なお平均 H(X |Y ) のあいまいさが残る。 伝えられる情報の量は I(X;Y )＝H(X)－H(X |Y ) ひずみを許した 場合の限界！ 2016/07/08 情報理論 講義資料

［ひずみが許される場合の情報源符号化定理］ 相互情報量I(X;Y ) が同じでも、平均ひずみ d は同じとは限らない ⇔ 平均ひずみ d が同じであっても、I(X;Y )は符号化の仕方で異なる ある与えられた値 D に対し、平均ひずみ d が d ≦ D を満たす条件の下で、あらゆる情報源符号化法を考えたときの 相互情報量 I(X;Y ) の最小値を考え、これを R(D) と表す。すなわち、 R(D) ＝ min {I(X;Y )} これを情報源S の速度・ひずみ関数（rate-distortion function）と呼ぶ。 d ≦ D ［ひずみが許される場合の情報源符号化定理］ 平均ひずみ d を D 以下に抑えるという条件の下で、任意の正数εに対して、情報源S を1情報源記号あたりの平均符号長Lが R(D) ≦ L ＜ R(D) +ε となるような2元符号へ符号化できる。しかし、どのような符号化を行っても、 d ≦ D である限り、LをR(D)より小さくすることはできない。 2016/07/08 情報理論 講義資料

速度-ひずみ関数(1) x y R(D) は、d ≦ D を満たす、あらゆる情報源符号化法を考えたときの I(X;Y ) の最小値。　では実際、これをどのようにして求めるのか？ 情報源符号化法を変えると、条件付確率 P( y| x) が変わる！ → I(X;Y ) の最小化は、d ≦D の条件の下で P( y| x) を変えることで行う＊ → 下図のような通信路を考え、この通信路の特性を変えることで I(X;Y ) の最小化を計ると解釈できる。この仮想的通信路を試験通信路と呼ぶ。 情報源S P(x) 試験通信路 P( y | x) あて先 x y 図: 試験通信路による速度・ひずみ関数R(D) の解釈 d ≦ D I(X;Y )最小化 ＊任意の条件付確率 P( y| x) を与えるような情報源符号化・復号法が存在する 2016/07/08 情報理論 講義資料

速度-ひずみ関数(2) 条件付確率 P( y| x) を用いれば、相互情報量 I(X;Y ) は I(X;Y )＝∑∑P(x, y)log2 ＝∑P(x)∑P(y|x) log2 と表せる。ここに P(y) は P(y) ＝∑P(x) P(y | x) により計算できる。また、d ≦D という条件は d ＝∑P(x)∑P(y | x) d(x, y) ≦ D と表せる。また、条件付確率は P(y | x) ≧ 0 ∑P(y | x) ＝ 1　for each x を満たさなければならない。 式②～④の条件の下に、式①のI(X;Y )を最小化すればよい！ P(x)P(y) P(x, y) x y P(y) P(y|x) ① P(x, y)＝P(x)P(y|x) x y P(y|x) が変数 他は既知 x ② x y ③ ④ y 一般には難しい 2016/07/08 情報理論 講義資料

⊕ [例]記憶のない２元情報源の場合(1/3) 1, 0 を確率 p, 1－p で発生する記憶のない2元情報源Sを考える。 また、ひずみ測度としては d(x, y) ＝ を用いるものとする。このとき、平均ひずみ d はビット誤り率となる。 この情報源に対して、0≦D≦0.5 が与えられたとき、 d≦D の元での速度・ひずみ関数 R(D)を求めよう。 相互情報量I(X;Y )＝H(X)－H(X |Y ) H(X)＝ H(p) なので、 H(X|Y) を最大化すればよい。 ここで、Y は左図のように、 1の発生確率が d である ような誤り源の出力E と X の排他的論理和で表せる。 0 ; x＝y 1 ; x≠y D>0.5 の場合は 誤る確率の方が 大きいことを意味する 図： 2元情報源に対する試験通信路 情報源S PX(1)＝p ⊕ E Y＝X  E 試験通信路 誤り源 PE(1)＝d X 2016/07/08 情報理論 講義資料

[例]記憶のない２元情報源の場合(2/3) Y＝X ⊕ E であるから、X＝Y ⊕ E となる。したがって、 H(X | Y)＝H(Y ⊕ E | Y)＝H(E | Y) が得られる。 H(E | Y) は Y の値を知ったときの E のあいまいさであるから、何も知らないときの E のあいまいさ H(E) より大きくなることはない。さらに、誤り源に記憶がなく定常であれば、H(E)＝ H( d ) であるが、そうでなければ、H(E)＜H( d ) であるから、 H(E | Y) ≦ H(E) ≦ H( d ) となる。それゆえ H(X | Y) ≦H( d ) を得る。d≦D≦1/2 なので、さらに H( d ) ≦H(D) となる。したがって、相互情報量 I(X;Y ) は、 I(X;Y )＝H(X)－H(X |Y )≧ H(p)－H(D) I(E;Y ) H(E | Y) H(Y | E) H(E) H(Y) H(E, Y) 2016/07/08 情報理論 講義資料

[例]記憶のない２元情報源の場合(3/3) d=Dで誤り源が無記憶定常で情報源Sと独立であるとき、等号が成立 　(I(X;Y )＝ H(p)－H(D)) するので、 記憶のない定常2元情報源S の速度・ひずみ関数は R(D)＝ H(p)－H(D) で与えられることが導けた。 左図で分かるように、速度・ひずみ 関数は、Dに関して単調減少であり、 下に凸な関数である。一般の速度・ ひずみ関数も同様な性質を持つこと が証明されている。 記憶のある情報源の場合にも、 　　I(X;Y )＝lim I(Xn;Yn)/n の最小値として、速度・ひずみ関数を 定義することができる。 図： 2元情報源の速度・ひずみ関数 R(D) D n→∞ 2016/07/08 情報理論 講義資料

ひずみが許される場合の情報源符号化法(1) ［ひずみが許される場合の情報源符号化定理］ 平均ひずみ d を D 以下に抑えるという条件の下で、任意の正数εに対して、情報源S を1情報源記号あたりの平均符号長Lが R(D) ≦ L ＜ R(D) +ε となるような2元符号へ符号化できる。しかし、どのような符号化を行っても、 d ≦ D である限り、LをR(D)より小さくすることはできない。 ひずみが許される場合の情報源符号化定理は、1情報源記号あたりの平均符号長を、速度・ひずみ関数 R(D) にいくらでも近づく符号化法の存在を示している。では、具体的な符号化方法はあるのか？ ひずみのない場合に比べて、はるかに難しい！ ベクトル量子化 変換符号化 予測符号化 etc. 参考図書 「情報・符号・暗号の理論」 今井秀樹 著、電子情報通信学会 2016/07/08 情報理論 講義資料

ひずみが許される場合の情報源符号化法(2) 情報源S P(x) CDへの符号化 x → w dn(x, w)最小 ひずみのない場合の情報源符号化 x w x, w は長さ n の系列　　w∈CD 図5.6 ひずみが許される場合の情報源符号化法 １） まず、情報源S の情報源アルファベットA の記号からなる長さ n の系列を N 個選び、それを符号語とする符号CD を作っておく。 ２） 情報源S から発生する長さ n の系列 x＝x1x2・・・xn に対し、CDの中から、ひずみ測度 dn(x, w)＝∑ d(xi, wi) が最小となるような符号語 w＝w1w2・・・wn ∈CD を選ぶ。 ３） この符号語に対し、ひずみのない場合の情報源符号化を行う。 i＝1 n d(x, y)は与えられる 2016/07/08 情報理論 講義資料

ひずみが許される場合の情報源符号化法(3) n次ベクトル空間 図5.7 はこの符号化法の概念図 図の各点は長さ n の系列 2重丸（青）で示されているのが CDの符号語 ひずみ測度が、左図において 距離に比例するものとする。 このとき、符号化は図の矢印の ように行われる。 つまり、この図の例では符号語と 　そのまわりの8個の系列を一つの 　符号語で代表させてしまう。 符号CD は、このように符号化したときに、平均ひずみができるだけ小さくなるように選ぶべきである。また、平均ひずみが同じであれば、符号語数の少ないことが望ましい。 図： CDへの符号化の概念図 CDの具体的構成法は 知られていない 2016/07/08 情報理論 講義資料

[例]無記憶２元情報源のひずみあり符号化(1/2) 1, 0 を確率 p, 1－p で発生する記憶のない2元情報源を考える。 また、ひずみ測度としては d(x, y) ＝ を用いるものとする。このとき、平均ひずみ d はビット誤り率となる。 ここで、CD として CD＝{000, 111} を考える。 CDへの符号化は、情報源系列とのひずみが最も小さい符号を選ぶことにより行われる。すなわち 0 0 0 1 1 1 0 0 1 1 1 0 0 1 0 1 0 1 1 0 0 0 1 1 とすればよい。 0 ; x＝y 1 ; x≠y 0 0 0 1 1 1 2016/07/08 情報理論 講義資料

[例]無記憶２元情報源のひずみあり符号化(2/2) このとき、平均ひずみは1情報源記号あたり 　　d＝1/3 ［3p(1－p)2 ＋ 3p2(1－p)］ となる。また、CDに符号化したとき、 符号語000, 111の発生確率はそれぞれ、 (1－p)3＋3p(1－p)2、3p2(1－p)＋p3 であるから、これに対し、ひずみのない 情報源符号化を行えば、1情報源記号 　あたりの平均符号長 L は 　　LB＝1/3［H( (1－p)3 ＋ 3p(1－p)2 )］ にいくらでも近づけることができる。 一方、d だけひずみを許すとき、平均 符号長 L の下限は 　　LI＝ H(p)－H( d ) となることが判る。 LB は LI の2倍近い値になっている。 図5.8 例5.5の符号化による平均ひずみ d および1情報源符号あたりの平均符号長の下限LB と LI p LB H(p) d LI 2016/07/08 情報理論 講義資料