(57)【特許請求の範囲】
【請求項１】
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードを複数のカテゴリに分類し、繰り返し復号における確率伝播計算に際し前記カテゴリ毎に予め決定された重み付けを伝播対象である対数尤度比（以下ＬＬＲと略す）に対して行うことを特徴として構成されるＬＤＰＣデコーダ。
【請求項２】
前記繰り返し復号における確率伝搬計算は、ｍｉｎＳｕｍアルゴリズムであって各カテゴリに属する検査マトリクスの列重みに合わせて重み付けする値を決定することを特徴として構成される請求項１項記載のＬＤＰＣデコーダ。
【請求項３】
前記タナーグラフとして、前記複数のカテゴリ内にＲＡ構造のカテゴリを有し、該カテゴリの重み付けは他のカテゴリの重み付けより大きくしたことを特徴として構成される請求項１または請求項２記載のＬＤＰＣデコーダ。
【請求項４】
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、グラフを構成する各ノードを、その検査マトリクスの列重みによる複数のグループ分けし、繰り返し復号における確率伝播計算に際しては、前記グループ毎に決定された重み付けを伝播対象である対数尤度比（ＬＬＲ）に対して行うことを特徴として構成されるＬＤＰＣデコーダ。
【請求項５】
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードを複数のカテゴリに分類し、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変えて該対数尤度比へのパラレルアクセスを可能にしたことを特徴として構成されるＬＤＰＣデコーダ。
【請求項６】
ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードは複数のカテゴリに分類することが可能であって、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変える構造を有し、前記対数尤度比へのパラレルアクセスを行う際、ＦＩＦＯ機能を有するキャッシング回路を介して行われることを特徴として構成される請求項５項記載のＬＤＰＣデコーダ。
【請求項７】
前記繰り返し復号における確率伝搬計算をｍｉｎＳｕｍアルゴリズムによって行う際、第１の最小値検出回路によって第１の最小値を検出し、該検出された第１の最小値に対応する入力をマスクして第２の最小値を検出する第２の最小値検出回路を有し、第１及び第２の最小値回路をパイプライン構造によって構成することにより等価的に一クロックで近似計算を実行することを特徴として構成される請求項２項記載のＬＤＰＣデコーダ。
【請求項８】
前記繰り返し復号における確率伝搬計算をｍｉｎＳｕｍアルゴリズムによって行う際、変数ノード分のＬＬＲを一時保存する第１のメモリと、請求項７記載の第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを有し、該第１のメモリへの入力は、請求項７記載の第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することによって順次行われ、該第１のメモリは、請求項２記載のカテゴリ分けがなされていて、カテゴリ毎に予め決められた重み付けを該第１のメモリ出力に対して行われ、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報によって選択される値を差引き、再びＭａｘＬｏｇ近似ｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を特徴として構成される請求項７記載のＬＤＰＣデコーダ。
【請求項９】
前記カテゴリ毎の重み付けを前記第１のメモリ出力ではなく、該第１のメモリ入力か若しくはｍｉｎＳｕｍアルゴリズム出力に逆戻る迄の経路に施すことを特徴として構成される請求項８記載のＬＤＰＣデコーダ。
【請求項１０】
前記タナーグラフによって決定される接続情報は、検査マトリクスにおける１の位置をインデックスの形で保存することを特徴として構成される請求項８または請求項９のＬＤＰＣデコーダ。
【請求項１１】
バリアブルノード分のＬＬＲを一時保存する第１のメモリを２面持ち、更に請求項７記載の第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを二面持ち、どちらか一方のメモリを出力として用いている場合は他のメモリを入力として用いて、繰り返し復号における繰り返しサイクル毎に交互に該メモリの入力と出力を入れ替えることを特徴として構成される請求項８記載のＬＤＰＣデコーダ。
【請求項１２】
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスＨの行列操作によって対角要素に１を持つ下三角マトリクスＴを含む上三角零マトリクス
【数１】
0005315693.tif 000137
なる関係を持つマトリクスＡ，Ｂ，Ｔを得る手段１を有し、更に該上三角零マトリクスより
【数２】
0005315693.tif 000138
なるマトリクスＦを得る手段２を有し、該手段１及び２は予め計算されるオフライン処理であって、その結果得られたマトリクスＦの要素１の位置をインデックスの形で蓄積するメモリ１と、情報ビット系列Ｓが格納されているメモリ２と第１の行カウンタを有しており、該第１の行カウンタによってアドレッシングされた前記メモリ１が出力されるインデックスによって更にアドレッシングされる前記メモリ２の出力を排他的論理和することによって第１のパリティ系列ｐ１を得る第１の回路を有しており、該パリティ系列ｐ１と前記オフライン処理で得られたマトリクスＢの積を取り、前記情報ビット系列Ｓと前記オフライン処理で得られたマトリクスＡの積を取って排他的論理和することによって
【数３】
0005315693.tif 000139
なる系列を格納するメモリ３を有し、前記オフライン処理で得られたマトリクスＴの要素１の位置をインデックスの形で蓄積するメモリ４と、第２のパリティ系列ｐ２が格納されるメモリ５と第２の行カウンタを有し、該第２の行カウンタによってアドレッシングされた前記メモリ４が出力されるインデックスによって更に逐次読み出しアドレッシングされる前記メモリ５の出力と、前記第２の行カウンタによってアドレッシングされるメモリ３の出力を排他的論理和をすることによって第２のパリティ系列ｐ２を得て前記第２の行カウンタによって書き込みアドレッシングされる前記メモリ４へ書き込む第２の回路を有しており、前記オフライン処理と第２及び第２の回路によるオンライン処理によって符号化処理を行うことを特徴として構成されるＬＤＰＣエンコーダ。
【請求項１３】
第２のパリティ系列ｐ２が格納される前記メモリ５をマトリクスＴの行重みの数分有したミラーメモリとし、マトリクスＴの要素の１の位置がインデックスとして格納されているメモリ４は単位アドレスに対して行重み分のインデックスを出力するフォーマットであって、これらのインデックスを各ミラーメモリに対して読み出しアドレッシングすることによって行重み分の排他的論理和を一度に行うことを特徴として構成される請求項１２記載のＬＤＰＣエンコーダ。
【請求項１４】
符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの列重みによって複数のカテゴリに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のカテゴリ毎の重み付け値を各カテゴリ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各カテゴリ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各カテゴリ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有することを特徴とするＬＤＰＣデコーダ。
【請求項１５】
チェックノード処理部での前記繰り返し復号における確率伝搬計算は、ｍｉｎＳｕｍアルゴリズムによって行なわれ、各カテゴリに属する検査マトリクスの列重みに合わせて重み付けする値を決定することを特徴とする請求項１４記載のＬＤＰＣデコーダ。
【請求項１６】
前記複数のカテゴリ内にＲＡ構造のカテゴリを有し、該カテゴリの重み付けは他のカテゴリの重み付けより大きくしたことを特徴とする請求項１４または請求項１５記載のＬＤＰＣデコーダ。
【請求項１７】
符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの列重みによって複数のグループに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のグループ毎の重み付け値を各グループ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各グループ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各グループ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有することを特徴とするＬＤＰＣデコーダ。
【請求項１８】
符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のカテゴリに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のカテゴリ毎の重み付け値を各カテゴリ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各カテゴリ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各カテゴリ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有し、
前記第１の変数ノードメモリのメモリバンクの数は各カテゴリに属する、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの重み分布に合わせて変更可能とされ、これにより前記第１の変数ノードメモリへのパラレルアクセスが可能であることを特徴とするＬＤＰＣデコーダ。
【請求項１９】
前記第１の変数ノードメモリへのパラレルアクセスを行うＦＩＦＯ機能を有するキャッシング回路を備えることを特徴とする請求項１８記載のＬＤＰＣデコーダ。
【請求項２０】
チェックノード処理手段は、
第１の最小値検出回路によって第１の最小値を検出する第１の最小値回路と、
前記第１の最小値回路により検出された第１の最小値に対応する入力をマスクして第２の最小値を検出する第２の最小値検出回路と、を有し、
前記第１及び第２の最小値回路はパイプライン構造とされて等価的に１クロックで近似計算を実行することを特徴とする請求項１５記載のＬＤＰＣデコーダ。
【請求項２１】
チェックノード処理手段は、
前記複数のカテゴリに分類された前記第１の変数ノードメモリおよび重み付け処理部へ出力する対数尤度比を一時保存する第１のメモリと、
前記第１の最小値及び第２の最小値と、その入力の２を法とする極性和を保存するチェックノード分の第２のメモリと、
を有し、
前記第１のメモリへの入力が、前記第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することが順次行ない、
各カテゴリ毎に予め決められた重み付けを該第１のメモリ出力に対して行い、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報よって選択される値を差引き、再びｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を行なうことを特徴とする請求項２０記載のＬＤＰＣデコーダ。
【請求項２２】
チェックノード処理手段は、
前記複数のカテゴリに分類された前記第１の変数ノードメモリおよび重み付け処理部へ出力する対数尤度比を一時保存する第１のメモリと、
前記第１の最小値及び第２の最小値と、その入力の２を法とする極性和を保存するチェックノード分の第２のメモリと、
を有し、
前記第１のメモリへの入力が、前記第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することが順次行ない、
各カテゴリ毎に予め決められた重み付けを前記第１のメモリ入力若しくはｍｉｎＳｕｍアルゴリズム出力に逆戻る迄の経路に対して行い、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報よって選択される値を差引き、再びｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を行なうことを特徴とする請求項２０記載のＬＤＰＣデコーダ。
【請求項２３】
前記タナーグラフによって決定される接続情報は、検査マトリクスにおける１の位置をインデックスの形で保存することを特徴として構成される請求項２１または請求項２２記載のＬＤＰＣデコーダ。
【請求項２４】
前記第１の変数ノードメモリと前記第２の変数ノードメモリ、および、前記第１のメモリと第２のメモリは、どちらか一方を出力として用いている場合には他方が入力として用いられ、繰り返し復号における繰り返しサイクル毎に交互に入力と出力が入れ替えられることを特徴とする請求項２１記載のＬＤＰＣデコーダ。
【請求項２５】
予め計算されるオフライン処理によって、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスＨの行列操作により対角要素に１を持つ下三角マトリクスＴを含む上三角零マトリクス
【数４】
0005315693.tif 000140
なる関係を持つマトリクスＡ，Ｂ，Ｔを得る第１の手段と、
前記上三角零マトリクスより、予め計算されるオフライン処理によって
【数５】
0005315693.tif 000141
なるマトリクスＦを得る第２の手段と、を備え、
前記第１の手段および第２の手段により得られたマトリクスＦの第１の要素の位置をインデックスの形で蓄積する第１のメモリと、
情報ビット系列Ｓが格納されている第２のメモリと、
第１の行カウンタと、
前記第１の行カウンタによってアドレッシングされた前記第１のメモリが出力するインデックスによってアドレッシングされた前記第２のメモリの出力の排他的論理和をとることによって第１のパリティ系列ｐ１を得る第１の回路と、
前記第１のパリティ系列ｐ１と前記オフライン処理で得られたマトリクスＢの積を取り、前記情報ビット系列Ｓと前記オフライン処理で得られたマトリクスＡの積を取って排他的論理和をとることによって得られた
【数６】
0005315693.tif 000142
なる系列を格納する第３のメモリと、
前記マトリクスＴの第１の要素の位置をインデックスの形で蓄積する第４のメモリと、
第２のパリティ系列ｐ２が格納される第５のメモリと、
第２の行カウンタと、
前記第２の行カウンタによってアドレッシングされた前記第４のメモリが出力するインデックスによって逐次読み出しがアドレッシングされる前記第５のメモリの出力と、前記第２の行カウンタによってアドレッシングされる前記第３のメモリの出力の排他的論理和をとることによって前記第２のパリティ系列ｐ２を得て前記第２の行カウンタによって書き込みアドレッシングされる前記第５のメモリへ書き込む第２の回路と、を有し、
前記オフライン処理と第１及び第２の回路によるオンライン処理によって符号化処理を行うことを特徴とするＬＤＰＣエンコーダ。
【請求項２６】
第２のパリティ系列ｐ２が格納される前記第５のメモリがマトリクスＴの行重みの数分有したミラーメモリであり、
マトリクスＴの要素の１の位置がインデックスとして格納されている第４のメモリは単位アドレスに対して行重み分のインデックスを出力するフォーマットであって、これらのインデックスを各ミラーメモリに対して読み出しアドレッシングすることによって行重み分の排他的論理和をとることを一度に行うことを特徴とする請求項２５記載のＬＤＰＣエンコーダ。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、誤り訂正符号化方式であるＬＤＰＣ（Low-Density Parity-Check）符号化方式のデコーダ及びエンコーダに関するものである。
【背景技術】
【０００２】
１９６２年にGallagerによりＬＤＰＣ符号化方式が提案されている。ＬＤＰＣ符号とは線形符号でその検査マトリクスの殆どの要素が“０”であるものをいう。古典的な符号理論では検査マトリクスを定めて符号の設計を行っていた。符号化理論の新時代を担うと言われるターボ原理を発端とするＬＤＰＣ符号化方式も同様の定義の仕方が可能である。しかし、本発明ではより本質を捉えたタナーグラフに基づく定義の仕方を用いることにする。【０００３】
タナーグラフとは変数ノードとチェックノードと呼ばれる二種類のノードで符号を表現する二部グラフで、各ノードに接続している枝をエッジといい、各ノードに接続している枝の数をそのノードの次数と呼ぶ。この枝の総数は検査マトリクスの“１”の立っている数であって検査マトリクスの列方向の“１”の数を列重み、行方向の“１”の数を行重みという。ＬＤＰＣ符号化方式でこの検査マトリクスは一意ではない。ＬＤＰＣ符号化方式のデコードはこの検査マトリクスに依存しており、繰返し復号と呼ばれる方法で確率伝搬を計算することによって行われる。【０００４】
近年、再発見されたＬＤＰＣ符号を更にシャノン限界に肉薄するといわれる強力な誤り訂正能力として発展させた方法は、タナーグラフ上の各ノード間の確率伝搬計算において、グラフが持つ符号の局所的な構造に基づいた確率伝搬計算を伝播対象である対数尤度比（ＬＬＲ）に対して行うに当たり、ランダム的に構成される符号と確率的繰り返し復号による方法で或る次数分布を持つＬＤＰＣと同じ符号のアンサンブルに対してＬＬＲの確率密度関数の変化を繰り返し回数毎に計算する手法であるＤＥ（Density Evolutionの略）を用いて次数分布を求めた点であり、非正則ＬＤＰＣ符号に対してこの手法を拡張し優れた次数分布を探索した点である。尚、ノードの次数が等しい正則グラフにより定まる符号を正則ＬＤＰＣ符号と呼び、次数が等しくない場合を非正則ＬＤＰＣと同じ符号と呼ぶ。【０００５】
タナーグラフ上の確率伝播計算はsum-productと呼ばれるメッセージ伝達型アルゴリズムが一般的であるが、これを忠実に実行しようとすると回路規模の増大を引き起こす。そこでMin(Max)Log領域における大胆な近似が行われている。尚、MaxLog領域における近似をＬＤＰＣ符号ではminSumアルゴリズムとも呼ばれている。【０００６】
以上説明した様に、シャノン限界に近い強力な誤り訂正能力を得ようとするにはＤＥに基づく次数分布に従った非正則ＬＤＰＣ符号を用いる必要がある。しかし、ＤＥは元々符号長が事実上無限大の場合についての繰り返し復号特性限界を示すもので、実際には例えば少なくとも１０6〜１０7ビット程度の膨大な符号長を納める為のメモリが必要であり、更に、重み分布も１００〜２００程度の高い最大次数を必要としている。ここで次数が高いということは回路規模がそれだけ大きいことを意味している。【０００７】
近年、移動通信等の通信分野で研究が著しく進められているが、それに伴い誤り訂正符号のエンコーダ及びデコーダの高性能化、高速化、効率化が強く求められている。しかしながら、シャノン限界に近い高性能化が実現出来たとしても移動体にとって現実的でないといった問題があった。【０００８】
これに対して最近、非正則ＬＤＰＣ符号の高重み分布を下げる試みがなされており、その中にノードをカテゴリに分割して低重み分布で発生しやすいエラーフロアに対処する方法が取られている。尚、これらのカテゴリには重み１のノードを持つカテゴリや、変数ノードをパンクチャリングするカテゴリも含まれている。【０００９】
また、sum―productの代わりにMin(Max)Log領域における大胆な近似を実現可能な回路規模のする為に用いられるが、その為に無視できない特性劣化を引き起こすといった問題があった。【００１０】
更に、対向するエンコーダは、その生成マトリクスが喩え低重み分布による疎な検査マトリクスを用いたとしてもそれに反して殆ど確実に疎なマトリクスにならない。疎であるということは低複雑度を意味する。そこで疎な検査マトリクスを活かしつつ符号を生成する算法が「２００１年、２月、アイ・イー・イー・イー・トランザクション・オン・インフォメーション・セオリ、第４７巻、第２号、６３８〜６５６頁(IEEE Transactions on information theory Volume 47,Issue 2,pp.638-656 “Efficient encoding of low-density parity-check codes)」に開示されている。【００１１】
特許文献１（特開２００５−６５２７１号公報）には、ターボ符号化方式における復号で使われるMax-Log-MAP と呼ばれるアルゴリズムが開示されている。LDPC符号化方式はターボ符号化方式と異なる方式であり、その符号化構造が全く異なる。只、繰り返し復号を行うという点で類似する。 【００１２】
繰り返し復号処理でのMaxLog 近似における重み付けであるが、特許文献１ではあたかも二つの重み付け（Ｗｃ、Ｗａ）を行っている如くみえるが、二つの内の一方の重み付け（Ｗｃ）は受信信号における情報系列（Λｃ（ｘｔ、０））に対して行っているだけで繰り返し復号処理の間、この情報系列（Λｃ（ｘｔ、０））は同一の値を取る。即ち、繰り返し復号における確率伝播対象であるLLR とは無関係なものである。そもそも受信信号に対する重み付けは、情報系列やパリティ系列はもとより変復調における信号点マッピングを考慮して決めるべきものであって、繰り返し復号処理における確率伝播対象であるLLR とは別に考えるべきものである。この様に整理すると、この例での確率伝播対象であるLLR は外部対数尤度比（ｅｘｔｒｉｎｘｉｃ ＬＬＲ；以下外部ＬＬＲと略す。） 一つであることが分かる。ターボ符号におけるMax-Log-MAP でこの外部ＬＬＲに対して重み付け処理を行うことは既に公知の事実で、例えば、特許文献２（特許第３２４６４８４号公報）の第一図ではシフト加算によって０．７５倍の重み付けを外部ＬＬＲに対して行い低複雑度で実現してる例が開示されている。 【００１３】
特許文献１の図５には、ハーフイタレーション毎の外部ＬＬＲに対して重み付け処理を行っている例が示されている。 【００１４】
即ち、特許文献１に開示される技術を含めて、基本的にターボ符号化方式の繰り返し復号は外部対数尤度比（ｅｘｔｒｉｎｘｉｃ ＬＬＲ）と呼ばれる一つの確率伝播対象に対して制御されているのである。 【００１５】
また、特許文献３（特開２００４―２６６４６３号公報）にはＬＤＰＣ符号化方式における解析の常套手段である密度発展法（Ｄｅｎｓｉｔｙ Ｅｖｏｌｕｔｉｏｎ）を、またこれも常套手段であるガウス近似法（Ｇａｕｓｓｉｎ Ａｐｐｒｏｘｉｍａｔｉｏｎ；以下ＧＡと略す。）で行い、ラテン方陣を使った生成方法が開示されている。【００１６】
即ち、特許文献３で用いている方法は“Ｓｙｍｍｅｔｒｙ ｃｏｎｄｉｔｉｏｎ“と呼ばれる関係が保存される確率伝播処理で、確率分布に対するトレースを平均値のみで行うことが出来、これで分散も同時にトレースしたことになるといった手法である。
【非特許文献１】２００１年、２月、アイ・イー・イー・イー・トランザクション・オン・インフォメーション・セオリ、第４７巻、第２号、６３８〜６５６頁(IEEE Transactions on information theory Volume 47,Issue2,pp.638-656 “Efficient encoding of low-density parity-check codes)
【特許文献１】特開２００５−６５２７１号公報
【特許文献２】特許第３２４６４８４号公報
【特許文献３】特開２００４―２６６４６３号公報
【発明の開示】
【発明が解決しようとする課題】
【００１７】
シャノン限界に近い強力な誤り訂正能力を得ようとするにはＤＥに基づく次数分布に従った非正則ＬＤＰＣ符号を用いる必要があるが、膨大な符号長を納める為のメモリが必要であり、回路規模が大きくなるという問題点がある。また、シャノン限界に近い高性能化が実現出来たとしても移動体にとって現実的でないといった問題があった。【００１８】
非正則ＬＤＰＣ符号の高重み分布を下げる試みがなされているが無視できない特性劣化を引き起こすといった問題があった。【００１９】
エンコーダには、疎なマトリクスが望まれるが、その生成マトリクスが喩え低重み分布による疎な検査マトリクスを用いたとしてもそれに反して殆ど確実に疎なマトリクスにならない。非特許文献１には疎な検査マトリクスを活かしつつ符号を生成する算法が開示されているものの、プログラムを作成する為の算法の開示されているのみで、高速動作が可能なアーキテクチャに対してはなんら触れられていない。【００２０】
本発明は上述したような従来技術が有する問題点に鑑みてなされたものであって、移動通信等の通信分野で用いられる移動体で実装可能な回路規模で、シャノン限界に近い強力な誤り訂正能力を持つＬＤＰＣ符号化方式を用いたデコーダ及びエンコーダを提供することを目的とするものである。【００２１】
更に、上記を実現するに当たって各ノードをカテゴリ分割した場合で回路規模削減の為に確率伝搬計算をMaxLog近似（minSumアルゴリズムともいう）等の近似計算を用いた場合でも高性能を発揮する方法を提供することを目的とするものである。【００２２】
更に、本発明は、高性能で高速化を実現するＬＤＰＣデコーダのアーキテクチャを提供することを目的とするものである。【００２３】
更に、ＬＤＰＣデコーダと対向するＬＤＰＣエンコーダでも回路規模の削減と高速化を実現する為の構成を提供することを目的とするものである。
【課題を解決するための手段】
【００２４】
本発明のＬＤＰＣデコーダは、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードを複数のカテゴリに分類し、繰り返し復号における確率伝播計算に際し前記カテゴリ毎に予め決定された重み付けを伝播対象である対数尤度比（以下ＬＬＲと略す）に対して行うことを特徴として構成される。
【００２５】
この場合、前記繰り返し復号における確率伝搬計算は、ｍｉｎＳｕｍアルゴリズムであって各カテゴリに属する検査マトリクスの列重みに合わせて重み付けする値を決定することとしてもよい。
【００２６】
また、前記タナーグラフとして、前記複数のカテゴリ内にＲＡ構造のカテゴリを有し、該カテゴリの重み付けは他のカテゴリの重み付けより大きくしてもよい。
【００２７】
本発明の他の形態によるＬＤＰＣデコーダは、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、グラフを構成する各ノードを、その検査マトリクスの列重みによる複数のグループ分けし、繰り返し復号における確率伝播計算に際しては、前記グループ毎に決定された重み付けを伝播対象である対数尤度比（ＬＬＲ）に対して行うことを特徴として構成される。
【００２８】
本発明の他の形態によるＬＤＰＣデコーダは、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクス、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードを複数のカテゴリに分類し、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変えて該対数尤度比へのパラレルアクセスを可能にしたことを特徴とする。
【００２９】
この場合、ＬＤＰＣ符号化方式におけるタナーグラフを用いて、各ノードは複数のカテゴリに分類することが可能であって、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変える構造を有し、前記対数尤度比へのパラレルアクセスを行う際、ＦＩＦＯ機能を有するキャッシング回路を介して行われることとしてもよい。【００３０】
また、前記繰り返し復号における確率伝搬計算をｍｉｎＳｕｍアルゴリズムによって行う際、第１の最小値検出回路によって第１の最小値を検出し、該検出された第１の最小値に対応する入力をマスクして第２の最小値を検出する第２の最小値検出回路を有し、第１及び第２の最小値回路をパイプライン構造によって構成することにより等価的に一クロックで近似計算を実行することとしてもよい。
【００３１】
また、前記繰り返し復号における確率伝搬計算をｍｉｎＳｕｍアルゴリズムによって行う際、変数ノード分のＬＬＲを一時保存する第１のメモリと、請求項７記載の第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを有し、該第１のメモリへの入力は、請求項７記載の第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することによって順次行われ、該第１のメモリは、請求項２記載のカテゴリ分けがなされていて、カテゴリ毎に予め決められた重み付けを該第１のメモリ出力に対して行われ、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報によって選択される値を差引き、再びｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を行なうこととしてもよい。
【００３２】
また、前記カテゴリ毎の重み付けを前記第１のメモリ出力ではなく、該第１のメモリ入力か若しくはｍｉｎＳｕｍアルゴリズム出力に逆戻る迄の経路に施すこととしてもよい。
【００３３】
また、前記タナーグラフによって決定される接続情報は、検査マトリクスにおける１の位置をインデックスの形で保存することとしてもよい。【００３４】
また、バリアブルノード分のＬＬＲを一時保存する第１のメモリを２面持ち、更に第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを二面持ち、どちらか一方のメモリを出力として用いている場合は他のメモリを入力として用いて、繰り返し復号における繰り返しサイクル毎に交互に該メモリの入力と出力を入れ替えることとしてもよい。
【００３５】
本発明のＬＤＰＣエンコーダは、
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスＨの行列操作によって対角要素に１を持つ下三角マトリクスＴを含む上三角零マトリクス
【００３６】
【数１】
0005315693.tif 000002
なる関係を持つマトリクスＡ，Ｂ，Ｔを得る手段１を有し、更に該上三角零マトリクスより【００３７】
【数２】
0005315693.tif 000003
なるマトリクスＦを得る手段２を有し、該手段１及び２は予め計算されるオフライン処理であって、その結果得られたマトリクスＦの要素１の位置をインデックスの形で蓄積するメモリ１と、情報ビット系列Ｓが格納されているメモリ２と第１の行カウンタを有しており、該第１の行カウンタによってアドレッシングされた前記メモリ１が出力されるインデックスによって更にアドレッシングされる前記メモリ２の出力を排他的論理和することによって第１のパリティ系列ｐ１を得る第１の回路を有しており、該パリティ系列ｐ１と前記オフライン処理で得られたマトリクスＢの積を取り、前記情報ビット系列Ｓと前記オフライン処理で得られたマトリクスＡの積を取って排他的論理和することによって【００３８】
【数３】
0005315693.tif 000004
なる系列を格納するメモリ３を有し、前記オフライン処理で得られたマトリクスＴの要素１の位置をインデックスの形で蓄積するメモリ４と、第２のパリティ系列ｐ２が格納されるメモリ５と第２の行カウンタを有し、該第２の行カウンタによってアドレッシングされた前記メモリ４が出力されるインデックスによって更に逐次読み出しアドレッシングされる前記メモリ５の出力と、前記第２の行カウンタによってアドレッシングされるメモリ３の出力を排他的論理和をすることによって第２のパリティ系列ｐ２を得て前記第２の行カウンタによって書き込みアドレッシングされる前記メモリ４へ書き込む第２の回路を有しており、前記オフライン処理と第２及び第２の回路によるオンライン処理によって符号化処理を行うことを特徴として構成される。【００３９】
この場合、第２のパリティ系列ｐ２が格納される前記メモリ５をマトリクスＴの行重みの数分有したミラーメモリとし、マトリクスＴの要素の１の位置がインデックスとして格納されているメモリ４は単位アドレスに対して行重み分のインデックスを出力するフォーマットであって、これらのインデックスを各ミラーメモリに対して読み出しアドレッシングすることによって行重み分の排他的論理和を一度に行うこととしてもよい。【００４０】
本発明の他の形態によるＬＤＰＣデコーダは、符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの列重みによって複数のカテゴリに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のカテゴリ毎の重み付け値を各カテゴリ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各カテゴリ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各カテゴリ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有することを特徴とする。
【００４１】
この場合、チェックノード処理部での前記繰り返し復号における確率伝搬計算は、ｍｉｎＳｕｍアルゴリズムによって行なわれ、各カテゴリに属する検査マトリクスの列重みに合わせて重み付けする値を決定するとしてもよい。
【００４２】
また、前記複数のカテゴリ内にＲＡ構造のカテゴリを有し、該カテゴリの重み付けは他のカテゴリの重み付けより大きくしてもよい。【００４３】
本発明の他の形態によるＬＤＰＣデコーダは、符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの列重みによって複数のグループに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のグループ毎の重み付け値を各グループ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各グループ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各グループ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有することを特徴とする。
【００４４】
本発明の他の形態によるＬＤＰＣデコーダは、符号を変数ノードとチェックノードにより表現するタナーグラフを用いたＬＤＰＣデコーダであって、
複数のカテゴリに分類された伝播対象である対数尤度比を各カテゴリ毎に格納する複数のメモリバンクを備えた第１の変数ノードメモリと、
前記複数のカテゴリ毎の重み付け値を各カテゴリ毎に格納する複数のメモリバンクを備えた第２の変数ノードメモリと、
前記第２の対数ノードメモリに格納される各カテゴリ毎の重み付け値を伝播対象である対数尤度比に応じて決定する重み付け処理部と、
前記第１の変数ノードメモリおよび第２の変数ノードメモリの各カテゴリ毎の格納内容から繰り返し復号における確率伝播計算を行なって伝播対象である対数尤度比として前記前記第１の変数ノードメモリおよび重み付け処理部へ出力するチェックノード処理手段と、
を有し、
前記第１の変数ノードメモリのメモリバンクの数は各カテゴリに属する、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスの重み分布に合わせて変更可能とされ、これにより前記第１の変数ノードメモリへのパラレルアクセスが可能であることを特徴とする。
【００４５】
この場合、前記第１の変数ノードメモリへのパラレルアクセスを行うＦＩＦＯ機能を有するキャッシング回路を備えることとしてもよい。【００４６】
また、チェックノード処理手段は、
第１の最小値検出回路によって第１の最小値を検出する第１の最小値回路と、
前記第１の最小値回路により検出された第１の最小値に対応する入力をマスクして第２の最小値を検出する第２の最小値検出回路と、を有し、
前記第１及び第２の最小値回路はパイプライン構造とされて等価的に１クロックで近似計算を実行するとしてもよい。【００４７】
また、チェックノード処理手段は、
前記複数のカテゴリに分類された前記第１の変数ノードメモリおよび重み付け処理部へ出力する対数尤度比を一時保存する第１のメモリと、
前記第１の最小値及び第２の最小値と、その入力の２を法とする極性和を保存するチェックノード分の第２のメモリと、
を有し、
前記第１のメモリへの入力が、前記第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することが順次行ない、
各カテゴリ毎に予め決められた重み付けを該第１のメモリ出力に対して行い、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報よって選択される値を差引き、再びｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を行なうこととしてもよい。
【００４８】
また、チェックノード処理手段は、
前記複数のカテゴリに分類された前記第１の変数ノードメモリおよび重み付け処理部へ出力する対数尤度比を一時保存する第１のメモリと、
前記第１の最小値及び第２の最小値と、その入力の２を法とする極性和を保存するチェックノード分の第２のメモリと、
を有し、
前記第１のメモリへの入力が、前記第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することが順次行ない、
各カテゴリ毎に予め決められた重み付けを前記第１のメモリ入力若しくはｍｉｎＳｕｍアルゴリズム出力に逆戻る迄の経路に対して行い、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報よって選択される値を差引き、再びｍｉｎＳｕｍアルゴリズムを行う繰り返し復号を行なうこととしてもよい。
【００４９】
この場合、前記タナーグラフによって決定される接続情報は、検査マトリクスにおける１の位置をインデックスの形で保存することとしてもよい。【００５０】
また、前記第１の変数ノードメモリと前記第２の変数ノードメモリ、および、前記第１のメモリと第２のメモリは、どちらか一方を出力として用いている場合には他方が入力として用いられ、繰り返し復号における繰り返しサイクル毎に交互に入力と出力が入れ替えられるとしてもよい。【００５１】
本発明の他の形態によるＬＤＰＣエンコーダは、予め計算されるオフライン処理によって、複数のノードを数個のカテゴリに分類可能な疎な検査マトリクスＨの行列操作により対角要素に１を持つ下三角マトリクスＴを含む上三角零マトリクス
【００５２】
【数４】
0005315693.tif 000005
なる関係を持つマトリクスＡ，Ｂ，Ｔを得る第１の手段と、
前記上三角零マトリクスより、予め計算されるオフライン処理によって【００５３】
【数５】
0005315693.tif 000006
なるマトリクスＦを得る第２の手段と、を備え、
前記第１の手段および第２の手段により得られたマトリクスＦの第１の要素の位置をインデックスの形で蓄積する第１のメモリと、
情報ビット系列Ｓが格納されている第２のメモリと、
第１の行カウンタと、
前記第１の行カウンタによってアドレッシングされた前記第１のメモリが出力するインデックスによってアドレッシングされた前記第２のメモリの出力の排他的論理和をとることによって第１のパリティ系列ｐ１を得る第１の回路と、
前記第１のパリティ系列ｐ１と前記オフライン処理で得られたマトリクスＢの積を取り、前記情報ビット系列Ｓと前記オフライン処理で得られたマトリクスＡの積を取って排他的論理和をとることによって得られた【００５４】
【数６】
0005315693.tif 000007
なる系列を格納する第３のメモリと、
前記マトリクスＴの第１の要素の位置をインデックスの形で蓄積する第４のメモリと、
第２のパリティ系列ｐ２が格納される第５のメモリと、
第２の行カウンタと、
前記第２の行カウンタによってアドレッシングされた前記第４のメモリが出力するインデックスによって逐次読み出しがアドレッシングされる前記第５のメモリの出力と、前記第２の行カウンタによってアドレッシングされる前記第３のメモリの出力の排他的論理和をとることによって前記第２のパリティ系列ｐ２を得て前記第２の行カウンタによって書き込みアドレッシングされる前記第５のメモリへ書き込む第２の回路と、を有し、
前記オフライン処理と第１及び第２の回路によるオンライン処理によって符号化処理を行うことを特徴とする。【００５５】
この場合、第２のパリティ系列ｐ２が格納される前記第５のメモリがマトリクスＴの行重みの数分有したミラーメモリであり、
マトリクスＴの要素の１の位置がインデックスとして格納されている第４のメモリは単位アドレスに対して行重み分のインデックスを出力するフォーマットであって、これらのインデックスを各ミラーメモリに対して読み出しアドレッシングすることによって行重み分の排他的論理和をとることを一度に行うこととしてもよい。【００５６】
本発明のＬＤＰＣデコーダは、タナーグラフにおいて各ノードが複数のカテゴリに分類することが可能であって、繰り返し復号における確率伝播計算に際し前記カテゴリ毎に予め決定された重み付けを伝播対象である対数尤度比（以下ＬＬＲと略す）に対して行うことが出来るので、カテゴリ毎に異なるＬＬＲの確率分布の偏りを補正することが出来、性能を向上させることが出来る。【００５７】
更に本発明のＬＤＰＣデコーダは、前記繰り返し復号における確率伝搬計算がMaxLog近似（或いはminSumアルゴリズムともいう）であって、各カテゴリに属する検査マトリクスの列重みに合わせて重み付けする値を決定することが出来るので、ＬＬＲの確率分布の偏りの原因である列重みの違いに合わせてＬＬＲの偏りを補正することが出来、性能を向上させることが出来る。【００５８】
更に本発明のＬＤＰＣデコーダは、前記タナーグラフにおいて、前記複数のカテゴリ内にＲＡ構造（Repeat Accumulate構造の略でジグザグ構造ともいう）のカテゴリを有しており、該カテゴリの重み付けは他のカテゴリの重み付けより大きくするので、ＲＡ構造を導入したことによる特性向上効果と、ＬＬＲの偏りの大きい他のカテゴリとの差を補正することが出来、更に性能を向上させることが出来る。【００５９】
更に本発明のＬＤＰＣデコーダは、ＬＤＰＣ符号化方式におけるタナーグラフおいて、グラフを構成する各ノードがその検査マトリクスの列重みによる複数のグループ分け可能であって、繰り返し復号における確率伝播計算に際しては、前記グループ毎に決定された重み付けを伝播対象である対数尤度比（ＬＬＲ）に対して行う様にしているのでＬＬＲの偏りをグループ毎に統一することが出来、適切な重み付けによる補正を掛けることが出来、性能を向上させる効果がある。【００６０】
更に本発明のＬＤＰＣデコーダは、ＬＤＰＣ符号化方式におけるタナーグラフおいて、各ノードが複数のカテゴリに分類可能であって、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変えて該対数尤度比へのパラレルアクセスを  可能にしているので、最適なメモリバンクの分割による低複雑度で効率的な高速動作を可能にする効果がある。【００６１】
更に本発明のＬＤＰＣデコーダは、ＬＤＰＣ符号化方式におけるタナーグラフおいて、各ノードが複数のカテゴリに分類可能であって、各カテゴリに属する検査マトリクスの重み分布に合わせて伝播対象である対数尤度比（ＬＬＲ）を格納するメモリバンクの分割数を変える構造を有し、前記対数尤度比へのパラレルアクセスを行う際ＦＩＦＯ機能を有するキャッシング回路を介して行われるので、一時的にアクセスが集中するタイミングが生じても平均化出来、メモリバンクの分割数の増加やオンチップバスの本数を削減させてＬＳＩのチップ面積を削減出来、コスト低減を可能にする効果がある。【００６２】
更に本発明のＬＤＰＣデコーダは繰り返し復号における確率伝搬計算をMaxLog近似（minSumアルゴリズムともいう）によって行う際、第１の最小値検出回路によって第１の最小値を検出し、該検出された第１の最小値に対応する入力をマスクして第２の最小値を検出する第２の最小値検出回路を有し、第１及び第２の最小値回路をパイプライン構造によって構成することにより等価的に一クロックで近似計算を実行することが出来るので高速動作を少ない回路規模で実現出来る効果がある。【００６３】
更に本発明のＬＤＰＣデコーダは繰り返し復号における確率伝搬計算をMaxLog近似（minSumアルゴリズムともいう）によって行う際、変数ノード分のＬＬＲを一時保存する第１のメモリと、特許請求の範囲第七項記載の第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを有し、該第１のメモリへの入力は、第１の最小値及び第２の最小値を元にタナーグラフによって決定される接続に基づいて該第１のメモリの保存値に加算することによって順次行われ、該第１のメモリは、カテゴリ分けがなされていて、カテゴリ毎に予め決められた重み付けを該第１のメモリ出力に対して行われ、その重み付けされたＬＬＲと受信値ＬＬＲとを加算した後、前記第２のメモリ蓄積結果である第１の最小値及び第２の最小値と２を法とする極性和を元にタナーグラフによって決定される接続情報よって選択される値を差し引いた後、再びMaxLog近似（minSumアルゴリズムともいう）を行う繰り返し復号を実現出来るので、少ないメモリ構成並びに近似による回路規模削減効果、並びに高速化、更に適切な重み付け補正によって性能を向上させる効果がある。【００６４】
更に本発明のＬＤＰＣデコーダは、前記カテゴリ毎の重み付けを前記第１のメモリ出力ではなく、該第１のメモリ入力か若しくはMaxLog近似（minSumアルゴリズムともいう）出力に逆戻る迄の経路に対し施すことを考慮してるのでＬＤＰＣデコーダの設計に際し自由度を持たせる効果がある。【００６５】
更に本発明のＬＤＰＣデコーダは、前記タナーグラフによって決定される接続情報は、検査マトリクスにおける１の位置をインデックスの形で保存する形態をとっているので、少ないメモリ容量で接続情報を保持し回路規模を削減する効果がある。【００６６】
更に本発明のＬＤＰＣデコーダは、バリアブルノード分のＬＬＲを一時保存する第１のメモリを２面持ち、更に特許請求の範囲第七項記載の第１の最小値及び第２の最小値とその入力の２を法とする極性和を保存するチェックノード分の第２のメモリを二面持ち、どちらか一方のメモリを出力として用いている場合は他のメモリを入力として用いて、繰り返し復号における繰り返しサイクル毎に交互に該メモリの入力と出力を入れ替える形態をとっているので、効率的なメモリの使用で、スピードを倍増させることが出来る。【００６７】
更に本発明のＬＤＰＣエンコーダは、検査マトリクスＨの行列操作によって対角要素に“１”を持つ  下三角マトリクスＴを含む上三角零マトリクス【００６８】
【数７】
0005315693.tif 000008
なる関係を持つマトリクスＡ，Ｂ，Ｔを得る手段１を有し、更に上三角零マトリクスより【００６９】
【数８】
0005315693.tif 000009
なるマトリクスＦを得る手段２を有しており、該手段１及び２は予め計算されるオフライン処理であって、その結果得られたマトリクスＦの要素１の位置をインデックスの形で蓄積するメモリ１と、情報ビット系列Ｓが格納されているメモリ２と第１の行カウンタを有しており、該第１の行カウンタによってアドレッシングされたメモリ１が出力されるインデックスによって更にアドレッシングされる前記メモリ２の出力を排他的論理和することによって第１のパリティ系列ｐ１を得る第１の回路を有しており、パリティ系列ｐ１と前記オフライン処理で得られたマトリクスＢの積を取り、情報ビット系列Ｓと前記オフライン処理で得られたマトリクスＡの積を取って排他的論理和することによって【００７０】
【数９】
0005315693.tif 000010
なる系列を格納するメモリ３を有しており、前記オフライン処理で得られたマトリクスＴの要素１の位置をインデックスの形で蓄積するメモリ４と、第２のパリティ系列ｐ２が格納されるメモリ５と第２の行カウンタを有し、該第２の行カウンタによってアドレッシングされた前記メモリ４が出力されるインデックスによって更に逐次読み出しアドレッシングされる前記メモリ５の出力と、前記第２の行カウンタによってアドレッシングされるメモリ３の出力を排他的論理和をすることによって第２のパリティ系列ｐ２を得て第２の行カウンタによって書込アドレッシングされるメモリ４へ書き込む第２の回路を有し、オフライン処理と第１及び第２の回路によるオンライン処理によって符号化処理を行う形態をとっているので、疎な検査マトリクスの有効性を保持して得られる効果が有り、少ないメモリ容量と簡単な排他的論理和による少ない回路規模でエンコード処理を実現出来る効果がある。【００７１】
更に本発明のＬＤＰＣエンコーダは、第２のパリティ系列ｐ２が格納される前記メモリ５をマトリクスＴの行重みの数分有したミラーメモリとし、マトリクスＴの要素の１の位置がインデックスとして格納されているメモリ４は、単位アドレスに対して行重み分のインデックスを出力するフォーマットであって、これらのインデックスを各ミラーメモリに対して読出しアドレッシングすることによって行重み分の排他的論理和を一度に行うことが出来るので、エンコード処理を高速に行う効果がある。【００７２】
本発明のＬＤＰＣ符号化方式は、特許文献１に開示されるターボ符号とは全く異なる符号化構造であって、タナーグラフと呼ばれる二部グラフ上の確率伝播を計算することによって繰り返し復号が実行される。この繰り返し復号における確率伝播計算に際しタナーグラフを構成するノードを複数のカテゴリに分類し、分類したカテゴリ毎に独立に予め決められた重み付けを伝搬対象である対数尤度比に対して行っているのが本発明である。これによってエラーフロアの解消のみならず高性能化を実現しているのである。本発明はＭａｘＬｏｇ近似（ｍｉｎＳｕｍアルゴリズム）による非線形処理を解析するものであるからもはや“Ｓｙｍｍｅｔｒｙ ｃｏｎｄｉｔｉｏｎ“の関係が保存されておらず、本発明の手法を用いる必要がある。【００７３】
本発明はＬＤＰＣ符号化方式のエンコーダとデコーダであってその解析法の権利化は行っていない。また本発明の理論的裏付けとなる解析方法も特許文献３とは異なるもので、特許文献３に開示される解析方法では本発明の符号化方式の解析は出来ない。 
【発明の効果】
【００７４】
以上説明した様に、本発明のＬＤＰＣ符号化方式によるエンコーダ及びデコーダは、移動通信等の通信分野でも実現可能な回路規模で高性能化、高速化、効率化を実現出来る手段を提供出来る。【００７５】
その為に、タナーグラフの各ノードを複数のカテゴリに分類して低重み分布による処理規模削減を行って、更に、sum-productの代わりにMin(Max)Log領域における大胆な近似によって回路規模の大幅な削減が有効であるが、その為に引き起こされる性能劣化を生ずることなく高性能化、高速化、効率化出来る手段を提供出来る。【００７６】
更に、本発明により低重み分布の検査マトリクスで高性能化、高速化、及び効率化を備えたデコーダを提供出来るが、エンコーダもまた同低重み分布の検査マトリクスの恩恵を得、高速に動作するアーキテクチャを実現出来る手段を提供出来る。
【図面の簡単な説明】
【００７７】
【図１】本発明のＬＤＰＣ符号化方式によるデコーダの実施形態を示す図である。
【図１Ａ】図１に示したデコーダの具体的な回路構成を示す図である。
【図２】本発明のＬＤＰＣ符号化方式によるカテゴリに分類されたタナーグラフ（ソケットモデル）の一例を示す図である。
【図３】本発明のＬＤＰＣ符号化方式によるカテゴリに分類された検査マトリクスの一例を示す図である。
【図４】本発明のＬＤＰＣ符号化方式によるカテゴリに分類された変数ノード及びチェックノードの重み分布の一例を示す図である。
【図５】本発明のＬＤＰＣ符号化方式によるカテゴリ毎に重み付けした方式の効果を示すモンテカルロシミュレーションによるビット誤り率特性を示す図である。
【図６】従来の単一の重み付け方式を用いたモンテカルロシミュレーションによるビット誤り率特性を示す図である。
【図７】チェックノード処理におけるHyperbolic tangent ruleとそれを簡易化したMin(Max)Log領域で近似した回路を示す図である。
【図８】本発明のＬＤＰＣ符号化方式によるエンコーダアーキテクチャの第１の回路を示す図である。
【図９】本発明のＬＤＰＣ符号化方式によるエンコーダアーキテクチャの第２の回路を示す図である。
【図１０】本発明のＬＤＰＣ符号化方式によるエンコーダアーキテクチャの第２の回路を高速化した回路を示す図である。
【符号の説明】
【００７８】
１０１    変数ノードＬＬＲを格納するメモリ
１０２    変数ノードＬＬＲを格納するメモリ
１０３    重み付け処理部
１０４    減算器
１０５    チェックノード処理部
１０６    チェックノードメモリ
１０７    重み付け処理部
８０１    第１のメモリ
８０２    第２のメモリ
８０３    第１の行カウンタ
８０４    排他的論理和
８０５    遅延素子
８０６    パリティ系列ｐ１用メモリ
９０１    第三のメモリ
９０２    第四のメモリ
９０３    第五のメモリ
９０４    行カウンタ
９０５    排他的論理和
９０６    遅延素子
９０７    セレクタ
１００１    第三のメモリ
１００２    第四のメモリ
１００３    第五のメモリ
１００３−１、２    ミラーメモリ
１００４    第２の行カウンタ
１００５    排他的論理和
【発明を実施するための最良の形態】
【００７９】
次に、本発明の実施形態について式と図面を参照しながら説明する前に、先ず、本発明の裏付けとなる解析をMaxLog近似（minSumアルゴリズムともいう）よって生じる非線形処理を含む密度発展法（Density Evolution；以下ＤＥと略す。）による解析的結果を交えて説明する。【００８０】
先ず、Gaussian Approximation（以下ＧＡと略す）による通常のＤＥと非線形処理を含むＤＥとの違いについて説明する。【００８１】
通常のＧＡではsumproductによる繰り返し復号過程を前提として、伝播対象であるＬＬＲの平均値をトレースすることによって行われる。即ち、列重みｉのシンボルｖｉに対してその平均値ｍｖ、ｉは、【００８２】
【数１０】
0005315693.tif 000011
アンサンブル平均で考えて変数ノードの次数分布を【００８３】
【数１１】
0005315693.tif 000012
とすると以下の関係を得る。【００８４】
【数１２】
0005315693.tif 000013
ここで、以下に説明する分散と平均値の条件【００８５】
【数１３】
0005315693.tif 000014
を用いて、【００８６】
【数１４】
0005315693.tif 000015
【００８７】
【数１５】
0005315693.tif 000016
なるΦ(x)を用いると、【００８８】
【数１６】
0005315693.tif 000017
となる。従って以下の関係を得る。【００８９】
【数１７】
0005315693.tif 000018
又sum-product復号法における”tanh rule”により行重みｊのシンボルｕｊに対してその平均値ｍｕ、ｊは、【００９０】
【数１８】
0005315693.tif 000019
アンサンブル平均で考えてチェックノードの次数分布を【００９１】
【数１９】
0005315693.tif 000020
とすると【００９２】
【数２０】
0005315693.tif 000021
で上記Φ(x)を用いると【００９３】
【数２１】
0005315693.tif 000022
で【００９４】
【数２２】
0005315693.tif 000023
であるから結局、【００９５】
【数２３】
0005315693.tif 000024
更に(5)式の【００９６】
【数２４】
0005315693.tif 000025
を用いると、【００９７】
【数２５】
0005315693.tif 000026
を得る。更に(1)式の【００９８】
【数２６】
0005315693.tif 000027
を用いると、以下の非正則に対する再帰式を得る。【００９９】
【数２７】
0005315693.tif 000028
予め与えられた次数プロファイルの元で再起式である上記（９）式により繰り返し復号過程における平均的な振る舞いをみることが出来る。時間的に無限大へ発展していけばエラーフリーになるし、途中で発展がストップすればエラーフリーを実現することが出来ないということである。その境目を反復閾値（Threshold）と呼びその時の受信値ＬＬＲ平均【０１００】
【数２８】
0005315693.tif 000029
に対応するＥｂ／Ｎ０がエラーフリー実現に必要なレベルとなる。【０１０１】
ここで、上式の発展過程をトレースするパラメータは一変数のみで良い。これは以下の分かり易い例から見て取ることが出来る。今行重ｄｃの場合のHyperbolic Tangent Ruleを考えると、【０１０２】
【数２９】
0005315693.tif 000030
であるから、左辺の確率変数ｕに対する統計的性質（分散σｕ2と平均値ｍｕ）と右辺の確率変数【０１０３】
【数３０】
0005315693.tif 000031
に対する統計的性質（分散σｖ2と平均値ｍｖ）によって期待値を考える必要がある。そこで先ず右辺の分散を考えると、【０１０４】
【数３１】
0005315693.tif 000032
ここで【０１０５】
【数３２】
0005315693.tif 000033
は互いに独立で同じ統計的性質を持つとすると、【０１０６】
【数３３】
0005315693.tif 000034
ここで、【０１０７】
【数３４】
0005315693.tif 000035
両式の差は、【０１０８】
【数３５】
0005315693.tif 000036
上式において固定値は”0”になるかどうかにおいて関係ないので省略し、tanhを指数表現により非積分項を見ると以下の様になる。【０１０９】
【数３６】
0005315693.tif 000037
上式の最後の【０１１０】
【数３７】
0005315693.tif 000038
は積分変数を含ず固定値なので省略して、残った非積分関数を【０１１１】
【数３８】
0005315693.tif 000039
とおいて、【０１１２】
【数３９】
0005315693.tif 000040
この関数の対象関数ｆ（−ｘ）は【０１１３】
【数４０】
0005315693.tif 000041
となって非積分関数【０１１４】
【数４１】
0005315693.tif 000042
は奇関数であることが分かる。従って【０１１５】
【数４２】
0005315693.tif 000043
となって、任意の【０１１６】
【数４３】
0005315693.tif 000044
なるＧＡにおいて【０１１７】
【数４４】
0005315693.tif 000045
従って（１０）式の分散の第１項は、【０１１８】
【数４５】
0005315693.tif 000046
従って（１０）式の分散は、【０１１９】
【数４６】
0005315693.tif 000047
次に左辺の確率変数ｕに対する統計的性質（分散σｕ2と平均値ｍｕ）で左辺の分散を考えると、【０１２０】
【数４７】
0005315693.tif 000048
結局左辺右辺の関係は【０１２１】
【数４８】
0005315693.tif 000049
より【０１２２】
【数４９】
0005315693.tif 000050
であるから【０１２３】
【数５０】
0005315693.tif 000051
となりうる両辺の統計的性質（分散σｕ2と平均値ｍｕ）と（分散σｖ2と平均値ｍｖ）によって平衡状態が保たれるようになる。即ち、この条件が成り立つ統計的性質（分散σｕ2と平均値ｍｕ）を持つｕが出力である。【０１２４】
一方、平均値の方は、上記の結果と矛盾無く状態が保存されているかどうかを見ると、【０１２５】
【数５１】
0005315693.tif 000052
より右辺は【０１２６】
【数５２】
0005315693.tif 000053
、左辺は当然【０１２７】
【数５３】
0005315693.tif 000054
従って平均値の観点からは、【０１２８】
【数５４】
0005315693.tif 000055
となりうる両辺の統計的性質（分散σu2と平均値ｍu）と（分散σv2と平均値ｍv）によって平衡状態が保たれるようになる。即ち、この条件が成り立つ統計的性質（分散σu2と平均値ｍu）を持つｕが出力である。【０１２９】
（２１）式と（２２）式の関係を見ると、例えば（２２）式の関係が成り立つ条件を使って（２１）式の左辺を計算すると、【０１３０】
【数５５】
0005315693.tif 000056
となって（２１）式と（２２）式の関係、即ち、平均値と分散の関係が矛盾無く成り立っていることが分かる。即ちHyperbolic Tangent Ruleにおける平均値とその分散のトレースは、平均値のみのトレースでも分散も同時にトレースしたことになるので、一変数のみ観測するばよい。【０１３１】
この関係は互いに独立な確率変数として扱っているので、Φ（＊）によって異なる統計的環境に対する確率変数に対しても成り立つ。従って、以下に示すカテゴリに分類したタナーグラフについてもそのまま使えることになる。以下カテゴリに分類したタナーグラフにおけるＧＡについて記す。【０１３２】
上述した従来の非正則ＬＤＰＣのＧＡではアンサンブル平均した形で全てのＬＬＲを単一の平均値で扱っていた。カテゴリに分類したタナーグラフでは、カテゴリ毎にアンサンブル平均しているので、その分詳細で正確な過程を評価することが出来る。即ち、変数ノードからチェックノードへ、且つ、チェックノードから変数ノードへのメッセージをカテゴリ毎に別けて考えている点である。今カテゴリの数をｎe個とし、カテゴリｉの或一つの枝が出る方向として接続されているチェックノード（変数ノード）に対し、カテゴリｊ（≠ｉ）の枝がdj本、カテゴリｉの枝がdi-1本入る方向として接続されているものとする。この状態でのＧＡを考える。【０１３３】
SumProductによる各更新過程の平均値を追い掛ける訳であるが、カテゴリ別に分けて考える為、【０１３４】
【数５６】
0005315693.tif 000057
毎にそれぞれまとめた次数の【０１３５】
【数５７】
0005315693.tif 000058
のベクトル表現を用いる。即ち任意の次数dでカテゴリｉの内列重diのメッセージV(i)dに対する平均値【０１３６】
【数５８】
0005315693.tif 000059
は、【０１３７】
【数５９】
0005315693.tif 000060
ここで、カテゴリｉの枝の内で任意に選んだ次数【０１３８】
【数６０】
0005315693.tif 000061
のノードに接続している枝の割合を表記するのに当たって以下の関係を用いる。【０１３９】
【数６１】
0005315693.tif 000062
カテゴリｉの枝の総数は【０１４０】
【数６２】
0005315693.tif 000063
であるから結局任意に選んだ次数【０１４１】
【数６３】
0005315693.tif 000064
のノードに接続している枝の割合は【０１４２】
【数６４】
0005315693.tif 000065
となる。【０１４３】
そこでカテゴリｉ内のアンサンブル平均で考えて以下の関係を得る。【０１４４】
【数６５】
0005315693.tif 000066
ここで、Φ(x)を用いると、【０１４５】
【数６６】
0005315693.tif 000067
従って以下の関係を得る。【０１４６】
【数６７】
0005315693.tif 000068
同様にカテゴリｊ（≠ｉ）の枝がdj本、カテゴリｉの枝がdi-1本入る方向として接続されているものとして、カテゴリ別に分けて考える為【０１４７】
【数６８】
0005315693.tif 000069
毎にそれぞれまとめた次数【０１４８】
【数６９】
0005315693.tif 000070
のベクトル表現を用いる。任意の次数dでカテゴリｉの内列重diのＬＬＲＵ(i)dに対する平均値【０１４９】
【数７０】
0005315693.tif 000071
は、sumProductにおける“tanh rule“を用いて、【０１５０】
【数７１】
0005315693.tif 000072
ここで、カテゴリｉの枝の内で任意に選んだ次数【０１５１】
【数７２】
0005315693.tif 000073
のノードに接続している枝の割合を表記するに当たって以下の関係を用いる。【０１５２】
【数７３】
0005315693.tif 000074
カテゴリｉの枝の総数は【０１５３】
【数７４】
0005315693.tif 000075
であるから結局任意に選んだ次数【０１５４】
【数７５】
0005315693.tif 000076
のノードに接続している枝の割合は【０１５５】
【数７６】
0005315693.tif 000077
となる。【０１５６】
そこでカテゴリｉ内のアンサンブル平均で考えて以下の関係を得る。【０１５７】
【数７７】
0005315693.tif 000078
Φ(x)を用いると【０１５８】
【数７８】
0005315693.tif 000079
で上式より、【０１５９】
【数７９】
0005315693.tif 000080
であるから結局、【０１６０】
【数８０】
0005315693.tif 000081
更に、上述の【０１６１】
【数８１】
0005315693.tif 000082
はｊに対しても同様の考えが成り立つから、【０１６２】
【数８２】
0005315693.tif 000083
を得る。更に上述の、【０１６３】
【数８３】
0005315693.tif 000084
を用いると、カテゴリに分類したタナーグラフにおけるＧＡの下記再帰式を得る。【０１６４】
【数８４】
0005315693.tif 000085
予め与えられた次数プロファイル【０１６５】
【数８５】
0005315693.tif 000086
の元で再帰式（３２）により繰り返し復号過程における平均的な振る舞いをみることが出来る。平均値ｍが繰り返しと共に無限大へ発展していけばエラーフリーで、途中で発展がストップすればエラーフリーを実現出来ない。その境目を反復閾値（Threshold）と呼び、その時の通信路ＬＬＲ平均ｍ（ｉ）u0 ｉ=１〜neに対応するＥb／Ｎ0がエラーフリー実現に必要なレベルとなる。また上式において、【０１６６】
【数８６】
0005315693.tif 000087
である。【０１６７】
以上はsumProductによるHyperbolic Tangent Ruleを用いた場合で、（２１）式と（２２）式の関係、即ち、平均値と分散の関係が繰り返し復号過程でも矛盾無く成り立っている場合である。即ちHyperbolic Tangent Ruleにおける平均値とその分散のトレースは、平均値のみのトレースでも分散も同時にトレースしたことになるので、一変数のみ観測すればよかった場合である。【０１６８】
しかし、MaxLog近似（或いはminSumアルゴリズムともいう）によって生じた非線形処理を含むＧＡの場合、もはや（２１）式、（２２）式の関係が成り立たなくなって、平均値のみのトレースで分散も同時にトレースしたことになるメリットを得ることが出来なくなってくる。【０１６９】
そこで、平均値と分散の両方を繰り返し復号過程でトレースし、そのＳＮＲが十分に大きくなるかどうかで判断する。途中でＳＮＲの増大がストップすれば性能が悪い。その境目の通信路ＬＬＲ平均ｍ（ｉ）u0 ｉ=１〜neに対応するＥb／Ｎ0をもって必要なレベルを判断する。【０１７０】
その為に、MaxLog近似（或いはminSumアルゴリズムともいう）における確率分布を求める必要がある。以下行重み４の場合を例に取ってその確率分布について記す。【０１７１】
行重みが４であるから、ｄｃ−１＝３で３変数の確率分布を求めることになる。【０１７２】
今、行方向の演算を考え、各ノードにおける対数尤度比をＬＬＲと表記する。従ってＬＬＲは推定対象であるノードの個数を除くdc-1個の独立な確率変数によって決定され、その確率変数をベクトルで【０１７３】
【数８７】
0005315693.tif 000088
と表記し、それぞれの確率密度関数を平均値ｍj、分散σ2jとして【０１７４】
【数８８】
0005315693.tif 000089
の様に表す。更に確率関数を以下の様に定義する。【０１７５】
【数８９】
0005315693.tif 000090
に対して【０１７６】
【数９０】
0005315693.tif 000091
、即ち、【０１７７】
【数９１】
0005315693.tif 000092
と【０１７８】
【数９２】
0005315693.tif 000093
はx以上の大きさを持つ確率変数【０１７９】
【数９３】
0005315693.tif 000094
の正の場合と負の場合の確率を表している。
ＬＬＲの確率密度分布(pdf)であるＱL(x)を求める為にＬＬＲの累積確率分布(cdf)を計算する。【０１８０】
【数９４】
0005315693.tif 000095
に対して、【０１８１】
【数９５】
0005315693.tif 000096
即ち、全ての【０１８２】
【数９６】
0005315693.tif 000097
が【０１８３】
【数９７】
0005315693.tif 000098
以上ならば【０１８４】
【数９８】
0005315693.tif 000099
も【０１８５】
【数９９】
0005315693.tif 000100
以上となる。従って【０１８６】
【数１００】
0005315693.tif 000101
で近似されるところの負の領域（odd number of negative value in Z）で最小の【０１８７】
【数１０１】
0005315693.tif 000102
でも【０１８８】
【数１０２】
0005315693.tif 000103
となるから、【０１８９】
【数１０３】
0005315693.tif 000104
となり、【０１９０】
【数１０４】
0005315693.tif 000105
で領域化される事象は全て【０１９１】
【数１０５】
0005315693.tif 000106
に含まれることになる。逆に全ての【０１９２】
【数１０６】
0005315693.tif 000107
が【０１９３】
【数１０７】
0005315693.tif 000108
以上でなければ【０１９４】
【数１０８】
0005315693.tif 000109
以下の事象が必ず存在するので【０１９５】
【数１０９】
0005315693.tif 000110
に含まれない。従って行重みが４で３変数の累積分布ＦL（ｌ）は、【０１９６】
【数１１０】
0005315693.tif 000111
従って、求めようとしているＬの確率密度分布ＱL(ｌ)は、上記(３６)式のＬの累積確率分布(cdf)をｌで微分することによって得られ、【０１９７】
【数１１１】
0005315693.tif 000112
となる。ｌ＞０の場合も同じ結果になるのでここでは省略する。
（３７）式よりMaxLog近似（或いはminSumアルゴリズムともいう）の平均値は、【０１９８】
【数１１２】
0005315693.tif 000113
によって得ることが出来る。また、分散は、【０１９９】
【数１１３】
0005315693.tif 000114
によって得ることが出来る。
これを（３２）式に当てはめるとMaxLog近似（或いはminSumアルゴリズムともいう）によって生じた非線形処理を含むカテゴリに分類したタナーグラフにおけるＧＡとなる。そのＧＡによって最適な重み付けを検索した結果を以下の例で示す。
【実施例】
【０２００】
多変数多項式；【０２０１】
【数１１４】
0005315693.tif 000115
実施したソケットモデルを図２に、検査マトリクスを図３に、また対応表を図４に示す。【０２０２】
この例はMulti-Typeと呼ばれるもので、Type毎にカテゴリ分けしている。上記（４０）式の多項式や図２〜図４のソケットモデルなどから行重みが４の単一行重みであることが分かる。この例を上記MaxLog近似（或いはminSumアルゴリズムともいう）によって生じた非線形処理を含むカテゴリに分類したタナーグラフにおけるＧＡによって最適な重み付けを探索する。重み付けに相当する箇所をブロック図で示すと図１の様になる。即ち異なるカテゴリ毎に独立に重み付けがなされる様に構成されている。同図上でに相当する箇所の重み付けで最高性能を発揮する値を下記表の左に記入すると以下の様になる。【０２０３】
【表１】
0005315693.tif 000116
【０２０４】
この結果が示す様に、ＲＡ構造を持つ列重み２の箇所の重み付けが０．９８で一番高く、他は０．５８〜０．６２程度となっている。これはＲＡ構造を持つカテゴリのノードは他の高い列重みからの信頼度の高いＬＬＲを得るのに対して逆にＲＡ構造以外のカテゴリのノードはＲＡ構造からの低い列重みからの信頼度の低いＬＬＲを得る為、ＲＡ構造のカテゴリは高い重み付けで、他のカテゴリは低い重み付けになったものと思われる。【０２０５】
尚、カテゴリ分けのないタナーグラフでMaxLog近似（或いはminSumアルゴリズムともいう）を用いたとき重み付けによって補正を掛けることが知られているが、これは全てのノードに対して単一の重み付けを行っているものである。或いは列重みではなく行重みに注目して重み付けを行っている。これに対して本発明は列重みに注目して重み付けを行っている点に注意が必要である。【０２０６】
例えば、行重みに注目して重み付けを行ったとすると、上記の例では全ての行重みが４で重み付けの値は同じということになってしまう。それにも関わらず、重み付けをカテゴリ毎に変えることによって特性向上が示される点が従来と大きく異なる点で、これは上記のカテゴリ分けされた状態での非線形処理を含むＤＥを試みた本発明で始めて明らかになった点であり、本発明はこの解析結果に基づいて行われたものである。【０２０７】
以上の結果を基に実際のMaxLog近似を使ったＬＤＰＣデコーダでモンテカルロシミュレーションを行った結果を図５に示す。同図において左のラインがsum-productを用いた特性で右のラインがMaxLog近似（或いはminSumアルゴリズムともいう）を用いた特性である。この条件で用いた重み付けは以下の様になる。【０２０８】
【表２】
0005315693.tif 000117
【０２０９】
最終的なモンテカルロシミュレーションにおいても、上記結果が示す様にＲＡ構造を持つ列重み２の箇所の重み付けが０．９９９９で一番高く、他は０．５８〜０．６９といった値になった。若干の最適化対象の動作点の違いで値が若干ずれているものの傾向としては同じものであることが分かる。【０２１０】
一方、従来の全てのノードに対して単一の重み付けを行う方法で他は全く同じ内容で重み付け係数の最適化を行いモンテカルロシミュレーションを行った結果を図６に示す。この時用いた重み付け係数を追記した表を以下に示す。【０２１１】
【表３】
0005315693.tif 000118
【０２１２】
図６の特性を見て分かるようにMaxLog近似（或いはminSumアルゴリズムともいう）を用いた右側のラインでは単一の重み付け係数だけではエラーフロアが生じてしまい用いることが出来ない状態となる。【０２１３】
以上が本発明の裏付けとなる解析結果であり、カテゴリに分類したタナーグラフによるMaxLog近似（或いはminSumアルゴリズムともいう）を用いたデコーダにカテゴリ毎の重み付けが有効であることを示すものである。【０２１４】
以下、図１を参照しながら本発明の実施例を説明する。図１は本発明のカテゴリに分類したタナーグラフによるMaxLog近似（或いはminSumアルゴリズムともいう）を用い、カテゴリ毎の重み付けを施すデコーダの構成を示すブロック図、図１Ａはその具体的な回路構成を示す図である。【０２１５】
図１に示すデコーダは、変数ノードメモリ１０１および１０２より構成されるメモリ１００、重み付け処理部１０３，１０７、減算器１０４、チェックノード処理部１０５およびチェックノードメモリ１０６から構成されている。【０２１６】
変数ノードを格納する変数ノードメモリ１０１と１０２はそれぞれ出力と入力とに切り替えられて使用されるもので、タナーグラフにおけるカテゴリ分割に従い、メモリバンク（不図示）によってこれらの内部は分割されている。また、受信値ＬＬＲを格納するエリアが設けられており、変数ノードの出力を受け持つ出力部は変数ノードを出力する際に受信値ＬＬＲを加算して出力する。【０２１７】
以下の説明では、変数ノードメモリ１０１と１０２のそれぞれが、現在、出力と入力に使用されているとして説明する。【０２１８】
上記の様にして出力された変数ノードＬＬＲは、MaxLog近似（或いはminSumともいう）の為の第１の最小値と第２の最小値と２を法とする極性和と最小値の位置を納めたチェックノードメモリ１０６から生成された値、即ち、同じ行内における変数ノードＬＬＲ【０２１９】
【数１１５】
0005315693.tif 000119
に対して【０２２０】
【数１１６】
0005315693.tif 000120
なる選択と極性付けを行ってカテゴリに対応する重み付けが重み付け処理部１０３によりなされているが、重み付け処理部１０３と同じ重み付け値を出力する重み付け処理部１０７の出力値を減算器１０４で差し引いた後にチェックノード処理部１０５に出力される。【０２２１】
チェックノード処理部１０５では、MaxLog近似（或いはminSumともいう）の為の第１の最小値と第２の最小値と２を法とする極性和と最小値の位置の検出を行う。【０２２２】
チェックノード処理部１０５の具体的な回路構成を図７に示す。図７（a）に示すように、Min(Max)Log領域における近似アルゴリズムでHyperbolic tangent ruleを実現している。ここで、チェックノード処理におけるメッセージ更新規範を、Hyperbolic tangent ruleと呼んでおり、図７（ｂ）に示す様に並列構成でパイプライン化しているので、平均的に見て１クロックで動作を完了する。回路動作はtree構成で最小値検出(min)を行い、その最小値をマスクして第２の最小値検出(Sub-min)を行っている。２ｓｔｅｐ動作であるが、パイプライン化しているので等価的に１クロックで全ての処理が完結する。尚、煩雑になるので図ではパイプライン用のF/Fを省略している。【０２２３】
図１に戻って、このチェックノード処理をチェックノード処理部１０５で行った後、得られた値（min、Sub-min、２を法とする極性和であるsign、そして最小値の位置を示すPosition）をチェックノードメモリ１０６に格納する。【０２２４】
チェックノードメモリ１０６はメモリ１００と同様に入力または出力として用いられる２つのメモリ部を備えるものであり、チェックノード処理部１０５の処理により得られた値を入力のメモリ部に格納する。また、同時に、それらを用いて選択と極性付けで得られた（４１）式におけるｕの値であるＬＬＲを変数ノードメモリ１０２へ格納する。その際、重み付け処理部１０３で予めカテゴリ毎に決められた重み付けを行ってから１０２へ格納する。【０２２５】
尚、このブロック図では格納する際に重み付け処理を行っているが、出力である変数ノードメモリ１０１で受信値ＬＬＲを加算する前に重み付け処理を行ってもよいし、チェックノード処理部１０５で出力する際に重み付け処理を行っても良い。【０２２６】
次のサイクルでは、こんどは変数ノードメモリ１０２が出力で変数ノードメモリ１０１が入力となるべく構成が入れ替わる。煩雑になるので図では省略しているが重み付け処理部１０３も入力である変数ノードメモリ１０１に対して行われる様になる。また、二部構成のチェックノードメモリ１０６も入力と出力が入れ替わり、予め決められた繰り返し回数になるまで繰り返しサイクル毎に交互にメモリの入力と出力を入れ替える処理が行われる。【０２２７】
これらのメモリのアクセスはカテゴリ毎に分割されたメモリバンク内で更にカテゴリ内の重み分布に応じてメモリバンクによる分割がなされており、パラレルで処理がすすむ様になっている。また、各カテゴリ内の重み分布の関係で一時的にパラレルアクセスが集中するタイミングが生じた場合を考慮してＦIＦＯ機能を有するキャッシング回路を介してメモリアクセスを行う様になっているので、平均化の効果でメモリバンクの分割数の増加やオンチップバスの本数の削減を行っている。【０２２８】
また、図中特に記載されていないが、ターナーグラフによって決定される接続情報は検査マトリクスの１の位置をインデックスの形で保存しているメモリが有り、少ないメモリ容量でＬＬＲの接続制御を行っている。【０２２９】
更に、図２，３，４を見て分かるように、この例ではカテゴリと列重みの関係がほぼ対応する様になっている。特に列重みに拘らずカテゴリ化で自由に重み付けを決めることも出来るが、この例の様に列重みによるグループ化をカテゴリに含ませることも可能である。【０２３０】
以上図１を参照しながらデコーダのアーキテクチャについて説明した。次に本発明によるエンコーダについて説明する。【０２３１】
低次数プロファイルによって決定される検査マトリクスＨは疎な行列となるから復号の為の処理量が少なく低複雑化に適している。しかし疎な検査マトリクスＨに対応した生成マトリクスＧはほとんど確実に疎な行列でなくなるので、この為符号化処理が復号処理に対して無視出来ないということになる。しかし、この疎な検査マトリクスを活かしつつ符号を生成する算法が知られている。そこで、高速化可能で処理規模の小さいアーキテクチャについて図を参照しながら説明する。【０２３２】
本発明の符号化処理は、予め計算（Pre-calculation）を行うオフライン処理（Offline process）とハードウェアによるオンライン処理（Online process）によって構成されている。予め行うオフライン処理では検査マトリクスの疎な性質を保ったままで行列変換を行う。またハードウェアによるオンライン処理では検査マトリクスの疎な性質を保ったまま作られた四つのマトリクスＡ，Ｂ，Ｔ及びＦを元に高速に符号化処理を実行する。【０２３３】
（１）  Pre-calculation (Offline process)
検査マトリクスの行入れ替えおよび列入れ替えによって以下の上三角零行列Ｈを得る。【０２３４】
【数１１７】
0005315693.tif 000121
ここで、Ｔは対角要素に”1”を持つ下三角行列で左から【０２３５】
【数１１８】
0005315693.tif 000122
を掛けると、以下の行列を得る。【０２３６】
【数１１９】
0005315693.tif 000123
ここでエンコーダ出力である符号語をベクトル表現で以下の様に表記する。【０２３７】
【数１２０】
0005315693.tif 000124
同ベクトル内ベクトルでsは情報ビット系列を表し、p1,p2はそれぞれパリティビット系列を表す。
符号語ベクトルＸと検査マトリクスＨとの間には【０２３８】
【数１２１】
0005315693.tif 000125
なる関係があるから、【０２３９】
【数１２２】
0005315693.tif 000126
これより以下の関係を得る。【０２４０】
【数１２３】
0005315693.tif 000127
（２）  Hardware Encoding (Online process)
上式を元に与えられた情報ビット系列sからエンコーダ出力の一部であるパリティビット系列p1を高速に生成する。【０２４１】
i. s → p1 ：  上式における第２の関係より、【０２４２】
【数１２４】
0005315693.tif 000128
上式における演算は全てＧＦ（２）上で行われ、ベクトルp1の大きさは”gap“と呼ばれる部分で非常に小さい。従って図８の様な簡単な回路で実現出来る。同図において、第１のメモリ８０１はオフライン処理で得られるマトリクスＦの要素１の位置をインデックスとして蓄積しており、第１の行カウンタ８０３によってアドレッシングされこの第１のメモリ８０１が出力するインデックスによって更にアドレッシングされる第２のメモリ８０２には情報ビット系列Ｓが格納されている。従って、マトリクスＦの要素である１のインデックスによって出力された情報ビットＳを排他的論理和回路８０４と遅延素子８０５によって２を法とする積算することになるので出力先のパリティ系列ｐ１を蓄積するメモリ８０６には上記（４７）式の【０２４３】
【数１２５】
0005315693.tif 000129
が格納されることになる。
ii. s, p1 → p 2 ：上記（４６）式における第１の関係より、【０２４４】
【数１２６】
0005315693.tif 000130
ここで、マトリクスＴは以下の様な対角要素に”1”を持つ下三角マトリクスである。
従って、【０２４５】
【数１２７】
0005315693.tif 000131
これより以下の関係を得る。【０２４６】
【数１２８】
0005315693.tif 000132
上式における演算は全てＧＦ（２）上で行われ、マトリクスTは下三角行列で疎な行列でもある。また、AもBも疎な行列であるから、図９の様な簡単な回路で実現出来る。【０２４７】
同図において、第３のメモリ９０１には（４７）式によるオンライン処理で得られたパリティ系列ｐ１と上述のオフライン処理で得られたマトリクスＢの積と前記情報ビット系列Ｓとオフライン処理で得られたマトリクスＡの積の和である【０２４８】
【数１２９】
0005315693.tif 000133
が格納されていて、第４のメモリ９０２にはオフライン処理で得られたマトリクスＴの要素１の位置をインデックスとして蓄積している。【０２４９】
第５のメモリ９０３は第２のパリティ系列ｐ２を格納し、第２の行カウンタ９０４によってアドレッシングされた第４のメモリ９０２が出力するインデックスを読み出しアドレスとするメモリであって、第５のメモリ９０３の出力と【０２５０】
【数１３０】
0005315693.tif 000134
が格納されている第３のメモリ９０１の出力が行の初回のみ排他的論理和を取る様にセレクタ９０７が第２の行カウンタ９０４によって制御され、その後は第２のパリティ系列ｐ２の方にセレクタ９０７が切り替わることによって、排他的論理和回路９０５と遅延素子９０６によって（５０）式の演算が実行される。尚、【０２５１】
【数１３１】
0005315693.tif 000135
のハードウェアでの演算は通常の設計事項であるのでここでは説明を省略する。【０２５２】
以上のオフライン処理と図８と図９に示されるハードウェアによるオンライン処理によって本発明のエンコーダが構成される。【０２５３】
図１０はエンコード処理の負荷の殆どを担う図９の回路を高速化したもので、図９に示したものと同様に、第２の行カウンタ１００４によってアドレッシングされたメモリ１００２のマトリクスＴの要素の１の位置をインデックスとして動作している。
7  図１０において、図９に示した構成と異なる点はこのインデックスが行重み分有る点で、同一の行内にある全ての１の位置に対するインデックスをパラレルに第２のパリティ系列ｐ２が格納されるメモリ１００３にアドレッシングしている点である。その為、第２のパリティ系列ｐ２が格納されるメモリとしてミラーメモリ１００３−１，２を付加して【０２５４】
【数１３２】
0005315693.tif 000136
が格納されている第３のメモリ１００１の出力と共に排他的論理和回路１００５によって一度期に（５０）式の演算を行い、その結果をミラーメモリ１００３−１，２を含む第２のパリティ系列ｐ２が格納されるメモリ１００３に格納して高速動作を実現したものである。
【図１】
0005315693.tif 000143
【図１Ａ】
0005315693.tif 000144
【図２】
0005315693.tif 000145
【図３】
0005315693.tif 000146
【図４】
0005315693.tif 000147
【図５】
0005315693.tif 000148
【図６】
0005315693.tif 000149
【図７】
0005315693.tif 000150
【図８】
0005315693.tif 000151
【図９】
0005315693.tif 000152
【図１０】
0005315693.tif 000153