(57)【要約】  本発明は、パリティ検査行列と関連付けられた２部グラフの変数ノードと制御ノードとの間でメッセージを交換する種類の、パリティ検査行列符号に従って信号値で表された受信語を反復復号するための機器に関し、前記方法は少なくとも、変数ノードの少なくとも１つのメッセージを、変数ノードに対応する位置に最尤のシンボルを有する確率と前記位置に現在のシンボルを有する確率との比を表す情報によって、前記値に従って設定するステップと、制御ノードから定められた変数ノードへの、定められたシンボルに関連する少なくとも１つのメッセージを、制御ノードにおいて定められた変数ノードとは異なる変数ノードから受け取られる、それぞれが式に対応するシーケンス内の前記異なる変数ノードと関連付けられたシンボルに関連するメッセージの最大値によって、定められた変数ノードのところの前記定められたシンボルを使った制御ノードの式に対応するシンボルシーケンスの間で、選択される最小値として求めるステップと、シンボルの集合全体に関連する変数ノードから制御ノードへのメッセージを、前記メッセージの最小値がゼロになるように求めるステップとを含む。
2010511337.tif 000002
【特許請求の範囲】
【請求項１】
パリティ検査行列と関連付けられた２部グラフの変数ノードと制御ノードとの間のメッセージの交換を使用する種類の、パリティ検査行列符号に従って信号値で表された受信語を反復復号する方法であって、
変数ノードからの少なくとも１つのメッセージを、変数ノードに対応する位置に最も有望なシンボルを有する確率と前記位置に現在のシンボルを有する確率との比を表す情報によって、前記値の関数として初期設定するステップと、
制御ノードから特定の変数ノードへの、特定のシンボルに関連する少なくとも１つのメッセージを、特定の変数ノードのところの前記特定のシンボルを使って制御ノードにおいて式を満たすシンボルのシーケンスの間で、制御ノードにおいて特定の変数ノード以外の変数ノードから受け取られる、それぞれが式を満たすシーケンス内のその別の変数ノードと関連付けられたシンボルに関連するメッセージの最大値が取る最小値として求めるステップと、
すべてのシンボルに関連する変数ノードから制御ノードへのメッセージを、前記メッセージの最小値がヌルになるように求めるステップと
のうちの少なくとも１つを含むことを特徴とする、方法。
【請求項２】
変数ノードからのメッセージを初期設定するステップが、
アルファベットの各シンボルごとに、シンボルの非ヌルビットと、変数ノードに対応する位置とに関連する２進対数尤度比の和を求めるステップと、
そのように求められた和の最小値を求めるステップと、
求められた各和からそのように求められた最小値を減じるステップと
を含む、請求項１に記載の復号方法。
【請求項３】
変数ノードのところのシンボルに関連する初期メッセージと、変数ノードにおいて受け取られる、シンボルに関連するすべてのメッセージとの和のような、前記変数ノードとシンボルとに関連する事後情報を求めるステップ
を含む、請求項１または２に記載の復号方法。
【請求項４】
各変数ノードごとに、その事後情報が最小であるシンボルを求めるステップと、
このようにしてすべての変数ノードについて求められたシンボルのシーケンスが符号語である場合、前記符号語を推定語として使用するステップと
を含む、請求項３に記載の復号方法。
【請求項５】
変数ノードから所与の制御ノードへのメッセージを求めるステップが、
各シンボルごとに、前記変数ノードのところのシンボルに関連する初期メッセージと、変数ノードにおいて所与の制御ノード以外の制御ノードから受け取られる、シンボルに関連するすべてのメッセージとの和を求めるステップと、
そのように求められた和の最小値を求めるステップと、
各シンボルごとに、そのように求められたシンボルに関連する和からそのように求められた最小値を減じるステップと
を含む、請求項１から４のいずれか一項に記載の復号方法。
【請求項６】
制御ノードから特定の定められた変数ノードへの少なくとも１つのメッセージを求めるステップが、
各シンボルごとに、制御ノードにおいて制御ノードと関連付けられた変数ノードの一部分だけから受け取られるメッセージの最大値が取る最小値と等しい中間値を求めるステップと、
中間値と、制御ノードと関連付けられた前記部分に属さない変数ノードから受け取られるメッセージとから、最大値が取る最小値を求めるステップと
を含む、請求項１から５のいずれか一項に記載の復号方法。
【請求項７】
符号のアルファベットに属するシンボルの対の間で、それぞれが各対の２つのシンボルと関連付けられた２つの値の最大値の最小値を求めるステップであり、
それぞれが特定の範囲内に含まれる値と関連付けられているシンボルを集約する集合を求めるサブステップと、
求められた集合の間で、選択された集合を再結合したものが少なくとも所定数のシンボルを含むように集合を選択するサブステップと、
各値が別々の範囲に対応する選択された集合に含まれるシンボルと関連付けられているときに、より大きい範囲に対応する集合に含まれるシンボルと関連付けられた値を２つの値の最大値として使用するサブステップと、
２つの値の最大値の比較により、各値が、同じ範囲に対応する選択された集合に含まれるシンボルと関連付けられているかどうか判定するサブステップと
を含む前記ステップ
を含む、請求項１から６のいずれか一項に記載の復号方法。
【請求項８】
符号が非２進アルファベット符号である、請求項１から７のいずれか一項に記載の復号方法。
【請求項９】
パリティ検査行列と関連付けられた２部グラフの変数ノードと制御ノードとの間のメッセージの交換を使用する種類の、パリティ検査行列符号に従って信号値で表された受信語を反復復号する機器であって、
変数ノードからの少なくとも１つのメッセージを、変数ノードに対応する位置に最も有望なシンボルを有する確率と前記位置に現在のシンボルを有する確率との比を表す情報によって、前記値の関数として初期設定する手段、および／または、
制御ノードから特定の変数ノードへの、特定のシンボルに関連する少なくとも１つのメッセージを、特定の変数ノードのところの前記特定のシンボルを使って制御ノードにおいて式を満たすシンボルのシーケンスの間で、制御ノードにおいて特定の変数ノード以外の変数ノードから受け取られる、それぞれが式を満たすシーケンス内のその別の変数ノードと関連付けられたシンボルに関連するメッセージの最大値が取る最小値として求める手段、および／または、
シンボルの集合に関連する変数ノードから制御ノードへのメッセージを、前記メッセージの最小値がヌルになるように求める手段
を備えることを特徴とする、機器。
【請求項１０】
変数ノードからのメッセージを初期設定する手段が、
アルファベットの各シンボルごとに、シンボルの非ヌルビットと、変数ノードに対応する位置とに関連する２進対数尤度比の和を求める手段と、
求められた和の最小値を求める手段と、
そのように求められた各和からそのように求められた最小値を減じる手段と
を備える、請求項９に記載の復号機器。
【請求項１１】
変数ノードのところのシンボルに関連する初期メッセージと、変数ノードにおいて受け取られる、シンボルに関連するすべてのメッセージとの和のような、前記変数ノードとシンボルとに関連する事後情報を求める手段を備える、請求項９または１０に記載の復号機器。
【請求項１２】
各変数ノードごとに、その事後情報が最小であるシンボルを求める手段と、
前記シーケンスが符号語である場合、前記符号語を推定語として使用する手段と
を備える、請求項１１に記載の復号機器。
【請求項１３】
変数ノードから所与の制御ノードへのメッセージを求める手段が、
各シンボルごとに、前記変数ノードのところのシンボルに関連する初期メッセージと、変数ノードにおいて所与の制御ノード以外の制御ノードから受け取られる、シンボルに関連するすべてのメッセージとの和を求める手段と、
そのように求められた和の最小値を求める手段と、
各シンボルごとに、そのように求められたシンボルに関連する和からそのように求められた最小値を減じる手段と
を備える、請求項９から１２のいずれか一項に記載の復号機器。
【請求項１４】
制御ノードから特定の変数ノードへの少なくとも１つのメッセージを求める手段が、
各シンボルごとに、制御ノードにおいて制御ノードと関連付けられた変数ノードの一部分だけから受け取られるメッセージの最大値が取る最小値と等しい中間値を求める手段と、
中間値、および制御ノードと関連付けられた前記部分に属さない変数ノードから受け取られるメッセージの最大値が取る最小値を求める手段と
を備える、請求項９から１３のいずれか一項に記載の復号機器。
【請求項１５】
符号のアルファベットに属するシンボルの対の中から、それぞれが各対の２つのシンボルと関連付けられた２つの値の最大値の最小値を求める手段が、
それぞれが特定の範囲内に含まれる値と関連付けられているシンボルを集約する集合を求める手段と、
そのように求められた集合の間で、選択された集合を再結合したものが少なくとも所定数のシンボルを含むように集合を選択する手段と、
各値が別々の範囲に対応する選択された集合に含まれるシンボルと関連付けられているときに、より大きい範囲に対応する集合に含まれるシンボルと関連付けられた値を２つの値の最大値として使用する手段と、
２つの値の最大値の比較により、各値が、同じ範囲に対応する選択された集合に含まれるシンボルと関連付けられているかどうか判定する手段と
を備える、請求項９から１４のいずれか一項に記載の復号機器。
【請求項１６】
符号が非２進アルファベット符号である、請求項９から１５のいずれか一項に記載の復号機器。
【請求項１７】
請求項９から１６のいずれか一項に記載の機器を備える通信装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、復号方法および復号機器、ならびにこのような復号機器を含む通信装置に関する。
【背景技術】
【０００２】
（一般にＫで表される長さの）情報語の（一般にＮ＞ＫであるＮで表される長さの）符号語への符号化が使用されるのは、干渉を受ける通信路における情報の伝送や（光ディスク上のひっかき傷といった）損傷を被りやすい媒体上での情報の記憶の場合のように、たとえ元の情報の一部が誤っており、または失われた場合でさえも元の情報全体を取り出すために、関連する情報に冗長性を付加することが必要とされるときである。
【０００３】
元の情報語を取り出すために受信時に（または記憶の場合には読取り時に）実行される復号は、一般に、誤りがあったとしても、冗長性が導入されているために、受け取られた語（記憶の場合に読み取られた語を指すのにも使用される語彙）から送られた（または記憶された）符号語を正確に取り出すことである誤りを訂正する第１のフェーズと、さらに、符号化時に実施された操作の逆の操作を実行することである、「逆マッピング」フェーズとを含む。
【０００４】
この状況においては、例えば、論文「Ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ」、Ｒ．Ｇａｌｌａｇｅｒ著、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第ＩＴ−８巻、２１−２８頁、１９６２年などに記載されている、低密度パリティ検査符号（以下、ＬＤＰＣ符号という）が知られている。
【０００５】
ＬＤＰＣ符号が特に興味深いのは、これらの符号が通信路の容量（シャノン限界）にきわめて近く、符号化率と性能の間で可能な限り最善の解決（ギルバート＝バルシャモフ限界に近い）を提供するだけでなく、これらの符号がメッセージパッシング型の反復復号も可能にするからである。
【０００６】
これまで、ＬＤＰＣ符号が（その情報を表すシンボルが０または１である、すなわちガロア体ＧＦ（２）において取られる）２進符号であるにせよ、（シンボルがｑ＞２であるガロア体ＧＦ（ｑ）において取られる）非２進符号であるにせよ、ＬＤＰＣ符号を復号する２つの主要なアルゴリズムが提案されている。
【０００７】
第１のアルゴリズムは、前記の論文において、「確率的復号（ｐｒｏｂａｂｉｌｉｓｔｉｃ  ｄｅｃｏｄｉｎｇ）」という名称で提案されており、一般には、ＳＰＡ（「Ｓｕｍ−Ｐｒｏｄｕｃｔ  Ａｌｇｏｒｉｔｈｍ：Ｓｕｍ−Ｐｒｏｄｕｃｔアルゴリズム」）またはＢＰ（「Ｂｅｌｉｅｆ  Ｐｒｏｐａｇａｔｉｏｎ：確信度伝搬」）復号法として知られている（以後この名称で示す）。このアルゴリズムは一般に最適と認められる。これは、ＳＰＡ復号法は、ＬＤＰＣ符号と関連付けられた２部グラフが閉路を含まないという条件で、最尤に向かって収束するからである。しかし、非２進ＬＤＰＣ符号の場合、実際の通信システムではそのダイナミックレンジが非常に広く、実施される計算の不安定度が高まるため、このアルゴリズムは使用できない。さらにこのアルゴリズムは必然的に多数の積を生じるために複雑になり、また熱雑音の知識にも左右される。
【０００８】
第２の準最適な復号アルゴリズムは、主にＭＳＡ（「Ｍｉｎ−Ｓｕｍ  Ａｌｇｏｒｉｔｈｍ：Ｍｉｎ−Ｓｕｍアルゴリズム」）という名称で知られている。ＭＳＡは、ＳＰＡほど複雑ではなく、熱雑音の知識とも無関係であるが、ＳＰＡと比べて、一般に、ＡＷＧＮ（「Ａｄｄｉｔｉｖｅ  Ｗｈｉｔｅ  Ｇａｕｓｓｉａｎ  Ｎｏｉｓｅ：付加白色ガウス雑音」）通信路では０．２５ｄＢから１ｄＢまで変動する、符号化率、不規則性、または使用される符号の長さの関数としての２進誤り率の点での性能損を被る。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
したがって、この状況において本発明は特に、（ＭＳＡなどと比べて）優れた性能と、最適アルゴリズム（ＳＰＡ）と比べて低い計算量とが組み合わされた、ＬＤＰＣ符号、特に非２進ＬＤＰＣ符号の復号のための解決法を提案しようとするものである。
【課題を解決するための手段】
【００１０】
したがって本発明は、パリティ検査行列と関連付けられた２部グラフの変数ノードと制御ノードとの間のメッセージの交換を使用する種類の、パリティ検査行列符号に従って信号値で表された受信語を反復復号する方法であって：
変数ノードからの少なくとも１つのメッセージを、変数ノードに対応する位置に最も有望なシンボルを有する確率と前記位置に現在のシンボルを有する確率との比を表す情報によって、前記値の関数として初期設定するステップと、
制御ノードから特定の変数ノードへの、特定のシンボルに関連する少なくとも１つのメッセージを、特定の変数ノードのところの前記特定のシンボルを使って制御ノードにおいて式を満たすシンボルのシーケンスの間で、制御ノードにおいて特定の変数ノード以外の変数ノードから受け取られる、それぞれが式を満たすシーケンス内のその別の変数ノードと関連付けられたシンボルに関連するメッセージの最大値が取る最小値として求めるステップと、
すべてのシンボルに関連する変数ノードから制御ノードへのメッセージを、前記メッセージの最小値がヌルになるように求めるステップと
のうちの少なくとも１つを含むことを特徴とする方法を提案する。
【００１１】
提案する解決法（以下、ＭＭＡ（「Ｍｉｎ−Ｍａｘ  Ａｌｇｏｒｉｔｈｍ：Ｍｉｎ−Ｍａｘアルゴリズム」）という）は、後述する実施形態から明らかになるように、少ない計算量で優れた性能を達成する。
【００１２】
実際には、変数ノードからのメッセージを初期設定するステップは:
アルファベットの各シンボルごとに、シンボルの非ヌルビットに関連する、変数ノードに対応する位置までの２進対数尤度比の和を求めるステップと、
求められた和の最小値を求めるステップと、
そのように求められた各和からそのように求められた最小値を減じるステップと
を含む。
【００１３】
さらにこの方法は、変数ノードにおけるシンボルに関連する初期メッセージと、変数ノードにおいて受け取られる、シンボルに関連するすべてのメッセージの和のような、変数ノードとシンボルとに関連する事後情報を求めるステップを含むこともでき、この場合、反復プロセスの終わりは、以下のように決定することができる：
各変数ノードごとに、事後情報が最小であるシンボルを求め、
そのようにすべての変数ノードについて求められたシンボルのシーケンスが符号語である場合、前記符号語を推定語として使用する。
【００１４】
変数ノードから所与の制御ノードへのメッセージを求める一実施形態は：
各シンボルごとに、前記変数ノードのところのシンボルに関連する初期メッセージと、変数ノードにおいて所与の制御ノード以外の制御ノードから受け取られる、シンボルに関連するすべてのメッセージの和を求めるステップと、
そのように求められた和の最小値を求めるステップと、
各シンボルごとに、そのように求められたシンボルに関連する和からそのように求められた最小値を減じるステップと
を含む。
【００１５】
制御ノードからそのように決定された変数ノードへの少なくとも１つのメッセージを求めるステップの実施では、後者は、例えば：
各シンボルごとに、制御ノードにおいて制御ノードと関連付けられた各変数ノードの一部分だけから受け取られるメッセージの最大値が取る最小値と等しい中間値を求めるステップと、
中間値と、制御ノードと関連付けられた前記部分に属さない変数ノードから受け取られたメッセージとから、最大値が取る最小値を求めるステップと
を含むことができる。
【００１６】
これら２つのステップは、より正確には：
各シンボルごとに、前記制御ノードに接続された変数ノードの一部分だけと関連付けられたシンボルのシーケンスの間で、シーケンスのシンボルの和に前記各変数ノードに対応する行列内の係数を掛け合わせたものがそのように求められた前記シンボルと等しくなるように、制御ノードにおいて前記部分の変数ノードから受け取られる、それぞれが前記シーケンス内のその変数ノードと関連付けられたシンボルに関連するメッセージの最大値が取る最小値と等しい中間値を求めるステップと、
各シンボルごとに、第１のシンボルが以前に計算された変数ノードの一部分に対応する中間値と関連付けられており、第２のシンボルが前記部分に属さない新しい変数ノードと関連付けられているシンボルの対の間で、第１のシンボルと第２のシンボルの和に対応する変数ノードの行列内の係数を掛け合わせたものがそのように求められた前記シンボルと等しくなるように、前記対の第１のシンボルに対して以前に計算された中間値と、制御ノードにおいて新しい変数ノードから受け取られる、前記対の第２のシンボルに関連するメッセージとの間の最大値が取る最小値と等しい新しい中間値を再帰的に求めるステップとして記述することができる。このようにして計算される新しい中間値は、旧い部分と新しい変数ノードを含む変数ノードの新しい部分に対応するものである。
【００１７】
これ（以下「ｆｏｒｗａｒｄ−ｂａｃｋｗａｒｄ」という）は著しく実際的な実施形態であり、最大値の最小値を探索しなければならない変数ノードの数（すなわち次元）を（好ましくは２まで）限定する。
【００１８】
さらに、以下で提案する一実施形態（「選択的実施法」）において、方法は、符号のアルファベットに属するシンボルの対の間で、それぞれが各対の２つのシンボルと関連付けられている２つの値の最大値の最小値を求めるステップであり：
それぞれが特定の範囲内に含まれる値と関連付けられているシンボルを集約する集合を求めるサブステップと、
求められた集合の間で、選択された集合を再結合したものが少なくとも所定数（この所定数は、本明細書で考察し、「ｍｉｎ−ｍａｘ式」という名称として後述する最大値の最小値の計算に十分な数である）のシンボルを含むような集合を選択するサブステップと、
各値が別々の範囲に対応する選択された集合に含まれるシンボルと関連付けられているときに、より大きい間隔に対応する集合に含まれるシンボルと関連付けられた値を２つの値の最大値として使用するサブステップと、
２つの値の最大値の比較により、各値が、同じ範囲に対応する選択された集合に含まれるシンボルと関連付けられているかどうか判定するサブステップと
を含むステップを含む。
【００１９】
取られた値に従い、実際にはその値の整数部分を使って各シンボルを集合へとグループ化すると、関与するシンボルの数が大幅に低減され、関与するシンボルと関連付けられる値の比較が単純化される。
【００２０】
符号は例えば非２進アルファベット符号などであり、この場合、提案する方法は特に興味深いものとなる。
【００２１】
また本発明は、パリティ検査行列と関連付けられた２部グラフの変数ノードと制御ノードとの間のメッセージの交換を使用する種類の、パリティ検査行列符号に従って信号値で表された受信語を反復復号する機器であって：
変数ノードからの少なくとも１つのメッセージを、変数ノードに対応する位置に最も有望なシンボルを有する確率と前記位置に現在のシンボルを有する確率との比を表す情報によって、前記値の関数として初期設定する手段、および／または、
制御ノードから特定の変数ノードへの、特定のシンボルに関連する少なくとも１つのメッセージを、特定の変数ノードのところの前記特定のシンボルを使って制御ノードにおいて式を満たすシンボルのシーケンスの間で、制御ノードにおいて特定の変数ノード以外の変数ノードから受け取られる、それぞれが式を満たすシーケンス内のその別の変数ノードと関連付けられたシンボルに関連するメッセージの最大値が取る最小値として求める手段、および／または、
すべてのシンボルに関連する変数ノードから制御ノードへの各メッセージを、前記各メッセージの最小値がヌルになるように決定する手段
を備えることを特徴とする機器も提案する。
【００２２】
この機器は、復号方法および関連する利点について先に想定した特徴に対応する任意選択の特徴を有してもよい。
【００２３】
最後に本発明は、このような機器を備える通信装置を提案する。
【００２４】
本発明の他の特徴および利点は、添付の図面を参照して示す以下の説明を考察すれば明らかになるであろう。
【図面の簡単な説明】
【００２５】
【図１】パリティ行列および関連するグラフを例示する図である。
【図２】本発明の教示に従った受信機を備える通信システムの主な要素を表す図である。
【図３】変数ノードと制御ノードとの間のメッセージの交換の技法を示す図である。
【図４】第１の実施形態で使用される「ｆｏｒｗａｒｄ−ｂａｃｋｗａｒｄ」法を示す図である。
【図５】第２の実施形態で提案する技法を例示する図である。
【図６】ＭＳＡ復号器と、２進および非２進ＬＤＰＣ符号のために本発明で提案する復号器を使って得られる性能の比較を表す図である。
【図７】後述する２つの実施形態を使って得られる性能の比較を表す図である。
【図８】ＭＳＡ復号と、２進および非２進符号のために本発明で提案する復号との計算量の比較を表す図である。
【発明を実施するための形態】
【００２６】
以下では、本発明の２つの実施形態を、両実施形態に共通の以下の表記法を使って説明する：
ｐは、ガロア体の次元（または拡大の次数）という厳密に正の整数である。
ｑ＝２ｐをガロア体の位数という。
Ｐ（Ｘ）は次数ｐの既約多項式であり、ＧＦ（２）内の係数＝｛０，１｝である。
ＧＦ（ｑ）＝｛０，１，．．．，ｑ−１｝は、ｑ個の要素を有するガロア体であり、ＧＦ（ｑ）の各要素をシンボルという。
【００２７】
ガロア体ＧＦ（ｑ）は、古典的には、多項式Ｐ（Ｘ）によって生成されたイデアルによる多項式の環ＧＦ（２）［Ｘ］の商として定義されるが、本明細書では、説明を簡略化するために、ガロア体ＧＦ（ｑ）は、後述する「ｓｕｍ」演算および「ｐｒｏｄｕｃｔ」演算を用いて与えられる整数の集合｛０，１，．．．，ｑ−１｝と同一とする（しかし、「単なる」整数と区別するためにガロア体の各要素をシンボルと呼ぶ）ことに留意されたい。
【００２８】
体構造のＧＦ（ｑ）を供給する「ｓｕｍ（和）」演算および「ｐｒｏｄｕｃｔ（積）」演算を定義するために、各シンボルａ∈ＧＦ（ｑ）は、ａを２進数で表記することに対応する２進シーケンスａ０ａ１．．．ａｐ−１と同一であり、言い換えると
【数１】
2010511337.tif 000003
であることに留意されたい。さらに、シンボルａは多項式
【数２】
2010511337.tif 000004
と関連付けられ、結果として、
【数３】
2010511337.tif 000005
になる。
【００２９】
２進値ａ０ａ１．．．ａｐ−１を以下ではシンボルａ∈ＧＦ（ｑ）のビットと呼ぶ。
【００３０】
その場合、２つのシンボルａ，ｂ∈ＧＦ（ｑ）の和は、
【数４】
2010511337.tif 000006
で表され、シンボルａとシンボルｂのビットごとの和で定義することができ、言い換えると、
【数５】
2010511337.tif 000007
である。
【００３１】
２つのシンボルａ，ｂ∈ＧＦ（ｑ）の積は、
【数６】
2010511337.tif 000008
で表され、この部分については、多項式ａ（Ｘ）と多項式ｂ（Ｘ）の積モジュロＰ（Ｘ）によって定義され、言い換えると、
【数７】
2010511337.tif 000009
である。
【００３２】
ＧＦ（ｑ）上のＬＤＰＣ符号は、低密度の非ヌル要素を有するパリティ行列Ｈ∈ＭＭ，Ｎ（ＧＦ（ｑ））によって定義される線形符号である（ＭＭ，Ｎ（ＧＦ（ｑ））はＧＦ（ｑ）内の係数を有するＭ行Ｎ列の行列の集合である）。その場合、以下の概念を導入することができる：
Ｎは、符号長であり、行列Ｈの列数に対応する。
Ｍは、パリティ検査の数であり、行列Ｈの行数に対応する。
Ｋ＝Ｎ−Ｍは、符号の次元であり、情報語の長さに対応する。
ｘ＝（ｘ１，ｘ２，．．．，ｘＮ）はｑ−ａｒｙ符号語、すなわち、ｘｔをｘの転置ベクトルとする場合に、Ｈ・ｘｔ＝０であり、ｈｍ，ｎを行列Ｈの行ｍ列ｎの要素とする場合に、
【数８】
2010511337.tif 000010
であるような、シンボルｘｎ∈ＧＦ（ｑ）のシーケンスである。
（ｘ１，０，ｘ１，１，．．．ｘ１，ｐ−１，ｘ２，０，ｘ２，１，．．．ｘ２，ｐ−１，．．．，ｘＮ，０，ｘＮ，１，．．．ｘＮ，ｐ−１）は、ｘｎ，０，ｘｎ，１，．．．，ｘｎ，ｐ−１をシンボルｘｎ∈ＧＦ（ｑ）のビットとする、対応する２進符号語である。
Ｇ∈ＭＫ，Ｎ（（ＧＦ（ｑ）））は、符号の生成行列、すなわち、ＧｔをＧの転置行列とする場合に、Ｈ・Ｇｔ＝０であるような階数Ｋの行列であり、シーケンス（ａ１，ａ２，．．．，ａＫ）∈ＧＦ（ｑ）Ｋを、ｑ−ａｒｙ情報語といい、（ｘ１，ｘ２，．．．，ｘＮ）＝（ａ１，ａ２，．．．，ａＫ）・Ｇの形に符号化される。
【００３３】
ＬＤＰＣ符号と関連付けられる２部グラフ、すなわちタナー（Ｔａｎｎｅｒ）グラフとして、
行列Ｈの列に対応するＮ変数ノードと、
行列Ｈの行に対応するＭ制御ノード
の２種類に分かれるＮ＋Ｍノードを含むグラフが定義され、変数ノードは、符号を定義する行列Ｈの対応する要素が非ヌルである場合に限って制御ノードに接続される。
【００３４】
以下では次の表記法を使用する：
指数ｍ，ｎは、それぞれ、制御ノード、変数ノードを指す。
Ｈ（ｍ）は、制御ノードｍに接続された変数ノードの集合を指し、これの位数を制御ノードｍの次数という。
Ｈ（ｎ）は、変数ノードｎに接続された制御ノードの集合を指し、これの位数を変数ノードｎの次数という。
【００３５】
この種のグラフに関する詳細は、論文「Ａ  ｒｅｃｕｒｓｉｖｅ  ａｐｐｒｏａｃｈ  ｔｏ  ｌｏｗ  ｃｏｍｐｌｅｘｉｔｙ  ｃｏｄｅｓ」、Ｒ．Ｍ．Ｔａｎｎｅｒ著、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第２７巻、第５号、５３３−５４７頁、１９８１年に記載されている。
【００３６】
例として図１に、ＧＦ（８）ＬＤＰＣ符号のパリティ行列および関連する２部グラフの一例を示す。２部グラフの各エッジにはＨの非ヌル係数が対応するが、グラフ表現を過度に複雑にしないように、グラフのエッジ上にはＨの係数を示していない。
【００３７】
図２に、本発明の技法に準拠した受信側装置を備える、非２進ＬＤＰＣ符号を使った通信システムのスキーマを示す。
【００３８】
送信時に（すなわち、送信されるべき情報を送る装置において）、特に符号化モジュールにおいて、２進情報語（ａ１，０，ａ１，１，．．．ａ１，ｐ−１，．．．，ａＫ，０，ａＫ，１，．．．ａＫ，ｐ−１）は、ａＫをビットａＫ，０，ａＫ，１，．．．ａＫ，ｐ−１によって決定されるシンボルとするｑ−ａｒｙ情報語（ａ１，．．．，ａＫ）に変換され、次いでｑ−ａｒｙ情報語はｑ−ａｒｙ符号語（ｘ１，ｘ２，．．．，ｘＮ）＝（ａ１，．．．，ａＫ）・Ｇに符号化される。次いでｑ−ａｒｙ符号語（ｘ１，ｘ２，．．．，ｘＮ）は、２進符号語（ｘ１，０，ｘ１，１，．．．ｘ１，ｐ−１，ｘ２，０，ｘ２，１，．．．ｘ２，ｐ−１，．．．，ｘＮ，０，ｘＮ，１，．．．ｘＮ，ｐ−１）に変換される。
【００３９】
実際には、２進情報語から２進符号語へ直接伝達する自然な方法は、２進生成行列を使用するものである。
【００４０】
符号化モジュールによって生成された２進符号語は変調モジュールに送られ、そこで通信路上で送られるべき信号に変換される。
【００４１】
受信側装置は：
λｎ，ｉ，ｎ∈｛１，．．．，Ｎ｝，ｉ∈｛０，．．．，ｐ−１｝で表される、通信路上で受け取られる信号に対応する２進対数尤度比（ＬＬＲ）を、式
【数９】
2010511337.tif 000011
に従って求める復調モジュールと、
復調モジュールから受け取られる２進ＬＬＲのシーケンスに基づき、以下にその２つの例を示す本発明で提案する復号方法の手段によって、（復号に成功した場合に送られるｑ−ａｒｙ符号語に等しい）長さＮのｑ−ａｒｙシーケンスを求める誤り訂正モジュール（以下復号器という）と、
復号器の出力のところのｑ−ａｒｙシーケンスを、復号に成功した場合には送られた情報語（ａ１，．．．，ａＫ）に対応するものである情報語に変換する逆マッピングモジュールと
を備える。
【００４２】
次に、復調モジュールによって供給される２進ＬＬＲに基づき、誤り訂正（すなわち復号器）モジュールにおいて受信語（すなわちｑ−ａｒｙシーケンス）を推定するために実行される、本発明で提案する復号方法の第１の例を説明する。
【００４３】
提案の復号は、反復的に、メッセージの交換を用いて実行される。したがってこの方法は：
復調モジュールによって供給される２進ＬＬＲに基づく初期設定ステップと、
２部グラフにおいて接続されている変数ノードと制御ノードとの間でメッセージが交換され、第１の反復ステップが初期設定ステップから生じる値に適用され、後続の各ステップが前のステップから生じる値に適用される反復ステップと
を含む。
【００４４】
初期設定ステップは、γｎ（ａ）で表される、シンボルａ∈ＧＦ（ｑ）に関する変数ノードｎ∈｛１，．．．Ｎ｝において得られる事前情報の計算から開始し、本明細書で説明する復号方法によれば、
【数１０】
2010511337.tif 000012
であり、ｓｎは、通信路観測を考慮に入れた、ｘｎの最も有望なシンボルを表す。
【００４５】
【数１１】
2010511337.tif 000013
であることに留意すると、事前情報は、各変数ノードｎにおいて、アルファベットの任意のシンボルａについて、以下のように計算することができる（以下ａｉはシンボルａの第ｉビットを表すものとする）。
【数１２】
2010511337.tif 000014
【００４６】
したがって、各事前情報γｎ（ａ）は、（位置ｎでの）シンボルａの信頼度の大きさを、最も有望なシンボルまでの距離として提供する。
【００４７】
次いで初期設定ステップは、変数ノードから制御ノードへのメッセージ（外来情報ともいう）の初期設定を続行（終了）することができる。シンボルａ∈ＧＦ（ｑ）に関して変数ノードｎ∈｛１，．．．Ｎ｝により制御ノードｍ∈Ｈ（ｎ）に送られるメッセージは、αｍ，ｎ（ａ）で表される。
【００４８】
本明細書で提案する復号方法によれば、外来情報は、事前情報に基づき、以下のように初期設定される：
αｍ，ｎ（ａ）＝γｎ（ａ）
【００４９】
各反復ステップは、図３に図示するように、２部グラフの各ノード間でのメッセージの交換によって実行され、したがって、以下のサブステップを含む：
制御ノードから変数ノードへのメッセージの計算。シンボルａ∈ＧＦ（ｑ）に関して制御ノードｍ∈｛１，．．．Ｍ｝によって変数ノードｎ∈Ｈ（ｍ）に送られるメッセージはβｍ，ｎ（ａ）で表される。このメッセージは、すべてのシンボルａ’∈ＧＦ（ｑ）に関して制御ノードｍによって変数ノードｎ’∈Ｈ（ｍ）−｛ｎ｝から受け取られるメッセージαｍ，ｎ’（ａ’）の関数として計算され、本明細書で提案する復号方法によれば、
【数１３】
2010511337.tif 000015
である。
事後情報の計算。シンボルａ∈ＧＦ（ｑ）に関して変数ノードｎ∈｛１，．．．Ｎ｝において計算される事後情報は、
【数１４】
2010511337.tif 000016
で表される。この情報は、変数ノードｎで得られる事前情報γｎ（ａ）と、シンボルａ∈ＧＦ（ｑ）に関して変数ノードｎによって制御ノードｍ∈Ｈ（ｎ）から受け取られるメッセージβｍ，ｎ（ａ）との関数として計算され、式によれば、
【数１５】
2010511337.tif 000017
である。
変数ノードから制御ノードへのメッセージ（すなわち外来情報）の計算。（新規の）メッセージαｍ，ｎ（ａ）は、変数ノードｎで得られる事前情報γｎ（ａ）と、シンボルａ∈ＧＦ（ｑ）に関して変数ノードｎによって制御ノードｍ’∈Ｈ（ｎ）−｛ｍ｝から受け取られるメッセージβｍ’，ｎ（ａ）との関数として計算され、式によれば、
【数１６】
2010511337.tif 000018
である。
【００５０】
したがって、最も有望なシンボルｓｎ（すなわちαｍ，ｎ＝αｍ，ｎ（ｓｎ）であるようなシンボル）では、各反復ごとに常にαｍ，ｎ（ｓｎ）＝０になる
各反復ごとに、事後情報
【数１７】
2010511337.tif 000019
に基づき、最も有望なシンボルに対応する硬判定を計算することができる。すでに述べたように、最も有望なシンボルは、最小の事後情報
【数１８】
2010511337.tif 000020
を生成するシンボルである。これら最も有望なシンボルのシーケンスが符号語に対応する場合、見つかった符号語は送られた元の符号語であるとみなされる。したがって復号が停止され、見つかった符号語が逆マッピングモジュールに渡される。
【００５１】
他方、これら最も有望なシンボルのシーケンスが符号語に対応しない場合、復号が所定の最大反復回数に達するまで続行され、所定の最大反復回数に達した場合には、復号に失敗したとみなされる。
【００５２】
制御ノードからのメッセージβｍ，ｎ（ａ）の計算に際して使用されるｍｉｎ−ｍａｘ式の有益な点は以下のように説明することができる。
【００５３】
以下、制御ノードをｍとし、制御ノードｍに接続された変数ノードをｎとし、シンボルをａ∈ＧＦ（ｑ）とする。制御ノードｍに接続されたその他の（すなわち変数ノードｎ以外の）変数ノードをｎ１，．．．，ｎｄで表す。したがって、前記の表記法を使用すると、Ｈ（ｍ）＝｛ｎ，ｎ１，．．．，ｎｄ｝になる。
【００５４】
メッセージβｍ，ｎ（ａ）は、（ＧＦ（ｑ）の各シンボルごとに）制御ノードｍによって変数ノードｎ１，．．．，ｎｄから受け取られるメッセージの関数として計算される。
【００５５】
シンボルのシーケンス（ａ１，．．．，ａｄ）が各変数ノードｎ１，．．．，ｎｄごとに１シンボルを含むとみなされる場合に、各変数ノードｎ，ｎ１，．．．，ｎｄごとに１シンボルを含むシーケンス（ａ，ａ１，．．．，ａｄ）が検査ｍ、すなわち、行ｍにおけるパリティ行列からの式、
【数１９】
2010511337.tif 000021
を満たすならば、このようなシーケンスを以下において許容（ａｄｍｉｓｓｉｂｌｅ）シーケンスという。
【００５６】
したがって、許容シーケンスは符号語の一部分を構成するはずである。
【００５７】
βｍ，ｎ（ａ）の計算は、すべての許容シーケンスを考慮に入れる。したがって、各許容シーケンス（ａ１，．．．，ａｄ）ごとに、このシーケンスの信頼性の大きさを与える（前記のように低い値が信頼性の高い情報に相当する）、このシーケンスの各シンボルに関して制御ノードｍによって変数ノードｎ１，．．．，ｎｄから受け取られるメッセージの最大値を計算することが可能である。正確には、
【数２０】
2010511337.tif 000022
という問題である。
【００５８】
この最大値がＭ（ａ１，．．．，ａｄ）で表される場合、メッセージβｍ，ｎ（ａ）は、すべての許容シーケンスについて計算されたすべての最大値の最小値に等しい。すなわち、
【数２１】
2010511337.tif 000023
である。
【００５９】
したがって、この最小値は、許容シーケンスのうちで最も有望なものを対象とし、その信頼性の尺度を与える。
【００６０】
このようにして、制御ノードｍにおいて得られるその他の情報を考慮に入れた、位置ｎにおけるシンボルａの信頼度に関する情報が得られる。
【００６１】
以下に、すべての許容シーケンスを毎回リストせずに、メッセージβｍ，ｎ（ａ）の計算を実施する第１の実際的方法を提案する。この第１の実施形態は、「ｆｏｒｗａｒｄ−ｂａｃｋｗａｒｄ」型の方法を使用し、以下のように表すことができる。
【００６２】
Ｍｉｎ−Ｍａｘアルゴリズム
入力：λ１，０，λ１，１，．．．，λ１，ｐ−１，λ２，０，λ２，１，．．．，λ２，ｐ−１，．．．，λＮ，０，λＮ，１，．．．，λＮ，ｐ−１  ２進ＬＬＲ
出力：ｓ１，ｓ２，．．．，ｓｎ  ｑ−ａｒｙシーケンス
【００６３】
初期設定
事前情報
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数２２】
2010511337.tif 000024
変数ノードからのメッセージの初期設定
各変数ノードｎ∈｛１，２，．．．，Ｎ｝および各制御ノードｍ∈Ｈ（ｎ）ごとに以下を実行する：
【数２３】
2010511337.tif 000025
【００６４】
反復
制御ノードからのメッセージ
各制御ノードｍ∈｛１，２，．．．，Ｍ｝（Ｈ（ｍ）＝｛ｎ１，ｎ２，．．．，ｎｄ｝、したがってｄは、Ｈ（ｍ）の位数）ごとに以下を実行する：
／／Ｆｏｒｗａｒｄ（前方）
【数２４】
2010511337.tif 000026
／／Ｂａｃｋｗａｒｄ（後方）
【数２５】
2010511337.tif 000027
／／制御ノードｍからのメッセージ
【数２６】
2010511337.tif 000028
事後情報
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数２７】
2010511337.tif 000029
硬判定：最も有望なシンボルの選択
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数２８】
2010511337.tif 000030
【数２９】
2010511337.tif 000031
の場合には終了する。
変数ノードからのメッセージ
各変数ノードｎ∈｛１，２，．．．，Ｎ｝および各制御ノードｍ∈Ｈ（ｎ）ごとに以下を実行する：
【数３０】
2010511337.tif 000032
【００６５】
本実施形態で使用される「ｆｏｒｗａｒｄ−ｂａｃｋｗａｒｄ」法は、図４に示されている。αｍ，ｎ（）という表記は、メッセージの集合αｍ，ｎ（ａ），ａ∈ＧＦ（ｑ）を意味し、Ｆｊ（），Ｂｊ（）およびβｍ，ｎ（）も同様である。中間量（または値）Ｆｊ（），Ｂｊ（）の使用は、２つのシンボル（ａ’、ａ”）を有する式が関与すること、すなわち、毎回ただ２つの次元だけについて最大値の最小値が求められることを意味する。
【００６６】
さらに、前記で制御ノードからのメッセージの計算においてＦｊ（ａ）およびＢｊ（ａ）を求めるのに使用されている「ｍｉｎ−ｍａｘ」型の式は、以下のように実行することができる。
【００６７】
説明を簡略化するために、ここでは行列Ｈの係数の値が無視され（すなわち、ｈｍ，ｎ＝１，∀ｎ∈Ｈ（ｍ）とみなされ）、したがって、「ｍｉｎ−ｍａｘ」型の式を、
【数３１】
2010511337.tif 000033
として表すことができ、この式の計算は以下のように行われる。
ａ∈ＧＦ（ｑ）について初期設定を行う：ｆ（ａ）＝＋∞；
ａ’∈ＧＦ（ｑ）について以下を実行する：
ａ”∈ＧＦ（ｑ）について以下を実行する：
【数３２】
2010511337.tif 000034
ｆ＝ｍａｘ（ｆ’（ａ’），ｆ”（ａ”））；
ｆ＜ｆ（ａ）の場合、ｆ（ａ）＝ｆ；
この計算の計算量はｑ２に比例することに留意されたい。
【００６８】
さらに、式が使用された場合、交換されるメッセージのダイナミックレンジは低くなり、したがって正規化は不要になることにも留意されたい。さらに、提案の解決法は、熱雑音の知識とも無関係である。
【００６９】
次に、計算量を低減するのに前記の低いダイナミックレンジが使用される本発明の第２の実施形態を説明する。特に目標とするのは、
【数３３】
2010511337.tif 000035
の形のｍｉｎ−ｍａｘ計算の負担を低減することである。
【００７０】
実際には（付録でも証明されているが）、この計算では、ｆ’（ａ’）およびｆ”（ａ”）の間のｑ＋１個の最低値（すなわち合計で２・ｑ個の値）に対応するシンボルａ’およびシンボルａ”だけを考察すれば十分であることが分かっている。
【００７１】
ｆ’（ａ’）およびｆ”（ａ”）の間のｑ＋１個の最低値に対応するシンボルａ’、シンボルａ”の数を、それぞれ、ｑ’、ｑ”で表す。その場合、ｑ’＋ｑ”＝ｑ＋１であり、前記計算の計算量は、
【数３４】
2010511337.tif 000036
に比例するものになる。
【００７２】
その場合、値ｆ’（ａ’）および値ｆ”（ａ”）がソートされているという条件で、ｆ（ａ），ａ∈ＧＦ（ｑ）の計算の計算量を低減することを想定することもできる。この場合、値ｆ’（ａ’）および値ｆ”（ａ”）をソートすることは、演算回数の点でも、メモリアクセスの点でも、無視し得ないほどの計算量を増大させるはずである。
【００７３】
値ｆ’（ａ’）および値ｆ”（ａ”）のソートを回避するために、ここでは、シンボルａ’およびシンボルａ”がｆ’（ａ’）およびｆ”（ａ”）の整数部分に従って記憶される。その場合、
【数３５】
2010511337.tif 000037
であるようなシンボルａ’（あるいは
【数３６】
2010511337.tif 000038
であるようなシンボルａ”）を含む集合Δ’ｋ（集合Δ”ｋ）（演算子
【数３７】
2010511337.tif 000039
は整数部分を指示する）が、以下のように表される。
【数３８】
2010511337.tif 000040
【００７４】
その場合には、集合Δ’＝Δ’０∪．．．∪Δ’Ｅおよび集合Δ”＝Δ”０∪．．．∪Δ”Ｅに含まれるシンボルａ’およびシンボルａ”の数がｑ＋１以上になるような最小の整数Ｅを求め、次いで、
【数３９】
2010511337.tif 000041
を使ってｆ（ａ）を計算すれば十分なはずである。
【００７５】
当然ながら、この方法を使っても、体の位数プラス１よりも多くの（＞ｑ＋１）シンボルの使用が必要になることもあるが、これにより値ｆ’（ａ’）および値ｆ”（ａ”）のソートが回避される。
【００７６】
集合Δ’ｋおよび集合Δ”ｋの使用には以下のような二重の利点がある：
「ｍｉｎ−ｍａｘ」型の式を計算するのに必要なシンボルの数（したがってループの数）が低減される。
最大値計算の大部分が不要になる。したがって最大値ｍａｘ（ｆ’（ａ’），ｆ”（ａ”））は、シンボルａ’およびシンボルａ”が同じ階数の集合に含まれる、すなわち、ａ’∈Δ’ｋ’およびａ”∈Δ”ｋ”であり、ｋ’＝ｋ”である場合に限って計算されればよい。その他の場合には、最大値は、最大階数の集合からのシンボルに対応する（すなわち、ｋ’＞ｋ”の場合にはｍａｘ＝ｆ’（ａ’）であり、ｋ”＞ｋ’の場合にはｍａｘ＝ｆ”（ａ”）である）。
【００７７】
この方法は以下のように使用される：
交換されるメッセージの整数部分がアルファベット（この場合はガロア体ＧＦ（ｑ））の各シンボルを区別するのに十分なほど洗練された基準を提供するように、事前情報の事前定義のダイナミックレンジが定義される。定数ＡＩ（「Ａｖｅｒａｇｅ  ａ  ｐｒｉｏｒｉ  Ｉｎｆｏｒｍａｔｉｏｎ：平均事前情報」）が使用され、初期設定ステップにおいて事前情報の計算後に（第１の実施形態参照）、
γａｖｅ＝｛γｎ（ａ）｜ｎ∈｛１，２，．．．Ｎ｝，ａ∈ＧＦ（ｑ）｝の平均値
が計算され、次いで、事前情報が以下のように正規化される。
【数４０】
2010511337.tif 000042
集合Δ’ｋおよび集合Δ”ｋの数がより少なくなるように、制御ノードからのメッセージの最大ダイナミックレンジが定義される。このために定数ＣＯＴ（「Ｃｕｔ  Ｏｆｆ  Ｔｈｒｅｓｈｏｌｄ：切り捨て閾値」）が使用され、「ｍｉｎ−ｍａｘ」式が以下のように計算される。
／／集合Δ’ｋおよび集合Δ”ｋを求める
ａ∈ＧＦ（ｑ）について
【数４１】
2010511337.tif 000043
の場合Δ’ｋにａを加え、
【数４２】
2010511337.tif 000044
の場合Δ”ｋにａを加える。
／／（Ｅで表される）使用すべき集合の数を求める。
ｃａｒｄ＝０；
（Ｅ＝０；Ｅ＜ＣＯＴ−１；Ｅ＋＋）について
（ｃａｒｄ＋＝（ｃａｒｄ（Δ’Ｅ）＋ｃａｒｄ（Δ”Ｅ）））≧ｑ＋１の場合ループを出る。
【００７８】
したがって、Ｅは、集合Δ’＝Δ’０∪．．．∪Δ’ＥおよびΔ”＝Δ”０∪．．．∪Δ”Ｅが、Ｅの最大値（すなわち値ＣＯＴ−１）に到達した場合を除いて、（前記のように）少なくともｑ＋１個の要素を集めたものになるように定義される。
【００７９】
したがってＥは、ループから出るときに、使用される集合の数を定義する。ループが最後まで実行される可能性もあり、その場合には、Ｅ＝ＣＯＴ−１（Ｅが到達する最大値）であり、ｃａｒｄ（Δ’∪Δ”）をｑ＋１より小さくすることができる（したがって、使用されるシンボルａ’およびシンボルａ”の数はｑ＋１より小さくなり、結果的に、「ｍｉｎ−ｍａｘ」計算の計算量はさらに低減されることになる）。これは一般には、復号が十分に進み、復号器がごく少数のシンボルだけに問い合わせする、最終反復時に生じる。
【００８０】
必要な場合には、整数Ｅが集合Δ’ｋおよびΔ”ｋ（０≦ｋ＜ＣＯＴ）から求められるものであることを強調するために、Ｅ＝Ｅ（Δ’，Δ”）という表記を使用する。
【００８１】
したがって、以下のアルゴリズムを提案する：
／／「ｍｉｎ−ｍａｘ」式の計算（選択的実施法）
ａ∈ＧＦ（ｑ）について初期設定を行う：ｆ（ａ）＝ＣＯＴ；
ｋ’＝０，．．．，Ｅおよびａ’∈Δ’ｋ’について以下を実行する：
ｋ”＝０，．．．，ｋ’−１およびａ”∈Δ”ｋ”について以下を実行する：
【数４３】
2010511337.tif 000045
／／ｋ’＞ｋ”であるため、ｆ’（ａ’）＝ｍａｘ（ｆ’（ａ’），ｆ”（ａ”））であることに留意されたい。
ｆ’（ａ’）＜ｆ（ａ）の場合ｆ（ａ）＝ｆ’（ａ’）
ｋ”＝０，．．．，Ｅおよびａ”∈Δ”ｋ”について以下を実行する：
ｋ’＝０，．．．，ｋ”−１およびａ’∈Δ’ｋ’について以下を実行する：
【数４４】
2010511337.tif 000046
／／ｋ”＞ｋ’であるため、ｆ”（ａ”）＝ｍａｘ（ｆ’（ａ’），ｆ”（ａ”））であることに留意されたい。
ｆ”（ａ”）＜ｆ（ａ）の場合、ｆ（ａ）＝ｆ”（ａ”）
ｋ＝０，．．．，Ｅについて以下を実行する：
ａ’∈Δ’ｋおよびａ”∈Δ”ｋについて以下を実行する：
【数４５】
2010511337.tif 000047
ｆ＝ｍａｘ（ｆ’（ａ’），ｆ”（ａ”））
ｆ＜ｆ（ａ）の場合ｆ（ａ）＝ｆ
【００８２】
次に、本発明で提案するアルゴリズムの第２の実施形態を詳細に説明する。
【００８３】
以下の３種類の集合を定義する。
集合ＡｊΔｋ：
【数４６】
2010511337.tif 000048
であるようなシンボルａ∈ＧＦ（ｑ）を含む。
集合ＦｊΔｋ：
【数４７】
2010511337.tif 000049
であるようなシンボルａ∈ＧＦ（ｑ）を含む。
集合ＢｊΔｋ：
【数４８】
2010511337.tif 000050
であるようなシンボルａ∈ＧＦ（ｑ）を含む。
【００８４】
この説明でも引き続き第１の実施形態の表記法を使用する。
【００８５】
その場合この第２の実施形態で提案するアルゴリズムは以下のとおりである。
【００８６】
Ｍｉｎ−Ｍａｘアルゴリズム
入力：λ１，０，λ１，１，．．．，λ１，ｐ−１，λ２，０，λ２，１，．．．，λ２，ｐ−１，．．．，λＮ，０，λＮ，１，．．．，λＮ，ｐ−１  ２進ＬＬＲ
出力：ｓ１，ｓ２，．．．ｓｎ  ｑ−ａｒｙシーケンス
定義されたＡＩ、例えば、ＧＦ（８）ではＡＩ＝４．６４７など
定義されたＣＯＴ、例えば、ＧＦ（８）ではＣＯＴ＝１０など
【００８７】
初期設定
事前情報
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数４９】
2010511337.tif 000051
以下を実行する：
γａｖｅ＝｛γｎ（ａ）｜ｎ∈｛１，２，．．．Ｎ｝，ａ∈ＧＦ（ｑ）｝の平均値
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数５０】
2010511337.tif 000052
変数ノードからのメッセージの初期設定
各変数ノードｎ∈｛１，２，．．．，Ｎ｝および各制御ノードｍ∈Ｈ（ｎ）ごとに以下を実行する：
【数５１】
2010511337.tif 000053
【００８８】
反復
制御ノードからのメッセージ
各制御ノードｍ∈｛１，２，．．．，Ｍ｝（Ｈ（ｍ）＝｛ｎ１，ｎ２，．．．，ｎｄ｝を設定する）ごとに以下を実行する：
／／集合ＡｊΔｋ
【数５２】
2010511337.tif 000054
／／Ｆｏｒｗａｒｄ（前方）
【数５３】
2010511337.tif 000055
／／Ｂａｃｋｗａｒｄ（後方）
【数５４】
2010511337.tif 000056
／／制御ノードｍからのメッセージ
【数５５】
2010511337.tif 000057
【００８９】
事後情報
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数５６】
2010511337.tif 000058
【００９０】
硬判定：最も有望なシンボルの選択
各変数ノードｎ∈｛１，２，．．．，Ｎ｝ごとに以下を実行する：
【数５７】
2010511337.tif 000059
【数５８】
2010511337.tif 000060
の場合には終了する；
【００９１】
変数ノードからのメッセージ
各変数ノードｎ∈｛１，２，．．．，Ｎ｝および各制御ノードｍ∈Ｈ（ｎ）ごとに以下を実行する：
【数５９】
2010511337.tif 000061
【００９２】
前記計算では、各「ｍｉｎ−ｍａｘ」型式の結果を求めるのに、前記のアルゴリズム（「／／「ｍｉｎ−ｍａｘ」式（選択的実施法）の計算」）が使用されている。
【００９３】
さらに、前記のように、初期設定ステップでは、交換されるメッセージの整数部分が、アルファベット（この場合のガロア体ＧＦ（ｑ））の各シンボルを区別するのに十分なほど洗練された基準を提供するように事前情報のダイナミックレンジが調整される。実際には、γａｖｅは、その２つの連続する符号語間での変動はごくわずかであることが分かっており、周期的にしか計算することができない。
【００９４】
前記のパラメータは、好ましくは：
【数６０】
2010511337.tif 000062
による乗算後に、タイプΔｋの各ステップが少数のシンボルだけしか含まないように、事前情報γｎ（ａ）の各値が十分な間隔を有し、
シミュレーションによって求めることのできるＣＯＴの値は、使用されるタイプΔｋの集合の数を決定するため、比較的低くなる
ように選択される。
これに関しては、例として示したＧＦ（８）上の定数ＡＩおよび定数ＣＯＴの値がシミュレーションによって求められており、これらの値は、符号の特性（長さ、不規則性、符号化率）とも使用される変調とも無関係に、ＡＷＧＮ通信路で、およびＧＦ（８）上の任意のＬＤＰＣ符号に使用できることに留意されたい。
【００９５】
図５に、説明のためにすぎないが、定数ＣＯＴ＝３、次数４（Ｈ（ｍ）＝｛ｎ１，ｎ２，ｎ３，ｎ４｝）の制御ノードｍの場合について、集合ＡｊΔｋ、ＦｊΔｋ、ＢｊΔｋと「ｆｏｒｗａｒｄ−ｂａｃｋｗａｒｄ」法を結合した使用例を図示する。
【００９６】
ガロア体、すなわちＧＦ（８）に基づくこの例では、集合Ｆ１Δｋ，ｋ＝０，１，２はそれぞれ３、１および４個のシンボルを含み、集合Ａ１Δｋ，ｋ＝０，１，２はそれぞれ４、３および１個のシンボルを含むものとする。その場合、値Ｆ２（ａ），ａ∈ＧＦ（８）の計算には、ｋ＝０とｋ＝１についてのみ、シンボルａ’∈Ｆ１Δｋおよびシンボルａ”∈Ａ２Δｋに対応する値Ｆ１（ａ’）および値αｍ，ｎ２（ａ”）を使用すれば十分である（したがって、４個のシンボルａ’と７個のシンボルａ”で合計１１個のシンボルになり、少なくとも合計ｑ＋１＝９個のシンボルがあればよいので十分である）。
【００９７】
値Ｆ２（ａ），ａ∈ＧＦ（８）が計算されると、シンボルａ∈ＧＦ（８）は、（計算された値の整数部分に従って）集合Ｆ２Δｋ，ｋ＝０，１，２に格納される。集合Ｆ２Δｋ，ｋ＝０，１，２は、それぞれ、６、２および０個のシンボルを含むものとする。その場合、値Ｆ３（ａ），ａ∈ＧＦ（８）の計算には、６個のシンボルａ’∈Ｆ２Δ０および３個のシンボルａ”∈Ａ３Δ０（合計９個のシンボルになる）に対応する値Ｆ２（ａ’）および値αｍ，ｎ３（ａ”）を使用すれば十分である。
【００９８】
以下では、ＧＦ（８）上のＬＤＰＣまたは２進符号について、様々な前記のアルゴリズムと従来技術におけるアルゴリズムの比較シミュレーションの結果を説明する。
【００９９】
ＭＭＡ（「ｍｉｎ−ｍａｘアルゴリズム」）は、本発明の主題であるアルゴリズムを表し、前記したその第１の実施形態を「標準的実施法」とし、その第２の実施形態を「選択的実施法」とする。
【０１００】
使用されるすべての符号はイレギュラーＬＤＰＣ符号である。２部グラフは、「Ｒｅｇｕｌａｒ  ａｎｄ  ｉｒｒｅｇｕｌａｒ  ｐｒｏｇｒｅｓｓｉｖｅ  ｅｄｇｅ−ｇｒｏｗｔｈ  Ｔａｎｎｅｒ  ｇｒａｐｈｓ」、Ｘ．Ｙ．Ｈｕ、Ｅ．Ｅｌｅｆｔｈｅｒｉｏｕ、Ｄ．Ｍ．Ａｒｎｏｌｄ著、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第５１巻、第１号、３８６−３９８頁、２００５年に記載されている「ＰＥＧ（Ｐｒｏｇｒｅｓｓｉｖｅ  Ｅｄｇｅ  Ｇｒｏｗｔｈ）」アルゴリズムを使って構築される。ＧＦ（８）上のＬＤＰＣ符号の場合、２部グラフの各エッジは、パリティ行列内の各非ヌル係数の場所に対応する。これらの係数は無作為に選択されている。以下では、使用される符号の不規則性は示さず、ｄｎａｖｅで表される変数ノードの平均次数を示す。
【０１０１】
２進ＬＤＰＣ符号の不規則性は、「Ｄｅｓｉｇｎ  ｏｆ  ｃａｐａｃｉｔｙ  ａｐｐｒｏａｃｈｉｎｇ  ｉｒｒｅｇｕｌａｒ  ｌｏｗ  ｄｅｎｓｉｔｙ  ｐａｒｉｔｙ  ｃｈｅｃｋ  ｃｏｄｅｓ」、Ｔ．Ｊ．Ｒｉｃｈａｒｄｓｏｎ、Ｍ．Ａ．Ｓｈｏｋｒｏｌｌａｈｉ、Ｒ．Ｌ．Ｕｒｂａｎｋｅ著、ＩＥＥＥ  Ｔｒａｎｓ．Ｉｎｆｏｒｍ．Ｔｈｅｏｒｙ、第４７巻、第２号、６１９−６３７頁、２００１年に記載されている「ｄｅｎｓｉｔｙ  ｅｖｏｌｕｔｉｏｎ」によって最適化されている。それでもなお、良好な２進符号に対応する不規則性は良好なｑ−ａｒｙ符号を得るのに適さない（逆もまた同様である）。一般に、ガロア体の位数が増加するほど、使用される符号はより「疎」で（２部グラフ中のエッジがより少なく）なければならず、そのため以下では、２進符号とＧＦ（８）上の符号の変数ノードの平均次数の差を使用する。
【０１０２】
シミュレーションは、ＱＰＳＫ変調を使ってＡＷＧＮ通信路について実行されている。さらに、性能比較は、１０−５の２進誤り率（ＢＥＲ）で実施されている。最大反復回数は２００回に定めされている。
【０１０３】
図６に、以下の特性を有する符号について、ＧＦ（８）上のＬＤＰＣ符号を用いたＭＭＡ復号器およびＭＳＡ復号器と、２進ＬＤＰＣ符号を用いたＭＳＡ復号器との性能を示す：
一方は、１００８情報ビット（すなわち３３６シンボル）、２０１６符号化ビット（すなわち６７２シンボル）（すなわち符号化率１／２）。
他方は、４０３２情報ビット（すなわち１３４４シンボル）、８０６４符号化ビット（すなわち２６８８シンボル）（すなわち符号化率１／２）。
２進符号では、ｄｎａｖｅ＝３．２７。
ＧＦ（８）上の符号では、ｄｎａｖｅ＝２．５。
以下について留意されたい：
ＧＦ（８）上のＬＤＰＣ符号について、ＭＭＡ復号器はＭＳＡ復号器よりも０．１５から０．２２ｄＢ優れている。
ＧＦ（８）上の符号（ＭＭＡ復号）は２進符号よりも０．３３ｄＢ優れている。
【０１０４】
また、実行されたシミュレーション（図示せず）によれば、ＧＦ（８）上のＬＤＰＣ符号について、ＭＭＡ復号器とＳＰＡ復号器とでは０．０４ｄＢの差しかないことが分かったことにも留意されたい。
【０１０５】
図７を参照して、「標準的」実施法と「選択的」実施法を使って得られたＭＭＡ復号器の性能を比較する。使用されたＧＦ（８）上のＬＤＰＣ符号は、それぞれ、変数ノードの平均次数が２．４、２．５および２．８であり、符号化率が１／３、１／２および４／５であり、２０１６ビットの２進長のものである。さらに、選択的実施法に使用された定数ＡＩおよび定数ＣＯＴは、
ＡＩ＝４．６４７、ＣＯＴ＝１０
に定められている。
【０１０６】
図７から、得られる性能はどちらの場合も事実上同一であり、言い換えると、選択的実施法では標準的実施法を上回る大きな性能損は生じないことが分かる。
【０１０７】
図８では、ＧＦ（８）上のＭＳＡ復号およびＭＭＡ復号（標準的実施法および選択的実施法）と、ＧＦ（２）（２進符号）上のＭＳＡ復号の計算量を比較している。
【０１０８】
演算回数は、２つの復号器によって実施された（すべての反復の累積の）１符号化ビット当たりの平均演算回数を１０００単位で表したものである。この数は信号対雑音比（ＳＮＲ）に依存し、信号／雑音比Ｅｂ／Ｎｏが増大した場合、２つの復号器によって実施される平均反復回数が減少する。
【０１０９】
各符号化率（１／３、１／２および４／５）ごとに、ＢＥＲが該当する領域に対応するＥｂ／Ｎｏの値での１符号化ビット当たりの平均演算回数が記録されている。
【０１１０】
ＧＦ（８）では、ＭＭＡ（標準的）復号器は、ＭＳＡ復号器より計算量が低い。これは、ＭＭＡ復号器がＭＳＡ復号器よりも高速で収束するからである。言い換えると、ＭＭＡ復号器によって実施される反復回数は、ＭＳＡ復号器によって実施される反復回数より少ない（２つの復号器は事実上１反復当たり同数の演算を実施する）。
【０１１１】
ＧＦ（８）では、ＭＭＡ（選択的）復号器の計算量は、ＭＭＡ（標準的）復号器の１／２から１／３である。２つの復号器によって実施される反復回数は同じであるが、各反復ごとにＭＭＡ（選択的）復号器が実施する演算数はＭＭＡ（標準的）復号器より少ない。
【０１１２】
最後に、ＧＦ（８）上のＭＭＡ（選択的）復号器の計算量は、２進ＭＳＡ復号器の１から２倍にすぎないことが分かる。
【０１１３】
以上の各実施形態は、単に本発明の可能な実施形態であるにすぎず、本発明はこれらの実施形態だけに限定されるものではない。
【０１１４】
（付録）
ＧＦ（ｑ）上で定義される、実数値を有する２つの関数ｆ’およびｆ”と、「ｍｉｎ−ｍａｘ」式
【数６１】
2010511337.tif 000063
によって定義される関数ｆを考察する。
【０１１５】
Δ’およびΔ”は、値の集合
｛ｆ’（ａ’）｜ａ’∈Δ’｝∪｛ｆ”（ａ”）｜ａ”∈Δ”｝
が、ｆ’およびｆ”のすべての値、すなわち、
｛ｆ’（ａ’）｜ａ’∈ＧＦ（ｑ）｝∪｛ｆ”（ａ”）｜ａ”∈ＧＦ（ｑ）｝からのｑ＋１個の最低値を含むようなＧＦ（ｑ）の２つの部分集合である。
【０１１６】
その場合、ｆ（ａ）は、より少数のシンボルａ’およびシンボルａ”が関与する式
【数６２】
2010511337.tif 000064
によって計算することができることを示す。
【０１１７】
第１のステップでは、任意のシンボルａ∈ＧＦ（ｑ）を、以下のように２つのシンボルの和として表すことができることを示す：
ａ＝δ’＋δ”、δ’∈Δ’、δ”∈Δ”
【０１１８】
このために、Ｉ（ｘ）（恒等関数）と
【数６３】
2010511337.tif 000065
（ａによる変換）により、２つの関数Ｉ、Ｔａ：ＧＦ（ｑ）→ＧＦ（ｑ）を定義する。２つの関数は全単射であり、以下の式が得られる
ｃａｒｄ（Ｉ（Δ’））＋ｃａｒｄ（Ｔａ（Δ”））＝ｃａｒｄ（Δ’）＋ｃａｒｄ（Δ”）≧ｑ＋１＞ｃａｒｄ（ＧＦ（ｑ））
したがって、
Ｉ（δ’）＝Ｔａ（δ”）であるようなδ’∈Δ’およびδ”∈Δ”が存在するということになり、これは、
【数６４】
2010511337.tif 000066
と等価であり、そのため、
【数６５】
2010511337.tif 000067
である。
【０１１９】
証明の第２のステップにおいて、ｓ’，ｓ”∈ＧＦ（ｑ）は、
【数６６】
2010511337.tif 000068
であり、ｆ（ａ）の定義における最小値を達成するような、言い換えると、
【数６７】
2010511337.tif 000069
であるような２つのシンボルを表す。
【０１２０】
δ’∈Δ’およびδ”∈Δ”は、（第１のステップ後に）ａ＝δ’＋δ”になるような要素である。シンボルΔ’およびシンボルΔ”は、関数ｆ’および関数ｆ”のすべての値の集合からのｑ＋１個の最低値に対応するものであることを想起されたい。
【０１２１】
その場合（背理法の推論によって）、
【数６８】
2010511337.tif 000070
または
【数６９】
2010511337.tif 000071
であった場合、値ｆ’（ｓ’）、値ｆ”（ｓ”）のうちの少なくとも１つは、ｑ＋１個の最低値以外になるはずであり、したがって、
ｍａｘ（ｆ’（δ’），ｆ”（δ”））＜ｍａｘ（ｆ’（ｓ’），ｆ”（ｓ”））
が得られることになり、これは、対ｓ’，ｓ”の最小文字と矛盾する。
【０１２２】
したがって必然的にｓ’∈Δ’およびｓ”∈Δ”であるはずであり、したがって、
【数７０】
2010511337.tif 000072
になる。
【図１】
2010511337.tif 000073
【図２】
2010511337.tif 000074
【図３】
2010511337.tif 000075
【図４】
2010511337.tif 000076
【図５】
2010511337.tif 000077
【図６】
2010511337.tif 000078
【図７】
2010511337.tif 000079
【図８】
2010511337.tif 000080
【国際調査報告】
2010511337.tif 000081
2010511337.tif 000082
2010511337.tif 000083
2010511337.tif 000084
2010511337.tif 000085
2010511337.tif 000086