(57)【要約】      （修正有）【課題】最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器に関するシステム、方法、デバイス、回路を提供する。【解決手段】変数ノードプロセッサ２０２及びチェックノードプロセッサ２０４を有するデータ復号化装置２００を備えるデータ処理システム。変数ノードプロセッサは、変数ノードからチェックノードへのメッセージを生成し、チェックノードから変数ノードへのメッセージに基づいて、認識される（perceived）値を計算するように動作可能である。チェックノードプロセッサは、チェックノードから変数ノードへのメッセージを生成し、変数ノードからチェックノードへのメッセージに基づいてチェックサムを計算するように動作可能である。変数ノードプロセッサ及びチェックノードプロセッサは異なるガロア体を有する。【選択図】図２
2014183569.tif 000002
【特許請求の範囲】
【請求項１】
データ復号化装置であって、
変数ノードプロセッサであって、変数ノードからチェノードへのメッセージを生成し、チェックノードから変数ノードへのメッセージに基づいて認識される値を計算するように動作可能である、変数ノードプロセッサと、
チェックノードプロセッサであって、前記チェックノードから変数ノードへのメッセージを生成し、変数ノードからチェノードへのメッセージに基づいてチェックサムを計算するように動作可能である、チェックノードプロセッサと、
を備え、前記変数ノードプロセッサ及び前記チェックノードプロセッサは異なるガロア体を備える、データ復号化装置。
【請求項２】
非バイナリ低密度パリティチェックデータ復号化器を備える、請求項１に記載の装置。
【請求項３】
前記チェックノードプロセッサは、前記変数ノードからチェックノードへの複数のメッセージのそれぞれにおいて複数のサブメッセージを処理するように動作可能な、最小値と次に最小の値との発見器回路と、
前記最小値と次に最小の値との発見器回路の出力を結合して前記チェックノードから変数ノードへのメッセージを生成するように動作可能な選択及び結合回路と、
を備える、請求項１に記載の装置。
【請求項４】
前記変数ノードからチェックノードへのメッセージ及び前記チェックノードから変数ノードへのメッセージは第１の異なるガロア体にあり、前記最小値と次に最小の値との発見器回路及び前記選択及び結合回路は第２の異なるガロア体にある、請求項３に記載の装置。
【請求項５】
前記第２のガロア体は前記第１のガロア体よりも大きい、請求項４に記載の装置。
【請求項６】
前記変数ノードからチェックノードへのメッセージを、第１の異なるガロア体から第２のガロア体に変換するように動作可能な体変換回路を更に備える、請求項１に記載の装置。
【請求項７】
前記体変換回路は、少なくとも１つの線形群を用いて前記変数ノードからチェックノードへのメッセージを変換するように動作可能である、請求項６に記載の装置。
【請求項８】
前記体変換回路は、線形群を用いた２つの演算を用いて前記変数ノードからチェックノードへのメッセージを変換するように動作可能である、請求項６に記載の装置。
【請求項９】
前記体変換回路は、線形群におけるパリティチェック行列を定義し、パリティチェック行列要素と線形群構成要素との間で写像を行うことによって前記変数ノードからチェックノードへのメッセージを変換するように動作可能である、請求項６に記載の装置。
【請求項１０】
前記体変換回路は、少なくとも部分的に、第１のガロア体の要素を含む符号語をバイナリ画像符号語に変換し、該バイナリ画像符号語及びパリティチェック行列のバイナリ画像を用いてシンドローム計算を行うことによって前記変数ノードからチェックノードへのメッセージを変換するように動作可能である、請求項６に記載の装置。
【請求項１１】
記憶デバイスに組み込まれる、請求項１に記載の装置。
【請求項１２】
前記記憶デバイスは、
データセットを保持する記憶媒体と、
前記記憶媒体上の前記データセットを感知し、該データセットに対応するアナログ出力を提供するように動作可能な読取り／書込みヘッドアセンブリと、
を備え、
前記変数ノードプロセッサは前記アナログ出力から導出された信号を受信するように動作可能である、請求項１１に記載の装置。
【請求項１３】
データ送信デバイスに組み込まれる、請求項１に記載の装置。
【請求項１４】
非バイナリ低密度パリティチェック符号化データを復号化する方法であって、
少なくとも部分的にチェックノードから変数ノードへの複数のメッセージベクトルに基づいて変数ノードプロセッサにおいて変数ノードからチェックノードへのメッセージベクトルを生成することであって、前記変数ノードからチェックノードへのメッセージベクトル及び前記チェックノードから変数ノードへのメッセージベクトルは第１のガロア体の要素を含むことと、
前記変数ノードからチェックノードへのメッセージベクトルを前記第１のガロア体から第２のガロア体に変換することであって、前記第２のガロア体は前記第１のガロア体よりも大きいことと、
少なくとも部分的に、前記第２のガロア体における変数ノードからチェックノードへの複数のメッセージベクトルに基づいて、チェックノードプロセッサにおいてチェックサム及び硬判定を計算することと、
前記変数ノードからチェックノードへの複数のメッセージベクトルに基づいて、前記チェックノードプロセッサにおいて最小値、最小値のインデックス及び準最小値を計算することと、
前記チェックノードプロセッサにおいて、前記最小値、前記最小値のインデックス及び前記準最小値を結合することによってチェックノードから変数ノードへのメッセージベクトルを生成することであって、該チェックノードから変数ノードへのメッセージベクトルは前記第１のガロア体の要素を用いて生成されることと、
を含む、非バイナリ低密度パリティチェック符号化データを復号化する方法。
【請求項１５】
前記変数ノードからチェックノードへのメッセージベクトルを前記第１のガロア体から前記第２のガロア体に変換することは、少なくとも１つの線形群を用いて前記第１のガロア体の要素を写像することを含む、請求項１４に記載の方法。
【請求項１６】
前記変数ノードからチェックノードへのメッセージベクトルを前記第１のガロア体から前記第２のガロア体に変換することは、一連の線形群を用いて前記第１のガロア体の要素からの複数の写像を行うことを含む、請求項１５に記載の方法。
【請求項１７】
前記変数ノードからチェックノードへのメッセージベクトルを前記第１のガロア体から前記第２のガロア体に変換することは、線形群においてパリティチェック行列を定義し、パリティチェック行列要素と線形群構成要素との間で写像を行うことを含む、請求項１４に記載の方法。
【請求項１８】
前記変数ノードからチェックノードへのメッセージベクトルを前記第１のガロア体から前記第２のガロア体に変換することは、前記第１のガロア体の要素を含む符号語をバイナリ画像符号語に変換し、該バイナリ画像符号語及びパリティチェック行列のバイナリ画像を用いてシンドローム計算を行うことを含む、請求項１４に記載の方法。
【請求項１９】
データ復号化回路であって、
変数ノードプロセッサであって、変数ノードからチェノードへのメッセージベクトルを生成し、チェックノードから変数ノードへのメッセージベクトルに基づいて認識される値を計算するように動作可能であり、前記認識される値は第１のガロア体の要素からの複数の値のうちの任意のものをとることができる、変数ノードプロセッサと、
チェックノードプロセッサであって、前記チェックノードから変数ノードへのメッセージベクトルを生成し、変数ノードからチェノードへのメッセージベクトルに基づいてチェックサムを計算するように動作可能であり、実質的に、前記第１のガロア体よりも大きい第２のガロア体を用いて動作し、前記第１のガロア体と前記第２のガロア体との間でメッセージを変換するように動作可能な、チェックノードプロセッサと、
を備える、データ復号化回路。
【請求項２０】
前記チェックノードプロセッサは、
前記変数ノードからチェックノードへの複数のメッセージベクトルのそれぞれにおいて複数のサブメッセージを処理するように動作可能な、最小値及び準最小値発見器回路であって、前記複数の変数ノードからチェックノードへのメッセージベクトルから、前記第１のガロア体の前記要素のそれぞれについて、最小対数尤度比と、最小対数尤度比のインデックスと、準最小対数尤度比とを特定するように動作可能であり、前記第２のガロア体の領域で動作する、最小値及び準最小値発見器回路と、
前記最小値及び準最小値発見器回路の出力を結合して、前記第１のガロア体の領域で前記チェックノードから変数ノードへのメッセージベクトルを生成するように動作可能な選択及び結合回路と、
を備える、請求項１９に記載のデータ復号化回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の様々な実施形態は、データ処理のシステム及び方法、より詳細には、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器に関するシステム及び方法を提供する。
【０００２】
［関連出願の相互参照］
本出願は、Wang他によって２０１３年３月１５日に出願された「Min-Sum BasedHybrid Non-Binary Low Density Parity Check Decoder」と題する米国特許出願第６１／７８６，３６７号の優先権を主張する（上記特許出願の本出願である）。上記特許出願は、全ての目的で引用することによりその全体が本明細書の一部をなす。
【背景技術】
【０００３】
記憶システム、携帯電話システム、及び無線送信システムを含む、様々なデータ処理システムが開発されている。それらのシステムでは、データが何らかの媒体を介して送信機から受信機に転送される。例えば、記憶システムにおいて、データは、送信機（すなわち書込み機能）から、記憶媒体を介して受信機（すなわち読取り機能）に送信される。情報はデジタルデータの形態で記憶及び送信されるので、誤りが生じ、この誤りは、訂正されない場合、データを破損し情報を使用不可能にする可能性がある。任意の転送の有効性は、様々な要因によって生じる、データ内の任意の損失によって影響される。デジタルデータ内の誤りを検出し訂正するために、多くのタイプの誤り検査システムが開発されている。１つのそのような誤り検査システムは低密度パリティチェック（ＬＤＰＣ：low density parity check）復号化器であり、低密度パリティチェック（ＬＤＰＣ）復号化器は符号語内のパリティビットに基づいて符号語内の誤りを検出及び訂正する。
【発明の概要】
【０００４】
本発明の様々な実施形態は、データ処理のシステム及び方法、より詳細には、データ処理システムにおけるデータ符号化のシステム及び方法を提供する。
【０００５】
変数ノードプロセッサ及びチェックノードプロセッサを有するデータ復号化装置を備えるデータ処理システムが開示される。変数ノードプロセッサは、変数ノードからチェックノードへのメッセージを生成し、チェックノードから変数ノードへのメッセージに基づいて、認識される（perceived）値を計算するように動作可能である。チェックノードプロセッサは、チェックノードから変数ノードへのメッセージを生成し、変数ノードからチェックノードへのメッセージに基づいてチェックサムを計算するように動作可能である。変数ノードプロセッサ及びチェックノードプロセッサは異なるガロア体を有する。
【０００６】
本概要は、本発明のいくつかの実施形態の概要のみを提供する。「一実施形態では」、「一実施形態によれば」、「様々な実施形態では」、「１つ又は複数の実施形態では」、「特定の実施形態では」等は、概して、その言い回しの後に続く特定の特徴、構造又は特性が本発明の少なくとも１つの実施形態に含まれ、本発明の２つ以上の実施形態に含まれる場合もあることを意味する。重要なことには、このような言い回しは必ずしも同じ実施形態を参照するとは限らない。この発明の概要は、本発明のいくつかの実施形態の概要のみを提供する。更なる実施形態は以下の詳細な説明、添付の特許請求の範囲、及び添付の図面において開示される。
【０００７】
図面を参照することにより、本発明の様々な実施形態の更なる理解を実現することができ、これらの実施形態については本明細書の残りの部分で説明する。図面において、同様の参照符号が幾つかの図面の全てにわたって類似の構成要素を指すのに用いられている。図面において、同様の参照符号はいくつかの図面を通じて類似した構成要素を指すのに用いられる。
【図面の簡単な説明】
【０００８】
【図１】図１Ａは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器のためのパリティチェック行列を示す図である。図１Ｂは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器においてシンドロームを計算するために図１Ａのパリティチェック行列に関連して用いられる符号語のベクトルを示す図である。図１Ｃは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器のための図１Ａのパリティチェック行列に等価なバイナリ画像を示す図である。図１Ｄは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器においてシンドロームを計算するために図１Ｃのバイナリ画像パリティチェック行列に関連して用いられる符号語のバイナリベクトルを示す図である。図１Ｅは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器のための図１Ａのパリティチェック行列に等価な線形群を示す図である。図１Ｆは、本発明の１つ又は複数の実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器においてシンドロームを計算するために図１Ｅのパリティチェック行列からの線形群に関連して用いられる符号語のバイナリベクトルを示す図である。
【図２】本発明の１つ又は複数の実施形態による最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器のブロック図である。
【図３】本発明の１つ又は複数の実施形態による、図２の変換回路の代わりに用いるのに適した変換回路のブロック図である。
【図４】本発明の１つ又は複数の実施形態による、最小値発見機、選択及び結合回路のブロック図である。
【図５】本発明の１つ又は複数の実施形態による第１の結合回路のブロック図である。
【図６】本発明の１つ又は複数の実施形態による第２の結合回路のブロック図である。
【図７】本発明の１つ又は複数の実施形態による、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化の方法を示す流れ図である。
【図８】本発明の１つ又は複数の実施形態による、記憶されたデータ又は送信データを取り出すか又は受信するのに用いることができる、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器を有する読取りチャネルのブロック図である。
【図９】本発明の１つ又は複数の実施形態による、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータ処理システムを備える記憶システムを示す図である。
【図１０】本発明の１つ又は複数の実施形態による、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータ処理システムを備える無線通信システムを示す図である。
【発明を実施するための形態】
【０００９】
本発明の様々な実施形態は、データを復号化するシステム及び方法に関し、より詳細には、ハイブリッド非バイナリ低密度パリティチェック（ＬＤＰＣ）コードを最小和に基づいて復号化するシステム及び方法に関する。ハイブリッド低密度パリティチェック復号化器は、チェックノード及び変数ノードが異なるガロア体サイズを有する復号化器である。非バイナリ低密度パリティチェック復号化器では、変数ノードはガロア体、すなわち有限数の要素を含む有限体ＧＦ（ｐｋ）からの、サイズｐｋによって特徴付けられるシンボルを含む。ここで、ｐは素数であり、ｋは正の整数である。ハイブリッド低密度パリティチェック復号化器では、ガロア体のサイズすなわち要素数は、変数ノードの場合とチェックノードの場合とで異なる。換言すれば、チェックノードの場合と変数ノードの場合とで２つの異なるガロア体を用いる。パリティチェック行列が線形群において定義される。非ハイブリッドガロア体復号化器を線形群に一般化することによって、ハイブリッドコードとともに用いることに関して最小和に基づく非バイナリ低密度パリティチェック復号化器を一般化することができる。この復号化器は変数ノードとチェックノードとの間での異なるガロア体間の写像を扱い、メッセージを変換する。チェックノードプロセッサからの硬判定を変数ノードプロセッサフォーマットに写像することができない場合、メッセージは硬判定を得るように再正規化される。
【００１０】
最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器におけるチェックノード（又はチェックノードプロセッサ）は、接続された変数ノード又は近傍の変数ノードから到来するメッセージを受信し、低密度パリティチェックコード用のパリティチェック行列を実装するように、各近傍変数ノードへの発信メッセージを生成する。チェックノードに到来するメッセージは本明細書においてＶ２Ｃメッセージとも呼ばれ、それらが変数ノードからチェックノードに流れることを示し、チェックノードからの発信メッセージは本明細書においてＣ２Ｖメッセージとも呼ばれ、それらがチェックノードから変数ノードに流れることを示す。チェックノードは複数のＶ２Ｃメッセージを用いて、各近傍変数ノードへの個別のＣ２Ｖメッセージを生成する。最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器におけるメッセージは、送信側の変数ノードが特定の値を含む確率を表す簡易尤度確率値又は対数尤度比（ＬＬＲ）値として送信されるスカラー値である。
【００１１】
ガロア体の各要素は、一意のバイナリベクトル形式を有する。シンボルをそれらの対応するバイナリベクトルに置き換えることにより符号語を変換することによって、符号語のバイナリ画像が得られる。バイナリ画像はパリティチェック行列のバイナリ画像によって復号化器においてチェックされる。各要素は２つの代替的な形式、すなわちバイナリベクトル形式及び一意のバイナリ行列形式を有する。パリティチェック行列のエントリを対応するバイナリ行列と置き換えると、パリティチェック行列のバイナリ画像が得られる。要素｛０，１，２，３｝を有するＧＦ（４）を用いた一実施形態では、データシンボル内の要素は、一意のバイナリ行列形式を有するそれらの対応するバイナリベクトルによって以下のように置き換えられる。
０→ベクトル：［００］；行列：［００；００］
１→ベクトル：［０１］；行列：［１０；０１］
２→ベクトル：［１０］；行列：［１１；１０］
３→ベクトル：［１１］；行列：［０１；１１］
【００１２】
ＧＦ（４）内の各エントリは、ＧＦ（４）内の全てのａ、ｂについて全単射写像ＧＦ（４）→ＧＦ（４）であり、バイナリ行列形式でｂ＝ｈ＊ａとして定義される。ここで、ｈはガロア体ＧＦ（４）の要素である。
【００１３】
ハイブリッド非バイナリ低密度パリティチェック復号化器は、符号語Ｃとパリティチェック行列Ｈとのドット積、すなわちＳ＝Ｃ・ＨをとることによりシンドロームＳを計算することによってデータ収束を検出する。シンドロームＳはデータが正しい値に収束したときに０を有するベクトルである。一例が図１Ａに示されている。ここで、パリティチェック行列１００はＧＦ（４）においてシンボル形式で示されている。パリティチェック行列１００及び符号語Ｃ１０２のドット積によってシンドローム１０４が得られる。シンドローム１０４は、データが正しい値に収束しているとき０である。一実施形態における符号語Ｃ１０２の例示的なベクトルが図１Ｂに示されている。符号語Ｃ１０２は上端から下方へのベクトル（vector from top end down）であり、パリティチェック行列１００を乗算することができるようになっている。等価な形式が図１Ｃに示されている。ここで、パリティチェック行列１１０はパリティチェック行列１００のバイナリ画像である。バイナリ画像パリティチェック行列１１０とバイナリ符号語Ｃ１１２とのドット積によってシンドローム１１４が得られ、これはデータが正しい値に収束しているとき０である。１つの実施形態における符号語Ｃ１１２の例示的なバイナリベクトルが図１Ｄに示されている。
【００１４】
非バイナリシンボルの行列形式が用いられる場合、非バイナリパリティチェック行列は、有限体に従って各シンボルを一意のバイナリ行列に置き換えることによってバイナリ行列に変換することができる。重ね合わせと呼ばれるこの動作は、ＧＦ（ｑ）から線形群に一般化することができる。
【００１５】
ガロア体と線形群との間の差は、線形群を用いると、限定ではないが加法的逆元又は乗法的逆元等の逆元を常に見つけることができるわけではないことである。しかしながら、逆関数が存在しない場合であってもパリティチェック行列を依然として線形群として定義することができる。線形群ＬＧ（２，２）が｛０，１，２，３，４，５，６｝として定義され、各要素が一意のバイナリ行列に対応する場合、以下のバイナリ行列定義を所与として、パリティチェック行列を線形群ＬＧ（２，２）に基づいて定義してパリティチェック行列のバイナリ画像を生成することができる。
０→行列：［００；００］
１→行列：［１０；０１］
２→行列：［１１；１０］
３→行列：［０１；１１］
４→行列：［１１；０１］
５→行列：［０１；１０］
６→行列：［１０；１１］
【００１６】
このプロセスは、７つのバイナリ行列を選択することを含み、それらのそれぞれが０〜６の異なる数字で称される。線形群の場合、各要素又はバイナリ行列の名前は設計プロセス中に定義される。符号語は依然としてＧＦ（４）内のシンボルシーケンスである。しかしながら、パリティチェック行列は線形群形式ＬＧ（２，２）をとる。ＬＧ（２，２）内の各エントリは、ＧＦ（４）内の全てのａ、ｂについて全単射写像ＧＦ（４）→ＧＦ（４）であり、バイナリ行列形式でｂ＝ｈ＊ａとして定義される。ここで、ｈは線形群ＬＧ（２，２）の要素である。
【００１７】
図１Ａ〜図１Ｄの例示的なシンドローム計算は図１Ｅ〜図１Ｆにおいて繰り返される。ここで、符号語ＣはＧＦ（４）形式をとり、パリティチェック行列Ｈは線形群ＬＧ（２，２）形式をとる。図１Ｅにおいて、線形群ＬＧ（２，２）形式のパリティチェック行列１２０がＧＦ（４）形式の上下ベクトル（top-down vector）符号語Ｃ１２２とともに示されている。１つの実施形態における符号語Ｃ１２２の例示的なベクトルが図１Ｆに示されている。
【００１８】
線形群は、上記で開示したように正方行列を用いて定義することができる。他の実施形態では、線形群は矩形行列に基づいて定義される。いくつかの代替的な実施形態では、線形群は３×１の行列に基づいて（based  on）定義され、線形群ＬＧ（３，１）が得られる。８つの要素ＬＧ（３，１）＝｛０，１，２，３，４，５，６，７｝を有する一実施形態では、これにより８つの行列が利用可能になる。これらはそれぞれ以下のように番号で呼ばれる。
０→行列：［０００］’
１→行列：［１００］’
２→行列：［０１０］’
３→行列：［１１０］’
４→行列：［００１］’
５→行列：［１０１］’
６→行列：［０１１］’
７→行列：［１１１］’
【００１９】
このため、パリティチェックを変換することができる線形群を、限定ではないが上記の例示的な実施形態等の方式で定義することができる。第１に、ガロア体は正方行列を有する線形群に一般化され、正方行列を有する線形群は矩形行列を有する線形群に一般化される。符号語Ｃは依然としてＧＦ（２）、すなわちバイナリガロア体のシンボルシーケンスである。しかしながら、ここでパリティチェック行列はＬＧ（３，１）形式の矩形行列の線形群である。ＬＧ（３，１）内の各エントリはＧＦ（２）内のａ、ＧＦ（８）内のｂについての単射写像ＧＦ（２）→ＧＦ（８）であり、バイナリ行列形式でｂ＝ｈ＊ａとして定義される。ここで、ｈは線形群ＬＧ（３，１）の要素であり、ａはｂの逆元である。例えば、Ｈ＝３；０→［０００］’；１→［００１］’であるのに対し、［００１］は逆元を有しない。バイナリ数０又は１に線形群ＬＧ（３，１）内の要素を乗算する場合、結果は３×１行列とバイナリ数を乗算したものである。結果がｂである場合（ここで、ｂ＝Ｈ＊ａ）、Ｈは線形群ＬＧ（３，１）の要素であり、ａはバイナリ数である。結果ｂは３×１のバイナリ行列である。ａはｂの逆元であると言うことができる。ＧＦ（２ｐ）内の２ｑ個のシンボルのみが逆元を有する。換言すれば、この実施形態では、ＧＦ（８）において演算するとき、逆元が常に存在するが、線形群ＬＧ（３，１）において演算するとき、常に逆元が存在するとは限らない。逆元が利用可能でないとき、ハイブリッド非バイナリ低密度パリティチェック復号化器はメッセージを再正規化して硬判定を得る。
【００２０】
非ハイブリッド復号化器をガロア体形式から線形群形式を有するハイブリッド復号化器に一般化するために、ハイブリッド復号化器内のチェックノードユニットは、Ｖ２ＣメッセージをＧＦ（２ｑ）からＧＦ（２ｐ）に写像するように構成される。チェックノードユニットはＧＦ（２ｐ）領域で演算し、チェックノードユニット結果（すなわちＣ２Ｖメッセージ）はＧＦ（２ｐ）からＧＦ（２ｑ）に逆写像される。ｐ＞ｑの線形群ＬＧ（ｐ，ｑ）の場合、変数ノード更新を実行しＶ２Ｃメッセージを生成する変数ノードユニットは次元２ｑを有し、Ｃ２Ｖメッセージを生成するチェックノードユニットは次元２ｐを有する。Ｖ２Ｃメッセージ及びＣ２Ｖメッセージはガロア体ＧＦ（２ｑ）においてサイズ２ｑ−１を有し、単純化された最小和に基づく復号化器内のｍｉｎ１メッセージ及びｍｉｎ２メッセージはガロア体ＧＦ（２ｐ）においてサイズ２ｐ−１を有する。線形群を用いて、シンボルが変数ノードユニットからチェックノードユニットのシンボルに写像される。ただし、チェックノードユニットにおけるいくつかのシンボルの場合、対応するシンボルは、再正規化することなく変数ノードユニットについて発見することができない。
【００２１】
Ｖ２Ｃメッセージ及びＣ２Ｖメッセージの双方がベクトルであり、それぞれが対数尤度比値を有する複数の部分メッセージを含み、それぞれがガロア体ＧＦ（２ｑ）においてサイズ２ｑ−１を有する。ただし、チェックノードプロセッサ又はチェックノードユニットにおけるｍｉｎ１メッセージ及びｍｉｎ２メッセージは、ハイブリッド復号化器において、ガロア体ＧＦ（２ｐ）においてサイズ２ｐ−１に変換される。特定の変数ノードからの各Ｖ２Ｃメッセージベクトルは、ガロア体内の各シンボルに対応する部分メッセージを含み、各部分メッセージは、変数ノードがその特定のシンボルを含む尤度を与える。例えば、２ｑ個の要素を有するガロア体ＧＦ（２ｑ）を所与とすると、Ｖ２Ｃメッセージ及びＣ２Ｖメッセージは、体内のシンボルごとの尤度を表す少なくとも２ｑ個の部分メッセージを含む。単純化された最小和復号化におけるメッセージ正規化は、最も可能性の高いシンボルに関して実行される。このため、Ｖ２Ｃ及びＣ２Ｖのベクトルフォーマットは２つの部分、すなわち、最も可能性の高いシンボルの特定及び他の２ｑ−１個のシンボルの対数尤度比を含む。なぜなら、最も可能性の高いシンボルは、正規化後に０に等しい対数尤度比を有するためである。
【００２２】
一般に、チェックノードから変数ノードへのＣ２Ｖベクトルメッセージは、宛先変数ノード以外の近傍変数ノードからの以前のラウンドのＶ２Ｃメッセージに基づいて、ガロア体内のシンボルｄごとに、宛先変数ノードがそのシンボルｄを含む確率を含む。チェックノードにおいて特定の近傍変数ノード用のＣ２Ｖメッセージを生成するのに用いられる近傍変数ノードからの入力は外部入力と呼ばれ、正のフィードバックを回避するために、Ｃ２Ｖメッセージが準備されている特定の近傍変数ノードを除く全ての近傍変数ノードからの以前のラウンドのＶ２Ｃメッセージを含む。このため、チェックノードは、宛先変数ノードに基づいてメッセージごとに異なる１組の外部入力を用いて近傍変数ノードごとに異なるＣ２Ｖメッセージを準備する。
【００２３】
本明細書において開示される、単純化された最小和復号化とも呼ばれる最小和に基づく復号化において、チェックノードは、近傍変数ノードからの全ての外部Ｖ２Ｃメッセージに基づいてガロア体内の非ゼロシンボルｄごとに、最小部分メッセージｍｉｎ１（ｄ）、ｍｉｎ１（ｄ）のインデックスｉｄｘ（ｄ）、及び準最小部分メッセージｍｉｎ２（ｄ）、すなわちｍｉｎ１（ｄ）を除外する全ての部分メッセージの最小値を計算する。換言すれば、特定のシンボルｄについての部分メッセージが全ての外部入力からのメッセージから収集され、そのシンボルｄについて収集された部分メッセージに基づいてｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）が計算される。値ｍｉｎ１（ｄ）は部分メッセージの最小値であり、ｉｄｘ（ｄ）はｍｉｎ１（ｄ）の部分メッセージインデックスであり、ｍｉｎ２（ｄ）は次に最小のすなわち準最小の部分メッセージであり、ｍｉｎ１（ｄ）を除外する全ての部分メッセージの最小値である。２ｐ−１個のシンボルを有するガロア体の場合、チェックノードは、最も可能性の高いシンボルを除く体内のｐ−１個の非ゼロシンボルのそれぞれについてｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の部分メッセージを計算する。ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の値はＣ２Ｖメッセージを計算する際に用いるようにメモリ内に記憶される。これは、各中間の順方向及び逆方向メッセージを記憶する従来の非バイナリチェックノードプロセッサよりも必要とするメモリがはるかに少ない。
【００２４】
図２に戻ると、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器２００のブロック図が示されている。図２のブロック図は、変数ノードプロセッサ２０２とチェックノードプロセッサ２０４との間の処理フローを示している。図２におけるように、複数の変数ノード及びチェックノードを単一の変数ノードプロセッサ２０２及びチェックノードプロセッサ２０４内に実装することができる。他の実施形態では、例えばタナーグラフ内の変数ノード及びチェックノードの数に直接対応する変数ノードプロセッサ及びチェックノードプロセッサの数を有する複数の変数ノードプロセッサ及びチェックノードプロセッサを備えることができる。最小和に基づく非バイナリ低密度パリティチェック復号化器２００はいかなる特定のトポロジーにも限定されず、任意の数の特定の用途の要件を満たすように適合させることができる。本明細書において提供される開示に基づいて、当業者であれば、現在既知のもの及び将来開発することができるもの双方の、最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化に適合させることができる多岐にわたる低密度パリティチェック回路を認識するであろう。
【００２５】
最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器２００に、入力チャネル２０６からの対数尤度比値が与えられ、これは対数尤度比メモリ２１０に記憶することができる。上記で検討したように、他の実施形態では、対数尤度比値ではなく簡易尤度確率値が用いられる。値は変数ノードプロセッサ２０２に与えられ、変数ノードプロセッサ２０２は入力チャネル２０６からの値と近傍チェックノードプロセッサ（例えば２０４）からのＣ２Ｖメッセージベクトルとに基づいて、変数ノードプロセッサ２０２に対応するシンボルの認識される値を更新する。変数ノードプロセッサ２０２は、チェックノードプロセッサ（例えば２０４）における近傍チェックノード用のＶ２Ｃメッセージベクトル２１２も生成する。Ｖ２Ｃメッセージベクトル２１２はメッセージフォーマット変換器２１４に与えられ、メッセージフォーマット変換器２１４はＶ２Ｃメッセージベクトル２１２のフォーマットを２つの部分、すなわち最も可能性の高いシンボル又は硬判定と、最も可能性の高いシンボルに正規化された他のシンボルの対数尤度比とからなるフォーマットに変換し、第２のフォーマットでの正規化されたＶ２Ｃメッセージベクトル２１６を得る。正規化されたＶ２Ｃメッセージベクトル２１６はエッジインターリーバー２２０に与えられ、エッジインターリーバー２２０はメッセージエッジにおける境界上でメッセージをシャッフルし、メッセージ間の雑音をランダム化し、依存関係を断つ。インターリーブされ正規化されたＶ２Ｃメッセージベクトル２２２はチェックノードプロセッサ２０４に提供され、チェックノードプロセッサ２０４は他の近傍変数ノードからの外部Ｖ２Ｃメッセージに基づいて近傍変数ノードプロセッサごとにＣ２Ｖメッセージ２２４を生成する。チェックノードプロセッサ２０４は、変数ノードプロセッサ２０２からの外部Ｖ２Ｃメッセージに基づいて、最小和に基づくアルゴリズムを用いてＣ２Ｖメッセージ２２４を生成する。チェックノードプロセッサ２０４はＶ２Ｃメッセージ２２２及びＣ２Ｖメッセージ２２４の写像又は変換も行い、Ｖ２Ｃメッセージ２２２及びＣ２Ｖメッセージ２２４がガロア体ＧＦ（２ｑ）においてサイズ２ｑ−１を有するようにする。ただし、チェックノードプロセッサ２０４はＧＦ（２ｐ）領域において最小和に基づく処理を実行し、チェックノードプロセッサ２０４におけるｍｉｎ１メッセージ及びｍｉｎ２メッセージはガロア体ＧＦ（２ｐ）においてサイズ２ｐ−１を有する。
【００２６】
チェックノードプロセッサ２０４は変換回路２４２を備える。変換回路２４２は、Ｖ２Ｃメッセージ２２２をガロア体ＧＦ（２ｑ）から変換し、ＧＦ（２ｐ）領域において変換されたＶ２Ｃメッセージ２４４を得る。変換されたＶ２Ｃメッセージ２４４は最小値発見器回路２４６に提供され、最小値発見器回路２４６は、ガロア体内のｑ個のシンボルのそれぞれについて、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の部分メッセージ２５０を計算する。選択回路２５２は部分メッセージ２５０から外部メッセージを選択し、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の外部メッセージを含む中間出力メッセージＡ（ｄ）２５４を得る。結合回路２５６は中間出力メッセージＡ（ｄ）２５４において外部メッセージを結合し、Ｃ２Ｖメッセージ２６０を得る。変換／再正規化回路２６２は、Ｃ２Ｖメッセージ２６０をＧＦ（２ｐ）領域から逆関数が利用可能なＧＦ（２ｑ）領域に変換し、逆関数が利用可能でないＧＦ（２ｑ）領域においてＣ２Ｖメッセージ２６０を再正規化し、ＧＦ（２ｑ）領域におけるＣ２Ｖメッセージ２２４を得る。これによって、変数ノードプロセッサ２０２及びチェックノードプロセッサ２０４においてガロア体サイズが異なるハイブリッド演算が可能になる。
【００２７】
Ｃ２Ｖメッセージ２２４はエッジデインターリーバー２２６に与えられ、エッジデインターリーバー２２６はエッジインターリーバー２２０のプロセスを逆に行い、次にこれがフォーマット復元回路２３０に与えられ、フォーマット復元回路２３０はメッセージベクトルを第２の正規化されたフォーマットから変数ノードプロセッサ２０２の第１のメッセージベクトルフォーマットに変換し、メッセージフォーマット変換器２１４のプロセスを逆に行う。結果として得られる第１のフォーマットのＣ２Ｖメッセージ２３２は変数ノードプロセッサ２０２に与えられ、変数ノードにおいて認識される対数尤度比値を更新するのに用いられる。他の実施形態では、変数ノードプロセッサ２０２は、第２の正規化されたフォーマットのメッセージベクトルを直接用いて演算するように適合される。これらの実施形態では、メッセージフォーマット変換器２１４及びフォーマット復元回路２３０は省かれる。
【００２８】
最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器２００における値が収束し安定するか、又は局所反復数について制限に達すると、変数ノードプロセッサ２０２は合計対数尤度比Ｓｎ（ａ）２３４を判定回路２３６に与え、合計対数尤度比Ｓｎ（ａ）のａｒｇｍｉｎａに基づいて硬判定２４０が生成される。
【００２９】
認識される対数尤度比値Ｌｊ（ａ）は、変数ノードプロセッサ２０２において実装される変数ノードにおいて既知であり、外部対数尤度比メモリ２１０内に記憶されているか又は入力チャネル２０６における測定値からそれらをオンザフライで計算することによって既知である。認識される対数尤度比値Ｌｊ（ａ）は式１を用いて計算される。
式１：
【数１】
2014183569.tif 000003
ここで、ｘｊはチャネルからの測定値ａに基づくコードシンボルであり、ｓｊは、ｊ番目のチェックノードについて計算された、コードシンボルｘｊの最も可能性の高いガロア体シンボルである。
【００３０】
確率の乗算及び除算を回避するために、ガロア体内の各要素が独自の値を有するように対数確率又は対数尤度比（ＬＬＲ）が用いられる。変数ノードプロセッサ２０２は、Ｃ２Ｖメッセージベクトル内の要素ごとに、到来する全てのＣ２ＶメッセージベクトルＲ’ｉ，ｊ＝［Ｒ’ｉ，ｊ（０）．．．Ｒ’ｉ，ｊ（ｑ−１）］にわたって対数尤度比値の和を計算する。次に、変数ノードプロセッサ２０２は、対数尤度比の和からそのチェックノードからの対数尤度比値を減算し、ｈｉ，ｊによる有限体乗算に従ってベクトルエントリを置換することによって、各近傍チェックノードに対しＶ２Ｃメッセージベクトル２１２  Ｑ’ｉ，ｊ＝［Ｑ’ｉ，ｊ（０）．．．Ｑ’ｉ，ｊ（ｑ−１）］を生成する。ｑ個の対数尤度比値によって形成されるこのベクトルフォーマットは、本明細書において第１のフォーマット又はフォーマットＩと呼ばれる。Ｖ２Ｃメッセージベクトル２１２は変数ノードプロセッサ２０２において式２及び式３に従って計算される。
式２：
【数２】
2014183569.tif 000004
ここで、Ｓｊ（ａ）は対数尤度比和であり、Ｌｊ（ａ）は変数ノードｊにおいて認識される対数尤度比値であり、
【数３】
2014183569.tif 000005
は全てのチェックノードからの対数尤度比である。
式３：
【数４】
2014183569.tif 000006
【数５】
2014183569.tif 000007
は変数ノードがメッセージを生成しているチェックノードからの以前のラウンドの対数尤度比である。
【００３１】
メッセージフォーマット変換器２１４は対数尤度比値が範囲を超えることを防ぐようにそれらを正規化し、最も可能性の高いシンボルに対しそれらを正規化する。正規化されたＶ２Ｃメッセージベクトル２１６（及び同様に正規化されたＣ２Ｖメッセージベクトル２２８）は、本明細書においてフォーマットＩＩとも呼ばれる第２のフォーマットをとり、このフォーマットは２つの部分、すなわち最も可能性の高いシンボルと、他のシンボルの対数尤度比とを含む。なぜなら、最も可能性の高いシンボルは正規化後に０に等しい対数尤度比を有するためである。これらのフォーマットＩＩの対数尤度比値は、正規化されたＶ２Ｃメッセージベクトル２１６においてＱｉ，ｊ＝［Ｑ＊ｉ，ｊ（０），Ｑｉ，ｊ（１）．．．Ｑｉ，ｊ（ｑ−１）］として表され、正規化されたＣ２Ｖメッセージベクトル２２８においてＲｉ，ｊ＝［Ｒ＊ｉ，ｊ（０），Ｒｉ，ｊ（１）．．．Ｒｉ，ｊ（ｑ−１）］として表される。ここで、Ｑ＊ｉ，ｊ（０）及びＲ＊ｉ，ｊ（０）は最も可能性の高いシンボルであり、Ｑｉ，ｊ（１）．．．Ｑｉ，ｊ（ｑ−１）及びＲｉ，ｊ（１）．．．Ｒｉ，ｊ（ｑ−１）は、それぞれ最も可能性の高いシンボルＱ＊ｉ，ｊ（０）及びＲ＊ｉ，ｊ（０）に正規化されたガロア体の残りのｑ−１個の要素の対数尤度比値である。メッセージの正規化によって対数尤度比値が変化するのみでなく、対数尤度比の順序も、絶対順序から最も可能性の高いシンボルに対する相対順序に変化することに留意されたい。このため、Ｑ’ｉ，ｊ（ａ）及びＳｉ，ｊ（ａ）はａ∈ＧＦ（ｑ）の絶対順序にある。フォーマットＩＩの対数尤度比値Ｑｉ，ｊ（ｄ）及びＲｉ，ｊ（ｄ）はそれぞれ最も可能性の高いシンボルＱ＊ｉ，ｊ及びＲ＊ｉ，ｊ（ａ）を用いた
【数６】
2014183569.tif 000008
の相対順序にある。
【００３２】
図３に進むと、本発明の１つ又は複数の実施形態による、変換回路２４２の代わりに用いるのに適した変換回路３００が開示されている。ここでもまた、Ｖ２Ｃメッセージ（軟値３０２及び硬判定３１０を含む）はＧＦ（２ｐ）領域内に２ｑ個の値を含むのに対し、チェックノードプロセッサはＧＦ（２ｑ）領域において最小和演算を実行する。変換回路３００は、ｈ＿｛ｉ，ｊ｝、すなわちパリティチェック行列Ｈ内のエントリを用いて、これをＧＦ（２ｐ）に変換する。結果として得られる軟値３０６は、ａ＝１．．．（２ｑ−１）についてｖ２ｃｔ（ｈ＿｛ｉ，ｊ｝＊ａ）＝ｖ２ｃ（ａ）又はｖ２ｃｔ（ｂ）＝ｍａｘとして計算され、硬判定３１４は、バイナリ形式を用いて写像を計算し、次にＧＦ（２ｐ）領域に戻して変換することによりｖ２ｃｔ＿ｈｄ＝ｈ＿｛ｉ，ｊ｝＊ｖ２ｃ＿ｈｄとして計算される。この硬判定計算は上記で開示したｂ＝ｈ＊ａのバイナリ行列乗算に対応する。２ｑ−１個のメッセージ３０２及び硬判定３１０は、マルチプレクサーアレイ３０４及び硬判定変換器３１２を用いて２ｐ−１個のメッセージ３０６及び硬判定３１４に直接変換される。より多くの利用可能な出力値３０６が存在するので、２ｐ−１個のメッセージ３０６内の追加の又は写像されていないメッセージが最大対数尤度比値（ｖ２ｃｔ（ｂ）＝ｍａｘ）に設定される。写像されていないメッセージを最大値に設定することによって、これらはチェックノードプロセッサにおけるｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の計算に影響を与えない。
【００３３】
チェックノードプロセッサは、ＧＦ（２ｐ）内の非ゼロシンボルａごとにｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の値の組を保持し、それらを軟値３０６及び硬判定３１４においてｖ２ｃｔ（ｄ）値を用いて更新する。このため、ＧＦ（２ｐ）内のａごとに、ＧＦ（２ｐ）内の（ｈ＿｛１，ｊ｝＊ａ）についてのみｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の値の組がｖ２ｃｔ（ｈ＿｛ｉ，ｊ｝＊ａ）によって更新される。他の組は、更新されていないかのように最大値によって更新される。いくつかの実施形態では、非ハイブリッド符号化器において用いられているようにｖ２ｃｔ＿ｈｄ３１４が用いられ、このためシンドロームＳ＿ｉがチェックノードごとに全ての接続された変数ノードのｖ２ｃｔ＿ｈｄの和から計算される。非ハイブリッド復号化器はシンドロームＳ＿ｉ及びｖ２ｃｔ＿ｈｄを用いてｃ２ｖｔ＿ｈｄ＝Ｓ＿ｉ＋ｖ２ｃｔ＿ｈｄを計算する。これは、チェックノードプロセッサにおいて内部で最小和計算に用いられる一時的な値である。ｃ２ｖｔ＿ｈｄはＧＦ（２ｐ）領域内にある。非ハイブリッド復号化器における逆再配列と同様に、チェックノードプロセッサからの結果はＧＦ（２ｑ）領域に戻して変換されるが、チェックノードプロセッサにおけるガロア体は変数ノードプロセッサにおけるガロア体よりも大きいので、全ての硬判定値の逆関数が存在しない場合がある。そのような場合、変換／再正規化回路２６２において適用される逆変換が再正規化によって実行される。
【００３４】
図４を参照すると、本発明の１つ又は複数の実施形態による、最小値発見器回路２４６、選択回路２５２、結合回路２５６及び変換回路２６２の代わりに用いるのに適した最小値発見器、選択及び結合回路４００が開示されている。最小値発見器、選択及び結合回路４００によって実行される機能は、単一の回路において実行することもできるし、複数の別個の回路にわたって機能を分割することもできる。２ｐ−１個の軟値４０４及び硬判定４０６を含む変換されたＶ２Ｃメッセージ４０２が、最小値発見器、選択及び結合回路４００の最小値発見器部４０８において処理される。この最小値発見器部４０８は、いくつかの実施形態において、最小値発見器回路２４６の機能を実行する。最小値発見器部４０８は、２ｐ−１個の軟値４０４を処理して、２ｐ−１個の軟値４０４のそれぞれについてｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の値４１６を生成するように動作可能な複数のｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の発見回路４１０、４１２、４１４を備える。
【００３５】
最小値発見器部４０８は、各近傍変数ノードからのメッセージベクトルにおける部分メッセージＱｉ，ｊｋ（ｄ）に基づいて、比較器及びバッファーを用いて各近傍変数ノードからの各メッセージベクトルを通じて反復的に走査することにより、２ｐ−１個の軟値４０４のそれぞれについて、ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の部分メッセージ４１６を計算する。最小値発見器部４０８におけるｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の発見回路４１０、４１２、４１４の演算は、以下の論理文並びに式４、式５及び式６において説明することができる。
【数７−１】
2014183569.tif 000009
式４，５，６：
【数７−２】
2014183569.tif 000010
【００３６】
硬判定４０６、すなわち各近傍変数ノードからの各メッセージベクトルのシンボル部分は、ＸＯＲ回路４１８及びメモリ４２０において処理される。変換されたＶ２Ｃメッセージ２４４における最も可能性の高いシンボル
【数８】
2014183569.tif 000011
のそれぞれがＸＯＲ回路４１８に提供され、ＸＯＲ回路４１８においてともにＸＯＲされる。中間チェックサム結果が第１の硬判定４２２とともにメモリ４２０に記憶され、硬判定Ｐｉ４２４が得られ、これによって、式７に従ってｋ＝１．．．ρｉについてチェックサムを計算し、式８に従って硬判定
【数９】
2014183569.tif 000012
を計算する。
式７，８：
【数１０】
2014183569.tif 000013
【００３７】
選択回路２５２及び結合回路２５６はＧＦ（２ｐ）領域において演算を行うが、ＧＦ（２ｐ）内の全てのシンボルをＣ２Ｖメッセージ２２４においてＧＦ（２ｑ）領域に逆写像することができるわけではない。したがって、選択回路２５２及び結合回路２５６は、接続された変数ノードごとのエントリ値に依拠して、ＧＦ（２ｐ）内の全てのｂについてメッセージ計算を実行する必要はない。逆元を有する全ての２ｑ−１個の非ゼロシンボルがｈ＿｛ｉ，ｊ｝に従って列挙される。リスト内のシンボルごとにａ＋ｃ２ｖｔ＿ｈｄが計算される。任意のａ＋ｃ２ｖｔ＿ｈｄが０に等しい場合、ａ＝ｃ２ｖｔ＿ｈｄは真の硬判定であり、すなわち、ｃ２ｖ＿ｈｄ＝ｃ２ｖｔ＿ｈｄである。この組ａを除いて、全ての他のシンボルが選択回路２５２及び結合回路２５６において処理される。そのようなシンボルが存在しない場合、全てのシンボルが選択回路２５２及び結合回路２５６において処理される必要がある。その場合、ｃ２ｖｔ＿ｈｄは逆元を有せず、このため真の硬判定ではないので、真の硬判定を発見するために再正規化が必要とされる。
【００３８】
ｍｉｎ１（ｄ）、ｉｄｘ（ｄ）及びｍｉｎ２（ｄ）の値４１６が、いくつかの実施形態において選択回路２５２の置き換えとして用いるのに適した選択回路４２６において処理される。１〜ρｉのｋの値についてｊｋ＝Ｎｉ（ｋ）である場合、選択回路４２６において近似メッセージ４２８が計算され、現在の変数ノードからのメッセージを回避する目的で、ｋ≠ｉｄｘ（ｄ）の場合、ｍｉｎ１（ｄ）が選択され、ｋ＝ｉｄｘ（ｄ）の場合、ｍｉｎ２（ｄ）が選択される。選択は、ｋの値を通じて巡回するインデックス入力によって制御される２ｐ−１個の選択器回路４３０、４３２、４３４の群において実行される。２ｐ−１個の選択器回路４３０、４３２、４３４は２ｐ−１個の近似メッセージ出力Ａ（１）（ｄ）４２８を生成する。出力Ａ（ｄ）は、ｋ≠ｉｄｘ（ｄ）の場合、ｍｉｎ１（ｄ）に設定され、ｋ＝ｉｄｘ（ｄ）の場合、ｍｉｎ２（ｄ）に設定される。この選択演算は、擬似コード文ｓｅｌｅｃｔ  ｉｄｘ＝＝ｋ？Ｂ：Ａによっても表すことができる。ここで、Ａ及びＢは特定のガロア体要素の最小対数尤度比値及び準最小対数尤度比値であり、ｉｄｘは最小対数尤度比値及び準最小対数尤度比値を与えた変数ノードを特定する入力であり、ｋは各変数ノードを通じて循環する変数である。
【００３９】
近似メッセージＡ（１）（ｄ）４２８は第１の結合回路４３６において処理され、２ｐ−１個の出力Ａ（２）（ｄ）４３８が得られる。中間出力メッセージＡ（２）（ｄ）４３８は第２の結合回路４４０に提供され、２ｑ−１個の出力ｃ２ｖｍ，１（ｄ）４４２が得られる。第１の結合回路４３６及び第２の結合回路４４０は、本発明のいくつかの実施形態において、結合回路２５６の置き換えとして用いるのに適しており、第２の結合回路４４０は変換／再正規化回路２６２の変換機能も実行する。
【００４０】
図５を参照すると、本発明の１つ又は複数の実施形態による第１の結合回路４３６の置き換えとして用いるのに適した第１の結合回路５００の一実施形態が開示されている。チェックノードプロセッサにおける全てのメッセージを変数ノードプロセッサに戻してマッピングすることができるわけではないので、チェックノードプロセッサにおける計算は、より小さな変数ノードプロセッサガロア体にマッピングしてそれにより回路面積を低減することができるメッセージを含むことしか必要としない。ｍｉｎ１及びｍｉｎ２の値は２ｐ−１個の近似メッセージＡ（１）（ｄ）５０２にロードされ、レジスターに記憶される。並び替えネットワーク５０４を用いて近似メッセージＡ（１）（ｄ）５０２の並び替え又は置換を行い、並び替えされた近似メッセージＡ（１）（ｄ＋ｂ）５０６を得る。ここで、ｂ５０３は０から２ｐ−１に掃引されるインデックス値として用いられるシンボルである。要素ｂごとに、ａ個のメッセージの順序が並び替えられ、ｂ個のメッセージと結合される。複数の加算器５１０が対数尤度比値の各対を結合し、これらは次に比較器５１２において比較され、最小値が選択され、２ｐ−１個の出力Ａ（２）（ｄ）５１４が得られる。全ての可能な値を通じてｂを掃引することによって、第１の結合回路５００が２ｐ−１個の近似メッセージＡ（１）（ｄ）５０２においてｍｉｎ１及びｍｉｎ２の値の全ての可能な組合せを加算する。他の実施形態では、ｂの値を掃引するのではなく、加算器のツリー構造を用いて、第１の結合回路５００によって実行される機能をより短い時間で、ただしより大きな回路を用いて完了する。
【００４１】
図６を参照すると、本発明の１つ又は複数の実施形態による第２の結合回路４４０の置き換えとして用いるのに適した第２の結合回路６００の一実施形態が開示されている。チェックノードプロセッサ内の全てのメッセージを変数ノードプロセッサに戻してマッピングすることができるわけではないので、チェックノードプロセッサにおける計算は、より小さな変数ノードプロセッサガロア体にマッピングしてそれにより回路面積を低減することができるメッセージを含むことしか必要としない。いくつかの実施形態では、（例えば図５の５１４からの）Ａ（２）（ｄ）値６０２はレジスターに記憶される。選択及び並び替えネットワーク６０６を用いてＡ（２）（ｄ）値６０２の並び替え又は置換を行い、並び替えされた近似メッセージＢ（ｄ＋ｂ）６１０を得る。ここで、ｂ６１２は０から２ｑ−１に掃引されるインデックス値として用いられるシンボルである。選択及び並び替えネットワーク６０６は、ｈｍ，ｊ，ｃ２ｖｔ＿ｈｄ値６０８に基づいて２ｐ−１個の入力メッセージから２ｑ個の出力メッセージ６０４を選択し並び替える。ここで、ｈｍ，ｊはｐ×ｑのバイナリ行列である。換言すれば、ＧＦ（２ｑ）におけるｂ＝０，１，．．．２ｑ−１について、選択及び並び替えネットワーク６０６はＢ（ｂ）＝Ａ（２）（ｈ＿｛ｍ，ｊ｝＊ｂ＋ｖ２ｃｔ＿ｈｄ）を選択し，Ｂ（ｂ＋１）＝Ａ（２）（ｈ＿｛ｍ，ｊ｝＊（ｂ＋１）＋ｖ２ｃｔ＿ｈｄ）を選択し、以下同様である。ｈｍ，ｊ６０８は線形群内の要素であり、このため変数ノードフィールドからチェックノードフィールドへの写像を実行する。並び替えられた近似メッセージＢ（ｄ＋ｂ）６１０は、加算器６１２においてｂを０から２ｑ−１に掃引することによって各可能な組合せにおいて互いに加算され、比較器６１４を用いて最小値が発見され、２ｑ個のＣ２Ｖ出力６０４が得られる。したがって、Ｃ２Ｖ（ａ）はＣ２Ｖ（ａ）＝ｍｉｎ＿｛ｂ＝０．．２ｑ−１｝（Ｂ（ａ）＋Ｂ（ｂ＋ａ））として計算される。
【００４２】
変換／再正規化回路２６２によって実行される再正規化は、必要な場合、ＧＦ（２ｑ）内のａごとにｃ２ｖｔ（ａ）〜ｃ２ｖｔ（ｈ＿｛ｉ，ｊ｝＊ａ）を設定する。このフォーマットでは、硬判定は存在せず、変数ノードプロセッサにおいてゼロパディングを含めてＣ２Ｖメッセージのフォーマットを変更することができる。
【００４３】
次に図７を参照すると、流れ図７００が本発明のいくつかの実施形態による最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化の方法を示している。図７の方法又はその変形形態は、図１〜図６に示すようなデータ復号化回路において実行することができる。流れ図７００によれば、認識されるシンボルは最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器においてチャネル値を用いて変数ノードごとに初期化される（ブロック７０２）。認識される値及び外部Ｃ２Ｖメッセージベクトルに基づいて、変数ノードについてＶ２Ｃメッセージベクトルが生成される（ブロック７０４）。いくつかの実施形態では、Ｖ２Ｃメッセージベクトルのフォーマットが変換され、対数尤度比値が最も可能性の高いシンボルの対数尤度比値に対し正規化される（ブロック７０６）。いくつかの実施形態では、エッジインターリーバーにおいてＶ２Ｃメッセージベクトルがインターリーブされる（ブロック７１０）。メッセージは変数ノードガロア体からチェックノードガロア体に変換される（ブロック７１２）。チェックノードごとにチェックサム及び硬判定が計算される（ブロック７１４）。最小値、最小値のインデックス及び次の最小値も、各チェックノードにおいてガロア体の要素ごとに外部Ｖ２Ｃメッセージベクトルに基づいて計算される（ブロック７１６）。硬判定を含めて（including）、ガロア体の要素ごとに最小値、最小値のインデックス及び準最小値を選択し結合して対数尤度比値を形成することによって、チェックノードごとにＣ２Ｖメッセージベクトルが生成され、チェックノードガロア体から変数ノードガロア体にメッセージが変換される（ブロック７２０）。いくつかの実施形態では、Ｃ２Ｖメッセージベクトルがデインタリーブされ、ブロック７１０のインターリーブが逆にされる（ブロック７２２）。いくつかの実施形態では、Ｃ２Ｖメッセージベクトルのフォーマットが復元され、ブロック７０６のフォーマット変換が逆にされる（ブロック７２４）。値が収束するか又は局所反復の制限に達するまで、反復が継続し、メッセージベクトルが生成され、変数ノードとチェックノードとの間で渡される。
【００４４】
最小和に基づくハイブリッド非バイナリ低密度パリティチェック復号化器はいかなる特定の用途にも限定されないが、本発明の実施形態から利益を受ける用途の幾つかの例が本明細書において提示される。図８を参照すると、アナログ信号８０２を処理し、アナログ信号８０２から誤りを伴うことなくユーザーデータビットを取り出すのに読取りチャネル８００が用いられる。いくつかの場合には、アナログ信号８０２は磁気記憶媒体における読取り／書き込みヘッドアセンブリから取り出される。他の場合には、アナログ信号８０２は、伝送媒体から信号を受信するように動作可能な受信機回路から取り出される。伝送媒体は、限定ではないがケーブル接続又は光接続等、有線又は無線とすることができる。本明細書において提供される開示に基づいて、当業者であれば、アナログ信号８０２を取り出すことができる多岐にわたるソースを認識するであろう。
【００４５】
読取りチャネル８００は、アナログ信号８０２を受信し処理するアナログフロントエンド８０４を含む。アナログフロントエンド８０４は、限定ではないが、当該技術分野において既知のアナログフィルター及び増幅器回路を含むことができる。本明細書において提供される開示に基づいて、当業者であれば、アナログフロントエンド８０４の一部として含めることができる多岐にわたる回路を認識するであろう。いくつかの場合には、アナログフロントエンド８０４の一部として含まれる可変利得増幅器の利得は変更可能とすることができ、アナログフロントエンド８０４に含まれるアナログフィルターのカットオフ周波数及びブーストは変更可能とすることができる。アナログフロントエンド８０４はアナログ信号８０２を受信及び処理し、処理されたアナログ信号８０６をアナログ／デジタル変換器８１０に提供する。
【００４６】
アナログ／デジタル変換器８１０は処理されたアナログ信号８０６を対応する一連のデジタルサンプル８１２に変換する。アナログ／デジタル変換器８１０は、アナログ入力信号に対応するデジタルサンプルを生成することが可能な当該技術分野において既知の任意の回路とすることができる。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に関連して用いることができる多岐にわたるアナログ／デジタル変換器回路を認識するであろう。デジタルサンプル８１２が等化器８１４に提供される。等化器８１４は等化アルゴリズムをデジタルサンプル８１２に適用し、等化出力８１６を得る。本発明のいくつかの実施形態では、等化器８１４は当該技術分野において既知のデジタル有限インパルス応答フィルター回路である。等化出力８１６に含まれるデータ又は符号語は、データ検出器８２０が処理に利用可能になるまでバッファー８１８内に記憶することができる。
【００４７】
データ検出器８２０は受信した入力に対しデータ検出プロセスを実行し、結果として検出された出力８２２が得られる。本発明のいくつかの実施形態では、データ検出器８２０はビタビアルゴリズムデータ検出器回路であるか、より具体的には、いくつかの場合には、当該技術分野において既知の最大事後（ＭＡＰ：maximum a posteriori）データ検出器回路である。これらの実施形態のうちのいくつかでは、検出された出力８２２は、各ビット又はシンボルが特定の値を有する尤度に関する対数尤度比軟情報を含む。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に関連して用いることができる多岐にわたるデータ検出器を認識するであろう。データ検出器８２０は、バッファー８１８内のデータセットが等化器８１４又は別のソースから入手可能であることに基づいて始動される。
【００４８】
データ検出器８２０からの検出された出力８２２が、バーストエラーに対しデータを保護するインターリーバー８２４に提供される。バーストエラーは局所的なビット群又はビット塊を上書きする。低密度パリティチェック復号化器はより均一に分散した誤りを訂正するのに最も適しているので、バーストエラーは低密度パリティチェック復号化器を凌ぐ可能性がある。インターリーバー８２４は、データ検出器８２０からの検出された出力８２２をインターリーブ又はシャッフリングしてインターリーブされた出力８２６を得ることによってこれを回避する。インターリーブされた出力８２６はメモリ８３０に記憶される。メモリ８３０からのインターリーブされた出力８２６は柔軟な飽和を用いた低密度パリティチェック復号化器８３２に提供され、低密度パリティチェック復号化器８３２はインターリーブされた出力８２６に対しパリティチェックを実行し、記憶若しくは伝送中、又は読取りチャネル８００の他の構成要素による処理中にデータにおいて生じた可能性がある任意の誤りを検出し訂正するために、記憶又は伝送前に低密度パリティチェック符号化器（図示せず）によって確立されたパリティ制約が満たされていることを確保する。
【００４９】
検出及び符号化の複数の反復を読取りチャネル８００において実行することができ、これは本明細書において大域反復と呼ばれる。（対照的に、局所反復は低密度パリティチェック復号化器８３２内で実行される復号化反復である。）大域反復を実行するために、低密度パリティチェック復号化器８３２からの対数尤度比値８３４がメモリ８３０に記憶され、デインターリーバー８３６においてデインタリーブされてインターリーバー８２４によって適用されたプロセスが逆に行われ、再びデータ検出器８２０に提供されて、データ検出器８２０が低密度パリティチェック復号化器８３２からの対数尤度比値８３４によって支援されたデータ検出プロセスを繰り返すことが可能になる。このようにして、読取りチャネル８００は複数の大域反復を実行し、データ検出器８２０及び低密度パリティチェック復号化器８３２が正しいデータ値に収束することを可能にすることができる。
【００５０】
低密度パリティチェック復号化器８３２は、インターリーバー８２４のインターリーブされた出力８２６に含まれるデータビット又はシンボルの値に関する硬判定８４０も生成する。低密度パリティチェック復号化器８３２からの硬判定８４０は硬判定デインターリーバー８４２においてデインタリーブされ、インターリーバー８２４において適用されたプロセスが逆に行われ、硬判定メモリ８４４に記憶され、その後ユーザーに提供されるか又は更に処理される。例えば、読取りチャネル８００の出力８４６を更に処理して、適用されたフォーマット変更を逆に行い、その後データを磁気記憶媒体に記憶するか又は伝送チャネルにわたってデータを送信することができる。
【００５１】
図９を参照すると、本発明のいくつかの実施形態によるハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータシステムの応用形態例として記憶システム９００が示されている。記憶システム９００は、本発明のいくつかの実施形態よるハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータ処理システムを有する読取りチャネル回路９０２を備える。記憶システム９００は、例えば、ハードディスクドライブとすることができる。記憶システム９００は、前置増幅器９０４、インターフェースコントローラー９０６、ハードディスクコントローラー９１０、モーターコントローラー９１２、スピンドルモーター９１４、ディスクプラッター９１６、及び読取り／書込みヘッド９２０も備える。インターフェースコントローラー９０６はディスクプラッター９１６への／からのデータのアドレス指定及びタイミングを制御する。ディスクプラッター９１６上のデータは、アセンブリがディスクプラッター９１６上に適切に位置決めされているときに読取り／書込みヘッドアセンブリ９２０によって検出することができる磁気信号の群からなる。１つの実施形態では、ディスクプラッター９１６は長手記録方式又は垂直記録方式のいずれかに従って記録される磁気信号を含む。
【００５２】
通常の読取り動作において、読取り／書込みヘッドアセンブリ９２０はモーターコントローラー９１２によって、ディスクプラッター９１６上の所望のデータトラックの上方に正確に位置決めされる。モーターコントローラー９１２は、ハードディスクコントローラー９１０の指示の下で読取り／書込みヘッドアセンブリ９２０をディスクプラッター９１６上の適切なデータトラックに移動することによって、ディスクプラッター９１６に対して読取り／書込みヘッドアセンブリ９２０を位置決めし、かつスピンドルモーター９１４を駆動する。スピンドルモーター９１４は所定のスピンレート（ＲＰＭ）でディスクプラッター９１６をスピンさせる。読取り／書込みヘッドアセンブリ９２０が適切なデータトラックに近接して位置決めされると、ディスクプラッター９１６がスピンドルモーター９１４によって回転するのに応じてディスクプラッター９１６上のデータを表す磁気信号が読取り／書込みヘッドアセンブリ９２０によって感知される。感知された磁気信号は、ディスクプラッター９１６上の磁気データを表す連続した微小アナログ信号として与えられる。この微小アナログ信号は、読取り／書込みヘッドアセンブリ９２０から、前置増幅器９０４を介して、読取りチャネル回路９０２に送信される。前置増幅器９０４は、ディスクプラッター９１６からアクセスされた微小アナログ信号を増幅するように動作可能である。そして、読取りチャネル回路９０２は受信したアナログ信号を復号及びデジタル化し、ディスクプラッター９１６に元々書き込まれた情報を再生する。このデータは、読取りデータ９２２として受信回路に与えられる。読取りチャネル回路９０２は、読取りデータを処理する間、ペナルティベースの多変量符号化を用いたデータ処理システムを用いて受信信号を処理する。ハイブリッド非バイナリ低密度パリティチェック復号化器を有するそのようなデータ処理システムは、図１〜図７に開示した回路及び方法に沿って実装することができる。書込み動作は実質的に、先行する読取り動作の反対であり、書込みデータ９２４が読取りチャネル回路９０２に与えられる。次にこのデータは符号化され、ディスクプラッター９１６に書き込まれる。
【００５３】
例えば安価なディスクの冗長アレイ又は独立ディスクの冗長アレイ（ＲＡＩＤ：redundant array of inexpensive disks又はredundantarray of independent disks）に基づく記憶システム等のより大型の記憶システムに、記憶システム９００を統合することができることに留意するべきである。このようなＲＡＩＤ記憶システムは、複数のディスクを論理ユニットとして結合し、冗長性を通じて安定性及び信頼性を増大させる。データは、種々のアルゴリズムに従って、ＲＡＩＤ記憶システムに含まれる複数のディスクにわたって拡散させることができ、ＲＡＩＤ記憶システムが単一のディスクであるかのようにオペレーティングシステムがアクセスすることができる。例えば、データはＲＡＩＤ記憶システム内の複数のディスクにミラーリングすることもできるし、複数の技法において複数のディスクにわたってスライスし分散させることもできる。ＲＡＩＤ記憶システム内の少数のディスクが故障するか又は利用不可能になる場合、誤り訂正技法を用いて、ＲＡＩＤ記憶システム内の他のディスクからのデータの残りの部分に基づいて、欠落データを再生することができる。ＲＡＩＤ記憶システム内のディスクは、限定ではないが、記憶システム９００等の個別の記憶システムとすることができ、互いに近接して配置することもできるし、セキュリティを増大させるために、より広範に分散させることもできる。書込み動作において、書込みデータがコントローラーに提供され、コントローラーは、例えば書込みデータのミラーリング又はストライピングによって、ディスクにわたって書込みデータを記憶する。読取り動作において、コントローラーはディスクからデータを検索する。次に、コントローラーは、ＲＡＩＤ記憶システムが単一のディスクであるかのように結果の読取りデータを生成する。
【００５４】
ハイブリッド非バイナリ低密度パリティチェック復号化器は、実質的に任意のチャネルにを介した情報の送信又は実質的に任意の媒体への情報の記憶に適用可能である。送信用途には、光ファイバー、無線周波数チャネル、有線又は無線のローカルエリアネットワーク、デジタル加入者線技術、無線セルラー、銅ファイバー又は光ファイバー等の任意の媒体によるイーサネット登録商標、ケーブルテレビ等のケーブルチャネル、及び地球衛星通信が含まれるが、これらに限定されるものではない。記憶用途には、ハードディスクドライブ、コンパクトディスク、デジタルビデオディスク、磁気テープ、並びにＤＲＡＭ、ＮＡＮＤフラッシュ、ＮＯＲフラッシュ、他の不揮発性メモリ及びソリッドステートドライブ等のメモリデバイスが含まれるが、これらに限定されるものではない。
【００５５】
さらに、記憶システム９００を、ディスクプラッター９１６によって提供された記憶装置に加えてデータを記憶するのに用いられるソリッドステートメモリを含むように変更することができることに留意するべきである。このソリッドステートメモリは、ディスクプラッター９１６と並列に用いて追加の記憶装置を提供することができる。そのような場合、ソリッドステートメモリは情報を受信し、その情報を読取りチャネル回路９０２に直接提供する。代替的に、ソリッドステートメモリはキャッシュとして用いることができ、この場合、ディスクプラッター（platter）９１６によって提供されるよりも高速のアクセス時間を提供する。そのような場合、ソリッドステートメモリはインターフェースコントローラー９０６と読取りチャネル回路９０２との間に配置することができ、ここで、要求されたデータがソリッドステートメモリ内で利用可能でないとき、又はソリッドステートメモリが新たに書き込まれたデータセットを保持するのに十分な記憶装置を有していないとき、ソリッドステートメモリはディスクプラッター９１６へのパススルーとして機能する。本明細書において提供される開示に基づいて、当業者であれば、ディスクプラッター９１６及びソリッドステートメモリの双方を含む様々な記憶システムを認識するであろう。
【００５６】
図１０を参照すると、本発明のいくつかの実施形態よる、ハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータ処理システムを有する送信機１００２を備えた無線通信システム１０００又はデータ送信デバイスが示されている。送信機１００２は当該技術分野において既知の転送媒体１００６を介して符号化された情報を送信するように動作可能である。符号化データは受信機１００４によって転送媒体１００６から受信される。送信機１００２はハイブリッド非バイナリ低密度パリティチェック復号化器を有するデータ処理システムを組み込む。ハイブリッド非バイナリ低密度パリティチェック復号化器を有するそのようなデータ処理システムは図１〜図７に開示した回路及び方法に沿って実装することができる。
【００５７】
上記のアプリケーションにおいて論述した様々なブロックは、他の機能とともに集積回路に実装することができることに留意すべきである。そのような集積回路は、所与のブロック、システム若しくは回路の機能の全て、又はブロック、システム若しくは回路のサブセットの機能の全てを含むことができる。また、ブロック、システム又は回路の要素を複数の集積回路にわたって実装することができる。そのような集積回路は、当該技術分野において知られている任意のタイプの集積回路とすることができる。この任意のタイプの集積回路には、モノリシック集積回路、フリップチップ集積回路、マルチチップモジュール集積回路及び／又は混合信号集積回路が含まれるが、これらに限定されるものではない。本明細書において論述されたブロック、システム又は回路の様々な機能を、ソフトウェア又はファームウェアのいずれかで実装することができることにも留意すべきである。そのような幾つかの場合には、システム全体、ブロック全体又は回路全体を、そのソフトウェア等価物又はファームウェア等価物を用いて実装することができる。他の場合には、所与のシステム、ブロック又は回路の一部分をソフトウェア又はファームウェアで実装することができる一方、他の部分はハードウェアで実装される。
【００５８】
結論として、本発明は、ハイブリッド非バイナリ低密度パリティチェック復号化器を用いてデータを処理する新規なシステム、デバイス、方法及び構成を提供する。本発明の１つ又は複数の実施形態の詳細な説明が上記で与えられたが、本発明の趣旨から逸脱することなく、様々な代替形態、変更形態及び均等物が当業者には明らかであろう。したがって、上記の説明は本発明の範囲を限定するものとして解釈されるべきではなく、本発明の範囲は添付の特許請求の範囲によって規定される。
【図１】
2014183569.tif 000014
【図２】
2014183569.tif 000015
【図３】
2014183569.tif 000016
【図４】
2014183569.tif 000017
【図５】
2014183569.tif 000018
【図６】
2014183569.tif 000019
【図７】
2014183569.tif 000020
【図８】
2014183569.tif 000021
【図９】
2014183569.tif 000022
【図１０】
2014183569.tif 000023