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