(57)【要約】【課題】  低密度付加情報発生用マトリックスを用いたエラー訂正方法及びその装置を提供する。【解決手段】  メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生方法において、パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成し、（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させ、（ｃ）トライアンギュラマトリックスと前記メッセージワードとを用いてパリティ情報を計算することによって、ＬＤＰＣを用いた符号化時に付加情報を効率よく計算しかつ計算量も減少させうる。【選択図】      図２
2004236313.tif 000002
【特許請求の範囲】
【請求項１】
メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生方法において、
（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する段階と、
（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最上位１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる段階と、
（ｃ）前記トライアンギュラマトリックスと前記メッセージワードとを用いてパリティ情報を計算する段階と、
（ｄ）式ＨＸ＝０を用いて従来の方法によって前記段階（Ｃ）で計算されていない残りのパリティ情報を計算する段階とを含み、ここでＸはコードワードマトリックスを示す方法。
【請求項２】
前記（ａ）段階は、
前記パリティチェックマトリックス内の各カラム内の最上端の１の位置を抽出する段階と、
前記最上端の１の位置が高いものから前記パリティチェックマトリックスの左側に位置すべく前記各カラムを再整列する段階とを含むことを特徴とする請求項１に記載のパリティ情報発生方法。
【請求項３】
前記（ｂ）段階は、
前記水平ラインＬ３の上部に対し、前記再整列パリティチェックマトリックスのメッセージマトリックス部分Ｍｍの各カラムを前記再整列パリティチェックマトリックスのパリティマトリックス部分Ｍｐの各カラムと左側から交換する段階を含むことを特徴とする請求項１に記載のパリティ情報発生方法。
【請求項４】
前記（ｃ）段階はバックワード代替計算法により行われることを特徴とする請求項１に記載の方法。
【請求項５】
前記（ｄ）段階はガウスエリメネーション演算方法により行われることを特徴とする請求項１に記載の方法。
【請求項６】
メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生方法において、
（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する段階と、
（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最上位１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置に基づいて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる段階と、
（ｃ）前記水平ラインＬ３の下部に存在するローに対し、前記ローに存在する１の位置に基づいてロー交換及びカラム交換を行うことによって拡張されたトライアンギュラマトリックスを生成する段階と、
（ｄ）前記拡張されたトライアンギュラマトリックス及び前記メッセージワードを用いてパリティ情報を計算する段階とを含む方法。
【請求項７】
前記（ｃ）段階は、
（ｃ１）前記水平ラインＬ３の下部に存在するローに対し、前記ロー内の右側から２番目の１の位置が、前記再整列パリティチェックマトリックスのパリティマトリックス部分Ｍｐの対角ラインＬ２より左側にあるローが存在するか否かを検査する段階と、
（ｃ２）前記ローが存在する場合、前記ローを前記水平ラインＬ３の下部のローのうち最上位ローとロー交換する段階と、
（ｃ３）前記新しい最上位ロー内に含まれた１のうち前記対角ラインＬ２より右側に存在する１を含む第１カラムを、前記新しい最上位ロー内に含まれた１のうち前記対角ラインＬ２の最も隣接した左側に存在する第２カラムとカラム交換する段階とを含むことを特徴とする請求項６に記載の方法。
【請求項８】
前記（ｃ）段階では対角ラインＬ２に沿ってロー及びカラム交換を行い続けて最後から２番目の１の位置が現在処理しようとする対角マトリックスより小さなローが存在しないまで繰り返して行うことを特徴とする請求項７に記載の方法。
【請求項９】
前記（ｄ）段階は、
（ｄ１）前記拡張されたトライアンギュラマトリックスと前記メッセージワードを用いてバックワード代替演算を行うことによって一部のパリティ情報を生成する段階を含むことを特徴とする請求項６に記載の方法。
【請求項１０】
前記（ｄ１）段階は、バックワード代替計算法を用いて行われることを特徴とする請求項９に記載の方法。
【請求項１１】
前記（ｄ）段階は、
（ｄ２）前記（ｄ１）段階で生成されていない前記パリティチェックマトリックスの部分に対し、ガウスエリミネーション方法を用いて残りのパリティ情報を計算する段階をさらに含む請求項５に記載の方法。
【請求項１２】
メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生装置において、
（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する手段と、
（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最上位１を通る再整列対角ラインＬ１の交差点Ｉを探し、前記交差点Ｉを取る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる手段と、
（ｃ）前記トライアンギュラマトリックスと前記メッセージワードとを用いてパリティ情報を計算する手段と、
（ｄ）式ＨＸ＝０を用いて従来の方法によって前記（ｃ）手段により生成されていない残りのパリティ情報を生成する手段とを含む装置。
【請求項１３】
前記（ａ）手段は、
前記パリティチェックマトリックス内の各カラム内の最上端の１の位置を抽出する手段と、
前記最上端の１の位置が高いものから前記パリティチェックマトリックスの左側に位置すべく前記各カラムを再整列する手段とを含むことを特徴とする請求項１２に記載の装置。
【請求項１４】
前記（ｂ）手段は、
前記水平ラインＬ３の上部に対し、前記再整列パリティチェックマトリックスのメッセージマトリックス部分Ｍｍの各カラムを前記再整列パリティチェックマトリックスのパリティマトリックス部分Ｍｐの各カラムと左側から交換する手段を含むことを特徴とする請求項１２に記載の装置。
【請求項１５】
前記（ｃ）手段は、バックワード代替計算法を用いてパリティ情報を生成することを特徴とする請求項１２に記載の装置。
【請求項１６】
前記（ｄ）手段は、ガウスエリメネーション演算方法を用いてパリティ情報を生成することを特徴とする請求項１２に記載の装置。
【請求項１７】
メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生手段において、
（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する手段と、
（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１の交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる手段と、
（ｃ）前記水平ラインＬ３の下部に存在するローに対し、前記ローに存在する１の位置に基づいてロー交換及びカラム交換を行うことによって拡張されたトライアンギュラマトリックスを生成する手段と、
（ｄ）前記拡張されたトライアンギュラマトリックス及び前記メッセージワードを用いてパリティ情報を計算する手段とを含む装置。
【請求項１８】
前記（ｃ）手段は、
（ｃ１）前記水平ラインＬ３の下部に存在するローに対し、前記ロー内の右側から２番目の１の位置が前記再整列パリティチェックマトリックスのパリティマトリックス部分Ｍｐの対角ラインＬ２より左側にあるローが存在するか否かを検査する手段と、
（ｃ２）前記ローが存在する場合、前記ローを前記水平ラインＬ３の下部のローのうち最上位ローとロー交換する手段と、
（ｃ３）前記新しい最上位ロー内に含まれた１のうち前記対角ラインＬ２より右側に存在する１を含む第１カラムを、前記新しい最上位ロー内に含まれた１のうち前記対角ラインＬ２の最も隣接した左側に存在する第２カラムとカラム交換する手段とを含むことを特徴とする請求項１７に記載の装置。
【請求項１９】
前記（ｄ）手段は、
（ｄ１）前記拡張されたトライアンギュラマトリックスと前記メッセージワードとを用いてバックワード代替演算を行うことによって一部パリティ情報を生成する手段を含むことを特徴とする請求項１７に記載の装置。
【請求項２０】
前記（ｄ）手段は、
（ｄ２）前記拡張されたトライアンギュラマトリックスを除いた前記パリティチェックマトリックスの部分に対し、ガウスエリミネーション方法を用いて残りのパリティ情報を計算する手段をさらに含む請求項１７に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はエラー訂正及び信号検出分野に係り、特に低密度付加情報発生用のマトリックスを用いたエラー訂正方法及びその装置に関する。
【背景技術】
【０００２】
エラー訂正のために使用するコードのうちＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  ｃｈｅｃｋ  Ｃｏｄｅ）を用いた符号化方法で付加情報を発生させるためにローとカラムとに一定数の１を含むパリティチェックコードを形成し、これを用いて付加情報を発生させる。すなわち、カラムとローとに一定数の１を含むマトリックスを形成し、これをパリティチェックマトリックスＨに置き、“Ｈｘ＝０”になるコードワードを発生させる。この際、ｘは元のデータと付加情報とが連結されている。このような計算を行うためにパリティチェックマトリックスＨをガウスエリメネーションを用いてジェネレーターマトリックスＧに変換するか、下位トライアンギュラ形態に変換してパリティ計算を行う。
【０００３】
ジェネレーターマトリックスＧは本来マトリックスのスパースネス（ｓｐａｒｓｅｎｅｓｓ）が喪失されて計算量が多くなる短所があり、下位トライアンギュラ形態も計算過程が複雑な短所があった。
【０００４】
すなわち、従来のパリティチェックマトリックスＨは図１に示された通りであり、“Ｈｘ＝０”になるコードワードを発生させるための下位トライアンギュラ形態の計算は次の式（１）のようであり、その計算過程が複雑であることが分かる。
【０００５】
【数１】
2004236313.tif 000003
パリティ情報を生成するための式ＨＸ＝０は上の式（１）により２つの式に分離される。１つはＡｓＴ＋Ｂｐ１Ｔ＋Ｔｐ２Ｔ＝０であり、ここでｓは元のデータ部分を示し、結合因子ｐ１、ｐ２はパリティデータ部分を示す。さらに他の１つは（−ＥＴ−１Ａ＋Ｃ）ｓ＋（−ＥＴＢ＋Ｄ）ｐ＝０であり、ここで、ＬＤＰＣ基本概念は、非特許文献１に開示されており、Ｈ  ｍａｔｒｉｘに対する技術は非特許文献２に開示されている。
【特許文献１】米国特許第６，４０５，３４３号
【非特許文献１】Ｄ．Ｊ．ＭａｃＫａｙ，“Ｇｏｏｄｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｏｎ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ，”ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｖｏｌ．４５，ｎｏ．２，ｐｐ．３９９−４３１，１９９９
【非特許文献２】Ｔ．Ｒｉｃｈａｒｄｓｏｎ，Ｒ．Ｕｒｂａｎｋｅ，“Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ，”ＩＥＥＥ  Ｔｒａｎｓ．ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｙ，ｖｏｌ．４７，ｎｏ．２，ｐｐ．６３８−６５６，２００１
【発明の開示】
【発明が解決しようとする課題】
【０００６】
したがって、本発明の目的は、低密度付加情報発生用マトリックスを用いたエラー訂正方法及びその装置を提供するところにある。
【０００７】
本発明の他の目的は、ＬＤＰＣの符号化時に付加情報を効率的に計算するための低密度付加情報発生用のマトリックスを用いるエラー訂正方法及びその装置を提供するところにある。
【課題を解決するための手段】
【０００８】
前述した課題を解決するために本発明は、メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生方法において、（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する段階と、（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる段階と、（ｃ）前記トライアンギュラマトリックスと前記メッセージワードとを用いてパリティ情報を計算する段階とを含む。
【０００９】
また本発明は、メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いてパリティ情報発生方法において、（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する段階と、（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる段階と、（ｃ）前記水平ラインＬ３の下部に存在するローに対し、前記ローに存在する１の位置に基づいてロー交換及びカラム交換を行うことによって拡張されたトライアンギュラマトリックスを生成する段階と、（ｄ）前記拡張されたトライアンギュラマトリックス及び前記メッセージワードを用いてパリティ情報を計算する段階とを含む。
【００１０】
また本発明は、メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐであるパリティチェックマトリックスＨを用いるパリティ情報発生装置において、（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する手段と、（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１との交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる手段と、（ｃ）前記トライアンギュラマトリックスと前記メッセージワードを用いてパリティ情報を計算する段階とを含む。
【００１１】
また本発明は、メッセージワード長ｍ、コードワード長ｃ、及びパリティ長がｐのパリティチェックマトリックスＨを用いてパリティ情報発生手段において、（ａ）前記パリティチェックマトリックスのカラム内に含まれた１の位置を基準に前記カラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する手段と、（ｂ）前記パリティチェックマトリックスＨのうちパリティ情報に対応するマトリックス部分Ｍｐの対角ラインＬ２と再整列パリティチェックマトリックスの最初１を通る再整列対角ラインＬ１の交差点Ｉを探し、前記交差点Ｉを通る水平ラインＬ３の上部に存在するローに含まれた１の位置を用いて前記再整列パリティチェックマトリックスをカラム交換することによってトライアンギュラマトリックスＴを発生させる手段と、（ｃ）前記水平ラインＬ３の下部に存在するローに対し、前記ローに存在する１の位置に基づいてロー交換及びカラム交換を行うことによって拡張されたトライアンギュラマトリックスを生成する手段と、（ｄ）前記拡張されたトライアンギュラマトリックス及び前記メッセージワードを用いてパリティ情報を計算する手段とを含む。
【発明の効果】
【００１２】
本発明は、ＬＤＰＣのエンコ−ダ具現のためのパリティチェックマトリックスを用いて付加情報を発生させる方法で演算量をさらに減少できてパリティ情報をさらに効率的に計算できる。
【発明を実施するための最良の形態】
【００１３】
以下、添付された図面を参照して本発明の望ましい実施例を説明する。
【００１４】
本発明において、パリティチェックマトリックスに加える変形はカラムまたはローの交換に限定される。カラムまたはローの交換は、カラムまたはローが全体的に変わってもパリティチェックマトリックスを用いた方程式で相互独立的な方程式が可能なので、パリティ情報の生成に影響を及ぼさないからである。
【００１５】
図２は、本発明による低密度付加情報発生用のマトリックスを用いたエラー訂正装置の一実施例に係るブロック図である。本発明に係るエラー訂正装置は、パリティチェックマトリックス発生部２１０、カラム再整列部２２０、トライアンギュラマトリックス発生部２３０、トライアンギュラマトリックス拡張部２４０、バックワード代替計算部２５０及び下位パリティ計算部２６０を含む。以下、前述したエラー訂正装置の動作を図３Ａないし図３Ｃ、及び図４を結び付けて説明する。
【００１６】
図２を参照すれば、パリティチェックマトリックス発生部２１０はコードワード長ｃを有し、その数はパリティ情報長ｐと同じロー、及びパリティ情報長ｐの長さを有し、その数はコードワード長ｃと同じカラムを有するパリティチェックマトリックスＨを生成する。パリティチェックマトリックスＨはその構成要素として０または１を有し、この際１の数は０の数に比べて非常に少ない。
【００１７】
図３Ａは、カラム再整列部により生成された再整列パリティチェックマトリックスＨ’を示す図である。
【００１８】
カラム再整列部２２０は各カラム内の最上端の１の位置の高い順にパリティチェックマトリックスＨ内のカラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する。言い換えれば、パリティチェックマトリックス内の各カラム内の最上端の１の位置が高いカラムであるほどパリティチェックマトリックス内で最も左側に位置するようにカラムを相互交換することによってカラムを再整列する。図３において濃い点線Ｌ１は各カラム内の最上端１を連結した‘再整列対角ライン’を示す。
【００１９】
図３Ｂは、再整列パリティチェックマトリックスＨ’内のパリティ対角ラインを示す図である。再整列パリティチェックマトリックスＨ’はメッセージワード長を横長として有するメッセージマトリックス部分Ｍｍ及びパリティ長を横長として有するパリティマトリックス部分Ｍｐとに分割されうる。この際、パリティマトリックス部分Ｍｐの対角ラインＬ２はパリティマトリックス部分Ｍｐの対角元素を連結したラインを示す。
【００２０】
図３Ｃは、トライアンギュラマトリックス発生部によるカラム交換過程を示す図である。
【００２１】
濃い実線Ｌ１は再整列対角ラインであり、濃い実線Ｌ２はパリティマトリックス部分Ｍｐの対角ラインであり、交差点ＩはラインＬ１とＬ２との交差点である。点線Ｌ３は交差点Ｉを通る水平ラインである。
【００２２】
トライアンギュラマトリックス発生部２３０は再整列パリティチェックマトリックスＨ’内のカラムを交換することによって図４Ａに現れたトライアンギュラマトリックスＴを生成する。この際、カラムの交換はメッセージマトリックス部分Ｍｍの最も左側にあるカラムとパリティマトリックス部分の最も左側にあるカラム間に行われる。すなわち、Ｃ１とＣｘ間にカラム交換が行われ、その後Ｃ２とＣｘ−１間にカラム交換が行われ、以降同様に交換工程が続けられる。
【００２３】
図４Ａは、生成されたトライアンギュラマトリックスＴを含むパリティチェックマトリックスを示す図である。トライアンギュラマトリックスＴの右側上部は全て０が分布し、ｐ個のカラムのうちカラム交換されたｋ個のカラムを除いた残りのカラムを含むパリティマトリックス部分Ｍｐは水平ラインＬ３を基準に上部には全て０を含み、下部には０及び１が含まれたマトリックス部分Ｃを含む。
【００２４】
トライアンギュラマトリックス拡張部２４０は複数のロー交換及びカラム交換を順次に行うことによって対角化されていないパリティチェックマトリックス部分Ｃを最大限対角化する。
【００２５】
図４Ｂ及び図４Ｃは、トライアンギュラマトリックス拡張部によりロー交換及びカラム交換を行う過程を示す図である。
【００２６】
まず、水平ラインＬ３下のあらゆるローのうち、各ロー内に含まれた１のうち右側から２番目にある１が対角ラインＬ２の左側に位置するローを抽出する。図４ＢでローＲ３がこのような条件を満たすローのうち１つを示す。次いで、抽出されたローＲ３を水平ラインＬ３の下位のローのうち最上位にあるローＲ１と交換する。もし、各ロー内に含まれた１のうち右側から２番目にある１が対角ラインＬ２の左側に位置するロー、例えばＲ３が存在しなければ、トライアンギュラマトリックス拡張部過程を終了する。
【００２７】
次いで、図４Ｃに示されたように、ローＲ３に含まれた１のうち対角ラインＬ２の右側に存在する１を含むカラムＣｑを、抽出したローＲ３の構成成分のうちＬ２の左側に位置する１を含むカラムＣｐと交換する。もし、Ｒ３の構成成分のうちＬ２の左側に位置する１を含むカラムＣｐが存在しなければｍカラム交換をそれ以上行わず、トライアンギュラ拡張過程を終了する。
【００２８】
各ローに含まれた２番目の１の位置が、対角ラインＬ２より左側に位置するローが存在しなくなるまで、ロー及びカラム交換過程は反復される。このような反復により、図４に示されたようにＣマトリックス領域ができるだけ小さくなるように下位トライアンギュラ領域が拡張される。
【００２９】
図４Ｄは、トライアンギュラマトリックス拡張部により拡張されたトライアンギュラマトリックスの一部を示したものである。図４Ｂ及び４Ｃの実施例で１つのカラムだけが交換が行われたので、トライアンギュラマトリックスＴの拡張された部分は横方向及び縦方向に１ビットだけが拡張された部分であることが分かる。
【００３０】
バックワード代替計算部２５０はトライアンギュラマトリックス拡張部２４０から発生したトライアンギュラマトリックス領域とメッセージビットを用いてバックワード代替計算を行うことによってパリティ情報を演算する。この計算は、次の式（２）のように示し、全体パリティビットのうちｋ個のパリティビット値を求められる。
【００３１】
【数２】
2004236313.tif 000004
下位パリティ計算部２６０はガウスエリメネーション演算方法または式（１）で表示された既存の方法により対角化されていない部分に対応するパリティビットの値を計算する。これはパリティビットｐ個のうち、バックワード代替計算部２５０で求めたｋ個を除いたパリティビット値はトライアンギュラマトリックス拡張部２４０によりトライアンギュラマトリックスに作られていない部分、すなわち、図４Ａに示されたＣマトリックスは既存のＨマトリックスの縮少された形態であるからである。
【００３２】
図５は、本発明による低密度付加情報発生用マトリックスを用いたエラー訂正方法の一実施例に係るフローチャートであって、図２を結び付けて説明する。
【００３３】
パリティチェックマトリックス発生部２１０はコードワード長ｃを有し、その数はパリティ情報長ｐと同じロー、及びパリティ情報長ｐの長さを有し、その数はコードワード長ｃと同じカラムを有するパリティチェックマトリックスＨを生成する（段階５０１）。
【００３４】
カラム再整列部２２０は、各カラム内の最上端の１の位置が高い順にパリティチェックマトリックスＨ内のカラムを再整列することによって再整列パリティチェックマトリックスＨ’を生成する（段階５０２）。
【００３５】
トライアンギュラマトリックス発生部２３０は再整列対角ラインＬ１とパリティマトリックス部分の対角ラインＬ２との交差点Ｉを探す（段階５０３）。
【００３６】
交差点Ｉを通る水平ラインＬ３の上部にあらゆるローに存在する１の位置を用いて再整列パリティチェックマトリックスＨ’内のカラムを交換することによってトライアンギュラマトリックスＴを生成する（段階５０４）。この際、カラムの交換はメッセージマトリックス部分Ｍｍの最も左側にあるカラムとパリティマトリックス部分の最も左側にあるカラム間で行われる。すなわち、Ｃ１とＣｘ間にカラム交換が行われ、その後Ｃ２とＣｘ−１間にカラム交換が行われ、以降同様に交換工程が続けられる。
【００３７】
水平ラインＬ３以下に存在するローのうち、各ロー内で右側から２番目に存在する１が対角ラインＬ２より左側に存在するローが存在するか否かを判断する（段階５０５）。
【００３８】
もし、存在するならば、トライアンギュラマトリックス拡張部２４０は複数のロー交換及びカラム交換を順次に行うことによって対角化されていないパリティチェックマトリックス部分Ｃを最大限対角化する（段階５０６及び５０７）。
【００３９】
まず、水平ラインＬ３下の全てのローのうち、各ロー内に含まれた１のうち右側から２番目にある１が対角ラインＬ２の左側に位置するローを抽出する。その後、抽出されたローＲ３を水平ラインＬ３の下位のローのうち最も上位にあるローＲ１と交換する（段階５０６）。
【００４０】
次いで、ローＲ３に含まれた１のうち対角ラインＬ２の右側に存在する１を含むカラムＣｑを、抽出したローＲ３の構成成分のうちＬ２の左側に位置する０を含むカラムＣｐと交換する（段階５０７）。
【００４１】
このような方法でロー及びカラム交換を行い続ける段階（５０８）。
【００４２】
段階５０１ないし５０８でトライアンギュラマトリックスを有するパリティチェックマトリックスが再生成される（段階５０９）。
【００４３】
バックワード代替計算部２５０はトライアンギュラマトリックス拡張部２４０から発生したトライアンギュラマトリックス領域とメッセージビットとを用いてバックワード代替計算を行うことによってパリティ情報を演算し、下位パリティ計算部２６０はガウスエリメネーション演算方法または式（１）で表示された既存方法により対角化されていない部分に対応するパリティビットの値を計算する（段階５１０）。
【００４４】
したがって、本発明は迅速なエンコーディングを必要とする応用分野に効率よく適用できる。
【産業上の利用可能性】
【００４５】
本発明は低密度パリティチェックマトリックスを用いたパリティ情報生成方法であって、低密度パリティチェックエンコーディングを用いるデータ記録及び再生分野に利用できる。
【図面の簡単な説明】
【００４６】
【図１】従来のエラー訂正のための付加情報を発生させるためのＨマトリックス構造図である。
【図２】本発明による低密度付加情報発生用のマトリックスを用いたエラー訂正装置の一実施例に係るブロック図である。
【図３Ａ】図２に示されたカラム整列部でパリティチェックマトリックスを再構成する過程を説明するための図である。
【図３Ｂ】図２に示されたカラム整列部でパリティチェックマトリックスを再構成する過程を説明するための図である。
【図３Ｃ】図２に示されたカラム整列部でパリティチェックマトリックスを再構成する過程を説明するための図である。
【図４Ａ】本発明に係るエラー訂正のための付加情報を発生させるためのＨマトリックス構造図である。
【図４Ｂ】本発明に係るエラー訂正のための付加情報を発生させるためのＨマトリックス構造図である。
【図４Ｃ】本発明に係るエラー訂正のための付加情報を発生させるためのＨマトリックス構造図である。
【図４Ｄ】本発明に係るエラー訂正のための付加情報を発生させるためのＨマトリックス構造図である。
【図５】本発明による低密度付加情報発生用のマトリックスを用いたエラー訂正方法の一実施例に係るフローチャートである。
【符号の説明】
【００４７】
２１０  パリティチェックマトリックス発生部
２２０  カラム再整列部
２３０  トライアンギュラマトリックス発生部
２４０  トライアンギュラマトリックス拡張部
２５０  バックワード代替計算部
２６０  下位パリティ計算部
【図１】
2004236313.tif 000005
【図２】
2004236313.tif 000006
【図３Ａ】
2004236313.tif 000007
【図３Ｂ】
2004236313.tif 000008
【図３Ｃ】
2004236313.tif 000009
【図４Ａ】
2004236313.tif 000010
【図４Ｂ】
2004236313.tif 000011
【図４Ｃ】
2004236313.tif 000012
【図４Ｄ】
2004236313.tif 000013
【図５】
2004236313.tif 000014