(57)【要約】【課題】高ガースＱＣ−ＬＤＰＣ符号を構成するための改良された方法が望まれている。【解決手段】方法は、符号を構成し、当該符号は、大きなガースの準巡回低密度パリティ検査符号である。符号の基本行列を選択する。基本行列に対応するコスト行列を求める。基本行列の単一の要素を繰り返し変更し、コストの削減を最大にする。コストが０であるとき、符号のパリティ検査行列を基本行列から構成し、符号化器において、当該パリティ検査行列を使用して情報ブロックを符号語として符号化する。【選択図】図１
2010057177.tif 000002
【特許請求の範囲】
【請求項１】
符号を構成する方法であって、該符号は、準巡回低密度パリティ検査符号であり、該方法は、
前記符号の基本行列を選択するステップと、
前記基本行列に対応するコスト行列を求めるステップと、
コストの削減を最大にするために、前記基本行列の単一の要素を繰り返し変更するステップと、
前記コストが０であるとき、前記符号のパリティ検査行列を前記基本行列から構成するステップと、
符号化器において、前記パリティ検査行列を使用して情報ブロックを符号語として符号化するステップと
を含む方法。
【請求項２】
前記変更するステップは、ヒルクライミング手順を使用する請求項１に記載の方法。
【請求項３】
前記基本行列は、パラメータに従って初期化される請求項１に記載の方法。
【請求項４】
前記コスト行列は、前記符号のガース、及び前記符号のサイクルに基づく重みベクトルに従って求められる請求項１に記載の方法。
【請求項５】
前記コスト行列を使用して利得行列を生成し、該利得行列の最大の正の利得を使用して前記削減を生成するステップをさらに含む請求項１に記載の方法。
【請求項６】
前記基本行列は、前記パラメータに基づいてランダムに選択される請求項３に記載の方法。
【請求項７】
前記コストは、前記ガース未満の長さを有する前記サイクルの数の関数である請求項４に記載の方法。
【請求項８】
前記コストは、非所望のサイクルの加重和に基づいている請求項７に記載の方法。
【請求項９】
前記コスト行列は、前記基本行列の任意の値を他の任意の可能な値に変更するコストを示す請求項１に記載の方法。
【請求項１０】
前記チャネルは、通信チャネルである請求項１に記載の方法。
【請求項１１】
前記チャネルは、後の回復及び復号に備えて、前記符号化された情報ブロックを記憶媒体上に書き込むステップを含む請求項１に記載の方法。
【請求項１２】
チャネルを通じて前記符号語を送信するステップと、
前記情報ブロックを回復するために復号器において前記符号語を復号するステップと
をさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には、エラー訂正符号に関し、より具体的には、大きなガース（girth）の準巡回低密度パリティ検査（quasi-cyclic low-density parity-check：ＱＣ−ＬＤＰＣ）符号を構成することに関する。
【背景技術】
【０００２】
エラー訂正符号
データの記憶及び通信の分野における基本的な問題は、効率的なエラー訂正符号を構成することである。別段の指定がない限り、以下の説明において「符号」と記載する場合には、いずれもエラー訂正符号を示すものと解されるべきである。
【０００３】
１つの非常に重要なエラー訂正符号は、線形ブロックエラー訂正符号である。
【０００４】
この符号は、Ｎ個のシンボルのブロックを使用して、ｋ個の情報シンボルのブロックを符号化する。ここで、Ｎ＞ｋである。Ｎ−ｋ個の追加シンボルは、破損した信号が雑音を有する通信チャネルにより受信されるとき、又は障害のある記憶媒体からの復旧時に、それらの破損した信号を訂正するのに使用される。パラメータｋは、符号の「次元」と呼ばれる。
【０００５】
符号のすべての制約条件を満たすＮ個のシンボルのブロックは、「符号語」と呼ばれ、ｋ個の情報シンボルの対応するブロックは、「情報ブロック」と呼ばれる。
【０００６】
線形符号は、パリティ検査行列によって表すことができる。バイナリ［Ｎ，ｋ］符号を表すパリティ検査行列は、Ｍ行及びＮ列を有する０及び１からなる行列である。パリティ検査行列のＮ列は、符号のＮ個のシンボルに対応する。この行列の線形独立行の個数は、Ｎ−ｋである。
【０００７】
ＬＤＰＣ符号
近年、反復方法を使用して復号することができる符号に多大な関心が寄せられている。１つの特に重要な反復復号可能な符号は、１９６３年にGallagerによって最初に説明された低密度パリティ検査（ＬＤＰＣ）符号である。これについては、非特許文献１及び２００３年１０月１４日にRichardson他に付与された「Methods and apparatus for decoding LDPC codes」と題する特許文献１を参照されたい。
【０００８】
多くのＬＤＰＣ符号は、ランダムな構成を使用する。たとえば、GallagerのオリジナルのバイナリＬＤＰＣ符号は、パリティ検査行列の観点から定義される。このパリティ検査行列は、０及び１のみからなり、少数の１は、予め定義された確率分布に従って行列内でランダムに配置される。一般に、反復復号器は、比較的少数の非ゼロのエントリーを有するパリティ検査行列がランダムな構成を有しようと、又は規則的な構成を有しようと、そのパリティ検査行列を有する符号に対して効果がある。
【０００９】
ＬＤＰＣ符号は、「タナーグラフ」を使用して表されることが多い。タナーグラフは、パリティ検査行列と等価である。タナーグラフでは、パリティ検査行列の列は、「ビットノード」として表される一方、パリティ検査行列の行は、「検査ノード」として表される。タナーグラフは、パリティ検査行列の対応する行及び列の位置に１がある場合に、ビットノードと検査ノードとの間の接続を含む２部グラフである。
【００１０】
ＱＣ−ＬＤＰＣ符号
ランダムな構成に基づくＬＤＰＣ符号は、ハードウェア復号器を製作することに伴う配線の複雑度が非常に高くなるという不利な点を有する。この理由から、より規則的な「準巡回」ＬＤＰＣ（ＱＣ−ＬＤＰＣ）符号が開発された。ＱＣ−ＬＤＰＣ符号の一例は、非特許文献２、特許文献２、及び特許文献３に説明されている。
【００１１】
ＱＣ−ＬＤＰＣ符号の規則的な構造によって、効率的且つ高速な超大規模集積（ＶＬＳＩ）の実施態様が可能になる。この理由から、たとえば、ＩＥＥＥ８０２．１６ｅ標準規格、ＩＥＥＥ８０２．１１ｎ標準規格、及びＤＶＢ−Ｓ２標準規格といった多数の無線通信標準規格は、ＱＣ−ＬＤＰＣ符号を使用している。
【００１２】
一般に、ＱＣ−ＬＤＰＣ符号は、特殊な構造を有するパリティ検査行列Ｈの形である。このパリティ検査行列Ｈによって、符号は、ハードウェア実施に非常に好都合なものとなる。パリティ検査行列は、ｐ×ｐ正方部分行列から構成される。これらの部分行列は、すべて０からなるか、又は循環置換行列であるかのいずれかである。
【００１３】
循環置換行列は、各行に単一の１を有する行列であり、１が位置する列は、行ごとに１つずつシフトされる。下式（１）の行列は、ｐ＝６を有する循環置換行列の一例である。
【００１４】
【数１】
2010057177.tif 000003
【００１５】
この行列は、行及び列が、位置０から開始してカウントされるとき、第０行の１は列２にあるので、「Ｉ（２）」と呼ばれる。置換行列Ｉ（０）は、単位行列である。Ｉ（ｔ）のインデックスｔの値がｐ以上である場合、行列はラップアラウンド（wrap around）し、その結果、ｐ＝６の場合に、Ｉ（２）＝Ｉ（８）＝Ｉ（１４）等を有する。ＱＣ−ＬＤＰＣ符号を記述する際に一般に使用され、且つ、本明細書で使用される１つの特殊な表記は、ｐ×ｐの全ゼロ行列がＩ（−１）と表されることである。
【００１６】
サイズｐ×ｐの部分行列を有する（Ｊ，Ｌ）ＱＣ−ＬＤＰＣ符号は、そのパリティ検査行列によって、下式（２）のように定義される。
【００１７】
【数２】
2010057177.tif 000004
【００１８】
ここで、０≦ｊ≦Ｊ−１であり、０≦ｌ≦Ｌ−１であり、ｐｊ，ｌは、範囲−１≦ｐｊ，ｌ≦ｐ−１の整数である。サイズＭ×Ｎのパリティ検査行列の場合、Ｎ＝ｐＬであり、ｍ＝ｐＪである。
【００１９】
特定のＱＣ−ＬＤＰＣパリティ検査行列は、下式（３）に示すような、対応するＪ×Ｌ次元の基本行列Ｂから構成することができる。この基本行列のエントリーは、パリティ検査行列の対応するエントリーの値ｐｊ，ｌである。
【００２０】
【数３】
2010057177.tif 000005
【００２１】
全ゼロの部分行列が使用されるとき、その結果のＬＤＰＣ符号は、「不規則な」ＬＤＰＣ符号となる可能性がある。不規則なＬＤＰＣ符号は、パリティ検査行列の異なる列又は行が、異なる個数の１を含む可能性がある符号である。
【００２２】
ＬＤＰＣ符号のガース
用途に応じて、ＬＤＰＣ符号は、「ウォータフォール」（符号しきい値付近のＳＮＲ）若しくは「エラーフロア」（高ＳＮＲ）レジームのいずれか又は双方における性能を最適化するように設計される。低いエラーフロアは、データ記憶装置及び通信システム等の非常に厳しい信頼性要求を有する用途にとって特に重要である。
【００２３】
ＬＤＰＣ符号のエラーフロア問題のいくつかの理論的解析は、エラーイベントが「トラッピングセット」によって引き起こされることを示している。これについては、たとえば、非特許文献３を参照されたい。トラッピングセットは、符号のタナーグラフにおける短いサイクルのクラスタに起因する。短いサイクルを伴うトラッピングセットを取り除く１つの方法は、タナーグラフにおける短いサイクルのクラスタリングを注意深く設計することである。
【００２４】
より単純な手法は、より大きなガースを有する符号を使用する。符号の「ガース」は、符号グラフにおける最短サイクルの長さである。短いサイクルを取り除くことによって、多数のサイクルが取り除かれる。これは、エラーフロアを低くする（改善する）効果を有する。
【００２５】
ＬＤＰＣ符号のガースを最適化することに関しては、かなりの従来技術が存在する。ある符号は、漸進的エッジ増大（progressive-edge growth：ＰＥＧ）方法を使用する。これについては、非特許文献４を参照されたい。
【００２６】
また、ＰＥＧ方法をＱＣ−ＬＤＰＣ符号に適用することに関する研究も行われてきた。これについては、非特許文献５を参照されたい。
【００２７】
高ガースＱＣ−ＬＤＰＣ符号は、ランダムな「推測及び試験（guess-and-test）」方法を使用して構成することもできる。これについては、非特許文献６を参照されたい。
【先行技術文献】
【特許文献】
【００２８】
【特許文献１】米国特許第６，６３３，８５６号明細書
【特許文献２】米国特許公開第２００６０１０９８２１号明細書
【特許文献３】米国特許公開第２００５０１４９８４５号明細書
【非特許文献】
【００２９】
【非特許文献１】T. Richardson及びR. Urbanke著「The Renaissance of Gallager's Low-Density Parity-Check Codes」（IEEE Communications Magazine, vol. 41, pp. 126-131, August 2003）
【非特許文献２】R. M. Tanner、D. Sridhara、及びT. Fuja著「A Class of Group-Structured LDPC Codes」（Proc. International Symposium on Communication Theory and Applications, Ambleside, U.K., July 2001）
【非特許文献３】T.J. Richardson著「Error Floors of LDPC Codes」（Proc. 41st Annual Allerton Conference on Communications, Control, and Computing 2003）
【非特許文献４】X. Y. Hu、E. Eleftheriou、及びD. M. Arnold著「Regular and Irregular Progressive Edge-Growth Tanner Graphs」（IEEE Trans. Info. Theory, vol. 51, pp. 386-398, 2005）
【非特許文献５】Z. Li、B. V. K. V. Kumar著「A Class of Good Quasi-cyclic low-density parity-check Codes Based on Progressive Edge Growth Graph」（Signals, Systems, and Computers, Conference Record of the 38th Asilomar Conference, vol. 2, pp. 1990-1994, 2004）
【非特許文献６】M. P. C. Fossorier著「Quasi-cyclic low-density parity-check codes from circulant permutation matrices」（IEEE Trans. Inform. Theory, vol. 50, no. 8,  pp. 1788-1793, Aug. 2004）
【発明の概要】
【発明が解決しようとする課題】
【００３０】
しかしながら、特定のブロック長及び次元の符号について達成することができるガースの観点から、それらの方法には改良の余地がある。したがって、高ガースＱＣ−ＬＤＰＣ符号を構成するための改良された方法が望まれている。
【課題を解決するための手段】
【００３１】
本発明の実施の形態は、高ガース準巡回低密度パリティ検査（ＱＣ−ＬＤＰＣ）符号を構成する方法を提供する。この方法は、ヒルクライミング最適化手順を使用する。ヒルクライミング手順は、符号のパラメータを貪欲に調整して、指定された符号及びガースのパラメータを満たす短い長さの符号を見つける。
【発明の効果】
【００３２】
ガースが与えられると、この方法は、従来技術のＰＥＧ方法又は「推測及び試験」方法と比較して、より少ない時間で、より短いブロック長のＱＣ−ＬＤＰＣ符号を構成することができる。この時間差は、大きな基本行列を有するＱＣ−ＬＤＰＣ符号では、著しい。
【図面の簡単な説明】
【００３３】
【図１】本発明の実施形態によるＱＣ−ＬＤＰＣ符号を使用して情報を符号化及び復号する方法のフロー図である。
【図２】本発明の実施形態による基本行列及び可能な置換行列のフロー図である。
【図３】本発明の実施形態による高ガースを有する準巡回低密度パリティ検査符号を構成する方法のフロー図である。
【図４】本発明のヒルクライミング最適化手順によって構成されたＱＣ−ＬＤＰＣ符号を従来技術の推測及び試験方法と比較するグラフである。
【図５】本発明のヒルクライミング最適化手順によって構成されたＱＣ−ＬＤＰＣ符号を従来技術の推測及び試験方法と比較するグラフである。
【図６】本発明のヒルクライミング最適化手順によって構成されたＱＣ−ＬＤＰＣ符号を従来技術の推測及び試験方法と比較するグラフである。
【発明を実施するための形態】
【００３４】
図１に示すように、本発明の実施の形態は、高ガースを有する準巡回低密度パリティ検査（ＱＣ−ＬＤＰＣ）符号１５０を構成する（１００）方法を提供する。このような符号は、次に、ソース１１０によって生成されたｋ個のシンボルの情報ブロックｕ［ａ］１０１を符号化する（１２０）のに使用することができる。符号化された情報は、Ｎ個のシンボルを含む符号語ｘ［ｎ］１０２として、雑音を有するチャネル１３０を通じて送信される。このチャネルは、通信チャネルとすることができる。また、「チャネル」は、記憶媒体とすることもできる。この場合、符号語は、後のリトリーブに備えて媒体に書き込まれる。
【００３５】
チャネルは、符号語を破損して信号ｙ［ｎ］１０３にする可能性がある。この信号は、次に、復号器１４０に渡される。復号器１４０は、ＱＣ−ＬＤＰＣ符号１５０を使用して情報ブロックｕ［ａ］１０１を再構成したものｚ［ａ］１０４の出力を試みる。
【００３６】
ＱＣ−ＬＤＰＣ符号のサイクルの検出
図２は、所与の基本行列Ｂ  ２１０のタナーグラフにおけるサイクルを示している。本発明を理解するには、タナーグラフにおけるサイクルをどのようにして特定することができるのかを理解することが役立つ。９×６基本行列Ｂ  ２１０並びに４つのパラメータｐ１、ｐ２、ｐ３、及びｐ４が示されている。２つの可能な対応するパリティ検査行列Ｈ  ２１１及びＨ  ２１２も示されている。各パリティ検査行列は、基本行列の関連パラメータｐ１、ｐ２、ｐ３、及びｐ４の４つの３×３循環置換部分行列２２０を有する。これらの４つの行列のパラメータのこれらの２つの可能な選択肢は、
行列２１１におけるｐ１＝０、ｐ２＝１、ｐ３＝２、及びｐ４＝１、並びに
行列２１２におけるｐ１＝０、ｐ２＝ｐ３＝ｐ４＝１
である。
【００３７】
第１の部分グラフは、破線２３１で示すように、長さ４のサイクルになる一方、後者の部分グラフは、長さ１２のサイクル２３２になる。
【００３８】
次に、シフトの選択と符号のタナーグラフにおける結果のサイクルの長さとの間の対応を説明する。パリティ検査行列の各行は、タナーグラフの検査ノードに対応し、各列は、タナーグラフのビットノードに対応する。サイクルは、検査ノードとビットノードとが交互になったノードを通じるパスに対応する。
【００３９】
図２に示すように、ノードを通じるパスは、直線的な移動として視覚化することができる。行に沿った横の移動は、そのパスの一部をなす同じパリティ検査に接続された２つのエッジを選択することに対応する。列に沿った縦の移動は、そのパスの次のステップをなす同じビットノードに接続された第２のエッジを選択することに対応する。
【００４０】
１つのサイクルについて、パスは、そのパスが開始したビットノードと同じビットノードで終了する。パスを基本行列のレベルで見るとき、パスがサイクルを形成することは必要ではあるが、十分ではない。換言すれば、パスは、基本行列において−１により表されるどの全ゼロ部分行列も通過しないことが必要とされる。潜在的なパスがこの条件を満たすものと仮定する。しかしながら、各循環置換部分行列は、ｐ個のパリティノード及びｐ個の変数ノードに対応するので、これは十分ではない。
【００４１】
パスは、同じ循環置換部分行列の異なるビットノードで終了する可能性があり、したがって、サイクルを完成しない可能性がある。十分であるものは、パスが戻るときに、そのパスが開始した循環部分行列の列と同じ列に戻る場合である。たとえば、サブグラフ２１１では、これは、長さ４のサイクルについて起こる。一方、サブグラフ２１２の循環シフトのわずかに異なる選択によって、これは、長さ１２のサイクルの後にのみ起こる。
【００４２】
次に、結果としてサイクルを生じるパラメータｐｊ，ｌに関する条件を指定することができる。所与のパスに沿った近傍の置換行列のｐｊ，ｌ間の差分が求められる。ここで、近傍のものは、同じ行にある。図２では、これらは、ｐ２−ｐ１及びｐ４−ｐ３である。代替的に、列に沿った差分の点からこれを記述することもできる。各差分は、パスが通過する置換行列の列におけるシフトに対応する。パスの終端において差分の合計が０（ｍｏｄ−ｐ）になる場合にのみ、パスは、開始した置換行列の同じ変数ノードに戻り、それによって、サイクルが定義される。図２の例について、長さ４のサイクルが存在するには、条件は、下式（４）となる。
【００４３】
【数４】
2010057177.tif 000006
【００４４】
これは、ｐ１＝０、ｐ２＝１、ｐ３＝２、ｐ４＝１の場合には満たされるが、ｐ１＝０、ｐ２＝ｐ３＝ｐ４＝１の場合には満たされない。ＱＣ−ＬＤＰＣ符号の各サイクルは、循環部分行列におけるｐ−１個の可能な巡回シフトによって得られるｐ−１個の他のサイクルに必然的に関係付けられる。
【００４５】
同じロジックは、より長いサイクルに拡張される。長方形に配列された基本行列の４つの要素を通る４サイクル通過については、符号のタナーグラフにおける長さ２ｉの任意のサイクルが、順序付けられた下式（５）の配列によって表された基本行列の２ｉ個の要素を通過する。
【００４６】
【数５】
2010057177.tif 000007
【００４７】
ここで、１≦ｋ＜ｉ、ｊｋ≠ｊｋ−１、ｌｋ≠ｌｋ−１、ｊｉ−１≠ｊ０、及びｌｉ−１≠ｌ０である。この順序付けられた配列は、長さ２ｉの「潜在的」なサイクルとみなすことができる。実際には、この配列は、基本行列においてトラバースされた要素が、式（４）を一般化したものを満たす場合にのみサイクルに対応する。この一般化したものを定義するために、以下の表記を使用する。下式が定義される。
【００４８】
【数６】
2010057177.tif 000008
【００４９】
符号が少なくとも２（ｉ＋１）のガースを有するための必要十分条件は、下式（６）である。
【００５０】
【数７】
2010057177.tif 000009
【００５１】
あらゆる次元対（Ｊ，Ｌ）及びガースｇ（グラフの最小の長さのサイクル）について、ｐ＜ｐｍｉｎ又はＮ＜Ｎｍｉｎであるときに、上式（６）を満たすパリティ検査行列が存在しないようなｐｍｉｎ（すなわち、Ｎｍｉｎ）が存在する。
【００５２】
次元（Ｊ，Ｌ）及びガースｇの高ガースＱＣ−ＬＤＰＣ符号を構成する方法を提供する。この方法は、基本行列Ｂと、その基本行列から構成された指定された符号がそのガースを有し、且つｐがｐｍｉｎに等しいか、又は少なくともできるだけｐｍｉｎに近くなるようなｐの値とを返す。
【００５３】
１つの従来技術の方法は、「推測及び試験」方法を使用する。これについては、Fossorier著「Quasi-cyclic low-density parity-check codes from circulant permutation matrices」（IEEE Trans. Inform. Theory, vol. 50, no. 8,  pp. 1788-1793, Aug. 2004）を参照されたい。推測及び試験方法では、上式（６）が満たされるような集合が見つかるまで、基本行列Ｂの非ゼロの要素について、０とｐ−１との間の（Ｊ−１）（Ｌ−１）個の整数が、ランダム且つ独立同一に分散される。
【００５４】
Fossorierは、ガース８以上の符号について、基本行列のすべての非ゼロの値が異なっていなければならないことを示している。それらのガースについてのFossorierの方法は、すべての整数が異なるように、（Ｊ−１）（Ｌ−１）個の整数が、１からｐ−１までの範囲でランダムに選択される方法であると考えられる。推測及び試験方法に関する問題は、この方法が、特に大きな基本行列であって、ＮがＮｍｉｎに接近している場合には、多くの時間を要するということである。
【００５５】
ヒルクライミング最適化手順
本発明の方法は、「ヒルクライミング」最適化手順である。ヒルクライミングは、多くの解を有するが、いくつかの解は他のものよりも優れている問題を解くのに使用することができる最適化技法である。この手順は、問題のランダム初期解から開始し、小さな変更を反復的に行って、その解を改善するものである。
【００５６】
本発明では、ランダムに選択された基本行列Ｂから開始する。また、コストからなる対応するコスト行列Ｃも有する。次に、「移動」を行うことによって基本行列Ｂを変更する。この移動によって、基本行列の単一の要素（ｐｊ，ｌ）の値が変更される。コストの削減を最大にする移動を選択する。コストは、基本行列Ｂに残っているガースよりも短い長さのサイクルの数の関数である。
【００５７】
基本行列のどの単一の値も、コストをさらに削減する値にもはや変更することができず、したがって、非所望のより短いサイクルの数になると、この方法は終了する。
【００５８】
この手順は、コスト行列Ｃによって定義されるコスト関数が非所望のサイクルの加重和であり、且つ異なる重みのサイクルがコスト関数において異なる重みを有するローカルヒルクライミングを使用する。
【００５９】
本発明の方法は、現在の符号の各長さのサイクルの数を追跡し、基本行列Ｂの各可能な要素を他の可能な値に変更する場合に、その結果得られるサイクルの数を追跡する。
【００６０】
この方法は、大きなガースを有する符号を検索するとき、サイクルがタナーグラフにおいて形成することができる多くの可能な方法のために、より複雑なものとなる。
【００６１】
コスト行列
コスト行列Ｃは、サイクルの数の加重和の点から、基本行列Ｂの任意の値を変更して、他の任意の可能な値を有するようにするコストを示す。したがって、任意の基本行列Ｂについて、下式（７）に示すような、対応するコスト行列が存在する。
【００６２】
【数８】
2010057177.tif 000010
【００６３】
ここで、ｃｊ，ｌ＝［ｃｊ，ｌ，０，ｃｊ，ｌ，１，．．．，ｃｊ，ｌ，ｐ−１］は、コストであり、ｃｊ，ｌ，ｚは、基本行列Ｂの要素ｐｊ，ｌを０≦ｚ≦ｐ−１の値ｚに割り当てるためのコストである。
【００６４】
Ｓｉを、順序付けられた配列によって表される、すべての可能で且つ異なる長さ２ｉの潜在的なサイクルの集合を表すものとし、｜Ｓｉ｜を、集合Ｓｉ内のすべての要素の個数を表すものとする。したがって、１≦ｋ≦｜Ｓｉ｜について、下式のＳｉｋを有するＳｉ＝｛ｓｉ１，ｓｉ２，．．．，ｓｉ｜Ｓｉ｜｝となる。
【００６５】
【数９】
2010057177.tif 000011
【００６６】
ガースは、ｇであり、重みベクトルは、ｗ＝［ｗ２，ｗ３，．．．，ｗｇ／２−１］である。ここで、ｗｉは、長さ２ｉのサイクルの重み又はコストである。
【００６７】
基本行列について、対応するコスト行列Ｃは、次のものに基づいている。各潜在的なサイクルについて、その潜在的なサイクルにおける基本行列の要素のそれぞれを調べる。各要素について、その潜在的なサイクルの他のすべての基本行列の要素が同じままであると仮定して、どの値がサイクルを引き起こすのかをチェックし、要素のその値をマーキングする。
【００６８】
たとえば、潜在的な６サイクルについて、ｐ１−ｐ２＋ｐ３−ｐ４＋ｐ５−ｐ６ mod ｐ＝０である場合にのみサイクルが存在することが分かっている。ここで、ｐ１〜ｐ６は、この潜在的な６サイクルの要素である。したがって、ｐ１−ｐ２＋ｐ３−ｐ４＋ｐ５−ｐ６ mod ｐの現在の合計の値が１である場合、ｐ１、ｐ３、及びｐ５のマーキングされた値が現在の値よりも小さな値であり、且つ、ｐ２、ｐ４、及びｐ６のマーキングされた値が現在の値よりも大きな値であることが分かる。
【００６９】
これは、基本行列の２ｉ個の異なる要素を含む潜在的なサイクルについては、比較的簡単である。潜在的なサイクルにおける基本行列のいくつかの要素が２回現れる場合には、これはより複雑になる。これは、サイズ８以上のサイクルについて生じる可能性があり、たとえば、図２の部分グラフ２１２で生じる。このような場合、基本行列のパスは、要素を３回通過するので、要素の値が変化すると、交代和（alternating sum）に対する貢献は、図２の長さ１２のサイクル２３２において２倍又は３倍になる。したがって、マーキングする値を見つけることは、より複雑となる。実際に、ｐが偶数であり且つ交代和の現在の値が偶数である場合には、２回繰り返す要素についてマーキングされた値が２つ以上存在する可能性がある。他方、ｐが偶数であり且つ交代和の現在の値が奇数である場合には、２回繰り返す要素についてマーキングされる値は存在しない場合がある。
【００７０】
形式的には、次のようにコスト行列が求められる。
【００７１】
ステップ１
０≦ｊ≦Ｊ−１、０≦ｌ≦Ｌ−１、及び０≦ｚ≦ｐ−１について、
コスト行列ｃｊ，ｌ，ｚ＝０を求める。
【００７２】
ステップ２
２≦ｉ≦ｇ／２−１について、
ｉ．０≦ｊ≦Ｊ−１、０≦ｌ≦Ｌ−１、及び０≦ｚ≦ｐ−１について、
ｘ（ｉ）ｊ，ｌ，ｚ＝０を設定する。ここで、ｘ（ｉ）ｊ，ｌ，ｚは、基本行列の要素ｐｊ，ｌが値ｚを有する場合に結果として生じる長さ２ｉのサイクルの数のカウントである。
ｉｉ．１≦ｋ≦｜Ｓｉ｜について、下式の交代和αを求める。
【００７３】
【数１０】
2010057177.tif 000012
【００７４】
ｉｉｉ．０≦ｅ≦２ｉ―１について、
【数１１】
2010057177.tif 000013
がｓｉｋにおいて固有である場合、マーキングされた値βを下式により求める。
【００７５】
【数１２】
2010057177.tif 000014
【００７６】
ｉｖ．
【数１３】
2010057177.tif 000015
がｓｉｋにおいて固有でなく初めて生じ且つα mod ２＝０である場合、マーキングされた値βを下式により求める。
【００７７】
【数１４】
2010057177.tif 000016
【００７８】
ｖ．
【数１５】
2010057177.tif 000017
がｓｉｋにおいて固有でなく初めて生じ且つ（ｐ−α）mod ２＝０である場合、追加のマーキングされた値βを下式により求める。
【００７９】
【数１６】
2010057177.tif 000018
【００８０】
ｖｉ．上記３つの場合のそれぞれにおいて、下式をインクリメントする。
【００８１】
【数１７】
2010057177.tif 000019
【００８２】
ステップ３
０≦ｊ≦Ｊ−１、０≦ｌ≦Ｌ−１、及び０≦ｚ≦ｐ−１について、下式の加重和を取る。
【００８３】
【数１８】
2010057177.tif 000020
【００８４】
コスト行列を求めるためのこの方法によると、ヒルクライミング方法は、記述するのが比較的簡単である。
【００８５】
本発明では、ランダムな基本行列Ｂ及び対応するコスト行列Ｃから開始して、基本行列及びその基本行列の要素の現在の値のそれぞれについてゼロコストを有する対応するコスト行列が見つかるまで、ランダムに関係を絶ちながら、コストの削減を最大にする単一の基本行列の要素の値を変更する移動を選択し続ける。この時点で、基本行列Ｂを返すか、又は正のコストを有する局所最適解で終了する場合には、失敗状態を示す。
【００８６】
図３は、本発明の方法を詳細に示している。ＱＣ−ＬＤＰＣ符号のパラメータを初期化する（３１０）。これらのパラメータは、基本行列ＢのＪ及びＬの次元、基本行列Ｂの部分行列ｐのサイズ、並びに基本行列Ｂの全ゼロ部分行列の位置を含む。
【００８７】
ガースｇ及び重みベクトルｗ＝［ｗ２，ｗ３，．．．，ｗｇ／２−１］を指定する（３１１）。重みベクトルｗは、ガースｇよりも短い長さを有する各タイプのサイクルの重みを有する。重みベクトルは、異なるタイプのサイクルの「コスト」を表す。
【００８８】
符号の初期パラメータに従って、初期基本行列Ｂをランダムに選択する（３２０）。
【００８９】
基本行列Ｂ並びに指定されたガースｇ及び重みベクトルｗに対応するコスト行列Ｃを求める（３３０）。このステップは、上記で詳細に説明した。
【００９０】
コスト行列Ｃを使用して利得行列Ｇを生成する（３４０）。０≦ｊ≦Ｊ−１及び０≦ｌ≦Ｌ−１について、下式とする。
【００９１】
【数１９】
2010057177.tif 000021
【００９２】
ここで、
【数２０】
2010057177.tif 000022
は、基本行列Ｂの位置ｊ，ｌにおける可能な最小コストであり、
【数２１】
2010057177.tif 000023
は、そのコストを与える要素ｐｊ，ｌの値であり、ｃ’ｊ，ｌは、要素ｐｊ，ｌの現在の値に関連付けられたコストである。利得行列Ｇ＝［ｇｊ，ｌ］は、下式として生成される。
【００９３】
【数２２】
2010057177.tif 000024
【００９４】
利得行列は、基本行列の各位置ｊ，ｌにおける要素の最良の移動の値を表す。
【００９５】
次に、下式を求める。
【００９６】
【数２３】
2010057177.tif 000025
【００９７】
すべて同じ最大利得を達成する複数の要素ｊ，ｌが存在する場合、ランダムに関係が絶たれる。最大利得ｇｍａｘが正であるか否かをチェックする（３５０）。
【００９８】
真である場合、最大利得ステップ
【数２４】
2010057177.tif 000026
を選択することによって基本行列Ｂを更新し（３６０）、コスト行列Ｃを求めるステップ（３３０）を繰り返す。
【００９９】
そうではなく偽である場合、すべての０≦ｊ≦Ｊ−１及び０≦ｌ≦Ｌ−１についてすべてのコスト
【数２５】
2010057177.tif 000027
が０であるか否かをチェックする（３７０）。真である場合、本発明のすべての要件を満たすＱＣ−ＬＤＰＣ符号の所望の基本行列Ｂを有することになり、現在の基本行列Ｂを出力する（３８０）。そうではなく偽である場合、ＦＡＩＬＵＲＥ（失敗）を出力する（３８１）。ＱＣ−ＬＤＰＣ符号１５０のパリティ検査行列Ｈが、基本行列Ｂから構成される（３９０）。
【０１００】
次に、ＱＣ−ＬＤＰＣ符号、すなわち、パリティ検査行列Ｈ１５０を符号化器で使用して、チャネル１３０を通じて復号器へ送信される情報ブロックｕ［ａ］を符号化する（１２０）ことができ、情報ブロックを再構成することができる。符号化された情報ブロックは、後のリトリーブに備えて記憶媒体に書き込むこともできる。
【０１０１】
図４〜図６のグラフは、Ｊ＝３、Ｌ＝９、ｇ＝８（ヒルクライミングの４０１、Fossorierの推測及び試験の４０２）、Ｊ＝３、Ｌ＝１２，ｇ＝８（ヒルクライミングの５０１、推測及び試験の５０２）、及びＪ＝３，Ｌ＝９、ｇ＝１０（ヒルクライミングの６０１、推測及び試験の６０２）のそれぞれについて、成功率及び循環行列サイズｐの関数としてヒルクライミング方法をFossorierの推測及び試験方法と比較している。Ｌ及びｇが増加するにつれて、本発明のヒルクライミングの成功率は、次第に、従来技術の推測及び試験の成功率よりも優れてきている。
【０１０２】
これらのグラフに示すように、その成功率は、従来技術の方法よりも少なくとも３桁大きい。
【図１】
2010057177.tif 000028
【図２】
2010057177.tif 000029
【図３】
2010057177.tif 000030
【図４】
2010057177.tif 000031
【図５】
2010057177.tif 000032
【図６】
2010057177.tif 000033
【外国語明細書】
2010057177.tif 000034
2010057177.tif 000035
2010057177.tif 000036
2010057177.tif 000037
2010057177.tif 000038
2010057177.tif 000039
2010057177.tif 000040
2010057177.tif 000041
2010057177.tif 000042
2010057177.tif 000043
2010057177.tif 000044
2010057177.tif 000045
2010057177.tif 000046
2010057177.tif 000047
2010057177.tif 000048
2010057177.tif 000049
2010057177.tif 000050
2010057177.tif 000051
2010057177.tif 000052
2010057177.tif 000053
2010057177.tif 000054
2010057177.tif 000055
2010057177.tif 000056
2010057177.tif 000057
2010057177.tif 000058
2010057177.tif 000059
2010057177.tif 000060
2010057177.tif 000061