(57)【要約】【課題】  低密度パリティ検査符号の復号処理には、チェック−変数メッセージと、変数−チェックメッセージとの保存に多くのＲＡＭを必要とする。また、ＲＡＭの個数の削減には、同時アクセス可能なメッセージの制限が伴うため、メッセージ更新のスケジュール、アドレス生成を細かく調整する必要があり、装置構成が複雑になる。【解決手段】  検査行列中の１の配置に対応したレジスタ３１間に、加算器４１を含む変数−チェック演算器ブロック３２が設置された変数−チェックメッセージ生成部１１と、検査行列中の１の配置に対応したレジスタ６１間に、比較器を含むチェック−変数演算ブロック６２が設置されたチェック−変数メッセージ生成部１２とを有する構成にすると、ＲＡＭを使用せず、複雑な制御を必要としない、構成が簡単で高速処理が可能な低密度パリティ検査符号の復号装置を提供することができる。【選択図】  図１
2007089064.tif 000002
【特許請求の範囲】
【請求項１】
誤り訂正符号化方式における疑似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置において、
複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、受信データ列を入力し、対数尤度比と事前値との和を含むデータである変数−チェックメッセージと、推定送信ビット列とを生成して出力する変数−チェックメッセージ生成手段と、
複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、前記変数−チェックメッセージ生成手段が出力した変数−チェックメッセージが入力されると、入力された前記変数−チェックメッセージに応じて生成したデータを含むチェック−変数メッセージを出力するチェック−変数メッセージ生成手段と、
前記チェック−変数メッセージ生成手段が出力したチェック−変数メッセージが含む所定のデータに、予め決められた定数を乗じて前記変数−チェックメッセージ生成手段に入力する正規化演算手段とを備え、
前記変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうち、所定のデータに、前記チェック−変数メッセージ生成手段の出力に対応するデータを加算して次の段のレジスタに保存し、所定のタイミングで、前記レジスタが保存しているデータである変数−チェックメッセージおよび推定送信ビット列を出力する変数−チェック演算手段を含み、
前記チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうちの２つと、前記変数−チェックメッセージ生成手段が出力したデータとのうち、値が最も小さいデータと、２番目に小さいデータとを選択して次の段のレジスタに保存し、所定のタイミングで、前記レジスタが保存しているデータをチェック−変数メッセージとして出力するチェック−変数演算手段を含み、
前記変数−チェック演算手段は、前記変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置され、
前記チェック−変数演算手段は、前記チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置される
ことを特徴とする復号装置。
【請求項２】
変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第１のクロックカウンタを含み、
チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第２のクロックカウンタを含み、
変数−チェック演算手段は、前記変数−チェックメッセージ生成手段が含むレジスタに保存されたデータの一部に加算するデータを、前記第１のクロックカウンタの値に応じて選択し、
チェック−変数メッセージ生成手段のレジスタは、前記第２のクロックカウンタがカウントした値を記憶し、
チェック−変数演算手段は、前記変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、前記レジスタが記憶している前記第２のクロックカウンタがカウントした値に対応する数値を出力して、次の段のレジスタに保存する
請求項１記載の復号装置。
【請求項３】
変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第１のクロックカウンタを含み、
チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第２のクロックカウンタを含み、
変数−チェック演算手段は、前記変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータの一部に加算するデータを前記第１のクロックカウンタの値と、前記変数−チェックメッセージ生成手段のレジスタに割り当てられた数値とに応じて選択し、
チェック−変数メッセージ生成手段のレジスタは、前記第２のクロックカウンタがカウントした値を記憶し、
チェック−変数演算手段は、前記変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、前記レジスタが記憶している前記第２のクロックカウンタがカウントした値と、前記変数−チェックメッセージ生成手段のレジスタに割り当てられた数値との組を出力して、次の段の前記レジスタに保存する
請求項１記載の復号装置。
【請求項４】
変数−チェックメッセージ生成手段、およびチェック−変数メッセージ生成手段は、変数−チェックメッセージの生成および出力と、チェック−変数メッセージの生成および出力とをそれぞれ所定の回数繰り返し、
前記変数−チェックメッセージ生成手段は、前記所定の回数変数−チェックメッセージの生成を繰り返してから、推定送信ビット列を出力する
請求項１から請求項３のうちいずれか１項記載の復号装置。
【請求項５】
変数−チェックメッセージ生成手段は、疑似巡回型低密度パリティ検査符号の検査行列を構成する巡回行列のサイズと同数のレジスタと変数−チェック演算手段とをそれぞれ含み、
チェック−変数メッセージ生成手段は、疑似巡回型低密度パリティ検査符号の検査行列を構成する巡回行列のサイズと同数のレジスタとチェック−変数演算手段とそれぞれを含む
請求項１から請求項４のうちいずれか１項記載の復号装置。
【請求項６】
誤り訂正符号化方式における疑似巡回型低密度パリティ検査符号を復号し、推定送信ビット列を出力する復号装置を備えた受信装置において、
受信した情報を復調して出力する復調器と、
前記復調器の出力データを前記復号装置に応じた形式の入力データに変換し、フレーム同期をとって前記復号装置に出力する同期制御−データ変換装置とを備え、
前記復号装置は、
複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、受信データ列を入力し、対数尤度比と事前値との和を含むデータである変数−チェックメッセージと、推定送信ビット列とを生成して出力する変数−チェックメッセージ生成手段と、
複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、前記変数−チェックメッセージ生成手段が出力した変数−チェックメッセージが入力されると、入力された前記変数−チェックメッセージに応じて生成したデータを含むチェック−変数メッセージを出力するチェック−変数メッセージ生成手段と、
前記チェック−変数メッセージ生成手段が出力したチェック−変数メッセージが含む所定のデータに、予め決められた定数を乗じて前記変数−チェックメッセージ生成手段に入力する正規化演算手段とを含み、
前記変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうち、所定のデータに、前記チェック−変数メッセージ生成手段の出力に対応するデータを加算して次の段のレジスタに保存し、所定のタイミングで、前記レジスタが保存しているデータである変数−チェックメッセージおよび推定送信ビット列を出力する変数−チェック演算手段を含み、
前記チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうちの２つと、前記変数−チェックメッセージ生成手段が出力したデータとのうち、値が最も小さいデータと、２番目に小さいデータとを選択して次の段のレジスタに保存し、所定のタイミングで、前記レジスタが保存しているデータをチェック−変数メッセージとして出力するチェック−変数演算手段を含み、
前記変数−チェック演算手段は、前記変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置され、
前記チェック−変数演算手段は、前記チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置される
ことを特徴とする受信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、受信データ系列を一定長のブロックに分割し、各ブロック毎独立に冗長系列を付加するブロック誤り訂正の復号装置および復号装置を含む受信装置であって、特に低密度パリティ検査（ＬＤＰＣ）符号の復号装置および復号装置を含む受信装置に関する。
【背景技術】
【０００２】
衛星通信システムや移動体通信システム等では、所要電力の低減やアンテナの小型化などのシステム構成上の要件を満たすため、大きな符号化利得を有する誤り訂正符号化技術の導入が行われている。低密度パリティ検査符号は、非常に大きな符号化利得を有する誤り訂正符号として知られており、各種の通信システムや、磁気記録などの記憶装置への導入が進んでいる。
【０００３】
低密度パリティ検査符号は、単に一つの誤り訂正符号化方式を示すのではなく、検査行列が疎である（行列中の成分のほとんどが０であり、１である成分の数が非常に少ない）という特徴をもった誤り訂正符号の総称である。
【０００４】
そして、疎な検査行列の選択によって、サム・プロダクト（ｓｕｍ−ｐｒｏｄｕｃｔ）アルゴリズムや、ミン・サム（ｍｉｎ−ｓｕｍ）アルゴリズムなどの繰り返し復号方式を用いることにより、理論限界に近い非常に大きな符号化利得を持つ誤り訂正符号化方式を構成することが可能であるという特徴をもっている（例えば、非特許文献１、および非特許文献２参照。）。
【０００５】
低密度パリティ検査符号の復号装置は、変数ノード処理装置による変数−チェックメッセージの更新と、チェックノード処理装置によるチェック−変数メッセージの更新とを交互に行い、一定回数各メッセージを更新した後、チェック−変数メッセージと受信データとから送信データの推定結果を得る（例えば、非特許文献２および非特許文献３参照。）。
【０００６】
【非特許文献１】ロバート・ギャラガ（Ｒｏｂｅｒｔ  Ｇ．  Ｇａｌｌａｇｅｒ）著、「ロー・デンシティ  パリティ・チェック  コーズ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ）」、（米国）、エムアイティー・プレス（ＭＩＴ  Ｐｒｅｓｓ）、１９６３年、ｐ．３９−５６
【非特許文献２】デビッド・マッカイ（Ｄａｖｉｄ  Ｊ．  Ｃ．  ＭａｃＫａｙ）著、「グット  エラー・コレクティング  コーズ  ベースト  オン  ベリー  スパース  メトリシィーズ（Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  Ｖｅｒｙ  Ｓｐａｒｓｅ  Ｍａｔｒｉｃｅｓ）、（米国）、アイトリプルイー  トランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ）、Ｖｏｌ．４５、Ｎｏ２、１９９９年３月、ｐ３９９−４３１
【非特許文献３】ジング・チェン（Ｊｉｎｇｈｕ  Ｃｈｅｎ）、マーク・フォッソリア（Ｍａｒｃ  Ｐ．  Ｃ．  Ｆｏｓｓｏｒｉｅｒ）著、「ニア  オプティマム  ユニヴァーサルビリーフ  プロパゲーション  ベースト  デコーディング  オブ  ローデンシティ  パリティチェック  コーズ（Ｎｅａｒ  Ｏｐｔｉｍｕｎ  Ｕｎｉｖｅｒｓａｌ  Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ  Ｂａｓｅｄ  Ｄｅｃｏｄｉｎｇ  ｏｆ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ  Ｃｏｄｅｓ）」、（米国）、アイトリプルイー  トランザクションズ  オン  コミュニケーションズ（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ）、Ｖｏｌ．５０、Ｎｏ．３、２００２年３月、ｐ．４０６−４１４
【発明の開示】
【発明が解決しようとする課題】
【０００７】
低密度パリティ検査符号の復号方式の技術的な問題点として、復号処理の過程で生じるデータの記憶用に多くのランダムアクセスメモリ（ＲＡＭ）を必要とする点や、ＲＡＭのアクセス速度によって復号処理全体の速度が制限される点などがある。
【０００８】
具体的には、低密度パリティ検査符号の復号処理は、２種類の処理装置によるメッセージの更新からなり、メッセージを一時的に蓄えておく記憶装置は必要不可欠である。そして、検査行列中の１の数に比例した個数のメッセージがあり、これを記憶装置としてのＲＡＭが保持した場合、多くのＲＡＭが必要になり、復号処理のスループットがＲＡＭへのアクセス速度で制限されるという問題がある。
【０００９】
また、ＲＡＭの個数を削減するためには同時アクセス可能なメッセージの制限を伴うため、メッセージ更新のスケジュールや、アドレス生成を細かく調整する必要があり、装置構成が複雑となるという問題がある。
【００１０】
そこで、本発明は、低密度パリティ検査符号の復号処理を高速に行い、構成が単純で小規模な復号装置および復号装置を含む受信装置を提供することを目的とする。
【課題を解決するための手段】
【００１１】
本発明による復号装置は、誤り訂正符号化方式における疑似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置であって、複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、受信データ列を入力し、対数尤度比と事前値との和を含むデータである変数−チェックメッセージと、推定送信ビット列とを生成して出力する変数−チェックメッセージ生成手段と、複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、変数−チェックメッセージ生成手段が出力した変数−チェックメッセージが入力されると、入力された変数−チェックメッセージに応じて生成したデータを含むチェック−変数メッセージを出力するチェック−変数メッセージ生成手段と、チェック−変数メッセージ生成手段が出力したチェック−変数メッセージが含む所定のデータに、予め決められた定数を乗じて変数−チェックメッセージ生成手段に入力する正規化演算手段とを備え、変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうち、所定のデータに、チェック−変数メッセージ生成手段の出力に対応するデータを加算して次の段のレジスタに保存し、所定のタイミングで、レジスタが保存しているデータである変数−チェックメッセージおよび推定送信ビット列を出力する変数−チェック演算手段を含み、チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうちの２つと、変数−チェックメッセージ生成手段が出力したデータとのうち、値が最も小さいデータと、２番目に小さいデータとを選択して次の段のレジスタに保存し、所定のタイミングで、レジスタが保存しているデータをチェック−変数メッセージとして出力するチェック−変数演算手段を含み、変数−チェック演算手段は、変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置され、チェック−変数演算手段は、チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置されることを特徴とする。
【００１２】
変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第１のクロックカウンタを含み、チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第２のクロックカウンタを含み、変数−チェック演算手段は、変数−チェックメッセージ生成手段が含むレジスタに保存されたデータの一部に加算するデータを、第１のクロックカウンタの値に応じて選択し、チェック−変数メッセージ生成手段のレジスタは、第２のクロックカウンタがカウントした値を記憶し、チェック−変数演算手段は、変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、レジスタが記憶している第２のクロックカウンタがカウントした値に対応する数値を出力して、次の段のレジスタに保存してもよい。
【００１３】
変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第１のクロックカウンタを含み、チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタの動作クロックに同期した第２のクロックカウンタを含み、変数−チェック演算手段は、変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータの一部に加算するデータを第１のクロックカウンタの値と、変数−チェックメッセージ生成手段のレジスタに割り当てられた数値とに応じて選択し、チェック−変数メッセージ生成手段のレジスタは、第２のクロックカウンタがカウントした値を記憶し、チェック−変数演算手段は、変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、レジスタが記憶している第２のクロックカウンタがカウントした値と、変数−チェックメッセージ生成手段のレジスタに割り当てられた数値との組を出力して、次の段のレジスタに保存してもよい。
【００１４】
変数−チェックメッセージ生成手段、およびチェック−変数メッセージ生成手段は、変数−チェックメッセージの生成および出力と、チェック−変数メッセージの生成および出力とをそれぞれ所定の回数繰り返し、変数−チェックメッセージ生成手段は、所定の回数変数−チェックメッセージの生成を繰り返してから、推定送信ビット列を出力してもよい。
【００１５】
変数−チェックメッセージ生成手段は、疑似巡回型低密度パリティ検査符号の検査行列を構成する巡回行列のサイズと同数のレジスタと変数−チェック演算手段とをそれぞれ含み、チェック−変数メッセージ生成手段は、疑似巡回型低密度パリティ検査符号の検査行列を構成する巡回行列のサイズと同数のレジスタとチェック−変数演算手段とそれぞれを含んでもよい。
【００１６】
本発明による受信装置は、誤り訂正符号化方式における疑似巡回型低密度パリティ検査符号を復号し、推定送信ビット列を出力する復号装置を備えた受信装置であって、受信した情報を復調して出力する復調器と、復調器の出力データを復号装置に応じた形式の入力データに変換し、フレーム同期をとって復号装置に出力する同期制御−データ変換装置とを備え、復号装置は、複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、受信データ列を入力し、対数尤度比と事前値との和を含むデータである変数−チェックメッセージと、推定送信ビット列とを生成して出力する変数−チェックメッセージ生成手段と、複数のレジスタを有する所定の段数のフィードバックシフトレジスタを複数個含み、変数−チェックメッセージ生成手段が出力した変数−チェックメッセージが入力されると、入力された変数−チェックメッセージに応じて生成したデータを含むチェック−変数メッセージを出力するチェック−変数メッセージ生成手段と、チェック−変数メッセージ生成手段が出力したチェック−変数メッセージが含む所定のデータに、予め決められた定数を乗じて変数−チェックメッセージ生成手段に入力する正規化演算手段とを含み、変数−チェックメッセージ生成手段は、当該変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうち、所定のデータに、チェック−変数メッセージ生成手段の出力に対応するデータを加算して次の段のレジスタに保存し、所定のタイミングで、レジスタが保存しているデータである変数−チェックメッセージおよび推定送信ビット列を出力する変数−チェック演算手段を含み、チェック−変数メッセージ生成手段は、当該チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタに保存されたデータのうちの２つと、変数−チェックメッセージ生成手段が出力したデータとのうち、値が最も小さいデータと、２番目に小さいデータとを選択して次の段のレジスタに保存し、所定のタイミングで、レジスタが保存しているデータをチェック−変数メッセージとして出力するチェック−変数演算手段を含み、変数−チェック演算手段は、変数−チェックメッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置され、チェック−変数演算手段は、チェック−変数メッセージ生成手段が含むフィードバックシフトレジスタが有するレジスタ間にそれぞれ設置されることを特徴とする。
【発明の効果】
【００１７】
本発明によれば、ＲＡＭを使用しないため、高速で低密度パリティ検査符号の復号処理を行うことができる。
【００１８】
また、チェック−変数演算手段が、変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、レジスタが記憶している第２のクロックカウンタがカウントした値に対応する数値を出力するように構成されている場合には、復号装置全体の装置規模を縮小することができる。
【００１９】
また、チェック−変数演算手段が、変数−チェックメッセージ生成手段の出力に対応するデータが最も小さい値となった時に、レジスタが記憶している第２のクロックカウンタがカウントした値と、変数−チェックメッセージ生成手段のレジスタに割り当てられた数値との組を出力するのように構成されている場合には、高精度なチェック−変数メッセージを生成することができる。
【発明を実施するための最良の形態】
【００２０】
実施の形態１．
本発明の復号装置の第１の実施の形態について、図面を参照して説明する。図１は、本発明による復号装置の第１の実施の形態の一構成例を示すブロック図である。
【００２１】
本発明による復号装置は、変数−チェックメッセージ生成部（変数−チェックメッセージ生成手段）１１、チェック−変数メッセージ生成部（チェック−変数メッセージ生成手段）１２、および正規化演算部（正規化演算手段）１３を含む。
【００２２】
変数−チェックメッセージ生成部１１には、復号装置が接続されている通信回線から、受信データ系列が入力される。一般に、受信データには雑音などによる誤りが生じているため、復号装置は、送信ビット列を推定し、推定した送信ビット列である推定送信ビット列を出力する。
【００２３】
擬似巡回型低密度パリティ検査符号は検査行列の形によって特徴づけられる。擬似巡回型低密度パリティ検査符号の検査行列は、（式１）に示すようにａ×ａ巡回行列を成分とするｍ×ｎブロック行列となる（ａ，ｍ，ｎは正の整数を表している）。
【００２４】
【数１】
2007089064.tif 000003
【００２５】
ここで（式１）のＨｉ，ｊは次の（式２）に記したａ×ａ巡回行列を表している。（ｉは０からｍ−１の間の整数を表し、ｊは０からｎ−１の間の整数を表している）。
【００２６】
【数２】
2007089064.tif 000004
【００２７】
巡回行列は、（式２）に示したように、第２行目の行ベクトルが第１行目の行ベクトルを１ビット左に巡回したものである。以下、第ｋ行目の列ベクトルは（ｋは２からｎの間の整数を表している）、第１行目の行ベクトルをｋ−１ビット左に巡回したものである。
【００２８】
以下、検査行列が（式１）の行列となる擬似巡回型の低密度パリティ検査符号の復号装置について説明する。
【００２９】
変数−チェックメッセージ生成部１１には、通信回線から入力される受信データ系列、および正規化演算部１３を介してチェック−変数メッセージ生成部１２の出力が入力される。チェック−変数メッセージ生成部１２の出力は、検査行列の行ブロック数ｍと同数の種類に分類されたデータ系列からなる。なお、チェック−変数メッセージ生成部１２の出力については後述する。
【００３０】
図２は、変数−チェックメッセージ生成部１１の一構成例を示すブロック図である。変数−チェックメッセージ生成部１１は、検査行列の列ブロックの総数ｎと同数の変数−チェックレジスタブロック２１と、加算器２３と、変数−チェックレジスタブロック２１が含むレジスタ３１のクロックに同期したカウンタであるカウンタブロック（第１のクロックカウンタ）２２を含む。
【００３１】
各変数−チェックレジスタブロック２１へは、正規化演算部１３を介して、後述するチェック−変数メッセージ生成部１２の出力が入力される。そして、各変数−チェックレジスタブロック２１の出力は、その変数−チェックレジスタブロック２１に対応する検査行列の列ブロックに相当する、各受信データ列の一部分に加算器２３で加算され、その加算結果が変数−チェックメッセージ生成部１１の出力になる。変数−チェックレジスタブロック２１は、検査行列の列ブロックの総数ｎと同数あり、変数−チェックメッセージ生成部１１の出力は、各変数−チェックレジスタブロック２１の出力に対応したｎ個の系統からなる。
【００３２】
図３は、変数−チェックレジスタブロック２１の一構成例を示すブロック図である。変数−チェックレジスタブロック２１は、検査行列を構成する巡回行列のサイズと同数のａ個のレジスタ３１と、レジスタ３１間に配置された変数−チェック演算器ブロック（変数−チェック演算手段）３２と、結線スイッチ３３と、出力スイッチ３４とを含む。なお、巡回行列のサイズとは巡回行列の行数または列数をいう。ここで、巡回行列は正方行列なので行数と列数とは同じである。
【００３３】
各レジスタ３１は、各変数−チェック演算器ブロック３２を介して直列に接続されている。そして、最後段のレジスタ３１に出力スイッチ３４が接続されている。出力スイッチ３４は、最後段のレジスタ３１の出力を、最前段のレジスタ３１の入力にフィードバックし、所定の回数フィードバックすると加算器２３に出力するように切り替える。
【００３４】
なお、レジスタの出力が後段のレジスタに入力されるように直列に接続され、最後段のレジスタの出力を最前段のレジスタの入力にフィードバックするように接続されているブロックを、フィードバックシフトレジスタという。
【００３５】
変数−チェックレジスタブロック２１には、検査行列の行ブロック数と同数のｍ系統のデータ列が入力され、すべてのデータが入力されると、出力スイッチ３４が切り替わり、ａ個のレジスタ３１が保存しているデータの一部を順次出力する。
【００３６】
結線スイッチ３３は、変数−チェックレジスタブロック２１への入力を変数−チェック演算器ブロック３２に入力するか否かを、検査行列によって予め定められたｍ個のそれぞれがａビットからなるビット列ｈ０（ｉ），ｈ１（ｉ），・・・，ｈａ−１（ｉ）によって定める（ｉは０からｍ−１の間の整数を表している）。すなわち、結線スイッチ３３は、変数−チェックレジスタブロック２１の入力端（図示せず）と、各変数−チェック演算器ブロック３２との間を結線するか否かによって、変数−チェックレジスタブロック２１への入力を変数−チェック演算器ブロック３２に入力するか否かを定める。
【００３７】
具体的には、例えば、ｈｋ（ｉ）が１であった時は、図３において、ｈｋ（ｉ）と記された部分を結線し、０であった時はｈｋ（ｉ）と記された部分を結線しない（ｋは、０からａ−１の間の整数を表している）。変数−チェックレジスタブロック２１は、結線数と同じ数の変数−チェック演算器ブロック３２を含む。このｍ個のａビットのビット列ｈ０（ｉ）、ｈ１（ｉ）、・・・、ｈａ−１（ｉ）（ｉ＝０，１，・・・，ｍ−１）の選択方法については後述する。
【００３８】
図４は、変数−チェック演算器ブロック３２の一構成例を示すブロック図である。変数−チェック演算器は、加算器４１、比較器４４、セレクタ４３、正負反転装置４２、およびＸＯＲゲート４５を含む。変数−チェック演算器ブロック３２の動作については後述する。
【００３９】
図５は、チェック−変数メッセージ生成部１２の一構成例を示すブロック図である。チェック−変数メッセージ生成部１２は、検査行列の行ブロックの総数ｍと同数のチェック−変数レジスタブロック５１と、チェック−変数レジスタブロック５１が含むレジスタ６１のクロックに同期したカウンタであるカウンタブロック（第２のクロックカウンタ）５２を含む。
【００４０】
各チェック−変数レジスタブロック５１の入力は、変数−チェックメッセージ生成部１１の出力である。すなわち、変数−チェックメッセージ生成部１１の各チェック−変数レジスタブロック２１の出力は、加算器２３を介してチェック−変数メッセージ生成部１１に入力される。
【００４１】
チェック−変数レジスタブロック５１は、検査行列の行ブロック数ｍと同数あり、チェック−変数メッセージ生成部１１の出力は、各チェック−変数レジスタブロック５１の出力に対応したｍ個の系統からなる。
【００４２】
図６は、チェック−変数レジスタブロック５１の一構成例を示すブロック図である。チェック−変数レジスタブロック５１は、検査行列を構成する巡回行列のサイズと同数のａ個のレジスタ６１と、レジスタ６１間に設置されたチェック−変数演算器ブロック（チェック−変数演算手段）６２と、結線スイッチ６３と、出力スイッチ６４とを含む。
【００４３】
各レジスタ６１は、各チェック−変数演算器ブロック６２を介して直列に接続されている。そして、最後段のレジスタ６１に出力スイッチ６４が接続されている。出力スイッチ６４は、最後段のレジスタ６１の出力を、最前段のレジスタ６１の入力にフィードバックし、所定の回数フィードバックすると、正規化演算部１３に出力するように切り替える。
【００４４】
チェック−変数レジスタブロック５１には、検査行列の行ブロック数と同数のｍ系統のデータ列が入力され、すべてのデータが入力されると、出力スイッチ６４が切り替わり、ａ個のレジスタ６１が保存しているデータを順次出力する。
【００４５】
結線スイッチ６３は、チェック−変数レジスタブロック５１への入力をチェック−変数演算器ブロック６２に入力するか否かを、検査行列によって予め定められた、ｎ個の各々がａビットからなるビット列ｇ０（ｊ），ｇ１（ｊ） ，・・・，ｇａ−１（ｊ）によって定める（ｊは０からｎ−１の間の整数を表している）。すなわち、結線スイッチ６３は、チェック−変数レジスタブロック５１の入力端（図示せず）と、各チェック−変数演算器ブロック６２との間を結線するか否かによって、チェック−変数レジスタブロック５１への入力をチェック−変数演算器ブロック６２に入力するか否かを定める。
【００４６】
具体的には、例えば、ｇｋ（ｊ）が１であった時は、図６において、ｇｋ（ｊ）と記された部分を結線し、０であった時はｇｋ（ｊ）と記された部分を結線しない（ｋは、０からａ−１間の整数を表している）。チェック−変数演算器ブロック６２は、結線数と同じ数のチェック−変数演算器を含む。このｎ個のａビットのビット列ｇ０（ｊ），ｇ１（ｊ） ，・・・，ｇａ−１（ｊ）（ｊ＝０，１，・・・，ｎ−１）の選択方法については後述する。
【００４７】
図７は、チェック−変数演算器ブロック６２の一構成例を示すブロック図である。チェック−変数演算器ブロック６２は、比較器７１および７２と、セレクタ７３および７４と、ＸＯＲゲート７５とを含む。チェック−変数演算器ブロック６２の動作については後述する。
【００４８】
本発明の復号装置は、変数−チェックメッセージ生成部１１の出力をチェック−変数メッセージ生成部１２に入力し、チェック−変数メッセージ生成部１２の出力を変数−チェックメッセージ生成部１１に入力する。以下、この処理を所定の回数繰り返した後、変数−チェックメッセージ生成部１１の出力を硬判定して得られるビット系列を、推定送信ビット列として復号装置の出力とする。一回の繰り返し処理には２×ａクロックを要し（ａは検査行列を構成する巡回行列のサイズ）、２×ａ×繰り返し回数分のクロックで復号処理を終える。
【００４９】
前述した変数−チェックレジスタブロック２１の結線を定めるｍ個のａビット列の選択について説明する。
【００５０】
前述したように、変数−チェックレジスタブロック２１は、検査行列の列ブロックの総数ｎと同数あり、その各々は検査行列の列ブロックに対応している。（式１）および（式２）に示すように、第ｊ列ブロック（ｊは０からｎ−１の間の整数を表している）はｍ個のａ×ａ巡回行列Ｈ０，ｊ，Ｈ１，ｊ，・・・，Ｈｍ−１，ｊからなり、これらの巡回行列の各行ベクトルは、（ｆ０（０，ｊ），ｆ１（０，ｊ），・・・，ｆａ−１（０，ｊ）），（ｆ０（１，ｊ），ｆ１（１，ｊ），・・・，ｆａ−１（１，ｊ）），・・・，（ｆ０（ｍ−１，ｊ），ｆ１（ｍ−１，ｊ），・・・，ｆａ−１（ｍ−１，ｊ））を巡回シフトしたものに一致する。変数−チェックレジスタブロック２１の結線を定めるｍ個のａビット列ｈ０（ｉ），ｈ１（ｉ），・・・，ｈａ−１（ｉ）（ｉ＝０，１，・・・，ｍ−１）は、上記の行ベクトルを用いて、次の（式３）によって決定される。
【００５１】
【数３】
2007089064.tif 000005
【００５２】
以上のように、ｎ個の変数−チェックレジスタブロック２１における結線は、それが対応する検査行列の列ブロックに依存している。以下ではこれらを区別し、検査行列の第ｊ列ブロック（ｊは０からｎ−１の間の整数を表している）に対応する結線をｈｋ（ｉ，ｊ）と記す。
【００５３】
次に、各変数−チェックレジスタブロック２１において、レジスタ３１に保存、更新される情報（データ）について説明する。レジスタ３１に保存、更新される情報は、メッセージ部分、およびその他の１ビットによって構成される。メッセージ部分は、変数−チェックメッセージ（ＶＣメッセージ）に相当するデータであり、その他の１ビット部分は、前回の繰り返し処理において変数−チェック演算器ブロック３２が計算したメッセージ部分のデータの正負を表す。これらのデータの詳細については後述する。
【００５４】
前述したチェック−変数レジスタブロック５１の結線を定めるｎ個のａビット列の選択について説明する。前述したように、チェック−変数レジスタブロック５１は、検査行列の行ブロックの総数ｍと同数あり、それらはそれぞれ検査行列の行ブロックに対応している。
【００５５】
（式１）および（式２）に示すように、第ｉ行ブロック（ｉは０からｍ−１の間の整数を表している）はｎ個のａ×ａ巡回行列Ｈ０，ｊ，Ｈ１，ｊ，・・・，Ｈｍ−１，ｊからなり、これらの巡回行列の各行ベクトルは（ｆ０（ｉ，０），ｆ１（ｉ，０），・・・，ｆａ−１（ｉ，０）），（ｆ０（ｉ，１），ｆ１（ｉ，１），・・・，ｆａ−１（ｉ，１）），・・・，（ｆ０（ｉ，ｎ−１），ｆ１（ｉ，ｎ−１），・・・，ｆａ−１（ｉ，ｎ−１））を巡回シフトしたものに一致する。
【００５６】
前述したチェック−変数レジスタブロック５１の結線を定めるｎ個のａビット列ｇ０（ｊ），ｇ１（ｊ） ，・・・，ｇａ−１（ｊ）（ｊ＝０，１，・・・，ｎ−１）は、上記の行ベクトルを用いて、次の（式４）によって決定される。
【００５７】
【数４】
2007089064.tif 000006
【００５８】
以上のように、ｎ個のチェック−変数レジスタブロック５１における結線は、それが対応する検査行列の行ブロックに依存している。以下ではこれらを区別し、検査行列の第ｉ列ブロック（ｉは０からｍ−１の間の整数を表している）に対応する結線をｇｋ（ｉ，ｊ）と記す。
【００５９】
次に、各チェック−変数レジスタブロック５１において、レジスタ６１に保存、更新される情報（データ）について説明する。レジスタ６１に保存、更新される情報はメッセージ部分、クロックカウンタの値、およびその他の１ビットによって構成される。メッセージ部分は、チェック−変数メッセージ（ＣＶメッセージ）に相当するデータである。
【００６０】
また、その他の１ビット部分は変数−チェックメッセージ生成部１１によって算出され、チェック−変数メッセージ生成部１２に入力されたメッセージの硬判定結果（１ビットで量子化したもの）に対するシンドロームであり、これらの値がすべて０であった場合、変数−チェックメッセージ生成部１１で算出されたメッセージの硬判定結果は符号語となり、復号装置が出力する推定送信ビット列になる。これらのデータの詳細については後述する。
【００６１】
次に、本発明の第１の実施の形態の動作について説明する。まず、変数−チェックメッセージ生成部１１の入力および出力と、チェック−変数メッセージ生成部１２の入力および出力とについて説明する。チェック−変数メッセージ生成部１２の出力データは、正規化演算部１３を介して、変数−チェックメッセージ生成部１１に入力される。
【００６２】
このチェック−変数メッセージ生成部１２の出力データは４つの種類に大別され、これらをそれぞれ、Ｌｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）と記す。ここで、ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表している。Ｌｔ，１（ｓ）、Ｌｔ，２（ｓ）は、チェック−変数メッセージに相当するデータである。Ｐ２（ｓ，ｔ）は、チェック−変数メッセージ生成部１２の入力データ（変数−チェックメッセージ生成部１１の出力データ）の硬判定結果（例えば、最上位ビット）と、（式１）の検査行列との積を示す１ビットのデータである。
【００６３】
μ（ｓ，ｔ）は、計算の精度に応じて使い分ける。具体的には、最も高い計算精度を要求する場合には、μ（ｓ，ｔ）は２つの整数の組を表すデータとし、それよりも粗い計算精度で十分な場合には、μ（ｓ，ｔ）は１つの整数を表すデータとする。さらに粗い計算精度で十分な場合には、μ（ｓ，ｔ）のデータを使用しない。計算精度が粗くなるに従って、μ（ｓ，ｔ）のデータ量が少なくなるため、装置規模は小さくなるという関係にある。
【００６４】
以下、μ（ｓ，ｔ）が２つの整数の組を表す、最も精度が高い場合について説明する。μ（ｓ，ｔ）については後述する。
【００６５】
正規化演算部１３には、チェック−変数メッセージ生成部１２の出力データＬｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）が入力される。正規化演算部１３は、Ｐ２（ｓ，ｔ）およびμ（ｓ，ｔ）については、入力と全く同じデータをそのまま出力し、Ｌｔ，１（ｓ）およびＬｔ，２（ｓ）については、予め定められた定数αを乗じたαＬｔ，１（ｓ）、およびαＬｔ，２（ｓ）を出力する。
【００６６】
従って、実際には図１に示すように、チェック−変数メッセージ生成部１２の出力データＬｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）は、そのまま変数−チェックメッセージ生成装置に入力されるのではなく、正規化演算部１３を介して、αＬｔ，１（ｓ）、αＬｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）が変数−チェックメッセージ生成部１１に入力されることになる。
【００６７】
なお、以下の説明においては、記号の乱用を防ぐため、この記述（定数αを乗じた記述）を省略し、変数−チェックメッセージ生成部１１に入力されるデータを、チェック−変数メッセージ生成部１２の出力データの記法であるＬｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）で表記する。
【００６８】
変数−チェックメッセージ生成部１１の入力データは、チェック−変数メッセージ生成部１２の出力と、通信路の出力Ｆｉ（ｉは０からｎａ−１の間の整数を表している）とである。
【００６９】
チェック−変数メッセージ生成部１２は、前述のように、検査行列（式１）の行ブロックの総数ｍと同数のチェック−変数レジスタブロック５１を含み、第ｓ番目のチェック−変数レジスタブロック５１の時刻ｔにおける出力は、Ｌｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）になる（ｓは０からｍ−１の間の整数を表し、tは０からａ−１の間の整数を表している）。これらは、出力時にチェック−変数レジスタブロック５１において、各レジスタ６１が保存しているデータである。
【００７０】
変数−チェックメッセージ生成部１１の出力は、チェック−変数メッセージ生成部１２の入力データになる。この入力データをＺｒ（ｌ）と記す。ここでｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している。変数−チェックメッセージ生成部１１は、前述のように、検査行列（式１）の列ブロックの総数ｎと同数の変数−チェックレジスタブロック２１を含み、第ｌ番目の変数−チェックレジスタブロック２１におけるｒ番目の出力がＺｒ（ｌ）となり（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）、Ｚｒ（ｌ）および後述する１ビットの情報Ｐ１（ｌ，ｒ）が、出力時に変数−チェックレジスタブロック２１において各レジスタ３１が保存しているデータである。
【００７１】
変数−チェックメッセージ生成部１１の動作について説明する。変数−チェックメッセージ生成部１１には、前述のように、Ｌｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、μ（ｓ，ｔ）、および通信路の出力Ｆｉ（ｉは０からｎａ−１の間の整数を表し、ｓは０からｍ−１の間の整数表し、tは０からａ−１の間の整数を表している）が入力される。そして、変数−チェックメッセージ生成部１１は、次の（式５）を用いて、Ｚｒ（ｌ）を算出する（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）。
【００７２】
【数５】
2007089064.tif 000007
【００７３】
なお、（式５）において、第１項が、対数尤度比を示し、第２項が事前値を示している。ここで、各Ｐ１（ｌ，ｒ）は１ビットのデータであり、変数−チェックメッセージ生成部１１における変数−チェックレジスタブロック２１の各レジスタ３１が予め保存している。変数−チェックメッセージ生成部１１は、（式５）を用いて変数−チェックメッセージデータＺｒ（ｌ）を算出する（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）とともに、算出したＺｒ（ｌ）を用いて、Ｐ１（ｌ，ｒ）を、次の（式６）によって更新する。
【００７４】
【数６】
2007089064.tif 000008
【００７５】
すなわち、Ｐ１（ｌ，ｒ）は、Ｚｒ（ｌ）の最上位ビットに相当する１ビットのデータであり、このデータの列（ビット列）が、推定送信ビット列として、復号装置から出力される。
【００７６】
変数−チェックレジスタブロック２１の動作について説明する。変数−チェックメッセージ生成部１１は、検査行列（式１）の列ブロックの総数ｎと同数の変数−チェックレジスタブロック２１を有し、各変数−チェックレジスタブロック２１は、検査行列を構成する巡回行列のサイズと同数のａ個のレジスタ３１を有する。
【００７７】
ここで、第ｌ番目の変数−チェックレジスタブロック２１における第ｒ番目のレジスタ３１に保存されているメッセージデータの初期状態（時刻０における値）をＺｒ（ｌ）（ａ）と記し、時刻ａ−ｊにおけるメッセージデータをＺｒ（ｌ）（ｊ）と記すことにする（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表し、ｊは０からａ−１の間の整数を表している）。初期状態を、Ｚｒ（ｌ）（ａ）＝０とすると、時刻ａ−ｊにおけるメッセージデータは、時刻ａ−ｊ−１におけるメッセージデータから、次の（式７）によって計算される。
【００７８】
【数７】
2007089064.tif 000009
【００７９】
ここで、（式７）の記号Ｐ１（ｌ，ｒ）ｊは、初期状態（時刻０における値）をＰ１（ｌ，ｒ）ａ＝Ｐ１（ｌ，ｒ）とし、時刻ａ−ｊにおいて、次の（式８）によって更新される。
【００８０】
【数８】
2007089064.tif 000010
【００８１】
変数−チェックメッセージ生成部１１の、第ｌ番目の変数−チェックレジスタブロック２１において、時刻ａ−ｊに第ｒ番目のレジスタ３１に保存されているデータは、Ｚｒ（ｌ）（ｊ）とＰ１（ｌ，ｒ）ｊとであり、これらを各時刻毎に（式７）と（式８）によって更新する処理を行う装置が、図４に示した変数−チェック演算器ブロック３２である。
【００８２】
変数−チェック演算器ブロック３２について説明する。変数−チェック演算器ブロック３２には、ｃｎｔ、μ、Ｌ１、Ｌ２、Ｐ２、Ｐ１−ｉｎ、およびＺｉｎが入力される。具体的には、比較器４４には、ｃｎｔとμとが入力される。セレクタ４３には、Ｌ１、Ｌ２、および比較器４４の出力が入力される。ＸＯＲゲート４５には、Ｐ２、およびＰ１−ｉｎが入力される。正負反転装置４２には、セレクタ４３の出力と、ＸＯＲゲート４５の出力とが入力される。加算器４１には、正負反転装置４２の出力と、Ｚｉｎとが入力される。
【００８３】
従って、比較器４４に入力されたクロックカウンタの値であるｃｎｔと、レジスタ３１に割り当てられた０からｎ−１の間の整数との比較結果に応じて、セレクタ４３が選択したＬ１またはＬ２を、加算器４１が、Ｚｉｎに加算する。
【００８４】
すなわち、クロックカウンタの値と、レジスタ３１に割り当てられた０からｎ−１の間の整数とに応じて、Ｚｉｎに加算される値が選択される。
【００８５】
そして、μ、Ｌ１、Ｌ２、およびＰ２は、それぞれ（式７）のμ（ｉ，ｊ）、Ｌｊ，１（ｓ）、Ｌｊ，２（ｓ）、およびＰ２（ｉ，ｊ）に対応し、ｃｎｔは、変数−チェックレジスタブロック２１毎に予め定められた０からｎ−１の間の整数ｌとクロックとに同期したカウンタの値に対応する０からａ−１の間の整数の組を表している。また、変数−チェック演算器ブロック３２は、入力ＺｉｎおよびＰ１−ｉｎに対し、次の（式９）、（式１０）に示すＺ１−ｏｕｔおよびＰ１−ｏｕｔを出力する。
【００８６】
【数９】
2007089064.tif 000011
【００８７】
【数１０】
2007089064.tif 000012
【００８８】
そして、出力されたＺ１−ｏｕｔおよびＰ１−ｏｕｔは、レジスタ３１を介して次の段の変数−チェック演算器ブロック３２に、ＺｉｎおよびＰ１−ｉｎとしてそれぞれ入力される。
【００８９】
この変数−チェック演算器ブロック３２を、第ｌ番目の変数−チェックレジスタブロック２１における第ｒ番目のレジスタ３１と第ｒ＋１番目のレジスタ３１との間に、｛ｈｒ（０,ｌ），ｈｒ（１,ｌ），ｈｒ（２,ｌ），・・・，ｈｒ（ｍ−１,ｌ）｝に含まれる１の数と同じ数だけ設置することで（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）、（式７）に示した演算処理を実現することができる。
【００９０】
（式７）と（式８）との計算によって、時刻ａにおいて第ｌ番目の変数−チェックレジスタブロック２１における第ｒ番目のレジスタ３１に保存されているメッセージデータＺｒ（ｌ）（０）と通信路出力Ｆｌａ＋ｒとの算術和が、次の（式１１）に示すように、（式５）におけるＺｒ（ｌ）と一致する。
【００９１】
【数１１】
2007089064.tif 000013
【００９２】
すべての入力データを入力し終えた時点（時刻ａ）で、変数−チェックメッセージ生成部１１の、第ｌ番目の変数−チェックレジスタブロック２１における、第ｒ番目のレジスタ３１に保存されているデータは、Ｚｒ（ｌ）（０）とＰ１（ｌ，ｒ）０とである。そして、その後、Ｚｒ（ｌ）（０）は、（式１１）を用いて加算され、チェック−変数メッセージ生成部１２に、各変数−チェックレジスタブロック２１の第０番目のレジスタ３１に保存されたデータが出力される。
【００９３】
変数−チェックレジスタブロック２１は、出力と同時に、第ｊ＋１番目のレジスタ３１に保存されたデータを、第ｊ番目のレジスタ３１へシフトして（ｊは０からａ−２の間の整数を表している）、第０番目のレジスタ３１を通して順次出力する。そして、変数−チェックレジスタブロック２１は、第ａ−１番目のレジスタ３１のメッセージ部分を初期化し、他の１ビットのデータ部分には、出力したメッセージデータＺｒ（ｌ）から（式６）によって導かれた１ビットデータを入力することで、すべての出力が完了した時点で各レジスタ３１は初期化される。
【００９４】
このように、変数−チェックメッセージ生成処理には、入力とそれに伴う処理にａクロック、出力にａクロックをそれぞれ要し、これらの動作を、それぞれ変数−チェックメッセージ生成部１１の入力処理モード、変数−チェックメッセージ生成部１１の出力モードという。
【００９５】
以上の処理により、図２、図３、図４に示した各構成部によって、変数−チェックメッセージＺｒ（ｌ）は、ＲＡＭを使用することなく、レジスタ３１とレジスタ３１間に設置された主に加算器４１からなる変数−チェック演算器ブロック３２によって算出される。
【００９６】
次に、チェック−変数メッセージ生成部１２の動作について説明する。チェック−変数メッセージ生成部１２の出力は、正規化演算部１３を介して変数−チェックメッセージ生成部１１に入力される。前述したように、これらのデータをＬｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）と記す（ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表している）。
【００９７】
チェック−変数メッセージ生成部１２は、前述したように、検査行列（式１）の列ブロックの総数ｍと同数のチェック−変数レジスタブロック５１を有し、第ｓ番目の変数−チェックレジスタブロック５１におけるａ−１−ｔ番目の出力が、Ｌｔ，１（ｓ）、Ｌｔ，２（ｓ）、Ｐ２（ｓ，ｔ）、およびμ（ｓ，ｔ）となる（ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表している）。そして、これらが、出力時にチェック−変数レジスタブロック１２において、各レジスタ６１に保存されているデータになる。
【００９８】
チェック−変数メッセージ生成部１２は、前述したように、変数−チェックメッセージ生成部１１の出力Ｚｒ（ｌ）が入力され（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）、次の（式１２）および（式１３）によってＬｔ，１（ｓ）およびＬｔ，２（ｓ）を算出する。
【００９９】
【数１２】
2007089064.tif 000014
【０１００】
【数１３】
2007089064.tif 000015
【０１０１】
ここで、Ｗｔ（ｓ）は次の（式１４）に示す集合を表す。すなわち、Ｌｔ，１（ｓ）は（式１４）の集合Ｗｔ（ｓ）の要素の中で値が最小のものとなり、Ｌｔ，２（ｓ）は集合Ｗｔ（ｓ）の要素の中で、値が２番目に小さいものとなる。
【０１０２】
【数１４】
2007089064.tif 000016
【０１０３】
なお、｜Ｚｊ（ｉ）｜はＺｊ（ｉ）の絶対値を表す。また、Ｐ２（ｓ，ｔ）を次の（式１５）によって算出する。
【０１０４】
【数１５】
2007089064.tif 000017
【０１０５】
ここで、（式１５）の各Ｐ１（ｉ，ｊ）は、前述した（式６）で示したように、Ｚｊ（ｉ）の正負を表す１ビットのデータである。このように、変数−チェックメッセージ生成部１１の出力Ｚｒ（ｌ）はチェック−変数メッセージ生成部１２に入力されるが、チェック−変数メッセージ生成部１２の内部では、Ｚｒ（ｌ）の正負を表す１ビット（最上位ビット）と、それ以外の絶対値を表すデータとに分割された形で処理される。
【０１０６】
また、μ（ｓ，ｔ）は、（式１４）の集合Ｗｔ（ｓ）の要素の中で、その値が最小のものが｜Ｚγ（λ）｜である時（すなわち、Ｌｔ，１（ｓ）＝｜Ｚγ（λ）｜である時）、次の（式１６）を満たす。
【０１０７】
【数１６】
2007089064.tif 000018
【０１０８】
チェック−変数レジスタブロック５１の動作について説明する。チェック−変数メッセージ生成部１２は、（式１）に示した検査行列の行ブロックの総数ｍと同数のチェック−変数レジスタブロック５１を有し、各チェック−変数レジスタブロック５１は、検査行列を構成する巡回行列のサイズと同数のａ個のレジスタ６１を有する。
【０１０９】
ここで、第ｓ番目のチェック−変数レジスタブロック５１における第ｔ番目のレジスタ６１に保存されているメッセージデータ部分の初期状態（時刻０における値）を、Ｌｔ，１（ｓ）（０），Ｌｔ，２（ｓ）（０）と記し、１ビットの情報Ｐ２（ｓ，ｔ）に相当するデータの初期状態をＰ２（ｓ，ｔ）０と記し、各データの時刻ｊにおけるデータを、それぞれＬｔ，１（ｓ）（ｊ）、Ｌｔ，２（ｓ）（ｊ）、Ｐ２（ｓ，ｔ）ｊと記す（ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表し、ｊは１からａの間の整数を表している）。
【０１１０】
初期状態として、Ｌｔ，１（ｓ）（０）とＬｔ，２（ｓ）（０）とをレジスタ６１が表現できる最大の数とし、Ｐ２（ｓ，ｔ）０＝０とすると、時刻ｊにおける各データは、時刻ｊ−１における各データから、次の（式１７）、（式１８）および（式１９）によって計算される。
【０１１１】
【数１７】
2007089064.tif 000019
【０１１２】
【数１８】
2007089064.tif 000020
【０１１３】
【数１９】
2007089064.tif 000021
【０１１４】
ここで、（式１７）および（式１８）のＷｔ−１（ｓ）（ｊ−１）は、次の（式２０）に示した集合を表している。
【０１１５】
【数２０】
2007089064.tif 000022
【０１１６】
すなわち、（式１７）のＬｔ，１（ｓ）（ｊ）はＷｔ−１（ｓ）（ｊ−１）の要素の中で値が最小のものであり、（式１８）のＬｔ，２（ｓ）（ｊ）はＷｔ−１（ｓ）（ｊ−１）の要素の中で、値が２番目に小さいものである。すなわち、Ｗｔ−１（ｓ）（ｊ−１）の要素の中で、値が最小のものと、値が２番目に小さいものとが選択され、次の段のレジスタ６１に保存される。
【０１１７】
（式１６）のμ（ｓ，ｔ）についても、同様に、時刻０における初期状態をμ（ｓ，ｔ）０とすると、時刻ｊにおけるデータμ（ｓ，ｔ）ｊは、次の（式２１）によって算出される。
【０１１８】
【数２１】
2007089064.tif 000023
【０１１９】
チェック−変数メッセージ生成部１２の、第ｓ番目のチェック−変数レジスタブロック５１において、時刻ｊに第ｔ番目のレジスタ６１に保存されているデータはＬｔ，１（ｓ）（ｊ）、Ｌｔ，２（ｓ）（ｊ）、Ｐ２（ｓ，ｔ）ｊ、およびμ（ｓ，ｔ）ｊであり、これらを各時刻毎に（式１７）、（式１８）、（式１９）および（式２１）によって更新する処理を行うブロックがチェック−変数演算器ブロック６２である。
【０１２０】
チェック−変数演算器ブロック６２について説明する。チェック−変数演算器ブロック６２には、Ｚ、ｃｎｔ、Ｐ２−ｉｎ、μｉｎ、Ｌ１−ｉｎ、およびＬ２−ｉｎが入力される。
【０１２１】
具体的には、ＸＯＲゲート７５には、Ｐ２−ｉｎとＺの正負を示す情報（Ｚの最上位ビット）とが入力される。比較器７１には、Ｌ２−ｉｎとＺの絶対値（Ｚの最上位以外のビット）とが入力される。比較器７２には、Ｌ１−ｉｎとＺの絶対値とが入力される。セレクタ７３には、Ｚの絶対値、Ｌ１−ｉｎ、Ｌ２−ｉｎ、および比較器７１の出力が入力され、比較器７１の出力結果に応じて出力を切り替える。セレクタ７４には、ｃｎｔ、μｉｎ、および比較器７２の出力が入力され、比較器７２の出力結果に応じて出力を切り替える。
【０１２２】
なお、図７では、Ｚを最上位ビット（Ｚの正負を示す情報）と、最上位以外のビット（Ｚの絶対値）とに分割することを白の菱形で示し、Ｚの最上位ビットをＸＯＲゲート７５に入力し、Ｚの最上位以外のビットを比較器７１、７２、セレクタ７３に入力している。
【０１２３】
そして、Ｚは、（式２０）のＺｊ−１（ｉ）に対応し、ｃｎｔは、０からｎ−１の間の整数と、クロックに同期したカウンタ値に対応する０からａ−１の間の整数との組を表している。チェック−変数演算器ブロック６２は、入力Ｌ１−ｉｎ、Ｌ２−ｉｎ、Ｐ２−ｉｎおよびμｉｎに対し、次の（式２２）、（式２３）、（式２４）および（式２５）に示すＬ１−ｏｕｔ、Ｌ２−ｏｕｔ、Ｐ２−ｏｕｔおよびμｏｕｔを出力する。
【０１２４】
【数２２】
2007089064.tif 000024
【０１２５】
【数２３】
2007089064.tif 000025
【０１２６】
【数２４】
2007089064.tif 000026
【０１２７】
【数２５】
2007089064.tif 000027
【０１２８】
すなわち、チェック−変数演算器ブロック６２は、（式２４）で示したように、これまでに算出したＺのうち、最も小さい値をＬ１−ｏｕｔとして、レジスタ６１を介して次の段のチェック−変数演算器ブロック６２に出力する。そして、次の段のチェック−変数演算器ブロック６２は、（式２５）で示したように、Ｌ１−ｉｎとして入力された前の段のＬ１−ｏｕｔの値が、最も小さくなったときに、μｏｕｔとして、ｃｎｔである０からｎ−１の間の整数と、クロックに同期したカウンタ値に対応する０からａ−１の間の整数との組を出力する。
【０１２９】
チェック−変数演算器ブロック６２を、第ｓ番目のチェック−変数レジスタブロック５１における第ｔ番目のレジスタ６１と第ｔ＋１番目のレジスタ６１との間に、｛ｇｔ（ｓ,０），ｇｔ（ｓ,１），ｇｔ（ｓ,２），・・・，ｇｔ（ｓ,ｎ−１）｝に含まれる１の数と同じ数だけ設置することで（ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表している）、（式１７）、（式１８）、（式１９）および（式２１）に示した演算処理を実現することができる。
【０１３０】
（式１７）、（式１８）、（式１９）および（式２１）の計算によって、時刻ａにおいて第ｓ番目のチェック−変数レジスタブロック５１における第ｔ番目のレジスタ６１に保存されているデータＬｔ，１（ｓ）（ａ）、Ｌｔ，２（ｓ）（ａ）、Ｐ２（ｓ，ｔ）ａ、およびμ（ｓ，ｔ）ａが、次の（式２６）、（式２７）、（式２８）および（式２９）に示すように、（式１２）におけるＬｔ，１（ｓ）、（式１３）におけるＬｔ，２（ｓ） 、（式１５）におけるＰ２（ｓ，ｔ）、および（式１６）におけるμ（ｓ，ｔ）に一致する。
【０１３１】
【数２６】
2007089064.tif 000028
【０１３２】
【数２７】
2007089064.tif 000029
【０１３３】
【数２８】
2007089064.tif 000030
【０１３４】
【数２９】
2007089064.tif 000031
【０１３５】
すべての入力データを入力し終えた時点（時刻ａ）で、チェック−変数メッセージ生成部１２の、第ｓ番目のチェック−変数レジスタブロック５１における、第ｔ番目のレジスタ６１に保存されているデータは、Ｌｔ，１（ｓ）（ａ）、Ｌｔ，２（ｓ）（ａ）、Ｐ２（ｓ，ｔ）ａ、およびμ（ｓ，ｔ）ａであり、これらは、各チェック−変数レジスタブロック５１の第ａ−１番目のレジスタ６１から、変数−チェックメッセージ生成部１１に出力される。チェック−変数メッセージ生成部１２は、出力と同時に、第ｊ番目のレジスタ６１に保存されたデータを、第ｊ＋１番目のレジスタ６１へシフトして（ｊは０からａ−２の間の整数を表している）、第ａ−１番目のレジスタ６１を通して順次出力する。
【０１３６】
第０番目のレジスタ６１を初期化することで、すべての出力が完了した時点で各レジスタ６１は初期化される。このように、チェック−変数メッセージ生成処理には、入力とそれに伴う処理にａクロック、出力にａクロックをそれぞれ要し、これらの動作をそれぞれチェック−変数メッセージ生成部１２の入力処理モード、チェック−変数メッセージ生成部１２の出力モードと呼ぶ。以上により、図５、図６、図７に示したブロックによって、チェック−変数メッセージ生成処理は、ＲＡＭを使用することなく、シフトレジスタとシフトレジスタ間に配置された主に加算器からなるチェック−変数演算器ブロック６２によって実現される。
【０１３７】
なお、変数−チェックメッセージ生成部１１、チェック−変数メッセージ生成部１２、および正規化演算部１３は、それぞれＩＣ（Ｉｎｔｅｇｒａｔｅｄ  Ｃｉｒｃｕｉｔ）等の半導体デバイスによって実現される。従って、変数−チェックメッセージ生成部１１が含む各ブロックや、チェック−変数メッセージ生成部１２が含む各ブロックは、それぞれＩＣ等の半導体デバイスによって実現される。
【０１３８】
次に、図１に示した本発明の復号装置全体の動作について説明する。図８は、復号装置全体の動作を示す説明図である。
【０１３９】
復号装置による処理は、変数−チェックメッセージ生成部１１が出力モードであり、チェック−変数メッセージ生成部１２が入力処理モードであるようにスタートする。
【０１４０】
復号処理スタート時には、変数−チェックレジスタブロック２１におけるレジスタ３１が保存しているデータをすべて０に初期化しておき、チェック−変数レジスタブロック５１におけるレジスタ６１が保存しているデータを初期化しておく。
【０１４１】
スタート時からａクロック経過するまでの間、変数−チェックメッセージ生成部１１がチェック−変数メッセージ生成部１２に出力するメッセージデータは、スタート時に変数−チェックレジスタブロック２１におけるレジスタ３１が保存しているデータをすべて０に初期化したことにより、受信データＦｌａ＋ｒと一致する（ｌは０からｎ−１の間の整数を表し、ｒは０からａ−１の間の整数を表している）。
【０１４２】
スタート時からａクロック経過すると、変数−チェックメッセージ生成部１１による、チェック−変数メッセージ生成部１２へのメッセージデータの出力は終了する。この時点で、変数−チェックレジスタブロック２１におけるレジスタ３１には、前述のようにＦｌａ＋ｒの正負を表す１ビットがセット（保存）されており、チェック−変数レジスタブロック５１におけるレジスタ６１には、次に変数−チェックメッセージ生成部１２に出力するデータが保存されている。
【０１４３】
以下、図８に示すように、ａクロック毎に入力処理モードと、出力モードとを切り替える。すなわち、チェック−変数メッセージ生成部１２による変数−チェックメッセージ生成部１１へのメッセージデータの出力と、変数−チェックメッセージ生成部１１からチェック−変数メッセージ生成１２へのメッセージデータの出力とが交互に行われる。
【０１４４】
各モードにおけるチェック−変数メッセージ生成部１２と変数−チェックメッセージ生成部１１とは、予め設定した回数分だけ上記処理を繰り返す。そして、最後に、変数−チェックメッセージ生成部１１を出力モード、チェック−変数メッセージ生成部１２を入力処理モードにし、変数−チェックメッセージ生成部１１は、出力のデータの正負を表す１ビットを、復号装置の出力として順次出力する。
【０１４５】
なお、チェック−変数メッセージ生成部１２において処理されているデータＰ２（ｓ，ｔ）は、上記復号処理の結果、受信データ中に含まれたエラーを訂正することができたか否かを判定するためのデータとして使用することができる。
【０１４６】
以上に述べたように、この実施の形態によれば、変数−チェックメッセージと推定送信ビットとを、ＲＡＭを使用することなく、複数のレジスタ３１と、各レジスタ３１間に設置された主に加算器からなる変数−チェック演算器ブロック３２によって算出する処理を行うことができる。
【０１４７】
また、この実施の形態によれば、チェック−変数メッセージを、ＲＡＭを使用することなく、複数のレジスタ６１と、各レジスタ６１間に設置された主に比較器からなるチェック−変数演算器ブロック６２によって算出する処理を行うことができる。
【０１４８】
そして、上記の処理を繰り返して、復号装置は、入力された受信データ系列を復号し、推定送信ビット列を出力する。すなわち、ＲＡＭを用いない簡単な構成の復号装置が、ＲＡＭのアクセス速度に制限されることなく、高速で、入力された受信データ系列を復号し、推定送信ビット列を出力することができる。
【０１４９】
また、この実施の形態によれば、チェック−変数メッセージ生成部１２において処理されているデータＰ２（ｓ，ｔ）を、受信データ中に含まれたエラーを訂正することができたか否かを判定するためのデータとして使用することができる。
【０１５０】
なお、記憶装置としてのＲＡＭを用いた低密度パリティ検査符号の復号装置の一構成例について、図面を参照して説明する。図９は、ＲＡＭを用いた低密度パリティ検査符号の復号装置の一構成例を示すブロック図である。この復号装置は、誤り訂正の対象となる受信データを保持する記憶装置してのＲＡＭ（図示せず）と、メッセージと呼ばれる復号処理の過程で生じるデータを保持するための記憶装置としてのＲＡＭによって実現されるメッセージメモリブロック８４と、ＲＡＭのアドレスを生成して制御するアドレス生成制御装置８２と、メッセージを更新するための変数ノード処理装置８１と、チェックノード処理装置８３とを含む。
【０１５１】
メッセージは変数−チェックメッセージと、チェック−変数メッセージとの２種類に大別される。これらのメッセージは、各々さらに細かく分類される。検査行列Ｈの行数がＭ、列数がＮである場合（ＭとＮとは正の整数をそれぞれ表している）、変数−チェックメッセージは、Ｚｉ，ｊに分類され、チェック−変数メッセージはＬｉ，ｊに分類される。
【０１５２】
添え字であるｉとｊとはそれぞれ０からＭ−１の間の整数を表し、および０からＮ−１の間の整数を表している。ｉは検査行列の行ベクトルまたは列ベクトルの成分に対応し、ｊは検査行列の列ベクトルの成分または行ベクトルの成分に対応する。変数ノード処理装置８１は、チェック−変数メッセージおよび受信データから、変数−チェックメッセージを更新する処理を行う。変数ノード処理の詳細は次の（式３０）で表される。
【０１５３】
【数３０】
2007089064.tif 000032
【０１５４】
ここで、ｊは０からＮ−１の間の整数を表し、ｉは０からＭ−１の間の整数を表し、Ｆｊは対応する受信データを示し、ｉ’はｉと一致しない０からＭ−１の間の整数であって、対応する検査行列の行ベクトルのｊに対応する成分が１であるものすべてにわたる。チェックノード処理装置８３は変数−チェックメッセージからチェック−変数メッセージを更新する処理を行う。チェックノード処理の詳細は次の（式３１）で表される。
【０１５５】
【数３１】
2007089064.tif 000033
【０１５６】
ここで、ｊは０からＮ−１の間の整数を表し、ｉは０からＭ−１の間の整数を表し、Ｐｉ，ｊは０または１のいずれかを表している。また、ｊ’はｊと一致しない０からＮ−１の間の整数であって、対応する検査行列の列ベクトルのｉに対応する成分が１であるものすべてにわたる。
【０１５７】
なお、検査行列が巡回行列のブロックからなる低密度パリティ検査符号（擬似巡回型低密度パリティ検査符号）の場合、検査行列の規則性を利用すれば、（式３０）における加算部分と、（式３１）における最小値算出処理部分のインデックスとをパターン化することができ、ＲＡＭアクセスのためのアドレス生成処理が簡単化できる。
【０１５８】
実施の形態２．
次に、本発明の第２の実施の形態について説明する。まず、第１の実施の形態の説明で前述したチェック−変数メッセージ生成部１２が算出する４種類のデータの内の１つであるμ（ｓ，ｔ）の役割について説明する（ｓは０からｍ−１の間の整数を表し、ｔは０からａ−１の間の整数を表している）。
【０１５９】
データμ（ｓ，ｔ）は、前述したように、０からｎ−１の間の整数、および０からａ−１の間の整数の２つの整数の組からなり、（式７）で示した変数−チェックメッセージ生成部１１が行う処理で、チェック−変数メッセージ生成部１２が出力した２つのデータＬｔ，１（ｓ）とＬｔ，２（ｓ）とのどちらを加算するか決定するために必要になる。
【０１６０】
Ｌｔ，１（ｓ）とＬｔ，２（ｓ）とは、前述したように、（式１４）における集合Ｗｔ（ｓ）の要素の中で、その値が最も小さいものと、２番目に小さいものとをそれぞれ表すが、ここで（式７）で示した変数−チェックメッセージ生成部１１での処理を、次の（式３２）に置き換えると、この演算で計算される値は、検査行列（式１）および（式２）の選択に依存するものの、（式７）が算出する値に比較的よく近似する。
【０１６１】
【数３２】
2007089064.tif 000034
【０１６２】
すなわち、（式１４）における集合Ｗｔ（ｓ）の要素の中でその値が最も小さいものと、２番目に小さいものとを両方使用するのではなく、２番目に小さいもののみを使用することにより、チェック−変数メッセージ生成部１２において、μ（ｓ，ｔ）を算出する必要がなくなる。
【０１６３】
そのため、チェック−変数レジスタブロック５１における各レジスタ６１のビット幅の削減や、チェック−変数演算器ブロック６２の構成の簡単化、および変数−チェック演算器ブロック３２の構成の簡単化を実現することができ、復号装置全体の装置規模を削減し、処理を簡単化することができる。
【０１６４】
図１０は、簡単化した変数−チェック演算器ブロック３２の一構成例を示すブロック図である。
【０１６５】
図１０に示すように、簡単化した変数−チェック演算器ブロック３２は、正負反転装置１０２と、加算機１０１と、ＸＯＲゲート１０３を含む。ＸＯＲゲート１０３には、Ｐ２とＰ１−ｉｎとが入力される。正負反転装置１０２には、Ｌ２とＸＯＲゲート１０３の出力が入力される。加算器１０１には、Ｚｉｎと正負反転装置１０２の出力とが入力される。なお、図１０に示した入出力データは、図４において、同記号（Ｐ１−ｉｎ等）で示したデータと同様なため、説明を省略する。
【０１６６】
以上のように、簡単化した変数−チェック演算器ブロック３２は、入力μ、およびＬ１を必要としないため、図４に示した第１の実施の形態の変数−チェック演算器３２と比較して構成が簡単化されており、対応する変数−チェックレジスタブロック２１におけるレジスタ３１のビット幅を削減することができる。
【０１６７】
図１１は、簡単化したチェック−変数演算器ブロック６２の一構成例を示すブロック図である。
【０１６８】
図１１に示すように、簡単化したチェック−変数演算器ブロック６２は、セレクタ１１３、比較器１１１および１１２を含む。ＸＯＲゲート１１４には、Ｚの正負を示す情報（Ｚの最上位ビット）とＰ２−ｉｎとが入力される。比較器１１１には、Ｚの絶対値（Ｚの最上位以外のビット）とＬ２−ｉｎとが入力される。比較器１１２には、Ｚの絶対値とＬ１−ｉｎとが入力される。セレクタ１１３には、Ｚの絶対値、Ｌ１−ｉｎ、Ｌ２−ｉｎ、比較器１１１の出力、および比較器１１２の出力が入力される。
【０１６９】
なお、図１１は、Ｚを最上位ビット（Ｚの正負を示す情報）と、最上位以外のビット（Ｚの絶対値）とに分割することを、白の菱形で示し、Ｚの最上位ビットをＸＯＲゲート７５に入力し、Ｚの最上位以外のビットを比較器１１１、１１２、セレクタ１１３に入力している。
【０１７０】
なお、図１１に示した入出力データは、図７において、同記号（Ｐ２−ｉｎ等）で示したデータとそれぞれ同様なため、説明を省略する。
【０１７１】
以上のように、簡単化したチェック−変数演算器ブロック６２は、入力μを必要としないため、図７に示した第１の実施の形態のチェック−変数演算器ブロック６２と比較して構成が簡単化されており、対応するチェック−変数レジスタブロック５１におけるレジスタ６１のビット幅を削減することができる。
【０１７２】
以上に述べたように、この実施の形態によれば、チェック−変数レジスタブロック５１におけるレジスタ６１のビット幅を削減するため、復号装置全体の装置規模を削減し、処理を簡単化することができる。
【０１７３】
なお、次の（式３３）によって計算を行うことにより、（式３２）よりも計算精度が高く、（式７）よりも簡単な処理でメッセージデータを算出することができる。
【０１７４】
【数３３】
2007089064.tif 000035
【０１７５】
（式３３）におけるμ’（ｉ，ｊ）は、０からａ−１の間の整数を表す。チェック−変数演算器ブロック６２は、第１の実施の形態と同様なタイミング（Ｌ１−ｉｎとして入力された前の段のＬ１−ｏｕｔの値が、最も小さくなったとき）で、μ’（ｉ，ｊ）を出力する。ここで、μ’（ｉ，ｊ）は、第１の実施の形態の（式７）および（式２５）において、μ（ｉ，ｊ）が０からｎ−１の間の整数と、０からａ−１の間の整数との組を表していたのと比較して、情報量を減らしており、その分変数−チェックメッセージデータの計算精度が下がる。
【０１７６】
チェック−変数演算器ブロック６２、および変数−チェック演算器ブロック３２の基本的な構成はそれぞれ第１の実施の形態で示した図７および図４とそれぞれ同様であるが、チェック−変数レジスタブロック５１における各レジスタ６１のビット幅を削減し、復号装置全体の装置規模を削減することができる。
【０１７７】
以上に述べたように、（式３３）を採用すれば、μ（ｓ，ｔ）の選択によって、計算精度と装置規模とのトレードオフにおいて、計算精度と装置規模とのバランスを、３種類（第１の実施の形態のようにμ（ｓ，ｔ）を用いるか、第２の実施の形態のようにμ’（ｉ，ｊ）を用いるか、または、μを用いないか）から選択することができる。
【実施例１】
【０１７８】
図１２は、本発明の復号装置１２８を使用したデータ通信（蓄積）装置の一構成例を示すブロック図である。
【０１７９】
データ通信（蓄積）装置は、データ送信装置１２１とデータ受信装置（受信装置）１２５とを含む。そして、データ送信装置１２１は、擬似巡回型低密度パリティ検査符号の符号化装置１２２、フレーム同期をとるための制御と、変調器１２４に合わせたデータへ変換するための同期制御・データ変換装置（同期制御−データ変換装置）１２３、および変調器１２４を含む。変調器１２４は、通信路、または記憶装置に情報を出力する。
【０１８０】
データ受信装置１２５は、通信路、または記憶装置から受信した情報を復調する復調器１２６、復調器１２６の出力データを復号装置１２６の入力データに変換し、フレーム同期をとる処理を行う同期制御・データ変換装置１２７、および本発明の復号装置１２８を含む。
【０１８１】
数値例として検査行列の列ブロックの総数ｎを６５、検査行列の行ブロックの総数ｍを８、巡回行列のサイズａを６３とした時、フレーム長が４０９５ビットのビット列をフレーム単位とすることができる。
【０１８２】
そして、（式２）で示した検査行列中の各ブロックの行ベクトル（ｆ０（ｉ，ｊ），ｆ１（ｉ，ｊ），・・・，ｆａ−１（ｉ，ｊ），）の重みが１以下であって（ｉは０から７の間の整数を表し、ｊは０から６４の間の整数を表している）、６５個の変数−チェックレジスタブロック２１がそれぞれ含む複数のレジスタ３１のうち、１組のレジスタ３１間に設置される変数−チェック演算器ブロック３２の数を２以下とする。そして、８個のチェック−変数レジスタブロック５１がそれぞれ含む複数のレジスタ６１のうち、１組のレジスタ６１間に設置されるチェック−変数演算器ブロック６２の数を２以下とするように設定する。
【０１８３】
すると、数百キロゲートの装置規模で、数百メガビット毎秒の処理を実現することができる。
【産業上の利用可能性】
【０１８４】
本発明は、衛星通信や移動体通信システム等における所要電力の低減や、アンテナの小型化などのシステム構成上の要件を満たすための誤り訂正技術として利用することができる。また、磁気記録などの記憶装置に関する信頼性向上のための誤り訂正技術として利用することができる。
【図面の簡単な説明】
【０１８５】
【図１】本発明による復号装置の第１の実施の形態の一構成例を示すブロック図である。
【図２】変数−チェックメッセージ生成部の一構成例を示すブロック図である。
【図３】変数−チェックレジスタブロックの一構成例を示すブロック図である。
【図４】変数−チェック演算器ブロックの一構成例を示すブロック図である。
【図５】チェック−変数メッセージ生成部の一構成例を示すブロック図である。
【図６】チェック−変数レジスタブロックの一構成例を示すブロック図である。
【図７】チェック−変数演算器ブロックの一構成例を示すブロック図である。
【図８】復号装置全体の動作を示す説明図である。
【図９】ＲＡＭを用いた低密度パリティ検査符号の復号装置の一構成例を示すブロック図である。
【図１０】簡単化した変数−チェック演算器ブロックの一構成例を示すブロック図である。
【図１１】簡単化したチェック−変数演算器ブロックの一構成例を示すブロック図である。
【図１２】本発明の復号装置を使用したデータ通信（蓄積）装置の一構成例を示すブロック図である。
【符号の説明】
【０１８６】
１１  変数−チェックメッセージ生成部
１２  チェック−変数メッセージ生成部
１３  正規化演算部
２１  変数−チェックレジスタブロック
２２、５２  カウンタブロック
２３、４１、１０１  加算器
３１、６１  レジスタ
３２  変数−チェック演算器ブロック
３３、６３  結線スイッチ
３４、６４  出力スイッチ
４２、１０２  正負反転装置
４３、７３、７４、１１３  セレクタ
４４、７１、７２、１１１、１１２  比較器
４５、７５、１０３、１１４  ＸＯＲゲート
５１  チェック−変数レジスタブロック
６２  チェック−変数演算器ブロック
８１  変数ノード処理装置
８２  アドレス生成制御装置
８３  チェックノード処理装置
８４  メッセージメモリブロック
１２１  データ送信装置
１２２  符号化装置
１２３、１２７  同期制御・データ変換装置
１２４  変調器
１２５  データ受信装置
１２６  復調器
１２８  復号装置
【図１】
2007089064.tif 000036
【図２】
2007089064.tif 000037
【図３】
2007089064.tif 000038
【図４】
2007089064.tif 000039
【図５】
2007089064.tif 000040
【図６】
2007089064.tif 000041
【図７】
2007089064.tif 000042
【図８】
2007089064.tif 000043
【図９】
2007089064.tif 000044
【図１０】
2007089064.tif 000045
【図１１】
2007089064.tif 000046
【図１２】
2007089064.tif 000047