(57)【要約】本発明のＬＤＰＣ符号用検査行列生成方法においては、たとえば、検査行列生成装置が、符号長，符号化率，ユークリット幾何符号を決定し、当該符号を並べ替えて基本行列を作成し、列の最大重みを選択するステップと、行の重みを連続する２種類に限定した状態で行と列の重みのアンサンブルを探索し、最適な行の重みのセットを決定するステップと、基本行列を底辺から順に削除するステップと、行の重みのセットを固定パラメータとして行と列の重みのアンサンブルを探索し、最適な列の重みのセットを決定するステップと、各重みのセットを固定パラメータとして行と列の重みの最適なアンサンブルを探索するステップと、最適なアンサンブルに基づいて行削除後の基本行列の重みをランダムに分割するステップと、を実行する。
2004006444.tif 000002
【特許請求の範囲】
【請求項１】
列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成するための検査行列生成方法において、
符号長と符号化率を決定する符号長／符号化率決定ステップと、
行および列の重みを決定し、「行と列の重みが一定」かつ「サイクル数が６以上」という条件を満たす基本行列を決定する基本行列決定ステップと、
条件「２＜列の重みの最大値≦基本行列における列内の１の数」を満たす列の重みの最大値を選択する最大重み選択ステップと、
行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索ステップと、
分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除ステップと、
前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索ステップと、
前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索ステップと、
最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項２】
ユークリット幾何符号を用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成するための検査行列生成方法において、
符号長と符号化率を決定する符号長／符号化率決定ステップと、
ベースとなるユークリット幾何符号を選択するユークリット幾何符号選択ステップと、
選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成する並べ替えステップと、
条件「２＜列の重みの最大値≦ユークリット幾何符号における列内の１の数」を満たす列の重みの最大値を選択する最大重み選択ステップと、
行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索ステップと、
分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除ステップと、
前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索ステップと、
前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索ステップと、
最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項３】
前記並べ替えステップで用いる特定の関係式は、
行列内の重みが列中の上部に配置されるように生成することを特徴とする請求の範囲第２項に記載の検査行列生成方法。
【請求項４】
前記ガウス近似法では、符号化率を固定した状態で、かつガウスノイズが最大になるように、行の重みと列の重みの最適なアンサンブル（ｔｈｒｅｓｈｏｌｄが最小となるアンサンブル）を１回の線形計画法で探索することを特徴とする請求の範囲第２項に記載の検査行列生成方法。
【請求項５】
前記第３の重み探索ステップでは、前記アンサンブルの重み配分を、重み単位の重み総数が整数で、かつ重み単位の重み総数の総和とユークリット幾何符号の「１」の総数とが等しくなるように調整し、
前記分割ステップでは、調整後のアンサンブルに基づいて分割処理を行うことを特徴とする請求の範囲第２項に記載の検査行列生成方法。
【請求項６】
前記分割ステップでは、基本のランダム系列のラテン方陣を作成し、当該ラテン方陣に基づいて、前記行削除後の基本行列における各行および各列から重み「１」を抽出することにより、各列および各行をランダムに分割することを特徴とする請求の範囲第２項に記載の検査行列生成方法。
【請求項７】
Ｃａｙｌａｙグラフを用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成するための検査行列生成方法において、
符号長と符号化率を決定する符号長／符号化率決定ステップと、
ベースとなるＣａｙｌａｙグラフの行および列の重みを決定して基本行列を作成するＣａｙｌａｙグラフ決定ステップと、
条件「２＜列の重みの最大値≦Ｃａｙｌａｙグラフにおける列内の１の数」を満たす列の重みの最大値を選択する最大重み選択ステップと、
行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索ステップと、
分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除ステップと、
前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索ステップと、
前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索ステップと、
最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項８】
前記ガウス近似法では、符号化率を固定した状態で、かつガウスノイズが最大になるように、行の重みと列の重みの最適なアンサンブル（ｔｈｒｅｓｈｏｌｄが最小となるアンサンブル）を１回の線形計画法で探索することを特徴とする請求の範囲第７項に記載の検査行列生成方法。
【請求項９】
前記第３の重み探索ステップでは、前記アンサンブルの重み配分を、重み単位の重み総数が整数で、かつ重み単位の重み総数の総和とＣａｙｌａｙグラフの「１」の総数とが等しくなるように調整し、
前記分割ステップでは、調整後のアンサンブルに基づいて分割処理を行うことを特徴とする請求の範囲第７項に記載の検査行列生成方法。
【請求項１０】
前記分割ステップでは、基本のランダム系列のラテン方陣を作成し、当該ラテン方陣に基づいて、前記行削除後の基本行列における各行および各列から重み「１」を抽出することにより、各列および各行をランダムに分割することを特徴とする請求の範囲第７項に記載の検査行列生成方法。
【請求項１１】
ユークリット幾何符号を用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成する検査行列生成装置において、
符号長と符号化率を決定する符号長／符号化率決定手段と、
ベースとなるユークリット幾何符号を選択するユークリット幾何符号選択手段と、
選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成する並べ替え手段と、
条件「２＜列の重みの最大値≦ユークリット幾何符号における列内の１の数」を満たす列の重みの最大値を選択する最大重み選択手段と、
行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索手段と、
分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除手段と、
前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索手段と、
前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索手段と、
最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割手段と、
を備えることを特徴とする検査行列生成装置。
【請求項１２】
Ｃａｙｌａｙグラフを用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成する検査行列生成装置において、
符号長と符号化率を決定する符号長／符号化率決定手段と、
ベースとなるＣａｙｌａｙグラフの行および列の重みを決定するＣａｙｌａｙグラフ決定手段と、
条件「２＜列の重みの最大値≦Ｃａｙｌａｙグラフにおける列内の１の数」を満たす列の重みの最大値を選択する最大重み選択手段と、
行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索手段と、
分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除手段と、
前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索手段と、
前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索手段と、
最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割手段と、
を備えることを特徴とする検査行列生成装置。
【発明の詳細な説明】
【技術分野】  この発明は、誤り訂正符号として低密度パリティ検査（ＬＤＰＣ：Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号を採用した場合における検査行列生成方法および検査行列生成装置に関するものであり、詳細には、確定的で特性が安定したＬＤＰＣ符号用検査行列を探索可能な検査行列生成方法および検査行列生成装置に関するものである。
【背景技術】  以下、従来のＬＤＰＣ符号用検査行列生成方法について説明する。第１３図は、ＬＤＰＣ符号化／復号システムを示す図である。第１３図において、１０１は符号化器であり、１０２は変調器であり、１０３は通信路であり、１０４は復調器であり、１０５は復号器である。ここでは、従来のＬＤＰＣ符号用検査行列生成方法を説明する前に、ＬＤＰＣ符号を使用した場合の符号化，復号の流れについて説明する。
まず、送信側の符号化器１０１では、後述する所定の方法で検査行列Ｈを生成する。そして、以下の条件に基づいて生成行列Ｇを求める。
Ｇ：ｋ×ｎ行列（ｋ：情報長，ｎ：符号語長）
ＧＨＴ＝０（Ｔは転置行列）
その後、符号化器１０１では、情報長ｋのメッセージ（ｍ１ｍ２…ｍｋ）を受け取り、上記生成行列Ｇを用いて符号語Ｃを生成する。
Ｃ＝（ｍ１ｍ２…ｍｋ）Ｇ
＝（ｃ１ｃ２…ｃｎ）    （ただし、Ｈ（ｃ１ｃ２…ｃｎ）Ｔ＝０）
そして、変調器１０２では、生成した符号語Ｃに対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭなどのデジタル変調を行い、送信する。
一方、受信側では、復調器１０４が、通信路１０３を介して受け取った変調信号に対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭなどのデジタル復調を行い、さらに、復号器１０５が、ＬＤＰＣ符号化された復調結果に対して、「ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム」による繰り返し復号を実施し、推定結果（もとのｍ１ｍ２…ｍｋに対応）を出力する。
ここで、従来のＬＤＰＣ符号用検査行列生成方法について具体的に説明する。ＬＤＰＣ符号用の検査行列としては、たとえば、ＬＤＰＣの発案者Ｇａｌｌａｇｅｒにより以下のような行列が提案されている（非特許文献１、第１４図参照）。
第１４図に示す行列は、「１」と「０」の２値の行列で、「１」の部分を塗りつぶしている。他の部分は全て「０」である。この行列は、１行の「１」の数（これを行の重みと表現する）が４で、１列の「１」の数（これを列の重みと表現する）が３であり、全ての列と行の重みが均一なため、これを一般に「Ｒｅｇｕｌａｒ−ＬＤＰＣ符号」と呼んでいる。また、Ｇａｌｌａｇｅｒの符号では、たとえば、第１４図に示すように、行列を３ブロックに分け、２ブロック目と３ブロック目に対してランダム置換を行っている。
しかしながら、このランダム置換には、所定のルールがないため、より特性の良好な符号を見つけるためには、計算機による時間のかかる探索を行わなければならなかった。
そこで、たとえば、計算機探索によらなくても確定的に行列を生成でき、比較的安定した良好な特性を示すＬＤＰＣ符号として、ユークリット幾何符号を用いる方法が、Ｙ．Ｋｏｕ等によって提案された（非特許文献２参照）。この方法では、規則的なｅｎｓｅｍｂｌｅ（アンサンブル）で構成された「Ｒｅｇｕｌａｒ−ＬＤＰＣ符号」について説明されている。
ここでは、有限幾何符号の一種であるユークリット幾何符号ＥＧ（２，２６）を用いてＬＤＰＣ符号の検査行列を生成する方法が提案されており、誤り率１０−４点において、シャノン限界から１．４５ｄＢに接近した特性を得ている。第１５図は、たとえば、ユークリット幾何符号ＥＧ（２，２２）の構成を示す図であり、行，列のそれぞれの重みが４，４の「Ｒｅｇｕｌａｒ−ＬＤＰＣ符号」構造をしている。
したがって、ユークリット幾何符号ＥＧ（ｍ，２ｓ）の場合、その特性は、以下のように規定される。
符号長：        ｎ＝２２ｓ−１
冗長ビット長：  ｎ−ｋ＝３ｓ−１
情報長：        ｋ＝２２ｓ−３ｓ
最小距離：      ｄｍｉｎ＝２ｓ＋１
密度：          ｒ＝２ｓ／（２２ｓ−１）
第１５図を見ても分かるように、ユークリット幾何符号は、各行の「１」の配置が行毎に巡回シフトした構造になっており、符号が容易にかつ確定的に構成できる特長がある。
Ｙ．Ｋｏｕらによる検査行列の生成方法では、さらに、上記ユークリット幾何符号に基づいて行と列の重みを変更し、行，列を必要に応じて拡張している。たとえば、ＥＧ（２，２２）の列の重みを１／２に分離する場合、Ｙ．Ｋｏｕらの論文では、１列内に４つある重みを１つ置きに２個づつ分離する。第１６図は、列の重みを４から２に規則的に分離した例を示す図である。
一方、上記「Ｒｅｇｕｌａｒ−ＬＤＰＣ符号」の特性よりも「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」の特性の方が良好であることが、Ｌｕｄｙ等により報告された（非特許文献３参照）。なお、上記「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」は、列と行の重みがそれぞれあるいはどちらか一方が均一でないＬＤＰＣ符号を表す。
そして、それは、Ｒｉｃｈａｒｄｓｏｎ等（非特許文献４参照）、あるいはＣｈｕｎｇ等（非特許文献５参照）によって理論的に解析された。
特に、Ｃｈｕｎｇ等は、繰り返し復号器における入力と出力の対数尤度比（ＬＬＲ）がガウス分布に近似できると仮定してＬＤＰＣ符号の「Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズム」を解析し、良好な行と列の重みのアンサンブルを求めている。
非特許文献１
Ｒ．Ｇ．Ｇａｌｌａｇｅｒ，Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ．Ｃａｍｂｒｉｄｇｅ，ＭＡ：ＭＩＴ  Ｐｒｅｓｓ，１９６３．
非特許文献２
Ｙ．Ｋｏｕ，Ｓ．Ｌｉｎ，ａｎｄ  Ｍ．Ｐ．Ｃ．Ｆｏｓｓｏｒｉｅｒ，”Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｆｉｎｉｔｅ  Ｇｅｏｍｅｔｒｉｅｓ：Ａ  Ｒｅｄｉｓｃｏｖｅｒｙ，”ＩＳＩＴ  ２０００，ｐｐ．２００，Ｓｏｒｒｅｎｔｏ，Ｉｔａｒｙ，Ｊｕｎｅ  ２５−３０，２０００．
非特許文献３
Ｍ．Ｇ．Ｌｕｂｙ，Ｍ．Ｍｉｔｚｅｎｍａｃｈｅｒ，Ｍ．Ａ．Ｓｈｏｋｒｏｌｌａｈｉ，ａｎｄ  Ｄ．Ａ．Ｓｐｉｅｌｍａｎ，“Ｉｍｐｒｏｖｅｄ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  Ｉｒｒｅｇｕｌａｒ  Ｇｒａｐｈｓ  ａｎｄ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ，”Ｐｒｏｃｅｅｄｉｎｇｓ  ｏｆ  １９９８  ＩＥＥＥ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｓｙｍｐｏｓｉｕｍ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ，ｐｐ．１７１，Ｃａｍｂｒｉｄｇｅ，Ｍａｓｓ．，Ａｕｇｕｓｔ  １６−２１，１９９８．
非特許文献４
Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ  ａｎｄ  Ｒ．Ｕｒｂａｎｋｅ，“Ｔｈｅ  ｃａｐａｃｉｔｙ  ｏｆ  ｌｏｗ−ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ−ｃｈｅｃｋ  ｃｏｄｅｓ  ｕｎｄｅｒ  ｍｅｓｓａｇｅ−ｐａｓｓｉｎｇ  ｄｅｃｏｄｉｎｇ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，ｖｏｌ．４７，Ｎｏ．２，ｐｐ．５９９−６１８，Ｆｅｂ．２００１．
非特許文献５
Ｓ．−Ｙ．Ｃｈｕｎｇ，Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ，ａｎｄ  Ｒ．Ｕｒｂａｎｋｅ，“Ａｎａｌｙｓｉｓ  ｏｆ  Ｓｕｍ−Ｐｒｏｄｕｃｔ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  ａ  Ｇａｕｓｓｉａｎ  Ａｐｐｒｏｘｉｍａｔｉｏｎ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，ｖｏｌ．４７，Ｎｏ．２，ｐｐ．６５７−６７０，Ｆｅｂ．２００１．
しかしながら、たとえば、上記Ｃｈｕｎｇ等による従来のＬＤＰＣ符号用検査行列生成方法は、行内の「１」の点の数（後述するバリアブルノードの次数配分に相当）と、列内の「１」の点の数（後述するチェックノードの次数配分に相当）と、の両方を変数として、下記の（１）式（ｒａｔｅ：符号化率）が最大となるバリアブルノードの次数配分およびチェックノードの次数配分を求めている。すなわち、ＳＮＲ（Ｓｉｇｎａｌ  ｔｏ  Ｎｏｉｓｅ  Ｒａｔｉｏ）が最小となるアンサンブルを線形計画法により探索している。
2004006444.tif 000003
そのため、上記「ｒａｔｅ」の最大値により得られる検査行列が流動的になり、特性が安定しない、という問題があった。また、従来のＬＤＰＣ符号用検査行列生成方法は、バリアブルノードの次数配分の導出とチェックノードの次数配分の導出とを所定回数にわたって繰り返し行っているため、探索処理にある程度の時間を要する、という問題もあった。
本発明は、上記に鑑みてなされたものであって、確定的で特性が安定し、かつ任意のアンサンブルに対応したＬＤＰＣ符号用の検査行列を容易に探索可能で、さらに、性能の良好な検査行列生成方法および検査行列生成装置を提供することを目的とする。
【発明の開示】
上述した課題を解決し、目的を達成するために、本発明にかかる検査行列生成方法にあっては、ユークリット幾何符号を用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成するために、符号長と符号化率を決定する符号長／符号化率決定ステップと、ベースとなるユークリット幾何符号を選択するユークリット幾何符号選択ステップと、選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成する並べ替えステップと、条件「２＜列の重みの最大値≦ユークリット幾何符号における列内の１の数」を満たす列の重みの最大値を選択する最大重み選択ステップと、行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索ステップと、分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除ステップと、前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索ステップと、前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索ステップと、最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割ステップと、を含むことを特徴とする。
つぎの発明にかかる検査行列生成方法において、前記並べ替えステップで用いる特定の関係式は、行列内の重みが列中の上部に配置されるように生成することを特徴とする。
つぎの発明にかかる検査行列生成方法にあっては、Ｃａｙｌａｙグラフを用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成するために、符号長と符号化率を決定する符号長／符号化率決定ステップと、ベースとなるＣａｙｌａｙグラフの行および列の重みを決定して基本行列を作成するＣａｙｌａｙグラフ決定ステップと、条件「２＜列の重みの最大値≦Ｃａｙｌａｙグラフにおける列内の１の数」を満たす列の重みの最大値を選択する最大重み選択ステップと、行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索ステップと、分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除ステップと、前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索ステップと、前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索ステップと、最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割ステップと、を含むことを特徴とする。
つぎの発明にかかる検査行列生成方法において、前記ガウス近似法では、符号化率を固定した状態で、かつガウスノイズが最大になるように、行の重みと列の重みの最適なアンサンブル（ｔｈｒｅｓｈｏｌｄが最小となるアンサンブル）を１回の線形計画法で探索することを特徴とする。
つぎの発明にかかる検査行列生成方法において、前記第３の重み探索ステップでは、前記アンサンブルの重み配分を、重み単位の重み総数が整数で、かつ重み単位の重み総数の総和とユークリット幾何符号の「１」の総数とが等しくなるように調整し、前記分割ステップでは、調整後のアンサンブルに基づいて分割処理を行うことを特徴とする。
つぎの発明にかかる検査行列生成方法において、前記分割ステップでは、基本のランダム系列のラテン方陣を作成し、当該ラテン方陣に基づいて、前記行削除後の基本行列における各行および各列から重み「１」を抽出することにより、各列および各行をランダムに分割することを特徴とする。
つぎの発明にかかる検査行列生成装置にあっては、ユークリット幾何符号を用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成する構成として、符号長と符号化率を決定する符号長／符号化率決定手段と、ベースとなるユークリット幾何符号を選択するユークリット幾何符号選択手段と、選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成する並べ替え手段と、条件「２＜列の重みの最大値≦ユークリット幾何符号における列内の１の数」を満たす列の重みの最大値を選択する最大重み選択手段と、行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索手段と、分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除手段と、前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索手段と、前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索手段と、最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割手段と、を備えることを特徴とする。
つぎの発明にかかる検査行列生成装置にあっては、Ｃａｙｌａｙグラフを用いて、列と行の重みまたはどちらか一方が均一でない低密度パリティ検査符号の検査行列を生成する構成として、符号長と符号化率を決定する符号長／符号化率決定手段と、ベースとなるＣａｙｌａｙグラフの行および列の重みを決定するＣａｙｌａｙグラフ決定手段と、条件「２＜列の重みの最大値≦Ｃａｙｌａｙグラフにおける列内の１の数」を満たす列の重みの最大値を選択する最大重み選択手段と、行の重みの数を連続する２種類に限定した状態で、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な行の重みのセットを決定する第１の重み探索手段と、分割後の行数を考慮して、前記基本行列を底辺から順に削除する行削除手段と、前記行の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、暫定的に、低密度パリティ検査符号の行の重みと列の重みのアンサンブルを探索し、その後、最適な列の重みのセットを決定する第２の重み探索手段と、前記行の重みのセットおよび前記列の重みのセットを固定パラメータとして、ガウス近似法による最適化を用いて、低密度パリティ検査符号の行の重みと列の重みの最適なアンサンブルを探索する第３の重み探索手段と、最終的なアンサンブルに基づいて前記行削除後の基本行列の行および列の重みを所定の手順でランダムに分割する分割手段と、を備えることを特徴とする。
【図面の簡単な説明】  第１図は、本発明にかかるＬＤＰＣ符号用検査行列生成方法を示すフローチャートであり、第２図は、選択されたユークリット幾何符号ＥＧ（２，２２）のマトリクスを示す図であり、第３図は、並べ替え後のマトリクス（基本行列）を示す図であり、第４図は、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブル（暫定）を示す図であり、第５図は、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブル（暫定）を示す図であり、第６図は、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルを示す図であり、第７図は、重み配分調整用テーブルの一具体例を示す図であり、第８図は、第６図に示すアンサンブルを調整後の、最終的な生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルを示す図であり、第９図は、従来の論文における分割手順を示す図であり、第１０図は、基本のランダム系列Ｃ（ｉ）と基本のランダム系列の置換パターンＬＢｊ（ｉ）を示す図であり、第１１図は、ラテン方陣行列Ｌｊｑ（ｉ）を示す図であり、第１２図は、Ｅｂ／Ｎｏ（情報１ビットあたりの信号電力対ノイズ電力比）と誤り率特性（ＢＥＲ）との関係を示す図であり、第１３図は、ＬＤＰＣ符号化／復号システムを示す図であり、第１４図は、従来のＬＤＰＣ符号用の検査行列を示す図であり、第１５図は、ユークリット幾何符号ＥＧ（２，２２）の構成を示す図であり、第１６図は、列の重みを４から２に規則的に分離した例を示す図である。
【発明を実施するための最良の形態】  本発明をより詳細に説術するために、添付の図面に従ってこれを説明する。
第１図は、本発明にかかるＬＤＰＣ符号用検査行列生成方法を示すフローチャートである。なお、本実施の形態におけるＬＤＰＣ符号用検査行列生成方法は、たとえば、設定されるパラメータに応じて通信装置内で実行する構成としてもよいし、通信装置外部の他の制御装置（計算機等）で実行することとしてもよい。本実施の形態におけるＬＤＰＣ符号用検査行列生成方法が通信装置外部で実行される場合は、生成済みのＬＤＰＣ符号用検査行列が通信装置に格納される。以降の実施の形態では、説明の便宜上、通信装置内で上記方法を実行する場合について説明する。
まず、本実施の形態のＬＤＰＣ符号用検査行列生成方法を説明する前に、本実施の形態のＬＤＰＣ符号用検査行列生成方法を実現可能な符号化器および復号器の位置付け、および「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の従来の検査行列生成方法について説明する。なお、ＬＤＰＣ符号化／復号システムの構成については、先に説明した第１３図と同様である。
送信側の符号化器１０１では、後述する本実施の形態のＬＤＰＣ符号用検査行列生成方法で検査行列Ｈを生成する。そして、以下の条件に基づいて生成行列Ｇを求める。
Ｇ：ｋ×ｎ行列（ｋ：情報長，ｎ：符号語長）
ＧＨＴ＝０（Ｔは転置行列）
その後、符号化器１０１では、情報長ｋのメッセージ（ｍ１ｍ２…ｍｋ）を受け取り、上記生成行列Ｇを用いて符号語Ｃを生成する。
Ｃ＝（ｍ１ｍ２…ｍｋ）Ｇ
＝（ｃ１ｃ２…ｃｎ）    （ただし、Ｈ（ｃ１ｃ２…ｃｎ）Ｔ＝０）
そして、変調器１０２では、生成した符号語Ｃに対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭなどのデジタル変調を行い、送信する。
一方、受信側では、復調器１０４が、通信路１０３を介して受け取った変調信号に対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭなどのデジタル復調を行い、さらに、復号器１０５が、ＬＤＰＣ符号化された復調結果に対して、「ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム」による繰り返し復号を実施し、推定結果（もとのｍ１ｍ２…ｍｋに対応）を出力する。
つぎに、Ｃｈｕｎｇ等（Ｓ．−Ｙ．Ｃｈｕｎｇ，Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ，ａｎｄ  Ｒ．Ｕｒｂａｎｋｅ，”Ａｎａｌｙｓｉｓ  ｏｆ  Ｓｕｍ−Ｐｒｏｄｕｃｔ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ  Ｕｓｉｎｇ  ａ  Ｇａｕｓｓｉａｎ  Ａｐｐｒｏｘｉｍａｔｉｏｎ，”ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ，ｖｏｌ．４７，Ｎｏ．２，ｐｐ．６５７−６７０，Ｆｅｂ．２００１．）によって理論的に解析された、「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の従来の検査行列生成方法について詳細に説明する。ここでは、繰り返し復号器における入力と出力の対数尤度比（ＬＬＲ）がガウス分布に近似できると仮定してＬＤＰＣ符号の「Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズム」を解析し、良好な行と列の重みのアンサンブルを求めている。
なお、上記論文に記述されたＬＤＰＣ符号用検査行列生成方法であるガウス近似法（Ｇａｕｓｓｉａｎ  Ａｐｐｒｏｘｉｍａｔｉｏｎ）では、前提として、検査行列における行内の「１」の点をバリアブルノードと定義し、列内の「１」の点をチェックノードと定義する。
まず、チェックノードからバリアブルノードへのＬＬＲメッセージ伝搬を解析する。０＜ｓ＜∞と０≦ｔ＜∞という条件において、以下の関数（２）式を定義する。なお、ｓ＝ｍｕ０はｕ０の平均値であり、ｕ０は分散値σｎ２のガウスノイズを含む伝送路を経由して受信した信号の対数尤度比（ＬＬＲ）であり、ｔは所定の繰り返しの時点におけるチェックノードのＬＬＲ出力値のアンサンブル平均である。
2004006444.tif 000004
なお、上記λ（ｘ）およびρ（ｘ）は、それぞれバリアブルノードおよびチェックノードの次数配分（バリアブルノードとチェックノードの各１行，各１列内の「１」の数を次数と表現する）の生成関数を表し、（３）式および（４）式のように表すことができる。また、λｉとρｉは、それぞれ次数ｉのバリアブルノードとチェックノードに属するエッジの比率を表す。また、ｄｌは最大バリアブルノードの次数であり、ｄｒは最大チェックノードの次数である。
2004006444.tif 000005
ただし、φ（ｘ）は下記（５）式のように定義する。
2004006444.tif 000006
そして、（２）式は、等価的に下記（６）式と表すことができる。
2004006444.tif 000007
なお、ｔｌはｌ番目の繰り返し時点におけるチェックノードのＬＬＲ出力値のアンサンブル平均である。
ここで、誤りが０となりうるＳＮＲの限界（ｔｈｒｅｓｈｏｌｄ）を求めるための条件は、ｌ→∞のときにｔｌ（ｓ）→∞（Ｒ＋と表現する）となることであり、この条件を満たすためには、以下の条件（７）式を満たす必要がある。
2004006444.tif 000008
つぎに、バリアブルノードからチェックノードへのＬＬＲメッセージ伝搬を解析する。０＜ｓ＜∞と０＜ｒ≦１という条件において、以下の関数（８）式を定義する。なお、ｒの初期値ｒ０はφ（ｓ）である。
2004006444.tif 000009
そして、（８）式は、等価的に下記（９）式と表すことができる。
2004006444.tif 000010
ここで、誤りが０となりうるＳＮＲの限界（ｔｈｒｅｓｈｏｌｄ）を求めるための条件は、ｒｌ（ｓ）→０となることであり、この条件を満たすためには、以下の条件（１０）式を満たす必要がある。
2004006444.tif 000011
さらに、上記Ｃｈｕｎｇ等の論文では、上記式を用いて以下の手順でバリアブルノードとチェックノードの最適な次数を探索している（ガウス近似法）。
（１）生成関数λ（ｘ）とガウスノイズσｎが与えられていると仮定し、生成関数ρ（ｘ）を変数として、前述した（１）式が最大となる点を探索する。なお、この探索における拘束条件は、ρ（１）＝１と正規化することと、上記（７）式を満たすことである。
（２）生成関数ρ（ｘ）とガウスノイズσｎが与えられていると仮定し（たとえば、（１）の結果より得られる値）、生成関数λ（ｘ）を変数として、（１）式が最大となる点を探索する。なお、この探索における拘束条件は、λ（１）＝１と正規化することと、上記（１０）式を満たすことである。
（３）最大「ｒａｔｅ」を求めるために、上記（１）と上記（２）を繰り返し実行し、生成関数λ（ｘ）と生成関数ρ（ｘ）のより良好なアンサンブルを線形計画法で探索する。
（４）最後に、ガウスノイズσｎより信号電力を１と正規化して、ＳＮＲの限界（ｔｈｒｅｓｈｏｌｄ）を求める（下記（１１）式参照）。
2004006444.tif 000012
しかしながら、上記Ｃｈｕｎｇ等の論文では、「ｒａｔｅ（符号化率）」の最大値により得られる検査行列が流動的になり、設計時の仕様として固定されるｒａｔｅが変動してしまう、という問題があった。また、上記Ｃｈｕｎｇ等の論文では、バリアブルノードの次数配分の導出とチェックノードの次数配分の導出とを所定回数にわたって繰り返し行っているため、探索処理にある程度の時間を要する、という問題や、任意のアンサンブル，任意の符号長，任意の符号化率に容易に対応することができない、という問題もあった。
そこで、本実施の形態においては、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に探索する方法について説明する（第１図参照）。具体的にいうと、ここでは、ユークリット幾何符号における１行または１列の「１」の配置を分割および削除することにより、「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を生成する。第１図は、実施の形態１のＬＤＰＣ符号用検査行列生成方法を示す図である。
本実施の形態のＬＤＰＣ符号用検査行列生成方法では、まず、符号長Ｎと符号化率ｒａｔｅを決定する（ステップＳ１）。これにより、検査行列のサイズがＮ×Ｍに確定する。なお、ＭはＮ×（１−ｒａｔｅ）で表すことができる。したがって、たとえば、Ｎ＝６０００，ｒａｔｅ＝０．５の場合、ＭはＭ＝６０００×０．５＝３０００となる。
つぎに、「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列のベースとなるユークリット幾何符号ＥＧ（２，２ｓ）を選択する（ステップＳ２）。ここでは、行の重みと列の重みがそれぞれ２ｓとなる。
つぎに、選択したユークリット幾何符号ＥＧ（２，２ｓ）を、列内の１の位置が列中のできるだけ上部にくるように、以下の手順で並べ替える（ステップＳ３）。まず、この並べ替え手順を一般的に表現すると、ｈｋ（Ｘ）∈ガロア体ＧＦ（２２ｓ），ｋ＝｛１，２，…，４×（２２ｓ−１）｝の場合、下記（１２）式のように表現できる。
2004006444.tif 000013
なお、ｉ＝１〜２２ｓ−１とする。また、（１２）式の（・）内の多項式は、ユークリット幾何符号ＥＧ（２，２ｓ）の最初の行を表現した式を表す。
そして、ｉ＝１〜２２ｓ−１，ｊ＝１〜ｉ−１までの間に、ｈｉ（Ｘ）＝ｈｊ（Ｘ）が存在する場合は、ｈｉ（Ｘ）を削除する。この並べ替え処理により、後述する行の削除処理（ステップＳ６）を行う場合に、できるだけ重みの大きい列を残すことができ、かつ列内の重みのバリエーションをできるだけ少なくすることができる。
具体例として、たとえば、ｓ＝２とした場合、すなわち、ユークリット幾何符号ＥＧ（２，２２）を選択した場合、上記並べ替え手順を実施すると、第２図のマトリクスが第３図のマトリクスのように並べ替えられる。第２図は、ステップＳ２にて選択されたユークリット幾何符号ＥＧ（２，２２）のマトリクスを示す図（空白は０を表す）であり、第３図は、並べ替え後のマトリクス（基本行列）を示す図である。
つぎに、列の最大重みγｌ（２＜γｌ≦２ｓ）を選択する（ステップＳ４）。ＬＤＰＣ符号を用いた符号化／復号においては、一般的に、２部グラフ上に「サイクル４」および「サイクル６」が少ないほど良好な特性を得ることができる。したがって、ＬＤＰＣ符号としては、「サイクル４」や「サイクル６」といった少ないサイクルの発生を抑制する構造が望ましい。ユークリット幾何符号には、すでに「サイクル４」が存在しないので、「サイクル６」を削減することによって、復号特性の向上を図る。たとえば、ユークリット幾何符号ＥＧ（２，２５）の場合には、重みが１２程度のときに「サイクル６」の数が減少し、よい特性を示すことが一般に知られているので、ここでは、γｌ＝１２を選択する。なお、ここでは、γｌ＝１２を選択することとしたが、これに限らず、上記条件を満たしていれば、これ以外の数を選択してもよい。
つぎに、ガウス近似法による最適化を用いて、暫定的に、要求された符号化率に基づく「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」のアンサンブルを求める（ステップＳ５）。なお、行の重み配分の生成関数ρ（ｘ）はρ（ｘ）＝ρｊｘｊ−１＋（１−ρｊ）ｘｊとする。ただし、ｊはｊ≧２の整数である。
そして、下記の（１３）式を満たすパラメータセット｛μ１，μ２｝を選択する（ステップＳ５）。なお、２≦μｉ≦２ｓ，ｉ∈｛１，２｝である。
2004006444.tif 000014
ただし、ｂｉ，ｉは非負の整数であり、μｉは行の重みを表し、ρ＿μｉ´は「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」にあわせて調整した重みμｉに属するエッジの比率を表す。ここでは、パラメータセットとして、μ１＝８，μ２＝９を選択する。第４図は、γｌ＝ｄｌ＝１２，ｒａｔｅ＝０．５の場合の、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブル（暫定）を示す図である。ｘは重みを表し、λｘおよびρｘはそれぞれバリアブルノードとチェックノードの重み配分を表す。また、表中σＧＡはガウス近似法により導出した「ｔｈｒｅｓｈｏｌ」時のノイズ分散値を表し、ＳＮＲｎｏｒｍ（ＧＡ）はガウス近似法により導出した「ｔｈｒｅｓｈｏｌ」時のＳＮＲとシャノン限界のＳＮＲとの差分を表す。
ここで、バリアブルノードの次数配分の生成関数λ（ｘ）とチェックノードの次数配分の生成関数ρ（ｘ）のアンサンブルを探索するための本実施の形態のガウス近似法の実行手順について説明する。
（１）符号化率「ｒａｔｅ」を固定する（ステップＳ１）。
（２）生成関数λ（ｘ）と生成関数ρ（ｘ）を同時に変数として扱い、ガウスノイズσｎが最大になるように、線形計画法で最適な生成関数λ（ｘ）と生成関数ρ（ｘ）を探索する。この探索における拘束条件は、λ（１）＝１，ρ（１）＝１と正規化し、さらに上記（１０）式を満たすことである。
このように、本実施の形態では、上記（９）式と上記（１０）式を満たす生成関数λ（ｘ）と生成関数ρ（ｘ）を１回の線形計画法で求めることとしたため、上記論文（ｃｈｕｎｇ等）のように、生成関数λ（ｘ）の導出と生成関数ρ（ｘ）の導出を繰り返し実行し、双方の最適値を求める方法よりも、容易かつ短時間に、確定的でかつ特性が安定したアンサンブルを生成できる。
つぎに、上記ステップＳ５で求めたｂ１，ｂ２，μ１，μ２にしたがって後述する行の分割処理（ステップＳ８）を実行した後の行数をＭ´とした場合、下記（１４）式に示す行数を、上記第３図に示す基本行列の底辺から順に削除する（ステップＳ６）。その結果、行削除後の行列は、列の重みのセットが｛ｄ１，ｄ２，…ｄα｝となる。
2004006444.tif 000015
つぎに、上記本実施の形態のガウス近似法による最適化を用いて、さらに上記で求めたμ１，μ２，ρ＿μ１´，ρ＿μ２´を固定のパラメータとして、暫定的に、要求された符号化率に基づく「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」のアンサンブルを求める（ステップＳ７）。そして、列の重みｘの数が１よりも小さくなった特定の列に関しては、その重みを候補から削除する。第５図は、γｌ＝ｄｌ＝１２，ｒａｔｅ＝０．５の場合の、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブル（暫定）を示す図である。
つぎに、上記で求めた重み配分を満たし、かつ下記の（１５）式を満たす、列の重み候補のセット｛γ１，γ２，…γｌ｝を選択する（ステップＳ７）。なお、γｌ≦２ｓである。そして、下記の（１５）式を満たさない列の重みが存在する場合には、その列の重みを候補から削除する。
2004006444.tif 000016
なお、各ａは、列の重みｄ＿β（β＝｛１，２，…α｝）を構成するための｛γ１，γ２，…γｌ｝に対する非負の整数となる係数を表し、ｉ，ｊは正の整数であり、γｉは列の重みを表し、γｌは列の最大重みを表す。
つぎに、上記本実施の形態のガウス近似法による最適化を用いて、さらに上記で求めたμ１，μ２，ρ＿μ１´，ρ＿μ２´と｛γ１，γ２，…γｌ｝を固定パラメータとして、要求された符号化率に基づく「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」のアンサンブルを求める（ステップＳ７）。第６図は、γｌ＝ｄｌ＝１２，ｒａｔｅ＝０．５の場合の、重み配分後の生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルを示す図である。
つぎに、分割処理を行う前に、第６図に示す生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルの重み配分を以下の手順で調整する（ステップＳ７）。なお、ここでは、第６図の重み配分を調整したものではないが、説明の便宜上、第７図の例を用いて上記調整手順について説明する。第７図は、重み配分調整用テーブルの一具体例を示す図である。
（１）ガウス近似法で求めた生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルをテーブルの２列目と３列目に設定する。
（２）重み配分λｘおよびρｘ（３列目）と、ユークリット幾何符号ＥＧ（２，２５）における全行列の「１」の総数ＴＰ＝２６６８８と、を乗算し、重み単位の重み総数を求め、さらに、当該重み単位の重み総数とその総和を４列目に設定する。
（３）重み単位の重み総数（４列目）を対応する重みｘで割り、重み単位の総列数を求め、それを５列目に設定する。
（４）重み単位の総列数が小数点以下を含む場合、丸め処理（四捨五入，切上げ，切捨て等）を行い、その結果を６列目に設定する。
（５）丸め処理後の重み単位の総列数（６列目）と対応する重みｘとを乗算し、丸め処理後の重み単位の重み総数を求め、それを７列目に設定する。そして、各重み総数の総和（７列目の合計の行）が行列内の「１」の総数（ＴＰ＝２６６８８）と等しいかどうかを確認する。
（６）行列内の「１」の総数に等しくない場合、丸め処理後の重み単位の重み総数（７列目）を整数単位で調整し、その結果を８列目に設定する。この場合、８列目の総和が、行列内の「１」の総数（ＴＰ＝２６６８８）に等しくなるように調整する。
（７）調整後の重み単位の重み総数（８列目）を対応する重みｘで割り、調整後の重み単位の総列数を求め、それを９列目に設定する。調整後の各重みの配分（１１列目）は、可能な限りガウス近似法で求めた値（３列目）に近い値にする。
なお、上記調整手順は、一般的に、下記の（１６），（１７），（１８）式のように表現することができる。まず、重みγｉに属する列の数ｎ＿γｉと、重みμｉに属する行の数ｎ＿μｉと、を以下の（１６）式で求める。なお、ｗｔは行を削除した後の行列の重みの総和を示す。
2004006444.tif 000017
そして、以下の条件（（１７），（１８）式）の下で、重みγｉに属する最終的な列の数ｎ＿γｉ´と、重みμｉに属する最終的な行の数ｎ＿μｉ´を求める。なお、λ＿γｉ´は行の削除後の行列にあわせて調整した重みγｉに属する列の比率を表し、ρ＿μｉ´は行の削除後の行列にあわせて調整した重みμｉに属する行の比率を表す。
2004006444.tif 000018
第８図は、上記の手順で第６図に示すアンサンブルを調整した場合の、ステップＳ７における最終的な生成関数λ（ｘ）と生成関数ρ（ｘ）のアンサンブルを示す図である。
最後に、ユークリット幾何符号における１行あるいは１列の分割手順（ステップＳ８）について説明する。たとえば、分割手順に関して、Ｙ．Ｋｏｕ等の論文では、規則的に分割する方法を提示している。第９図は、上記論文における分割手順を示す図である。まず、第９図に示すように行列のナンバリングを行う。ここでは、列番号を左端から順に１，２，３，…とし、行番号を上から順に１，２，３，…とする。そして、たとえば、３２点×１列を８点×４列に分割する場合、下記（１９）式にしたがって規則的に分割する。
2004006444.tif 000019
なお、ｍ＝１，２，３，４とし、ｎ＝０，１，２，３，４，５，６，７とし、ｌはＥＧ（２，２５）の列番号を表す。また、Ｂ１（ｘ）はＥＧ（２，２５）のｌ列目の「１」の位置を表し、Ｓｍ（ｎ）は分割後の行列のｍ列目の「１」の位置を表す。
具体的にいうと、ＥＧ（２，２５）における１列中の「１」の位置を示す行番号は、
2004006444.tif 000020
となり、その結果、分割後の行列における１〜４列目の「１」の位置を示す行番号は、Ｂｌ（ｘ）から「１」の番号が規則的に抽出され、
2004006444.tif 000021
となる。すなわち、３２点×１列が８点×４列に分割される。
一方、本発明におけるユークリット幾何符号の分割処理は、上記のように規則的に分割するのではなく、Ｂｌ（ｘ）から「１」の番号をランダムに抽出する（後述するランダム分割の具体例を参照）。なお、この抽出処理は、ランダム性が保持されるのであればどのような方法を用いてもよい。
これにより、分割後の行列のｍ列目の「１」の位置の一例をＲｍ（ｎ）とした場合、Ｒｍ（ｎ）は、たとえば、
2004006444.tif 000022
となる。
ここで、上記ランダム分割の一例、すなわち、上記「乱数系列のラテン方陣を用いた分割方法」を詳細に説明する。ここでは、ランダム分割を行う場合のランダム系列を容易かつ確定的に生成する。この方法による利点は、送信側と受信側が同じランダム系列を生成できることにある。これは、現実のシステムではきわめて重要となる。また、符号特性の条件が正確に規定できる、という利点もある。
（１）基本のランダム系列を作成する。
以下に、ランダム系列作成の一例を記述する。ここでは、説明の便宜上、ユークリット幾何符号ＥＧ（２，２５）を用いる。ユークリット幾何符号ＥＧ（２，２５）の場合、１行に存在する「１」の数は２５＝３２個である。
ＰをＰ≧２ｓを満たす最小の素数とした場合、たとえば、２５のときはＰ＝３７となる。ここで、系列長Ｐ−５＝３２の基本のランダム系列Ｃ（ｉ）を（２０）式にしたがって作成する。
2004006444.tif 000023
ただし、ｉ＝０，１，…，Ｐ−２とし、Ｇ０はガロア体ＧＦ（Ｐ）の原始元である。その結果、Ｃ（ｉ）は、
2004006444.tif 000024
2004006444.tif 000025
となる。
（２）系列長が２５＝３２となるように、３２より大きい数を削除する。
2004006444.tif 000026
（３）基本のランダム系列を一定間隔で読み出すためにスキップ間隔Ｓ（ｊ）を以下の（２１）式のように定義する。
2004006444.tif 000027
（４）以下の（２２）式で置換パターンＬＢｊ（ｉ）を作成する。
2004006444.tif 000028
なお、ＬＢｊ（ｉ）も２ｓより大きい数字は削除する。第１０図は、基本のランダム系列Ｃ（ｉ）と基本のランダム系列の置換パターンＬＢｊ（ｉ）を示す図である。
（５）ｑ列ｉ行でｊ番目のラテン方陣行列Ｌｊｑ（ｉ）を以下の（２３）式で算出することによって、分割処理を行う。このとき、ステップＳ６の削除処理によって、列の重みｄ＿βがｄ＿β＜２ｓの場合には、ｄ＿β以上の数字をＬｊｑ（ｉ）の要素から間引く。
2004006444.tif 000029
第１１図は、ラテン方陣行列Ｌｊｑ（ｉ）を示す図である。このラテン方陣行列Ｌｊｑ（ｉ）は、拡張する対象の行列のｊ×３２＋ｑ列目の分割パターンを決める。たとえば、削除により短縮されたＥＧ（２，２５）の６７０列目ｇ６７０（ｌ）を
2004006444.tif 000030
とし、これを重み６の５列と重み２の１列に分割する。対応するラテン方陣Ｌｊｑ（ｉ）は２０＊３２＋３０＝６７０であるため、
2004006444.tif 000031
となる。結果として、分割パターンは以下のようになる。
2004006444.tif 000032
以下では、上記で説明したＬＤＰＣ符号の特性を比較する。第１２図は、Ｅｂ／Ｎｏ（情報１ビットあたりの信号電力対ノイズ電力比）と誤り率特性（ＢＥＲ）との関係を示す図である。なお、復号法は「Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズム」である。この特性は、第８図に示すアンサンブルを使用したものであり、Ｙ．Ｋｏｕ等の論文のように規則的に分割した場合と、乱数系列のラテン方陣による分割処理を実行した場合と、の特性比較を示す。
第１２図からわかるように、本実施の形態の分割方法を用いた場合には、シャノン限界に１．２ｄＢ程度まで近づいているのがわかる。このように、Ｙ．Ｋｏｕ等の論文のような規則的な分割では、「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」であっても大幅な改善は見込めないが、本実施の形態のランダム分割を実施すると、ループの発生する確率が大幅に減るので性能が画期的に改善される。
このように、本実施の形態においては、まず、符号長と符号化率を決定し、つぎに、ベースとなるユークリット幾何符号を選択し、つぎに、選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成し、つぎに、条件「２＜γｌ≦２ｓ」を満たす列の重みの最大値を選択し、つぎに、行の重みの数を連続する２種類に限定した状態で、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な行の重みのセットを決定し、つぎに、分割後の行数を考慮して基本行列を底辺から順に削除し、つぎに、行の重みのセットを固定パラメータとして、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な列の重みのセットを決定し、つぎに、行の重みのセットおよび列の重みのセットを固定パラメータとして、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号の最適なアンサンブルを探索し、最後に、このアンサンブルに基づいて行削除後の基本行列の重みを所定の手順でランダムに分割する。これにより、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に生成できる。
なお、本実施の形態においては、「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を生成するために、ユークリット幾何符号を用いたが、これに限らず、たとえば、Ｃａｙｌｅｙグラフを用いて、確定的な「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」を構成することとしてもよい。この場合、先に説明した、「ベースとなるユークリット幾何符号を選択する処理（ステップＳ２）」、「選択したユークリット幾何符号を（１２）式に基づいて並べ替えて基本行列を作成する処理（ステップＳ３）」、に置き換えて、「ベースとなるＣａｙｌａｙグラフの行および列の重みを決定して基本行列を作成する処理」、を実行する。これ以外の処理については、上記第１図の処理と同様である。
したがって、Ｃａｙｌｅｙグラフを用いた場合であっても、上記と同様の手順を実施することによって、同様の効果を得ることができる。なお、Ｃａｙｌｅｙグラフには「Ｊ．Ｒｏｓｅｎｔｈａｌ，Ｐ．Ｏ．Ｖｏｎｔｏｂｅｌ，”Ｃｏｎｓｔｒｕｃｔｉｏｎ  ｏｆ  ＬＤＰＣ  ｃｏｄｅｓ  ｕｓｉｎｇ  Ｒａｍａｎｕｊａｎ  ｇｒａｐｈｓ  ａｎｄ  ｉｄｅａｓ  ｆｒｏｍ  Ｍａｒｇｕｌｉｓ，”ｉｎ  Ｐｒｏｃ．ｏｆ  ｔｈｅ  ３８−ｔｈ  Ａｌｌｅｒｔｏｎ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎ，Ｃｏｎｔｒｏｌ，Ｃｏｍｐｕｔｉｎｇ，２０００，ｐｐ．２４８−２５７」に示されているように、Ｍａｇｕｌｉｓの構成法やＲａｍａｎｕｊａｎグラフの構成法がある。
また、上記では、基本行列にユークリット幾何符号またはＣａｙｌｅｙグラフを用いることとしたが、これに限らず、「行と列の重みが一定」かつ「サイクル数が６以上」という条件を満たす行列であれば、たとえば、射影幾何符号等の、ユークリット幾何符号以外の行列を用いることとしてもよい。
以上、説明したとおり、本発明によれば、まず、符号長と符号化率を決定し、つぎに、ベースとなるユークリット幾何符号を選択し、つぎに、選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成し、つぎに、列の重みの最大値を選択し、つぎに、行の重みの数を連続する２種類に限定した状態で、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な行の重みのセットを決定し、つぎに、分割後の行数を考慮して基本行列を底辺から順に削除し、つぎに、行の重みのセットを固定パラメータとして、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な列の重みのセットを決定し、つぎに、行の重みのセットおよび列の重みのセットを固定パラメータとして、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号の最適なアンサンブルを探索し、最後に、このアンサンブルに基づいて行削除後の基本行列の重みを所定の手順でランダムに分割する。これにより、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に生成できる、という効果を奏する。
つぎの発明によれば、行列内の重みが列中の上部に配置されるように並べ替えることとした。これにより、行の削除処理を行う場合に、重みの大きい列を残すことができ、かつ列内の重みのバリエーションを少なくすることができる、という効果を奏する。
つぎの発明によれば、まず、符号長と符号化率を決定し、つぎに、ベースとなるＣａｙｌａｙグラフの行および列の重みを決定して基本行列を作成し、つぎに、列の重みの最大値を選択し、つぎに、行の重みの数を連続する２種類に限定した状態で、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な行の重みのセットを決定し、つぎに、分割後の行数を考慮して基本行列を底辺から順に削除し、つぎに、行の重みのセットを固定パラメータとして、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な列の重みのセットを決定し、つぎに、行の重みのセットおよび列の重みのセットを固定パラメータとして、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号の最適なアンサンブルを探索し、最後に、このアンサンブルに基づいて行削除後の基本行列の重みを所定の手順でランダムに分割する。これにより、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に生成できる、という効果を奏する。
つぎの発明によれば、生成関数λ（ｘ）と生成関数ρ（ｘ）を１回の線形計画法で求めることとしたため、上記論文のように、生成関数λ（ｘ）の導出と生成関数ρ（ｘ）の導出を繰り返し実行し、双方の最適値を求める方法よりも、容易かつ短時間に、確定的でかつ特性が安定したＬＤＰＣ符号用の検査行列を生成することができる、という効果を奏する。
つぎの発明によれば、重み配分を、重み単位の重み総数が整数で、かつ重み単位の重み総数の総和とユークリット幾何符号の「１」の総数とが等しくなるように調整する。これにより、高精度な分割処理を実現できる、という効果を奏する。
つぎの発明によれば、ランダム系列のラテン方陣を作成することによって、符号特性の条件を正確に規定できる、という効果を奏する。
つぎの発明によれば、まず、符号長と符号化率を決定し、つぎに、ベースとなるユークリット幾何符号を選択し、つぎに、選択したユークリット幾何符号を特定の関係式に基づいて並べ替えて基本行列を作成し、つぎに、列の重みの最大値を選択し、つぎに、行の重みの数を連続する２種類に限定した状態で、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な行の重みのセットを決定し、つぎに、分割後の行数を考慮して基本行列を底辺から順に削除し、つぎに、行の重みのセットを固定パラメータとして、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な列の重みのセットを決定し、つぎに、行の重みのセットおよび列の重みのセットを固定パラメータとして、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号の最適なアンサンブルを探索し、最後に、このアンサンブルに基づいて行削除後の基本行列の重みを所定の手順でランダムに分割する構成とした。これにより、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に生成できる、という効果を奏する。
つぎの発明によれば、まず、符号長と符号化率を決定し、つぎに、ベースとなるＣａｙｌａｙグラフの行および列の重みを決定して基本行列を作成し、つぎに、列の重みの最大値を選択し、つぎに、行の重みの数を連続する２種類に限定した状態で、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な行の重みのセットを決定し、つぎに、分割後の行数を考慮して基本行列を底辺から順に削除し、つぎに、行の重みのセットを固定パラメータとして、暫定的に、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号のアンサンブルを探索し、その後、最適な列の重みのセットを決定し、つぎに、行の重みのセットおよび列の重みのセットを固定パラメータとして、ガウス近似法によりＩｒｒｅｇｕｌａｒ−ＬＤＰＣ符号の最適なアンサンブルを探索し、最後に、このアンサンブルに基づいて行削除後の基本行列の重みを所定の手順でランダムに分割する構成とした。これにより、確定的で特性が安定し、かつ任意のアンサンブル，任意の符号長，任意の符号化率に対応した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」用の検査行列を、短時間で容易に生成できる、という効果を奏する。
【産業上の利用可能性】  以上のように、本発明にかかるＬＤＰＣ符号用検査行列生成方法および検査行列生成装置は、誤り訂正符号としてＬＤＰＣ符号を採用した通信システムに有用であり、特に、確定的で特性が安定した「Ｉｒｒｅｇｕｌａｒ−ＬＤＰＣ符号」を生成する装置に適している。
【図１】
2004006444.tif 000033
【図２】
2004006444.tif 000034
【図３】
2004006444.tif 000035
【図４】
2004006444.tif 000036
【図５】
2004006444.tif 000037
【図６】
2004006444.tif 000038
【図７】
2004006444.tif 000039
【図８】
2004006444.tif 000040
【図９】
2004006444.tif 000041
【図１０】
2004006444.tif 000042
【図１１】
2004006444.tif 000043
【図１２】
2004006444.tif 000044
【図１３】
2004006444.tif 000045
【図１４】
2004006444.tif 000046
【図１５】
2004006444.tif 000047
【図１６】
2004006444.tif 000048
【国際調査報告】
2004006444.tif 000049
2004006444.tif 000050