(57)【要約】【課題】簡単な構成で、LDPC符号の復号処理を、高速に実行することができるようにする。【解決手段】格納位置決定部２０１は、復号装置の各RAMのそれぞれにおける、対数尤度比λnまたは対数事後確率比qnの格納位置を決定する処理を制御する。格納位置決定部２０１により決定された格納位置は、制御部２０３に供給され、コントローラの内部のメモリなどに記憶される。復号部２０２は、格納位置決定部２０１により決定された格納位置に基づいて、復号装置の各RAMのそれぞれに記憶されている対数尤度比λnまたは対数事後確率比qnを読み出し、受信した符号語を復号する処理を制御する。本発明は、LDPC符号の復号を行う復号装置に適用することができる。【選択図】図５
2008278184.tif 000002
【特許請求の範囲】
【請求項１】
LDPC（Low Density Parity Check）符号の復号を行う復号装置において、
１符号語分の対数尤度比または対数事後確率比を、それぞれ独立したアドレスに格納する複数の格納手段と、
前記複数の格納手段のそれぞれに格納された前記１符号語分の対数尤度比または対数事後確率比の中から、前記LDPC符号の符号化処理において用いられた検査行列の、所定の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比であって、複数個の前記対数尤度比または対数事後確率比を同時に読み出す読み出し手段と
を備える復号装置。
【請求項２】
前記格納手段の個数が、前記検査行列の行重みの最大値未満とされる
請求項１に記載の復号装置。
【請求項３】
前記検査行列の任意の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比を、前記複数の格納手段から全て読み出すのに必要な読み出し回数が、
前記検査行列の行重みの最大値を、前記格納手段の個数で割った値の小数点以下を切り上げて整数化した数である
請求項１に記載の復号装置。
【請求項４】
前記検査行列の行重みの最大値を、前記格納手段の個数で割った値の小数点以下を切り上げて整数化した数の読み出し回数で、
前記検査行列の任意の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比を、前記複数の格納手段から全て読み出せるように、前記１符号語分の対数尤度比または対数事後確率比のそれぞれを、前記複数の格納手段に格納する格納位置決定手段をさらに備える
請求項３に記載の復号装置。
【請求項５】
前記格納手段のそれぞれが、前記LDPC符号の符号長、または検査行列の重み行列の列数を、前記格納手段の個数で割った値、または、その値に１を加算した値、もしくはその値に１を減算した値に対応するアドレス数を有し、
前記１符号語分の対数尤度比または対数事後確率比が前記複数の格納手段に、それぞれ格納される
請求項４に記載の復号装置。
【請求項６】
前記格納位置決定手段は、前記１符号語分の対数尤度比または対数事後確率比のそれぞれが格納された格納手段と前記アドレスを特定する格納位置決定情報を生成し、
前記読み出し手段は、前記格納位置決定情報に基づいて、複数個の前記対数尤度比または対数事後確率比を同時に読み出す
請求項５に記載の復号装置
【請求項７】
前記検査行列が、複数個の小行列であって、それぞれＰ行Ｐ列の小行列で構成される場合、
前記小行列のP個の要素に対応するP個の対数尤度比または対数事後確率比を、１つの前記格納手段の１つのアドレスに格納する
請求項１に記載の復号装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、簡単な構成で、LDPC符号の復号処理を、高速に実行することができるようにする復号装置に関する。
【背景技術】
【０００２】
近年、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野の研究が著しく進められているが、それに伴い、誤り訂正符号化及び復号の効率化を目的として符号理論に関する研究も盛んに行われている。
【０００３】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されている。また、これらのターボ符号が開発される一方で、古くから知られる符号化方法である低密度パリティ検査符号(Low Density Parity Check codes)（以下、LDPC符号という）が脚光を浴びつつある。
【０００４】
LDPC符号は、R. G. Gallagerによる「R. G. Gallager, "Low Density Parity Check Codes", Cambridge, Massachusetts: M. I. T. Press, 1963」において最初に提案されたものであり、その後、「D. J. C. MacKay, "Good error correcting codes based on very sparse matrices", IEEE Trans. Inf. Theory, IT-45, pp. 399-431, 1999」や、「M. G. Luby, M. Mitzenmacher, M. A. Shokrollahi and D. A. Spielman, "Analysis of low density codes and improved designs using irregular graphs", in Proceedings of ACM Symposium on Theory of Computing, pp. 249-258, 1998」等において再注目されるに至ったものである。
【０００５】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる（例えば、非特許文献１参照）。
【０００６】
LDPC符号は、行列内の非ゼロ値要素の数が非常に少ない、疎なパリティ検査行列Ｈにより定義される線形符号であり、検査行列Ｈの各行及び各列の非ゼロ値要素の数が一定のもので規定される符号をregular LDPC符号、そうでないものをirregular LDPC符号と呼ぶ。
【０００７】
LDPC符号の符号化は、検査行列Ｈをガウスの消去法と適切な列の入れ替えにより生成行列Gを生成し、kビットの情報ビットのベクトルsと生成行列Ｇとに基づいて、nビットの符号語のベクトルcを生成する。符号化に関する更なる詳細については、非特許文献２に記述されている。
【０００８】
LDPC符号の復号法としては、代表的なものにsum-product復号法がある。これは基本的にはBelief Propagation(BP)として知られているアルゴリズムと等価なものである。
【０００９】
また、LDPC符号を定義しているタナーグラフ上で動作するメッセージパッシングアルゴリズムに基づいた反復復号アルゴリズムにより復号される。
【００１０】
タナーグラフでは、変数ノードの各々は、検査行列Ｈの各列に対応し、チェックノードの各々は、検査行列Ｈの各行に対応する。また、このアルゴリズムの目標は、受信値より各送信シンボルに対応する事後確率を求めることであるが、一般にLDPC符号のタナーグラフはループを含むため、BPにより正確な事後確率は計算できず近似計算となる。ただし、グラフが疎である場合には、この近似手法が比較的良好な結果を与えることが知られている（例えば、非特許文献３参照）。
【００１１】
また、sum-product復号法におけるチェックノードから変数ノードへのメッセージαの更新に用いる変数ノードからチェックノードへのメッセージβを検査行列の行毎に更新することによって、イタレーション回数が少なくても通常のsum-product復号法と同等の性能を実現でき、メモリ量も削減できるアルゴリズム(Layered BPアルゴリズム)も提案されている（例えば、非特許文献４参照）。
【００１２】
これらのLDPC復号では、検査行列の行毎に一符号語分の対数尤度比ベクトル？=[λ1λ2 …λn …λN]または対数事後確率比ベクトルQ=[ ｑ1 ｑ2 …ｑn … ｑN]の中からM行N列の検査行列Ｈのm行n列目の要素をhmnとしたときhmn = 1を満たすものを選択する必要があり、例えば、hmn = 1を満たす組がNH組あったとし、時間間隔をTSとすると、それぞれについて変数ノードからチェックノードへのメッセージの更新及びを行うのに、チェックノードから変数ノードへのメッセージの更新を行うのに、2×NH×TS の時間が必要となる。また、この変数ノードからチェックノードへのメッセージの更新及びチェックノードから変数ノードへのメッセージの更新をNI回繰り返し行うとすると、受信符号語を復号するのにかかる時間は、2×NH×NI×TS となる。一般的に復号に許容されるレイテンシは、2×NH×NI×TSよりも小さい場合が多く、この構成での実装は困難な場合がある。
【００１３】
そこで、sum-product復号法において、全ノードにおけるメッセージ更新の計算を同時に計算する構成が提案されている（例えば、非特許文献５参照）。この構成の場合、NH組の計算を1クロックで行うため、復号にかかる時間は、2×NI×TSとなりレイテンシを非常に小さくすることが可能となる。
【００１４】
また、検査行列に対して、行置換や列置換を施すことによって、構成行列（P×Pの単位行列、そのコンポーネントの1のうち1個以上が0になった準単位行列、単位行列若しくは準単位行列をサイクリックシフトしたシフト行列、単位行列、準単位行列、若しくはシフト行列の複数の和である和行列、またはP×Pのゼロ行列）の組み合わせで表すことができる検査行列に変換し、そうすることで、LDPC符号の復号におけるチェックノードから変数ノードへのメッセージの更新及び、変数ノードからチェックノードへのメッセージの更新の計算をP個並列に行うことが可能となる構成も提案されている（例えば、特許文献１参照）。これにより、復号にかかるクロック数を抑えつつ、回路規模も実現可能な範囲に抑えることが可能となる。この構成の場合、復号にかかる時間は2×NH×NI×TS / Pとなる。また、検査行列が上記構成行列の組合せで表されるとき、構成行列がゼロ行列のとき０、ゼロ行列でないとき１に置き換えて表現したM/P行N/P列の行列を重み行列と呼ぶ。
【００１５】
【非特許文献１】R. G. Gallager, "Low density parity check codes," IRE Trans. Inform. Theory, vol. 8, pp. 21-28, Jan. 1962.
【００１６】
【非特許文献２】D. J. C. MacKay, “Good error-correcting codes based on very sparse matrices,” IEEE Trans. Inform. Theory, vol. 45, pp. 399-431, Oct. 1999.
【００１７】
【非特許文献３】和田山 正, “バースト通信路に適した反復復号法,” 電子情報通信学会論文誌D-II, vol. J88-D-II, no.2, pp. 170-187, 2005.
【００１８】
【非特許文献４】D. E. Hocevar, “A reduced complexity decoder architecture via layered decoding of LDPC codes,” IEEE Workshop on Signal Processing Systems, pp. 107-112, 2004.
【００１９】
【非特許文献５】C. Howland and A. Blanksby, “Parallel Decoding Architectures for Low Density Parity Check Codes,” IEEE International Symposium on Circuits and Systems, vol. 4, pp. 742-745, May. 2001.
【００２０】
【特許文献１】特開2004-343170号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかしながら、非特許文献５の技術では、全てのノードにおけるメッセージ更新の計算を並列に行う必要があるため回路規模が増大してしまうという問題がある。また、この構成の場合、ノード間の接続を配線によって行うため複数の検査行列に対して復号器を共有することは困難であるという問題がある。
【００２２】
また、Layered BP復号法の場合には、検査行列の各行におけるhmn = 1を満たす複数のｑnを一度に読み出し、検査行列1行分のメッセージ更新の計算を並列に行う構成が考えられるが、この構成を実現するためには、ｑnをレジスタに保存して、例えば、符号長個（N個）のｑnの中から各行におけるhmn = 1を満たす複数のｑnをセレクトするセレクタが必要になる。一般的に、LDPCの符号長は数千から数万と大きいことから、この構成の回路規模は増大してしまうと考えられる。
【００２３】
さらに、次世代無線LANなどに用いられる場合など実装するアプリケーションによっては、要求レイテンシが厳しく、特許文献１の構成でも要求レイテンシを満たせない場合が生じる。
【００２４】
本発明はこのような状況に鑑みてなされたものであり、簡単な構成で、LDPC符号の復号処理を、高速に実行することができるようにするものである。
【課題を解決するための手段】
【００２５】
本発明の一側面は、LDPC（Low Density Parity Check）符号の復号を行う復号装置において、１符号語分の対数尤度比または対数事後確率比を、それぞれ独立したアドレスに格納する複数の格納手段と、前記複数の格納手段のそれぞれに格納された前記１符号語分の対数尤度比または対数事後確率比の中から、前記LDPC符号の符号化処理において用いられた検査行列の、所定の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比であって、複数個の前記対数尤度比または対数事後確率比を同時に読み出す読み出し手段とを備える復号装置である。
【００２６】
前記格納手段の個数が、前記検査行列の行重みの最大値未満とされるようにすることができる。
【００２７】
前記検査行列の任意の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比を、前記複数の格納手段から全て読み出すのに必要な読み出し回数が、前記検査行列の行重みの最大値を、前記格納手段の個数で割った値の小数点以下を切り上げて整数化した数であるようにすることができる。
【００２８】
前記検査行列の行重みの最大値を、前記格納手段の個数で割った値の小数点以下を切り上げて整数化した数の読み出し回数で、前記検査行列の任意の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比を、前記複数の格納手段から全て読み出せるように、前記１符号語分の対数尤度比または対数事後確率比のそれぞれを、前記複数の格納手段に格納する格納位置決定手段をさらに備えるようにすることができる。
【００２９】
前記格納手段のそれぞれが、前記LDPC符号の符号長、または検査行列の重み行列の列数を、前記格納手段の個数で割った値、または、その値に１を加算した値、もしくはその値に１を減算した値に対応するアドレス数を有し、前記１符号語分の対数尤度比または対数事後確率比が前記複数の格納手段に、それぞれ格納されるようにすることができる。
【００３０】
前記格納位置決定手段は、前記１符号語分の対数尤度比または対数事後確率比のそれぞれが格納された格納手段と前記アドレスを特定する格納位置決定情報を生成し、前記読み出し手段は、前記格納位置決定情報に基づいて、複数個の前記対数尤度比または対数事後確率比を同時に読み出すようにすることができる。
【００３１】
前記検査行列が、複数個の小行列であって、それぞれＰ行Ｐ列の小行列で構成される場合、前記小行列のP個の要素に対応するP個の対数尤度比または対数事後確率比を、１つの前記格納手段の１つのアドレスに格納するようにすることができる。
【００３２】
本発明の一側面においては、１符号語分の対数尤度比または対数事後確率比が、それぞれ独立したアドレスに格納され、前記複数の格納手段のそれぞれに格納された前記１符号語分の対数尤度比または対数事後確率比の中から、前記LDPC符号の符号化処理において用いられた検査行列の、所定の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比であって、複数個の前記対数尤度比または対数事後確率比が同時に読み出される。
【発明の効果】
【００３３】
本発明によれば、簡単な構成で、LDPC符号の復号処理を、高速に実行することができる。
【発明を実施するための最良の形態】
【００３４】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書または図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書または図面に記載されていることを確認するためのものである。従って、明細書または図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００３５】
本発明の一側面の復号装置は、LDPC（Low Density Parity Check）符号の復号を行う復号装置において、１符号語分の対数尤度比または対数事後確率比を、それぞれ独立したアドレスに格納する複数の格納手段（例えば、図４のRAM１００乃至RAM１０３）と、前記複数の格納手段のそれぞれに格納された前記１符号語分の対数尤度比または対数事後確率比の中から、前記LDPC符号の符号化処理において用いられた検査行列の、所定の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比であって、複数個の前記対数尤度比または対数事後確率比を同時に読み出す読み出し手段（例えば、図９のステップＳ２０３の処理を実行する図５の復号部２０２）とを備える。
【００３６】
この復号装置は、前記検査行列の行重みの最大値を、前記格納手段の個数で割った値の小数点以下を切り上げて整数化した数の読み出し回数で、前記検査行列の任意の１行における非ゼロ値の要素に対応する前記対数尤度比または対数事後確率比を、前記複数の格納手段から全て読み出せるように、前記１符号語分の対数尤度比または対数事後確率比のそれぞれを、前記複数の格納手段に格納する格納位置決定手段（例えば、図５の格納位置決定部２０１）をさらに備えるようにすることができる。
【００３７】
以下、図面を参照して、本発明の実施の形態について説明する。
【００３８】
最初に、本発明で用いられるLDPC(Low Density Parity Check)符号の復号について説明する。
【００３９】
LDPC符号は、例えば、移動体通信や深宇宙通信といった通信分野、及び地上波又は衛星ディジタル放送といった放送分野において用いられる、低密度パリティ検査符号の誤り訂正符号化及び復号の方式である。
【００４０】
符号性能の理論的限界としては、いわゆるシャノン(C. E. Shannon)の通信路符号化定理によって与えられるシャノン限界が知られている。符号理論に関する研究は、このシャノン限界に近い性能を示す符号を開発することを目的として行われている。
【００４１】
近年では、シャノン限界に近い性能を示す符号化方法として、例えば、並列連接畳み込み符号(PCCC(Parallel Concatenated Convolutional Codes))や、縦列連接畳み込み符号(SCCC(Serially Concatenated Convolutional Codes))といった、いわゆるターボ符号化(Turbo coding)と呼ばれる手法が開発されているが、これらのターボ符号が開発される一方で、古くから知られる符号化方法であるLDPC符号が脚光を浴びつつある。
【００４２】
LDPC符号は、近年の研究により、ターボ符号等と同様に、符号長を長くしていくにしたがって、シャノン限界に近い性能が得られることがわかりつつある。また、LDPC符号は、最小距離が符号長に比例するという性質があることから、その特徴として、ブロック誤り確率特性がよく、さらに、ターボ符号等の復号特性において観測される、いわゆるエラーフロア現象が殆ど生じないことも利点として挙げられる。
【００４３】
LDPC符号は、行列内の非ゼロ値の要素の数が非常に少ない、疎なパリティ検査行列Ｈにより定義される線形符号であり、検査行列Ｈの各行及び各列の非ゼロ値要素の数が一定のもので規定される符号をregular LDPC符号、そうでないものをirregular LDPC符号と呼ぶ。
【００４４】
以下では二元LDPC符号を例に説明する。LDPC符号の符号化は、検査行列Ｈに基づいて生成行列Gを生成し、この生成行列Gを２元の情報メッセージに対して乗算することによって符号語を生成することで実現される。具体的には、LDPC符号による符号化を行う符号化装置は、まず、検査行列Ｈの転置行列ＨTとの間に、式G・HT=0が成立する生成行列Gを算出する。ここで、生成行列Gが、K×N行列である場合には、符号化装置は、生成行列Gに対してKビットからなる情報メッセージ（ベクトルｓ）を乗算し、Nビットからなる符号語のベクトルｃ（＝ｓ・Ｇ）を生成する。この符号化装置によって生成された符号語は、例えば値が「0」の符号ビットが「+1」に、値が「1」の符号ビットが「−1」にといったようにマッピングされて送信され、所定の通信路を介して受信側において受信されることになる。
【００４５】
LDPC符号の符号化は、検査行列をH、生成行列をG、Kビットの情報ビットのベクトルをs、Nビットの符号語のベクトルをcで表すと、以下の式(1)によってなされることになる。
【００４６】
【数１】
2008278184.tif 000003
【００４７】
一方、LDPC符号の復号は、Gallagerが確率復号(Probabilistic Decoding)と称して提案
したアルゴリズムであって、変数ノード(variable node（メッセージノード(message node)とも呼ばれる。）)と、チェックノード(check node)とからなる、いわゆるタナーグラフ(Tanner graph)上での確率伝播(belief propagation)によるメッセージ・パッシング・アルゴリズムによって行うことが可能である。
【００４８】
LDPC符号の復号法としては、代表的なものにsum-product復号法がある。これは基本的にはBelief Propagation(BP)として知られているアルゴリズムと等価なものである。
【００４９】
ここで、タナーグラフとは、検査行列Ｈが式（２）のように与えられたとき、図１で表されるものであり、図中の上側の白い円で示されたノードを変数ノードと呼び、下側の黒い円で示されたノードをチェックノードと呼ぶ。変数ノードの各々は検査行列Ｈの各列に対応し、チェックノードの各々は検査行列Ｈの各行に対応する。また、このアルゴリズムの目標は、受信値より各送信シンボルに対応する事後確率を求めることであるが、一般にLDPC符号のタナーグラフはループを含むため、BPにより正確な事後確率は計算できず近似計算となる。ただし、グラフが疎である場合には、この近似手法が比較的良好な結果を与えることが知られている。
【００５０】
【数２】
2008278184.tif 000004
【００５１】
ここで、二元のLDPC符号についてsum-product復号法の手順を説明する。
【００５２】
符号Cは、符号長N、検査記号数Mの二元LDPC符号とし、式（３）で表される検査行列Ｈにより定義されるものとする。なお、以下において、「←」または「→」の記号は、変数などへの値の代入を表しており、「≡」の記号は、所定の値、変数などの定義を表すものとする。
【００５３】
【数３】
2008278184.tif 000005
【００５４】
ここで、hmnは検査行列Ｈのm行n列目の要素を表しており、
変数mと変数nはそれぞれ1≦m≦M，1≦n≦Nを満たす整数である。
【００５５】
例えば、受信信号から得られる１符号語分の対数尤度比ベクトルΛ=[λ1 λ2 …λn …λN]の内、第ｎ番目のビットの対数尤度比をλn（以下、適宜、単に、λnと示す）、m番目のチェックノードからn番目の変数ノードへ送られるメッセージをαmn（以下、適宜、単に、αmnと示す）、n番目の変数ノードからm番目のチェックノードに送られるメッセージをβmn（以下、適宜、単に、βmnと示す）とすると、sum-product復号法においては、次の「STEPA１」乃至「STEPA６」の各ステップの処理を行うことにより復号がなされる。
【００５６】
ここで、対数尤度比λnは、式（４）のように定義される。また、P(x|y)は、受信信号がyであったときに、本来の送信信号がxである条件付確率を表す。また、伝送路がAWGN（Additive White Gaussian Noise）通信路を仮定でき、その雑音の分散がσ2で表されるとき、λnは式（５）のように表すことができる。
【００５７】
【数４】
2008278184.tif 000006
【数５】
2008278184.tif 000007
【００５８】
STEPA1：初期化
hmn = 1を満たす全ての組(m, n)について、αmnを0に設定する。また、ループカウンタlを1に設定する。受信語ベクトルy=[y1 y2 … yn … yN]から1≦n≦Nの全てのnについてλnを式（５）に従って計算する。
STEPA2：変数ノード処理
hmn = 1を満たす全ての組(m, n)について、βmnを式（６）により計算する。ここで、n番目の変数ノードに接続するチェックノードの番号の集合をB(n)とする。
【００５９】
【数６】
2008278184.tif 000008
【００６０】
STEPA3：チェックノード処理
hmn = 1を満たす全ての組(m, n)について、αmnを式（７）により計算する。ここで、m番目のチェックノードに接続する変数ノードの番号の集合をA(m)とする。
【００６１】
【数７】
2008278184.tif 000009
【００６２】
ここで、
【００６３】
【数８】
2008278184.tif 000010
【数９】
2008278184.tif 000011
【００６４】
と定義される。
【００６５】
STEPA4：推定符号語の決定
1≦n≦Nの全てのnについて、式（１０）を計算し、更に、式（１０）により得られたｑnを用いて式（１１）を計算し、推定符号語ベクトルcハット（ただし、以下、明細書の文章中では、c_hと記載し、数式中では文字cの上に＾を記載した記号をもって記載する）= [c_h1 c_h2 …c_hn …c_hN]を求める。ここで、式（１０）のｑnは対数事後確率比（以下、適宜、単に、ｑnと示す）である。
【００６６】
【数１０】
2008278184.tif 000012
【数１１】
2008278184.tif 000013
【００６７】
STEPA5：パリティ検査
推定符号語ベクトルc_h = [c_h1 c_h2 …c_hn …c_hN]が、式（１２）を満たす場合、c_h = [c_h1 c_h2 …c_hn …c_hN]を推定符号語として出力し、処理は終了される。
【００６８】
【数１２】
2008278184.tif 000014
【００６９】
STEPA6：カウンタのインクリメント
l≦lmaxならば、l←l + 1とした後、STEPA2に戻る。l≦lmaxでなければc_h = [c_h1 c_h2 …c_hn …c_hN] を推定符号語として出力し、処理は終了される。なお、このsum-product復号法による復号については、非特許文献２と非特許文献３に詳細に記述されている。
【００７０】
また、上述したsum-product復号法における対数事後確率比ｑnの更新手順を行毎に行うことで、イタレーション回数が少なくても通常のsum-product復号法と同等の性能を実現でき、メモリ量も削減できるアルゴリズム(Layered BPアルゴリズム)も提案されている。Layered BP（アルゴリズム）復号法においては、次の「STEPB１」乃至「STEPB５」の各ステップの処理を行うことにより復号がなされる。
【００７１】
STEPB1：初期化
hmn=1を満たす全ての組(m, n)についてαmnを0に設定する。また、ループカウンタlを1に設定する。受信語ベクトルy=[y1 y2 … yn … yN]から1≦n≦Nの全てのnについてλnを式（５）に従って計算し、ｑnに代入する。
【００７２】
STEPB2：検査行列の行毎の変数ノード・チェックノード処理
検査行列の行毎に、hmn =1を満たす全ての組(m, n)について、式（１３）乃至式（１５）を順に計算する。すなわち、式（１３）で求めたβnを用いて式（１４）を計算し、式（１４）により得られたαmnを用いて式（１５）を計算し、検査行列Ｈの行毎に対数事後確率比ｑnを更新する。
【００７３】
【数１３】
2008278184.tif 000015
【数１４】
2008278184.tif 000016
【数１５】
2008278184.tif 000017
【００７４】
STEPB3：推定符号語の決定
1≦n≦Nの全てのnについて、STEPB2の結果得られるｑnを用いて、式（１１）を計算し、推定符号語ベクトルc_h = [c_h1 c_h2 …c_hn …c_hN]を求める。
【００７５】
STEPB4：パリティ検査
c_h = [c_h1 c_h2 …c_hn …c_hN]が、式（１２）を満たす場合、c_h = [c_h1 c_h2 …c_hn …c_hN]を推定符号語として出力し、処理は終了される。
【００７６】
STEPB5：カウンタのインクリメント
l≦lmaxならば、l←l + 1とした後、STEPB2に戻る。l≦lmaxでなければc_h = [c_h1 c_h2 …c_hn …c_hN]を推定符号語として出力し、処理は終了される。
【００７７】
このように、LDPC符号の復号のパリティ検査においては、式（１２）に示されるように、検査行列Ｈの転置行列と、推定符号語との積が演算され、その演算結果が０であるか否かが判定されるから、検査行列Ｈの各行において、非ゼロ値（「１」）の要素の位置に対応する（hmn = 1を満たす（m,n）に対応する）推定符号語のビットを抽出して、その抽出されたビット同士の間で排他的論理和を演算する必要がある。
【００７８】
そして、検査行列Ｈの転置行列と、推定符号語との積が０とならない場合、再度、変数ノード処理、チェックノード処理が行われ、対数事後確率比ｑnが再度演算されて更新されることになるが、このとき、再度演算されて更新される対数事後確率比ｑnは、上述した排他的論理和の演算に用いられるビットに対応する対数事後確率比ｑn、すなわち検査行列Ｈの各行において、hmn = 1を満たす（m,n）に対応するｑnのみでよい。
【００７９】
このように、LDPC符号の復号を行う場合には、対数事後確率比ｑnを更新するために、式（６）乃至式（７）、式（１３）乃至式（１５）などの演算の処理を、検査行列Ｈの各行において計算する必要があるので、Ｍ行ある検査行列Ｈの行毎に、Ｎ個の対数尤度比λn (1≦n≦N)、またはＮ個の対数事後確率比ｑn (1≦n≦N)の中からhmn = 1を満たす（m,n）に対応するλnまたはｑnのみを選択して抽出できるようにしなければ、効率的な復号の処理を実現することはできない。
【００８０】
従って、例えば、LDPC符号の復号を行う復号装置を構成する場合、Ｍ個ある検査行列Ｈの行毎に、メモリやレジスタなどに記憶されているＮ個の対数尤度比λn (1≦n≦N)、またはＮ個の対数事後確率比ｑn (1≦n≦N)の中からhmn =1を満たす（m,n）に対応するλnまたはｑnを選択して出力するセレクタなどが従来より設けられていた。
【００８１】
例えば、復号装置のデコードレイテンシに十分な余裕がある場合には、Ｎ個のλnまたはＮ個のｑnを、１つのRAM（Random Access Memory）に保存し、検査行列Ｈの各行におけるhmn =1を満たすλｎまたはｑnを、RAMのアドレスを指定することにより1つずつ読み出して計算を行えば良い。この構成を、以下、構成Aと称する。
【００８２】
しかし、構成Aの場合、復号が完了するまでに必要な処理の時間が増大する。例えば、検査行列Ｈにおいて、hmn = 1を満たす組（m,n）がNH個あったとし、復号の繰り返し回数をNIとする。いまの場合、検査行列ＨのM行分の復号を行うために、NH個の要素について、それぞれ変数ノード処理、チェックノード処理の計算が行われるので、2×NHクロックの処理が必要となる。また、この復号をNI回繰り返すことになるので、受信符号語を復号するのにかかる時間は、時間間隔をTSとすると、2×NH×NI×TS となる。
【００８３】
例えば、次に受信される符号語がレジスタやメモリなどに蓄積され終わるまでのクロック数をNBとすると、NB > 2×NH×NIであれば、この構成Aを採用することも可能である。しかし、NB <2×NH×NIである場合、構成Aを採用することはできない。また、構成Aでは、レイテンシを小さくしたい場合、復号が完了するまでに必要な処理のクロック数が多いため、高速な動作周波数が必要となり、実装が容易ではない。
【００８４】
sum-product復号法の復号装置の構成として、検査行列ＨのM行分の変数ノード処理、チェックノード処理の計算を同時に計算する構成も提案されている。この構成を、以下、構成Ｂと称する。構成Ｂの場合、検査行列ＨのM行分のNH個の要素についての、変数ノード処理、チェックノード処理の計算をそれぞれ1クロックで行うため、復号にかかる時間は、2×NI×TSとなり、例えば、構成Ａの場合と比較してレイテンシを非常に小さくすることが可能となる。
【００８５】
しかしながら、構成Ｂの場合、検査行列ＨのM行分の計算を並列に行う必要があるため回路規模が増大してしまうという問題がある。また、構成Ｂの場合、符号長が異なるLDPC符号、符号化率が異なるLDPC符号、異なる検査行列を持つLDPC符号の復号を行う復号装置を、１つの復号装置として実現することは困難であり、符号依存性が高い構成といえる。
【００８６】
また、Layered BP復号法の復号装置を構成する場合には、検査行列Ｈの各行におけるhmn=1を満たす（m,n）に対応するλnまたはｑnを一度に読み出し、検査行列Ｈの1行分の変数ノード処理及びチェックノード処理の計算を並列に行う構成が考えられるが、この構成を実現するためには、λnまたはｑnをレジスタに保存して、N（符号長）個のｑnの中から各行におけるhmn=1を満たす（m,n）に対応するλnまたはｑnを逐次選択するセレクタが必要になる。一般的に、LDPC符号の符号長は数千から数万と大きいので、このような構成では、回路規模が非常に大きくなってしまう。
【００８７】
検査行列に対して、行置換や列置換を施すことによって、例えば、Ｐ×Ｐ（Ｐ行Ｐ列）の単位行列を構成行列とし、構成行列の組み合わせで表すことができる検査行列に変換し、そうすることで、LDPC符号の復号におけるチェックノード処理、変数ノード処理の計算をＰ個並列に行う構成も提案されている。この構成を、以下、構成Ｃと称する。構成Ｃによれば、受信符号語を復号するのにかかる時間は、2×NH×NI×TS/Ｐとなる。これにより、復号にかかる時間を抑えつつ、回路規模も実現可能な範囲に抑えることが可能となるが、次世代無線LANなど、極めて小さいレイテンシが要求される場合、やはり高速な動作周波数が必要となり、実装が容易ではない。
【００８８】
しかしながら、仮に、単純な構成で、検査行列の各行におけるｈmn = 1を満たす（m,n）に対応するλnまたはｑnを、最短の時間で複数個同時に選択する機能を実現することができれば、復号にかかる時間を少なくすることができ、また、回路規模もあまり大きくなることはない。
【００８９】
そこで、本発明においては、λnまたはｑnを、１個ずつ、P個ずつ、または1行分全て選択するのではなく、検査行列の各行におけるhmn = 1を満たす（m,n）に対応するλnまたはｑnを、最短の時間で複数個（v個またはv×P個）同時に選択する構成を採用する。
【００９０】
このような構成を採用することで、例えば、構成Ｃの場合と比較して、復号にかかる時間を、さらに抑制することができるとともに、構成Ｂの場合と比較して回路規模を小さくすることも可能となる。
【００９１】
例えば、N個のλnまたはｑnの中から複数個のλnまたは複数個のｑnを取り出すために、複数のRAMを用意し、各RAMの１つのアドレスにそれぞれ１個のλnまたは１個のｑnを格納する。あるいはまた、検査行列がP行P列の構成行列で構成されている場合には、P個のλnまたはｑnにより構成されるデータを複数個同時に取り出すために、各RAMの１つのアドレスにそれぞれＰ個のλnまたはＰ個のｑnを格納する。
【００９２】
ただし、単純に（例えば、受信符号語の第１ビット目から順番に）複数のRAMにλnもしくはｑnを格納しただけでは、λnまたはｑnを取り出すときに、１つのRAMの異なるアドレスへの同時アクセスが生じる可能性が高く、検査行列における全ての行において、hmn = 1を満たす（m,n）に対応するλnもしくはｑnを最短の時間で複数個同時に読み出すことは出来なくなる。
【００９３】
簡単な例を用いて説明する。例えば、式（１６）で表されるような符号化率１／２、符号長２４の符号語を符号化または復号するための検査行列Ｈに対して、式（１７）で表される２４個のｑnをRAMａ乃至RAMｄの4つのRAMに分割して格納する場合、すなわち、ｑnを4つずつ同時に取り出す場合を考える。
【００９４】
【数１６】
2008278184.tif 000018
【数１７】
2008278184.tif 000019
【００９５】
いまの場合、符号長N=24であるので、ｑnを4つのRAMに分割して保存する場合、各RAMには6(= 24/4)のアドレスが必要となる。例えば、符号語の第１ビット目から順番にｑnを、RAMａ乃至RAMdに順に格納していくと、例えば、図2のようになる。
【００９６】
次に、図2のように格納されたｑnの中から、検査行列Ｈの各行についてｈmn = 1を満たすものを読み出す。
【００９７】
いまの場合、検査行列Ｈの第1行目では、(m, n) = (1, 1), (1, 2), (1, 4), (1, 6), (1, 10), (1, 13), (1, 14)がｈmn = 1を満たすので、２４個のｑnの中から、これら７個の(m, n)に対応するｑ1, ｑ2, ｑ4, ｑ6, ｑ10, ｑ13, ｑ14を読み出せば良いのだが、図2に示されるように格納された場合、ｑ2, ｑ6, ｑ10, ｑ14が同一のRAM（RAMb）に格納されてしまっており、例えば、これら７個のｑnを４つのRAMから7個の値を読み出そうとする際の最短時間である2クロックで読み出そうとすると、例えば、RAMbのアドレス［１］およびアドレス［２］を同時に読み出し、さらにアドレス［３］およびアドレス［４］を同時に読み出すなど、異なる２個のアドレスに同時アクセスしなければならない。また、RAMbの異なるアドレスへの同時アクセスを行うことなく、７個のｑnを全て読み出そうとすると4クロックかかってしまい効率的ではない。
【００９８】
次に、図3のようにｑnを、RAMａ乃至RAMｄに格納する場合を考える。この場合、検査行列Ｈの第1行目において読み出すべき、ｑ1、ｑ2、ｑ4、ｑ6、ｑ10、ｑ13、ｑ14は、全て4つのRAMのそれぞれに均等に格納されており、検査行列Ｈの第1行目の読み出すべき７個のｑnを、異なるアドレスへの同時アクセスを行うことなく２クロックで全て読み出すことが出来る。
【００９９】
さらに、図３のように、ｑnを、RAMａ乃至RAMｄに格納すれば、検査行列Ｈの第２行目以後についても、読み出すべきｑnを、第１行目の場合と同様に2クロックで読み出すことができる。
【０１００】
従って、図3に示されるように、検査行列Ｈの第１行目乃至第１２行目の各行において読み出すべきｑnを、すべて２クロック以下で読み出すことができるように、ｑnのRAMへの格納位置を適切に設定すれば、１つずつｑnを読み出す場合と比較して効率良く、高速にｑnを読み出すことが可能となる。また、図3に示されるようにｑnのRAMへの格納位置を適切に設定し、それぞれの格納位置を記憶しておくようにすれば、アドレスの指定により所望のｑnを取り出すことが可能となるので、例えば、複数個のｑnの中から、hmn = 1を満たす（m,n）に対応するｑnを逐次選択するためのセレクタなども不要となる。
【０１０１】
なお、ｑnのRAMへの格納位置を適切に設定するための処理については後述する。
【０１０２】
さらに、図3に示されるようにｑnのRAMへの格納位置を適切に設定すれば、１行分のhmn = 1を満たす（m,n）に対応するｑnが各行における読み出しの最短時間である２クロックで読み出される。従って、読み出されたｑnを用いて行われる変数ノード処理、チェックノード処理を２回に分けて行うようにすればよいので回路の共有化が図れ、1行分の変数ノード処理、チェックノード処理を、まとめて１回で行う構成の場合と比較して、回路規模を1/ Nrd（いまの場合、Nrd＝２）に削減することが可能となる。
【０１０３】
図３に示されるようにｑnのRAMへの格納位置が適切に設定された場合、符号長をN、検査行列Ｈの行重みの最大値をwRMax、λnまたはｑnを保存するRAMの数をNram、RAMのアドレス数をNaddr、検査行列Ｈの1行分のλnまたはｑnを取り出すために必要なクロック数をNrdとすると、式（１８）が成り立つ。Nramは、実装するシステムにおける要求レイテンシを満たすように、動作周波数や検査行列及び復号繰り返し回数などから定める。また、検査行列がP×Pの小行列の組合せで表されるとき、各RAMの１つのアドレスにP個のλnまたはｑnを格納するため、見かけ上の符号長N'を式（１９）のように定義する。ここで、N'がNramで割り切れ、そのNram個のRAMに均等にλnまたはｑnが格納されるとすると、RAMのアドレス数Naddrは式（２０）のように表される。
【０１０４】
【数１８】
2008278184.tif 000020
【数１９】
2008278184.tif 000021
【数２０】
2008278184.tif 000022
【０１０５】
なお、検査行列Ｈの行重みの最大値wRMaxは、検査行列Ｈの任意１行における、非ゼロ値の要素の最大数を表しており、例えば、式（１６）の検査行列Ｈには、１行あたり、最大で７個の要素「１」が含まれているので、行重みの最大値wRMaxは、７となる。
【０１０６】
また、検査行列Ｈが、例えば、式（２１）に示されるようなサイクリック構造を持つP×P（Ｐ行Ｐ列）の小行列（いまの場合、P = 4）の組合せで構成されている場合には、P×P行列を１つのhmnの要素とみなすことで、上述した方式を適用することが出来る。この例では、検査行列Ｈが点線で区切られた複数の小行列により構成されている。すなわち、点線で区切られた１区画が１個の小行列であり、式（２１）は、４×８＝３２個の小行列で構成され、それぞれの小行列は、４×４（４行４列）で構成されている。
【０１０７】
【数２１】
2008278184.tif 000023
【０１０８】
ここで、サイクリック構造とは、行列を構成する要素を、例えば、左右方向に、移動（シフト）させることで別の行列が得られる構造のことをいう。例えば、式（２１）の最も左上側の小行列の第１行目乃至第４行目の要素を、すべて右方向に１だけシフトさせると、その小行列の右側に隣接する小行列と同じになる。
【０１０９】
式（２１）を、式（２２）のようにみなし、各RAMに格納するλnまたはｑnを1個から４個に変更することにより、本発明の構成を適用することが可能である。ただし、その際には、Nram×P個のデータをパラレルに処理する必要があるため、変数ノード処理、チェックノード処理を行う回路の規模もP倍になる。
【０１１０】
本発明においては、一符号語分の対数事後確率比ｑnを更新する際に必要なαmn及びｑnの値を、それぞれ複数のRAMに分割して格納することにより、一度に複数の値の読み出しまたは書き込みを行い復号する復号装置を実現する。
【０１１１】
以下、本発明を、Layered BP復号法に適用した場合の例について図面を参照して説明する。
【０１１２】
図４は、本発明を適用した復号装置の一実施の形態に係る構成例を示すブロック図である。この復号装置１０は、例えば、図示せぬ他の装置からLDPC符号により符号化されて送信されてきた符号語を受信し、受信した符号語の誤り訂正を行って復号するようになされている。
【０１１３】
また、ここでは、この復号装置１０が、例えば、式（１６）に示される検査行列Ｈを用いてLDPC符号により符号化された符号語を復号する例について説明する。式（１６）にしめされる検査行列Ｈは、１２行２４列なので、検査行列の行と列を表す変数m, nはそれぞれ1≦m≦１２，１≦n≦２４を満たす整数となる。
【０１１４】
同図に示される復号装置１０の例では、受信符号語の対数尤度比λnまたは対数事後確率比ｑnを格納するRAMが、RAM１００乃至RAM１０３の４個のRAMにより構成されている。いまの場合、RAMの数Nram＝４であるから、式（２０）により各RAMのアドレス数Naddr=６が算出される。RAM１００乃至RAM１０３のアドレス数は、それぞれ６個（アドレス［１］乃至アドレス［６］）とされている。
【０１１５】
また、検査行列Ｈの行重みの最大値wRMax ＝７であるから、式（１８）により、検査行列Ｈの1行分のλnまたはｑnを取り出すために必要なクロック数Nrd＝２と算出される。
【０１１６】
また、この例では、αmnを記憶するRAMとしてRAM１０４乃至RAM１０７の４個のRAMが設けられている。いまの場合、RAM１０４乃至RAM１０７のアドレス数は、それぞれ２４個（アドレス［１］乃至アドレス［2４］）とされている。
【０１１７】
コントローラ１１２は、メモリなどを有する構成とされ、後述するように予め決定された受信符号語の対数尤度比λnまたは対数事後確率比ｑnの適切な格納位置を内部のメモリに記憶するようになされており、その情報を元に復号装置１０の各部を制御する。
【０１１８】
復号装置１０による復号が行われる場合、最初に、復号すべき符号語が受信され、例えば、その符号語１語分の各ビットに対応する対数尤度比λnが、スイッチ１０８乃至スイッチ１１１のそれぞれに供給される。符号長が２４ビットである場合、２４個のλnが、例えば、λ1乃至λ24の順に、スイッチ１０８乃至スイッチ１１１のそれぞれに供給される。
【０１１９】
このとき、コントローラ１１２は、内部のメモリなどに記憶されている格納位置に基づいて、スイッチ１０８乃至スイッチ１１１を制御する制御信号C１１乃至制御信号ｃ１４を出力する。これにより、２４個のλnは、スイッチ１０８乃至スイッチ１１１からそれぞれ信号d1乃至信号d４として出力され、RAM１００乃至RAM１０３のそれぞれのアドレスに適切に格納されていくことになる。
【０１２０】
この例では、RAM１００乃至RAM１０３の格納位置がそれぞれｑ1乃至ｑ24で示されており、この格納位置は、図３を参照して説明した格納位置と同様である。なお、まだｑnが算出されていないとき、すなわち、受信した符号語の対数尤度比λnがRAM１００乃至RAM１０３に格納されるときは、λ1乃至λ24がそれぞれｑ1乃至ｑ24で示された格納位置に格納されるものとする。
【０１２１】
そして、コントローラ１１２は、内部のメモリなどに記憶されている格納位置と、検査行列Ｈの情報に基づいて、制御信号ｃ２１乃至制御信号ｃ２４を出力し、RAM１００乃至RAM１０３から、検査行列Ｈの第１行目においてhmn = 1を満たす（m,n）に対応するλnを、更新前の対数事後確率比ｑnとして読み出し、変数ノード処理部１１３に供給する。ここでは、最大４個のλnまたはｑnが同時に読み出されて信号g1乃至信号g4として変数ノード処理部１１３に供給される。
【０１２２】
なお、αmnの値は、初期値が0としてRAM１０４乃至RAM１０７に記憶されるか、または、はじめて読み出す際に０に初期化されており、コントローラ１１２から出力された制御信号ｃ３１乃至制御信号ｃ３４に基づいて、演算に必要となるαmnがRAM１０４乃至RAM１０７から信号a１乃至信号a4として読み出されて変数ノード処理部１１３に供給される。
【０１２３】
変数ノード処理部１１３は、式（１３）により示される演算を行い、βnを算出し、算出されたβnを、それぞれ信号b1乃至信号b4としてチェックノード処理部１１４及び遅延回路１２５に供給する。ここでは、RAM１００乃至RAM１０３から同時に読み出されたλn（更新前のｑn）について同時に演算がなされる。
【０１２４】
チェックノード処理部１１４は、式（１４）により示される演算を行い、αmnを更新する。更新されたαmnは、信号a1´乃至信号a４´として演算器１１５と、RAM１０４乃至RAM１０７とにそれぞれ供給され、RAM１０４乃至RAM１０７に記憶されているαmnの値が更新される。
【０１２５】
遅延回路１２５は、チェックノード処理部１１４において、αmnの更新のための計算において生じる遅延分だけ信号ｂ１乃至信号ｂ４を遅延させる。
【０１２６】
演算器１１５は、式（１５）に示される演算を行い、更新された対数事後確率比ｑnを算出する。ここでは、遅延回路１２５及びチェックノード処理部１１４から同時に供給されたβn及び更新されたαmnの分だけ同時に対数事後確率比ｑnが算出され、それぞれ信号g1´乃至信号g４´としてスイッチ１０８乃至スイッチ１１１に供給される。
【０１２７】
このとき、コントローラ１１２が、内部のメモリなどに記憶されている格納位置に基づいて、制御信号C１１乃至制御信号C１４を出力し、更新されたｑnは、スイッチ１０８乃至スイッチ１１１からそれぞれ信号d1乃至信号d４として出力され、RAM１００乃至RAM１０３のそれぞれのアドレスに適切に格納され、RAM１００乃至RAM１０３に格納されている値が更新されていくことになる。この操作を検査行列の全ての行に対して行い、２４個のｑnを更新する。
【０１２８】
検査行列Ｈの１行分のhmn = 1を満たす（m,n）に対応するλn（またはｑn）が全て読み出されて変数ノード処理部１１３乃至演算器１１５の処理により更新された対数事後確率比ｑnが算出された後、RAM１００乃至RAM１０３に格納されている対数事後確率比ｑnの値がそれぞれ読み出され、パリティ検査部１１６に供給される。なお、上述したように、Nrd（＝２）回で、検査行列Ｈの１行分のｈmn = 1を満たす（m,n）に対応するλn（またはｑn）は全て読み出されることになる。
【０１２９】
パリティ検査部１１６は、上述したLayered BP復号法の「STEPB３」と「STEPB４」の各ステップの処理を行って、パリティ検査の結果（OKまたはNG）を表す信号pを生成し、コントローラ１１２に供給する。
【０１３０】
パリティ検査部１１６から結果NGを表す信号pが供給された場合、コントローラ１１２は、内部のメモリなどに記憶されている格納位置と、検査行列Ｈの情報に基づいて、制御信号ｃ２１乃至制御信号ｃ２４と、制御信号ｃ３１乃至制御信号ｃ３４を出力して、RAM１００乃至RAM１０３から再び検査行列Ｈの第１行目においてhmn = 1を満たす（m,n）に対応する対数事後確率比ｑnを読み出し、また、RAM１０４乃至RAM１０７からそれらに対応するαmnを読み出し、演算器１１３に供給する。これにより、RAM１００乃至RAM１０３に格納されている値がさらに更新されていくことになる。
【０１３１】
パリティ検査部１１６から結果OKを表す信号pが供給された場合、コントローラ１１２は、制御信号ｃ４を出力して、スイッチ１１７から１符号語分のｑnを符号判定部１１８に出力させる。
【０１３２】
そして、符号判定部１１８が、供給された信号の正または負の符号を判定し、例えば、正ならば「０」、負ならば「１」として、復号結果である１符号語分（２４ビット）のデータを出力する。
【０１３３】
図５は、コントローラ１１２の機能的構成例を示すブロック図である。
【０１３４】
同図に示される格納位置決定部２０１は、RAM１００乃至RAM１０３のそれぞれにおける、対数尤度比λnまたは対数事後確率比ｑnの格納位置（例えば、RAMを特定するID）を決定する処理を制御する。
【０１３５】
格納位置決定部２０１により決定された格納位置は、制御部２０３に供給され、コントローラ１１２の内部のメモリなどに記憶される。
【０１３６】
復号部２０２は、格納位置決定部２０１により決定された格納位置に基づいて、RAM１００乃至RAM１０３のそれぞれに記憶されている対数尤度比λnまたは対数事後確率比ｑnを読み出し、受信した符号語を復号する処理を制御する。すなわち、復号部２０２は、上述した、Layered BP復号法の「STEPB１」乃至「STEPB５」の各ステップの処理を、復号装置１０に実行させる。
【０１３７】
制御部２０３は、例えば、格納位置決定部２０１、および復号部２０２に処理の実行を指令し、復号装置１０の各部を制御する制御信号の生成など各種の処理を制御する。また、制御部２０３は、格納位置決定部２０１により決定された格納位置、および予め設定された検査行列Ｈを、内部のメモリに記憶したり、またそれらをメモリから読み出して、格納位置決定部２０１、または復号部２０２に供給する。
【０１３８】
なお、ここでは、格納位置決定部２０１が、コントローラ１１２の機能ブロックとして設けられていると説明したが、格納位置決定部２０１が、必ずしも復号装置１０に設けられている必要はない。例えば、復号装置１０とは別の装置（例えば、パーソナルコンピュータなど）に格納位置決定部２０１と同等の機能ブロックが設けられることとし、その装置により決定された格納位置の情報が、例えば、通信により復号装置１０に送信され、復号装置１０のコントローラ１１２の内部のメモリに格納位置が記憶されるようにすることも可能である。
【０１３９】
図６は、本発明における、対数尤度比λnまたは対数事後確率比ｑnのRAM１００乃至RAM１０３への格納位置を適切に設定するための処理である、格納位置決定処理を説明するフローチャートである。この処理を実行することにより、復号装置１０は、各λnまたはｑnを、どのRAMのどのアドレスに格納すれば、復号を行うときλnまたはｑnを最短の時間で取り出せるかを見つけ出す。すなわち、この処理が実行されることにより、図３を参照して上述したような格納位置が決定される。ここでは、この処理が、例えば、予め復号回路とは別の装置などによって実行され、その結果決定された格納位置がコントローラ１１２内の内部メモリに格納されるものとする。
【０１４０】
また、ここでは、λnまたはｑnを格納する複数のRAMであって、例えば4つのRAM（RAM１００乃至RAM１０３）のそれぞれに対して、例えば、1, 2, 3, 4のように番号を割り当てることとする。以下で用いる格納位置候補r' = [r'1 r'2 … r'i … r'N']（以下、適宜、単に、r'と示す）は、ｑnがどのRAMに格納されるかを示しており、例えば、r'8 = 4であれば、ｑ8のデータは番号「4」のRAM（RAM１０３）に格納されることを示す。
【０１４１】
図６のステップＳ１０１において、格納位置決定部２０１は、複数のRAMのそれぞれへの格納位置候補の生成数をカウントする変数itrを０に初期化する。
【０１４２】
ステップS１０２において、変数itrを１だけインクリメントする。
【０１４３】
ステップＳ１０３において、格納位置決定部２０１は、図７を参照して後述する格納位置候補生成処理を実行し、第１回目の格納位置候補r' = [r'1 r'2 … r'i … r'N']を生成する。いまの場合、符号長Ｎは２４なので、式（１９）によりＮ´も２４となる。したがって、ここでは、r'1乃至r'24の格納位置候補が生成されることになる。
【０１４４】
ステップＳ１０４において、格納位置決定部２０１は、図８を参照して後述する格納位置候補チェック処理を実行する。これにより、ステップＳ１０３の処理で生成された第１回目の格納位置候補r' = [r'1 r'2 … r'i … r'N']に、Ｎ個のλnまたはＮ個のｑnがそれぞれ格納された場合、hmn = 1を満たす（m,n）に対応するλnまたはｑnを、Nrdクロック以下で読み出せるか否かが判定される。
【０１４５】
いまの場合、RAM（RAM１００乃至RAM１０３）の個数は４個なのでNram=４、RAMのアドレス数Naddr=６、行重みの最大値wRMax=７であるから、式（１８）により、検査行列Ｈの1行分のλnまたはｑnを取り出すために必要なクロック数Nrd＝２となる。つまり、hmn=1を満たす（m,n）に対応するλnまたはｑnを、２回以下で読み出すことができれば、その格納位置候補は、図３を参照して上述したように適切に設定された格納位置であるといえ、格納位置候補チェック処理のチェック結果はＯＫとなる。
【０１４６】
一方、hmn=1を満たす（m,n）に対応するλnまたはｑnを、２クロック以下で読み出すことができなければ、その格納位置候補は、適切に設定された格納位置であるといえず、さらに格納位置候補を生成する必要があるといえ、格納位置候補チェック処理のチェック結果はＮＧとなる。
【０１４７】
ステップＳ１０４の処理の後、ステップＳ１０５において、格納位置決定部２０１は、格納位置候補チェック処理のチェック結果はＯＫであったか否かを判定する。チェック結果がOKではない（NG）と判定された場合、さらに格納位置候補を生成する必要があるので、処理は、ステップＳ１０７に進む。
【０１４８】
ステップ１０７において、変数itrが候補の総数nMAXと異なるか否かを判定する。itrがnMAXと異なっていれば、まだ生成可能な候補が存在するので、S１０２に戻り、次の候補の生成を行う。
【０１４９】
そして、ステップＳ１０３の処理で、第２回目の格納位置候補r' = [r'1 r'2 … r'i … r'N']が生成され、ステップＳ１０４の処理で、第２回目の格納位置候補r' = [r'1 r'2 … r'i … r'N']に、Ｎ個のλnまたはＮ個のｑnがそれぞれ格納された場合、hmn = 1を満たす（m,n）に対応するλnまたはｑnを、Nrdクロック以下で読み出せるか否かが判定される。
【０１５０】
このように、ステップＳ１０５において、格納位置候補チェック処理のチェック結果はＯＫと判定されるまで、ステップ１０７及びステップＳ１０２乃至Ｓ１０５の処理が繰り返し実行される。ステップＳ１０５において、格納位置候補チェック処理のチェック結果はＯＫと判定された場合、ステップ１０６によって、格納位置候補r'を最終的に決定された格納位置rとして格納位置決定処理は終了する。この場合、例えば、図３を参照して上述したような適切な格納位置が決定されたことになる。
【０１５１】
itrがnMAXと一致していれば、全ての候補が出尽くしたので、処理が終了する。この場合、いわば例外的に、λnまたはｑnの格納位置として存在し得る格納位置候補を全て生成してチェックしたにも係らず、適切に設定された格納位置が見つからなかったことになる。
【０１５２】
次に、図７のフローチャートを参照して、図６のステップＳ１０３の格納位置候補生成処理の詳細な例について説明する。
【０１５３】
ステップＳ１２１において、格納位置決定部２０１は、変数itrが１であるか否かを判定する。例えば、格納位置候補生成処理で第１回目の格納位置候補が生成される場合、変数itrが１なので、処理は、ステップＳ１２４に進むことになる。
【０１５４】
ステップＳ１２４において、格納位置決定部２０１は、変数ｉを１、格納位置候補r１を１にセットする。
【０１５５】
そして処理は、ステップＳ１２３に進み、格納位置決定部２０１は、格納位置候補r'iの値がNramより大きいか否かを判定する。いまの場合、Nram=4であり、ステップＳ１２４の処理でセットされた変数iの値は１なので、格納位置候補r'1（=1）≦ Nram（=４）となり、処理はステップＳ１２５に進む。
【０１５６】
ステップＳ１２５では、変数iの値が１だけインクリメントされ、ステップＳ１２６において、変数ｉがＮ´以下であるか否かが判定される。いまの場合変数ｉ（=2）≦ Ｎ´（=24）となり、処理は、ステップＳ１２７に進む。
【０１５７】
ステップＳ１２７において、格納位置決定部２０１は、格納位置候補r'iを１にセットする。いまの場合、格納位置候補r'2=1なる。そして、処理は、ステップＳ１２３に戻る。
【０１５８】
そして、r'2（=1）≦ Nram（=4）なので、処理は、ステップＳ１２３からステップＳ１２５乃至Ｓ１２７へと進む。
【０１５９】
このように、ステップＳ１２３及びステップ１２５乃至Ｓ１４４の処理が繰り返し実行され、変数iの値が２５になったとき、格納位置候補r' = [1 1 … 1]つまり、r'1=1、r'2=1、r'3=1、・・・r'24=1とされており、これが第１回目に生成された格納位置候補となる。
【０１６０】
ただし、この格納位置候補が生成された場合、Ｎ個のλnまたはN個のｑnが全てRAM１００に格納されることになるので、実際の格納位置としては不適切であり、当然ステップＳ１０４の処理によりチェック結果がＮＧとなる。
【０１６１】
第２回目の格納位置候補が生成される場合、図６のステップS１０２により変数itrが２であるので、図７のステップＳ１２１の判定により、処理は、ステップＳ１２２に進む。
【０１６２】
ステップＳ１２２において、格納位置決定部２０１は、変数ｉを１だけデクリメントする。これにより、iは２４（＝２５−１）となる。そして、格納位置候補r'iを１だけインクリメントする。いまの場合、r'24が２（１＋１）にセットされることになる。
【０１６３】
そして処理は、ステップＳ１２３に進み、格納位置候補r'iの値がNramより大きいか否かを判定する。いまの場合、格納位置候補r'24（=2）≦ Nram（=４）となり、処理はステップＳ１２５に進む。
【０１６４】
ステップＳ１２５では、変数iの値が１だけインクリメントされ、ステップＳ１２６において、変数ｉがＮ´以下であるか否かが判定される。いまの場合変数ｉ（=25）> Ｎ´（=24）となり、処理が終了する。いまの場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=1、r'24=2とされている。
【０１６５】
同様に、第３回目の格納位置候補が生成される場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=1、r'24=3となり、第４回目の格納位置候補が生成される場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=1、r'24=4となる。
【０１６６】
第５回目の格納位置候補が生成される場合、図７のステップＳ１２１の判定により、処理は、ステップＳ１２２に進み、格納位置決定部２０１は、変数ｉを１だけデクリメントする。これにより、iは２４（＝２５−１）となる。そして、格納位置候補r'iを１だけインクリメントする。いまの場合、r'24が5（4＋１）にセットされることになる。
【０１６７】
そして処理は、ステップＳ１２３に進み、いまの場合、格納位置候補r'24（=5）> Nram（=４）となり、ステップＳ１２３の判定により、処理は、ステップＳ１２８に進む。
【０１６８】
ステップＳ１２８において、格納位置決定部２０１は、変数ｉの値が１であるか否かを判定する。いまの場合、変数ｉ＝２４なので、処理はステップＳ１２２に戻る。
【０１６９】
ステップＳ１２２において、格納位置決定部２０１は、変数ｉを１だけデクリメントする。これにより、iは２３（＝２４−１）となる。そして、格納位置候補r'iを１だけインクリメントする。これにより、r'23は２（＝１＋１）となる。
【０１７０】
その後、処理は、ステップＳ１２３に進み、格納位置候補r'iの値がNramより大きいか否かが判定される。いまの場合、格納位置候補r'23（=2）≦ Nram（=４）となり、処理はステップＳ１２５に進む。
【０１７１】
そして、ステップＳ１２５とステップＳ１２６の処理を経て、ステップＳ１２７に進み、格納位置候補r'24が１にセットされ、処理はステップＳ１２３に戻る。
【０１７２】
さらに、ステップＳ１２３及びステップ１２５乃至Ｓ１２６の処理を経て、処理は終了する。いまの場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=2、r'24=1とされている。
【０１７３】
同様に、第６回目の格納位置候補が生成される場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=2、r'24=2とされ、第７回目の格納位置候補が生成される場合、格納位置候補r'1=1、r'2=1、r'3=1、・・・r'23=2、r'24=3とされる。
【０１７４】
このように、格納位置候補を繰り返して生成することにより、最大でNramN' = ４24（４の２４乗）通りの格納位置候補r'が生成されることになる。すなわち、第４24回目の格納位置候補が生成される場合、格納位置候補r'1=4、r'2=4、r'3=4、・・・r'24=4とされる。なお、第４24回目の格納位置候補が生成された後、図６のステップS１０４及びステップS１０５の処理を経てS１０７の処理に進む。図６のステップＳ１０７の処理において、変数itrが候補の総数nMAX（= ４24）と等しいと判定されるので、格納位置決定処理が終了することになる。
【０１７５】
次に、図８のフローチャートを参照して、図６のステップＳ１０４の格納位置候補チェック処理の詳細な例について説明する。
【０１７６】
ステップＳ１６１において、格納位置決定部２０１は、ステップＳ１０２の処理で生成された格納位置候補r' = [r'1 r'2 … r'i … r'N']に基づいて、RAM１００乃至RAM１０３にλnまたはｑnを格納した場合、検査行列Ｈの各行において、ｈmn = 1を満たす（m,n）に対応するλnまたはｑnが、RAM１００乃至RAM１０３にそれぞれいくつ格納されているかをカウントし、カウント結果を、カウンタ値として保持する。
【０１７７】
例えば、RAM１００に格納されているλnまたはｑnの個数をカウントしたカウンタ値、RAM１０１に格納されているλnまたはｑnの個数をカウントしたカウンタ値、・・・のように、４つのRAMのそれぞれに対応して４つのカウンタ値が保持される。さらに、カウンタ値は、検査行列の各行（１２行分）に対して取得されるので、いまの場合、４８（＝１２×４）通りのカウンタ値が保持されることになる。
【０１７８】
例えば、カウンタ値を格納する変数であるカウンタcntm,kを、予め定義しておく。ここで、変数ｍと変数ｋについて、
【０１７９】
1≦m≦M´，1≦ｋ≦Nram
【０１８０】
とする。ここで、M'は式（２３）のように定義されるものである。
【０１８１】
【数２３】
2008278184.tif 000024
【０１８２】
このカウンタcntm,kに、４つのRAMのそれぞれに格納されているλnまたはｑnの個数をカウントしたカウンタ値が保持される。
【０１８３】
例えば、ステップＳ１０3の処理で生成された格納位置候補r' = [r'1 r'2 … r'i … r'N']が[1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4]であった場合、検査行列Ｈが式（１６）で表されるものであるとすると、検査行列の第１行目においてhmn = 1となるのは、(m, n) = (1, 1), (1, 2), (1, 4), (1, 6), (1, 10), (1, 13), (1, 14)であり、r'1 = 1, r'2 = 1, r'4 = 1, r'6 = 1, r'10 = 2, r'13 = 3, r'14 = 3であるので、検査行列Ｈの第１行目において取り出したいｑn、つまり、ｑ1, ｑ2, ｑ4, ｑ6, ｑ10, ｑ13, ｑ14は、番号「1」のRAM（RAM１００）に4個、番号「2」のRAM（RAM１０１）に1個、番号「3」のRAM（RAM１０２）に2個、番号「4」のRAM（RAM１０３）に0個格納されていることになり、cnt1,1 = 4, cnt1,2 = 1, cnt1,3 = 2, cnt1,4 = 0となる。
【０１８４】
ステップＳ１６２において、格納位置決定部２０１は、ステップＳ１６１の処理で得られた４８通りのカウンタ値のうちのいずれかが、Nrdを超えているか否かを判定する。いまの場合、Nrdは２であるから、RAM１００乃至RAM１０３のいずれかに、各行においてhmn = 1を満たす（m,n）に対応するλnまたはｑnが、３個以上格納されている場合、ステップＳ１６２において、カウンタ値のうちのいずれかが、Nrdを超えていたと判定され、処理は、ステップＳ１６４に進む。
【０１８５】
この場合、ｈmn = 1を満たす（m,n）に対応するλnまたはｑnを、Nrdクロック以下で読み出せないことになるので、チェック結果ＮＧを表すフラグなどが設定される。なお、上述した例の場合、cnt1,1(=4) > Nrd（= 2）であるので、この格納位置候補は不適であり、チェック結果NGになる。
【０１８６】
一方、ステップＳ１６２において、格納位置決定部２０１は、ステップＳ１６１の処理で得られた４８個のカウンタ値のうちのいずれも、Nrdを超えていないと判定された場合、処理は、ステップＳ１６３に進む。
【０１８７】
この場合、例えば、図３のように、hmn = 1を満たす（m,n）に対応するλnまたはｑnを、Nrd回以下のクロック数で読み出せることになるので、チェック結果ＯＫを表すフラグなどが設定される。
【０１８８】
このようにして、生成された格納位置候補が適切であるか否かがチェックされる。すなわち、検査行列Ｈの任意の１行において、読み出すべきｑn（またはλn）を２回で全て読み出せるか否かがチェックされる。
【０１８９】
なお、図６乃至図８を参照して上述した処理は、対数尤度比λnまたは対数事後確率比ｑnのRAM１００乃至RAM１０３への格納位置を適切に設定するための処理の一例であって、他の方式により格納位置が適切に設定されるようにしてもよい。
【０１９０】
例えば、候補r'において、λnまたはｑnが各RAMに均等な個数格納されるような候補のみを生成してもよい。つまり、式（１９）により求められるN'がNramで割り切れるときは、Naddr = N' / Nramとなるように格納位置候補が生成され、N'がNramで割り切れないときは、Naddr = ceil(N' / Nram)、またはNaddr = floor(N' / Nram)となるように格納位置候補が生成されるようにする。いまの場合、１符号語分の２４個のｑn（またはλn）が、４個のRAMにそれぞれ６個ずつ格納されるように格納位置候補が生成される。また、この場合、RAM１００乃至RAM１０３のそれぞれが、LDPC符号の符号長（または検査行列の重み行列の列数）を、RAMの個数で割った値、または、その値に１を加算した値、もしくはその値に１を減算した値に対応するアドレス数を有することになる。
【０１９１】
図７を参照して上述した処理では、生成される候補の総数は、NramN'で表すことができると説明したが、この方式で格納位置候補を生成した場合、生成される格納位置候補の総数nMAXは、式（２４）で表すことができる。ただし、記号“!”は階乗を表し、xCyはx個のものから異なるy個のものを選ぶ組合せの総数を表す。このようにすることで、格納位置候補生成処理で生成する候補の数を削減することができ、より効率的な検索が可能である。
【０１９２】
【数２４】
2008278184.tif 000025
【０１９３】
このように、図６乃至図８を参照して上述した処理とは異なる方式で格納位置が適切に設定されるようにしてもよい。要は、図３を参照して上述したような適切な格納位置が決定されるようにすればよい。
【０１９４】
また、上述したように、格納位置決定部２０１により、例えば、図６乃至図８を参照して上述した処理が実行されることで、決定された格納位置は、制御部２０３に供給され、予めコントローラ１１２の内部のメモリなどに記憶される。すなわち、図６のステップＳ１０６の処理で、格納位置候補r' が決定された格納位置rとしてコントローラ１１２の内部のメモリなどに記憶される。
【０１９５】
次に、図９のフローチャートを参照して、復号装置１０による復号処理を説明する。この処理は、例えば、復号すべき符号語を受信したとき実行されるものとする。
【０１９６】
ステップS２０１において、変数ｍ及び変数ｌを１に初期化する。
【０１９７】
ステップＳ２０２において、復号部２０２は、対数尤度比λnをRAM１００乃至RAM１０３に格納する。
【０１９８】
このとき、例えば、その符号語１語分の各ビットに対応する対数尤度比λnが、スイッチ１０８乃至スイッチ１１１のそれぞれに供給され、コントローラ１１２の内部のメモリなどに記憶されている格納位置に基づいて、スイッチ１０８乃至スイッチ１１１を制御する制御信号C１１乃至制御信号C１４が出力される。これにより、２４個のλnがRAM１００乃至RAM１０３のそれぞれのアドレスに適切に格納されていく。
【０１９９】
なお、この後の処理で、RAM１００乃至RAM１０３のそれぞれのアドレスに格納された２４個の対数尤度比λnが、２４個の対数事後確率比ｑnとして更新されていくことになる。
【０２００】
ステップＳ２０３において、復号部２０２は、検査行列Ｈの第ｍ行目において、hmn = 1を満たす（m,n）に対応するλnをそれぞれRAM１００乃至RAM１０３から読み出す。
【０２０１】
このとき、コントローラ１１２の内部のメモリなどに記憶されている格納位置と、検査行列Ｈの情報に基づいて、制御信号ｃ２１乃至制御信号ｃ２４が出力され、RAM１００乃至RAM１０３から、検査行列Ｈの第１行目においてhmn = 1を満たす（m,n）に対応するλnが更新前の対数事後確率比qnとして読み出され、変数ノード処理部１１３に供給される。また、制御信号ｃ３１乃至制御信号ｃ３４に基づいて、演算に必要となるαmnがRAM１０４乃至RAM１０７から信号a１乃至信号a4として読み出されて変数ノード処理部１１３に供給される。
【０２０２】
ステップＳ２０４において、復号部２０２は、αmn、βnの値を計算する。
【０２０３】
このとき、変数ノード処理部１１３が、式（１３）により示される演算を行い、算出されたβnを、チェックノード処理部１１４に供給する。また、チェックノード処理部１１４が、式（１４）により示される演算を行う。
【０２０４】
ステップＳ２０５において、復号部２０２は、検査行列Ｈの１行分のhmn = 1を満たす（m,n）に対応するλn（またはqn）を全て、RAM１００乃至RAM１０３から読み出したか否かを判定し、まだ読み出していないと判定された場合、処理は、ステップＳ２０３に戻り、ステップＳ２０３乃至ステップＳ２０５の処理が繰り返し実行される。
【０２０５】
なお、図６乃至図８を参照して上述した処理が実行されて格納位置が決定されたことにより、あと１回のRAM１００乃至RAM１０３から読み出しにより、検査行列Ｈの１行分のhmn = 1を満たす（m,n）に対応するλn（またはqn）は全て読み出されることになる。
【０２０６】
ステップＳ２０５において、検査行列Ｈの１行分のhmn = 1を満たす（m,n）に対応するλn（またはqn）を全て、RAM１００乃至RAM１０３から読み出したと判定された場合、すなわち、ステップＳ２０３乃至２０５の処理がそれぞれ２回ずつ実行された後、処理は、ステップＳ２０６に進む。
【０２０７】
ステップS２０６において、復号部２０２は、式（１３）により求めた検査行列1行分のβnを用いて、チェックノード処理部１１４により更新されたαmnを演算させ、更新されたαmnを、信号a1´乃至信号a４´として演算器１１５と、RAM１０４乃至RAM１０７とにそれぞれ供給する。さらに、演算器１１５が、式（１５）に示される演算を行い、対数事後確率比qnが算出されてRAM１００乃至RAM１０３に格納されている値が更新される。
【０２０８】
ステップS２０７では、検査行列M行分、つまり検査行列の全ての行に対して、qnの更新を行ったか否かを判定する。いまの場合、Mは１２である。ステップＳ２０７において、ｍがMと等しくないと判定された場合、まだ全ての行に対して計算が終了していないので、処理は、ステップS２０８に進み、ｍを１だけインクリメントして、ステップS２０３に戻る。一方、ステップＳ２０７において、ｍがMと等しいと判定された場合、全ての行に対して計算が終了しているので、処理は、ステップS２０９に進む。
【０２０９】
ステップＳ２０９において、復号部２０２は、パリティ検査を行う。このとき、パリティ検査部１１６が、上述したLayered BP復号法の「STEPB３」と「STEPB４」の各ステップの処理を行って、パリティ検査の結果（OKまたはNG）を表す信号pを生成し、コントローラ１１２に供給する。
【０２１０】
ステップＳ２１０において、復号部２０２は、ステップＳ２０９におけるパリティ検査の結果がＯＫであったか否か、または、繰り返し回数を表す変数ｌが繰り返し回数の上限であるlmaxに達したか否かを判定し、結果ＯＫではなかった（結果ＮＧ）と判定された場合、処理は、ステップＳ２１１に進む。
【０２１１】
ステップＳ２１１において、復号部２０２は、変数ｍの値を１に初期化し、変数ｌの値を１だけインクリメントし、ステップＳ２０３に戻り、それ以後の処理が繰り返し実行される。
【０２１２】
ステップＳ２１０において、結果ＯＫと判定された場合、または、繰り返し回数を表す変数ｌが繰り返し回数の上限であるlmaxに達したと判定された場合、処理は、ステップＳ２１２に進み、復号部２０２は、復号結果を出力する。
【０２１３】
このとき、制御信号ｃ４が出力されて、スイッチ１１７から１符号語分のqnが符号判定部１１８に出力される。そして、符号判定部１１８が、供給された信号の正または負の符号を判定し、例えば、正ならば「０」、負ならば「１」として、復号結果である１符号語分（２４ビット）のデータを出力する。
【０２１４】
このようにしてLDPC符号の復号が行われる。
【０２１５】
このように、本発明によれば、λnまたはqnが複数個（Nram個）のRAMに格納され、検査行列の各行におけるhmn = 1を満たすλnまたはqnを複数個同時に読み出す構成とされるので、従来のように、λnまたはqnを１つのRAMに保存し、アドレス指定により1つずつ読み出す構成の場合と比較して、復号にかかるクロック数をNram分の１に抑えることが可能となる。
【０２１６】
また、本発明によれば、検査行列１行分の計算（αmn、βn、qnの値の演算）がNrd回に分けて行われるので、検査行列1行分のλnまたはqnを、一度に全て読み出す構成であって、1行分の計算を並列に行う構成の場合と比較して、回路規模を１／Nrdに削減することが可能であるとともに、計算回路の共有化を図ることも可能である。
【０２１７】
さらに、検査行列1行分のλnまたはqnを一度に全て読み出す構成の場合、λnまたはqnをレジスタなどに保持させて、その中から所望のλnまたはqnを逐次選択するセレクタなどが必要になるのに対して、本発明においては、そのセレクタが不要になるので回路規模の削減が可能となる。
【０２１８】
また、本発明を、例えば、式（２１）に示されるようなサイクリック構造を有する小行列によって構成される検査行列を用いるLDPC符号の復号装置に適用することも可能である。上述したように、式（２１）は、３２個の小行列で構成されており、それぞれの小行列は、４×４（４行４列）で構成されている。
【０２１９】
図１０は、本発明を適用した復号装置の別の構成例を示すブロック図である。同図の復号装置１１は、式（２１）に示される検査行列Ｈを用いてLDPC符号の復号を行う。
【０２２０】
図１０の例では、図４の場合と異なり、RAM１００乃至RAM１０７の各RAMへ書き込むデータが1アドレスに対して１個ではなくP個（いまの場合、4個）になるため、最初に書き込まれる対数尤度比λnをP個蓄積してＰ個まとめて1個のデータとするシンボル連接回路１２３が設けられている。
【０２２１】
例えば、１個のλnまたは１個のqnが１オクテットのデータとして表される場合、RAM１００乃至RAM１０７の各RAMの１アドレスには、４オクテットのデータが書き込まれることになる。
【０２２２】
また、図１０の例では、図４の場合と異なり、復号結果を出力する前に、まとめて1個のデータとされていたものを、元のP個（いまの場合、4個）のデータに戻すシンボル分割回路１２４が設けられている。
【０２２３】
従って、同図において、RAM１００乃至RAM１０３に供給されるデータを表す信号d1乃至信号d４、RAM１００乃至RAM１０３から読み出されたデータを表す信号g1乃至信号g4、RAM１０４乃至RAM１０７から読み出されたデータを表す信号ａ1乃至信号ａ4は、それぞれ、例えば４オクテット分のデータに対応する信号とされる。
【０２２４】
さらに、図１０の例では、図４の場合と異なり、RAM１００乃至RAM１０３から出力された４個のデータのビット位置をシフトさせるサイクリックシフタ１１９乃至サイクリックシフタ１２２が設けられている。サイクリックシフタ１１９乃至１２２は、例えば、４個のλnまたは４個のqnに対応する４オクテットのデータを構成する各オクテットをシフトさせるようになされている。
【０２２５】
式（２１）を構成する３２個の小行列は、４行４列で構成されているが、これらの小行列において、値が１（非ゼロ値）の要素は、１行あたり１のみである。従って、変数ノード処理部１１３に４個のλnまたは４個のqnを供給する場合、４個のλnまたは４個のqnの中から検査行列Ｈの非ゼロ値の要素に対応するλnまたはqn、すなわちhmn = 1を満たすλnまたはqnを特定する必要がある。
【０２２６】
サイクリックシフタ１１９乃至１２２は、４個のλnまたは４個のqnに対応する４オクテットのデータのうち、hmn = 1を満たすλnまたはqnに対応するオクテットのデータを、例えば、第１オクテットにシフトさせるようになされている。なお、サイクリックシフタ１１９乃至１２２のそれぞれは、コントローラ１１２から出力される制御信号ｃ５１乃至制御信号ｃ５４により制御され、上述したようにデータをシフトさせる。
【０２２７】
従って、同図においてサイクリックシフタ１１９乃至１２２から出力されるデータを表す信号g１１乃至信号g１４は、それぞれ信号g１乃至信号g４のデータのオクテット位置がシフトされた４オクテット分のデータに対応する信号とされる。
【０２２８】
また、図１０の変数ノード処理部１１３乃至演算器１１５、および遅延回路１２５は、それぞれ図４の場合と同様の処理を行うものであるが、例えば、それぞれ演算回路が４個並列に接続された構成とされ、４個のデータに対して処理が並列に行われるようになされている。
【０２２９】
従って、同図における変数ノード処理部１１３から出力されるデータを表す信号b1乃至信号b4、チェックノード処理部１１４から出力されるデータを表す信号a1´乃至信号ａ4´、および演算器１１５から出力されるデータを表す信号g1´乃至信号g4´は、それぞれ、例えば４オクテット分のデータに対応する信号とされる。
【０２３０】
図１０の例における、それ以外の部分の構成は、図４の場合と同様である。
【０２３１】
このように、本発明を適用して、サイクリック構造を有する小行列によって構成される検査行列を用いるLDPC符号の復号装置を構成することもできる。
【０２３２】
さらに、本発明は、符号長がＮ（いまの場合、２４）以下のものであれば、異なる符号化率、異なる符号長、または異なる検査行列を用いるLDPC符号の復号を行うことが可能である。
【０２３３】
例えば、上述した例とは異なる符号化率、異なる符号長、または異なる検査行列を用いる場合、図６乃至図８を参照して上述した処理をあらためて行い、格納位置決定部２０１により新たな格納位置を決定させる。
【０２３４】
そして、コントローラ１１２に、新たな格納位置と検査行列に対応して制御信号ｃ１１乃至制御信号ｃ１４、制御信号ｃ２１乃至制御信号ｃ２４、および制御信号ｃ３１乃至制御信号ｃ３４を出力させるようにすればよい。
【０２３５】
ただし、新たに定まるNrd × M'の値が、元のNrd × M'の値以下である必要がある。
【０２３６】
例として、例えば、式（１６）で示された検査行列Ｈに代えて式（２５）で示される検査行列Ｈを用いる場合を考える。式（２５）の検査行列Ｈの場合、符号化率が２／３のLDPC符号に用いられるものとされ、行重みの最大値wRMax = 11とされる。いまの場合、Nram = 4であるので、式（１８）によりNrd =３（＝ ceil(wRMax / Nram) = ceil(11/4)）となる。
【０２３７】
【数２５】
2008278184.tif 000026
【０２３８】
この場合、図６乃至図８を参照して上述した処理により、格納位置を決定した場合、決定された格納位置候補r' = [r'1 r'2 … r'i … r'N']として、例えば、r' = [1 1 1 1 2 3 2 3 3 4 2 4 4 2 2 1 3 2 3 3 1 4 4 4]が得られる。この格納位置にqnなどを格納することで、検査行列が式（１６)の場合と、回路構成を変更することなく、図４または図１０を参照して上述した構成の復号装置１０により、式（２５）で示される検査行列Ｈを用いたLDPＣ符号を復号することが可能である。
【０２３９】
なお、以上においては、Layered BP復号法の場合を例として説明したが、本発明を、sum-product復号法の復号装置に用いることも可能である。
【０２４０】
なお、上述した一連の処理は、ハードウェアにより実行させることもできるし、ソフトウェアにより実行させることもできる。上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、専用のハードウェアに組み込まれているコンピュータ、または、各種のプログラムをインストールすることで、各種の機能を実行することが可能な、例えば図１１に示されるような汎用のパーソナルコンピュータ５００などに、ネットワークや記録媒体からインストールされる。
【０２４１】
図１１において、CPU（Central Processing Unit）５０１は、ROM（Read Only Memory）５０２に記憶されているプログラム、または記憶部５０８からRAM（Random Access Memory）５０３にロードされたプログラムに従って各種の処理を実行する。RAM５０３にはまた、CPU５０１が各種の処理を実行する上において必要なデータなども適宜記憶される。
【０２４２】
CPU５０１、ROM５０２、およびRAM５０３は、バス５０４を介して相互に接続されている。このバス５０４にはまた、入出力インタフェース５０５も接続されている。
【０２４３】
入出力インタフェース５０５には、キーボード、マウスなどよりなる入力部５０６、CRT(Cathode Ray Tube)、ＬＣＤ(Liquid Crystal display)などよりなるディスプレイ、並びにスピーカなどよりなる出力部５０７、ハードディスクなどより構成される記憶部５０８、モデム、LANカードなどのネットワークインタフェースカードなどより構成される通信部５０９が接続されている。通信部５０９は、インターネットを含むネットワークを介しての通信処理を行う。
【０２４４】
入出力インタフェース５０５にはまた、必要に応じてドライブ５１０が接続され、磁気ディスク、光ディスク、光磁気ディスク、或いは半導体メモリなどのリムーバブルメディア５１１が適宜装着され、それらから読み出されたコンピュータプログラムが、必要に応じて記憶部５０８にインストールされる。
【０２４５】
上述した一連の処理をソフトウェアにより実行させる場合には、そのソフトウェアを構成するプログラムが、インターネットなどのネットワークや、リムーバブルメディア５１１などからなる記録媒体からインストールされる。
【０２４６】
なお、この記録媒体は、図１１に示される、装置本体とは別に、ユーザにプログラムを配信するために配布される、プログラムが記録されている磁気ディスク（フロッピディスク（登録商標）を含む）、光ディスク（CD-ROM(Compact Disk-Read Only Memory),DVD(Digital Versatile Disk)を含む）、光磁気ディスク（MD（Mini-Disk）（登録商標）を含む）、もしくは半導体メモリなどよりなるリムーバブルメディア５１１により構成されるものだけでなく、装置本体に予め組み込まれた状態でユーザに配信される、プログラムが記録されているROM５０２や、記憶部５０８に含まれるハードディスクなどで構成されるものも含む。
【０２４７】
本明細書において上述した一連の処理を実行するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【図面の簡単な説明】
【０２４８】
【図１】タナーグラフの例を示す図である。
【図２】不適切なRAMの格納位置の例を示す図である。
【図３】適切なRAMの格納位置の例を示す図である。
【図４】本発明の一実施の形態に係る復号装置の構成例を示すブロック図である。
【図５】図４のコントローラで実行されるソフトウェアの機能的構成例を示すブロック図である。
【図６】格納位置決定処理の例を説明するフローチャートである。
【図７】格納位置候補生成処理の例を説明するフローチャートである。
【図８】格納位置候補チェック処理の例を説明するフローチャートである。
【図９】復号処理の例を説明するフローチャートである。
【図１０】本発明の一実施の形態に係る復号装置の別の構成例を示すブロック図である。
【図１１】パーソナルコンピュータの構成例を示すブロック図である。
【符号の説明】
【０２４９】
１０  復号装置，  １００乃至１０７  RAM，  １１２  コントローラ，  １１３  変数ノード処理部，  １１４  チェックノード処理部，  １１５  演算器，  １１６  パリティ検査部，  １１８  符号判定部，  １２３  Ｐシンボル連接回路，  １２４  Ｐシンボル分割回路，  １２５  遅延回路，  ２０１  格納位置決定部，  ２０２  復号部，  ２０３  制御部  ５００  パーソナルコンピュータ，  ５０１  CPU，  ５１１  リムーバブルメディア
【図１】
2008278184.tif 000027
【図２】
2008278184.tif 000028
【図３】
2008278184.tif 000029
【図４】
2008278184.tif 000030
【図５】
2008278184.tif 000031
【図６】
2008278184.tif 000032
【図７】
2008278184.tif 000033
【図８】
2008278184.tif 000034
【図９】
2008278184.tif 000035
【図１０】
2008278184.tif 000036
【図１１】
2008278184.tif 000037