(57)【要約】      （修正有）【課題】非バイナリー階層化低密度パリティチェック復号化器を提供する。【解決手段】正規化された検査ノード／変数ノードメッセージと、正規化された復号化器入力とに基づいて、変数ノード／検査ノードメッセージを生成するとともに感知された値を計算し、正規化された復号化値を出力するように動作可能な変数ノードプロセッサと、正規化された変数ノード／検査ノードメッセージに基づいて検査ノード／変数ノードメッセージを生成するように動作可能な検査ノードプロセッサとを備える。【選択図】図２
2015070606.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック復号化器であって、
正規化された検査ノード／変数ノードメッセージと、正規化された復号化器入力とに基づいて、変数ノード／検査ノードメッセージを生成するとともに感知された値を計算し、正規化された復号化値を出力するように動作可能な変数ノードプロセッサと、
正規化された変数ノード／検査ノードメッセージに基づいて前記検査ノード／変数ノードメッセージを生成するように動作可能な検査ノードプロセッサと、
を備え、前記変数ノードプロセッサ及び前記検査ノードプロセッサは、階層化されたマルチレベル復号化を実行するように動作可能である、低密度パリティチェック復号化器。
【請求項２】
請求項１に記載の復号化器であって、前記正規化された復号化器入力及び前記正規化された復号化値は、硬判定及び軟データを含み、該軟データは、対応する前記硬判定の尤度に対して正規化されている、復号化器。
【請求項３】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、前記正規化された復号化器入力を正規化されていないフォーマットに変換するように動作可能なフォーマット変換回路を備える、復号化器。
【請求項４】
請求項３に記載の復号化器であって、シンボルの尤度値の前記正規化されていないフォーマットは、ガロア体の各要素について、該シンボルが、対応する該要素の値を有する確率を含む、復号化器。
【請求項５】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、前階層の前記検査ノード／変数ノードメッセージを正規化されていないフォーマットに変換するように動作可能なフォーマット変換回路を備える、復号化器。
【請求項６】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、第１の部分及び第２の部分を備え、該復号化器は、前記変数ノードプロセッサの第１の部分と前記変数ノードプロセッサの第２の部分との間にシフターを更に備え、該シフターは、前階層と現階層との間の巡回シフトの差分に基づいて巡回シフトを適用して前記現階層の総尤度値を得るように動作可能である、復号化器。
【請求項７】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、前階層の前記検査ノード／変数ノードメッセージを、以前の復号化反復において計算された前記前階層の前記変数ノード／検査ノードメッセージに加算して、前記前階層の総尤度値を得るように動作可能な加算器を備え、該加算器の入力及び出力は、正規化されていないフォーマットである、復号化器。
【請求項８】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、デルタエントリー値によって前階層の総尤度値を再配列して、前記前階層の再配列された尤度値を得るように動作可能な再配列回路を備え、前記デルタエントリー値は、現階層のＨ行列エントリー値を前階層のＨ行列エントリー値によって除算したものを含む、復号化器。
【請求項９】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、以前の復号化反復において計算された現階層の前記検査ノード／変数ノードメッセージを正規化されていないフォーマットに変換するように動作可能なフォーマット変換回路を備える、復号化器。
【請求項１０】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、以前の復号化反復において計算された現階層の正規化されていない検査ノード／変数ノードメッセージを、前記現階層の正規化されていない総尤度値から減算して、前記現階層の正規化されていない変数ノード／検査ノードメッセージを得るように動作可能な減算器を備える、復号化器。
【請求項１１】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、現階層の正規化されていない総尤度値を、前記正規化された復号化値として、前記現階層の正規化された総尤度値に変換するように動作可能な正規化回路を備える、復号化器。
【請求項１２】
請求項１に記載の復号化器であって、前記変数ノードプロセッサは、現階層の正規化されていない変数ノード／検査ノードメッセージを、前記現階層の前記正規化された変数ノード／検査ノードメッセージに変換するように動作可能な正規化回路を備える、復号化器。
【請求項１３】
請求項１に記載の復号化器であって、前記検査ノードプロセッサは、最小和ベースのアルゴリズムを適用するように動作可能である、復号化器。
【請求項１４】
請求項１に記載の復号化器であって、該復号化器は、集積回路として実施される、復号化器。
【請求項１５】
請求項１に記載の復号化器であって、該復号化器は、記憶デバイスに組み込まれている、復号化器。
【請求項１６】
請求項１に記載の復号化器であって、該復号化器は、送信システムに組み込まれている、復号化器。
【請求項１７】
非バイナリー階層化低密度パリティチェック復号化器においてデータを復号化する方法であって、
前階層の変数ノード／検査ノードメッセージのフォーマットを、正規化されたフォーマットから正規化されていないフォーマットに変換することであって、復号化される前記データは、前記変数ノード／検査ノードメッセージによって表されることと、
前記前階層の検査ノード／変数ノードメッセージのフォーマットを、前記正規化されたフォーマットから前記正規化されていないフォーマットに変換することと、
前記前階層の前記変数ノード／検査ノードメッセージと、前記前階層の前記検査ノード／変数ノードメッセージと、デルタＨ行列値とに少なくとも部分的に基づいて、現階層の変数ノード／検査ノードメッセージを生成することであって、該現階層の該変数ノード／検査ノードメッセージは、前記正規化されたフォーマットであることと、
前記変数ノード／検査ノードメッセージに基づく前記正規化されたフォーマットの復号化されたデータを前記非バイナリー階層化低密度パリティチェック復号化器から出力することと、
を含む、非バイナリー階層化低密度パリティチェック復号化器においてデータを復号化する方法。
【請求項１８】
請求項１７に記載の方法であって、前記デルタＨ行列値は、ガロア体除算演算において現階層のＨ行列エントリー値を前階層のＨ行列エントリー値によって除算したものを含む、方法。
【請求項１９】
請求項１７に記載の方法であって、前記正規化されたフォーマットは、硬判定及び軟データを含み、該軟データは、対応する前記硬判定の尤度に対して正規化され、シンボルの尤度値の前記正規化されていないフォーマットは、ガロア体の各要素について、該シンボルが、対応する該要素の値を有する確率を含む、方法。
【請求項２０】
記憶システムであって、
記憶媒体と、
前記記憶媒体に対して配置されるとともに前記記憶媒体上の情報に対応する検知された信号を提供するように動作可能なヘッドアセンブリと、
前記検知された信号から取り出されたアナログ信号をサンプリングして一連のデジタルサンプルを得るように動作可能なアナログ／デジタル変換器回路と、
前記アナログ／デジタル変換器回路の出力から取り出された信号内のデータを復号化するように動作可能な非バイナリー階層化低密度パリティチェック復号化器であって、該非バイナリー階層化低密度パリティチェック復号化器の入力及び出力は、硬判定及び軟データを含む正規化されたフォーマットであり、前記軟データは、対応する前記硬判定の尤度に対して正規化されている、非バイナリー階層化低密度パリティチェック復号化器と、
を備える、記憶システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明の様々な実施の形態は、低密度パリティチェック復号化のためのシステム及び方法を提供する。
【背景技術】
【０００２】
記憶システム、携帯電話システム、及び無線送信システムを含む、様々なデータ処理システムが開発されている。かかるシステムでは、データが何らかの媒体を介して送信機から受信機に転送される。例えば、記憶システムにおいて、データは、送信機（すなわち書き込み機能）から、記憶媒体を介して受信機（すなわち読み出し機能）に送信される。情報はデジタルデータの形態で記憶及び送信されるので、誤りが生じ、この誤りは、訂正されない場合、データを破損し情報を使用不可能にする可能性がある。任意の転送の有効性は、様々な要因によって生じる、データ内の任意の損失によって影響される。デジタルデータ内の誤りを検出し訂正するために、多くのタイプの誤り検査システムが開発されている。例えば、データビット群（パリティビットを含む）が偶数個又は奇数個の１を有することを保証するパリティビットをデータビット群に追加することができ、低密度パリティチェック（ＬＤＰＣ）復号化器等のエラー訂正システムにおいて用いることができる。
【発明の概要】
【０００３】
本発明のいくつかの実施形態は、正規化された検査ノード／変数ノードメッセージと、正規化された復号化器入力とに基づいて、変数ノード／検査ノードメッセージを生成するとともに感知された値を計算し、正規化された復号化値を出力するように動作可能な変数ノードプロセッサと、正規化された変数ノード／検査ノードメッセージに基づいて前記検査ノード／変数ノードメッセージを生成するように動作可能な検査ノードプロセッサとを備える非バイナリー階層化低密度パリティチェック復号化器を提供する。
【０００４】
この概要は、本発明によるいくつかの実施の形態の概略のみを提供するものである。本発明の多くの他の実施の形態は、以下の詳細な説明、添付の特許請求の範囲、及び添付の図面からより完全に明らかとなるであろう。
【０００５】
図面を参照することにより、本発明の様々な実施形態の更なる理解を実現することができ、これらの実施形態については本明細書の残りの部分で説明する。図面において、同様の参照符号がいくつかの図面の全てにわたって類似の構成要素を指すのに用いられている。
【図面の簡単な説明】
【０００６】
【図１】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において復号化することができる低密度パリティチェック符号のタナーグラフである。
【図２】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を示す図である。
【図３】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において用いることができるゼロパディング回路を示す図である。
【図４】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において用いることができる正規化回路を示す図である。
【図５】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化のための動作の流れ図である。
【図６】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化を有する読み出しチャネルのブロック図である。
【図７】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を備える記憶システムを示す図である。
【図８】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を備える無線通信システムを示す図である。
【図９】本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を有するデータ処理回路を備える別の記憶システムを示す図である。
【発明を実施するための形態】
【０００７】
本発明の実施形態は、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器に関する。低密度パリティチェック技術は、実質的に任意のチャネルによる情報の送信又は実質的に任意の媒体への情報の記憶に適用可能である。送信に適用されるものには、光ファイバー、無線周波数チャネル、有線又は無線のローカルエリアネットワーク、デジタル加入者線技術、無線セルラー、銅ファイバー又は光ファイバー等の任意の媒体によるイーサネット登録商標、ケーブルテレビ等のケーブルチャネル、及び地球衛星通信が含まれるが、これらに限定されるものではない。記憶に適用されるものには、ハードディスクドライブ、コンパクトディスク、デジタルビデオディスク、磁気テープ、並びにＤＲＡＭ、ＮＡＮＤフラッシュ、ＮＯＲフラッシュ、他の不揮発性メモリ及びソリッドステートドライブ等のメモリデバイスが含まれるが、これらに限定されるものではない。
【０００８】
低密度パリティチェック符号は、サイズｍ×ｎの疎なパリティチェック行列Ｈによって定義される。ここで、ｍ＜ｎである。長さｎの符号語ｃは、Ｈによって定義されたｍ個の全てのパリティチェック方程式を満たす。すなわち、ｃＨＴ＝０である。ここで、０はゼロベクトルである。復号化器の収束は、シンドロームｓ＝ｃＨＴが全てゼロであるか否かを判断することによって検査される。シンドロームは、長さｍのベクトルであり、各ビットは、パリティチェックに対応する。シンドローム内のゼロのビットは、検査が満たされていることを意味する一方、シンドローム内の非ゼロのビットは、満たされていない検査（ＵＳＣ）である。定義によれば、符号語は、シンドロームｓ＝０を有する。非符号語は、非ゼロのシンドロームを有する。
【０００９】
低密度パリティチェック符号は、反復的な復号化アルゴリズムを有するグラフベースの符号としても既知である。このグラフベースの符号は、図１に示すようなタナーグラフ１００に視覚的に表すことができる。低密度パリティチェック復号化器では、複数のパリティチェックが、複数の検査ノード１０２、１０４、及び１０６において一群の変数ノード１１０、１１２、１１４、１１６、１１８、及び１２０について実行される。変数ノード１１０〜１２０と検査ノード１０２〜１０６との間の接続（又はエッジ）は、符号の強度を、データが取得された際に低密度パリティチェック符号を実行するのに必要とされる復号化器の複雑度とバランスさせるものが、低密度パリティチェック符号が設計される際に選択される。一群におけるパリティビットの数及び配置は、低密度パリティチェック符号が設計される際に選択される。接続された変数ノード１１０〜１２０と検査ノード１０２〜１０６との間においてメッセージが反復的なプロセスで渡され、変数ノード１１０〜１２０に現われるべき値についての信念が、接続された検査ノード１０２〜１０６に渡される。パリティチェックは、これらのメッセージに基づいて検査ノード１０２〜１０６において実行され、それらの結果は、接続された変数ノード１１０〜１２０に返され、必要に応じて信念が更新される。
【００１０】
非バイナリー低密度パリティチェック復号化器では、変数ノード１１０〜１２０はガロア体、すなわち有限数の要素を含む有限体ＧＦ（ｐｋ）からの、サイズｐｋによって特徴付けられるシンボルを含む。ここで、ｐは素数であり、ｋは正の整数である。非バイナリー低密度パリティチェック復号化器における変数ノード値を表すメッセージは、送信側の変数ノードが特定の値を含む確率を表す尤度値を含む多次元ベクトルである。「尤度値」という用語は、単純尤度確率値として表されるのか、対数尤度比（ＬＬＲ）値として表されるのか、又は尤度の他の任意の表現として表されるのかを問わず、本明細書では、シンボルが特定の値を有する尤度又は確率を指すのに用いられる。
【００１１】
変数ノード１１０〜１２０と検査ノード１０２〜１０６との間の接続は、以下のような行列の形式で提示することができる。この行列において、列は変数ノードを表し、行は検査ノードを表し、変数ノード列と検査ノード行との交点におけるガロア体からのランダムな非ゼロの要素ａ（ｉ，ｊ）は、その変数ノードとその検査ノードとの間の接続を示し、その変数ノードとその検査ノードとの間のメッセージの置換（permutation）を提供する。
【数１】
2015070606.tif 000003
【００１２】
例えば、ＧＦ（４）復号化器のいくつかの実施形態では、各ガロア体要素ａ（ｉ，ｊ）は、０、１、２、又は３の対応する巡回行列のためのシフトを指定する。
【００１３】
非バイナリー階層化低密度パリティチェック復号化器は、パリティチェックＨ行列が巡回部分行列からなる行列である擬似巡回符号を用いる。これらの巡回部分行列は、Ｈ行列の非ゼロのエントリー値ａ（ｉ，ｊ）によって指定された異なる巡回シフトを用いて単位行列及びヌル行列を巡回シフトしたものである。各巡回行列Ｐｉ，ｊは、以下の形式を有するｐ×ｐ部分行列である。
【数２】
2015070606.tif 000004
式中、エントリー値αは、２ｍ−１個の可能な値を有するガロア体ＧＦ（２ｍ）上の要素である。
【００１４】
いくつかの実施形態では、エントリー値αは、ガロア体からランダムに選択される。エントリー値αは、そのエントリーによって接続された変数ノードと検査ノードとの間のメッセージの置換を提供する。この置換では、現階層のエントリー値によるガロア体におけるメッセージの乗算が実行される。正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器における変数ノードユニット又は変数ノードプロセッサによって実行されるこの置換は、本明細書では再配列とも呼ばれる。同様に、メッセージが、検査ノードから変数ノードに戻されたとき、メッセージは、前階層のエントリー値によって逆再配列される。この逆再配列では、現階層のエントリー値によるガロア体におけるメッセージの除算が実行される。
【００１５】
一群の変数ノード１１０〜１２０用に複数の検査ノード１０２〜１０６を設けることによって、エラー検査における冗長性が提供され、エラーを検出するだけでなく訂正することが可能になる。各検査ノード１０２〜１０６は、その近傍（又は接続された）変数ノードからメッセージとして渡されたビット又はシンボルに対してパリティチェックを実行する。図１のタナーグラフ１００に対応する例示の低密度パリティチェック符号では、検査ノード１０２は、変数ノード１１２、１１６、１１８、及び１２０のパリティを検査する。変数ノードの感知された値が、接続された検査ノードからのパリティチェック結果に基づいて更新される。例えば、変数ノード１１０の感知された値又は尤度値（ＬＶ）は、接続された検査ノード１０４、１０６からの検査ノードメッセージ（Ｃ２，Ｃ３）とともに、チャネル尤度値又は前の尤度値に基づいて更新される。値は、低密度パリティチェック符号が変数ノード１１０〜１２０における一群のデータビット及びパリティビットについて或る値に収束するまで、又は最大反復回数に達するまで、接続された変数ノード１１０〜１２０と検査ノード１０２〜１０６との間を反復的プロセスで往復して渡される。例えば、変数ノード１１０は、本明細書では変数ノード／検査ノードメッセージ（variable node to check node messages）又はＶ２Ｃメッセージと呼ばれるメッセージを検査ノード１０４及び１０６に渡す。検査ノード１０２は、本明細書では検査ノード／変数ノードメッセージ（check node to variable node messages）又はＣ２Ｖメッセージと呼ばれるメッセージを変数ノード１１２、１１６、１１８、及び１２０に戻す。変数ノード１１０〜１２０と検査ノード１０２〜１０６との間のメッセージは、確率又は信念であり、したがって、低密度パリティチェック復号化アルゴリズムは、信念伝播アルゴリズムとも呼ばれる。ノードからの各メッセージは、ビット又はシンボルがそのノードの現在の値とそのノードへの前のメッセージとに基づく或る特定の値を有する確率を表す。
【００１６】
変数ノードから任意の特定の近傍検査ノードへのメッセージは、正のフィードバックを防止するためにその特定の検査ノードからの最後のメッセージが計算から省略されることを除いて、その変数ノードの現在の値と近傍検査ノードからその変数ノードへの最後のメッセージとに基づいて、複数のアルゴリズムのうちの任意のものを用いて計算される。同様に、検査ノードから任意の特定の近傍変数ノードへのメッセージは、正のフィードバックを防止するためにその特定の変数ノードからの最後のメッセージが計算から省略されることを除いて、その検査ノードの現在の値と近傍変数ノードからその検査ノードへの最後のメッセージとに基づいて計算される。ローカルな復号化反復がシステムにおいて実行されるにつれて、メッセージは、変数ノード１１０〜１２０と検査ノード１０２〜１０６との間を往来し、ノード１０２〜１２０における値は、それらの値が収束して変化を停止するまで、又は最大反復回数に達するまで、渡されたメッセージに基づいて調整される。
【００１７】
正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器では、パリティチェックＨ行列は、Ｌ個の階層に分割され、Ｈ行列は行ごとに処理され、巡回行列は階層ごとに処理される。行が処理されると、列の結果が、各行の結果に基づいて更新される。階層化された復号化は、場合によっては復号化器において結果に収束する時間を削減することができる。
【００１８】
尤度値は、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において、正規化されたフォーマット又は絶対フォーマットのいずれかで表すことができる。絶対フォーマット又は正規化されていないフォーマットでは、シンボル又は変数ノードの尤度値は、ガロア体の各要素について、シンボル又は変数ノードがその要素の値を有する確率を含む。したがって、ＧＦ（ｑ）復号化器の場合、シンボルの尤度値は、そのシンボルがｑ個のガロア体要素のそれぞれの値を有する尤度を与えるｑ個の確率を含む。正規化されたフォーマットでは、尤度値は、シンボルの最尤値を有するガロア体要素を識別する硬判定と、残りのガロア体要素の値の確率とを含む。各確率は、最尤ガロア体要素の尤度に対して正規化されている。したがって、ＧＦ（ｑ）復号化器の場合、シンボルの正規化された尤度値は、最尤シンボル値と、シンボルが、最尤要素の尤度に対して正規化された残りのｑ個のガロア体要素のそれぞれの値を有する尤度とを与える、硬判定とｑ−１個の確率とを含む。最小和復号化アルゴリズム又はその変形形態を用いる復号化器では、ｑ個の尤度の尤度値の和は１になり、最小のものが最も確からしい。これらの実施形態では、正規化された尤度値は、Ｑｉ，ｊ＝［Ｑ＊ｉ，ｊ（０），Ｑｉ，ｊ（１）．．．Ｑｉ，ｊ（ｑ−１）］として表すことができる。ここで、Ｑ＊ｉ，ｊ（０）は、最尤ガロア体要素を識別する硬判定であり、Ｑｉ，ｊ（１）．．．Ｑｉ，ｊ（ｑ−１）は、残りのガロア体要素の値の確率であり、各確率は、最尤ガロア体要素の尤度に対して正規化されており、それぞれから最尤ガロア体要素の尤度を減算することによって計算される。いくつかの実施形態では、絶対尤度値は、ガロア体における要素の順序に従ってベクトル内で順序付けられる一方、正規化された尤度値は、尤度に従ってベクトル内で順序付けられ、最尤ガロア体要素値がベクトル内で最初に配置され、最小尤度のものが最後に配置される。
【００１９】
対数尤度比を用いるＧＦ（４）非バイナリー階層化低密度パリティチェック復号化器のいくつかの実施形態について、以下の表は、ガロア体からの４つの可能なシンボル値の硬判定及び正規化された対数尤度比を規定している。
【００２０】
【表１】
2015070606.tif 000005
【００２１】
上記表において、３つの対数尤度比値ＬＬＲ０、ＬＬＲ１、ＬＬＲ２は、以下のように計算される。
ｈｄ＝００である場合、ＬＬＲ０＝ｌｏｇ（確率（ｈｄ＝０１））−ｌｏｇ（確率（ｈｄ＝００））；
ｈｄ＝００である場合、ＬＬＲ１＝ｌｏｇ（確率（ｈｄ＝１０））−ｌｏｇ（確率（ｈｄ＝００））；
ｈｄ＝００である場合、ＬＬＲ２＝ｌｏｇ（確率（ｈｄ＝１１））−ｌｏｇ（確率（ｈｄ＝００））；
ｈｄ＝０１である場合、ＬＬＲ０＝ｌｏｇ（確率（ｈｄ＝００））−ｌｏｇ（確率（ｈｄ＝０１））；
ｈｄ＝０１である場合、ＬＬＲ１＝ｌｏｇ（確率（ｈｄ＝１１））−ｌｏｇ（確率（ｈｄ＝０１））；
ｈｄ＝０１である場合、ＬＬＲ２＝ｌｏｇ（確率（ｈｄ＝１０））−ｌｏｇ（確率（ｈｄ＝０１））；
ｈｄ＝１０である場合、ＬＬＲ０＝ｌｏｇ（確率（ｈｄ＝１１））−ｌｏｇ（確率（ｈｄ＝１０））；
ｈｄ＝１０である場合、ＬＬＲ１＝ｌｏｇ（確率（ｈｄ＝００））−ｌｏｇ（確率（ｈｄ＝１０））；
ｈｄ＝１０である場合、ＬＬＲ２＝ｌｏｇ（確率（ｈｄ＝０１））−ｌｏｇ（確率（ｈｄ＝１０））；
ｈｄ＝１１である場合、ＬＬＲ０＝ｌｏｇ（確率（ｈｄ＝１０））−ｌｏｇ（確率（ｈｄ＝１１））；
ｈｄ＝１１である場合、ＬＬＲ１＝ｌｏｇ（確率（ｈｄ＝０１））−ｌｏｇ（確率（ｈｄ＝１１））；
ｈｄ＝１１である場合、ＬＬＲ２＝ｌｏｇ（確率（ｈｄ＝００））−ｌｏｇ（確率（ｈｄ＝１１））；
【００２２】
図２を参照すると、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器２００が、ブロック図形式で示されている。復号化されるデータの入来する尤度値が、入力２０２において受信され、初期Ｑメッセージ、すなわち変数ノード／検査ノードメッセージとして復号化器入力バッファー又はメモリ２０４に記憶される。いくつかの実施形態では、これらの尤度値は、硬判定及び軟データを含む。「軟データ」という語句は、本明細書において用いられるとき、信頼性データの各インスタンスがシンボルが正しく検出された尤度を示す信頼性データを意味するようにその最も広い意味で用いられる。本発明のいくつかの実施形態では、軟データ又は信頼性データは、当該技術分野で既知であるような対数尤度比データである。いくつかの実施形態では、尤度値は対数尤度比である。正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器２００では、入力２０２は、正規化された尤度値を受信し、復号化器出力２３６は、正規化された尤度値を与える。
【００２３】
メモリ２０４は、現在処理されている階層の前階層の記憶されたＱメッセージ２０６を得る。本明細書では、上記現在処理されている階層の前階層は、前階層とも呼ばれ、上記現在処理されている階層は、接続された階層とも呼ばれる。したがって、記憶されたＱメッセージ２０６は、チャネル尤度値によって初期化されるか、又は前の復号化反復若しくは以前の復号化反復において計算され、したがって、古いＱメッセージである。記憶されたＱメッセージ２０６は、正規化されたフォーマットであり、前階層のＨ行列エントリー値Ｈ（ｉ−１）によって再配列されており、前階層のシフト値ＳＨ（ｉ−１）だけシフトされている。正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器２００のいくつかの実施形態では、正規化された尤度値は、加算又は減算を行う前に絶対尤度値に変換される。なぜならば、加算又は減算は、特定の解の尤度値に対して演算を行うからである。正規化された尤度値から絶対尤度値への変換は、本明細書では、ゼロパディングと呼ばれる。ゼロパディング回路への入力は、ｑ＝４の場合、｛ｈｄ，ｌｌｒ０，ｌｌｒ１，ｌｌｒ２｝であり、出力は、｛ｌｌｒ’０，ｌｌｒ’１，ｌｌｒ’２，ｌｌｒ’３｝である。ここで、ｌｌｒ’（ｉ）（ｉ＝０，１，２，３）は、シンボルが対数領域において「ｉ」である確率である。フォーマット変換回路又はゼロパディング回路２０８は、記憶されたＱメッセージ２０６を受信し、それらのＱメッセージを、正規化された尤度値から絶対尤度値に変換し、絶対フォーマットのＱメッセージ２１０を出力する。ゼロパディング回路２０８は、正規化された尤度値から絶対尤度値に変換するための任意の好適な回路部を備えることができる。本明細書において提供される開示に基づくと、当業者であれば、ゼロパディング回路２０８に備えることができる多岐にわたる回路を認識するであろう。
【００２４】
加算器２１２は、Ｑメッセージ２１０を、前階層の検査ノード／変数ノードメッセージ、すなわち新しいＲメッセージ２１６に加算して、前階層の総尤度値を含む和、すなわちＳメッセージ２１８を得る。新しいＲメッセージ２１６は、ゼロパディング回路２１４によって、正規化されたフォーマットの新しいＲメッセージ２７０から変換された絶対フォーマットである。新しいＲメッセージ２１６は、少なくとも部分的に過去の前の復号化反復又は以前の復号化反復において計算された古いＲメッセージ２６６とは対照的に、現在の復号化反復において計算されるので「新しい」と呼ばれる。Ｈ行列における列は変数ノードを表し、列内の全ての非ゼロエントリーを加算することによって、接続された変数ノードが加算され、検査ノードへの入力が得られることを再度述べておく。加算器２１２は、いくつかの実施形態では、アレイ形式で動作する、尤度値を加算するための任意の好適な回路部を備えることができる。本明細書において提供される開示に基づくと、当業者であれば、加算器２１２に備えることができる多岐にわたる回路を認識するであろう。
【００２５】
Ｓメッセージ２１８は、再配列回路２２０に提供される。この再配列回路は、検査ノードの更新の準備をするとともに非ゼロのＨ行列エントリー値によって指定された置換を適用するために、Ｓメッセージ２１８を再配列する置換を適用する。Ｓメッセージ２１８のシンボルの順序は、前階層のＨ行列エントリー値Ｈ（ｉ−１）によって再配列されるとともに前階層のシフト値ＳＨ（ｉ−１）だけシフトされた、記憶されたＱメッセージ２０６の順序と同じである。このメッセージを、現階層の復号化プロセスのための検査ノードプロセッサ又は検査ノードユニット２６４に渡すために、Ｓメッセージ２１８は、前階層のＨ行列エントリー値Ｈ（ｉ−１）によって除算され、次いで、現階層のＨ行列エントリー値Ｈ（ｉ）を乗算される。再配列回路２２０へのパラメーター２２２は、デルタエントリー値（Ｈ（ｉ）／Ｈ（ｉ−１））である。ここで、演算子「／」は、ＧＦ（ｑ）における除算演算を表す。いくつかの実施形態では、パラメーター２２２のデルタエントリー値（Ｈ（ｉ）／Ｈ（ｉ−１））は、事前に計算されて任意の好適なメモリに記憶される。再配列回路２２０は、ガロア体における除算を実行するための任意の好適な回路部を備えることができる。本明細書において提供される開示に基づくと、当業者であれば、ルックアップ回路等の、再配列回路２２０に備えることができる多岐にわたる回路を認識するであろう。例えば、ガロア体の４つの要素０〜３が０、１、α、α２であるＧＦ（４）の実施形態では、ガロア体における乗算は、再配列回路２２０によって次のように実行することができる。要素２（α）に要素１（１）を乗算したものはα×１、すなわちαに等しく、これは要素２である。同様に、要素２×２＝α×α＝α２であり、これは要素３である。要素２×３＝α×α２＝１であり、これは要素１である。このように、要素２に１、２、及び３を乗算したものは、それぞれ要素２、３、及び１になり、これらは、要素１、２、及び３を置換したものである。再配列回路２２０は、変数ノードユニット２５４の第１の部分の出力において前階層のＰメッセージ２２４を与える。Ｐメッセージ２２４は絶対フォーマットである。
【００２６】
再配列回路２２０からのＰメッセージ２２４は、現階層の総軟尤度値を含む現階層のＰメッセージ２３２を与えるシフター２２６に提供される。このシフターは、Ｐメッセージ２２４内のシンボル値をシフト値２３０だけシフトして次の巡回部分行列を生成する巡回シフター又はバレルシフターである。シフト値２３０は、前階層と現階層との間の巡回シフトの差分を表す。現階層のＰメッセージ２３２は、絶対フォーマットである。シフター２２６は、メッセージベクトルをバレルシフトするための任意の好適な回路部を備えることができる。本明細書において提供される開示に基づくと、当業者であれば、シフター２２６に備えることができる多岐にわたる回路を認識するであろう。ＧＦ（４）復号化器用のシフター２２６のビット単位の関数は４＊ｂ＊ｐである。ここで、ｂは各尤度値をビット単位でグループ分けしたものであり、ｐは巡回サイズである。
【００２７】
現階層のＰメッセージ２３２は、減算器２４４に提供される。この減算器は、現階層の検査ノード／変数ノードメッセージ、すなわち絶対フォーマットの古いＲメッセージ２４２を現階層のＰメッセージ２３２から減算して、絶対フォーマットの現階層のＤメッセージ２４６を得る。古いＲメッセージ２４２は、古いＲメッセージ２６６を正規化されたフォーマットから絶対フォーマットに変換するゼロパディング回路２４０から取得される。現階層の検査ノード／変数ノードメッセージ、すなわち古いＲメッセージ２４２は、前の復号化反復中に生成された現階層の古い値である。一般に、検査ノードから変数ノードへのベクトルメッセージは、ガロア体における各シンボルｄについて、宛先変数ノードが、当該宛先変数ノード以外の近傍変数ノードからの、先行ラウンドの変数ノード／検査ノードメッセージに基づいて、そのシンボルｄを含む確率を含む。特定の近傍変数ノードのための検査ノード／変数ノードメッセージを生成するために検査ノードにおいて用いられる近傍変数ノードからの入力は、外部入力（extrinsic inputs）と呼ばれ、正のフィードバックを回避するために、検査ノード／変数ノードメッセージが準備中である特定の近傍変数ノードを除く全ての近傍変数ノードからの、先行ラウンドの変数ノード／検査ノードメッセージを含む。検査ノードは、宛先変数ノードに基づくメッセージごとに異なる一組の外部入力を用いて、近傍変数ノードごとに異なる、検査ノード／変数ノードメッセージを準備する。現階層の検査ノード／変数ノードメッセージ、すなわち古いＲメッセージ２４２を以前の反復から減算することによって、本来の入力（intrinsic input）が除去され、変数ノードのための検査ノード／変数ノードメッセージを生成する外部入力のみが残される。減算器２４４は、尤度値を減算するための任意の好適な回路部を備えることができる。本明細書において提供される開示に基づくと、当業者であれば、減算器２４４に備えることができる多岐にわたる回路を認識するであろう。
【００２８】
Ｄメッセージ２４６は、正規化回路２５０に提供される。この正規化回路は、Ｄメッセージ２４６のフォーマットを絶対フォーマットから、正規化されたフォーマットに変換し、正規化されたフォーマットの新しいＱメッセージ２５２を得る。新しいＱメッセージ２５２は、変数ノードユニット２５６の第２の部分から出力され、後続の復号化反復のためにメモリ２０４に記憶されて、現階層の前のチャネル値又は計算された値を上書きし、また、新しいＱメッセージ２５２をスケーリングして、スケーリングされた変数ノード／検査ノードメッセージ２６２を得るスケーリング回路２６０にも提供される。
【００２９】
検査ノードプロセッサ又は検査ノードユニット２６４は、スケーリングされた変数ノード／検査ノードメッセージ２６２に基づいて古いＲメッセージ２６６及び新しいＲメッセージ２７０の検査ノード／変数ノードメッセージを生成する。検査ノードユニット２６４は、任意の低密度パリティチェック復号化アルゴリズムを適用することができる。このアルゴリズムは、最小和ベースの復号化アルゴリズム等であるが、これらに限定されるものではない。最小和ベースの復号化アルゴリズムのいくつかの実施形態では、検査ノードユニット２６４は、以下の論理に従って、各近傍変数ノードからのメッセージベクトル内の部分メッセージＱｉ，ｊｋ（ｄ）に基づいて、ガロア体におけるｑ個のシンボルのそれぞれについて、最小値ｍｉｎ１（ｄ）と、２番目の最小値、すなわち次の最小値ｍｉｎ２（ｄ）と、最小値のインデックスｉｄｘ（ｄ）とを計算する。
【数３】
2015070606.tif 000006
【００３０】
検査ノードユニット２６４は、変数ノード／検査ノードメッセージ２６２の正負符号も計算し、現階層のＨ行列の各非ゼロ要素の正負符号値及び累積的な正負符号を追跡する。前のローカルな復号化反復（したがって、古い）において計算された正負符号値を有する現階層の最小値、次の最小値、及びインデックス値が与えられると、検査ノードユニット２６４は、現階層の検査ノード／変数ノードメッセージ、すなわち古いＲメッセージ２６６を計算する。現在のローカルな復号化反復（したがって、新しい）において計算された正負符号値を有する前階層の最小値、次の最小値、及びインデックス値が与えられると、検査ノードユニット２６４は、前階層の検査ノード／変数ノードメッセージ、すなわち新しいＲメッセージ２７０を計算する。
【００３１】
検査ノードユニット２６４は、どの特定の低密度パリティチェックアルゴリズムにも限定されるものではなく、変数ノード／検査ノードメッセージに基づいて検査ノード／変数ノードメッセージを生成するための任意の好適な回路部を備えることができることを再度述べておく。本明細書において提供される開示に基づくと、当業者であれば、検査ノードユニット２６４に備えることができる多岐にわたる回路を認識するであろう。
【００３２】
変数ノードユニット２５４、２５６及び検査ノードユニット２６４は、非バイナリーデータの階層化された復号化を実行するために上記のようにともに動作する。変数ノードユニット２５４、２５６は、古いＲメッセージ２６６及び新しいＲメッセージ２７０の検査ノード／変数ノードメッセージに基づいて、変数ノード／検査ノードメッセージ２６２を生成し、感知された値を計算する。「感知された値」という用語は、本明細書では、復号化されるシンボルの値を指すのに用いられ、いくつかの実施形態では、尤度値によって表される。検査ノードユニット２６４は、変数ノード／検査ノードメッセージ２６２に基づいて、検査ノード／変数ノードメッセージを生成し、チェックサムを計算する。
【００３３】
変数ノードユニット２５６の第２の部分における正規化回路２３４も、シフター２２６からの現階層のＰメッセージ２３２を処理し、現階層のＰメッセージ２３２のフォーマットを絶対フォーマットから正規化されたフォーマットに変換する。正規化回路２３４は、復号化器出力２３６において、正規化されたフォーマットのＰメッセージを与える。復号化器出力２３６におけるＰメッセージは、軟データ及び復号化値とも呼ばれる。いくつかの実施形態では、変数ノードユニット２５６の第２の部分は、最も高い尤度以外のガロア体要素の尤度を省略した、正規化回路２３４の出力からの硬判定も出力する。
【００３４】
図３を参照すると、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において用いることができるゼロパディング回路３１０が示されている。正規化された尤度値から絶対尤度値への変換は、本明細書ではゼロパディングと呼ばれることを再度述べておく。ゼロパディング回路３１０は、入力として、ガロア体からの硬判定３１２又は最尤値と、ガロア体の各残りの要素の尤度ＬＶ（０）３０２、ＬＶ（１）３０４、．．．ＬＶ（ｑ−２）３０６とを含む、変換されるシンボルごとの正規化された尤度値を受信する。ゼロパディング回路３１０は、尤度ＬＶ’（０）３１４、ＬＶ’（１）３１６、．．．ＬＶ’（ｑ−２）３２０及びＬＶ’（ｑ−１）３２２を出力する。尤度３１４〜３２２には、硬判定３１２についての最尤ガロア体要素の尤度と、残りのガロア体要素の尤度とが含まれ、最も可能性の高いものの尤度が、正規化の逆を行うためにそれぞれに追加される。
【００３５】
図４を参照すると、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器において用いることができる正規化回路４００が示されている。正規化回路４００は、絶対フォーマットの入力を正規化されたフォーマットの出力に変換する。正規化回路４００は、尤度ＬＶ’（０）４０２、ＬＶ’（１）４０４、．．．ＬＶ’（ｑ−２）４０６及びＬＶ’（ｑ−１）４１０を受信する。最小ファインダーマルチプレクサーアレイ４１２が、４つの尤度４０２〜４１０の中から最小値を見つけ、この最小値を有するガロア体要素のインデックスを硬判定４１４として出力する。例えば、対数尤度比を用いる復号化器では、ＬＬＲ’（ｉ）が最小値である場合、硬判定４１４は「ｉ」である。硬判定の尤度は、最小尤度４２４として出力され、残りのガロア体要素の尤度４１６、４２０、４２２は、最小ファインダーマルチプレクサーアレイ４１２によって表１に従った順序で配置される。減算回路４２６は、最小尤度４２４を尤度４１６から減算して尤度ＬＶ（０）４３４を得る。減算回路４３０は、最小尤度４２４を尤度４２０から減算して尤度ＬＶ（１）４３６を得る。減算回路４３２は、最小尤度４２４を尤度４２２から減算して尤度ＬＶ（ｑ−２）４４０を得る。ガロア体における要素の数に基づいて、必要に応じて追加の減算回路が備えられる。
【００３６】
図５を参照すると、流れ図５００が、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化のための方法を示している。流れ図５００によると、正規化されたフォーマットの古い前階層の変数ノード／検査ノードメッセージが、復号化器メモリから取り出される（ブロック５０２）。この古い前階層の変数ノード／検査ノードメッセージは、本明細書では、古いＱメッセージとも呼ばれる。古い前階層の変数ノード／検査ノードメッセージ及び新しい前階層の検査ノード／変数ノードメッセージは、絶対フォーマットに変換される（ブロック５０４）。これらの新しい前階層の検査ノード／変数ノードメッセージは、本明細書では、新しいＲメッセージとも呼ばれる。絶対フォーマットの新しい前階層の検査ノード／変数ノードメッセージは、絶対フォーマットの古い前階層の変数ノード／検査ノードメッセージに加算されて、前階層の総尤度値が得られる（ブロック５０６）。これらの前階層の総尤度値は、デルタエントリー値によって再配列されて、再配列された前階層の尤度値が得られる（ブロック５０８）。これによって、前階層の総尤度値が再配列されて、検査ノード更新の準備がされ、非ゼロのＨ行列エントリー値によって指定された置換が適用される。前階層の総尤度値は、本明細書では、Ｓメッセージとも呼ばれる。いくつかの実施形態では、デルタエントリー値は、ＧＦ（ｑ）における除算演算を用いて、現階層のＨ行列エントリー値Ｈ（ｉ）を前階層のＨ行列エントリー値Ｈ（ｉ−１）によって除算したものである（Ｈ（ｉ）／Ｈ（ｉ−１））である。再配列された前階層の尤度値は、前階層と現階層との間の巡回シフトの差分だけシフトされ、絶対フォーマットの現階層の尤度値が得られる（ブロック５１０）。現階層の尤度値は、正規化されたフォーマットに変換され、軟復号化器出力として出力される（ブロック５１２）。古い現階層の検査ノード／変数ノードメッセージは、絶対フォーマットに変換される（ブロック５１４）。古い現階層の検査ノード／変数ノードメッセージは、本明細書では、古いＲメッセージとも呼ばれる。絶対フォーマットの古い現階層の検査ノード／変数ノードメッセージは、絶対フォーマットの現階層の尤度値から減算されて、絶対フォーマットの現階層の変数ノード／検査ノードメッセージが得られる（ブロック５１６）。現階層の変数ノード／検査ノードメッセージは、本明細書では、Ｄメッセージとも呼ばれる。現階層の変数ノード／検査ノードメッセージは、正規化されたフォーマットに変換され、それらの値は、復号化器メモリにおいて更新される（ブロック５１８）。検査ノード処理が実行されて、正規化されたフォーマットの新しい前階層の検査ノード／変数ノードメッセージ及び正規化されたフォーマットの古い現階層の検査ノード／変数ノードメッセージが生成され、復号化反復の階層の処理が完了する（ブロック５２０）。復号化器において最大反復回数に達したか否か又は復号化器が収束したか否かについての判断が行われる（ブロック５２２）。最大反復回数に達した場合又は復号化器が収束した場合には、復号化は終了する（ブロック５２４）。そうでない場合、復号化は、ブロック５０２において継続される。
【００３７】
本明細書において開示された正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器は、どの特定の用途にも限定されるものでないが、本発明の実施形態から利益を得るいくつかの用途例が、本明細書において提示される。図６を参照すると、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０を有する読み出しチャネル６００が示されている。アナログ信号６０２を処理し、アナログ信号６０２から誤りを伴うことなくユーザーデータビットを取り出すのに読み出しチャネル６００が用いられる。いくつかの場合には、アナログ信号６０２は磁気記憶媒体における読み出し／書き込みヘッドアセンブリから取り出される。他の場合には、アナログ信号６０２は、伝送媒体から信号を受信するように動作可能な受信機回路から取り出される。伝送媒体は、限定ではないがケーブル接続又は光接続等、有線又は無線とすることができる。本明細書において提供される開示に基づいて、当業者であれば、アナログ信号６０２を取り出すことができる多岐にわたるソースを認識するであろう。
【００３８】
読み出しチャネル６００は、アナログ信号６０２を受信し処理するアナログフロントエンド６０４を含む。アナログフロントエンド６０４は、限定ではないが、当該技術分野において既知のアナログフィルター及び増幅器回路を含むことができる。本明細書において提供される開示に基づいて、当業者であれば、アナログフロントエンド６０４の一部として含めることができる多岐にわたる回路を認識するであろう。いくつかの場合には、アナログフロントエンド６０４の一部として含まれる可変利得増幅器の利得は変更可能とすることができ、アナログフロントエンド６０４に含まれるアナログフィルターのカットオフ周波数及びブーストは変更可能とすることができる。アナログフロントエンド６０４はアナログ信号６０２を受信及び処理し、処理されたアナログ信号６０６をアナログ／デジタル変換器６１０に提供する。
【００３９】
アナログ／デジタル変換器６１０は処理されたアナログ信号６０６を対応する一連のデジタルサンプル６１２に変換する。アナログ／デジタル変換器６１０は、アナログ入力信号に対応するデジタルサンプルを生成することが可能な当該技術分野において既知の任意の回路とすることができる。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に関連して用いることができる多岐にわたるアナログ／デジタル変換器回路を認識するであろう。他の実施形態では、デジタルデータは、フラッシュメモリ等の、記憶デバイス又は他のソースから直接取り出される。デジタルサンプル６１２が等化器６１４に提供される。等化器６１４は等化アルゴリズムをデジタルサンプル６１２に適用し、等化出力６１６を得る。本発明のいくつかの実施形態では、等化器６１４は当該技術分野において既知のデジタル有限インパルス応答フィルター回路である。等化出力６１６に含まれるデータ又は符号語は、データ検出器６２４が処理に利用可能になり、かつ記憶された等化サンプルを受信する（６２２）準備ができるまでバッファー６２０内に記憶することができる。
【００４０】
データ検出器６２４は受信した入力に対しデータ検出プロセスを実行し、結果として検出された出力６２６が得られる。本発明のいくつかの実施形態では、データ検出器６２４はビタビアルゴリズムデータ検出器回路であるか、より具体的には、いくつかの場合には、当該技術分野において既知の最大事後（ＭＡＰ：maximum a posteriori）データ検出器回路である。これらの実施形態では、検出された出力６２６は、各ビット又はシンボルが特定の値を有する尤度に関する対数尤度比軟情報を含む。本明細書において提供される開示に基づいて、当業者であれば、本発明の様々な実施形態に関連して用いることができる多岐にわたるデータ検出器を認識するであろう。データ検出器６２４は、バッファー６２０内のデータセットが等化器６１４又は別のソースから入手可能であることに基づいて始動される。
【００４１】
データ検出器６２４からの検出された出力６２６が、バーストエラーに対しデータを保護するインターリーバー６３０に提供される。バーストエラーは局所的なビット群又はビット塊を上書きする。低密度パリティチェック復号化器はより均一に分散した誤りを訂正するのに最も適しているので、バーストエラーは低密度パリティチェック復号化器を凌ぐ可能性がある。インターリーバー６３０は、データ検出器６２４からの検出された出力６２６をインターリーブ又はシャッフリングしてインターリーブされた出力６３２を得ることによってこれを回避する。インターリーブされた出力６３２はメモリ６３４に記憶される。メモリ６３４からのインターリーブされた出力６３６は正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０に提供され、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０はインターリーブされた出力６３６に対しパリティチェックを実行し、記憶若しくは伝送中にデータにおいて生じた可能性がある任意の誤りを検出し訂正するために、記憶又は伝送前に低密度パリティチェック符号化器（図示せず）によって確立されたパリティ制約が満たされていることを確保する。
【００４２】
検出及び復号化の複数の反復を読み出しチャネル６００において実行することができ、これは本明細書において大域反復と呼ばれる。（対照的に、局所反復は正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０内で実行される復号化反復である。）大域反復を実行するために、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０からの尤度比値６４２がメモリ６３４に記憶され、デインターリーバー６４６においてデインターリーブされてインターリーバー６３０によって適用されたプロセスが逆に行われ、再びデータ検出器６２４に提供されて、データ検出器６２４が正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０からの対数尤度比値６４２によって支援されたデータ検出プロセスを繰り返すことが可能になる。このようにして、読み出しチャネル６００は複数の大域反復を実行し、データ検出器６２４及び正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０が正しいデータ値に収束することを可能にすることができる。
【００４３】
正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０は、インターリーバー６３０のインターリーブされた出力６３２に含まれるデータビット又はシンボルの値についての硬判定６５２も生成する。ＧＦ（４）低密度パリティチェック復号化器では、これらの硬判定は、インデックス００、０１、１０、及び１１を有する４つのフィールド要素によって表すことができる。
【００４４】
正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化６４０からの硬判定６５２は、インターリーバー６３０において適用されたプロセスの逆を行う硬判定デインターリーバー６５４においてデインターリーブされ、ユーザーに提供される前又は更に処理される前に硬判定メモリ６６０に記憶される。例えば、読み出しチャネル６００の出力６６２は、データを磁気記憶媒体に記憶する前又はデータを送信チャネルにわたって送信する前に適用されたフォーマット変更を反転するように更に処理することができる。
【００４５】
図７を参照すると、本発明のいくつかの実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器の応用形態例として記憶システム７００が示されている。記憶システム７００は、本発明の１つ又は複数の実施形態よる正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を有するデータ処理システムを有する読み出しチャネル回路７０２を備える。記憶システム７００は、例えば、ハードディスクドライブとすることができる。記憶システム７００は、前置増幅器７０４、インターフェースコントローラー７０６、ハードディスクコントローラー７１０、モーターコントローラー７１２、スピンドルモーター７１４、ディスクプラッター７１６、及び読み出し／書き込みヘッド７２０も備える。インターフェースコントローラー７０６はディスクプラッター７１６への／からのデータのアドレス指定及びタイミングを制御する。ディスクプラッター７１６上のデータは、アセンブリがディスクプラッター７１６上に適切に位置決めされているときに読み出し／書き込みヘッドアセンブリ７２０によって検出することができる磁気信号の群からなる。１つの実施形態では、ディスクプラッター７１６は長手記録方式又は垂直記録方式のいずれかに従って記録される磁気信号を含む。
【００４６】
通常の読み出し動作において、読み出し／書き込みヘッドアセンブリ７２０はモーターコントローラー７１２によって、ディスクプラッター７１６上の所望のデータトラックの上方に正確に位置決めされる。モーターコントローラー７１２は、ハードディスクコントローラー７１０の指示の下で読み出し／書き込みヘッドアセンブリ７２０をディスクプラッター７１６上の適切なデータトラックに移動することによって、ディスクプラッター７１６に対して読み出し／書き込みヘッドアセンブリ７２０を位置決めし、かつスピンドルモーター７１４を駆動する。スピンドルモーター７１４は所定のスピンレート（ＲＰＭ）でディスクプラッター７１６をスピンさせる。読み出し／書き込みヘッドアセンブリ７２０が適切なデータトラックに近接して位置決めされると、ディスクプラッター７１６がスピンドルモーター７１４によって回転するのに応じてディスクプラッター７１６上のデータを表す磁気信号が読み出し／書き込みヘッドアセンブリ７２０によって感知される。感知された磁気信号は、ディスクプラッター７１６上の磁気データを表す連続した微小アナログ信号として与えられる。この微小アナログ信号は、読み出し／書き込みヘッドアセンブリ７２０から、前置増幅器７０４を介して、読み出しチャネル回路７０２に送信される。前置増幅器７０４は、ディスクプラッター７１６からアクセスされた微小アナログ信号を増幅するように動作可能である。そして、読み出しチャネル回路７０２は受信したアナログ信号をデジタル化及び復号化し、ディスクプラッター７１６に元々書き込まれた情報を再生する。このデータは、読み出しデータ７２２として受信回路に与えられる。読み出しデータを処理している間、読み出しチャネル回路７０２は、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を用いて受信信号を処理する。そのような正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器は、図２〜図４に関して上記で開示した回路に沿って実施することができる。いくつかの実施形態では、復号化は、図５に関して上記で開示したプロセスに沿って実行することができる。書き込み動作は実質的に、先行する読み出し動作の反対であり、書き込みデータ７２４が読み出しチャネル回路７０２に与えられる。次にこのデータは符号化され、ディスクプラッター７１６に書き込まれる。
【００４７】
例えば安価なディスクの冗長アレイ又は独立ディスクの冗長アレイ（ＲＡＩＤ：redundant array of inexpensive disks又はredundantarray of independent disks）に基づく記憶システム等のより大型の記憶システムに、記憶システム７００を統合することができることに留意するべきである。このようなＲＡＩＤ記憶システムは、複数のディスクを論理ユニットとして結合し、冗長性を通じて安定性及び信頼性を増大させる。データは、種々のアルゴリズムに従って、ＲＡＩＤ記憶システムに含まれる複数のディスクにわたって拡散させることができ、ＲＡＩＤ記憶システムが単一のディスクであるかのようにオペレーティングシステムがアクセスすることができる。例えば、データはＲＡＩＤ記憶システム内の複数のディスクにミラーリングすることもできるし、複数の技法において複数のディスクにわたってスライスし分散させることもできる。ＲＡＩＤ記憶システム内の少数のディスクが故障するか又は利用不可能になる場合、誤り訂正技法を用いて、ＲＡＩＤ記憶システム内の他のディスクからのデータの残りの部分に基づいて、欠落データを再生することができる。ＲＡＩＤ記憶システム内のディスクは、限定ではないが、記憶システム７００等の個別の記憶システムとすることができ、互いに近接して配置することもできるし、セキュリティを増大させるために、より広範に分散させることもできる。書き込み動作において、書き込みデータがコントローラーに提供され、コントローラーは、例えば書き込みデータのミラーリング又はストライピングによって、ディスクにわたって書き込みデータを記憶する。読み出し動作において、コントローラーはディスクからデータを取り出す。次に、コントローラーは、ＲＡＩＤ記憶システムが単一のディスクであるかのように結果の読み出しデータを生成する。
【００４８】
さらに、記憶システム７００を、ディスクプラッター７１６によって提供された記憶装置に加えてデータを記憶するのに用いられるソリッドステートメモリを含むように変更することができることに留意するべきである。このソリッドステートメモリは、ディスクプラッター７１６と並列に用いて追加の記憶装置を提供することができる。そのような場合、ソリッドステートメモリは情報を受信し、その情報を読み出しチャネル回路７０２に直接提供する。代替的に、ソリッドステートメモリはキャッシュとして用いることができ、この場合、ディスクプラッター７１６によって提供されるよりも高速のアクセス時間を提供する。そのような場合、ソリッドステートメモリはインターフェースコントローラー７０６と読み出しチャネル回路７０２との間に配置することができ、ここで、要求されたデータがソリッドステートメモリ内で利用可能でないとき、又はソリッドステートメモリが新たに書き込まれたデータセットを保持するのに十分な記憶装置を有していないとき、ソリッドステートメモリはディスクプラッター７１６へのパススルーとして機能する。本明細書において提供される開示に基づいて、当業者であれば、ディスクプラッター７１６及びソリッドステートメモリの双方を含む多岐にわたる記憶システムを認識するであろう。
【００４９】
図８を参照すると、本発明のいくつかの実施形態よる、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を有する受信機８０４を備えた無線通信システム８００又はデータ送信デバイスが示されている。送信機８０２は当該技術分野において既知の転送媒体８０６を介して符号化された情報を送信するように動作可能である。符号化データは受信機８０４によって転送媒体８０６から受信される。受信機８０４は正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を組み込む。復号化は、図２〜図４に関して上記で論述したものと同様の回路を用いて実行することができ、及び／又は図５に関して上記で論述したプロセスに沿って実行することができる。
【００５０】
図９を参照すると、本発明の１つ又は複数の実施形態による正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を有するデータ処理回路９１０を備える別の記憶システム９００が示されている。ホストコントローラー回路９０６が、記憶されるデータ（すなわち、書き込みデータ９０２）を受信する。このデータは、データ処理回路９１０に提供され、このデータ処理回路において、低密度パリティチェック符号器を用いて符号化される。符号化されたデータは、ソリッドステートメモリアクセスコントローラー回路９１２に提供される。ソリッドステートメモリアクセスコントローラー回路９１２は、ソリッドステートメモリへのアクセス及びソリッドステートメモリからのアクセスを制御することが可能な当該技術分野において既知の任意の回路とすることができる。ソリッドステートメモリアクセスコントローラー回路９１２は、受信された符号化データをソリッドステートメモリ９１４への転送のためにフォーマットする。ソリッドステートメモリ９１４は、当該技術分野において既知の任意のソリッドステートメモリとすることができる。本発明のいくつかの実施形態では、ソリッドステートメモリ９１４はフラッシュメモリである。後になって、前に書き込まれたデータがソリッドステートメモリ９１４からアクセスされるとき、ソリッドステートメモリアクセスコントローラー回路９１２は、データをソリッドステートメモリ９１４に要求し、要求したデータをデータ処理回路９１０に提供する。次に、データ処理回路９１０は、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を用いて受信データを復号化する。この復号化は、図２〜図４に関して上記で論述したものと同様の回路を用いて実行することができ、及び／又は図５に関して上記で論述したプロセスに沿って実行することができる。復号化されたデータは、ホストコントローラー回路９０６に提供され、このホストコントローラー回路において、読み出しデータ９０４として渡される。
【００５１】
上記のアプリケーションにおいて論述した様々なブロックは、他の機能とともに集積回路に実装することができることに留意すべきである。そのような集積回路は、所与のブロック、システム若しくは回路の機能の全て、又はブロック、システム若しくは回路のサブセットの機能の全てを含むことができる。また、ブロック、システム又は回路の要素を複数の集積回路にわたって実装することができる。そのような集積回路は、当該技術分野において既知の任意のタイプの集積回路とすることができる。この任意のタイプの集積回路には、モノリシック集積回路、フリップチップ集積回路、マルチチップモジュール集積回路及び／又は混合信号集積回路が含まれるが、これらに限定されるものではない。本明細書において論述されたブロック、システム又は回路の様々な機能を、ソフトウェア又はファームウェアのいずれかで実装することができることにも留意すべきである。そのようないくつかの場合には、システム全体、ブロック全体又は回路全体を、そのソフトウェア等価物又はファームウェア等価物を用いて実装することができる。他の場合には、所与のシステム、ブロック又は回路の一部分をソフトウェア又はファームウェアで実装することができる一方、他の部分はハードウェアで実装することができる。
【００５２】
結論として、本発明の実施形態は、正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化を用いてデータを処理する新規なシステム、デバイス、方法及び構成を提供する。本発明の１つ又は複数の実施形態の詳細な説明が上記で与えられたが、本発明の趣旨から逸脱することなく、様々な代替形態、変更形態及び均等物が当業者には明らかであろう。したがって、上記の説明は本発明の範囲を限定するものとして解釈されるべきではなく、本発明の範囲は添付の特許請求の範囲によって規定される。
【符号の説明】
【００５３】
図２
２０２  Channel LV  チャネルＬＶ
２０４  Memory  メモリ
２０８、２１４、２４０  Zero Padding Circuit  ゼロパディング回路
２１２  Adder  加算器
２２０  Rearranging Circuit  再配列回路
２２６  Shifter  シフター
２３４、２５０  Normalizing Circuit  正規化回路
２４４  Subtractor  減算器
２５４  Variable Node Unit P1  変数ノードユニットＰ１
２５６  Variable Node Unit P2  変数ノードユニットＰ２
２６０  Scaling Circuit  スケーリング回路
２６４  Check Node Unit  検査ノードユニット
図３
３１０  Zero-Padding Circuit  ゼロパディング回路
図４
４１２  Minimum Finder And Multiplexer Array  最小ファインダーマルチプレクサーアレイ
４２６、４３０、４３２  Subtraction Circuit  減算回路
図５
５０２  Retrieve Old Previous Layer Variable Node To Check Node Messages InNormalized Format From Decoder Memory  正規化されたフォーマットの古い前階層の変数ノード／検査ノードメッセージを復号化器メモリから取り出す
５０４  Convert Old Previous Layer Variable Node To Check Node Messages AndNew Previous Layer Check Node To Variable Node Messages To Absolute Format  古い前階層の変数ノード／検査ノードメッセージ及び新しい前階層の検査ノード／変数ノードメッセージを絶対フォーマットに変換する
５０６  Add New Previous Layer Check Node To Variable Node Messages InAbsolute Format To Old Previous Layer Variable Node To Check Node Messages InAbsolute Format To Yield Total Previous Layer Likelihood Values  絶対フォーマットの新しい前階層の検査ノード／変数ノードメッセージを、絶対フォーマットの古い前階層の変数ノード／検査ノードメッセージに加算して、前階層の総尤度値を得る
５０８  Rearrange Total Previous Layer Likelihood Values By Delta EntryValue To Yield Rearranged Previous Layer Likelihood Values  前階層の総尤度値をデルタエントリー値によって再配列して、再配列された前階層の尤度値を得る
５１０  Shift Rearranged Previous Layer Likelihood Values By The DifferenceIn Cyclic Shifts Between The Previous Layer And The Current Layer To YieldCurrent Layer Likelihood Values In Absolute Format  再配列された前階層の尤度値を、前階層と現階層との間の巡回シフトの差分だけシフトして、絶対フォーマットの現階層の尤度値を得る
５１２  Convert Format Of Current Layer Likelihood Values To NormalizedFormat And Output As Soft Decoder Output  現階層の尤度値のフォーマットを正規化されたフォーマットに変換し、軟復号化器出力として出力する
５１４  Convert Format Of Old Current Layer Check Node To Variable NodeMessages To Absolute Format  古い現階層の検査ノード／変数ノードメッセージのフォーマットを絶対フォーマットに変換する
５１６  Subtract Old Current Layer Check Node To Variable Node Messages InAbsolute Format From Current Layer Likelihood Values In Absolute Format ToYield Current Layer Variable Node To Check Node Messages In Absolute Format  絶対フォーマットの古い現階層の検査ノード／変数ノードメッセージを、絶対フォーマットの現階層の尤度値から減算して、絶対フォーマットの現階層の変数ノード／検査ノードメッセージを得る
５１８  Convert Format Of Current Layer Check Node To Variable Node MessagesTo Normalized Format And Update Values In Decoder Memory  現階層の検査ノード／変数ノードメッセージのフォーマットを正規化されたフォーマットに変換し、復号化器メモリにおいて値を更新する
５２０  Perform Check Node Processing To Generate New Previous Layer CheckNode To Variable Node Messages in Normalized Format And Old Current Layer CheckNode  To Variable Node Messages InNormalized Format  検査ノード処理を実行して、正規化されたフォーマットの新しい前階層の検査ノード／変数ノードメッセージ及び正規化されたフォーマットの古い現階層の検査ノード／変数ノードメッセージを生成する
５２２  Max Iterations Or Converged?  最大反復であるか又は収束したか？
５２４  Finished  終了
図６
６０４  Analog Front End  アナログフロントエンド
６１０  Analog To Digital Converter  アナログ／デジタル変換器
６１４  Equalizer  等化器
６２０  Buffer  バッファー
６２４  Detector  検出器
６３０  Interleaver  インターリーバー
６３４  Memory  メモリ
６４０  Non-Binary Layered Low Density Parity Check Decoder With NormalizedInput And Output  正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器
６４６  Deinterleaver  デインターリーバー
６５４  HD Deinterleaver  ＨＤデインターリーバー
６６０  HD Memory  ＨＤメモリ
図７
７０２  Read Channel Including Non-Binary Layered Low Density Parity CheckDecoder With Normalized Input And Output  正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を備える読み出しチャネル
７０４  Preamp  前置増幅器
７０６  Interface Controller  インターフェースコントローラー
７１０  Hard Disk Controller  ハードディスクコントローラー
７１２  Motor Controller  モーターコントローラー
７１４  Spindle Motor  スピンドルモーター
７１６  Disk Platter  ディスクプラッター
７２０  Read/Write Head  読み出し／書き込みヘッド
７２２  Read Data  読み出しデータ
７２４  Write Data  書き込みデータ
図８
８０２  Transmitter  送信機
８０４  Receiver Including Non-Binary Layered Low Density Parity CheckDecoder With Normalized Input And Output  正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を備える受信機
８０６  Transfer Medium  転送媒体
図９
９０２  Write Data  書き込みデータ
９０４  Read Data  読み出しデータ
９０６  Host Controller Circuit  ホストコントローラー回路
９１０  Data Processing Circuit Having Non-Binary Layered Low Density ParityCheck Decoder With Normalized Input And Output  正規化された入力及び出力を有する非バイナリー階層化低密度パリティチェック復号化器を有するデータ処理回路
９１２  Solid State Memory Access Controller Circuit  ソリッドステートメモリアクセスコントローラー回路
９１４  Solid State Memory  ソリッドステートメモリ
【図１】
2015070606.tif 000007
【図２】
2015070606.tif 000008
【図３】
2015070606.tif 000009
【図４】
2015070606.tif 000010
【図５】
2015070606.tif 000011
【図６】
2015070606.tif 000012
【図７】
2015070606.tif 000013
【図８】
2015070606.tif 000014
【図９】
2015070606.tif 000015