移動通信システムにおけるブロック低密度パリティ検査符号の符号化／復号化装置及び方法
【課題】移動通信システムで誤り訂正能力を最大化するＬＤＰＣ符号を符号化/復号化する装置及び方法を提供する。
【解決手段】ＬＤＰＣ復号において、パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、そこから出力された信号から以前の信号を減算して出力する第１の加算器と、そこから出力された信号をデインタリービングして出力するデインタリーバと、その出力信号の確率値を検出して出力する検査ノード復号器と、その出力信号から、デインタリーバから出力された信号を減算する第２の加算器と、そこから出力された信号をインタリービングして変数ノード復号器及び第１の加算器に出力するインタリーバと、パリティ検査行列を生成し、デインタリービング方式及びインタリービング方式をパリティ検査行列に対応して制御する制御器とを含む。
【解決手段】ＬＤＰＣ復号において、パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、そこから出力された信号から以前の信号を減算して出力する第１の加算器と、そこから出力された信号をデインタリービングして出力するデインタリーバと、その出力信号の確率値を検出して出力する検査ノード復号器と、その出力信号から、デインタリーバから出力された信号を減算する第２の加算器と、そこから出力された信号をインタリービングして変数ノード復号器及び第１の加算器に出力するインタリーバと、パリティ検査行列を生成し、デインタリービング方式及びインタリービング方式をパリティ検査行列に対応して制御する制御器とを含む。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は移動通信システムに関するもので、特に、ブロック低密度パリティ検査符号を符号化/復号化する装置及び方法に関するものである。
【背景技術】
【０００２】
１９７０年代末の米国で、セルラー(ｃｅｌｌｕｌａｒ)方式の無線移動通信システム(Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）が開発された以来、韓国ではアナログ方式の１世代(１ｓｔ Ｇｅｎｅｒａｔｉｏｎ)移動通信システムと呼ばれるＡＭＰＳ(Ａｄｖａｎｃｅｄ Ｍｏｂｉｌｅ Ｐｈｏｎｅ Ｓｅｒｖｉｃｅ)方式で音声通信サービスを提供し始めた。以後、１９９０年代中盤から韓国では、２世代移動通信システムとして符号分割多重接続(Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ：以下、“ＣＤＭＡ”とする)方式のシステムを商用化して音声及び低速データサービスを提供した。
【０００３】
１９９０年代末から向上した無線マルチメディアサービス、全世界的ローミング(ｒｏａｍｉｎｇ)、高速データサービスなどを目標で始まった３世代移動通信システムであるＩＭＴ(Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ)-２０００は、現在一部商用化されてサービスが提供されている。特に、３世代移動通信システムは、移動通信システムでサービスするデータ量が急速に増加するに従って、より高速のデータを伝送するために開発された。すなわち、３世代移動通信システムは、パケットサービス通信システム形態で発展してきている。パケットサービス通信システムは、バースト(ｂｕｒｓｔ)パケットデータを複数の移動局に伝送するシステムとして、大容量データ伝送に適合するように設計されている。その結果、パケットサービス通信システムは高速パケットサービスのために発展している。
【０００４】
一方、現在は３世代移動通信システムから４世代移動通信システムに発展している状態である。４世代移動通信システムは、以前世代の移動通信システムのように単純な無線通信サービスに限定されず、有線通信ネットワークと無線通信ネットワークとの効率的連動及び統合サービスを目標として標準化されている。したがって、無線通信ネットワークで有線通信ネットワークの容量(ｃａｐａｃｉｔｙ)に近接する大容量データを伝送できる技術開発が要求されている。
【０００５】
このように、音声サービスデータだけでなく、映像、無線データなどの多様な情報を処理して伝送できる高速大容量通信システムが要求されることによって、適正なチャンネル符号化方式を用いてシステム伝送効率を高くすることが、システム性能向上に必須的な要素で作用するようになる。しかしながら、移動通信システムは、移動通信システムの特性上、データを伝送するときに、チャンネルの状況により雑音と、干渉(ｉｎｔｅｒｆｅｒｅｎｃｅ)及びフェージング(ｆａｄｉｎｇ)などによって不回避に誤り(ｅｒｒｏｒ)が発生する。したがって、誤り発生は、情報データの損失をもたらす。
【０００６】
このような誤り発生による情報データ損失を減少させるために、チャンネルの性格によって多様な誤り制御技術を使用することによって、移動通信システムの信頼度を向上させることができる。誤り制御技術の中で、誤り訂正符号(ｅｒｒｏｒ-ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅ)を使用する技術が一番普遍的である。ここで、誤り訂正符号の代表的な符号であるターボ符号(ｔｕｒｂｏ ｃｏｄｅ)と、低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：以下、“ＬＤＰＣ”とする)符号について説明する。
【０００７】
ターボ符号
ターボ符号は、最近第３世代移動通信システムで注目されている同期方式と非同期方式ですべて使用されている誤り訂正符号である。従来から順方向誤り訂正のために主に利用された畳み込み符号(ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅ)に比べて、このターボ符号は、高速データ伝送時に性能利得が優れると知られている。また、ターボ符号は、伝送チャンネルで発生する雑音による誤りを效果的に訂正してデータ伝送の信頼度を向上するという長所を有する。
【０００８】
ＬＤＰＣ符号
ＬＤＰＣ符号は、因子(ｆａｃｔｏｒ)グラフで和積(ｓｕｍ-ｐｒｏｄｕｃｔ)アルゴリズムに基づいた反復復号アルゴリズムを用いて復号することができる。ＬＤＰＣ符号の復号器(ｄｅｃｏｄｅｒ）は、和積アルゴリズムに基づいた反復復号アルゴリズムを使用するため、ターボ符号の復号器に比べて低い複雑度を有するだけでなく、並列処理復号器で実現することが容易である。ＬＤＰＣ符号を因子グラフで表現すると、ＬＤＰＣ符号の因子グラフ上にサイクルが存在するようになる。このサイクルが存在するＬＤＰＣ符号の因子グラフ上の反復復号は、準最適(ｓｕｂ-ｏｐｔｉｍａｌ)とは、既によく知られている事実である。また、ＬＤＰＣ符号は、反復復号を通じて優れた性能を有することも実験的に立証された事実である。しかしながら、ＬＤＰＣ符号の因子グラフで短い長さのサイクルが多く存在する場合には、ＬＤＰＣ符号の性能劣化が発生される。そのため、ＬＤＰＣ符号の因子グラフ上に短い長さのサイクルが存在しないようにＬＤＰＣ符号を設計するための研究が持続的に遂行されている。
【０００９】
ＬＤＰＣ符号の符号化過程は、一般的に高いウェイト(ｗｅｉｇｈｔ)密度を有する生成行列(ｇｅｎｅｒａｔｉｎｇ ｍａｔｒｉｘ）の特性により低いウェイト密度を有するパリティ検査行列(ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）を用いる形態で発展されてきた。ここで、“ウェイト”とは、生成行列及びパリティ検査行列を構成する要素(ｅｌｅｍｅｎｔ)のうち０でない値を有する要素の個数を示す。特に、パリティ検査行列でパリティに該当する部分行列(ｐａｒｔｉａｌ ｍａｔｒｉｘ）の形態が規則的な形態を有すると、より効率的な符号化が可能である。
【００１０】
一方、ＬＤＰＣ符号は０でない値を有する多様な符号を含んでいるため、ＬＤＰＣ符号の実用化問題において、多様な形態を有するＬＤＰＣ符号の効率的な符号化アルゴリズムと効率的な復号アルゴリズムを開発することが非常に重要である。また、ＬＤＰＣ符号のパリティ検査行列は、ＬＤＰＣ符号の性能を決定するため、優れた性能を有するパリティ検査行列を設計することも非常に重要である。すなわち、優れた性能を有する効率的なパリティ検査行列と、効率的な符号化アルゴリズム及び復号アルゴリズムを同時に考慮しなければ、高性能のＬＤＰＣ符号を生成することが可能になる。
【００１１】
また、ＬＤＰＣ符号は、大部分の要素が０の値を有し、０の値を有する要素以外の極少数の要素が１の値を有するパリティ検査行列によって定義される。例えば、(Ｎ，ｊ，ｋ)ＬＤＰＣ符号は、ブロック長Ｎである線形ブロック符号(ｌｉｎｅａｒ ｂｌｏｃｋ ｃｏｄｅ）で、各列(ｃｏｌｕｍｎ)ごとにｊ個の１の値を有する要素と、各行(ｒｏｗ)ごとにｋ個の１の値を有する要素を有し、１の値を有する要素を除いた要素は、すべて０の値を有する要素で構成された疎(ｓｐａｒｓｅ)構造のパリティ検査行列によって定義される。
【００１２】
上記に説明したように、パリティ検査行列内の各列のウェイト値がｊ個に一定で、パリティ検査行列内の各行のウェイト値がｋ個に一定のＬＤＰＣ符号を“均一ＬＤＰＣ符号”と称する。一方、パリティ検査行列内の各列のウェイト値と各行のウェイト値が一定しないＬＤＰＣ符号を“不均一ＬＤＰＣ符号”と称する。一般的に、均一ＬＤＰＣ符号の性能に比べて、不均一ＬＤＰＣ符号の性能がさらに優れると知られている。しかしながら、不均一ＬＤＰＣ符号の場合に、パリティ検査行列内の各列のウェイト値と各行のウェイト値が一定しないため、すなわち、不均一なため、パリティ検査行列内の各列のウェイトの個数と各行のウェイトの個数を適切に調節しなければ、優れた性能の保障を受けることができない。
【００１３】
ここで、図１を参照して、(Ｎ，ｊ，ｋ)ＬＤＰＣ符号、一例として(８，２，４)ＬＤＰＣ符号のパリティ検査行列を説明する。
【００１４】
図１は、一般的な(８，２，４)ＬＤＰＣ符号のパリティ検査行列を示す図である。図１を参照すると、(８，２，４)ＬＤＰＣ符号のパリティ検査行列Ｈは、８個の列と４個の行で構成されており、各列のウェイトの個数は２として均一で、各行のウェイトの個数は４として均一である。このように、パリティ検査行列内の各列のウェイトの個数と各行のウェイトの個数が均一である。したがって、図１に示している(８，２，４)ＬＤＰＣ符号は均一ＬＤＰＣ符号となる。
【００１５】
図１では、(８，２，４)ＬＤＰＣ符号のパリティ検査行列について説明する。その次に、図２を参照して、図１に示した(８，２，４)ＬＤＰＣ符号の因子グラフを説明する。
【００１６】
図２は、図１の(８，２，４)ＬＤＰＣ符号の因子グラフを示す図である。図２を参照すると、(８，２，４)ＬＤＰＣ符号の因子グラフは８個の変数ノード(ｖａｒｉａｂｌｅ ｎｏｄｅ)、すなわち、ｘ１２１１と、ｘ２２１３と、ｘ３２１５、ｘ４２１７と、ｘ５２１９と、ｘ６２２１と、ｘ７２２３と、ｘ８２２５と、４個の検査ノード２２７，２２９，２３１，２３３で構成される。（８，２，４)ＬＤＰＣ符号のパリティ検査行列のｉ番目の行とｊ番目の列が交差する地点にウェイト、すなわち、１の値を有する要素が存在する場合に、変数ノードｘｊとｉ番目の検査ノードとの間にブランチ(ｂｒａｎｃｈ)が形成される。
【００１７】
上述したように、ＬＤＰＣ符号のパリティ検査行列は、非常に少ない個数のウェイトを有するため、比較的長い長さを有するブロック符号でも反復復号を通じて復号が可能で、ブロック符号のブロック長さを継続して増加させると、ターボ符号のようにＳｈａｎｎｏｎのチャンネル容量限界に近接する形態の性能を示す。流れ伝送方式を使用するＬＤＰＣ符号の反復復号過程がターボ符号の反復復号過程にほとんど近接する性能を有する。
一方、高性能のＬＤＰＣ符号を生成するための条件を説明すると、次のようである。
【００１８】
(１)ＬＤＰＣ符号の因子グラフ上のサイクルを考慮すべきである。
サイクルとは、ＬＤＰＣ符号の因子グラフで変数ノードと検査ノードを接続するエッジが構成するループ(ｌｏｏｐ)を示すのに、サイクルの長さはループを構成するエッジの個数に定義される。サイクルの長さが長いということは、ＬＤＰＣ符号の因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が多いという意味である。その反対に、サイクルの長さが短いということは、ＬＤＰＣ符号の因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が少ないということを意味する。
【００１９】
ＬＤＰＣ符号の因子グラフ上のサイクルを長く生成するほど、ＬＤＰＣ符号の性能が増加するようになる。その理由は、次のようである。ＬＤＰＣ符号の因子グラフ上のサイクルを長く生成する場合に、ＬＤＰＣ符号の因子グラフ上に短い長さのサイクルが多く存在するときに発生する誤りフロア(ｅｒｒｏｒ ｆｌｏｏｒ）のような性能劣化が発生しないためである。
【００２０】
(２)ＬＤＰＣ符号の効率的な符号化を考慮すべきである。
ＬＤＰＣ符号は、ＬＤＰＣ符号の特性上畳み込み符号やターボ符号に比べて符号化の複雑度が高くてリアルタイム符号化が容易でない。ＬＤＰＣ符号の符号化複雑度を減少するために、反復累積(Ｒｅｐｅａｔ Ａｃｃｕｍｕｌａｔｅ：ＲＡ)符号などが提案された。反復累積符号もＬＤＰＣ符号の符号化複雑度を低下させるのに限界を有する。したがって、ＬＤＰＣ符号の効率的な符号化を考慮しなければならない。
【００２１】
(３)ＬＤＰＣ符号の因子グラフ上の次数分布を考慮すべきである。
一般的に、不均一ＬＤＰＣ符号が均一ＬＤＰＣ符号より性能が優れる。その理由は、不均一ＬＤＰＣ符号の因子グラフが多様な次数を有するためである。ここで、“次数(ｄｅｇｒｅｅ)”とは、ＬＤＰＣ符号の因子グラフ上で各ノード、すなわち変数ノードと検査ノードに接続されているエッジの個数を示す。また、ＬＤＰＣ符号の因子グラフ上の“次数分布”とは、特定次数を有するノードが全体ノードの中にどのくらい存在するかを示す。特定の次数分布を有するＬＤＰＣ符号の性能が優れるということは、既に証明したところである。
【００２２】
図３は、一般的なブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。図３の説明に先立って、ブロックＬＤＰＣ符号は、効率的な符号化だけでなく効率的なパリティ検査行列の貯蔵及び性能改善をすべて考慮した新たなＬＤＰＣ符号である。このブロックＬＤＰＣ符号は、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。図３を参照すると、ブロックＬＤＰＣ符号のパリティ検査行列は、全体パリティ検査行列を複数の部分ブロックに分割し、部分ブロックの各々に順列行列(ｐｅｒｍｕｔａｔｉｏｎ ｍａｔｒｉｘ)))を対応させる形態を有する。図３に示すように、“Ｐ”はＮｓxＮｓサイズを有する順列行列を示し、この順列行列Ｐの上付き添え字ａｉｊは０≦ａｉｊ≦Ｎｓ-１又はａｉｊ＝∞を有する。図３において、“Ｐ”は部分ブロックの行の個数を、“ｑ”は部分ブロックの列の個数を、それぞれ示す。“ｉ”は、対応する順列行列がパリティ検査行列の部分ブロックのｉ番目の行に位置することを意味し、“ｊ”は対応する順列行列がパリティ検査行列の部分ブロックのｊ番目の列に位置することを意味する。すなわち、
【００２３】
【数１】
【００２４】
は、ｉ番目の行とｊ番目の列で交差する部分ブロックに位置する順列行列である。
【００２５】
ここで、図４を参照して、上記の順列行列について説明する。
図４に示すように、循列行列ＰはＮｓxＮｓサイズを有する正方形行列として、循列行列Ｐを構成するＮｓ個の行のウェイトがそれぞれ１で、循環行列Ｐを構成するＮｓ個の行のウェイトもそれぞれ１である行列を示す。
【００２６】
一方、図３で、順列行列の上付き添え字ａｉｊ＝０である場合、すなわち、順列行列Ｐ０は単位行列
【００２７】
【数２】
【００２８】
を示し、順列行列Ｐの上付き添え字ａｉｊ＝∞である場合、すなわち順列行列Ｐ∞はゼロ行列を示す。
【００２９】
図３で、ブロックＬＤＰＣ符号の全体パリティ検査行列は、全体列の個数がＮｓxｑ(ｐ≦ｑ)で、全体行の個数がＮｓxｐであるため、ブロックＬＤＰＣ符号の全体パリティ検査行列が最大ランク(ｆｕｌｌ ｒａｎｋ)を有する場合に、部分ブロックのサイズに関係なく符号化率(ｃｏｄｉｎｇ ｒａｔｅ）は、下記の＜式１＞のようである。
【００３０】
【数３】
【００３１】
すべてのｉ、ｊに対してａｉｊ≠∞である場合に、部分ブロックの各々に対応する順列行列は、各々ゼロ行列でないことを示し、部分ブロックの各々に対応する順列行列の各行のウェイトはｐ、各列のウェイトはｑである均一ＬＤＰＣ符号となる。ここで、部分ブロックに対応する順列行列を“部分行列”と称する。
【００３２】
また、全体パリティ検査行列にはｐ-１個の従属的な(ｄｅｐｅｎｄｅｎｔ)行が存在するため、符号化率は＜式１＞で計算した符号化率より高い値を有する。このブロックＬＤＰＣ符号は、全体パリティ検査行列を構成する部分行列それぞれの１番目の行のウェイト位置が決定されると、残りのＮｓ-１個の行のウェイト位置が決定される。したがって、全体パリティ検査行列の情報を貯蔵するために、不規則にウェイトを選択する場合に比べて必要とするメモリのサイズが１/Ｎｓに縮小される。
【００３３】
図５は、一般的な均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【００３４】
図５に示すようにパリティ検査行列は、均一ブロックＬＤＰＣ符号、すなわち(ｓ，r)配列(ａｒｒａｙ)符号のパリティ検査行列である。(ｓ，r)配列符号は代表的な均一ブロックＬＤＰＣ符号として、この(ｓ，r)アレイ符号は、図３でＮｓ＝ｓで、ｑ＝ｓで、ｐ＝ｒであるブロックＬＤＰＣ符号に該当する。ここで、ｓは奇数である素数であり、ｒは常にｒ≦ｓの条件を満足する。
【００３５】
(ｓ，r)配列符号のパリティ検査行列は、ｓ２個の列とｒxｓ個の行を有し、ランクはｒx(ｓ-１)となる。ここで、(ｓ，r)配列符号のパリティ検査行列のランクがｒ(ｓ-1）となる理由は、(ｓ，r)配列符号のパリティ検査行列の行方向へのｒ個の部分行列は、この部分行列内の各々のｐ個の行をすべて加算すると、すべての要素が１の値を有する行が生成されるためである。すなわち、すべての要素が１の値を有するｒ個の行が生成されるため、ｒ個の従属である行が存在することが分かる。したがって、(ｓ，r)配列符号の符号化率Ｒａｒｒａｙは、下記の＜式２＞のように示す。
【００３６】
【数４】
【００３７】
上記に説明したように、(ｓ，r)配列符号は、その代数的(ａｌｇｅｂｒａｉｃ)な特性から長さが４のサイクルが因子グラフ上に存在しないことがわかり、またメモリ容量も減少させることができる。
【００３８】
しかしながら、(ｓ，r)配列符号は、均一ＬＤＰＣブロック符号であるため、不均一ＬＤＰＣ符号に比べては性能劣化が発生する。また、ブロックＬＤＰＣ符号の場合に、ブロックＬＤＰＣ符号自体のランダムな性質(ｒａｎｄｏｍｎｅｓｓ）が低いため、優れた性能を保障することができない。つまり、(ｓ，r)配列符号は、効率的な符号化を考慮したものであるが、符号化において複雑度は相変わらず高く、長さ４のサイクルが存在しないが、長さ６のサイクルは存在する。次数分布を考慮しないため、性能面で劣化が発生する。
【００３９】
図６は、一般的な不均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。図６の説明に先立って、不均一ブロックＬＤＰＣ符号は、図５に説明したように、配列符号を効率的な符号化を考慮して変形した形態のブロックＬＤＰＣ符号である。図６において、不均一ブロックＬＤＰＣ符号のパリティ検査行列でｋ、ｒはｋ，ｒ≦ｓの条件を満たす整数で(但し、ｓは素数)、Ｉはｓxｓサイズの単位行列を示し、０はｓxｓサイズのゼロ行列を示す。図６に示すように、不均一ブロックＬＤＰＣ符号のパリティ検査行列は、図３でＮｓ＝ｓで、ｑ＝ｋで、ｐ＝ｒのブロックＬＤＰＣ符号のパリティ検査行列に該当する。
【００４０】
一方、ＬＤＰＣ符号の効率的な符号化のために、図６のように全体パリティ検査行列の中でパリティに該当する部分行列を完全下三角行列で構成して線形時間内で符号化が可能にした。全体パリティ検査行列の構造、すなわち情報語に該当する部分行列と、パリティに該当する部分行列構造は下記で説明するため、ここではその詳細な説明を省略する。このようにパリティに該当する部分行列を完全下三角行列で構成する場合に、パリティ検査行列の構造的な特性によってパリティ検査行列は常に最大ランクを有するようになる。そのため、変形された配列符号、すなわち不均一ＬＤＰＣ符号のブロック長さはｋｓとなり、符号化率Ｒは下記の＜式３＞のように示す。
【００４１】
【数５】
【００４２】
しかしながら、図６のようにパリティに該当する部分行列が完全下三角行列形態を有するパリティ検査 行列を有する不均一ＬＤＰＣ符号は、配列符号に比べては符号化面で一層効率的であるが、ＬＤＰＣ符号の生成時に考慮すべき因子グラフ上の次数分布を考慮せず、また長さの短いサイクルに対する除去もやはり考慮しなかった。そのため、ランダムな特性をを有する不均一ＬＤＰＣ符号に比べては低い誤り訂正能力を有する。したがって、誤り訂正能力を最大化する不均一ＬＤＰＣ符号に対する必要性が増大されている。
【発明の開示】
【発明が解決しようとする課題】
【００４３】
したがって、本発明の目的は、移動通信システムで誤り訂正能力を最大化するＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【００４４】
本発明の他の目的は、移動通信システムで最小サイクル長さが最大になるＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【００４５】
また本発明の目的は、移動通信システムで符号化の複雑度が最小化されたＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【課題を解決するための手段】
【００４６】
上記した目的を達成するための方法において、本発明は、ブロック低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：ＬＤＰＣ)符号のパリティ検査行列が情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に基づいて前記パリティ検査行列のサイズを決定する段階と、前記決定されたサイズのパリティ検査行列を予め定められた個数のブロックに分割する段階と、前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類する段階と、前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形態で順列行列を配列する段階と、前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一になるように前記順列行列を配列する段階と、を有することを特徴とする。
【００４７】
また、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号方法であって、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を生成し、前記パリティ検査行列に対応してデインタリービング方式及びインタリービング方式を決定する段階と、受信信号の確率値を検出する段階と、前記受信信号の確率値から以前復号時に生成された信号を減算して第１の信号を生成する段階と、前記第１の信号を入力して前記デインタリービング方式でデインタリービングする段階と、前記デインタリービングされた信号を入力して確率値を検出する段階と、前記デインタリービングされた信号の確率値で前記デインタリービングされた信号を減算して第２の信号を生成する段階と、前記第２の信号を前記インタリービング方式でインタリービングし、前記インタリービングされた信号を反復復号する段階と、を含むことを特徴とする。
【００４８】
なお、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化方法であって、情報語と予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算して第１の信号を生成する段階と、前記情報語と前記パリティ検査行列の第２の部分行列と乗算して第２の信号を生成する段階と、前記第１の信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第３の信号を生成する段階と、前記第２の信号と第３の信号を加算して第４の信号を生成する段階と、前記第４の信号と前記パリティ検査行列の第５の部分行列を乗算して第５の信号を生成する段階と、前記第２の信号と前記第５の信号を加算して第６の信号を生成する段階と、前記第６の信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第７の信号を生成する段階と、前記情報語と、前記第４の信号を第１のパリティで、前記第７の信号を第２のパリティとし、前記ブロックＬＤＰＣ符号フォーマットに対応するように多重化して出力する段階と、を有することを特徴とする。
【００４９】
本発明は、パリティ検査行列は、複数の情報部分ブロックと複数のパリティ部分ブロックの行と列の行列形態で配列され、前記パリティ検査行列は前記情報部分ブロックの行列で構成された情報部分と前記パリティ部分ブロックの行列で構成されたパリティ部分に区分され、前記情報部分ブロックの各々は複数の情報ビットを示す行列で構成され、前記パリティ部分ブロックの各々は、複数のパリティビットを示す行列で構成され、前記パリティ検査行列は複数の行に存在する情報部分ブロックとパリティ部分ブロックが各々第１の情報行列と第１のパリティ行列及び第２のパリティ行列に分割され、前記複数の行を除いた残りの行に存在する情報部分ブロックとパリティ部分ブロックが各々第２の情報行列と第３のパリティ行列及び第４のパリティ行列に分割され、前記第１及び第２の情報行列と、第１及び第３のパリティ行列と、第２及び第４のパリティ行列は各々同一の列に配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記第４のパリティ行列と第２のパリティ行列の逆行列と前記第１のパリティ行列の積と前記第３のパリティ行列の和が単位行列になるように設定する段階と、前記第１のパリティ行列と前記第３のパリティ行列に対応する第１のパリティベクトルの転置ベクトルは、前記第４のパリティ行列と前記第２のパリティ行列の逆行列と前記第１の情報行列の積と前記第２の情報行列の和を前記第１の情報行列と前記第２の情報行列に対応する情報ベクトルを乗算した値になるように決定する段階と、前記第２のパリティ行列と第４のパリティ行列に対応する第２のパリティベクトルの転置ベクトルは、前記第２のパリティ行列の逆行列と前記第１の情報行列と前記情報ベクトルの転置ベクトルを乗算した値と前記第１のパリティ行列と前記第１のパリティベクトルの転置ベクトルを乗算した値を加算した値を乗算した値になるように決定する段階と、を有することを特徴とする。
【００５０】
さらに、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号のパリティ検査行列は、複数の部分ブロックの行と列の行列形態で配列され、前記複数の部分ブロック各々にはＮｓxＮｓサイズを有する行列が前記複数の部分ブロックの各々に対応して予め定められた指数だけシフトして生成された順列行列が配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記ブロックＬＤＰＣ符号のブロックサイクルを任意の第１の値に決定する段階と、前記ブロックサイクルを決定した後に、前記部分ブロックの各々に配列された順列行列の中に、その指数が奇数である順列行列の指数の和から前記部分ブロックの各々に配列された順列行列のうち、その指数が偶数である順列行列の指数の和を減算した値と任意の第２の値を乗算した値になるように前記第２の値を決定し、前記部分ブロックの各々が前記第１の値と第２の値を乗算した値に対応するサイクルを有するように制御する段階と、を有することを特徴とする。
【００５１】
上記の目的を達成するための装置において、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号装置であって、所定の制御により、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、前記変数ノード復号器から出力された信号から以前復号時に生成された信号を減算して出力する第１の加算器と、前記第１の加算器から出力された信号を入力して前記パリティ検査行列に対応して設定されたデインタリービング方式でデインタリービングして出力するデインタリーバと、所定の制御信号により、前記パリティ検査行列を構成する行のそれぞれのウェイトに対応して検査ノードを接続し、前記デインタリーバからの出力信号の確率値を検出して出力する検査ノード復号器と、前記検査ノード復号器の出力信号から、前記デインタリーバから出力された信号を減算する第２の加算器と、前記第２の加算器から出力された信号を前記パリティ検査行列により設定されたインタリービング方式でインタリービングして前記変数ノード復号器及び前記第１の加算器に出力するインタリーバと、前記パリティ検査行列を生成し、前記デインタリービング方式及びインタリービング方式を前記パリティ検査行列に対応して制御する制御器と、を含むことを特徴とする。
【００５２】
また、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化装置であって、情報語を入力して予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算する第１の行列乗算器と、前記情報語を入力して前記パリティ検査行列の第２の部分行列と乗算する第２の行列乗算器と、前記第１の行列乗算器から出力された信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第３の行列乗算器と、前記第２の行列乗算器から出力された信号と第３の行列乗算器から出力された信号とを加算する第１の加算器と、前記第１の加算器から出力された信号と前記パリティ検査行列の第５の部分行列とを乗算する第４の行列乗算器と、前記第２の行列乗算器から出力された信号と前記第４の行列乗算器から出力された信号とを加算する第２の加算器と、前記第２の加算器から出力された信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第５の行列乗算器と、前記情報語と、前記第１の加算器の出力信号を第１のパリティとし、前記第５の行列乗算器の出力信号を第２のパリティとして前記ブロックＬＤＰＣ符号フォーマットに相応するように多重化して出力するスイッチと、を含むことを特徴とする。
【発明の効果】
【００５３】
本発明は、移動通信システムで最小サイクル長さが最大になるブロックＬＤＰＣ符号を提案することによって、誤り訂正能力を最大化させてシステム性能を向上させる効果を有する。また、本発明は、効率的なパリティ検査行列を生成することによって、ブロックＬＤＰＣ符号の符号化複雑度を最小化させる効果も有する。
【発明を実施するための最良の形態】
【００５４】
以下、本発明の望ましい実施形態を添付の図面を参照して詳細に説明する。
下記の説明で、本発明に関連した公知の機能又は構成に関する説明が本発明の要旨を不明にすると判断された場合に、その詳細な説明を省略する。
【００５５】
本発明は、優秀な性能の不均一低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：以下、“ＬＤＰＣ”とする)符号を符号化及び復号化する方案を提示する。すなわち、本発明は、因子(ｆａｃｔｏｒ)グラフ上の最小サイクルの長さが最大になり、符号化複雑度が最小になり、因子グラフ上の次数分布が最適化される分布を有する不均一ＬＤＰＣ符号の符号化及び復号化方案を提示する。
【００５６】
ＬＤＰＣ符号の因子グラフ上のサイクルとは、因子グラフで変数ノードと検査ノードを接続するエッジ(ｅｄｇｅ)によって構成されるループを示すが、サイクルの長さはループを構成するエッジの個数に定義される。サイクルの長さが長いということは、因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が多いことを示す。因子グラフ上のサイクルの長さを長く生成するほど、ＬＤＰＣ符号の性能が向上するようになる。その反面、因子グラフ上に長さの短いサイクルが多く存在するほどＬＤＰＣ符号は誤りフロア(ｅｒｒｏｒ ｆｌｏｏｒ）の性能劣化が示すため、誤り訂正能力が低下する。すなわち、因子グラフ上に長さの短いサイクルが多く存在する場合に、長さの短いサイクルに属している任意のノードから出発した自分の情報が少ない反復回数を経てまた帰ってくるようになり、反復回数が増加するほど、その情報が継続して自分に帰って来るようになる。したがって、情報アップデートがよくなされなくて、結局、ＬＤＰＣ符号の誤り訂正能力が低下される。
【００５７】
図７は、パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【００５８】
図７を説明するに先立ち、ブロックＬＤＰＣ符号は効率的な符号化だけでなく効率的なパリティ検査行列の貯蔵及び性能の改善をすべて考慮した新たなＬＤＰＣ符号である。このブロックＬＤＰＣ符号は、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。図７に示すように、ブロックＬＤＰＣ符号のパリティ検査行列は、４個のブロックで構成され、斜線は１の値を有する要素(ｅｌｅｍｅｎｔ)が存在する位置を意味し、死線部分以外の部分はすべて０の値を有する要素が存在する位置を意味する。また、Ｐは、従来技術の図４で説明した順列行列(ｐｅｒｍｕｔａｔｉｏｎ ｍａｔｒｉｘ）と同一の順列行列を示す。ここで、順列行列Ｐは、図４で説明したように、ＮｓxＮｓサイズを有する正方形行列で、この順列行列Ｐを構成するＮｓ個の行のそれぞれのウェイトが１であり、Ｎｓ個の行のそれぞれのウェイトも１である行列を示す。ここで、“ウェイト”とは、パリティ検査行列を構成する要素のうち、０でない値を有する要素の個数を示す。
【００５９】
図７に示すブロックＬＤＰＣ符号のサイクル構造を分析するために、部分行列Ｐａのｉ番目の行に位置する１の値を有する要素を基準として定め、ｉ番目の行に位置する１の値を有する要素を“０-ポイント”と称する。ここで、“部分行列”は、部分ブロックに対応する行列を示す。すると、０-ポイントは部分行列Ｐａの(i＋ａ)番目の列に位置される。
【００６０】
０-ポイントと同一の行に位置した部分行列Ｐｂでの１の値を有する要素を“１-ポイント”と称する。この０-ポイントと同じ理由で、１-ポイントは部分行列Ｐｂの(ｉ＋ｂ)番目の列に位置する。
【００６１】
次に、１-ポイントと同一の列に位置した部分行列Ｐｃでの１の値を有する要素を“２-ポイント”と称する。部分行列Ｐｃが単位行列Ｉの列の各々を右にモジューロ(ｍｏｄｕｌｏ)Ｎｓに対してｃだけ移動して得られた行列であるため、２-ポイントはこの部分行列Ｐｃの(ｉ＋ｂ−ｃ)番目の行に位置するようになる。
【００６２】
また、２-ポイントと同じ行に位置した部分行列Ｐｄでの１の値を有する要素を“３-ポイント”と称する。３-ポイントは、部分行列Ｐｄでの(i＋ｂ-ｃ＋ｄ)番目の列に位置するようになる。
【００６３】
最後に、３-ポイントと同一の列に位置した部分行列Ｐａでの１の値を有する要素を“４-ポイント”と称する。この４-ポイントは、部分行列Ｐａの(ｉ＋ｂ-ｃ＋ｄ-ａ)番目の行に位置するようになる。
【００６４】
図７に示すＬＤＰＣ符号のサイクル構造で、長さが４であるサイクルが存在すると、０-ポイントと４-ポイントは相互に同一の位置となる。すなわち、０-ポイントと４-ポイントとの間には、下記の＜式４＞のような関係が成立するようになる。
【００６５】
【数６】
【００６６】
そして、上記の＜式４＞をさらに整理すると、下記の＜式５＞のようである。
【００６７】
【数７】
【００６８】
その結果、＜式５＞のような関係が成立するときに、長さ４のサイクルが生成される。一般的に、０-ポイントと４ｍ-ポイントが最初に同一になる場合は、ｉ≡ｉ＋ｍ(ｂ-ｃ＋ｄ-ａ)関係が成立され、下記の＜式６＞のような関係が成立される。
【００６９】
【数８】
【００７０】
さらに説明すると、与えられたａ、ｂ、ｃ、ｄに対して＜式６＞を満たす正の整数の中で最小値を有する正の整数をｍとする場合に、図７に示すようなブロックＬＤＰＣ符号のサイクル構造では長さが４ｍであるサイクルが最小長さを有するサイクルとなる。
【００７１】
結果的に、上記したように、(ａ-ｂ＋ｃ-ｄ)≠０である場合にｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ)＝１を満たすと、ｍ＝Ｎｓになる。ここで、ｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ)は、整数Ｎｓとａ-ｂ＋ｃ-ｄの最大公約数の計算のための機能をする。したがって、長さが４Ｎｓであるサイクルが最小長さを有するサイクルとなる。
【００７２】
図７に説明したように、ブロックＬＤＰＣ符号のサイクルに関する分析は、ブロックＬＤＰＣ符号のパリティ検査行列を構成するブロックの個数が４を超える場合、すなわちパリティ検査行列を構成する部分行列の個数が４を超える場合にも適用可能である。ここで、図８を参照して、パリティ検査行列を構成する部分行列の個数が４を超える場合のＬＤＰＣ符号のサイクル構造について説明する。
【００７３】
図８は、パリティ検査行列が６個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【００７４】
図８に示すブロックＬＤＰＣ符号のパリティ検査行列は、６個のブロックで構成されており、図７で説明したように、斜線は１の値を有する要素が存在する位置を示し、この斜線部分以外の部分はすべて０の値を有する要素が存在する位置を示す。また、Ｐも従来技術である図４で説明した順列行列と同一の順列行列を示す。図７で説明したような方法で、図８におけるブロックＬＤＰＣ符号のサイクル構造を分析すると、長さが６ｍであるサイクルが最小長さを有するサイクルとなる。
【００７５】
一般的に、０-ポイントと６ｍ-ポイントが最初に同一になる場合は、ｉ≡ｉ＋ｍ(ｂ-ｃ＋ｄ-ｅ＋ｆ-ａ)(ｍｏｄ Ｎｓ)の関係が成立され、下記の＜式７＞のような関係を満たすようになる。
【００７６】
【数９】
【００７７】
これら与えられたａ、ｂ、ｃ、ｄ、ｅ、ｆに対して＜式７＞を満たす正の整数の中で、最小値を有する正の整数を“ｍ”とすると、図８に示すブロックＬＤＰＣ符号のサイクル構造では長さが６ｍであるサイクルが最小長さを有するサイクルになる。
【００７８】
上記に述べたように、(ａ-ｂ＋ｃ-ｄ＋ｅ-ｆ)≠０である場合にｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ＋ｅ-ｆ)＝１を満たすと、ｍ＝Ｎｓになる。したがって、長さが６Ｎｓであるサイクルが最小長さを有するサイクルになる。
【００７９】
上記に説明したように、ブロックＬＤＰＣ符号について、次のような規則が推定可能である。
【００８０】
<規則１>
ブロックＬＤＰＣ符号で長さが２lであるサイクルが存在すると、下記の＜式８＞の条件を満たすべきである。
【００８１】
【数１０】
【００８２】
＜式８＞ｄ、ａｉ(ｉ＝１，２，…，２１)は長さが２lであるサイクルが順次的に通過する順列行列の指数を示す。すなわち、ブロックＬＤＰＣ符号のパリティ検査行列を構成する部分ブロックに対して長さが２lであるサイクルが
【００８３】
【数１１】
【００８４】
の順に通過することを示す。ここで、すべてのａｉが相互に異なる必要はなく、重複的に通過する部分ブロックが存在することも可能であることはもちろんである。
【００８５】
<規則２>
ｍは、下記の＜式９＞を満たす最小の正の整数であると定義する。
【００８６】
【数１２】
【００８７】
＜式９＞で、ａｉは、全体パリティ検査行列でブロック単位のサイクルが形成されるように適切に選択された順列行列の指数である。そして、ａｉは＜規則１＞の説明と同様に、すべて相互に異なる必要はなく、重複的に通過する部分ブロックが存在することも可能であることはもちろんである。つまり、部分行列
【００８８】
【数１３】
【００８９】
は最小長さが２lｍであるサイクル構造を有する。
【００９０】
＜規則１＞と＜規則２＞を用いると、ブロックＬＤＰＣ符号のサイクル構造の特性を分析することが容易になる。一例として、＜規則１＞と＜規則２＞を用いると、配列符号で最小長さが６であるサイクルが正確にどのくらい分布しているかが分かるだけでなく、下記で説明するブロックＬＤＰＣ符号のブロック単位のサイクル(以下、“ブロックサイクル”と称する)構造の特性分析も容易になる。ここで、ブロックサイクルは、パリティ検査行列の構成において、サイクル長さを調整するのに重要な要素であり、ブロックサイクルを図９及び＜規則１＞と＜規則２＞を使用して説明する。
【００９１】
図９は、ブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図９を参照すると、ブロックＬＤＰＣ符号を構成するブロックの各々がウェイト１を有すると仮定し、このブロックがサイクルを構成する場合に“ブロックサイクルを構成する”と定義する。図９には、左側から４個のブロックで構成されたブロックサイクルと、６個のブロックで構成されたブロックサイクルと、８個のブロックで構成されたブロックサイクルが示している。そして、＜規則１＞と＜規則２＞で説明したように、短い長さのブロックサイクルが構成されるとしてもブロックサイクルを構成するブロックの各々に該当する部分行列を適切に選択するようになると、実際のパリティ検査行列では短い長さのサイクルが生成されないように制御できる。しかしながら、ブロックＬＤＰＣ符号で複数のブロックサイクルが重複される場合は、ブロックサイクル内の実際のサイクルの最小長さが減少される。その結果、実際のパリティ検査行列で短い長さのサイクルが生成されるという問題点が発生する。
【００９２】
ここで、図１０及び＜規則１＞と＜規則２＞を用いてブロックＬＤＰＣ符号で複数のブロックサイクルが重複される問題点について説明する。また、ブロックＬＤＰＣ符号のパリティ検査行列を生成するときに、重複されたブロックサイクルを避けるべき理由についても説明する。
【００９３】
図１０は、パリティ検査行列の６個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図１０に示している矢印に従って、次のような順次的なブロック順序を考慮することができる。
【００９４】
【数１４】
【００９５】
順次的なブロック順序による部分行列の指数は、Ｎｓの値に関係なく下記の＜式１０＞の条件を常に満たす。
【００９６】
【数１５】
【００９７】
＜式１０＞を＜規則２＞で説明した＜式９＞に適用させると、ｍ＝１となる。したがって、図１０に示すような６個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、全体パリティ検査行列を構成するいずれの部分行列を選択しても、常にその長さが１２であるサイクル構造を含むようになる。すなわち、図１０に示すような６個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、パリティ検査行列の最小サイクル長さは最大１２に制限されるものである。
【００９８】
図１１は、パリティ検査行列の７個の部分ブロックが重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図１１に示している矢印に従って、次のような順次的なブロック順序を考慮することができる。
【００９９】
【数１６】
【０１００】
順次的なブロック順序による部分行列の指数は、Ｎｓの値に関係なく下記の＜式１１＞の条件を常に満たす。
【０１０１】
【数１７】
【０１０２】
＜式１１＞を＜規則２＞で説明した＜式９＞に適用すると、ｍ＝１となる。したがって、図１１に示すようなパリティ検査行列の７個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、全体パリティ検査行列を構成するいずれの部分行列を選択しても、常にその長さが１４であるサイクル構造を含む。すなわち、図１１に示すように、パリティ検査行列の７個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、パリティ検査行列の最小サイクル長さは最大１４に制限される。
【０１０３】
上述したように、ブロックＬＤＰＣ符号でパリティ検査行列を構成するブロックの間にブロックサイクルが多く重複されている場合に、パリティ検査行列の部分行列を選択する方法に関係なく、サイクルの最小長さをを最大化するのに制限が発生してその性能が劣化することが分かる。したがって、ブロックＬＤＰＣ符号でパリティ検査行列を生成する場合に、できるだけブロックサイクル自体を少なく生成して重複ブロックサイクルが発生しないように考慮しなければならない。
【０１０４】
次に、ブロックサイクル以外に効率的な符号化を考慮してブロックＬＤＰＣ符号のパリティ検査行列を生成する方法について説明する。
【０１０５】
本発明では、ブロックＬＤＰＣ符号の符号化方式としてＲｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式を使用することにする。このＲｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式を符号化方式で使用するため、パリティ検査行列は完全下三角行列と類似した形態を有するほど符号化の複雑度も最小化させることができる。
【０１０６】
図１２は、完全下三角行列形態を有するパリティ検査行列を示す図である。
【０１０７】
図１２に示すように、パリティ検査行列は、完全下三角行列形態を有し、情報部分(ｉｎｆｏｒｍａｔｉｏｎ ｐａｒｔ)とパリティ部分(ｐａｒｉｔｉｅｓ ｐａｒｔ）で構成される。ここで、情報部分は、ブロックＬＤＰＣ符号を符号化する過程で、実際の情報語にマッピングされるパリティ検査行列の部分を示し、パリティ部分はブロックＬＤＰＣ符号を符号化する過程で実際パリティにマッピングされるパリティ検査行列の部分を示す。パリティ部分は、図１２に示すように、単位行列Ｉに基づいて０行列と部分行列が存在し、部分行列が完全下三角形態を有する。
【０１０８】
図１３は、完全下三角行列形態と類似した形態を有するパリティ検査行列を示す図である。図１３に示すように、パリティ検査行列が、図１２に示した完全下三角行列形態のパリティ検査行列に比べてはパリティ部分の形態が完全下三角行列形態から外れる。図１３において、情報部分の順列行列Ｐの上付き添え字ａｉｊは０≦ａｉｊ≦Ｎｓ-１又はａｉｊ＝∞である。この順列行列Ｐの上付き添え字ａｉｊ＝０である場合、すなわち順列行列Ｐ０は単位行列
【０１０９】
【数１８】
【０１１０】
を示し、順列行列Ｐの上付き添え字ａｉｊ＝∞である場合、すなわち順列行列Ｐ∞はゼロ行列を示す。図１３で、“ｍ”は情報部分にマッピングされる部分ブロックの行の個数を、“ｑ”はパリティ部分にマッピングされる部分ブロックの列の個数を、それぞれ示す。“ｉ”は、対応する順列行列がパリティ検査行列の部分ブロックのｉ番目の行に位置することを意味し、“ｊ”は対応する順列行列がパリティ検査行列の部分ブロックのｊ番目の列に位置することを意味する。すなわち、
【０１１１】
【数１９】
【０１１２】
は、ｉ番目の行とｊ番目の列で交差する部分ブロックに位置する順列行列である。
また、上記のパリティ部分の順列行列の上付き添え字ａｉ、ｘ、ｙは、順列行列Ｐの指数(上付き添え字)を示し、但し、説明の便宜上、このａｉ、ｘ、ｙは情報部分との区分のために相互に異なるように設定しただけである。すなわち、図１３で、
【０１１３】
【数２０】
【０１１４】
も順列行列で、パリティ部分の対角部分に位置する。上付き添え字ａ１〜ａｍは部分行列に順次にインデックスが付けられることを示す。図１３で、ｐｘとｐｙも順列行列で、説明の便宜上、情報部分との区分のために相互に異なるように設定して示す。
【０１１５】
図１３に示すようなパリティ検査行列を有するブロックＬＤＰＣ符号のブロック長さをＮであると仮定すると、ブロックＬＤＰＣ符号の符号化複雑度はブロック長さＮに対して線形的に増加する。
【０１１６】
図１３のパリティ検査行列を有するＬＤＰＣ符号の一番大きい問題点は、部分ブロックの長さがＮｓであるときに、ブロックＬＤＰＣ符号の因子グラフ上に常に次数(ｄｅｇｒｅｅ)が１であるＮｓ個の検査ノードが生成されることである。ここで、次数が１である検査ノードは、反復復号による性能改善に影響を与えることができない。したがって、Ｒｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式に基づいた標準ＬＤＰＣ符号は、次数が１である検査ノードを含んでいない。したがって、次数が１である検査ノードを含まずに効率的な符号化が可能なようにパリティ検査行列を設計するために、図１３のパリティ検査行列を基本的なパリティ検査行列として仮定する。図１３のように、部分行列で構成されたパリティ検査行列で部分行列の選択は、ブロックＬＤＰＣ符号の性能改善において非常に重要な要素で、したがって部分行列の適切な選択基準を探すことも非常に重要な要素となる。
【０１１７】
したがって、ブロックＬＤＰＣ符号の生成において、次のような設計基準を考慮してパリティ検査行列を構成する。
【０１１８】
＜ブロックＬＤＰＣ符号のパリティ検査行列の設計基準＞
【０１１９】
(１)パリティ部分は固定された形態を有するように構成される。
パリティ部分が固定された形態を有するということは、後術する図１６に示すように単位行列が位置する形態を有することを意味する。
【０１２０】
(２)優先的に次数の低い部分行列から順次的に選択する。
本発明で、部分行列の“次数”とは、３と５との間の次数を呼ばれる。また、部分行列は、次数の低い部分行列から順次に選択するときに、ブロックサイクルができるだけ少なく生成されるように配列し、次数の低い部分行列間の最小長さを有するサイクルをできるだけ長く構成する。
【０１２１】
(３)次数の低い部分行列をすべて構成した後に、次数の高い部分行列を順次に構成する。次数の高い部分行列を配列するときに、できるだけ全体的に最小長さのサイクルを長く構成する。
【０１２２】
上記したブロックＬＤＰＣ符号のパリティ検査行列設計基準に基づいて、ブロックＬＤＰＣ符号のパリティ検査行列の設計方法を説明する。
【０１２３】
ここで、ブロックＬＤＰＣ符号のパリティ検査行列の設計方法とブロックＬＤＰＣ符号の符号化方法を容易にするために、図１３に示すようなパリティ検査行列を図１４のように６個の部分行列で構成された形態であると仮定する。
【０１２４】
図１４は、図１３のパリティ検査行列を６個の部分ブロックに分割した図である。図１４を参照すると、図１３に示したように、ブロックＬＤＰＣ符号のパリティ検査行列を情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分ブロックに分割する。ここで、情報部分は、図１２及び図１３で説明した情報部分のようにブロックＬＤＰＣ符号を符号化する過程で、実際の情報語にマッピングされるパリティ検査行列の部分を示し、但し、説明の便宜上、情報部分ｓは参照符号を異にして表示しただけである。また、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２は、図１２及び図１３に説明したパリティ部分のようにブロックＬＤＰＣ符号を符号化する過程で、実際のパリティにマッピングされるパリティ検査行列の部分を示し、パリティ部分を２個の部分に分割した。
【０１２５】
部分行列Ａ、Ｃは情報部分ｓの部分ブロック、すなわち部分ブロックＡ、Ｃに対応し、部分行列Ｂ、Ｄは第１のパリティ部分ｐ１の部分ブロックＢ、Ｄに対応し、部分行列Ｔ、Ｅは第２のパリティ部分ｐ２の部分ブロックＴ、Ｅに対応する。ここで、図１４にパリティ検査行列が７個の部分ブロックに分割されるように示しているが、‘０’は別途の部分ブロックでなく、部分ブロックＴに対応する部分行列Ｔが完全下三角形態を有するため、対角線を中心としてゼロ行列が配置された領域を‘０’で表示する。情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分行列を用いて符号化方法を簡略にする過程は、下記の図１７で説明する。
【０１２６】
以下に、図１４の部分行列は、図１５を参照して説明する。
【０１２７】
図１５は、図１４の部分行列Ｂの転置行列と、部分行列Ｅと、部分行列Ｔと、部分行列Ｔの逆行列を示す図である。図１５を参照すると、
【０１２８】
【数２１】
【０１２９】
を示す。また、図１５に示す順列行列、例えば、
【０１３０】
【数２２】
【０１３１】
は単位行列となりうる。上記したように、順列行列の指数、すなわちａ１が０である場合には、順列行列
【０１３２】
【数２３】
【０１３３】
が単位行列となる。また、順列行列の指数、すなわち、ａ１が予め設定された値により増加する場合には、順列行列が増加した設定値により循環シフトされ、つまり、順列行列
【０１３４】
【数２４】
【０１３５】
が単位行列になる。
【０１３６】
図１７は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列の生成過程を示すフローチャートである。図１７の説明に先立って、ブロックＬＤＰＣ符号を生成するためには、生成しようとするブロックＬＤＰＣ符号の符号語サイズと符号化率を決定し、この決定された符号語サイズと符号化率によりパリティ検査行列のサイズを決定すべきである。ブロックＬＤＰＣ符号の符号語サイズがＮで、符号化率をＲであると仮定すると、パリティ検査行列のサイズはＮ(１-Ｒ)xＮとなる。また、図１７に示すようにブロックＬＤＰＣ符号のパリティ検査行列生成過程は、最初に通信システムのシステム状態に応じて生成され、この生成されたパリティ検査行列を用いることによって、実質的にパリティ検査行列の生成過程は１回のみを遂行すると良い。
【０１３７】
図１７を参照すると、制御器は、ステップ１７１１で、サイズＮ(１-Ｒ)xＮのパリティ検査行列を横軸にｐ個のブロックに分割し、縦軸でｑ個のブロックに分割して総ｐxｑブロックに分割した後に、ステップ１７１３に進行する。ここで、ブロックそれぞれのサイズはＮｓxＮｓであるため、パリティ検査行列はＮｓxｑ個の行と、Ｎｓxｐ個の列で構成される。ステップ１７１３で、制御器は、ｐｘｑ個のブロックに分割したパリティ検査行列を情報部分ｓとパリティ部分、すなわち第１のパリティ部分ｐ１と第２のパリティ部分ｐ２に分類し、ステップ１７１５及びステップ１７２１に進行する。
【０１３８】
ステップ１７１５で、制御器は、情報部分ｓをブロックＬＤＰＣ符号の高性能を保障する次数分布による‘０’でないブロック又は非ゼロ行列、‘０’であるブロック又はゼロ行列であるブロックを決定し、ステップ１７１７に進行する。ここで、ブロックＬＤＰＣ符号の高性能を保障する次数分布は上記したようであるため、その詳細な説明を省略する。ステップ１７１７で、制御器は、ブロックＬＤＰＣ符号の高性能を保障する次数分布により決定したブロックの中に低い次数を有するブロックのうち、非ゼロ行列部分に上記したようにブロックサイクルの最小サイクル長さが最大になるように順列行列
【０１３９】
【数２５】
【０１４０】
を決定し、ステップ１７１９に進行する。ここで、順列行列
【０１４１】
【数２６】
【０１４２】
を決定するとき、情報部分ｓだけでなく第１及び第２のパリティ部分Ｐ１、Ｐ２のブロックサイクルも考慮して決定すべきである。
【０１４３】
ステップ１７１９で、制御器は、ブロックＬＤＰＣ符号の優れた性能を保障する次数分布により決定されたブロックの中に、高い次数を有するブロックのうちの非ゼロ行列部分にランダムに順列行列
【０１４４】
【数２７】
【０１４５】
を決定して終了する。ここで、高い次数を有するブロックのうちの非ゼロ行列部分に適用する順列行列
【０１４６】
【数２８】
【０１４７】
を決定するときにも、ブロックサイクルの最小サイクルサイズが最大になるように順列行列
【０１４８】
【数２９】
【０１４９】
を決定すべきである。また、情報部分ｓだけでなく第１のパリティ部分ｐ１と第２のパリティ部分ｐ２のブロックサイクルも考慮して決定すべきである。上記のように、パリティ検査行列の情報部分ｓに順列行列
【０１５０】
【数３０】
【０１５１】
を配列した形態を図１６に示す。
【０１５２】
ステップ１７２１で、制御器は、第１及び第２のパリティ部分ｐ１、ｐ２を４個の部分行列Ｂ、Ｔ、Ｄ、Ｅに分割した後に、ステップ１７２３に進行する。ステップ１７２３で、制御器は、部分行列Ｂを構成する部分ブロックの中に２個の部分ブロックに０でない順列行列Ｐｙと
【０１５３】
【数３１】
【０１５４】
を入力し、ステップ１７２５に進行する。ここで、部分行列Ｂを構成する部分ブロックの中に２個の部分ブロックに０でない順列行列Ｐｙと
【０１５５】
【数３２】
【０１５６】
を入力する構造は、既に図１５を参照して説明した。
【０１５７】
ステップ１７２５で、制御器は、部分行列Ｔの対角部分ブロックには単位行列Ｉを入力し、部分行列Ｔの対角成分の下に(ｉ，ｉ＋１)番目の部分ブロックには任意の順列行列
【０１５８】
【数３３】
【０１５９】
を入力し、ステップ１７２７に進行する。ここで、部分行列Ｔの対角部分ブロックには単位行列Ｉを入力し、この部分行列Ｔの対角成分の下の(ｉ，ｉ＋１)番目の部分ブロックには任意の順列行列
【０１６０】
【数３４】
【０１６１】
を入力する方法は、図１５を参照して説明した。
【０１６２】
ステップ１７２７で、制御器は、部分行列Ｄに順列行列Ｐｘを入力した後に、ステップ１７２９に進行する。ステップ１７２９で、制御器は、部分行列Ｅには最後の部分ブロックのみに
【０１６３】
【数３５】
【０１６４】
を入力して終了する。ここで、部分行列Ｅを構成する部分ブロックの中に最後の部分ブロックに２個の
【０１６５】
【数３６】
【０１６６】
を入力する構造は、既に図１５を参照して説明した。
【０１６７】
ブロックＬＤＰＣ符号のパリティ検査行列で、部分行列Ｂと、部分行列Ｄ、及び部分行列Ｅを適切に構成すると、ブロックＬＤＰＣ符号の符号化過程を容易に制御することができる。ここで、ブロックＬＤＰＣ符号の符号化過程を容易にするために、パリティ検査行列の部分行列Ｂと、部分行列Ｄ、及び部分行列Ｅを構成する過程について説明する。
【０１６８】
上記に説明したように、図１３のパリティ検査行列を図１４に説明したような部分行列に分割する場合に、図１５のように示すことができる。
【０１６９】
符号語ベクトルｃは図１４に示すように情報部分ｓと、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２に分割する場合に、符号語ベクトルｃは、情報語ベクトルｓ と、第１のパリティベクトルＰ1と、第２のパリティベクトルＰ2に分割可能である。この場合、パリティ検査行列と符号語ベクトルｃの積は、下記の＜式１２＞及び＜式１３＞のように示す。
【０１７０】
【数３７】
【数３８】
【０１７１】
＜式１２＞で、Ｔは転置(ｔｒａｎｓｐｏｓｅ)演算を示し、＜式１３＞で第１のパリティベクトルＰ1と関連した部分、すなわち
【０１７２】
【数３９】
【０１７３】
は下記の＜式１４＞を用いて得られる。
【０１７４】
【数４０】
【０１７５】
＜式１４＞で、行列φのサイズの自乗に比例してブロックＬＤＰＣ符号の符号化複雑度が発生されるため、本発明では第１のパリティベクトルＰ1を求めるために使用される行列φを単位行列Ｉとなるように設定する。このように、行列φを単位行列Ｉになるように設定することによって、ブロックＬＤＰＣ符号の符号化複雑度が最小化される。ここで、図１５を参照して、行列φを単位行列Ｉになるように設定する過程について説明する。
【０１７６】
まず、順列行列
【０１７７】
【数４１】
【０１７８】
は、単位行列Ｉに固定可能である。図１５に示した部分行列Ｔ-１の部分ブロックで、
【０１７９】
【数４２】
【０１８０】
部分は行列
【０１８１】
【数４３】
【０１８２】
から行列
【０１８３】
【数４４】
【０１８４】
までの積である
【０１８５】
【数４５】
【０１８６】
を示す。行列φは、下記の＜式１５＞〜＜式１７＞を用いて求められる。
【０１８７】
まず、図１５で部分行列Ｅは、一つの部分ブロックを除いてはすべてゼロ行列であるため、部分行列Ｅと部分行列Ｔの逆行列であるＴ-1の乗算は部分行列Ｔの逆行列であるＴ-１の最後行と部分行列Ｅの最後ブロックの乗算形態で＜式１５＞のように示す。
【０１８８】
【数４６】
【０１８９】
部分行列Ｅと部分行列Ｔの逆行列Ｔ-１の積に部分行列Ｂを乗算すると、<式１６>のように示す。
【０１９０】
【数４７】
【０１９１】
（ここで、ｋはＰｙの位置により決定される任意の自然数である。）
＜式１６＞に示すように、部分行列Ｅと部分行列Ｔの逆行列であるＴ-１の積に部分行列Ｂを乗算する場合に、部分行列Ｂが２個の部分ブロックを除いてはすべてゼロ行列を含むため、部分行列Ｂの２個のブロックのみに対して乗算を遂行することで、簡単に演算される。
【０１９２】
もし、
【０１９３】
【数４８】
【０１９４】
に設定すると、φ≒ＥＴ-１Ｂ＋Ｄ＝Ｉになる。したがって、行列φは単位行列Ｉとなる。そして、＜式１７＞ は、行列φが単位行列Ｉになる条件を簡略に示すものである。
【０１９５】
【数４９】
【０１９６】
＜式１５＞〜＜式１７＞に示すように、行列φが単位行列Ｉになるように設定すると、ブロックＬＤＰＣ符号の符号化過程は、その複雑度が最小化できる。
【０１９７】
次に、図１８を参照して、本発明によるパリティ検査行列を使用してブロックＬＤＰＣ符号を符号化する過程を説明する。
【０１９８】
図１８は、本発明の実施形態によるブロックＬＤＰＣ符号の符号化過程を示すフローチャートである。図１８を参照すると、制御器は、ステップ１８１１で、ブロックＬＤＰＣ符号で符号化するための情報語ベクトルsを受信し、ステップ１８１３及びステップ１８１５に進行する。ここで、ブロックＬＤＰＣ符号で符号化するために受信された情報語ベクトルsの長さはｋであると仮定する。ステップ１８１３で、制御器は、この情報語ベクトルsとパリティ検査行列（Ａs）の部分行列Ａを行列乗算を遂行した後に(s)、ステップ１８１７に進行する。ここで、部分行列Ａに存在する１の値を有する要素の個数は、０の値を有する要素の個数に比べて非常に少ないため、情報語ベクトルsとパリティ検査行列の部分行列Ａの行列乗算は、比較的少ない回数の和積(ｓｕｍ-ｐｒｏｄｕｃｔ)演算のみで可能になる。また、部分行列Ａで１の値を有する要素の位置は０でないブロック位置とそのブロックの順列行列の指数で示すことができ、それによって、所定のパリティ検査行列に比べて非常に簡単な演算のみでも行列乗算が遂行可能である。ステップ１８１５で、制御器は、パリティ検査行列の部分行列Ｃと情報語ベクトルsの行列乗算を遂行し(Ｃs)、ステップ１８１９に進行する。
【０１９９】
一方、ステップ１８１７で、制御器は、情報語ベクトルsとパリティ検査行列(ＥＴ-１Ａs)の部分行列Ａの行列乗算結果と行列ＥＴ-１の行列乗算を遂行し、ステップ１８１９に進行する。上述したように、行列ＥＴ-１で１の値を有する要素の個数は非常に少ないため、ブロックの順列行列の指数がわかるだけでも、行列乗算を容易に遂行することができる。ステップ１８１９で、制御器は、ＥＴ-１ＡsとＣsを加算して第１のパリティベクトルp1を計算した後(p1＝ＥＴ-1Ａs＋Ｃs )、ステップ１８２１に進行する。ここで、加算演算は、排他的加算(ｅｘｃｌｕｓｉｖｅ ＯＲ)演算で同一のビットが加算されるときには０となり、相違したビットが加算されるときには１となる。その結果、ステップ１８１９までの過程は、＜式１４＞で説明したような第１のパリティベクトルp1を計算するためのことである。
【０２００】
ステップ１８２１で、制御器は、パリティ検査行列の部分行列Ｂと第１のパリティベクトルp1 を乗算し(Ｂp1)、その値にＡsを加算した後に(Ａs＋Ｂp1)、ステップ１８２３に進行する。ここで、＜式１２＞に説明したように、情報語ベクトルsと第１のパリティベクトルp1を知ると、第２のパリティベクトルp2を求めるために、パリティ検査行列の部分行列Ｔの逆行列Ｔ-１を乗算しなければならない。したがって、ステップ１８２３で、制御器は、第２のパリティベクトルp2を求めるために、ステップ１８２１で計算したベクトルに部分行列Ｔの逆行列Ｔ-１を乗算した後（p2＝Ｔ-1(Ａs＋Ｂp1)）、ステップ１８２５に進行する。上記したように、符号化するためのブロックＬＤＰＣ符号の情報語ベクトルsのみを知ると、第１のパリティベクトルp1と、第２のパリティベクトルp2を求めることができ、その結果、符号語ベクトルすべてが得られる。そして、制御器は、ステップ１８２５で、情報語ベクトルsと、第１のパリティベクトルp1と、第２のパリティベクトルp2で生成された符号語ベクトルcを生成して伝送し、上記の手順を終了する。
【０２０１】
図１９は、本発明の実施形態での機能を遂行するためのブロックＬＤＰＣ符号の符号化装置の内部構造を示すブロック構成図である。
【０２０２】
図１９を参照すると、ブロックＬＤＰＣ符号の符号化装置は、行列Ａ乗算器１９１１と、行列Ｃ乗算器１９１３と、行列ＥＴ-１乗算器１９１５と、第１の加算器１９１７と、行列Ｂ乗算器１９１９と、第２の加算器１９２１と、行列ＥＴ-１乗算器１９２３と、スイッチ１９２５，１９２７，１９２９とを含む。
【０２０３】
まず、入力信号、すなわちブロックＬＤＰＣ符号で符号化しようとする長さｋの情報語ベクトルsが入力され、入力された長さｋの情報語ベクトルsはスイッチ１９２５、行列Ａ乗算器１９１１、及び行列Ｃ乗算器１９１３に入力される。この行列Ａ乗算器１９１１は、情報語ベクトルsと全体パリティ検査行列の部分行列Ａを乗算した後に、行列ＥＴ-1乗算器１９１５と加算器１９２１に出力する。また、行列Ｃ乗算器１９１３は、情報語ベクトルsと全体パリティ検査行列の部分行列Ｃを乗算した後に、第１の加算器１９１７に出力する。行列ＥＴ-１を乗算器１９１５は、行列Ａ乗算器１９１１から出力した信号に全体パリティ検査行列の部分行列ＥＴ-１を乗算した後に、第１の加算器１９１７に出力する。
【０２０４】
第１の加算器１９１７は、行列ＥＴ-１乗算器１９１５から出力された信号と行列Ｃ乗算器１９１３から出力された信号を入力して加算した後に、行列Ｂ乗算器１９１９及びスイッチ１９２７に出力する。ここで、第１の加算器１９１７は、ビット別に排他的論理和(ＸＯＲ)演算を遂行する。例えば、長さ３であるベクトルｘ＝(ｘ１，ｘ２，ｘ３)と長さ３であるベクトルｙ＝(ｙ１，ｙ２，ｙ３)が加算器１９１７に入力される場合に、加算器１９１７は長さ３であるベクトルｘ＝(ｘ１，ｘ２，ｘ３)と長さ３であるベクトルｙ＝(ｙ１，ｙ２，ｙ３)を排他的論理和演算して長さ３であるベクトル
【０２０５】
【数５０】
【０２０６】
同一のビットが演算されると０になり、相異なるビットが演算されると１になる排他的論理和演算を示す。すなわち、第１の加算器１９１７から出力される信号が第１のパリティベクトルp1になる。
【０２０７】
また、行列Ｂ乗算器１９１９は、第１の加算器１９１７から出力された信号、すなわち第１のパリティベクトルp1を入力して全体パリティ検査行列の部分行列Ｂを乗算した後に、加算器１９２１に出力する。加算器１９２１は、行列Ｂ乗算器１９１９から出力された信号と行列Ａ乗算器１９１１から出力された信号を加算した後に、行列Ｔ-１乗算器１９２３に出力する。ここで、加算器１９２１は、加算器１９１７で説明したように、行列Ｂ乗算器１９１９から出力された信号と行列Ａ乗算器１９１１から出力された信号を排他的論理和演算した後に、行列Ｔ-１乗算器１９２３に出力する。
【０２０８】
行列Ｔ-１乗算器１９２３は、加算器１９２１から出力された信号と行列Ｔ-１を乗算した後に、スイッチ１９２９に出力する。ここで、行列Ｔ-１乗算器１９２３の出力が、結局第２のパリティベクトルp2になる。一方、スイッチ１９２５，１９２７，１９２９は、各々自分の伝送する時点のみでスイッチオン(ｓｗｉｔｃｈ ｏｎ)されて該当信号を伝送する。すなわち、情報語ベクトルsが伝送される時点で、スイッチ１９２５がスイッチオンされ、第１のパリティベクトルp1が伝送される時点でスイッチ１９２７がスイッチオンされ、第２のパリティベクトルp2が伝送される時点でスイッチ１９２９がスイッチオンされる。
【０２０９】
上記したように、全体パリティ検査行列の部分行列を適切に選択することによって、行列乗算ＥＴ-１が比較的簡単になり、それによって、ＥＴ-１ＡsＴの計算が容易になる。なお、行列φが単位行列Ｉになってp1Ｔを計算するためのφ-１の演算過程が省略される。
【０２１０】
上記では、効率的な符号化を考慮したブロックＬＤＰＣ符号の生成方法について説明した。上記のブロックＬＤＰＣ符号は、ブロックＬＤＰＣ符号の構造的な特性によって、パリティ検査行列に関連した情報を貯蔵するためのメモリ効率が高いだけでなく、パリティ検査行列で部分行列を適切に選択することによって効率的な符号化が可能になる。しかしながら、ブロック単位でパリティ検査行列を生成することによって、不規則性(ｒａｎｄｏｍｎｅｓｓ）は減少し、それによるブロックＬＤＰＣ符号の性能の劣化をもたらす。すなわち、上記のように、不均一ブロックＬＤＰＣ符号が均一ブロックＬＤＰＣ符号に比べて性能が良いため、ブロックＬＤＰＣ符号を設計することにおいて、全体パリティ検査行列で部分行列を選択することは非常に重要な要素として作用するようになる。
【０２１１】
ここで、図１６を参照してブロックＬＤＰＣ符号のサイクル特性を考慮して効率的な符号化が可能であり、かつ優れた性能を有するブロックＬＤＰＣ符号の具体的な生成方法について説明する。
【０２１２】
図１６は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列を示す図である。図１６を参照すると、ブロックＬＤＰＣ符号のパリティ検査行列は構造の単純性を考慮して、上述したように
【０２１３】
【数５１】
【０２１４】
に設定する。この場合、行列φは単位行列Ｉとなって効率的な符号化を可能にする。ここで、パリティ検査行列の部分行列のブロック長さＮｓ＝３１で、したがってＰ-１＝Ｐ３０である。パリティ検査行列の全体列に対するブロックの個数は３２個であるため、全体ブロック長さが３２x３１＝９９２で、符号化率１/２のブロックＬＤＰＣ符号のパリティ検査行列が生成される。
【０２１５】
その結果、図１６に示すようにブロックＬＤＰＣ符号は、パリティ検査行列の列を基準としてウェイト値が２である１５個のブロックと、ウェイト値が３である１２個のブロックと、ウェイト値が１１である５個のブロックで構成された不均一ブロックＬＤＰＣ符号になる。したがって、図１６に示すように、ブロックＬＤＰＣ符号の次数分布は、下記の＜式１８＞のように示す。
【０２１６】
【数５２】
【０２１７】
＜式１８＞で、ｆｉはブロックＬＤＰＣ符号の因子グラフで全体変数ノードに対する次数がｉである変数ノードの比率を示し、ｆρｉはブロックＬＤＰＣ符号の因子グラフで全体検査ノードに対する次数がｉである検査ノードの比率を示す。その一例として、ブロック長さがＮｓ＝３２であるブロックＬＤＰＣ符号において、ブロックＬＤＰＣ符号の因子グラフ上で全体３２個の変数ノードの中に１５個の変数ノードに該当するパリティ検査行列の列がウェイト値３２を有し、１２個の変数ノードに該当するパリティ検査行列の列がウェイト値３を有し、５個の変数ノードに該当するパリティ検査行列の列がウェイト値１１を有する。これら変数ノードだけでなく、検査ノードに対応するパリティ検査行列に対しても、変数ノードに対して遂行したことと同一の形態でウェイト値を考慮することができる。一方、＜式１８＞に示すように、次数分布は、しきい値(ｔｈｒｅｓｈｏｌｄ ｖａｌｕｅ)を有するＬＤＰＣ符号の次数分布にほとんど近接した形態を有する。また、図１６に示しているブロックＬＤＰＣ符号の場合は、次数が２，３であるノード間に存在するサイクルの最小サイズが１２であり、全体ノード間の場合は最小サイズが６である。
【０２１８】
次に、図２０を参照して、本発明の実施形態によるパリティ検査行列を用いてブロックＬＤＰＣ符号を復号する段階について説明する。
【０２１９】
図２０は、本発明の実施形態によりブロックＬＤＰＣ符号の復号装置の内部構造を示す図である。図２０を参照すると、ブロックＬＤＰＣ符号の復号装置は、変数ノード部２０００と、加算器２０１５と、デインタリーバ(ｄｅｉｎｔｅｒｌｅａｖｅｒ)２０１７と、インタリーバ２０１９と、制御器２０２１と、メモリ２０２３と、加算器２０２５と、検査ノード部２０５０と、硬判定器２０２９とを含んで構成される。変数ノード部２０００は、変数ノード復号器２０１１と、スイッチ２０１３で構成され、検査ノード部２０５０は検査ノード復号器２０２７で構成される。
【０２２０】
無線チャンネルを通じて受信される受信信号は、変数ノード部２０００の変数ノード復号器２０１１に入力される。変数ノード復号器２０１１は、この受信された受信信号の確率値を計算し、計算された確率値をアップデートした後にスイッチ２０１３及び加算器２０１５に出力する。ここで、変数ノード復号器２０１１は、ブロックＬＤＰＣ符号の復号装置に予め設定されているパリティ検査行列に対応して変数ノードを接続し、変数ノードに接続された‘１’の個数だけの入力値と出力値を有するアップデート演算が遂行される。変数ノードの各々に接続された‘１’の個数は、パリティ検査行列を構成する列のそれぞれのウェイト値と同一である。したがって、パリティ検査行列を構成する列のそれぞれのウェイトにより、変数ノード復号器２０１１の内部演算が異なるように遂行される。
【０２２１】
第１の加算器２０１５は、変数ノード復号器２０１１から出力される信号と以前反復復号過程でインタリーバ２０１９の出力信号を入力し、変数ノード復号器２０１１からの信号から以前反復復号過程でインタリーバ２０１９の出力信号を減算した後に、デインタリーバ２０１７に出力する。ここで、復号過程が最初の復号過程である場合に、インタリーバ２０１９の出力信号は‘０’であるとみなすことはもちろんである。
【０２２２】
デインタリーバ２０１７は、第１の加算器２０１５から出力された信号を入力して予め設定されている設定方式に対応してデインタリービングした後に、第２の加算器２０２５と検査ノード復号器２０２７に出力する。ここで、デインタリーバ２０１７の内部構造は、パリティ検査行列に対応する構造を有し、その理由は、パリティ検査行列の‘１’の値を有する要素の位置によりデインタリーバ２０１７に対応するインタリーバ２０１９の入力値に対する出力値が相互に異なるためである。
【０２２３】
第２の加算器２０２５は、以前反復復号過程での検査ノード復号器２０２７の出力信号とデインタリーバ２０１７の出力信号を受信し、以前反復復号過程での検査ノード復号器２０２７の出力信号からデインタリーバ２０１７の出力信号を減算した後に、インタリーバ２０１９に出力する。検査ノード復号器２０２７は、ブロックＬＤＰＣ符号の復号装置に予め設定されているパリティ検査行列に対応して検査ノードを接続し、検査ノードに接続された‘１’の個数だけの入力値と出力値を有するアップデート演算が遂行される。検査ノードの各々に接続された‘１’の個数は、パリティ検査行列を構成する行のそれぞれのウェイト値と同一である。したがって、パリティ検査行列を構成する行のそれぞれのウェイト値により検査ノード復号器２０２７の内部演算が相互に異なるようになる。
【０２２４】
インタリーバ２０１９は、制御器２０２１の制御によって予め設定されている設定方式で、加算器２０２５から出力された信号をインタリービングした後に、加算器２０１５及び変数ノード復号器２０１１に出力する。ここで、制御器２０２１は、メモリ２０２３に貯蔵されているインタリービング方式に関連した情報を読み出してインタリーバ２０１９のインタリービング方式を制御するようになる。また、この復号化過程が最初の復号過程である場合には、デインタリーバ２０１７の出力信号は‘０’であるとみなすことはもちろんである。
【０２２５】
上記のような過程を反復して遂行することによって、誤りなしの高信頼度の復号化を遂行し、予め設定された設定反復回数に該当する反復復号化を遂行した後に、スイッチ２０１３は変数ノード復号器２０１１と加算器２０１５との間をスイッチオフする。その後、スイッチ２０１３は、変数ノード復号器２０１１と硬判定器２０２９との間をスイッチオンして変数ノード復号器２０１１から出力された信号を硬判定器２０２９に出力する。硬判定器２０２９は、変数ノード復号器２０１１から出力された信号を入力して硬判定した後に、その硬判定結果を出力し、この硬判定器２０２９の出力値が最終的に復号された値になる。
【図面の簡単な説明】
【０２２６】
【図１】一般的な(８，２，４)ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図２】図１の(８，２，４)ＬＤＰＣ符号の因子グラフを示す図である。
【図３】一般的なブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。
【図４】図３の循環行列Ｐを示す図である。
【図５】一般的な均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図６】一般的な不均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図７】パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【図８】パリティ検査行列が６個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【図９】ブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１０】パリティ検査行列の６個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１１】パリティ検査行列の７個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１２】完全下三角行列形態を有するパリティ検査行列を示す図である。
【図１３】完全下三角行列形態に類似した形態を有するパリティ検査行列を示す図である。
【図１４】図１３のパリティ検査行列を６個の部分ブロックに分割した図である。
【図１５】図１４の部分行列Ｂの転置行列と、部分行列Ｅと、部分行列Ｔと、部分行列Ｔの逆行列を示す図である。
【図１６】本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図１７】本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列の生成過程を示すフローチャートである。
【図１８】本発明の実施形態によるブロックＬＤＰＣ符号の符号化過程を示すフローチャートである。
【図１９】本発明の実施形態によるブロックＬＤＰＣ符号の符号化装置の内部構造を示すブロック構成図である。
【図２０】本発明の実施形態によるブロックＬＤＰＣ符号の復号装置の内部構造を示す図である。
【符号の説明】
【０２２７】
１９１１ 行列Ａ乗算器
１９１３ 行列Ｃ乗算器
１９１５ 行列ＥＴ-１乗算器
１９１７ 第１の加算器
１９１９ 行列Ｂ乗算器
１９２１ 第２の加算器
１９２３ 行列ＥＴ-１乗算器
１９２５，１９２７，１９２９ スイッチ
【技術分野】
【０００１】
本発明は移動通信システムに関するもので、特に、ブロック低密度パリティ検査符号を符号化/復号化する装置及び方法に関するものである。
【背景技術】
【０００２】
１９７０年代末の米国で、セルラー(ｃｅｌｌｕｌａｒ)方式の無線移動通信システム(Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ Ｓｙｓｔｅｍ）が開発された以来、韓国ではアナログ方式の１世代(１ｓｔ Ｇｅｎｅｒａｔｉｏｎ)移動通信システムと呼ばれるＡＭＰＳ(Ａｄｖａｎｃｅｄ Ｍｏｂｉｌｅ Ｐｈｏｎｅ Ｓｅｒｖｉｃｅ)方式で音声通信サービスを提供し始めた。以後、１９９０年代中盤から韓国では、２世代移動通信システムとして符号分割多重接続(Ｃｏｄｅ Ｄｉｖｉｓｉｏｎ Ｍｕｌｔｉｐｌｅ Ａｃｃｅｓｓ：以下、“ＣＤＭＡ”とする)方式のシステムを商用化して音声及び低速データサービスを提供した。
【０００３】
１９９０年代末から向上した無線マルチメディアサービス、全世界的ローミング(ｒｏａｍｉｎｇ)、高速データサービスなどを目標で始まった３世代移動通信システムであるＩＭＴ(Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｍｏｂｉｌｅ Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎ)-２０００は、現在一部商用化されてサービスが提供されている。特に、３世代移動通信システムは、移動通信システムでサービスするデータ量が急速に増加するに従って、より高速のデータを伝送するために開発された。すなわち、３世代移動通信システムは、パケットサービス通信システム形態で発展してきている。パケットサービス通信システムは、バースト(ｂｕｒｓｔ)パケットデータを複数の移動局に伝送するシステムとして、大容量データ伝送に適合するように設計されている。その結果、パケットサービス通信システムは高速パケットサービスのために発展している。
【０００４】
一方、現在は３世代移動通信システムから４世代移動通信システムに発展している状態である。４世代移動通信システムは、以前世代の移動通信システムのように単純な無線通信サービスに限定されず、有線通信ネットワークと無線通信ネットワークとの効率的連動及び統合サービスを目標として標準化されている。したがって、無線通信ネットワークで有線通信ネットワークの容量(ｃａｐａｃｉｔｙ)に近接する大容量データを伝送できる技術開発が要求されている。
【０００５】
このように、音声サービスデータだけでなく、映像、無線データなどの多様な情報を処理して伝送できる高速大容量通信システムが要求されることによって、適正なチャンネル符号化方式を用いてシステム伝送効率を高くすることが、システム性能向上に必須的な要素で作用するようになる。しかしながら、移動通信システムは、移動通信システムの特性上、データを伝送するときに、チャンネルの状況により雑音と、干渉(ｉｎｔｅｒｆｅｒｅｎｃｅ)及びフェージング(ｆａｄｉｎｇ)などによって不回避に誤り(ｅｒｒｏｒ)が発生する。したがって、誤り発生は、情報データの損失をもたらす。
【０００６】
このような誤り発生による情報データ損失を減少させるために、チャンネルの性格によって多様な誤り制御技術を使用することによって、移動通信システムの信頼度を向上させることができる。誤り制御技術の中で、誤り訂正符号(ｅｒｒｏｒ-ｃｏｒｒｅｃｔｉｎｇ ｃｏｄｅ)を使用する技術が一番普遍的である。ここで、誤り訂正符号の代表的な符号であるターボ符号(ｔｕｒｂｏ ｃｏｄｅ)と、低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：以下、“ＬＤＰＣ”とする)符号について説明する。
【０００７】
ターボ符号
ターボ符号は、最近第３世代移動通信システムで注目されている同期方式と非同期方式ですべて使用されている誤り訂正符号である。従来から順方向誤り訂正のために主に利用された畳み込み符号(ｃｏｎｖｏｌｕｔｉｏｎａｌ ｃｏｄｅ)に比べて、このターボ符号は、高速データ伝送時に性能利得が優れると知られている。また、ターボ符号は、伝送チャンネルで発生する雑音による誤りを效果的に訂正してデータ伝送の信頼度を向上するという長所を有する。
【０００８】
ＬＤＰＣ符号
ＬＤＰＣ符号は、因子(ｆａｃｔｏｒ)グラフで和積(ｓｕｍ-ｐｒｏｄｕｃｔ)アルゴリズムに基づいた反復復号アルゴリズムを用いて復号することができる。ＬＤＰＣ符号の復号器(ｄｅｃｏｄｅｒ）は、和積アルゴリズムに基づいた反復復号アルゴリズムを使用するため、ターボ符号の復号器に比べて低い複雑度を有するだけでなく、並列処理復号器で実現することが容易である。ＬＤＰＣ符号を因子グラフで表現すると、ＬＤＰＣ符号の因子グラフ上にサイクルが存在するようになる。このサイクルが存在するＬＤＰＣ符号の因子グラフ上の反復復号は、準最適(ｓｕｂ-ｏｐｔｉｍａｌ)とは、既によく知られている事実である。また、ＬＤＰＣ符号は、反復復号を通じて優れた性能を有することも実験的に立証された事実である。しかしながら、ＬＤＰＣ符号の因子グラフで短い長さのサイクルが多く存在する場合には、ＬＤＰＣ符号の性能劣化が発生される。そのため、ＬＤＰＣ符号の因子グラフ上に短い長さのサイクルが存在しないようにＬＤＰＣ符号を設計するための研究が持続的に遂行されている。
【０００９】
ＬＤＰＣ符号の符号化過程は、一般的に高いウェイト(ｗｅｉｇｈｔ)密度を有する生成行列(ｇｅｎｅｒａｔｉｎｇ ｍａｔｒｉｘ）の特性により低いウェイト密度を有するパリティ検査行列(ｐａｒｉｔｙ ｃｈｅｃｋ ｍａｔｒｉｘ）を用いる形態で発展されてきた。ここで、“ウェイト”とは、生成行列及びパリティ検査行列を構成する要素(ｅｌｅｍｅｎｔ)のうち０でない値を有する要素の個数を示す。特に、パリティ検査行列でパリティに該当する部分行列(ｐａｒｔｉａｌ ｍａｔｒｉｘ）の形態が規則的な形態を有すると、より効率的な符号化が可能である。
【００１０】
一方、ＬＤＰＣ符号は０でない値を有する多様な符号を含んでいるため、ＬＤＰＣ符号の実用化問題において、多様な形態を有するＬＤＰＣ符号の効率的な符号化アルゴリズムと効率的な復号アルゴリズムを開発することが非常に重要である。また、ＬＤＰＣ符号のパリティ検査行列は、ＬＤＰＣ符号の性能を決定するため、優れた性能を有するパリティ検査行列を設計することも非常に重要である。すなわち、優れた性能を有する効率的なパリティ検査行列と、効率的な符号化アルゴリズム及び復号アルゴリズムを同時に考慮しなければ、高性能のＬＤＰＣ符号を生成することが可能になる。
【００１１】
また、ＬＤＰＣ符号は、大部分の要素が０の値を有し、０の値を有する要素以外の極少数の要素が１の値を有するパリティ検査行列によって定義される。例えば、(Ｎ，ｊ，ｋ)ＬＤＰＣ符号は、ブロック長Ｎである線形ブロック符号(ｌｉｎｅａｒ ｂｌｏｃｋ ｃｏｄｅ）で、各列(ｃｏｌｕｍｎ)ごとにｊ個の１の値を有する要素と、各行(ｒｏｗ)ごとにｋ個の１の値を有する要素を有し、１の値を有する要素を除いた要素は、すべて０の値を有する要素で構成された疎(ｓｐａｒｓｅ)構造のパリティ検査行列によって定義される。
【００１２】
上記に説明したように、パリティ検査行列内の各列のウェイト値がｊ個に一定で、パリティ検査行列内の各行のウェイト値がｋ個に一定のＬＤＰＣ符号を“均一ＬＤＰＣ符号”と称する。一方、パリティ検査行列内の各列のウェイト値と各行のウェイト値が一定しないＬＤＰＣ符号を“不均一ＬＤＰＣ符号”と称する。一般的に、均一ＬＤＰＣ符号の性能に比べて、不均一ＬＤＰＣ符号の性能がさらに優れると知られている。しかしながら、不均一ＬＤＰＣ符号の場合に、パリティ検査行列内の各列のウェイト値と各行のウェイト値が一定しないため、すなわち、不均一なため、パリティ検査行列内の各列のウェイトの個数と各行のウェイトの個数を適切に調節しなければ、優れた性能の保障を受けることができない。
【００１３】
ここで、図１を参照して、(Ｎ，ｊ，ｋ)ＬＤＰＣ符号、一例として(８，２，４)ＬＤＰＣ符号のパリティ検査行列を説明する。
【００１４】
図１は、一般的な(８，２，４)ＬＤＰＣ符号のパリティ検査行列を示す図である。図１を参照すると、(８，２，４)ＬＤＰＣ符号のパリティ検査行列Ｈは、８個の列と４個の行で構成されており、各列のウェイトの個数は２として均一で、各行のウェイトの個数は４として均一である。このように、パリティ検査行列内の各列のウェイトの個数と各行のウェイトの個数が均一である。したがって、図１に示している(８，２，４)ＬＤＰＣ符号は均一ＬＤＰＣ符号となる。
【００１５】
図１では、(８，２，４)ＬＤＰＣ符号のパリティ検査行列について説明する。その次に、図２を参照して、図１に示した(８，２，４)ＬＤＰＣ符号の因子グラフを説明する。
【００１６】
図２は、図１の(８，２，４)ＬＤＰＣ符号の因子グラフを示す図である。図２を参照すると、(８，２，４)ＬＤＰＣ符号の因子グラフは８個の変数ノード(ｖａｒｉａｂｌｅ ｎｏｄｅ)、すなわち、ｘ１２１１と、ｘ２２１３と、ｘ３２１５、ｘ４２１７と、ｘ５２１９と、ｘ６２２１と、ｘ７２２３と、ｘ８２２５と、４個の検査ノード２２７，２２９，２３１，２３３で構成される。（８，２，４)ＬＤＰＣ符号のパリティ検査行列のｉ番目の行とｊ番目の列が交差する地点にウェイト、すなわち、１の値を有する要素が存在する場合に、変数ノードｘｊとｉ番目の検査ノードとの間にブランチ(ｂｒａｎｃｈ)が形成される。
【００１７】
上述したように、ＬＤＰＣ符号のパリティ検査行列は、非常に少ない個数のウェイトを有するため、比較的長い長さを有するブロック符号でも反復復号を通じて復号が可能で、ブロック符号のブロック長さを継続して増加させると、ターボ符号のようにＳｈａｎｎｏｎのチャンネル容量限界に近接する形態の性能を示す。流れ伝送方式を使用するＬＤＰＣ符号の反復復号過程がターボ符号の反復復号過程にほとんど近接する性能を有する。
一方、高性能のＬＤＰＣ符号を生成するための条件を説明すると、次のようである。
【００１８】
(１)ＬＤＰＣ符号の因子グラフ上のサイクルを考慮すべきである。
サイクルとは、ＬＤＰＣ符号の因子グラフで変数ノードと検査ノードを接続するエッジが構成するループ(ｌｏｏｐ)を示すのに、サイクルの長さはループを構成するエッジの個数に定義される。サイクルの長さが長いということは、ＬＤＰＣ符号の因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が多いという意味である。その反対に、サイクルの長さが短いということは、ＬＤＰＣ符号の因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が少ないということを意味する。
【００１９】
ＬＤＰＣ符号の因子グラフ上のサイクルを長く生成するほど、ＬＤＰＣ符号の性能が増加するようになる。その理由は、次のようである。ＬＤＰＣ符号の因子グラフ上のサイクルを長く生成する場合に、ＬＤＰＣ符号の因子グラフ上に短い長さのサイクルが多く存在するときに発生する誤りフロア(ｅｒｒｏｒ ｆｌｏｏｒ）のような性能劣化が発生しないためである。
【００２０】
(２)ＬＤＰＣ符号の効率的な符号化を考慮すべきである。
ＬＤＰＣ符号は、ＬＤＰＣ符号の特性上畳み込み符号やターボ符号に比べて符号化の複雑度が高くてリアルタイム符号化が容易でない。ＬＤＰＣ符号の符号化複雑度を減少するために、反復累積(Ｒｅｐｅａｔ Ａｃｃｕｍｕｌａｔｅ：ＲＡ)符号などが提案された。反復累積符号もＬＤＰＣ符号の符号化複雑度を低下させるのに限界を有する。したがって、ＬＤＰＣ符号の効率的な符号化を考慮しなければならない。
【００２１】
(３)ＬＤＰＣ符号の因子グラフ上の次数分布を考慮すべきである。
一般的に、不均一ＬＤＰＣ符号が均一ＬＤＰＣ符号より性能が優れる。その理由は、不均一ＬＤＰＣ符号の因子グラフが多様な次数を有するためである。ここで、“次数(ｄｅｇｒｅｅ)”とは、ＬＤＰＣ符号の因子グラフ上で各ノード、すなわち変数ノードと検査ノードに接続されているエッジの個数を示す。また、ＬＤＰＣ符号の因子グラフ上の“次数分布”とは、特定次数を有するノードが全体ノードの中にどのくらい存在するかを示す。特定の次数分布を有するＬＤＰＣ符号の性能が優れるということは、既に証明したところである。
【００２２】
図３は、一般的なブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。図３の説明に先立って、ブロックＬＤＰＣ符号は、効率的な符号化だけでなく効率的なパリティ検査行列の貯蔵及び性能改善をすべて考慮した新たなＬＤＰＣ符号である。このブロックＬＤＰＣ符号は、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。図３を参照すると、ブロックＬＤＰＣ符号のパリティ検査行列は、全体パリティ検査行列を複数の部分ブロックに分割し、部分ブロックの各々に順列行列(ｐｅｒｍｕｔａｔｉｏｎ ｍａｔｒｉｘ)))を対応させる形態を有する。図３に示すように、“Ｐ”はＮｓxＮｓサイズを有する順列行列を示し、この順列行列Ｐの上付き添え字ａｉｊは０≦ａｉｊ≦Ｎｓ-１又はａｉｊ＝∞を有する。図３において、“Ｐ”は部分ブロックの行の個数を、“ｑ”は部分ブロックの列の個数を、それぞれ示す。“ｉ”は、対応する順列行列がパリティ検査行列の部分ブロックのｉ番目の行に位置することを意味し、“ｊ”は対応する順列行列がパリティ検査行列の部分ブロックのｊ番目の列に位置することを意味する。すなわち、
【００２３】
【数１】
【００２４】
は、ｉ番目の行とｊ番目の列で交差する部分ブロックに位置する順列行列である。
【００２５】
ここで、図４を参照して、上記の順列行列について説明する。
図４に示すように、循列行列ＰはＮｓxＮｓサイズを有する正方形行列として、循列行列Ｐを構成するＮｓ個の行のウェイトがそれぞれ１で、循環行列Ｐを構成するＮｓ個の行のウェイトもそれぞれ１である行列を示す。
【００２６】
一方、図３で、順列行列の上付き添え字ａｉｊ＝０である場合、すなわち、順列行列Ｐ０は単位行列
【００２７】
【数２】
【００２８】
を示し、順列行列Ｐの上付き添え字ａｉｊ＝∞である場合、すなわち順列行列Ｐ∞はゼロ行列を示す。
【００２９】
図３で、ブロックＬＤＰＣ符号の全体パリティ検査行列は、全体列の個数がＮｓxｑ(ｐ≦ｑ)で、全体行の個数がＮｓxｐであるため、ブロックＬＤＰＣ符号の全体パリティ検査行列が最大ランク(ｆｕｌｌ ｒａｎｋ)を有する場合に、部分ブロックのサイズに関係なく符号化率(ｃｏｄｉｎｇ ｒａｔｅ）は、下記の＜式１＞のようである。
【００３０】
【数３】
【００３１】
すべてのｉ、ｊに対してａｉｊ≠∞である場合に、部分ブロックの各々に対応する順列行列は、各々ゼロ行列でないことを示し、部分ブロックの各々に対応する順列行列の各行のウェイトはｐ、各列のウェイトはｑである均一ＬＤＰＣ符号となる。ここで、部分ブロックに対応する順列行列を“部分行列”と称する。
【００３２】
また、全体パリティ検査行列にはｐ-１個の従属的な(ｄｅｐｅｎｄｅｎｔ)行が存在するため、符号化率は＜式１＞で計算した符号化率より高い値を有する。このブロックＬＤＰＣ符号は、全体パリティ検査行列を構成する部分行列それぞれの１番目の行のウェイト位置が決定されると、残りのＮｓ-１個の行のウェイト位置が決定される。したがって、全体パリティ検査行列の情報を貯蔵するために、不規則にウェイトを選択する場合に比べて必要とするメモリのサイズが１/Ｎｓに縮小される。
【００３３】
図５は、一般的な均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【００３４】
図５に示すようにパリティ検査行列は、均一ブロックＬＤＰＣ符号、すなわち(ｓ，r)配列(ａｒｒａｙ)符号のパリティ検査行列である。(ｓ，r)配列符号は代表的な均一ブロックＬＤＰＣ符号として、この(ｓ，r)アレイ符号は、図３でＮｓ＝ｓで、ｑ＝ｓで、ｐ＝ｒであるブロックＬＤＰＣ符号に該当する。ここで、ｓは奇数である素数であり、ｒは常にｒ≦ｓの条件を満足する。
【００３５】
(ｓ，r)配列符号のパリティ検査行列は、ｓ２個の列とｒxｓ個の行を有し、ランクはｒx(ｓ-１)となる。ここで、(ｓ，r)配列符号のパリティ検査行列のランクがｒ(ｓ-1）となる理由は、(ｓ，r)配列符号のパリティ検査行列の行方向へのｒ個の部分行列は、この部分行列内の各々のｐ個の行をすべて加算すると、すべての要素が１の値を有する行が生成されるためである。すなわち、すべての要素が１の値を有するｒ個の行が生成されるため、ｒ個の従属である行が存在することが分かる。したがって、(ｓ，r)配列符号の符号化率Ｒａｒｒａｙは、下記の＜式２＞のように示す。
【００３６】
【数４】
【００３７】
上記に説明したように、(ｓ，r)配列符号は、その代数的(ａｌｇｅｂｒａｉｃ)な特性から長さが４のサイクルが因子グラフ上に存在しないことがわかり、またメモリ容量も減少させることができる。
【００３８】
しかしながら、(ｓ，r)配列符号は、均一ＬＤＰＣブロック符号であるため、不均一ＬＤＰＣ符号に比べては性能劣化が発生する。また、ブロックＬＤＰＣ符号の場合に、ブロックＬＤＰＣ符号自体のランダムな性質(ｒａｎｄｏｍｎｅｓｓ）が低いため、優れた性能を保障することができない。つまり、(ｓ，r)配列符号は、効率的な符号化を考慮したものであるが、符号化において複雑度は相変わらず高く、長さ４のサイクルが存在しないが、長さ６のサイクルは存在する。次数分布を考慮しないため、性能面で劣化が発生する。
【００３９】
図６は、一般的な不均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。図６の説明に先立って、不均一ブロックＬＤＰＣ符号は、図５に説明したように、配列符号を効率的な符号化を考慮して変形した形態のブロックＬＤＰＣ符号である。図６において、不均一ブロックＬＤＰＣ符号のパリティ検査行列でｋ、ｒはｋ，ｒ≦ｓの条件を満たす整数で(但し、ｓは素数)、Ｉはｓxｓサイズの単位行列を示し、０はｓxｓサイズのゼロ行列を示す。図６に示すように、不均一ブロックＬＤＰＣ符号のパリティ検査行列は、図３でＮｓ＝ｓで、ｑ＝ｋで、ｐ＝ｒのブロックＬＤＰＣ符号のパリティ検査行列に該当する。
【００４０】
一方、ＬＤＰＣ符号の効率的な符号化のために、図６のように全体パリティ検査行列の中でパリティに該当する部分行列を完全下三角行列で構成して線形時間内で符号化が可能にした。全体パリティ検査行列の構造、すなわち情報語に該当する部分行列と、パリティに該当する部分行列構造は下記で説明するため、ここではその詳細な説明を省略する。このようにパリティに該当する部分行列を完全下三角行列で構成する場合に、パリティ検査行列の構造的な特性によってパリティ検査行列は常に最大ランクを有するようになる。そのため、変形された配列符号、すなわち不均一ＬＤＰＣ符号のブロック長さはｋｓとなり、符号化率Ｒは下記の＜式３＞のように示す。
【００４１】
【数５】
【００４２】
しかしながら、図６のようにパリティに該当する部分行列が完全下三角行列形態を有するパリティ検査 行列を有する不均一ＬＤＰＣ符号は、配列符号に比べては符号化面で一層効率的であるが、ＬＤＰＣ符号の生成時に考慮すべき因子グラフ上の次数分布を考慮せず、また長さの短いサイクルに対する除去もやはり考慮しなかった。そのため、ランダムな特性をを有する不均一ＬＤＰＣ符号に比べては低い誤り訂正能力を有する。したがって、誤り訂正能力を最大化する不均一ＬＤＰＣ符号に対する必要性が増大されている。
【発明の開示】
【発明が解決しようとする課題】
【００４３】
したがって、本発明の目的は、移動通信システムで誤り訂正能力を最大化するＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【００４４】
本発明の他の目的は、移動通信システムで最小サイクル長さが最大になるＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【００４５】
また本発明の目的は、移動通信システムで符号化の複雑度が最小化されたＬＤＰＣ符号を符号化/復号化する装置及び方法を提供することにある。
【課題を解決するための手段】
【００４６】
上記した目的を達成するための方法において、本発明は、ブロック低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：ＬＤＰＣ)符号のパリティ検査行列が情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に基づいて前記パリティ検査行列のサイズを決定する段階と、前記決定されたサイズのパリティ検査行列を予め定められた個数のブロックに分割する段階と、前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類する段階と、前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形態で順列行列を配列する段階と、前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一になるように前記順列行列を配列する段階と、を有することを特徴とする。
【００４７】
また、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号方法であって、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を生成し、前記パリティ検査行列に対応してデインタリービング方式及びインタリービング方式を決定する段階と、受信信号の確率値を検出する段階と、前記受信信号の確率値から以前復号時に生成された信号を減算して第１の信号を生成する段階と、前記第１の信号を入力して前記デインタリービング方式でデインタリービングする段階と、前記デインタリービングされた信号を入力して確率値を検出する段階と、前記デインタリービングされた信号の確率値で前記デインタリービングされた信号を減算して第２の信号を生成する段階と、前記第２の信号を前記インタリービング方式でインタリービングし、前記インタリービングされた信号を反復復号する段階と、を含むことを特徴とする。
【００４８】
なお、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化方法であって、情報語と予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算して第１の信号を生成する段階と、前記情報語と前記パリティ検査行列の第２の部分行列と乗算して第２の信号を生成する段階と、前記第１の信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第３の信号を生成する段階と、前記第２の信号と第３の信号を加算して第４の信号を生成する段階と、前記第４の信号と前記パリティ検査行列の第５の部分行列を乗算して第５の信号を生成する段階と、前記第２の信号と前記第５の信号を加算して第６の信号を生成する段階と、前記第６の信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第７の信号を生成する段階と、前記情報語と、前記第４の信号を第１のパリティで、前記第７の信号を第２のパリティとし、前記ブロックＬＤＰＣ符号フォーマットに対応するように多重化して出力する段階と、を有することを特徴とする。
【００４９】
本発明は、パリティ検査行列は、複数の情報部分ブロックと複数のパリティ部分ブロックの行と列の行列形態で配列され、前記パリティ検査行列は前記情報部分ブロックの行列で構成された情報部分と前記パリティ部分ブロックの行列で構成されたパリティ部分に区分され、前記情報部分ブロックの各々は複数の情報ビットを示す行列で構成され、前記パリティ部分ブロックの各々は、複数のパリティビットを示す行列で構成され、前記パリティ検査行列は複数の行に存在する情報部分ブロックとパリティ部分ブロックが各々第１の情報行列と第１のパリティ行列及び第２のパリティ行列に分割され、前記複数の行を除いた残りの行に存在する情報部分ブロックとパリティ部分ブロックが各々第２の情報行列と第３のパリティ行列及び第４のパリティ行列に分割され、前記第１及び第２の情報行列と、第１及び第３のパリティ行列と、第２及び第４のパリティ行列は各々同一の列に配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記第４のパリティ行列と第２のパリティ行列の逆行列と前記第１のパリティ行列の積と前記第３のパリティ行列の和が単位行列になるように設定する段階と、前記第１のパリティ行列と前記第３のパリティ行列に対応する第１のパリティベクトルの転置ベクトルは、前記第４のパリティ行列と前記第２のパリティ行列の逆行列と前記第１の情報行列の積と前記第２の情報行列の和を前記第１の情報行列と前記第２の情報行列に対応する情報ベクトルを乗算した値になるように決定する段階と、前記第２のパリティ行列と第４のパリティ行列に対応する第２のパリティベクトルの転置ベクトルは、前記第２のパリティ行列の逆行列と前記第１の情報行列と前記情報ベクトルの転置ベクトルを乗算した値と前記第１のパリティ行列と前記第１のパリティベクトルの転置ベクトルを乗算した値を加算した値を乗算した値になるように決定する段階と、を有することを特徴とする。
【００５０】
さらに、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号のパリティ検査行列は、複数の部分ブロックの行と列の行列形態で配列され、前記複数の部分ブロック各々にはＮｓxＮｓサイズを有する行列が前記複数の部分ブロックの各々に対応して予め定められた指数だけシフトして生成された順列行列が配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、前記ブロックＬＤＰＣ符号のブロックサイクルを任意の第１の値に決定する段階と、前記ブロックサイクルを決定した後に、前記部分ブロックの各々に配列された順列行列の中に、その指数が奇数である順列行列の指数の和から前記部分ブロックの各々に配列された順列行列のうち、その指数が偶数である順列行列の指数の和を減算した値と任意の第２の値を乗算した値になるように前記第２の値を決定し、前記部分ブロックの各々が前記第１の値と第２の値を乗算した値に対応するサイクルを有するように制御する段階と、を有することを特徴とする。
【００５１】
上記の目的を達成するための装置において、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号装置であって、所定の制御により、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、前記変数ノード復号器から出力された信号から以前復号時に生成された信号を減算して出力する第１の加算器と、前記第１の加算器から出力された信号を入力して前記パリティ検査行列に対応して設定されたデインタリービング方式でデインタリービングして出力するデインタリーバと、所定の制御信号により、前記パリティ検査行列を構成する行のそれぞれのウェイトに対応して検査ノードを接続し、前記デインタリーバからの出力信号の確率値を検出して出力する検査ノード復号器と、前記検査ノード復号器の出力信号から、前記デインタリーバから出力された信号を減算する第２の加算器と、前記第２の加算器から出力された信号を前記パリティ検査行列により設定されたインタリービング方式でインタリービングして前記変数ノード復号器及び前記第１の加算器に出力するインタリーバと、前記パリティ検査行列を生成し、前記デインタリービング方式及びインタリービング方式を前記パリティ検査行列に対応して制御する制御器と、を含むことを特徴とする。
【００５２】
また、本発明は、ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化装置であって、情報語を入力して予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算する第１の行列乗算器と、前記情報語を入力して前記パリティ検査行列の第２の部分行列と乗算する第２の行列乗算器と、前記第１の行列乗算器から出力された信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第３の行列乗算器と、前記第２の行列乗算器から出力された信号と第３の行列乗算器から出力された信号とを加算する第１の加算器と、前記第１の加算器から出力された信号と前記パリティ検査行列の第５の部分行列とを乗算する第４の行列乗算器と、前記第２の行列乗算器から出力された信号と前記第４の行列乗算器から出力された信号とを加算する第２の加算器と、前記第２の加算器から出力された信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第５の行列乗算器と、前記情報語と、前記第１の加算器の出力信号を第１のパリティとし、前記第５の行列乗算器の出力信号を第２のパリティとして前記ブロックＬＤＰＣ符号フォーマットに相応するように多重化して出力するスイッチと、を含むことを特徴とする。
【発明の効果】
【００５３】
本発明は、移動通信システムで最小サイクル長さが最大になるブロックＬＤＰＣ符号を提案することによって、誤り訂正能力を最大化させてシステム性能を向上させる効果を有する。また、本発明は、効率的なパリティ検査行列を生成することによって、ブロックＬＤＰＣ符号の符号化複雑度を最小化させる効果も有する。
【発明を実施するための最良の形態】
【００５４】
以下、本発明の望ましい実施形態を添付の図面を参照して詳細に説明する。
下記の説明で、本発明に関連した公知の機能又は構成に関する説明が本発明の要旨を不明にすると判断された場合に、その詳細な説明を省略する。
【００５５】
本発明は、優秀な性能の不均一低密度パリティ検査(Ｌｏｗ Ｄｅｎｓｉｔｙ Ｐａｒｉｔｙ Ｃｈｅｃｋ：以下、“ＬＤＰＣ”とする)符号を符号化及び復号化する方案を提示する。すなわち、本発明は、因子(ｆａｃｔｏｒ)グラフ上の最小サイクルの長さが最大になり、符号化複雑度が最小になり、因子グラフ上の次数分布が最適化される分布を有する不均一ＬＤＰＣ符号の符号化及び復号化方案を提示する。
【００５６】
ＬＤＰＣ符号の因子グラフ上のサイクルとは、因子グラフで変数ノードと検査ノードを接続するエッジ(ｅｄｇｅ)によって構成されるループを示すが、サイクルの長さはループを構成するエッジの個数に定義される。サイクルの長さが長いということは、因子グラフでループを構成する変数ノードと検査ノードを接続するエッジの個数が多いことを示す。因子グラフ上のサイクルの長さを長く生成するほど、ＬＤＰＣ符号の性能が向上するようになる。その反面、因子グラフ上に長さの短いサイクルが多く存在するほどＬＤＰＣ符号は誤りフロア(ｅｒｒｏｒ ｆｌｏｏｒ）の性能劣化が示すため、誤り訂正能力が低下する。すなわち、因子グラフ上に長さの短いサイクルが多く存在する場合に、長さの短いサイクルに属している任意のノードから出発した自分の情報が少ない反復回数を経てまた帰ってくるようになり、反復回数が増加するほど、その情報が継続して自分に帰って来るようになる。したがって、情報アップデートがよくなされなくて、結局、ＬＤＰＣ符号の誤り訂正能力が低下される。
【００５７】
図７は、パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【００５８】
図７を説明するに先立ち、ブロックＬＤＰＣ符号は効率的な符号化だけでなく効率的なパリティ検査行列の貯蔵及び性能の改善をすべて考慮した新たなＬＤＰＣ符号である。このブロックＬＤＰＣ符号は、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。図７に示すように、ブロックＬＤＰＣ符号のパリティ検査行列は、４個のブロックで構成され、斜線は１の値を有する要素(ｅｌｅｍｅｎｔ)が存在する位置を意味し、死線部分以外の部分はすべて０の値を有する要素が存在する位置を意味する。また、Ｐは、従来技術の図４で説明した順列行列(ｐｅｒｍｕｔａｔｉｏｎ ｍａｔｒｉｘ）と同一の順列行列を示す。ここで、順列行列Ｐは、図４で説明したように、ＮｓxＮｓサイズを有する正方形行列で、この順列行列Ｐを構成するＮｓ個の行のそれぞれのウェイトが１であり、Ｎｓ個の行のそれぞれのウェイトも１である行列を示す。ここで、“ウェイト”とは、パリティ検査行列を構成する要素のうち、０でない値を有する要素の個数を示す。
【００５９】
図７に示すブロックＬＤＰＣ符号のサイクル構造を分析するために、部分行列Ｐａのｉ番目の行に位置する１の値を有する要素を基準として定め、ｉ番目の行に位置する１の値を有する要素を“０-ポイント”と称する。ここで、“部分行列”は、部分ブロックに対応する行列を示す。すると、０-ポイントは部分行列Ｐａの(i＋ａ)番目の列に位置される。
【００６０】
０-ポイントと同一の行に位置した部分行列Ｐｂでの１の値を有する要素を“１-ポイント”と称する。この０-ポイントと同じ理由で、１-ポイントは部分行列Ｐｂの(ｉ＋ｂ)番目の列に位置する。
【００６１】
次に、１-ポイントと同一の列に位置した部分行列Ｐｃでの１の値を有する要素を“２-ポイント”と称する。部分行列Ｐｃが単位行列Ｉの列の各々を右にモジューロ(ｍｏｄｕｌｏ)Ｎｓに対してｃだけ移動して得られた行列であるため、２-ポイントはこの部分行列Ｐｃの(ｉ＋ｂ−ｃ)番目の行に位置するようになる。
【００６２】
また、２-ポイントと同じ行に位置した部分行列Ｐｄでの１の値を有する要素を“３-ポイント”と称する。３-ポイントは、部分行列Ｐｄでの(i＋ｂ-ｃ＋ｄ)番目の列に位置するようになる。
【００６３】
最後に、３-ポイントと同一の列に位置した部分行列Ｐａでの１の値を有する要素を“４-ポイント”と称する。この４-ポイントは、部分行列Ｐａの(ｉ＋ｂ-ｃ＋ｄ-ａ)番目の行に位置するようになる。
【００６４】
図７に示すＬＤＰＣ符号のサイクル構造で、長さが４であるサイクルが存在すると、０-ポイントと４-ポイントは相互に同一の位置となる。すなわち、０-ポイントと４-ポイントとの間には、下記の＜式４＞のような関係が成立するようになる。
【００６５】
【数６】
【００６６】
そして、上記の＜式４＞をさらに整理すると、下記の＜式５＞のようである。
【００６７】
【数７】
【００６８】
その結果、＜式５＞のような関係が成立するときに、長さ４のサイクルが生成される。一般的に、０-ポイントと４ｍ-ポイントが最初に同一になる場合は、ｉ≡ｉ＋ｍ(ｂ-ｃ＋ｄ-ａ)関係が成立され、下記の＜式６＞のような関係が成立される。
【００６９】
【数８】
【００７０】
さらに説明すると、与えられたａ、ｂ、ｃ、ｄに対して＜式６＞を満たす正の整数の中で最小値を有する正の整数をｍとする場合に、図７に示すようなブロックＬＤＰＣ符号のサイクル構造では長さが４ｍであるサイクルが最小長さを有するサイクルとなる。
【００７１】
結果的に、上記したように、(ａ-ｂ＋ｃ-ｄ)≠０である場合にｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ)＝１を満たすと、ｍ＝Ｎｓになる。ここで、ｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ)は、整数Ｎｓとａ-ｂ＋ｃ-ｄの最大公約数の計算のための機能をする。したがって、長さが４Ｎｓであるサイクルが最小長さを有するサイクルとなる。
【００７２】
図７に説明したように、ブロックＬＤＰＣ符号のサイクルに関する分析は、ブロックＬＤＰＣ符号のパリティ検査行列を構成するブロックの個数が４を超える場合、すなわちパリティ検査行列を構成する部分行列の個数が４を超える場合にも適用可能である。ここで、図８を参照して、パリティ検査行列を構成する部分行列の個数が４を超える場合のＬＤＰＣ符号のサイクル構造について説明する。
【００７３】
図８は、パリティ検査行列が６個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【００７４】
図８に示すブロックＬＤＰＣ符号のパリティ検査行列は、６個のブロックで構成されており、図７で説明したように、斜線は１の値を有する要素が存在する位置を示し、この斜線部分以外の部分はすべて０の値を有する要素が存在する位置を示す。また、Ｐも従来技術である図４で説明した順列行列と同一の順列行列を示す。図７で説明したような方法で、図８におけるブロックＬＤＰＣ符号のサイクル構造を分析すると、長さが６ｍであるサイクルが最小長さを有するサイクルとなる。
【００７５】
一般的に、０-ポイントと６ｍ-ポイントが最初に同一になる場合は、ｉ≡ｉ＋ｍ(ｂ-ｃ＋ｄ-ｅ＋ｆ-ａ)(ｍｏｄ Ｎｓ)の関係が成立され、下記の＜式７＞のような関係を満たすようになる。
【００７６】
【数９】
【００７７】
これら与えられたａ、ｂ、ｃ、ｄ、ｅ、ｆに対して＜式７＞を満たす正の整数の中で、最小値を有する正の整数を“ｍ”とすると、図８に示すブロックＬＤＰＣ符号のサイクル構造では長さが６ｍであるサイクルが最小長さを有するサイクルになる。
【００７８】
上記に述べたように、(ａ-ｂ＋ｃ-ｄ＋ｅ-ｆ)≠０である場合にｇｃｄ(Ｎｓ，ａ-ｂ＋ｃ-ｄ＋ｅ-ｆ)＝１を満たすと、ｍ＝Ｎｓになる。したがって、長さが６Ｎｓであるサイクルが最小長さを有するサイクルになる。
【００７９】
上記に説明したように、ブロックＬＤＰＣ符号について、次のような規則が推定可能である。
【００８０】
<規則１>
ブロックＬＤＰＣ符号で長さが２lであるサイクルが存在すると、下記の＜式８＞の条件を満たすべきである。
【００８１】
【数１０】
【００８２】
＜式８＞ｄ、ａｉ(ｉ＝１，２，…，２１)は長さが２lであるサイクルが順次的に通過する順列行列の指数を示す。すなわち、ブロックＬＤＰＣ符号のパリティ検査行列を構成する部分ブロックに対して長さが２lであるサイクルが
【００８３】
【数１１】
【００８４】
の順に通過することを示す。ここで、すべてのａｉが相互に異なる必要はなく、重複的に通過する部分ブロックが存在することも可能であることはもちろんである。
【００８５】
<規則２>
ｍは、下記の＜式９＞を満たす最小の正の整数であると定義する。
【００８６】
【数１２】
【００８７】
＜式９＞で、ａｉは、全体パリティ検査行列でブロック単位のサイクルが形成されるように適切に選択された順列行列の指数である。そして、ａｉは＜規則１＞の説明と同様に、すべて相互に異なる必要はなく、重複的に通過する部分ブロックが存在することも可能であることはもちろんである。つまり、部分行列
【００８８】
【数１３】
【００８９】
は最小長さが２lｍであるサイクル構造を有する。
【００９０】
＜規則１＞と＜規則２＞を用いると、ブロックＬＤＰＣ符号のサイクル構造の特性を分析することが容易になる。一例として、＜規則１＞と＜規則２＞を用いると、配列符号で最小長さが６であるサイクルが正確にどのくらい分布しているかが分かるだけでなく、下記で説明するブロックＬＤＰＣ符号のブロック単位のサイクル(以下、“ブロックサイクル”と称する)構造の特性分析も容易になる。ここで、ブロックサイクルは、パリティ検査行列の構成において、サイクル長さを調整するのに重要な要素であり、ブロックサイクルを図９及び＜規則１＞と＜規則２＞を使用して説明する。
【００９１】
図９は、ブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図９を参照すると、ブロックＬＤＰＣ符号を構成するブロックの各々がウェイト１を有すると仮定し、このブロックがサイクルを構成する場合に“ブロックサイクルを構成する”と定義する。図９には、左側から４個のブロックで構成されたブロックサイクルと、６個のブロックで構成されたブロックサイクルと、８個のブロックで構成されたブロックサイクルが示している。そして、＜規則１＞と＜規則２＞で説明したように、短い長さのブロックサイクルが構成されるとしてもブロックサイクルを構成するブロックの各々に該当する部分行列を適切に選択するようになると、実際のパリティ検査行列では短い長さのサイクルが生成されないように制御できる。しかしながら、ブロックＬＤＰＣ符号で複数のブロックサイクルが重複される場合は、ブロックサイクル内の実際のサイクルの最小長さが減少される。その結果、実際のパリティ検査行列で短い長さのサイクルが生成されるという問題点が発生する。
【００９２】
ここで、図１０及び＜規則１＞と＜規則２＞を用いてブロックＬＤＰＣ符号で複数のブロックサイクルが重複される問題点について説明する。また、ブロックＬＤＰＣ符号のパリティ検査行列を生成するときに、重複されたブロックサイクルを避けるべき理由についても説明する。
【００９３】
図１０は、パリティ検査行列の６個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図１０に示している矢印に従って、次のような順次的なブロック順序を考慮することができる。
【００９４】
【数１４】
【００９５】
順次的なブロック順序による部分行列の指数は、Ｎｓの値に関係なく下記の＜式１０＞の条件を常に満たす。
【００９６】
【数１５】
【００９７】
＜式１０＞を＜規則２＞で説明した＜式９＞に適用させると、ｍ＝１となる。したがって、図１０に示すような６個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、全体パリティ検査行列を構成するいずれの部分行列を選択しても、常にその長さが１２であるサイクル構造を含むようになる。すなわち、図１０に示すような６個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、パリティ検査行列の最小サイクル長さは最大１２に制限されるものである。
【００９８】
図１１は、パリティ検査行列の７個の部分ブロックが重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。図１１に示している矢印に従って、次のような順次的なブロック順序を考慮することができる。
【００９９】
【数１６】
【０１００】
順次的なブロック順序による部分行列の指数は、Ｎｓの値に関係なく下記の＜式１１＞の条件を常に満たす。
【０１０１】
【数１７】
【０１０２】
＜式１１＞を＜規則２＞で説明した＜式９＞に適用すると、ｍ＝１となる。したがって、図１１に示すようなパリティ検査行列の７個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、全体パリティ検査行列を構成するいずれの部分行列を選択しても、常にその長さが１４であるサイクル構造を含む。すなわち、図１１に示すように、パリティ検査行列の７個の部分行列が重複されたブロックサイクルが存在するブロックＬＤＰＣ符号の場合に、パリティ検査行列の最小サイクル長さは最大１４に制限される。
【０１０３】
上述したように、ブロックＬＤＰＣ符号でパリティ検査行列を構成するブロックの間にブロックサイクルが多く重複されている場合に、パリティ検査行列の部分行列を選択する方法に関係なく、サイクルの最小長さをを最大化するのに制限が発生してその性能が劣化することが分かる。したがって、ブロックＬＤＰＣ符号でパリティ検査行列を生成する場合に、できるだけブロックサイクル自体を少なく生成して重複ブロックサイクルが発生しないように考慮しなければならない。
【０１０４】
次に、ブロックサイクル以外に効率的な符号化を考慮してブロックＬＤＰＣ符号のパリティ検査行列を生成する方法について説明する。
【０１０５】
本発明では、ブロックＬＤＰＣ符号の符号化方式としてＲｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式を使用することにする。このＲｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式を符号化方式で使用するため、パリティ検査行列は完全下三角行列と類似した形態を有するほど符号化の複雑度も最小化させることができる。
【０１０６】
図１２は、完全下三角行列形態を有するパリティ検査行列を示す図である。
【０１０７】
図１２に示すように、パリティ検査行列は、完全下三角行列形態を有し、情報部分(ｉｎｆｏｒｍａｔｉｏｎ ｐａｒｔ)とパリティ部分(ｐａｒｉｔｉｅｓ ｐａｒｔ）で構成される。ここで、情報部分は、ブロックＬＤＰＣ符号を符号化する過程で、実際の情報語にマッピングされるパリティ検査行列の部分を示し、パリティ部分はブロックＬＤＰＣ符号を符号化する過程で実際パリティにマッピングされるパリティ検査行列の部分を示す。パリティ部分は、図１２に示すように、単位行列Ｉに基づいて０行列と部分行列が存在し、部分行列が完全下三角形態を有する。
【０１０８】
図１３は、完全下三角行列形態と類似した形態を有するパリティ検査行列を示す図である。図１３に示すように、パリティ検査行列が、図１２に示した完全下三角行列形態のパリティ検査行列に比べてはパリティ部分の形態が完全下三角行列形態から外れる。図１３において、情報部分の順列行列Ｐの上付き添え字ａｉｊは０≦ａｉｊ≦Ｎｓ-１又はａｉｊ＝∞である。この順列行列Ｐの上付き添え字ａｉｊ＝０である場合、すなわち順列行列Ｐ０は単位行列
【０１０９】
【数１８】
【０１１０】
を示し、順列行列Ｐの上付き添え字ａｉｊ＝∞である場合、すなわち順列行列Ｐ∞はゼロ行列を示す。図１３で、“ｍ”は情報部分にマッピングされる部分ブロックの行の個数を、“ｑ”はパリティ部分にマッピングされる部分ブロックの列の個数を、それぞれ示す。“ｉ”は、対応する順列行列がパリティ検査行列の部分ブロックのｉ番目の行に位置することを意味し、“ｊ”は対応する順列行列がパリティ検査行列の部分ブロックのｊ番目の列に位置することを意味する。すなわち、
【０１１１】
【数１９】
【０１１２】
は、ｉ番目の行とｊ番目の列で交差する部分ブロックに位置する順列行列である。
また、上記のパリティ部分の順列行列の上付き添え字ａｉ、ｘ、ｙは、順列行列Ｐの指数(上付き添え字)を示し、但し、説明の便宜上、このａｉ、ｘ、ｙは情報部分との区分のために相互に異なるように設定しただけである。すなわち、図１３で、
【０１１３】
【数２０】
【０１１４】
も順列行列で、パリティ部分の対角部分に位置する。上付き添え字ａ１〜ａｍは部分行列に順次にインデックスが付けられることを示す。図１３で、ｐｘとｐｙも順列行列で、説明の便宜上、情報部分との区分のために相互に異なるように設定して示す。
【０１１５】
図１３に示すようなパリティ検査行列を有するブロックＬＤＰＣ符号のブロック長さをＮであると仮定すると、ブロックＬＤＰＣ符号の符号化複雑度はブロック長さＮに対して線形的に増加する。
【０１１６】
図１３のパリティ検査行列を有するＬＤＰＣ符号の一番大きい問題点は、部分ブロックの長さがＮｓであるときに、ブロックＬＤＰＣ符号の因子グラフ上に常に次数(ｄｅｇｒｅｅ)が１であるＮｓ個の検査ノードが生成されることである。ここで、次数が１である検査ノードは、反復復号による性能改善に影響を与えることができない。したがって、Ｒｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式に基づいた標準ＬＤＰＣ符号は、次数が１である検査ノードを含んでいない。したがって、次数が１である検査ノードを含まずに効率的な符号化が可能なようにパリティ検査行列を設計するために、図１３のパリティ検査行列を基本的なパリティ検査行列として仮定する。図１３のように、部分行列で構成されたパリティ検査行列で部分行列の選択は、ブロックＬＤＰＣ符号の性能改善において非常に重要な要素で、したがって部分行列の適切な選択基準を探すことも非常に重要な要素となる。
【０１１７】
したがって、ブロックＬＤＰＣ符号の生成において、次のような設計基準を考慮してパリティ検査行列を構成する。
【０１１８】
＜ブロックＬＤＰＣ符号のパリティ検査行列の設計基準＞
【０１１９】
(１)パリティ部分は固定された形態を有するように構成される。
パリティ部分が固定された形態を有するということは、後術する図１６に示すように単位行列が位置する形態を有することを意味する。
【０１２０】
(２)優先的に次数の低い部分行列から順次的に選択する。
本発明で、部分行列の“次数”とは、３と５との間の次数を呼ばれる。また、部分行列は、次数の低い部分行列から順次に選択するときに、ブロックサイクルができるだけ少なく生成されるように配列し、次数の低い部分行列間の最小長さを有するサイクルをできるだけ長く構成する。
【０１２１】
(３)次数の低い部分行列をすべて構成した後に、次数の高い部分行列を順次に構成する。次数の高い部分行列を配列するときに、できるだけ全体的に最小長さのサイクルを長く構成する。
【０１２２】
上記したブロックＬＤＰＣ符号のパリティ検査行列設計基準に基づいて、ブロックＬＤＰＣ符号のパリティ検査行列の設計方法を説明する。
【０１２３】
ここで、ブロックＬＤＰＣ符号のパリティ検査行列の設計方法とブロックＬＤＰＣ符号の符号化方法を容易にするために、図１３に示すようなパリティ検査行列を図１４のように６個の部分行列で構成された形態であると仮定する。
【０１２４】
図１４は、図１３のパリティ検査行列を６個の部分ブロックに分割した図である。図１４を参照すると、図１３に示したように、ブロックＬＤＰＣ符号のパリティ検査行列を情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分ブロックに分割する。ここで、情報部分は、図１２及び図１３で説明した情報部分のようにブロックＬＤＰＣ符号を符号化する過程で、実際の情報語にマッピングされるパリティ検査行列の部分を示し、但し、説明の便宜上、情報部分ｓは参照符号を異にして表示しただけである。また、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２は、図１２及び図１３に説明したパリティ部分のようにブロックＬＤＰＣ符号を符号化する過程で、実際のパリティにマッピングされるパリティ検査行列の部分を示し、パリティ部分を２個の部分に分割した。
【０１２５】
部分行列Ａ、Ｃは情報部分ｓの部分ブロック、すなわち部分ブロックＡ、Ｃに対応し、部分行列Ｂ、Ｄは第１のパリティ部分ｐ１の部分ブロックＢ、Ｄに対応し、部分行列Ｔ、Ｅは第２のパリティ部分ｐ２の部分ブロックＴ、Ｅに対応する。ここで、図１４にパリティ検査行列が７個の部分ブロックに分割されるように示しているが、‘０’は別途の部分ブロックでなく、部分ブロックＴに対応する部分行列Ｔが完全下三角形態を有するため、対角線を中心としてゼロ行列が配置された領域を‘０’で表示する。情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分行列を用いて符号化方法を簡略にする過程は、下記の図１７で説明する。
【０１２６】
以下に、図１４の部分行列は、図１５を参照して説明する。
【０１２７】
図１５は、図１４の部分行列Ｂの転置行列と、部分行列Ｅと、部分行列Ｔと、部分行列Ｔの逆行列を示す図である。図１５を参照すると、
【０１２８】
【数２１】
【０１２９】
を示す。また、図１５に示す順列行列、例えば、
【０１３０】
【数２２】
【０１３１】
は単位行列となりうる。上記したように、順列行列の指数、すなわちａ１が０である場合には、順列行列
【０１３２】
【数２３】
【０１３３】
が単位行列となる。また、順列行列の指数、すなわち、ａ１が予め設定された値により増加する場合には、順列行列が増加した設定値により循環シフトされ、つまり、順列行列
【０１３４】
【数２４】
【０１３５】
が単位行列になる。
【０１３６】
図１７は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列の生成過程を示すフローチャートである。図１７の説明に先立って、ブロックＬＤＰＣ符号を生成するためには、生成しようとするブロックＬＤＰＣ符号の符号語サイズと符号化率を決定し、この決定された符号語サイズと符号化率によりパリティ検査行列のサイズを決定すべきである。ブロックＬＤＰＣ符号の符号語サイズがＮで、符号化率をＲであると仮定すると、パリティ検査行列のサイズはＮ(１-Ｒ)xＮとなる。また、図１７に示すようにブロックＬＤＰＣ符号のパリティ検査行列生成過程は、最初に通信システムのシステム状態に応じて生成され、この生成されたパリティ検査行列を用いることによって、実質的にパリティ検査行列の生成過程は１回のみを遂行すると良い。
【０１３７】
図１７を参照すると、制御器は、ステップ１７１１で、サイズＮ(１-Ｒ)xＮのパリティ検査行列を横軸にｐ個のブロックに分割し、縦軸でｑ個のブロックに分割して総ｐxｑブロックに分割した後に、ステップ１７１３に進行する。ここで、ブロックそれぞれのサイズはＮｓxＮｓであるため、パリティ検査行列はＮｓxｑ個の行と、Ｎｓxｐ個の列で構成される。ステップ１７１３で、制御器は、ｐｘｑ個のブロックに分割したパリティ検査行列を情報部分ｓとパリティ部分、すなわち第１のパリティ部分ｐ１と第２のパリティ部分ｐ２に分類し、ステップ１７１５及びステップ１７２１に進行する。
【０１３８】
ステップ１７１５で、制御器は、情報部分ｓをブロックＬＤＰＣ符号の高性能を保障する次数分布による‘０’でないブロック又は非ゼロ行列、‘０’であるブロック又はゼロ行列であるブロックを決定し、ステップ１７１７に進行する。ここで、ブロックＬＤＰＣ符号の高性能を保障する次数分布は上記したようであるため、その詳細な説明を省略する。ステップ１７１７で、制御器は、ブロックＬＤＰＣ符号の高性能を保障する次数分布により決定したブロックの中に低い次数を有するブロックのうち、非ゼロ行列部分に上記したようにブロックサイクルの最小サイクル長さが最大になるように順列行列
【０１３９】
【数２５】
【０１４０】
を決定し、ステップ１７１９に進行する。ここで、順列行列
【０１４１】
【数２６】
【０１４２】
を決定するとき、情報部分ｓだけでなく第１及び第２のパリティ部分Ｐ１、Ｐ２のブロックサイクルも考慮して決定すべきである。
【０１４３】
ステップ１７１９で、制御器は、ブロックＬＤＰＣ符号の優れた性能を保障する次数分布により決定されたブロックの中に、高い次数を有するブロックのうちの非ゼロ行列部分にランダムに順列行列
【０１４４】
【数２７】
【０１４５】
を決定して終了する。ここで、高い次数を有するブロックのうちの非ゼロ行列部分に適用する順列行列
【０１４６】
【数２８】
【０１４７】
を決定するときにも、ブロックサイクルの最小サイクルサイズが最大になるように順列行列
【０１４８】
【数２９】
【０１４９】
を決定すべきである。また、情報部分ｓだけでなく第１のパリティ部分ｐ１と第２のパリティ部分ｐ２のブロックサイクルも考慮して決定すべきである。上記のように、パリティ検査行列の情報部分ｓに順列行列
【０１５０】
【数３０】
【０１５１】
を配列した形態を図１６に示す。
【０１５２】
ステップ１７２１で、制御器は、第１及び第２のパリティ部分ｐ１、ｐ２を４個の部分行列Ｂ、Ｔ、Ｄ、Ｅに分割した後に、ステップ１７２３に進行する。ステップ１７２３で、制御器は、部分行列Ｂを構成する部分ブロックの中に２個の部分ブロックに０でない順列行列Ｐｙと
【０１５３】
【数３１】
【０１５４】
を入力し、ステップ１７２５に進行する。ここで、部分行列Ｂを構成する部分ブロックの中に２個の部分ブロックに０でない順列行列Ｐｙと
【０１５５】
【数３２】
【０１５６】
を入力する構造は、既に図１５を参照して説明した。
【０１５７】
ステップ１７２５で、制御器は、部分行列Ｔの対角部分ブロックには単位行列Ｉを入力し、部分行列Ｔの対角成分の下に(ｉ，ｉ＋１)番目の部分ブロックには任意の順列行列
【０１５８】
【数３３】
【０１５９】
を入力し、ステップ１７２７に進行する。ここで、部分行列Ｔの対角部分ブロックには単位行列Ｉを入力し、この部分行列Ｔの対角成分の下の(ｉ，ｉ＋１)番目の部分ブロックには任意の順列行列
【０１６０】
【数３４】
【０１６１】
を入力する方法は、図１５を参照して説明した。
【０１６２】
ステップ１７２７で、制御器は、部分行列Ｄに順列行列Ｐｘを入力した後に、ステップ１７２９に進行する。ステップ１７２９で、制御器は、部分行列Ｅには最後の部分ブロックのみに
【０１６３】
【数３５】
【０１６４】
を入力して終了する。ここで、部分行列Ｅを構成する部分ブロックの中に最後の部分ブロックに２個の
【０１６５】
【数３６】
【０１６６】
を入力する構造は、既に図１５を参照して説明した。
【０１６７】
ブロックＬＤＰＣ符号のパリティ検査行列で、部分行列Ｂと、部分行列Ｄ、及び部分行列Ｅを適切に構成すると、ブロックＬＤＰＣ符号の符号化過程を容易に制御することができる。ここで、ブロックＬＤＰＣ符号の符号化過程を容易にするために、パリティ検査行列の部分行列Ｂと、部分行列Ｄ、及び部分行列Ｅを構成する過程について説明する。
【０１６８】
上記に説明したように、図１３のパリティ検査行列を図１４に説明したような部分行列に分割する場合に、図１５のように示すことができる。
【０１６９】
符号語ベクトルｃは図１４に示すように情報部分ｓと、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２に分割する場合に、符号語ベクトルｃは、情報語ベクトルｓ と、第１のパリティベクトルＰ1と、第２のパリティベクトルＰ2に分割可能である。この場合、パリティ検査行列と符号語ベクトルｃの積は、下記の＜式１２＞及び＜式１３＞のように示す。
【０１７０】
【数３７】
【数３８】
【０１７１】
＜式１２＞で、Ｔは転置(ｔｒａｎｓｐｏｓｅ)演算を示し、＜式１３＞で第１のパリティベクトルＰ1と関連した部分、すなわち
【０１７２】
【数３９】
【０１７３】
は下記の＜式１４＞を用いて得られる。
【０１７４】
【数４０】
【０１７５】
＜式１４＞で、行列φのサイズの自乗に比例してブロックＬＤＰＣ符号の符号化複雑度が発生されるため、本発明では第１のパリティベクトルＰ1を求めるために使用される行列φを単位行列Ｉとなるように設定する。このように、行列φを単位行列Ｉになるように設定することによって、ブロックＬＤＰＣ符号の符号化複雑度が最小化される。ここで、図１５を参照して、行列φを単位行列Ｉになるように設定する過程について説明する。
【０１７６】
まず、順列行列
【０１７７】
【数４１】
【０１７８】
は、単位行列Ｉに固定可能である。図１５に示した部分行列Ｔ-１の部分ブロックで、
【０１７９】
【数４２】
【０１８０】
部分は行列
【０１８１】
【数４３】
【０１８２】
から行列
【０１８３】
【数４４】
【０１８４】
までの積である
【０１８５】
【数４５】
【０１８６】
を示す。行列φは、下記の＜式１５＞〜＜式１７＞を用いて求められる。
【０１８７】
まず、図１５で部分行列Ｅは、一つの部分ブロックを除いてはすべてゼロ行列であるため、部分行列Ｅと部分行列Ｔの逆行列であるＴ-1の乗算は部分行列Ｔの逆行列であるＴ-１の最後行と部分行列Ｅの最後ブロックの乗算形態で＜式１５＞のように示す。
【０１８８】
【数４６】
【０１８９】
部分行列Ｅと部分行列Ｔの逆行列Ｔ-１の積に部分行列Ｂを乗算すると、<式１６>のように示す。
【０１９０】
【数４７】
【０１９１】
（ここで、ｋはＰｙの位置により決定される任意の自然数である。）
＜式１６＞に示すように、部分行列Ｅと部分行列Ｔの逆行列であるＴ-１の積に部分行列Ｂを乗算する場合に、部分行列Ｂが２個の部分ブロックを除いてはすべてゼロ行列を含むため、部分行列Ｂの２個のブロックのみに対して乗算を遂行することで、簡単に演算される。
【０１９２】
もし、
【０１９３】
【数４８】
【０１９４】
に設定すると、φ≒ＥＴ-１Ｂ＋Ｄ＝Ｉになる。したがって、行列φは単位行列Ｉとなる。そして、＜式１７＞ は、行列φが単位行列Ｉになる条件を簡略に示すものである。
【０１９５】
【数４９】
【０１９６】
＜式１５＞〜＜式１７＞に示すように、行列φが単位行列Ｉになるように設定すると、ブロックＬＤＰＣ符号の符号化過程は、その複雑度が最小化できる。
【０１９７】
次に、図１８を参照して、本発明によるパリティ検査行列を使用してブロックＬＤＰＣ符号を符号化する過程を説明する。
【０１９８】
図１８は、本発明の実施形態によるブロックＬＤＰＣ符号の符号化過程を示すフローチャートである。図１８を参照すると、制御器は、ステップ１８１１で、ブロックＬＤＰＣ符号で符号化するための情報語ベクトルsを受信し、ステップ１８１３及びステップ１８１５に進行する。ここで、ブロックＬＤＰＣ符号で符号化するために受信された情報語ベクトルsの長さはｋであると仮定する。ステップ１８１３で、制御器は、この情報語ベクトルsとパリティ検査行列（Ａs）の部分行列Ａを行列乗算を遂行した後に(s)、ステップ１８１７に進行する。ここで、部分行列Ａに存在する１の値を有する要素の個数は、０の値を有する要素の個数に比べて非常に少ないため、情報語ベクトルsとパリティ検査行列の部分行列Ａの行列乗算は、比較的少ない回数の和積(ｓｕｍ-ｐｒｏｄｕｃｔ)演算のみで可能になる。また、部分行列Ａで１の値を有する要素の位置は０でないブロック位置とそのブロックの順列行列の指数で示すことができ、それによって、所定のパリティ検査行列に比べて非常に簡単な演算のみでも行列乗算が遂行可能である。ステップ１８１５で、制御器は、パリティ検査行列の部分行列Ｃと情報語ベクトルsの行列乗算を遂行し(Ｃs)、ステップ１８１９に進行する。
【０１９９】
一方、ステップ１８１７で、制御器は、情報語ベクトルsとパリティ検査行列(ＥＴ-１Ａs)の部分行列Ａの行列乗算結果と行列ＥＴ-１の行列乗算を遂行し、ステップ１８１９に進行する。上述したように、行列ＥＴ-１で１の値を有する要素の個数は非常に少ないため、ブロックの順列行列の指数がわかるだけでも、行列乗算を容易に遂行することができる。ステップ１８１９で、制御器は、ＥＴ-１ＡsとＣsを加算して第１のパリティベクトルp1を計算した後(p1＝ＥＴ-1Ａs＋Ｃs )、ステップ１８２１に進行する。ここで、加算演算は、排他的加算(ｅｘｃｌｕｓｉｖｅ ＯＲ)演算で同一のビットが加算されるときには０となり、相違したビットが加算されるときには１となる。その結果、ステップ１８１９までの過程は、＜式１４＞で説明したような第１のパリティベクトルp1を計算するためのことである。
【０２００】
ステップ１８２１で、制御器は、パリティ検査行列の部分行列Ｂと第１のパリティベクトルp1 を乗算し(Ｂp1)、その値にＡsを加算した後に(Ａs＋Ｂp1)、ステップ１８２３に進行する。ここで、＜式１２＞に説明したように、情報語ベクトルsと第１のパリティベクトルp1を知ると、第２のパリティベクトルp2を求めるために、パリティ検査行列の部分行列Ｔの逆行列Ｔ-１を乗算しなければならない。したがって、ステップ１８２３で、制御器は、第２のパリティベクトルp2を求めるために、ステップ１８２１で計算したベクトルに部分行列Ｔの逆行列Ｔ-１を乗算した後（p2＝Ｔ-1(Ａs＋Ｂp1)）、ステップ１８２５に進行する。上記したように、符号化するためのブロックＬＤＰＣ符号の情報語ベクトルsのみを知ると、第１のパリティベクトルp1と、第２のパリティベクトルp2を求めることができ、その結果、符号語ベクトルすべてが得られる。そして、制御器は、ステップ１８２５で、情報語ベクトルsと、第１のパリティベクトルp1と、第２のパリティベクトルp2で生成された符号語ベクトルcを生成して伝送し、上記の手順を終了する。
【０２０１】
図１９は、本発明の実施形態での機能を遂行するためのブロックＬＤＰＣ符号の符号化装置の内部構造を示すブロック構成図である。
【０２０２】
図１９を参照すると、ブロックＬＤＰＣ符号の符号化装置は、行列Ａ乗算器１９１１と、行列Ｃ乗算器１９１３と、行列ＥＴ-１乗算器１９１５と、第１の加算器１９１７と、行列Ｂ乗算器１９１９と、第２の加算器１９２１と、行列ＥＴ-１乗算器１９２３と、スイッチ１９２５，１９２７，１９２９とを含む。
【０２０３】
まず、入力信号、すなわちブロックＬＤＰＣ符号で符号化しようとする長さｋの情報語ベクトルsが入力され、入力された長さｋの情報語ベクトルsはスイッチ１９２５、行列Ａ乗算器１９１１、及び行列Ｃ乗算器１９１３に入力される。この行列Ａ乗算器１９１１は、情報語ベクトルsと全体パリティ検査行列の部分行列Ａを乗算した後に、行列ＥＴ-1乗算器１９１５と加算器１９２１に出力する。また、行列Ｃ乗算器１９１３は、情報語ベクトルsと全体パリティ検査行列の部分行列Ｃを乗算した後に、第１の加算器１９１７に出力する。行列ＥＴ-１を乗算器１９１５は、行列Ａ乗算器１９１１から出力した信号に全体パリティ検査行列の部分行列ＥＴ-１を乗算した後に、第１の加算器１９１７に出力する。
【０２０４】
第１の加算器１９１７は、行列ＥＴ-１乗算器１９１５から出力された信号と行列Ｃ乗算器１９１３から出力された信号を入力して加算した後に、行列Ｂ乗算器１９１９及びスイッチ１９２７に出力する。ここで、第１の加算器１９１７は、ビット別に排他的論理和(ＸＯＲ)演算を遂行する。例えば、長さ３であるベクトルｘ＝(ｘ１，ｘ２，ｘ３)と長さ３であるベクトルｙ＝(ｙ１，ｙ２，ｙ３)が加算器１９１７に入力される場合に、加算器１９１７は長さ３であるベクトルｘ＝(ｘ１，ｘ２，ｘ３)と長さ３であるベクトルｙ＝(ｙ１，ｙ２，ｙ３)を排他的論理和演算して長さ３であるベクトル
【０２０５】
【数５０】
【０２０６】
同一のビットが演算されると０になり、相異なるビットが演算されると１になる排他的論理和演算を示す。すなわち、第１の加算器１９１７から出力される信号が第１のパリティベクトルp1になる。
【０２０７】
また、行列Ｂ乗算器１９１９は、第１の加算器１９１７から出力された信号、すなわち第１のパリティベクトルp1を入力して全体パリティ検査行列の部分行列Ｂを乗算した後に、加算器１９２１に出力する。加算器１９２１は、行列Ｂ乗算器１９１９から出力された信号と行列Ａ乗算器１９１１から出力された信号を加算した後に、行列Ｔ-１乗算器１９２３に出力する。ここで、加算器１９２１は、加算器１９１７で説明したように、行列Ｂ乗算器１９１９から出力された信号と行列Ａ乗算器１９１１から出力された信号を排他的論理和演算した後に、行列Ｔ-１乗算器１９２３に出力する。
【０２０８】
行列Ｔ-１乗算器１９２３は、加算器１９２１から出力された信号と行列Ｔ-１を乗算した後に、スイッチ１９２９に出力する。ここで、行列Ｔ-１乗算器１９２３の出力が、結局第２のパリティベクトルp2になる。一方、スイッチ１９２５，１９２７，１９２９は、各々自分の伝送する時点のみでスイッチオン(ｓｗｉｔｃｈ ｏｎ)されて該当信号を伝送する。すなわち、情報語ベクトルsが伝送される時点で、スイッチ１９２５がスイッチオンされ、第１のパリティベクトルp1が伝送される時点でスイッチ１９２７がスイッチオンされ、第２のパリティベクトルp2が伝送される時点でスイッチ１９２９がスイッチオンされる。
【０２０９】
上記したように、全体パリティ検査行列の部分行列を適切に選択することによって、行列乗算ＥＴ-１が比較的簡単になり、それによって、ＥＴ-１ＡsＴの計算が容易になる。なお、行列φが単位行列Ｉになってp1Ｔを計算するためのφ-１の演算過程が省略される。
【０２１０】
上記では、効率的な符号化を考慮したブロックＬＤＰＣ符号の生成方法について説明した。上記のブロックＬＤＰＣ符号は、ブロックＬＤＰＣ符号の構造的な特性によって、パリティ検査行列に関連した情報を貯蔵するためのメモリ効率が高いだけでなく、パリティ検査行列で部分行列を適切に選択することによって効率的な符号化が可能になる。しかしながら、ブロック単位でパリティ検査行列を生成することによって、不規則性(ｒａｎｄｏｍｎｅｓｓ）は減少し、それによるブロックＬＤＰＣ符号の性能の劣化をもたらす。すなわち、上記のように、不均一ブロックＬＤＰＣ符号が均一ブロックＬＤＰＣ符号に比べて性能が良いため、ブロックＬＤＰＣ符号を設計することにおいて、全体パリティ検査行列で部分行列を選択することは非常に重要な要素として作用するようになる。
【０２１１】
ここで、図１６を参照してブロックＬＤＰＣ符号のサイクル特性を考慮して効率的な符号化が可能であり、かつ優れた性能を有するブロックＬＤＰＣ符号の具体的な生成方法について説明する。
【０２１２】
図１６は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列を示す図である。図１６を参照すると、ブロックＬＤＰＣ符号のパリティ検査行列は構造の単純性を考慮して、上述したように
【０２１３】
【数５１】
【０２１４】
に設定する。この場合、行列φは単位行列Ｉとなって効率的な符号化を可能にする。ここで、パリティ検査行列の部分行列のブロック長さＮｓ＝３１で、したがってＰ-１＝Ｐ３０である。パリティ検査行列の全体列に対するブロックの個数は３２個であるため、全体ブロック長さが３２x３１＝９９２で、符号化率１/２のブロックＬＤＰＣ符号のパリティ検査行列が生成される。
【０２１５】
その結果、図１６に示すようにブロックＬＤＰＣ符号は、パリティ検査行列の列を基準としてウェイト値が２である１５個のブロックと、ウェイト値が３である１２個のブロックと、ウェイト値が１１である５個のブロックで構成された不均一ブロックＬＤＰＣ符号になる。したがって、図１６に示すように、ブロックＬＤＰＣ符号の次数分布は、下記の＜式１８＞のように示す。
【０２１６】
【数５２】
【０２１７】
＜式１８＞で、ｆｉはブロックＬＤＰＣ符号の因子グラフで全体変数ノードに対する次数がｉである変数ノードの比率を示し、ｆρｉはブロックＬＤＰＣ符号の因子グラフで全体検査ノードに対する次数がｉである検査ノードの比率を示す。その一例として、ブロック長さがＮｓ＝３２であるブロックＬＤＰＣ符号において、ブロックＬＤＰＣ符号の因子グラフ上で全体３２個の変数ノードの中に１５個の変数ノードに該当するパリティ検査行列の列がウェイト値３２を有し、１２個の変数ノードに該当するパリティ検査行列の列がウェイト値３を有し、５個の変数ノードに該当するパリティ検査行列の列がウェイト値１１を有する。これら変数ノードだけでなく、検査ノードに対応するパリティ検査行列に対しても、変数ノードに対して遂行したことと同一の形態でウェイト値を考慮することができる。一方、＜式１８＞に示すように、次数分布は、しきい値(ｔｈｒｅｓｈｏｌｄ ｖａｌｕｅ)を有するＬＤＰＣ符号の次数分布にほとんど近接した形態を有する。また、図１６に示しているブロックＬＤＰＣ符号の場合は、次数が２，３であるノード間に存在するサイクルの最小サイズが１２であり、全体ノード間の場合は最小サイズが６である。
【０２１８】
次に、図２０を参照して、本発明の実施形態によるパリティ検査行列を用いてブロックＬＤＰＣ符号を復号する段階について説明する。
【０２１９】
図２０は、本発明の実施形態によりブロックＬＤＰＣ符号の復号装置の内部構造を示す図である。図２０を参照すると、ブロックＬＤＰＣ符号の復号装置は、変数ノード部２０００と、加算器２０１５と、デインタリーバ(ｄｅｉｎｔｅｒｌｅａｖｅｒ)２０１７と、インタリーバ２０１９と、制御器２０２１と、メモリ２０２３と、加算器２０２５と、検査ノード部２０５０と、硬判定器２０２９とを含んで構成される。変数ノード部２０００は、変数ノード復号器２０１１と、スイッチ２０１３で構成され、検査ノード部２０５０は検査ノード復号器２０２７で構成される。
【０２２０】
無線チャンネルを通じて受信される受信信号は、変数ノード部２０００の変数ノード復号器２０１１に入力される。変数ノード復号器２０１１は、この受信された受信信号の確率値を計算し、計算された確率値をアップデートした後にスイッチ２０１３及び加算器２０１５に出力する。ここで、変数ノード復号器２０１１は、ブロックＬＤＰＣ符号の復号装置に予め設定されているパリティ検査行列に対応して変数ノードを接続し、変数ノードに接続された‘１’の個数だけの入力値と出力値を有するアップデート演算が遂行される。変数ノードの各々に接続された‘１’の個数は、パリティ検査行列を構成する列のそれぞれのウェイト値と同一である。したがって、パリティ検査行列を構成する列のそれぞれのウェイトにより、変数ノード復号器２０１１の内部演算が異なるように遂行される。
【０２２１】
第１の加算器２０１５は、変数ノード復号器２０１１から出力される信号と以前反復復号過程でインタリーバ２０１９の出力信号を入力し、変数ノード復号器２０１１からの信号から以前反復復号過程でインタリーバ２０１９の出力信号を減算した後に、デインタリーバ２０１７に出力する。ここで、復号過程が最初の復号過程である場合に、インタリーバ２０１９の出力信号は‘０’であるとみなすことはもちろんである。
【０２２２】
デインタリーバ２０１７は、第１の加算器２０１５から出力された信号を入力して予め設定されている設定方式に対応してデインタリービングした後に、第２の加算器２０２５と検査ノード復号器２０２７に出力する。ここで、デインタリーバ２０１７の内部構造は、パリティ検査行列に対応する構造を有し、その理由は、パリティ検査行列の‘１’の値を有する要素の位置によりデインタリーバ２０１７に対応するインタリーバ２０１９の入力値に対する出力値が相互に異なるためである。
【０２２３】
第２の加算器２０２５は、以前反復復号過程での検査ノード復号器２０２７の出力信号とデインタリーバ２０１７の出力信号を受信し、以前反復復号過程での検査ノード復号器２０２７の出力信号からデインタリーバ２０１７の出力信号を減算した後に、インタリーバ２０１９に出力する。検査ノード復号器２０２７は、ブロックＬＤＰＣ符号の復号装置に予め設定されているパリティ検査行列に対応して検査ノードを接続し、検査ノードに接続された‘１’の個数だけの入力値と出力値を有するアップデート演算が遂行される。検査ノードの各々に接続された‘１’の個数は、パリティ検査行列を構成する行のそれぞれのウェイト値と同一である。したがって、パリティ検査行列を構成する行のそれぞれのウェイト値により検査ノード復号器２０２７の内部演算が相互に異なるようになる。
【０２２４】
インタリーバ２０１９は、制御器２０２１の制御によって予め設定されている設定方式で、加算器２０２５から出力された信号をインタリービングした後に、加算器２０１５及び変数ノード復号器２０１１に出力する。ここで、制御器２０２１は、メモリ２０２３に貯蔵されているインタリービング方式に関連した情報を読み出してインタリーバ２０１９のインタリービング方式を制御するようになる。また、この復号化過程が最初の復号過程である場合には、デインタリーバ２０１７の出力信号は‘０’であるとみなすことはもちろんである。
【０２２５】
上記のような過程を反復して遂行することによって、誤りなしの高信頼度の復号化を遂行し、予め設定された設定反復回数に該当する反復復号化を遂行した後に、スイッチ２０１３は変数ノード復号器２０１１と加算器２０１５との間をスイッチオフする。その後、スイッチ２０１３は、変数ノード復号器２０１１と硬判定器２０２９との間をスイッチオンして変数ノード復号器２０１１から出力された信号を硬判定器２０２９に出力する。硬判定器２０２９は、変数ノード復号器２０１１から出力された信号を入力して硬判定した後に、その硬判定結果を出力し、この硬判定器２０２９の出力値が最終的に復号された値になる。
【図面の簡単な説明】
【０２２６】
【図１】一般的な(８，２，４)ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図２】図１の(８，２，４)ＬＤＰＣ符号の因子グラフを示す図である。
【図３】一般的なブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。
【図４】図３の循環行列Ｐを示す図である。
【図５】一般的な均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図６】一般的な不均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図７】パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【図８】パリティ検査行列が６個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構造を概略的に示す図である。
【図９】ブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１０】パリティ検査行列の６個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１１】パリティ検査行列の７個の部分行列が重複されたブロックＬＤＰＣ符号のブロックサイクル構造を概略的に示す図である。
【図１２】完全下三角行列形態を有するパリティ検査行列を示す図である。
【図１３】完全下三角行列形態に類似した形態を有するパリティ検査行列を示す図である。
【図１４】図１３のパリティ検査行列を６個の部分ブロックに分割した図である。
【図１５】図１４の部分行列Ｂの転置行列と、部分行列Ｅと、部分行列Ｔと、部分行列Ｔの逆行列を示す図である。
【図１６】本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図１７】本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列の生成過程を示すフローチャートである。
【図１８】本発明の実施形態によるブロックＬＤＰＣ符号の符号化過程を示すフローチャートである。
【図１９】本発明の実施形態によるブロックＬＤＰＣ符号の符号化装置の内部構造を示すブロック構成図である。
【図２０】本発明の実施形態によるブロックＬＤＰＣ符号の復号装置の内部構造を示す図である。
【符号の説明】
【０２２７】
１９１１ 行列Ａ乗算器
１９１３ 行列Ｃ乗算器
１９１５ 行列ＥＴ-１乗算器
１９１７ 第１の加算器
１９１９ 行列Ｂ乗算器
１９２１ 第２の加算器
１９２３ 行列ＥＴ-１乗算器
１９２５，１９２７，１９２９ スイッチ
【特許請求の範囲】
【請求項１】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号装置であって、
所定の制御により、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、
前記変数ノード復号器から出力された信号から以前復号時に生成された信号を減算して出力する第１の加算器と、
前記第１の加算器から出力された信号を入力して前記パリティ検査行列に対応して設定されたデインタリービング方式でデインタリービングして出力するデインタリーバと、
所定の制御信号により、前記パリティ検査行列を構成する行のそれぞれのウェイトに対応して検査ノードを接続し、前記デインタリーバからの出力信号の確率値を検出して出力する検査ノード復号器と、
前記検査ノード復号器の出力信号から、前記デインタリーバから出力された信号を減算する第２の加算器と、
前記第２の加算器から出力された信号を前記パリティ検査行列により設定されたインタリービング方式でインタリービングして前記変数ノード復号器及び前記第１の加算器に出力するインタリーバと、
前記パリティ検査行列を生成し、前記デインタリービング方式及びインタリービング方式を前記パリティ検査行列に対応して制御する制御器と、
を含むことを特徴とする装置。
【請求項２】
前記制御器は、前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に対応するようにパリティ検査行列のサイズを決定し、前記決定されたサイズのパリティ検査行列を予め定められた設定個数のブロックに分割し、前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類し、前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形で単位行列を配列した後に、前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値を不均一にするように前記順列行列を配列して前記パリティ検査行列を生成することを特徴とする請求項１記載の装置。
【請求項３】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２記載の装置。
【請求項４】
前記制御器は、前記情報部分に分類されたブロックの中に前記順列行列が配列されるブロックを決定し、前記順列行列が配列されるように決定されたブロックの中に予め設定された次数未満の次数を有するブロックに対しては前記最小サイクル長さが最大になるように前記順列行列を配列した後に、前記順列行列が配列されるように決定されたブロックの中に前記設定された次数以上の次数を有するブロックに対してはランダムに前記順列行列を配列することを特徴とする請求項３記載の装置。
【請求項５】
前記制御器は、前記第１のパリティ部分を構成するブロックを第１の部分ブロックに対応するブロックと第２の部分ブロックに対応するブロックに分割し、前記第２のパリティ部分を構成するブロックを第３の部分ブロックに対応するブロックと第４の部分ブロックに対応するブロックに分類し、前記第１の部分ブロック及び第２の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列し、前記第３の部分ブロックに分類されたブロックの中に予め定められたブロックに前記完全下三角形で単位行列を配列した後に、前記第４の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列することを特徴とする請求項３記載の装置。
【請求項６】
前記制御器は、前記第３の部分ブロックに分類されたブロックの中に対角をなすブロックに前記単位行列を配列することを特徴とする請求項５記載の装置。
【請求項７】
前記制御器は、前記第３の部分ブロックに分類されたブロックの中に前記単位行列が配列されたブロックと平行した下位ブロックに前記順列行列を配列することを特徴とする請求項５記載の装置。
【請求項８】
前記制御器は、前記第４の部分ブロックに分類されたブロックの中に最後ブロックに前記順列行列を配列することを特徴とする請求項５記載の装置。
【請求項９】
前記制御器は、前記第４の部分ブロックに配列された順列行列、前記第３の部分ブロックに配列された順列行列の逆行列、前記第１の部分ブロックに配列された順列行列の行列の積と前記第２の部分ブロックに配列された順列行列とを加算することによって前記順列行列になるように決定することを特徴とする請求項５記載の装置。
【請求項１０】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号方法であって、
情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を生成し、前記パリティ検査行列に対応してデインタリービング方式及びインタリービング方式を決定する段階と、
受信信号の確率値を検出する段階と、
前記受信信号の確率値から以前復号時に生成された信号を減算して第１の信号を生成する段階と、
前記第１の信号を入力して前記デインタリービング方式でデインタリービングする段階と、
前記デインタリービングされた信号を入力して確率値を検出する段階と、
前記デインタリービングされた信号の確率値で前記デインタリービングされた信号を減算して第２の信号を生成する段階と、
前記第２の信号を前記インタリービング方式でインタリービングし、前記インタリービングされた信号を反復復号する段階と、
を含むことを特徴とする方法。
【請求項１１】
前記パリティ検査行列を生成する段階は、
前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に基づいて前記パリティ検査行列のサイズを決定する段階と、
前記決定されたサイズのパリティ検査行列を予め定められた個数のブロックに分割する段階と、
前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類する段階と、
前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形態で順列行列を配列する段階と、
前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一になるように前記順列行列を配列する段階と、
を有することを特徴とする請求項１０記載の方法。
【請求項１２】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項１１記載の方法。
【請求項１３】
前記情報部分に分類されたブロックにウェイト値が不均一にするように前記順列行列を配列する段階は、
前記情報部分に分類されたブロックの中に前記順列行列が配列されるブロックを決定する段階と、
前記順列行列が配列されるように決定されたブロックの中に予め設定された次数未満の次数を有するブロックに対しては前記最小サイクル長さが最大になるように前記順列行列を配列する段階と、
前記順列行列が配列されるように決定されたブロックのうちに、前記設定次数以上の次数を有するブロックに対してはランダムに前記順列行列を配列する段階と、
を有することを特徴とする請求項１２記載の方法。
【請求項１４】
前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形で単位行列を配列する段階は、
前記第１のパリティ部分を構成するブロックを第１の部分ブロックに対応するブロックと第２の部分ブロックに対応するブロックに分割し、前記第２のパリティ部分を構成するブロックを第３の部分ブロックに対応するブロックと第４の部分ブロックに対応するブロックに分類する段階と、
前記第１の部分ブロック及び第２の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列する段階と、
前記第３の部分ブロックに分類されたブロックの中に予め定められたブロックに前記完全下三角形で単位行列を配列する段階と、
前記第４の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列する段階と、
を有することを特徴とする請求項１２記載の方法。
【請求項１５】
前記第３の部分ブロックに分類されたブロックの中に前記単位行列が配列されるブロックは、前記第３の部分ブロックに分類されたブロックの中に対角をなすブロックであることを特徴とする請求項１４記載の方法。
【請求項１６】
前記第３の部分ブロックに分類されたブロックの中に、前記単位行列が配列されたブロックと平行した下位ブロックに前記順列行列を配列する段階をさらに有することを特徴とする請求項１４記載の方法。
【請求項１７】
前記第４の部分ブロックに分類されたブロックの中に、前記順列行列が配列されるブロックは前記第４の部分ブロックに分類されたブロックの中に最後ブロックであることを特徴とする請求項１４記載の方法。
【請求項１８】
前記第４の部分ブロックに配列された順列行列、前記第３の部分ブロックに配列された順列行列の逆行列、前記第１の部分ブロックに配列された順列行列の行列の積と前記第２の部分ブロックに配列された順列行列とを加算した行列が単位行列になるように前記順列行列を決定することを特徴とする請求項１４記載の方法。
【請求項１９】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化装置であって、
情報語を入力して予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算する第１の行列乗算器と、
前記情報語を入力して前記パリティ検査行列の第２の部分行列と乗算する第２の行列乗算器と、
前記第１の行列乗算器から出力された信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第３の行列乗算器と、
前記第２の行列乗算器から出力された信号と第３の行列乗算器から出力された信号とを加算する第１の加算器と、
前記第１の加算器から出力された信号と前記パリティ検査行列の第５の部分行列とを乗算する第４の行列乗算器と、
前記第２の行列乗算器から出力された信号と前記第４の行列乗算器から出力された信号とを加算する第２の加算器と、
前記第２の加算器から出力された信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第５の行列乗算器と、
前記情報語と、前記第１の加算器の出力信号を第１のパリティとし、前記第５の行列乗算器の出力信号を第２のパリティとして前記ブロックＬＤＰＣ符号フォーマットに相応するように多重化して出力するスイッチと、
を含むことを特徴とする装置。
【請求項２０】
前記第１の部分行列及び第２の部分行列は前記情報部分に対応する部分行列で、前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一にするように前記順列行列を配列された行列であることを特徴とする請求項１９記載の装置。
【請求項２１】
前記第３の部分行列と第４の部分行列は前記第１のパリティ部分に対応する部分行列で、前記第５の部分行列と第６の部分行列は前記第２のパリティ部分に対応する部分行列で、前記第３の部分行列と第４の部分行列は予め定められた位置に順列行列が配列された行列で、前記第５の部分行列は完全下三角形で単位行列が配列された行列であることを特徴とする請求項１９記載の装置。
【請求項２２】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２１記載の方法。
【請求項２３】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化方法であって、
情報語と予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算して第１の信号を生成する段階と、
前記情報語と前記パリティ検査行列の第２の部分行列と乗算して第２の信号を生成する段階と、
前記第１の信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第３の信号を生成する段階と、
前記第２の信号と第３の信号を加算して第４の信号を生成する段階と、
前記第４の信号と前記パリティ検査行列の第５の部分行列を乗算して第５の信号を生成する段階と、
前記第２の信号と前記第５の信号を加算して第６の信号を生成する段階と、
前記第６の信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第７の信号を生成する段階と、
前記情報語と、前記第４の信号を第１のパリティで、前記第７の信号を第２のパリティとし、前記ブロックＬＤＰＣ符号フォーマットに対応するように多重化して出力する段階と、
を有することを特徴とする方法。
【請求項２４】
前記第１の部分行列及び第２の部分行列は前記情報部分に対応する部分行列で、前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一にするように前記順列行列を配列された行列であることを特徴とする請求項２３記載の方法。
【請求項２５】
前記第３の部分行列と第４の部分行列は前記第１のパリティ部分に対応する部分 行列で、前記第５の部分行列と第６の部分行列は前記第２のパリティ部分に対応する部分行列で、前記第３の部分行列と第４の部分行列は予め定められた位置に順列行列が配列された行列で、前記第５の部分行列は完全下三角形で単位行列が配列された行列であることを特徴とする請求項２３記載の方法。
【請求項２６】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２５記載の方法。
【請求項２７】
パリティ検査行列は、複数の情報部分ブロックと複数のパリティ部分ブロックの行と列の行列形態で配列され、前記パリティ検査行列は前記情報部分ブロックの行列で構成された情報部分と前記パリティ部分ブロックの行列で構成されたパリティ部分に区分され、前記情報部分ブロックの各々は複数の情報ビットを示す行列で構成され、前記パリティ部分ブロックの各々は、複数のパリティビットを示す行列で構成され、前記パリティ検査行列は複数の行に存在する情報部分ブロックとパリティ部分ブロックが各々第１の情報行列と第１のパリティ行列及び第２のパリティ行列に分割され、前記複数の行を除いた残りの行に存在する情報部分ブロックとパリティ部分ブロックが各々第２の情報行列と第３のパリティ行列及び第４のパリティ行列に分割され、前記第１及び第２の情報行列と、第１及び第３のパリティ行列と、第２及び第４のパリティ行列は各々同一の列に配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、
前記第４のパリティ行列と第２のパリティ行列の逆行列と前記第１のパリティ行列の積と前記第３のパリティ行列の和が単位行列になるように設定する段階と、
前記第１のパリティ行列と前記第３のパリティ行列に対応する第１のパリティベクトルの転置ベクトルは、前記第４のパリティ行列と前記第２のパリティ行列の逆行列と前記第１の情報行列の積と前記第２の情報行列の和を前記第１の情報行列と前記第２の情報行列に対応する情報ベクトルを乗算した値になるように決定する段階と、
前記第２のパリティ行列と第４のパリティ行列に対応する第２のパリティベクトルの転置ベクトルは、前記第２のパリティ行列の逆行列と前記第１の情報行列と前記情報ベクトルの転置ベクトルを乗算した値と前記第１のパリティ行列と前記第１のパリティベクトルの転置ベクトルを乗算した値を加算した値を乗算した値になるように決定する段階と、
を有することを特徴とする方法。
【請求項２８】
前記第２のパリティ行列は完全下三角行列であることを特徴とする請求項２７記載の方法。
【請求項２９】
前記第１の情報行列及び第２の情報行列は不均一のウェイト値を有することを特徴とする請求項２７記載の方法。
【請求項３０】
ブロック低密度パリティ検査(ＬＤＰＣ)符号のパリティ検査行列は、複数の部分ブロックの行と列の行列形態で配列され、前記複数の部分ブロック各々にはＮｓxＮｓサイズを有する行列が前記複数の部分ブロックの各々に対応して予め定められた指数だけシフトして生成された順列行列が配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、
前記ブロックＬＤＰＣ符号のブロックサイクルを任意の第１の値に決定する段階と、
前記ブロックサイクルを決定した後に、前記部分ブロックの各々に配列された順列行列の中に、その指数が奇数である順列行列の指数の和から前記部分ブロックの各々に配列された順列行列のうち、その指数が偶数である順列行列の指数の和を減算した値と任意の第２の値を乗算した値になるように前記第２の値を決定し、前記部分ブロックの各々が前記第１の値と第２の値を乗算した値に対応するサイクルを有するように制御する段階と、
を有することを特徴とする方法。
【請求項３１】
前記指数は１以上で、前記第１の値以下であることを特徴とする請求項３０記載の方法。
【請求項１】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号装置であって、
所定の制御により、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を構成する列のそれぞれのウェイトにより変数ノードを接続して受信信号の確率値を検出して出力する変数ノード復号器と、
前記変数ノード復号器から出力された信号から以前復号時に生成された信号を減算して出力する第１の加算器と、
前記第１の加算器から出力された信号を入力して前記パリティ検査行列に対応して設定されたデインタリービング方式でデインタリービングして出力するデインタリーバと、
所定の制御信号により、前記パリティ検査行列を構成する行のそれぞれのウェイトに対応して検査ノードを接続し、前記デインタリーバからの出力信号の確率値を検出して出力する検査ノード復号器と、
前記検査ノード復号器の出力信号から、前記デインタリーバから出力された信号を減算する第２の加算器と、
前記第２の加算器から出力された信号を前記パリティ検査行列により設定されたインタリービング方式でインタリービングして前記変数ノード復号器及び前記第１の加算器に出力するインタリーバと、
前記パリティ検査行列を生成し、前記デインタリービング方式及びインタリービング方式を前記パリティ検査行列に対応して制御する制御器と、
を含むことを特徴とする装置。
【請求項２】
前記制御器は、前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に対応するようにパリティ検査行列のサイズを決定し、前記決定されたサイズのパリティ検査行列を予め定められた設定個数のブロックに分割し、前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類し、前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形で単位行列を配列した後に、前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値を不均一にするように前記順列行列を配列して前記パリティ検査行列を生成することを特徴とする請求項１記載の装置。
【請求項３】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２記載の装置。
【請求項４】
前記制御器は、前記情報部分に分類されたブロックの中に前記順列行列が配列されるブロックを決定し、前記順列行列が配列されるように決定されたブロックの中に予め設定された次数未満の次数を有するブロックに対しては前記最小サイクル長さが最大になるように前記順列行列を配列した後に、前記順列行列が配列されるように決定されたブロックの中に前記設定された次数以上の次数を有するブロックに対してはランダムに前記順列行列を配列することを特徴とする請求項３記載の装置。
【請求項５】
前記制御器は、前記第１のパリティ部分を構成するブロックを第１の部分ブロックに対応するブロックと第２の部分ブロックに対応するブロックに分割し、前記第２のパリティ部分を構成するブロックを第３の部分ブロックに対応するブロックと第４の部分ブロックに対応するブロックに分類し、前記第１の部分ブロック及び第２の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列し、前記第３の部分ブロックに分類されたブロックの中に予め定められたブロックに前記完全下三角形で単位行列を配列した後に、前記第４の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列することを特徴とする請求項３記載の装置。
【請求項６】
前記制御器は、前記第３の部分ブロックに分類されたブロックの中に対角をなすブロックに前記単位行列を配列することを特徴とする請求項５記載の装置。
【請求項７】
前記制御器は、前記第３の部分ブロックに分類されたブロックの中に前記単位行列が配列されたブロックと平行した下位ブロックに前記順列行列を配列することを特徴とする請求項５記載の装置。
【請求項８】
前記制御器は、前記第４の部分ブロックに分類されたブロックの中に最後ブロックに前記順列行列を配列することを特徴とする請求項５記載の装置。
【請求項９】
前記制御器は、前記第４の部分ブロックに配列された順列行列、前記第３の部分ブロックに配列された順列行列の逆行列、前記第１の部分ブロックに配列された順列行列の行列の積と前記第２の部分ブロックに配列された順列行列とを加算することによって前記順列行列になるように決定することを特徴とする請求項５記載の装置。
【請求項１０】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の復号方法であって、
情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列を生成し、前記パリティ検査行列に対応してデインタリービング方式及びインタリービング方式を決定する段階と、
受信信号の確率値を検出する段階と、
前記受信信号の確率値から以前復号時に生成された信号を減算して第１の信号を生成する段階と、
前記第１の信号を入力して前記デインタリービング方式でデインタリービングする段階と、
前記デインタリービングされた信号を入力して確率値を検出する段階と、
前記デインタリービングされた信号の確率値で前記デインタリービングされた信号を減算して第２の信号を生成する段階と、
前記第２の信号を前記インタリービング方式でインタリービングし、前記インタリービングされた信号を反復復号する段階と、
を含むことを特徴とする方法。
【請求項１１】
前記パリティ検査行列を生成する段階は、
前記情報語を前記ブロックＬＤＰＣ符号で符号化するときに適用される符号化率と、符号語長に基づいて前記パリティ検査行列のサイズを決定する段階と、
前記決定されたサイズのパリティ検査行列を予め定められた個数のブロックに分割する段階と、
前記ブロックを前記情報部分に対応するブロックと、前記第１のパリティ部分に対応するブロックと、前記第２のパリティ部分に対応するブロックに分類する段階と、
前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形態で順列行列を配列する段階と、
前記情報部分に分類されたブロックに前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一になるように前記順列行列を配列する段階と、
を有することを特徴とする請求項１０記載の方法。
【請求項１２】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項１１記載の方法。
【請求項１３】
前記情報部分に分類されたブロックにウェイト値が不均一にするように前記順列行列を配列する段階は、
前記情報部分に分類されたブロックの中に前記順列行列が配列されるブロックを決定する段階と、
前記順列行列が配列されるように決定されたブロックの中に予め設定された次数未満の次数を有するブロックに対しては前記最小サイクル長さが最大になるように前記順列行列を配列する段階と、
前記順列行列が配列されるように決定されたブロックのうちに、前記設定次数以上の次数を有するブロックに対してはランダムに前記順列行列を配列する段階と、
を有することを特徴とする請求項１２記載の方法。
【請求項１４】
前記第１のパリティ部分に分類されたブロックの中に予め定められたブロックに順列行列を配列し、前記第２のパリティ部分に分類されたブロックの中に予め定められたブロックに完全下三角形で単位行列を配列する段階は、
前記第１のパリティ部分を構成するブロックを第１の部分ブロックに対応するブロックと第２の部分ブロックに対応するブロックに分割し、前記第２のパリティ部分を構成するブロックを第３の部分ブロックに対応するブロックと第４の部分ブロックに対応するブロックに分類する段階と、
前記第１の部分ブロック及び第２の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列する段階と、
前記第３の部分ブロックに分類されたブロックの中に予め定められたブロックに前記完全下三角形で単位行列を配列する段階と、
前記第４の部分ブロックに分類されたブロックの中に予め定められたブロックに前記順列行列を配列する段階と、
を有することを特徴とする請求項１２記載の方法。
【請求項１５】
前記第３の部分ブロックに分類されたブロックの中に前記単位行列が配列されるブロックは、前記第３の部分ブロックに分類されたブロックの中に対角をなすブロックであることを特徴とする請求項１４記載の方法。
【請求項１６】
前記第３の部分ブロックに分類されたブロックの中に、前記単位行列が配列されたブロックと平行した下位ブロックに前記順列行列を配列する段階をさらに有することを特徴とする請求項１４記載の方法。
【請求項１７】
前記第４の部分ブロックに分類されたブロックの中に、前記順列行列が配列されるブロックは前記第４の部分ブロックに分類されたブロックの中に最後ブロックであることを特徴とする請求項１４記載の方法。
【請求項１８】
前記第４の部分ブロックに配列された順列行列、前記第３の部分ブロックに配列された順列行列の逆行列、前記第１の部分ブロックに配列された順列行列の行列の積と前記第２の部分ブロックに配列された順列行列とを加算した行列が単位行列になるように前記順列行列を決定することを特徴とする請求項１４記載の方法。
【請求項１９】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化装置であって、
情報語を入力して予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算する第１の行列乗算器と、
前記情報語を入力して前記パリティ検査行列の第２の部分行列と乗算する第２の行列乗算器と、
前記第１の行列乗算器から出力された信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第３の行列乗算器と、
前記第２の行列乗算器から出力された信号と第３の行列乗算器から出力された信号とを加算する第１の加算器と、
前記第１の加算器から出力された信号と前記パリティ検査行列の第５の部分行列とを乗算する第４の行列乗算器と、
前記第２の行列乗算器から出力された信号と前記第４の行列乗算器から出力された信号とを加算する第２の加算器と、
前記第２の加算器から出力された信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算する第５の行列乗算器と、
前記情報語と、前記第１の加算器の出力信号を第１のパリティとし、前記第５の行列乗算器の出力信号を第２のパリティとして前記ブロックＬＤＰＣ符号フォーマットに相応するように多重化して出力するスイッチと、
を含むことを特徴とする装置。
【請求項２０】
前記第１の部分行列及び第２の部分行列は前記情報部分に対応する部分行列で、前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一にするように前記順列行列を配列された行列であることを特徴とする請求項１９記載の装置。
【請求項２１】
前記第３の部分行列と第４の部分行列は前記第１のパリティ部分に対応する部分行列で、前記第５の部分行列と第６の部分行列は前記第２のパリティ部分に対応する部分行列で、前記第３の部分行列と第４の部分行列は予め定められた位置に順列行列が配列された行列で、前記第５の部分行列は完全下三角形で単位行列が配列された行列であることを特徴とする請求項１９記載の装置。
【請求項２２】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２１記載の方法。
【請求項２３】
ブロック低密度パリティ検査(ＬＤＰＣ)符号の符号化方法であって、
情報語と予め生成されている、情報語に対応する情報部分と、パリティに対応する第１のパリティ部分及び第２のパリティ部分で構成される前記パリティ検査行列の第１の部分行列と乗算して第１の信号を生成する段階と、
前記情報語と前記パリティ検査行列の第２の部分行列と乗算して第２の信号を生成する段階と、
前記第１の信号と、前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第３の信号を生成する段階と、
前記第２の信号と第３の信号を加算して第４の信号を生成する段階と、
前記第４の信号と前記パリティ検査行列の第５の部分行列を乗算して第５の信号を生成する段階と、
前記第２の信号と前記第５の信号を加算して第６の信号を生成する段階と、
前記第６の信号と前記パリティ検査行列の第３の部分行列と第４の部分行列の逆行列の行列積を乗算して第７の信号を生成する段階と、
前記情報語と、前記第４の信号を第１のパリティで、前記第７の信号を第２のパリティとし、前記ブロックＬＤＰＣ符号フォーマットに対応するように多重化して出力する段階と、
を有することを特徴とする方法。
【請求項２４】
前記第１の部分行列及び第２の部分行列は前記情報部分に対応する部分行列で、前記ブロックＬＤＰＣ符号の因子グラフの最小サイクル長さが最大になり、ウェイト値が不均一にするように前記順列行列を配列された行列であることを特徴とする請求項２３記載の方法。
【請求項２５】
前記第３の部分行列と第４の部分行列は前記第１のパリティ部分に対応する部分 行列で、前記第５の部分行列と第６の部分行列は前記第２のパリティ部分に対応する部分行列で、前記第３の部分行列と第４の部分行列は予め定められた位置に順列行列が配列された行列で、前記第５の部分行列は完全下三角形で単位行列が配列された行列であることを特徴とする請求項２３記載の方法。
【請求項２６】
前記第２のパリティ部分に分類されたブロックの中に、予め決定されたブロックに完全下三角形で配列された順列行列が単位行列であることを特徴とする請求項２５記載の方法。
【請求項２７】
パリティ検査行列は、複数の情報部分ブロックと複数のパリティ部分ブロックの行と列の行列形態で配列され、前記パリティ検査行列は前記情報部分ブロックの行列で構成された情報部分と前記パリティ部分ブロックの行列で構成されたパリティ部分に区分され、前記情報部分ブロックの各々は複数の情報ビットを示す行列で構成され、前記パリティ部分ブロックの各々は、複数のパリティビットを示す行列で構成され、前記パリティ検査行列は複数の行に存在する情報部分ブロックとパリティ部分ブロックが各々第１の情報行列と第１のパリティ行列及び第２のパリティ行列に分割され、前記複数の行を除いた残りの行に存在する情報部分ブロックとパリティ部分ブロックが各々第２の情報行列と第３のパリティ行列及び第４のパリティ行列に分割され、前記第１及び第２の情報行列と、第１及び第３のパリティ行列と、第２及び第４のパリティ行列は各々同一の列に配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、
前記第４のパリティ行列と第２のパリティ行列の逆行列と前記第１のパリティ行列の積と前記第３のパリティ行列の和が単位行列になるように設定する段階と、
前記第１のパリティ行列と前記第３のパリティ行列に対応する第１のパリティベクトルの転置ベクトルは、前記第４のパリティ行列と前記第２のパリティ行列の逆行列と前記第１の情報行列の積と前記第２の情報行列の和を前記第１の情報行列と前記第２の情報行列に対応する情報ベクトルを乗算した値になるように決定する段階と、
前記第２のパリティ行列と第４のパリティ行列に対応する第２のパリティベクトルの転置ベクトルは、前記第２のパリティ行列の逆行列と前記第１の情報行列と前記情報ベクトルの転置ベクトルを乗算した値と前記第１のパリティ行列と前記第１のパリティベクトルの転置ベクトルを乗算した値を加算した値を乗算した値になるように決定する段階と、
を有することを特徴とする方法。
【請求項２８】
前記第２のパリティ行列は完全下三角行列であることを特徴とする請求項２７記載の方法。
【請求項２９】
前記第１の情報行列及び第２の情報行列は不均一のウェイト値を有することを特徴とする請求項２７記載の方法。
【請求項３０】
ブロック低密度パリティ検査(ＬＤＰＣ)符号のパリティ検査行列は、複数の部分ブロックの行と列の行列形態で配列され、前記複数の部分ブロック各々にはＮｓxＮｓサイズを有する行列が前記複数の部分ブロックの各々に対応して予め定められた指数だけシフトして生成された順列行列が配列され、誤り訂正性能を向上させるための前記パリティ検査行列を生成する方法であって、
前記ブロックＬＤＰＣ符号のブロックサイクルを任意の第１の値に決定する段階と、
前記ブロックサイクルを決定した後に、前記部分ブロックの各々に配列された順列行列の中に、その指数が奇数である順列行列の指数の和から前記部分ブロックの各々に配列された順列行列のうち、その指数が偶数である順列行列の指数の和を減算した値と任意の第２の値を乗算した値になるように前記第２の値を決定し、前記部分ブロックの各々が前記第１の値と第２の値を乗算した値に対応するサイクルを有するように制御する段階と、
を有することを特徴とする方法。
【請求項３１】
前記指数は１以上で、前記第１の値以下であることを特徴とする請求項３０記載の方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図１９】
【図２０】
【公開番号】特開２００８−１７２８２４（Ｐ２００８−１７２８２４Ａ）
【公開日】平成２０年７月２４日（２００８．７．２４）
【国際特許分類】
【出願番号】特願２００８−４４８９８（Ｐ２００８−４４８９８）
【出願日】平成２０年２月２６日（２００８．２．２６）
【分割の表示】特願２００６−５２４５７６（Ｐ２００６−５２４５７６）の分割
【原出願日】平成１６年８月２６日（２００４．８．２６）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【Ｆターム（参考）】
【公開日】平成２０年７月２４日（２００８．７．２４）
【国際特許分類】
【出願日】平成２０年２月２６日（２００８．２．２６）
【分割の表示】特願２００６−５２４５７６（Ｐ２００６−５２４５７６）の分割
【原出願日】平成１６年８月２６日（２００４．８．２６）
【出願人】（５０３４４７０３６）サムスン エレクトロニクス カンパニー リミテッド (2,221)
【Ｆターム（参考）】
[ Back to top ]