(57)【特許請求の範囲】
【請求項１】
パリティチェック符号化された受信信号に対して、Ｌａｙｅｒｅｄ復号化アルゴリズムにより検査行列の複数の階層の階層毎に確率演算処理を並列に実行して復号処理を行なう復号化装置であって、
前記確率演算処理を並列に実行する確率演算処理部と、
前記確率演算処理部を制御することにより、前記複数の階層のうちの１つの階層内での確率演算処理を、複数段の確率演算処理により実行し、第１段の処理では前記検査行列の各列で一番上に出現する１の位置に対応するビットノード処理、全ての１の位置において前記ビットノード処理が計算された行におけるチェックノード処理、及び前記ビットノード処理及び前記チェックノード処理が行なわれた列に対する事後確率更新処理の各々を並列に実行させ、第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて計算できるビットノ―ド処理、全ての１の位置において前記ビットノード処理が計算された行におけるチェックノード処理、及び前記ビットノード処理及び前記チェックノード処理が行なわれた列に対する事後確率更新処理の各々を並列に実行させる確率演算処理制御部と
を含む復号化装置。
【請求項２】
パリティチェック符号化された受信信号に対して、Ｌａｙｅｒｅｄ復号化アルゴリズムにより検査行列の複数の階層の階層毎に確率演算処理を並列に実行して復号処理を行なう復号化装置であって、
前記確率演算処理を並列に実行する確率演算処理部と、
前記確率演算処理部を制御することにより、前記複数の階層のうちの１つの階層内での確率演算処理を、複数段の確率演算処理により実行し、第１段の処理においてビットノード処理、チェックノード処理、及び事後確率更新処理を含む前記１つの階層内での全確率演算を並列に実行させ、第２段以降の処理において、前記検査行列の同一列に複数の１が発生する列において上から２番目以降の１に対応するビットノード処理の再計算及び前記再計算の結果に応じて再計算が必要となる確率演算を並列に実行させる確率演算処理制御部と、
を含む復号化装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本願開示は、一般に復号化装置に関し、詳しくはＬＤＰＣ符号に対する復号化装置に関する。
【背景技術】
【０００２】
ＬＤＰＣ（Low Density Parity Check:低密度パリティ検査）とは、送信信号がチャネル雑音により誤って受信された場合に、その誤りを訂正する手法の一つである。ＬＤＰＣ符号を用いた送受信方式では、誤り訂正を行うためにＬＤＰＣ検査行列Ｈが用いられる。送信信号Ｔｘは、送信側においてＨ×Ｔｘ＝０となるようにして送信している。従って送信した信号が受信側で正しく受信された場合には、受信信号ＲｘはＨ×Ｒｘ＝０という条件を満たすことになる。このＨ×Ｒｘという計算をパリティ検査と呼ぶ。
【０００３】
図１は、ＬＤＰＣ符号を用いた送受信モデルを示す図である。送信側１０からＨ×Ｔｘ＝０となるように送信した送信信号Ｔｘ＝［００１００１］が、伝送路においてチャネル雑音を受け、受信信号Ｒｘ＝［０１１００１］として受信側１２に受信される。この受信信号Ｒｘに対するパリティ検査Ｈ×Ｒｘの結果はゼロにならず、受信信号Ｒｘには誤りがあることが分かる。受信側１２では、ＬＤＰＣ復号化を行なうＬＤＰＣ復号器を用いて、Ｈ×Ｒｘ＝０となるように誤り訂正を行う。これにより誤り訂正後の受信信号Ｒｘ’＝［００１００１］が得られる。
【０００４】
図２は、パリティ検査で用いる行列計算の定義を示す図である。図２に示すように、パリティ検査の行列計算では、通常の行列演算の積和計算において「積」が論理積（＆）演算となり、「和」が排他的論理和（ＸＯＲ）となった演算を行なう。
【０００５】
図３は、ＬＤＰＣ検査行列及び確率メッセージについて説明するための図である。ＬＤＰＣ検査行列は図３に示すようにＭ×Ｎの行列であり、各列をｂ１乃至ｂＮで示し、各行をｃ１乃至ｃＭで示す。ｂ１乃至ｂＮはビットノード、ｃ１乃至ｃＭはチェックノードと呼ばれる。検査行列Ｈのｍ行ｎ列の要素が“１”であれば、チェックノードｃｍからビットノードｂｎへの確率メッセージαｍｎと、ビットノードｂｎからチェックノードｃｍへの確率メッセージβｍｎとが定義される。即ち、検査行列Ｈにおいて値が“１”である要素に対応するビットノードｂｎとチェックノードｃｍとの組に対して、確率メッセージαｍｎとβｍｎとが定義される。これらの確率メッセージは、受信信号の確率を高めるためにチェックノードとビットノードの間で交換される。各ビットノードｂｎに対して受信信号の事後確率ｓｕｍｎが定義される。
【０００６】
ＬＤＰＣ復号処理では、受信信号の確率的な信頼度情報から算出した確率情報を更新していくことにより、パリティ検査結果がゼロになるような受信信号を求める。ＬＤＰＣ復号アルゴリズムとして、良好な訂正能力を持つＬａｙｅｒｅｄ復号アルゴリズムが一般的に用いられる。
【０００７】
図４はＬａｙｅｒｅｄアルゴリズムを用いたＬＤＰＣ復号器の構成の一例を示す図である。ＬＤＰＣ復号器２０は、確率演算処理部２１とパリティ検査部２２とを含む。ＬＤＰＣ復号器２０への入力λは受信信号から導出した値で、送信信号が０なのか１なのかを確率的に表した事前確率であり、ＬＬＲ（Log-Likelihood Ratio）と呼ばれる。ＬＤＰＣ復号器２０の出力Ｒｘ’は誤り訂正後の受信信号である。確率演算処理部２１は、事前確率λｎに基づいて事後確率ｓｕｍｎを求め、反復処理により事後確率ｓｕｍを更新していくことにより、確率を高める処理を行なう。この確率演算処理は、受信信号の確率的な信頼度を表わす事前確率から、パリティチェックに基づく受信信号の拘束条件を考慮して事後確率を求めることに相当する。パリティ検査部２２は、事後確率ｓｕｍを用いてＲｘ’を算出してパリティ検査Ｈ×Ｒｘ’の演算を行なう。このパリティ検査の結果がゼロであるか否かに基づいて、復号処理を終了するか或いは事後確率ｓｕｍをフィードバックして反復処理をもう一回繰返すかが制御される。
【０００８】
確率演算処理部２１は、ビットノード処理部２５、チェックノード処理部２６、及び事後確率更新処理部２７を含む。ビットノード処理部２５は、事前確率λｎ又は事後確率ｓｕｍｎと確率メッセージαｍｎとを用いて確率メッセージβｍｎを算出する。具体的には、初期状態においては事後確率ｓｕｍｎとして事前確率λｎを用いて確率メッセージβｍｎを算出し、その後の反復処理では事後確率更新処理部２７が求めたｓｕｍｎを用いて確率メッセージβｍｎを算出する。チェックノード処理部２６は、確率βｍｎを用いて確率αｍｎを更新する。事後確率更新処理部２７は、ビットノード処理部２５で算出したβｍｎとチェックノード処理部２６で算出したαｍｎとを用いて事後確率ｓｕｍｎを更新する。
【０００９】
ビットノード処理部２５が実行するビットノード処理ｆｂ（ｓｕｍｎ，αｍｎ）は、具体的には以下のように計算される。
βｍｎ＝ｆｂ（ｓｕｍｎ，αｍｎ）＝ｓｕｍｎ−αｍｎ                （１）
また、事後確率更新処理部２７が計算する事後確率更新処理ｆｓ（αｍｎ，βｍｎ）は、具体的には以下のように計算される。
ｓｕｍｎ＝ｆｓ（αｍｎ，βｍｎ）＝βｍｎ＋αｍｎ                （２）
上記のビットノード処理と事後確率更新処理との間においてチェックノード処理により更新後のαｍｎを計算し、更新後のαｍｎを用いて事後確率更新処理を実行することで、事後確率ｓｕｍｎの確率を繰り返し処理により順次高めていくことができる。なおＬａｙｅｒｅｄアルゴリズムでは、チェックノード処理におけるαｍｎの計算式の違いにより、Layered BPアルゴリズム、Layered Min-sumアルゴリズム、及びLayered Normalized Min-sumアルゴリズム等がある。
【００１０】
Ｌａｙｅｒｅｄ復号アルゴリズムは、検査行列を階層と呼ばれる複数の行ブロックに分割し確率演算処理を行うアルゴリズムである。例えば、Ｍ×ＮのＬＤＰＣ検査行列を、各階層がＰ行からなるＬ個の階層に分割して確率演算処理を行う。
【００１１】
図５は、各階層がＰ行からなるＬ個の階層に分割したＬＤＰＣ検査行列を示す図である。図６は、１階層内でのＬａｙｅｒｅｄアルゴリズムの実行順序を示す図である。図７は、複数の階層でのＬａｙｅｒｅｄアルゴリズムの実行順序を示す図である。前述の説明のように、検査行列の要素が“１”である位置（αｍｎ及びβｍｎが定義されている位置）に対して確率演算処理が実行される。この際、１階層の中では、図６に示されるように、Ｌａｙｅｒｅｄ復号アルゴリズムの確率演算処理（ビットノード処理部、チェックノード処理部、及び事後確率更新処理部）が順番に実行される。またビットノード処理部、チェックノード処理部、及び事後確率更新処理部の各々は、１階層内のＰ行に対して並列に実行される。ここで階層ｌに対する確率演算処理により求められたｎ列目の事後確率をｓｕｍｎｌと表わす。図６に示されるように、階層ｌ−１の事後確率に基づいて階層ｌの事後確率を求める処理、即ちｓｕｍｎｌ−１→βｍｎ→αｍｎ→ｓｕｍｎｌを順次計算する処理が１階層内で実行される。
【００１２】
上記のｓｕｍｎｌ−１→βｍｎ→αｍｎ→ｓｕｍｎｌを順次計算する処理を纏めてｓｕｍｎｌ＝ｆｌ（ｓｕｍｎｌ−１）と表わすと、複数の階層における確率演算処理は図７のように示すことができる。図７に示すように、第１階層の事後確率ｓｕｍｎ１は初期値ｓｕｍｎ０に基づいて計算し、第２階層の事後確率ｓｕｍｎ２は第１階層の事後確率ｓｕｍｎ１に基づいて計算し、第３階層の事後確率ｓｕｍｎ３は第１階層の事後確率ｓｕｍｎ２に基づいて計算する。以降、各階層について同様にして事後確率を求めていく。
【００１３】
上記の処理において、第ｌ階層の事後確率ｓｕｍｎｌは第ｌ−１階層の事後確率ｓｕｍｎｌ−１に基づいて計算しており、この第ｌ階層内での事後確率ｓｕｍｎｌは各Ｐ行の値“１”の位置に対して同時に実行される。このような処理では、検査行列によるデータ衝突という問題が起こる場合がある。
【００１４】
図８は、データ衝突の発生を示す図である。図８に示すように１つの階層ｌ中の同一の列に２つ“１”が存在する場合を考える。Ｌａｙｅｒｅｄアルゴリズムでは、上段側の“１”の位置に対する事後確率ｓｕｍｎｌ（ｓｕｍｎｌ（１）として示す）の計算が、１つ前の階層の事後確率ｓｕｍｎｌ−１に基づいて計算される。またそれと並行して、下段側の“１”の位置に対する事後確率ｓｕｍｎｌ（ｓｕｍｎｌ（２）として示す）の計算も、１つ前の階層の事後確率ｓｕｍｎｌ−１に基づいて計算される。本来であれば、上段の事後確率ｓｕｍｎｌ（１）の計算により事後確率ｓｕｍｎｌが更新されているので、下段側の“１”の位置に対する事後確率ｓｕｍｎｌ（２）の計算は、更新後の事後確率ｓｕｍｎｌ（１）の値に基づいて行なうことが好ましい。しかしながらＬａｙｅｒｅｄアルゴリズムでは計算処理の効率化のためにＰ行に対して並列処理を行なっているので、同一列に複数の“１”が存在する場合には、間違った値を用いて確率演算するというデータ衝突問題が起こる。このデータ衝突が発生すると、間違った値を用いるため、誤差を生じ、その結果、誤り訂正能力に影響を与えてしまう。このようなデータ衝突問題は、同一階層内の同一列に複数個の“１”がある検査行列に対して発生する。
【００１５】
非特許文献1は、近似によりデータ衝突を解決する手法を開示する。この手法は、ある階層においてデータ衝突が起こっている列に対して、当該階層の処理が終わってから、更新後の２個の事後確率を加算して求めた和から前階層の事後確率を減算する処理を実行する。この後処理により、事後確率の近似計算を行う。この処理では、あくまで近似処理が行なわれるだけであり、正しい事後確率値を用いて計算しているのではない。このような事後確率の近似処理では、受信ＢＥＲ（Ｂｉｔ  Ｅｒｒｏｒ  Ｒａｔｅ）特性が劣化し、劣悪な受信環境において安定した受信ができない。
【先行技術文献】
【特許文献】
【００１６】
【特許文献１】国際公開第ＷＯ２００４／１０７５８５号パンフレット
【特許文献２】特開２００６−１９１２４６号公報
【特許文献３】特開２００４−１８６９４０号公報
【特許文献４】特開２００６−３０４１３０号公報
【非特許文献】
【００１７】
【非特許文献１】Arthur Segard, Francois Verdier, David Declercq and Pascal Urard, “ADVB-S2 Compliant LDPC Decoder Integrating the Horizontal Shuffle Scheduling,”ISPACS 2006, pp. 1013-1016, Dec. 2006
【発明の概要】
【発明が解決しようとする課題】
【００１８】
以上を鑑みると、Ｌａｙｅｒｅｄアルゴリズムにおいてデータ衝突時に正しい事後確率値を計算可能な復号化装置が望まれる。
【課題を解決するための手段】
【００１９】
パリティチェック符号化された受信信号に対して、Ｌａｙｅｒｅｄ復号化アルゴリズムにより検査行列の複数の階層の階層毎に確率演算処理を並列に実行して復号処理を行なう復号化装置は、前記確率演算処理を並列に実行する確率演算処理部と、前記確率演算処理部を制御することにより、前記複数の階層のうちの１つの階層内での確率演算処理を、複数段の確率演算処理により実行し、第１段の処理では前記検査行列の各列で一番上に出現する１の位置に対応するビットノード処理、全ての１の位置において前記ビットノード処理が計算された行におけるチェックノード処理、及び前記ビットノード処理及び前記チェックノード処理が行なわれた列に対する事後確率更新処理の各々を並列に実行させ、第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて計算できるビットノ―ド処理、全ての１の位置において前記ビットノード処理が計算された行におけるチェックノード処理、及び前記ビットノード処理及び前記チェックノード処理が行なわれた列に対する事後確率更新処理の各々を並列に実行させる確率演算処理制御部とを含む。
【発明の効果】
【００２０】
本願開示の少なくとも１つの実施例によれば、Ｌａｙｅｒｅｄアルゴリズムにおいてデータ衝突時に正しい事後確率値を計算できる。
【図面の簡単な説明】
【００２１】
【図１】ＬＤＰＣ符号を用いた送受信モデルを示す図である。
【図２】パリティ検査で用いる行列計算の定義を示す図である。
【図３】ＬＤＰＣ検査行列及び確率メッセージについて説明するための図である。
【図４】ＬＤＰＣ復号器の構成の一例を示す図である。
【図５】Ｌ個の階層に分割したＬＤＰＣ検査行列を示す図である。
【図６】１階層内でのＬａｙｅｒｅｄアルゴリズムの実行順序を示す図である。
【図７】複数の階層でのＬａｙｅｒｅｄアルゴリズムの実行順序を示す図である。
【図８】データ衝突の発生を示す図である。
【図９】データ衝突解決方法を示す図である。
【図１０】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第１の実施例を示す図である。
【図１１】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第１の実施例を示すフローチャートである。
【図１２】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により確率演算処理を実行するＬＤＰＣ復号器の構成の第１の実施例を示す図である。
【図１３】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第２の実施例を示す図である。
【図１４】チェックノード処理におけるαｍｎの計算を示す図である。
【図１５】符号再計算及び絶対値再計算の必要性を判断する具体的な処理のフローチャートである。
【図１６】符号再計算及び絶対値再計算の必要性を判断する一般的な処理のフローチャートである。
【図１７】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第２の実施例を示すフローチャートである。
【図１８】並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により確率演算処理を実行するＬＤＰＣ復号器の構成の第２の実施例を示す図である。
【図１９】シミュレーションにより得たＢＥＲ特性結果を示す図である。
【図２０】ＬＤＰＣ復号器を備えたシステム構成の一例を示す図である。
【発明を実施するための形態】
【００２２】
以下に、本発明の実施例を添付の図面を用いて詳細に説明する。
【００２３】
図９は、データ衝突解決方法を示す図である。図９に示すように検査行列Ｈの階層ｌにおいて同一列に２つの“１”がある場合、前段処理１５０を行ってから後段処理１５１を実行する。この際、前段処理１５０において、上段側の“１”の事後確率ｓｕｍｎｌ（１）を計算し、下段側の“１”の位置に対する事後確率ｓｕｍｎｌ（２）は計算しなくてよい。或いは、前段処理１５０において、上段側の“１”の事後確率ｓｕｍｎｌ（１）を計算するのと同時に下段側の“１”の位置に対する事後確率ｓｕｍｎｌ（２）を計算してもよい。後段処理１５１においては、上段側の“１”の事後確率ｓｕｍｎｌ（１）を用いて、下段側の“１”の位置に対する事後確率ｓｕｍｎｌ（２）の計算を行なう。下段側の“１”が階層ｌ内の同一列の最後の“１”であれば、この事後確率ｓｕｍｎｌ（２）が階層ｌの確率演算処理後の事後確率ｓｕｍｎｌとなる。下段側の“１”が階層ｌ内の同一列の最後の“１”でなく、更に下段に３つめの“１”があれば、同様にして更なる後段処理１５１を実行し、３つめの“１”に対する事後確率ｓｕｍｎｌ（３）を求める。
【００２４】
前段処理１５０及び後段処理１５１は、並列性を可能な限り維持しつつデータ衝突を考慮して実行される。即ち、他の列及び他の行に対する確率演算処理が前段処理１５０や後段処理１５１と同時に並行して実行可能であれば、それらの処理を並列に実行する。以下に詳細に説明する第１の実施例では、第１段の処理において、データ衝突の影響を受けずに正しく計算できる全確率演算を並列に実行する。更に、その後段の処理において、第１段の処理では未計算であり、データ衝突の影響を受けるために第１段の処理の実行結果を利用して初めて正しく計算できる確率演算を並列に実行する。より一般的には、複数段の処理において、第１段の処理においてはデータ衝突の影響を受けずに正しく計算できる全確率演算処理を並列に実行し、その後の第ｎ段（ｎ：２以上の整数）の処理においては第ｎ−１段までの処理の確率演算結果を用いる処理を並列に実行する。また第２の実施例では、第１段の処理において、全確率演算を並列に実行する。更に、その後段の処理において、データ衝突の影響を受けるために再計算が必要な確率演算処理を並列に実行する。より一般的には、複数段の処理において、第１段の処理においては全確率演算処理を並列に実行し、その後の第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて再計算が必要な処理を並列に実行する。
【００２５】
このように、Ｌａｙｅｒｅｄアルゴリズムにおいて、１つの階層内での確率演算処理を、並列性を維持しつつデータ衝突を考慮して複数回の確率演算処理に分けて実行する。第１段では、データ衝突の影響を受けずに正しく計算できる確率演算を含む複数の確率演算処理を並列に実行し、第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて正しく計算できる確率演算処理を並列に実行する。ここで、並列性を維持するというのは、可能な限り維持すると言うことであり、並列性が維持できないときには並列処理にはならないことを許容する。例えば、第ｎ段の処理において実行すべき確率演算処理が１つしかなければ、当然ながらその１つの処理のみが実行される。また正しく計算できる確率演算というのは、着目階層内で上から順に１行ずつ確率演算処理を行なった場合と同一の結果をもたらす確率演算のことである。
【００２６】
図１０は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第１の実施例を示す図である。階層ｌの一例として行列３０が示される。第２行第１列の位置、第３行第１列の位置、第４行第４列の位置、第４行第６列の位置の合計４つの位置において、同一列に複数の“１”が発生するデータ衝突が起きている。即ち、これら４つの位置においては、前階層ｌ−１の確率演算処理の結果のみを用いたのでは、正しい事後確率値を計算することはできない。またこれら４つの位置の確率βに影響を受ける位置においても、正しい事後確率値を求めることができない。
【００２７】
図１０において、集合Ｓ（βｉ）はｉ段の処理により演算すべき確率メッセージβの集合である。また集合Ｓ（αｉ）はｉ段の処理により演算すべき確率メッセージαの集合である。更に集合Ｓ（ｓｕｍｉ）はｉ段の処理により演算すべき事後確率ｓｕｍの集合である。行列３０の例の場合、まず集合群３１に示す各集合に対して、第１段の確率演算処理が並列に実行される。即ち、データ衝突の影響を受けずに事後確率を正しく計算できる全確率演算処理を実行する。この場合、各列で最初に出現する“１”の位置に対応する確率βを求める確率演算処理（即ちビットノード処理）は、正しく計算することができる。即ち、集合Ｓ（β１）＝｛β１１，β１６，β２４，β２５，β３３｝については、前階層ｌ−１の確率演算処理の結果のみを用いて正しく計算することができる。また全ての“１”の位置においてビットノード処理が正しく計算された行における確率αを求める確率演算処理（即ちチェックノード処理）は、正しく計算することができる。即ち、集合Ｓ（α１）＝｛α１１，α１６｝については、既に実行済みのビットノード処理の結果を用いて正しく計算することができる。またビットノード処理及びチェックノード処理が正しく行なわれた列に対する事後確率ｓｕｍを求める確率演算処理（即ち事後確率更新処理）は、取り敢えず正しく計算することができる。即ち、集合Ｓ（ｓｕｍ１）＝｛ｓｕｍ１，ｓｕｍ６｝については、既に実行済みのビットノード処理及びチェックノード処理の結果を用いて取り敢えず正しく計算することができる。なおここで言う「取り敢えず正しい計算」とは、この段の処理については正しい更新演算であるが、後段において更に更新され得る計算と言うことである。
【００２８】
次に集合群３２に示す各集合に対して、第２段の確率演算処理が並列に実行される。即ち、第１段までの処理の確率演算結果を用いて事後確率を正しく計算できる確率演算処理を並列に実行する。この場合、第１段までの確率演算処理で事後確率ｓｕｍ及び確率αが正しく更新されている列に対する確率βを更新する確率演算処理（即ちビットノード処理）は、第１段までの処理の確率演算結果を用いて正しく計算することができる。即ち、集合Ｓ（β２）＝｛β２１，β４６｝については、第１段までの確率演算処理の結果を用いて正しく計算することができる。また全ての“１”の位置においてビットノード処理が正しく計算された行における確率αを求める確率演算処理（即ちチェックノード処理）は、正しく計算することができる。即ち、集合Ｓ（α２）＝｛α２１，α２４，α２５｝については、既に実行済みのビットノード処理の結果を用いて正しく計算することができる。またビットノード処理及びチェックノード処理が正しく行なわれた列に対する事後確率ｓｕｍを求める確率演算処理（即ち事後確率更新処理）は、取り敢えず正しく計算することができる。即ち、集合Ｓ（ｓｕｍ２）＝｛ｓｕｍ１，ｓｕｍ４，ｓｕｍ５｝については、既に実行済みのビットノード処理及びチェックノード処理の結果を用いて取り敢えず正しく計算することができる。
【００２９】
次に集合群３３に示す各集合に対して、第３段の確率演算処理が並列に実行される。即ち、第２段までの処理の確率演算結果を用いて事後確率を正しく計算できる確率演算処理を並列に実行する。この場合、第２段までの確率演算処理で事後確率ｓｕｍ及び確率αが正しく更新されている列に対する確率βを更新する確率演算処理（即ちビットノード処理）は、第２段までの処理の確率演算結果を用いて正しく計算することができる。即ち、集合Ｓ（β３）＝｛β３１，β４４｝については、第２段までの確率演算処理の結果を用いて正しく計算することができる。また全ての“１”の位置においてビットノード処理が正しく計算された行における確率αを求める確率演算処理（即ちチェックノード処理）は、正しく計算することができる。即ち、集合Ｓ（α３）＝｛α３１，α３３，α４４，α４６｝については、既に実行済みのビットノード処理の結果を用いて正しく計算することができる。またビットノード処理及びチェックノード処理が正しく行なわれた列に対する事後確率ｓｕｍを求める確率演算処理（即ち事後確率更新処理）は、正しく計算することができる。即ち、集合Ｓ（ｓｕｍ３）＝｛ｓｕｍ１，ｓｕｍ３，ｓｕｍ４，ｓｕｍ６｝については、既に実行済みのビットノード処理及びチェックノード処理の結果を用いて正しく計算することができる。
【００３０】
図１１は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第１の実施例を示すフローチャートである。ステップＳ１で初期化処理を行なう。即ち、事後確率ｓｕｍｎに、初期値として事前確率λｎを代入する。その後、検査行列の各階層についてステップＳ２以降の処理を繰り返す。ステップＳ２で、着目階層においてデータ衝突があるか否かを判断する。即ち、着目階層の同一列に複数の“１”が存在するか否かを判断する。データ衝突がない場合にはステップＳ３に進む。データ衝突がある場合にはステップＳ６に進む。
【００３１】
ステップＳ３で、集合Ｓに対してビットノード処理を実行する。ここで集合Ｓとは、着目階層において、検査行列の値が“１”である全ての要素の集合である。ステップＳ４で、集合Ｓに対してチェックノード処理を実行する。ステップＳ５で、集合Ｓに対して事後確率更新処理を実行する。これらステップＳ３乃至Ｓ５の処理は、従来のＬａｙｅｒｅｄアルゴリズムと同様に、着目階層内の全ての行に対して各確率演算処理を並列に実行する処理である。これらの各確率演算処理が終了するとステップＳ１２に進む。
【００３２】
データ衝突がある場合に実行されるステップＳ６では、何段目の処理であるかを示す変数ｉを１に初期化する。ステップＳ７で、集合Ｓ（βｉ）に対してビットノード処理を実行する。前述のように、集合Ｓ（βｉ）はｉ段の処理により演算すべき確率メッセージβの集合である。ステップＳ８で、集合Ｓ（αｉ）に対してチェックノード処理を実行する。集合Ｓ（αｉ）はｉ段の処理により演算すべき確率メッセージαの集合である。ステップＳ９で、集合Ｓ（ｓｕｍｉ）に対して事後確率更新処理を実行する。集合Ｓ（ｓｕｍｉ）はｉ段の処理により演算すべき事後確率ｓｕｍの集合である。ステップＳ１０で、着目階層の確率演算処理が完了したか否かを判断する。着目階層の確率演算処理が完了していない場合には、ステップＳ１１で変数ｉの値を１増加させ、ステップＳ７に戻り以降の処理を繰り返す。着目階層の確率演算処理が完了すると、ステップＳ１２に進む。
【００３３】
ステップＳ１２では、検査行列の最後の階層の確率演算処理が完了したか否かを判断する。最後の階層の確率演算処理が完了していない場合には、ステップＳ２に戻り、次の階層を対象としてステップＳ２以降の処理を繰り返す。最後の階層の確率演算処理が完了すると、ステップＳ１３で、パリティ検査を実行する。即ち、求められた事後確率ｓｕｍｎから算出したＲｘ’に対して検査行列を掛けて、演算結果がゼロになるか否かを判断する。パリティ検査結果がゼロでなければ、ステップＳ２に戻り以降の処理を繰り返すことにより、事後確率ｓｕｍｎを再度更新する。パリティ検査結果がゼロになるまで、上記の処理を反復的に実行し、パリティ検査結果がゼロになると処理を終了する。
【００３４】
図１２は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により確率演算処理を実行するＬＤＰＣ復号器の構成の第１の実施例を示す図である。図１２のＬＤＰＣ復号器４０は、基本構成として、ビットノード処理部４１、チェックノード処理部４２、事後確率更新処理部４３、及びパリティ検査部４４を含む。ビットノード処理部４１は、事前確率λｎ又は事後確率ｓｕｍｎと確率メッセージαｍｎとを用いて確率メッセージβｍｎを算出する。具体的には、初期状態においては事後確率ｓｕｍｎとして事前確率λｎを用いて確率メッセージβｍｎを算出し、その後の反復処理では事後確率更新処理部４３が求めたｓｕｍｎを用いて確率メッセージβｍｎを算出する。チェックノード処理部４２は、確率βｍｎを用いて確率αｍｎを更新する。事後確率更新処理部４３は、ビットノード処理部４１で算出したβｍｎとチェックノード処理部４２で算出したαｍｎとを用いて事後確率ｓｕｍｎを更新する。パリティ検査部４４は、事後確率ｓｕｍを用いてＲｘ’を算出してパリティ検査Ｈ×Ｒｘ’の演算を行なう。このパリティ検査の結果がゼロであるか否かに基づいて、復号処理を終了するか或いは事後確率ｓｕｍをフィードバックして反復処理をもう一回繰返すかが制御される。
【００３５】
ＬＤＰＣ復号器４０は更に、ビットノード処理開始制御部４５、チェックノード処理開始制御部４６、事後確率更新処理開始制御部４７、データ衝突検出部４８、βメモリ４９、αメモリ５０、及びＬＬＲメモリ５１を含む。ＬＤＰＣ復号器４０は更に、β集合演算開始テーブル５２、α集合演算開始テーブル５３、及びｓｕｍ集合演算開始テーブル５４を含む。各処理開始制御部４５乃至４７が確率演算処理制御部として機能し、上述の各処理部４１乃至４３を含む確率演算処理部を制御する。
【００３６】
データ衝突検出部４８は、階層カウンタが示す検査行列の着目階層について、データ衝突があるか否かを判断する。データ衝突検出部４８は、データ衝突の有無に応じてビットノード処理開始制御部４５、チェックノード処理開始制御部４６、及び事後確率更新処理開始制御部４７を制御する。データ衝突がない場合、これら処理開始制御部４５乃至４７は、それぞれビットノード処理部４１、チェックノード処理部４２、及び事後確率更新処理部４３を制御し、階層内の全てのビットノード処理、チェックノード処理、及び事後確率更新処理を実行する。
【００３７】
データ衝突がある場合、ビットノード処理開始制御部４５は、β集合演算開始テーブル５２が示すＬＬＲメモリ５１とαメモリ５０の必要なアドレスから読み出したデータに基づいて、ビットノード処理部４１にビットノード処理を実行させる。即ち、ｉ段目の処理において、ビットノード処理部４１が、集合Ｓ（βｉ）に対してビットノード処理を実行する。ｉ段目の処理の集合Ｓ（βｉ）を示すデータがβ集合演算開始テーブル５２に格納されている。またチェックノード処理開始制御部４６は、α集合演算開始テーブル５３が示すβメモリ４９の必要なアドレスから読み出したデータに基づいて、チェックノード処理部４２にチェックノード処理を実行させる。即ち、ｉ段目の処理において、チェックノード処理部４２が、集合Ｓ（αｉ）に対してビットノード処理を実行する。ｉ段目の処理の集合Ｓ（αｉ）を示すデータがα集合演算開始テーブル５３に格納されている。また事後確率更新処理開始制御部４７は、ｓｕｍ集合演算開始テーブル５４が示すαメモリ５０とβメモリ４９の必要なアドレスから読み出したデータに基づいて、事後確率更新処理部４３に事後確率更新処理を実行させる。即ち、ｉ段目の処理において、事後確率更新処理部４３が、集合Ｓ（ｓｕｍｉ）に対して事後確率更新処理を実行する。ｉ段目の処理の集合Ｓ（ｓｕｍｉ）を示すデータがｓｕｍ集合演算開始テーブル５４に格納されている。
【００３８】
図１３は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第２の実施例を示す図である。階層ｌの一例として行列６０が示される。第２行第１列の位置、第３行第１列の位置、第４行第４列の位置、第４行第６列の位置の合計４つの位置において、同一列に複数の“１”が発生するデータ衝突が起きている。即ち、これら４つの位置においては、前階層ｌ−１の確率演算処理の結果のみを用いたのでは、正しい事後確率値を計算することはできない。またこれら４つの位置の確率βに影響を受ける位置においても、正しい事後確率値を求めることができない。
【００３９】
確率演算処理の第２の実施例では、第１段の処理において、全確率演算を並列に実行する。更に、その後段の処理において、データ衝突の影響を受けるために再計算が必要となる確率演算処理を並列に実行する。図１３において、Ｃ（βｉ）は、後段処理である再計算処理においてｉ回目の再計算の対象となる確率メッセージβの集合である。Ｃ（αｉ）及びＣ（ｓｕｍｉ）は、Ｃ（βｉ）の再計算の結果に応じて再計算の要否の判定が必要となる確率メッセージαの集合及び事後確率ｓｕｍの集合である。Ｅ（βｉ）、Ｅ（αｉ）、及びＥ（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要である場合に、Ｃ（βｉ）、Ｃ（αｉ）、及びＣ（ｓｕｍｉ）を再計算したことの影響を受けるβ、α、及びｓｕｍの集合である。Ｃ’（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要ない場合に、Ｃ（βｉ）を再計算したことにより値が変化する事後確率ｓｕｍの集合である。Ｅ’（βｉ）、Ｅ’（αｉ）、及びＥ’（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要ない場合に、Ｃ（βｉ）を再計算したことによる値が変化するＣ’（ｓｕｍｉ）により影響を受けるβ、α、及びｓｕｍの集合である。
【００４０】
第１回目の再計算処理では、集合群６１に対する再計算が実行される。Ｃ（β１）として、データ衝突のある“１”のうち最上行にあるβ２１が再計算の対象となる。またβ２１の再計算の結果、Ｃ（α１）及びＣ（ｓｕｍ１）の再計算が必要な場合には、Ｃ（α１）、Ｃ（ｓｕｍ１）、Ｅ（β１）、Ｅ（α１）、及びＥ（ｓｕｍ１）が再計算される。逆にＣ（α１）及びＣ（ｓｕｍ１）の再計算が必要ない場合には、Ｃ’（ｓｕｍ１）、Ｅ’（β１）、Ｅ’（α１）、及びＥ’（ｓｕｍ１）が再計算される。同様にして、第２回目の再計算処理では集合群６１に対する再計算が実行され、データ衝突のある“１”のうち第２番目の行にあるβ３１が再計算の対象となる。また、第３回目の再計算処理では集合群６３に対する再計算が実行され、データ衝突のある“１”のうち第３番目の行の一番左にあるβ４４が再計算の対象となる。また、第４回目の再計算処理では集合群６４に対する再計算が実行され、データ衝突のある“１”のうち第３番目の行の左から２番目にあるβ４６が再計算の対象となる。
【００４１】
以下に、Ｃ（αｉ）、Ｃ（ｓｕｍｉ）の再計算処理の必要性の有無の判断について説明する。Ｌａｙｅｒｅｄアルゴリズムで一般的に使われているチェックノード計算は、Min-sum系のチェックノード計算である。このMin-sum系のチェックノード計算式の代表として、Min-sumアルゴリズムのチェックノード計算式は以下の式（３）のようになる。
【００４２】
【数１】
0005434454.tif 000002
ここでＡ（ｍ）は、タナーグラフにおいてチェックノードｃｍに接続する全てのビットノ
ードの集合を表わす。即ち、Ａ（ｍ）は、チェックノードｃｍに対応する検査行列の行に
おいて“１”である列の位置に対応するビットノードの集合である。Ａ（ｍ）＼ｎは、Ａ（ｍ）からｂｎを除いたビットノードの集合を表わす。即ち、図１４に示すように、αｍｎを計算するときにはβｍｎを使わず、残りの集合Ａ（ｍ）＼ｎのβを用いる。
【００４３】
Min-sum系のチェックノード計算式を絶対値計算部分と符号計算部分との２つの部分に分けて考える。αｍｎの絶対値は、集合Ａ（ｍ）＼ｎのβの絶対値の最小値に等しい。従ってβｍｎが最小値ではない場合には、αｍｎの絶対値は全体集合Ａ（ｍ）のβの絶対値の最小値と同値である、βｍｎが最小値の場合には、αｍｎの絶対値は全体集合Ａ（ｍ）のβの絶対値の第２最小値と同値である。αｍｎの符号は、Ａ（ｍ）＼ｎのβの符号の掛け算で算出する。符号位乗算の特性により、αｍｎの符号は、全体集合Ａ（ｍ）のβ符号を乗算してから更にβｍｎの符号を乗算することにより求めてもよい。
【００４４】
図１５は、符号再計算及び絶対値再計算の必要性を判断する具体的な処理のフローチャートである。図１５に示すフローチャートは、図１３に示す第１回目の再計算処理における集合群６１を説明するものである。ステップＳ１において、前述の式（１）を用いてβ’２１＝ｆｂ（ｓｕｍ１ｌ（１），α２１）を再計算する。再計算前のβに対して、β’は再計算後の値を示す。ここでｓｕｍ１ｌ（１）は、階層ｌの第１行（チェックノードｃ１に対応する行）に対して実行した確率演算処理により求められた第１列（ビットノードｂｎに対応する列）の事後確率である。なおチェックノードｃ２のチェックノード処理においては、前記式（３）から分かるように、α２１はβ２４及びβ２５から求め、α２４はβ２１及びβ２５から求め、α２５はβ２１及びβ２４から求めることになる。従って、β’２１の再計算により、少なくともα２４及びα２５の計算が影響を受けることになる。
【００４５】
まず前提として、確率演算処理の第２の実施例では、第１段の処理において全確率演算を並列に実行するが、例えば上記チェックノードｃ２については、再計算の対象であることが分かっているβ２１を用いずにチェックノード処理を計算しておく。即ち、β２１を除いた|β２４|及び|β２５|のうちで最小値と第２最小値を計算し、これら最小値と第２最小値とに基づいて、α２１、α２４、及びα２５の絶対値計算を行なっておく。但し、α２１、α２４、及びα２５の符号の計算については、β２１、β２４、及びβ２５の符号を用いて計算しておく。なおα２１の絶対値は上記最小値に同値であるとする。この第１段の処理における全確率演算の並列処理が終了してから、後段処理としての再計算が実行される。
【００４６】
まずステップＳ２で、前階層のｓｕｍ１ｌ−１から計算したβ２１の符号とｓｕｍ１ｌ（１）から再計算したβ’２１の符号とが異なるか否かを判断する。符号が異なる場合には、前記式（３）から分かるように、β’２１の再計算によりα２４及びα２５の符号が変化することになるので、α２４及びα２５の符号を再計算する（ステップＳ３）。ステップＳ２の判断において符号が異ならない場合には、符号を再計算する必要はない（ステップＳ４）。
【００４７】
次にステップＳ５で、再計算したβ’２１の絶対値|β’２１|が、|β２４|及び|β２５|の最小値より小さいか否かを判断する。最小値より小さい場合には、|β’２１|を新たな最小値、|β２４|及び|β２５|の最小値を新たな第２最小値として、α２４及びα２５の絶対値を再計算する（ステップＳ６）。ステップＳ５の判断の結果がＮＯの場合（最小値より小さくない場合）、ステップＳ７に進む。
【００４８】
ステップＳ７で、再計算したβ’２１の絶対値|β’２１|が、|β２４|及び|β２５|の最小値より大きく且つ|β２４|及び|β２５|の第２最小値より小さいか否かを判断する。判断結果がＹＥＳの場合、|β’２１|を新たな第２最小値として、α２４及びα２５の絶対値を再計算する（ステップＳ８）。またステップＳ７の判断結果がＮＯの場合、α２４及びα２５の絶対値の再計算は必要ない。
【００４９】
なお図１５のフローチャートでは、説明を簡単にするために、チェックノードｃ２について、再計算の対象であることが分かっているβ２１を用いずにチェックノード処理を計算しておくことを前提としたが、β２１を含めた通常のチェックノード処理を行なってもよい。この場合には、β’２１の再計算の影響を調べる際に、β’２１が最小値又は第２最小値であるか否かの判断と共に、β２１が最小値又は第２最小値であったか否かの判断も行なえばよい。即ち、図１５のステップＳ９において絶対値再計算必要なしと判断したが、β２１が最小値又は第２最小値であった場合には、このβ２１を用いて計算したα２４及びα２５については再計算が必要になるので、適宜再計算を行なえばよい。
【００５０】
図１５のフローチャートの処理を実行することにより、図１３に示す第１回目の再計算処理において、集合群６１に対する再計算が実行される。図１５のステップＳ３、Ｓ６、Ｓ８の場合、図１３においてＣ（α１）及びＣ（ｓｕｍ１）の再計算が必要となり、Ｃ（α１）＝｛α２４，α２５｝が上記のように再計算されるとともに、Ｃ（ｓｕｍ１）＝｛ｓｕｍ１，ｓｕｍ２，ｓｕｍ３｝が再計算される。またこれらの再計算の結果影響を受けるＥ（β１）、Ｅ（α１）、及びＥ（ｓｕｍ１）が再計算される。また図１５のステップＳ４及びＳ９の場合、図１３においてＣ（α１）のチェックノード処理の再計算の必要はないが、β’２１が再計算されているので、Ｃ’（ｓｕｍ１）＝｛ｓｕｍ１｝の事後確率更新処理が再計算される。またこの再計算の結果影響を受けるＥ’（β１）、Ｅ’（α１）、及びＥ’（ｓｕｍ１）が再計算される。
【００５１】
図１６は、符号再計算及び絶対値再計算の必要性を判断する一般的な処理のフローチャートである。ステップＳ１において、前述の式（１）を用いてβ’ｍｎ＝ｆｂ（ｓｕｍｎｌ（ｉ），αｍｎ）を再計算する。ステップＳ２で、前階層のｓｕｍｎｌ−１あるいはｓｕｍｎｌ（ｉ−２）から計算したβｍｎの符号と着目階層のｓｕｍｎｌ（ｉ）から再計算したβ’ｍｎの符号とが異なるか否かを判断する。符号が異なる場合には、前記式（３）から分かるように、β’ｍｎの再計算によりαの符号が変化することになるので、αの符号を再計算する（ステップＳ３）。ステップＳ２の判断において符号が異ならない場合には、符号を再計算する必要はない（ステップＳ４）。
【００５２】
次にステップＳ５で、再計算したβ’ｍｎの絶対値|β’ｍｎ|が、集合Ａ（ｍ）＼ｎのβの最小値ｍｉｎ１より小さいか否かを判断する。最小値より小さい場合には、|β’ｍｎ|を新たな最小値、元の最小値ｍｉｎ１を新たな第２最小値として、αの絶対値を再計算する（ステップＳ６）。ステップＳ５の判断の結果がＮＯの場合（最小値より小さくない場合）、ステップＳ７に進む。
【００５３】
ステップＳ７で、再計算したβ’ｍｎの絶対値|β’ｍｎ|が、集合Ａ（ｍ）＼ｎのβの最小値ｍｉｎ１より大きく且つ集合Ａ（ｍ）＼ｎのβの第２最小値ｍｉｎ２より小さいか否かを判断する。判断結果がＹＥＳの場合、|β’ｍｎ|を新たな第２最小値として、αの絶対値を再計算する（ステップＳ８）。またステップＳ７の判断結果がＮＯの場合、αの絶対値の再計算は必要ない。
【００５４】
図１７は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理の第２の実施例を示すフローチャートである。ステップＳ１で初期化処理を行なう。即ち、事後確率ｓｕｍｎに、初期値として事前確率λｎを代入する。その後、検査行列の各階層についてステップＳ２以降の処理を繰り返す。ステップＳ２で、集合Ｓに対してビットノード処理を実行する。ここで集合Ｓとは、着目階層において、検査行列の値が“１”である全ての要素の集合である。ステップＳ３で、集合Ｓに対してチェックノード処理を実行する。ステップＳ４で、集合Ｓに対して事後確率更新処理を実行する。これらステップＳ２乃至Ｓ４の処理は、従来のＬａｙｅｒｅｄアルゴリズムと同様に、着目階層内の全ての行に対して各確率演算処理を並列に実行してよい。なお後々再計算が必要になることが確実である確率演算については、実行せずに未計算の状態としておいてもよい。
【００５５】
次にステップＳ５で、着目階層においてデータ衝突があるか否かを判断する。即ち、着目階層の同一列に複数の“１”が存在するか否かを判断する。データ衝突がない場合にはステップＳ１９に進む。データ衝突がある場合にはステップＳ６に進む。
【００５６】
ステップＳ６では、何段目の処理であるかを示す変数ｉを１に初期化する。ステップＳ７で、集合Ｃ（βｉ）に対してビットノード処理を実行する。前述のように、集合Ｃ（βｉ）は、ｉ回目の再計算の対象となる確率メッセージβの集合である。ステップＳ８で、Ｃ（αｉ）及びＣ（ｓｕｍｉ）に対して再計算の必要があるか否かを判断する。前述のように、Ｃ（αｉ）及びＣ（ｓｕｍｉ）は、Ｃ（βｉ）の再計算の結果に応じて再計算の要否の判定が必要となる確率メッセージαの集合及び事後確率ｓｕｍの集合である。
【００５７】
ステップＳ８の判断結果がＹＥＳの場合、ステップＳ９で、Ｃ（αｉ）及びＣ（ｓｕｍｉ）に対して再計算を実行する。ステップＳ１０で、集合Ｅ（βｉ）に対してビットノード処理を再計算する。ステップＳ１１で、集合Ｅ（αｉ）に対してチェックノード処理を再計算する。ステップＳ１２で、集合Ｅ（ｓｕｍｉ）に対して事後確率更新処理を再計算する。なお前述のように、Ｅ（βｉ）、Ｅ（αｉ）、及びＥ（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要である場合に、Ｃ（βｉ）、Ｃ（αｉ）、及びＣ（ｓｕｍｉ）を再計算したことの影響を受けるβ、α、及びｓｕｍの集合である。以上の処理が完了すると、ステップＳ１７に進む。
【００５８】
ステップＳ８の判断結果がＮＯの場合、ステップＳ１３で、Ｃ’（ｓｕｍｉ）に対して再計算を実行する。前述のように、Ｃ’（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要ない場合に、Ｃ（βｉ）を再計算したことにより値が変化する事後確率ｓｕｍの集合である。ステップＳ１４で、集合Ｅ’（βｉ）に対してビットノード処理を再計算する。ステップＳ１５で、集合Ｅ’（αｉ）に対してチェックノード処理を再計算する。ステップＳ１６で、集合Ｅ’（ｓｕｍｉ）に対して事後確率更新処理を再計算する。なお前述のように、Ｅ’（βｉ）、Ｅ’（αｉ）、及びＥ’（ｓｕｍｉ）は、Ｃ（αｉ）及びＣ（ｓｕｍｉ）の再計算が必要ない場合に、Ｃ（βｉ）を再計算したことによる値が変化するＣ’（ｓｕｍｉ）により影響を受けるβ、α、及びｓｕｍの集合である。以上の処理が完了すると、ステップＳ１７に進む。
【００５９】
ステップＳ１７では、再計算判定すべき集合に対する判定及び再計算が完了したか否かを判断する。完了していない場合には、ステップＳ１８で変数ｉの値を１増加させ、ステップＳ７に戻り以降の処理を繰り返す。ステップＳ１７の判定の結果、再計算判定すべき集合に対する判定及び再計算が完了している場合には、ステップＳ１９に進む。
【００６０】
ステップＳ１９で、検査行列の最後の階層の確率演算処理が完了したか否かを判断する。最後の階層の確率演算処理が完了していない場合には、ステップＳ２に戻り、次の階層を対象としてステップＳ２以降の処理を繰り返す。最後の階層の確率演算処理が完了すると、ステップＳ２０で、パリティ検査を実行する。即ち、求められた事後確率ｓｕｍｎから算出したＲｘ’に対して検査行列を掛けて、演算結果がゼロになるか否かを判断する。パリティ検査結果がゼロでなければ、ステップＳ２に戻り以降の処理を繰り返すことにより、事後確率ｓｕｍｎを再度更新する。パリティ検査結果がゼロになるまで、上記の処理を反復的に実行し、パリティ検査結果がゼロになると処理を終了する。
【００６１】
図１８は、並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により確率演算処理を実行するＬＤＰＣ復号器の構成の第２の実施例を示す図である。図１８のＬＤＰＣ復号器７０は、基本構成として、ビットノード処理部７１、チェックノード処理部７２、事後確率更新処理部７３、及びパリティ検査部７８を含む。データ衝突の無い場合には、通常のＬａｙｅｒｅｄアルゴリズムと同様に動作する。即ち、ビットノード処理部７１は、事前確率λｎ又は事後確率ｓｕｍｎと確率メッセージαｍｎとを用いて確率メッセージβｍｎを算出する。具体的には、初期状態においては事後確率ｓｕｍｎとして事前確率λｎを用いて確率メッセージβｍｎを算出し、その後の反復処理では事後確率更新処理部７３が求めたｓｕｍｎを用いて確率メッセージβｍｎを算出する。チェックノード処理部７２は、確率βｍｎを用いて確率αｍｎを更新する。事後確率更新処理部７３は、ビットノード処理部７１で算出したβｍｎとチェックノード処理部７２で算出したαｍｎとを用いて事後確率ｓｕｍｎを更新する。パリティ検査部７８は、事後確率ｓｕｍを用いてＲｘ’を算出してパリティ検査Ｈ×Ｒｘ’の演算を行なう。このパリティ検査の結果がゼロであるか否かに基づいて、復号処理を終了するか或いは事後確率ｓｕｍをフィードバックして反復処理をもう一回繰返すかが制御される。
【００６２】
ＬＤＰＣ復号器７０は更に、データ衝突検出部７４、ビットノード再計算部７５、チェックノード再計算部７６、事後確率更新再計算部７７、ビットノード再計算制御部７９、チェックノード再計算制御部８０、及び事後確率更新再計算制御部８１を含む。ＬＤＰＣ復号器７０は更に、再計算判定部８２、β集合再計算用テーブル８３、α集合再計算用テーブル８４、ｓｕｍ集合再計算用テーブル８５、βメモリ８６、αメモリ８７、ＬＬＲメモリ８８、最小値＆第２最小値＆符号メモリ８９を含む。βメモリ８６は、計算されたβ及び再計算されたβを格納する。αメモリ８７は、計算されたα及び再計算されたαを格納する。ＬＬＲメモリ８８は、初期値λ、計算されたｓｕｍ及び再計算されたｓｕｍを格納する。各再計算制御部７９乃至８１及び再計算判定部８２が確率演算処理制御部として機能し、各再計算部７５乃至７７を含む確率演算処理部の動作を制御する。
【００６３】
ビットノード処理部７１、チェックノード処理部７２、及び事後確率更新処理部７３による通常のＬａｙｅｒｅｄアルゴリズムと同様の動作は、データ衝突の有無に関わらず、まず着目階層内の全ての確率演算処理に対して実行される。その動作においてチェックノード処理部７２が算出した最小値、第２最小値、及び符号を、最小値＆第２最小値＆符号メモリ８９に保存しておく。データ衝突検出部７４は、階層カウンタが示す検査行列の着目階層について、データ衝突があるか否かを判断する。データ衝突がない場合、データ衝突検出部７４は、着目階層の全ての事後確率ｓｕｍをＬＬＲメモリ８８に上書きする。データ衝突がある場合、データ衝突検出部７４は、ビットノード再計算制御部７９に再計算指示を出す。ビットノード再計算制御部７９は、データ衝突検出部７４からの指示に基づいて、β集合再計算用テーブル８３の示す再計算対象のβについて、ビットノード処理をビットノード再計算部７５に再計算させる。再計算判定部８２は、最小値＆第２最小値＆符号メモリ８９から読み込んだデータとβの再計算の結果とに基づいて、再計算判定を行う。再計算判定部８２は、再計算判定の結果に基づいて、ビットノード再計算制御部７９、チェックノード再計算制御部８０、及び事後確率更新再計算制御部８１に指示を出す。ビットノード再計算制御部７９は、再計算判定部８２からの指示に応じ、β集合再計算用テーブル８３の示す再計算対象のβについて、ビットノード処理をビットノード再計算部７５に再計算させる。チェックノード再計算制御部８０は、再計算判定部８２からの指示に応じ、α集合再計算用テーブル８４の示す再計算対象のαについて、チェックノード処理をチェックノード再計算部７６に再計算させる。事後確率更新再計算制御部８１は、再計算判定部８２からの指示に応じ、ｓｕｍ集合再計算用テーブル８５の示す再計算対象のｓｕｍについて、事後確率更新処理を事後確率更新再計算部７７に再計算させる。着目階層内で再計算すべき集合に対する再計算が終了すると、次の階層に対する確率演算処理が実行される。
【００６４】
図１９は、シミュレーションにより得たＢＥＲ特性結果を示す図である。並列性を可能な限り維持しつつデータ衝突を考慮し複数回の処理により実行する確率演算処理を、ＩＳＤＢ−Ｓ２（Integrated Services Digital Broadcasting via Satellite - Second
Generation）に適用した。この際、ＩＳＤＢ−Ｓ２の１１個の符号化率の中で、最もデータ衝突が大きい符号化率７／８の検査行列を用いて、シミュレーションを行った。シミュレーションは、変調方式ＱＰＳＫ、通信モデルＡＷＧＮ、入力ビット数１０，７７１，２００ビット、ＬＤＰＣ復号処理最大繰返し回数５０回を設定して実行した。ＬＤＰＣ復号処理の繰り返し回数が５０回に到達してもパリティ検査値が満足できない場合には、復号処理を終了するよう設定した。図１９のＢＥＲ特性結果に示されるように、提案手法は、従来の手法に比較して良好なＢＥＲ特性が得られる。１０−４のＢＥＲ特性で比較した場合、提案手法は従来手法より約０．２ｄＢの利得を得ることができた。なお前述の確率演算処理の第１の実施例及び第２の実施例の何れも、正しい更新値を用いた確率演算処理を行なうので、第１の実施例及び第２の実施例の間で結果は同じとなる。
【００６５】
図２０は、ＬＤＰＣ復号器を備えたシステム構成の一例を示す図である。図２０に示すシステムは、復調部１００、ＬＤＰＣ復号器１０１、及び復号データ処理部１０２を副汲む。復調部１００により、アナログ受信信号を復調及びＡＤ変換してデジタル受信データをＬＤＰＣ復号器１０１に供給する。ＬＤＰＣ復号器１０１は、前述の第１の実施例又は第２の実施例の確率演算処理によりＬＤＰＣ復号処理を実行し、デジタル受信データの誤り訂正を行なう。ＬＤＰＣ復号器１０１による誤り訂正後のデータは、復号データ処理部１０２に供給され、復号データ処理部１０２により所望の処理が実行される。
【００６６】
以上、本発明を実施例に基づいて説明したが、本発明は上記実施例に限定されるものではなく、特許請求の範囲に記載の範囲内で様々な変形が可能である。
【００６７】
上記第１の実施例又は第２の実施例の確率演算処理において、チェックノード処理として具体的に如何なる計算をするかは問題ではない。Min-sumアルゴリズムによるチェックノード処理であってよいし、Normalized Min-sumアルゴリズムやOffset Min-sumアルゴリズムのチェックノード処理であってもよい。
【００６８】
なお本願発明は以下の内容を含むものである。
（付記１）
低密度パリティチェック符号化された受信信号に対して、Ｌａｙｅｒｅｄ復号化アルゴリズムにより検査行列の複数の階層の階層毎に確率演算処理を並列に実行して復号処理を行なう復号化装置であって、
前記確率演算処理を並列に実行する確率演算処理部と、
前記確率演算処理部を制御することにより、前記複数の階層のうちの１つの階層内での確率演算処理を、並列性を維持しつつデータ衝突を考慮して複数段の確率演算処理に分け、第１段の処理ではデータ衝突の影響を受けずに正しく計算できる確率演算を含む複数の確率演算処理を並列に実行させ、第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて正しく計算できる確率演算処理を並列に実行させる確率演算処理制御部と
を含む復号化装置。
（付記２）
前記確率演算処理制御部により制御される前記確率演算処理部は、前記第１段の処理においてデータ衝突の影響を受けずに正しく計算できる確率演算を並列に実行し、第２段以降の処理において、前記第１段の処理では未計算であり、データ衝突の影響を受けるために前段までの処理の実行結果を利用して初めて正しく計算できる確率演算を並列に実行することを特徴とする付記１記載の復号化装置。
（付記３）
前記確率演算処理制御部により制御される前記確率演算処理部は、前記第１段の処理において全確率演算を並列に実行し、第２段以降の処理において、データ衝突の影響を受けるために再計算が必要な確率演算処理を並列に実行することを特徴とする付記１記載の復号化装置。
（付記４）
前記確率演算処理制御部により制御される前記確率演算処理部は、第２段以降の処理において、データ衝突の影響を受けるために再計算が必要となる確率演算処理を特定し、該特定された確率演算処理を並列に実行することを特徴とする付記３記載の復号化装置。
（付記５）
前記確率演算処理制御部により制御される前記確率演算処理部は、前記再計算が必要となる確率演算処理を特定する際に、既に再計算した結果の値に応じて再計算が必要となる確率演算処理を特定することを特徴とする付記４記載の復号化装置。
（付記６）
前記確率演算処理は、前記受信信号の確率的な信頼度を表わす事前確率からパリティチェックに基づく受信信号の拘束条件を考慮して事後確率を求める処理であり、
前記事前確率を初期値とする前記事後確率と第１の確率メッセージとから第２の確率メッセージを求めるビットノード処理と、
前記ビットノード処理が求めた前記第２の確率メッセージに基づいて前記第１の確率メッセージの更新値を求めるチェックノード処理と、
前記ビットノード処理が求めた前記第２の確率メッセージと、前記チェックノード処理が求めた前記第１の確率メッセージの更新値とに基づいて、前記事後確率の更新値を求める事後確率更新処理と
を含むことを特徴とする付記１乃至５いずれか一項記載の復号化装置。
（付記７）
低密度パリティチェック符号化された受信信号に対して、Ｌａｙｅｒｅｄ復号化アルゴリズムにより検査行列の複数の階層の階層毎に確率演算処理を並列に実行して復号処理を行なう復号化方法であって、
複数の階層のうちの１つの階層内での確率演算処理を、並列性を維持しつつデータ衝突を考慮して複数段の確率演算処理に分け、
第１段の処理ではデータ衝突の影響を受けずに正しく計算できる確率演算を含む複数の確率演算処理を並列に実行し、
第ｎ段の処理においては第ｎ−１段までの処理の確率演算結果を用いて正しく計算できる確率演算処理を並列に実行する
各段階を含む復号化方法。
（付記８）
前記第１段の処理においてデータ衝突の影響を受けずに正しく計算できる確率演算を並列に実行し、第２段以降の処理において、前記第１段の処理では未計算であり、データ衝突の影響を受けるために前段までの処理の実行結果を利用して初めて正しく計算できる確率演算を並列に実行することを特徴とする付記７記載の復号化方法。
（付記９）
前記第１段の処理において全確率演算を並列に実行し、第２段以降の処理において、データ衝突の影響を受けるために再計算が必要な確率演算処理を並列に実行することを特徴とする付記７記載の復号化方法。
【符号の説明】
【００６９】
４０  ＬＤＰＣ復号器
４１  ビットノード処理部
４２  チェックノード処理部
４３  事後確率更新処理部
４４  パリティ検査部４４
４５  ビットノード処理開始制御部
４６  チェックノード処理開始制御部
４７  事後確率更新処理開始制御部
４８  データ衝突検出部
４９  βメモリ
５０  αメモリ
５１  ＬＬＲメモリ
５２  β集合演算開始テーブル
５３  α集合演算開始テーブル
５４  ｓｕｍ集合演算開始テーブル
【図１】
0005434454.tif 000003
【図２】
0005434454.tif 000004
【図３】
0005434454.tif 000005
【図４】
0005434454.tif 000006
【図５】
0005434454.tif 000007
【図６】
0005434454.tif 000008
【図７】
0005434454.tif 000009
【図８】
0005434454.tif 000010
【図９】
0005434454.tif 000011
【図１０】
0005434454.tif 000012
【図１１】
0005434454.tif 000013
【図１２】
0005434454.tif 000014
【図１３】
0005434454.tif 000015
【図１４】
0005434454.tif 000016
【図１５】
0005434454.tif 000017
【図１６】
0005434454.tif 000018
【図１７】
0005434454.tif 000019
【図１８】
0005434454.tif 000020
【図１９】
0005434454.tif 000021
【図２０】
0005434454.tif 000022