(57)【要約】      （修正有）【課題】ＬＤＰＣ復号を簡易化し、復号化性能を向上する。【解決手段】検査ノードの中で、検査ノード処理を遂行する少なくとも一つの検査ノードを選択するスケジューラーと、前記変数ノードに対する入力ＬＬＲ値を初期値として格納し、検査ノードに接続された変数ノードに対してアップデートされたＬＬＲ値を格納するＬＬＲメモリと、検査ノードに対して検査ノード処理が遂行された結果である検査ノードメッセージを格納するメモリと、ＬＬＲメモリから読み出された該当ＬＬＲ値から、検査ノードメッセージメモリに格納されている前記選択された検査ノードの検査ノードメッセージを減算して変数ノードメッセージを生成し、変数ノードメッセージに対して検査ノード処理を遂行し、検査ノード処理結果値に変数ノードメッセージを加算してアップデートされたＬＬＲ値を計算しメモリに伝達する少なくとも一つの統合ノードプロセッサーと、を含むことを特徴とする。【選択図】図７
2006148937.tif 000002
【特許請求の範囲】
【請求項１】
パリティ検査ノード行列により複数の検査ノードと複数の変数ノードで構成される低密度パリティ検査符号を復号する装置であって、
前記検査ノードの中で、検査ノード処理を遂行する少なくとも一つの検査ノードを選択する検査ノード選択スケジューラーと、
前記変数ノードに対する入力ＬＬＲ(Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ)値を初期ＬＬＲ値として格納し、前記選択された検査ノードに接続された変数ノードに対してアップデートされたＬＬＲ値を格納するＬＬＲメモリと、
前記選択された検査ノードに対して検査ノード処理が遂行された結果である検査ノードメッセージを格納する検査ノードメッセージメモリと、
前記ＬＬＲメモリから読み出された該当ＬＬＲ値から、前記検査ノードメッセージメモリに格納されている前記選択された検査ノードの検査ノードメッセージを減算して変数ノードメッセージを生成し、前記変数ノードメッセージに対して検査ノード処理を遂行し、前記検査ノード処理結果値に前記変数ノードメッセージを加算してアップデートされたＬＬＲ値を計算し、前記計算されたＬＬＲ値を前記ＬＬＲメモリに伝達する少なくとも一つの統合ノードプロセッサーと、
を含むことを特徴とする装置。
【請求項２】
前記検査ノード選択スケジューラーは、前記複数の検査ノードを一つずつインデキシングしてインデキシング順に選択し、或いは一定規則に従って前記複数の検査ノードのうちの少なくとも一つを選択することを特徴とする請求項１記載の装置。
【請求項３】
前記検査ノード選択スケジューラーは、前記ＬＬＲメモリから同じＬＬＲ値が同時に読み出されないように前記少なくとも一つの検査ノードを選択することを特徴とする請求項２記載の装置。
【請求項４】
前記選択された検査ノードと関連した変数ノードメッセージは、前記選択された検査ノードの検査ノードメッセージを前記接続された変数ノードの瞬時ＬＬＲ値から減算することで、下記の式のように計算されることを特徴とする請求項１記載の装置。
【数１】
2006148937.tif 000022
ここで、ｍは前記選択された検査ノードのインデックスで、ｎは前記選択された検査ノードと接続される変数ノードのインデックスで、
【数２】
2006148937.tif 000023
はｊ＋１番目の反復復号時の変数ノードメッセージで、
【数３】
2006148937.tif 000024
は前記選択された検査ノードに対するノード処理が始まる前段階のｎ番目の変数ノードの瞬時ＬＬＲ値である。
【請求項５】
前記検査ノードメッセージは、下記の式のように計算されることを特徴とする請求項４記載の装置。
【数４】
2006148937.tif 000025
ここで、
【数５】
2006148937.tif 000026
はｊ＋１番目の反復時の検査ノードメッセージで、Ｆは検査ノードメッセージの検査ノード処理関数で、ｄｃはｍ番目の検査ノードと接続された変数ノードメッセージの数である。また、ｎは、前記変数ノードメッセージのインデックスで、ｎ０乃至
【数６】
2006148937.tif 000027
の範囲を有する。
【請求項６】
前記アップデートされたＬＬＲ値は、下記の式のように計算されることを特徴とする請求項５記載の装置。
【数７】
2006148937.tif 000028
ここで、
【数８】
2006148937.tif 000029
は前記アップデートされたＬＬＲ値で、
【数９】
2006148937.tif 000030
は前記初期ＬＬＲ値である。
【請求項７】
前記アップデートされたＬＬＲ値を用いて硬判定を遂行する硬判定部と、
前記硬判定された結果を格納するビットバッファ部と、
前記硬判定された結果に対してパリティ検査を遂行し、パリティ検査結果が良いと、前記統合ノードプロセッサーの動作を中断させ、前記パリティ検査結果が悪いと、前記統合ノードプロセッサーの動作を反復させるパリティ検査部と、
をさらに含むことを特徴とする請求項１記載の装置。
【請求項８】
前記パリティ検査部は、前記複数の検査ノードがすべて一度ずつ選択されたときに前記パリティ検査を遂行することを特徴とする請求項１記載の装置。
【請求項９】
前記ＬＬＲメモリ及び検査ノードメッセージメモリは、前記複数の検査ノードに各々対応するサブメトリックブロックに分割されることを特徴とする請求項１記載の装置。
【請求項１０】
前記サブメトリックブロックは、それぞれ該当検査ノードに対応する検査ノードメッセージ値或いは該当検査ノードに接続された変数ノードのＬＬＲ値を格納することを特徴とする請求項９記載の装置。
【請求項１１】
前記少なくとも一つの統合ノードプロセッサーは、前記選択された少なくとも一つの選択された検査ノードに対応することを特徴とする請求項１記載の装置。
【請求項１２】
パリティ検査ノード行列により複数の検査ノードと複数の変数ノードで構成される低密度パリティ検査符号を復号する方法であって、
前記複数の検査ノードのうち検査ノード処理を遂行する少なくとも一つの検査ノードを選択する段階と、
前記選択された検査ノードに対応する検査ノードメッセージを読み出し、前記検査ノードと接続された変数ノードのＬＬＲ値から前記検査ノードメッセージ値を減算して変数ノードメッセージを計算する段階と、
前記計算された変数ノードメッセージに検査ノード処理を遂行して検査ノードメッセージを生成し、前記生成された検査ノードメッセージを格納する段階と、
前記ＬＬＲ値に前記生成された検査ノードメッセージを加算してアップデートされたＬＬＲ値を計算し格納する段階と、
前記アップデートされたＬＬＲ値に対して硬判定及びパリティ検査を遂行する段階と、
を有することを特徴とする方法。
【請求項１３】
前記選択する段階は、
前記複数の検査ノードを一つずつインデキシングしてインデキシング順に選択し、或いは一定規則に従って前記複数の検査ノードのうちの少なくとも一つを選択することを特徴とする請求項１２記載の方法。
【請求項１４】
同じＬＬＲ値が同時に読み出されないように少なくとも一つの検査ノードを選択することを特徴とする請求項１３記載の方法。
【請求項１５】
前記選択された検査ノードと関連した変数ノードメッセージは、前記選択された検査ノードの検査ノードメッセージを前記接続された変数ノードの瞬時ＬＬＲ値から減算することで、下記の式のように計算されることを特徴とする請求項１２記載の方法。
【数１０】
2006148937.tif 000031
ここで、ｍは前記選択された検査ノードのインデックスで、ｎは前記選択された検査ノードと接続される変数ノードのインデックスで、
【数１１】
2006148937.tif 000032
はｊ＋１番目の反復復号時の変数ノードメッセージで、
【数１２】
2006148937.tif 000033
は前記選択された検査ノードに対するノード処理が始まる前段階のｎ番目の変数ノードの瞬時ＬＬＲ値である。
【請求項１６】
前記検査ノードメッセージは、下記の式のように計算されることを特徴とする請求項１５記載の方法。
【数１３】
2006148937.tif 000034
ここで、
【数１４】
2006148937.tif 000035
はｊ＋１番目の反復時の検査ノードメッセージで、Ｆは検査ノードメッセージの検査ノード処理関数で、ｄｃはｍ番目の検査ノードと接続された変数ノードメッセージの数である。また、ｎは、前記変数ノードメッセージのインデックスで、ｎ０乃至
【数１５】
2006148937.tif 000036
の範囲を有する。
【請求項１７】
前記アップデートされたＬＬＲ値は、下記の式のように計算されることを特徴とする請求項１６記載の方法。
【数１６】
2006148937.tif 000037
ここで、
【数１７】
2006148937.tif 000038
は前記アップデートされたＬＬＲ値で、
【数１８】
2006148937.tif 000039
は前記初期ＬＬＲ値である。
【請求項１８】
前記硬判定及びパリティ検査を遂行する段階は、
硬判定を遂行し、前期硬判定された結果に対してパリティ検査を遂行し、パリティ検査の結果が良いと、復号を中断し、パリティ検査の結果が悪いと、反復復号を遂行するパリティ検査部をさらに含んでなることを特徴とする請求項１３記載の方法。
【請求項１９】
前記パリティ検査は、前記複数の検査ノードがすべて一度ずつ選択されたときに前記パリティ検査を遂行することを特徴とする請求項１２記載の方法。
【請求項２０】
前記ＬＬＲ値及び検査ノードメッセージは、前記複数の検査ノードに各々対応するサブメトリックブロックに分割されたメモリに格納されることを特徴とする請求項１２記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はエラー訂正復号化装置及びその方法に関するもので、特に、低密度パリティ検査符号(Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅ：以下、“ＬＤＰＣ符号”とする)の復号の複雑度を低下して復号化性能を向上させる復号化装置及び方法に関するものである。
【背景技術】
【０００２】
通常、デジタル通信システムは伝送路で発生する雑音によって誤りが発生し、この発生した誤りを除去するために多様な方式で誤り訂正を遂行している。最近、標準化が進行中である３ＧＰＰ(３ｒｄ  Ｇｅｎｅｒａｔｉｏｎ  Ｐａｒｔｎｅｒｓｈｉｐ  Ｐｒｏｊｅｃｔ)又は３ＧＰＰ  ２を適用する無線通信システムでは、音声及び制御信号の伝送のために畳み込み符号(ｃｏｎｖｏｌｕｔｉｏｎａｌ  ｃｏｄｅ)とターボ符号(ｔｕｒｂｏ  ｃｏｄｅ)の使用が提案されている。高速伝送のためのターボ符号は、低い信号対雑音比で非常に低いビット誤り率が得られるという長所を有する。しかしながら、このターボ符号は、符号語の最小距離特性によってターボ符号で符号化された信号の復元の際に希望するビット誤り部分で誤りフロー(ｅｒｒｏｒ  ｆｌｏｏｒ)が発生することがある。また、ターボ符号は、復号時に誤りが発生した符号語に対する検出不可能確率が比較的高いという問題を有する。したがって、最近ではターボ符号と類似し、或いは優れた性能を有するＬＤＰＣ符号が新たに提示されている。
【０００３】
このＬＤＰＣ符号は、同一の長さのターボ符号に比べて最小距離が大きい。その結果、誤りフローがターボ符号に比べて非常に低いビット誤り率で発生し、誤りが発生した符号語に対する検出不可能確率が非常に低くて実験的に‘０’に近い。また、並列構造への実現が可能なため、復号時間を画期的に短縮させ、反復復号ごとに遂行するパリティ検査を通じて追加されるＣＲＣ(Ｃｙｃｌｉｃ  Ｒｅｄｕｎｄａｎｃｙ  Ｃｈｅｃｋ)のようなオーバーヘッド又は復号停止アルゴリズムがなくても効率的な復号停止が可能である。
【０００４】
図１は、ＬＣＰＣ構造を示す図である。
【０００５】
図１を参照すると、ＬＤＰＣ符号は符号を定義するパリティ検査行列(Ｐａｒｉｔｙ  ｃｈｅｃｋ  ｍａｔｒｉｘ）の各行と列に‘１’の数が大変小さい符号であって、検査ノード(ｃｈｅｃｋ  ｎｏｄｅ)１００と、変数ノード(ｖａｒｉａｂｌｅ  ｎｏｄｅ)１１０と、検査ノード１００と変数ノード１１０とを接続するエッジ(ｅｄｇｅ)１１５とから構成されたファクターグラフ(ｆａｃｔｏｒ  ｇｒａｐｈ)により、その構造が定義できる。検査ノード１００から検査ノード処理(ｃｈｅｃｋ  ｎｏｄｅ  ｐｒｏｃｅｓｓｉｎｇ)後に変数ノード１１０に伝達される値は、検査ノードメッセージ１１５ａとなり、変数ノード１１０から変数ノード処理後に検査ノード１００に伝達される値は変数ノードメッセージ１１５ｂとなる。
【０００６】
ＬＤＰＣ符号の復号過程は、一般的にｓｕｍ-ｐｒｏｄｕｃｔアルゴリズムによる反復復号(ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ)により遂行される。このとき、最適のｓｕｍ-ｐｒｏｄｕｃｔアルゴリズムは、多少複雑な計算式を含む。これを単純化したＭｉｎ-ｓｕｍアルゴリズムのような準最適方法のｍｅｓｓａｇｅ-ｐａｓｓｉｎｇアルゴリズムを用いる復号も可能である。
【０００７】
以下、図２を参照して、ＬＤＰＣ符号についてより詳細に説明する。
【０００８】
図２は、ファクターグラフ及びパリティ検査行列によるＬＤＰＣ符号構造の一例を示す図である。
【０００９】
図２を参照すると、ＬＤＰＣ符号のファクターグラフは、定められたＬＤＰＣ符号のパリティ検査式を示す４個の検査ノード２００と、各シンボルを示す８個の変数ノード２１０と、これらの連関性を示すエッジ２２０とから構成される。エッジ２２０は、検査ノード２００が示すパリティ検査式に含まれるコードシンボルに該当する変数ノード２１０とこの検査ノード２００とを接続する。ここでは、すべての検査ノード２００の各々に接続される変数ノードの数が６個に一定し、すべての変数ノード２１０の各々に接続された検査ノードの数が３個に一定した正規ＬＤＰＣ符号を例として示す。図示しないが、各検査ノードと変数ノードに接続された分岐の数が一定でないＬＤＰＣ符号は非正規ＬＤＰＣ符号と称する。
【００１０】
また、ファクターグラフに対応するパリティ検査行列(Ｈ)２３０は、図２に示す。これは、パリティ検査式のグラフィック表現と類似し、パリティ検査行列２３０の各列及び各行には同一の個数の１がある。すなわち、パリティ検査行列２３０の各列は各変数ノード２１０に対する検査ノード２００の接続を示す３個の１を有し、各行は各検査ノード２００に対する変数ノード２１０の接続を示す６個の１を有する。
【００１１】
このＬＤＰＣを復号化する過程は、ファクターグラフ上の変数ノードと検査ノードが各ノード別に生成及びアップデートしたメッセージを相互に交換する過程を反復してなされる。このとき、各ノードではｓｕｍ-ｐｒｏｄｕｃｔアルゴリズム或いはそれに類似した準最適の方法を用いてメッセージがアップデートされる。これに基づいたＬＤＰＣ符号の反復復号過程は、下記のようである。
【００１２】
図３は、一般的なＬＤＰＣ符号の全体ブロック構成を示す図である。
【００１３】
図３を参照すると、ＬＤＰＣ復号化装置は、受信情報を格納しているメモリブロック３００と、変数ノードに対する演算を遂行する変数ノードプロセッサー３４０と、検査ノードに対する演算を遂行する検査ノードプロセッサー３２０と、検査ノードでエラーがすべて訂正されたかを検査して反復復号するか否かを決定するパリティ検査ブロック３３０と、メモリアクセスコントローラ３４０とから構成される。
【００１４】
ＬＤＰＣの概略的な復号手順は、次のようである。
【００１５】
１．受信されたシンボルが変数ノードの初期ＬＬＲ(Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ)値としてメモリ３００に格納される。このとき、メモリ３００に格納されているＬＬＲ値は、自分の関連したエッジへの変数ノードの出力メッセージとなる。
【００１６】
２．検査ノードプロセッサー３２０がメモリ３００に格納された変数ノード値(すなわち、変数ノードメッセージであるＬＬＲ値）を読み出す。パリティー検査ブロック３３０は、読み出された変数ノード値のパリティ検査を遂行し、検査ノードプロセッサー３２０は、変数ノード値の０と１に対する伝送路遷移確率を計算し、この計算された確率値(検査ノードメッセージ）を再びメモリ３００の変数ノード値として上書き(ｏｖｅｒｗｒｉｔｅ)する。
【００１７】
３．変数ノードプロセッサー３４０は、メモリ３００に上書きされた変数ノード値を読み出して最終ＬＬＲ値を含む変数ノードメッセージを計算する。
【００１８】
４．パリティー検査ブロック３３０で、パリティー検査に成功して反復復号の終了を決定するまで、上記のステップ２，３を反復することで信頼度を高める。
【００１９】
ここで、変数ノードプロセッサー３４０及び検査ノードプロセッサー３２０は、それぞれパリティ検査行列の列と行で１の位置に該当するメモリ領域から値を読み出して計算した後に、同一のメモリ領域に更に格納する。
【００２０】
ステップ２、３で、変数ノード及び検査ノードプロセッサー３４０，３２０は、それぞれ自機と接続されているエッジからの入力(検査ノードメッセージ及び変数ノードメッセージ）を通じて出力メッセージを計算する。ここで、検査ノードプロセッサー３２０と、変数ノードプロセッサー３４０の各々はパリティ検査行列の列と行で、１の位置に該当するメモリブロック３００のサブブロックの値を読み出して計算した後に格納する。
【００２１】
以下、変数ノードメッセージ及び検査ノードメッセージの計算過程について、詳細に説明する。ここで、デグリー(ｄｅｇｒｅｅ）ｄｃは、検査ノードに接続される変数ノードの数を示し、パリティ検査行列で各列に存在する１の個数と同一である。そして、ｄｖは、変数ノードに接続される検査ノードの数を示し、パリティ検査行列で各行に存在する１の個数と同一である。
【００２２】
まず、ｍ番目の検査ノードからｎ番目の変数ノードに伝送される検査ノードメッセージを下記の＜数１＞のようにアップデートされる。
【００２３】
【数１】
2006148937.tif 000003
【００２４】
すなわち、上記の＜数１＞は、ｄｃ個の変数ノードに接続されたｍ番目の検査ノードメッセージのｊ番目の反復復号時の計算式で、
【００２５】
【数２】
2006148937.tif 000004
は、ｍ番目の検査ノードに伝達される変数ノードメッセージをリオーダーリング(ｒｅｏｒｄｅｒｉｎｇ)して生成したものを示す。但し、ｎ番目の変数ノードからｍ番目の検査ノードに伝達される変数ノードメッセージが
【００２６】
【数３】
2006148937.tif 000005
であるとき、
【００２７】
【数４】
2006148937.tif 000006
を基準としてリオーダーリングを遂行する。ｍ番目の検査ノードからｎ番目の変数ノードに伝達されるメッセージ
【００２８】
【数５】
2006148937.tif 000007
は、
【００２９】
【数６】
2006148937.tif 000008
を除いた入力変数ノードメッセージの非線形関数からなる。
【００３０】
次に、変数ノードメッセージは下記の＜数７＞のようにアップデートされる。
【００３１】
【数７】
2006148937.tif 000009
【００３２】
上記の＜数７＞は、デグリーがｄｖであるｍ番目の変数ノードに対する計算式で、変数ノードメッセージは、ｍ番目の検査ノードからの入力である
【００３３】
【数８】
2006148937.tif 000010
を除いた入力検査ノードメッセージと最初のＬＬＲである
【００３４】
【数９】
2006148937.tif 000011
の和となる。
【００３５】
最後に、各反復復号時にＬＬＲは下記の＜数１０＞のようにアップデートされる。
【００３６】
【数１０】
2006148937.tif 000012
【００３７】
ここで、
【００３８】
【数１１】
2006148937.tif 000013
は、ｎ番目の変数ノードのｊ＋１番目の反復復号後のＬＬＲ値で、初期のＬＬＲ値
【００３９】
【数１２】
2006148937.tif 000014
と入力検査ノードメッセージとの和でアップデートされる。
【００４０】
上記の＜数７＞と＜数１０＞のように、変数ノード及びＬＬＲアップデートは簡単な加算演算で容易に実現可能であるが、検査ノードアップデートは非線形関数で示すため、ハードウェアの複雑度が上昇するという問題点があった。したがって、このハードウェアの複雑度を低下するための最適のアルゴリズムが要求される。
【００４１】
上記のように、検査ノード処理と変数ノード処理を分離して演算する方式は、多くのメモリの容量を使用するようになる。すなわち、メモリ３００は、各エッジ(ｅｄｇｅ)に関する情報を全て格納すべきであり、各検査ノード及び変数ノードでは必要な値をメモリから読み出して演算を遂行し、ＬＬＲ値を求める。このとき、変数ノード処理は、すべてのエッジに対して検査ノード処理を遂行した後に遂行される。その結果、検査ノード処理をすべて遂行する間に変数ノードプロセッサーは動作しなくなり、反対に変数ノード処理を遂行する間は検査ノードプロセッサーは動作しない。すなわち、一つのメモリから複数個のデータを読み出して処理すべきなため、メモリアクセスが遅延される問題が発生する。
【発明の開示】
【発明が解決しようとする課題】
【００４２】
したがって、上記のような従来技術の問題点を解決するために、本発明の目的は、ＬＤＰＣデコーダの実現において効率的な復号方式とそれに適合したデコーダの構造を提供することにある。
【００４３】
また、本発明の目的は、ＬＤＰＣデコーダの効率的なメモリ構造とそれによる効率的な復号方式を提供することにある。
【００４４】
本発明の他の目的は、ＬＤＰＣデコーダのメモリ分割を最小化し、検査ノード処理及び変数ノード処理を交互に遂行する方法及び装置を提供することにある。
【課題を解決するための手段】
【００４５】
上記の目的を達成するために、本発明は、パリティ検査ノード行列により複数の検査ノードと複数の変数ノードで構成される低密度パリティ検査符号を復号する装置であって、前記検査ノードの中で、検査ノード処理を遂行する少なくとも一つの検査ノードを選択する検査ノード選択スケジューラーと、前記変数ノードに対する入力ＬＬＲ(Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ)値を初期ＬＬＲ値として格納し、前記選択された検査ノードに接続された変数ノードに対してアップデートされたＬＬＲ値を格納するＬＬＲメモリと、前記選択された検査ノードに対して検査ノード処理が遂行された結果である検査ノードメッセージを格納する検査ノードメッセージメモリと、前記ＬＬＲメモリから読み出された該当ＬＬＲ値から、前記検査ノードメッセージメモリに格納されている前記選択された検査ノードの検査ノードメッセージを減算して変数ノードメッセージを生成し、前記変数ノードメッセージに対して検査ノード処理を遂行し、前記検査ノード処理結果値に前記変数ノードメッセージを加算してアップデートされたＬＬＲ値を計算し、前記計算されたＬＬＲ値を前記ＬＬＲメモリに伝達する少なくとも一つの統合ノードプロセッサーと、を含むことを特徴とする。
【００４６】
また、本発明は、パリティ検査ノード行列により複数の検査ノードと複数の変数ノードで構成される低密度パリティ検査符号を復号する方法であって、前記複数の検査ノードのうち検査ノード処理を遂行する少なくとも一つの検査ノードを選択する段階と、前記選択された検査ノードに対応する検査ノードメッセージを読み出し、前記検査ノードと接続された変数ノードのＬＬＲ値から前記検査ノードメッセージ値を減算して変数ノードメッセージを計算する段階と、前記計算された変数ノードメッセージに検査ノード処理を遂行して検査ノードメッセージを生成し、前記生成された検査ノードメッセージを格納する段階と、前記ＬＬＲ値に前記生成された検査ノードメッセージを加算してアップデートされたＬＬＲ値を計算し格納する段階と、前記アップデートされたＬＬＲ値に対して硬判定及びパリティ検査を遂行する段階と、を有することを特徴とする。
【発明の効果】
【００４７】
本発明は、ＬＤＰＣの非効率的なメモリの分割と復号方式を改善し、検査ノード処理と変数ノード処理を同時に遂行することによって、処理量を向上することができる効果がある。また、本発明は、単純なメモリの分割及びノードプロセッサーの単純化を通じてハードウェアの複雑度を低下することができる効果がある。
【発明を実施するための最良の形態】
【００４８】
以下、本発明の望ましい実施形態を添付の図面を参照して詳細に説明する。
【００４９】
図面の説明において、同一の構成要素に対してはできるだけ同一の参照番号及び参照符号を使用して説明する。本発明に関連した公知の構成及び機能に関する具体的な説明が本発明の要旨を不明にすると判断された場合に、その詳細な説明を省略する。
【００５０】
図４は、一般的な復号過程によるメモリ分割を示す図である。
【００５１】
図４を参照すると、パリティ検査行列のためのメモリと単位行列(ｉｄｅｎｔｉｔｙ  ｍａｔｒｉｘ)のためのメモリが各々備えられ、メモリは検査ノードプロセッサー及び変数ノードプロセッサーのノード数だけのサブメトリックブロックに分割される。すなわち、メモリの行は、検査ノードと平行に接続され、メモリの列の分割されたサブメトリックブロックは変数ノードと平行に接続される。図面において、小さな斜線ブロックは、受信信号‘１’を格納しているサブメトリックブロックを示す。
【００５２】
１段階で、受信情報は各メモリのサブブロックに入力される。
【００５３】
２段階で、検査ノード処理部４１０は、各列の分割されたサブメトリックブロックの値に対してそれぞれ検査ノード処理及びパリティ検査を遂行した後に、検査ノード処理の結果値を再びサブメトリックブロックに格納して検査ノードメッセージをアップデートする。
【００５４】
３段階で、変数ノード処理部４２０は、各行のサブメトリックブロックにアップデートされた値を読み出して変数ノードの演算を遂行し、硬判定(ｈａｒｄ-ｄｅｃｉｓｉｏｎ)復号及びＬＬＲ演算を遂行した後に結果値を再びサブメトリックブロックの値を格納することによって、変数ノードメッセージをアップデートする。メモリのサブメトリックブロックのサイズは、変数ノード及び検査ノードプロセッサーの個数により決定される。したがって、変数ノード及び検査ノードプロセッサーの個数が多いほど、メモリのサブメトリックブロックの分割の数が増加するため、ハードウェアの高い複雑度をもたらす。しかしながら、変数ノード及び検査ノードプロセッサーの数が減少してメモリの分割されたサブメトリックブロックの数が減少すると、メモリアクセスの速度が低下され、それによる処理量は低くなる。
【００５５】
図５は、一般的なＬＤＰＣ復号方式のフローチャートである。
【００５６】
図５を参照すると、検査ノード処理５８０と変数ノード処理５９０は順次に接続され、一つの演算過程が遂行してから次の演算過程が進行される。これら演算過程は、パリティー検査に成功するまで反復(ｉｔｅｒａｔｉｏｎ)される。
【００５７】
ステップＳ５００で、検査ノードプロセッサーは、受信情報を読み出してメモリに格納する。これをＬＤＰＣ復号の初期化と称する。
【００５８】
ステップＳ５１０で、検査ノードプロセッサーは、メモリのサブメトリックブロックに格納された情報ビットを読み出す。ステップＳ５２０で、検査ノードプロセッサーは、ステップＳ５２５で情報ビットのパリティを検査する間に、検査ノード処理を遂行する。このとき、パリティー検査の結果が良好であると、検査ノードプロセッサは復号を中断する。一方、ステップＳ５３０で、検査ノードプロセッサは、検査ノード処理の結果値をメモリに変数ノード値でアップデートして検査ノードメッセージを更新する。検査ノードメッセージの更新を遂行した後に、検査ノードプロセッサは、変数ノード処理領域５９０に進む。
【００５９】
ステップＳ５４０で、変数ノードプロセッサーは、メモリのサブメトリックブロックから検査ノードメッセージによってアップデートされた変数ノード値を読み出す。変数ノードプロセッサーは、ステップＳ５５０でアップデートされた変数ノード値を加算し、ステップＳ５６０でこの加算した結果値から該当行の変数ノード値を減算した後に、ステップＳ５６５で、ステップＳ５５０の結果値を硬判定する。ステップＳ５７０で、変数ノードプロセッサーは、ステップＳ５６０の結果値を変数ノード値としてメモリのサブメトリックブロックに格納した後にステップＳ５１０に戻る。
【００６０】
上記の一般的なＬＤＰＣ復号方式では、すべての情報ビットに対して検査ノード処理を遂行した後に、順次的に変数ノード処理が遂行される。すなわち、一度の反復復号が検査ノード処理と変数ノード処理の２段階からなるため、以前段階の変数或いは検査ノードのメッセージでそれぞれの検査或いは変数ノード処理が進行される。したがって、検査ノードメッセージと変数ノードメッセージを格納するためのメモリを共有可能になるが、反復による復号性能の収束速度(ｃｏｎｖｅｒｇｅｎｃｅ  ｓｐｅｅｄ)が遅いという短所がある。また、並列ノードプロセッサー構造の実現が可能であるが、実際のノード数だけのプロセッサーを実現する場合にハードウェアの複雑度が非常に大きくて実質的に実現される可能性が非常に少ない。
【００６１】
したがって、後述する本発明のより望ましい実施形態では、一度の復号過程で検査ノード処理と変数ノード処理を交互に反復して進行する方式を用いる。すなわち、一度の復号過程でアップデートされたメッセージで新たなメッセージが生成されるため、反復による復号性能の収束速度が速いという長所がある。また、検査ノードと変数ノードを交互に一つのノードずつ順次的に復号が進行可能で、数個ずつ部分的に並列に進行可能である。また、一回の反復復号中のアップデートされたメッセージを用いることによって収束速度が増加するようになる。加えて、この場合に常に変数ノードと検査ノードのメッセージをすべて格納することによって発生するメモリの増加は、復号方式により検査ノードの数だけ分割し、或いは検査ノードプロセッサーの数だけ分割することで最小化できる。
【００６２】
以下、本発明の望ましい実施形態による検査ノード処理と変数ノード処理を進行する方法について詳細に説明する。
【００６３】
ＬＤＰＣデコーダのメモリには、検査ノードメッセージ及び各変数ノードに該当するＬＬＲ値が格納され、復号しようとする検査ノードの選択でデコーダの動作が始まる。変数ノード及び検査ノード処理とＬＬＲアップデートが一つの統合されたノード処理で処理される。
【００６４】
第１に、下記の＜数１３＞のように、入力ＬＬＲ値の瞬時ＬＬＲ値を各変数ノードに対して格納し、検査ノードメッセージを‘０’にセッティングする。
【００６５】
【数１３】
2006148937.tif 000015
【００６６】
第２に、検査ノードｃｍが選択される。検査ノードを選択する方法及び手順は、多様に実現されることができる。検査ノードを一つ或いは数個のグループにインデキシング(ｉｎｄｅｘｉｎｇ)し、このインデキシング順に選択し、一定規則に従って均一(ｕｎｉｆｏｒｍ)に選択できる。また、復号サイクルの特性を考慮して、検査ノードごとに選択比率を異にして選択することもできる。ここで、一つの検査ノードが選択された場合の動作を説明する。
【００６７】
第３に、ｃｍに関連したすべての変数ノードメッセージを生成する。このｃｍに接続されたエッジの検査ノードメッセージを該当変数ノードの瞬時ＬＬＲ値から減算することで、下記の＜数１４＞のように変数ノードメッセージを生成する。
【００６８】
【数１４】
2006148937.tif 000016
【００６９】
ここで、ｎはｃｍに接続された変数ノードのインデックスで、ｎ０〜
【００７０】
【数１５】
2006148937.tif 000017
の範囲を有する。
【００７１】
【数１６】
2006148937.tif 000018
は選択されたｃｍに対するノード処理が始まる前段階のｎ番目の変数ノードの瞬時ＬＬＲ値である。
【００７２】
第４に、生成された変数ノードメッセージを用いて下記の＜数１７＞のように検査ノード処理を遂行する。
【００７３】
【数１７】
2006148937.tif 000019
【００７４】
ここで、Ｆは検査ノード処理関数で、
【数１８】
2006148937.tif 000020
を除いた入力変数からなる非線形関数で、多様な方法で実現可能である。＜数１＞がその代表的な例に該当する。
【００７５】
第５に、＜数１７＞を通じて得られた検査ノードメッセージを該当検査ノード値としてメモリに格納した後、第４の過程が進行される間に臨時に格納されている第３の過程の変数ノードメッセージから新たな検査ノードメッセージを用いて、下記の＜数１９＞のようにＬＬＲ値をアップデートする。
【００７６】
【数１９】
2006148937.tif 000021
【００７７】
第６に、すべての検査ノードが一度ずつ選択され、一度の反復復号が終了すると、アップデートされたＬＬＲ値を用いてパリティ検査を遂行する、パリティ検査結果が良いと、復号を中断し、それとも第２の過程に戻る。パッティーは、検査ノードプロセッサーのアップデートごとにパリティ検査ノードを確認することができる。
【００７８】
上記したように、デコーダのメモリは、該当検査ノードの検査ノーメッセージと瞬時ＬＬＲ値だけを格納しておき、検査ノードメッセージとを瞬時ＬＬＲ値を用いて該当検査ノードの変数ノード処理及び検査ノード処理を一度に遂行する統合ノードプロセッサーを使用する。この統合されたノードプロセッサーを使用することによって、計算量が増加することなく、迅速に収束される復号を遂行するようになる。すなわち、一つの検査ノードに対する統合ノード処理が遂行される度に周辺検査ノードのＬＬＲＤ値が更新されることによって、次の検査ノードの検査ノード処理に影響を及ぼすようになる。
【００７９】
図６Ａは、本発明の望ましい実施形態によるメモリ構造を示す図である。
【００８０】
図６Ａを参照すると、メモリ６００は、検査ノードの数Ｄだけのブロックに分割され、この分割されたブロックの各々は該当検査ノードに対する検査ノードメッセージを格納する。復号の際には、各検査ノードに該当する検査ノードメッセージが順次に読み出され、ブロック内の格納されている検査ノードメッセージを“１ワード(ｗｏｒｄ)”と称する。
【００８１】
図６Ｂは、本発明の他の実施形態によるメモリ構造を示す図である。
【００８２】
図６Ｂを参照すると、メモリ構造は、ブロックタイプのＬＤＰＣ符号に適用可能な並列デコーダ構造に適当である。メモリ６１０は、検査ノードの数Ｄだけのブロックに分割される。この分割された一つのブロックは、Ｐ個の検査ノードメッセージが１ワードで格納され、Ｐ個の検査ノードメッセージが同時に読み出されて使用されることによって、並列デコーダの構造が可能になる。並列デコーダの構造は、後述する図１０を参照して詳細に説明する。
【００８３】
図７は、本発明の望ましい実施形態によるＬＤＰＣデコーダの構造を示す図である。
【００８４】
図７を参照すると、ＬＤＰＣデコーダは、検査ノード選択スケジューラー７００と、検査ノード処理及びＬＬＲアップデートを遂行する統合ノードプロセッサー７１０と、検査ノードプロセッサー７１４の検査ノードの数だけに分割されたＬＬＲメモリ７２０及び検査ノードメッセージメモリ７４０と、硬判定部７３０とから構成される。
【００８５】
サイクルごとに検査ノード選択スケジューラー７００は、所定の規則に従って検査ノードプロセッサー７１４の検査ノードのうち検査ノード処理を遂行する検査ノードを選択する。
【００８６】
ＬＬＲメモリ７２０は、入力ＬＬＲ値を初期値として格納し、検査ノードメッセージメモリ７４０は検査ノードメッセージの初期値を‘０’に初期化し、以後、該当検査ノードの検査ノード処理が遂行された結果値を格納する。すなわち、検査ノードメッセージメモリ７４０は、検査ノード処理が遂行された結果である検査ノードメッセージを検査ノード別に分割されたそれぞれのサブメトリックブロックに格納する。
【００８７】
統合ノードプロセッサー７１０は、加算器/減算器７１２と、検査ノードプロセッサー７１４と、フリップフロップ７１６と、加算器７１８とから構成され、変数ノードメッセージと検査ノードメッセージ及びＬＬＲ値を一度にアップデートする。
【００８８】
検査ノード選択スケジューラー７００によって検査ノードが選択されると、加算器/減算器７１２は、ＬＬＲメモリ７２０から読み出した該当ＬＬＲ値から検査ノードメッセージに格納されている選択された検査ノードに対応する検査ノードメッセージを減算して変数ノードメッセージを生成する。この変数ノードメッセージは、フリップフロップ７１６に格納されると同時に、検査ノードプロセッサー７１４に入力される。ここで、該当ＬＬＲ値は、選択された検査ノードに接続された変数ノードのＬＬＲ値である。
【００８９】
検査ノードプロセッサー７１４は、入力された変数ノードメッセージに対して上記の＜数１７＞を用いて検査ノード処理を遂行する。検査ノード処理結果値は、ＬＬＲメモリ７２０に格納されると同時に、加算器７１８に入力される。加算器７１８は、＜数１９＞のように、検査ノード処理結果値にフリップフロップ７１６に格納された変数ノードメッセージを加算してアップデートされたＬＬＲ値を計算する。アップデートされたＬＬＲ値は、ＬＬＲメモリ７２０に格納され、かつ、硬判定部７３０に入力される。
【００９０】
硬判定部７３０は、アップデートされたＬＬＲ値に硬判定を遂行して０と１を判断する。ビットバッファ７３４は、硬判定部７３０で硬判定された値を格納し、パリティー検査ブロック７３２は、この硬判定値のパリティ検査を遂行する。パリティー検査ブロック７３２の検査結果が良いと、ＬＤＰＣデコーダは、反復復号を終了し、ビットバッファ７３４の硬判定値を復号結果値として出力する。パリティ検査結果が悪いと、検査ノード選択スケジューラー７００は、次の検査ノードを選択する。パリティ検査は、多様な条件を設定することができる。例えば、パリティ検査は、すべての検査ノードが一度ずつ選択されるときに遂行可能である。
【００９１】
図７のように、本発明の望ましい実施形態によるＬＤＰＣデコーダは、検査ノード処理後に変数メッセージを生成する時点で、ＬＬＲメモリ７２０に格納されている以前段階のＬＬＲ値を有し、変数ノード処理を遂行する。すなわち、検査ノード処理の出力が、すぐ変数ノードメッセージのアップデートに用いられ、収束速度を一層増加させ、反復回数を減少させるという利点がある。また、同一の反復回数に対して、収束速度が増加して処理量及び性能が向上する。
【００９２】
以下、図４及び図８を比べて本発明による復号方式について説明する。
【００９３】
図８は、本発明の望ましい実施形態による復号方式に適用されるメモリ構造の概念図である。ここで、メモリ８００の構造は、図７の検査ノードメッセージメモリ７４０と、ＬＬＲメモリ７２０に適用可能である。
【００９４】
一度の反復を遂行すうために、図４では、２段階と３段階を順次に遂行すべく、図８では、すべての検査ノードを一度ずつ選択するだけでも一度の反復が遂行可能である。
【００９５】
具体的に図８を参照すると、メモリ８００の行は、検査ノードプロセッサーの数だけサブメトリックブロックに分割され、小さな斜線ブロックは受信情報の１の値を格納する。
【００９６】
すなわち、メモリ８００でそれぞれのサブメトリックブロックは、該当する検査ノードに対応する検査ノードメッセージが更新された値を格納する。また、メモリ８００は、特定検査ノードに接続された変数ノードに対応するＬＬＲ値が更新された値を格納する。
【００９７】
図９は、本発明の望ましい実施形態による復号方式のフローチャートである。
【００９８】
図７を参照して図９を説明すると、ステップＳ９０２で、ＬＬＲ値は、ＬＬＲメモリ７２０のサブメトリックブロックに各々該当する値が入力される。ステップＳ９０４で、検査ノード選択スケジューラー７００は、検査ノードを選択する。このとき、選択される検査ノードの数は一つ或いはそれ以上になり、選択方法も順次に或いは均一に選択されることができる。
【００９９】
ステップＳ９０６で、統合ノードプロセッサー７１０は、検査ノードメッセージメモリ７４０から選択された検査ノードに該当する以前検査ノードメッセージを読み出す。
【０１００】
ステップＳ９０８で、統合ノードプロセッサー７１０は、選択された検査ノードに接続された変数ノードに対するＬＬＲ値から以前検査ノードメッセージ値を減算し、変数ノードメッセージをアップデートする。ステップＳ９１０で、統合ノードプロセッサー７１０は、アップデートされた変数ノードメッセージに検査ノード処理を遂行して検査ノードメッセージを生成する。ステップＳ９２１で、統合ノードプロセッサー７１０は、生成された検査ノードメッセージを検査ノードメッセージメモリ７４０に格納される。
【０１０１】
ステップＳ９１４で、統合ノードプロセッサー７１０は、ＬＬＲ値に生成された検査ノードメッセージを加算してＬＬＲ値をアップデートし、ステップＳ９１６で、このアップデートされたＬＬＲ値はＬＬＲメモリ７２０に格納される。同時に、ステップＳ９１８で、アップデートされたＬＬＲ値に対して硬判定及びパリティ検査が遂行される。パリティ検査結果が良いと、ステップ９２０に進んで、復号が中断され、硬判定された値が出力される。硬判定及びパリティ検査結果が悪いと、ステップＳ９０４に戻って継続して反復復号を遂行する。
【０１０２】
以下、本発明の他の実施形態では、複数の統合ノードプロセッサーを平行に備えるＬＤＰＣデコーダについて説明する。
【０１０３】
図１０は、本発明の他の実施形態による並列ＬＤＰＣデコーダの構造を示す図である。
【０１０４】
図１０を参照すると、ＬＤＰＣデコーダは、検査ノード選択スケジューラー１００２と、検査ノード処理及びＬＬＲアップデートを遂行する統合ノードプロセッサー部１０１０と、検査ノードの数だけ分割されるＬＬＲメモリ１０２０及び検査ノードメッセージメモリ１０３０と、硬判定部１０４０とから構成される。
【０１０５】
検査ノード選択スケジューラー１００２は、検査ノードプロセッサーの検査ノードのうち検査ノード処理を遂行する検査ノードを一個或いは数個を順序に或いは異にして選択できる。このとき、複数の検査ノードが選択される場合に、一度に同じＬＬＲをアクセスし、或いはメモリアクセス時に衝突が発生しないようにスケジューリングする。ブロックタイプの構造的ＬＤＰＣ符号の場合に、このような並列的な構造を実現するのに容易で、図６Ｂのメモリ構造及び並列統合ノードプロセッサーで実現が可能である。
【０１０６】
統合ノードプロセッサー部１０１０と、検査ノードの数だけ分割されたＬＬＲメモリ１０２０及び検査ノードメッセージメモリ１０３０と、硬判定部１０４０は、図７の構成と同一に動作するため、その詳細な説明を省略する。
【０１０７】
ここで、太線は、平行に動作する複数の統合ノードプロセッサーに対する並列入出力を示す。その一例として、ＬＤＰＣ符号のパリティ検査行列がＰ＊Ｐでブロック化された構造であれば、一つのブロックに属するすべての検査ノードメッセージ１ワードに設定して読み出すことができる。読み出されたメッセージが処理されるときは、パリティ検査行列による検査ノードメッセージに順列(ｐｅｒｍｕｔａｔｉｏｎ)をつけるべきである。
【０１０８】
パリティ検査行列がランダムに生成されている場合に、パリティ検査行列は、検査ノードメッセージメモリ１０３０及びＬＬＲメモリ１０２０をアクセスする間に衝突が発生しないように設計すべきである。このとき、スケジューリング検査ノード選択において、統合ノードプロセッサー部１０１０の各統合ノードプロセッサーが同じメモリを同時にアクセスしない方法、或いは統合ノードプロセッサー間に適切な遅延(ｄｅｌａｙ)を提供する方法が利用可能である。
【０１０９】
以上、本発明の詳細な説明においては具体的な実施形態に関して説明したが、本発明の範囲を外れない限り、様々な変形が可能であることは、当該技術分野における通常の知識を持つ者には自明なことであろう。したがって、本発明の範囲は、前述の実施形態に限定されるものではなく、特許請求の範囲の記載及びこれと均等なものに基づいて定められるべきである。
【図面の簡単な説明】
【０１１０】
【図１】一般的なＬＤＰＣ復号の構造を示す図である。
【図２】一般的なファクターグラフ及びパリティ検査行列を示す図である。
【図３】一般的なＬＤＰＣ符号の全体ブロックを示す構成図である。
【図４】従来のメモリ分割による復号過程を示す図である。
【図５】従来技術による復号方式のフローチャートである。
【図６Ａ】本発明の望ましい実施形態によるメモリ構造を示す図である。
【図６Ｂ】本発明の他の実施形態によるメモリ構造を示す図である。
【図７】本発明の望ましい実施形態によるＬＤＰＣデコーダの構造を示す図である。
【図８】本発明の望ましい実施形態による復号方式のメモリ構造を示す概念図である。
【図９】本発明の望ましい実施形態による復号方式のフローチャートである。
【図１０】本発明の他の実施形態による並列ＬＤＰＣデコーダの構造を示す図である。
【符号の説明】
【０１１１】
７００  検査ノード選択スケジューラー
７１０  統合ノードプロセッサー
７１２  加算器/減算器
７１４  検査ノードプロセッサー
７１６  フリップフロップ
７１８  加算器
７２０  ＬＬＲメモリ
７３０  硬判定部
７３２  パリティー検査ブロック
７３４  ビットバッファ
７４０  検査ノードメッセージメモリ
【図１】
2006148937.tif 000040
【図２】
2006148937.tif 000041
【図３】
2006148937.tif 000042
【図４】
2006148937.tif 000043
【図５】
2006148937.tif 000044
【図６Ａ】
2006148937.tif 000045
【図６Ｂ】
2006148937.tif 000046
【図７】
2006148937.tif 000047
【図８】
2006148937.tif 000048
【図９】
2006148937.tif 000049
【図１０】
2006148937.tif 000050