(57)【要約】【課題】本発明は複数の可変ノードおよび複数の制御ノードを含むバイパータイトグラフにより表現できる誤り訂正符号を復号するメッセージパッシングタイプの反復復号法に関し、前記メッセージを対数可能性比により表す。【解決手段】構成上含む可変ノードと制御ノードの各対について、複数の復号反復の各反復において前の反復における送信外部情報（αｍｎ）と比較して、前記可変ノードが前記制御ノードへメッセージとして送信することを意図する外部情報（αｔｅｍｐｍｎ）の符号に変化を検出し、符号変化がある場合に前記外部情報を振幅削減演算（Ｆｒｅｄ）に委ね、その後前記外部情報を制御ノードに送信する。【選択図】図３
2008199623.tif 000002
【特許請求の範囲】
【請求項１】
複数の可変ノードおよび複数の制御ノードを含むバイパータイトグラフにより表現できる誤り訂正符号を復号するためのメッセージパッシングタイプの反復復号法であって、前記メッセージを対数可能性比により表し、構成上含む可変ノードと制御ノードの各対について複数の復号反復の各反復において、前記前の反復における送信外部情報（αｍｎ）と比較して、前記可変ノードが前記制御ノードへメッセージとして送信することを意図する前記外部情報
【数１】
2008199623.tif 000059
の前記符号に変化を検出し、符号変化がある前記場合に前記外部情報を振幅削減演算（Ｆｒｅｄ）に委ね、その後前記外部情報を前記制御ノードに送信することを特徴とする復号方法。
【請求項２】
請求項１に記載の復号法において、前記振幅削減演算が非線形演算であることを特徴とする復号法。
【請求項３】
請求項２に記載の復号法において、前記振幅削減演算が閾値
【数２】
2008199623.tif 000060
と比較して、前記外部情報の絶対値に限界を設ける演算であることを特徴とする復号法。
【請求項４】
請求項３に記載の復号法において、前記閾値を適応的に計算することを特徴とする復号法。
【請求項５】
請求項４に記載の復号法において、前記前の反復における前記可変ノードから前記制御ノードへの前記送信外部情報の前記絶対値として、前記閾値を入手することを特徴とする復号法。
【請求項６】
請求項３に記載の復号法において、前記前の反復における前記可変ノードから前記制御ノードへの前記送信外部情報の前記絶対値の最小値として、前記閾値を入手することを特徴とする復号法。
【請求項７】
請求項１に記載の復号法において、前記振幅削減演算が線形演算であることを特徴とする復号法。
【請求項８】
請求項７に記載の復号法において、前記振幅削減演算が、厳密に正であり、厳密に１より小さい係数による乗算であることを特徴とする復号法。
【請求項９】
請求項８に記載の復号法において、前記係数を適応的に計算することを特徴とする復号法。
【請求項１０】
請求項３乃至請求項６のいずれかに記載の復号法において、厳密に正であり、厳密に１より小さい係数によりそのように処理する前記外部情報の乗算が前記外部情報に限界を設ける前記演算に続くことを特徴とする復号法。
【請求項１１】
請求項１乃至請求項１０の１つに記載の復号法において、
【数３】
2008199623.tif 000061
が前記指標ｎを持つ前記ノードに関連する前記変数の事前値であり、βｍｎが前記指標ｍを持つ前記制御ノードによる前記指標ｎを持つ前記可変ノードへの前記送信メッセージであり、
【数４】
2008199623.tif 000062
により、前記外部情報を計算することを特徴とする復号法。
【請求項１２】
請求項１乃至請求項１１の１つに記載の復号法において、
αｍｎ’が前記指標ｎ’を持つ前記可変ノードから前記指標ｍを持つ前記制御ノードへの前記メッセージを示し、Ｈ（ｍ）が前記指標ｍを持つ前記制御ノードに隣接する前記可変ノードの前記セットであり、ｘが正であればｓｇｎ（ｘ）＝１であり、その他の場合ｓｇｎ（ｘ）＝−１である次式：
【数５】
2008199623.tif 000063
により、前記指標ｎを持つ制御ノードから前記指標ｍを持つ可変ノードへの前記送信メッセージβｍｎを計算することを特徴とする復号法。
【請求項１３】
ソフトウェア手段を含むコンピュータプログラムであって、ソフトウェア手段がコンピュータにおいて動作する場合に前記請求項の１つに記載の前記復号法における前記ステップを実装するようにするソフトウェア手段を含むコンピュータプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信またはデータ記録分野における誤り訂正符号の復号に関係する。より正確には、本発明はＬＤＰＣ（Ｌｏｗ  Ｄｅｎｓｉｔｙ  Ｐａｒｉｔｙ  Ｃｈｅｃｋ、低密度パリティチェック）符号またはターボ符号などのバイパータイトグラフにより表現できる誤り訂正符号の反復メッセージパッシング復号法に関する。
【背景技術】
【０００２】
バイパータイトグラフにより表現できる誤り訂正符号は広く、多様な符号、有利な特性が最近再発見された、１９６２年のＩＥＥＥ情報理論論文誌ＩＴ−８巻２１−２８頁に発表された「低密度パリティチェック符号（Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ）」と題するその文献においてＲ．ガラガー（Ｒ．Ｇａｌｌａｇｅｒ）が最初に記載した特にＬＤＰＣ符号、および１９９６年のＩＥＥＥ情報理論論文誌４４巻１０号１２６１−１２７１頁に掲載のその新境地を開く文献「最適に近い誤り訂正符号化および復号化：ターボ符号（Ｎｅａｒ  ｏｐｔｉｍｕｍ  ｅｒｒｏｒ  ｃｏｒｒｅｃｔｉｎｇ  ｃｏｄｉｎｇ  ａｎｄ  ｄｅｃｏｄｉｎｇ：ｔｕｒｂｏ−ｃｏｄｅｓ）」においてＣ．ベルー（Ｃ．Ｂｅｒｒｏｕ）他が紹介したターボ符号を含む。
【０００３】
用語バイパータイトグラフは無指向性グラフに与え、このグラフでは全てのノードを２つの非結合サブセットにより構成し、いずれか１つのサブセットが持つ２つのノードはグラフのエッジにより相互に接続しない。
【０００４】
幾つかの誤り訂正符号はバイパータイトグラフにより表現できる。符号ワードを構成する記号と関連する第１のサブセットのノードと符号制約、典型的にはパリティ制御と関連する第２のサブセットのノードとにグラフを分割する。制約グループと関連するバイパータイトグラフはタナー（Ｔａｎｎｅｒ）グラフとしても既知である。
【０００５】
符号ワード記号は一般にガロア（Ｇａｌｏｉｓ）フィールドＦ２＝｛０、１｝の要素、換言すればビットであるが、さらに一般的には符号ワード記号は特有の２つのフィールド
【０００６】
【数１】
2008199623.tif 000003
【０００７】
の要素であり、従って２ｐのアルファベットの要素である。以後一般性を失うことなく、ｐ＝１、即ちバイナリ符号の場合に制限することとする。
【０００８】
バイパータイトグラフにより表現できる符号は、ＭＰ（Ｍｅｓｓａｇｅ  Ｐａｓｓｉｎｇ、メッセージパッシング）またはＢＰ（Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ、信頼性の伝播）としても既知の反復メッセージパッシング復号を使用して復号することができる。この復号法に関する一般的記述は、１９９６年の「符号および一般的なグラフに関する復号（Ｃｏｄｅｓ  ａｎｄ  ｄｅｃｏｄｉｎｇ  ｏｎ  ｇｅｎｅｒａｌ  ｇｒａｐｈｓ）」と題するＮ．ワイバーグ（Ｎ．Ｗｉｂｅｒｇ）による文献に見ることができる。反復ＭＰ復号は事実復号分野で良く知られるアルゴリズム、即ちターボ符号に使用する「前進後退」アルゴリズムおよびＬＤＰＣ符号に対するガラガーアルゴリズムの一般化である。
【０００９】
簡単化のため、以後ＬＤＰＣ符号のコンテキストにおけるメッセージパッシングによる反復復号原理を繰り返すこととする。線形符号（Ｋ、Ｎ）を考え、ここでＫは情報ビット数を表す符号の大きさであり、Ｎは符号化ビット数を表す符号長である。Ｍ＝Ｎ−Ｋはパリティビット数、すなわち等価的にパリティ制約数に対応する。
【００１０】
図１に、線形符号（Ｋ、Ｎ）のタナーグラフを示した。グラフの左には、符号ビットに対応する、「可変」タイプのノード、即ちさらに簡単に「可変」ノードとしてさらに示すノードを示し、右にはパリティ制御に対応する、「制御」タイプのノード、即ちさらに簡単に「制御」ノードとしてさらに示すノードを示す。グラフの結合マトリックスは符号パリティマトリックスに対応し、符号パリティマトリックスは次元ＭｘＮを有する。従ってバイパータイトグラフは「可変」タイプのＮノードおよび「制御」タイプのＭノードを含み、ｈｍｎ＝１である場合にのみ可変ノードｎは制御ノードｍに接続する。例えば、図１のグラフは以下のパリティマトリックスを持つ符号（１０、５）に対応する。
【００１１】
【数２】
2008199623.tif 000004
【００１２】
生成器マトリックスＧにより線形符号を定義し、生成器マトリックスの要素はバイナリ値であり、符号ワードｘ＝（ｘ１、ｘ２、、、ｘＮ）は次式により情報ビットワードａ＝（ａ１、ａ２、、、ａＫ）から入手することが一般的に思い出されるであろう。
【００１３】
【数３】
2008199623.tif 000005
【００１４】
全ての符号ワードはパリティ制御を実証するので、以下の式を得る：
【００１５】
【数４】
2008199623.tif 000006
【００１６】
上式で、ＧＴはマトリックスＧの置換を示す。
【００１７】
符号ワードｘを通信チャネルにおいて送信し、データサポートにおいて記録する。受信またはサポートを読み、雑音を伴うｘのバージョンを回復する、即ちｙ＝（ｙ１、ｙ２、、、ｙＮ）である。復号演算は観測ｙからｘ、従ってａを見出すことにある。
【００１８】
反復メッセージパッシング復号原理を記述する前に以下の記法に関して見解を合わせることにする：
【００１９】
Ｈ（ｎ）はバイパータイトグラフにおける可変ノードｎに接続する全ての制御ノード、換言すればノードｎに隣接する全てのノードを示す；
【００２０】
Ｈ（ｍ）はバイパータイトグラフにおける制御ノードｍに接続する全ての可変ノード、換言すればノードｍに隣接する全てのノードである；
【００２１】
αｎはバイパータイトグラフにおける可変ノードｎに関係する事前情報、換言すれば符号ワードの第ｎ番目のビットに関係する事前情報を表す。この情報は受信信号および伝送チャネル特性を考慮する。この情報は復号器入力を構成し、ソフト値の形式で、即ち次の確率により復調器が一般に供給する：
【００２２】
【数５】
2008199623.tif 000007
【００２３】
即ち、さらに便宜的には対数可能性比即ちＬＬＲ（Ｌｏｇ  Ｌｉｋｅｌｉｈｏｏｄ  Ｒａｔｉｏ、対数可能性比）として既知の対数確率比の形式である：
【００２４】
【数６】
2008199623.tif 000008
【００２５】
従って、集中ガウシアン白色雑音（ＡＷＧＮ）およびＢＰＳＫ変調の場合、復調器は単に次式を計算する：
【００２６】
【数７】
2008199623.tif 000009
【００２７】
上式で、σ２は雑音偏差である。
【００２８】
αｍｎは可変ノードｎが制御ノードｍ∈Ｈ（ｎ）へ送信するメッセージを表す。ターボ符号を参照すると、αｍｎは外部情報としてさらに既知である；
【００２９】
βｎｍは対称的に制御ノードｍが可変ノードｎ∈Ｈ（ｍ）へ送信するメッセージを表す。βｎｍもまた外部情報と呼ぶ；
【００３０】
【数８】
2008199623.tif 000010
【００３１】
は可変ノードｎに対する事後情報を表す：事後情報は事前情報αｎおよび可変ノードｎがその隣接制御ノードから復号過程で受信するメッセージβｎｍの双方を考慮する；
【００３２】
【数９】
2008199623.tif 000011
【００３３】
は、ソフト値
【００３４】
【数１０】
2008199623.tif 000012
【００３５】
に対応するハード値であり、換言すればビットｘｎに対して行う決定である。
【００３６】
反復メッセージパッシング復号の原理を図２に示す。
【００３７】
ステップ２１０で、メッセージαｍｎを各可変ノードｎと制御ノードの対ｍ∈Ｈ（ｎ）に対して初期化する。メッセージαｍｎを一般に事前情報により初期化する、換言すればαｍｎ＝αｎ、∀ｍＨ（ｎ）である。反復カウンタＩｔｅｒをまた０に初期化する。
【００３８】
初期化ステップに反復ループが続き、以下のステップを含む：
【００３９】
ステップ２２０で、制御ノードを処理する。より正確には各制御ノードｍに対して、制御ノードｍからそれぞれの可変ノードｎ∈Ｈ（ｍ）宛てのメッセージβｍｎを計算する、即ち：
【００４０】
【数１１】
2008199623.tif 000013
【００４１】
上式で、ＦＣは制御ノードの処理関数を示す。任意の所与ノード対ｍ、ｎ∈Ｈ（ｍ）に対し、制御ノードｍ自体が可変ノードｎ’∈Ｈ（ｍ）−｛ｎ｝から受信したメッセージの関数として、メッセージβｍｎを計算する。可変ノードからそれ自体への外部情報の戻りはないことを結果として注記することにする。制御ノードの処理ステップはまた水平ステップとして既知である。
【００４２】
ステップ２３０で、可変ノードを対称的に処理する。より正確には各可変ノードｎに対して、それぞれの制御ノードｍ∈Ｈ（ｎ）宛てのメッセージαｍｎを計算する、即ち：
【００４３】
【数１２】
2008199623.tif 000014
【００４４】
上式で、ＦＶは可変ノードの処理関数を示す。所与ノード対ｎ、ｍ∈Ｈ（ｎ）に対し、可変ノードｎ自体が制御ノードｍ’∈Ｈ（ｎ）−｛ｍ｝から受信したメッセージの関数として、メッセージαｍｎを計算し、従って以前のようにノードからそれ自体への外部情報の戻りはない。可変ノードの処理ステップはまた垂直ステップとして既知である。
【００４５】
ステップ２４０で、事後情報
【００４６】
【数１３】
2008199623.tif 000015
【００４７】
を事前情報αｎからおよび可変ノードｎがその隣接制御ノードｍ∈Ｈ（ｎ）から受信するメッセージβｍｎから推定し、記号により以下のように表す：
【００４８】
【数１４】
2008199623.tif 000016
【００４９】
上式で、ＦＡＰは事後推定関数を示す。
【００５０】
ステップ２５０で、ソフト値
【００５１】
【数１５】
2008199623.tif 000017
【００５２】
に基づくハード値
【００５３】
【数１６】
2008199623.tif 000018
【００５４】
に関する決定を行う、即ち：
【００５５】
【数１７】
2008199623.tif 000019
【００５６】
上式で、ＦＤは決定関数を示す。ＢＰＳＫ変調の場合典型的に、ソフト値の符号に関する決定を行う、換言すれば
【００５７】
【数１８】
2008199623.tif 000020
【００５８】
とする。以後便宜上、ビット値をその変調値により特定することにする。ビット「０」は従来通り値「＋１」により、ビット「１」は値「−１」により表すこととする。
【００５９】
ステップ２６０で、ベクトル
【００６０】
【数１９】
2008199623.tif 000021
【００６１】
が符号ワードであるか、換言すればベクトルα￣がパリティ制御を満足するかについて調べる。答えが肯定であれば、ステップ２６５でループを抜け、復号ワードは
【００６２】
【数２０】
2008199623.tif 000022
【００６３】
である。答えが否定であれば、ステップ２６７で反復回数を増し、ステップ２７０で実行した反復回数Ｉｔｅｒが閾値Ｉｔｅｒ＿ｍａｘに達したかについて比較を行う。達していなければ、ステップ２２０に再ループすることにより反復復号を続ける。これに失敗すると、復号演算は失敗したと考えられ、ステップ２７５で停止する。
【００６４】
反復ループにおけるステップの順序は図２に開示するものと異なりうる。特に順序を逆にし、可変ノードおよび制御ノードを処理し、次いでメッセージβｍｎを初期化する：βｍｎ＝０、∀ｎ∈｛１、、、Ｎ｝および∀ｍ∈Ｈ（ｎ）により開始することが可能である。
【００６５】
図２に概要を示す反復復号原理によれば、全ての制御ノードを処理し、次いで全ての可変ノードを処理する、または上記のように全ての可変ノードを処理し、次いで全ての制御ノードを処理する。これは「並列スケジューリング」または再度「フラディングスケジューリング」として既知である。その他のタイプのスケジューリングが文献において提案され；これらのタイプを２つに範疇に分類することができる：
−直列タイプのスケジューリングであり、「直列スケジューリング」、「シャッフルＢＰ」、「水平シャッフル」または「垂直シャッフル」として示すスケジューリングタイプを配置することができる範疇である。直列タイプのスケジューリングは制御ノードおよび可変ノード双方に適用することができる。制御ノードに適用する場合、復号には以下の方策を使用する：
・可変ノードｎ∈Ｈ（ｍ）宛てのメッセージβｍｎを計算することにより、単一の制御ノードｍをまず処理する；
・各可変ノードｎ∈Ｈ（ｍ）から制御ノードｍ’∈Ｈ（ｎ）−｛ｍ｝宛てのメッセージαｍ’ｎを更新し、送信する。これら同じ可変ノードに関する事後情報
【００６６】
【数２１】
2008199623.tif 000023
【００６７】
をまた更新する；
・次制御ノードを処理し、制御ノードがなくなるまで前の２つのステップを反復する。
【００６８】
２元的方法では、制御ノード毎に処理を実行する代わりに、可変ノード毎に処理を実行することができる。想定する場合に応じて、「水平シャッフル」順序または「垂直シャッフル」順序について言及することとする。
【００６９】
前述の２つの順序タイプはまた「混合」または「グループシャッフル」順序の形式に混合することができる。混合スケジューリングに対応する復号方策の記述は２００５年２月のＩＥＥＥ通信技術論文誌５３巻２号２０９−２１３頁に記載のＪ．ザン（Ｊ．Ｚｈａｎｇ）他著「シャッフル反復復号（Ｓｈｕｆｆｌｅｄ  ｉｔｅｒａｔｉｖｅ  ｄｅｃｏｄｉｎｇ）」と題する文献に見られよう。方策はノードのグループへの分割に基づき、処理はグループ内で並列であり、１つのグループから次グループへは直列である。より正確には制御グループにおける分割について：
・可変ノードｎ∈Ｈ（ｍｉ）宛てのメッセージβｍｉｎ、ｉ＝１、、、ｇを計算することにより、制御ノード｛ｍ１、ｍ２、、、ｍｇ｝を含む第１のグループＧを処理し；
・各可変ノードｎ∈Ｈ（ｍｉ）、ｉ＝１、、、ｇからそれぞれ制御ノードｍ’∈Ｈ（ｎ）−｛ｍｉ｝宛てのメッセージαｍ’ｎを更新し、送信する。これら同じ可変ノードに関する事後情報
【００７０】
【数２２】
2008199623.tif 000024
【００７１】
をまた更新する；
・次制御ノードグループを処理し、制御ノードグループがなくなるまで前の２つのステップを反復する。
【００７２】
２元的方法では、制御ノードグループへの分割に代わり、可変ノードグループへの分割に基づき演算することが可能である。
【００７３】
ＬＤＰＣ符号に関する反復メッセージパッシング復号に対する２つの主なアルゴリズムが既知である：「対数ＢＰ］としてさらに既知の「ＳＰＡ（Ｓｕｍ  Ｐｒｏｄｕｃｔ
Ａｌｇｏｒｉｔｈｍ（積和アルゴリズム）」および「基部を持つＢＰ］としてさらに既知の「最小和」アルゴリズムである。これら２つのアルゴリズムに関する詳細な記述は記録システムのための符号化および信号処理ＣＲＣハンドブックにおいて公開のＷ．Ｅ．ライアン（Ｗ．Ｅ．Ｒｙａｎ）著「ＬＤＰＣ符号入門」と題する文献に見られ、リンクＷＷＷ．ＣＳＥＥ．ＷＶＵ．ｅｄｕ／ｗｃｒｌ／１ｄｐｃ．ｈｔｍ．から入手可能であろう。
【００７４】
ＳＰＡおよび最小和アルゴリズムは制御ノードの処理ステップにおいてのみ異なり、制御ノードの処理ステップを以下に詳細に示すこととする。その他のステップは同一である、即ち：
【００７５】
可変ノードを処理するステップ２３０は以下のようにメッセージαｍｎを計算することにある：
【００７６】
【数２３】
2008199623.tif 000025
【００７７】
上式で、
【００７８】
【数２４】
2008199623.tif 000026
【００７９】
は制御ノードｍ’∈Ｈ（ｎ）−｛ｍ｝から可変ノードｎが受信する全てのメッセージβｍ’ｎを表し、Ｃｍｎはこれら制御ノードのそれぞれに対して実証するパリティ制御に対応する事象を表す。ｙｎが独立であるとして、αｍｎを以下のようにＬＬＲの形式で表すことができることを示す：
【００８０】
【数２５】
2008199623.tif 000027
【００８１】
事後情報を推定するステップ２４０は以下の計算を含む：
【００８２】
【数２６】
2008199623.tif 000028
【００８３】
上式で、ＢｎはＨ（ｎ）の全ての制御ノードから可変ノードｎが受信するメッセージを表し、Ｃｎはこれら制御ノードのそれぞれに対して実証するパリティ制御に対応する事象を表す。前と同じ仮定において、
【００８４】
【数２７】
2008199623.tif 000029
【００８５】
を以下のようにＬＬＲの形式で表すことができることを示す：
【００８６】
【数２８】
2008199623.tif 000030
【００８７】
式（１２）および式（１４）に従い次式が成立することを注記する：
【００８８】
【数２９】
2008199623.tif 000031
【００８９】
従って可変ノードを処理するステップ２３０を、事後情報を推定した後、反復の最後に配置することができる。ノード（ｍ）が自体に送信する外部情報（ここではβｍｎ）は戻されないことを、式（１５）は意味する。
【００９０】
ハード値の決定に関するステップ２５０を次式により簡単に達成する：
【００９１】
【数３０】
2008199623.tif 000032
【００９２】
上式で、ｘが正であればｓｇｎ（ｘ）＝１であり、その他の場合ｓｇｎ（ｘ）＝−１である。
【００９３】
以下のパリティ制御を計算することにより、ステップ２６０においてハード値に関するパリティ制御の実証を達成する：
【００９４】
【数３１】
2008199623.tif 000033
【００９５】
以下の場合にのみパリティ制御を全て満足する：
【００９６】
【数３２】
2008199623.tif 000034
【００９７】
制御ノードを処理するステップ２２０はＳＰＡアルゴリズムについて次式を計算することにある：
【００９８】
【数３３】
2008199623.tif 000035
【００９９】
上式で、ｃｍ＝１は制御ノードｍに対して満足するパリティ条件を意味し、Ａ＊ｍｎは可変ノードｎ’∈Ｈ（ｍ）−｛ｎ｝から制御ノードｍが受信する全てのメッセージαｍｎ’を表す。βｍｎを次式のごとく表すことができることを示す：
【０１００】
【数３４】
2008199623.tif 000036
【０１０１】
最小和アルゴリズムによる制御ノードの処理は式（２０）の簡単化になる。関数Φ（ｘ）が急速に衰退し、Φ（ｘ）がその逆数と等しければ、即ちΦ（Φ（ｘ））＝ｘであれば、以下の近似を正当に行うことができる：
【０１０２】
【数３５】
2008199623.tif 000037
【０１０３】
最小和復号アルゴリズムがＳＰＡ復号アルゴリズムより十分により簡単であるのは、最小和復号アルゴリズムが加算、比較および符号変更のみを行うからである。加えて、最小和アルゴリズムの実行は雑音偏差σ２の推定とは独立である。その代わり、式（２１）による値βｍｎの近似はＳＰＡ復号アルゴリズムと比較して性能の損失になる。
【０１０４】
ＳＰＡ復号アルゴリズムは実際には最小和アルゴリズムよりより良好に動作するが、それにも関わらず雑音電力を誤って推定する場合その性能は著しく劣化することがある。
【０１０５】
最小和アルゴリズムの種々の修正版が、その性能を改善するために提案されている。例えば、Ｗ．Ｅ．ライアンによる前述の文献は近似式（２１）に修正項を持ち込む。そのように修正するアルゴリズムの性能は、その場合ＳＰＡアルゴリズムの性能に近くなるが、雑音電力の推定誤りに強く依存することになる。加えて、修正項は復号の複雑さをかなり増加させる。２００５年１１月７日の「低複雑度符号器および復号器による速度適応ＬＤＰＣ符号（Ｒａｔｅ−ｃｏｍｐａｔｉｂｌｅ  ＬＤＰＣ  ｃｏｄｅｓ  ｗｉｔｈ  ｌｏｗ  ｃｏｍｐｌｅｘｉｔｙ  ｅｎｃｏｄｅｒ  ａｎｄ  ｄｅｃｏｄｅｒ）」と題する文献３ＧＰＰ  ＴＳＧ  ＲＡＮ  ＷＧ１  ＃４３では、この修正版はさらに洗練されている。その文献で開示される方法はδの最小値αｍｎ’に対してのみ式（２１）に修正項を持ち込むことにあり、換言すれば式（２０）に最も貢献する値のみを持ち込む。とはいえ雑音電力の推定誤りには、このアルゴリズムは敏感のままである。
【０１０６】
【非特許文献１】ＩＥＥＥ情報理論論文誌ＩＴ−８巻２１−２８頁、１９６２年
【非特許文献２】ＩＥＥＥ情報理論論文誌４４巻１０号１２６１−１２７１頁、１９９６年１０月
【非特許文献３】ＩＥＥＥ通信技術論文誌５３巻２号２０９−２１３頁、２００５年２月
【非特許文献４】３ＧＰＰ  ＴＳＧ  ＲＡＮ  ＷＧ１  ＃４３、２００５年１１月７日
【非特許文献５】ＷＷＷ．ＣＳＥＥ．ＷＶＵ．ｅｄｕ／ｗｃｒｌ／１ｄｐｃ．ｈｔｍ．
【発明の開示】
【発明が解決しようとする課題】
【０１０７】
本発明の全般的な目的はメッセージパッシングタイプの反復復号アルゴリズムを提案することであり、このアルゴリズムはバイパータイトグラフにより表現することができる誤り訂正符号の復号を可能にし、誤り率および収斂速度に関して最小和アルゴリズムよりより良好に実行し、一方複雑さおよびＳＰＡアルゴリズムの雑音推定に対する敏感性はない。
【課題を解決するための手段】
【０１０８】
本発明は、複数の可変ノードおよび複数の制御ノードを含むバイパータイトグラフにより表現できる誤り訂正符号を復号する反復メッセージパッシング復号法として定義し、前記メッセージを対数可能性比により表す。複数の復号反復の各反復において可変ノードと制御ノードを含む各対について、前の反復における送信外部情報と比較して、前記可変ノードが前記制御ノードへメッセージとして送信することを意図する外部情報の符号変化を検出し、符号変化がある場合に前記外部情報を振幅削減演算に委ね、その後前記外部情報を前記制御ノードに送信する。
【０１０９】
第１の代替実施形態によれば、振幅削減演算は非線形演算である。例えば振幅削減演算は閾値と比較して、前記外部情報の絶対値に限界を設ける演算である。好ましくは、閾値を適応的に計算する。
【０１１０】
第１の適応例の法則によれば、前の反復における前記可変ノードから前記制御ノードへの送信外部情報の絶対値として、閾値を入手する。
【０１１１】
第２の適応例の法則によれば、前の反復における前記可変ノードから前記制御ノードへの送信外部情報の絶対値の最小値として、前記閾値を入手する。
【０１１２】
第２の代替実施形態によれば、振幅削減演算は線形演算であり、厳密に正であり、厳密に１より小さい係数による例えば乗算である。有利には、前記係数を適応的に計算する。
【０１１３】
第３の例によれば、厳密に正であり、厳密に１より小さい係数によりそのように処理する外部情報の乗算が外部情報に限界を設ける演算に続く。
【０１１４】
【数３６】
2008199623.tif 000038
【０１１５】
が指標ｎを持つ可変ノードに関連する変数の事前値であり、βｍｎが指標ｍを持つ制御ノードによる指標ｎを持つ可変ノードへの送信メッセージである、
【０１１６】
【数３７】
2008199623.tif 000039
【０１１７】
により、前記外部情報を計算することができる。
【０１１８】
αｍｎ’が、指標ｎ’を持つ可変ノードから指標ｍを持つ制御ノードへのメッセージを示し、Ｈ（ｍ）が指標ｍを持つ制御ノードに隣接する可変ノードのセットであり、ｘが正であればｓｇｎ（ｘ）＝１であり、その他の場合ｓｇｎ（ｘ）＝−１である次式：
【０１１９】
【数３８】
2008199623.tif 000040
【０１２０】
により、指標ｎを持つ制御ノードから指標ｍを持つ可変ノードへのメッセージβｍｎを計算することができる。
【０１２１】
本発明は、またソフトウェア手段を含むコンピュータプログラムに関し、ソフトウェア手段はコンピュータにおいて動作する場合以上に開示する復号法におけるステップを実装するようにする。
【発明を実施するための最良の形態】
【０１２２】
Ｎ可変ノードおよびＭ制御ノードを持つバイパータイトグラフにより表現できる誤り訂正符号に対するさらなる考察を提示する。説明のため、一般性を失うことなく、この訂正符号がＬＤＰＣ符号であることを以後仮定しよう。
【０１２３】
本発明は以下の事実を明らかにすることに基づく：可変ノードからのメッセージ、換言すればＬＬＲ形式で表す外部情報値αｍｎが１つの反復から次に対して変動する場合、即ち一般的に可変ノードからのメッセージが変動パターンを再現する場合、最小和アルゴリズムは収斂しないか、または非常に緩やかに収斂するのみである。値αｍｎにおける変動は一般に受信ワードにおける雑音分散による。本発明の原理は、これらの変動が生じる場合にこれらの変動を緩和し、アルゴリズムが収斂状態に入るようにすることである。
【０１２４】
図３は本発明の一実施形態による復号処理を表す。ステップ３１０、３６０、３６５、３６７，３７０および３７５は図２のステップ２１０、２６０、２６５、２６７、２７０および２７５にそれぞれ同じである。ステップ３２０は図２のステップ２２０に対応し、最小和アルゴリズムによる式（２１）におけるメッセージβｎｍの推定を説明している。ステップ３４０は図２のステップ２４０に対応し、事後値
【０１２５】
【数３９】
2008199623.tif 000041
【０１２６】
に関する式（１４）を説明している。最後に、ステップ３５０は図２のステップ２５０に対応し、決定関数式（１６）を明示している。
【０１２７】
外部情報値αｍｎをテーブルに蓄積し、このテーブルを各反復において更新することを仮定することとする。式（１５）
【０１２８】
【数４０】
2008199623.tif 000042
【０１２９】
からＬＬＲ形式の新しい外部値を計算することにより、ステップ３３０は開始する。一方従来の最小和復号処理と違って、そのように計算する各値を中間値としてまず蓄積し、その後処理し、次いで外部情報値テーブルに蓄積する。ステップ３３０においてｎおよびｍの値に関して処理を順番に行い、従って１つの中間値のみが必要であることを注記することとする。
【０１３０】
中間値
【０１３１】
【数４１】
2008199623.tif 000043
【０１３２】
の符号を既に蓄積したαｍｎの符号、換言すれば前の反復において入手し、可変ノードｎから制御ノードｍへメッセージとして送信する外部情報値の符号と比較する。これらの符号が同じ、即ち
【０１３３】
【数４２】
2008199623.tif 000044
【０１３４】
であれば、振動はなく、αｍｎを
【０１３５】
【数４３】
2008199623.tif 000045
【０１３６】
によりリフレッシュし、制御ノードｍに対する場合にこの値を送信する。
【０１３７】
一方、２つの符号が異なれば、即ち
【０１３８】
【数４４】
2008199623.tif 000046
【０１３９】
であれば、符号切り替えにより値
【０１４０】
【数４５】
2008199623.tif 000047
【０１４１】
の信頼性の欠如を伝達する。
【０１４２】
【数４６】
2008199623.tif 000048
【０１４３】
の振幅を削減することにより、この信頼性の欠如を考慮する。次いで、そのように入手する、即ち：
【０１４４】
【数４７】
2008199623.tif 000049
【０１４５】
のように入手する値により、αｍｎをリフレッシュし、この値を制御ノードｍに送信する。
【０１４６】
第１の代替実施形態によれば、振幅削減演算
【０１４７】
【数４８】
2008199623.tif 000050
【０１４８】
は非線形、例えば限界を設ける演算である。その場合、値αｍｎを次式により更新する：
【０１４９】
【数４９】
2008199623.tif 000051
【０１５０】
上式で、αＴｍｎは可変ノードｎおよび制御ノードｍに関連する正の閾値である。有利には、閾値αＴｍｎ、１≦ｍ≦Ｍ、１≦ｎ≦Ｎを適応的に入手する。より正確には、閾値を事前情報の絶対値、即ち
【０１５１】
【数５０】
2008199623.tif 000052
【０１５２】
により（ステップ３１０で）初期化し、次いで適応法則手段により更新する。
【０１５３】
第１の適応例の法則によれば、各ノード対（ｎ、ｍ）に対して現在の反復閾値は前の反復が持つ外部情報の絶対値に等しい、換言すれば式（２３）の計算に次の演算が先行する：
【０１５４】
【数５１】
2008199623.tif 000053
【０１５５】
従って符号切り替えの場合前の反復からのメッセージの絶対値により、現在の反復におけるメッセージαｍｎの振幅を制限する。
【０１５６】
第２の適応例の法則によれば、各ノード対（ｎ、ｍ）に対して現在の反復閾値は同じノード対に対する前の反復からの外部情報の最小絶対値に等しい、換言すればステップ３３０は以下のように体系的な閾値の更新を含む：
【０１５７】
【数５２】
2008199623.tif 000054
【０１５８】
この場合等価な方法で以下により、ステップ３３０を実装することができる：
【０１５９】
【数５３】
2008199623.tif 000055
【０１６０】
上式で、
【０１６１】
【数５４】
2008199623.tif 000056
【０１６２】
はノード対（ｎ、ｍ）に対して観測する外部情報の最小振幅である。
【０１６３】
第２の実施形態によれば、振幅削減演算は線形（ＬＬＲにより）である。換言すれば、符号切り替えを検出すれば、外部情報の振幅は以下のように減衰する：
【０１６４】
【数５５】
2008199623.tif 000057
【０１６５】
上式で、λは係数であり、０＜λ＜１である。有利には、実装のためλ＝１−２−ｂを選択することとし、ｂは厳密に正整数である。
【０１６６】
係数λは適応的であるように選択することができる。
【０１６７】
第３の実施形態によれば、振幅削減演算は線形演算と非線形演算、例えば前記のように限界を設ける演算と減衰演算の組み合わせでありうる。外部情報はその場合式（２３）と式（２７）を組み合わせることにより更新する：
【０１６８】
【数５６】
2008199623.tif 000058
【０１６９】
本発明の範囲を逸脱することなく、振幅削減演算に関するその他の代替実施形態、線形または非線形、適応的または非適応的もまた考えられる。非線形演算の中では、原点に基礎を置くＳ字状関数を特に使用することができる。
【０１７０】
制御ノードにより開始する並列順序の場合について、本発明を説明した。一方本発明は可変ノードにより開始する並列順序にも適合することは当業者に明らかである。本発明はまた以上で定義したように直列および混合順序にも適合する。
【０１７１】
図４を使用して、有意の信号対雑音比の範囲について本発明の最小和アルゴリズム（ｉｎｖｅｎｔｉｖｅ  Ｍｉｎ−Ｓｕｍ  ａｌｇｏｒｉｔｈｍ、ＩＭＳＡ）と従来の最小和およびＳＰＡアルゴリズムの性能を誤り率（ＢＥＲ）により比較することができる。この場合、式（２６）により与えられる閾値に関する適応法則の第２の例を使用した。実行する反復回数は全ての場合に２００に等しい。使用する２つの符号は非規則的なＬＤＰＣ符号［１００８、２０１６］および［４０３２，８０６４］であり、それ故出力は１／２である。チャネルはＡＷＧＮ（Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅ、付加白色ガウシアン雑音）であると仮定し、変調はＱＰＳＫである。
【０１７２】
本発明の最小和アルゴリズムの性能はＳＰＡアルゴリズムの性能に非常に近く、複雑度については従来の最小和アルゴリズムの複雑度と同等であることを注記する。
【０１７３】
本発明はバイパータイトグラフにより表現できる誤り訂正符号、特にＬＤＰＣ符号またはターボ符号の復号に適合する。データ記録または通信分野において、特に既にＬＤＰＣ符号を使用する通信システム、例えば規格ＩＥＥＥ８０２．３ａ（イーサネット（登録商標）１０Ｇビット／秒）、ＤＶＢ−Ｓ２（衛星ビデオ一斉送信）、ＩＥＥＥ８０２．１６（ＷｉＭＡＸ）に準拠する通信システム、または例えば規格ＩＥＥＥ８０２．１１（ＷＬＡＮ）およびＩＥＥＥ８０２．２０（移動広帯域無線アクセス）に準拠するシステムに本発明を使用することができる。
【図面の簡単な説明】
【０１７４】
【図１】符号（Ｋ、Ｎ）に対するタナーグラフの例を示す。
【図２】従来技術から既知の反復メッセージパッシング復号原理を図式で示す。
【図３】本発明の一実施形態による反復メッセージパッシング復号法を図式で示す。
【図４】２つの特定のＬＤＰＣ符号に対して本発明の復号法により得られる誤り率を従来技術と比較して示す。
【符号の説明】
【０１７５】
Ｍ  パリティビット数
ｍ  制御ノード
Ｎ  符号長
ｎ  可変ノード
【図１】
2008199623.tif 000064
【図２】
2008199623.tif 000065
【図３】
2008199623.tif 000066
【図４】
2008199623.tif 000067
【外国語明細書】
2008199623.tif 000068
2008199623.tif 000069
2008199623.tif 000070
2008199623.tif 000071
2008199623.tif 000072
2008199623.tif 000073
2008199623.tif 000074
2008199623.tif 000075
2008199623.tif 000076
2008199623.tif 000077
2008199623.tif 000078
2008199623.tif 000079
2008199623.tif 000080
2008199623.tif 000081
2008199623.tif 000082
2008199623.tif 000083
2008199623.tif 000084
2008199623.tif 000085
2008199623.tif 000086
2008199623.tif 000087
2008199623.tif 000088
2008199623.tif 000089
2008199623.tif 000090
2008199623.tif 000091
2008199623.tif 000092
2008199623.tif 000093
2008199623.tif 000094
2008199623.tif 000095
2008199623.tif 000096
2008199623.tif 000097
2008199623.tif 000098
2008199623.tif 000099
2008199623.tif 000100