(57)【要約】【課題】低密度パリティ検査符号を含む誤り訂正符号化方式は、フレーム長いほど、大きな符号化利得が得られる。フレーム長が非常に長い場合、その符号化と復号処理に多くの計算量が必要、符号化装置及び復号装置が複雑大規模化する。これを改善する。【解決手段】送信データ系列をＬ個の短系列に分割し、この短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって符号化し、更に、Ｌ個の該符号化系列の各々を前記擬似巡回符号の段数ｍと同じ数の長さｍの短系列に分割し、置換手段１４によって順序を入れ替えた後、更にｍ段擬似巡回型低密度パリティ検査符号化方式によって符号化して出力する符号化装置１０を設けた。これにより、前記段数ｍの約数ｐ個の、ノード処理回路（例：最小値算出回路）を有する構成の単純な復号装置２０により、フレーム長が大きく、符号化利得の大きな符号の効率的な復号処理が可能となる。【選択図】図１
2010073922.tif 000002
【特許請求の範囲】
【請求項１】
送信データ系列をＬ個の短系列に分割するデータ分割手段と、この分割されたＬ個の短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化して出力する第１の符号化手段とを備え、
前記第１の符号化手段から出力される長さＮの各符号系列に基づいて冗長系列を生成しこれを前記第１の符号化手段から出力される複数の符号系列と同様に出力する冗長系列出力手段とを備え、
前記冗長系列出力手段を、前記第１の符号化手段で符号化された長さＮでＬ個の符号系列を入力し各データ系列の順序を入れ換えて出力するデータ置換手段と、このデータ置換手段から出力される置換された符号系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式により符号化し出力する第２の符号化手段とを含む構成としたことを特徴とする誤り訂正符号化装置。
【請求項２】
請求項１に記載の誤り訂正符号化装置において、
前記データ置換手段を、前記第１の符号化処理部で符号化されたＬ個のデータ系列の各々を前記第１の擬似巡回型低密度パリティ検査符号の段数ｍと同数の長さｍの短系列に分割する短系列分割部と、この分割によって設定される(L×N)／ｍ個で長さｍの短系列単位で順序を入れ替えて、Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力するデータ置換処理部とを含む構成としたことを特徴とする誤り訂正符号化装置。
【請求項３】
請求項２に記載の誤り訂正符号化装置において、
前記データ置換処理部を、Ｌ個の入力ポートを備えると共にＮ個の出力ポートを備えて振り分けを行うセレクタと、このセレクタから出力される各小ブロックを巡環置換する複数の巡環置換器から成る巡環置換回路とを含む構成としたことを特徴とする誤り訂正符号化装置。
【請求項４】
請求項２に記載の誤り訂正符号化装置において、
前記第２の符号化手段は、前記データ置換手段から出力される置換された符号系列の各々を長さ（Ｌ＋Ｓ）×ｍ以下の系列（Ｓは自然数）に符号化（誤り訂正符号化）し出力する機能を備えていることを特徴とした誤り訂正符号化装置。
【請求項５】
請求項２に記載の誤り訂正符号化装置において、
前記データ置換手段を第１の置換手段とすると共に、前記第２の符号化手段で符号化されるＮ／ｍ個の符号系列で長さＳ×ｍのパリティ部分の各々を入力し、順序を入れ替えてＳ個の長さＮの系列を出力する第２の置換手段を設け、
この第２の置換手段の出力であるＳ個の長さＮの系列の一部分を、段数ｍで長さＮの第３の擬似巡回型低密度パリティ検査符号で符号化する第３の符号化手段を装備し、
この第３の符号化手段で符号化されたパリティ部分の各々を、前記第１の符号化手段で符号化されたＬ個のデータ系列と同様に、符号化された送信データとして出力することを特徴とした誤り訂正符号化装置。
【請求項６】
請求項４に記載の誤り訂正符号化装置において、
前記データ置換手段は、前記第１の符号化手段によって符号化された出力データの内、Ｌ個の第１の低密度パリティ検査符号系列を長さｍの小ブロックに分割して（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の上位Ｌ行に配置すると共に、前記Ｎ／ｍ個の第２の低密度パリティ検査符号の長さＳ×ｍのパリティ系列を、長さｍの小ブロックに分割して前記（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の下位Ｓ行に配置した場合に、当該第２の低密度パリティ検査符号の符号を構成するＬ＋Ｓ個の小ブロックの各々が同一行及び同一列に現れないように配置する機能を備えていることを特徴とした誤り訂正符号化装置。
【請求項７】
請求項５に記載の誤り訂正符号化装置において、
前記データ置換手段は、前記第１の符号化手段によって符号化された出力データの内、Ｌ個の第１の低密度パリティ検査符号系列を長さｍの小ブロックに分割して（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の上位Ｌ行に配置すると共に、前記Ｓ個の第３の長さＮの低密度パリティ検査符号系列を長さｍの小ブロックに分割して、前記（Ｌ＋Ｓ）行、Ｎ／ｍ列の２次元配列の下位Ｓ行に配置した場合に、前記第３の低密度パリティ検査符号の符号を構成するＬ＋Ｓ個の小ブロックの各々が同一行及び同一列に現れないようにそれぞれ配置する機能を備えていることを特徴とした誤り訂正符号化装置。
【請求項８】
誤り訂正符号化装置で符号化され送信されてきたデータを復号すると共にエラーが付加されている場合に当該エラーを訂正する復号装置であって、
前記誤り訂正符号化装置を前記１乃至４の何れか一つに記載の誤り訂正符号化装置とすると共に、
当該誤り訂正符号化装置から送信されてくるデータの内、前記誤り訂正符号化装置の第１の符号化手段で処理された複数の符号化系列のデータと前記誤り訂正符号化装置の冗長系列算出手段で処理された複数の符号化系列のデータとを分けて記憶する複数のデータ記憶手段と、この各データ記憶手段の記憶動作を制御するメモリコントローラとを備え、
前記各データ記憶手段に対応して併設され当該各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新動作を、前記アドレス生成手順にて特定された回数分繰り返えし実行する復号用更新処理手段を有し、
前記メモリコントローラが、前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御機能を備えていることを特徴とした復号装置。
【請求項９】
請求項８に記載の復号装置において、
前記各データ記憶手段をＮ／ｍ個（Ｎは自然数、ｍは擬似巡回型低密度パリティ検査符号の段数）設けると共に、当該各データ記憶手段を、ビット数がｂ×ｐ（ｂは自然数、ｐはｍの約数）、ワード数がｍ／ｐ×（Ｌ＋Ｓ）のＲＡＭ（ランダム・アクセス・メモリ）により構成したことを特徴とする復号装置。
【請求項１０】
請求項９に記載の復号装置において、
前記各ＲＡＭの内、前記Ｎ／ｍ個の第ｊ番目のＲＡＭ（ｊは０から（N/m)−1の間の整数）は、初期状態として、
第(m/p) ×ｉ＋ｋ番目のアドレス（ｉは０からＬ−1の間の整数、ｋは０から(m/p)−1 の間の整数）に、前記第１の低密度パリティ検査符号で符号化されたＬ個の系列の内のｉ番目の系列に対応する受信シンボル列ｆ(0),ｆ(1),…, ｆ(N−1)の中のｆ(jm＋ｋ）,
ｆ(jm＋(m/p)＋ｋ），ｆ(jm＋2×(m/p)＋ｋ），…，ｆ(jm＋(p−1）×(m/p)＋ｋ）を保持すると共に、
第(m/p)×Ｌ番目以降のアドレスに、第２の低密度パリティ検査符号で符号化されたパリティ列に対応する受信シンボル列を保持することを特徴とした復号装置。
【請求項１１】
請求項９に記載の復号装置において、
前記各ＲＡＭの内、前記Ｎ／ｍ個の第ｊ番目のＲＡＭ（ｊは０から（N/m)−1の間の整数）は、初期状態として、
第(m/p)×ｉ＋ｋ番目のアドレス（ｉは０からＬ−1 の間の整数、ｋは０から(m/p)−1 の間の整数）に、前記第１の低密度パリティ検査符号で符号化されたＬ個の系列の内のｉ番目の系列に対応する受信シンボル列ｆ(0),ｆ(1),…, ｆ(N−1)の中のｆ(jm＋ｋ）,
ｆ(jm＋(m/p)＋ｋ），ｆ(jm ＋2×(m/p)＋ｋ），…，ｆ(jm＋(p−1）×(m/p)＋ｋ）を保持すると共に、
第(m/p)×Ｌ番目以降のアドレスに、第３の低密度パリティ検査符号で符号化されたパリティ列に対応する受信シンボル列を保持することを特徴とした復号装置。
【請求項１２】
請求項９に記載の復号装置において、
前記復号用更新処理手段を、前記各ＲＡＭに保持されたデータをｂビット毎に与えらえれた量だけ巡回シフトするＮ／ｍ個の巡回シフト回路を備えた巡回シフト処理部と、前記Ｎ／ｍ個の巡回シフト回路の各出力側に装備されたｐ個のノード処理部から成るノード処理手段と、前記ｐ個のノード処理部からの出力結果を保持する遅延素子とを備えた構成とし、これら各構成要素の協働により前記更新動作が実行される構成としたことを特徴とした復号装置。
【請求項１３】
請求項９に記載の復号装置において、
前記復号用更新処理手段を、前記各ＲＡＭに保持されたデータをｂビット毎に与えらえれた量だけ巡回シフトするＮ／ｍ個の巡回シフト処理部と、この各巡回シフト処理部の出力を入力するｐ個の減算器と、この各減算器の出力結果を保持する複数の第１の遅延素子と、前記各減算器からの各出力を入力し伝送処理するｐ個のノード処理部を備えたノード処理手段と、この各ノード処理手段の出力結果を保持すると共にこれを前記減算器へ送り込む第２の遅延素子と、前記ノード処理手段と第１の遅延素子の各出力を加算し更新情報をして前記各ＲＡＭに送り込むｐ個の加算器とを備え、これら各構成要素の協働により前記更新動作が実行される構成としたことを特徴とした復号装置。
【請求項１４】
請求項１２又は１３に記載の復号装置において、
前記ノード処理手段のｐ個の各ノード処理部を最小値算出手段によって構成すると共に、この前記各最小値算出処理部が、
そのデータ入力段に設けられ前記各減算器からの出力データの内の４個の出力データを入力データとして入力し絶対値が小さい二つの数値と当該絶対値が最小の数値が入力された入力ポートに対応する番号を出力する複数の２／４データ処理部と、この複数の各２／４データ処理部の出力側に順次トーナメント上に設けられた同一の機能を備えた複数の２／４データ処理部と、この２／４データ処理部の最終出力段に位置する２／４データ処理部の出力を入力し当該２／４データ処理部のポート番号Ｐと同一番号の出力ポートにはＸ１  を出力し且つそれ以外の番号の出力ポートにはＸ０  を出力する機能を備えたデマルチプレクサと、前記入力データに基づいて所定の演算を行って外部へ出力する排他的論理和回路とを有し、
これにより、入力データ数ｋ個の入力数値の内の絶対値が最小の数値の入力ポートに対応する番号を出力する機能を備えると共に、前記ｋ個の入力数値の最上位ビット全体から選択したｋ−１個の最上位ビットの排他的論理和をすべて算出する機能を備えていることを特徴とした復号装置。
【請求項１５】
発信側に符号化装置を備えると共に受信側に前記符号化装置に対応した復号装置を備えたデータ通信装置において、
前記符号化装置として、前記請求項１乃至７のいずれか１項に記載の誤り訂正符号化装置を装備したことを特徴としたデータ通信装置。
【請求項１６】
請求項１５に記載のデータ通信装置において、
前記復号装置として、前記請求項８乃至１４のいずれか１項に記載の誤り訂正符号化装置を装備したことを特徴としたデータ通信装置。
【請求項１７】
送信データ系列をデータ分割手段によりＬ個の短系列に分割し、
この分割されたＬ個の短系列の各々を第１の符号化手段によりｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化し、
前記第１の符号化手段から出力される長さＮの各符号系列に基づいて冗長系列出力手段が冗長系列を生成してこれを前記第１の符号化手段から出力される複数の符号系列と共に冗長系列のデータとして出力すると共に、
前記冗長系列のデータ出力に際しては、前記第１の符号化手段で符号化された長さＮでＬ個の符号系列をデータ置換手段が入力し且つ各データ系列の順序を入れ換えて出力し、
その後、この出力される置換された符号系列の各々を、第２の符号化手段によってｍ段擬似巡回型低密度パリティ検査符号化方式に符号化（誤り訂正符号化）するようにしたことを特徴とする誤り訂正符号化方法。
【請求項１８】
請求項１７に記載の誤り訂正符号化方法において、
前記データ置換手段が実行する入力データに対するデータ系列の順序を入れ換えて出力する工程にあっては、前記第１の符号化処理部で符号化されたＬ個のデータ系列の各々を前記第１の擬似巡回型低密度パリティ検査符号の段数ｍと同数の長さｍの短系列に分割する工程を短系列分割部が実行し、この分割によって設定される(L×N)／ｍ個で長さｍの短系列単位で順序を入れ替えて、Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力する工程をデータ置換処理部が実行するようにしたことを特徴とする誤り訂正符号化方法。
【請求項１９】
請求項１８に記載の誤り訂正符号化方法において、
前記データ置換処理部が実行する短系列単位での順序を入れ替える工程では、
Ｌ個の入力ポートを備えると共にＮ個の出力ポートを備えたセレクタが前記振り分け工程を実行し、
これにより出力される各小ブロックを巡環置換する工程を複数の巡環置換器から成る巡環置換回路が実行するようにし、
これにより、前記Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力するようにしたことを特徴とする誤り訂正符号化方法。
【請求項２０】
誤り訂正符号化装置で符号化され送信されてきたデータを復号すると共にエラーが付加されている場合に当該エラーを訂正する復号方法であって、
前記誤り訂正符号化装置から送信されてくるデータの内、前記誤り訂正符号化装置が有する第１の符号化手段で処理された複数の符号化系列のデータと前記誤り訂正符号化装置が有する冗長系列算出手段で処理された複数の符号化系列のデータとを、複数のデータ記憶手段に分けて記憶し、
前記各データ記憶手段に対応して併設され当該各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新動作を、復号用更新処理手段が、前記アドレス生成手順にて特定された回数分繰り返えして実行し、
前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御工程をメモリコントローラが実行するようにしたことを特徴とする復号方法。
【請求項２１】
送信データ系列をＬ個の短系列に分割するデータ分割処理機能、
この分割されたＬ個の短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化（誤り訂正符号化）して出力する第１の符号化処理機能、
前記第１の符号処理機能の実行によって生成される長さＮの各符号系列に基づいて冗長系列を生成しこれを前記第１の符号化処理機能によって生成され出力される前記複数の符号系列の場合と同様に出力する冗長系列出力処理機能を設け、
前記冗長系列出力出力処理機能を、前記第１の符号化処理機能により符号化された長さＮでＬ個の符号系列を入力し各データ系列の順序を入れ換えて出力処理するデータ置換処理機能、及びこれにより出力される置換された符号系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式により符号化（誤り訂正符号化）し出力する第２の符号化処理機能を含む構成とし、
これらをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２２】
請求項２１に記載の誤り訂正符号化プログラムにおいて、
前記データ置換処理機能は、前記第１の符号化処理機能により符号化されたＬ個のデータ系列の各々を前記第１の擬似巡回型低密度パリティ検査符号の段数ｍと同数の長さｍの短系列に分割する短系列分割処理機能と、この分割によって設定される(L×N)／ｍ個で長さｍの短系列単位で順序を入れ替えて、Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力するデータ置換処理機能とを含む構成とし、
これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２３】
請求項２２に記載の誤り訂正符号化プログラムにおいて、
前記データ置換処理機能は、Ｌ個の入力ポートを備えると共にＮ個の出力ポートを備えて振り分けを行う振分け処理機能と、この振分け処理機能により振り分けられて前記Ｎ個の出力ポートから出力される各小ブロックを巡環置換する巡環置換機能とを含む構成とし、  これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２４】
請求項２２に記載の誤り訂正符号化プログラムにおいて、
前記第２の符号化処理機能は、前記データ置換処理機能により出力される置換された符号系列の各々を、長さ（Ｌ＋Ｓ）×ｍ以下の系列（Ｓは自然数）に符号化（誤り訂正符号化）し出力処理する構成とし、
これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２５】
請求項２２に記載の誤り訂正符号化プログラムにおいて、
前記データ置換処理機能を第１の置換処理機能とすると共に、前記第２の符号化処理機能で符号化されるＮ／ｍ個の符号系列で長さＳ×ｍのパリティ部分の各々を入力し、順序を入れ替えてＳ個の長さＮの系列を出力する第２の置換処理機能を設け、
この第２の置換処理機能による得られるＳ個の長さＮの系列の一部分を、段数ｍで長さＮの第３の擬似巡回型低密度パリティ検査符号で符号化処理する第３の符号化処理機能を設け、
この第３の符号化処理機能により符号化されたパリティ部分の各々を、前記第１の符号化処理機能で符号化されたＬ個のデータ系列と同様に、符号化された送信データとして出力処理する構成とし、
これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２６】
請求項２４に記載の誤り訂正符号化プログラムにおいて、
前記データ置換処理機能は、前記第１の符号化処理機能が実行されて符号化された出力データの内、Ｌ個の第１の低密度パリティ検査符号系列を長さｍの小ブロックに分割して（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の上位Ｌ行に配置すると共に、前記Ｎ／ｍ個の第２の低密度パリティ検査符号の長さＳ×ｍのパリティ系列を、長さｍの小ブロックに分割して前記（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の下位Ｓ行に配置した場合に、当該第２の低密度パリティ検査符号の符号を構成するＬ＋Ｓ個の小ブロックの各々が同一行及び同一列に現れないように配置処理する機能を備えた構成とし、
これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２７】
請求項２５に記載の誤り訂正符号化プログラムにおいて、
前記データ置換処理機能は、前記第１の符号化処理機能が実行されて符号化された出力データの内、Ｌ個の第１の低密度パリティ検査符号系列を長さｍの小ブロックに分割して（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の上位Ｌ行に配置すると共に、前記Ｓ個の第３の長さＮの低密度パリティ検査符号系列を長さｍの小ブロックに分割して、前記（Ｌ＋Ｓ）行、Ｎ／ｍ列の２次元配列の下位Ｓ行に配置した場合に、前記第３の低密度パリティ検査符号の符号を構成するＬ＋Ｓ個の小ブロックの各々が同一行及び同一列に現れないようにそれぞれ配置処理する機能を備えた構成とし、
これをコンピュータに実行させるようにしたことを特徴とする誤り訂正符号化プログラム。
【請求項２８】
誤り訂正符号化装置上で誤り訂正符号化処理プログラムが実行され符号化されて送信されてくる送信データ系列にかかるデータを復号装置上で復号処理すると共にエラーが付加されている場合に当該エラーを訂正する復号処理プログラムであって、
前記符号化されて送信されてくる送信データ系列にかかるデータの内、前記誤り訂正符号化装置上で実行される第１の符号化処理機能で処理された複数の符号化系列のデータと、前記誤り訂正符号化装置上で実行される冗長系列出力処理機能で処理された複数の符号化系列のデータとを分けて複数のデータ記憶手段にそれぞれ記憶処理する記憶動作制御機能を設け、
前記各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新処理動作を、前記アドレス生成手順にて特定された回数分繰り返えして実行する復号用更新処理機能を備え、
前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御機能を設け、
これらをコンピュータに実行させるようにしたことを特徴とする復号処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号化装置、復号装置等に係り、特に、擬似巡回型（Ｑuaci  Ｃyclic）の低密度パリティ検査（Ｌow  Ｄensity  Ｐarity  Ｃheck：ＬＤＰＣ）符号に基づいたもので、情報系列を一定長のブロックに分割し、ブロック毎に独立に冗長系列を付加するブロック誤り訂正の誤り訂正符号化装置、復号装置、符号化方法、復号方法、及びそのプログラムに関する。
【背景技術】
【０００２】
衛星通信、或いは移動体通信システム等においては、所要電力の低減、アンテナの小型化などのシステム構成上の要件を満たすため、大きな符号化利得を有する誤り訂正符号化技術の導入が行われている。この場合、低密度パリティ検査（Ｌow  Ｄensity  Ｐarity  Ｃheck：ＬＤＰＣ）符号は、大きな符号化利得を有する誤り訂正符号として知られており、前記の各種通信システム、或いは磁気記録などの記憶装置への導入が進んでいる。【０００３】
低密度パリティ検査符号は、単に一つの誤り訂正符号化方式を示すのではなく、検査行列が疎である（行列中の成分の殆どが「０」であり、「１」である成分の数が非常に少ない）という特徴をもった誤り訂正符号の総称である。
そして疎の状態の検査行列を選択することにより、サム・プロダクト（ｓｕｍ−ｐｒｏｄｕｃｔ）アルゴリズム、ミン・サム（ｍｉｎ−ｓｕｍ）アルゴリズムなどの繰り返し復号方式を用いることにより、大きな符号化利得を持つ誤り訂正符号化方式を構成することが可能となるという利点が得られる（例えば非特許文献１、２を参照）。【０００４】
ここで、式１に、ｒ×ｎのブロック行列を示す（ｒ，ｎはｒ≦ｎとなる自然数）。この式１に示すブロック行列の各成分おいて、Ｉｉ，ｊは、ｍ×ｍの巡回置換行列、或いは零行列、を表す（記号ｍは自然数、記号ｉは０からｒ−１の間の整数、記号ｊは０からｎ−１の間の整数を示す）。
【数１】
2010073922.tif 000003
【０００５】
この式１の形のブロック行列を検査行列とする低密度パリティ検査符号を、特に、ｍ段擬似巡回パリティ検査符号と呼ぶ。即ち、ｎ×ｍビットのすべての情報系列の中で、前記行列Ｈとの行列積が零となる系列の集合が、フレーム長＝ｎ×ｍ、検査行列＝Ｈ、から成るｍ段擬似巡回パリティ検査符号となる。【０００６】
低密度パリティ検査符号の復号方式である前記サム・プロダクト、ミン・サムアルゴリズムは、自然数ｎに対して段数ｍが小さいほど、復号処理及びそれを実現する装置が複雑化する傾向にある。
従って、上述した巡回置換行列Ｉｉ，ｊでは、サイズｍを大きくすることによって、復号処理の複雑度を抑えつつフレーム長を長くすることが可能であるが、一般にこのような構成の低密度パリティ検査符号では、フレーム長の増加に伴った符号化利得の大きな増加が望めないという問題点がある。【０００７】
又、低密度パリティ検査行列を用いて入力情報系列から低密度パリティ検査符号を生成する誤り訂正符号化装置についての関連技術として下記特許文献１がある。この特許文献１に記載の技術は、行の重みと同数の巡回置換行列を配置した行を前記所定の重み分布を満たす行数分連続させ、且つ行の重みを漸次的に増加乃至減少させるように構成した前記低密度パリティ検査行列を出力する手段を備え、これによって、乱数系列を用いる手法に比較して性能向上図ることを意図したものである。
【先行技術文献】
【非特許文献】
【０００８】
【非特許文献１】著者：ロバート  ギャラガ（Ｒobert Ｇallager）題名：ロー・デンシティ  パリティ・チェック  コーズ（Ｌow−Ｄensity  Ｐarity−Ｃheck  Ｃodes）／説明頁  第２１頁から第２８頁発行元：アイトリプルイートランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔransactions  Ｏn  Ｉnformation  Ｔheory）発行年月日：１９６２年１月
【非特許文献２】著者：ディー・ジェー・シー  マッカイ（Ｄ．Ｊ．Ｃ．ＭacKay）題名：グット  エラー・コレクティング  コーズ  ベースト  オン  ベリー  スパースメトリシィーズ（Ｇood  Ｅrror−Ｃorrecting  Ｃodes  Ｂased  Ｏn  Ｖery  Ｓparse  Ｍatrices）説明頁  第３９９頁から第４３１頁発行元：アイトリプルイートランザクションズ  オン  インフォメーション  セオリー（ＩＥＥＥ  Ｔransactions  Ｏn  Ｉnformation  Ｔheory）  発行年月日：１９９９年３月
【特許文献】
【０００９】
【特許文献１】国際公開番号ＷＯ２００６／１０６８４１
【発明の開示】
【発明が解決しようとする課題】
【００１０】
上述した低密度パリティ検査符号を含む誤り訂正符号化方式（非特許文献１、２）のものは、一般にフレーム長を長くするほど、より大きな符号化利得が得られる。しかしながら、その一方で、フレーム長が非常に長い場合、その符号化と復号処理に多くの計算量を必要とし、符号化装置及び復号装置が複雑化、大規模化するという不都合がある。
特に、単純に擬似巡回型の低密度パリティ検査符号の段数を大きくしてフレーム長を長くした場合には、フレーム長の増大に伴う符号化利得の改善度が少ないことから、本質的な解決には至らない状態となっている。【００１１】
又、特許文献１に記載のものは、低密度パリティ検査符号の生成に特徴を持たせて誤り訂正符号化装置全体の性能向上をはかるようにしたものであり、フレーム長の増大に伴う符号化利得の改善については、直接的な関連性は有してはいない。【００１２】
本発明は、上記関連技術の有する不都合を改善し、特に、フレーム長が長くても、大きな符号化利得を得る符号化装置、符号化方法及びそのプログラムを、並びに、当該大きな符号化利得を得ることができる符号化装置に応答して稼働し当該符号化装置で符号化されたデータを小規模で復号処理をなし得る構成が単純化された復号装置、復号方法及びそのプログラムを提供することを、その目的とする。
【課題を解決するための手段】
【００１３】
上記目的を達成するため、本発明にかかる誤り訂正符号化装置は、送信データ系列をＬ個の短系列に分割するデータ分割手段と、この分割されたＬ個の短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化（誤り訂正符号化）して出力する第１の符号化手段とを備え、前記第１の符号化手段から出力される長さＮの各符号系列に基づいて冗長系列を生成しこれを前記第１の符号化手段から出力される複数の符号系列と同様に出力する冗長系列出力手段とを備えている。【００１４】
そして、前述した冗長系列出力手段を、前記第１の符号化手段で符号化された長さＮでＬ個の符号系列を入力し各データ系列の順序を入れ換えて出力するデータ置換手段と、このデータ置換手段から出力される置換された符号系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式により符号化（誤り訂正符号化）し出力する第２の符号化手段とにより構成したことを特徴とする。【００１５】
又、上記目的を達成するため、本発明にかかる復号装置は、誤り訂正符号化装置で符号化され送信されてきたデータを復号すると共にエラーが付加されている場合に当該エラーを訂正する復号装置であって、前述した誤り訂正符号化装置から送信されてくるデータの内、前記誤り訂正符号化装置の第１の符号化手段で処理された複数の符号化系列のデータと前記誤り訂正符号化装置の冗長系列算出手段で処理された複数の符号化系列のデータとを分けて記憶する複数のデータ記憶手段と、この各データ記憶手段の記憶動作を制御するメモリコントローラとを備えている。【００１６】
更に、この復号装置は、前述した各データ記憶手段に対応して併設され当該各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新動作を、前記アドレス生成手順にて特定された回数分繰り返えし実行する復号用更新処理手段を有する。そして、前記メモリコントローラが、前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御機能を備えていることを特徴とする。【００１７】
又、上記目的を達成するため、本発明にかかる誤り訂正符号化方法は、送信データ系列をデータ分割手段によりＬ個の短系列に分割し、この分割されたＬ個の短系列の各々を第１の符号化手段によりｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化し、前記第１の符号化手段から出力される長さＮの各符号系列に基づいて冗長系列出力手段が冗長系列を生成してこれを前記第１の符号化手段から出力される複数の符号系列と共に冗長系列のデータとして出力する。
続いて、前述した冗長系列のデータ出力に際しては、前記第１の符号化手段で符号化された長さＮでＬ個の符号系列を、データ置換手段が入力した後各データ系列の順序を入れ換えて出力し、その後に、この出力される置換された符号系列の各々を、第２の符号化手段によってｍ段擬似巡回型低密度パリティ検査符号化方式に符号化（誤り訂正符号化）するようにしたことを特徴とする。【００１８】
更に、上記目的を達成するため、本発明にかかる復号方法は、誤り訂正符号化装置で符号化され送信されてきたデータを復号すると共にエラーが付加されている場合に当該エラーを訂正する復号方法であって、
前記誤り訂正符号化装置を前記１乃至４の何れか一つに記載の誤り訂正符号化装置から送信されてくるデータの内、前記誤り訂正符号化装置の第１の符号化手段で処理された複数の符号化系列のデータと前記誤り訂正符号化装置の冗長系列算出手段で処理された複数の符号化系列のデータとを複数のデータ記憶手段に分けて記憶し、
前記各データ記憶手段に対応して併設され当該各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新動作を、復号用更新処理手段が前記アドレス生成手順にて特定された回数分繰り返えして実行し、
前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御工程をメモリコントローラが実行するようにしたことを特徴とする。【００１９】
又、上記目的を達成するため、本発明にかかる誤り訂正符号化処理プログラムは、送信データ系列をＬ個の短系列に分割するデータ分割処理機能、この分割されたＬ個の短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化（誤り訂正符号化）して出力する第１の符号化処理機能、  前記第１の符号処理機能の実行によって生成される長さＮの各符号系列に基づいて冗長系列を生成しこれを前記第１の符号化処理機能によって生成され出力される前記複数の符号系列の場合と同様に出力する冗長系列出力処理機能とを有し、前記冗長系列出力出力処理機能を、前記第１の符号化処理機能により符号化された長さＮでＬ個の符号系列を入力し各データ系列の順序を入れ換えて出力処理するデータ置換処理機能、及びこれにより出力される置換された符号系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式により符号化（誤り訂正符号化）し出力する第２の符号化処理機能とを含む構成とし、  これらをコンピュータに実行させるようにしたことを特徴とする。【００２０】
更に、上記目的を達成するため、本発明にかかる復号処理プログラムは、誤り訂正符号化装置上で誤り訂正符号化処理プログラムが実行され符号化されて送信されてくる送信データ系列にかかるデータを復号装置上で復号処理すると共にエラーが付加されている場合に当該エラーを訂正する復号処理プログラムであって、
前記符号化されて送信されてくる送信データ系列にかかるデータの内、前記誤り訂正符号化装置上で実行される第１の符号化処理機能で処理された複数の符号化系列のデータと、前記誤り訂正符号化装置上で実行される冗長系列出力処理機能で処理された複数の符号化系列のデータとを分けて複数のデータ記憶手段にそれぞれ記憶処理する記憶動作制御機能、前記各データ記憶手段のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新処理動作を、前記アドレス生成手順にて特定された回数分繰り返えして実行する復号用更新処理機能、前記複数の各データ記憶手段に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御機能、これらをコンピュータに実行させるようにしたことを特徴とする。
【発明の効果】
【００２１】
本発明は、上述したように、送信データ系列の符号化に際しては、基本的に、ｍ段擬似巡回型低密度パリティ検査符号化方式を一方の符号化手段によって符号化を実行し、データ置換手段を介して冗長系列を置換出力したものを更に他方の符号化手段で符号化するという複数の組み合わせて符号化する構成としたので、フレーム長の増大によって符号化利得が大きく改善されるという優れた効果を奏する。【００２２】
又、受信側にあって、符号化されたデータ系列の復号化に際しては、フレーム長の増大されたデータ系列が送り込まれても前述した送信データ系列の符号化の場合と同様のｍ段擬似巡回型低密度パリティ検査符号に対応した復号化処理が実行されるので、回路規模の増大や使用メモリ個数の増大を伴うことなく復号処理が可能となり、これにより、復号処理の高速化、復号処理動作時における消費電力の抑制という優れた効果を奏する。
【図面の簡単な説明】
【００２３】
【図１】本発明の第１実施形態における誤り訂正符号化装置部分を示すブロック図である。
【図２】本発明の第１実施形態における復号装置部分を示すブロック図である。
【図３】図１に開示した誤り訂正符号化装置の一部を構成するデータ置換手段を示すブロック図である。
【図４】図３に開示したデータ置換手段の動作例を示す説明図である。
【図５】図１に開示した誤り訂正符号化装置から出力される符号化されたデータ系列のフレーム構成を示す説明図である。
【図６】図１に開示した復号装置の一部を構成するノード処理手段の例（最小値算出手段）を示すブロック図である。
【図７】図５に開示したデータ系列のフレーム構成に対応してｍシンボル毎に区切られた受信フレームのフレーム構成を示す説明図である。
【図８】図２に開示した復号装置にあって、メモリコントローラによる複数のＲＡＭに対するアクセス方法の例を示す図で、式５と式７とにより算出されるアドレス値に従ってアクセスされる場合の例がそれぞれ領域（Ａ），領域（Ｂ）となる場合を示す説明図である。
【図９】図２に開示した復号装置にあって、巡回シフト処理部の動作例を示す説明図である。
【図１０】本発明の第２実施形態における復号装置の一部を構成するノード処理手段として装備された積回路（積装置）の例を示すブロック図である。
【図１１】本発明の第３実施形態を示す図で、図１に開示した第１実施形態における誤り訂正符号化装置の他の例を示すブロック図である。
【図１２】本発明の第４実施形態を示す図で、図１に開示した第１実施形態における誤り訂正符号化装置および復号装置をデータ通信装置に装備した場合の例を示すブロック図である。
【発明を実施するための最良の形態】
【００２４】
〔第１の実施形態〕
次に、本発明にかかる誤り訂正符号化装置および当該符号化装置に対応した復号装置の第１実施形態を、図１乃至図９に基づいて説明する。
本第１の実施形態にかかる符号化装置は、長さＫの送信データ系列を入力する送信データ系列入力手段と、入力された前記送信データ系列から冗長系列を算出する冗長系列算出手段とを備え、この冗長系列と前記送信データ系列とを対応する復号装置に向けて出力し復号するように構成したものである。【００２５】
図１に本第１実施形態における誤り訂正符号化装置１０を示し、この符号化装置１０から出力される符号化されたデータを復号化して出力する復号装置２０を図２に示す。【００２６】
〔誤り訂正符号化装置１０の構成〕
本第１実施形態における誤り訂正符号化装置１０は、図１に示すように、長さＫの送信データ系列１０１をＬ個の短系列に分割するデータ分割手段１１と、この分割されたＬ個の短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化（誤り訂正符号化）して出力する第１の符号化手段１２と、この第１の符号化手段１２から出力される長さＮの各符号系列１０３に基づいて冗長系列を生成しこれを前記第１の符号化手段１２から出力される複数の符号系列１０３と同様に出力する冗長系列出力手段１３とを備えている。【００２７】
上記冗長系列出力手段１３は、前記第１の符号化手段１２で符号化された長さＮでＬ個の符号系列１０３を入力し各データ系列の順序を入れ換えて出力するデータ置換手段１４と、このデータ置換手段１４から出力される置換された符号系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式により符号化（誤り訂正符号化）し出力する第２の符号化手段１５とを備えて構成されている。【００２８】
これを更に詳述する。
図１に示す符号化装置１０は、上述したように、長さＫ（Ｋは自然数）の送信データ系列１０１を入力して、当該長さＫの送信データ系列１０１から冗長系列を算出し、当該送信データ系列と冗長系列とを併せた符号系列を出力する装置である。【００２９】
この内、第１の符号化手段１２は、式１の検査行列を持つ複数のｍ段擬似巡回型（Quasi Cyclic）の低密度パリティ検査符号（ＬＤＰＣ：Low Density
Parity Check）のエンコーダであるＬ個の符号化処理部１２０，１２１，……１２Ｌ−１により構成されている。記号ｍは自然数を示す。
即ち、図１のｍ段低密度パリティ検査符号の符号化手段である第１の符号化手段１２は、前述した長さＫの送信データ系列をそれぞれＬ個（Ｌは自然数）に分割した各系列を長さＮの系列にそれぞれ符号化して出力する機能を備えている。【００３０】
この第１の符号化手段１２には、当該符号化手段１２のＬ個の符号化処理部１２０，１２１，……１２Ｌ−１の各出力を入力して複数の各データ系列につきその順序を入れ替えて出力する巡回置換機能を備えたデータ置換手段１４が併設されている。記号１０４はデータ置換手段１４から出力される複数のデータ系列を示す。【００３１】
このデータ置換手段１４の出力側には、前述した第１の符号化手段１３と同様に機能する第２の符号化手段１５が装備されている。【００３２】
この第２の符号化手段１５は、前述したデータ置換手段１４の出力系列の各々を、長さ（Ｌ＋Ｓ）×ｍ以下の系列に符号化（誤り訂正符号化）して出力する機能を有し、前述した第１の符号化手段１２と同様に機能するｍ段低密度パリティ検査符号（ＬＤＰＣ）のエンコーダであるＮ／ｍ個の符号化処理部１５０，１５１，……１５Ｌ−１（１−２）により構成され、これによって、後述するように符号化され且つ冗長化された複数のデータ系列を復号装置に向けて送信出力するようになっている。【００３３】
上記データ置換手段１４の一例を図３に示す。
この図３に示すデータ置換手段１４は、前述したＬ個の入力データ系列の各々を（Ｌは自然数）、前記擬似巡回型低密度パリティ検査符号の段数ｍと同数の長さｍの小ブロックに区切る（短系列に分割する）置換用データ分割部としての短系列分割部１４Ａと、この分割によって設定される（Ｌ×Ｎ）／ｍ個で長さｍの小ブロック単位で順序を入れ換えて、Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力するデータ置換部１６とにより構成され、これにより、前述した巡回置換機能が実行されるように構成されている。【００３４】
ここで、このデータ置換手段１４の上記置換用データ分割部（短系列分割部）１４Ａは、第１の符号化手段１２によって符号化された出力データの内、Ｌ個の第１の低密度パリティ検査符号系列を長さｍの小ブロックに分割して（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の上位Ｌ行に配置すると共に、前記Ｎ／ｍ個の第２の低密度パリティ検査符号の長さＳ×ｍのパリティ系列を、長さｍの小ブロックに分割して前記（Ｌ＋Ｓ）行、（Ｎ／ｍ）列の２次元配列の下位Ｓ行に配置した場合に、当該第２の低密度パリティ検査符号の符号を構成するＬ＋Ｓ個の小ブロックの各々が同一行及び同一列に現れないように配置する機能を備えている。【００３５】
このデータ置換手段１４の上記データ置換部１６は、前記置換用データ分割部１４Ａで区切られた小ブロック単位で予め定められたパターンに従ってデータの置換を行うセレクタ１４Ｂと、このセレクタ１４Ｂから出力される各系列についてその長さｍの小ブロックの内部で予め定められた量の巡回置換を行う巡回置換回路１４Ｃとから成る。【００３６】
この内、セレクタ１４ＢはＬ個の入力ポートを備えると共にＮ個の出力ポートを備えて振り分けを行う機能を有し、又、巡回置換回路１４Ｃは、各系列ごとに対応して複数の巡回置換器１４Ｃ１，１４Ｃ２，１４Ｃ３……を備え、これによって上述した巡回置換が各系列ごとに迅速に実行されるようになっている。【００３７】
又、前述したセレクタ１４Ｂへの入力は前述したように置換用データ分割部１４Ａの出力であるＬ個の前記長さｍの小ブロック化されたデータ系列であり、当該セレクタ１４Ｂの出力は、ｎ個の長さｍの小ブロックのデータ系列となる。ここで、自然数ｎは、前述したｍ段擬似巡回型低密度パリティ検査符号のフレーム長Ｎを（Ｎは自然数）を段数ｍで割った数値に一致する。尚、このセレクタ１４Ｂの行うデータ置換の規則については、後述する動作説明の欄にて詳述する。【００３８】
〔復号装置２０の構成〕
図２に、上記符号化方式によって符号化されたデータを復号化する復号装置２０を示す。この図２に示す復号装置２０は、上述した誤り訂正符号化装置１０で符号化され送信されてきたデータを複号すると共にエラーが付加されている場合に当該エラーを訂正する機能を備えている。【００３９】
この復号装置２０は、前述した誤り訂正符号化装置１０から送信されてくるデータの内、前記誤り訂正符号化装置１０の第１の符号化手段１２で処理された複数の符号化系列のデータ１０３と前記誤り訂正符号化装置１０の冗長系列算出手段１３で処理された複数の符号化系列のデータとを分けて記憶する複数のデータ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１を備えたデータ記憶手段２１と、この各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１の記憶動作を制御するメモリコントローラ２０Ａとを備えている。【００４０】
更に、この復号装置２０は、前記各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１に対応して併設され当該各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段の同一アドレスに記憶する更新動作を、前記アドレス生成手順にて特定された回数分繰り返えし実行する復号用更新処理手段２２を備えている。【００４１】
そして、前述したメモリコントローラ２０Ａが、前記複数の各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１に書き込んだ時とは逆の手順で取り出すと共に、これを復号データとして出力する復号データ出力制御機能を備えている。【００４２】
前述したデータ記憶手段２１は、具体的にはＮ／ｍ個（Ｎは自然数、ｍは擬似巡回型低密度パリティ検査符号の段数）のデータ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１を有すると共に、当該各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１を、ビット数は、ｂ×ｐ（ｂは自然数、ｐはｍの約数）、ワード数がｍ／ｐ×（Ｌ＋Ｓ）のＲＡＭ（ランダム・アクセス・メモリ）により構成されている。【００４３】
上記データ記憶手段２１は、具体的には、前述した図１における第１，第２の各符号化手段（低密度パリティ検査符号の符号化手段）の出力系列の長さＮ，（Ｌ＋Ｓ）×ｍ，の内、大きい方の数値を前記ｍで割った商と同数から成る複数のＲＡＭにより構成されている。【００４４】
そして、前記各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１の内、前記Ｎ／ｍ個の第ｊ番目のＲＡＭ（ｊは０から（N/m)−1の間の整数）は、初期状態として、第(m/p)×ｉ＋ｋ番目のアドレス（ｉは０からＬ−1の間の整数、ｋは０から(m/p)−1の間の整数）に、前記第１の低密度パリティ検査符号で符号化されたＬ個の系列の内のｉ番目の系列に対応する受信シンボル列ｆ(0),ｆ(1),…, ｆ(N−1)の中のｆ(jm＋ｋ）,ｆ(jm＋(m/p)＋ｋ），ｆ(jm＋2×(m/p)＋ｋ），…，ｆ(jm＋(p−1）×(m/p)＋ｋ）を保持すると共に、第(m/p)×Ｌ番目以降のアドレスには、第２の低密度パリティ検査符号で符号化されたパリティ列に対応する受信シンボル列を保持するように設定されている。【００４５】
前述した復号用更新処理手段２２は、前記各ＲＡＭ２１０，２１１，２１２，…２１ｎ−１に保持されたデータをｂビット毎に与えらえれた量だけ巡回シフトするＮ／ｍ個の巡回シフト回路２３０，２３１，２３２，…からなる巡回シフト処理部２３と、この各巡回シフト回路２３０，２３１，２３２，…の各出力側に装備されたｐ個のノード処理部２４０，２４１，２４２，…から成るノード処理手段２４と、前述したｐ個の各ノード処理部２４０，２４１，２４２，…からの出力結果を保持する前述したデータ記憶手段２１とを備えた構成とし、これら各構成要素の協働により前記更新動作が実行されるようになっている。【００４６】
これを更に詳述すると、復号用更新処理手段２２は、図２に示すように、前記各ＲＡＭ２１０，２１１，〜２１ｎ−１に保持されたデータをｂビット毎に与えらえれた量だけ巡回シフトするＮ／ｍ個の前述した巡回シフト回路２３０，２３１，２３２，…２３ｎ−１からなる巡回シフト処理部２３と、この各巡回シフト回路２３０，２３１，２３２，…２３ｎ−１の出力を入力するｎ個の減算器２５と、この各減算器２５の出力結果を保持する複数の第１の遅延素子部２６０，２６１，２６２，…２６ｎ−１から成る第１の遅延素子２６と、前記各減算器２５からの各出力を入力し伝送処理する前述したｐ個のノード処理部２４１，２４２，２４３，…２４ｐを備えたノード処理手段２４と、このノード処理手段２４の各出力結果を保持すると共にこれらを前記各減算器２５へ送り込む複数の第２の遅延素子部２８ａ，２８ｂ，…を備えた第２の遅延素子２８と、前記ノード処理手段２４と前記第１の遅延素子２６の各出力を加算し更新情報として前記各ＲＡＭに送り込むｎ個の加算器２９とを備え、これら各構成要素の協働により前記更新動作が実行される構成となっている。【００４７】
ここで、上記各ＲＡＭのワード数は前記Ｎと前記（Ｌ＋Ｓ）×ｍの内小さい方の数値を前記ｍの約数ｐで割った商に一致する。このため、以後の説明では、記述を簡単にするため特に断らない限り、Ｎ≧（Ｌ＋Ｓ）×ｍとする。【００４８】
この復号装置２０は、上述したように、ワード数が（Ｌ＋Ｓ）×（ｍ／ｐ）に一致するＮ／ｍ個のＲＡＭを備えている。又、この各ＲＡＭと同数の第１の遅延素子２６、加算器２９、減算器２５、及びｐ個（ｍの約数）の第２の遅延素子２８を備えている。そして、この図２の実施形態にあっては、この第１の遅延素子２６の遅延量は、前記ノード処理手段２４における処理遅延量と一致するように構成されている。この第２の遅延素子２８の遅延量については、後述する動作説明の欄にて詳述する。【００４９】
又、この復号装置２０では、前述した各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１の読み出しポートに、巡回シフト処理部２３を配置した場合を例示したが、図２に示すように、書き込みポート部分に、当該巡回シフト処理部２３と同等に機能する巡回シフト処理部３３を装備するようにしてもよい。【００５０】
尚、この巡回シフト処理部２３，３３は、読み出しポート側或いは書き込みポート側の一方が、他方を共有できるため、必ずしも読み出しポートと書き込みポートの両方を装備する必要はなく、どちらか一方を備えるのみでよい。後述する動作説明の欄では、説明を簡単にするため、両方に備えている場合について説明する。【００５１】
図６に、復号装置２０の一部を構成するノード処理手段２４の一例を示す。この図６は、ノード処理手段２４を構成するｐ個の各ノード処理部２４０，２４１，２４２，２４３，…２４ｐ−１を最小値算出手段をもって構成した点に特徴を有する。【００５２】
この内、最小値算出手段（ノード処理部）２４０  は、そのデータ入力段に設けられ前記各減算器２５からの出力データを各４つの束に区分して入力し絶対値が小さい二つの数値と当該絶対値が最小の数値とを対応する入力ポートの番号と共に出力する複数の２／４データ処理部２４Ａと、この複数の各２／４データ処理部２４Ａの出力側に順次トーナメント形式に設けられた同一の機能を有する複数の２／４データ処理部２４Ｂとを備えている。【００５３】
これを更に詳述する。
この図６に示す最小値算出手段（ノード処理部）２４０  は、上述したように、トーナメント状に結線された２／４データ処理部２４Ａ，２４Ｂと、デマルチプレクサ２７Ｃと、排他的論理和回路２４Ｄとを含んで構成されている。この内、２／４データ処理部２４Ａ，２４Ｂは、上述したように、４つの正整数を入力し、その内で値の小さい二つと、最も小さい値が入力された入力ポート番号とを出力するように構成されている。【００５４】
トーナメント最下段（入力段）における２／４データ処理部２４Ａへの入力データは、当該最小値算出回路部（ノード処理部）２４０の入力データの絶対値とし、プラス／マイナスの符号を表す１ビットはの排他的論理和回路２４Ｄへ入力される。トーナメントの最上段における該２／４データ処理部２４Ｂの出力は、該最小値算出回路部（ノード処理部）２４１へのすべての入力データの絶対値の中で最小値Ｘ０と二番目に小さい値Ｘ１、及び最小値を入力した入力ポート番号Ｐとなる。
他の最小値算出手段（ノード処理部）２４１，２４２，２４３，…２４ｐ−１についても同様である。【００５５】
これにより、入力データ数ｋ個の入力数値の内の絶対値が最小の数値の入力ポートに対応する番号を出力する機能が実行される。そして、これに基づいて、前記ｋ個の入力数値の最上位ビット全体から選択したｋ−１個の最上位ビットの排他的論理和がすべて算出されるようになっている。【００５６】
また、図６において、デマルチプレクサ２４Ｃは、当該トーナメント最上段の２／４データ処理部２４Ｂの出力を入力し、該入力ポート番号Ｐと同番号の出力ポートにはＸ１を出力し、それ以外の番号の出力ポートにはＸ０を出力する。この最小値算出手段２４０，２４１，２４２…の各出力は、構成要素であるデマルチプレクサ２４Ｃの出力に、排他的論理和回路２４Ｄの出力結果に応じて符号ビット（１ビット）を付加して、それぞれ出力される。【００５７】
一方、上記最小値算出手段（ノード処理部）２４２４０，２４１，２４２…は、上記出力のほかに、図２に示す復号装置２０における第２の遅延素子２８への入力データとしても出力する。この第２の遅延素子２８への出力データは、前記トーナメントの最上段における前記２／４データ処理部２４Ｂの出力であるＸ０，Ｘ１，Ｐと、前記排他的論理和回路２４Ｄの各出力ビットである。【００５８】
〔動作説明１：符号化装置〕
最初に、図１の符号化装置１０の動作について説明する。
まず、送信データ系列をデータ分割手段１１によりＬ個の短系列に分割する短系列分割工程（ステップＳ５０１）と、この分割されたＬ個の短系列の各々を第１の符号化手段１２によりｍ段擬似巡回型低密度パリティ検査符号化方式によって長さＮ（Ｌ，ｍは自然数、Ｎはｍの倍数）の符号系列にそれぞれ符号化する第１の符号化工程（ステップＳ５０２）と、この第１の符号化手段１２から出力される長さＮの各符号系列に基づいて冗長系列出力手段１３が冗長系列を生成してこれを前記第１の符号化手段１２から出力される複数の符号系列と共に冗長系列のデータとして出力する冗長系列生成出力工程（ステップＳ５０３）とを備えている。【００５９】
そして、この冗長系列のデータ出力（ステップＳ５０３）に際しては、前記第１の符号化手段１２で符号化された長さＮでＬ個の符号系列をデータ置換手段１４が入力し且つ各データ系列の順序を入れ換えて出力する工程（ステップＳ５０３−(1)）が実行され、その後に、この出力される置換された符号系列の各々を第２の符号化手段１５によってｍ段擬似巡回型低密度パリティ検査符号化方式に符号化（誤り訂正符号化）する工程（ステップＳ５０３−(2)）が実行される。【００６０】
ここで、上記データ置換手段１４が実行する入力データに対するデータ系列の順序を入れ換えて出力する工程（ステップＳ５０３−(1)）にあっては、前記第１の符号化手段１２で符号化されたＬ個のデータ系列の各々を前記第１の擬似巡回型低密度パリティ検査符号の段数ｍと同数の長さｍの短系列に分割する（小ブロックに区切る）工程を短系列分割部１４Ａが実行し（ステップＳ５０３−(1)ａ）、この分割によって設定される(L×N)／ｍ個で長さｍの短系列単位で順序を入れ替えて、Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力する工程（ステップＳ５０３−(1)ｂ）をデータ置換部１６が実行するように構成した。【００６１】
更に、データ置換部１６が実行する短系列単位での順序を入れ替える工程（ステップＳ５０３−(1)ｂ）では、Ｌ個の入力ポートを備えると共にＮ個の出力ポートを備えたセレクタ１４Ｂが前記振り分け工程を実行し、これにより出力される各小ブロックを巡環置換する工程を複数の巡環置換器から成る巡環置換回路１４Ｃが実行するようにし、これにより、前記Ｎ／ｍ個で長さが最大Ｌ×ｍの系列を出力する手順となっている。【００６２】
これを更に具体的に説明する。
上記符号化装置１０にあっては、前述したように、まず、長さＫの送信データ系列１０１を取り込み、データ分割部１１で長さＫ０，Ｋ１，…ＫＬ−１のＬ個の短系列に分割する（Ｋ０，Ｋ１，…ＫＬ−１とＬは自然数）。次に、この分割されたＬ個の各送信データ短系列１０２を、対応するＬ個の符号化処理部１２０，１２１，……１２Ｌ−１を備えた第１の符号化手段１２によって符号化する。【００６３】
即ち、図１のｍ段低密度パリティ検査符号の符号化手段である第１の符号化手段１２は、前述した長さＫの送信データ系列をそれぞれＬ個（Ｌは自然数）に分割した各系列を長さＮの系列にそれぞれ符号化する。
そして、このＬ個の長さＮの符号系列１０３は、図１に示すように第１の符号化手段１２出力されると共に、データ置換手段１４へ入力される。【００６４】
このデータ置換手段１４は、前述したＬ個の長さＮの符号系列１０３を長さＬ×ｍ以下のデータ系列１０４に置換して最大ｎ個出力する（ｎはＮをｍで割った値を表す）。この最大長Ｌ×ｍのデータ系列１０４の各々は、続いて、第２の符号化手段（ｍ段擬似巡回型低密度パリティ検査符号化手段）１５はよって符号化され、これによって冗長化された符号系列を算出し出力する。
この符号系列から前記第２の符号化手段１５への入力系列を除いた長さＳ×ｍ（Ｓは自然数）のパリティ系列が、前記データ置換手段１４の出力系列数と同数（最大ｎ個）出力される。【００６５】
これを更に詳述する。
図３に示すデータ置換手段１４は、前述したようにＬ個の長さＮの系列を入力する。ここで、図３におけるＬ個のデータ系列１０３を、便宜上、左から入力系列０、入力系列１、…、入力系列Ｌ−１とする。【００６６】
次に、この入力したデータ系列１０３の各々を、置換用分割部１４Ａによって前述した段数ｍと同数の長さｍの小ブロックに分割し、ｎ個の長さｍの小ブロックからなる系列データとして（ｎはＮをｍで割った値）、データ置換部１６のセレクタ１４Ｂへ入力する。このセレクタ１４Ｂは、Ｌ個の入力ポートとｎ個の出力ポートを持っており、この各入出力ポートを、便宜上、左から０、１、２、…の順序で番号付けると入力ポート０に入力系列０が入力され、入力ポート１に入力系列１が入力される（以下同様）。【００６７】
このセレクタ１４Ｂへの入力は、小ブロック単位で行われ、当該Ｌ個の入力ポートから入力されたＬ個の小ブロックの各々は、ｎ個の出力ポートのいずれかへ振り分けられるか、もしくは破棄される。この出力ポートの各々から出力される小ブロック数は最大Ｌ個となる。そして、このセレクタ１４Ｂへ入力された小ブロックの出力ポートへの振り分けは、同一出力ポートから出力される各小ブロックの入力ポートがすべて異なるように設定される。【００６８】
即ち、このセレクタ１４Ｂの出力ポートＸからは最大Ｌ個の小ブロックが出力されるが（Ｘは０からｎ―１の間の整数）、当該小ブロックの中で入力ポートＹから入力された小ブロック数をＴ（Ｘ，Ｙ）とすると、０からＬ−１の間のすべての整数Ｙについて、Ｔ（Ｘ，Ｙ）が１以下になるように設定される。
このセレクタ１４Ｂの出力ポートから出力される各小ブロックは、巡回置換部１４Ｃによってデータ系列毎に対応処理され巡回置換されて、本データ置換手段１４の出力となる。【００６９】
上述したデータ置換手段１４の置換出力処理部１６の一部を成すセレクタ１４Ａの動作例を図４に示す。この図４に示すセレクタ１４Ａの動作例は、図４（Ａ）では入力ポート数Ｌが出力ポート数ｎ（＝Ｎ／ｍ）に一致している場合、図４（Ｂ）では入力ポート数Ｌが出力ポート数ｎより小さい場合、図４（Ｃ）では入力ポート数Ｌが出力ポート数ｎより大きい場合、について示す。
いずれの場合も、同一出力ポートから出力される各小ブロックの入力ポートが、すべて異なるように設定されている。特に図４（Ｃ）では入力小ブロックの一部がいずれの出力ポートにも現れず、破棄された場合が示されている。【００７０】
上記符号化装置１０の出力データとなるフレーム構成の一例を図５に示す。
この図５において、上段Ｌ行に水平方向に並べられたｎ個の長さｍの小ブロックは、前述した図１に開示した第１の符号化手段１２におけるｍ段低密度パリティ検査符号の符号語を構成するシンボルとなっている。一方、図１に開示した第２の符号化手段１５におけるｍ段低密度パリティ検査符号の符号語を構成するＬ＋Ｓ個の小ブロックの各々は、同一行及び同一列に現れないように、前述したデータ置換手段１４によって置換配置されている。【００７１】
〔動作説明２：復号装置〕
前述した図５では、誤り訂正符号化装置１０の出力データのフレーム構成の一例を開示した。この図５に示すフレーム構成のデータが通信路を通って伝送される途中で雑音が加わり、復調器等を通って、受信データとして該復号装置２０に入力される。【００７２】
この復号装置２０では、誤り訂正符号化装置１０で符号化され送信されてきたデータを複号すると共にエラーが付加されている場合に当該エラーを訂正するように動作する。
この場合、まず、前記誤り訂正符号化装置１０から送信されてくるデータの内、当該誤り訂正符号化装置１０が有する第１の符号化手段１２で処理された複数の符号化系列のデータと前記誤り訂正符号化装置１０が有する冗長系列算出手段１３で処理された複数の符号化系列のデータとを、複数の記憶部からなるデータ記憶手段２１に分けて記憶される（ステップＳ６０１）。【００７３】
続いて、各データ記憶部２１に対応して併設され当該各データ記憶部のアドレスに保持されているデータを予め設定されたアドレス生成手順に従って読み出して更新処理し再び元のデータ記憶手段２１の同一アドレスに記憶する更新動作を、復号用更新処理手段２２が、前記アドレス生成手順にて特定された回数分繰り返えして実行する（ステップＳ６０２）。【００７４】
ここで、複数の各データ記憶部（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１に保持されたデータの内、予め設定された前記アドレス生成手順によって特定される各シンボルの最上位ビットを前記各データ記憶手段に書き込んだ時とは逆の手順で取り出すと共にこれを復号データとして出力する復号データ出力制御工程をメモリコントローラ２０Ａが実行する（ステップＳ６０３）ようにした。【００７５】
以下、これを更に詳述する。
上記復号装置２０は、図２に示したように、前記ｎ（＝Ｎ／ｍ）個のランダム・アクセス・メモリ（ＲＡＭ：データ記憶部）２１０，２１１，２１２，…２１ｎ−１を備えたデータ記憶手段２１を備え、前述した受信データを当該データ記憶部２１０，２１１，２１２，…２１ｎ−１に対して以下に記すように格納する。【００７６】
まず、受信データを図５のフレーム構成に対応して図７に示すように、長さｍシンボル毎に区切り、各々をＦｊ（ｉ）と記す（ｉは０からＴ−１の間の整数、Ｔは前記Ｌ＋Ｓ、ｊは０からｎ−１の間の整数）。
この記号Ｆｊ（ｉ）は、ｍ個のシンボルｆｊ（ｉ）（０），ｆｊ（ｉ）（１），…，ｆｊ（ｉ）（ｍ−１）からなり、各シンボルはｂビットのデータを表す（ｂは自然数）。【００７７】
前記ｎ個のＲＡＭ２１０，２１１…を、０からｎ−１の整数で番号付けると、第ｊ番目の該ＲＡＭの第（ｍ／ｐ）×ｉ＋ｋのアドレス（ｉは０からＴ−１の間の整数、ｋは０から（ｍ／ｐ）−1の間の整数）には、ｐ個のデータｆｊ（ｉ）（ｋ），ｆｊ（ｉ）（（ｍ／ｐ）＋ｋ），ｆｊ（ｉ）（２×（ｍ／ｐ）＋ｋ），…，ｆｊ（ｉ）（（ｐ−１）×（ｍ／ｐ）＋ｋ）が格納される。【００７８】
この図２の復号装置２０は、前記受信データを前記ｎ個のＲＡＭ２１０，２１１…に格納し、各遅延素子２６，２８をゼロに初期化した状態で復号処理を始動させる。
まず、ｎ個のＲＡＭ２１０，２１１…からデータを読み出す。そして、その読み出しアドレスの生成を、以下のようにして行う。
ここで、図１中のＬ個の第１の符号化手段（ｍ段擬似巡回低密度パリティ検査符号化手段）１２の検査行列を下記の次式２とする。
【数２】
2010073922.tif 000004
【００７９】
記号ｉは０からＬ−１の間の整数とする。又、以下では記述を簡単にするため、０からＬ−１の間の整数ｉに関して、式２の行列  Ｈ（ｉ）の行ベクトル数ｒｉが同一の自然数ｒであるとする。
この各整数ｉによって行ベクトル数が異なる場合は、復号処理に要する処理時間（クロック）数が変わるだけで基本的には同一である。【００８０】
今、記号ｈｋ，ｊ（ｉ）を、式２の検査行列に関する（ｋ，ｊ）成分であるｍ×ｍ巡回置換行列Ｉｋ，ｊ（ｉ）の第一行ベクトルにおける非零成分位置を表す整数「０≦ｈｋ，ｊ（ｉ）＜ｍ」とすると、時間パラメータｔ＝０からｔ＝（ｍ／ｐ）×Ｌ−１における第ｊランダム・アクセス・メモリの読み出しアドレス値「Ａ（０）（ｊ，ｔ）」は、次の式３で算出される（ｊは０からｎ−１の間の整数）。
【数３】
2010073922.tif 000005
【００８１】
ここで、「ｔ／（ｍ／ｐ）」は、ｔを（ｍ／ｐ）で割った商を表す。次いで、時間パラメータｔをリセットし、次の時間ｔ＝０からｔ＝（ｍ／ｐ）×Ｌ−１における第ｊランダム・アクセス・メモリの読み出しアドレス値「Ａ（１）（ｊ，ｔ）」を、次の式４で算出する。
【数４】
2010073922.tif 000006
【００８２】
以下、同様にして、一般に時間パラメータをｔとすると、ｔ＝０からｔ＝（ｍ／ｐ）×Ｌ−１における第ｊランダム・アクセス・メモリの読み出しアドレス値「Ａ（ｋ）（ｊ，ｔ）」を次の式５で算出する（ｋは０からｒ−1 の間の整数）。
【数５】
2010073922.tif 000007
【００８３】
上記読出しアドレス値「Ａ（ｋ）（ｊ，ｔ）」は、前述した第１の符号化手段１２にかかる擬似巡回型低密度パリティ検査符号の検査行列を示す式２から、上記式５を用いて算出される。即ち、アドレス値  Ａ（０）（ｊ，ｔ），Ａ（１）（ｊ，ｔ），……，Ａ（ｒ−１）（ｊ，ｔ）に従ってｎ個のＲＡＭ２１０，２１１，２１２，……２１ｎ−１からデータを逐次読み出す。この場合、全体では、（ｍ／ｐ）×Ｌ×ｒの時間を要する。【００８４】
次に、図１における第２の符号化手段１５にかかるｎ個の擬似巡回型低密度パリティ検査符号の検査行列を示す式６を用いて、読出しアドレス値を算出する方法について説明する。ここで、式２の場合と同様に、説明を単純にするため行ブロック数ｉ（ｉは０からｎ−１の間の整数）によらず一定の自然数Ｉにする。
【数６】
2010073922.tif 000008
【００８５】
前述した図５に示すフレーム構成例において、左から「Ｒ（ｉ）(０)，Ｒ１（ｉ）（１），…，Ｒ（ｉ）（Ｌ＋Ｓ−１）」番目の小ブロックが、図１における第２の符号化手段１５にかかるｎ個の擬似巡回型低密度パリティ検査符号の内、第ｉ番目の低密度パリティ検査符号語を構成しているものとする（ｉは０からｎ−１の間の整数）。【００８６】
前述した図３（データ置換手段１４）に開示された構成及び図４（コレクタの動作）に示すように、０からＬ＋Ｓ−１の間の互いに異なる整数ａ，ｂに対しては、Ｒ（ｉ）（ａ）≠Ｒ（ｉ）（ｂ）となる。
そして、上記したように、（ｍ／ｐ）×Ｌ×ｒステップかけて、式５によって逐次アドレス値を算出した後、時刻パラメータｔをリセットして、時間ｔ＝０から時間ｔ＝（ｍ／ｐ）×ｎ−１における、第ｊランダム・アクセス・メモリの読み出しアドレス値Ｂ（ｋ）（ｊ，ｔ）を、次の式７で算出する。
【数７】
2010073922.tif 000009
【００８７】
ここで、記号ｋは０からＩ−１の間の整数であり、またψ（ｊ，ｔ）は、前記したＲ（［ｔ／（ｍ／ｐ）］）（ｊ）の逆関数であって、次の（式８）を満たす０からＬ＋Ｓ−１の間の整数である。
【数８】
2010073922.tif 000010
【００８８】
以上、前記Ａ（０）（ｊ，ｔ），Ａ（１）（ｊ，ｔ），……，Ａ（ｒ−１）（ｊ，ｔ）に従ってアドレス値を算出し、前記Ｂ（０）（ｊ，ｔ），Ｂ（１）（ｊ，ｔ），……，Ｂ（１）（ｊ，ｔ），……，Ｂ（Ｉ−１）（ｊ，ｔ）に従ってアドレス値を算出する。ここで、アドレス値算出の順序は必ずしも前記順序でなくてもよく、Ｂ（０）（ｊ，ｔ），Ｂ（１）（ｊ，ｔ），…，Ｂ（Ｉ−１）（ｊ，ｔ）が先でも良い。【００８９】
以上のように、トータルで（ｍ／ｐ）×Ｌ×ｒ＋（ｍ／ｐ）×ｎ×Ｉステップを一周期としてデータをランダム・アクセス・メモリ（ＲＡＭ）２１０，２１１，２１２，……２１ｎ−１から逐次読み出していく。【００９０】
図８に、上記式５と式７のアクセス方法の違いを示す。
前述したｎ個の各ＲＡＭ２１０，２１１，２１２，…２１ｎ−１のアドレス値を、０〜（ｍ／ｐ）−１、ｍ／ｐ〜２（ｍ／ｐ）−１、……のように長さｍ／ｐの区間で区切ると、上述した式５により算出されるアドレス値に従ってアクセスされる領域は、全てのランダム・アクセス・メモリ（ＲＡＭ）２１０，２１１，２１２，…２１ｎ−１において同一の区間となる（図６中、アクセス領域（Ａ）参照）。【００９１】
これに対し、式７により算出されるアドレス値に従ってアクセスされる領域は、互いに異なる区間となる（図６中、アクセス領域（Ｂ）参照）。この式７のアドレス値に従ってアクセスされる領域は、前述した図３のデータ置換手段１４によって規定される。このため、換言すると、式７により算出されるアドレス値に従ってアクセスされる領域が互いに異なる区間となるように、図３に示すデータ置換手段１４を予めその機能内容を特定しておくことが重要となる。【００９２】
以上に説明した手順で、ＲＡＭ２１０，２１１，２１２，…２１ｎ−１より読み出されるデータは、巡回シフト回路２３０，２３１，２３２，…２３ｎ−１からなる巡回シフト処理部２３へ入力される。
このように、ＲＡＭ２１０，２１１，２１２，…２１ｎ−１のビット長はｐシンボル分であり（ｂ×ｐビット）、巡回シフト処理部２３は予め定められたシフト量だけ、ｐシンボル分のデータをシンボル毎に巡回シフトする。該シフト量は前記読出しアドレスに関連つけて定まり、式５によって算出されたアドレス値  Ａ（ｋ）（ｊ，ｔ）で読み出したデータに関するシフト量は次の式９で算出される。
【数９】
2010073922.tif 000011
【００９３】
同様に、式７によって算出されたアドレス値Ｂ（ｋ）（ｊ，ｔ）で読み出したデータに関するシフト量は、次の式１０で算出される。
【数１０】
2010073922.tif 000012
【００９４】
図９に、上述した巡回シフト処理部２３の動作の一例を示す。
この図７は、前述したｐシンボル分のデータ列を図７中の下方向へｘ個巡回シフト（ｘは０からｐ−１の間の整数）したデータ列を出力する。
前述したｎ個のＲＡＭ２１０，２１１，２１２，…２１ｎ−１より、式５と式７によって読み出されたデータは式９と式１０に記載された量だけ巡回シフトされ、遅延素子部２８ａ，２８ｂ，…を備えた第２の遅延素子２８の出力データを減算し、遅延素子部２６０，２６１…２６ｎ−１を備えた第１の遅延素子２６およびｐ個のノード処理部２４０，２４１，２４２，…２４ｐ−１を備えたノード処理手段２４とへそれぞれ入力される。【００９５】
この場合、第１の遅延素子２６のデータは初期値をゼロとしておくため、一巡目ではゼロが減算される（変化なし）。図２の復号処理装置２０はｐ個のノード処理部２４０，２４１，２４２，…２４ｐ−１を備えたノード処理手段２４を備えており、前記ＲＡＭ２１０，２１１，２１２，…２１ｎ−１を起源とするｐシンボル分のデータをシンボル単位でｐ個に分割し、各々をｐ個の各ノード処理部２４０，２４１，２４２，…２４ｐ−１へ入力する。
ノード処理手段２４の各ノード処理部２４０，２４１，２４２，…２４ｐ−１は、前記ｎ個のＲＡＭ２１０，２１１，２１２，…２１ｎ−１を起源とするデータの内、１シンボル分（合計ｎシンボル）を入力する。【００９６】
図３に開示した最小値算出手段は、本実施形態では、ノード処理手段２４の各ノード処理部２４０，２４１，２４２，…２４ｐ−１を構成するものである。この最小値算出手段（ノード処理部）２４０，２４１，２４２，…２４ｐ−１は、ｎ個のシンボルＹ０，Ｙ１，…，Ｙｎ−１を入力し、（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１を出力する機能を備えている。【００９７】
ここで、ｑｉ，Ｘｉは次の式１１、式１２で算出される。
【数１１】
2010073922.tif 000013
【００９８】
【数１２】
2010073922.tif 000014
【００９９】
ここで、ｓ（Ｙ）はＹ＜０の時は１、Ｙ≧０の時は０とする。又、記号＝は排他的論理和を表す。上記最小値算出手段（ノード処理部）２４０，２４１，２４２，…２４ｐ−１の各出力は、（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１であり、これを前記第１の遅延素子２６の各遅延素子部２６０，２６１，２６２，…２６ｎ−１を経由したデータと加算し、対応する巡回シフト回路３３０，３３１，３３２，……を介して、対応する前記ＲＡＭ２１０，２１１，２１２，…２１ｎ−１に書き込む。【０１００】
ここで、巡回シフト処理部３３におけるシフト量は、読出し時に使用した巡回シフト処理部２３のシフト量を相殺するものとする。即ち、読出し時に使用した巡回シフト処理部２３において下方向へｘ個巡回シフトした場合には（図７参照）、巡回シフト処理部３３では上方向へｘ個巡回シフト（下方向へｐ−ｘ個シフト）するものとする。
この巡回シフト処理部３３を通したデータを前述したＲＡＭ２１０，２１１，２１２，…２１ｎ−１に書き込む際には、前述した式５と式７とによってアドレス計算された読出しアドレスと同じアドレスに書き込むものとする。【０１０１】
ノード処理手段２４の出力データは、上述したように第１の遅延素子２６の各遅延素子部２６０，２６１，２６２，…２６ｎ−１の出力データと加算される他、第２の遅延素子２８の各遅延素子部へ入力される。
前記ノード処理手段２４の各ノード処理部２４０，２４１，２４２，…２４ｐ−１として前述したように最小値算出手段を用いた場合は、出力データ（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１をそのまま第２の遅延素子２８へ入力する代わりに、前述した構成の欄に開示したように、前記Ｘ０、Ｘ１、Ｐと前記排他的論理和の各出力ビットを入力することで、遅延素子で使用される記憶容量を有効に削減することができる。【０１０２】
このため、ノード処理手段２４の各ノード処理部２４０，２４１，２４２，…２４ｐ−１として上述したように最小値算出手段（図６参照）を用いる場合には図６に開示したように、前記Ｘ０、Ｘ１、Ｐと前記排他的論理和回路２４Ｄの各出力ビットを図２の第２の遅延素子２８へ入力するものとする。この場合、この第２の遅延素子２８の出力側では、各減算器２５へ入力する前に、前記Ｘ０、Ｘ１、Ｐと前記排他的論理和回路２４Ｄの各出力ビットから、前記（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１を生成する装置が必要となる。【０１０３】
このように、ｎ個のＲＡＭ２１０，２１１，２１２，…２１ｎ−１から式５と式７に示したアドレス生成手順によって読み出されたデータが、前記ノード処理手段２４を経由して更新され、再びＲＡＭ２１０，２１１，２１２，…２１ｎ−１の同一アドレスに記憶される。この式５と式７に示したアドレスすべてに。わたって、上記更新処理を行った段階で、一回の復号処理（一周期分）が終了する。【０１０４】
この場合、一回の復号処理に際しては、最低でも（ｍ／ｐ）×Ｌ×ｒ＋（ｍ／ｐ）×ｎ×Ｉ回のステップを必要となる。二回目の復号処理は一回目と全く同様の手順で、式５と式７とに示したアドレス生成手順に従って、前記ＲＡＭ２１０，２１１，２１２，…２１ｎ−１からデータを読出し、更新して、書き込む。三回目以降も全く同様であり、予め定めた所定の回数を繰り返した後、前記ＲＡＭ２１０，２１１，２１２，…２１ｎ−１内に保持されたデータの各シンボルにおける最上位ビットを（前記受信データを該ランダム・アクセス・メモリに書き込んだ際と逆の手順で）取り出し、出力する。この出力データが、復号結果となる。【０１０５】
尚、前述した第２の遅延素子２８の遅延量は一回の繰り返し復号処理に要するステップ数と一致する。従って、一回目の復号処理の際には、減算器２５の前記第２の遅延素子２８側の入力はゼロであったが、二回目以降の復号処理においては、当該減算器２５の第２の遅延素子２８側の入力は、直前の復号処理においてノード処理手段２４から出力されたデータとなる。【０１０６】
ここで、上述した各構成要素の機能および当該各構成要素相互間の応答動作については、これを実行可能にプログラム化し、コンピュータに実行させるように構成してもよい。なお、前記プログラムは記録媒体に記録されて商取引の対象となる。【０１０７】
このように、上記第１実施形態にあっては、送信データ系列をＬ個の短系列に分割し、Ｌ個の該短系列の各々をｍ段擬似巡回型低密度パリティ検査符号化方式によって符号化し、出力すると共に、Ｌ個の該符号化系列の各々を前記擬似巡回符号の段数ｍと同じ数の長さｍの短系列に分割し、データ置換手段１４によって順序を入れ替えた後、さらにｍ段擬似巡回型低密度パリティ検査符号化方式によって符号化する構成としたものである。これにより、前記段数ｍの約数ｐ個の、ノード処理手段（最小値算出装置、あるいは積装置）を有する構成の単純な復号装置により、フレーム長が大きく、符号化利得の大きな符号の効率的な復号処理が可能となる。【０１０８】
以上説明したように、本第１の実施形態は、上記の如く構成され機能するので、これによると、送信データ系列の符号化に際しては、基本的に、ｍ段擬似巡回型低密度パリティ検査符号化方式を一方の符号化手段によって符号化を実行し、データ置換手段を介して冗長系列を置換出力したものを更に他方の符号化手段で符号化するという複数の組み合わせて符号化する構成としたので、フレーム長の増大によって符号化利得が大きく改善されるという優れた効果を奏する誤り訂正符号化装置、符号化方法及びそのプログラムを提供することができる。【０１０９】
又、受信側にあって、符号化されたデータ系列の復号化に際しては、フレーム長の増大されたデータ系列が送り込まれても前述した送信データ系列の符号化の場合と同様のｍ段擬似巡回型低密度パリティ検査符号に対応した復号化処理が実行されるので、回路規模の増大や使用メモリ個数の増大を伴うことなく復号処理が可能となり、これにより、復号処理の高速化、復号処理動作時における消費電力の抑制という優れ効果を奏する復号装置、復号方法及びそのプログラムを提供することができる。
〔第２の実施形態〕【０１１０】
次に、本発明の第２の実施形態を図１０に基づいて説明する。
ここで、前述した第１実施形態と同一の構成部材については同一の符号を用いるものとする。【０１１１】
この第２実施形態では、前述した図２に示す復号装置２０において、ノード処理手段２４を構成する各ノード処理部２４０，２４１，２４２，…２４ｎ−１として装備した最小値算出手段に代えて、図１０に示す積回路（積装置）３４を使用した点に特徴を有する。その他の構成は、前述した図２の開示内容と同一となっている。また、図１に開示した符号化装置１０についても、そのまま、本第２実施形態に採用されている。【０１１２】
この図１０に示す積回路３４は、複数のデータ系列に対応してそれぞれ複数の加算器３４Ａと、第１，第２の変換テーブル３４Ｂ，３４Ｆと、排他的論理和回路３４Ｃと、減算器３４Ｅとを備えている。【０１１３】
前述した第１実施形態における復号装置２０（図２参照）で開示したように、ノード処理手段２４の各ノード処理部２４０，２４１，２４２，…２４ｐ−１は、前述したｎ個のＲＡＭ２１０，２１１，２１２，…２１ｎ−１を起源とするデータの内、１シンボル分（合計ｎシンボル）を入力する。【０１１４】
この図１０に示す積回路３４も、同様に前述したｎ個のＲＡＭ２１０，２１１，２１２，…２１ｎ−１から、ｎ個のシンボルＹ０，Ｙ１，…，Ｙｎ−１を入力し、（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１を出力する機能を備えている。
ここで、Ｘｉ  は、次の式１３で与えられる（ｉは０からｎ−１の間の整数）。又、ｑｉは、前述した式１１で与えられる。
【数１３】
2010073922.tif 000015
【０１１５】
ここで、式１３におけるＴ（Ｙ）は、次の式１４で与えられる。
【数１４】
2010073922.tif 000016
【０１１６】
上記図１０に示すように、上記第１の変換テーブル３４Ｂは、外部からの要請に応じて、入力シンボルＹに対して式１４のＴ（Ｙ）を出力するように構成されている。又、第２の変換テーブル３４Ｅの変換テーブルは、入力データＹに対して、Ｔ（Ｘ）＝ＹとなるシンボルＸを出力するテーブルとして機能する（これは、予めＴ（Ｙ）の逆関数をテーブル化してある）。【０１１７】
一方、この図１０に示す積回路３４をノード処理手段２４として使用した本第２実施形態にあっては、前述した図６の最小値算出手段を使用した場合と異なり、図１０における出力データ「（−１）ｑ０Ｘ０，（−１）ｑ１Ｘ１，…，（−１）ｑｎ−１Ｘｎ−１」を、そのままに状態で前述した第２の遅延素子２８へ入力する。
その他の構成およびその作用効果は、前述した第１実施形態の場合と同一となっている。
ここで、上述した各構成要素が備えている機能および構成要素相互間の連携機能については、これを実行可能にプログラム化しコンピュータに実行させるように構成してもよい。なお、前記プログラムは記録媒体に記録されて商取引の対象となる。【０１１８】
このように、上記第２実施形態にあっては、ノード処理手段２４として前述した最小値算出手段（図３）と同等に機能する積装置３４を使用したので、前述した第１実施形態の場合と同等の作用効果を得ることが可能な復号装置２０を得ることができ、更に、積回路（積装置）３４の出力をそのまま第２の遅延素子２８へ入力し得るので、受信データの格納処理をより迅速に成し得るという利点がある。
〔第３の実施形態〕【０１１９】
次に、本発明の第３の実施形態を、図１１に基づいて説明する。
この第３の実施形態では、前述した図１に開示した誤り訂正符号化装置１０において、前記データ置換手段１４を第１の置換手段１４とすると共に、前記第２の符号化手段１５で符号化されるＮ／ｍ個の符号系列で長さＳ×ｍのパリティ部分の各々を入力し、順序を入れ替えてＳ個の長さＮの系列を出力する第２の置換手段４４を新たに装備した点に特徴を有する。【０１２０】
更に、この第２の置換手段４４の出力であるＳ個の長さＮの系列の一部分を、段数ｍで長さＮの擬似巡回型低密度パリティ検査符号で符号化する複数の符号化処理部を備えた第３の符号化手段４５を装備した。
そして、この第３の符号化手段４５で符号化されたパリティ部分の各々を、前記第２の符号化手段１５で符号化されたＬ個のデータ系列と同様に、符号化された送信データとして出力するようになっている。【０１２１】
即ち、この第３の実施形態では、図１の誤り訂正符号化装置１０において、第２の符号化手段（ｍ段低密度パリティ検査符号化手段）１５の出力側に第２の置換手段４４を装備し、更に、この第２の置換手段４４の出力側に、前述した第１の符号化手段１２と同等に機能するｍ段低密度パリティ検査符号化手段である第３の符号化手段４５を装備する構成とした。
その他の構成およびその作用効果は、前述した第１実施形態の場合と同一となっている。【０１２２】
ここで、上述した各構成要素が備えている機能および構成要素相互間の連携した応答機能については、これを実行可能にプログラム化しコンピュータに実行させるように構成してもよい。なお、前記プログラムは記録媒体に記録されて商取引の対象となる。【０１２３】
このようにしても、前述した図１の構成において説明した自然数Ｌ，ｎ，Ｓの設定によっては、図５に示したフレーム構成の符号系列を生成することができ、図２の復号装置２０によって復号処理することができ、かかる点において、前述した第１実施形態と同等の作用効果を得ることができる。
〔第４の実施形態〕【０１２４】
本発明にかかる符号化装置および復号装置を使用したデータ通信装置１００の一例を図１２に示す。【０１２５】
データの送信側（送信機８０）は、本発明の上記各実施形態における符号化装置１０、フレーム同期をとるための制御および変調器に合わせたデータ変換をするための同期制御・変調期入力生成装置８２、及び変調器８３からなる。変調器８３の出力は無線通信路（或いは記憶装置）へ出力される。符号８４は送信アンテナを示す。【０１２６】
又、データの受信側（受信機９０）は、無線通信路（或いは記憶装置）から得られる情報を復調する復調器９２と、この復調器９２の出力データを復号器用の入力データへ変換し且つフレーム同期をとる処理を行う同期制御・復号入力生成装置９３、及び本発明にかかる上記各実施形態における復号装置２０とにより構成されている。符号９１は受信アンテナを示す。
その他の構成およびその作用効果は前述した第１の実施形態と同一となっている。【０１２７】
これにより、前述した各実施形態における符号化装置１０および復号装置２０が、上記送信機８０および受信機９０内で効果的に機能し、これにより、データ通信が装置全体で円滑に機能することとなる。
【実施例１】
【０１２８】
次に、前述した第１実施形態における誤り訂正符号化装置１０および復号装置２０について、より具体化した実施例を、数値例を用いて説明する。【０１２９】
図１の符号化処理装置１０において、前記自然数Ｌ，ｎ，Ｓを各々Ｌ＝６３、ｎ＝６５、Ｓ＝１とし、第１の符号化手段１２の各符号化処理部１２０，１２１，……１２Ｌ−１で対象とする擬似巡回型低密度パリティ検査符号の段数ｍを６３とする。この図１における各符号化処理部１２０，１２１，……１２Ｌ−１にある６３個の擬似巡回低密度パリティ検査符号の検査行列を示す式１において、行ブロック数ｒ＝４とし、Ｉ０，２＝Ｉ１，６４＝Ｉ２，６３＝Ｉ３，６２＝０（６３×６３のゼロ行列）とする。【０１３０】
この場合、第１の符号化手段１２の出力は４０９５ビット（Ｎ＝ｍ×ｎ＝６３×６５）であり、合計４０９５×６３ビットが図１のデータ置換手段１４に入力される。
ここで、このデータ置換手段１４の入力ポート数を６３とし、出力ポート数を６５とする。この各入力ポートには、ブロック長６３ビットの小ブロックに分割された６３段擬似巡回低密度パリティ検査符号の出力（第１の符号化手段１２の出力）である６５ブロック分の符号化データが入力される。【０１３１】
そして、この入力ポートを０から６２の整数で、又この出力ポートを０から６４の整数で番号を付ける。このデータ置換手段１４の入力ポートｉのｊ番目の小ブロック（ｉは０から６２の間の整数、ｊは０から６２の間の整数）を、（６５＋ｉ−ｊ）を６５で割った余りに一致する出力ポートへ出力する。【０１３２】
この入力―出力間の各置換は、データ置換手段１４の図３に開示したデータ置換手段１４の説明において挙げた条件を満たす。このデータ置換手段１４の出力側にある巡回置換手段１６Ｂのシフト量はランダムに定めてよいが、仮に、ｋ番目の前記出力ポート（ｋは０から６４の間の整数）にある巡回置換手段１６Ｂの第ｈ番目の小ブロック出力時（ｈは０から６２）におけるシフト量（ｋ＋ｈ）を６３で割った余りに一致するものとする。【０１３３】
前記６５個の該出力ポートから出力された長さ６３の小ブロックからなる系列を、各々図１の第２の符号化手段（６３段低密度パリティ検査符号化手段）１５によって符号化する。
ここで、この第２の符号化手段１５の検査行列である式６における行ブロック数をＩ１，０＝１とする。この第２の符号化手段１５では６５個の符号化処理部１５０，１５１，……１５Ｌ−１の各出力（６３段低密度パリティ検査符号化手段の各出力）におけるパリティ部分６５×６３ビットを、前記４０９５×６３ビットの第１の符号化手段（６３段擬似巡回低密度パリティ検査符号化手段）１２の出力と共に出力する。【０１３４】
この数値例におけるフレーム構成は、図５においてｍ＝６３、Ｎ＝４０９５，Ｌ＝６３、Ｓ＝１としたものであり、最下段のデータ列である前記６５個の第１の符号化手段（６３段低密度パリティ検査符号化手段）の出力におけるパリティ部分６５×６３ビットを次のように配置することで、図５の説明において挙げた条件を満たす。【０１３５】
最下段のデータ列を小ブロック（長さ６３ビット）毎に左から並べる時、左端を０番目、右端を６４番目とすると、データ置換手段１４の第ｋ番目の出力ポートから出た小ブロック系列に直結する６３段低密度パリティ検査符号化手段（第１の符号化手段）１２から出力されたパリティ６３ビットを（ｋは０から６４の間の整数）、「６５＋６３−ｋ」を６５で割った余りに一致する位置におくことにする。上記数値例に対する復号装置２０（図２参照）では、例えば前述したｐ（ｐはｍ＝６３の約数）を７とした場合、７個のノード処理部を備えたノード処理手段２４と６５個のＲＡＭを備えた構成となる。【０１３６】
この場合、一回の復号処理に要するステップ数は（６３／７）×６３×４＋（６３／７）×６５×１＝２８５３となる。これは図２における第２の遅延素子の遅延量の下限となる。また、１シンボル＝７ビット（ｂ＝７）とすると、該６５個のＲＡＭの各々はビット幅がｂ×ｐ＝７×７＝４９ビット、ワード数がｍ／ｐ×（Ｌ＋Ｓ）＝９×６４＝５７６となる。【０１３７】
次に、図１１に開示した実施形態の一例にかかる数値例について説明する。
図１１中の符号化手段（第１，第２の各符号化手段１２，１５）の部分に関しては、前述した数値例と同一とする。即ち、Ｌ＝６３、ｎ＝６５、Ｓ＝１、ｍ＝６３とする。
図１におけるデータ置換手段１４の構成も前述した数値例のデータ置換手段１４の場合と全く同様とするが、このデータ置換手段１４の出力ポートの内、出力ポート０，１，２，６４から出力される系列を破棄し、４つの出力ポート後に配置された第２の符号化手段１５の６３段擬似巡回符号化を行わないこととする。【０１３８】
この時点で、前述した図５のフレーム構成における最下段のデータ列は左端（０番目）から６０番目までは、図１の上記数値例と同様に第１の符号化手段１２に出力（図１の低密度パリティ検査符号のパリティ部分）が割当てられるが、６１番目から６４番目は前記出力ポート０，１，２，６４から出力される系列を破棄したため、空白となる。【０１３９】
図１１に開示した実施形態の一例においては、この部分は図１１の第２のデータ置換手段４４と第３の符号化手段（低密度パリティ検査符号化手段）４５を用いて算出する。
即ち、図１１の第３の置換手段４４は、前述したフレーム構成における最下段のデータ列の左端（０番目）から６０番目を左端（０番目）から順次出力し、それを１つの６３段低密度パリティ検査符号化手段（第３の符号化手段）４５に入力する。この該６３段低密度パリティ検査符号化手段（第３の符号化手段）４５は、前述した図１の６３段低密度パリティ検査符号化手段（第１の符号化手段）１２と同等の昨日を備えた符号化手段が使用されている。【０１４０】
即ち、本実施例における数値例では、図１１の第２の置換手段４４はシンボル毎にパラレル／シリアル変換する装置に相当し、その出力側に位置する図１１の低密度パリティ検査符号化符号（第３の符号化手段）４５は一つとなる。この第３の符号化手段４５の出力する符号系列のパリティ部分（４シンボル分）を前述した図５のフレーム構成における最下段のデータ列の６１番目から６４番目に割当てる。本実施例の数値例におけるフレーム構成は、前述した図５の説明において挙げた条件を満たす。【０１４１】
上記数値例に対する復号装置２０では、前述した符号化装置１０における数値例と同様にｐ＝７とした場合、７個のノード処理部から成るノード処理手段と６５個のＲＡＭを備える。一回の復号処理に要するステップ数は、図１の第２の符号化手段１５における低密度パリティ検査符号を４つ分破棄しているため、その分、式７で生成するアドレスが減り、図１１の第３の符号化手段４５で使用している一つの低密度パリティ検査符号を図１の低密度パリティ検査符号と同じにしているため、式５で生成するアドレスが増える。【０１４２】
従って、トータルで（６３／７）×（６３＋１）×４＋（６３／７）×（６５−４）×１＝２８５３となる。これは前述した数値例の場合と同様に復号装置２０における第２の遅延素子の各遅延素子部における遅延量の下限となる。また、１シンボル＝７ビット（ｂ＝７）とすると、該６５個のＲＡＭの各々はビット幅がｂ×ｐ＝７×７＝４９ビット、ワード数がｍ／ｐ×（Ｌ＋Ｓ）＝９×６４＝５７６となり、復号装置２０の規模は前述した図１の符号化装置１０における数値例と同様になる。【０１４３】
ここで、上述した各構成要素が備えている具体的な機能および構成要素相互間の具体的な連携機能については、これを実行可能にプログラム化しコンピュータに実行させるように構成してもよい。なお、前記プログラムは記録媒体に記録されて商取引の対象となる。【０１４４】
以上、実施形態（及び実施例）を参照して本願発明を説明したが、本願発明は上記実施形態（及び実施例）に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。【０１４５】
この出願は２００８年１２月２５日に出願された日本出願特願２００８−３３０９１０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１４６】
本発明の応用例として、衛星通信、あるいは移動体通信システム等における、所要電力の低減、アンテナの小型化などのシステム構成上の要件を満たすための誤り訂正技術として、或いは磁気記録などの記憶装置に関する信頼性向上のための誤り訂正技術としての適用が挙げられる。
【符号の説明】
【０１４７】
１０  誤り訂正符号化装置
１１  データ分割部
１２  第１の符号化手段（擬似巡回型低密度パリティ符号化手段）
１２０，１２１，…１２Ｌ−１符号化処理部
１３  冗長系列出力手段
１４  データ置換手段（第１の置換手段）
１４Ａ  短絡系分割部
１４Ｂ  セレクタ
１４Ｃ  巡回置換部
１４Ｃ０，１４Ｃ１，…１４ＣＬ−１巡回置換回路
１５  第２の符号化手段（擬似巡回型低密度パリティ符号化手段）
１５０，１５１，…１５ｎ−１符号化処理部
２０  復号装置
２０Ａ  メモリコントローラ
２１  データ記憶手段
２１０，２１１，…２１ｎ−１  データ記憶部
２３，３３  巡回シフト手段
２３０，２３１，…２３ｎ−１  巡回シフト部
２４  ノード処理手段
２４０，２４１，…２４ｐ−１  ノード処理部（最小値演算手段，積回路）
２４Ａ，２４Ｂ  2/4データ処理部
２４Ｃ  デマルチプレクサ
２４Ｄ  排他論理和回路
２５  減算器
２６  第１の遅延素子
２６０，２６１，…２６ｎ−１  遅延素子部
２８  第２の遅延素子
２９  加算器
３４０，３４１，…３４ｐ−１  ノード処理部（積回路）
３４Ａ  積回路の加算器
３４Ｂ  第１の変換テーブル
３４Ｃ  排他的論理和回路
３４Ｅ  積回路の減算器
３４Ｆ  第２の変換テーブル
４４  第２の置換手段
４５  第３の符号化手段
５１  同期制御・変調器入力生成装置
５２  変調器
６１  復調器
６２  同期制御・復号装置入力生成装置
【図１】
2010073922.tif 000017
【図２】
2010073922.tif 000018
【図３】
2010073922.tif 000019
【図４】
2010073922.tif 000020
【図５】
2010073922.tif 000021
【図６】
2010073922.tif 000022
【図７】
2010073922.tif 000023
【図８】
2010073922.tif 000024
【図９】
2010073922.tif 000025
【図１０】
2010073922.tif 000026
【図１１】
2010073922.tif 000027
【図１２】
2010073922.tif 000028
【国際調査報告】
2010073922.tif 000029
2010073922.tif 000030
2010073922.tif 000031
2010073922.tif 000032