(57)【特許請求の範囲】
【請求項１】
誤り訂正符号化方式における擬似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置であって、
送信ビット列の推定情報を少なくとも記憶する情報記憶装置と、
ループ状に結線された複数のレジスタからなるフィードバックレジスタを含み、前記推定情報を入力し、入力された前記推定情報を更新するためのメッセージを生成して出力する二組のフィードバックシフトレジスタ型のチェックノード処理装置と、
二組の前記チェックノード処理装置のうち前記推定情報を入力する一方を選択するためのマルチプレクサと、
二組の前記チェックノード処理装置のうち前記メッセージを出力する一方を選択するためのデマルチプレクサと、
前記デマルチプレクサによって選択された前記チェックノード処理装置から出力されたメッセージから前記推定情報を更新し、更新された前記推定情報を出力する加算回路と、を備え、
前記チェックノード処理装置は、前記推定情報を並べ替えるための置換回路と、前記チェックノード処理装置が有する前記レジスタに保存されたデータのうちの二つと前記推定情報が出力したデータとのうち、値が最も小さいデータと２番目に小さいデータと、を選択して次の段のレジスタに保存する比較回路と、を含み、
前記比較回路は、前記チェックノード処理装置が有する前記レジスタ間にそれぞれ設置されることを特徴とする復号装置。
【請求項２】
前記推定情報の更新履歴を記憶する履歴記憶装置を、さらに有し、
前記加算回路は、前記デマルチプレクサによって選択された前記チェックノード処理装置から出力されたメッセージと前記更新履歴から前記推定情報を更新し、更新された前記推定情報を出力し、
前記チェックノード処理装置から出力されるメッセージは前記更新履歴として前記履歴記憶装置に一時記憶されることを特徴とする請求項１に記載の復号装置。
【請求項３】
前記チェックノード処理装置は、擬似巡回型低密度パリティ検査符号の検査行列を構成する成分の巡回行列のサイズと同数の前記レジスタを有することを特徴とする請求項１，２の内いずれか１項に記載の復号装置。
【請求項４】
二つの前記チェックノード処理装置の内、一方をチェックノード処理装置Ｌ，他方をチェックノード処理装置Ｒとする時、前記送信ビット列の推定情報の入力を選択する前記マルチプレクサが前記チェックノード処理装置Ｌを選択した場合には、前記メッセージの出力する前記デマルチプレクサは前記チェックノード処理装置Ｒを選択し、前記マルチプレクサが前記チェックノード処理装置Ｒを選択した場合には、前記デマルチプレクサは前記チェックノード処理装置Ｌを選択することを特徴とする請求項３に記載の復号装置。
【請求項５】
請求項１，２，３，４の内いずれか１項に記載の復号装置を有することを特徴とするデータ通信装置。
【請求項６】
請求項１，２，３，４の内いずれか１項に記載の復号装置を有することを特徴とするデータ記憶装置。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願についての記載）
本発明は、日本国特許出願：特願２００８−２８６４５８号（２００８年１１月  ７日出願）の優先権主張に基づくものであり、同出願の全記載内容は引用をもって本書に組み込み記載されているものとする。
本発明は、誤り訂正符号化方式における擬似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置に関し、特に、情報系列を一定長のブロックに分割し、ブロック毎独立に冗長系列を付加するブロック誤り訂正の復号方式及びその回路であって、特に擬似巡回型（Ｑｕａｓｉ−Ｃｙｃｌｉｃ）低密度パリティ検査（Ｌｏｗ−Ｄｅｎｓｉｔｙ−Ｐａｒｉｔｙ−Ｃｈｅｃｋ）符号の復号装置に関する。
【背景技術】
【０００２】
現在、衛星通信、あるいは移動体通信システム等においては、所要電力の低減、アンテナの小型化などのシステム構成上の要件を満たすため、大きな符号化利得を有する誤り訂正符号化技術の導入が行われている。【０００３】
低密度パリティ検査符号は、非常に大きな符号化利得を有する誤り訂正符号として知られており、上記の各種通信システム、および、磁気記録などの記憶装置への導入が進んでいる。【０００４】
低密度パリティ検査符号は、単に一つの誤り訂正符号化方式を示すのではなく、検査行列が疎である（行列中の成分のほとんどが0であり、1である成分の数が非常に少ない）という特徴をもった誤り訂正符号の総称である。【０００５】
疎な検査行列の選択によって、サム・プロダクト（ｓｕｍ−ｐｒｏｄｕｃｔ）アルゴリズム、ミン・サム（ｍｉｎ−ｓｕｍ）アルゴリズムなどの繰り返し復号方式を用いることにより、理論限界に近い非常に大きな符号化利得を持つ誤り訂正符号化方式を構成することが可能であるという特徴をもっている（例えば、非特許文献１，２参照）。【０００６】
低密度パリティ検査符号の復号方式に関連する技術的問題点として、復号処理の過程で一時的に生じる中間データの保持用に多くのランダムアクセスメモリ（ＲＡＭ）を必要とする点が挙げられる。【０００７】
復号処理においては上記中間データを繰り返し更新し、十分な回数まで繰り返した後に上記中間データから算出されるデータの正負によって送信データを判定する。上記中間データの更新処理は、検査行列の各行ベクトル毎に行ベクトルのハミング重みと同数の上記中間データを使用するため、高速処理のためには、同時に多くのデータを参照する必要があり、そのため多くの数のランダムアクセスメモリー(ＲＡＭ)を使用し、中間データを分割して保持する必要がある。【０００８】
特に、高符号化率の低密度パリティ検査符号においては行ベクトルのハミング重みが大きくなるため、その分多くのＲＡＭを必要とする。また、各ＲＡＭのサイズは使用する符号の検査行列によって定まり、復号装置が実装されるデバイスで用意されるＲＡＭのサイズに必ずしも一致しないため、ＲＡＭ数の増加は必要となる記憶容量の増加につながる場合もある。【０００９】
低密度パリティ検査符号の復号装置に関する従来技術の一実施例について説明する（非特許文献３を参照）。以下では行列Ｈを［数式１］に示すように、ｒ行ｎ列で（ｎは1より大きい整数、ｒはｎよりも小さな正の整数）、各成分がｍ×ｍの巡回置換行列、あるいは零行列からなるブロック行列とする（ｍは正数）。【００１０】
【数１】
0005488472.tif 000002
［数式１］においてＩｉ，ｊはｍ×ｍの巡回置換行列あるいは零行列を表すが（ｉは０からｒ−１の間の整数、ｊは０からｎ−１の間の整数）、以下では説明を簡単にするため、Ｉｉ，ｊはｍ×ｍの巡回置換行列を表すとする。【００１１】
ある成分（ｉ，ｊ）において、Ｉｉ，ｊが零行列となる場合も基本的な動作は同様である。［数式１］の行列Ｈを検査行列とした低密度パリティ検査符号は特に擬似巡回型低密度パリティ検査符号と呼ばれている。【００１２】
図７は擬似巡回型低密度パリティ検査符号に関する従来技術による復号装置のブロック図を表す。図７の復号装置はメッセージと呼ばれる復号処理の過程で生じる中間データを保持するためのメモリ群に加え、上記メッセージを更新するためのチェックノード処理回路と加算装置、および、遅延回路からなる。【００１３】
擬似巡回型低密度パリティ検査符号によって符号化されたデータは通信路を経由し、復号装置の入力Ｆ0，Ｆ1，…，ＦＮ−1となる（Ｎ＝ｍｎ）。後述するようにメモリにて保持、および、更新される各データの正負を示すビット列が復号結果として復号装置から出力される。【００１４】
従来技術による復号方法、および、装置図７について説明する。図７(ｂ)は図７(ａ)に示した復号装置における処理を並列化（並列数＝２）したもので、原理的には図７(ａ)と同等のものである。以下では主に図７(ａ)について説明する。【００１５】
図７(ａ)中のメモリ（０）、メモリ（１）、…、メモリ（ｎ―１）の各々にはｍ個のデータが保持されており、合計ｍｎ個のデータＺ0，Ｚ1，…，ＺＮ−1が保持されている。上記データＺ0，Ｚ1，…，ＺＮ−1の初期値は復号装置への入力データ（通信路の出力データ）Ｆ0，Ｆ1，…，ＦＮ−1であり、以下に示す復号処理の過程で逐次更新される。【００１６】
上記データＺｕは（ｕは０からＮ−１の間の整数）、［数式２］に示すように、図７(ａ)中の下段にあるメモリ（Ｌ）に保持されたデータＬｕ←ｖによって減算されて（ｖは０からＲ−１の間の整数であり、Ｒ＝ｍｒ）、データＺｕ→ｖを得る。【００１７】
【数２】
0005488472.tif 000003
上記データＺｕ←ｖは遅延回路に入力されると共に、チェックノード処理回路に入力される。チェックノード処理回路では以下の［数式３］に示す処理を行う。【００１８】
なお、［数式３］においてＢ（ｖ）は検査行列の第ｖ行ベクトル中の成分が１となる位置を示す。また、ｓｇｎ（Ｚ）はＺの値が負の時、ｓｇｎ（Ｚ）＝−１、そうでない時ｓｇｎ（Ｚ）＝＋１とする。【００１９】
【数３】
0005488472.tif 000004
［数式３］によって算出されたＬ’ｕ←ｖは上記データＬｕ←ｖの更新結果であり、図７中の下段にある上記メモリ（Ｌ）に保持される。低密度パリティ検査符号の復号処理においては中心的役割を果たすのは［数式３］に示したチェックノード処理である。【００２０】
Ｌｖ（１），Ｌｖ（２）を各々集合｛｜Ｚｕ→ｖ｜｜ｕ∈Ｂ(ｖ)｝の最小値と２番目に小さい値とし、Ｌｖ（１）＝｜Ｚｕ→ｖ｜となるＢ(ｖ)の元ｕをｕminとする。また、Ｚｕ→ｖが負の値である時、ｑｕ→ｖ＝１、そうでない時ｑｕ→ｖ＝０とすると、［数式３］のデータＬ’ｕ←ｖは次の［数式４］ように記述することが出来る。【００２１】
【数４】
0005488472.tif 000005
なお、［数式４］においてｓｖ＝Σｕ∈Ｂ(ｖ)ｑｕ→ｖとする。【００２２】
図８は図７中にあるチェックノード処理回路７−２の構成の一例を表すブロック図である。上記集合Ｂ(ｖ)の全ての元ｕに関して、Ｚｕ→ｖを入力する。データＺｕ→ｖは量子化されており、最上位ビットが正負、残りの下位ビットが絶対値を表す。【００２３】
これらの最上位ビットと下位ビットは分離され、上位ビットは［数式４］における符号（正負）の算出、下位ビットは第一及び第二最小値の算出装置に入力され、［数式４］に示したデータＬ’ｕ←ｖを得る。【００２４】
上記データＬ’ｕ←ｖは［数式５］に示すように、図７の遅延回路７−４を通して得られる前述のデータＺｕ→ｖに加算され、加算結果Ｚｕは、図７の上記メモリ７−１の同一箇所に保持される。【００２５】
【数５】
0005488472.tif 000006
以下ｖ＝０，１，…，Ｒ−１の順に上記の処理を行うことによって、メモリ中のデータが更新される。【００２６】
以上が繰り返し復号における一回の復号処理に相当する。前述のように変数ｖは検査行列の第ｖ行ベクトルを示しており、すべての行ベクトルについて一通り処理を実行することで一回の復号処理が終了する。これを十分な回数まで繰り返した後、Ｚｕの数値が負の数ならば受信データＦｕの復号結果を1とし、そうでない場合には０として復号処理を終了する。【００２７】
上記のように、低密度パリティ検査符号の復号処理においては、送信ビット列の推定情報であるデータＺｕを記憶するための記憶装置と、送信ビット列の推定情報であるデータＺｕの更新履歴に相当する情報であるデータＬｕ→ｖを記憶するための記憶装置が必要である。【００２８】
復号処理を効率的に行うためには、各ｖ（＝０，１，…，Ｒ−１）ごとに集合Ｂ（ｖ）の全ての元ｕについてデータＺｕを用意し、チェックノード処理回路へ入力する必要がある。【００２９】
このため、データＺｕを例えば、単一のメモリの一アドレスに保持した場合にはチェックノード処理回路への入力を用意するためにＢ(ｖ)の元と同じ数の回数分だけメモリへアクセスする必要があり、［数式４］（あるいは［数式３］）の演算を開始するまでにタイムラグが生じる、また、アドレス生成が複雑となる等の課題が生じる。【００３０】
一方データＺｕを単一のメモリではなく複数に分割されたメモリ中の一アドレスに保持した場合には上記タイムラグの課題は解消できる。［数式１］の検査行列を持つ擬似巡回型低密度パリティ検査符号の場合には、図７（ａ）に記したようにｎ個のメモリを用意し、メモリ（ｊ）の第ｋアドレスにデータＺｊｍ＋ｋを保持することで（ｊは０からｎ−１の間の整数、ｋは０からｍ−１の間の整数）、各メモリへ一度アクセスすることでチェックノード処理回路への入力に必要なデータを揃えることが可能となる。しかし、この場合、多数のＲＡＭを使用する必要があるという課題が生じる。【００３１】
ランダムアクセスが可能な記憶装置数の削減に関して、従来技術を表す図７中の下段のメモリ（Ｌ）を除去し、［数式２］においてデータＬｕ←ｖによる減算を省略した方法がある（非特許文献４を参照）。【００３２】
この技術による復号装置のブロック図を図９に示す。これは回路規模の削減に効果的であるものの、依然としてデータＺｕの保持に多くのランダム・アクセス・メモリを使用するのに加えて、データＬｕ←ｖによる減算を行わないことにより、復号装置の出力にビットエラーが残留し、復号特性が劣化する場合が見られる等の問題が生じる。【００３３】
また、ＲＡＭの使用を避け、シフトレジスタを多用して構成が単純で高速処理可能とする解決策については符号の長さＮが数千ビット以上の場合、あるいは冗長ビット数が多く符号化率が著しく小さい場合には回路規模が大きくなるという課題がある（例えば、特許文献１参照）。
【先行技術文献】
【特許文献】
【００３４】
【特許文献１】特開２００７−８９０６４号公報
【非特許文献】
【００３５】
【非特許文献１】「ロー・デンシティ  パリティ・チェック  コーズ（Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｃｏｄｅｓ）」、ロバート  ギャラガ（Ｒｏｂｅｒｔ  Ｇａｌｌａｇｅｒ）著、アイトリプルイー  トランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ）出版、ＰＰ．２１−２８、１９６２年１月
【非特許文献２】「グット  エラー・コレクティング  コーズ  ベースト  オン  ベリー  スパース  メトリシィーズ（Ｇｏｏｄ  Ｅｒｒｏｒ−Ｃｏｒｒｅｃｔｉｎｇ  Ｃｏｄｅｓ  Ｂａｓｅｄ  ｏｎ  ｖｅｒｙ  ｓｐａｒｓｅ  ｍａｔｒｉｃｅｓ）」、ディー・ジェー・シー  マッカイ（Ｄ．Ｊ．Ｃ．  ＭａｃＫａｙ）著、アイトリプルイー  トランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ）出版、ＰＰ．３９９−４３１、１９９９年３月
【非特許文献３】「エフィシェント  シリアル  メッセージ・パッシング  スケジュール  フォー  エル・ディー・ピー・シー  デコーディング（Ｅｆｆｉｃｉｅｎｔ  Ｓｅｒｉａｌ  Ｍｅｓｓａｇｅ−Ｐａｓｓｉｎｇ  Ｓｃｈｅｄｕｌｅ  ｆｏｒ  ＬＤＰＣ  Ｄｅｃｏｄｉｎｇ）」、エラン・シャロン（Ｅｒａｎ Ｓｈａｒｏｎ）、シモン・リシン（Ｓｉｍｏｎ Ｌｉｔｓｙｎ）、ヤコブ・ゴールドバーガー（Ｊａｃｏｂ Ｇｏｌｄｂｅｒｇｅｒ）共著、アイトリプルイー  トランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔｒａｎｓａｃｔｉｏｎｓ  ｏｎ  Ｉｎｆｏｒｍａｔｉｏｎ  Ｔｈｅｏｒｙ）出版、ＰＰ．４０７６−４０９１、２００７年１１月
【非特許文献４】「ハイ  スループット  ロー・デンシティ  パリティ・チェック  デコーダー  アーキテクチャ（Ｈｉｇｈ  Ｔｈｒｏｕｇｈｐｕｔ  Ｌｏｗ−Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ−Ｃｈｅｃｋ  Ｄｅｃｏｄｅｒ  Ａｒｃｈｉｔｅｃｔｕｒｅ）」、イー・イェオ（Ｅ  Ｙｅｏ）、ピー・パザド（Ｐ．Ｐａｋｚａｄ）、ビー・ニコリック（Ｂ．Ｎｉｋｏｌｉｃ）、ヴィー・アナンタラン（Ｖ  Ａｎａｎｔｈａｒａｍ）共著、２００１  アイトリプルイー  グローバル  テレコミュニケーションズ  コンファレンス（２００１  ＩＥＥＥ  Ｇｌｏｂａｌ  Ｔｅｌｅｃｏｍｍｕｎｉｃａｔｉｏｎｓ  Ｃｏｎｆｅｒｅｎｃｅ）発行、ＰＰ．３０１９−３０２４、２００１年１１月
【発明の概要】
【発明が解決しようとする課題】
【００３６】
上記特許文献１、及び非特許文献１〜４の全開示内容はその引用をもって本書に繰込み記載する。
以下の分析は、本発明の観点から与えられる。
低密度パリティ検査符号に関する従来の復号装置においては、復号処理の演算中に生じる中間データを保持／更新する必要があり、更に一つの処理に多くの中間データを参照する必要があるため、中間データを多数のランダムアクセスが可能な記憶装置に分割して保持する必要がある点が問題となる。【００３７】
各記憶装置に要求されるサイズは使用する符号の検査行列によって定まり、デコーダーが実装されるデバイスで用意される記憶装置（ランダム・アクセス・メモリ；ＲＡＭ）のサイズに必ずしも一致しない場合があるため、この多数の記憶装置が必要となる問題点は記憶容量の増加にもつながる。【００３８】
上記中間データを単純に一つ（あるいは少数）の記憶装置にまとめて保持する場合には、復号処理の核であるチェックノード処理に必要な中間データを集めるために複数回にわたって記憶装置からの読込みを行う必要が生じ（更新された中間データを記憶装置に書き込む場合も同様）、これによって復号処理時間及び遅延時間の増加、処理速度の低下を招く。【００３９】
特に高符号化率の低密度パリティ検査符号においては、行ベクトルのハミング重みが大きく、一度の処理に参照が必要な中間データの量が多いため、復号処理・遅延時間の増加は顕著となり、本質的な問題の解決には至らない。【００４０】
本発明は、上記の点に鑑みなされたもので、擬似巡回型低密度パリティ検査符号において、復号処理時間・遅延時間の大幅な増加を伴うことなく必要なランダムアクセスメモリ（ＲＡＭ）の数を大幅に削減可能な復号装置を提供するものである。
【課題を解決するための手段】
【００４１】
本発明の復号装置は、誤り訂正符号化方式における擬似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置であって、送信ビット列の推定情報を少なくとも記憶する情報記憶装置と、ループ状に結線された複数のレジスタからなるフィードバックレジスタを含み、推定情報を入力し、入力された推定情報を更新するためのメッセージを生成して出力する二組のフィードバックシフトレジスタ型のチェックノード処理装置と、二組のチェックノード処理装置のうち推定情報を入力する一方を選択するためのマルチプレクサと、二組のチェックノード処理装置のうちメッセージを出力する一方を選択するためのデマルチプレクサと、デマルチプレクサによって選択されたチェックノード処理装置から出力されたメッセージから推定情報を更新し、更新された推定情報を出力する加算回路と、を備え、チェックノード処理装置は、推定情報を並べ替えるための置換回路と、チェックノード処理装置が有するレジスタに保存されたデータのうちの二つと推定情報が出力したデータとのうち、値が最も小さいデータと２番目に小さいデータと、を選択して次の段のレジスタに保存する比較回路と、を含み、比較回路は、チェックノード処理装置が有するレジスタ間にそれぞれ設置される。
【発明の効果】
【００４２】
本発明によれば、［数式１］に示した検査行列Ｈの列ベクトル毎に生成される合計Ｎ＝ｍｎ個のデータＺ0，Ｚ1，…，ＺＮ−1を保持するためのｎ個のメモリとｎ個の入力データの比較処理からなるチェックノード処理装置を有することなく、一つ（あるいはデバイスの要請に合わせて小数個）のＲＡＭなどの記憶装置を有し、複数のレジスタと二つの２入力比較処理からなる比較回路をループ状に結線したフィードバックシフトレジスタ型のチェックノード処理装置を持つ構成としている。このため、処理速度／遅延時間／回路規模の増大を伴うことなく、使用する記憶装置の数を大幅に削減した復号装置構成が可能となる。本発明によって、復号装置における記憶容量／回路規模の削減、および、復号処理動作時における消費電力の低下等の効果がある。
【図面の簡単な説明】
【００４３】
【図１】本発明の実施の形態の復号装置を示すブロック図である。
【図２】図１中のチェックノード処理装置の一例を示すブロック図である。
【図３】図２中の比較回路の一例を示すブロック図である。
【図４】並列化されたチェックノード処理装置の一例を示すブロック図である。
【図５】図２中の加算回路の一例を示すブロック図である。
【図６】一部のメモリを削除した本発明技術による復号装置の一実施例を示すブロック図である。
【図７】従来技術における復号装置の一例を示すブロック図である。
【図８】従来技術におけるチェックノード処理装置を示すブロック図である。
【図９】一部のメモリを削除した従来技術による復号装置の一実施例を示すブロック図である。
【図１０】従来技術による復号処理例を示す模式図である。
【図１１】本発明技術による復号処理例を示す模式図である。
【図１２】メモリ１−１の初期状態の一例を示す模式図である。
【図１３】復号処理の動作の一例を示すタイムチャートである。
【図１４】本発明の復号装置を使用したデータ通信・記憶装置の一例を示すブロック図である。
【発明を実施するための形態】
【００４４】
本発明の実施形態に係る復号装置は、誤り訂正符号化方式における擬似巡回型低密度パリティ検査符号を復号し、復号結果である推定送信ビット列を出力する復号装置であって、送信ビット列の推定情報を少なくとも記憶する情報記憶装置と、ループ状に結線された複数のレジスタからなるフィードバックレジスタを含み、推定情報を入力し、入力された推定情報を更新するためのメッセージを生成して出力する二組のフィードバックシフトレジスタ型のチェックノード処理装置と、二組のチェックノード処理装置のうち推定情報を入力する一方を選択するためのマルチプレクサと、二組のチェックノード処理装置のうちメッセージを出力する一方を選択するためのデマルチプレクサと、デマルチプレクサによって選択されたチェックノード処理装置から出力されたメッセージから推定情報を更新し、更新された推定情報を出力する加算回路と、を備え、チェックノード処理装置は、推定情報を並べ替えるための置換回路と、チェックノード処理装置が有するレジスタに保存されたデータのうちの二つと推定情報が出力したデータとのうち、値が最も小さいデータと２番目に小さいデータと、を選択して次の段のレジスタに保存する比較回路と、を含み、比較回路は、チェックノード処理装置が有するレジスタ間にそれぞれ設置される。
【００４５】
本発明の復号装置において、推定情報の更新履歴を記憶する履歴記憶装置を、さらに有し、加算回路は、デマルチプレクサによって選択されたチェックノード処理装置から出力されたメッセージと更新履歴から推定情報を更新し、更新された推定情報を出力し、チェックノード処理装置から出力されるメッセージは更新履歴として履歴記憶装置に一時記憶されてもよい。
【００４６】
本発明の復号装置において、チェックノード処理装置は、擬似巡回型低密度パリティ検査符号の検査行列を構成する成分の巡回行列のサイズと同数のレジスタを有するようにしてもよい。
【００４７】
本発明の復号装置において、二つのチェックノード処理装置の内、一方をチェックノード処理装置Ｌ，他方をチェックノード処理装置Ｒとする時、送信ビット列の推定情報の入力を選択するマルチプレクサがチェックノード処理装置Ｌを選択した場合には、メッセージの出力するデマルチプレクサはチェックノード処理装置Ｒを選択し、マルチプレクサがチェックノード処理装置Ｒを選択した場合には、デマルチプレクサはチェックノード処理装置Ｌを選択するようにしてもよい。
【００４８】
本発明の復号装置において、送信ビット列の推定情報を記憶するすべての情報記憶装置は、情報記憶装置からの読出しの動作クロックに同期して動作し、値が予め設定した正数になるごとに０にリセットするクロックカウンタを含み、クロックカウンタがカウントした値に一致するアドレスを読出しアドレスし、マルチプレクサ、および、デマルチプレクサの切り替えをクロックカウンタがカウントした値によるアドレス生成が一巡した段階で行うようにしてもよい。
【００４９】
本発明のデータ通信装置は、上記の復号装置を有するようにしてもよい。
【００５０】
本発明のデータ記憶装置は、上記の復号装置を有するようにしてもよい。
【００５１】
なお、本発明の各種の構成要素は、その機能を実現するように形成されていればよく、例えば、所定の機能を発揮する専用のハードウェア、所定の機能がコンピュータプログラムにより付与されたデータ処理装置、コンピュータプログラムによりデータ処理装置に実現された所定の機能、これらの任意の組み合わせ、等として実現することができる。
【００５２】
また、本発明の各種の構成要素は、必ずしも個々に独立した存在である必要はなく、複数の構成要素が一個の部材として形成されていること、一つの構成要素が複数の部材で形成されていること、ある構成要素が他の構成要素の一部であること、ある構成要素の一部と他の構成要素の一部とが重複していること、等でもよい。
本発明の実施の一形態を図面を参照して以下に説明する。
【００５３】
［構成の説明］
本実施の形態の復号装置全体の構成を図１のブロック図に示す。本実施の形態の復号装置は、［数式１］の検査行列を持つ擬似巡回型低密度パリティ検査符号の復号装置であり、図１に示すように、二組の記憶装置であるメモリ１−１，１−３と二つのフィードバックシフトレジスタ（ＦＳＲ）型のチェックノード処理装置１−２Ａ，１−２Ｂを備え、上記二つのチェックノード処理装置１−２Ａ，１−２Ｂを切り替えるためのマルチプレクサ１−４、デマルチプレクサ１−５、加算回路１−６、および、アドレス生成装置１−７，１−８からなる。
【００５４】
通信路の出力である受信データ列をＦ0，Ｆ1，…，ＦＮ−1と記し、受信データ列を構成する各シンボルＦｉがｂ´ビットで表現されているとすると（ｉは０からＮ−１の間の整数、ｂ´は正数）、メモリ１−１は最大で（ｂ＋ｒ）Ｎビットの記憶容量を必要とする（ｂはｂ´以上の正数）。
【００５５】
メモリ１−１は主として送信ビット列の推定情報を記憶する情報記憶装置である。また、図１のメモリ（Ｌ）１−３は最大で（２ｂ−１＋ｌｏｇ２ｎ）ｍｒビットの記憶容量を必要とする（ｌｏｇ２ｎ部分は小数点以下切り上げ）。メモリ（Ｌ）１−３は送信ビット列の推定情報の更新履歴を記憶する履歴記憶装置である。
【００５６】
図２は図１中に示したＦＳＲ型のチェックノード処理装置１−２Ａ，１−２Ｂに関する一実施例のブロック図を表す。チェックノード処理装置は、図２に示すように、ｍ個のレジスタ２−１と、比較回路２−２、および、二つの置換回路２−３，２−４、からなる。
【００５７】
各レジスタのビットサイズは最大（２ｂ−１＋ｌｏｇ２ｎ）ビットであり、内訳は上記［数式４］中のＬｖ（１）、Ｌｖ（２）に相当する二つのデータ（各ｂ−１ビット）、［数式４］中のuminに相当する最大ｌｏｇ２ｎビットのポインタ、および、［数式４］中のｓｖに相当する１ビットである。
【００５８】
チェックノード処理装置にはｎｍ個の各ｂビットからなるデータがｎ個並列にｍ単位時間にわたって入力される。その間レジスタのデータが逐次更新され、入力が終了した時点でレジスタに保持されているデータが順次出力される。
【００５９】
置換回路２−３は、入力データを分割して並べ替え、レジスタ間に配置された各比較回路へデータを振り分ける装置であり、並べ替え、振り分けの方法は検査行列［数式１］の成分である巡回置換行列の選択に依存して次に記すように決定する。便宜上、図２中のｍ個のレジスタを右から左に向かって０，１，２，…，ｍ−１と記し、また、上記ｎ個の入力を０，１，２，…，ｎ−１と記して区別する。
【００６０】
検査行列の第ｉ行ブロックは（Ｉｉ，０，Ｉｉ，１，…，Ｉｉ，ｎ−１）であり（ｉは０からｒ−１の間の整数）、ｍ×ｍ巡回置換行列Ｉｉ，ｊにおける第０行ベクトルの唯一の非零成分位置をｈｉ，ｊとする時（ｊは０からｎ−１の間の整数、ｈｉ，ｊは０からｍ−１の間の整数）、入力側の置換回路２−３は入力ｊ（ｊは０からｎ−１の間の整数）をレジスタｍ−ｈｉ，ｊとレジスタｍ−ｈｉ，ｊ−１の間に位置する比較回路に入力する様に結線する。置換回路２−４は出力側であるが、結線の方法は入力側の置換回路２−３と同様である。
【００６１】
図３の比較回路は、二つの入力データの数値の大小を比較し、その内数値の小さい方を出力する比較器３−１、出力を選択するためのマルチプレクサ３−２、ポインタ更新回路３−３、入力データの最上位ビットとそれ以外の下位ビットを分離する装置３−４、および、排他的論理和回路３−５からなる。
【００６２】
また、図２のチェックノード処理装置に利用される比較回路は、図３に示した入力データ（Ｌ（１），Ｌ（２），ｕｍｉｎ，ｓ）をそのまま出力する機能も備えている。これは単に上記入力データと図３の出力データをマルチプレクサで選択することで実現できるため、図中での記述は省略した。図中のデータ（Ｌ（１），Ｌ（２），ｕｍｉｎ，ｓ）に関する詳細は後述する。
【００６３】
図４は図２のチェックノード処理装置を２重に並列化した装置に関する一実施例のブロック図を表す。図２と同様に、レジスタ４−１、図３の比較回路４−２、および、置換回路４−３，４−４からなる。
【００６４】
レジスタの個数は図２と同様ｍ個であるが、比較回路の個数は２倍となる。この場合、ｎｍ個の各ｂビットからなるデータは２ｎ個並列にｍ／２単位時間にわたって入力される。３重以上に並列化した場合については基本的に２重の並列化と同様なので省略する。
【００６５】
図５は図１における加算回路１−６の構成要素に関する一実施例のブロック図を表す。
加算回路１−６は図５の回路が最大ｎ個並列に配置された構成となる。図５の回路は主に加算器５−１とマルチプレクサ５−２，５−３からなり、入力は図中でＬ（１），Ｌ（２），ｕｍｉｎ，ｓ，Ｚ，ｑと記されたデータである。
【００６６】
中でもＬ（１），Ｌ（２），ｕｍｉｎ，ｓの示すデータは図３中のＬ（１），Ｌ（２），ｕｍｉｎ，ｓに対応し、チェックノード処理装置の出力するデータに一致する。次の［数式６］は、上記６個のデータと出力Ｚ´との関係を示している。
【００６７】
【数６】
0005488472.tif 000007
上記データＬ（１），Ｌ（２），ｕｍｉｎ，ｓのビット幅は各々ｂ−１，ｂ−１，ｌｏｇ２ｎ，１ビット（合計２ｂ−１＋ｌｏｇ２ｎビット）であり、Ｚ，ｑは各々ｂ，１ビットである。
【００６８】
なお、入力データｑのビット幅が１ビットよりも大きな場合には、予め定めた手段によって１ビットを選択する。また、［数式６］においてｕは予め定められた定数である。加算回路は［数式４］と［数式５］に示した演算を行う装置といえる。
【００６９】
図６は図１におけるメモリ（Ｌ）１−３を削除した復号装置である。メモリ（Ｌ）１−３を使用しないことにより、必要な記憶容量が削減されると共に加算回路の数を削減することも出来る。一般に、メモリの削除によって誤り率特性が劣化するが、［数式１］の検査行列Ｈの選択によっては誤り率特性（誤り訂正能力）の劣化が極めてわずかな場合がある。
【００７０】
［動作の説明］
図１の復号装置の動作に関する詳細を説明する前に、本発明の復号方式の原理について、例を用い、従来方式との対比で説明する。簡単のため［数式１］の検査行列において、ｒ＝２、ｎ＝ｍ＝３とし、次の［数式７］で表される検査行列を持つ擬似巡回型低密度パリティ検査符号を例として説明する。
【００７１】
【数７】
0005488472.tif 000008
図１０は従来技術による復号処理の流れの概略を示したブロック図である。
【００７２】
本発明による復号処理の流れとの対比を強調し、記述を簡略化するため、細部の記述、および、細部の処理については省略してある。従来技術においては三つのメモリ（メモリ（０）、メモリ（１）、メモリ（２））に中間データを保持し、これらを繰り返し更新する。
【００７３】
メモリ（０）は検査行列の第０〜第２列ベクトル、メモリ（１）は第３〜第５列ベクトル、メモリ（２）は第６〜第８列ベクトルに対応し、第(i)時点において、メモリ（０）からデータＡ０、メモリ（１）からデータＢ１、メモリ（２）からデータＣ２を各々読み出す。
【００７４】
この各メモリからのデータの読み出し順序は検査行列の列ベクトルによって定まる。各列ベクトルにおいて、その成分が１である場所に対応するデータを読み出すことになる。
【００７５】
ここで読み出された三つのデータ（Ａ０，Ｂ１，Ｃ２）はチェックノード処理装置に入力され、（Ａ０＊，Ｂ１＊，Ｃ２＊）と更新されて（更新処理をφと表す）、各メモリに書き込まれる（読み込み時と同一アドレス）。以下同様に、第(ii)時点において、（Ａ１，Ｂ２，Ｃ０）の読み出し／更新／書込み、第(iii)時点において、（Ａ２，Ｂ０，Ｃ１）の読み出し／更新／書込みが行われる。
【００７６】
次いで、第(iv)時点において、第(i)〜第(iii)時点で更新されたデータ（Ａ２＊，Ｂ１＊，Ｃ０＊）を読み出して更新し、以下（Ａ０＊，Ｂ２＊，Ｃ１＊）の読み出し／更新／書込み、（Ａ１＊，Ｂ０＊，Ｃ２＊）を読み出し／更新／書込みを行って、一回の繰り返し処理が終了する。
【００７７】
ここでメモリ数の単純な削減は処理時間の増大を伴う点について説明する。第(iv)時点において、メモリ（０）の第２アドレスにおけるデータとメモリ（１）の第１アドレスのデータ、メモリ（２）の第０アドレスのデータの組合せは第(i)〜第(iii)時点で現れなかった組合せである。
【００７８】
従って、三つのメモリの代わりに、これらを束ねて、例えば、（Ａ０，Ｂ１，Ｃ２）を第０アドレスのデータ、（Ａ１，Ｂ２，Ｃ０）を第１アドレスのデータ、（Ａ２，Ｂ０，Ｃ１）を第２アドレスのデータとした一つのメモリで代替しても、第(iv)時点において、必要なデータを揃えるには３回のメモリアクセスが必要となり、遅延が生じる。
【００７９】
この結果、単純なメモリの合成は処理時間の増大を伴うことになる。本発明はこの点を解決し、上記の（Ａ０，Ｂ０，Ｃ０）を第０アドレスのデータ、（Ａ１，Ｂ１，Ｃ１）を第１アドレスのデータ、（Ａ２，Ｂ２，Ｃ２）を第２アドレスのデータとした一つの代替メモリを使用して処理時間の増大を伴わない復号装置を提供する。
【００８０】
図１１は、［数式６］の検査行列を持つ擬似巡回型低密度パリティ検査符号に関して、本発明による復号処理の流れの概略を示したブロック図である。前述の従来技術による復号処理の流れとの対比を強調し、記述を簡略化するため、細部の記述、および、細部の処理については省略してある。
【００８１】
図１１のブロック図は一つのメモリ、および、三つのレジスタと比較回路（φ）をループ状に結線したチェックノード処理装置からなる。メモリは第０アドレスにデータ（Ａ０，Ｂ０，Ｃ０）、第１アドレスに（Ａ１，Ｂ１，Ｃ１）、第２アドレス（Ａ２，Ｂ２，Ｃ２）を格納するものし、各レジスタの初期値Ｓは比較処理φと任意の入力Ｘに対してφ（Ｓ，Ｘ）＝Ｘとなる様に選択する。
【００８２】
第(i)時点において、メモリからデータ（Ａ０，Ｂ０，Ｃ０）が読み出され、データが３分割されて、Ａ０は右端、Ｃ０は中央、Ｂ０は左端の比較回路φへ入力される。なお、マルチプレクサ（ＭＵＸ）は時点(i)〜(iii)の間、（ａ）側が選択されるとする。
【００８３】
各レジスタは上記のように初期化されており、入力後の各レジスタの保持する値は図中の様に、左からＡ０、Ｂ０、Ｃ０となる。第(ii)時点において、Ａ１は右端、Ｃ１は中央、Ｂ１は左端の比較回路φへ入力され、入力後の各レジスタが保持する値は左からφ（Ｃ０，Ａ１）、φ（Ａ０，Ｂ１）、φ（Ｂ０，Ｃ１）となる。
【００８４】
第(iii)時点においても同様に、Ａ２は右端、Ｃ２は中央、Ｂ２は左端の比較回路φへ入力され、入力後の各レジスタが保持する値は左からφ（Ｂ０，Ｃ１，Ａ２）、φ（Ｃ０，Ａ１，Ｂ２）、φ（Ａ０，Ｂ１，Ｃ２）となる。なお、比較演算処理φの性質より、任意の入力Ａ，Ｂ，Ｃに対してφ（φ（Ａ，Ｂ），Ｃ）＝φ（Ａ，Ｂ，Ｃ）が成立する。
【００８５】
第(iii)時点終了時に三つのレジスタが保持している値は、図１０に示した時点(i)、(ii)、(iii)における処理結果に一致しており、両者が同じ結果をもたらすことがわかる。第(iv)時点ではレジスタの値を使用してメモリを更新し、各レジスタを初期化した後、時点(iv)、(Ｖ)、(Vi)と同様の手順で処理を続行する。
【００８６】
ここでメモリからのデータ読み出し順序は前述の順序と同じであるが、レジスタへの入力の前段階であるマルチプイレクサは時点(iv)、(Ｖ)、(Vi)の間、（ｂ）側を選択することにする。
【００８７】
なお、上記のように実際には時点(iii)と(iv)の間に各レジスタの値を用いてメモリ内容を更新する処理が必要であり、これを効率的に行うため、後で説明するようにレジスタと比較回路をループ上に結線したチェックノード処理装置を２面用意した図１の構成を採用する。
【００８８】
以上、本発明の基本的な原理を単純な例を用いて説明した。以下では、［数式１］の検査行列を持つ擬似巡回型低密度パリティ検査符号に関する細に本発明の復号装置１の動作について説明する。
【００８９】
復号処理開始時の時点において、通信路の出力である受信データ列Ｆ0，Ｆ1，…，ＦＮ−1が得られているものとし、図１のメモリ１−１、メモリ（Ｌ）１−３は初期化されているとする。
【００９０】
なお、メモリ１−１の構成の一例としてビット幅をｎ（ｂ＋ｒ）ビット、ワード数をｍと設定し、メモリ（Ｌ）１−３の構成の一例としてビット幅を（２ｂ−１＋ｌｏｇ２ｎ）ｍビット、ワード数をｒと設定した場合について説明する。
【００９１】
実装されるデバイスの要請に依存して、各メモリはビット幅方向に関して任意の適当な個数に分割することができる。なお、ビット幅方向に関して任意の適当な個数に分割した場合にも読出し／書込みのアドレスは共有することができる。
【００９２】
メモリ（Ｌ）１−３の初期化は全てのデータを零とすることで行う。メモリ１−１についてはその初期化の一例を図１２に示す。図１２中のデータＦｉのビット幅はｂビット、ｑiはｒビットとする（ｉは０からｎｍ−１の間の整数）。
【００９３】
以下では図１中の二つのチェックノード処理装置を区別するため、便宜上左側のチェックノード処理装置を１−２Ｂ、右側のチェックノード処理装置を１−２Ａと示すことにする。
【００９４】
同様に、図１中の二つの加算回路を区別するため、便宜上左側の加算回路を１−６Ｂ、右側の加算回路を１−６Ａと示すことにする。二つのチェックノード処理装置１−２Ａ，１−２Ｂにおける各レジスタのビット幅は最大（２ｂ−１＋ｌｏｇ２ｎ）ビットであり、その初期値は次のように定める。
【００９５】
チェックノード処理装置１−２Ｂのレジスタの初期値は、[構成の説明]で述べたＬｖ（１）、Ｌｖ（２）に相当するデータ（各ｂ−１ビット）部分を各々ｂ−１ビットで表現される数値の最大値とし、それ以外を零に設定する。
【００９６】
また、チェックノード処理装置１−２Ａにおける各レジスタの初期値はすべて零とする。以下で説明するように復号処理の過程で１−２Ｂ、あるいは１−２Ａの何れか一方のレジスタを初期化することがあるが、この際の初期化方法は、上記１−２Ｂの初期化方法に従う。即ち、レジスタ中のデータを全て零に初期化するのは復号処理開始時における場合１−２Ａのみである。
【００９７】
本実施の形態の図１の復号装置に関する動作の一例を示す図１３のタイムチャートを使って、メモリ１−１に保持されたデータ、および、二つのチェックノード処理装置中のレジスタに保持されたデータの更新処理を中心に説明する。ｔを０からｍ−１の間の整数として、以下に示す処理をＢ（ｔ）、Ｃ（ｔ）と記す。
【００９８】
・ Ｂ（ｔ）：メモリ１−１の第ｔアドレスからｎ個分のデータ（各々ｂ＋ｒビット）を読み出し、このデータとチェックノード処理装置１−２Ａ（あるいは１−２Ｂ）からデマルチプレクサ１−５を介して出力されるｎ個分のデータ（各々２ｂ−１＋ｌｏｇ２ｎビット）を加算回路１−６Ｂに入力する。
【００９９】
また、上記加算回路１−６Ｂの出力とメモリ（Ｌ）１−３の第ｘ（ｔ）アドレスからロードしたデータを加算回路１−６Ａに入力して、上記加算回路１−６Ａの出力結果を得る（ｘ（ｔ）はｔ、および、［数式１］の検査行列Ｈに依存して定まる０〜ｒ−１の間の整数）。
【０１００】
・ Ｃ（ｔ）：加算回路（１―６Ｌ）の出力結果をメモリ１−１の第ｔアドレスに書き込む。また、上記出力結果をマルチプレクサ１−４を介してチェックノード処理装置１−２Ｂ（あるいは１−２Ａ）へ入力し、上記チェックノード処理装置１−２Ｂ（あるいは１−２Ａ）のレジスタに保持されているデータを更新する。
【０１０１】
なお、上記処理Ｂ（ｔ）において、チェックノード処理装置１−２Ａ（あるいは１−２Ｂ）における各レジスタからデータを出力する際、同時に各レジスタ中のデータを右に一つシフトするものとする（右端のレジスタのデータは左端へシフト）。また、メモリ（Ｌ）１−３への書込みについては後述する。
【０１０２】
まず初めに時点ｔ＝０において処理Ｂ（０）を実行する。この時、前述のようにメモリ１−１の第０アドレスからデータを読み込むと共にチェックノード処理装置（図１３中ではFSR-CN処理）１−２Ａの各レジスタの保持するデータを出力、および、シフトする。時点ｔ＝１においては処理Ｂ（１）とＣ（０）を実行する。
【０１０３】
この時、メモリ１−１の第１アドレスからデータを読み込むと共に第０アドレスに上記処理Ｂ（０）において算出されたデータを書き込む。上記データを（Ｗ０，Ｗｍ，…，Ｗ（ｎ−１）ｍ）と示すと書込み後の図１２中の第０アドレスのデータは（Ｗ０，Ｗｍ，…，Ｗ（ｎ−１）ｍ，ｑ０´，ｑｍ´，…，ｑ（ｎ−１）ｍ´）となる。
【０１０４】
ここで、ｑｉｍ´は図１２に記したｒビットデータｑｉｍの予め定められた位置の１ビットをＷｉｍが負の時１とし、それ以外の時０として得られるデータを表す（ｉは０からｎ−１の間の整数）。
【０１０５】
上記データ（Ｗ０，Ｗｍ，…，Ｗ（ｎ−１）ｍ，ｑ０´，ｑｍ´，…，ｑ（ｎ−１）ｍ´）はチェックノード処理装置１−２Ｂに入力され、レジスタの保持するデータは更新される。
【０１０６】
チェックノード処理装置１−２Ａの各レジスタについてはｔ＝０の時と同様に出力、および、シフト処理がなされる。以下時点ｔ＝ｍ−１まで同様の処理を繰り返し行う。
【０１０７】
時点ｔ＝ｍでは、時点ｔ＝ｍ−１で実行した処理Ｂ（ｍ−１）の結果得られたデータをメモリ１−１の第ｍ−１アドレスに書き込む。上記データは同時にチェックノード処理装置１−２Ｂに入力され、レジスタの保持するデータは更新される。
【０１０８】
チェックノード処理装置１−２Ａについては各レジスタを初期化する。前述のように初期化はＬｖ（１）、Ｌｖ（２）に相当するデータ（各ｂ−１ビット）部分を各々ｂ−１ビットで表現される数値の最大値とし、それ以外を零とすることを意味する。時点ｔ＝０から時点ｔ＝ｍまでの上記の処理によって、［数式１］の検査行列Ｈにおける第０行ブロック分の処理が終了したことになる。
【０１０９】
次の時点ｔ＝ｍ＋１においては再び処理Ｂ（０）を実行するが、その際、図１中のマルチプレクサ１−４、デマルチプレクサ１−５を切り替え、チェックノード処理装置１−２Ｂの各レジスタの保持するデータを出力、および、シフトする。
【０１１０】
さらに次の時点ｔ＝ｍ＋２において、Ｂ（０）の算出結果が入力され、レジスタが更新されるのは１−２Ａのチェックノード処理装置となる。このようにチェックノード処理装置には出力／シフトモードと入力／更新モードがあり、この二つのモードを交互に行うことになる。
【０１１１】
即ち、時点０から時点ｍの間においてチェックノード処理装置１−２Ｂは入力／更新モード、１−２Ａは出力／シフトモードであり、時点ｍ＋１から時点２ｍ＋１の間はその逆（チェックノード処理装置１−２Ｂが出力／シフトモード、１−２Ａが入力／更新モード）となる。
【０１１２】
なお、上記二つのモードを切り替える際には、上記マルチプレクサ１−４、デマルチプレクサ１−５の切り替えに加え、チェックノード処理装置の図２の置換回路２−３，２−４の切り替えも行う。
【０１１３】
以下同様に繰り返し、時点ｔ＝ｒ（ｍ＋１）−１で検査行列の全ての行ブロックに関する処理が終了し、これは前述のように、一回の繰り返し処理に相当する。処理Ｂ（０）から処理Ｂ（ｍ−１）が実行される間、上記チェックノード処理装置１−２Ｂのｍ個のレジスタの保持するデータ全体はシフトを繰り返すのみで更新されない。
【０１１４】
上記レジスタの保持するデータはメモリ（Ｌ）１−３にコピーされるが、ｍ単位時間の間、同一データが上記レジスタに保持されているため、メモリ（Ｌ）１−３への書込み方法は、１単位時間で一度に行う、あるいはｍ単位時間かけて順次行う等の自由度がある。
【０１１５】
以上の処理を十分な回数まで繰り返すことで、メモリ１−１のデータが順次更新され、最終的に復号結果を得る。以上示したように、メモリ１−１からの読出し、および、書込みのアドレスは第０アドレス、第１アドレス、第２アドレス…と自然数の順序となっており、このため、例えば、図１のアドレス生成装置１−７は、単にクロックカウンタによって実現できる。
【０１１６】
従ってアドレス生成のための特別な装置を必要としない利点も見出すことができる。図１３のタイムチャートにあるように上記マルチプレクサ１−４とデマルチプレクサ１−５の切り替えは上記メモリ１−１への読出し、書込みのアドレスが一巡した段階で実行する。
【０１１７】
つぎに、図２に一例を示したチェックノード処理装置、および、図３に一例を示した比較回路の動作について説明する。前述のようにチェックノード処理装置には出力／シフトモードと入力／更新モードがあり、図１３のタイムチャートに示したように上記二つのモードをｍ時点周期で切り替える。
【０１１８】
出力／シフトモードは、単に各レジスタに保持されたデータをループ状の結線に従って隣接するレジスタにシフトする処理からなる。この時、レジスタ間に配置された比較回路は（マルチプレクサ側からの入力に依存せず）レジスタからの入力をそのまま出力する。
【０１１９】
入力／更新モードでは、図１のマルチプレクサ１−４からの入力によってレジスタに保持されたデータを更新し、上記データをループ状の結線に従って隣接するレジスタに保持する。
【０１２０】
[構成の説明]において述べたように各レジスタに保持されるデータの構成は（Ｌ（１），Ｌ（２），ｕｍｉｎ，ｓ）であり、これが比較回路への一方の入力となる。ここで、Ｌ（１）とＬ（２）は共に非負の値であり、Ｌ（１）≦Ｌ（２）の大小関係がある。
【０１２１】
マルチプレクサ側からのもう一方の入力をＺとする。図３の比較回路の動作は以下の通りである。入力Ｚを最上位ビットＺＡと上記最上位ビット以外のビットからなるＺＢに分離する。ＺＡはＺの正負を現す１ビットであり、ＺＢはＺの絶対値を表す。
【０１２２】
最上位ビットＺＡはレジスタからの入力ｓと共に排他的論理和回路３−５に入力されて、ｓ´として出力される。一方、ＺＢはＬ（１），Ｌ（２）と共に、図３の比較装置３−１に入力され、三つの非負数ＺＢ，Ｌ（１），Ｌ（２）の中で最も小さい値をＬ（１）´として出力し、上記三つの非負数で２番目に小さい値を小さい値をＬ（２）´として出力する。
【０１２３】
なお、ＺＢのビット幅は最上位ビットＺＡを除いた絶対値部分であるためｂ−１ビットとなり、Ｌ（１），Ｌ（２）のビット幅に一致する。レジスタからのもう一つの入力ｕｍｉｎは、Ｌ（１）が入力ＺＢに置き換えられた時のみ比較回路毎に予め設定された値に更新され、それ以外の場合には何の処理も施さずにｕｍｉｎ´として出力される。
【０１２４】
なお、上記の予め設定された値は、検査行列の列ブロックのいずれかを指し示すポインタであり、［数式１］において検査行列の列ブロック数はｎであるため、ビット数はｌｏｇ２ｎである。
【０１２５】
［発明の他の実施の形態］
図４は[構成の説明]において述べたように、図２のチェックノード処理装置を２重に並列化した装置である。図１の復号装置におけるチェックノード処理装置として図４を使用することにより、図１２で動作の流れを示した復号処理の２単位時間分を１単位時間で行うことができ、復号処理に要する時間を半分にすることができる。但し、この場合[構成の説明]において述べたように比較回路の個数は並列処理数に比例して多くなる。
【０１２６】
図６はメモリ（Ｌ）１−３を削除した本発明による復号装置の一実施例を示したブロック図である。図１の本発明による復号装置と比較してメモリ（Ｌ）１−３の削除以外に加算回路も一つ削減されている。図６に示すように、チェックノード処理装置６−２、マルチプレクサ６−３、デマルチプレクサ６−４の構成は図１の復号装置におけるものと同一である。
【０１２７】
メモリ６−１は図１２に示した例において、データｑｉの部分を１ビットしてよいため（ｉは０からｎｍ−１までの間の整数）、メモリの記憶容量はｎｍ（ｂ＋１）ビットと少なくなる。図１の復号装置と比較してメモリを削減できる。
【０１２８】
一般に、このメモリの削除によって誤り率特性が劣化するが、［数式１］の検査行列Ｈの選択によっては誤り率特性の劣化が極めてわずかな場合がある。図６の復号装置においても図４の並列化されたチェックノード処理装置を適用することによって、図２のチェックノード処理装置を使用する場合に比べて半分の時間で復号処理を行うことができる。
【０１２９】
図２のチェックノード処理装置に関して、各レジスタのビットサイズは上記Ｌｖ（１）、Ｌｖ（２）に相当する二つのデータ（各ｂ−１ビット）、［数式４］中のuminに相当する最大ｌｏｇ２ｎビットのポインタ、および、［数式４］中のｓｖに相当する１ビットの合計（２ｂ−１＋ｌｏｇ２ｎ）ビットと説明したが、これを削減することが可能である。
【０１３０】
上記Ｌｖ（１）、Ｌｖ（２）に相当する二つのデータは各々ｂ−１ビットであり、正負を表す符号ビットを除けば、図１２においてＦで示したデータ部分のビット幅に等しく設定しているが必ずしもそうする必要はなく、より小さなビット数で設定しても良い。
【０１３１】
この場合、図３の比較回路への上記入力データＺを入力の際に予め設定した定数で割るなどしてビット数を削減する。例えば、図３の分離装置３−４後に上記の絶対値部分ＺＢを１ビット右にシフトすることで（定数２で割ることに相当）各レジスタ毎に２ビットの削減が可能となる。
【０１３２】
また、上記ポインタのビット数はｌｏｇ２ｎビットであるが、例えば、ポインタの下位ｄビット分（ｄはｌｏｇ２ｎより小さい正数）のみをレジスタに保持し、それ以外を切り捨てることによってビット数削減が可能となる。一般にこのポインタビット数の削減によって演算結果が変化し、誤り率特性の劣化を引き起こすことがあるが、劣化の程度は［数式１］の検査行列の選択にも依存し、劣化が極めて僅かな場合もある。具体的数値を用いた後述の［実施例］の項目で説明するように、上記ポインタのビット数削減による誤り率特性の劣化が僅かであるような場合、チェックノード処理装置の回路規模削減、メモリ（Ｌ）１−３の記憶容量削減の観点で有効である。
【０１３３】
［実施例］
本発明の復号装置を使用したデータ通信（蓄積）装置の一例を図１４に示す。データの送信側は低密度パリティ検査符号の符号化装置１４−１、フレーム同期をとるための制御と、変調器に合わせたデータへ変換するための同期制御・変調期入力生成装置１４−２、および、変調器１４−３からなる。
【０１３４】
変調器の出力は通信路、あるいは記憶装置へ出力される。データの受信側では通信路、あるいは記憶装置から得られる情報を復調する復調器１４−４と復調器の出力データを復号器の入力データへ変換し、フレーム同期をとる処理を行う同期制御・復号装置入力生成装置１４−５、および、本発明の復号装置１４−６からなる。
【０１３５】
数値例として、［数式１］の検査行列のサイズをｎ＝６５、ｒ＝４、ｍ＝６３とした時、フレーム長が４０９５ビットのビット列を伝送フレームの単位とした通信が行える。この時、１フレーム中の約６％が誤り訂正のための冗長構成部分となる。
【０１３６】
復号器への入力データを構成する各シンボルのビット幅ｂが６ビットである時、チェックノード処理装置の各レジスタのビット数は１８ビット程度であるから、二つのチェックノード処理装置におけるレジスタのビット総数は２．３Ｋビット程度であり、回路規模に大きなインパクトを与えることはなくＲＡＭ数を削減することができる。
【０１３７】
また、この符号に関して、上記の［発明の他の実施の形態］において述べたように、チェックノード処理装置におけるポインタ部分のビット幅を下位１ビットのみ保持することにした場合、誤り率特性の劣化は０．１から０．２ｄＢ程度であり、下位２ビットにした場合の劣化は０．１ｄＢ以下と劣化量はごく僅かである。これによりチェックノード処理装置のレジスタ、および、メモリ（Ｌ）１−３の記憶容量を３０％程度削減することができる。
【０１３８】
なお、本発明は本実施の形態に限定されるものではなく、その要旨を逸脱しない範囲で各種の変形を許容する。例えば、本発明の活用例として、衛星通信、あるいは移動体通信システム等における、所要電力の低減、アンテナの小型化などのシステム構成上の要件を満たすための誤り訂正技術として、あるいは磁気記録などの記憶装置に関する信頼性向上のための誤り訂正技術としての適用が挙げられる。
なお、本発明の全開示（請求の範囲を含む）の枠内において、さらにその基本的技術思想に基づいて、実施形態ないし実施例の変更・調整が可能である。また、本発明の請求の範囲の枠内において種々の開示要素の多様な組み合わせないし選択が可能である。すなわち、本発明は、請求の範囲を含む全開示、技術的思想にしたがって当業者であればなし得るであろう各種変形、修正を含むことは勿論である。
【符号の説明】
【０１３９】
１−１，１−３，６−１，７−１，７−３，９−１  ランダム・アクセス・メモリ
１−２，６−２  チェックノード処理装置
１−４，３−２，５−２，５−３，６−３，８−４  マルチプレクサ
１−５，６−４  デマルチプレクサ
１−６，６−５  加算回路
１−７，１−８，６−６  アドレス生成装置
２−１，４−１  レジスタ
２−２，４−２  比較回路
２−３，２−４，４−３，４−４  置換回路
３−１  比較器
３−３  ポインタ更新回路
３−４，８−２  分離回路
３−５，５−４，８−３  排他的論理和回路
５−１，７−５，９−４  加算器
７−２，９−２  チェックノード処理回路
７−４，９−３  遅延回路
７−６，９−５  置換器
８−１  第１／第２最小値算出回路
１４−１  符号化装置
１４−２  同期制御・変調器入力生成装置
１４−３  変調器
１４−４  復調器
１４−５  同期制御・復号装置入力生成装置
１４−６  復号装置
【図１】
0005488472.tif 000009
【図２】
0005488472.tif 000010
【図３】
0005488472.tif 000011
【図４】
0005488472.tif 000012
【図５】
0005488472.tif 000013
【図６】
0005488472.tif 000014
【図７】
0005488472.tif 000015
【図８】
0005488472.tif 000016
【図９】
0005488472.tif 000017
【図１０】
0005488472.tif 000018
【図１１】
0005488472.tif 000019
【図１２】
0005488472.tif 000020
【図１３】
0005488472.tif 000021
【図１４】
0005488472.tif 000022