近年、各種デジタル通信・記録システムが急速な勢いで普及しており、情報を伝達・蓄積する際に雑音等によって生じるエラーから情報を保護する技術の重要性が増している。誤り訂正符号化技術はこのためのキーテクノロジーの一つとして広く知られている。符号理論は、経済的、かつ信頼性の高いシステムの構築を目的とした誤り訂正符号化、及びその復号方式に関する理論であり、その歴史は1948年のShannonによる通信路符号化定理の発見、あるいは1950年のHammingによるHamming符号の発明にはじまるとされている。以来、理論・実用の両面から多くの研究がなされている。

　符号理論では、通常、システムの信頼性を表す指標として受信情報が正しく復号されない確率(復号誤り率)を採用し,経済性を表す指標として通信路コスト(符号化率)、及び符号化・復号のコスト(計算量)を採用する。一般に信頼性(復号誤り率)と経済性(特に復号の計算量)はトレードオフの関係にあり、このトレードオフ関係は符号理論における最重要研究課題の一つである。

　誤り訂正符号の復号法は、硬判定復号と軟判定復号に大別される。前者の硬判定復号では、通信路(復調器)の出力系列に対し、各成分毎独立に送信情報を推定して得られた系列(硬判定系列)のみに基づいて送信情報系列を推定する。このように通信路の出力系列を一旦硬判定系列に変換することにより、一般に復号処理は簡易化されるが、この硬判定系列への変換に伴う情報の損失を免れない。これに対し、通信路出力が持つ情報をなるべく損なうこと無く復号過程に利用しようとするのが後者の軟判定復号である。Hamming符号の発明以来、符号理論において最も研究成果が蓄積されたものの一つにBCH符号に代表される代数的(及び代数幾何的)符号構成法とその硬判定復号(限界距離復号)法に関する理論、所謂代数的符号理論があり、符号理論における他の研究領域と比較してその完成度は極めて高い。一方、代数的符号への軟判定復号の適用に関しては前述のトレードオフ関係に直結する重要な研究課題であるにもかかわらず研究が十分に進んでいるとは言い難い。

　本研究は、理論・実用の両面において特に重要な代数的符号のクラスについて経済的かつ効率的な軟判定復号アルゴリズムを提供することを目的とし、Berlekamp,Chase,Forneyらの先駆的研究に基づいて幾つかの軟判定復号方式とアルゴリズムを提案する。提案する一連の軟判定復号アルゴリズムは、復号器の出力となる候補符号語を逐次生成する繰り返し形軟判定復号であり、いずれも本研究で得られた基本アルゴリズムを繰り返し用いることにより構成されているという点で共通点がある。各軟判定復号アルゴリズムの基本的な構造はほぼ同一であるという特長を有している。本学位論文は以下に示すように全部で七つの章と一つの付録からなる。

　第1章では、符号理論における中心的な研究課題の一つである復号問題について触れ、硬判定復号と軟判定復号の違い、最適(最尤)復号、及び準最適復号の基本戦略等について述べる。

　第2章では、本論文で扱う軟判定復号器を構成する上で基礎となるアルゴリズムを提案する。まず軟判定復号において核となる処理が四つのタイプに分類できることを示す。次いで、各タイプの処理についてそれを実行する効率的なアルゴリズムを構成する。ここで構成する四つのアルゴリズム(I〜IV)の内、アルゴリズムIは、本論文の付録で示されるように、ある種の多重系列を生成するシフトレジスタ合成問題を解くためのアルゴリズムに一致し、第3章で扱う一般化最小距離(GMD)復号、及び第5章で提案する復号方式に応用される。アルゴリズムIIは、アルゴリズムIの入出力関係を反転させたものであり、Iと組み合わせて第6章で扱うChase復号に応用される。また、アルゴリズムIIIはBerlekamp-Masseyアルゴリズムと本質的に同等であり、IVはIIIの入出力関係を反転させたものである。さらに本章では、これら四つのアルゴリズムを統一的に記述することが可能であることを示す。

　第3章では、代数的符号に関する効率的なGMD復号アルゴリズム(one-pass GMD decoding algorithm)を提案する。一般に、GMD復号では限界距離復号アルゴリズムを繰り返し適用することによって復号器出力の候補符号語集合を算出するため、限界距離復号アルゴリズムの計算量のd倍(dは符号の設計距離)のオーダーの計算量を必要とする。ここで提案するGMD復号アルゴリズムの計算量のオーダーは、限界距離復号の計算量のオーダーに一致する。即ち、GMD復号に要する計算量のオーダーを1/dに減らすことができる。尚、GMD復号アルゴリズム高速化については、アプローチの仕方は異なるものの、他の研究者によっても類似の結果が報告されている。計算量の削減は次の理由による。従来のGMD復号アルゴリズムにおいて、第k回目の限界距離復号結果と第k+1回目限界距離復号結果の相関に注目し、それを用いることで、k回目の結果から、(限界距離復号を実行するよりも遥かに少ない手順で)直接k+1回目の結果を算出することが可能となる。このアイディアは、Chase復号にも適用することができ、それによって効率的なChase復号アルゴリズムを構成できることが第6章で示される。

　第4章では、GMD復号で得られた候補符号語集合の中で最も尤度の高い符号語が、すべての符号語の中で最も尤度の高い最尤の符号語となるための十分条件について検討する。このような十分条件として、Taipale-Pursley(TP)基準が知られている。これに対し、本章では新たな十分条件を導入する。これは一般にTP基準よりも緩く、より必要十分に近い条件であることが示される。また、その判定が極めて単純な手続きによって簡単に実行できることも特長の一つである。

　第5章では、計算量を大幅に増やすことなく、GMD復号の復号誤り率特性を改善し、より最尤復号の特性に近づける方法について検討する。具体的には、第3章で構成したGMD復号アルゴリズムに基づいて、より多くの候補符号語を効率的に算出する方法を提案する。さらに本章では、計算機シミュレーションによって誤り率特性を評価することで提案アルゴリズムの効果を示す。

　第6章では、効率的なChase復号アルゴリズム(one-pass Chase decoding algorithm)、及びそれに基づいた最尤復号アルゴリズムを提案する。GMD復号の場合と同様、計算量のオーダーは従来比1/dとなる。ここで提案するアルゴリズムは第2章のアルゴリズムI,IIを組み合わせて得られる。また最尤復号に関しては、候補符号語が最尤であるための十分条件の導入が最近多くの研究者によって検討されており、これによって最尤復号の平均計算量が低減されることが計算機シミュレーション等によって確認されている。本章では、Kanekoらの結果に基づいてこの最尤性判定条件についても検討する。

　第7章では、本論文の結果をまとめる。また、付録では第2章のアルゴリズム1とある種の多重系列を生成するシフトレジスタ合成問題との関連を明らかにする。

　本文は、「Algebraic Soft-Decision Decoding of a Class of Linear Block Codes(代数的手法に基づく誤り訂正符号の軟判定復号方式に関する研究)」と題し、信頼性の高いデジタル通信・記憶システムの構築を目的とした誤り訂正符号の軟判定復号技術に関する研究をまとめたものであって、全7章からなり、英文で記述されている。軟判定復号技術は、雑音のある伝送路を用いてデジタル情報を伝送する系において、雑音の加わった受信信号から送信情報を推定する際に、その推定値の確からしさに関する情報も同時に取り出し、これを利用することによって誤り率の改善を図る技術であるが、一方で誤り訂正に要する計算量の増加を伴う。本論文では、理論・実用の両面において特に重要な誤り訂正符号のクラスについて、軟判定復号器設計の基礎理論を構築し、それに基づいていくつかのタイプの経済的かつ効率的な軟判定復号アルゴリズムを提案している。

　第1章は「Introduction」であって、誤り訂正符号化技術の中心的な研究課題の一つである復号問題、統計的に最適な軟判定復号である最尤復号法、また本論文で主に研究対象としている準最適軟判定復号法について述べるとともに、本研究の目的、本論文の構成を示している。

　第2章は「Fundamental Algorithms」と題し、代数的手法に基づいた誤り訂正符号の軟判定復号問題が、ある一連の代数方程式を解く問題に帰着されることを示すとともに、これを解くための効率的なアルゴリズムをBerlekamp-Masseyの理論を拡張することにより与えている。また、ここで提案されているアルゴリズムは誤り訂正符号の復号問題に関連して従来から独立に提案されてきた多くのアルゴリズムをその特殊な場合として含む一般的なものであることが示されている。さらに、本論文の付録において、ここでのアルゴリズムが多重系列を生成するシフトレジスタ合成問題の解法に応用できることを示している。第2章の結果は、復号アルゴリズム設計の基礎理論を与えており、以下の章では、この結果に基づいて様々なタイプの軟判定復号アルゴリズムを統一的・具体的に構成する方法が論じられている。

　第3章は「One-pass Generalized-Minimum-Distance Decoding Algorithm」と題し、Forneyによって定式化された代表的な軟判定復号方式の一つであるGMD復号を効率的に実行するアルゴリズムを与えている。これにより、設計最小距離dの誤り訂正符号に関して、計算量のオーダーは従来比で1/dとなることが示されている。

　第4章は「Acceptance Criteria for Generalized Minimum Distance Decoding」と題し、第3章で論じたGMD復号の出力結果が最適となるための新たな十分条件を導いている。これは誤り率特性の評価、及び誤り検出を行う場合に有用である。この十分条件は、従来知られている条件よりも緩く、より必要十分条件に近いことが示されており、さらに計算機実験によってその効果を確認している。

　第5章は「Bounded Distance +t Soft-Decision BCH Decoding」と題し、第3,4章で論じているGMD復号の誤り率特性を改善する方法、及びそれを実行するアルゴリズムを提案している。計算量のオーダーはGMD復号と同一であることが示されている。また、計算機実験を通して誤り率特性を評価し、その有効性を示している。

　第6章は「Fast Chase Decoding and Maximum-Likelihood Decoding」と題し、Chaseによって定式化されたChase復号を効率的に実行するアルゴリズムを与えている。これにより、設計距離dの誤り訂正符号に関して、計算量のオーダーは従来比で1/dとなることが示されている。また、最尤復号を実現するための方針の一つとして、最近研究が進んでいる最尤性判定法と第2,6章の結果を組み合わせて得られた最尤復号アルゴリズムが提示されている。

　第7章は「Conclusion」であり、本論文の成果を要約するとともに、今後の課題が示されている。

　以上とれを要するに、本論文は、データ伝送のさらなる高信頼化・高速化を目的とした誤り訂正符号化・復号技術において、復号アルゴリズム設計の基礎理論を構築し、それに基づいて幾つかのタイプの効率的な軟判定復号方式と実装方法を提案するとともに、計算量と誤り率特性の評価を通して個々の方式の有効性を示しており、電子情報工学上貢献するところが少なくない。

　よって本論文は博士(工学)の学位請求論文として合格と認められる。