(57)【要約】ＬＤＰＣデコーダなどのメッセージ受け渡し用デコーダを実現する技術について説明する。ハードウェアの実施構成を容易にするために、メッセージは１／２ｌｏｇ２の整数倍に量子化される。メッセージが、コンパクト度の大きな可変ノードメッセージ表現形式と、コンパクト度の少ない制約ノードメッセージ表現形式との間で変換される。可変ノードメッセージ形式により、単純な加算と減算とによる可変ノードメッセージ処理の実行が可能となるのに対して、制約ノード表現により、単純な加算と減算による制約ノードメッセージ処理の実行が可能となる。累算器モジュールと、減算器モジュールと、遅延パイプラインとを用いて、可変ノードと制約ノードとが実現される。累算器モジュールは累積メッセージサムを生成する。ノードの累積メッセージサムが記憶され、次いで、遅延パイプラインから得られる遅延入力メッセージが上記累積メッセージサムから減算されて、出力メッセージが形成される。遅延パイプラインは、異なるレベルのノードに対応する処理操作を順次行うことを可能にする可変遅延素子を備える。
2005506733.tif 000002
【特許請求の範囲】
【請求項１】
デコーダによる処理方法において、
値を受信するステップと、
量子化値を形成するために、１／２ｌｏｇ２の整数倍の量子化ステップサイズを用いて前記受信値を量子化するステップと、
出力メッセージの少なくとも一部を形成して、チェックノード処理操作と可変ノード処理操作のうちの一方を前記量子化値に対して行うステップと、を有することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記受信値が対数尤度値であることを特徴とする方法。
【請求項３】
請求項２に記載の方法において、前記対数尤度値が対数尤度比または対数尤度比の近似値のうちの一方であることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、検出した値に定数を乗算することにより前記受信値を形成するステップをさらに有することを特徴とする方法。
【請求項５】
請求項４に記載のデコーダによる処理方法において、前記受信値が受信した符号語の一部であることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記受信値を量子化するステップが、
符号ビットと絶対値との組み合わせとして構成される前記量子化値の符号ビットと絶対値とを形成するステップを含むことを特徴とする方法。
【請求項７】
請求項６に記載の方法において、チェックノード処理操作と可変ノード処理操作のうちの一方を実行するステップが、
変換済み絶対値を形成して、前記量子化値に含まれる絶対値の関数として一定数をシフトするステップと、
出力用変換済み絶対値を形成して、前記変換済み絶対値に対して少なくとも１回のチェックノード処理操作を実行するステップと、を含むことを特徴とする方法。
【請求項８】
請求項７に記載の方法において、チェックノード処理操作と可変ノード処理操作のうちの一方を実行するステップが、
対数尤度メッセージ絶対値を形成する第２の変換処理を実行するステップをさらに含むことを特徴とする方法。
【請求項９】
請求項８に記載の方法において、チェックノード処理操作と可変ノード処理操作のうちの一方を実行するステップが、
出力用符号ビット値を形成して、前記量子化値の符号ビットに対して少なくとも１回のチェックノード処理操作を実行するステップをさらに含むことを特徴とする方法。
【請求項１０】
請求項９に記載の方法において、チェックノード処理操作と可変ノード処理操作のうちの一方を実行するステップが、
デコーダメッセージを形成するために、前記出力用符号ビット値を前記形成済み対数尤度メッセージ絶対値と組み合わせるステップをさらに含むことを特徴とする方法。
【請求項１１】
請求項１０に記載の方法において、前記デコーダメッセージが可変ノードデコーダメッセージに対する制約ノードであることを特徴とする方法。
【請求項１２】
請求項１１に記載の方法において、
可変ノードデコーダメッセージに対する前記制約ノードをメモリに記憶するステップと、
可変ノードデコーダメッセージに対する前記記憶済みの制約ノードを可変ノードプロセッサへ出力するステップと、
可変ノードデコーダメッセージに対する前記制約ノードの関数として制約ノードメッセージに対する可変ノードを形成して、前記可変ノードプロセッサを操作するステップと、をさらに有することを特徴とする方法。
【請求項１３】
メッセージ受け渡し用デコーダによる方法において、
量子化対数尤度値を形成するために、１／２ｌｏｇ２の整数倍の量子化ステップサイズを用いて入力値を量子化するステップと、
前記量子化対数尤度値を入力値として用いて、メッセージ受け渡し用デコーダ処理操作を実行するステップと、を有することを特徴とする方法。
【請求項１４】
請求項１３に記載の方法において、入力値を量子化する前記ステップが、
符号ビットと絶対値との組み合わせとして構成される前記量子化対数尤度値の符号ビットと絶対値とを形成するステップを含むことを特徴とする方法。
【請求項１５】
請求項１４に記載の方法において、メッセージ受け渡し用デコーダ処理操作を実行する前記ステップが、
変換済み絶対値を形成するために、前記量子化対数尤度値に含まれる絶対値の関数として一定数をシフトするステップと、
出力用変換済み絶対値を形成するために、前記変換済み絶対値に対して少なくとも１回のチェックノード処理操作を実行するステップと、を含むことを特徴とする方法。
【請求項１６】
請求項１３に記載の方法において、前記尤度値が対数尤度比または対数尤度比の近似値であることを特徴とする方法。
【請求項１７】
請求項１３に記載の方法において、
送信値を検出するステップと、
前記対数尤度値を形成するために、前記検出した送信値に定数を乗算するステップと、を有することを特徴とする方法。
【請求項１８】
請求項１３に記載の方法において、メッセージ受け渡し用デコーダ処理操作を実行する前記ステップが、前記量子化対数尤度値を入力値として用いて可変ノード処理操作を実行するステップを含むことを特徴とする方法。
【請求項１９】
請求項１８に記載の方法において、前記可変ノード処理操作が低密度パリティチェック符号可変ノード処理操作であることを特徴とする方法。
【請求項２０】
検出した値を処理する装置において、
量子化対数尤度値を形成するために、１／２ｌｏｇ２の整数倍に量子化した対数尤度値を形成する手段と、
前記量子化対数尤度値を入力値として用いてパリティチェック復号化処理を実行するための、対数尤度値を形成する前記手段と結合されたパリティチェックデコーダと、を有することを特徴とする装置。
【請求項２１】
請求項２０に記載の装置において、前記パリティチェックデコーダが、
前記形成した量子化対数尤度値のうちの少なくともいくつかを用いて可変ノード処理操作を実行する可変ノード処理回路と、
可変ノード処理により形成した量子化対数尤度値に対してチェックノード処理操作を実行するチェックノード処理回路と、を備えることを特徴とする装置。
【請求項２２】
請求項２１に記載の装置において、
個々の形成した量子化対数尤度値が符号ビットと絶対値とを含み、
変換済み絶対値を形成するために、前記チェックノード処理回路が、少なくとも１つの量子化対数尤度値の中に含まれる前記絶対値の関数として一定数をシフトするシフト回路を備えることを特徴とする装置。
【請求項２３】
請求項２２に記載の装置において、前記チェックノード処理回路が、
出力用変換済み絶対値を形成するために、前記変換済み絶対値に対して少なくとも１回のチェックノード処理操作を実行する手段をさらに備えることを特徴とする装置。
【請求項２４】
メッセージ受け渡し復号化処理の一部としてノード処理操作を実行する装置であって、
１ノード毎に複数のノードに対応する１組の入力メッセージを受信し、ノードに対応する１組のメッセージ内のメッセージ数が、前記ノードのレベルＤ（但しＤはゼロでない正の整数）に等しい入力メッセージを順番に処理する累算器モジュールを有する装置において、上記累算器モジュールが、さらに、
個々の受信メッセージ値の関数として、ノードに対応する１組のメッセージ内の個々の受信した組のメッセージ用として生成する１つの総ノードサムを形成する加算回路と、
前記形成された総ノードサムを記憶する記憶装置と、
前記加算回路が処理した前記入力メッセージを記憶して、前記入力メッセージが対応するノードのレベルに比例する時間内に個々のトータルサムを形成する制御可能な遅延ユニットと、
ノードに対応するトータルサムと、該ノードに対応する出力メッセージとから、前記ノードに対応する遅延メッセージを形成するメッセージ形成モジュールと、を有し、前記メッセージ形成モジュールが、ノードに対応する個々の入力メッセージに対して１つの出力メッセージを形成することを特徴とする装置。
【請求項２５】
請求項２４に記載の装置において、前記メッセージ形成モジュールが、
ノードに対応する個々の遅延メッセージ値を前記ノードに対応するトータルサムから減算するための、前記記憶装置および前記遅延素子と結合された減算回路をさらに有することを特徴とする装置。
【請求項２６】
請求項２５に記載の装置において、前記制御可能な遅延ユニットが、該ユニットにより受信中のメッセージに対応するノードレベルを示すノードレベル信号を受信する入力部を備えることを特徴とする装置。
【請求項２７】
請求項２６に記載の装置において、先入れ先出しデータ記憶装置として前記制御可能な遅延ユニットを実現することを特徴とする装置。
【請求項２８】
請求項２５に記載の装置において、前記加算回路が、
入力メッセージを受信する第１の入力部を備えた加算器と、
前記加算器により形成されたランニングサムを記憶するための、および、前記記憶されたランニングサムを出力するための、前記加算器および前記記憶装置と結合された追加記憶装置と、
前記追加の記憶装置から前記記憶済みランニングサムを受信するための、および、ノードクロック信号の制御の下で制御される前記加算器の第２の入力部へ、前記記憶済みランニングサムと０のうち一方を出力するための、前記追加記憶装置と結合された多重化装置と、を含むことを特徴とする装置。
【請求項２９】
請求項２８に記載の装置において、
前記記憶装置が、前記ノードクロック信号を受信する制御入力部をさらに備え、前記記憶装置が、前記ノードクロック信号の指示の下で前記総ノードサムとして用いられる前記記憶済みランニングサムを記憶することを特徴とする装置。
【請求項３０】
請求項２９に記載の装置において、
前記ノードクロック信号をオンにセットして、前記加算回路がノードに対応する第１のメッセージを受信したとき、前記多重化装置に０を出力させる手段をさらに有することを特徴とする装置。
【請求項３１】
請求項３０に記載の装置において、前記ノードクロック信号は、前記多重化装置に０を出力させると同時に、前記記憶装置に前記総ノードサムとして前記ランニングサムを記憶させることを特徴とする装置。
【請求項３２】
メッセージ受け渡し復号化システムで使用するノードプロセッサにおいて、
ノードに対応する１組の受信メッセージから総メッセージ合計を形成する累算器モジュールと、
前記記憶済みメッセージが対応するノードのレベルに正比例する時間中、個々の組の受信メッセージ内のメッセージを記憶する可変遅延素子を備えたメッセージ遅延ラインと、
前記累算器モジュールおよび前記メッセージ遅延ラインと結合された減算器モジュールとを備え、該減算器モジュールは、ノードに対応する個々の遅延メッセージを減算して、前記遅延メッセージの減算時に、前記累算器モジュールが形成した前記総メッセージ合計を同じノードに対応する組の受信メッセージから形成することを特徴とするノードプロセッサ。
【請求項３３】
請求項３２に記載のノードプロセッサにおいて、前記累算器モジュールが、
メッセージが処理される対象ノードに対応する累積されたサムを記憶するラッチを備え、累積されたサムが、前記ラッチに順次記憶される異なるノードに対応することを特徴とするノードプロセッサ。
【請求項３４】
請求項３３に記載のノードプロセッサにおいて、前記ノードプロセッサが、
ノードに対応するメッセージのランニングサムを形成する手段と、
前記ラッチに前記ランニングサムを記憶するために用いる制御信号に応じて前記ランニングサムをリセットする手段と、をさらに備え、前記記憶されたランニングサムが累積されたサムであることを特徴とするノードプロセッサ。
【請求項３５】
請求項３４に記載のノードプロセッサにおいて、
前記ノードプロセッサが可変ノードプロセッサであり、
前記累算器モジュールが、前記ラッチに前記ランニングサムを記憶する前にメッセージの前記ランニングサムに入力値を加算する加算器をさらに備えることを特徴とするノードプロセッサ。
【請求項３６】
請求項３４に記載のノードプロセッサにおいて、前記可変遅延素子が複数のメッセージ記憶位置を含み、前記複数のメッセージ記憶位置のメッセージ記憶位置の数は、前記ノードプロセッサが実行する処理操作の対象となるノードの最高レベルと少なくとも同じ大きさの数となることを特徴とするノードプロセッサ。
【請求項３７】
請求項３６に記載のノードプロセッサにおいて、前記可変遅延素子が、前記可変遅延素子が受信する前記メッセージに対応するノードのレベルを示す信号を受信する制御入力部をさらに備えることを特徴とするノードプロセッサ。
【請求項３８】
メッセージ受け渡し用デコーダでノード処理操作を実行する方法において、
ノードに対応する個々の処理対象メッセージを順次受信するステップであって、同じノードに対応するメッセージは１組のメッセージの一部となり、複数の異なるノードに対応する組のメッセージを或る時間にわたって受信するステップと、
トータルサムを形成するのに用いる組のメッセージと同じノードに対応する総メッセージ合計をノードに対応する個々の組の受信メッセージから形成するステップと、
前記個々の受信メッセージが対応するノードのレベルに正比例する時間だけ個々の受信メッセージを遅延させるステップと、
前記遅延メッセージと同じノードに対応する前記総メッセージ合計から個々の遅延メッセージを減算し、それによって、出力メッセージを形成するステップと、を有することを特徴とする方法。
【請求項３９】
請求項３８に記載の方法において、個々の各受信メッセージを遅延させる前記ステップが、
処理対象として受信するメッセージが対応するノードレベルを示す制御信号を受信するステップ、を含むことを特徴とする方法。
【請求項４０】
請求項３９に記載の方法において、
個々の組の受信メッセージに対する前記総メッセージ合計を形成するために、受信メッセージのランニングサムに個々の受信メッセージを加算するステップをさらに有することを特徴とする方法。
【請求項４１】
請求項４０に記載の方法において、
１組のメッセージ内の最後のメッセージがランニングサムに加算されるとすぐに、記憶装置内へ前記ランニングサムをラッチするステップをさらに有し、前記ラッチされたランニングサムが総メッセージ合計となることを特徴とする方法。
【請求項４２】
請求項４１に記載の方法において、
前記記憶装置内へ前記ランニングサムをラッチする前に、前記ランニングサムに入力値を加算するステップをさらに有することを特徴とする方法。
【請求項４３】
請求項４１に記載の方法において、直前の受信メッセージとは異なるノードに対応するメッセージを受信する度に、前記ランニングサムを０に初期化するステップをさらに有することを特徴とする方法。
【請求項４４】
請求項４１に記載の方法において、同じ制御信号によって前記ラッチと初期化ステップとを制御することを特徴とする方法。
【請求項４５】
請求項４０に記載の方法において、前記形成済み出力メッセージを１回に１つずつ順番に出力するステップをさらに有することを特徴とする方法。
【発明の詳細な説明】
【関連出願についての記載】
【０００１】
本願は、米国仮出願第６０／３２８，４６９号（２００１年１０月１０日出願）の利益と、米国仮出願第６０／２９８，４８０号（２００１年６月１５日出願）の利益とを主張するものであり、米国特許出願明細書第０９／９７５，３３１号（２００１年１０月１０日出願）の一部継続特許である。上記特許の各々は本願で参照により援用される。
【技術分野】
【０００２】
本発明は、例えば、低密度パリティチェック（ＬＤＰＣ）符号のようなパリティチェック符号を利用することにより、２進データ内のエラー検出および／またはエラー訂正を行う方法及び装置を目的とする。
【背景技術】
【０００３】
エラー訂正符号は、通信及びデータ記憶システムに遍在するものである。最近、低密度パリティチェック（ＬＤＰＣ）符号として公知の符号の種類に相当の関心が生れている。
【０００４】
ＬＤＰＣ符号は、タナー（Tanner）グラフとしばしば呼ばれる２部分グラフにより好適に表される。このグラフでは、一方の組のノード（可変ノード）は符号語のビットに対応し、チェックノードと呼ばれることもある他方の組のノード（制約ノード）は、符号を定義するパリティチェック制約条件の組に対応する。上記グラフのエッジは可変ノードを制約ノードに接続させる。グラフのエッジにより接続している場合、可変ノードと制約ノードは隣接ノードと言われる。説明を簡略にするために、本願では、一対のノードは多くて１つのエッジに接続しているものと一般に仮定する。個々の可変ノードに対して１ビットの符号語が対応づけられる。場合によっては、符号語からこれらのビットの若干をパンクチャする（除去する）こともある。説明を簡略にするために、本願ではパンクチャリングを利用しないものと一般に仮定する。
【０００５】
個々の制約ノードに対して、（可変ノードとビットとの対応によって）制約ノードと隣接するビット０モジュロ２のサムとなる場合、すなわちビットが偶数個の１を含む場合、かつ、この場合に限って、可変ノード列と１対１で対応するビット列が当該符号の符号語となる。
【０００６】
エッジに沿ったグラフの範囲内のメッセージの交換を行い、着信メッセージに基づくノードでの計算によりこれらのメッセージの更新を行うことによって、ＬＤＰＣ符号語の復号化に用いられるデコーダおよび復号化アルゴリズムが作動する。このようなアルゴリズムは一般にメッセージ受け渡しアルゴリズムと呼ばれる。グラフ内の各可変ノードには、受信値と命名されるソフトビットが最初に与えられる。このソフトビットは、通信チャネルなどからの観察により決定されるような、対応ビット値の推定値を示すものである。個々のビットの推定値は統計的に独立したものであることが理想的である。この理想は満たされない場合が多く、実際に満たされていない。受信値の収集により受信語が構成される。本願の目的として、受信装置などが通信システムで観察した信号を受信語と特定することができる。
【０００７】
可変ノードや制約ノードなどのノードに結合するエッジの数は、ノードのレベルと呼ばれる。正則グラフや正則符号はすべての可変ノードが同一のレベル、ｊなど、を有するものであり、すべての制約ノードは同一のレベル、ｋなど、を有する。この場合、上記符号は（ｊ，ｋ）正則符号であると言うことができる。これらの符号は、最初、Gallager（１９６１年）により発明されたものであった。“正則”符号とは対照的に、非正則符号とは異なるレベルの制約ノードおよび／または可変ノードを持つ符号である。例えば、可変ノードのなかには、レベル４の可変ノードもあれば、レベル３の可変ノードもあり、さらにレベル２の可変ノードもある。
【０００８】
非正則符号はその表現および／または実現がより複雑となる場合があるのに対して、非正則ＬＤＰＣ符号の方は、正則ＬＤＰＣ符号と比べると、優れたエラーの訂正／検出性能を示すことが可能であることが証明されている。
【０００９】
復号化処理についてさらに正確な説明を行うために、本願ではＬＤＰＣグラフの記述に際してソケットという考えが導入される。ソケットとは、グラフ内のエッジをグラフ内のノードに対応するものと解釈することができる。各ノードには、個々のエッジについて１個のソケットがあり、個々のエッジは上記ソケットに結合し、これらのエッジはソケットの中へ“プラグイン”される。したがって、レベルｄのノードは、このノードに結合するｄ個のソケットを持つことになる。グラフがＬ個のエッジを有する場合、可変ソケットと呼ばれるＬ個のソケットがグラフの可変ノード側に設けられ、制約ソケットと呼ばれるＬ個のソケットがグラフの制約ノード側に設けられる。特定及び順序づけを行う目的のために、可変ソケットに１、．．．、Ｌと番号を付けることができる。これによって可変ノードに結合する可変ソケットが連続して出現することになる。このような場合、最初の３個の可変ノードが、それぞれ、レベルｄ１、ｄ２、ｄ３を持っていれば、可変ソケット１、．．．、ｄ１は第１の可変ノードに結合し、可変ソケットｄ１＋１、．．．、ｄ１＋ｄ２は第２の可変ノードに結合し、可変ソケットｄ１＋ｄ２＋１、...、ｄ１＋ｄ２＋ｄ３は第３の可変ノードに結合する。制約ノードソケットにも同様に１、．．．、Ｌと番号を付けることが可能であり、１つの制約ノードに結合する制約ソケットが連続して出現する。エッジは、ソケットのペアリングと見ることができる。このペアリングはグラフの各々の側から伸びる個々の対からなるものである。したがって、グラフのエッジはインタリーバすなわちグラフの一方の側、例えば可変ノード側などから他方の側、例えば制約ノード側などへのソケットに対する順列を表す。これらのシステムと関連する順列は複雑なものとなる場合が多い。
【００１０】
長さ１０とレート１／２とから成る（３，６）正則ＬＤＰＣ符号を確定する例示の２部分グラフ１００が図１に示されている。長さ１０は、１０個の可変ノードＶ１〜Ｖ１０が存在することを示し、個々の可変ノードは符号語Ｘ１〜Ｘ１０の１ビットと特定され（この場合、パンクチャリングは行われない）、一般に参照番号１０２によって特定される。レート１／２は、可変ノードの数の１／２のチェックノードが存在することを示す。すなわち、参照番号１０６によって特定される５個のチェックノードＣ１〜Ｃ５が存在する。後述するように、レート１／２は、５個の制約条件が線形的に独立していることをさらに示す。ライン１０４の個々のラインは、チェックノードと可変ノードとの間の通信路や接続部などのエッジを表し、上記各ラインは上記エッジに接続する。各エッジによって、可変ソケットと制約ソケットの２つのソケットが特定される。エッジには、その可変ソケットやその制約ソケットに基づいて番号を付けることができる。可変ソケットが可変ノードに接続するノードポイントで可変ノード側にエッジの順序が出現するように、可変ソケットの番号付けは（最上部から底部への）エッジの順序に対応している。制約ソケットが制約ノードに接続しているノードポイントで制約ノード側にエッジの順序が出現するように、制約ソケットの番号付けは（最上部から底部への）エッジの順序に対応している。復号化中、メッセージはエッジに沿って双方向に受け渡される。したがって、復号化処理の一部として、制約ノードから可変ノードへエッジに沿ってメッセージの受け渡しが行われる。また、可変ノードから制約ノードへの逆の受け渡しの場合も同様のメッセージの受け渡しが行われる。
【００１１】
グラフを用いて符号を表す代替例として、図２に図示のような行列表現の利用がある。符号の行列表現では、パリティチェック行列と一般に呼ばれる行列Ｈ２０２には、関連するエッジ接続と、可変ノードと、制約ノード情報とが含まれる。説明を簡略にするために、本願では多くて１つのエッジが任意の一対のノードに接続すると仮定している。行列Ｈでは、個々の列は可変ノードのうちの１つのノードに対応し、一方、個々の行は制約ノードのうちの１つの制約ノードに対応する。例示の符号には１０個の可変ノードと５個の制約ノードとが存在するため、行列Ｈには１０個の列と５個の行とが含まれる。エッジがグラフ内に存在すれば、すなわち、２個のノードが隣接ノードであれば、特定の可変ノードと特定の制約ノードとに対応する行列のエントリは１にセットされ、２つのノードが隣接ノードでなければ、行列のエントリは０にセットされる。例えば、可変ノードＶ１はエッジによって制約ノードＣ１に接続しているため、‘１’が行列２０２の最上位左手コーナーに配置される。これに対して、可変ノードＶ４は制約ノードＣ１に接続していないため、‘０’が行列２０２の第１の行の第４の位置に配置され、対応する可変ノードと制約ノードとが接続していないことが示される。Ｈの行がＧＦ［２］にわたって線形的に独立したベクトルであれば、制約条件は線形的に独立していると言える。可変ソケットであれ、制約ソケットであれ、ソケットによるエッジの番号付けはＨ内の‘１’の番号付けに対応する。行列２０８に図示のように、可変ソケットの番号付けは、列内での最上部から底部への番号付けと、左から右への列から列への処理とに対応する。行列２１０に図示のように、制約ソケットの番号付けは、行の両端にわたる左から右への番号付けと、行から行への最上部から底部への処理とに対応する。
【００１２】
行列表現の場合、送信対象の符号語Ｘは、処理対象の符号語のビットＸ１〜Ｘｎを含むベクトル２０６として表すことができる。行列２０６と２０２との積が０に等しい、すなわちＨｘ＝０の場合、かつ、この場合に限って、ビット列Ｘ１〜Ｘｎは符号語である。
【００１３】
ＬＤＰＣグラフに対応する符号語について解説するという文脈では、場合によっては符号語のパンクチャリングを行う場合もあると理解すべきである。パンクチャリングは、符号語からビットを除去して、より短い符号語を実際に形成するアクションである。ＬＤＰＣグラフの場合、これは、グラフ内の可変ノードのいくつかが、実際には送信されないビットに対応することを意味する。これらの可変ノードと、これら可変ノードに対応するビットとは状態変数と呼ばれることが多い。パンクチャリングを利用する場合、通信チャネルを介して物理的に通信されない符号語部の再構成を行うために、デコーダを用いることができる。パンクチャされた符号語を送信する場合、受信装置は脱落している受信語の値（ビット）を最初にポピュレートすることができ、例えば恣意的に１か０が割り当てられるが、これらの値が完全に信頼できるものではないという旨の、すなわち、上記値が削除されるという旨の表示（ソフトビット）が伴う。簡略のため、これらの受信機にポピュレートされた値は、これらの値の使用時に処理対象の受信語の一部であると本願では仮定する。
【００１４】
例えば、図３に図示のシステム３５０について考えてみる。システム３５０は、エンコーダ３５２と、デコーダ３５７と、通信チャネル３５６とを備える。エンコーダ３５０は、入力データＡを処理して符号語Ｘを形成する符号化回路３５３を備える。符号語Ｘには、エラー検出および／またはエラー訂正を目的として若干の冗長性が含まれている。通信チャネルを介して符号語Ｘを送信してもよい。或いは、何らかのデータ選択技術によりデータ選択装置３５４を介して符号語Ｘを分割して、それぞれ第１部分と第２部分Ｘ’、Ｘ”にすることができる。次いで、通信チャネルを介して符号語部分のうちの一方の部分、例えば第１部分Ｘ’などをデコーダ３５７を備えた受信機へ送信しながら、第２部分Ｘ”をパンクチャすることもできる。通信チャネル３５６により生じた歪みの結果、送信済みの符号語の部分が紛失したり、破損したりする可能性がある。デコーダから見ると、パンクチャされたビットは紛失ビットと解釈することもできる。
【００１５】
受信機では、ソフトビットが受信語の中へ挿入され、紛失ビットやパンクチャビットにとって代わる。この挿入済みソフトビットは、Ｘ”ビットの削除および／または送信時の紛失ビットを示す。
【００１６】
デコーダ３５７は、受信語Ｙと任意の挿入済みソフトビットとからなる完全な符号語Ｘの再構成を図り、次いで、データ復号化処理を実行して、上記再構成した符号語ＸからＡの形成を行う。
【００１７】
デコーダ３５７は、受信語Ｙと任意の挿入済みソフトビットとからなる完全な符号語Ｘを再構成するための、ＬＤＰＣデコーダなどのチャネルデコーダ３５８を備えている。さらに、デコーダ３５７は、符号語の中に含まれる冗長な情報を取り除いて、上記再構成した符号語Ｘから元の入力データＡを形成するためのデータデコーダ３５９を備えている。
【００１８】
受信語に対してＬＤＰＣ復号化処理、例えばエラー訂正処理とエラー検出処理などを実行することにより、ＬＤＰＣ符号化と関連して形成された受信語を処理して、再構成したバージョンの元の符号語を作成できることが理解される。次いで、この再構成した符号語に対してデータの復号化を行い、符号化した原データの回復を行うことができる。データ復号化処理は、上記再構成済みの符号語からある特定のサブセットのビットを単純に選択するなどの処理であってもよい。
【００１９】
上述のように、ＬＤＰＣ復号化処理には一般にメッセージ受け渡しアルゴリズムが含まれる。多くのおそらく有用なメッセージ受け渡しアルゴリズムが存在するが、このようなアルゴリズムの利用はＬＤＰＣ復号化に限定されるものではない。以下詳細に後述するように、本発明は、多くの状況で非常に良好で最適に近いパフォーマンスを示すことが多い簡単な、例えば複雑さの少ないハードウェアによるデコーダアルゴリズムの実施構成を提供する方法および装置を目的とするものである。本発明が提案するアルゴリズムは、周知の信頼度伝播アルゴリズムに近似したものと見ることができる。
【００２０】
以下のセクションで解説する本発明を容易に理解するために、信頼度伝播について以下簡単に数学的説明を行う。
【００２１】
（２進）ＬＤＰＣ符号の信頼度伝播は以下のように表現できる。グラフのエッジに沿って送信されるメッセージは、可変ノードに対応するビットの対数尤度 log ｐ０ /ｐ１ と解釈される。ここで、（ｐ０，ｐ１）は対応ビットに対する条件つき確率分布を表す。但しｐｘは当該ビットが値ｘをとる確率を示す。受信機がデコーダへ出力するソフトビットも対数尤度の形で示される。したがって、これらの受信値すなわち受信語の要素は、通信チャネルが出力するビットの観察に対して条件付けられる対応ビットの対数尤度となる。一般に、メッセージｍは対数尤度ｍを表し、受信値ｙは対数尤度ｙを表す。パンクチャされたビットの場合、対数尤度受信値ｙは０にセットされ、ｐ０＝ｐ１＝１/２を示す。
【００２２】
次に、信頼度伝播のメッセージ受け渡し規則について考えることにする。メッセージは、チェックノードから可変ノードへのメッセージに対してはｍＣ２Ｖによって示され、可変ノードからチェックノードへのメッセージに対してはｍＶ２Ｃによって示される。ｄ個のエッジを持つ可変ノードについて考えることにする。個々のエッジｊ＝１，．．．，ｄについて、ｍＣ２Ｖ(i)はエッジｉの着信メッセージを示すものとする。復号化処理の初期化時に、本願ではすべてのエッジに対してｍＣ２Ｖ＝０とセットする。一般に、可変ノードからの出力メッセージはｍＶ２Ｃ(ｊ）＝ y + (Σdi=1 ｍＣ２Ｖ(i))-ｍＣ２Ｖ(ｊ) によって示される。この演算に対応する（エッジメッセージではない）ノードから得られる出力用復号化ソフト値は ｘｏｕｔ ＝y + (Σdi=1 ｍＣ２Ｖ(i))によって示される。この出力に対応する出力用ハード決定はｘｏｕｔの符号から得られる。
【００２３】
チェックノードにおいて、チェックノードの‘符号’と絶対値とを用いてメッセージを表すようにする方が好都合である場合が多い。したがって、メッセージｍに対して、ｍｐ∈ＧＦ［２］はメッセージの‘パリティ’を示すものとする。すなわち、ｍ  ０ならばｍｐ＝０、ｍ＜０ならばｍｐ＝１となる。さらに、ｍｒ∈［０，∞］はｍの絶対値を示すものとする。したがって、
2005506733.tif 000003
が得られる。チェックノードにおいて、ｍｐの更新値とｍｒの更新値とは別個の値となる。本願では、レベルｄのチェックノード用として、以下の式が得られる：
2005506733.tif 000004
但し、すべての加算がＧＦ［２］にわたって行われ、
2005506733.tif 000005
但し本願では、Ｆ（ｘ）：＝ｌｏｇ  ｃｏｔｈ（ｘ／２）と定義する。上記双方の式では、上付添字Ｖ２Ｃは制約ノードにおける着信メッセージを示す。本願では、Ｆはそれ自身の逆数、すなわち、Ｆ−１（ｘ）＝Ｆ（ｘ）であることに留意されたい。
【発明の開示】
【発明が解決しようとする課題】
【００２４】
本発明は、メッセージ受け渡し復号化技術と関連して利用される復号化処理の実行方法および装置を目的とするものである。本発明の技術はＬＤＰＣ符号に関して使用するのに特に適している。
【課題を解決するための手段】
【００２５】
本願の背景についてのセクションで、本願出願者は、ＬＤＰＣ復号化と関連して利用可能な信頼度伝播アルゴリズムに関する数学的記載を行った。上記記載によれば、アルゴリズムの実行時に遭遇する主要な困難は関数Ｆとその逆関数に関わるものであることは明らかである。その他の必要な処理は実行が比較的簡単なものとなる傾向がある。
【００２６】
ＬＤＰＣデコーダのハードウェア実施構成を容易にするために、本発明のいくつかの実施形態では、対数尤度値が１／２ｌｏｇ２の整数倍に量子化される。例えば、対数尤度値は対数尤度比またはその近似値としてもよい。
【００２７】
対数尤度比は以下のように説明することができる。ｘをビットとする。おそらく他のビットと共にｘは信号として送信され、受信機が結果としてｚを観察したと仮定する。ｘの対数尤度比は
2005506733.tif 000006
と定義される。但し、ｐ（ｚ｜ｘ＝ｉ）は、条件ｘ＝ｉの場合にｚが観察される条件つき確率を示す。信号設定方式、チャネルモデルなどに応じてｙを計算するための多くの可能な方法および形態が存在する。ｘに対する２つの可能性が事前に予想されると仮定すると、その尤度比
2005506733.tif 000007
はｚが既知の場合のｘの事後の確率すなわち
2005506733.tif 000008
に等しくなる。したがって、本願では対数尤度比を単にｙ＝log ｐ０ /ｐ１ と示す場合が多い。但し、ｐｉはｘ＝ｉという条件つき確率を示す。本発明の様々なＬＤＰＣ復号化の実施形態が行われる間、本願では、このような対数尤度比（メッセージなど）が少なくとも近似的に計算される。但し、条件設定情報は個々の反復に伴って増加する。
【００２８】
実際のデジタルメッセージ受け渡し用デコーダの実施構成では、デコーダメッセージは有限個のビットにより表される。本発明に基づく量子化の利用を予想して、本願では、スケーリングパラメータδを導入する。記載した本発明の例示実施構成では、メッセージは整数ｍであり、メッセージは対数尤度ｍδで表されると解釈される。したがって、例示の実施形態では、本発明のメッセージは整数であり、この整数は、本発明に基づいてδによりスケールされて、対応する対数尤度が確定される。
【００２９】
本発明に基づいて、本願では、実施にさらに適した別の関数に関数Ｆを置き換えることにより、本願の発明の背景のセクションで記載した関数Ｆへの近似が行われる。種々の実施形態では、本願で論じている最初の近似値はその逆数と共にわずかに修正される。そのため結果を出力するデコーダは真の信頼度伝播デコーダに近いパフォーマンスを示すことになる。
【００３０】
下記のように、ｅ−δｘでＦ（δｘ）を級数展開することにより上記近似という考えを理解することができる。
【００３１】
2005506733.tif 000009
したがって、δｘの大きな値に対して、関数ｌｏｇ（ｃｏｔｈ（δｘ／２））を２ｅ−δｘで十分に近似させることが可能となる。本発明の目標が複雑さの少ない実施構成を見つけ出すことであるということを考えると、２ｅ−δｘによる関数Ｆ（ｘ）の近似はきわめて魅力的である。Ｆ（ｘ）を２ｅ−δｘと単に置き換えれば、チェックノード更新の絶対値部分は下式の形をとることになる：
2005506733.tif 000010
但し［ｘ］はｘの整数部を示す。
【００３２】
δ＝ｌｏｇ２を選択した場合、チェックノードの信頼性の更新に必要な計算が特に単純となり、加算演算とシフト演算とを利用する実施構成が可能になることに留意されたい。おおよそ１／５よりも大きな符号レートに対して、δ＝ｌｏｇ２をセットすることにより、ほぼ最大の信頼度の伝播パフォーマンスを達成するのに十分な解決が得られるということがわかる。低いレートの場合、この量子化はあまりに粗すぎるものとなり、δ＝１／２ｌｏｇ２をセットする方が望ましい場合もある。このようにδを選ぶ主な利点として、ｌｏｇ演算の計算が大幅に単純化できるという点が挙げられる。
【００３３】
δ＝ｌｏｇ２の場合について考える。この場合、制約ノードの更新計算は下式の形をとる：
2005506733.tif 000011
本願で使用するのは対数関数の整数部であるため、プライオリティエンコーダとしてこの関数を実行することができる。すなわち、前提とする２進表現で第１の‘１’の位置を単に確定するだけでこの関数の実行が可能となる。
【００３４】
２ｅ−δｘによるｌｏｇ（ｃｏｔｈ（δｘ／２））の近似は、δｘが小さな値の場合、結果として比較的大きな誤りを生じる可能性がある。順関数と逆関数とを穏やかに調整することによりある程度のエラーの補正を行うことが可能となる。さらに詳しく言えば、制約ノードの更新中に小さなオフセットの印加が可能であり、本発明の種々の実施形態ではこのようなオフセットが印加される。上記により、更新計算は下式の形をとる：
2005506733.tif 000012
さらに、可変ノードでは上記更新計算は下式の形をとる：
2005506733.tif 000013
但し、Ｃ１とＣ２は定数であり、“priority”とは、議論している適切な２進表現で第１の‘１’を見つける処理を意味する。プライオリティエンコーダの意味と例示の実施構成に関しては以下の詳細な説明でさらに詳述する。
【００３５】
以下ハードウェアについて考察を行う。変換については当面無視して、メッセージ更新を行うための主計算が、単純化された形の下式を持つことに留意されたい。
【００３６】
2005506733.tif 000014
本願は、時間的に連続するメッセージ受け渡し処理の実行を提案するものである。着信メッセージは、例えばクロックサイクル当たり１メッセージずつ着信する。したがって、クロックサイクル当たり１つの出力エッジメッセージの形成が可能な効率的なパイプライン構造を設けることが望ましい。本発明には、上記計算の役割を上述のように実現する特別の構造、ノードプロセッサ、についての記載も含まれる。この特定の実施構成によってメッセージの受け渡し処理の効率的、能率的計算が行われる。
【発明を実施するための最良の形態】
【００３７】
上述のように、ＬＤＰＣデコーダの実施形態という文脈で、説明を目的として本発明の復号化方法および装置について記載する。図４と図５を参照しながら、ＬＤＰＣ符号の復号化に関係するステップについて最初に説明し、次いで本発明のさらに詳細な説明を行う。
【００３８】
図４は２部分グラフ４００を用いて例示の非正則ＬＤＰＣ符号を示す図である。このグラフにはｍ個のチェックノード４０２と、ｎ個の可変ノード４０６と、複数のエッジ４０４とが含まれる。チェックノードと可変ノードとの間のメッセージがエッジ４０４を介して交換される。受信語Ｙに対応するソフト入力ビットｙ１〜ｙｎと、ソフト（またはハード）出力Ｘ１〜Ｘｎとが参照番号４０８によって示されている。ｍ番目のチェックノードは参照番号４０２’を用いて特定され、ｎ番目の可変ノードは参照番号４０６’を用いて特定され、一方、ｎ番目のソフト入力ｙｎと、ｎ番目のソフト出力ｘｎとはそれぞれ参照番号４１０、４０９を用いて図４に示されている。
【００３９】
可変ノード４０６は、受信語ｙ１，．．．，ｙｎから得られる入力ソフト値と共に制約ノード４０２からのメッセージを処理して、可変ノードに対応する出力変数ｘ１，．．．，ｘｎの値を更新し、制約ノード用メッセージを形成する。個々の可変ノードに接続する個々のエッジ用の可変ノードにより１つのメッセージが形成される。上記形成されたメッセージは、エッジに結合する制約ノードへエッジに沿って可変ノードから送信される。説明を目的として、可変ノードから制約ノードへのメッセージは、本願では時々刻々略語Ｖ２Ｃを用いて示すことがある。一方、制約ノードから可変ノードへのメッセージは略語Ｃ２Ｖを用いて示す。この略語のＶ成分とＣ成分とに対して添字を加えて、特定のメッセージのソース／宛先として役立つ可変ノードと制約ノードのうちの特定の一方のノードを示すようにしてもよい。各制約ノード４０２は、エッジを介して可変ノードから受信したメッセージを処理する責任を果たす。可変ノードから受信したＶ２Ｃメッセージは制約ノード４０２により処理され、次いで、各制約ノードに結合するエッジに沿って返送されるＣ２Ｖメッセージが形成される。次いで、可変ノード４０６はソフト入力値と共にＣ２Ｖメッセージを処理し、新たなＶ２Ｃメッセージを形成し、送信し、次いでソフト出力ｘｉを形成する。可変ノード４０６での処理実行シーケンスには、チェックノード４０２へ形成済みメッセージを送信するステップと、可変ノードでソフト出力ｘｉを形成するステップと、チェックノードからメッセージを受信するステップとが含まれ、可変ノード４０６からの出力ｘｉによって、符号語が首尾よく復号化されたことが示されるまで、あるいは、固定メッセージの受け渡し反復回数の終了などの何らかの別の停止基準が満たされるまで、上記シーケンスを繰り返し、すなわち反復して実行してもよい。上述の処理シーケンスは、記載の順序で厳密に行う必要はないと理解すべきである。ノード処理は非同期的に進行してもよく、また、可変ノード処理と制約ノード処理とを同時に行ってもよい。それにもかかわらず、反復処理の論理フローは上述のものと同様のものとなる。
【００４０】
メッセージＶ２ＣおよびＣ２Ｖは、各々Ｋビットなどの１ビット以上であってもよい。但しｋはゼロでない正の整数値である。同様に、ソフト出力ｘｉは１ビット以上であってもよい。マルチビットメッセージとマルチビット出力とによって、上記メッセージまたは出力の信用性情報または信頼性情報を中継する機会が与えられる。マルチビット（ソフト）出力の場合、ソフト出力値の符号を用いて、復号化済み符号語のビットなどの、可変ノードに対応する復号化処理の単一ビットハード出力を行ってもよい。出力ソフト値は、復号化ソフト値に対応するものであってもよいし、或いは、ＬＤＰＣデコーダが唯一のモジュールである別のさらに大きな反復処理時に使用することも可能ないわゆる非本質的情報（対応する入力情報を除外する）に対応する値であってもよい。
【００４１】
ＬＤＰＣ符号に対応する反復メッセージ受け渡し処理について図５ａ〜５ｄを参照しながら以下さらに解説する。
【００４２】
ＬＤＰＣ符号の復号化時に、個々の制約ノードと可変ノードでの処理を独立に実行することも可能である。したがって、復号化処理の特定の反復に対して可変ノード処理と制約ノード処理のいくつかまたはすべてが終了するまで、可変ノード処理および／または制約ノード処理は例えば一度に１ノードずつ順番に実行してもよい。これによって、単一装置の処理用ハードウェアを設け、このハードウェアを再使用して、所望の場合、可変ノードおよび／または制約ノードの各々に対応する処理の実行が可能となる。ＬＤＰＣ復号化の別の重要な特徴として、特定の処理反復中に使用するＶ２ＣとＣ２Ｖメッセージを、例えば同一処理の反復中に、同時に形成する必要がないという点が挙げられる。これによって、利用メッセージの最後の更新以来の遅延時間に関わりなく、非同期的におよび同時に制約ノード処理と可変ノード処理とを実行できる実施構成が可能となる。すべての可変ノードと制約ノードとが受信メッセージを処理し、更新メッセージの形成に十分な数のメッセージ更新と反復とを実行した後、可変ノードの（ハード）出力は収束し、グラフが適切に設計され、処理中の受信語の中に残りの未訂正のエラーが存在しないと仮定される。
【００４３】
個々のチェックノードと可変ノードにおける処理を独立の処理と見ることができると仮定して、単一の例示チェックノードＣｎ５０２’と可変ノードＶｎ５０６’とで実行する反復処理について図５ａ〜５ｄを参照しながら以下さらに詳述する。説明を目的として、本願では量子化した信頼度伝播アルゴリズムが仮定されている。したがって、受信値と受信メッセージとは実数である。正の数はハードビット決定０に対応し、負の数はハードビット決定１に対応する。絶対値が大きければ大きいほど高い信頼性が示される。したがって、数０は絶対的信頼性の無さ（unreliability）を示し、（正負の）符号は無関係になる。このアルゴリズムで実行する計算の詳細については上記セクションに記載されている。
【００４４】
図５ａはＬＤＰＣ復号化処理時の初期ステップを示す。最初、処理対象の受信語から、受信値（対数尤度を表す１以上のビット）ｙｎなどのソフト入力が可変ノードＶｎ５０６’に出力される。復号化処理の開始時のＣ２Ｖメッセージと、ソフト出力Ｘｎ５０９とが最初０にセットされる。ゼロ値Ｃ２Ｖメッセージと入力ｙｎなどの受信した入力に基づいて、可変ノードＶｎ５０６’は、この可変ノードに接続している個々のチェックノード用の１つのＶ２Ｃメッセージを形成する。一般に、初期のステップでは、これらのメッセージの各々はｙｎに等しい。
【００４５】
図５ｂで、可変ノードＶｎ５０６’に接続するエッジの各々に沿って送信されている形成済みＶ２Ｃメッセージが示されている。したがって、チェックノードＣｍ５０２’を含む可変ノードＶｎ５０６’と結合されたチェックノード５０２の各々へ更新済みＶ２Ｃメッセージが送信される。
【００４６】
Ｖ２Ｃメッセージの形成に加えて、可変ノード処理の結果として、この処理を行う可変ノードに対応するソフト出力Ｘｎ５０９’の更新が行われる。ソフト出力Ｘｎの更新状態が図５ｃに示されている。異なるステップとして示してはいるが、Ｖ２Ｃメッセージの出力と同時にソフト出力の出力を行ってもよい。
【００４７】
以下さらに後述するように、本発明のいくつかの実施形態によれば、ソフト出力（あるいはソフト出力の対応するハード決定）を用いて、受信語から符号語をいつ回復したか、すなわちパリティ制約条件が出力値によっていつ満たされたかを判定するようにしてもよい。これによって、（得られた符号語が不正確である、すなわち、送信された符号語ではない場合はあるものの）首尾よく復号化が行われ、それによって、ある一定の最大許容回数のメッセージ受け渡し反復が終了する前に、タイミングの良く反復復号化処理の停止が可能となる。
【００４８】
チェックノードＣｍ５０２’などのチェックノードは、該チェックノードに接続しているエッジに沿ってＶ２Ｃメッセージを受信するとすぐに、チェックノード処理の実行が可能となる。受信したＶ２Ｃメッセージはチェックノードで処理されて、更新済みＣ２Ｖメッセージを形成し、特定のチェックノードに接続する個々のエッジに対して１つのＣ２Ｖメッセージが形成される。チェックノード処理の結果として、エッジに沿って可変ノードへ返送されるＣ２Ｖメッセージは、チェックノードに接続するもう一方のエッジで受信したＶ２Ｃメッセージの各々の値に依って変化するが、上記Ｃ２Ｖメッセージは、上記Ｃ２Ｖメッセージを送信している送信先の特定の可変ノードから受信したＶ２Ｃメッセージに依って（通常また好ましくは）変化することはない。したがって、Ｃ２Ｖメッセージを用いて情報の送信が行われる。この情報は、上記メッセージが送信される送信先ノード以外の可変ノードから受信したメッセージによって形成されるものである。
【００４９】
図５ｄは、ノード５０６’を含む可変ノードへの更新済みＣ２Ｖメッセージの受け渡しを示す。特に、図５ｄには、制約ノードＣｍ５０２’が、更新済みＣｍ２Ｖｎメッセージを可変ノードＶｎ５０６’へ出力しながら、２つの更新済みＣ２Ｖメッセージを出力している状態が示されている。Ｖｎ５０６’は、Ｖｎ５０６’が接続する別の制約ノードから追加の更新済みＣ２Ｖｎメッセージも受信する。
【００５０】
更新済みＣ２Ｖメッセージの受信時に、可変ノード処理を繰り返して、上記更新済みＶ２Ｃメッセージとソフト出力との形成が可能となる。次いで、デコーダの停止基準が満たされるまで、Ｃ２Ｖメッセージの更新をさらに繰り返すことなども可能である。
【００５１】
したがって、図５ａ〜５ｄに図示の処理は、復号化処理が停止されるまで、初期値ではなく更新済みメッセージ値を用いて第１の反復後に繰り返される。
【００５２】
本発明は、受け渡されるメッセージの形式と、これらのメッセージに対して実行される計算と、これらの計算を実行するハードウェア構造とに関する。本発明を文脈の中で説明するために、ＬＤＰＣデコーダの実施構成について簡単に述べる。この実施構成は例示を目的とするものである。効率的な実施構成アーキテクチャについては、“ＬＤＰＣ符号の復号化方法および装置”という名称の米国特許出願明細書第０９／９７５，３３３号（２００１年１０月１０日出願）に解説されている。この特許は本願に参照により明白に援用されている。
【００５３】
本発明の１つの特徴によれば、メッセージ受け渡し復号化用入力値ｙは、１／２ｌｏｇ２の整数倍となるように量子化した対数尤度値の形をとる。量子化対数尤度値の形成は受信値の処理を含むものであってもよい。この受信値から、尤度比やその近似値などの対数尤度値が形成される。次いで、これらの対数尤度値は、１／２ｌｏｇ２の整数比のステップサイズを用いて量子化され、量子化対数尤度値が形成される。これらの対数尤度値は、種々の実施形態で、対数尤度比またはその近似値となる。このような量子化された対数尤度比を利用することによりデコーダの実施構成が容易になる。
【００５４】
尤度比などの量子化対数尤度値を受信値から形成する回路は、受信機の中へ直接組み込むことも可能である。この受信機は、図６に図示のデコーダ６００などの本発明のメッセージ受け渡し用デコーダに先行する通信チャネル３５６の一部を形成する。
【００５５】
様々な回路を用いて、本発明に基づく量子化対数尤度比を形成してもよい。以下図１５を簡単に参照すると、受信値ｙｉｎから量子化された対数尤度比ｙ０を形成する例示回路１５００が示されている。図１５の回路は、付加ガウスノイズが存在するＢＰＳＫ（＋１，−１）シグナリングのケースに適している。この場合、個々の受信値は対応ビットの対数尤度比に比例すると仮定することができる。このような場合、単にある定数の逓倍により受信値を対数尤度比に変換することも可能である。
【００５６】
値ｙｉｎは、受信回路が受信した値であってもよい。この受信値を処理して、本発明のメッセージ受け渡し用デコーダが出力した対数尤度比ｙ０が形成される。回路１５００は、（２／ｓ２）だけ入力値Ｙｉｎを逓倍して対数尤度比を形成する乗算器１５０２を備える。但しｓ２は、通信チャネルが受信信号の中へ導入する付加ガウスノイズに対応する定数である。この結果生じる対数尤度比は次いで量子化装置１５０４により量子化され、１／２ｌｏｇ２の整数倍となる。乗数１５０２が形成する対数尤度比を１／２ｌｏｇ２により除し、次いで、絶対値が１５を上回る場合には、＋１５または−１５までこの結果を飽和し、上回らない場合には、量子化した対数尤度比ｙ０として上記結果値の５ｌｓｂｓ（最下位ビット）をとることにより量子化装置１５０４を実現することができる。次いで、デコーダ回路６００への入力としてこの量子化対数尤度比Ｙ０を出力することができる。
【００５７】
図６は、一度に１エッジずつ、メッセージ処理操作を順次実行する単純な直列デコーダ６００を描くものである。ＬＤＰＣデコーダ６００は、デコーダ制御モジュール６１０と、Ｖ２Ｃエッジメモリ６３０と、Ｃ２Ｖエッジメモリ６５０と、可変ノードプロセッサ６２０と、制約ノードプロセッサ６４０と、出力バッファ６６０とを備える。本発明に関して説明を簡略にするために、本願では、デコーダは一定の反復回数の間作動する、つまり収束検出を行わないものと仮定する。
【００５８】
Ｖ２Ｃエッジメモリ６３０とＣ２Ｖエッジメモリ６５０には、個々のＫビット位置が１つのエッジに対応する個々のＬＫビットメモリ位置が含まれ、Ｌは、使用ＬＤＰＣグラフ内のエッジの総数であり、Ｋはエッジに沿って交換されるメッセージ当たりのビット数である。出力バッファ６６０には、可変ノード出力値ｘを記憶するメモリが含まれる。この可変ノード出力値ｘはハード（１ビット）値またはソフト（１以上のビット）値のいずれであってもよい。
【００５９】
デコーダ制御モジュール６１０には記憶された形のグラフを記述する情報が含まれる。デコーダ制御モジュール６１０は、以下に説明するようなメッセージ受け渡し制御のためにこの情報を利用する。各受信値とメッセージはＫビットから構成されるものと仮定する。デコーダは連続して作動する。デコーダは可変ノード更新をまず実行し、次いで、制約ノード更新処理を実行する。デコーダは、このサイクルをある一定回数繰り返し、最終の可変ノード更新後に終了する。最初に、Ｃ２Ｖメッセージメモリが０でポピュレートされる（可変ノード処理と制約ノード処理とが物理的に同時に行われることに留意されたい。上述の順序は処理中の情報のフローを示すものである。）
以下可変ノードの更新について説明する。デコーダ制御モジュール６１０は、可変ノードソケットの順序でＣ２ＶメッセージメモリからＣ２Ｖメッセージの読み出しを行わせ、このＣ２Ｖメッセージを可変ノードプロセッサ６２０へ配信させる。デコーダ制御モジュール６１０は、当該時点にどのメッセージを読み出すべきかを示すメッセージ識別子（メモリ位置やポインタなど）をＣ２Ｖエッジメッセージメモリ６５０へ信号で送信する。図１を参照すると、例えば、可変ノードプロセッサ６２０へ配信される最初の３個のメッセージは可変ノードｖ１へ着信するメッセージである。可変ノードプロセッサ６２０へ配信される次の３個のメッセージは可変ノードｖ２へ着信するメッセージ、等々である。
【００６０】
所定ノードのメッセージは可変ノードプロセッサ６２０により処理される。可変ノードプロセッサ６２０は、デコーダ制御モジュール６１０から信号、ノード境界を示すノードクロック信号、を受信する。この信号は、可変ノードプロセッサに対して、現在処理されているノードのレベルについて実際に知らせる。特定ノードに対応する最後の着信メッセージの着信と完全に一致した時点で上記信号は送信可能であり、種々の実施形態で送信されている。
【００６１】
ノード更新計算は可変ノードプロセッサ６２０で実行される。発信用Ｖ２Ｃメッセージは、可変ソケット順に、すなわち着信メッセージのエッジ順に対応する順序で送出され、Ｖ２Ｃエッジメッセージメモリ６３０に記憶される。ソフト出力値やハード出力値は出力バッファ６６０に記憶される。可変ノード更新の終了時に、この更新が最後の更新でなければ、デコーダは制約ノード更新の実行へ進む。
【００６２】
以下制約ノードの更新について説明する。制約ノードの更新は、可変ノードの更新の場合と非常に似ているので簡単に説明する。デコーダ制御モジュール６１０は、Ｖ２Ｃメッセージメモリ６３０からのＶ２Ｃメッセージの読み出しを制約ソケット順に行わせ、制約ノードプロセッサ６４０への配信を行わせる。デコーダ制御モジュール６１０は、どのメッセージを読み出すかを示すメッセージ識別子（メモリ位置など）をＶ２Ｃエッジメッセージメモリ６３０へ信号で送信する。所定の制約ノード向けのメッセージは制約ノードプロセッサ６４０により処理される。制約ノードプロセッサ６４０は、ノード境界を示すデコーダ制御モジュール６１０から信号、ノードクロック信号を受信する。発信用Ｃ２Ｖメッセージは、制約ソケット順に、すなわち着信メッセージのエッジ順に対応する順序で送出され、これらのメッセージはＣ２Ｖエッジメッセージメモリ６５０に記憶される。
【００６３】
可変ノード更新と制約ノード更新とには共に完全な反復が含まれる。（前述したように、可変ノード処理と制約ノード処理とを同時に行ってもよい。）
図６に図示の例示ＬＤＰＣデコーダシステム６００という文脈で、本発明の様々なノードプロセッサ特性について以下説明する。本願では、本発明によるＬＤＰＣ復号化に利用可能な或る特定の組からなる計算とメッセージ形式とについて説明する。所定のノード用の複数のメッセージまたはすべてのメッセージが同時にプロセッサに着信し、複数のメッセージまたはすべてのメッセージのノード処理が同時進行する並列実施構成において、図６の直列デコーダにおけるノードプロセッサの実現時に説明したものと同じ計算が利用可能であることを理解されたい。さらに、ノードプロセッサを複製して、いくつかのノードの並列処理を同時に行うことも可能である。
【００６４】
本発明を具現化する例示の５ビットメッセージをベースとするアルゴリズムについて詳細な説明を行う。入力ソフト値とメッセージとは対数尤度比の形をとり、本発明に基づいてδ＝ｌｏｇ２の倍数で量子化される。したがって、５ビットのメッセージは、生じ得る整数値｛−１５、−１４，．．．，−１、０、１，．．．，＋１５｝を表す。実際には、“符号と絶対値”としてこれらのソフト値を表すと都合がよい。符号は、対応するビットに対して、対応するハード決定などの優先値を示す値０または１をとる。絶対値は符号の信頼性を示す：絶対値が大きいほど高い信頼性を示すものとなる。（あるＭ＜１５について、入力ソフト値の絶対値を｛０，１，．．．，Ｍ｝の範囲に限定することは一般に優れた着想である。上記表現では、符号０を持つ‘０’絶対値と符号１を持つ‘０’絶対値の２つの‘０’絶対値が実際には存在することにも留意されたい。）したがって、本願の例では、ｍｐが符号ビットを示し、ｍｒが信頼性を示す一対（ｍｐ，ｍｒ）からなる４ビットの負でない値としてメッセージが書き込まれる。このようなメッセージが得られたと仮定して、典型的なスケールされた対数尤度比、すなわち、
2005506733.tif 000015
を示すためにｍを用いることにする。可変ノードの更新式を以下に示す：
2005506733.tif 000016
出力メッセージｍＶ２Ｃ（ｊ）が値０を持つ場合、符号は任意に選ぶことができる。出力メッセージの絶対値が１５を上回る場合、この絶対値は飽和され、例えば１５にセットされる。
【００６５】
図７と図８とは、上述の直列デコーダに対する上記規則の例示実施構成を示す図である。図７は図６に描かれたデコーダに適した可変ノードプロセッサ７００の実施構成を示す。特定の可変ノードに対するメッセージ（ｍ）が順番に着信する。各メッセージｍはＫビットを含む。各受信メッセージは、加算器７１０によって、単位遅延素子７１２が出力した前回のサム、すなわち累積メッセージサムと加算される。加算器７１０へ出力された累積メッセージサムは、新たなノードに対応するメッセージの受信と共に“０”にリセットされる。受信したソフト入力値ｙは、加算器７２０において、遅延素子７１２が出力した累積メッセージサムに加算され、新たな累積されたサムＳＵＭが形成される。処理済みのノードに対応するすべてのメッセージが加算されて、完全な累積トータルサムを形成した場合、値ＳＵＭはラッチされ、ラッチ７３０に記憶される。外部ノードクロック信号の結果として上記ラッチングが行われる。上記外部ノードクロック信号のタイミングが制御され、完全なサムのラッチングが保証される。ノードクロック信号はノードレベルの関数として決定される。各受信メッセージは、可変遅延素子７６０を含む遅延ラインを介しても受け渡される。可変遅延素子７６０の継続時間は実施されるノードレベルに対応する。
【００６６】
特定の可変ノードに対応する、処理対象の第１のメッセージが遅延ラインから出現し、ラッチ７３０に記憶されたラッチ済みのトータルサムから加算器７４０によってメッセージ値が減算される。この出力結果は、飽和オペレータ（saturation operator）７７０を介して次に受け渡され、出力メッセージ値が、例えばＫビットに限定されるような所望の範囲内に在ることが保証される。飽和オペレータ７７０の前と後に配置される単位遅延素子７４２と７７２を用いて、可変ノード処理操作と制約ノード処理操作との同期が図られる。
【００６７】
図８は、図６に描かれているデコーダで使用するのに適した制約ノードプロセッサ８００の実施構成を示す。チェックノードプロセッサ８００は、分割回路８０１と、符号処理回路８０２と、絶対値処理回路８０４と、合成回路８９９とを備える。可変ノードプロセッサ７００の場合のように、特定のチェックノードに対するメッセージｍが順番に着信する。制約ノードの更新は、符号更新処理と絶対値更新処理とに分離され、分割回路８０１を用いて、メッセージ内の絶対値情報から符号ビットの分離が行われる。受信メッセージの単一符号ビットは分割回路８０１により分割され、符号ビット処理回路８０２へ出力されて処理される。Ｋビットのメッセージｍのうちの残りのＫ−１ビットはメッセージ処理回路８０４へ出力される。さらに、ノードクロック信号とノードレベル信号とが、符号処理回路８０２と絶対値処理回路８０４の双方の対応する入力部へ出力される。
【００６８】
符号処理回路８０２により実行されるような符号更新処理についてまず説明する。着信符号ビットは、排他的論理サム（ＸＯＲ）論理回路８１０の入力部へ出力される前に、単位遅延素子８０３により１クロックサイクル遅延される。ＸＯＲ回路８１０は、この着信符号ビットと、前回のＸＯＲの結果との排他的論理サムすなわちモジュロ２のサムを実行する。ここで前回のＸＯＲの結果は第２の単位遅延素子８１５が遅延させたもので、ＸＯＲ回路８１０の第２の入力へ出力される前のものである。このようにして、処理対象ノードに対応するすべての符号ビットのＸＯＲは、反復処理による総ＸＯＲの結果すなわち積ＳＵＭｓｉｇｎを形成する。値ＳＵＭｓｉｇｎは、当該ノードに対応する遅延符号ビットを持つ後続するＸＯＲ用として、ノードクロック信号８３０の制御の下でラッチ８３０に記憶される。ＭＵＸ８１３を使用して、ＸＯＲの対象値０が出力され、第１のメッセージの符号ビットは当該ノードに対応する。別の時点で、ＭＵＸ８１３は遅延されたＸＯＲの結果を出力する。
【００６９】
遅延素子８０３から始まるＸＯＲパスの中を通る受け渡しに加えて、可変遅延素子８２０を備えた遅延ラインを介して個々の符号ビットの受け渡しが行われる。素子８２０の遅延はノードレベル信号により制御され、その結果、符号ビットに課せられる遅延継続時間はノードレベルに対応することになる。ノードに対応するすべての符号ビットが合成されると、本願でＳＵＭｓｉｇｎとして示すトータルサム（排他的論理サム）がラッチ８３０に記憶される。値ＳＵＭｓｉｇｎのラッチングは、前述した可変ノード更新処理の場合のように外部ノードクロック信号の指示の下で行われる。この信号はＭＵＸ８１３の出力制御にも使用される。
【００７０】
可変ノードの更新の場合のように、符号ビットは遅延ラインから順番に出現する。この遅延符号ビットの値は、加算器８４０でＳＵＭｓｉｇｎから減算（排他的論理サム操作）される。この結果は出力メッセージの符号を構成する。いくつかの追加遅延素子８４１、８４３がプロセッサ８０２に挿入されていて、回路８０４が実行する絶対値更新と符号更新との同期保持が図られることに留意されたい。
【００７１】
絶対値処理回路８０４により実行される絶対値更新処理について次に説明する。第１のステップで、（Ｋ−１）ビットを用いて表される着信絶対値ｍＶ２Ｃｒ(i)が制約領域値に変換される。この変換は、変換回路８５０を用いて、メッセージｍＶ２Ｃｒ(i)を上記値Ｃ２-mv2cｒ(i)と置換するステップとなる。上記変換処理の目標は、単純サムと単純減算とを用いて制約処理を実行できる形式でメッセージ値を表すことである。実際には、シフト演算として上記変換の実行が可能となる。すなわち、値Ｃは２進形式で記憶され、ｍＶ２Ｃｒ(i)だけ右側へシフトされ、変換済みのメッセージが得られる。５ビットデコーダの例の場合、有効であることが判明した値Ｃが１６進数表記法で６０００により示される。
【００７２】
４ビットなどのさらにコンパクトなメッセージ絶対値部分の可変ノード領域表現から、１５ビットなどのメッセージレベル部分のさらに長い制約ノード領域表現への変更を行う転送変換処理９００について説明する詳細なフローチャートは図９を参照されたい。ステップ９０６で、可変ノード領域と制約ノード領域との間の変換に用いる定数Ｃは、受信メッセージの絶対値部分により示される場所を示す１０進値（数）分だけ右側へシフトされる。さらに、シフト演算の結果空いた左ビット位置（上位ビット）に０が挿入される。
【００７３】
例えば、ステップ９０２で１０進値の２を持つ４ビット（００１０）を入力すると仮定する。ステップ９０６で、２進定数Ｃ＝１１０００００００００００００は右側へ２つの場所分だけシフトされ、一番左側のビットは、００１１０００００００００００の制約ノード（２進）領域絶対値を結果として生じる０でパッドされる。
【００７４】
ステップ９０８で、その時制約ノードの形のメッセージの絶対値部分９１０（１５ビットなど）が出力され、さらなる処理が行われる。この出力値は、追加処理による制約ノード処理に適した変換済み絶対値を表す。
【００７５】
図８を再度参照すると、加算器８６０と可変遅延素子８８０への出力に先行して、単位遅延素子８５１を介して変換済み絶対値が受け渡されていることがわかる。
【００７６】
遅延素子８５１により出力されたエッジメッセージを、加算器８６０の遅延された出力に加算し、加算器８６０を用いて変換済みのエッジメッセージ絶対値のサムが形成され、累積されたサムＳＵＭｍａｇが形成される。この累積されたサムＳＵＭｍａｇはノードクロック信号の受信時にラッチ８７０に記憶され、ノードに対応するすべてのエッジメッセージが一括して加算されることが示されている。ｍｕｘ８６３の制御にもノードクロック信号が用いられ、ノードに対応する第１のメッセージが加算器８６０へ出力されると、“０”が出力される。したがって、ｍｕｘ８６０は、複数のノードの各ノードに対応するメッセージ処理の開始時に累積されたサムのリセット処理を行う。
【００７７】
変換済みの遅延エッジメッセージの絶対値は、その後遅延ライン８８０から出現し、これらの値は、単位遅延素子８９１への出力に先行して、加算器８９０内の記憶済みのサムＳＵＭｍａｇから減算される。次いで、変換回路８９５が遅延素子８９１から得た出力用遅延絶対値に対して逆変換が実行される。
【００７８】
制約ノードから可変ノードメッセージ表現への変換を実行するこの第２の変換回路は１つの実施形態例では以下のように作動する。プライオリティエンコーダが、制約領域絶対値メッセージの２進表現で表される第１の‘１’の位置を確定する。この位置は右側から表現することにする。したがって、ｖは制約領域絶対値を示すものとし、ｌ（ｖ）は制約領域の“位置”を示すものとする。一般に、ｖの１０進整数値ｖが２ｊ以上かつ２ｊ＋１−１以下であれば、ｌ（ｖ）＝ｊとなる。ｖが０であれば、ｌ（ｖ）は０となる。ｌ（ｖ）が１５以上であれば、（４ビット可変ノードメッセージ絶対値の場合）出力用絶対値は０にセットされる。ｌ（ｖ）が１５未満であれば、この出力用絶対値は１５−ｌ（ｖ）となる。
【００７９】
図１０はステップ８９５で実行される変換処理１０００を示すフローチャートであり、このフローチャートは、制約ノード領域から得られるメッセージ絶対値を元の可変ノード領域表現にする変換を含む。この時点で、ステップ８６０と８９１で実行されるメッセージ加算演算および減算演算の結果として、メッセージ絶対値は、ステップ８５０（この場合メッセージは１５ビット長であった）の出力時よりも多いビット（メッセージは２０ビット長であってもよい）を含むようにしてもよいことに留意されたい。
【００８０】
ステップ１００４で、制約ノード領域形式でのメッセージの絶対値部分１００２を受信し、右側からのビット位置をカウントすることにより左側からの最初の“１”の位置が決定される。例えば、絶対値部分１００２が（００００００１００００００００００１００）の場合、プライオリティエンコーダを用いて、左側からの第１の‘１’ビットが、右側から測定してビット位置１４に生じることを確認することが可能となる。
【００８１】
次に、ステップ１００６で、所定のビット位置は、可変ノード領域形式でのメッセージ絶対値表現に用いるビット数で表すことができる最大値と比較される。例えば、可変ノード領域でメッセージ絶対値用として４ビットを使用した場合、最大値は１５になる。このような場合、所定のビット位置が１５以上であれば、処理はステップ１００８へ進む。所定のビット位置が１５未満であれば、処理はステップ１００６からステップ１０１０へ進む。
【００８２】
ステップ１００８で、可変ノード領域メッセージ絶対値表現のすべてのビット、例えば４ビットは０にセットされ、それによって受信した制約ノードメッセージの絶対値１００２の可変ノード領域形式が形成される。
【００８３】
ステップ１０１０の処理について説明する。ステップ１０１０で、可変ノード領域形式でのメッセージ絶対値表現に用いるビット数を用いて表すことができる最大値から、ステップ１００６で得られる特定されたビット位置の数を減じることにより可変領域形式内でのメッセージ絶対値が形成される。例えば、可変ノード領域での４ビット絶対値表現を仮定した場合、ステップ１０１０で、ステップ１００６からのビット位置、例えば本例の場合の１４が１５から減算されることになり、この結果、２進で（０００１）として表される１（１５−１４＝１）の可変ノードメッセージ絶対値が得られることになる。
【００８４】
ステップ１０１２で、今度は、可変ノード領域絶対値形式のメッセージ絶対値１０１４が、例えば遅延素子８９７へ出力される。
【００８５】
制約ノードプロセッサのいくつかの実施構成では、制約領域形式よりむしろ可変領域形式で信頼性を遅延ライン８８０に記憶する方が好都合である。これによって複雑さを少なくすることが可能となる。というのは、制約領域形式よりも可変領域形式の方が必要なビット数が大幅に少なくて済むからである。この実施形態用の図８を修正するために、遅延ライン８８０の出力部に機能ブロック８５０を複製し、機能ブロック８８０の後ではなく、機能ブロック８８０の前で遅延ラインへの入力を受信するようにする。
【００８６】
本願の上記例では、（１符号ビットと４絶対値ビットの）５ビット可変ノードメッセージを用いたが、必要に応じて定数を調整しながら利用範囲を増減するだけで、上記ビットよりも少ないビット数またはそれ以上のビット数を含むメッセージに対して上記記載の規則を適用できることは理解できよう。
【００８７】
場合によっては、対数尤度比用の２ｌｏｇ２の間隔の方が、上記解説した例示のｌｏｇ２間隔よりも望ましいこともあることは理解できよう。このケースは一般に、さらに少数のビット数から構成されるメッセージと関連して利用される。ｌｏｇ２から２ｌｏｇ２への変更は、制約ノードにおける上述の更新規則の変更を伴うことになるが、可変ノードでの上述の更新規則の変更は行われない。制約ノードでの修正は、すべてのメッセージがｌｏｇ２間隔の場合と同様であり、偶数値の絶対値だけが許容され、かつ、この場合、絶対値の最終ビットは常に０になり、この最終ビットをメッセージの一部として受け渡す必要はなく、種々の実施形態では、この最終ビットがメッセージの一部として受け渡されることはないことを指摘しておく。
【００８８】
別のいくつかのケースでは、１／２ｌｏｇ２の間隔の方が望ましい場合もある。図１１と図１２は、１／２ｌｏｇ２間隔の実施形態に対する転送変換処理及び反転変換処理１１００、１２００を描く図であり、上記変換は、ｌｏｇ２間隔の実施形態用としてそれぞれ図９と図１０に示す変換に対応するものである。再言するが、例えば変換処理８５０と８９５などの更新規則は制約ノードで変更が生じるが、可変ノードでは変更が生じることはない。絶対値の最下位ビット（ビット順が与えられた場合の最も右側のビット）が０の場合、着信絶対値の５ビット絶対値表現での第５のビットなどの最下位ビットは脱落する、すなわちメッセージ絶対値が右側へ１だけシフトされる、すなわち同じ意味であるが２で除算される、という点を除いて、制約ノード領域への変換はｌｏｇ２間隔の場合のように進行する。最下位ビットが１である場合、同じ処理が実行されるが、変換時に用いる定数Ｃは異なるものとなる。このような場合、定数Ｃは、ＣとＣ／２の間のわずかに小さな値で置き換えられる。制約ノード処理は、処理中のメッセージの絶対値部分の残りビットを用いて前と同じように逆方向変換ポイントまで進行する。
【００８９】
図１１は、１／２ｌｏｇ２間隔を使用するケースで、可変ノード領域形式の絶対値メッセージの一部１１０２を制約ノード領域形式へ変換する処理１１００を示す。ステップ１１０４に例示のように、例えばビット５のＬＳＢはメッセージの絶対値部分から分けられて、ステップ１１００へ出力されるのに対して、４上位ビットなどの残りビットはステップ１１０６へ出力される。ステップ１１００で、ＬＳＢは０と比較され、変換処理時に定数Ｃ用としてどの値を用いるべきかが判定される。ＬＳＢ＝０であれば、ステップ１１１３へ処理は進み、そこでＣは第１の値１１０００００００００００００にセットされる。これに対して、ＬＳＢ＝１であれば、処理はステップ１１００からステップ１１１４へ進み、Ｃは第２の値１００００１０００００００００にセットされる。値Ｃは、ステップ１１１３または１１１４から、メッセージの絶対値部分１１０２の４ビットなどの残りの上位ビットを受信するステップ１１０６へ出力される。
【００９０】
ステップ１１０６で定数Ｃは、メッセージ絶対値の（４ビットなどの）残りビットの１０進値によって指定される数の場所だけ右側へシフトされ、このシフト演算の結果空いた左ビット位置に０が挿入される。次いで、ステップ１１０８で、制約ノード領域絶対値形式のメッセージ絶対値１１１０（１５ビット）が、例えば遅延素子８５１へ出力される。
【００９１】
１／２ｌｏｇ２のケースで、例えば制約ノード領域表現から可変ノード領域表現への逆方向変換には、出力メッセージの最下位ビットの検出に用いるｌｏｇ２間隔で存在する以上の追加ステップが含まれる。ｌｏｇ２間隔規則を用いて得られる値はメッセージ内のもう一方の、上位ビットを示す。
【００９２】
１／２ｌｏｇ２のケースでの最下位ビットの値を確定するために、制約ノード領域絶対値の第１の‘１’の右側のいくつかのビットがチェックされる。しきい値を用いて、最下位ビットが０になるか１になるかが判定される。１つの特定の１／２ｌｏｇ２実施形態では、制約ノード領域値ｖがしきい値ｔ２ｌ（ｖ）と比較される。但し、ｔはある適当な所定の定数である。ｖがｔ２ｌ（ｖ）よりも大きければ、ＬＳＢは０にセットされ、そうでなければ、ＬＳＢは１にセットされる。同じしきい値規則を用いる多くの代替実現例が存在することは理解できよう。
【００９３】
図１２は、制約ノード領域形式のメッセージの絶対値部分１２０２を可変ノード領域形式へ変換する処理１２００を示す。この処理はステップ１２０４から始まり、このステップで右側から測定した場合の、左側からの最初の“１”の位置が決定される。プライオリティエンコーダを用いてこの処理を実行してもよい。次いで、ステップ１２０６で、可変ノード領域内のメッセージ絶対値を表すのに用いるＬＳＢを除いて、特定されたビット位置が、ビット数により表すことが可能な最大数よりも大きいかどうかの決定が行われる。例えば、５ビットを用いて可変ノード領域内の絶対値を表すと仮定すると、ＬＳＢ＝４ビット用の５ビット−１を使用して１０進最大値１５を表すことが可能となる。このような場合、ステップ１２０６で、特定されたビット位置が最大数１５を上回るか否かに関する判定が行われる。答えがイエスならば、処理はステップ１２０８へ進む。そうでなければ処理はステップ１２１２へ進む。
【００９４】
メッセージ絶対値を０にセットすべきであるという判定の結果、処理はステップ１２０８へ進む。ステップ１２０８で、可変ノード領域メッセージ絶対値表現のすべてのビットが０にセットされ、（０００００などの）メッセージ絶対値が可変ノード領域形式で形成される。この変換が終了すると、処理はステップ１２０８からステップ１２１４へ進む。
【００９５】
ステップ１２０８に代わる別の処理経路を表すステップ１２１０で、可変ノード領域形式のメッセージ絶対値の非ＬＳＢビットの数により表すことが可能な最大値から、上記特定された数、すなわちビット位置の数が減算される。例えば、可変ノード領域形式の５ビット絶対値表現を仮定すると、ＬＳＢに４ビットが加算される。４ビットにより表すことが可能な最大の数は１５である。したがって、ステップ１２１０で示すような実施形態では、特定されたビット位置の数が１５から減算されて、可変ノード領域内に４上位ビットの絶対値が形成されることになる。
【００９６】
ステップ１２１２で、メッセージ絶対値の制約ノード領域表現１２０２の絶対値に存在する一番左側の“１”の右側に、ＬＳＢ、例えば５ビットの例示絶対値の第５ビットが１以上のビット値から確定される。
【００９７】
ステップ１２１４で、可変ノード形式になっている、例えば５ビットの形成済みのメッセージ絶対値１２１６が単位遅延素子８９７などへ出力される。
【００９８】
図７と図８は、図１３を参照してさらに説明しようとする基本的構造の１例と２例をそれぞれ含むものである。メッセージ更新のための主計算が単純化された下式の形を持つことを想起されたい：
2005506733.tif 000017
さらに、クロックサイクル当たり１つの出力エッジメッセージの形成が可能な効率的なパイプライン構造を備えることが望ましい。本発明のハードウェア設計には、以下の観察に対する相応の配慮が払われ、以下に列挙する特徴がサポートされている：
入出力データ間に明白な依存状態が存在しないため、パイプラインを十分に深くして非常に高いクロックレートをサポートすることが可能となる。
【００９９】
可変レベルのノードを処理しながら、パイプラインはその効率を維持することができる。
【０１００】
上式の加算と減算は、逆演算が行われる演算である、対応する法（モジュロ加算／減算、乗算／除算など）に従う任意の演算に対して一般化することができる。
【０１０１】
上記パイプラインは、関数変換、飽和、遅延素子などの追加の前処理段と後処理段とを備えてもよい。
【０１０２】
一般化して提案したパイプライン構造を表すメッセージ処理システム１３００が図１３に例示されている。処理システム１３００では、様々なシステム構成要素の駆動に用いるエッジクロック信号によって定められるように、クロックサイクル当たり１メッセージずつ入力メッセージ“Ａ”が順に受信される。処理システム１３００は、ノードクロック信号とノードレベル信号の受信も行う。ノードクロック信号はノードフレーム作成用信号として役立つものであり、新たなノードに対応するメッセージが累算器モジュール１３０２のメッセージ入力部へ出力されると、ノードクロック信号はオンにセットされる。後述するように、ノードクロック信号は、メッセージのランニングサムの初期化と、個々のノード用として形成されたトータルサムのラッチングとを含む様々な処理の制御に利用される。処理の実行対象ノードに対応する、メッセージ数などのレベルの関数としてノードクロック信号は生成される。ノードレベル信号は、処理が行われている対象ノードのレベルを示すための、当該ノードに対応するメッセージの数を示す信号である。後述するように、このノードレベル信号は可変遅延素子１３０６を制御するのに用いられ、可変遅延素子１３０６は受信メッセージを遅延するのに用いられる。図１４に図示の対応するデータフローを参照しながら、システム１３００の処理について以下さらに解説する。説明を簡略にするために、前処理段と後処理段はいずれもスキップし、簡単な加減算演算を仮定する。
【０１０３】
処理システム１３００には、モジュールと呼ばれることもある２つの計算段、すなわちアキュミュレーションモジュール“Ａ”１３０２と減算モジュール“Ｓ”１３０４が含まれる。減算モジュールは出力メッセージを形成するので、メッセージ形成モジュールと呼ぶこともある。システム１３００には、遅延メッセージ“Ｄ”を出力する可変遅延素子１３０６を備えた可変メッセージ遅延経路も含まれる。
【０１０４】
アキュミュレーションモジュール“Ａ”１３０２は順番に入力メッセージを受信し、ノードに対応する個々のセットのメッセージに対してトータルサムを形成する。アキュミュレーションモジュール１３０２は、加算器１３１０と、単位遅延素子１３１２と、ｍｕｘ１３１４と、ノードサムラッチ１３１６とを具備する。単位遅延素子１３１２を用いて、加算器１３１０が生成したランニングサムが記憶される。ＭＵＸ１３１４は、加算器１３１０の入力部のうちの一方の入力部へ、遅延素子１３１２が出力した０かランニングサムのいずれかを出力する。上記ＭＵＸは、ノードクロック信号によって制御され、ノードに対応する第１のメッセージが加算器１３１０の他方の入力部へ出力されると０を出力し、その他のすべての場合、ランニングサムＢを出力する。このようにして、加算器は、ノードに対応する受信メッセージを加算して、当該ノードのトータルサムを形成することになる。
【０１０５】
ノードクロック信号は、ノードサムラッチ１３１６の中へランニングサムをストローブするために用いられる。ノードクロック信号がオンにセットされ、値がラッチされた時点で、ランニングサムは当該ノードのトータルサムを表す。
【０１０６】
減算モジュールすなわちメッセージ形成モジュール“Ｓ”１３０４は、その入力として、アキュミュレーションモジュール１３０２が生成したトータルサムと、可変遅延素子１３０６が遅延させた入力メッセージとを受信する。“Ｓ”１３０４段は、ノードサムラッチ１３１６に記憶されたトータルサム“Ｃ”から遅延入力メッセージを順次減算し、ノードＮなどのノードに対してクロックサイクル当たり１メッセージずつ出力メッセージを形成する。この減算演算の結果、段“Ａ”１３０２の処理による出力に先行して、出力メッセージ“Ｅ”が出力レジスタ１３２１に記憶され、“Ｓ”１３０４を完全に重ね合わせたり、折り畳む（folded）ことが可能となる。例えば、段“Ａ”１３０２がノードＮ＋１に対する処理を実行している間、段“Ｓ”はノードＮに対する処理を実行することができる。
【０１０７】
遅延素子１３０６を備えた可変遅延ラインの目的は、ノードＮ＋１用の入力メッセージを記憶しながら、ノードＮ用の、“Ｄ”として表される遅延された原入力メッセージを減算段“Ｓ”へ出力することである。処理用クロックサイクルの装置では、ノードに対応するメッセージに印加される遅延素子１３０８の遅延は、上記メッセージが対応する現在のノードレベルに等しい。例えば、レベル４のノードに対応するメッセージは、可変遅延素子１３０６によって４クロックサイクルだけ遅延され、レベル２のノードに対応するメッセージは２クロックサイクルだけ遅延されることになる。マルチノードレベルをサポートするために、１つの実施形態では、可変遅延素子１３０６が実装され、この可変遅延素子には、サポートされている最大のノードレベルと同数のメッセージを記憶できる少なくとも十分な記憶空間が設けられる。
【０１０８】
可変遅延素子１３０６と遅延メッセージＤとを利用することにより、折り返し（folded）パイプライン処理に必要な二重の読み出しを除くことによってメッセージメモリの帯域幅が節減される。遅延素子１３０６を備えた遅延ラインには、外部遅延値制御装置（可変出力タップを備えたシフトレジスタなど）か、内部遅延値制御装置（組み込み型ＦＩＦＯなど）かのいずれかを実際には設けることが可能であることに留意されたい。遅延制御論理は多重処理用ノードの両端での共有が可能なため、第１の方法の方がベクトルデコーダ用として望ましい場合がある。
【０１０９】
ノードフレーム作成用信号に利用するノードクロック信号の周波数変更処理と、遅延素子１３０６により課せられるメッセージ遅延の制御に用いるレベル信号の変更処理の双方を行うことにより、上述のパイプライン構造によってリアルタイムでのノードレベルの変更が可能となる。これらの制御信号を介して、パイプライン深さを簡単に変更することが可能となる。この文脈では、パイプライン深さとは、（ノードＮ用の）第１の着信メッセージがシステム１３００の中へ処理用として送出された時点から、（ノードＮ用の）第１の出力メッセージＥがパイプライン出力部に出現する時点までの遅延と解釈することができる。可変の深さをもつパイプラインは、非正則ＬＤＰＣ符号をサポートすることができる著しいパフォーマンス上の利点を提供することが可能である。なぜなら、１反復当たりで必要なサイクル総数は、グラフ内のエッジ数にレベル拡散度（最大レベルと最小レベル間の差）をプラスしたものに等しいからである。
【０１１０】
これに対し、固定されたパイプライン設計は、１反復当たり（最大エッジレベル）＊（ノード数）回のサイクルを必要とし、このサイクルは特に、レベル拡散度が大きい場合、エッジ数よりも際だって大きなものになる場合がある。
【０１１１】
図１４は、ノードレベル３からノードレベル４への切り替えを行う時点でシステム１３００に存在するＡからＤまでの様々な値の１例を含むチャート１４００を示す図である。ノードレベルの切り替えに起因して、入力データの着信と関連する遅延などのパイプラインの機能停止が生じないことに留意されたい。
【０１１２】
図１４は、ノード１（ｎ１）、ノード２（ｎ２）、ノード３（ｎ３）、ノード４（ｎ４）からなる４個のノードに対応するメッセージと関連する処理を示す。単一ラインを含む図１４のチャート内のセルはｎ１に対応する。２本のラインを含むセルはｎ２に対応する。３本のラインを含むセルはｎ３に対応する。さらに、４本のラインを含むセルはｎ４に対応する。第１列１４０１に例示のように、ノードｎ１とｎ２とはレベル３であるが、ノードｎ３とｎ４とはレベル４である。チャート１４００内の各行が異なるクロックサイクルに対応するのに対して、図示のように列は異なる値に対応している。
【０１１３】
第２列１４０２は、クロックサイクル当たり１メッセージずつ受信した順序で受信メッセージＡをリストしたものである。第３の列１４０４は、個々の処理クロックサイクル中のランニングサムＢをリストしたものである。列１４０４では、列１４０４内のメッセージｎ１_ｅ０から出るｎ１などのノードインジケータが、簡潔さを旨として省かれていることに留意されたい。第４の列１４０６は、メッセージ処理の一部として個々のノードに対して生成されたラッチ済みのトータルサムＣをリストしたものである。第５の列１４０８は、遅延素子１３０６が出力した遅延値Ｄをリストしたものである。上記遅延値Ｄは列Ｃにおけるサムから減算され、出力メッセージＥが形成される。上記形成済み出力メッセージは第６の列１４１０にリストされている。
【０１１４】
当然のことであるが、パイプライン深さの変更に起因して、出力側データストリームに空のスロットが生じることになる。ノードが（昇順または降順で）レベルによってソートされている場合、１反復当たりの空のスロットの総数はレベル拡散度に等しく、処理済みのメッセージ数と比較して非常に少なくなる。その結果非常に高度のパイプラインの利用が可能となる。
【０１１５】
上記記載のＬＤＰＣ復号化方法とノードプロセッサ実施構成とによって、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）などの様々なハードウェアプラットフォームや、特定用途向け集積回路（ＡＳＩＣ）におけるＬＤＰＣ復号化の実行が可能になる。本発明は、単純な並行性と、実現し易いノードとが明らかに利用できる上記設定で特に有用である。
【０１１６】
本発明の復号化方法および復号化装置の多くの追加変形例は、本発明に関する上記記載に照らして当業者には明白である。このような変形例は本発明の範囲に属するものと考えるべきである。
【図面の簡単な説明】
【０１１７】
【図１】長さ１０の例示の正則ＬＤＰＣ符号の２部分グラフ表示を示す。
【図２】図１にグラフィックに示した符号の行列表現である。
【図３】データの符号化、送信、復号化を示す。
【図４】例示の非正則ＬＤＰＣ符号の２部分グラフ表示である。
【図５】図５ａ〜５ｄの組み合わせを含み、図４に示すＬＤＰＣ符号に基づくＬＤＰＣ復号化処理の一部として実行されるステップを示す。
【図６】本発明に基づいて実現したノードプロセッサを備えた直列ＬＤＰＣデコーダを示す。
【図７】可変ノードプロセッサの実施構成を示す。
【図８】制約ノードプロセッサの実施構成を示す。
【図９】制約ノード処理に対応する、それぞれ、第１の変換処理と第２の変換処理を示す。この場合、ｌｏｇ２量子化ステップサイズは５ビットメッセージで使用される。
【図１０】制約ノード処理に対応する、それぞれ、第１の変換処理と第２の変換処理を示す。この場合、ｌｏｇ２量子化ステップサイズは５ビットメッセージで使用される。
【図１１】制約ノード処理に対応する、それぞれ、第１の変換処理と第２の変換処理とを示す。この場合１/２ｌｏｇ２量子化ステップサイズは６ビットメッセージで使用される。
【図１２】制約ノード処理に対応する、それぞれ、第１の変換処理と第２の変換処理とを示す。この場合１/２ｌｏｇ２量子化ステップサイズは６ビットメッセージで使用される。
【図１３】メッセージ受け渡し用デコーダで使用する、本発明に基づいて実現するノードプロセッサの一般的構造を示す。
【図１４】図１３に例示のノードプロセッサにより、異なるレベルのノードに対応するメッセージの処理中に順番に形成される様々なメッセージと値とを示す。
【図１５】受信機が検出した値から得られる量子化対数尤度値の形成に使用可能な装置を示す。
【符号の説明】
【０１１８】
１３００  処理システム
１３０２  累算器モジュール
１３０４  減算モジュール
１３０６  可変遅延素子
１３１０  加算器
１３１２  遅延素子
１３１４  ＭＵＸ
１３１６  ノードサムラッチ
１３２１  出力レジスタ
【図３】
2005506733.tif 000018
【図６】
2005506733.tif 000019
【図７】
2005506733.tif 000020
【図８】
2005506733.tif 000021
【図９】
2005506733.tif 000022
【図１０】
2005506733.tif 000023
【図１１】
2005506733.tif 000024
【図１２】
2005506733.tif 000025
【図１３】
2005506733.tif 000026
【図１４】
2005506733.tif 000027
【図１５】
2005506733.tif 000028
【国際公開パンフレット】
2005506733.tif 000029
2005506733.tif 000030
2005506733.tif 000031
2005506733.tif 000032
2005506733.tif 000033
2005506733.tif 000034
2005506733.tif 000035
2005506733.tif 000036
2005506733.tif 000037
2005506733.tif 000038
2005506733.tif 000039
2005506733.tif 000040
2005506733.tif 000041
2005506733.tif 000042
2005506733.tif 000043
2005506733.tif 000044
2005506733.tif 000045
2005506733.tif 000046
2005506733.tif 000047
2005506733.tif 000048
2005506733.tif 000049
2005506733.tif 000050
2005506733.tif 000051
2005506733.tif 000052
2005506733.tif 000053
2005506733.tif 000054
2005506733.tif 000055
2005506733.tif 000056
2005506733.tif 000057
2005506733.tif 000058
2005506733.tif 000059
2005506733.tif 000060
2005506733.tif 000061
2005506733.tif 000062
2005506733.tif 000063
2005506733.tif 000064
2005506733.tif 000065
2005506733.tif 000066
2005506733.tif 000067
2005506733.tif 000068
2005506733.tif 000069
2005506733.tif 000070
2005506733.tif 000071
2005506733.tif 000072
2005506733.tif 000073
2005506733.tif 000074
2005506733.tif 000075
2005506733.tif 000076
2005506733.tif 000077
2005506733.tif 000078
2005506733.tif 000079
2005506733.tif 000080
2005506733.tif 000081
2005506733.tif 000082
2005506733.tif 000083
【国際調査報告】
2005506733.tif 000084
2005506733.tif 000085
2005506733.tif 000086
2005506733.tif 000087