(57)【特許請求の範囲】
【請求項１】
LDPC符号のビットノード演算を複数の処理に分割して行うビットノード演算部と、
前記ビットノード演算部により分割して処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求め、復号を行うことを繰り返すビット判定部と、
前記LDPC符号のパリティチェック方程式を満たすか否かの判定を前記ビット判定部により求められた前記ビット判定値に基づいて行い、前記パリティチェック方程式を満たす場合に前記ビットノード演算と前記復号を終了させる判定部と
を備える復号装置。
【請求項２】
前記判定部による直前の前記判定時に求められたシンドロームを保存するシンドローム保存部と、
前回の前記復号時に前記ビット判定部により求められた前記ビット判定値を保存するビット判定値保存部と
をさらに備え、
前記判定部は、今回の前記復号時に前記ビット判定部により求められた前記ビット判定値と、前記ビット判定値保存部に保存されている前記ビット判定値との差分に基づいて、前記シンドローム保存部に保存されている前記シンドロームを更新し、更新した前記シンドロームに基づいて、前記判定を行う
請求項１に記載の復号装置。
【請求項３】
LDPC符号のビットノード演算を複数の処理に分割して行い、
分割した処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求めて復号を行うことを繰り返し、
前記LDPC符号のパリティチェック方程式を満たすか否かの判定を前記ビット判定値に基づいて行い、
前記パリティチェック方程式を満たす場合に前記ビットノード演算と前記復号を終了させる
ステップを含む復号方法。
【請求項４】
LDPC符号のビットノード演算を複数の処理に分割して行い、
分割した処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求めて復号を行うことを繰り返し、
前記LDPC符号のパリティチェック方程式を満たすか否かの判定を前記ビット判定値に基づいて行い、
前記パリティチェック方程式を満たす場合に前記ビットノード演算と前記復号を終了させる
ステップを含む処理をコンピュータに実行させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本技術は、復号装置、復号方法、およびプログラムに関し、特に、繰り返し復号の演算量を減らすことができるようにした復号装置、復号方法、およびプログラムに関する。
【背景技術】
【０００２】
［LDPC符号について］
近年、誤り訂正符号としてLDPC(Low-Density Parity-Check)符号が注目されている（非特許文献１）。LDPC符号は、それを定義するパリティチェック行列が疎なものであることを特徴とする。疎な行列とは、行列の要素の"1"の個数が非常に少なく構成される行列をいう。
【０００３】
図１は、(12,6)LDPC符号のパリティチェック行列の例を示す図である。
【０００４】
図１のパリティチェック行列Hは、各列の重み（"1"の数）が"3"、各行の重みが"6"の行列である。LDPC符号による符号化は、パリティチェック行列Hに基づいて生成行列Gを生成し、生成行列Gを２元の情報に乗算して符号語を生成することで実現される。
【０００５】
具体的には、LDPC符号による符号化を行う符号化装置は、パリティチェック行列Hの転置行列HTとの間にGHT=0が成立する生成行列Gを算出する。ここで、生成行列Gがk×n行列である場合には、符号化装置は、生成行列Gに対してkビットからなる情報を乗算し、nビットからなる符号語を生成する。符号化装置によって生成された符号語は、値が"0"の符号ビットが"+1"に、値が"1"の符号ビットが"−1"にマッピングされて送信され、所定の通信路を介して受信側において受信される。
【０００６】
一方、LDPC符号の復号方法としては、パリティチェック行列を２部グラフで表現し、チェックノードとビットノードの間で尤度情報を交換しながら繰り返し処理を行う方法が知られている。
【０００７】
図２は、図１のパリティチェック行列Hの２部グラフを示す図である。
【０００８】
図２の上段に示す白抜きの四角がチェックノードを表し、下段に示す白抜きの丸がビットノードを表す。チェックノードはパリティチェック行列の行に対応し、ビットノードはパリティチェック行列の列に対応する。パリティチェック行列Hの0以外の要素をノード間の接続に対応させた場合、図２に示すように各チェックノードとビットノードがエッジで接続される。
【０００９】
[従来のBP復号]
ここで、LDPC符号の復号方法の一つであるBP(Belief Propagation)復号について説明する。
【００１０】
符号ビット長をN、パリティチェック行数Mのパリティチェック行列をH=[Hmn]とする。mは行番号（チェックノード番号）を表し、0≦m＜Mの値をとる。nは列番号（ビットノード番号）を表し、0≦n＜Nの値をとる。また、m番目のパリティチェック演算に用いられるビット番号の集合をN(m)={n | Hmn=1}とし、n番目のビットを用いてパリティチェック演算を行うパリティチェック番号の集合をM(n)={m | Hmn=1}とする。N(m)={n | Hmn=1}は、m番目のチェックノード（チェックノードm）に繋がるビットノードの集合を表し、M(n)={m | Hmn=1}は、n番目のビットノード（ビットノードn）に繋がるチェックノードの集合を表す。
【００１１】
n番目のビットの受信値から求まる初期の尤度をFn、i回目の復号処理におけるチェックノードmからビットノードnへの尤度をεmn(i)、i回目の復号処理におけるビットノードnからチェックノードmへの尤度をzmn(i)とする。また、i回目の復号処理によって得られたビットnの事後尤度をzn(i)とする。繰り返し復号は、復号処理があらかじめ定められた最大回数だけ繰り返し行われることによって実現される。この場合、BP復号は次のように表される。
【００１２】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各zmn(0)にFnを設定する。
【００１３】
ステップ１：
(i)チェックノード演算
LDPC復号回路は、全てのnと、m∈M(n)を満たす全てのmについて、次式（１）、（２）によりεmn(i)を求める。式（１）のn’は、N(m)に含まれるビットノードのうちの、nを除くビットノードを表す。
【数１】
0005790029.tif 000002
【数２】
0005790029.tif 000003
【００１４】
(ii)ビットノード演算
LDPC復号回路は、全てのmと、n∈N(m)を満たす全てのnについて、次式（３）によりzmn(i)を求め、式（４）によりzn(i)を求める。式（３）のm’は、M(n)に含まれるチェックノードのうちの、mを除くチェックノードを表す。
【数３】
0005790029.tif 000004
【数４】
0005790029.tif 000005
【００１５】
ステップ２：
(i)硬判定
LDPC復号回路は、zn(i)＞0である場合にはwn(i)=1、zn(i)＜0である場合にはwn(i)=0として硬判定を行う。またLDPC復号回路は、硬判定の結果に基づいて、硬判定値（ビット判定値）を要素とするベクトルである判定値ベクトルw(i)=[wn(i)]を求める。
【００１６】
(ii)復号終了条件判定
LDPC復号回路は、パリティチェック方程式Hw(i)の演算であるパリティチェック演算を行う。LDPC復号回路は、パリティチェック方程式Hw(i)=0を満たす、すなわち0≦m＜Mについて次式（５）を満たす場合、または、復号処理の繰り返し回数iがあらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、それ以外の場合、LDPC復号回路はiを1増やしてステップ１の処理を行う。
【数５】
0005790029.tif 000006
【００１７】
ステップ３：
LDPC復号回路は、復号結果としてw(i)を出力する。
【００１８】
BP復号は、以上のように１回の復号処理においてチェックノード演算が全て終了した後にビットノード演算を全て行うものである。すなわち、ステップ１の(i)のチェックノード演算においてεmn(i)を求め、その結果を用いて、(ii)のビットノード演算においてzmn(i),zn(i)を求めるようになされている。
【００１９】
[従来のgroup shuffled BP復号]
ところで、LDPC符号の繰り返し復号において、復号が収束するまでの回数を少なくするための方法が提案されている（非特許文献２，３）。
【００２０】
非特許文献２には、ビットノード演算を分割して行うgroup shuffled BP復号が記載されている。また、特許文献１には、group shuffled BP復号回路を複数用いてレプリカ結合する復号回路が記載されている。特許文献２には、shuffled BP復号回路において尤度の更新スケジュールを変更することによって、効率よく復号できる復号装置ならびに方法が記載されている。
【００２１】
次に、group shuffled BP復号について説明する。group shuffled BP復号は次のように表される。ビットノードを分割するグループ数をG、各グループで処理するビットノードの数をNg=N/Gとする。
【００２２】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各zmn(0)にFnを設定する。
【００２３】
ステップ１：
LDPC復号回路は、処理対象とするビットノードのグループを表す変数gを0からG-1まで変えながら、(i)のチェックノード演算と(ii)のビットノード演算を繰り返す。すなわち、LDPC復号回路は、G個のチェックノードのグループのうちの１つ目のグループを対象としてチェックノード演算とビットノード演算を行う。次に、LDPC復号回路は、２つ目のグループを対象としてチェックノード演算とビットノード演算を行い、以降、３つ目以降のグループを順次対象として、チェックノード演算とビットノード演算を行う。
【００２４】
（i）チェックノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（６）、（７）によりεmn(i)を求める。
【数６】
0005790029.tif 000007
【数７】
0005790029.tif 000008
【００２５】
（ii）ビットノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（８）によりzmn(i)を求め、式（９）によりzn(i)を求める。
【数８】
0005790029.tif 000009
【数９】
0005790029.tif 000010
【００２６】
ステップ２：
（i）硬判定
LDPC復号回路は、zn(i)＞0である場合にはwn(i)=1、zn(i)＜0である場合にはwn(i)=0として硬判定を行う。またLDPC復号回路は、硬判定の結果に基づいて、判定値ベクトルw(i)=[wn(i)]を求める。
【００２７】
（ii）復号終了条件判定
LDPC復号回路は、パリティチェック方程式Hw(i)=0を満たす、すなわち0≦m＜Mについて次式（１０）を満たす場合、または、復号処理の繰り返し回数があらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、それ以外の場合、LDPC復号回路はiを1増やしてステップ１の処理を行う。
【数１０】
0005790029.tif 000011
【００２８】
ステップ３：
LDPC復号回路は、復号結果としてw(i)を出力する。
【００２９】
図３は、以上のようなgroup shuffled BP復号を行うLDPC復号回路の構成を示すブロック図である。
【００３０】
図３のLDPC復号回路１は、チェックノード演算回路１１、ビットノード演算回路１２、硬判定回路１３、パリティチェック回路１４、および出力回路１５から構成される。チェックノード演算回路１１とビットノード演算回路１２に対しては、n番目のビットの受信値から求まる初期の尤度であるFnが入力される。
【００３１】
チェックノード演算回路１１は、ステップ１（i）の処理として説明したように、ビットノードの所定のグループを対象としてチェックノード演算を行い、εmn(i)を求める。チェックノード演算回路１１はεmn(i)をビットノード演算回路１２に出力する。
【００３２】
ビットノード演算回路１２は、ステップ１（ii）の処理として説明したようにビットノード演算を行い、zmn(i)とzn(i)を求める。ビットノード演算回路１２は、zn(i)を硬判定回路１３に出力し、zmn(i)と、前回（i-1回目）の復号処理により求められたzmn(i-1)をチェックノード演算回路１１に出力する。
【００３３】
硬判定回路１３は、ステップ２（i）の処理として説明したように硬判定を行う。硬判定回路１３は、判定値ベクトルwn(i)をパリティチェック回路１４と出力回路１５に出力する。
【００３４】
パリティチェック回路１４は、ステップ２（ii）の処理として説明したように復号終了条件判定を行う。パリティチェック回路１４は、符号ビット長に等しいNのビットノードについてのビットノード演算が終了する毎に、復号終了条件判定を１度行う。パリティチェック方程式Hw(i)=0を満たさない場合であって、復号処理の繰り返し回数があらかじめ定められた最大回数に到達していないとき、復号終了条件を満たさないと判定される。また、パリティチェック方程式Hw(i)=0を満たす場合、または、復号処理の繰り返し回数があらかじめ定められた最大回数に到達している場合、復号終了条件を満たすと判定される。
【００３５】
パリティチェック回路１４は、復号終了条件を満たさないと判定した場合、iを1増やして復号処理を繰り返すことを指示する制御信号をチェックノード演算回路１１とビットノード演算回路１２に出力する。一方、パリティチェック回路１４は、復号終了条件を満たすと判定した場合、そのことを表す信号を出力回路１５に出力する。
【００３６】
出力回路１５は、復号終了条件を満たすことを表す信号がパリティチェック回路１４から供給された場合、判定値ベクトルwn(i)を復号結果として出力する。
【００３７】
[従来のlayered BP復号]
非特許文献３には、ターボ復号、あるいはlayered BP復号として知られる、チェックノード演算を複数の処理に分割して行う復号方法が記載されている。次に、Layered BP復号について説明する。Layered BP復号は次のように表される。
【００３８】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各εmn(0)に0を設定する。
【００３９】
ステップ１：
LDPC復号回路は、処理対象とするチェックノードを表す変数mを0からM-1まで変えながら、(i)のビットノード演算と(ii)のチェックノード演算を繰り返す。
【００４０】
（i）ビットノード演算
LDPC復号回路は、n∈N(m)を満たすnについて、次式（１１）によりzmn(i-1)を求める。
【数１１】
0005790029.tif 000012
【００４１】
（ii）チェックノード演算
LDPC復号回路は、n∈N(m)を満たすnについて、次式（１２）、（１３）によりεmn(i)を求める。
【数１２】
0005790029.tif 000013
【数１３】
0005790029.tif 000014
【００４２】
ステップ２：
（i）硬判定
LDPC復号回路は、全てのnについて、次式（１４）によりzn(i)を求める。
【数１４】
0005790029.tif 000015
【００４３】
また、LDPC復号回路は、zn(i)＞0である場合にはwn(i)=1、zn(i)＜0である場合にはwn(i)=0として硬判定を行う。またLDPC復号回路は、硬判定の結果に基づいて、判定値ベクトルw(i)=[wn(i)]を求める。
【００４４】
（ii）復号終了条件判定
LDPC復号回路は、パリティチェック方程式Hw(i)=0を満たす、すなわち0≦m＜Mについて次式（１５）を満たす場合、または、復号処理の繰り返し回数があらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、それ以外の場合、LDPC復号回路は、iを1増やしてステップ１の処理を行う。
【数１５】
0005790029.tif 000016
【００４５】
ステップ３：
LDPC復号回路は、復号結果としてw(i)を出力する。
【００４６】
非特許文献４には、受信語を硬判定したものが符号語の条件を満たすかどうかを復号処理の繰り返し前に判定し、符号語の条件を満たす場合には復号処理を繰り返さないようにする技術が記載されている。
【先行技術文献】
【特許文献】
【００４７】
【特許文献１】特表２００８−５２７７６０号公報
【特許文献２】特開２００８−１６９５９号公報
【非特許文献】
【００４８】
【非特許文献１】R. G. Gallager, "Low-density parity-check codes," IRE Trans. Inform. Theory, vol. IT-8, pp. 21-28, Jan. 1962.
【非特許文献２】J. Zhang and M. Fossorier, “Shuffled belief propagation decoding,”  Proc. 36th Annu. Asilomar Conf. Signals, Syst., Computers, pp. 8-15, Nov. 2002.
【非特許文献３】M. M. Mansour and N. R. Shanbhag, “Turbo decoder architecture for low-density parity-check codes,”  Proc. Global Telecommun. Conf., pp. 1383-1388, Nov. 2002.
【非特許文献４】Timo Lehnigk-Emden, Norbert When and Friedbert Berens, “Enhanced iteration control for ultra low power LDPC decoding,”  proceedings of ICT-MobileSummit 2008.
【発明の概要】
【発明が解決しようとする課題】
【００４９】
一般に、装置は低消費電力である方が望ましく、LDPC復号機能を搭載する装置についても同様である。LDPC復号はその演算量に応じた電力を消費する復号方法であるため、低消費電力を実現するためには、より少ない演算量となる復号方法の実現が求められる。
【００５０】
本技術はこのような状況に鑑みてなされたものであり、繰り返し復号の演算量を減らすことができるようにするものである。
【課題を解決するための手段】
【００５１】
本技術の一側面の復号装置は、LDPC符号のビットノード演算を複数の処理に分割して行うビットノード演算部と、前記ビットノード演算部により分割して処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求め、復号を行うことを繰り返すビット判定部と、前記LDPC符号のパリティチェック方程式を満たすか否かの判定を前記ビット判定部により求められた前記ビット判定値に基づいて行い、前記パリティチェック方程式を満たす場合に前記ビットノード演算と前記復号を終了させる判定部とを備える。
【００５５】
前記判定部による直前の前記判定時に求められたシンドロームを保存するシンドローム保存部と、前回の前記復号時に前記ビット判定部により求められた前記ビット判定値を保存するビット判定値保存部とをさらに設けることができる。この場合、前記判定部には、今回の前記復号時に前記ビット判定部により求められた前記ビット判定値と、前記ビット判定値保存部に保存されている前記ビット判定値との差分に基づいて、前記シンドローム保存部に保存されている前記シンドロームを更新させ、更新させた前記シンドロームに基づいて、前記判定を行わせることができる。
【００５８】
本技術の一側面においては、LDPC符号のビットノード演算が複数の処理に分割して行われ、分割した処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求めて復号を行うことが繰り返され、前記LDPC符号のパリティチェック方程式を満たすか否かの判定が前記ビット判定値に基づいて行われ、前記パリティチェック方程式を満たす場合に前記ビットノード演算と前記復号が終了する。
【発明の効果】
【００５９】
本技術によれば、繰り返し復号の演算量を減らすことができる。
【図面の簡単な説明】
【００６０】
【図１】パリティチェック行列の例を示す図である。
【図２】図１のパリティチェック行列の２部グラフを示す図である。
【図３】LDPC復号回路の構成を示すブロック図である。
【図４】本技術を適用したgroup shuffled BP復号の流れを示すフローチャートである。
【図５】図４の処理を行う復号回路の構成例を示すブロック図である。
【図６】シミュレーション結果を示す図である。
【図７】本技術を適用した他のgroup shuffled BP復号の流れを示すフローチャートである。
【図８】パリティチェック回路の構成例を示すブロック図である。
【図９】本技術を適用したlayered BP復号の流れを示すフローチャートである。
【図１０】コンピュータの構成例を示すブロック図である。
【発明を実施するための形態】
【００６１】
以下、発明を実施するための形態について説明する。説明は以下の順序で行う。
１．第１の実施の形態（group shuffled BP復号の変形）
２．第２の実施の形態（layered BP復号の変形）
【００６２】
＜第１の実施の形態＞
[group shuffled BP復号の変形]
従来のgroup shuffled BP復号では、チェックノード演算とビットノード演算からなる１回のステップ１の復号演算全体が終わる毎に、硬判定と復号終了条件判定が行われる。これに対して、本技術を適用したgroup shuffled BP復号においては、１回の復号演算を分割し、その分割した復号演算の間に、硬判定と復号終了条件判定が行われる。
【００６３】
分割した復号演算の間に復号終了条件を満たすと判定した場合には復号演算全体を終えることなく途中で処理を終了させることによって、同じ復号性能を維持しながら演算量を削減することが可能になる。
【００６４】
本技術を適用したgroup shuffled BP復号は次のように表される。
【００６５】
なお、ここでも、符号ビット長をN、パリティチェック行数Mのパリティチェック行列をH=[Hmn]とする。mは行番号（チェックノード番号）を表し、0≦m＜Mの値をとる。nは列番号（ビットノード番号）を表し、0≦n＜Nの値をとる。また、m番目のパリティチェック演算に用いられるビット番号の集合をN(m)={n | Hmn=1}とし、n番目のビットを用いてパリティチェック演算を行うパリティチェック番号の集合をM(n)={m | Hmn=1}とする。
【００６６】
また、n番目のビットの受信値から求まる初期の尤度をFn、i回目の復号処理におけるチェックノードmからビットノードnへの尤度をεmn(i)、i回目の復号処理におけるビットノードnからチェックノードmへの尤度をzmn(i)とする。i回目の復号処理によって得られたビットnの事後尤度をzn(i)とする。ビットノードを分割するグループ数をG、各グループで処理するビットノードの数をNg=N/Gとする。
【００６７】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各zmn(0)にFnを設定する。
LDPC復号回路は、Fn＞0である場合にはwn(0)=1、Fn＜0である場合にはwn(0)=0として硬判定を行う。またLDPC復号回路は、硬判定の結果に基づいて、判定値ベクトルw=[wn(0)]を求める。
【００６８】
ステップ１：
LDPC復号回路は、処理対象とするビットノードのグループを表す変数gを0からG-1まで変えながら、(i)のチェックノード演算、(ii)のビットノード演算、(iii)の硬判定、および（iv）の復号終了条件判定を繰り返す。
【００６９】
すなわち、LDPC復号回路は、G個のチェックノードのグループのうちの１つ目のグループを対象としてチェックノード演算とビットノード演算を行った後、１つ目のグループを対象とした復号演算の結果に基づいて硬判定と復号終了条件判定を行う。LDPC復号回路は、復号終了条件を満たすと判定した場合、処理を終了させる。一方、復号終了条件を満たさないと判定した場合、LDPC復号回路は、２つ目以降のグループを順次対象として同様の処理を行う。
【００７０】
（i）チェックノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（１６）、（１７）によりεmn(i)を求める。
【数１６】
0005790029.tif 000017
【数１７】
0005790029.tif 000018
【００７１】
（ii）ビットノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（１８）によりzmn(i)を求め、式（１９）によりzn(i)を求める。
【数１８】
0005790029.tif 000019
【数１９】
0005790029.tif 000020
【００７２】
（iii）硬判定
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnについて、zn(i)＞0である場合にはwn(i)=1、zn(i)＜0である場合にはwn(i)=0として硬判定を行う。硬判定により、部分的な硬判定値が求められることになる。またLDPC復号回路は、硬判定の結果に基づいて、判定値ベクトルwのn番目の要素をwn(i-1)からwn(i)に更新する。
【００７３】
（iv）復号終了条件判定
LDPC復号回路は、パリティチェック方程式Hwの演算であるパリティチェック演算を行う。LDPC復号回路は、パリティチェック方程式Hw=0を満たす、すなわち0≦m＜Mについて次式（２０）を満たす場合、ステップ３の処理を行う。式（２０）による計算は、i-1回目の復号処理の結果が用いられている点で式（１０）の計算と異なる。
【数２０】
0005790029.tif 000021
【００７４】
0≦m＜Mについて式（２０）を満たさない場合であって、いまの変数gがG-1でないとき、LDPC復号回路はgを1増やしてステップ１の処理を継続する。また、0≦m＜Mについて式（２０）を満たさない場合であって、いまの変数gがG-1であるとき、LDPC復号回路はステップ２の処理を行う。
【００７５】
ステップ２：
LDPC復号回路は、復号処理の繰り返し回数があらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、復号処理の繰り返し回数があらかじめ定められた最大回数に到達していない場合、LDPC復号回路はiを1増やしてステップ１の処理を行う。
【００７６】
ステップ３：
LDPC復号回路は、復号結果として判定値ベクトルwを出力する。
【００７７】
以上の一連の流れを図４のフローチャートに示す。図４において破線Ｌ１で囲んで示す処理がステップ１の処理に対応し、一点鎖線Ｌ２で囲んで示す処理がステップ２の処理に対応する。図４のステップＳ１は初期化に対応し、ステップＳ９はステップ３の処理に対応する。適宜、各ステップの処理と、各ステップの処理を実行する構成との対応について図５（後述）の構成を用いて説明する。
【００７８】
すなわち、LDPC復号回路は、ステップＳ１において初期化を行い、ステップＳ２において変数gに0を設定する。初期化としてiに1を設定する処理と、ステップＳ２の変数gに0を設定する処理は図５のLDPC復号回路１の各回路により行われ、各zmn(0)にFnを設定する処理は、チェックノード演算回路１１とビットノード演算回路１２により行われる。また、初期化として判定値ベクトルw=[wn(0)]を求める処理は硬判定回路１３により行われる。
【００７９】
また、LDPC復号回路は、ステップＳ３においてチェックノード演算を行い、ステップＳ４においてビットノード演算を行う。ステップＳ３のチェックノード演算はチェックノード演算回路１１により行われ、ステップＳ４のビットノード演算はビットノード演算回路１２により行われる。
【００８０】
LDPC復号回路は、ステップＳ５において硬判定を行い、ステップＳ６において、硬判定の結果に基づいて判定値ベクトルwを更新する。ステップＳ５の硬判定とステップＳ６の判定値ベクトルwの更新処理は硬判定回路１３により行われる。
【００８１】
LDPC復号回路は、ステップＳ７においてパリティチェック演算を行い、ステップＳ８において、パリティチェック方程式Hw=0を満たすか否かを判定する。ステップＳ７のパリティチェック演算と、ステップＳ８の判定はパリティチェック回路１４により行われる。LDPC復号回路は、パリティチェック方程式Hw=0を満たすとステップＳ８において判定した場合、ステップＳ９において判定値ベクトルwを出力し、処理を終了させる。判定値ベクトルwを出力する処理は出力回路１５により行われる。
【００８２】
一方、パリティチェック方程式Hw=0を満たさないとステップＳ８において判定した場合、LDPC復号回路は、ステップＳ１０において、変数gがG-1であるか否かを判定する。変数gがG-1ではないとステップＳ１０において判定した場合、ステップＳ１１において、変数gの値を1増やし、ステップＳ３以降の処理を繰り返す。ステップＳ１０の判定はパリティチェック回路１４により行われ、ステップＳ１１の処理はLDPC復号回路１の各回路により行われる。
【００８３】
一方、変数gがG-1であるとステップＳ１０において判定した場合、LDPC復号回路は、ステップＳ１２において、iが最大回数に到達したか否かを判定する。iが最大回数に到達していないとステップＳ１２において判定した場合、LDPC復号回路は、ステップＳ１３において、変数iの値を1増やし、ステップＳ２以降の処理を繰り返す。ステップＳ１２の判定はパリティチェック回路１４により行われ、ステップＳ１３の処理はLDPC復号回路１の各回路により行われる。
【００８４】
iが最大回数に到達したとステップＳ１２において判定した場合、LDPC復号回路は、ステップＳ９において判定値ベクトルwを出力し、処理を終了させる。
【００８５】
従来のgroup shuffled BP復号では、１回の復号処理の途中でパリティチェック方程式Hw=0を満たす復号結果が得られたとしてもビットノードの全てのグループを対象とした復号演算が終了した後に復号終了条件判定が行われる。従って、１回の復号処理内でG回の復号演算が必ず行われる。一方、本技術を適用したgroup shuffled BP復号によれば、１回の復号処理の間に復号終了条件判定が行われるため、g＜G-1回目の復号演算でパリティチェック方程式Hw=0を満たす復号結果が得られた場合には残りの処理が行われない。これにより、演算量を削減することができ、演算量を削減することができることによって、装置の消費電力を抑えることが可能になる。
【００８６】
［回路構成］
図５は、本技術の一実施形態に係る復号装置２１に設けられるLDPC復号回路１の構成例を示すブロック図である。図５に示す構成のうち、図３の構成と同じ構成には同じ符号を付してある。
【００８７】
図５のLDPC復号回路１は、チェックノード演算回路１１、ビットノード演算回路１２、硬判定回路１３、パリティチェック回路１４、出力回路１５、および選択回路３１から構成される。チェックノード演算回路１１、ビットノード演算回路１２、および選択回路３１に対しては、n番目のビットの受信値から求まる初期の尤度であるFnが入力される。
【００８８】
チェックノード演算回路１１は、変数gを0に設定し、ステップ１（i）の処理として説明したようにチェックノード演算を行い、εmn(i)を求める。チェックノード演算回路１１はεmn(i)をビットノード演算回路１２に出力する。チェックノード演算回路１１は、適宜、出力回路１５からの制御信号に従って変数gを1増やし、チェックノードのグループを切り替えてチェックノード演算を繰り返す。
【００８９】
ビットノード演算回路１２は、ステップ１（ii）の処理として説明したように、チェックノード演算回路１１により求められたεmn(i)を用いてzmn(i)とzn(i)を求める。ビットノード演算回路１２は、zn(i)を選択回路３１に出力し、zmn(i)と、直前の繰り返し復号により求められたzmn(i-1)をチェックノード演算回路１１に出力する。
【００９０】
選択回路３１は、初期化時、Fnを選択して硬判定回路１３に出力する。また、選択回路３１は、ビットノード演算回路１２により求められたzn(i)が供給された場合、zn(i)を選択し、硬判定回路１３に出力する。
【００９１】
硬判定回路１３は、初期化時、選択回路３１により選択されたFnに基づいて、Fn＞0である場合にはwn(0)=1、Fn＜0である場合にはwn(0)=0として硬判定を行い、判定値ベクトルw=[wn(0)]を求める。硬判定回路１３は、判定値ベクトルwをパリティチェック回路１４と出力回路１５に出力する。
【００９２】
また、硬判定回路１３は、ビットノード演算回路１２により求められたzn(i)が選択回路３１から供給された場合、ステップ１（iii）の処理として説明したように硬判定を行う。また、硬判定回路１３は、硬判定の結果に基づいて判定値ベクトルwを更新し、更新後の判定値ベクトルwをパリティチェック回路１４と出力回路１５に出力する。
【００９３】
パリティチェック回路１４は、ステップ１（iv）の処理として説明したように復号終了条件判定を行う。すなわち、パリティチェック回路１４は、ビットノードの１つのグループ（Ng）を対象としたビットノード演算が終了する毎に、新たに得られた硬判定値を元に、復号終了条件判定を行う。
【００９４】
パリティチェック回路１４は、復号終了条件を満たすと判定した場合、そのことを表す信号を出力回路１５に出力する。一方、パリティチェック回路１４は、復号終了条件を満たさないと判定した場合、変数gがG-1でないときには、変数gを1増やして演算を繰り返すことを指示する制御信号を出力する。また、パリティチェック回路１４は、復号終了条件を満たさないと判定した場合、変数gがG-1であり、iが最大回数に到達していないときには、iを1増やして演算を繰り返すことを指示する制御信号を出力する。パリティチェック回路１４から出力された制御信号はチェックノード演算回路１１とビットノード演算回路１２に供給される。
【００９５】
出力回路１５は、復号終了条件を満たすことを表す信号がパリティチェック回路１４から供給された場合、判定値ベクトルwを復号結果として出力する。
【００９６】
［シミュレーション結果］
図６は、従来のBP復号、従来のgroup shuffled BP復号、および本技術を適用したgroup shuffled BP復号のそれぞれの方法を用いてLDPC復号を行った場合の演算量のシミュレーション結果を表す図である。
【００９７】
シミュレーションモデルは、符号ビット長が1440、情報ビット長が1344のLDPC符号をBPSK変調によって変調して送信し、送信信号が白色雑音通信路を経た後に、復号処理の最大の繰り返し回数を16として繰り返し復号を行うものである。グラフの横軸は、ビットあたりのエネルギー(Eb)対雑音電力密度(N0)の比(Eb/N0)を表し、縦軸は、平均のビットノード演算数を符号ビット長で割った値(Nb)を表す。
【００９８】
図６に示すように、いずれの復号方法においても、Eb/N0の値が大きくなるに従って、Nbの値は小さくなっている。従来のBP復号と従来のgroup shuffled BP復号の場合、１回の復号処理において符号ビット長と同じ1440のビットノード演算が行われる。そのため、ビットノード演算数を符号ビット長で割って得られる値は、処理終了までの復号処理の繰り返し回数と等しい、1以上、16以下の整数の値となる。図６より、グラフで示された全てのEb/N0において、従来のBP復号より従来のgroup shuffled BP復号の方が少ない繰り返し回数で処理が完了していることが読み取れる。
【００９９】
１回の復号処理が途中で終了することがあるため、本技術を適用したgroup shuffled BP復号を用いた場合のビットノード演算数は、従来のgroup shuffled BP復号を用いた場合のビットノード演算数と等しいか、それより小さくなる。従来のgroup shuffled BP復号を用いた場合のビットノード演算数は、繰り返し回数と符号ビット長を乗算して得られた値によって表される。
【０１００】
図６より、グラフで示された全てのEb/N0において、本技術を適用したgroup shuffled BP復号を用いた場合のNbの値は、従来のgroup shuffled BP復号を用いた場合の値より小さくなっており、演算量が削減されたことが読み取れる。例えば、Eb/N0=6dBの条件では、従来のgroup shuffled BP復号ではNb=1.16であったのに対し、本技術を適用したgroup shuffled BP復号ではNb=0.87となり、演算量が約25%削減されている。
【０１０１】
［パリティチェック演算について］
従来のgroup shuffled BP復号と比べた場合、本技術を適用したgroup shuffled BP復号では復号終了条件判定の回数（パリティチェック演算の回数）が約G倍となる。この場合であっても、全体の演算量が多くならないことについて説明する。
【０１０２】
ここで、ステップ１(iii)で更新される硬判定値wn(i)の数（判定値ベクトルwの要素の数）は、nがgNg≦n＜(g+1)Ngの範囲にある値であり、その数がNg個であることに着目する。
【０１０３】
まず、ステップ１(iii)で硬判定値wn(i)が更新される前のパリティチェック方程式の左辺は、次式（２１）で表される。式（２１）は、式（２０）の変数gにg-1を代入することによって導かれる。硬判定値wn(i)が更新される前のパリティチェック方程式の左辺で表される値をシンドロームSm’とする。
【数２１】
0005790029.tif 000022
【０１０４】
ステップ１(iii)で更新された、更新後の硬判定値wn(i)を用いた新しいシンドロームSmは、シンドロームSm’を用いて次式（２２）のように求めることができる。
【数２２】
0005790029.tif 000023
【０１０５】
従来のgroup shuffled BP復号におけるパリティチェック演算は、硬判定によって新たに得られたN個全ての硬判定値wn(i)を用いて行う必要がある。これに対し、本技術を適用したgroup shuffled BP復号におけるシンドロームSmの演算は、直前に計算されたシンドロームSm’と、前回の復号処理で求められた硬判定値wn(i-1)とを保存しておけば、シンドロームSm’に対して、今回の復号処理で更新されたNg個のビットノードの硬判定値の差分だけを反映させればよいことが分かる。
【０１０６】
シンドロームSmの演算量は、演算に用いる硬判定値wn(i)の数の違いから、従来のgroup shuffled BP復号におけるパリティチェック演算の演算量の約1/Gである。つまり、約G倍に回数が増加したパリティチェック演算の１回あたりの演算量は約1/Gとなる。その結果、従来のgroup shuffled BP復号におけるパリティチェック演算の演算量と、本技術を適用したgroup shuffled BP復号におけるパリティチェック演算の演算量は、ほぼ同等の演算量になる。
【０１０７】
ここで説明したパリティチェック演算を組み込んだ、本技術を適用したgroup shuffled BP復号について説明する。
【０１０８】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各zmn(0)にFnを設定する。
LDPC復号回路は、Fn＞0である場合にはwn(0)=1、Fn＜0である場合にはwn(0)=0として、判定値ベクトルw=[wn(0)]を求める。
LDPC復号回路は、判定値ベクトルw=[wn(0)]を用いて、シンドロームSmを次式（２３）により求める。
【数２３】
0005790029.tif 000024
【０１０９】
また、LDPC復号回路は、全てのm（0≦m＜M）についてSm=0を満たす場合はステップ３の処理を行う。すなわち、Sm=0を満たす場合、復号結果が出力され、処理が終了される。一方、全てのmについてSm=0を満たさない場合、LDPC復号回路は、シンドロームSm’としてSmを代入し、ステップ１の処理を行う。
【０１１０】
ステップ１：
LDPC復号回路は、変数gを0からG-1まで変えながら、(i)のチェックノード演算、(ii)のビットノード演算、(iii)の硬判定、および（iv）の復号終了条件判定を繰り返す。
【０１１１】
（i）チェックノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（２４）、（２５）によりεmn(i)を求める。
【数２４】
0005790029.tif 000025
【数２５】
0005790029.tif 000026
【０１１２】
（ii）ビットノード演算
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnと、m∈M(n)を満たすmについて、次式（２６）によりzmn(i)を求め、式（２７）によりzn(i)を求める。
【数２６】
0005790029.tif 000027
【数２７】
0005790029.tif 000028
【０１１３】
（iii）硬判定
LDPC復号回路は、gNg≦n＜(g+1)Ngを満たすnについて、zn(i)＞0である場合にはwn(i)=1、zn(i)＜0である場合にはwn(i)=0として硬判定を行う。また、LDPC復号回路は、硬判定の結果に基づいて、判定値ベクトルwのn番目の要素をwn(i-1)からwn(i)に更新する。
【０１１４】
（iv）復号終了条件判定
LDPC復号回路は、m∈{∪M(n) | gNg≦n＜(g+1)Ng}を満たすm（gNg≦n＜(g+1)Ngの範囲にあるビットノードnに繋がるチェックノードmの和集合に属するチェックノードm）について、シンドロームSmを次式（２８）により更新する。
【数２８】
0005790029.tif 000029
【０１１５】
LDPC復号回路は、全てのm（0≦m＜M）についてSm=0を満たす場合はステップ３の処理を行う。
【０１１６】
全てのmについてSm=0を満たさない場合であって、いまの変数gがG-1でないとき、LDPC復号回路は、シンドロームSm’に式（２８）により求めたSmを代入し、変数gを1増やしてステップ１の処理を継続する。一方、全てのmについてSm=0を満たさない場合であって、いまの変数gがG-1であるとき、LDPC復号回路はステップ２の処理を行う。
【０１１７】
ステップ２：
LDPC復号回路は、復号処理の繰り返し回数があらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、復号処理の繰り返し回数があらかじめ定められた最大回数に到達していない場合、LDPC復号回路はiを1増やしてステップ１の処理を行う。
【０１１８】
ステップ３：
LDPC復号回路は、復号結果として判定値ベクトルwを出力する。
【０１１９】
以上の処理においては、初期化時に、判定値ベクトルw=[wn(0)]を元にしたシンドロームSm’を求める演算が必要になっている。このとき、Sm’=0を満たせば、その時点で復号結果を出力して処理を終了し、ステップ１、ステップ２の処理を行わないようにすることができる。
【０１２０】
以上の一連の流れを図７のフローチャートに示す。図７において破線Ｌ１１で囲んで示す処理がステップ１の処理に対応し、一点鎖線Ｌ１２で囲んで示す処理がステップ２の処理に対応する。図７のステップＳ２１は初期化に対応し、ステップＳ３１はステップ３の処理に対応する。適宜、各ステップの処理と、各ステップの処理を実行する構成との対応について説明する。
【０１２１】
すなわち、LDPC復号回路は、ステップＳ２１において初期化を行い、ステップＳ２２において変数gに0を設定する。また、LDPC復号回路は、ステップＳ２３においてチェックノード演算を行い、ステップＳ２４においてビットノード演算を行う。LDPC復号回路は、ステップＳ２５において硬判定を行い、ステップＳ２６において硬判定値を保存する。硬判定値を保存する処理は後述する図８の硬判定値保存回路４１により行われる。
【０１２２】
ステップＳ２７において、LDPC復号回路は、硬判定の結果に基づいて判定値ベクトルwを更新する。LDPC復号回路は、ステップＳ２８において、パリティチェック演算として、式（２８）に従ってシンドロームSmの演算を行う。前回の復号処理（i-1回目の復号処理）において求められたシンドロームSmが保存されている場合、式（２８）の演算においては、保存されていたシンドロームSmがシンドロームSm’として用いられる。LDPC復号回路は、ステップＳ２９において、式（２８）の演算により求めたシンドロームSmを保存する。
【０１２３】
ステップＳ３０において、LDPC復号回路はSm=0を満たすか否かを判定する。LDPC復号回路は、Sm=0を満たすとステップＳ３０において判定した場合、ステップＳ３１において判定値ベクトルwを出力し、処理を終了させる。
【０１２４】
一方、Sm=0を満たさないとステップＳ３０において判定した場合、LDPC復号回路は、ステップＳ３２において、変数gがG-1であるか否かを判定する。変数gがG-1ではないとステップＳ３２において判定した場合、ステップＳ３３において、変数gの値を1増やし、ステップＳ２３以降の処理を繰り返す。
【０１２５】
一方、変数gがG-1であるとステップＳ３２において判定した場合、LDPC復号回路は、ステップＳ３４において、iが最大回数に到達したか否かを判定する。iが最大回数に到達していないとステップＳ３４において判定した場合、LDPC復号回路は、ステップＳ３５において、変数iの値を1増やし、ステップＳ２２以降の処理を繰り返す。
【０１２６】
iが最大回数に到達したとステップＳ３４において判定した場合、LDPC復号回路は、ステップＳ３１において判定値ベクトルwを出力し、処理を終了させる。
【０１２７】
［パリティチェック回路の構成］
図８は、以上のようにして直前に計算されたシンドロームSm’と前回の復号処理で求められた硬判定値wn(i-1)とを保存し、復号終了条件判定を行うパリティチェック回路１４の構成例を示すブロック図である。
【０１２８】
パリティチェック回路１４は、硬判定値保存回路４１、シンドローム計算回路４２、シンドローム保存回路４３、および判定回路４４から構成される。硬判定回路１３から出力された硬判定値wn(i)は硬判定値保存回路４１とシンドローム計算回路４２に入力される。
【０１２９】
硬判定値保存回路４１は、硬判定回路１３により求められた硬判定値wn(i)を保存する。また、硬判定値保存回路４１は、iが1増加したとき、保存していた硬判定値wn(i)をwn(i-1)としてシンドローム計算回路４２に出力する。
【０１３０】
シンドローム計算回路４２は、初期化時、硬判定回路１３により求められた硬判定値wn(0)を用いて、式（２３）に従ってシンドロームSmを求める。また、シンドローム計算回路４２は、iが1以上であるとき、式（２８）に従ってシンドロームSmを求める。シンドロームSmの演算には、シンドローム保存回路４３から出力されたシンドロームSm’と、硬判定回路１３により求められ、新たに更新された硬判定値wn(i)と、硬判定値保存回路４１から出力された硬判定値wn(i-1)とが用いられる。シンドローム計算回路４２は、新たに求めたシンドロームSmをシンドローム保存回路４３と判定回路４４に出力する。
【０１３１】
シンドローム保存回路４３は、シンドローム計算回路４２により求められたシンドロームSmを保存する。シンドローム保存回路４３は、硬判定値wn(i)が新たに求められたとき、保存していたシンドロームSmを、直前のシンドロームSm’としてシンドローム計算回路４２に出力する。
【０１３２】
判定回路４４は、全てのmについてSm=0を満たすか否かを判定し、判定結果に基づいて、復号を終了するか、継続するかの動作を切り替えるための制御信号を出力する。判定回路４４から出力された制御信号は、図５のチェックノード演算回路１１とビットノード演算回路１２に供給される。
【０１３３】
＜第２の実施の形態＞
[layered BP復号の変形]
繰り返し復号の１回の復号処理の間隔よりも短い間隔で復号終了条件判定を行い、復号終了条件を満たす場合には処理を終了させることはlayered BP復号に適用することも可能である。本技術を適用したlayered BP復号は次のように表される。
【０１３４】
初期化：
LDPC復号回路は、iに1を設定する。
LDPC復号回路は、各εmn(0)に0を設定する。
LDPC復号回路は、Fn＞0である場合にはwn=1、Fn＜0である場合にはwn=0として硬判定を行い、判定値ベクトルw=[wn]を求める。
【０１３５】
LDPC復号回路は、パリティチェック方程式Hw=0を満たすか否かを判定し、満たすと判定した場合、ステップ３の処理を行う。一方、パリティチェック方程式Hw=0を満たさないと判定した場合、LDPC復号回路はステップ１の処理を行う。
【０１３６】
ステップ１：
LDPC復号回路は、変数mを0からM-1まで変えながら、(i)のビットノード演算、（ii）のチェックノード演算、（iii）の硬判定、および（iv）の復号終了条件判定を繰り返す。
【０１３７】
すなわち、LDPC復号回路は、パリティチェック行列の１行目を対象としてビットノード演算とチェックノード演算を行った後、１行目を対象とした復号演算の結果に基づいて硬判定と復号終了条件判定を行う。LDPC復号回路は、復号終了条件判定によって復号終了条件を満たすと判定した場合、復号を終了させる。一方、復号終了条件を満たさないと判定した場合、LDPC復号回路は、２行目以降を順次対象として同様の処理を行う。
【０１３８】
（i）ビットノード演算
LDPC復号回路は、n∈N(m)を満たすnについて、次式（２９）によりzmn(i-1)を求める。
【数２９】
0005790029.tif 000030
【０１３９】
（ii）チェックノード演算
LDPC復号回路は、n∈N(m)を満たすnについて、次式（３０）、（３１）によりεmn(i)を求める。
【数３０】
0005790029.tif 000031
【数３１】
0005790029.tif 000032
【０１４０】
（iii）硬判定
LDPC復号回路は、n∈N(m)を満たすnについて、次式（３２）によりzn(i)を求める。
【数３２】
0005790029.tif 000033
【０１４１】
また、LDPC復号回路は、zn(i)＞0である場合にはwn=1、zn(i)＜0である場合にはwn=0として硬判定を行い、判定値ベクトルwを更新する。
【０１４２】
（iv）復号終了条件判定
LDPC復号回路は、パリティチェック方程式Hw=0を満たす場合はステップ３の処理を行う。一方、LDPC復号回路は、パリティチェック方程式Hw=0を満たさない場合であって、いまの変数mがM-1でないとき、LDPC復号回路はmを1増やしてステップ１の処理を継続する。パリティチェック方程式Hw=0を満たさない場合であって、いまの変数mがM-1であるとき、LDPC復号回路はステップ２の処理を行う。
【０１４３】
ステップ２：
LDPC復号回路は、復号処理の繰り返し回数があらかじめ定められた最大回数に到達した場合、ステップ３の処理を行う。一方、復号処理の繰り返し回数があらかじめ定められた最大回数に到達していない場合、LDPC復号回路はiを1増やしてステップ１の処理を行う。
【０１４４】
ステップ３：
LDPC復号回路は、復号結果として判定値ベクトルwを出力する。
【０１４５】
以上のような一連の流れを図９のフローチャートに示す。図９において破線Ｌ２１で囲んで示す処理がステップ１の処理に対応し、一点鎖線Ｌ２２で囲んで示す処理がステップ２の処理に対応する。図９のステップＳ５１は初期化に対応し、ステップＳ５９はステップ３の処理に対応する。
【０１４６】
すなわち、LDPC復号回路は、ステップＳ５１において初期化を行い、ステップＳ５２において変数mに0を設定する。初期化としてiに1を設定する処理と、ステップＳ２の変数mに0を設定する処理はLDPC復号回路１の各回路により行われ、各εmn(0)に0を設定する処理は、チェックノード演算回路１１とビットノード演算回路１２により行われる。また、初期化として判定値ベクトルw=[wn(0)]を求める処理は硬判定回路１３により行われる。
【０１４７】
また、LDPC復号回路は、ステップＳ５３においてビットノード演算を行い、ステップＳ５４においてチェックノード演算を行う。ステップＳ５３のビットノード演算はビットノード演算回路１２により行われ、ステップＳ５４のチェックノード演算はチェックノード演算回路１１により行われる。
【０１４８】
LDPC復号回路は、ステップＳ５５において硬判定を行い、ステップＳ５６において、硬判定の結果に基づいて判定値ベクトルwを更新する。ステップＳ５５の硬判定とステップＳ５６の判定値ベクトルwの更新処理は硬判定回路１３により行われる。
【０１４９】
LDPC復号回路は、ステップＳ５７においてパリティチェック演算を行い、ステップＳ５８においてパリティチェック方程式Hw=0を満たすか否かを判定する。ステップＳ５７のパリティチェック演算と、ステップＳ５８の判定はパリティチェック回路１４により行われる。
【０１５０】
LDPC復号回路は、パリティチェック方程式Hw=0を満たすとステップＳ５８において判定した場合、ステップＳ５９において判定値ベクトルwを出力し、処理を終了させる。判定値ベクトルwを出力する処理は出力回路１５により行われる。
【０１５１】
一方、パリティチェック方程式Hw=0を満たさないとステップＳ５８において判定した場合、LDPC復号回路は、ステップＳ６０において、変数mがM-1であるか否かを判定する。変数mがM-1ではないとステップＳ６０において判定した場合、ステップＳ６１において、変数mの値を1増やし、ステップＳ５３以降の処理を繰り返す。
【０１５２】
一方、変数mがM-1であるとステップＳ６０において判定した場合、LDPC復号回路は、ステップＳ６２において、iが最大回数に到達したか否かを判定する。iが最大回数に到達していないとステップＳ６２において判定した場合、LDPC復号回路は、ステップＳ６３において、変数iの値を1増やし、ステップＳ５２以降の処理を繰り返す。ステップＳ６０の判定はパリティチェック回路１４により行われ、ステップＳ６１の処理はLDPC復号回路１の各回路により行われる。
【０１５３】
iが最大回数に到達したとステップＳ６２において判定した場合、LDPC復号回路は、ステップＳ５９において判定値ベクトルwを出力し、処理を終了させる。
【０１５４】
従来のlayered BP復号では、１回の復号処理の途中でパリティチェック方程式Hw=0を満たす復号結果が得られたとしても全てのチェックノード演算を実行した後に復号終了条件判定が行われる。従って、１回の復号処理内でM回の復号演算が必ず行われる。一方、本技術を適用したlayered BP復号によれば、１回の復号処理の間に復号終了条件判定が行われるため、m＜M-1回目の復号演算でパリティチェック方程式Hw=0を満たす復号結果が得られた場合には残りの処理を行う必要がなく、演算量を削減することができる。また、演算量を削減することができることにより、装置の消費電力を抑えることが可能になる。
【０１５５】
なお、本技術を適用したlayered BP復号においても、直前に計算されたシンドロームSm’と前回の復号処理で求められた硬判定値wn(i-1)とを保存しておき、上述したように、復号終了条件判定をシンドロームを用いて行うようにすることも可能である。
【０１５６】
［コンピュータの構成例等］
上述した一連の処理は、ハードウェアにより実行することもできるし、ソフトウェアにより実行することもできる。以上の処理をソフトウェアで実現することによって、LDPC復号にかかる時間を短縮することができる。
【０１５７】
一連の処理をソフトウェアにより実行する場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または汎用のパーソナルコンピュータなどに、プログラム記録媒体からインストールされる。
【０１５８】
図１０は、上述した一連の処理をプログラムにより実行するコンピュータのハードウェアの構成例を示すブロック図である。
【０１５９】
CPU(Central Processing Unit)５１、ROM(Read Only Memory)５２、RAM(Random Access Memory)５３は、バス５４により相互に接続されている。
【０１６０】
バス５４には、さらに、入出力インタフェース５５が接続されている。入出力インタフェース５５には、キーボード、マウスなどよりなる入力部５６、ディスプレイ、スピーカなどよりなる出力部５７が接続される。また、入出力インタフェース５５には、ハードディスクや不揮発性のメモリなどよりなる記憶部５８、ネットワークインタフェースなどよりなる通信部５９、リムーバブルメディア６１を駆動するドライブ６０が接続される。
【０１６１】
以上のように構成されるコンピュータでは、CPU５１が、例えば、記憶部５８に記憶されているプログラムを入出力インタフェース５５及びバス５４を介してRAM５３にロードして実行することにより、上述した一連の処理が行われる。
【０１６２】
CPU５１が実行するプログラムは、例えばリムーバブルメディア６１に記録して、あるいは、ローカルエリアネットワーク、インターネット、デジタル放送といった、有線または無線の伝送媒体を介して提供され、記憶部５８にインストールされる。
【０１６３】
なお、コンピュータが実行するプログラムは、本明細書で説明する順序に沿って時系列に処理が行われるプログラムであっても良いし、並列に、あるいは呼び出しが行われたとき等の必要なタイミングで処理が行われるプログラムであっても良い。
【０１６４】
本技術の実施の形態は、上述した実施の形態に限定されるものではなく、本技術の要旨を逸脱しない範囲において種々の変更が可能である。
【０１６５】
例えば、本技術は、以下のような構成もとることができる。
【０１６６】
（１）
繰り返し復号の１回の復号処理の間隔よりも短い間隔で復号終了条件を満たすか否かの判定を行い、前記復号終了条件を満たす場合、１回の前記復号処理の途中で処理を終了させる判定部を備える
復号装置。
【０１６７】
（２）
前記復号終了条件は、線形ブロック符号のパリティチェック方程式を満たすことである
前記（１）に記載の復号装置。
【０１６８】
（３）
前記線形ブロック符号はLDPC符号である
前記（２）に記載の復号装置。
【０１６９】
（４）
ビットノード演算を複数の処理に分割して行うビットノード演算部と、
前記ビットノード演算部により分割して処理が行われる毎に、分割して行われた処理の結果に基づいて部分的なビット判定値を求め、復号を行うビット判定部と
をさらに備え、
前記判定部は、前記ビット判定部により求められた前記ビット判定値に基づいて、前記復号終了条件を満たすか否かの判定を行う
前記（３）に記載の復号装置。
【０１７０】
（５）
前記判定部による直前の前記復号終了条件を満たすか否かの判定時に求められたシンドロームを保存するシンドローム保存部と、
前回の前記復号処理時に前記ビット判定部により求められた前記ビット判定値を保存するビット判定値保存部と
をさらに備え、
前記判定部は、今回の前記復号処理時に前記ビット判定部により求められた前記ビット判定値と、前記ビット判定値保存部に保存されている前記ビット判定値との差分に基づいて、前記シンドローム保存部に保存されている前記シンドロームを更新し、更新した前記シンドロームに基づいて、前記復号終了条件を満たすか否かの判定を行う
前記（４）に記載の復号装置。
【０１７１】
（６）
前記判定部は、１回目の前記復号処理を開始する前に前記復号終了条件を満たすか否かの判定を行い、前記復号終了条件を満たす場合、前記繰り返し復号を行わない
前記（１）乃至（５）のいずれかに記載の復号装置。
【０１７２】
（７）
チェックノード演算を複数の処理に分割して行うチェックノード演算部をさらに備え、
前記ビット判定部は、前記チェックノード演算部により分割して処理が行われる毎に、分割して行われた処理の結果に基づいて前記ビット判定値を求める
前記（１）乃至（６）のいずれかに記載の復号装置。
【符号の説明】
【０１７３】
１  LDPC復号回路，  １１  チェックノード演算回路，  １２  ビットノード演算回路，  １３  硬判定回路，  １４  パリティチェック回路，  １５  出力回路，  ３１  選択回路，  ４１  硬判定値保存回路，  ４２  シンドローム計算回路，  ４３  シンドローム保存回路，  ４４  判定回路
【図１】
0005790029.tif 000034
【図２】
0005790029.tif 000035
【図３】
0005790029.tif 000036
【図４】
0005790029.tif 000037
【図５】
0005790029.tif 000038
【図６】
0005790029.tif 000039
【図７】
0005790029.tif 000040
【図８】
0005790029.tif 000041
【図９】
0005790029.tif 000042
【図１０】
0005790029.tif 000043