(57)【要約】  パリティビットを生成するにあたり、逆行列演算が必要なくてして全行列領域で逆代入が可能であるブロック単位のパリティチェック行列生成方法及び装置とその記録媒体と係り、該方法は、垂直方向に低密度パリティチェック行列を分割し、第１パリティビットベクトルの長さを基とする第１領域と、第２パリティビットベクトルの長さを基とする第２領域とを形成する段階と、第２領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する段階と、二重対角線行列の位置を基に水平方向に前記第１領域を第３領域及び第４領域に分割し、第２領域を第５領域及び第６領域に分割する段階と、列ウェートが同じである条件を満足するように、第３領域、第４領域、第５領域及び第６領域に含まれるブロック単位行列を生成する段階とを含む。
2008536437.tif 000002
【特許請求の範囲】
【請求項１】
ブロック単位の低密度パリティチェック行列の生成方法において、
垂直方向に前記低密度パリティチェック行列を分割し、第１パリティビットベクトルの長さを基とする第１領域と、第２パリティビットベクトルの長さを基とする第２領域とを形成する段階と、
前記第２領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する段階と、
前記二重対角線行列の位置を基に水平方向に前記第１領域を第３領域及び第４領域に分割し、前記第２領域を第５領域及び第６領域に分割する段階と、
列ウェートが同じである条件を満足するように、前記第３領域、第４領域、第５領域及び第６領域に含まれるブロック単位行列を生成する段階とを含むことを特徴とするブロック単位の低密度パリティチェック行列の生成方法。
【請求項２】
前記二重対角線行列を有するブロック単位の行列を生成する段階は、単位行列ブロックを利用して前記二重対角線行列が配置されるように、前記ブロック単位の行列が生成されることを特徴とする請求項１に記載の方法。
【請求項３】
前記二重対角線行列を有するブロック単位の行列を生成する段階は、
前記二重対角線行列の上位に単位行列ブロックが配置されるように、前記ブロック単位の行列を生成する段階と、
前記二重対角線行列の下位にシフト行列ブロックが配置されるように、前記ブロック単位の行列を生成する段階とを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記第３領域、第４領域、第５領域及び第６領域に含まれるブロック単位行列を生成する段階は、
前記第２領域の上部以外の前記低密度パリティチェック行列の残りの領域でブロック単位のサイクル４現象が防止されるように、単位行列ブロック、シフト行列ブロック及びゼロ行列ブロックの位置を決定する段階と、
前記決定された位置を基に前記ブロック単位の行列を生成する段階とをさらに含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記第３領域、第４領域、第５領域及び第６領域に含まれたブロック単位行列を生成する段階は、
前記第３領域及び第４領域でリチャードソン行列（φ）が単位行列になる条件を満足するように、前記単位行列ブロック、前記シフト行列ブロック及び前記ゼロ行列ブロックの位置を決定する段階をさらに含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記垂直方向に前記低密度パリティチェック行列を分割する段階は、メッセージデータベクトルに対応する他の領域を形成する段階を含み、
前記第３領域、第４領域、第５領域及び第６領域に含まれるブロック単位行列を生成する段階は、
第１単位行列ブロックが第２領域の下部の最右側列に配置され、最右側列を除外した第２領域の下部の残り領域に第２単位行列ブロックと第１シフト行列ブロックのうち一つと第１ゼロ行列ブロックとが垂直方向及び水平方向に交互に配置されるように、ブロック単位行列を生成する段階と、
第３単位行列ブロック及び第２シフト行列ブロックが前記第１領域の上部領域の最上ブロック単位行に水平に交互に配置され、第３シフト行列ブロックが前記第２シフト行列ブロックのうち一つを含む列の所定位置に配置されるように、前記ブロック単位行列を生成する段階と、
前記第４単位行列ブロックが前記第１領域の下部の最下行に配置され、第４シフト行列ブロックが前記最下行にある最右ブロックの真上に配置されるように、前記ブロック単位行列を生成する段階とを含み、
前記方法は、前記他の領域でサイクル４現象を防止するために、生成された行列ブロックのタイプをチェックしつつブロック単位行列を生成する段階をさらに含むことを特徴とする請求項１に記載の方法。
【請求項７】
前記各シフト行列ブロックは、＋ｐ番目のシフト行列ブロックと−ｐ番目のシフト行列ブロックのうち一つであり、前記ｐは整数であることを特徴とする請求項６に記載の方法。
【請求項８】
前記ｐは、１の値を有することを特徴とする請求項７に記載の方法。
【請求項９】
前記各第１シフト行列ブロックは、＋ｐ番目のシフト行列ブロックであり、前記各第２及び第３シフト行列ブロックは、−ｐ番目のシフト行列ブロックであり、前記各第４シフト行列ブロックは、＋ｐ番目のシフト行列ブロックであることを特徴とする請求項６に記載の方法。
【請求項１０】
前記他の領域でサイクル４現象を防止するために、生成された行列ブロックのタイプをチェックしつつブロック単位行列を生成する段階は、
前記第２領域の上部以外の前記低密度パリティチェック行列の残り領域でブロック単位のサイクル４現象が防止されるように、単位行列ブロック、シフト行列ブロック及びゼロ行列ブロックの位置を決定する段階と、
前記決定された位置を基に前記ブロック単位の行列を生成する段階とをさらに含むことを特徴とする請求項６に記載の方法。
【請求項１１】
ブロック単位の低密度パリティチェック行列の生成装置において、
第１パリティビットベクトル及び第２パリティビットベクトルの長さを基に垂直方向に前記低密度パリティチェック行列の領域を分割する第１領域分割部と、
前記低密度パリティチェック行列の分割された領域のうち、前記第２パリティビットベクトルに対応する領域の上部位置に二重対角線行列が配置されるように、ブロック単位の行列を生成する二重対角線行列ブロック生成部と、
前記二重対角線行列ブロック生成部により生成された二重対角線行列の位置を基に水平方向に前記低密度パリティチェック行列領域を分割する第２領域分割部と、
前記低密度パリティチェック行列のブロック単位の列ウェートが同一になるように、前記低密度パリティチェック行列の垂直方向及び水平方向に分割された領域に含まれるブロック単位行列を生成するブロック単位行列生成部とを備えることを特徴とするブロック単位の低密度パリティチェック行列の生成装置。
【請求項１２】
前記二重対角線行列ブロック生成部は、
単位行列ブロックを利用して前記二重対角線行列が配置されるように、前記ブロック単位の行列を生成することを特徴とする請求項１１に記載の装置。
【請求項１３】
前記二重対角線行列ブロック生成部は、
前記二重対角線行列のうち上部に単位行列ブロックが配置され、前記二重対角線行列のうち下部にシフト行列ブロックが配置されるように、ブロック単位の行列を生成することを特徴とする請求項１１に記載の装置。
【請求項１４】
前記ブロック単位行列生成部は、前記分割された領域のうち前記第１パリティビットベクトルと第２パリティビットベクトルとに対応する領域でブロック単位のサイクル４現象が防止され、リチャードソン行列（φ）が単位行列になるように、既設定のブロック単位行列タイプ情報と位置情報とを基にブロック単位の行列を生成することを特徴とする請求項１３に記載の装置。
【請求項１５】
前記ブロック単位行列生成部は、前記分割された領域のうちメッセージデータベクトルに対応する領域で前記ブロック単位のサイクル４現象を防止するために、前記分割された領域で既生成の行列ブロックのタイプをチェックしつつブロック単位の行列を生成することを特徴とする請求項１４に記載の装置。
【請求項１６】
前記ブロック単位行列生成部は、前記分割された領域のうち前記第１パリティビットベクトルと第２パリティビットベクトルとに対応する領域でブロック単位のサイクル４現象が防止され、リチャードソン行列（φ）が単位行列になるように、既設定のブロック単位行列タイプ情報と位置情報とを基にブロック単位の行列を生成することを特徴とする請求項１２に記載の装置。
【請求項１７】
ブロック単位の低密度パリティチェック行列の生成方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、
前記方法は、
第１パリティビットベクトルと第２パリティビットベクトルとの長さを基に垂直方向に前記低密度パリティチェック行列の領域を分割する段階と、
前記分割された領域のうち前記第２パリティビットベクトルに対応する領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する段階と、
前記二重対角線行列を基に水平方向に前記低密度パリティチェック行列の領域を分割する段階と、
前記低密度パリティチェック行列のブロック単位の列ウェートが同一になるように、前記低密度パリティチェック行列の垂直方向及び水平方向に分割された領域に含まれるブロック単位行列を生成する段階とを含むことを特徴とするコンピュータで読み取り可能な記録媒体。
【請求項１８】
前記二重対角線行列を有するブロック単位の行列を生成する段階は、単位行列ブロックを利用して前記二重対角線行列が配置されるように、前記ブロック単位行列を生成することを特徴とする請求項１７に記載のコンピュータで読み取り可能な記録媒体。
【請求項１９】
前記二重対角線行列を有するブロック単位の行列を生成する段階は、
前記二重対角線行列の上位に単位行列ブロックが配置されるように、前記ブロック単位の行列を生成する段階と、
前記二重対角線行列の下位にシフト行列ブロックが配置されるように、前記ブロック単位の行列を生成する段階とを含むことを特徴とする請求項１７に記載のコンピュータで読み取り可能な記録媒体。
【請求項２０】
前記第３領域、第４領域、第５領域及び第６領域に含まれるブロック単位行列を生成する段階は、
前記第２領域の上部以外の前記低密度パリティチェック行列の残り領域でブロック単位のサイクル４現象が防止されるように、単位行列ブロック、シフト行列ブロック及びゼロ行列ブロックの位置を決定する段階と、
前記決定された位置を基に前記ブロック単位の行列を生成する段階とをさらに含むことを特徴とする請求項１９に記載のコンピュータで読み取り可能な記録媒体。
【請求項２１】
前記方法は、逆行列を計算せずに逆代入によりパリティビットを得る段階をさらに含むことを特徴とする請求項１０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パリティチェック行列の生成方法及び装置に係り、さらに詳細には、パリティビット生成を容易にするブロック単位の低密度パリティチェック行列を生成する方法及び装置に関する。
【背景技術】
【０００２】
エラー訂正のための付加情報を生成するために、低密度パリティチェック（ＬＤＰＣ：Low  Density  Parity  Check）コーディング方法が広く使われている。ＬＤＰＣコーディングとは、「０」と「１」とから構成され、「１」の数が「０」の数よりはるかに少ないＬＤＰＣ行列Ｈを利用してパリティビットを生成する方法である。
【０００３】
パリティチェック行列で、各行（row）または列（column）に含まれた１の数は、それぞれ行次数（row  degree）及び列次数（column  degree）という。あらゆる行の行次数が同一であるか、またはあらゆる列の列次数が同じであるパリティチェック行列を規則的（regular）パリティチェック行列といい、そうでない場合を不規則的（irregular）パリティチェック行列という。規則的パリティチェック行列で行次数は、行ウェート（Ｗｒ：row  weight）といい、列次数は、列ウェート（Ｗｃ：column  weight）という。
【０００４】
ＬＤＰＣコーディングを利用したパリティビット生成は、式（１）により行われる。
【０００５】
【数１】
2008536437.tif 000003
式（１）で、Ｈはｍ＊ｎパリティチェック行列であり、Ｘはｎ＊１のコードワード行列である。Ｘは、（ｎ−ｍ）長さのメッセージデータベクトルＳと、ｍ長さのパリティビットベクトルＰとから構成される。従って、（メッセージデータベクトルＳの長さ（ｎ−ｍ））＋（パリティビットベクトルＰの長さ（ｍ））＝ｎになる。
【０００６】
かようなＬＤＰＣコーディングの概念は、D.J.MacKay、“Good  error-correction  codes  based  on  very  sparse  matrices”,IEEE  Trans.On  Information  Theory,vol.45,no.2,pp.399-431,1999に開示されており、ＭａｃＫａｙによれば、パリティビットは、ガウス消去法などの行列演算を利用して式（１）を解いて生成されるとのことである。しかし、ＬＤＰＣコーディングの場合、コードの長さが長く、パリティチェック行列Ｈの大きさが非常に大きいために、ガウス消去法などを利用したエンコーディングは、計算過程が非常に複雑である。
【０００７】
これを解決するために、パリティチェック行列を他のフォーマットに変換する効率的なコーディング方法（以下、リチャードソンの方法とする）がリチャードソン（T.J.Richardson）により開発された。図１は、リチャードソンの方法により変換されたパリティチェック行列のフォーマットを表した図である。
【０００８】
リチャードソンの方法によれば、パリティチェック行列Ｈを行交換及び列交換することによって、パリティチェック行列Ｈ’に変換する。変換されたパリティチェック行列Ｈ’は、図１に図示されているように、右側上端の角部分１００の構成要素がいずれも０から構成されねばならない。すなわち、変換されたパリティチェック行列Ｈ’は、Ａ、Ｂ、Ｃ、Ｄ、Ｅ及びＴ領域（area）から構成され、Ｔ領域は、右側上端の角部分１００の構成要素がいずれも０である。
【０００９】
リチャードソンの方法によれば、パリティチェック行列の右側上端の角部分１００の構成要素ｔ個がいずれも０であるために、ｔ個のパリティビットは、逆代入（back-substitution）により容易に求めることができるので、パリティビット生成が容易である。しかし、（ｍ−ｔ）個のパリティビットを求めるためには、相変らず逆行列演算が必要である。（ｍ−ｔ）個の残りパリティビットを求める過程は、次の通りである。
【００１０】
リチャードソンの方法により、式（１）は式（２）のように書き換えられる。
【００１１】
【数２】
2008536437.tif 000004
式（２）でＳは、メッセージデータベクトル、Ｐ１、Ｐ２は、それぞれ第１パリティビットベクトル及び第２パリティビットベクトルである。式（２）は、式（３）及び（４）の行列方程式で表現される。
【００１２】
ＡＳ＋ＢＰ１＋ＴＰ２＝０，ＣＳ＋ＤＰ１＋ＥＰ２＝０          （３）
（−ＥＴ−１Ａ＋Ｃ）Ｓ＋（−ＥＴ−１Ｂ＋Ｄ）Ｐ１＝（−ＥＴ−１Ａ＋Ｃ）Ｓ＋φＰ１＝０      （４）
式（４）でリチャードソン行列φは、（−ＥＴ−１Ｂ＋Ｄ）である。式（３）及び（４）を連立して解くならば、式（５）と（６）とのように、第１パリティビットベクトルＰ１及び第２パリティビットベクトルＰ２を定義できる。
【００１３】
Ｐ１＝−（−ＥＴ−１Ｂ＋Ｄ）−１（−ＥＴ−１Ａ＋Ｃ）Ｓ＝−φ−１（−ＥＴ−１Ａ＋Ｃ）Ｓ      （５）
Ｐ２＝−Ｔ−１（ＡＳ＋ＢＰ１）        （６）
上のような方法によれば、ｔ個のパリティ情報は、逆代入方法により容易に求められるとしても、残り（ｍ−ｔ）個のパリティ情報を得るためには、逆行列演算、すなわちφ−１を計算しなければならないので、パリティビット生成が容易でない。
【００１４】
図２は、行と列とに一定の数の１を含むブロックｂ単位の既存のブロック単位のＬＤＰＣ行列の例である。図２は、単位行列ブロックを利用してＴ領域に一つの対角線行列を形成し、Ａ、Ｃ、Ｂ、Ｄ、Ｅ領域に単位行列ブロックとシフト行列ブロックとをランダムに配置している。
【００１５】
従って、Ｔ領域に含まれたブロックに対応するパリティビットは、逆代入により容易に求めることができるが、ギャップ（gap）として定義されるＥ領域に単位行列ブロックとシフト行列ブロックとがランダムに配置されるので、Ｅ領域とＤ領域とのブロックに対応するパリティビットを求めるためには、やはり逆行列演算φ−１を計算しなければならないので、パリティビット生成が困難である。
【発明の開示】
【発明が解決しようとする課題】
【００１６】
本発明は、前述の問題点を解決するために案出され、パリティビットを生成するにあたり、逆行列演算が必要なくてして全行列領域で逆代入が可能なブロック単位のパリティチェック行列生成方法及び装置とその記録媒体とを提供しようとするものである。
【課題を解決するための手段】
【００１７】
前記のような目的を達成するために、本発明は、ａ）第１パリティビットベクトルと第２パリティビットベクトルとの長さを基に、垂直方向にＬＤＰＣ行列の領域を分割する段階と、ｂ）前記分割された領域のうち前記第２パリティビットベクトルに対応する領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する段階と、ｃ）前記二重対角線行列の位置を基に、水平方向に前記ＬＤＰＣ行列の領域を分割する段階と、ｄ）前記ＬＤＰＣ行列のブロック単位の列ウェートが同一になるように、前記ＬＤＰＣ行列の垂直方向及び水平方向に分割された領域に含まれるブロック単位行列を生成する段階とを含む方法を提供する。
【００１８】
前記のような目的を達成するために、本発明は、第１パリティビットベクトル及び第２パリティビットベクトルの長さを基に、垂直方向にＬＤＰＣ行列の領域を分割する第１領域分割部と、前記ＬＤＰＣ行列の分割された領域のうち、前記第２パリティビットベクトルに対応する領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する二重対角線行列ブロック生成部と、前記二重対角線行列ブロック生成部により生成された二重対角線行列の位置を基に、水平方向に前記ＬＤＰＣ行列領域を分割する第２領域分割部と、前記ＬＤＰＣ行列のブロック単位の列ウェートが同一になるように、前記ＬＤＰＣ行列の垂直方向及び水平方向に分割された領域に含まれるブロック単位行列を生成するブロック単位行列生成部とを備える装置を提供する。
【００１９】
前記のような目的を達成するために、本発明は、ブロック単位のパリティチェック行列生成方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体において、前記方法は、第１パリティビットベクトルと第２パリティビットベクトルとの長さを基に、垂直方向にＬＤＰＣ行列の領域を分割する段階と、前記分割された領域のうち前記第２パリティビットベクトルに対応する領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する段階と、前記二重対角線行列の位置を基に、水平方向に前記ＬＤＰＣ行列の領域を分割する段階と、前記ＬＤＰＣ行列のブロック単位の列ウェートが同一になるように、前記ＬＤＰＣ行列の垂直方向及び水平方向に分割された領域に含まれるブロック単位行列を生成する段階とを含む記録媒体を提供する。
【００２０】
本発明の追加的な概念及び／または利点は、以下での詳細な説明で説明され、詳細な説明から明白となるか、あるいは発明の実行によって分かるであろう。
【発明の効果】
【００２１】
本発明によれば、パリティビットを生成するとき、逆行列演算が必要ではなくしてパリティチェック行列の全領域に対して逆代入が可能なので、さらに容易にパリティビットを生成できる。
【発明を実施するための最良の形態】
【００２２】
以下、添付された図面を参照しつつ、本発明による望ましい一実施形態について詳細に説明する。
【００２３】
図３は、ブロック単位のＬＤＰＣのコーディングまたはデコーディング時、式（２）により定義されたパリティチェック方程式でのＬＤＰＣ行列Ｈ’３００とコードワードベクトルｘ３１０との概念図である。
【００２４】
図３を参照するに、パリティチェック行列Ｈ’３００はｍ＊ｎサイズを有し、コードワードベクトルｘ３１０はｎ＊１サイズを有する。コードワードベクトルｘ３１０は、（ｎ−ｍ）長さのメッセージデータベクトルＳ；及びｍ１長さの第１パリティビットベクトルＰ１、ｍ２長さの第２パリティビットベクトルＰ２から構成される。従って、メッセージデータベクトルＳの長さ（ｎ−ｍ）＋第１パリティビットＰ１のベクトル長さ（ｍ１）＋第２パリティビットＰ２のベクトル長さ（ｍ２）＝ｎであり、ｍ１＋ｍ２＝ｍである。以下でさらに詳細に説明されるように、ＬＤＰＣ行列Ｈ’３００のＡ、Ｃ、Ｂ、Ｄ、Ｔ、及びＥ領域は、メッセージデータベクトルＳの長さ、第１パリティビットベクトルＰ１の長さ及び第２パリティビットベクトルＰ２の長さにより決定される。
【００２５】
図４は、本発明によるブロック単位のＬＤＰＣ行列の生成方法の動作フローチャートである。図４を参照するに、図３に図示された第１パリティビットベクトルＰ１の長さｍ１と第２パリティビットベクトルＰ２の長さｍ２とにより決定された地点で、ＬＤＰＣ行列Ｈ’の領域が垂直方向に分割される（４０１）。これにより、図３のＬＤＰＣ行列Ｈ’３００は、図５Ａに示されたように、５０１と５０２との地点で垂直方向に３領域ＡＣ、ＢＤ、及びＴＥに分けられる。３領域ＡＣ、ＢＤ、及びＴＥは、水平方向に隣接した領域である。５０１地点は、第２パリティビットベクトルＰ２の長さｍ２により決定され、５０２地点は、第１パリティビットベクトルＰ１の長さｍ１により決定される。しかし、５０１地点は、第２パリティビットベクトルＰ２の長さｍ２と第１パリティビットベクトルＰ１の長さｍ１とのうち一つにより決定されるように具現され、５０２地点は、第１パリティビットベクトルＰ１の長さｍ１とメッセージデータベクトルＳの長さ（ｎ−ｍ）とのうちいずれか一つにより決定されるように具現されうる。
【００２６】
次に、第２パリティビットベクトルＰ２に対応する領域ＴＥ５０３の上部に、図５Ｂに図示されているように、二重対角線行列５０４が配置されるように、ブロック単位の行列を生成する（４０２）。このとき、ブロック単位の二重対角線行列５０４に対して領域ＴＥの上端部５０５の構成要素ブロックは、いずれもゼロ（０）行列ブロックを生成する。二重対角線行列５０４は、単位行列ブロックを利用して生成できる。しかし、二重対角線行列５０４は、上位対角線行列に単位行列ブロックが配置され、下位対角線行列にシフト行列ブロックが配置されるように、ブロック単位の行列を生成できる。
【００２７】
４０２段階で生成された二重対角線行列５０４の位置を基に、ＬＤＰＣ行列Ｈ’３００を図５Ｃに図示された５０６地点で水平方向に分割する（４０３）。これにより、ＬＤＰＣ行列Ｈ’は、図３の３００のようにメッセージデータベクトルＳに対応するＡ及びＣ領域と、第１パリティビットベクトルＰ１に対応するＢ及びＤ領域と、第２パリティビットベクトルＰ２に対応するＴ及びＥ領域とに分割される。Ａ領域は、メッセージデータベクトルＳに対応する上部領域、Ｃ領域はメッセージデータベクトルＳに対応する下部領域として定義できる。Ｂ領域は、第１パリティビットベクトルＰ１に対応する上部領域、Ｄ領域は、第１パリティビットベクトルＰ１に対応する下部領域として定義できる。Ｔ領域は、第２パリティビットベクトルＰ２に対応する上部領域として定義でき、Ｅ領域は、第２パリティビットベクトルＰ２に対応する下部領域として定義できる。
【００２８】
このように、ＬＤＰＣ行列Ｈ’３００が６個の領域Ａ、Ｃ、Ｂ、Ｄ、Ｔ、及びＥに分割されれば、分割されたＡ、Ｃ、Ｂ、Ｄ、Ｅ領域がサイクル４現象を避ける条件、列ウェート（Ｗｃ）が同じである条件、及びリチャードソン行列φが単位行列でなければならない条件を満足するように、ブロック単位の行列を生成する（４０４）。
【００２９】
図６は、図４の４０４段階の詳細フローチャートである。図５及び図６を参照し、ＬＤＰＣ行列Ｈ’のＡ、Ｃ、Ｂ、Ｄ、Ｅ領域でのブロック単位行列の生成過程について説明すれば、次の通りである。図５Ｄの領域Ｂ、Ｄ、Ｅ、及びＴで「０」は、シフトされていない単位行列ブロック（unit  matrix  block）を表し、「−１」は「−１負」シフト行列ブロックを表し、「＋１」は「＋１正」シフト行列ブロックを表し、マークされていない行列ブロックは、ゼロ行列ブロック（zero  matrix  block）を表す。
【００３０】
まず、Ｅ領域で、図５Ｄに図示されているように、単位行列ブロック、シフト行列ブロック及びゼロ行列ブロックが配置されるように、ブロック単位行列が生成される（６０１）。図５Ｄに図示されたＥ領域を介して分かるように、Ｅ領域は、最右側ブロック単位列に単位行列ブロックが配置され、前記最右側ブロック単位列を除外した領域で単位行列ブロックとシフト行列ブロックとのうち一つと、ゼロ行列ブロックとが垂直方向及び水平方向に交互に配置されるように、ブロック単位行列を生成する。図５Ｄで利用したシフト行列ブロックは、＋１番目の正シフト行列ブロックである。＋１番目の正シフト行列ブロックは、図８に図示されているように、単位行列８０１に含まれた１の位置を、＋１番目の正シフト行列ブロック８０３と共に右側に１マスずつシフトして得られる。
【００３１】
Ｂ領域で、図５Ｄに図示されているように、シフト行列ブロック、単位行列ブロック、及びゼロ行列ブロックが配置されるように、ブロック単位行列を生成する（６０２）。すなわち、最上位ブロック単位行は、単位行列ブロックとシフト行列ブロックとが水平方向に交互に配置され、前記最上位ブロック単位行でシフト行列ブロックが配置された列の所定位置にシフト行列ブロックが配置されるように、ブロック単位行列を生成する。図５Ｄで前記所定位置は、Ｂ領域の最下端の直上ブロックの位置に該当する。Ｂ領域でのシフト行列は、−１番目の負シフト行列ブロックを使用する。−１番目の負シフト行列は、図８に図示された−１番目の負シフト行列８０２と共に単位行列８０１に含まれた１を左側に１マスずつシフトして得られる。
【００３２】
Ｄ領域で、図５Ｄに図示されているように、シフト行列ブロック、単位行列ブロック及びゼロ行列ブロックが配置されるように、ブロック単位行列を生成する（６０３）。すなわち、最下位ブロック単位行は、単位行列ブロックが配置され、Ｄ領域での最下位ブロック単位行で最左側に位置したブロックの直上ブロックにシフト行列ブロックが配置されるように、ブロック単位の行列を生成する。Ｄ領域で使われたシフト行列ブロックは、＋１番目の正シフト行列ブロックである。
【００３３】
次に、Ａ及びＣ領域でサイクル４現象を防止する条件を満足するように、Ａ及びＣ領域に既生成の行列ブロックのタイプをチェックしつつ、ブロック単位行列を順次に生成する（６０４）。前記サイクル４条件は、図７に図示されているように、単位行列ブロック７０１，７０２，７０３，７０４）の位置が四角形をなるサイクル４現象を防止できるように、ブロック単位行列を配置するのである。前記サイクル４現象が発生する場合、正常なパリティビットチェックコーディング及びデコーディングを行えない。前記単位行列ブロック７０１の位置が、例えば（２，２）番目ブロックの位置に該当すれば、単位行列ブロック７０２の位置は、（２，８）番目ブロックの位置に該当し、単位行列ブロック７０３の位置は、（４，２）番目ブロックの位置に該当し、単位行列ブロック７０４の位置は、（４，８）番目ブロックの位置に該当しうる。
【００３４】
図６での前記Ｅ、Ｂ、Ｄ領域についてのブロック単位行列生成順序は変更可能である。また、Ｅ、Ｂ、Ｄ領域でのゼロ行列、単位行列及びシフト行列の位置は、Ｅ、Ｂ、Ｔ、Ｄ領域でサイクル４現象を防止する条件、リチャードソン行列φが単位行列になる条件、及び列ウェート（Ｗｃ）が同じ条件を満足するように既定のものである。
【００３５】
また、パリティチェック行列に対する列ウェート（Ｗｃ）が同じである条件を満足するように、前記Ａ、Ｃ領域でのブロック単位行列を生成する。Ａ、Ｃ領域でのブロック単位行列生成は、Ｂ、Ｄ、Ｅ、Ｔ領域でのブロック単位行列の生成後に行われる。図５Ｄは、列ウェートが３である場合である。Ｂ、Ｄ、Ｅ、Ｔ領域で利用されるシフト行列ブロックは、＋Ｐ番目の正シフト行列ブロック、または−Ｐ番目の負シフト行列ブロックを利用できる。＋Ｐ番目の正シフト行列ブロックは、単位行列ブロックでの１の位置を右側にＰマスほど移動させた行列ブロックであり、−Ｐ番目の負シフト行列ブロックは、単位行列ブロックでの１の位置を左側にＰマスほど移動させた行列ブロックである。
【００３６】
これにより、図５Ｄに図示されているようなブロック単位のＬＤＰＣ行列が生成されうる。図５ＤのＢ、Ｄ、Ｅ、Ｔ領域内のブロックに記載されている数字「０」は、シフトがなされていない単位行列ブロックを表し、「−１」は、負シフトがなされた行列ブロックを表し、「＋１」は、正シフトがなされた行列ブロックを表す。図５Ｄで、ｂＭ１＝ｍ１であり、ｂＭ２＝ｍ２であり、ｂは１ブロックの長さである。何も表示されていないブロックは、ゼロ行列ブロックを表す。
【００３７】
図９は、本発明の望ましい実施形態によるパリティチェック行列生成装置の機能ブロック図である。
【００３８】
第１領域分割部９０１は、既設定のパリティチェック行列領域を垂直方向に分割する。すなわち、入力される第１パリティビットベクトル長と第２パリティビットベクトル長とを利用し、図５Ａに図示されているように、既設定のパリティチェック行列領域を垂直方向に分割する。しかし、図４で言及した通り、メッセージデータベクトル長と第１パリティビットベクトル長とのうち一つを利用して５０２地点を決定し、第１パリティビットベクトル長と第２パリティビットベクトル長とのうち一つを利用して５０１地点を決定し、パリティチェック行列領域を水平に隣接した３領域に垂直方向に分割できる。
【００３９】
二重対角線行列ブロック生成部９０２は、第１領域分割部９０１で垂直方向に分割されたパリティチェック行列で、第２パリティビットベクトルに対応する領域の上部に二重対角線行列が配置されるように、ブロック単位の行列を生成する。すなわち、図４の４０２段階で説明した通り、二重対角線行列が配置されるように、ブロック単位の行列を生成する。
【００４０】
第２領域分割部９０３は、二重対角線行列ブロック生成部９０２により生成された二重対角線行列ブロックの位置を基に、パリティチェック行列を水平方向に分割する。これにより、パリティチェック行列の領域は、図５Ｃに図示されているように、６個の領域に分割される。
【００４１】
ブロック単位行列生成部９０４は、Ｂ、Ｄ、Ｅ、Ｔ領域に対してパリティチェック行列の列ウェートが同じである条件、サイクル４現象を防止する条件、及びリチャードソン行列φが単位行列になる条件を満足するように、既設定のブロック単位行列タイプ情報及び位置情報を基に、前記Ｂ、Ｄ、Ｅ、Ｔ領域でのブロック単位行列を生成する。すなわち、Ｂ、Ｄ、Ｅ、Ｔ領域が８×８ブロックであるならば、図５Ｄに図示されているように行列ブロックが生成されるように、既設定のブロックの位置とそれに対応する行列ブロックのタイプ情報とを基に、ブロック単位行列生成部９０４は、ブロック単位行列を生成する。例えば、Ｔ領域の二重対角線行列が配置されるブロック位置と、それに対応する行列ブロックのタイプ情報とが単位行列ブロックとして設定されれば、二重対角線行列が配置されるブロック位置でブロック単位行列生成部９０４は、単位行列ブロックを生成する。
【００４２】
また、ブロック単位行列生成部９０４は、Ａ領域及びＣ領域についてパリティチェック行列の列ウェートが同じである条件、サイクル４現象を防止する条件を満足するように、Ａ領域及びＣ領域で以前に生成されたブロック単位行列のタイプをチェックしつつ、ブロック単位行列を生成する。これにより、ブロック単位行列生成部９０４は、図５Ｄに図示されているようなブロック単位のＬＤＰＣ行列が生成される。図５Ｄから分かるように、Ｅ領域の最右側列に単位行列ブロックが配置されるので、パリティチェック行列の全領域に対して逆代入が可能である。
【００４３】
このように生成されるパリティチェック行列を利用する場合、第１パリティビットベクトル及び第２パリティビットベクトルは、式（７）及び式（８）のように定義可能である。
【００４４】
Ｐ１＝−（−ＥＴ−１Ａ＋Ｃ）Ｓ        （７）
Ｐ２＝−Ｔ−１（ＡＳ＋ＢＰ１）        （８）
式（７）から分かるように、本発明によれば、逆行列演算φ−１を計算する必要がない。
【００４５】
一方、本発明によるパリティチェック行列生成方法は、コンピュータプログラムとして作成可能である。前記プログラムを構成するコード及びコードセグメントは、当分野のコンピュータプログラマによって容易に推論されうる。また、前記プログラムは、コンピュータで読み取り可能な情報記録媒体に保存され、コンピュータで読み取り可能であり、かつコンピュータにより実行されることによって、パリティチェック行列の生成方法を具現する。前記情報記録媒体は、磁気記録媒体、光記録媒体及びキャリアウェーブ媒体を含む。
【００４６】
以上、本発明についてその望ましい実施形態を中心に説明した。本発明が属する技術分野で当業者は、本発明が本発明の本質的な特性から外れない範囲で変形された形態に具現可能であることを理解することができるであろう。従って、開示された実施形態は、限定的な観点ではなくして説明的な観点から考慮されねばならない。本発明の範囲は、前述の説明ではなくして特許請求の範囲に示されており、それと同等な範囲内にあるあらゆる差異点は、本発明に含まれるものと解釈されるのである。
【図面の簡単な説明】
【００４７】
【図１】リチャードソンの方法により変換されたパリティチェック行列のフォーマットを表した図である。
【図２】既存のブロック単位のＬＤＰＣ行列の例である。
【図３】ＬＤＰＣコーディングまたはデコーディング時、ブロック単位のＬＤＰＣ行列Ｈ’とコードワードベクトルｘとの概念図である。
【図４】本発明によるブロック単位のＬＤＰＣ行列の生成方法の動作フローチャートである。
【図５Ａ】本発明によるブロック単位のＬＤＰＣ行列の生成過程を図示した例である。
【図５Ｂ】本発明によるブロック単位のＬＤＰＣ行列の生成過程を図示した例である。
【図５Ｃ】本発明によるブロック単位のＬＤＰＣ行列の生成過程を図示した例である。
【図５Ｄ】本発明によるブロック単位のＬＤＰＣ行列の生成過程を図示した例である。
【図６】図４の４０４段階の詳細フローチャートである。
【図７】サイクル４現象を発生させるパリティチェック行列の例示図である。
【図８】本発明で利用される単位行列ブロック、−１番目の負シフト行列ブロック及び＋１番目の正シフト行列ブロックの例示図である。
【図９】本発明によるブロック単位のＬＤＰＣ行列の生成装置の機能ブロック図である。
【図１】
2008536437.tif 000005
【図２】
2008536437.tif 000006
【図３】
2008536437.tif 000007
【図４】
2008536437.tif 000008
【図５Ａ】
2008536437.tif 000009
【図５Ｂ】
2008536437.tif 000010
【図５Ｃ】
2008536437.tif 000011
【図５Ｄ】
2008536437.tif 000012
【図６】
2008536437.tif 000013
【図７】
2008536437.tif 000014
【図８】
2008536437.tif 000015
【図９】
2008536437.tif 000016
【国際調査報告】
2008536437.tif 000017
2008536437.tif 000018
2008536437.tif 000019