(57)【要約】      （修正有）【課題】復号化器回路と、シンドローム計算回路と、ハッシュ計算回路とを備えるデータ処理システムを提供する。【解決手段】復号化器回路は、合成行列の第１の部分に基づいて復号化アルゴリズムを復号化器入力に適用して、符号語を生成するように動作可能である。シンドローム計算回路は、符号語と合成行列の第１の部分とに基づいてシンドロームを計算するように動作可能である。ハッシュ計算回路は、合成行列の第２の部分に基づいてハッシュを計算するように動作可能である。復号化器回路は、シンドロームが、合成行列の第１の部分に基づく符号語が正しいことを示すが、第２のテストが、符号語が誤訂正されていることを示すときに、ハッシュに基づいて符号語を訂正するように動作可能でもある。【選択図】図５
2014116927.tif 000002
【特許請求の範囲】
【請求項１】
データ処理システムであって、
合成行列の第１の部分に基づいて復号化アルゴリズムを復号化器入力に適用して符号語を生成するように動作可能な復号化器回路と、
前記符号語と前記合成行列の前記第１の部分とに基づいてシンドロームを計算するように動作可能なシンドローム計算回路と、
前記合成行列の第２の部分に基づいてハッシュを計算するように動作可能なハッシュ計算回路と、
を備え、前記シンドロームが、前記合成行列の前記第１の部分に基づく前記符号語が正しいことを示すが、第２のテストが、前記符号語が誤訂正されていることを示すとき、前記復号化器回路は、前記ハッシュに少なくとも部分的に基づいて前記符号語を訂正するように動作可能である、データ処理システム。
【請求項２】
前記復号化器回路は低密度パリティ検査復号化器を備え、前記合成行列はパリティ検査行列を含む、請求項１に記載のデータ処理システム。
【請求項３】
前記合成行列全体に基づいて前記復号化アルゴリズムを前記復号化器入力に再適用することによって、前記復号化器回路に前記符号語を訂正させるように動作可能な誤訂正ハンドリング処理回路を更に備える、請求項１に記載のデータ処理システム。
【請求項４】
前記第２のテストは、前記ハッシュを期待値と比較することを含む、請求項１に記載のデータ処理システム。
【請求項５】
前記第２のテストは、前記符号語に基づいて計算された巡回冗長検査ビットを前記復号化器入力における入力元の巡回冗長検査ビットと比較する巡回冗長検査を含む、請求項１に記載のデータ処理システム。
【請求項６】
前記ハッシュを用いて部分符号語を探索し、該部分符号語を前記符号語と結合することによって、前記復号化器回路を用いて前記符号語を訂正するように動作可能な誤訂正ハンドリング処理回路を更に備える、請求項１に記載のデータ処理システム。
【請求項７】
前記誤訂正ハンドリング処理回路は、前記ハッシュを用いて、部分符号語及びハッシュ値の対のルックアップテーブルにおいて前記部分符号語を探索するように動作可能である、請求項６に記載のデータ処理システム。
【請求項８】
前記誤訂正ハンドリング処理回路は、前記部分符号語を前記符号語と結合することが前記誤訂正された符号語を訂正するか否かを、前記部分符号語を前記符号語と結合したことによる結果の符号語を期待値と比較することによって判断するように動作可能である、請求項６に記載のデータ処理システム。
【請求項９】
前記誤訂正ハンドリング処理回路は、前記部分符号語を前記符号語と結合することが前記誤訂正された符号語を訂正するか否かを、巡回冗長検査を用いて判断するように動作可能である、請求項６に記載のデータ処理システム。
【請求項１０】
前記合成行列に対応するパリティ生成行列に基づいて入力データを符号化するように動作可能な低密度パリティ検査符号化器回路を更に備える、請求項１に記載のデータ処理システム。
【請求項１１】
前記入力データを符号化して不要なデータパターンを除外するように動作可能なパターン制約符号化器を更に備え、前記復号化器入力は、前記低密度パリティ検査符号化器の出力から取り出され、前記低密度パリティ検査符号化器回路は、前記合成行列の前記第２の部分に対応するパリティビットを生成するように動作可能であり、前記パリティビットは、前記パターン制約符号化器を通過することなく前記復号化器回路に提供される、請求項１０に記載のデータ処理システム。
【請求項１２】
前記合成行列の前記第２の部分に対応する前記復号化器入力内のパリティビットは、線形性を満たす、請求項１に記載のデータ処理システム。
【請求項１３】
前記データ処理システムは、記憶デバイス及び受信デバイスからなる群から選択されるデバイスの一部として実施される、請求項１に記載のデータ処理システム。
【請求項１４】
前記データ処理システムは、集積回路として実施される、請求項１に記載のデータ処理システム。
【請求項１５】
データを復号化する方法であって、
合成行列の第１の部分に基づいて復号化アルゴリズムを前記データに適用することであって、符号語を生成することと、
前記符号語と前記合成行列の前記第１の部分とを乗算することであって、シンドロームを生成することと、
前記合成行列の第２の部分に基づいて前記復号化アルゴリズムを前記データに適用することであって、第２の符号語を生成することと、
前記第２の符号語と前記合成行列の前記第２の部分とを乗算することであって、ハッシュを生成することと、
前記シンドロームが、前記符号語が正しいことを示すが、第２のテストが、前記符号語が誤訂正されていることを示すとき、前記ハッシュに少なくとも部分的に基づいて前記符号語を訂正することと、
を含む、データを復号化する方法。
【請求項１６】
前記シンドロームが、前記符号語が正しいことを示すが、前記第２のテストが、前記符号語が誤訂正されていることを示すとき、前記符号語は、前記合成行列全体に基づいて前記復号化アルゴリズムを前記データに再適用することによって訂正される、請求項１５に記載の方法。
【請求項１７】
前記符号語は、前記ハッシュを用いて、部分符号語及びハッシュ値の対のルックアップテーブルにおいて部分符号語を探索し、前記部分符号語を前記符号語と排他的ＯＲ演算で結合することによって訂正される、請求項１５に記載の方法。
【請求項１８】
前記訂正された符号語を、巡回冗長検査を用いてテストすることを更に含む、請求項１７に記載の方法。
【請求項１９】
前記第２のテストは、前記ハッシュを期待値と比較することを含む、請求項１５に記載の方法。
【請求項２０】
記憶システムであって、
記憶媒体と、
前記記憶媒体に対して配置されるとともに前記記憶媒体上の情報に対応する検知信号を提供するように動作可能なヘッドアセンブリと、
データ処理システムと、
を備え、前記データ処理システムは、
前記検知信号から取り出されたアナログ信号をサンプリングして一連のデジタルサンプルを生成するように動作可能なアナログ／デジタル変換器回路と、
前記デジタルサンプルを等化してデータセットを生成するように動作可能な等化器回路と、
データ検出アルゴリズムを前記データセットに適用して、検出された出力を生成するように動作可能なデータ検出器回路と、
データ復号化回路と、
を備え、前記データ復号化回路は、
合成行列の第１の部分に基づいて復号化アルゴリズムを前記検出された出力に適用して符号語を生成するように動作可能な復号化器と、
前記符号語と前記合成行列の前記第１の部分とに基づいてシンドロームを計算するように動作可能なシンドローム計算回路と、
前記合成行列の第２の部分に基づいてハッシュを計算するように動作可能なハッシュ計算回路と、
を備え、前記シンドロームが、前記合成行列の前記第１の部分に基づく前記符号語が正しいことを示すが、第２のテストが、前記符号語が誤訂正されていることを示すとき、前記復号化器は、前記ハッシュに少なくとも部分的に基づいて前記符号語を訂正するように動作可能である、記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の様々な実施形態は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化のためのシステム及び方法を提供する。
【背景技術】
【０００２】
記憶システム、携帯電話システム、及び無線伝送システムを含む様々なデータ転送システムが開発されてきた。そのようなシステムでは、データが或る送信機から媒体を介して
受信機に転送される。例えば、記憶システムでは、データは、送信機（すなわち、書込み機能部）から記憶媒体を介して受信機（すなわち、読取り機能部）に送信される。場合によっては、データ処理機能部がデータセットを受信し、データ復号化アルゴリズムをそれらのデータセットに適用して、最初に書き込まれたデータセットを回復する。また、場合によっては、データ復号化プロセスを適用することは、結果が実際には正しくないときでも、内部の復号化器メトリックがその結果が正しいことを示唆している場合には、正しい結果を提供する。そのような誤訂正は、検出するのが困難である可能性があり、受信側デバイスの動作に致命的となる場合がある。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
復号化器回路と、シンドローム計算回路と、ハッシュ計算回路とを備えるデータ処理システムが開示される。
【課題を解決するための手段】
【０００４】
復号化器回路は、合成行列の第１の部分に基づいて復号化アルゴリズムを復号化器入力に適用して、符号語を生成するように動作可能である。シンドローム計算回路は、符号語と合成行列の第１の部分とに基づいてシンドロームを計算するように動作可能である。ハッシュ計算回路は、合成行列の第２の部分に基づいてハッシュを計算するように動作可能である。復号化器回路は、シンドロームが、合成行列の第１の部分に基づく符号語が正しいことを示すが、第２のテストが、符号語が誤訂正されていることを示すときに、ハッシュに基づいて符号語を訂正するように動作可能でもある。
【０００５】
この概要は、本発明による幾つかの実施の形態の概略のみを提供するものである。更なる実施形態は、以下の詳細な説明、添付の特許請求の範囲、及び添付の図面に開示される。
【０００６】
図を参照することにより、本発明の様々な実施形態の更なる理解を実現することができ、これらの実施の形態については明細書の残りの部分で説明する。図において、同様の参照符号が幾つかの図面の全てにわたって類似の構成要素を指すのに用いられる場合がある。
【図面の簡単な説明】
【０００７】
【図１】本発明の１つ又は複数の実施形態による、生成行列と、トランケートされた部分行列Ｈ及び特別階層（special layer）Ｓを含む対応するパリティ検査行列とを示す図である。
【図２】本発明の１つ又は複数の実施形態による、符号化システムと、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備える復号化システムとを有するデータ処理システムを示す図である。
【図３】本発明の１つ又は複数の実施形態による、誤訂正サポート処理を伴う低密度パリティ検査符号化器を備える符号化システムを示す図である。
【図４】本発明の１つ又は複数の実施形態による、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備える復号化システムを示す図である。
【図５】本発明の幾つかの実施形態による、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器のブロック図である。
【図６】本発明の様々な実施形態による、低密度パリティ検査復号化中の内部レベル誤訂正ハンドリング処理のための方法を示す流れ図である。
【図７】本発明の様々な実施形態による、低密度パリティ検査復号化中の外部レベル誤訂正ハンドリング処理のための方法を示す流れ図である。
【図８】本発明の幾つかの実施形態による、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備える記憶システムを示す図である。
【図９】本発明の幾つかの実施形態による、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備える無線通信システムを示す図である。
【発明を実施するための形態】
【０００８】
誤訂正ハンドリング処理を伴う低密度パリティ検査（ＬＤＰＣ）復号化器が、パリティ検査Ｈ０行列に追加された特別階層Ｓを用いて、復号化器が正しくない符号語に収束している誤訂正を検出して解決することを援助する。図１に示すように、生成行列Ｇ１００が、誤訂正サポート処理を伴う低密度パリティ検査符号化器内で適用され、トランケートされた部分行列Ｈ０１０４及び特別階層Ｓ１０６を含むパリティ検査Ｈ行列１０２が生成される。この特別階層は、符号語又は符号化されたデータを復号化するために、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器内で用いられる。パリティ検査Ｈ行列１０２は、本明細書では、合成行列とも呼ばれる。部分行列Ｈ０１０４は、ユーザーデータビット及びパリティビットに対応し、低密度パリティ検査復号化器における変数ノードと検査ノードとの間の接続を規定する。部分行列Ｈ０１０４は、低密度パリティ検査アルゴリズムを符号語に適用するために低密度パリティ検査復号化器によって用いられる標準的な低密度パリティ検査行列又はＨ行列とすることができるが、これに限定されるものではない。部分行列Ｈ０１０４は、当該技術分野において知られている任意のＨ行列又はそれ以外のものとすることができ、当業者であれば、２進及び非２進、準巡回等の、本発明の種々の実施形態に関して用いることができる様々なＨ行列を認識するであろう。復号化器側では、特別階層Ｓ１０６は、より多くのパリティビットを追加した部分行列Ｈ０１０４と同じ構造を有するが、これに限定されるものではない。幾つかの実施形態では、特別階層Ｓ１０６は、部分行列Ｈ０１０４よりも高密度である。符号化器側では、これは、生成行列Ｇ１００のサイズの増大をもたらす。
【０００９】
特別階層Ｓ１０６は、データが収束したときに用いられる。これは、幾つかの実施形態では、シンドロームが０であるとき、すなわち、部分行列Ｈ０に基づく低密度パリティ検査復号化の硬判定結果Ｖに部分行列Ｈ０を乗算することによって得られたベクトルが０に等しいときに識別される。（シンドローム＝部分行列Ｈ０×硬判定又は訂正された符号語Ｖ。）特別階層Ｓ１０６は、幾つかの実施形態では、２つの目的で用いられる。本明細書では内部レベルと呼ばれる、これらの２つの目的のうちの１つでは、部分行列Ｈ０１０４のみを用いて計算されたシンドロームが０であるが、巡回冗長検査（ＣＲＣ）（これに限定されない）等の他のテストは、データが誤訂正されており、硬判定がエラーを含むことを示しているときに、特別階層Ｓ１０６は、完全Ｈ行列（full H matrix）１０２に基づく余剰低密度パリティ検査（extra lowdensity parity check）復号化を実行するのに用いられる。本明細書では外部レベルと呼ばれる、２つの目的のうちのもう１つでは、特別階層Ｓ１０６は、低密度パリティ検査符号化器においてハッシュ値を計算し、低密度パリティ検査復号化器においてそのハッシュ値を検査し、そして、そのハッシュ値に基づく小さな符号語を用いて、誤訂正された符号語の訂正を試みるのにも用いられる。ハッシュ値は、誤訂正された符号語に追加されてこの誤訂正された符号語を訂正することができる事前に計算された小さな符号語又は部分符号語を識別するのに用いられる。他の実施形態では、特別階層Ｓ１０６は、これらの目的のうちの一方にしか用いられない。
【００１０】
誤訂正ハンドリング処理の内部レベルでは、低密度パリティ検査復号化は、最初に部分行列Ｈ０１０４を用いて実行され、特別階層Ｓ１０６は無効又は未使用にされる。シンドロームが、データが収束するとともに復号化が完了したものと低密度パリティ検査復号化器が判断したことを意味するゼロであるが、別のテストが、データが誤訂正されたことを示している場合、低密度パリティ検査復号化は、部分行列Ｈ０１０４及び特別階層Ｓ１０６の双方を含む完全Ｈ行列１０２を用いて繰り返される。特に、完全Ｈ行列１０２のフルシンドロームは、シンドロームとハッシュとを連結したものである。幾つかの実施形態では、誤訂正は、低密度パリティ検査復号化がシンドローム＝０で完了した後にハッシュ値を計算することによって検出され、そのハッシュ値が０でない場合、誤訂正が発生している。幾つかの実施形態では、誤訂正検出は、ハッシュ値が０である場合には、復号化されているデータ内のユーザービット又はコントローラービットに組み込まれた外部の巡回冗長検査ビットを用いて巡回冗長検査テストを実行することも含む。本明細書に提供された開示内容に基づくと、当業者であれば、本発明の種々の実施形態に関して用いることができる他の誤訂正検出技法を認識するであろう。完全Ｈ行列１０２を用いて低密度パリティ検査復号化を繰り返した後、誤訂正が、ハッシュ、外部の巡回冗長検査、又は他のデータ完全性のテストを介して依然として示されている場合、制御は、幾つかの実施形態では、外部レベルの誤訂正ハンドリング処理に渡される。
【００１１】
外部レベルの誤訂正ハンドリング処理では、所与のハッシュ値について、小さな符号語が、ハッシュ値に基づいてルックアップテーブルから取り出されるか又は別の方法で得られる。各ハッシュ値は、０個、１個、又は複数個の小さな符号語を取り出す場合がある。１つ又は複数の符号語は、０のハッシュ値を用いても取り出される場合があり、これは、誤訂正が、０のハッシュ値にもかかわらず、外部の巡回冗長検査又は他のデータ完全性のテストを用いて検出されるときに起こり得る。これらの小さな符号語は、部分行列Ｈ０１０４について事前に計算される。取り出された各小さな符号語は、低密度パリティ検査復号化によって生成される誤訂正された符号語に適用されて、その適用が、誤訂正された符号語を訂正するか否かが判断される。幾つかの実施形態では、各小さな符号語は、排他的ＯＲ（ＸＯＲ）演算を用いて、誤訂正された符号語と結合される。その結果の符号語のシンドロームが０である場合、その結果の符号語は、訂正された符号語である。線形性を満たすハッシュを用いることによって、ハッシュ値及び小さな符号語は、誤訂正されている復号化された符号語を編集及び訂正するのに用いることができる。線形性は、任意の２進ベクトルＡ及びＢについて、ＨＡＳＨ（Ａ  ＸＯＲ  Ｂ）＝ＨＡＳＨ（Ａ）  ＸＯＲ  ＨＡＳＨ（Ｂ）を条件として規定する。特に、復号化された符号語Ａについて、小さな符号語Ｂが同じハッシュ値を用いて発見され、符号語Ａ  ＸＯＲ  符号語Ｂの結果がＨＡＳＨ＝０となる場合、これは、この小さな符号語を誤訂正された符号語に適用した結果、完全Ｈ行列１０２の場合の符号語が得られ、訂正前のような、部分行列Ｈ０１０４のみの場合の符号語は得られないことを意味する。なぜならば、ＨＡＳＨ（Ａ）＝ＨＡＳＨ（Ｂ）である場合、ＨＡＳＨ（Ａ）  ＸＯＲ  ＨＡＳＨ（Ｂ）＝０であるからである。ハッシュ値について線形性を有しない実施形態では、訂正された符号語について、あらゆる小さな符号語がテストされ、巡回冗長検査が再計算される。外部レベルの誤訂正ハンドリング処理は、誤訂正が、その重みが低密度パリティ検査符号の最小距離に近い低重み符号語によって引き起こされるという仮定と、そのような低重み符号語のリストが、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器に利用可能であり、管理可能なサイズを有するという仮定とに基づいている。
【００１２】
再度、小さな符号語が、部分行列Ｈ０１０４について事前に計算される。部分行列Ｈ０１０４を設計時に生成するとき、小さな符号語も、それらのハッシュ値とともに生成される。これらのハッシュ値及び小さな符号語の対は、ルックアップテーブルに記憶されるか又は別の方法で低密度パリティ検査復号化器に利用可能にされる。幾つかの実施形態では、低密度パリティ検査復号化中に取り出し及び使用に利用可能にされる小さな符号語の設計時の選択は、低密度パリティ検査復号化器の広範囲にわたる設計シミュレーション中に誤訂正を引き起こす小さな符号語を識別することに少なくとも部分的に基づいている。これらの小さな符号語は、低密度パリティ検査復号化器によってアクセス可能なメモリ内のルックアップテーブル（これに限定されない）を含む任意の適した方法で低密度パリティ検査復号化器に利用可能にすることができる。本明細書に提供された開示内容に基づくと、当業者であれば、小さな符号語及びハッシュの対を本発明の種々の実施形態に関して用いることができる低密度パリティ検査復号化器に利用可能にすることができる他の方法を認識するであろう。
【００１３】
準巡回パリティ検査行列を用いる幾つかの実施形態では、符号語は、巡回同値語（cyclically equivalent words）のクラスに分割される。特別階層Ｓが同じ巡回構造を有し、その高さが巡回（circulant）のサイズを分割する一実施形態、換言すれば、ハッシュビット長が巡回サイズを分割する一実施形態では、ルックアップテーブルは、同値符号語のクラスごとに１つのハッシュ値しか含まず、ハッシュ及び小さな符号語の対のサイズが大幅に削減される。非２進低密度パリティ検査準巡回行列を用いる実施形態では、符号語のガロア体多重性（Galois filed multiplicity）を考慮に入れて、記憶される対の数を同様にして削減することができる。符号語が変換される、準巡回又はガロア体の同値（equivalence）を用いる実施形態では、ハッシュ値は同値変換される。したがって、同値符号語の場合、ハッシュ値は、再計算されるのではなく、同じクラスからの符号語について既に計算された既知のハッシュ値の単純な準巡回変換及び／又はガロア体乗算によって得られる。これは、記憶される対の数を大幅に削減することができる。記憶される対の一意性を保持するために、幾つかの実施形態では、同じクラスからの全ての同値符号語の中で最小のハッシュ値が、ルックアップテーブルにおいて同値のクラス全体の代表として用いられる。
【００１４】
ハッシュ値は、特別階層Ｓ１０６に基づいて計算され、復号化されるデータに余剰パリティビットとして含まれる。幾つかの実施形態では、ハッシュ値は、シンドロームと同じ方法で低密度パリティ検査復号化器において計算される。シンドロームは、特別階層Ｓ１０６を除いた部分行列Ｈ０１０４に基づいて計算され、ハッシュ値は、部分行列Ｈ０１０４を除いた特別階層Ｓ１０６に基づいて計算される。したがって、ハッシュは、特別階層Ｓ１０６の硬判定結果に特別階層Ｓを乗算したものとして計算される。（ハッシュ＝特別階層Ｓ×特別階層Ｓの硬判定又は訂正された符号語。）低密度パリティ検査符号化は、完全Ｈ行列１０２に対応する生成行列Ｇ１００に基づいて実行される。したがって、ハッシュ値は、特別階層Ｓ１０６に関連付けられた余剰パリティビットに対応する。他の幾つかの実施形態では、特別階層Ｓ１０６を用いてパリティビットの数を増加させるのではなく、符号化器から生成されて復号化器に送信される通常のチャネル巡回冗長検査データの量は削減される。
【００１５】
事前に選択された特別階層Ｓ１０６が与えられると、ハッシュ値Ｓ＊Ｃが、生成される小さな符号語Ｃごとに計算される。誤訂正は、通常、小さな符号語、又は全体的な符号語の一部分（section）に起因して生じるので、復号化における誤訂正によって、正しい符号語Ｄは生成されず、或る小さな符号語ＣについてＤ  ＸＯＲ  Ｃに等しい誤訂正された符号語Ｅが生成される。ハッシュ値を用いてルックアップテーブルから小さな符号語Ｃを取り出し、訂正Ｅ  ＸＯＲ  Ｃ＝Ｄ  ＸＯＲ  Ｃ  ＸＯＲ  Ｃ＝Ｄを適用することによって、正しい符号語Ｄが得られる。
【００１６】
内部レベル及び外部レベルの誤訂正ハンドリング処理が実行された後、外部レベルの誤訂正ハンドリング処理からの訂正された符号語に対して、外部の巡回冗長検査テスト（これに限定されない）等の追加のテストを実行することができ、訂正された符号語が依然として正しくない場合、追加の訂正技法を行使することができる。
【００１７】
図２〜図４を参照すると、本発明の様々な実施形態によるデータ処理システムが示されている。本発明の１つ又は複数の実施形態による、符号化システムと、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備える復号化システムとを有するデータ処理システムが、図２に示されている。このデータ処理システムは、ユーザーデータビット２０２を処理し、それらのユーザーデータビットを記憶装置２０８に記憶するか又は送信チャネル２０８を通過させ、エラーを導入することなくユーザーデータビット２１４を取り出すのに用いられる。記憶又は送信されるユーザーデータ２０２は、誤訂正サポート処理を伴う低密度パリティ検査符号化器を備えた符号化システム２０４によって受信される。誤訂正サポート処理を伴う低密度パリティ検査符号化器を備えた符号化システム２０４は、パリティ検査Ｈ行列の特別階層Ｓ用のハッシュ値を計算することを含めて、生成Ｇ行列に基づき低密度パリティ検査符号化器においてユーザーデータ２０２を符号化する。誤訂正サポート処理を伴う低密度パリティ検査符号化器を備えた符号化システム２０４は、ハッシュ値が余剰パリティビットとして含まれる符号化されたデータ２０６を生成する。符号化されたデータ２０６は、磁気ハードドライブ又は無線電波信号（これらに限定されない）等の記憶装置／送信チャネル２０８に記憶又は送信される。符号化されたデータ２１０は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備えた復号化システム２１２によって記憶装置／送信チャネル２０８から取り出され、復号化される。誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備えた復号化システム２１２は、低密度パリティ検査復号化アルゴリズムを、取り出された符号化されているデータ２１０に適用する。データが収束し、シンドロームが０であるが、他のテストが誤訂正を示す場合、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備えた復号化システム２１２は、内部レベルの誤訂正ハンドリング処理及び外部レベルの誤訂正ハンドリング処理の一方又は双方を適用して、復号化されたユーザーデータ２１４を生成する。
【００１８】
図３を参照すると、本発明の１つ又は複数の実施形態による、誤訂正サポート処理を伴う低密度パリティ検査符号化器を備えた符号化システム３０４が示されている。この符号化システムは、図２の誤訂正サポート処理を伴う低密度パリティ検査符号化器を備えた符号化システム２０４の代わりに幾つかの実施形態における使用に適している。ユーザーデータ３０２は、ユーザーデータ３０２用の巡回冗長検査ビット３１８を生成するチャネル巡回冗長検査符号化器３１６によって処理される。巡回冗長検査ビット３１８は、マルチプレクサー３２０によって又は他の任意の適した方法でユーザーデータ３０２に追加されて、チャネル巡回冗長検査ビットを有するユーザーデータ３２２が生成される。チャネル巡回冗長検査ビットを有するユーザーデータ３２２は、幾つかの実施形態では、エラーが削減されるように、チャネル巡回冗長検査ビットを有するユーザーデータ３２２を記憶又は送信用に準備するパターン制約符号化器３２４によって符号化される。パターン制約符号化器３２４は、最大遷移ラン（ＭＴＲ）、ランレングス制限（ＲＬＬ）、又は他の制約等のパターン制約（これに限定されない）を適用することができる。本明細書に提供された開示内容に基づくと、当業者であれば、本発明の種々の実施形態に関して用いることができる様々なパターン制約符号化器を認識するであろう。
【００１９】
パターン制約符号化器３２４からの符号化されたユーザービット３２６は、誤訂正サポート処理を伴う低密度パリティ検査符号化器（encoder）３３０において符号化される。誤訂正サポート処理を伴う低密度パリティ検査符号化器３３０は、部分行列Ｈ０及び特別階層Ｓを有するＨ行列に対応する生成行列Ｇに基づいて、低密度パリティ検査符号化アルゴリズムを適用する。この適用には、生成行列Ｇ用のハッシュ値を計算することと、特別階層Ｓ用の余剰パリティビットとしてそれらのハッシュ値を含めることとが含まれる。幾つかの実施形態では、ハッシュ値は、誤訂正サポート処理を伴う低密度パリティ検査符号化器３３０において、巡回冗長検査アルゴリズムを用いて計算される。誤訂正サポート処理を伴う低密度パリティ検査符号化器３３０は、データフィールド３３２及びパリティフィールド３３４をパリティ挿入回路３３８に提供する。パリティ挿入回路３３８は、生成行列Ｇに従って、パリティフィールド３３４からのパリティビットをデータフィールド３３２からのデータビット内に挿入し、符号化されたデータ３０６を生成する。
【００２０】
パターン制約符号化器３２４におけるパターン制約符号化の後にハッシュ値を計算することによって、符号化されたデータ３０６は、パターン制約に違反する場合がある。しかしながら、小さな符号語を取り出して、誤訂正された符号語を訂正するのに用いることができるように、ハッシュは、外部レベルの誤訂正ハンドリング処理において用いられる線形性ハッシュを復元する。したがって、ハッシュ値は、パターン制約符号化を受けない、２４ビット又は３２ビットのハッシュビット（これらに限定されない）等の少数のビットを含むことができるが、これは、低密度パリティ検査復号化器があらゆる小さな符号語をテストして誤訂正された符号語を訂正する必要があるとは限らないことを含む、線形性ハッシュの利点を提供する。パターン制約符号化の前にユーザーデータに余剰の３２ビットを埋め込むことによってユーザービットを拡張するＣＲＣ−３２アルゴリズム等の通常の巡回冗長検査が実行される場合、これらの追加のビットがパターン制約符号化器３２４を通過するので、線形性は失われる。ハッシュ値が線形性を保持するとき、編集された語の巡回冗長検査値の、多大なコストを要する再計算を伴うことなく、符号語をそのハッシュ又は巡回冗長検査の値にのみ基づいて編集することができる。
【００２１】
図４を参照すると、本発明の１つ又は複数の実施形態による、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備えた復号化システム４１２が示されている。復号化システム４１２は、符号化されたアナログデータ４１０を受信するアナログフロントエンド回路４４０を備える。アナログ信号は、記憶デバイス又は伝送媒体から取り出されるときの符号化されたデータ３０６に対応する。アナログフロントエンド回路４４０は、符号化されたアナログデータ４１０を処理し、処理されたアナログ信号をアナログ／デジタル変換器回路４４２に提供する。アナログフロントエンド回路４４０には、限定ではないが、当該技術分野において知られているようなアナログフィルター及び増幅器回路が含まれ得る。本明細書において提供される開示に基づくと、当業者であれば、アナログフロントエンド回路４４０の一部として含めることができる種々の回路部を認識するであろう。幾つかの実施形態では、符号化されたアナログデータ４１０は記憶媒体（図示せず）に関連して配置される読取り／書込みヘッドアセンブリ（図示せず）から取り出される。他の実施形態では、符号化されたアナログデータ４１０は伝送媒体（図示せず）から信号を受信するように動作可能な受信機回路（図示せず）から取り出される。伝送媒体は有線又は無線とすることができる。本明細書において提供される開示に基づくと、当業者であれば、符号化されたアナログデータ４１０を取り出すことができる種々のソースを認識するであろう。
【００２２】
アナログ／デジタル変換器回路４４２は処理されたアナログ信号を対応する一連のデジタルサンプルに変換する。アナログ／デジタル変換器回路４４２は、アナログ入力信号に対応するデジタルサンプルを生成することが可能な当該技術分野において既知の任意の回路とすることができる。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に関連して用いることができる種々のアナログ／デジタル変換器回路を認識するであろう。デジタルサンプルが等化器回路４４４に与えられる。等化器回路４４４はデジタルサンプル３１２に等化アルゴリズムを適用して、等化出力を生成する。本発明の幾つかの実施形態では、等化器回路４４４は当該技術分野において既知のデジタル有限インパルス応答フィルター回路である。幾つかの場合、等化器４４４は、データ検出器回路４４６が処理に利用可能になるまで１つ又は複数の符号語を保持するのに十分かつデータ検出器回路４４６による複数回の処理のためのメモリを備える。等化出力３１６は、例えばソリッドステート記憶システム内の記憶デバイスから直接受信できることを可能とすることができる。そのような場合、アナログフロントエンド回路３０２、アナログ／デジタル変換器回路３１０、及び等化器回路３１４は、データがデジタルデータ入力として受信される場合に除去することができる。
【００２３】
データ検出器回路４４６は、受信した符号語又はデータセットにデータ検出アルゴリズムを適用するように動作可能であり、幾つかの場合、データ検出器回路４４６は２つ以上の符号語を並列に処理することができる。本発明の幾つかの実施形態では、データ検出器回路４４６は当該技術分野において知られているようなビタビアルゴリズムデータ検出器回路である。本発明の他の実施形態では、データ検出器回路４４６は当該技術分野において知られているような最大事後データ検出器回路である。一般的なフレーズ「ビタビデータ検出アルゴリズム」又は「ビタビアルゴリズムデータ検出器回路」は、任意のビタビ検出アルゴリズム若しくはビタビアルゴリズム検出器回路又はそれらの変形形態を意味するように最も広い意味で用いられることに留意されたい。それらの変形形態には、双方向ビタビ検出アルゴリズム又は双方向ビタビアルゴリズム検出器回路が含まれるが、これらに限定されるものではない。また、一般的なフレーズ「最大事後データ検出アルゴリズム」又は「最大事後データ検出器回路」は、任意の最大事後検出アルゴリズム若しくは最大事後検出器回路又はそれらの変形形態を意味するように最も広い意味で用いられる。それらの変形形態には、単純化された最大事後データ検出アルゴリズム及び最大対数最大事後データ検出アルゴリズム、又は対応する検出器回路が含まれるが、これらに限定されるものではない。本明細書において提供される開示に基づくと、当業者であれば、本発明の様々な実施形態に関連して用いることができる種々のデータ検出器回路を認識するであろう。データ検出器回路４４６は、等化器回路４４４又は中央メモリ回路４５０からのデータセットの入手可能性に基づいて始動される。
【００２４】
完了すると、データ検出器回路４４６は検出器出力を与える。検出器出力は軟データを含む。本明細書において用いられるとき、フレーズ「軟データ」は、信頼度データを意味するように最も広い意味で用いられ、この信頼度データの各インスタンスは、対応するビット位置又はビット位置群が正しく検出されている尤度を示す。本発明の幾つかの実施形態では、軟データ又は信頼度データは当該技術分野において知られているような対数尤度比データである。検出された出力はローカルインターリーバー回路４４８に与えられる。ローカルインターリーバー回路４４８は、検出された出力として含まれるデータセットの副部分（sub-portions）（すなわちローカルチャンク）をシャッフルするように動作可能であり、インターリーブされた符号語を与え、このインターリーブされた符号語は中央メモリ回路４５０に記憶される。ローカルインターリーバー回路４４８は、データセットをシャッフルして再配置されたデータセットを得ることが可能な当該技術分野において知られている任意の回路とすることができる。
【００２５】
誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４が利用可能になると、前に記憶されたインターリーブされた符号語が、記憶された符号語として中央メモリ回路４５０からアクセスされ。グローバルインターリーバー／デインターリーバー回路４５２によって全体的にインターリーブされる。グローバルインターリーバー／デインターリーバー回路４５２は、符号語を全体的に再配列することが可能な、当該技術分野において既知の任意の回路とすることができる。グローバルインターリーバー／デインターリーバー回路４５２は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４に復号化器入力を提供する。
【００２６】
誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４は、低密度パリティ検査復号化アルゴリズムを復号化器入力に適用して、復号化された出力４６０を生成する。データが、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４において収束して、０のシンドロームを生成する場合、１つ又は複数の誤訂正テストが、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４において結果の符号語に対して実行され、その符号語が誤訂正されたか否かを判断する。誤訂正が検出された場合、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４は、復号化された出力４６０が正しいものとなるように、内部レベル及び外部レベルの誤訂正ハンドリング処理のうちの１つ又は複数を実行する。
【００２７】
内部レベルの誤訂正ハンドリング処理では、特別階層Ｓ４６２が用いられて、完全Ｈ行列１０２に基づく余剰低密度パリティ検査復号化が実行される。換言すれば、低密度パリティ検査復号化アルゴリズムが、部分行列Ｈ０だけでなく完全Ｈ行列１０２に対して実行され、そのため、復号化された出力４６０は、完全Ｈ行列１０２に基づく符号語となる。
【００２８】
外部レベルの誤訂正ハンドリング処理では、特別階層Ｓに基づいて計算されたハッシュ値が用いられて、主要な低密度パリティ検査復号化からの符号語と結合される対応する小さな符号語が検索される。したがって、復号化された出力４６０内の符号語は、小さな符号語のルックアップテーブル又はリスト４６４からの小さな符号語と結合される。復号化された出力４６０内の符号語又は訂正された符号語は、硬判定キュー４６６に記憶される。特に、特別階層Ｓ４６２及び小さな符号語のリスト４６４は、内部レベル及び外部レベルの誤訂正ハンドリング処理の動作を示すために、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４の外側に示されているが、幾つかの実施形態では、双方のレベルの誤訂正ハンドリング処理は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４の内部で実行される。
【００２９】
硬判定キュー４６６内の符号語は、パリティ除去回路４６８によって処理されて、パリティビットが除去され、パターン制約復号化器４７０において復号化されるデータビットを生成する。パターン制約復号化器４７０は、符号化システム３０４内のパターン制約符号化器３２４によって実行された符号化を反転する。チャネル巡回冗長検査４７２は、復号化された結果のビットに対して実行される。エラーが検出された場合、訂正が、巡回冗長検査訂正用の小さな符号語のリスト４７４を用いて、硬判定キュー４６６に記憶された符号語に対して行われる。他の実施形態では、チャネル巡回冗長検査４７２の代わりに他の外部のデータ検査及び訂正の技法を適用することができる。本明細書に提供された開示内容に基づくと、当業者であれば、本発明の種々の実施形態に関して用いることができる様々なデータ完全性検査及び訂正のアルゴリズムを認識するであろう。チャネル巡回冗長検査４７２が満たされると、復号化されたユーザーデータ４１４が、復号化システム４１２から出力される。
【００３０】
誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４によって適用されるようなデータ復号化アルゴリズムが収束せず、局所的な反復（誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４を通る反復）がそれ以上可能でない場合、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器４５４からの軟（soft）復号化器出力が、グローバルインターリーバー／デインターリーバー回路４５２を介して中央メモリ回路４５０に転送される。復号化された軟出力を中央メモリ回路４５０に記憶する前に、復号化された軟出力は全体的にデインターリーブされて、中央メモリ回路４５０に記憶される全体的にデインターリーブされた出力が生成される。全体的なデインターリーブによって、記憶された符号語に以前に適用された全体的なインターリーブは反転されて、復号化器入力が生成される。データ検出器回路４４６が利用可能になると、前に記憶されたデインターリーブされた出力が、中央メモリ回路４５０からアクセスされ、ローカルデインターリーバー回路４５６によって局所的にデインターリーブされる。ローカルデインターリーバー回路４５６は、ローカルインターリーバー回路４４８によって最初に実行されたシャフリングを反転するように軟復号化器出力を再配列する。デインターリーブされた結果の出力は、データ検出器回路４４６に提供される。このデータ検出器回路は、等化器回路４４４からの等化された出力として受信された対応するデータセットのその後の検出をガイドするのに用いられる。
【００３１】
図５を参照すると、本発明の幾つかの実施形態による誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器５００が示されている。誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器５００は、パリティ検査計算又はメッセージ生成技法のためのどの特定のアルゴリズムにも限定されない。誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器５００では、データビット又はシンボルは、復号化される際に変数ノードに記憶され、パリティ検査は、複数の検査ノードにおいて実行される。低密度パリティ検査符号が設計される際に、変数ノードと検査ノードとの間の接続（又はエッジ）が選択される。Ｈ行列内の非ゼロ要素は、変数ノードと検査ノードとの間の接続を表し、列は変数ノードを表し、行は検査ノードを表し、非２進復号化器の場合、変数ノード列と検査ノード行との交点におけるガロア体からのランダムな非ゼロの要素は、その変数ノードとその検査ノードとの間の接続を示し、その変数ノードとその検査ノードとの間のメッセージのための並べ替え（permutation）を提供する。メッセージが、接続された変数ノードと検査ノードとの間を反復プロセスで渡され、変数ノードに現われるべき値についての信念（beliefs）が、接続された検査ノードに渡される。パリティ検査が、メッセージに基づいて検査ノードにおいて実行され、それらの結果が、接続された変数ノードに返され、必要に応じて信念が更新される。非２進低密度パリティ検査復号化器におけるメッセージは、多次元ベクトルであり、一般的にはプレーン尤度確率（plain-likelihoodprobability）ベクトル又は対数尤度比ベクトルのうちのいずれかである。
【００３２】
誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器５００への入力データ５０２は、メモリ５０４に記憶される。入力データ５０２は、変数ノード値確率を表す軟値を含む。メモリ５０４からの確率値５０６は、変数ノードプロセッサ５１０に提供され、この変数ノードプロセッサは、各ビット又は各シンボルの知覚値の確率値を含む、変数ノードから検査ノードへのメッセージ５２０を生成する。検査ノードプロセッサ５２２は、変数ノードから検査ノードへのメッセージ５２０を受信し、接続された変数ノードからのメッセージに基づいて、検査ノードごとのパリティ検査計算を実行する。また、検査ノードプロセッサ５２２は、検査ノードから変数ノードへのメッセージ５２４も生成し、変数ノードプロセッサ３１０が、接続された検査ノードからの、検査ノードから変数ノードへのメッセージ５２４に基づいて、変数ノードごとに知覚値を更新することを可能にする。
【００３３】
最小和（min-sum）ベースの低密度パリティ検査復号化器では、検査ノードプロセッサ５２２は、最も低い（すなわち、最小の）対数尤度比値を選択し、それらの値を、符号調整して、接続された変数ノードにフィードバックする。更新された変数ノード値は、変数ノードプロセッサ５１０若しくは検査ノードプロセッサ５２２のいずれか又は双方が、ローカル復号化の反復中にメモリ５０４において更新することもできる。変数ノードプロセッサ５１０からの確率値５１２も、硬判定出力５１６を生成する硬判定出力回路５１４に提供することができる。
【００３４】
低密度パリティ検査復号化器５００内のスケジューラ／誤訂正ハンドリング処理回路５３０は、検査ノードから変数ノードへのメッセージ生成及び変数ノードから検査ノードへのメッセージ生成、パリティ検査及び変数ノード更新の順序を制御すること、並びに変数ノードプロセッサ５１０及び検査ノードプロセッサ５２２に、最初に部分行列Ｈ０のみを用いて入力データ５０２を復号化させること（これらに限定されない）等の、低密度パリティ検査復号化器５００におけるＨ行列の処理を制御する。スケジューラ／誤訂正ハンドリング処理回路５３０は、誤訂正ハンドリング処理も実施する。
【００３５】
シンドローム／ハッシュ計算回路５３２は、パリティ検査行列Ｈ０の低密度パリティ検査復号化の硬判定結果Ｖに部分行列Ｈ０を乗算することによってシンドロームを計算し、特別階層Ｓの低密度パリティ検査復号化の硬判定結果に特別階層Ｓを乗算することによってハッシュ値を計算する。このように、ハッシュ値は、シンドロームと同じ方法で計算され、シンドロームは、特別階層Ｓ１０６を除く部分行列Ｈ０１０４に基づいて計算され、ハッシュ値は、部分行列Ｈ０１０４を除く特別階層Ｓ１０６に基づいて計算される。シンドローム／ハッシュ計算回路５３２は、独立した回路として実施することもできるし、シンドローム／ハッシュ計算回路を含む組み合わせ回路として実施することもできる。
【００３６】
部分行列Ｈ０のみを用いた入力データ５０２の最初の復号化の後、シンドローム／ハッシュ計算回路５３２によって計算されたシンドロームが０であり、データが収束したことを示す場合、シンドローム／ハッシュ計算回路５３２は、ハッシュを計算し、スケジューラ／誤訂正ハンドリング処理回路５３０は、ハッシュが０であるか否かを判断する。ハッシュがゼロでない場合、スケジューラ／誤訂正ハンドリング処理回路５３０は、内部レベルの誤訂正ハンドリング処理を実施して、変数ノードプロセッサ５１０及び検査ノードプロセッサ５２２に、Ｈ行列１０２全体を用いて入力データ５０２の復号化を繰り返させる。幾つかの実施形態では、ハッシュが、最初の復号化後にゼロである場合、巡回冗長検査回路５３６は、符号化器によってユーザービット内に組み込まれた外部の巡回冗長検査ビットに対して巡回冗長検査を実行し、巡回冗長検査が失敗した場合、誤訂正が識別され、スケジューラ／誤訂正ハンドリング処理回路５３０は、内部レベルの誤訂正ハンドリング処理を実施する。幾つかの実施形態では、対象シンボルフリッピング（targeted symbol flipping）（これに限定されない）等の他のエラー訂正技法が、誤訂正ハンドリング処理と組み合わされる。
【００３７】
入力データ５０２の復号化が、Ｈ行列１０２全体を用いて繰り返され、シンドロームが再び０となった後、誤訂正テストが、シンドローム／ハッシュ計算回路５３２によって計算されたハッシュ値に基づいて、また、幾つかの実施形態では巡回冗長検査に基づいて、スケジューラ／誤訂正ハンドリング処理回路５３０によって繰り返される。誤訂正が再び識別された場合、スケジューラ／誤訂正ハンドリング処理回路５３０は、ハッシュに関連付けられた小さな符号語を検索する内部レベルの誤訂正ハンドリング処理中にシンドローム／ハッシュ計算回路５３２によって計算されたハッシュを用いて、外部レベルの誤訂正ハンドリング処理を実施する。小さな符号語が発見された場合、この小さな符号語を誤訂正された符号語とＸＯＲ演算で結合することによって、この誤訂正された符号語が訂正され、訂正された符号語が生成される。
【００３８】
図６を参照すると、流れ図６００が、本発明の幾つかの実施形態による内部レベル誤訂正ハンドリング処理のための動作を示している。流れ図６００によると、データセクターが読み取られる（ブロック６０２）。幾つかの実施形態では、データセクターは、磁気記憶媒体に対して配置された読取り／書込みヘッドアセンブリによって読み取られる。他の実施形態では、データセクターは、伝送媒体から信号を受信するように動作可能な受信機回路から取り出される。データセクター用の軟入力が計算される（ブロック６０４）。幾つかの実施形態では、これは、ビタビ検出器又は最大事後データ検出器回路等のデータ検出器によって実行される。低密度パリティ検査復号化が、パリティ検査Ｈ行列内の特別階層が無効にされた状態で、データセクター軟入力に対して実行される（ブロック６０６）。結果のシンドロームが０であるか否かについての判断が行われる（ブロック６１０）。このシンドロームは、特別階層が無効にされた状態での低密度パリティ検査復号化の硬判定結果に部分行列Ｈ０を乗算することによって計算される。シンドロームが０である場合、結果のハッシュが０であるか否かについての判断が行われる（ブロック６１２）。ハッシュは、特別階層の硬判定結果に特別階層を乗算することによって計算される。ブロック６１２において、ハッシュが０であると判断された場合、幾つかの実施形態では、特別階層が無効にされた状態での低密度パリティ検査復号化によって生成された符号語は正しいとみなされ、その符号語の硬判定出力が用いられる（ブロック６２２）。ブロック６１２において、ハッシュが０でないと判断された場合、又はブロック６１０において、シンドロームが０でないと判断された場合、低密度パリティ検査復号化が、パリティ検査Ｈ行列内の特別階層が有効にされた状態で、データセクター軟入力に対して繰り返される（ブロック６１４）。結果のシンドロームが０であるか否かについての別の判断が行われる（ブロック６１６）。許容されたローカル及びグローバルの復号化反復回数の後に、ブロック６１６において、シンドロームが０でないと判断された場合、データは収束しておらず、事後処理訂正を実行することができる（ブロック６２４）。そのような事後処理訂正は、対象シンボルフリッピング等の任意のタイプのデータ訂正技法又はエラー回復技法を含むことができる。事後処理訂正が成功しない場合又は利用可能でない場合、復号化は失敗している。ブロック６１６において、シンドロームが０であると判断された場合、結果のハッシュが０であるか否かについての判断が行われる（ブロック６２０）。このハッシュが０である場合、復号化は成功したとみなされ、その符号語の硬判定出力が用いられる（ブロック６２２）。ハッシュが０でない場合、外部レベル誤訂正ハンドリング処理が実行される（ブロック６２６）。他の実施形態では、誤訂正は、ブロック６１２及び６２０において、巡回冗長検査及びハッシュ値（これらに限定されない）等の外部のテストに基づいて識別される。
【００３９】
図７を参照すると、流れ図７００が、本発明の幾つかの実施形態による外部レベル誤訂正ハンドリング処理のための動作を示している。流れ図７００によると、ハッシュ値が用いられて、同じハッシュ値を有する小さな符号語が探索される（ブロック７０２）。ブロック７０２は、部分行列Ｈ０の小さな符号語の事前に計算されたリストを、それらの小さな符号語の対応するハッシュ値とともに用いて実行される。この場合も、低密度パリティ検査復号化器において生成されるハッシュ値が、特別階層の硬判定結果に特別階層を乗算することによって計算される。この小さな符号語は、ルックアップテーブル内で探索される。このルックアップテーブルでは、小さな符号語が、パリティ検査行列Ｈの特別階層Ｓについて設計時に事前に計算されたそれらの小さな符号語の対応するハッシュ値と対になって記憶されている。一致するハッシュ値を有する小さな符号語が発見されたか否かについての判断が行われる（ブロック７０４）。発見されない場合、小さな符号語が、誤訂正された符号語を訂正するのに利用可能でないので、外部レベル誤訂正ハンドリング処理は失敗しており、事後処理訂正が実行される（ブロック７０６）。そのような事後処理訂正は、対象シンボルフリッピング等の任意のタイプのデータ訂正技法又はエラー回復技法を含むことができる。事後処理訂正が成功しない場合又は利用可能でない場合、復号化は失敗している。
【００４０】
ブロック７０４において、小さな符号語が、低密度パリティ検査復号化器において計算されたハッシュ値を用いて発見されたと判断された場合、この小さな符号語は、誤訂正された符号語に適用される（ブロック７０８）。幾つかの実施形態では、これは、この小さな符号語を誤訂正された符号語とＸＯＲ演算で結合することによって達成される。チャネル巡回冗長検査が再計算される（ブロック７１０）。チャネル巡回冗長検査が満たされているか否かについての判断が行われる（ブロック７１２）。満たされている場合、訂正された符号語が正しいとみなされ、この訂正された符号語の硬判定出力が用いられる（ブロック７１４）。チャネル巡回冗長検査が満たされていない場合、完全行列Ｈの小さな符号語のリストが全て試行されたか否かについての判断が行われる（ブロック７１６）。全て試行されている場合、小さな符号語が誤訂正された符号語を訂正するのに利用可能でないので、外部レベル誤訂正ハンドリング処理は失敗しており、事後処理訂正が実行される（ブロック７０６）。更なる小さな符号語が試行されずに残っている場合、別の小さな符号語が選択され、誤訂正された符号語に適用される（ブロック７２０）。チャネル巡回冗長検査が再計算され（ブロック７１０）、小さな符号語が、誤訂正された符号語の訂正を試行せずに残っている間、この動作は続く。ブロック７１６及び７２０は、完全パリティ検査行列Ｈの小さな符号語の事前に計算された圧縮リストを用いて実行される。
【００４１】
本明細書に開示された誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器は、どの特定の用途にも限定されず、本発明の実施形態からの利益を得る幾つかの用途例が、図８及び図９に提示されている。図８を参照すると、本発明の幾つかの実施形態による誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器の例示的な応用形態として、記憶システム８００が示されている。記憶システム８００は、本発明の幾つかの実施形態による誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を有する読取りチャネル回路８０２を備える。記憶システム８００は、例えば、ハードディスクドライブとすることができる。記憶システム８００は、前置増幅器８０４、インターフェースコントローラー８０６、ハードディスクコントローラー８１０、モーターコントローラー８１２、スピンドルモーター８１４、ディスクプラッター８１６、及び読取り／書込みヘッドアセンブリ８２０も備える。インターフェースコントローラー８０６はディスクプラッター８１６への／からのデータのアドレス指定及びタイミングを制御する。ディスクプラッター８１６上のデータは、アセンブリがディスクプラッター８１６上に適切に位置決めされているときに読取り／書込みヘッドアセンブリ８２０が検出することができる磁気信号群からなる。１つの実施形態では、ディスクプラッター８１６は、長手記録方式又は垂直記録方式のいずれかに従って記録される磁気信号を含む。
【００４２】
通常の読取り動作では、読取り／書込みヘッドアセンブリ８２０はモーターコントローラー８１２によって、ディスクプラッター８１６上の所望のデータトラックの上方に正確に位置決めされる。モーターコントローラー８１２は、ハードディスクコントローラー８１０の指示の下で読取り／書込みヘッドアセンブリ８２０をディスクプラッター８１６上の適切なデータトラックに移動させることによって、ディスクプラッター８１６に対して読取り／書込みヘッドアセンブリ８２０を位置決めし、かつスピンドルモーター８１４を駆動する。スピンドルモーター８１４は、決められたスピンレート（ＲＰＭ）でディスクプラッター８１６をスピンさせる。読取り／書込みヘッドアセンブリ８２０が適切なデータトラックに近接して位置決めされると、ディスクプラッター８１６がスピンドルモーター８１４によって回転するのに応じてディスクプラッター８１６上のデータを表す磁気信号が読取り／書込みヘッドアセンブリ８２０によって感知される。感知された磁気信号は、ディスクプラッター８１６上の磁気データを表す連続した微小アナログ信号として与えられる。この微小アナログ信号は、読取り／書込みヘッドアセンブリ８２０から前置増幅器８０４を介して読取りチャネル回路８０２に転送される。前置増幅器８０４は、ディスクプラッター８１６からアクセスされた微小アナログ信号を増幅するように動作可能である。そして、読取りチャネル回路８０２は、受信したアナログ信号を復号化及びデジタル化し、ディスクプラッター８１６に最初に書き込まれた情報を再生する。このデータは、読取りデータ８２２として受信回路に与えられる。受信情報の処理の一部として、読取りチャネル回路８０２は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を用いて、受信信号に対してデータ復号化プロセスを実行する。誤訂正ハンドリング処理を伴うそのような低密度パリティ検査復号化器は、図１〜図５に関して上記で開示された低密度パリティ検査復号化器と一致するように実施することができる。幾つかの場合、誤訂正ハンドリング処理を伴うデータ復号化は、図６及び図７に関連して上記で開示された流れ図と一致するように実行することができる。書込み動作は実質的に、先行する読取り動作の反対の動作であり、書込みデータ８２４が読取りチャネル回路８０２に与えられ、ディスクプラッター８１６に書き込まれる。
【００４３】
例えばＲＡＩＤ（安価なディスクの冗長アレイ又は独立ディスクの冗長アレイ）に基づく記憶システム等のより大型の記憶システムに、記憶システム８００を統合することができることに留意すべきである。このようなＲＡＩＤ記憶システムは、複数のディスクを論理ユニットとして結合し、冗長性を通じて安定性及び信頼性を増大させる。データは、種々のアルゴリズムに従って、ＲＡＩＤ記憶システムに含まれる複数のディスクにわたって拡散させることができ、ＲＡＩＤ記憶システムが単一のディスクであるかのようにオペレーティングシステムがアクセスすることができる。例えば、データはＲＡＩＤ記憶システム内の複数のディスクにミラーリングすることもできるし、複数の技法において複数のディスクにわたってスライスし分散させることもできる。ＲＡＩＤ記憶システム内の少数のディスクが故障するか又は利用不可能になる場合、誤り訂正技法を用いて、ＲＡＩＤ記憶システム内の他のディスクからのデータの残りの部分に基づいて、欠落データを再生することができる。ＲＡＩＤ記憶システム内のディスクは、限定ではないが、記憶システム８００等の個別の記憶システムとすることができ、互いに近接して配置することもできるし、セキュリティを増大させるために、より広範に分散させることもできる。書込み動作において、書込みデータがコントローラーに提供され、コントローラーは、例えば書込みデータのミラーリング又はストライピングによって、ディスクにわたって書込みデータを記憶する。読取り動作において、コントローラーはディスクからデータを検索する。次に、コントローラーは、ＲＡＩＤ記憶システムが単一のディスクであるかのように結果の読取りデータを生成する。
【００４４】
図９を参照すると、本発明の幾つかの実施形態による、送信機９０２と、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を備えた受信機９０４とを備える無線通信システム９００又はデータ伝送デバイスが示されている。通信システム９００は、当該技術分野において知られているような転送媒体９０６を介して、符号化された情報を送信するように動作可能な送信機９０２を備える。符号化されたデータは、受信機９０４によって転送媒体９０６から受信される。受信機９０４は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器を組み込んでいる。そのような誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器は、図１〜図５に関する上記開示内容と一致するように実施することができる。場合によっては、誤訂正ハンドリング処理を伴うデータ復号化は、図６及び図７に関して上記で開示した流れ図と一致するように実行することができる。
【００４５】
低密度パリティ検査技術は、実質的に任意のチャネルによる情報の伝送又は実質的に任意の媒体上での情報の記憶に応用可能である。伝送の応用形態には、光ファイバー、無線周波数チャネル、有線又は無線のローカルエリアネットワーク、デジタル加入者線技術、無線セルラー、銅ファイバー又は光ファイバー等の任意の媒体によるイーサネット（登録商標）、ケーブルテレビ等のケーブルチャネル、及び地球衛星間通信が含まれるが、これらに限定されない。記憶の応用形態には、ハードディスクドライブ、コンパクトディスク、デジタルビデオディスク、磁気テープ、並びにダイナミックランダムメモリ、ＮＡＮＤ（negated-AND）フラッシュ、ＮＯＲ（negated-OR）フラッシュ、他の不揮発性メモリ及びソリッドステートドライブ等のメモリデバイスが含まれるが、これらに限定されない。
【００４６】
上記の応用形態において論述した様々なブロックは、他の機能とともに集積回路に実装することができることに留意すべきである。そのような集積回路は、所与のブロック、システム若しくは回路の機能の全て、又はブロック、システム若しくは回路の機能のサブセットのみを含むことができる。また、ブロック、システム又は回路の要素を複数の集積回路にわたって実装することができる。そのような集積回路は、モノリシック集積回路、フリップチップ集積回路、マルチチップモジュール集積回路及び／又は混合信号集積回路を含むが、これらに限定されるものではない、当該技術分野において知られている任意のタイプの集積回路とすることができる。本明細書において論述されたブロック、システム又は回路の様々な機能を、ソフトウェア又はファームウェアのいずれかで実装することができることにも留意すべきである。そのような幾つかの場合には、システム全体、ブロック全体又は回路全体を、そのソフトウェア等価物又はファームウェア等価物を用いて実装することができる。他の場合には、所与のシステム、ブロック又は回路の一部分をソフトウェア又はファームウェアで実装することもできる一方、他の部分はハードウェアで実装される。
【００４７】
結論として、本発明は、誤訂正ハンドリング処理を伴う低密度パリティ検査復号化器のための新規なシステム及び方法を提供する。本発明の１つ又は複数の実施形態の詳細な説明が上記で与えられたが、本発明の趣旨から逸脱することなく、様々な代替形態、修正形態及び均等物が当業者には明らかであろう。したがって、上記の説明は本発明の範囲を限定するものとして解釈されるべきではなく、本発明の範囲は添付の特許請求の範囲によって規定される。
【図１】
2014116927.tif 000003
【図２】
2014116927.tif 000004
【図３】
2014116927.tif 000005
【図４】
2014116927.tif 000006
【図５】
2014116927.tif 000007
【図６】
2014116927.tif 000008
【図７】
2014116927.tif 000009
【図８】
2014116927.tif 000010
【図９】
2014116927.tif 000011