ユニバーサルな誤り訂正符号の構成法に関する研究

1977年にI.Csiszar、J.KornerおよびK.Martonは、通信路特性を予め知ることなく符号化・復号化が行なえ、かつ符号長を長くしたときの復号誤り率が、その通信路における最適な符号と同程度であるような「ユニバーサル(万能)符号」の存在を示した。しかしながら、その具体的な構成法は現在まで未知のままであった。本研究では、無記憶通信路に対して、復号誤り率がForneyの限界式を達成するようなユニバーサル符号の実用的な計算量での構成法を開発することを目的とし、以下に述べるような成果を得た。1.無記憶通信路の中で最も取り扱いが容易であると考えられる加法的通信路について、代数幾何符号を外部符号として用い、内部符号を可変とした連接符号によって構成される符号を提案し、内部符号をそれぞれ最大相互情報量復号法および一般化最小距離復号法によって復号したとき、誤り率特性がForneyの限界式に漸近することを明らかにした。2.一般の無記憶通信路について所望の性能を有する符号の構成法として、可変内部符号によって得られた符号語を同一のタイプを有する系列に写像する方法を提案した。但し、系列のタイプとは、系列中における各シンボルの相対頻度を表す。そして、この符号に対して前述の復号法を適用した場合、一般の通信路に対してもForneyの限界式を満たすことを明らかにした。尚、これら提案した符号の構成・符号化・復号化は全て符号長の多項式オーダで行える。

1977年にI.Csiszar、J.KornerおよびK.Martonは、通信路特性を予め知ることなく符号化・復号化が行なえ、かつ符号長を長くしたときの復号誤り率が、その通信路における最適な符号と同程度であるような「ユニバーサル(万能)符号」の存在を示した。しかしながら、その具体的な構成法は現在まで未知のままであった。本研究では、無記憶通信路に対して、復号誤り率がForneyの限界式を達成するようなユニバーサル符号の実用的な計算量での構成法を開発することを目的とし、以下に述べるような成果を得た。1.無記憶通信路の中で最も取り扱いが容易であると考えられる加法的通信路について、代数幾何符号を外部符号として用い、内部符号を可変とした連接符号によって構成される符号を提案し、内部符号をそれぞれ最大相互情報量復号法および一般化最小距離復号法によって復号したとき、誤り率特性がForneyの限界式に漸近することを明らかにした。2.一般の無記憶通信路について所望の性能を有する符号の構成法として、可変内部符号によって得られた符号語を同一のタイプを有する系列に写像する方法を提案した。但し、系列のタイプとは、系列中における各シンボルの相対頻度を表す。そして、この符号に対して前述の復号法を適用した場合、一般の通信路に対してもForneyの限界式を満たすことを明らかにした。尚、これら提案した符号の構成・符号化・復号化は全て符号長の多項式オーダで行える。