(57)【要約】  低密度パリティチェック行列の生成方法及び装置を提供する。本発明は、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する段階と、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する段階と、一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを上下対称的に、水平方向に配列する段階とを含む。
2008516546.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェック行列の生成方法において、
単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する段階と、
単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する段階と、
一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを上下対称的に、水平方向に配列する段階とを含むことを特徴とする方法。
【請求項２】
前記一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、
前記ｐ回目正−シフトブロックの直上部または直下部に前記ｐ回目負−シフトブロックを配列する段階を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、
前記正−シフトブロック及び負−シフトブロックを前記正−シフトブロック及び負−シフトブロックのシフト番号順に配列する段階を含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階をさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階は、
前記正−シフトブロック及び前記負−シフトブロックと同じ大きさの単位行列及び零行列を水平方向及び垂直方向に交互に配列することによって、下部サブ行列を生成する段階と、
前記下部サブ行列を、前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に配列する段階とを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記上部サブ行列及び前記下部サブ行列を交互に配列することによって、規則的パリティチェック行列を生成する段階を含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記規則的パリティチェック行列を生成する段階は、
前記上部サブ行列の直下部に前記下部サブ行列を配列することによって、第１サブ行列を生成する段階と、
前記上部サブ行列の直上部に前記下部サブ行列を配列することによって、第２サブ行列を生成する段階と、
前記第１サブ行列の左側または右側に前記第２サブ行列を配列する段階とを含むことを特徴とする請求項６に記載の方法。
【請求項８】
低密度パリティチェック行列の生成装置において、
単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する正−シフトブロック生成部と、
単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する負−シフトブロック生成部と、
前記ｐ回目正−シフトブロック及び前記ｐ回目負−シフトブロックを上下方向に対称的に配列することによって、上部サブ行列を生成する上部サブ行列生成部とを備えることを特徴とする装置。
【請求項９】
前記上部サブ行列生成部は、
前記ｐ回目正−シフトブロックの直上部または直下部に前記ｐ回目負−シフトブロックを配列することによって、前記上部サブ行列を生成することを特徴とする請求項８に記載の装置。
【請求項１０】
前記上部サブ行列生成部は、
前記正−シフトブロック及び前記負−シフトブロックを水平方向に、前記正−シフトブロック及び前記負−シフトブロックのシフト番号順に配列することによって、前記上部サブ行列を生成することを特徴とする請求項８に記載の装置。
【請求項１１】
前記正−シフトブロック及び負−シフトブロックと同じ大きさの単位行列及び零行列を水平方向及び垂直方向に交互に配列することによって、前記上部サブ行列と同じ大きさの下部サブ行列を生成する下部サブ行列生成部と、
前記上部サブ行列の直下部に前記下部サブ行列を配列することによって、第１サブ行列を生成する第１サブ行列生成部とをさらに備えることを特徴とする請求項８に記載の装置。
【請求項１２】
前記上部サブ行列の直上部に前記下部サブ行列を配列することによって、第２サブ行列を生成する第２サブ行列生成部と、
前記第１サブ行列及び前記第２サブ行列を水平方向に対称的に配列することによって、規則的パリティチェック行列を生成するパリティチェック行列生成部とをさらに備えることを特徴とする請求項１１に記載の装置。
【請求項１３】
低密度パリティチェック行列の生成方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する段階と、
単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する段階と、
一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを上下対称的に、水平方向に配列する段階を含むことを特徴とする記録媒体。
【請求項１４】
前記一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、
前記ｐ回目正−シフトブロックの直上部または直下部に前記ｐ回目負−シフトブロックを配列する段階を含むことを特徴とする請求項１３に記載の記録媒体。
【請求項１５】
前記一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、
前記正−シフトブロック及び負−シフトブロックを前記正−シフトブロック及び負−シフトブロックのシフト番号順に配列する段階を含むことを特徴とする請求項１３に記載の記録媒体。
【請求項１６】
前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階をさらに含むことを特徴とする請求項１３に記載の記録媒体。
【請求項１７】
前記上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階は、
前記正−シフトブロック及び前記負−シフトブロックと同じ大きさの単位行列及び零行列を水平方向及び垂直方向に交互に配列することによって、下部サブ行列を生成する段階と、
前記下部サブ行列を、前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に配列する段階とを含むことを特徴とする請求項１６に記載の記録媒体。
【請求項１８】
前記上部サブ行列及び前記下部サブ行列を交互に配列することによって、規則的パリティチェック行列を生成する段階をさらに含むことを特徴とする請求項１３に記載の記録媒体。
【請求項１９】
規則的パリティチェック行列を生成する段階は、
前記上部サブ行列の直下部に前記下部サブ行列を配列することによって、第１サブ行列を生成する段階と、
前記上部サブ行列の直上部に前記下部サブ行列を配列することによって、第２サブ行列を生成する段階と、
前記第１サブ行列の左側または右側に前記第２サブ行列を配列する段階とを含むことを特徴とする請求項１８に記載の記録媒体。
【請求項２０】
ｐ回目正−シフトブロックまたは負−シフトブロックは、水平方向に現れないことを特徴とする請求項１に記載の方法。
【請求項２１】
ｐ回目正−シフトブロック及びｐ回目負−シフトブロックの対を上下方向に対称的に配列し、前記ｐ回目正−シフトブロック及びｐ回目負−シフトブロック対は、ある対の対応列に“１”と同じ行インデックスを有さないことを特徴とする請求項１に記載の方法。
【請求項２２】
一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、
水平方向にシフト番号が重ならない限り、前記正−シフトブロック及び前記負−シフトブロックをランダムに配列することを特徴とする請求項１に記載の方法。
【請求項２３】
前記上部サブ行列及び前記下部サブ行列のそれぞれは、複数個のサブ−シフトブロックを含み、
前記上部サブ行列の２個のサブシフトブロックの同じ列には、２個の１が同じ列インデックスを有さず、
前記下部サブ行列の２個のサブシフトブロックの同じ列には、２個の１が同じ列インデックスを有することを特徴とする請求項５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティチェック行列の生成方法に係り、さらに詳細には、サイクル４現象を防止し、さらに簡単にパリティチェック行列を生成する方法に関する。
【背景技術】
【０００２】
図１Ａは、低密度パリティチェックコーディング及びデコーディング方法の概念を示す図である。
【０００３】
エラー訂正のための付加情報の生成方法において、低密度パリティチェック（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ：ＬＤＰＣ）コーディング方法が広く使われている。低密度パリティチェックコーディングとは、‘０’と‘１’から構成され、‘１’の数が‘０’の数よりはるかに少ない低密度パリティチェック行列Ｈを利用してパリティ情報を生成する方法である。
【０００４】
パリティチェック行列で、各行または列に含まれた１の個数は、それぞれ行次数及び列次数という。あらゆる行の行次数が同一であり、あらゆる列の列次数が同一であるパリティチェック行列を規則的パリティチェック行列といい、そうでない場合を不規則的パリティチェック行列という。規則的パリティチェック行列において行次数は、行ウェイト（ｒｏｗ  ｗｅｉｇｈｔ：Ｗｒ）といい、列次数は、列ウェイト（ｃｏｌｕｍｎ  ｗｅｉｇｈｔ：Ｗｃ）という。
【０００５】
ＬＤＰＣコーディングを利用したパリティ情報の生成は、以下の式（１）により行われる。
【０００６】
ＨＸ＝０        （１）
ここで、Ｈは、ｍ＊Ｎのパリティチェック行列であり、Ｘは、ｎ＊１のコードワード行列である。Ｘは、ｍ個のメッセージ情報とｐ個のパリティ情報とから構成される。したがって、ｍ＋ｐ＝ｎである。
【０００７】
このようなＬＤＰＣコーディングの基本概念は、Ｄ.Ｊ.ＭａｃＫａｙ，“Ｇｏｏｄ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｏｎ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ，”ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ.４５，ｎｏ.２，ｐｐ.３９９〜４３１，１９９９に開示されており、この文献によれば、パリティ情報は、ガウス消去法などの行列演算を利用して式（１）を解くことによって生成されうる。
【０００８】
また、低密度パリティチェックデコーディングは、前記数式に基づいてパリティ検算を行う過程を含む。
【０００９】
既存のＬＤＰＣコードのパリティチェック行列を構成する方法は、大きく２つに分けられる。第１の方法は、パリティチェック行列Ｈのそれぞれの列に対して、要素１行インデックスをユーザーにより定められた任意の規則によって選択する方法である。例えば、第１列には１、３、５の行インデックスを、第２列には２、４、６の行インデックスを、第３列には７、９、１１の行インデックスを、．．．、要素１要素と選択する方法である。この方法は、具現が容易であるが、ＢＥＲ（Ｂｉｔ  Ｅｒｒｏｒ  Ｒａｔｅ）性能が低下する。第２の方法は、パリティチェック行列Ｈのそれぞれの列に対して、要素１行インデックスをランダムに選択する方法である。この方法は、１の位置がランダムであるため、具現が複雑であるが、ＢＥＲ性能に優れている。
【００１０】
第２の方法でパリティチェック行列を生成する一例は、次の通りである。まず、第１列で任意のｗｃ個の要素１行インデックスを選択する。その後、第２列で、既に生成された第１列の要素１行インデックスと二つ以上は重ならないように、任意の要素１行インデックスを選択する。その後、第３列で、既に生成された第１列及び第２列のうち、いずれか一つの要素１行インデックスと二つ以上は重ならないように、任意の要素１行インデックスを選択する。最後に、前記過程を最後の列まで繰り返す。
【００１１】
すなわち、従来のパリティチェック行列の生成方法は、パリティチェック行列Ｈ内のあらゆる任意の二列の要素１行インデックスのうち、二つ以上は重ならないように任意の要素１行インデックスを選択する。
【００１２】
前記のいずれの方法を選択しても、サイクル４現象が発生することを防止するように、パリティチェック行列の要素１の位置が選択されなければならない。
【００１３】
図１Ｂは、サイクル４現象を発生させるパリティチェック行列を示す図である。サイクル４現象は、パリティチェック行列に含まれた要素１が特定位置の関係にあるときに現れる、デコーディングのＢＥＲ性能の低下現象である。このとき、特定位置とは、要素１がパリティチェック行列内で直四角形の４つの角に対応する位置をいう。例えば、（２，２）、（２，８）、（４，８）、（４，２）の位置に１が存在する場合である。
【００１４】
しかし、現在サイクル４現象を防止するための一般的なアルゴリズムは存在しておらず、前記の方法で低密度パリティチェック行列を構成するときも、これを考慮して１の位置を選択しなければならない不便さが存在する。
【００１５】
また、パリティチェック行列をメモリに保存する場合は、要素１の行インデックスをメモリに保存するが、一般的にパリティチェック行列は、その大きさが非常に大きいので、要素１行インデックスを保存するためには非常に大きいメモリを必要とする。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、前記課題を解決するために案出されたものであって、サイクル４現象を防止し、かつさらに簡単にパリティチェック行列を生成する方法を提供することを目的とする。
【００１７】
また、本発明は、パリティチェック行列が占めるメモリの容量を減少させたパリティチェック行列の生成方法を提供することを目的とする。
【課題を解決するための手段】
【００１８】
本発明によれば、低密度パリティチェック行列の生成方法において、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する段階と、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する段階と、一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを上下対称的に、水平方向に配列する段階とを含む。
【００１９】
ここで、前記一つ以上の前記ｐ回目正−シフトブロック及び一つ以上の前記ｐ回目負−シフトブロックを、水平方向に配列する段階は、前記ｐ回目正−シフトブロックの直上部または直下部に前記ｐ回目負−シフトブロックを配列する段階を含むことを特徴とする。
【００２０】
また、ここで、前記正−シフトブロック及び前記負−シフトブロックを水平方向にシフト番号順に配列する段階を含むことを特徴とする。
【００２１】
また、本発明は、前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階をさらに含むことを特徴とする。ここで、前記上部サブ行列の直上部または直下部に、単位行列及び零行列を交互に配列する段階は、前記正−シフトブロック及び前記負−シフトブロックと同じ大きさの単位行列及び零行列を水平方向及び垂直方向に交互に配列することによって、下部サブ行列を生成する段階と、前記下部サブ行列を、前記正−シフトブロック及び前記負−シフトブロックを上下方向に対称的に配列することによって生成された上部サブ行列の直上部または直下部に配列する段階とを含む。
【００２２】
また、本発明は、低密度パリティチェック行列の生成装置において、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する正−シフトブロック生成部と、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する負−シフトブロック生成部と、前記ｐ回目正−シフトブロック及び前記ｐ回目負−シフトブロックを上下方向に対称的に配列することによって、上部サブ行列を生成する上部サブ行列生成部とを備えることを特徴とする。
【発明の効果】
【００２３】
本発明によれば、サイクル４現象を防止し、かつさらに簡単にパリティチェック行列を生成する方法が提供される。
【００２４】
また、本発明によれば、パリティチェック行列が占めるメモリの容量が減少する。
【発明を実施するための最良の形態】
【００２５】
以下、添付された図面を参照して本発明による望ましい一実施形態を詳細に説明する。
【００２６】
図２は、本発明の第１実施形態によって生成されたパリティチェック行列を示す図である。
【００２７】
本発明のあらゆる実施形態で、パリティチェック行列は、一つ以上のシフトブロックから構成される。シフトブロックは、正−シフトブロックと負−シフトブロックとに分けられる。ｐ回目正−シフトブロックは、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって生成された行列を意味し、ｐ回目負−シフトブロックは、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって生成された行列を意味する。
【００２８】
図２に示すように、本発明の第１実施形態では、パリティチェック行列の上部半分及び下部半分に、ｐ回目正−シフトブロック及び負−シフトブロックが上下方向に対称的に存在する。ｐ回目正−シフトブロックが上部に位置する場合には、ｐ回目負−シフトブロックがその直下部に位置し、ｐ回目負−シフトブロックが上部に位置する場合には、ｐ回目正−シフトブロックがその直下部に位置する。また、ｐ回目正−シフトブロックまたは負−シフトブロックは、重複して現れない。
【００２９】
サイクル４現象を防止するための本発明でのパリティチェック行列を構成するための２つの規則は、次の通りである。
【００３０】
規則１）ｐ回目正−シフトブロック及びそれに対応するｐ回目負−シフトブロックが、上下方向に対称的に配列される。
【００３１】
規則２）ｐ回目正−シフトブロックまたは負−シフトブロックは水平方向に重複して現れない。
【００３２】
ｍ＊Ｎのパリティチェック行列を構成するためのサブブロックの大きさは、ｍ／２＊ｍ／２である。したがって、ｎ＝ｍ／２＊Ｎの関係を有し、ｍ＊Ｎパリティチェック行列一つを構成するのに必要なブロックの個数は、２Ｎ（Ｎ個の正−シフトブロック及びＮ個の負−シフトブロック）である。
【００３３】
図２のように構成されたパリティチェック行列は、少ないメモリを必要とする。これは、従来の方法のように各列ごとに要素１行インデックスを保存する代わりに、正または負シフトブロックのシフト番号、すなわちｐのみを保存すれば済むためである。例えば、図２の実施形態で、パリティチェック行列内のシフト番号、すなわちａ、ｂ、．．．（左側から）のみを保存すれば、パリティチェック行列を構成することが可能である。正−シフトまたは負−シフトブロックの内部構造は、シフト番号によって特定され、パリティチェック行列は、シフト番号の配列順序によって特定可能であるためである。
【００３４】
以下で、ｐ回目正−シフトブロックは、Ｓ＋ｐと表記し、ｐ回目負−シフトブロックは、Ｓ−ｐと表記する。
【００３５】
図３は、図２のように構成されたパリティチェック行列でサイクル４現象が防止される理由を示す図である。図３で、パリティチェック行列は、Ｓ＋１、Ｓ−１、Ｓ＋３、Ｓ−３の４個のシフトブロックを含む。
【００３６】
まず、上部に存在するサブブロックＳ＋１、Ｓ＋２、Ｓ＋３、．．内で２つの頂点を選択し、下部に存在するサブブロックＳ−１、Ｓ−２、Ｓ−３、．．内で残りの２頂点を選択する場合を説明する。ここで、頂点はサイクル４現象を発生させる直四角形の４個の角をいう。
【００３７】
シフトブロックは、単位行列のあらゆる構成要素が右または左にシフトされた行列であり、単位行列は、水平方向または垂直方向のどの方向でも要素１が一つしか存在しないので、シフトブロック内のあらゆる行に含まれた要素１の個数（ｒｏｗ  ｗｅｉｇｈｔ）及びシフトブロック内のあらゆる列に含まれた要素１の個数（ｃｏｌｕｍｎ  ｗｅｉｇｈｔ）は、いずれも１である。したがって、シフトブロック内で任意の要素１が選択されれば、その要素１を含む列または行には、他の要素１が存在しない。
【００３８】
本発明のパリティチェック行列は、垂直方向において、ｐ回目正−シフトブロックの上部または下部には、それに対応するｐ回目負−シフトブロックが存在するので、上下方向に対応するシフトブロック間には、要素１の行インデックスが重ならない。例えば、図３でシフトブロックＳ＋１内の要素１  ３０１と同じ列に存在する、シフトブロックＳ−１内の要素１  ３０２の行インデックスは、４であって、シフトブロックＳ＋１の要素１  ３０１の行インデックスの２と異なる。また、同様に要素１  ３０３と要素１  ３０４との行インデックスは、互いに異なる。
【００３９】
また、本発明のパリティチェック行列は、水平方向において、ｐ回目正−シフトブロックまたは負−シフトブロックの左右方向には、それに対応するｐ＋Ｎ番目（ここで、Ｎは整数）正−シフトブロックまたは負−シフトブロックが存在するので、結局、左右方向に対応するシフトブロックの間には要素１の列インデックスが重ならない。例えば、図３でシフトブロックＳ＋１内の要素１  ３０１と同じ行に存在する、シフトブロックＳ＋３内の要素１  ３０３の列インデックスは、５であって、シフトブロックＳ＋１の要素１  ３０１の列インデックスの３と異なる。また、同様に要素１  ３０５と要素１  ３０４との列インデックスは、互いに異なる。
【００４０】
前記の２つの特性によって、結局、本発明によって生成されたパリティチェック行列内の任意の直四角形の頂点に対応する４個の位置に、要素１が全て存在する場合は存在できない。すなわち、４個の頂点のうちいずれか一つは、必ず要素０となる。結局、本発明によって生成されたパリティチェック行列は、サイクル４現象が発生しない。
【００４１】
次の場合として、サブブロック内で２個の要素１を頂点として選択する場合を説明する、一つのシフトブロックに含まれた要素１は、水平方向に列インデックスが重ならず、縦方向には行インデックスが重ならないため、４個の要素１がそれぞれの角となる直四角形は生成されない。
【００４２】
図４は、図２の実施形態によるパリティチェック行列の生成方法を示す時間フローチャートである。
【００４３】
段階４１０で、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する。
【００４４】
段階４２０で、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する。
【００４５】
段階４３０で、ｐ回目正−シフトブロック及びｐ回目負−シフトブロックを上下方向に対称的に配列することによって、低密度パリティチェック行列を生成する。このとき、正−シフトブロックが上部に置かれる場合には、あらゆる正−シフトブロックが上部に位置しなければならず、負−シフトブロックが上部に置かれる場合には、あらゆる負−シフトブロックが上部に位置しなければならない。
【００４６】
変形された実施形態で、シフトブロックは、シフト番号ｐが並べられるように、シフトブロックが配列されることも可能である。この場合には、メモリ容量が追加的に減少する。この実施形態は、図５で説明する。
【００４７】
図５は、本発明の第２実施形態によって生成されたパリティチェック行列を示す図である。図５の実施形態のパリティチェック行列は、シフト番号が規則的の特徴を有する。すなわち、左側から右側方向に
Ｓ＋１、Ｓ＋２、Ｓ＋３、．．の順にシフトブロックが配列される。これにより、パリティチェック行列を保存するためのメモリがさらに減少する。メモリは、全体シフトブロックの個数Ｎのみ保存すればよいためである。図５には、正シフトブロックが上部に存在するが、変形された実施形態で正−シフトシフトブロックと負−シフトブロックとの位置は、置き換えられてもよい。
【００４８】
以下の全ての実施形態で、シフトブロックは、シフト番号順に配列して表記する。しかし、変形された実施形態で、シフトブロックは、水平方向にシフト番号が重ならない限り、ランダムに配列可能である。
【００４９】
図６は、本発明の第３実施形態によって生成されたパリティチェック行列を示す図である。図６に示すように、図６の実施形態によるパリティチェック行列は、図２のパリティチェック行列の下部に図２のパリティチェック行列と同じ大きさの下部サブ行列６００が追加される。下部サブ行列６００は、上部サブ行列６１０を構成するシフトブロックＳ＋１、Ｓ＋２、．．
Ｓ−１、Ｓ−２、．．と大きさが同じ一つ以上の単位行列Ｉ及び零行列０から構成され、単位行列Ｉ及び零行列０は、水平方向及び垂直方向に交互に配列される。
【００５０】
図６のパリティチェック行列は、行ウェイトが３である。しかし、列ウェイトは一定でない。
【００５１】
図７は、図６のパリティチェック行列でサイクル４現象が防止される理由を示す図である。
【００５２】
まず、上部サブ行列６１０で２つの頂点を選択し、下部サブ行列６００で２つの頂点を選択する場合を説明する。ここで、頂点は、サイクル４現象を発生させる直四角形の４個の角をいう。
【００５３】
図２の場合と同様に、図６のパリティチェック行列は、まず、上部に存在するシフトブロックの水平方向において、ｐ回目正−シフトブロックまたは負−シフトブロックの左右方向には、それに対応するｐ＋Ｎ番目（ここで、Ｎは整数）正−シフトブロックまたは負−シフトブロックが存在するので、結局、左右方向に対応するシフトブロックの間には、要素１の列インデックスが重ならない。例えば、図３でシフトブロックＳ＋１内の要素１  ３０１と同じ行に存在する、シフトブロックＳ＋３内の要素１  ７０２の列インデックスは、５であって、シフトブロックＳ＋１の要素１  ３０１の列インデックスの３と異なる。
【００５４】
また、下部に存在するシフトブロックの水平方向において、下部のシフトブロックが単位行列であるので、左右方向に対応するシフトブロック間には、要素１の列インデックスが重複されうる。しかし、前述したように、上部サブブロック６００内の要素１間には、同じ列インデックスを有することができないので、単位行列内で列インデックスが同一である２つの要素１に対応する上部サブブロック内の位置に、２つの要素１がいずれも存在することはできない。例えば、図７で、単位行列内の要素１  ７０３と要素１  ７０４とは、互いに列インデックスが３と同一であるが、上部サブ行列６１０内で要素１  ７０４の列インデックスに対応する位置７０５には、要素１が存在していないため、結局サイクル４現象が発生しない。
【００５５】
次の場合として、上部サブ行列６１０内または下部サブ行列６００内で４個の要素１をいずれも選択する場合には、単位行列またはシフトブロックに含まれた要素１は、１０インデックス及び行インデックスが重ならないため、４個の要素１がそれぞれの角となる直四角形は生成されない。
【００５６】
図８は、図６のパリティチェック行列を生成する方法を示す時間フローチャートである。
【００５７】
段階８１０で、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する。
【００５８】
段階８２０で、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する。
【００５９】
段階８３０で、ｐ回目正−シフトブロック及びｐ回目負−シフトブロックを上下方向に対称的に配列することによって、上部サブ行列６１０を生成する。
【００６０】
段階８４０で、上部サブ行列６１０を構成するシフトブロックと同じ大きさを有する単位行列Ｉ及び零行列０を水平方向及び垂直方向に交互に配列することによって、下部サブ行列６００を生成する。
【００６１】
段階８５０で、上部サブ行列６１０直下部または直上部に下部サブ行列６００を配列することによって、パリティチェック行列を生成する。
【００６２】
図９は、本発明の第４実施形態によって生成されたパリティチェック行列を示す図である。図９のパリティチェック行列は、第１サブ行列９２０と第２サブ行列９３０とを含む。第１サブ行列９２０は、上部サブ行列９１０の直下部に下部サブ行列９００が位置する行列であり、第２サブ行列９３０は、上部サブ行列９１０の直上部に下部サブ行列９００が位置する行列である。
【００６３】
図９のパリティチェック行列は、次のような２つの特徴を有する。
【００６４】
第１に、列ウェイト及び行ウェイトが一定の規則的パリティチェック行列である。
【００６５】
第２に、列ウェイトは３であり、行ウェイトは、Ｎ／２＋（Ｎ／２＊１／２）＝３Ｎ／４である。ここで、Ｎは、水平方向のシフトブロックの個数＋単位行列の個数＋零行列の個数である。
【００６６】
図１０は、図９のパリティチェック行列を生成する方法を示す時間フローチャートである。段階１０１０で、単位行列のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロックを生成する。
【００６７】
段階１０２０で、単位行列のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロックを生成する。
【００６８】
段階１０３０で、ｐ回目正−シフトブロック及びｐ回目負−シフトブロックを上下方向に対称的に配列することによって、上部サブ行列９１０を生成する。
【００６９】
段階１０４０で、上部サブ行列９１０を構成するシフトブロックと同じ大きさを有する単位行列Ｉ及び零行列０を水平方向及び垂直方向に交互に配列することによって、下部サブ行列９００を生成する。
【００７０】
段階１０５０で、上部サブ行列９１０直下部に下部サブ行列９００を配列することによって、第１サブ行列９２０を生成し、上部サブ行列９１０直上部に下部サブ行列９００を配列することによって、第２サブ行列９３０を生成する。
【００７１】
段階１０６０で、第１サブ行列９００の左側または右側に第２サブ行列９１０を配列することによって、パリティチェック行列を生成する。
【００７２】
図１１は、本発明によるパリティチェック行列の生成装置を示す図である。
【００７３】
本発明によるパリティチェック行列の生成装置は、正−シフトブロック生成部１１１０、負−シフトブロック生成部１１２０、上部サブ行列生成部１１３０、下部サブ行列生成部１１４０、第１サブ行列生成部１１５０、第２サブ行列生成部１１６０、及びパリティチェック行列生成部１１７０を備える。
【００７４】
正−シフトブロック生成部１１１０は、単位行列１１０２のあらゆる構成要素を右にｐ回シフトさせることによって、ｐ回目正−シフトブロック１１１２を生成し、負−シフトブロック生成部１１２０は、単位行列１１０２のあらゆる構成要素を左にｐ回シフトさせることによって、ｐ回目負−シフトブロック１１２２を生成する。
【００７５】
上部サブ行列生成部１１３０は、ｐ回目正−シフトブロック１１１２及びｐ回目負−シフトブロック１１２２を上下方向に対称的に配列することによって、上部サブ行列１１３２を生成する。特に、上部サブ行列生成部１１３０は、ｐ回目正−シフトブロック１１１２の直上部または直下部にｐ回目負−シフトブロックを配列することによって、上部サブ行列１１３２を生成する。
【００７６】
上部サブ行列１１３２は、それ自体としてパリティチェック行列として使用可能である。このとき、上部サブ行列生成部１１３０は、正−シフトブロック１１１２及び負−シフトブロック１１２２を水平方向にシフト番号順に配列することによって、上部サブ行列１１３２を生成でき、この場合、パリティチェック行列が占めるメモリ容量がさらに減少する。
【００７７】
下部サブ行列生成部１１４０は、正−シフトブロック１１１２及び負−シフトブロック１１２２と同じ大きさの単位行列１１０２及び零行列を水平方向及び垂直方向に交互に配列することによって、上部サブ行列１１３２と同じ大きさの下部サブ行列１１４２を生成する。
【００７８】
第１サブ行列生成部１１５０は、上部サブ行列１１３２の直下部に前記下部サブ行列１１４２を配列することによって、第１サブ行列１１５２を生成し、第２サブ行列生成部１１６０は、上部サブ行列１１３２の直上部に下部サブ行列１１４２を配列することによって、第２サブ行列１１６２を生成する。第１サブ行列１１５２及び第２サブ行列１１６２は、その自体としてパリティチェック行列として使用可能である。
【００７９】
パリティチェック行列生成部１１７０は、第１サブ行列１１５２及び第２サブ行列１１６２を水平方向に対称的に配列することによって、規則的パリティチェック行列１１７２を生成する。
【００８０】
本発明によれば、サイクル４現象を防止し、かつさらに簡単にパリティチェック行列を生成する方法が提供される。また、本発明によれば、パリティチェック行列が占めるメモリの容量が減少する。
【００８１】
一方、本発明に係るパリティチェック行列の生成方法は、コンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現されうる。前記プログラムを具現するコード及びコードセグメントは、当該分野のコンピュータプログラマーによって容易に推論されうる。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取られるデータが保存される全ての種類の記録装置を含む。コンピュータで読み取り可能な記録媒体の例としては、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光ディスクなどがあり、またキャリアウェーブ（例えば、インターネットを介した伝送）形態に具現されるものを含む。また、コンピュータで読み取り可能な記録媒体は、ネットワークに連結されたコンピュータシステムに分散され、分散方式でコンピュータで読み取り可能なコードとして保存されかつ実行されうる。
【００８２】
以上の説明は、本発明の一実施形態に過ぎず、当業者は、本発明の本質的特性から外れない範囲で変形された形態で具現できるであろう。従って、本発明の範囲は、前記実施形態に限定されずに、特許請求範囲に記載された内容と同等な範囲内にある多様な実施形態が含まれると解釈されねばならない。
【図面の簡単な説明】
【００８３】
【図１Ａ】低密度パリティチェックコーディング及びデコーディング方法の概念を示す図である。
【図１Ｂ】サイクル４現象を発生させるパリティチェック行列を示す図である。
【図２】本発明の第１実施形態によって生成されたパリティチェック行列を示す図である。
【図３】図２のように構成されたパリティチェック行列でサイクル４現象が防止される理由を示す図である。
【図４】図２の実施形態によるパリティチェック行列の生成方法を示す時間フローチャートである。
【図５】本発明の第２実施形態によって生成されたパリティチェック行列を示す図である。
【図６】本発明の第３実施形態によって生成されたパリティチェック行列を示す図である。
【図７】図６のパリティチェック行列でサイクル４現象が防止される理由を示す図である。
【図８】図６のパリティチェック行列を生成する方法を示す時間フローチャートである。
【図９】本発明の第４実施形態によって生成されたパリティチェック行列を示す図である。
【図１０】図９のパリティチェック行列を生成する方法を示す時間フローチャートである。
【図１１】本発明によるパリティチェック行列の生成装置を示す図である。
【図１Ａ】
2008516546.tif 000003
【図１Ｂ】
2008516546.tif 000004
【図２】
2008516546.tif 000005
【図３】
2008516546.tif 000006
【図４】
2008516546.tif 000007
【図５】
2008516546.tif 000008
【図６】
2008516546.tif 000009
【図７】
2008516546.tif 000010
【図８】
2008516546.tif 000011
【図９】
2008516546.tif 000012
【図１０】
2008516546.tif 000013
【図１１】
2008516546.tif 000014
【国際調査報告】
2008516546.tif 000015
2008516546.tif 000016