(57)【特許請求の範囲】
【請求項１】
パリティチェック行列に基づいてメッセージ情報から符号語を生成する方法であって、
三角部分行列Ｔ、部分行列Ａ、部分行列Ｂ、部分行列Ｃｍ１、及び部分行列Ｄｍ１を含み
【数４】
0005913560.tif 000005
で配列される第１の行列に対して、前記部分行列Ｃｍ１に追加の三角行列化演算を行うことで前記部分行列Ｃｍ１及びＤｍ１の最後の行を全て０とすると共に、当該最後の行を削除して、前記部分行列Ａ、前記部分行列Ｂ、前記部分行列Ｃｍ１、及び前記部分行列Ｄｍ１を部分行列Ａｍ２、部分行列Ｂｍ２、部分行列Ｃｍ２、及び部分行列Ｄｍ２にそれぞれ変換し、もって、前記第１の行列から、前記三角部分行列Ｔ、前記部分行列Ａｍ２、前記部分行列Ｂｍ２、前記部分行列Ｃｍ２、及び前記部分行列Ｄｍ２を含み
【数５】
0005913560.tif 000006
で配列される第２の行列を生成することを特徴とする方法。
【請求項２】
前記三角部分行列Ｔは上三角部分行列であり、前記追加の三角行列化演算は上三角行列化演算であることを特徴とする請求項１に記載の方法。
【請求項３】
前記符号語はメッセージ情報をｕとし、第１ビット長パリティ部分をｐ１、第２ビット長パリティ部分をｐ２として、
ｐ２＝（Ｃｍ２−１Ｄｍ２）ｕと、
ｐ１＝Ｔ−１（Ａｍ２ｐ２＋Ｂｍ２ｕ）と
の２式を満たすように生成されることを特徴とする請求項１または２のいずれか一項に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
＜優先出願＞
本願は、その全体で参照することにより本明細書に組み込まれる、２０１１年４月８日に出願された米国特許第１３／０８３，３４１号の優先利益を主張するものである。
【背景技術】
【０００２】
多くの電気デバイスおよびシステムは、金属導体、光ファイバケーブル、および空気等の伝送媒体を介して、情報を相互に交換する。粗悪または欠陥のある伝送媒体は、そのような情報にエラーを引き起こし得る。媒体の伝送能力（例えば、伝送速度）を超えることもまた、エラーを引き起こし得る。ある状況においては、エラーを訂正することができる。多くの従来の技法は、受信された後に情報の妥当性をチェックするために符号を使用する。いくつかの符号もまた、エラーを訂正することを支援し得る。例えば、低密度パリティチェック（ＬＤＰＣ）符号をエラー訂正に使用することができる。しかしながら、いくつかの従来の技法では、ＬＤＰＣ符号を使用することは、複雑なコーディング演算を伴い得るか、または多数の回路構成要素が動作することを要求し得る。したがって、ＬＤＰＣ符号は、いくつかのデバイスまたはシステムにとって不適切であり得る。
【図面の簡単な説明】
【０００３】
【図１】本発明の実施形態による、ＬＤＰＣ符号に関するメッセージ情報を符号化して、符号語を形成するように構成されるエンコーダを含む、装置のブロック図を示す。
【図２】本発明の実施形態による、ＬＤＰＣ符号のパリティチェック行列Ｈの実施例を示す。
【図３】本発明の実施形態による、ＬＤＰＣ符号のパリティチェック行列Ｈに基づいて情報を符号化する方法のフローチャートである。
【図４】本発明の実施形態による、ＬＤＰＣ符号のパリティチェック行列Ｈから生成された行列のブロック構造を示す。
【図５】本発明の実施形態による、図４の行列から生成された行列のブロック構造を示す。
【図６】本発明の実施形態による、図４の行列から生成された行列のブロック構造を示す。
【図７】本発明の実施形態による、エンコーダを含むシステムのブロック図を示す。
【発明を実施するための形態】
【０００４】
図１は、本発明の実施形態による、ＬＤＰＣ符号に関するメッセージ情報ｕを符号化して、符号語Ｖｍを形成するように構成されるエンコーダ１０１を含む、装置１００のブロック図を示す。装置１００は、メッセージ情報ｕを提供する情報源１１０と、エンコーダ１０１から符号語Ｖｍを受信するメモリ領域１２０とを含むことができる。情報源１１０は、メモリコントローラまたはプロセッサ等のデバイスによって提供することができる。メモリ領域１２０は、符号語Ｖｍを記憶するメモリアレイを含むことができる。エンコーダ１０１およびメモリ領域１２０は、メモリデバイスまたはメモリコントローラ等の同一デバイスに含まれることができる。装置１００は、メモリモジュール、情報を無線で伝送および受信することが可能なシステムまたはデバイス、および／または情報伝送においてエラー訂正を提供する能力を有する他の通信システムおよびデバイスを含んでもよい。図１は、本明細書で説明される実施形態に焦点を当てるように、装置１００の追加の詳細を省略する。
【０００５】
エンコーダ１０１は、Ｈ行列１３０に関するメッセージ情報ｕから符号語Ｖｍを生成する、ＬＤＰＣエンコーダの形態で実現することができる。Ｈ行列１３０は、装置１００の内部に、または装置１００の外部に記憶することができる。Ｈ行列１３０は、ＬＤＰＣ符号のパリティチェック行列Ｈを含むことができる。当業者によって理解されるように、情報を伝送する際に使用される符号のＨ行列１３０等のＨ行列は、漸進的エッジ成長ＬＤＰＣ符号構造、リード・ソロモンＬＤＰＣ符号構造、ユークリッド幾何学に基づくＬＤＰＣ符号構造、ファンデルモンド行列および巡回置換ブロックに基づくＬＤＰＣ符号構造、ならびに種々の他のＬＤＰＣ構造等の種々の符号構造を使用して、生成（例えば、構築）することができる。Ｈ行列１３０等のＨ行列は、コンピュータによって生成することができる。
【０００６】
図１は、符号語Ｖｍが、パリティ情報ｐおよびメッセージ情報ｕの組み合わせを含有する系統的符号語であり得ることを示す、符号語Ｖｍ＝［ｐｕ］を示す。メッセージ情報ｕは、いくつかの情報ビットを含むことができる。パリティ情報ｐは、いくつかのパリティビットを含むことができる。符号語Ｖｍ＝［ｐｕ］は、メッセージ情報ｕのメッセージビットが、Ｈ行列１３０の列の一部分に対応することができ、パリティ情報ｐのパリティビットが、行列１３０の列の別の部分に対応することができる、Ｈ行列１３０によって定義することができる。図１は、パリティ情報ｐが第１の符号語位置に位置し、その後にメッセージ情報ｕが続く、符号語Ｖｍ＝［ｐｕ］の実施例を示す。順番を逆転させることもできる。メッセージ情報ｕは、符号語Ｖｍ＝［ｕｐ］であるように、第１の符号語位置に位置することができ、その後にパリティ情報ｐが続く。
【０００７】
装置１００では、Ｈ行列１３０等の符号の所与のＨ行列とともに、メッセージ情報ｕが分かっているため、エンコーダ１０１によって行われる符号化演算は、受信されたメッセージ情報ｕおよび所与のＨ行列に基づいて、パリティ情報ｐを生成することを伴う。次いで、エンコーダ１０１は、符号語Ｖｍ＝［ｐｕ］を形成するように、受信されたメッセージ情報ｕを生成されたパリティ情報ｐと組み合わせることができる。元のメッセージ情報ｕを読み出すように符号語Ｖｍを復号することは、逆の順番で行うこともできる。例えば、パリティ情報ｐを生成するように符号化中に行われる符号化プロセス（例えば、ステップ）は、復号された情報を生成するように、逆の順番で符号語Ｖｍに行うことができる。次いで、符号化に使用される同一のＨ行列は、復号された情報に基づいて元のメッセージ情報ｕを生成するために、復号中に使用することができる。本明細書の説明は、図２から７を参照して詳細に説明されるように、受信されたメッセージ情報ｕおよびＬＤＰＣ符号の所与のＨ行列に基づいて、符号語Ｖｍ＝［ｐｕ］を生成する符号化に焦点を当てる。
【０００８】
図２は、ＬＤＰＣ符号のパリティチェック行列Ｈの実施例を示す。行列Ｈは、行および列で配列され、（ｎ−ｋ＋ｍ）行およびｎ列に対応する、サイズ（ｎ−ｋ＋ｍ）×（ｎ）を有する。パラメータｍは、行列Ｈの従属行の数に対応する。行列の階数は、その行列の従属行の数である。したがって、行列Ｈが最大階数行列である場合、パラメータｍ＝０である。行列Ｈが階数欠陥（例えば、最大階数ではない）行列である場合、パラメータｍ＞０である。パラメータｎは、符号語の中の符号ビットの数である。パラメータｋは、符号語の中の情報ビットの数である。したがって、行列Ｈの各行（各符号語）の中に、ｋ個の情報ビットおよびｎ−ｋ個のパリティビットの組み合わせによって形成される、ｎ個の全符号ビットがある。
【０００９】
図２に示されるように、行列Ｈは、ゼロ（「０」）および１（「１」）の入力のみを有する、２進数行列の実施例である。ＬＤＰＣ符号は、大部分は、０および限定数の１を含有する、パリティチェック行列Ｈを使用する。簡単にするために、図１は、行列Ｈの入力のうちのいくつかのみを示す。図１の行列Ｈ等のパリティチェック行列Ｈに基づいて、本明細書で説明されるエンコーダ（例えば、図１のエンコーダ１０１）は、パリティ情報およびメッセージ情報の組み合わせを含む符号語を生成するために、メッセージ情報と関連付けられるパリティ情報を生成することができる。
【００１０】
図３は、本発明の実施形態による、ＬＤＰＣ符号のパリティチェック行列Ｈに基づいて情報を符号化する方法３００のフローチャートである。方法３００で使用されるパリティチェック行列Ｈは、図１および図２を参照して上記で説明されるＬＤＰＣ符号の行列Ｈを含むことができる。
【００１１】
図３では、方法３００は、パリティチェック行列Ｈ（例えば、図１および図２の行列Ｈ）から第１の行列（例えば、Ｈｍ）を生成する活動３１０を含むことができる。第１の行列は、それが第１の行列の左上隅に上三角部分行列を有するように生成することができる。活動３１０はまた、第１の行列を生成するために使用されるパリティチェック行列Ｈの階数を計算することもできる。
【００１２】
上三角部分行列の行の総数がパリティチェック行列Ｈの階数に等しい場合、方法３００は、少なくとも部分的に第１の行列に基づいて、メッセージ情報を符号化するようにパリティ情報を生成する活動３２０を含むことができる。方法３２０は、活動３２０を行った後に停止してもよい。
【００１３】
第１の上三角部分行列の行の総数がパリティチェック行列Ｈの階数より小さい場合、方法３００は、第２の行列（例えば、Ｈｍ２）を生成する（例えば、形成する）ように、第１の行列の第２の部分行列に上三角行列化演算を行う活動３３０を続けてもよい。方法３００の３４０の活動は、少なくとも部分的に第２の行列に基づいて、メッセージ情報を符号化するようにパリティ情報を生成することができる。
【００１４】
方法３００の活動３１０、３２０、３３０、および３４０のうちのいくつかまたは全ては、コンピュータ等の電子ユニットのプロセッサによって行うことができる。例えば、活動３１０、３２０、および３３０は、コンピュータによって行うことができる。方法３００の活動３１０、３２０、３３０、および３４０のうちのいくつかまたは全てはまた、図１のエンコーダ１０１等のエンコーダによって行うことができる。そのようなエンコーダは、プロセッサ、メモリコントローラ、またはメモリデバイス等のデバイスに含むことができる。方法３００は、図４から７を参照して以下で説明される１つ以上の活動を含んでもよい。
【００１５】
図４は、本発明の実施形態による、ＬＤＰＣ符号のパリティチェック行列Ｈから生成された行列Ｈｍのブロック構造を示す。行列Ｈｍは、図１または図２の行列Ｈ等のＬＤＰＣ符号のパリティチェック行列Ｈから生成することができる。本明細書で説明されるエンコーダ（例えば、図１のエンコーダ１０１）は、メッセージ情報を受信し、パリティ情報および受信されたメッセージ情報を有する符号語を生成するために行列Ｈｍを使用することができる。
【００１６】
従来、生成行列Ｇｍが、メッセージ情報を符号化するために使用される。例えば、行列Ｈ＝［Ｉｎ−ｋ｜Ｐ］を、行列Ｈから生成することができ、この場合Ｉｎ−ｋは、恒等部分行列であり、Ｐは、行列Ｇの部分行列である。次いで、ＰＴが部分行列Ｐの転置を表す、Ｇｍ＝［ＰＴ｜Ｉｋ］であるように、行列Ｇｍを行列Ｇから生成することができる。符号語＝ｕ＊Ｇｍを生成することができ、この式中の記号「＊」は、乗算を表す。したがって、従来の符号化では、生成行列Ｇｍが、メッセージ情報を符号化するために使用される。しかしながら、従来の方法は、複雑で、いくつかのシステムまたはデバイスにとって不適切であり得る。例えば、生成行列Ｇｍまたは生成行列Ｇｍおよび行列Ｈの両方と関連付けられる情報を処理して記憶するために、多数の回路構成要素、例えば、排他的ＯＲ（ＸＯＲ）ゲートが必要とされ得る。
【００１７】
本明細書で説明されるエンコーダは、従来の生成行列Ｇｍ等の行列を生成することなく、行列Ｈｍから直接、符号語を生成することができる。本明細書で説明されるように行列Ｈｍに基づいて符号語を生成するエンコーダは、あまり複雑ではなく、削減された数の構成要素、例えば、排他的ＯＲゲートを有し得る。
【００１８】
図４に示されるように、行列Ｈｍは、行列Ｈｍの種々の部分に位置する部分行列Ｔ、Ａ、Ｂ、Ｅ、Ｃ、およびＤを含む。例えば、部分行列Ｔは、行列Ｈｍの左上隅部分に位置する。部分行列Ｂは、行列Ｈｍの右上隅部分に位置する。部分行列Ａは、部分行列Ｔと部分行列Ｂとの間の行列Ｈｍの中間部分に位置する。部分行列Ｅは、部分行列Ｔより下側の行列Ｈｍの左下隅部分に位置する。部分行列Ｄは、行列Ｈｍの右下隅部分に位置する。部分行列Ｄは、部分行列Ｅと部分行列Ｄとの間、および部分行列Ａより下側の行列Ｈｍの中間部分に位置する。これらの部分行列のサイズは、以下の通りである。
Ｔ：（ｎ−ｋ−ｇ）×（ｎ−ｋ−ｇ）
Ａ：（ｎ−ｋ−ｇ）×ｇ
Ｂ：（ｎ−ｋ−ｇ）×ｋ
Ｃ：ｇ×ｇ
Ｄ：ｇ×ｋ
Ｅ：ｇ×（ｎ−ｋ−ｇ）
【００１９】
行列Ｈｍは、貪欲上三角行列化演算として知られているプロセスを行うことによって生成することができる。この演算は、行列Ｈｍの左上隅に、部分行列Ｔである上三角行列を生成する。この演算は、パリティチェック行列Ｈの行のみを交換すること、列のみを交換すること、または行および列のみを交換することを伴う。パリティチェック行列Ｈの行へのいずれの算術演算（例えば、いずれのガウス消去演算）も、この演算では行われない。
【００２０】
部分行列Ｔは、（ｎ−ｋ−ｇ）行および（ｎ−ｋ−ｇ）列を有する、正方形の上三角行列である。部分行列Ｔは、その対角線入力に全て１を有し、その対角線入力より下側に全て０を有する。部分行列Ｔの行の数がパリティチェック行列Ｈの階数Ｒに等しい場合には、ｇ＝０である、（ｎ−ｋ−ｇ）＝Ｒであるように、行列Ｈｍの中でパラメータｇ＝０である。また、ｇ＝０である場合には、部分行列Ａは消去され、部分行列Ｂの一部になり、部分行列Ｅ、Ｃ、およびＤは消去され、部分行列Ｔおよび部分行列Ｂの一部になる。この場合、（ｎ−ｋ＝Ｒ）であり、部分行列Ｔがサイズ（ｎ−ｋ＝Ｒ）×（ｎ−ｋ＝Ｒ）を有し、部分行列Ｂがサイズ（ｎ−ｋ＝Ｒ）×ｋを有する、行列Ｈｍ＝［Ｔ｜Ｂ］である。
【００２１】
ｕがメッセージ情報を表す、符号語Ｖｍ＝［ｐｕ］を生成するために、図１のエンコーダ１０１等のエンコーダが行列Ｈｍを使用するとき、パリティ情報（ｐ）を以下のように生成することができる（ｇ＝０について）。行列Ｈｍについては、有効符号語Ｖｍのシンドロームは、式Ｈｍ＊ＶｍＴ＝０が満たされるように、サイズｎ−ｋの全てゼロのベクトルである。Ｈｍ＝［Ｔ｜Ｂ］およびＶｍ＝［ｐｕ］であるため、ＶｍＴ＝［ｐｕ］Ｔを式Ｈｍ＊ＶｍＴ＝０に代入することによって、以下の式を得ることができる。
【数１】
0005913560.tif 000002
上記の式を解くことにより、以下の方程式（１）をもたらす。
Ｔｐ＝Ｂｕ、したがって、
ｐ＝Ｔ−１Ｂｕ                                            （方程式１）
【００２２】
図１のエンコーダ１０１等のエンコーダは、符号語Ｖｍのパリティ情報ｐを生成するように構成することができる。したがって、ＬＤＰＣ符号の所与のパリティチェック行列Ｈについて、図４に示される行列Ｈｍを生成することができる。行列Ｈｍの部分行列Ｔの行の総数がパリティチェック行列Ｈの階数Ｒに等しい場合には、エンコーダは、方程式（１）に基づいてパリティ情報ｐを生成するように構成することができる。パリティ情報は、符号語Ｖｍ＝［ｐｕ］を生成するように、受信されたメッセージ情報ｕと組み合わせることができる。行列Ｈｍの部分行列Ｔの行の総数がパリティチェック行列Ｈの階数Ｒに等しい場合に、本明細書で説明されるエンコーダが、方程式（１）に基づいて符号語Ｖｍを生成することができるため、エンコーダは、他の値、例えば、Ｂおよびｕが行列Ｈｍおよびメッセージ情報ｕから入手可能であるため、（パリティチェック行列Ｈではなく）行列ＨｍおよびＴ−１のみを符号化のために記憶（例えば、メモリに記憶）してもよい。符号化中に、エンコーダは、Ｔ−１および行列Ｈｍの記憶された入力を読み出して、方程式（１）に基づいてパリティ情報ｐを生成し、かつ符号語Ｖｍ＝［ｐｕ］を生成するように、メモリにアクセスしてもよい。
【００２３】
行列Ｈｍの部分行列Ｔの行の総数がパリティチェック行列Ｈの階数Ｒより小さい場合、図５および図６を参照して説明されるように、パリティ情報を生成するように、追加の演算を図４の行列Ｈｍに行うことができる。
【００２４】
図４を参照して上記で説明されるように、行列Ｈｍは、パリティチェック行列Ｈの行または列のみ、あるいは両方を交換することによって生成することができる。行列Ｈｍを生成するために使用されるプロセスはまた、追跡記録（例えば、マップ）を生成すること（例えば、作成すること）を含んでもよい。この追跡記録は、行列Ｈｍの生成中に交換されたパリティチェック行列Ｈの行または列の位置番号を追跡する（例えば、マップする）ことができる。行列Ｈｍの部分行列Ｔが、パリティチェック行列Ｈの列を交換することによって生成されるため、追跡記録はまた、部分行列Ｔの少なくとも一列の位置番号とパリティチェック行列Ｈの少なくとも一列の位置番号との間のリンクも含有する。
【００２５】
追跡記録は、元のメッセージ情報ｕを得るために、符号語Ｖｍの復号中に使用することができる。例えば、復号中に、デインターリービング演算等の演算を行うことができる。そのような演算は、系統的形態ではない符号語Ｖを生成するように、追跡記録に基づくが、逆の順番で、符号語Ｖｍの列を交換することもできる。元のメッセージ情報ｕを生成するためにパリティチェック行列Ｈを使用して、符号語Ｖを復号するためにデコーダを使用することができる。
【００２６】
行列Ｈｍの部分行列Ｔを生成する上三角行列化演算中に、部分行列Ｔの列を生成するように、パリティチェック行列Ｈの列をランダムに選択することができる。このランダム選択は、Ｒがパリティチェック行列Ｈの階数である、サイズＲ×Ｒを有する部分行列Ｔの確率を増加させてもよい。部分行列Ｔの行の総数は、部分行列ＴがサイズＲ×Ｒを有するときのＲに等しい。部分行列ＴのサイズがＲ×Ｒである場合には、行列Ｈｍは、完全三角構造を有することができ、例えば、図４のパラメータｇがゼロに等しい（例えば、ｎ−ｋ＝Ｒ）、Ｈｍ＝［Ｔ｜Ｂ］である。図４を参照して上記で説明されるように、方程式１は、部分行列ＴがサイズＲ×Ｒを有する場合に、エンコーダで使用することができる。
【００２７】
場合によっては、パリティチェック行列Ｈの入力の値に応じて、上三角行列化演算は、サイズＲ×Ｒを有する部分行列Ｔの生成に失敗し得る（例えば、部分行列Ｔの行の総数がＲより小さい）。そのような場合、行列Ｈｍは、完全三角構造を持たないが、パラメータｇがゼロではない、図４に示されるような近三角構造を有する。この場合、方程式（１）は、パリティ情報を生成するために適用不可能であり得る。しかしながら、行列Ｈｍ１（図５）および行列Ｈｍ２（図６）を生成するように、追加の演算を行列Ｈｍに行うことができる。パリティ情報は、行列Ｈｍ２に基づいて生成することができる。
【００２８】
図５および図６は、それぞれ、本発明の実施形態による、図４の行列Ｈｍから生成された行列Ｈｍ１およびＨｍ２のブロック構造を示す。符号語Ｖｍは、図５の行列Ｈｍ１の説明の後に以下で説明されるように、図６の行列Ｈｍ２を使用して生成することができる。
【００２９】
図５に示されるように、行列Ｈｍ１は、図４の行列Ｈｍのものと同一のブロック構造を有する。しかしながら、図５の行列Ｈｍ１の部分行列Ｅ、Ｃｍ１、およびＤｍ１の入力の値は、図４の行列Ｈｍの対応する部分行列Ｅ、Ｃ、およびＤのものとは異なる。図５に示されるように、部分行列Ｅの全ての入力はゼロ（「０」）である。部分行列Ｃｍ１およびＤｍ１は、その入力の全てをゼロにするように部分行列Ｅに行われる演算により、図４の対応する部分行列ＣおよびＤより低希薄（より高密度）であり得る。そのような演算は、算術演算、例えば、ガウス消去演算を含むことができる。部分行列Ｅ、Ｃ、およびＤの行が行列Ｈｍの同一行の一部であるため、行列Ｈｍの部分行列Ｅの行に行われる演算はまた、行列Ｈｍの部分行列ＣおよびＤの行も修正する。したがって、部分行列Ｅの全ての入力がゼロになった後、図４の部分行列ＣおよびＤは、図５の部分行列Ｃｍ１およびＤｍ１になる。
【００３０】
図６は、本発明の実施形態による、行列Ｈｍ１から生成された行列Ｈｍ２のブロック構造を示す。行列Ｈｍ２から、符号語Ｖｍのパリティ情報を生成する方程式を得るように、計算を行うことができる。図６に示されるように、行列Ｈｍ２は、図５の行列Ｈｍのものと同一のブロック構造を示す。しかしながら、行列Ｈｍ２は、全てゼロの入力を有する、いくつかの行ｒを含むことができる。図６に示される、行列Ｈｍ１の特定数の行および列、ならびに行列Ｈｍ１の部分行列のうちのそれぞれの特定のサイズは、本明細書の説明に焦点を当てることに役立つように、例証目的のためのものにすぎない。
【００３１】
図４を参照して上記で説明されるように、（図６に示されるような）上三角部分行列Ｔを生成するように、上三角行列化演算をパリティチェック行列Ｈに行うことができる。図５および図６では、部分行列Ｃｍ１の対角線に可能な限り多くの１（「１」）を持たせるように、追加の上三角行列化演算を部分行列Ｃｍ１に行うことができる。追加の上三角行列化演算は、部分行列Ｃｍ１の対角線内の全ての入力に１という値を持たせなくてもよい。しかしながら、追加の上三角行列化演算は、部分行列Ｃｍ１の対角線内の少なくとも１つの入力に１という値を持たせてもよい。例えば、図６に示されるように、追加の上三角行列化演算は、部分行列Ｃｍ１の対角線内の５つの入力のうちの３つに１という値を持たせてもよい。部分行列Ｃｍ１の中の入力ｘは、１または０のいずれかであり得る。追加の上三角行列化演算は、図６に示される場合等、追加の１を部分行列Ｃｍ１の対角線内で形成することができないときに、停止してもよい。追加の上三角行列化演算はまた、部分行列Ｄｍ１の最終行のうちの１つ以上に０という値を持たせてもよい。追加の上三角行列化演算は、行列Ｈｍ２を生成する。図６に示されるように、行列Ｈｍ２は、全ての入力がゼロを有する、いくつかの行ｒを有する。図６は、実施例としてｒ＝２を示す。ｒの値は、変化し得る。
【００３２】
全てゼロを伴う入力を有する、これらのｒ行は、パリティチェック行列Ｈの中の従属行に対応する。したがって、ｒ行を行列Ｈｍ２から除去することができる。したがって、ｒ行が除去された後、行列Ｈｍ２は、行列Ｈｍ１より少ない行（ｒ行だけ少ない）を有することができる。
【００３３】
部分行列Ｃｍ１に行われる追加の上三角行列化演算は、行を交換すること、列を交換すること、および算術演算（例えば、ガウス消去演算）の任意の組み合わせを含むことができる。比較として、三角部分行列Ｔ（図４）を生成するようにパリティチェック行列Ｈに行われる上三角行列化演算は、いずれの算術演算も含まなくてもよい（例えば、行および列のみを交換する）。
【００３４】
部分行列Ｃｍ１に行われる追加の上三角行列化演算はまた、部分行列Ａ、Ｂ、Ｃｍ１、およびＤｍ１の行および列を修正することもできる。したがって、追加の上三角行列化演算後に、行列Ｈｍ１（図５）の部分行列Ａ、Ｂ、Ｃｍ１、およびＤｍ１は、図６の行列Ｈｍ２の部分行列Ａｍ２、Ｂｍ２、Ｃｍ２、およびＤｍ２になる。
【００３５】
ｕがメッセージ情報を表す、符号語Ｖｍ＝［ｐｕ］を生成するために、図１のエンコーダ１０１等のエンコーダが行列Ｈｍ２を使用するとき、パリティ情報ｐを以下のように生成することができる。
【００３６】
図４、図５、および図６を参照して上記で説明されるように、行列Ｈｍ２は、行列Ｈｍ１から生成され、ひいては、行列Ｈｍから生成される（図４）。行列Ｈｍが適切な三角構造（パラメータがｇがゼロではない）を有するため、Ｖｍ＝［ｐｍｕ］の系統的符号語のパリティ情報ｐは、（ｎ−ｋ−ｇ）ビット長パリティ部分ｐ１およびｇビット長パリティ部分ｐ２といった、２つの部分から成ると見なすことができる。よって、ｐ＝［ｐ１ｐ２］であり、したがって、Ｖｍ＝［ｐｕ］＝［ｐ１ｐ２ｕ］である。
【００３７】
行列Ｈｍ２については、有効符号語Ｖｍのシンドロームは、Ｈｍ２＊ＶｍＴ＝０が満たされるように、サイズｎ−ｋの全てゼロのベクトルである。Ｖｍ＝［ｐ１ｐ２ｕ］であるため、ＶｍＴ＝［ｐ１ｐ２ｕ］Ｔである。図６に示されるように、
【数２】
0005913560.tif 000003
であり、ＶｍＴ＝［ｐ１ｐ２ｕ］Ｔを方程式Ｈｍ２＊ＶｍＴ＝０に置換することによって、以下の方程式を得ることができる。
【数３】
0005913560.tif 000004
【００３８】
上記の方程式を解くことにより、以下の方程式（２）および方程式（３）をもたらす。
Ｃｍ２ｐ２＝Ｄｍ２ｕ  したがって、
ｐ２＝（Ｃｍ２−１Ｄｍ２）                             （方程式２）
Ｔｐ１＝（Ａｍ２ｐ２＋Ｂｍ２ｕ）  したがって、
ｐ１＝Ｔ−１（Ａｍ２ｐ２＋Ｂｍ２ｕ）  方程式（２）からのｐ２＝（Ｃｍ２−１Ｄｍ２）を方程式ｐ１＝Ｔ−１（Ａｍ２ｐ２＋Ｂｍ２ｕ）に代入することにより、方程式（３）をもたらす。
ｐ１＝Ｔ−１（Ａ（Ｃｍ２−１Ｄｍ２）＋Ｂｍ２ｕ）             （方程式３）
【００３９】
方程式（２）および方程式（３）に基づいて、図１のエンコーダ１０１等のエンコーダ１０１は、符号語Ｖｍのパリティ情報ｐを生成するように構成することができる。したがって、ＬＤＰＣ符号の所与のパリティチェック行列Ｈについて、図６に示される行列Ｈｍ２を生成することができる。次いで、行列Ｈｍ２に基づいて、パリティ情報ｐ１およびｐ２を生成するように、方程式（２）および方程式（３）を計算することができる。エンコーダは、符号語Ｖｍ＝［ｐ１ｐ２ｕ］を生成するように、パリティ情報ｐ１およびｐ２を受信されたメッセージ情報ｕと組み合わせることができる。
【００４０】
上記で説明されるように、行列Ｈｍ１およびＨｍ２を生成するために使用されるプロセスはまた、追跡記録（例えば、マップ）を生成すること（例えば、作成すること）を含んでもよい。この追跡記録は、行列Ｈｍ１およびＨｍ２の生成中に交換されたパリティチェック行列Ｈの行または列の位置番号を追跡することができる。例えば、この追跡記録は、部分行列Ｅの全ての入力をゼロにする演算および部分行列Ｃｍ１に行われた三角行列化演算の両方の間に交換された、パリティチェック行列Ｈの行または列の位置番号を追跡することができる。この追跡記録はまた、行列Ｈｍ１およびＨｍ２の生成中に交換されたパリティチェック行列Ｈの行または列の位置番号を結び付ける（例えば、マップする）こともできる。したがって、この追跡記録はまた、行列Ｈｍ２の列の位置番号とパリティチェック行列Ｈの列の位置番号との間のリンクも含有する。
【００４１】
行列Ｈｍ１およびＨｍ２（図５および６）の生成中に生成される追跡記録と、行列Ｈｍ（図４）の生成中に生成される追跡記録の組み合わせは、元のメッセージ情報ｕを得るために、符号語Ｖｍの復号中にパリティチェック行列Ｈとともに使用することができる。行列Ｈｍ、Ｈｍ１、およびＨｍ２の生成、ならびに追跡記録の生成および方程式１、２、および３等の関連活動は、コンピュータ等の電子ユニットによって行うことができる。例えば、そのような電子ユニットは、パリティチェック行列Ｈと関連付けられる入力情報を受信してもよい。次いで、入力情報に基づいて、電子ユニットは、Ｈｍ、Ｈｍ１、およびＨｍ２、追跡記録、ならびに方程式１、２、および３等の出力情報を生成してもよい。
【００４２】
上記で説明されるように、本明細書で説明されるエンコーダは、方程式（２）および（３）に基づいて符号語Ｖｍを生成することができる。方程式（２）および（３）の中のパラメータにおける乗算は、排他的ＯＲ加算等の演算によって得ることができる。したがって、他の値、例えば、Ａ、Ｂ、およびｕが、行列Ｈｍおよびメッセージ情報ｕから入手可能であるため、エンコーダは、（パリティチェック行列Ｈではなく）行列Ｈｍ２および積Ｃｍ２−１Ｄｍ２のみを記憶してもよい。さらなる計算が、Ｄｍ＝ＥＴ−１Ｂを提供してもよい。Ｄｍが行列Ｈｍ１から入手可能であり得、Ｄｍ２も入手可能であり得、Ｄｍ２がＤｍの修正版であるため、Ｄｍ２は、符号化演算のために記憶される必要がなくてもよい。したがって、代替として、エンコーダは、（Ｄｍ２を記憶することなく）行列Ｈｍ２およびＣｍ２−１およびＴ−１のみを記憶（例えば、メモリに記憶）してもよい。符号化中に、エンコーダは、行列Ｈｍ２およびＣｍ２−１およびＴ−１の入力を読み出して、方程式（２）および（３）に基づいてパリティ情報ｐ１およびｐ２を生成し、かつ符号語Ｖｍ＝［ｐ１ｐ２ｕ］を生成するように、メモリにアクセスしてもよい。
【００４３】
比較として、従来の符号化は、生成行列Ｇｍの部分行列Ｐを記憶し得る。部分行列Ｐは、サイズｋ×（ｎ−ｋ）を有する。本明細書で説明される符号化では、行列Ｈｍ２の部分行列Ｃｍ２−１およびＤｍ２およびＴ−１のうちのそれぞれは、部分行列Ｐのサイズより小さいサイズを有する。
【００４４】
図７は、本発明の実施形態による、エンコーダ７０１を含むシステム７００のブロック図を示す。エンコーダ７０１は、図１のエンコーダ１０１に対応することができる。例えば、エンコーダ７０１は、Ｈ行列７３０に関するメッセージ情報ｕから符号語Ｖｍを生成する、ＬＤＰＣエンコーダの形態で実現することができる。Ｈ行列７３０は、システム７００の内部に、またはシステム７００の外部に記憶することができる。
【００４５】
システム７００は、情報を記憶するメモリデバイスを有する、メモリシステムであり得る。例えば、システム７００は、メモリデバイスを含むことができる、デバイス７２０から及びデバイス７２０へと往復する情報の転送を制御するように、メモリコントローラを含むことができる、デバイス７１０を含むことができる。
【００４６】
図７に示されるように、デバイス７２０に転送される情報は、図１から図６を参照して上記で説明される符号語Ｖｍに対応することができる、符号語Ｖｍを含むことができる。デバイス７２０は、メモリセル７２１を含むことができる。デバイス７２０は、書き込み動作中にデバイス７１０から符号語Ｖｍを受信し、メモリセル７２１に符号語Ｖｍを記憶することができる。デバイス７２０はまた、符号語Ｖｍをデバイス７１０に出力する読取動作を含むこともできる。メモリセル７２１は、揮発性メモリセル、不揮発性メモリセル、または両方を含むことができる。揮発性メモリセルの実施例は、ランダムアクセスメモリ（ＲＡＭ）セルを含む。不揮発性メモリセルの実施例は、フラッシュメモリセル、抵抗ランダムアクセスメモリ（ＲＲＡＭ（登録商標））セル、および相変化メモリセル、ならびに他の種類の不揮発性メモリセルを含む。
【００４７】
システム７００は、デバイス７１０のメモリ７２５およびデバイス７２０のメモリセル７２１の一方または両方に、符号化演算と関連付けられるパラメータを記憶することができる。これらのパラメータは、図４から６を参照して上記で説明される追跡記録等の追跡記録を含むことができる。デバイス７１０のデコーダ７０２は、（デバイス７２０から受信される）符号語Ｖｍを復号して元のメッセージ情報ｕを得るために、記憶されたパラメータおよびＨ行列７３０を使用してもよい。
【００４８】
システム７００はまた、汎用プロセッサ等のプロセッサ、または特定用途向け集積回路（ＡＳＩＣ）を含むことができる、デバイス７４０を含むこともできる。動作、例えば、デバイス７２０の書き込み動作中に、デバイス７１０は、インターフェース７５１に連結される、その入力において、メッセージ情報ｕを受信してもよい。デバイス７１０は、メッセージ情報ｕを有する符号語Ｖｍを生成し、インターフェース７５２に連結される、その出力に符号語Ｖｍを提供してもよい。別の動作、例えば、デバイス７２０の読取動作中に、デバイス７１０は、インターフェース７５２を介して、デバイス７２０から出力される符号語Ｖｍを受信し、メッセージ情報ｕを得るように符号語Ｖｍを復号し、次いで、インターフェース７５１を介して、メッセージ情報ｕをデバイス７４０に送信してもよい。インターフェース７５１は、有線インターフェースまたは無線インターフェース、あるいは両方の組み合わせを含むことができる。インターフェース７５２は、有線インターフェースまたは無線インターフェース、あるいは両方の組み合わせを含むことができる。インターフェース７５１および７５２のうちのそれぞれは、双方向インターフェースを含むことができる。例えば、インターフェース７５２は、同双方向インターフェース上でデバイス７２０を往復して符号語Ｖｍを転送するように、双方向導体（例えば、直列バスまたは並列バス）を含むことができる。
【００４９】
システム７００はまた、記憶デバイス７６０を含むこともできる。記憶デバイス７６０の一部分またはメモリ７２５全体は、システム７００の外部にあり得る。記憶デバイス７６０は、１つ以上のプロセッサ（例えば、コンピュータの中または無線通信デバイスの中のプロセッサ）によって、あるいはデバイス７１０または７４０によって実装されたときに、本明細書で説明される符号語Ｖｍの生成と関連付けられる全ての動作または動作の一部を行うことができる、命令を備える、任意の形態のコンピュータ可読記憶媒体を含むことができる。例えば、記憶デバイス７６０は、図１から図６を参照して上記で説明される、行列Ｈｍ、Ｈｍ１、およびＨｍ２等の行列を生成する、方程式（１）、（２）、および（３）等の方程式を計算する、および追跡記録（例えば、行および列の交換）を生成する命令を含むことができる。記憶デバイス７６０に記憶される命令を行うプロセッサは、システム７００から外部で、システムに含むことができる。例えば、そのようなプロセッサは、システム７００とは異なるコンピュータの一部であり得る。
【００５０】
代替として、または記憶デバイス７６０に加えて、電子ユニット７７０は、図１から図６を参照して上記で説明される、行列Ｈｍ、Ｈｍ１、およびＨｍ２等の行列を生成する、方程式（１）、（２）、および（３）等の方程式を計算する、および追跡記録（例えば、行および列の交換）を生成するように動作することができる。例えば、電子ユニット７７０は、パリティチェック行列Ｈと関連付けられる入力情報を受信してもよい。次いで、入力情報に基づいて、電子ユニット７７０は、行列Ｈｍ、Ｈｍ１、およびＨｍ２、追跡記録、ならびに方程式１、２、および３等の出力情報を生成してもよい。電子ユニット７７０によって生成される情報のうちの少なくともいくらか（例えば、行列Ｈｍ、Ｈｍ１、およびＨｍ２、方程式（１）、（２）、および（３）、ならびに追跡記録に含まれる情報のうちの少なくともいくらか）は、符号語Ｖｍを生成するためにエンコーダ７０１によって使用し、かつ符号語Ｖｍを復号するためにデコーダ７０２によって使用することができる。
【００５１】
システム７００の一部分（例えば、デバイス７１０および７２０）またはシステム７００の全ては、同一の半導体チップの中、同一の集積回路パッケージの中、または同一の回路基板の中に含むことができる。
【００５２】
装置（例えば、装置１００）およびシステム（例えば、システム７００）の説明図は、種々の実施形態の構造の一般的理解を提供することを目的とし、本明細書で説明される構造を利用し得る装置およびシステムの全ての要素および特徴の完全な説明を提供することを目的としていない。
【００５３】
図１から７を参照して上記で説明される構成要素のうちのいずれかは、ソフトウェアを介したシミュレーションを含む、いくつかの方法で実装することができる。したがって、上記で説明される装置（例えば、装置１００）およびシステム（例えば、システム７００）は全て、本明細書では「モジュール」（または「１つのモジュール」）として特徴付けられてもよい。そのようなモジュールは、装置（例えば、装置１００）の設計者による所望に応じて、かつ種々の実施形態の特定の実装のために、適宜、ハードウェア回路、シングルおよび／またはマルチプロセッサ回路、メモリ回路、ソフトウェアプログラムモジュールおよびオブジェクト、および／またはファームウェア、ならびにそれらの組み合わせを含んでもよい。例えば、そのようなモジュールは、ソフトウェア電気信号シミュレーションパッケージ、電力利用および範囲シミュレーションパッケージ、キャパシタンス・インダクタンスシミュレーションパッケージ、電力／熱放散シミュレーションパッケージ、信号伝送・受信シミュレーションパッケージ、および／または種々の潜在的な実施形態の動作を操作またはシミュレートするために使用されるソフトウェアおよびハードウェアの組み合わせ等のシステム動作シミュレーションパッケージに含まれてもよい。
【００５４】
種々の実施形態の装置およびシステムは、高速コンピュータ、通信および信号処理回路、シングルまたはマルチプロセッサモジュール、単一または複数の組み込みプロセッサ、マルチコアプロセッサ、メッセージ情報スイッチ、および多層マルチチップモジュールを含む特定用途向けモジュールで使用される、電子回路を含んでもよく、または電子回路に含まれてもよい。そのような装置およびシステムはさらに、テレビ、携帯電話、パーソナルコンピュータ（例えば、ラップトップコンピュータ、デスクトップコンピュータ、手持ち方程式コンピュータ、タブレットコンピュータ等）、ワークステーション、ラジオ、ビデオプレーヤ、オーディオプレーヤ（例えば、ＭＰ３（Ｍｏｔｉｏｎ  Ｐｉｃｔｕｒｅ  Ｅｘｐｅｒｔｓ  Ｇｒｏｕｐ，Ａｕｄｉｏ  Ｌａｙｅｒ  ３）プレーヤ）、車両、医療デバイス（例えば、心臓モニタ、血圧モニタ等）、セットトップボックス、およびその他等の種々の電子システム内に従属部品として含まれてもよい。
【００５５】
図１から７を参照して上記で説明される実施形態は、メッセージ情報を符号化するための装置および方法を含む。そのような装置および方法は、上三角部分行列を有する第１の行列を生成するために、低密度パリティチェック（ＬＤＰＣ）符号のパリティチェック行列を使用することを含むことができる。メッセージ情報を符号化するパリティ情報は、上三角部分行列の行の総数がパリティチェック行列の階数に等しい場合、第１の行列に基づいて生成することができる。上三角部分行列の行の総数がパリティチェック行列の階数より少ない場合には、第２の行列を生成するように、第１の行列の第２の部分の中の第２の部分行列に三角行列化演算を行うことができる。メッセージ情報を符号化するパリティ情報は、第２の行列に基づいて生成することができる。本明細書で説明される符号化は、符号語を形成するようにパリティ情報およびメッセージ情報を組み合わせることができる。符号語の復号も行うことができる。例えば、パリティ情報を生成するように符号化中に行われるプロセス（例えば、ステップ）は、復号された情報を生成するように、逆の順番で行うことができる。次いで、符号化に使用される同一のＨ行列は、元のメッセージ情報を生成するために、復号中に使用することができる。追加の装置および方法を含む、他の実施形態が説明される。
【００５６】
上記の説明および図面は、当業者が本発明の実施形態を実践することを可能にするように、本発明のいくつかの実施形態を例証する。他の実施形態は、構造、論理、電気、プロセス、および他の変更を組み込んでもよい。実施例は、可能な変形例を類型化するにすぎない。いくつかの実施形態の部分および特徴は、他の実施形態の部分および特徴に含まれ、または代用されてもよい。多くの他の実施形態が、上記の説明を読んで理解することによって、当業者に明白となるであろう。
【図１】
0005913560.tif 000007
【図２】
0005913560.tif 000008
【図３】
0005913560.tif 000009
【図４】
0005913560.tif 000010
【図５】
0005913560.tif 000011
【図６】
0005913560.tif 000012
【図７】
0005913560.tif 000013