(57)【特許請求の範囲】
【請求項１】
グラフベースの符号を使用して符号化された符号化されたデータを復号する方法であって、
（ａ）候補の復号された符号語を生成するために、前記符号化されたデータを復号することと、
（ｂ）前記候補の復号された符号語が復号された正しい符号語ではない場合に、前記復号された正しい符号語を生成することを試みるためにトラッピング・セット（ＴＳ）−ＲＯＭリスト復号方法を実行することであって、
前記候補の復号された符号語は、少なくとも１つの満足されないチェックノードを有し、満足されないチェックノードは、パリティ検査に合格しないチェックノードであり、
前記ＴＳ−ＲＯＭリスト復号方法は、ＲＯＭメモリ内に格納された１つまたは複数のＴＳプロファイルにアクセスし、
第１の格納されたＴＳプロファイルは、少なくとも１つの満足されないチェック（ＵＳＣ）ノードの格納された情報および少なくとも１つの誤って満足されたチェック（ＭＳＣ）ノードの格納された情報を含み、ＭＳＣノードは、（ｉ）誤りのあるビットノード（ＥＢＮ）に関連し、（ｉｉ）前記パリティ検査を満足するチェックノードであり、
第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードおよび１つまたは複数のＭＳＣノードを有するトラッピング・セットに関連し、前記第２の格納されたＴＳプロファイルは、前記１つまたは複数のＵＳＣノードの格納された情報を含むが、前記１つまたは複数のＭＳＣノードに関する情報を含まない
実行することと
を含む方法。
【請求項２】
前記第１の格納されたＴＳプロファイルは、前記第２の格納されたＴＳプロファイルの前記トラッピング・セットより支配的であるトラッピング・セットに関連する、請求項１に記載の発明。
【請求項３】
前記ＴＳ−ＲＯＭリスト復号方法は、
（ｂ１）前記候補の復号された符号語内の前記少なくとも１つのＵＳＣノードに関連する１つまたは複数のＥＢＮを識別することと、
（ｂ２）（ｉ）前記候補の復号された符号語が１つまたは複数のＭＳＣノードを有し、（ｉｉ）前記ＲＯＭメモリが前記１つまたは複数のＭＳＣノードに関する情報を含む場合に、前記１つまたは複数のＭＳＣに関連する１つまたは複数のＥＢＮを識別することと、
（ｂ３）前記識別されたＥＢＮを変更することと、
（ｂ４）さらなる処理を実行することであって、
ステップ（ｂ２）が１つまたは複数のＥＢＮを識別する場合に、前記さらなる処理は、前記変更された候補の復号された符号語に対して症候群チェックを実行することを含み、
ステップ（ｂ２）が１つまたは複数のＥＢＮを識別しない場合に、前記さらなる処理は、変更された符号化されたデータを復号することを含む
実行することと
を含む、請求項１に記載の発明。
【請求項４】
ＴＳプロファイル内の満足されないチェックノードごとに、前記ＴＳプロファイルは、
前記満足されないチェックノードが配置される復号レイヤ（たとえば、ＬＡＹＥＲ）と、
前記復号レイヤ内の前記満足されないチェックノード（ＵＳＣ）のインデックス（たとえば、ＵＳＣ＿ＩＮＤＥＸ）と、
前記満足されないチェックノードに関連する１つまたは複数の誤りのあるビットノード（ＥＢＮ）の１つまたは複数のインデックス（たとえば、ＥＢＮ＿ＩＮＤＥＸ）と
を含み、ＴＳプロファイル内の誤って満足されたチェックノードごとに、前記ＴＳプロファイルは、
前記誤って満足されたチェックノードに関連する１つまたは複数の誤りのあるビットノードの位置情報（たとえば、ＢＬＯＣＫ＿ＣＯＬＵＭＮ、Ｂ＿ＩＮＤＥＸ）
を含む、請求項１に記載の発明。
【請求項５】
前記ＲＯＭメモリは、複数の格納されたＴＳプロファイルを含み、
前記複数の格納されたＴＳプロファイルの前記復号レイヤ、ＵＳＣインデックス、およびＥＢＮインデックスは、第１テーブル（たとえば、Ｐテーブル５１４）に格納され、
誤って満足されたチェックノードに関連する前記誤りのあるビットノードの前記位置情報は、第２テーブル（たとえば、ＥＩテーブル５１８）に格納される
請求項４に記載の発明。
【請求項６】
前記格納されたＴＳプロファイルは、前記第１テーブル内で、前記格納されたＴＳプロファイル内の満足されないチェックノードの個数に基づいてグループ化され、
同一の個数の満足されないチェックノードを有する格納されたＴＳプロファイルの各グループ内の前記格納されたＴＳプロファイルは、ＴＳプロファイル優位性によって順序付けられ、ＴＳプロファイルの優位性は、前記関連するトラッピング・セットがステップ（ａ）の前記復号のエラーフロア特性に対して有する影響に依存する
請求項５に記載の発明。
【請求項７】
複数の満足されないチェックノードを有するＴＳプロファイルごとに、
前記満足されないチェックノードは、前記ＴＳプロファイル内で復号レイヤによってグループ化され、
同一の復号レイヤを有する満足されないチェックノードのグループ内の前記満足されないチェックノードは、ＵＳＣインデックスによって配置される
請求項６に記載の発明。
【請求項８】
前記ＲＯＭメモリは、第３テーブル（たとえば、Ｅテーブル５１６）および第４テーブル（たとえば、Ｂテーブル５１２）をさらに含み、
前記第３テーブルは、一致するＴＳプロファイルの誤って満足されたチェックノードに関連する前記誤りのあるビットノードの前記位置情報の前記第２テーブル内のアドレス（たとえば、ＥＩＴＡＢＬＥ＿ＳＴＡＲＴ＿ＡＤＤＲＥＳＳ、ＥＩＴＡＢＬＥ＿ＥＮＤ＿ＡＤＤＲＥＳＳ）を識別し、
前記第１テーブル内と同一の個数の満足されないチェックノードを有する格納されたＴＳプロファイルのグループごとに、前記第４テーブルは、
（ｉ）格納されたＴＳプロファイルの前記グループの前記第１テーブル内の開始アドレス（たとえば、ＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴ）と、
（ｉｉ）誤って満足されたチェックノードに関連する位置情報を有する前記グループ内のＴＳプロファイルの個数（たとえば、ＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳ）と、
（ｉｉｉ）格納されたＴＳプロファイルの前記グループの前記第３テーブル内の開始アドレス（たとえば、ＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴ）と
を識別する、請求項５に記載の発明。
【請求項９】
前記グラフベースの符号は、Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ（ＬＤＰＣ）符号である、請求項１に記載の発明。
【請求項１０】
グラフベースの符号を使用して符号化された符号化されたデータを復号する装置であって、
（ａ）候補の復号された符号語を生成するために、前記符号化されたデータを復号する手段と、
（ｂ）前記候補の復号された符号語が復号された正しい符号語ではない場合に、前記復号された正しい符号語を生成することを試みるためにトラッピング・セット（ＴＳ）−ＲＯＭリスト復号方法を実行する手段であって、
前記候補の復号された符号語は、少なくとも１つの満足されないチェックノードを有し、満足されないチェックノードは、パリティ検査に合格しないチェックノードであり、
前記ＴＳ−ＲＯＭリスト復号方法は、ＲＯＭメモリ内に格納された１つまたは複数のＴＳプロファイルにアクセスし、
第１の格納されたＴＳプロファイルは、少なくとも１つの満足されないチェック（ＵＳＣ）ノードの格納された情報および少なくとも１つの誤って満足されたチェック（ＭＳＣ）ノードの格納された情報を含み、ＭＳＣノードは、（ｉ）誤りのあるビットノード（ＥＢＮ）に関連し、（ｉｉ）前記パリティ検査を満足するチェックノードであり、
第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードおよび１つまたは複数のＭＳＣノードを有するトラッピング・セットに関連し、前記第２の格納されたＴＳプロファイルは、前記１つまたは複数のＵＳＣノードの格納された情報を含むが、前記１つまたは複数のＭＳＣノードに関する情報を含まないことを含む装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル信号処理に関し、具体的には、ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ（ＬＤＰＣ）コーディングと称するデータ符号化方法に関する。
【背景技術】
【０００２】
通信は、送信器による、通信チャネルを介する受信器への情報の伝送である。実世界では、通信チャネルは、送信器から受信される情報のひずんだ版を受信器に出力する、雑音のある通信路である。ハード・ディスク（ＨＤ）ドライブは、送信器から情報を受け入れ、その情報を格納し、その後、おそらくは、その情報の多少ひずんだコピーを受信器に送る、１つのそのような雑音のある通信路である。
【先行技術文献】
【特許文献】
【０００３】
【特許文献１】米国仮出願第６１／０８９，２９７号
【特許文献２】米国特許出願第ＸＸ／ｘｘｘ，ｘｘｘ号（整理番号０８−０２４１）
【発明の概要】
【発明が解決しようとする課題】
【０００４】
ＨＤドライブなどの通信チャネルによって導入されるひずみは、チャネル・エラーすなわち、チャネル入力信号が０であった時に受信器がチャネル出力信号を１と解釈し、およびその逆を行う状況を引き起こすのに十分に大きい場合がある。チャネル・エラーは、スループットを下げ、したがって望ましくない。したがって、チャネル・エラーを検出し、かつ／または訂正するツールの継続する必要がある。ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ（ＬＤＰＣ）コーディングは、チャネル・エラーを検出し、訂正する１つの方法である。ＬＤＰＣ符号は、低信号対雑音比（ＳＮＲ）応用のための非常に低いビット誤り率（ＢＥＲ）を達成できる、既知のシャノン限界に近い符号の１つである。ＬＤＰＣ復号は、その並列性の可能性、低い実施複雑さ、短い復号待ち時間、ならびに高ＳＮＲでのより深刻でないエラーフロアによって区別される。ＬＤＰＣ符号は、事実上すべての次世代通信標準規格について検討されている。
【課題を解決するための手段】
【０００５】
ある種の実施形態で、本発明は、グラフベースの符号を使用して符号化された符号化されたデータを復号する方法を含む。この方法は、（ａ）候補の復号された符号語を生成するために、符号化されたデータを復号することと、（ｂ）候補の復号された符号語が復号された正しい符号語ではない場合に、復号された正しい符号語を生成することを試みるためにトラッピング・セット（ＴＳ）−ＲＯＭリスト復号方法を実行することとを含む。候補の復号された符号語は、少なくとも１つの満足されないチェックノードを有し、満足されないチェックノードは、パリティ検査に合格しないチェックノードである。ＴＳ−ＲＯＭリスト復号方法は、ＲＯＭメモリ内に格納された１つまたは複数のＴＳプロファイルにアクセスする。第１の格納されたＴＳプロファイルは、少なくとも１つの満足されないチェック（ＵＳＣ）ノードの格納された情報および少なくとも１つの誤って満足されたチェック（ＭＳＣ）ノードの格納された情報を含む。ＭＳＣノードは、（１）誤りのあるビットノード（ＥＢＮ）に関連し、（２）パリティ検査を満足するチェックノードである。第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードおよび１つまたは複数のＭＳＣノードを有するトラッピング・セットに関連し、第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードの格納された情報を含むが、１つまたは複数のＭＳＣノードに関する情報を含まない。
【０００６】
他の実施形態で、本発明は、グラフベースの符号を使用して符号化された符号化されたデータを復号する装置である。この装置は、（ａ）候補の復号された符号語を生成するために、符号化されたデータを復号するように適合された復号器と、（ｂ）候補の復号された符号語が復号された正しい符号語ではない場合に、復号された正しい符号語を生成することを試みるためにトラッピング・セット（ＴＳ）−ＲＯＭリスト復号方法を実行するように適合されたポストプロセッサとを含む。候補の復号された符号語は、少なくとも１つの満足されないチェックノードを有し、満足されないチェックノードは、パリティ検査に合格しないチェックノードである。ＴＳ−ＲＯＭリスト復号方法は、ＲＯＭメモリ内に格納された１つまたは複数のＴＳプロファイルにアクセスする。第１の格納されたＴＳプロファイルは、少なくとも１つの満足されないチェック（ＵＳＣ）ノードの格納された情報および少なくとも１つの誤って満足されたチェック（ＭＳＣ）ノードの格納された情報を含む。ＭＳＣノードは、（１）誤りのあるビットノード（ＥＢＮ）に関連し、（２）パリティ検査を満足するチェックノードである。第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードおよび１つまたは複数のＭＳＣノードを有するトラッピング・セットに関連し、第２の格納されたＴＳプロファイルは、１つまたは複数のＵＳＣノードの格納された情報を含むが、１つまたは複数のＭＳＣノードに関する情報を含まない。
【０００７】
本発明の他の態様、特徴、および利益は、次の詳細な説明、添付の特許請求の範囲、および添付図面からより十分に明らかになり、添付図面では、類似する符号が、類似するまたは同一の要素を識別する。
【図面の簡単な説明】
【０００８】
【図１】ＬＤＰＣコーディングを利用する通常のハード・ディスク（ＨＤ）ドライブ１００の一部を示すブロック図である。
【図２】図２（Ａ）は、ＬＤＰＣ  Ｈ行列２００を示す図であり、図２（Ｂ）は、Ｈ行列２００のタナー・グラフを示す図である。
【図３】復号器１１２によって使用される通常のＬＤＰＣ復号方法３００を示す流れ図である。
【図４】トラッピング・セットを識別し、これらのトラッピング・セットに関するさまざまな情報を記録するオフライン・トラッピング・セット（ＴＳ）シミュレーション・ツール４００を示すブロック図である。
【図５】本発明の一実施形態によるＬＤＰＣ復号システム５００を示すブロック図である。
【図６】図５のＲＯＭ  Ｐテーブル５１４の例示的レイアウトを示す図である。
【図７】図５のＢテーブル５１２の例示的レイアウトを示す図である。
【図８】図５のＥテーブル５１６の例示的レイアウトを示す図である。
【図９】図５のＥＩテーブル５１８の例示的レイアウトを示す図である。
【図１０】図５のＲＡＭ  Ｐテーブル５２２の例示的レイアウトを示す図である。
【図１１】図５のＲＡＭインデックス・テーブル５２４の例示的レイアウトを示す図である。
【図１２】図５のＬＤＰＣ復号システム５００によって使用される例示的プロセス１２００を示す流れ図である。
【図１３】図５のポストプロセッサ５０４によって実施される図１２の例示的なＴＳ−ＲＯＭリスト復号プロセス１２０６を示す流れ図である。
【図１４】図１３の例示的なＴＳ−ＲＯＭ検索プロセス１３１４を示す流れ図である。
【図１５】図１２の例示的なＴＳ−ＲＡＭリスト復号プロセス１２０８を示す流れ図である。
【図１６】図１２の例示的なＴＳ−ＲＡＭ更新プロセス１２１６を示す流れ図である。
【発明を実施するための形態】
【０００９】
図１は、ＬＤＰＣコーディングを利用する通常のハード・ディスク（ＨＤ）ドライブ１００の一部のブロック図である。ＨＤドライブ１００は、プラッタ１０２および読取りチャネル１０４を含む。読取りチャネル１０４は、ＬＤＰＣ符号器１０６、書込みプロセッサ１０８、読取りプロセッサ１１０、およびＬＤＰＣ復号器１１２を含む。経路１１４は、ＬＤＰＣ符号器１０６とＬＤＰＣ復号器１１２との間の雑音のある通信路である。
【００１０】
プラッタ１０２に書き込まれる情報語は、ＬＤＰＣ符号語を作るためにＬＤＰＣ符号器１０６によって処理される。ＬＤＰＣ符号語は、書込みプロセッサ１０８に送られ、書込みプロセッサ１０８は、複数のモジュール、たとえば、ＢＰＳＫ（二進移相変調）符号器、ディジタル−アナログ変換器などを含む。書込みプロセッサ１０８の出力１１６が、プラッタ１０２に書き込まれる。
【００１１】
プラッタ１０２から読み取られた信号１１８は、読取りプロセッサ１１０に送られ、読取りプロセッサ１１０は、複数のモジュール、たとえば、前置増幅器、連続時間フィルタ、固定インパルス応答フィルタ、検出器、アナログ−ディジタル変換器などを含む。読取りプロセッサ１１０は、対数尤度比（ＬＬＲ）値ＬｃｈをＬＤＰＣ復号器１１２に出力し、ＬＤＰＣ復号器１１２は、復号された情報語を出力する。さらに、ＬＤＰＣ復号器１１２は、ＥＬＤＰＣ値を読取りプロセッサ１１０に送り返す。ＥＬＤＰＣは、下の式６によって定義され、中間の計算されたＬＬＲ値を表す。読取りプロセッサ１１０は、ＥＬＤＰＣ値を使用して、その性能を調整し、これは、ターボ復号として知られるプロセスである。
【００１２】
ＬＤＰＣ符号化
ＬＤＰＣ符号器１０６は、情報語のビットに、ＬＤＰＣ符号によって指定される複数のパリティ・ビットを付加して、符号語を作る。情報語のビットは、可変ビットとして知られ、これらの可変ビットの個数は、Ｋと表される。あるＬＤＰＣ符号語内のビットの総数は、Ｎと表される。したがって、パリティ・ビットの個数は、Ｎ−Ｋによって与えられる。特定のＬＤＰＣ符号のレートは、Ｋ／Ｎすなわち、符号語長さに対する情報語長さの比である。したがって、９ビット符号語を作るために３ビット情報語のそれぞれに６つのパリティ・ビットを付加するＬＤＰＣ符号は、１／３のレートを有する。通常のＨＤドライブの場合に、情報語長さＫは、４０９６ビット（通常のＨＤドライブ・セクタの長さ）であり、パリティ・ビットの個数は、４５０６ビットの符号語長さおよび０．９のレートについて、約４１０ビットである。
【００１３】
ＬＤＰＣ符号語内の各パリティ・ビットは、その特定のＬＤＰＣ符号によって指定される特定の形でその符号語内の１つまたは複数の他の（可変またはパリティ）ビットに関連し、パリティ・ビットに割り当てられる値は、ＬＤＰＣ符号を満足するようにセットされる。通常のＬＤＰＣ符号は、関連するビットがパリティ検査制約を満足する、たとえば、関連するビットの合計が偶数である、すなわち、合計ｍｏｄｕｌｏ  ２＝０であることを指定する。
【００１４】
ＬＤＰＣ符号
特定のＬＤＰＣ符号は、パリティ検査行列またはＨ行列あるいは単純にＨとして知られる１および０の２次元行列によって定義される。Ｈは、ＬＤＰＣ符号器とＬＤＰＣ復号器との両方によって、先験的に既知である。Ｈは、Ｎ列Ｎ−Ｋ行を含む、すなわち、符号語のすべてのビットの列およびすべてのパリティ・ビットの行を含む。Ｈの各１は、列の符号語ビットと行のパリティ・ビットとの間の関連を表す。たとえば、Ｈの第３行第７列の１は、第３パリティ検査ビットが符号語の第７ビットに関連することを意味する。検査ビットおよびその検査ビットに関連するすべての可変ビットのｍｏｄｕｌｏ  ２合計は、０でなければならない。
【００１５】
Ｈのある列内の１の個数は、その列の重みｗｃとして知られる。同様に、Ｈのある行内の１の個数は、その行の重みｗｒとして知られる。すべての列が同一のｗｃを有し、すべての行が同一のｗｒを有するＨによって定義されるＬＤＰＣ符号は、正則ＬＤＰＣ符号（ｒｅｇｕｌａｒ  ＬＤＰＣ  ｃｏｄｅ）として知られる。ｗｃおよび／またはｗｒがそれぞれすべての列および／または行にまたがって同一ではないＨによって定義されるＬＤＰＣ符号は、非正則ＬＤＰＣ符号として知られる。
【００１６】
通常のＬＤＰＣを定義する特性は、Ｈが「疎」であるすなわち、Ｈの要素が、少数の１を伴ってほとんどが０であることである。研究は、Ｈ行列が、通常は良好に動作するためにｗｃ≧３を必要とし、非正則ＬＤＰＣ符号が正則ＬＤＰＣ符号より性能が優れていることを示した。
【００１７】
図２（Ａ）に、ＬＤＰＣ  Ｈ行列２００を示す。Ｈ行列２００は、Ｎ＝９列およびＮ−Ｋ＝６行を含む。したがって、Ｈ行列２００は、３ビットの情報語を受け入れ、６つのパリティ・ビットを付加し、９ビットの符号語を出力するＬＤＰＣ符号を定義する。したがって、この特定のＬＤＰＣ符号のレートは、３／９すなわち１／３である。Ｈ行列２００によって定義されるＬＤＰＣ符号は、正則であり、２のｗｃおよび３のｗｒを伴う。
【００１８】
チャネル出力：対数尤度比
図１に戻って、ＬＤＰＣ符号器１０６とＬＤＰＣ復号器１１２との間の経路１１４は、雑音のある通信路であり、したがって、復号器１１２は、ＬＤＰＣ符号器１０６によって出力された符号語の完全なコピーは受け取らない。その代わりに、読取りプロセッサ１１０は、１つまたは複数のＬｃｈ値を出力し、ここで、各Ｌｃｈ値は、チャネル入力符号語内の１ビットに対応する。
【００１９】
各Ｌｃｈ値は、対数尤度比（ＬＬＲ）である。ＬＬＲは、複数のビットを含むデータ構造であり、ここで、単一の符号ビットは、硬判定（すなわち、オリジナル・ビットが１または０のどちらであったかに関する読取りプロセッサ１１０の最良の推測）を示し、残りの大きさビットは、その硬判定での読取りプロセッサ１１０の信頼度の度合を示す。より正確には、ＬＬＲは、
【数１】
0005276173.tif 000002
を表し、ここで、ｐ０は、サンプルが０を表す確率であり、ｐ１は、サンプルが１を表す確率である。
【００２０】
たとえば、読取りプロセッサ１１０は、各Ｌｃｈ値を５ビット・データ構造として出力することができ、ここで、最上位ビットは、硬判定値を示す符号ビットであり、４つの大きさビットの１６個の値は、硬判定の信頼度を示す。したがって、たとえば、１つの通常の方式で、２進数０００００のＬＬＲ値は、最小信頼度を有する０の硬判定値を示し、２進数０１１１１の値は、最大信頼度を有する０の硬判定値を示し、２進数１００００は、未使用であり、２進数１０００１は、最小信頼度を有する１の硬判定値を示し、２進数１１１１１の値は、最大信頼度を有する１の硬判定値を示すはずである。
【００２１】
ＬＤＰＣ復号：確率伝搬
図３は、復号器１１２によって使用される通常のＬＤＰＣ復号方法３００の流れ図である。ＬＤＰＣ復号器１１２は、Ｎ個のＬｃｈ値を受け取り、復号された情報語を出力する。復号方法３００の心臓部は、確率伝搬と呼ばれる反復的２相メッセージパッシング・アルゴリズムである。確率伝搬は、タナー・グラフと呼ばれる視覚化の使用を用いて最もよく説明される。
【００２２】
図２（Ｂ）は、Ｈ行列２００のタナー・グラフである。一般に、タナー・グラフは、１）Ｈ内の列の数と等しい（したがって、可変ビットの個数と等しい）ビットノードの個数ｎ、２）Ｈ内の行の個数と等しい（したがって、パリティ・ビットの個数と等しい）チェックノードの個数ｍ、３）それぞれが単一のビットノードを単一のチェックノードに接続する、辺としても知られる線、４）ビットノードｎのそれぞれについて、受信器から受け取られたオリジナルのＬｃｈ値、および５）ビットノードｎのそれぞれについて、計算された硬判定出力値
【数２】
0005276173.tif 000003
を含む。タナー・グラフ２（Ｂ）は、９つのビットノードｎ０〜ｎ８、６つのチェックノードｍ０〜ｍ５、ビットノードをチェックノードに接続する１８個の辺２０２、９つのＬｃｈ値、および９つの
【数３】
0005276173.tif 000004
値を含む。
【００２３】
タナー・グラフの辺は、（すなわち、可変）ビットノードｎとチェックノードｍの間の関係を表す、すなわち、辺は、Ｈ内の１を表す。たとえば、図２（Ｂ）では、辺２０２は、第１のビットノードｎ０を第４のチェックノードｍ３に接続し、これは、図２（Ａ）のＨ行列２００の第１列第４行に１があることを意味する。
【００２４】
タナー・グラフは、二部グラフである、すなわち、辺は、ビットノードをチェックノードに接続することだけができ、ビットノードを別のビットノードにまたはチェックノードを別のチェックノードに接続することはできない。辺によって特定のチェックノードｍに接続されたすべてのビットノードｎの集合を、Ｎ（ｍ）と表す。辺によって特定のビットノードｎに接続されたすべてのチェックノードｍの集合を、Ｍ（ｎ）と表す。
【００２５】
特定の（ビットまたはチェック）ノードのインデックスは、グラフ内のそのノードのオリジナル・シーケンスである。（ビットまたはチェック）ノードの次数は、そのノードに接続された辺の個数である。したがって、タナー・グラフ内のビットノードｎの次数は、対応するＨ行列内の列ｎの重みｗｃと等しく、タナー・グラフ内のチェックノードｍの次数は、対応するＨ行列内の行ｍの重みｗｒと等しい。
【００２６】
図３に戻って、処理は、ステップ３０２で開始され、ステップ３０４すなわち復号器初期化に進む。復号器初期化３０４は、ビットノードｎに接続されたすべての辺（たとえば、図２（Ｂ）の２０２）にビットノードｎに関連する対応するＬｃｈ値をセットし、ビットノードｎの
【数４】
0005276173.tif 000005
値にビットノードｎのＬｃｈの硬判定値をセットすることを含む。したがって、たとえば、図２（Ｂ）では、ビットノードｎ０に関連するＬｃｈ値が＋５である場合に、ステップ３０４で、ビットノードｎ０をチェックノードｍ０およびｍ３に接続する２つの辺２０２に＋５がセットされ、ビットノードｎの
【数５】
0005276173.tif 000006
値に１がセットされる。このステップの第１部分を表す代替の形は、ビットノードｎ０が、集合Ｍ（ｎ０）内の各チェックノードｍに＋５のメッセージを送ることである。ビットノードｎからチェックノードｍに送られるメッセージは、Ｑｎｍと表され、ここで、Ｑｎｍは、ＬＬＲの形である。初期化されたばかりの復号器の状態を、状態０と称する。
【００２７】
次に、ステップ３０４は、症候群チェック・ステップ３０６に、Ｎ個の
【数６】
0005276173.tif 000007
値を含むベクトル
【数７】
0005276173.tif 000008
を送る。ベクトル
【数８】
0005276173.tif 000009
は、符号語候補である。症候群チェック・ステップ３０６は、次の式１を使用して症候群ベクトルｚを計算する。
【数９】
0005276173.tif 000010
ここで、ＨＴは、Ｈ行列の転置行列である。ｚが０ベクトルである場合には、ベクトル
【数１０】
0005276173.tif 000011
は、Ｈによって定義されるすべてのパリティ検査制約を満足している、すなわち、
【数１１】
0005276173.tif 000012
は有効な符号語である。その場合には、処理は、巡回冗長検査（ＣＲＣ）チェック３１８に進む。
【００２８】
その代わりに、ｚが０ベクトルではない場合には、ベクトル
【数１２】
0005276173.tif 000013
は、パリティ検査制約のうちの１つまたは複数に不合格であり、これを、通常は、満足されないチェックノードまたはＵＳＣと称する。０スカラ値ではない症候群ベクトルｚ内の要素の個数は、ベクトル
【数１３】
0005276173.tif 000014
内のＵＳＣの個数ｂである。さらに、症候群ベクトルｚの非ゼロ・スカラ要素のインデックスは、ベクトル
【数１４】
0005276173.tif 000015
内のＵＳＣのインデックスである。
【００２９】
ベクトル
【数１５】
0005276173.tif 000016
が症候群チェック３０６に不合格である場合には、処理は、１つまたは複数の復号反復３０８の第１の反復に継続する。復号反復３０８は、３つのステップすなわち、１）確率伝搬チェックノード更新ステップ３１０、２）確率伝搬ビットノード更新ステップ３１２、および３）症候群チェック・ステップ３１４（ステップ３０６と同一である）を含む。
【００３０】
確率伝搬チェックノード更新ステップ３１０では、各チェックノードｍは、集合Ｎ（ｍ）内のすべてのビットノードｎから受け取ったＱｎｍ個のメッセージを使用して、次の式２、３、および４に従って、Ｒｍｎと表されるメッセージを計算する。
【数１６】
0005276173.tif 000017
ここで、ｉは、復号反復であり、Ｎ（ｍ）＼ｎは、ビットノードｎを除外した集合Ｎ（ｍ）であり、βは、正の定数であり、その値は、符号パラメータに依存する。計算されたＲｍｎ個のメッセージは、その後、同一の辺に沿って、集合Ｎ（ｍ）内のすべてのビットノードｎに送り返される。Ｑｎｍ個のメッセージに似て、Ｒｍｎ個のメッセージは、ＬＬＲである。
【００３１】
次に、確率伝搬ビットノード更新ステップ３１２では、各ビットノードｎは、次の式５に従ってＱｎｍ個のメッセージを計算する。
【数１７】
0005276173.tif 000018
ここで、
【数１８】
0005276173.tif 000019
は、ビットノードｎのＬｃｈ値であり、Ｍ（ｎ）＼ｍは、チェックノードｍを除外した集合Ｍ（ｎ）である。次に、ビットノードｎは、計算されたＱｎｍ個のメッセージを集合Ｍ（ｎ）内のすべてのチェックノードｍに送る。
【００３２】
また、ビットノード更新ステップ３１２中に、各ビットノードｎは、次の式６および７に従って、その
【数１９】
0005276173.tif 000020
値を更新する。
【数２０】
0005276173.tif 000021
Ｐｎ≧０の場合には、
【数２１】
0005276173.tif 000022
であり、Ｐｎ＜０の場合には、
【数２２】
0005276173.tif 000023
である。式６によって生成される値を、Ｅ値またはＥＬＤＰＣ値とも称する。通常、ＥＬＤＰＣ値は、ターボ復号として知られるチューニング・プロセスの一部として読取りプロセッサ（たとえば、図１の読取りプロセッサ１１０）に送り返される。式７によって生成される値を、Ｐ値と称する。式２〜７によって表される特定の確率伝搬アルゴリズムは、ｍｉｎ−ｓｕｍアルゴリズムとして知られる。
【００３３】
【数２３】
0005276173.tif 000024
が、各復号反復３０８中に更新され、最終的に復号プロセス３００によって出力されることに留意されたい。オリジナルのＬＬＲ値Ｌｃｈは、復号プロセス３００中に変更されないままになる。言い換えると、各復号反復３０８中に、各ビットノードｎは、その投票を、チェックノードｍを介して関連するすべての他のビットノードｎの正しい値に関して投じる。たとえば、図２（Ｂ）では、ビットノードｎ０は、チェックノードｍ０およびｍ３に関連する。したがって、ｎ０は、その投票を、チェックノードｍ０およびｍ３に関連するビットノードすなわちｎ３、ｎ５、ｎ６、およびｎ７の正しい値に関して投じる。ビットノードｎのＬｃｈ値の大きさ値が大きいほど（すなわち、信頼度が高いほど）、ビットノードｎの投票はより多くカウントされる。この投票の正味の効果は、低いＬｃｈ大きさ値（すなわち、信頼度）を有するビットノードの
【数２４】
0005276173.tif 000025
値が、そのビットノードが関連する高信頼度ビットノードの確率を変更し、これに従うことである。言い換えると、あるビットノードのＬｃｈ値が、誤りのある硬判定値および小さい大きさを含む場合に、他のビットノードの組み合わされた投票は、１回または複数回の反復の後に、その誤りのある硬判定値を訂正する傾向がある。
【００３４】
ビットノード更新ステップ３１２は、復号器の現在の
【数２５】
0005276173.tif 000026
値から構成されたベクトル
【数２６】
0005276173.tif 000027
を症候群チェック・ステップ３１４に送る。ステップ３１４の症候群チェックは、上で述べたステップ３０６の症候群チェックと同一である。ベクトル
【数２７】
0005276173.tif 000028
が症候群チェック３１４に合格する場合には、ベクトル
【数２８】
0005276173.tif 000029
がＣＲＣステップ３１８に送られる。
【００３５】
ＬＤＰＣ復号：巡回冗長検査および誤って満足されたチェックノード
症候群チェック３０６または３１４に合格することは、ベクトル
【数２９】
0005276173.tif 000030
が有効な符号語であることだけを意味し、必ずしも復号された正しい符号語（ＤＣＣＷ）であることは意味しない。ＬＤＰＣ復号器がＤＣＣＷではない有効な符号語を生成することが有り得る。その場合に、ベクトル
【数３０】
0005276173.tif 000031
内には、ＵＳＣではなく、誤って満足されたチェックノード（ＭＳＣ）がある。したがって、有効なベクトル
【数３１】
0005276173.tif 000032
がＤＣＣＷであることを保証するために、プロセス３００は、ベクトル
【数３２】
0005276173.tif 000033
を巡回冗長検査（ＣＲＣ）３１８に渡す。ＣＲＣチェックは、伝送または格納中のデータの変更を検出できるチェックサム演算である。
【００３６】
ベクトル
【数３３】
0005276173.tif 000034
がＣＲＣチェックに合格する場合には、ベクトル
【数３４】
0005276173.tif 000035
は、ＤＣＣＷであり、プロセス３００は、グローバル変数ＤＣＣＷに真をセットし、ベクトル
【数３５】
0005276173.tif 000036
を出力し、ステップ３２０で終了する。そうでない場合には、ベクトル
【数３６】
0005276173.tif 000037
はＤＣＣＷではなく、プロセス３００は、グローバル変数ＤＣＣＷに偽をセットし、ベクトル
【数３７】
0005276173.tif 000038
を出力し、ステップ３２０で終了する。グローバル変数ＤＣＣＷは、ＤＣＣＷが生成されたか否かを他の復号プロセス（たとえば、下で述べる図１２のＴＳ−ＲＯＭリスト復号プロセス１２０６）に知らせる。
【００３７】
ステップ３１４に戻って、ベクトル
【数３８】
0005276173.tif 000039
が症候群チェックに不合格である場合には、ベクトル
【数３９】
0005276173.tif 000040
は、それでも１つまたは複数のＵＳＣを含む。ＵＳＣを解決する通常の方法は、もう１つの復号反復３０８を実行することである。しかし、特定のベクトル
【数４０】
0005276173.tif 000041
内に、穏当な長さの時間では絶対に満足できない１つまたは複数のＵＳＣが存在する場合がある。したがって、ＬＤＰＣ復号器は、通常、特定のベクトル
【数４１】
0005276173.tif 000042
に対して実行できる復号反復の回数において制限される。反復の最大回数の通常の値は、５０から２００までの範囲にわたる。
【００３８】
図３では、ステップ３１６が、反復の最大回数に達したかどうかを判定する。そうでない場合には、もう１つの復号反復３０８が実行される。その代わりに、反復の最大回数に達した場合には、復号器プロセス３００が失敗した、すなわち、復号器は、「失敗した復号器」である。その場合には、プロセス３００は、グローバル変数ＤＣＣＷに偽をセットし、ベクトル
【数４２】
0005276173.tif 000043
を出力し、ステップ３２０で終了する。
【００３９】
失敗した復号器のベクトル
【数４３】
0005276173.tif 000044
が、少数（たとえば、１６個未満）のＵＳＣを含む場合には、ベクトル
【数４４】
0005276173.tif 000045
は、ニア・コードワード（ｎｅａｒ  ｃｏｄｅｗｏｒｄ）（ＮＣＷ）と呼ばれる。失敗した復号器のベクトル
【数４５】
0005276173.tif 000046
が、多数の（たとえば、１５個を超える）ＵＳＣを含む場合には、ベクトル
【数４６】
0005276173.tif 000047
は、無効符号語（ｉｎｖａｌｉｄ  ｃｏｄｅｗｏｒｄ）（ＩＣＷ）と呼ばれる。
【００４０】
失敗した復号プロセスを処理する２つの通常の方法は、１）対応するデータの再送を要求することまたは２）１つもしくは複数の後処理（ＰＰ）方法にベクトル
【数４７】
0005276173.tif 000048
を渡すことである。通常、ベクトル
【数４８】
0005276173.tif 000049
内のＵＳＣの個数ｂは、この２つの方法のどちらが使用されるかを規定する。大きいｂ（たとえば、１６を超える）は、通常、再送または他の後処理方法によって処理され、小さいｂ値は、エラーフロア軽減後処理方法によって処理される。
【００４１】
ＢＥＲ、ＳＮＲ、およびエラーフロア
ＬＤＰＣ復号器のビット誤り率（ＢＥＲ）は、処理されるｘ個のビットについて何個の誤って復号されたビットが生成されるかを表す比率である。したがって、たとえば、１０−９のＢＥＲを有する復号器は、平均して、処理される１０億ビットごとに１つの誤ったビットを生成する。ＢＥＲが小さいほど、復号器はよりよい。ＬＤＰＣ復号器のＢＥＲは、復号器が失敗するすなわち、復号された正しい符号語ＤＣＣＷに収束せずに終了する時に、高まる（悪化する）。
【００４２】
ＬＤＰＣ復号器のＢＥＲは、復号器の入力信号の信号対雑音比（ＳＮＲ）によって強く影響される。ＳＮＲの関数としてのＢＥＲのグラフは、通常、２つの別個の領域すなわち、ＢＥＲがＳＮＲの単位上昇を前提としてすばやく改善される（減少する）最初の「滝」領域と、ＳＮＲの単位上昇がＢＥＲのささやかな改善だけをもたらす後続の「エラーフロア」領域とを含む。したがって、エラーフロア領域での大きいＢＥＲ改善を達成するためには、ＳＮＲ向上以外の方法が必要である。
【００４３】
ＬＤＰＣ復号のエラーフロア特性を改善する１つの方法は、符号語長さを増やすことである。しかし、符号語長さの増加は、ＬＤＰＣ復号に必要なメモリおよび他のコンピューティング・リソースをも増やす。したがって、ＨＤドライブ上の読取りチャネル・デバイスについて通常そうであるように、そのようなリソースが厳密に制限される場合には、必要なエラーフロア改善をもたらすために、他の方法を見つけなければならない。
【００４４】
もう１つの不足するリソースが、処理サイクルである。通常、指定されたスループットを達成するために、ＨＤドライブは、符号語を復号するために固定された個数の読取りチャネル処理サイクルを計上する。その予算を超える方法（すなわち、オフザフライ（ｏｆｆ−ｔｈｅ−ｆｌｙ）法）は、スループットを下げる。より望ましいのは、クロックサイクル割当内でＤＣＣＷを回復し、したがってスループットを下げないオンザフライ法である。
【００４５】
トラッピング・セットおよび支配的トラッピング・セット
（ａ，ｂ）トラッピング・セットは、復号器が反復の最大回数以内に満足できないｂ個のＵＳＣおよびこれらのＵＳＣに関連するａ個の誤りのあるビットノード（ＥＢＮ）の集合である。トラッピング・セットの大多数は、５つ未満のＵＳＣおよび１０個未満のＥＢＮを含む。トラッピング・セットは、ＬＤＰＣ復号器のエラーフロア特性に大きい影響を有する、すなわち、ＬＤＰＣ復号器がＤＣＣＷへの収束に失敗する時に、これは、しばしば、トラッピング・セットのゆえである。
【００４６】
ＬＤＰＣ復号器のエラーフロア特性を改善する１つの形は、（ｉ）失敗した復号器の
【数４９】
0005276173.tif 000050
ベクトル内のＵＳＣを調べ、トラッピング・セット（ある場合に）を識別し、（ｉｉ）これらのＵＳＣに関連するＥＢＮを識別し、（ｉｉｉ）これらのトラッピング・セットに関連する１つまたは複数のＥＢＮを反転し、（ｉｖ）復号器を再始動することである。１つの可能な実施態様では、ＬＤＰＣ復号器が初期化されたばかりである、すなわち、復号器が状態０である場合に、ＥＢＮの反転は、（ｉ）ＥＢＮのＬｃｈ値の硬判定値を反転することすなわち、１を０にし、逆も同様にすることと、（ｉｉ）その同一のＬｃｈ値の大きさビットすなわち信頼度に最大値、たとえば全ビット１をセットすることとを含む。復号器が、状態０以外のある状態である場合には、ＥＢＮの反転は、（ｉ）ＥＢＮのＰ値（上の式７によって定義される）の硬判定値を判定することと、（ｉｉ）そのＥＢＮのＬｃｈ値、Ｐ値、およびすべての関連するＱｎｍ個のＬＬＲの硬判定値に、ステップ（ｉ）の硬判定値の反対をセットすることと、（ｉｉｉ）そのＥＢＮのＬｃｈ値、Ｐ値、およびすべての関連するＱｎｍ個のＬＬＲの大きさビットに最大値をセットすることとを含む。しばしば、１つまたは２つのＥＢＮを反転することによって、トラッピング・セットが「破壊され」、再始動された復号器は、ＤＣＣＷに収束する。
【００４７】
異なるトラッピング・セットは、破壊された時に、エラーフロア特性の異なる改善をもたらす。支配的トラッピング・セット（ＤＴＳ）は、その破壊がＢＥＲ／エラーフロア特性の指定された改善をもたらす、トラッピング・セットの最小限のセットを指す。たとえば、ＤＴＳ−１は、ＢＥＲの単一桁の、たとえば１０−９から１０−１０への大きさ改善をもたらすトラッピング・セットの最小限のセットを指し、ＤＴＳ−３は、ＢＥＲの３桁の、たとえば１０−１０から１０−１３への大きさ改善をもたらす。
【００４８】
ニア・コードワードのリスト復号
リスト復号は、トラッピング・セットを検出し、破壊する、１つの後処理法である。リスト復号では、ベクトル
【数５０】
0005276173.tif 000051
内の観察されたトラッピング・セットが、既知のトラッピング・セットの１つまたは複数のリストと照合される。トラッピング・セット・リストは、通常、リスト内の各トラッピング・セット内のすべてのＵＳＣのインデックスおよびこれらのＵＳＣに関連する１つまたは複数のＥＢＮのインデックスを含む。観察されたトラッピング・セットと一致するトラッピング・セットが、リスト内で見つかる場合には、ＥＢＮインデックス値（１つまたは複数）が、リストから取り出される。次に、これらのビットノードが反転され、図３の復号プロセス３００が再始動される。
【００４９】
トラッピング・セット・シミュレーション
リスト復号に必要なトラッピング・セット・リストは、通常、ソフトウェア・シミュレーション・ツールおよびハードウェア・シミュレーション・ツールを使用してオフラインで生成される。図４は、トラッピング・セットを識別し、これらのトラッピング・セットに関するさまざまな情報を記録するオフライン・トラッピング・セット（ＴＳ）シミュレーション・ツール４００のブロック図である。ツール４００は、たとえば、フィールドプログラマブル・ゲート・アレイ（ＦＰＧＡ）内で実施することができる。ＬＤＰＣの正しい符号語（ＣＣＷ）４０２が、チャネルおよび信号モデル４０４に送られ、このチャネルおよび信号モデル４０４は、図１の雑音のある通信路１１４の挙動をエミュレートする。チャネルおよび信号モデル４０４は、Ｌｃｈ値４０６をＬＤＰＣ復号器４０８に出力する。ＬＤＰＣ復号器４０８が、ニア・コードワード（ＮＣＷ）４１０を生成する場合には、ＮＣＷ  ４１０が、症候群チェック・モジュール４１２および不一致位置レコーダ４１４に送られる。症候群チェック４１２は、ＮＣＷ  ４１０内のすべてのＵＳＣのインデックス４１６を出力する。不一致位置レコーダ４１４は、ＮＣＷ  ４１０をＣＣＷ  ４０２と比較し、ＮＣＷ  ４１０内のすべてのＥＢＮのインデックス４１８を出力する。ＵＳＣインデックス４１６およびＥＢＮインデックス４１８が、トラッピング・セット（ＴＳ）情報４２０を構成する。
【００５０】
所与のＬＤＰＣ実施態様について、すべての可能なトラッピング・セットが、数百万個に達する場合がある。しかし、その実施態様のエラーフロアにおける大きい（すなわち、１桁以上の）改善の達成は、通常、すべての可能なトラッピング・セットのサブセットすなわち支配的トラッピング・セット（ＤＴＳ）のみを必要とする。したがって、オフラインＴＳシミュレーション・ツール４００は、ＤＴＳ−Ｎコンパイラ４２２を含み、ＤＴＳ−Ｎコンパイラ４２２は、その入力としてＴＳ情報４２０をとり、ＤＴＳ−Ｎ情報４２４を生成する。
【００５１】
ＤＴＳ−Ｎコンパイラ４２２は、３ステップ・プロセスすなわち、収集、ランキング、および評価を使用する。トラッピング・セット収集法は、トラッピング・セットを検出するのに、符号グラフの構造に基づく決定論的雑音インパルスを利用する。次に、収集されたトラッピング・セットは、ディスタンス・トゥー・エラー・バウンダリ（ｄｉｓｔａｎｃｅ−ｔｏ−ｅｒｒｏｒ  ｂｏｕｎｄａｒｙ、ＤＥＢ）値によってランキングされ、ここで、小さいＤＥＢ値を有するトラッピング・セットが、エラーフロアにより多く寄与する。次に、重点的サンプリングが、トラッピング・セットを評価し、予測されたランキングを確認するのに使用される。
【００５２】
実際には、そのようなＦＰＧＡベースのオフライン・シミュレーションは、実行に１年を要する可能性がある。たとえば、４Ｇｂ／ｓ  ＨＤドライブについて１０−１５のＢＥＲをもたらすトラッピング・セットを識別するためには、オフライン・シミュレーション・ツール（たとえば、図４のツール４００）を約２８９日間動作させる必要がある。通常、この時間制約は問題ではない。というのは、しばしば、ＨＤドライブ読取りチャネルの最終設計とチップの量産との間に１年から２年の遅延があるからである。
【００５３】
トラッピング・セット読取り専用メモリ（ＴＳ−ＲＯＭ）
したがって、図４のツール４００のようなオフラインＴＳシミュレーション・ツールを使用することによって、特定のＬＤＰＣ実施態様についてエラーフロア特性の改善をもたらす１つまたは複数のトラッピング・セットまたは支配的トラッピング・セットを先験的に識別することが可能である。ランタイム環境でリスト復号を実施する１つの形は、オフライン生成された図４のトラッピング・セット情報４２０をトラッピング・セット読取り専用メモリ（ＴＳ−ＲＯＭ）に格納し、そのＴＳ−ＲＯＭをリスト・デコーダ・プログラムと結合することである。ＴＳ−ＲＯＭリスト・デコーダ・プログラムは、
【数５１】
0005276173.tif 000052
で観察されるＵＳＣをＴＳ−ＲＯＭに格納されたトラッピング・セットと比較する。一致が見つかる場合には、ＴＳ−ＲＯＭリスト・デコーダ・プログラムは、ＬＤＰＣ復号器内の適当なビットノード値を反転し、復号器を再始動する。
【００５４】
通常、ＴＳ−ＲＯＭ情報は、単一リンク・リストまたは二重リンク・リストにランダムに格納され、このリストは、ブルート・フォース順次検索を使用して検索される。通常、各（ａ，ｂ）トラッピング・セットは、ＴＳ−ＲＯＭリスト内で（２＋ａ＋ｂ）個のレコードを占める。したがって、（４，４）トラッピング・セット・プロファイル（すなわち、４つのＵＳＣおよび４つのＥＢＮ）について、１０個のレコードすなわち、４つのＵＳＣがあることを示す１つのレコード、それに続く４つの個々のＵＳＣレコード、次に４つのＥＢＮがあることを示すレコード、それに続く４つの個々のＥＢＮレコードがある。通常のＴＳ−ＲＯＭリスト実施態様は、約１００個のトラッピング・セットを格納し、誤って満足されたチェックノードに関する情報は全く格納しない。
【００５５】
そのようなＴＳ−ＲＯＭ実施態様が経済的に実用的であるためには、単一のＴＳ−ＲＯＭが、多数の実施態様で、要求されるエラーフロア改善を達成できなければならない。しかし、トラッピング・セットは、同一のＬＤＰＣ符号が実施される時であっても、実施態様によって変化する。たとえば、２つのＨＤドライブで使用されるＬＤＰＣ符号が同一の場合であっても、これらのＨＤドライブに関連するトラッピング・セットが異なる場合がある。具体的に言うと、研究から、トラッピング・セットが、ＨＤドライブのジッタ・プロファイル、記号間干渉特性、およびパルス整形方式によって影響を受けることが示された。これらの要因は、異なる製造業者のＨＤドライブの間だけではなく、同一製造業者の異なるＨＤドライブ・モデルの間でも変化する可能性があり、同一モデルの異なるプロダクション・ランの間の変動すらある。したがって、トラッピング・セットは、２つの同一モデルのハード・ドライブの間でさえ変化し得る。そのように多数の異なるＨＤドライブのＬＤＰＣトラッピング・セットをシミュレートすることは、非実用的である。それでも、ＨＤドライブの大きいクラスに共通するトラッピング・セットだけをロードされたＴＳ−ＲＯＭは、特定のＨＤドライブと対にされた時に、要求されるレベルのエラーフロア改善をもたらさない可能性がある。
【００５６】
ＴＳ−ＲＯＭの性能を改善する１つの方法は、製造されたデバイスのテスト・モデルから得られた結果を用いて、ＦＰＧＡベースのオフライン・シミュレーション・ツール（たとえば、図４のツール４００）によって生成された情報を補足することである。通常、回路設計が最終化された後に、その設計の限られた個数のテスト・モデルが、量産が始まる前に製造され、テストのために配布される。特定のＨＤドライブ実施態様について１０−１５のＢＥＲをもたらすトラッピング・セットを判定するのに１年を要する場合があるが、１０−１２のＢＥＲをもたらすトラッピング・セットを判定するのには、１日のみを要する。したがって、テスト・モデルは、限られた時間期間の間にＬＤＰＣテスト・モードで動作させられ、発見されたトラッピング・セットのすべてが格納される。まだＴＳ−ＲＯＭ内にはない、発見されたトラッピング・セットのすべてが、ＴＳ−ＲＯＭに追加される。消費者に配布される実際のデバイスを使用することによって、この方法は、ＦＰＧＡベースのオフライン・シミュレーション・ツール（たとえば、図４のツール４００）に発見されなかった可能性があるトラッピング・セットを取り込む。
【００５７】
トラッピング・セット・ランダムアクセス・メモリ（ＴＳ−ＲＡＭ）
ＴＳ−ＲＯＭの静的トラッピング・セット・リストに対する１つのランタイム代替案は、トラッピング・セット情報をトラッピング・セット・ランダムアクセス・メモリ（ＴＳ−ＲＡＭ）に格納し、図４のオフライン・トラッピング・セット・シミュレーション・ツール４００を、実際の個々のデバイス（たとえば、ＨＤドライブ）に対して動作するランタイム・トラッピング・セット収集分析ツールにすることである。チャネルおよび信号モデル（たとえば、図４のモデル４０４）から初期値を受け取るのではなく、ランタイム・ツールは、その特定のデバイスの実際の信号を処理する。ランタイム・ツールは、リスト復号器機能性を含む、すなわち、ランタイム・ツールは、観察されたＵＳＣをＴＳ−ＲＡＭ内の格納されたトラッピング・セット情報と照合し、一致が見つかる場合には、格納された情報を使用して、復号器ビットノード値を変更し、復号器を再始動することを試みる。一致が見つからない場合には、ランタイム・ツールは、観察されたトラッピング・セットを分析する、すなわち、ＵＳＣに関連するＥＢＮを識別し、観察されたトラッピング・セットが、ＴＳ−ＲＡＭへの格納に関するしきい要件（たとえば、ＤＴＳ−Ｎへのメンバシップ）を満足したかどうかを判定する。
【００５８】
理論的に、上で説明したＴＳ−ＲＡＭツールは、すべての実施態様のトラッピング・セット・プロファイルに適合することができる。現実には、図４のオフライン・シミュレーション・ツール４００によって実行されるトラッピング・セット／支配的トラッピング・セット・シミュレーションは、計算的に複雑である。具体的に言うと、おそらくは数百万個のトラッピング・セットから支配的トラッピング・セットを構成することが、特に複雑である。この複雑さが、上で説明したＴＳ−ＲＡＭツールをほとんどのＨＤドライブに不適切にする。通常、ＨＤドライブは、高いレート（たとえば、４ギガビット毎秒）でデータを出力し、非常に低いＢＥＲ／エラーフロア・レート（たとえば、１０−１３から１０−１５）を要求するが、そのファームウェアでささやかなコンピューティング・リソースのみを提供する。
【００５９】
さらに、ＴＳ−ＲＡＭツールは、図４のオフライン・シミュレーション・ツール４００に似て、ＥＢＮインデックスを生成するために正しい符号語（ＣＣＷ）を必要とする。ＣＣＷは、オフライン・シミュレーション環境では簡単に入手可能であるが、ランタイム環境ではそうではない。
【００６０】
本発明のある種の実施形態によれば、ＲＯＭ内の格納されたトラッピング・セット・プロファイルの編成のために、方法が実行される。トラッピング・セット・プロファイルは、優位性によってすなわち、ＬＤＰＣ復号器のエラーフロア特性に対する影響によって、ランキングされる。より支配的なトラッピング・セット・プロファイルは、満足されないチェックノード（ＵＳＣ）と誤って満足されたチェックノード（ＭＳＣ）との両方に関する情報を含むが、より支配的でないトラッピング・セット・プロファイルは、ＵＳＣに関する情報だけを含む。次に、トラッピング・セット・プロファイル情報は、複数のリンクされた階層データ・テーブルに編成され、この階層データ・テーブルは、ポインタチェース検索を使用する最も支配的な一致するトラッピング・セット・プロファイルのすばやい突止めおよび取出しを可能にする。
【００６１】
本発明のある種の実施形態によれば、ＲＡＭ内の支配的トラッピング・セットの収集および識別のために、効率的なランタイム方法が実行される。可能な場合には、新たに発見されたトラッピング・セットが、ＲＡＭに格納され、次に、トラッピング・セットが最後に一致した時以降にＲＡＭが検索された回数、トラッピング・セットがＲＡＭに追加された時以降にそのトラッピング・セットが一致した総回数、満足されないチェックノードの個数、および誤りのあるビットノードの個数という要因のうちのいずれか１つまたは複数に基づいてソートされ、またはランキングされる。低いランキングのトラッピング・セット・プロファイルは、新たに発見されたトラッピング・セット・プロファイルのための余地を作るためにＲＡＭから削除される。したがって、図４のＤＴＳ−Ｎコンパイラ４２２で使用されるものなどの支配的トラッピング・セットの先験的識別のための非常に計算的に複雑なオフライン方法を使用することに加えてまたはその代わりに、本発明のこれらの実施形態は、できる限り多数の新たに発見されたトラッピング・セットが格納され、非支配的トラッピング・セット・プロファイルが周期的なランキングおよび削除によって選別される、低い計算的複雑さの後天的方法を実行する。
【００６２】
本発明の実施形態は、通常は、オンザフライ方法である、すなわち、ＬＤＰＣ復号のために計上されたクロックサイクル内にＤＣＣＷを回復でき、したがって、システム・スループットに悪影響を与えない。
【００６３】
図５は、本発明の一実施形態によるＬＤＰＣ復号システム５００のブロック図である。図１の従来技術のＨＤドライブ１００に類似する本発明のＨＤドライブでは、図５のＬＤＰＣ復号システム５００は、図１のＬＤＰＣ復号器１１２に類似するＬＤＰＣ復号器の一部として実施される。その範囲で、図５の入力Ｌｃｈ値は、図１の復号器入力Ｌｃｈ値に類似し、図５の出力
【数５２】
0005276173.tif 000053
ベクトルは、図１の復号された情報語に類似する。
【００６４】
ＬＤＰＣ復号器５０２は、Ｌｃｈ値を受け取り、図３のＬＤＰＣ復号プロセス３００を実行し、ベクトル
【数５３】
0005276173.tif 000054
をポストプロセッサ５０４およびＴＳ−ＲＡＭアップデータ５０６に出力する。ポストプロセッサ５０４は、後処理（ＰＰ）方法リスト５０８に接続され、ＰＰ方法リスト５０８は、後処理方法、たとえばＴＳ−ＲＯＭリスト復号、ＴＳ−ＲＡＭリスト復号などを表す１つまたは複数の実行可能プログラムを含むメモリである。ポストプロセッサ５０４が、特定のＰＰ方法を実行することを必要とする場合には、ポストプロセッサ５０４は、ＰＰ方法リスト５０８から実行可能プログラムを読み取り、そのプログラムを実行する。ポストプロセッサ５０４は、任意の個数のこれらのＰＰ方法を並列にまたは順次実行することができる。ポストプロセッサ５０４は、ベクトル
【数５４】
0005276173.tif 000055
を出力し、これは、ＬＤＰＣ復号システム５００から出力されることに加えて、ＴＳ−ＲＡＭアップデータ５０６にも送られる。
【００６５】
データ・テーブル
実行中に、特定のＰＰ方法が、ＰＰ方法実行可能プログラム・コードとは別々のデータ構造にアクセスすることを必要とする場合がある。具体的に言うと、ＴＳ−ＲＯＭリスト復号方法およびＴＳ−ＲＡＭリスト復号方法は、それぞれＴＳ−ＲＯＭ  ５１０およびＴＳ−ＲＡＭ  ５２０に格納されたトラッピング・セット情報の１つまたは複数のリストにアクセスする。
【００６６】
図５の例示的実施形態では、ＴＳ−ＲＯＭ  ５１０は、４つのテーブルすなわち、Ｂテーブル５１２、Ｐテーブル５１４、Ｅテーブル５１６、およびＥＩテーブル５１８を含む。ＴＳ−ＲＡＭ  ５２０は、２つのテーブルすなわち、ＲＡＭ  Ｐテーブル５２２およびＲＡＭインデックス５２４を含む。テーブルは、１つまたは複数の等しいサイズの行（レコード）および１つまたは複数の等しいサイズの列（フィールド）に編成された、ディジタル・データの２次元行列である。テーブルのレコードは、０から始めて上から下へ順番に番号を付けられる。この番号が、レコード番号である。
【００６７】
Ｐテーブル５１４および５２２は、ＵＳＣおよびそれに関連するＥＢＮに関する情報を含む。Ｂテーブル５１２は、ＲＯＭ  Ｐテーブル５１４のポインタ情報を含む。ＥＩテーブル５１８は、ＭＳＣに関する情報を含み、Ｅテーブル５１６は、ＥＩテーブル５１８のポインタ情報を含む。ＲＡＭインデックス・テーブル５２４は、ＲＡＭ  Ｐテーブル５２２のポインタ情報を含む。
【００６８】
図６は、図５のＲＯＭ  Ｐテーブル５１４の例示的レイアウトである。ＲＯＭ  Ｐテーブル５１４は、トラッピング・セット・プロファイル情報すなわち、ＵＳＣインデックスおよびＥＢＮインデックスを含む。ＲＯＭ  Ｐテーブル５１４は、各格納されたトラッピング・セットのＵＳＣごとに１つの、複数のレコード（行）を含む。レコード番号６０２は、０から始まる、Ｐテーブル５１４内のレコードの順序位置である。
【００６９】
ＲＯＭ  Ｐテーブル５１４内の各レコードは、３つのフィールドすなわち、ＬＡＹＥＲ  ６０４、ＵＳＣ＿ＩＮＤＥＸ  ６０６、およびＥＢＮ＿ＩＮＤＥＸ  ６０８を含む。一部のＬＤＰＣ復号器は、更新動作のセットを並列に実行するように構成され、これを、レイヤと称する。ＬＡＹＥＲ  ６０４は、ＵＳＣを含んだ復号レイヤの番号を示す。ＵＳＣ＿ＩＮＤＥＸ  ６０６は、ＵＳＣのインデックスを含む。ＥＢＮ＿ＩＮＤＥＸ  ６０８は、ＵＳＣに関連する１つまたは２つのＥＢＮのインデックスを含む。
【００７０】
ＲＯＭ  Ｐテーブル５１４は、まずｂ（すなわち、
【数５５】
0005276173.tif 000056
内のＵＳＣの個数）に基づいてソートされ、たとえば、ｂ＝２を有するすべてのトラッピング・セットが最初に現れ、すべてのｂ＝３トラッピング・セットがそれに続くなどである。したがって、ｂ＝２範囲にトラッピング・セットごとに２つのレコード（たとえば、６１０、６１２）があり、最終的に、ｂ＝３を有するトラッピング・セットの３レコード・セット（たとえば、６１４、６１６）、ｂ＝４を有するトラッピング・セットの４レコード・セット（６１８、６２０）などが続く。
【００７１】
各ｂ範囲内では、トラッピング・セットは、優位性すなわち、そのトラッピング・セットがエラーフロア特性に対して有する影響によってソートされる。エラーフロア特性に対してより大きい影響を有するトラッピング・セットは、ｂ範囲の始めに現れ、より少ない影響を有するトラッピング・セットは、終り近くに現れる。その後、特定のトラッピング・セットのレコードは、ＵＳＣ＿ＩＮＤＥＸ  ６０６によってソートされる。
【００７２】
図７は、図５のＢテーブル５１２の例示的レイアウトである。Ｂテーブル５１２は、ＲＯＭ  Ｐテーブル５１４内のｂ値ごとに、ＲＯＭ  Ｐテーブル５１４内およびＥテーブル５１６内のそのｂ値の最初の出現へのポインタと、そのｂ値のＥテーブル５１６内のレコードの個数とを含む。したがって、Ｂテーブル５１２内には、ｂ値ごとに単一のレコードがあり、このｂ値は、レコード番号７０２によって示される。しかし、レコード番号７０２は０から始まるが、ｂ値は、通常は、２以上から始まる。したがって、本発明のこの例示的実施形態では、レコード番号７０２にオフセットを加算して、対応するｂ値を作る。たとえば、ｂ≧２を有するトラッピング・セットだけが格納される場合には、２のオフセットが、対応するｂ値に達するために各レコード番号に加算される。
【００７３】
フィールドＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴ  ７０４は、ＲＯＭ  Ｐテーブル５１４内の特定のｂ値の最初の出現の位置を含む。フィールドＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴ  ７０６は、Ｅテーブル５１６内の特定のｂ値の最初の出現の位置を含む。フィールドＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳ  ７０８は、この特定のｂ値の、Ｅテーブル５１６内のレコードの個数を含む。
【００７４】
図８は、図５のＥテーブル５１６の例示的レイアウトである。Ｅテーブル５１６は、ＥＩテーブル５１８内のＭＳＣレコードへのポインタを含む。Ｅテーブル５１６内の各レコードは、レコード番号８０２、ＥＩＴＡＢＬＥ＿ＳＴＡＲＴ＿ＡＤＤＲＥＳＳフィールド８０４、およびＥＩＴＡＢＬＥ＿ＥＮＤ＿ＡＤＤＲＥＳＳフィールド８０６を有する。ＥＩＴＡＢＬＥ＿ＳＴＡＲＴ＿ＡＤＤＲＥＳＳフィールド８０４は、ＥＩテーブル５１８内の対応するデータの最初の出現へのポインタを含み、ＥＩＴＡＢＬＥ＿ＥＮＤ＿ＡＤＤＲＥＳＳフィールド８０６は、ＥＩテーブル５１８内の対応するデータの最後の出現へのポインタを含む。
【００７５】
図９は、図５のＥＩテーブル５１８の例示的レイアウトである。ＥＩテーブル５１８は、ＭＳＣに関連するＥＢＮのインデックスを格納する。ＥＩテーブル５１８内の各レコードは、レコード番号９０２を有し、２つのフィールドすなわちＢＬＯＣＫ＿ＣＯＬＵＭＮフィールド９０４およびＢ＿ＩＮＤＥＸフィールド９０６を含む。ＢＬＯＣＫ＿ＣＯＬＵＭＮフィールド９０４は、ＥＢＮが配置されたブロック列を示し、Ｂ＿ＩＮＤＥＸフィールド９０６は、ＥＢＮのインデックスである。
【００７６】
図１０は、図５のＲＡＭ  Ｐテーブル５２２の例示的レイアウトである。ＲＡＭ  Ｐテーブル５２２は、ＲＯＭ  Ｐテーブル５１４内では見つからない新たに識別されたトラッピング・セットのプロファイルを格納する。ＲＡＭ  Ｐテーブル５２２内の各行（すなわち、レコード）は、レコード番号１００２を有し、２つのフィールドすなわち２ビットのＴＡＧフィールド１００４およびＲ＿ＷＯＲＤフィールド１００６を含む。ＴＡＧフィールド１００４の４つの可能な値は、Ｒ＿ＷＯＲＤフィールド１００６内のレコード・タイプおよびデータの構造を示す。ＴＡＧフィールド１００４が１１の値を有する場合には、レコードは、トラッピング・セット全体に関する情報を含むプライマリ・レコードである。ＴＡＧフィールド１００４が１０の値を有する場合には、レコードは、セカンダリ・レコードであり、トラッピング・セット・プロファイル内の特定のＵＳＣに関する情報を含む。ＴＡＧフィールド１００４が００または０１の値を有する場合には、Ｒ＿ＷＯＲＤフィールド１００６は空である、すなわち、このレコードは、新たに識別されたトラッピング・セットのプロファイル情報を格納するのに使用可能である。トラッピング・セット・プロファイルは、通常、単一のプライマリ・レコードとそれに続くｂ個のセカンダリ・レコードとを含む。
【００７７】
レコードがプライマリ・レコードである場合には、Ｒ＿ＷＯＲＤフィールド１００６は、４つのサブフィールドすなわち、（ｉ）ｂ値サブフィールド１００８、（ｉｉ）トラッピング・セットＥＢＮの個数を記録するａ値サブフィールド１０１０、（ｉｉｉ）このトラッピング・セットに最後に一致したＴＳ−ＲＡＭ検索の個数を示すＬＡＳＴ＿ＨＩＴ＿ＮＵＭサブフィールド１０１２、および（ｉｖ）このトラッピング・セットがＴＳ−ＲＡＭに格納された時以降にこの特定のトラッピング・セット・プロファイルが観察されたトラッピング・セットと一致した回数を記録するＨＩＴ＿ＣＯＵＮＴＥＲサブフィールド１０１４を含む。
【００７８】
レコードがセカンダリ・レコードである場合には、Ｒ＿ＷＯＲＤフィールド１００６は、トラッピング・セット内の単一のＵＳＣのレイヤ（ＬＡＹＥＲフィールド１０１６）およびインデックス（ＵＳＣ＿ＩＮＤＥＸフィールド１０１８）と、そのＵＳＣに関連する１つまたは複数のＥＢＮのインデックス（ＥＢＮ＿ＩＮＤＥＸフィールド１０２０）とを含む。
【００７９】
図１１は、図５のＲＡＭインデックス・テーブル５２４の例示的レイアウトである。ＲＡＭインデックス・テーブル５２４内には、ＲＡＭ  Ｐテーブル５２２内のトラッピング・セット・プロファイルごとに１つのレコードがある。ＲＡＭインデックス・テーブル５２４内の各レコードは、単一のフィールドＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴ  １１０２を含む。ＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴ  １１０２は、ＲＡＭ  Ｐテーブル５２２内の特定のトラッピング・セット・プロファイルの始めへのポインタである、すなわち、ＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴ  １１０２は、トラッピング・セット・プロファイル・プライマリ・レコードの図１０のレコード番号１００２を含む。ＲＡＭインデックス・テーブル５２４内のレコードは、優位性によってソートされ、その結果、ＲＡＭインデックス・テーブル５２４内の最初のレコードは、ＲＡＭ  Ｐテーブル５２２内の最も支配的なトラッピング・セットをポイントし、ＲＡＭインデックス・テーブル５２４内の最後のレコードは、ＲＡＭ  Ｐテーブル５２２内の最も支配的でないレコードをポイントするようになる。
【００８０】
図１２は、図５のＬＤＰＣ復号システム５００によって使用される例示的プロセス１２００の流れ図である。処理は、ステップ１２０２で開始され、ステップ１２０４すなわち、図５のＬＤＰＣ復号器５０２によるＬｃｈ値のＬＤＰＣ復号に進む。ステップ１２０４でのＬＤＰＣ復号がＤＣＣＷを作る場合には、プロセス１２００は、ステップ１２１８で終了する。そうでない場合には、処理は、ステップ１２０６すなわち、ＴＳ−ＲＯＭリスト復号（図５のポストプロセッサ５０４によって実行される）に進む。
【００８１】
ステップ１２０６がＤＣＣＷを作る場合には、プロセス１２００は、ステップ１２１８で終了する。そうでない場合には、処理は、ステップ１２０８すなわち、ＴＳ−ＲＡＭリスト復号（図５のポストプロセッサ５０４によって実行される）に進む。ステップ１２０８がＤＣＣＷを作る場合には、プロセス１２００は、ステップ１２１８で終了する。そうでない場合には、処理は、１つまたは複数の追加の後処理方法１２１０、１２１２、…、１２１４（図５のポストプロセッサ５０４によって実行される）に進み、これらは、類似する形で動作する。
【００８２】
ＴＳ−ＲＡＭリスト復号１２０８または追加の後処理方法１２１０、１２１２、…、１２１４のいずれかがＤＣＣＷを作る場合には、処理はステップ１２１６に進み、ここで、図５のＴＳ−ＲＡＭ  ５２０が、おそらくはＴＳ−ＲＡＭアップデータ５０６によって更新される。その後、処理はステップ１２１８で終了する。
【００８３】
図１２は、後処理方法１２０７〜１２１４の１つの可能なシーケンシングを示す。後処理方法のほとんどすべてのシーケンスを使用することができるが、いくつかのシーケンスは、他のシーケンスより実用的である。たとえば、ＲＯＭに既に格納されているトラッピング・セットがＲＡＭ内で重複しないことを保証するために、ＴＳ−ＲＯＭリスト復号をＴＳ−ＲＡＭリスト復号の前にシーケンシングすることが望ましい。
【００８４】
ＴＳ−ＲＯＭリスト復号
図１３は、図５のポストプロセッサ５０４によって実施される図１２の例示的なＴＳ−ＲＯＭリスト復号プロセス１２０６の流れ図である。処理は、ステップ１３０２で開始され、ステップ１３０４に進み、ここで、プロセス１２０６は、図１２のＬＤＰＣ復号器１２０４から受け取られたベクトル
【数５６】
0005276173.tif 000057
内で観察されたＵＳＣの個数ｂｏｂｓｅｒｖｅｄが、０を超え、プロセス１２０６によって効率的に処理できるＵＳＣの最大個数ｂｍａｘ未満であるかどうかを判定する。ｂｏｂｓｅｒｖｅｄ＝０の場合には、ベクトル
【数５７】
0005276173.tif 000058
内にＵＳＣはなく（すなわち、
【数５８】
0005276173.tif 000059
は、ニア・コードワード・ミスコレクションである）、したがって、照合すべきトラッピング・セットはない。ステップ１３０４が偽に評価される場合には、プロセス１２０６は終了する。そうでない場合には、処理は、ステップ１３０６に継続される。
【００８５】
ステップ１３０６では、復号器の現在の状態を格納し、状態１というラベルを付ける。次に、処理はステップ１３０８に継続され、ここで、観察されたＵＳＣを、まず復号レイヤによって、次にインデックスによってソートする。次に、ステップ１３１０で、次の４つの値を図５のＢテーブル５１２からフェッチし、格納する。
（１）ｂ＝ｂｏｂｓｅｒｖｅｄについて、図７のＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴフィールド７０４、
（２）ｂ＝ｂｏｂｓｅｒｖｅｄ＋１について、図７のＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴフィールド７０４、
（３）ｂ＝ｂｏｂｓｅｒｖｅｄについて、図７のＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴフィールド７０６、および
（４）ｂ＝ｂｏｂｓｅｒｖｅｄについて、図７のＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳフィールド７０８。
第１の値は、プロセス１２０６に、図５のＰテーブル５１４内のどこで一致するトラッピング・セット情報の検索を開始すべきか（すなわち、ＵＳＣインデックスおよびＥＢＮインデックス）を指示し、第２の値は、プロセス１２０６に、いつその検索を終了すべきかを指示する。同様に、第３および第４の値は、プロセス１２０６に、拡張情報（すなわち、ＭＳＣインデックス）の検索を開始すべき場所および終了すべき場所を指示する。
【００８６】
したがって、たとえば、ｂｏｂｓｅｒｖｅｄ＝５の場合には、プロセス１２０６は、ｂ＝５およびｂ＝６について図７のＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴフィールド７０４の値をフェッチし、ｂ＝５について図７のＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴフィールド７０６の値および図７のＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳフィールド７０８の値をフェッチする。
【００８７】
次に、ステップ１３１２で、プロセス１２０６は、図５のＰテーブル５１４を選択し、ｂ＝ｂｏｂｓｅｒｖｅｄのＰＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴの格納された値によって示されるアドレスに行く。次に、ステップ１３１４で、ＴＳ−ＲＯＭから、観察されたＵＳＣと一致するトラッピング・セットを検索する。
【００８８】
図１４は、図１３の例示的なＴＳ−ＲＯＭ検索プロセス１３１４の流れ図である。プロセス１３１４は、ステップ１４０２で開始され、ステップ１４０４で、観察されたＵＳＣの同形一致である図５のＰテーブル５１４内の次のレコードを検索する。観察されたＵＳＣの特定のセットの同形一致は、ＵＳＣの個数およびこれらのＵＳＣの間の距離が観察されたＵＳＣと同一であるトラッピング・セットである。したがって、観察されたＵＳＣが［１，３，１０］である場合には、［１，３，１０］は一致であり、［２，４，１１］は同形一致であり、［３，５，１２］、［４，６，１３］なども同形一致である。一致が見つからない場合には、プロセス１３１４は、一致なしの状況１４０６で終了する。
【００８９】
そうではなく、ステップ１４０４で一致が見つかる場合には、ステップ１４０８で、一致するＰテーブル・レコードの図６のＥＢＮ＿ＩＮＤＥＸフィールド６０８の値を格納する。ＥＢＮ＿ＩＮＤＥＸフィールドは、この一致するトラッピング・セットに関連する１つおよびおそらくは２つの誤りのあるビットノードのインデックスを格納する。
【００９０】
次に、プロセス１３１４は、すべての拡張情報すなわち、この一致するトラッピング・セット内の誤って満足されたチェックノード（ＭＳＣ）に関連するＥＢＮのインデックスを突き止めることを試みる。拡張情報は、ＥＩテーブル５１８内で保持される。しかし、拡張情報は、Ｐテーブル５１４内に格納されたすべてのトラッピング・セットについて保持されるのではなく、各ｂ範囲内のトラッピング・セットのサブセットについてのみ保持される。そのサブセットは、特定のｂ範囲内のより支配的なトラッピング・セットすなわち、エラーフロア特性に対するより大きい影響を有するトラッピング・セットに対応する。上で述べたように、Ｐテーブル５１４内では、特定のｂ範囲内のトラッピング・セットが、優位性によってソートされ、したがって、拡張情報は、そのｂ範囲内の最初のｘ個のレコードのみについて保持される。ＥＩテーブル５１８内の各ｂ範囲の始めおよび終りは、Ｂテーブル５１２内のフィールド、ＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴ  ７０６およびＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳ  ７０８によって示される。
【００９１】
プロセス１３１４は、ＲＯＭ  Ｐテーブル５１４のレコードから検索する時に、トラッピング・セットの内部カウントを維持する。したがって、たとえば、プロセス１３１４が、図６のＰテーブル５１４内のｂ＝２トラッピング・セットから検索している場合に、プロセス１３１４は、レコード０および１をトラッピング・セット０（たとえば、図６のトラッピング・セット６１０）として、レコード２および３をトラッピング・セット１（たとえば、図６のトラッピング・セット６１２）としてなど、識別する。このトラッピング・セット番号を、ＴＳＮＵＭと称する。
【００９２】
ステップ１４１０で、ＴＳＮＵＭを、図１３のステップ１３１０で格納されたＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳフィールドの値と比較する。ＴＳＮＵＭがＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳの値より大きい場合には、拡張情報は使用可能ではなく、プロセス１３１４は、一致、拡張情報なしの状況１４１２で終了する。
【００９３】
そうではなく、ステップ１４１０で、ＴＳＮＵＭがＮＵＭ＿ＥＴＡＢＬＥ＿ＥＮＴＲＩＥＳの格納された値以下であることがわかる場合には、拡張情報が、この一致するトラッピング・セットについて存在する。ステップ１４１４で、ＴＳＮＵＭをＥＴＡＢＬＥ＿ＳＴＡＲＴ＿ＯＦＦＳＥＴの格納された値に加算して、変数ＥＴＡＢＬＥ＿ＥＮＴＲＹ＿ＡＤＤＲＥＳＳを作る。
【００９４】
次に、ステップ１４１６で、プロセス１３１４は、図５のＥテーブル５１６を選択し、変数ＥＴＡＢＬＥ＿ＥＮＴＲＹ＿ＡＤＤＲＥＳＳの値と等しいアドレスを有するレコードに行き、図８のＥＩＴＡＢＬＥ＿ＳＴＡＲＴ＿ＡＤＤＲＥＳＳフィールド８０４および図８のＥＩＴＡＢＬＥ＿ＥＮＤ＿ＡＤＤＲＥＳＳフィールド８０６の値を格納する。
【００９５】
次に、ステップ１４１８で、プロセス１３１４は、図５のＥＩテーブル５１８を選択し、格納されたＥＩＴＡＢＬＥ＿ＳＴＡＲＴ＿ＡＤＤＲＥＳＳ値とＥＩＴＡＢＬＥ＿ＥＮＤ＿ＡＤＤＲＥＳＳ値との間のすべてのレコードの、図９のＢＬＯＣＫ＿ＣＯＬＵＭＮフィールド９０４および図９のＢ＿ＩＮＤＥＸフィールド９０６の値を格納する。最後に、プロセス１３１４は、一致、拡張情報ありの状況１４２０で終了する。
【００９６】
図１３に戻って、ステップ１３１４が、一致なしの状況で終了する場合には、プロセス１２０６は、ステップ１３１６で終了する。
【００９７】
ステップ１３１４が、一致、拡張情報なしの状況で終了する場合には、プロセス１２０６は、このトラッピング・セットに関連するＵＳＣインデックスおよびいくつかのＥＢＮインデックスを、拡張情報なしで（すなわち、ＭＳＣに関連するＥＢＮのインデックスなしで）処理する。この場合に、ステップ１３１８で、これらのＥＢＮインデックスのビットノードを反転し、ステップ１３２０で、反復ＬＤＰＣ復号を実行する。ステップ１３２０の処理は、復号器初期化ステップ３０４および初期症候群チェック・ステップ３０６がスキップされることを除いて、図３のプロセス３００と同一である。ステップ１３２０がＤＣＣＷに収束する場合には、プロセス１２０６は、ステップ１３１６で終了する。そうでない場合には、ステップ１３２２で、復号器を状態１に復元し、次の一致するトラッピング・セットを、ステップ１３１４で検索する。
【００９８】
ステップ１３１４が、一致、拡張情報ありの状況で終了する場合には、プロセス１２０６は、一致するトラッピング・セットに関連するすべてのＥＢＮのインデックスを有する。この場合には、確率伝搬（たとえば、図３のステップ３１０および３１２）を実行する必要はない。そうではなく、ステップ１３２４で、ＥＢＮを反転し、結果のベクトル
【数５９】
0005276173.tif 000060
を、症候群チェック１３２６にサブミットする。ベクトル
【数６０】
0005276173.tif 000061
が、ステップ１３２６で症候群チェックに不合格である場合には、プロセス１２０６は、ステップ１３２２に進む。そうではなく、ベクトル
【数６１】
0005276173.tif 000062
が症候群チェックに合格する（すなわち、ベクトル
【数６２】
0005276173.tif 000063
が、有効な符号語である）場合には、ステップ１３２８で、ＣＲＣチェックをベクトル
【数６３】
0005276173.tif 000064
に対して実行して、これが実際に正しい符号語であるかどうかを判定する。ベクトル
【数６４】
0005276173.tif 000065
がＣＲＣチェック１３２８に合格する（すなわち、ベクトル
【数６５】
0005276173.tif 000066
がＤＣＣＷである）場合には、プロセス１２０６は、ステップ１３１６で終了する。ベクトル
【数６６】
0005276173.tif 000067
がＣＲＣチェック１３２８に不合格である場合には、プロセス１２０６は、ステップ１３２２に進む。
【００９９】
ＴＳ−ＲＡＭリスト復号
図５のポストプロセッサ５０４によって利用されるもう１つのＰＰ方法が、図１２のＴＳ−ＲＡＭリスト復号１２０８すなわち、ランダムアクセス・メモリなどの揮発性メモリに格納されたトラッピング・セット情報を使用するトラッピング・セットのリスト復号である。ＴＳ−ＲＡＭリスト復号は、図５のＲＡＭ  Ｐテーブル５２２が選択されたトラッピング・セットのＵＳＣおよびＥＢＮの情報を格納するという点で、ＴＳ−ＲＯＭリスト復号に似ている。しかし、ＲＯＭ  Ｐテーブル５１４とは異なって、ＲＡＭ  Ｐテーブル５２２は、図５のＴＳ−ＲＡＭアップデータ５０６によってランタイム中に変更される。したがって、最も重要な情報だけ、たとえばＵＳＣインデックスおよびＥＢＮインデックスだけが、格納される。拡張情報（たとえば、図５のＥＩテーブル５１８）は、ＴＳ−ＲＡＭ内では維持されない。
【０１００】
プロファイルも、ＲＡＭ  Ｐテーブル５２２内にはどのような形であれソートされない。そうではなく、図５の別々のＲＡＭインデックス・テーブル５２４は、優位性によってソートされた、ＲＡＭ  Ｐテーブル５２２内に格納されたトラッピング・セット・プロファイルのアドレスのリストを維持する。
【０１０１】
図１５は、図１２の例示的なＴＳ−ＲＡＭリスト復号プロセス１２０８の流れ図である。処理は、ステップ１５０２で開始され、ステップ１５０４に進み、このステップ１５０４は、目的および動作において図１３のステップ１３０４と同一である。ステップ１５０４が偽に評価される場合には、プロセス１２０８は、ステップ１５０６で終了し、そうでない場合には、処理は、ステップ１５０８に継続され、ここで、現在の復号器状態を記録し、状態１というラベルを付ける。その後、処理はステップ１５１０に継続される。
【０１０２】
ステップ１５１０では、プロセス１２０８は、図５のＲＡＭ  Ｐテーブル５２２内の最も支配的なトラッピング・セット・プロファイルに行く。具体的に言うと、ＲＡＭインデックス・テーブル５２４は、優位性によってＲＡＭ  Ｐテーブル５２２内のプロファイルをランキングするので、プロセス１２０８は、ＲＡＭインデックス・テーブル５２４内の最初のレコードに行き、図１１のＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴフィールド１１０２の値を取り出す。次に、プロセス１２０８は、ＲＡＭ  Ｐテーブル５２２内のポインタをその格納されたオフセット値に移動する。
【０１０３】
ステップ１５１２で、プロセス１２０８は、ＴＳ−ＲＡＭ検索が実行された総数すなわち、プロセス１２０８が実行された総回数を記憶するグローバル変数ＲＡＭ＿ＳＥＡＲＣＨ＿ＣＯＵＮＴを増分する。また、ステップ１５１２で、プロセス１２０８は、観察されたＵＳＣの同形一致について、ＲＡＭインデックス・テーブル５２４によって示される順序すなわち減少する優位性の順で、ＲＡＭ  Ｐテーブル５２２内のプロファイルを調べる。一致が見つからない場合には、処理はステップ１５１４に継続される。
【０１０４】
そうではなく、ステップ１５１２で一致が見つかる場合には、ステップ１５１６で、一致したプロファイルの図１０のＬＡＳＴ＿ＨＩＴ＿ＮＵＭフィールド１０１２に、グローバル変数ＲＡＭ＿ＳＥＡＲＣＨ＿ＣＯＵＮＴの値をセットし、図１０のＨＩＴ＿ＣＯＵＮＴＥＲフィールド１０１４を１つ増分する。次に、ステップ１５１８で、図１０のＥＢＮ＿ＩＮＤＥＸフィールド１０２０の値を格納する。ステップ１５２０で、ＥＢＮ＿ＩＮＤＥＸ値に配置されたビットノードを反転し、ステップ１５２２で、ＬＤＰＣ復号を実行する。ステップ１５２２は、図１３のステップ１３２０と同一である。復号プロセス１５２２がＤＣＣＷに収束する場合には、処理はステップ１５１４に継続され、そうでない場合には、ステップ１５２４で、復号器を状態１にリセットし、その後、処理は、ステップ１５１２に継続され、ここで、別の同形一致をＰテーブル５２２内で検索する。
【０１０５】
ステップ１５１４では、プロセス１２０８は、図１１のＲＡＭインデックス・テーブル５２４を更新する。具体的に言うと、ステップ１５１４で、ＲＡＭ  Ｐテーブル５２２内のフィールド、たとえばＬＡＳＴ＿ＨＩＴ＿ＮＵＭ  １０１２、ＨＩＴ＿ＣＯＵＮＴＥＲフィールド１０１４、ＵＳＣノードの個数フィールド１００８、およびＥＢＮの個数フィールド１０１０の任意の組合せに基づいて、ＲＡＭ  Ｐテーブル５２２内のすべてのＴＳ−ＲＡＭプロファイルをソートする。次に、すべてのソートされたプロファイルのアドレスすなわちすべてのプライマリ・レコードのレコード番号１００２を、図１１のＲＡＭインデックス・テーブル５２４内にレコードとして格納する。プロファイル・アドレスは、それらがステップ１５１４でソートされたのと同一の順序（たとえば、最も支配的から最も少なく支配的へ）でＲＡＭインデックス・テーブル５２４に格納される。
ステップ１５１４が完了した後に、処理は、ステップ１５０６で終了する。
【０１０６】
ＴＳ−ＲＡＭアップデータ
図１２のプロセス１２００の議論で説明したように、ＴＳ−ＲＯＭリスト復号１２０６以外の任意の後処理方法がＤＣＣＷに達する場合に、それが、新しいトラッピング・セットが発見されたことを意味する場合がある。そうである場合には、ステップ１２１６が、その新しいトラッピング・セットを図５のＲＡＭ  Ｐテーブル５２２に追加することを試みる場合がある。
【０１０７】
一実施形態では、ステップ１２１６は、支配的トラッピング・セットをＴＳ−ＲＡＭ  ５２０内で保持するための、低い複雑さのプロセスである。具体的に言うと、この実施形態では、ステップ１２１６は、図４のＤＴＳ−Ｎコンパイラ４２２によって実行される計算などの支配的トラッピング・セットを先験的に判定するための網羅的計算を実行するのではなく、その代わりに、（ｉ）１つまたは複数の要因、たとえば、トラッピング・セットが最後に一致した時以降にＴＳ−ＲＡＭが何回検索されたか、トラッピング・セットが一致した総回数、ＵＳＣの個数、ＥＢＮの個数などの任意の組合せに基づいてＴＳ−ＲＡＭトラッピング・セットをランキングし、次に、（ｉｉ）新たに発見されたトラッピング・セットのための余地を作るために、最も低いランキングのトラッピング・セットを追い出す。これらの要因を使用するＴＳ−ＲＡＭ  ５２０内のトラッピング・セットのランキングは、通常、オフライン・シミュレーション・ツール（たとえば、図４のコンパイラ４２２）によって実行される分析よりかなりより少なく複雑である。
【０１０８】
図１６は、図１２の例示的なＴＳ−ＲＡＭ更新プロセス１２１６の流れ図である。処理は、ステップ１６０２で開始され、ステップ１６０４に進み、ここで、ＤＣＣＷが図１２のＴＳ−ＲＡＭリスト復号プロセス１２０８によって生成されたかどうかを判定する。そうである場合には、トラッピング・セット・プロファイルをＴＳ−ＲＡＭに追加する必要はなく、プロセス１２１６は、ステップ１６０８で終了する。
【０１０９】
そうではなく、ステップ１６０４がｎｏ／偽に評価される場合には、これは、ＴＳ−ＲＯＭリスト復号またはＴＳ−ＲＡＭリスト復号以外のある後処理方法がＤＣＣＷに達し、したがって、新しいトラッピング・セットが発見され、ＲＡＭに付加されなければならないことを意味する。ステップ１６１０で、トラッピング・セット・プロファイルを生成する。トラッピング・セット・プロファイルは、トラッピング・セットＵＳＢのインデックスと、これらのＵＳＢに関連するＥＢＮのインデックスとを含む。ＵＳＢインデックスは、図５のＬＤＰＣ復号器５０２によって既に生成済みである。ＥＢＮインデックスを生成するために、ステップ１６１０で、ポストプロセッサ５０４によって生成されたＤＣＣＷ
【数６７】
0005276173.tif 000068
を、ＬＤＰＣ復号器５０２によって生成されたベクトル
【数６８】
0005276173.tif 000069
と比較する。
【０１１０】
ステップ１６１２で、新しいトラッピング・セット・プロファイルを付加するのに十分な空き空間があるかどうかを判定する。そうである場合には、ステップ１６１４で、新しいトラッピング・セット・プロファイルを、ＲＡＭ  Ｐテーブル５２２に付加し、プロセス１２１６は、ステップ１６１６に進む。
【０１１１】
しかし、ステップ１６１２で、新しいトラッピング・セット・プロファイルを付加するのに十分な空き空間がＲＡＭ  Ｐテーブル５２２内にない場合には、ステップ１６１８で、最も低いランキングの追出しに適するトラッピング・セット・プロファイルを追い出す。この例では、プロファイルの追出し適格性は、そのプロファイルが最後に一致した時以降にＲＡＭが検索された回数すなわち、グローバル変数ＲＡＭ＿ＳＥＡＲＣＨ＿ＣＯＵＮＴの値からプロファイルのＬＡＳＴ＿ＨＩＴ＿ＮＵＭフィールドの値を引いたものによって決定される。介在する検索の回数が、指定されたしきい値より多い場合には、そのプロファイルは、追出しに適する。すべてのプロファイルが、まず追出し適格性によってランキングされると仮定すると、すべての追出しに適するレコードは、図１１のＲＡＭインデックス・テーブル５２４の終りにある。
【０１１２】
したがって、ステップ１６１８では、ＲＡＭインデックス・テーブル５２４内の最後のレコードを選択し、ＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴフィールド１１０２の値を取り出す。ＲＡＭ  Ｐテーブル５２２内で格納されたオフセット値（取り出されたＲＡＭ＿ＰＴＡＢＬＥ＿ＯＦＦＳＥＴ値によって示される）に配置されたプロファイルが、追出しに適する場合には、ＲＡＭ  Ｐテーブル５２２内の格納されたオフセット値に配置されたプライマリ・レコードおよび関連するセカンダリ・レコードが削除される。ステップ１６２０で、ＲＡＭインデックス・テーブルＭＳＢを更新し、その後、制御はステップ１６１２にループ・バックし、ここで、新しいトラッピング・セット・プロファイルを付加するのに十分な空き空間がＲＡＭ  Ｐテーブル５２２内にあるかどうかを判定する。ステップ１６２０の処理は、図１５のステップ１５１４の処理と同一である。
【０１１３】
そうではなく、ステップ１６１８で、最低ランキングのプロファイルが追出しに適さない場合には、処理は、ステップ１６１６に継続される。ステップ１６１６では、ＲＡＭインデックス・テーブル５２４を更新し、処理は、ステップ１６０８で終了する。ステップ１６１６の処理は、図１５のステップ１５１４の処理と同一である。
【０１１４】
本発明を、ＬＤＰＣコーディングおよび復号を実施するハード・ディスク・ドライブの文脈で説明したが、本発明は、それに限定はされない。一般に、本発明を、ＬＤＰＣコーディングおよび復号を用いる任意の適切な通信経路内で実施することができる。
【０１１５】
さらに、上で使用された例示的な確率伝搬アルゴリズムは、オフセットｍｉｎ−ｓｕｍアルゴリズム（ＯＭＳ）であるが、本発明は、それに限定はされず、本発明を、任意の確率伝搬変形、たとえば、ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム（ＳＰＡ）またはＢａｈｌ−Ｃｏｃｋｅ−Ｊｅｌｉｎｅｋ−Ｒａｖｉｖ（ＢＣＪＲ）アルゴリズムと共に使用することができる。
【０１１６】
さらに、上で使用された確率伝搬の例は、すべてのチェックノードが単一のチェックノード更新ステップ中に更新され、その後、すべてのビットノードが単一のビットノード更新ステップで更新される、特定の復号スケジュール（フラッディング・スケジュール）を使用したが、本発明は、それには限定されず、本発明を、任意の復号スケジュール、たとえば、ローシリアルスケジュール、カラムシリアルスケジュール、およびローカラム・シリアルスケジュールと共に使用することができる。
【０１１７】
さらに、上で使用された例示的ＬＤＰＣ復号器は、非階層復号器であったが、本発明は、それに限定はされず、本発明を、階層復号器と非階層復号器との両方と共に使用することができる。
【０１１８】
さらに、上で与えた例示的ＴＳ−ＲＡＭ実施態様は、トラッピング・セット・プロファイルをＨＤドライブの読取りチャネル内のＲＡＭに格納すると仮定したが、本発明は、それに限定はされない。ＲＡＭ  Ｐテーブル（たとえば、図５の５２２）を、ＨＤドライブのプラッタに格納するか、フラッシュ・メモリなどの別々のメモリ内に格納することもできる。
【０１１９】
さらに、上で与えた例示的ＴＳ−ＲＯＭ実施態様は、読取り専用メモリの文脈で説明されたが、本発明は、それに限定はされない。一般に、本明細書と特許請求の範囲との両方で使用される時に、用語「ＲＯＭ」は、そのデバイス内のデータを変更できるか否かにかかわりなく、静的ＴＳプロファイル・データを格納するすべてのデータストレージ・デバイスを指すと解釈されなければならない。
【０１２０】
さらに、本発明の実施形態を、ＬＤＰＣ符号の文脈で説明したが、本発明は、それに限定はされない。本発明の実施形態を、グラフによって定義できる任意の符号、たとえば、トルネード符号、構造化ＩＲＡ符号のために実施することができる。というのは、これが、トラッピング・セットに苦しむグラフ定義される符号であるからである。
【０１２１】
本発明を、対数尤度比の受取りに関して説明したが、本発明は、それに限定はされない。尤度比などの他のソフト値または硬判定値が処理される、本発明の実施形態を想定することができる。
【０１２２】
本発明を、方法およびこれらの方法を実践する装置の形で実施することができる。本発明を、磁気記録媒体、光記録媒体、ソリッド・ステート・メモリ、フロッピ・ディスケット、ＣＤ−ＲＯＭ、ハード・ドライブ、または任意の他の機械可読記憶媒体などの有形の媒体内で実施されるプログラム・コードの形で実施することもでき、プログラム・コードがコンピュータなどの機械にロードされ、その機械によって実行される時に、その機械は、本発明を実践する装置になる。本発明を、記憶媒体に格納される、機械にロードされ、かつ／またはこれによって実行される、あるいは電気配線またはケーブリングを介する、光ファイバを介する、もしくは電磁放射を介するなどのある伝送媒体または搬送波を介して伝送されるいずれであれ、プログラム・コードの形で実施することもでき、プログラム・コードがコンピュータなどの機械にロードされ、その機械によって実行される時に、その機械は、本発明を実践する装置になる。汎用プロセッサ上で実施される時に、プログラム・コード・セグメントは、プロセッサと組み合わさって、特定の論理回路に類似して動作する独自のデバイスをもたらす。
【０１２３】
そうではないと明示的に述べられない限り、各数値および範囲は、単語「約」（“ａｂｏｕｔ”ｏｒ“ａｐｐｒｏｘｉｍａｔｅｌｙ”）が値または範囲の値に先行するかのように近似として解釈されなければならない。
【０１２４】
さらに、添付の特許請求の範囲に表された本発明の範囲から逸脱せずに、本発明の性質を説明するために説明され、図示された部分の詳細、材料、および配置におけるさまざまな変更を当業者が行えることを理解されたい。
【０１２５】
特許請求の範囲での図面番号および／または図面符号の使用は、特許請求の範囲の解釈を容易にするために請求される主題の１つまたは複数の可能な実施形態を識別することを意図されたものである。そのような使用を、これらの特許請求の範囲の範囲を対応する図面に示された実施形態に必ず限定するものとして解釈してはならない。
【０１２６】
本明細書に示された例示的方法のステップが、必ずしも説明された順序で実行されることを必要とせず、そのような方法のステップの順序が、単に例示と理解されなければならないことを理解されたい。同様に、本発明のさまざまな実施形態と一貫する方法において、追加ステップをそのような方法に含めることができ、ある種のステップを削除しまたは組み合わせることができる。
【０１２７】
次の方法請求項の要素は、存在する場合に、対応するラベル付けを伴って特定のシーケンスで詳説されるが、請求項詳説が、これらの要素の一部またはすべてを実施するための特定のシーケンスを他の形で暗示しない限り、これらの要素は、必ずしもその特定のシーケンスで実施されることに限定はされないことが意図されている。
【０１２８】
本明細書での「一実施形態」（“ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ”ｏｒ“ａｎ  ｅｍｂｏｄｉｍｅｎｔ”）への言及は、その実施形態に関連して説明される特定の特徴、構造、または特性を、本発明の少なくとも１つの実施形態に含めることができることを意味する。本明細書のさまざまな場所での句「一実施形態で」の出現は、必ずしもすべてが同一の実施形態に言及するものではなく、必ずしも他の実施形態と相互に排他的な別々のまたは代替の実施形態でもない。同一のことが、用語「実施態様」にもあてはまる。
【図１】
0005276173.tif 000070
【図２】
0005276173.tif 000071
【図３】
0005276173.tif 000072
【図４】
0005276173.tif 000073
【図５】
0005276173.tif 000074
【図６】
0005276173.tif 000075
【図７】
0005276173.tif 000076
【図８】
0005276173.tif 000077
【図９】
0005276173.tif 000078
【図１０】
0005276173.tif 000079
【図１１】
0005276173.tif 000080
【図１２】
0005276173.tif 000081
【図１３】
0005276173.tif 000082
【図１４】
0005276173.tif 000083
【図１５】
0005276173.tif 000084
【図１６】
0005276173.tif 000085