(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法において、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含む検査行列生成方法であって、
前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする検査行列生成方法。
【請求項２】
ＬＤＰＣ（Low-Density  Parity  Check）符号用の既知の非正則なパリティ検査行列を用いて、複数の符号化率に対応する場合の検査行列生成方法であって、
前記既知の非正則なパリティ検査行列の列次数分布を制約条件として密度発展法を実行し、当該密度発展法の実行により得られる列次数分布に基づいて生成した行列を、前記既知の非正則なパリティ検査行列に連結することにより、所望の符号化率に対応したパリティ検査行列を生成することを特徴とする検査行列生成方法。
【請求項３】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を用いて所定の情報ビットを符号化する符号化方法であって、
ｐ行×ｐ列の巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＰＣ（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  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
前記検査行列生成ステップにて生成された非正則なパリティ検査行列を用いて所定の情報ビットを符号化する符号化ステップと、
を含み、
前記符号化ステップでは、「情報長Ｋ／巡回置換行列の個数ｒ」において切り上げした整数値をｐに選び、さらに、「ｐ×ｒ−Ｋ」の数の既知の値を、前記非正則なパリティ検査行列における情報ビット部分にほぼ一様な間隔で挿入して、符号化することを特徴とする符号化方法。
【請求項６】
送信側において、前記請求項３、４または５にて符号化が行われた場合、
受信側では、前記パリティ検査行列の同一のビットに対応する値について、既知の値を確定して復号することを特徴とする復号方法。
【請求項７】
送信側において、
ｐ行×ｐ列の巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするための、複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＰＣ（Low-Density  Parity  Check）符号用のＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
前記検査行列生成ステップにて生成された非正則なパリティ検査行列を用いて所定の情報ビットを符号化する符号化ステップと、
を実行し、
受信側において、既知の「Overlapped巡回近似minアルゴリズム」を実行して復号処理を行う場合、
受信側の復号器は、列処理における加算処理（並列処理）の処理時間を把握し、解を得るタイミングに達した段階で次の列処理を行うことを特徴とする復号方法。
【請求項８】
ＬＤＰＣ（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における巡回置換行列の縦方向（行方向）の個数である。【００１０】
【数１】
0004602418.tif 000002
【００１１】
ただし、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐ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）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、を含む検査行列生成方法であって、前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする。
【発明の効果】
【００１９】
この発明によれば、広い符号化率に対応可能な、非正則なＬＤＰＣ符号用のパリティ検査行列を生成することができる、という効果を奏する。
【図面の簡単な説明】
【００２０】
【図１】図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む通信システムの構成例を示す図である。
【図２−１】図２−１は、符号生成における積和演算部の構成を示す図である。
【図２−２】図２−２は、図２−１に示す積和演算部を用いた符号生成部の構成例を示す図である。
【図３】図３は、マスク行列Ｚによりマスク後のイレギュラーなパリティ検査行列ＨMの構成例を示す図である。
【図４】図４は、符号構成法の性能比較をした結果を示す図である。
【図５】図５は、実施の形態１の符号構成法を示す図である。
【図６】図６は、システムで用意する一番低い符号化率をＲ0＝１／５とした場合の符号を示す図である。
【図７】図７は、実施の形態１の符号構成法の一例を示す図である。
【図８】図８は、実施の形態２の符号構成法の一例を示す図である。
【図９】図９は、実施の形態３の符号構成法の一例を示す図である。
【図１０】図１０は、実施の形態４の符号構成法の一例を示す図である。
【図１１】図１１は、ＬＤＰＣ復号器の構成例を示す図である。
【図１２】図１２は、擬似巡回符号の一例を示す図である。
【図１３】図１３は、イレギュラーＱＣ−ＬＤＰＣ符号の並列処理を示す図である。
【図１４】図１４は、既知のパリティ検査行列の一例を示す図である。
【図１５】図１５は、複数の符号化率に対応したＬＤＰＣ符号を構成する処理を示す図である。
【図１６】図１６は、符号化率１／３のパリティ検査行列の一例を示す図である。
【図１７】図１７は、符号化率１／３のパリティ検査行列の一例を示す図である。
【図１８】図１８は、本発明にかかる符号化処理／復号処理を移動体通信システムに適用した場合の構成例を示す図である。
【図１９】図１９は、ＱＣ符号のパリティ検査行列の一例を示す図である。
【図２０】図２０は、検査行列の一例をタナーグラフで表現した場合を示す図である。
【符号の説明】
【００２１】
１  ＬＤＰＣ符号化器
２  変調器
３  通信路
４  復調器
５  ＬＤＰＣ復号器
５１  積和演算部
【発明を実施するための最良の形態】
【００２２】
以下に、本発明にかかる検査行列生成方法、符号化方法および復号方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。【００２３】
実施の形態１．
図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ＬＤＰＣ符号化器１と変調器２を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とＬＤＰＣ復号器５を含む構成とする。【００２４】
ここで、ＬＤＰＣ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。【００２５】
送信装置内のＬＤＰＣ符号化器１では、本実施の形態の検査行列生成方法により生成されたパリティ検査行列、すなわち、後述する所定のマスキングルールに基づいてマスキング処理が行われたＭ行×Ｎ列のパリティ検査行列Ｈ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］）は、下記（４−１）式のように定義することができる。【００３２】
【数２−１】
0004602418.tif 000003
【００３３】
なお、ｈm,nは、パリティ検査行列ＨQCLにおいて、行番号ｍ，列番号ｎの要素を表す。また、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。たとえば、Ｉ（１）は、下記（４−２）式のように表すことができる。【００３４】
【数２−２】
0004602418.tif 000004
【００３５】
上記パリティ検査行列ＨQCLは、左側の行列（情報ビットに対応する部分）が、上記（２）式で示したＱＣ符号のパリティ検査行列と同一の擬似巡回行列ＨQCであり、右側の行列（パリティビットに対応する部分）が、下記（５−１）式または（５−２）式に示すＩ（０）を階段状に配置した行列ＨTまたはＨDである。【００３６】
【数３−１】
0004602418.tif 000005
【００３７】
【数３−２】
0004602418.tif 000006
【００３８】
ただし、上記階段状の構造で用いている巡回置換行列は、Ｉ（０）に限定しているわけではなく、任意のＩ（ｓ｜ｓ∈［０，ｐ−１］）の組み合わせでもよい。【００３９】
また、上記ＬＤＧＭ構造とは、上記（４−１）式に示す行列のように、パリティ検査行列の一部を下三角行列にした構造のことをいう。この構造を用いることにより、生成行列Ｇを用いずに符号化を容易に実現できる。たとえば、組織符号語ｖを下記（６）式のように表し、情報メッセージｕ＝（ｕ1，ｕ2，…，ｕK）が与えられた場合、パリティ要素ｐm＝（ｐ1，ｐ2，…，ｐM）は、「ＨQCL・ｖT＝０」を満たすように、すなわち、下記（７）式のように生成する。【００４０】
ｖ＝（ｖ1，ｖ2，…，ｖK，ｖK+1，ｖK+2，…，ｖN）
＝（ｕ1，ｕ2，…，ｕK，ｐ1，ｐ2，…，ｐM）                …（６）
ただし、Ｎ＝Ｋ＋Ｍである。【００４１】
【数４】
0004602418.tif 000007
【００４２】
さらに、本実施の形態においては、上記（４−１）式のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、特定の規則性を設けている。具体的には、パリティ検査行列ＨQCLの左側の擬似巡回行列ＨQC部分において、ｐ0,lを任意の整数とした場合、行番号ｊ（＝０，１，２，…Ｊ−１），列番号ｌ（＝０，１，２，…Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、下記（８−１）式，下記（８−２）式，下記（８−３）式または（８−４）式となる規則性を設ける。【００４３】
ｐj,l＝ｐ0,l（ｊ＋１）ｍｏｄ  ｐ                    …（８−１）
ｐj,l＝（ｐ0,l（ｊ＋１）ｍｏｄ  ｐA）ｍｏｄ  ｐ      …（８−２）
ｐj,l＝（（ｐ−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐ        …（８−３）
ｐj,l＝（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ
ｐA＝１５７
０≦ｊ≦Ｊ−１
ｐ：ｐｒｉｍｅ  ｎｕｍｂｅｒ
…（８−４）【００４４】
なお、上記（８−１）式および（８−２）式は、ｐ0,l，ｊおよびｐの関数であるため、巡回置換行列の１行目の“１”の列位置さえ決まれば他の行における“１”の位置も計算により算出できる特徴がある。しかしながら、情報長はｋ＝ｐ×Ｌにより決まるため、情報長を変える際には、ｐを変化させる必要がある。そのｐの値により巡回置換行列の２行目以降のｐj,lの値が変動し、それにより、ループの分布において小さいループの個数が増え、性能を劣化させる場合がある。たとえば、ｐの値が小さい場合に小さいループの個数が増える。一方、上記（８−３）式，（８−４）式は、ｐ0,l，ｊ，ｐおよびｐAの関数である。ｐAは、任意の値でもよいが、システムが要求するＭＡＸの情報長のときに最も良い性能が得られるように決定されることが望ましい。ＭＡＸの情報長を固定値Ｌで割って求められる最大値をｐAに設定することで、最も良い性能が得られる。上記（８−３）式，（８−４）式では、上記（８−１）式，（８−２）式におけるｐ＝ｐAにおいて小さいループが極力少なくなるように探索したｐ0,lを用いており、その結果、１行目以外のｐj,lの値も小さいループを構成するために重要である。したがって、上記（８−３）式，（８−４）式では、ｐ＝ｐAにおけるｐj,lの値をできるだけ維持し、ｐj,lが情報長できまるｐ以上の場合だけｐj,lを変化させる式となっている。この場合、ｐj,lは、部分的な変化のみとなり、劣化する確率を下げる効果がある。また、上記「ｐA＝１５７」は、情報長Ｋ＝ｐ×Ｌ（Ｌ＝３６）が５０００〜６０００近辺を想定した場合の値となる。【００４５】
たとえば、上記（８−４）式を用い、ｐA＝１５７，Ｌ＝３６とした場合、ｐ0,lの一例として下記（９）式のように表すことができる。
｛ｐ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｝
＝｛11,8,73,16,143,48,143,150,31,38,22,115,135,116,55,55,84,13,12,116,131,33,3,7,115,43,11,2,11,17,1,31,15,7,2,54｝
…（９）【００４６】
つづいて、本実施の形態の検査行列生成方法における特徴的な処理である、パリティ検査行列ＨQCLに対するマスク処理について説明する。【００４７】
たとえば、上記（４−１）式に示す左側の行列を、下記（１０−１）式に示すように、Ｊ×Ｌの擬似巡回行列ＨQCと表し、マスク行列Ｚ（＝［ｚj,l］）をＧＦ（２）上のＪ行×Ｌ列の行列とした場合、後述する所定のルールを適用すると、マスク処理後の行列ＨMQCは、下記（１０−２）式のように表すことができる。【００４８】
【数５−１】
0004602418.tif 000008
【００４９】
【数５−２】
0004602418.tif 000009
【００５０】
なお、上記（１０−２）式におけるｚj,lＩ（ｐj,l）は、下記（１１）式のように定義される。【００５１】
【数６】
0004602418.tif 000010
【００５２】
上記０行列は、ｐ行×ｐ列の０行列である。また、行列ＨMQCは、擬似巡回行列ＨQCをマスク行列Ｚの０要素によりマスクし、重み分布を非一様（イレギュラー）にした行列であり、また、行列ＨMQCの巡回置換行列の分布は、マスク行列Ｚの次数分布と同じである。【００５３】
ただし、上記重み分布を非一様にする場合のマスク行列Ｚの重み分布は、既知の密度発展法で求めることとする。たとえば、７２行×３６列のマスク行列は、密度発展法による列次数分布に基づいて、下記（１２）式のように表すことができる。【００５４】
【数７】
0004602418.tif 000011
【００５５】
また、マスク行列ＺAは、下記（１３）式に示すような行列となる。【００５６】
【数８】
0004602418.tif 000012
【００５７】
また、ＺA（１：３６，２：１３）は、ＺAのサブマトリックスであり、１行〜３６行と２行〜１３列で構成されるサブマトリックスを示す。【００５８】
したがって、本実施の形態において、最終的に求めるイレギュラーなパリティ検査行列ＨMは、たとえば、７２行×３６列のマスク行列Ｚ、７２（行番号ｊは０〜７１）×３６（列番号ｌは０〜３５）の擬似巡回行列ＨQC、および７２（行番号ｊは０〜７１）×３６（列番号ｌは０〜３５）のＨTを用いて、下記（１４）式のように表すことができる。【００５９】
ＨM＝［Ｚ×ＨQC｜ＨT］
＝［ＨMQC｜ＨT］                              …（１４）【００６０】
すなわち、ＬＤＰＣ符号Ｃを生成するためのパリティ検査行列ＨMQCは、マスク行列Ｚと擬似巡回行列ＨQCの行番号ｊ＝０の巡回置換行列の値の設計により、与えられる。【００６１】
つづいて、レギュラーなパリティ検査行列ＨMを用いて、生成行列Ｇを用いずに符号化を実現する場合の実装例を以下に示し、その動作を説明する。なお、ここでは、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを、下記（１５−１）式に示す行列とする。【００６２】
【数９−１】
0004602418.tif 000013
【００６３】
また、上記（１５−１）式に示す行列をマスク化したイレギュラーなパリティ検査行列ＨMを、下記（１５−２）式に示す行列とする。【００６４】
【数９−２】
0004602418.tif 000014
【００６５】
また、情報メッセージをｕ＝（ｕp,1  ｕp,2）＝（０１１００  １１００１）とする。ただし、ｕp,lは、ｕをｐビット単位で区切り、ｌに対して昇順に番号を付したものである。【００６６】
ここで、生成行列Ｇを用いずに符号を生成する場合の処理として、ｐ行分のマスク処理後の行列ＨMQCと情報メッセージｕとの積和演算について説明する。【００６７】
図２−１は、符号生成における積和演算部５１の構成を示す図である。ここでは、基準クロックを１クロックとし、図中、遅延素子（Ｄ）６１は１クロック単位で動作し、遅延素子（Ｄ）６２はｐクロック単位で動作する（この例ではｐ＝５）。また、列カウンタ６３はｐクロック単位で動作し、行カウンタ６４はＬ・ｐクロック単位で動作する（この例ではＬ＝２）。【００６８】
図２−１において、擬似巡回行列ＨQCのｊ行ｌ列目の巡回置換行列は、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ），「０≦ｊ≦Ｊ−１」，「０≦ｌ≦Ｌ−１」，ｐA＝１５７であるため、行カウンタ６４にてｊを昇順にＬ・ｐクロック単位でカウントし、列カウンタ６３にて「ｌ＋１」を昇順にｐクロック単位でカウントし、演算部７５にて（ｐA−ｐ0,l）を求め、乗算器６５にて「（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ」を算出し、その値をセレクタ６６に入力し、長さｐのレジスタ６７の“１”の位置を決めることにより、ｊ行ｌ列目の巡回置換行列の１行目の“１”の位置をセットする。【００６９】
一方、情報メッセージｕについては、長さｐ毎に区切り、遅延素子６２を介してｐクロック単位でレジスタ６８，６９に順に入力する。そして、加算器７０にてレジスタ６９内の長さｐの情報メッセージｕとレジスタ６７内のビット列とのＥＸＯＲを計算し、加算器７２にてＥＸＯＲ演算結果の各ビットの総和を計算する。この処理により、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ）の１行目と情報メッセージのｕp,lとの積和計算が実現できる。つぎに、レジスタ６７を、遅延素子６１を用いてシフトすることにより、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ）の２行目が生成でき、同様に、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ）の２行目と情報メッセージのup,lとの積和計算が実現できる。その後、この処理をｐ回にわたって繰り返し実行することにより、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ）のｐ行分の積和計算結果ｐp,j´が得られる。なお、ｐp,j´はｊ行目の巡回置換行列全ての積和計算結果のｐビットを意味する。【００７０】
つぎに、ｌ＝０からｌ＝Ｌ−１まで、Ｉ（（（（ｐA−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐA）ｍｏｄ  ｐ）とｕp,lとの積和を計算するために、遅延素子６２と加算器７２により、Ｌ回にわたって繰り返しＥＸＯＲ演算を行う。この操作をｊ＝０からｊ＝Ｊ−１まで繰り返し実行し、マスク処理後の行列ＨMQCとｕとの積和計算結果果ｐp,j´を得る。なお、セレクタ７３では、ｚj,l＝０のとき０を選択出力し、ｚj,l＝１のとき加算器７１出力を選択出力する。【００７１】
また、図２−２は、図２−１に示す積和演算部５１を用いた符号生成部の構成例を示す図である。ここでは、遅延素子（Ｄ）７４がＬ・ｐクロック単位で動作する。図２−２において、ｐビット単位に昇順にｊに番号を付した系列（パリティビット）をｐp,jとすると、系列ｐp,jは、遅延素子７４と加算器７５によるＥＸＯＲ演算で得られる。すなわち、「ｐp,j＝ｐp,j´＋ｐp,j-1´」を計算する。なお、ｐp,0´＝０である。【００７２】
なお、上記擬似巡回行列ＨQCをマスク行列Ｚの０要素によりマスクする場合のマスキングルールについては、先に出願した「特願２００５−３６７０７７」記載のルールを適用する。【００７３】
つづいて、本実施の形態においては、さらに、符号化率１／５までの符号構成法について説明する。システム構成については図１と同様である。ここでは、「特願２００５−３６７０７７」の内容に基づいて、符号化率１／５以上の符号化を実現する。【００７４】
具体的には、符号化率１／５に対応する１４４（行番号ｊは０〜１４３）×３６（列番号ｌは０〜３５）の擬似巡回行列ＨQCを、１４４行×３６列のマスク行列Ｚの０要素によりマスクする場合のマスキングルールを説明する。ここでは、本実施の形態の通信装置が、上記１４４×３６の擬似巡回行列ＨQCを非正則（イレギュラー）にするためのマスク行列Ｚを、規則的なマスキングルールにより生成する。【００７５】
なお、マスク行列Ｚ生成後、最終的に求めるイレギュラーなパリティ検査行列ＨMは、たとえば、１４４行×３６列のマスク行列Ｚ、上記１４４×３６の擬似巡回行列ＨQC、および１４４（行番号ｊは０〜１４３）×１４４（列番号ｌは０〜１４３）のＨTを用いて、下記（１６）式のように表すことができる。【００７６】
ＨM＝［Ｚ×ＨQC｜ＨT］
＝［ＨMQC｜ＨT］                          …（１６）【００７７】
また、上記ＨTを下記（１７）式のように定義し、さらに、ＨT内のＴDを下記（１８）式のように定義する。【００７８】
【数１０】
0004602418.tif 000015
【００７９】
【数１１】
0004602418.tif 000016
【００８０】
また、符号化率１／２の符号に対応するイレギュラーなパリティ検査行列を「ＨM(1/2)＝［ＺA×ＨQC(1/2)｜ＨT(1/2)］」と仮定する。ただし、ＺA（＝ＺA(1/2)）は３６行×３６列のマスク行列であり、ＨQC(1/2)は、上記擬似巡回行列ＨQCにおける上から１／４の３６（行番号ｊは０〜３５）×３６（列番号ｌは０〜３５）の擬似巡回行列を表し、ＨT(1/2)は上記ＴDである。また、符号化率１／３、１／４，１／５に対応して、イレギュラーなパリティ検査行列をＨM(1/3)，ＨM(1/4)，ＨM(1/5)（＝ＨM）と表し、マスク行列をＺA(1/3)，ＺA(1/4)，ＺA(1/5)（＝Ｚ）と表し、擬似巡回行列をＨQC(1/3)，ＨQC(1/4)，ＨQC(1/5)（＝ＨQC）と表し、ＨT(1/3)，ＨT(1/4)，ＨT(1/5)（＝ＨT）と表す。【００８１】
たとえば、上記処理にて生成されたマスク行列Ｚは、下記（１９）式のように表すことができる。【００８２】
【数１２】
0004602418.tif 000017
【００８３】
図３は、上記のように生成したマスク行列Ｚによりマスク後の、イレギュラーなパリティ検査行列ＨMの構成例を示す図である。【００８４】
このように、本実施の形態においては、マスク行列Ｚを、符号化率１／２に対応するマスク行列ＺAの部分行列のみを使って構成しているため、符号化率に応じてマスク行列が大きくなった場合であっても、マスク行列を記憶するためのメモリを少なくすることができる。【００８５】
また、符号化率に応じた各マスク行列は、列方向に同一パターンができないように、マスク行列ＺAの部分行列をシフトしながら使用している。具体的には、マスク行列ＺAの部分行列を列次数の重い部分行列（重み１４）と軽い部分行列（重み４以下）とに分け、それぞれをシフトしながら用いている。たとえば、マスク行列ＺAにおいて、ＺA（１：３６，２：１３）はＺAの部分行列であるが、マスク行列ＺA(1/3)においては、これを列単位で左シフトさせ、シフト後のＺA（１：３６，３：１４）をマスク行列ＺAのＺA（１：３６，２：１３）の下に連結させている。そして、マスク行列ＺA(1/4)，ＺA(1/5)についても、列方向に同一パターンができないように、マスク行列ＺAの部分行列をシフトしながら使用する。これにより、ＨTを用いた場合に発生しやすい小さいループを、回避することができる。【００８６】
つづいて、前述のイレギュラーなパリティ検査行列ＨMを用いて、複数の符号化率に対応したＬＤＰＣ符号を構成する場合について説明する。【００８７】
たとえば、前述の符号構成法によって生成され、ＭとＮで規定された符号における符号化率の下限は、１／３から１／６の間が望ましい。また、それ以下の符号化率を実現するためには、上記符号化率１／５の場合の符号構成法と同様の符号構成法よりも、後述する繰り返し送信を用いて実現する方が良好な性能が得られる。【００８８】
図４は、上記符号化率１／５の場合の符号構成法と同様の方法で符号化率１／１０まで作成した場合と、符号語の繰り返し送信を用いた場合（符号化率１／５までは上記符号を用い、それより小さい符号化率では繰り返し送信を用いた場合）と、の性能比較をした結果を示す図であり、ここでは、繰り返し送信を用いた方が良い性能となることがわかる。なお、図４において、符号は情報長１３５２ビットのＬＤＰＣ符号を用いている。また、通信路はＡＷＧＮで、変調はＢＰＳＫを仮定している。【００８９】
また、図５は、本実施の形態の符号構成法の一例を示す図であり、たとえば、符号化率０．５の符号を基準符号語とし、それよりも高い符号化率（＝０．７５）の符号語を生成する場合はパリティのパンクチャを行う。なお、この際の復号には符号化率１／２の検査行列を使って、パンクチャリングビットに対応する受信ＬＬＲに０を挿入し、通常のＬＤＰＣ復号を行えばよい。一方、低い符号化率（＝１／３）の符号語を生成する場合は、パリティを追加している。この際の復号には、図３に示すように、符号化率に対応した検査行列ＨMの部分行列のみを用いて復号する。【００９０】
ここで、複数の符号化率に対応したＬＤＰＣ符号の構成法を具体的に説明する。たとえば、システムで用意する一番低い符号化率をＲ0＝１／３以下とする。図６は、たとえば、システムで用意する一番低い符号化率をＲ0＝１／５とした場合の符号を示す図である。【００９１】
たとえば、符号化率Ｒ0＝１／５に対応する符号がメモリに記憶され、符号化率Ｒ1の符号を構成する場合、符号化率Ｒ1が１／２未満であれば、すなわち、符号化率Ｒ1が１／２〜１／５の間であれば、パリティビットを符号語の最後尾から順にパンクチャする。【００９２】
一方で、たとえば、１／５以下の符号化率が必要となった場合、本実施の形態では、図７に示すように、情報長Ｋ，符号長Ｎの符号化率Ｋ／Ｎ＝１／５の符号語（図７中のＡ＋パリティビット）に、列重みの重い順から選択した符号語ビットＢ（長さｂ：各列に対応するビットの情報はＡと同じ）を加えて符号化率Ｋ／（Ｎ＋ｂ）の符号語を生成する。たとえば、ｂ＝Ｋの場合、符号化率は１／６となり、ｂ＝Ｎの場合は、符号化率１／１０となる。図７は、１／５以下の符号化率が必要となった場合における、本実施の形態の符号構成法を示す図である。【００９３】
また、ｂ＝Ｎのように同一の符号語が繰り返し２回にわたって送られ、さらにそれ以上に低い符号化率が必要な場合は、再度列重みの重い順から選択した当該低い符号化率に対応したビット数の符号語ビットを繰り返し送ることとした。これにより、さらに低い符号化率でも実現可能とする。【００９４】
そして、上記の方法により符号化された符号語が通信路を通って受信機で受信され、復号器が誤りを訂正する際に符号語の一部あるいは全てが重複した場合には、その重複したビットの受信値を、重複した個数分だけ加算平均し、その結果を復号器に渡すこととした。また、列重みの重い列に対応する符号語ビットは復号性能がよくなることが知られている。したがって、本実施の形態では、上記処理によりノイズ成分の分散値を下げることができ、それに伴って信頼度が上がる（対応するビットの誤り確率が下がり）ため、復号性能を向上させることができる。【００９５】
なお、本実施の形態において、巡回置換行列のｐが奇数（２以外）の素数であることとして記載したが、ｐについてはこれに限らず、奇数を選んでもよい。この場合、高符号化率のパンクチャ時に性能が劣化する可能性があるが、劣化は僅かである。一方で、素数については、計算量が増加することを回避するためにテーブルを持ち予め記憶しておく必要があるが、奇数の場合はその値を記憶しておく必要はない。【００９６】
実施の形態２．
つづいて、実施の形態２の符号構成法について説明する。ここでは、前述した実施の形態１と異なる処理について説明する。【００９７】
前述したＬＤＰＣ符号用のパリティ検査行列において、巡回置換行列のｐ（奇数または２以外の素数）を可変にすると、情報長Ｋ＝ｐ×ｒ（ｒは単位行列の数：実施の形態１ではｒ＝３６）を可変にすることができる。一方で、情報長Ｋがｐ×ｒで表現できないような場合は、図８に示すように符号語を構成する。【００９８】
たとえば、ＬＤＰＣ符号化器１では、Ｋ／ｒにおいて切り上げした整数値をｐに選び、「（Ｋ／ｒにおいて切り上げした整数ｐ）×ｒ−Ｋ」の数だけ、パリティ検査行列における列次数の重い箇所に対応するビット順に、既知の値の“０”か“１”を挿入して符号化する。そして、復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【００９９】
これにより、信頼度の最も高い（１００％誤り無し）既知の値を、列次数の重いビットに割り振ることができるため、復号性能がよくなる。【０１００】
また、実施の形態１にて生成したＬＤＰＣ符号用のイレギュラーなパリティ検査行列を用いて符号化し、符号長Ｎの符号語を生成する際に、パリティ検査行列の行数Ｍと列数Ｎによって決まる符号化率（Ｎ−Ｍ）／Ｎ以下の符号化率を実現する場合についても、図８に示すように符号語を構成する。【０１０１】
たとえば、上記同様、情報ビットに対応するパリティ検査行列の中で、列次数の重い順に、既知の値の“０”か“１”を挿入して符号化する。これにより、容易に低符号化率の符号語を生成することができる。復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【０１０２】
これにより、意図的に低符号化率の符号を構成でき、信頼度の最も高い（１００％誤り無し）既知の値を列次数の重いビットに割り振ることができるため、列次数の重いビットの復号性能が全体の復号性能に大きく影響する場合には、良好な復号性能が得られる。【０１０３】
実施の形態３．
つづいて、実施の形態３の符号構成法について説明する。ここでは、前述した実施の形態１および２と異なる処理について説明する。【０１０４】
実施の形態１にて生成したＬＤＰＣ符号用のパリティ検査行列において、巡回置換行列のｐ（奇数または２以外の素数）を可変にすると、情報長Ｋ＝ｐ×ｒ（ｒは単位行列の数：実施の形態１ではｒ＝３６）を可変にすることができる。一方で、情報長Ｋがｐ×ｒで表現できないような場合は、図９に示すように符号語を構成する。【０１０５】
たとえば、ＬＤＰＣ符号化器１では、Ｋ／ｒにおいて切り上げした整数値をｐに選び、「（Ｋ／ｒにおいて切り上げした整数ｐ）×ｒ−Ｋ」の数だけ、検査行列における情報ビット部分（マスク処理後の行列ＨMQCの列に対応するビット部分）の列次数の軽い箇所に対応するビット順に、既知の値の“０”か“１”を挿入して符号化する。そして、復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【０１０６】
誤り分布において、列次数の軽い箇所に対応するビットの影響力が大きい場合、すなわち、劣化の要因が列次数の軽い箇所にあるような場合は、列次数の軽い箇所に対応するビット順に、既知の値の“０”か“１”を挿入して符号化したほうが、性能がよくなる。【０１０７】
また、実施の形態１にて生成したＬＤＰＣ符号用のイレギュラーなパリティ検査行列を用いて符号化し、符号長Ｎの符号語を生成する際に、パリティ検査行列の行数Ｍと列数Ｎによって決まる符号化率（Ｎ−Ｍ）／Ｎ以下の符号化率を実現する場合についても、図９に示すように符号語を構成する。【０１０８】
たとえば、上記同様、情報ビットに対応するパリティ検査行列の中で、列次数の軽い順に、既知の値の“０”か“１”を挿入して符号化する。これにより、容易に低符号化率の符号語を生成することができる。復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【０１０９】
これにより、意図的に低符号化率の符号を構成でき、さらに、列次数の軽いビットの復号性能が全体の復号性能に大きく影響する場合、すなわち、劣化の要因が列次数の軽い箇所にあるような場合であっても、列次数の軽いビットを既知データで確定することができるので、良好な復号性能を得ることができる。【０１１０】
実施の形態４．
つづいて、実施の形態４の符号構成法について説明する。ここでは、前述した実施の形態１、２または３と異なる処理について説明する。【０１１１】
実施の形態１にて生成したＬＤＰＣ符号用のパリティ検査行列において、巡回置換行列のｐ（奇数または２以外の素数）を可変にすると、情報長Ｋ＝ｐ×ｒ（ｒは単位行列の数：実施の形態１ではｒ＝３６）を可変にすることができる。一方で、情報長Ｋがｐ×ｒで表現できないような場合は、図１０に示すように符号語を構成する。【０１１２】
たとえば、ＬＤＰＣ符号化器１では、Ｋ／ｒにおいて切り上げした整数値をｐに選び、「（Ｋ／ｒにおいて切り上げした整数ｐ）×ｒ−Ｋ」の数だけ、検査行列における情報ビット部分（マスク処理後の行列ＨMQCの列に対応するビット部分）にほぼ一様な間隔で、既知の値の“０”か“１”を挿入して符号化する。そして、復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【０１１３】
誤り分布において、劣化の要因が列次数の重い軽いに起因しないような場合は、検査行列における情報ビット部分（マスク処理後の行列ＨMQCの列に対応するビット部分）にほぼ一様な間隔で、既知の値の“０”か“１”を挿入して符号化したほうが、良好な性能が得られる場合がある。【０１１４】
また、前述した実施の形態２では、パリティ検査行列の行数Ｍと列数Ｎによって決まる符号化率（Ｎ−Ｍ）／Ｎ以下の符号化率を用意するために、既知の値を列次数の重い列に対応するビットに割り振ったが、一方で、既知の値の数が多すぎた場合には、性能劣化を起こすことがある。したがって、本実施の形態では、以下の方法により、低符号化率を実現する。【０１１５】
たとえば、前述したＬＤＰＣ符号用のイレギュラーなパリティ検査行列を用いて符号化し、符号長Ｎの符号語を生成する際に、パリティ検査行列の行数Ｍと列数Ｎによって決まる符号化率（Ｎ−Ｍ）／Ｎ以下の符号化率を実現する場合についても、図１０に示すように符号語を構成する。【０１１６】
具体的には、上記同様、検査行列における情報ビット部分（マスク処理後の行列ＨMQCの列に対応するビット部分）にほぼ一様な間隔で、既知の値の“０”か“１”を挿入して符号化する。これにより、容易に低符号化率の符号後を生成することができる。復号側では、パリティ検査行列の同一のビットに対応する値については、既知の値の“０”か“１”を確定して復号する。【０１１７】
一例として、情報ビット数が検査行列の情報ビットに対応する列数の１／２である場合、情報ビット系列をｕ＝｛ｕ1，ｕ2，…，ｕk｝とする、既知の値“０”を挿入した情報系列ｕ´はｕ´＝｛ｕ1，０，ｕ2，０，ｕ3，０，…，ｕk，０｝となる。前述したように符号化率１／５の符号では、この操作により符号化率が１／１０となる。また、情報ビット数を検査行列の情報ビットに対応する列数の１／３とした場合は、既知数が大きくても劣化が発生しない場合がある。このように、本実施の形態においては、容易に低符号化率の符号を用意でき、さらに、既知数が大きい場合の劣化を抑えることができる。【０１１８】
実施の形態５．
実施の形態５では、実施の形態１にて生成したイレギュラーなパリティ検査行列ＨMを用いた符号化処理、に対応する復号処理について説明する。【０１１９】
本実施の形態のＬＤＰＣ復号は、行処理と列処理による確率情報（ＬＬＲ）の算出および更新を、１ビットずつまたは予め定めた複数ビットずつ行う場合に適用可能であり、たとえば、演算処理を並列化することにより、繰り返し回数の低減を図る。なお、本実施の形態においては、途中結果保持部のＢmn(i)およびＳmを、並列化の数にかかわらず１セットとし、並列化されたすべての処理部が同一のＢmnCおよびＳmを更新していく、いわゆる「Overlapped」されたＢmnCおよびＳmを用いた「巡回近似minアルゴリズム」を実行する。以降、本実施の形態の復号アルゴリズムを、「Overlapped巡回近似minアルゴリズム」と呼ぶ。【０１２０】
ここで、本実施の形態の受信装置において実施される「Overlapped巡回近似minアルゴリズム」を以下に示す。【０１２１】
（初期化ステップ）
まず、繰り返し回数ｌ＝１および最大繰り返し回数ｌmaxを設定する。さらに、初期時におけるｍ行目の最小ｋ値のＬＬＲをβmn(i)(0)として、受信ＬＬＲ：λnを入力し、下記（４３）式に示すようにＢmn(i)Cを求める。また、初期時におけるｍ行目のＬＬＲ：βmn(0)の符号として、ｓｇｎ（λn）を入力し、下記（２０）式に示すようにＳmを求める。【０１２２】
【数１３】
0004602418.tif 000018
【０１２３】
ただし、Ｂmn(i)Cは、ｍ行目の最小ｋ値のＬＬＲ：βmn(i)の絶対値であり、並列処理の際に共通に用いられる。また、ｎ（ｉ）は、Ｂmn(i)Cの中で最小ｉ番目のＬＬＲの列番号である。【０１２４】
（行処理ステップ）
つぎに、行処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、チェックノードｍからビットノードｎへ送るビットｎの繰り返しｌ回目のＬＬＲ：αmn(l)を、下記（２１）式により更新する。なお、Ｇは並列数であり、ＮGは並列化された各復号回路が処理する列数である。また、Ｇ・Ｎg＝Ｎである。また、本実施の形態においては、各行処理の開始列は任意とし、最終列まで処理が終了した段階で、再度最初の列から巡回的に復号処理を行う。【０１２５】
【数１４】
0004602418.tif 000019
【０１２６】
具体的には、たとえば、列数：ＮG毎にＧ個に分割された各列郡にそれぞれ割り当てられたＧ個の行処理部が、並列に行処理を実行する。【０１２７】
（列処理ステップ）
つぎに、列処理として、０≦ｇ≦Ｇ−１，ｇ・ＮG＋１≦ｎ≦（ｇ＋１）・ＮGおよび各ｍについて、ビットノードｎからチェックノードｍへ送るビットｎの繰り返しｌ回目のＬＬＲ：βmn(l)を、下記（２２）式により更新する。すなわち、本実施の形態においては、上記のように並列に行処理が行われた後の各列について、並列に、下記（２２）式に示す列処理を実行する。【０１２８】
【数１５】
0004602418.tif 000020
【０１２９】
また、各ｎについて、硬判定のための、ビットｎの繰り返しｌ回目の事後値βn(l)を下記（２３）式により更新する。【０１３０】
【数１６】
0004602418.tif 000021
【０１３１】
（停止規範）
その後、たとえば、ビットｎの繰り返しｌ回目の事後値βn(l)が「βn(l)＞０」の場合には、復号結果を「ｘn´＝１」とし（ｘ´は元の送信信号ｘに対応）、一方、「βn(l)≦０」の場合には、復号結果を「ｘn´＝０」とし、復号結果ｘ´＝（ｘ1´，ｘ2´，…，ｘN´）を得る。【０１３２】
そして、パリティ検査の結果が「Ｈｘ´＝０」または繰り返し回数が「ｌ＝ｌmax」の場合（いずれか１つの条件を満たしている場合）に、そのときの復号結果ｘ´を出力する。なお、上記２つの条件のどちらも満たしていない場合は、「ｌ＝ｌ＋１」とし、上記行処理に戻り、以降、順に演算を実行する。【０１３３】
つづいて、上記「Overlapped巡回近似minアルゴリズム」を実現する実施の形態５のＬＤＰＣ復号器５の構成および動作について説明する。【０１３４】
図１１は、本実施の形態のＬＤＰＣ復号器５の構成例を示す図であり、受信情報から受信ＬＬＲを算出する受信ＬＬＲ算出部１１と復号処理を行う復号コア部１２ａで構成されている。また、復号コア部１２ａは、復号の途中結果（中間値）を保持しておくためのメモリで構成された途中結果保持部２１ａと、行処理（並列処理）を実行する行処理部２２−１〜２２−Ｇと、列処理（並列処理）を実行する列処理部２３−１〜２３−Ｇと、復号処理の停止規範として、列処理における事後値の硬判定およびパリティ検査結果の正誤判定を行う復号結果判定部２４と、復号の繰り返し制御を行う制御部２５ａと、を備えている。【０１３５】
図１１において、本実施の形態のＬＤＰＣ復号器５は、各行処理部および各列処理部が並列に処理を行う際、上記（２０）式，（２１）式，（２２）式に従って、途中結果保持部２１ａのＢmnCおよびＳmを共通に使用し、それぞれが更新する。この並列処理により、ＢmnCおよびＳmは、並列数に応じて急速に更新され、それに伴って、復号の繰り返し回数を大幅に削減することができる。【０１３６】
つづいて、前述した実施の形態１〜４の処理により構成された符号に対する復号処理として、たとえば、「Overlapped巡回近似minアルゴリズム」を用いた場合の効果について説明する。【０１３７】
たとえば、上記のような並列処理において、同一クロックで同一行の演算が発生し、同一バッファを参照するような問題が生じる場合、従来は、追加回路による対策が必要であった。これは「Overlapped巡回近似minアルゴリズム」のみならず、如何なる復号法においても同様であった。【０１３８】
この問題の解決のために、本実施の形態においては、ｐ×ｐの巡回置換行列から成る擬似巡回行列をマスク化することにより生成されたパリティ検査行列の特徴を利用して、復号における並列処理の実施時に、行と列の重複が発生しないように並列処理の列グループを、G1=[0*p+1,1*p+1,2*p+1,…]，G2=[0*p+2,1*p+2,2*p+2,…]，G3=[0*p+3,1*p+3,2*p+3,…]，…に分割し、各グループの要素の最小値から順に全グループあるいは一部のグループを同時に実行する。【０１３９】
また、特定の列のグループの復号処理において、列に関連する行を並列に処理する。たとえば、図１２に示す擬似巡回符号の場合、G1=[1,6,11,16,21]，G2=[2,7,12,17,22]，G3=[3,8,13,18,23]，G4=[4,9,14,19,24]，G5=[5,10,15,20,25]に分割する。この際、G1，G2，G3，G4，G5は並列に処理するが、同時にそれぞれ各グループの最初の要素1,2,3,4,5の列が実行され、次に6,7,8,9,10の列が実行されるため、列の重複は発生しない。また、G1の最初の要素の列番号は１であるが、これに関連する行番号は１，６，１１であり、この３つの行は並行に処理できる。同時に、G2の最初の要素の列番号は2であるが、これに関連する行番号は２，７，１２であり、この３つの行も並行に処理でき、かつG1にて処理する行番号との重複はない。同様に、全グループにおいて、行および列の重複はないため、特別の追加回路がなくても、上記グループ分けにより重複なく並列処理が実行できる。【０１４０】
また、イレギュラーなマスク化擬似巡回行列を用いた際には、列処理の重い部分と軽い部分で処理時間の差異が発生する可能性がある。一般に、非正則のＬＤＰＣ符号で列次数が重いものと軽いものが混在した際に、列次数が重い箇所の列処理が支配的になり、高速化の支障になる問題がある。【０１４１】
たとえば、図１３に示すとおり、ＱＣ−ＬＤＰＣ符号での並列処理を巡回置換行列のサイズｐ単位で行う場合、その範囲では、全て同じ列次数なので列処理における加算処理（図１５のadditionに相当）の処理時間はｐ個全て一致する。また、行は一致しないので、行処理の衝突回避処理も必要としない。共通化したaddition回路のトーナメント方式の加算のタイミングは、列次数２以下，２〜３，４〜７，８〜１５，１６〜３１，３２〜６３で、それぞれタイミングＴ＝１，２，３，４，５，６で解が得られる。そのため、解が出るタイミングを制御して巡回行列単位で処理していけば、タイミングロスは発生しない。すなわち、列重みに応じて解の出力時間を把握し、解を得るタイミングに達したら次の列処理を行なえばよい。この方法により、列次数の重い箇所の列処理が支配的になる問題を回避することができる。【０１４２】
なお、本実施の形態においては、「Overlapped巡回近似minアルゴリズム」を並列処理する場合について記載したが、これに限らず、巡回置換行列から成る擬似巡回行列をマスク化することにより生成されたパリティ検査行列を利用して符号化が行われるシステムであれば、その他のＬＤＰＣ用復号法を並列処理する場合についても同様に適用可能である。【０１４３】
実施の形態６．
実施の形態１では、巡回置換行列Ｉ（ｐj,l）を一定のルールで構成した例を示したが、他の行列に適用してもよく、本実施の形態では、たとえば、一般に公開されている（ＺＴＥ  et  al,“Comparison  of  structured  LDPC  Codes  and  3GPP  Turbo  codes”、  3GPP  TSG  RAN  WG1  #43,R1-051360,Seoul,Korea  7th-11th,  Nov.2005）図１４に示すような符号化率１／３の行列を用いて、実施の形態１のように符号化率１／５を構成しても良い。なお、図１４中の数字はｐj,lの値を示しており、−１の場合はｐ×ｐの０行列を意味する。【０１４４】
具体的には、図１４に示す行列を符号化率１／３のＭ×Ｎの行列ＨCHとすると、２Ｍ×（５／３Ｎ）の行列ＨCH´を図１５のように構成する。Ａは巡回置換行列の組み合わせによる行列で構成され、単位行列Ｉを右下に２つ連結させ配置する。行列Ａの重み分布は密度発展法で導出する。この方法により、実施の形態１と同様に、ＬＤＰＣ用のパリティ検査行列を生成することができる。また、図１６のように構成することとしてもよい。巡回置換行列と０行列の組み合わせによるＭ×Ｍの行列ＨCMとＭ×Ｍの行列Ａにより、２Ｍ×３Ｍの行列ＨCM´を図１６のように構成する。行列ＨCMおよびＡの重み分布は密度発展法で導出する。また、右側の行列は、図１４の右側の行列と同様な構成とする。なお、行列内のＸの数値は任意の数値とする。この方法により、ＲＣ−ＬＤＰＣ符号を構成できる。または、図１７のようにしてもよい。巡回置換行列と０行列の組み合わせによるＭ×Ｍの行列ＨCMとＭ×Ｍの行列Ａにより、２Ｍ×３Ｍの行列ＨCM´を図１７のように構成する。行列ＨCMおよびＡの重み分布は密度発展法で導出する。また、右側の行列は、前述した（５−２）式を用いる。この方法により、ＲＣ−ＬＤＰＣ符号を構成できる。【０１４５】
なお、行列Ａの構成法は、本実施の形態のように巡回置換行列の任意の組み合わせによる行列で構成することとしてもよいし、前述した実施の形態１のように規則的なルールに基づいて構成することとしてもよい。また、複数の符号化率に対応したＬＤＰＣ符号を構成する処理については、上記図１４に示すようなパリティ検査行列に限らず、どのようなパリティ検査行列においても適用可能である。【０１４６】
実施の形態７．
つづいて、前述した実施の形態１〜６の符号化処理／復号処理を適用するシステムについて説明する。たとえば、本発明にかかるＬＤＰＣ符号化処理および復号処理は、移動体通信（端末，基地局），無線ＬＡＮ，光通信，衛星通信，量子暗号装置等、通信機器全般に適用できるものであり、具体的には、図１に示すＬＤＰＣ符号化器１，ＬＤＰＣ復号器５を、各通信機器に搭載し、誤り訂正を行う。【０１４７】
図１８は、本発明にかかる符号化処理／復号処理を、移動体端末１００およびその移動体端末１００と通信を行う基地局２００を備えた移動体通信システムに適用した場合の構成例を示す図であり、移動体端末１００は、物理層ＬＤＰＣ符号化器１０２と変調器１０３と復調器１０４と物理層ＬＤＰＣ復号器１０５とアンテナ１０７とを備え、基地局２００は、物理層ＬＤＰＣ復号器２０２と復調器２０３と変調器２０４と物理層ＬＤＰＣ符号化器２０５とアンテナ２０７とを備えている。【０１４８】
また、図１８に示す移動体端末１００および基地局２００には、物理層にフェージング通信路等に適用する物理層ＬＤＰＣ符号化器１０２および物理層ＬＤＰＣ復号器１０５が搭載されている。なお、移動体端末１００および基地局２００の物理層ＬＤＰＣ符号化器には、前述した実施の形態１〜６で説明したＬＰＤＣ符号化器のいずれかの構成を適用し、移動体端末１００および基地局２００の物理層ＬＤＰＣ復号器には、前述した実施の形態１〜６で説明したＬＤＰＣ復号器の構成を適用する。【０１４９】
上記のように構成される移動体通信システムにおいて、移動体端末１００からデータを送信する場合は、まず、データとして、物理層では、パケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器１０２が符号化する。この符号化データを、変調器１０３とアンテナ１０７を介して無線通信路へ送出する。【０１５０】
一方、基地局２００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ２０７と復調器２０３を介して受け取り、復調後の受信データを物理層用ＬＤＰＣ復号器２０２にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。そして、この情報パケットを、ネットワークを介して通信先へ転送する。なお、ネットワークから移動体端末１００が各種データを受信する場合についても、上記と同様の処理で、基地局２００が移動体端末１００へ符号化データを送信し、移動体端末１００が各種データを再生する。基地局２００が移動体端末１００へ符号化データを送信する場合は、まず、物理層では、パケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器２０５が符号化する。この符号化データを、変調器２０４とアンテナ２０７を介して無線通信路へ送出する。一方、移動体端末１００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ１０７と復調器１０４を介して受け取り、復調後の受信データを物理層ＬＤＰＣ復号器１０５にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。
【産業上の利用可能性】
【０１５１】
以上のように、本発明にかかる検査行列生成方法および符号化方法は、ディジタル通信における符号化技術として有用であり、特に、符号化方式としてＬＤＰＣ符号を採用する通信装置に適している。
【図１】
0004602418.tif 000022
【図２−１】
0004602418.tif 000023
【図２−２】
0004602418.tif 000024
【図３】
0004602418.tif 000025
【図４】
0004602418.tif 000026
【図５】
0004602418.tif 000027
【図６】
0004602418.tif 000028
【図７】
0004602418.tif 000029
【図８】
0004602418.tif 000030
【図９】
0004602418.tif 000031
【図１０】
0004602418.tif 000032
【図１１】
0004602418.tif 000033
【図１２】
0004602418.tif 000034
【図１３】
0004602418.tif 000035
【図１４】
0004602418.tif 000036
【図１５】
0004602418.tif 000037
【図１６】
0004602418.tif 000038
【図１７】
0004602418.tif 000039
【図１８】
0004602418.tif 000040
【図１９】
0004602418.tif 000041
【図２０】
0004602418.tif 000042