(57)【要約】【課題】低密度パリティ検査符号の復号に要する演算量を低減することにより高い復号スループットを得る。【解決手段】本発明の一態様としての復号装置は、検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、検査行列の行毎に、行処理演算を行うことにより行処理演算データを計算する行処理演算手段と、検査行列の行毎に、前記行により規定されるパリティ検査式の成立に対する信頼性の程度を表す信頼度係数を計算する信頼度係数計算手段と、検査行列の列毎に、列処理演算を行うことにより列処理演算データを計算する列処理演算手段と、前記行処理演算手段の処理と前記信頼度係数計算手段の処理と前記列処理演算手段の処理とを１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記行処理演算手段の処理と前記信頼度係数計算手段の処理を省略する繰り返し制御手段と、を備える。【選択図】図１
2009100222.tif 000002
【特許請求の範囲】
【請求項１】
検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、
受信語データを受信する受信手段と、
前記受信手段により受信された受信語データを、初期化された列処理演算データとして行番号および列番号ごとに記憶する列処理演算データ記憶手段と、
行処理演算データの書き込み要求を受けて前記行処理演算データを行番号および列番号ごとに記憶する行処理演算データ記憶手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する行処理演算データを計算し、計算された行処理演算データの前記書き込み要求を前記行処理演算記憶手段に行う、行処理演算手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、前記行により規定されるパリティ検査式の成立に対する信頼性の程度を表す信頼度係数を計算する信頼度係数計算手段と、
前記検査行列の列毎に、「１」の要素に対して前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する前記列処理演算データを計算し、計算された列処理演算データを行番号および列番号ごとに前記列処理演算データ記憶手段に書き込む列処理演算手段と、
前記行処理演算手段の処理と前記信頼度係数計算手段の処理と前記列処理演算手段の処理とを１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記行処理演算手段の処理と前記信頼度係数計算手段の処理を省略する繰り返し制御手段と、
を備えた、低密度パリティ検査符号の復号装置。
【請求項２】
前記セットを１回以上繰り返したとき、前記検査行列の「１」の要素に対して、前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、読み出した前記行処理演算データに基づき前記受信語データを補正して補正受信語データを生成するデータ生成手段と、
前記補正受信語データを硬判定することにより硬判定データを取得する硬判定手段と、
前記検査行列に基づき前記硬判定データをパリティ検査し、前記パリティ検査の結果が真であるときは、前記硬判定データを復号語データとして出力するパリティ検査手段と、を備え、
前記繰り返し制御手段は、前記パリティ検査の結果が偽であるときは、前記セットの繰り返し実行を引き続き行う、
ことを特徴とする請求項１に記載の復号装置。
【請求項３】
前記検査行列における全ての行に対して前記信頼度係数が前記閾値を満たしたとき、または前記セットを所定回数繰り返し実行したとき、前記繰り返し制御手段による繰り返し実行を終了させる終了手段と、
前記検査行列の「１」の要素に対して、前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、読み出した前記行処理演算データに基づき前記受信語データを補正して補正受信語データを生成するデータ生成手段と、
前記補正受信語データを硬判定することにより硬判定データを取得する硬判定手段と、
前記硬判定データを復号語データとして出力する出力手段と、
をさらに備えた請求項１に記載の復号装置。
【請求項４】
前記検査行列の行毎に、第１の値または第２の値を示すフラグを記憶するフラグ記憶手段と、
前記行毎の前記フラグを前記第２の値に初期化するフラグ初期化手段と、をさらに備え、
前記信頼度係数計算手段は、前記行毎の前記信頼度係数が前記閾値を満たしたときは、前記行毎の前記フラグを第１の値に変更し、
前記繰り返し制御手段は、前記行毎に前記フラグ記憶手段を参照することにより前記行毎の前記信頼度係数が前記閾値を満たすかどうかを判断する、
ことを特徴とする請求項１ないし３のいずれか一項に記載の復号装置。
【請求項５】
検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、
受信語データを受信する受信手段と、
前記受信手段により受信された前記受信語データを記憶するデータ記憶手段と、
行番号および列番号ごとに初期化された行処理演算データを記憶する行処理演算データ記憶手段と、
列処理演算データの書き込み要求を受けて前記列処理演算データを行番号および列番号ごとに記憶する列処理演算データ記憶手段と、
前記検査行列の行毎に、「１」の要素に対して前記データ記憶手段から前記受信語データを読み出すとともに前記行処理演算データ記憶手段から前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する列処理演算データを計算し、前記列処理演算データの書き込み要求を前記列処理演算データ記憶手段に行う列処理演算手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段から前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する前記行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込む行処理演算手段と、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した前記列処理演算データを用いて前記行により規定されるパリティ検査式の成立に対する信頼性の程度を表す信頼度係数を計算する信頼度係数計算手段と、
前記検査行列の行毎に、前記列処理演算手段により計算された前記列処理演算データと、前記行処理演算手段により計算された前記行処理演算データとに基づいて前記データ記憶手段内の前記受信語データを更新するデータ更新手段と、
前記列処理演算手段の処理、前記行処理演算手段の処理、前記信頼度係数計算手段の処理および前記データ更新手段の処理を１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記列処理演算手段の処理、前記行処理演算手段の処理、前記信頼度係数計算手段の処理および前記データ更新手段の処理の実行を省略する繰り返し制御手段と、
を備えた低密度パリティ検査符号の復号装置。
【請求項６】
前記検査行列におけるすべての行について前記信頼度係数が前記閾値を満たしたとき、または、所定回数の前記繰り返しを行ったとき、前記繰り返し制御手段による繰り返し実行を終了させる終了手段と、
前記データ記憶手段から前記受信語データを読み出し、硬判定を行うことにより、復号語データを出力する、硬判定手段と、
をさらに備えたことを特徴とする請求項５に記載の復号装置。
【請求項７】
前記検査行列の行毎に、第１の値または第２の値を示すフラグを記憶するフラグ記憶手段と、
前記行毎の前記フラグを前記第２の値に初期化するフラグ初期化手段と、をさらに備え、
前記信頼度係数計算手段は、前記行毎の前記信頼度係数が前記閾値を満たしたときは、前記行毎の前記フラグを第１の値に変更し、
前記繰り返し制御手段は、前記行毎に前記フラグ記憶手段を参照することにより前記行毎の前記信頼度係数が前記閾値を満たすかどうかを判断する、
ことを特徴とする請求項５に記載の復号装置。
【請求項８】
検査行列により定義される低密度パリティ検査符号を復号する復号方法であって、
受信語データを受信することにより、初期化された列処理演算データを行番号および列番号ごとに列処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した列処理演算データを用いて前記行により規定されるパリティ検査式の成立性に対する信頼性の程度を表す信頼度係数を計算し、
前記検査行列の列毎に、「１」の要素に対して前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する前記列処理演算データを計算し、計算した列処理演算データを行番号および列番号ごとに前記列処理演算データ記憶手段に書き込み、
前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記列処理演算データの計算および書き込みを１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記行処理演算データの計算および書き込み、ならびに前記信頼度係数の計算を省略する
ことを特徴とする低密度パリティ検査符号の復号方法。
【請求項９】
前記セットを１回以上繰り返し実行したとき、前記検査行列の「１」の要素に対して、前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、読み出した前記行処理演算データに基づき前記受信語データを補正し、
補正した受信語データを硬判定することにより硬判定データを取得し、
前記検査行列に基づき前記硬判定データをパリティ検査し、
前記パリティ検査の結果が真であるときは、前記硬判定データを復号語データとして出力し、
前記パリティ検査の結果が偽であるときは、前記セットの繰り返し実行を引き続き行う、
ことを特徴とする請求項８に記載の復号方法
【請求項１０】
前記検査行列における全ての行に対して前記信頼度係数が前記閾値を満たしたとき、または前記セットを所定回数繰り返し実行したとき、前記セットの繰り返し実行を終了し、
前記検査行列の「１」の要素に対して、前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、読み出した前記行処理演算データに基づき前記受信語データを補正して補正受信語データを生成し、
前記補正受信語データを硬判定することにより硬判定データを取得し、
前記硬判定データを復号語データとして出力する、
ことを特徴とする請求項８に記載の復号方法。
【請求項１１】
検査行列により定義される低密度パリティ検査符号を復号する復号方法であって、
受信語データを受信し、受信した受信語データをデータ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記データ記憶手段から前記受信語データを読み出すとともに、初期化された行処理演算データを行番号および列番号ごとに記憶した行処理演算データ記憶手段から「１」の要素に対して前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する列処理演算データを計算し、前記列処理演算データを行番号および列番号ごとに列処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段から前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する前記行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した前記列処理演算データを用いて前記行により規定されるパリティ検査式の成立に対する信頼性の度合いを表す信頼度係数を計算し、
前記検査行列の行毎に、前記第４の処理で計算された前記列処理演算データと、前記第５の処理で計算された前記行処理演算データとに基づいて前記データ記憶手段内の前記受信語データを更新し、
前記列処理演算データの計算および書き込み、前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記受信語データの更新を１セットとして繰り返し実行し、
前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては、前記列処理演算データの計算および書き込み、前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記受信語データの更新を省略する、
ことを特徴とする低密度パリティ検査符号の復号方法。
【請求項１２】
前記検査行列におけるすべての行について前記信頼度係数が前記閾値を満たしたとき、または、前記セットを所定回数繰り返し実行したとき、前記セットの繰り返し実行を終了し、
前記データ記憶手段から前記受信語データを読み出し、硬判定を行うことにより、復号語データを出力する、
ことを特徴とする請求項１１に記載の復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信システムや記録システムなどに用いられるＬＤＰＣ(Low Densｉty Parｉty Check：低密度パリティ検査) 符号を復号する復号装置および復号方法に関し、特に復号アルゴリズムに関わる。
【背景技術】
【０００２】
ＬＤＰＣ符号は、パリティ検査行列を用いて行処理演算と列処理演算と呼ばれる確率計算を繰り返し行い、受信語データの事後確率を求めることで復号する。
【０００３】
行処理演算とは、パリティ検査行列における行（パリティ検査式）毎に、「１」の要素に対応する列処理演算データを用いて「１」の要素毎の行処理演算データを求める処理である。また列処理演算とは、パリティ検査行列における列毎に、「１」の要素に対応する行処理演算データを用いて「１」の要素毎の列処理演算データを求める処理である。一般には、パリティ検査行列の全ての行に対して行処理演算を行った後、全ての列に対して列処理演算を行う。
【０００４】
ＬＤＰＣ符号の復号処理において、パリティ検査行列の行方向に処理演算を行う行処理演算は、非線形関数の計算を行うため特に演算量が大きい。そのため、一般には非特許文献１で提案されているように、パリティ検査行列における各行の各々において、「１」の要素毎に、当該要素を除く他の「１」の要素に対応する列処理演算データのうち最小値を、当該「１」の要素に対する行処理演算データとして求めるmｉn-sum復号が用いられる。
【非特許文献１】Marc P. C. Fossorｉer, M. Mｉhaljevｉc and H. Ｉmaｉ“Reduced Complexｉty Ｉteratｉve Decodｉng of Low-Densｉty Parｉty Check Codes Based on Belｉef Propagaton” ＩEEE Trans..on Commun. Vol.47, No.5, pp.673-680, May. 1999
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかしながらmｉn-sum復号を用いても、列処理演算データの最小値を計算するための比較演算を行（パリティ検査式）に含まれる「１」の数分だけ繰り返し行わなければならず、復号処理全体の中に占める行処理演算の量は依然として大きい。特に符号化率の高いLDPC符号では、行（パリティ検査式）に含まれる「１」の数が多いため、演算量が特に大きくなり、復号スループットが低下するといった問題があった。
【０００６】
本発明は、低密度パリティ検査符号の復号に要する演算量を低減することにより高い復号スループットを得ることができるようにした低密度パリティ検査符号の復号装置および復号方法を提供する。
【課題を解決するための手段】
【０００７】
本発明の一態様としての復号装置は、
検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、
受信語データを受信する受信手段と、
前記受信手段により受信された受信語データを、初期化された列処理演算データとして行番号および列番号ごとに記憶する列処理演算データ記憶手段と、
行処理演算データの書き込み要求を受けて前記行処理演算データを行番号および列番号ごとに記憶する行処理演算データ記憶手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する行処理演算データを計算し、計算された行処理演算データの前記書き込み要求を前記行処理演算記憶手段に行う、行処理演算手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、前記行により規定されるパリティ検査式の成立に対する信頼性の程度を表す信頼度係数を計算する信頼度係数計算手段と、
前記検査行列の列毎に、「１」の要素に対して前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する前記列処理演算データを計算し、計算された列処理演算データを行番号および列番号ごとに前記列処理演算データ記憶手段に書き込む列処理演算手段と、
前記行処理演算手段の処理と前記信頼度係数計算手段の処理と前記列処理演算手段の処理とを１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記行処理演算手段の処理と前記信頼度係数計算手段の処理を省略する繰り返し制御手段と、
を備える。
【０００８】
本発明の一態様としての復号装置は、
検査行列により定義される低密度パリティ検査符号を復号する復号装置であって、
受信語データを受信する受信手段と、
前記受信手段により受信された前記受信語データを記憶するデータ記憶手段と、
行番号および列番号ごとに初期化された行処理演算データを記憶する行処理演算データ記憶手段と、
列処理演算データの書き込み要求を受けて前記列処理演算データを行番号および列番号ごとに記憶する列処理演算データ記憶手段と、
前記検査行列の行毎に、「１」の要素に対して前記データ記憶手段から前記受信語データを読み出すとともに前記行処理演算データ記憶手段から前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する列処理演算データを計算し、前記列処理演算データの書き込み要求を前記列処理演算データ記憶手段に行う列処理演算手段と、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段から前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する前記行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込む行処理演算手段と、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した前記列処理演算データを用いて前記行により規定されるパリティ検査式の成立に対する信頼性の程度を表す信頼度係数を計算する信頼度係数計算手段と、
前記検査行列の行毎に、前記列処理演算手段により計算された前記列処理演算データと、前記行処理演算手段により計算された前記行処理演算データとに基づいて前記データ記憶手段内の前記受信語データを更新するデータ更新手段と、
前記列処理演算手段の処理、前記行処理演算手段の処理、前記信頼度係数計算手段の処理および前記データ更新手段の処理を１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記列処理演算手段の処理、前記行処理演算手段の処理、前記信頼度係数計算手段の処理および前記データ更新手段の処理の実行を省略する繰り返し制御手段と、
を備える。
【０００９】
本発明の一態様としての復号方法は、
検査行列により定義される低密度パリティ検査符号を復号する復号方法であって、
受信語データを受信することにより、初期化された列処理演算データを行番号および列番号ごとに列処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段に記憶された前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した列処理演算データを用いて前記行により規定されるパリティ検査式の成立性に対する信頼性の程度を表す信頼度係数を計算し、
前記検査行列の列毎に、「１」の要素に対して前記行処理演算データ記憶手段に記憶された前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する前記列処理演算データを計算し、計算した列処理演算データを行番号および列番号ごとに前記列処理演算データ記憶手段に書き込み、
前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記列処理演算データの計算および書き込みを１セットとして繰り返し実行し、前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては前記行処理演算データの計算および書き込み、ならびに前記信頼度係数の計算を省略する
ことを特徴とする。
【００１０】
本発明の一態様としての復号方法は、
検査行列により定義される低密度パリティ検査符号を復号する復号方法であって、
受信語データを受信し、受信した受信語データをデータ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記データ記憶手段から前記受信語データを読み出すとともに、初期化された行処理演算データを行番号および列番号ごとに記憶した行処理演算データ記憶手段から「１」の要素に対して前記行処理演算データを読み出し、列処理演算を行うことにより前記「１」の要素に対する列処理演算データを計算し、前記列処理演算データを行番号および列番号ごとに列処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、「１」の要素に対して前記列処理演算データ記憶手段から前記列処理演算データを読み出し、行処理演算を行うことにより前記「１」の要素に対する前記行処理演算データを計算し、計算した行処理演算データを行番号および列番号ごとに行処理演算データ記憶手段に書き込み、
前記検査行列の行毎に、前記列処理演算データ記憶手段から読み出した前記列処理演算データを用いて前記行により規定されるパリティ検査式の成立に対する信頼性の度合いを表す信頼度係数を計算し、
前記検査行列の行毎に、前記第４の処理で計算された前記列処理演算データと、前記第５の処理で計算された前記行処理演算データとに基づいて前記データ記憶手段内の前記受信語データを更新し、
前記列処理演算データの計算および書き込み、前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記受信語データの更新を１セットとして繰り返し実行し、
前記セットを繰り返し実行する間において前記信頼度係数が閾値を満たした行に対しては、前記列処理演算データの計算および書き込み、前記行処理演算データの計算および書き込み、前記信頼度係数の計算、および前記受信語データの更新を省略する、
ことを特徴とする。
【発明の効果】
【００１１】
本発明により、低密度パリティ検査符号の復号にかかる演算量を低減し、高い復号スループットを得ることができる。
【発明を実施するための最良の形態】
【００１２】
以下、図面を参照しながら本実施形態について詳細に説明する。
【００１３】
図１は、本発明の第１の実施形態に係わる復号装置の構成を示すブロック図である。なお、この復号装置は、符号化を行う符号化装置の構成も同時に備えていてもよい。
【００１４】
上記復号装置は、入力メモリ１０１、スケジューラ（繰り返し制御手段、終了手段）１０２、行処理部（行処理演算手段、信頼度係数計算手段）１０３、中間メモリ（行処理演算データ記憶手段、列処理演算データ記憶手段）１０４、列処理部（列処理演算手段、データ補正手段）１０５、硬判定部１０６、パリティ検査部１０７、及び出力バッファ（出力手段）１０８を備える。
【００１５】
入力メモリ１０１は、図示しない前段の信号処理部から入力される受信語データ（符号データフレーム）を受け取り、受け取った受信語データを、復号処理の間、保持する。入力メモリ１０１はたとえば受信語データを受信する受信手段を含む。受信語データは、符号化装置で生成される符号語のビット数と同数の要素からなり、各要素はそれぞれ対応するビットの対数尤度比（ＬＬＲ：Log Lｉkelｉhood Rate）を表す。入力メモリ１０１に保持される受信語データの各対数尤度比は入力ＬＬＲと称する。
【００１６】
ここで対数尤度比（ＬＬＲ）とは、データビットが０である確率P(x=0)と１である確率P(x=1)の比の対数値（底は自然対数）をとったもので、以下の式で表される。
【数１】
2009100222.tif 000003
【００１７】
受信語データの一例を図９に示す。ここでは７ビットからなる符号語に対応する受信語データが示され、受信語データは７個のＬＬＲ（入力ＬＬＲ）からなる。
【００１８】
スケジューラ（繰り返し制御手段）１０２は、復号処理全体の制御を行う。スケジューラ１０２は、行処理部１０３及び列処理部１０５へそれぞれ行処理（行処理演算と、シンドローム値（信頼度係数）演算）、および列処理（列処理演算と、出力ＬＬＲ（補正ＬＬＲ）演算）の実行を指示する。本実施形態では、行処理および列処理を１セットとし、このセットを１回以上繰り返し実行することで復号が行われる。
【００１９】
また、スケジューラ１０２は、復号開始時に入力メモリ１０１内の受信語データ（入力ＬＬＲ）を中間メモリ１０４に送出することを入力メモリ１０１に指示する。
【００２０】
またスケジューラ１０２は、列処理部１０５による列処理のタイミングに合わせて、入力メモリ１０１内の受信語データ（入力ＬＬＲ）を列処理部１０５へ出力するように入力メモリ１０１に指示する。
【００２１】
また、スケジューラ１０２は、パリティ検査部１０７から入力されるパリティ検査結果（真ＯＲ偽）、及び現時点までに行った復号の繰り返し回数から、復号処理を終了するか否かを判断し、復号処理の終了を決定したときは、復号結果（復号語）を、図示しない後段の信号処理部へ出力するよう出力バッファ１０８へ指示する。
【００２２】
また，スケジューラ１０２は、必要最小限の行処理のみを実行するよう行処理部１０３を制御することで、復号処理全体で必要となる演算量を削減し、復号スループットを向上することを特徴としている。この特徴の詳細については、行処理部１０３および列処理部１０５の後に、説明する。
【００２３】
中間メモリ１０４は、行処理部１０３と列処理部１０５間でデータをやりとりするために用いられる。復号開始時は、スケジューラ１０２の指示に応じて入力メモリ１０１から入力される受信語データ（入力ＬＬＲ）を、初期化された列処理演算データ（列要素ＬＬＲ）として、パリティ検査行列における行番号および列番号ごとに記憶する。
【００２４】
パリティ検査行列の一例を図９（Ｂ）に示す。このパリティ検査行列は７ビットの符号語に対応するものであり、たとえば図９（Ａ）の受信語データの復号に用いることができる。列処理演算データの例を図１０（Ｂ）に示す（詳細は後述する）。パリティ検査行列における列の個数はたとえば受信語データの要素数と同一であり、同一の列番号の各行要素には同一の入力ＬＬＲ（受信語データにおいて列番号に対応する入力ＬＬＲ）が、初期化された列処理演算データとして中間メモリ１０４に記憶される。ただし、初期化された列処理演算データは、パリティ検査行列において「１」の要素ついてだけ記憶し、「０」の要素については、演算で使用しないため、記憶しなくてもよい。たとえば図９（Ｂ）のパリティ検査行列の場合、z14,z16,z17などは記憶してなくてもよい。
【００２５】
行処理部（行処理演算手段、信頼度係数計算手段）１０３は、スケジューラ１０２から指定される行インデックスのパリティ検査式に従って行処理（行処理演算と、シンドローム値（信頼度係数）演算）を実行する。ここで行インデックスとは、ＬＤＰＣ(Low Densｉty Parｉty Check：低密度パリティ検査)符号のパリティ検査行列の行インデックスを意味する。
【００２６】
行処理部１０３は、具体的には、検査行列における指定された行の「１」の要素に対して中間メモリ１０４に記憶された列処理演算データ（最初は初期化された列処理演算データ）を読み出し、行処理演算を行うことにより、前記「１」の要素に対する行要素ＬＬＲ（行処理演算データ）を計算する。
【００２７】
また、行処理部１０３は、上記行処理で読み出された列処理演算データを用いて、上記指定された行のパリティ検査式の成立に対する信頼性の程度を表すシンドローム値（信頼度係数）を計算する。
【００２８】
行処理部１０３は、シンドローム値（信頼度係数）をスケジューラ１０２へ出力し、行要素ＬＬＲ（行処理演算データ）を行番号および列番号ごとに中間メモリ１０４へ書き込む。
【００２９】
なお、後述するように１回目の復号では、行処理部１０３は、スケジューラ１０２から全ての行インデックスを順次指定されるが、２回目あるいはそれ以降の復号では、最小限の行インデックスが指定され、これにより、復号処理全体で必要となる演算量を低減している。
【００３０】
ここでシンドローム値（信頼度係数）は以下の数式２により、行要素ＬＬＲ（行処理演算データ）は数式３により求められる。
【数２】
2009100222.tif 000004
上記の数式２および数式３において、ｍはパリティ検査式の行インデックスを表し、ｎは列インデックスを表す。図９（Ｂ）の場合、ｍは１〜３、ｎは１〜７である。
【００３１】
Ｎ（ｍ）は行インデックスｍのパリティ検査式において「１」の値をもつ列インデックスの集合を表し、Ｎ(ｍ)＼ｎは、集合Ｎ（ｍ）のうちｎを除いた列インデックスの部分集合を表す。
【００３２】
【数３】
2009100222.tif 000005
は
【数４】
2009100222.tif 000006
の符号を示し、
【数５】
2009100222.tif 000007
は列要素ＬＬＲ（列処理演算データ）
【数６】
2009100222.tif 000008
の符号を示す。
【００３３】
【数７】
2009100222.tif 000009
は、列インデックス集合Ｎ（ｍ）に含まれる列インデックスに対応する列要素ＬＬＲ（列処理演算データ）
【数８】
2009100222.tif 000010
のうち、絶対値が最も小さい列要素ＬＬＲ（列処理演算データ）を示す。同様に
【数９】
2009100222.tif 000011
は、列インデックス集合Ｎ(ｍ)＼ｎに含まれる列インデックスに対応する列要素ＬＬＲ（列処理演算データ）
【数１０】
2009100222.tif 000012
のうち、絶対値が最も小さい列要素ＬＬＲ（列処理演算データ）を示す。
【００３４】
ｉは復号処理の繰り返し回数を表し、ｉ回目の復号処理における行処理演算で得られる行要素ＬＬＲ（行処理演算データ）
【数１１】
2009100222.tif 000013
は、ｉ−１回目の復号処理で得られる列要素ＬＬＲ（列処理演算データ）
【数１２】
2009100222.tif 000014
を用いて計算される。なお１回目の復号処理では、
【数１３】
2009100222.tif 000015
となる（中間メモリ１０４の説明を参照）。Fnは、図示しない前段の信号処理部から復号装置へ入力される入力ＬＬＲ（受信語データ）を表す。
【００３５】
上記の数式２に従ってシンドローム値（信頼度係数）を具体的に求める様子と、上記の数式３にしたがって行要素ＬＬＲ（行処理演算データ）を具体的に求める様子とを図１０（Ｂ）に示す。ここでは行要素ＬＬＲ（行処理演算データ）としてr11を求める例が示され、またシンドローム値（信頼度係数）としてs1を求める例が示される。ただしパリティ検査行列は図９（Ｂ）に示すものであるとする。r11を求めるには、１行目で「１」の要素に対応する列処理演算データz12,z13,z15を中間メモリ１０４から読み出し（z11は用いない）上記数式２に従って計算すればよい。また、行要素ＬＬＲ（行処理演算データ）s1を求めるには、１行目で「１」の要素に対応する列処理演算データz11,z12,z13,z15を中間メモリ１０４から読み出し、上記数式３に従って計算すればよい。
【００３６】
ここで数式２および数式３を比べると分かるように、シンドローム値（信頼度係数）
【数１４】
2009100222.tif 000016
の計算では行インデックスｍのパリティ検査式に含まれる全ての列インデックスの列要素ＬＬＲ（列処理演算データ）
【数１５】
2009100222.tif 000017
を用いるのに対し、行要素ＬＬＲ（行処理演算データ）
【数１６】
2009100222.tif 000018
の計算では着目している列インデックスｎを除いた列要素ＬＬＲ（列処理演算データ）
【数１７】
2009100222.tif 000019
を用いて計算する。そのため、行要素ＬＬＲ（行処理演算データ）
【数１８】
2009100222.tif 000020
の計算の際に数式３を用いず、数式４を用いて計算する方法もある。この方法では、シンドローム値（信頼度係数）を計算する際に、絶対値が最小の列要素ＬＬＲ（列処理演算データ）だけではなく、絶対値が最小の列要素ＬＬＲの列インデックス
【数１９】
2009100222.tif 000021
と，２番目に絶対値が最小な列要素ＬＬＲ（列処理演算データ）を
【数２０】
2009100222.tif 000022
として保持しておく。
【数２１】
2009100222.tif 000023
【００３７】
また、行処理演算では、数式３の代わりに、
【数２２】
2009100222.tif 000024
に対し係数αを乗算する数式５、もしくは係数βを減算する数式６を用いてもよい。
【数２３】
2009100222.tif 000025
【００３８】
上記数式６においてｍａｘ（ｘ、ｙ）は、ｘもしくはｙのうち、どちらか大きな方を出力する関数である。これらの数式５および数式６に示すアルゴリズムはmodｉfｉed-mｉn-sumアルゴリズムと呼ばれ、一般に数式３で示すmｉn-sumアルゴリズムよりも復号性能がよい。
【００３９】
列処理部１０５は、スケジューラ１０２から指定される列インデックスの列について列処理（列処理演算、出力ＬＬＲ（補正ＬＬＲ）演算）を実行する。列処理部１０５は、すべての列インデックスについてスケジューラ１０２から順次、指定され、指定された各列インデックスについて列処理を行う。
【００４０】
具体的には、検査行列における指定された列の「１」の要素に対して中間メモリ１０４に記憶された行要素ＬＬＲ（行処理演算データ）を読み出し、読み出した行要素ＬＬＲ（行処理演算データ）と、入力メモリ１０１から入力される入力ＬＬＲ（受信語データにおいて、スケジューラ１０２により指定された列に対応するＬＬＲ）とに基づき、列処理演算を行うことにより、前記「１」の要素に対する列要素ＬＬＲ（列処理演算データ）を計算する。列処理部１０５は、計算した列要素ＬＬＲ（列処理演算データ）を、行番号および列番号ごとに中間メモリ１０４に書き込む（以前の値は更新されるものとする）。以下に、列要素ＬＬＲ（列処理演算データ）
【数２４】
2009100222.tif 000026
を求める計算式を示す。
【数２５】
2009100222.tif 000027
【００４１】
ここで、Fnは列インデックスｎの入力ＬＬＲ（受信語データ）を表し、
【数２６】
2009100222.tif 000028
は行処理部１０３で計算される行要素ＬＬＲ（行処理演算データ）を表す。さらにＭ(ｎ)＼ｍは、集合Ｍ（ｎ）のうちｍを除いた行インデックスの部分集合を表す。
【００４２】
上記の数式７に従って列要素ＬＬＲ（列処理演算データ）を求める様子を図１０（Ａ）に示す。ここではz11を求める例が示される。ただしパリティ検査行列は図９（Ｂ）に示すものであるとする。z11を求めるには、１列目で「１」の要素に対応する列処理演算データr21を中間メモリ１０４から読み出し（z31は用いない）、また、１列目に対応する入力ＬＬＲ（受信語データ）F1を入力メモリ１０１から読み出し、上記数式７に従って計算すればよい。
【００４３】
また列処理部１０５は、スケジューラ１０２から指定された列における「１」の要素に対して、中間メモリ１０４に記憶された行要素ＬＬＲ（行処理演算データ）を読み出し、読み出した前記行処理演算データに基づき、入力メモリ１０１から入力される入力ＬＬＲ（受信語データにおいて、スケジューラ１０２により指定された列に対応するＬＬＲ）を補正することにより、出力ＬＬＲ（補正ＬＬＲ）を計算する。列処理部１０５は、計算した、出力ＬＬＲ（補正ＬＬＲ）を硬判定部１０６に出力する。つまり、入力メモリ１０１に入力された受信語データ（入力ＬＬＲ）は、行処理および列処理により、補正受信語データ（出力ＬＬＲあるいは補正ＬＬＲ）へ補正されて、出力される。
【００４４】
ここで出力ＬＬＲ（補正ＬＬＲ）
【数２７】
2009100222.tif 000029
を求める計算式を以下に示す。以下のように入力ＬＬＲFnと行要素ＬＬＲ（行処理演算データ）
【数２８】
2009100222.tif 000030
から出力ＬＬＲ
【数２９】
2009100222.tif 000031
が求まる。
【数３０】
2009100222.tif 000032
【００４５】
数式７の列要素ＬＬＲ（列処理演算データ）
【数３１】
2009100222.tif 000033
が、着目している行インデックスの行要素ＬＬＲ（行処理演算データ）
【数３２】
2009100222.tif 000034
を第２項の総和に含めないのに対し、出力ＬＬＲ（補正ＬＬＲ）
【数３３】
2009100222.tif 000035
の計算では、着目している行インデックスを含めて、列インデックスｎの列中に“１”が存在する行インデックスの行要素ＬＬＲ（行処理演算データ）
【数３４】
2009100222.tif 000036
を第２項の総和に含める。つまり、出力ＬＬＲ（補正ＬＬＲ）
【数３５】
2009100222.tif 000037
は、列インデックスｎの列中に“１”が存在する行のパリティ検査式を用いて計算された行要素ＬＬＲ（行処理演算データ）
【数３６】
2009100222.tif 000038
の総和を、入力ＬＬＲ Fnに加算した値となる。
【００４６】
上記の数式８に従って出力ＬＬＲ（補正ＬＬＲ）を求める様子を図１０（Ａ）に示す。ここではz2を求める例が示される。ただしパリティ検査行列は図９（Ｂ）に示すものであるとする。z2を求めるには、２列目で「１」の要素に対応する行要素ＬＬＲ（行処理演算データ）r12,r32を中間メモリ１０４から読み出し、また、２列目に対応する入力ＬＬＲ（受信語データ）F2を入力メモリ１０１から読み出し、上記数式８に従って計算すればよい。
【００４７】
中間メモリ１０４は、上述したように、行処理部１０３と列処理部１０５間でデータをやりとりするために用いられ、行処理部１０３から書き込まれる行要素ＬＬＲ（行処理演算データ）
【数３７】
2009100222.tif 000039
と、列処理部１０５から書き込まれる列要素ＬＬＲ（列処理演算データ）
【数３８】
2009100222.tif 000040
を保持する。中間メモリ１０４は行処理部１０３および列処理部１０５からの書き込み要求を受けて、行要素ＬＬＲ（行処理演算データ）
【数３９】
2009100222.tif 000041
と列要素ＬＬＲ（列処理演算データ）
【数４０】
2009100222.tif 000042
とを記憶する。中間メモリ１０４は、必要に応じて行要素ＬＬＲ（行処理演算データ）
【数４１】
2009100222.tif 000043
を列処理部１０５へ、列要素ＬＬＲ（列処理演算データ）
【数４２】
2009100222.tif 000044
を行処理部１０３へ、それぞれ出力する。
【００４８】
図２は、スケジューラ１０２の詳細ブロック図である。ただし、図２では、行処理の計算量の低減に関わるブロックのみを示し、その他の基本的な処理を行うブロック、たとえば復号の繰り返し回数をカウントするカウンタ等の表示は省略している。
【００４９】
スケジューラ１０２は行処理判定部２０１と行処理制御部２０２を備える。
【００５０】
行処理判定部２０１はシンドロームチェック部２０１Ａ、シンドローム値判定部２０１Ｂ、及び行処理判定メモリ２０１Ｃ（フラグ記憶手段、フラグ初期化手段）を有する。
【００５１】
行判定処理部２０１は、行処理部１０３から行ごとに入力されるシンドローム値（信頼度係数）を符号と絶対値とに分離し、符号の情報をシンドロームチェック部２０１Ａ、絶対値の情報をシンドローム値判定部２０１Ｂにそれぞれ入力する。
【００５２】
シンドロームチェック部２０１Ａはシンドローム値の符号の正負を検査し、正の場合に真を、負の場合に偽を行処理判定メモリ２０１Ｃへ出力する。
【００５３】
シンドローム値判定部２０１Ｂは、入力された絶対値があらかじめ定義した閾値よりも大きいかどうかを判定し、閾値よりも大きい場合には真を、閾値以下の場合には偽を行処理判定メモリ２０１Ｃへ出力する。なお、ここでの閾値は計算機シミュレーションなどの数値実験によりあらかじめ求めておくものとする。また閾値は、行インデックス毎に異なる値を設定してもよい。
【００５４】
行処理判定メモリ２０１Ｃは、検査行列の行インデックス毎に処理フラグを有する。処理フラグの初期値はたとえば真（第２の値）に設定されている。行処理判定メモリ２０１Ｃは、シンドロームチェック部２０１Ａ及びシンドローム値判定部２０１Ｂからの入力が共に真である場合に、スケジューラ１０２へ入力されたシンドローム値に対応する行インデックスの処理フラグを偽（第１の値）にする。上述したように、行インデックスとは、ＬＤＰＣ(Low Densｉty Parｉty Check：低密度パリティ検査)符号のパリティ検査行列の行インデックスを意味する。
【００５５】
行処理制御部２０２は、行処理判定メモリ２０１Ｃに基づき、次に処理すべき行インデックスを選択し、選択した行インデックスを指定することにより行処理の実行を行処理部１０３へ指示する。この際、処理フラグが偽である行インデックスの行処理はスキップするように行インデックスの番号を選択する。選択の方法は、たとえば行インデックス番号の昇順である。１つの行処理が終了するごとに（シンドローム値（信頼度係数）が行処理部１０３から入力されるごとに）、次に処理すべき行インデックスを選択し、選択した行インデックスを行処理部１０３に指示する。このように必要最小限の行処理のみを実行するよう行処理部１０３を制御することで、復号処理全体で必要となる計算量を削減し、復号スループットを向上することができる。
【００５６】
硬判定部１０６は、列処理部１０５から入力される出力ＬＬＲ（補正ＬＬＲ）の正負を判定する。正の時は０、負のときは１と判定する。ビット毎に判定された０または１の硬判定結果（硬判定データ）はパリティ検査部１０７と出力バッファ１０８とへ出力される。
【００５７】
パリティ検査部１０７は、硬判定部１０６から入力される硬判定データが、ＬＤＰＣ符号のパリティ検査式（検査行列における各行の検査式）を満たすかどうかを検査し、パリティ検査式がすべて満たされるか否かを示す検査結果をスケジューラ１０２へ出力する。
【００５８】
出力バッファ１０８は、硬判定部１０６から入力される硬判定データを保持する。出力バッファ１０８は、スケジューラ１０２から出力の指示がなされた硬判定データを、図示しない後段の信号処理部へ出力する。出力の指示がなかった硬判定データはたとえば廃棄する。スケジューラ１０２では、硬判定部１０６から真（すべての検査式が満たされる）を示す検査結果が入力されたとき、この検査結果が得られた硬判定データを出力するように出力バッファ１０８に指示する。
【００５９】
次に、上記のような構成を有する復号装置の動作について説明する。
【００６０】
図３は、図１の復号装置の動作の流れを示したフローチャートである。なお、図３ではｍが行インデックス、ｎが列インデックスを表し、パリティ検査行列の行数をＭ、列数をＮとする。また、ｉを繰り返し回数とし、Ｉｍａｘを最大繰り返し回数とする。処理３０２〜処理３０８が行処理に相当し、処理３０９〜処理３１２が列処理に相当する。
【００６１】
図示しない前段の信号処理部より、受信語データ（入力ＬＬＲ）が図１の復号装置に入力される。受信語データが全て入力されると、復号装置は復号処理を開始する。なお入力された受信語データは、復号処理が行われる間、入力メモリ１０１において保持される。
【００６２】
まず、ステップ３０１では初期処理を行う。具体的には、行処理判定メモリ２０１Ｃにおける行処理フラグを全て真（第２の値）にし、さらに繰り返し回数ｉを１に設定する。
【００６３】
次にステップ３０２で、行処理を実行する行インデックスｍを１に設定する。
【００６４】
次にステップ３０３で、行インデックスｍの行処理フラグが真かどうかを判定し、行処理フラグが偽（第１の値）の場合には、行処理演算とシンドローム値（信頼度係数）演算とをスキップし、ステップ３０７へ進む。行処理フラグが真の場合には、ステップ３０４にて行インデックスｍについて行処理演算を実行する。そして、続くステップ３０５で、シンドローム値（信頼度係数）の絶対値が予め定めた閾値より大きく、かつ、シンドローム値（信頼度係数）の符号が０（正）かどうかを判定する（シンドローム値（信頼度係数）演算）。
【００６５】
ステップ３０５の判定がＮＯの場合にはステップ３０７へ進む。ステップ３０５の判定がＹＥＳの場合にはステップ３０６へ進み、行インデックスｍの行処理フラグを偽に設定する。
【００６６】
ステップ３０７では、行インデックスｍが最終行インデックスＭであるかどうかを判定し、ＮＯの場合にはステップ３０８で行インデックスｍをインクリメントし、ステップ３０３へ戻る。
【００６７】
ステップ３０７の判定がＹＥＳの場合にはステップ３０９に進み、列インデックスｎを１に設定する。そしてステップ３１０で列インデックスｎについて列処理を実行する。
【００６８】
続いて、ステップ３１１で列インデックスｎが最終列インデックスＮであるかどうかを判定し、ＮＯの場合にはステップ３１２において列インデックスｎをインクリメントし、処理３１０へ戻る。
【００６９】
ステップ３１１の判定がＹＥＳの場合には、硬判定を行った後、ステップ３１３においてパリティ検査を行う。パリティ検査の結果が真（すべての検査式が満たされる）の場合には復号処理を終了し、硬判定により得られた硬判定データを復号度データとして出力し、偽の場合にはステップ３１４へ進む。
【００７０】
ステップ３１４では繰り返し回数ｉが最大繰り返し数Ｉｍａｘに達したかどうかを判定し、ＹＥＳの場合には復号処理を終了する。硬判定により得られた硬判定データは後段に出力してもよいし廃棄してもよい。ＮＯの場合にはステップ３１５で繰り返し回数ｉをインクリメントした後、ステップ３０２へ戻る。
【００７１】
ところで、図３の説明では、ステップ３１３において繰り返し１回毎にパリティ検査を行うこととしたが、複数回の繰り返し毎にパリティ検査を行っても良い（その場合、出力ＬＬＲ（補正ＬＬＲ）演算も複数回の繰り返し毎に行っても良い）。繰り返し１回毎に行う場合に比べ、余分に繰り返しが発生する可能性があるが、本発明では行処理フラグにより行処理を制御するため、演算量が大きな行処理に関しては余分な演算量は発生しない。例えば平均的に繰り返しが５回発生するような環境では、パリティ検査を繰り返し５回毎に行うように設定することで１〜４回目のパリティ検査にかかる演算量を削減することができる。
【００７２】
また、行処理フラグが偽（“０”）ということは、パリティ検査を満たしていることを意味するので、全ての行インデックスの行処理フラグの論理和が偽になった時点で処理完了を判断し、パリティ検査を行うことなく、硬判定を行い、復号処理を終了するようにしてもよい。
【００７３】
図４は、ガウス性熱雑音通信路において本実施形態の復号装置と従来の復号装置との行処理演算量の比を示すグラフである。このグラフは本発明者らによる独自の数値実験の結果に基づき得られたものである。また図５は、第１の実施形態の復号装置と従来の復号装置のそれぞれのビット誤り率（BER）特性を示すグラフである。
【００７４】
ＬＤＰＣ符号の検査行列としては、符号長1004bｉt、パリティ長502bｉt、符号化率0.5のレギュラーＬＤＰＣ符号の検査行列を用い、最大繰り返し数を２０回とし、変調方式はＢＰＳＫとした。
【００７５】
図４において、横軸がＥｂ／Ｎ０（ビット当たりのエネルギー対雑音電力比）を示し、縦軸が従来方式の行処理演算量を１とした場合の本発明の行処理演算量を示している。図４より、本実施形態によれば従来方式と比べ行処理演算量が１割弱削減できていることが理解される。
【００７６】
また図５から、本実施形態と従来方式とのビット誤り率特性がほぼ同一であることが確認できる。
【００７７】
以上から、本実施形態により、ビット誤り率特性をほとんど劣化させることなく、行処理演算量を１割弱削減できることが分かる。
【００７８】
以上のように本実施形態によれば、mｉn-sum復号の行処理で得られるシンドローム値（信頼度係数）が閾値を満たすときは行処理フラグを偽に設定し、行処理フラグが真である行のみ行処理を実行するよう制御する。これにより、必要最低限の行処理のみが実行されるため、復号全体の演算量を削減することができ、復号スループットを向上することができる。
【００７９】
次に本発明の第２の実施形態について説明する。
【００８０】
図６に本発明の第２の実施形態に係わる復号装置の構成を示すブロック図である。
【００８１】
第１の実施形態の復号装置は行処理と列処理がそれぞれ一括して実行されるFloodｉng Schedule型であったのに対し、第２の実施形態の復号装置は、行処理と列処理が、行インデックス毎に逐次的に実行されるSequentｉal Schedule型となっていることを特徴とする。なお、この復号装置は、符号化装置の構成をさらに備えていてもよい。
【００８２】
図６の復号装置は、ＬＬＲメモリ（受信手段、データ記憶手段）６０１、ＬＬＲ更新処理部（列処理演算手段、行処理演算手段、信頼度係数計算手段、データ更新手段、列処理演算データ記憶手段）６０２、中間メモリ（行処理演算データ記憶手段）６０３、スケジューラ（繰り返し制御手段、フラグ記憶手段、フラグ初期化手段）６０４、及び硬判定部６０５を備える。
【００８３】
ＬＬＲメモリ６０１は、図示しない前段の信号処理部から入力される受信語データ（入力ＬＬＲ）を記憶し、これを復号完了まで、出力ＬＬＲとして、保持する。受信語データは第１の実施形態と同様、符号語の各ビットに対応する入力ＬＬＲからなっている。ＬＬＲメモリ６０１は、スケジューラ６０４からの指示により、保持している出力ＬＬＲを、ＬＬＲ更新処理部６０２との間で入出力し、出力ＬＬＲはＬＬＲ更新処理部６０２にて更新される。そしてＬＬＲ更新処理完了時にはＬＬＲメモリ６０１は、硬判定部６０５へ、更新された受信語データ（更新された出力ＬＬＲ）を全て出力する。
【００８４】
ＬＬＲ更新処理部６０２は、スケジューラ６０４からの実行指示に従い、ＬＬＲメモリ６０１から入力される出力ＬＬＲと、中間メモリ６０３から入力される行要素ＬＬＲ（行処理演算データ）とを用いて、指定された行インデックス毎に、行処理（シンドローム値（信頼度係数）演算、行処理演算）および列処理（列処理演算、更新処理）を実行する。ＬＬＲ更新処理部６０２は、シンドローム値（信頼度係数）をスケジューラ６０２へ出力し、行要素ＬＬＲ（行処理演算データ）を中間メモリ６０３へ書き込み、出力ＬＬＲをＬＬＲメモリ６０１へ書き込む。列処理演算データについては、ＬＬＲ更新処理部６０２は、たとえば自身の内部で保持する。つまりＬＬＲ更新処理部６０２は、書き込み要求を受けて列処理演算データを行番号および列番号ごとに記憶する列処理演算データ記憶手段を含んでもよい。この列処理演算データ記憶手段は中間メモリ６０３に備えさせてもよい。
【００８５】
以下、数式を用いて行インデックスｍに対して行われる、行処理（シンドローム値（信頼度係数）演算、行処理演算）および列処理（列処理演算、更新演算）について説明する。
【００８６】
まず、出力ＬＬＲqn と行要素ＬＬＲ（行処理演算データ）
【数４３】
2009100222.tif 000045
とを用いて以下の式により列処理演算を行うことにより、列要素ＬＬＲ（列処理演算データ）を計算する。
【数４４】
2009100222.tif 000046
【００８７】
なお、復号開始時(ｉ=1)にはqmn=qn=Fn となる。Fnは、図示しない前段の信号処理部から復号装置へ入力されるＬＬＲ（受信語データ）である。続いて行処理（シンドローム値（信頼度係数）演算と、行処理演算）を実行し、シンドローム値（信頼度係数）
【数４５】
2009100222.tif 000047
と行要素ＬＬＲ（行処理演算データ）
【数４６】
2009100222.tif 000048
を以下の数式１０および数式１１により求める。
【数４７】
2009100222.tif 000049
ｎは列インデックスを表し、ｉは復号の繰り返し回数を表す。
Ｎ（ｍ）は行インデックスｍのパリティ検査式において“１”の値をもつ列インデックスの集合を表す。
Ｎ(ｍ)＼ｎは、集合Ｎ（ｍ）のうちｎを除いた列インデックスの部分集合を表す。
ｓｉｇｎ（x）、 ｍｉｎ（ｘ）は、本発明の第１の実施形態で説明した関数である。
【００８８】
ここで本発明の第１の実施形態と同様に、行要素ＬＬＲ（行演算処理データ）
【数４８】
2009100222.tif 000050
の計算は数式１０ではなく、シンドローム値
【数４９】
2009100222.tif 000051
を利用する数式４を用いて計算してもよいし、さらに数式５および数式６のようなmodｉfｉed-mｉn-sumアルゴリズムを用いてもよい。
【００８９】
数式１０により、各列インデックスの行要素ＬＬＲ（行処理演算データ）
【数５０】
2009100222.tif 000052
が計算された後、以下の数式１２に示す更新演算により出力ＬＬＲqnを更新する。なお２回目以降の繰り返しにおける復号処理では、qnの値は、１つ前の復号処理で更新されたものを引き続き使用する。
【数５１】
2009100222.tif 000053
【００９０】
このように、ＬＬＲ更新処理部６０２では、行毎に、行処理と列処理を行うことにより、出力ＬＬＲをパリティ検査式毎に更新するという特徴をもつ。
【００９１】
中間メモリ６０３は、ＬＬＲ更新処理部６０２の説明から理解されるように、ＬＬＲ更新処理部６０２により計算される行要素ＬＬＲ（行処理演算データ）
【数５２】
2009100222.tif 000054
を、ＬＬＲ更新処理部６０２からの書き込み要求を受けて、記憶する。中間メモリ６０３は、復号処理の実行の間、書き込み要求された行要素ＬＬＲ（行処理演算データ）
【数５３】
2009100222.tif 000055
を保持する。
【００９２】
スケジューラ６０４は、復号処理全体の制御を行う。
【００９３】
具体的にはスケジューラ６０４は、ＬＬＲ更新処理部６０２へＬＬＲ更新処理（行処理および列処理）の実行を指示する。
【００９４】
また、スケジューラ６０４は、ＬＬＲ更新処理部６０２から入力されるシンドローム値（信頼度係数）、及びあらかじめ与えられる最大繰り返し回数から復号処理を終了するかどうかを判断する。
【００９５】
また、スケジューラ６０４は、復号処理の終了を決定した際には、更新された受信語データ、すなわち更新された出力ＬＬＲを硬判定部６０５へ出力するようＬＬＲメモリ６０１へ指示する。
【００９６】
図７は、スケジューラ６０４の詳細ブロック図である。
【００９７】
スケジューラ６０４はＬＬＲ更新処理判定部７０１、ＬＬＲ更新処理制御部７０２、シンドローム累積部７０３、繰り返し回数カウント部７０４、及び復号完了判定部（終了手段）７０５を備える。
【００９８】
ＬＬＲ更新処理判定部７０１はシンドロームチェック部７０１Ａ、シンドローム値判定部７０１Ｂ、及びＬＬＲ更新処理判定メモリ７０１Ｃを有する。
【００９９】
ＬＬＰ更新処理判定部７０１は、ＬＬＲ更新処理部６０２から行毎に入力されるシンドローム値（信頼度係数）を符号と絶対値に分離し、符号の情報をシンドロームチェック部７０１Ａに、絶対値の情報をシンドローム値判定部７０１Ｂにそれぞれ入力する。
【０１００】
シンドロームチェック部７０１Ａは、シンドローム値（信頼度係数）の符号の正負を検査し、正の場合に真を、負の場合に偽を行処理判定メモリ７０１Ｃ及びシンドローム累積部７０３へ出力する。
【０１０１】
シンドローム値判定部７０１Ｂは、入力された絶対値があらかじめ定義した閾値よりも大きいかどうかを判定し、閾値よりも大きい場合には真を、小さい場合には偽をＬＬＲ更新処理判定メモリ７０１Ｃへ出力する。なお、閾値はあらかじめ計算機シミュレーションなどの数値実験により求めるものとする。 また閾値は、行インデックス毎に異なる値を設定してもよい。
【０１０２】
ＬＬＲ更新処理判定メモリ７０１Ｃは、検査行列における行インデックス毎にＬＬＲ更新処理フラグを保持する。ＬＬＲ更新処理フラグの初期値はたとえば真（第２の値）に設定されている。ＬＬＲ更新処理判定メモリ７０１Ｃは、シンドロームチェック部７０１Ａ及びシンドローム値判定部７０１Ｂからの入力が共に真である場合に、ＬＬＲ更新処理部６０２から入力されたシンドローム値に対応する行インデックスのＬＬＲ更新処理フラグを偽（第１の値）にする。行インデックスとは、第１の実施形態と同様、ＬＤＰＣ符号のパリティ検査行列の行インデックスを意味する。
【０１０３】
ＬＬＲ更新処理制御部７０２は、ＬＬＲ更新処理判定メモリ７０１Ｃに基づき、次にＬＬＲ更新処理を行うべき行インデックスを選択し、選択した行インデックスを指定することによりＬＬＲ更新処理の実行をＬＬＲ更新処理部６０２へ指示する。この際、ＬＬＲ更新処理フラグが偽である行インデックスのＬＬＲ更新処理はスキップするように行インデックスを選択する。行インデックスの選択方法は、たとえば行インデックス番号の昇順である。このように必要最小限のＬＬＲ更新処理のみを実行するようＬＬＲ更新処理部６０２を制御することで、復号処理全体で必要となる演算量を削減し、復号スループットを向上することができる。
【０１０４】
シンドローム累積部７０３は、シンドローム累積部７０３は、シンドロームチェック部７０１Ａから行インデックス毎に入力されるシンドロームチェック結果（真（“１”）または偽（“０”））をすべての行について累積(論理積)することによりシンドローム累積値を得る。すべての行についてシンドロームチェック結果が真となったときのみ、シンドローム累積値は真となり、１つでもシンドロームチェック結果が偽である行があるときシンドローム累積値は偽となる。シンドローム累積部７０３は、シンドローム累積値を、復号完了判定部７０５へ出力する。
【０１０５】
繰り返し回数カウント部７０４は、復号処理の繰り返し回数をカウントし、 繰り返し回数を復号完了判定部７０５へ出力する。
【０１０６】
復号完了判定部７０５は、シンドローム累積部７０３から入力されるシンドローム累積値が真になったとき、または繰り返し回数カウント部７０４から入力される繰り返し回数があらかじめ設定された最大繰り返し数に達したとき、復号処理の完了を判定する。復号完了判定部７０５は、復号処理の完了を判定したとき、更新された出力ＬＬＲ（更新された受信語データ）を硬判定部６０５へ出力するようＬＬＲメモリ６０１へ指示する。
【０１０７】
硬判定部６０５は、ＬＬＲメモリ６０１から入力される出力ＬＬＲの正負を判定し、正の時は０、負のときは１を選択する。ビット毎に判定された０または１である硬判定データは、図示しない後段の信号処理部へ出力される。
【０１０８】
次に、上記のような構成を有する復号装置の動作について説明する。
【０１０９】
図８は、図６の復号装置の動作の流れを示すフローチャートである。なお、図８ではｍが行インデックス、Ｍがパリティ検査行列の行数を表し、ｉは繰り返し回数、Ｉｍａｘは最大繰り返し回数を表す。
【０１１０】
図示しない前段の信号処理部より、受信語データ（入力ＬＬＲ）が復号装置に入力され、受信語データが全て入力されると、復号処理が開始される。入力された受信語データ（入力ＬＬＲ）は、復号処理の間、ＬＬＲメモリ６０１で出力ＬＬＲとして保持され、復号処理により更新される。
【０１１１】
まず、ステップ８０１では初期処理を行う。具体的には、ＬＬＲ更新処理判定メモリ７０１Ｃが持つＬＬＲ更新処理フラグを全て真にし、繰り返し回数ｉを１に設定する。
【０１１２】
次にステップ８０２で、ＬＬＲ更新処理を実行する行インデックスｍを１に設定する。
【０１１３】
次にステップ８０３で行インデックスｍのＬＬＲ更新処理フラグが真かどうかを判定し、ＬＬＲ更新処理フラグが真でない場合、ＬＬＲ更新処理をスキップし、ステップ８０７へ進む。ＬＬＲ更新処理フラグが真の場合には、ステップ８０４にて行インデックスｍについてＬＬＲ更新処理を実行し、続くステップ８０５でシンドローム値（信頼度係数）の絶対値が予め定めた閾値より大きくかつ、シンドローム値（信頼度係数）の符号が０かどうかを判定する。
【０１１４】
ステップ８０５の判定がＮＯの場合にはステップ８０７へ進む。一方、ステップ８０５の判定がＹＥＳの場合にはステップ８０６へ進み、行インデックスｍのＬＬＲ更新処理フラグを偽に設定する。
【０１１５】
ステップ８０７では、行インデックスｍが最終行インデックスＭであるかどうかを判定し、ＮＯの場合にはステップ８０８において行インデックスｍをインクリメントし、ステップ８０３へ戻る。
【０１１６】
ステップ８０７の判定がＹＥＳの場合にはステップ８０９に進み、シンドローム累積値の判定を行う。シンドローム累積値が真の場合には、硬判定を行った後、復号処理を終了し、偽の場合にはステップ８１０へ進む。
【０１１７】
ステップ８１０では繰り返し回数ｉが最大繰り返し数Ｉｍａｘに達したかどうかを判定する。Ｉｍａｘに達した場合には、たとえば硬判定を行った後、復号処理を終了し、達していない場合にはステップ８１１において繰り返し回数ｉをインクリメントした後、ステップ８０２へ戻る。
【０１１８】
以上のように本実施形態によれば、mｉn-sum復号のＬＬＲ更新処理で得られるシンドローム値（信頼度係数）が閾値を満たすときはＬＬＲ更新処理フラグを偽に設定し、ＬＬＲ更新処理フラグが真の行のみＬＬＲ更新処理を実行するよう制御する。これにより、必要最低限のＬＬＲ更新処理のみの実行が可能となるため、復号全体の演算量を削減することができ、復号スループットを向上することができる。
【０１１９】
本発明はＬＤＰＣ符号を用いるシステムであれば、いかなるシステムに対しても応用可能である。例えば通信システム、放送システムをはじめ、磁気記録システム、光ディスクシステム、更には半導体メモリ等、様々なストレージシステムでも用いることが可能である。
【０１２０】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１２１】
【図１】本発明の第１の実施形態に係る復号装置の構成を示すブロック図。
【図２】図１の復号装置におけるスケジューラのブロック図。
【図３】本発明の第１の実施形態に係る復号方法を説明するフローチャート。
【図４】本発明の第１の実施形態と従来方式との行処理の演算量比を示すグラフ。
【図５】本発明の第１の実施形態と従来方式のビット誤り率特性を表すグラフ。
【図６】本発明の第２の実施形態に係る復号装置の構成を示すブロック図。
【図７】図６のスケジューラのブロック図。
【図８】本発明の第２の実施形態に係る復号方法を説明するフローチャート。
【図９】受信語データの一例とおよびパリティ検査行列の一例を示す図。
【図１０】行処理および列処理を説明する図。
【符号の説明】
【０１２２】
１０１：入力メモリ（受信手段）
１０２：スケジューラ（繰り返し制御手段、終了手段、フラグ記憶手段、フラグ初期化手段）
１０３：行処理部（行処理演算手段、信頼度係数計算手段）
１０４：中間メモリ（行処理演算データ記憶手段、列処理演算データ記憶手段）
１０５：列処理部（列処理演算手段、データ補正手段）
１０６：硬判定部
１０７：パリティ検査部
１０８：出力バッファ
２０１：行処理判定部
２０２：行処理制御部。
２０１Ａ：シンドロームチェック部
２０１Ｂ：シンドローム値判定部
２０１Ｃ：行処理判定メモリ
６０１：ＬＬＲメモリ（受信手段、データ記憶手段）６０１
６０２：ＬＬＲ更新処理部（列処理演算手段、行処理演算手段、信頼度係数計算手段、データ更新手段、列処理演算データ記憶手段）
６０３：中間メモリ（行処理演算データ記憶手段）
６０４：スケジューラ（繰り返し制御手段、フラグ記憶手段、フラグ初期化手段）
６０５：硬判定部
７０１：ＬＬＲ更新処理判定部
７０２：ＬＬＲ更新処理制御部
７０３：シンドローム累積部
７０４：繰り返し回数カウント部
７０５：復号完了判定部（終了手段）
７０１Ａ：シンドロームチェック部
７０１Ｂ：シンドローム値判定部
７０１Ｃ：ＬＬＲ更新処理判定メモリ
【図１】
2009100222.tif 000056
【図２】
2009100222.tif 000057
【図３】
2009100222.tif 000058
【図４】
2009100222.tif 000059
【図５】
2009100222.tif 000060
【図６】
2009100222.tif 000061
【図７】
2009100222.tif 000062
【図８】
2009100222.tif 000063
【図９】
2009100222.tif 000064
【図１０】
2009100222.tif 000065