1 まえがき

1990年代の通信路符号におけるターボ符号の発明[1],LDPC符号の再発見[2]以来シャノン限界に迫る符号化性能と実時間による実行とを両立させる符号を構成することは情報理論の主要なテーマの1つとなっている.

LDPC符号は通信路符号化のみならず無歪みおよび有歪み情報源符号化への適用に関しても研究がなされてきた.情報源をPUとしたとき,無歪み情報源符号化の場合,圧縮レートがブロック長が長くなるにつれてエントロピー限界H(U)=ΣaPU(a)log1/PU(a)に近づくときを,また,有歪み情報源符号化の場合,情報源からのメッセージと復号器で復号されたメッセージとの違いの許容度を表す数をDとした際に圧縮レートがブロック長が長くなるにつれてレート・歪み関数R(D)=minPV|U:Σa,bPUVd(a,b)≦DI(U;V)に近づくときを,それぞれの符号は漸近最良性を持つという.一方,通信路符号の場合は通信路をWY|Xとしたとき,復号誤り確率がブロック長が長くなるに従って0に近づく際の伝送レートが通信路容量C(WY|X)=maxPxI(X;Y)に近づくとき,その符号は漸近最良性を持つという。ただし,H(U),I(U;V)はそれぞれ確率変数Uのエントロピー,確率変数UおよびVに関する相互情報量と呼ばれる量である.

MillerとBurshtein[5]はLDPC行列で構成された通信路符号の漸近最良性を,MatsunagaとYamamoto[4]は有歪み情報源符号の漸近最良性をそれぞれ示した.また,MartinianとWainwright[3]は多端子系であるWyner-Ziv系とGel'fand-Pinsker系に関して符号を構成し,その漸近最良性を示した.―方で,漸近最良性が示された系は情報源が一様分布であることとか,通信路雑音は付加雑音であることなど,系の統計的な性質に対してある種の対称性が仮定されていた.もし現実的な系に対して漸近最良性を満足する符号を構成する必要が生じた場合,このような仮定は大きな制限となってくる.

本論文は,疎行列を用いて一般の定常無記憶情報源や通信路の符号を構成しその漸近最良性を示す.まず,疎行列の構成法を示し,次いで疎行列で構成されたユニバーサル符号に関して誤り指数を与える.次に有歪み符号を構成し漸近最良性を示し,シミュレーションでその性質を確認する.最後に通信路符号を構成し漸近最良性を示した後で,有歪み情報源符号と組み合わせることで情報源・通信路結合系の符号を構成する.このとき疎行列で構成された符号は,通常のブロック符号で構成された符号よりも少ない最適化の実行回数で実現できることが示される.

分散ビデオ符号化からステガノグラフィまで,多くの応用が見込まれる多端子系は有歪み情報源符号化と通信路符号化との組み合わせで構成されることが多いため,疎行列符号の多端子系への適用も期待される.本論文は,その基礎的部分の検討を行ったものである.

2 疎行列の構成

考察する対象は2端子通信系における符号化,復号化である.符号はアルファベット[O:q-1]上で行う.ここで,qは素数とする.アルファベットに関しては行列操作が行われるため集合[O:q-1]には体としての構造が与えられているものと仮定する.従って,以後アルファベットを[O:g-1]と記す代わりに適宜GF(q)記法も用いる.また,特に注意しない場合はlogの底はqとする.

疎行列とは非ゼロの要素数が0の要素数に比べて小さいものをいう.ここで取り扱う疎行列の構成を次に示す.

[n×k疎行列Aの構成]tをO(logn)の偶数の値をとる疎行列パラメータとする.

Step1:Aの全ての要素を0とする.

各行において次のStep2で示す操作を行う.

Step2:数α∈[1:k]および数b∈[1:q-1]を一様ランダムに取り出す.次に数bをa列にある数字に加える.この際の加法はqを法とする.以上の操作をt回繰り返して行い,次の行に移る.

3 無歪みユニバーサル符号

3.1問題設定と主定理

図1に示す系を考察する.PUは集合GF(q)上の確率分布で,i.i.d.すなわち.PUn[Un=un]IIni=1 Pu[Ui;ui]が成り立つと仮定する.符号器ψn:GF(q)n→GF(q)kは情報源から出力されたメッセージ系列un∈CF(q)nを符号語mk∈GF(q)kに圧縮する.このとき,圧縮レートRをR=k/nとして定義する.また,復号器ψn:GF(q)k→GF(q)nは符号語mkから元のメッセージ系列を推定し,un∈CF(q)nを出力する。

なお,ここで注意すべきことは符号器ψnおよび復号器ψnは情報源の確率分布PUの情報を知らないということである.我々は,この様な条件の下で疎行列を用いて符号器ψn,復号器ψnを構成し,漸近的に復号誤りが0に収束する場合の収束速度を評価する.

まず,情報源PUの属する確率分布族の集合P(T)をP(T)def={P∈{GF(q)上のi.i.d.確率分布}|min a∈[O:q-1]P(a)>T}とする.ただし,Tは正の定数次にn×k疎行列Aを用いて符号器をψn(un)def=unA,復号器をψn(mk)def=argminun:unA=mkH(Pun)として構成する.ここで,Punはunのタイプ(各文字の頻度分布)である.符号器および復号器はTを用いていないことに注意する.このとき,圧縮レートRが予め与えられている際に,任意のP∈P(T)に対して復号誤りΣunP(un)1[un≠ψn(ψn(un))]は次のように評価される.

定理1 P(T)の部分集合Pη(T)(0<η<1)をPn(T)def={P∈P(T)|H(P)<η}のように定義する.このとき,誤り指数〓が任意のP∈P(T)について成り立つような符号器ψn復号器ψnを構成する疎行列Aは高い確率で存在する.

シミュレーション実験の結果については紙面の都合上省略する.

4 有歪み情報源符号

4.1問題設定と主定理

図2に示す系を考察する.情報源PUはi.i.d、で,情報源からの出力をunとする.歪み測度dn:CF(q)n×GF(q)n→R+および定数D≧0が与えられた際に,復号器の出力を併とすると,dn(un,un)/n≦Dを満足するような符号器ψn=GF(q)n→GF(q)kおよび復号器ψn:CF(q)k→GF(q)nを疎行列を用いて構成したい.このとき次の定理が成り立つ.

定理2 条件付き確率分布PV|Uを予め与えて固定しておく.十分大きい数n,l,およびkに対してl+k/n>H(V)+δ1/3およびl/n<H(V|U)-δを満足する正数δが存在するならばn×l疎行列Aおよびn×k疎行列Bを用いて〓を満足する符号器ψnおよび復号器ψnが構成できる.

上の定理で存在が示された符号器ψnおよび復号器ψnは次のように構成される.

[符号器の構成]符号器はベクトル量子化部および圧縮部よりなる.

ベクトル量子化部:情報源からの出力unが与えられたとき,vudef=arg maxvn:vnA=clPVn|Un(vu|un)で定義されるvnを出力する.ここで,cl∈GF(q)lは固定された非ゼロの行ベクトルである.

圧縮部:vnは圧縮部でmkdef=vnBのように圧縮・符号化される.

[復号器の構成]符号語mk∈aF(q)kが与えられたとき,undef=argmaxvu:vnA=clvnB-mkPVn(vn)で定義されるベクトル量子化vnの推定語unを出力する.

定理の条件l+k/n>H(V)+δ1/3およびl/n<H(VlU)-δが十分に小さい数δに対して成り立っているとする,このとき,l+k/n=H(V)+2δ1/3およびl/n=H(V|U)-2δとすると,圧縮レートk/nはI(U;V)+2(δ+δ1/3)となる.もし,I(U;V)がレート・歪券関数R(D)に等しいならば,ここで構成した符号は漸近最良性を持つことがいえる.

シミュレーション実験の結果については紙面の都合上省略する.

5 通信路符号

5.1問題設定と主定理

図3に示す系を考察する.通信路WY|Xは無記憶定常すなわち,WYn|Xn(yn|xn)=Пni=1WY|X(yi|Xi)と仮定する.このとき,復号誤りを漸近的にいくらでも小さくするような符号器ψn:GF(q)k→GF(q)nおよび復号器ψn:GF(q)n→GF(q)kを疎行列を用いて構成したい.このとき次の定理が成り立つ.

定理3確率分布Pxを固定しておく.十分大きい数n,l,およびkに対してl+k/n<H(X)-δおよびl/n>H(X|Y)+δ1/3を満足する正数δが存在するならば,n×l疎行列Aおよびn×k疎行列Bを用いて〓を満足する符号器ψnおよび復号器ψnが構成できる.

上の定理で存在が示された符号器ψnおよび復号器ψnは次のように構成される.

[符号器の構成]送りたいメッセージmk∈GF(q)kが与えられたとき,符号語はψn(mk)def=argmaxxn:xnA=clxnB-mkPXn(xn)で定義される.

[復号器の構成]復号器は推定部と復元部よりなる.

推定部:符号語の推定xndef=argmaxxn:xnA=clPXn|Yn(xn|yn)を出力する.

復元部:送られたメッセージの推定量mkdef=xnBを出力する.

定理の条件l+k/n<H(X)-δおよびl/n>H(X|Y)+δ1/3が十分に小さい数δに対して成り立っているとする.このとき,l+k/n=H(X)-2δおよびl/n=H(X|Y)+2δ1/3,とすると,伝送レートk/nは1(X;Y)-2(δ+δ1/3)となる.もしI(X;Y)が通信路容量C(WY|X)に等しいならば,ここで構成した符号は漸近最良性を持つことがいえる.

5.2情報源・通信路結合符号化

定理2と定理3とを組み合わせることによって疎行列符号化ならではの興味深い結果が導出される.ここで,図4に示す情報源・通信路結合符号化系を考察する.

系1[情報源・通信路結合線形符号化]情報源PU,条件付き確率分布PV|U,および適信路WY|Xが与えられ,H(V|Y)<H(V|U)が成り立っと仮定する.(このとき確率変数XとVとを同一視した.)十分大きい数nおよびlに対してH(V|Y)+δ1/3<l/n<H(V|U)-δを満足する正数δが存在するならば,n×l疎行列Aを用いて〓を満足する符号器ψn(JL)および復号器ψn(JL)が構成できる.

上記の系で述べていることは,ある条件の下,ベクトル量子化器の出力をそのまま通信路符号とすればよいということである.これによって,与えられた歪み基準と通信路に対して従来に比較して単純な符号が疎行列を用いて構成できることがわかる.

6 まとめ

疎行列を用いて,無歪みユニバーサル符号,有歪み情報源符号および通信路符号を構成し,無歪みユニバーサル符号に関しては復号誤り指数を求め,また,有歪み情報源符号および通信路符号に関しては,構成した符号が漸近最良性を持つことを示した.疎行列を用いて符号を構成することによって,sum-product法や線形計画法など効率的なアルゴリズムで近似的に実現できることが期待される.

図1: 無歪み情報源符号化系

図2: 有歪み情報源符号化系

図3: 通信路符号化系

図4: 情報源・通信路結合符号化系

本論文は、「Coding Theorems for Point-to-Point Communication Systems using Sparse Matrix Codes (疎行列を用いた2端子通信系における符号化定理)」と題し、6章から構成されている。データ系列の冗長性を取り除き、より小さいサイズに圧縮する情報源符号における符号化効率の限界は、無ひずみ圧縮の場合はエントロピー関数で与えられ、有歪み圧縮ではレート歪み関数で与えられる。また、通信路で生じた誤りを訂正可能にする通信路符号では、符号化効率の限界は通信路容量で与えられる。これらの限界は、ランダム符号化手法を用いて達成可能なことが証明されているが、最近、実用的な時間で符号化・復号化が可能な疎行列を利用した符号で,その限界の達成を目指す研究が盛んに行なわれている。本論文では、一般の定常無記憶情報源や通信路に対して、そのような疎行列を用いた符号の構成法を提案し、その符号構成法で符号化効率の限界を達成できるという漸近最良性を、理論的に証明している。

第1章「Introduction」では、取り扱う通信システムモデルを紹介すると共に、本研究の目的および従来研究に対する本研究の位置付けを述べている。

第2章「Preliminaries for Sparse Matrix Coding」では、疎行列の構成方法、疎行列とランダムウォークとの関係を述べると共に、ランダムウォークに関して成り立つ幾つかの補助定理を与えている。さらに、系列のタイプに関する基本的な補助定理を示している。

第3章「Lossless Universal Source Coding」では、無ひずみ情報源符号化問題を取り扱っている。疎行列を用いて固定長のユニバーサル符号化を行なった場合、任意の定常無記憶情報源に対して、与えられた符号化レートにおける誤り指数を理論的に導出している。また、2値定常無記憶情報源の場合に対して、sum-product復号を行なった場合をシミュレーションし、理論との比較を行なっている。

第4章「Lossy Source Coding」では、有ひずみ情報源符号化に対して、二つの疎行列を用いた符号化法を提案している。一つ目の疎行列でベクトル量子化を行い、二つ目の疎行列でベクトル量子化後のデータを無ひずみ圧縮する符号構成となっている。本章では、この提案した符号で、漸近的な圧縮限界であるレートひずみ関数を達成できることを証明している。また、非漸近的な場合に対して、LCLP (Linear Code Linear Programming)復号法を改良した復号法を提案し、シミュレーションにより、時分割限界よりよい性能を達成できることを示している。

第5章「Channel Coding」では、4章で有ひずみ情報源符号化用に提案した符号の双対な符号が、通信路符号化に利用できることを示している。そして、その符号を用いることにより、通信路符号における符号化効率の限界である通信路容量を、漸近的に達成できることを理論的に証明している。さらに、第5章では、第4章の有ひずみ情報源符号化と通信路符号化を一度に行なう「情報源・通信路同時符号化」を取り扱っている。情報源符号化と通信路符号化を個別に行なって接続する場合は、それぞれで2個の疎行列が必要となり、符号化・復号化の処理も二度必要になる。しかし、互いに双対な符号を用いて同時符号化を行なうと、ある条件を満たす場合は、情報源符号化で用いる疎行列と通信路符号化で用いる疎行列の働きが互いに打ち消し合うことになり、一つの疎行列だけで、情報源符号化と通信路符号化の同時符号化が可能なことを証明している。

第6章「Conclusion and Future Works」では、本論文の成果をまとめると共に、今後の研究課題を示している。

なお、本論文第3章は丸山充との共同研究、第4.2節第4.3節および第5章は村松純との共同研究、第4.4節は本多淳也および山本博資との共同研究であるが、これら全てにおいて、論文提出者が主体となって符号化問題の設定、符号化定理の証明、シミュレーションを行なったものであり、論文提出者の寄与が十分であると判断する。

したがって、博士(科学)の学位を授与できると認める。