(57)【特許請求の範囲】
【請求項１】
連結性行列によって表されるプロトグラフに対応する準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号を求める方法であって、
少なくとも１つの複製線に沿って前記連結性行列の少なくとも幾つかの要素を複製するステップであって、拡張された連結性行列を生成し、該連結性行列内の前記少なくとも幾つかの要素の値は、所定のガースによって示されるパターンを形成する、複製するステップと、
前記拡張された連結性行列に対応する階層準巡回（ＨＱＣ）ＬＤＰＣ符号を求めるステップであって、該ＨＱＣ  ＬＤＰＣ符号は、巡回部分行列の行列によって表される、求めるステップと、
前記ＨＱＣ  ＬＤＰＣ符号を表す前記行列の前記少なくとも幾つかの要素を除去するステップであって、該行列が前記複製線に沿ってスカッシングされ、前記ＱＣ  ＬＤＰＣ符号が生成されるようにする、除去するステップと
を有し、該方法の各ステップは、プロセッサによって実行される、連結性行列によって表されるプロトグラフに対応する準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号を求める方法。
【請求項２】
前記所定のガースは、１０以上である請求項１に記載の方法。
【請求項３】
前記プロトグラフは、空間結合符号を表す請求項１に記載の方法。
【請求項４】
前記パターンは、２よりも大きい値を有する少なくとも２つの要素または３よりも大きい値を有する少なくとも１つの要素を有する連結性行列の行または列を含む請求項１に記載の方法。
【請求項５】
前記ＨＱＣ  ＬＤＰＣ符号は、制限された２レベルＨＱＣ  ＬＤＰＣ符号である請求項１に記載の方法。
【請求項６】
前記求めるステップは、
前記拡張された連結性行列を階層準巡回（ＨＱＣ）ＬＤＰＣ符号ファミリーに変換するステップと、
前記ＨＱＣ  ＬＤＰＣ符号ファミリーから、前記ＨＱＣ  ＬＤＰＣ符号の前記ガースが最適化されるような少なくとも１つのＨＱＣ  ＬＤＰＣ符号を選択するステップと
をさらに含む請求項１に記載の方法。
【請求項７】
前記選択するステップは、山登り法による手順を用いる請求項６に記載の方法。
【請求項８】
前記山登り法による手順は、
前記ファミリー内の前記ＨＱＣ  ＬＤＰＣ符号ごとにツリー構造を選択するステップと、
前記ツリー構造ごとにコストを求めるステップと、
前記ツリー構造内の単一のエッジラベルを繰返し変更するステップであって、前記コストの低減を最大にする、繰返し変更するステップと、
前記コストが最小のときに、前記ツリー構造から前記ＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列を構築するステップと
をさらに含む請求項７に記載の方法。
【請求項９】
前記変換するステップは、前記連結性行列の、制限された２レベルＨＱＣ  ＬＤＰＣ符号ファミリーへの直接変換である請求項６に記載の方法。
【請求項１０】
前記ＨＱＣ  ＬＤＰＣ符号は、多項式パリティ検査行列によって表され、該ＨＱＣ  ＬＤＰＣ符号の前記行列は、前記符号を表す基本行列であり、前記方法は、
前記多項式パリティ検査行列を基本行列符号にコンバートするステップであって、前記行列を生成する、コンバートするステップ
をさらに含む請求項１に記載の方法。
【請求項１１】
前記基本行列符号は、４×４の部分行列を用いて構築される請求項１０に記載の方法。
【請求項１２】
前記変換するステップは、
前記拡張された連結性行列を、対応するＨＱＣ  ＬＤＰＣ符号ファミリーを記述する多項式パリティ検査行列ファミリーに変換するステップであって、多項式パリティ検査行列の要素は、第１の変数ｘおよび第２の変数ｙの多項式を含み、前記複製線の両側の前記第２の変数ｙの指数は等しい、変換するステップ
を含む請求項６に記載の方法。
【請求項１３】
前記選択するステップは、
前記多項式パリティ検査行列ファミリーにおける自由度を最適化するステップであって、前記ＨＱＣ  ＬＤＰＣ符号を得る、最適化するステップと、
前記ＨＱＣ  ＬＤＰＣの前記多項式パリティ検査行列を基本行列符号にコンバートするステップであって、前記ＨＱＣ  ＬＤＰＣ符号の前記行列を生成する、コンバートするステップと
を含む請求項１２に記載の方法。
【請求項１４】
前記複製線は、前記連結性行列の行間または列間に延び、前記拡張された連結性行列の前記要素は、前記行列のＮ個の要素に対応し、前記除去するステップは、
前記複製線の両側の前記行列から２つの要素を除く全てを除去するステップ
をさらに含む請求項１に記載の方法。
【請求項１５】
前記要素の数は４に等しく、前記除去するステップが、前記複製線の両側の前記行列から２つの要素を除去するステップを含むようになっている請求項１に記載の方法。
【請求項１６】
前記スカッシング手順は、前記拡張された連結性行列内の各複製された列に対応する４つの列の各組から、基本行列内の２つの列を除去し、前記拡張された連結性行列内の各複製された行に対応する４つの行の各組から、前記基本行列内の２つの行をさらに除去する請求項１３に記載の方法。
【請求項１７】
前記ＨＱＣ  ＬＤＰＣ符号は、Ｋ個のレベルを含み、Ｋ個の変数の多変量多項式パリティ検査行列によって定義される請求項１に記載の方法。
【請求項１８】
前記行列の各部分行列は、巡回構造を有し、該部分行列の前記要素の値は、遷移線を越えると巡回フローを変化させる請求項１に記載の方法。
【請求項１９】
前記ＨＱＣ  ＬＤＰＣ符号を用いてデータを符号化するステップであって、符号化データを生成する、符号化するステップと、
前記符号化データをチャネルを介して送信するステップと
をさらに含む請求項１に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号に関し、より詳細には、高ガースを有するＱＣ  ＬＤＰＣ符号を求めることに関する。
【背景技術】
【０００２】
低密度パリティ検査（ＬＤＰＣ）符号の構築のために、大きく分けて２つの方法を用いることができる。一方の組は、高度にランダムなグラフ構築に基づく一方、他方は、構造化された代数的構築に基づく。ランダムなグラフ構築は、シャノン容量に近づくＬＤＰＣ符号を生成することができる。
【０００３】
ＬＤＰＣグラフ構築は、通常「タナーグラフ」を用いる。タナーグラフは、符号語ビットを表す「変数」ノードと、パリティ検査を表す「検査」ノードとを含む２部グラフである。ここで、変数ノードは、符号のパリティ検査行列内の対応するエントリーが非ゼロである場合にのみ、エッジによって検査ノードに連結される。タナーグラフは、既知である。
【０００４】
高度にランダムなタナーグラフ構築に基づく符号は、シャノン限界に密に近づくことができるが、符号のタナーグラフにおける検査ノードと変数ノードとの間の不規則な連結は、高い配線複雑度を意味するので、これらの構築は、ハードウェアにおいて実施するのが容易でない。実際の実施態様では、より構造化された構築が好ましい。なぜなら、これらは、はるかにより実際的な配線、および復号化器におけるより直接的な並列性を提供するためである。
【０００５】
準巡回ＬＤＰＣ（ＱＣ  ＬＤＰＣ）符号は、パリティ検査行列を用いる構造化されたグラフである。パリティ検査行列は、巡回構造を有する部分行列に分割される。構造化されたグラフは、ハードウェアにおいて実装するのが実際的であるので、ＱＣ  ＬＤＰＣ符号は、ＩＥＥＥ８０２．１６ｅ標準規格、ＤＶＢ−Ｓ２標準規格、およびＩＥＥＥ８０２．１１標準規格に従って実装されるような様々な通信ネットワークにおいて用いられる。
【０００６】
ほとんどの用途にとって、信号対雑音比（ＳＮＲ）が比較的低い「ウォーターフォール」レジームにおける復号化性能を最適化することが重要である。
【０００７】
しかしながら、用途によっては、ウォーターフォール性能を最適化することは十分でない。より高いＳＮＲレジームにおける多くのＬＤＰＣ符号に固有の「エラーフロア」も回避しなくてはならない。性能曲線における「エラーフロア」は、ＳＮＲが増加するとともに復号化失敗率が急速に減少し続けないことを意味する。エラーフロアを除去するかまたは低くすることは、高密度磁気記録および高速光ファイバー通信システムを含む、極度の信頼性需要を必要とする用途に特に重要である。
【０００８】
通常、ＱＣ  ＬＤＰＣ符号は、有限幾何学、有限フィールド、および組合せ設計を含む、広範にわたる技法に基づいて構築される。近年、「畳み込み」符号または「空間結合」符号の分野にも多くの関心が集まっている。「畳み込み」符号または「空間結合」符号は、従来のランダム構築よりもはるかに構造化されているが、シャノン容量に密に近づくこと、またはさらには２元消失通信路（ＢＥＣ）においてシャノン容量を達成することも示されている。ここで、これらの符号は、準巡回構築を用いて実装することができるので重要であり、このため、他の構造化されたＱＣ  ＬＤＰＣ符号の実用性を保ちながら、非常に良好な性能を達成することができるはずである。
【０００９】
確率伝搬（ＢＰ）復号化器を用いて復号化されたＬＤＰＣ符号のエラーフロア問題は、一般に、「トラッピングセット」によって引き起こされる。トラッピングセットは、不正確な確信において互いを補強する一組の少数のビットである。ビットのトラッピングセットは、符号のタナーグラフにおいて、クラスタリングされた短いサイクルで常に配列される。トラッピングセットを除去する１つの方法は、短いサイクルのクラスターが存在しないように、タナーグラフを設計することである。代替的な、少なくとも概念的により単純な手法は、より大きなガースを用いて符号を設計することである。符号の「ガース」は、タナーグラフにおける最も短いサイクルの長さとして定義される。短いサイクルを除去することによって、サイクルの危険な可能性がある構成を排除することができ、願わくはエラーフロアを低くすることができる。
【００１０】
良好なウォーターフォール性能を有する符号は、不可避的に、符号グラフの要素または変数ノードの次数の分布にある不規則性を有する。ＱＣ  ＬＤＰＣ符号の場合、これらの不規則な分布は、「プロトグラフ」の観点で最も容易に説明される。プロトグラフは、タナーグラフの変形であり、同じタイプのビットおよび検査が単一の「プロトビット」または「プロト検査」によって表される。プロトグラフは、符号ファミリーを記述する既知の方法である。
【００１１】
ＱＣ  ＬＤＰＣ符号の場合、プロトビットは、例えば、同じ巡回部分行列に属するビットを表すことができる。ウォーターフォール性能のために最適化された符号において生じるプロトグラフは、通常、複数のエッジによって連結されたプロトビットおよびプロト検査の幾つかの対を有する。そのようなプロトグラフに対応するＱＣ  ＬＤＰＣ符号を構築する直接的な方法は、巡回部分行列が１より大きい重みの行および列を有するＱＣ  ＬＤＰＣ符号を用いる。不都合なことに、これらのＱＣ  ＬＤＰＣ符号は、不可避的に、該ＱＣ  ＬＤＰＣ符号のタナーグラフにおいて短いサイクルを有する。
【００１２】
したがって、プロトグラフが複数のエッジによって連結されたプロトビットおよびプロト検査の対を有する場合であってもプロトグラフに対応するＱＣ  ＬＤＰＣ符号が所定の比較的高いガースを有するように、該ＱＣ  ＬＤＰＣ符号を求める方法を提供する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００１３】
本発明の目的は、プロトグラフに対応する準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号が所定のガースを有するように、該ＱＣ  ＬＤＰＣ符号を求めるためのシステムおよび方法を提供することである。さらに、別の目的は、１０以上のガースを有するＱＣ  ＬＤＰＣ符号を生成することができる方法を提供することである。
【課題を解決するための手段】
【００１４】
本発明の幾つかの実施の形態は、ＱＣ  ＬＤＰＣ符号が階層構造を有する場合、階層準巡回（ＨＱＣ）ＬＤＰＣ符号を表すパリティ検査行列を、符号のタナーグラフ内の短いサイクルが除去されるように変更することができるという認識に基づいている。ＨＱＣ  ＬＤＰＣ符号のパリティ検査行列は、複数のレベルを含み、各レベルは、巡回部分行列によって形成される。特に、レベルを形成する巡回部分行列のそれぞれが巡回部分−部分行列を含み、複数のレベルについて、以下同様である。
【００１５】
本発明の幾つかの実施の形態は、プロトグラフを表す連結性行列の要素の値が所定のパターンを形成する場合、プロトグラフの直接変換によって生成されるＱＣ  ＬＤＰＣ符号は、不可避的に短いサイクルを有するという別の認識に基づいている。所定のパターンは、ガースに固有である。例えば、所定のガースが少なくとも１０である場合、パターンは、２よりも大きい値を有する少なくとも２つの要素または３よりも大きい値を有する少なくとも１つの要素を有する連結性行列の行または列を含む。このため、サイクルを除去するために、ＨＱＣ  ＬＤＰＣ符号を表す行列は、示されたパターンを形成する連結性行列の要素の値に依拠して変更されなくてはならない。
【００１６】
本発明の幾つかの実施の形態は、所定のガースによって示される連結性行列の幾つかの要素が複製線に沿って複製される場合、拡張された連結性行列に対応するＨＱＣ  ＬＤＰＣ符号を、複製線に沿ってスカッシングし、ＱＣ  ＬＤＰＣ符号を生成することができるというさらに別の認識に基づいている。
【００１７】
したがって、本発明の幾つかの実施の形態は、連結性行列によって表されるプロトグラフに対応する準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号が所定のガースを有するように、該ＱＣ  ＬＤＰＣ符号を求める方法を開示する。本方法のステップは、連結性行列の少なくとも幾つかの要素を複製するステップであって、拡張された連結性行列を生成し、該連結性行列内の少なくとも幾つかの要素の値は、所定のガースによって示されるパターンを形成する、複製するステップと、拡張された連結性行列に対応する階層準巡回（ＨＱＣ）ＬＤＰＣ符号を求めるステップと、該ＨＱＣ  ＬＤＰＣ符号を表す行列の少なくとも幾つかの要素を除去するステップであって、該行列が複製線に沿ってスカッシングされ、ＱＣ  ＬＤＰＣ符号が生成されるようにする、除去するステップと、を含み、該方法のステップは、プロセッサによって実行される。
【００１８】
幾つかの実施の形態では、所定のガースは、１０以上であり、プロトグラフは、空間結合符号を表すことができ、および／またはＨＱＣ  ＬＤＰＣ符号は、制限された２レベルＨＱＣ  ＬＤＰＣ符号とすることができる。１つの実施の形態では、ＨＱＣ  ＬＤＰＣ符号を求めることは、拡張された連結性行列を階層準巡回（ＨＱＣ）ＬＤＰＣ符号ファミリーに変換することと、ＨＱＣ  ＬＤＰＣ符号ファミリーから、ＨＱＣ  ＬＤＰＣ符号のガースが最適化されるような少なくとも１つのＨＱＣ  ＬＤＰＣ符号を選択することと、を含む。
【００１９】
例えば、選択することは、ガースを最適化するために山登り法による手順を用いることができる。山登り法による手順は、ファミリー内のＨＱＣ  ＬＤＰＣ符号ごとにツリー構造を選択するステップと、ツリー構造ごとにコストを求めるステップと、ツリー構造内の単一のエッジラベルを繰返し変更するステップであって、コストの低減を最大にする、繰返し変更するステップと、コストが最小のときに、ツリー構造からＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列を構築するステップと、を含むことができる。
【００２０】
また、１つの実施の形態では、変換は、連結性行列の、制限された２レベルＨＱＣ  ＬＤＰＣ符号ファミリーへの直接変換とすることができる。付加的にまたは代替的に、変換ステップは、拡張された連結性行列を、対応するＨＱＣ  ＬＤＰＣ符号ファミリーを記述する多項式パリティ検査行列ファミリーに変換することができ、多項式パリティ検査行列の要素は、第１の変数ｘおよび第２の変数ｙの多項式を含み、複製線の両側の第２の変数ｙの指数は等しい。また、選択することは、多項式パリティ検査行列ファミリーにおける自由度を最適化することであって、ＨＱＣ  ＬＤＰＣ符号を得る、最適化することと、ＨＱＣ  ＬＤＰＣの多項式パリティ検査行列を基本行列符号にコンバートすることであって、ＨＱＣ  ＬＤＰＣ符号の行列を生成する、コンバートすることとをオプションで含むことができる。スカッシング手順は、拡張された連結性行列内の各複製された列に対応する４つの列の各組から、基本行列符号内の２つの列を除去することができ、拡張された連結性行列内の各複製された行に対応する４つの行の各組から、基本行列内の２つの行をさらに除去する。
【００２１】
また、様々な実施の形態において、ＨＱＣ  ＬＤＰＣ符号は、多項式パリティ検査行列および基本行列によって表される。例えば、基本行列は４×４の部分行列を用いて構築することができる。幾つかの実施の形態は、多項式パリティ検査行列を基本行列にコンバートする。
【００２２】
通常、複製線は、連結性行列の行間または列間に延在する。また、連結性行列の要素は、符号を表す行列のＮ個の行または列にそれぞれ対応することができる行または列である。複製することは、Ｎ／２個の複製を作製することを含むことができ、除去することは、複製線の両側の行列から２つの要素を除く全てを除去することをさらに含むことができる。例えば、Ｎが４に等しい場合、除去することは、複製線の両側の行列の行または列の２つの複製から２つの行または列を除去することを含む。
【００２３】
別の実施の形態は、準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号に基づいてデータを符号化するためのシステムであって、データを提供するためのソースと、パリティ検査行列によって表されるＨＱＣ  ＬＤＰＣ符号を格納するメモリであって、行列の各部分行列は、巡回構造を有し、該部分行列の要素の値は、遷移線を越えると巡回フローを変化させる、メモリと、ＨＱＣ  ＬＤＰＣ符号を用いてデータを符号化して符号化データを生成し、チャネルを介して該符号化データを送信する符号化器と、を備える、準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号に基づいてデータを符号化するためのシステムを開示する。
【図面の簡単な説明】
【００２４】
【図１】本発明の幾つかの実施の形態による、準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号を求める方法のブロック図である。
【図２Ａ】１つの実施の形態による、ＱＣ  ＬＤＰＣ符号を求めるための一例の概略図である。
【図２Ｂ】１つの実施の形態による、ＱＣ  ＬＤＰＣ符号を求めるための一例の概略図である。
【図３Ａ】行列およびグラフ表現におけるサイクルを形成する経路の例を示す図である。
【図３Ｂ】行列およびグラフ表現におけるサイクルを形成する経路の例を示す図である。
【図４】ＨＱＣ  ＬＤＰＣ符号を表すツリー行列の一例である。
【図５Ａ】プロトグラフの例である。
【図５Ｂ】プロトグラフの例である。
【図６】プロトグラフの例である。
【図７Ａ】図６のプロトグラフから導出されたタナーグラフの例である。
【図７Ｂ】図６のプロトグラフから導出されたタナーグラフの例である。
【図８】制限された２レベル階層ＱＣ  ＬＤＰＣ符号を表すツリー行列の要素の一例を示す図である。
【図９】本発明の１つの実施の形態による高ガースＱＣ  ＬＤＰＣ符号を構築するための方法のブロック図である。
【図１０】１つの実施の形態による、山登り法によるガース最大化のブロック図である。
【図１１】本発明の幾つかの実施の形態を用いる様々なシステムの概略図である。
【発明を実施するための形態】
【００２５】
システムおよび方法の概観
図１は、準巡回（ＱＣ）低密度パリティ検査（ＬＤＰＣ）符号１５０を求めるための方法１００のブロック図を示している。ＱＣ  ＬＤＰＣ符号は、該ＱＣ  ＬＤＰＣ符号が所定のガース１１７を有するように、連結性行列（Ｃ）１１０によって表されるプロトグラフに従って求められる。本方法のステップは、プロセッサ１０１によって実行される。ＱＣ  ＬＤＰＣ符号１５０は、メモリ（図示せず）内に格納することができ、該ＱＣ  ＬＤＰＣ符号１５０を用いてデータ１６０を符号化して（１７０）、無線チャネルまたは有線チャネルを介した送信のための符号化データ１８０を生成することができる。このデータもメモリ内に格納することができる。
【００２６】
本発明の幾つかの実施の形態は、所定のガースによって示される連結性行列の幾つかの要素が複製線に沿って複製されて、拡張された連結性行列が形成される場合、該拡張された連結性行列に対応する階層準巡回（ＨＱＣ）ＬＤＰＣ符号を、複製線に沿ってスカッシングし、ＱＣ  ＬＤＰＣ符号を生成することができるという認識に基づいている。ＨＱＣ  ＬＤＰＣ符号を表す巡回部分行列の行列は、複数のレベルを含み、各レベルは、巡回部分行列によって形成される。特に、レベルを形成する巡回部分行列は、巡回部分−部分行列を含み、複数のレベルについて、以下同様である。
【００２７】
図２Ａおよび図２Ｂは、プロトグラフ２１０等のプロトグラフに従ってＱＣ  ＬＤＰＣ符号を求める非限定的な例を示している。この例は、方法１００のステップを説明するのに役立ち、本発明の範囲を限定することを意図していない。
【００２８】
「プロトグラフ」は、タナーグラフの分類を導出するのに用いることができるテンプレートである。プロトグラフ内の各ノードは、タナーグラフ内のノードの「タイプ」を表す。ノードは、プロトグラフから導出されたタナーグラフにおいてｐ回複製される。例えば、プロトグラフ２１０は、１、２、および３でラベル付けされた３つのタイプの変数ノードと、ＡおよびＢでラベル付けされた２つのタイプの検査ノードとを含む。このプロトグラフに基づいてタナーグラフを導出するために、タイプＡの各検査ノードは、タイプ１の３つの変数、タイプ２の２つの変数、およびタイプ３の１つの変数に連結される一方、タイプＢの各検査ノードは、タイプ２の２つの変数およびタイプ３の１つの変数に連結されるべきである。
【００２９】
全てのプロトグラフは、連結性行列によって等価に表すことができる。連結性行列は、プロトグラフ内の検査タイプ数に等しい行数と、変数タイプ数に等しい列数とを有する。連結性行列内の各要素は、プロトグラフ内で検査ノードのタイプを変数ノードのタイプに連結する複数のエッジに対応する重みである。例示のために、プロトグラフ２１０は、連結性行列２０５
【数１】
0005843733.tif 000002
によって表すことができる。
【００３０】
図２Ａに示すプロトグラフは、本方法を示す目的で提供されるほんの一例にすぎない。図５Ａおよび図５Ｂは、本方法の入力として用いることができるプロトグラフの他の例を示している。これらのプロトグラフは、「片側空間結合符号（one-sided spatially coupled codes）」を表す。これらのプロトグラフにおいて、ビットタイプおよび検査タイプを連結する複数のエッジが存在することに留意されたい。
【００３１】
本発明の幾つかの実施の形態は、連結性行列の要素の値が所定のパターン１１５を形成する場合、プロトグラフの「直接変換」によって得られるＱＣ  ＬＤＰＣ符号は、不可避的に長さ６または８の短いサイクルを有するという別の認識に基づいている。所定のパターンは、ガース固有である。例えば、所望のガースまたは所定のガースが少なくとも１０である場合、パターンは、２よりも大きい値を有する少なくとも２つの要素または３よりも大きい値を有する少なくとも１つの要素を有する連結性行列の行または列を含む。例えば、連結性行列２０５は、１０に等しいガースによって示されるパターン１１５に従う行２１２および列２１４を含む。
【００３２】
このため、不可避的な短いサイクルを有することなくＱＣ  ＬＤＰＣ符号を得るために、連結性行列は、複製線１２７、例えば、線２１６および２２５に沿って複製され、拡張された連結性行列１２５が生成される。複製は、パターン１１５によって示された行数または列数に対応する複数の中間ステップを有することができる。図２Ａに示す例では、複製線は、拡張された連結性行列２２０を形成する線２１６および２２５、並びに最終的に２３０を含む。本明細書において用いられるとき、複製線とは、パターンを形成する要素がその上で複製される線である。通常、複製線は、行列の行間または列間の線である。複製線は、いずれの行または列が複製されるかに関する情報を保持する。
【００３３】
次に、拡張された連結性行列１２５に対応する階層準巡回（ＨＱＣ）ＬＤＰＣ符号１３５が求められる（１３０）。例えば、拡張された連結性行列２３０は、階層準巡回（ＨＱＣ）ＬＤＰＣ符号ファミリー２４０に変換することができ、ＨＱＣ  ＬＤＰＣ符号のガースが最適化されるように、ＨＱＣ  ＬＤＰＣ符号２５０が選択される（２４５）。１つの実施の形態は、以下に示すように、山登り法による手順を用いてガースを最適化する。
【００３４】
図２Ｂに示す行列２６０は、ＨＱＣ  ＬＤＰＣ符号を表す行列１３５の一例である。行列２６０は、「基本行列」である。幾つかの実施の形態では、ＨＱＣ  ＬＤＰＣ符号は、以下でより詳細に説明するように、多項式パリティ検査行列によって表され、多項式パリティ検査行列は、基本行列にコンバートされ、行列が生成される。本発明の例では、行列２６０は、４×４の巡回部分行列を含み、重みＩのＱＣ  ＬＤＰＣ符号を表す。
【００３５】
行列１３５は、拡張された連結性行列１２５Ｃ’に対応する。このため、行列１３５の少なくとも幾つかの要素を除去して、元の連結性行列Ｃ１１０のＱＣ  ＬＤＰＣ符号を生成する。特に、様々な実施の形態において、行列１３５は、複製線に沿ってスカッシングされる（１４０）。通常、拡張された連結性行列の行または列は、基本行列のＮ個の行または列に対応する。したがって、スカッシングによって複製線の両側において基本行列から行または列が除去される。図２Ａおよび図２Ｂの例では、Ｎは、４に等しく、すなわち、拡張された連結性行列２３０の各列が行列２６０内の４つの列に対応する。このため、スカッシングは、複製線の両側において行列２６０から２つの列を除去することを含む。具体的には、複製線２２５の両側で２つの列２６５が除去され、行列２７０が生成される。同様に、複製線２１６の両側で２つの行２７５が除去され、行列２８０が生成される。
【００３６】
行列２８０は、ＱＣ  ＬＤＰＣ符号１５０の一例である。模範行列（exemplar matrix）から見て取ることができるように、本発明の幾つかの実施の形態によって求められたＱＣ  ＬＤＰＣ符号１５０は、特殊な構造を有する。符号は、部分行列を含む。例えば、線２８５によって示すように、符号２８０は、６つの部分行列を含む。各部分行列２８１は、巡回構造を有するが、部分行列の要素の値は、線２９０および２９５等の遷移線を越えると、巡回フローを変化させる。これは、ＨＱＣ  ＬＤＰＣ符号を表す行列をスカッシングすることによって、符号２８０が形成されるためである。
【００３７】
本方法１００の上記のステップは、一組の例を用いて以下でより詳細に説明される。これらの例は、本発明の範囲を限定することを意図するものではない。
【００３８】
準巡回ＬＤＰＣ符号
ＱＣ  ＬＤＰＣ符号を全体として検討する前に、「重みＩ（Ｊ，Ｌ）正則」ＱＣ  ＬＤＰＣ符号と呼ばれる重要な特殊な事例を定義することが有用である。これらの符号のパリティ検査行列は、それぞれがｐ×ｐの巡回置換行列であるＪ・Ｌの部分行列から構成される。
【００３９】
Ｉｉ，ｐが、ｉ個の位置だけｐ×ｐの恒等行列を循環的に右シフトすることによって得られる、巡回置換行列または「巡回シフト行列」を表すものとする。ここで、０≦ｉ≦ｐ−１である。このためＩ０，ｐは、ｐ×ｐの恒等行列である。この開示では、ｐに対する依存を抑え、Ｉｉ，ｐの代わりにＩｉと書く。例として、ｐ＝４である場合、
【数２】
0005843733.tif 000003
である。
【００４０】
重みＩ（Ｊ，Ｌ）のＱＣ  ＬＤＰＣ符号のパリティ検査行列は、下式（１）である。
【００４１】
【数３】
0005843733.tif 000004
【００４２】
そのような符号のブロック長は、Ｎ＝ｐＬである。
【００４３】
Ｉｋ＝（Ｉ１）ｋを用いて、パリティ検査行列を下式（２）のように書き換えることができる。
【００４４】
【数４】
0005843733.tif 000005
【００４５】
行列Ｈは、ダミー変数ｘの冪乗であるエントリーを有する行列として、下式（３）のように、抽象的に表すこともできる。
【００４６】
【数５】
0005843733.tif 000006
【００４７】
行列Ｈ（ｘ）は、エントリーがｘの多項式であるパリティ検査行列に一般化することができ、結果として、下式（４）のような標準的なＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列となる。
【００４８】
【数６】
0005843733.tif 000007
【００４９】
ここで、１≦ｊ≦Ｊ、１≦ｌ≦Ｌについて、下式（５）の関係がある。
【００５０】
【数７】
0005843733.tif 000008
【００５１】
バイナリＱＣ  ＬＤＰＣ符号の場合、多項式係数ｃｓ［ｊ，ｌ］は０または１である。
【００５２】
例１  Ｃを、下式（６）のように、パリティ検査行列によって記述される長さ９のＱＣ  ＬＤＰＣ符号とする。
【００５３】
【数８】
0005843733.tif 000009
【００５４】
この符号の場合、Ｊ＝２、Ｌ＝３、およびｐ＝３であり、行列Ｈは、下式（７）のように書くことができる。
【００５５】
【数９】
0005843733.tif 000010
【００５６】
パリティ検査行列の多項式バージョンは、下式（８）となる。
【００５７】
【数１０】
0005843733.tif 000011
【００５８】
ＱＣ  ＬＤＰＣ符号は、該ＱＣ  ＬＤＰＣ符号のパリティ検査行列内の巡回部分行列の中の最大重みに従って、または等価に、該ＱＣ  ＬＤＰＣ符号のパリティ検査行列内の多項式の最大重みに従って分類することができる。多項式の重みは、その多項式内の非ゼロ項の数である。「重みＭ」のＱＣ  ＬＤＰＣ符号は、Ｈ（ｘ）内の全ての多項式エントリーｈｊ，ｌ（ｘ）の中の最大重みがＭであるＱＣ  ＬＤＰＣ符号として定義される。
【００５９】
例１の符号においてｗｔ（ｈ２，３（ｘ））＝２であり、すなわち、ｈ２，３（ｘ）＝ｘ１＋ｘ２は、２項式であるので、かつ全ての１≦ｊ≦Ｊ、１≦ｌ≦Ｌについてｗｔ（ｈ２，３（ｘ））≧ｗｔ（ｈｊ，ｌ（ｘ））であるので、例１の符号は、重みＩＩのＱＣ  ＬＤＰＣ符号である。
【００６０】
この説明において、重みＩのＱＣ  ＬＤＰＣ符号の基本行列を、符号、すなわち、ｌｏｇｘ（Ｈ（ｘ））を定義する冪乗のＪ×Ｌの行列（巡回シフト）であると定義し、ここで、エントリーごとに対数が取られ、全ゼロ部分行列を示すために、ｌｏｇｘ（０）を−１であると定義する。例えば、パリティ検査行列（３）に対応する基本行列は、下式（９）である。
【００６１】
【数１１】
0005843733.tif 000012
【００６２】
ＱＣ  ＬＤＰＣ符号のグラフ表現
ＬＤＰＣ符号は、該ＬＤＰＣ符号のパリティ検査行列Ｈによって表すこともできるし、等価に該ＬＤＰＣ符号のタナーグラフによって表すこともできる。ＬＤＰＣ符号のタナーグラフは、符号語ビットを表す「変数」ノードと、パリティ検査を表す「検査」ノードとを含む２部グラフである。ここで、変数ノードは、Ｈ内の対応するエントリーが非ゼロである場合にのみ、エッジによって検査ノードに連結される。ノードの次数は、該ノードに入るエッジ数として定義される。
【００６３】
「プロトグラフ」は、タナーグラフの分類を導出するテンプレートとして用いることができる。プロトグラフ内の各ノードは、タナーグラフ内のノードの「タイプ」を表す。ノードは、プロトグラフから導出されたタナーグラフにおいてｐ回複製される。
【００６４】
図６は、３つのタイプ（１，２，３）の変数ノードおよび２つのタイプ（Ａ，Ｂ）の検査ノードを有するプロトグラフ例を示している。タイプＡの各検査は、３つのタイプのそれぞれの１つの変数に連結され、タイプＢの各検査は、タイプ２の１つの変数およびタイプ３の２つの変数に連結される。同様に、タイプ１の各変数は、タイプＡの１つの検査に連結され、以下同様である。
【００６５】
図７Ａおよび図７Ｂは、ｐ＝３である、図６のプロトグラフから導出された２つのタナーグラフを示している。特定のプロトグラフに対応する多くの可能なタナーグラフが存在し、これらのタナーグラフは、必ずしも準巡回構造を有する必要がない。図７Ａのタナーグラフは、準巡回構造を有しない。対照的に、図７Ｂのタナーグラフは、準巡回構造を有し、実際に、例１において与えられたＱＣ  ＬＤＰＣ符号のパリティ検査行列を有する。
【００６６】
プロトグラフは、連結性行列によって等価に記述することができる。連結性行列は、プロトグラフ内の検査タイプ数に等しい数の行、および変数タイプ数に等しい数の列を有する。連結性行列内の各エントリーは、プロトグラフ内に、検査ノードタイプを変数ノードタイプに連結する幾つのエッジが存在するかを記述する。例えば、図１に示すプロトグラフの連結性行列Ｃは、下式（１９）である。
【００６７】
【数１２】
0005843733.tif 000013
【００６８】
特定のプロトグラフによって規定されるテンプレートから準巡回パリティ検査行列Ｈ（ｘ）を導出するために、対応する連結性行列内の各エントリーを、該エントリーに等しい重みの多項式と置き換えることができる。この手順は、ＱＣ  ＬＤＰＣ符号へのプロトグラフの「直接変換」と呼ばれる。
【００６９】
例えば、式（１０）において与えられる連結性行列Ｃを有するプロトグラフは、下式（１１）のパリティ検査行列を有するＱＣ  ＬＤＰＣ符号に直接変換することができる。
【００７０】
【数１３】
0005843733.tif 000014
【００７１】
ここで、ａ、ｂ、ｃ、ｄ、ｅ、およびｆは、０とｐ−１との間の整数の指数であり、ｅ≠ｆである。
【００７２】
多項式のためにいずれの指数を選ぶかに依拠して、ＱＣ  ＬＤＰＣ符号へのプロトグラフの多数の可能な直接変換が存在する。例えば、連結性行列（１０）は、下式（１２）のパリティ検査行列を有するＱＣ  ＬＤＰＣ符号に直接コンバートすることができる。
【００７３】
【数１４】
0005843733.tif 000015
【００７４】
ＱＣ  ＬＤＰＣ符号におけるサイクル
サイクルは、タナーグラフ内のノードを通る経路であり、検査ノードと変数ノードとの間を交互に行き来し、同じノードで開始および終了する。パリティ検査行列符号の観点で、サイクルは、行列の同じ行で開始および終了する、行列を通る一連の交互の垂直水平運動として特徴づけることができる。（列に沿った）垂直運動は、サイクルの次のステップを形成する同じ変数ノードに連結された第２のエッジに対応する。（行に沿った）水平運動は、経路の一部分を形成する同じ検査ノードに連結された２つのエッジに対応する。
【００７５】
例えば、パラメータＪ＝４、Ｌ＝９、およびｐ＝３を有する重みＩのＱＣ  ＬＤＰＣ符号のパリティ検査行列を検討する。この例では、パリティ検査行列は、パリティ検査行列において長方形パターンに配列された４つの３×３の巡回シフト部分行列を含む。図３Ａおよび図３Ｂは、これらの４つの行列のパラメータの２つの選択を示している。図３Ａは、それぞれパラメータａ＝０、ｂ＝１、ｃ＝２、およびｄ＝１を有する行列３１１〜３１４を示している。パラメータ｛ａ，ｂ，ｃ，ｄ｝は、恒等行列からのシフトを示している。図３Ｂは、それぞれのパラメータａ＝０、ｂ＝ｃ＝ｄ＝１を有する行列３２１〜３２４を示している。
【００７６】
サイクルが存在するための必要十分条件は、基本行列を通る経路が、開始エントリーに戻るとき、該経路が開始した巡回シフト行列の同じ列に戻ることである。例えば、４つ全ての行列を通る経路を検討する。経路３１０によって長さ４のサイクルが生じる。一方、図３Ｂの例では、巡回シフト選択が僅かに異なり、巡回シフト行列の同じ列への戻りは、基本行列の回りをさらに２回通過した後に初めて生じ、その結果、長さ１２のサイクルを有する経路３２０となる。
【００７７】
結果として、１組のｐ個のサイクルを生じる｛ａ，ｂ，ｃ，ｄ｝に対する条件は、以下の方法に従って計算することができる。所与の経路に沿った近傍の置換行列と関連付けられたシフトインデックスの交代和を計算する。ここで、全ての奇数のシフトインデックスは、加算されるのではなく減算される。例えば、図３Ａおよび図３Ｂの左側の経路を検討する。和は、−ａ＋ｂ−ｃ＋ｄである。和における近傍シフトインデックス間の各差は、巡回置換行列のいずれの列、すなわち、いずれの変数ノードを経路が通過するかにおけるシフトに対応する。経路の終わりにおいて差の合計がゼロ（ｐを法とする）となる場合のみ、経路は、開始置換行列において同じ変数ノードに戻り、それによってサイクルを形成する。図３Ａの例の場合、長さ４のサイクルが存在する条件は、下式（１３）である。
【００７８】
【数１５】
0005843733.tif 000016
【００７９】
これは、ａ＝０、ｂ＝１、ｃ＝２、ｄ＝１の場合に満たされるが、ａ＝０、ｂ＝ｃ＝ｄ＝１では満たされない。
【００８０】
下式（１４）のような２×３の多項式パリティ検査行列によって定義された重みＩＩの符号のより複雑な例を検討する。
【００８１】
【数１６】
0005843733.tif 000017
【００８２】
また、下式（１５）の順序付けされた数列を検討する。
【００８３】
【数１７】
0005843733.tif 000018
【００８４】
ここで、Ｏ内の各対（ｊ，ｌ）は、１≦ｊ≦Ｊ＝２および１≦ｌ≦Ｌ＝３を満たす。この順序付けされた数列は、Ｈ（ｘ）を通る一連の直線的な運動を指定する。ここで、各対内の第１の数は、Ｈ（ｘ）の行を指定し、第２の数は、Ｈ（ｘ）の列を指定する。タナーグラフを通る候補サイクルを指定するために、幾つかの実施の形態は、係数インデックスｓを、
【数１８】
0005843733.tif 000019
となるようにＯ内の各対（ｊ，ｌ）と関連付ける。ここで、式（５）に従ってｃＳ［ｊ，ｌ］が定義される。この係数インデックスの数列をＳで表す。数列内の各ステップがタナーグラフ内の別個のエッジをトラバースすることに対応することを保証するには、Ｏ内の近傍対（ｊ−，ｌ−）および（ｊ＋，ｌ＋）並びにＳ内の対応する近傍係数インデックスｓ−およびｓ＋の次のもの、すなわち、（ｊ−，ｌ−）＝（ｊ＋，ｌ＋）の場合、対応するインデックスｓ−≠ｓ＋であることを必要とする。
【００８５】
候補サイクルは、ｐを法とするＳ内の係数インデックスの交代和がゼロに等しい場合に実際にサイクルである。本発明の例では、係数インデックスのそれぞれの（順序付けされた）集合のために、下式（１６）、（１７）の２つの選択肢を検討する。
【００８６】
【数１９】
0005843733.tif 000020
【００８７】
これらの選択肢のそれぞれが、符号のタナーグラフを通る長さ６のサイクルに対応する。３を法とする交代和は、ゼロに等しいことを検証することができる。それぞれ、これらの和は、下式（１８）、（１９）である。
【００８８】
【数２０】
0005843733.tif 000021
【００８９】
不都合なことに、より高い重みのＱＣ  ＬＤＰＣ符号は、不可避的に短いサイクルを含む。任意の重みＩＩＩのＱＣ  ＬＤＰＣ符号が不可避的に長さ６のサイクルを含む。また、重みＩＩのＱＣ  ＬＤＰＣ符号のパリティ検査行列Ｈ（ｘ）が同じ行または同じ列内に２つの重み２の多項式を含む場合、その符号は、不可避的に８サイクルを有する。
【００９０】
これらの不可避的な６サイクルおよび８サイクルは、直接変換を用いて、いずれのプロトグラフを、高ガースを有する準巡回符号にコンバートすることができるかに対して、重大な制限を課す。例えば、プロトグラフが、３つのエッジによって検査タイプに連結された変数タイプを有する場合、直接変換によって不可避的に、得られるＱＣ  ＬＤＰＣ符号が６サイクルとなる。この欠点は、方法１００を用いる本発明の実施の形態によって克服される。１０以上のガースを有するＱＣ  ＬＤＰＣ符号を求めるために、幾つかの実施の形態は、階層ＱＣ  ＬＤＰＣ符号を用いる。
【００９１】
階層ＱＣ  ＬＤＰＣ符号
階層ＱＣ  ＬＤＰＣ（ＨＱＣ  ＬＤＰＣ）符号は、レベルから形成される。各レベルは、準巡回構造を有する部分行列によって形成される。構造は、少なくとも２つの等価で相補的な形式で、すなわち、１つは、ＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列の観点で、もう１つは、これらのＨＱＣ  ＬＤＰＣ符号の「ツリー構造」の観点で指定することができる。
【００９２】
例２：例えば、下式（２０）において指定されるｐ＝８の多項式パリティ検査行列を検討する。多項式エントリーのうちの任意のものの最も高い重みが２（例えば、ｈｌ，３（ｘ）＝ｘ１＋ｘ７）であり、行列内に１２個の列が存在するので、これは、長さ９６の重みＩＩのＱＣ  ＬＤＰＣ符号である。
【００９３】
【数２１】
0005843733.tif 000022
【００９４】
一方、このパリティ検査行列は、該パリティ検査行列を階層ＱＣ  ＬＤＰＣ符号にするさらなる構造を有する。特に、この例では、（２０）の多項式の各３×３の部分行列は、３×３の部分行列の２×２の部分行列の左側および右側双方の組と同様に巡回構造を有する。
【００９５】
標準的なＱＣ  ＬＤＰＣ符号において基礎をなす巡回部分行列を表すのにダミー変数ｘの多項式を用いるのと同様に、式（２０）における変数ｘによって表される巡回行列およびｘの多項式の各３×３の部分行列内の巡回配置の双方を表すのに、２つのダミー変数ｘおよびｙの２変量多項式を用いることができる。後者の巡回構造は、ダミー変数ｙによって表される。さらなるダミー変数ｚによって３×３の巡回部分行列の２×２の巡回構造をさらに表すことができる。
【００９６】
このため、この例の幾つかの実施の形態は、式（２０）の６×１２の多項式パリティ検査行列Ｈ（ｘ）を、下式（２１）に従って２×４の２部多項式パリティ検査行列Ｈ（ｘ，ｙ）に変換する。
【００９７】
【数２２】
0005843733.tif 000023
【００９８】
幾つかの実施の形態は、プロセスを繰り返して、Ｈ（ｘ，ｙ）を、下式（２２）に従って１×２の３変量多項式パリティ検査行列Ｈ（ｘ，ｙ，ｚ）に変換する。
【００９９】
【数２３】
0005843733.tif 000024
【０１００】
多項式パリティ検査行列（２０）、（２１）、および（２２）への、この符号のパリティ検査行列の３つの表現のそれぞれは、この３レベルＨＱＣ  ＬＤＰＣ符号の階層における「レベル」に対応する。
【０１０１】
ＨＱＣ  ＬＤＰＣ符号を構築するとき、幾つかの実施の形態は、他の方向に進み、すなわち、Ｈ（ｘ，ｙ，ｚ）のような行列をＨ（ｘ）に拡張し、その後、最終的にエントリーが１およびゼロである全パリティ検査行列に拡張する。多項式行列を拡張するには、全てのレベルにおける巡回行列のサイズが知られなくてはならない。
【０１０２】
より正式には、ＨＱＣ  ＬＤＰＣ符号は、以下の定義によって説明することができる。
【０１０３】
定義１：Ｋ個のレベルを有するＨＱＣ  ＬＤＰＣ符号が、Ｋ個の変数のＪ［Ｋ］×Ｌ［Ｋ］の多変量多項式パリティ検査行列Ｈ（・）によって定義される。Ｈ（・）のｊ番目の行およびｌ番目の列（１≦ｊ≦Ｊ［Ｋ］，１≦ｌ≦Ｌ［Ｋ］）のエントリーは、Ｋ個の変数ｘ［１］，．．．，ｘ［Ｋ］にわたるＫ変量多項式ｈｊ，ｌ（・，．．．，・）である。ｘ［Ｋ］（１≦ｋ≦Ｋ）におけるこれらの多項式のうちの任意のものの最大指数はｐ［ｋ］−１である。項
【数２４】
0005843733.tif 000025
（ここで、全てのｋについて０≦ｓｋ≦ｐ［ｋ］−１）と関連付けられる係数は、
【数２５】
0005843733.tif 000026
である。これらの定義を用いて、下式（２３）のＪ［Ｋ］・Ｌ［Ｋ］の多項式によって符号を定義した。
【０１０４】
【数２６】
0005843733.tif 000027
【０１０５】
そのような符号のパリティ検査行列は、Ｈ（ｘ［１］，．．．，ｘ［Ｋ］）のＪ［Ｋ］・Ｌ［Ｋ］個のエントリーのそれぞれを、下式（２４）の部分行列と置き換えることによって得られる。
【０１０６】
【数２７】
0005843733.tif 000028
【０１０７】
ここで、
【数２８】
0005843733.tif 000029
は、クロネッカー積を表す。再帰的関係Ｊ［Ｋ−１］＝Ｊ［Ｋ］・ｐ［Ｋ］およびＬ［Ｋ−１］＝Ｌ［Ｋ］・ｐ［Ｋ］（ここで、０≦ｋ≦Ｋ）を定義すると、このように構築されたパリティ検査行列は、
【数２９】
0005843733.tif 000030
個の行と、
【数３０】
0005843733.tif 000031
個の列とを有する。
【０１０８】
例２（続き）：この例の符号は、３レベルＨＱＣ  ＬＤＰＣ符号である。定義１を用いてこの例を説明するために、まずｘをｘ［１］とし、ｙをｘ［２］とし、ｚをｘ［３］とする。
【０１０９】
この例では、ｐ［１］＝８、ｐ［２］＝３、ｐ［３］＝２である。したがって、Ｊ［３］＝１、Ｌ［３］＝２；Ｊ［２］＝２、Ｌ［２］＝４；Ｊ［１］＝６、Ｌ［１］＝１２；およびＪ［０］＝４８、Ｌ［０］＝９６である。
【０１１０】
例えば、（２２）式の項ｈ１，１（ｘ，ｙ，ｚ）を、下式（２５）のように書き換えることができる。
【０１１１】
【数３１】
0005843733.tif 000032
【０１１２】
ここで、下式（２６）
ｃ２，０，０［１，１］＝ｃ１，２，０［１，１］＝ｃ７，２，０［１，１］＝ｃ７，１，１［１，１］＝ｃ０，２，１［１，１］＝ｃ６，２，１［１，１］＝１                （２６）
の場合を除いて、全ての係数
【数３２】
0005843733.tif 000033
がゼロである。
【０１１３】
１つの変数のＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列Ｈ（ｘ［１］）の式（４）において与えられる形式を生成するために、幾つかの実施の形態は、第１のレベルを除く全てについて、下式（２７）の構造を用いる。各ｈｉ，ｌ（ｘ［１］，．．．，ｘ［Ｋ］）をｘ［１］の多項式行列と置き換えることができる。
【０１１４】
【数３３】
0005843733.tif 000034
【０１１５】
行列Ｈ（ｘ［１］）は、サイズＪ［１］×Ｌ［１］である。非ゼロ係数ｃ０，２，１［１，１］およびｃ６，２，１［１，１］に対応するｈ１，１（ｘ［１］，ｘ［２］，ｘ［３］）の最終項、すなわち、
【数３４】
0005843733.tif 000035
を検討する。式（２７）によれば、Ｈ（ｘ［０］）へのこの項の寄与は、
【数３５】
0005843733.tif 000036
であり、ここで、
【数３６】
0005843733.tif 000037
である。
【０１１６】
式（２７）の形式は、幾つかのＨＱＣ  ＬＤＰＣ符号の構造を明らかにする。行列
【数３７】
0005843733.tif 000038
の各行および各列は、正確に１つの非ゼロ要素を有する。係数
【数３８】
0005843733.tif 000039
が非ゼロである場合、置換行列
【数３９】
0005843733.tif 000040
がこれらの非ゼロ要素のそれぞれのロケーションにおいて追加される。
【０１１７】
ＨＱＣ  ＬＤＰＣ符号のツリー構造
任意のＨＱＣ  ＬＤＰＣ符号のツリー構造は、例えば、以下の定義２に基づいて、ラベル付けされたツリーの行列によって表すことができる。以下の定義の動機となる基本的観測は、任意のＨＱＣ  ＬＤＰＣ符号を定義する多項式の非ゼロ項が、ラベル付けされたツリーによって表すことができる階層クラスタリングを有するということである。正式に、そのようなラベル付けされたツリーを以下のように定義する。
【０１１８】
定義２：ＫレベルＨＱＣ  ＬＤＰＣ符号を定義するＫ個の変数のＪ［Ｋ］×Ｌ［Ｋ］の多変量多項式パリティ検査行列Ｈ（・）内のエントリーに対応するラベル付けされたツリーＴがＫ個のレベル（１，．．．，Ｋ）によって定義される。各ツリーのルートノードは、最上位（Ｋ番目の）レベルにおける単一のノードである。レベルｋにおける各ノード（１≦ｋ≦Ｋ）は、該ノードを下の次のレベルのノードに連結する複数のエッジを有する。エッジ数は、集合｛１，．．．，ｐ［ｋ］−１｝内の整数である。
【０１１９】
図４は、３レベル階層ＱＣ  ＬＤＰＣ符号のツリー構造の一例を示している。レベルｋにおけるノードの下の各エッジが集合｛０，１，．．．，ｐ［ｋ］−１｝内の整数によってラベル付けされている。エッジが同じ親を共有する場合、すなわち、上位レベルの同じノードに連結されている場合、エッジは、「兄弟」と呼ばれる。兄弟ノードのエッジラベルは、別個であるように制約される。最下位ノードの下のエッジを「リーフ」と呼ぶ。｜Ｔ［ｋ］｜を用いて、レベルｋにおけるＴのエッジ数、すなわち、レベルｋにおける親ノードを有するエッジの集合を表す。ツリー４１０は、Ｔ１，１であり、ツリー４２０は、Ｔ１，２である。
【０１２０】
例２で論考した符号は、図４に示す２つのラベル付けされたツリーの行列によって特徴付けられる。ツリー４１０は多項式ｈ１，１（ｘ，ｙ，ｚ）を特徴付け、ツリー４２０は、式（２２）に指定するように、ｈ１，２（ｘ，ｙ，ｚ）を特徴付ける。
【０１２１】
定義３：ＫレベルＨＱＣ  ＬＤＰＣ符号のツリー構造は、ラベル付けされたツリーＴ＝｛Ｔｊ，ｌ｝（１≦ｊ≦Ｊ［Ｋ］、１≦ｌ≦Ｌ［Ｋ］）の行列によって指定される。Ｔｊ，ｌの各リーフに、単一の非ゼロ係数
【数４０】
0005843733.tif 000041
を１対１で関連付ける。リーフからルートノードまでの一意の経路上のエッジラベルがｅ１，．．．，ｅｋである場合、リーフと関連付けられた非ゼロ係数は、
【数４１】
0005843733.tif 000042
である。
【０１２２】
ある特定の場合（全ゼロ多項式に対応する）、「ヌル」ツリーを定義することを望む。これは、存在しないツリーである（したがって、全ての係数がゼロとなるようなエッジが存在しない）。特殊なシンボル＊を用いてヌルツリーを表す。
【０１２３】
ツリーＴｊ，ｌのレベルＫの下のエッジ数は、ｈｊ，ｌ（ｘ［１］，．．．，ｘ［Ｋ］）において現れるｘ［Ｋ］の別個の冪乗数を示す。レベルＫ−１における各ノードは、これらの項のうちの１つに対応する。レベルＫ−１におけるノードのそれぞれの下のエッジ数は、その項と関連付けられたｘ［Ｋ−ｌ］の別個の冪乗数を示し、ツリーを下って以下同様である。ツリー内のリーフ数は、多項式ｈｊ，ｌ（ｘ［１］，．．．，ｘ［Ｋ］）内の項数に等しい。（全ての（ｊ，ｌ）対にわたる）最下位レベルノードのうちの任意のものの下のリーフの最大数は、符号の重み（重みＩ、重みＩＩ等）を表す。エッジラベルは、非ゼロ多項式を定義する指数を示す。
【０１２４】
レベルｋにおけるノードのうちの任意のものの下のリーフの最大数によって、階層符号のきめ細かい「レベルｋの重み」を定義することもできる。階層符号は、異なるレベルにおいて異なる重みを有することができ、例えば、図４に示すツリー構造を有する例２からの符号は、レベル１（最も低いレベル）において重みＩＩであり、レベル２において重みＩＩＩであり、レベル３において重みＩＩである。
【０１２５】
任意のＨＱＣ  ＬＤＰＣ符号を、定義１に定義するように該ＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列の観点で定義することもできるし、等価に、定義３に定義するように該ＨＱＣ  ＬＤＰＣ符号のツリー構造の観点で定義することもできる。
【０１２６】
階層ＱＣ  ＬＤＰＣ符号におけるサイクル
高ガースＨＱＣ  ＬＤＰＣ符号を構築することを可能にするために、該高ガースＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列を調べることによって、該高ガースＨＱＣ  ＬＤＰＣ符号がそのタナーグラフにおいて特定の長さを有する否かを識別することができる必要がある。以下は、ＨＱＣ  ＬＤＰＣ符号が特定の長さのサイクルを有するための、該符号の多項式パリティ検査行列に対する必要十分条件である。標準的なＱＣ  ＬＤＰＣ符号におけるサイクルと比較して、ＨＱＣ  ＬＤＰＣ符号におけるサイクルは、以下の定義および定理に従って、全ての階層レベルにおいて同時にサイクルである必要がある。
【０１２７】
定義４：ＨＱＣ  ＬＤＰＣ符号のＫ変量のＪ［Ｋ］×Ｌ［Ｋ］の多項式パリティ検査行列Ｈ（・）を通る長さ２Λの経路Ｐは、２つの集合ＯおよびＳによって指定される。すなわち、Ｐ＝｛Ｏ，Ｓ｝である。
【０１２８】
第１の集合Ｏは、下式（２９）となるような順序付けされた数列である。
【０１２９】
【数４２】
0005843733.tif 000043
【０１３０】
全ての（ｊ，ｌ）∈Ｏについて｜Ｃ［ｊ，ｌ］｜＞０であり、ここで、集合Ｃ［ｊ，ｌ］は、下式（３０）のように、非ゼロであるＨ（・）のｊ番目の行およびｌ番目の列における多項式内の一組の係数であると定義される。
【０１３１】
【数４３】
0005843733.tif 000044
【０１３２】
第２の集合Ｓは、下式（３１）のような、係数インデックスの長さＫのベクトルの集合である。
【０１３３】
【数４４】
0005843733.tif 000045
【０１３４】
ここで、表記によって暗に意味されているように、全てのｔ（１≦ｔ≦２Λ）について（ｊｔ，ｌｔ）∈Ｏであり、｜Ｓ｜＝｜Ｏ｜である。
【０１３５】
さらに、ｓ［ｊ，ｌ］のｋ番目の座標ｓｋ［ｊ，ｌ］は、全ての（ｊ，ｌ）∈Ｏについて０≦ｓｋ［ｊ，ｌ］≦ｐ［ｋ］−１を満たし、全ての（ｊ，ｌ）∈Ｏについてｃｓ［ｊ，ｌ］［ｊ，ｌ］∈Ｃ［ｊ，ｌ］を満たす。ここで、ｃｓ［ｊ，ｌ］［ｊ，ｌ］は、
【数４５】
0005843733.tif 000046
の簡略表記である。
【０１３６】
Ｏの連続要素が同一である、すなわち、あるｔ（１≦ｔ≦２Λ）について（ｊｔ，ｌｔ）＝（ｊｔ＋１，ｌｔ＋１）である場合、ｓ［ｊｔ，ｌｔ］≠ｓ［ｊｔ＋１，ｌｔ＋１］である。
【０１３７】
定理１：Ｋ変量のＪ［Ｋ］×Ｌ［Ｋ］の多項式パリティ検査行列Ｈ（・）を通る経路長２Λの経路Ｐ＝｛Ｏ，Ｓ｝は、全てのｋ（１≦ｋ≦Ｋ）について、下式（３２）である場合にのみ、タナーグラフの長さ２Λのサイクルに対応する。
【０１３８】
【数４６】
0005843733.tif 000047
【０１３９】
ここで、各ｋ（１≦ｋ≦Ｋ）について、交代和Σ［ｋ］は、下式（３３）によって定義される。
【０１４０】
【数４７】
0005843733.tif 000048
【０１４１】
定理２：Ｋレベル階層ＱＣ  ＬＤＰＣ符号が少なくとも２（Λ＋１）のガースを有するための必要十分条件は、以下のとおりである。最大でも２Λの長さ（少なくとも４、最大でも２Λの経路長）の多項式パリティ検査行列を通る全ての経路について、条件（３２）は、少なくとも１つのｋ（１≦ｋ≦Ｋ）について成り立たない。
【０１４２】
例として、（２０）および（２１）において、それぞれ指定される多項式パリティ検査行列Ｈ（ｘ）およびＨ（ｘ，ｙ）を再び検討する。まず、Ｈ（ｘ）によって指定される符号の非階層記述を検討する。経路Ｐ｛Ｏ，Ｓ｝をトラバースする長さ４のサイクルが存在する。ここで、
【数４８】
0005843733.tif 000049
である。これは順に、４つの多項式
【数４９】
0005843733.tif 000050
に対応する。ｃ２［０，０］、ｃ１［１，０］、ｃ７［１，５］、およびｃ０［０，５］を選択した結果、
【数５０】
0005843733.tif 000051
となる。和を計算すると、下式（３４）となる。
【０１４３】
【数５１】
0005843733.tif 000052
【０１４４】
ここで、この符号について、ｐ［１］＝８である。この例は、一般表記において、非階層ＱＣ  ＬＤＰＣ符号におけるサイクルの試験を確認する。
【０１４５】
階層的視点から同じサイクルを検討する。式（２１）の２レベル表現Ｈ（ｘ，ｙ）に関連して、タナーグラフを通る同じサイクルが順序付けされた数列
【数５２】
0005843733.tif 000053
に対応する。ここで、多項式ｘ２＋（ｘ＋ｘ７）ｙ２およびｘ７ｙ＋（１＋ｘ６）ｙ２を得る。これらはそれぞれ、
【数５３】
0005843733.tif 000054
および
【数５４】
0005843733.tif 000055
である。同じサイクルは、係数インデックス
【数５５】
0005843733.tif 000056
に対応する。
【０１４６】
各係数の第１の部分インデックスが１レベルビューにおいて選択された係数の部分インデックスに対応することに留意されたい。経路に沿った交代和は、
【数５６】
0005843733.tif 000057
である。ここで、この符号についてｐ［１］＝８およびｐ［２］＝３である。
【０１４７】
ＨＱＣ  ＬＤＰＣ符号は、ＱＣ  ＬＤＰＣ符号の一般化であり、不可避的なサイクルも有する可能性もある。特に、符号を定義するツリー行列におけるいずれかのラベル付けされたツリーが３つのリーフを有する場合、任意のＨＱＣ  ＬＤＰＣ符号について長さ６のサイクルが不可避的に存在することになる。ＨＱＣ  ＬＤＰＣ符号を定義するラベル付けされたツリーの行列のいずれかの行またはいずれかの列において、ともに２つのリーフを有するラベル付けされたツリーの対が存在する場合、不可避的に８つのサイクルが存在することになる。
【０１４８】
制限された２レベルＨＱＣ  ＬＤＰＣ符号
本発明の方法の１つの実施の形態は、「制限された２レベル」ＨＱＣ  ＬＤＰＣ符号と呼ぶＨＱＣ  ＬＤＰＣ符号を用いる。「制限された２レベル」が暗に意味するように、制限された２レベルＨＱＣ  ＬＤＰＣ符号内の階層は、２つのレベルしか有しない。さらなる「制限」は、第１の（最も低い）レベルの重みが１であることである。これらの符号のツリー構造記述の観点で、ラベル付けされたツリーは、全て、図８に示すような形式を有し、最下レベルにおけるノードは、それぞれ、正確に１つのリーフを有する、すなわち、リーフは、兄弟を有しない。第２のレベルにおけるノードは、任意の数のエッジを有することができる。
【０１４９】
制限された２レベル符号が２つのレベルを有することは、該制限された２レベル符号が、２つのダミー変数Ｈ（ｘ，ｙ）の多項式パリティ検査行列によって記述されることを意味する。重み１を有する最も低いレベルへの制約は、行列Ｈ（ｘ，ｙ）内の任意の重みｗの多項式が下式（３５）の形式を有しなくてはならないことを意味する。
【０１５０】
【数５７】
0005843733.tif 000058
【０１５１】
ここで、全てのＡｉ個の指数は、別個でなくてはならない。通常通り、指数は、ｘ指数について０とｐ［１］−１との間の範囲をとり、ｙ指数について０とｐ［２］−１との間の範囲をとる整数である。
【０１５２】
上述したように、「直接変換」は、プロトグラフと等価の連結性行列を、多項式エントリーが連結性行列のエントリーと等しい重みを有した多項式パリティ検査行列Ｈ（ｘ）と置き換えることによって、プロトグラフを標準的なＱＣ  ＬＤＰＣ符号にコンバートする。プロトグラフを制限された２レベルＨＱＣ  ＬＤＰＣ符号にコンバートする同様の直接変換が存在する。ある直接変換は、連結性行列を、多項式エントリーがそれぞれ制限された形式の式（３５）を有し、重みが連結性行列内のエントリーに等しい２変量多項式パリティ検査行列Ｈ（ｘ，ｙ）と置き換える。
【０１５３】
例えば、図６に示すプロトグラフ６００に対応する連結性行列は、下式（３６）である。
【０１５４】
【数５８】
0005843733.tif 000059
【０１５５】
この行列は、下式（３７）の多項式パリティ検査行列を有する２レベルの制限されたＨＱＣ  ＬＤＰＣ符号に直接変換される。
【０１５６】
【数５９】
0005843733.tif 000060
【０１５７】
ここで、ａ、ｂ、ｃ、ｄ、ｅ、およびｆは、０とｐ［１］−１との間の整数の係数であり、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、およびＦは、Ｅ≠Ｆを満たす０とｐ［２］−１との間の整数の係数である。
【０１５８】
符号設計パイプライン
図９は、本発明の１つの実施の形態による高ガースＱＣ  ＬＤＰＣ符号を構築する方法のブロック図を示している。実施の形態は、以下のように説明される。所定のプロトグラフ９０１および所定のガース９０２が本方法への入力である。プロトグラフ９０１は、連結性行列９０３として表される（９１０）。連結性行列内のエントリーの重みおよび相対的ロケーションに依拠して、実施の形態は、連結性行列を拡張して（９２０）拡張された連結性行列９０４を得る。次に、拡張された連結性行列は、制限された２レベルＨＱＣ  ＬＤＰＣ符号９０５の多項式パリティ検査行列ファミリーに直接変換される（９３０）。この実施の形態では、パラメータｐ［２］のために４の値を用いる。次に、ガース最適化手順（以下でより詳細に説明される）を用いて残りの自由度を最適化する（９４０）ために、実施の形態は、全ての不可避的でない６サイクルおよび８サイクルを排除し、対応するタナーグラフ内に不可避的な短いサイクルのみを有するＨＱＣ  ＬＤＰＣ符号９０６を得る。実施の形態は、そのＨＱＣ  ＬＤＰＣ符号の多項式パリティ検査行列を、等価な基本行列９０７にコンバートする（９５０）。最後に、「スカッシング手順」９６０を用いて不可避的なサイクルを除去し、本発明の所望の高ガースＱＣ  ＬＤＰＣ符号９０９を得る。
【０１５９】
実施の形態は、符号を、スカッシングに適合する形で拡張し、対象のパラメータに合う有効なパリティ検査行列を生成する。この手順の結果生じるＬＤＰＣ符号は、ＱＣ  ＬＤＰＣとなり、ＨＱＣ  ＬＤＰＣ符号ではないが、最終構造は、ＨＱＣ  ＬＤＰＣ符号の構造と同様である。
【０１６０】
示すように、手順は、最初にプロトグラフの連結性行列Ｃを生成する。例示の目的で、プロトグラフ２１０が図２Ａに示されているプロトグラフであると仮定する。「拡張」手順は、以下のように機能する。まず、値２以上の２つ以上の要素、または値３の単一の要素を有する行列の各行を、複製のためにマーキングする。値２以上の２つ以上の要素を有する各列もマーキングする。次に、Ｃを拡張して新たな連結性行列Ｃ’を生成する。連結性行列Ｃ’において、複製のためにマーキングされたＣ内の行のそれぞれが複製される。次に、再び拡張を行い、マーキングされた列のそれぞれを複製することによって、Ｃ’からＣ’’を生成する。スカッシングに着手するときに明らかとなるように、行列Ｃ’およびＣ’’において、いずれの行および列が互いの複製版であるかを追跡しなくてはならない。
【０１６１】
本発明の例において、連結性行列２０５は、下式（３８）である。
【０１６２】
【数６０】
0005843733.tif 000061
【０１６３】
この連結性行列における第１の行２１２は、値３を有する要素（およびまた、値２以上の２つの要素）を含み、このため、これをマーキングし、第２の列２１４も、値２以上の２つの列を有するのでマーキングする。第１の行を複製すると、下式（３９）が得られる（２２０）。
【０１６４】
【数６１】
0005843733.tif 000062
【０１６５】
ここで、第２の列を複製すると、拡張された連結性行列２３０として下式（４０）が得られる。
【０１６６】
【数６２】
0005843733.tif 000063
【０１６７】
Ｃ’’において、第１の行および第２の行、並びにまた第２の列および第３の列が、互いの複製版として追跡される。これは、複製線２１６および２２５によって表記される。
【０１６８】
次に、拡張された連結性行列２３０Ｃ’’を、ｐ［２］＝４を有する２レベルの制限されたＨＱＣ  ＬＤＰＣ符号ファミリーを表す多項式パリティ検査行列２４０Ｈ’’（ｘ，ｙ）に直接変換する。この変換を、１つの追加制約の下で行う。制約は、複製された行の対または複製された列の対内のｙ指数が、互いに同一でなくてはならないことである。ｐ［１］の値は、設計パラメータとして残される。
【０１６９】
本発明の例では、拡張された連結性行列２３０Ｃ’’は、多項式パリティ検査行列２４０であるＨ’’（ｘ，ｙ）に直接変換され、下式（４１）の形式が得られる。
【０１７０】
【数６３】
0005843733.tif 000064
【０１７１】
この行列の第１の行および第２の行並びに第２の列および第３の列（複製線を横切る行および列）におけるｙ指数は、互いに同一となるように制限されていることに留意されたい。そうでない場合、全ての指数は、任意のｘ指数ａｉについて０≦ａｉ≦ｐ［１］−１を満たし、任意のｙ指数Ａｉについて０≦Ａｉ≦ｐ［２］−１＝３を満たす自由なパラメータである。
【０１７２】
次のステップにおいて、ガース最大化手順（以下でより詳細に説明される）を適用して自由度を最適化し（９４０）、不可避的な短いサイクルを除く短いサイクルが存在しないように一組のｘ係数ａｉおよびｙ係数Ａｉを生成する。例えば、ｐ［１］＝２００で本発明のガース最大化手順を用いると、Ｈ’’（ｘ，ｙ）におけるｘ係数およびｙ係数の下式（４２）の選択２５０によって不可避的な短いサイクルを除いて６サイクルまたは８サイクルが生成されないことがわかる。
【０１７３】
【数６４】
0005843733.tif 000065
【０１７４】
上記の多項式パリティ検査行列を有する符号は、下式（４３）によって与えられる基本行列Ｂ’’２６５を有する重みＩのＱＣ  ＬＤＰＣ符号と等価である。
【０１７５】
【数６５】
0005843733.tif 000066
【０１７６】
基本行列Ｂ’’は、４×４の巡回部分行列で構成される。
【０１７７】
ここで、拡張された連結性行列Ｃ’’に対応する基本行列Ｂ’’を有する。本発明の手順における次のステップは、Ｂ’’から列および行を除去して、本発明の元の連結性行列Ｃに対応する基本行列を得る。
【０１７８】
まず、連結性行列Ｃ’’の各列は、基本行列Ｂ’’の４つの列に対応する。本発明の手順の次のステップにおいて、Ｃ’’における複製としてマーキングされた列に焦点を当てる。残りの２つの列を保持し、Ｃ’’内の複製された対の左列に対応する４つから、Ｂ’’内の右の２つの列を除去し、また、Ｃ’’内の複製された対の右列に対応する４つから、Ｂ’’内の左の２つの列を除去するが、右の２つの列を保持する。
【０１７９】
本発明の例において、Ｃ’’２３０の第２の列および第３の列は、複製としてマーキングされるため、Ｂ’’２６０から４つの列２６５を除去し、間引きされた行列２７０Ｂ’を得る。
【０１８０】
この段階において、連結性行列Ｃ’内の各行は、基本行列Ｂ’内の４つの行に対応する。ここで、Ｃ’において複製としてマーキングされた行に焦点を当てる。Ｃ’内の複製された対内の最上行に対応する４つからＢ’内の最も上の２つの行を保持し、Ｃ’内の複製された対の最下行に対応する４つからＢ’内の最も下の２つの行を保持する。このさらなる間引き手順Ｂによって得られた基本行列を呼び出す。これは、本発明の元の連結性行列Ｃに対応する基本行列である。
【０１８１】
本発明の例では、Ｃ’２２０の第１の行および第２の行は、複製としてマーキングされている。これは、行列２７０から最も上の４つの行２７５を除去し、最終基本行列２８０を得るべきであることを意味する。このため、最終的に、下式（４４）を得る。
【０１８２】
【数６６】
0005843733.tif 000067
【０１８３】
最終基本行列Ｂによって定義される符号は、階層ＱＣ  ＬＤＰＣ符号ではない。なぜなら、その基本行列は、巡回しない４×４の部分行列から構築されているためである。それでも、この符号は、元のプロトグラフによって定義される分類のメンバーである。本発明の例では、基本行列内の４つの行および４つの列の各群は、検査タイプまたはビットを定義する。このため、本発明の例では、Ｂの構造から、各第１の検査タイプが第１のタイプの３つのビットに連結され、第２のタイプの２つのビットに連結され、プロトグラフによる必要に応じて、以下同様に連結される。
【０１８４】
さらに、本発明の拡張およびスカッシング手順は、符号から全ての「不可避的な」６サイクルおよび８サイクルを除去する。なぜなら、全てのそのような不可避的なサイクルは、関連する４×４の部分行列内の３つの行または３つの列を用い、そのような各部分行列から２つの行または列を除去してあるためである。このため、ガース最大化手順が全ての他の６サイクルおよび８サイクルを除去すると仮定すると、得られるＱＣ  ＬＤＰＣ符号は、少なくとも１０のガースを有することになる。
【０１８５】
ガース最大化手順
実施の形態の１つの変形形態では、多項式パリティ検査行列ファミリー９０５内の自由度９４０は、山登り法によるガース最大化を用いて最適化され、そのタナーグラフ内の唯一の短いサイクルが「不可避的な」短いサイクル９０６であるＨＱＣ  ＬＤＰＣ符号が生成される。
【０１８６】
図１０は、１つの実施の形態による、山登り法によるガース最大化のブロック図を示している。ガース最大化への入力は、ＨＱＣ  ＬＤＰＣ符号ファミリーを指定するラベル付けされていないツリーＴｉ，ｊの行列である。出力は、各ツリーの各エッジの値である。所望のツリー構造を有する符号からランダムに選択された符号を用いて手順を初期化する（１０１０）。これは、兄弟エッジが別個のラベルを有しなくてはならないという制約を受けるツリーＴにラベルをランダムに割り当てることを意味する。
【０１８７】
手順への別の入力は、各サイクルタイプと関連付けられた「コスト関数」１０１１である。用いられるコスト関数は、所望のガース未満の長さを有する現在の符号におけるサイクル数に依拠する。より短いサイクルがより長いサイクルよりもコストが高くなるよう重み付けされるように、重みベクトルが用いられる。例えば、ガース１０が望ましい場合、４サイクルごとに１００のコストを割り当て、６サイクルごとに１０のコストを割り当て、８サイクルごとに１のコストを割り当てる。本方法は、コストを最小にするので、まず４サイクルを除去し、次に６サイクルを除去し、最終的に８サイクルを除去する。
【０１８８】
ガース最大化法は、一連のエッジラベルを反復的に更新する。各反復において、本方法は、単一のエッジラベルを、コスト関数の最大の低減を達成する値に変更する。例えば、エッジごとに、そのラベルを全ての他の可能なラベルに変更するコストを記述する「コスト行列」が求められる（１０３０）。コスト行列から、各可能なエッジを各可能なラベルに変更するコストの改善を与える「利得行列」を生成することができる（１０４０）。
【０１８９】
本方法は、いかなる単一の係数も、コスト（したがって望ましくないサイクル数）をさらに低減する値に変更することがもはやできないときに終了する。正式には、これは、利得行列における最大利得がもはや正でない（１０５０）ことを意味する。この時点で、ＨＱＣ  ＬＤＰＣ符号を表す現在のツリー行列を出力する（１０７０）。正の利得がある場合、これは、コストを改善することができることを意味し、コストを最も改善するエッジラベル変化を用いてツリー行列１０６０を適切に更新する。次に、コスト行列を再度求め（１０３０）、反復する。
【０１９０】
エッジラベルに対する兄弟制約を受けて更新が実行される。これによって符号のツリー構造が保持され、このため、符号のプロトグラフ構造は、更新の下で不変である。単一のエッジラベルにおける変化は、複数の符号係数（そのエッジの子孫のツリー内のリーフ数に等しい）に対し滴下効果を有することができる。
【０１９１】
本発明の実施の形態によって求められるＱＣ  ＬＤＰＣ符号は、図１１に示すシステム１１００等による復号化手順および符号化手順の双方において用いることができる。本発明の実施の形態は、メモリ内に格納することができる、高ガースを有する準巡回低密度パリティ検査（ＱＣ−ＬＤＰＣ）符号１１５０を構築する方法１００を提供する。次に、符号化器１１２０によって、そのような符号を用いて、データ、例えば、ソース１１１０によって生成されるｋ個のシンボルの情報ブロックｕ［ａ］１１０１を符号化することができる。符号化データは、Ｎ個のシンボルを含む符号語ｘ［ｎ］１１０２として雑音チャネル１１３０を通じて送信することができる。チャネルは、通信チャネルとすることができる。「チャネル」は、ストレージ媒体とすることもできる。この場合、符号語は、後の検索のために媒体に書き込まれる。
【０１９２】
チャネルが符号語を破損させて信号ｙ［ｎ］１１０３にする可能性がある。次に、信号は、復号化器１１４０に渡される。復号化器１１４０は、ＱＣ−ＬＤＰＣ符号１１５０を用いて情報ブロックｕ［ａ］１１０１の再構築ｚ［ａ］１１０４を出力しようと試みる。
【０１９３】
本発明の上述した実施の形態は、多数の方法のうちの任意のものにおいて実施することができる。例えば、実施の形態は、ハードウェア、ソフトウェア、またはそれらの組合せを用いて実施することができる。ソフトウェアコードは、ソフトウェアにおいて実施されるとき、単一のコンピューターにおいて提供されているか複数のコンピューター間で分散されているかにかかわらず、任意の適切なプロセッサまたはプロセッサ群において実行することができる。そのようなプロセッサは、集積回路構成要素内の１つまたは複数のプロセッサとともに、集積回路として実装することができる。しかし、プロセッサは、任意の適切なフォーマットの回路部を用いて実装することもできる。
【０１９４】
また、コンピューターは、ラックマウント型コンピューター、デスクトップコンピューター、ラップトップコンピューター、ミニコンピューター、またはタブレットコンピューター等の複数の形式のうちの任意のもので実施することができることを理解すべきである。そのようなコンピューターは、企業ネットワークまたはインターネット等のローカルエリアネットワークまたはワイドエリアネットワークを含む任意の適切な形態の１つまたは複数のネットワークによって相互接続することができる。そのようなネットワークは、任意の適切な技術に基づくことができ、任意の適切なプロトコルに従って動作することができ、無線ネットワーク、有線ネットワーク、または光ファイバーネットワークを含むことができる。
【０１９５】
また、本発明の実施の形態は、一例が提供された方法として実施することができる。方法の一部として実行される動作は、任意の適切な方法で順序付けすることができる。したがって、動作が示されたものと異なる順序で実施される実施の形態を構築することができる。異なる順序には、幾つかの動作が例示的な実施の形態において一連の動作として示されている場合であっても、それらの動作を同時に実行することを含むことができる。
【０１９６】
特許請求の範囲における、請求項の構成要素を修飾する「第１の」、「第２の」等の順序を示す語の使用は、１つの請求項構成要素の別の請求項構成要素に対するいかなる優先度、優位性、若しくは順序、または方法の動作が実行される時間的順序もそれ自体が暗示するものではなく、単に、ある特定の名前を有する１つの請求項構成要素を、（順序を示す用語を用いることを除いて）同じ名前を有する別の要素と区別し、請求項構成要素間を区別するためのラベルとしてのみ用いられる。
【図１】
0005843733.tif 000068
【図２Ａ】
0005843733.tif 000069
【図２Ｂ】
0005843733.tif 000070
【図３Ａ】
0005843733.tif 000071
【図３Ｂ】
0005843733.tif 000072
【図４】
0005843733.tif 000073
【図５Ａ】
0005843733.tif 000074
【図５Ｂ】
0005843733.tif 000075
【図６】
0005843733.tif 000076
【図７Ａ】
0005843733.tif 000077
【図７Ｂ】
0005843733.tif 000078
【図８】
0005843733.tif 000079
【図９】
0005843733.tif 000080
【図１０】
0005843733.tif 000081
【図１１】
0005843733.tif 000082