低密度パリティ検査符号のパリティ検査行列生成方法
【課題】低密度パリティ検査（ＬＤＰＣ）符号のパリティ検査行列生成方法を提供する。
【解決手段】本発明のＬＤＰＣ符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法は、ＬＤＰＣ符号を設計するためのパラメータを決定し、決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を生成し、第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成し、第２のパリティ検査行列を再整列することにより第３のパリティ検査行列を生成する。
【解決手段】本発明のＬＤＰＣ符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法は、ＬＤＰＣ符号を設計するためのパラメータを決定し、決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を生成し、第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成し、第２のパリティ検査行列を再整列することにより第３のパリティ検査行列を生成する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、低密度パリティ検査（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ：以下、“ＬＤＰＣ”と称する。）符号を使用する通信システムに関し、特に、特定の形態のＬＤＰＣ符号のパリティ検査行列生成方法に関する。
【背景技術】
【０００２】
無線通信システムにおいて、チャネルの様々な雑音、フェージング現象、及びシンボル間干渉（Ｉｎｔｅｒ−Ｓｙｍｂｏｌ Ｉｎｔｅｒｆｅｒｅｎｃｅ：以下、“ＩＳＩ”と称する。）によりリンク性能が著しく低下する。したがって、次世代移動通信、デジタルブロードキャスト、及びモバイルインターネットのような高いデータ処理量及び信頼度が要求される高速デジタル通信システムを実現するためには、雑音、フェージング、及びＩＳＩを克服する技術を開発することが重要である。近年では、歪曲された情報を効率的に復元することにより通信の信頼度を高めるための方法としてエラー訂正符号に関する研究が活発になされている。
【０００３】
１９６０年代にＧａｌｌａｇｅｒにより初めて紹介されたＬＤＰＣ符号は、その当時の技術をはるかに追い抜く実現複雑度により長い間忘れられてきた。しかしながら、１９９３年Ｂｅｒｒｏｕ、Ｇｌａｖｉｅｕｘ、及びＴｈｉｔｉｍａｊｓｈｉｍａにより発見されたターボ符号がＳｈａｎｎｏｎのチャネルリミットに近接する性能を示すため、ターボ符号の性能及び特性に関する多くの分析がなされつつ反復復号及びグラフに基づくチャネル符号化に関する多くの研究が進められてきた。このような研究により、ＬＤＰＣ符号は、１９９０年代後半に再研究され、ＬＤＰＣ符号に対応するタナーグラフ（ファクターグラフの特別ケース）上で積和（ｓｕｍ−ｐｒｏｄｕｃｔ）アルゴリズムに基づく反復復号を適用することにより復号化を実行すると、Ｓｈａｎｎｏｎのチャネルリミットに近接する性能を有することが証明された。
【０００４】
ＬＤＰＣ符号は、通常、グラフ表現技術を用いて示され、グラフ理論、代数学、及び確率論に基づく方法を通じて多くの特性を分析することができる。一般的に、チャネル符号のグラフモデルは、符号の描写に有用であり、符号化されたビットに関する情報をグラフ内の頂点（ｖｅｒｔｅｘ）にマッピングし、各ビット間の関係をグラフ内のエッジにマッピングすることにより、各頂点が各エッジを介して所定のメッセージをやりとりする通信ネットワークと見なすことができ、したがって、自然の復号アルゴリズムを導出することが可能となる。例えば、グラフの一種と見なされることができるトレリス（ｔｒｅｌｌｉｓ）から導出された復号アルゴリズムは、よく知られているビタビ（Ｖｉｔｅｒｂｉ）アルゴリズム、及びＢａｈｌ、Ｃｏｃｋｅ、Ｊｅｌｉｎｅｋ、及びＲａｖｉｖ（ＢＣＪＲ）アルゴリズムを含む。
【０００５】
ＬＤＰＣ符号は、一般的に、パリティ検査行列と定義され、タナーグラフ（Ｔａｎｎｅｒ ｇｒａｐｈ）と称される二部グラフ（ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ）を用いて表現することができる。この二部グラフは、グラフを構成する頂点が相互に異なる２つのタイプに分けられることを意味し、ＬＤＰＣ符号は、変数ノードと検査ノードと呼ばれる頂点を含む二部グラフで表現される。この変数ノードは、この符号化されたビットに一対一にマッピングされる。
【０００６】
図１及び図２を参照して、ＬＤＰＣ符号のグラフ表現方法について説明する。
図１は、４個の行及び８個の列を含むＬＤＰＣ符号のパリティ検査行列Ｈ１の例を示す。
図１を参照すると、列の個数が８であるために、パリティ検査行列Ｈ１は、長さ８の符号語を生成するＬＤＰＣ符号を意味し、この列は、符号化された８ビットにマッピングされる。
【０００７】
図２は、図１のＨ１に対応するタナーグラフを示す図である。
図２を参照すると、ＬＤＰＣ符号のタナーグラフは、８個の変数ノードｘ１（２０２）、ｘ２（２０４）、ｘ３（２０６）、ｘ４（２０８）、ｘ５（２１０）、ｘ６（２１２）、ｘ７（２１４）、及びｘ８（２１６）と４個の検査ノード２１８、２２０、２２２、及び２２４とを含む。ここで、ＬＤＰＣ符号のパリティ検査行列Ｈ１のｉ番目の列及びｊ番目の行は、変数ノードｘｉ及びｊ番目の検査ノードにマッピングされる。また、ＬＤＰＣ符号のパリティ検査行列Ｈ１のｉ番目の列及びｊ番目の行が相互に交差する地点での１の値、すなわち、０でない値は、図２に示すタナーグラフ上で変数ノードｘｉとｊ番目の検査ノード間にエッジが存在することを意味する。
【０００８】
ＬＤＰＣ符号のタナーグラフにおいて、変数ノード及び検査ノードの次数は、各ノードに接続されているエッジの個数を意味し、この次数は、ＬＤＰＣ符号のパリティ検査行列で関連するノードに対応する列又は行で０でないエントリーの個数と同一である。例えば、図２において、変数ノードｘ１（２０２）、ｘ２（２０４）、ｘ３（２０６）、ｘ４（２０８）、ｘ５（２１０）、ｘ６（２１２）、ｘ７（２１４）、及びｘ８（２１６）の次数は、それぞれ４、３、３、３、２、２、２、及び２であり、検査ノード２１８、２２０、２２２、及び２２４の次数は、それぞれ６、５、５、及び５である。
【０００９】
また、図２の変数ノードに対応する図１のパリティ検査行列Ｈ１のそれぞれの列で０でないエントリーの個数は、上記した次数４、３、３、３、２、２、２、及び２と一致し、図２の検査ノードに対応する図１のパリティ検査行列Ｈ１のそれぞれの行で０でないエントリーの個数は、上記した次数６、５、５、及び５と一致する。
【００１０】
ＬＤＰＣ符号のノードに対する次数分布（ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ）を示すために、次数がｉである変数ノードの個数と変数ノードの総数との比率をｆｉとして定義し、次数がｊである検査ノードの個数と検査ノードの総数との比率をｇｊとして定義する。
例えば、図１及び図２に対応するＬＤＰＣ符号の場合には、ｆ２＝４／８、ｆ３＝３／８、ｆ４＝１／８、ｉ≠２、３、４に対してｆｉ＝０であり、ｇ５＝３／４、ｇ６＝１／４である、ｊ≠５、６に対してｇｊ＝０である。
【００１１】
ＬＤＰＣ符号の長さをＮ、すなわち、列の個数をＮとして定義し、行の個数をＮ／２として定義する時、上述した次数分布を有する全パリティ検査行列で０でないエントリーの密度は、下記の数式（１）のように計算される。
【数１】
【００１２】
上記数式（１）において、Ｎが増加するに従って、パリティ検査行列内の‘１’の密度は減少する。一般的に、ＬＤＰＣ符号について、符号長さＮが０でないエントリーの密度に反比例するので、Ｎが大きいＬＤＰＣ符号は、非常に低い密度を有する。ＬＤＰＣ符号の名称での用語“低密度”は、上述した関係に由来する。
【００１３】
次に、図３を参照して本発明で適用される構造的なＬＤＰＣ符号のパリティ検査行列の特性について説明する。
図３は、ヨーロッパデジタルブロードキャスト標準の１つである第２世代衛星デジタルビデオブロードキャスト（ＤＶＢ−Ｓ２）で標準技術として採択されたＬＤＰＣ符号を概略的に示す。
図３において、Ｎ１は、ＬＤＰＣ符号語の長さを示し、Ｋ１は、情報語の長さを提供し、（Ｎ１−Ｋ１）は、パリティ長さを提供する。また、整数Ｍ１及びｑは、ｑ＝（Ｎ１−Ｋ１／Ｍ１）を満足するように決定される。好ましくは、Ｋ１／Ｍ１は、整数でなければならない。
【００１４】
図３を参照すると、パリティ検査行列でパリティ部分、すなわち、Ｋ１番目の列から（Ｎ１−１）番目の列までの構成は、デュアル対角（ｄｕａｌ ｄｉａｇｏｎａｌ）形態を有する。したがって、パリティ部分に対応する列の次数分布について、次数‘１’を有する最後の列を除いて、すべての列は、次数‘２’を有する。
【００１５】
パリティ検査行列において、情報語部分、すなわち、０番目の列から（Ｋ１−１）番目の列までの構成は、次の規則を用いてなされる。
〔規則１〕 パリティ検査行列で情報語に対応するＫ１個の列をＭ１個の列で構成された複数のグループにグループ化することにより、トータルＫ１／Ｍ１個の列グループを生成する。各列グループに属している列を形成する方法は、下記の規則２に従う。
【００１６】
〔規則２〕 最初に、ｉ（ここで、ｉ＝１，．．．，Ｋ１／Ｍ１）番目の列グループ内の各０番目の列での‘１’の位置を決定する。各ｉ番目の列グループ内の０番目の列の次数をＤｉで示す際に、‘１’を有する行の位置を
【数２】
と仮定すると、‘１’を有する行の位置
【数３】
は、ｉ番目の列グループ内のｊ（ここで、ｊ＝１，２，．．．，Ｍ１−１）番目の列で下記の数式（２）のように定義される。
【数４】
【００１７】
上述した規則に従うと、ｉ番目（ここで、ｉ＝１，．．．，Ｋ１／Ｍ１）の列グループに属している列の次数がすべてＤｉに等しいことを分かる。
上述した規則に従ってパリティ検査行列に関する情報を格納しているＤＶＢ−Ｓ２ ＬＤＰＣ符号の構成を容易に理解するために、次のような具体的な例について説明する。
【００１８】
具体的な例として、Ｎ１＝３０、Ｋ１＝１５、Ｍ１＝５、及びｑ＝３の場合に、３個の列グループ内の０番目の列に対する‘１’を有する行の位置に関する情報の３つのシーケンスは、次のように表現することができる。ここで、これらのシーケンスは、説明の便宜上、“加重値−１位置シーケンス（ｗｅｉｇｈｔ−１ ｐｏｓｉｔｉｏｎ ｓｅｑｕｅｎｃｅｓ）”と称する。
【数５】
【００１９】
各列グループ内の０番目の列の“加重値−１位置シーケンス”について、説明の便宜上、対応する位置シーケンスだけが列グループ別に次のように表現されることができる。例えば、
０ １ ２
０ １１ １３
０ １０ １４
言い換えれば、このｉ番目のラインでのｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループに対する行の位置に関する情報を順次に示す。
【００２０】
上述した具体的な例に対応する情報と規則１及び規則２とを用いてパリティ検査行列を構成することにより、図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号と同一の概念を有するＬＤＰＣ符号を生成することができる。
規則１及び規則２に従って設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号が構造形状を用いて効率的に符号化することができることが知られている。パリティ検査行列に基づくＤＶＢ−Ｓ２を用いてＬＤＰＣ符号化を実行する工程での各ステップについては、次のような例を挙げて説明する。
【００２１】
以下の説明において、具体的な例として、Ｎ１＝１６２００、Ｋ１＝１０８００、Ｍ１＝３６０、及びｑ＝１５を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する符号化工程について説明する。説明の便宜のために、長さＫ１を有する情報語ビットは、
【数６】
として示され、長さ（Ｎ１−Ｋ１）を有するパリティビットは、
【数７】
として表現される。
【００２２】
〔ステップ１〕ＬＤＰＣ符号化器は、パリティビットを次のように初期化する。
【数８】
【００２３】
〔ステップ２〕ＬＤＰＣ符号化器は、パリティ検査行列を示す格納されているシーケンスの０番目の“加重値−１位置シーケンス”から列グループ内で‘１’が位置した行に関する情報を読み出す。
０ ２０８４ １６１３ １５４８ １２８６ １４６０ ３１９６ ４２９７ ２４８１ ３３６９ ３４５１ ４６２０ ２６２２
【数９】
【００２４】
ＬＤＰＣ符号化器は、上記読み出された情報及び１番目の情報語ビットｉ０を用いて下記の数式（３）に従って特定のパリティビットｐｘをアップデートする。ここで、ｘは、
【数１０】
の値を示す。
【数１１】
上述した数式（３）において、
【数１２】
は、
【数１３】
として表現することもでき、
は、２進加算を意味する。
【００２５】
〔ステップ３〕次に、ＬＤＰＣ符号化器は、ｉ０の後の次の３５９個の情報語ビットｉｍ（ここで、ｍ＝１，２，．．．，３５９）に対して下記の数式（４）の値を求める。
【数１４】
上述した数式（４）において、ｘは、
【数１５】
の値を示す。上述した数式（４）は、上述した数式（２）と同一の概念を有することに留意しなければならない。
【００２６】
次いで、ＬＤＰＣ符号化器は、上述した数式（４）で求められた値を用いて数式（３）と類似した動作を実行する。すなわち、ＬＤＰＣ符号化器は、ｉｍに対して
【数１６】
をアップデートする。例えば、ｍ＝１、すなわち、ｉ１に対して、ＬＤＰＣ符号化器は、下記の数式（５）で定義されるように、パリティビット
【数１７】
をアップデートする。
【数１８】
上述した数式（５）において、ｑ＝１５であることに留意しなければならない。ＬＤＰＣ符号化器は、ｍ＝１，２，．．．，３５９に対して上記のような工程を同様に実行する。
【００２７】
〔ステップ４〕ステップ２と同様に、ＬＤＰＣ符号化器は、３６１番目の情報語ビットｉ３６０に対して１番目の“加重値−１位置シーケンス”
【数１９】
の情報を読み出し、特定のｐｘをアップデートする。ここで、ｘは、
【数２０】
である。
ＬＤＰＣ符号化器は、ｉ３６０の後の次の３５９個の情報語ビットｉ３６１，ｉ３６２，．．．，ｉ７１９に数式（４）を同様に適用することにより、
【数２１】
をアップデートする。
【００２８】
〔ステップ５〕ＬＤＰＣ符号化器は、それぞれの３６０個の情報語ビットを有するすべてのグループに対してステップ２、３、及び４を反復する。
【００２９】
〔ステップ６〕ＬＤＰＣ符号化器は、最終的に数式（６）を用いてパリティビットを決定する。
【数２２】
【００３０】
上述した数式（６）のパリティビットｐｉは、ＬＤＰＣ符号化が完了したパリティビットである。
上述したように、ＤＶＢ−Ｓ２において、ＬＤＰＣ符号化器は、ステップ１からステップ６までの工程を介してＬＤＰＣ符号化を行う。
【００３１】
ＬＤＰＣ符号の性能がタナーグラフのサイクル特性に密接に関連していることがよく知られている。特に、タナーグラフにおいて、短い長さのサイクルの個数が多い場合に性能劣化が発生し得ることが実験によりよく知られている。したがって、高性能を有するＬＤＰＣ符号を設計するためには、タナーグラフ上のサイクル特性を考慮すべきである。
【００３２】
しかしながら、良好なサイクル特性を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法は提案されていない。実際に、ＤＶＢ−Ｓ２ ＬＤＰＣ符号に対して、タナーグラフのサイクル特性の最適化が考慮されていないため、エラーフロア（ｅｒｒｏｒ ｆｌｏｏｒ）現象は、高い信号対雑音比（ＳＮＲ）で観察される。これらの理由で、ＤＶＢ−Ｓ２構造を有するＬＤＰＣ符号を設計する際にサイクル特性を効率的に改善させることができる方法が要求されているという問題がある。
【発明の概要】
【発明が解決しようとする課題】
【００３３】
したがって、本発明は、上述した従来技術の問題点を解決するために提案されたものであり、その目的は、ＬＤＰＣ符号を使用する通信システムにおけるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために巡回置換行列に基づいて設計された準巡回ＬＤＰＣ符号のパリティ検査行列生成方法を提供することにある。
【００３４】
また、本発明は、ＬＤＰＣ符号を使用する通信システムにおけるタナーグラフ特性がよいＤＶＢ−Ｓ２ ＬＤＰＣ符号と同一のＬＤＰＣ符号のパリティ検査行列生成方法を提供することにある。
【課題を解決するための手段】
【００３５】
上記のような目的を達成するために、本発明の一態様によれば、低密度パリティ検査（ＬＤＰＣ）符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法が提供される。前記方法は、前記ＬＤＰＣ符号を設計するためのパラメータを決定するステップと、前記決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を形成するステップと、前記第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成するステップと、前記第２のパリティ検査行列を再整列させることにより第３のパリティ検査行列を生成するステップと、を有する。
【発明の効果】
【００３６】
本発明は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するにあたりタナーグラフの特性を最適化することによりＬＤＰＣ符号を使用する通信システムの性能を最適化することができる。
【図面の簡単な説明】
【００３７】
【図１】長さが８であるＬＤＰＣ符号のパリティ検査行列の一例を示す図である。
【図２】長さが８であるＬＤＰＣ符号のパリティ検査行列の一例のタナーグラフを示す図である。
【図３】ＤＶＢ−Ｓ２ ＬＤＰＣ符号の概略的な構成を示す図である。
【図４】ＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列の一例を示す図である。
【図５】本発明の実施形態による図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列で所定の規則に従って各列及び行を再配列することにより生成されるパリティ検査行列を示す図である。
【図６】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図７】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を変換することにより得られた結果を示す図である。
【図８】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する工程を示すフローチャートである。
【図９】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号のコンピュータシミュレーション結果を示す図である。
【図１０】本発明の実施形態による再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送受信器の構成を示すブロック図である。
【図１１】本発明の実施形態によるＬＤＰＣ符号を使用する送信装置の構成を示すブロック図である。
【図１２】本発明の実施形態によるＬＤＰＣ符号を使用する受信装置の構成を示すブロック図である。
【図１３】本発明の実施形態によるＬＤＰＣ符号を使用する受信装置での受信動作を示すフローチャートである。
【発明を実施するための形態】
【００３８】
以下、本発明の好適な一実施形態を、添付図面を参照しつつ詳細に説明する。
下記の説明において、明瞭性と簡潔性の観点から、本発明に関連した公知の機能や構成に関する具体的な説明が本発明の要旨を不明瞭にすると判断される場合には、その詳細な説明を省略する。
【００３９】
本発明は、タナーグラフの特性が優秀なＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法を提供する。また、本発明は、設計されたＬＤＰＣ符号のパリティ検査行列を用いてＬＤＰＣ符号語を生成する方法及びその装置を提供する。
【００４０】
図４に示すＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号の構造特性について説明する。
図４に示すパリティ検査行列の場合に、Ｎ１＝３０、Ｋ１＝１５、Ｍ１＝５、及びｑ＝３であり、３個の列グループ内の０番目の列に対する行の“加重値−１位置シーケンス”は、次のようである。
０ １ ２
０ １１ １３
０ １０ １４
ここで、このｉ番目のラインでのｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループで１を有する行の位置に関する情報を順次に示す。
【００４１】
まず、図４のパリティ検査行列は、次のような規則に従って再構成される。図４は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を示す図である。
〔規則３〕 ０番目の行〜（Ｎ１−Ｋ１−１）番目の行は、（ｑ・ｉ＋ｊ）番目の行が（Ｍ１・ｊ＋ｉ）番目の行に位置するように再整列させる。ここで、０≦ｉ＜Ｍ１及び０≦ｊ＜ｑである。
〔規則４〕 ０番目の列〜（Ｋ１−１）番目の列は、そのままおき、Ｋ１番目の列〜（Ｎ１−１）番目の列は、（Ｋ１＋ｑ・ｉ＋ｊ）番目の列が（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列に位置するように再整列させる。
【００４２】
図５に示す形態を有するパリティ検査行列は、規則３及び規則４に従って図４のパリティ検査行列を再構成することにより得られる。
図５は、本発明の実施形態による図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列で所定の規則に従って各列及び行を再配列することにより生成されるパリティ検査行列を示す図である。
【００４３】
図５において、‘１’が０番目の行の（Ｎ１−１）番目の列にあると仮定すると、図５のパリティ検査行列がＭ１×Ｍ１、すなわち、５×５のサイズを有する巡回置換行列で構成された準巡回ＬＤＰＣ符号の一種であることをわかる。
ここで、‘巡回置換行列’は、恒等行列（ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ）の各行を右方に１つずつ巡回移動させた置換行列の１つの種類を意味する。また、‘準巡回ＬＤＰＣ符号’は、パリティ検査行列を同一のサイズを有するいくつかのブロックに区分し、巡回置換行列又は０行列を各ブロックにマッピングすることにより生成されたＬＤＰＣ符号の一種を意味する。
【００４４】
要約すると、規則３及び規則４を通じてＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を再構成することにより準巡回ＬＤＰＣ符号と近似したパリティ検査行列を得ることができることをわかる。また、ＤＶＢ−Ｓ２ ＬＤＰＣ符号が規則３及び規則４の逆工程を通じて準巡回ＬＤＰＣ符号から生成されることができることが予想される。
【００４５】
ＤＶＢ−Ｓ２ ＬＤＰＣ符号についての研究結果は、ほとんど知られていないが、準巡回ＬＤＰＣ符号の場合には非常に様々な設計方法が知られている。特に、準巡回ＬＤＰＣ符号の設計方法は、タナーグラフ上のサイクル特性を最適化する周知の方法を含む。
【００４６】
本発明の実施形態は、よく知られている準巡回ＬＤＰＣ符号のタナーグラフ上のサイクル特性を改善する方法を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法を提供する。
しかしながら、準巡回ＬＤＰＣ符号のサイクル特性を改善する方法が主な内容ではないため、説明の便宜上、具体的な内容を省略する。
【００４７】
以下では、準巡回ＬＤＰＣ符号を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するための方法について説明する。ＤＶＢ−Ｓ２ ＬＤＰＣ符号は、符号語長さＮ１、情報語長さＫ１、パリティ長さ（Ｎ１−Ｋ１）、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１を有する。
【００４８】
準巡回ＬＤＰＣ符号のパリティ検査行列を図６に示す。
図６は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を示す図である。
図６に示すパリティ検査行列は、（Ｎ１−Ｋ１）個の行及びＮ１個の列を有し、Ｍ１×Ｍ１個の部分ブロックに分けられる。説明の便宜上、ｔ＝Ｋ１／Ｍ１である場合に、図６のパリティ検査行列での情報語部分及びパリティ部分は、それぞれｔ個の列ブロック及びｑ個の列ブロックで構成され、合計ｑ個の行ブロックを有する。ここで、Ｎ１／Ｍ１＝ｔ＋ｑである。
【００４９】
図６のパリティ検査行列を構成する各部分ブロックは、巡回置換行列又はゼロ行列に対応する。ここで、巡回置換行列は、Ｍ１×Ｍ１サイズを有し、次のように定義される巡回置換行列Ｐに基づいて生成される。
【数２３】
【００５０】
図６において、ａｉｊは０〜Ｍ１−１の整数又は“∞”の値を有し、Ｐ０は恒等行列Ｉとして定義され、Ｐ∞は、Ｍ１×Ｍ１ゼロ行列を意味する。また、パリティ部分の数字‘０’は、Ｍ１×Ｍ１ゼロ行列を意味する。
【００５１】
図６のパリティ検査行列のもっとも大きい特徴は、パリティに対応する列ブロックが図に示すように恒等行列Ｉと、巡回置換行列
【数２４】
と、を有することにある。
言い換えれば、パリティに対応する列ブロックは、図６に示す構成に固定される。巡回置換行列
【数２５】
は、次のように定義される。
【数２６】
【００５２】
図６に示す準巡回ＬＤＰＣ符号は、パリティ部分に対応する列ブロックの構成が固定されるので、準巡回ＬＤＰＣ符号のサイクルを最適化する工程で変わらない部分である。
言い換えれば、このパリティ部分に対応する列ブロックが図６のパリティ検査行列で固定されるので、このパリティに対応する変数ノード間の接続状態は、タナーグラフ上で決定され、これにより、このタナーグラフのサイクルを最適化するために情報語部分に対応する変数ノード間の接続状態を最適化するだけでよい。
【００５３】
上述したように、準巡回ＬＤＰＣ符号のタナーグラフ上のサイクル特性を最適化する非常に様々な方法が知られている。本発明では、サイクル特性が最適化されたタナーグラフを有する準巡回ＬＤＰＣ符号の設計方法が主な内容ではないため、具体的な内容を省略する。
【００５４】
準巡回ＬＤＰＣ符号の設計方法を通じて図６の準巡回パリティ検査行列でパリティ部分の構成が固定された状態で優秀な性能を有することができるように次数分布が決定されると仮定する。
対応する次数分布に従って情報語部分に対応する列ブロックで巡回置換行列及びゼロ行列の位置が定められ、タナーグラフのサイクル特性が最適化される。
【００５５】
例えば、図７に示す形態は、図６のパリティ検査行列で１番目の行ブロックでの最後の（Ｎ１／Ｍ１）番目又は（ｔ＋ｑ）番目の列ブロックに対応する巡回置換行列
【数２７】
で１番目の行での最後の列の‘１’を除去することにより行うことができる。
図７は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を変換することにより得られた結果を示す図である。
図７において、巡回置換行列
【数２８】
が次のような行列Ｑに変更されることに留意すべきである。
【数２９】
【００５６】
次の規則５及び規則６は、規則３及び規則４の逆工程を適用することにより定義される。
〔規則５〕 ０番目の列〜（Ｋ１−１）番目の列は、そのままおき、Ｋ１番目の列〜（Ｎ１−１）番目の列は、（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列が（Ｋ１＋ｑ・ｉ＋ｊ）番目の列に位置するように再整列させる。ここで、０≦ｉ＜Ｍ１及び０≦ｊ＜ｑである。
〔規則６〕 ０番目の行〜（Ｎ１−Ｋ１−１）番目の行は、（Ｍ１・ｊ＋ｉ）番目の行が（ｑ・ｉ＋ｊ）番目の行に位置するように再整列される。
【００５７】
規則５及び規則６を適用することにより上述した工程を通じて図６の準巡回ＬＤＰＣ符号から生成されたＬＤＰＣ符号のパリティ検査行列は、例えば、図３に示したＤＶＢ−Ｓ２ ＬＤＰＣ符号の形態を有するパリティ検査行列となる。
符号語長さ、情報語長さ、及びパリティ長さが、それぞれＮ１、Ｋ１、及び（Ｎ１−Ｋ１）であり、ｑ＝（Ｎ１−Ｋ１）／Ｍ１であるＤＶＢ−Ｓ２パリティ検査行列を設計するための上述した方法は、次のような工程に要約することができる。
【００５８】
〔ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程〕
図８は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する工程を示すフローチャートである。
図８を参照すると、ステップ８０１で、所望するＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要なパラメータを決定する。本発明では、良好な次数分布だけではなく符号語長さ及び情報語長さのようなパラメータがＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するためにあらかじめ定められていると仮定する。
【００５９】
次に、ステップ８０３で、図６に示すように、Ｍ１×Ｍ１サイズの巡回置換行列及びゼロ行列で構成された準巡回ＬＤＰＣ符号のパリティ検査行列は、ステップ８０１で決定されたパラメータに従って構成される。図６において、パリティ部分に対応する列ブロックは、常に特定の形態に固定されている。
【００６０】
次に、ステップ８０５で、準巡回ＬＤＰＣ符号のタナーグラフのサイクル特性を改善するアルゴリズムを適用することにより図６の情報語部分に対応する列ブロックの巡回置換行列を決定する。ここで、サイクル特性を改善するためには既知のアルゴリズムを使用してもよい。
次に、ステップ８０７で、図７に示したパリティ検査行列は、例えば、ステップ８０５で確定された図６のパリティ検査行列で１番目の行での最後の列の‘１’を除去することにより得られる。
【００６１】
次に、ステップ８０９で、図７のパリティ検査行列での列及び行は、規則５及び規則６を図７のパリティ検査行列に適用することにより再整列される。最終的に得られたパリティ検査行列は、例えば、図３に示したＤＶＢ−Ｓ２ ＬＤＰＣ符号であることができる。
符号語は、上記のようなステップを通じて設計されたＬＤＰＣ符号に上述したＤＶＢ−Ｓ２ ＬＤＰＣ符号化工程を適用することにより生成されることができる。
【００６２】
ＤＶＢ−Ｓ２ ＬＤＰＣ符号の性能を分析するために、次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計した。例えば、
Ｎ１＝６４８０００、Ｋ１＝３８８８０、Ｍ１＝３６０、ｑ＝７２
【００６３】
このパラメータを有する符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、以下の表１及び表２に示すパリティ検査行列は、例えば、ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程を適用することにより合計Ｎ１／Ｍ１＝１８０個の列ブロック及びｑ＝（Ｎ１−Ｋ１）／Ｍ１＝７２個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。ｉ番目の列のｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループで１を有する行の位置に関する情報を順次に示す。
【表１】
【表２】
【００６４】
また、次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計した。例えば、
Ｎ１＝１６２００、Ｋ１＝９７２０、Ｍ１＝３６０、ｑ＝１８
このパラメータを有する符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、表３〜表６に示すパリティ検査行列は、例えば、ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程に適用することにより合計Ｎ１／Ｍ１＝４５個の列ブロック及びｑ＝（Ｎ１−Ｋ１）／Ｍ１＝１８個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。ｉ番目の列のｉ番目の“加重値−１位置シーケンス”がｉ番目の列グループで１を有する行の位置に関する情報を順次に示すことに留意する。
【００６５】
【表３】
【表４】
【表５】
【表６】
【００６６】
新たに設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号と既存のＤＶＢ−Ｓ２ ＬＤＰＣ符号間の性能比較を図９に示す。
図９は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号のコンピュータシミュレーション結果を示す図である。
【００６７】
加法性白色ガウス雑音（Ａｄｄｉｔｉｖｅ Ｗｈｉｔｅ Ｇａｕｓｓｉａｎ Ｎｏｉｓｅ：ＡＷＧＮ）チャネルが二位相偏移（ＢＰＳＫ）変調方式を使用する場合に、約０．１５ｄＢの性能改善がＢＥＲ＝１０−４でなされることをわかる。
符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号の性能改善は、表１〜表６に示すように、このパリティ検査行列に関する情報だけを変更することによりなすことができる。
【００６８】
図８を参照して説明したＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程は、符号化率が３／５である場合だけでなく様々な符号化率に対しても使用されることができる。次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号は、他の符号化率を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計に対する実施形態として設計された。
Ｎ１＝６４８００、Ｋ１＝４３２００、Ｍ１＝３６０、ｑ＝６０
【００６９】
このパラメータを有する符号化率が２／３であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、表７〜表１０に示すパリティ検査行列は、例えば、図８のＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程を適用することにより合計Ｎ１／Ｍ１＝１８０個の列ブロック及びｑ＝６０個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。
【００７０】
【表７】
【表８】
【表９】
【表１０】
【００７１】
図１０は、本発明の実施形態による再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送受信器の構成を示すブロック図である。
【００７２】
図１０を参照すると、メッセージｕは、受信器１０３０に送信される前に送信器１０１０内のＬＤＰＣ符号化器１０１１に入力される。ＬＤＰＣ符号化器１０１１は、入力されたメッセージｕを符号化し、符号化された信号ｃを変調器１０１３に送信する。変調器１０１３は、この符号化された信号を変調し、この変調された信号ｓを無線チャネル１０２０を通じて受信器１０３０に送信する。受信器１０３０内の復調器１０３１は、送信器１０１０により送信された信号ｒを復調し、この復調された信号ｘをＬＤＰＣ復号化器１０３３に出力する。その後に、ＬＤＰＣ復号化器１０３３は、メッセージの推定値
【数３０】
を無線チャネル１０２０を介して受信されたデータから計算する。
【００７３】
この再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送信装置の具体的な構成を図１１に示す。
図１１は、本発明の実施形態による再設計されたＬＤＰＣ符号を使用する送信装置の構成を示すブロック図である。
送信装置は、制御部１１３０、ＬＤＰＣ符号パリティ検査行列抽出部１１１０、及びＬＤＰＣ符号化器１１５０を含む。
【００７４】
ＬＤＰＣ符号パリティ検査行列抽出部１１１０は、システムの要求事項に従ってＬＤＰＣ符号パリティ検査行列を抽出する。ＬＤＰＣ符号パリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、送信装置から与えられることもでき、又は送信装置で生成することもできる。
【００７５】
制御部１１３０は、システムの要求事項に合うように符号化率、符号語の長さ、又は情報語の長さに従って必要なパリティ検査行列を決定するように制御する。
ＬＤＰＣ符号化器１１５０は、制御部１１３０及びＬＤＰＣ符号パリティ検査行列抽出部１１１０により読み出されたＬＤＰＣ符号パリティ検査行列情報に基づいて符号化を実行する。
【００７６】
図１２は、本発明の実施形態による受信装置の構成を示すブロック図である。
図１２は、この再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムから送信された信号を受信し、この受信された信号からユーザが所望するデータを復元する受信装置を示す図である。
【００７７】
受信装置は、制御部１２５０、パリティ検査行列決定部１２３０、ＬＤＰＣ符号パリティ検査行列抽出部１２７０、復調器１２１０、及びＬＤＰＣ復号化器１２９０を含む。
復調器１２１０は、受信されたＬＤＰＣ符号を復調し、該復調された信号をパリティ検査行列決定部１２３０及びＬＤＰＣ復号化器１２９０に送信する。
【００７８】
パリティ検査行列決定部１２３０は、制御部１２５０の制御の下で、この復調された信号に基づいてシステムで使用されたＬＤＰＣ符号のパリティ検査行列を判定する。
制御部１２５０は、パリティ検査行列決定部１２３０からの判定結果をＬＤＰＣ符号パリティ検査行列抽出部１２７０及びＬＤＰＣ復号化器１２９０に送信する。
【００７９】
ＬＤＰＣ符号パリティ検査行列抽出部１２７０は、制御部１２５０の制御の下でシステムより要求されるＬＤＰＣ符号のパリティ検査行列を抽出し、該パリティ検査行列をＬＤＰＣ復号化器１２９０に送信する。上述したように、ＬＤＰＣ符号のパリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、受信装置から与えられることもでき、受信装置で生成することもできる。
【００８０】
ＬＤＰＣ復号化器１２９０は、制御部１２５０の制御の下で、復調器１２１０から送信された受信信号及びＬＤＰＣ符号パリティ検査行列抽出部１２７０から送信されたＬＤＰＣ符号のパリティ検査行列に関する情報に基づいて復号化を実行する。
【００８１】
図１２での受信装置の動作フローチャートを図１３に示す。
ステップ１３０１で、復調器１２１０は、再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムから送信された信号を受信し、該受信された信号を復調する。この後に、ステップ１３０３で、パリティ検査行列決定部１２３０は、この復調された信号に基づいてシステムで使用されたＬＤＰＣ符号のパリティ検査行列を決定する。
【００８２】
パリティ検査行列決定部１２３０により決定された結果は、ステップ１３０５で、ＬＤＰＣ符号パリティ検査行列抽出部１２７０に伝達される。ＬＤＰＣ符号パリティ検査行列抽出部１２７０は、ステップ１３０７で、システムにより要求されるＬＤＰＣ符号のパリティ検査行列を抽出し、これをＬＤＰＣ復号化器１２９０に伝達する。
【００８３】
上述したように、ＬＤＰＣ符号のパリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、送信装置内から与えられることもでき、又は送信装置で生成することもできる。
【００８４】
この後、ＬＤＰＣ復号化器１２９０は、ステップ１３０９で、ＬＤＰＣ符号パリティ検査行列抽出部１２７０から伝達されたＬＤＰＣ符号のパリティ検査行列に関する情報に基づいて復号化を実行する。
【００８５】
以上、本発明を具体的な実施形態を参照して詳細に説明してきたが、本発明の範囲及び趣旨を逸脱することなく様々な変更が可能であるということは、当業者には明らかであり、本発明の範囲は、上述の実施形態に限定されるべきではなく、特許請求の範囲の記載及びこれと均等なものの範囲内で定められるべきである。
【符号の説明】
【００８６】
１０１０ 送信器
１０１１ ＬＤＰＣ符号化器
１０１３ 変調器
１０２０ 無線チャネル
１０３０ 受信器
１０３１ 復調器
１０３３ ＬＤＰＣ復号化器
１１１０ ＬＤＰＣ符号パリティ検査行列抽出部
１１３０ 制御部
１１５０ ＬＤＰＣ符号化器
１２１０ 復調器
１２３０ パリティ検査行列決定部
１２５０ 制御部
１２７０ ＬＤＰＣ符号パリティ検査行列抽出部
１２９０ ＬＤＰＣ復号化器
【技術分野】
【０００１】
本発明は、低密度パリティ検査（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ：以下、“ＬＤＰＣ”と称する。）符号を使用する通信システムに関し、特に、特定の形態のＬＤＰＣ符号のパリティ検査行列生成方法に関する。
【背景技術】
【０００２】
無線通信システムにおいて、チャネルの様々な雑音、フェージング現象、及びシンボル間干渉（Ｉｎｔｅｒ−Ｓｙｍｂｏｌ Ｉｎｔｅｒｆｅｒｅｎｃｅ：以下、“ＩＳＩ”と称する。）によりリンク性能が著しく低下する。したがって、次世代移動通信、デジタルブロードキャスト、及びモバイルインターネットのような高いデータ処理量及び信頼度が要求される高速デジタル通信システムを実現するためには、雑音、フェージング、及びＩＳＩを克服する技術を開発することが重要である。近年では、歪曲された情報を効率的に復元することにより通信の信頼度を高めるための方法としてエラー訂正符号に関する研究が活発になされている。
【０００３】
１９６０年代にＧａｌｌａｇｅｒにより初めて紹介されたＬＤＰＣ符号は、その当時の技術をはるかに追い抜く実現複雑度により長い間忘れられてきた。しかしながら、１９９３年Ｂｅｒｒｏｕ、Ｇｌａｖｉｅｕｘ、及びＴｈｉｔｉｍａｊｓｈｉｍａにより発見されたターボ符号がＳｈａｎｎｏｎのチャネルリミットに近接する性能を示すため、ターボ符号の性能及び特性に関する多くの分析がなされつつ反復復号及びグラフに基づくチャネル符号化に関する多くの研究が進められてきた。このような研究により、ＬＤＰＣ符号は、１９９０年代後半に再研究され、ＬＤＰＣ符号に対応するタナーグラフ（ファクターグラフの特別ケース）上で積和（ｓｕｍ−ｐｒｏｄｕｃｔ）アルゴリズムに基づく反復復号を適用することにより復号化を実行すると、Ｓｈａｎｎｏｎのチャネルリミットに近接する性能を有することが証明された。
【０００４】
ＬＤＰＣ符号は、通常、グラフ表現技術を用いて示され、グラフ理論、代数学、及び確率論に基づく方法を通じて多くの特性を分析することができる。一般的に、チャネル符号のグラフモデルは、符号の描写に有用であり、符号化されたビットに関する情報をグラフ内の頂点（ｖｅｒｔｅｘ）にマッピングし、各ビット間の関係をグラフ内のエッジにマッピングすることにより、各頂点が各エッジを介して所定のメッセージをやりとりする通信ネットワークと見なすことができ、したがって、自然の復号アルゴリズムを導出することが可能となる。例えば、グラフの一種と見なされることができるトレリス（ｔｒｅｌｌｉｓ）から導出された復号アルゴリズムは、よく知られているビタビ（Ｖｉｔｅｒｂｉ）アルゴリズム、及びＢａｈｌ、Ｃｏｃｋｅ、Ｊｅｌｉｎｅｋ、及びＲａｖｉｖ（ＢＣＪＲ）アルゴリズムを含む。
【０００５】
ＬＤＰＣ符号は、一般的に、パリティ検査行列と定義され、タナーグラフ（Ｔａｎｎｅｒ ｇｒａｐｈ）と称される二部グラフ（ｂｉｐａｒｔｉｔｅ ｇｒａｐｈ）を用いて表現することができる。この二部グラフは、グラフを構成する頂点が相互に異なる２つのタイプに分けられることを意味し、ＬＤＰＣ符号は、変数ノードと検査ノードと呼ばれる頂点を含む二部グラフで表現される。この変数ノードは、この符号化されたビットに一対一にマッピングされる。
【０００６】
図１及び図２を参照して、ＬＤＰＣ符号のグラフ表現方法について説明する。
図１は、４個の行及び８個の列を含むＬＤＰＣ符号のパリティ検査行列Ｈ１の例を示す。
図１を参照すると、列の個数が８であるために、パリティ検査行列Ｈ１は、長さ８の符号語を生成するＬＤＰＣ符号を意味し、この列は、符号化された８ビットにマッピングされる。
【０００７】
図２は、図１のＨ１に対応するタナーグラフを示す図である。
図２を参照すると、ＬＤＰＣ符号のタナーグラフは、８個の変数ノードｘ１（２０２）、ｘ２（２０４）、ｘ３（２０６）、ｘ４（２０８）、ｘ５（２１０）、ｘ６（２１２）、ｘ７（２１４）、及びｘ８（２１６）と４個の検査ノード２１８、２２０、２２２、及び２２４とを含む。ここで、ＬＤＰＣ符号のパリティ検査行列Ｈ１のｉ番目の列及びｊ番目の行は、変数ノードｘｉ及びｊ番目の検査ノードにマッピングされる。また、ＬＤＰＣ符号のパリティ検査行列Ｈ１のｉ番目の列及びｊ番目の行が相互に交差する地点での１の値、すなわち、０でない値は、図２に示すタナーグラフ上で変数ノードｘｉとｊ番目の検査ノード間にエッジが存在することを意味する。
【０００８】
ＬＤＰＣ符号のタナーグラフにおいて、変数ノード及び検査ノードの次数は、各ノードに接続されているエッジの個数を意味し、この次数は、ＬＤＰＣ符号のパリティ検査行列で関連するノードに対応する列又は行で０でないエントリーの個数と同一である。例えば、図２において、変数ノードｘ１（２０２）、ｘ２（２０４）、ｘ３（２０６）、ｘ４（２０８）、ｘ５（２１０）、ｘ６（２１２）、ｘ７（２１４）、及びｘ８（２１６）の次数は、それぞれ４、３、３、３、２、２、２、及び２であり、検査ノード２１８、２２０、２２２、及び２２４の次数は、それぞれ６、５、５、及び５である。
【０００９】
また、図２の変数ノードに対応する図１のパリティ検査行列Ｈ１のそれぞれの列で０でないエントリーの個数は、上記した次数４、３、３、３、２、２、２、及び２と一致し、図２の検査ノードに対応する図１のパリティ検査行列Ｈ１のそれぞれの行で０でないエントリーの個数は、上記した次数６、５、５、及び５と一致する。
【００１０】
ＬＤＰＣ符号のノードに対する次数分布（ｄｅｇｒｅｅ ｄｉｓｔｒｉｂｕｔｉｏｎ）を示すために、次数がｉである変数ノードの個数と変数ノードの総数との比率をｆｉとして定義し、次数がｊである検査ノードの個数と検査ノードの総数との比率をｇｊとして定義する。
例えば、図１及び図２に対応するＬＤＰＣ符号の場合には、ｆ２＝４／８、ｆ３＝３／８、ｆ４＝１／８、ｉ≠２、３、４に対してｆｉ＝０であり、ｇ５＝３／４、ｇ６＝１／４である、ｊ≠５、６に対してｇｊ＝０である。
【００１１】
ＬＤＰＣ符号の長さをＮ、すなわち、列の個数をＮとして定義し、行の個数をＮ／２として定義する時、上述した次数分布を有する全パリティ検査行列で０でないエントリーの密度は、下記の数式（１）のように計算される。
【数１】
【００１２】
上記数式（１）において、Ｎが増加するに従って、パリティ検査行列内の‘１’の密度は減少する。一般的に、ＬＤＰＣ符号について、符号長さＮが０でないエントリーの密度に反比例するので、Ｎが大きいＬＤＰＣ符号は、非常に低い密度を有する。ＬＤＰＣ符号の名称での用語“低密度”は、上述した関係に由来する。
【００１３】
次に、図３を参照して本発明で適用される構造的なＬＤＰＣ符号のパリティ検査行列の特性について説明する。
図３は、ヨーロッパデジタルブロードキャスト標準の１つである第２世代衛星デジタルビデオブロードキャスト（ＤＶＢ−Ｓ２）で標準技術として採択されたＬＤＰＣ符号を概略的に示す。
図３において、Ｎ１は、ＬＤＰＣ符号語の長さを示し、Ｋ１は、情報語の長さを提供し、（Ｎ１−Ｋ１）は、パリティ長さを提供する。また、整数Ｍ１及びｑは、ｑ＝（Ｎ１−Ｋ１／Ｍ１）を満足するように決定される。好ましくは、Ｋ１／Ｍ１は、整数でなければならない。
【００１４】
図３を参照すると、パリティ検査行列でパリティ部分、すなわち、Ｋ１番目の列から（Ｎ１−１）番目の列までの構成は、デュアル対角（ｄｕａｌ ｄｉａｇｏｎａｌ）形態を有する。したがって、パリティ部分に対応する列の次数分布について、次数‘１’を有する最後の列を除いて、すべての列は、次数‘２’を有する。
【００１５】
パリティ検査行列において、情報語部分、すなわち、０番目の列から（Ｋ１−１）番目の列までの構成は、次の規則を用いてなされる。
〔規則１〕 パリティ検査行列で情報語に対応するＫ１個の列をＭ１個の列で構成された複数のグループにグループ化することにより、トータルＫ１／Ｍ１個の列グループを生成する。各列グループに属している列を形成する方法は、下記の規則２に従う。
【００１６】
〔規則２〕 最初に、ｉ（ここで、ｉ＝１，．．．，Ｋ１／Ｍ１）番目の列グループ内の各０番目の列での‘１’の位置を決定する。各ｉ番目の列グループ内の０番目の列の次数をＤｉで示す際に、‘１’を有する行の位置を
【数２】
と仮定すると、‘１’を有する行の位置
【数３】
は、ｉ番目の列グループ内のｊ（ここで、ｊ＝１，２，．．．，Ｍ１−１）番目の列で下記の数式（２）のように定義される。
【数４】
【００１７】
上述した規則に従うと、ｉ番目（ここで、ｉ＝１，．．．，Ｋ１／Ｍ１）の列グループに属している列の次数がすべてＤｉに等しいことを分かる。
上述した規則に従ってパリティ検査行列に関する情報を格納しているＤＶＢ−Ｓ２ ＬＤＰＣ符号の構成を容易に理解するために、次のような具体的な例について説明する。
【００１８】
具体的な例として、Ｎ１＝３０、Ｋ１＝１５、Ｍ１＝５、及びｑ＝３の場合に、３個の列グループ内の０番目の列に対する‘１’を有する行の位置に関する情報の３つのシーケンスは、次のように表現することができる。ここで、これらのシーケンスは、説明の便宜上、“加重値−１位置シーケンス（ｗｅｉｇｈｔ−１ ｐｏｓｉｔｉｏｎ ｓｅｑｕｅｎｃｅｓ）”と称する。
【数５】
【００１９】
各列グループ内の０番目の列の“加重値−１位置シーケンス”について、説明の便宜上、対応する位置シーケンスだけが列グループ別に次のように表現されることができる。例えば、
０ １ ２
０ １１ １３
０ １０ １４
言い換えれば、このｉ番目のラインでのｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループに対する行の位置に関する情報を順次に示す。
【００２０】
上述した具体的な例に対応する情報と規則１及び規則２とを用いてパリティ検査行列を構成することにより、図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号と同一の概念を有するＬＤＰＣ符号を生成することができる。
規則１及び規則２に従って設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号が構造形状を用いて効率的に符号化することができることが知られている。パリティ検査行列に基づくＤＶＢ−Ｓ２を用いてＬＤＰＣ符号化を実行する工程での各ステップについては、次のような例を挙げて説明する。
【００２１】
以下の説明において、具体的な例として、Ｎ１＝１６２００、Ｋ１＝１０８００、Ｍ１＝３６０、及びｑ＝１５を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する符号化工程について説明する。説明の便宜のために、長さＫ１を有する情報語ビットは、
【数６】
として示され、長さ（Ｎ１−Ｋ１）を有するパリティビットは、
【数７】
として表現される。
【００２２】
〔ステップ１〕ＬＤＰＣ符号化器は、パリティビットを次のように初期化する。
【数８】
【００２３】
〔ステップ２〕ＬＤＰＣ符号化器は、パリティ検査行列を示す格納されているシーケンスの０番目の“加重値−１位置シーケンス”から列グループ内で‘１’が位置した行に関する情報を読み出す。
０ ２０８４ １６１３ １５４８ １２８６ １４６０ ３１９６ ４２９７ ２４８１ ３３６９ ３４５１ ４６２０ ２６２２
【数９】
【００２４】
ＬＤＰＣ符号化器は、上記読み出された情報及び１番目の情報語ビットｉ０を用いて下記の数式（３）に従って特定のパリティビットｐｘをアップデートする。ここで、ｘは、
【数１０】
の値を示す。
【数１１】
上述した数式（３）において、
【数１２】
は、
【数１３】
として表現することもでき、
は、２進加算を意味する。
【００２５】
〔ステップ３〕次に、ＬＤＰＣ符号化器は、ｉ０の後の次の３５９個の情報語ビットｉｍ（ここで、ｍ＝１，２，．．．，３５９）に対して下記の数式（４）の値を求める。
【数１４】
上述した数式（４）において、ｘは、
【数１５】
の値を示す。上述した数式（４）は、上述した数式（２）と同一の概念を有することに留意しなければならない。
【００２６】
次いで、ＬＤＰＣ符号化器は、上述した数式（４）で求められた値を用いて数式（３）と類似した動作を実行する。すなわち、ＬＤＰＣ符号化器は、ｉｍに対して
【数１６】
をアップデートする。例えば、ｍ＝１、すなわち、ｉ１に対して、ＬＤＰＣ符号化器は、下記の数式（５）で定義されるように、パリティビット
【数１７】
をアップデートする。
【数１８】
上述した数式（５）において、ｑ＝１５であることに留意しなければならない。ＬＤＰＣ符号化器は、ｍ＝１，２，．．．，３５９に対して上記のような工程を同様に実行する。
【００２７】
〔ステップ４〕ステップ２と同様に、ＬＤＰＣ符号化器は、３６１番目の情報語ビットｉ３６０に対して１番目の“加重値−１位置シーケンス”
【数１９】
の情報を読み出し、特定のｐｘをアップデートする。ここで、ｘは、
【数２０】
である。
ＬＤＰＣ符号化器は、ｉ３６０の後の次の３５９個の情報語ビットｉ３６１，ｉ３６２，．．．，ｉ７１９に数式（４）を同様に適用することにより、
【数２１】
をアップデートする。
【００２８】
〔ステップ５〕ＬＤＰＣ符号化器は、それぞれの３６０個の情報語ビットを有するすべてのグループに対してステップ２、３、及び４を反復する。
【００２９】
〔ステップ６〕ＬＤＰＣ符号化器は、最終的に数式（６）を用いてパリティビットを決定する。
【数２２】
【００３０】
上述した数式（６）のパリティビットｐｉは、ＬＤＰＣ符号化が完了したパリティビットである。
上述したように、ＤＶＢ−Ｓ２において、ＬＤＰＣ符号化器は、ステップ１からステップ６までの工程を介してＬＤＰＣ符号化を行う。
【００３１】
ＬＤＰＣ符号の性能がタナーグラフのサイクル特性に密接に関連していることがよく知られている。特に、タナーグラフにおいて、短い長さのサイクルの個数が多い場合に性能劣化が発生し得ることが実験によりよく知られている。したがって、高性能を有するＬＤＰＣ符号を設計するためには、タナーグラフ上のサイクル特性を考慮すべきである。
【００３２】
しかしながら、良好なサイクル特性を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法は提案されていない。実際に、ＤＶＢ−Ｓ２ ＬＤＰＣ符号に対して、タナーグラフのサイクル特性の最適化が考慮されていないため、エラーフロア（ｅｒｒｏｒ ｆｌｏｏｒ）現象は、高い信号対雑音比（ＳＮＲ）で観察される。これらの理由で、ＤＶＢ−Ｓ２構造を有するＬＤＰＣ符号を設計する際にサイクル特性を効率的に改善させることができる方法が要求されているという問題がある。
【発明の概要】
【発明が解決しようとする課題】
【００３３】
したがって、本発明は、上述した従来技術の問題点を解決するために提案されたものであり、その目的は、ＬＤＰＣ符号を使用する通信システムにおけるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために巡回置換行列に基づいて設計された準巡回ＬＤＰＣ符号のパリティ検査行列生成方法を提供することにある。
【００３４】
また、本発明は、ＬＤＰＣ符号を使用する通信システムにおけるタナーグラフ特性がよいＤＶＢ−Ｓ２ ＬＤＰＣ符号と同一のＬＤＰＣ符号のパリティ検査行列生成方法を提供することにある。
【課題を解決するための手段】
【００３５】
上記のような目的を達成するために、本発明の一態様によれば、低密度パリティ検査（ＬＤＰＣ）符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法が提供される。前記方法は、前記ＬＤＰＣ符号を設計するためのパラメータを決定するステップと、前記決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を形成するステップと、前記第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成するステップと、前記第２のパリティ検査行列を再整列させることにより第３のパリティ検査行列を生成するステップと、を有する。
【発明の効果】
【００３６】
本発明は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するにあたりタナーグラフの特性を最適化することによりＬＤＰＣ符号を使用する通信システムの性能を最適化することができる。
【図面の簡単な説明】
【００３７】
【図１】長さが８であるＬＤＰＣ符号のパリティ検査行列の一例を示す図である。
【図２】長さが８であるＬＤＰＣ符号のパリティ検査行列の一例のタナーグラフを示す図である。
【図３】ＤＶＢ−Ｓ２ ＬＤＰＣ符号の概略的な構成を示す図である。
【図４】ＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列の一例を示す図である。
【図５】本発明の実施形態による図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列で所定の規則に従って各列及び行を再配列することにより生成されるパリティ検査行列を示す図である。
【図６】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図７】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を変換することにより得られた結果を示す図である。
【図８】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する工程を示すフローチャートである。
【図９】本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号のコンピュータシミュレーション結果を示す図である。
【図１０】本発明の実施形態による再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送受信器の構成を示すブロック図である。
【図１１】本発明の実施形態によるＬＤＰＣ符号を使用する送信装置の構成を示すブロック図である。
【図１２】本発明の実施形態によるＬＤＰＣ符号を使用する受信装置の構成を示すブロック図である。
【図１３】本発明の実施形態によるＬＤＰＣ符号を使用する受信装置での受信動作を示すフローチャートである。
【発明を実施するための形態】
【００３８】
以下、本発明の好適な一実施形態を、添付図面を参照しつつ詳細に説明する。
下記の説明において、明瞭性と簡潔性の観点から、本発明に関連した公知の機能や構成に関する具体的な説明が本発明の要旨を不明瞭にすると判断される場合には、その詳細な説明を省略する。
【００３９】
本発明は、タナーグラフの特性が優秀なＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法を提供する。また、本発明は、設計されたＬＤＰＣ符号のパリティ検査行列を用いてＬＤＰＣ符号語を生成する方法及びその装置を提供する。
【００４０】
図４に示すＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号の構造特性について説明する。
図４に示すパリティ検査行列の場合に、Ｎ１＝３０、Ｋ１＝１５、Ｍ１＝５、及びｑ＝３であり、３個の列グループ内の０番目の列に対する行の“加重値−１位置シーケンス”は、次のようである。
０ １ ２
０ １１ １３
０ １０ １４
ここで、このｉ番目のラインでのｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループで１を有する行の位置に関する情報を順次に示す。
【００４１】
まず、図４のパリティ検査行列は、次のような規則に従って再構成される。図４は、ＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を示す図である。
〔規則３〕 ０番目の行〜（Ｎ１−Ｋ１−１）番目の行は、（ｑ・ｉ＋ｊ）番目の行が（Ｍ１・ｊ＋ｉ）番目の行に位置するように再整列させる。ここで、０≦ｉ＜Ｍ１及び０≦ｊ＜ｑである。
〔規則４〕 ０番目の列〜（Ｋ１−１）番目の列は、そのままおき、Ｋ１番目の列〜（Ｎ１−１）番目の列は、（Ｋ１＋ｑ・ｉ＋ｊ）番目の列が（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列に位置するように再整列させる。
【００４２】
図５に示す形態を有するパリティ検査行列は、規則３及び規則４に従って図４のパリティ検査行列を再構成することにより得られる。
図５は、本発明の実施形態による図４のＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列で所定の規則に従って各列及び行を再配列することにより生成されるパリティ検査行列を示す図である。
【００４３】
図５において、‘１’が０番目の行の（Ｎ１−１）番目の列にあると仮定すると、図５のパリティ検査行列がＭ１×Ｍ１、すなわち、５×５のサイズを有する巡回置換行列で構成された準巡回ＬＤＰＣ符号の一種であることをわかる。
ここで、‘巡回置換行列’は、恒等行列（ｉｄｅｎｔｉｔｙ ｍａｔｒｉｘ）の各行を右方に１つずつ巡回移動させた置換行列の１つの種類を意味する。また、‘準巡回ＬＤＰＣ符号’は、パリティ検査行列を同一のサイズを有するいくつかのブロックに区分し、巡回置換行列又は０行列を各ブロックにマッピングすることにより生成されたＬＤＰＣ符号の一種を意味する。
【００４４】
要約すると、規則３及び規則４を通じてＤＶＢ−Ｓ２ ＬＤＰＣ符号のパリティ検査行列を再構成することにより準巡回ＬＤＰＣ符号と近似したパリティ検査行列を得ることができることをわかる。また、ＤＶＢ−Ｓ２ ＬＤＰＣ符号が規則３及び規則４の逆工程を通じて準巡回ＬＤＰＣ符号から生成されることができることが予想される。
【００４５】
ＤＶＢ−Ｓ２ ＬＤＰＣ符号についての研究結果は、ほとんど知られていないが、準巡回ＬＤＰＣ符号の場合には非常に様々な設計方法が知られている。特に、準巡回ＬＤＰＣ符号の設計方法は、タナーグラフ上のサイクル特性を最適化する周知の方法を含む。
【００４６】
本発明の実施形態は、よく知られている準巡回ＬＤＰＣ符号のタナーグラフ上のサイクル特性を改善する方法を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する方法を提供する。
しかしながら、準巡回ＬＤＰＣ符号のサイクル特性を改善する方法が主な内容ではないため、説明の便宜上、具体的な内容を省略する。
【００４７】
以下では、準巡回ＬＤＰＣ符号を用いてＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するための方法について説明する。ＤＶＢ−Ｓ２ ＬＤＰＣ符号は、符号語長さＮ１、情報語長さＫ１、パリティ長さ（Ｎ１−Ｋ１）、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１を有する。
【００４８】
準巡回ＬＤＰＣ符号のパリティ検査行列を図６に示す。
図６は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を示す図である。
図６に示すパリティ検査行列は、（Ｎ１−Ｋ１）個の行及びＮ１個の列を有し、Ｍ１×Ｍ１個の部分ブロックに分けられる。説明の便宜上、ｔ＝Ｋ１／Ｍ１である場合に、図６のパリティ検査行列での情報語部分及びパリティ部分は、それぞれｔ個の列ブロック及びｑ個の列ブロックで構成され、合計ｑ個の行ブロックを有する。ここで、Ｎ１／Ｍ１＝ｔ＋ｑである。
【００４９】
図６のパリティ検査行列を構成する各部分ブロックは、巡回置換行列又はゼロ行列に対応する。ここで、巡回置換行列は、Ｍ１×Ｍ１サイズを有し、次のように定義される巡回置換行列Ｐに基づいて生成される。
【数２３】
【００５０】
図６において、ａｉｊは０〜Ｍ１−１の整数又は“∞”の値を有し、Ｐ０は恒等行列Ｉとして定義され、Ｐ∞は、Ｍ１×Ｍ１ゼロ行列を意味する。また、パリティ部分の数字‘０’は、Ｍ１×Ｍ１ゼロ行列を意味する。
【００５１】
図６のパリティ検査行列のもっとも大きい特徴は、パリティに対応する列ブロックが図に示すように恒等行列Ｉと、巡回置換行列
【数２４】
と、を有することにある。
言い換えれば、パリティに対応する列ブロックは、図６に示す構成に固定される。巡回置換行列
【数２５】
は、次のように定義される。
【数２６】
【００５２】
図６に示す準巡回ＬＤＰＣ符号は、パリティ部分に対応する列ブロックの構成が固定されるので、準巡回ＬＤＰＣ符号のサイクルを最適化する工程で変わらない部分である。
言い換えれば、このパリティ部分に対応する列ブロックが図６のパリティ検査行列で固定されるので、このパリティに対応する変数ノード間の接続状態は、タナーグラフ上で決定され、これにより、このタナーグラフのサイクルを最適化するために情報語部分に対応する変数ノード間の接続状態を最適化するだけでよい。
【００５３】
上述したように、準巡回ＬＤＰＣ符号のタナーグラフ上のサイクル特性を最適化する非常に様々な方法が知られている。本発明では、サイクル特性が最適化されたタナーグラフを有する準巡回ＬＤＰＣ符号の設計方法が主な内容ではないため、具体的な内容を省略する。
【００５４】
準巡回ＬＤＰＣ符号の設計方法を通じて図６の準巡回パリティ検査行列でパリティ部分の構成が固定された状態で優秀な性能を有することができるように次数分布が決定されると仮定する。
対応する次数分布に従って情報語部分に対応する列ブロックで巡回置換行列及びゼロ行列の位置が定められ、タナーグラフのサイクル特性が最適化される。
【００５５】
例えば、図７に示す形態は、図６のパリティ検査行列で１番目の行ブロックでの最後の（Ｎ１／Ｍ１）番目又は（ｔ＋ｑ）番目の列ブロックに対応する巡回置換行列
【数２７】
で１番目の行での最後の列の‘１’を除去することにより行うことができる。
図７は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要な準巡回ＬＤＰＣ符号のパリティ検査行列を変換することにより得られた結果を示す図である。
図７において、巡回置換行列
【数２８】
が次のような行列Ｑに変更されることに留意すべきである。
【数２９】
【００５６】
次の規則５及び規則６は、規則３及び規則４の逆工程を適用することにより定義される。
〔規則５〕 ０番目の列〜（Ｋ１−１）番目の列は、そのままおき、Ｋ１番目の列〜（Ｎ１−１）番目の列は、（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列が（Ｋ１＋ｑ・ｉ＋ｊ）番目の列に位置するように再整列させる。ここで、０≦ｉ＜Ｍ１及び０≦ｊ＜ｑである。
〔規則６〕 ０番目の行〜（Ｎ１−Ｋ１−１）番目の行は、（Ｍ１・ｊ＋ｉ）番目の行が（ｑ・ｉ＋ｊ）番目の行に位置するように再整列される。
【００５７】
規則５及び規則６を適用することにより上述した工程を通じて図６の準巡回ＬＤＰＣ符号から生成されたＬＤＰＣ符号のパリティ検査行列は、例えば、図３に示したＤＶＢ−Ｓ２ ＬＤＰＣ符号の形態を有するパリティ検査行列となる。
符号語長さ、情報語長さ、及びパリティ長さが、それぞれＮ１、Ｋ１、及び（Ｎ１−Ｋ１）であり、ｑ＝（Ｎ１−Ｋ１）／Ｍ１であるＤＶＢ−Ｓ２パリティ検査行列を設計するための上述した方法は、次のような工程に要約することができる。
【００５８】
〔ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程〕
図８は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計する工程を示すフローチャートである。
図８を参照すると、ステップ８０１で、所望するＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計のために必要なパラメータを決定する。本発明では、良好な次数分布だけではなく符号語長さ及び情報語長さのようなパラメータがＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するためにあらかじめ定められていると仮定する。
【００５９】
次に、ステップ８０３で、図６に示すように、Ｍ１×Ｍ１サイズの巡回置換行列及びゼロ行列で構成された準巡回ＬＤＰＣ符号のパリティ検査行列は、ステップ８０１で決定されたパラメータに従って構成される。図６において、パリティ部分に対応する列ブロックは、常に特定の形態に固定されている。
【００６０】
次に、ステップ８０５で、準巡回ＬＤＰＣ符号のタナーグラフのサイクル特性を改善するアルゴリズムを適用することにより図６の情報語部分に対応する列ブロックの巡回置換行列を決定する。ここで、サイクル特性を改善するためには既知のアルゴリズムを使用してもよい。
次に、ステップ８０７で、図７に示したパリティ検査行列は、例えば、ステップ８０５で確定された図６のパリティ検査行列で１番目の行での最後の列の‘１’を除去することにより得られる。
【００６１】
次に、ステップ８０９で、図７のパリティ検査行列での列及び行は、規則５及び規則６を図７のパリティ検査行列に適用することにより再整列される。最終的に得られたパリティ検査行列は、例えば、図３に示したＤＶＢ−Ｓ２ ＬＤＰＣ符号であることができる。
符号語は、上記のようなステップを通じて設計されたＬＤＰＣ符号に上述したＤＶＢ−Ｓ２ ＬＤＰＣ符号化工程を適用することにより生成されることができる。
【００６２】
ＤＶＢ−Ｓ２ ＬＤＰＣ符号の性能を分析するために、次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計した。例えば、
Ｎ１＝６４８０００、Ｋ１＝３８８８０、Ｍ１＝３６０、ｑ＝７２
【００６３】
このパラメータを有する符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、以下の表１及び表２に示すパリティ検査行列は、例えば、ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程を適用することにより合計Ｎ１／Ｍ１＝１８０個の列ブロック及びｑ＝（Ｎ１−Ｋ１）／Ｍ１＝７２個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。ｉ番目の列のｉ番目の“加重値−１位置シーケンス”は、ｉ番目の列グループで１を有する行の位置に関する情報を順次に示す。
【表１】
【表２】
【００６４】
また、次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計した。例えば、
Ｎ１＝１６２００、Ｋ１＝９７２０、Ｍ１＝３６０、ｑ＝１８
このパラメータを有する符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、表３〜表６に示すパリティ検査行列は、例えば、ＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程に適用することにより合計Ｎ１／Ｍ１＝４５個の列ブロック及びｑ＝（Ｎ１−Ｋ１）／Ｍ１＝１８個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。ｉ番目の列のｉ番目の“加重値−１位置シーケンス”がｉ番目の列グループで１を有する行の位置に関する情報を順次に示すことに留意する。
【００６５】
【表３】
【表４】
【表５】
【表６】
【００６６】
新たに設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号と既存のＤＶＢ−Ｓ２ ＬＤＰＣ符号間の性能比較を図９に示す。
図９は、本発明の実施形態によるＤＶＢ−Ｓ２ ＬＤＰＣ符号のコンピュータシミュレーション結果を示す図である。
【００６７】
加法性白色ガウス雑音（Ａｄｄｉｔｉｖｅ Ｗｈｉｔｅ Ｇａｕｓｓｉａｎ Ｎｏｉｓｅ：ＡＷＧＮ）チャネルが二位相偏移（ＢＰＳＫ）変調方式を使用する場合に、約０．１５ｄＢの性能改善がＢＥＲ＝１０−４でなされることをわかる。
符号化率が３／５であるＤＶＢ−Ｓ２ ＬＤＰＣ符号の性能改善は、表１〜表６に示すように、このパリティ検査行列に関する情報だけを変更することによりなすことができる。
【００６８】
図８を参照して説明したＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程は、符号化率が３／５である場合だけでなく様々な符号化率に対しても使用されることができる。次のようなパラメータを有するＤＶＢ−Ｓ２ ＬＤＰＣ符号は、他の符号化率を有するＤＶＢ−Ｓ２ ＬＤＰＣ符号の設計に対する実施形態として設計された。
Ｎ１＝６４８００、Ｋ１＝４３２００、Ｍ１＝３６０、ｑ＝６０
【００６９】
このパラメータを有する符号化率が２／３であるＤＶＢ−Ｓ２ ＬＤＰＣ符号を設計するために、表７〜表１０に示すパリティ検査行列は、例えば、図８のＤＶＢ−Ｓ２ ＬＤＰＣ符号設計工程を適用することにより合計Ｎ１／Ｍ１＝１８０個の列ブロック及びｑ＝６０個の行ブロックを有する準巡回ＬＤＰＣ符号から得ることができる。
【００７０】
【表７】
【表８】
【表９】
【表１０】
【００７１】
図１０は、本発明の実施形態による再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送受信器の構成を示すブロック図である。
【００７２】
図１０を参照すると、メッセージｕは、受信器１０３０に送信される前に送信器１０１０内のＬＤＰＣ符号化器１０１１に入力される。ＬＤＰＣ符号化器１０１１は、入力されたメッセージｕを符号化し、符号化された信号ｃを変調器１０１３に送信する。変調器１０１３は、この符号化された信号を変調し、この変調された信号ｓを無線チャネル１０２０を通じて受信器１０３０に送信する。受信器１０３０内の復調器１０３１は、送信器１０１０により送信された信号ｒを復調し、この復調された信号ｘをＬＤＰＣ復号化器１０３３に出力する。その後に、ＬＤＰＣ復号化器１０３３は、メッセージの推定値
【数３０】
を無線チャネル１０２０を介して受信されたデータから計算する。
【００７３】
この再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムにおける送信装置の具体的な構成を図１１に示す。
図１１は、本発明の実施形態による再設計されたＬＤＰＣ符号を使用する送信装置の構成を示すブロック図である。
送信装置は、制御部１１３０、ＬＤＰＣ符号パリティ検査行列抽出部１１１０、及びＬＤＰＣ符号化器１１５０を含む。
【００７４】
ＬＤＰＣ符号パリティ検査行列抽出部１１１０は、システムの要求事項に従ってＬＤＰＣ符号パリティ検査行列を抽出する。ＬＤＰＣ符号パリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、送信装置から与えられることもでき、又は送信装置で生成することもできる。
【００７５】
制御部１１３０は、システムの要求事項に合うように符号化率、符号語の長さ、又は情報語の長さに従って必要なパリティ検査行列を決定するように制御する。
ＬＤＰＣ符号化器１１５０は、制御部１１３０及びＬＤＰＣ符号パリティ検査行列抽出部１１１０により読み出されたＬＤＰＣ符号パリティ検査行列情報に基づいて符号化を実行する。
【００７６】
図１２は、本発明の実施形態による受信装置の構成を示すブロック図である。
図１２は、この再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムから送信された信号を受信し、この受信された信号からユーザが所望するデータを復元する受信装置を示す図である。
【００７７】
受信装置は、制御部１２５０、パリティ検査行列決定部１２３０、ＬＤＰＣ符号パリティ検査行列抽出部１２７０、復調器１２１０、及びＬＤＰＣ復号化器１２９０を含む。
復調器１２１０は、受信されたＬＤＰＣ符号を復調し、該復調された信号をパリティ検査行列決定部１２３０及びＬＤＰＣ復号化器１２９０に送信する。
【００７８】
パリティ検査行列決定部１２３０は、制御部１２５０の制御の下で、この復調された信号に基づいてシステムで使用されたＬＤＰＣ符号のパリティ検査行列を判定する。
制御部１２５０は、パリティ検査行列決定部１２３０からの判定結果をＬＤＰＣ符号パリティ検査行列抽出部１２７０及びＬＤＰＣ復号化器１２９０に送信する。
【００７９】
ＬＤＰＣ符号パリティ検査行列抽出部１２７０は、制御部１２５０の制御の下でシステムより要求されるＬＤＰＣ符号のパリティ検査行列を抽出し、該パリティ検査行列をＬＤＰＣ復号化器１２９０に送信する。上述したように、ＬＤＰＣ符号のパリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、受信装置から与えられることもでき、受信装置で生成することもできる。
【００８０】
ＬＤＰＣ復号化器１２９０は、制御部１２５０の制御の下で、復調器１２１０から送信された受信信号及びＬＤＰＣ符号パリティ検査行列抽出部１２７０から送信されたＬＤＰＣ符号のパリティ検査行列に関する情報に基づいて復号化を実行する。
【００８１】
図１２での受信装置の動作フローチャートを図１３に示す。
ステップ１３０１で、復調器１２１０は、再設計されたＤＶＢ−Ｓ２ ＬＤＰＣ符号を使用する通信システムから送信された信号を受信し、該受信された信号を復調する。この後に、ステップ１３０３で、パリティ検査行列決定部１２３０は、この復調された信号に基づいてシステムで使用されたＬＤＰＣ符号のパリティ検査行列を決定する。
【００８２】
パリティ検査行列決定部１２３０により決定された結果は、ステップ１３０５で、ＬＤＰＣ符号パリティ検査行列抽出部１２７０に伝達される。ＬＤＰＣ符号パリティ検査行列抽出部１２７０は、ステップ１３０７で、システムにより要求されるＬＤＰＣ符号のパリティ検査行列を抽出し、これをＬＤＰＣ復号化器１２９０に伝達する。
【００８３】
上述したように、ＬＤＰＣ符号のパリティ検査行列は、表１〜表１０に示すシーケンス情報から抽出することもでき、パリティ検査行列を格納しているメモリから抽出することもでき、送信装置内から与えられることもでき、又は送信装置で生成することもできる。
【００８４】
この後、ＬＤＰＣ復号化器１２９０は、ステップ１３０９で、ＬＤＰＣ符号パリティ検査行列抽出部１２７０から伝達されたＬＤＰＣ符号のパリティ検査行列に関する情報に基づいて復号化を実行する。
【００８５】
以上、本発明を具体的な実施形態を参照して詳細に説明してきたが、本発明の範囲及び趣旨を逸脱することなく様々な変更が可能であるということは、当業者には明らかであり、本発明の範囲は、上述の実施形態に限定されるべきではなく、特許請求の範囲の記載及びこれと均等なものの範囲内で定められるべきである。
【符号の説明】
【００８６】
１０１０ 送信器
１０１１ ＬＤＰＣ符号化器
１０１３ 変調器
１０２０ 無線チャネル
１０３０ 受信器
１０３１ 復調器
１０３３ ＬＤＰＣ復号化器
１１１０ ＬＤＰＣ符号パリティ検査行列抽出部
１１３０ 制御部
１１５０ ＬＤＰＣ符号化器
１２１０ 復調器
１２３０ パリティ検査行列決定部
１２５０ 制御部
１２７０ ＬＤＰＣ符号パリティ検査行列抽出部
１２９０ ＬＤＰＣ復号化器
【特許請求の範囲】
【請求項１】
低密度パリティ検査（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ：以下、ＬＤＰＣと記す）符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法であって、
前記ＬＤＰＣ符号を設計するためのパラメータを決定するステップと、
前記決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を形成するステップと、
前記第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列を再整列させることにより第３のパリティ検査行列を生成するステップと、を有することを特徴とする低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項２】
第２のパリティ検査行列を生成するステップは、前記第１のパリティ検査行列で１番目の行の最後の列の‘１’を除去することにより前記第２のパリティ検査行列を生成することを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項３】
第３のパリティ検査行列を生成するステップは、下記の規則１、規則２に従って前記第２のパリティ検査行列を再整列させるステップを含み、
前記規則１は、前記第２のパリティ検査行列の０番目の列乃至（Ｋ１−１）番目の列は、そのままにしておき、Ｋ１番目の列乃至（Ｎ１−１）番目の列は、（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列が（Ｋ１＋ｑ・ｉ＋ｊ）番目の列に位置するように再整列させる。ここで、Ｋ１は、前記第２のパリティ検査行列の情報語の長さを示し、Ｎ１は、符号語の長さを示し、０≦ｉ＜Ｍ１、０≦ｊ＜ｑ、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１であり、この時、Ｍ１、ｑ、及びＫ１／Ｍ１は、整数であり、
前記規則２は、前記第２のパリティ検査行列の０番目の行乃至（Ｎ１−Ｋ１−１）番目の行は、（Ｍ１・ｊ＋ｉ）番目の行が（ｑ・ｉ＋ｊ）番目の行に位置するように再整列させる。ここで、Ｋ１は、前記第２のパリティ検査行列の情報語の長さを示し、Ｎ１は、符号語の長さを示し、０≦ｉ＜Ｍ１、０≦ｊ＜ｑ、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１であり、この時、Ｍ１、ｑ、及びＫ１／Ｍ１は、整数である、ことを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項４】
前記第３のパリティ検査行列は、以下の表１に定義されるように生成されることを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表１】
【請求項５】
前記第３のパリティ検査行列は、以下の表２に定義されるように生成されることを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表２】
【請求項６】
前記第３のパリティ検査行列は、以下の表３に定義されるように生成されることを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表３】
【請求項７】
前記第３のパリティ検査行列は、情報語に対応する列を所定の個数の列をそれぞれ有する列にグループ化した複数の列グループで構成され、
前記表１での各行は、前記パリティ検査行列の対応する列グループで‘１’が位置する行の位置を示すシーケンス情報を含むことを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項１】
低密度パリティ検査（Ｌｏｗ−Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ−Ｃｈｅｃｋ：以下、ＬＤＰＣと記す）符号を使用する少なくとも制御部を有する通信システムにおける該制御部の制御によるパリティ検査行列生成方法であって、
前記ＬＤＰＣ符号を設計するためのパラメータを決定するステップと、
前記決定されたパラメータに従って準巡回ＬＤＰＣ符号の第１のパリティ検査行列を形成するステップと、
前記第１のパリティ検査行列でパリティ部分の所定の部分の除去を通じて第２のパリティ検査行列を生成するステップと、
前記第２のパリティ検査行列を再整列させることにより第３のパリティ検査行列を生成するステップと、を有することを特徴とする低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項２】
第２のパリティ検査行列を生成するステップは、前記第１のパリティ検査行列で１番目の行の最後の列の‘１’を除去することにより前記第２のパリティ検査行列を生成することを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項３】
第３のパリティ検査行列を生成するステップは、下記の規則１、規則２に従って前記第２のパリティ検査行列を再整列させるステップを含み、
前記規則１は、前記第２のパリティ検査行列の０番目の列乃至（Ｋ１−１）番目の列は、そのままにしておき、Ｋ１番目の列乃至（Ｎ１−１）番目の列は、（Ｋ１＋Ｍ１・ｊ＋ｉ）番目の列が（Ｋ１＋ｑ・ｉ＋ｊ）番目の列に位置するように再整列させる。ここで、Ｋ１は、前記第２のパリティ検査行列の情報語の長さを示し、Ｎ１は、符号語の長さを示し、０≦ｉ＜Ｍ１、０≦ｊ＜ｑ、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１であり、この時、Ｍ１、ｑ、及びＫ１／Ｍ１は、整数であり、
前記規則２は、前記第２のパリティ検査行列の０番目の行乃至（Ｎ１−Ｋ１−１）番目の行は、（Ｍ１・ｊ＋ｉ）番目の行が（ｑ・ｉ＋ｊ）番目の行に位置するように再整列させる。ここで、Ｋ１は、前記第２のパリティ検査行列の情報語の長さを示し、Ｎ１は、符号語の長さを示し、０≦ｉ＜Ｍ１、０≦ｊ＜ｑ、及びｑ＝（Ｎ１−Ｋ１）／Ｍ１であり、この時、Ｍ１、ｑ、及びＫ１／Ｍ１は、整数である、ことを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【請求項４】
前記第３のパリティ検査行列は、以下の表１に定義されるように生成されることを特徴とする請求項１に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表１】
【請求項５】
前記第３のパリティ検査行列は、以下の表２に定義されるように生成されることを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表２】
【請求項６】
前記第３のパリティ検査行列は、以下の表３に定義されるように生成されることを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【表３】
【請求項７】
前記第３のパリティ検査行列は、情報語に対応する列を所定の個数の列をそれぞれ有する列にグループ化した複数の列グループで構成され、
前記表１での各行は、前記パリティ検査行列の対応する列グループで‘１’が位置する行の位置を示すシーケンス情報を含むことを特徴とする請求項４に記載の低密度パリティ検査符号のパリティ検査行列生成方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【公開番号】特開２０１２−２３９２４０（Ｐ２０１２−２３９２４０Ａ）
【公開日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願番号】特願２０１２−２００５９０（Ｐ２０１２−２００５９０）
【出願日】平成２４年９月１２日（２０１２．９．１２）
【分割の表示】特願２０１０−５４６７０３（Ｐ２０１０−５４６７０３）の分割
【原出願日】平成２１年２月１８日（２００９．２．１８）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【出願人】（５０９１９１１５９）ポステック アカデミー‐インダストリー ファウンデーション (6)
【Ｆターム（参考）】
【公開日】平成２４年１２月６日（２０１２．１２．６）
【国際特許分類】
【出願日】平成２４年９月１２日（２０１２．９．１２）
【分割の表示】特願２０１０−５４６７０３（Ｐ２０１０−５４６７０３）の分割
【原出願日】平成２１年２月１８日（２００９．２．１８）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【出願人】（５０９１９１１５９）ポステック アカデミー‐インダストリー ファウンデーション (6)
【Ｆターム（参考）】
[ Back to top ]