(57)【要約】低密度パリティ・チェック（ＬＤＰＣ）符号にも長い符号語にも使用するのに特に好適なメッセージ伝送復号技術を利用して、符号語（９０２）を復号する方法と装置が記載される。記載の方法によって、極めて小さいグラフ（１０００）の複数の同一のコピーから構成されたグラフ構造の復号が可能になる。より小さいグラフのコピーにはより大きいグラフ構造を作成するため、制御された置換動作（９０４）が行われる。同じ制御された置換は、小さいグラフの複製されたコピー間で伝送されるメッセージを支援するために直接実施される。グラフの個々のコピーに対応するメッセージはメモリ内に記憶され、ＳＩＭＤ読み出しまたは書き込み命令を使用して、グラフの各コピーから１つずつアクセスされる。グラフ置換命令は、例えば周期的置換動作を利用して、メッセージ・メモリ以外で反応するメッセージの各セット内にメッセージを単に並べ替えることによって実行できるので、小さいグラフの異なるコピーに対応してメッセージが処理回路に送られる。
2004531972.tif 000002
【特許請求の範囲】
【請求項１】
メッセージ伝送復号動作を行う装置において、
ＬセットのＺ個のＫ−ビット・メッセージを記憶するための記憶域のセットを含むメモリであって、Ｚは１よりも大きい正の整数であり、ＫおよびＬはゼロではない正の整数であるメモリと、
それぞれが制約ノード処理動作および可変ノード処理動作の少なくとも一方を実行する複数のノード処理ユニットを含むノード・プロセッサと、
メモリとノード処理ユニットとに結合され、Ｚ個のＫ−ビット・メッセージのセットを前記メモリと前記ノード・プロセッサ間で伝送し、スイッチ制御情報に応答してメッセージの前記セットの少なくとも１つ中のメッセージを並べ替えるためのスイッチング・デバイスとを備える装置。
【請求項２】
前記スイッチング・デバイスに結合され、メッセージの少なくとも１つの前記セット中のメッセージの並べ替えを制御するのに使用される前記スイッチ制御情報を作成するためのメッセージ配列制御モジュールを更に備える請求項１に記載の装置。
【請求項３】
スイッチング・デバイスはメッセージのセットに含まれるメッセージを並べ替えるためのメッセージ・ローテーション動作を実行する回路を含む請求項２に記載の装置。
【請求項４】
メッセージ配列制御モジュールは、メッセージのセットがメモリから読み出される順序に関する情報と、メモリから読み出されるメッセージの個々のセットで前記スイッチによってどのようなメッセージの並べ替えが行われるべきかを示す情報とを記憶する請求項２に記載の装置。
【請求項５】
メッセージ配列制御モジュールはさらに前記メモリに結合され、かつセット識別子を順次生成し、各々のセット識別子は単一の読み出し、または書込動作の一部としてメッセージのセットに対応する記憶域をアクセスするようにメモリを制御する請求項２に記載の装置。
【請求項６】
各々のセット識別子は単一のメモリ・アドレスである請求項５に記載の装置。
【請求項７】
前記複数のノード処理ユニットは並列に配列されたＺ個のノード処理ユニットを含み、Ｚ個のノード処理ユニットのそれぞれ１個は、前記メモリと前記ノード・プロセッサ間で送られるＺ個のメッセージのセットの各々のうちの異なるメッセージを処理するように並行して動作する請求項２に記載の装置。
【請求項８】
前記メモリはメッセージの各セットをユニットとしてアドレス指定できるようにすることによって、メッセージのセットを単一のＳＩＭＤ読み出し動作で前記メモリから読み出し可能にするアドレス入力を含む請求項７に記載の装置。
【請求項９】
前記メモリはメッセージの各セットをユニットとしてアドレス指定できるようにすることによってメッセージ・セットを単一のＳＩＭＤ書き込み動作で前記メモリへと書き込み可能にするアドレス入力を含む請求項７に記載の装置。
【請求項１０】
前記複数個のノード処理ユニットの各々は、ノード処理ユニットの動作を制約ノード処理動作モードと、可変ノード処理動作モード間で切り換えるための制御信号を受信する制御信号入力を含む請求項１に記載の装置。
【請求項１１】
前記複数個のノード処理ユニットに結合され、前記複数個のノード処理ユニットを制御するために使用される前記制御信号を生成する復号器制御デバイスを更に備える請求項１０に記載の装置。
【請求項１２】
Ｚ個の処理ユニットの各々は、前記スイッチング・デバイスから受信した少なくとも１つのメッセージから少なくとも１つの新規メッセージを作成するための可変ノードの低密度パリティ・チェック・メッセージ処理動作を実行する請求項１１に記載の装置。
【請求項１３】
複数個のノード処理ユニットの少なくとも１つは、複数の逐次的な可変ノード処理動作の各々で使用される複数のメッセージを示す情報を含む請求項１０に記載の装置。
【請求項１４】
復号器制御デバイスはさらに前記メッセージ送信制御デバイスに結合され、
該メッセージ送信制御デバイスは、可変ノード処理動作モード中と、制約ノード処理動作モード中とでは異なる、ＬセットのＺ個のメッセージの各々がメモリから読み出される順序を指定する請求項７に記載の装置。
【請求項１５】
メッセージ配列モジュールに結合された復号器制御モジュールを更に備え、該復号器制御モジュールはＬセットのＺ個のメッセージの各々が前記メモリから読み出される順序を制御するために使用される情報をメッセージ配列モジュールに供給する手段を含む請求項２に記載の装置。
【請求項１６】
前記復号器制御デバイスは更に、前記メモリに供給されたセット識別子の生成を制御するエッジ・インデックスをメッセージ配列モジュールに供給する手段を含む請求項１５に記載の装置。
【請求項１７】
ノード度情報のセットを記憶し、ノード・プロセッサに結合されたノード度メモリを更に備える請求項１６に記載の装置。
【請求項１８】
制御デバイスは更に、記憶されたノード度情報のセットのうちのどのノード度情報が任意の所定の時点でノード・プロセッサに供給されるかを判定するために使用されるノード索引を生成する請求項１７に記載の装置。
【請求項１９】
前記メモリに結合され、制約ノード処理動作と、可変ノード処理動作の少なくとも一方を実行するための第２の複数個のノード処理ユニットを含む第２のノード・プロセッサを更に備える請求項１に記載の装置。
【請求項２０】
前記ノード・プロセッサを前記第２のノード・プロセッサに結合し、ＬセットのＺ個のＫビット・メッセージを記憶するための付加的な記憶域のセットを含む付加的なメモリを更に備える請求項１９に記載の装置。
【請求項２１】
前記ノード・プロセッサを前記付加的なメモリに結合し、Ｚ個のＫビット・メッセージのセットを前記ノード・プロセッサと前記付加的なメモリとの間で伝送し、かつ第２のスイッチによって伝送された少なくとも１つのメッセージのセット中の前記メッセージを並べ替えるための第２のスイッチング・デバイスを更に備える請求項２０に記載の装置。
【請求項２２】
前記ノード・プロセッサは可変ノード復号器のパリティ・チェック処理動作を実行するための可変ノード・プロセッサであり、
前記付加的なノード・プロセッサは制約ノードのパリティ・チェックの復号器処理動作を実行するための制約ノード・プロセッサである請求項２１に記載の装置。
【請求項２３】
前記付加的なノード・プロセッサに結合され、それに含まれる第２の複数の処理ユニットの各々の出力から、パリティ・チェック復号動作が成功裏に完了した時点を判定するためのパリティ・チェック確認装置を更に備える請求項２１に記載の装置。
【請求項２４】
メッセージ伝送復号動作を行う装置において、
ＬセットのＺ個のＫ−ビット・メッセージを記憶するための第１の記憶域セットを含む第１のメモリであって、ＬおよびＺは１よりも大きい正の整数であり、Ｋはゼロではない正の整数である第１のメモリと、
第１の複数のノード処理ユニットとを含む第１のノード・プロセッサであって、各ノード処理ユニットは第１のノード・プロセッサに供給されるＺ個のＫビット・メッセージの各セット中の少なくとも１個のＫビット・メッセージを受信するためのものとする該第１のノード・プロセッサと、
前記第１のメモリを第１のノード・プロセッサに結合し、メッセージのセットを前記第１のノード・プロセッサと前記第１のメモリとの間で伝送し、かつ第１のスイッチによって伝送された少なくとも幾つかのメッセージのセット中の前記メッセージを並べ替えるための前記第１のスイッチング・デバイスとを備える装置。
【請求項２５】
前記第１のノード・プロセッサに結合され、ＬセットのＺ個のＫビット・メッセージを記憶するための第２の記憶域セットを含む第２のメモリと、
前記第２のメモリと前記第１のメモリとに結合され、第２の複数個のノード処理ユニットを含む第２のノード・プロセッサとを更に備える請求項２４に記載の装置。
【請求項２６】
前記付加的なメモリを第２のノード・プロセッサに結合し、Ｚ個のＫビット・メッセージのセットを前記付加的なメモリ・デバイスから受信し、かつ受信されたＺ個のメッセージの各セット中の１つのメッセージを前記第２の複数のノード処理ユニットの１つに供給するための付加的なスイッチング・デバイスを更に備える請求項２５に記載の装置。
【請求項２７】
第１のノード・プロセッサは可変ノード・プロセッサであり、
前記装置はさらに前記第１のノード・プロセッサに含まれる前記複数個の処理ユニットに結合され、且つ前記第１の複数個のノード処理ユニットの各々の出力から復号動作が成功裏に完了した時点を判定する手段を備える請求項２４に記載の装置。
【請求項２８】
メッセージ伝送復号処理を行う方法において、
ＬセットのＫ−ビット・メッセージをメモリに記憶するステップであって、各セットのＫビット・メッセージは１からＺまでのメッセージを含み、ＬおよびＺは１よりも大きい正の整数であり、Ｋはゼロではない正の整数であるステップと、
メモリから前記Ｋビット・メッセージのセットの１つを読み出すステップと、
前記読み出されたＫビット・メッセージのセットでメッセージ並べ替え動作を行って、並べ替えられたＺ個のＫビット・メッセージのセットを作成するステップと、
並行して、並べ替えられたメッセージのセット中のＺ個のメッセージをベクトル・プロセッサに供給するステップと、
Ｚ個の供給されたメッセージを入力として用いて、メッセージ伝送復号動作を実行するようにベクトル・プロセッサを作動させるステップと、を含む方法。
【請求項２９】
前記メッセージ伝送復号動作は、供給された並べ替えられたメッセージのセット中のＺ個のメッセージからＺ個の復号器メッセージのセットを生成する請求項２６に記載の方法。
【請求項３０】
Ｚ個の復号器メッセージを生成するためにベクトル・プロセッサを作動させるステップは、
並行してＺ回のノード処理動作を実行するステップを含む請求項２９に記載の方法。
【請求項３１】
Ｚ回のノード処理動作の各々は制約ノード処理動作と可変ノード処理動作の一方である請求項３０に記載の方法。
【請求項３２】
メモリから読み出されるべきＺ個のメッセージのセットを示すメッセージ・セット識別子を生成するステップをさらに含む請求項２８に記載の方法。
【請求項３３】
前記Ｋビット・メッセージのセットの１つを読み出すステップが、
メモリから読み出されるべきメッセージのセットを示す前記メッセージ・セット識別子を利用してＳＩＭＤ読み出し動作を実行するステップを含む請求項３２に記載の方法。
【請求項３４】
第２のメッセージ並べ替え動作を実行し、該第２のメッセージ並べ替え動作は、生成された復号器メッセージの並べ替えられたセットを生成するために、生成されたＺ個の復号器メッセージのセットで実行されるステップを更に含む請求項２８に記載の方法。
【請求項３５】
生成された復号器メッセージの並べ替えられたセットを前記メモリに記憶するステップを更に含む請求項３４に記載の方法。
【請求項３６】
生成された復号器メッセージの並べ替えられたセットを記憶するステップは、前記生成された復号器メッセージの並べ替えられたセットをメモリへと書き込むためのＳＩＭＤ書き込み動作を実行することを含む請求項３５に記載の方法。
【請求項３７】
第２のメッセージ並べ替え動作を実行するステップは、メモリから読み出された前記Ｋビット・メッセージのセットで実行されたメッセージ並べ替え動作の逆動作を実行することを含む請求項３４に記載の方法。
【請求項３８】
記憶されたメッセージ・セット置換情報にアクセスするステップを更に含むと共に、
メッセージ並べ替え動作を実行するステップは、
アクセスされ記憶されたメッセージ・セット置換情報の機能として前記並べ替えを実行するステップを含む請求項２８に記載の方法。
【請求項３９】
前記メッセージ・セット置換情報は周期的ローテーション情報を含む請求項３７に記載の方法。
【請求項４０】
前記メッセージ伝送復号動作は可変ノード処理動作であり、各々の可変ノード処理動作は決定値の生成を含み、
前記方法は復号条件が満たされたか否かを判定するためにベクトル・プロセッサを動作させることによって生成された決定値を検査するステップを更に含む請求項２８に記載の方法。
【請求項４１】
メッセージ伝送復号処理を行う方法において、
Ｚ個のＫビット・メッセージのセットを生成するためにノード・ベクトル・プロセッサを作動させるステップであって、ＬおよびＺは１よりも大きい正の整数であり、Ｋはゼロではない正の整数であるステップと、
Ｚ個のＫビット・メッセージの並べ替えられたセットを生成するために、生成されたＺ個のＫビット・メッセージのセットでメッセージ並べ替え動作を実行するステップと、
Ｚ個のＫビット・メッセージの並べ替えられたセットをメモリ・デバイスに記憶するために単一の書き込み動作を実行するステップと、を含む方法。
【請求項４２】
単一の書き込み動作を実行するステップは、メッセージの並べ替えられたセット中のＺ個のメッセージを並行してメモリに書き込むＳＩＭＤ書き込み動作を実行することを含む請求項４１に記載の方法。
【請求項４３】
Ｚ個のＫビット・メッセージのセットを生成するためにノード・ベクトル・プロセッサを作動させるステップは、
並行してＺ個のノード処理動作を実行するステップを含み、各ノード処理動作は前記Ｚ個のＫビット・メッセージのセット中の１つのメッセージを生成する請求項４１に記載の方法。
【請求項４４】
Ｚ個のノード処理動作は可変ノード処理動作である請求項４３に記載の方法。
【請求項４５】
Ｚ個のノード処理動作は制約ノード処理動作である請求項４３に記載の方法。
【請求項４６】
Ｚ個のＫビット・メッセージの生成されたセットでのメッセージ並べ替え動作の実行には、
メッセージのセット中のメッセージを並べ替えるスイッチング動作を実行することによってＺ個のＫビット・メッセージのセット中のメッセージを循環させるステップを含む請求項４３に記載の方法。
【請求項４７】
低密度のパリティ・チェック復号動作を行う方法において、
記憶されたメッセージのセットを読み出すためにＳＩＭＤ読み出し動作を行うステップと、
メッセージの記憶されたセットでメッセージ並べ替え動作を行うステップと、
並列に配列された複数個のノード処理ユニットを含むノード・プロセッサに、メッセージの並べ替えられたセットを供給するステップと、
メッセージの供給され並べ替えられたセットの機能として、更新されたメッセージのセットを生成するために複数個のノード処理ユニットを作動させるステップと、を含む方法。
【請求項４８】
前記更新されたメッセージのセット中の更新されたメッセージを、ＳＩＭＤ書き込み動作を用いてメモリ・デバイスへと書き込むステップを更に含む請求項４７に記載の方法。
【請求項４９】
更新されたメッセージをメモリ・デバイスへと書き込む前に、前記更新されたメッセージのセット中の更新されたメッセージでメッセージ並べ替え動作を行うステップを更に含む請求項４８に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は２００１年６月１５日出願の米国仮出願Ｓ．Ｎ．６０／２９８，４８０号の利益を主張するものである。
【０００２】
本発明は例えば低密度パリティ・チェック（ＬＤＰＣ）符号のようなパリティ・チェック符号を利用して、バイナリ・データ内のエラーを検出および／または修正するための方法と装置を目的とするものである。
【背景技術】
【０００３】
最近の情報化時代では、例えばビデオ、オーディオ、統計情報等のような様々な種類の情報を表し、かつ通信するために例えば１と０のような２進値が用いられる。残念なことに、バイナリ・データの記憶、送信、および／または処理中に不慮のエラーが生ずることがあり、例えば１が０に、またはその逆に変化することがある。
【０００４】
一般に、データ伝送の場合に、受信側はノイズまたは歪みがある状態で受信された各ビットを観察し、ビット値の表示だけしか得られない。このような環境では、観察された値は“ソフト”ビットのソースであると解釈される。ソフト・ビットはビット値の好適な推定、すなわち１または０をその推定値の信頼性のある程度の指示と共に示す。エラー数が比較的少くても、少数のエラーまたは歪みレベルによってもデータが使用不能となることがあり、または伝送エラーの場合はデータの再伝送が必要になることがある。
【０００５】
エラーをチェックし、また場合によってはエラーを修正するメカニズムを備えるために、綿密に設計した冗長性を採り入れてバイナリ・データを符号化することができる。データのユニットを符号化すると、一般に符号語と呼ばれるものが生成される。符号語はその冗長性により、符号語がそこから生成され入力したデータのユニット以上のビットを含む場合がよくある。
【０００６】
伝送された符号語から生じた信号が受信され、または処理された場合、オリジナルのデータ・ユニットを復元するため、受信された信号のエラーを識別し、かつ／または修正し、またはその信号から歪みを除去するのに信号内に見られる符号語内に含まれる冗長性の情報を利用することができる。このようなエラーのチェックおよび／または修正は復号プロセスの一部として実施することができる。エラーが存在しない場合、または修正可能なエラーまたは歪みの場合、復号を利用して、処理中のソース・データから符号化されたオリジナルのデータ・ユニットを復元することができる。復元不可能なエラーである場合は、復号プロセスは、オリジナルのデータを完全には復元できない旨のある種の表示を生成することがある。このような復号不良の表示を利用してデータの再伝送を開始することができる。
【０００７】
データの冗長性は、記憶されまたは伝送されるデータの信頼性を高めることができる一方で、記憶スペース、および／または貴重な通信帯域幅の利用という代償を要する。したがって、効率的に冗長性を加え、データ内に誘導される冗長性が所定量である場合、得られるエラーの修正／検出の能力の量を最大限にすることが望まれる。
【０００８】
データ通信用に光ファイバー回線の使用が増大し、一方でデータが例えばディスク・ドライブ、テープ等のようなデータ記憶デバイスから読み出され、またはこれに書き込むことができる速度が高まると共に、データ記憶および伝送能力を効率的に利用するだけではなく、高速度でデータを符号化および復号する能力を高める必要性が高まっている。
【０００９】
符号化の効率と高速のデータ伝送速度が重要である一方で、例えば消費者デバイスのような広範なデバイスで使用するのに実際的な符号化システムおよび／または復号システムにとっては、エンコーダおよび／または復号器を適正なコストで実施できることが重要である。したがって、例えばハードウェアのコストの点で、エラーの修正および／または検出の目的で利用される符号化／復号方式を効率的に実施できる能力が重要であることがある。
【００１０】
エラー修正の目的で長年にわたって様々な種類の符号化方式が採用されてきた。一般に“ターボ符号”と呼ばれるある種の符号は最近になって発明されたものである（１９９３年）。ターボ符号には畳み込み符号のような旧来の符号化技術よりも顕著な利点があり、多くの用途を見いだしている。
【００１１】
ターボ符号の出現に関連して、一般に低密度パリティ・チェック（ＬＤＰＣ）符号と呼ばれる別の種類の関連する、明らかに簡単な符号への関心が高まって来ている。ＬＤＰＣ符号は実際には約４０年前（１９６１年）に発明されたものであるが、前面に出てきたのは最近になってからである。ターボ符号およびＬＤＰＣ符号は、いわゆる反復型の符号化システムの文脈で用いられる符号化方式であり、すなわちこれらは反復型復号器を用いて復号される。最近になって、ＬＤＰＣ符号はＬＤＰＣ符号化パラメータが適正に選択されれば、例えば約１０００ビットを超える符号語サイズのような大きい符号語のターボ符号を凌ぐ、またはこれと匹敵するような極めて優れたエラーの検出および修正性能を提供できることが判明している。その上、ＬＤＰＣ符号は潜在的にはターボ符号よりも大幅に高い速度で復号できる可能性がある。
【００１２】
多くの符号化方式では、エラーの検出および修正の目的には、より長い符号語の方が符号化の相互作用がより多数のビットに及ぶので、より弾力的である場合が多い。このように、長い符号語を使用することが、エラーを検出し修正する能力を高めるために有利であることがある。このことはターボ符号およびＬＤＰＣ符号について特に当てはまる。したがって、多くの用途では例えば長さが１０００ビットを超える符号語のような長い符号語を使用することが望ましい。
【００１３】
そのような符号を使用することで最も期待がもてる長い符号語という背景で、ＬＰＤＣ符号化およびターボ符号化を採用する際に直面する困難さは、主にこれらの符号化システムを実施する複雑さである。実際的な意味では、複雑さはじかに実施のコストにつながる。これらの符号化システムは双方とも、畳み込み符号およびリードソロモン符号のような従来から使用されている符号化システムよりも大幅に複雑である。
【００１４】
信号処理アルゴリズムの複雑さの分析では通常は動作のカウントに焦点が当たる。反復型符号化システムで、特にＬＤＰＣ符号の場合にハードウェアの並列処理を利用しようと試みると、著しい複雑さは計算上の必要性からではなく、ルーティングの必要性から生ずる。問題の根は符号自体の構造にある。
【００１５】
ＬＤＰＣ符号およびターボ符号は反復型プロセス内でのメッセージのインターリービングに依拠している。符号が良好に機能するには、このインターリービングは良好なミキシング・プロパティを有していなければならない。それによって複雑なインターリービング・プロセスを実施する必要が生ずる。
【００１６】
ＬＤＰＣ符号はタナー・グラフと呼ばれる場合が多い２部構成のグラフで良く表され、１セットのノード、すなわち可変ノードは符号語のビットに対応し、場合によってはチェック・ノードとも呼ばれる他のセットのノード、すなわち制約ノードが符号を定義するパリティ・チェック制約のセットに対応する。グラフ内のエッジは可変ノードを制約ノードに接続する。可変ノードと制約ノードとは、それらがグラフ内のエッジで接続されている場合は隣接と呼ばれる。簡略にするため、一般に一対のノードが最大１つのエッジで接続されるものと想定する。各々の可変ノードには１ビットの符号語が関連している。場合によっては、後述するようにこれらのビットの幾つかはパンクチュアドまたは既知の(punctured or known)ビットである場合がある。
【００１７】
可変ノード・シーケンスと一対一で関連するビット・シーケンスは、各々の制約ノードについて、（可変ノードとの関連を介して）制約ノードに隣接するビットの総和が０モジュロ２になる場合、すなわち偶数の１を備えている場合、そしてその場合に限り符号の符号語である。
【００１８】
ＬＤＰＣを復号するために使用される復号器および復号アルゴリズムは、グラフ内でエッジに沿ってメッセージを交換し、かつ着信メッセージに基づいてノードで計算を行い、これらのメッセージを更新することで動作する。このようなアルゴリズムは一般にメッセージ伝送アルゴリズムと呼ばれる。グラフ内の各々の可変ノードには受信値と呼ばれるソフト・ビットが最初に供給され、これは例えば通信チャネルからの観察によって判定された関連するビット値の推定値を示す。理想的には、別個のビットの推定値は統計的に独立している。このような理想は実際には侵害されることがあり、その場合が多い。受信された値の集積が受信語を構成する。このアプリケーションの目的で、例えば通信システム内の受信側によって観察された信号は受信語で識別されてもよい。
【００１９】
ノード、すなわち可変ノードまたは制約ノードに取付けられたエッジ数はノード度と呼ばれる。規則的なグラフまたは符号とは、全ての可変ノードが例えばｊのような同じエッジ数を有し、全ての制約ノードが例えばｋのような同じエッジ数を有するグラフまたは符号のことである。この場合は、符号は（ｊ，ｋ）規則的符号と呼ぶ。これらは元々は（１９６１年）ガラガー氏によって考察された符号であった。“規則的”符号とは対称的に、不規則符号は異なる度合いの制約符号および／または可変符号を有している。例えば、ある種の可変ノードの度合いは４であり、他の可変ノードは３であり、更に他の可変ノードは２である。
【００２０】
不規則な符号は表示し、および／または実現するのがより複雑である場合があるものの、不規則な符号は、規則的な符号と比較すると優れたエラーの修正／検知性能をもたらすことができることが判明している。
【００２１】
復号プロセスをより正確に説明するため、ＬＤＰＣグラフ内のソケットという概念を導入する。ソケットとはグラフ内のエッジとグラフ内のノードとの関連性であると見なすことができる。各々のノードには各エッジごとに１つのソケットが取付けられ、エッジがソケット“へと差し込まれる”。このように、度合いｄのノードにはｄ個のソケットが取付けられている。グラフがＬ個のエッジを有している場合は、グラフの可変ノード側には可変ソケットと呼ばれるＬ個のソケットがあり、グラフの制約ノード側には制約ソケットと呼ばれるＬ個のソケットがある。識別と配列の目的で、可変ソケットは１，．．．，Ｌと列挙できるので、１つの可変ノードに取付けられた可変ソケットは全て連続して現れる。このような場合、最初の３つの可変ノードがそれぞれｄ１、ｄ２、ｄ３の度合いを有している場合には、最初の可変ノードに可変ソケット１，．．．，ｄ１が取り付けられ、２番目の可変ノードに可変ソケットｄ１＋１，．．．，ｄ１＋ｄ２が取り付けられ、３番目の可変ノードに可変ソケットｄ１＋ｄ２＋１，．．．，ｄ１＋ｄ２＋ｄ３が取り付けられる。同様に、制約ソケットは１，．．．，Ｌと列挙でき、１つの制約ノードに取付けられた制約ソケットは全て連続して現れる。全てのエッジは一対のソケットであると見なすことができ、各対の１つはグラフの各々の側から現れる。このように、グラフのエッジは、例えば可変ノード側のようなグラフの一方の側から、例えば制約ノード側のような他方の側へのソケットのインターリーブ、または置換を表している。これらのシステムに関連する置換は前述のインターリービングの複雑さを反映して複雑である場合が多く、それらを実施するにはメッセージ伝送のための複雑なルーティングが必要となる。
【００２２】
グラフ上で実施されるメッセージ伝送アルゴリズムの概念はＬＤＰＣ復号よりも包括的である。全体図はグラフ内のエッジに沿ってメッセージを交換し、送信メッセージを作成するために着信メッセージに基づいて計算を行うノードを有するグラフである。
【００２３】
長さが１０で、レートが１／２の（３，６）規則的ＬＤＰＣ符号を決定する２部構成のグラフ１００の例が図１に示されている。長さ１０は、各々が１ビットの符号語Ｘ１−Ｘ１０で識別された（この場合はパンクチュアリングがない）、全体を参照符号１０２で表す１０個の可変ノードＶ１−Ｖ１０があることを示している。レート１／２は可変ノードの半分のチェック・ノード、すなわち参照符号１０６で表す５個のチェック・ノードＣ１−Ｃ５があることを示している。更にレート１／２は後述するように５つの制約が一次独立していることを示している。各々の線１０４は線が接続されているチェック・ノードと可変ノードとの間の例えば通信経路または接続のようなエッジを表している。各々のエッジは２つのソケット、すなわち１つは可変ソケット、１つは制約ソケットを識別する。エッジはそれらの可変ソケットまたは制約ソケットに応じて列挙されることができる。可変ソケットの列挙は、それらが可変ノードに接続されているポイントで可変ノード側に現れる際のエッジ配列（上部から下部へ）に対応している。制約ソケットの列挙は、それらが制約ノードに接続されているポイントで制約ノード側に現れる際のエッジ配列（上部から下部へ）に対応している。復号中、メッセージはエッジに沿って双方向に伝送される。このように、復号プロセスの一部として、メッセージはエッジに沿って制約ノードから可変ノードへと、またはその逆方向へと伝送される。
【００２４】
図１は長さ１０の符号に関連したグラフを示しているが、長さ１０００の符号語についてのグラフを表すのは１００倍複雑であることが理解されよう。
【００２５】
符号を表すためにグラフを利用することの代替案は、図２に示したようなマトリクス表示を利用することである。符号のマトリクス表示では、一般にパリティ・チェック・マトリクスと呼ばれるマトリクスＨ２０２が、関連するエッジ接続と、可変ノードおよび制約ノード情報とを含んでいる。マトリクスＨ内では、各列は可変ノードの１つに対応し、一方、各行は列のノードの１つに対応している。例示した符号には１０の可変ノードと５つの制約ノードがあるので、マトリクスＨは１０列と５行を含んでいる。特定の可変ノードと特定の制約ノードに対応するマトリクスのエントリは、エッジがグラフ内に存在する場合、すなわち２つのノードが隣接している場合は１に設定され、それ以外の場合は０に設定される。例えば、可変ノードＶ１はエッジによって制約ノードＣ１に接続されているので、マトリクス２０２の最上部の左コーナーに１が置かれる。しかし、可変ノードＶ４は制約ノードＣ１に接続されていないので、マトリクス２０２の最初の行の４番目の位置には０が置かれ、対応する可変ノードおよび制約ノードが接続されていないことを示す。Ｈの行がＧＦ〔２〕（第２次ガロア拡大体）にわたって一次独立したベクトルであるならば、制約は一次独立しているものと言える。可変であれ、制約であれソケットによってエッジを列挙することはＨ内で１を列挙することに対応する。可変ソケットの列挙は、マトリクス２０８に示すように、列内での上部から下部への列挙、および列から列へと左から右に進む列挙に対応している。制約ソケットの列挙はマトリクス２１０に示すように、行にわたって左から右への列挙、および行から行へと上部から下部に進む列挙に対応している。
【００２６】
マトリクス表示の場合、伝送されるべき符号語Ｘは処理される予定の符号語のビットＸ１−Ｘｎを含むベクトル２０６として表すことができる。ビット・シーケンスＸ１−Ｘｎは、マトリクス２０６と２０２の積が０に等しい場合、すなわちＨｘ＝０の場合に、またその場合に限り符号語となる。
【００２７】
ＬＤＰＣグラフに関連した符号語の検討という状況で、場合によっては符号語がパンクチュア状態になる場合があることが理解されよう。パンクチュアリングとは、符号語からビットを除去して、事実上より短い符号語を産出する動作である。ＬＤＰＣグラフの場合、このことはグラフ内の幾つかの可変ノードが実際には伝送されないビットに対応することを意味している。これらの可変ノードと、それらに関連するビットは状態変数と呼ばれることが多い。パンクチュアリングが利用される場合、復号器を用いて、通信チャネルを経て物理的に通信されない符号語の部分を再構成することができる。パンクチュアド符号語が伝送される場合は、受信デバイスは最初に、例えば任意の態様で１または０が割り当てられた欠けている受信された語の値（ビット）を、これらの値が完全に信頼できないことの表示、すなわちこれらの値は削除されることの表示（ソフト・ビット）と共にポピュレートしてよい。本発明を説明する目的で、使用される場合、これらの受信器−ポピュレートされた値は処理されるべき受信された語の一部であると見なすことにする。
【００２８】
例えば図３に示されているシステム３５０を検討してみる。システム３５０は符号器３５２、復号器３５７、および通信チャネル３５６を含んでいる。符号器３５２は入力データＡを処理して符号語Ｘを生成する符号化回路３５３を含んでいる。符号語Ｘは、エラーの検出および／または修正の目的で、ある程度の冗長性を含んでいる。符号語Ｘは通信チャネルを経て伝送されることができる。あるいは、符号語Ｘをある種のデータ選択技術によってデータ選択デバイス３５４を介して第１と第２の部分Ｘ’、Ｘ”に分割することができる。次に、第２の部分Ｘ”がパンクチュア状態にある一方で、例えば第１の部分Ｘ’のような符号語の１つを通信チャネルを経て復号器３５７を含む受信器に伝送してもよい。通信チャネル３５６により生成される歪みの結果、伝送された符号語の一部は損失され、または破損される場合がある。復号器の観点から見ると、パンクチュアド・ビットは損失されたものと解釈してよい。
【００２９】
受信器にてソフト・ビットが受信された語に挿入されて、損失されたビット、またはパンクチュア状態のビットの代わりになる。挿入されたビットはＸ”ソフト・ビットの削除の表示、および／または伝送中のビット損失を示す。
【００３０】
復号器３５７は受信された語Ｙおよび何らかの挿入されたソフト・ビットから完全な符号語Ｘを再構成し、次にデータ復号動作を行って再構成された符号語ＸからＡを生成することを試みる。
【００３１】
復号器３５７は受信された語Ｙから完全な符号語Ｘを再構成するためのチャネル復号器３５８を含んでいる。加えて、復号器は符号語に含まれている冗長性情報を除去して、再構成された符号語Ｘからオリジナルの入力データＡを生成するためのデータ復号器３５９を含んでいる。
【００３２】
ＬＤＰＣ符号化に関連して生成された受信された語を、例えばエラーの修正および検出動作のようなＬＤＰＣ復号動作を行うことによって処理し、オリジナルの符号語の再構成バージョンを作成できることが理解されよう。再構成された符号語は次にデータ復号されて、符号化されたオリジナル・データが復元される。データ復号プロセスは例えば、再構成された符号語からビットの特定のサブセットを単に選択することでよい。
【００３３】
ＬＤＰＣ復号動作は一般に、メッセージ伝送アルゴリズムを備えている。潜在的に有用なメッセージ伝送アルゴリズムは多数あり、このようなアルゴリズムの利用はＬＤＰＣ復号に限定されるものではない。本発明は事実上、このようなメッセージ伝送アルゴリズムのどの文脈にでも応用でき、したがって様々なメッセージ伝送システムで使用でき、ＬＤＰＣ復号器はその１例であるに過ぎない。
【００３４】
万全を期すため、確率伝搬法(belief propagation)として知られている、最もよく知られたメッセージ伝送アルゴリズムの１つの実現の１例を簡単に数学的に説明する。
【００３５】
（バイナリ）ＬＤＰＣ符号用についての確率伝搬法は下記のように表すことができる。グラフのエッジに沿って伝送されるメッセージは、可変ノードに関連するビットについて対数尤度log Ｐ０／Ｐ１として解釈される。ここで（Ｐ０、Ｐ１）は関連するビットでの条件付きの確率分布を表している。受信器によって復号器に供給されるソフト・ビットも対数尤度の形式で与えられる。このように、受信された値、すなわち受信された語の要素は、通信チャネルによって供給されるビットの観察で条件付けられた関連ビットの対数尤度である。一般に、メッセージｍは対数尤度ｍを表し、受信された値ｙは対数尤度ｙを表す。パンクチュアド・ビットの場合は、受信された値ｙは０に設定され、Ｐ0＝Ｐ1＝１／２を示す。
【００３６】
確率伝搬法のメッセージ伝送規則について検討してみる。メッセージはチェック・ノードから可変ノードへのメッセージであればｍｃ２ｖと表記され、可変ノードからチェック・ノードへのメッセージであればｍｖ２ｃと表記される。ｄ個のエッジを有する可変ノードについて検討する。各エッジｊ＝１，．．．，ｄについて、ｍｃ２ｖ（ｉ）がエッジｉ上の着信メッセージを示すものとする。復号プロセスのまさに最初のエッジについてｍｃ２ｖ＝０と設定する。次に、発信メッセージが下記によって与えられる。
【００３７】
2004531972.tif 000003
チェック・ノードでは‘正負符号’と大きさを利用してメッセージを表す方が便利である。このように、メッセージｍについてｍｐ∈ＧＦ〔２〕がメッセージの‘パリティ’を示すものとする。すなわち、ｍ≧０である場合はｍｐ＝０であり、ｍ＜０である場合はｍｐ＝１である。加えて、ｍｒ∈〔０、∞〕がｍの大きさを示すものとする。すなわち、ｍ＝−１ｍｐｍｒとなる。チェック・ノードでの更新はｍｐとｍｒでは別個である。度合いｄのチェック・ノードについて下記が得られる。
【００３８】
2004531972.tif 000004
但し、全ての加算はＧＦ〔２〕を介するものであり、また、
2004531972.tif 000005
但しＦ（ｘ）：＝log coth（ｘ／２）であるものと定義される。（上記の双方の方程式とも上付き文字ｖ２ｃはチェック・ノードにおける着信メッセージを示す）Ｆはそれ自体の逆数であるとする。すなわちＦ−１＝Ｆ（ｘ）である。
【００３９】
殆どのメッセージ伝送アルゴリズムは確率伝搬法の近似法であると見なすことができる。いずれかの実際のディジタル式実施形態では、メッセージは有限数のビットと、適宜に適応されたメッセージ更新規則とからなることが理解されよう。
【００４０】
大きい符号語についてＬＤＰＣ符号の表示に関する複雑さは、少なくとも並列処理を活用しようとするハードウェアの実施形態では手ごわいものであることが理解されよう。加えて、高速での処理をサポートできるようにメッセージの伝送を実施することが困難である場合もある。
【００４１】
ＬＤＰＣ符号の利用をより実際的なものにするため、大きい符号語に対応するＬＤＰＣ符号を効率的かつコンパクトに表す方法が必要である。そうすることによって、符号を表す、すなわち関連するグラフを記述するのに必要な情報量を低減する。加えて、例えば４つまたはそれ以上のノードまたはエッジのような複数のノードおよび複数のエッジに関連するメッセージの伝送を容易に制御できる方法で並行して実施できることによって、大きい符号語でも適正な時間量で効率的に復号できるような技術が必要とされる。さらに、幾つかの異なるＬＤＰＣ符号を復号するのに充分にフレキシブルな復号器アーキテクチャが必要である。その理由は、多くのアプリケーションが異なる長さと速度の符号を必要とするからである。さらに一層必要であるのは、特定のＬＤＰＣ符号の規格をプログラムできるようにするアーキテクチャである。
【発明の開示】
【発明を解決するための手段】
【００４２】
本発明はメッセージ伝送復号技術を利用して語に復号動作を実行する方法と装置に関するものである。本発明の技術は例えば長さが７５０ビット以上の符号語のような大きいＬＤＰＣ符号に使用するのに特に適しているが、より短い長さの符号にも利用できる。本発明の技術と装置は更に、他の種類のメッセージ伝送アルゴリズムが利用されるグラフ設計および復号にも利用できる。しかし本発明を説明する目的で、ＬＤＰＣ復号器および復号技術の例を説明する。
【００４３】
本発明の技術によって、全体のＬＤＰＣグラフの大部分がＺ倍小さいグラフの、例えばＺ個の複数のコピーから構成されているように見える、ある種の階層構造を有するＬＤＰＣグラフを復号することができる。Ｚ個のグラフ・コピーは同一のものでもよい。正確を期すためにより小さいグラフを投影されたグラフと呼ぶ。この技術は、同期的かつ並行してＺ個の同一の小さいＬＤＰＣグラフを復号する復号器を最初に検討することによって最も明解に理解できる。単一の小さいＬＤＰＣグラフについてメッセージ伝送復号器について検討してみる。復号器はメッセージ伝送アルゴリズムに対応して一連の動作を実施する。ここで、同じ復号器を増やして、同期的かつ並行してＺ個の同じ前記のＬＤＰＣグラフを復号するものとする。メッセージ伝送アルゴリズムの各動作はＺ回再現される。復号プロセスの効率は向上するが、その理由は、全体として復号がＺ倍速くなり、またメッセージ伝送プロセスを制御するために必要な制御機構がＺ個のコピーごとに再現される必要がなく、Ｚ個のコピーで共用できるからである。更に、上記のＺ−並行復号器をベクトル復号器と見なすこともできる。より小さいグラフのＺ個のコピーを作成するプロセスをより小さい（投影された）グラフのベクトル化であると見なすことができる。より小さいグラフの各ノードはＺ個のノードを含むベクトル・ノードになり、より小さいグラフの各エッジはＺ個のエッジを含むベクトル・エッジになり、より小さいグラフの復号で交換される各メッセージはＺ個のメッセージを含むベクトル・メッセージになる。
【００４４】
本発明はベクトル復号器が事実上、投影されたグラフよりもＺ倍大きい１つの大きいグラフを復号するように修正しつつ、上記のベクトル化の効率を得るものである。これは投影されたグラフのＺ個のコピーを制御された態様で相互連結することによって達成される。特に、ベクトル・エッジ内のＺ個のエッジが、例えば可変ノード側から制約ノード側へと進行する際に、投影されたグラフのコピー間で置換、または交換されるようにできる。Ｚ個の並行して投影されたグラフに対応するベクトル化されたメッセージ伝送プロセスで、前記の交換は、ベクトル・メッセージがベクトル化されたグラフの一方の側から他方の側に送られる際に、ベクトル・メッセージ内にメッセージを置換することによって実施される。
【００４５】
投影されたＬＤＰＣグラフを１，ｊ，．．．，Ｚで索引付けするものとする。厳密に並列の復号器では、グラフｊ内の可変ノードはグラフｊ内の制約ノードだけに接続されている。本発明によって、各々が各グラフ・コピーからの対応するベクトル・エッジを含む１つのベクトル・エッジを取り出すとＺ個のエッジ内での置換が可能になる。例えば、ベクトル・エッジ内のエッジに対応する制約ソケットを例えば並べ替えのように置換することができる。以下ではベクトル・エッジ内での例えば並べ替えのような置換をローテーションと呼ぶ場合が多い。
【００４６】
このように、本発明によって、比較的小容量のメモリを使用して比較的大きいグラフを表す、例えば記述することができる。例えば、投影されたグラフを記述する情報と、ローテーションを記述する情報とを記憶することによってグラフを表示できる。あるいは、グラフの記述を、グラフの連結性を記述する機能を実行する回路として具体化してもよい。
【００４７】
したがって、本発明のグラフ表示技術は並行した、例えばベクトル化されたグラフの実現を容易にする。その上、本発明のグラフ表示技術を、状態変数を有する、または有していない規則的、または不規則的グラフの復号を支援するために使用することができる。投影されたグラフ内のノード度を記述する情報を記憶し、ベクトル・ノード処理要素に供給してもよい。ベクトル・ノードに属する全てのノードは同じノード度を有しているので、ノード度情報は１つの投影されたグラフにしか必要ではないことに留意されたい。
【００４８】
様々な実施形態で、復号器はプログラム可能にすることによって、例えば記憶され、投影されたグラフおよび記憶されたローテーション情報に関して、または実施された機能に関して表現されるような複数のグラフ記述でプログラムされることができる。したがって、本発明の復号器は例えば規則的符号と不規則的な符号の双方のような多数の異なる符号を復号するようにプログラム可能である。ある特定の実施形態では、復号器は固定的なグラフ、または固定的なノード度およびこの情報用として使用される。このような実施形態では、グラフ記述情報は事前プログラムされたものでも、または暗示されたものでもよい。このような場合、復号器はプログラム可能な実施形態よりもフレキシビリティは低いが、プログラム可能性を支援するために必要な資源は節減される。
【００４９】
本発明の一実施形態によれば、記憶域の行を含むメッセージ・メモリが備えられる。各々の行はメッセージに対応しており、メッセージは投影されたグラフの１つのコピーと関連している。Ｚ個の複数の投影されたグラフに対応するメッセージが積み重ねられて、１列当たりＺ個のメッセージがある列を形成する。このような列はベクトル・メッセージに対応している。このようなメモリ構造によって、ベクトル・エッジに対応する例えばＺ個のメッセージ・セットのようなベクトル・メッセージが、例えば１回の動作で列内のＺ個のメッセージの全てにアクセスできるようなＳＩＭＤ命令を用いて、ユニットとしてメモリから読み出され、またはメモリへと書き込まれることが可能になる。このように、メモリはベクトル・メッセージの読み出しと書き込みをユニットとして支援する。したがって、本発明はＺ個のメッセージのセット中の個々のメッセージごとに別の読み出し／書き込みアドレスを備える必要がなくなる。
【００５０】
メモリから読み出された後のメッセージ伝送処理の単数または複数の時点で、Ｚ個のメッセージには例えば並べ替え動作のような置換動作が行われる。並べ替え動作はローテーション動作、または短縮してローテーションでよい。これらのローテーション動作は、ベクトル・エッジに関連するローテーションに対応している。ベクトル・エッジは投影されたグラフのＺ個のコピーを相互に連結して、単一の大きいグラフを形成する。このローテーションは例えば対応するベクトル（制約または可変）ノード・プロセッサに供給されるメッセージに先立って適用してもよい。あるいは、ローテーションをベクトル・ノード・プロセッサによる処理の後に適用してもよい。
【００５１】
ローテーションは例えばメッセージ・メモリをベクトル・ノード処理ユニットに接続し、これらのメッセージがメモリからベクトル・ノード処理ユニットへと送られる際にこれらのメッセージを並べ替える単純なスイッチング・デバイスを使用して実施してもよい。このような実施例では、メモリから読み出された各々のベクトル・メッセージ内のメッセージの１つが、スイッチング・デバイスによってベクトル・メッセージに適用されたローテーションによって決定されたとおりに、ベクトル・ノード・プロセッサ内のＺ個の並列のノード処理ユニットの対応する１つに供給される。上記のローテーション動作に加えて、またはその代わりにスイッチング・デバイスによって実施されるローテーション動作が、ベクトル・メッセージがメモリに書き込まれる前で、ノード処理の後にベクトル・メッセージに適用されてもよい。
【００５２】
投影されたグラフの記憶された、または計算された記述は例えば、投影されたグラフに対応する行内のメッセージが、制約ノードおよび／または可変ノードの処理中にメモリから読み出され、かつ／またはメモリに書き込まれる順序に関する情報を含んでいてもよい。大きいグラフ全体のメッセージは複数の行に記憶され、各行は小さいグラフの別のコピーに対応し、行はメッセージの列を形成するように配列される。メッセージの各列は単一のユニットとしてアクセス可能であるベクトル・メッセージを表す。このように、本発明によって投影されたグラフの複数のコピーに対応するベクトル・メッセージがアクセスされる順序を決定するために、投影されたグラフの行内のメッセージにいかにアクセスするかに関する情報を利用することができる。
【００５３】
読み出し／書き込み動作が可変ノード側の処理であるか、制約ノード側の処理であるかに応じた、ベクトル・メッセージがメモリから読み出される順序、またはメモリに書き込まれる順序の変更は、メッセージに行われる最初の置換であるといってよい。この置換は投影されたグラフに関連するインターリーバに対応する。投影された復号器グラフから大きい復号器グラフを表現するため、例えばローテーション情報のような第２セットの置換情報が、（例えば列のような）ベクトル・メッセージのアクセス順序情報に加えて記憶される。スイッチング制御情報を表す（例えばローテーション情報のような）第２の置換情報は、例えばメッセージの列のような各々のベクトル・メッセージ中のメッセージが、例えばメモリから読み出され、および／またはメモリに書き込まれる場合にどのように並べ替えられるかを示す。この二段階の置換は、完全なＬＤＰＣグラフを記述するより大きい置換を異なる機構を介して実施される２つの部分へと組み込む。
【００５４】
特定の一実施形態では、周期的な置換が第２レベルの置換として用いられるが、その理由は、このような置換の実施が容易であり、その記述がコンパクトであるからである。この場合は、説明目的でこの第２レベルの置換を記述するためにローテーションという用語を用いる動機付けになる。しかし、第２レベルの置換はローテーションに限定されるものではなく、その他の並べ替え方式を用いても実現できることを理解されたい。
【００５５】
本発明の種々の実施形態で、復号器は、例えば各々のソフト出力の正負符号またはパリティ・ビットのような１つのビットを有する多重ビットのソフト出力を生成する。この１つのビットを有する多重ビットのソフト出力は、全てのエラーが修正された場合、または受信された語にエラーがない場合のオリジナルの符号語のような、復号器のハード決定出力に対応する。次に例えば復元された符号語のような復号器出力を更に処理して、伝送された符号語を生成するために、符号化の時点で使用されたオリジナル・データを復元してもよい。
【００５６】
本発明の１つの特徴によれば、可変ノード処理をそれぞれ完全に反復した後に生成されるソフト出力および／またはハード出力は、符号語を示すパリティ・チェックの制約が現行のハード決定によって満たされているか否かを判定するために検査される。このチェック・プロセスはグラフの二段階に繰り込まれた置換構造の利点も得られる。反復的な復号プロセス（メッセージ伝送）は、符号語の復元が一旦このようにして検出されると停止してもよい。したがって、比較的エラーがない信号の場合、例えばメッセージ伝送復号プロセスが２、３回反復された後、復号は速やかに完了し、検知されることができる。しかし、受信された語がより多くのエラーを含む場合は、復号が成功する前に復号プロセスの多くの反復がなされ、またはタイムアウトの制約のためにプロセスは停止される。
【００５７】
本発明によって、成功した復号の速やかな検知により各々の受信語に固定回数の復号の反復を割り当てるシステムと比較して、資源をより効率的に利用できるようになる。
【００５８】
本発明の復号技術によって、例えば制約および／または可変ノードの復号器処理動作のような多数の復号動作を並行して行うことができるので、本発明の復号器を受信された語を高速度で復号するために使用できる。更に、本発明の新規の技術が大きいグラフを表示するため、および／またはこのようなグラフに関連する復号動作用のメッセージ伝送を制御するために利用されれば、大きいグラフの記述を記憶し、またそれらのメッセージのルーティングを制御する困難さが軽減され、および／または克服される。
【００５９】
本発明のＬＤＰＣ符号のある種の一般化および復号技術は、より大きいアルファベットを介した２つの可能な値を有するビットの単なる符号化／復号だけではなく、ある程度多くの可能性を含んでいる。本発明の方法と装置を使用して、制約ノードがパリティ・チェックの制約以外の制約を表す符号を復号することもできる。本発明を適用できるその他の関連する一般化には、メッセージ伝送アルゴリズムがグラフ上で実施される状況、またグラフを設計する選択肢を有するような状況も含まれる。本発明の用途を考慮に入れて、どのようにして本発明の技術をこれらのより一般的な状況に適用するかは当業者には明らかであろう。
【００６０】
本発明の復号技術および復号器のその他の多くの利点、特徴、および態様は以下の詳細な説明から明らかにされる。
【発明を実施するための最良の形態】
【００６１】
前述のように、本発明の復号方法および装置を説明するためにＬＤＰＣ復号器の実施形態として記載する。先ず図４および図５を参照してＬＤＰＣ符号の復号に含まれるステップを記載し、次に本発明の様々な特徴をより詳細に説明する。
【００６２】
図４は二部構造のグラフ４００を使用した不規則的ＬＤＰＣ符号の例を示している。グラフはｍ個のチェック・ノード４０２と、ｎ個の可変ノード４０６と、複数個のエッジ４０４とを含んでいる。チェック・ノードと可変ノードとの間でメッセージはエッジ４０４を経て交換される。受信された語Ｙに対応するソフト入力ビットｙ１からｙｎ、およびソフト（またはハード）出力ｘ１からｘｎは参照番号４０８で示されている。ｍ番目のチェック・ノードは参照番号４０２’を用いて特定され、ｎ番目の可変ノードは参照番号４０６’を用いて特定され、一方、ｎ番目のソフト入力ｙｎ、およびｎ番目のソフト出力ｘｎは図４では参照番号４１０、４０９をそれぞれ用いて示されている。
【００６３】
可変ノード４０６は受信された語ｙ１，．．．，ｙｎからの入力ソフト値と共に制約ノード４０２からのメッセージを処理して、可変ノードに対応する出力変数の値ｘ１，．．．，ｘｎの値を更新し、かつ制約ノードへのメッセージを作成する。１つのメッセージは可変ノードに接続された各々のエッジごとに可変ノードによって作成される。作成されたメッセージはエッジに沿って可変ノードからエッジに取付けられた制約ノードへと伝送される。説明目的のため、可変ノードから制約ノードへのメッセージは、本明細書では時々略号Ｖ２Ｃを用いて示され、一方、可変ノードから制約ノードへのメッセージは略号Ｃ２Ｖを用いて示される。特定のメッセージの発信源／発信先としての役割を果たす可変ノードと制約ノードの特定の１つを示すために、この略号のＶとＣの成分に指標を付与してもよい。各々の制約ノード４０２は特定の制約ノードに取付けられたエッジを経て可変ノードから受信されたメッセージを処理する役割を負っている。可変ノードから受信されたＶ２Ｃメッセージは制約ノード４０２によって処理されてＣ２Ｖメッセージが作成され、これは次に各々の制約ノードに取付けられたエッジに沿って返送される。次に可変ノード４０６はソフト入力値と共にＣ２Ｖメッセージを処理して、新たなＶ２Ｃメッセージを作成し、かつ伝送し、またソフト出力ｘｉを生成する。可変ノード４０６で処理を行う手順には次のステップが含まれる。すなわち、作成されたメッセージをチェック・ノード４０２に伝送し、可変ノードでソフト出力ｘｉを生成し、かつチェック・ノードからのメッセージを受信し、これらのステップは、可変ノード４０６からの出力ｘｉによって符号語が成功裏に復号されたことが示されるまで、または例えば固定回数のメッセージ伝送の反復の完了のようなその他の停止の判断基準が満たされるまで、繰り返して、すなわち反復的に行われてもよい。上記の動作手順は厳密に上記の順序で行われる必要がないことを理解されたい。ノード処理は非同期的に行われ、可変ノード処理および制約ノード処理は同時に行われてもよいことに留意されたい。それでも尚、反復的プロセスの論理は前述のとおりである。
【００６４】
メッセージＶ２ＣおよびＣ２Ｖは例えば各々がＫビットの単数または複数のビットでよく、但しｋはゼロではない正の整数値である。同様に、ソフト出力ｘｉは単数または多重ビットでよい。多重ビットのメッセージおよび出力によって、メッセージまたは出力内の信頼度の情報または信頼性の情報を信頼する可能性が得られる。多重ビット、（ソフト）出力の場合、例えば復号された符号語のビットのような、可変ノードに対応する復号プロセスの単一ビットのハード出力を供給するために、ソフト出力値の正負符号を利用してもよい。出力されたソフト値は復号されたソフト値に対応してもよく、または代替として、ＬＤＰＣ復号器がその内部でほんの１個のモジュール(but one module)である別のより大きい反復的プロセスで使用できるいわゆる外因性情報（対応する入力情報を除く）であってもよい。
【００６５】
ここで図５ａから図５ｄについてＬＤＰＣ符号の復号に関連する反復的メッセージ伝送プロセスを更に説明する。
【００６６】
ＬＤＰＣ符号を復号する場合、各々の制約ノードおよび可変ノードでの処理は独立して行ってもよい。したがって、可変ノード処理および／または制約ノード処理は、復号プロセスの特定の反復について可変ノードおよび制約ノードの処理の一部または全部が完了するまで、一時に１つのノードずつ例えば順次行ってもよい。このようにすれば、可変ノードおよび／または制約ノードの各々と関連する処理を行うために、単一ユニットの処理ハードウェアを供給することができ、また必要ならば再利用することができる。ＬＤＰＣ復号の他の重要な特徴は、特定の処理反復中に使用されるＶ２ＣおよびＣ２Ｖが、例えば同じ処理反復中のように必ずしも同時に生成される必要がないことである。このようにすれば、使用されるメッセージがいつ最後に更新されたかに関わりなく、制約ノードと可変ノードの処理を並行して実行できる実施形態が可能になる。可変ノードおよび制約ノードの処理の全てが受信メッセージを処理し、更新メッセージを作成する充分な回数のメッセージ更新および反復に続いて、グラフが適切に設計されていること、および処理される受信語に未修正のエラーが残されていないことを前提として、可変ノードの（ハード）出力が収束する。
【００６７】
各々のチェック・ノードおよび可変ノードでの処理を独立した動作であると見なすことができるものとして、ここで図５ａ−５ｄを参照してチェック・ノードＣｎ５０２’および可変ノードＶｎ５０６’の一例での反復的処理についてより詳細に説明する。説明目的のため、メッセージ値とソフト入出力値を数字であると考える。正数は０のハード・ビット決定に対応し、負数は１のハード・ビット決定に対応する。マグニチュードが大きいことは信頼性が高いことを示す。したがって、数字０は完全に信頼できないことを示し、符号（正または負）は無関係である。この規則は、ソフト値（メッセージ、受信され、出力された値）が関連するビットの対数尤度を表す標準的な通例と一致している。すなわちソフト値は下記の形式をとる。
【００６８】
log｛（確率ビットが０）／（確率ビットが１）｝
但し、確率は例えば受信された値の場合は通信チャネルからのビットの物理的な観測のような、ある無作為の変数によって条件付けられる。
【００６９】
図５ａはＬＤＰＣ復号プロセスの最初のステップを示している。最初に、可変ノードＶｎ５０６’に、ソフト入力、例えば処理される受信語から受信された値（１またはそれ以上のビット）ｙｎが供給される。復号動作の開始時点でのＣ２Ｖメッセージおよびソフト出力Ｘｎ５０９は最初は０に設定される。例えばゼロ値Ｃ２Ｖメッセージ、および入力ｙｎのような受信した入力に基づいて、可変ノードＶｎ５０６’は、それが接続されている各々のチェック・ノードごとに１つのＶ２Ｃメッセージを作成する。標準的には、最初のステップで、これらの各メッセージはｙｎに等しい。
【００７０】
図５ｂでは、作成されたＶ２Ｃメッセージは可変ノードＶｎ５０６’に接続された各々のエッジに沿って伝送されたものとして示されている。このように、更新されたＶ２Ｃメッセージは、可変ノードＶｎ５０６’に結合されたチェック・ノードＣｍ５０２’を含む各チェック・ノード５０２に伝送される。
【００７１】
Ｖ２Ｃメッセージの作成に加えて、可変ノードの処理の結果、処理を行う可変ノードに対応するソフト出力Ｘｎ５０９’が更新される。図５ｃにはソフト出力Ｘｎが更新されたことが示されている。異なるステップとして示されているものの、ソフト出力はＶ２Ｃが出力されると同時に出力されてよい。
【００７２】
以下に後述するように、本発明のある実施形態では、受信された語から符号語がいつ復元されたのか、すなわちパリティ制約が出力値によっていつ満たされたのかを判定するためにソフト出力（またはそれらに関連するハード決定）を利用してもよい。これは成功した復号を示し（発見された符号語は正しくないが、すなわち伝送された符号語ではないが）、それによって反復的な復号プロセスはタイムリーに、例えばある固定された最大許容メッセージ伝送の反復数が完了する前に停止することができる。
【００７３】
チェック・ノードの処理は、チェック・ノード、例えばチェック・ノードＣｍ５０２’が、それが接続されているエッジに沿ってＶ２Ｃメッセージを一旦受信すると実行することができる。受信されたＶ２Ｃメッセージはチェック・ノード内で処理されて、特定のチェック・ノードに接続された各エッジごとに１つの更新されたＣ２Ｖメッセージを作成する。チェック・ノードの処理の結果、エッジに沿って可変ノードに返送されたＣ２ＶメッセージはＶ２Ｃメッセージの各々の値に左右される。このＶ２Ｃメッセージはチェック・ノードに接続された他のエッジで受信されたものである。しかし（通常は、また好適には必ずしもではなく）Ｃ２Ｖメッセージが伝送されている特定の可変ノードから受信されたＶ２Ｃメッセージには左右されない。このように、Ｃ２Ｖメッセージは、メッセージが伝送されているノード以外の可変ノードより受信されたメッセージから作成された情報を伝送するために利用される。
【００７４】
図５ｄは更新されたＣ２Ｖメッセージのノード５０６’を含む可変ノードへの伝送を示している。特に、図５ｄには制約ノードＣｍ５０２’が更新された２つのＣ２Ｖメッセージを出力していることが示されており、更新されたＣｍ２Ｖｎメッセージは可変ノードＶｎ５０６’に供給される。Ｖｎ５０６’は更に、それが接続されている他の制約ノード（単数または複数）からの別の更新されたＣ２Ｖｎメッセージ（単数または複数）を受信する。
【００７５】
更新されたＣ２Ｖメッセージを受信すると、可変ノード処理を繰り返して、更新されたＶ２Ｃメッセージおよびソフト出力を作成することができる。次に、Ｃ２Ｖメッセージの更新を繰り返すことができ、復号器停止基準が満たされるまでそれが継続される。
【００７６】
このように、図５ａ−５ｄに示された処理は、初期値に対して更新されたメッセージ値を用いて、最初の反復以降、復号プロセスが停止するまで繰り返される。
【００７７】
ＬＤＰＣ復号プロセスの反復的な性質、および個々のノードでの処理を他のノードでの処理とは独立して行うことができるという事実によって、ＬＤＰＣ復号器を実施する際に大きいフレキシビリティが得られる。しかし、前述したように、エッジとノードとの関係が本当に複雑なので、例えばグラフの記述のようなエッジの関係性情報を記憶することが困難になることがある。更に重要な点は、グラフの複雑さによって、複数のメッセージが同時に伝送されるべき場合にメッセージの伝送を並行して実施することが困難になることがあることである。
【００７８】
実際のＬＰＤＣ復号器の実施形態は制約ノードおよび／または可変ノード間のエッジに沿って伝送されるメッセージを記憶するためのエッジ・メモリを含んでいる場合が多い。加えて、これらの実施形態はエッジ接続、またはソケット対を特定する情報を含み、それによって、場合により復号グラフを規定する置換マップと呼ばれることがあるグラフ記述子を含んでいる。この置換マップは記憶されたデータとして実施してもよく、または置換を計算し、または置換を意味する回路として実施してもよい。ノードに関連する実際の処理を行うには、エッジ・メモリに加えて単数または複数のノード処理ユニットが必要である。
【００７９】
ＣＰＵがベクトル処理ユニットとして動作することを制御し、かつＣＰＵに結合されたメモリを使用してメッセージの伝送を制御するためにソフトウェアが使用される、ソフトウェアによるＬＤＰＣ復号器の実施が可能である。ソフトウェアの実施形態では、復号器のグラフ記述と、エッジ・メッセージ、並びにＣＰＵを制御するのに用いられる復号器ルーチンを記憶するために単一のメモリを使用することもできる。
【００８０】
後述するように、本発明の様々な実施形態で、単数または複数のエッジ・メモリを使用してもよい。多重エッジ・メモリの一実施例では、Ｃ２Ｖメッセージの記憶と伝送用に第１のエッジ・メモリが使用され、Ｖ２Ｃメッセージの記憶と伝送用に第２のエッジ・メモリが使用される。このような実施形態では、例えば一方が制約ノード処理を行い、他方が可変ノード処理を行うための多重ノード処理ユニットを使用してもよく、しばしば使用される。後述するように、このような実施形態によって可変処理動作と制約処理動作を並行して実施することができ、その結果生じたメッセージは復号プロセスの次の反復で使用されるように２つのメッセージ・メモリの各々に書き込まれる。
【００８１】
ここで引き続き本発明を説明する上で用いられる小さいＬＤＰＣグラフとその表現の簡単な例を提示する。ＬＤＰＣグラフの説明の後で、小さいグラフを復号するために使用できるＬＤＰＣ復号器を説明する。
【００８２】
図６はグラフ６００の形式の簡単な不規則的ＬＤＰＣ符号を示している。符号は５つの可変ノードＶ１からＶ５６０２によって示されるように５つの長さの符号である。４つのチェック・ノードＣ１からＣ４６０６は、メッセージがそれを介して伝送される全部で１２のエッジ６０４によって可変ノード６０２に結合されている。
【００８３】
図７はマトリクス７０２、７０４を用いて、図６に示したＬＤＰＣ符号をパリティ・チェック・マトリクスの形式で示している。前述したように、エッジは１を使用して置換マトリクスＨ７０２内に表示されている。ビットｘｉは可変ノードＶｉに関連している。マトリクス７０６と７０８はグラフ内のエッジに対応して、Ｈ内に可変ソケット順序と制約ソケット順序のそれぞれに応じて索引付けされた１を示している。
【００８４】
説明のために、１２のエッジが可変ノード側から、すなわちそれらの可変ソケットに応じて置換されることにする。可変ノード６０２とチェック・ノード６０６の間のエッジによって確立される連結は図６に示される。説明のため、チェック・ノードＣ１、Ｃ２、Ｃ３に接続する可変ノードＶ１に取付けられたエッジには、可変ソケット置換に対応して１、２、３のラベルが割当てられている。可変ノードＶ２はエッジ４、５、６によってそれぞれチェック・ノードＣ１、Ｃ３、Ｃ４に接続されている。可変ノードＶ３はエッジ７、８によってそれぞれチェック・ノードＣ１およびＣ４に結合されている。加えて、可変ノードＶ４はエッジ９、１０によってそれぞれチェック・ノードＣ２およびＣ４に結合され、一方、可変ノードＶ５はエッジ１１、１２によってそれぞれチェック・ノードＣ２およびＣ３に結合されている。この索引付けは図７のマトリクス７０６、すなわち可変ソケット順に対応している。
【００８５】
図８は接続されている可変ノードおよびチェック・ノードに対して可変ノード側から置換された図６の１２個のエッジの関係を示している。行８０２は５つの可変ノードＶ１からＶ５を示している。変数８０２の下には、特定の可変ノードに接続された関連するソケットに対応するエッジ１から１２の８０４が示されている。エッジは可変ノード側から配列されているので、行８０４には１−１２の順序で出現していることに留意されたい。メッセージは行８０４内に示された順序でメモリに記憶されるものと想定しよう。
【００８６】
可変ノードの処理中、メモリ内の１２のエッジ・メッセージは、例えば８０４に示された順序で順次アクセスされる。このように、可変ノードの処理中にメッセージは単純に順番に読み出され、処理ユニットに供給されてよい。
【００８７】
行８０６は図６および７の符号内に存在する４つの制約ノードＣ１からＣ４を示している。エッジは制約ノードに接続された順を反映して行８０４’内で並べ替えられているが、表示された索引付けは可変ノード側から誘発されたものであることに留意されたい。したがって、エッジ・メッセージが可変ノード側から順に記憶されるものと想定すると、制約ノード処理を行う際にメッセージは行８０４’に示された順に読み出されよう。すなわち、制約ノード処理中に、メッセージは１、４、７、２、９、１１、３、５、１２、６、８、１０の順にメモリから読み出されよう。メッセージ配列モジュールを使用して、可変ノードおよびチェック・ノードの処理動作中にメモリからデータを読み出し、またはメモリにデータを書き込むために、例えば記憶域のようなエッジ・メッセージ・アクセス情報の適正なシーケンスを出力することができる。
【００８８】
ここで図９に関連して、一時に１つのエッジずつ順次メッセージ処理動作を行う直列ＬＤＰＣ復号器９００と、図６に示された符号の例を用いた復号について説明する。ＬＤＰＣ復号器９００は復号器制御モジュール９０２と、メッセージ配列モジュール（ソケット置換メモリ）９０４と、ノード度メモリ９１０と、エッジ・メモリ９０６と、ノード・プロセッサ９０８と、出力バッファ９１６と、ハード決定メモリ９１２と、パリティ・チェック確認器９１４とを備えている。
【００８９】
エッジ・メモリ９０６はＬ個のＫビット記憶域を含んでおり、各々のＫビット記憶域は１つのエッジに対応している。但し、Ｌは使用されるＬＤＰＣグラフ内のエッジの総数であり、Ｋはエッジに沿って交換されるメッセージ当たりのビット数である。具体性を持たせるため、メッセージは可変ソケットによって誘導されるエッジ配列に従った順序で記憶されるものと想定する。このように、例えばグラフ６００の場合、エッジ１，２，．．．，１２に対応するメッセージは表示された順序で記憶される。ハード決定メモリ９１２はＬ個の１ビット記憶域を含んでおり、各々の１ビット記憶域は１つのエッジに対応している。このメモリはそれぞれのエッジに沿って可変ノードによって伝送されるハード決定を記憶するので、パリティ・チェック制約を確認できる。パリティ・チェック確認器９１４は、チェック・ノード・プロセッサがメッセージを受信するとハード・ビット決定を受ける。パリティ・チェックはパリティ・チェック確認器で確認され、全てのチェックが満たされている場合は、収束信号を復号器制御モジュール９０２に伝送する。
【００９０】
メッセージ配列モジュール９０４は、可変ノード側から見た、または制約ノード側から見たエッジ・メモリ内のメッセージの配列を記述する情報を含む置換マップまたは参照用テーブルとして具体化してもよい。このように、本例のグラフ６００の場合、制約側から見たエッジの配列を満たすシーケンス１、４、７、２、９、１１、３、５、１２、６、８、１０は効率的にメッセージ配列モジュールに記憶されよう。このシーケンスは制約ノード処理のためのメッセージを配列することとパリティ・チェック確認器９１４によって処理されるためのハード決定メモリ９１２から読み出されたハード決定を配列することに使用される。
【００９１】
図９の復号器では、エッジに対応するメッセージはノード・プロセッサによって処理された後で上書きされる。このようにして、エッジ・メモリはＶ２ＣメッセージとＣ２Ｖメッセージを交番で記憶する。ハード決定の確認は制約ノード処理中に、例えばＶ２Ｃメッセージがエッジ・メッセージ・メモリ９０６から読み出される際に行われる。
【００９２】
復号器制御ユニット９０２は、例えば収束信号を受けることにより、または許容された反復カウントに達することにより反復的な復号プロセスを停止する時点を判定するために、ノード処理ユニットおよびパリティ・チェック確認器にノード度情報を供給するために、または供給を制御するために、かつメッセージ配列モジュール９０４へのエッジ索引の供給を制御するために、復号器の動作を可変ノード処理動作モードとチェック・ノード処理動作モードの間で切り換える役割を果たす。動作中、復号器制御モジュール９０２はエッジ索引をメッセージ配列モジュール９０４に伝送する。数値、すなわちエッジ索引はグラフ内の全てのエッジをとおる順序で時間を経て増分される。実施されているグラフ内の各エッジごとに異なるエッジ索引、例えば一意的なエッジ索引が使用される。受信された各々のエッジ索引に応答して、メッセージ配列モジュールは例えばエッジ・メモリ・アドレス情報のようなエッジ識別子を出力し、それによって例えば読み出しまたは書き込みのようなアクセスがなされるエッジ記憶域が所定の任意の時間に選択される。可変ソケットの配列と仮定すると、メッセージ配列モジュール９０４は、可変ノード処理中にメッセージが順次読み出され、かつ再び書き込まれるようにし、また制約ノード処理中にメッセージが制約ソケット配列に対応する順序で読み出され、再び書き込まれるようにする。このようにして、上記の例では、メッセージは可変ノード処理中に１、２、３，．．．，１２の順に読み出され、または再び書き込まれ、かつ同時に、ハード決定が１、２、３，．．．，１２の順にハード決定メモリ９１２へと書き込まれる。制約ノード処理中、メッセージは１、４、７、２、９、１１、３、５、１２、６、８、１０の順に読み出され、かつ再び書き込まれ、かつ同時に、メッセージ配列モジュール９０４はハード決定ビットがハード決定メモリ９１２から１、４、７、２、９、１１、３、５、１２、６、８、１０の順に読み出されるようにする。
【００９３】
復号器制御モジュール９０２から受けたエッジ識別子に応答してメッセージがエッジ・メモリから読み出されると、これらのメッセージはノード・プロセッサ９０８に供給される。ノード・プロセッサ９０８は動作モードに応じて適宜の制約ノードまたは可変ノードの処理動作を行い、それによって任意の所定の時点で実施される特定のノードに対応する更新メッセージを作成して受信したメッセージを利用する。その結果生ずる更新メッセージは次にエッジ・メッセージへと再び書き込まれて、メモリから読み出されたばかりのメッセージに上書きされる。特定のノードに送られたメッセージは連続的なブロックとして、すなわち順次ノード・プロセッサに到達する。復号器制御モジュール９０２は、例えばノードに対応する最後のメッセージを示して、ノード度情報を提供することによって、ノード・プロセッサへノード表現の信号を送る。グラフ６００の例の場合、可変ノード度が例えばシーケンス（３、３、２、２、２）として指定され、制約ノード度が例えばシーケンス（３、３、３、３）として指定されよう。この情報はノード度メモリ９１０内に記憶され、次に復号器制御モジュール９０２がエッジ索引を介して反復する際にこのモジュールによって読み出されよう。あるいは、ノード度情報は各々のノード処理ユニットへと前もってプログラムされてもよい。これは、例えば前もってノード度が均一であることが判明している場合、すなわちグラフが規則的である場合に好適であり得る。
【００９４】
パリティ・チェック確認器９１４は、着信メッセージが単一ビットであり、発信メッセージが計算され、内部計算がより簡単であること以外はチェック・ノード・プロセッサと全く同様に動作する。
【００９５】
可変ノードの動作モード中、例えば可変ノードの各々の関連するメッセージ更新およびソフト出力値作成動作のような処理が完了するまで、可変ノード計算がノード処理ユニットによって一時に１つのノードずつ行われる。メッセージは可変ノード側の順にノード・プロセッサ９０８に送られるので、１つのノードに対応する全てのメッセージが順次ノード・プロセッサ９０８に到達する。可変ノード処理の反復が完了すると、復号器制御モジュール９０２によって復号器９００は制約ノードの処理動作モードへと切り換えられる。Ｃ／Ｖ制御信号の変化に応答して、ノード処理ユニット９０８は可変ノード処理モードから制約ノード処理モードへと切り換わる。加えて、メッセージ配列モジュール９０４が、メッセージ識別子が制約ソケットの順にエッジ・メモリへと供給されるモードへと切り換わる。Ｃ／Ｖ制御線を経て送信される単数または複数の制御信号を利用して、制約ノード処理と可変ノード処理間の切り換えが制御される。
【００９６】
復号器制御回路９０２が、制約ノード処理を制約ノードのシーケンスで一時に１つのノードずつ行うように復号器を制御すると、エッジ・メモリに記憶されているメッセージは、この場合は制約ノード処理によって作成されるＣ２Ｖメッセージによって再び更新される。フルセットの制約ノードに関連する処理が完了すると、復号器制御回路９０２は可変ノード処理動作モードに再び切り換わる。このようにして、復号器９００は可変ノード処理と制約ノード処理の間で切り換えられる。前述したように、復号器制御回路９０２が復号動作が完了したことを判定するまで、処理は一時に１つのノードずつ順次行われる。
【００９７】
図９に示したスカラまたは逐次的ＬＤＰＣ復号システムは比較的僅かなハードウェアを使用して実施できる。加えて、これはソフトウェアによる実施にも良く適している。残念ながら、実施される処理の逐次的な性質により比較的遅い復号器の実施形態になる傾向がある。したがって、図９に示されたスカラのアーキテクチャはある種の注目すべき特性を有しているものの、高い復号速度と大きい符号語の使用が必要とされる光通信またはデータ記憶のような高帯域幅のアプリケーションには適さない傾向がある。
【００９８】
ベクトル化された大きいＬＤＰＣグラフを復号するための復号器を提示する前に、本発明のグラフ・ベクトル化の特徴に関する基本的なコンセプトと技術について説明する。ベクトル化の説明の後に、本発明を実施したベクトル化されたＬＤＰＣ復号器の例を提示する。
【００９９】
ＬＤＰＣグラフのベクトル化に対する理解を得る目的で、パリティ・チェック・マトリクスＨを有する‘小さい’ＬＤＰＣ符号を検討する。小さいグラフはより大きいベクトル化されたグラフの文脈で、投影されたグラフと呼ばれる。ΨはＺ×Ｚの置換マトリクスのサブセットを示すものとする。Ψ内の置換の逆もΨ内にあるものと想定する。グラフが小さい、投影されたグラフであるとすると、Ｈの各要素をＺ×Ｚマトリクスと入れ換えることによってＺ倍大きいＬＤＰＣグラフを形成することができる。Ｈの０の要素は、０で示されるゼロ・マトリクスと入れ換えられる。Ｈの１の要素は各々Ψからのマトリクスと入れ換えられる。このようにして、ＬＤＰＣグラフをＺ倍大きく‘リフト’する。表示の複雑さは大まかには、置換マトリクス｜ＥＨ｜log ｜Ψ｜を指定するのに必要なビット数プラスＨを表すために必要な複雑さからなっている。但し｜ＥＨ｜はＨ内の１の数を示し、｜Ψ｜はΨ内の個別の置換数を示す。例えば、Ψが周期的置換のスペースである場合、｜Ψ｜＝Ｚである。実際にはｎ〜１０００の場合、例えばＺ＝１６である。
【０１００】
2004531972.tif 000006
例：小さいパリティ・チェック・マトリクスをリフトすると、σｉｉ＝１，．．．，１６は投影された可変ソケットの順でここに索引付けして示されたΨの要素である。
【０１０１】
サブセットΨは一般に様々な判断基準を用いて選択することができる。上記の構造の主要な動機付けの１つは復号器のハードウェア実施形態を簡略化することである。したがって、ハードウェア、例えばスイッチング・ネットワークで効率的に実施可能できる置換にΨを限定することが有利である。
【０１０２】
並列スイッチング・ネットワークのトポロジーはマルチプロセッサのアーキテクチャおよび高速通信スイッチに関連してよく研究されたテーマである。置換サブセットΨに適したアーキテクチャの実際的な一例は、例えばオメガ（完全なシャッフル）／デルタ・ネットワーク、対数シフタ・ネットワーク等を含む等級の多層スイッチング・ネットワークである。これらのネットワークの実施の複雑さは適度なものであり、サブセットΨにとって充分な豊かさをもたらす。加えて、多層スイッチング・ネットワークは良好にスケーリングされ、例えばその複雑さはＮlog Ｎのように増大する。但しＮはネットワークへの入力数である。それによってこのネットワークは超並列ＬＤＰＣ復号器に特に適している。あるいは、本発明の復号器では、比較的低レベルの並列構造と少ないＺで、置換のサブセットΨを単一の層で実施することができる。
【０１０３】
ＬＤＰＣグラフは、いずれかの一対のノードが１つ以上のエッジによって接続されている場合は“多重エッジ”を有すると言われる。多重エッジは１つ以上のエッジによって接続された一対のノードを接続するエッジのセットである。ＬＤＰＣグラフにとって多重エッジを有することは一般に望ましくはないが、多くの場合、投影されたグラフが多重のエッジを処理するベクトル化されたグラフ構造ではそれが必要になる。パリティ・チェック・マトリクスの概念を拡張して、マトリクスのエントリが関連するノード対を接続するエッジ数が示されるようにできる。符号語の定義は依然として同じである。すなわち、符号は０，１のセットであり、ベクトルｘはＨ×＝０モジュロ２を満たす。投影されたグラフを多重のエッジでベクトル化する場合、本発明によって、多重エッジ内の各々のエッジはΨからの置換マトリクスと置き換えられ、これらのマトリクスが加算されて、全符号の拡張されたパリティ・チェック・マトリクスが産出される。このように、投影されたグラフのパリティ・チェック・マトリクスＨ内のｊ＞１が、Ψからの置換の合計σｋ＋σｋ＋１．．．＋σｋ＋ｊ−１へと‘リフト’される。通常は、合計の要素が選択されるので、σｋ＋σｋ＋１．．．＋σｋ＋ｊ−１の各エントリは０か１である。すなわち全体のグラフは多重エッジを有していない。
【０１０４】
上記のリフティングは１つの制約を有していると思われる。上記の構造の下で、符号の長さと符号化されたデータ・ユニットの長さの双方ともＺの倍数でなければならない。しかしこの明白な制約は容易に克服される。符号化されるべきデータ・ユニットがＡＺ＋Ｂの長さを有し、Ａは正の整数であり、Ｂは１からＺまでであり、また所望の符号長さはＣＺ＋Ｄであり、Ｃは正の整数であり、Ｄは１からＺ−１までであると想定する。ＥＺ≧ＣＺ＋Ｄ＋（Ｚ−Ｂ）になるようにＥを最小の正の整数とする。データ・ユニットが符号語の一部に見えるように長さＥＺの符号語を作成するために、（Ａ＋１）Ｚの長さのデータ・ユニットを符号化するリフトされたグラフを設計し、これを利用して以下のように所望の符号パラメータを作成することができる。データ・ユニットの長さがＡＺ＋Ｂであるとすると、Ｚ−Ｂゼロを連結して長さ（Ａ＋１）Ｚのデータ・ユニットが作成される。そのデータ・ユニットは符号化されて、長さＥＺの符号語が作成される。Ｚ−Ｂゼロは伝送されない。符号語内の他のＥＺ−（Ｚ−Ｂ）の範囲外でＥＺ−ＣＺ−Ｄ−（Ｚ−Ｂ）ビットが選択され、それらがパンクチュア状態になる。パンクチュア・ビットの数は０からＺ−１までであることに留意されたい。これらのビットは伝送されないので、伝送される実際のビット数はＥＺ−（Ｚ−Ｂ）−（ＥＺ−ＣＺ−Ｄ−（Ｚ−Ｂ））＝ＣＺ＋Ｄであり、これが所望の符号長である。前もって追加のゼロとパンクチュアド・ビットに関して承知している受信側は、ソフト・ビットとパンクチュアド・ビットを入れ換えて削除を示し、またソフト・ビットと既知のゼロ・ビットを入れ換えて可能な最大の信頼度でゼロ値を示す。長さＥＺの拡張された受信語はここで復号されて、オリジナル・データ・ユニットが復元される。実際には、通常は僅か１つのベクトル・ノードからのビットをパンクチュア状態にし、僅か１つのベクトル・ノードからの既知のビットを言明することによってこれらの調整を行う。
【０１０５】
ここでＬＤＰＣグラフをベクトル化する前述の技術を利用した様々な復号器の関係性について扱う。
【０１０６】
前述のように、ＬＤＰＣ符号のメッセージ伝送復号には、符号を表すグラフのエッジに沿ってメッセージを伝送し、かつ例えば可変ノードおよび制約ノードのようなグラフのノードでのメッセージに基づいて計算を行うことが含まれる。
【０１０７】
ベクトル化されたＬＤＰＣグラフの場合、復号プロセスを以下のようにベクトル化することができる。復号器はそれが投影されたＬＤＰＣ符号のＺ個のコピーを同期的かつ並行して復号しているかのように動作する。復号プロセスの制御は投影されたＬＤＰＣのグラフに対応し、Ｚ個のコピー全体で共用してもよい。このように、復号器は、ベクトル・エッジを横切りかつベクトル・ノードによって受信されるベクトル・メッセージ上で動作するものと説明され、各ベクトルはＺの要素を有している。ソケットもベクトル化される。特に、ベクトル・ノード・プロセッサは並列のＺ個のノード・プロセッサを備え、メッセージのベクトル（ｍ１，．．．，ｍＺ）がベクトル・ノード・プロセッサに送られると、メッセージｍｉがｉ番目のプロセッサに送られる。このように、ベクトル・ノード・プロセッサ内ではメッセージのルーティングまたは並べ替えは行われない。すなわちベクトル・メッセージは固定的な態様でプロセッサのベクトルと位置合わせされる。
【０１０８】
Ｚ個の投影されたグラフの純粋に分解された並列の実施形態と上記の実施形態との１つの相違は、メッセージ伝送プロセス中にメッセージがベクトル・メッセージ内で並べ替えされることである。この並べ替え動作はローテーションと呼ばれる。ローテーションはΨによって規定される置換動作を実施する。ローテーションであるので、投影されたグラフのＺ個のコピーの処理経路が混合し、それによってこれらが連結されて単一の大きいグラフが形成される。投影されたグラフに必要な制御情報に加えて、ローテーションを指定する制御情報が必要である。幸運なことに、ローテーション制御情報は比較的僅かなメモリを使用して指定できる。
【０１０９】
本発明によってローテーション用には様々な置換を利用できるが、周期的な置換はこのような置換を行うのが容易であるので特に好適である。簡略にするため、ここでΨは周期的置換のグループを含むものと想定する。この場合、本例の大きいＬＤＰＣグラフは準周期的構造を有するように制約される。この例の目的で、Ｎをグラフ内の可変ノード数とし、Ｍをグラフ内の制約ノード数とする。第１にＮとＭの双方ともＺの倍数であり、Ｎ＝ｎＺおよびＭ＝ｍＺであるものとする。但しＺは周期の順序を示す。
【０１１０】
ノードが二重に索引付けされることに注目されたい。このとき、可変ノードｖｉ，ｊは投影されたグラフのｉ番目のコピーからのＪ番目の可変ノードである。Ψは周期的置換のグループであるので、ｋ＝１，．．．，Ｚとして可変ノードｖｉ＋ｋmod ｚ，ｊが制約ノードＣａ＋ｋmod ｚ，ｂであるならば、可変ノードｖｉ，ｊは制約ノードＣａ，ｂに接続されている。
【０１１１】
ここで極めて小さいグラフ表示とローテーション情報とを用いて大きいグラフを表現する本発明の技術を、グラフ６００のベクトル化に関する図１０から１６を参照して説明する。これらの図面を参照して説明される技術は極めて大きいＬＤＰＣグラフにも適用できる。
【０１１２】
本発明によれば、図６に示した小さいグラフを複製し、すなわち複数のコピーを作成し、次に複製されたグラフの様々なコピーを相互に連結するローテーション動作を実施することによって大きいグラフを作成することができる。大きいグラフ構造内の小さいグラフは投影されたグラフと呼ばれる。
【０１１３】
図１０は図６に示された小さいグラフの３つのコピーを並行して作成した結果を示している。可変ノード６０２’、６０２”、６０３’”は図６のグラフの３つのコピーの作成によって生じた第１から第３までのグラフにそれぞれ対応している。加えて、チェック・ノード６０６’、６０６”、６０６’”は３つのコピーの製造から生じた第１から第３のグラフに対応している。３つのグラフの１つのノードを３つのグラフの別の１つのノードに連結するエッジがないことに留意されたい。したがって、基本グラフを３だけ“リフト”するこのコピー・プロセスによって、３つのばらばらな同一のグラフが生ずる。
【０１１４】
図１１はマトリクス１１０２および１１０４を用いた前述のコピー・プロセスの結果を示している。オリジナルのグラフの３つのコピーを作成するためには、マトリクス７０２内の各々の非ゼロ要素の代わりに３×３の単位行列（identity matrix）に置き換えられることに留意されたい。このように、マトリクス７０２内のそれぞれの１は、対角線に沿って１を有し、またはその他のどの場所にも０を有する３×３マトリクスと置き換えられて、マトリクス１１０２が作成される。マトリクス１１０２のエッジ数はマトリクス７０２が有するエッジ数の３倍であり、図６に示した基本グラフの３つのコピーごとにそれぞれ１２のエッジを有することに留意されたい。この場合、変数ｘｉｊは可変ノードＶｉｊに対応している。
【０１１５】
図１２はグラフ１０００を構成する（３×１２）３６のエッジと、（３×５）１５の可変ノードと、（３×４）１２の制約ノードとの関係を示している。図８の場合のように、エッジは可変ノード側から置換される。
【０１１６】
注釈のために、ノード、制約、またはエッジを特定するために用いられる最初の数は、例えば第１、第２、または第３のグラフ・コピーのようなエッジが属するグラフ・コピーを示している。２番目の数は、基本グラフの特定のコピー内の要素の数を特定するために用いられている。
【０１１７】
例えば、行１２０２’内で、グラフの第１のコピーのエッジ２を示すために（１，２）の値が用いられ、一方、行１２０２”内で、グラフの第２のコピーのエッジ２を示すために（２，２）の値が用いられている。
【０１１８】
エッジ行１２０２’、１２０２”、１２０２’”は可変ノードに関連するので、図８に示したエッジの行８０４の３つのコピーを表す行８０４の単なるコピーであることに留意されたい。同様に、エッジ行１２０４’、１２０４”、１２０４’”は可変ノードに関連するので、図８に示したエッジの行８０４’の３つのコピーを表す。
【０１１９】
ここで規定されたＺ＝３の並行グラフを復号するために図９の復号器９００をどのように修正するのかについて簡単に説明する。ノード・プロセッサ９０８はベクトル・ノード・プロセッサから構成され、３つの同一のノードを並行して同時に処理することができる。ノード・プロセッサ９０８からの出力は全てベクトク化されることによって、以前に搬送された３倍のデータを搬送する。ハード決定メモリ９１２とエッジ・メッセージ・メモリ９０６は３倍広く構成され、各々が単一のＳＩＭＤ命令の方向を利用して３つのユニット（それぞれ、ビット・メッセージまたはＫビット・メッセージ）を並行して書き込みまたは読み出しできる。そこでこれらのメモリからの出力は以前よりも３倍広いベクトルとなる。パリティ・チェック確認器９１４と出力バッファ９１６も、全ての処理が適宜に並列処理されて適宜にベクトル化される。
【０１２０】
ここでローテーションを本例に導入することを検討してみる。これは図１１に示された３×３単位行列の各々を図１３に示すような３×３周期的置換マトリクスと置き換えることによって示すことができる。図１３で用いられている周期的置換には３つの可能性があることに留意されたい。置換マトリクスの最初の行の第１、第２、または第３の位置のどの位置に置換マトリクスが“１”を有しているかを示すことによって、単位行列と置き換えられる特定の置換マトリクスを示すことができる。例えば左上から始まり、右下コーナーへと進む（ベクトル制約ソケットの順序）マトリクス１３０２の場合、ローテーションはシーケンス（２、２、３、３、１、１、１、３、２、１、２、３）によって指定できよう。
【０１２１】
図１４は制約ノード側で周期的置換（ローテーション）を行う効果を示している。置換は制約ノード側から行われるので、可変ノード側からのエッジ間の関係、例えば配列は行１４０２’、１４０２”、および１４０２’”に示したものと変わらない。しかし、制約側からは置換の結果、列内のエッジ、例えば特定のベクトル・エッジ内のエッジは行１４０４’、１４０４”、１４０４’”に示すように並べ替えされる。それによって投影されたグラフの異なるコピーに対応するノード間の相互連結が生ずる。
【０１２２】
例えば、図１１の行１１０４の列１に関連して行１４０４の列１を検討してみる。ベクトル・エッジの置換、動作の結果、ここでは制約ノードＣ１，１はエッジ（１，１）とは対照的にエッジ（２，１）に連結され、制約ノードＣ２，１はエッジ（２，１）とは対照的にエッジ（３，１）に連結され、また制約ノードＣ３，１はエッジ（３，１）とは対照的にエッジ（１，１）に連結されていることに留意されたい。
【０１２３】
投影されたグラフのＺ個の並行処理のコピーを復号するために復号器９００をどのようにベクトル化するかについて上記に説明した。ローテーションを実施するためにメッセージ経路にスイッチを導入することによって、図１３に記載されたＬＤＰＣ符号が復号される。
【０１２４】
図１５は本発明の様々な特徴を組入れた復号器を示している。復号器１５００はローテーションによって復号器６００を完全にベクトル化する。図でＺ＝４を示すが、本例はＺ＝３であり、一般に任意のＺ＞１を有することができるが、実際には整数ｋの場合の２ｋの形式のＺの値の方がより好適である場合が多い。復号器６００との類似性は明らかである。特に、復号器制御モジュール１５０２とノード度メモリ１５１０は復号器９００内のそれぞれの対応部品９０２および９１０と同一、または類似の機能を果たす。例えば、図１３および１４に規定されたＬＤＰＣ符号を復号するには、これらの構成部品の動作は、グラフ６００の例を復号する場合の復号器９００の対応部品と全く同一である。エッジ・メッセージ・メモリ１５０６とハード決定メモリ１５１２は復号器９００内の対応部品９０６および９１２のベクトル化されたバージョンである。復号器９００ではメモリは単一のユニット（Ｋビット・メッセージまたはビット）を記憶するのに対して、復号器１５００内の対応するメモリはセット、すなわちベクトル、メッセージを記憶し、その結果Ｚ×Ｋビットのメッセージが記憶される。これらのベクトルはＳＩＭＤ命令を用いて単一ユニットとして書き込まれ、または読み出される。このように、メッセージ配列モジュール１５０４からこれらのモジュールに送られるメッセージ識別子は、復号器９００の識別子と同じであるか類似している。メッセージ配列モジュール１５０４は復号器９００内に対応部品９０４が有している役割を超えて、例えばローテーションのような置換情報を記憶し、かつ供給するという付加的な役割を有している。復号例６００で復号器９００はそのメッセージ配列モジュール９０４にエッジ・シーケンス（１、４、７、２、９、１１、３、５、１２、６、８、１０）を記憶したことを想起されたい。復号器１５００を使用して図１３および１４の符号を復号するものとする。メッセージ配列モジュール１５０４は、制約ノード処理中にメッセージ・ベクトルにアクセスするため、上記と同じシーケンスを記憶し、さらに、ベクトル・メッセージの同じシーケンスに関連するローテーションを記述するシーケンス（２、２、３、３、１、１、１、３、２、１、２、３）をも記憶するであろう。このシーケンスは、メッセージ配列モジュール１５０４によって使用されることで、スイッチ１５２０および１５２２がベクトル・メッセージとベクトル・ハード決定ビットをそれぞれ循環させるようにする循環信号(rot signal)を発生する基礎の役割を果たす。（ハード決定ビットは可変ノード処理モードの間だけ供給されることに留意されたい。）ベクトル・パリティ・チェック確認器１５４１は復号器９００内の対応部品９１４のベクトル・バージョンである。出力収束信号は以前と同様にスカラであることに留意されたい。出力バッファ１５１６はバッファ９１６と同様の目的を果たすが、出力データはベクトルとして書き込まれる。ベクトル・ノード・プロセッサ１５０８は例えば、各々が９０８の場合のように並列であるＺ個のノード・プロセッサである。これらのノードは復号器制御モジュール１５０２からのノード度信号(deg signal)およびＣ／Ｖ制御信号を共用するであろう。
【０１２５】
ソフト復号器またはハード復号器の決定を出力する能力を促進するため、可変処理ユニットによって作成されたソフト決定はバッファ１５１６のソフト決定入力に供給される。このようにして、復号が完了する前の任意の時点で、ソフト決定をバッファ１５１６の出力から得ることができる。
【０１２６】
更に、復号器１５００が図１３および１４の例を復号するためにどのように機能するかを検討する。最初は、エッジ・メッセージ・メモリ１５０６に０がポピュレートされる。復号器制御モジュール１５０２は先ず可変ノード処理モードに切り換えられる。エッジ・メッセージ・メモリ１５０６のベクトル（この時点では全て０）が順次読み出され、可変ノード処理のためにベクトル・ノード・プロセッサ１５０８に送られる。ベクトル・ノード・プロセッサ１５０８は次に、可変ノードからの各エッジに沿って受信された値だけを出力する。このことを示す前記の最初のメッセージを表記するのにｙが使用される。このように、送出ベクトルはｉ＝１，．．．，１２の場合、昇順で（ｙ１，ｉ、ｙ２，ｉ、ｙ３，ｉ）となろう。循環信号はスイッチング回路１５２０、１５２２によって行われるメッセージの並べ替えを制御するために利用される。メッセージ配列モジュール１５０４からの循環信号によってベクトル内のメッセージは循環されて、以下のような処理されたベクトルが生成される。（ｙ２，１、ｙ３，１、ｙ１，１）、（ｙ３，２、ｙ１，２、ｙ２，２）、（ｙ１，３、ｙ２，３、ｙ３，３）、（ｙ２，４、ｙ３，４、ｙ１，４）、（ｙ３，５、ｙ１，５、ｙ２，５）、（ｙ１，６、ｙ２，６、ｙ３，６）、（ｙ３，７、ｙ１，７、ｙ２，７）、（ｙ２，８、ｙ３，８、ｙ１，８）、（ｙ１，９、ｙ２，９、ｙ３，９）、（ｙ３，１０、ｙ１，１０、ｙ２，１０）、（ｙ１，１１、ｙ２，１１、ｙ３，１１）、（ｙ２，１２、ｙ３，１２、ｙ１，１２）。処理されたベクトルが表示された順序で一旦エッジ・メモリ１５０６に書き込まれると、復号器制御モジュール１５０２は制約モードに切り換わる。次に、記憶されたベクトル・メッセージは（１、４、７、２、９、１１、３、５、１２、６、８、１０）の順に読み出される。このように、これらは以下の順でベクトル・ノード・プロセッサ１５０８へと提示される。（ｙ２，１、ｙ３，１、ｙ１，１）、（ｙ２，４、ｙ３，４、ｙ１，４）、（ｙ３，７、ｙ１，７、ｙ２，７）、（ｙ３，２、ｙ１，２、ｙ２，２）、（ｙ１，９、ｙ２，９、ｙ３，９）、（ｙ１，１１、ｙ２，１１、ｙ３，１１）、（ｙ１，３、ｙ２，３、ｙ３，３）、（ｙ３，５、ｙ１，５、ｙ２，５）、（ｙ２，１２、ｙ３，１２、ｙ１，１２）、（ｙ１，６、ｙ２，６、ｙ３，６）、（ｙ２，８、ｙ３，８、ｙ１，８）、（ｙ３，１０、ｙ１，１０、ｙ２，１０）。ベクトル・ノード・プロセッサ１５０８は並列の３つの（Ｚ＝３）ノード・プロセッサとして実施される。各メッセージ・ベクトル（メッセージのセット）の最初の要素（メッセージ）は第１のノード・プロセッサに送られ、第２のメッセージは第２のプロセッサに送られ、第３のメッセージは第３のプロセッサにそれぞれ送られる。処理されている現在のノード度を示すノード度信号はノード度メモリ１５１０によってベクトル・ノード・プロセッサ１５０８の３つの並列プロセッサへと供給される。この時点で、ノード度信号は制約が（全て）ノード度３であり、したがって最初のプロセッサは最初の制約ノードではｙ２，１、ｙ２，４、およびｙ３，７を処理し、または第２の制約ノードではｙ３，２、ｙ１，９、およびｙ１，１１を処理することを示している。同様に、第２のプロセッサは最初の制約ノードではｙ３，１、ｙ３，４、およびｙ１，７を処理し、または第２の制約ノードではｙ１，２、ｙ２，９、およびｙ２，１１を処理するであろう。
【０１２７】
ｍｉ，ｊが着信メッセージｙｉ，ｊに対応する発信メッセージを示すものとする。ベクトルがベクトル・ノード・プロセッサ１５０８から発しているので、スイッチ１５２０への循環信号によってベクトルが並べ替えられ、それによって以前のローテーションが逆になる。このため、それらはｊ＝１、４、７、２、９、１１、３、５、１２、６、８、１０の順序で（ｍ１，ｊ、ｍ２，ｊ、ｍ３，ｊ）としてエッジ・メモリに到達する。メッセージは読み出されたメッセージ識別子の順序に従ってメッセージへと再び書き込まれ、したがって書き込み後はｊ＝１，．．．，１２の順序で（ｍ１，ｊ、ｍ２，ｊ、ｍ３，ｊ）としてメモリ内に出現する。ここでメッセージ配列モジュール１５０４が復号器制御モジュール１５０２によって供給されたＣ／Ｖ信号に応答して可変ノード処理モードへと切り換わる。次にメッセージ・ベクトルはｊ＝１，．．．，１２の順序で読み出され、可変ノード処理のためにベクトル・ノード・プロセッサ１５０８に送られる。これをもって反復が完了する。
【０１２８】
可変ノード処理中、ベクトル・ノード・プロセッサ１５０８は、出力バッファ１５１６に記憶されているソフト復号されたベクトルをも出力する。これはスイッチング回路１５２２に供給されるハード決定をも出力する。１ビットのハード決定のベクトルには、対応する時間にメッセージ・ベクトルと同じローテーション動作が行われる。スイッチング回路１５２２によって生成された循環ハード決定ベクトルは次に、ハード決定メモリ１５１２内に配列され、そこに記憶される。メッセージ・ベクトルに適用されたものと同じローテーションが適用される結果、ハード決定は制約ノード処理中にベクトル・メッセージが読み出される順序と同じ順序で読み出されてもよい。制約ノード処理中、ハード決定は、並列処理でＺのパリティ・チェックを行うベクトル・パリティ・チェック確認器１５１４に送られる。全てのパリティ・チェックが満たされると、収束信号ＣＯＮが発生され、発信される。復号の成功を示す収束信号の受信に応答して、復号器制御モジュール１５０２は復号プロセスを停止する。
【０１２９】
復号器１５００にはそれぞれが本発明を実施する多くの変形があることは明らかであろう。例えば、代りにスイッチ１５２０をエッジ・メッセージ・メモリ１５０６とベクトル・ノード・プロセッサ１５０８の間のデータ経路に沿って配置することも可能であろう。同様に、代りにスイッチ１５２２をハード決定メモリ１５１２とベクトル・パリティ・チェック確認器１５１４の間のデータ経路に沿って配置することも可能であろう。このような置き換えには循環信号のタイミングを適切に調整することも含まれる。ハード決定メモリ１５１２、ベクトル・パリティ・チェック確認器１５１４、および付随するデータ経路は必ずしも使用する必要はなく、固定回数の反復を行う復号器の実施形態では省かれ、したがって収束の検知は必要ない。本発明にかんがみて更に多くの変形が当業者には明らかであろう。
【０１３０】
図１６は本発明の別の実施形態に基づいて実施された復号器１６００を示している。復号器１６００は復号器１５００の要素と同一の、または同類の多くの要素を含んでいる。したがって簡潔にするため、このような要素は図１５で用いられたものと同じ参照番号で識別され、再び詳細には説明しない。復号器１６００は例えばメッセージ更新動作のような可変ノード処理動作と制約ノード処理動作の双方を同時に、例えば同時にかつ独立して実行することができる。可変ノード処理と制約ノード処理の反復間で切り換えられる態様なので並置復号器と表記してもよい。図１５の復号器の実施形態はこれとは対照的に、復号器１６００は可変ノードと制約ノードの処理動作を独立して、例えば同時に行うことができるので非同期反復復号器と表記することができる。
【０１３１】
復号器回路１６００は図１６に示すように互いに結合された、復号器制御モジュール１６０２と、メッセージ配列モジュール１６０４と、第１スイッチング回路１６２１と、Ｖ２Ｃエッジ・メッセージ・メモリ１６０６と、制約ノード・ベクトル・プロセッサ（例えば並列のＺ個の制約ノード・プロセッサ）１６０９と、第２スイッチング回路１６２０と、Ｃ２Ｖエッジ・メッセージ・メモリ１６０７と、可変ノード・ベクトル・プロセッサ１６０８（例えば並列のＺ個の可変ノード・プロセッサ）と、ハード決定メモリ１６１２と、第３スイッチ回路１６２２とを含んでいる。
【０１３２】
制約ノード・ベクトル・プロセッサ１６０９および可変ノード・プロセッサ１６０８のそれぞれを実施するために、Ｚ個を並列で使用可能な個々の制約ノード・プロセッサと個々の可変ノード・プロセッサの様々な実施形態は、２００１年１０月１０日に出願され、本明細書に参考文献として明確に組込まれている名称「パリティ・チェック・デコーダ用のノード・プロセッサ」(Node Processors For Use in Parity Check Decoders)の米国特許仮出願第６０／３２８，４６９号に詳細に記載されている。本特許出願の発明者はこの組込まれている仮特許出願に記名された発明者でもある。
【０１３３】
図１６の実施形態で制約メッセージと可変メッセージの独立した、および／または並行した更新を支援するため、別個のエッジ・メッセージ・メモリ１６０６、１６０７、およびスイッチング回路１６２０、１６２１が使用され、制約ノード処理動作と可変ノード処理動作の双方が支援される。図１５の実施形態と同様に、メッセージ・メモリ１６０６、１６０７は各々Ｌ個（Ｚ×Ｋビット）のベクトル・メッセージを記憶することができる。例えばＺ個のＫビット・メッセージの列のようなメモリ１６０６、１６０７内の各ベクトル・メッセージは単一の読み出しまたは書き込み動作によって読み出し、または書き込みが可能である。
【０１３４】
Ｖ２Ｃエッジ・メッセージ・メモリ１６０６がＶ２Ｃメッセージを記憶するために用いられ、したがって可変ノード・ベクトル・プロセッサ１６０８からデータを受けるスイッチング回路１６２１の出力と結合された書き込み入力を有する。Ｃ２Ｖメッセージ・メモリ１６０７はＣ２Ｖエッジ・メッセージを記憶するために使用され、したがって制約ノード・ベクトル・プロセッサ１６０９の出力に結合された書き込み入力を有する。
【０１３５】
スイッチ１６２０および１６２１は、可変ノード・ベクトル・プロセッサ１６０８をＶ２Ｃエッジ・メッセージ・メモリの入力と、Ｃ２Ｖエッジ・メッセージ・メモリの出力とにそれぞれ結合するために使用される。特定の一実施形態では、メッセージ・ベクトルはベクトル制約ソケット順に記憶される。メッセージ・ベクトルはＣ２Ｖエッジ・メッセージ・メモリ１６０７に書き込まれ、ベクトル制約ソケットの順に、すなわち直線的にＶ２Ｃエッジ・メッセージ・メモリ１６０６から読み出されるので、外部制御は必要ない（復号器制御モジュール１６０２から出力されるエッジ索引はメッセージ配列モジュール１６０４を経て不変のままにその制約エッジ索引出力へと送られる）。メッセージ・ベクトルはＣ２Ｖエッジ・メッセージ・メモリ１６０７から読み出され、ベクトル可変ソケットの順にＶ２Ｃエッジ・メッセージ・メモリ１６０６へと書き込まれる。メッセージ配列モジュール１６０４はその配列を示す可変エッジ索引信号を発生する。この信号はＣ２Ｖエッジ・メッセージ・メモリ１６０７の読み出しを制御し、遅延された後、Ｖ２Ｃエッジ・メッセージ・メモリ１６０６に送られることに留意されたい。遅延はスイッチ１６２０および１６２１、およびベクトル可変ノード・プロセッサ１６０８によって行われる処理に必要な時間を考慮に入れたものである。この遅延は図１６に示すように、可変ノード度信号によって処理されるノード度に応じたものでよい。
【０１３６】
可変的な遅延によるパイプライン・ストールの処理を回避するため、制約ノードと可変ノードの双方は、同じノード度のノードが連続的に処理されるように配列される。ノード・グループをノード度によって単調に分別することによって、例えばノード度を増減することによって異なるノードを有するノード・グループの境界に出現するパイプライン・ストールを更に低減することが達成可能である。実施を簡単にするため、実施形態９００、１５００および１６００のノード度は増分するものと想定されている。
【０１３７】
図１６に示された特定の実施形態では、ベクトルはベクトル制約ノード・ローテーション順に記憶される。スイッチ１６２０は、各々のＣ２Ｖベクトル・メッセージが可変ノード・ベクトル・プロセッサ１６０８へと進行すると、各ベクトル内のメッセージを可変ローテーションへと循環させ、次にスイッチ１６２１は同じベクトル・エッジに対応する発信Ｖ２Ｃベクトル・メッセージに逆ローテーションを適用する。スイッチ１６２０に送られた循環信号は、ベクトル制約ノード・プロセッサ内の処理時間に整合する遅延の後に、ローテーション逆転回路１６２４を介してスイッチ１６２１に送られる。この遅延はノード度メモリ１６１０によって出力された制約ノード度信号によって示されるような、制約ノード度によって左右されることがある。
【０１３８】
復号器１６００は復号器制御モジュール１６０２を含んでいる。復号器制御モジュールは前述の制御モジュール１５０２と同様に動作する。しかし１６０２では、Ｃ／Ｖ制御信号は生成されない。再出発の前に、ベクトル・エッジのセット全てを循環するカウンタによってエッジ索引作成機能を提供することができる。
【０１３９】
ソフト決定の出力に加えて、ベクトルＶ２Ｃメッセージが作成されるごとに、ベトクル可変ノード・プロセッサ１６０８内のＺ個の可変ノード処理ユニットの各々によって、エッジ当たり１つずつハード決定が作成される。ベクトル・メッセージはＶ２Ｃエッジ・メッセージ・メモリ１６０６へと書き込まれる一方、スイッチ１６２２によって循環された後で、Ｚ×１ビットのハード決定出力がハード決定出力メモリ１６１２へと書き込まれる。スイッチ１６２２とハード決定メモリ１６１２はスイッチ１６２１、およびＶ２Ｃエッジ・メッセージ・メモリ１６０６のそれぞれと同じ制御信号の下で動作する。
【０１４０】
結果として生じたＺ×１の循環されたベクトルは、並列に接続されたＺ個のパリティ・チェック確認器を含むベクトル・パリティ・チェック確認器１６１４に送られる。確認器１６１４は、パリティ・チェックが満たされているか否かを判定し、全てが満たされている場合は収束信号が発生され、復号器制御モジュールに送られる。収束を示す信号の受信に応答して、復号器制御モジュールは受信された符号語の復号を停止する。実施形態１６００では、符号語が出力バッファに書き込まれた後の１回の反復として収束検知信号を利用できる。何故ならば、反復Ｎからのデータの制約の確認は、反復Ｎ＋１の間に行われ、また収束信号は反復Ｎ＋１が完了した後で利用できるからである。
【０１４１】
異なる収束検知回路を使用している復号器１６００として、図１７は復号器１７００によって例示されるような実施形態を示しており、制約の確認はＺ×Ｋビットの出力値Ｘが出力バッファ１７１６に書き込まれると“実行中に”達成される。この場合、メモリ・ブロック１７１２は、ベクトル制約が可変ノード・プロセッサ１７０８から出力されたハード決定によって更新されると、制約状態を記録する。各々の制約状態記憶域は符号語のパリティ・チェック制約に対応する。いずれかの制約状態記憶域の最後の更新で、これらのパリティ・チェックの値が確認される。反復Ｎの間の全ての確認が満たされると、反復Ｎの直後にベクトル・パリティ・チェック確認器１７１４によって収束信号が発生され、出力される。これは復号器制御モジュール１７０２に対して、出力バッファ１７１６内のデータが妥当であることを承認するものである。図１７の実施形態では、メッセージ配列モジュール１７０４は、（エッジ索引とは対照的に）制約ノード索引を規定する、図１６の実施形態では作成されなかった追加の信号を発生する。制約ノード索引は現行のＶ２Ｃメッセージの制約ノードの宛先を特定する。このフィールドはそれが供給される制約状態メモリ１７１２への索引の役割を果たす。
【０１４２】
図１６および図１７の実施形態は図１５の実施形態よりもやや多い回路を必要とするものの、双方のベクトル・ノード・プロセッサが各々の反復処理中にフルに活用されるので、ベクトル制約および可変ノード・プロセッサ１６０９／１７０９、１６０８／１７０８をより効率的に利用できるという利点を有している。加えて、制約および可変ノード処理は並行して、例えば同時に行われるので、復号時間は図１５の実施形態と比較して短縮される。
【０１４３】
上記の復号方法によって、ＳＩＭＤ動作を支援できるソフトウェアおよび汎用コンピュータを使用して、例えばＬＤＰＣ復号のようなメッセージ伝送復号を行うことができる。このような実施形態では、１つ又はそれ以上の並列プロセッサはベクトル処理ユニットの役をし、又は単一プロセッサ内のハードウエアは並列の多重ベクトル処理動作を実行するのに使用してもよい。このような実施形態では、エッジ・メモリ、置換マップ、およびノード当たりのメッセージ数に関する情報を全て共通のメモリ、例えばコンピュータの主記憶装置に記憶することができる。メッセージ伝送制御論理、および復号器制御論理をコンピュータの処理ユニットで実行されるソフトウェア・ルーチンとして実施できる。加えて、ソフトウェアおよび単数または複数のＳＩＭＤ処理命令を使用してスイッチング・デバイスを実施できる。
【０１４４】
上記のＬＤＰＣ復号方法によってフィールド・プログラマブル・ゲート・アレイ（ＦＰＧＡ）のような種々のハードウェア・プラットフォームで、またはアプリケーション特有集積回路でＬＤＰＣ復号を実施できる。本発明は特に、簡単な並列処理を明らかに活用できるような設定で有用である。
【０１４５】
本発明の復号の方法および装置のその他の多くの変形は、本発明の上記の説明にかんがみて当業者には明らかであろう。このような変形は本発明の範囲内にあるものと見なされる。
【図面の簡単な説明】
【０１４６】
【図１】長さが１０の規則的ＬＤＰＣ符号の例の二部構造グラフ表現を示す。
【図２】図１に図形的に示した符号のマトリクス表現である。
【図３】データの符号化、伝送、および復号を示す。
【図４】不規則ＬＤＰＣ符号の例の二部構造グラフ表現である。
【図５】図５ａから５ｄの組合わせからなる図５は、図４に示されたＬＤＰＣ符号に従ったＬＤＰＣ復号動作の一部として実行されるステップを示す。
【図６】本発明による実施例を示すために極めて大きいＬＤＰＣ符号の基礎として使用される小さいＬＤＰＣ符号のグラフ表現である。
【図７】図６に図形的に示した小さいＬＤＰＣ符号のパリティ・チェック・マトリクス表現を示す。
【図８】図６に示した符号のエッジをいかにして可変ノード側から順に配列できるか、例えば置換できるかを示し、また同じエッジがいかにして制約ノード側から現れるかを示す。
【図９】直列のＬＤＰＣ復号動作を実行するシステムを示す。
【図１０】図６に示した小さいＬＤＰＣグラフの３つのコピーを作成する効果を図形的に示す。
【図１１】図１０に示したＬＤＰＣグラフのパリティ・チェック・マトリクス表現を示す。
【図１２】図１１に示した符号のエッジをいかにして可変ノード側から順に配列、例えば置換できるか、および同じエッジがいかにして制約ノード側から現れるかを示す。
【図１３】図１１に示した３×３単位行列を本発明の１実施例に基づいて周期的置換マトリクスと置き換える効果を示す。
【図１４】図１３に示した符号のエッジを本発明に基づいていかにして可変ノード側から順に列挙できるか、また周期的置換がなされた後に、同じエッジがいかにして制約ノード側から現れるかを示す。
【図１５】図９の復号器をベクトル化する本発明に基づいて実施されたＬＤＰＣ復号器を示す。
【図１６】本発明に基づいて実施された他のＬＤＰＣ復号器を示す。
【図１７】本発明に基づいて実施された他のＬＤＰＣ復号器を示す。
【符号の説明】
【０１４７】
９００  ＬＤＰＣ復号器
９０２  復号器制御モジュール
９０４  メッセージ配列モジュール（ソケット置換メモリ）
９０６  エッジ・メモリ
９０８  ノード・プロセッサ
９１０  ノード度メモリ
９１２  ハード決定メモリ
９１４  パリティ・チェック確認器
９１６  出力バッファ
【図３】
2004531972.tif 000007
【図９】
2004531972.tif 000008
【図１５】
2004531972.tif 000009
【図１６】
2004531972.tif 000010
【図１７】
2004531972.tif 000011
【国際公開パンフレット】
2004531972.tif 000012
2004531972.tif 000013
2004531972.tif 000014
2004531972.tif 000015
2004531972.tif 000016
2004531972.tif 000017
2004531972.tif 000018
2004531972.tif 000019
2004531972.tif 000020
2004531972.tif 000021
2004531972.tif 000022
2004531972.tif 000023
2004531972.tif 000024
2004531972.tif 000025
2004531972.tif 000026
2004531972.tif 000027
2004531972.tif 000028
2004531972.tif 000029
2004531972.tif 000030
2004531972.tif 000031
2004531972.tif 000032
2004531972.tif 000033
2004531972.tif 000034
2004531972.tif 000035
2004531972.tif 000036
2004531972.tif 000037
2004531972.tif 000038
2004531972.tif 000039
2004531972.tif 000040
2004531972.tif 000041
2004531972.tif 000042
2004531972.tif 000043
2004531972.tif 000044
2004531972.tif 000045
2004531972.tif 000046
2004531972.tif 000047
2004531972.tif 000048
2004531972.tif 000049
2004531972.tif 000050
2004531972.tif 000051
2004531972.tif 000052
2004531972.tif 000053
2004531972.tif 000054
2004531972.tif 000055
2004531972.tif 000056
2004531972.tif 000057
2004531972.tif 000058
2004531972.tif 000059
2004531972.tif 000060
2004531972.tif 000061
2004531972.tif 000062
2004531972.tif 000063
2004531972.tif 000064
2004531972.tif 000065
2004531972.tif 000066
2004531972.tif 000067
2004531972.tif 000068
2004531972.tif 000069
2004531972.tif 000070
2004531972.tif 000071
2004531972.tif 000072
2004531972.tif 000073
2004531972.tif 000074
【国際調査報告】
2004531972.tif 000075