(57)【要約】  次世代移動体通信や深宇宙通信で用いられる低密度パリティ検査（LDPC）符号を、サイクル分布を利用して構成する方法および送／受信装置とシステムを開示する。当該方法は、LDPC符号の基本行列における、非零の巡回シフト要素値から構成されるブロックサイクルの分布を決定するブロックサイクル決定ステップと、決定したブロックサイクルの分布に基づいて、各ブロックサイクルに含まれる非零の巡回シフト要素値の優先度を決定する優先度決定ステップと、LDPC符号の検査行列のあらゆる大きさの置換要素について最大公約数を求め、それを素因数分解する計算ステップを含む。この方法によれば、すべての異なる置換要素を利用して得られた構造化LDPC符号の実際の検査行列のいずれにも、ショートループが含まれないようにすることができる。
2010035501.tif 000002
【特許請求の範囲】
【請求項１】
サイクル分布を利用してLDPC符号を構成する方法であって、
LDPC符号の基本行列における、非零の巡回シフト要素値から構成されるブロックサイクルの分布を決定するブロックサイクル決定ステップと、
決定したブロックサイクルの分布に基づいて、各ブロックサイクルに含まれる非零の巡回シフト要素値の優先度を決定する優先度決定ステップと、
LDPC符号の検査行列のあらゆる大きさの置換要素について最大公約数を求め、それを素因数分解する計算ステップと、
を有する方法。
【請求項２】
次式において置換要素の最大公約数の素因数が含まれないように、ブロックサイクルを構成する巡回シフト値を決定する巡回シフト値決定ステップ、をさらに有する、
請求項１に記載の方法。
【数１】
2010035501.tif 000010
【請求項３】
LDPC符号の基本行列において、相互に重なり合ったブロックサイクルが複数含まれるとき、相互に重なり合った、ブロックサイクルの長さが短いブロックサイクルにおける巡回シフト値を先に決定する、
請求項１に記載の方法。
【請求項４】
LDPC符号の基本行列において、異なるブロックサイクルに共通の巡回シフト値が含まれるとき、重なり合ったブロックサイクルがより長いブロックサイクルとなるように共通の巡回シフト値を決定する、
請求項３に記載の方法。
【請求項５】
LDPC符号の基本行列において、相互に重なり合ったブロックサイクルが複数含まれるとき、相互に重なり合った、ブロックサイクルの長さが短いブロックサイクルにおける巡回シフト値を先に決定する、
請求項２に記載の方法。
【請求項６】
LDPC符号の基本行列において、異なるブロックサイクルに共通の巡回シフト値が含まれるとき、重なり合ったブロックサイクルがより長いブロックサイクルとなるように共通の巡回シフト値を決定する、
請求項１に記載の方法。
【請求項７】
請求項１から６のいずれかに記載の方法に基づいてLDPC符号化を行う符号化手段と、
前記LDPC符号化を施されたビット系列を変調して、データシンボルを生成する変調手段と、
前記データシンボルを送信する送信手段と、
を具備する送信装置。
【請求項８】
制御信号を復調する復調手段と、
復調された制御信号を復号する復号手段と、
前記復号手段から入力された各受信側からの制御信号に基づいて、符号化率および／または再送を制御する制御手段と、
前記変調手段からの前記データシンボルと、制御手段からの制御信号と、パイロット信号とを多重する多重手段と、をさらに具備し、
前記符号化手段は、前記制御手段から入力された符号化率で抽出した符号化ビット系列を、前記変調手段へ出力し、
前記送信手段は、前記多重手段において多重されたベースバンド信号周波数変換して、無線信号として送信する、
請求項７に記載の送信装置。
【請求項９】
送信側から送信された信号を受信する受信手段と、
受信した信号をデータ列と制御情報とに分離する分離手段と、
前記分離手段からの前記データ列を復調する復調手段と、
復調されたデータ列を、請求項１から６のいずれかに記載の方法で復号し、受信結果状態に基づいてACK／NACKの判定を行う復号手段と、
を具備する受信装置。
【請求項１０】
前記分離手段からの受信パイロット信号に基づいて品質推定を行う回線品質推定手段と、
前記回線品質推定手段からのCQIと、前記復号手段からの前記受信結果状態に基づくACK／NACK信号とによって、フィードバック情報用のフレームを生成する制御信号生成手段と、をさらに具備する、
請求項９に記載の受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信分野において、最適化されたサイクル分布を利用して低密度パリティ検査符号（LDPC Code:Low Density Parity-Check Code、以下「LDPC符号」と称す）を構成する方法およびその送信装置、受信装置と送受信システムに関する。特に、異なる置換要素を用いて得られた構造化LDPC符号の検査行列におけるショートループを、ブロックサイクル(Block Cycle)に基づいて効果的に除去する方法およびその送信装置、受信装置に関する。
【背景技術】
【０００２】
近年、技術の発展に伴い、無線通信システムでは非常に高いレートでデータを伝送することが可能となった。このため、従来技術に比べより高い効率の符号化方式が必要とされている。低密度パリティ検査（LDPC）符号は、最近十年ほどの間に再発見された非常に有力なフォワード誤り訂正符号化方法(Forward Error Correcting codes)である。極めて長い符号語長の条件下で、LDPC符号はすでにシャノン限界に迫っているため、ターボ符号の有効な代替技術とみなされており、次世代移動体通信と深宇宙通信で用いられる可能性が大きい。【０００３】
LDPC符号は、1962年にGallagerによって最初に発見された。LDPC符号とは、パリティ検査行列に基づいて定義される符号であり、各列が小さい定数j（j≧1）である1を含み、各行が小さい定数k（k＞j）である１を含むという特性を有する。Gallagerは、これら符号語間の最小距離は、符号長の増加に伴い線形に増加すること、またBSC（Bynary Symmetric Channel:バイナリ対称チャネル）において、復号誤り確率は、符号長の増加に従って小さくなることを証明した。【０００４】
1981年、Tannerがグラフを用いて符号語を表現するコンセプトを発表したことから、LDPC符号の検査行列は、タナーグラフと呼ばれる双方向2部グラフに対応付けられるようになった。タナーグラフ用いて構成されたLDPC符号は、並列復号により、復号の複雑さを大幅に低減することを可能とした。タナーはまた、Sum-ProductアルゴリズムとMin-Sum アルゴリズムという二つの情報伝達アルゴリズムを詳細に分析し、有限／無ループのタナーグラフに基づくSum-Product復号法とMin-Sum復号法の最適性を証明した。しかし、タナーグラフは実際にはランダムなグラフを用いて構成されたものであり、ショートループがタナーグラフ内に存在することは避けられず、これらのショートループが復号情報の重複伝達を招いて、復号過程のメッセージ間で独立性仮定を満たせなくなり、反復復号アルゴリズムの収束性に悪影響を与えている。【０００５】
1996年に、Mackay、Spielmanらが、LDPC符号がターボ符号と同様の優れた機能を有し、符号長が長い場合においてはターボ符号を凌ぐことをそれぞれ再発見した。現在、LDPC符号に関しては、主として以下の方向に集中して研究が行われている。【０００６】
第一に、LDPC符号をGF（2）上で構成するのではなく、GF（4）、GF（8）など、多元(GF(q))のガロア拡大体上で符号化する問題である。Mackay、Daveyらは、この方向において多くの研究を行い、すばらしい成果を上げた（参考文献1：D.J.C.MacKay, R.M.Neal “Near Shannon Limit Performance of low density parity check codes”, Electronics Letters, 32(18):1645-1646, August 1996. Reprinted Electronics Letters, vol 33, no 6, 13th March 1997, p.457-458）（参考文献2：M.C.Davey，D.J.C.MacKay“Low density parity check codes over GF(q)”,In Proceedings of the 1998 IEEE Information Theory Workshop, p.70-71、IEEE, June 1998)。多元検査行列を入念に構成することにより、性能を大幅に向上することが可能となった。【０００７】
第二に、Gallagerの提起したLDPC符号では、検査行列の列と行の重みは固定であり、通常、正則LDPC符号（Regular LDPCまたはGallager符号）と呼ばれる。Luby、Mitzenmacher、Shokrollahi、Spielmanは、非正則な2元LDPC符号(Irregular LDPC)を構成することを初めて発表した（参考文献3：M.Luby, M.Mitzenmacher, M.A.Shokrollahi, D.A.Spielman, V.Stemann “Practical loss-resilient codes”,Proc.29th Annu. Symp. Theory of Computing, 1997, p.150-159）。【０００８】
Lubyは1998年に、行、列の重みの制限を緩和し、列（行）ごとの重みが異なる非正則LDPC符号を構成することを発表した。研究結果によれば、当初のGallager符号に比べ、非正則LDPC符号の性能は大幅に向上した。現在、これら二つの研究方向を最適に組み合わせ、より性能が高い非GF（2）の非正則LDPC符号の探求が行われている。驚くべきことに、Daveyによってターボ符号より性能が優れたLDPC符号が発見されている（参考文献4：Matthew C.Davey, “PHD Thesis: Error-correction using Low-Density Parity-Check Code”, Gonville and Caius College, Cambridge, 1999）。
【発明の概要】
【０００９】
復号アルゴリズムが相対的にシンプルであることと、ハードウェアのレベルが向上したことにより、1998年以来、LDPC符号のハードウェアの実現は興味深い研究テーマとなっている。Flarion社はスループットが10Gb/sのLDPC復号チップを製作している。また、LDPCの復号アルゴリズムによれば、より高い次数での並列処理を実現できるため、広範に応用される見通しがある。
【００１０】
しかしながら、上記のような従来技術では、ショートループの存在によってLDPC復号アルゴリズムの性能が劣化する問題を解決するには至っていない。
【００１１】
本発明は、比較的小さいループ長を持つショートループを、ブロックサイクルに基づいて効果的に除去する方法およびその送信装置、受信装置と送受信システムを提供する。この方法によれば、構造化LDPC符号(Structured LDPC codes)の基本行列中の重なり合った（overlap）ブロックサイクルにおける巡回シフト要素に、構造化LDPC符号のすべての置換要素（expanding factor）の最大公約数が含まれないようにすることによって、実際の検査行列中に存在するショートループを効果的に除去して、より優れた誤り訂正性能を持つ構造化LDPC符号を生成する。
【００１２】
本発明の一の態様によれば、LDPC符号の基本行列における、非零の巡回シフト要素値から構成されるブロックサイクルの分布を決定するブロックサイクル決定ステップと、決定したブロックサイクルの分布に基づいて、各ブロックサイクルに含まれる非零の巡回シフト要素値の優先度を決定する優先度決定ステップと、LDPC符号の検査行列のあらゆる大きさの置換要素に対して最大公約数を求め、それを素因数分解する計算ステップとを有する、サイクル分布を利用してLDPC符号を構成する方法を提供する。
【００１３】
本発明の方法によれば、重なり合ったブロックサイクルによって、実現可能な実際のループ長の上限が決まるため、交差するブロックサイクル中の巡回シフト値に、構造化LDPC符号のすべての置換要素の最大公約数が含まれないようにすることで、すべての異なる置換要素を利用して得られる構造化LDPC符号の実際の検査行列に、ショートループが含まれないことを保証できる。
【００１４】
本発明の他の態様によれば、上述の方法に従ってLDPC符号化を行う符号化手段と、前記LDPC符号化後のビット系列を変調して、データシンボルを生成する変調手段と、前記データシンボルを送信する送信手段とを具備する送信装置を提供する。
【００１５】
本発明のさらに他の態様によれば、送信側から送信された信号を受信する受信手段と、受信したデータ信号をデータ列と制御情報とに分離する分離手段と、前記分離手段からの前記データ列を復調する復調手段と、復調されたデータ列を上述の方法に従って復号して、受信結果状態ＡＣＫ／ＮＡＣＫ（ACKnowledgement/Negative ACKnowledgement）の判定を行う復号手段とを具備する受信装置を提供する。
【図面の簡単な説明】
【００１６】
【図１】LDPC符号の検査行列と行重みおよび列重みを示す図
【図２】LDPC符号のタナーグラフ
【図３ａ】検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルを示す概念図
【図３ｂ】検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルを示す概念図
【図４】IEEE 802.16e規格の符号化率3/4のLDPC符号のパリティ検査行列を示す図
【図５】置換要素zfを用いて基本行列を置換して得られる、実際の符号化に用いられる検査行列の概念図
【図６】相互に重なり合ったブロックサイクルについての概念図
【図７】基本行列中のブロックサイクルと対応する、実際の検査行列におけるショートループの概念図
【図８】基本行列における値を最適に選択した場合に、対応する実際の検査行列にショートループが存在しないことを示す概念図
【図９】相互に重なり合ったブロックサイクルにおける、巡回シフト値の選択案の概念図
【図１０】相互に重なり合ったブロックサイクルが複数含まれる基本行列の概念図
【図１１】本発明の実施例による送信装置の構造の概念図
【図１２】本発明の実施例による受信装置の構造の概念図
【発明を実施するための形態】
【００１７】
以下、本発明の上述およびその他の目的、特徴および長所がさらに明確となるよう、図面と組み合わせて本発明の好ましい実施例を説明する。
【００１８】
以下、図面を参照して本発明の実施例を詳細に説明する。なお、本発明に対する理解があいまいになることを防ぐために、本発明に必須ではない細部や機能の説明は省略する。
【００１９】
本発明がよりよく理解されるよう、まず、LDPC符号の検査行列によって定義される行重み、列重みと、LDPC符号の検査行列の行と列とに対応する、LDPC符号化のタナーグラフについて説明する。
【００２０】
図1は、LDPC符号の検査行列によって定義される行重みと列重みを示す。図1において、行列中のある行またはある列の非零要素の個数が、対応する行または列の重みを表している。図１に示すように、第1〜12列の列重みは、順に3、3、3、3、2、2、2、2、1、1、1、1である。
【００２１】
LDPC符号は、実質的には線形ブロック符号である。図2は、図1に示すLDPC符号の検査行列の行と列とに対応する、LDPC符号化のタナーグラフである。図2に示すように、1つの線形符号は、1つのタナーグラフ（2部グラフ（bipartite graph）とも称す）に表すことができ、Ｇ＝｛Ｖ∪Ｃ，Ｅ｝と記す。ここで、集合Ｖは変数ノード（variable node）から構成される集合であり、各変数ノードは、LDPC符号語における該当する列の符号化ビットに対応している。集合Ｃはチェックノード（check node）の集合を表し、各チェックノードは各検査条件式、すなわちLDPC符号語行列の該当する行に対応している。集合Ｅは、エッジの集合を表す。
【００２２】
タナーグラフの変数ノードに対応する符号化ビットが、あるチェックノードが表す検査条件式に関係する場合（すなわち、当該符号化ビットに対応する検査行列の列ベクトルにおいて、チェックノードに対応する行の要素が「0」ではない場合）には、例えば、図1に示すLDPC符号の検査行列の行と列において、第5行の第2、5、9列の要素は「０」ではない。したがって、エッジ（edge）を用いてチェックノード5と変数ノード2、5、9をそれぞれ接続することができる。また、各ノードに接続するエッジの本数を、当該ノードの次数（degree）と称する。
【００２３】
したがって、LDPC符号のパリティ検査行列の各列に対応する符号化ビットは、タナーグラフにおける変数ノードとして表され、パリティ検査行列の各行に対応するパリティ検査条件式は、チェックノードで表される。現在、LDPC符号化ビットの性能に対する研究は、LDPC符号化の誤り訂正性能の解析のため、主として上記のタナーグラフに基づいて行われている。
【００２４】
図3a、3bはそれぞれ検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルの定義を示している。図3bに示すタナーグラフにおいて、上の数字は検査行列の列に対応する変数ノードを表し、下の数字は検査行列の行に対応するチェックノードを表している。図3bにおける各接続線は、行列中の非零要素を表している。タナーグラフにおいて、任意のある変数ノードから出発し、チェックノードと変数ノードを通り出発点に戻るループがあり、なおかつ経由する変数ノードとチェックノードが重複せずにループが得られた場合、そのループを「サイクル」と称す。
【００２５】
例えば、図3bに示すように、変数ノード５から出発し、チェックノード3、変数ノード7、チェックノード4、変数ノード8、チェックノード5とまわって、出発点である変数ノード5へ戻っている、このような閉じた経路をループと呼ぶ。タナーグラフにおいて、長さｖのループは、あるノードから出発して再び当該ノードへ戻る、ｖ本のエッジを含む閉じた経路である。タナーグラフにおける最短のループの長さの値を周長（girth）と称す。LDPC符号のパリティ検査行列に定義されるタナーグラフでは、図3bに示すように、長さ4のループが存在しうる最短のループである。ループの存在がLDPC符号化の反復復号性能に影響を与えるというのが、現在の共通の認識であり（参考文献1を参照）、反復復号プロセスの収束性に影響する。したがって、LDPC符号の構成過程においては、ショートループ（例えば、長さ4または6など、所定値（例えば8）より小さい長さのループ）が出現することをできるかぎり避ける必要がある。このため、各変数ノードが構成可能なループの最小の長さが、当該変数ノードがLDPC反復復号アルゴリズムに与える影響を決定する。つまり、ある変数ノードが構成可能なループの最小の長さが小さいほど、誤り訂正能力が弱くなる。
【００２６】
ターボ符号と比較して、LDPC符号の復号プロセスはシンプルであり、また並列度が高い。しかし、LDPC符号は本質的にはブロック符号であるため、検査行列は多くの零要素を含む疎な行列である。通常の場合においては、検査行列の次数が大きいため、逆演算を求めることが非常に複雑になり、また符号化の複雑さの指数も、符号長が増加するにしたがって増加する。
【００２７】
また、システマチックコード(組織符号)については、その符号化プロセスは実際には入力された情報ビットに基づいて、対応するパリティビットを決定するプロセスであるため、検査行列を直接利用して線形符号化が行えることが望ましい。また、LDPCの検査行列は次数が大きく、IEEE 802.16eにおいて符号化率1/2と規定されているLDPC符号は最大符号長が2304であるため、対応する検査行列は1152×2304の行列となる。受信側および送信側で、このような行列を保持するためには、多くのメモリを占用する必要があり、またメモリの読み取りおよび情報ビットとの乗算操作によって、相応の処理遅延が引き起こされる。
【００２８】
これらの問題に基づいて、構造化LDPC（Structured-LDPC，または準巡回LDPC、Quasi-LDPCとも称す）が提案された（参考文献3、4を参照）。すなわち、まず次数の小さいm×n次の基本行列を定義し、実際に符号化する際には、次数z×zの部分行列を用いて基本行列中の非零要素を置き換えることにより、実際の符号化に用いる（m×z）×（n×z）の検査行列が得られる。
【００２９】
図4はIEEE 802.16規格（2005年版、8.4.9.2.5.1節のLDPC符号に関する記載）を例にとり、選択肢の一つである符号化率3/4のLDPC符号のパリティ検査行列を示している。図4に示すように、ここでは6行×24列、符号化率3/4のLDPC符号の基本行列が提示されている。図4における要素「−1」は、実際には図1における要素「0」に対応し、「−1」以外の要素は、対応する巡回シフト値を表す。この基本行列における各要素はすべてz×zの部分行列を表しており、zの大きさの違いによって、同一の基本行列を用いて、符号化率が同じで符号長が異なる一組のLDPC符号を得ることができる。行列の置換の面から見れば、図4における要素「−1」はz×zの全要素零行列を表し、その他の要素は、z×zの単位行列の列を｛p(f,i,j)｝で表される値で巡回シフトして得られた部分行列を表している。zが取る値は、規格において定義された置換要素zf,  f∈[0,18]に対応している。要素「0」は、巡回シフトされていない単位行列を表し、その他のシフトの値｛p(f,i,j)｝は、対応する置換要素zfと行列中の「非零」および「−1」要素から、以下の式（1）によって計算して得られる。
【数１】
2010035501.tif 000003
ここで、p(i,j)は巡回シフト値を表す。
【００３０】
上記の内容から、ｚが取る値の違いに応じて、同一のLDPC符号化の基本行列から一連の離散的な符号長が得られることがわかる。図5の右側の行列は、置換後の検査行列である。行列の左側の要素aはシステマチックビットに対応しており、元の情報ビットのビット数を表している。規格によれば、基本行列において、システマチックビット部分に対応する列数はkbと定義され、kbは基本行列の列数（nb）から行数（mb）を減算した数に等しい。実際の検査行列の次数は、置換要素zfを、列数（nb）と行数（mb）にそれぞれ乗算したものである。例えば、置換要素zf =3に設定した場合、実際の検査行列は、図5の右側の行列が示すように、6行×3×8列×3＝18行×24列の行列となる。
【００３１】
IEEE 802.16e規格において、zの取る値の範囲は24〜96であり、ステップサイズは4である。ここで、ステップサイズとは連続するzが取る値の間隔を指す。例えば、z=24の後続の値は、順に28，32，36，…，88，92，96である。つまり、合計19個の置換要素zの値が規定され、z0＜z1＜…＜z18と記される。LDPCの基本行列は一定であるため、置換要素を変更することによって、同一の基本行列から生成された、次数は異なるが符号化率は同じである一連の検査行列が得られる。このような構造を称して、構造化LDPC符号という。
【００３２】
図5は、置換要素zfを用いて基本行列を置換して得られた、実際の符号化に用いられる検査行列を示す。図5において、左側は構造化LDPC符号の基本行列であり、右側は置換後の検査行列である。図5からわかるように、構造化LDPC符号の基本行列は、その中の非零要素が実際はz×zの部分行列に対応している。したがって、基本行列においてこれらの非零要素は小さなブロックであるため、これらの非零元素が構成するループをブロックサイクル（block cycle）と称す（図3aの左上側の正方形ブロックサイクルを参照）。したがって、ブロックサイクルは、基本行列における非零要素で構成されるループである。もし異なるブロックサイクルが重なり合うと、つまり、異なるブロックサイクルが共通の非零要素を含むと、これらの重なり合ったブロックサイクルは、長さがより長いブロックサイクルを構成する。
【００３３】
図6は、相互に重なり合ったブロックサイクルについての概念図である。図6に示すように、長さ4の重なり合った2つのブロックサイクル、すなわちブロックサイクル（a02→a00→a20→a22）とブロックサイクル（a12→a11→a21→a22）が含まれている。ここでは、ループ長を用いて、ブロックサイクル中の変数ノードとチェックノード間を接続するエッジの数を表す。この2つのブロックサイクルに共通の要素はa22である。さらに、長さ6のブロックサイクル、すなわち（a02→a00→a20→a21→a11→a12）も存在する。この、長さ4の重なり合った2つのブロックサイクルは、長さ14のブロックサイクル（またはチェーンとも称す）、すなわちa22→a21→a11→a12→a02→a00→a20→a22→a12→a11→a21→a20→a00→a02→a22を構成することができる。
【００３４】
基本行列におけるブロックサイクルと、検査行列に実際に存在するループ（または物理ループとも称す）のループ長との関係は、次式（2）で決定することができる。ブロックサイクルの長さLBcycleを2l、aiをブロックサイクル中の巡回シフト値、ｚを構造化LDPC符号の基本行列の置換要素とし、ｒを次式（2）を成立させる最小の正の整数（ここで、ｒは自然数）とすると、
【数２】
2010035501.tif 000004
となり、置換要素を用いて基本行列から得られた実際の検査行列において、当該ブロックサイクルに対応する実際の検査行列中のループの実際のループ長は、LPcycle=rLBcycle=2lrである。r=1の場合は、LPcycle=LBcycleであり、r＞1の場合は、LPcycle＞LBcycle、すなわち実際の検査行列におけるループの実際のループ長は、基本行列におけるブロックサイクルのループ長より長くなる。
【００３５】
基本行列における同一行または同一列の非零要素の、対応する実際の検査行列における実際の非零要素の行と列の座標への影響を利用すれば、次式（3）が成立することがわかる。
a22−a21＋a11−a12＋a02−a00＋a20−a22＋a12−a11＋a21−a20＋a00−a02 ≡ 0 (mod z)   …(3)
【００３６】
つまり、重なり合った複数のブロックサイクルから構成されるブロックサイクルは、実際の置換要素が取る値に関わらず、すべて
【数３】
2010035501.tif 000005
となる。そのため、このとき一定してLPcycle=LBcyclの関係を有する。したがって、重なり合ったブロックサイクルは、実現可能な実際のループ長の上限を決定する。
【００３７】
構造化LDPC符号は、1つの基本行列が複数の異なる置換要素に対応しているため、1つの基本行列から異なる次数の複数の検査行列を得ることが可能であり、さらにこれら検査行列からは、同じ符号化率で符号長の異なる複数のLDPC符号が得られる。通常は、コンピュータで探索する方法により基本行列における非零要素を特定するが、この方法では、異なる置換要素から得られたすべての検査行列にショートループが存在しないことを保証することは困難である。
【００３８】
図７は実際の検査行列における、基本行列中のブロックサイクルに対応するショートループの概念図である。図7に示すように、基本行列中の非零要素a00、a02、a20、a22から構成されるブロックサイクルは、a00=4, a02=3, a20=2, a22 =7であれば、上記の式（2）から（a00−a02＋a20−a22）=6が得られる。
【００３９】
（1）置換要素z=4のとき（図7における置換要素=4の場合に対応）、6 mod(4)≠0である。すなわち、式（2）を成立させるためには、rは必然的に1より大きくなければならない。この場合には、前記のとおり、LPcycle＞LBcycle=4となる。
（2）置換要素z=6のとき（図7における置換要素=6の場合に対応）、6 mod(6)=0である。すなわち、式（2）を成立させる最小の正の整数はr=1はであり、前記のとおり、LPcycle=LBcycle=4となる。つまり、置換要素z=6の場合に得られた実際の検査行列中に、長さ4のショートループが存在する。したがって、置換要素zの19個の値に対して、実際の検査行列中に長さ4のショートループが存在する場合がある。前述のとおり、この場合には生成されるLDPC符号復号アルゴリズムの性能を低下させてしまう。
【００４０】
つまり、適切な非零要素の値を選択するようにすれば、どのような置換要素の場合でも、基本行列から生成される実際の検査行列にショートループは含まれない。
【００４１】
このような事実に基づき、本発明の実施例では、ブロックサイクルに基づいて、小さいループ長を持つショートループを効果的に除去する。当該実施例においては、構造化LDPC符号の基本行列の行数と列数、および対応する非零要素の位置を決定した後、さらに各非零要素の値を決定して、実際の検査行列を生成する。選択された非零要素の値が、本明細書において前述した特定の性質を有する場合には、すべての置換要素について、基本行列から生成される実際のどの検査行列にもショートループが含まれない。図8は基本行列における値を適切に選択した場合に、対応する実際の検査行列にショートループが存在しないことを示す概念図である。各非零要素の値は、次のプロセスで決定する。
【００４２】
1）基本行列におけるブロックサイクルの分布を決定する。
2）決定されたブロックサイクルの分布に基づいて、各ブロックサイクルに対し、当該ブロックサイクルが含む非零要素値の優先度を決定する。ループ長が短い相互に重なり合ったブロックサイクルに対して、高い優先度を割り当てる。
3）取り得る置換要素すべてについて、その最大公約数（GCD, greatest common divider）を求め、それを素因数分解する。
4）ブロックサイクルにおける非零の巡回シフト要素の値を決定し、
【数４】
2010035501.tif 000006
が置換要素の最大公約数の素因数を含まないようにする。すなわち、LDPC符号の基本行列において重なり合ったブロックサイクル中の、非零の巡回シフト要素が、LDPC符号のすべての置換要素の最大公約数を含まないように、ブロックサイクル中の非零の巡回シフト要素の値を決定する。
【００４３】
以下、IEEE 802.16e規格の規定を例にとり、各非零要素値を決定するプロセスを説明する。ここで定義された、置換要素zが取る値の範囲は24〜96であり、粒度はgz=4である。これら置換要素はziと記され、ここでiは0〜18の整数を表し、かつz0＜z1＜…＜z18である。したがって、次式（4）を用いてziを表すことができる。
zi＝4×（6＋i）,  ここで、i ∈[0,18]      …（4）
上記の式から、この19個の異なる置換要素すべての最大公約数は4であるため、2×2に分解できる。
【００４４】
図6を参照すると、長さ4の相互に重なり合った2つのブロックサイクル、すなわちブロックサイクル（a02→a00→a20→a22）とブロックサイクル（a12→a11→a21→a22）が含まれている。この2つのブロックサイクルの共通要素はa22である。また、図6に示す重なりには、長さ6のブロックサイクル、すなわち（a02→a00→a20→a21→a11→a12）も存在している。この、長さ4の重なり合った2つのブロックサイクルは、長さ14のブロックサイクル（またはチェーンとも称す）を構成することができ、その経路はa22→a21→a11→a12→a02→a00→a20→a22→a12→a11→a21→a20→a00→a02→a22である。
【００４５】
上記の式（3）によれば、a22−a21＋a11−a12＋a02−a00＋a20−a22＋a12−a11＋a21−a20＋a00−a02 ≡ 0 (mod z) の関係がある。
【００４６】
すなわち、重なり合った複数のブロックサイクルによって構成されるブロックサイクルは、実際の置換要素が取る値に関わらず、常に
【数５】
2010035501.tif 000007
が成り立つ。したがって、このとき一定してLPcycle=LBcyclの関係を有する。
【００４７】
この結果、重なり合ったブロックサイクルにおける、非零の巡回シフト要素aijの値をどのように選択しても、任意の置換要素によって構成された実際の検査行列中に、必然的に長さ14のループが含まれる。したがって、重なり合ったブロックサイクルは、実現可能な実際のループ長の上限を決定する。すなわち、非零要素aijの値をどのように選択しても、実際の検査行列において、実現可能な最大ループ長は14である。そのため、実際の検査行列中のループの分布を最適化することは、長さ4のブロックサイクルと長さ6のブロックサイクルとに対応するループの長さをできるかぎり14に近づけるよう、非零要素aijの値をいかに選択するかに帰結する。
【００４８】
IEEE 802.16e規格の規定によれば、置換要素ｚの最大公約数は4と定義されている。当該最大公約数は2×2に分解することができる。上記ステップ3）の記載によれば、
【数６】
2010035501.tif 000008
に置換要素zの最大公約数4の素因数2が含まれないようにするためには、長さ4のブロックサイクルにおける非零の巡回シフト値の要素が、次式（5）と（6）を成立させる必要がある。
(a00−a02＋a22−a20)≠2k, ここで、k∈N      …（5）
(a12−a22＋a21−a11)≠2k, ここで、k∈N      …（6）
つまり、式（5）および（6）の結果は奇数となる。したがって、式（2）即ち
【数７】
2010035501.tif 000009
を、すべてのｚに対して成立させるためには、rは必ず因数4を含み、r≧4でなければならない。よって、実際の検査行列における、長さ4のブロックサイクルに対応するループの長さはLPcycle≧r×LBcycl=16であることがわかる。これは前記の最適化の条件を明らかに満たしている。
【００４９】
長さ6のブロックサイクルについては、当該ブロックサイクルに含まれる非零要素が、次式（7）を成立させなければならない。
(a00−a02＋a12−a11＋a21−a20)= formula(2) + formula(3)   …（7）
【００５０】
上記の内容から、選択された非零要素値は、式（5）および（6）の結果を奇数としているので、式（7）の結果は必然的に偶数となり、素因数2を含む。したがって、実際の検査行列において、すべての置換要素が長さ6のショートループを含まないようにするためには、式（2）を成立させるrの値が必ず1より大きくなるよう、式（7）の結果が4の倍数にならないようにする必要がある。このため、上記6個の非零要素の選択は、さらに、長さ4の重なり合った2つのブロックサイクルに共通の要素であるa22の奇偶に基づいて決定することができる。すなわち、
1．a22が奇数であれば、その他の非零要素の値は、(a00−a02−a20)と(a12−a11＋a21)とをいずれも偶数とし、なおかつ4に対する余りが互いに異なるような値にしなければならない。
2．a22が偶数であれば、その他の非零要素の値は、(a00−a02−a20)と(a12−a11＋a21)とをいずれも奇数とし、なおかつ4に対する余りを等しくする値にしなければならない。
【００５１】
以下、a22が偶数である場合を例にとり、その他の要素の決定方法を詳細に説明する。2つのブロックサイクルに共通の要素a22＝6とすると、この場合、図9に示すように、長さ4の2つのブロックサイクルについて、a00=12, a02=2, a20=7, a12 =11, a11=9, a21=5とすると、a00−a02＋a22−a20（ブロックサイクルa02→a00→a20→a22）とa12−a22＋a21−a11（ブロックサイクルa12→a11→a21→a22）がいずれも奇数、すなわちa00−a02＋a22−a20≡1 (mod 2)かつa12−a22＋a21−a11 ≡1 (mod 2)となる。また、長さ6のブロックサイクルにおける非零要素は、次のような性質となる。
1) （a00−a02−a20）と（a12−a11＋a21）とを4で除算した余りが同一、すなわちa00−a02−a20 ≡1 (mod 4) かつa12−a11＋a21≡ 3 (mod 4)
2)  a00−a02＋a12−a11＋a21−a20 ≡2 (mod 4)、すなわち、上記式の結果は4の倍数ではない
【００５２】
式（7）の結果は、置換要素の最大公約数4で割り切れないため、式（2）を成立させる最小の正の整数rは少なくとも2の倍数、すなわち素因数2を含まなければならないので、r≧2である。よって、実際の検査行列における、長さ6のブロックサイクルに対応するループの長さはLPcycle≧r×LBcycl=12であることがわかる。これは前記の最適化の条件を明らかに満たしている。
【００５３】
また、基本行列において、相互に重なり合ったブロックサイクルが、複数含まれる場合には、その中で、長さのより小さい重なり合ったブロックサイクルが、より高い優先度を有する。すなわち、重なり合った、短いブロックサイクルにおける非零要素の値を、最初に決定する。
【００５４】
図10は、相互に重なり合ったブロックサイクルを複数含む、基本行列の概念図である。図10に示すように、長さ4のブロックサイクル（a02→a00→a20→a22）と長さ4のブロックサイクル（a12→a11→a21→a22）が重なり合っており、共通の要素はa22である。また、長さ6のブロックサイクル（a04→a06→a36→a35→a45→a44）と長さ4のブロックサイクル（a06→a07→a37→a36）が重なり合っており、共通の要素はa06とa36である。前者に含まれる、重なり合ったブロックサイクルの長さは、後者より小さいため、前者はより高い充当優先度を有する。
【００５５】
図11は、本発明の実施例による送信局のブロック図である。以下の説明において、データの送信側を送信局、データの受信側を受信局とする。図11に示すように、送信局はLDPC符号化部101、制御部109、変調部102、多重部103、送信RF（Radio Frequency）部104、受信RF部106、復調部107、復号部108およびアンテナ105を具備する。
【００５６】
LDPC符号化部101では、検査符号を用いて、マザー符号化率（mother code rate）にてLDPC符号化を行う。制御部109から入力した符号化率に基づいて、抽出された符号化ビット系列を変調部102へ出力する。
【００５７】
変調部102では、LDPC符号化ビット系列を変調してデータシンボルを生成し、多重部103へ出力するとともに、制御部109からの制御情報に基づいて、符号化率、変調方式および再送を制御する。
【００５８】
多重部103では、変調部102から入力したデータシンボル、制御部109から入力した制御情報、およびパイロット信号を多重する。
【００５９】
送信RF部104では、多重部103で多重したベースバンド信号を周波数変換してRF信号とし、アンテナ105から送信する。
【００６０】
受信RF部106では、受信局からの制御信号（CQIおよびACK/NACK情報）をアンテナ105で受信し、それを周波数変換してベースバンド信号とする。
【００６１】
復調部107では、制御信号（CQIおよびACK/NACK情報）を復調し、復号部108へ出力する。
【００６２】
復号部108では、変調された制御信号（CQIおよびACK/NACK情報）を復号し、制御部109へ出力する。
【００６３】
制御部109では、復号部108から入力した各受信局からの制御信号（CQIおよびACK/NACK情報）に基づいて、符号化率と再送を制御する。本発明の実施例によれば、受信局から報告されるCQI（Channel Quality Indicator）として、SINR（Signal Interference Noise Ratio）、平均SIR（Signal Interference Ratio）、MCS（Modulation Coding Scheme）パラメータを用いることができる。
【００６４】
図12は、本発明の実施例による受信装置の構成を示すブロック図である。以下の説明において、データの送信側を送信局、データの受信側を受信局とする。図12に示すように、本発明の実施例の受信装置は、受信RF部202、分離部203、復調部204、LDPC復号部205、制御信号生成部207、回線品質推定部206、符号化部208、変調部209、送信RF部210およびアンテナ201を具備する。
【００６５】
受信RF部202では、アンテナ201を介して送信局から送信された信号を受信し、周波数変換してベースバンド信号とする。受信したデータ信号は分離部203へ出力し、受信したパイロット信号は回線品質推定部206へ出力する。
【００６６】
分離部203では、受信したデータ信号をデータ系列と制御情報（符号化率、データ系列長など）に分離し、データ系列を復調部204へ、制御情報（符号化率、データ系列長など）をLDPC復号部205へ出力する。
【００６７】
復調部204では、分離部203から入力したデータ系列を復調する。LDPC復号部205では、復調後のデータ系列に対し誤り訂正復号（LDPC復号）を行い、受信データを得る。また、受信データのエラーチェックを行い、ACK/NACK判定を行う。判定結果であるACK/NACK信号は、制御信号生成部207へ出力される。
【００６８】
制御信号生成部207では、回線品質推定部206から入力したCQIおよびLDPC復号部205から入力したACK/NACK信号から、フィードバック情報用のフレームを生成し、符号化部208へ出力する。
【００６９】
符号化部208、変調部209では、制御信号生成部207から入力したフィードバック情報を符号化、変調し、送信RF部210へ出力する。
【００７０】
送信RF部210は符号化および変調された信号を周波数変換してRF信号とし、アンテナ201から送信する。
【００７１】
しかしながら、受信装置における送信部（符号化部208、変調部209、送信RF部210から構成される）は、送信局の送信部と同様の構成でもよいし、その他の構成でもよい。
【００７２】
以上、好ましい実施例を用いて本発明を説明したが、本発明の思想及び範囲内で種々の変更、置換及び追加が可能であることは、当業者にとって自明である。従って、本発明の範囲は上述の特定の実施例に限定されるものではなく、添付の「請求の範囲」によって限定されるべきものである。
【００７３】
また、上記実施例の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部または全てを含むように１チップ化されてもよい。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【００７４】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。
【００７５】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。
【００７６】
２００８年９月２７日出願の中国出願２００８１０１６８９１３．９に含まれる明細書、図面及び要約書の開示内容は、すべて本願に援用される。
【図１】
2010035501.tif 000011
【図２】
2010035501.tif 000012
【図３ａ】
2010035501.tif 000013
【図３ｂ】
2010035501.tif 000014
【図４】
2010035501.tif 000015
【図５】
2010035501.tif 000016
【図６】
2010035501.tif 000017
【図７】
2010035501.tif 000018
【図８】
2010035501.tif 000019
【図９】
2010035501.tif 000020
【図１０】
2010035501.tif 000021
【図１１】
2010035501.tif 000022
【図１２】
2010035501.tif 000023
【手続補正書】
【提出日】平成22年11月26日(2010.11.26)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信分野において、最適化されたサイクル分布を利用して低密度パリティ検査符号（LDPC Code:Low Density Parity-Check Code、以下「LDPC符号」と称す）を構成する方法およびその送信装置、受信装置と送受信システムに関する。特に、異なる置換要素を用いて得られた構造化LDPC符号の検査行列におけるショートループを、ブロックサイクル(Block Cycle)に基づいて効果的に除去する方法およびその送信装置、受信装置に関する。
【背景技術】
【０００２】
近年、技術の発展に伴い、無線通信システムでは非常に高いレートでデータを伝送することが可能となった。このため、従来技術に比べより高い効率の符号化方式が必要とされている。低密度パリティ検査（LDPC）符号は、最近十年ほどの間に再発見された非常に有力なフォワード誤り訂正符号化方法(Forward Error Correcting codes)である。極めて長い符号語長の条件下で、LDPC符号はすでにシャノン限界に迫っているため、ターボ符号の有効な代替技術とみなされており、次世代移動体通信と深宇宙通信で用いられる可能性が大きい。
【０００３】
LDPC符号は、1962年にGallagerによって最初に発見された。LDPC符号とは、パリティ検査行列に基づいて定義される符号であり、各列が小さい定数j（j≧1）である1を含み、各行が小さい定数k（k＞j）である１を含むという特性を有する。Gallagerは、これら符号語間の最小距離は、符号長の増加に伴い線形に増加すること、またBSC（Bynary Symmetric Channel:バイナリ対称チャネル）において、復号誤り確率は、符号長の増加に従って小さくなることを証明した。
【０００４】
1981年、Tannerがグラフを用いて符号語を表現するコンセプトを発表したことから、LDPC符号の検査行列は、タナーグラフと呼ばれる双方向2部グラフに対応付けられるようになった。タナーグラフ用いて構成されたLDPC符号は、並列復号により、復号の複雑さを大幅に低減することを可能とした。タナーはまた、Sum-ProductアルゴリズムとMin-Sum アルゴリズムという二つの情報伝達アルゴリズムを詳細に分析し、有限／無ループのタナーグラフに基づくSum-Product復号法とMin-Sum復号法の最適性を証明した。しかし、タナーグラフは実際にはランダムなグラフを用いて構成されたものであり、ショートループがタナーグラフ内に存在することは避けられず、これらのショートループが復号情報の重複伝達を招いて、復号過程のメッセージ間で独立性仮定を満たせなくなり、反復復号アルゴリズムの収束性に悪影響を与えている。
【０００５】
1996年に、Mackay、Spielmanらが、LDPC符号がターボ符号と同様の優れた機能を有し、符号長が長い場合においてはターボ符号を凌ぐことをそれぞれ再発見した。現在、LDPC符号に関しては、主として以下の方向に集中して研究が行われている。
【０００６】
第一に、LDPC符号をGF（2）上で構成するのではなく、GF（4）、GF（8）など、多元(GF(q))のガロア拡大体上で符号化する問題である。Mackay、Daveyらは、この方向において多くの研究を行い、すばらしい成果を上げた（参考文献1：D.J.C.MacKay, R.M.Neal “Near Shannon Limit Performance of low density parity check codes”, Electronics Letters, 32(18):1645-1646, August 1996. Reprinted Electronics Letters, vol 33, no 6, 13th March 1997, p.457-458）（参考文献2：M.C.Davey，D.J.C.MacKay“Low density
parity check codes over GF(q)”,In Proceedings of the 1998 IEEE Information Theory Workshop, p.70-71、IEEE, June 1998)。多元検査行列を入念に構成することにより
、性能を大幅に向上することが可能となった。
【０００７】
第二に、Gallagerの提起したLDPC符号では、検査行列の列と行の重みは固定であり、通常、正則LDPC符号（Regular LDPCまたはGallager符号）と呼ばれる。Luby、Mitzenmacher、Shokrollahi、Spielmanは、非正則な2元LDPC符号(Irregular LDPC)を構成することを初めて発表した（参考文献3：M.Luby, M.Mitzenmacher, M.A.Shokrollahi, D.A.Spielman, V.Stemann “Practical loss-resilient codes”,Proc.29th Annu. Symp. Theory of Computing, 1997, p.150-159）。
【０００８】
Lubyは1998年に、行、列の重みの制限を緩和し、列（行）ごとの重みが異なる非正則LDPC符号を構成することを発表した。研究結果によれば、当初のGallager符号に比べ、非正則LDPC符号の性能は大幅に向上した。現在、これら二つの研究方向を最適に組み合わせ、より性能が高い非GF（2）の非正則LDPC符号の探求が行われている。驚くべきことに、Daveyによってターボ符号より性能が優れたLDPC符号が発見されている（参考文献4：Matthew
C.Davey, “PHD Thesis: Error-correction using Low-Density Parity-Check Code”, Gonville and Caius College, Cambridge, 1999）。
【発明の概要】
【０００９】
復号アルゴリズムが相対的にシンプルであることと、ハードウェアのレベルが向上したことにより、1998年以来、LDPC符号のハードウェアの実現は興味深い研究テーマとなっている。Flarion社はスループットが10Gb/sのLDPC復号チップを製作している。また、LDPCの復号アルゴリズムによれば、より高い次数での並列処理を実現できるため、広範に応用される見通しがある。
【００１０】
しかしながら、上記のような従来技術では、ショートループの存在によってLDPC復号アルゴリズムの性能が劣化する問題を解決するには至っていない。
【００１１】
本発明は、比較的小さいループ長を持つショートループを、ブロックサイクルに基づいて効果的に除去する方法およびその送信装置、受信装置と送受信システムを提供する。この方法によれば、構造化LDPC符号(Structured LDPC codes)の基本行列中の重なり合った（overlap）ブロックサイクルにおける巡回シフト要素に、構造化LDPC符号のすべての置換要素（expanding factor）の最大公約数が含まれないようにすることによって、実際の検査行列中に存在するショートループを効果的に除去して、より優れた誤り訂正性能を持つ構造化LDPC符号を生成する。
【００１２】
本発明の一の態様によれば、LDPC符号の基本行列における、非零の巡回シフト要素値から構成されるブロックサイクルの分布を決定するブロックサイクル決定ステップと、決定したブロックサイクルの分布に基づいて、各ブロックサイクルに含まれる非零の巡回シフト要素値の優先度を決定する優先度決定ステップと、LDPC符号の検査行列のあらゆる大きさの置換要素に対して最大公約数を求め、それを素因数分解する計算ステップとを有する、サイクル分布を利用してLDPC符号を構成する方法を提供する。
【００１３】
本発明の方法によれば、重なり合ったブロックサイクルによって、実現可能な実際のループ長の上限が決まるため、交差するブロックサイクル中の巡回シフト値に、構造化LDPC符号のすべての置換要素の最大公約数が含まれないようにすることで、すべての異なる置換要素を利用して得られる構造化LDPC符号の実際の検査行列に、ショートループが含まれないことを保証できる。
【００１４】
本発明の他の態様によれば、上述の方法に従ってLDPC符号化を行う符号化手段と、前記LDPC符号化後のビット系列を変調して、データシンボルを生成する変調手段と、前記デー
タシンボルを送信する送信手段とを具備する送信装置を提供する。
【００１５】
本発明のさらに他の態様によれば、送信側から送信された信号を受信する受信手段と、受信したデータ信号をデータ列と制御情報とに分離する分離手段と、前記分離手段からの前記データ列を復調する復調手段と、復調されたデータ列を上述の方法に従って復号して、受信結果状態ＡＣＫ／ＮＡＣＫ（ACKnowledgement/Negative ACKnowledgement）の判定を行う復号手段とを具備する受信装置を提供する。
【図面の簡単な説明】
【００１６】
【図１】LDPC符号の検査行列と行重みおよび列重みを示す図
【図２】LDPC符号のタナーグラフ
【図３ａ】検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルを示す概念図
【図３ｂ】検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルを示す概念図
【図４】IEEE 802.16e規格の符号化率3/4のLDPC符号のパリティ検査行列を示す図
【図５】置換要素zfを用いて基本行列を置換して得られる、実際の符号化に用いられる検査行列の概念図
【図６】相互に重なり合ったブロックサイクルについての概念図
【図７】基本行列中のブロックサイクルと対応する、実際の検査行列におけるショートループの概念図
【図８】基本行列における値を最適に選択した場合に、対応する実際の検査行列にショートループが存在しないことを示す概念図
【図９】相互に重なり合ったブロックサイクルにおける、巡回シフト値の選択案の概念図
【図１０】相互に重なり合ったブロックサイクルが複数含まれる基本行列の概念図
【図１１】本発明の実施例による送信装置の構造の概念図
【図１２】本発明の実施例による受信装置の構造の概念図
【発明を実施するための形態】
【００１７】
以下、本発明の上述およびその他の目的、特徴および長所がさらに明確となるよう、図面と組み合わせて本発明の好ましい実施例を説明する。
【００１８】
以下、図面を参照して本発明の実施例を詳細に説明する。なお、本発明に対する理解があいまいになることを防ぐために、本発明に必須ではない細部や機能の説明は省略する。
【００１９】
本発明がよりよく理解されるよう、まず、LDPC符号の検査行列によって定義される行重み、列重みと、LDPC符号の検査行列の行と列とに対応する、LDPC符号化のタナーグラフについて説明する。
【００２０】
図1は、LDPC符号の検査行列によって定義される行重みと列重みを示す。図1において、行列中のある行またはある列の非零要素の個数が、対応する行または列の重みを表している。図１に示すように、第1〜12列の列重みは、順に3、3、3、3、2、2、2、2、1、1、1、1である。
【００２１】
LDPC符号は、実質的には線形ブロック符号である。図2は、図1に示すLDPC符号の検査行列の行と列とに対応する、LDPC符号化のタナーグラフである。図2に示すように、1つの線形符号は、1つのタナーグラフ（2部グラフ（bipartite graph）とも称す）に表すことができ、Ｇ＝｛Ｖ∪Ｃ，Ｅ｝と記す。ここで、集合Ｖは変数ノード（variable node）から構成される集合であり、各変数ノードは、LDPC符号語における該当する列の符号化ビットに対応している。集合Ｃはチェックノード（check node）の集合を表し、各チェックノー
ドは各検査条件式、すなわちLDPC符号語行列の該当する行に対応している。集合Ｅは、エッジの集合を表す。
【００２２】
タナーグラフの変数ノードに対応する符号化ビットが、あるチェックノードが表す検査条件式に関係する場合（すなわち、当該符号化ビットに対応する検査行列の列ベクトルにおいて、チェックノードに対応する行の要素が「0」ではない場合）には、例えば、図1に示すLDPC符号の検査行列の行と列において、第5行の第2、5、9列の要素は「０」ではない。したがって、エッジ（edge）を用いてチェックノード5と変数ノード2、5、9をそれぞれ接続することができる。また、各ノードに接続するエッジの本数を、当該ノードの次数（degree）と称する。
【００２３】
したがって、LDPC符号のパリティ検査行列の各列に対応する符号化ビットは、タナーグラフにおける変数ノードとして表され、パリティ検査行列の各行に対応するパリティ検査条件式は、チェックノードで表される。現在、LDPC符号化ビットの性能に対する研究は、LDPC符号化の誤り訂正性能の解析のため、主として上記のタナーグラフに基づいて行われている。
【００２４】
図3a、3bはそれぞれ検査行列とタナーグラフの形式で、LDPC符号に対応するタナーグラフ中のサイクルの定義を示している。図3bに示すタナーグラフにおいて、上の数字は検査行列の列に対応する変数ノードを表し、下の数字は検査行列の行に対応するチェックノードを表している。図3bにおける各接続線は、行列中の非零要素を表している。タナーグラフにおいて、任意のある変数ノードから出発し、チェックノードと変数ノードを通り出発点に戻るループがあり、なおかつ経由する変数ノードとチェックノードが重複せずにループが得られた場合、そのループを「サイクル」と称す。
【００２５】
例えば、図3bに示すように、変数ノード５から出発し、チェックノード3、変数ノード7、チェックノード4、変数ノード8、チェックノード5とまわって、出発点である変数ノード5へ戻っている、このような閉じた経路をループと呼ぶ。タナーグラフにおいて、長さｖのループは、あるノードから出発して再び当該ノードへ戻る、ｖ本のエッジを含む閉じた経路である。タナーグラフにおける最短のループの長さの値を周長（girth）と称す。LDPC符号のパリティ検査行列に定義されるタナーグラフでは、図3bに示すように、長さ4のループが存在しうる最短のループである。ループの存在がLDPC符号化の反復復号性能に影響を与えるというのが、現在の共通の認識であり（参考文献1を参照）、反復復号プロセスの収束性に影響する。したがって、LDPC符号の構成過程においては、ショートループ（例えば、長さ4または6など、所定値（例えば8）より小さい長さのループ）が出現することをできるかぎり避ける必要がある。このため、各変数ノードが構成可能なループの最小の長さが、当該変数ノードがLDPC反復復号アルゴリズムに与える影響を決定する。つまり、ある変数ノードが構成可能なループの最小の長さが小さいほど、誤り訂正能力が弱くなる。
【００２６】
ターボ符号と比較して、LDPC符号の復号プロセスはシンプルであり、また並列度が高い。しかし、LDPC符号は本質的にはブロック符号であるため、検査行列は多くの零要素を含む疎な行列である。通常の場合においては、検査行列の次数が大きいため、逆演算を求めることが非常に複雑になり、また符号化の複雑さの指数も、符号長が増加するにしたがって増加する。
【００２７】
また、システマチックコード(組織符号)については、その符号化プロセスは実際には入力された情報ビットに基づいて、対応するパリティビットを決定するプロセスであるため、検査行列を直接利用して線形符号化が行えることが望ましい。また、LDPCの検査行列は次数が大きく、IEEE 802.16eにおいて符号化率1/2と規定されているLDPC符号は最大符号
長が2304であるため、対応する検査行列は1152×2304の行列となる。受信側および送信側で、このような行列を保持するためには、多くのメモリを占用する必要があり、またメモリの読み取りおよび情報ビットとの乗算操作によって、相応の処理遅延が引き起こされる。
【００２８】
これらの問題に基づいて、構造化LDPC（Structured-LDPC，または準巡回LDPC、Quasi-LDPCとも称す）が提案された（参考文献3、4を参照）。すなわち、まず次数の小さいm×n次の基本行列を定義し、実際に符号化する際には、次数z×zの部分行列を用いて基本行列中の非零要素を置き換えることにより、実際の符号化に用いる（m×z）×（n×z）の検査行列が得られる。
【００２９】
図4はIEEE 802.16規格（2005年版、8.4.9.2.5.1節のLDPC符号に関する記載）を例にとり、選択肢の一つである符号化率3/4のLDPC符号のパリティ検査行列を示している。図4に示すように、ここでは6行×24列、符号化率3/4のLDPC符号の基本行列が提示されている。図4における要素「−1」は、実際には図1における要素「0」に対応し、「−1」以外の要素は、対応する巡回シフト値を表す。この基本行列における各要素はすべてz×zの部分行列を表しており、zの大きさの違いによって、同一の基本行列を用いて、符号化率が同じで符号長が異なる一組のLDPC符号を得ることができる。行列の置換の面から見れば、図4における要素「−1」はz×zの全要素零行列を表し、その他の要素は、z×zの単位行列の列を｛p(f,i,j)｝で表される値で巡回シフトして得られた部分行列を表している。zが取る値は、規格において定義された置換要素zf,  f∈[0,18]に対応している。要素「0」は、巡回シフトされていない単位行列を表し、その他のシフトの値｛p(f,i,j)｝は、対応する置換要素zfと行列中の「非零」および「−1」要素から、以下の式（1）によって計算して得られる。
【数１】
2010035501.tif 000024
ここで、p(i,j)は巡回シフト値を表す。
【００３０】
上記の内容から、ｚが取る値の違いに応じて、同一のLDPC符号化の基本行列から一連の離散的な符号長が得られることがわかる。図5の右側の行列は、置換後の検査行列である。行列の左側の要素aはシステマチックビットに対応しており、元の情報ビットのビット数を表している。規格によれば、基本行列において、システマチックビット部分に対応する列数はkbと定義され、kbは基本行列の列数（nb）から行数（mb）を減算した数に等しい。実際の検査行列の次数は、置換要素zfを、列数（nb）と行数（mb）にそれぞれ乗算したものである。例えば、置換要素zf =3に設定した場合、実際の検査行列は、図5の右側の行列が示すように、6行×3×8列×3＝18行×24列の行列となる。
【００３１】
IEEE 802.16e規格において、zの取る値の範囲は24〜96であり、ステップサイズは4である。ここで、ステップサイズとは連続するzが取る値の間隔を指す。例えば、z=24の後続の値は、順に28，32，36，…，88，92，96である。つまり、合計19個の置換要素zの値が規定され、z0＜z1＜…＜z18と記される。LDPCの基本行列は一定であるため、置換要素を変更することによって、同一の基本行列から生成された、次数は異なるが符号化率は同じである一連の検査行列が得られる。このような構造を称して、構造化LDPC符号という。
【００３２】
図5は、置換要素zfを用いて基本行列を置換して得られた、実際の符号化に用いられる検査行列を示す。図5において、左側は構造化LDPC符号の基本行列であり、右側は置換後
の検査行列である。図5からわかるように、構造化LDPC符号の基本行列は、その中の非零要素が実際はz×zの部分行列に対応している。したがって、基本行列においてこれらの非零要素は小さなブロックであるため、これらの非零元素が構成するループをブロックサイクル（block cycle）と称す（図3aの左上側の正方形ブロックサイクルを参照）。したがって、ブロックサイクルは、基本行列における非零要素で構成されるループである。もし異なるブロックサイクルが重なり合うと、つまり、異なるブロックサイクルが共通の非零要素を含むと、これらの重なり合ったブロックサイクルは、長さがより長いブロックサイクルを構成する。
【００３３】
図6は、相互に重なり合ったブロックサイクルについての概念図である。図6に示すように、長さ4の重なり合った2つのブロックサイクル、すなわちブロックサイクル（a02→a00→a20→a22）とブロックサイクル（a12→a11→a21→a22）が含まれている。ここでは、ループ長を用いて、ブロックサイクル中の変数ノードとチェックノード間を接続するエッジの数を表す。この2つのブロックサイクルに共通の要素はa22である。さらに、長さ6のブロックサイクル、すなわち（a02→a00→a20→a21→a11→a12）も存在する。この、長さ4の重なり合った2つのブロックサイクルは、長さ14のブロックサイクル（またはチェーンとも称す）、すなわちa22→a21→a11→a12→a02→a00→a20→a22→a12→a11→a21→a20→a00→a02→a22を構成することができる。
【００３４】
基本行列におけるブロックサイクルと、検査行列に実際に存在するループ（または物理ループとも称す）のループ長との関係は、次式（2）で決定することができる。ブロックサイクルの長さLBcycleを2l、aiをブロックサイクル中の巡回シフト値、ｚを構造化LDPC符号の基本行列の置換要素とし、ｒを次式（2）を成立させる最小の正の整数（ここで、ｒは自然数）とすると、
【数２】
2010035501.tif 000025
となり、置換要素を用いて基本行列から得られた実際の検査行列において、当該ブロックサイクルに対応する実際の検査行列中のループの実際のループ長は、LPcycle=rLBcycle=2lrである。r=1の場合は、LPcycle=LBcycleであり、r＞1の場合は、LPcycle＞LBcycle、すなわち実際の検査行列におけるループの実際のループ長は、基本行列におけるブロックサイクルのループ長より長くなる。
【００３５】
基本行列における同一行または同一列の非零要素の、対応する実際の検査行列における実際の非零要素の行と列の座標への影響を利用すれば、次式（3）が成立することがわかる。
a22−a21＋a11−a12＋a02−a00＋a20−a22＋a12−a11＋a21−a20＋a00−a02 ≡ 0 (mod
z)   …(3)
【００３６】
つまり、重なり合った複数のブロックサイクルから構成されるブロックサイクルは、実際の置換要素が取る値に関わらず、すべて
【数３】
2010035501.tif 000026
となる。そのため、このとき一定してLPcycle=LBcyclの関係を有する。したがって、重なり合ったブロックサイクルは、実現可能な実際のループ長の上限を決定する。
【００３７】
構造化LDPC符号は、1つの基本行列が複数の異なる置換要素に対応しているため、1つの基本行列から異なる次数の複数の検査行列を得ることが可能であり、さらにこれら検査行列からは、同じ符号化率で符号長の異なる複数のLDPC符号が得られる。通常は、コンピュータで探索する方法により基本行列における非零要素を特定するが、この方法では、異なる置換要素から得られたすべての検査行列にショートループが存在しないことを保証することは困難である。
【００３８】
図７は実際の検査行列における、基本行列中のブロックサイクルに対応するショートループの概念図である。図7に示すように、基本行列中の非零要素a00、a02、a20、a22から構成されるブロックサイクルは、a00=4, a02=3, a20=2, a22 =7であれば、上記の式（2）から（a00−a02＋a20−a22）=6が得られる。
【００３９】
（1）置換要素z=4のとき（図7における置換要素=4の場合に対応）、6 mod(4)≠0である。すなわち、式（2）を成立させるためには、rは必然的に1より大きくなければならない。この場合には、前記のとおり、LPcycle＞LBcycle=4となる。
（2）置換要素z=6のとき（図7における置換要素=6の場合に対応）、6 mod(6)=0である。すなわち、式（2）を成立させる最小の正の整数はr=1はであり、前記のとおり、LPcycle=LBcycle=4となる。つまり、置換要素z=6の場合に得られた実際の検査行列中に、長さ4のショートループが存在する。したがって、置換要素zの19個の値に対して、実際の検査行列中に長さ4のショートループが存在する場合がある。前述のとおり、この場合には生成されるLDPC符号復号アルゴリズムの性能を低下させてしまう。
【００４０】
つまり、適切な非零要素の値を選択するようにすれば、どのような置換要素の場合でも、基本行列から生成される実際の検査行列にショートループは含まれない。
【００４１】
このような事実に基づき、本発明の実施例では、ブロックサイクルに基づいて、小さいループ長を持つショートループを効果的に除去する。当該実施例においては、構造化LDPC符号の基本行列の行数と列数、および対応する非零要素の位置を決定した後、さらに各非零要素の値を決定して、実際の検査行列を生成する。選択された非零要素の値が、本明細書において前述した特定の性質を有する場合には、すべての置換要素について、基本行列から生成される実際のどの検査行列にもショートループが含まれない。図8は基本行列における値を適切に選択した場合に、対応する実際の検査行列にショートループが存在しないことを示す概念図である。各非零要素の値は、次のプロセスで決定する。
【００４２】
1）基本行列におけるブロックサイクルの分布を決定する。
2）決定されたブロックサイクルの分布に基づいて、各ブロックサイクルに対し、当該ブロックサイクルが含む非零要素値の優先度を決定する。ループ長が短い相互に重なり合ったブロックサイクルに対して、高い優先度を割り当てる。
3）取り得る置換要素すべてについて、その最大公約数（GCD, greatest common divider）を求め、それを素因数分解する。
4）ブロックサイクルにおける非零の巡回シフト要素の値を決定し、
【数４】
2010035501.tif 000027
が置換要素の最大公約数の素因数を含まないようにする。すなわち、LDPC符号の基本行列において重なり合ったブロックサイクル中の、非零の巡回シフト要素が、LDPC符号のすべての置換要素の最大公約数を含まないように、ブロックサイクル中の非零の巡回シフト要素の値を決定する。
【００４３】
以下、IEEE 802.16e規格の規定を例にとり、各非零要素値を決定するプロセスを説明する。ここで定義された、置換要素zが取る値の範囲は24〜96であり、粒度はgz=4である。これら置換要素はziと記され、ここでiは0〜18の整数を表し、かつz0＜z1＜…＜z18である。したがって、次式（4）を用いてziを表すことができる。
zi＝4×（6＋i）,  ここで、i ∈[0,18]      …（4）
上記の式から、この19個の異なる置換要素すべての最大公約数は4であるため、2×2に分解できる。
【００４４】
図6を参照すると、長さ4の相互に重なり合った2つのブロックサイクル、すなわちブロックサイクル（a02→a00→a20→a22）とブロックサイクル（a12→a11→a21→a22）が含まれている。この2つのブロックサイクルの共通要素はa22である。また、図6に示す重なりには、長さ6のブロックサイクル、すなわち（a02→a00→a20→a21→a11→a12）も存在している。この、長さ4の重なり合った2つのブロックサイクルは、長さ14のブロックサイクル（またはチェーンとも称す）を構成することができ、その経路はa22→a21→a11→a12→a02→a00→a20→a22→a12→a11→a21→a20→a00→a02→a22である。
【００４５】
上記の式（3）によれば、a22−a21＋a11−a12＋a02−a00＋a20−a22＋a12−a11＋a21−a20＋a00−a02 ≡ 0 (mod z) の関係がある。
【００４６】
すなわち、重なり合った複数のブロックサイクルによって構成されるブロックサイクルは、実際の置換要素が取る値に関わらず、常に
【数５】
2010035501.tif 000028
が成り立つ。したがって、このとき一定してLPcycle=LBcyclの関係を有する。
【００４７】
この結果、重なり合ったブロックサイクルにおける、非零の巡回シフト要素aijの値をどのように選択しても、任意の置換要素によって構成された実際の検査行列中に、必然的に長さ14のループが含まれる。したがって、重なり合ったブロックサイクルは、実現可能な実際のループ長の上限を決定する。すなわち、非零要素aijの値をどのように選択しても、実際の検査行列において、実現可能な最大ループ長は14である。そのため、実際の検査行列中のループの分布を最適化することは、長さ4のブロックサイクルと長さ6のブロックサイクルとに対応するループの長さをできるかぎり14に近づけるよう、非零要素aijの値をいかに選択するかに帰結する。
【００４８】
IEEE 802.16e規格の規定によれば、置換要素ｚの最大公約数は4と定義されている。当該最大公約数は2×2に分解することができる。上記ステップ3）の記載によれば、
【数６】
2010035501.tif 000029
に置換要素zの最大公約数4の素因数2が含まれないようにするためには、長さ4のブロックサイクルにおける非零の巡回シフト値の要素が、次式（5）と（6）を成立させる必要がある。
(a00−a02＋a22−a20)≠2k, ここで、k∈N      …（5）
(a12−a22＋a21−a11)≠2k, ここで、k∈N      …（6）
つまり、式（5）および（6）の結果は奇数となる。したがって、式（2）即ち
【数７】
2010035501.tif 000030
を、すべてのｚに対して成立させるためには、rは必ず因数4を含み、r≧4でなければならない。よって、実際の検査行列における、長さ4のブロックサイクルに対応するループの長さはLPcycle≧r×LBcycl=16であることがわかる。これは前記の最適化の条件を明らかに満たしている。
【００４９】
長さ6のブロックサイクルについては、当該ブロックサイクルに含まれる非零要素が、次式（7）を成立させなければならない。
(a00−a02＋a12−a11＋a21−a20)= formula(2) + formula(3)   …（7）
【００５０】
上記の内容から、選択された非零要素値は、式（5）および（6）の結果を奇数としているので、式（7）の結果は必然的に偶数となり、素因数2を含む。したがって、実際の検査行列において、すべての置換要素が長さ6のショートループを含まないようにするためには、式（2）を成立させるrの値が必ず1より大きくなるよう、式（7）の結果が4の倍数にならないようにする必要がある。このため、上記6個の非零要素の選択は、さらに、長さ4の重なり合った2つのブロックサイクルに共通の要素であるa22の奇偶に基づいて決定することができる。すなわち、
1．a22が奇数であれば、その他の非零要素の値は、(a00−a02−a20)と(a12−a11＋a21)とをいずれも偶数とし、なおかつ4に対する余りが互いに異なるような値にしなければならない。
2．a22が偶数であれば、その他の非零要素の値は、(a00−a02−a20)と(a12−a11＋a21)とをいずれも奇数とし、なおかつ4に対する余りを等しくする値にしなければならない。
【００５１】
以下、a22が偶数である場合を例にとり、その他の要素の決定方法を詳細に説明する。2つのブロックサイクルに共通の要素a22＝6とすると、この場合、図9に示すように、長さ4の2つのブロックサイクルについて、a00=12, a02=2, a20=7, a12 =11, a11=9, a21=5とすると、a00−a02＋a22−a20（ブロックサイクルa02→a00→a20→a22）とa12−a22＋a21−a11（ブロックサイクルa12→a11→a21→a22）がいずれも奇数、すなわちa00−a02＋a22−a20≡1 (mod 2)かつa12−a22＋a21−a11 ≡1 (mod 2)となる。また、長さ6のブロックサイクルにおける非零要素は、次のような性質となる。
1) （a00−a02−a20）と（a12−a11＋a21）とを4で除算した余りが同一、すなわちa00−a02−a20 ≡1 (mod 4) かつa12−a11＋a21≡ 3 (mod 4)
2)  a00−a02＋a12−a11＋a21−a20 ≡2 (mod 4)、すなわち、上記式の結果は4の倍数ではない
【００５２】
式（7）の結果は、置換要素の最大公約数4で割り切れないため、式（2）を成立させる最小の正の整数rは少なくとも2の倍数、すなわち素因数2を含まなければならないので、r≧2である。よって、実際の検査行列における、長さ6のブロックサイクルに対応するループの長さはLPcycle≧r×LBcycl=12であることがわかる。これは前記の最適化の条件を明らかに満たしている。
【００５３】
また、基本行列において、相互に重なり合ったブロックサイクルが、複数含まれる場合には、その中で、長さのより小さい重なり合ったブロックサイクルが、より高い優先度を
有する。すなわち、重なり合った、短いブロックサイクルにおける非零要素の値を、最初に決定する。
【００５４】
図10は、相互に重なり合ったブロックサイクルを複数含む、基本行列の概念図である。図10に示すように、長さ4のブロックサイクル（a02→a00→a20→a22）と長さ4のブロックサイクル（a12→a11→a21→a22）が重なり合っており、共通の要素はa22である。また、長さ6のブロックサイクル（a04→a06→a36→a35→a45→a44）と長さ4のブロックサイクル（a06→a07→a37→a36）が重なり合っており、共通の要素はa06とa36である。前者に含まれる、重なり合ったブロックサイクルの長さは、後者より小さいため、前者はより高い充当優先度を有する。
【００５５】
図11は、本発明の実施例による送信局のブロック図である。以下の説明において、データの送信側を送信局、データの受信側を受信局とする。図11に示すように、送信局はLDPC符号化部101、制御部109、変調部102、多重部103、送信RF（Radio Frequency）部104、受信RF部106、復調部107、復号部108およびアンテナ105を具備する。
【００５６】
LDPC符号化部101では、検査符号を用いて、マザー符号化率（mother code rate）にてLDPC符号化を行う。制御部109から入力した符号化率に基づいて、抽出された符号化ビット系列を変調部102へ出力する。
【００５７】
変調部102では、LDPC符号化ビット系列を変調してデータシンボルを生成し、多重部103へ出力するとともに、制御部109からの制御情報に基づいて、符号化率、変調方式および再送を制御する。
【００５８】
多重部103では、変調部102から入力したデータシンボル、制御部109から入力した制御情報、およびパイロット信号を多重する。
【００５９】
送信RF部104では、多重部103で多重したベースバンド信号を周波数変換してRF信号とし、アンテナ105から送信する。
【００６０】
受信RF部106では、受信局からの制御信号（CQIおよびACK/NACK情報）をアンテナ105で受信し、それを周波数変換してベースバンド信号とする。
【００６１】
復調部107では、制御信号（CQIおよびACK/NACK情報）を復調し、復号部108へ出力する。
【００６２】
復号部108では、変調された制御信号（CQIおよびACK/NACK情報）を復号し、制御部109へ出力する。
【００６３】
制御部109では、復号部108から入力した各受信局からの制御信号（CQIおよびACK/NACK情報）に基づいて、符号化率と再送を制御する。本発明の実施例によれば、受信局から報告されるCQI（Channel Quality Indicator）として、SINR（Signal Interference Noise Ratio）、平均SIR（Signal Interference Ratio）、MCS（Modulation Coding Scheme）パラメータを用いることができる。
【００６４】
図12は、本発明の実施例による受信装置の構成を示すブロック図である。以下の説明において、データの送信側を送信局、データの受信側を受信局とする。図12に示すように、本発明の実施例の受信装置は、受信RF部202、分離部203、復調部204、LDPC復号部205、制御信号生成部207、回線品質推定部206、符号化部208、変調部209、送信RF部210およびアンテナ201を具備する。
【００６５】
受信RF部202では、アンテナ201を介して送信局から送信された信号を受信し、周波数変換してベースバンド信号とする。受信したデータ信号は分離部203へ出力し、受信したパイロット信号は回線品質推定部206へ出力する。
【００６６】
分離部203では、受信したデータ信号をデータ系列と制御情報（符号化率、データ系列長など）に分離し、データ系列を復調部204へ、制御情報（符号化率、データ系列長など）をLDPC復号部205へ出力する。
【００６７】
復調部204では、分離部203から入力したデータ系列を復調する。LDPC復号部205では、復調後のデータ系列に対し誤り訂正復号（LDPC復号）を行い、受信データを得る。また、受信データのエラーチェックを行い、ACK/NACK判定を行う。判定結果であるACK/NACK信号は、制御信号生成部207へ出力される。
【００６８】
制御信号生成部207では、回線品質推定部206から入力したCQIおよびLDPC復号部205から入力したACK/NACK信号から、フィードバック情報用のフレームを生成し、符号化部208へ出力する。
【００６９】
符号化部208、変調部209では、制御信号生成部207から入力したフィードバック情報を符号化、変調し、送信RF部210へ出力する。
【００７０】
送信RF部210は符号化および変調された信号を周波数変換してRF信号とし、アンテナ201から送信する。
【００７１】
しかしながら、受信装置における送信部（符号化部208、変調部209、送信RF部210から構成される）は、送信局の送信部と同様の構成でもよいし、その他の構成でもよい。
【００７２】
以上、好ましい実施例を用いて本発明を説明したが、本発明の思想及び範囲内で種々の変更、置換及び追加が可能であることは、当業者にとって自明である。従って、本発明の範囲は上述の特定の実施例に限定されるものではなく、添付の「請求の範囲」によって限定されるべきものである。
【００７３】
また、上記実施例の説明に用いた各機能ブロックは、典型的には集積回路であるＬＳＩとして実現される。これらは個別に１チップ化されてもよいし、一部または全てを含むように１チップ化されてもよい。ここでは、ＬＳＩとしたが、集積度の違いにより、ＩＣ、システムＬＳＩ、スーパーＬＳＩ、ウルトラＬＳＩと呼称されることもある。
【００７４】
また、集積回路化の手法はＬＳＩに限るものではなく、専用回路または汎用プロセッサで実現してもよい。ＬＳＩ製造後に、プログラムすることが可能なＦＰＧＡ（Field Programmable Gate Array）や、ＬＳＩ内部の回路セルの接続や設定を再構成可能なリコンフィギュラブル・プロセッサーを利用してもよい。
【００７５】
さらには、半導体技術の進歩または派生する別技術によりＬＳＩに置き換わる集積回路化の技術が登場すれば、当然、その技術を用いて機能ブロックの集積化を行ってもよい。バイオ技術の適用等が可能性としてありえる。
【００７６】
２００８年９月２７日出願の中国出願２００８１０１６８９１３．９に含まれる明細書、図面及び要約書の開示内容は、すべて本願に援用される。
【手続補正２】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
サイクル分布を利用してLDPC符号を構成する方法であって、
LDPC符号の基本行列における、非零の巡回シフト要素値から構成されるブロックサイクルの分布を決定するブロックサイクル決定ステップと、
決定したブロックサイクルの分布に基づいて、各ブロックサイクルに含まれる非零の巡回シフト要素値の優先度を決定する優先度決定ステップと、
LDPC符号の検査行列のあらゆる大きさの置換要素について最大公約数を求め、それを素因数分解する計算ステップと、
を有する方法。
【請求項２】
次式において置換要素の最大公約数の素因数が含まれないように、ブロックサイクルを構成する巡回シフト値を決定する巡回シフト値決定ステップ、をさらに有する、
請求項１に記載の方法。
【数１】
2010035501.tif 000031
【請求項３】
LDPC符号の基本行列において、相互に重なり合ったブロックサイクルが複数含まれるとき、相互に重なり合った、ブロックサイクルの長さが短いブロックサイクルにおける巡回シフト値を先に決定する、
請求項１に記載の方法。
【請求項４】
LDPC符号の基本行列において、異なるブロックサイクルに共通の巡回シフト値が含まれるとき、重なり合ったブロックサイクルがより長いブロックサイクルとなるように共通の巡回シフト値を決定する、
請求項３に記載の方法。
【請求項５】
LDPC符号の基本行列において、相互に重なり合ったブロックサイクルが複数含まれるとき、相互に重なり合った、ブロックサイクルの長さが短いブロックサイクルにおける巡回シフト値を先に決定する、
請求項２に記載の方法。
【請求項６】
LDPC符号の基本行列において、異なるブロックサイクルに共通の巡回シフト値が含まれるとき、重なり合ったブロックサイクルがより長いブロックサイクルとなるように共通の巡回シフト値を決定する、
請求項１に記載の方法。
【請求項７】
請求項１から６のいずれかに記載の方法に基づいてLDPC符号化を行う符号化手段と、
前記LDPC符号化を施されたビット系列を変調して、データシンボルを生成する変調手段と、
前記データシンボルを送信する送信手段と、
を具備する送信装置。
【請求項８】
制御信号を復調する復調手段と、
復調された制御信号を復号する復号手段と、
前記復号手段から入力された各受信側からの制御信号に基づいて、符号化率および／または再送を制御する制御手段と、
前記変調手段からの前記データシンボルと、制御手段からの制御信号と、パイロット信号とを多重する多重手段と、をさらに具備し、
前記符号化手段は、前記制御手段から入力された符号化率で抽出した符号化ビット系列を、前記変調手段へ出力し、
前記送信手段は、前記多重手段において多重されたベースバンド信号周波数変換して、無線信号として送信する、
請求項７に記載の送信装置。
【請求項９】
送信側から送信された信号を受信する受信手段と、
受信した信号をデータ列と制御情報とに分離する分離手段と、
前記分離手段からの前記データ列を復調する復調手段と、
復調されたデータ列を、請求項１から６のいずれかに記載の方法で復号し、受信結果状態に基づいてACK／NACKの判定を行う復号手段と、
を具備する受信装置。
【請求項１０】
前記分離手段からの受信パイロット信号に基づいて品質推定を行う回線品質推定手段と、
前記回線品質推定手段からのCQIと、前記復号手段からの前記受信結果状態に基づくACK／NACK信号とによって、フィードバック情報用のフレームを生成する制御信号生成手段と、をさらに具備する、
請求項９に記載の受信装置。
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】全図
【補正方法】変更
【補正の内容】
【図１】
2010035501.tif 000032
【図２】
2010035501.tif 000033
【図３ａ】
2010035501.tif 000034
【図３ｂ】
2010035501.tif 000035
【図４】
2010035501.tif 000036
【図５】
2010035501.tif 000037
【図６】
2010035501.tif 000038
【図７】
2010035501.tif 000039
【図８】
2010035501.tif 000040
【図９】
2010035501.tif 000041
【図１０】
2010035501.tif 000042
【図１１】
2010035501.tif 000043
【図１２】
2010035501.tif 000044
【国際調査報告】
2010035501.tif 000045
2010035501.tif 000046