(57)【要約】  巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則な擬似巡回行列を生成する擬似巡回行列生成ステップと、正則な擬似巡回行列を非正則にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、特定の符号化率に対応するマスク行列を用いて、正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置したＬＤＧＭ構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、を含むこととした。
2008016117.tif 000002
【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法において、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含む検査行列生成方法であって、
前記マスク行列生成ステップでは、
まず、基準となる１／２以下の符号化率（第１の符号化率）に対応する第１のマスク行列の列次数分布を計算し、つぎに、前記第１のマスク行列の列次数分布を制約条件として次に符号化率の低い第２の符号化率に対応する第２のマスク行列の列次数分布を計算し、以降、必要に応じて、前段のマスク行列の列次数分布を制約条件として第３のマスク行列、第４のマスク行列、…の列次数分布を順に計算する次数分布計算ステップと、
符号化率の最も高い第１のマスク行列から順に、対応するマスク行列の列次数分布に基づいて、当該マスク行列の列の重み位置を決定する重み位置決定ステップと、
を含み、
前記検査行列生成ステップでは、最初に生成する検査行列を、前記符号化率１／２以下に対応した検査行列とすることを特徴とする検査行列生成方法。
【請求項２】
前記検査行列生成ステップでは、最後に生成する検査行列を、符号化率１／３未満に対応する検査行列とすることを特徴とする請求項１に記載の検査行列生成方法。
【請求項３】
前記重み位置決定ステップでは、
列次数が小さいことに起因して発生する誤りの確率に基づいて、マスク行列生成処理を、列次数の大きい列と小さい列に分けて行うこととし、
列次数の小さい列については、「同一列内の重みの間隔を２行以上離す」という第１の条件および「乱数に基づいて配置する」という第２の条件を満たすように、マスク行列の列の重み位置を決定することを特徴とする請求項２に記載の検査行列生成方法。
【請求項４】
前記重み位置決定ステップでは、前記第２の条件を満たすように、
所定の方法で乱数列を生成し、
当該乱数列において差分が１の要素が存在する場合に、一方の要素を乱数列の最後に移動することにより、要素間の差分が２以上となる擬似乱数系列を生成し、
当該擬似乱数系列を列次数毎に分割して、それぞれを列重みの行位置番号とすることを特徴とする請求項３に記載の検査行列生成方法。
【請求項５】
前記重み位置決定ステップでは、列次数分布における列次数の降順に、マスク行列の列を配置することを特徴とする請求項３に記載の検査行列生成方法。
【請求項６】
前記重み位置決定ステップでは、列次数分布における列次数の降順に、マスク行列の列を配置することを特徴とする請求項４に記載の検査行列生成方法。
【請求項７】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化方法であって、
前記請求項２に記載の処理で生成された非正則なパリティ検査行列を用いて所定の情報ビットを符号化する符号化ステップ、
を含むことを特徴とする符号化方法。
【請求項８】
前記符号化ステップでは、情報長Ｋ，符号長Ｎ（情報ビットＡ＋パリティビットＰ）の符号化率Ｋ／Ｎの符号語に、情報ビットＡのうち列重みの重い順から選択した符号語ビットＢ（ビット長ｂ）を加えて、符号化率Ｋ／（Ｎ＋ｂ）の符号語「Ａ＋Ｐ＋Ｂ」を生成することを特徴とする請求項７に記載の符号化方法。
【請求項９】
前記符号化率Ｋ／Ｎを３／７とし、前記符号化率Ｋ／（Ｎ＋ｂ）を１／３とすることを特徴とすることを特徴とする請求項８に記載の符号化方法。
【請求項１０】
さらに低い符号化率が必要な場合は、前記「Ａ＋Ｐ＋Ｂ」を繰り返した符号語ビットを生成することを特徴とする請求項９に記載の符号化方法。
【請求項１１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する通信装置であって、
前記請求項２に記載の処理で、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成することを特徴とする通信装置。
【請求項１２】
誤り訂正技術として、ＬＤＰＣ（Low-Density  Parity  Check）符号を採用する通信システムであって、
前記請求項７に記載の処理で、所定の情報ビットを符号化する送信装置と、
既知の処理で符号語を復号する受信装置と、
を備えることを特徴とする通信システム。
【請求項１３】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化器において、
前記請求項７に記載の処理で、所定の情報ビットを符号化する符号化手段、
を備えることを特徴とする符号化器。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ディジタル通信における符号化技術に関するものであり、特に、ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法、当該パリティ検査行列を用いて所定の情報ビットを符号化する符号化方法、および復号方法に関するものである。
【背景技術】
【０００２】
以下、符号化方式としてＬＤＰＣ符号を採用する従来の通信システムについて説明する。ここでは、ＬＤＰＣ符号の一例として擬似巡回（ＱＣ：Quasi-Cyclic）符号（非特許文献１参照）を採用する場合について説明する。【０００３】
まず、符号化方式としてＬＤＰＣ符号を採用する従来の通信システムにおける、符号化／復号処理の流れを簡単に説明する。【０００４】
送信側の通信装置（送信装置と呼ぶ）内のＬＤＰＣ符号化器では、後述する従来の方法でパリティ検査行列Ｈを生成する。さらに、ＬＤＰＣ符号化器では、たとえば、Ｋ行×Ｎ列の生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を生成する。ただし、ＬＤＰＣ用のパリティ検査行列をＨ（Ｍ行×Ｎ列）とした場合、生成行列Ｇは、ＧＨT＝０（Ｔは転置行列）を満たす行列となる。【０００５】
その後、ＬＤＰＣ符号化器では、情報長Ｋのメッセージ（ｍ1，ｍ2，…，ｍK）を受け取り、このメッセージおよび上記生成行列Ｇを用いて、下記（１）式のように、符号語Ｃを生成する。ただし、Ｈ（ｃ1，ｃ2，…，ｃN）T＝０とする。
Ｃ＝（ｍ1，ｍ2，…，ｍK）Ｇ
＝（ｃ1，ｃ2，…，ｃN）          …（１）【０００６】
そして、送信装置内の変調器では、ＬＤＰＣ符号化器で生成した符号語Ｃに対して、ＢＰＳＫ（Binary  Phase  Shift  Keying），ＱＰＳＫ（Quadrature  Phase  Shift  Keying），多値ＱＡＭ（Quadrature  Amplitude  Modulation）等の所定の変調方式を用いてディジタル変調を行い、その変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を受信装置に送信する。【０００７】
一方、受信側の通信装置（受信装置と呼ぶ）では、復調器が、受け取った変調信号ｙ＝（ｙ1，ｙ2，…，ｙN）に対して、上記ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のＬＤＰＣ復号器が、復調結果に対して「ｓｕｍ−ｐｒｏｄｕｃｔアルゴリズム」による繰り返し復号を実施し、その復号結果（元のメッセージｍ1，ｍ2，…，ｍKに対応）を出力する。【０００８】
ここで、ＬＤＰＣ符号用の従来のパリティ検査行列生成方法を具体的に説明する。ＬＤＰＣ符号用のパリティ検査行列としては、たとえば、下記非特許文献１において、以下のＱＣ符号のパリティ検査行列が提案されている（図１１参照）。図１１に示すＱＣ符号のパリティ検査行列は、５行×５列の巡回置換行列（ｐ＝５）が縦方向（Ｊ＝３）と横方向（Ｌ＝５）に配置された行列となっている。【０００９】
一般的には、Ｍ（＝ｐＪ）行×Ｎ（＝ｐＬ）列の（Ｊ，Ｌ）ＱＣ符号のパリティ検査行列ＨQCは、下記（２）式のように定義することができる。なお、ｐは奇数（２以外）の素数であり、Ｌはパリティ検査行列ＨQCにおける巡回置換行列の横方向（列方向）の個数であり、Ｊはパリティ検査行列ＨQCにおける巡回置換行列の縦方向（行方向）の個数である。【００１０】
【数１】
2008016117.tif 000003
【００１１】
ただし、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。【００１２】
また、ＬＤＰＣ符号の設計の際には、一般的に、長さが短いループが多く存在するときに性能の劣化を引き起こすため、内径を大きくし、長さが短いループ（ループ４，ループ６等）の数を少なくする必要がある。【００１３】
なお、図１２は、検査行列の一例をタナーグラフで表現した場合を示す図であり、｛０，１｝の２元のＭ行×Ｎ列のパリティ検査行列Ｈにおいて、各列に対応するノードをビットノードｂn（１≦ｎ≦Ｎ）と呼び（図中の○に相当）、各行に対応するノードをチェックノードｃm（１≦ｍ≦Ｍ）と呼び（図中の□に相当）、さらに、検査行列の行と列の交点に“１”がある場合にそのビットノードとチェックノードを枝で接続する２部グラフをタナーグラフと呼ぶ。また、上記ループとは、図１２に示すように、特定のノード（図中の○や□に相当）から始まりそのノードで終わる閉路のことを表し、また、内径とは、その最小ループを意味する。また、ループの長さは、閉路を構成する枝の数で表現され、長さに応じて、簡易的にループ４，ループ６，ループ８…と表現する。【００１４】
また、下記非特許文献１においては、（Ｊ，Ｌ）ＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCにおける内径ｇの範囲が、「４≦ｇ≦１２（ｇは偶数）」とされている。ただし、ｇ＝４を回避することは容易であり、多くの場合、ｇ≧６である。【００１５】
【非特許文献１】M.Fossorier  “Quasi-Cyclic  Low  Density  Parity  Check  Code”  ISIT2003,  pp150,  Japan,  June  29-July  4,  2003.
【発明の開示】
【発明が解決しようとする課題】
【００１６】
しかしながら、上記従来の技術によれば、符号化率を変化させるために複数の全く異なる検査行列が必要であり、それに伴って、メモリ量が大きくなり、回路も複雑になる、という問題があった。【００１７】
本発明は、上記に鑑みてなされたものであって、広い符号化率に対応可能な、非正則（行と列の重みが非一様）なＬＤＰＣ符号用のパリティ検査行列を生成するとともに、さらに、従来技術と比較して回路規模を低減可能な検査行列生成方法を得ることを目的とする。
【課題を解決するための手段】
【００１８】
上述した課題を解決し、目的を達成するために、本発明にかかる検査行列生成方法は、ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法であって、巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、を含む検査行列生成方法であって、前記マスク行列生成ステップでは、まず、基準となる１／２以下の符号化率（第１の符号化率）に対応する第１のマスク行列の列次数分布を計算し、つぎに、前記第１のマスク行列の列次数分布を制約条件として次に符号化率の低い第２の符号化率に対応する第２のマスク行列の列次数分布を計算し、以降、必要に応じて、前段のマスク行列の列次数分布を制約条件として第３のマスク行列、第４のマスク行列、…の列次数分布を順に計算する次数分布計算ステップと、符号化率の最も高い第１のマスク行列から順に、対応するマスク行列の列次数分布に基づいて、当該マスク行列の列の重み位置を決定する重み位置決定ステップと、を含み、前記検査行列生成ステップでは、最初に生成する検査行列を、前記符号化率１／２以下に対応した検査行列とすることを特徴とする。
【発明の効果】
【００１９】
この発明によれば、広い符号化率に対応可能な、非正則なＬＤＰＣ符号用のパリティ検査行列を生成することができる、という効果を奏する。
【図面の簡単な説明】
【００２０】
【図１】図1は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む通信システムの構成例を示す図である。
【図２−１】図２−1は、符号化率１／３の符号に対応するマスク行列Ｚを生成する場合のマスキングルールを説明するための図である。
【図２−２】図２−２は、符号化率１／３の符号に対応するマスク行列Ｚを生成する場合のマスキングルールを説明するための図である。
【図２−３】図２−３は、符号化率１／３の符号に対応するマスク行列Ｚを生成する場合のマスキングルールを説明するための図である。
【図２−４】図２−４は、符号化率１／３の符号に対応するマスク行列Ｚを生成する場合のマスキングルールを説明するための図である。
【図２−５】図２−５は、符号化率１／３の符号に対応するマスク行列Ｚを生成する場合のマスキングルールを説明するための図である。
【図３】図３は、マスク行列Ｚによりマスク後のイレギュラーなパリティ検査行列ＨMの構成例を示す図である。
【図４】図４は、符号構成法の一例を示す図である。
【図５】図５は、システムで用意する一番低い符号化率をＲ0＝３／７とした場合の符号を示す図である。
【図６】図６は、符号語の生成処理の一例を示す図である。
【図７】図７は、符号語の生成処理の一例を示す図である。
【図８】図８は、一般に公開されている符号化率３／４の行列の一例を示す図である。
【図９】図９は、図８に示す行列を符号化率３／４のＭ×Ｎの行列ＨCHとした場合の、４Ｍ×（７／３）Ｎの行列ＨCH´の一例を示す図である。
【図１０】図1０は、任意の巡回置換行列の組み合わせによるＭ×（Ｎ−Ｍ）の行列をＨCHとした場合の、４Ｍ×（７／３）Ｎの行列ＨCH´の一例を示す図である。
【図１１】図1１は、ＱＣ符号のパリティ検査行列の一例を示す図である。
【図１２】図1２は、検査行列の一例をタナーグラフで表現した場合を示す図である。
【符号の説明】
【００２１】
１  ＬＤＰＣ符号化器
２  変調器
３  通信路
４  復調器
５  ＬＤＰＣ復号器
【発明を実施するための最良の形態】
【００２２】
以下に、本発明にかかる検査行列生成方法、符号化方法および復号方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。【００２３】
実施の形態１．
図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ＬＤＰＣ符号化器１と変調器２を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とＬＤＰＣ復号器５を含む構成とする。【００２４】
ここで、ＬＤＰＣ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。【００２５】
送信装置内のＬＤＰＣ符号化器１では、本実施の形態の検査行列生成方法により生成されたパリティ検査行列、すなわち、後述する所定のマスキングルールに基づいてマスキング処理が行われたＭ行×Ｎ列のパリティ検査行列ＨMを生成する。【００２６】
その後、ＬＤＰＣ符号化器１では、情報長Ｋのメッセージ（ｕ1，ｕ2，…，ｕK）を受け取り、このメッセージおよび上記パリティ検査行列ＨMを用いて、下記（３）式のように、長さＮの符号語ｖを生成する。なお、本実施の形態においては、従来技術において計算していた生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を用いずに、情報ビットの符号化処理を行う。
ｖ＝｛（ｖ1，ｖ2，…，ｖN）∈ＧＦ（２）｜（ｖ1，ｖ2，…，ｖN）ＨMT＝０｝
…（３）【００２７】
そして、送信装置内の変調器２では、ＬＤＰＣ符号化器１で生成した符号語ｖに対して、ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の所定の変調方式によりディジタル変調を行い、その変調信号ｘ＝（ｘ1，ｘ2，…，ｘN）を、通信路３を介して受信装置に送信する。【００２８】
一方、受信装置では、復調器４が、通信路３を介して受け取った変調信号ｙ＝（ｙ1，ｙ2，…，ｙN）に対して、上記ＢＰＳＫ，ＱＰＳＫ，多値ＱＡＭ等の変調方式に応じたディジタル復調を行い、さらに、受信装置内のＬＤＰＣ復号器５が、公知の復号アルゴリズムによる繰り返し復号を実施し、その復号結果（元のメッセージｕ1，ｕ2，…，ｕKに対応）を出力する。【００２９】
つづいて、本実施の形態における検査行列生成方法を詳細に説明する。なお、本実施の形態においては、イレギュラー（重み分布が非一様）なパリティ検査行列を生成することとし、その構造として、ＬＤＧＭ（Low  Density  Generation  Matrix）構造を採用することを前提とする。また、以下において説明する各実施の形態の検査行列生成処理については、通信装置内のＬＤＰＣ符号化器１で実行することとしてもよいし、または、通信装置の外部で予め実行しておくこととしてもよい。通信装置の外部で実行される場合には、生成済みの検査行列を内部メモリに記憶しておく。【００３０】
まず、本実施の形態の検査行列生成処理により生成されるマスキング処理後のイレギュラーなパリティ検査行列ＨMの前提となる、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを定義する。【００３１】
たとえば、Ｍ（＝ｐＪ）行×Ｎ（＝ｐＬ＋ｐＪ）列のＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCL（＝［ｈm,n］）は、下記（４−１）式のように定義することができる。【００３２】
【数２−１】
2008016117.tif 000004
【００３３】
なお、ｈm,nは、パリティ検査行列ＨQCLにおいて、行番号ｍ，列番号ｎの要素を表す。また、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。たとえば、Ｉ（１）は、下記（４−２）式のように表すことができる。【００３４】
【数２−２】
2008016117.tif 000005
【００３５】
上記パリティ検査行列ＨQCLは、左側の行列（情報ビットに対応する部分）が、上記（２）式で示したＱＣ符号のパリティ検査行列と同一の擬似巡回行列ＨQCであり、右側の行列（パリティビットに対応する部分）が、下記（５−１）式または（５−２）式に示すＩ（０）を階段状に配置した行列ＨTまたはＨDである。なお、下記（５−１）式，（５−２）式において、Ｉは単位行列であり、０は零行列である。【００３６】
【数３−１】
2008016117.tif 000006
【００３７】
【数３−２】
2008016117.tif 000007
【００３８】
ただし、上記階段状の構造で用いている巡回置換行列は、Ｉ（０）に限定しているわけではなく、任意のＩ（ｓ｜ｓ∈［０，ｐ−１］）の組み合わせでもよい。【００３９】
また、上記ＬＤＧＭ構造とは、上記（４−１）式に示す行列のように、パリティ検査行列の一部を下三角行列にした構造のことをいう。この構造を用いることにより、生成行列Ｇを用いずに符号化を容易に実現できる。たとえば、組織符号語ｖを下記（６）式のように表し、情報メッセージｕ＝（ｕ1，ｕ2，…，ｕK）が与えられた場合、パリティ要素ｐm＝（ｐ1，ｐ2，…，ｐM）は、「ＨQCL・ｖT＝０」を満たすように、すなわち、下記（７）式のように生成する。【００４０】
ｖ＝（ｖ1，ｖ2，…，ｖK，ｖK+1，ｖK+2，…，ｖN）
＝（ｕ1，ｕ2，…，ｕK，ｐ1，ｐ2，…，ｐM）        …（６）
ただし、Ｎ＝Ｋ＋Ｍである。【００４１】
【数４】
2008016117.tif 000008
【００４２】
さらに、本実施の形態においては、上記（４−１）式のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、特定の規則性を設けている。具体的には、パリティ検査行列ＨQCLの左側の擬似巡回行列ＨQC部分において、ｐ0,lを任意の整数とした場合、行番号ｊ（＝０，１，２，…Ｊ−１），列番号ｌ（＝０，１，２，…Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、下記（８−１）式、（８−２）式、（８−３）式または（８−４）式となる規則性を設ける。【００４３】
ｐj,l＝ｐ0,l（ｊ＋１）ｍｏｄ  ｐ
…（８−１）
ｐj,l＝（（ｐ−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐ
…（８−２）
ｐj,l＝（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ
ｐA＝１５７
０≦ｊ≦Ｊ−１
ｐ：ｐｒｉｍｅ  ｎｕｍｂｅｒ
…（８−３）
ｐj,l＝（（ｐ0,l（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ
ｐA＝１５７
０≦ｊ≦Ｊ−１
ｐ：ｐｒｉｍｅ  ｎｕｍｂｅｒ
…（８−４）【００４４】
なお、上記ｐAは、システムが要求するＭＡＸの情報長の時に最も良い性能が得られるように決定する。上記「ｐA＝１５７」は、情報長ｐ×Ｌ（＝３６）が５０００〜６０００近辺を想定した場合の値となる。【００４５】
たとえば、上記（８−４）式を用い、Ｌ＝３６とした場合、一例として下記（９）式のように表すことができる。
｛ｐ0,1，ｐ0,2，ｐ0,3，ｐ0,4，ｐ0,5，ｐ0,6，ｐ0,7，ｐ0,8，ｐ0,9，ｐ0,10，ｐ0,11，ｐ0,12，ｐ0,13，ｐ0,14，ｐ0,15，ｐ0,16，ｐ0,17，ｐ0,18，ｐ0,19，ｐ0,20，ｐ0,21，ｐ0,22，ｐ0,23，ｐ0,24，ｐ0,25，ｐ0,26，ｐ0,27，ｐ0,28，ｐ0,29，ｐ0,30，ｐ0,31，ｐ0,32，ｐ0,33，ｐ0,34，ｐ0,35，ｐ0,36｝
＝｛7,87,36,15,53,11,16,136,59,45,137,31,56,66,31,37,2,22,131,21,6,92,56,72,53,23,21,36,73,127,25,15,10,1,107,18｝
…（９）【００４６】
つづいて、本実施の形態の検査行列生成方法における特徴的な処理である、パリティ検査行列ＨQCLに対するマスク処理について説明する。【００４７】
たとえば、上記（４−１）式に示す左側の行列を、下記（１０−１）式に示すように、Ｊ×Ｌの擬似巡回行列ＨQCと表し、マスク行列Ｚ（＝［ｚj,l］）をＧＦ（２）上のＪ行×Ｌ列の行列とした場合、後述する所定のルールを適用すると、マスク処理後の行列ＨMQCは、下記（１０−２）式のように表すことができる。【００４８】
【数５−１】
2008016117.tif 000009
【００４９】
【数５−２】
2008016117.tif 000010
【００５０】
なお、上記（１０−２）式におけるｚj,lＩ（ｐj,l）は、下記（１１）式のように定義される。【００５１】
【数６】
2008016117.tif 000011
【００５２】
上記０行列は、ｐ行×ｐ列の０行列である。また、行列ＨMQCは、擬似巡回行列ＨQCをマスク行列Ｚの０要素によりマスクし、重み分布を非一様（イレギュラー）にした行列であり、また、行列ＨMQCの巡回置換行列の分布は、マスク行列Ｚの次数分布と同じである。【００５３】
ただし、上記重み分布を非一様にする場合のマスク行列Ｚの重み分布は、後述するように、所定の密度発展法で求めることとする。たとえば、４８行×３６列のマスク行列は、密度発展法による列次数分布に基づいて、下記（１２−１）式〜（１２−５）式のように表すことができる。【００５４】
【数７−１】
2008016117.tif 000012
【００５５】
【数７−２】
2008016117.tif 000013
【００５６】
【数７−３】
2008016117.tif 000014
【００５７】
【数７−４】
2008016117.tif 000015
【００５８】
【数７−５】
2008016117.tif 000016
【００５９】
したがって、本実施の形態において、最終的に求めるイレギュラーなパリティ検査行列ＨMは、たとえば、４８行×３６列のマスク行列Ｚ、４８行（行番号ｊは０〜４７）×３６列（列番号ｌは０〜３１）の擬似巡回行列ＨQC、および４８行（行番号ｊは０〜４７）×４８列（列番号ｌは０〜４７）のＨTを用いて、下記（１３）式のように表すことができる。【００６０】
ＨM＝［Ｚ×ＨQC｜ＨT］
＝［ＨMQC｜ＨT］                …（１３）【００６１】
すなわち、ＬＤＰＣ符号Ｃを生成するためのパリティ検査行列ＨMQCは、マスク行列Ｚと擬似巡回行列ＨQCの行番号ｊ＝０の巡回置換行列の値の設計により、与えられる。【００６２】
つづいて、本実施の形態のマスキングルールを具体的に説明する。本実施の形態においては、一例として、符号化率３／７までの符号構成法について説明する。ここでは、後述する既知のマスキングルールを前提として、符号化率３／７以上の符号化を実現する。【００６３】
図２−１は、本実施の形態のマスク行列生成処理を示すフローチャートである。ここで、符号化率３／７までの符号構成法について説明する前に、図２−１にしたがって、既知のマスキングルールについて説明する。一例として、符号化率１／３の符号に対応するマスク行列Ｚを生成する。【００６４】
なお、ここでは、マスク行列生成処理を、通信装置内のＬＤＰＣ符号化部１にて実行する場合の例を示す。また、符号化率１／２の符号に対応するイレギュラーなパリティ検査行列ＨM(1/2)を「ＨM(1/2)＝［ＺA×ＨQCU｜ＨD］」と仮定する。ただし、ＨQCUは、上記擬似巡回行列ＨQCにおける上半分の３２（行番号ｊは０〜３１）×３２（列番号ｌは０〜３１）の擬似巡回行列を表し、ＨDは、上記（５−２）式に示す、たとえば、３２（行番号ｊは０〜３１）×３２（列番号ｌは０〜３１）の行列とする。【００６５】
まず、通信装置内のＬＤＰＣ符号化器１では、マスク行列のサイズを設定する（ステップＳ１）。ここでは、一例として、符号化率１／３の符号に対応するマスク行列Ｚを６４行×３２列の行列とし、符号化率１／２の符号に対応するマスク行列ＺAを３２行×３２列の行列とする。【００６６】
つぎに、ＬＤＰＣ符号化器１は、マスク行列ＺAの行数を最大次数とし、上記（５−２）式に示すＨDの次数分布を制約条件として、密度発展法により、マスク行列ＺAの列次数分布を計算する（ステップＳ２）。図２−２は、パリティ検査行列ＨM(1/2)（＝［ＺA×ＨQCU｜ＨD］）の列次数分布の一例を示す図であり、列次数１４，４，３の欄に記載の数字（分数）がマスク行列ＺAの列次数分布を表している。なお、列次数２の欄は、ＨDの列次数分布に対応している。【００６７】
さらに、ＬＤＰＣ符号化器１は、マスク行列Ｚの行数を最大次数とし、上記（５−１）式に示す６４（行番号ｊは０〜６３）×６４（列番号ｌは０〜６３）のＨTの次数分布、および上記で求めたマスク行列ＺAの列次数分布、を制約条件として、密度発展法により、マスク行列Ｚの列次数分布を計算する（ステップＳ２）。図２−３は、符号化率１／３の符号に対応するイレギュラーなパリティ検査行列ＨM(1/3)（＝［Ｚ×ＨQC｜ＨT］）の列次数分布の一例を示す図であり、列次数２８，８，４，３（９列分）の欄に記載の数字がマスク行列Ｚの列次数分布を表している。なお、列次数３の（４１−９）／９６と列次数１の欄は、ＨTの列次数分布に対応している。【００６８】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列ＺAの列次数分布に基づいて、下記優先順位＃１の条件を満たすように、マスク行列ＺAにおける列次数の大きい列、すなわち、ここでは列次数１４の列（５／６４）の、“１”の位置を決める（ステップＳ３）。たとえば、Ｚに連続する“１”が存在する場合は、ＨDの縦に連続するＩ（０）との間で４箇所に巡回置換行列が存在し、それらがループ４を構成する可能性があるため、下記優先順位＃１の条件を満たすことにより、その可能性を排除する。【００６９】
・優先順位＃１の条件：同一列内の“１”の間隔は２行以上離す【００７０】
このとき、上記列次数の大きい列は、“１”の密度が大きいため、後述する優先順位＃２の条件を満たす必要はない。また、上記で求めた列次数１４を実現するために、同一列において“１”が連続しても良いが、その数は可能な限り少なくする。【００７１】
そして、ここでは、列次数の大きい列が１４の一つしか存在していないが、たとえば、列次数の大きい列が１４，１３，１２…等のように複数存在する場合は、左から列次数の降順にマスク行列ＺAの列を配置する（ステップＳ３）。【００７２】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列ＺAの列次数分布に基づいて、上記優先順位＃１の条件および下記優先順位＃２の条件を満たすように、マスク行列ＺAにおける列次数の小さい列、すなわち、ここでは列次数４，３の列（１８／６４，９／６４）の、“１”の位置を決める（ステップＳ４）。たとえば、規則的なルールに基づく巡回置換行列の組み合わせに対して、マスク行列の“１”の配置も規則的である場合、特定のループを構成するマスク行列の“１”の配置が存在すると、規則的であるがゆえに多重的に同一ループが多数個存在する可能性がある。しかしながら、下記優先順位＃２の条件を満たすことにより、その発生確率を減らすことができる。【００７３】
・優先順位＃２の条件：乱数に基づき配置する【００７４】
そして、上記列次数の大きい列につづいて、左から列次数の降順にマスク行列ＺAの列を配置する（ステップＳ４）。【００７５】
たとえば、上記ステップＳ３およびＳ４にて生成されたマスク行列ＺAは、（１４）式に示すような行列となる。【００７６】
【数８】
2008016117.tif 000017
【００７７】
なお、密度発展法により求めたマスク行列ＺAの列次数分布に基づいてマスク行列ＺAを構成する場合、小さい列次数の列（列次数３，４等）に小さいループ（ループ４，６等）が含まれていると、誤り確率が上がり、良好な性能が得られない場合がある。このような場合、ＬＤＰＣ符号化器１は、小さい列次数の列の重みを増やすことで、性能劣化を回避する。上記マスク行列ＺAの場合は、図２−２に示す列次数分布において、列次数３の列（９／６４）のうちの３列の重みを増やしている。すなわち、上記（１４）式においては、列次数１４が５列，列次数４が２１列，列次数３が６列となっている。【００７８】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列Ｚの列次数分布に基づいて、上記優先順位＃１の条件を満たすように、マスク行列Ｚにおける列次数の大きい列、すなわち、ここでは列次数２８の列（５／９６）の、“１”の位置を決める（ステップＳ５）。このとき、上記列次数の大きい列は、“１”の密度が大きいため、上記優先順位＃２の条件を満たす必要はない。また、上記で求めた列次数２８を実現するために、同一列において“１”が連続しても良いが、その数は可能な限り少なくする。【００７９】
そして、ここでは、列次数の大きい列が２８の一つしか存在していないが、列次数の大きい列が複数存在する場合は、左から列次数の降順にマスク行列Ｚの列を配置する（ステップＳ５）。【００８０】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列Ｚの列次数分布に基づいて、上記優先順位＃１の条件および上記優先順位＃２の条件を満たすように、マスク行列Ｚにおける列次数の小さい列、すなわち、ここでは列次数８，４，３の一部の列（１０／９６，８／９６，９／９６）の、“１”の位置を決める（ステップＳ６）。【００８１】
そして、上記列次数の大きい列につづいて、左から列次数の降順にマスク行列Ｚの列を配置する（ステップＳ６）。【００８２】
なお、密度発展法により求めたマスク行列Ｚの列次数分布に基づいてマスク行列Ｚを構成する場合、小さい列次数の列（列次数３，４，８等）に小さいループ（ループ４，６等）が含まれていると、誤り確率が上がり、良好な性能が得られない場合がある。このような場合、ＬＤＰＣ符号化器１は、小さい列次数の列の重みを増やすことで、性能劣化を回避する。【００８３】
また、ＬＤＰＣ符号を多値変調のような不均一な誤り確率のアプリケーションに適用する場合、誤り確率の小さいビットを列次数の大きい列に対応するビットに割り当て、誤り確率の大きいビットを列次数の小さい列に対応するビットに割り当てると、性能が向上する。このような場合に、上記ステップＳ３〜Ｓ６に示すように、左側から列次数の降順に列を並べておくと、ビットのオーダリングが容易となる。【００８４】
図２−４は、上記のように生成したマスク行列ＺAによりマスク後の、イレギュラーなパリティ検査行列ＨM(1/2)の構成例を示す図であり、図２−５は、上記のように生成したマスク行列Ｚによりマスク後の、イレギュラーなパリティ検査行列ＨM(1/3)の構成例を示す図である。なお、図２−５において、図示のＨQCDは、上記擬似巡回行列ＨQCにおける下半分の３２（行番号ｊは３２〜６３）×３２（列番号ｌは０〜３１）の擬似巡回行列を表す。また、図示の０は０行列を表し、図示のＩは単位行列を表し、ＨDとＩと０でＨTを構成する。【００８５】
つぎに、上記符号化率１／３の符号生成処理を前提として、符号化率３／７以上の符号化を実現する方法について説明する。本実施の形態のマスク行列生成処理として、上記符号化率１／３の符号生成処理と異なる処理について説明する。なお、本実施の形態においては、後述するように、最初に構成する検査行列を符号化率３／４に対応した検査行列としているが、これに限らず、符号化率１／２以下に対応する検査行列であればよい。【００８６】
たとえば、符号化率３／４の符号に対応するイレギュラーなパリティ検査行列を「ＨM(3/4)＝［ＺA×ＨQC(3/4)｜ＨT(3/4)］」と仮定する。ただし、ＺA（＝ＺA(3/4)）は１２行×３６列のマスク行列であり、ＨQC(3/4)は、擬似巡回行列ＨQCにおける上から１／４の１２（行番号ｊは０〜１１）×３６（列番号ｌは０〜３５）の擬似巡回行列を表し（（４−１）式参照）、ＨT(3/4)は上記ＨDである（（５−２）式参照）。また、符号化率３／５，３／６＝１／２，３／７に対応したイレギュラーなパリティ検査行列をＨM(3/5)，ＨM(1/2)，ＨM(3/7)（＝ＨM）と表し、マスク行列をそれぞれＺA(3/5)，ＺA(1/2)，ＺA(3/7)（＝Ｚ）と表し、擬似巡回行列をそれぞれＨQC(3/5)，ＨQC(1/2)，ＨQC(3/7)（＝ＨQC）と表し、Ｉ（０）を階段状に配置した行列をそれぞれＨT(3/5)，ＨT(1/2)，ＨT(3/7)（＝ＨT）と表す。【００８７】
たとえば、図２−１のステップＳ２の処理において、本実施の形態のＬＤＰＣ符号化器１では、まず、符号化率３／４に対応して、マスク行列ＺAの行数を最大次数とし、ＨT(3/4)（＝ＴD）の次数分布を制約条件として、密度発展法により、マスク行列ＺAの列次数分布を計算する。つぎに、ＬＤＰＣ符号化器１は、符号化率３／５に対応して、上記ＨT(3/5)の次数分布および上記で求めたマスク行列ＺAの列次数分布を制約条件として、密度発展法により、マスク行列ＺA(3/5)の列次数分布を計算する。つぎに、一つ前のマスク行列の列次数分布を制約条件として、密度発展法により、符号化率３／６に対応したマスク行列の列次数分布を順次計算し、最後に、上記ＨTの次数分布および符号化率３／６に対応したマスク行列ＺA(3/6)の列次数分布を制約条件として、密度発展法により、符号化率３／７に対応したマスク行列Ｚの列次数分布を計算する。【００８８】
つぎに、ＬＤＰＣ符号化器１では、図２−１のステップＳ３〜Ｓ６の処理において、前述した実施の形態１と同様に、優先順位＃１の条件および優先順位＃２の条件に基づいて、符号化率３／４，３／５に対応するマスク行列の各列の“１”の位置を決め、その後、さらに、同様の手順で、符号化率３／６，３／７に対応するマスク行列の各列の“１”の位置を決める。上記本実施の形態の処理にて生成されたマスク行列Ｚは、上記（１２−１）式〜（１２−５）式のように表すことができる。【００８９】
図３は、上記のように生成したマスク行列Ｚによりマスク後の、イレギュラーなパリティ検査行列ＨMの構成例を示す図である。【００９０】
つづいて、前述のイレギュラーなパリティ検査行列ＨMを用いて、複数の符号化率に対応したＬＤＰＣ符号を構成する場合について説明する。【００９１】
たとえば、前述の符号構成法によって生成され、ＭとＮで規定された符号における符号化率の下限を１／２から１／３の間とした。また、それ以下の符号化率を実現するためには、後述する繰り返し送信を用いて良好な性能を得る。【００９２】
また、図４は、本実施の形態の符号構成法の一例を示す図であり、たとえば、符号化率０．７５の符号を基準符号語とし、それよりも高い符号化率（＝０．９）の符号語を生成する場合はパリティのパンクチャを行う。なお、この際の復号には符号化率３/４の検査行列を使って、パンクチャリングビットに対応する受信ＬＬＲに０を挿入し、通常のＬＤＰＣ復号を行えばよい。一方、低い符号化率（＝３／５）の符号語を生成する場合は、パリティを追加している。この際の復号には、図３に示すように、符号化率に対応した検査行列ＨMの部分行列のみを用いて復号する。【００９３】
ここで、複数の符号化率に対応したＬＤＰＣ符号の構成法を具体的に説明する。たとえば、システムで用意する一番低い符号化率をＲ0＝１／２以下とする。図５は、たとえば、システムで用意する一番低い符号化率をＲ0＝３／７とした場合の符号を示す図である。【００９４】
たとえば、符号化率Ｒ0＝３／７に対応する符号がメモリに記憶され、符号化率Ｒ1の符号を構成する場合、符号化率Ｒ1が３／４未満であれば、すなわち、符号化率Ｒ1が３／４〜３／７の間であれば、パリティビットを符号語の最後尾から順にパンクチャする。【００９５】
一方で、たとえば、３／７以下の符号化率が必要となった場合、本実施の形態では、図６に示すように、情報長Ｋ，符号長Ｎの符号化率Ｋ／Ｎ＝３／７の符号語（図６中のＡ＋パリティビット）に、列重みの重い順から選択した符号語ビットＢ（長さｂ：各列に対応するビットの情報はＡと同じ）を加えて符号化率Ｋ／（Ｎ＋ｂ）の符号語を生成する。たとえば、ｂ＝(２／３)＊Ｋの場合、符号化率は１／３となり、ｂ＝Ｋの場合は、符号化率３／１０となる。図６は、３／７以下の符号化率が必要となった場合における、本実施の形態の符号構成法を示す図である。【００９６】
また、ｂ＝（２／３）＊Ｋ（図７のＢの箇所）のように同一の符号語の一部が繰り返し２回にわたって送られ、さらにそれ以上に低い符号化率が必要な場合は、再度「Ａ＋パリティビット＋Ｂ」の符号語ビットを繰り返し送ることも可能とした。これは、列重みの重いＢの箇所のみ重複して送ることにより性能が向上する事が確認されているためである。また、さらに低い符号化率を実現するためには、この部分（Ａ＋パリティビット＋Ｂ）をさらに重複して送る。【００９７】
そして、上記の方法により符号化された符号語が通信路を通って受信機で受信され、復号器が誤りを訂正する際に符号語の一部あるいは全てが重複した場合には、その重複したビットの受信値を、重複した個数分だけ加算平均し、その結果を復号器に渡すこととした。また、列重みの重い列に対応する符号語ビットは復号性能がよくなることが知られている。したがって、本実施の形態では、上記処理によりノイズ成分の分散値を下げることができ、それに伴って信頼度が上がる（対応するビットの誤り確率が下がり）ため、復号性能を向上させることができる。【００９８】
なお、本実施の形態において、巡回置換行列のｐが奇数（２以外）の素数であることとして記載したが、ｐについてはこれに限らず、奇数を選んでもよい。この場合、高符号化率のパンクチャ時に性能が劣化する可能性があるが、劣化は僅かである。一方で、素数については、計算量が増加することを回避するためにテーブルを持ち予め記憶しておく必要があるが、奇数の場合はその値を記憶しておく必要がない。【００９９】
このように、本実施の形態においては、従来技術とは異なり、符号化率を変化させるために複数の全く異なる検査行列をメモリに記憶しておく必要がないため、従来よりもメモリ量を小さくでき、回路を簡単化できる。【０１００】
また、本実施の形態においては、たとえば、符号化率１／２に対応する検査行列を基準に検査行列を拡大しているときと比べて、符号化率３／４に対応するより小さい検査行列から拡大することとし、また、３／４以上の符号化率の際には符号化率３／４に対応する検査行列に従って復号処理を行うこととしたので、符号化率１／２に対応する検査行列を基準にする場合と比較して復号に関する計算量を低減することができる。また、３／７以下の符号化率であっても、列次数の重い箇所の符号語の再送回数を多くすることによって、低い符号化率を実現することができるので、本実施の形態においては、性能の劣化を抑えながら、より広い符号化率を実現することができる。【０１０１】
実施の形態２．
前述の実施の形態１では、巡回置換行列Ｉ（ｐj,l）を一定のルールで構成した例について示したが、本実施の形態では、たとえば、一般に公開されている図８（“Draft  IEEE  Standard  forLocal  and  metropolitan  area  networks,  Part  16:  Air  Interface  for  Fixed  and  Mobile  Broadband  Wireless  Access  Systems,  Amendment  for  Physical  and  Medium  Access  Control  Layers  for  Combined  Fixed  and  Mobile  Operation  in  Licensed  Bands”,  IEEE  P802.16e/D9,  June  2005）に示すような符号化率３／４の行列を用いて、符号化率３／７を実現する。なお、図８中の数字はｐj,lの値を示しており、−１はｐ×ｐの０行列を意味する。【０１０２】
具体的には、図８に示す行列を符号化率３／４のＭ×Ｎの行列ＨCHとした場合、４Ｍ×（７／３）Ｎの行列ＨCH´を図９のように構成する。たとえば、Ａは巡回置換行列の組み合わせによる行列で構成され、さらに、単位行列Ｉを２つ連結させて右下に階段状に配置する。行列Ａの重み分布は密度発展法で導出する。この方法により、前述した実施の形態１と同様にＬＤＰＣ用のパリティ検査行列を生成することができる。【０１０３】
なお、行列Ａの構成法は、本実施の形態のように巡回置換行列の任意の組み合わせによる行列で構成することとしてもよいし、前述した実施の形態１のように規則的なルールに基づいて構成することとしてもよい。また、複数の符号化率に対応したＬＤＰＣ符号を構成する処理については、上記図８に示すようなパリティ検査行列に限らず、どのようなパリティ検査行列においても適用可能である。【０１０４】
また、たとえば、任意の巡回置換行列の組み合わせによるＭ×（Ｎ−Ｍ）の行列をＨCHとする場合には、４Ｍ×（７／３）Ｎの行列ＨCH´を図１０のように構成する。Ａは巡回置換行列の組み合わせによる行列で構成され、さらに、ＨCHとＡの右側にＨDを配置する。行列Ａの重み分布は密度発展法で導出する。この方法により、前述の実施の形態１と同様に、ＬＤＰＣ用のパリティ検査行列を生成することができる。【０１０５】
また、前述した実施の形態１および上記実施の形態２における符号構成法および符号化法は、消失訂正符号の符号化にも適用可能である。
【産業上の利用可能性】
【０１０６】
以上のように、本発明にかかる検査行列生成方法および符号化方法は、ディジタル通信における符号化技術として有用であり、特に、符号化方式としてＬＤＰＣ符号を採用する通信装置に適している。
【図１】
2008016117.tif 000018
【図２−１】
2008016117.tif 000019
【図２−２】
2008016117.tif 000020
【図２−３】
2008016117.tif 000021
【図２−４】
2008016117.tif 000022
【図２−５】
2008016117.tif 000023
【図３】
2008016117.tif 000024
【図４】
2008016117.tif 000025
【図５】
2008016117.tif 000026
【図６】
2008016117.tif 000027
【図７】
2008016117.tif 000028
【図８】
2008016117.tif 000029
【図９】
2008016117.tif 000030
【図１０】
2008016117.tif 000031
【図１１】
2008016117.tif 000032
【図１２】
2008016117.tif 000033
【手続補正書】
【提出日】平成20年2月7日(2008.2.7)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号用のパリティ検査行列を生成する検査行列生成方法において、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｇｅｎｅｒａｔｉｏｎ  Ｍａｔｒｉｘ）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含む検査行列生成方法であって、
前記マスク行列生成ステップでは、
まず、基準となる１／２以下の符号化率（第１の符号化率）に対応する第１のマスク行列の列次数分布を計算し、つぎに、前記第１のマスク行列の列次数分布を制約条件として次に符号化率の低い第２の符号化率に対応する第２のマスク行列の列次数分布を計算し、以降、必要に応じて、前段のマスク行列の列次数分布を制約条件として第３のマスク行列、第４のマスク行列、…の列次数分布を順に計算する次数分布計算ステップと、
符号化率の最も高い第１のマスク行列から順に、対応するマスク行列の列次数分布に基づいて、当該マスク行列の列の重み位置を決定する重み位置決定ステップと、
を含み、
前記検査行列生成ステップでは、最初に生成する検査行列を、前記符号化率１／２以下に対応した検査行列とすることを特徴とする検査行列生成方法。
【請求項２】
前記検査行列生成ステップでは、最後に生成する検査行列を、符号化率１／３未満に対応する検査行列とすることを特徴とする請求項１に記載の検査行列生成方法。
【請求項３】
前記重み位置決定ステップでは、
列次数が小さいことに起因して発生する誤りの確率に基づいて、マスク行列生成処理を、列次数の大きい列と小さい列に分けて行うこととし、
列次数の小さい列については、「同一列内の重みの間隔を２行以上離す」という第１の条件および「乱数に基づいて配置する」という第２の条件を満たすように、マスク行列の列の重み位置を決定することを特徴とする請求項２に記載の検査行列生成方法。
【請求項４】
前記重み位置決定ステップでは、前記第２の条件を満たすように、
所定の方法で乱数列を生成し、
当該乱数列において差分が１の要素が存在する場合に、一方の要素を乱数列の最後に移動することにより、要素間の差分が２以上となる擬似乱数系列を生成し、
当該擬似乱数系列を列次数毎に分割して、それぞれを列重みの行位置番号とすることを特徴とする請求項３に記載の検査行列生成方法。
【請求項５】
前記重み位置決定ステップでは、列次数分布における列次数の降順に、マスク行列の列を配置することを特徴とする請求項３に記載の検査行列生成方法。
【請求項６】
前記重み位置決定ステップでは、列次数分布における列次数の降順に、マスク行列の列を配置することを特徴とする請求項４に記載の検査行列生成方法。
【請求項７】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化方法であって、
前記請求項２に記載の処理で生成された非正則なパリティ検査行列を用いて所定の情報ビットを符号化する符号化ステップ、
を含むことを特徴とする符号化方法。
【請求項８】
前記符号化ステップでは、情報長Ｋ，符号長Ｎ（情報ビットＡ＋パリティビットＰ）の符号化率Ｋ／Ｎの符号語に、情報ビットＡのうち列重みの重い順から選択した符号語ビットＢ（ビット長ｂ）を加えて、符号化率Ｋ／（Ｎ＋ｂ）の符号語「Ａ＋Ｐ＋Ｂ」を生成することを特徴とする請求項７に記載の符号化方法。
【請求項９】
前記符号化率Ｋ／Ｎを３／７とし、前記符号化率Ｋ／（Ｎ＋ｂ）を１／３とすることを特徴とすることを特徴とする請求項８に記載の符号化方法。
【請求項１０】
さらに低い符号化率が必要な場合は、前記「Ａ＋Ｐ＋Ｂ」を繰り返した符号語ビットを生成することを特徴とする請求項９に記載の符号化方法。
【請求項１１】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号用のパリティ検査行列を生成する通信装置であって、
前記請求項２に記載の処理で、ＬＤＧＭ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｇｅｎｅｒａｔｉｏｎ  Ｍａｔｒｉｘ）構造の非正則なパリティ検査行列を生成することを特徴とする通信装置。
【請求項１２】
誤り訂正技術として、ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号を採用する通信システムであって、
前記請求項７に記載の処理で、所定の情報ビットを符号化する送信装置と、
既知の処理で符号語を復号する受信装置と、
を備えることを特徴とする通信システム。
【請求項１３】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化器において、
前記請求項７に記載の処理で、所定の情報ビットを符号化する符号化手段、
を備えることを特徴とする符号化器。
【請求項１４】
ＬＤＰＣ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ）符号用のパリティ検査行列を生成する検査行列生成方法において、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｇｅｎｅｒａｔｉｏｎ  Ｍａｔｒｉｘ）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含むことを特徴とする検査行列生成方法。
【国際調査報告】
2008016117.tif 000034
2008016117.tif 000035