(57)【要約】  通信システムにおいて受信したデータを階層的に復号する方法であって、複数の要素を含むコードワードを受信する工程（２００）と、コードワードに付随するパリティ検査行列の少なくとも１つの列の行をグループに分割することによって、複数の要素を確率値に変換する工程（２０４）と、グループの少なくともいくつかを別々に処理する工程（２０６）とを含む方法。
2008507240.tif 000002
【特許請求の範囲】
【請求項１】
通信システムにおいて受信されるデータを階層的に復号する方法であって、
複数の要素を含むコードワードを受信する工程と、
前記コードワードに付随するパリティ検査行列の少なくとも１つの列の行をグループに分割し、それらのグループの少なくともいくつかを別々に処理することによって前記複数の要素を確率値に変換する工程と、
を含む前記方法。
【請求項２】
請求項１記載の方法であって、グループの少なくともいくつかを処理する工程が、
グループの前記少なくとも１つの列について確率値を計算する工程と、
少なくとも１つの列の確率値の少なくともいくつかを組み合わせる工程と、
を含んでいる前記方法。
【請求項３】
請求項２記載の方法であって、組み合わせる工程が、前記少なくとも１つの列についてその他の処理が実質的に何も実行されていない時間内に実行される前記方法。
【請求項４】
請求項１記載の方法であって、パリティ検査行列の行をグループに分割する工程が、少なくとも１つのブロック行が次のブロック行と異なるグループに含まれるように前記少なくとも１つの列を分割する工程を含んでいる前記方法。
【請求項５】
請求項１記載の方法であって、複数の要素を変換する工程が、前記少なくとも１つの列の行が別の列の行と異なるグループに分割されるように複数の要素を変換する工程を含んでいる前記方法。
【請求項６】
システムであって、
１つのメモリに接続された複数の並列計算ブロックと、
前記計算ブロックに接続された複数のパリティ検査更新ブロック（ＰＣＵＢ）と、
ＰＣＵＢに接続された、各々が１つのメモリを含む複数のコラム・ストア・ブロック（ＣＳＢ）と、
を含み、
システムは、パリティ検査行列の少なくとも１つの列の少なくともいくつかの行をグループに分割し、
システムは、各グループを別々に処理する、
前記システム。
【請求項７】
請求項６記載のシステムであって、少なくともいくつかの行が、少なくとも１つのブロック行が次のブロック行と異なるグループに含まれるように分割される前記システム。
【請求項８】
請求項６記載のシステムであって、１つのブロック行が計算ブロックおよびＰＣＵＢによって処理されて１つのベクトルを生成する前記システム。
【請求項９】
請求項８記載のシステムであって、ベクトルがＣＳＢメモリに記憶される前記システム。
【請求項１０】
請求項６記載のシステムであって、システムは、
コードワードを受信する工程と、
コードワードに付随する確率を決定する工程と、
を含む階層的復号アルゴリズムを実行する前記システム。
【請求項１１】
請求項１０記載のシステムであって、システムは、
前記コードワードに付随するパリティ検査行列の少なくとも１つの列に関して、行列の行のうちの少なくともいくつかをグループに分割し、
各グループを別々に処理する、
ことによってコードワードに付随する確率を決定する工程を実行する、
前記システム。
【発明の詳細な説明】
【技術分野】
【０００１】
（背景）
多くのデータ通信技術に共通する１つの問題点は、雑音によってデータが破壊されることである。通信チャネルに関する信号対雑音比（ＳＮＲ）は、そのチャネル上を運ばれる通信の品質を表す１つの指標である。すなわち、それは、データを運ぶ信号のそのチャネル上に存在する雑音に対する相対的強度（距離および時間とともに減衰する）を意味する。これらの因子は、チャネル上で受信されるデータ・ビット又はシンボルが、送信されたデータ・ビット又はシンボルと比べて誤りである尤度（ｌｉｋｅｌｉｈｏｏｄ）に直接関連する。この尤度には、チャネル上での通信に関する誤りの確率が反映される。それは、通常、ビット誤り率（ＢＥＲ）で表現され、それは、受信され、誤りとして復号されたビットの送信された合計ビットに対する比率である。一般に、データ通信における誤りの尤度は、通信技術を開発するときに考慮すべき事項である。通信技術を実用的なものとするために、通信データにおける誤りを検出および修正する方法を取り入れることが必要である。
【０００２】
このために、データの冗長符号化を利用した誤りを検出および修正する技術が採用されている。一般に、冗長符号化は、送信されるデータ・ストリームの中に、何も付加的な情報を持たないが、受信されるデータ・ストリーム中に誤りが存在するかどうかを示すデータ・ビットを挿入することを含む。より複雑な符号では、誤りが存在していても、受信したデータ・ストリームから真の送信データを推定する能力を提供するものがある。
【発明の開示】
【発明が解決しようとする課題】
【０００３】
１つの復号技術は、階層的復号（ｌａｙｅｒｅｄ  ｄｅｃｏｄｉｎｇ）として知られている。階層的復号は、以下に詳細に説明するように、一般にグループ又は層の形になったパリティ検査行列（ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ）の行を処理する工程を含む。各層は、順番に処理されるが、各層の処理は、直前の層の処理で得られたデータに依存する。しかし、このような復号アーキテクチャは、各層の処理間に固有のデータ待ち時間（ｌａｔｅｎｃｙ）が存在するように設計される。例えば、パリティ検査行列の１つの層の処理を開始するためには、まずそれに先行する層の処理によって得られたデータを入手する必要がある。しかし、このデータは、直ちに利用できるものではない。それどころか、データは、処理に使用するために収集される目的地に向かうデコーダのパイプライン中にある。このようなデータ待ち時間は、デコーダの性能を低下させる。
【課題を解決するための手段】
【０００４】
（概要）
上述の問題点のすべて又はいくつかは、ＬＤＰＣ符号用の階層的復号方式を改善することによって解決する。１つの例示的実施の形態は、複数の要素を含むコードワード（ｃｏｄｅｗｏｒｄ）を受信し、そのコードワードに付随するパリティ検査行列の少なくとも１つの列の行をグループに分割（ｄｉｖｉｄｉｎｇ）し、それらのグループの少なくともいくつかを別々に処理することによって、それらの複数の要素を確率値に変換する工程を含む。
【０００５】
別の１つの実施の形態は、複数の列および行を有するパリティ検査行列に付随する、複数の要素を含むコードワードを受信し、そのパリティ検査行列の少なくともいくつかの列の少なくともいくつかの行をグループに分割（ｐａｎｔｉｔｉｏｎｉｎｇ）する工程を含み、各グループを別々に処理する工程を含む。
【０００６】
更に別の１つの実施の形態は、１つのメモリに接続された複数の並列計算ブロックと、それらの計算ブロックに接続された複数のパリティ検査更新ブロック（ＰＣＵＢ）と、各々が１つのメモリを含み、ＰＣＵBに接続された複数のコラム・ストア・ブロック（ＣＳＢ：ｃｏｌｕｍｎ  ｓｔｏｒｅ  ｂｌｏｃｋ）とを含む。このシステムは、パリティ検査行列の少なくとも１つの列の少なくともいくつかの行をグループに分割（ｐａｎｔｉｔｉｏｎｓ）し、各グループを別々に処理する。
【０００７】
本発明の例示的な実施の形態についての詳細な説明のために、ここで添付図面を参照する。
【０００８】
（詳細な説明）
以下の説明および特許請求の範囲において、用語「含んでいる」および「含む」は、非排他的意味で使用されており、従って、「含むが、それに限定されない」ことを意味するものとして解釈されるべきである。また、用語「接続する」又は「接続」は、間接的又は直接的な電気的接続のいずれかを意味する。従って、第１の装置が第２の装置に接続されるとき、その接続は、直接的な電気的接続であってもよいし、他の装置や接続手段を介した間接的な接続であってもよい。更に、Ｔ  Ｔという表記は、上下限の制限（ｃｅｉｌｉｎｇ  ｆｕｎｃｔｉｏｎ）を意味する。
【０００９】
以下の説明は、本発明の各種の実施の形態について行われる。それらの実施の形態のうちの１つ又は複数のものが好適なものであっても、開示された実施の形態は、本発明の範囲を限定するものとして解釈されるべきでないし、あるいは、利用されるべきものでもない。加えて、当業者であれば、以下の説明が幅広い応用を有しており、任意の実施の形態についての説明が実施の形態の一例となることのみを意図しており、本発明の範囲をその実施の形態に限定する意図がないことを理解されよう。
【実施例】
【００１０】
ここに開示されるものは、上述のデータ依存性を排除するように修正された階層的復号アルゴリズムである。これは、従来技術によるものと比べて復号性能において本質的に優れている。更に、任意の適切な通信システムにこの修正されたアルゴリズムを組み込むために使用されるハードウエア・システムが開示されている。詳細には、修正されたアルゴリズムは、パリティ検査行列のすべて又はいくつかの行を、各々が他のものと独立して処理されるようになった別々のグループに分割する工程を含む。どの１つのグループもパリティ検査マクロ行列の２つの連続した行を処理することがないため、上述のデータ待ち時間の問題が緩和又は解消される。
【００１１】
冗長符号の１つのクラスは、低密度パリティ検査（ＬＤＰＣ）符号である。この符号のクラスに従えば、１つの疎行列（ｓｐａｒｓｅ  ｍａｔｒｉｘ）Ｈがその符号を定義する。このペイロード・データ（すなわち、送信すべきデータ）の符号化又はコードワードｃは、ガロア場（Ｇａｌｏｉｓ  ｆｉｅｌｄ）ＧＦ（２）において次式を満たす。
【００１２】
（数１）
Ｈｃ＝０                      （１）
【００１３】
各コードワードｃは、ソース・メッセージｓと、そのソース・メッセージｓに対応するパリティ検査ビットとを組み合わせたものを含む。符号化ｃが送信され、チャネルによって加えられる雑音をｎとしたとき、受信するネットワーク要素は、信号ベクトルｒ＝ｃ＋ｎを受信する。受信機側のデコーダは、行列Ｈを知っているため、それは、ベクトルｚ＝Ｈrを計算することができる。しかし、ｒ＝ｃ＋ｎであり、Ｈｃ＝０であるため、次のようになる。
【００１４】
（数２）
ｚ＝Ｈｒ＝Ｈｃ＋Ｈｎ＝Ｈｎ            （２）
【００１５】
このように、復号プロセスは、ＧＦ（２）で次式を満足する最も疎なベクトルｘを見つける工程を含む。
【００１６】
（数３）
Ｈｘ＝ｚ                （３）
【００１７】
ベクトルｘは、雑音ベクトルｎの最良の推定となり、受信した信号ベクトルｒからそれを減算して符号化ｃを回復でき、そこから更に元のソース・メッセージｓを回復できる。
【００１８】
高性能のＬＤＰＣ符号のデコーダは、一般にハードウエアに組み込むことが難しい。ランダム符号が良い符号であるというシャノン（Ｓｈａｎｎｏｎ）の格言が成り立つ一方で、効率的なハードウエアを実現するのは、秩序である。符号の不規則性とハードウエアの効率性との間のこの困難なトレードオフを解決するために、ビリーフ伝搬（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）技術が、ある程度の効率性を実現するＬＤＰＣ復号の反復的実施を提供する。ビリーフ伝搬復号アルゴリズムは、また確率伝搬アルゴリズム、メッセージ・パッシング・アルゴリズム（ｍｅｓｓａｇｅ  ｐａｓｓｉｎｇ  ａｌｇｏｒｉｔｈｍ）、サム・プロダクト・アルゴリズム（ｓｕｍ−ｐｒｏｄｕｃｔ  ａｌｇｏｒｉｔｈｍ）とも呼ばれる。
【００１９】
反復的ビリーフ伝搬アルゴリズムは、ＬＤＰＣ符号の２進数パリティ検査特性をベースとする。正しいＬＤＰＣコードワード・ベクトルとパリティ検査行列の各行との積は、ゼロである。ビリーフ伝搬方式に従えば、受信されたデータは、入力ノードと検査ノードとを有する二分グラフの各入力ノード（すなわち、「ビット・ノード」）における入力確率を表すために用いられる。ビリーフ伝搬法の各反復において、ビット確率メッセージは、入力ノードから検査ノードに送られ、入力ノードに戻されて加算された更新値によってパリティ検査制約条件に従って更新される。データは、典型的には、次のように定義される対数尤度比（ＬＬＲ：ｌｏｇ  ｌｉｋｅｌｉｈｏｏｄ  ｒａｔｉｏ）として表される。
【００２０】
【数４】
2008507240.tif 000003
【００２１】
ここで、ｃは、チャネルを通して受信された符号化ビットである。
【００２２】
従来の実施において、ビリーフ伝搬アルゴリズムは、２つの値の行列を使用する。第１の行列Ｌは、ｊ入力ノードに対するＬＬＲを記憶し、第２の行列Ｒは、ｍパリティ検査ノード更新の結果を記憶する。ここで、ｍは、パリティ検査の行の指数であり、ｊは、パリティ検査行列Ｈの列（又は入力ノード）の指数である。この従来のやり方の汎用的演算は、第１のステップにおいて、各々のチェック・サムについてそのチェック・サムに使用される他の入力のうちの１つの入力ノード値の確率を推定することによってＲ値を決定する。このアルゴリズムの第２ステップは、各列について、その入力ノードが関与するパリティ検査行列の行からのその入力ノードに関するＲ値を組み合わせることによって、行列ＬのＬＬＲ確率値を決定する。次に、結果の確率値から「ハード」による判断がなされ、パリティ検査行列に与えられる。この２段階の反復的な方式は、式（１）が満足されるまで（ＧＦ（２）においてすべてのパリティ検査の行がゼロに等しい）、あるいは、別の収束条件が満たされるまで、あるいは、反復回数が上限回数に達するまで繰り返される。ＬＤＰＣ復号化については、ここに参照によって取り込まれる、同一出願人による「デジタル通信用のハードウエア効率の高い低密度パリティ検査符号（Ｈａｒｄｗａｒｅ−Ｅｆｆｉｃｉｅｎｔ  Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅ  ｆｏｒ  Ｄｉｇｉｔａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）」と題する米国特許出願第１０／３２９，５９７号（公開番号ＵＳ２００４／００３４８２８  Ａ１）に詳細に述べられている。
【００２３】
上述の私の出願番号１０／３２９，５９７号は、ビリーフ伝搬デコーダ回路への効率的なハードウエア実現に特にうまく適合できる低密度パリティ検査（ＬＤＰＣ）符号について述べている。詳細には、ＬＤＰＣ符号は、マクロ行列（ｍａｃｒｏ−ｍａｔｒｉｘ）として構成されており、それの行および列は、対応するパリティ検査行列のブロック行およびブロック列を表している。各々のゼロのエントリは、ｐｘｐ次元のすべてがゼロのサブ行列に対応する。逆に、非ゼロの各エントリは、巡回シフトされる識別行列のようなｐｘｐ次元の順列サブ行列（ｐｅｒｍｕｔａｔｉｏｎ  ｓｕｂｍａｔｒｉｘ）に対応する。ここでシフトは、マクロ行列の順列サブ行列のエントリの位置に対応する。このように、マクロ行列は、パリティ検査行列に対する「簡便表記法」の１つの形として機能する。マクロ行列の列がグループ化されることによって、マクロ行列グループの中の１つの列だけが任意の与えられた行中のパリティ検査サムに寄与するようになる。デコーダ回路は、いろんなデータ幅および深さで論理的に接続できるバンクの形に構成されるパリティ検査値推定メモリ（ｅｓｔｉｍａｔｅ  ｍｅｍｏｒｙ）を含む。並列加算器が外因性の推定値を発生し、それらがパリティ検査更新回路に与えられて、新しいパリティ検査値の推定を発生する。それらのパリティ検査値の推定は、メモリに戻して記憶され、またビット更新回路に送られて入力ノードに対する確率値を更新する。
【００２４】
反復的復号（ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ）のための１つの方式は、「階層的復号」として知られている。そこにおいて、上述のパリティ検査行列は、水平方向の層又は行の集合として見られ、各層は、１つのコンポネント符号を表す。階層的復号は、各々の連続した層に対して復号アルゴリズムを適用することによって実行される。特定の層に対する復号アルゴリズムの実行には、前の層の復号によって得られた計算結果の利用が含まれる。階層的復号アルゴリズムは、並列化された復号ハードウエアを用いて実行できるため、更に詳細には、階層的復号が本質的に従来のビリーフ伝搬アルゴリズムと異なるため、復号の性能は、階層的復号アルゴリズムおよび／又は並列化復号ハードウエアを使用しない復号プロセスの性能よりも優れている。
【００２５】
上述のビリーフ伝搬アルゴリズムは、次の式（５）−（１１）に示すように、階層的復号モードにおいて実行される。パリティ検査行列の行は、重なりのないサブセットにグループ化される。ここで、各サブセットの各列は、最大重み１を有する。すなわち、各サブセット中の各列は、最大１のエントリを有する。例えば、図１ａで、階層的復号は、ｐ行を含むパリティ検査マクロ行列１００の各行を復号プロセスの１つの層として取り上げて実行される。各サブセットは、１つのユニットとして処理され、サブセットは、１つずつ前のサブセットの結果を使用しながら次々と処理される。行列１００中の各々の「１」エントリは、図１ｂに示すように、ｐｘｐのサブ行列１０２を表す。これは、好ましくは、巡回シフトされる識別行列である。行列１００中の各々の「０」エントリは、ゼロのエントリで埋まったｐｘｐサブ行列を表す。
【００２６】
本質的に、階層的復号は、次の式（５）−（１１）を使用して、受信したコードワードｃの送信前の値を決定する工程を含む。実際に受信されるコードワードは、２進数ビットの代わりに有理数（ｆｒａｃｔｉｏｎｓ）（例えば、多値を取るエントリ（ｅｎｔｒｉｅｓ）又はソフト・データ（ｓｏｆｔ−ｄａｔａ））を含む。一般に、有理数は、パリティ検査行列の各エントリに対応するＲｍｊを含む行列Ｒを計算するために使用される。それらのＲｍｊ値は、列ごとに組み合わされてベクトルＬを形成する。ベクトルＬのエントリ値Ｌ（ｑｊ）は、受信したコードワードの各エントリが送信前に元々２進数「０」ビット又は「１」ビットであった数学的確率を表す。こうして、２進数ビットを有するベクトルｃが決まる。ベクトルｃの各エントリは、ベクトルＬの１つのエントリに対応する。例えば、ベクトルＬの第１エントリが、送信前にそのエントリが「０」ビットであったことを示す値を含む場合には、ベクトルｃの第１エントリには、「０」ビットが割り当てられる。同様に、ベクトルＬの第４エントリのエントリ値が、送信前にそのエントリが「１」であったことが最も確かであることを示す場合には、ベクトルｃの第４エントリには、「１」が割り当てられる。従って、復号の精度は、ベクトルｃおよびパリティ検査行列Ｈに関して（１）が真であることを検証することによって決定される。もしそれが真であれば、ベクトルｃは、それが送信側で送信されたように受信機側で再現されたということである。もし（１）が真でなければ、別の反復処理が実行される。この処理は、例えば、予め定められた反復回数が完了するとか、（１）が真であることが確認された後など、多様な条件のいずれかが満たされるときに終了する。
【００２７】
数学的に、この処理は、受信された多値のソフト・データを用いてＬＬＲ、Ｌ（ｑｊ）、Ｖｙの初期化推定で開始される。典型的には、加算的な白色ガウス雑音（ＡＷＧＮ）チャネルに関しては、この初期推定は、
【数５】
2008507240.tif 000004
となる。ここで、σ２は、チャネルの雑音を表す。次に行ごとの（ｐｅｒ−ｒｏｗ）（又は外因性の）ＬＬＲ確率が、チェック・サム・サブセットの各行ｍの各列ｊについて導かれる。
【００２８】
【数６】
2008507240.tif 000005
【００２９】
これらの行ごとの確率は、入力ノード値の確率に関する推定となり、行それ自身からの推定への寄与が排除される。少なくともいくつかの実施の形態では、次に下記の（６）に示すように、値Ａｍｉおよび符号値ｓｍＪを導くことができる。開示の範囲は、（６）−（１０）に与えられる式に限定されない。（６）−（１０）の任意の部分は、任意の他の演算又は近似によって置き換えることができる。更に、（６）−（１０）のすべてを代替的な適当なアルゴリズムで完全に置き換えることもできる。
【００３０】
【数７】
2008507240.tif 000006
【００３１】
（６）に対して、多くの計算形式の任意のもの、あるいは、（６）やそれの変形以外の任意の他の適当な計算／近似技法を使用することができるが、本発明の好適な実施の形態に従う関数Ψの例には、次のようなものがある。
【００３２】
【数８】
2008507240.tif 000007
【００３３】
関数Ψは、それ自身の負の逆関数である：Ψ（Ψ（ｘ））＝−｜ｘ｜。計算の便宜上、ｔａｎｈ（Ｌ／２）を次のように表すことができる。
【００３４】
【数９】
2008507240.tif 000008
【００３５】
符号（ｓｉｇｎ）は、次式から決まる。
【００３６】
【数１０】
2008507240.tif 000009
【００３７】
これは、各列自身の寄与を排除した、負の確率の数の奇数／偶数決定である。各値Ｆ？ｍ；-の更新された推定は、次のようになる。
【００３８】
【数１１】
2008507240.tif 000010
【００３９】
（１０）のｓｍ/項の前の負符号は、関数Ψがそれ自身の負の逆関数であることから意図的に含められている。このように、値Ｒｍｊは、それ自身、入力ノードに対する値を使用せずに、パリティ検査行列のｍ番目の行の他の入力ノードから導かれる入力ノード／に対するＬＬＲの推定に対応する。
【００４０】
復号反復の各々における第２ステップでは、各入力ノードに対するＬＬＲ推定が更新される。本発明の好適な実施の形態に従えば、これは、次のように各列（すなわち、各入力ノード）に対して実行される。
【００４１】
【数１２】
2008507240.tif 000011
【００４２】
ここで、推定値ＲｍＪは、この導出では、式（１０）から得られる最新の更新値である。この列推定は、ハード・デシジョン・チェック（ｈａｒｄ  ｄｅｃｉｓｉｏｎ  ｃｈｅｃｋ）に使用される。これは、この反復のための式（５）で使用されるＲｍｊ-の値と対照的である。これは、パリティ検査行列Ｈのこのサブセットについての前の反復から生成された値である。
【００４３】
反復によって誤りのない復号に収束したかどうかの判定は、列ごとのＬＬＲｓＬ（ｑｊ）に基づいてなされる。
【００４４】
【数１３】
2008507240.tif 000012
【００４５】
【数１４】
2008507240.tif 000013
【００４６】
次にコードワード・ベクトル
【数１５】
2008507240.tif 000014
がパリティ検査行列Ｈに提供されて、積がゼロであるかが決まる。これは、上で述べたように、コードワード・ベクトルｃが有効なコードワードであり、それからペイロード・データ部分が容易に抽出できることを示す。階層的復号は、ここに参照によって取り込まれる出願番号１０／８０６，８７９号の同一出願人による米国特許出願「デジタル通信用の階層的低密度パリティ検査復号（Ｌａｙｅｒｅｄ  Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｄｅｃｏｄｉｎｇ  ｆｏｒ  Ｄｉｇｉｔａｌ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）」に更に詳細に説明されている。
【００４７】
前に述べたように、パリティ検査マクロ行列は、複数の行および列を含む。マクロ行列の各エントリは、パリティ検査行列のｐｘｐ次元のサブ行列を表す。このように、マクロ行列の各行は、パリティ検査行列のｐ行を表し、またマクロ行列の各列は、パリティ検査行列のｐ列を表す。これらのｐ行は、まとめて１つのブロック行（すなわち、１つの層）を形成し、またｐ列は、まとめて１つのブロック列を形成する。階層的復号技術を採用するアルゴリズムでは、ｐ行を含むパリティ検査行列の層の各々が順番に処理される。各層の処理は、前の層の処理によって得られた結果に依存する。パリティ検査マクロ行列の各エントリは、ｐｘｐ次元のサブ行列を表す。サブ行列のサイズｐおよび並列化因子ｚは、一般にサイクル当たりにｚ行が処理されると仮定して、各層に対する最小の可能な処理時間を
【数１６】
2008507240.tif 000015
サイクルと決定する。しかし、デコーダの部品を通してｚ行又はｚ列のデータを移動させる際に含まれるデータおよび／又は処理の待ち時間が存在する。一般に、デコーダの各種ハードウエア層を通してデータ・パイプラインの遅延が存在する。これは、単一のクロック・サイクル中にデコーダの部品の少なくともいくつかを通してデータをプッシュできないためである。先に述べたように、階層的復号は、復号すべき各層が前の層に対してデータ依存性を有することを必須とする。このように、現在の層を復号する前に、デコーダの部品は、前の層の完了まで強制的に待たされることによって、前の層からのデータを現在の層の復号中に利用することができる。従って、層あたりの実効時間は、層あたりの総データ待ち時間および［ｐ／ｚ]の最小サイクル時間である。層の処理時間（すなわち、サイクル時間）は、データ待ち時間だけ増加する。このデータ待ち時間は、デコーダのスループットに対して本質的に負の影響を与える。
【００４８】
例えば、図１ａのパリティ検査マクロ行列１００を参照すると、最後の行が最初の行に巡回する場合を含み、非ゼロのエントリが別の非ゼロのエントリの直下に現れるとき、上述のデータ依存性の問題が発生する。データ依存性の問題は、上述のように、特別な行中の特別な列を処理するために必要なデータが手に入らないために発生する。マクロ行列１００の縦方向の列グルーピング１，３，５，６，７，８および９で、このデータ依存性の問題は、すべての列で発生する。グルーピング２および４では、データ依存性の問題は、最後の２つの列でのみ発生する。
【００４９】
上述のように、ベクトルＬの各成分Ｌ（ｑｊ）は、（５）の各々の前のＲｍｊ項を除去して、利用可能になり次第、（１１）の更新された項を加えるようにして、最新のＲｍｊ項を累積したものである。もしその項が利用できなければ、データ依存性の問題が発生する。このデータ依存性の問題は、列ｊについて、単一のＬ（ｑｊ）累積を、この／番目の、後に詳しく説明する列に相対的にＡおよびＢとラベル付けされた２つの別の累積（すなわち、グループ）に分割することによって解消される。ブロック行の各々もＡ又はＢとラベル付けされる。好適な実施の形態で、各ブロック列のブロック行は、別のブロック列のブロック行と異なるようにラベル付けされる。１つの与えられた列ｊに対して、Ａとラベル付けされたブロック行は、Ａの累積に付随し、またＢとラベル付けされたブロック行は、Ｂ累積に付随する。これと異なる任意の適切なラベル付けのやり方を採用してもよい。
【００５０】
少なくともいくつかの実施の形態では、累積Ａは、Ａとラベル付けされたそれらのブロック行からの項を含み、累積Ｂは、Ｂとラベル付けされたそれらのブロック行からの項を含む。このように、パリティ検査行列の各列に対して、Ｌ（ｑｊ）累積ＡおよびＢは、それぞれ、次のように表記することができる。
【００５１】
【数１７】
2008507240.tif 000016
【００５２】
【数１８】
2008507240.tif 000017
【００５３】
（１３）および（１４）は、それぞれ、等価的に（５）および（１１）によって実行される計算を含む。少なくともいくつかの実施の形態では、（１３）は、Ａとラベル付けされた行に対してのみ用いられ、（１４）は、Ｂとラベル付けされた行に対してのみ用いられる。項
【数１９】
2008507240.tif 000018
は、直前の反復から得られた（５）中の項に対応する。項Ｒｍｊは、（１１）で用いられる（１０）から最近求められた項に対応する。列ｊに関して、Ａ１ｊからＡＬｊの指数順は、パリティ検査行列によって定義されたように寄与する、Ａとラベル付けされたブロック行中の行を指す。同様に、Ｂ１ｊからＢＬｊの指数順は、パリティ検査行列によって定義されたように寄与する、Ｂとラベル付けされたブロック行中の行を指す。項
【数２０】
2008507240.tif 000019
は、反復の開始時でのこの列ｊに関するＬ変数の初期値である。それの値は、下記の（１５）によって決まる。
【００５４】
各々の反復の終わりに、特定の列ｊに関して、ＬＡＪおよびＬＢＪが組み合わされて全体的なＬ（ｑ’ｊ）項に対応する１つの項を形成する。この項は、L,-とラベル付けされて、次のように計算される。
【００５５】
【数２１】
2008507240.tif 000020
【００５６】
このＬｊは、次に
【数２２】
2008507240.tif 000021
と改めてラベル付けされ、後に次の反復に使用される。
【００５７】
少なくともいくつかの実施の形態のいくつかのケースでは、この修正されたアルゴリズムは、列／に関して、ブロック行ＡとＢとが交互に処理されるようにする。しかし、ブロック行ＡおよびＢは、必ずしも交互に処理する必要はなく、任意の順序で処理することができる。データ待ち時間の問題は、累積ＡおよびＢを適切に選択すれば、ＬＡＪ又はＬＢＪのいずれの計算でもパリティ検査行列の連続したブロック行の発生がなくなるため、回避される。少なくともいくつかの実施の形態において、グループＡ、ＢおよびＣのように付加的なグループを使用することができる。すなわち、ブロック行を２つの別々の累積にグループ分けする代わりに、ブロック行を３又はそれ以上の別々の累積にグループ分けすることができる。それらの累積は、２つの累積について用いられたのと同じように処理される。
【００５８】
図２は、修正されたアルゴリズムを説明するフロー図を示す。プロセスは、ソフト・データを含むコードワードを受信する工程（ブロック２００）から始まる。次に、すべて又はいくつかの列ｊについて
【数２３】
2008507240.tif 000022
およびＬＢＪが受信されたソフト・データに初期化される（ブロック２０２）。必ずしもすべての列である必要はないが、少なくとも１つの列について、上で説明したように、ブロック行がＡ又はＢのように指定される（ブロック２０４）。しかし、少なくともいくつかの実施の形態において、そのような指定は、アルゴリズムを実行するハードウエアの設計の段階で実行される。次に、修正されたアルゴリズムは、（６）、（９）および（１０）のように、ブロック行の少なくともいくつかの中で、少なくともいくつかの行ｍの少なくともいくつかの列ｊに対して計算される（ブロック２０６）。ブロック２０６に示すように、シンボルＬχｊは、関連するブロック行に依存して、また関連する列ｊがこの多重累積技法を採用しているかどうかに依存して、ＬＡＪ、ＬＢＪ又はＬ（ｑｊ）を指すように使用されている。代替となる本質的に等価なアルゴリズムや演算および／又は近似を（６）、（９）および（１０）の代わりに使用することができる。ブロック２０６で、（６）が計算される前に、まず、Ｌｘｊと、前の反復で得られた
【数２４】
2008507240.tif 000023
の値を使用して項Ｌ（ｑｍｊ）を更新する。しかし、最初の反復では、前の反復というのが存在しないため、
【数２５】
2008507240.tif 000024
にゼロの値が代入される。ブロック２０６では、（１０）が計算されたあとで、（６）の前に計算されたＬ（ｑｍｊ）の値と、現在の反復から得られたｆ？ｍ／の値とを用いてＬｘｊが更新される。
【００５９】
すべてのブロック行のプロセス２０８が処理されると、プロセスは、次に進む。そうでなければ、別のブロック行が処理される（ブロック２０８）。ブロック２１０では、各々の適用可能な列について、ＬＡｊおよびLey-が組み合わされて、（１５）のようにベクトルＬに対する値が得られる。また、ブロック２１０では、ＬＡｊとＬβ；-の値がＬｙの値にセットされる。適用可能な列（単数又は複数）に対するＬ／値が
【数２６】
2008507240.tif 000025
に変換されて、ベクトルＬが得られる（ブロック２１２）。これは、次にベクトルＬの確率に基づいてビット・ベクトルｃに変換される（ブロック２１４）。ＬＪ，ＬＱ）およびＬ（ｑｊ）の表記は、相互に交換可能であることを指摘しておく。これら３つの項の各々は、特別な列／に対するベクトルＬの値を示している。ブロック２１４でベクトルｃが決まったあとで、（１）が満足されない場合、あるいは、反復の最大回数に達していない場合、あるいは、その他の判定基準のいずれもが満足されない場合には、プロセスが繰り返される。そうでなければ、プロセスは、完了する（ブロック２１６）。
【００６０】
修正されたアルゴリズムは、達成される誤り率に対して負の効果を持つかもしれない。この負の効果は、問題が発生する列数を最小化するようにパリティ検査行列を設計して、修正されたアルゴリズムを適用しなければならない列数を減らすことによって最小化できる。例えば、図１ａのマクロ行列は、データ待ち時間の問題が発生する可能性を持つ１７個の列を有する。図１ｃに示すように、マクロ行列１００を、合計２４個の列のうち３つだけがデータ待ち時間の問題を含むように再設計することによって、誤り悪化を無視できる程度にすることができる。そのような再設計は、上で提示した修正されたアルゴリズムを数個の列に対して組み込めばよいことを意味し、残りの列には、上で述べた修正されたアルゴリズムを含む任意の適切なアルゴリズムを採用することができる。
【００６１】
追加の計算（１５）およびそれに付随する更新は、他の既知のアルゴリズムに存在せず、修正されたアルゴリズムに存在する。この計算とそれに付随する更新は、それらを実行するために追加の時間が必要となるため、アルゴリズムに対して一定の非効率性を導入する。そのような非効率性を最小化するために、計算および、いくつかの実施の形態では、それの更新は、好ましくは、プロセッサがパリティ検査行列の関連する列についてどんな計算も実行していない時間ギャップに実行される。１つのタイプのそのような時間ギャップは、エントリとして少なくとも１つのゼロを有するパリティ検査マクロ行列の列中に見出すことができる。詳細には、ゼロのエントリと同じ行を共有するその他の列が非ゼロのエントリを有する場合、プロセッサは、それらの非ゼロのエントリに対してアルゴリズムを実行する。階層的復号は、１つの行のすべての列又はほとんどすべての列に対してほとんど同時にアルゴリズムを実行する必要があるため、ゼロのエントリは、その間にその特別な列に対して何も計算が実行されていない「遊休」ポイントとして等価的に働く。そのような時間ギャップ又は遊休ポイントの時間が（１５）を計算するために利用される。さもなければ浪費される時間に（１５）が計算されるため、（１５）を計算するために追加の時間が不要となり、効率は、よい方向に影響される。いくつかの実施の形態では、（１５）の計算は、いくつかの反復について完全にスキップされる。
【００６２】
図３は、上述の修正されたアルゴリズムを実施するために用いられるハードウエア・システム３００を示す。ハードウエア・システム３００は、ストレージ・メモリ２９８、複数のパリティ検査更新ブロック（ＰＣＵＢ）３０２、複数のコラム・ストア・ブロック（ＣＳＢ）３０４、ルータ・ブロック３１０、リバース・ルータ・ブロック３１２および多重並列加算器ブロック３０６および３０８を含む。受信されたソフト・データは、データ・バス３５０を通してシステム３００に送られる。受信されたソフト・データは、最初にＣＳＢ３０４に送られて、そこでデータは、上述のように、ｊのすべての値について、ベクトルＬの成分Ｌ（ｑｊ）に初期化される。次に、ベクトルＬは、ＣＳＢ３０４に記憶される。データは、ＣＳＢ３０４からデータ・バス３５２を経てリバース・ルータ・ブロック３１２に送られ、そこでデータは、システム３００が要求する形に再構成される。
【００６３】
ベクトルＬの値
【数２７】
2008507240.tif 000026
は、次にデータ・バス３５４を経て、並列加算器ブロック３０６に送られる。並列加算器ブロック３０６で、各列について、（５）中の演算又は類似の演算／近似が実行される。それには、少なくともいくつかの実施の形態では、（１３）および（１４）又は（１３）および（１４）に類似した演算／近似が含まれる。詳細には、ＲｍＪの値が
【数２８】
2008507240.tif 000027
の値から差し引かれる。それらの減算の結果は、それぞれバス３５６および３５８を経て、ＰＣＵＢ３０２および並列加算器ブロック３０８に送られる。ＰＣＵＢ３０２は、演算（６）、（９）および（１０）又はそれらに等価な演算および／又は近似を実行する。それらの演算の結果は、バス３６０を経て並列加算器ブロック３０８に送られる。この結果は、またバス３６２を経て記憶装置２９８にも送られる。結果は、並列加算器ブロック３０８において、（１３）又は（１４）の一部である（１１）を実行するために用いられる。すなわち、並列加算器ブロック３０６での演算の結果がＰＣＵＢ３０２で計算されたＲｍ；-値に加えられて値ＬｘＪを生成する。これらの値は、バス３６４を使用して、それらの値を必要に応じて再構成するルータ・ブロック３１０に送られる。最後に、値は、バス３６６を経てＣＳＢ３０４に転送され、ＣＳＢ３０４に記憶されて、次の反復での使用に備える。
【００６４】
図４は、ＣＳＢ３０４の詳細な図を示す。ＣＳＢ３０４は、整列／シフト・モジュール３１４、アドレス発生モジュール３１６、マルチプレクサ３２０およびコラム・サム・メモリ３１８を含む。整列／シフト・モジュール３１４は、必ずしも同一の構造又は組成のものである必要はない。Ｌベクトル、ＬＡおよび／又はＬＢの値がコラム・サム・メモリ３１８に記憶される。少なくともいくつかの実施の形態では、ＬＡおよび／又はＬＢの値は、別々に記憶される。上で述べたように、ルータ・ブロック３１０からの値は、ＣＳＢ３０４に記憶される。書き込み演算の間に、これらの値は、バス３６８を経てＣＳＢ３０４に送られる。整列／シフト・モジュール３１４は、必要に応じてデータを構成するために用いられる。マルチプレクサ３２０は、バス３７０を経た送信チャネルのデータを通すか、あるいは、バス３７２を経たルータ・ブロック３１０からのデータを通す。アドレス発生モジュール３１６は、マルチプレクサ３２０を通過するデータをバス３７４を経てコラム・サム・メモリ３１８に記憶するために用いられる。逆に、読み出し演算の間には、データは、バス３７６を経てコラム・サム・メモリ３１８から読み出され、必要に応じてデータを再構成する整列／シフト・モジュール３１４を通過し、更にバス３７８を経て図３のリバース・ルータ３１２に送られる。
【００６５】
図５ａは、特定のブロック列に関して反復を開始する際の、発生する処理位相のシーケンスとメモリ演算のシーケンスとを時間ギャップなしで示す。図５ａは、５個の列に分割される。列５００は、処理されるセグメント（すなわち、ブロック行Ａ又はＢ）を示す。列５０２は、Ａ又はＢ行の他のＡ又はＢ行に対する指数番号を示す。列５０４は、実行されるアクション（すなわち、読み出し又は書き込み）を示す。列５０６は、タイミング情報を与える。列５０８は、プロセスがスタート／ストップ位相で発生するか、あるいは、メイン位相で発生するかを示す。これらの両方の場合について以下に詳しく説明する。
【００６６】
位相５１０は、スタート／ストップ位相であり、一般に、現在のブロック行について書き込み演算が完了しつつある一方で、次のブロック行について読み出し演算が始まっていることを意味する。このケースでは、ブロック行Ａ１がＣＳＢメモリ３１４から読み出されている。しかし、位相５１０は、ブロック行Ａ１（この列の最初のブロック行）を表しているため、ブロック行Ａ１に対して読み出し演算が開始されたこの時点で、完了している前の書き込み演算はない。この理由のため、ブロック行Ａ１の読み出し演算は、スタート／ストップ位相５１０のすべて又はいくらかを占有する。この位相のための時間が待ち時間であり、それは、データ・パイプラインを完全に通過するために要する時間（すなわち、データがＣＳＢを離れて、データが戻ってくるまでの時間）である。
【００６７】
位相５１２は、メイン位相であり、一般に単一ブロック行の主要部分が処理されていることを意味する。ここで、ブロック行Ａ１がメモリから読み出され、後にメモリに書き込まれる。この位相の時間は、最小のサイクル時間[ｐ／ｚ]と待ち時間との差である。位相５１４は、スタート／ストップ位相であり、図示のようにブロック行Ａ１の読み出しステップに対する演算から、ブロック行Ａ１およびＢ１に対する演算への遷移を表す。位相５１４を実行するために要する時間が待ち時間である。スタート／ストップ位相およびメイン位相は、このように、パリティ検査マクロ行列のブロック行のすべてが処理されてしまうまで続く。
【００６８】
図５ｂは、演算（１５）においてＬＡＪおよびＬＢｊの結果を組み合わせるためのメモリ演算および位相シーケンスを示す（すなわち、パリティ検査マクロ行列のブロック行のすべてが処理されたあとで）。図６は、コラム・サム・メモリ３１８の詳細図を示す。コラム・サム・メモリ３１８は、バッファ・メモリ６００、加算器ブロック６０４、マルチプレクサ６１０およびメモリ６１２を含む。図５ｂおよび図６を同時に参照すれば、処理すべき最後のブロック行ＢＬは、ブロック行Ｂのグルーピングに含まれる。図５ｂのＸおよびＹと記された演算は、（１５）の計算を２つの別々のステップで実行するために用いられる。Ｘステップは、
【数２９】
2008507240.tif 000028
を計算する。Ｙステップは、
【数３０】
2008507240.tif 000029
を計算する。詳細には、Ｘステップの間、メモリ６１２に書き込まれる代わりに、ＬＡｊ-  データは、バス６０２上の入力のデータ・フローから取り出されて、加算器ブロック６０４においてバス６１４を経てバッファ・メモリ６００から読み出された
【数３１】
2008507240.tif 000030
データと組み合わされて、一時的な値７｝を与え、それがＬＡ／データの代わりにバス６２０を介してメモリ６００に書き込まれる。Ｙステップの間、Ｌｓ／データは、メモリ６１２に書き込まれる代わりに、バス６０２上の入力のデータ・フローから取り出されて、バス６１４を経てバッファ・メモリ６００から読み出された一時的な値７｝と組み合わされて、値Ｌｙを与え、それがバス６２０を介してバッファ・メモリ６００に書き込まれる。この値Ｌｙは、上で述べたように、次にパリティ検査行列中の次のブロック行についての後続の反復で使用される。コラム・サム・メモリ３１８のデータ出力は、メモリ６１２出力からバス６１８を通して、バッファ・メモリ６００出力からバス６１４、６２６を通して、バッファ・メモリ６００への入力からバス６２４を通して転送される。
【００６９】
以上の議論は、本発明の原理および各種の実施の形態の実例を意味するものである。上の開示を完全に理解すれば、当業者には、数多くの変形および修正が明らかとなる。例えば、上で提示したアルゴリズム（単数又は複数）又はそれの変形を実施するためにメモリ、ハードウエア、サポート用の論理および演算シーケンスの数多くのその他の構成を用いることができる。任意の複数個のメモリを含む解決策を使用することができる。本発明は、そのような変形および修正のすべてを包含するものとして解釈すべきである。
【図面の簡単な説明】
【００７０】
【図１ａ】パリティ検査マクロ行列の図。
【図１ｂ】図１ａのパリティ検査マクロ行列のサブ行列の図。
【図１ｃ】本発明の実施の形態に従って再配置されたエントリを有する図１ａのパリティ検査マクロ行列のサブ行列の図。
【図２】本発明の実施の形態に従うフロー図。
【図３】本発明の実施の形態に従うＬＤＰＣデコーダ・アーキテクチャのブロック図。
【図４】コラム・サム・ブロックのブロック図。
【図５ａ】本発明の実施の形態に従うメモリ動作と位相シーケンスを示す図。
【図５ｂ】本発明の実施の形態に従うメモリ動作と位相シーケンスを示す図。
【図６】本発明の実施の形態に従うコラム・サム・ブロックのブロック図。
【図１ａ】
2008507240.tif 000031
【図１ｂ】
2008507240.tif 000032
【図１ｃ】
2008507240.tif 000033
【図２】
2008507240.tif 000034
【図３】
2008507240.tif 000035
【図４】
2008507240.tif 000036
【図５ａ】
2008507240.tif 000037
【図５ｂ】
2008507240.tif 000038
【図６】
2008507240.tif 000039
【手続補正書】
【提出日】平成19年1月30日(2007.1.30)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
通信システムにおいて受信されるデータを階層的に復号する方法であって、
複数の要素を含むコードワードを受信する工程であって、該コードワードは行および列を有するパリティ検査行列によって表される低密度パリティ検査符号に従って符号化されていて、前記複数の要素の各々が前記パリティ検査行列の１つの列に関連していて、パリティ検査行列の列が入力ノードに対応していて、またパリティ検査行列の行がパリティ検査サムに対応している、前記受信工程と、
前記パリティ検査行列の少なくとも１つの列の行をグループに分割する工程と、
次の工程を含む演算シーケンス、即ち：
グループの各行に対して、その行のパリティ検査サムに寄与する各入力ノードに関する確率値から前のチェック・ノード値を差し引く工程；
減算工程の結果を用いて、その行に関する新しいチェック・ノード値を生成する工程；
その行に関するパリティ検査サムに寄与する各入力ノードについて、前記新しいチェック・ノード値と減算工程の前記結果とを用いて確率値を更新する工程；
、を含む前記演算シーケンスを実行することによって前記グループの少なくともいくつかのうちの各々を別々に処理する工程と、
次に、前記別々に処理されたグループの各々からの少なくとも１つの列の更新された確率値を組み合わせる工程と、
を含む前記方法。
【請求項２】
請求項１記載の方法であって、前記組み合わせる工程が、前記少なくとも１つの列についてその他の処理が実質的に何も実行されていない時間内に実行される前記方法。
【請求項３】
請求項１記載の方法であって、前記パリティ検査行列の行をグループに分割する工程が、少なくとも１つのブロック行が次のブロック行と異なるグループに含まれるように前記少なくとも１つの列を分割する工程を含んでいる前記方法。
【請求項４】
行および列を有するパリティ検査行列によって表される低密度パリティ検査符号に従って符号化された受信信号ストリームを復号するためのシステムであって、複数の要素の各々が前記パリティ検査行列の１つの列に関連していて、前記パリティ検査行列の列が入力ノードに対応している前記システムが、
１つのメモリに接続された複数の並列計算ブロックと、
前記計算ブロックに接続され、前記パリティ検査行列の１つの行について、参加する入力ノードに対応する検査ノード値を更新するための複数のパリティ検査更新ブロック（ＰＣＵＢ）と、
前記ＰＣＵＢに接続され、各々が前記パリティ検査行列の複数の行の各々に関連する複数の入力ノードに対応する、更新された確率値を記憶するための１つのメモリを含んでいる複数のコラム・ストア・ブロック（ＣＳＢ）であって、コラム・ストア・ブロックの各々が、
行の第１のグループに関連する少なくとも１つの入力ノードに関する更新された確率値を記憶するための第１のメモリ部分と、
行の第２のグループに関連する少なくとも１つの入力ノードに関する更新された確率値を記憶するための第２のメモリ部分と、
少なくとも１つの入力ノードに関する前記第１および第２のメモリ部分からの更新された確率値を組み合わせるための回路と、
を含んでいる前記複数のコラム・ストア・ブロック（ＣＳＢ）と、
を含む前記システム。
【請求項５】
請求項４記載のシステムであって、前記組み合わせるための回路が、少なくとも１つの入力ノードに関する確率値の少なくともいくつかを組み合わせる演算を、前記複数のパリティ検査更新ブロックおよびコラム・ストア・ブロックがその少なくとも１つの入力ノードに関連する情報に対して何も演算を実行していない時間に実行するように動作できる前記システム。
【請求項６】
請求項１記載の方法であって、前記パリティ検査行列の行がサブセットにグループに分割され、該サブセット中において、各列が最大列重み１を有する前記方法。
【請求項７】
請求項１記載の方法であって、前記パリティ検査行列は、ブロック行およびブロック列の形に構成されたゼロ値および非ゼロ値のエントリを有するマクロ行列によって表され、各々のゼロ値エントリは、ｐｘｐのゼロ値行列に対応し、各々の非ゼロ値エントリは、パリティ検査行列を定義するように、各行および各列にせいぜい唯１つの「１」エントリを有し、それ以外には、「０」エントリを有するｐｘｐの順列行列に対応している前記方法。
【国際調査報告】
2008507240.tif 000040