情報理論における最も基本的な問題として,ノイズを含む通信路を通して正しく情報を伝送する通信路符号化と,与えられたデータをより短いデータ系列に変換する情報源符号化がある.また,情報源符号化はデータの損失が許されるかどうかで無歪み符号化(無歪み圧縮)と有歪み符号化(有歪み圧縮)に分類される.ここで無歪み圧縮については理論限界を達成可能かつ高速な符号化方式が早くから知られていたが,通信路符号化および有歪み圧縮において理論限界に近い性能をもつ実用的な符号化方式の構成は現在においても重要な研究課題となっている.

本論文ではこれら通信路符号化および有歪み圧縮について考える.これらの問題においては,対称モデル,すなわち対称通信路の符号化および一様情報源の対称な歪み基準における符号化については多くの研究がなされており,polar符号やLDPC符号といった線形符号により有限の符号長で理論限界に近い性能を達成できることが知られている.一方,現実に用いられる通信路や情報源は必ずしも対称とは限らないが,非対称モデルに対する研究はそれほど多くない.対称でない通信路や情報源の符号化においては,理論限界を達成するために符号語の各シンボルが従うべき理想的な頻度分布が一様分布とならない.一般に線形符号においては各シンボルが一様に出現するため,非対称モデルに対して素朴に線形符号を適用した場合には理論限界を達成することができない.このような非対称モデルの符号化を線形符号の枠組みで行う方式としてはGallagerの多元符号を用いる方法が主に知られているが,これは理論限界を漸近的には達成可能であるものの,現実的には計算量等の問題からあまり実用的ではない.

そこで本論文では非対称モデルにおける通信路符号化と有歪み圧縮について,polar符号またはLDPC符号を用いた新たな符号化方式を提案し,理論限界を漸近的に達成可能であることを示した.提案方式では一様でない符号語を生成する際に,Gallagerの方法のかわりに無歪み圧縮を応用した方法を用いる.これは,無歪み圧縮が一様でない生起確率をもつ系列を一様な系列へと変換する操作だとみなせることから無歪み圧縮の逆操作を用いれば一様でない符号語を生成できるはずというアイディアに基づく.同じアイディアを用いた符号はMiyake-Muramatsuによって提案されているが,彼らの方法がNP完全問題の厳密計算を前提としているのに対し,提案方式では有限の符号長で理論限界に近い性能を現実的な計算量で達成できる.

まず,第2章では通信路符号化および有歪み圧縮の理論限界を示すとともに,非対称モデルの符号化問題を対称モデルの符号化に帰着させる従来手法としてGallagerの方法を紹介した.また,無歪み圧縮において知られている効率的な符号化法についても併せて紹介した.

第3章ではpolar符号を用いた通信路符号と有歪み符号の提案を行った.Polar符号は通信路分極とよばれる現象を用いた符号化方式として2008年にArikanによって提案された.これは多項式時間で2値対称通信路の通信路容量を漸近的に達成できることが理論的に示された最初の符号として近年盛んに研究がなされており,その漸近最適性は後に一般の通信路の符号化および有歪み圧縮に対しても拡張されている.ここで非対称モデルにおける通信路符号化および有歪み圧縮についてはGallagerの方法により最適性が示されているが,これは大きなアルファベットサイズの多元polar符号を必要とするために,計算量が非常に大きくなる問題があった.そこで本論文ではpolar符号による無歪み圧縮を応用した符号化方式を新たに提案し,その漸近最適性を示した.

Polar符号による無歪み圧縮では,一様でない頻度分布をもつnビット情報源系列X = (X1, X2,..., Xn ) をpolar符号の生成行列G によってU = G Xと可逆変換する.ここで生成行列G の構造から,変換後の系列U = (U1, U2,..., Un ) の各シンボルUi は (A) 以前のビットU1,..., Ui -1を見ればUi の情報が復元できる,(B) 以前のビットU1,..., Ui -1 を見たうえでもUi は一様ランダムである(すなわちUi の情報は全く分からない),という2パターンのみに分かれることが示される.したがって,グループ (B) に属するビットについてのみ情報を送信すればU 全体が復元でき,そこからG の逆変換によりX が復元できる.すなわち,グループ (A) に属するビットの数だけ系列を圧縮できることになる.

本論文ではこのpolar符号による無歪み圧縮を用いて通信路符号を構成した.提案手法においては,一様系列をグループ (B) に属するビットに割り当てることにより系列U を生成する.Polar符号の性質から,グループ (A) に属するビットの値を適切に決めることにより,理想的なシンボル分布をもつ符号語X = U G -1を構成できる.ここで通信路符号化において通信路入力X に対する出力Y を考えた場合,グループ (B) に属するビットUi はさらに (B1) 以前のビットU1,..., Ui -1 を見たうえでもUi は一様ランダムだが,通信路出力Y を併せて見ればUi の情報を復元できる,(B2) 以前のビットU1,..., Ui -1 と通信路出力Y を見たうえでもUi は一様ランダム,という2パターンに分極する.ここでグループ (B1) に属するビットに一様なメッセージを割り当てることにより,入力系列X の理想的な頻度分布を崩さず,かつ通信路出力からメッセージが復元することが可能な通信路符号を構成できることを本論文では示した.また,有歪み圧縮の場合にも通信路符号の符号化と復号を入れ替えることにより漸近最適な符号を構成することができることを併せて示した.

第4章では low density parity check (LDPC) 符号を用いた通信路符号と有歪み符号の提案を行った.LDPC符号は疎なパリティ検査行列を用いて定義される線形符号であり,belief propagation (BP) と呼ばれる復号法により符号長に対して線形時間で理論限界に近い性能を達成できることが実験的に知られている.

LDPC符号が通信路容量を達成可能であることは理論的にも証明がなされ,またその最適性は有歪み圧縮にも拡張されている.ただし,LDPC符号の最適性においてはNP完全な復号問題を解くことを仮定しており,多項式時間で最適性を保証できるような復号アルゴリズムは一般には知られていない.ここで対称通信路についてはBP復号を用いることによりpolar符号に比べて実験的に良い性能を達成できることが知られているが,非対称モデルの場合にはGallagerの方法とMiyake-Muramatsuの方法いずれを用いた場合でも多項式時間アルゴリズムの性能が著しく悪化する問題があった.

そこで本論文では無歪み圧縮を用いるアイディアをMiyake-Muramatsuとは異なる形で適用した符号化方式を提案した.Miyake-Muramatsuの方式はLDPC符号による固定長符号を無歪み圧縮に用いるものであるが,固定長無歪み圧縮は有限の符号長では元の系列を正しく復号できない場合があり,さらにNP完全な復号問題を厳密に解く必要がある.そこで提案手法では可変長符号である算術符号またはhomophonic符号を無歪み圧縮に用いる.これらの可変長符号の適用にあたっては符号語中の各シンボルの生起確率を計算する必要があるが,これはBPを用いることで効率的に計算できる.さらに,計算した確率が近似値であった場合も可変長符号では符号化率がわずかに悪化するのみで,即座に復号失敗とはならないため近似アルゴリズムとの相性が良い.まず第4章では,符号化・復号における計算が厳密にできた場合に理論限界を達成可能であることを証明した.

次に第5章では,第4章で提案したLDPC符号による通信路符号および有歪み符号に対する実用的なアルゴリズムの提案を行い,シミュレーションによりそれらの性能を確認した.提案方式における通信路符号の復号および有歪み符号の符号化における主要な計算は,与えられた系列に対して事後確率が最大となる符号語を求める符号語推定問題と,符号語の各シンボルの周辺確率の計算の2つからなる.まず5.2節ではBPを用いて周辺確率の近似計算を行う効率的なアルゴリズムの提案を行い,厳密計算を行った場合とほぼ同等の符号化率が達成できることを確認した.次に5.3節と5.4節では符号語推定の問題に対する近似アルゴリズムの提案を行った.この問題は通信路符号化と有歪み圧縮で共通の形の最適化問題となるが,近似アルゴリズムに求められる性質は両者で大きく異なる.まず5.3節では有歪み圧縮における符号語推定の問題に対してBPの改良版であるRBP (Reinforced Belief Propagation) とマトロイド最適化を組み合わせたアルゴリズムを提案した.次に5.4節では通信路符号化における符号語推定の問題を線形計画法を用いて解く手法 (LP復号) を紹介し,また多元LDPC符号に対してLP復号を高速に行う手法を新たに提案した.

最後に第6章では本論文の成果を総括し,またGallagerの方法と無歪み圧縮による方法の誤り指数の比較といった問題を今後の課題として述べた.

本論文は,「Efficient Polar and LDPC Coding for Asymmetric Channels and Sources (非対称な通信路と情報源の効率的なpolar符号化およびLDPC符号化)」と題し、6章から構成されている。情報を高品質で速く伝送するために、誤り訂正を行う通信路符号化およびデータ圧縮を行う情報源符号化が重要となる。情報源符号化は、元のデータを誤りなく復号できる無ひずみ圧縮と、復号データに歪みを許してさらに圧縮率を上げる有歪み圧縮があるが、有歪み情報源符号化は通信路符号化と双対な関係がある。近年、通信路符号化や有歪み情報源符号化の符号化レートの理論限界を漸近的に達成し、かつ実用的にもよい性能を達成できる符号として、polar符号およびLDPC(低密度パリティ検査)符号が注目を集めているが、それらは主に対称モデル(通信路の確率遷移行列が対称、あるいは情報源が一様分布で歪み測度関数が対称なモデル)が取り扱われていた。これに対して、本論文では、一般の非対称なモデルに対する、polar符号およびLDPC符号の効率のよい符号化法を提案し、それらの符号化法で漸近的に理論限界を達成できることを示すと共に、実用的にもよい性能を達成できる符号化/復号化アルゴリズムを与えている。

第1章「Introduction」では、研究の背景を述べると共に、本研究の目的および従来研究に対する本論文の位置付けを述べている。

第2章「Preliminaries: Coding Theorems」では、通信路符号化と歪みを許す情報源符号化に対する符号化レートの理論限界を与える符号化定理を紹介すると共に、本論文で利用する算術符号やインターバルアルゴリズムを用いたHomophonic符号化法を紹介している。

第3章「Polar Codes for Asymmetric Channels and Sources」では、非対称モデルに対するpolar符号を取り扱っている。まず、polar符号の非一様確率変数に対する偏極特性を明らかにし、その特性に基づいて、非対称モデルに対する新しい通信路符号化法および有歪み情報源符号化法を提案している。次に、それらの方式で理論限界である通信路容量およびレート歪み関数を達成できることを数学的に証明し、さらに、数値実験結果により、実用的にもよい性能を達成できることを明らかにしている。

第4章「LDPC Codes for Asymmetric Channels and Sources」では、非対称モデルに対するLDPC符号を取り扱っている。非対称モデルに対する有歪み情報源符号化は、ベクトル量子化と無歪み情報源符号化を縦続に行い、その各々にLDPC符号を用いることで理論限界が達成できることが知られている。しかし、無ひずみ圧縮にLDPC符号を用いているため、実用的には性能がかなり悪い欠点があった。これに対し、本論文では、無歪み情報源符号化を可変長の算術符号を用いて行う方式を提案している。さら通信路符号化が有歪み情報源符号化と双対性があることを利用して、上記の方式を通信路化に適用する方式を提案している。具体的には、符号器では、LDPC符号とインターバルアルゴリズムを用いたHomophonic符号を組み合わせて符号化を行い、復号では、LDPC符号の符号語推定とHomophonic符号の復号を縦続に実行する手法を提案している。さらに、これらの符号化法で、理論源限界である通信路容量とレート歪み関数を漸近的に達成できることを数学的に証明している。

第5章「Practical Algorithms for LDPC Codes」では、第4章で提案したLDPC符号を用いた通信路符号の復号化および有歪み情報源符号の符号化を実用的に性能よく行えるアルゴリズムを提案している。具体的には、まず、Belief Propagationを用いて周辺確率の近似計算を行う効率的なアルゴリズムを与え、厳密計算を行った場合とほぼ同等の性能が達成できることを示している。また、有歪み情報源符号化のベクトル量子化部を効率よく実行するために、Belief Propagationの改良版であるReinforced Belief Propagationとマトロイド最適化を組み合わせたアルゴリズムを提案している。さらに、通信路符号化の符号語推定問題を効率よく実行するために、線形計画法を用いて復号する従来手法を多元LDPC符号に拡張し、線形計画法復号を高速に行う手法を与えている。最後に、これらの提案手法が従来の手法より性能がよいことを、数値実験により確認している。

第6章「Conclusion」では、本研究の結果と貢献をまとめている。

なお、本論文の第3章, 第4章, 第5章の成果は、山本博資との共同研究であるが、論文提出者が主体となって新しい符号化法の提案、理論解析、数値実験を行った者であり、論文提出者の寄与が十分であると判断する。

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