(57)【特許請求の範囲】
【請求項１】
ＬＤＰＣ（Low-Density  Parity  Check）符号用のパリティ検査行列を生成する検査行列生成方法であって、
巡回置換行列が行方向と列方向に配置されかつ当該巡回置換行列に特定の規則性を持たせた正則（行と列の重みが一様）な擬似巡回行列を生成する擬似巡回行列生成ステップと、
所定の符号化率に対応する前記正則な擬似巡回行列を非正則（行と列の重みが非一様）にするためのマスク行列の列次数を計算し、前記列次数を制約条件として複数の符号化率に対応可能なマスク行列を生成するマスク行列生成ステップと、
特定の符号化率に対応するマスク行列を用いて、前記正則な擬似巡回行列内の特定の巡回置換行列を０行列に変換し、非正則なマスク化擬似巡回行列を生成するマスク化ステップと、
前記マスク化擬似巡回行列と巡回置換行列を階段状に配置した行列とを所定位置に配置した、ＬＤＧＭ（Low  Density  Generation  Matrix）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、
を含むことを特徴とする検査行列生成方法。
【請求項２】
前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝ｊ（ｌ＋１）ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする請求項１に記載の検査行列生成方法。
【請求項３】
前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝（ｊ＋１）（ｌ＋１）ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする請求項１に記載の検査行列生成方法。
【請求項４】
前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝ｐ0,l（ｊ＋１）ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする請求項１に記載の検査行列生成方法。
【請求項５】
前記正則な擬似巡回行列において、行番号ｊ（０≦ｊ≦Ｊ−１）、列番号ｌ（０≦ｌ≦Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、「ｐj,l＝（（ｐ−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐ」となる特定の規則性を設ける（Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１）、列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列）ことを特徴とする請求項１に記載の検査行列生成方法。
【請求項６】
まず、前記ＬＤＧＭ構造の非正則なパリティ検査行列に基づいて、ｐ0,L-1の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,L-1を求め、
つぎに、ｐ0,L-2の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,L-2を求め、
以降、同様の処理でｐ0,L-3、ｐ0,L-4，ｐ0,L-5を順に求め、最後に、ｐ0,0の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,0を求めることを特徴とする請求項４に記載の検査行列生成方法。
【請求項７】
まず、前記ＬＤＧＭ構造の非正則なパリティ検査行列に基づいて、ｐ0,L-1の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,L-1を求め、
つぎに、ｐ0,L-2の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,L-2を求め、
以降、同様の処理でｐ0,L-3、ｐ0,L-4，ｐ0,L-5を順に求め、最後に、ｐ0,0の値を１からｐ−１まで変化させ、最小ループが最大かつ当該最小ループの数が最小となるｐ0,0を求めることを特徴とする請求項５に記載の検査行列生成方法。
【請求項８】
前記マスク行列生成ステップでは、
まず、基準となる第１の符号化率に対応する第１のマスク行列の列次数分布を計算し、つぎに、前記第１のマスク行列の列次数分布を制約条件として次に符号化率の低い第２の符号化率に対応する第２のマスク行列の列次数分布を計算し、以降、必要に応じて、前段のマスク行列の列次数分布を制約条件として第３のマスク行列、第４のマスク行列、…の列次数分布を順に計算する次数分布計算ステップと、
符号化率の最も高い第１のマスク行列から順に、対応するマスク行列の列次数分布に基づいて、当該マスク行列の列の重み位置を決定する重み位置決定ステップと、
を含むことを特徴とする請求項１に記載の検査行列生成方法。
【請求項９】
前記重み位置決定ステップでは、
列次数が小さいことに起因して発生する誤りの確率に基づいて、マスク行列生成処理を、列次数の大きい列と小さい列に分けて行うこととし、
列次数の大きい列については、「同一列内の重みの間隔を２行以上離す」という第１の条件を満たすように、マスク行列の列の重み位置を決定し、
列次数の小さい列については、前記第１の条件および「乱数に基づいて配置する」という第２の条件を満たすように、マスク行列の列の重み位置を決定することを特徴とする請求項８に記載の検査行列生成方法。
【請求項１０】
前記重み位置決定ステップでは、前記第２の条件を満たすように、
所定の方法で乱数列を生成し、
当該乱数列において差分が１の要素が存在する場合に、一方の要素を乱数列の最後に移動することにより、要素間の差分が２以上となる擬似乱数系列を生成し、
当該擬似乱数系列を列次数毎に分割して、それぞれを列重みの行位置番号とすることを特徴とする請求項９に記載の検査行列生成方法。
【請求項１１】
前記重み位置決定ステップでは、列次数分布における列次数の降順に、マスク行列の列を配置することを特徴とする請求項８に記載の検査行列生成方法。
【請求項１２】
前記第２のマスク行列以降の各マスク行列は、列方向に同一パターンができないように、前記第１のマスク行列の部分行列をシフトしながら使用することを特徴とする請求項８に記載の検査行列生成方法。
【請求項１３】
前記巡回置換行列のサイズを可変とし、任意の符号長に対応することを特徴とする請求項１に記載の検査行列生成方法。
【請求項１４】
ＬＤＰＣ（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-Cycilc）符号（非特許文献１参照）を採用する場合について説明する。【０００３】
まず、符号化方式としてＬＤＰＣ符号を採用する従来の通信システムにおける、符号化／復号処理の流れを簡単に説明する。【０００４】
送信側の通信装置（送信装置と呼ぶ）内のＬＤＰＣ符号化器では、後述する従来の方法でパリティ検査行列Ｈを生成する。さらに、ＬＤＰＣ符号化器では、たとえば、Ｋ行×Ｎ列の生成行列Ｇ（Ｋ：情報長，Ｎ：符号語長）を生成する。ただし、ＬＤＰＣ用のパリティ検査行列をＨ（Ｍ行×Ｎ列）とした場合、生成行列Ｇは、ＧＨ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における巡回置換行列の縦方向（行方向）の個数である。【００１０】
【数１】
0004620132.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）構造の非正則なパリティ検査行列を生成する検査行列生成ステップと、を含むことを特徴とする。
【発明の効果】
【００２０】
この発明によれば、特定の規則性を持たせた正則な擬似巡回行列に対して、非正則な行列を生成するための所定のマスキングルールを適用することとしたので、容易にＬＤＧＭ構造の非正則なパリティ検査行列を生成することができる。また、従来のように、生成行列Ｇを生成する必要がないので、回路規模を大幅に削減することができる。
【図面の簡単な説明】
【００２１】
【図１】図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。
【図２−１】図２−１は、符号生成における積和演算部の構成を示す図である。
【図２−２】図２−２は、図２−１に示す積和演算部を用いた符号生成部の構成例を示す図である。
【図３】図３は、実施の形態１のマスク行列生成処理を示すフローチャートである。
【図４】図４は、パリティ検査行列ＨM(1/2)の列次数分布の一例を示す図である。
【図５】図５は、パリティ検査行列ＨM(1/3)の列次数分布の一例を示す図である。
【図６】図６は、マスク行列ＺAによりマスク後のイレギュラーなパリティ検査行列ＨM(1/2)の構成例を示す図である。
【図７】図７は、マスク行列Ｚによりマスク後のイレギュラーなパリティ検査行列ＨM(1/3)の構成例を示す図である。
【図８】図８は、ｐ0,lの探索方法を示すフローチャートである。
【図９】図９は、符号化率１／１０の符号に対応するイレギュラーなパリティ検査行列ＨMの列次数分布の一例を示す図である。
【図１０】図１０は、マスク行列Ｚによりマスク後のイレギュラーなパリティ検査行列ＨMの構成例を示す図である。
【図１１】図１１は、実施の形態４の符号構成法を示す図である。
【図１２】図１２は、システムで用意する一番低い符号化率をＲ0＝１／１０とした場合の符号を示す図である。
【図１３】図１３は、従来と本発明の送信処理を示す図である。
【図１４】図１４は、情報パケット長ｋ＝Ｎ−Ｍが列サイズ、パリティパケット長Ｍが行サイズのＨERAL´を示す図である。
【図１５】図１５は、実施の形態６のＬＤＰＣ符号のパリティ検査行列ＨMの構成を示す図である。
【図１６−１】図１６−１は、実施の形態６の消失訂正符号化復号法を説明するための図である。
【図１６−２】図１６−２は、実施の形態６の消失訂正符号化復号法を説明するための図である。
【図１６−３】図１６−３は、実施の形態６の消失訂正符号化復号法を説明するための図である。
【図１７】図１７は、実施の形態７におけるＩＰベースのストリーミングシステムの構成例を示す図である。
【図１８】図１８は、ＲＴＰプロトコルを示す図である。
【図１９】図１９は、本発明にかかる符号化処理／復号処理を移動体通信システムに適用した場合の構成例を示す図である。
【図２０】図２０は、ＱＣ符号のパリティ検査行列の一例を示す図である。
【図２１】図２１は、検査行列の一例をタナーグラフで表現した場合を示す図である。
【符号の説明】
【００２２】
１  ＬＤＰＣ符号化器
２  変調器
３  通信路
４  復調器
５  ＬＤＰＣ復号器
５１  積和演算部
【発明を実施するための最良の形態】
【００２３】
以下に、本発明にかかる検査行列生成方法の実施の形態を図面に基づいて詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。【００２４】
実施の形態１．
図１は、ＬＤＰＣ符号化器およびＬＤＰＣ復号器を含む本実施の形態の通信システムの構成例を示す図である。図１において、送信側の通信装置（送信装置と呼ぶ）は、ＬＤＰＣ符号化器１と変調器２を含む構成とし、受信側の通信装置（受信装置と呼ぶ）は、復調器４とＬＤＰＣ復号器５を含む構成とする。【００２５】
ここで、ＬＤＰＣ符号を採用する通信システムにおける符号化処理，復号処理の流れを簡単に説明する。【００２６】
送信装置内のＬＤＰＣ符号化器１では、本実施の形態の検査行列生成方法により生成されたパリティ検査行列、すなわち、後述する所定のマスキングルールに基づいてマスキング処理が行われたＭ行×Ｎ列のパリティ検査行列Ｈ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］）は、下記（４−１）式のように定義することができる。【００３３】
【数２−１】
0004620132.tif 000003
【００３４】
なお、ｈm,nは、パリティ検査行列ＨQCLにおいて、行番号ｍ，列番号ｎの要素を表す。また、０≦ｊ≦Ｊ−１，０≦ｌ≦Ｌ−１において、Ｉ（ｐj,l）は、行番号：ｒ（０≦ｒ≦ｐ−１），列番号：「（ｒ＋ｐj,l）ｍｏｄ  ｐ」の位置が“１”となり、その他の位置が“０”となる巡回置換行列である。たとえば、Ｉ（１）は、下記（４−２）式のように表すことができる。【００３５】
【数２−２】
0004620132.tif 000004
【００３６】
上記パリティ検査行列ＨQCLは、左側の行列（情報ビットに対応する部分）が、上記（２）式で示したＱＣ符号のパリティ検査行列と同一の擬似巡回行列ＨQCであり、右側の行列（パリティビットに対応する部分）が、下記（５−１）式または（５−２）式に示すＩ（０）を階段状に配置した行列ＨTまたはＨDである。【００３７】
【数３−１】
0004620132.tif 000005
【００３８】
【数３−２】
0004620132.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）                …（６）
ただし、Ｎ＝Ｋ＋Ｍである。【００４２】
【数４】
0004620132.tif 000007
【００４３】
さらに、本実施の形態においては、上記（４−１）のように定義されたＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、特定の規則性を設けている。具体的には、パリティ検査行列ＨQCLの左側の擬似巡回行列ＨQC部分において、行番号ｊ（＝０，１，２，…Ｊ−１），列番号ｌ（＝０，１，２，…Ｌ−１）に配置されたｐ行×ｐ列の巡回置換行列Ｉ（ｐj,l）のｐj,lに、下記（８−１）式または下記（８−２）式となる特定の規則性を設けている。【００４４】
ｐj,l＝ｊ（ｌ＋１）ｍｏｄ  ｐ                      …（８−１）
ｐj,l＝（ｊ＋１）（ｌ＋１）ｍｏｄ  ｐ              …（８−２）【００４５】
また、ｐ0,lを任意の整数とし、巡回置換行列Ｉ（ｐj,l）のｐj,lに、下記（９−１）式または下記（９−２）式となる特定の規則性を設けることとしてもよい。【００４６】
ｐj,l＝ｐ0,l（ｊ＋１）ｍｏｄ  ｐ                    …（９−１）
ｐj,l＝（（ｐ−ｐ0,l）（ｊ＋１））ｍｏｄ  ｐ        …（９−２）【００４７】
なお、本実施の形態においては、上記（８−１）式，（８−２）式，（９−１）式，（９−２）式に限らず、ｊ，ｌ，ｐj,l等のパラメータで構成できる他の規則性を設けることとしてもよい。【００４８】
以上のように、本実施の形態においては、巡回置換行列の行番号ｊと列番号ｌによってｐj,lを特定できる規則性、または、特定の行番号、具体的には、行番号ｊ＝０のｐ0,lを任意の整数とし、それ以外の行番号ｊによりｐj,lを特定できる規則性、を持たせる。これにより、後述するように、たとえば、擬似巡回行列ＨQCの行数が大きくなるような場合であっても、ＨQC全体のｐj,lを記憶する必要がなくなる。【００４９】
また、上記（８−１）式あるいは上記（８−２）式を用いる場合には、擬似巡回行列ＨQCについて何も記憶する必要がない。【００５０】
また、上記（９−１）式あるいは上記（９−２）式を用いる場合には、ｐ0,lだけを記憶しておけばよい。このとき、ｐ0,lは擬似巡回行列ＨQCの列数分だけ記憶しておけばよく、行数の大きいＨQCであっても少ないメモリで実現することができる。また、これらの規則性により、ｐ0,lの整数倍でｊ行目の置換行列の１行目の列番号が決まるため、具体的には、行毎にｐ0,lの足し算をするだけでよく、少ない計算量で実現することができる。【００５１】
なお、何も記憶する必要がない上記（８−１）式あるいは上記（８−２）式を用いる場合よりも、上記（９−１）式あるいは上記（９−２）式を用いる場合の方が、取り得る組み合わせの幅が広がるため、性能の良い組み合わせを選ぶことができる。ただし、ｐ0,lの探索方法については後述する。【００５２】
つづいて、本実施の形態の検査行列生成方法における特徴的な処理である、パリティ検査行列ＨQCLに対するマスク処理について説明する。【００５３】
たとえば、上記（４−１）式に示す左側の行列を、下記（１０−１）式に示すように、Ｊ×Ｌの擬似巡回行列ＨQCと表し、マスク行列Ｚ（＝［ｚj,l］）をＧＦ（２）上のＪ行×Ｌ列の行列とした場合、後述する所定のルールを適用すると、マスク処理後の行列ＨMQCは、下記（１０−２）式のように表すことができる。【００５４】
【数５−１】
0004620132.tif 000008
【００５５】
【数５−２】
0004620132.tif 000009
【００５６】
なお、上記（１０−２）式におけるｚj,lＩ（ｐj,l）は、下記（１１）式のように定義される。【００５７】
【数６】
0004620132.tif 000010
【００５８】
上記０行列は、ｐ行×ｐ列の０行列である。また、行列ＨMQCは、擬似巡回行列ＨQCをマスク行列Ｚの０要素によりマスクし、重み分布を非一様（イレギュラー）にした行列であり、また、行列ＨMQCの巡回置換行列の分布は、マスク行列Ｚの次数分布と同じである。【００５９】
ただし、上記重み分布を非一様にする場合のマスク行列Ｚの重み分布は、後述するように、所定の密度発展法で求めることとする。たとえば、６４行×３２列のマスク行列は、密度発展法による列次数分布に基づいて、下記（１２）式のように表すことができる。【００６０】
【数７】
0004620132.tif 000011
【００６１】
したがって、本実施の形態において、最終的に求めるイレギュラーなパリティ検査行列ＨMは、たとえば、６４行×３２列のマスク行列Ｚ、６４（行番号ｊは０〜６３）×３２（列番号ｌは０〜３１）の擬似巡回行列ＨQC、および６４（行番号ｊは０〜６３）×６４（列番号ｌは０〜３１）のＨTを用いて、下記（１３）式のように表すことができる。【００６２】
ＨM＝［Ｚ×ＨQC｜ＨT］
＝［ＨMQC｜ＨT］                              …（１３）【００６３】
すなわち、ＬＤＰＣ符号Ｃを生成するためのパリティ検査行列ＨMQCは、マスク行列Ｚと擬似巡回行列ＨQCの行番号ｊ＝０の巡回置換行列の値の設計により、与えられる。【００６４】
つづいて、レギュラーなパリティ検査行列ＨMを用いて、生成行列Ｇを用いずに符号化を実現する場合の実装例を以下に示し、その動作を説明する。なお、ここでは、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLを、下記（１４−１）式に示す行列とする。【００６５】
【数８−１】
0004620132.tif 000012
【００６６】
また、上記（１４−１）式に示す行列をマスク化したイレギュラーなパリティ検査行列ＨMを、下記（１４−２）式に示す行列とする。【００６７】
【数８−２】
0004620132.tif 000013
【００６８】
また、情報メッセージをｕ＝（ｕp,1  ｕp,2）＝（０１１００  １１００１）とする。ただし、ｕp,lは、ｕをｐビット単位で区切り、ｌに対して昇順に番号を付したものである。【００６９】
ここで、生成行列Ｇを用いずに符号を生成する場合の処理として、ｐ行分のマスク処理後の行列ＨMQCと情報メッセージｕとの積和演算について説明する。【００７０】
図２−１は、符号生成における積和演算部５１の構成を示す図である。ここでは、基準クロックを１クロックとし、図中、遅延素子（Ｄ）６１は１クロック単位で動作し、遅延素子（Ｄ）６２はｐクロック単位で動作する（この例ではｐ＝５）。また、列カウンタ６３はｐクロック単位で動作し、行カウンタ６４はＬ・ｐクロック単位で動作する（この例ではＬ＝２）。【００７１】
図２−１において、擬似巡回行列ＨQCのｊ行ｌ列目の巡回置換行列は、Ｉ（ｊ・（ｌ＋１）），「０≦ｊ≦Ｊ−１」，「０≦ｌ≦Ｌ−１」であるため、行カウンタ６４にてｊを昇順にＬ・ｐクロック単位でカウントし、列カウンタ６３にて「ｌ＋１」を昇順にｐクロック単位でカウントし、乗算器６５にて「ｊ・（ｌ＋１）」を算出し、その値をセレクタ６６に入力し、長さｐのレジスタ６７の“１”の位置を決めることにより、ｊ行ｌ列目の巡回置換行列の１行目の“１”の位置をセットする。【００７２】
一方、情報メッセージｕについては、長さｐ毎に区切り、遅延素子６２を介してｐクロック単位でレジスタ６８，６９に順に入力する。そして、加算器７０にてレジスタ６９内の長さｐの情報メッセージｕとレジスタ６７内のビット列とのＥＸＯＲを計算し、加算器７２にてＥＸＯＲ演算結果の各ビットの総和を計算する。この処理により、Ｉ（ｊ・（ｌ＋１））の１行目と情報メッセージのｕp,lとの積和計算が実現できる。つぎに、レジスタ６７を、遅延素子６１を用いてシフトすることにより、Ｉ（ｊ・（ｌ＋１））の２行目が生成でき、同様に、Ｉ（ｊ・（ｌ＋１））の２行目と情報メッセージのup,lとの積和計算が実現できる。その後、この処理をｐ回にわたって繰り返し実行することにより、Ｉ（ｊ・（ｌ＋１））のｐ行分の積和計算結果ｐp,j´が得られる。なお、ｐp,j´はｊ行目の巡回置換行列全ての積和計算結果のｐビットを意味する。【００７３】
つぎに、ｌ＝０からｌ＝Ｌ−１まで、Ｉ（ｊ・（ｌ＋１））とｕp,lとの積和を計算するために、遅延素子６２と加算器７２により、Ｌ回にわたって繰り返しＥＸＯＲ演算を行う。この操作をｊ＝０からｊ＝Ｊ−１まで繰り返し実行し、マスク処理後の行列ＨMQCとｕとの積和計算結果ｐp,j´を得る。なお、セレクタ７３では、ｚj,l＝０のとき０を選択出力し、ｚj,l＝１のとき加算器７１出力を選択出力する。【００７４】
また、図２−２は、図２−１に示す積和演算部５１を用いた符号生成部の構成例を示す図である。ここでは、遅延素子（Ｄ）７４がＬ・ｐクロック単位で動作する。図２−２において、ｐビット単位に昇順にｊに番号を付した系列（パリティビット）をｐp,jとすると、系列ｐp,jは、遅延素子７４と加算器７５によるＥＸＯＲ演算で得られる。すなわち、「ｐp,j＝ｐp,j´＋ｐp,j-1´」を計算する。なお、ｐp,0´＝０である。【００７５】
つづいて、上記擬似巡回行列ＨQCをマスク行列Ｚの０要素によりマスクする場合のマスキングルールを具体的に説明する。ここでは、本実施の形態の通信装置が、６４（行番号ｊは０〜６３）×３２（列番号ｌは０〜３１）の擬似巡回行列Ｈ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は、（１５）式に示すような行列となる。【００８８】
【数９】
0004620132.tif 000014
【００８９】
なお、密度発展法により求めたマスク行列ＺAの列次数分布に基づいてマスク行列ＺAを構成する場合、小さい列次数の列（列次数３，４等）に小さいループ（ループ４，６等）が含まれていると、誤り確率が上がり、良好な性能が得られない場合がある。このような場合、ＬＤＰＣ符号化器１は、小さい列次数の列の重みを増やすことで、性能劣化を回避する。上記マスク行列ＺAの場合は、図４に示す列次数分布において、列次数３の列（９／６４）のうちの３列の重みを増やしている。すなわち、（１５）式においては、列次数１４が５列，列次数４が２１列，列次数３が６列となっている。【００９０】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列Ｚの列次数分布に基づいて、上記優先順位＃１の条件を満たすように、マスク行列Ｚにおける列次数の大きい列、すなわち、ここでは列次数２８の列（５／９６）の、“１”の位置を決める（ステップＳ５）。このとき、上記列次数の大きい列は、“１”の密度が大きいため、上記優先順位＃２の条件を満たす必要はない。また、上記で求めた列次数２８を実現するために、同一列において“１”が連続しても良いが、その数は可能な限り少なくする。【００９１】
そして、ここでは、列次数の大きい列が２８の一つしか存在していないが、列次数の大きい列が複数存在する場合は、左から列次数の降順にマスク行列Ｚの列を配置する（ステップＳ５）。【００９２】
つぎに、ＬＤＰＣ符号化器１は、上記マスク行列Ｚの列次数分布に基づいて、上記優先順位＃１の条件および上記優先順位＃２の条件を満たすように、マスク行列Ｚにおける列次数の小さい列、すなわち、ここでは列次数８，４，３の一部の列（１０／９６，８／９６，９／９６）の、“１”の位置を決める（ステップＳ６）。【００９３】
そして、上記列次数の大きい列につづいて、左から列次数の降順にマスク行列Ｚの列を配置する（ステップＳ６）。【００９４】
たとえば、上記ステップＳ５およびＳ６にて生成されたマスク行列Ｚは、上記（１２）式のように表すことができる。上記（１２）式において、ＺA（１：３２，２：５）は、マスク行列ＺAの１行目〜３２行目および２列目〜５列目のサブマトリックスを表し、ＺA（１：３２，１）は、マスク行列ＺAの１行目〜３２行目および１列目のサブマトリックスを表し、ＺA（１：３２，７：１６）は、マスク行列ＺAの１行目〜３２行目および７列目〜１６列目のサブマトリックスを表す。【００９５】
なお、密度発展法により求めたマスク行列Ｚの列次数分布に基づいてマスク行列Ｚを構成する場合、小さい列次数の列（列次数３，４，８等）に小さいループ（ループ４，６等）が含まれていると、誤り確率が上がり、良好な性能が得られない場合がある。このような場合、ＬＤＰＣ符号化器１は、小さい列次数の列の重みを増やすことで、性能劣化を回避する。【００９６】
また、ＬＤＰＣ符号を多値変調のような不均一な誤り確率のアプリケーションに適用する場合、誤り確率の小さいビットを列次数の大きい列に対応するビットに割り当て、誤り確率の大きいビットを列次数の小さい列に対応するビットに割り当てると、性能が向上する。このような場合に、上記ステップＳ３〜Ｓ６に示すように、左側から列次数の降順に列を並べておくと、ビットのオーダリングが容易となる。【００９７】
図６は、上記のように生成したマスク行列ＺAによりマスク後の、イレギュラーなパリティ検査行列ＨM(1/2)の構成例を示す図であり、図７は、上記のように生成したマスク行列Ｚによりマスク後の、イレギュラーなパリティ検査行列ＨM(1/3)の構成例を示す図である。なお、図７において、図示のＨQCDは、上記擬似巡回行列ＨQCにおける下半分の３２（行番号ｊは３２〜６３）×３２（列番号ｌは０〜３１）の擬似巡回行列を表す。また、図示の０は０行列を表し、図示のＩは単位行列を表し、ＨDとＩと０でＨTを構成する。【００９８】
つづいて、擬似乱数系列を用いたマスク行列設計法について説明する。たとえば、上記では、上記優先順位＃１の条件および優先順位＃２の条件を満たすように、小さい列次数の列内の“１”の位置を決めている。具体的には、本実施の形態では、同一列内の１”の位置の差分が２以上となる擬似乱数系列を用いて、小さい列次数の列内の“１”の位置を決める。【００９９】
たとえば、本実施の形態では、下記（１６）式に示すフェルマーの小定理に基づいて乱数を生成する。なお、Ｇ0はＧＦ（ｐ）の原始元である。
Ａ（ｉ）＝Ｇ0iｍｏｄ  ｐ，ｉ＝０，１，２，…，ｐ−２      …（１６）【０１００】
そして、その乱数列の中で差分が１の要素が存在する場合は、たとえば、後ろの要素を最後に移動する処理を施し、この処理を施した後の乱数系列を用いて、小さい列次数の列内の“１”の位置を決める。【０１０１】
具体的には、上記乱数系列をｐ＝１１，Ｇ0＝２として生成する場合、
｛1  2  4  8  5  10  9  7  3  6｝
となるため、要素間差分が１となっている、要素１と要素２，要素１０と要素９、のそれぞれの後ろの要素２，９を最後尾に移動する。すなわち、
｛1  4  8  5  10  7  3  6  2  9｝
となる。【０１０２】
その後、上記並べ替え後の乱数系列を列次数毎に分割して、行位置番号とする。たとえば、列次数３を２列，列次数４を１列とした場合は、乱数系列を、
｛1  4  8｝，｛5  10  7｝，｛3  6  2  9｝
というように分割して、分割後の各要素を、列中の“１”の行番号とする。【０１０３】
そして、この乱数系列により“１”の位置決めが終了した場合には、さらに異なる原始元にて同様に乱数系列を生成し、その乱数系列を用いて残りの列の“１”の位置を決める。【０１０４】
この処理により、小さいループが発生しづらくなる、という効果が得られる。また、ＨTを使用し、マスク行列の同一列において“１”が隣り合っている場合には、短いループが発生する可能性があるが、上記乱数系列を用いることにより、その可能性を回避することができる。【０１０５】
なお、上記乱数系列の生成方法は、一例であり、同一列内の要素の差分が２以上となる擬似乱数系列であれば、どのような系列を用いてもよい。【０１０６】
つづいて、ｐ0,lの探索方法について説明する。ここでは、マスク行列ＺA使用時で、かつ、上記（９−１）式または上記（９−２）式に基づく擬似巡回行列ＨQCを用いた場合の、本実施の形態の通信装置によるｐ0,lの探索方法について説明する。また、上記図３において求めたマスク行列ＺAを用いて、ＨM(1/2)を「ＨM(1/2)＝［ＺA×ＨQCU｜ＨD］」と仮定する。【０１０７】
図８は、本実施の形態のｐ0,lの探索方法を示すフローチャートである。まず、ＬＤＰＣ符号化器１では、「ＨM(1/2)＝［ＺA×ＨQCU｜ＨD］」に基づいて、ｐ0,L-1の値を１からｐ−１まで変化させ、最小ループが最大となり、その最小ループの数が最小となるｐ0,L-1を求める（ステップＳ１１）。このとき、ＨM(1/2)の１列目から（Ｌ−２）列目までの巡回置換行列は、全て０行列に置き換えていることを条件とする。【０１０８】
つぎに、ＬＤＰＣ符号化器１では、「ＨM(1/2)＝［ＺA×ＨQCU｜ＨD］」に基づいて、ｐ0,L-2の値を１からｐ−１まで変化させ、最小ループが最大となり、その最小ループの数が最小となるｐ0,L-2を求める（ステップＳ１２）。このとき、ＨM(1/2)の１列目から（Ｌ−３）列目までの巡回置換行列は、全て０行列に置き換えていることを条件とする。【０１０９】
以降、ＬＤＰＣ符号化器１では、上記と同様の処理で、ｐ0,L-3，ｐ0,L-4，ｐ0,L-5を求めていき、最後に、「ＨM(1/2)＝［ＺA×ＨQCU｜ＨD］」に基づいて、ｐ0,0の値を１からｐ−１まで変化させ、最小ループが最大となり、その最小ループの数が最小となるｐ0,0を求める（ステップＳ１３）。【０１１０】
上記ステップＳ１１〜Ｓ１３の処理を実行することにより、最小ループの影響を受けやすい列次数の小さな列から優先的にｐ0,lが確定していくため、良い性能の検査行列を設計することができる。【０１１１】
ここで、上記探索方法で求めたｐ0,lの一例を以下に示す。たとえば、３２（行番号ｊは０〜３１）×３２（列番号ｌは０〜３１）のＨQCに対して上記（９−２）式を用いた場合、
ｐ0,0＝３９，ｐ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＝３２
となる。【０１１２】
なお、本実施の形態においては、パリティ検査行列にＨDやＨTを含まない場合であっても、上記擬似乱数系列を用いたマスク行列設計法および上記ｐ0,lの探索方法を、容易に適用可能である。【０１１３】
このように、本実施の形態においては、ＬＤＧＭ構造のＱＣ−ＬＤＰＣ符号のパリティ検査行列ＨQCLに、擬似巡回行列ＨQC部分の行番号ｊ，列番号ｌに配置された巡回置換行列の１行目の列番号が上記（８−１）式，上記（８−２）式，上記（９−１）式，上記（９−２）式となる特定の規則性を設け、当該特定の規則性を設けた擬似巡回行列ＨQCを、所定の方法で生成されたマスク行列を用いてマスクすることにより、イレギュラーなパリティ検査行列を生成することとした。これにより、ＬＤＧＭ構造のレギュラーなパリティ検査行列ＨQCLから、ＬＤＧＭ構造のイレギュラーなパリティ検査行列ＨMを生成することができる。また、パリティ検査行列の一部を階段状の構造にしたことにより、生成行列Ｇを用いずに符号化を容易に実現でき、生成行列Ｇを生成する必要がないので、回路規模を大幅に低減することができる。【０１１４】
実施の形態２．
前述の実施の形態１では、符号化率１／３までの符号構成法について説明したが、本実施の形態においては、たとえば、符号化率１／１０までの符号構成法について説明する。なお、システム構成については、前述した実施の形態１の図１と同様である。ここでは、前述した実施の形態１と異なる処理について説明する。【０１１５】
ここで、符号化率１／１０に対応する２８８（行番号ｊは０〜２８７）×３２（列番号ｌは０〜３１）の擬似巡回行列ＨQCを、２８８行×３２列のマスク行列Ｚの０要素によりマスクする場合のマスキングルールを具体的に説明する。ここでは、本実施の形態の通信装置が、上記２８８×３２の擬似巡回行列ＨQCを非正則（イレギュラー）にするためのマスク行列Ｚを、規則的なマスキングルールにより生成する。【０１１６】
以下、本実施の形態のマスク行列生成処理として、前述した実施の形態１の図３と異なる処理について説明する。なお、マスク行列Ｚ生成後、最終的に求めるイレギュラーなパリティ検査行列ＨMは、たとえば、２８８行×３２列のマスク行列Ｚ、上記２８８×３２の擬似巡回行列ＨQC、および２８８（行番号ｊは０〜２８７）×２８８（列番号ｌは０〜２８７）のＨTを用いて、下記（１７）式のように表すことができる。【０１１７】
ＨM＝［Ｚ×ＨQC｜ＨT］
＝［ＨMQC｜ＨT］                          …（１７）【０１１８】
また、上記ＨTを下記（１８）式のように定義し、さらに、ＨT内のＴDを下記（１９）式のように定義する。【０１１９】
【数１０】
0004620132.tif 000015
【０１２０】
【数１１】
0004620132.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/10)（＝ＨM）と表し、マスク行列をＺA(1/3)，ＺA(1/4)，…，ＺA(1/10)（＝Ｚ）と表し、擬似巡回行列をＨQC(1/3)，ＨQC(1/4)，…，ＨQC(1/10)（＝ＨQC）と表し、ＨT(1/3)，ＨT(1/4)，…，ＨT(1/10)（＝ＨT）と表す。【０１２２】
たとえば、図３のステップＳ２の処理において、本実施の形態のＬＤＰＣ符号化器１では、まず、符号化率１／２に対応して、マスク行列ＺAの行数を最大次数とし、上記ＨT(1/2)（＝ＴD）の次数分布を制約条件として、密度発展法により、マスク行列ＺAの列次数分布を計算する。つぎに、ＬＤＰＣ符号化器１は、符号化率１／３に対応して、上記ＨT(1/3)の次数分布および上記で求めたマスク行列ＺAの列次数分布を制約条件として、密度発展法により、マスク行列ＺA(1/3)の列次数分布を計算する。以降、一つ前のマスク行列の列次数分布を制約条件として、密度発展法により、符号化率１／４，１／５，…に対応したマスク行列の列次数分布を順次計算し、最後に、上記ＨTの次数分布および符号化率１／９に対応したマスク行列ＺA(1/9)の列次数分布を制約条件として、密度発展法により、マスク行列Ｚの列次数分布を計算する。図９は、符号化率１／１０の符号に対応するイレギュラーなパリティ検査行列ＨM＝［Ｚ×ＨQC｜ＨT］の列次数分布の一例を示す図である。【０１２３】
つぎに、ＬＤＰＣ符号化器１では、図３のステップＳ３〜Ｓ６の処理において、前述した実施の形態１と同様に、優先順位＃１の条件および優先順位＃２の条件に基づいて、符号化率１／２，１／３に対応するマスク行列の各列の“１”の位置を決め、その後、さらに、同様の手順で、符号化率１／４，１／５，…，１／１０に対応するマスク行列の各列の“１”の位置を決める。【０１２４】
たとえば、上記本実施の形態の処理にて生成されたマスク行列Ｚは、下記（２０）式のように表すことができる。【０１２５】
【数１２】
0004620132.tif 000017
【０１２６】
図１０は、上記のように生成したマスク行列Ｚによりマスク後の、イレギュラーなパリティ検査行列ＨMの構成例を示す図である。【０１２７】
このように、本実施の形態においては、マスク行列Ｚを、符号化率１／２に対応するマスク行列ＺAの部分行列のみを使って構成しているため、符号化率に応じてマスク行列が大きくなった場合であっても、マスク行列を記憶するためのメモリを少なくすることができる。【０１２８】
また、符号化率に応じた各マスク行列は、列方向に同一パターンができないように、マスク行列ＺAの部分行列をシフトしながら使用している。具体的には、マスク行列ＺAの部分行列を列次数の重い部分行列（重み１４）と軽い部分行列（重み４以下）とに分け、それぞれをシフトしながら用いている。たとえば、マスク行列ＺAにおいて、ＺA（１：３２，１：５）は列次数１４の部分行列であるが、マスク行列ＺA(1/3)においては、これを列単位で左シフトさせ、シフト後のＺA（１：３２，２：５）ＺA（１：３２，１）をマスク行列ＺAのＺA（１：３２，１：５）の下に連結させている。また、マスク行列ＺAにおいて、ＺA（１：３２，６：３２）は列次数４以下の部分行列であるが、マスク行列ＺA(1/3)においては、ＺA（１：３２，６：３２）の中から必要な列数の部分行列ＺA（１：３２，７：１６）を使用し、このＺA（１：３２，７：１６）をマスク行列ＺAのＺA（１：３２，６：１５）の下に連結させている。そして、マスク行列ＺA(1/4)，ＺA(1/5)，ＺA(1/6)…についても、列方向に同一パターンができないように、マスク行列ＺAの部分行列をシフトしながら使用する。これにより、ＨTを用いた場合に発生しやすい小さいループを、回避することができる。【０１２９】
実施の形態３．
つづいて、実施の形態１および２において生成したパリティ検査行列が任意の符号長に対応する場合のルールについて説明する。【０１３０】
巡回置換行列Ｉ（ｐj,l）のサイズｐを可変にすることにより、任意の符号長に対応することはできるが、その際、本実施の形態では、以下のルールで、ｐj,lの値を変更する。【０１３１】
（１）「ｐ≦ｐA」の場合は、下記（２１）式に示すように、ｐj,lの値を変更する。
ｐj,llen＝ｐj,lPAｍｏｄ  ｐ                    …（２１）
なお、ｐj,llenは、サイズｐのときの巡回置換行列の最初の行の１の列番号で、ｐj,lPAはサイズｐAのときの巡回置換行列の最初の行の１の列番号であり、このｐj,lPAおよびｐAは事前に求めておくものとする。【０１３２】
（２）「ｐ＞ｐA」の場合は、下記（２２）式，下記（２３）式、下記（２４）式または上記（２１）式に示すように、ｐj,lの値を変更する。【０１３３】
【数１３】
0004620132.tif 000018
【０１３４】
【数１４】
0004620132.tif 000019
【０１３５】
【数１５】
0004620132.tif 000020
【０１３６】
なお、上記（２２）式ＳMは、マスク行列の行数、αは「０＜α≦１」の任意の実数の定数である。また、上記（２３）式の第二項は、第一項に加算または減算する整数を一般的に表現したものである。この部分は「（（ｐ／ｐA）×α）以下の乱数」でもよい。【０１３７】
上記（１）に関しては、ｐが変化してもｐj,llenがｐを越えなければ変化しない、という特徴があり、これにより、ループの分布が殆ど変化しない、という効果が得られる。【０１３８】
一方、上記（２）に関しては、整数倍にｐが増加した際にはループの分布が変らないが、整数倍で割り切れない倍数の場合に中間値を補足する効果がある。【０１３９】
たとえば、あるＬＤＰＣ符号が、ｐA＝１０で、下記（２５）式のようなマスク化擬似巡回行列Ｈで構成されていると仮定する。【０１４０】
【数１６】
0004620132.tif 000021
【０１４１】
ここで、下記（２６）式に示すような擬似巡回行列Ｈ´がループ２ｉを持つための必要十分条件は、下記（２７）式の場合、下記（２８）式となる。【０１４２】
【数１７】
0004620132.tif 000022
【０１４３】
【数１８】
0004620132.tif 000023
【０１４４】
【数１９−１】
0004620132.tif 000024
【０１４５】
なお、上記Δは下記（２９）式である。【０１４６】
【数１９−２】
0004620132.tif 000025
【０１４７】
従って、この条件を用いて考えると、上記（２５）式に示す行列Ｈは、（１−２）＋（６−９）＋（６−２）＝０のループ６が存在しているのがわかる。【０１４８】
また、ｐA＝１０に対してｐ＝１１０の場合、上記（２４）式を適用すると、下記（３０）式となる。この場合、同一箇所で（１１−２２）＋（６６−９９）＋（６６−２２）＝０となり、ループの分布は変わらないため、ｐA＝１０のときのループの分布を保証できるという意味では、この方法（上記（２４）式）でもよい。【０１４９】
【数２０】
0004620132.tif 000026
【０１５０】
しかしながらｐがｐAの整数倍の場合、ｐ／ｐAの倍数以外の数字が存在しないことを考えると、ｐ／ｐAに対して小さい値を上記（２４）式の値に加算すると、さらにループを分解でき、大きいループの分布を構成できる可能性が増える。たとえば、上記（２２）式でα＝１／４を用いた場合、下記（３１）式となり、同一箇所で（１１−２２）＋（６６−１０２）＋（６７−２２）＝−２≠０となり、ループ６の条件を満たさなくなる。【０１５１】
【数２１】
0004620132.tif 000027
【０１５２】
一方、上記（２４）式はｐ／ｐAの倍数でループが全て規定されているから、上記（２２）式の第二項がｐ／ｐAに比べて十分に小さければ、新たに小さいループを規定する条件が発生する確率は低くなる。すなわち、上記（２２）式を適用した場合にはループの分布が大きい値にシフトすることが期待できる。【０１５３】
実施の形態４．
実施の形態４では、前述した実施の形態１〜３にて求めたイレギュラーなパリティ検査行列ＨMを用いて、複数の符号化率に対応したＬＤＰＣ符号を構成する。【０１５４】
図１１は、本実施の形態の符号構成法を示す図であり、たとえば、符号化率０．５の符号を基準符号語とし、それよりも高い符号化率（＝０．７５）の符号語を生成する場合はパリティのパンクチャを行い、低い符号化率（＝１／３）の符号語を生成する場合はパリティを追加している。なお、パンクチャリングビットには、受信ＬＬＲに０を挿入し、通常のＬＤＰＣ復号を行えばよい。【０１５５】
ここで、複数の符号化率に対応したＬＤＰＣ符号の構成法を具体的に説明する。たとえば、システムで用意する一番低い符号化率をＲ0＝１／３以下とする。図１２は、たとえば、システムで用意する一番低い符号化率をＲ0＝１／１０とした場合の符号を示す図である。【０１５６】
たとえば、符号化率Ｒ0＝１／１０に対応する符号がメモリに記憶され、符号化率Ｒ1の符号を構成する場合、符号化率Ｒ1が１／２未満であれば、すなわち、符号化率Ｒ1が１／２〜１／１０の間であれば、パリティビットを符号語の最後尾から順にパンクチャする。【０１５７】
一方で、符号化率Ｒ1が１／２よりも高い場合は、ＬＤＰＣ符号のパンクチャリングビットの集合ｒ´を以下のように表現する。たとえば、符号化率Ｒl＝Ｋ／（Ｋ＋Ｋ／２(l-1)）に対して長さｒのパリティビットを仮定すると（ｌ＝２，３，…）、パンクチャリングビットの集合ｒ´は、下記（３２）式のように表すことができる。【０１５８】
ｒ´＝ｒ＼｛ｒ（１：２(l-1)：Ｋ）｝
…（３２）【０１５９】
なお、上記｛ｒ（１：２(l-1)：Ｋ）｝は、ｒの集合の、１番目の要素からＫ番目の要素までの２(l-1)ステップの要素を示し、上記（３２）式は、集合ｒから集合｛ｒ（１：２(l-1)：Ｋ）｝を除いた集合を意味する。【０１６０】
したがって、１ビットずつパンクチャする場合は、集合｛ｒ（１：２(l-1)：Ｋ）｝に対して、｛ｒ（１：２(l-1)：Ｋ）｝＼｛ｒ（１：２(l-1+1)：Ｋ）｝とした要素の後ろの要素から削除していき、それをｒの集合から除いてパンクチャビットとする。このとき、図１１に示すとびとびに表現されているパンクチャビットを、後ろから順にパンクチャできるように並べ替える。【０１６１】
このように、本実施の形態においては、特定の符号化率の符号語を基準とし、基準符号語より高い符号化率に関してはパリティのパンクチャを行い、低い符号化率に関してはパリティを増加させることとし、その際、符号化率に応じて個別にパリティ検査行列を生成することなく、一つのパリティ検査行列ＨMを用いて、上記パンクチャ処理およびパリティ追加処理を実現することとした。これにより、容易に複数の符号化率に対応できるとともに、さらに、符号化率の数に相当するパリティ検査行列を用意する必要がなくなるので、回路規模を大幅に削減できる。【０１６２】
実施の形態５．
実施の形態５では、前述したＬＤＰＣ符号の消失訂正符号への応用について記載する。ここまで説明したＬＤＰＣ符号は、通信機の物理層にて実装するタイプの誤り訂正符号であったが、これを消失訂正符号としてもそのまま活用できるので、以降説明を加える。【０１６３】
任意の符号長，符号化率に対して、確率的に小さい受信パケット数で復号を成功させることを目的とする際には、前述したＬＤＰＣ符号に基づく消失訂正符号が適している。一方、符号化パケットに対して復号可能な消失パケット数を保証する必要がある場合、あるいはバースト性の消失パケット数を保証する必要がある場合には、ＢＣＨ符号等の巡回符号に基づく消失訂正符号が有効となる。【０１６４】
消失訂正用の符号として、ここまで説明してきた本発明にかかるＬＤＰＣ符号、あるいは一般のＬＤＰＣ符号を元に構成する。また、消失パケット数を保証する意味でHamming符号，巡回符号，ＢＣＨ符号あるいは最小距離が保証できるＬＤＰＣ符号を元に構成する。これらの消失訂正符号は、無線通信や光ファイバーや銅線による有線通信などに活用できる。あるいは、分散してディスクに符号化パケットを保存し、どこかのディスクが破損した際に消失訂正符号により再生を行うことも可能となる。この際、データをパケット単位（データパケット）に消失訂正符号化した符号化パケットを異なるディスクに分散させて保存するシステムに対し、保存したディスクが部分的に壊れた際に、その壊れたディスクの符号化パケットのみを、必要最小限の別に保存した符号化パケットのみを集めて再生する機能を持つ。また、データパケットを一部更新する際に、関連する最小限の符号化パケットのみを訂正する。【０１６５】
本実施の形態では、ＢＣＨ符号等の代数的符号を用いた符号化復号法について述べる。なお、以降の説明では、パケット単位で説明するが、処理はパケット内の同一のビット位置毎に並列に符号化復号処理するものとする。【０１６６】
まず、一般に検査行列で定義される符号に関して、その符号を消失訂正符号として用いる場合の処理方法を示す。任意の線形符号のＭ行Ｎ列の２元検査行列ＨERAを、以下の手順で消失訂正用検査行列に変換する。【０１６７】
（１）ＨERAをＭ×(Ｎ−Ｍ)行列ＡとＭ×Ｍ行列Ｂとを用いて下記（３３）式のように定義する。
ＨERA＝［Ａ｜Ｂ］
Ｂ≠０
…（３３）【０１６８】
（２）Ｂの逆行列Ｂ-1を用いて下記（３４）式に示す変換を行い、下記（３５）式を生成する。なお、ＩはＭ×Ｍの単位行列である。
ＨERA´＝［Ｂ-1Ａ｜Ｂ-1Ｂ］＝［Ｂ-1Ａ｜Ｉ］
…（３４）
ＨERAL´＝［Ｂ-1Ａ］
…（３５）【０１６９】
（３）上記ＨERAL´を用いて情報パケットｕ＝（ｕ1  ｕ2  …  ｕN-M）に対し、パリティパケットｐ＝（ｐ1  ｐ2  …  ｐM）を下記（３６）式のように作成する。
ｐT＝ＨERAL´×ｕT
…（３６）【０１７０】
（４）送信パケットは、ｖ＝（ｕ｜ｐ）を図１３に示すように送り、受信側ではガウス消去法等により復号する。
（５）受信パケットの壊れたパケットは、Ｈの“１”の立っている関連する情報パケットから再生する。
（６）データパケット更新時はＨの“１”の立っている関連するパリティパケットを修正する。【０１７１】
ここまでの流れにおいて、従来法との違いは、ＬＴ符号やRaptor符号、あるいは「特願2005-101134」の誤り訂正符号化装置にて用いた方式では、情報系列ｕは送信せず、パリティのみを送信する手順になっている。【０１７２】
（ＢＣＨ符号を用いた実施例）
ＢＣＨ符号などの線形ブロック符号を表現する際、符号長Ｎと情報長ｋを用いて(Ｎ，ｋ)符号という呼び方をする。今、一例として、ＢＣＨ符号の２元（７，４）符号の検査行列を下記（３７）式に示す。【０１７３】
【数２２】
0004620132.tif 000028
【０１７４】
上記手順（１）より、下記（３８）式、下記（３９）式となる。【０１７５】
【数２３】
0004620132.tif 000029
【０１７６】
【数２４】
0004620132.tif 000030
【０１７７】
なお、Ｂ＝Ｉのため、ＨBCH´＝［Ｂ-1Ａ｜Ｂ-1Ｂ］＝［Ｂ-1Ａ｜Ｉ］はすでに完了している。一般には、上記操作を行い、単位行列Ｉを生成する作業が必要になる。【０１７８】
つぎに、ＨBCHL´＝［Ｂ-1Ａ］を求める。Ｂ＝Ｉのため、Ｂ-1＝Ｉとなり、ＨBCHL´＝［Ｂ-1Ａ］＝［Ａ］となる。同様に、生成行列ＧBCHよりＧBCH＝［Ｅ｜Ｄ］＝［Ｅ-1Ｅ｜Ｅ-1Ｄ］＝［Ｉ｜Ｅ-1Ｄ］とすると、［Ｅ-1Ｄ］T＝［Ｂ-1Ａ］＝ＨBCHL´となるため、生成行列あるいはその生成行列を定義する生成多項式よりもとめても良い。【０１７９】
また、生成行列ＧBCHをそのまま用いてｃ＝ｕ×ＧBCHTとして符号化パケットを生成し、受信成功した符号化パケットｃiに対応したＨBCH´＝［Ｂ-1Ａ｜Ｂ-1Ｂ］＝［Ｂ-1Ａ｜Ｉ］は、下三角行列が含まれているため、後退代入により符号語ｖ＝（ｕ｜ｐ）は求められる。【０１８０】
たとえば、後退代入によりｕ＝（ｕ1  ｕ2  ｕ3  ｕ4）＝（０  １  ０  １）を、Ａの１行目を用いてＧＦ（２）上で積和演算すると「１×０＋１×１＋１×０＋０×０＝１」となり、ＨBCH´×ｖT＝０を満たすためには、パリティパケットｐ＝（ｐ1  ｐ2  ｐ3）のｐ1はＩの１行目を用いて、「１＋ｐ1×１＝０」よりｐ1＝１となる。２行目、３行目も同様の計算によりｐ2＝０，ｐ3＝０となる。【０１８１】
一方、ｐはｐT＝ＨERAL´×ｕTでも求めることができ、それらの符号語は一致する。また、復号する際、受信パケット成功が「ｕ1，ｕ2，ｐ2，ｐ3＝０，１，０，０」とすると、下記（４０）式のｐ2，ｐ3がそれぞれ２行目と３行目に対応するため、それらの行を用いて下記（４１）式に示す計算用行列を用意する【０１８２】
【数２５】
0004620132.tif 000031
【０１８３】
【数２６】
0004620132.tif 000032
【０１８４】
この行列にガウス消去法等をかけて下記（４２）式に記載の行列に変換する。【０１８５】
【数２７】
0004620132.tif 000033
【０１８６】
この行列より、「ｕ1，ｕ2，ｐ2，ｐ3＝０，１，０，０」を用いて、後退代入により「ｕ3，ｕ4＝０，１」を解くことができる。【０１８７】
また、生成行列ＧBCHをそのまま用いて、ｃ＝ｕ×ＧBCHTとして符号化パケットを生成し、受信成功した符号化パケットｃiに対応したＧBCHTの行を集めてガウス消去法等をかけても良い。この場合でも、下記（４３）式のＩの部分は、計算対象からはずし、上記と同等にＥ-1Ｄ部分行列のみを計算してもよい。【０１８８】
【数２８】
0004620132.tif 000034
【０１８９】
従来の方式では、情報パケットを送らないため、同等の誤り率の通信路に適用するのに検査行列を７行×４列の検査行列を用意し、その中の４パケットが受信成功したとすると、４行分のガウス消去法を行わなければならず、計算量が大きくなる。また、分散ディスクシステムのように、一度にパケットを保存しているディスクが複数台壊れることが無い場合は、上記手順（５）のような手順で、全ての符号化パケットを用いなくても、一部のパケットのみから自己再生できる。たとえば、パリティパケットｐ1が壊れたことが分かったら、上記（４０）式の１行目の１の立っている列に対応する情報パケット「ｕ1，ｕ2，ｕ3＝０，１，０」のみを用いて、ｐ1＝ｕ1＋ｕ2＋ｕ3で再生できる。また、同等の操作は、もともとの上記（３７）式に示すパリティ検査行列を用いてもできる。【０１９０】
たとえば、再生したい消失(壊れた)パケットに対応する列の中で１が立っている行に対し、その行の中で自分の列以外に１が立っている列に対応したパケットを用いて、それらに対応する自分以外のパケットは、全て正常である場合、その行重み−１個のパケットから自らのパケットを自己再生できる。従って、いずれの方法を用いてもよい。【０１９１】
さらに、やはり分散ディスクシステムのような用途の場合、ある情報パケットが保存してある内容を更新する場合、従来は、再度すべてのディスクを符号化して分散する必要があった。これでは効率が悪いので、更新したデータパケットに関連するパリティパケットのみを更新する手順とする。たとえば、上記（４０）式に対し、ｕ1を更新したい場合は、ｐ1＝ｕ1＋ｕ2＋ｕ3とｐ3＝ｕ1＋ｕ2＋ｕ4でｐ1，ｐ3のみ更新すればよい。上記例では、それほど計算量が減っていないように見えるが、実際の検査行列はもっと疎であるため、計算量の効果は大きくなる。同等の操作は、上記（３７）式に示すもともとのパリティ検査行列を用いてもできる。【０１９２】
たとえば、更新したい情報パケットに対応する列の中で１が立っている行に対し、その行の中で自分の列以外に１が立っている列に対応したパケットを用いて、その行重み−１個のパケットから関連するパリティを更新する。従って、いずれの方法を用いてもよい。【０１９３】
以上のような操作は、一般の線形符号（ハミング符号，巡回符号，ＢＣＨ符号，ＬＤＰＣ符号，畳み込み符号，ターボ符号等）であれば、全て同様な操作で消失訂正符号化復号できる。【０１９４】
また、（ｎ，ｋ）線形符号Ｃの検査記号Ｃをｌ個増やして作られた（ｎ＋１，ｋ）線形符号をＣの拡大符号と呼ぶ。特に、最小距離が奇数の２元（ｎ，ｋ）線形符号に対しては、１ビット検査ビットを付加することにより、最小距離を１だけ増やすことができる。このためには、各符号語に重みが偶数となるように検査ビットを付ければよい。すなわち、符号語（ｗ1，ｗ2，…，ｗn）に対し、下記（４４）式となるような検査ビットｐAを付加し、（ｗ1，ｗ2，…，ｗn，ｐA）を符号語とする符号Ｃ´を作る。このような検査ビットｐAを全パリティ検査ビットと呼ぶ。【０１９５】
ｐA＝ｗ1＋ｗ2＋…＋ｗn
…（４４）【０１９６】
このようにして作られた符号Ｃ´は、元の符号の検査行列をＨとすると、下記（４５）式に示すようにＨの全成分が０の列を付け加え、全成分が１の行を一つ付け加えて得られる（ｎ−ｋ＋１）×ｎ行列Ｈ´を検査行列とする（ｎ＋１，ｋ）線形符号である。このような符号を用い、最小距離をｄ＋１とした拡大符号を本消失訂正符号に用いても良い。【０１９７】
【数２９】
0004620132.tif 000035
【０１９８】
また、一つ付け加える行が、０，１が混在した任意の要素でも最小距離ｄを保証した上で符号を構成できるため、この構成でも良い。【０１９９】
（最小距離の拡大法の適用）
また、生成行列ＧBCHを生成する際、ＢＣＨ符号の生成多項式、たとえば、（７，４）符号の場合、ｇ（ｘ）＝ｘ3＋ｘ＋１を用いているが、このｇ（ｘ）＝ｘ3＋ｘ＋１にｘ＋１をかけたｇ（ｘ）´（＝ｘ3＋ｘ＋１）（ｘ＋１）を用いて生成行列Ｇ´BCHを生成し、ｃ＝ｕ×Ｇ´BCHTとして符号化パケットを生成し、受信が成功した符号化パケットｃiに対応したＧ´BCHTの行を集めてガウス消去法等をかけてもよい。この場合でも、Ｇ´BCHT＝［Ｉ／Ｅ-1Ｄ］のＩの部分は計算対象からはずし、上記と同等にＥ-1Ｄ部分行列のみを計算してもよい。最小距離ｄの（ｎ，ｋ）符号のＧBCHに対してこのＧ´BCHを用いた符号は最小距離ｄ＋１の（ｎ＋１，ｋ）符号となる。【０２００】
（符号語長の調整法）
最小距離ｄの（ｎ，ｋ）符号の検査行列Ｈに対して、任意のｎ−ｋ×ｚの行列Ｅを連接したＨ´´をＨ´´＝［Ｈ｜Ｅ］のように連接すると、最小距離ｄの（ｎ＋ｚ，ｋ）符号を構成できる。これらの手法を用いて、実際のパラメータにあわせた符号を構成し、消失訂正に用いる。【０２０１】
（本方式の効果）
本発明では、ＨERAL´を用いることにより、情報系列とパリティ系列の両方を含む符号語ｖ＝（ｕ｜ｐ）を送信でき、かつ受信に成功した情報パケットｕ´と受信に成功したパリティパケットｐ´の総数が「ｕのパケット数×１０５％」程度集めれば、復号を実行できる。つまり、図１４に示す情報パケット長ｋ＝Ｎ−Ｍが列サイズ、パリティパケット長Ｍが行サイズのＨERAL´に対し、「ｐ´＝（ｕのパケット数×105％)−ｋ」個集まれば、ガウス消去法や「特願2005-101134」の誤り訂正符号化装置にて提案した方式であるＰＣＣ（Polynominal  Combinatorial  Computation）等により復号できる。【０２０２】
従来の方式では、情報パケットを送らないため、同等の誤り率の通信路に適用するのに、上記実施の形態の場合、検査行列を７行×４列の検査行列を用意し、その中の４パケットが受信成功したとすると、４行分のガウス消去法を行わなければならず、計算量が大きくなる。この従来例に対して計算量を少なくできる。【０２０３】
また、BCH符号を用いる場合、「符号化パケットＮ：情報パケットｋ：訂正可能パケットｄ−１（ｄ：最小距離)」が以下のように確定できる。【０２０４】
符号化パケットN：情報パケットｋ：訂正可能パケットd-1(d:最小距離)
７：４：２
１５：１１：２
１５：７：４
１５：５：６
３１：２６：２
３１：２１：４
３１：１６：６
３１：１１：１０
３１：６：１４
６３：５７：２
６３：５１：４
６３：４５：６
６３：３９：８
６３：３６：１０
６３：３０：１２
６３：２４：１４
６３：１８：２０
１２７：１２０：２
１２７：１１３：４
１２７：１０６：６
１２７：９９：８
１２７：９２：１０
１２７：８５：１２
１２７：７８：１４
１２７：７１：１８
１２７：６４：２０
２５５：２４７：２
２５５：２３９：４
２５５：２３１：６
２５５：２２３：８
２５５：２１５：１０
２５５：２０７：１２
２５５：１９９：１５
２５５：１９１：１６
など。【０２０５】
よって、消失可能なパケット数ｄ−１を保証できるメリットがある。つまり、ｄ−１個パケットが消失しても確実に訂正できる。また、ＢＣＨ符号の１ビット拡大符号を用いると、【０２０６】
符号化パケットN：情報パケットｋ：訂正可能パケットd-1(d:最小距離)
８：４：３
１６：１１：３
１６：７：５
１６：５：７
３２：２６：３
３２：２１：５
３２：１６：７
３２：１１：１１
３２：６：１５
６４：５７：３
６４：５１：５
６４：４５：７
６４：３９：９
６４：３６：１１
６４：３０：１３
６４：２４：１５
６４：１８：２１
１２８：１２０：３
１２８：１１３：５
１２８：１０６：７
１２８：９９：９
１２８：９２：１１
１２８：８５：１３
１２８：７８：１５
１２８：７１：１９
１２８：６４：２１
２５６：２４７：３
２５６：２３９：５
２５６：２３１：７
２５６：２２３：９
２５６：２１５：１１
２５６：２０７：１３
２５６：１９１：１７
など。【０２０７】
よって、消失可能なパケット数ｄ−１を保証できるメリットがある。つまり、ｄ−１個のパケットが消失しても確実に訂正できる。同様な効果は、最小距離ｄが保証されている符号であれは全てに適用できる。【０２０８】
また、上記のように符号長や情報長が要求と合わない場合は、情報部分を既知データでパディングする方法がある。【０２０９】
たとえば、符号長ｎ´＝１５０で情報長ｋ´＝１００位にするには、
２５５：２０７：１２
を使って、情報部に１０５個既知の０等でパディングする。そうすると、
１５０：１０２：１２
になる。既知の値でパディングしただけなので訂正できるパケット数は変らない。【０２１０】
同様な効果を示す方法に、ＢＣＨ符号等の巡回符号を短縮化して用いることもできる。この場合、巡回符号の特徴を失わないために、符号化パケットの左端から連続する情報パケットを除いて短縮化するのが普通である。この場合、検査行列を除いた情報パケットに相当する検査行列を削除する。【０２１１】
また、これに拡大符号という方法を用いると、符号長が＋１で修正できるパケット数が＋１となる
２５６：２０７：１３
というものが作れる。この場合、情報部に１０６個既知の０等でパディングすると、
１５０：１０１：１３
が作れる。【０２１２】
さらに、ＢＣＨ符号のような巡回符号の場合は、全て連続するＮ−Ｋ個が消失しても修正できるので、バースト誤りに対する誤り訂正能力も保証できるメリットがある。また、自己再生や更新に関してもパケットの一部を使って再生，更新を行うことができ、従来のように全ての情報パケットを使って符号化パケットを作る必要がなくなるメリットがある。これは１ビット拡大符号でも同様の効果を奏する。単一バースト誤りに限定すると、短縮化巡回符号でもＮ−Ｋ個が消失しても修正できる。【０２１３】
実施の形態６．
つづいて、本発明にかかるＬＤＰＣ符号を用いた効率的な消失訂正符号化復号法を示す。図１５は、本実施の形態のＬＤＰＣ符号のパリティ検査行列ＨMの構成を示す図である。ＨTが上記（１９）式のように、行重みが２の対角行列を階段状にした構成となっている場合、【０２１４】
（第１ステップ）
ＨTのＴD左端の列に１が立っている最初の行に対応するＨMの行と２番目のＨMの行とを足し算する。つぎに、２番目に１が立っている列に対しても同様に足し算をしていく。この操作を繰り返すことにより、ＴDの部分行列が単位行列になるようにする（図１６−１〜図１６−２への変換）。【０２１５】
（第２ステップ）
つぎに、「Dual  Diagonal」となったＨTに対し、第１ステップと同様に処理していく（図１６−２から図１６−３への変換）。これらの操作によりＨM＝［Ａ｜Ｉ］の形に変換できるため、ＨERAL´＝［Ａ］を容易に作成できる。前述したＬＤＰＣ符号は、符号長および符号化率が可変にでき、各符号長，符号化率で良い性能が得られる効果があるが、消失訂正符号としても同様の効果が得られ、かつ実施の形態５に示すメリットを全て満足することが可能となる。【０２１６】
この変換方法は、一部あるいは全てのステップを使って下三角行列の行重みが２のＬＤＧＭ構造であれば、すべてに適用できる。また、行重みが２以上でも同様な操作を重み分繰り返すことで適用できる。【０２１７】
また、生成行列ＧM＝［Ｉ｜Ａ］をそのまま用いて、ｃ＝ｕ×ＧBCHTとして符号化パケットを生成し、受信成功した符号化パケットｃiに対応したＧBCHTの行を集めてガウス消去法等をかけても良い。この場合でも、ＧBCHT＝［Ｉ／Ａ］のＩの部分は、計算対象からはずし、上記と同等にＡ部分行列のみを計算してもよい。【０２１８】
実施の形態７．
図１７は、実施の形態７におけるＩＰベースのストリーミングシステムの構成例を示す図であり、映像／音声信号の送信側が圧縮符号化部１０１とＦＥＣ（Forward  Error  Correction）／インタリーブ部１０２とＲＴＰ（Real-time  Transfer  Protocol）部１０３とＵＤＰ（User  Datagram  Protocol）／ＩＰ部１０４とを備え、受信側が信号受信部１０５とＲＴＰ部１０６とＦＥＣ処理部１０７と画像処理／復号化部１０８とを備えている。なお、ＦＥＣは誤り訂正符号化復号部を意味し、ＲＴＰはリアルタイム画像伝送プロトコルであり、ＵＤＰ／ＩＰはリアルタイム性を重視したＩＰプロトコルである。【０２１９】
以下、図１８を用いてＦＥＣに関連したＲＴＰプロトコルについて説明する。図１８のように、ＲＴＰパケットに約７個のＴＳ（Transport  Stream）パケットが含まれており、情報ＲＴＰパケットは約５ＲＴＰパケットで構成され、それにパリティパケットが誤り率に応じて１〜数パケット（場合によっては数十パケット）追加される。【０２２０】
たとえば、前述した実施の形態５のＢＣＨ符号「ｎ：ｋ：ｄ−１＝６３：３６：１０」を使うと、「５ＲＴＰパケット（各７ＴＳパケット）＋１ＴＳパケット」（全３６ＴＳパケット）を情報パケット、「６ＴＳパケット＋３ＲＴＰパケット（各７ＴＳパケット）」(全２７ＴＳパケット)、で構成できる。この場合、ランダムな１０ＴＳパケットあるいは連続する２７ＴＳパケットの消失まで訂正できる。【０２２１】
たとえば、実施の形態５のＢＣＨ符号の拡大符号「ｎ：ｋ：ｄ−１＝６４：３６：１１」を使い、１パケット分短縮すると、「ｎ：ｋ：ｄ−１＝６３：３５：１１」となる。この場合、５ＲＴＰパケットの情報パケット（全３５パケット）、４ＲＴＰパケットのパリティパケット（全２８パケット）、で構成できる。また、ランダムな１１ＴＳパケットの消失まで訂正できる。【０２２２】
このほかのＢＣＨ符号のパラメータ、ＬＤＰＣ符号、その他の線形符号すべてがこの消失訂正符号に適用できる。その他、パケットおよびディスク単位の消失訂正を行うあらゆる用途に適用できる。【０２２３】
実施の形態８．
つづいて、前述した実施の形態１〜７の符号化処理／復号処理を適用するシステムについて説明する。たとえば、本発明にかかるＬＤＰＣ符号化処理および復号処理は、移動体通信（端末、基地局），無線ＬＡＮ，光通信，衛星通信，量子暗号装置等、通信機器全般に適用できるものであり、具体的には、図１に示すＬＤＰＣ符号化器１（実施の形態１〜４に対応），ＬＤＰＣ復号器５や、実施の形態５に記載の消失訂正符号化機能，実施の形態６に記載の消失訂正符号化復号機能を、各通信機器に搭載し、誤り訂正を行う。【０２２４】
図１９は、本発明にかかる符号化処理／復号処理を、移動体端末２００およびその移動体端末２００と通信を行う基地局３００を備えた移動体通信システムに適用した場合の構成例を示す図であり、移動体端末２００は、消失訂正ＬＤＰＣ符号化器２０１と物理層ＬＤＰＣ符号化器２０２と変調器２０３と復調器２０４と物理層ＬＤＰＣ復号器２０５と消失訂正ＬＤＰＣ復号器２０６とアンテナ２０７とを備え、基地局３００は、消失訂正ＬＤＰＣ復号器３０１と物理層ＬＤＰＣ復号器３０２と復調器３０３と変調器３０４と物理層ＬＤＰＣ符号化器３０５と消失訂正ＬＤＰＣ符号化器３０６とアンテナ３０７とを備えている。【０２２５】
また、図１９に示す移動体端末２００および基地局３００には、物理層にフェージング通信路等に適用する物理層ＬＤＰＣ符号化器および物理層ＬＤＰＣ復号器が搭載されており、データリンク層等の上位層に消失訂正ＬＤＰＣ符号化器および消失訂正ＬＤＰＣ復号器が搭載されている。なお、移動体端末２００および基地局３００の物理層ＬＤＰＣ符号化器には、前述した実施の形態１〜４で説明したＬＰＤＣ符号化器のいずれかの構成を適用する。また、移動体端末２００および基地局３００の消失訂正ＬＤＰＣ符号化器および消失訂正ＬＤＰＣ復号器には、実施の形態５および６に記載の符号化機能および復号機能を適用する。【０２２６】
上記のように構成される移動体通信システムにおいて、移動体端末２００からデータを送信する場合は、まず、データとして、たとえば、音声，メール，WEB等の情報データをパケット化し、消失訂正ＬＤＰＣ符号化器２０１により符号化する。つぎに、物理層では、このパケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器２０２が符号化する。この符号化データを、変調器２０３とアンテナ２０７を介して無線通信路へ送出する。【０２２７】
一方、基地局３００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ３０７と復調器３０３を介して受け取り、復調後の受信データを物理層用ＬＤＰＣ復号器３０２にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。上位層では、消失訂正ＬＤＰＣ復号器３０１が、誤り訂正が成功したパケットのみを用いて情報パケットを再生する。そして、この情報パケットを、ネットワークを介して通信先へ転送する。なお、ネットワークから移動体端末２００が各種データを受信する場合についても、上記と同様の処理で、基地局３００が移動体端末２００へ符号化データを送信し、移動体端末２００が各種データを再生する。基地局３００が移動体端末２００へ符号化データを送信する場合は、まず、データとして、たとえば、音声，メール，ＷＥＢ等の情報データをパケット化し、消失訂正ＬＤＰＣ符号化器３０６により符号化する。つぎに、物理層では、このパケットデータ単位に、フェージング通信路用の物理層ＬＤＰＣ符号化器３０５が符号化する。この符号化データを、変調器３０４とアンテナ３０７を介して無線通信路へ送出する。一方、移動体端末２００では、無線通信路中で発生した誤りを含む受信信号を、アンテナ２０７と復調器２０４を介して受け取り、復調後の受信データを物理層ＬＤＰＣ復号器２０５にて訂正する。そして、物理層では、パケット単位で誤り訂正が成功したかどうかを、上位層に通知する。上位層では、消失訂正ＬＤＰＣ復号器２０６が、誤り訂正が成功したパケットのみを用いて情報パケットを再生する。
【産業上の利用可能性】
【０２２８】
以上のように、本発明にかかる検査行列生成方法および符号化方法は、ディジタル通信における符号化技術として有用であり、特に、符号化方式としてＬＤＰＣ符号を採用する通信装置に適している。
【図１】
0004620132.tif 000036
【図２−１】
0004620132.tif 000037
【図２−２】
0004620132.tif 000038
【図３】
0004620132.tif 000039
【図４】
0004620132.tif 000040
【図５】
0004620132.tif 000041
【図６】
0004620132.tif 000042
【図７】
0004620132.tif 000043
【図８】
0004620132.tif 000044
【図９】
0004620132.tif 000045
【図１０】
0004620132.tif 000046
【図１１】
0004620132.tif 000047
【図１２】
0004620132.tif 000048
【図１３】
0004620132.tif 000049
【図１４】
0004620132.tif 000050
【図１５】
0004620132.tif 000051
【図１６−１】
0004620132.tif 000052
【図１６−２】
0004620132.tif 000053
【図１６−３】
0004620132.tif 000054
【図１７】
0004620132.tif 000055
【図１８】
0004620132.tif 000056
【図１９】
0004620132.tif 000057
【図２０】
0004620132.tif 000058
【図２１】
0004620132.tif 000059