(57)【要約】      （修正有）【課題】低密度パリティチェックコーディングにおける低密度パリティチェック行列の変換において、パリティ情報生成のための演算量を減少させる。【解決手段】パリティチェック行列の行及び／または列に対して行移動及び／または列移動を行うことにより、パリティチェック行列に、対角線要素が“１”より構成され、前記対角線要素の上部は“０”より構成され、前記対角線要素の下部は“０”または“１”より構成されるサブブロックを含ませる。【選択図】図３
2005312034.tif 000002
【特許請求の範囲】
【請求項１】
低密度パリティチェックコーディングのパリティチェック行列変換方法において、
前記パリティチェック行列の行及び／または列について行移動及び／または列移動を行うことにより、前記パリティチェック行列に、対角線要素が“１”より構成され、前記対角線要素の上部は“０”より構成され、前記対角線要素の下部は“０”または“１”より構成されたサブブロックを含ませることを特徴とする方法。
【請求項２】
ａ）パリティチェック行列の第１行に連結された列を前記パリティチェック行列の左側に移動する段階と、
ｂ）前記第１行と前記移動した列とを含む、サブブロックの下部に位置する領域を現在検索領域として定義し、前記現在検索領域の右側を現在非検索領域として定義する段階と、
ｃ）‘前記現在検索領域に含まれた“１”の個数＝行次数−１’を満足する移動行を検索する段階と、
ｄ）前記移動行が存在する場合に、前記検索された移動行及び前記移動行と連結された列を列移動及び／または行移動することにより、前記移動行と前記移動行に連結された列との交差点を前記現在非検索領域の左上端に移動させる段階とを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記ｄ）前記検索された移動行を移動する段階は、
前記検索された移動行に連結された移動列を列移動することで前記現在非検索領域の最左列に移動し、前記移動行を行移動することで前記現在非検索領域の最上行に移動することを特徴とする請求項２に記載の方法。
【請求項４】
前記ｄ）前記検索された移動行を移動する段階は、
ｄ１）前記検索された移動行のうち、第１移動行に連結された第１移動列を前記現在非検索領域の最左列に移動する段階と、
ｄ２）前記第１移動行を前記非検索領域の最上行に移動する段階とを含むことを特徴とする請求項３に記載の方法。
【請求項５】
ｅ）前記現在検索領域を、前記ｄ）段階で移動した移動列を含み、かつ前記ｄ）段階で移動した移動行を除した領域に更新し、前記現在非検索領域を、前記更新された現在検索領域の右側に更新する段階を更に含むことを特徴とする請求項２に記載の方法。
【請求項６】
ｆ）前記段階ｃ）ないし段階ｅ）を、現在検索領域を更新しつつ前記パリティチェック行列の最後の行まで繰り返す段階を含むことを特徴とする請求項５に記載の方法。
【請求項７】
ｇ）前記移動行が存在しない場合に、前記現在非検索領域に存在する一つ以上の列を前記パリティチェック行列の前部に移動する段階と、
ｈ）前記現在検索領域を、前記現在検索領域に前記移動された列を追加した領域に更新し、前記現在非検索領域を、前記更新された現在検索領域の右側に更新する段階とを含むことを特徴とする請求項２に記載の方法。
【請求項８】
ｇ）前記列を移動する段階は、
ｇ１）前記現在検索領域に含まれた行のうち、現在非検索領域に存在する“１”の個数が最も小さい条件行を検索する段階と、
ｇ２）前記検索された条件行に連結された条件列のうち、任意の列を前記パリティチェック行列の最左列に移動する段階とを含むことを特徴とする請求項７に記載の方法。
【請求項９】
ｉ）前記段階ｃ）ないし段階ｅ）を、前記現在検索領域及び更新された現在非検索領域を更新しつつ前記パリティチェック行列の最後の列まで繰り返す段階を含むことを特徴とする請求項７に記載の方法。
【請求項１０】
低密度パリティチェックコーディングのパリティチェック行列を利用したパリティ情報生成方法において、
前記パリティチェック行列は、対角線要素が“１”より構成され、前記対角線要素の上部は“０”より構成され、前記対角線要素の下部は“０”または“１”より構成されたサブブロックを含み、
前記サブブロックは、前記パリティチェック行列の列移動及び／または行移動を通じて生成されることを特徴とする方法。
【請求項１１】
前記列交換及び／または行交換は、
ａ）パリティチェック行列の第１行に連結された列を前記パリティチェック行列の左側に移動する段階と、
ｂ）前記移動した列を含むサブブロックの下部に位置する領域を現在検索領域として定義し、前記現在検索領域の右側を現在非検索領域として定義する段階と、
ｃ）“前記現在検索領域に含まれた１の個数＝行次数−１”を満足する移動行を検索する段階と、
ｄ）前記移動行が存在する場合に、前記検索された移動行及び前記移動行と連結された列を、列移動及び／または行移動することで前記現在非検索領域の左上端に移動させる段階とを含むことを特徴とする請求項１０に記載の方法。
【請求項１２】
ｅ）前記移動行が存在しない場合に、前記現在非検索領域に存在する一つ以上の列を前記パリティチェック行列の前部に移動する段階と、
ｆ）前記現在検索領域を、前記現在検索領域に前記移動した列を追加した領域に更新し、前記現在非検索領域を前記更新された現在検索領域の右側に更新する段階と、を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
請求項２に記載された方法をコンピュータで実行させるためのプログラムを記録したコンピュータ可読記録媒体。
【請求項１４】
低密度パリティチェックコーディングによってデータをエンコーディングし、エラー訂正を行うための記録及び／または再生システムに使用するための変換されたパリティチェック行列を生成する方法において、
−前記パリティチェック行列の第１行とリンクする列を識別する段階と、
−前記リンクされた列を移動させることで前記パリティチェック行列の左側列を形成する段階と、
−前記リンクされた列内の前記パリティチェック行列に残余する行として第１検索領域を設定する段階と、
−リンクされていない列内の前記パリティチェック行列に残余する行として第２検索領域を設定する段階と、
−前記残余行のうち、‘前記第１検索領域に含まれた“１”の個数＝次数行の行次数−１’である前記次数行を識別する段階と、
−前記第２検索領域で、前記識別された次数行とリンクされた次数列とをシフトさせることにより前記第２検索領域の左側の列を形成し、前記識別された次数行をシフトさせることにより前記第１及び第２検索領域の上端部分の行を形成する段階と、
−前記次数行が識別されなければ、前記残余行のうち、前記第２検索領域内の“１”の個数が最も小さい条件行を識別する段階と、
−前記第２検索領域内で、前記条件行とリンクされた最大条件列とを移動させることによって前記パリティチェック行列の左側列を形成する段階とを含むことを特徴とする方法。
【請求項１５】
−前記第１行、あるいは前記リンクされた列及び前記次数列、または前記最大条件列内の次数行の下部に残余する行として前記第１検索領域を更新する段階と、
−前記第１行、あるいは前記リンクされていない列内の次数行の下部に残余する行として前記第２検索領域を更新する段階とを含み、
ここで、前記方法は、前記パリティチェック行列の最後の行に到達するまで行われることを特徴とする請求項１４に記載の方法。
【請求項１６】
前記記録及び／または再生システムは、対角線要素が“１”であるパリティチェック行列を使用し、エラー訂正を行うために前記最後の行に到達した後には、前記対角線要素の下部に存在する下部ブロックの少なくとも一つの構成要素が“１”であることを特徴とする請求項１５に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、エラー訂正のためのパリティ情報生成方法に係り、より詳細には、低密度パリティチェックコーディングにおいて低密度パリティチェック行列の変換方法に関する。
【背景技術】
【０００２】
エラー訂正のための付加情報生成方法において、低密度パリティチェックコーディング方法が広く使用されている。低密度パリティチェックコーディングとは、‘０’と‘１’より構成され、‘１’の数が‘０’の数よりはるかに小さい低密度パリティチェック行列Ｈを利用してパリティ情報を生成する方法である。パリティチェック行列Ｈの行に含まれた１の個数及び列に含まれた１の個数が一定である場合を規則的パリティチェック行列と言い、そうではない場合を不規則的パリティチェック行列と言う。パリティチェック行列で各行または列に含まれた１の個数はそれぞれ行次数及び列次数という。
【０００３】
ＬＤＰＣコーディングを利用したパリティ情報生成は、次の式（１）により行われる。
【０００４】
ＨＸ＝０      （１）
ここで、Ｈはｍ＊ｎのパリティチェック行列であり、Ｘはｎ＊１のコードワード行列である。Ｘは、ｍ個のメッセージ情報とｐ個のパリティ情報とより構成される。したがって、ｍ＋ｐ＝ｎである。
【０００５】
そのようなＬＤＰＣコーディングの基本概念は、非特許文献１に開示されており、この非特許文献１によれば、パリティ情報は、ガウス消去法などの行列演算を利用して式（１）を解くことで生成されうる。しかし、行列演算を利用する方法は、演算量が多いという問題点がある。
【０００６】
最近、式（１）を更に容易に解く方法が紹介された。この方法によれば、パリティチェック行列Ｈを下三角行列と呼ばれる特殊な形態のサブブロックを含むパリティチェック行列Ｈ’に変換し、変換されたパリティチェック行列Ｈ’を利用して順次にパリティ情報を生成する。この方法は、非特許文献２に開示されている。
【０００７】
以下、図１及び図２Ａないし図２Ｆを参照して従来の方法によるＨ行列変換方法を説明する。
【０００８】
図１は、従来の方法によってＨ行列をＨ’行列に変換する方法を示す時間フローチャートであり、図２Ａないし図２Ｆは、図１の方法の各段階によって生成されるＨ行列を示す図である。このような従来の方法は、欲張りアルゴリズム（Ｇｒｅｅｄｙ  Ａｌｇｏｒｉｔｈｍ）と呼ばれる。
【０００９】
段階１１０で、行列Ｈの第１行と連結されたあらゆる列を行列Ｈの最左側に移動する。ここで、‘行に連結された列’は、行に存在する‘１’を交差する列を意味し、‘移動’は、ｉ）行または列の交換及びｉｉ）他の行または列のシフトを通じて行われる。図２Ａは、第１行が４個の“１”を含む場合、段階１１０を経たＨ行列を示す。
【００１０】
段階１２０で、現在検索領域を、Ｈ行列全体で第１行及び段階１１０で生成された１を含む列を除いた残りの領域（図２ＢのＡ１）として定義する。検索領域は、以下の過程で行われる行検索または列検索において、“１”の個数を判断する基準領域になる。
【００１１】
段階１３０で、検索領域Ａ１について、行次数が１である行Ｒ１、Ｒ２、・・・Ｒｋを検索する。図２Ｃで、Ｒ１、Ｒ２・・・は、検索領域Ａ１に含まれた１の個数が１である、すなわち行次数が１である行を示す。
【００１２】
段階１４０で、次数が１である行が存在するかを判断する。もし、次数が１である行Ｒ１、Ｒ２、・・・Ｒｋが存在すれば、段階１５０ないし１８０に進行する。
【００１３】
段階１５０で、行Ｒ１、Ｒ２、・・・Ｒｋ及びこの行にそれぞれ連結された列Ｃ１、Ｃ２、・・・、Ｒｋを、行移動及び列移動を通じて検索領域Ａ１の左上端の方向に順次に移動する。例えば、検索領域Ａ１について、次数が１である行がＲ１及びＲ２である場合、まず、Ｒ１と連結されたＣ１を検索領域Ａ１の最左列に移動し、Ｒ１を検索領域Ａ１の最上端に移動させる。その後、Ｒ２と連結されたＣ２を検索領域Ａ１の第２左側に移動し、Ｒ２を検索領域Ａ１の第２上端に移動させる。その結果、検索領域Ａ１の左上端に単位行列Ｉ１が生成される（図２Ｄ）。
【００１４】
段階１６０で、現在検索領域の第１列の番号を示す現在インデックスｉを、段階１３０で検索された行の個数ｋほど増加させる。図２Ｄで、現在インデックスｉは５であり、検索された行の個数ｋは２である。
【００１５】
段階１７０で、現在検索領域を、検索領域Ａ１から単位行列Ｉ１を除いた領域（図２ＥのＡ２）に更新する。
【００１６】
段階１８０で、現在インデックスｉがパリティチェック行列Ｈの行の個数ｎより大きいかを判断する。もし小さければ、段階１３０に進行し、もし大きければ、行列変換の手続きを終了する。
【００１７】
もし、段階１４０で、次数が１である行が存在しなければ、段階１５５ないし１７５に進行する。
【００１８】
段階１５５で、現在検索領域Ａ１について最小の次数を有する行Ｒｍｉｎを検索する。
【００１９】
段階１６５で、現在検索領域Ａ１でＲｍｉｎと連結された列Ｃｍｉｎ１、Ｃｍｉｎ２、・・・、Ｃｍｉｎｌを検索し、検索されたＣｍｉｎ１、Ｃｍｉｎ２、・・・、Ｃｍｉｎｌのうち、任意のｌ−１個の列をＨ行列の最左側の部分に移動する（図２Ｆ）。
【００２０】
段階１７５で、現在検索領域の第１列の番号を示す現在インデックスｉを段階ｌ−１ほど増加させる。図２Ｆで、現在インデックスｉは５であり、ｌは３である。
【００２１】
段階１８５で、検索領域を、検索領域Ａ１から、段階１６５で移動させた列を除いた領域Ａ２に更新する（図２Ｇ）。
【００２２】
段階１９５で、現在インデックスｉがパリティチェック行列Ｈの行の個数ｎより大きいかを判断する。もし小さければ、段階１３０に進行し、もし大きければ、行列変換の手続きを終了する。
【００２３】
図２Ｈは、従来の方法により生成された変換されたＨ行列を示す。図２ＨのＨ行列は、単位行列Ｉが対角線方向に連結されたブロックを有し、そのブロック内の右上端の部分、すなわち“０”値のみからなる部分を利用して順次的なパリティ情報計算が行われる。
【００２４】
順次的なパリティ情報の計算のために必要な条件は、変換されたＨ行列が、そのブロックの対角線が“１”の値より構成され、その対角線の右上部（図２ＨのＤ）が“０”の値のみより構成された、いわゆる下三角行列を有さねばならないというものである。図２Ｈの変換されたＨ行列は、行列は単位行列Ｉが対角線方向に連結された下三角行列を含むため、そのような条件を満足する。
【００２５】
Ｈ行列からのパリティ情報計算は、下三角行列が大きいほど計算量が減る。すなわち、従来の方法で、単位行列の大きさが増加するほどパリティ情報生成に必要な計算量は減る。
【００２６】
しかし、図２Ｈの単位行列Ｉは、単位行列Ｉの対角線の右上部だけでなく、左下部も“０”値を有するため、下三角行列の増加には限界がある。もし、変換されたＨ行列が、そのサブブロックの右上部のみが“０”値より構成され、左下部には何らの条件も加えられていなければ、そのようなサブブロック内の下三角行列は図２Ｈの下三角行列より更に大きくなるかもしれない。すなわち、従来の方法は、順次的なパリティ計算のためのサブブロックが単位行列状に生成されるため、下三角行列の大きさの増加に限界があるという問題点が存在する。
【非特許文献１】Ｄ．Ｊ．  ＭａｃＫａｙ、“Ｇｏｏｄ  ｅｒｒｏｒ−ｃｏｒｒｅｃｔｉｏｎ  ｃｏｄｅｓ  ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ、”ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ、ｖｏｌ．４５、ｎｏ．２、ｐｐ．３９９〜４３１、１９９９
【非特許文献２】Ｔ．  Ｒｉｃｈａｒｄｓｏｎ、Ｒ．  Ｕｒｂａｎｋｅ、“Ｅｆｆｉｃｉｅｎｔ  ｅｎｃｏｄｉｎｇ  ｏｆ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ、”ＩＥＥＥ  Ｔｒａｎｓ．  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  ｔｈｅｏｒｙ、ｖｏｌ．４７、ｎｏ．２、ｐｐ．６３８〜６５６、２００１
【発明の開示】
【発明が解決しようとする課題】
【００２７】
本発明は、前記した問題点を解決するためになされたものであって、順次的なパリティ情報計算のためにＨ行列が有さねばならないサブブロックを単位行列の形態ではない他の形態に形成することにより、Ｈ行列内の下三角行列Ｄの部分の大きさが更に増加した変換されたＨ行列の生成方法を提供することを目的とする。
【課題を解決するための手段】
【００２８】
前記した課題を解決するための本発明は、低密度パリティチェックコーディングのパリティチェック行列変換方法において、前記パリティチェック行列の行及び／または列について行移動及び／または列移動を行うことにより、前記パリティチェック行列に、対角線要素が“１”より構成され、前記対角線要素の上部は“０”より構成され、前記対角線要素の下部は“０”または”１”より構成されたサブブロックを含ませる。
【００２９】
また前記した本発明は、ａ）パリティチェック行列の第１行に連結された列を前記パリティチェック行列の左側に移動する段階と、ｂ）前記第１行と前記移動した列とを含む、サブブロックの下部に位置する領域を現在検索領域として定義し、前記現在検索領域の右側を現在非検索領域として定義する段階と、ｃ）‘前記現在検索領域に含まれた“１”の個数＝行次数−１’を満足する移動行を検索する段階と、ｄ）前記移動行が存在する場合に、前記検索された移動行及び前記移動行と連結された列を列移動及び／または行移動することにより、前記移動行と前記移動行に連結された列との交差点を前記現在非検索領域の左上端に移動させる段階とを含む。
【００３０】
ここで、前記ｄ）前記検索された移動行を移動する段階は、前記検索された移動行に連結された移動列を列移動することで前記現在非検索領域の最左列に移動し、前記移動行を行移動することで前記現在非検索領域の最上行に移動することを特徴とする。
【００３１】
また、本発明は、ｇ）前記移動行が存在しない場合に、前記現在非検索領域に存在する一つ以上の列を前記パリティチェック行列の前部に移動する段階と、ｈ）前記現在検索領域を、前記現在検索領域に前記移動した列を追加した領域に更新し、前記現在非検索領域を、前記更新された現在検索領域の右側に更新する段階とを含む。
【００３２】
ここで、ｇ）前記列を移動する段階は、ｇ１）前記現在検索領域に含まれた行のうち、現在非検索領域に存在する“１”の個数が最も小さい条件行を検索する段階と、ｇ２）前記検索された条件行に連結された条件列のうち、任意の列を前記パリティチェック行列の最左列に移動する段階とを含むことを特徴とする。
【００３３】
また、本発明は、低密度パリティチェックコーディングのパリティチェック行列を利用したパリティ情報生成方法において、前記パリティチェック行列は、対角線要素が“１”より構成され、前記対角線要素の上部は“０”より構成され、前記対角線要素の下部は“０”または“１”より構成されたサブブロックを含み、前記サブブロックは、前記パリティチェック行列の列移動及び／または行移動を通じて生成されることを特徴とする。
【発明の効果】
【００３４】
本発明は、パリティチェック行列の行交換及び列交換を従来の方法と異なる基準により行うことにより、パリティ情報生成のために演算量を更に減少させうるパリティチェック行列を生成する。
【発明を実施するための最良の形態】
【００３５】
以下、添付図面を参照して本発明に係る好ましい一実施例を詳細に説明する。
【００３６】
図３は、本発明の一実施例によって変換されたＨ行列を生成する方法を示す時間フローチャートである。また、図４Ａないし図４Ｉは、図３の方法の各段階で生成されるＨ行列を示す図である。以下、図３の方法を図４Ａないし図４Ｉを参照して説明する。
【００３７】
段階３１０で、行列Ｈの第１行と連結されたあらゆる列を行列Ｈの最左側に移動する。ここで、‘行に連結された列’は、行に存在する‘１’を交差する列を意味し、‘移動’は、Ｉ）行または列の交換、及びｉｉ）他の行または列のシフトを通じて行われる。
【００３８】
例えば、第１行に連結された列がＣ２、Ｃ４、Ｃ７、Ｃ１５であれば、Ｃ２、Ｃ４、Ｃ７、Ｃ１５を何れも抽出した後に順に行列Ｈの最左側に移動し、残りの列は、右側にシフトさせる。Ｃ２、Ｃ４、Ｃ７、Ｃ１５の順序は本発明の具現とは関係ない。図４ＡのサブブロックＳＢ１は、段階３１０が行われることにより生成された第１行で“１”を含むブロックを示す。サブブロックＳＢ２は、何れも“０”値のみより構成される。“１”が含まれた列はサブブロックＳＢ１に移動したためである。
【００３９】
段階３２０で、行列ＨでサブブロックＳＢ１の下部に位置するサブブロックＡ１を現在検索領域として定義する。検索領域は、以下の過程で行われる行検索または列検索において、次数の計算の基準となる領域である。また、現在非検索領域は、行列Ｈで現在検索領域の右側として定義される。図４Ｂで斜線で示した領域Ａ１が現在検索領域であり、行列Ｈで斜線で示した領域の右側の領域Ａ１’は現在非検索領域である。
【００４０】
段階３３０で、現在検索領域Ａ１の内部に含まれた“１”の個数が行次数−１である移動行Ｒ１、Ｒ２、・・・、Ｒｋを検索する。図４Ｃで、行Ｒ１は、行次数が３であり、現在検索領域Ａ１内に２個の“１”を有するため、前記の条件を満足する行であり、行Ｒ２は、行次数が４であり、検索領域Ａ１内に３個の“１”を有するため、前記の条件を満足する行である。
【００４１】
段階３４０で、段階３３０で移動行Ｒ１、Ｒ２、・・・、Ｒｋが存在すれば、段階３５０ないし３６０に進行する。
【００４２】
段階３５０で、列交換及び行交換を行うことによって移動行Ｒ１を非検索領域Ａ１’の左上端に移動させる。これを詳細に説明すれば次の通りである。
【００４３】
第一段階として、移動行Ｒ１に連結された列Ｃ１を現在非検索領域Ａ１’の最左列（Ｈ行列の第５列）に移動する。残りの列は右へ１列ずつシフトされる。
【００４４】
第二段階として、移動行Ｒ１を非検索領域Ａ１’の最上行に移動させる。残りの行は下側に１行ずつシフトされる。
【００４５】
図４Ｄは、段階３５０が行われた後に形成されたＨ行列を示す。
【００４６】
段階３６０で、現在検索領域の第１行の番号を示す現在インデックスｊを段階３３０で１ほど増加させる。図４Ｄで、現在インデックスｉは５であり、移動した行の個数は１である。
【００４７】
段階３７０で、現在検索領域及び現在非検索領域を更新する。すなわち、検索領域Ａ１から段階３５０で発生した行が除去され、検索領域Ａ１に段階３５０で発生した列が追加された領域Ａ２を現在検索領域に更新する。図４Ｅで斜線で示した領域は検索領域Ａ２であり、斜線で示した領域の右側は非検索領域Ａ２’である。
【００４８】
段階３８０で、現在インデックスｊがパリティチェック行列の列数ｎより大きいかを判断する。もし大きければ、行列変換手続きを終了し、もし小さければ、段階３３０に進行する。
【００４９】
段階３４０で、もし、段階３３０で行Ｒ１、Ｒ２、・・・、Ｒｋが存在しなければ、段階３５５ないし３９５に進行する。段階３５５ないし３９５は、段階３３０で移動行が検索されない場合に列移動を通じて移動行を発生させるための手続きである。
【００５０】
段階３５５で、現在検索領域Ａ２’に含まれた行のうち、現在非検索領域Ａ２’内に存在する“１”の個数が最も小さい条件行Ｒｍａｘ１、Ｒｍａｘ２、・・・、Ｒｍａｘｌを検索する。ここで、ｌ条件行の個数を示す。
【００５１】
図４Ｆで、現在非検索領域内に存在する“１”の個数が最も小さい行はＲａである。
【００５２】
段階３６５で、最大次数行に連結された列Ｃｍａｘ１、Ｃｍａｘ２、・・・、Ｃｍａｘｌのうち、任意の条件列Ｃｍａｘを行列Ｈの第１列に移動する。図４Ｇは、条件列Ｃｍａｘが行列Ｈの第１列に移動することを示し、図４Ｈは、条件列Ｃｍａｘが移動した後の行列Ｈを示す。
【００５３】
段階３７５で、現在検索領域の第１行の番号を示す現在インデックスｊを、移動した条件列の個数１ほど増加させる。
【００５４】
段階３８５で、現在検索領域及び現在非検索領域を更新する。すなわち、現在検索領域Ａ２に移動後の条件列を追加した領域Ａ３を現在検索領域に更新し、更新された現在検索領域の右側領域Ａ３’を現在非検索領域に更新する。
【００５５】
段階３９５で、現在インデックスｊがパリティチェック行列Ｈの列個数ｎより大きいかを判断する。もし大きければ、行列変換手続きを終了させ、もし小さければ、段階３３０に進行する。
【００５６】
段階３５５ないし３９５は、段階３７０で移動行が存在していない場合に列移動を利用して移動行を発生させるための手続きである。最大次数列が行列Ｈの第１列に移動することにより現在検索領域に含まれた“１”の個数が増加し、増加した“１”の個数は移動行の発生を引き起こすためである。
【００５７】
図３の方法で、段階３４０ないし段階３８０は、移動行及びそれと連結された列を列移動及び行移動することにより下三角行列を発生させるための手続きである。段階３４０ないし３８０は、現在検索領域を基準に行われ、それ以上の移動行が発生しない場合には、前記したように段階３５５ないし３９５を行うことにより移動行の発生を引き起こす。
【００５８】
図５Ａ及び図５Ｂは、従来の方法と本発明により生成されたパリティチェック行列の構成を示す図である。
【００５９】
パリティ情報生成のための式（１）を容易に解くための必要条件は、ｉ）変換後のパリティチェック行列は対角要素が何れも１より構成されねばならず、ｉｉ）対角要素の上部は何れも０より構成されねばならない。
【００６０】
図５Ａを参照するに、従来の方法によるパリティチェック行列Ｈａは、行列変換により発生したサブブロックＳＢａを含む。サブブロックＳＢａは、パリティ情報生成のための式（１）を容易に計算するための前記した条件ｉ）及びｉｉ）を何れも満足させることが分かる。特徴的に、従来の方法は、サブブロックＳＢａの対角要素の下部Ｄａ＿ｄｏｗｎが何れも０である。
【００６１】
図５Ｂを参照するに、本発明によるパリティチェック行列Ｈｂは、行列変換により発生したサブブロックＳＢｂを含む。サブブロックＳＢａと同様に、サブブロックＳＢｂは、パリティ情報生成のための式（１）を容易に計算するための前記した条件ｉ）及びｉｉ）を何れも満足させる。しかし、従来の方法とは違って、サブブロックＳＢｂの対角要素の下部は０または１である。
【００６２】
結局、従来の方法と本発明は、行交換及び列交換を行うことにより図５Ａ及び図５Ｂに示した行列にパリティチェック行列を変換する。したがって、同じパリティチェック行列について従来の方法と本発明とを適用させれば、従来の方法によるサブブロックＳＢａよりは本発明によるサブブロックＳＢｂが更に大きくなる確率が高い。なぜなら、サブブロックＳＢａはサブブロックＳＢｂより‘対角要素の下部が何れも０である’という追加条件を満足せねばならないためである。
【００６３】
サブブロックＳＢａ、ＳＢｂの大きさが増加するほど、式（１）を解くのに必要な演算量は減るため、結局、本発明は式（１）を解くのに必要な演算量を減少させるという効果がある。
【００６４】
一方、本発明に係るパリティチェック行列変換方法はコンピュータプログラムで作成できる。前記プログラムを構成するコード及びコードセグメントは、当該分野のコンピュータプログラマーによって容易に推論されうる。また、前記プログラムは、コンピュータ可読情報保存媒体に保存され、コンピュータによって読まれ且つ実行されることによりパリティチェック行列の変換を具現する。前記情報保存媒体は、磁気記録媒体、光記録媒体、及びキャリアウェーブ媒体を含む。
【００６５】
以上、本発明について好ましい実施例を中心に説明した。当業者ならば、本発明が、本発明の本質的な特性から逸脱しない範囲で変形された形態に具現されうるということが理解できる。したがって、開示された実施例は、限定的な観点でなく説明的な観点から考慮されねばならない。本発明の範囲は、前記した説明でなく、特許請求の範囲に記載されており、それと同じ範囲内にあるあらゆる相違点は本発明に含まれたものと解釈されねばならない。
【産業上の利用可能性】
【００６６】
前記したように、本発明は、低密度パリティチェックコーディング、特に、低密度パリティチェック行列の変換方法に適用可能である。
【図面の簡単な説明】
【００６７】
【図１】従来の方法によってＨ行列をＨ’行列に変換する方法を示す時間フローチャートである。
【図２Ａ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｂ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｃ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｄ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｅ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｆ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｇ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図２Ｈ】図１の方法の各段階によって生成されるＨ行列を示す図である。
【図３】本発明の一実施例によって変換されたＨ行列を生成する方法を示す時間フローチャートである。
【図４Ａ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｂ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｃ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｄ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｅ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｆ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｇ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｈ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図４Ｉ】図３の方法の各段階で生成されるＨ行列を示す図である。
【図５Ａ】従来の方法により生成されたパリティチェック行列の構成を示す図である。
【図５Ｂ】本発明により生成されたパリティチェック行列の構成を示す図である。
【図１】
2005312034.tif 000003
【図２Ａ】
2005312034.tif 000004
【図２Ｂ】
2005312034.tif 000005
【図２Ｃ】
2005312034.tif 000006
【図２Ｄ】
2005312034.tif 000007
【図２Ｅ】
2005312034.tif 000008
【図２Ｆ】
2005312034.tif 000009
【図２Ｇ】
2005312034.tif 000010
【図２Ｈ】
2005312034.tif 000011
【図３】
2005312034.tif 000012
【図４Ａ】
2005312034.tif 000013
【図４Ｂ】
2005312034.tif 000014
【図４Ｃ】
2005312034.tif 000015
【図４Ｄ】
2005312034.tif 000016
【図４Ｅ】
2005312034.tif 000017
【図４Ｆ】
2005312034.tif 000018
【図４Ｇ】
2005312034.tif 000019
【図４Ｈ】
2005312034.tif 000020
【図４Ｉ】
2005312034.tif 000021
【図５Ａ】
2005312034.tif 000022
【図５Ｂ】
2005312034.tif 000023