JP4595574B2 - 復号装置および方法、並びにプログラム - Google Patents

Description

本発明は、復号装置および方法、並びにプログラムに関し、特に、代数的手法を用いた誤り訂正符号技術において復号性能を向上させることができるようにする復号装置および方法、並びにプログラムに関する。

従来、代数幾何符号、例えばリードソロモン（Reed-Solomon）符号やその部分体部分符号としてのBCH（Bose-Chaudhuri-Hocquenghem）符号に対する復号方法として、その代数的性質を利用した、性能コストおよび計算コストが共に良い方法が知られている。

例えば、符号長ｎ、情報長ｋ、定義体GF(q)(q=p^m,p:素数)、最小距離d=n-kのリードソロモン符号をRS(n,k)とすると、硬判定受信語をハミング（Hamming）距離が最小の符号語に復号する限界距離復号方法は、t<d/2を満たすｔ個の誤りシンボルの訂正を保証するものとして良く知られている方法である。また、Guruswami-Sudanによるリスト復号（以下、G-Sリスト復号と称する）方法は、T＜√ｎｋを満たすｔ個の誤りシンボルの訂正を保証している（例えば、非特許文献１参照）。

このG-Sリスト復号の拡張版として軟判定受信語を用いたKoetter-Vardyによるリスト復号（以下、K-Vリスト復号と称する）方法は、G-Sリスト復号の場合と同様に、受信情報から各シンボルの信頼性の算出、信頼性から２変数多項式補間条件の抽出、２変数多項式の補間、並びに、補間多項式の因数分解による復号語リスト作成の４つの手順により構成され、硬判定復号時に比べてより高い性能を持つことが知られている（非特許文献２参照）。また、再符号化（Re-encode）により、その計算コストも現実的な範囲まで削減する方法も知られている（非特許文献３参照）。

一方、線形符号としては、確率伝播（belief propagation）を用いた繰り返し復号により限界性能に近い高性能を得られる低密度パリティ検査符号（LDPC（Low Density Parity-check Code）が昨今注目されている（非特許文献４参照）。

このLDPC符号に用いられる確率伝播は、一般に低密度なパリティ検査行列を持つ線形符号にしか有効でないことが理論的に知られており、また、リードソロモン符号やBCH符号のパリティ検査行列を低密度化することはNP-hard問題として知られている（非特許文献５）。
以上のようなことから、リードソロモン符号やBCH符号に確率伝播を用いた復号方法を適用することは困難であるとされてきた。

しかしながら、２００４年、ナラヤナン（Narayanan）等により、受信語の信頼性に応じて対角化を行ったパリティ検査行列を用いることにより、確率伝播を用いた復号方法を、リードソロモン符号、BCH符号、および、その他の低密度でないパリティ検査行列を持つ線形符号に対して効果的に適用することができることが示された（非特許文献６）。以下、そのABP（Adaptive Belief Propagation）復号方法について説明する。

例えば、符号長ｎを６とし、情報長ｋを３とし、符号化率rを１／２とする符号で、以下の式（１）に示される３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。

このとき、符号空間Ｃは、以下の式（２）により示される。

ある符号語があるチャネル、例えばBPSK（Binary Phase Shift Keying）変調後に、AWGN（Adaptive White Gaussian Noise）チャネルを通った後、以下の式（３）に示されるような受信語として受信器に受け取られたとする。

このような場合に受信器の復号装置により実行される復号処理の流れを図１のフローチャートを参照して説明する。

最初に、ステップＳ１において、復号装置は受信語の信頼性順を探索する。復号装置は、受信された受信語より、各受信シンボル（式（３）の右辺の各項）の絶対値の大きさを各受信シンボルの信頼性の高さとし、各受信シンボルについて順位付けを行う。つまり、復号装置は、例えば以下の式（４）の丸で囲まれた数字の様に、各受信シンボルに対して、信頼性の低い順に番号をつける。

次に、復号装置は、ステップＳ２において、この順位付けされた各受信シンボルを所定の規則に従って並び替え、シンボルの優先順位の順序を変換する。この規則は、後述するように、互いに異なる規則が外側繰り返し回数分予め用意されており、その外側繰り返しの度に異なる方法が選択される。

順序を変換すると復号装置は、次にステップＳ３において、その順序に応じてパリティ検査行列Ｈの対角化を行う。例えば、順序の変換により、各受信シンボルに対してその信頼性の低い順に優先順位を付した場合、復号装置は、パリティ検査行列Ｈに対して、その信頼性の低いシンボルに対応する列より順に対角化を行う。

例えば、各受信シンボルの信頼性順が上述した式（４）に示されるような場合、パリティ検査行列Ｈの、信頼性の最も低いシンボルに対応する列は第３列であり、次に信頼性の低いシンボルに対応する列は第５列であり、その次に信頼性の低いシンボルに対応する列は第１列であり、さらにその次に信頼性の低いシンボルに対応する列は第４列または第６列であり、最も信頼性の高いシンボルに対応する列は第２列となる。復号装置は、その優先順位に従ってパリティ検査行列Ｈの対角化を行う。

すなわち、復号装置は、まず、パリティ検査行列Ｈに対して第３列を要に基本変形を行う。具体的には、復号装置は、第３列を「１００」とするように、第１行と第３行の排他的論理和を第３行とし、パリティ検査行列Ｈを以下の式（５）のように変換する。

次に、復号装置は、パリティ検査行列Ｈに対して第５列を要に基本変形を行う。具体的には、復号装置は、第５列を「０１０」とするように、第２行と第３行を入れ替え、パリティ検査行列Ｈを以下の式（６）のように変換する。

次に、復号装置は、パリティ検査行列Ｈに対して第１列を要に基本変形を行う。具体的には、復号装置は、第１列を「００１」とするように、第１行と第３行の排他的論理和を第１行に代入し、第２行と第３行の排他的論理和を第２行に代入し、パリティ検査行列Ｈを以下の式（７）に示されるようなパリティ検査行列Ｈ_newに変換する。

なお、対角化を試みた列がそれ以前に対角化した列と線形従属であった場合、復号装置は、その列をそのまま残し次の順位の列で対角化を試みる。この様にして、復号装置は、パリティ検査行列Ｈのランク分対角化を行い、新たなパリティ検査行列Ｈ_newを得る。そして、復号装置は、ステップＳ４において、その得られたパリティ検査行列Ｈ_newを用いて確率伝播による信頼性の更新を行う。

図２は式（７）に示されるパリティ検査行列Ｈ_newに対応するタナーグラフである。確率伝播（belief propagation）はタナーグラフのエッジに沿ってメッセージを行き来させることによって実現される。図２において、バリアブルノード（variable node）１１乃至バリアブルノード１６は、行列（図２の場合パリティ検査行列Ｈ_new）の各列に対応するノードである。チェックノード（check node）２１乃至チェックノード２３は、行列（図２の場合パリティ検査行列Ｈ_new）の各行に対応するノードである。

以下において、ｉおよびｊを自然数とし、第ｉ番目のバリアブルノードから第ｊ番目のチェックノードへのメッセージをＲ_i,jと称し、第ｊ番目のチェックノードから第ｉ番目のバリアブルノードへのメッセージをＱ_i,jと称し、第ｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ(ｉ)と称し、第ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ(ｊ)と称する。

このとき、メッセージＲ_i,jおよびメッセージＱ_i,jの更新式はそれぞれ以下の式（８）および式（９）の様になる。

式（９）において、係数θはVertical Step Damping Factorと呼ばれる収束係数であり、その値は０＜θ≦１である。メッセージＱ_i,jの初期値としては受信シンボルｙ_jが設定され、外部情報（Extrinsic Information）

の更新は、以下の式（１０）により行われる。

つまり、復号装置は、図１のステップＳ５において、各符号シンボルの対数尤度比（LLR：LogLikelihood Ratio）Λ_qを以下の式（１１）のように算出する。

式（１１）において、係数α₁はAdaptive Belief Propagation Damping Factorと呼ばれる収束係数であり、その値は０＜α≦１である。

LLRを算出した復号装置は、ステップＳ６に処理を進め、算出したLLRの信頼性順を探索する。すなわち、復号装置は、算出したLLRの絶対値の大きさを信頼性とし、その順序を探索する。後述するようにLLRの更新は、所定の条件を満たすまで繰り返し行われる。この信頼性順の探索は、次回の更新（パリティ検査行列Ｈの対角化）のために行われる。

復号装置は、次にステップＳ７において、以上のように算出（更新）されたLLRを復号し、復号語を得る。この復号方法としては、例えば、硬判定復号、限界距離復号、または、K-Vリスト復号等がある。そして、復号装置は、ステップＳ８において、予め定められた所定の条件である、内側繰り返し復号停止条件SC１を満たすか否かを判定する。

この確率伝播（belief propagation）によるLLRの更新は事前に用意された繰り返し停止条件SCを満たすまで繰り返される。復号装置は、確率伝播によって更新されたLLRの信頼性を用いて、再度LLRの更新を行う。つまり、復号装置は、得られたLLRの絶対値の大きさを信頼性とし、その信頼性の低いシンボルに対応する列順にパリティ検査行列の対角化を再度行うことにより、新たな確率伝播によるLLRの更新を行うことができる。そして復号装置はLLRを更新する度に、その得られたLLRを用いて復号を行う（繰り返し復号を行う）。これを内側繰り返し復号と称する。復号装置は、この内側繰り返し復号を、事前に用意された内側繰り返し復号停止条件SC１を満たすまで繰り返す。

すなわち、復号装置は、図１のステップＳ８において、内側繰り返し復号停止条件SC１を満たしていないと判定した場合、処理をステップＳ３に戻し、それ以降の処理を繰り返す。また、復号装置は、ステップＳ８において、内側繰り返し復号停止条件SC１を満たしたと判定した場合、処理をステップＳ９に進める。

ステップＳ９において、復号装置は、外側繰り返し復号停止条件SC２を満たすか否かを判定し、満たさないと判定した場合、処理をステップＳ２に戻し、それ以降の処理を繰り返す。

つまり、復号装置は、パリティ検査行列Ｈの列の対角化優先順位の初期値として、受信値の信頼性順以外の順位付け方法（互いに異なる方法）を予め複数用意する。そして復号装置は、その複数の方法を用いて、シリアルもしくはパラレルに、上述した内側繰り返し復号を複数回行う（内側繰り返し復号を繰り返し行う）。これを外側繰り返し復号と称する。復号装置は、この外側繰り返し復号を、事前に用意された外側繰り返し復号停止条件SC２を満たすまで繰り返す。

例えば、対象となる線形符号がリードソロモン符号である場合の繰り返し復号停止条件SCの例について説明する。

例えば、予め定められた最大繰り返し回数をＮ回とし、Λ_qの硬判定結果をｄ＝（d1,d2,・・・,d6）とする。ここで、硬判定結果ｄ_iは、以下の式（１２）のように表される。

このとき、復号装置は、例えば、パリティ検査行列Ｈと硬判定結果ｄの積の値が０（Ｈ・ｄ＝＝０）であるか、または、繰り返し数ｔが最大繰り返し回数Ｎ以上（ｔ≧Ｎ）であること（少なくともいずれか一方を満たすこと）を繰り返し復号停止条件SC（内側繰り返し復号停止条件SC１または外側繰り返し復号停止条件SC２）とすることができる。

また、復号装置は、これ以外にも、例えば、限界距離復号が成功したか、または、繰り返し数ｔが最大繰り返し回数Ｎ以上（ｔ≧Ｎ）であること（少なくともいずれか一方を満たすこと）を繰り返し復号停止条件SC（内側繰り返し復号停止条件SC１または外側繰り返し復号停止条件SC２）とすることもできるし、K-Vリスト復号が成功したか、または、繰り返し数ｔが最大繰り返し回数Ｎ以上（ｔ≧Ｎ）であること（少なくともいずれか一方を満たすこと）を繰り返し復号停止条件SC（内側繰り返し復号停止条件SC１または外側繰り返し復号停止条件SC２）とすることもできるし、さらに、単に、繰り返し数ｔが最大繰り返し回数Ｎ以上（ｔ≧Ｎ）であることのみを繰り返し復号停止条件SC（内側繰り返し復号停止条件SC１または外側繰り返し復号停止条件SC２）とすることもできる。

以上のような外側繰り返し復号が行われた後、ステップＳ９において、外側繰り返し復号停止条件SC２を満たしたと判定した場合、復号装置は、復号処理を終了する。
V.Guruswami,M.Sudan, Improved decoding of Reed-Solomon and Algebraic-Geometry codes, IEEE Transactions on Information Theory,vol.45,pp1757-1767,1999 R.Koetter,A.Vardy, Algebraic soft-decision decoding of Reed-Solomon codes, IEEE Transactions on Information Theory,2001 R.Koetter,J.Ma,A.Vardy,A.Ahmed, Efficient Interpolation and Factorization in Algebraic Soft-Decision Decoding of Reed-Solomon codes, Proceedings of ISIT2003 D.MacKay, Good Error-Correcting Codes Based on Very Sparse Matrices, IEEE Transactions on Information Theory,1999 Berlekamp,R.McEliece,H.van Tilborg, On the inherent intractability of certain coding problems, IEEE Transactions on Information Theory,vol.24,pp.384-386,May,1978 Jing Jiang,K.R.Narayanan, Soft Decision Decoding of RS Codes Using Adaptibe Parity Check Matrices. Proceedings of IEEE Internationnal Symposium on Information Theory 2004

しかしながら、以上のような、従来のAdaptive Belief Propagationを用いた手法で復号が行われる場合、無視できない確率でデコーダエラー、つまり、復号装置側でエラーと認識できないエラーが生起してしまい、復号装置において良い復号性能が得られない恐れがあった。

本発明はこのような状況に鑑みてなされたものであり、Adaptive Belief Propagationによって更新された信頼性を用いて繰り返し復号を行う際に、復号装置が、途中得られた復号語候補のリストを保持し、最後にリストより最も復号語らしいものを選出するようにすることにより、デコーダエラー生起確率が抑制され、より高い復号性能を得ることができるようにするものである。

本発明の復号装置は、供給された符号語および符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する保持手段と、保持手段に保持されている信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化手段と、対角化手段により対角化されたパリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播手段と、符号語の各シンボルとして、確率伝播手段により行われた確率伝播によって更新されたメッセージを用いて対数尤度比を算出する対数尤度比算出手段と、対数尤度比算出手段により算出された対数尤度比の信頼性順を探索し、対数尤度比および対数尤度比の信頼性順に関する情報を用いて、保持手段に保持されている符号語および信頼性順に関する情報を更新する信頼性順探索手段と、対数尤度比算出手段により算出された対数尤度比を用いて復号を行う復号手段と、対角化手段によるパリティ検査行列の対角化、確率伝播手段による確率伝播、対数尤度比算出手段による対数尤度比の算出、信頼性順探索手段による信頼性順の探索、および復号手段による復号を所定の回数繰り返させるように制御する復号制御手段と、復号制御手段により制御されて行われる繰り返し復号により得られる復号語のリストを作成して保持する復号語リスト作成手段と、復号語リスト作成手段により作成された復号語リストより復号語を１つ選択する復号語選択手段とを備えることを特徴とする。

前記所定の回数は予め定められた値であるようにすることができる。

前記対角化手段は、パリティ検査行列の、信頼性順の最も低い受信シンボルに対応する列から順に優先的に対角化を行うようにすることができる。

前記対角化手段は、パリティ検査行列の各列を、各列が対応する受信シンボルの信頼性順の低い順に並べ、さらにその順番の一部を所定の方法で並び替え、その並び替えられた順番にパリティ検査行列の各列の対角化を行うようにすることができる。

前記対角化手段は、パリティ検査行列の対角化を行う列の優先順位の初期値の決定方法を複数種類予め用意しており、優先順位を初期化する度に決定方法を変更するようにすることができる。

前記復号手段は、対数尤度比算出手段により算出された対数尤度比を用いて硬判定復号を行うようにすることができる。

前記復号手段は、線形符号として有限体F_q（ｑ＝ｐ^m，ｐ；素数）上代数幾何符号もしくはその同型を用い、複数回の更新により得られた信頼性を入力として復号を行うようにすることができる。

前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてSudan,Grusuwami-Sudan，若しくは、その他のアルゴリズムによる硬判定リスト復号を行うようにすることができる。

前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてKoetter-Vardy，若しくは、その他のアルゴリズムによる重複度設定および軟判定リスト復号を行うようにすることができる。

前記復号語選択手段は、復号語リストに登録されている復号語に対して最大事後確率復号を行い、復号語を１つ選択するようにすることができる。

本発明の復号方法は、供給された符号語および符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する第１の保持部に保持されている信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化ステップと、対角化ステップの処理により対角化されたパリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播ステップと、符号語の各シンボルとして、確率伝播ステップの処理により行われた確率伝播によって更新されたメッセージを用いて対数尤度比を算出する対数尤度比算出ステップと、対数尤度比算出ステップの処理により算出された対数尤度比の信頼性順を探索し、対数尤度比および対数尤度比の信頼性順に関する情報を用いて、第１の保持部に保持されている符号語および信頼性順に関する情報を更新する信頼性順探索ステップと、対数尤度比算出ステップの処理により算出された対数尤度比を用いて復号を行う復号ステップと、対角化ステップの処理によるパリティ検査行列の対角化、確率伝播ステップの処理による確率伝播、対数尤度比算出ステップの処理による対数尤度比の算出、信頼性順探索ステップの処理による信頼性順の探索、および復号ステップの処理による復号を所定の回数繰り返させるように制御する復号制御ステップと、復号制御ステップの処理により制御されて行われる繰り返し復号により得られる復号語のリストを作成して第２の保持部に保持させる復号語リスト作成ステップと、復号語リスト作成ステップの処理により作成された復号語リストより復号語を１つ選択する復号語選択ステップとを含むことを特徴とする。

本発明のプログラムは、供給された符号語および符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する第１の保持部に保持されている信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化ステップと、対角化ステップの処理により対角化されたパリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播ステップと、符号語の各シンボルとして、確率伝播ステップの処理により行われた確率伝播によって更新されたメッセージを用いて対数尤度比を算出する対数尤度比算出ステップと、対数尤度比算出ステップの処理により算出された対数尤度比の信頼性順を探索し、対数尤度比および対数尤度比の信頼性順に関する情報を用いて、第１の保持部に保持されている符号語および信頼性順に関する情報を更新する信頼性順探索ステップと、対数尤度比算出ステップの処理により算出された対数尤度比を用いて復号を行う復号ステップと、対角化ステップの処理によるパリティ検査行列の対角化、確率伝播ステップの処理による確率伝播、対数尤度比算出ステップの処理による対数尤度比の算出、信頼性順探索ステップの処理による信頼性順の探索、および復号ステップの処理による復号を所定の回数繰り返させるように制御する復号制御ステップと、復号制御ステップの処理により制御されて行われる繰り返し復号により得られる復号語のリストを作成して第２の保持部に保持させる復号語リスト作成ステップと、復号語リスト作成ステップの処理により作成された復号語リストより復号語を１つ選択する復号語選択ステップとを含むことを特徴とする。

本発明の復号装置および方法、並びにプログラムにおいては、供給された符号語および符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報が保持され、その保持されている信頼性順に関する情報に基づいて、パリティ検査行列の対角化が行われ、対角化されたパリティ検査行列を用いて確率伝播が行われてメッセージが更新され、符号語の各シンボルとして、その確率伝播によって更新されたメッセージを用いて対数尤度比が算出され、算出された対数尤度比の信頼性順が探索され、対数尤度比および対数尤度比の信頼性順に関する情報を用いて、保持されている符号語および信頼性順に関する情報が更新され、算出された対数尤度比を用いて復号が行われ、パリティ検査行列の対角化、確率伝播、対数尤度比の算出、信頼性順の探索、および復号が所定の回数繰り返されるように制御され、その復号により得られる復号語のリストが作成されて保持され、またその作成された復号語リストより復号語が１つ選択される。

本発明によれば、代数的手法を用いた誤り訂正符号技術を実現することができる。特に、デコーダエラー生起確率が抑制されるようにすることができ、より高い復号性能を得ることができる。

以下、本発明の実施の形態について図を参照して説明する。

図３は、本発明を適用した復号装置の構成例を示すブロック図である。

図３に示されるABP（Adaptive Belief Propagation）復号装置３１は、供給された受信語をAdaptive Belief Propagationを用いた手法で復号する装置であり、受信語を入力として受け付け、その受信語を復号した復号語を出力する装置である。ABP復号装置３１は、復号制御部４１、受信語保持部４２、信頼性順探索部４３、順序変換部４４、パリティ検査行列対角化部４５、確率伝播部４６、LLR算出部４７、LLR信頼性順探索部４８、復号部４９、復号語追加部５０、内側繰り返し回数カウント部５１、外側繰り返し回数カウント部５２、および復号語選択部５３を有している。

復号制御部４１は、ABP復号装置３１の各部を制御し、ABP復号装置３１が行う復号処理の制御に関する処理を行う。受信語保持部４２は、ABP復号装置３１の外部より供給される受信語（符号語）を取得し、一時的に保持する。また、受信語保持部４２は、信頼性順探索部４３によりその受信語の各受信シンボルに対して信頼性の高さに応じた優先順位付けが行われると、各受信シンボルに対応させてその優先順位の情報を保持する。さらに、受信語保持部４２は、LLR信頼性順探索部４８より供給される更新されたLLRやその信頼性順（優先順位）の情報を取得し、それらの情報を各受信シンボルに対応させて保持する（保持する情報を更新する）。受信語保持部４２は、そのように保持されている各受信シンボルの優先順位の情報を順序変換部４４に供給する。

信頼性順探索部４３は、受信語保持部４２に保持されている受信語（符号語）の各受信シンボルに対して、その絶対値の大きさに応じて信頼性の順位付けを行う。例えば、信頼性順探索部４３は、受信シンボルの絶対値が大きいほどより信頼性が高いものとし、信頼性の低い方から順に（絶対値が小さい方から順に）受信シンボルに優先順位を付ける。

順序変換部４４は、復号制御部４１に制御され、受信語保持部４２より供給される受信語（各受信シンボル）の優先順位の情報を、所定のアルゴリズムで変換し、並び替えを行う。つまり、順序変換部４４は、予め複数用意された所定の方法の内、復号制御部４１により選択された方法で、受信語（各受信シンボル）の優先順位を変換し、その変換した情報をパリティ検査行列対角化部４５に供給する。

パリティ検査行列対角化部４５は、復号制御部４１に制御され、順序変換部４４より供給された変換後の受信語（各受信シンボル）の優先順位の情報、または、受信語保持部４２より供給される受信語（各受信シンボル）の優先順位の情報のいずれか一方に基づいて、パリティ検査行列Ｈの列の対角化を行う。パリティ検査行列対角化部４５は、その対角化後のパリティ検査行列Ｈ_newを確率伝播部４６に供給する。

確率伝播部４６は、パリティ検査行列対角化部４５より供給されるパリティ検査行列Ｈ_newを用いて確率伝播を行い、メッセージを更新し、それをLLR算出部４７に供給する。LLR算出部４７は、供給されたメッセージに基づいてLLRを算出し、LLRの更新を行う。LLR算出部４７は、その更新されたLLRをLLR信頼性順探索部４８に供給する。

LLR信頼性順探索部４８は、LLR算出部４７において更新されたLLRの信頼性順を探索し、その情報（更新済みのLLRやその信頼性順に関する情報）を受信語保持部４２および復号部４９に供給する。復号部４９は、供給されたLLRを復号し、得られた復号語を復号語追加部５０に供給する。なお、復号部４９による復号方法は、例えば、限界距離復号、硬判定復号、またはK-Vリスト復号等であってもよく、それ以外のどのような方法であってもよい。

復号語追加部５０は、復号部４９より復号結果として供給される復号語をリスト化し、復号語リスト５０Ａとして保持する（復号語リストを作成し、保持する）。つまり、復号語追加部５０は、内部に半導体メモリやハードディスク等の記憶媒体よりなる記憶領域を有しており、その記憶領域内に得られた復号語をリスト化した復号語のリスト（復号語リスト５０Ａ）を保持している。復号語追加部５０は、復号部４９より新たな復号語が供給されると、その復号語を復号語リスト５０Ａに追加して記憶する。そして復号語追加部５０は、その処理が終了したことを示す処理終了通知を内側繰り返し回数カウント部５１に供給する。

内側繰り返し回数カウント部５１は、その内部にカウンタを有しており、内側繰り返し復号の回数をカウントし、そのカウント値を保持する。つまり、内側繰り返し回数カウント部５１は、復号語追加部５０より処理終了通知が供給される度に、その通知の取得回数をカウントし、そのカウント値（これまでに行われた内側繰り返し復号の回数に関する情報）を復号制御部４１に供給する。復号制御部４１は、そのカウント値に基づいて、内側繰り返し復号を終了させるか否かを判定する。内側繰り返し復号を終了させる場合、復号制御部４１は、順序変換部４４を制御して受信シンボルの優先順位の変換処理を実行させるとともに、内側繰り返し回数カウント部５１に対して、そのカウント値をリセットさせ、さらに、外側繰り返し回数カウント部５２を制御し、そのカウント値をインクリメントさせる。内側繰り返し復号を終了させない場合、復号制御部４１は、パリティ検査行列対角化部４５を制御してパリティ検査行列Ｈの対角化を実行させる。

外側繰り返し回数カウント部５２は、その内部にカウンタを有しており、外側繰り返し復号の回数をカウントし、そのカウント値を保持する。つまり、外側繰り返し回数カウント部５２は、復号制御部４１に制御されてカウント値をインクリメントすることで外側繰り返し復号の回数をカウントする。そしてカウントを行うと、外側繰り返し回数カウント部５２は、その度に、復号語選択部５３を制御し、復号語の選択を実行させる。

復号語選択部５３は、外側繰り返し回数カウント部５２に制御され、復号語追加部５０より復号語リスト５０Ａを取得し、そこに登録されている復号語の中から、最適な復号語（最も復号語らしいもの）を選択する。このとき復号語選択部５３は、復号語リスト５０Ａの復号語に対して例えばMAP（Maximum APosteriori probability：最大事後確率）復号を行い、最適な復号語を１つ選択する。復号語選択部５３は、その選択された復号語を、ABP復号装置３１の外部に出力する。

以上のような復号処理の流れを、図４のフローチャートを参照して説明する。なお、ここでは具体的な例を適宜適用して説明する。つまり、有限体として

、線形符号ｃとして符号長７、情報長３のリードソロモン符号であるRS(7,3)に対する復号処理の場合を具体例として説明する。

復号処理の流れを説明する前に、まず、パリティ検査行列Ｈについて説明する。なお、ここでは、

の原始根をαとし、原始多項式を以下の式（１３）で表す。

また、符号の生成多項式を以下の式（１４）で表す。

このとき符号空間Ｃのパリティ検査行列Ｈは以下の式（１５）で与えられる。

式（１５）に示されるように、このときのパリティ検査行列Ｈは４行×７列の行列により構成される。

ところで、有限体

はＦ₂の３次拡大体であるので、その行列をすべて４次元に展開することが可能である。つまり、式（１５）で示されるパリティ検査行列Ｈを３次元展開すると、以下の式（１６）に示されるように、Ｆ₂上に１２行×２１列のパリティ検査行列Ｈ_expが得られる。

このとき、対応する符号語もパリティ検査行列Ｈの場合と同様に、以下の式（１７）に示されるように、Ｆ₂上に２１ビットに展開される。

この符号語をBPSK変調し、それを、AWGNチャネル上を伝送させた結果、LLRとして、例えば、以下の式（１８）で示されるような受信語ｙが得られたとする。

このような受信語ｙがABP復号装置３１に供給され、受信語保持部４２がその受信語ｙを保持すると、復号処理が開始される。復号処理が開始されると、最初に、信頼性順探索部４３は、ステップＳ２１において、受信語保持部４２に保持されている受信語ｙ（すなわちLLR）に対して各受信シンボルの信頼性順を探索する。

例えば、信頼性順探索部４３が、式（１８）で示される受信語ｙに対して、信頼性順の探索を行い、各受信シンボルに信頼性の低い順に順序をつけると以下の式（１９）の様になる。

つまり、この場合、対角化するパリティ検査行列Ｈ_exp（式（１６））の列のインデックスの順は、その優先順位の低い順に左から整列させると以下の通りとなる。

4,6,3,14,2,12,15,7,10,20,1,13,19,8,9,18,5,11,17,21,16

順序変換部４４は、ステップＳ２２において、必要に応じて、このように受信シンボルの優先順の順序（すなわち、パリティ検査行列Ｈ_expにおける対角化する列の優先順序）を変換する。例えば、受信シンボルの信頼性の低い順に優先順位を付ける場合は、順序変換部４４は、上述した順序で各受信シンボルの優先順を設定（または変更）する。

パリティ検査行列対角化部４５は、ステップＳ２３において、ステップＳ２２において設定（変更）された順序に応じてパリティ検査行列Ｈ_expの対角化を行う。

例えば、式（１６）に示されるパリティ検査行列Ｈ_expについて、パリティ検査行列対角化部４５が上述した受信シンボルの優先順に従って、その各受信シンボルに対応した列から順に対角化を行うと、以下の式（２０）で示されるパリティ検査行列Ｈ_newが得られる。

式（２０）において、パリティ検査行列のＨ_new四角で囲まれている要素を含む列が、対角化が行われた列である。ステップＳ２４において、確率伝播部４６は、この式（２０）で示されるパリティ検査行列Ｈ_newを用いて確率伝播を行い、メッセージを更新する。そして、ステップＳ２５において、LLR算出部４７は、その更新されたメッセージを用いて外部情報を更新し、さらにLLRを算出する（LLRを更新する）。LLR信頼性順探索部４８は、ステップＳ２６において、そのLLRの信頼性順を探索する。このように、確率伝播部４６、LLR算出部４７、およびLLR信頼性順探索部４８が、上述した式（２０）に示されるパリティ検査行列Ｈ_newを用いてLLRの更新に関する処理を行うことにより、例えば、以下の式（２１）に示されるような、新たなLLRとその信頼性順が得られる。

LLR信頼性順探索部４８は、この情報を受信語保持部４２に保持させるとともに、それを復号部４９にも供給する。復号部４９は、ステップＳ２７において、その更新された新たなLLR（式（２１））に対して、例えば、硬判定復号、限界距離復号、またはK-Vリスト復号等の復号を行い、復号語を得る。なお、復号部４９は、この復号方法として、どのような方法を用いるようにしてもよい。

このように復号語が得られると、復号語追加部５０は、ステップＳ２８において、その新たに得られた復号語を復号語リスト５０Ａに追加する。内側繰り返し回数カウント部５１は、ステップＳ２９において、その内側繰り返し復号の回数である内側繰り返し数Ｔ_inをカウントする（カウント値をインクリメントする）。

ステップＳ３０において、復号制御部４１は、その内側繰り返し数Ｔ_in（すなわち、内側繰り返し回数カウント部５１によりカウントされたカウント値）が、内側繰り返し復号停止条件SC１として予め定められた所定の閾値である最大内側繰り返し回数Ｎ₁以上であるか（Ｎ₁に達したか）否かを判定する。

内側繰り返し数Ｔ_inが最大内側繰り返し回数Ｎ₁より小さい（内側繰り返し数Ｔ_inが最大内側繰り返し回数Ｎ₁に達していない）と判定した場合、復号制御部４１は、処理をステップＳ２３に戻し、それ以降の処理を実行させる。つまり、この場合、復号制御部４１は、パリティ検査行列対角化部４５を制御する。パリティ検査行列対角化部４５は、受信語保持部４２より最新のLLRを取得し、パリティ検査行列Ｈの対角化を行う。

以上のように、ステップＳ２３乃至ステップＳ３０の処理が繰り返され、内側繰り返し復号が行われる。そして、ステップＳ３０において、内側繰り返し数Ｔ_inが最大内側繰り返し回数Ｎ₁以上である（内側繰り返し数Ｔ_inが最大内側繰り返し回数Ｎ₁に達した）と判定した場合、復号制御部４１は、処理をステップＳ３１に進める。

ステップＳ３１において、内側繰り返し回数カウント部５１は、復号制御部４１に制御されて、内側繰り返し数Ｔ_inをリセットし、初期値に戻す。ステップＳ３２において、外側繰り返し回数カウント部５２は、復号制御部４１に制御されて、外側繰り返し復号の回数である外側繰り返し数Ｔ_outをカウントする（カウント値をインクリメントする）。

そして、ステップＳ３３において、復号制御部４１は、その外側繰り返し数Ｔ_OUT（すなわち、外側繰り返し回数カウント部５２によりカウントされたカウント値）が、外側繰り返し復号停止条件SC２として予め定められた所定の閾値である最大外側繰り返し回数Ｎ₂以上であるか（Ｎ₂に達したか）否かを判定する。

外側繰り返し数Ｔ_OUTが最大外側繰り返し回数Ｎ₂より小さい（外側繰り返し数Ｔ_OUTが最大外側繰り返し回数Ｎ₂に達していない）と判定した場合、復号制御部４１は、処理をステップＳ２２に戻し、それ以降の処理を実行させる。つまり、この場合、復号制御部４１は、順序変換部４４を制御する。順序変換部４４は、受信語保持部４２より最新のLLRを取得し、各受信シンボルの優先順を所定の方法で変換する。

つまり、順序変換部４４は、パリティ検査行列の対角化優先順位の設定方法（内側繰り返し復号における優先順位の初期値）として、互いに異なる複数の方法（順位の設定の仕方）を予め用意している。復号制御部４１は、その複数の方法の中から未使用の方法を１つ選択し、その実行を指示する。順序変換部４４は、その制御に基づいて（選択された方法を用いて）パリティ検査行列の対角化優先順位の設定を行う（順序を変換する）。

例えば、順序変換部４４が、第１回目の内側繰り返し復号における優先順位の初期値（第１回目の外側繰り返しにおいて順序変換部４４が設定した優先順位）として、受信値のLLRの信頼性の低い順を採用としたとする。このとき、式（１９）に示される受信語ｙにおいて、パリティ検査行列の対角化優先順位のインデックスは、左から順に以下のように整列される。

これに対して、第２回目の内側繰り返し復号における優先順位の初期値の設定時（第２回目の外側繰り返しにおいて順序変換部４４が優先順位を設定する時）においては、順序変換部４４は、上述した方法と異なる方法を採用する。例えば、順序変換部４４は、上述したインデックスの順序に対し、以下に示されるように、２１／Ｎ₂＝２１／３＝７列分の入れ換えを行う。

つまり、この場合、第１回目の内側繰り返し復号における優先順位の初期値の順序に対して、優先順位第１位乃至第７位の受信シンボルと、第８位乃至第１４位の受信シンボルとでその優先順位を入れ替えている。さらに、順序変換部４４は、第２回目の内側繰り返し復号における優先順位の初期値として、以下に示されるように、別の７ビット入れ替える方法を採用する。

つまり、この場合、第２回目の内側繰り返し復号における優先順位の初期値の順序に対して、優先順位第１位乃至第７位の受信シンボルと、第１５位乃至第２１位の受信シンボルとでその優先順位を入れ替えている。

このようにすることにより、順序変換部４４は、各回の内側繰り返し復号における優先順位の初期値を、互いに異なるものにすることができる。第１回目の内側繰り返しにおいては、パリティ検査行列対角化部４５は、順序変換部４４がこのように設定した初期値を取得し、その順序に従ってパリティ検査行列の対角化を行う。

以上のように、ステップＳ２２乃至ステップＳ３３の処理が繰り返され、外側繰り返し復号が行われる。そして、ステップＳ３３において、外側繰り返し数Ｔ_OUTが最大外側繰り返し回数Ｎ₂以上である（外側繰り返し数Ｔ_OUTが最大外側繰り返し回数Ｎ₂に達した）と判定した場合、復号制御部４１は、処理をステップＳ３４に進める。

ステップＳ３４において、外側繰り返し回数カウント部５２は、復号制御部４１に制御されて外側繰り返し数Ｔ_OUTをリセットし、初期値に戻す。そして、ステップＳ３５において、復号語選択部５３は、例えば、MAP復号等を実行することによって、復号語追加部５０において生成された復号語リストより、最適と思われる復号語（最も復号語らしいもの）を１つ選択し、それを復号語としてABP復号装置３１の外部に出力する。

ステップＳ３５の処理が終了すると、復号語選択部５３は、復号処理を終了する。ABP復号装置３１は、以上のような復号処理を受信した各受信語に対して行う。

図５は、以上のように短縮リードソロモン符号RS（7,3）を従来のABP復号方法で復号する場合の復号性能と、上述した本発明を適用したABP復号方法により復号する場合の復号性能の比較を示すグラフである。

図５において、曲線６１で示されるグラフが、従来のABP復号方法を用いた場合の復号性能を示しており、曲線６２で示されるグラフが、本発明を適用したABP復号方法を用いた場合の復号性能を示している。なお、従来のABP復号方法においては、繰り返し停止条件SC1,SC2として限界距離復号成功を用い、更新されたLLRを元に限界距離復号を行うようになされている。また、本発明を適用したABP復号方法においては、最大内側繰り返し回数Ｎ₁を５回とし、最大外側繰り返し回数Ｎ₂を１回とし、その繰り返しの度に復号された復号語をリストとして確保し、最後にMAP復号を行うようになされている。図５に示されるように、本発明を適用したABP復号方法の場合（曲線６２）、従来のABP復号方法の場合（曲線６１）に対して縦軸で示されるフレームエラー率（FER）が低下しており、エラー訂正能力が向上していることがわかる。

以上のように、ABP復号装置３１は、繰り返し復号において得られた復号語をリスト化し（復号語リストに追加し）、内側繰り返し復号回数と外側繰り返し復号回数を予め定められた所定の回数とし、それらの回数が繰り返された後に、得られた復号語リストの中から、所定の方法で最適な復号語を１つ選択するようにしたので、復号時にエラーと認識できないデコーダエラー生起確率が抑制されるようにすることができ、より高い復号性能を得ることができる。

また、付言すると、ABP復号装置３１は、受信語に対して最初からMAP復号を行うのではなく、繰り返し復号を行うことにより、復号語の候補を絞り込んでからMAP復号を行うようにしたので、復号処理の負荷を軽減し、より高速に復号処理を行うことができるだけでなく、その製造コストや運用コストを低減させることができる。

なお、以上において、Adaptive Belief Propagationを行ってLLRの更新を行う際、全ての繰り返しの過程において復号を行ったり、復号語リストに候補を加えたりする必要はなく、それらの処理を部分的に実行するようにしてもよい。例えば、各内側繰り返し復号の最後の１回分だけが復号されて、復号語リストに加えられるようにしてもよい。

また、得られた復号語リストから最適と思われる復号語をひとつ選定する際に、MAP復号でなくても、任意の選定方法を適用することができる。例えば、ビット（受信シンボル）ごとの信頼性を比較して、所定の閾値（threshold）以下の信頼性を所定のビット数以上持つ様な符号語はリストから省く、といった手順により選択するようにしてもよい。

さらに、以上においては、復号装置３１がリードソロモン符号を復号するように説明したが、これに限らず、例えば、BCH符号を復号するようにしてもよいし、それ以外の符号化方法に対して復号を行うようにしてもよい。

次に、以上のようなABP復号の誤り訂正システムへの適用方法の具体的な例について説明する。図６は、本発明のABP復号を誤り訂正システムに適用する場合の例について説明する図である。図６において、誤り訂正システム１００は、符号化装置１０１、チャネル１０２、および復号装置１０３により構成されるテレビジョン放送等に利用されるデジタル信号送受信システムである。

符号化装置１０１は、例えば放送局等のような、デジタル信号であるテレビジョン信号を送信する送信装置として構成される。符号化装置１０１は、リードソロモン符号化部（RS符号化部）１１１、インタリーバ１１２、および畳み込み符号化部１１３を有している。

RS符号化部１１１は、入力された情報を、リードソロモン符号を用いて符号化し、それを出力する。インタリーバ１１２は、入力されたデジタル情報の並べ替えを行い、それを出力する。畳み込み符号化部１１３は、入力されたデジタル情報に対して畳み込み符号を行って出力する。

符号化装置１０１の外部より供給された送信用のデジタル情報は、符号化装置１０１のRS符号化部１１１において、リードソロモン符号化された後、インタリーバ１１２に供給される。インタリーバ１１２は、主に通信路であるチャネル１０２において発生するバースト的誤りを拡散させるために、情報の並べ替え（インタリービング）を行う。リードソロモン符号は、複数ビットを１シンボルとする誤り訂正を行うので、インタリーバ１１２は、シンボル単位でバースト的誤りを拡散するシンボルインタリービングを行う。

並べ替えが行われた送信用のデジタル情報は、さらに、畳み込み符号化部１１３において、複数の情報ブロックに基づいて逐次的に符号系列が定まる畳み込み符号が行われる。例えば、拘束長Ｋの畳み込み符号化部１１３は、インタリーバ１１２よりデジタル情報がｋビットの情報ブロック毎に供給されると、今回供給された情報ブロックだけでなく、過去に供給された情報ブロックも含めたＫ個の情報ブロックに基づいて、ｎビットの符号ブロックに符号化する。

そして、畳み込み符号化されたデジタル情報は、図示せぬ通信部を介して、送信可能なデータ形式に変換され、送信語として、チャネル１０２上に送出される。つまり、符号化装置１０１は、供給されたテレビジョン信号を符号化して送信（放送）する。その送信された送信語は、チャネル１０２を介して復号装置１０３に供給される。すなわち、チャネル１０２は、このテレビジョン信号が伝送される有線または無線の伝送路である。

復号装置１０３は、例えば、放送局（符号化装置１０１）より送信（放送）されるテレビジョン信号を受信する受信装置（デジタルテレビジョン受像機等）として構成される。復号装置１０３は、畳み込み復号部１２１、デインタリーバ１２２、およびABP復号部１３１を有している。

畳み込み復号部１２１は、入力に対して、例えばBCJR（Bahl, Cocke, Jelinek, and Raviv）アルゴリズムやSOVA（Soft Output Viterbi Algorithm）による復号等に代表される、畳み込み符号の軟判定復号を行い、得られた復号語を出力する。デインタリーバ１２２は、並べ替えられた情報を元の順序に戻す。ABP復号部１３１は、図３に示されるABP復号装置３１を誤り訂正システム１００に適応させたものであり、基本的にABP復号装置３１と同様の構成を有しており、同様の処理を行う。従って、ABP復号部１３１の構成および処理内容は、上述したABP復号装置３１の説明を適用することができるので、その詳細な説明を省略するが、ABP復号部１３１は、デインタリーバ１２２より供給された情報（並べ替えられた軟判定復号結果）に対してABP繰り返し復号処理を行い、生成された復号語リストからMAP復号等により最適な復号語を選択し、それを出力する。

復号装置１０３は、受信したテレビジョン信号を復号する。すなわち、復号装置１０３は、図示せぬ通信部を介して、チャネル１０２上を伝送された送信語を受信する。受信された送信語（すなわち、受信語）は、畳み込み復号部１２１に供給され、畳み込み符号の軟判定復号が行われる。デインタリーバ１２２は、その畳み込み復号された受信語を取得すると、符号化装置１０１のインタリーバ１１２において行われたインタリービングに対応した方法で情報の並び替えを行い、並び替えられた情報を元の順序に戻す処理（デインタリービング）を行う。ABP復号部１３１は、上述した方法で、元の順序に戻されたデジタル情報に対して、ABP繰り返し復号を行い、ABPによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。そして、ABP復号部１３１は、得られた復号語（符号化装置１０１において符号化される前のデジタル情報を再現したもの）を、復号装置１０３の外部に出力する。

以上のようにして、図６の誤り訂正システム１００において、復号装置１０３は、容易に、性能の良い復号処理を行うことができ、より正確な通信を行うことができる。また、復号装置１０３は、ABP復号部１３１が、MAP復号を行う前に、繰り返し復号を行うことにより復号語の候補を絞り込むので、復号処理の負荷を軽減し、復号装置１０３の製造コストおよび運用コストを抑制させることができる。

なお、誤り訂正システム１００において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、BCH符号を適用するようにしてもよいし、それ以外の符号化方法を適用するようにしてもよい。

図７は、本発明のABP復号を誤り訂正システムに適用する場合の他の例について説明する図である。図７において、誤り訂正システム１５０は、符号化装置１５１、チャネル１５２、および復号装置１５３により構成されるシステムであり、例えば、ディジタルテレビ等のデジタル通信システムに用いられるシステムである。

符号化装置１５１は、図６の符号化装置１０１と同様の装置であり、符号化装置１０１と基本的に同様の構成を有し、同様の処理を行う。すなわち、符号化装置１５１は、RS符号化部１１１、インタリーバ１１２、および畳み込み符号化部１１３を有する。それらについての説明は符号化装置１０１の場合と同様であるので省略する。

チャネル１５２は、図６のチャネル１０２と同様であり、テレビジョン信号が伝送される有線または無線の伝送路である。

復号装置１５３は、畳み込み復号部１６１、デインタリーバ１２２、ABP復号部１３１、およびインタリーバ１１２を有している。畳み込み復号部１６１は、図示せぬ通信部を介して受信した受信語（符号化装置１５１より送信され、チャネル１５２を介して伝送された送信語）を取得すると、その受信語に対して、例えば、BCJRアルゴリズムやSOVA等を用いて、軟判定復号を行う。そして、畳み込み復号部１６１は、この軟判定復号された受信語をデインタリーバ１２２に供給する。また、畳み込み復号部１６１には、インタリーバ１１２より、ABP復号部１３１においてABP繰り返し復号が行われた受信語が再度並び替えられて供給される。畳み込み復号部１３１は、この受信語に対しても、図示せぬ通信部より供給された受信語の場合と同様に、例えば、BCJRアルゴリズムやSOVA等を用いて、軟判定復号を行い、デインタリーバ１２２に供給する。

デインタリーバ１２２は、図６の復号装置１０３の場合と同様に動作し、畳み込み復号部１６１より供給される軟判定復号結果の並べ替えを行い、その並べ替え結果をABP復号部１３１に供給する。

ABP復号部１３１は、図６の復号装置１０３の場合と同様に動作し、デインタリーバ１２２より供給される情報（並べ替えられた軟判定復号結果）に対してABP繰り返し復号処理を行い、生成された復号語リストからMAP復号等により最適な復号語を選択し、それを出力する。また、ABP復号部１３１は、その得られた復号語をインタリーバ１１２に供給する。

インタリーバ１１２は、符号化装置１５１の場合と同様に動作し、ABP復号部１３１より供給される情報（復号語）を所定の順番に並び替える。このインタリーバ１１２による並べ替えのパターンは、符号化装置１５１の場合と同様である。このようにして並べ替えられたデジタル情報は、再び畳み込み復号部１６１に供給される。

以上のように、復号装置１５３は、図示せぬ通信部において取得した受信語に対して、デインタリーバ１２２とインタリーバ１１２を介しながら、畳み込み復号部１６１による軟判定復号と、ABP復号部１３１による繰り返し復号とを繰り返し行い、復号処理における復号誤り確率を小さくしていく。なお、この復号装置１５３全体の復号の繰り返し回数は、予め定められていてもよいし、例えば、誤り訂正する箇所の数等のような所定の条件に基づいて、繰り返しを中止するか否かが判定されるようにしてもよい。

このように図７の誤り訂正システム１５０において、復号装置１５３は、容易に、性能の良い復号処理を行うことができ、より正確な通信を行うことができる。また、復号装置１０３は、ABP復号部１３１が、MAP復号を行う前に、繰り返し復号を行うことにより復号語の候補を絞り込むので、復号処理の負荷を軽減し、復号装置１０３の製造コストおよび運用コストを抑制させることができる。

なお、誤り訂正システム１５０において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、BCH符号を適用するようにしてもよいし、それ以外の符号化方法を適用するようにしてもよい。

図８は、本発明のABP復号を誤り訂正システムに適用する場合の、さらに他の例について説明する図である。図８において、誤り訂正システム２００は、符号化装置２０１、チャネル２０２、および復号装置２０３により構成されるシステムであり、例えば、DVD（Digital Versatile Disc）レコードプレーヤ等のデジタル記録媒体記録再生装置に用いられるシステムである。

すなわち、記録再生装置（誤り訂正システム２００）は、外部より供給されたデジタル情報を、符号化処理部（符号化装置２０１）において符号化し、図示せぬ記録再生処理部において記録媒体（チャネル２０２）に記録する。また、記録再生装置（誤り訂正システム２００）は、記録媒体（チャネル２０２）に記録されているデジタル情報を、記録再生処理部において再生し、復号処理部（復号装置２０３）において復号処理を行って元のデジタル情報を取得し、その情報を外部に出力する。

符号化装置２０１は、デジタル情報に互いに異なる次元に関するリードソロモン符号を行うリードソロモン符号化部（RS符号化部）２１１−１乃至リードソロモン符号化部（RS符号化部）２１１−ｎ（ｎは自然数）からなる。

例えば、符号化装置２０１の外部より供給されたデジタル情報は、RS符号化部２１１−１において１次元目に関するリードソロモン符号化が行われる。続いて、デジタル情報は、RS符号化部２１１−２乃至RS符号化部２１１−ｎの各部において、２次元目乃至ｎ次元目までの各次元目に関するリードソロモン符号が順に行われる。RS符号化部２１１−ｎによる符号化が終了すると、符号化装置２０１は、符号化されたデジタル情報を記録再生処理部（図示せず）に供給する。

記録再生処理部は、符号化装置２０１より供給された情報をNRZI（Non Return to Zero Invert）変換（NRZI符号化）するなどして記録媒体（チャネル２０２）に記録する。また、記録再生処理部は、記録媒体（チャネル２０２）に記録されているデジタル情報（リードソロモン符号化されたデジタル情報）を再生し、そのデジタル情報に施されたNRZI変換を元に戻し（復号し）、そのデジタル情報を復号装置２０３に供給する。

復号装置２０３は、符号化装置２０１に対応する復号器であり、デジタル情報に互いに異なる次元に関して、ABP繰り返し復号処理を行うｎ個のABP復号部（ABP復号部２３１−１乃至ABP復号部２３１−ｎ）を有している。

ABP復号部２３１−１乃至ABP復号部２３１−ｎは、それぞれ、符号化装置２０１のRS符号化部２１１−１乃至RS符号化部２１１−ｎに対応し、各次元に関するリードソロモン符号に対して、ABPを用いた繰り返し復号処理、並びに、得られた復号語リストからの最適な復号語の選択処理を行う。ABP復号部２３１−１乃至ABP復号部２３１−ｎは、それぞれ、図３に示される復号装置３１と基本的に同様の構成であり、基本的に同様の動作を行う。従って、復号装置２０３の各ABP復号部は、それぞれ、図６や図７のABP復号部１３１の場合と同様に、図３のブロック図、および図４に示されるフローチャートを適用することができる。

すなわち、復号装置２０３は、各ABP復号部（ABP復号部２３１−１乃至ABP復号部２３１−ｎの各部）において、上述したように繰り返し復号処理等を行う。その際、復号装置２０３は、図８に示されるように、符号化装置２０１の場合と逆に、まず、ABP復号部２３１−ｎにおいて第ｎ次元目に関する復号処理から行い、続いて、直列に接続される各ABP復号部において、それぞれ、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるように復号処理を行い、最後にABP復号部２３１−１において第１次元目に関する復号処理を行う。復号装置２０３は、このようにして復元した元のデジタル情報を記録再生装置（誤り訂正システム２００）の外部に出力する。

このようにすることにより、誤り訂正システム２００の復号装置２０３は、容易に性能の良い復号処理を行うことができる。つまり、記録再生装置としての誤り訂正システム２００は、より正確にデジタル情報の記録および再生を行うことができる。また、復号装置２０３は、ABP復号部２３１−１乃至ABP復号部２３１−ｎのそれぞれが、MAP復号（復号語の選択）を行う前に、繰り返し復号を行うことにより復号語の候補を絞り込むので、復号処理の負荷を軽減し、復号装置２０３の製造コストおよび運用コストを抑制させることができる。

なお、誤り訂正システム２００において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、BCH符号を適用するようにしてもよいし、それ以外の符号化方法を適用するようにしてもよい。

図９は、本発明のABP復号を誤り訂正システムに適用する場合の、さらに他の例について説明する図である。図９において、誤り訂正システム２５０は、符号化装置２５１、チャネル２５２、および復号装置２５３により構成されるシステムであり、例えば、DVDレコードプレーヤ等のデジタル記録媒体記録再生装置に用いられるシステムである。

すなわち、図８の場合と同様に、記録再生装置（誤り訂正システム２５０）は、外部より供給されたデジタル情報を、符号化処理部（符号化装置２５１）において符号化し、図示せぬ記録再生処理部において記録媒体（チャネル２５２）に記録する。また、記録再生装置（誤り訂正システム２５０）は、記録媒体（チャネル２５２）に記録されているデジタル情報を、記録再生処理部において再生し、復号処理部（復号装置２５３）において復号処理を行って元のデジタル情報を取得し、その情報を外部に出力する。

符号化装置２５１は、図８の符号化装置２０１と同様の符号化装置であり、符号化装置２０１と同様の構成を有し、同様の処理を行う。すなわち、例えば、符号化装置２５１の外部より供給されたデジタル情報は、RS符号化部２１１−１において１次元目に関するリードソロモン符号化が行われる。続いて、デジタル情報は、RS符号化部２１１−２乃至RS符号化部２１１−ｎの各部において、２次元目乃至ｎ次元目までの各次元目に関するリードソロモン符号が順に行われる。RS符号化部２１１−ｎによる符号化が終了すると、符号化装置２５１は、符号化されたデジタル情報を記録再生処理部（図示せず）に供給する。

記録再生処理部は、符号化装置２５１より供給された情報をNRZI（Non Return to Zero Invert）変換（NRZI符号化）するなどして記録媒体（チャネル２５２）に記録する。また、記録再生処理部は、記録媒体（チャネル２５２）に記録されているデジタル情報（リードソロモン符号化されたデジタル情報）を再生し、そのデジタル情報に施されたNRZI変換を元に戻し（復号し）、そのデジタル情報を復号装置２５３に供給する。

復号装置２５３は、符号化装置２５１に対応する復号器であり、それぞれが、図８に示される復号装置２０３と同様の構成であり、同様の復号処理を行う、直列に接続されたｍ個の復号部である復号部２６１−１乃至復号部２６１−ｍを有している。

復号部２６１−１乃至復号部２６１−ｍは、それぞれ、図８の復号装置２０３と同様に、符号化装置２５１のRS符号化部２１１−１乃至RS符号化部２１１−ｎに対応し、各次元に関するリードソロモン符号に対してABPを用いた繰り返し復号を行う、直列に接続されたｎ個の復号部であるABP復号部２３１−１乃至ABP復号部２３１−ｎを有している。

復号装置２５３は、まず、記録再生処理部（図示せず）より供給されたデジタル情報（チャネル２５２を介して供給されたデジタル情報）に対して、復号部２６１−１のABP復号部２３１−１乃至ABP復号部２３１−ｎの各部において、ABPを用いた繰り返し復号処理や得られた復号語リストからの復号語の選択処理を行う。

その際、復号部２６１−１は、符号化装置２５１の場合と逆に、まず、ABP復号部２３１−ｎにおいて第ｎ次元目に関する復号処理から行い、続いて、直列に接続される各ABP復号部において、それぞれ、ｎ−１次元目、ｎ−２次元目と順に次元数を下げるように復号処理を行い、最後にABP復号部２３１−１において第１次元目に関する復号処理を行う。

復号処理が終了すると、復号部２６１−１は、復号されたデジタル情報を復号部２６１−２に供給する。復号部２６１−２は、復号部２６１−１の場合と同様に、ABP復号部２３１−１乃至ABP復号部２３１−ｎを用いて、次元数を１つずつ下げるような順番で各次元に関してABPを用いた繰り返し復号処理を行い、復号されたデジタル情報を次の復号部に供給する。このようにして、順にｍ番目の復号部２６１−ｍまで復号処理が続けられる。復号部２６１−ｍにおける復号処理が完了すると、復号装置２５３は、その復号されたデジタル情報を記録再生装置（誤り訂正システム２５０）の外部に出力する。

このようにすることにより、復号装置２５３は、容易に性能の良い復号処理を行うことができ、記録再生装置としての誤り訂正システム２５０は、より正確にディジタル情報の記録および再生を行うことができる。また、復号装置２５３は、ABP復号部２３１−１乃至ABP復号部２３１−ｎのそれぞれが、MAP復号（復号語の選択）を行う前に、繰り返し復号を行うことにより復号語の候補を絞り込むので、復号処理の負荷を軽減し、復号装置２５３の製造コストおよび運用コストを抑制させることができる。

なお、誤り訂正システム２５０において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、BCH符号を適用するようにしてもよいし、それ以外の符号化方法を適用するようにしてもよい。

上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウエアにより実行させることもできる。この場合、例えば、上述した復号装置や誤り訂正システムは、それぞれ、図１０に示されるようなパーソナルコンピュータとして構成されるようにしてもよい。

図１０において、パーソナルコンピュータ３００のCPU（Central Processing Unit）３０１は、ROM（Read Only Memory）３０２に記憶されているプログラム、または記憶部３１３からRAM（Random Access Memory）３０３にロードされたプログラムに従って各種の処理を実行する。RAM３０３にはまた、CPU３０１が各種の処理を実行する上において必要なデータなども適宜記憶される。

CPU３０１、ROM３０２、およびRAM３０３は、バス３０４を介して相互に接続されている。このバス３０４にはまた、入出力インタフェース３１０も接続されている。

入出力インタフェース３１０には、キーボード、マウスなどよりなる入力部３１１、CRT（Cathode Ray Tube）、LCD（Liquid Crystal Display）などよりなるディスプレイ、並びにスピーカなどよりなる出力部３１２、ハードディスクなどより構成される記憶部３１３、モデムなどより構成される通信部３１４が接続されている。通信部３１４は、インターネットを含むネットワークを介しての通信処理を行う。

入出力インタフェース３１０にはまた、必要に応じてドライブ３１５が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア３２１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部３１３にインストールされる。

上述した一連の処理をソフトウエアにより実行させる場合には、そのソフトウエアを構成するプログラムが、ネットワークや記録媒体からインストールされる。

この記録媒体は、例えば、図１０に示されるように、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フレキシブルディスクを含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（ＭＤ（Mini-Disk）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア３２１により構成されるだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM３０２や、記憶部３１３に含まれるハードディスクなどで構成される。

なお、本明細書において、記録媒体に記録されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。

また、本明細書において、システムとは、複数のデバイス（装置）により構成される装置全体を表すものである。なお、以上において、１つの装置として説明した構成を分割し、複数の装置として構成するようにしてもよい。逆に、以上において複数の装置として説明した構成をまとめて１つの装置として構成されるようにしてもよい。また、各装置の構成に上述した以外の構成を付加するようにしてももちろんよい。さらに、システム全体としての構成や動作が実質的に同じであれば、ある装置の構成の一部を他の装置の構成に含めるようにしてもよい。

従来の復号処理の流れを説明するフローチャートである。 従来の復号処理に対応するタナーグラフの例を示す図である。 本発明を適用した復号装置の構成例を示すブロック図である。 図３の復号装置により実行される復号処理の流れを説明するフローチャートである。 従来の復号処理と本発明を適用した復号処理とでフレームエラー率を比較するための図である。 本発明を適用した誤り訂正システムの構成例を示すブロック図である。 本発明を適用した誤り訂正システムの他の構成例を示すブロック図である。 本発明を適用した誤り訂正システムの、さらに他の構成例を示すブロック図である。 本発明を適用した誤り訂正システムの、さらに他の構成例を示すブロック図である。 本発明を適用したパーソナルコンピュータの構成例を示す図である。

符号の説明

３１ ABP復号装置， ４１ 復号制御部， ４２ 受信語保持部， ４３ 信頼性順探索部， ４４ 順序変換部， ４５ パリティ検査行列対角化部， ４６ 確率伝播部， ４７ LLR算出部， ４８ LLR信頼性順探索部， ４９ 復号部， ５０ 復号語追加部， ５０Ａ 復号語リスト， ５１ 内側繰り返し回数カウント部， ５２ 外側繰り返し回数カウント部， ５３ 復号語選択部， １００ 誤り訂正システム， １０１ 符号化装置， １０２ チャネル， １０３ 復号装置， １１１ RS符号化部， １１２ インタリーバ， １１３ 畳み込み符号化部， １２１ 畳み込み復号部， １２２ デインタリーバ， １３１ ABP復号部， １５０ 誤り訂正システム， １５１ 符号化装置， １５２ チャネル， １５３ 復号装置， １６１ 畳み込み復号部， ２００ 誤り訂正システム， ２０１ 符号化装置， ２０２ チャネル， ２０３ 復号装置， ２１１−１乃至２１１−ｎ RS符号化部， ２３１−１乃至２３１−ｎ ABP復号部， ２５０ 誤り訂正システム， ２５１ 符号化装置， ２５２ チャネル， ２５３ 復号装置， ２６１−１乃至２６１−ｍ 復号部， ３００ パーソナルコンピュータ

Claims (12)

1. 環Ｒ上線形符号に対する復号処理を行う復号装置であって、
   供給された符号語および前記符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する保持手段と、
   前記保持手段に保持されている前記信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化手段と、
   前記対角化手段により対角化された前記パリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播手段と、
   前記符号語の各シンボルとして、前記確率伝播手段により行われた確率伝播によって更新された前記メッセージを用いて対数尤度比を算出する対数尤度比算出手段と、
   前記対数尤度比算出手段により算出された前記対数尤度比の信頼性順を探索し、前記対数尤度比および前記対数尤度比の信頼性順に関する情報を用いて、前記保持手段に保持されている前記符号語および前記信頼性順に関する情報を更新する信頼性順探索手段と、
   前記対数尤度比算出手段により算出された前記対数尤度比を用いて復号を行う復号手段と、
   前記対角化手段によるパリティ検査行列の対角化、前記確率伝播手段による確率伝播、前記対数尤度比算出手段による前記対数尤度比の算出、前記信頼性順探索手段による前記信頼性順の探索、および前記復号手段による復号を所定の回数繰り返させるように制御する復号制御手段と、
   前記復号制御手段により制御されて行われる繰り返し復号により得られる復号語のリストを作成して保持する復号語リスト作成手段と、
   前記復号語リスト作成手段により作成された前記復号語リストより復号語を１つ選択する復号語選択手段と
   を備えることを特徴とする復号装置。
2. 前記所定の回数は予め定められた値である
   ことを特徴とする請求項１に記載の復号装置。
3. 前記対角化手段は、前記パリティ検査行列の、前記信頼性順の最も低い受信シンボルに対応する列から順に優先的に対角化を行う
   ことを特徴とする請求項１に記載の復号装置。
4. 前記対角化手段は、前記パリティ検査行列の各列を、各列が対応する受信シンボルの信頼性順の低い順に並べ、さらにその順番の一部を所定の方法で並び替え、その並び替えられた順番に前記パリティ検査行列の各列の対角化を行う
   ことを特徴とする請求項１に記載の復号装置。
5. 前記対角化手段は、前記パリティ検査行列の対角化を行う列の優先順位の初期値の決定方法を複数種類予め用意しており、前記優先順位を初期化する度に前記決定方法を変更する
   ことを特徴とする請求項１に記載の復号装置。
6. 前記復号手段は、前記対数尤度比算出手段により算出された前記対数尤度比を用いて硬判定復号を行う
   ことを特徴とする請求項１に記載の復号装置。
7. 前記復号手段は、線形符号として有限体Fq（ｑ＝ｐm，ｐ；素数）上代数幾何符号もしくはその同型を用い、複数回の更新により得られた前記信頼性を入力として復号を行う
   ことを特徴とする請求項１に記載の復号装置。
8. 前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、前記復号手段は、複数回の更新により得られた前記信頼性を入力としてSudan,Grusuwami-Sudan，若しくは、その他のアルゴリズムによる硬判定リスト復号を行う
   ことを特徴とする請求項７に記載の復号装置。
9. 前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、前記復号手段は、複数回の更新により得られた前記信頼性を入力としてKoetter-Vardy，若しくは、その他のアルゴリズムによる重複度設定および軟判定リスト復号を行う
   ことを特徴とする請求項７に記載の復号装置。
10. 前記復号語選択手段は、前記復号語リストに登録されている復号語に対して最大事後確率復号を行い、復号語を１つ選択する
    ことを特徴とする請求項１に記載の復号装置。
11. 環Ｒ上線形符号に対する復号処理を行う復号装置の復号方法であって、
    供給された符号語および前記符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する第１の保持部に保持されている前記信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化ステップと、
    前記対角化ステップの処理により対角化された前記パリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播ステップと、
    前記符号語の各シンボルとして、前記確率伝播ステップの処理により行われた確率伝播によって更新された前記メッセージを用いて対数尤度比を算出する対数尤度比算出ステップと、
    前記対数尤度比算出ステップの処理により算出された前記対数尤度比の信頼性順を探索し、前記対数尤度比および前記対数尤度比の信頼性順に関する情報を用いて、前記第１の保持部に保持されている前記符号語および前記信頼性順に関する情報を更新する信頼性順探索ステップと、
    前記対数尤度比算出ステップの処理により算出された前記対数尤度比を用いて復号を行う復号ステップと、
    前記対角化ステップの処理によるパリティ検査行列の対角化、前記確率伝播ステップの処理による確率伝播、前記対数尤度比算出ステップの処理による前記対数尤度比の算出、前記信頼性順探索ステップの処理による前記信頼性順の探索、および前記復号ステップの処理による復号を所定の回数繰り返させるように制御する復号制御ステップと、
    前記復号制御ステップの処理により制御されて行われる繰り返し復号により得られる復号語のリストを作成して第２の保持部に保持させる復号語リスト作成ステップと、
    前記復号語リスト作成ステップの処理により作成された前記復号語リストより復号語を１つ選択する復号語選択ステップと
    を含むことを特徴とする復号方法。
12. 環Ｒ上線形符号に対する復号処理をコンピュータに行わせるプログラムであって、
    供給された符号語および前記符号語の各シンボルの値の信頼性の順序である信頼性順に関する情報を保持する第１の保持部に保持されている前記信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化ステップと、
    前記対角化ステップの処理により対角化された前記パリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播ステップと、
    前記符号語の各シンボルとして、前記確率伝播ステップの処理により行われた確率伝播によって更新された前記メッセージを用いて対数尤度比を算出する対数尤度比算出ステップと、
    前記対数尤度比算出ステップの処理により算出された前記対数尤度比の信頼性順を探索し、前記対数尤度比および前記対数尤度比の信頼性順に関する情報を用いて、前記第１の保持部に保持されている前記符号語および前記信頼性順に関する情報を更新する信頼性順探索ステップと、
    前記対数尤度比算出ステップの処理により算出された前記対数尤度比を用いて復号を行う復号ステップと、
    前記対角化ステップの処理によるパリティ検査行列の対角化、前記確率伝播ステップの処理による確率伝播、前記対数尤度比算出ステップの処理による前記対数尤度比の算出、前記信頼性順探索ステップの処理による前記信頼性順の探索、および前記復号ステップの処理による復号を所定の回数繰り返させるように制御する復号制御ステップと、
    前記復号制御ステップの処理により制御されて行われる繰り返し復号により得られる復号語のリストを作成して第２の保持部に保持させる復号語リスト作成ステップと、
    前記復号語リスト作成ステップの処理により作成された前記復号語リストより復号語を１つ選択する復号語選択ステップと
    を含むことを特徴とするプログラム。

Images