(57)【要約】【課題】より高い復号性能を得ることができるようにする。【解決手段】  既知情報付ABP復号装置３１の既知情報設定部４２は、復号処理を開始する前に、入力部４１を介して取得した情報に基づいて既知シンボルの信頼度に関する既知情報を設定し、それを既知情報保持部４３に保持させる。受信語保持部５１が受信語を保持すると、既知情報付加部５２は、既知情報保持部４３より既知情報を取得し、受信語保持部５１が保持する受信語にその既知情報を付加する。既知情報付ABP復号装置３１の各部は、その既知情報が付加された受信語に対してABPを用いた繰り返し復号を行い、復号語を得る。本発明は、誤り訂正システムに適用することができる。【選択図】図４
2006238127.tif 000002
【特許請求の範囲】
【請求項１】
環Ｒ上線形符号に対する復号処理を行う復号装置であって、
一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持する符号語保持手段と、
前記符号語保持手段により保持される前記符号語に対して、短縮された前記一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加手段と、
前記既知情報付加手段により前記既知情報が付加される前記符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号手段と
を備えることを特徴とする復号装置。
【請求項２】
前記既知情報を設定する既知情報設定手段をさらに備え、
前記既知情報付加手段は、前記既知情報設定手段により設定された前記既知情報を前記符号語に対して付加する
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記既知情報設定手段は、前記既知シンボルに対して十分に高い信頼度を割り当てる
ことを特徴とする請求項２に記載の復号装置。
【請求項４】
前記既知情報設定手段により設定される前記既知情報を保持する既知情報保持手段をさらに備え、
前記既知情報付加手段は、前記既知情報保持手段により保持された前記既知情報を前記符号語に対して付加する
ことを特徴とする請求項２に記載の復号装置。
【請求項５】
前記信頼度は対数尤度比である
ことを特徴とする請求項１に記載の復号装置。
【請求項６】
前記繰り返し復号手段は、
前記既知情報付加手段により前記既知情報が付加される、前記符号語保持手段に保持される前記符号語の各シンボルの値の信頼性の高さの順を探索する第１の信頼性順探索手段と、
前記第１の信頼性順探索手段により探索される前記信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化手段と、
前記対角化手段により対角化された前記パリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播手段と、
前記符号語の各シンボルとして、前記確立伝播手段により行われた確率伝播によって更新された前記メッセージを用いて対数尤度比を算出する対数尤度比算出手段と、
前記対数尤度比算出手段により算出された前記対数尤度比の信頼性順を探索する第２の信頼性順探索手段と、
前記対数尤度比算出手段により算出された前記対数尤度比を用いて復号を行う復号手段と、
前記繰り返し復号を停止するための第１の条件を満たすか否かを判定する第１の判定手段と、
前記繰り返し復号を停止するための第２の条件を満たすか否かを判定する第２の判定手段と、
前記第１の判定手段による第１の判定結果および前記第２の判定手段による第２の判定結果に基づいて、前記第１の信頼性順探索手段による各シンボルの値の信頼性の高さ順の探索、前記対角化手段によるパリティ検査行列の対角化、前記確立伝播手段による確率伝播、前記対数尤度比算出手段による前記対数尤度比の算出、前記第２の信頼性順探索手段による前記信頼性の高さ順の探索、および前記復号手段による復号を所定の停止条件を満たすまで繰り返させるように制御する復号制御手段と
を備えることを特徴とする請求項１に記載の復号装置。
【請求項７】
前記対角化手段は、前記パリティ検査行列の、前記信頼性順の最も低い受信シンボルに対応する列から順に優先的に対角化を行う
ことを特徴とする請求項６に記載の復号装置。
【請求項８】
前記対角化手段は、前記パリティ検査行列の各列を、各列が対応する受信シンボルの信頼性順の低い順に並べ、さらにその順番の一部を所定の方法で並び替え、その並び替えられた順番に前記パリティ検査行列の各列の対角化を行う
ことを特徴とする請求項６に記載の復号装置。
【請求項９】
前記対角化手段は、前記パリティ検査行列の対角化を行う列の優先順位の初期値の決定方法を複数種類予め用意しており、前記優先順位を初期化する度に前記決定方法を変更する
ことを特徴とする請求項６に記載の復号装置。
【請求項１０】
前記復号手段は、前記対数尤度比算出手段により算出された前記対数尤度比を用いて硬判定復号を行う
ことを特徴とする請求項６に記載の復号装置。
【請求項１１】
前記復号手段は、線形符号として有限体Fq（ｑ＝ｐm，ｐ；素数）上代数幾何符号もしくはその同型を用い、複数回の更新により得られた前記信頼性を入力として復号を行う
ことを特徴とする請求項６に記載の復号装置。
【請求項１２】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、前記復号手段は、複数回の更新により得られた前記信頼性を入力としてSudan,Grusuwami-Sudan，若しくは、その他のアルゴリズムによる硬判定リスト復号を行う
ことを特徴とする請求項１１に記載の復号装置。
【請求項１３】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、前記復号手段は、複数回の更新により得られた前記信頼性を入力としてKoetter-Vardy，若しくは、その他のアルゴリズムによる重複度設定および難判定リスト復号を行う
ことを特徴とする請求項１１に記載の復号装置。
【請求項１４】
環Ｒ上線形符号に対する復号処理を行う復号装置の復号方法であって、
一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持部に保持させる保持ステップと、
前記保持ステップの処理により前記保持部に保持される前記符号語に対して、短縮された前記一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加ステップと、
前記既知情報付加ステップの処理により前記既知情報が付加される前記符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号ステップと
を含むことを特徴とする復号方法。
【請求項１５】
環Ｒ上線形符号に対する復号処理をコンピュータに行わせるプログラムであって、
一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持部に保持させる保持ステップと、
前記保持ステップの処理により前記保持部に保持される前記符号語に対して、短縮された前記一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加ステップと、
前記既知情報付加ステップの処理により前記既知情報が付加される前記符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号ステップと
を含むことを特徴とするプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号装置および方法、並びにプログラムに関し、特に、代数的手法を用いた誤り訂正符号技術において復号性能を向上させることができるようにする復号装置および方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来、代数幾何符号、例えばリードソロモン（Reed-Solomon）符号やその部分体部分符号としてのBCH（Bose-Chaudhuri-Hocquenghem）符号に対する復号方法として、その代数的性質を利用した、性能コストおよび計算コストが共に良い方法が知られている。
【０００３】
例えば、符号長ｎ、情報長ｋ、定義体GF(q)(q=pm,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を１／２とする符号で、以下の式（１）に示される３×６行列Ｈをパリティ検査行列として持つような線形符号Ｃを考える。
【０００９】
【数１】
2006238127.tif 000003
【００１０】
このとき、符号空間Ｃは、以下の式（２）により示される。
【００１１】
【数２】
2006238127.tif 000004
【００１２】
ある符号語があるチャネル、例えばBPSK（Binary Phase Shift Keying）変調後に、AWGN（Adaptive White Gaussian Noise）チャネルを通った後、以下の式（３）に示されるような受信語として受信器に受け取られたとする。
【００１３】
【数３】
2006238127.tif 000005
【００１４】
このような場合に受信器の復号装置により実行される復号処理の流れを図１のフローチャートを参照して説明する。
【００１５】
最初に、ステップＳ１において、復号装置は受信語の信頼性順を探索する。復号装置は、受信された受信語より、各受信シンボル（式（３）の右辺の各項）の絶対値の大きさを各受信シンボルの信頼性の高さとし、各受信シンボルについて順位付けを行う。つまり、復号装置は、例えば以下の式（４）の丸で囲まれた数字の様に、各受信シンボルに対して、信頼性の低い順に番号をつける。
【００１６】
【数４】
2006238127.tif 000006
【００１７】
次に、復号装置は、ステップＳ２において、この順位付けされた各受信シンボルを所定の規則に従って並び替え、シンボルの優先順位の順序を変換する。この規則は、後述するように、互いに異なる規則が外側繰り返し回数分予め用意されており、その外側繰り返しの度に異なる方法が選択される。
【００１８】
順序を変換すると復号装置は、次にステップＳ３において、その順序に応じてパリティ検査行列Ｈの対角化を行う。例えば、順序の変換により、各受信シンボルに対してその信頼性の低い順に優先順位を付した場合、復号装置は、パリティ検査行列Ｈに対して、その信頼性の低いシンボルに対応する列より順に対角化を行う。
【００１９】
例えば、各受信シンボルの信頼性順が上述した式（４）に示されるような場合、パリティ検査行列Ｈの、信頼性の最も低いシンボルに対応する列は第３列であり、次に信頼性の低いシンボルに対応する列は第５列であり、その次に信頼性の低いシンボルに対応する列は第１列であり、さらにその次に信頼性の低いシンボルに対応する列は第４列または第６列であり、最も信頼性の高いシンボルに対応する列は第２列となる。復号装置は、その優先順位に従ってパリティ検査行列Ｈの対角化を行う。
【００２０】
すなわち、復号装置は、まず、パリティ検査行列Ｈに対して第３列を要に基本変形を行う。具体的には、復号装置は、第３列を「１００」とするように、第１行と第３行の排他的論理和を第３行とし、パリティ検査行列Ｈを以下の式（５）のように変換する。
【００２１】
【数５】
2006238127.tif 000007
【００２２】
次に、復号装置は、パリティ検査行列Ｈに対して第５列を要に基本変形を行う。具体的には、復号装置は、第５列を「０１０」とするように、第２行と第３行を入れ替え、パリティ検査行列Ｈを以下の式（６）のように変換する。
【００２３】
【数６】
2006238127.tif 000008
【００２４】
次に、復号装置は、パリティ検査行列Ｈに対して第１列を要に基本変形を行う。具体的には、復号装置は、第１列を「００１」とするように、第１行と第３行の排他的論理和を第１行に代入し、第２行と第３行の排他的論理和を第２行に代入し、パリティ検査行列Ｈを以下の式（７）に示されるようなパリティ検査行列Ｈnewに変換する。
【００２５】
【数７】
2006238127.tif 000009
【００２６】
なお、対角化を試みた列がそれ以前に対角化した列と線形従属であった場合、復号装置は、その列をそのまま残し次の順位の列で対角化を試みる。この様にして、復号装置は、パリティ検査行列Ｈのランク分対角化を行い、新たなパリティ検査行列Ｈnewを得る。そして、復号装置は、ステップＳ４において、その得られたパリティ検査行列Ｈnewを用いて確率伝播による信頼性の更新を行う。
【００２７】
図２は式（７）に示されるパリティ検査行列Ｈnewに対応するタナーグラフである。確率伝播（belief propagation）はタナーグラフのエッジに沿ってメッセージを行き来させることによって実現される。図２において、バリアブルノード（variable node）１１乃至バリアブルノード１６は、行列（図２の場合パリティ検査行列Ｈnew）の各列に対応するノードである。チェックノード（check node）２１乃至チェックノード２３は、行列（図２の場合パリティ検査行列Ｈnew）の各行に対応するノードである。
【００２８】
以下において、ｉおよびｊを自然数とし、第ｉ番目のバリアブルノードから第ｊ番目のチェックノードへのメッセージをＲi,jと称し、第ｊ番目のチェックノードから第ｉ番目のバリアブルノードへのメッセージをＱi,jと称し、第ｉ番目のバリアブルノードに連接するチェックノードのインデックス集合をＪ(ｉ)と称し、第ｊ番目のチェックノードに連接するバリアブルノードのインデックス集合をＩ(ｊ)と称する。
【００２９】
このとき、メッセージＲi,jおよびメッセージＱi,jの更新式はそれぞれ以下の式（８）および式（９）の様になる。
【００３０】
【数８】
2006238127.tif 000010
【００３１】
式（９）において、係数θはVertical Step Damping Factorと呼ばれる収束係数であり、その値は０＜θ≦１である。メッセージＱi,jの初期値としては受信シンボルｙjが設定され、外部情報（Extrinsic Information）
【００３２】
【数９】
2006238127.tif 000011
の更新は、以下の式（１０）により行われる。
【００３３】
【数１０】
2006238127.tif 000012
【００３４】
つまり、復号装置は、図１のステップＳ５において、各符号シンボルの対数尤度比（LLR：LogLikelihood Ratio）Λqを以下の式（１１）のように算出する。
【００３５】
【数１１】
2006238127.tif 000013
【００３６】
式（１１）において、係数α1は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は、以下の式（１２）のように表される。
【００４５】
【数１２】
2006238127.tif 000014
【００４６】
このとき、復号装置は、例えば、パリティ検査行列Ｈと硬判定結果ｄの積の値が０（Ｈ・ｄ＝＝０）であるか、または、繰り返し数ｔが最大繰り返し回数Ｎ以上（ｔ≧Ｎ）であること（少なくともいずれか一方を満たすこと）を繰り返し復号停止条件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
【発明の開示】
【発明が解決しようとする課題】
【００４９】
例えば、通信等の規格として採用される誤り訂正システムにおけるリードソロモン符号は、その符号長が実際に通信する必要のある情報の情報長に対して設定されたものであり、２nの符号長で符号化する原始的なリードソロモン符号の短縮符号が用いられることが多い。
【００５０】
しかしながら、以上のような、従来のAdaptive Belief Propagationを用いた手法は、受信語のみの信頼性を用いて復号を行う手法であり、受信されないシンボルを持つ短縮符号の短縮部分の扱いには対応しておらず、また、符号語のある部分のシンボルが既知であったとしても、その既知情報を利用することはしていない。
【００５１】
このような誤り訂正システムにおいて、エラーの生起を低減させる、より高性能な復号方法が求められているという課題があった。
【００５２】
本発明はこのような状況に鑑みてなされたものであり、短縮された符号語を受信語として受信し、Adaptive Belief Propagationによって更新された信頼性を用いて繰り返し復号を行う際に、デコーダエラー生起確率が抑制され、より高い復号性能を得ることができるようにするものである。
【課題を解決するための手段】
【００５３】
本発明の復号装置は、一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持する符号語保持手段と、符号語保持手段により保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加手段と、既知情報付加手段により既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号手段とを備えることを特徴とする。
【００５４】
前記既知情報を設定する既知情報設定手段をさらに備え、既知情報付加手段は、既知情報設定手段により設定された既知情報を符号語に対して付加するようにすることができる。
【００５５】
前記既知情報設定手段は、既知シンボルに対して十分に高い信頼度を割り当てるようにすることができる。
【００５６】
前記既知情報設定手段により設定される既知情報を保持する既知情報保持手段をさらに備え、既知情報付加手段は、既知情報保持手段により保持された既知情報を符号語に対して付加するようにすることができる。
【００５７】
前記信頼度は対数尤度比であるようにすることができる。
【００５８】
前記繰り返し復号手段は、既知情報付加手段により既知情報が付加される、符号語保持手段に保持される符号語の各シンボルの値の信頼性の高さの順を探索する第１の信頼性順探索手段と、第１の信頼性順探索手段により探索される信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化手段と、対角化手段により対角化されたパリティ検査行列を用いて確率伝播を行いメッセージを更新する確率伝播手段と、符号語の各シンボルとして、確立伝播手段により行われた確率伝播によって更新されたメッセージを用いて対数尤度比を算出する対数尤度比算出手段と、対数尤度比算出手段により算出された対数尤度比の信頼性順を探索する第２の信頼性順探索手段と、対数尤度比算出手段により算出された対数尤度比を用いて復号を行う復号手段と、繰り返し復号を停止するための第１の条件を満たすか否かを判定する第１の判定手段と、繰り返し復号を停止するための第２の条件を満たすか否かを判定する第２の判定手段と、第１の判定手段による第１の判定結果および第２の判定手段による第２の判定結果に基づいて、第１の信頼性順探索手段による各シンボルの値の信頼性の高さ順の探索、対角化手段によるパリティ検査行列の対角化、確立伝播手段による確率伝播、対数尤度比算出手段による対数尤度比の算出、第２の信頼性順探索手段による信頼性の高さ順の探索、および復号手段による復号を所定の停止条件を満たすまで繰り返させるように制御する復号制御手段とを備えるようにすることができる。
【００５９】
前記対角化手段は、パリティ検査行列の、信頼性順の最も低い受信シンボルに対応する列から順に優先的に対角化を行うようにすることができる。
【００６０】
前記対角化手段は、パリティ検査行列の各列を、各列が対応する受信シンボルの信頼性順の低い順に並べ、さらにその順番の一部を所定の方法で並び替え、その並び替えられた順番にパリティ検査行列の各列の対角化を行うようにすることができる。
【００６１】
前記対角化手段は、パリティ検査行列の対角化を行う列の優先順位の初期値の決定方法を複数種類予め用意しており、優先順位を初期化する度に決定方法を変更するようにすることができる。
【００６２】
前記復号手段は、対数尤度比算出手段により算出された対数尤度比を用いて硬判定復号を行うようにすることができる。
【００６３】
前記復号手段は、線形符号として有限体Fq（ｑ＝ｐm，ｐ；素数）上代数幾何符号もしくはその同型を用い、複数回の更新により得られた信頼性を入力として復号を行うようにすることができる。
【００６４】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてSudan,Grusuwami-Sudan，若しくは、その他のアルゴリズムによる硬判定リスト復号を行うようにすることができる。
【００６５】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてKoetter-Vardy，若しくは、その他のアルゴリズムによる重複度設定および難判定リスト復号を行うようにすることができる。
【００６６】
本発明の復号方法は、一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持部に保持させる保持ステップと、保持ステップの処理により保持部に保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加ステップと、既知情報付加ステップの処理により既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号ステップとを含むことを特徴とする。
【００６７】
本発明のプログラムは、一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持部に保持させる保持ステップと、保持ステップの処理により保持部に保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加ステップと、既知情報付加ステップの処理により既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号ステップとを含むことを特徴とする。
【００６８】
本発明の復号装置および方法、並びにプログラムにおいては、一部のシンボルが省略されることにより符号長が短縮化された符号語が取得されて保持され、その保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度が、既知情報として付加され、その既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号が行われる。
【発明の効果】
【００６９】
本発明によれば、代数的手法を用いた誤り訂正符号技術を実現することができる。特に、デコーダエラー生起確率が抑制されるようにすることができ、より高い復号性能を得ることができる。
【発明を実施するための最良の形態】
【００７０】
以下に本発明の実施の形態を説明するが、本明細書に記載の発明と、発明の実施の形態との対応関係を例示すると、次のようになる。この記載は、請求項に記載されている発明をサポートする実施の形態が本明細書に記載されていることを確認するためのものである。従って、発明の実施の形態中には記載されているが、発明に対応するものとして、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その発明に対応するものではないことを意味するものではない。逆に、実施の形態が発明に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その発明以外の発明には対応しないものであることを意味するものでもない。
【００７１】
さらに、この記載は、本明細書に記載されている発明の全てを意味するものではない。換言すれば、この記載は、本明細書に記載されている発明であって、この出願では請求されていない発明の存在、すなわち、将来、分割出願されたり、補正により追加されたりする発明の存在を否定するものではない。
【００７２】
本発明においては、環Ｒ上線形符号に対する復号処理を行う復号装置（例えば、図３の既知情報付ABP復号装置）が提供される。この復号装置では、一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持する符号語保持手段（例えば、図３の受信語保持部）と、符号語保持手段により保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加手段（例えば、図３の既知情報付加部）と、既知情報付加手段により既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号手段（例えば、図３の信頼性順探索部乃至外側繰り返し復号停止判定部）とを備える。
【００７３】
前記既知情報を設定する既知情報設定手段（例えば、図３の既知情報設定部）をさらに備え、既知情報付加手段は、既知情報設定手段により設定された既知情報を符号語に対して付加するようにすることができる。
【００７４】
前記既知情報設定手段は、既知シンボルに対して十分に高い信頼度を割り当てるようにすることができる。
【００７５】
前記既知情報設定手段により設定される既知情報を保持する既知情報保持手段（例えば、図３の既知情報保持部）をさらに備え、既知情報付加手段は、既知情報保持手段により保持された既知情報を符号語に対して付加するようにすることができる。
【００７６】
前記信頼度は対数尤度比であるようにすることができる。
【００７７】
前記繰り返し復号手段は、既知情報付加手段により既知情報が付加される、符号語保持手段に保持される符号語の各シンボルの値の信頼性の高さの順を探索する第１の信頼性順探索手段（例えば、図３の信頼性探索部）と、第１の信頼性順探索手段により探索される信頼性順に関する情報に基づいて、パリティ検査行列の対角化を行う対角化手段（例えば、図３のパリティ検査行列対角化部）と、対角化手段により対角化されたパリティ検査行列を用いて確率伝播を行い、メッセージを更新する確率伝播手段（例えば、図３の確率伝播部）と、符号語の各シンボルとして、確立伝播手段により行われた確率伝播によって更新されたメッセージを用いて対数尤度比を算出する対数尤度比算出手段（例えば、図３のLLR算出部）と、対数尤度比算出手段により算出された対数尤度比の信頼性順を探索する第２の信頼性順探索手段（例えば、図３のLLR信頼性順探索部）と、対数尤度比算出手段により算出された対数尤度比を用いて復号を行う復号手段（例えば、図３の復号部）と、繰り返し復号を停止するための第１の条件を満たすか否かを判定する第１の判定手段（例えば、図３の内側繰り返し復号停止判定部）と、繰り返し復号を停止するための第２の条件を満たすか否かを判定する第２の判定手段（例えば、図３の外側繰り返し復号停止判定部）と、第１の判定手段による第１の判定結果および第２の判定手段による第２の判定結果に基づいて、第１の信頼性順探索手段による各シンボルの値の信頼性の高さ順の探索、対角化手段によるパリティ検査行列の対角化、確立伝播手段による確率伝播、対数尤度比算出手段による対数尤度比の算出、第２の信頼性順探索手段による信頼性の高さ順の探索、および復号手段による復号を所定の停止条件を満たすまで繰り返させるように制御する復号制御手段（例えば、図３の復号制御部）とを備えるようにすることができる。
【００７８】
前記対角化手段は、パリティ検査行列の、信頼性順の最も低い受信シンボルに対応する列から順に優先的に対角化を行う（例えば、図６のステップＳ４４）ようにすることができる。
【００７９】
前記対角化手段は、パリティ検査行列の各列を、各列が対応する受信シンボルの信頼性順の低い順に並べ、さらにその順番の一部を所定の方法で並び替え、その並び替えられた順番にパリティ検査行列の各列の対角化を行う（例えば、図６のステップＳ４３）ようにすることができる。
【００８０】
前記対角化手段は、パリティ検査行列の対角化を行う列の優先順位の初期値の決定方法を複数種類予め用意しており、優先順位を初期化する度に決定方法を変更する（例えば、図６のステップＳ４３）ようにすることができる。
【００８１】
前記復号手段は、対数尤度比算出手段により算出された対数尤度比を用いて硬判定復号を行う（例えば、図６のステップＳ４８）ようにすることができる。
【００８２】
前記復号手段は、線形符号として有限体Fq（ｑ＝ｐm，ｐ；素数）上代数幾何符号もしくはその同型を用い、複数回の更新により得られた信頼性を入力として復号を行う（例えば、図６のステップＳ４８）ようにすることができる。
【００８３】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてSudan,Grusuwami-Sudan，若しくは、その他のアルゴリズムによる硬判定リスト復号を行う（例えば、図６のステップＳ４８）ようにすることができる。
【００８４】
前記代数幾何符号としてのリードソロモン符号、BCH符号、若しくはそれらの同型に対して、復号手段は、複数回の更新により得られた信頼性を入力としてKoetter-Vardy，若しくは、その他のアルゴリズムによる重複度設定および難判定リスト復号を行う（例えば、図６のステップＳ４８）ようにすることができる。
【００８５】
本発明においては、環Ｒ上線形符号に対する復号処理を行う復号装置の復号方法が提供される。この復号方法においては、一部のシンボルが省略されることにより符号長が短縮化された符号語を取得して保持部に保持させる保持ステップ（例えば、図５のステップＳ２４）と、保持ステップの処理により保持部に保持される符号語に対して、短縮された一部のシンボルであり、既知の値により構成される既知シンボルの信頼度を、既知情報として付加する既知情報付加ステップ（例えば、図６のステップＳ４１）と、既知情報付加ステップの処理により既知情報が付加される符号語に対して、確率伝播を用いた繰り返し復号を行う繰り返し復号ステップ（例えば、図６のステップＳ４３乃至ステップＳ５０）とを含む。
【００８６】
本発明のプログラムにおいても、各ステップが対応する実施の形態（但し一例）は、本発明の復号方法と同様である。
【００８７】
以下、本発明の実施の形態について図を参照して説明する。
【００８８】
図３は、本発明を適用した復号装置の構成例を示すブロック図である。
【００８９】
図３に示される既知情報付ABP（Adaptive Belief Propagation）復号装置３１は、短縮された符号語が送信される誤り訂正システムの復号装置であり、その短縮された符号語（送信されたシンボル）を受信語として受信し、その受信語に、符号語の短縮された部分（未送信のシンボル）を付加し、それ（符号語全体）をAdaptive Belief Propagationを用いた手法で復号する装置である。詳細については後述するが、既知情報付ABP復号装置３１は、供給（受信）された受信語（送信されたシンボルの受信値（信頼度））に、短縮された部分（未送信のシンボル）の信頼度を付加して、その全体についてAdaptive Belief Propagationを用いた手法で復号する。
【００９０】
このとき、受信語の各シンボルの正しい値（送信前の値）は未知の値である。これに対して、その受信語に付加される未送信のシンボルは、例えば「０」等の所定の値により構成される。つまり、この未送信のシンボルの正しい値（送信前の値）は既知である。従って、以下において、受信語のシンボルを未知シンボルと称し、受信語に付加する未送信のシンボルを既知シンボルと称することもある。また、この既知シンボルの信頼度（受信語に付加する情報）を既知情報と称することもある。
【００９１】
なお、受信語の各未知シンボルの値の絶対値の大きさは、その信頼性の高さ（信頼度）を表すことになる。つまり、値が正の場合、絶対値が大きいほど「より『１』らしい」ということになり、値が負の場合、絶対値が大きいほど「より『０』らしい」ということになる。これに対して、既知シンボルはその正しい値が既知であるので、その信頼度は基本的に十分に高い値に設定される。
【００９２】
既知情報付ABP復号装置３１は、図３に示されるように、入力部４１、既知情報設定部４２、既知情報保持部４３、受信語保持部５１、既知情報付加部５２、信頼性探索部５３、順序変換部５４、パリティ検査行列対角化部５５、確率伝搬部５６、LLR（LogLikelihood Ratio：対数尤度比）算出部５７、LLR信頼性順探索部５８、復号部５９、内側繰り返し復号停止判定部６０、復号制御部６１、および外側繰り返し復号停止判定部６２を有している。
【００９３】
入力部４１は、例えば、キーボード等の入力デバイスや外部入力端子等よりなり、復号処理が開始される前に、外部より供給される、既知シンボルに関する情報を入力情報として受け付け、その入力情報を既知情報設定部４２に供給する。つまり、入力部４１は、既知シンボルのビット数や各既知シンボルに割り当てる信頼度の値やその割り当て方法等の情報を外部より受け付け、それらの情報を既知情報設定部４２に供給する。なお、入力部４１の代わりに、半導体メモリ等の記録媒体よりなる記憶部を設け、その記憶部に上述したような既知シンボルに関する情報を予め記憶させ、必要に応じてその情報を既知情報設定部４２に供給させるようにしてもよい。
【００９４】
既知情報設定部４２は、入力部４１より供給される情報（既知シンボルに関する情報）に基づいて、受信語に付加する既知情報を設定し、それを既知情報保持部４３に供給する。既知情報保持部４３は、半導体メモリ等の記録媒体を有しており、既知情報設定部４２より供給される既知情報を一時的に保持し、要求に応じて、その既知情報を既知情報付加部５２に供給する。
【００９５】
受信語保持部５１は、既知情報付ABP復号装置３１の外部より供給される受信語（未知シンボル）を取得し、一時的に保持する。また、受信語保持部５１は、既知情報付加部５２により、保持している受信語に対して既知情報が付加されると、その既知情報が付加された受信語を一時的に保持する。また、受信語保持部５１は、信頼性順探索部５３により、その既知情報が付加された受信語の各シンボルに対して信頼性の高さ（受信値の絶対値の大きさ）に応じた所定の方法で優先順位付けが行われると、各シンボルに対応させてその優先順位の情報を保持する。さらに、受信語保持部５１は、LLR信頼性順探索部５８より、更新された各シンボルの信頼度（LLR）やその信頼性順（優先順位）の情報が供給されると、それらの情報を保持する（保持する情報を更新する）。受信語保持部５１は、そのように保持されている各シンボルの優先順位の情報を順序変換部５４またはパリティ検査行列対角化部５５に供給する。
【００９６】
既知情報付加部５２は、既知情報保持部４３に保持されている既知情報を取得すると、それを受信語保持部５１に保持されている受信語に付加し、それを受信語保持部５２に保持させる。
【００９７】
信頼性順探索部５３は、受信語保持部５１に保持されている、既知情報が付加された受信語の各シンボルに対して、その絶対値の大きさに応じて所定の方法で信頼性の順位付けを行う。例えば、信頼性順探索部５２は、絶対値が大きいシンボルほどより信頼性が高いシンボルとし、信頼性の低い方から順に（絶対値が小さい方から順に）各シンボルに優先順位を付ける。
【００９８】
順序変換部５４は、復号制御部６１に制御され、受信語保持部５１より供給される、既知情報が付加された受信語（の各シンボル）の優先順位の情報を、所定のアルゴリズムで変換し、並び替えを行う。つまり、順序変換部５４は、予め複数用意された所定の方法の内、復号制御部６１により選択された方法で、受信語（各受信シンボル）の優先順位を変換し、その変換した情報をパリティ検査行列対角化部５５に供給する。
【００９９】
パリティ検査行列対角化部５５は、復号制御部６１に制御され、順序変換部５４より供給された優先順序変換後の各シンボルの優先順位の情報、または、受信語保持部５１より供給される、既知情報が付加された受信語の各シンボルの優先順位の情報のいずれか一方に基づいて、パリティ検査行列Ｈの列の対角化を行う。パリティ検査行列対角化部５５は、その対角化後のパリティ検査行列Ｈnewを確率伝播部５６に供給する。
【０１００】
確率伝播部５６は、パリティ検査行列対角化部５５より供給されるパリティ検査行列Ｈnewを用いて確率伝播を行い、メッセージを更新し、それをLLR算出部５７に供給する。LLR算出部５７は、供給されたメッセージに基づいてLLRを算出し、LLRの更新を行う。LLR算出部５７は、その更新されたLLRをLLR信頼性順探索部５８に供給する。LLR信頼性順探索部５８は、LLR算出部５７において更新されたLLRの信頼性順を探索し、その情報（更新済みのLLRやその信頼性順に関する情報）を受信語保持部５２および復号部５９に供給する。
【０１０１】
復号部５９は、供給されたLLRを復号する。なお、復号部５９による復号方法は、例えば、限界距離復号、硬判定復号、またはK-Vリスト復号等であってもよく、それ以外のどのような方法であってもよい。復号部５９は、復号を１回行う度に、そのこと（復号結果）を内側繰り返し復号停止判定部６０に通知する。そして、内側繰り返し復号停止条件SC１および外側繰り返し復号停止条件SC２の両方を満たすと、復号部５９は、繰り返し復号を終了し、最後の復号により得られた復号語を既知情報付ABP復号装置３１の外部に出力する。
【０１０２】
内側繰り返し復号停止判定部６０は、復号部５９により繰り返し行われる内側繰り返し復号を停止するか否かを判定する処理を行う。内側繰り返し復号停止判定部６０は、その内部に半導体メモリ等の記録媒体を有しており、予め定められた所定の内側繰り返し復号停止条件SC１を記憶している。また、内側繰り返し復号停止判定部６０は、内部にカウンタを有しており、復号部５９による内側繰り返し復号の回数をカウントする。内側繰り返し復号停止判定部６０は、さらに、そのカウント値（これまでに行われた内側繰り返し復号の回数に関する情報）や、復号部５９の復号により得られた復号語の値等に基づいて、内部に記憶している内側繰り返し復号停止条件SC１が満たされたか否か（内側繰り返し復号を停止するか否か）を判定し、その判定結果を復号制御部６１に供給する。内側繰り返し復号を停止する場合、内側繰り返し復号停止判定部６０は、復号制御部６１に制御され、内部のカウンタのカウント値をリセットする。
【０１０３】
復号制御部６１は、既知情報付ABP復号部３１の各部を制御し、既知情報が付加された受信語に対してAdaptive Belief Propagationを用いた繰り返し復号を繰り返し実行するように制御する。
【０１０４】
例えば、復号制御部６１は、内側繰り返し復号停止判定部６０より供給される判定結果に基づいて、順序変換部５４、パリティ検査行列体格化部５５、内側繰り返し復号停止判定部６０、または外側繰り返し復号停止判定部６２等を制御する。
【０１０５】
より具体的に説明すると、例えば、内側繰り返し復号停止判定部６０により、内側繰り返し復号を停止しないと判定された場合、復号制御部６１は、パリティ検査行列対角化部５５を制御し、受信語保持部５１より各シンボルの優先順位の情報を取得させ、パリティ検査行列の対角化に関する処理を実行させる。
【０１０６】
また、例えば、内側繰り返し復号停止判定部６０により、内側繰り返し復号を停止すると判定された場合、復号制御部６１は、順序変換部５４を制御し、受信語保持部５１より各シンボルの優先順位の情報を取得させ、その優先順位の情報を変換させ、それをパリティ検査行列対角化部５５に供給させる。また、復号制御部６１は、パリティ検査行列対角化部５５に、その順序変換部５４より供給される優先順位の情報に基づいてパリティ検査行列の対角化に関する処理を実行させる。さらに、復号制御部６１は、内側繰り返し復号停止判定部６０を制御し、その内部のカウンタのカウント値をリセットさせる。また、復号制御部６１は、外側繰り返し復号停止判定部６２を制御し、外側繰り返し復号の回数をカウントさせるとともに、その外側繰り返し復号を停止するか否かを判定させる。
【０１０７】
また、それ以外にも、復号制御部６１は、例えば、外側繰り返し復号停止判定部６２より供給される判定結果に基づいて、外側繰り返し復号停止判定部６２等を制御する。
【０１０８】
より具体的に説明すると、例えば、外側繰り返し復号停止判定部６２により、外側繰り返し復号を停止すると判定された場合、復号制御部６１は、外側繰り返し復号停止判定部６２を制御し、その内部のカウンタのカウント値をリセットさせるとともに、復号部５９への通知処理を行わせる。そして、復号制御部６１は、既知情報付ABP復号装置３１の各部を制御し、その受信語に対する復号処理を終了させる。
【０１０９】
外側繰り返し復号停止判定部６２は、復号部５９により繰り返し行われる外側繰り返し復号を停止するか否かを判定する処理を行う。外側繰り返し復号停止判定部６２は、その内部に半導体メモリ等の記録媒体を有しており、予め定められた所定の外側繰り返し復号停止条件SC２を記憶している。また、外側繰り返し復号停止判定部６２は、内部にカウンタを有しており、復号部５９による外側繰り返し復号の回数をカウントする。外側繰り返し復号停止判定部６２は、さらに、そのカウント値（これまでに行われた内側繰り返し復号の回数に関する情報）や、復号部５９の復号により得られた復号語の値等に基づいて、内部に記憶している外側繰り返し復号停止条件SC２が満たされたか否か（外側繰り返し復号を停止するか否か）を判定し、その判定結果を復号制御部６１に供給する。
【０１１０】
例えば、外側繰り返し復号停止判定部６２は、内側繰り返し復号が停止される度に、復号制御部６１に制御され、内部のカウンタのカウント値をインクリメントし（外側繰り返し復号の回数をカウントし）、外側繰り返し復号停止条件SC２が満たされるか否かを判定し、その判定結果を復号制御部６１に供給する。外側繰り返し復号を停止する場合、外側繰り返し復号停止判定部６２は、復号制御部６１に制御され、内部のカウンタのカウント値をリセットするとともに、復号部５９に、内側繰り返し復号停止条件SC１および外側繰り返し復号停止条件SC２が満たされることを通知し、復号語を出力させる。
【０１１１】
つまり、既知情報付ABP復号装置３１は、受信語の各シンボルの受信値に、既知シンボルの信頼度からなる既知情報を付加してその全体について復号処理を行う。従って、例えば、２3＝８個のシンボルが６個のシンボルに短縮リードソロモン符号化された符号語が受信語として受信される場合、既知情報付ABP復号装置３１の既知情報付加部５２は、２個の既知シンボルの信頼度を既知情報として受信語に付加する。
【０１１２】
このときのタナーグラフは、図２のタナーグラフに対して、図４に示されるようになる。つまり受信語に対するバリアブルノード（variable node）１１乃至バリアブルノード１６に既知情報に対するバリアブルノード７１およびバリアブルノード７２が付加される。すなわち、受信語に既知情報を付加するためにパリティ検査行列の列数も変更され、新たな列が付加される。
【０１１３】
これにより、タナーグラフには、点線で示される図２と同様のエッジに加えて、実線で示されるバリアブルノード７１およびバリアブルノード７２に対するエッジが追加される。確率伝播部５６は、これらの新たなエッジを含む全てのエッジに沿ってメッセージを行き来させる。
【０１１４】
次に、以上のような既知情報付ABP復号装置による処理の流れについて説明する。
【０１１５】
最初に、復号処理の前に行われる既知情報設定処理について図５のフローチャートを参照して説明する。
【０１１６】
例えば、ユーザの指示等に基づいて既知情報設定処理が開始されると、最初に入力部４１は、ステップＳ２１において、受信する符号語における短縮されるシンボルに関する情報を取得する。入力部４１は、符号化装置より伝送路を介して取得する受信語に含まれない符号語（短縮され伝送されない部分）、すなわち、既知シンボルに関する情報の入力を受け付け、それを取得する。例えば、入力部４１には、既知シンボルのシンボル数（ビット数）や、各既知シンボルの値等の情報が、外部の装置より供給されたり、またはユーザにより入力されたりする。入力部４１は、それらを受け付け、取得する。
【０１１７】
また、ステップＳ２２において、入力部４１は、ステップＳ２１の場合と同様に供給される、既知シンボルに対する信頼度の割り当て方法に関する情報を取得する。例えば、入力部４１は、どの既知シンボルにどのような値の信頼度を割り当てるかを決定する、信頼度の割り当て方法（その割り当てる値も含む）に関する情報を取得する。
【０１１８】
ステップＳ２３において、既知情報設定部４２は、ステップＳ２１およびステップＳ２２の処理により、入力部４１により取得された既知シンボルに関する情報および既知シンボルに対する信頼度の割り当て方法に関する情報に基づいて、短縮される各シンボル（各既知シンボル）に対して信頼度を割り当てる。ステップＳ２４において既知情報保持部２４は、その割り当てられた信頼度の情報を既知情報として保持し、既知情報設定処理を終了する。
【０１１９】
次に、以上のように設定された既知情報を用いて復号処理を行う復号処理について、図６のフローチャートを参照して説明する。
【０１２０】
受信語が既知情報付ABP復号装置３１に供給され、受信語保持部５１がその受信語を保持すると、復号処理が開始される。復号処理が開始されると、最初に、位置情報付加部５２は、ステップＳ４１において、既知情報保持部４３に保持されている既知情報を取得し、それを受信語保持部５１に保持されている受信語に付加する。
【０１２１】
受信語に既知情報が付加されると、既知情報付ABP復号装置３１の各部は、その既知情報が付加された受信語に対して、図１のフローチャートの場合と同様の復号処理を行う。すなわち、既知情報付ABP復号装置３１の各部は、図１のステップＳ１乃至ステップＳ９のそれぞれにおいて、受信語に対して行う処理と同様に、既知情報が付加された受信語に対して図６のステップＳ４２乃至ステップＳ５０の処理を行う。
【０１２２】
つまり、受信語に既知情報が付加されると、信頼性順探索部５２は、ステップＳ４２において、受信語保持部４２に保持されているその既知情報が付加された受信語（すなわちLLR）に対して各シンボルの信頼性順を探索する。
【０１２３】
ステップＳ４３において、順序変換部５４は、その信頼性順（パリティ検査行列における各シンボルに対応する列に割り当てられる対角化の優先順位、すなわち、対角化を行う順序）を変換する。パリティ検査行列対角化部５５は、ステップＳ４４において、各シンボルに割り当てられた信頼性順（対角化の優先順位）に応じてパリティ検査行列の対角化を行う。
【０１２４】
ステップＳ４５において、確率伝播部５６は、その対角化が行われたパリティ検査行列を用いて確率伝播を行ってメッセージを更新し、ステップＳ４６において、LLR算出部５７は、その更新されたメッセージに基づいて、各シンボルの新たなLLRを算出する（LLRを更新する）。ステップＳ４７において、LLR信頼性順探索部５８は、その新たなLLRの信頼性順を探索し、受信語保持部５１に保持される情報を更新する。
【０１２５】
ステップＳ４８において、復号部５９は、LLR算出部５７により求められた新たなLLRを復号し、復号語を得る。ステップＳ４９において、内側繰り返し復号停止判定部６０は、内側繰り返し復号停止条件SC１を満たすか否かを判定することにより、内側繰り返し復号を停止するか否かを判定する。そして、内側繰り返し復号停止条件SC１を満たさない（内側繰り返し復号を停止しない）と判定した場合、内側繰り返し復号停止判定部６０は、復号制御部６１に制御され、処理をステップＳ４４に戻し、それ以降の処理を繰り返す。つまり、既知情報付ABP復号装置３１は、ステップＳ４４乃至ステップＳ４９の処理を繰り返すことにより、内側繰り返し復号を行う。
【０１２６】
ステップＳ４９において、内側繰り返し復号停止条件SC１を満たす（内側繰り返し復号を停止する）と判定した場合、内側繰り返し復号停止判定部６０は、復号制御部６１に制御され、内側繰り返し復号を停止し、カウンタをリセットする等した後、処理をステップＳ５０に進める。
【０１２７】
ステップＳ５０において、外側繰り返し復号停止判定部６２は、外側繰り返し復号停止条件SC２を満たすか否かを判定することにより、外側繰り返し復号を停止するか否かを判定する。そして、外側繰り返し復号停止条件SC２を満たさない（外側繰り返し復号を停止しない）と判定した場合、外側繰り返し復号停止判定部６２は、復号制御部６１に制御され、処理をステップＳ４３に戻し、それ以降の処理を繰り返す。つまり、既知情報付ABP復号装置３１は、ステップＳ４３乃至ステップＳ５０の処理を繰り返すことにより、外側繰り返し復号を行う。
【０１２８】
ステップＳ５０において、外側繰り返し復号停止条件SC２を満たす（外側繰り返し復号を停止する）と判定した場合、外側繰り返し復号停止判定部６２は、復号制御部６１に制御され、外側繰り返し復号を停止し、カウンタをリセットしたり、復号部５９において得られた復号語を出力させたり等した後、復号処理を終了する。既知情報付ABP復号装置３１は、以上のような復号処理を受信した各受信語に対して行う。
【０１２９】
次に以上の処理を具体的な例を用いて説明する。例えば、有限体
【０１３０】
【数１３】
2006238127.tif 000015
上における線形符号ｃとして符号長２０４、情報長１８８のリードソロモン符号であるRS(204,188)に対する復号処理を行う場合について説明する。このときの、符号の生成多項式を以下の式（１３）のようにする。
【０１３１】
【数１４】
2006238127.tif 000016
【０１３２】
また、情報語は以下の式（１４）のようにする。
【０１３３】
【数１５】
2006238127.tif 000017
【０１３４】
さらに、情報多項式を以下の式（１５）のようにする。
【０１３５】
【数１６】
2006238127.tif 000018
【０１３６】
このとき、組織的符号化による符号語を以下の式（１６）のように表す。
【０１３７】
【数１７】
2006238127.tif 000019
【０１３８】
この符号語に対応する符号多項式は以下の式（１７）で与えられる。
【０１３９】
【数１８】
2006238127.tif 000020
【０１４０】
なお、式（１７）において、関数q(x)はそれぞれ関数f(x)x16を関数g(x)で割ったときの商であり、関数p(x)はそのときの余りである。
【０１４１】
このようなRS(204,188)は、原始的なリードソロモン符号のRS(255,239)の５１シンボルに値「０」を充当した符号語と情報語のリードソロモン符号とみなすことができる。すなわち、情報語は以下の式（１８）のように表すことができる。
【０１４２】
【数１９】
2006238127.tif 000021
【０１４３】
この場合、後半の第１８９番目のシンボルf188から第２３９番目のシンボルf238までの５１シンボルに値「０」が充当されている。また、符号語は、以下の式（１９）のように表すことができる。
【０１４４】
【数２０】
2006238127.tif 000022
【０１４５】
この場合、後半の第２０５番目のシンボルｃ204から第２５５番目のシンボルｃ254までの５１シンボルに値「０」が充当されている。つまり、RS(255,239)の情報語の一部のシンボルに値「０」を充当して符号化を行うことにより、以下の式（２０）に示されるような１８８シンボルの実質的な情報語を符号長２０４の符号語に符号化する（短縮符号化する）場合と等価になる。
【０１４６】
【数２１】
2006238127.tif 000023
【０１４７】
つまり、以上のような短縮符号化の結果として、式（２０）に示される情報語が符号化された、以下の式（２１）に示される符号長２０４の符号語が得られる。
【０１４８】
【数２２】
2006238127.tif 000024
【０１４９】
このように短縮符号化を実現する符号化装置は、値「０」を充当した５１シンボルについては送信せずに、この式（２１）で示される符号語（短縮符号化された２０４シンボル分）のみを、伝送路を介して復号装置に送信する。
【０１５０】
この短縮化された符号語（式（２１））は、ガロア体GF（２8）をガロア体GF（２）上の８次元ベクトル空間とし、各シンボルを８ビットに展開することができる。すなわち、式（２１）で示される符号語は、以下の式（２２）に示される１６３２ビットの列に展開される。
【０１５１】
【数２３】
2006238127.tif 000025
【０１５２】
符号化装置が、この式（２２）のγをBPSK（Binary Phase Shift Keying）変調後、分散σのAWGN（Adaptive White Gaussian Noise）チャネル上に送信した場合、復号装置（例えば、既知情報付ABP復号装置３１）において受信される受信語ｙは、以下の式（２３）に示される。
【０１５３】
【数２４】
2006238127.tif 000026
【０１５４】
この受信語から算出される各符号シンボルの対数尤度比（LLR）Λは、以下の式（２４）のように表される。
【０１５５】
【数２５】
2006238127.tif 000027
【０１５６】
既知情報付ABP復号装置３１は、以上の受信語だけでなく、短縮部分についてもAdaptive Belief Propagationを行う。短縮された５１シンボル分は以下の式（２５）で示される。
【０１５７】
【数２６】
2006238127.tif 000028
【０１５８】
この式（２５）の短縮部分の各シンボルを上述した受信語の場合と同様にそれぞれ８ビットに展開すると、以下の式（２６）に示されるような列が得られる。
【０１５９】
【数２７】
2006238127.tif 000029
【０１６０】
式（２６）の各シンボルの値は全て「０」である（「０」であることは既知である）。従って、既知情報付ABP復号装置３１の既知情報設定部４２は、この式（２６）に示される短縮部分（既知シンボル）に対応する信頼性Λを、例えば、十分に大きな実数Ｍを用いて、以下の式（２７）のように設定する（図５のステップＳ２３の処理）。
【０１６１】
【数２８】
2006238127.tif 000030
【０１６２】
既知情報付ABP復号装置３１の既知情報付加部５２は、このような式（２７）で示される既知情報（短縮部分に対応する４０８ビット分の信頼性）を受信語に対応する１６３２ビット分の信頼性に付加し、合計２０４０ビット分の信頼性とする（図６のステップＳ４１）。既知情報付ABP復号装置３１の各部は、図６のステップＳ４２以降の処理を実行することにより、この２０４０ビットの線形符号に対する信頼性についてAdaptive Belief Propagation復号を行う。
【０１６３】
図７は、以上のように短縮リードソロモン符号RS（204,188）を従来のABP復号方法（Adaptive Belief PropagationとK-Vリスト復号の組み合わせ）で復号する場合の復号性能と、上述した本発明を適用したABP復号方法（受信語に短縮部分の情報を付加してからAdaptive Belief PropagationとK-Vリスト復号の組み合わせにより復号を行う方法）により復号する場合の復号性能の比較を示すグラフである。
【０１６４】
図７において、曲線８１で示されるグラフが、従来のABP復号方法を用いた場合の復号性能を示しており、曲線８２で示されるグラフが、本発明を適用したABP復号方法を用いた場合の復号性能を示している。図７に示されるように、本発明を適用したABP復号方法の場合（曲線８２）、従来のABP復号方法の場合（曲線８１）に対して縦軸で示されるフレームエラー率（FER）が低下しており、エラー訂正能力が向上していることがわかる。なお、この短縮化のサイズを大きくするほど（短縮部分のビット数を増やすほど）、より復号性能は向上する。
【０１６５】
以上のように、既知情報付ABP復号装置３１は、短縮された既知シンボルについて十分に大きな信頼度を割り当て、その信頼度を既知情報として、受信語の信頼度に付加し、その全体についてABPを用いた復号処理を行うことにより、エラー生起確率が抑制されるようにすることができ、より高い復号性能を得ることができる。
【０１６６】
なお、短縮部分に充当するLLR（受信語に付加する既知シンボルのLLR）は、全て同じ値である必要はなく、例えば、シンボル毎に互いに異なる値（信頼度）を割り当てるようにしてもよい。また、一部のシンボルにのみ異なる信頼度を割り当てるようにしてもよい。
【０１６７】
また、短縮前の符号語内において、短縮部分のシンボル列が連続的に分布していなくてもよく、どのシンボルが短縮化されるようにしても良い。また、符号化処理毎にその短縮化される位置が異なるようにしてもよく、毎回任意の箇所で短縮化される（任意のシンボルが短縮化される）ようにしてもよい。ただし、その短縮化されたシンボルの位置に関する情報は、復号装置において既知である必要がある。例えば、既知情報付ABP復号装置３１は、受信語を受信する前にその既知シンボルの位置に関する情報を、入力部４１を介して取得するようにする。既知情報付加部５２は、この情報に基づいて各既知シンボルを付加する位置を特定する。このようにすることにより、既知情報付加部５２は、短縮前の符号語の任意の位置が短縮された場合であっても、各既知シンボルを受信語の正しい位置（元のシンボル位置）に付加することができる。
【０１６８】
さらに、既知情報付ABP復号装置３１は、Adaptive Belief Propagationを用いて繰り返し復号を行い、LLRを更新する度に、既知シンボルの信頼度を十分大きな値に再設定するようにしてもよい。つまり、繰り返し復号におけるLLRの更新による既知シンボルの低下を抑制するようにしてもよい。
【０１６９】
また、復号部５９は、繰り返し復号において、LLR算出部５７において算出された新たなLLRを用いて復号を行うが、その際、受信語のシンボルに対応するLLRだけでなく、既知シンボルに対応するLLRも含めて復号処理を行うようにしてもよい。さらに、その復号の際に、得られた復号語と既知情報との整合性を調査し、その調査結果に基づいて復号の成否を判定するようにしてもよい。例えば、短縮部分に既知シンボルとして値「０」を設定したにも関わらず、復号結果としてその既知シンボルの値が「０」以外のものになった場合、それを復号語候補から外すようにしてもよい。
【０１７０】
さらに、送信側の符号化方法が例えば符号位置符号化であっても、既知情報付ABP復号装置３１は、上述した復号方法により、符号語を復号することができる。また、符号化方法がリードソロモン符号でなくてもよく、符号位置符号化されたリードソロモン符号とｎ×ｎの対角正則行列で写り合う様な符号化方法であれば、既知情報付ABP復号装置３１は、上述した復号方法により、符号語を復号することができる。
【０１７１】
次に、以上のような既知情報付ABP復号の誤り訂正システムへの適用方法の具体的な例について説明する。図８は、本発明の既知情報付ABP復号を誤り訂正システムに適用する場合の例について説明する図である。図８において、誤り訂正システム１００は、符号化装置１０１、チャネル１０２、および復号装置１０３により構成されるテレビジョン放送等に利用されるデジタル信号送受信システムである。
【０１７２】
符号化装置１０１は、例えば放送局等のような、デジタル信号であるテレビジョン信号を送信する送信装置として構成される。符号化装置１０１は、リードソロモン符号化部（RS符号化部）１１１、インタリーバ１１２、および畳み込み符号化部１１３を有し、情報語を短縮符号化し、それを、チャネル１０２を介して複合装置１０３に送信する。
【０１７３】
RS符号化部１１１は、入力された情報語を、リードソロモン符号を用いて短縮符号化し、所定のシンボル数の符号語を出力する。インタリーバ１１２は、入力された符号語の並べ替えを行い、それを出力する。畳み込み符号化部１１３は、入力された符号語に対して畳み込み符号を行って出力する。
【０１７４】
符号化装置１０１の外部より供給された送信用のデジタル情報は、符号化装置１０１のRS符号化部１１１において、リードソロモン符号化された後、インタリーバ１１２に供給される。インタリーバ１１２は、主に通信路であるチャネル１０２において発生するバースト的誤りを拡散させるために、情報の並べ替え（インタリービング）を行う。リードソロモン符号は、複数ビットを１シンボルとする誤り訂正を行うので、インタリーバ１１２は、シンボル単位でバースト的誤りを拡散するシンボルインタリービングを行う。
【０１７５】
並べ替えが行われた送信用のデジタル情報は、さらに、畳み込み符号化部１１３において、複数の情報ブロックに基づいて逐次的に符号系列が定まる畳み込み符号が行われる。例えば、拘束長Ｋの畳み込み符号化部１１３は、インタリーバ１１２よりデジタル情報がｋビットの情報ブロック毎に供給されると、今回供給された情報ブロックだけでなく、過去に供給された情報ブロックも含めたＫ個の情報ブロックに基づいて、ｎビットの符号ブロックに符号化する。
【０１７６】
そして、畳み込み符号化されたデジタル情報は、図示せぬ通信部を介して、送信可能なデータ形式に変換され、送信語として、チャネル１０２上に送出される。つまり、符号化装置１０１は、供給されたテレビジョン信号を符号化して送信（放送）する。その送信された送信語は、チャネル１０２を介して復号装置１０３に供給される。すなわち、チャネル１０２は、このテレビジョン信号が伝送される有線または無線の伝送路である。
【０１７７】
復号装置１０３は、例えば、放送局（符号化装置１０１）より送信（放送）されるテレビジョン信号を受信する受信装置（デジタルテレビジョン受像機等）として構成される。復号装置１０３は、畳み込み復号部１２１、デインタリーバ１２２、および既知情報付ABP復号部１３１を有している。
【０１７８】
畳み込み復号部１２１は、入力に対して、例えばBCJR（Bahl, Cocke, Jelinek, and Raviv）アルゴリズムやSOVA（Soft Output Viterbi Algorithm）による復号等に代表される、畳み込み符号の軟判定復号を行い、得られた復号語を出力する。デインタリーバ１２２は、並べ替えられた情報を元の順序に戻す。既知情報付ABP復号部１３１は、図３に示される既知情報付ABP復号装置３１を誤り訂正システム１００に適応させたものであり、基本的に既知情報付ABP復号装置３１と同様の構成を有しており、同様の処理を行う。従って、既知情報付ABP復号部１３１の構成および処理内容は、上述した既知情報付ABP復号装置３１の説明を適用することができるので、その詳細な説明を省略するが、既知情報付ABP復号部１３１は、デインタリーバ１２２より供給された情報（並べ替えられた軟判定復号結果）に対して既知情報を付加し、ABP繰り返し復号処理を行い、得られた復号語を出力する。
【０１７９】
復号装置１０３は、受信したテレビジョン信号を復号する。すなわち、復号装置１０３は、図示せぬ通信部を介して、チャネル１０２上を伝送された送信語を受信する。受信された送信語（すなわち、受信語）は、畳み込み復号部１２１に供給され、畳み込み符号の軟判定復号が行われる。デインタリーバ１２２は、その畳み込み復号された受信語を取得すると、符号化装置１０１のインタリーバ１１２において行われたインタリービングに対応した方法で情報の並び替えを行い、並び替えられた情報を元の順序に戻す処理（デインタリービング）を行う。既知情報付ABP復号部１３１は、上述した方法で、元の順序に戻されたデジタル情報に対して、既知情報を付加し、ABP繰り返し復号を行い、ABPによる信頼性の更新後、硬判定後限界距離復号、リスト復号、もしくは、軟値をそのまま入力として軟判定リスト復号を行う。そして、既知情報付ABP復号部１３１は、得られた復号語（符号化装置１０１において符号化される前のデジタル情報を再現したもの）を、復号装置１０３の外部に出力する。
【０１８０】
以上のようにして、図６の誤り訂正システム１００において、復号装置１０３は、受信語に既知情報を付加してから繰り返し復号を行うことにより、容易に、性能の良い復号処理を行うことができ、より正確な通信を行うことができる。
【０１８１】
なお、誤り訂正システム１００において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、BCH符号を適用するようにしてもよいし、それ以外の符号化方法を適用するようにしてもよい。
【０１８２】
図９は、本発明の既知情報付ABP復号を誤り訂正システムに適用する場合の他の例について説明する図である。図９において、誤り訂正システム１５０は、符号化装置１５１、チャネル１５２、および復号装置１５３により構成されるシステムであり、例えば、ディジタルテレビ等のデジタル通信システムに用いられるシステムである。
【０１８３】
符号化装置１５１は、図８の符号化装置１０１と同様の装置であり、符号化装置１０１と基本的に同様の構成を有し、同様の処理を行う。すなわち、符号化装置１５１は、短縮リードソロモン符号化を行うRS符号化部１１１、順番を並び替えるインタリーバ１１２、および畳み込み符号化を行う畳み込み符号化部１１３を有する。それらについての説明は符号化装置１０１の場合と同様であるので省略する。
【０１８４】
チャネル１５２は、図８のチャネル１０２と同様であり、テレビジョン信号が伝送される有線または無線の伝送路である。
【０１８５】
復号装置１５３は、畳み込み復号部１６１、デインタリーバ１２２、既知情報付ABP復号部１３１、およびインタリーバ１１２を有している。畳み込み復号部１６１は、図示せぬ通信部を介して受信した受信語（符号化装置１５１より送信され、チャネル１５２を介して伝送された送信語）を取得すると、その受信語に対して、例えば、BCJRアルゴリズムやSOVA等を用いて、軟判定復号を行う。そして、畳み込み復号部１６１は、この軟判定復号された受信語をデインタリーバ１２２に供給する。また、畳み込み復号部１６１には、インタリーバ１１２より、既知情報付ABP復号部１３１において既知情報付ABP繰り返し復号が行われた復号語が再度並び替えられて符号語として供給される。畳み込み復号部１３１は、この符号語に対しても、図示せぬ通信部より供給された受信語の場合と同様に、例えば、BCJRアルゴリズムやSOVA等を用いて、軟判定復号を行い、デインタリーバ１２２に供給する。
【０１８６】
デインタリーバ１２２は、図６の復号装置１０３の場合と同様に動作し、畳み込み復号部１６１より供給される軟判定復号結果の並べ替えを行い、その並べ替え結果を既知情報付ABP復号部１３１に供給する。
【０１８７】
既知情報付ABP復号部１３１は、図６の復号装置１０３の場合と同様に動作し、デインタリーバ１２２より供給される情報（並べ替えられた軟判定復号結果）に対して既知情報を付加し、既知情報付ABP繰り返し復号処理を行い、得られた復号語を出力する。また、既知情報付ABP復号部１３１は、その得られた復号語をインタリーバ１１２に供給する。
【０１８８】
インタリーバ１１２は、符号化装置１５１の場合と同様に動作し、既知情報付ABP復号部１３１より供給される情報（復号語）を所定の順番に並び替える。このインタリーバ１１２による並べ替えのパターンは、符号化装置１５１の場合と同様である。このようにして並べ替えられたデジタル情報は、再び畳み込み復号部１６１に供給される。
【０１８９】
以上のように、復号装置１５３は、図示せぬ通信部において取得した受信語に対して、デインタリーバ１２２とインタリーバ１１２を介しながら、畳み込み復号部１６１による軟判定復号と、既知情報付ABP復号部１３１による既知情報付繰り返し復号とを繰り返し行い、復号処理における復号誤り確率を小さくしていく。なお、この復号装置１５３全体の復号の繰り返し回数は、予め定められていてもよいし、例えば、誤り訂正する箇所の数等のような所定の条件に基づいて、繰り返しを中止するか否かが判定されるようにしてもよい。
【０１９０】
このように図９の誤り訂正システム１５０において、復号装置１５３は、容易に、性能の良い復号処理を行うことができ、より正確な通信を行うことができる。
【０１９１】
なお、誤り訂正システム１５０において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、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復号部２３１−１において第１次元目に関する復号処理を行う。復号装置２０３は、このようにして復元した元のデジタル情報を記録再生装置（誤り訂正システム２００）の外部に出力する。
【０２００】
このようにすることにより、誤り訂正システム２００の復号装置２０３は、容易に性能の良い復号処理を行うことができる。つまり、記録再生装置としての誤り訂正システム２００は、より正確にデジタル情報の記録および再生を行うことができる。
【０２０１】
なお、誤り訂正システム２００において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、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を用いた繰り返し復号処理を行い、復号されたデジタル情報を次の復号部に供給する。このようにして、順にｍ番目の復号部２６１−ｍまで復号処理が続けられる。復号部２６１−ｍにおける復号処理が完了すると、復号装置２５３は、その復号されたデジタル情報を記録再生装置（誤り訂正システム２５０）の外部に出力する。
【０２１１】
このようにすることにより、復号装置２５３は、容易に性能の良い復号処理を行うことができ、記録再生装置としての誤り訂正システム２５０は、より正確にデジタル情報の記録および再生を行うことができる。
【０２１２】
なお、誤り訂正システム２５０において、リードソロモン符号を用いるように説明したが、これに限らず、例えば、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復号部，  ２５０  誤り訂正システム，  ２５１  符号化装置，  ２５２  チャネル，  ２５３  復号装置，  ２６１−１乃至２６１−ｍ  復号部，  ３００  パーソナルコンピュータ
【図１】
2006238127.tif 000031
【図２】
2006238127.tif 000032
【図３】
2006238127.tif 000033
【図４】
2006238127.tif 000034
【図５】
2006238127.tif 000035
【図６】
2006238127.tif 000036
【図７】
2006238127.tif 000037
【図８】
2006238127.tif 000038
【図９】
2006238127.tif 000039
【図１０】
2006238127.tif 000040
【図１１】
2006238127.tif 000041
【図１２】
2006238127.tif 000042