(57)【要約】【課題】ビット更新とパリティ更新とをパイプラインで処理できるようにする。【解決手段】イレギュラーＬＤＰＣ符号復号器は、ビット処理ユニット10-1乃至10-M（M=p1m1）と、パリティ処理ユニット20-1乃至20-mと、コントローラ40とを含む。ユニット10-1〜10-Mは、p1×p1の第１の順列行列がm1×n1に配列された構造の第１のパリティ検査行列と、p2×p2の第２の順列行列をm2×n2に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つ構造のパリティ検査行列のそれぞれ第１乃至第Ｍ行に対応して設けられ、その行内の値が“１”の各列位置に対応するビット情報を順次更新する。ユニット20-1乃至20-mは、ユニット10-1乃至10-Mによるビット更新が第１のパリティ検査行列についてはp1個、第２のパリティ検査行列についてはp2個の列位置について終了する毎に、そのp1個あるいはp2個の列位置が属するp1あるいはp2列内の値が“１”の各行位置に対応するパリティ情報を更新する。【選択図】      図２
2006339799.tif 000002
【特許請求の範囲】
【請求項１】
ｐ１×ｐ１の第１の順列行列がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を復号するイレギュラー低密度パリティチェック符号復号器であって、
前記第１のパリティ検査行列及び前記第２のパリティ検査行列の各行に対応して設けられ、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を実行するｐ１ｍ１個のビット処理ユニットと、
前記ｎ１×ｍ１に配列されたｎ１ｍ１個の前記第１の順列行列及び前記ｎ２×ｍ２に配列されたｎ２ｍ２個の前記第２の順列行列に共通に、且つｐ２よりも大きいｐ１の前記第１の順列行列の各列に対応して設けられ、前記第１の順列行列と前記第２の順列行列の当該列が属する前記パリティ検査行列の列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を実行するｐ１個のパリティ処理ユニットと、
前記ｐ１ｍ１個のビット処理ユニットによるビット更新処理が前記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する前記第１のパリティ検査行列のｐ１列に対応するパリティ更新処理を前記ｐ１個のパリティ処理ユニットにより実行させ、前記ｐ１個のパリティ処理ユニットによるパリティ更新処理が前記第１のパリティ検査行列の最初のｐ１列について終了した場合に、前記ｐ１ｍ１個のビット処理ユニットによる次のビット更新処理を開始させ、前記ｐ２ｍ２個のビット処理ユニットによるビット更新処理が前記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する前記第２のパリティ検査行列のｐ２列に対応するパリティ更新処理を前記ｐ２個のパリティ処理ユニットにより実行させ、前記ｐ２個のパリティ処理ユニットによるパリティ更新処理が前記第２のパリティ検査行列の最初のｐ２列について終了した場合に、前記ｐ２ｍ２個のビット処理ユニットによる次のビット更新処理を開始させるコントローラと
を具備することを特徴とするイレギュラー低密度パリティチェック符号復号器。
【請求項２】
前記第１のパリティ検査行列と前記第２のパリティ検査行列とは、ｐ１×ｎ１＝ｐ２×ｎ２の条件を満たすことを特徴とする請求項１記載のイレギュラー低密度パリティチェック符号復号器。
【請求項３】
前記ｐ１ｍ１個のビット処理ユニットの各々は、
前記第１のパリティ検査行列または前記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を順次加算する加算処理により、そのパリティ情報の値の総和を計算する加算回路と、
前記加算回路によって計算された総和から前記第１のパリティ検査行列または前記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を減じる減算処理を実行する減算回路とを含む
ことを特徴とする請求項１記載のイレギュラー低密度パリティチェック符号復号器。
【請求項４】
前記コントローラは、前記ｐ１ｍ１個のビット処理ユニットにそれぞれ含まれている前記減算回路による減算処理が、前記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、前記ビット更新処理が当該ｐ１個の列位置について終了したとして、そのｐ１個の列位置が属するｐ１列に対応するパリティ更新処理を前記ｐ１個のパリティ処理ユニットにより実行させ、前記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、前記ビット更新処理が当該ｐ２個の列位置について終了したとして、そのｐ２個の列位置が属するｐ２列に対応するパリティ更新処理を前記ｐ２個のパリティ処理ユニットにより実行させることを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項５】
前記ｐ１ｍ１個のビット処理ユニットの各々は、前記減算回路の出力を確率演算のための特定の関数の演算値に変換する第１のルックアップテーブルを含み、
前記ｐ１個のパリティ処理ユニットの各々は、その出力側に、更新されたパリティ情報の値を前記特定の関数の演算値に変換する第２のルックアップテーブルを含む
ことを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項６】
前記第１のパリティ検査行列内の前記ｎ１ｍ１個の順列行列の配列ｎ１×ｍ１はｍ１＜ｎ１の関係があり、
前記ｐ１個のパリティ処理ユニットの各々は、前記第１のパリティ検査行列の対応する列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力し、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新し、
前記第２のパリティ検査行列内の前記ｎ２ｍ２個の順列行列の配列ｎ２×ｍ２はｎ２＜ｍ２の関係があり、
前記ｐ１個のパリティ処理ユニットの各々は、前記第２のパリティ検査行列の対応する列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力し、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新することを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項７】
前記ｐ１ｍ１個のビット処理ユニットの各々は、前記減算回路の出力を確率演算のための特定の関数の演算値に変換する第１のルックアップテーブルを含み、
前記ｐ１個のパリティ処理ユニットの各々は、その出力側に、更新されたｍ２個のパリティ情報の値を前記特定の関数の演算値に変換するｍ２個の第２のルックアップテーブルを含む
ことを特徴とする請求項６記載のイレギュラー低密度パリティチェック符号復号器。
【請求項８】
ｐ１×ｐ１の第１の順列行列がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる、ｐ１×ｎ１＝ｐ２×ｎ２の条件を満たす連接行列を検査行列とするイレギュラー低密度パリティチェック符号を復号するイレギュラー低密度パリティチェック符号復号器。
【請求項９】
ｐ１×ｐ１の第１の順列行列がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を復号する低密度パリティチェック符号復号方法であって、
前記第１のパリティ検査行列及び前記第２のパリティ検査行列の各行毎に、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を並行して実行するビット更新ステップと、
前記第１のパリティ検査行列に対してはｐ１列を単位にし、前記第２のパリティ検査行列に対してはｐ２列を単位にして、その列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を並行して実行するパリティ更新ステップと、
前記ビット更新ステップによるビット更新処理が前記第１のパリティ検査行列の各行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する前記第１のパリティ検査行列のｐ１列に対応する前記パリティ更新ステップによるパリティ更新処理を実行させるステップと、
前記パリティ更新ステップによるパリティ更新処理が前記第１のパリティ検査行列の最初のｐ１列について終了した場合に、前記ビット処理ステップによる次のビット更新処理を開始させるステップと、
前記ビット更新ステップによるビット更新処理が前記第２のパリティ検査行列の各行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する前記第２のパリティ検査行列のｐ２列に対応する前記パリティ更新ステップによるパリティ更新処理を実行させるステップと、
前記パリティ更新ステップによるパリティ更新処理が前記第２のパリティ検査行列の最初のｐ２列について終了した場合に、前記ビット処理ステップによる次のビット更新処理を開始させるステップと
を具備することを特徴とする低密度パリティチェック符号復号方法。
【請求項１０】
前記ビット更新ステップは、
前記パリティ検査行列の各行毎に、当該行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を順次加算する加算処理を並行して実行することにより、前記パリティ検査行列の各行毎にパリティ情報の値の総和を計算する加算ステップと、
前記加算ステップによって計算された前記パリティ検査行列の各行毎の総和から、それぞれ前記パリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を減じる減算処理を並行して実行する減算ステップとを含む
ことを特徴とする請求項９記載の低密度パリティチェック符号復号方法。
【請求項１１】
前記ビット更新ステップは、前記減算ステップにおける前記各行毎の減算処理の結果を、当該各行毎に設けられた第１のルックアップテーブルにより確率演算のための特定の関数の演算値に変換するステップを含み、
前記パリティ更新ステップは、前記第１のパリティ検査行列のｐ１列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、及び前記第２のパリティ検査行列のｐ２列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、その更新されたパリティ情報の値を、当該ｐ２行の各行毎に設けられた第２のルックアップテーブルにより前記特定の関数の演算値に変換するステップを含む
ことを特徴とする請求項１０記載の低密度パリティチェック符号復号方法。
【請求項１２】
前記第１のパリティ検査行列内の前記ｎ１ｍ１個の順列行列の配列ｎ１×ｍ１はｍ１＜ｎ１の関係があり、前記第２のパリティ検査行列内の前記ｎ２ｍ２個の順列行列の配列ｎ２×ｍ２はｎ２＜ｍ２の関係があり、
前記パリティ更新ステップは、
前記第１のパリティ検査行列のｐ１列を単位に、その列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力するステップと、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新するステップと、
前記第２のパリティ検査行列のｐ２列を単位に、その列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力するステップと、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新するステップと
を含む
ことを特徴とする請求項１０記載の低密度パリティチェック符号復号方法。
【請求項１３】
前記ビット更新ステップは、前記減算ステップにおける前記各行毎の減算処理の結果を、当該各行毎に設けられた第１のルックアップテーブルにより確率演算のための特定の関数の演算値に変換するステップを含み、
前記パリティ更新ステップは、前記第１のパリティ検査行列のｐ１列を単位とするパリティ更新処理により、そのｐ１列の各列毎に、その列内の値が“１”のｒ個の行位置に対応するパリティ情報が更新される都度、及び前記第２のパリティ検査行列のｐ２列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、そのｐ１列またはｐ２列のの各列毎に更新されたｍ１個またはｍ２個のパリティ情報の値を、当該ｐ２行の各行毎に設けられたｍ２個の第２のルックアップテーブルにより前記特定の関数の演算値に同時に変換するステップを含む
ことを特徴とする請求項１２記載の低密度パリティチェック符号復号方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、イレギュラー低密度パリティチェック（Irregular Low Density Parity Check）符号を復号するためのイレギュラー低密度パリティチェック符号復号器及び方法に関する。
【背景技術】
【０００２】
最近、誤り検査訂正符号として、低密度パリティチェック符号（以下、ＬＤＰＣ符号と称する）が注目されている。ＬＤＰＣ符号を復号する技術として、メッセージパッシングアルゴリズム（Message-Passing Algorithm）が知られている（例えば、非特許文献１参照）。メッセージパッシングアルゴリズムでは、ＬＤＰＣ符号を復号するために、当該ＬＤＰＣ符号における検査行列（パリティ検査行列）の行毎のビット更新と、列毎のパリティ更新とが反復実行される。
【非特許文献１】アンドリュー・ジェイ・ブランクスビー(Andrew J. Blanksby），クリス・ジェイ・ホーランド(Chris J. Howland)，「A 690-mW 1-Gb/s 1024-b, rate-1/2 低密度パリティチェック符号復号器(A 690-mW 1-Gb/s 1024-b, Rate-1/2 Low-Density Parity-Check Code Decoder)」，IEEE Journal of Solid-State Circuits, Vol. 37, No. 3, March 2002 p.404-412」
【発明の開示】
【発明が解決しようとする課題】
【０００３】
メッセージパッシングアルゴリズムによりＬＤＰＣ符号を復号する場合に、ビット更新とパリティ更新とは相互に依存している。このため従来技術においては、ビット更新が終了するまでパリティ更新を開始できないし、パリティ更新が終了するまでビット更新を開始できない。特に、異なる配列のパリティ検査行列が連接されたイレギュラーＬＤＰＣ符号については高速符号化をすることができなかった。
【０００４】
本発明は上記事情を考慮してなされたものでその目的は、ビット更新とパリティ更新とをパイプラインで処理することで高速復号化を可能とするイレギュラー低密度パリティチェック符号復号器及び方法を提供することにある。
【課題を解決するための手段】
【０００５】
本発明の１つの観点によれば、ｐ１×ｐ１の第１の順列行列がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラーＬＤＰＣ符号（イレギュラー低密度パリティチェック符号）を復号するイレギュラーＬＤＰＣ符号復号器が提供される。このイレギュラーＬＤＰＣ符号復号器は、上記パリティ検査行列の各行に対応して設けられ、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を実行するｐ１ｍ１個のビット処理ユニットと、上記ｎ１×ｍ１に配列されたｎ１ｍ１個の順列行列及び前記ｎ２×ｍ２に配列されたｎ２ｍ２個の前記第２の順列行列に共通に、且つｐ２よりも大きいｐ１の前記第１の順列行列の各列に対応して設けられ、前記第１の順列行列と前記第２の順列行列の当該列が属する上記パリティ検査行列の列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を実行するｐ１個のパリティ処理ユニットと、上記ｐ１ｍ１個のビット処理ユニットによるビット更新処理が上記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する第１のパリティ検査行列のｐ１列に対応するパリティ更新処理を上記ｐ１個のパリティ処理ユニットにより実行させ、上記ｐ１個のパリティ処理ユニットによるパリティ更新処理が上記第１のパリティ検査行列の最初のｐ１列について終了した場合に、上記ｐ１ｍ１個のビット処理ユニットによる新たなビット更新処理を開始させ、上記ｐ２ｍ２個のビット処理ユニットによるビット更新処理が上記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する第２のパリティ検査行列のｐ２列に対応するパリティ更新処理を上記ｐ２個のパリティ処理ユニットにより実行させ、上記ｐ２個のパリティ処理ユニットによるパリティ更新処理が上記第２のパリティ検査行列の最初のｐ２列について終了した場合に、上記ｐ２ｍ２個のビット処理ユニットによる次のビット更新処理を開始させるコントローラとを備えることを特徴とする。
【０００６】
このように、上記イレギュラーＬＤＰＣ符号復号器は、ＬＤＰＣ符号のパリティ検査行列が、ｐ１×ｐ１の第１の順列行列をｎ１×ｍ１に配列した構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を前提として構成されている。特に、第１のパリティ検査行列と第２のパリティ検査行列とは、ｐ１×ｎ１＝ｐ２×ｎ２の条件を満たすことが好ましい。
【０００７】
上記の構成のＬＤＰＣ符号復号器においては、パリティ検査行列の各行に対応して設けられたｐ１ｍ１個のビット処理ユニットにより、第１のパリティ検査行列または第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理が並行して行われる。このｐ１ｍ１個のビット処理ユニットによるビット更新処理が第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了すると、ｐ１個のパリティ処理ユニットによる、そのｐ１個の列位置が属するパリティ検査行列のｐ１列に対応するパリティ更新処理を実行し、またビット更新処理が第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了すると、ｐ２個のパリティ処理ユニットによる、そのｐ２個の列位置が属するパリティ検査行列のｐ２列に対応するパリティ更新処理を実行することが可能となる。つまり、従来のように、ビット更新処理がパリティ検査行列の各行の全ての列位置について終了するのを待つことなく、第１のパリティ検査行列についてはｐ１個の列位置、第２のパリティ検査行列についてはｐ２個の列位置についてのビット更新が終了する毎に、更新されたビット情報を用いて、そのｐ１個またはｐ２個の列位置が属するパリティ検査行列のｐ１列またはｐ２列に対応するパリティ更新処理を実行できる。また、上記ｐ１個のパリティ処理ユニットによるパリティ更新処理が第１のパリティ検査行列の最初のｐ１列について終了した場合、あるいは上記ｐ２個のパリティ処理ユニットによるパリティ更新処理が第２のパリティ検査行列の最初のｐ２列について終了した場合に、上記ｐ１ｍ１個のビット処理ユニットによる次のビット更新処理を開始させることが可能となる。つまり、従来のように、パリティ更新処理がパリティ検査行列の全ての列について終了するのを待つことなく、パリティ検査行列の最初のｍ列についてのパリティ更新が終了した段階で、更新されたパリティ情報を用いて、次の新たなビット更新処理を開始できる。換言するならば、ビット更新処理とパリティ更新処理とをパイプラインで反復させることができる。
【０００８】
ここで、上記ｐ１ｍ１個のビット処理ユニットの各々が、上記第１のパリティ検査行列または上記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を順次加算する加算処理により、そのパリティ情報の値の総和を計算する加算回路と、この加算回路によって計算された総和から上記第１のパリティ検査行列または上記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を減じる減算処理を実行する減算回路とを含む構成とすると良い。
【０００９】
この場合、減算処理による減算処理の途中（減算処理による減算処理が第１のパリティ検査行列についてはｐ１個、第２のパリティ検査行列についてはｐ２個の列位置について終了した段階）で、パリティ更新処理を開始できる。また、減算処理による減算処理中でも、第１のパリティ検査行列については最初のｐ１列についてのパリティ更新処理が終了した場合、第２のパリティ検査行列については最初のｐ２列についてのパリティ更新処理が終了した場合に、そのパリティ更新処理で更新されたパリティ情報を用いて、次のビット更新処理における加算処理を開始できる。
【００１０】
また、上記ｐ１ｍ１個のビット処理ユニットの各々が、上記減算回路の出力を確率演算のための特定の関数の演算値に変換する第１のルックアップテーブルを含み、上記ｐ１個のパリティ処理ユニットの各々が、その出力側に、更新されたパリティ情報の値を上記特定の関数の演算値に変換する第２のルックアップテーブルを含む構成とすると良い。このような構成においては、ｐ１ｍ１個のビット処理ユニットの各々の入力側にルックアップテーブルを設けるのに比べて、イレギュラーＬＤＰＣ符号復号器全体で必要とするルックアップテーブルの個数を減らすことができる。
【００１１】
また、上記第１のパリティ検査行列内の上記ｎ１ｍ１個の順列行列の配列ｎ１×ｍ１がｍ１＜ｎ１の関係にある場合に、上記ｐ１個のパリティ処理ユニットの各々が、上記第１のパリティ検査行列の対応する列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力し、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新し、上記第２のパリティ検査行列内の上記ｎ２ｍ２個の順列行列の配列ｎ２×ｍ２がｎ２＜ｍ２の関係にある場合に、上記ｐ１個のパリティ処理ユニットの各々が、上記第２のパリティ検査行列の対応する列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力し、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新する構成とすると良い。この場合、各パリティ処理ユニットによるパリティ更新処理を短時間で実行できる。
【発明の効果】
【００１２】
本発明によれば、ビット更新とパリティ更新とをパイプラインで処理することができ、これによりイレギュラーＬＤＰＣ符号の復号に要する時間を大幅に短縮することができる。
【発明を実施するための最良の形態】
【００１３】
以下、本発明の一実施形態につき図面を参照して説明する。  
まず、本実施形態で適用される、イレギュラーＬＤＰＣ符号のパリティ検査行列Ｈについて説明する。このパリティ検査行列Ｈは、図１に示すように、ｐ１×ｐ１の第１の順列行列（Permuted Matrix）Ｉg,h（ｇ＝１，２，…ｍ１，ｈ＝１，２，…，ｎ１）がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列Ｉg,h（ｇ＝１，２，…ｍ２，ｈ＝ｎ１＋１，ｎ１＋２，…，ｎ１＋ｎ２）をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列として表される。各順列行列Ｉg,hは検査行列Ｈのサブマトリクスであり、第１の順列行列についてはｐ１×ｐ１の単位行列Ｉ、第２の順列行列についてはｐ２×ｐ２の単位行列Ｉの異なる２つの行の交換、もしくは異なる２つの列の交換を、複数回数繰り返すことにより得られる行列である。第１のパリティ検査行列と第２のパリティ検査行列とは、ｐ１×ｎ１＝ｐ２×ｎ２の条件を満たすように構成される。この場合、検査行列Ｈの行数Ｍはｐ１ｍ１であり、列数Ｎは（ｐ１ｎ１＋ｐ２ｎ２）である。図１の例では、ｍ１＝３、ｎ１＝５、ｍ２＝５、ｎ１＝３である。検査行列Ｈは、Ｍ（＝ｐ１ｍ１）個のパリティノードと、Ｎ（＝ｐ１ｎ１＋ｐ２ｎ２）個のビットノードを含む。この検査行列Ｈは、イレギュラーＬＤＰＣ符号がＮ（＝ｐ１ｎ１＋ｐ２ｎ２）ビットである場合を前提としている。このイレギュラーＬＤＰＣ符号のｊ番目（ｊ＝１，２，…，Ｎ）のビットをｘjと表現する。検査行列Ｈの各行は、周知のように、それぞれ１つのパリティチェック方程式であると見なすことができる。検査行列Ｈの第ｉ行に対応するパリティチェック方程式は、第ｉパリティチェック方程式と呼ばれる。ＮビットのイレギュラーＬＤＰＣ符号は、検査行列Ｈ内の全てのパリティチェック方程式、つまり第１乃至第Ｍパリティチェック方程式を満足しなければならない。
【００１４】
図１中の各順列行列Ｉg,hにおける斜めの線は、値が“１”のビットの位置の軌跡を表す。図１から明らかなように、検査行列Ｈを構成する３（ｍ１）×５（ｎ１）個の各第１の順列行列Ｉg,hの各行及び各列内の“１”の個数、５（ｍ２）×３（ｎ２）個の各第２の順列行列Ｉg,hの各行及び各列内の“１”の個数はいずれも１である。したがって、検査行列Ｈの各行及び各列内の“１”の個数は、ｎ１×ｍ１の配列中ではそれぞれｎ１個及びｍ１個、ｎ２×ｍ２の配列中ではそれぞれｎ２個及びｍ２個である。ｍ１とｎ１はｍ１＜ｎ１を満たすように設定される。このため検査行列Ｈのｎ１×ｍ１の配列中では１行内の“１”の個数は、１列内の１の個数に比べて多い。
【００１５】
メッセージパッシングアルゴリズムによりイレギュラーＬＤＰＣ符号を復号するには、一般にビット更新とパリティ更新とを反復する必要がある。
【００１６】
通常、ビット更新は次式で表現される。
【数１】
2006339799.tif 000003
【００１７】
ここで、ｒi,j，Ｍ(i)，Ｍ(i)＼ｊ，ｊ'∈M(i)＼ｊ，ｑi,j'，ｓｇｎ(ｑi,j'),Ψ( )は次の通りである。  
ｒi,jは、パリティノードからビットノードに、検査行列Ｈの第ｉ行の各ビット（但し、第ｉ行のｊ番目の位置のビットを除く）に対応するパリティ情報（信頼性情報）ｑi,j'を受け渡すことにより求められる。ｒi,jは、検査行列Ｈの第ｉ行内のｊ番目の位置に対応する符号ビットｘjに関する信頼性を表すビット情報（信頼性情報）である。ここでは、ｒi,jは、ビットｘjが０または１である確率それ自体ではなくて、その確率の対数値を表すものとする。ここで対数値を用いるのは、乗除算を加減算に置き換えることを可能とするためである。
【００１８】
Ｍ(i)は、検査行列Ｈの第ｉ行内で“１”となるビットの列位置の集合を表す。  
Ｍ(i)＼jは、ｊを除くＭ(i)を表す。  
ｊ'∈Ｍ(i)＼ｊは、ｊを除くＭ(i)に含まれている任意の列位置を表す。  
ｑi,j'は、検査行列Ｈの第ｉ行内のｊ番目の位置に対応する符号ビットｘj'に関する信頼性を表すパリティ情報（信頼性情報）である。ｑi,j'は、ビットｘj'が０または１である確率それ自体ではなくて、その確率の対数値を表すものとする。
【００１９】
ｓｇｎ(ｑi,j')は、ｑi,j'の符号を表す。ｑi,j'の符号は当該ｑi,j'の最上位ビットＭＳＢで示される。もし、ｑi,j'が負であるなら、ｓｇｎ(ｑi,j')＝−１となり、ＭＳＢ(ｑi,j')＝１である。また、ｑi,j'が負でないなら、つまり零または正であるなら、ｓｇｎ(ｑi,j')＝＋１となり、ＭＳＢ(ｑi,j')＝０である。
【００２０】
Ψ( )は、確率演算のための関数（以下、Ψ関数と称する）である。
【００２１】
また、パリティ更新は次式で表現される
【数２】
2006339799.tif 000004
【００２２】
ここで、ｑi,j，ｐj，Ｎ(j)，Ｎ(j)＼ｉ，ｉ'∈Ｎ(j)＼ｉ，ｒi',jは次の通りである。  
ｑi,jは、ビットノードからパリティノードに、検査行列Ｈの第ｊ行の各ビット（但し、第ｊ列のｉ番目の位置のビットを除く）に対応するビット情報（信頼性情報）ｒi',jを受け渡すことにより求められる。ｑi,jは、検査行列Ｈの第ｉ行内のｊ番目の位置のビットｘjに関する信頼性を表すパリティ情報（信頼性情報）である。このｑi,jが上記ｑi,j'として上記式（１）に従うビット更新に用いられる。
【００２３】
ｐjは、イレギュラーＬＤＰＣ符号が通信チャネルを通って出力された際に、その出力から推定される当該符号中のｊ番目のビットｘjが１または０である確率（初期確率）の対数値を表す。検査行列Ｈにおいて値が“１”の各ビットに対応するｑi,jの初期値はｐjに一致する。
【００２４】
Ｎ(j)は、検査行列Ｈの第ｊ列で“１”となるビットの行位置の集合を表す。  
Ｎ(j)＼ｉは、ｉを除くＮ(j)を表す。  
ｉ'∈Ｎ(j)＼ｉは、ｉを除くＮ(j)に含まれている任意の行位置を表す。  
ｒi',jは、検査行列Ｈの第ｉ行内のｊ番目の位置のビットｘjに関する信頼性を表すビット情報（信頼性情報）である。このｒi',jには、上記式（１）に従う計算で更新されたｒi,jが用いられる。
【００２５】
図２は本発明の一実施形態に係るイレギュラーＬＤＰＣ符号復号器の構成を示すブロック図である。同図に示すように、イレギュラーＬＤＰＣ符号復号器は、Ｍ個（Ｍ＝ｐ１ｍ１＝３ｐ１）のビット処理ユニット１０-1乃至１０-Mと、ｐ１個のパリティ処理ユニット２０-1乃至２０-mと、メモリ３０と、コントローラ４０とから構成される。パリティ処理ユニット２０-1乃至２０-mは、パリティ検査行列Ｈがｐ１×ｎ１＝ｐ２×ｎ２の条件を満たす場合に、ｐ１とｐ２のうち大きい方の数だけ設けられる。
【００２６】
ビット処理ユニット１０-1乃至１０-Mは、それぞれ検査行列Ｈの第１行乃至第Ｍ行に対応して設けられる。ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）は、上記式（１）で示される、検査行列Ｈの第ｉ行におけるビット更新の処理を実行する。
【００２７】
パリティ処理ユニット２０-1乃至２０-mは、検査行列Ｈにおける第１のパリティ検査行列と第２のパリティ検査行列とに含まれる全ての順列行列Ｉg,hに共通に、第１のパリティ検査行列の順列行列Ｉg,h内の第１列乃至第ｐ１列に対応して設けられる。
【００２８】
パリティ処理ユニット２０-k（ｋ＝１，２，…，ｐ１）は、第１のパリティ検査行列については、全てのｈ（ｈ＝１，２，…，ｎ１、但し、ｎ１＝５）について、順列行列Ｉg,h内の第ｋ列が属する検査行列Ｈ内の第（（ｈ−１）ｐ１＋ｋ）列のパリティ更新を行うのに用いられる。つまり、パリティ処理ユニット２０-kは、第１のパリティ検査行列では、第ｋ列、第（ｐ１＋ｋ）列、第（２（ｐ１）＋ｋ）列、第（３（ｐ１）＋ｋ）列及び第（４（ｐ１）＋ｋ）列のパリティ更新を行うのに用いられる。例えば、パリティ処理ユニット２０-１は、第１のパリティ検査行列における第１列、第（ｐ１＋１）列、第（２（ｐ１）＋１）列、第（３（ｐ１）＋１）列及び第（４（ｐ１）＋１）列のパリティ更新を行うのに用いられる。同様に、パリティ処理ユニット２０-mは、第１のパリティ検査行列における第ｐ１列、第２（ｐ１）列、第３（ｐ１）列、第４（ｐ１）列及び第５（ｐ１）列（第Ｎ−（ｐ２ｎ２）列）のパリティ更新を行うのに用いられる。
【００２９】
また、パリティ処理ユニット２０-k（ｋ＝１，２，…，ｐ２）は、第２のパリティ検査行列については、全てのｈ（ｈ＝ｎ１＋１，ｎ１＋２，…，ｎ１＋ｎ２、但し、ｎ１＝５，ｎ２＝３）について、順列行列Ｉg,h内の第ｋ列が属する検査行列Ｈ内の第（（ｈ−１）ｐ２＋ｋ）列のパリティ更新を行うのに用いられる。すなわち、第２のパリティ検査行列に対しては、パリティ処理ユニット２０-1乃至２０-mの一部（パリティ処理ユニット２０-1乃至２０-p2）が用いられる。パリティ処理ユニット２０-kは、第２のパリティ検査行列では、第ｋ列、第（ｐ２＋ｋ）列、及び第（２（ｐ２)＋ｋ）列のパリティ更新を行うのに用いられる。例えば、パリティ処理ユニット２０-１は、第２のパリティ検査行列における第１列、第（ｐ２＋１）列、第（２（ｐ２）＋１）列のパリティ更新を行うのに用いられる。同様に、パリティ処理ユニット２０-p1は、第２のパリティ検査行列における第ｐ２列、第２（ｐ２）列、及び第３（ｐ２）列のパリティ更新を行うのに用いられる。
【００３０】
メモリ３０は、ビット処理ユニット１０-1乃至１０-Mによって算出されるビット情報及びパリティ処理ユニット２０-1乃至２０-mによって算出されるパリティ情報を記憶するのに用いられる。ここでは、メモリ３０は、検査行列Ｈを構成する３×５個（ｎ１×ｍ１個）の順列行列Ｉ1,1，Ｉ2,1，Ｉ3,1，Ｉ1,2，Ｉ2,2，Ｉ3,2，Ｉ1,3，Ｉ2,3，Ｉ3,3，Ｉ1,4，Ｉ2,4，Ｉ3,4，Ｉ1,5，Ｉ2,5及びＩ3,5にそれぞれ対応する３×５個（ｎ１×ｍ１個）のメモリユニットと、５×３個（ｎ２×ｍ２個）の順列行列Ｉ1,6，Ｉ2,6，Ｉ3,6，Ｉ4,6，Ｉ5,6，Ｉ1,7，Ｉ2,7，Ｉ3,7，Ｉ4,7，Ｉ5,7，Ｉ1,8，Ｉ2,8，Ｉ3,8，Ｉ4,8，及びＩ5,8にそれぞれ対応する５×３個（ｎ２×ｍ２個）のメモリユニットから構成されているものとする。この３×５個（ｎ１×ｍ１個）及び５×３個（ｎ２×ｍ２個）のメモリユニットは同時にアクセス可能である。ここで、順列行列Ｉg,hに対応するメモリ３０内の記憶領域の状態を、Ｑg,hまたはＲg,hで表す。Ｑg,hはメモリ３０内の対応する記憶領域にパリティ情報が格納されている状態を表し、Ｒg,hはメモリ３０内の対応する記憶領域にビット情報が格納されている状態を表す。
【００３１】
コントローラ４０は、イレギュラーＬＤＰＣ符号復号器に入力されるイレギュラーＬＤＰＣ符号の復号処理を制御する。具体的には、コントローラ４０は、ビット処理ユニット１０-1乃至１０-M及びパリティ処理ユニット２０-1乃至２０-mの動作を制御するシーケンサとして機能する。
【００３２】
図３は図２中のビット処理ユニット１０-i（ｉ＝１，２，…，Ｍ）の構成を示すブロック図である。上記式（１）で示されるビット更新の処理は、Π操作の部分と、Ψ関数を用いた操作の部分と、Σ操作の部分とに大別される。Ψ( )の操作はルックアップテーブルを用いて実現可能である。そこで、ビット処理ユニット１０-iは、Σ操作の部分に相当する総和計算回路１１０と、Ψ関数を用いた操作の部分に相当するルックアップテーブル（ＬＵＴ）１２０と、Π操作の部分に対応する符号計算回路１３０とから構成される。
【００３３】
さて、Σ操作の部分は、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊにそれぞれ対応するΨ(ｑi,j)の総和を算出するための加算処理の部分と、その総和から当該第ｉ行内の値が“１”の各位置ｊに対応するΨ(ｑi,j)を減じる減算処理の部分とに分解できる。そこで本実施形態では、総和計算回路１１０は、加算回路１１１と、減算回路１１２とから構成される。
【００３４】
加算回路１１１は、１対のレジスタ１１１ａと、マルチプレクサ（ＭＵＸ）１１１ｂ及び１１１ｃと、加算器１１１ｄとから構成される。１対のレジスタ１１１ａは、Ψ(ｑi,j)の総和を算出するための加算処理の中間結果（または最終結果）を保持するのに用いられる。ここで、Ψ(ｑi,j)の総和を算出するための加算処理の最後の中間結果は、当該加算処理の最終結果であり、Ψ(ｑi,j)の総和を示す。１対のレジスタ１１１ａの一方にΨ(ｑi,j)の総和が保持されると、他方のレジスタが、新たなΨ(ｑi,j)の総和を算出するための加算処理の中間結果を保持するのに用いられる。このように、１対のレジスタ１１１ａは、Ψ(ｑi,j)の総和の中間結果を保持するためのレジスタとして、Ψ(ｑi,j)の総和が求められる毎に切り替えて使用される。
【００３５】
マルチプレクサ１１１ｂは、検査行列Ｈの第ｉ行内の値が“１”の各位置（列位置）ｊに対応するΨ(ｑi,j)を順次選択する。検査行列Ｈの第ｉ行内で“１”となる位置ｊは、行毎に一意に定められる。したがって、第ｉ行内で“１”となる位置ｊに対応するΨ(ｑi,j)は、一意に特定できる。マルチプレクサ１１１ｃは、１対のレジスタ１１１ａの一方に保持されている中間結果（前回までの加算処理の結果）の出力を選択する。加算器１１１ｄは、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j)と、マルチプレクサ１１１ｃによって選択された中間結果とを加算する。この加算器１１１ｄの加算結果は、Ψ(ｑi,j)の総和を算出するための加算処理の新たな中間結果を表す。加算器１１１ｄの加算に用いられた、レジスタ１１１ａ内の中間結果は、加算器１１１ｄの加算結果、つまりΨ(ｑi,j)の総和を算出するための加算処理の新たな中間結果に更新される。
【００３６】
このようにして加算回路１１１においては、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するΨ(ｑi,j)がマルチプレクサ１１１ｂによって順次選択される毎に、その選択されたΨ(ｑi,j)とその時点において１対のレジスタ１１１ａの一方に保持されている中間結果（マルチプレクサ１１１ｃによって選択された中間結果）とを加算する動作が実行される。また、加算の都度、その加算に用いられたレジスタ１１１ａ内の中間結果が、その加算の結果である新たな中間結果に更新される。やがて、第ｉ行内の値が“１”の最後の位置ｊに対応するΨ(ｑi,j)と、その時点においてレジスタ１１１ａに保持されている中間結果とが加算されたものとする。明らかなように、この加算の結果は、Ψ(ｑi,j)の総和、即ちＭ(i)に含まれている全てのｊにそれぞれ対応するΨ(ｑi,j)の総和を表す。
【００３７】
上述した加算回路１１１においてΨ(ｑi,j)の総和を算出する動作は、順列行列Ｉg,hの１行の処理、つまり１回の加算処理が１サイクルで実行できるものとすると、ｎ１＋ｎ２（＝８）サイクルで実行できる。ここで、１サイクルの時間をＴcycとすると、Ψ(ｑi,j)の総和は（ｎ１＋ｎ２）Ｔcyc（＝８Ｔcyc）で算出される。
【００３８】
減算回路１１２は、マルチプレクサ（ＭＵＸ）１１２ａ及び１１２ｂと、減算器１１２ｃとから構成される。マルチプレクサ１１２ａは、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するΨ(ｑi,j)の総和が１対のレジスタ１１１ａの一方に保持されたサイクルの次のサイクルから、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するΨ(ｑi,j)を順次選択する。一方、マルチプレクサ１１２ｂは、上記総和が保持されているレジスタ１１１ａの出力、つまり上記総和を選択する。減算器１１２ｃは、マルチプレクサ１１２ｂによって選択された総和からマルチプレクサ１１１ａによって選択されたΨ(ｑi,j)を減算する。これにより、Ｍ(i)＼ｊを満足する全ての位置ｊ'に対応するΨ(ｑi,j')の総和が算出される。この減算器１１２ｃによる、上記総和（一方のレジスタ１１１ａに保持されている総和）からΨ(ｑi,j)を減算する動作は、検査行列Ｈの第ｉ行内の値が“１”の全ての位置ｊに対応するΨ(ｑi,j)について実行される。よって減算回路１１２においては、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊについて、Ｍ(i)＼ｊを満足する全ての位置ｊ'に対応するΨ(ｑi,j')の総和が順次算出される。検査行列Ｈの第ｉ行内の値が“１”の各位置ｊについて、Ｍ(i)＼ｊを満足する全ての位置ｊ'に対応するΨ(ｑi,j')の総和を算出する動作は、ｎ１＋ｎ２（＝８）サイクルで実行できる。この減算回路１１２における減算処理の期間、加算回路１１１における次の加算処理を実行することが可能である。この場合、マルチプレクサ１１１ｃは、先の加算処理の場合と異なって、１対のレジスタ１１１ａのうちの他方のレジスタ（つまり、減算回路１１２における減算処理でマルチプレクサ１１２ｂによって選択されていない方のレジスタ）の出力を選択する。この他方のレジスタの内容が、加算回路１１１内の加算器１１１ｄの加算結果に更新される。但し、加算回路１１１における次の加算処理は、パリティ処理ユニット２０-kによって、第１のパリティ検査行列については第１乃至第ｐ１列内、第２のパリティ検査行列については第１乃至第ｐ２列内の値が“１”の各位置ｉに対応する新たなΨ(ｑi,j)が求められた後に開始される。
【００３９】
ルックアップテーブル１２０は、減算器１１２の減算結果（つまり総和計算回路１１０の計算結果）をΨ関数の演算値、即ちΨ(減算結果)に変換するのに用いられる。ルックアップテーブル１２０は、減算器１１２の減算結果で参照される。この減算結果の示す値をｘとすると、そのｘで特定されるルックアップテーブル１２０のエントリには、そのｘに固有のΨ(ｘ)が予め格納されている。このため、減算器１１２の減算結果ｘでルックアップテーブル１２０を参照するだけで、当該テーブル１２０からΨ(ｘ)を取得することができる。本実施形態では、ｘで指定されるルックアップテーブル１２０のエントリには、Ψ(ｘ)として、Ψ(ｘ)＝−log(tanh(x/2))が格納されている。
【００４０】
符号計算回路１３０は、１対のレジスタ１３１と、マルチプレクサ（ＭＵＸ）１３２及び１３３と、排他的論理和回路１３４と、マルチプレクサ（ＭＵＸ）１３５及び１３６と、排他的論理和回路１３７と、マルチプレクサ（ＭＵＸ）１３８とから構成される。１対のレジスタ１３１は、符号計算の中間結果（または最終結果）を保持するのに用いられる例えば１ビットのレジスタである。１対のレジスタ１３１内の一方に符号計算の最終結果が保持されると、他方のレジスタが、新たな符号計算の中間結果を保持するのに用いられる。
【００４１】
マルチプレクサ１３２は、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するｑi,jのＭＳＢ、つまり符号を順次選択する。ｑi,jのＭＳＢを、ＭＳＢ(ｑi,j)と表現することもある。マルチプレクサ１３３は、１対のレジスタ１１１ａの一方に保持されている前回までの符号計算の中間結果（符号）を選択する。排他的論理和回路１３４は、マルチプレクサ１３２によって選択された符号と、マルチプレクサ１３３によって選択された前回までの符号計算の中間結果（符号）との排他的論理和を取る。この排他的論理和回路１３４の排他的論理和結果は、符号計算の新たな中間結果を表す。排他的論理和回路１３４の演算に用いられた、レジスタ１３１内の中間結果は、排他的論理和回路１３４の排他的論理和結果、つまり符号計算の新たな中間結果に更新される。
【００４２】
このようにして符号計算回路１３０においては、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するＭＳＢ(ｑi,j)がマルチプレクサ１３２によって順次選択される毎に、その選択されたＭＳＢ(ｑi,j)とその時点においてレジスタ１３１に保持されている符号計算の中間結果との排他的論理和を取る演算が実行される。また、排他的論理和演算の都度、その演算に用いられたレジスタ１３１内の中間結果が、その排他的論理和演算の結果である新たな中間結果に更新される。やがて、第ｉ行内の値が“１”の最後の位置ｊに対応するＭＳＢ(ｑi,j)と、その時点においてレジスタ１３１に保持されている中間結果との排他的論理和が取られたものとする。明らかなように、この排他的論理和演算の結果（最終結果）は、第ｉ行内の値が“１”の全ての位置ｊに対応するｑi,jの符号の乗積、即ちＭ(i)に含まれている全てのｊにそれぞれ対応するｑi,jの符号の乗積を表す。上述した符号計算回路１３０においてＭＳＢ(ｑi,j)の排他的論理和を算出する動作、つまり符号計算動作は、加算回路１１１による加算処理と同期して行われ、ｎ１＋ｎ２（＝８）サイクルで実行できる。
【００４３】
マルチプレクサ１３５は、Ｍ(i)に含まれている全てのｊにそれぞれ対応するＭＳＢ(ｑi,j)の排他的論理和（つまり排他的論理和演算の最終結果）が、１対のレジスタ１３１の一方に保持されたサイクルの次のサイクルから、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊに対応するＭＳＢ(ｑi,j)を順次選択する。一方、マルチプレクサ１３６は、上記排他的論理和が保持されているレジスタ１３１の出力、つまり上記排他的論理和を選択する。排他的論理和回路１３７は、マルチプレクサ１３６によって選択された排他的論理和とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j)との排他的論理和を取る。これにより、Ｍ(i)＼ｊを満足する全ての位置ｊ'に対応するｑi,j'の符号の乗積が求められる。この排他的論理和回路１３７による、上記乗積（一方のレジスタ１３１に保持されている乗積）とＭＳＢ(ｑi,j)との排他的論理和を取る演算は、検査行列Ｈの第ｉ行内の値が“１”の全ての位置ｊに対応するＭＳＢ(ｑi,j)について実行される。よって符号計算回路１３０においては、検査行列Ｈの第ｉ行内の値が“１”の各位置ｊについて、Ｍ(i)＼ｊを満足する全ての位置ｊ'に対応するｑi,j'の符号の乗積が順次算出される。マルチプレクサ１３８は、ルックアップテーブル１２０の出力または当該出力の符号を反転した値を、排他的論理和回路１３７の出力に応じてｒi,jとして選択する。
【００４４】
図４は図２中のパリティ処理ユニット２０-k（ｋ＝１，２，…，ｍ）の構成を示すブロック図である。パリティ処理ユニット２０-kは、検査行列Ｈの列ｊ内の“１”の位置（行位置ｉ）に対応するｒi,jを用いて、当該列ｊ内の全てのパリティ更新を同時に行うように構成されている。そのため、パリティ処理ユニット２０-kは、図４に示すように、５つの加算器２０１，２０２，２０３，２０４及び２０５と、５つの減算器２０６，２０７，２０８，２０９及び２１０と、５つのルックアップテーブル（ＬＵＴ）２１１，２１２，２１３，２１４及び２１５とから構成される。
【００４５】
第１のパリティ検査行列に対する処理では、加算器２０１にｒi1,jとｒi2,j、加算器２０２にはｒi3,j（ｒi4,jは“０”）、加算器２０３にはｐj（ｒi5,jは“０”）がそれぞれ入力される。また、第２のパリティ検査行列に対する処理では、加算器２０１にｒi1,jとｒi2,j、加算器２０２にはｒi3,jとｒi4,j、加算器２０３にはｒi5,jとｐjがそれぞれ入力される。
加算器２０１はｒi1,jとｒi2,jとを加算し、加算器２０２はｒi3,jとｒi4,jとを加算し、加算器２０３はｒi5,jとｐjとを加算する。ここで、ｒi1,j，ｒi2,j，ｒi3,j，ｒi4,j及びｒi5,jは、検査行列Ｈの第ｊ列（列ｊ）内で“１”となるビット位置ｉ１，ｉ２，ｉ３，ｉ４，ｉ５に対応するビット情報を表す。今、第１のパリティ検査行列の第ｊ列が３つの順列行列Ｉ1,h，Ｉ2,h及びＩ3,h内に位置しているものとすると、第ｊ列内の“１”となる位置は順列行列Ｉ1,h，Ｉ2,h及びＩ3,h内にそれぞれ１箇所ずつ存在する。つまり、ｒi1,j，ｒi2,j及びｒi3,jは、第１のパリティ検査行列の第ｊ列内で“１”となる、順列行列Ｉ1,h，Ｉ2,h及びＩ3,h内のビット位置に対応するビット情報を表す。第１のパリティ検査行列の第ｊ列内で“１”となるビット位置ｉ１，ｉ２，ｉ３は、行毎に一意に定められる。したがって、第ｊ列内で“１”となるビット位置ｉ１，ｉ２，ｉ３に対応するｒi1,j，ｒi2,j及びｒi3,jは、一意に特定できる。
【００４６】
同様にして、第２のパリティ検査行列の第ｊ列が５つの順列行列Ｉ1,h，Ｉ2,h，Ｉ3,h，Ｉ4,h及びＩ5,h内に位置しているものとすると、第ｊ列内の“１”となる位置は順列行列Ｉ1,h，Ｉ2,h，Ｉ3,h，Ｉ4,h及びＩ5,h内にそれぞれ１箇所ずつ存在する。つまり、ｒi1,j，ｒi2,j，ｒi3,j，ｒi4,j及びｒi5,jは、第２のパリティ検査行列の第ｊ列内で“１”となる、順列行列Ｉ1,h，Ｉ2,h，Ｉ3,h，Ｉ4,h及びＩ5,h内のビット位置に対応するビット情報を表す。第２のパリティ検査行列の第ｊ列内で“１”となるビット位置ｉ１，ｉ２，ｉ３，ｉ４，ｉ５は、行毎に一意に定められる。したがって、第ｊ列内で“１”となるビット位置ｉ１，ｉ２，ｉ３，ｉ４，ｉ５に対応するｒi1,j，ｒi2,j，ｒi3,j，ｒi4,j及びｒi5,jは、一意に特定できる。
【００４７】
加算器２０４は、加算器２０１及び加算器２０２の加算結果を加算する。つまり加算器２０４は、ｒi1,j，ｒi2,j，ｒi3,j及びｒi4,jの総和を算出する。加算器２０５は、加算器２０４及び加算器２０３の加算結果を加算する。つまり加算器２０５は、ｒi1,j，ｒi2,j，ｒi3,j，ｒi4,j及びｒi5,jの総和とｐjとの和を算出する。このように、加算器２０１乃至２０５は、ｒi1,j，ｒi2,j，ｒi3,j，ｒi4,j及びｒi5,jの総和とｐjとの和を算出するための加算回路を構成している。加算器２０５の加算結果は、イレギュラーＬＤＰＣ符号中のビットｘjが１または０である、現時点において推定される確率ｑjを表す。
【００４８】
減算器２０６は、加算器２０５の加算結果からｒi1,jを減じる。この減算器２０６の減算結果は、更新されたパリティ情報ｑi1,jを表す。減算器２０７は、加算器２０５の加算結果からｒi2,jを減じる。この減算器２０７の減算結果は、更新されたパリティ情報ｑi2,jを表す。減算器２０８は、加算器２０５の加算結果からｒi3,jを減じる。この減算器２０８の減算結果は、更新されたパリティ情報ｑi3,jを表す。減算器２０９は、加算器２０５の加算結果からｒi4,jを減じる。この減算器２０９の減算結果は、更新されたパリティ情報ｑi4,jを表す。減算器２１０は、加算器２０５の加算結果からｒi5,jを減じる。この減算器２１０の減算結果は、更新されたパリティ情報ｑi5,jを表す。
【００４９】
つまりパリティ処理ユニット２０-kにおいては、第１のパリティ検査行列の第ｊ列（ｊ＝ｋ，ｐ１＋ｋ，２（ｐ１）＋ｋ，３（ｐ１）＋ｋ，４（ｐ１）＋ｋ）内で“１”のビットに対応する３つのｑi1,j，ｑi2,j及びｑi3,jiを同時に得ることができる。これによりＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j)及びＭＳＢ(ｑi3,ji)も得られる。更に、減算器２０６，２０７及び２０８の減算結果であるｑi1,j，ｑi2,j及びｑi3,jiで、それぞれルックアップテーブル２１１，２１２及び２１３を同時に参照することにより、Ψ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,ji)を同時に得ることができる。Ψ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,j)は、それぞれΨ(ｑi,j)として、ビット処理ユニット１０-iにおけるビット更新に用いられる。
【００５０】
また、パリティ処理ユニット２０-kにおいては、第２のパリティ検査行列の第ｊ列（ｊ＝ｋ，ｐ２＋ｋ，２（ｐ２）＋ｋ）内で“１”のビットに対応する５つのｑi1,j，ｑi2,j，ｑi3,j，ｑi4,j及びｑi5,jiを同時に得ることができる。これによりＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j) ，ＭＳＢ(ｑi3,j) ，ＭＳＢ(ｑi4,j)及びＭＳＢ(ｑi5,ji)も得られる。更に、減算器２０６，２０７，２０８，２０９及び２１０の減算結果であるｑi1,j，ｑi2,j，ｑi3,j，ｑi4,j及びｑi5,jiで、それぞれルックアップテーブル２１１，２１２，２１３，２１４及び２１５を同時に参照することにより、Ψ(ｑi1,j)，Ψ(ｑi2,j) ，Ψ(ｑi3,j) ，Ψ(ｑi4,j)及びΨ(ｑi5,ji)を同時に得ることができる。Ψ(ｑi1,j)，Ψ(ｑi2,j) ，Ψ(ｑi3,j) ，Ψ(ｑi4,j)及びΨ(ｑi5,j)は、それぞれΨ(ｑi,j)として、ビット処理ユニット１０-iにおけるビット更新に用いられる。
【００５１】
本実施形態では、上記したように、パリティ処理ユニット２０-kの出力側にルックアップテーブル２０１，２１２，２１３，２１４及び２１５を備えている。パリティ処理ユニット２０-kの出力側にルックアップテーブル２０１，２１２，２１３，２１４及び２１５を備える代わりに、ビット処理ユニット１０-i内のマルチプレクサ１３２及び１３５の出力側にそれぞれルックアップテーブルを設けることも可能である。この場合、パリティ処理ユニットのルックアップテーブル数は０となるものの、１つのビット処理ユニットにつき（つまり１行の処理当たり）、５つのルックアップテーブルを必要とする。したがって、イレギュラーＬＤＰＣ符号復号器全体では、５×ｐ１ｍ１（＝１５（ｐ１））個のルックアップテーブルを必要とする。これに対して本実施形態では、１つのビット処理ユニット１０-iにつき１つのルックアップテーブルを必要とすると共に、１つパリティ処理ユニット２０-kにつきｍ２個のルックアップテーブルを必要とする。この場合、イレギュラーＬＤＰＣ符号復号器全体では、１×ｐ１ｍ１＋ｍ２×ｐ１＝ｐ１（ｍ１＋ｍ２）（＝８（ｐ１））個のルックアップテーブルだけで済む。つまり、本実施形態においては、パリティ処理ユニット２０-kの出力側にルックアップテーブルを備えることにより、イレギュラーＬＤＰＣ符号復号器全体では、ルックアップテーブルの個数を１５（ｐ１）個から８（ｐ１）個に削減できる。
【００５２】
次に、図２のイレギュラーＬＤＰＣ符号復号器内のコントローラ４０によって制御される、ビット処理ユニット１０-1乃至１０-M及びパリティ処理ユニット２０-1乃至２０-mにおける計算の流れについて、図５、図６及び図７を参照して説明する。図５は、ビット処理ユニット１０-1乃至１０-Mによるビット更新処理（水平計算処理ＨＣＡＬＣ）及びパリティ処理ユニット２０-1乃至２０-mによるパリティ更新処理（垂直計算処理ＶＣＡＬＣ）における、サイクル毎の入出力情報を示す。図６及び図７は、検査行列Ｈを構成する３×５個（ｎ１×ｍ１個）の順列行列と５×３個（ｎ２×ｍ２個）の順列行列にそれぞれ対応するメモリ３０内の領域の状態の遷移を示す。図５乃至図７では、第１のパリティ検査行列における順列行列Ｉg,h（ｇ＝１，２，３、ｈ＝１，２，…，５）と第２のパリティ検査行列における順列行列Ｉg,h（ｇ＝１，２，…，５、ｈ＝６，７，８）内の値が“１”の各ビットに対応するΨ(ｑi,j)及びｒi,jの集合が、それぞれＱg,h及びＲg,hで表されている。Ｑg,hは、ＭＳＢ(ｑi,j)も含む。
【００５３】
＜初期化＞
まずコントローラ４０は、初期化作業として、メモリ３０内の各メモリユニットに、通信チャネルの出力により求められた確率の対数値であるｐjを、Ψ(ｐj)及びｓｇｎ(ｐj)として格納する。即ち本実施形態においては、全てのｊについて、第１のパリティ検査行列についてはΨ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,j)、第２のパリティ検査行列についてはΨ(ｑi1,j)，Ψ(ｑi2,j) ，Ψ(ｑi3,j) ，Ψ(ｑi4,j)及びΨ(ｑi5,j)として、共にΨ(ｐj)の値がセットされる。ｑi1,j，ｑi2,j，ｑi3,j，ｑi4,j及びｑi5,jは、検査行列Ｈの第ｊ列内で“１”となるビット位置ｉ１，ｉ２，ｉ３，ｉ４及びｉ５にそれぞれ対応するパリティ情報ｑi,j（ｉ＝ｉ１，ｉ２，ｉ３，ｉ４，ｉ５）を表す。また、ＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j) ，ＭＳＢ(ｑi3,j) ，ＭＳＢ(ｑi4,j)及びＭＳＢ(ｑi5,j)として、共にｓｇｎ(ｐj)の値がセットされる。またコントローラ４０は、Ｍ個のビット処理ユニット１０-1乃至１０-M内のレジスタ１３１及び１１１ａを、いずれもゼロに初期化する。
【００５４】
＜第１サイクル＞
第１サイクルから第５サイクルまでは、第１のパリティ検査行列に対する処理が実行される。まず、第１サイクルでは、Ｍ個のビット処理ユニット１０-1乃至１０-Mによって加算処理が開始される。即ち、ビット処理ユニット１０-1乃至１０-M内のレジスタ１３１にＭＳＢ(ｑi,j1)が格納され、レジスタ１１１ａにΨ(ｑi,j1)が格納される。ｑi,j1は、検査行列Ｈの第ｉ行内で“１”となる５つのビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちのｊ１に対応するパリティ情報ｑi,j（ｊ＝ｊ１）を表す。つまり、ビット処理ユニット１０-1乃至１０-M内のレジスタ１３１及び１１１ａにそれぞれ格納される情報ＭＳＢ(ｑi,j1)及びΨ(ｑi,j1)は、第１パリティ検査行列の各行内で“１”となる位置のうちの最左端に対応するものであり、メモリ３０に格納されているＱ1,1,Ｑ2,1及びＱ3,1に相当する。
【００５５】
＜第２サイクル＞
第２サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j2)が選択される。そして第２サイクルでは、このΨ(ｑi,j2)を用いて加算回路１１１による加算処理が行われる。即ち、第１サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j2)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j2)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j2)が選択される。第２サイクルでは、このＭＳＢ(ｑi,j2)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第１サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j2)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j2)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j2)及びＭＳＢ(ｑi,j2)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの２番目のビット位置ｊ２（ｊ＝ｊ２）に対応するものであり、メモリ３０に格納されているＱ1,2,Ｑ2,2及びＱ3,2に相当する。
【００５６】
＜第３サイクル＞
第３サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j3)が選択される。そして第３サイクルでは、このΨ(ｑi,j3)を用いて加算回路１１１による加算処理が行われる。即ち、第２サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j3)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j3)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j3)が選択される。第３サイクルでは、このＭＳＢ(ｑi,j3)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第２サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j3)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j3)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j3)及びＭＳＢ(ｑi,j3)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの３番目のビット位置ｊ３（ｊ＝ｊ３）に対応するものであり、メモリ３０に格納されているＱ1,3,Ｑ2,3及びＱ3,3に相当する。
【００５７】
＜第４サイクル＞
第４サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j4)が選択される。そして第４サイクルでは、このΨ(ｑi,j4)を用いて加算回路１１１による加算処理が行われる。即ち、第３サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j4)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j4)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j4)が選択される。第４サイクルでは、このＭＳＢ(ｑi,j4)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第３サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j4)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j4)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j4)及びＭＳＢ(ｑi,j4)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの４番目のビット位置ｊ４（ｊ＝ｊ４）に対応するものであり、メモリ３０に格納されているＱ1,4,Ｑ2,4及びＱ3,4に相当する。
【００５８】
＜第５サイクル＞
第５サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j5)が選択される。そして第５サイクルでは、このΨ(ｑi,j5)を用いて加算回路１１１による加算処理が行われる。即ち、第４サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j5)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j5)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j5)が選択される。第５サイクルでは、このＭＳＢ(ｑi,j5)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第４サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j5)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j5)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j5)及びＭＳＢ(ｑi,j5)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの５番目のビット位置ｊ５（ｊ＝ｊ５）に対応するものであり、メモリ３０に格納されているＱ1,5,Ｑ2,5及びＱ3,5に相当する。
【００５９】
＜第６サイクル＞
第６サイクルから第８サイクルまでは、第２のパリティ検査行列に対する処理が実行される。第６サイクルでは、第１のパリティ検査行列と同様にして、Ｍ個のビット処理ユニット１０-1乃至１０-Mによって加算処理が開始される。即ち、ビット処理ユニット１０-1乃至１０-M内のレジスタ１３１にＭＳＢ(ｑi,j6)が格納され、レジスタ１１１ａにΨ(ｑi,j6)が格納される。ｑi,j6は、第２のパリティ検査行列の第ｉ行内で“１”となる３つのビット位置ｊ６，ｊ７，ｊ８のうちのｊ６に対応するパリティ情報ｑi,j（ｊ＝ｊ６）を表す。つまり、ビット処理ユニット１０-1乃至１０-M内のレジスタ１３１及び１１１ａにそれぞれ格納される情報ＭＳＢ(ｑi,j6)及びΨ(ｑi,j6)は、検査行列Ｈの各行内で“１” となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの６番目に対応するものであり、メモリ３０に格納されているＱ1,6,Ｑ2,6,Ｑ3,6,Ｑ4,6及びＱ5,6に相当する。
【００６０】
＜第７サイクル＞
第７サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j7)が選択される。そして第７サイクルでは、このΨ(ｑi,j7)を用いて加算回路１１１による加算処理が行われる。即ち、第６サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j7)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j7)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j7)が選択される。第７サイクルでは、このＭＳＢ(ｑi,j7)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第１サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j7)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j7)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j7)及びＭＳＢ(ｑi,j7)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの７番目のビット位置ｊ７（ｊ＝ｊ７）に対応するものであり、メモリ３０に格納されているＱ1,7,Ｑ2,7,Ｑ3,7,Ｑ4,7及びＱ5,7に相当する。
【００６１】
＜第８サイクル＞
第８サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j8)が選択される。そして第８サイクルでは、このΨ(ｑi,j8)を用いて加算回路１１１による加算処理が行われる。即ち、第７サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j8)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j8)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j8)が選択される。第８サイクルでは、このＭＳＢ(ｑi,j8)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第７サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j8)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j8)との排他的論理和演算結果は（排他的論理和演算の最終結果）、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j8)及びＭＳＢ(ｑi,j8)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの８番目のビット位置ｊ８（ｊ＝ｊ８）に対応するものであり、メモリ３０に格納されているＱ1,8,Ｑ2,8,Ｑ3,8,Ｑ4,8及びＱ5,8に相当する。
【００６２】
＜第９サイクル＞
第９サイクルでは、ビット処理ユニット１０-1乃至１０-M内の減算回路１１２による減算処理が開始される。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（つまりビット処理ユニット１０-iにおいては、検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,1，Ｑ2,1及びＱ3,1とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j1)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j1)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j1)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００６３】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j1)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j1)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j1)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、第１のパリティ検査行列の第１列乃至第ｐ１列に対応する順列行列Ｉ1,1，Ｉ2,1，及びＩ3,1内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,1，Ｒ2,1，及びＲ3,1で表す。この場合、第９サイクルでは、Ｒ1,1，Ｒ2,1，及びＲ3,1が生成されて、メモリ３０に格納されることになる（図６（Ｂ））。
【００６４】
＜第１０サイクル＞
第１０サイクルでは、ビット処理ユニット１０-1乃至１０-M内の減算回路１１２による減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,2，Ｑ2,2及びＱ3,2とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j2)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j2)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j2)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００６５】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j2)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j2)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j2)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、第１のパリティ検査行列の第（ｐ１＋１）列乃至第２（ｐ１）列に対応する順列行列Ｉ1,2，Ｉ2,2，及びＩ3,2内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,2，Ｒ2,2，及びＲ3,2で表す。この場合、第１０サイクルでは、Ｒ1,2，Ｒ2,2，及びＲ3,2が生成されて、メモリ３０に格納されることになる（図６(Ｃ)）。
【００６６】
さて、第１０サイクルでは、第９サイクルでメモリ３０に格納されたＲ1,1，Ｒ2,1，及びＲ3,1内の各要素ｒi,jを利用することができる。このため第１０サイクルでは、コントローラ４０の制御によって、パリティ処理ユニット２０-1乃至２０-mによるパリティ更新処理が開始される。即ち第１０サイクルでは、Ｒ1,1，Ｒ2,1，及びＲ3,1内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、第１のパリティ検査行列における第１列乃至第ｐ１列の各列毎に、Ψ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,ji)と、ＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j)及びＭＳＢ(ｑi3,ji)と、ｑjとが求められる。この第１列乃至第ｍ列の各列毎のΨ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,ji)とＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j)及びＭＳＢ(ｑi3,ji)とｑjとによって、メモリ３０に格納されているＱ1,1，Ｑ2,1及びＱ3,1がそれぞれＱ'1,1，Ｑ'2,1及びＱ'3,1に更新される（図６（Ｃ））。
【００６７】
このように本実施形態では、パリティ更新処理を、第１のパリティ検査行列における第１行乃至第Ｍ行の各行内の全ビットに対応するビット更新処理が完了する前に開始できる。即ち本実施形態では、第１パリティ検査行列内の順列行列Ｉ1,1，Ｉ2,1，及びＩ3,1内の値が“１”の各ビット位置に対応するビット更新のみが終了した段階でパリティ更新処理を開始できる。換言するならば、本実施形態によれば、ビット更新とパリティ更新とをパイプラインで処理することができる。
【００６８】
＜第１１サイクル＞
第１１サイクルでは、更新されたＱ'1,1，Ｑ'2,1及びＱ'3,1内の各要素ｑi,jを利用することができる。このため第１１サイクルでは、コントローラ４０の制御によって、ビット処理ユニット１０-1乃至１０-Mによる次のビット更新処理が開始され、上記第１サイクルと同様の加算処理が行われる。但し、この加算処理の結果は、上記第１サイクル（乃至第８サイクル）における加算処理の結果を保持するのに用いられた上記一方のレジスタではなく、１対のレジスタ１１１ａのうちの他方のレジスタに保持される。
【００６９】
このように本実施形態では、ビット更新処理を、第１のパリティ検査行列における第１列乃至第Ｎ列の各列内の全ビットに対応するパリティ更新処理が完了する前に開始できる。即ち本実施形態では、第１のパリティ検査行列内の順列行列Ｉ1,1，Ｉ2,1，及びＩ3,1内の各ビット位置に対応するパリティ更新のみが終了した段階で次のビット更新処理を開始できる。換言するならば、ビット更新処理とパリティ更新処理との対をパイプラインで反復することができる。
【００７０】
また、第１１サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,3，Ｑ2,3及びＱ3,3とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j3)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j3)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j3)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００７１】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j3)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j3)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j3)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（２（ｐ１）＋１）列乃至第３（ｐ１）列に対応する順列行列Ｉ1,3，Ｉ2,3，及びＩ3,3内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,3，Ｒ2,3，及びＲ3,3で表す。この場合、第１１サイクルでは、Ｒ1,3，Ｒ2,3，及びＲ3,3が生成されて、メモリ３０に格納されることになる（図６（Ｄ））。
【００７２】
また、第１１サイクルでは、第１０サイクルでメモリ３０に格納されたＲ1,2，Ｒ2,2，及びＲ3,2内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,2，Ｑ2,2及びＱ3,2がそれぞれＱ'1,2，Ｑ'2,2及びＱ'3,2に更新される（図６（Ｄ））。
【００７３】
＜第１２サイクル＞
第１２サイクルでは、更新されたＱ'1,2，Ｑ'2,2及びＱ'3,2を用いて、上記第２サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００７４】
また、第１２サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,4，Ｑ2,4及びＱ3,4とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j4)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j4)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j4)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００７５】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j4)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j4)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j4)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（３（ｐ１）＋１）列乃至第４（ｐ１）列に対応する順列行列Ｉ1,4，Ｉ2,4，及びＩ3,4内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,4，Ｒ2,4，及びＲ3,4で表す。この場合、第１２サイクルでは、Ｒ1,4，Ｒ2,4，及びＲ3,4が生成されて、メモリ３０に格納されることになる（図６（Ｅ））。
【００７６】
また、第１２サイクルでは、第１１サイクルでメモリ３０に格納されたＲ1,3，Ｒ2,3，及びＲ3,3内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,3，Ｑ2,3及びＱ3,3がそれぞれＱ'1,3，Ｑ'2,3及びＱ'3,3に更新される（図６（Ｅ））。
【００７７】
＜第１３サイクル＞
第１３サイクルでは、更新されたＱ'1,3，Ｑ'2,3及びＱ'3,3を用いて、上記第３サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００７８】
また、第１３サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,5，Ｑ2,5及びＱ3,5とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j5)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j5)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j5)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００７９】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j5)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j5)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j5)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（４（ｐ１）＋１）列乃至第５（ｐ１）列に対応する順列行列Ｉ1,5，Ｉ2,5，及びＩ3,5内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,5，Ｒ2,5，及びＲ3,5で表す。この場合、第１３サイクルでは、Ｒ1,5，Ｒ2,5，及びＲ3,5が生成されて、メモリ３０に格納されることになる（図７（Ｆ））。
【００８０】
また、第１３サイクルでは、第１２サイクルでメモリ３０に格納されたＲ1,4，Ｒ2,4，及びＲ3,4内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,4，Ｑ2,4及びＱ3,4がそれぞれＱ'1,4，Ｑ'2,4及びＱ'3,4に更新される（図７（Ｆ））。
【００８１】
＜第１４サイクル＞
第１４サイクルでは、更新されたＱ'1,4，Ｑ'2,4及びＱ'3,4を用いて、上記第４サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００８２】
また、第１４サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,6，Ｑ2,6，Ｑ3,6，Ｑ4,6及びＱ5,6とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j6)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j6)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j6)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００８３】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j6)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j6)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j6)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（５（ｐ１）＋１）列乃至第（５（ｐ１）＋ｐ２）列に対応する順列行列Ｉ1,6，Ｉ2,6，Ｉ3,6，Ｉ4,6及びＩ5,6内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,6，Ｒ2,6，Ｒ3,6，Ｒ4,6及びＲ5,6で表す。この場合、第１４サイクルでは、Ｒ1,6，Ｒ2,6，Ｒ3,6，Ｒ4,6及びＲ5,6が生成されて、メモリ３０に格納されることになる（図７（Ｇ））。
【００８４】
また、第１４サイクルでは、第１３サイクルでメモリ３０に格納されたＲ1,5，Ｒ2,5，及びＲ3,5内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,5，Ｑ2,5及びＱ3,5がそれぞれＱ'1,5，Ｑ'2,5及びＱ'3,5に更新される（図７（Ｇ））。
【００８５】
＜第１５サイクル＞
第１５サイクルでは、更新されたＱ'1,5，Ｑ'2,5及びＱ'3,5を用いて、上記第５サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００８６】
また、第１５サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,７，Ｑ2,７，Ｑ3,７，Ｑ4,７及びＱ5,７とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j７)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j７)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j７)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００８７】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j７)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j７)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j７)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（５（ｐ１）＋２ｐ＋１）列乃至第（５（ｐ１）＋２（２ｐ）列に対応する順列行列Ｉ1,7，Ｉ2,7，Ｉ3,7，Ｉ4,7及びＩ5,7内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,7，Ｒ2,7，Ｒ3,7，Ｒ4,7及びＲ5,7で表す。この場合、第１５サイクルでは、Ｒ1,7，Ｒ2,7，Ｒ3,7，Ｒ4,7及びＲ5,7が生成されて、メモリ３０に格納されることになる（図７（Ｈ））。
【００８８】
また、第１５サイクルでは、第１４サイクルでメモリ３０に格納されたＲ1,６，Ｒ2,６，Ｒ23,６，Ｒ4,6及びＲ5,6内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,6，Ｑ2,6，Ｑ3,6，Ｑ4,6及びＱ5,6がそれぞれＱ'1,6，Ｑ'2,6，Ｑ'3,6，Ｑ'4,6及びＱ'5,6に更新される（図７（Ｈ））。
【００８９】
＜第１６サイクル＞
第１６サイクルでは、更新されたＱ'1,6，Ｑ'2,6，Ｑ'3,6，Ｑ'4,6及びＱ'5,6を用いて、上記第６サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００９０】
また、第１６サイクルでは、上記加算処理と並行して、ビット処理ユニット１０-1乃至１０-Mによる減算処理が行われる。この減算処理には、各ビット処理ユニット１０-i（ｉ＝１，２，…Ｍ）内の上記一方のレジスタ１１１ａに保持されている加算処理の最終結果（検査行列Ｈの第ｉ行内で値が“１”となる位置に対応するΨ(ｑi,j)の総和）と、メモリ３０に格納されているＱ1,8，Ｑ2,8，Ｑ3,8，Ｑ4,8及びＱ5,8とが用いられる。この減算処理では、上記加算処理の最終結果からΨ(ｑi,j8)が減じられる。そのため、減算回路１１２内のマルチプレクサ１１２ｂでは、１対のレジスタ１１１ａのうち、加算処理の最終結果を保持しているものが選択される。また、減算回路１１２内のマルチプレクサ１１２ａでは、Ψ(ｑi,j8)が選択される。そして、マルチプレクサ１１２ｂによって選択された加算処理の最終結果から、マルチプレクサ１１２ａによって選択されたΨ(ｑi,j8)が、減算回路１１２内の減算器１１２ｃによって減じられる。
【００９１】
一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、排他的論理和の最終結果からＭＳＢ(ｑi,j8)を除外する演算が行われる。そのため、符号計算回路１３０内のマルチプレクサ１３６では、１対のレジスタ１３１のうち、排他的論理和の最終結果を保持しているものが選択される。また、符号計算回路１３０内のマルチプレクサ１３５では、ＭＳＢ(ｑi,j8)が選択される。そして、マルチプレクサ１３６によって選択された排他的論理和の最終結果とマルチプレクサ１３５によって選択されたＭＳＢ(ｑi,j8)との排他的論理和演算が、符号計算回路１３０内の排他的論理和回路１３７によって行われる。この排他的論理和回路１３７の演算結果に従って、マルチプレクサ１３８において出力される情報の符号が決定され、ビット情報ｒi,jが求められる。このビット情報ｒi,jは、対応する行ｉ及び列ｊの位置で決まるメモリ３０の位置に格納される。ここで、検査行列Ｈの第（５（ｐ１）＋２（ｐ２）＋１）列乃至第（５（ｐ１）＋３（ｐ２））列に対応する順列行列Ｉ1,8，Ｉ2,8，Ｉ3,8，Ｉ4,8及びＩ5,8内の値が“１”の各ビット位置に対応するｒi,jの集合を、それぞれＲ1,8，Ｒ2,8，Ｒ3,8，Ｒ4,8及びＲ5,8で表す。この場合、第１６サイクルでは、Ｒ1,8，Ｒ2,8，Ｒ3,8，Ｒ4,8及びＲ5,8が生成されて、メモリ３０に格納されることになる（図７（Ｉ））。
【００９２】
また、第１６サイクルでは、第１５サイクルでメモリ３０に格納されたＲ1,7，Ｒ2,7，Ｒ3,7，Ｒ4,7及びＲ5,7内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-p2によって行われる。これにより、メモリ３０に格納されているＱ1,7，Ｑ2,7，Ｑ3,7，Ｑ4,7及びＱ5,7がそれぞれＱ'1,7，Ｑ'2,7，Ｑ'3,7，Ｑ'4,7及びＱ'5,7に更新される（図７（Ｉ））。
【００９３】
＜第１７サイクル＞
第１７サイクルでは、更新されたＱ'1,7，Ｑ'2,7，Ｑ'3,7，Ｑ'4,7及びＱ'5,7を用いて、上記第７サイクルと同様の加算処理がビット処理ユニット１０-1乃至１０-Mによって行われる。
【００９４】
また、第１７サイクルでは、第１６サイクルでメモリ３０に格納されたＲ1,7，Ｒ2,7，Ｒ3,7，Ｒ4,7及びＲ5,7内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-p2によって行われる。これにより、メモリ３０に格納されているＱ1,8，Ｑ2,8，Ｑ3,8，Ｑ4,8及びＱ5,8がそれぞれＱ'1,8，Ｑ'2,8，Ｑ'3,8，Ｑ'4,8及びＱ'5,8に更新される。
【００９５】
以上のようにして、ビット更新処理とパリティ更新処理とからなる１回目の反復動作が完了する。但し、次の２回目の反復動作におけるビット更新処理は、既に第１１サイクル（つまり先行する１回目の反復動作におけるパリティ更新処理が開始されたサイクルの次のサイクル）から開始されている。
【００９６】
このように本実施形態では、検査行列Ｈにおける第１行乃至第Ｍ行の各行内の値が“１”のビットに対応するビット更新を、１６サイクル、つまり２（ｎ１）＋２（ｎ２）サイクルで実行できる。
【００９７】
第１８サイクル以降も上記第１２サイクル以降と同様の動作が行われる。なお、ビット更新処理とパリティ更新処理との反復動作は、検査行列Ｈの全ての列ｊ（ｊ＝１，２，…，Ｎ）について、その列ｊに対応する第１のパリティ検査行列ではｍ１（＝３）個、第２のパリティ検査行列ではｍ２（＝５）個のｑjに基づいて判定される硬判定値が第ｊパリティチェック方程式を満足するようになるまで行われる。但し、一定回数の反復動作を実行しても、パリティチェック方程式を満足しない列が１つでも存在する場合には、イレギュラーＬＤＰＣ符号の復号に失敗したとして、復号動作は強制終了される。
【００９８】
上記実施形態では、パリティ処理ユニット２０-kは、検査行列Ｈの列ｊ内の“１”の位置（行位置ｉ）に対応するｒi,jを用いて、当該列ｊ内の全てのパリティ更新を同時に行うように構成されている。しかし、パリティ処理ユニット２０-kに代えて、ビット処理ユニット１０-iと同様の構成を有するパリティ処理ユニットを用いても良い。つまり、加算処理と減算処理とにより、２サイクルで、検査行列Ｈの列ｊ内の各行位置ｉに対応するパリティ情報ｑi,jを順次更新する構成とすることも可能である。この場合、パリティ処理ユニットの出力側に１つのルックアップテーブルを設けるだけで済む。但し、パリティ更新処理に必要なサイクル数が、パリティ処理ユニット２０-kを用いる場合の２倍となる。また、次のビット更新処理の開始時期が１サイクル遅くなる。
【００９９】
また上記実施形態では、検査行列Ｈが３×５の第１の順列行列と５×３の第２の順列行列を含むアレイ構成である場合を想定している。しかし、検査行列Ｈ内の順列行列の配列は上記実施形態に限らない。即ち、検査行列Ｈは、ｐ１×ｐ１の第１の順列行列がｎ１×ｍ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｎ２×ｍ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列とし、ｐ１×ｎ１＝ｐ２×ｎ２の条件を満たせば良い。
【０１００】
なお、本発明は、上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合せにより種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。
【図面の簡単な説明】
【０１０１】
【図１】本発明の一実施形態で適用されるイレギュラーパリティ検査行列Ｈの構造を示す図。
【図２】本発明の一実施形態に係るイレギュラーＬＤＰＣ符号復号器の構成を示すブロック図。
【図３】図２中のビット処理ユニット１０-i（ｉ＝１，２，…，Ｍ）の構成を示すブロック図。
【図４】図２中のパリティ処理ユニット２０-k（ｋ＝１，２，…，ｐ１）の構成を示すブロック図。
【図５】ビット処理ユニット１０-1乃至１０-Mによるビット更新処理及びパリティ処理ユニット２０-1乃至２０-mによるパリティ更新処理における、サイクル毎の入出力情報を示す図。
【図６】検査行列Ｈを構成する３×５個（ｎ１×ｍ１個）の第１の順列行列と５×３個（ｎ２×ｍ２個）の第２の順列行列にそれぞれ対応するメモリ３０内の領域の状態の遷移を示す図。
【図７】検査行列Ｈを構成する３×５個（ｎ１×ｍ１個）の第１の順列行列と５×３個（ｎ２×ｍ２個）の第２の順列行列にそれぞれ対応するメモリ３０内の領域の状態の遷移を示す図。
【符号の説明】
【０１０２】
１０-1〜１０-M，１０-i…ビット処理ユニット、２０-1〜２０-N，２０-k…パリティ処理ユニット、３０…メモリ、４０…コントローラ、１１０…総和計算回路、１１１…加算回路、１１２…減算回路、１２０…ルックアップテーブル（第１のルックアップテーブル）、１３０…符号計算回路、２０７〜２０９…ルックアップテーブル（第２のルックアップテーブル）。
【図１】
2006339799.tif 000005
【図２】
2006339799.tif 000006
【図３】
2006339799.tif 000007
【図４】
2006339799.tif 000008
【図５】
2006339799.tif 000009
【図６】
2006339799.tif 000010
【図７】
2006339799.tif 000011
【手続補正書】
【提出日】平成18年5月26日(2006.5.26)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
ｐ１×ｐ１の第１の順列行列がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を復号するイレギュラー低密度パリティチェック符号復号器であって、
前記第１のパリティ検査行列及び前記第２のパリティ検査行列の各行に対応して設けられ、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を実行するｐ１ｍ１個のビット処理ユニットと、
前記ｍ１×ｎ１に配列されたｍ１ｎ１個の前記第１の順列行列及び前記ｍ２×ｎ２に配列されたｍ２ｎ２個の前記第２の順列行列に共通に、且つｐ２よりも大きいｐ１の前記第１の順列行列の各列に対応して設けられ、前記第１の順列行列と前記第２の順列行列の当該列が属する前記パリティ検査行列の列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を実行するｐ１個のパリティ処理ユニットと、
前記ｐ１ｍ１個のビット処理ユニットによるビット更新処理が前記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する前記第１のパリティ検査行列のｐ１列に対応するパリティ更新処理を前記ｐ１個のパリティ処理ユニットにより実行させ、前記ｐ１個のパリティ処理ユニットによるパリティ更新処理が前記第１のパリティ検査行列の最初のｐ１列について終了した場合に、前記ｐ１ｍ１個のビット処理ユニットによる次のビット更新処理を開始させ、前記ｐ２ｍ２個のビット処理ユニットによるビット更新処理が前記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する前記第２のパリティ検査行列のｐ２列に対応するパリティ更新処理を前記ｐ２個のパリティ処理ユニットにより実行させ、前記ｐ２個のパリティ処理ユニットによるパリティ更新処理が前記第２のパリティ検査行列の最初のｐ２列について終了した場合に、前記ｐ２ｍ２個のビット処理ユニットによる次のビット更新処理を開始させるコントローラと
を具備することを特徴とするイレギュラー低密度パリティチェック符号復号器。
【請求項２】
前記第１のパリティ検査行列と前記第２のパリティ検査行列とは、ｐ１×ｍ１＝ｐ２×ｍ２の条件を満たすことを特徴とする請求項１記載のイレギュラー低密度パリティチェック符号復号器。
【請求項３】
前記ｐ１ｍ１個のビット処理ユニットの各々は、
前記第１のパリティ検査行列または前記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を順次加算する加算処理により、そのパリティ情報の値の総和を計算する加算回路と、
前記加算回路によって計算された総和から前記第１のパリティ検査行列または前記第２のパリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を減じる減算処理を実行する減算回路とを含む
ことを特徴とする請求項１記載のイレギュラー低密度パリティチェック符号復号器。
【請求項４】
前記コントローラは、前記ｐ１ｍ１個のビット処理ユニットにそれぞれ含まれている前記減算回路による減算処理が、前記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、前記ビット更新処理が当該ｐ１個の列位置について終了したとして、そのｐ１個の列位置が属するｐ１列に対応するパリティ更新処理を前記ｐ１個のパリティ処理ユニットにより実行させ、前記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、前記ビット更新処理が当該ｐ２個の列位置について終了したとして、そのｐ２個の列位置が属するｐ２列に対応するパリティ更新処理を前記ｐ２個のパリティ処理ユニットにより実行させることを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項５】
前記ｐ１ｍ１個のビット処理ユニットの各々は、前記減算回路の出力を確率演算のための特定の関数の演算値に変換する第１のルックアップテーブルを含み、
前記ｐ１個のパリティ処理ユニットの各々は、その出力側に、更新されたパリティ情報の値を前記特定の関数の演算値に変換する第２のルックアップテーブルを含む
ことを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項６】
前記第１のパリティ検査行列内の前記ｍ１ｎ１個の順列行列の配列ｍ１×ｎ１はｍ１＜ｎ１の関係があり、
前記ｐ１個のパリティ処理ユニットの各々は、前記第１のパリティ検査行列の対応する列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力し、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新し、
前記第２のパリティ検査行列内の前記ｍ２ｎ２個の順列行列の配列ｍ２×ｎ２はｎ２＜ｍ２の関係があり、
前記ｐ２個のパリティ処理ユニットの各々は、前記第２のパリティ検査行列の対応する列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力し、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新することを特徴とする請求項３記載のイレギュラー低密度パリティチェック符号復号器。
【請求項７】
前記ｐ１ｍ１個のビット処理ユニットの各々は、前記減算回路の出力を確率演算のための特定の関数の演算値に変換する第１のルックアップテーブルを含み、
前記ｐ１個のパリティ処理ユニットの各々は、その出力側に、更新されたｍ２個のパリティ情報の値を前記特定の関数の演算値に変換するｍ２個の第２のルックアップテーブルを含む
ことを特徴とする請求項６記載のイレギュラー低密度パリティチェック符号復号器。
【請求項８】
ｐ１×ｐ１の第１の順列行列がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる、ｐ１×ｍ１＝ｐ２×ｍ２の条件を満たす連接行列を検査行列とするイレギュラー低密度パリティチェック符号を復号するイレギュラー低密度パリティチェック符号復号器。
【請求項９】
ｐ１×ｐ１の第１の順列行列がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を復号する低密度パリティチェック符号復号方法であって、
前記第１のパリティ検査行列及び前記第２のパリティ検査行列の各行毎に、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を並行して実行するビット更新ステップと、
前記第１のパリティ検査行列に対してはｐ１列を単位にし、前記第２のパリティ検査行列に対してはｐ２列を単位にして、その列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を並行して実行するパリティ更新ステップと、
前記ビット更新ステップによるビット更新処理が前記第１のパリティ検査行列の各行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する前記第１のパリティ検査行列のｐ１列に対応する前記パリティ更新ステップによるパリティ更新処理を実行させるステップと、
前記パリティ更新ステップによるパリティ更新処理が前記第１のパリティ検査行列の最初のｐ１列について終了した場合に、前記ビット処理ステップによる次のビット更新処理を開始させるステップと、
前記ビット更新ステップによるビット更新処理が前記第２のパリティ検査行列の各行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する前記第２のパリティ検査行列のｐ２列に対応する前記パリティ更新ステップによるパリティ更新処理を実行させるステップと、
前記パリティ更新ステップによるパリティ更新処理が前記第２のパリティ検査行列の最初のｐ２列について終了した場合に、前記ビット処理ステップによる次のビット更新処理を開始させるステップと
を具備することを特徴とする低密度パリティチェック符号復号方法。
【請求項１０】
前記ビット更新ステップは、
前記パリティ検査行列の各行毎に、当該行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を順次加算する加算処理を並行して実行することにより、前記パリティ検査行列の各行毎にパリティ情報の値の総和を計算する加算ステップと、
前記加算ステップによって計算された前記パリティ検査行列の各行毎の総和から、それぞれ前記パリティ検査行列の対応する行内の値が“１”の各列位置に対応する対数表現されたパリティ情報の値を減じる減算処理を並行して実行する減算ステップとを含む
ことを特徴とする請求項９記載の低密度パリティチェック符号復号方法。
【請求項１１】
前記ビット更新ステップは、前記減算ステップにおける前記各行毎の減算処理の結果を、当該各行毎に設けられた第１のルックアップテーブルにより確率演算のための特定の関数の演算値に変換するステップを含み、
前記パリティ更新ステップは、前記第１のパリティ検査行列のｐ１列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、及び前記第２のパリティ検査行列のｐ２列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、その更新されたパリティ情報の値を、当該ｐ２行の各行毎に設けられた第２のルックアップテーブルにより前記特定の関数の演算値に変換するステップを含む
ことを特徴とする請求項１０記載の低密度パリティチェック符号復号方法。
【請求項１２】
前記第１のパリティ検査行列内の前記ｍ１ｎ１個の順列行列の配列ｍ１×ｎ１はｍ１＜ｎ１の関係があり、前記第２のパリティ検査行列内の前記ｍ２ｎ２個の順列行列の配列ｍ２×ｎ２はｎ２＜ｍ２の関係があり、
前記パリティ更新ステップは、
前記第１のパリティ検査行列のｐ１列を単位に、その列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力するステップと、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新するステップと、
前記第２のパリティ検査行列のｐ２列を単位に、その列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力するステップと、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新するステップと
を含む
ことを特徴とする請求項１０記載の低密度パリティチェック符号復号方法。
【請求項１３】
前記ビット更新ステップは、前記減算ステップにおける前記各行毎の減算処理の結果を、当該各行毎に設けられた第１のルックアップテーブルにより確率演算のための特定の関数の演算値に変換するステップを含み、
前記パリティ更新ステップは、前記第１のパリティ検査行列のｐ１列を単位とするパリティ更新処理により、そのｐ１列の各列毎に、その列内の値が“１”のｒ個の行位置に対応するパリティ情報が更新される都度、及び前記第２のパリティ検査行列のｐ２列を単位とするパリティ更新処理により、その列内の値が“１”の各行位置に対応するパリティ情報が更新される都度、そのｐ１列またはｐ２列の各列毎に更新されたｍ１個またはｍ２個のパリティ情報の値を、当該ｐ２行の各行毎に設けられたｍ２個の第２のルックアップテーブルにより前記特定の関数の演算値に同時に変換するステップを含む
ことを特徴とする請求項１２記載の低密度パリティチェック符号復号方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】０００５
【補正方法】変更
【補正の内容】
【０００５】
本発明の１つの観点によれば、ｐ１×ｐ１の第１の順列行列がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２（ｐ１＞ｐ２）の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラーＬＤＰＣ符号（イレギュラー低密度パリティチェック符号）を復号するイレギュラーＬＤＰＣ符号復号器が提供される。このイレギュラーＬＤＰＣ符号復号器は、上記パリティ検査行列の各行に対応して設けられ、当該行内の値が“１”の各列位置に対応するビット情報を順次更新するためのビット更新処理を実行するｐ１ｍ１個のビット処理ユニットと、上記ｍ１×ｎ１に配列されたｍ１ｎ１個の順列行列及び前記ｍ２×ｎ２に配列されたｍ２ｎ２個の前記第２の順列行列に共通に、且つｐ２よりも大きいｐ１の前記第１の順列行列の各列に対応して設けられ、前記第１の順列行列と前記第２の順列行列の当該列が属する上記パリティ検査行列の列内の値が“１”の各行位置に対応するパリティ情報を更新するためのパリティ更新処理を実行するｐ１個のパリティ処理ユニットと、上記ｐ１ｍ１個のビット処理ユニットによるビット更新処理が上記第１のパリティ検査行列の対応する行内のｐ１個の列位置について終了する毎に、そのｐ１個の列位置が属する第１のパリティ検査行列のｐ１列に対応するパリティ更新処理を上記ｐ１個のパリティ処理ユニットにより実行させ、上記ｐ１個のパリティ処理ユニットによるパリティ更新処理が上記第１のパリティ検査行列の最初のｐ１列について終了した場合に、上記ｐ１ｍ１個のビット処理ユニットによる新たなビット更新処理を開始させ、上記ｐ２ｍ２個のビット処理ユニットによるビット更新処理が上記第２のパリティ検査行列の対応する行内のｐ２個の列位置について終了する毎に、そのｐ２個の列位置が属する第２のパリティ検査行列のｐ２列に対応するパリティ更新処理を上記ｐ２個のパリティ処理ユニットにより実行させ、上記ｐ２個のパリティ処理ユニットによるパリティ更新処理が上記第２のパリティ検査行列の最初のｐ２列について終了した場合に、上記ｐ２ｍ２個のビット処理ユニットによる次のビット更新処理を開始させるコントローラとを備えることを特徴とする。
【手続補正３】
【補正対象書類名】明細書
【補正対象項目名】０００６
【補正方法】変更
【補正の内容】
【０００６】
このように、上記イレギュラーＬＤＰＣ符号復号器は、ＬＤＰＣ符号のパリティ検査行列が、ｐ１×ｐ１の第１の順列行列をｍ１×ｎ１に配列した構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列を持つイレギュラー低密度パリティチェック符号を前提として構成されている。特に、第１のパリティ検査行列と第２のパリティ検査行列とは、ｐ１×ｍ１＝ｐ２×ｍ２の条件を満たすことが好ましい。
【手続補正４】
【補正対象書類名】明細書
【補正対象項目名】００１１
【補正方法】変更
【補正の内容】
【００１１】
また、上記第１のパリティ検査行列内の上記ｍ１ｎ１個の順列行列の配列ｍ１×ｎ１がｍ１＜ｎ１の関係にある場合に、上記ｐ１個のパリティ処理ユニットの各々が、上記第１のパリティ検査行列の対応する列内の値が“１”のｍ１個の行位置に対応するビット情報を同時に入力し、当該ｍ１個の行位置に対応するビット情報をもとに当該ｍ１個の行位置に対応するパリティ情報を同時に更新し、上記第２のパリティ検査行列内の上記ｍ２ｎ２個の順列行列の配列ｍ２×ｎ２がｎ２＜ｍ２の関係にある場合に、上記ｐ１個のパリティ処理ユニットの各々が、上記第２のパリティ検査行列の対応する列内の値が“１”のｍ２個の行位置に対応するビット情報を同時に入力し、当該ｍ２個の行位置に対応するビット情報をもとに当該ｍ２個の行位置に対応するパリティ情報を同時に更新する構成とすると良い。この場合、各パリティ処理ユニットによるパリティ更新処理を短時間で実行できる。
【手続補正５】
【補正対象書類名】明細書
【補正対象項目名】００１３
【補正方法】変更
【補正の内容】
【００１３】
以下、本発明の一実施形態につき図面を参照して説明する。  
まず、本実施形態で適用される、イレギュラーＬＤＰＣ符号のパリティ検査行列Ｈについて説明する。このパリティ検査行列Ｈは、図１に示すように、ｐ１×ｐ１の第１の順列行列（Permuted Matrix）Ｉg,h（ｇ＝１，２，…ｍ１，ｈ＝１，２，…，ｎ１）がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列Ｉg,h（ｇ＝１，２，…ｍ２，ｈ＝ｎ１＋１，ｎ１＋２，…，ｎ１＋ｎ２）をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列として表される。各順列行列Ｉg,hは検査行列Ｈのサブマトリクスであり、第１の順列行列についてはｐ１×ｐ１の単位行列Ｉ、第２の順列行列についてはｐ２×ｐ２の単位行列Ｉの異なる２つの行の交換、もしくは異なる２つの列の交換を、複数回数繰り返すことにより得られる行列である。第１のパリティ検査行列と第２のパリティ検査行列とは、ｐ１×ｍ１＝ｐ２×ｍ２の条件を満たすように構成される。この場合、検査行列Ｈの行数Ｍはｐ１ｍ１であり、列数Ｎは（ｐ１ｎ１＋ｐ２ｎ２）である。図１の例では、ｍ１＝３、ｎ１＝５、ｍ２＝５、ｎ１＝３である。検査行列Ｈは、Ｍ（＝ｐ１ｍ１）個のパリティノードと、Ｎ（＝ｐ１ｎ１＋ｐ２ｎ２）個のビットノードを含む。この検査行列Ｈは、イレギュラーＬＤＰＣ符号がＮ（＝ｐ１ｎ１＋ｐ２ｎ２）ビットである場合を前提としている。このイレギュラーＬＤＰＣ符号のｊ番目（ｊ＝１，２，…，Ｎ）のビットをｘjと表現する。検査行列Ｈの各行は、周知のように、それぞれ１つのパリティチェック方程式であると見なすことができる。検査行列Ｈの第ｉ行に対応するパリティチェック方程式は、第ｉパリティチェック方程式と呼ばれる。ＮビットのイレギュラーＬＤＰＣ符号は、検査行列Ｈ内の全てのパリティチェック方程式、つまり第１乃至第Ｍパリティチェック方程式を満足しなければならない。
【手続補正６】
【補正対象書類名】明細書
【補正対象項目名】００１４
【補正方法】変更
【補正の内容】
【００１４】
図１中の各順列行列Ｉg,hにおける斜めの線は、値が“１”のビットの位置の軌跡を表す。図１から明らかなように、検査行列Ｈを構成する３（ｍ１）×５（ｎ１）個の各第１の順列行列Ｉg,hの各行及び各列内の“１”の個数、５（ｍ２）×３（ｎ２）個の各第２の順列行列Ｉg,hの各行及び各列内の“１”の個数はいずれも１である。したがって、検査行列Ｈの各行及び各列内の“１”の個数は、ｍ１×ｎ１の配列中ではそれぞれｎ１個及びｍ１個、ｍ２×ｎ２の配列中ではそれぞれｎ２個及びｍ２個である。ｍ１とｎ１はｍ１＜ｎ１を満たすように設定される。このため検査行列Ｈのｍ１×ｎ１の配列中では１行内の“１”の個数は、１列内の１の個数に比べて多い。
【手続補正７】
【補正対象書類名】明細書
【補正対象項目名】００２５
【補正方法】変更
【補正の内容】
【００２５】
図２は本発明の一実施形態に係るイレギュラーＬＤＰＣ符号復号器の構成を示すブロック図である。同図に示すように、イレギュラーＬＤＰＣ符号復号器は、Ｍ個（Ｍ＝ｐ１ｍ１＝３ｐ１）のビット処理ユニット１０-1乃至１０-Mと、ｐ１個のパリティ処理ユニット２０-1乃至２０-mと、メモリ３０と、コントローラ４０とから構成される。パリティ処理ユニット２０-1乃至２０-mは、パリティ検査行列Ｈがｐ１×ｍ１＝ｐ２×ｍ２の条件を満たす場合に、ｐ１とｐ２のうち大きい方の数だけ設けられる。
【手続補正８】
【補正対象書類名】明細書
【補正対象項目名】００３０
【補正方法】変更
【補正の内容】
【００３０】
メモリ３０は、ビット処理ユニット１０-1乃至１０-Mによって算出されるビット情報及びパリティ処理ユニット２０-1乃至２０-mによって算出されるパリティ情報を記憶するのに用いられる。ここでは、メモリ３０は、検査行列Ｈを構成する３×５個（ｍ１×ｎ１個）の順列行列Ｉ1,1，Ｉ2,1，Ｉ3,1，Ｉ1,2，Ｉ2,2，Ｉ3,2，Ｉ1,3，Ｉ2,3，Ｉ3,3，Ｉ1,4，Ｉ2,4，Ｉ3,4，Ｉ1,5，Ｉ2,5及びＩ3,5にそれぞれ対応する３×５個（ｍ１×ｎ１個）のメモリユニットと、５×３個（ｍ２×ｎ２個）の順列行列Ｉ1,6，Ｉ2,6，Ｉ3,6，Ｉ4,6，Ｉ5,6，Ｉ1,7，Ｉ2,7，Ｉ3,7，Ｉ4,7，Ｉ5,7，Ｉ1,8，Ｉ2,8，Ｉ3,8，Ｉ4,8，及びＩ5,8にそれぞれ対応する５×３個（ｍ２×ｎ２個）のメモリユニットから構成されているものとする。この３×５個（ｍ１×ｎ１個）及び５×３個（ｍ２×ｎ２個）のメモリユニットは同時にアクセス可能である。ここで、順列行列Ｉg,hに対応するメモリ３０内の記憶領域の状態を、Ｑg,hまたはＲg,hで表す。Ｑg,hはメモリ３０内の対応する記憶領域にパリティ情報が格納されている状態を表し、Ｒg,hはメモリ３０内の対応する記憶領域にビット情報が格納されている状態を表す。
【手続補正９】
【補正対象書類名】明細書
【補正対象項目名】００５１
【補正方法】変更
【補正の内容】
【００５１】
本実施形態では、上記したように、パリティ処理ユニット２０-kの出力側にルックアップテーブル２１１，２１２，２１３，２１４及び２１５を備えている。パリティ処理ユニット２０-kの出力側にルックアップテーブル２１１，２１２，２１３，２１４及び２１５を備える代わりに、ビット処理ユニット１０-i内のマルチプレクサ１３２及び１３５の出力側にそれぞれルックアップテーブルを設けることも可能である。この場合、パリティ処理ユニットのルックアップテーブル数は０となるものの、１つのビット処理ユニットにつき（つまり１行の処理当たり）、５つのルックアップテーブルを必要とする。したがって、イレギュラーＬＤＰＣ符号復号器全体では、５×ｐ１ｍ１（＝１５（ｐ１））個のルックアップテーブルを必要とする。これに対して本実施形態では、１つのビット処理ユニット１０-iにつき１つのルックアップテーブルを必要とすると共に、１つパリティ処理ユニット２０-kにつきｍ２個のルックアップテーブルを必要とする。この場合、イレギュラーＬＤＰＣ符号復号器全体では、１×ｐ１ｍ１＋ｍ２×ｐ１＝ｐ１（ｍ１＋ｍ２）（＝８（ｐ１））個のルックアップテーブルだけで済む。つまり、本実施形態においては、パリティ処理ユニット２０-kの出力側にルックアップテーブルを備えることにより、イレギュラーＬＤＰＣ符号復号器全体では、ルックアップテーブルの個数を１５（ｐ１）個から８（ｐ１）個に削減できる。
【手続補正１０】
【補正対象書類名】明細書
【補正対象項目名】００５２
【補正方法】変更
【補正の内容】
【００５２】
次に、図２のイレギュラーＬＤＰＣ符号復号器内のコントローラ４０によって制御される、ビット処理ユニット１０-1乃至１０-M及びパリティ処理ユニット２０-1乃至２０-mにおける計算の流れについて、図５、図６及び図７を参照して説明する。図５は、ビット処理ユニット１０-1乃至１０-Mによるビット更新処理（水平計算処理ＨＣＡＬＣ）及びパリティ処理ユニット２０-1乃至２０-mによるパリティ更新処理（垂直計算処理ＶＣＡＬＣ）における、サイクル毎の入出力情報を示す。図６及び図７は、検査行列Ｈを構成する３×５個（ｍ１×ｎ１個）の順列行列と５×３個（ｍ２×ｎ２個）の順列行列にそれぞれ対応するメモリ３０内の領域の状態の遷移を示す。図５乃至図７では、第１のパリティ検査行列における順列行列Ｉg,h（ｇ＝１，２，３、ｈ＝１，２，…，５）と第２のパリティ検査行列における順列行列Ｉg,h（ｇ＝１，２，…，５、ｈ＝６，７，８）内の値が“１”の各ビットに対応するΨ(ｑi,j)及びｒi,jの集合が、それぞれＱg,h及びＲg,hで表されている。Ｑg,hは、ＭＳＢ(ｑi,j)も含む。
【手続補正１１】
【補正対象書類名】明細書
【補正対象項目名】００６０
【補正方法】変更
【補正の内容】
【００６０】
＜第７サイクル＞
第７サイクルでは、ビット処理ユニット１０-1乃至１０-Mの加算回路１１１内のマルチプレクサ１１１ｂによってΨ(ｑi,j7)が選択される。そして第７サイクルでは、このΨ(ｑi,j7)を用いて加算回路１１１による加算処理が行われる。即ち、第６サイクルにおいてレジスタ１１１ａに格納されていた値と、マルチプレクサ１１１ｂによって選択されたΨ(ｑi,j7)とが、加算回路１１１内の加算器１１１ｄによって加算される。加算器１１１ｄの加算結果、つまりレジスタ１１１ａに格納されていた値とΨ(ｑi,j7)との和は、当該レジスタ１１１ａに格納される。一方、ビット処理ユニット１０-1乃至１０-Mの符号計算回路１３０では、当該符号計算回路１３０内のマルチプレクサ１３２によってＭＳＢ(ｑi,j7)が選択される。第７サイクルでは、このＭＳＢ(ｑi,j7)を用いて符号計算回路１３０内の排他的論理和回路１３４による排他的論理和演算が行われる。即ち、排他的論理和回路１３４では、第６サイクルにおいてレジスタ１３１に格納されていた値と、マルチプレクサ１３２によって選択されたＭＳＢ(ｑi,j7)との排他的論理和が計算される。排他的論理和回路１３４の演算結果、つまりレジスタ１３１に格納されていた値とＭＳＢ(ｑi,j7)との排他的論理和演算結果は、当該レジスタ１３１に格納される。なお、Ψ(ｑi,j7)及びＭＳＢ(ｑi,j7)は、検査行列Ｈの第ｉ行内で“１”となるビット位置ｊ１，ｊ２，ｊ３，ｊ４，ｊ５，ｊ６，ｊ７，ｊ８のうちの７番目のビット位置ｊ７（ｊ＝ｊ７）に対応するものであり、メモリ３０に格納されているＱ1,7,Ｑ2,7,Ｑ3,7,Ｑ4,7及びＱ5,7に相当する。
【手続補正１２】
【補正対象書類名】明細書
【補正対象項目名】００６６
【補正方法】変更
【補正の内容】
【００６６】
さて、第１０サイクルでは、第９サイクルでメモリ３０に格納されたＲ1,1，Ｒ2,1，及びＲ3,1内の各要素ｒi,jを利用することができる。このため第１０サイクルでは、コントローラ４０の制御によって、パリティ処理ユニット２０-1乃至２０-mによるパリティ更新処理が開始される。即ち第１０サイクルでは、Ｒ1,1，Ｒ2,1，及びＲ3,1内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、第１のパリティ検査行列における第１列乃至第ｐ１列の各列毎に、Ψ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,j)と、ＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j)及びＭＳＢ(ｑi3,j)と、ｑjとが求められる。この第１列乃至第ｐ１列の各列毎のΨ(ｑi1,j)，Ψ(ｑi2,j)及びΨ(ｑi3,j)とＭＳＢ(ｑi1,j)，ＭＳＢ(ｑi2,j)及びＭＳＢ(ｑi3,j)とｑjとによって、メモリ３０に格納されているＱ1,1，Ｑ2,1及びＱ3,1がそれぞれＱ'1,1，Ｑ'2,1及びＱ'3,1に更新される（図６（Ｃ））。
【手続補正１３】
【補正対象書類名】明細書
【補正対象項目名】００８８
【補正方法】変更
【補正の内容】
【００８８】
また、第１５サイクルでは、第１４サイクルでメモリ３０に格納されたＲ1,６，Ｒ2,６，Ｒ3,６，Ｒ4,6及びＲ5,6内の各要素ｒi,jを利用したパリティ更新が、パリティ処理ユニット２０-1乃至２０-mによって行われる。これにより、メモリ３０に格納されているＱ1,6，Ｑ2,6，Ｑ3,6，Ｑ4,6及びＱ5,6がそれぞれＱ'1,6，Ｑ'2,6，Ｑ'3,6，Ｑ'4,6及びＱ'5,6に更新される（図７（Ｈ））。
【手続補正１４】
【補正対象書類名】明細書
【補正対象項目名】００９９
【補正方法】変更
【補正の内容】
【００９９】
また上記実施形態では、検査行列Ｈが３×５の第１の順列行列と５×３の第２の順列行列を含むアレイ構成である場合を想定している。しかし、検査行列Ｈ内の順列行列の配列は上記実施形態に限らない。即ち、検査行列Ｈは、ｐ１×ｐ１の第１の順列行列がｍ１×ｎ１に配列された構造の第１のパリティ検査行列と、ｐ２×ｐ２の第２の順列行列をｍ２×ｎ２に配列した構造の第２のパリティ検査行列とを並べて得られる連接行列とし、ｐ１×ｍ１＝ｐ２×ｍ２の条件を満たせば良い。