(57)【要約】      （修正有）【課題】ＬＤＰＣ復号化器及びデータ検出器を有するデータ処理システムにおいて、ＬＤＰＣ復号化器及びデータ検出器における処理時間のバランスをより良好にとるための装置および方法を提供する。【解決手段】データセットにおけるデータ値を検出するように動作可能なデータ検出器と、前記データセットに対して複数の復号化反復を反復的に実行するように動作可能な低密度パリティチェック復号化器であって、前記複数の復号化反復は、復号化器処理時間と検出器処理時間とのバランスをとるための完全な復号化反復及び部分復号化反復の選択を含む、低密度パリティチェック復号化器と、を備える。【選択図】図２
2014064269.tif 000002
【特許請求の範囲】
【請求項１】
データを処理するための装置であって、
データセットにおけるデータ値を検出するように動作可能なデータ検出器と、
前記データセットに対して複数の復号化反復を反復的に実行するように動作可能な低密度パリティチェック復号化器であって、前記複数の復号化反復は、復号化器処理時間と検出器処理時間とのバランスをとるための完全な復号化反復及び部分復号化反復の選択を含む、低密度パリティチェック復号化器と、
を備える、データを処理するための装置。
【請求項２】
前記低密度パリティチェック復号化器は、前記復号化器処理時間が前記検出器処理時間を超えることなく、前記完全な復号化反復及び部分復号化反復の選択に含めることができる前記完全な復号化反復の数及び前記部分復号化反復の数を求めるように動作可能である、請求項１に記載の装置。
【請求項３】
前記低密度パリティチェック復号化器は、前記復号化器処理時間が前記検出器処理時間を超えることなく、前記完全な復号化反復及び部分復号化反復の選択に、可能な限り多くの前記完全な復号化反復及び部分復号化反復を含めるように動作可能である、請求項２に記載の装置。
【請求項４】
前記検出器処理時間を前記データ検出器から前記低密度パリティチェック復号化器に通信するように動作可能な部分反復コントローラーを更に備える、請求項１に記載の装置。
【請求項５】
前記データ検出器は、軟出力ビタビアルゴリズム検出器を備える、請求項１に記載の装置。
【請求項６】
前記復号化器処理時間及び前記検出器処理時間は同じデータセットについてバランスがとられている、請求項１に記載の装置。
【請求項７】
前記復号化器処理時間及び前記検出器処理時間は、前記データ検出器及び前記低密度パリティチェック復号化器において同時に処理される異なるデータセットについてバランスがとられている、請求項１に記載の装置。
【請求項８】
前記低密度パリティチェック復号器は非層復号化器を含み、前記部分復号化反復は、前記非層復号化器のためのＨ行列における複数の列のサブセットが処理されるローカル復号化反復を含む、請求項１に記載の装置。
【請求項９】
前記低密度パリティチェック復号化器は層復号化器を含み、前記部分復号化反復は、前記層復号化器のためのＨ行列における複数の層のサブセットが処理されるローカル復号化反復を含む、請求項１に記載の装置。
【請求項１０】
前記低密度パリティチェック復号化器は、前記部分復号化反復のうちの１つにおいて生成された新たなデータと、前記完全な復号化反復のうちの１つにおいて生成された古いデータと、の結合に基づいて、前記部分復号化反復のうちの前記１つにおいてチェックノードから変数ノードへのメッセージを生成するように動作可能である、請求項１に記載の装置。
【請求項１１】
前記装置は集積回路として実装される、請求項１に記載の装置。
【請求項１２】
前記装置は記憶デバイス内に組み込まれる、請求項１に記載の装置。
【請求項１３】
前記記憶デバイスは独立ディスクの冗長アレイを含む、請求項１２に記載の装置。
【請求項１４】
前記装置は送信システム内に組み込まれる、請求項１に記載の装置。
【請求項１５】
データを処理するための方法であって、
データ検出器においてデータセットのデータ値を検出することと、
前記データ検出器において、前記データセットのための検出器処理時間を求めることと、
低密度パリティチェック復号化器において前記データセットに対し複数のローカル復号化反復を実行することであって、該複数のローカル復号化反復は、復号化器処理時間と前記検出器処理時間とのバランスをとるための完全な復号化反復及び部分復号化反復の選択を含む、実行することと、
を含む、データを処理するための方法。
【請求項１６】
請求項１５に記載の方法であって、
前記復号化器処理時間が前記検出器処理時間を超えることなく、前記複数のローカル復号化反復に可能な限り多くの前記完全な復号化反復及び前記部分復号化反復を含めることを更に含む、方法。
【請求項１７】
前記低密度パリティチェック復号化器は非層復号化器を含み、前記部分復号化反復のうちの１つを実行することは、前記ローカル復号化反復中に前記非層復号化器のためのＨ行列における複数の列のサブセットを処理することを含む、請求項１５に記載の方法。
【請求項１８】
前記低密度パリティチェック復号化器は層復号化器を含み、前記部分復号化反復のうちの１つを実行することは、前記ローカル復号化反復中に前記層復号化器のためのＨ行列における複数の層のサブセットを処理することを含む、請求項１５に記載の方法。
【請求項１９】
前記部分復号化反復のうちの１つを実行することは、前記部分復号化反復のうちの１つにおいて生成された新たなデータと、前記完全な復号化反復のうちの１つにおいて生成された古いデータと、の結合に基づいて、前記復号化反復のうちの前記１つにおいてチェックノードから変数ノードへのメッセージを生成することを含む、請求項１５に記載の方法。
【請求項２０】
記憶システムであって、
データセットを維持する記憶媒体と、
前記記憶媒体上の前記データセットを感知するように動作可能な読取り／書込みヘッドアセンブリと、
前記データセットを処理するための装置であって、
前記データセットにおけるデータ値を検出するように動作可能なデータ検出器と、
前記データセットに対して複数の復号化反復を反復的に実行するように動作可能な低密度パリティチェック復号化器であって、前記複数の復号化反復は、復号化器処理時間と検出器処理時間とのバランスをとるための完全な復号化反復及び部分復号化反復の選択を含む、低密度パリティチェック復号化器と、
を備える、装置と、
を備える、記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本願は、部分ローカル反復を用いたＬＤＰＣ復号化器に関する。
【背景技術】
【０００２】
記憶システム、携帯電話システム、及び無線送信システムを含む、様々なデータ処理システムが開発されている。それらのシステムでは、データが何らかの媒体を介して送信機から受信機に転送される。例えば、記憶システムにおいて、データは、送信機（すなわち書込み機能）から、記憶媒体を介して受信機（すなわち読取り機能）に送信される。情報はデジタルデータの形態で記憶及び送信されるので、誤りが生じ、この誤りは、訂正されない場合、データを破損し情報を使用不可能にする可能性がある。任意の転送の有効性は、様々な要因によって生じる、データ内の任意の損失によって影響される。デジタルデータ内の誤りを検出し訂正するために、多くのタイプの誤り検査システムが開発されている。例えば、おそらく最も単純なシステムでは、パリティビットをデータビット群に付加し、データビット群（パリティビットを含む）が偶数個又は奇数個の１を有することを確実にすることができる。奇数パリティを用いるとき、記憶又は送信のためにデータが準備されると、群内の１にセットされたデータビット数がカウントされ、群内に偶数個の１が存在する場合、群が奇数個の１を有することを確実にするためにパリティビットは１にセットされる。群内に奇数個の１が存在する場合、群が奇数個の１を有することを確実にするためにパリティビットは０に設定される。記憶装置からデータが取り出されるか又は送信により受信された後、パリティを再びチェックすることができ、群が偶数のパリティを有する場合、少なくとも１つの誤りがデータ内に生じている。この単純なレベルでは、幾つかの誤りを検出することができるが、訂正することはできない。
【０００３】
パリティビットは、低密度パリティチェック（ＬＤＰＣ）復号化器を含む誤り訂正システムにおいて用いることもできる。図１に示すように、ＬＤＰＣ符号は、タナーグラフ１００において視覚的に表現することができるパリティベースの符号である。ＬＤＰＣ復号化器では、複数のチェックノード１０２、１０４、１０６、及び１０８において、変数ノード１１０、１１２、１１４、１１６、１１８、１２０、１２２、及び１２４の群に対し複数のパリティチェックが行われる。ＬＤＰＣ符号が設計されるときに変数ノード１１０〜１２４とチェックノード１０２〜１０８との間の接続（すなわちエッジ）が選択され、データが取得されるときにＬＤＰＣ符号を実行するのに必要とされる復号化器の複雑度に対する符号の強度のバランスがとられる。ＬＤＰＣ符号が設計されるときに群内のパリティビットの数及び配置が選択される。接続された変数ノード１１０〜１２４とチェックノード１０２〜１０８との間で反復プロセスにおいてメッセージが渡される。このメッセージは、変数ノード１１０〜１２４において現れるはずの値に関する確信度を接続されたチェックノード１０２〜１０８に渡す。チェックノード１０２〜１０８において、メッセージに基づいてパリティチェックが実行され、接続された変数ノード１１０〜１１４に結果が返され、必要な場合に確信度が更新される。ＬＤＰＣ復号化器は、バイナリ形式で実装することもできるし、非バイナリ形式で実装することもできる。バイナリＬＤＰＣ復号化器において、変数ノード１１０〜１２４は、記憶デバイスから取り出されるか、送信システムによって受信されるか、又は何らかの他の形で得られたデータ及びパリティビットの群に基づくスカラー値を含む。バイナリＬＤＰＣ復号化器におけるメッセージは、送信側の変数ノードが特定の値を含む確率を表す単純尤度確率値又は対数尤度比（ＬＬＲ）値として送信されるスカラー値である。非バイナリＬＤＰＣ復号化器では、変数ノード１１０〜１２４はガロア体からのシンボルを含む。ガロア体はすなわち、サイズｐｋによって特徴付けられる有限数の要素を含む有限体ＧＦ（ｐｋ）であり、ここでｐは素数でありｋは正の整数である。非バイナリＬＤＰＣ復号化器におけるメッセージは多次元ベクトルであり、通常、単純尤度確率ベクトル又はＬＬＲベクトルのいずれかである。
【０００４】
変数ノード１１０〜１２４とチェックノード１０２〜１０８との間の接続は、以下のように行列形式で示すことができる。ここで、列は変数ノードを表し、行はチェックノードを表し、変数ノード列とチェックノード行との交点におけるガロア体からのランダム非ゼロ要素ａ（ｉ，ｊ）は、変数ノードとチェックノードとの間の接続を示し、変数ノードとチェックノードとの間のメッセージの置換を提供する。
【数１】
2014064269.tif 000003
【０００５】
変数ノード１１０〜１２４の群に複数のチェックノード１０２〜１０８を提供することによって、誤り検査における冗長性がもたらされ、誤りが検出されるだけでなく訂正されることが可能になる。各チェックノード１０２〜１０８は、その近傍の（すなわち接続された）変数ノードからメッセージとして渡されたビット又はシンボルに対しパリティチェックを実行する。図１のタナーグラフ１００に対応する例示的なＬＤＰＣ符号では、チェックノード１０２は変数ノード１１０、１１６、１２０、及び１２２のパリティを検査する。ＬＤＰＣ符号が変数ノード１１０〜１２４におけるデータ及びパリティビットの群のための値に収束するまで、反復プロセスにおいて、接続された変数ノード１１０〜１２４とチェックノード１０２〜１０８との間で値が行き来する。例えば、変数ノード１１０はチェックノード１０２及び１０６にメッセージを渡す。チェックノード１０２は変数ノード１１０、１１６、１２０、及び１２２にメッセージを返す。変数ノード１１０〜１２４とチェックノード１０２〜１０８との間のメッセージは確率又は確信度であり、このためＬＤＰＣ復号化アルゴリズムは確率伝搬アルゴリズムとも呼ばれる。ノードからの各メッセージは、ノードの現在の値及びノードへの以前のメッセージに基づいて、ビット又はシンボルが或る特定の値を有する確率を表す。
【０００６】
変数ノードから任意の特定の近傍チェックノードへのメッセージが、変数ノードの現在の値と近傍チェックノードから変数ノードへの最新のメッセージとに基づいて、複数のアルゴリズムのうちの任意のものを用いて計算される。ただし、その特定のチェックノードからの最新のメッセージは、正のフィードバックを防ぐために計算から除外される。同様に、チェックノードから任意の特定の近傍変数ノードへのメッセージが、チェックノードの現在の値と近傍変数ノードからチェックノードへの最新のメッセージとに基づいて計算される。ただし、その特定の変数ノードからの最新のメッセージは、正のフィードバックを防ぐために計算から除外される。システムにおいてローカル復号化反復が実行されると、ノード１０２〜１２４における値が収束し変化を止めるまで、又は処理が停止するまで、変数ノード１１０〜１２４とチェックノード１０２〜１０８との間でメッセージが行き来し、渡されたメッセージに基づいてノード１０２〜１２４における値が調整される。
【０００７】
ビタビ検出器及びＬＤＰＣ復号化器等のデータ検出器を有するデータ処理システムでは、検出器又は復号化器のいずれかがデータブロックを処理するのにより時間がかかる場合があり、これにより、それらのうちの一方において、他方が処理を完了するのを待つ間の遅延が生じる。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
【課題を解決するための手段】
【０００９】
本発明は、例えばＬＤＰＣ復号化器及びデータ検出器を有するデータ処理システムにおいて、ＬＤＰＣ復号化器及びデータ検出器における処理時間のバランスをより良好にとるのに用いることができる、部分ローカル反復を用いたＬＤＰＣ復号化器のためのシステム及び方法に関する。ローカル復号化反復を２つ以上のセグメントに分割することによって、グローバル反復中に一部の復号化反復すなわち部分復号化反復を実行して、ＬＤＰ復号化器及びデータ検出器における処理時間のバランスをより密接にとることができる。幾つかの実施形態では、データ検出器におけるデータセクターのための処理時間が求められ、ＬＤＰＣ復号化器は、データ検出器処理時間に基づいて、実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数を求める。幾つかの実施形態では、ＬＤＰＣ復号化器は、データセクターのために利用可能な処理時間を可能な限り完全に埋め、同じデータセクターについてデータ検出器における処理時間を超えることなく、可能な限り長く完全なローカル復号化反復及び部分ローカル復号化反復を実行する。ローカル復号化反復は、符号語のためのＨ行列を２つ以上のセグメントに分割することによって分割することができる。Ｈ行列は、ＬＤＰＣ復号化器における処理時間に対しより精密な制御を提供するように、等しいサイズ又は異なるサイズの複数のセグメントに分割することができる。ＬＤＰＣ復号化器は階層的復号化器又は非階層的復号化器とすることができる。幾つかの階層的復号化器の実施形態では、Ｈ行列は行によって分割することができ、部分反復によって層内の行のサブセットを処理する。幾つかの非階層的復号化器の実施形態では、Ｈ行列は列によって分割することができ、部分反復によってＨ行列内の列のサブセットを処理する。
【００１０】
この概要は、本発明による幾つかの実施の形態の概略のみを提供するものである。本発明の多くの他の目的、特徴、利点、及び他の実施の形態は、以下の詳細な説明、添付の特許請求の範囲、及び添付の図面からより完全に明らかとなるであろう。
【００１１】
図面を参照することにより、本発明の様々な実施形態の更なる理解を実現することができ、これらの実施形態については本明細書の残りの部分で説明する。図面において、同様の参照符号が幾つかの図面の全てにわたって類似の構成要素を指すのに用いられている。幾つかの場合には、小文字からなるサブラベルが、複数の類似の構成要素のうちの１つを表すように参照符号に関連付けられている。存在するサブラベルを指定することなく参照符号が参照されるとき、そのような複数の類似の構成要素全てを指すことが意図される。
【図面の簡単な説明】
【００１２】
【図１】例示的な従来技術によるＬＤＰＣ符号のタナーグラフを示す図である。
【図２】本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を有するデータ検出及び復号化回路を示す図である。
【図３】Ａは、本発明の幾つかの実施形態による、２つのデータセクターのインターリーブされた検出及び復号化を示す図であり、検出器が処理を完了するのを待つ間、ＬＤＰＣ復号化器において処理時間が浪費される。Ｂは、本発明の幾つかの実施形態による、２つのデータセクターのインターリーブされた検出及び復号化を示す図であり、検出器及びＬＤＰＣ復号化器における処理時間のバランスを取るために、ＬＤＰＣ復号化器において部分ローカル反復が行われる。
【図４】本発明の幾つかの実施形態による、非層ＬＤＰＣ復号化器（non-layer LDPC decoder）における部分ローカル反復を可能にするＨ行列の分割を示す図である。
【図５】本発明の幾つかの実施形態による、部分ローカル反復を用いた非層ＬＤＰＣ復号化器のブロック図である。
【図６】Ａは、本発明の幾つかの実施形態による、部分ローカル反復が無効にされたＬＤＰＣ層復号化器（LDPC layer decoder）における３層Ｈ行列を用いた階層的復号化を示す図である。Ｂは、本発明の幾つかの実施形態による、第１のローカル反復における最初の２つの層をスキップするように部分ローカル反復が有効にされたＬＤＰＣ層復号化器における３層Ｈ行列を用いた階層的復号化を示す図である。
【図７】本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ層復号化器のブロック図である。
【図８】本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器によるデータ検出及び復号化動作の流れ図である。
【図９】本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を有するデータ処理回路を備える記憶システムを示す図である。
【図１０】本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を有するデータ処理回路を備える無線通信システムを示す図である。
【発明を実施するための形態】
【００１３】
本発明は、例えばＬＤＰＣ復号化器及びデータ検出器を有するデータ処理システムにおいて、ＬＤＰＣ復号化器及びデータ検出器における処理時間のバランスをより良好にとるのに用いることができる、部分ローカル反復を用いたＬＤＰＣ復号化器のためのシステム及び方法に関する。様々な実施形態において用いられるＬＤＰＣ復号化器は、バイナリ復号化器、非バイナリ復号化器、階層的復号化器、及び非階層的復号化器を含み、かつ任意の適切な復号化アルゴリズムを用いる、任意のタイプのＬＤＰＣ復号化器とすることができる。ＬＤＰＣ技術は、実質的に任意のチャネルによる情報の送信又は実質的に任意の媒体への情報の記憶に適用可能である。送信に適用されるものには、光ファイバー、無線周波数チャネル、有線又は無線のローカルエリアネットワーク、デジタル加入者線技術、無線セルラー、銅ファイバー又は光ファイバー等の任意の媒体によるイーサネット登録商標、ケーブルテレビ等のケーブルチャネル、及び地球衛星通信が含まれるが、これらに限定されるものではない。記憶に適用されるものには、ハードディスクドライブ、コンパクトディスク、デジタルビデオディスク、磁気テープ、並びにＤＲＡＭ、ＮＡＮＤフラッシュ、ＮＯＲフラッシュ、他の不揮発性メモリ及びソリッドステートドライブ等のメモリデバイスが含まれるが、これらに限定されるものではない。
【００１４】
ローカル復号化反復を２つ以上のセグメントに分割することによって、グローバル反復中に一部の復号化反復すなわち部分復号化反復を実行し、ＬＤＰＣ復号化器及びデータ検出器の処理時間のバランスをより密にとることができる。幾つかの実施形態では、データ検出器におけるデータセクターの処理時間が求められ、ＬＤＰＣ復号化器は、このデータ検出器処理時間に基づいて、実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数を求める。幾つかの実施形態では、ＬＤＰＣ復号化器は、同じデータセクターについてのデータ検出器における処理時間を超えることなく、可能な限り完全にデータセクターに利用可能な処理時間を埋めて、完全なローカル復号化反復及び部分ローカル復号化反復を可能な限り長く実行する。ローカル復号化反復は、符号語のためのＨ行列を２つ以上のセグメントに分割することによって分割することができる。Ｈ行列は等しいサイズの、又はＬＤＰＣ復号化器の処理時間に対しより精密な制御を与えるように異なるサイズの複数のセグメントに分割することができる。ＬＤＰＣ復号化器は階層的復号化器又は非階層的復号化器とすることができる。幾つかの階層的復号化器の実施形態では、Ｈ行列は行によって分割することができ、部分反復によって層内の行のサブセットが処理される。幾つかの非階層的復号化器の実施形態では、Ｈ行列は列によって分割することができ、部分反復によってＨ行列内の列のサブセットが処理される。
【００１５】
図２を参照すると、本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器２２２を備えることができるデータ復号化器回路２００の１つの実施態様が開示されている。データ復号化回路２００はデータ入力２０２を含み、データ入力２０２はチャネル検出器２０４に供給される。幾つかの実施形態では、データ入力２０２はデジタルデータストリームであり、例えば磁気記憶デバイスから読み取られたデジタル化され等化されたデータを含む。チャネル検出器２０４は、限定ではないが、軟出力ビタビアルゴリズム検出器（ＳＯＶＡ）又は最大事後（ＭＡＰ）検出器を含む当該技術分野において既知の任意のタイプのチャネル検出器とすることができる。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に従って用いることができる様々なチャネル検出器を認識するであろう。さらに、データ入力２０２が入力データバッファー２０６に提供され、入力データバッファー２０６はデータ入力２０２から受信した複数のデータセットを保持するように設計される。入力データバッファー２０６のサイズは、データ入力２０２を介したデータセット入力が、以下でより完全に説明するように、少なくとも、同じデータセットの第１の反復処理が完了し、かつ処理されたデータがピンポンバッファー２３０（すなわちキューイングバッファー）において利用可能になるまで利用可能なままであるように、十分なバッファリングを提供するように選択することができる。入力データバッファー２０６はチャネル検出器２１０にデータセットを提供する。チャネル検出器２０４と同様に、チャネル検出器２１０は、限定ではないが、ＳＯＶＡ検出器又はＭＡＰ検出器を含む当該技術分野において既知の任意のタイプのチャネル検出器とすることができる。ここでもまた、本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に従って用いることができる様々なチャネル検出器を認識するであろう。
【００１６】
チャネル検出器２０４及びチャネル検出器２１０の双方の出力がマルチプレクサー２１２を介してインターリーバー回路２１６に提供される。そのような出力は、例えば、対数尤度比（ＬＬＲ）値とすることができる。インターリーバー回路２１６は２つのピンポンバッファー２１４、２２０を用いて、チャネル検出器２０４の出力をインターリーブし、それとは別個にチャネル検出器２１０の出力をインターリーブする。ピンポンバッファー２１４におけるバッファーのうちの一方は、チャネル検出器２０４からの出力の以前のインターリーブプロセスの結果を保持し、部分ローカル反復を用いたＬＤＰＣ復号化器２２２にアンロードされる一方、ピンポンバッファー２１４の他方のバッファーは、現在インターリーブされているチャネル検出器２０４からのデータセットを保持する。同様に、ピンポンバッファー２２０におけるバッファーのうちの一方は、チャネル検出器２１０からの出力の以前のインターリーブプロセスの結果を保持し、ＬＤＰＣ復号化器２２２にアンロードされる一方、ピンポンバッファー２２０の他方のバッファーは、現在インターリーブされているチャネル検出器２１０からのデータセットを保持する。
【００１７】
通常動作において、第１のデータセットがデータ入力２０２を介してチャネル検出器２０４にもたらされる。チャネル検出器２０４はそのチャネル検出アルゴリズムを実行し、硬出力及び軟出力の双方をマルチプレクサー２１２に提供する。硬判定データ及び軟判定データがピンポンバッファー２１４のうちの一方のバッファーに書き込まれる。チャネル検出器２０４におけるデータセットのための処理時間が求められ、ＬＤＰＣ復号化器２２２に提供される。検出器処理時間は、データセットのための処理の持続時間の表示を提供し、この検出器処理時間は、クロックサイクル単位又は他の測定単位で測定することもできるし、標準データセットのための処理時間に基づく相対的な測定値とすることもできる。同時に、検出器出力がバッファーに書き込まれ、インターリーバー２１６は、インターリーバーアルゴリズム／マッピングに基づいて、連続していないメモリ／バッファーアドレスに連続データを書き込むことによってデータセットをインターリーブする。インターリーバー２１６がインターリーブプロセスを完了すると、インターリーブされたデータがＬＤＰＣ復号化器２２２によって復号化される。
【００１８】
ＬＤＰＣ復号化器２２２は、利用可能な処理時間を満たすために、適宜、完全な復号化反復と一部の復号化反復すなわち部分復号化反復とを混合したものを実行し、ＬＤＰＣ復号化器２２２が、チャネル検出器２０４が処理を完了するのをアイドル状態で待つことがないようにするが、検出器処理時間を超えて、チャネル検出器２０４が、ＬＤＰＣ復号化器２２２が処理を完了するのを待つようになることはない。復号化時間は、同じデータセットについて、それがチャネル検出器２０４において処理されるときの処理時間に基づいてＬＤＰＣ復号化器２２２において調整することもできるし、例えば２つの検出器２０４及び２１０の長い方の処理時間に合わせることを試みて、チャネル検出器２０４若しくはチャネル検出器２１０又はそれらの両方において現在処理されているデータセットのための処理時間に基づくこともできる。幾つかの実施形態では、チャネル検出器２０４及び／又はチャネル検出器２１０における処理時間に関する情報をＬＤＰＣ復号化器２２２に渡すために、及び幾つかの実施形態では処理時間を求めるのを支援するために、部分反復コントローラー２５０を設けることができる。幾つかの実施形態では、部分反復コントローラー２５０は、チャネル検出器２０４における処理時間に基づいて、実行すべき完全な反復及び部分反復の数等の復号化リソースをＬＤＰＣ復号化器２２２に割り当てるのも支援する。
【００１９】
データが収束した場合、ＬＤＰＣ復号化器２２２はその出力を硬判定出力２２４として出力データバッファー２３４に出力し、その特定のデータセットについて処理が完了する。代替的に、データが収束しない場合、ＬＤＰＣ復号化器２２２は、その出力（軟出力及び硬出力の双方）をピンポンバッファー２３０に書き込む。
【００２０】
ピンポンバッファー２３０に書き込まれたデータはチャネル検出器２１０にフィードバックされる。チャネル検出器２１０は、入力データバッファー２０６からピンポンバッファー２３０における出力に対応するデータセットを選択し、ピンポンバッファー２３０からフィードバックされた、ＬＤＰＣ復号化器２２２によって生成された軟出力データによって支援される後続のデータ検出を実行する。入力データバッファー２０６において維持されているデータのために以前に生成された軟データを用いることによって、チャネル検出器２１０は通常、強化された精度で後続のチャネル検出を実行する。この後続のチャネル検出の出力はマルチプレクサー２１２を介してインターリーバー２１６に渡される。このデータはピンポンバッファー２２０の一方のバッファーに書き込まれ、インターリーバー２１６はデータをインターリーブする。次に、インターリーブされたデータはＬＤＰＣ復号化器２２２に渡され、ＬＤＰＣ復号化器２２２において２回目に復号化される。第１の反復と同様に、データが収束したか否か、又はピンポンバッファー２３０内にデータを処理するのに不十分な空間が存在するか否かに関して判断が行われる。データが収束したか、又はピンポンバッファー２３０内にデータを処理するのに不十分な空間が存在する場合、ＬＤＰＣ復号化器２２２はその出力を硬判定出力２２４として出力データバッファー２３４に書き込み、その特定のデータセットに付いて処理が完了する。代替的に、データが収束せず、かつピンポンバッファー２３０内に追加のデータセットを受信するのに十分なバッファー空間が存在する場合、ＬＤＰＣ復号化器２２２は、その出力（軟出力及び硬出力の双方）をピンポンバッファー２３０に書き込み、ピンポンバッファー２３０においてその出力は、第３の通過のためにチャネル検出器２１０に戻される。第２の検出器及び復号化器反復からのデータセットがピンポンバッファー２３０に書き込まれた後に、少なくとも、第１の検出器及び復号化器反復からのデータセットのための予約済みの空間を有することによって、ピンポンバッファー２３０において十分な空間が定義される。特に、幾つかの実施形態では、ピンポンバッファー２１４、２２０、２３０のうちの１つ又は複数を省くことができ、処理時間の適合が改善したことにより、構成要素間でデータセットが直接渡される。
【００２１】
例として、第１のデータセットをデータ入力２０２において適用することができ、このデータセットは収束するのに複数の反復を要する一方、データ入力２０２において適用される全ての後続のデータセットが最初の通過において（すなわち単一の反復において）収束することに留意されたい。そのような場合、第１のデータセットは、出力データバッファー２３４において利用可能なメモリの量によって制限される複数回（すなわち複数のグローバル反復）処理することができる。出力データバッファー２３４がフルになるか、又は順序付けされた一組の出力が利用可能になると、第１のデータセットに対応する最も近時の硬判定出力が硬判定出力として提供され、デインターリーバー２３４は出力を再順序付けし、第１の出力を第１の位置に置く。これが行われると、出力データバッファー２３４が出力２３６として一掃される。
【００２２】
２つのデータセットの交互の検出及び復号化が部分ローカル反復なしでデータ復号化回路２００において進行する場合があるときの当該交互の検出及び復号化が図３Ａの図３００に示されている。図３００において、２つのデータセットが異なるクロスハッチの向きによって区別されている。図３００内の各ブロックは、データセットを処理するためのタイムスロットを表す。図３００は、処理のピンポン特性を図式的に示すことを意図したものであり、チャネル検出器２０４及びＬＤＰＣ復号化器２２２における処理タイムスロット間、又はチャネル検出器２０４若しくはＬＤＰＣ復号化器２２２のいずれかにおける連続処理タイムスロット間のタイミング関係を正確に示すことを意図したものではない。検出器処理時間粒度はデータセット又はセクターに基づく。換言すれば、チャネル検出器２０４は各タイムスロットにつき１つの全体データセットを処理する。復号化器処理時間はローカル復号化反復に基づき、例示的なＬＤＰＣ復号化器２２２が処理タイムスロットあたり複数のローカル復号化反復を実行する。幾つかの実施形態では、データ復号化回路２００はクライアント−サーバーコーデックシステムであり、ここでチャネル検出器２０４及びＬＤＰＣ復号化器２２２は、ピンポン形式でデータセットを連続して処理する。チャネル検出器２０４及びＬＤＰＣ復号化器２２２は様々なコードレートオプション、復号化器スケジューリング、データセクター内のユーザデータ長等に起因して様々な処理時間を有することができる。ＬＤＰＣ復号化器２２２における処理時間がチャネル検出器２０４よりも短い場合、ＬＤＰＣ復号化器２２２はチャネル検出器２０４からの出力を待つ。
【００２３】
第１のデータセットはチャネル検出器２０４においてタイムスロット３０２で処理され、次にＬＤＰＣ復号化器２２２においてタイムスロット３１４で復号化される。チャネル検出器２０４及び次にＬＤＰＣ復号化器２２２におけるデータセットの処理は単一のグローバル反復を表す。ＬＤＰＣ復号化器２２２において内部的に繰り返されるデータセットの処理はローカル反復又はローカル復号化反復である。ＬＤＰＣ復号化器２２２が完全なローカル復号化反復のみを実行する場合、最新の完全なローカル復号化反復の完了後まで待ち時間３１６を有する場合があり、その後にチャネル検出器２０４からの次のデータセットの処理を開始することができる。タイムスロット３０２中にチャネル検出器２０４において第１のデータセットが完了すると、チャネル検出器２０４においてタイムスロット３０４で第２のデータセットが処理され、次にＬＤＰＣ復号化器２２２においてタイムスロット３２０で復号化される。データセットの交互の処理すなわちピンポン処理は、データがデータセットについて収束するか、又はデータセットについて最大許容可能グローバル反復数が完了するまで継続し、その後、そのデータセットは新たなデータセットを通すためにデータ復号化回路２００から追い出される。このため、第１のデータセットは、チャネル検出器２０４及びＬＤＰＣ復号化器２２２において、タイムスロット３０２、３１４、３０６、３２４、及び３１２で処理することができる。第２のデータセットはチャネル検出器２０４及びＬＤＰＣ復号化器２２２においてタイムスロット３０４、３２０、３１０、及び３３０で処理することができる。ＬＤＰＣ復号化器２２２において各タイムスロット３１４、３２０、３２４、３３０で、ＬＤＰＣ復号化器２２２は、可能な最新の完全な復号化反復を完了した後、データがチャネル検出器２０４から利用可能になってＬＤＰＣ復号化器２２２において新たなグローバル反復を開始するまで、非アクティブな待ち期間３１６、３２２、３２６、３３２を有する場合がある。
【００２４】
待機期間３１６、３２２、３２６、３３２を埋めることを試みてＬＤＰＣ復号化器２２２において追加の完全なローカル復号化反復を加えることによって、ＬＤＰＣ復号化器２２２における処理時間、すなわちタイムスロットの持続時間が、チャネル検出器２０４の処理時間、すなわちタイムスロットの持続時間を超えることになる。ＬＤＰＣ復号化器２２２における処理時間がチャネル検出器２０４における処理時間を超えた場合、システムにおけるレイテンシ全体が増大する。ＬＤＰＣ復号化器２２２において部分ローカル反復を実行することによって、待ち期間３１６、３２２、３２６、３３２は、チャネル検出器２０４における処理時間を超えることなく更なる復号化が占めることができる。部分ローカル復号化反復は完全なローカル復号化反復よりも要する時間が短く、このため待ち期間３１６、３２２、３２６、３３２内に収まることができる。これらの追加のローカル復号化反復によって復号化性能が改善し、このためデータ復号化回路２００の性能全体が改善する。
【００２５】
図３Ｂの図３５０に示すように、ＬＤＰＣ復号化器２２２における待ち期間は、部分ローカル復号化反復を加えることによって実質的に除去することができる。第１のデータセットはチャネル検出器２０４及びＬＤＰＣ復号化器２２２においてタイムスロット３５２、３６４、３５６、３７４、及び３６２で処理することができる。第２のデータセットはチャネル検出器２０４及びＬＤＰＣ復号化器２２２においてタイムスロット３５４、３７０、３６０、及び３８０で処理することができる。チャネル検出器２０４及びＬＤＰＣ復号化器２２２における実際の処理時間は、部分ローカル復号化反復を用いて、ＬＤＰＣ復号化器２２２における待ち時間を低減又は除去するように実質的に適合される。
【００２６】
図４を参照すると、本発明の幾つかの実施形態による、Ｈ行列４００をセグメントに分割して非層ＬＤＰＣ復号化器における部分ローカル反復を可能にすることが示されている。この例では、Ｈ行列４００は大きさの等しい２つのセグメント、すなわち左側４０２及び右側４０４に分割される。他の実施形態では、Ｈ行列４００は列によって３つ以上のセグメント又は大きさの等しくないセグメントに分割することができる。非層ＬＤＰＣ復号化器では、Ｈ行列４００は行ごと、列ごとに処理される。完全なローカル復号化反復は、両側４０２及び４０４を処理し、単一の行又は語から例えば行４０６の全ての列を処理するか、又は２つの行にわたって、例えば１つの反復中に行４１０の右側４０４及び行４１２の左側４０２を処理する。非層ＬＤＰＣ復号化器におけるグローバル復号化反復は第１の行４０６の左側４０２における、Ｈ行列４００の左上の巡回行列で開始することもできるし、任意の他の行で、左側４０２の代わりに右側４０４で開始することもできる。このように、非層ＬＤＰＣ復号化器において、部分反復はグローバル復号化反復の開始時、反復中、又は終了時に実行することができる。このように、部分反復は、左側４０２又は右側４０４のいずれかにおいて開始する、Ｈ行列４００の片側４０２又は４０４のみの処理の後に復号化を終了することによって達成することができる。
【００２７】
単一の行（例えば４０６）から、又は２つの行（例えば４１０及び４１２）にわたって２つの半分のセクションを処理した後、それらの２つの半分のセクションのためのＶ２Ｃメッセージコンテンツに基づいて、ローカル反復を完了する、行のためのＣ２Ｖメッセージを生成することができる。幾つかの実施形態では、Ｈ行列４００全体が処理された第１のローカル反復の後、最も近時の処理済みの半分の行からの現在のデータを、最も近時のものの前の処理済みの半分の行からの古いデータと結合することによって、Ｃ２Ｖメッセージを各半分の行の後に更新することができる。このため、Ｃ２Ｖメッセージを更新するのに用いられる左側４０２及び右側４０４のためのデータは現在のデータ及び古いデータの双方を含むことができる。
【００２８】
図５を参照すると、本発明の様々な実施形態による、単純化された最小和（min-sum）に基づく復号化アルゴリズムを適用する例示的な非層ＬＤＰＣ復号化器５００、この例では非バイナリ復号化器が示されている。ここでもまた、部分ローカル反復を用いたＬＤＰＣ復号化器は、最小和に基づく復号化とともに用いることにも、いかなる特定のＬＤＰＣ復号化アルゴリズムにも限定されないことに留意することが重要である。例えば図２のＬＤＰＣ復号化器２２２の代わりに非層ＬＤＰＣ復号化器５００を用いることができる。
【００２９】
非層ＬＤＰＣ復号化器５００は入力チャネル５０２からＬＬＲ値を与えられ、このＬＬＲ値はＬＬＲメモリ５０４に記憶することができる。記憶された値５０６は加算器／減算器アレイ５１０に与えられる。加算器／減算器アレイ５１０は変数ノードプロセッサ若しくは変数ノードユニット（ＶＮＵ）、又はＶＮＵの一部分とも呼ばれる。加算器／減算器アレイ５０６は、入力チャネル５０２からの値及びＣ２Ｖメッセージベクトル５１２に基づいて、シンボルの認識された値を更新する。加算器／減算器アレイ５１０はチェックサム計算回路５１６に外部ＬＬＲ出力５１４を生成し、チェックサム計算回路５１６はパリティチェック出力５２０を生成する。例えば、チェックサム計算回路５１６はＧＦ（ｑ）に対するパリティチェック方程式
【数２】
2014064269.tif 000004
を計算するマルチプレクサー及びＸＯＲ回路を含むことができる。ここで、
【数３】
2014064269.tif 000005
であり、
【数４】
2014064269.tif 000006
は符号語ベクトルであり、ＨＴはＬＤＰＣ復号化器のためのＨ行列の変形である。加算器／減算器アレイ５１０は、正規化／飽和回路５２４に対し外部ＬＬＲ出力５２２も生成し、正規化／飽和回路５２４は硬判定出力５２６を生成する。
【００３０】
加算器／減算器アレイ５１０は、Ｃ２Ｖメッセージベクトル５１２をシンボル値に加算する更新関数を実行し、データセット内のシンボルごとのガロア体における要素ごとの更新された尤度値又はＬＬＲ値を示すＶ２Ｃメッセージベクトル５３０を生成する。Ｖ２Ｃメッセージベクトル５３０は正規化／スケーリング／飽和回路５３２に与えられ、正規化／スケーリング／飽和回路５３２はＬＬＲ値をスケーリングし、それらを正規化されたＶ２Ｃメッセージベクトル５３４に変換する。正規化されたＶ２Ｃメッセージベクトル５３４は、硬判定（最も可能性が高いＧＦ要素の表示）及びシンボルごとの残りのＧＦ要素のＬＬＲ値を含み、それぞれが硬判定に対し正規化されている。例えば、ＧＦ（４）ＬＤＰＣ復号化器では、正規化／スケーリング／飽和回路５３２はシンボルごとに４つのＬＬＲデータ値をとり、４つの値のうちの最も高いＬＬＲデータ値を特定し、最も高いＬＬＲデータ値の値に対し４つのＬＬＲデータ値を正規化する。この例が、以下の例示的なシンボルを用いて示される。
【表１】
2014064269.tif 000007
【００３１】
この例では、正規化／スケーリング／飽和回路５３２は、硬判定「１０」に対応するＬＬＲデータ値「２２」を選択する。次に、硬判定値「００」、「０１」、「１０」、及び「１１」に対応するＬＬＲデータ値は、ＬＬＲデータ値のそれぞれから「２２」を減算することによってＬＬＲデータ値「２２」に対し正規化され、以下の正規化されたシンボルが生成される。
【表２】
2014064269.tif 000008
【００３２】
ＬＬＲ値は、正規化されたＬＬＲデータ値のそれぞれにスケーリング係数を乗算する正規化／スケーリング／飽和回路５３２においてスケーリングすることもできる。スケーリング係数はユーザープログラム可能とすることができる。例として、０．５のスケーリング係数を用いると、正規化されたＶ２Ｃメッセージベクトル５３４は、現在の例に基づいて以下のスケーリングされたシンボルを含むことができる。
【表３】
2014064269.tif 000009
【００３３】
Ｖ２Ｃメッセージベクトル５３４は再配列器５３６に与えられ、再配列器５３６は、メッセージエッジにおける境界上のメッセージをシャッフルし、雑音をランダム化し、メッセージ間の依存性を断ち、再配列されたＶ２Ｃメッセージベクトル５４０及び５４２を生成する。再配列されたＶ２Ｃメッセージベクトル５４０及び５４２は、それぞれバレルシフター５４４及び５４６に与えられ、バレルシフター５４４及び５４６は再配列されたＶ２Ｃメッセージベクトル５４０及び５４２におけるシンボル値をシフトして次の巡回部分行列を生成し、シフトされたＬＬＲ値５５０及び５５２を生成する。幾つかの実施形態では、入力チャネル５０２において提供される符号語の符号構造は、以下の形式の符号構造行列を含む。
【数５】
2014064269.tif 000010
ここで、ＰＩ、Ｊのそれぞれが重み１を有するｐ×ｐの巡回行列であるか又は恒等行列の置換であり、巡回行列サイズＬは行の重みである。以下はＰＩ、Ｊを表すｐ×ｐの巡回行列の例である。
【数６】
2014064269.tif 000011
【００３４】
バレルシフター５４４及び５４６は、現在受信している巡回行列を恒等行列にシフトするように動作可能である。そのような恒等行列は以下の通りとすることができる。
【数７】
2014064269.tif 000012
【００３５】
バレルシフター５４４はシフトされた出力５５０を与え、シフトされた出力５５０は硬判定ＨＤの大きさ及び正負符号を含む。バレルシフター５４６はシフトされた出力５５２を与え、シフトされた出力５５２は、硬判定ＨＤに対して正規化された、残りのＬＬＲ値の大きさを含む。シフトされた出力５５０はパリティ／ＨＤの計算回路５５４に提供され、パリティ／ＨＤの計算回路５５４はシフトされた出力５５０における硬判定の累積正負符号を計算し、処理されているＨ行列の部分の非ゼロ要素ごとの結果としての正負符号値５５６と硬判定とをパリティ／ＨＤメモリ５６０内に記憶する。
【００３６】
シフトされた出力５５２はＬＬＲ比較回路５６２に提供され、ＬＬＲ比較回路５６２は、処理されているＨ行列の部分内の全ての外因性の（extrinsic）Ｖ２Ｃメッセージに基づいて、ガロア体内の非ゼロシンボルｄごとに、第１の最小ＬＬＲ値又はサブメッセージｍｉｎ１（ｄ）（すなわち最も低いＬＬＲ値）、ｍｉｎ１（ｄ）のインデックスｉｄｘ（ｄ）（すなわち第１の最小ＬＬＲデータ値に対応する行内のロケーション）、及び第２の最小ＬＬＲ値又はサブメッセージｍｉｎ２（ｄ）（すなわち２番目に低いＬＬＲ値）、すなわちｍｉｎ１（ｄ）を除く全てのサブメッセージの最小値を計算する。換言すれば、特定のシンボルｄのためのサブメッセージは、処理されているＨ行列の部分のための全ての外因性の入力からのメッセージから収集され、そのシンボルｄのために収集されたサブメッセージに基づいて、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）が計算される。ｑ個のシンボルを有するガロア体の場合、チェックノードは、最も可能性の高いシンボル、すなわち硬判定ＨＤを除くガロア体内のｑ−１個の非ゼロシンボルのそれぞれについて、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）のサブメッセージを計算することになる。
【００３７】
ここでもまた、Ｈ行列内の列は変数ノードを表し、行はチェックノードを表し、Ｈ行列内の非ゼロ値は、非ゼロ交点における列と行との間の接続を示す。通常、部分ローカル反復処理のための最小和に基づく復号化アルゴリズムは、最も可能性の高いシンボルすなわちＨＤを除くガロア体の非ゼロ要素ごとに、処理されているＨ行列の部分内の接続された変数ノード（又は非ゼロ行値）の中で、ＨＤ以外の非ゼロガロア体要素ごとの最も低いＬＬＲ値及び次に低いＬＬＲ値を求めることによって、処理されているＨ行列の部分又はセグメントにおける各接続された変数ノードからチェックノードへの最も低い外因性の入力値を特定する。
【００３８】
Ｈ行列は複数のセグメント、例えば左側及び右側に分割されるので、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）値は、Ｈ行列の各側について交互に計算され、それよって、部分反復の後に、例えば左側の処理の後に、右側について新たに特定されたｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）の値、並びに左側について以前に特定されたｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）の値に基づいて、又は右側の処理の後に、左側について新たに特定されたｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）の値、並びに右側について以前に特定されたｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）の値に基づいて、チェックノード更新を実行することができる。
【００３９】
ＬＬＲ比較回路５６２において最も低いＬＬＲ値及び次に低いＬＬＲ値の特定が実行され、結果５６４（２セグメントＨ行列の場合）が例えばスイッチ５７２によって左側の結果５６６及び右側の結果５７０に分割される。左側の結果５６６（すなわちｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）値）が左レジスタアレイ５７４内に記憶される。右側の結果５７０（すなわちｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）値）が右レジスタアレイ５７６内に記憶される。２セグメントＬＤＰＣ復号化器のためのレジスタアレイ５７４及び５７６は、各チェックノードすなわちＨ行列の行におけるＨＤ以外の非ゼロＧＦ要素ごとに、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）の値の左のセット及び右のセットを記憶する。ＧＦ（４）復号化器の幾つかの実施形態では、チェックノードすなわちＨ行列の行ごとに、Ｈ行列の左側のためのｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）の３つのレジスタからなるセットが存在し、Ｈ行列の右側のためのｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）の３つのレジスタからなるセットが存在する。３つの行を有する符号構造行列を用いて、左レジスタアレイ５７４及び右レジスタアレイ５７６はそれぞれ、以下の例に示すように、第１の最小ＬＬＲデータ値、第２の最小ＬＬＲデータ値、インデックス値からなる３つのセットを記憶する。
【表４】
2014064269.tif 000013
【００４０】
Ｈ行列の各側についてＬＬＲ比較回路５６２においてＬＬＲ比較プロセスを開始する前に、左レジスタアレイ５７４又は右レジスタアレイ５７６が初期値、例えばゼロにリセットされる。Ｈ行列のその側における各列を処理する際に第１の非ゼロＬＬＲ値が受信されると、その値が初期ゼロ値を上書きする。Ｈ行列のその側における各列の処理が継続するとき、非ゼロＧＦ要素のＬＬＲ値がｍｉｎ１（ｄ）レジスタ内の値よりも低い場合、ｍｉｎ１（ｄ）レジスタは当該非ゼロＧＦ要素のＬＬＲ値を用いて更新され、ｍｉｎ１（ｄ）レジスタ内の以前の値が次に低い値としてｍｉｎ２（ｄ）レジスタ内にコピーされ、ｉｄｘ（ｄ）レジスタが現在機能中の列のインデックスを用いて更新される。非ゼロＧＦ要素のＬＬＲ値がｍｉｎ１（ｄ）レジスタ内の値よりも大きいが、ｍｉｎ２（ｄ）レジスタ内の値よりも低い場合、ｍｉｎ２（ｄ）レジスタは当該ＧＦ要素のＬＬＲ値を用いて更新される。各列が処理されると、このＬＬＲ比較は、チェックノードすなわち列内の行ごとに、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）、及びｍｉｎ２（ｄ）のレジスタからなるセットについて実行される。
【００４１】
ＬＬＲ比較回路５６２におけるＨ行列のセグメントの処理の終了時に、選択ネットワーク５７８が、左レジスタアレイ５７４に記憶されている、記憶された左側の結果５８０（すなわちｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）の値）と、右レジスタアレイ５７６に記憶されている、記憶された右側の結果５８２（すなわちｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）の値）と、に基づいて、チェックノード更新を実行する。チェックノード更新は、片側（例えば５７４）について新たに特定された値と、他方の側（例えば５７６）について以前に特定された値と、に基づき、新たに特定された値を有する側は、Ｈ行列が処理されるのに伴い左側と右側との間で交互になる。例えば、Ｈ行列の左側（例えば４０２）の全ての列が処理されると、更新遅延の後、左レジスタアレイ５７４内に記憶された新たなｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）値と、右レジスタアレイ５７６内に記憶された古いｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）値と、に基づいてチェックノード更新が実行される。次に、Ｈ行列の右側（例えば４０４）が上記で開示されたように処理され、まず右レジスタアレイ５７６をリセットする。Ｈ行列の右側が処理されると、更新遅延（例えば３２０）の後に、左レジスタアレイ５７４内に記憶された古いｍｉｎ１＿ｌ（ｄ）、ｉｄｘ＿ｌ（ｄ）、及びｍｉｎ２＿ｌ（ｄ）値と、右レジスタアレイ５７６内に記憶された新たなｍｉｎ１＿ｒ（ｄ）、ｉｄｘ＿ｒ（ｄ）、及びｍｉｎ２＿ｒ（ｄ）値と、に基づいて別のチェックノード更新を実行することができる。
【００４２】
ＬＬＲ比較回路５６２、レジスタアレイ５７４及び５７６、並びに選択ネットワーク５７８は、まとめてチェックノードプロセッサ又はチェックノードユニット（ＣＮＵ）と呼ぶことができる。本明細書に開示され、単純化された最小和に基づく非層ＬＤＰＣ復号化器の幾つかの実施形態において用いることができる単純化された最小和に基づくＣＮＵは、圧縮回路とも呼ばれる。選択ネットワーク５７８は、ｍｉｎ１（ｄ）又はｍｉｎ２（ｄ）のいずれかを、Ｃ２Ｖメッセージ５１２において用いられることになる出力５８４として選択し、外因性の値のみが選択されるようにする。現在の列インデックスが最小値のインデックスに等しく、Ｃ２Ｖメッセージがｍｉｎ１（ｄ）値を提供した変数ノードについて準備されていることを意味する場合、Ｃ２Ｖメッセージ５１２において用いられることになる値は第２の最小値ｍｉｎ２（ｄ）である。そうでない場合、Ｃ２Ｖメッセージ５１２において用いられることになる値は第１の最小値ｍｉｎ１（ｄ）である。選択ネットワーク５７８は、Ｈ行列の両側から最も低いＬＬＲ値を選択し、それらの両側からのｍｉｎ１（ｄ）又はｍｉｎ２（ｄ）の値も検討する。Ｈ行列の左側を処理するとき、これは以下の式に従って達成することができる。
【数８】
2014064269.tif 000014
（式１）
ここで、ｄはＧＦ要素インデックスであり、ｃｉｒｃ＿ｉｄｘは機能中の列のインデックスであり、すなわち、Ｃ２Ｖメッセージが生成されている変数ノードのインデックスであり、ｉｄｘ＿ｌはｍｉｎ１＿ｌ（ｄ）値の列インデックスである。ＧＦ（４）復号化器の場合、ｄ＝０、１、２である。外側最小ステートメント（outer min statement）は、左側又は右側のいずれかから外因性最小ＬＬＲ値を選択する。この例では、Ｈ行列の左側が処理されているので、機能中の列のインデックスｃｉｒｃ＿ｉｄｘは左側にあり、ｍｉｎ１＿ｒ（ｄ）は機能中の列において変数ノードから到来することができず、したがって外因性入力からのものとなる。対照的に、ｍｉｎ１＿ｌ（ｄ）は機能中の列において変数ノードから到来することができ、このためｉｄｘ＿ｌ（ｄ）は機能中の列インデックスｃｉｒｃ＿ｉｄｘと比較される。それらが等しい場合、ｍｉｎ１＿ｌ（ｄ）は外因性入力ではないので、ｍｉｎ１＿ｌ（ｄ）ではなくｍｉｎ２＿ｌ（ｄ）値が用いられる。特に、Ｈ行列が更に分割される場合、式は３つ以上の部分から選択するように適合することができる。
【００４３】
Ｈ行列の右側を処理するとき、選択ネットワーク５７８は、以下の式に従って、Ｈ行列の両側から最も低いＬＬＲ値を選択する。
【数９】
2014064269.tif 000015
（式２）
ここで、ｉｄｘ＿ｒは右側のｍｉｎ１＿ｒ（ｄ）値の列インデックスである。ここでもまた、外側最小ステートメントは、左側又は右側のいずれかから外因性最小ＬＬＲ値を選択する。この例では、Ｈ行列の右側が処理されているので、機能中の列のインデックスｃｉｒｃ＿ｉｄｘは右側にあり、ｍｉｎ１＿ｌ（ｄ）は機能中の列において変数ノードから到来することができず、したがって外因性入力からのものとなる。対照的に、ｍｉｎ１＿ｒ（ｄ）は機能中の列において変数ノードから到来することができ、このためｉｄｘ＿ｒ（ｄ）は機能中の列インデックスｃｉｒｃ＿ｉｄｘと比較される。それらが等しい場合、ｍｉｎ１＿ｒ（ｄ）は外因性入力ではないので、ｍｉｎ１＿ｒ（ｄ）ではなくｍｉｎ２＿ｒ（ｄ）値が用いられる。
【００４４】
Ｃ２Ｖメッセージベクトル５１２の一部分を形成するガロア体の要素ごとのＲ値又はＬＬＲ値が、選択ネットワーク５７８において、例えばＧＦ（４）ＬＤＰＣ復号化器において式３〜５に従って、ｓｅｌ［ｄ］に基づいて計算される。
【数１０】
2014064269.tif 000016
（式３）
【数１１】
2014064269.tif 000017
（式４）
【数１２】
2014064269.tif 000018
（式５）
【００４５】
より多くのガロア体要素を有するＬＤＰＣ復号化器の場合、追加のＲ項について更なる式が存在することになる。
【００４６】
Ｃ２Ｖメッセージ５１２において用いられる硬判定ＨＤ及び正負符号は、パリティ／ＨＤメモリ５６０の出力５８６において与えられ、正負符号又はパリティはシンボルの累積正負符号及び現在の正負符号のＸＯＲとして計算される。Ｃ２Ｖメッセージベクトル５１２において硬判定値として用いられるＲ＿ＨＤ値は、式６に従って計算することができる。
【数１３】
2014064269.tif 000019
（式６）
ここで、ｓｇｎ＿ｌ及びｓｇｎ＿ｒはＨ行列の部分ごとの正負符号又はパリティ値であり、Ｑ＿ＨＤはＶ２Ｃメッセージベクトル５４０における以前の硬判定であり、ＸＯＲ演算において結合される。ここでもまた、Ｈ行列が３つ以上の部分に分割される場合、式６は追加の正負符号の項を有することになる。式１〜式６を実施するのに用いられるハードウェアは、Ｈ行列の部分ごとに共有し用いることもできるし、Ｈ行列の部分ごとに複製することもできる。
【００４７】
パリティ／ＨＤメモリ５６０の出力５８６及び選択ネットワーク５７８の出力５８４は、それぞれバレルシフター５８８及び５９０に提供される。バレルシフター５８８及び５９０は、出力５８６における硬判定及びそれらの正負符号、並びに出力５８４におけるＣ２Ｖメッセージ値をシフトして、それぞれ、巡回行列部分行列間をシフトする、シフトされた硬判定及び正負符号５９２並びにシフトされたＣ２Ｖメッセージ値５９４を生成する。シフトされたＣ２Ｖメッセージ値５９４並びにシフトされた硬判定及び正負符号５９２は結合され、逆再配列器５９６において処理される。逆再配列器５９６は入力５９２及び５９４を結合し、再配列器５３６の効果を逆転させ、Ｃ２Ｖメッセージベクトル５１２を生成する。逆再配列器５９６の結合部分は、本明細書において、データ復元回路と呼ばれ、行を再組み立てして、元のデータの近似値を生成する。
【００４８】
部分反復スケジューラー５９９は、外部検出器（例えばチャネル検出器２０４又は２１０）における処理時間に基づいて、グローバル反復中に非層ＬＤＰＣ復号化器５００において実行すべき完全なローカル符号化反復及び部分ローカル符号化の数を求める。幾つかの実施形態では、部分反復スケジューラー５９９は、検出器処理時間を超えることなく検出器処理時間に近づくことになる完全なローカル符号化反復及び部分ローカル符号化の数を割り当てる。幾つかの他の実施形態では、部分反復スケジューラー５９９は復号化器処理時間が検出器処理時間を僅かに超えることを許可することができる。部分反復スケジューラー５９９は、グローバルローカル復号化反復の開始時、反復中、又は終了時に、部分ローカル復号化反復を実行させることができる。部分反復スケジューラー５９９は、予め、又はグローバル復号化反復の開始時に、非層ＬＤＰＣ復号化器５００において実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数を求めることもできるし、各ローカル復号化反復の開始時に、検出器処理時間を超えることなく完全なローカル復号化反復又は部分ローカル復号化反復のための十分な復号化器処理時間が残っているか否かを判断することもできる。
【００４９】
幾つかの実施形態では、部分反復スケジューラー５９９は同じデータセットについて復号化器処理時間と検出器処理時間とのバランスをとる。これらの実施形態では、検出器及び復号化器がピンポンデータ処理方式の任意の時点において異なるデータセットを処理している場合があるので、単一のタイムスロットの検出器及び復号化器の処理時間はバランスがとられていない場合があるが、データセット群について検出器及び復号化器の平均処理時間のバランスがとられることになる。他の実施形態では、部分反復スケジューラー５９９は、現在復号化されているデータセットの復号化器処理時間と、現在検出されているデータセットの検出器処理時間とのバランスをとることができるが、これらは異なるデータセットである場合がある。
【００５０】
図６Ａ及び図６Ｂを参照すると、本発明の幾つかの実施形態による、Ｈ行列６００及び６５０を複数のセグメントに分割して、ＬＤＰＣ層復号化器における部分ローカル反復を可能にすることが示されている。層復号化器において、Ｈ行列６００及び６５０が層において復号化される。ここで各層は１つ又は複数の行を含んでいる。層は、復号化器において現在処理されている単数又は複数の行を指す。層復号化器における各ローカル復号化反復中、Ｈ行列内の各行は１回処理される。
【００５１】
ＬＤＰＣ層復号化器において部分ローカル反復が無効にされている場合、又はグローバル復号化反復中に、検出器処理時間に合わせるために部分ローカル反復が必要とされない場合、Ｈ行列の層復号化は図６Ａに示す通りにすることができる。この例では、Ｈ行列６００は３つの層（異なるクロスハッチパターンによって区別される）を含み、それらの層のそれぞれがＨ行列の１つ又は複数の行を含むことができる。Ｈ行列６００の３つ全ての層が、この例の第１のローカル反復６０２、第２のローカル反復６０４、及び第３の最後の反復６０６中に完全に処理される。このため、ＬＤＰＣ層復号化器におけるグローバル復号化反復６１０は、それぞれＨ行列６００の全ての層を含む３つの完全なローカル復号化反復を実行する。
【００５２】
ＬＤＰＣ層復号化器において部分ローカル反復が可能にされるか又は用いられるとき、Ｈ行列の１つ又は複数の層をローカル復号化反復から除外することができる。例えば、図６Ｂに示すように、Ｈ行列６５０の最初２つの層６６４及び６６６を部分ローカル反復６５２における処理から除外することができ、最後の層６６２のみを処理してＬＤＰＣ層復号化器における第１のローカル反復６５２の処理時間を低減する。このため、グローバル反復６６０は、第１のローカル反復６５２においてＨ行列６５０の最後の層６６２を処理することによって開始し、その後２つの完全なローカル反復６５４及び６５６が続く。このため、ＬＤＰＣ層復号化器における部分ローカル反復は、Ｈ行列６５０における層のサブセットのみを処理することによって達成される。チェックノード計算を実行し、部分ローカル反復のためのＣ２Ｖメッセージを生成するとき、古いデータ及び新たなデータを結合してＨ行列６５０全体のためのＣ２Ｖメッセージを生成することができる。ここで、Ｃ２Ｖメッセージは部分ローカル反復において最後に処理された層の新たなデータと、部分ローカル反復から除外された層についての古いデータと、に基づく。この古いデータは、これらの層が処理された最新の完全なローカル反復から得られる。
【００５３】
図７を参照すると、本発明の幾つかの実施形態による、単純化された最小和に基づく復号化アルゴリズムを適用する、部分ローカル反復を用いたＬＤＰＣ層復号化器７００が開示されている。ここでもまた、部分ローカル反復を用いたＬＤＰＣ層復号化器７００が、最小和に基づく復号化とともに用いることにも、いかなる特定のＬＤＰＣ復号化アルゴリズムにも限定されないことに留意することが重要である。ＬＤＰＣ層復号化器７００は、例えば、図２のＬＤＰＣ復号化器２２２の代わりに用いることができる。この例示的な実施形態では、２つの巡回行列が並列に処理される。復号化器メモリ７０２は、軟ＬＬＲ入力値、Ｑ値、及び軟ＬＬＲ出力Ｐ値を記憶する。復号化器メモリ７０２はピンポンメモリである。復号化器メモリ７０２は、それぞれ処理されている異なる巡回行列に基づいて、接続された（又は前の）層のＱ値７０４及び７０６をそれぞれ変換器７１０及び７１２に提供する。ＧＦ（４）の実施形態では、Ｑ値７０４及び７０６はそれぞれ１つの硬判定及び３つの軟ＬＬＲ値からなる。
【００５４】
変換器７１０及び７１２は、Ｑ値を、硬判定及び３つの軟ＬＬＲ値を含むフォーマットから４つの軟ＬＬＲ値を含むフォーマットに変換する。情報は２つのフォーマットにおいて等しい。加算器７１４及び７１６は接続された層のＱ値（変換器７１０及び７１２によって変換される）を、巡回行列の各シンボルの接続された層のＲ値７１８及び７２０にそれぞれ加算し、各シンボルの軟ＬＬＲ値７２２及び７２４を生成する。ＧＦ（４）を用いた一実施形態では、各加算器７１４及び７１６はそれぞれ４つの加算器からなり、接続された層のＱ値に巡回行列の各シンボルの接続された層のＲ値をそれぞれ加算して、各シンボルの軟ＬＬＲ値７２２及び７２４を得るように構成されている。
【００５５】
各シンボルの軟ＬＬＲ値７２２及び７２４は正規化器７２６及び７２８に提供される。正規化器７２６及び７２８は軟ＬＬＲ値７２２及び７２４のそれぞれにおいて４つの値を比較してそれぞれの最小値を特定し、その最小値を他の３つの軟ＬＬＲ値から減算し、それによって軟ＬＬＲ値７２２及び７２４のそれぞれを、それらのそれぞれの最小値に対し正規化する。
【００５６】
正規化器７２６及び７２８からの正規化された変数ノードＬＬＲ値が置換回路７３０及び７３２に提供される。置換回路７３０及び７３２は変数ノード更新値を再配列して、チェックノード更新を準備し、Ｈ行列の非ゼロ要素によって指定された置換を適用する。ＧＦ（４）の実施形態では、ガロア体の４つの要素０〜３は、０、１、α、α２である。置換回路７３０及び７３２によって適用される置換はガロア体における乗算である。要素２（α）に要素１（１）を乗算したものはα×１すなわちαに等しく、これは要素２である。同様に、要素２×２＝α×α＝α２であり、これは要素３である。要素２×３＝α×α２＝１であり、これは要素１である。このため、要素２に１、２、及び３を乗算した結果、要素２、３、及び１となり、これらは要素１、２、及び３の置換である。パリティチェック計算において、各硬判定値はＨ行列の非ゼロ要素（１、２、又は３）を乗算され、結果が合わせてＸＯＲされる。
【００５７】
シフター７３４及び７３６は、置換回路７３０及び７３２の出力を処理して、軟ＬＬＲ値を列の順序に戻すようにシフトし、パリティチェック計算機によって用いられる硬判定（例えばパリティチェック計算機５００によって用いられる硬判定５０２及び５０４）として軟ＬＬＲ出力７３８及び７４０を生成する。シフター７３４及び７３６を用いて行の順序から列の順序にシフトする。なぜなら、ＬＤＰＣ層復号化器７００はデータを行の順序で処理するが、出力される合計の軟ＬＬＲは、列の順序となっている入力ＬＬＲを減算して外因性のＬＬＲ値を得るために列によって順序付けされるためである。デルタシフター７４２及び７４４も置換回路７３０及び７３２の出力を処理し、置換回路７３０及び７３２の出力を、現在の層及び接続された層の巡回行列シフト数における差だけシフトする。所与の列では、様々なシフト数を有する巡回行列が存在し、デルタシフター７４２及び７４４は現在の層及び接続された層の異なるシフト数を補償する。
【００５８】
デルタシフター７４２及び７４４の出力が変換器７４６及び７４８に与えられ、変換器７４６及び７４８は１つの硬判定及び３つの軟ＬＬＲ値を含むフォーマットから、４つの軟ＬＬＲ値を含むフォーマットに戻すように変換する。次に、減算器７５０及び７５２は、変換器７４６及び７４８によって提供された軟ＬＬＲ  Ｐ値から現在の層のシンボルのＲ値７５４及び７５６を減算し、現在の層のシンボルのＱ値７５８及び７６０を得る。次に、現在の層のシンボルのＱ値７５８及び７６０が正規化器７６２及び７６４において正規化され、正規化器７６２及び７６４はＱ値７５８及び７６０のそれぞれにおける４つの値を比較して、それぞれの最小値を特定し、その最小値をＱ値７５８及び７６０の他の３つの要素から減算し、それによってＱ値７５８及び７６０のそれぞれを、それらのそれぞれの最小値に対して正規化する。正規化されたＱ値７７０及び７７２が復号化器メモリ７０２に提供されて、現在の層のＱ値が更新され、スケーラー７７４及び７７６にも提供されて、チェックノードから変数ノードへの更新を実行するための新たなＱ値を得る。
【００５９】
スケーラー７７４及び７７６は、正規化器７６２及び７６４からの正規化されたＱ値７７０及び７７２をスケーリングし、新たなＱ値７７８及び７８０を生成するか、又はＱ値正負符号７８２及び７８４とともに絶対軟値を生成する。新たなＱ値７７８及び７８０並びにそれらの正負符号７８２及び７８４はチェックノードユニット７８６に提供され、チェックノードユニット７８６は、最小値と、第２のすなわち次の最小値と、最小値のインデックスと、を求める。新たなＱ値の正負符号７８２及び７８４は正負符号累算器７９０及び正負符号メモリにも提供される。正負符号累算器７９０はＱ値７７８及び７８０の現在の層の累積正負符号を計算及び記憶し、正負符号メモリ７９２はＨ行列の各非ゼロ要素の正負符号値を記憶する。
【００６０】
最終状態レジスタ７９４は、最小値、第２の最小値、最小値のインデックス、及び現在の層の累積正負符号からなる最終状態を記憶する。これらの最終状態値は２組のＲ生成器７９５、７９６、７９７、及び７９８に提供され、これらはシンボルの最終状態及び現在の列インデックスに基づいて、接続された層又は現在の層のＲ値を生成する。Ｒ生成器７９５及び７９６は処理されている２つの巡回行列の現在の層のＲ値を生成し、Ｒ生成器７９７及び７９８は処理されている２つの巡回行列の接続された層のＲ値を生成する。現在の列インデックスが最小値のインデックスに等しい場合、Ｒの値は第２の最小値である。そうでない場合、Ｒの値はその層の最小値である。Ｒの正負符号は、シンボルの累積正負符号及び現在の正負符号のＸＯＲである。
【００６１】
ＬＤＰＣ層復号化器７００の動作中、Ｑ値及びＲ値が復号化器７００を通じて反復的に循環すると、パリティチェック計算機７９９は軟ＬＬＲ出力７３８及び７４０に基づいてパリティチェックを計算する。全ての層が処理された後、パリティチェック計算機７９９によって計算された、満たされていないチェックの数がゼロに等しい場合、ＬＤＰＣ層復号化器７００は収束しており、処理は停止することができ、復号化されたデータをコントローラー７０５に提供することができる。
【００６２】
部分反復スケジューラー７０３は、外部の検出器（例えばチャネル検出器２０４又は２１０）における処理時間に基づいて、グローバル反復中にＬＤＰＣ層復号化器７００において実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数を求める。幾つかの実施形態では、部分反復スケジューラー７０３は、検出器処理時間を超えることなく、検出器処理時間に近づく完全なローカル復号化反復及び部分ローカル復号化反復の数を割り当てる。幾つかの他の実施形態では、部分反復スケジューラー７０３は、復号化器処理時間が僅かに検出器処理時間を超えることを許可することができる。部分反復スケジューラー７０３は、グローバルローカル復号化反復の開始時、反復中、又は終了時に、部分ローカル復号化反復を実行させることができる。部分反復スケジューラー７０３は、予め、又はグローバル復号化反復の開始時に、層ＬＤＰＣ復号化器７００において実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数を求めることもできるし、各ローカル復号化反復の開始時に、検出器処理時間を超えることなく完全なローカル復号化反復又は部分ローカル復号化反復のための十分な復号化器処理時間が残っているか否かを判断することもできる。
【００６３】
図８を参照すると、本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を用いたデータ検出及び復号化動作の流れ図８００が示されている。流れ図８００に従って、データセット又はセクターがデータ入力において受信される（ブロック８０２）。データ検出器が利用可能であるとき（ブロック８０４）、データセクターはデータ検出器において次に処理されるように選択される（ブロック８０６）。これはデータ入力からの新たなデータセクターとすることもできるし、別のグローバル反復で処理されるデータ復号化器出力からの復号化されたデータセクターとすることもできる。選択されたデータセクターに対しデータ検出アルゴリズムが実行される（ブロック８１０）。データセクターについて、検出器処理時間が求められる（ブロック８１２）。検出器処理時間は、クロックサイクル単位で、又は任意の他の測定単位で測定することもできるし、予期される処理時間又は標準処理時間に対して指定することもできる。検出器処理時間は、データセットごとに１回計算することもできるし、データセットが検出器を通過するごとに計算することもできる。
【００６４】
データ検出プロセスと並行して、データ復号化プロセスを実行することができる。データセットはデータ検出器とデータ復号化器との間で、ピンポン形式で交互になっている。データ復号化器が利用可能であるとき（ブロック８２０）、復号化されることになるデータ検出器出力からのデータセットが選択される（ブロック８２２）。幾つかの実施形態では、データセットは中央ピンポンバッファーにおいてデータ検出器とデータ復号化器との間でバッファリングされる。同じデータセクターについて復号化処理時間が検出器処理時間を超えることを防ぎながら、復号化器における用いられない処理サイクルを低減するように、データ復号化器において実行すべき完全なローカル復号化反復及び部分ローカル復号化反復の数が求められる（ブロック８２４）。完全なローカル復号化反復及び部分ローカル復号化反復の数は、復号化の前に求めることもできるし、検出器処理時間を復号化器に対し指定して、復号化器が、復号化器におけるあと１回の完全な反復によって、復号化器処理時間がそのセクターについて検出器処理時間を超えることになるまで、データセットを通常通りに処理することを可能にすることもできる。その時点において、復号化器は、部分反復によって復号化器処理時間が検出器処理時間を超えない場合、部分反復を実行することができる。求められた数の完全なローカル復号化反復及び部分ローカル復号化反復がデータ復号化器において選択されたデータセクターに対し実行される（ブロック８２６）。データが収束しているか、又は最大数のグローバル反復がそのデータセットに対し実行された場合、検出／復号化されたデータセットが出力される（ブロック８３０）。データセットは出力された後、検出器／復号化器処理システムから除去され、データ入力からの新たなデータセクターのための空間を提供する。
【００６５】
本明細書において開示される部分ローカル反復を用いたＬＤＰＣ復号化器はいかなる特定の用途にも限定されないが、本発明の実施形態から利益を受ける用途の幾つかの例が図９及び図１０に提示されている。図９を参照すると、本発明の幾つかの実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を有する読取りチャネル回路９０２を含む記憶デバイス９００が示されている。記憶システム９００は、例えば、ハードディスクドライブとすることができる。記憶システム９００は、前置増幅器９０４、インターフェースコントローラー９０６、ハードディスクコントローラー９１０、モーターコントローラー９１２、スピンドルモーター９１４、ディスクプラッター９１６、及び読取り／書込みヘッド９２０も備える。インターフェースコントローラー９０６はディスクプラッター９１６への／からのデータのアドレス指定及びタイミングを制御する。ディスクプラッター９１６上のデータは、アセンブリがディスクプラッター９１６上に適切に位置決めされているときに読取り／書込みヘッドアセンブリ９２０によって検出することができる磁気信号の群からなる。１つの実施形態では、ディスクプラッター９１６は長手記録方式又は垂直記録方式のいずれかに従って記録される磁気信号を含む。
【００６６】
通常の読取り動作において、読取り／書込みヘッドアセンブリ９２０はモーターコントローラー９１２によって、ディスクプラッター９１６上の所望のデータトラックの上方に正確に位置決めされる。モーターコントローラー９１２は、ハードディスクコントローラー９１０の指示の下で読取り／書込みヘッドアセンブリ９２０をディスクプラッター９１６上の適切なデータトラックに移動することによって、ディスクプラッター９１６に対して読取り／書込みヘッドアセンブリ９２０を位置決めし、かつスピンドルモーター９１４を駆動する。スピンドルモーター９１４所定のスピンレート（ＲＰＭ）でディスクプラッター９１６をスピンさせる。読取り／書込みヘッドアセンブリ９２０が適切なデータトラックに近接して位置決めされると、ディスクプラッター９１６がスピンドルモーター９１４によって回転するのに応じてディスクプラッター９１６上のデータを表す磁気信号が読取り／書込みヘッドアセンブリ９２０によって感知される。感知された磁気信号は、ディスクプラッター９１６上の磁気データを表す連続した微小アナログ信号として与えられる。この微小アナログ信号は、読取り／書込みヘッドアセンブリ９２０から、前置増幅器９０４を介して、読取りチャネル回路９０２に送信される。前置増幅器９０４は、ディスクプラッター９１６からアクセスされた微小アナログ信号を増幅するように動作可能である。そして、読取りチャネル回路９０２は受信したアナログ信号を復号及びデジタル化し、ディスクプラッター９１６に元々書き込まれた情報を再生する。このデータは、読取りデータ９２２として受信回路に与えられる。受信した情報を復号化することの一部として、読取りチャネル回路９０２は部分ローカル反復を用いたＬＤＰＣ復号化器を用いて受信した信号を処理する。部分ローカル反復を用いたそのようなＬＤＰＣ復号化器は、図２〜図７に関連して上記で開示したものに沿って実装することができる。幾つかの例では、部分ローカル反復を用いたＬＤＰＣ復号化は、図８に関連して上記で開示した流れ図に沿って実行することができる。書込み動作は実質的に、先行する読取り動作の反対であり、書込みデータ９２４が読取りチャネル回路９０２に与えられる。次にこのデータは符号化され、ディスクプラッター９１６に書き込まれる。記憶システム９００の様々な機能又はブロックをソフトウェア又はファームウェアのいずれかに実装することができる一方、他の機能又はブロックはハードウェアに実装されることに留意すべきである。
【００６７】
例えばＲＡＩＤ（安価なディスクの冗長アレイ又は独立ディスクの冗長アレイ）に基づく記憶システム等のより大型の記憶システムに、記憶システム９００を統合することができる。このようなＲＡＩＤ記憶システムは、複数のディスクを論理ユニットとして結合し、冗長性を通じて安定性及び信頼性を増大させる。データは、種々のアルゴリズムに従って、ＲＡＩＤ記憶システムに含まれる複数のディスクにわたって拡散させることができ、ＲＡＩＤ記憶システムが単一のディスクであるかのようにオペレーティングシステムがアクセスすることができる。例えば、データはＲＡＩＤ記憶システム内の複数のディスクにミラーリングすることもできるし、複数の技法において複数のディスクにわたってスライスし分散させることもできる。ＲＡＩＤ記憶システム内の少数のディスクが故障するか又は利用不可能になる場合、誤り訂正技法を用いて、ＲＡＩＤ記憶システム内の他のディスクからのデータの残りの部分に基づいて、欠落データを再生することができる。ＲＡＩＤ記憶システム内のディスクは、限定ではないが、記憶システム９００等の個別の記憶システムとすることができ、互いに近接して配置することもできるし、セキュリティを増大させるために、より広範に分散させることもできる。書込み動作において、書込みデータがコントローラーに提供され、コントローラーは、例えば書込みデータのミラーリング又はストライピングによって、ディスクにわたって書込みデータを記憶する。読取り動作において、コントローラーはディスクからデータを検索する。次に、コントローラーは、ＲＡＩＤ記憶システムが単一のディスクであるかのように結果の読取りデータを生成する。
【００６８】
図１０を参照すると、本発明の様々な実施形態による、部分ローカル反復を用いたＬＤＰＣ復号化器を有する受信機１００４を備えるデータ送信システム１０００が示されている。データ送信システム１０００は、当該技術分野において既知の、符号化された情報を転送媒体１００６を介して送信するように動作可能な送信機１００２を備える。符号化データは受信機１００４によって転送媒体１００６から受信される。受信機１００４は、受信した入力を処理して元々送信されたデータを生成する。受信した情報の処理の一部として、受信機１００４は部分ローカル反復を用いたＬＤＰＣ復号化器を用いて受信したデータを復号する。部分ローカル反復を有するそのようなＬＤＰＣ復号化器は、図２〜図７に関連して上記で開示したものに沿って実施することができる。幾つかの場合、部分ローカル反復を用いたＬＤＰＣ復号化は、図８に関連して上記で開示した流れ図に沿って実行することができる。
【００６９】
上記の応用形態において論述した様々なブロックは、他の機能とともに集積回路に実装することができることに留意すべきである。そのような集積回路は、所与のブロック、システム若しくは回路の機能の全て、又はブロック、システム若しくは回路の機能の一部を含むことができる。また、ブロック、システム又は回路の要素を複数の集積回路にわたって実装することができる。そのような集積回路は、モノリシック集積回路、フリップチップ集積回路、マルチチップモジュール集積回路及び／又は混合信号集積回路を含むが、これらに限定されるものではない、当該技術分野において知られている任意のタイプの集積回路とすることができる。本明細書において論述されたブロック、システム又は回路の様々な機能を、ソフトウェア又はファームウェアのいずれかで実装することができることにも留意すべきである。そのような幾つかの場合には、システム全体、ブロック全体又は回路全体を、そのソフトウェア等価物又はファームウェア等価物を用いて実装することができる。他の場合には、所与のシステム、ブロック又は回路の一部分をソフトウェア又はファームウェアで実装することもできる一方、他の部分はハードウェアで実装される。
【００７０】
結論として、本発明は、部分ローカル反復を用いたＬＤＰＣ復号化器のための新規なシステム、デバイス、方法、及び構成を提供する。本発明の１つ又は複数の実施形態の詳細な説明が上記で与えられたが、本発明の趣旨から逸脱することなく、様々な代替形態、修正形態及び均等物が当業者には明らかであろう。したがって、上記の説明は本発明の範囲を限定するものとして解釈されるべきではなく、本発明の範囲は添付の特許請求の範囲によって規定される。
【図１】
2014064269.tif 000020
【図２】
2014064269.tif 000021
【図３】
2014064269.tif 000022
【図４】
2014064269.tif 000023
【図５】
2014064269.tif 000024
【図６】
2014064269.tif 000025
【図７】
2014064269.tif 000026
【図８】
2014064269.tif 000027
【図９】
2014064269.tif 000028
【図１０】
2014064269.tif 000029