(57)【特許請求の範囲】
【請求項１】
符号化符号語を復号するための方法であって、
（ａ）前記符号化符号語に対して、対数尤度比（ＬＬＲ）値の第１の組を生成するステップであって、各ＬＬＲ値が硬判定値および信頼値を有する、ステップと、
（ｂ）ＬＬＲ値の前記第１の組に基づいて、前記符号化符号語に対して復号を実行して、ｂ個の非満足チェック・ノード（ＵＳＣ）を有する復号符号語を生成するステップと、
（ｃ）前記符号化符号語に対して、ＬＬＲ値の第２の組を生成するステップであって、少なくとも１つのＬＬＲ値がＵＳＣの前記個数ｂに基づいた信頼値を有する、ステップと、
（ｄ）ＬＬＲ値の前記第２の組に基づいて、前記符号化符号語に対して復号を実行するステップとを具備する方法。
【請求項２】
前記符号化符号語が、ＬＤＰＣ符号語である、請求項１に記載の方法。
【請求項３】
前記第２の組の各ＬＬＲ値が、ＵＳＣの前記個数ｂに等しい信頼値を有する、請求項１に記載の方法。
【請求項４】
ステップ（ｃ）およびステップ（ｄ）が、第１のターボ等化方法の単一の繰り返しに対応する、請求項１に記載の方法。
【請求項５】
前記第１のターボ等化方法の１つまたは複数の追加の繰り返しをさらに具備する、請求項４に記載の方法。
【請求項６】
ステップ（ａ）およびステップ（ｂ）が、第２のターボ等化方法の単一の繰り返しに対応し、前記第１の組内の前記ＬＬＲ値の前記信頼値が、前記符号化符号語のいかなる先行する復号からのＵＳＣの前記個数ｂに基づかない、請求項４に記載の方法。
【請求項７】
（１）前記符号化符号語に対して、ＬＬＲ値の第３の組を生成するステップであって、前記信頼値のいずれもが、前記符号化符号語のいかなる先行する復号からのＵＳＣの前記個数ｂに基づかない、ステップと、
（２）ＬＬＲ値の前記第３の組に基づいて、前記符号化符号語に対して復号を実行するステップと、
を含む第２のターボ等化方法の１つまたは複数の繰り返しをさらに具備する、請求項４に記載の方法。
【請求項８】
前記方法が、前記第１のターボ等化方法の繰り返しの第１の組を前記第２のターボ等化方法の繰り返しの第２の組とインタリーブするステップを具備し、
第１の組の各々が、前記第１のターボ等化方法の１つまたは複数の繰り返しを含み、
第２の組の各々が、前記第２のターボ等化方法の１つまたは複数の繰り返しを含む、
請求項７に記載の方法。
【請求項９】
ステップ（ｃ）が、
（ｃ１）ＵＳＣの前記個数ｂを指定された閾値と比較するステップと、
（ｃ２）ＵＳＣの前記個数ｂが前記指定された閾値よりも大きくない場合、ＵＳＣの前記個数ｂに基づいた信頼値を有するように前記少なくとも１つのＬＬＲ値を生成するステップと、
を含む、請求項１に記載の方法。
【請求項１０】
符号化符号語を復号するための装置であって、
（ａ）前記符号化符号語に対して、対数尤度比（ＬＬＲ）値の１つまたは複数の組を生成する手段であって、各ＬＬＲ値が硬判定値および信頼値を有する、手段と、
（ｂ）ＬＬＲ値の前記１つまたは複数の組の１つに基づいて、前記符号化符号語に対して復号を実行する手段とを備え、
前記手段（ａ）は、前記符号化符号語に対して、ＬＬＲ値の第１の組を生成するように適合され、
前記手段（ｂ）は、ｂ個の非満足チェック・ノード（ＵＳＣ）を有する復号符号語を生成するために、ＬＬＲ値の前記第１の組に基づいて、前記符号化符号語に対して復号を実行するように適合され、
前記手段（ａ）は、前記符号化符号語に対して、ＬＬＲ値の第２の組を生成するように適合され、少なくとも１つのＬＬＲ値がＵＳＣの前記個数ｂに基づいた信頼値を有し、
前記手段（ｂ）は、ＬＬＲ値の前記第２の組に基づいて、前記符号化符号語に対して復号を実行するように適合される、装置。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の相互参照
本出願は、整理番号０８−１０５７−ＰＲとして２００９年３月５日に出願された米国仮出願第６１／１５７，６７１号の利益を主張し、同出願の教示は、その全体が参照により本明細書に組み込まれる。
【０００２】
本出願の主題は、（１）整理番号０８−０２４１として２００８年１２月１２日に出願されたＰＣＴ出願第ＰＣＴ／ＵＳ０８／８６５２３号の主題、（２）整理番号０８−１２９３として２００８年１２月１２日に出願されたＰＣＴ出願第ＰＣＴ／ＵＳ０８／８６５３７号の主題、および（３）整理番号０８−０２４８として２００９年３月１０日に出願された米国出願第１２／４０１，１１６号の主題に関し、それらすべての出願の教示は、その全体が参照により本明細書に組み込まれる。
【０００３】
本発明は、デジタル信号処理に関し、詳細には、低密度パリティ検査（ＬＤＰＣ：ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ）符号化として知られるデータ符号化方法に関する。
【背景技術】
【０００４】
通信は、通信チャネルを介した、送信機による受信機への情報の伝送である。現実世界では、通信チャネルは、雑音のあるチャネルであり、送信機から送信された情報の歪んだバージョンを受信機に提供する。ハードディスク（ＨＤ）ドライブは、そのような雑音のあるチャネルの１つであり、送信機から情報を受け取り、その情報を保存し、その後、その情報の多かれ少なかれ歪んだコピーを受信機に提供する。
【０００５】
ＨＤドライブなどの通信チャネルによって導入された歪みは、チャネル誤りを引き起こすのに十分な大きさであることがあり、すなわち、その場合は、受信機は、チャネル入力信号が０であるときにチャネル出力信号を１と解釈し、または１であるときに０と解釈する。チャネル誤りは、スループットを低下させ、したがって、望ましくない。そのため、チャネル誤りを検出および／または訂正するツールが今現在も必要とされている。低密度パリティ検査（ＬＤＰＣ）符号化は、チャネル誤りの検出および訂正のための１つの方法である。
【０００６】
ＬＤＰＣ符号は、信号対雑音比（ＳＮＲ：ｓｉｇｎａｌ−ｔｏ−ｎｏｉｓｅ  ｒａｔｉｏ）が低い適用例に対して非常に低いビット誤り率（ＢＥＲ：ｂｉｔ−ｅｒｒｏｒ  ｒａｔｅ）を達成できる、知られた近シャノン限界符号（ｎｅａｒ−Ｓｈａｎｎｏｎ−ｌｉｍｉｔ  ｃｏｄｅ）の中に含まれる。ＬＤＰＣ復号は、並列化、低い実装の複雑さ、短い復号待ち時間に加えて、高いＳＮＲにおけるさほど厳しくない誤りフロア（ｅｒｒｏｒ−ｆｌｏｏｒ）に対するその可能性によって際立っている。ＬＤＰＣ符号は、実質的にすべての次世代通信規格のために考えられている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国仮出願第６１／１５７，６７１号
【特許文献２】ＰＣＴ出願第ＰＣＴ／ＵＳ０８／８６５２３号
【特許文献３】ＰＣＴ出願第ＰＣＴ／ＵＳ０８／８６５３７号
【特許文献４】米国出願第１２／４０１，１１６号
【非特許文献】
【０００８】
【非特許文献１】A. C. Douillard、A. Picart、M. Jezequel、P. Didier、C. Berrou、A. Glavieux、「Iterative correction of intersymbol interference: Turbo-equalization」、Eur. Trans. Commun.、vol. 6,、507〜511頁、1995年9月〜10月
【非特許文献２】Yeap, B. L.、Liew, T. H.、Hamorsky, J.、Hanzo, L.B.、「Comparative Study of Turbo Equalization Schemes using Convolutional, Convolutional Turbo, and Block-Turbo Codes」、IEEE Transactions on Wireless Communications, 1(2)、266〜273頁
【発明の概要】
【課題を解決するための手段】
【０００９】
一実施形態では、本発明は、符号化符号語を復号するための方法である。符号化符号語に対して、対数尤度比（ＬＬＲ：ｌｏｇ−ｌｉｋｅｌｉｈｏｏｄ  ｒａｔｉｏ）値の第１の組が生成され、各ＬＬＲ値は、硬判定値（ｈａｒｄ−ｄｅｃｉｓｉｏｎ  ｖａｌｕｅ）および信頼値（ｃｏｎｆｉｄｅｎｃｅ  ｖａｌｕｅ）を有する。ＬＬＲ値の第１の組に基づいて、符号化符号語に対して復号が実行され、ｂ個の非満足チェック・ノード（ＵＳＣ：ｕｎｓａｔｉｓｆｉｅｄ  ｃｈｅｃｋ  ｎｏｄｅ）を有する復号符号語を生成する。符号化符号語に対して、ＬＬＲ値の第２の組が生成され、少なくとも１つのＬＬＲ値が、ＵＳＣの個数ｂに基づいた信頼値を有する。ＬＬＲ値の第２の組に基づいて、符号化符号語に対して復号が実行される。
【００１０】
本発明の他の態様、特徴、および利点は、以下の詳細な説明、添付の特許請求の範囲、および添付の図面からより十分に明らかとなり、図面において、同じ参照番号は、同様または同一の要素を識別する。
【図面の簡単な説明】
【００１１】
【図１】ＬＤＰＣ符号化を利用する通信システム１００のブロック図である。
【図２】（Ａ）はＬＤＰＣ  Ｈ行列２００を示す図であり、（Ｂ）はＨ行列２００のタナー・グラフ（Ｔａｎｎｅｒ  ｇｒａｐｈ）である。
【図３】図１の復号器１１４によって使用される典型的なＬＤＰＣ復号方法３００のフローチャートである。
【図４】ターボ等化システム４００のブロック図である。
【図５】本発明の一実施形態によるターボ等化システム５００のブロック図である。
【発明を実施するための形態】
【００１２】
図１は、ＬＤＰＣ符号化を利用する、通信システム１００のブロック図である。データ源１０２は、元の情報語１０４として知られる１組のビットを生成する。ＬＤＰＣ符号化器１０６は、元の情報語１０４を符号化して、チャネル入力符号語としても知られる符号語１０８を生成する。ＬＤＰＣ符号化は、以下でより詳細に説明される。その後、符号化器１０６は、例えばハード・ドライブ円盤など、雑音のあるチャネル１１０を介して、符号語１０８を送る。
【００１３】
チャネル検出器１１２は、雑音のあるチャネル１１０から、１組の値ｙとして符号語１０８を受け取る。チャネル検出器１１２は、受け取った値ｙを、１組の対数尤度比（ＬＬＲ）値ＬＣＨに変換する。ＬＬＲ値は、（ｉ）対応する値ｙによって示される１ビット硬判定値に関する復号器の最良推測を表す符号ビット（ｓｉｇｎ  ｂｉｔ）と、（ｉｉ）硬判定に対する復号器の信頼度を表す１つまたは複数の大きさビット（ｍａｇｎｉｔｕｄｅ  ｂｉｔ）とを含む。例えば、チャネル検出器１１２は、５ビットのＬＬＲとして各ＬＣＨ値を出力することができ、その場合、最上位ビットは、硬判定を示す符号ビットであり、４つの大きさビットの値は、硬判定の信頼度を示す。したがって、１つの可能なＬＬＲ方式では、バイナリの０００００のＬＬＲ値は、信頼度が最小の、０の硬判定であり、バイナリの０１１１１のＬＬＲ値は、信頼度が最大の、０の硬判定であり、バイナリの１０００１のＬＬＲ値は、信頼度が最小の、１の硬判定であり、バイナリの１１１１１のＬＬＲ値は、信頼度が最大の、１の硬判定であり、バイナリの１００００は、使用されない。
【００１４】
チャネル検出器１１２は、ＬＣＨ値をＬＤＰＣ復号器１１４に送る。その後、ＬＤＰＣ復号器１１４は、１組のＬＣＨ値に対して１つまたは複数の復号繰り返し１１６（「局所的繰り返し」）を実行して、復号符号語
【数１】
0005506828.tif 000002
を生成する。ＬＤＰＣ復号器１１４は、（ｉ）ＬＤＰＣ復号器１１４が正しい復号符号語（ＤＣＣＷ：ｄｅｃｏｄｅｄ  ｃｏｒｒｅｃｔ  ｃｏｄｅｗｏｒｄ）に達した場合、すなわち、
【数２】
0005506828.tif 000003
がチャネル入力符号語１０８と同じである場合、または（ｉｉ）ＬＤＰＣ復号器１１４がＤＣＣＷに達することなく最大許容可能回数の局所的繰り返しを実行した場合、すなわちＬＤＰＣ復号器１１４が失敗した場合に終了する。復号器１１４は、終了すると、復号符号語
【数３】
0005506828.tif 000004
をデータ送り先１１８に出力する。ＬＤＰＣ復号は、以下で詳細に説明される。
【００１５】
ＬＤＰＣ符号化
【００１６】
符号語１０８を生成するため、ＬＤＰＣ符号化器１０６は、情報語１０４のビットに、ＬＤＰＣ符号によって指定される数個のパリティ・ビットを付加する。情報語１０４のビットの個数は、Ｋで表される。符号化符号語のビットは、変数ビット（ｖａｒｉａｂｌｅ  ｂｉｔ）として知られ、それら変数ビットの個数は、Ｎで表される。したがって、パリティ・ビットの個数は、Ｎ−Ｋによって与えられる。
【００１７】
ＬＤＰＣ符号語の各パリティ・ビットは、特定のＬＤＰＣ符号によって指定される特定の方法で、その符号語内の１つまたは複数の他の（変数またはパリティ）ビットに関連付けられ、パリティ・ビットに割り当てられる値は、ＬＤＰＣ符号を満足するように設定される。典型的なＬＤＰＣ符号は、関連するビットがパリティ検査制約を満足すること、例えば、関連するビットの和が偶数、すなわち、２を法とする和＝０であることを指定する。
【００１８】
ＬＤＰＣ符号
特定のＬＤＰＣ符号は、パリティ検査行列（ｐａｒｉｔｙ−ｃｈｅｃｋ  ｍａｔｒｉｘ）、またはＨ行列、または単にＨとして知られる、１と０とからなる２次元行列によって定義される。Ｈは、ＬＤＰＣ符号化器および復号器の両方によって、事前に知られている。Ｈは、Ｎ個の列と、Ｎ−Ｋ個の行とを含み、すなわち、列は符号語の各ビットに対応し、行は各パリティ・ビットに対応する。Ｈ内の各１は、その列の符号語ビットとその行のパリティ・ビットの間の関連を表す。例えば、Ｈの３行７列にある１は、第３のパリティ検査ビットが符号語の第７のビットに関連することを意味する。検査ビットとその検査ビットに関連するすべての変数ビットの値の２を法とする和は、０でなければならない。典型的なＬＤＰＣ符号の定義特性は、Ｈが「疎ら」であること、すなわち、Ｈの要素は、大部分が０であり、相対的に僅かな要素が１であることである。
【００１９】
図２（Ａ）は、ＬＤＰＣ  Ｈ行列２００を示している。Ｈ行列２００は、Ｎ＝９の列と、Ｎ−Ｋ＝６の行とを含む。したがって、Ｈ行列２００は、３ビットの情報語を受け取り、６つのパリティ・ビットを付加し、９ビットの符号語を出力する、ＬＤＰＣ符号を定義する。
ＬＤＰＣ復号：信念伝播法
【００２０】
図３は、図１の復号器１１４によって使用されるＬＤＰＣ復号方法３００のフローチャートである。復号方法３００の核心は、信念伝播法（ｂｅｌｉｅｆ  ｐｒｏｐａｇａｔｉｏｎ）と呼ばれる、繰り返し２フェース・メッセージ・パッシング・アルゴリズムである。信念伝播法は、タナー・グラフを使用して説明することができる。
【００２１】
図２（Ｂ）は、Ｈ行列２００のタナー・グラフである。一般に、タナー・グラフは、１）Ｈの列の数に等しい（したがって変数ビットの数Ｎに等しい）多数の（変数ノードとしても知られる）ビット・ノードｎと、２）Ｈの行の数に等しい（したがってパリティ・ビットの数に等しい）多数のチェック・ノードｍと、３）各々が単一のビット・ノードｎｉを単一のチェック・ノードｍｉに結合するエッジ２０２と、４）各ビット・ノードｎｉについての元のＬＣＨ値と、５）各ビット・ノードｎｉについての計算された硬判定出力値
【数４】
0005506828.tif 000005
とを含む。図２（Ｂ）のタナー・グラフは、９個のビット・ノードｎ０〜ｎ８と、６個のチェック・ノードｍ０〜ｍ５と、ビット・ノードをチェック・ノードに接続する１８本のエッジと、９個のＬＣＨ値と、９個の
【数５】
0005506828.tif 000006
値とを含む。
【００２２】
タナー・グラフのエッジは、ビット・ノードｎとチェック・ノードｍの間の関係を表し、エッジは、Ｈ内の１に相当する。例えば、図２（Ａ）において、Ｈ行列２００の第１列、第４行には１が存在するので、図２（Ｂ）において、エッジ２０２は第１のビット・ノードｎ０を第４のチェック・ノードｍ３に接続する。
【００２３】
タナー・グラフは、２部グラフ（ｂｉｐａｒｔｉｔｅ  ｇｒａｐｈ）であり、すなわち、エッジは、ビット・ノードをチェック・ノードにだけ接続することができ、ビット・ノードを別のビット・ノードに、またはチェック・ノードを別のチェック・ノードに接続することはできない。エッジによって特定のチェック・ノードｍに接続されるすべてのビット・ノードｎの集合は、Ｎ（ｍ）で表される。エッジによって特定のビット・ノードｎに接続されるすべてのチェック・ノードｍの集合は、Ｍ（ｎ）で表される。特定の（ビットまたはチェック）ノードのインデックスは、グラフ内でのその順序（ｏｒｄｉｎａｌ  ｓｅｑｕｅｎｃｅ）である。
【００２４】
図３に戻ると、処理は、ステップ３０２において開始し、復号器初期化のステップ３０４に進む。復号器初期化３０４は、各ビット・ノードｎに接続されたすべてのエッジ（例えば図２（Ｂ）のエッジ２０２）に、ビット・ノードｎに関連する対応するＬＣＨ値を設定することと、ビット・ノードｎの
【数６】
0005506828.tif 000007
値に、ビット・ノードｎのＬＣＨの硬判定値を設定することとを含む。したがって、例えば、図２（Ｂ）において、ビット・ノードｎ０に関連するＬＣＨ値が１０進値の＋５である場合、ステップ３０４において、ビット・ノードｎ０をチェック・ノードｍ０およびｍ３に接続する２本のエッジ２０２は、＋５に設定され、ビット・ノードｎの
【数７】
0005506828.tif 000008
値は、１に設定される。このステップの第１の部分を別の仕方で表現すると、ビット・ノードｎ０は集合Ｍ（ｎ０）内の各チェック・ノードに＋５のメッセージを送る、となる。ビット・ノードｎからチェック・ノードｍに送られたメッセージは、ビット・ノード・メッセージまたはＱメッセージと呼ばれ、Ｑｎｍで表される。
【００２５】
その後、ステップ３０４は、Ｎ個の
【数８】
0005506828.tif 000009
値を含む候補復号符号語ベクトル
【数９】
0005506828.tif 000010
を、シンドローム検査ステップ３０６に送る。シンドローム検査ステップ３０６は、以下の式（１）、すなわち、
【数１０】
0005506828.tif 000011
を使用して、シンドローム・ベクトルｚを計算し、ここで、ＨＴはＨ行列の転置である。シンドローム・ベクトルｚが０ベクトルである場合、ベクトル
【数１１】
0005506828.tif 000012
は、Ｈによって定義されたすべてのパリティ検査制約を満足しており、すなわち、
【数１２】
0005506828.tif 000013
は、有効復号符号語である。その場合、処理は、巡回冗長検査（ＣＲＣ：ｃｙｃｌｉｃ−ｒｅｄｕｎｄａｎｃｙ  ｃｈｅｃｋ）ステップ３１８に進む。
【００２６】
代わりに、シンドローム・ベクトルｚが０ベクトルでない場合、ベクトル
【数１３】
0005506828.tif 000014
は、パリティ検査制約の１つまたは複数を満足していない。シンドローム・ベクトルｚの各非ゼロ要素は、満足していないパリティ検査制約を表し、非満足チェック・ノード（ＵＳＣ）とも呼ばれる。シンドローム・ベクトルｚ内の非ゼロ要素の個数は、ベクトル
【数１４】
0005506828.tif 000015
内のＵＳＣの個数ｂである。さらに、シンドローム・ベクトルｚの非ゼロ要素のインデックスは、ベクトル
【数１５】
0005506828.tif 000016
内のＵＳＣのインデックスである。
【００２７】
ベクトル
【数１６】
0005506828.tif 000017
がシンドローム検査３０６に不合格になった場合、処理は、１つまたは複数の復号繰り返し３０８（「局所的繰り返し」）の第１の繰り返しに進む。復号繰り返し３０８は、３つのステップ、すなわち、１）信念伝播法のチェック・ノード更新ステップ３１０と、２）信念伝播法のビット・ノード更新ステップ３１２と、３）ステップ３０６と同じであるシンドローム検査ステップ３１４とを含む。
【００２８】
信念伝播法のチェック・ノード更新ステップ３１０では、各チェック・ノードｍは、集合Ｎ（ｍ）内のすべてのビット・ノードｎから受け取ったＱｎｍメッセージを使用して、以下の式（２）、式（３）、式（４）、すなわち
【数１７】
0005506828.tif 000018
によって、Ｒｍｎと呼ばれる１つまたは複数のチェック・ノード・メッセージまたはＲメッセージを計算し、ここで、ｉは、復号繰り返しであり、Ｎ（ｍ）＼ｎは、ビット・ノードｎを除外した集合Ｎ（ｍ）であり、関数ｓｇｎは、そのオペランドの符号を返し、βは、その値が符号パラメータに依存する正の定数である。各チェック・ノードｍは、計算されたＲｍｎメッセージを、先と同じエッジに沿って、集合Ｎ（ｍ）内のすべてのビット・ノードｎに送り返す。
【００２９】
次に、信念伝播法のビット・ノード更新ステップ３１２では、各ビット・ノードｎは、以下の式（５）、すなわち、
【数１８】
0005506828.tif 000019
によって、１つまたは複数のＱｎｍメッセージを計算し、ここで、
【数１９】
0005506828.tif 000020
は、ビット・ノードｎの元のＬＣＨ値であり、Ｍ（ｎ）＼ｍは、チェック・ノードｍを除外した集合Ｍ（ｎ）である。その後、各ビット・ノードｎは、計算されたＱｎｍメッセージを、集合Ｍ（ｎ）内のすべてのチェック・ノードｍに送る。
【００３０】
また、ビット・ノード更新ステップ３１２の最中に、各ビット・ノードｎは、以下の式（６）、式（７）、すなわち、
【数２０】
0005506828.tif 000021
によって、その
【数２１】
0005506828.tif 000022
値を更新する。Ｐｎ≧０である場合、
【数２２】
0005506828.tif 000023
であり、Ｐｎ＜０である場合、
【数２３】
0005506828.tif 000024
である。式（６）によって生成される値は、外部値またはＥ値とも呼ばれ、ＥＬＤＰＣで表される。式（７）によって生成される値は、Ｐ値と呼ばれる。式（２）〜式（７）によって表される特定の信念伝播法アルゴリズムは、最小和アルゴリズム（ｍｉｎ−ｓｕｍ  ａｌｇｏｒｉｔｈｍ）として知られている。
【数２４】
0005506828.tif 000025
値は、各復号繰り返し３０８の最中に更新され、最終的に復号プロセス３００によって出力されることに留意されたい。元のＬＬＲ値ＬＣＨは、復号プロセス３００の間、変化せずにいる。
【００３１】
ビット・ノード更新ステップ３１２は、復号器の現在の
【数２５】
0005506828.tif 000026
値から構成されるベクトル
【数２６】
0005506828.tif 000027
を、シンドローム検査ステップ３１４に送る。ステップ３１４のシンドローム検査は、上で説明されたステップ３０６のシンドローム検査と同じである。ベクトル
【数２７】
0005506828.tif 000028
がシンドローム検査３１４に合格した場合、ベクトル
【数２８】
0005506828.tif 000029
は、ＣＲＣステップ３１８に送られる。
【００３２】
ＬＤＰＣ復号：巡回冗長検査および誤満足チェック・ノード
シンドローム検査３０６または３１４に合格したことは、ベクトル
【数２９】
0005506828.tif 000030
が有効復号符号語であることを意味するが、必ずしも正しい復号符号語（ＤＣＣＷ）であることを意味しない。ＬＤＰＣ復号器が、ＤＣＣＷではない有効復号符号語を生成することは可能である。その場合、ベクトル
【数３０】
0005506828.tif 000031
内にＵＳＣは存在しないが、誤満足チェック・ノード（ＭＳＣ：ｍｉｓ−ｓａｔｉｓｆｉｅｄ  ｃｈｅｃｋ  ｎｏｄｅ）、すなわち、偶数個の誤ったビット・ノードに関連付けられたチェック・ノードが存在する。したがって、有効なベクトル
【数３１】
0005506828.tif 000032
がＤＣＣＷであることを保証するために、プロセス３００は、ベクトル
【数３２】
0005506828.tif 000033
を巡回冗長検査（ＣＲＣ）３１８に渡す。ＣＲＣ検査は、伝送中または保存中のデータ交替を検出することができるチェックサム演算である。
【００３３】
ベクトル
【数３３】
0005506828.tif 000034
がＣＲＣ検査に合格した場合、ベクトル
【数３４】
0005506828.tif 000035
はＤＣＣＷであり、プロセス３００は、グローバル変数ＤＣＣＷを真に設定し、ベクトル
【数３５】
0005506828.tif 000036
を出力して、ステップ３２０において終了する。不合格になった場合、ベクトル
【数３６】
0005506828.tif 000037
はＤＣＣＷでなく、プロセス３００は、グローバル変数ＤＣＣＷを偽に設定し、ベクトル
【数３７】
0005506828.tif 000038
を出力して、ステップ３２０において終了する。グローバル変数ＤＣＣＷは、ＤＣＣＷが生成されたかどうかを他の復号プロセスに通知する。
【００３４】
ステップ３１４に戻ると、ベクトル
【数３８】
0005506828.tif 000039
がシンドローム検査に不合格になった場合、１つまたは複数のＵＳＣが存在する。ＵＳＣを解決する典型的な方法は、別の復号繰り返し３０８を実行することである。しかし、特定の局所的復号セッションには、妥当な時間量では満足されない１つまたは複数のＵＳＣが存在することがある。したがって、ＬＤＰＣ復号器は、一般に、実行できる復号繰り返しの回数を制限される。繰り返しの最大回数の典型的な値は、５０から２００の範囲内にある。
【００３５】
図３において、ステップ３１６は、繰り返しの指定最大回数に達したかどうかを判定する。達していない場合、別の復号繰り返し３０８が実行される。代わりに、繰り返しの最大回数に達した場合、復号器プロセス３００は失敗する。その場合、プロセス３００は、グローバル変数ＤＣＣＷを偽に設定し、ベクトル
【数３９】
0005506828.tif 000040
を出力して、ステップ３２０において終了する。
完了したプロセス３００の実行は、局所的復号セッションとして知られている。
【００３６】
ＢＥＲ、ＳＮＲ、および誤りフロア
ＬＤＰＣ復号器のビット誤り率（ＢＥＲ）は、復号ビットが誤った値をもつ確率を表す。したがって、例えば、ＢＥＲが１０−９である復号器は、平均して、１０億個の復号ビット毎に１個の誤りビットを生成する。ＬＤＰＣ局所的復号セッションのＤＣＣＷへの収束の失敗は、復号器のＢＥＲに寄与する。
【００３７】
ＬＤＰＣ復号器のＢＥＲは、復号器の入力信号の信号対雑音比（ＳＮＲ）によって強く影響される。ＳＮＲの関数としてのＢＥＲのグラフは、一般に、２つの異なる領域、すなわち、ＳＮＲが１単位増加した場合にＢＥＲが速やかに改善（減少）する、最初の「ウォータフォール（ｗａｔｅｒｆａｌｌ）」領域と、ＳＮＲの増加がＢＥＲの限られた改善をもたらすに過ぎない、その後の「誤りフロア」領域とを含む。したがって、誤りフロア領域において著しいＢＥＲの改善を達成するには、ＳＮＲの増加以外の方法が必要である。
【００３８】
ＬＤＰＣ復号の誤りフロア特性を改善するための１つの方法は、符号語の長さを増やすことである。しかし、符号語長の増加は、ＬＤＰＣ復号のために必要とされるメモリおよび他のコンピューティング・リソースも増加させる。したがって、ＨＤドライブのリード・チャネル・デバイスに典型的に見られるように、そのようなリソースが厳しく制限される場合、必要な誤りフロアの改善をもたらす他の方法が見出されなければならない。
【００３９】
別の希少なリソースは、処理サイクルである。一般に、指定されたスループットを達成するため、ＨＤドライブは、一定数のリード・チャネル処理サイクルを符号語の復号に予め割り当てる。その割当量を超える方法（例えばオフ・ザ・フライ（ｏｆｆ−ｔｈｅ−ｆｌｙ）方法）は、スループットを低下させる。より望ましいのは、割り当てられたクロック・サイクル内でＤＣＣＷを回復し、したがって、スループットを低下させない、オン・ザ・フライ（ｏｎ−ｔｈｅ−ｆｌｙ）方法である。
【００４０】
ＬＤＰＣ復号器の誤りフロア特性を改善するための別の方法は、１つまたは複数の後処理（ｐｏｓｔ−ｐｒｏｃｅｓｓｉｎｇ）方法を使用することである。後処理方法は、局所的復号セッションが、許容された繰り返しの最大回数内にＤＣＣＷに収束することに失敗した場合に起動される。後処理方法は、復号プロセスに関連する１つまたは複数の変数（例えば、ｙ値、ＬＣＨ値、および／または復号器の動作パラメータ）を調整して、復号を再び開始する。復号自体と同様に、後処理方法もしばしば繰り返され、復号プロセスの入力に多くの順次的な変更を施す。
【００４１】
典型的なＬＤＰＣ局所的復号セッションでは、復号器は、最初の数回の復号繰り返し内でＤＣＣＷに収束する。代わりに、ＬＤＰＣ復号器が、繰り返しの指定最大回数内にＤＣＣＷに収束することに失敗した場合、それは一般に、２つのシナリオのうちの一方に起因する。第１のシナリオでは、入力符号語が、非常に多くのビット誤りを含み、すなわち、非常に僅かな正しい値しか含まないため、復号器は、すべてのビット誤りを訂正することができず、出力ベクトル
【数４０】
0005506828.tif 000041
は、ビット誤りを多く（例えば１６個より多く）含む無効復号符号語（ＩＣＷ：ｉｎｖａｌｉｄ  ｄｅｃｏｄｅｄ  ｃｏｄｅｗｏｒｄ）である。ＩＣＷを処理するための典型的な後処理方法は、入力符号語の再送を必要とする。再送はオフ・ザ・フライ方法であり、したがって、望ましくないが、一般に、ＩＣＷを訂正するための信頼できる唯一の選択肢である。
【００４２】
第２のシナリオでは、復号符号語は、僅かな個数（例えば１６個以下）のＵＳＣを所有する。そのような復号符号語は、近符号語（ＮＣＷ：ｎｅａｒ  ｃｏｄｅｗｏｒｄ）として知られている。しばしば、ＮＣＷ内のＵＳＣは、さらなる復号繰り返しに影響されない、トラッピング・セット（ｔｒａｐｐｉｎｇ  ｓｅｔ）として知られる、安定な構成を形成する。ＮＣＷ／トラッピング・セットは、ＬＤＰＣ復号器の誤りフロア特性に著しい影響を有する。
【００４３】
ターボ等化
ターボ等化は、ＮＣＷを訂正するための後処理方法の一族に関連する。具体的には、ターボ等化は、復号中に復号器によって生成された１つまたは複数の値を取得し、それらの値を元のＬＬＲ値と組み合わせて、新しい調整ＬＬＲ値を生成し、その後、新しい調整ＬＬＲ値は、復号器への新しい入力となる。
【００４４】
典型的なターボ等化方式では、失敗した復号器のＥＬＤＰＣ値は、元のＬＣＨ値と組み合わされて、新しい調整ＬＣＨ値を生成する。その後、調整ＬＣＨ値は、復号器に供給され戻し、復号が再実行される。ＬＣＨ値を調整し、復号を再実行するステップは、大域的繰り返しとして知られている。
【００４５】
一般に、ターボ等化は、繰り返しプロセスである。ＬＤＰＣ復号器が、調整ＬＣＨ値を用いてＤＣＣＷに達することに失敗した場合、別の大域的繰り返しが実行され、すなわち、調整ＬＣＨ値が、失敗した復号器の新しいＥＬＤＰＣ値と再び組み合わされて、ＬＤＰＣ復号器に供給され戻す。大域的繰り返しは、（ｉ）ＬＤＰＣ復号器がＤＣＣＷに達した場合、または（ｉｉ）指定最大許容回数の大域的繰り返しが実行された場合に停止する。復号のために新しい符号語が受け取られた瞬間から最後の大域的繰り返しが完了する瞬間までの、ターボ等化によって実行されるステップは、大域的復号セッションとして知られている。
【００４６】
ターボ等化についてのより多くの情報は、（ｉ）A. C. Douillard、A. Picart、M. Jezequel、P. Didier、C. Berrou、A. Glavieux、「Iterative correction of intersymbol interference: Turbo-equalization」、Eur. Trans. Commun.、vol. 6,、507〜511頁、1995年9月〜10月、（ｉｉ）Yeap, B. L.、Liew, T. H.、Hamorsky, J.、Hanzo, L.B.、「Comparative Study of Turbo Equalization Schemes using Convolutional, Convolutional Turbo, and Block-Turbo Codes」、IEEE Transactions on Wireless Communications, 1(2)、266〜273頁において見出すことができ、両文献は、参照によりその全体が本明細書に組み込まれる。
【００４７】
図４は、ターボ等化システム４００のブロック図である。ターボ等化システム４００は、バッファ４０２と、チャネル検出器４０４（例えば、ＭＡＰ検出器、ビタビ（Ｖｉｔｅｒｂｉ）検出器など）と、加算ノード４０６と、ＬＤＰＣ復号器４０８と、バッファ４１２と、遅延バッファ４１６とを含む。ターボ等化システム４００は、チャネル検出器１１２およびＬＤＰＣ復号器１１４から成る図１の通信システム１００の一部に類似している。
【００４８】
バッファ４０２は、雑音のあるチャネル（例えば図１のチャネル１１０）から受け取った等化チャネル・サンプル値ｙをバッファする。チャネル検出器４０４は、（ｉ）バッファ４０２から１組のｙサンプルを読み、（ｉｉ）バッファ４１２から一致する１組の外部情報値ＥＬＤＰＣ（第１の大域的繰り返しの場合はＥＬＤＰＣ＝０）を読み、初期ＬＬＲ値ＬＣＤを生成する。加算ノード４０６は、（ｉ）遅延バッファ４１６から受け取った外部情報値
【数４１】
0005506828.tif 000042
を、（ｉｉ）初期ＬＬＲ値ＬＣＤから減算して、調整ＬＬＲ値ＬＣＨを生成する。ＬＤＰＣ復号器４０８は、調整ＬＬＲ値ＬＣＨを使用して１つまたは複数の局所的繰り返し４１０を実行し、（ｉ）符号語
【数４２】
0005506828.tif 000043
と、（ｉｉ）新しい１組の外部情報値ＥＬＤＰＣとを生成する。外部情報値ＥＬＤＰＣは、ＬＤＰＣ復号器４０８によって生成されたＬＬＲ値から、調整ＬＬＲ値ＬＣＨをマイナスしたものである（式６および式７を参照）。バッファ４１２は、外部情報値
【数４３】
0005506828.tif 000044
を生成するために、１つの大域的繰り返しのための外部情報値ＥＬＤＰＣを保存する。同様に、遅延バッファ４１６は、外部情報値
【数４４】
0005506828.tif 000045
を保存し、それをサンプル数個だけ遅延させて（サンプルの数はチャネル検出器４０４の処理遅延に依存する）、外部情報値
【数４５】
0005506828.tif 000046
を生成する。
【００４９】
各大域的繰り返し４１４は、（ｉ）バッファ４０２および４１２から値を受け取り、ＬＬＲ値ＬＣＤを生成する、チャネル検出器４０４と、（ｉｉ）差を生成する、加算ノード４０６と、（ｉｉｉ）局所的復号セッションを実行する、ＬＤＰＣ復号器４０８と、（ｉｖ）ＥＬＤＰＣ値の対応する組を保存し、遅延させる、バッファ４１２および４１６とを含む。したがって、与えられた大域的繰り返しｉにおいて、加算ノード４０６は、初期ＬＬＲ値ＬＣＤから、大域的繰り返しｉ−１において生成されたＥＬＤＰＣ値（すなわち、大域的繰り返しｉ−１からの
【数４６】
0005506828.tif 000047
、最初の大域的繰り返し、すなわち、ｉ＝０の場合は、
【数４７】
0005506828.tif 000048
）を減算する。
【００５０】
システム４００の動作の一例は、以下のようである。変数の上付きの添字は、特定の変数が属する大域的繰り返しを指示する。例えば、
【数４８】
0005506828.tif 000049
は、第３の大域的繰り返し（すなわち大域的繰り返し３）において復号器４０８によって生成されたＥＬＤＰＣ値を指示する。
【００５１】
復号のためにｙ信号の新しい１組を受け取ると、システム４００は、ＥＬＤＰＣ値のすべてをゼロに初期化する。
【数４９】
0005506828.tif 000050
は、初期化中に大域的繰り返し１において復号器４０８によって生成されるＥＬＤＰＣ値を指示するので、システム４００は、（バッファ４１２に保存され、大域的繰り返し１の最中にチャネル検出器４０４において適用される）値
【数５０】
0005506828.tif 000051
と、（遅延バッファ４１６に保存され、大域的繰り返し１の最中に加算ノード４０６において適用される）値
【数５１】
0005506828.tif 000052
とをゼロに初期化する。
【００５２】
システム４００の大域的繰り返し１では、チャネル検出器４０４において適用されるバッファされた外部情報値
【数５２】
0005506828.tif 000053
と、加算ノード４０６において適用される遅延された外部情報値
【数５３】
0005506828.tif 000054
は、ヌル（ｎｕｌｌ）である。したがって、調整ＬＬＲ値ＬＣＨは、初期ＬＬＲ値ＬＣＤに等しい。ＬＤＰＣ復号器４０８は、調整ＬＬＲ値ＬＣＨに対して１つまたは複数の局所的繰り返しを実行し、新しい外部情報値
【数５４】
0005506828.tif 000055
をバッファ４１２に出力し、バッファ４１２は、バッファされた外部情報値
【数５５】
0005506828.tif 000056
を遅延バッファ４１６に出力する。
【００５３】
大域的繰り返し１の最中に、復号器４０８がＤＣＣＷに収束する場合、ＬＤＰＣ復号は成功である。その場合、チャネル検出器４０４は、復号するｙ値の次の組を受け取り、バッファ４１２および４１６は、ゼロに再初期化される。他方、
【数５６】
0005506828.tif 000057
がＤＣＣＷでない場合、システム４００は、別の大域的繰り返し４１４（すなわち大域的繰り返し２）を開始する。
【００５４】
大域的繰り返し２において、チャネル検出器４０４は、バッファされたｙ値と、バッファされた外部情報値
【数５７】
0005506828.tif 000058
とを処理して、新しい初期ＬＬＲ値ＬＣＤを生成し、それを加算ノード４０６に提供する。加算ノード４０６は、新しい初期ＬＬＲ値ＬＣＤから、バッファされた外部情報値
【数５８】
0005506828.tif 000059
を減算し、結果の調整ＬＬＲ値ＬＣＨをＬＤＰＣ復号器４０８に送り、そこで、新しい局所的復号セッションが開始される。ＬＤＰＣ復号器４０８は、調整ＬＬＲ値ＬＣＨに対して１つまたは複数の局所的繰り返しを実行し、新しい外部情報値
【数５９】
0005506828.tif 000060
をバッファ４１２に出力し、バッファ４１２は、バッファされたＬＬＲ値
【数６０】
0005506828.tif 000061
を遅延バッファ４１６に出力する。
【００５５】
大域的繰り返し２の最中に、復号器４０８がＤＣＣＷに収束する場合、ＬＤＰＣ復号は成功である。その場合、チャネル検出器４０４は、復号するｙ値の次の組を受け取り、バッファ４１２および４１６は、ゼロに再初期化される。他方、
【数６１】
0005506828.tif 000062
がＤＣＣＷでない場合、システム４００は、別の大域的繰り返し４１４（すなわち大域的繰り返し３）を開始する。
【００５６】
大域的繰り返し３において、チャネル検出器４０４は、バッファされたｙ値と、バッファされた外部情報値
【数６２】
0005506828.tif 000063
とを処理して、新しい初期ＬＬＲ値ＬＣＤを生成し、それを加算ノード４０６に提供する。加算ノード４０６は、新しい初期ＬＬＲ値ＬＣＤから、バッファされた外部情報値
【数６３】
0005506828.tif 000064
を減算し、結果の調整ＬＬＲ値ＬＣＨをＬＤＰＣ復号器４０８に送り、そこで、新しい局所的復号セッションが開始される。ＬＤＰＣ復号器４０８は、調整ＬＬＲ値ＬＣＨに対して１つまたは複数の局所的繰り返しを実行し、新しい外部情報値
【数６４】
0005506828.tif 000065
をバッファ４１２に出力し、バッファ４１２は、バッファされたＬＬＲ値
【数６５】
0005506828.tif 000066
を遅延バッファ４１６に出力する。
【００５７】
大域的繰り返し３の最中に、復号器４０８がＤＣＣＷに収束する場合、ＬＤＰＣ復号は成功である。その場合、チャネル検出器４０４は、復号するｙ値の次の組を受け取り、バッファ４１２および４１６は、ゼロに再初期化される。他方、
【数６６】
0005506828.tif 000067
がＤＣＣＷでない場合、システム４００は、別の大域的繰り返し４１４（すなわち大域的繰り返し４）を開始する。
【００５８】
大域的繰り返しのこのプロセスは、ＤＣＣＷが生成されるまで、または大域的繰り返しの最大回数に達するまで続けられる。
【００５９】
図５は、本発明の一実施形態による、ターボ等化システム５００のブロック図である。図４のターボ等化システム４００と同様に、ターボ等化システム５００は、チャネル検出器１１２およびＬＤＰＣ復号器１１４から成る図１の通信システム１００の一部に類似している。図５のバッファ５０２、チャネル検出器５０４、加算ノード５０６、ＬＤＰＣ復号器５０８、バッファ５１２、および遅延バッファ５１６は、それぞれ、図４のバッファ４０２、チャネル検出器４０４、加算ノード４０６、ＬＤＰＣ復号器４０８、バッファ４１２、および遅延バッファ４１６に類似している。加えて、ターボ等化システム５００は、ＬＬＲ調整器５２０と、スイッチ５１８とを含む。ＬＬＲ生成器５２４は、バッファ５０２と、チャネル検出器５０４と、加算ノード５０６と、ＬＤＰＣ復号器５０８と、バッファ５１２と、遅延バッファ５１６と、ＬＬＲ調整器５２０と、論理ブロック５２２と、スイッチ５１８とを含む。
【００６０】
加算ノード５０６に適用されるのに加えて、チャネル検出器５０４によって生成された初期ＬＬＲ値ＬＣＤは、ＬＬＲ調整器５２０にも適用される。ＬＤＰＣ復号器５０８に直接適用される代わりに、加算ノード５０６によって生成された標準の調整ＬＬＲ値ＬＰ１が、スイッチ５１８に適用される。
【００６１】
ＬＬＲ調整器５２０は、（ｉ）チャネル検出器５０４から初期ＬＬＲ値ＬＣＤを受け取り、（ｉｉ）ＬＤＰＣ復号器５０８から先行する局所的復号セッションからの復号符号語
【数６７】
0005506828.tif 000068
内のｂ個の非満足チェック・ノードを受け取る。ＬＬＲ調整器５２０は、以下の式（８）、すなわち、
ＬＰ２＝ｓｉｇｎ（Ｌ１）＊ｂ，    （８）
によって、改善された調整ＬＬＲ値ＬＰ２を計算し、ここで、改善された調整ＬＬＲ値ＬＰ２は、対応する初期ＬＬＲ値ＬＣＤの符号を有するが、大きさは、先のＵＳＣの個数ｂに等しい。したがって、例えば、特定の初期ＬＬＲ値ＬＣＤの硬判定が否定的であり、
【数６８】
0005506828.tif 000069
内のＵＳＣの個数ｂが５である場合、ＬＰ２は−５である。その後、改善された調整ＬＬＲ値ＬＰ２は、スイッチ５１８に適用される。
【００６２】
スイッチ５１８は、（ｉ）論理ブロック５２２から１ビット制御信号Ｓを受け取り、（ｉｉ）加算ノード５０６から標準の調整ＬＬＲ値ＬＰ１を受け取り、（ｉｉｉ）ＬＬＲ調整器５２０から改善された調整ＬＬＲ値ＬＰ２を受け取る。Ｓが１である場合、スイッチ５１８は、選択された調整ＬＬＲ値ＬＣＨとして、改善された調整ＬＬＲ値ＬＰ２をＬＤＰＣ復号器５０８に出力する。Ｓが０である場合、スイッチ５１８は、選択された調整ＬＬＲ値ＬＣＨとして、標準の調整ＬＬＲ値ＬＰ１をＬＤＰＣ復号器５０８に出力する。
【００６３】
論理ブロック５２２は、現在の大域的復号繰り返しの回数ｉと、ＬＤＰＣ復号器５０８からの値ｂとを受け取る。論理ブロック５２２は、以下の３つの条件、すなわち、
（１）ｂはｂｍａｘ以下である
（２）ｉはＰを法として０に等しくない
（３）ｉはｉＳＴＡＲＴより大きい
がすべて満たされる場合に、制御信号Ｓとして１を出力する。ｂｍａｘは、ターボ等化システムによって許容されるＵＳＣノードの最大個数を表す。ｂｍａｘの典型的な値は、１６である。ｉは、与えられた大域的繰り返しの序数である。序数ｉは、０に初期化され、大域的繰り返しが開始される毎にインクリメントされる。Ｐは、改善された大域的繰り返しの頻度を表すオペレータ定義の値である。例えば、Ｐが４である場合、それぞれの標準の大域的繰り返しごとに、改善された大域的繰り返しが３回実行される。ｉＳＴＡＲＴは、標準の大域的繰り返し方法を使用する最初の大域的繰り返しのオペレータ定義の回数である。例えば、ｉＳＴＡＲＴが２に設定された場合、最初の２回の大域的繰り返しは、標準の大域的繰り返しである。例えば、Ｐ＝４かつｉＳＴＡＲＴ＝２である場合、大域的繰り返し１、２は、標準の大域的繰り返しであり、大域的繰り返し３は、改善された大域的繰り返しであり、大域的繰り返し４は、標準の大域的繰り返しであり、大域的繰り返し５、６、７は、改善された大域的繰り返しであり、繰り返し８は、標準の大域的繰り返しであり、これ以降も同様に、大域的繰り返し１２、１６、２０、…は、標準の大域的繰り返しであり、他のすべての大域的繰り返しは、改善された大域的繰り返しである。
【００６４】
３つの条件のいずれか１つまたは複数が満たされない場合、論理ブロック５２２は、制御信号Ｓとして０を出力する。
【００６５】
ＬＤＰＣ復号器５０８は、選択された調整ＬＬＲ値ＬＣＨを受け取り、復号を実行する。ＬＤＰＣ復号器５０８は、値の３つの組、すなわち、（１）遅延バッファ５１２に提供される新しい１組の外部情報値
【数６９】
0005506828.tif 000070
と、（２）下流の処理に提供される新しい復号符号語
【数７０】
0005506828.tif 000071
と、（３）ＬＬＲ調整器５２０およびスイッチ５１８に提供される復号符号語
【数７１】
0005506828.tif 000072
内のＵＳＣの個数ｂとを出力する。ＬＤＰＣ復号器５０８がＤＣＣＷに収束しない場合、システム５００の別の大域的繰り返しが実行される。システム５００は、（ｉ）ＬＤＰＣ復号器５０８がＤＣＣＷに収束した場合、または（ｉｉ）システム５００が許容された大域的繰り返しの最大回数内でＤＣＣＷに収束することに失敗した場合に終了する。
【００６６】
改善された大域的繰り返しの頻度Ｐが１に設定された場合、システム５００によって実行されるすべての大域的繰り返しが標準の大域的繰り返しであることに留意されたい。同様に、最初の標準の大域的繰り返しの回数ｉＳＴＡＲＴが、大域的繰り返しの最大回数に等しく設定された場合、すべての大域的繰り返しは、標準の大域的繰り返しである。
【００６７】
研究によって、本発明の実施形態が、繰り返し復号システムのＢＥＲについて１０倍の改善をもたらし得ることが示された。
【００６８】
本発明は、ＬＤＰＣ符号化および復号を実施するハードディスク・ドライブについての文脈で説明されたが、本発明は、そのようには限定されない。一般に、本発明は、ＬＤＰＣ符号化および復号を伴う任意の適切な通信経路において実施することができる。
【００６９】
さらに、上で使用された例示的な信念伝播法アルゴリズムは、オフセット最小和アルゴリズム（ＯＭＳ：ｏｆｆｓｅｔ  ｍｉｎ−ｓｕｍ  ａｌｇｏｒｉｔｈｍ）であるが、本発明は、そのようには限定されず、任意の信念伝播法の変形、例えば、積和アルゴリズム（ＳＰＡ：ｓｕｍ−ｐｒｏｄｕｃｔ  ａｌｇｏｒｉｔｈｍ）またはＢａｈｌ−Ｃｏｃｋｅ−Ｊｅｌｉｎｅｋ−Ｒａｖｉｖ（ＢＣＪＲ）アルゴリズムとともに使用することもできる。
【００７０】
またさらに、上で使用された信念伝播法の例は、すべてのチェック・ノードが単一のチェック・ノード更新ステップ中に更新され、それに続いて、すべてのビット・ノードが単一のビット・ノード更新ステップ中に更新される、特定の復号スケジュール（フラッディング・スケジュール（ｆｌｏｏｄｉｎｇ  ｓｃｈｅｄｕｌｅ））を利用したが、本発明は、そのようには限定されず、任意の復号スケジュール、例えば、行シリアル・スケジュール（ｒｏｗ−ｓｅｒｉａｌ  ｓｃｈｅｄｕｌｅ）、列シリアル・スケジュール（ｃｏｌｕｍｎ−ｓｅｒｉａｌ  ｓｃｈｅｄｕｌｅ）、および行−列シリアル・スケジュール（ｒｏｗ−ｃｏｌｕｍｎ  ｓｅｒｉａｌ  ｓｃｈｅｄｕｌｅ）とともに使用することもできる。
【００７１】
またさらに、例示的なシステム５００は、標準の大域的繰り返しと併せて改善された大域的繰り返しを実行したが、本発明は、そのようには限定されない。例えば、本発明の一実施形態は、改善された大域的繰り返しのみを利用するシステムである。そのようなシステムは、図５のシステム５００と類似しているが、加算ノード５０６、論理ブロック５２２、スイッチ５１８、および遅延バッファ５１６は省かれる。
【００７２】
またさらに、例示的なシステム５００は、改善された大域的繰り返しを実行すべきときを決定するのに３つの特定の基準を利用したが、本発明は、そのようには限定されない。無基準（例えば常に改善された大域的繰り返しを実行する）を含む、任意の適切な数およびタイプの基準を利用することができる。
【００７３】
またさらに、例示的なシステム５００は、改善された調整ＬＬＲ値の大きさをＵＳＣの個数ｂに等しく設定するが、代替実施形態では、改善された調整ＬＬＲ値の大きさは、ｂの値に基づいた異なる数（例えばｂ＋１）に等しく設定することができる。
【００７４】
またさらに、上で使用された例示的なＬＤＰＣ復号器は、非階層的復号器（ｎｏｎ−ｌａｙｅｒｅｄ  ｄｅｃｏｄｅｒ）であったが、本発明は、そのようには限定されず、階層的復号器および非階層的復号器の両方とともに使用することができる。
【００７５】
またさらに、本発明の実施形態は、ＬＤＰＣ符号についての文脈で説明されたが、本発明は、そのようには限定されない。本発明の実施形態は、グラフによって定義できる任意の符号、例えば、トルネード符号（ｔｏｒｎａｄｏ  ｃｏｄｅ）、構造化ＩＲＡ符号（ｓｔｒｕｃｔｕｒｅｄ  ＩＲＡ  ｃｏｄｅ）のために、グラフ定義符号がトラッピング・セットに悩まされる場合に、実施することができる。
【００７６】
本発明は、方法およびそれらの方法を実行するための装置の形態で具現することができる。本発明は、磁気記録媒体、光記録媒体、ソリッド・ステート・メモリ、フロッピ・ディスケット、ＣＤ−ＲＯＭ、ハード・ドライブ、または他の任意の機械可読記憶媒体などの有形な媒体内に具現されるプログラム・コードの形態でも具現することができ、プログラム・コードがコンピュータなどの機械にロードされ、機械によって実行された場合、その機械は本発明を実行するための装置となる。本発明は、例えば、記憶媒体に保存され、機械にロードされ、および／または機械によって実行されるにせよ、あるいは電気的ワイヤもしくはケーブル、光ファイバ、または電磁放射など、何らかの伝送媒体または搬送波を介して伝送されるにせよ、プログラム・コードの形態でも具現することができ、プログラム・コードがコンピュータなどの機械にロードされ、機械によって実行された場合、その機械は本発明を実行するための装置となる。汎用プロセッサで実施される場合、プログラム・コード・セグメントは、プロセッサと組み合わされて、特定の論理回路に類似した動作をする独特なデバイスを提供する。
【００７７】
別途明示的に述べない限り、各数値および範囲は、値または範囲の値の前にあたかも「約」または「略」という語が置かれているかのように、近似的なものと解釈されるべきである。
【００７８】
本発明の本質を説明するために説明され例示された部分の細部、材料、および構成に、本発明の範囲から逸脱することなく、当業者によって様々な変更を施せることがさらに理解されよう。
【００７９】
本明細書で説明された例示的な方法のステップは、必ずしも説明された順序で実行する必要がないこと、そのような方法のステップの順序は、例示的なものに過ぎないと理解されるべきであることを理解されたい。同様に、そのような方法には、追加のステップが含まれてよく、本発明の様々な実施形態と矛盾しない方法では、あるステップを省略することができ、または組み合わせることができる。
【００８０】
本明細書における「一実施形態（ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」または「一実施形態（ａｎ  ｅｍｂｏｄｉｍｅｎｔ）」に対する言及は、その実施形態に関連して説明された特定の特徴、構造、または特性が、本発明の少なくとも１つの実施形態に含まれ得ることを意味する。本明細書の様々な場所に現れる「一実施形態では（ｉｎ  ｏｎｅ  ｅｍｂｏｄｉｍｅｎｔ）」という句は、必ずしもすべてが同じ実施形態に言及しているわけではなく、別個または代替の実施形態は、必ずしも他の実施形態と相互に排他的なわけではない。同じことは、「実施（ｉｍｐｌｅｍｅｎｔａｔｉｏｎ）」という用語にも当てはまる。
【図１】
0005506828.tif 000073
【図２】
0005506828.tif 000074
【図３】
0005506828.tif 000075
【図４】
0005506828.tif 000076
【図５】
0005506828.tif 000077