(57)【要約】      （修正有）【課題】変換されたＧＰＣ行列が、所定の復号方法、即ち、事前確率伝播（ＡＰＰ）復号またはビリーフ伝播（ＢＰ）復号に基づく符号化方法で、より良好な性能を発揮することを目的とする。【解決手段】方法は、線形ブロック２元符号を表す汎用パリティチェック行列を変換する。まず、入力汎用パリティチェック行列が、線形ブロック２元符号について定義される。補助集合が、入力汎用パリティチェック行列から形成され、半順序集合に編成される。それぞれの補助集合の部分集合が、リストに順序付けられ、パリティチェック方程式が、順序付けられた部分集合のリストから構築される。このパリティチェック方程式は、出力汎用パリティチェック行列に変換される。この出力汎用パリティチェック行列は、線形ブロック２元符号に従って符号化されたメッセージを復号するために使用することができる。【選択図】図１
2004274709.tif 000002
【特許請求の範囲】
【請求項１】
線形ブロック２元符号を表す汎用パリティチェック行列を変換する方法であって、
前記線形ブロック２元符号についての、入力汎用パリティチェック行列を定義することと、
前記入力汎用パリティチェック行列から補助集合を形成することと、
それぞれの補助集合の部分集合をリストに順序付けることと、
前記順序付けられた部分集合のリストからパリティチェック方程式を構築することと、
前記パリティチェック方程式を、出力汎用パリティチェック行列に変換することと、
前記線形ブロック２元符号に従って符号化されたメッセージを、前記出力汎用パリティチェック行列によって復号することと
を含む方法。
【請求項２】
前記入力汎用パリティチェック行列は、Ｍ行×Ｎ列を有し、かつ（ｎ，ｋ）線形ブロック２元符号を表し、前記出力汎用パリティチェック行列は、Ｍ’行×Ｎ’列を有し、Ｎ’はＮよりも大きい、請求項１に記載の方法。
【請求項３】
前記補助集合は、制約集合、共通集合、および単一ビット集合を含む請求項１に記載の方法。
【請求項４】
前記入力汎用パリティチェック行列の各行について、各制約集合を形成するために、該行において１であるビットの集合を取り出すことをさらに含む請求項３に記載の方法。
【請求項５】
前記制約集合の対から前記共通集合を形成することをさらに含む請求項３に記載の方法。
【請求項６】
以前に形成された共通集合の対から共通部分を形成することをさらに含む請求項５に記載の方法。
【請求項７】
２ビットより少ないビットを含むあらゆる共通集合を廃棄することをさらに含む請求項３に記載の方法。
【請求項８】
前記入力汎用パリティチェック行列の単一ビットの可能なすべての集合から前記単一ビット集合を形成することをさらに含む請求項３に記載の方法。
【請求項９】
前記それぞれの補助集合の部分集合の順序付けは、前記補助部分集合の子から開始し、次に他の部分集合から開始する、請求項１に記載の方法。
【請求項１０】
前記子および他の部分集合の順序付けは、大きな部分集合から小さな部分集合に向かって行われる、請求項１に記載の方法。
【請求項１１】
対応するパリティチェック方程式を構築するために、ある特定の補助集合のあらゆるビットを含む共通部分のない部分集合の１つまたは２つ以上の集まりを求めることをさらに含む請求項１に記載の方法。
【請求項１２】
それぞれのパリティチェック方程式は、前記出力ＧＰＣ行列の行に対応する、請求項１に記載の方法。
【請求項１３】
選択されたパリティチェック方程式を廃棄することをさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、データの記憶およびデータの送信のための誤り訂正符号の分野に関し、より具体的には、復号方法のための汎用パリティチェック行列の取得に関する。
【背景技術】
【０００２】
データの記憶および通信の分野における基本的な問題は、誤り訂正符号（ＥＣＣ）の実用的な復号方法の開発である。これについては、Lin等著の「Error Control Coding: Fundamentals and Applications」Prentice Hall: Englewood Cliffs, NJ, 1983、Peterson等著の「Error-Correcting Codes」2nd edition, MIT Press: Cambridge, Mass., 1972、およびMacWilliams等著の「The Theory of Error-Correcting Codes」North-Holland: New York, NY, 1977を参照されたい。
【０００３】
重要な部類のこのような復号方法は、事後確率伝播（ＡＰＰ）復号方法、および「和積」復号方法としても知られているビリーフ伝播（ＢＰ）復号方法によって例示される従来技術の繰り返し復号方法を含む。他の関連する多種多様な復号方法は、ＡＰＰ復号方法またはＢＰ復号方法の簡略化、またはそれ以外の変更に基づいている。これらの復号方法に関する論文を集めたものは、「Special Issue on Codes on Graphs and Iterative Algorithms」IEEE Transactions on Information Theory, 47(2), February 2001に収録されている。
【０００４】
これらの復号方法は、汎用パリティチェック（ＧＰＣ）行列によって特定される符号の表現を使用する。これについては、Mackay著の「Relationships between Sparse Graph Codes」Proceedings of IBIS 2000を参照されたい。これらの方法の復号性能は、通常、符号を表すために使用されるＧＰＣ行列に依存する。
【０００５】
２元線形ブロック誤り訂正符号の基本定義
「符号」へのあらゆる言及は、ここでは特に、２元線形ブロック誤り訂正符号を意味する。これらの符号の背景にある基本的なアイデアは、Ｎビットのブロックを用いてｋビットのメッセージを符号化することである。ここで、Ｎ＞ｋである。追加されるＮ−ｋビットは、破損したメッセージを復号するために使用される。破損は、記憶媒体の故障または送信チャネルのノイズによって引き起こされる可能性がある。
【０００６】
符号Ｃは、ビット長Ｎを有する符号語の２ｋ個の可能なブロックの集合によって定義される。パラメータＮおよびｋを有する符号は、しばしば（Ｎ，ｋ）符号と呼ばれる。符号は、通常、Ｎおよびｋが大きい場合に、はるかに効果的になる。しかしながら、パラメータＮおよびｋのサイズが増加するに伴い、破損したメッセージの復号の難しさも増加する。
【０００７】
汎用パリティチェックＧＰＣ行列
任意の２つの符号語の２を法とする和も符号語である場合に、その２元ブロック符号は「線形」である。例えば、１１１０１００および０１１１０１０の２を法とする和は、１００１１１０である。２元ブロック符号が線形である場合に、任意の２つの符号語の２を法とする和は、別の符号語を形成する。線形符号は、汎用パリティチェック（ＧＰＣ）行列によって表すことができる。実際には、線形符号は、多くの異なるＧＰＣ行列によって表すことができる。
【０００８】
（ｎ，ｋ）符号を表すＧＰＣ行列は、Ｍ行およびＮ列を有する１および０からなる行列によって定義される。ここで、Ｎ≧ｎである。ＧＰＣ行列の列は、最初のｎ列が、符号のｎビットに対応するように配置される。残りのＮ−ｎ列は、符号の定義を助ける「状態変数ビット」に対応する。これらの状態変数ビットは、時として、「隠れビット」または「補助ビット」と呼ばれる。ｎの値は、ＧＰＣ行列を用いて符号を完全に特定するために、Ｍ行×Ｎ列の行列と共に特定されなければならない。
【０００９】
ＧＰＣ行列の各行は、パリティチェック制約を表す。ある特定の行によって表される制約に含まれるビットは、その行において１を有する列に対応する。パリティチェック制約は、２を法とする和が求められた場合に、ビットの和が偶数、すなわち０でなければならないことを強制する。例えば、Ｎ＝７のＧＰＣ行列は次のようになる。
【００１０】
【数１】
2004274709.tif 000003
【００１１】
このＧＰＣ行列は、次の３つの制約を表す。
【００１２】
【数２】
2004274709.tif 000004
【００１３】
ここで、変数ｘｉは、第ｉビットの値を表し、０または１の値であることができる。下記のシンボルは、２を法とする和を表す。
【００１４】
【数３】
2004274709.tif 000005
【００１５】
このＧＰＣ行列は、よく知られているハミング（７，４）符号を表す１つの方法である。この符号は、本発明によって以下に変換される符号の例として使用される。
【００１６】
ＧＰＣ行列によって表されるＭ個の異なる制約の中には、線形従属となり得るものがある。（１）式および（５）式によって与えられるＧＰＣ行列では、すべての制約が、線形独立である。同じ符号についての別の表現は、Ｎ＝ｎ＝７のＧＰＣ行列である。
【００１７】
【数４】
2004274709.tif 000006
【００１８】
このＧＰＣ行列において、最後の４行は、最初の３行の組み合わせを加算することによって得ることができる。これは、最後の４行が冗長な制約にすぎず、実際には３つの線形独立の行のみが存在することを暗に意味する。例えば、第４行は、最初の２行を加算することにより得ることができる。このＧＰＣ行列については、３つの線形独立の行が存在する。（ｎ，ｋ）符号のＮ行×Ｍ列のＧＰＣ行列の表現には、一般に、Ｎ−ｋ個の線形独立の行が存在する。
【００１９】
（１）式および（５）式で与えられるＧＰＣ行列は、隠れビットを一切使用しなかった。隠れビットを使用し、かつ同じ符号を表す別のＧＰＣ行列は、Ｎ＝１１で、かつｎ＝７のＧＰＣ行列である。
【００２０】
【数５】
2004274709.tif 000007
【００２１】
ＧＰＣ行列に基づく復号方法
上述したように、ＧＰＣ行列による符号の表現を使用する従来技術の復号方法は、事後確率伝播（ＡＰＰ）復号方法、ビリーフ伝播（ＢＰ）、および「和積」復号方法を含む。同じ符号が２つの異なるＧＰＣ行列を用いて表される場合に、これらの復号方法の性能も異なる。
【００２２】
多くの場合、復号方法の性能は、最尤（ＭＬ）法を使用する最適な復号器と比較して測定される。ＭＬ復号器は、２ｋ個の可能なすべての符号語をスキャンし、送信された確率の最も高い符号語を選択する。しかしながら、ＭＬ復号方法は、ｋが大きい場合には実用的ではない。
【００２３】
一般的に言うと、ＢＰ復号方法は、計算の複雑さのコストを除いて、ＡＰＰ復号方法よりも幾分性能が良い。これらの方法に基づく他の復号方法は、通常、性能と複雑さと間の同様のトレードオフを伴うが、分類として、これらの復号方法は、Ｎおよびｋが大きな符号に対して実用的であるとみなされる。
【００２４】
一般に、ＢＰ復号方法およびＡＰＰ復号方法に基づく繰り返し復号法、またはＢＰ復号方法およびＡＰＰ復号方法に類似の繰り返し復号法は、次の制約、すなわち、各行における１の数が少ないこと、行の数が多いこと、および行列内の任意の２つの行について、双方の行において１を有する列の数が少ないこと、すなわち理想的には０または１であること、を満たすＧＰＣ行列によるＭＬ復号にかなり近い性能を有する。
【００２５】
多くの符号、例えば、Gallagerによって「Low-density parity check codes」Vol.21, Research Monograph Series, MIT Press, 1963に最初に記載された低密度パリティチェック（ＬＤＰＣ）符号、またはKhandkar等によって「Irregular Repeat-Accumulate Codes」2nd International Symposium on Turbo codes and Related Topics, pp. 1-8, 2000に記載された不規則繰り返し累積（ＩＲＡ）符号は、それらのＧＰＣ行列が可能な限りこれらの特性を有するように設計される。ＢＰ復号方法およびＡＰＰ復号方法は、これらの符号に対してかなりよく機能する。
【００２６】
いくつかの符号、例えば、一段多数決論理復号可能符号は、他の基準を用いるように設計されたが、ＢＰ復号またはＡＰＰ復号に適当なＧＰＣ行列表現を有する。ＢＰ復号方法およびＡＰＰ復号方法の性能は、これらの符号に対しても良好である。これについては、Lucas等著の「Iterative Decoding of One-Step Majority Logic Decodable Codes Based on Belief Propagation」IEEE Transactions on Communications, vol. COM-48, pp. 931-937, 2000を参照されたい。
【００２７】
例えばBose-Chaudhuri-Hocquenghen（ＢＣＨ）符号、ならびにユークリッド幾何学または射影幾何学に基づく符号といった他の古典的な符号も、ＭＬ復号でよく機能し、既知のＧＰＣ行列表現を有する。しかしながら、これらの古典的な符号に対する既知のＧＰＣ行列表現は、上記３つの制約を満たさず、したがって、繰り返し復号方法の性能は劣る。
【００２８】
したがって、符号のＧＰＣ行列表現を、同じ符号の別のＧＰＣ行列表現に変換する方法が必要とされている。より具体的には、変換されたＧＰＣ行列が、繰り返し復号方法と共に使用される場合に、元の行列よりも良好に機能するようにＧＰＣ行列表現を変換することが望まれている。
【発明の開示】
【発明が解決しようとする課題】
【００２９】
本発明は、線形ブロック２元符号を表す、入力汎用パリティチェック（ＧＰＣ）行列を、同一の符号を表す出力ＧＰＣ行列に変換する方法を提供する。本発明の目的は、変換されたＧＰＣ行列が、所定の復号方法、例えば、事前確率伝播（ＡＰＰ）復号またはビリーフ伝播（ＢＰ）復号に基づく符号化方法で、より良好な性能を発揮することである。
【課題を解決するための手段】
【００３０】
入力ＧＰＣ行列は、Ｍ行およびＮ列を有する。行列のすべてのエントリは、１または０である。列は、符号の送信されるビットまたは状態変数ビットを表し、行は、ビット間のパリティチェック制約を表す。
【００３１】
この変換方法は、まず、入力ＧＰＣ行列から、３つの異なる、ビットの「補助集合」を形成する。この補助集合は、「制約」集合、「共通」集合、および「単一ビット」集合を含む。ビットの制約集合は、入力ＧＰＣ行列のパリティチェックに従うように制約される。共通集合は、制約集合の対の共通部分から形成される。単一ビット集合は、入力ＧＰＣ行列の単一のビットから形成される。
【００３２】
この変換の第２ステップは、補助集合を編成し、それぞれのビットの集合について、その集合のすべての部分集合をリストにする。
【００３３】
この変換方法の第３ステップでは、パリティチェック方程式が、出力ＧＰＣ行列に対して構築される。
【００３４】
第４ステップでは、それぞれのビットの集合に対して少なくとも１つのパリティチェック方程式が残っている限り、得られたパリティチェック方程式のいくつかが、廃棄され得る。
【００３５】
最後に、この変換方法の第５ステップでは、残っているパリティチェック方程式が、出力ＧＰＣ行列に変換される。次に、この出力ＧＰＣ行列は、入力ＧＰＣ行列を用いることによって可能な性能よりも良好な性能でメッセージを復号するために使用され得る。
【発明を実施するための最良の形態】
【００３６】
図１は、本発明による、誤り訂正符号（ＥＣＣ）についての汎用パリティチェック行列を変換する方法１００のステップを示している。本方法１００では、まず、（ｎ，ｋ）符号１１２を表すＭ×Ｎの入力ＧＰＣ行列Ｈ１１１を定義する（１１０）。変換１００は、同一の符号１１２を表すＭ’×Ｎ’の出力ＧＰＣ行列Ｈ’１６１を生成する。値Ｎ’は、値Ｎよりも大きい。この理由は、元の表現に使用されるすべての変数をそのままにし、かつ、状態変数ビットを加えるからである。出力行列１６１は、元の入力行列１１１が使用された場合に得られるであろう性能よりも良好な性能でメッセージ１７１を復号する（１７０）ために使用することができる。
【００３７】
本方法のステップ１２０は、３つの、異なるビットの補助集合Ｓ１２１を形成する。これら３つの補助集合は、入力ＧＰＣ行列１１１の列に対応するＮビットの集合の全パリティを表す。１からＮの整数でＮビットをインデックスする。第ｉビットの値をｘｉによって示す。ここで、ｘｉは、値０または値１を取ることができる。ビットの任意の補助集合Ｓ１２１に対して、この補助集合Ｓのビットの２を法とする和を表すために、表記ｘｓを用いている。例えば、ｘ１＝１、ｘ２＝０、およびｘ３＝１の場合に、ｘ｛１，２，３｝は、次のようになる。
【００３８】
【数６】
2004274709.tif 000008
【００３９】
明らかに、ｘｓ＝０は、集合Ｓのビットの和が、偶数であることを意味する。この和を、集合Ｓのパリティと呼ぶ。一方、ｘｓ＝１は、集合Ｓのパリティが奇数であることを意味する。
【００４０】
我々が形成する状態変数ビットのすべては、入力行列１１１の元のＮビットの集合から導出される。実際には、本方法において、３つの異なる種類のビットの補助集合を使用する。これらの異なる集合を「制約集合」１２２、「共通集合」１２３、および「単一ビット」集合１２４と呼ぶ。ＧＰＣ行列を用いてこれらの異なる補助集合を形成する手順を説明する。
【００４１】
【数７】
2004274709.tif 000009
【００４２】
この行列は、我々が、前に紹介したものであり、ハミング（７，４）符号を表す。
【００４３】
制約集合
制約補助集合１２２は、次のように形成される。入力行列Ｈ１１１の各行について、その行の１であるビットの集合を取り出す。本例では、第１行から集合｛１，２，３，５｝を、第２行から｛２，３，４，６｝を、および第３行から｛３，４，５，７｝を得る。ＧＰＣ行列の定義により、あらゆる制約集合Ｓ１２２についてｘｓ＝０であることを知る。
【００４４】
共通集合
制約集合１２２の対から共通補助集合１２３を形成する。本例では、｛１，２，３，５｝と｛２，３，４，６｝との共通部分から共通集合｛２，３｝を、｛１，２，３，５｝と｛３，４，５，７｝との共通部分から共通集合｛３，５｝を、および｛２，３，４，６｝と｛３，４，５，７｝との共通部分から共通集合｛３，４｝を得る。２ビットより少ないビットを含むあらゆる共通集合を廃棄する。可能な場合には、前に形成された共通集合の対の共通部分を形成し、前に得られたあらゆる集合または２ビットより少ないビットを含むあらゆる集合を廃棄することにより、新たな共通集合を得る。新たな共通集合を得ることができなくなるまで、前に得られた共通集合の共通部分を用いて共通集合を形成し続ける。
【００４５】
共通集合１２３のいくつかを、この段階で廃棄することができる。共通集合のいくつかを廃棄し、出力ＧＰＣ行列１６１が管理可能なサイズであることを確実にすることが望ましい場合がある。残っている共通集合は、最終的には、出力ＧＰＣ行列Ｈ’１６１に使用される新しい状態変数ビットに対応する。
【００４６】
単一ビット集合
入力ＧＰＣ行列Ｈ１１１のＮビットのうちの１ビットだけを含む可能なすべての集合を形成することにより、単一ビット補助集合１２４を得る。本例では、単一ビット集合｛１｝、｛２｝、｛３｝、｛４｝、｛５｝、｛６｝、および｛７｝を得る。
【００４７】
集合の編成およびリスト化
ステップ１３０では、制約集合１２２、共通集合１２３、および単一ビット集合１２４を、図２に示すように、補助集合の半順序集合Ｐ２００に編成する。図２において、連結されている補助集合は、親子関係によって関係付けられ、子の上に親が描かれている。Ｐにおけるビットの補助集合Ｓが、Ｐにおける別のビットの補助集合Ｔの部分集合である場合に、Ｓ＜Ｔを記載する。Ｓ＜Ｔであり、かつＳ＜Ｕ＜Ｔとなるような他の集合ＵがＰにおいて存在しない場合には、ＳがＴの「子」であるといい、ＴがＳの「親」であるという。本例では、集合｛１，２，３，５｝は、集合｛２，３｝および集合｛１｝の親である。しかし、｛２｝＜｛２，３｝＜｛１，２，３，５｝であるので、集合｛１，２，３，５｝は、｛２｝の親ではない。この部分集合の関係は、Ｐの要素の半順序を生ずる。半順序集合の背景については、R. P. Stanley著の「Enumerative Combinatorics, Vol. 1」, Cambridge University Press, 1986を参照されたい。
【００４８】
制約集合および共通集合のそれぞれについて、その集合のすべての部分集合をリストにする。本方法の好ましい実施の形態では、このリストは、子を他の部分集合の前に列挙することにより編成される。本方法の好ましい実施の形態では、まず、子の集合および他の部分集合の中で、より大きな集合を列挙する。本例では、図３に示すリスト３００を得る。
【００４９】
出力ＧＰＣ行列のパリティチェック方程式の構築
ステップ１４０では、順序付けられたリスト３００を用いて、ビットの各制約集合および各共通集合についての少なくとも１つのパリティチェック方程式を構築する。このステップは、これら２つの集合について同様である。唯一の相違は、制約集合Ｓについて、我々がｘｓ＝０であることを知っていることであり、それを利用する。
【００５０】
各制約集合および各共通集合について、その集合のあらゆるビットを含む共通部分のない部分集合の１つまたは２つ以上の集まりを求める。本方法の好ましい実施の形態では、次の手順を用いてこれを行う。集合について、部分集合のリスト２００の最初の子から開始する。例えば、集合｛１，２，３，５｝について、最初の子は｛２，３｝である。集合からそれらのビットを除去する。例えば、ビット１および５を残す。次に、残っているビットの部分集合を含むリスト上の最初の部分集合、例えば部分集合１を求めることを試みる。再び、その集合からそれらのビットを除去し、すべてのビットが、交わらない部分集合を成すまで繰り返す。本例では、次の方程式を得る。
【００５１】
【数８】
2004274709.tif 000010
【００５２】
この式から、対応するパリティチェック方程式として次の方程式を得る。
【００５３】
【数９】
2004274709.tif 000011
【００５４】
本方法の好ましい実施の形態では、先行するパリティチェックの１つにまだ含まれていない、リストの中の次の子に進み、上記手順を繰り返すことによって、それぞれの集合についての付加的な冗長パリティチェックを求めることを試みる。本例では、次の方程式を得る。
【００５５】
【数１０】
2004274709.tif 000012
【００５６】
あらゆる子が、１つまたは２つ以上のパリティチェックに含まれるまで続ける。図４は、本例の出力行列について構築されたパリティチェック方程式４００を示している。
【００５７】
２を法とする計算の下では、すべての変数が、それらの負のものと等しいので、共通集合を用いて導出された方程式を標準形式に再構成できることに留意されたい。この標準形式は、方程式の左辺にパリティの和を有し、右辺にゼロを有する。本例では、次の方程式を得る。
【００５８】
【数１１】
2004274709.tif 000013
【００５９】
パリティチェック方程式の廃棄
本方法のオプションのステップ１５０では、選択されたパリティチェック方程式を廃棄することができる。しかしながら、出力ＧＰＣ行列１６１が、入力ＧＰＣ行列１１１と同じ符号に対応することを保証するために、それぞれの制約集合およびそれぞれの共通集合に対応する少なくとも１つの方程式が存在することが不可欠である。したがって、本例では、｛１，２，３，５｝の集合を用いて導出された方程式の１つを廃棄することができるが、方程式を両方とも廃棄することはできない。
【００６０】
パリティチェック方程式のすべての対が、２つまたは３つ以上の同じ変数を決して含まないことを確実にするために、パリティチェック方程式のいくつかを廃棄することが望ましい場合がある。
【００６１】
これは、出力ＧＰＣ行列１６１のいずれの２行も、同じ列の２つ以上に１を持たないことを保証し、これについては、ＡＰＰ復号もしくはＢＰ復号に基づく復号アルゴリズム、またはＡＰＰ復号もしくはＢＰ復号と同様の復号アルゴリズムに使用されたときの、ＧＰＣ行列の望ましい特性として前に列挙した。
【００６２】
出力ＧＰＣ行列へのパリティチェック方程式の変換
次に、残っているパリティチェック方程式４００が、出力ＧＰＣ行列１６１Ｈ’に変換される（１６０）。それぞれのパリティチェック方程式は、出力ＧＰＣ行列の１行に対応する。本例では、我々が、前のステップ１５０で、パリティチェック方程式のいずれも廃棄しなかったと仮定して、（７，４）ハミング符号についての出力ＧＰＣ行列１６１を得る。
【００６３】
【数１２】
2004274709.tif 000014
【００６４】
それぞれの列の上に、入力ＧＰＣ行列の対応する列からのビットまたはビットの集合を示している。
【００６５】
ステップ１７０では、メッセージ１７１を復号するために、出力ＧＰＣ行列１６１を使用することができる。
【００６６】
本発明の効果
出力ＧＰＣ行列Ｈ’１６１は、常に、入力ＧＰＣ行列Ｈ１１１と同一の符号を表す。さらに、この出力ＧＰＣ行列は、例えばＡＰＰ復号方法またはＢＰ復号方法を用いて、メッセージ１７１に対して、入力行列よりも良好な復号性能を有することができる。本例では、出力行列の各行は、３つの１のみを有するのに対し、入力ＧＰＣ行列は、各行に４つの１を有する。出力行列Ｇ’では、いずれの２行も、２つまたは３つ以上の同じ列に１を有しないのに対し、入力ＧＰＣ行列については、行のすべての対が、２つの同じ列に１を有する。
【００６７】
出力ＧＰＣ行列が、入力ＧＰＣ行列よりも多くの状態変数ビットを有すること、および出力ＧＰＣ行列が、通常、入力ＧＰＣ行列よりも多くの冗長チェックを使用することにも注目されたい。
【００６８】
本発明によって変換されたＧＰＣ行列を用いると、ビリーフ伝播復号方法は、はるかに良好な性能を発揮できることが、実験により示される。例えば、Golay（ｎ＝２３、ｋ＝１２）符号を考える。このパリティチェック行列によってこの符号が表現可能であることを、例えばLin等著の「Error Control Coding: Fundamentals and Applications」, Prentice Hall: Englewood Cliffs, NJ, 1983に見られる標準的な理論を用いて示すことができる。
【００６９】
【数１３】
2004274709.tif 000015
【００７０】
ＨＧｏｌａｙは、２３行および２３列を有する。ＨＧｏｌａｙは、ＢＰまたはＡＰＰのような繰り返し復号方法による使用に対して、望まれるすべての特性を有するとは限らないことに注目されたい。特に、行の多くの対は、いくつかの同じ列に１を有する。
【００７１】
我々が、ＨＧｏｌａｙを、本方法についての入力ＧＰＣ行列として使用すると、いかなる共通集合もパリティチェック方程式も廃棄することなく、出力ＧＰＣ行列Ｈ’Ｇｏｌａｙを得る。この出力ＧＰＣ行列Ｈ’Ｇｏｌａｙは、４９５行および２３０列を有する。
【００７２】
ＨＧｏｌａｙおよびＨ’Ｇｏｌａｙの双方を用いて、標準的なＢＰ復号方法を実施し、通信路が、２元消失通信路であると仮定した。２元消失通信路では、それぞれのビットは、確率ｐｅで消失し、確率１−ｐｅで正しく受信される。ｐｅ＝０．１６の消失確率に対して、ＨＧｏｌａｙを用いたＢＰ復号方法は、受信ブロックの約０．４９％を復号できない。これに対し、Ｈ’Ｇｏｌａｙを用いた復号方法は、受信ブロックの約０．０８７％のみを復号できないにすぎない。他の消失確率についても、同様の改善が得られた。
【００７３】
Golay符号が小さな値のｎおよびｋを有し、２元消失通信路が特にシンプルであることから、これらの結果を、最適な最尤復号の性能と比較することができる。Ｈ’Ｇｏｌａｙを用いたＢＰ復号の性能が、最適なＭＬ復号とほとんど見分けがつかないことを見出している。特に、ｐｅ＝０．１６の消失確率を用いてランダムに発生させた２３０，０００個のブロックのうち、Ｈ’Ｇｏｌａｙを用いたＢＰ復号は、２００個のブロックを復号できなかった。しかし、それらのブロックは、最尤復号も復号できなかったブロックとまさに同じであった。
【００７４】
他の大きな符号についての実験も、ＢＰ復号方法の復号性能が、本方法によって変換されたＧＰＣ行列を用いて改善可能であることを示している。
【００７５】
本発明については、好ましい実施の形態を例に説明してきたが、さまざまな他の適用および変更を、本発明の精神および範囲内においてなし得ることが理解されるべきである。したがって、添付した特許請求の範囲の目的は、本発明の真の精神および範囲内に入るすべての変形および変更を網羅することである。
【図面の簡単な説明】
【００７６】
【図１】本発明による方法のフローチャートである。
【図２】補助集合の半順序集合の図である。
【図３】補助集合の部分集合の編成されたリストである。
【図４】パリティチェック方程式のリストである。
【図１】
2004274709.tif 000016
【図２】
2004274709.tif 000017
【図３】
2004274709.tif 000018
【図４】
2004274709.tif 000019
【外国語明細書】
2004274709.tif 000020
2004274709.tif 000021
2004274709.tif 000022
2004274709.tif 000023
2004274709.tif 000024
2004274709.tif 000025
2004274709.tif 000026
2004274709.tif 000027
2004274709.tif 000028
2004274709.tif 000029
2004274709.tif 000030
2004274709.tif 000031
2004274709.tif 000032
2004274709.tif 000033
2004274709.tif 000034
2004274709.tif 000035
2004274709.tif 000036
2004274709.tif 000037
2004274709.tif 000038
2004274709.tif 000039
2004274709.tif 000040
2004274709.tif 000041
2004274709.tif 000042
2004274709.tif 000043
2004274709.tif 000044