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