(57)【要約】  ブロック低密度パリティ検査（ＬＤＰＣ）符号を符号化する装置及び方法を提供する。情報語ベクトルを受信すると、符号化器は、情報語ベクトルを予め設定されている生成行列に従ってブロックＬＤＰＣに符号化する。変調器は、ブロックＬＤＰＣ符号を予め設定されている変調方式を使用して変調シンボルに変調した後、送信機は、変調シンボルを送信する。移動通信システムにおいて、最小のサイクル長が最大となるブロックＬＤＰＣ符号を提案することにより、エラー訂正能力を最大化させる。また、パリティ検査行列を使用して効率的な生成行列を生成することにより、ブロックＬＤＰＣ符号の符号化の複雑度を最小化させることができる。
2008501287.tif 000002
【特許請求の範囲】
【請求項１】
ブロック低密度パリティ検査（ＬＤＰＣ）符号を符号化する方法であって、
情報語ベクトルを受信するステップと、
前記情報語ベクトルを予め設定されている生成行列に従ってブロックＬＤＰＣに符号化するステップとを具備することを特徴とする方法。
【請求項２】
前記ブロックＬＤＰＣ符号を予め設定されている変調方式を使用して変調シンボルに変調するステップと、
前記変調シンボルを送信するステップとをさらに具備することを特徴とする請求項１に記載の方法。
【請求項３】
前記生成行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列を変形して生成された行列であることを特徴とする請求項１に記載の方法。
【請求項４】
前記ブロックＬＤＰＣ符号は、前記情報語ベクトルと、第１のパリティベクトルと、第２のパリティベクトルとを含み、前記生成行列は、前記情報語ベクトルにマッピングされる第１の行列と、前記第１のパリティベクトルにマッピングされる第２の行列と、前記第２のパリティベクトルにマッピングされる第３の行列とを含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記第１の行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列の前記情報語ベクトルにマッピングされる第４の行列が変形された行列であり、前記第２の行列は、前記パリティ検査行列の前記第１のパリティベクトルにマッピングされる第５の行列が変形された行列であり、前記第３の行列は、前記パリティ検査行列の前記第２のパリティベクトルにマッピングされる第６の行列が変形された行列であることを特徴とする請求項４に記載の方法。
【請求項６】
前記第１の行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列の前記情報語ベクトルにマッピングされる第４の行列と予め設定されている第５の行列を乗算した行列であり、前記第２の行列は、前記パリティ検査行列の前記第１のパリティベクトルにマッピングされる第６の行列と前記第５の行列を乗算した行列であり、前記第３の行列は、前記パリティ検査行列の前記第２のパリティベクトルにマッピングされる第７の行列と前記第５の行列を乗算した行列であることを特徴とする請求項４に記載の方法。
【請求項７】
前記情報語ベクトルを予め設定されている前記生成行列に従って前記ブロックＬＤＰＣ符号に符号化するステップは、
前記第４の行列のすべての行をブロック単位で加算した行列と前記情報語ベクトルの転置ベクトルを乗算したベクトルが前記第１のパリティベクトルの転置ベクトルを予め設定された値だけ循環シフトしたベクトルとなるように、前記第１のパリティベクトルを生成するステップと、
逆代入方式を使用して前記第２のパリティベクトルを生成するステップと、
前記情報語ベクトルに前記第１のパリティベクトル及び第２のパリティベクトルを接続して前記ブロックＬＤＰＣ符号を生成するステップとを具備することを特徴とする請求項６に記載の方法。
【請求項８】
前記第４の行列のすべての行をブロック単位で加算した行列は、前記第４の行列に含まれている部分ブロックの同一の行を加算して生成されることを特徴とする請求項７記載の方法。
【請求項９】
前記第１のパリティベクトルは、下記（式１）を使用して生成されることを特徴とする請求項７に記載の方法。
【数１】
2008501287.tif 000109
ここで、
【数２】
2008501287.tif 000110
は、前記情報語ベクトルを示し、
【数３】
2008501287.tif 000111
は、前記第１のパリティベクトルを示し、
【数４】
2008501287.tif 000112
は、前記情報語ベクトルの転置ベクトルを示し、
【数５】
2008501287.tif 000113
は、前記第１のパリティベクトルの転置ベクトルを示し、Ｐｘは、Ｎｓ×Ｎｓサイズを有する順列行列をｘだけ循環シフトした行列を示し、
【数６】
2008501287.tif 000114
は、前記
【数７】
2008501287.tif 000115
をｘだけ循環シフトしたベクトルを示し、
【数８】
2008501287.tif 000116
は、該当行列のすべての行をブロック単位で加算する演算を示す。
【請求項１０】
前記該当行列のすべての行をブロック単位で加算する演算は、該当行列に含まれる部分ブロックの同一の行を加算する演算であることを特徴とする請求項９に記載の方法。
【請求項１１】
ブロック低密度パリティ検査（ＬＤＰＣ）符号を符号化する装置であって、
前記情報語ベクトルを予め設定されている生成行列に従ってブロックＬＤＰＣに符号化する符号化器と、
前記ブロックＬＤＰＣ符号を予め設定されている変調方式を使用して変調シンボルに変調する変調器と、
前記変調シンボルを送信する送信機とを具備することを特徴とする装置。
【請求項１２】
前記生成行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列を変形して生成されることを特徴とする請求項１１に記載の装置。
【請求項１３】
前記ブロックＬＤＰＣ符号は、前記情報語ベクトルと、第１のパリティベクトルと、第２のパリティベクトルとを具備し、前記生成行列は、前記情報語ベクトルにマッピングされる第１の行列と、前記第１のパリティベクトルにマッピングされる第２の行列と、前記第２のパリティベクトルにマッピングされる第３の行列とを具備することを特徴とする 請求項１１に記載の装置。
【請求項１４】
前記第１の行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列の前記情報語ベクトルにマッピングされる第４の行列が変形された行列であり、前記第２の行列は、前記パリティ検査行列の前記第１のパリティベクトルにマッピングされる第５の行列が変形された行列であり、前記第３の行列は、前記パリティ検査行列の前記第２のパリティベクトルにマッピングされる第６の行列が変形された行列であることを特徴とする請求項１３に記載の装置。
【請求項１５】
前記第１の行列は、前記情報語ベクトルから前記ブロックＬＤＰＣ符号を生成する時に適用される長さに対応するパリティ検査行列の前記情報語ベクトルにマッピングされる第４の行列と予め設定されている第５の行列を乗算した行列であり、前記第２の行列は、前記パリティ検査行列の前記第１のパリティベクトルにマッピングされる第６の行列と前記第５の行列を乗算した行列であり、前記第３の行列は、前記パリティ検査行列の前記第２のパリティベクトルにマッピングされる第７の行列と前記第５の行列を乗算した行列であることを特徴とする請求項１３に記載の装置。
【請求項１６】
前記符号化器は、
前記情報語ベクトルと前記第４の行列のすべての行をブロック単位で加算した行列を乗算する行列乗算器と、
前記行列乗算器から出力された信号を予め設定された値だけ循環シフトして前記第１のパリティベクトルを生成する循環シフト器と、
前記情報語ベクトル及び前記循環シフト器から出力された信号を逆代入方式にて処理して前記第２のパリティベクトルを生成する逆代入方式処理器と、
前記情報語ベクトルと、第１のパリティベクトルと、第２のパリティベクトルとをスイッチングして、前記ブロックＬＤＰＣ符号を生成するスイッチとを具備することを特徴とする請求項１５に記載の装置。
【請求項１７】
前記符号化器は、前記第４の行列のすべての行をブロック単位で加算した行列と前記情報語ベクトルの転置ベクトルを乗算したベクトルを前記第１のパリティベクトルの転置ベクトルを予め設定された値だけ循環シフトしたベクトルとなるように、前記第１のパリティベクトルを生成し、逆代入方式を使用して前記第２のパリティベクトルを生成した後に、前記情報語ベクトルに前記第１のパリティベクトル及び第２のパリティベクトルを接続して前記ブロックＬＤＰＣ符号を生成することを特徴とする請求項１５に記載の装置。
【請求項１８】
前記第４の行列のすべての行をブロック単位で加算した行列は、前記第４の行列に含まれている部分ブロックの同一の行を加算して生成されることを特徴とする請求項１７に記載の装置。
【請求項１９】
前記符号化器は、下記（式２）を使用して前記第１のパリティベクトルを生成することを特徴とする請求項１７に記載の装置。
【数９】
2008501287.tif 000117
ここで、
【数１０】
2008501287.tif 000118
は、前記情報語ベクトルを示し、
【数１１】
2008501287.tif 000119
は、前記第１のパリティベクトルを示し、
【数１２】
2008501287.tif 000120
は、前記情報語ベクトルの転置ベクトルを示し、
【数１３】
2008501287.tif 000121
は、前記第１のパリティベクトルの転置ベクトルを示し、
Ｐｘは、Ｎｓ×Ｎｓサイズを有する順列行列をｘだけ循環シフトした行列を示し、
【数１４】
2008501287.tif 000122
は、前記
【数１５】
2008501287.tif 000123
をｘだけ循環シフトしたベクトルを示し、
【数１６】
2008501287.tif 000124
は、該当行列のすべての行をブロック単位で加算する演算を示す。
【請求項２０】
前記該当行列のすべての行をブロック単位で加算する演算は、該当行列に含まれる部分ブロックの同一の行を加算する演算であることを特徴とする請求項１９に記載の装置。
【請求項２１】
ブロック低密度パリティ検査（ＬＤＰＣ）符号を復号化する方法であって、
信号を受信するステップと、
復号化されるブロックＬＤＰＣ符号の長さに従って予め設定されているパリティ検査行列を使用して前記受信信号を復号化するステップと、
前記ブロックＬＤＰＣ符号を前記復号化された受信信号から検出するステップとを具備することを特徴とする方法。
【請求項２２】
前記パリティ検査行列に従って前記受信信号を復号化し、前記復号化された受信信号から前記ブロックＬＤＰＣ符号を検出するステップは、
前記パリティ検査行列に従ってデインターリービング方式及びインターリービング方式を決定するステップと、
前記受信信号の確率値を検出するステップと、
前記受信信号の確率値から以前の復号化過程で生成された信号を減算して第１の信号を生成するステップと、
前記第１の信号を前記デインターリービング方式を使用してデインターリービングするステップと、
前記デインターリービングされた信号から確率値を検出するステップと、
前記デインターリービングされた信号の確率値から前記デインターリービングされた信号を減算して第２の信号を生成するステップと、
前記第２の信号を前記インターリービング方式にてインターリービングするステップと、
前記インターリービングされた信号を反復復号化して、前記ブロックＬＤＰＣ符号を検出するステップとを具備することを特徴とする請求項２１に記載の方法。
【請求項２３】
ブロック低密度パリティ検査（ＬＤＰＣ）符号を復号化する装置であって、
信号を受信する受信機と、
復号化されるブロックＬＤＰＣ符号の長さに対応して予め設定されているパリティ検査行列を使用して前記受信信号を復号化し、前記復号化された受信信号から前記ブロックＬＤＰＣ符号を検出する復号化器とを具備することを特徴とする装置。
【請求項２４】
前記復号化器は、
前記パリティ検査行列に含まれた各々の列のウェイトに従って変数ノードを接続することによって、前記受信信号の確率値を検出する変数ノード復号化器と、
前記変数ノード復号化器から出力された信号から以前の復号化過程で生成された信号を減算する第１の加算器と、
前記第１の加算器から出力された信号を、前記パリティ検査行列に従って設定されたデインターリービング方式にてデインターリービングするデインターリーバと、
前記パリティ検査行列に含まれた各々の行のウェイトに従って検査ノードを接続することによって、前記デインターリーバから出力された信号の確率値を検出する検査ノード復号化器と、
前記検査ノード復号化器から出力された信号から前記デインターリーバから出力された信号を減算する第２の加算器と、
前記第２の加算器から出力された信号を前記パリティ検査行列に従って設定されたインターリービング方式にてインターリービングし、前記インターリービングされた信号を前記変数ノード復号化器及び前記第１の加算器へ出力するインターリーバと、
前記デインターリービング方式及び前記インターリービング方式を前記パリティ検査行列に従って制御する制御器とを具備することを特徴とする請求項２３に記載の装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ブロック低密度パリティ検査(Low Density Parity Check；以下、“ＬＤＰＣ”と称する)符号を符号化／復号化するための装置及び方法に関するものである。
【背景技術】
【０００２】
通信において、もっとも根本的な問題は、チャネルを介してデータを効率的にかつ信頼性よく送信することである。最近、活発に研究されている次世代マルチメディア移動通信システムでは、初期の音声を主とするサービスを超えて、映像及び無線データなどのような多様な情報を処理して送信することができる高速の通信システムを要求する。従って、システムに適合したチャネル符号化方式を使用してシステム効率を増加させることが必須的である。
【０００３】
データ送信は、チャネル状況に従って、雑音、干渉、及びフェージング(fading)などによる不回避なエラーが発生して、大量の情報の損失が生じる。一般的に、上記情報の損失を減少させるために、チャネル特性に基づいて、多様なエラー制御方式(error-control technique)を用いて、移動通信システムの信頼度を向上させる。もっとも基本的なエラー制御方式は、エラー訂正符号(error correction code)を使用する。
【０００４】
図１は、従来の移動通信システムにおける送受信機の構成を概略的に示す図である。図１を参照すると、まず、送信機において、送信メッセージ‘ｕ’は、チャネルを介して送信される前に、符号化器(encoder)１１１によって予め設定されている符号化方式にて符号化される。また、符号化器１１１によって符号化された符号化シンボル‘ｃ’は、あらかじめ設定されている変調方式を使用して変調器１１３によって変調され、上記変調された信号‘ｓ’は、チャネル１１５を介して受信機へ送信される。
【０００５】
上記受信機において、受信された信号‘ｒ’は、上記送信機が送信した信号‘ｓ’に、チャネル状況に従って幾つかの雑音などが混合された形態の歪曲された信号となる。上記受信信号‘ｒ’は、復調器(demodulator)１５３によって、上記送信機の変調器１１３で適用した変調方式に対応する復調方式にて復調され、上記復調された信号‘ｘ’は、復号化器１０９によって、上記送信機の符号化器１０１で適用した符号化方式に対応する復号化方式にて復号化される。復号化器１５５によって復号化された信号は、
【数１】
2008501287.tif 000003
となる。
【０００６】
従って、上記送信機が送信した信号‘ｕ’を受信機がエラー無しに復元するために、高性能のチャネル符号化器及び復号化器が要求されている。特に、チャネル１０５が無線チャネルである場合に、チャネルによるエラーは、さらに深刻な問題となる。上記受信機の復号化器１５５は、チャネルを介して受信されたデータに基づいて送信メッセージを推定することができる。
【０００７】
移動通信システムが急速に発展していくに伴い、無線ネットワークにおいて、有線ネットワークの容量に近い大容量データを伝送可能な技術の開発が望まれている。このように、音声中心のサービスを越えて、映像、無線データなどの様々な情報を処理して伝送可能な高速の且つ大容量の通信システムが求められるに伴い、適正なチャネル符号化方式を用いてシステム伝送効率を高めることがシステム性能の向上に必須的な要素として作用する。しかしながら、移動通信システムは、移動通信システムの特性上、データを伝送する際に、チャネル状況に従って、雑音、干渉、及びフェージングなどによるエラーの発生が不可避であり、このため、上記エラー発生による情報データの損失が発生する。
【０００８】
このようなエラー発生による情報データの損失を低減させるために、チャネル特性に従って様々なエラー制御方式を用いることにより、上記移動通信システムの信頼度を向上させることができる。上記エラー制御方式のうちの最も普遍的に用いられているエラー制御方式は、エラー訂正符号を用いる方式である。上記エラー訂正符号の代表的な符号としては、ターボ符号と、低密度パリティ検査（Low Density Parity Check；以下、「ＬＤＰＣ」と称する。）符号などがある。
上記ターボ符号は、従来、エラー訂正のために汎用されていた畳み込み符号に比べて、高速データの伝送時における性能利得に優れていることが知られており、伝送チャネルにおける雑音によるエラーを効率的に訂正して、データ伝送の信頼度を高めることができる、という長所を有する。
【０００９】
また、上記ＬＤＰＣ符号は、ファクター（factor）グラフ上において、和積アルゴリズム（sum-product algorithm）に基づく反復復号化アルゴリズムを用いて復号化することができる。上記ＬＤＰＣ符号の復号化器は、上記和積アルゴリズムに基づく反復復号化アルゴリズムを用いるため、上記ターボ符号の復号化器に比べて低い複雑度を有するだけではなく、並列処理復号化器として実現することが容易である。
【００１０】
一方、Ｓｈａｎｎｏｎのチャネル符号化理論によれば、チャネルの容量を超えないデータレートに限って信頼性のある通信が可能であることが明らかにされている。しかしながら、 Ｓｈａｎｎｏｎのチャネル符号化理論においては、チャネルの容量限界までのデータレートをサポートするチャネル符号化及び復号化方法についての具体的な提示は全くなかった。通常、ブロックサイズが極めて大きなランダム符号は、Ｓｈａｎｎｏｎのチャネル符号化理論のチャネル容量限界に近い性能を示すが、ＭＡＰ（maximum a posteriori）またはＭＬ（maximum likelihood）復号化方法を用いる場合、その多大な計算の負荷が存在するために、実際に実現することが不可能であった。
【００１１】
上記ターボ符号は、１９９３年Ｂｅｒｒｏｕ、Ｇｌａｖｉｅｕｘ、及びＴｈｉｔｉｍａｊｓｈｉｍａによって提案されており、Ｓｈａｎｎｏｎのチャネル符号化理論のチャネル容量限界に近い高性能を有している。上記ターボ符号の提案により、符号の反復復号化とグラフ表現についての研究が活発に行われており、この時点において、Ｇａｌｌａｇｅｒが１９６２年に既に提案したＬＤＰＣ符号が新たに注目を浴びている。また、上記ターボ符号とＬＤＰＣ符号のファクターグラフ上にはサイクルが存在するが、上記サイクルが存在する上記ＬＤＰＣ符号のファクターグラフ上における反復復号化は、準最適（suboptimal）であることが既に知られており、上記ＬＤＰＣ符号は、反復復号化によって高性能を有することも実験的に立証されている。これまで知られている最高の性能を有するＬＤＰＣ符号は、ブロックサイズ１０７を用い、ビットエラーレート（ＢＥＲ：Bit Error Rate）１０−５において、Ｓｈａｎｎｏｎのチャネル符号化理論のチャネル容量限界において単に０．０４［ｄＢ］程度の差分を有する性能を示す。また、ｑ＞２であるガロアフィールド（Galois Field；以下、「ＧＦ」と称する。）、すなわち、ＧＦ（ｑ）において定義されたＬＤＰＣ符号は、その復号化過程中に複雑度が増加するが、バイナリ符号に比べて遥かに高性能を示す。しかしながら、上記ＧＦ（ｑ）において定義されたＬＤＰＣ符号の反復復号化アルゴリズムの復号化が成功することについて、満足のいく理論的な説明は未だなされていないのが現状である。
【００１２】
また、上記ＬＤＰＣ符号は、Ｇａｌｌａｇｅｒにより提案された符号であり、大部分のエレメントが０の値を有し、上記０の値を有するエレメント以外の極めて小数のエレメントが０ではない値を有する、例えば、１の値を有するパリティ検査行列により定義される。以下、説明の便宜上、上記０ではない値を１であると仮定して説明する。
例えば、（Ｎ，ｊ，ｋ）ＬＤＰＣ符号は、ブロックの長さがＮである線形ブロック符号であり、列ごとにｊ個の１の値を有するエレメントと、各行ごとにｋ個の１の値を有するエレメントを有し、上記１の値を有するエレメントを除いたエレメントは、すべて０の値を有するエレメントにより構成された疎行列であるパリティ検査行列により定義される。
上述したように、上記パリティ検査行列内の各列のウェイトはｊに一定であり、上記パリティ検査行列内の各行のウェイトはｋに一定なＬＤＰＣ符号を均一ＬＤＰＣ符号と称する。ここで、上記ウェイトとは、上記パリティ検査行列を構成するエレメントのうちの０ではない値を有するエレメントの数を示す。これとは異なり、上記パリティ検査行列内の各列のウェイトと各行のウェイトが一定でないＬＤＰＣ符号を不均一ＬＤＰＣ符号と称する。通常、上記均一ＬＤＰＣ符号の性能に比べて、上記不均一ＬＤＰＣ符号の性能の方が一層優れていることが知られている。しかしながら、上記不均一ＬＤＰＣ符号の場合、パリティ検査行列内の各列のウェイトと各行のウェイトが一定ではないため、すなわち、不均一であるため、パリティ検査行列内の各列のウェイトと各行のウェイトを適切に調節しなければ、高性能を保証することができない。
【００１３】
図２は、通常の（８，２，４）ＬＤＰＣ符号のパリティ検査行列を示す図である。図２を参照すると、まず、上記（８，２，４）ＬＤＰＣ符号のパリティ検査行列Ｈは、８個の列と４個の行を有しており、各列のウェイトは、２に固定され、各行のウェイトは、４に固定されている。このように、上記パリティ検査行列内の各列のウェイトと各行のウェイトが均一であるため、図２に示されている（８，２，４）ＬＤＰＣ符号は、均一ＬＤＰＣ符号となる。
【００１４】
図３は、図２の（８，２，４）ＬＤＰＣ符号のファクターグラフを示す図である。図３を参照すると、上記（８，２，４）ＬＤＰＣ符号のファクターグラフは、８個の変数ノード、すなわち、ｘ１３００と、ｘ２３０２と、ｘ３３０４と、ｘ４３０６と、ｘ５３０８と、ｘ６３１０と、ｘ７３１２と、ｘ８３１４と、４個の検査ノード３１６、３１８、３２０、３２２と、から構成される。上記（８，２，４）ＬＤＰＣ符号のパリティ検査行列のｉ番目の行とｊ番目の列とが交差する地点に１の値を有する、すなわち、０ではない値を有するエレメントが存在する場合、変数ノードｘｉとｊ番目の検査ノードとの間にブランチが生成される。
【００１５】
上述したように、ＬＤＰＣ符号のパリティ検査行列は極めて小さなウェイトを有するため、比較的長いブロック符号においても反復復号化を通じて復号化が可能であり、ブロック符号のブロック長を増大し続けていくと、ターボ符号のようにＳｈａｎｎｏｎのチャネル容量限界に近い性能を示す。また、ＭａｃＫａｙとＮｅａｌは、流れ伝達方式（flow transfer scheme）を用いるＬＤＰＣ符号の反復復号化過程がターボ符号の反復復号化過程にほとんど近い性能を有することを既に証明している。
【００１６】
一方、高性能のＬＤＰＣ符号を生成するためには、幾つかの条件を満足しなければならないが、上記条件を説明すると、下記の通りである。
（１）ＬＤＰＣ符号のファクターグラフ上のサイクルを考慮しなければならない。
上記“サイクル”とは、ＬＤＰＣ符号のファクターグラフにおいて、変数ノードを検査ノードに接続するエッジで形成されたループを意味する。サイクルの長さは、ループを構成するエッジの個数として定義される。長いサイクルは、ＬＤＰＣ符号のファクターグラフでループを構成する変数ノードを検査ノードに接続するエッジの個数が多いことを意味する。これとは異なり、短いサイクルは、ＬＤＰＣ符号のファクターグラフにおいて、ループを構成する変数ノードを検査ノードに接続するエッジの個数が少ないことを意味する。
上記ＬＤＰＣ符号のファクターグラフ上のサイクルを長く生成するほど、上記ＬＤＰＣ符号の性能がよくなるが、その理由は、下記の通りである。上記ＬＤＰＣ符号のファクターグラフ上のサイクルを長く生成する場合、上記ＬＤＰＣ符号のファクターグラフ上に短いサイクルが多く存在する際に生じるエラーフロアなどの性能劣化が生じないためである。
【００１７】
（２）ＬＤＰＣ符号の効率よい符号化を考慮しなければならない。
上記ＬＤＰＣ符号は、上記ＬＤＰＣ符号の特性から、畳み込み符号やターボ符号に比べて符号化の複雑度が高く、リアルタイムの符号化が困難である。上記ＬＤＰＣ符号の符号化の複雑度を減らすために、反復累積符号（ＲＡ（Repeat Accumulate） code）などが提案されているが、上記反復累積符号にも、上記ＬＤＰＣ符号の符号化の複雑度を減少させることに関しては、限界を示している。このため、ＬＤＰＣ符号の効率よい符号化を考慮しなければならない。
【００１８】
（３）ＬＤＰＣ符号のファクターグラフ上の次数分布を考慮しなければならない。
通常、均一ＬＤＰＣ符号よりも不均一ＬＤＰＣ符号の方の性能が優れているが、その理由は、上記不均一ＬＤＰＣ符号のファクターグラフ上の次数が様々であるためである。ここで、上記次数とは、上記ＬＤＰＣ符号のファクターグラフ上において、各ノード、すなわち、変数ノードと検査ノードとに接続されているエッジの数を示す。また、ＬＤＰＣ符号のファクターグラフ上の次数分布とは、特定の次数を有するノードが全体のノード中にどれだけ存在するかを示す。特定の次数分布を有するＬＤＰＣ符号の性能に優れているということは、Ｒｉｃｈａｒｄｓｏｎらが既に立証している。
【００１９】
図４は、通常のブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。図４を説明するに先立って、まず、上記ブロックＬＤＰＣ符号は、効率よい符号化だけではなく、パリティ検査行列の効率的な格納、及び性能面での改善を両方とも考慮した新たなＬＤＰＣ符号であり、上記ブロックＬＤＰＣ符号は、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。
【００２０】
図４を参照すると、上記ブロックＬＤＰＣ符号のパリティ検査行列は、全体のパリティ検査行列を多数の部分ブロックに分割し、上記部分ブロックの各々に１つの順列行列を対応付ける形状を有する。図４に示されているＰは、Ｎｓ×Ｎｓサイズを有する順列行列を示し、上記順列行列Ｐの上付き添字ａｐｑは０≦ａｐｑ≦Ｎｓ−１若しくはａｐｑ＝∞を有する。また、上記ｐは、当該順列行列が上記パリティ検査行列の多数の部分ブロックに分けられたうちのｐ番目の行に位置することを示し、ｑは、当該順列行列が上記パリティ検査行列の多数の部分ブロックに分けられたうちのｑ番目の列に位置することを示す。すなわち、
【数２】
2008501287.tif 000004
は、上記多数の部分ブロックにより構成されたパリティ検査行列のｐ番目の行とｑ番目の列が交差する個所の部分ブロックに存在する順列行列を示す。すなわち、上記ｐとｑは、上記パリティ検査行列において上記情報部分に相当する部分ブロックの行と列の数を示す。
【００２１】
図５は、図４の順列行列Ｐを示す図である。図５に示すように、上記順列行列Ｐは、Ｎｓ×Ｎｓサイズを有する正方行列であり、上記順列行列Ｐは、上記順列行列Ｐを構成するＮｓ個の列の各々のウェイトが１であり、上記順列行列Ｐを構成するＮｓ個の行の各々のウェイトも１である行列を示す。ここで、上記順列行列ＰのサイズをＮｓ×Ｎｓとしているが、上記順列行列Ｐが正方行列であるため、そのサイズを、説明の便宜上、Ｎｓとも表現することに留意すべきである。
【００２２】
一方、図４において、上記順列行列Ｐの上付き添字ａｐｑが０であるとき、すなわち、順列行列Ｐ０は単位行列（identity matrix）
【数３】
2008501287.tif 000005
を示し、上記順列行列Ｐの上付き添字ａｐｑが∞であるとき、すなわち、順列行列Ｐ∞は０行列を示す。ここで、
【数４】
2008501287.tif 000006
は、サイズがＮｓ×Ｎｓである単位行列を示す。
【００２３】
図４に示すように、上記ブロックＬＤＰＣ符号の全体のパリティ検査行列は、全体の行の数がＮｓ×ｐであり、全体の列の数がＮｓ×ｑ（但し、ｐ≦ｑ）であるため、上記ブロックＬＤＰＣ符号の全体のパリティ検査行列が最大ランク(rank)を有する場合、上記部分ブロックのサイズとは無関係に、符号化率は下記（式１）のように表わすことができる。
【数５】
2008501287.tif 000007
一方、すべてのｐ、ｑについてａｐｑ≠∞である場合、上記部分ブロックの各々に対応する順列行列の各々は０行列ではないことを示し、部分ブロックの各々に対応する順列行列の各々の各列のウェイトがｐであり、各行のウェイトがｑである均一ＬＤＰＣ符号となる。ここで、上記部分ブロックに対応する順列行列を「部分行列」と称する。
【００２４】
また、上記全体のパリティ検査行列にはｐ−１個の従属的な行が存在するため、符号化率は、上記（式１）において計算した符号化率よりも大きな値を有する。上記ブロックＬＤＰＣ符号は、全体のパリティ検査行列を構成する部分行列の各々の最初の行のウェイト位置が決められると、残りのＮｓ−１個の行のウェイト位置が決められるため、上記全体のパリティ検査行列の情報を格納するために不規則的にウェイトを選択する場合に比べて、必要とされるメモリのサイズが１／Ｎｓに減少する。
【００２５】
一方、上述したように、ＬＤＰＣ符号のファクターグラフ上のサイクルとは、パリティ検査行列のＬＤＰＣ符号のファクターグラフにおいて変数ノードと検査ノードとを接続するエッジが構成するループのことであり、上記サイクルの長さは、上記ループを構成するエッジの数として定義される。上記サイクルが長いことは、上記ＬＤＰＣ符号のファクターグラフにおいて、ループを構成する変数ノードと検査ノードとを接続するエッジの数が多いことを示す。上記ＬＤＰＣ符号のファクターグラフ上のサイクルを長く生成するほど、上記ＬＤＰＣ符号の性能がよくなる。
【００２６】
これとは異なり、上記ＬＤＰＣ符号のファクターグラフ上に短いサイクルがたくさん存在するほど、上記ＬＤＰＣ符号は、エラーフロアなどの性能劣化が現れるため、エラー訂正能力が低下する。すなわち、上記ＬＤＰＣ符号のファクターグラフ上に短いサイクルがたくさん存在する場合、上記短いサイクルに属している任意の１つのノードから出発した自身の情報が、幾つかの反復回数後に再び自身に戻って、上記反復回数が増えるに伴い、その情報が継続して自身に戻るため、情報更新がうまく行われず、結局、エラー訂正能力が低下される。
【００２７】
図６は、パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構成を概略的に示す図である。しかしながら、図６を説明するに先立って、上記ブロックＬＤＰＣ符号は、効率よい符号化だけではなく、パリティ検査行列の効率的な格納及び性能面での改善を考慮したＬＤＰＣ符号であって、均一ＬＤＰＣ符号の構造を一般化させて拡張した概念のＬＤＰＣ符号である。図６に示すブロックＬＤＰＣ符号のパリティ検査行列は、４個のブロックにより構成され、斜線は、１の値を有するエレメントが存在する位置を示し、上記斜線部分を除く部分は、いずれも０の値を有するエレメントが存在する位置を示す。また、Ｐは、図５を参照して説明したような順列行列と同一の順列行列を示す。
【００２８】
図６に示すブロックＬＤＰＣ符号のサイクル構造を分析するために、部分行列Ｐａのｉ番目の行に位置する１の値を有するエレメントを基準にして定め、上記ｉ番目の行に位置する１の値を有するエレメントを“０−点”と称する。ここで、上記部分行列は、上記部分ブロックに対応する行列を示す。すると、上記０−点は、上記部分行列Ｐａのｉ＋ａ番目の列に位置する。
【００２９】
上記０−点と同一の行に位置している部分行列Ｐｂにおける１の値を有するエレメントを“１−点”と称する。上記０−点と同様に、上記１−点は、部分行列Ｐｂのｉ＋ｂ番目の列に位置する。
【００３０】
次いで、上記１−点と同一の列に位置している部分行列Ｐｃにおける１の値を有するエレメントを“２−点”と称する。上記部分行列Ｐｃが単位行列Ｉの列の各々を右側にモジューロＮｓに対してｃだけ移動して得た行列であるため、２−点は上記部分行列Ｐｃのｉ＋ｂ−ｃ番目の行に位置する。
【００３１】
また、上記２−点と同一の行に位置している部分行列Ｐｄにおける１の値を有するエレメントを“３−点”と称する。上記３−点は、上記部分行列Ｐｄにおけるｉ＋ｂ−ｃ＋ｄ番目の列に位置する。
【００３２】
最後に、上記３−点と同一の列に位置している部分行列Ｐａにおける１の値を有するエレメントを“４−点”と称する。上記４−点は、上記部分行列Ｐａにおけるｉ＋ｂ−ｃ＋ｄ−ａ番目の行に位置する。
【００３３】
図６に示すＬＤＰＣ符号のサイクル構造において、長さが４であるサイクルが存在すると、上記０−点と４−点は互いに同一の位置となる。すなわち、上記０−点と４−点との間には、下記（式２）のような関係が成り立つ。
【数６】
2008501287.tif 000008
【００３４】
そして、上記（式２）を再びまとめると、下記（式３）のように表現することができる。
【数７】
2008501287.tif 000009
【００３５】
結果的に、上記（式３）のような関係が成り立つと、長さが４であるサイクルが生成される。一般に、０−点と４ｐ−点が最初に同一となる場合には、
【数８】
2008501287.tif 000010
の関係が成り立ち、下記（式４）のような関係が成り立つ。
【数９】
2008501287.tif 000011
【００３６】
換言すると、与えられたａ、ｂ、ｃ、ｄに対して上記（式４）を満足する正の整数のうちの最小値を有する正の整数をｐとすると、図６に示すようなブロックＬＤＰＣ符号のサイクル構造では、長さが４ｐであるサイクルが最小長を有するサイクルとなる。
【００３７】
結果的に、上述したように、（ａ−ｂ＋ｃ−ｄ）≠０の場合に、ｇｃｄ（Ｎｓ，ａ−ｂ＋ｃ−ｄ）＝１が成り立つと、ｐ＝Ｎｓとなり、このため、長さが４Ｎｓであるサイクルが最小長を有するサイクルとなる。
【００３８】
一方、上記ブロックＬＤＰＣ符号の符号化方式として、Ｒｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式が使用される。Ｒｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式を符号化方式として用いるため、パリティ検査行列の形態は、完全下三角行列（full lower triangular matrix）の形状に類似した形状を有するほど、符号化の複雑度を小さくさせることができる。
【００３９】
図７は、完全下三角行列の形状と類似した形状を有するパリティ検査行列を示す図である。しかしながら、図７に示すパリティ検査行列は、完全下三角行列の形状と類似した形状を有する完全下三角行列の形状のパリティ検査行列であるのに対し、パリティ部分の形状が完全な下三角行列になっていない。
【００４０】
図７を参照すると、情報部分の順列行列Ｐの上付き添字ａｐｑは、上述したように、０≦ａｐｑ≦Ｎｓ−１又はａｐｑ＝∞を有し、上記情報部分の順列行列Ｐの上付き添字ａｐｑが０である場合、すなわち、Ｐ０は単位行列
【数１０】
2008501287.tif 000012
を示し、上記順列行列Ｐの上付き添字ａｐｑが∞であるとき、すなわち、順列行列Ｐ∞は０行列を示す。また、ｐとｑは、上記パリティ検査行列において、上記情報部分に相当する部分ブロックの行と列の数を示す。さらに、上記パリティ部分の順列行列Ｐの上付き添字ａｐ、ｘ、ｙも順列行列Ｐの指数を示している。ここでは、説明の便宜上、上記パリティ部分を情報部分と識別するために異なる添え字を使っている。すなわち、図７において、
【数１１】
2008501287.tif 000013
も順列行列であり、上記パリティ部分の対角部分に位置する部分行列に順次にインデックスを与えたものである。
【００４１】
また、図７において、ＰｘとＰｙも順列行列であり、説明の便宜上、任意のインデックスを与えたものである。図７に示すように、パリティ検査行列を有するブロックＬＤＰＣ符号のブロックサイズをＮと仮定すると、上記ブロックＬＤＰＣ符号の符号化の複雑度は、上記ブロックサイズＮに対して線形的に増加する（０（Ｎ））。
【００４２】
一方、図７に示すパリティ検査行列を有するＬＤＰＣ符号の最大の問題点は、部分ブロックのサイズをＮｓとしたとき、上記ブロックＬＤＰＣ符号のファクターグラフ上において、常に次数が１であるＮｓ個の検査ノードが生成されるということにある。ここで、上記次数が１である検査ノードは、反復復号化による性能の改善に影響せず、従って、Ｒｉｃｈａｒｄｓｏｎ-Ｕｒｂａｎｋｅ方式のような標準不均一ＬＤＰＣ符号は、次数が１の検査ノードを含んでいない。
【００４３】
従って、次数が１である検査ノードを含むことなく、効率よい符号化が可能であるように、パリティ検査行列を設計するために、図７のようなパリティ検査行列を基本的なパリティ検査行列であると仮定する。
【００４４】
上記部分行列を含んでいる図７のパリティ検査行列において、部分行列の選択は、上記ブロックＬＤＰＣ符号の性能の改善に極めて重要な要素であり、このため、上記部分行列の適切な選択の基準を見出すことも極めて重要な要素となる。
【００４５】
以下、上述のブロックＬＤＰＣ符号の構成に基づいて、上記ブロックＬＤＰＣ符号のパリティ検査行列の設計方法について説明する。
【００４６】
ここで、上記ブロックＬＤＰＣ符号のパリティ検査行列の設計方法と上記ブロックＬＤＰＣ符号の符号化方法に関する説明を容易にするために、図７に示されるパリティ検査行列は、図８に示すような６個の部分行列で構成された形態であると仮定する。
【００４７】
図８は、６個の部分ブロックに分割された図７のパリティ検査行列を示す図である。図８を参照すると、図７に示すブロックＬＤＰＣ符号のパリティ検査行列を、情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分ブロックに分割する。ここで、上記情報部分ｓは、図７を参照して述べた情報部分のように、ブロックＬＤＰＣ符号を符号化する過程において、実際の情報語にマッピングされる上記パリティ検査行列の部分を示す。但し、ここでは説明の便宜上、表記を異にしている。また、上記第１のパリティ部分ｐ１と第２のパリティ部分ｐ２は、図７を参照して説明したパリティ部分のように、上記ブロックＬＤＰＣ符号を符号化する過程において、実際のパリティにマッピングされる上記パリティ検査行列の部分を示し、上記パリティ部分を２つの部分に分割したものである。
【００４８】
上記情報部分ｓの部分ブロック、すなわち、部分ブロックＡ８０２と部分ブロックＣ８０４に対応する部分行列がＡとＣであり、上記第１のパリティ部分ｐ１の部分ブロック、すなわち、部分ブロックＢ８０６と部分ブロックＤ８０８に対応する部分行列がＢとＤであり、第２のパリティ部分ｐ２の部分ブロック、すなわち、部分ブロックＴ８１０と部分ブロックＥ８１２に対応する部分行列がＴ及びＥである。ここで、図８には、上記パリティ検査行列が７個の部分ブロックに分割されていることを示しているが、‘０’は、別途の部分ブロックではなく、部分ブロックＴ８１０に対応する部分行列Ｔが完全下三角の形状を有するため、対角線を中心に０行列が配置された領域を‘０’と表記しているだけであることに留意すべきである。上記情報部分ｓと、第１のパリティ部分ｐ１と、第２のパリティ部分ｐ２の部分行列を用いて符号化方法を簡略にする過程は、図１０を参照して後述するので、ここでは、その詳細な説明を省略する。
【００４９】
以下、図８の部分行列を図９を参照して説明する。図９は、図７のパリティ検査行列の部分行列を、図８の部分行列Ｂの転置行列と、部分行列Ｅと、部分行列Ｔと、部分行列Ｔの逆行列として示す図である。図９を参照すると、部分行列ＢＴは、上記部分行列Ｂの転置行列(transpose matrix)を示し、部分行列Ｔ−１は、上記部分行列Ｔの逆行列を示す。また、図９において、
【数１２】
2008501287.tif 000014
は、
【数１３】
2008501287.tif 000015
を示す。
【００５０】
さらに、図９において、上記順列行列
【数１４】
2008501287.tif 000016
は、単位行列となることもある。これは、上述したように、上記順列行列の指数、すなわち、ａ１が０となる場合には、上記順列行列
【数１５】
2008501287.tif 000017
が単位行列となるためであり、また、上記順列行列の指数、すなわち、ａ１が予め設定された値だけ増加する場合には、上記順列行列が上記増加した設定値に該当する分だけさらに循環シフトされて、結果的に、上記順列行列
【数１６】
2008501287.tif 000018
が単位行列となるためである。
【００５１】
図１０は、通常のブロックＬＤＰＣ符号のパリティ検査行列の生成過程を示す手順図である。図１０を説明するに先立って、ブロックＬＤＰＣ符号を生成するためには、生成されるブロックＬＤＰＣ符号の符号語サイズと符号化率を決め、上記決められた符号語サイズと符号化率に応じて、パリティ検査行列のサイズを決めなければならない。上記ブロックＬＤＰＣ符号の符号語サイズがＮであり、符号化率がＲと仮定すると、パリティ検査行列のサイズは、Ｎ（１−Ｒ）×Ｎとなる。
【００５２】
また、図１０に示すブロックＬＤＰＣ符号のパリティ検査行列の生成過程は、最初に通信システムのシステム状況に合うように生成され、それ以降では、上記生成されているパリティ検査行列を用いるものであるため、実質的に、図１０のパリティ検査行列の生成過程は、１回だけ遂行されればよい。
図１０を参照すると、まず、制御器は、ステップ１０１１において、上記サイズＮ（１−Ｒ）×Ｎのパリティ検査行列を、横軸方向にｐ個のブロックに分割し、縦軸方向にｑ個のブロックに分割して、総計でｐ×ｑ個のブロックに分割した後、ステップ１０１３へ進む。ここで、上記ブロックの各々のサイズはＮｓ×Ｎｓであるため、上記パリティ検査行列は、Ｎｓ×ｐ個の行とＮｓ×ｑ個の列とから構成される。ステップ１０１３において、上記制御器は、上記ｐ×ｑ個のブロックに分割されたパリティ検査行列を情報部分ｓとパリティ部分、すなわち、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２とに分類し、ステップ１０１５及びステップ１０２１へ進む。
【００５３】
ステップ１０１５において、上記制御器は、上記情報部分ｓを、上記ブロックＬＤＰＣ符号の高性能を保証する次数分布に合うように、０ではないブロック、すなわち、０行列ではないブロックと０であるブロック、すなわち、０行列であるブロックを決め、ステップ１０１７へ進む。ここで、上記ブロックＬＤＰＣ符号の高性能を保証する次数分布は、上述の通りであるため、ここでは、その詳細な説明を省略する。
【００５４】
ステップ１０１７において、上記制御器は、上記ブロックＬＤＰＣ符号の高性能を保証する次数分布に合うように決定されたブロックのうち、低い次数を有するブロック中の０行列ではない部分に、上述したように、ブロックサイクルの最小サイクルの長さが最大になるように、順列行列
【数１７】
2008501287.tif 000019
を決定し、ステップ１０１９へ進む。ここで、上記順列行列
【数１８】
2008501287.tif 000020
を決定する際には、上記情報部分ｓだけではなく、上記第１のパリティ部分ｐ１と第２のパリティ部分ｐ２のブロックサイクルも考慮して決めなければならない。
【００５５】
ステップ１０１９において、上記制御器は、上記ブロックＬＤＰＣ符号の高性能を保証する次数分布に合うように決定されたブロックのうち、高次数を有するブロック中の０行列ではない部分に、ランダムに順列行列
【数１９】
2008501287.tif 000021
を決定した後に終了する。ここで、上記高次数を有するブロックのうち、０行列ではない部分に適用すべき順列行列
【数２０】
2008501287.tif 000022
を決定する時にも、同様に、ブロックサイクルの最小サイクルのサイズが最大になるように、順列行列
【数２１】
2008501287.tif 000023
を決定しなければならず、また、上記情報部分ｓだけではなく、上記第１のパリティ部分ｐ１と第２のパリティ部分ｐ２のブロックサイクルも考慮して決めなければならない。上記のように、パリティ検査行列の情報部分ｓに順列行列
【数２２】
2008501287.tif 000024
を配列した形態を図７に示してある。
【００５６】
一方、ステップ１０２１において、上記制御器は、上記パリティ部分、すなわち、第１のパリティ部分ｐ１と第２のパリティ部分ｐ２を４個の部分行列、すなわち、部分行列Ｂと、部分行列Ｔと、部分行列Ｄ、及び部分行列Ｅに分割した後、ステップ１０２３へ進む。ステップ１０２３において、上記制御器は、上記部分行列Ｂを構成する部分ブロックのうちの２個の部分ブロックに、０ではない順列行列Ｐｙと
【数２３】
2008501287.tif 000025
とを入力し、ステップ１０２５へ進む。ここで、上記部分行列Ｂを構成する部分ブロックのうち、２個の部分ブロックに、０ではない順列行列Ｐｙと
【数２４】
2008501287.tif 000026
とを入力する構造は、既に図９を参照して述べている。
【００５７】
ステップ１０２５において、上記制御器は、上記部分行列Ｔの対角部分ブロックには、単位行列Ｉを入力し、上記部分行列Ｔの対角成分の下の（ｉ，ｉ＋１）番目の部分ブロックには、任意の順列行列
【数２５】
2008501287.tif 000027
を入力し、ステップ１０２７へ進む。ここで、上記部分行列Ｔの対角部分ブロックには、単位行列Ｉを入力し、上記部分行列Ｔの対角成分の下の（ｉ，ｉ＋１）番目の部分ブロックには、任意の順列行列
【数２６】
2008501287.tif 000028
を入力する構造は、既に図９を参照して述べている。
【００５８】
ステップ１０２７において、上記制御器は、上記部分行列Ｄに順列行列Ｐｘを入力し、ステップ１０２９へ進む。ステップ１０２９において、上記制御器は、上記部分行列Ｅにおける最後の部分ブロックにのみ
【数２７】
2008501287.tif 000029
を入力した後に終了する。ここで、上記部分行列Ｅを構成する部分ブロックのうちの最後の部分ブロックに２個の
【数２８】
2008501287.tif 000030
を入力する構造は、既に図９を参照して述べている。
【発明の開示】
【発明が解決しようとする課題】
【００５９】
上述したように、ＬＤＰＣ符号は、ターボ符号とともに、高速なデータの伝送時に性能ゲインに優れていることが知られており、伝送チャネルにおいて生じる雑音によるエラーを効果的に訂正して、データ伝送の信頼度を高めることができるというメリットを有する。しかしながら、上記ＬＤＰＣ符号は、符号化率という観点で欠点を有する。すなわち、上記ＬＤＰＣ符号は、比較的高い符号化率を有するため、符号化率という観点で制限がある、という短所を有する。既存のＬＤＰＣ符号の場合、大部分１／２の符号化率を有し、一部のみ１／３の符号化率を有する。このように、符号化率という観点での制限は、結果的に、高速の大容量データの伝送に致命的な影響を及ぼす。
【００６０】
もちろん、比較的低い符号化率を実現するために、密度進化（density evolution）などの方式を用いて最適な性能を示す次数分布を求めることはできるが、上記最適な性能を示す次数分布を有するＬＤＰＣ符号を実現することは、ファクターグラフ上のサイクル構造とハードウェアの実現などの種々の制約条件によって困難さがあった。
【００６１】
したがって、本発明の目的は、ブロックＬＤＰＣ符号を符号化／復号化する装置及び方法を提供することにある。
【００６２】
また、本発明の目的は、移動通信システムにおいて、符号化の複雑度を最小にするブロックＬＤＰＣ符号を符号化／復号化する装置及び方法を提供することにある。
【課題を解決するための手段】
【００６３】
上記のような目的を達成するために、本発明の第１の見地によると、ブロック低密度パリティ検査（ＬＤＰＣ）符号を符号化する方法は、情報語ベクトルを受信するステップと、上記情報語ベクトルを予め設定されている生成行列に従って、ブロックＬＤＰＣに符号化するステップとを具備することを特徴とする。
【００６４】
本発明の第２の見地によると、ブロック低密度パリティ検査（ＬＤＰＣ）符号を符号化する装置は、上記情報語ベクトルを予め設定されている生成行列に従ってブロックＬＤＰＣに符号化する符号化器と、上記ブロックＬＤＰＣ符号を予め設定されている変調方式を使用して変調シンボルに変調する変調器と、上記変調シンボルを送信する送信機とを具備することを特徴とする。
【００６５】
本発明の第３の見地によると、ブロック低密度パリティ検査（ＬＤＰＣ）符号を復号化する方法は、信号を受信するステップと、復号化されるブロックＬＤＰＣ符号の長さに従って予め設定されているパリティ検査行列を使用して上記受信信号を復号化するステップと、上記ブロックＬＤＰＣ符号を上記復号化された受信信号から検出するステップとを具備することを特徴とする。
【００６６】
本発明の第４の見地によると、ブロック低密度パリティ検査（ＬＤＰＣ）符号を復号化する装置は、信号を受信する受信機と、復号化されるブロックＬＤＰＣ符号の長さに対応して予め設定されているパリティ検査行列を使用して上記受信信号を復号化し、上記復号化された受信信号から上記ブロックＬＤＰＣ符号を検出する復号化器とを具備することを特徴とする。
【発明の効果】
【００６７】
本発明は、移動通信システムにおいて、最小のサイクル長が最大となるブロックＬＤＰＣ符号を提案することにより、エラー訂正能力を最大化させる。したがって、上記ブロックＬＤＰＣ符号を使用して、受信データを正確に復号化することができ、高信頼性の復号化が可能である、という利点を有する。
【００６８】
また、本発明は、パリティ検査行列を使用して効率的な生成行列を生成することにより、ブロックＬＤＰＣ符号の符号化の複雑度を最小化させることができる、という利点を有する。
【００６９】
すなわち、本発明は、ブロックＬＤＰＣ符号を提案することによって、ファクターグラフ上で反復復号化を適用して優秀な性能を保証することができる、という利点を有する。
【００７０】
さらに、本発明は、ブロック単位でブロックＬＤＰＣ符号のパリティ検査行列を構成することによって、最小の復号化の複雑度を有しつつも、復号化速度の観点から向上した復号化器の実現が可能である。特に、本発明は、簡素な行列積とブロック単位逆代入方式を使用して、符号化の複雑度を最小化させることできる、という利点を有する。
【発明を実施するための最良の形態】
【００７１】
以下、本発明の望ましい実施形態を添付の図面を参照して詳細に説明する。以下の説明では、本発明に関連した公知の機能又は構成に関する具体的な説明が本発明の要旨を不明にすると判断される場合には、その詳細な説明を省略する。
本発明は、優秀な性能を有するブロック低密度パリティ検査（ＬＤＰＣ：Low Density Parity Check、以下、「ＬＤＰＣ」と称する。）符号（以下、「可変長ブロックＬＤＰＣ符号」と称する。）を符号化及び復号化する装置及び方法を提案する。すなわち、本発明は、ファクターグラフ上の最小サイクルの長さが最大となり、上記ブロックＬＤＰＣ符号の符号化のための複雑度が最小となり、上記ファクターグラフ上の次数分布が最適値１の分布を有するブロックＬＤＰＣ符号の符号化及び復号化装置及び方法を提案する。さらに、本発明において、別途に図示及び説明してはいないが、図１を参照して説明した送受信機の構成に、本発明によるブロックＬＤＰＣ符号の符号化及び復号化装置を適用できることはもちろんである。
【００７２】
図１１は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列から分割された６個の部分行列のうち、部分行列Ｂの転置行列ＢＴ、部分行列Ｄ、及び部分行列Ｔを示す図である。
【００７３】
図１１を説明するに先立って、上記パリティ検査行列は、図８を参照して従来技術の部分で説明されたものと同一の部分ブロック構造を有する。すなわち、上記ブロックＬＤＰＣ符号のパリティ検査行列は、情報部分‘ｓ’、第１のパリティ部分ｐ１、及び第２のパリティ部分ｐ２に対する部分ブロックに分割される。ここで、上記情報部分‘ｓ’は、上記ブロックＬＤＰＣ符号を符号化する過程の間に、実際の情報語にマッピングされる上記パリティ検査行列の部分を示す。上記第１のパリティ部分ｐ１及び第２のパリティ部分ｐ２は、上記ブロックＬＤＰＣ符号を符号化する過程の間に実際のパリティにマッピングされる上記パリティ検査行列の部分を示す。
【００７４】
図８に示すように、上記情報部分‘s’は、部分ブロックＡと部分ブロックＣとに区分され、上記第１のパリティ部分ｐ１は、部分ブロックＢと部分ブロックＤとに区分され、上記第２のパリティ部分ｐ２は、部分ブロックＴと部分ブロックＥとに区分される。そして、部分行列Ａ及びＣは、上記部分ブロックＡ及び部分ブロックＣに対応し、部分行列Ｂ及びＤは、上記部分ブロックＢ及び部分ブロックＤに対応し、部分行列Ｔ及びＥは、上記部分ブロックＴ及び部分ブロックＥに対応する。
【００７５】
図１１を参照すると、上記部分行列Ｂは、２つの同一の順列行列
【数２９】
2008501287.tif 000031
及び０行列を含む。上記順列行列Ｐは、Ｎｓ×Ｎｓサイズを有する正方行列であり、上記順列行列Ｐは、上記順列行列Ｐを構成するＮｓ個の列の各々のウェイトが１であり、上記順列行列Ｐを構成するＮｓ個の行の各々のウェイトも１である行列を示す。ここで、上記順列行列ＰのサイズをＮｓ×Ｎｓとしているが、上記順列行列Ｐが正方行列であるため、そのサイズを、説明の便宜上、Ｎｓとも表現することに留意すべきである。
【００７６】
図９を参照して上述したように、上記部分行列Ｂは、順列行列
【数３０】
2008501287.tif 000032
及びＰＸ、０行列を含む。すなわち、従来のブロックＬＤＰＣ符号の場合に、ＥＴ−１Ｂ＋Ｄ＝Ｉを満足させるためには、上記部分行列Ｂの０行列ではない順列行列
【数３１】
2008501287.tif 000033
及びＰＸ は、図９を参照して説明したように固定されなければならず、また、順列行列
【数３２】
2008501287.tif 000034
及びＰＸ は、互いに異なる順列行列である。しかしながら、本発明では、上記部分行列Ｂの０行列ではない２個の順列行列
【数３３】
2008501287.tif 000035
の位置を固定させる必要がない、すなわち、上記２個の順列行列
【数３４】
2008501287.tif 000036
の位置を変えることができる。また、上記部分行列Ｔは、二重対角(dual diagonal)構造で、単位行列(Identity Matrix)Ｉと０行列とを含む。上記部分行列Ｄは、ＰＸの部分行列を含む。
【００７７】
図１１において、上記順列行列Ｐの上付き添字ａｉ及びｘは、上記順列行列Ｐの指数を示す。
【００７８】
上記２つの順列行列
【数３５】
2008501287.tif 000037
が上記部分行列Ｂの転置行列(transpose matrix)ＢＴにマッピングされ、上記順列行列ＰＸが上記部分行列Ｄにマッピングされることを一例にして説明したが、上記順列行列
【数３６】
2008501287.tif 000038
が、全部で３個ある順列行列のうち、上記部分行列Ｂの転置行列ＢＴと上記部分行列Ｄに対応づけられている２個の順列行列にマッピングされると、図１１を参照して説明したものと同一の効果を生ずる。すなわち、上記順列行列
【数３７】
2008501287.tif 000039
が上記部分行列Ｂの転置行列ＢＴに存在する２個の順列行列のうちのいずれか１個の順列行列にマッピングされ、上記順列行列
【数３８】
2008501287.tif 000040
が上記部分行列Ｄに存在する順列行列にマッピングされるとしても、図１１を参照して説明したものと同一の効果を有する。
【００７９】
これとは異なり、上記順列行列
【数３９】
2008501287.tif 000041
が上記部分行列Ｂの転置行列ＢＴに存在する２個の順列行列及び上記部分行列Ｄに存在する順列行列のすべてにマッピングされるとしても、図１１を参照して説明したものと同一の効果を有する。
【００８０】
また、図１１において、上述したように、上記順列行列の指数、すなわち、ａ１が０となる場合には、上記順列行列
【数４０】
2008501287.tif 000042
が単位行列となるために、上記順列行列
【数４１】
2008501287.tif 000043
は、単位行列となることもできる。また、上記順列行列の指数、すなわち、ａ１は、予め定められた値だけ増加し、上記順列行列は、上記予め定められた値だけ循環シフトされて、結果的に、上記順列行列
【数４２】
2008501287.tif 000044
が単位行列となる。
【００８１】
従来のブロックＬＤＰＣ符号の場合には、復号化器で使用されるパリティ検査行列をそのまま符号化器の生成行列(Ｇ；Generation Matrix)として使用する。しかしながら、本発明で提案するブロックＬＤＰＣ符号の場合には、復号化器で使用されるパリティ検査行列を符号化器の生成行列として使用するものではなく、上記復号化器で使用されるパリティ検査行列を変形して、符号化器の生成行列として使用することによって、上記ブロックＬＤＰＣ符号の符号化の複雑度も最小化させる。
Ｈで示されるパリティ検査行列は、下記（式５）に示すように表現されることができる。
【００８２】
【数４３】
2008501287.tif 000045
【００８３】
上記（式５）において、Ｈ１は、上記パリティ検査行列Ｈで情報語にマッピングされる行列、すなわち、情報部分‘ｓ’にマッピングされる行列を示し、Ｈ２は、上記パリティ検査行列Ｈでパリティにマッピングされる、すなわち、第１のパリティ部分ｐ１及び第２のパリティ部分ｐ２にマッピングされる行列を示す。すなわち、上記Ｈ１は、部分行列Ａと部分行列Ｃとを含む行列であり、上記Ｈ２は、部分行列Ｂと部分行列Ｔと、部分行列Ｄと、部分行列Ｅとを含む行列である。しかしながら、本発明で提案される符号化方式がＲｉｃｈａｒｄｓｏｎ−Ｕｒｂａｎｋｅ方式に基づかなくてもよいので、上記提案された符号化方式は、Ｒｉｃｈａｒｄｓｏｎ−Ｕｒｂａｎｋｅ方式のように、上記ブロックＬＤＰＣ符号のパリティ検査行列を６個の部分行列に分割する必要がない。すなわち、上記提案された方式は、上記パリティ検査行列を情報部分にマッピングされる行列Ｈ１と、第１のパリティ部分及び第２のパリティ部分にマッピングされる行列Ｈ２１及びＨ２２とに区分する。
【００８４】
一方、符号化器で使用される上記パリティ検査行列Ｈを変形した生成行列は、Ｈ’で示され、上記生成行列Ｈ’は、新たな行列Ｆを使用して下記（式６）のように表現することができる。
【数４４】
2008501287.tif 000046
上記（式６）において、Ｆは、サイズ（Ｎ−Ｋ）×（Ｎ−Ｋ）を有する行列を示し、Ｎは、符号のブロックサイズ又は符号語の長さを示し、Ｋは、情報語の長さを示す。上記行列Ｆは、図１２に示され、これは、下記で説明するので、その詳細な説明を省略する。上記（式５）を参照して説明したパリティ検査行列Ｈと同様に、上記生成行列Ｈ’は、情報語にマッピングされるＨ１’とパリティにマッピングされるＨ２’とに区分され、Ｈ２’は、第１のパリティにマッピングされるＨ２１’と第２のパリティにマッピングされるＨ２２’とに区分される。
【００８５】
上記（式６）に示す生成行列Ｈ’において、最後のブロックに該当する０行列ではないすべての順列行列の指数がモジューロ(modulo)-Ｎｓ演算を通してａｍだけ減少され、第２のパリティにマッピングされるＨ２２’は、ブロック単位の二重対角構造で単位行列を有し、上記単位行列を除いた残りの行列は、すべて０行列を含む。
【００８６】
次いで、上記生成行列Ｈ’を使用して上記ブロックＬＤＰＣ符号を符号化する過程について説明する。
【００８７】
まず、上記ブロックＬＤＰＣ符号の符号語ベクトル(vector)
【数４５】
2008501287.tif 000047
は、情報語ベクトル
【数４６】
2008501287.tif 000048
と、第１のパリティベクトル
【数４７】
2008501287.tif 000049
と、第２のパリティベクトル
【数４８】
2008501287.tif 000050
とに分割されることができる。上述したように、上記第１のパリティベクトル
【数４９】
2008501287.tif 000051
は、上記部分ブロックＢ及びＤにマッピングされ、上記第２のパリティベクトル
【数５０】
2008501287.tif 000052
は、部分ブロックＴ及びＥにマッピングされる。
【００８８】
上記第１のパリティベクトル
【数５１】
2008501287.tif 000053
の符号化は、下記（式７）及び（式８）を使用して遂行される。
【００８９】
まず、
【数５２】
2008501287.tif 000054
であるので、下記（式７）の関係を満足する。
【００９０】
【数５３】
2008501287.tif 000055
【００９１】
（式７）において、
【数５４】
2008501287.tif 000056
は、上記Ｈ１’のすべての行をブロック単位で加算したＮｓ×Ｋのサイズを有する行列を示す。ここで、上記ブロック単位の加算に基づく行列演算が図４を参照して説明したパリティ検査行列に適用されると、その演算結果の行列は、Ｎs×ｑＮｓ行列となり、各Ｎｓ×Ｎｓ行列は、各ブロック列に該当する順列行列をすべて加算した行列となる。例えば、第１のＮｓ×Ｎｓ行列は、図４において、
【数５５】
2008501287.tif 000057
の値を有する。
【００９２】
上記
【数５６】
2008501287.tif 000058
と同様に、
【数５７】
2008501287.tif 000059
は、上記Ｈ２１’のすべての行をブロック単位で加算したＮｓ×Ｎｓのサイズを有する行列を示す。また、
【数５８】
2008501287.tif 000060
は、上記Ｈ２２’のすべての行をブロック単位で加算したＮｓ×（Ｎ−Ｋ−Ｎｓ）のサイズを有する行列を示す。
【００９３】
ここで、“上記行列の行をブロック単位で加算する”ということは、該当行列に含まれた部分ブロックの各々の行を加算するにあたって、上記部分ブロックの各々のｌ番目に位置した行は、ｌ番目に位置した行同士のみで加算することを意味する。（式７）において、
【数５９】
2008501287.tif 000061
の演算は、上記Ｈ２２’が図１１に示す部分行列Ｔのように二重対角構造を有するので、行をブロック単位で加算した行列は、すべてのエレメントが０であるＮｓ×（Ｎ−Ｋ−Ｎｓ）サイズの０行列となる。
【数６０】
2008501287.tif 000062
がＮｓ×（Ｎ−Ｋ−Ｎｓ）サイズの０行列となるので、
【数６１】
2008501287.tif 000063
項は、上記（式７）から除去され、従って、行列Ｈ２１’は、図１１を参照して説明するような部分行列Ｂの特性に従って、下記（式８）のように表現されることができる。
【００９４】
【数６２】
2008501287.tif 000064
【００９５】
（式８）において、
【数６３】
2008501287.tif 000065
は、
【数６４】
2008501287.tif 000066
をｘだけ循環シフト(cyclic shift)したベクトルであり、
【数６５】
2008501287.tif 000067
は、上記第１のパリティベクトル
【数６６】
2008501287.tif 000068
の転置ベクトルを示す。
【００９６】
一方、上記第２のパリティベクトル
【数６７】
2008501287.tif 000069
は、上記Ｈ２２’が二重対角構造を有するために、逆代入(back substitution)方式を使用して容易に計算することができる。上記ブロックＬＤＰＣ符号は、反復蓄積(Repeat Accumulate；以下‘ＲＡ'と称する。)符号とは異なり、ブロック構造を有するために、上記逆代入方式をブロック単位で遂行することができ、上記第２のパリティベクトル
【数６８】
2008501287.tif 000070
の演算速度を増加させることができる。
【００９７】
まず、上記ＲＡ符号がパリティベクトル
【数６９】
2008501287.tif 000071
を有すると仮定すると、ｐ２は、ｐ１が決定された後に計算されることができる。これと同様に、ｐ２が決定された後にｐ３を計算することができる。従って、上記（Ｎ−Ｋ）個のパリティビットの各々を順次に計算しなければならない。
【００９８】
しかしながら、本発明で提案するブロックＬＤＰＣ符号の符号化過程では、生成行列Ｈ’のパリティにマッピングされる部分ブロックが二重対角構造を有するので、ｐ１から
【数７０】
2008501287.tif 000072
を同時に計算することができ、次のＮｓ個のビットを以前のステップで計算したｐ１から
【数７１】
2008501287.tif 000073
を使用して同時に計算できる。したがって、本発明で提案するブロックＬＤＰＣ符号の符号化過程は上記ＲＡ符号の符号化過程よりＮｓ倍さらに速い。
図１３は、本発明の実施形態によるブロックＬＤＰＣ符号のパリティ検査行列を示す図である。図１３に示すパリティ検査行列は、符号化率が１／２であるブロックＬＤＰＣ符号のパリティ検査行列を示し、１２×２４個のブロックを含む。
【００９９】
図１３において、各ブロック内の数字は、該当ブロックに位置した順列行列の指数値を示し、Ｉは、該当ブロックに位置した単位行列を示す。一方、ブロックサイズＮｓを有するブロックＬＤＰＣ符号のパリティ検査行列に対する順列行列の指数値は、該当ブロックに位置した順列行列の指数値の各々に対してモジュロ−Ｎｓ演算を遂行することによって計算されることができる。すなわち、該当ブロックの指数値が該当ブロックのサイズＮｓよりも大きい場合には、上記モジュロ−Ｎｓ演算が遂行されなければならないことを意味する。
【０１００】
一般的に、上記指数値はＮｓより小さくなければならない。しかしながら、上記同一のパリティ検査行列が大きいブロックサイズ及び小さいブロックサイズで共通に使用される場合に、上記Ｎｓよりもさらに大きい指数値が行列に含まれる場合がある。このような場合、符号化率及びブロックサイズに従って多くのパリティ検査行列が必要とされるが、必要とされるメモリの容量は減少する。上記順列行列の指数にＮｓでモジュロ演算を遂行した結果、その値が０であれば、該当ブロックに位置する順列行列は、単位行列となる。
【０１０１】
図１４は、本発明の実施形態によるブロックＬＤＰＣ符号の生成行列を示す図である。しかしながら、図１４を説明する前に、上述したように、上記生成行列Ｈ’は上記パリティ検査行列Ｈに行列Ｆを乗じて生成された行列である。上記行列Ｆは、図１２を参照して説明される。
【０１０２】
図１２は、本発明の実施形態による生成行列Ｈ’を生成するために使用される行列Ｆを示す図である。図１２を参照すると、上記行列Ｆにおいて、単位行列Ｉは、対角線に沿って位置し、順列行列
【数７２】
2008501287.tif 000074
は、上記対角線の最後部分に位置する行列である。
ここで、上記順列行列
【数７３】
2008501287.tif 000075
は、上記パリティ検査行列の順列行列Ｅの最後の部分に位置する順列行列
【数７４】
2008501287.tif 000076
のネガティブ指数（negative exponent）を有する順列行列である。そして、図１２では、ａｍを１（ａｍ＝１）と仮定する。
図１４を参照すると、上述したように、上記生成行列Ｈ’は、上記パリティ検査行列Ｈに上記行列Ｆを乗算した行列である。しかしながら、上述したように、上記行列Ｆの最後部分に位置する順列行列
【数７５】
2008501287.tif 000077
がＰ−１であるので、上記生成行列Ｈ’は、上記パリティ検査行列Ｈと比較して、上記生成行列Ｈ’の最後のブロック行に位置した行列のみ、その指数が１ずつ小さな値を有する。
【０１０３】
図１５は、本発明の実施形態によるブロックＬＤＰＣ符号を符号化する手順を示すフローチャートである。図１５を参照すると、まず、ステップ１５１１で、制御器(図示せず)は、上記ブロックＬＤＰＣ符号に符号化される情報語ベクトル
【数７６】
2008501287.tif 000078
を受信する。ここで、上記情報語ベクトル
【数７７】
2008501287.tif 000079
は上記ブロックＬＤＰＣ符号に符号化するための符号化率に対応するサイズを有し、上記情報語ベクトル
【数７８】
2008501287.tif 000080
のサイズがｋであると仮定する。
【０１０４】
ステップ１５１３で、上記制御器は、生成行列Ｈ’のＨ１’でのすべての行をブロック単位で加算した行列と上記受信された情報語ベクトル
【数７９】
2008501287.tif 000081
の転置ベクトルとを使用して、第１のパリティベクトル
【数８０】
2008501287.tif 000082
を計算する。ここで、上記生成行列Ｈ’のＨ１’でのすべての行をブロック単位で加算した行列は、Ｎｓ×Ｋのサイズを有し、第１のパリティベクトル
【数８１】
2008501287.tif 000083
は、上記（式８）を使用して計算される。
【０１０５】
ステップ１５１５で、上記制御器は、上記情報語ベクトル
【数８２】
2008501287.tif 000084
と第１のパリティベクトル
【数８３】
2008501287.tif 000085
とを使用して、逆代入方式によって第２のパリティベクトル
【数８４】
2008501287.tif 000086
を計算した後、ステップ１５１７で、上記制御器は、上記情報語ベクトル
【数８５】
2008501287.tif 000087
と、第１のパリティベクトル
【数８６】
2008501287.tif 000088
と、第２のパリティベクトル
【数８７】
2008501287.tif 000089
とを使用して符号語ベクトル
【数８８】
2008501287.tif 000090
を生成し、上記生成された符号語ベクトル
【数８９】
2008501287.tif 000091
を送信する。
【０１０６】
図１６は、本発明の実施形態によるブロックＬＤＰＣ符号の符号化装置の内部構成を示すブロック図である。図１６を参照すると、上記ブロックＬＤＰＣ符号の符号化装置は、行列乗算器１６１１と、メモリ１６１３と、循環シフト器１６１５と、逆代入方式処理器１６１７と、スイッチ１６１９，１６２１，及び１６２３と、を含む。
【０１０７】
まず、入力信号、すなわち、ブロックＬＤＰＣ符号に符号化したい長さｋの情報語ベクトル
【数９０】
2008501287.tif 000092
が入力され、上記入力された長さｋの情報語ベクトル
【数９１】
2008501287.tif 000093
は、スイッチ１６１９と、行列乗算器１６１１と、逆代入方式処理器１６１７とへ入力される。ここで、行列乗算器１６１１は、上記情報語ベクトル
【数９２】
2008501287.tif 000094
とメモリ１６１３に記憶されている生成行列Ｈ’のＨ１’でのすべての行をブロック単位で加算したＮｓ×Ｋのサイズを有する行列を乗算した後、その乗算結果を循環シフト器１６１５へ出力する。行列乗算器１６１１から出力された信号は、第１のパリティベクトル
【数９３】
2008501287.tif 000095
の転置ベクトル
【数９４】
2008501287.tif 000096
をｘだけ循環シフトしたベクトル
【数９５】
2008501287.tif 000097
である。
【０１０８】
循環シフト器１６１５は、行列乗算器１６１１から出力された信号を上記ｘだけ逆に循環シフトして、第１のパリティベクトル
【数９６】
2008501287.tif 000098
の転置ベクトル
【数９７】
2008501287.tif 000099
を計算し、第１のパリティベクトル
【数９８】
2008501287.tif 000100
の転置ベクトル
【数９９】
2008501287.tif 000101
を使用して、第１のパリティベクトル
【数１００】
2008501287.tif 000102
を計算し、その計算の結果を逆代入方式処理器１６１７及びスイッチ１６２１へ出力する。
逆代入方式処理器１６１７は、上記情報ベクトル
【数１０１】
2008501287.tif 000103
及び循環シフト器１６１５から出力された第１のパリティベクトル
【数１０２】
2008501287.tif 000104
を使用して、逆代入方式によって第２のパリティベクトル
【数１０３】
2008501287.tif 000105
を計算した後、その計算の結果をスイッチ１６２３へ出力する。
【０１０９】
一方、スイッチ１６１９，１６２１，１６２３の各々は、自身が伝送する時点でのみスイッチングオンされて、当該信号を伝送する。すなわち、スイッチ１６１９は、情報語ベクトル
【数１０４】
2008501287.tif 000106
が伝送される時点でスイッチングオンされ、スイッチ１６２１は、第１のパリティベクトル
【数１０５】
2008501287.tif 000107
が伝送される時点でスイッチングオンされ、スイッチ１６２３は、第２のパリティベクトル
【数１０６】
2008501287.tif 000108
が伝送される時点でスイッチングオンされる。
【０１１０】
一方、上記ＬＤＰＣ符号系列のすべての符号は、ファクターグラフ上において、和積アルゴリズムにより復号化することが可能である。上記ＬＤＰＣ符号の復号化方式は、双方向伝達方式と流れ伝達方式とに大別できる。上記双方向伝達方式を使用して復号化動作を行う場合に、各検査ノードは、各々１つノードプロセッサーを有するので、復号化の複雑度が上記検査ノードの数に比例して増加する。しかしながら、すべての検査ノードが同時に更新されるために、復号化の速度は、非常に速くなる。
【０１１１】
これとは異なり、上記流れ伝達方式は、１個のノードプロセッサーが存在してすべてのファクターグラフ上のノードを通過しながら情報を更新する。従って、復号化の複雑度は簡素になるが、パリティ検査行列のサイズが大きくなるほど、すなわち、ノードの数が増えるほど、復号化の速度が遅くなる。しかしながら、本発明で提案されるブロックＬＤＰＣ符号のように、ブロック単位でパリティ検査行列を生成すると、復号化の間に、上記パリティ検査行列を構成しているブロックの数と同一数のノードプロセッサーが使用される。この場合、上記双方向伝達方式よりは、復号化の複雑度が減少され、また、上記流れ伝達方式よりは、復号化の速度が速い復号化器を実現することができる。
【０１１２】
図１７は、本発明の実施形態によるブロックＬＤＰＣ符号の復号化装置の内部構成を示すブロック図である。図１７を参照すると、ブロックＬＤＰＣ符号の復号化装置は、ブロック制御器１７１０と、変数ノードパート１７００と、加算器１７１５と、デインターリーバ１７１７と、インターリーバ１７１９と、制御器１７２１と、メモリ１７２３と、加算器１７２５と、検査ノードパート１７５０と、硬判定器１７２９と、を含む。変数ノードパート１７００は、変数ノード復号化器１７１１と、スイッチ１７１３及び１７１４と、を含み、検査ノードパート１７５０は、検査ノード復号化器１７２７を含む。
まず、無線チャネルを介して受信される受信信号は、ブロック制御器１７１０へ入力される。ブロック制御器１７１０は、上記受信信号のブロックサイズを決定し、また、上記復号化装置に対応する符号化装置でパンクチュアリングされた情報語部分が存在する場合、上記パンクチュアリングされた情報語部分に‘０’を挿入して全体のブロックサイズを調整した後、変数ノード復号化器１７１１へ出力する。
【０１１３】
変数ノード復号化器１７１１は、ブロック制御器１７１０から出力された信号を受信し、ブロック制御器１７１０から出力された信号の確率値を計算し、上記計算された確率値を更新した後、スイッチ１７１３及びスイッチ１７１４へ出力する。ここで、変数ノード復号化器１７１１は、上記ブロックＬＤＰＣ符号の復号化装置に予め設定されているパリティ検査行列に従って変数ノードを接続し、上記変数ノードに接続された１の個数と同じ個数の入力値と出力値とを有する更新演算が遂行される。上記変数ノードの各々に接続された１の個数は、上記パリティ検査行列を構成する列の各々のウェイトと同一である。従って、上記パリティ検査行列を構成する列の各々のウェイトに従って、上記変数ノード復号化器１７１１の内部演算が異なる。スイッチ１７１３がスイッチングオンされる場合のみを除外し、スイッチ１７１４は、変数ノード復号化器１７１１の出力信号を加算器１７１５へ出力するようにスイッチングオンされる。
【０１１４】
加算器１７１５は、変数ノード復号化器１７１１から出力された信号と以前の反復復号化過程（iteration decoding）におけるインターリーバ１７１９の出力信号とを受信し、変数ノード復号化器１７１１から出力された信号から以前の反復復号化過程におけるインターリーバ１７１９の出力信号を減算した後、デインターリーバ１７１７へ出力する。ここで、上記復号化過程が最初の復号化過程である場合に、インターリーバ１７１９の出力信号が‘０’であると見なさなければならない。
【０１１５】
デインターリーバ１７１７は、加算器１７１５から出力された信号を受信し、予め設定されている方式に従ってデインターリービングした後、加算器１７２５及び検査ノード復号化器１７２７へ出力する。ここで、デインターリーバ１７１７の内部構成は、上記パリティ検査行列に相当する構成を有し、その理由は、上記パリティ検査行列の‘１’の値を有するエレメントの位置に従って、デインターリーバ１７１７に対応するインターリーバ１７１９の入力値に対する出力値が異なるためである。
【０１１６】
加算器１７２５は、以前の反復復号化過程における検査ノード復号化器１７２７の出力信号とデインターリーバ１７１７の出力信号とを受信し、上記以前の反復復号化過程における検査ノード復号化器１７２７の出力信号からデインターリーバ１７１７の出力信号を減算した後に、インターリーバ１７１９へ出力する。検査ノード復号化器１７２７は、上記ブロックＬＤＰＣ符号の復号化装置に予め設定されているパリティ検査行列に従って検査ノードを接続し、上記検査ノードに接続された‘１’の個数だけの入力値と出力値とを有する更新演算が行われる。上記検査ノードの各々に接続された‘１’の個数は、上記パリティ検査行列を構成する行の各々のウェイトと同一である。従って、上記パリティ検査行列を構成している行の各々のウェイトに従って、検査ノード復号化器１７２７の内部演算が異なる。
【０１１７】
ここで、インターリーバ１７１９は、制御器１７２１の制御によって予め設定されている方式にて、加算器１７２５から出力された信号をインターリービングした後に、加算器１７１５及び変数ノード復号化器１７１１へ出力する。ここで、制御器１７２１は、メモリ１７２３に記憶されているインターリービング方式に関連した情報を読み込んで、インターリーバ１７１９のインターリービング方式を制御する。また、上記復号化過程が最初の復号化過程である場合には、デインターリーバ１７１７の出力信号が０’であると見なさなければならない。
【０１１８】
上記のような過程を繰り返し遂行することによって、エラーを起こすことなく、高信頼度の復号化を遂行する。
【０１１９】
予め設定された回数だけ反復復号化を行った後に、スイッチ１７１４は、上記変数ノード復号化器１７１１と加算器１７１５との間の接続をスイッチングオフにした後、スイッチ１７１３は、変数ノード復号化器１７１１と硬判定器１７２９との間の接続をスイッチングオンにして、変数ノード復号化器１７１１から出力された信号を硬判定器１７２９へ出力する。硬判定器１７２９は、変数ノード復号化器１７１１から出力された信号を硬判定した後、その硬判定の結果を出力し、硬判定器１７２９の出力値は、最終的に復号化された値となる。
【０１２０】
なお、本発明の詳細な説明においては、具体的な実施の形態について説明したが、本発明の範囲から逸脱しない範囲内であれば、種々な変形が可能であることは言うまでもない。よって、本発明の範囲は、上述した実施の形態に限定されるものではなく、特許請求の範囲とその均等物によって定められるべきである。
【図面の簡単な説明】
【０１２１】
【図１】従来の移動通信システムにおける送受信機の構成を概略的に示す図である。
【図２】従来の(８，２，４)ＬＤＰＣ符号のパリティ検査行列を示す図である。
【図３】図２に示した(８，２，４)ＬＤＰＣ符号のファクターグラフを示す図である。
【図４】従来のブロックＬＤＰＣ符号のパリティ検査行列を概略的に示す図である。
【図５】図４に示した順列行列Ｐを示す図である。
【図６】パリティ検査行列が４個の部分行列で構成されたブロックＬＤＰＣ符号のサイクル構成を概略的に示す図である。
【図７】完全下三角行列と類似した形状を有するパリティ検査行列を示す図である。
【図８】図７に示したパリティ検査行列を６個の部分ブロックに分割して示す図である。
【図９】図８に示した部分行列Ｂの転置行列、部分行列Ｅ、部分行列Ｔ、及び部分行列Ｔの逆行列を示す図である。
【図１０】従来のブロックＬＤＰＣ符号のパリティ検査行列の生成手順を示すフローチャートである。
【図１１】本発明の実施形態による不均一ブロックＬＤＰＣ符号のパリティ検査行列から分割された６個の部分行列のうち、部分行列Ｂの転置行列ＢＴ、部分行列Ｄ、及び部分行列Ｔを示す図である。
【図１２】本発明の実施形態による生成行列Ｈ’を生成するために使用される行列Ｆを示す図である。
【図１３】本発明の実施形態による不均一ブロックＬＤＰＣ符号のパリティ検査行列を示す図である。
【図１４】本発明の実施形態による不均一ブロックＬＤＰＣ符号の生成行列を示す図である。
【図１５】本発明の実施形態による不均一ブロックＬＤＰＣ符号を符号化する手順を示すフローチャートである。
【図１６】本発明の実施形態による不均一ブロックＬＤＰＣ符号の符号化装置の内部構成を示すブロック図である。
【図１７】本発明の実施形態による不均一ブロックＬＤＰＣ符号の復号化装置の内部構成を示すブロック図である。
【符号の説明】
【０１２２】
１６１１  行列乗算器
１６１３  メモリ
１６１５  循環シフト器
１６１７  逆代入方式処理機
１６１９  スイッチ
１６２１  スイッチ
１６２３  スイッチ
【図１】
2008501287.tif 000125
【図２】
2008501287.tif 000126
【図３】
2008501287.tif 000127
【図４】
2008501287.tif 000128
【図５】
2008501287.tif 000129
【図６】
2008501287.tif 000130
【図７】
2008501287.tif 000131
【図８】
2008501287.tif 000132
【図９】
2008501287.tif 000133
【図１０】
2008501287.tif 000134
【図１１】
2008501287.tif 000135
【図１２】
2008501287.tif 000136
【図１３】
2008501287.tif 000137
【図１４】
2008501287.tif 000138
【図１５】
2008501287.tif 000139
【図１６】
2008501287.tif 000140
【図１７】
2008501287.tif 000141
【国際調査報告】
2008501287.tif 000142