(57)【要約】【課題】信号対雑音電力比に対する復号誤り率特性をシャノン理論限界に近づけるための誤り訂正符号の組織的な構成法を見出し、できる限り低密度でランダム符号化に近い検査行列の構成法を見出すこと。【解決手段】３次元パリテイ符号の3軸パリテイ検査線に対応する3段からなる検査行列を、段毎に巡回シフトしながら拡大し、検査行列を低密度化して復号演算処理を高速化すると共に、拡大検査行列を列方向にランダムに置換してランダム符号化し、シャノン理論限界に近い良好な復号特性を実現する。【選択図】  図４
2007166437.tif 000002
【特許請求の範囲】
【請求項１】
次元数３、符号サイズ５から10の3次元立体構造のパリテイ符号を構成し、その検査行列の水平、垂直、奥行きの3段からなる検査行列部分を、各段ごとに検査行列の長さだけ巡回シフトしながら横方向に50倍（符号サイズの小さい場合）から10倍（符号サイズの大きい場合）に拡大して、所要の符号ブロック長となるよう拡大設定し、検査行列における要素１の出現率を疎としたることを特徴とする検査行列を作成する。ついで、1段目をそのままとして、2段目と3段目に対応する検査行列部分をあわせてランダムに列置換してランダム符号化に近づけるよう構成したることを特徴とする検査行列をもちいる拡大高次元パリテイ符号の構成とその回路および機器。
【請求項２】
上記、拡大後の検査行列のランダム化における2段目と3段目の列置換を別々のランダム置換を用いて行うことにより、ランダム符号性を向上したる検査行列をもちいたることを特徴とする誤り訂正符号の構成と回路および機器。
【請求項３】
拡大後の検査行列のランダム化を第1段、第2段、第3段それぞれ独立に行うことを特徴とする拡大高次元パリテイ符号の検査行列を有する誤り訂正符号の構成と回路および機器。
【請求項４】
上記請求項において示した拡大高次元パリテイ符号の検査行列の各段の置換において、検査行列要素１が四角形のコーナーとなるループを形成しないよう、他段のある同行に要素１が存在する２列方向に、置換する段のある同行に2つの要素が一致する場合には、その置換を排除して、異なる置換を行うことで復号特性を悪くするループ構造を排除したることを特徴とする、拡大高次元パリテイ符号の検査行列のランダム化方法。
【請求項５】
拡大する基となる高次元パリテイ符号の次元を3次元から4次元ないし5次元に拡大して拡大高次元パリテイ符号を上記請求項の手法により構成したることを特徴とする誤り訂正符号の構成と回路および装置。
【請求項６】
検査行列を拡大するとき、基の高次元パリテイ符号の検査行列をそのまま横に整数倍だけ拡大するのでなく、検査行列の幅を部分的に切り出し短縮した形で何箇所か拡大することにより、検査行列の行によって1の数が異なるため、よりランダムな符号化を持つ非正則な拡大高次元パリテイ符号の構成と回路および装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、パケットデータを用いるデジタル通信系の誤りを訂正し、通信の高信頼度化を実現するために利用される高性能誤り訂正符号化方式および装置に関するものである。本発明は各種の雑音等の要因によって発生する受信データの誤りに対して高性能に誤りの訂正を可能とする通信方式、回路方式およびその装置に関する。高速無線LAN方式や高性能携帯電話方式、光通信方式など多くの通信方式と機器に適用でき、通信機器や多くの産業電子機器の高性能化に利用することができる。
【背景技術】
【０００２】
高速度な無線LANや携帯電話、さらにはケーブルLAN方式において、ランダムな誤りやバースト状の誤りが存在する劣悪な環境のパケット通信においては、誤り訂正符号化方式が採用され、受信誤り率の改善がおこなわれている。受信信号の品質は通常、受信信号電力対雑音電力比で評価され、この電力比の小さい場合ほど劣悪な通信環境といわれる。
【０００３】
小さい受信信号電力対雑音電力比で良好な誤り訂正能力を持つ誤り訂正符号化方式が１９６０年代から研究開発されてきた。しかしながら、現在までに実現された受信信号電力対雑音電力比に対する復号誤り率特性は、シャノンによって与えられた理論限界（シャノン限界という）に較べ、かなり特性の劣化したものであった。このため、従来の実用通信機器においては、通信に必要な誤り率を実現するために、シャノン限界に比べ何倍も高い送信電力の増加や、送信電力を一定にすると伝送可能な符号伝送速度を大きく低減する必要があった。
【特許文献１】特開２００１−１３６０７７号公報
【発明の開示】
【発明が解決しようとする課題】
【０００４】
シャノン限界に迫る良好な誤り訂正符号化方式が研究の対象とされてきた。多くの符号の探索の結果、最近においては、低密度パリテイ検査符号方式（Low Density Parity Check; 以下LDPCと略記）をサム−プロダクト（Sum-Product 和−積による演算処理）復号する方式がもっともシャノン理論限界に迫りうる方式であることが示されるに至った。
【０００５】
LDPC符号は、１９６０年代にガァラガー（R.G.Gallager）により提案されたが、１９９６，１９９９年に再評価されるまで、その性能が十分世に知られることがなかった。最近において、情報通信量の拡大に伴って、従来に比べ数千ビットから１万ビットという長いブロック符号が用いられるようになり、ランダム符号化に近い符号構成となってきたことと、情報処理技術や半導体の性能向上により、従来困難であった優れた復号演算処理の実現の可能性が高まってきたことにより、シャノン限界に近い符号性能の向上が期待されることとなってきた。
【０００６】
このLDPC符号化方式は、パリテイ検査方式に特徴があり、パリテイ検査行列の各行に含まれる1の数、すなわちパリテイビット毎に検査されるビット数が従来の符号に比べて著しく少ない特徴を持つ。このため、相対的に計算速度が速くなる。したがって、パリテイ検査ビットとそれに対応する信号点ビットの加算値の対応計算を高速にかつ多数回実行して、信号ビットとパリテイビットの相互の信頼度を逐次向上してゆく確率伝搬ないし信頼度伝搬処理演算が可能となり、誤り率の向上が可能となった。
【０００７】
しかし、LDPC符号の検査行列の構成には多くの自由度があり、それをどのように決定すべきか一般的な設計指針が明らかでない課題がある。このため、効率的なLDPC符号の構成探索が困難となっている。本考案では、LDPCに新たな幾何学的な解釈を与えることでLDPCの新たな符号ファミリーを設定し、設計することを可能とした。
【課題を解決するための手段】
【０００８】
本発明は、先に発明者が開発した高次元パリテイ符号(High Dimensional Parity Code,
HDPCと略記)を出発点とし、その検査行列がLDPCと同じ構造を有することを発見し、LDPCの１ファミリーであることを明らかにする。また一方、ガァラガーのLDPC符号は次元数３の符号サイズがたとえば6の高次元パリテイ符号に対応することを明らかにし、ＬＤＰＣ符号の幾何学的構造の一面を明らかとした。
【０００９】
符号構造の明確なHDPC符号からLDPC符号を構成するための拡張手段を示す。HDPC符号は構造としてほぼLDPC符号と同様の構造を持つが、検査行列に含まれる１の割合がLDPCに較べて多く、かつ高次元立体構造に準じた配列になっている。このため、１の数のより疎で、1の配列に構造性を持たない検査行列に拡張することが求められる。以下では、発明の実施の形態を具体的に示す。
【発明の効果】
【００１０】
本発明の誤り訂正符号化方式および装置によって、新しいLDPC符号方式および装置を設計する具体的方策が明らかになるとともに、規格化信号対雑音電力比に対し良好な誤り率特性を実現できるので、各種通信機器の性能を向上することができる。  
【発明を実施するための最良の形態】
【００１１】
誤り訂正符号化半導体LSIおよび誤り訂正復号化半導体LSIとして実現される。
【実施例１】
【００１２】
図１は説明のために、３次元符号について各辺の符号サイズが２のもっとも簡潔なHDPC符号の構造を示す。以下次元数Ｎ、符号サイズＭのHDPC符号をＮDmＭのように記す。図１のHDPC符号は３Dm2と表現される。一般に、Ｎ次元HDPC符号は、Ｎ次元立体構造の符号点配列からなり、各辺はＭ個の符号点からなる。図１では、最小の符号サイズの場合であるので、情報符号ビットは1個のみで、他はすべてパリテイ検査ビットとなる。
【００１３】
各符号点には、それを貫く各次元のＮ本のパリテイ検査線が存在している。各パリテイ検査線は、合計Ｍ個の符号点からなり、そのうち１個はパリテイビットであり、他のＭ−１個は情報ビットである。パリテイビットは偶数パリテイ、すなわち各パリテイ検査線上の１を示す符号点数が偶数となるようパリテイビットの値を送信側で決定する。この操作は符号化という。
【００１４】
符号の送信は、立方体状の構造を持つ符号から、決められた一定の順番に従って各符号ビットをシリアルに順次通信路に送り出してゆく。通常ランダムな順番に送出される。それは以下の理由による。受信側ではシリアルに到着した符号ビットを送信側の送り出しと同一のランダムな順番により立体構造状に再構築し、立体状の符号構造を再現する。このとき、通信路で受ける連続状のバースト誤りは、受信側の立体構造ではランダムにばらまくように配置され、誤りの検出と訂正の効率を向上できる。
【００１５】
次いで、受信ビット毎に送信側で設定された各次元方向のパリテイ条件にしたがって、他の符号やパリテイビットとの関係が確認にされていき、各ビットの信頼度が計算され、逐次繰り返し演算により信頼度を向上してゆく。この操作を復号という。以下、本符号を含むLDPC符号の復号には、上記の繰り返し演算によって、逐次符号の信頼度を向上してゆく効率的なサム・プロダクト復号法が開発されている。その詳細は文献  和田山  正著、低密度パリテイ検査符号とその復号法（トリケップス、ホワイトシリーズ222）ほかに譲る。
【００１６】
図2は、３Ｄｍ２符号の復号に際して受信側で行うパリテイ検査機能を検査行列Ｈとして示したものである。図１に示したように、３Ｄｍ２符号は3次元の各方向それぞれに２×２＝４本のパリテイ検査線があり、3次元全体では12本の検査線が存在する。それを行列として表現したのが、図2の検査行列である。検査行列の各行の長さは符号長に相当する８ビットであり、パリテイ検査を行うビットについてのみ１が立ち、他は０となっている。したがって、1の数は符号のサイズに等しい2となる。各行はそれぞれの検査線の検査すべきビット位置を示し、検査線数に対応して12行ある。一方、検査行列を列についてみると、１の数は符号の次元数に等しい３となる。このように、各行に含まれる１の数がすべて等しく２であり、また各列に含まれる１の数もすべて等しく３である。このような検査行列をもつ符号を正則（レギュラー）という。そうでない場合を非正則（イレギュラー）という。
【００１７】
図３はガァラガーによるLDPC符号の検査行列の構成法を示す。検査行列は３段に分けられる。最上段の第１行目はｋ（＝６）個の１の一塊からなり、第２行は第１行をｋビット巡回シフトした状態である。順次各行はｋビットだけシフトして作られる。１の値のない場所はすべて０である。検査行列の行の長さは符号長に対応する。なお、符号長はｋの整数倍であるとは限らない。第２段、および第３段は第１段の列をそれぞれ独立にランダムに置換したものからなる。このような置換を行っても検査行列の各行の１の数（重み）は最初のｋの値と変らず、また各列の１の重みも最初と変わらず３のままである。したがって、ガァラガーによるLDPC符号は正則LDPC符号であることがわかる。
【００１８】
以上から、HDPC符号は検査行列の対応から正則LDPC符号の１つであることがわかる。逆に、正則LDPC符号は３次元符号サイズｋ（＝６）のHDPC符号であることがわかる。
しかるに、HDPC符号の検査行列とLDPC符号の検査行列を比較すると、検査行列に含まれる１の数の割合がHDPCでは多く、かつ１の配列に符号の立体構造に基づく検査行列に構造が見られる。１の割合が高くなると、復号演算にかかる計算時間が長くなり、また構造性の符号の場合、復号誤り率特性が悪くなることが知られている。
【００１９】
これら２つの欠点を改善するため、本発明においては、基のHDPC符号の検査行列を拡張した場合の検査行列を図４に示す。基礎となるHDPC（3DmM,３次元でサイズＭ）の検査行列の各段をひとまとめにして、横方向に基のHDPCの符号長だけ巡回シフトしながらｎ倍に拡大する。なお、基の検査行列があてはまらない箇所にはすべて０を挿入する。したがって、拡大しても各列、各行の１の重みは変化せずもとのままである。なお、ｎ倍に拡大されたので拡大検査行列に含まれる１の数はｎ倍となるが、検査行列の大きさ（面積）は、行と列ともにｎ倍になるのでｎ×ｎとなり、拡大HDPC符号における検査行列における１の密度は、HDPC検査行列密度のｎ分の１に低密度化されることがわかる。
【００２０】
ついで、ランダムな符号構造に近づけるため、２段目と３段目の検査行列の列置換を乱数等に従いランダムに行う。この場合、２段目と３段目を同時に置換する場合と、２段目と３段目を別のランダム置換で行う２つの場合がある。その違いについては以下で検討するが、ここでは、２段目と３段目を同時に置換するものとする。ランダムに列置換を行っても、各段の各列には１はひとつしかないので、置換しても検査行列全体としての列重みは変化せず３のままである。また、行方向の重みも１の存在箇所が同じ行方向で位置が変化するだけであるので、置換後も変化しない。したがって、拡大HDPC符号も正則LDPC符号であることが示される。また、符号の符号化率（符号ブロック長に対する情報ビット数の割合）は、拡大する前の基のHDPCと変らない。
【００２１】
しかるに、ランダム列置換を行うとき考慮すべき重要な条件がある。それは、拡大HDPC検査行列の2段目3段目をランダム置換によって形成する場合、検査行列のなかに、図5に示すような１が四角形の隅に４つ配置されるループ構造を作らないようにする必要があることである。ループの形成は検査ビットを２重に割り付けた無駄な符号化であるとともに、復号演算において事後確率計算が正確にできない場合が出てくるため復号特性が劣化する。ランダムな置換を行うとき、ループの出現となる場合には、その置換を用いないように置換のプログラムを組むことで除外できる。ループの形成を避けるためには、図２と図4からわかるように、検査行列の１段目において、ある行の１がある場所（サイズの数だけある）の列方向に当たる２段目及び３段目において、同行に１が２個以上並ばないような置換を選ぶ事である。
【００２２】
基となるHDPC符号の検査行列をそのまま整数倍だけ拡大する場合、正則な符号が構成されることをみてきた。ここでは、検査行列の列のある部分のみを切り出すと、行によって１が除かれるので、そのような部分検査行列をいくつか加えることにより、拡大された検査行列の行方向の１の数が異なるので、非正則な拡大HDPC符号の検査行列が形成される。なお、列方向の１の数は変化しない。非正則化によって、よりランダムな符号化ができるので、シャノン理論限界に近い良好な復号特性が得られる場合がある。
【００２３】
以下、具体的な符号について、計算機シミュレーションによって得られた特性を比較検討する。なお、復号演算処理には、LDPC符号に一般的なサム・プロダクト復号法を用いた。その詳細は前記文献による。シミュレーションでは、基のHDPCを3次元とし、サイズ６（３Ｄｍ６）に選んだ場合を以下に検討する。なお、拡大HDPC符号のブロック長は、基のHDPCのブロック長と拡大数との積になるので、2つの自由度がある。ところで、３Ｄｍ６の符号長は216ビット、情報ビット数125、検査ビット数91ビット、よって伝送速度R=0.579となる。拡大数n=46とすると、拡大HDPC符号のブロック長は9,936ビット、伝送速度は変らず同じである。特性比較を行うLDPC符号はほぼ等しい符号長を持つ正則LDPC符号とした。符号長10,002ビット、情報ビット数5,001ビット、伝送速度R=0.5の符号である。
【００２４】
シミュレーション結果を図６に示す。横軸は基準化信号対雑音電力比（１ビットあたりの信号エネルギー対付加的白色雑音の電力密度ともいう）Eb/N0（デシベルdB）であり、縦軸は復号後のビット誤り率を示す。シミュレーションでは、誤り率の小さいところでの特性を正確に出すためビット数1億個について計算した。サム・プロダクト復号における繰り返し演算回数20回とした。基準化信号対雑音電力比の良いところでは、十分収束した計算結果を得ている。なお、拡大HDPC符号とLDPC符号とでは、伝送速度が異なるため、それぞれの伝送速度に対する復号特性のシャノン理論限界を求めて比較する。拡大HDPC符号の伝送速度R=0.579,正則LDPC符号の伝送速度R=0.5であり、誤り率の良いところでのシャノン理論限界Eb/N0は、図６においてそれぞれ0.58dBと0.19dBとなり、約0.39dBの差がある。
【００２５】
基のHDPC 3Dm6符号の復号特性は符号長が短いこともあり、所要の復号誤り率特性を得るのに必要な基準化信号対雑音電力比は大きい。拡大HDPC符号では、小さな信号対雑音電力比で良好な誤り率特性が実現されており、その改善度はきわめて大きい。
【００２６】
LDPC符号と本発明による拡大HDPC符号の復号誤り率特性を比較すると、復号誤り率が10-6以上の場合には、提案方式が良好であることが示された。たとえば、復号誤り率10-3を達成するに必要な基準化信号対雑音電力比は提案方式ではシャノン理論限界に対し0.58dBと良好であるのに対し、LDPCでは1.45dBとなり、提案符号が0.6dB良いことがわかる。また、復号誤り率10-6では、LDPC符号がシャノン理論限界に対し1.63dBに対して提案拡大HDPC符号では1.15dBとなり、0.48dB特性が良好なことがわかる。携帯電話における利用においては、10-5における特性が規定されるので、ここで比較すると0.55dB特性がよく、十分に携帯電話システムの性能向上に寄与できる値である。
【００２７】
なお、復号誤り率が10-6から10-8の領域で提案符号の特性が劣化することが示された。この原因を検討するため、先に述べた検査行列の2段目と3段目をランダム置換する乱数を変更した場合が、図６に示す（１）と（２）で、誤り率の特性に大きな変化がみられた。このことから、ランダム符号化が誤り率の小さいところでの特性に重要な条件があることが示された。なお、復号誤り率が10-6より大きい範囲では、ランダム置換による差は殆ど見られない。このため、検査行列の2段目と3段目を独立にランダムに変更することが望ましいとの結論に至った。
【産業上の利用可能性】
【００２８】
携帯電話方式の実現において、従来の誤り訂正符号に較べても、また最近の符号に較べても特性が良好であるので、利用の可能性が高い。また、広く各種のデジタル機器の誤り訂正回路にLSIに実装して利用される期待が大きい。  
【図面の簡単な説明】
【００２９】
【図１】本発明の基となる3次元符号サイズ２の最も簡潔な3次元パリテイ符号の構成を示す。また、8個の符号点と水平方向、縦方向、奥行き３方向のパリテイ検査線との対応を示す。（実施例１）
【図２】図1の3次元サイズ２のパリテイ符号に対応する検査行列Ｈを示す，（実施例１）
【図３】ガァラガーによる検査行列の構成法。
【図４】提案符号による検査行列の構成法。（実施例１）
【図５】検査行列におけるループの形成状況を示す。
【図６】本発明による提案符号の基準化信号対雑音電力比と復号誤り率特性。（実施例１）
【図１】
2007166437.tif 000003
【図２】
2007166437.tif 000004
【図３】
2007166437.tif 000005
【図４】
2007166437.tif 000006
【図５】
2007166437.tif 000007
【図６】
2007166437.tif 000008