ある非定常な情報源クラスに対して最適レートを達成する因果

信州大学工学部
学士論文
ある非定常な情報源クラスに対して
最適レートを達成する因果的な量子化器
指導教員
学科
学籍番号
氏名
西新幹彦准教授
電気電子工学科
10T2058E
園木佑介
2014 年 3 月 25 日
目次
序章
1
1.1
研究の背景と目的 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
1.2
構成 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
歪みを許す因果的な符号化
1
2.1
情報源符号化と量子化器 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1
2.2
因果性と最適レート . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3
3
定常無記憶情報源に対する既存の結果
4
4
ブロック毎に定常無記憶な情報源
5
4.1
情報源と量子化器の特徴 . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5
4.2
ブロック量子化器の必要性
. . . . . . . . . . . . . . . . . . . . . . . . . . .
7
4.3
ブロック量子化器の最適性
. . . . . . . . . . . . . . . . . . . . . . . . . . .
8
1
2
まとめ
5
10
謝辞
11
参考文献
11
付録 A
補題の証明
12
A.1
補題 1 の証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
12
A.2
補題 2 の証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13
A.3
補題 3 の証明 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
15
i
1 序章
1.1 研究の背景と目的
現代の情報社会において扱うデータ量は膨大なものとなってきている．これらのデータをそ
のまま伝送することは非常に効率が悪い．そこで，情報源を効率よく符号化し，通信時間や通
信量を抑える情報圧縮技術は必要不可欠なものである．このような通信では，元の情報源とこ
れを符号化・復号化したものの間に一定の歪みを許容し，その上でどのような量子化器を使え
ば符号化レートがおさえられるかを考える事が重要である．その事について，1982 年に [1] で
David L.Neuhoﬀ らによって，与えられた許容歪みを達成した上で符号化レートを最小化する
為には，情報源系列の各文字に独立に作用する量子化器を 2 種類用意し，それらを一定の割合
で使用すればよいことが示された．本論文では，ブロック毎に定常無記憶な情報源に対して量
子化する場合には，１文字ずつではなく，ブロック毎に量子化することで最小の符号化レート
が得られることを示す．
1.2 構成
以降，本論文では，2 章で情報源符号化及び量子化器，因果性と最適レートについて述べ，
3 章で定常無記憶情報源及び無記憶量子化器についての説明と，達成し得る最適レートについ
てを述べ，4 章でブロック毎に定常無記憶な情報源の特徴及びブロック量子化器を用いた最適
レートと任意の量子化器の符号化レートとの比較の過程とその結果について述べ，5 章でまと
めとする．
2 歪みを許す因果的な符号化
2.1 情報源符号化と量子化器
情報源とは，情報源アルファベットと呼ばれる集合 X に値をとる確率変数 X = {Xk }∞
k=−∞
である．
情報源符号化は次のような手順で行われる．符号器は情報源 X を見て二進系列
Z = {Zk }∞
k=1 を生成する．この二進系列を符号語と呼ぶ．復号器は符号語を受け取り，
ˆ1, X
ˆ 2 , · · · を生成する．復号
X1 , X2 , · · · の復元として，復号アルファベット Xˆ に値をとる X
ˆ = {X
ˆ k }∞ を復号系列と呼ぶ．ここで，符号器が限りなく過去の文字を見
器が生成する X
k=1
ている一方で，受信者には X1 , X2 , · · · を届けることのみを考えていることに注意されたい．
符号器と復号器の組を単に符号と呼ぶ．
1
n
系列の表記法として xn
m , (xm , · · · , xn ) を定義する．また，Xm は xi ∈ X からなる系列
xm
n の全体を表す．
∞
ˆ
一般に，写像 fk : X−∞
→ Xˆ の列 {fk }∞
k=1 を量子化器と呼ぶ．情報源 X と復号系列 X
の関係は量子化器を用いて
∞
ˆ k = fk (X−∞
X
),
k = 1, 2, · · ·
と表される．符号が与えられると，符号器と復号器の直列接続として量子化器が自然に定義さ
れる．このような量子化器を符号から導かれる量子化器と呼ぶ．一般的な通信モデルを図 1 に
表す．図 1 では情報源 X を符号器によって二進系列 Z が生成され，Z が復号器によって復
ˆ となる．歪み ρ(x, x
ˆ との間で発生する．
号系列 X
ˆ) は X と X
図1
一般的な通信
図 1 の符号器と復号器から導かれる量子化器の出力を図 2 のように歪みなしで符号化する
場合，その性能は図 1 の通信モデルより悪くはならない．したがって，一般性を損なうことな
く，本研究では情報源を量子化器で歪ませた上で，歪みの無い符号器及び復号器によって通信
するものとして考える．
図 2 量子化器を用いた通信
2
2.2 因果性と最適レート
k
量子化器 {fk } が因果的であるとは，任意の k = 1, 2, · · · に対し，xk−∞ = y−∞
であれば
∞
fk (x∞
−∞ ) = fk (y−∞ )
が成り立つことをいう．これは，直感的には，量子化器の出力が未来の入力によらないことを
意味している．符号から導かれる量子化器が因果的であるとき，その符号を因果的であるとい
う．符号から導かれる量子化器が因果的であるということと，符号器の入力と復号器の出力の
間に遅延が発生することは無関係である．以降，本研究では量子化器はすべて因果的であると
仮定する．したがって，いちいち因果的と断らない場合もある．
本研究では，非負実数値をとる文字単位の歪み測度 ρ(x, x
ˆ), x ∈ X , x
ˆ ∈ Xˆ に基づいて情報
源と復号系列の間の歪みを定義する．長さ K の文字列の歪みを
K
1 ∑
ρ(xi , x
ˆi )
K i=1
ρK (xK
ˆK
1 ,x
1 ),
と定め，情報源 X に対する量子化器 {fk } の平均歪みを
[
]
ˆ 1K )
ρ({fk }) , lim sup E ρK (X1K , X
(1)
K→∞
と定める．符号の平均歪みとはその符号から導かれる量子化器の平均歪みのことである．歪み
測度 ρ に対し，最小の平均歪みを，
[
]
Dmin , E inf ρ(X, x
ˆ)
x
ˆ∈Xˆ
と定める．これはしばしば 0 となる事が多い．
符号が 1 秒間に送る情報量を表す符号化レート r を
r , lim sup
K→∞
]
1 [
∞
E LK (X−∞
)
K
(2)
∞
ˆ K を復元するときまでに復号器が受け取った bit 数の合
と定める．ここで，LK (X−∞
)はX
計である．例えば，符号器が x∞
−∞ を受け取り，z1 , z2 , z3 . . . zl を生成し，zl までを受け取っ
た復号器が x
ˆK を生成するとき，LK (x∞
−∞ ) = l となる．
D > Dmin に対し，平均歪みが D 以下であるような任意の因果的な符号の符号化レートの
下限を rc (D) と定義し，任意の符号を用いた最適レートと呼ぶ．[1] の結果より，次の定理が
分かっている．
3
定理 1 任意の符号を用いた最適レートは，平均歪みが D 以下であるような因果的な量子化
器の全体 Fc (D) を用いて，
ˆ
rc (D) = inf H(X),
Fc (D)
ただし D > Dmin
(3)
ˆ は，復号系列 {X
ˆ k } のエントロピーレートを表しており，
と表される．ここで，H(X)
ˆ , lim sup 1 H(X
ˆ 1K )
H(X)
K→∞ K
1
= lim sup H(f (X K ))
K→∞ K
(4)
ˆ
ˆK) は X
ˆ K のエントロピーである．特に {X
ˆ k } が定常である時，H(X)
と定義される．H(X
1
1
は，
ˆ = lim 1 H(X
ˆ 1K )
H(X)
K→∞ K
のように極限で表すことができる．
3 定常無記憶情報源に対する既存の結果
定常無記憶情報源とは，情報源に定常性があり，かつ記憶の無い情報源のことである．情報
源 X は k 番目に対して Xk で表される．無記憶な量子化器とは，情報源 1 文字を見て，復号
系列 1 文字を生成する量子化器である．無記憶な量子化器を f m とすると，k = 1, 2, . . . に対
ˆ k の間には
して，情報源 Xk ，復号系列 X
ˆ k = f m (Xk )
X
の関係がある．平均歪みは
]
K
1 ∑
ˆ
ρ(Xi , Xi )
ρ(f ) = lim sup E
K i=1
K→∞
[
m
= lim sup
K→∞
= lim sup
K→∞
K
1 ∑
ˆi)
Eρ(Xi , X
K i=1
K
1 ∑
ˆ1)
Eρ(X1 , X
K i=1
= EρK (X1 , f m (X1 ))
で書ける．これは情報源が定常である為，情報源と復号系列のある 1 組の歪みが分かれば，系
ˆ は，
列の平均歪みが分かるという事である．ここで，エントロピーレート H(X)
ˆ = H(X
ˆ 1 ) = H(f m (X1 ))
H(X)
4
と書ける．
定義 1 定常無記憶情報源 X に対して無記憶量子化器を適用したときの許容歪み D を満たす
符号化レートの下限を rcm (D) と書き，無記憶量子化器を用いた最適レートと呼ぶ．
定義 1 では単一の量子化器を使い続ける場合を考えているが，2 つの量子化器を一定の割合
で使用することもできる．いま，2 つの無記憶量子化器 Q1 , Q2 を考え，それぞれの平均歪み
を D1 , D2 , 符号化レートを r1 , r2 とおく．各 k = 1, 2, . . . に対して，nk ∈ {1, 2} が定めら
れ，Xˆk = Qnk (Xk ) のように量子化するとする．このとき
K
1 ∑
1{nk = 1}
K→∞ K
λ , lim
k=1
が存在するならば上記の方法による平均歪みと符号化レートはそれぞれ λD1 + (1 − λ)D2 ,
λr1 + (1 − λ)r2 となる．これを，量子化器 Q1 , Q2 を λ : 1 − λ の割合で使用するタイムシェ
アリングという．言い換えると，タイムシェアリングを用いることによって，2 つの量子化器
を内分する任意の性能が実現できる．なお，λ が存在するならば nk は確率変数であっても
よい．
定義 2 情報源 X に対し，2 つの定常無記憶量子化器をタイムシェアリングで適用したときの
許容歪み D を満たす符号化レートの下限を r¯cm (D) と書き，定常無記憶量子化器のタイムシェ
アリングを用いた最適レートと呼ぶ．
r¯cm は，rcm の凸包となり，その様子は図 3 となる．
[1] の結果から，次の等式が分かっている．
定理 2 定常無記憶な情報源に対して，
rc (D) = r¯cm (D)
が成り立つ．これは，定常無記憶な情報源に対して最適レートを達成するような量子化器は，
1 文字ずつ量子化する量子化器を許容歪みに合わせてタイムシェアリングする事によって得ら
れる事を示している．
4 ブロック毎に定常無記憶な情報源
4.1 情報源と量子化器の特徴
本論文では，非定常な情報源の 1 つとして，ブロック長 N （N は自然数）のブロック毎に
mN
定常無記憶な情報源について考える．情報源 X は m 番目のブロックについて {X(m−1)N
+1 }
で書くことができ，ブロック内では記憶を持っていても構わない．
ブロック量子化器 f b は，ブロック長 N によって特徴付けられ，情報源を N 毎に量子化す
5
図3
最適レートの一例
b
る．つまり，f b は，(f1b , f2b , . . . , fN
) の列であると言え，
b
b 2
b
N
f b (xN
1 ) , (f1 (x1 ), f2 (x1 ), . . . , fN (x1 ))
ˆ は
と表せる．また，量子化器 f b によって生成される復号系列 X
ˆ 1N = f b (X1N )
X
ˆ 2N = f b (X 2N )
X
N +1
N +1
..
.
b
mN
ˆ mN
X
(m−1)N +1 = f (X(m−1)N )
..
.
と書ける．
長さ N のブロック毎に定常無記憶な情報源 X に対して，長さ N のブロック量子化器 f b
を適応する場合，平均歪みと符号化レートは次のように表される．
補題 1 情報源 X に対する長さ N のブロック量子化器 f b の平均歪み ρ(f b ) は，
ˆ 1N )]
ρ(f b ) = E[ρN (X1N , X
と表される．証明は付録 A.1 に示す．
補題 2 情報源 X に対する長さ N のブロック量子化器 f b の符号化レートは
r=
1
H(f b (X1N ))
N
と表される．証明は付録 A.2 に示す．
6
4.2 ブロック量子化器の必要性
今，表 1 に示すブロック毎に定常無記憶な情報源の一例に対して，無記憶な量子化器及びブ
ロック量子化器を使用した場合を考える．この情報源はブロック長が 2 で，遇数番目の文字は
奇数番目の文字に依存している．この情報源に対して，無記憶な量子化器をタイムシェアリン
表1
ブロック毎に定常無記憶な情報源の一例
X2m
X2m−1
0
1
0
0.5
0.1
1
0.1
0.3
グで使用した場合の最適レート及びブロック量子化器の最適レートと，それをタイムシェアリ
ングで使用した場合の最適レートを図 4 に表す．
図4
無記憶な量子化器とブロック量子化器の比較
図 4 から分かるように，ブロック毎に定常無記憶な情報源に対して，ブロック量子化器をタ
イムシェアリングで使用した場合の最適レートは，無記憶な量子化器をタイムシェアリングで
使用した場合の最適レートを常に下回っている事がわかる．よって，ブロック毎に定常無記憶
な情報源に対して，無記憶な量子化器をタイムシェアリングで使用することが最適ではないこ
とが分かる．
7
4.3 ブロック量子化器の最適性
この節では，情報源に対し任意の量子化器を使った際の符号化レート rc (D) とブロック毎に
b(N )
定常な量子化器のレート rc
b(N )
(D) の凸包である r¯c
(D) とを比較する．
b
定義 3 情報源 X に対してブロック量子化器 f を適用したときの許容歪み D を満たす符号
b(N )
化レートの下限を rc
(D) と書き，ブロック量子化器を用いた最適レートと呼ぶ．
定義 4 情報源 X に対し，2 つの量子化器をタイムシェアリングで適用したときの許容歪み D
b(N )
を満たす符号化レートの下限を r¯c
(D) と書き，ブロック量子化器のタイムシェアリングを
用いた最適レートと呼ぶ．
b(N )
ここで，関数 r¯c
b(N )
(·) は rc
(·) の下からの凸包をとったものとなる事に注意されたい．し
たがって，
r¯cb(N ) (D) ≤ rcb(N ) (D)
(5)
が成り立つ．また，どちらも単調減少である．
ブロック量子化器を使用した際の最適レートと任意の因果的な量子化器を使用した際の最適
レートの間には次の関係が成り立つ．
定理 2 ブロック毎に定常無記憶な情報源に対して
rc (D) = r¯cb(N ) (D)
(6)
が成り立つ．
（証明）2 つの因果的な量子化器のタイムシェアリングもまた 1 つの因果的な量子化器であ
るので
rc (D) ≤ r¯cb(N ) (D)
b(N )
は自明である．したがって以降は rc (D) ≥ r¯c
u
(i)
,
(i−1)N
x−∞
(i−1)N
(D) を示す．そのためには，U (i) , X−∞
，
とおいて，
rcL(N ) (D) = inf lim sup
Fc (D) K→∞
L(N )
なる量を導入し，rc (D) ≥ rc
K
1 ∑ 1
(i)
ˆ iN
H(X
)
(i−1)N +1 |U
K i=1 N
b(N )
(D) ≥ r¯c
(D > Dmin )
ˆ は Fc (D)
(D) を示せばよい．ここで，右辺の X
に属する任意の量子化器によって生成されていることに注意されたい．
L(N )
まず，rc (D) ≥ rc
(D) を示す．
(i−1)N
ˆ iN
H(X
(i−1)N |X−∞
ˆ iN
ˆ (i−1)N )
) ≤ H(X
(i−1)N +1 |X1
8
である事に注意すれば，
K
K
1 ∑
1 ∑
(i)
ˆ iN
ˆ iN
ˆ (i−1)N )
H(X
) ≤ lim sup
H(X
(i−1)N |U
(i−1)N +1 |X1
KN i=1
KN
K→∞
i=1
lim sup
K→∞
1
ˆ 1KN )
H(X
K→∞ KN
1
ˆ 1K )
≤ lim sup H(X
K
K→∞
ˆ 1K )
= H(X
= lim sup
を得る．ここで，両辺の inf をとれば
rcL(N ) (D) ≤ rc (D)
となる．
L(N )
b(N )
(D) ≥ r¯c
(D) を示す．そのために今，任意の量子化器 {fk } ∈ Fc (D) を考
(m)
ˆ はこれによって生成されているとする．条件付きエントロピー H(X
ˆ mN
え，X
) は，
(m−1)N |U
次に，rc
(m−1)N
確率変数 X−∞
(m−1)N
から得られる確率測度 µ−∞
を用いて
∫
(m−1)N
ˆ mN
H(X
(m−1)N +1 |X−∞
)=
(m−1)N
(m)
ˆ mN
H(X
= u(m) )dµ−∞
(m−1)N +1 |U
(m−1)N
と書く事ができる．ここで {fk } を用いて u(m) ∈ X−∞
(u(m) ) (7)
に対してブロック量子化器
b
fm,u
(m) を
N
(m)
b
x1 ), . . . , fmN (u(m) xN
fm,u
(m) (x1 ) , (f(m−1)N +1 (u
1 ))
と定義する．すると，
mN
b
ˆ mN
X
(m−1)N +1 = fm,U (m) (X(m−1)N +1 )
が成り立つので，情報源がブロック毎に定常無記憶であることから，
mN
(m)
(m)
b
ˆ mN
= u(m) )
H(X
= u(m) ) = H(fm,u
(m) (X(m−1)N +1 )|U
(m−1)N +1 |U
mN
b
= H(fm,u
(m) (X(m−1)N +1 ))
b
N
= H(fm,u
(m) (X1 ))
(8)
と書ける．
b
今，ブロック量子化器 fm,u
(m) の平均歪みを
˜ u(m) , ρ(f b (m) )
D
m,u
b
˜
とおく．すると fm,u
(m) は平均歪み Dum を達成し，さらに補題 2 より，その符号化レートは
1
b
N
N H(fm,u(m) (X1 ))
である．よって式（5）より，
1
b
b(N ) ˜
˜ u(m) )
H(fm,u
(Du(m) ) ≥ r¯cb(N ) (D
(m) ) ≥ rc
N
9
(9)
が成り立つ，式 (7)(8)(9) より，
∫
(m−1)N
(m)
ˆ mN
H(X
)=
(m−1)N +1 |U
b
N
H(fm,u
(u(m) )
(m) (X1 ))dµ−∞
∫
˜ u(m) )dµ(m−1)N (u(m) )
≥ N r¯cb(N ) (D
−∞
b(N )
となるが，r¯c
(·) は凸なので，イェンセンの不等式より，
∫
(m)
b(N )
ˆ mN
˜ u(m) dµ(m−1)N (u(m) ))
H(X
|U
)
≥
N
r
¯
(
D
c
−∞
(m−1)N +1
となる．さらに，
∫
˜ u(m) dµ(m−1)N (u(m) ) = ρ(f(m−1)N +1 , . . . , fmN )
D
−∞
(10)
が成り立つ（補題 3 として付録 A.3 で証明）ので
(m)
ˆ mN
H(X
) ≥ N r¯cb(N ) (ρ(f(m−1)N +1 , . . . , fmN ))
(m−1)N +1 |U
b(N )
を得る．したがって，r¯c
lim sup
K→∞
の凸性と単調減少性から，
K
K
1 ∑
1 ∑ b(N )
(i)
ˆ iN
|U
)
≥
lim
sup
H(X
r¯c (ρ(f(i−1)N +1 , . . . , fiN ))
(i−1)N +1
KN i=1
K→∞ K i=1
≥
K
∑
b(N ) 1
lim sup r¯c (
ρ(f(i−1)N +1 , . . . , fiN ))
K i=1
K→∞
≥ r¯cb(N ) (lim inf
K→∞
K
1 ∑
ρ(f(i−1)N +1 , . . . , fiN ))
K i=1
≥ r¯cb(N ) (ρ({fk }))
≥ r¯cb(N ) (D)
が成り立つ．ただし，最後の不等式で {fk } ∈ Fc (D) を用いた．また，量子化器 {fk } ∈ Fc (D)
は任意であったので，
rcL(N ) (D) ≥ r¯cb(N ) (D)
が成り立つ．
5 まとめ
無記憶な量子化器による量子化は，定常無記憶な情報源に対しては有効だが，非定常である
情報源の一例であるブロック毎に定常無記憶な情報源に対しては有効でない事が分かった．本
10
論文では，非定常独立な情報源に対して，それがブロック毎に定常無記憶である場合は，どの
ように量子化すれば最も最適な性能を達成できるかを数学的に明らかにした．まず，ブロック
(
)
˜ 及びブロック毎のエントロピー H f b (X mN
毎の平均歪み D
(m−1)N +1 ) を導き，ブロック毎に
量子化した場合の最適レートと任意の因果的な量子化器の符号化レートとの比較を行った．任
意の因果的な量子化器の符号化レートは，その情報源が与えられた平均歪み D であるときに
とり得る最も小さい値であるので，ブロック毎に量子化した場合の最適レートがこれに等しけ
れば，ブロック毎に定常独立な情報源は，ブロック毎に量子化すれば符号化レートの最小値を
b(N )
得られるという事が確認できる．その結果，rc (D) = r¯c
(D) という等式が得られた．以上
の事から，ブロック毎にタイムシェアリングで量子化すれば最適な性能を達成することが数式
的に証明出来た．今後は，ブロック毎に定常である以外の非定常な情報源について，どのよう
に量子化すれば最適な性能を達成出来るのかという課題が有るので，この分野無しにして歪
み・レート関数の研究は成し得ないであろう．
謝辞
本研究を終えるにあたり，終始一貫して丁寧なご指導を賜りました指導教員の西新幹彦准教
授に心より感謝と敬意の意を申し上げます．
参考文献
[1] D. L. Neuhoﬀ and R. K. Gilbert, ”Causal source codes,” IEEE Trans. Inf Theory, vol.
IT-28,no. 5, pp.701-713, Sep.1982
11
付録 A
補題の証明
A.1 補題 1 の証明
式 (1) から
˜ 1K )]
ρ(f b ) = lim sup E[ρK (X1K , X
K→∞
ˆ 1mN )]
≥ lim sup E[ρmN (X mN , X
m→∞
= lim sup E[
m→∞
K
1 ∑
˜ 1mN )]
ρmN (X1mN , X
mN i=1
1 ∑
iN
ˆ iN
E[ρN (X(i−1)N
+1 , X(i−1)N +1 )]
m→∞ m
i=1
[
]
ˆ 1N )
= lim sup E ρN (X1N , X
m→∞
[
]
ˆ 1N )
= E ρN (X1N , X
m
= lim sup
が成り立つ．ただし，最後から 2 番目の等号は，情報源はブロック毎に定常をあることを用い
てる．
次に逆向きの不等式を示す．本証明では
ρmax , sup ρ(x, x
ˆ)
x,ˆ
x
が実数として存在すると仮定する．さらに，任意の自然数 K に対して，mK , ⌊ K
N ⌋，rK ,
K − mK N とおけば，
K = mK N + rK , 0 ≤ rK < N
12
が成り立つ．これらを用いると，
[ (
)]
˜ 1K
ρ(f b ) = lim sup E ρK X1K , X
K→∞
[
]
mK∑
N +rK
1
ˆi)
= lim sup E
ρ(Xi , X
mK N + rK
K→∞
i=1
[
(m N
)]
K
∑
1
ˆ i ) + rK ρmax
ρ(Xi , X
≤ lim sup E
mK N + rK
K→∞
i=1
[
(m N
)]
K
∑
1
ˆ i + N ρmax )
≤ lim sup E
ρN (Xi , X
mK N + rK
K→∞
i=1
]
[
mK
∑
N
N
iN
ˆ iN
ρN (X(i−1)N
ρmax
= lim sup E
+1 , X(i−1)N +1 ) +
mK N + rK i=1
mK N + rK
K→∞
(
)
[
]
mK N
N
N ˆN
= lim sup
E ρN (X1 , X1 ) +
ρmax
mK N + rK
mK N + r K
K→∞
[
]
ˆ 1N )
= E ρN (X1N , X
を得る．ここに，K → ∞ のとき mK → ∞ であることを用いた．
A.2 補題 2 の証明
定理 1 の証明と同様の議論により，ブロック量子化器 f b の符号化レート r は
r = lim sup
K→∞
ˆ =
と表される．以下では H(X)
]
1 [
∞
ˆ
E LK (X−∞
) = H(X)
K
1
b
N
N H(f (X1 ))
を示す．
13
まず，エントロピーの定義より，
1
ˆ 1K )
H(X
K→∞ K
1
ˆ 1mN )
≥ lim sup
H(X
mN
m→∞
m
1 ∑
ˆ iN
ˆ (i−1)N
= lim sup
H(X
(i−1)N +1 |X(i−2)N +1 )
m→∞ mN
i=1
ˆ = lim sup
H(X)
= lim sup
m→∞
= lim sup
m→∞
= lim sup
m→∞
m
1 ∑
ˆ iN
H(X
(i−1)N +1 )
mN i=1
m
1 ∑
ˆ 1N )
H(X
mN i=1
1
ˆN)
H(X
1
N
1
ˆ 1N )
= H(X
N
1
= H(f b (X1N ))
N
が成り立つ．
次に逆向きの不等式を示す．本証明では
ˆ 1N ) < ∞
H(X
を仮定する．補題 1 の証明と同じく mK ，rK を定めると，
(
)
ˆ = lim sup 1 H X
ˆ 1K
H(X)
K→∞ K
(m
)
K
(
)
(
)
1 ∑
(i−1)N
r
m
N
iN
K
K
ˆ
ˆ
ˆ
ˆ
= lim sup
H X
(i−1)N +1 |X(i−2)N +1 + H XmK N +1 |X(mK −1)N +1
K→∞ K
i=1
)
(m
K
1 ∑
ˆ iN
ˆ rK
= lim sup
H(X
(i−1)N +1 ) + H(XmK N +1 )
K→∞ K
i=1
(
)
mK + 1
ˆ 1N
≤ lim sup
H X
K→∞ mK N + rK
1 ( ˆN)
= H X1
N
)
1 (
= H f b (X1N )
N
が成り立つ．
14
A.3 補題 3 の証明
b
˜ u = ρ(fm,u
ここでは，式（10）を証明する．D
) であるから，
∫
∫
(m−1)N
˜ u dµ(u) =
D
∫
=
∫
=
∫
b
ρ(fm,u
)dµ−∞
(u)
[ (
)]
EX1N ρN X1N , fm,u (X1N ) dµ(u)
EX mN
(m−1)N +1
[ (
)]
mN
mN
ρN X(m−1)N
,
f
(X
)
dµ(u)
+1 m,u
(m−1)N +1
[ (
)
]
mN
mN
(m)
ρN X(m−1)N
= u(m) dµ(u)
+1 , fm,U (X(m−1)+1 ) |U
[ (
)]
mN
= EX mN
ρN X(m−1)N
, fm,U
,U
+1
(m−1)N +1
[
]
mN
ˆ mN
= E ρN (X(m−1)N
,
X
)
+1
(m−1)N +1
=
EX mN
|U
(m−1)N +1
= ρ ({fk })
ここで，下から 3 番目の等式は
∫
∫
E[f (X, Y )|Y = y]dµ(y) =
E[f (X, y)|Y = y]dµ(y)
∫ ∑
=
f (x, y)P r{X = x|Y = y}dµ(y)
x
=
=
∑∑
y
x
y
x
∑∑
f (x, y)P r{X = x|Y = y}P r{Y = y}
f (x, y)P r{X = x|Y = y}
= E[f (X, Y )]
である事を利用した．
15

Download Report