(57)【特許請求の範囲】
【請求項１】
（ａ）シンボルデータシーケンスをチャンネル（１１５）から受信（１５）し、前記シンボルデータシーケンスは、送信機（１１０）によってチャンネル（１１５）上に送出された第２のシンボルデータシーケンスのチャンネルの歪曲された部分を有し、前記第２のシンボルデータシーケンスは、関連情報ビットに基づいて前記送信機（１１０）によって生成され、
（ｂ）２つ以上のプロセッサからなる第１の組は、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作し、受信した前記シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応し、第１のトレリスは、前記受信したシンボルデータシーケンスにおける冗長性を示し、前記動作が関連情報ビットに対する軟推定を生成し、この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成し、さらに、
前記送信機は元の情報ビットの畳込み符号化によって符号化ビットを得て、その符号化ビットをインターリーブすることによって関連情報ビットを生成し、
前記（ｂ）は、２つ以上のプロセッサからなる第１の組が符号化ビットに対する軟推定をインターリーブしたものの２つ以上の各重複サブシーケンスを用いて前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作することを含み、
前記方法はさらに（ｃ）２つ以上のプロセッサからなる第２の組は、関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作し、デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応し、前記第２のトレリスは畳込み符号化に対応する構造を有し、前記デインターリーブしたものの２つ以上の重複サブシーケンスに対する前記並行動作は符号化ビットに対する軟推定を生成することを特徴とする受信機（１２０）を動作させる方法。
【請求項２】
前記方法は、さらに、複数の受信シンボルデータシーケンスのそれぞれに対して前記（ａ）および（ｂ）を実行し、前記受信したシンボルデータシーケンスの少なくとも１つに対して、前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整することを含む請求項１記載の方法。
【請求項３】
前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスの数は、前記受信したシンボルデータシーケンスの長さに基づいて行われる請求項２記載の方法。
【請求項４】
前記受信したシンボルデータシーケンスの少なくとも１つに対して、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項２記載の方法。
【請求項５】
請求項１記載の方法において、前記第２のシンボルデータシーケンスは関連情報ビットの畳込み符号化に基づいて生成され、第１のトレリスは畳込み符号化に基づく構造を有し、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる第１の組が並行して実行する前記動作は、受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ復号化を実現することを含む方法。
【請求項６】
請求項１記載の方法において、前記第１のトレリスは、前記シンボルデータシーケンスと第２のシンボルデータシーケンスとの所与の線形関係に基づいた構造を有し、前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる前記第１の組が並行して実行する前記の動作は、前記受信したシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復調処理を並行して実行し、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ等化を実現することを含む方法。
【請求項７】
（ｄ）のステップとして前記ステップ（ｂ）および（ｃ）を複数回反復することをさらに含む請求項１記載の方法。
【請求項８】
請求項７記載の方法は、前記２つ以上のプロセッサからなる第２の組が、前記関連情報ビットに対する軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作して、元の情報ビットに対する軟推定を生成することを更に含む方法。
【請求項９】
前記（ｂ）は復調処理を表し、前記（ｃ）は復号化処理を表し、前記（ｄ）は受信した前記シンボルデータシーケンスのターボ等化を実現する請求項７記載の方法。
【請求項１０】
前記（ｂ）は第１の復号化処理を表し、前記（ｃ）は第２の復号化処理を表し、前記（ｄ）は受信した前記シンボルデータシーケンスのターボ復号化を実現する請求項７記載の方法。
【請求項１１】
前記（ｂ）および（ｃ）の反復は、所定の閾値を超える前記符号化ビットの軟推定および関連情報ビットの軟推定に基づいて停止される請求項７記載の方法。
【請求項１２】
関連情報ビットの軟推定の前記デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項７記載の方法。
【請求項１３】
請求項１〜１２記載の方法を実施するシステム。
【請求項１４】
請求項１〜１２記載の方法を実行する指示を有することを特徴とするコンピュータプログラム記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に通信分野に関し、より詳細には並列処理環境における復調や復号化、等化のためのトレリスベースの方法を実行するシステムおよび方法に関する。
【背景技術】
【０００２】
トレリスベースの方法は、ビタビ復号化、ビタビ等化、ターボ復号化およびターボ等化などの方法を含む。トレリスベースの方法は計算集約型である。そのため、この問題を解決する機構の必要性が高まっている。特に、トレリスベースの方法の実行可能性を最大限とする機構の必要性が高まっている。さらに、受信機能における柔軟性を高めるため、ソフトウェア上で信号処理を実行可能な受信システムおよび無線システムへの一般的な必要性も高まっている。
【０００３】
ソフトウェア無線（ＳＤＲ）システムは、ハードウェア上で通常実現されてきたコンポーネント（例えば、ミキサ、フィルタ、増幅器、変調器／復調器、検出器など）をコンピュータシステム上でソフトウェアを用いて実現している無線通信システムである。基本的なＳＤＲは無線周波数（ＲＦ）フロントエンドからなり、アナログ−デジタル変換器を介してコンピュータシステムに接続される。大部分の信号処理は、専用のハードウェアを使用するのではなく、コンピュータシステムによって実行される。このようなソフトウェアをベースとした設計にしたがって様々なソフトウェアを実行することによって、様々な形式の無線プロトコル（波形と呼ばれることもある）を送受信可能な無線を実現している。
【０００４】
ソフトウェア無線を実現するシステムおよび方法の改善が望まれる。
【０００５】
ターボ等化において、送信機は、情報源からビット｛ａk｝列を受信する。送信機はビットストリームを符号化（例えば、エラー修正コードを用いる）して、符号化ビットストリームを生成する。また、送信機は、定義した順列にしたがって符号化ビットストリームの各データブロックをインターリーブして、インターリーブビットストリームを生成できる。送信機は、インターリーブビットストリームを、シンボルセット（すなわちコンステレーション）から取り出したシンボル｛ｘk｝のシーケンスに対応づける。送信機は、シンボルシーケンスに基づいてキャリア信号を変調し、変調キャリアを生成する。送信機は、変調キャリアをチャンネル上に送出する。受信機は、ノイズを含む送信信号である信号をピックアップ（または受信）する。受信機は受信信号を復調して、シンボル｛ｙk｝のシーケンスを得る。その後、受信機はターボ等化方法を用いてシンボルシーケンス｛ｙk｝を処理して、元のビットストリーム｛ａk｝のビットを推定する。上述したように、高い確率でターボ等化を実行できるシステムおよび方法が必要である。
【発明の概要】
【０００６】
１組の実施形態において、受信シンボルデータシーケンスＹから情報を再生する方法は、以下の動作を含む。シンボルデータシーケンスＹは、チャンネルから受信される。このシンボルデータシーケンスＹは、送信機によってチャンネル上に送出されたシンボルデータシーケンスＸに対応する。ここで、シンボルデータシーケンスＸは、関連情報ビットに基づいて送信機によって生成される。２つ以上のプロセッサからなる第１の組は、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して並行して動作する。この場合、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応する。第１のトレリスは、シンボルデータシーケンスにおける冗長性を示す。この並行動作によって、関連情報ビットに対する軟推定が生成される。この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成できる。
【０００７】
一実施形態において、前記方法は、ビタビ復号化を実行する。別の実施形態において、前記方法は、ビタビ等化を実行する。さらに別の実施形態において、前記方法はターボ復号化処理を実行するためのさらなる動作を含む。さらに別の実施形態において、前記方法は、ターボ等化処理を実行するためのさらなる動作を含む。
【０００８】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、フィードバックデータシーケンスの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して並行して動作し、２つ以上のプロセッサからなる第２の組は、関連情報ビットの軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作する。デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応する。第２のトレリスは、畳込み符号化に対応する構造を有する。（畳込み符号化は、送信機によって実行される。畳込み符号化は元の情報ビットに対して実行されて符号化ビットを生成する。この符号化ビットは、その後インターリーブされて、関連情報ビットが生成される）。デインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作することによって、符号化ビットに対する軟推定が生成される。フィードバックデータシーケンスは、符号化ビットに対する軟推定をインターリーブしたものである。前記方法は、例えば終了条件が満たされるまで、第１の組のプロセッサの処理と、第２の組のプロセッサの処理とを交互に繰り返すことを含んでもよい。
【０００９】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、プロセッサ列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する。同様に、２つ以上のプロセッサからなる第２の組は、プロセッサ列から選択される。
【００１０】
１組の実施形態において、システムは、チャンネルから受信したシンボルデータシーケンスＹを処理するために、以下のように構成されてもよい。この場合、シンボルデータシーケンスＹは、送信機によってチャンネル上に送出されたシンボルデータシーケンスＸに対応する。ここで、シンボルデータシーケンスＸは、関連情報ビットに基づいて送信機によって生成される。前記システムは、それぞれ第１のプログラムコードで構成された２つ以上のプロセッサからなる第１の組を含んでもよい。この場合、第１のプログラムコードは、第１の組のプロセッサによって実行されると、第１の組のプロセッサが、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して並行して動作するようにする（ａ）。シンボルデータシーケンスＹの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応する。第１のトレリスは、シンボルデータシーケンスＹにおける冗長性を示す。この並行動作によって、関連情報ビットに対する軟推定が生成される。この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成できる。
【００１１】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、プロセッサ列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する。
【００１２】
いくつかの実施形態において、前記システムはビタビ復号化またはビタビ等化を実行するように構成されてもよい。他の実施形態において、前記システムは、ターボ復号化またはターボ等化を実行するように拡張されてもよい。
【００１３】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサによって実行されると、複数の受信シンボルデータシーケンスのそれぞれに対して動作を実行させる（ａ）。
【００１４】
ターボの実施形態において、送信機は、元の情報ビットの畳込み符号化を行って符号化ビットを生成し、符号化ビットのインターリーブによって関連情報ビットを生成する。さらに、動作（ａ）は、フィードバックデータシーケンスの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作する２つ以上からなるプロセッサの第１の組を含み、前記システムは、第２のプログラムコードで構成される２つ以上のプロセッサからなる第２の組をさらに含む。第２のプログラムコードは、第２の組のプロセッサによって実行されると、第２の組のプロセッサが、関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作するようにする（ｂ）。この場合、デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応する。第２のトレリスは、畳込み符号化に対応する構造を有する。デインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作することによって、符号化ビットに対する軟推定が生成される。フィードバックデータシーケンスは、符号化ビットに対する軟推定をインターリーブしたものである。
【００１５】
２つ以上のプロセッサからなる第１の組と２つ以上のプロセッサからなる第２の組とは、（ａ）および（ｂ）を複数回、交互にそれぞれ実行するようにプログラムされている。
【００１６】
ターボの実施形態において、前記システムは、以下の１つ以上を実行するように構成されてもよい。遡及デパンクチャ（すなわち、第２の組のプロセッサによってあらかじめ演算された結果を用いたデパンクチャ）を行う、反復回数の増加に伴って、内部情報を、２つのプロセッサ組間でやりとりされる軟推定へ段階的に混合する、反復回数やＳ／Ｎ比の関数の増加に伴って、近接サブシーケンス間の重複量を減少させる、およびトレリス上でのフォワードパスまたはバックワードパスで零ベクトルが発生した場合は常に零ベクトル置換を行う。
【００１７】
１組の実施形態において、ターボ等化を実行する方法は以下を含んでもよい。（ａ）チャンネルからシンボルデータシーケンスＹを受信する。この場合、シンボルデータシーケンスＹは、チャンネル上に送出されたシンボルデータシーケンスＸに対応し、シンボルデータシーケンスＸは、元の情報ビットに基づいて生成される。（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバック情報をインターリーブしたものの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに並行して復調処理を実行して、フィードフォワード情報を生成する。（ｃ）２つ以上のプロセッサからなる第２の組が、フィードフォワード情報をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して復号化処理を実行して、フィードバック情報を生成する。（ｄ）（ｂ）および（ｃ）を含む処理の組を繰り返す。（ｅ）２つ以上のプロセッサからなる第３の組が並行して動作し、フィードフォワード情報のデインターリーブしたものの２つ以上の重複サブシーケンスから元の情報ビットに対する軟推定を生成する。この軟推定は、元の情報ビットに対応する受信メッセージを形成するのに使用可能である。
【００１８】
いくつかの実施形態において、第３の組のプロセッサは、第２の組のプロセッサと同一である（または重複する）。
【００１９】
いくつかの実施形態において、第１の組のプロセッサは、第２の組のプロセッサと同一である（または重複する）。
【００２０】
１組の実施形態において、送信情報を受信する方法は以下を含んでもよい。（ａ）チャンネルを介してシンボルデータシーケンスＹを受信する。この場合、シンボルデータシーケンスＹは、チャンネル上に送出されたシンボルデータシーケンスＸに対応し、シンボルデータシーケンスＸは、元の情報ビットに基づいて生成される。（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して並行して復調処理を実行して、フィードフォワード情報の２つ以上の対応ブロックを生成する。（ｃ）１つ以上のプロセッサからなる第２の組がフィードフォワード情報の２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデインターリーブを実行して、修正データシーケンスを生成する。（ｄ）２つ以上のプロセッサからなる第３の組が、修正データシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成する。（ｅ）１つ以上のプロセッサからなる第４の組が、フィードバック情報の２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブを実行して、フィードバックデータシーケンスを生成する。（ｆ）（ｂ）、（ｃ）、（ｄ）および（ｅ）を含む処理の組を繰り返す。（ｇ）２つ以上のプロセッサからなる第３の組が、修正データシーケンスの２つ以上の対応サブシーケンスに対して並行して動作して、元の情報ビットに対する軟推定を生成する。この軟推定は、元の情報ビットに対応する受信メッセージを形成するのに使用可能である。
【００２１】
いくつかの実施形態において、第１、第２、第３および第４の組のプロセッサは、プロセッサの列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する。
【００２２】
いくつかの実施形態において、第１、第２、第３および第４の組のプロセッサは、互いに素の組である。
【００２３】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、２つ以上のプロセッサからなる第３の組と同一である（または重複する）。
【００２４】
いくつかの実施形態において、１つ以上のプロセッサからなる第２の組は、１つ以上のプロセッサからなる第４の組と同一である（または重複する）。
【００２５】
１組の実施形態において、復調および／または復号化システムは、少なくともメッセージパッシングアルゴリズムの復調および復号化成分を並列処理する。復調成分は、フィードバックシーケンスの受信シンボルシーケンスおよびそれぞれの重複サブシーケンスの重複サブシーケンスに対して並行して実行され、それによってフィードフォワード情報を生成する。デパンクチャおよびデインターリーブ後、フィードフォワード情報の重複サブシーケンスは、復号化成分によって並行して処理され、それによってフィードバック情報を生成する。フィードバック情報はインターリーブおよびパンクチャされて、次の反復において復調成分によって使用されるフィードバックシーケンスを得る。前記システムの様々な実施形態は、コードオーバーレイ、段階的内部フィードバック、遡及デパンクチャ、すべての零条件を処理するプロシージャなどの機能も含んでもよい。
【００２６】
１組の実施形態において、送信情報を受信する方法は以下のように実行してもよい。前記方法は以下を含んでもよい。（ａ）シンボルデータシーケンスを受信する。（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスの２つ以上の対応サブシーケンスに対して並行して復調処理を実行して、フィードフォワード情報の２つ以上の対応ブロックを生成する。（ｃ）１つ以上のプロセッサからなる第２の組がフィードフォワード情報の２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデパンクチャおよびデインターリーブを実行して、修正データシーケンスを生成する。（ｄ）２つ以上のプロセッサからなる第３の組が、修正データシーケンスの２つ以上の対応サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成する。（ｅ）１つ以上のプロセッサからなる第４の組が、フィードバック情報の２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブおよびパンクチャを実行して、フィードバックデータシーケンスを生成する。（ｂ）、（ｃ）、（ｄ）および（ｅ）を含む１組の処理は、例えば、収束が得られるまで複数回繰り返される。さらに、第３の組のプロセッサは並行して処理を行い、修正データシーケンスの２つ以上の対応サブシーケンスに基づいて元の情報ビットに対して、軟推定（例えば、ＬＬＲ）を生成する。この軟推定に対してハードリミッティングが実行されて、元の情報ビットに対する硬推定を得てもよい。
【００２７】
その硬推定に基づいて、受信メッセージを形成してもよい。受信メッセージは、出力装置を介してユーザに提示されるか、ネットワークを介して送信されるか、または将来的なアクセスまたは送信にそなえて保存されてもよい。一実施形態において、受信メッセージは出力信号に変換され、出力信号は、ユーザデータのパケットを作成するために使用される。
【００２８】
いくつかの実施形態において、第１、第２、第３および第４の組のプロセッサは、プロセッサの列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面矩形格子（または高次元格子）を形成する。
【００２９】
いくつかの実施形態において、第１の組のプロセッサによって実行された復調処理によって、送信シンボルに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードフォワード情報のブロックを作成する。この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【００３０】
いくつかの実施形態において、第３の組のプロセッサによって実行された復号処理によって、符号化ビットに関する内部情報および外部情報が作成される。また、第３の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードバック情報のブロックを作成する。この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【００３１】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含む。このフォワード収束領域は、復調処理のフォワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。
【００３２】
いくつかの実施形態において、前記方法は、フォワード収束領域の長さが動作の組のうちで現在までに完了した反復数の関数として減少することを含んでもよい。
【００３３】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、バックワード収束領域を含む。このバックワード収束領域は、復調処理のバックワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。
【００３４】
いくつかの実施形態において、デパンクチャ処理は、修正データシーケンスのパンクチャにあらかじめ演算された値を投入することを含む。この場合、あらかじめ演算された値は、動作の組の前の反復における復号化処理で演算されたフィードバック情報のブロックからの指定要素である。
【００３５】
いくつかの実施形態において、前記復調処理は、第１の組の各プロセッサが対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数と等しい。
【００３６】
いくつかの実施形態において、前記復号化処理は、第３の組の各プロセッサが対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第３の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のデータ位置でアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数と等しい。
【００３７】
１組の実施形態において、送信情報を受信する方法は、プロセッサ列が、受信データシーケンスに対してメッセージパッシングアルゴリズムを実行することを含んでもよい。メッセージパッシングアルゴリズムを実行する処理は複数回の処理反復を実行することを含んでもよい。各処理反復は、（１）プロセッサ列のプロセッサのうちの２つ以上のプロセッサからなる第１のサブセットがフィードバックデータシーケンスの対応部分を用いて受信シンボルシーケンスの重複部分に対して復調処理を並行して実行してフィードフォワード情報を得て、（２）プロセッサ列のプロセッサのうちの２つ以上のプロセッサからなる第２のサブセットがフィードフォワード情報にデインターリーブおよびデパンクチャを施したものの重複部分に対して復号化処理を並行して実行してフィードバック情報を得る（フィードバックデータシーケンスは、フィードバック情報にインターリーブおよびパンクチャを施したものである）ことを含む。
【００３８】
１組の実施形態において、情報を受信する方法は以下のように実行してもよい。（ａ）シンボルデータシーケンスを受信する。（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスの２つ以上の対応サブシーケンスに並行して復調処理を実行して、フィードフォワード情報の２つ以上の対応ブロックを生成する。（ｃ）１つ以上のプロセッサからなる第２の組がフィードフォワード情報の２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデパンクチャおよびデインターリーブを実行して、修正データシーケンスを生成する。（ｄ）２つ以上のプロセッサからなる第１の組が、修正データシーケンスの２つ以上の対応サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成する。（ｅ）１つ以上のプロセッサからなる第２の組が、フィードバック情報の２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブおよびパンクチャを実行して、フィードバックデータシーケンスを生成する。（ｂ）、（ｃ）、（ｄ）および（ｅ）を含む処理の組を複数回繰り返してもよい。２つ以上のプロセッサからなる第１の組が、修正データシーケンスの２つ以上の対応サブシーケンスに基づいて元の情報ビットに対する軟推定を生成してもよい。この軟推定に対してハードリミッティングが実行されて、元の情報ビットに対する硬推定を得てもよい。
【００３９】
その硬推定に基づいて、受信メッセージを形成してもよい。受信メッセージは、出力装置を介してユーザに提示されるか、ネットワークを介して送信されるか、または将来的なアクセスまたは送信にそなえて保存されてもよい。一実施形態において、受信メッセージは出力信号に変換され、出力信号は、ユーザデータのパケットを作成するために使用される。
【００４０】
いくつかの実施形態において、第１および第２の組のプロセッサは、プロセッサの列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面矩形格子（または高次元格子）を形成する。
【００４１】
いくつかの実施形態において、前記復調処理によって、送信シンボルに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードフォワード情報のブロックを作成する。この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【００４２】
いくつかの実施形態において、前記復号処理によって、符号化ビットに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードバック情報のブロックを作成する。この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【００４３】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含む。このフォワード収束領域は、復調処理のフォワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。
【００４４】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、バックワード収束領域を含む。このバックワード収束領域は、復調処理のバックワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。
【００４５】
いくつかの実施形態において、デパンクチャの動作は、修正データシーケンスのパンクチャ位置にあらかじめ演算された値を投入することを含む。この場合、あらかじめ演算された値は、動作の組の前の反復における復号化処理で演算されたフィードバック情報のブロックからの指定要素である。
【００４６】
いくつかの実施形態において、前記復調処理は、第１の組の各プロセッサが対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のシンボル位置でアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数と等しい。
【００４７】
いくつかの実施形態において、前記復号化処理は、第１の組の各プロセッサが対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のデータ位置でアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数と等しい。
【００４８】
いくつかの実施形態において、（ｂ）の各反復は、復調プログラムを第１の組のプロセッサのうちの各プロセッサの命令メモリへ読み込むことを含む。この場合、復調プログラムは、第１の組の各プロセッサによって実行されると、プロセッサに、対応シンボルデータサブシーケンスおよびフィードバックデータシーケンスの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。（ｄ）の各反復は、復号化プログラムを第１の組のプロセッサのうちの各プロセッサの命令メモリへ読み込むことを含む。この場合、復号化プログラムは、第１の組の各プロセッサによって実行されると、プロセッサに、修正データシーケンスの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。
【００４９】
１組の実施形態において、送信情報受信方法は、プロセッサ列が、受信データシーケンスに対してメッセージパッシングアルゴリズムを実行することを含んでもよい。メッセージパッシングアルゴリズムを実行する処理は複数回の処理反復を実行する。各処理反復は、（１）プロセッサ列のプロセッサからなる第１のサブセットがフィードバックデータシーケンスの対応部分を用いた受信シンボルシーケンスの重複部分に対して復調処理を並行して実行してフィードフォワード情報を得て、（２）プロセッサのうちの第１のサブセットがフィードフォワード情報にデインターリーブおよびデパンクチャを施したものの重複部分に対して復号化処理を並行して実行してフィードバック情報を得る（フィードバックデータシーケンスは、フィードバック情報にインターリーブおよびパンクチャを施したものである）ことを含む。
【００５０】
以下の図面を参照して以下の詳細な説明を検討することによって、本発明の実施形態をより理解することができる。
【図面の簡単な説明】
【００５１】
【図１Ａ】送信情報を受信する方法の１組の実施形態を図示する。
【図１Ｂ】送信情報を受信するシステムの１組の実施形態を図示する。
【図２】いくつかの実施形態による通信システム１００のブロック図である。
【図３】送信機１１０の実施形態を図示する。
【図４】受信機によって実行される処理動作のブロック図である。
【図５】フィルタ３１０の一実施形態の周波数特性のグラフである。
【図６】一実施形態による復調トレリスの表である。
【図７】畳込みエンコーダ２１０の一実施形態のブロック図である。
【図８】図４の処理動作の実行のために使用されるマルチプロセッサ演算システムの一実施形態を示す。
【図９】図４の処理動作のパイプライン化および並列化した構成を示す。
【図１０】図４の処理動作の代替のパイプライン化および並列化した構成を示す。
【図１１】一実施形態による、送信シンボルおよび受信シンボルのためのパケット構造を示す。
【図１２】受信パケットの第１のペイロードシーケンスを網羅する８つの重複ウィンドウの例を示す。
【図１３Ａ】ペイロードシーケンスにおけるウィンドウに対するフォワード演算間隔およびフォワード助走間隔を示す。
【図１３Ｂ】ペイロードシーケンスにおけるウィンドウに対するバックワード演算間隔およびバックワード助走間隔を示す。
【図１４】２つの連続ウィンドウに対する助走間隔と出力領域との関係を示す。
【図１５Ａ】受信シンボルを処理して送信情報を再生する方法の一実施形態を図示する。
【図１５Ｂ】受信シンボルを処理して送信情報を再生するシステムの一実施形態を図示する。
【図１６Ａ】受信シンボルを処理して送信情報を再生する方法の代替の実施形態を図示する。
【図１６Ｂ】受信シンボルを処理して送信情報を再生するシステムの代替の実施形態を図示する。
【図１７】受信機１２０の１組の実施形態によるＣＣ Ｍｏｄｅデータレートに対するＳ／Ｎ比の表である。
【図１８】本明細書において数学的行列アルゴリズムプロセッサ（ＭＭＡＰ）と呼ぶ処理システムの一実施形態を図示するブロック図である。
【図１９】ＭＭＡＰ接続方式の一実施形態を図示するブロック図である。
【図２０】動的に構成可能なプロセッサ（ＤＣＰ）とも呼ばれるプロセッサの一実施形態を図示するブロック図である。
【図２１】動的に構成可能な通信素子（ＤＣＣ）の一実施形態を図示するブロック図である。
【発明を実施するための形態】
【００５２】
本発明は様々な修正および代替の形態が可能であるが、その特定の実施形態は図面における例によって示され、本明細書において詳細に説明される。ただし、図面および詳細な説明は、本発明を開示の特定の形態に限定する意図はないが、一方、添付の特許請求の範囲によって定義される本発明の精神および範囲内のすべての修正、同等物、および代替物を網羅することを意図する。
【００５３】
参考例としての引用
【００５４】
米国特許番号第７，４１５，５９４（２００８年８月１９日発行、２００３年６月２４日出願、名称：「Ｐｒｏｃｅｓｓｉｎｇ Ｓｙｓｔｅｍ Ｗｉｔｈ Ｉｎｔｅｒｓｐｅｒｓｅｄ Ｓｔａｌｌ Ｐｒｏｐａｇａｔｉｎｇ Ｐｒｏｃｅｓｓｏｒｓ Ａｎｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎ Ｅｌｅｍｅｎｔｓ」、発明者Ｍ．Ｂ．Ｄｏｅｒｒ等）」を参照し、その内容全体を本明細書に参照として組み入れる。上記’５９４特許は、本発明のいくつかの実施形態を実装するために使用可能な、本明細書において時折「ＨｙｐｅｒＸ」アーキテクチャとよばれるマルチプロセッサアーキテクチャについて記載する。
【００５５】
以下は、本明細書において使用される略語の一覧である。
ＢＥＲ  ビットエラー率
ＣＰＭ  連続位相変調
ＤＦＥ  決定フィードバック等化
ＤＭＲ  データメモリ／ルーティングユニット
ＤＢＰＳＫ  差動位相変調方式
ＤＥＣ  デコーダ
ＥＱ／Ｄ  等化／変調器
ＦＩＲ  有限インパルス応答
ｋｂ／ｓ  キロバイト／秒
ＬＬＲ  対数尤度比
ＬＵＴ  ルックアップテーブル
ＭＡＰ  帰納的最大確率（ＭａｘｉｍｕｍＡ−Ｐｏｓｔｅｒｉｏｒｉ Ｐｒｏｂａｂｉｌｉｔｙ）
Ｍｂ／ｓ  メガビット／秒
ＭＰＭ  メッセージパッシング法
ＭＳＫ  最小偏移変調
ＰＥ  処理要素
ＱＢＬ−ＭＳＫ  準帯域制限ＭＫＳ  
ＳＩＳＯ  ソフト入力／ソフト出力
ＳＬＩＣＥ  兵士のレベルの統合通信環境（Ｓｏｌｄｉｅｒ−Ｌｅｖｅｌ Ｉｎｔｅｇｒａｔｅｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｅｎｖｉｒｏｎｍｅｎｔ）
ＳＮＲ  Ｓ／Ｎ比
ＳＲＷ  兵士の無線の波形（Ｓｏｌｄｉｅｒ Ｒａｄｉｏ Ｗａｖｅｆｏｒｍ）
【００５６】
本発明の様々な実施形態は、受信信号に対するトレリスベースの処理を実行して、受信信号の復調、復号化、および／または等化を実現するためのシステムおよび方法に関する。例えば、本発明の実施形態は、とりわけ、ビタビ復号化、ビタビ等化、ターボ復号化、ターボ等化などのトレリスベースの方法に対して使用できる。
【００５７】
トレリスベースの各方法は、その構成処理ブロック（例えば復調器やデコーダ、等化器）が、意図的にエンコーダによって、または偶発的に通信チャンネルによって導入された冗長性に関して説明される点で関連している。この冗長性は、ビットが送信機で符号化される方法、またはチャンネル応答を示すタップ付き遅延線の出力で受信されたサンプル間の相互関係に基づくトレリスに関して説明される。
【００５８】
ビタビ復号化はトレリスベースの復号化の一般的方法であって、送信機における畳込み符号化と組み合わせて使用される。畳込み符号化は、送信シンボルストリームに冗長性を意図的に加える際に使用される。
【００５９】
ビタビ等化は、チャンネル誘発の冗長性に基づいたシンボル検出の方法である。ビタビ等化は、受信シンボルと基準コンステレーションとの間の差異計量を最小化しようとするものである。この場合、基準コンステレーション中の各点は、推定チャンネル応答より求められる。ビタビ等化は、線形等化または決定フィードバック等化（ＤＦＥ）の方法が問題であるか、または計算困難である状況において実行可能である。
【００６０】
反復的（ターボとも呼ばれる）方法は、インループ構造を構成する２つ以上のトレリスベースのユニットを用いて、トレリスベースのアプローチ上に構築される。この場合、各ユニットは復調器またはデコーダである。（例えば、ターボ復号化は、２つのデコーダを用いてもよい。ターボ等化は、１つの復調器および１つのデコーダを用いてもよい。）これらのユニットは、反復的ループにおいて「ソフト」信頼性推定を交換して、エラー確率を最小限に抑える。反復的方法は、低デシベルのシャノン限界内での処理を実現するために使用されており、それによって複数の反復というさらなる複雑性は正当化されてきた。
【００６１】
１組の実施形態において、演算方法１０は、図１Ａに示されるような動作を含んでもよい。
【００６２】
１５において、シンボルデータシーケンスＹがチャンネルから受信される。このシンボルデータシーケンスＹは、送信機によってチャンネル上に送出されたシンボルデータシーケンスＸに対応する。シンボルデータシーケンスＹは、シンボルデータシーケンスＸでノイズを含むものや、チャンネル歪曲されたものである。（例えば、チャンネルは、マルチパスなどの歪を発生させる場合がある。）シンボルデータシーケンスＸは、関連情報ビットに基づいて送信機によって生成される。例えば、送信機は、関連情報ビットに対して畳込み符号化を実行してシンボルデータシーケンスＸを生成してもよい。別の例として、送信機は、関連情報ビット（または関連情報ビット群）をシンボル組、すなわち、コンステレーション中のシンボルにマッピングすることによって、シンボルデータシーケンスＸを生成してもよい。
【００６３】
２０において、２つ以上のプロセッサからなる第１の組は、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して並行して動作を行う。シンボルデータシーケンスＹの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応する。（トレリスの各部は、サブシーケンスの重複と同様に重複してもよい）。第１のトレリスは、シンボルデータシーケンスＹにおける冗長性を示し、例えば、シンボルデータシーケンスにおける冗長性を表す構造を有する。この並行動作を実行することによって、関連情報ビットに対する軟推定が生成される。
【００６４】
第１の組のプロセッサのうちの各プロセッサは、シンボルデータシーケンスＹの重複サブシーケンスの対応するものに基づいて、軟推定の対応サブシーケンスを生成してもよい。図に示すように、各プロセッサは、対応シンボルデータサブシーケンスに対して動作を行って、第１のトレリスの各部に対してトレリスデータ値を生成し、トレリスデータ値のサブセットに基づく軟推定の対応サブシーケンスを生成してもよい。（例えば、ビタビ復号化またはビタビ等化の場合、トレリスデータ値は、ブランチメトリックおよびパスメトリックを含んでもよい。ターボ復号化またはターボ等化の場合、トレリスデータ値は、フォワード走査において演算されたアルファ値と、バックワード走査において演算されたベータ値とを含んでもよい）。サブセット以外のトレリスデータ値は捨ててもよい。すなわち、いずれの軟推定の生成にも使用しなくてもよい。例えば、シンボルデータサブシーケンスと、近接（左右）シンボルデータサブシーケンスとの間の重複部分に対応するトレリスデータ値は捨ててもよい。別の例として、シンボルデータサブシーケンスと、左隣のシンボルデータサブシーケンスとの間の重複部分に対応するトレリスデータ値は捨ててもよい。
【００６５】
「重複サブシーケンス」は、近接サブシーケンスと少なくとも部分的に重複した各サブシーケンスを意味しており、他のすべてのサブシーケンスと重複したサブシーケンスを意味するものではない。（なお、サブシーケンスのうちの最初のサブシーケンスは右側にのみ近接サブシーケンスがあり、最後のサブシーケンスは右側にのみ近接サブシーケンスがあることになる。したがって、最初のサブシーケンスは右端に重複部分があり、最後のサブシーケンスは左端に重複部分があることになる）。
【００６６】
第１の組のプロセッサのうちの各プロセッサは、シンボルデータシーケンスＹの２つ以上のサブシーケンスのうちの対応する一方に対して処理を行う。ただし、その他の実施形態も検討されている。例えば、いくつかの実施形態において、各プロセッサは、２つ以上のサブシーケンスに対して処理を行う。その他の実施形態において、各サブシーケンスは、２つ以上の第１の組のプロセッサによって処理される。
【００６７】
上述したように、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応する。トレリスの各部は、シンボルデータシーケンスＹの対応サブシーケンスと同様に重複してもよい。第１の組のプロセッサのうちの各プロセッサは、第１のトレリスの対応部分と同形および同一構造のミニトレリスを保持し、ミニトレリスを用いてシンボルデータシーケンスＹの対応サブシーケンスに対して処理を行う。したがって、各プロセッサは、それぞれのサブシーケンスに対して処理を行う際に互いに干渉しない。
【００６８】
上述のように、並行動作を実行することによって、関連情報ビットに対する軟推定が生成される。いくつかの実施形態において、この軟推定は、関連情報ビットに対応する受信メッセージを形成するために使用される（または使用可能である）。例えば、この軟推定に対してハードリミッティングを行って関連情報ビットに対する硬推定を生成してもよい。いくつかの実施形態において、この硬推定をさらに処理して、受信メッセージを生成してもよい。この受信メッセージは、音声やデータ、映像出力など、ユーザに対する出力を生成するために使用してもよい。また、受信メッセージは、将来的なアクセスまたは送信にそなえて保存されてもよい。
【００６９】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、プロセッサ列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する。例えば、Ｈｙｐｅｒ−Ｘアーキテクチャにしたがって構成された列などである。いくつかの実施形態において、プロセッサ列のうちの各プロセッサは、演算動作、論理動作、ビット操作動作などの基本動作を含む命令セットからの命令を実行するように構成される。いくつかの実施形態において、プロセッサ列の各プロセッサは、動的にプログラム可能である。
【００７０】
いくつかの実施形態において、前記方法１０は、複数の受信シンボルデータシーケンスのそれぞれに対して（ａ）および（ｂ）を実行することも含んでもよい。さらに、シンボルデータシーケンスの２つ以上の重複サブシーケンスの数は、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対して調整されてもよい。一実施形態において、シンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整する動作は、受信シンボルデータシーケンスの長さに基づいて実行される。例えば、サブシーケンスの長さが比較的一定となるように数を調整してもよい。したがって、シンボルデータシーケンスが長いと、短いシンボルデータシーケンスよりも生成されるサブシーケンスの数が多くなる。
【００７１】
いくつかの実施形態において、前記方法１０は、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対して、シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整することも含んでよい。例えば、Ｓ／Ｎ比が高い場合、重複量は小さい。しかしながら、Ｓ／Ｎ比が下がると、重複量は増加する。
【００７２】
いくつかの実施形態において、シンボルデータシーケンスＸは送信機における関連情報ビットの畳込み符号化に基づいて生成される。第１のトレリスは畳込み符号化に基づく構造を有する。畳込み符号化は、１より小さい率を有する。トレリスは、畳込み符号化に起因してシンボルデータシーケンスに存在する冗長性を表す。シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる第１の組が並行して実行する上述の動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ復号化を実現することを含んでもよい。
【００７３】
この並列復号化処理において、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分を走査して、シンボルデータシーケンスのうちの２つ以上のサブシーケンスの対応する１つに基づいてブランチメトリックおよびパスメトリックを演算する。（ブランチメトリックは、トレリス部分における各エッジに対して算出されてもよい。パスメトリックは、トレリス部分の各ノードにおける追加−比較−選択動作を用いて算出されてもよい）。走査後、第１の組のプロセッサのうちの各プロセッサは、関連情報ビットの軟推定の対応サブシーケンスを再生するために、トレースバック処理を実行してもよい。トレースバック処理は、対応するトレリス部分の終端から始端までサバイバーパス（最小パスメトリックのパス）を探すことを含む。サバイバーパスの最初の部分は捨ててもよい。すなわち、軟推定の対応サブシーケンスを生成するために使用されない。最初の部分は、シンボルデータサブシーケンスとその前のシンボルデータサブシーケンスとの重複に対応する部分である場合がある（すなわち、サバイバーパスを算出するために使用されるもの）。
【００７４】
いくつかの実施形態において、第１のトレリスは、シンボルデータシーケンスＹとシンボルデータシーケンスＸとの所与の線形関係に基づいた構造を有する。例えば、シンボルデータシーケンスＸとシンボルデータシーケンスとの間に介在する有効チャンネルの既知のインパルス応答に基づく。（なお、この有効チャンネルは、物理チャンネルに加えて、送信機および受信機にフィルタ構造を含んでもよい）。第１のトレリスは、有効チャンネルに起因して受信シンボルデータシーケンスに存在する冗長性を表す。シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる第１の組が並行して実行する上述の動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復調処理を並行して実行し、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ等化を実現することを含んでもよい。
【００７５】
この並列復調処理において、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分を走査して、シンボルデータシーケンスのうちの２つ以上のサブシーケンスの対応する１つに基づいてブランチメトリックおよびパスメトリックを演算する。（ブランチメトリックは、トレリス部分における各エッジに対して算出されてもよい。パスメトリックは、トレリス部分の各ノードにおける追加−比較−選択動作を用いて算出されてもよい）。走査後、第１の組のプロセッサのうちの各プロセッサは、関連情報ビットの軟推定の対応サブシーケンスを再生するために、トレースバック処理を実行してもよい。トレースバック処理は、対応するトレリス部分の終端から始端までサバイバーパス（最小パスメトリックのパス）を探すことを含む。サバイバーパスの最初の部分は捨ててもよい。すなわち、軟推定の対応サブシーケンスを生成するために使用されない。最初の部分は、シンボルデータサブシーケンスとその前のシンボルデータサブシーケンスとの重複に対応する部分である場合がある（すなわち、サバイバーパスを算出するために使用されるもの）。
【００７６】
方法１０のいくつかの実施形態において、送信機は、元の情報ビットの畳込み符号化によって符号化ビットを得て、その符号化ビットをインターリーブすることによって関連情報ビットを生成するものとする。そのような一実施形態を図１Ｂに示す。この実施形態において、前記方法は、畳込み符号化の復号化を処理する処理２５を含む。処理２０は、２つ以上のプロセッサからなる第１の組がフィードバックシーケンスの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作することを含む。このフィードバックシーケンスは、処理２５によって生成された、符号化ビットに対する軟推定をインターリーブしたものである。処理２０のインターリーブしたものは、フィードバック情報とともにシンボルデータシーケンスを用い、図１Ｂでは２０’とする。
【００７７】
処理２５において、２つ以上のプロセッサからなる第２の組は、関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作する。この場合、デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応する。第２のトレリスは、畳込み符号化に対応する構造を有してもよい。デインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作することによって、符号化ビットに対する軟推定が生成される。
【００７８】
第２の組の２つ以上のプロセッサのそれぞれは、デインターリーブしたものの２つ以上の重複サブシーケンスの対応する１つに対して動作してもよい。いくつかの実施形態において、デインターリーブしたものの重複サブシーケンスの数は、シンボルデータシーケンスの重複サブシーケンスの数に等しい。ただし、代替の実施形態において、それらの数は異なる。
【００７９】
前記方法１０は、図１Ｂの２７に示すように、例えば反復条件が満たされるまで、処理２０’および処理２５を複数回繰り返すことを含んでもよい。様々な終了条件のいずれもが考えられる。例えば、一実施形態において、処理２０’と処理２５とは、所定回数繰り返されてもよい。別の実施形態において、反復は、軟推定の信頼性に基づいた条件が満たされるまで継続してもよい。例えば、反復は、関連情報ビットの大部分またはすべての軟推定や符号化ビットの軟推定の信頼性が所与の閾値を超えるまで継続してもよい。一実施形態において、ｋ番目のビットに対する所与の軟推定の信頼性は、以下の式によって算出してもよい。
【数１】
0005406369.tif 000002
ここで、ＳRは受信シンボルを示し、ＳTは送信参照シンボル、σ2はノイズ分散である。最初の非発散項における加算は、ｂ（ｋ）＝１の場合に、送信参照シンボルの組に対して演算される。第２の非発散項における加算は、ｂ（ｋ）＝０の場合に、送信参照シンボルの組に対して演算される。
【００８０】
前記方法１０は、例えば、２つ以上のプロセッサからなる第１の組が処理２０’の最後の反復を終了した後などに、２つ以上のプロセッサからなる第２の組が関連情報ビットに対する軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作して、元の情報ビットに対する軟推定を生成することを含んでもよい。
【００８１】
いくつかの実施形態において、処理２０’は復調処理を表し、処理２５は復号化処理を表し、処理２０’および処理２５の反復は、シンボルデータシーケンスのターボ等化を実現する。
【００８２】
いくつかの実施形態において、処理２０’は第１の復号化処理を表し、処理２５は第２の復号化処理を表し、処理２０’および処理２５の反復は、シンボルデータシーケンスのターボ復号化を実現する。
【００８３】
いくつかの実施形態において、前記方法１０は、元の情報ビットの軟推定に基づいた受信メッセージの形成を含んでもよい。受信メッセージは出力信号を生成するために使用してもよく、出力信号はスピーカや表示画面などの出力装置を駆動するために使用されてもよい。
【００８４】
図１Ｂの前記方法は、複数の受信シンボルデータシーケンスのそれぞれに対して実行されてもよい。いくつかの実施形態において、第１の組のプロセッサの数は、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対して調整されてもよい。例えば、受信シンボルデータシーケンスの長さが変わると、シンボルデータシーケンス毎の重複サブシーケンスの数もそれに応じて変化して、例えば、各サブシーケンスの長さを比較的一定に保ってもよい。第１の組のプロセッサの数は、重複サブシーケンスの数に等しく設定してもよい。
【００８５】
上述のように、図１Ｂの前記方法は、複数の受信シンボルデータシーケンスのそれぞれに対して実行してもよい。いくつかの実施形態において、第２の組のプロセッサの数は、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対して調整してもよい。例えば、現在のシンボルデータシーケンスの長さを前のシンボルデータシーケンスと比べて変化した場合に、そのプロセッサの数を調整してもよい。処理されているサブシーケンス、すなわち、デインターリーブしたもののサブシーケンスに対する長さを比較的一定に保つために、第２の組のプロセッサの数を更新してもよい（例えば、継続的に更新してもよい）。
【００８６】
いくつかの実施形態において、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスの数は、受信シンボルデータシーケンスの少なくとも１つに対して調整されてもよい。（関連情報ビットの軟推定の）デインターリーブしたものの２つ以上の重複サブシーケンスの数は、受信シンボルデータシーケンスの少なくとも１つに対して調整されてもよい。例えば、一実施形態において、受信データシーケンスの現在の１つの長さを受信データシーケンスの前の１つと比べて変化した場合に、その両方の数を調整してもよい。
【００８７】
いくつかの実施形態において、前記シンボルデータシーケンスＹの２つ以上の重複サブシーケンス間の重複量は、例えばＳ／Ｎ比の変化に応じて調整してもよい。前記方法は、Ｓ／Ｎ比の時間の経過にともなった追跡を含んでもよい。それによって、現在の受信シンボルデータシーケンスに対する予測Ｓ／Ｎ比に基づいて、重複量を調整できる。
【００８８】
一実施形態において、シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量の調整は、処理２０’および処理２５の前記複数の反復の少なくとも１つに対して実行される。例えば、（処理２０’および処理２５の前記複数の反復のうちの）現在完了している反復の数に応じて、重複量を減少させてもよい。
【００８９】
いくつかの実施形態において、例えば、処理２０’および処理２５の複数の反復のうちの少なくとも１つに対して、（関連情報ビットの軟推定の）デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量を調整してもよい。例えば、（処理２０’および処理２５の前記複数の反復のうちの）現在完了している反復の数に応じて、重複量を減少させてもよい。
【００９０】
いくつかの実施形態において、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスの重複量は調整されてもよい。（関連情報ビットの軟推定の）デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量は調整されてもよい。例えば、一実施形態において、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量の調整は、処理２０’および処理２５の前記複数の反復の少なくとも１つに対して実行される。デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量の調整は、処理２０’および処理２５の前記複数の反復の少なくとも１つに対して実行される。
【００９１】
いくつかの実施形態において、近接サブシーケンス間の重複量は、生成されている軟推定の信頼性に基づいて調整されてもよい（すなわち、関連情報ビットに対する軟推定および符号化ビットに対する軟推定）。例えば、一実施形態によれば、全信頼性（または一部）が１／４より大きくなるまで、この重複量をまずＬ１に設定してＬ１で維持し、その後重複量をＬ２に設定してもよい。全信頼性（または一部）が１／２より大きくなるまで、この重複量はＬ２を維持し、その後重複量はＬ３に設定される。全信頼性（または一部）が３／４より大きくなるまで、この重複量はＬ３を維持し、その後処理２０’および処理２５の反復は停止される。値Ｌ１、Ｌ２およびＬ３はＬ１＞Ｌ２＞Ｌ３＞０となるように選択される。それによって、重複量は３つの閾値を使用した制御スケジュールにしたがって調整される。重複量に対する様々な値の組み合わせ、閾値数、閾値とともに、様々な類似の実施形態が考えられる。
【００９２】
いくつかの実施形態において、シンボルデータシーケンスＹの２つ以上のサブシーケンスの少なくとも１つはフォワード収束領域を含む。（例えば、一実施形態において、サブシーケンスのうちの最初のサブシーケンスを除くサブシーケンスのそれぞれは、対応するフォワード収束領域を含む）。処理２０’は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分に対してフォワードトレリス走査を実行して、第１のトレリスの対応部分の各時間ステップにおける（すなわち、シンボルデータシーケンスＹの対応サブシーケンス内の時間ステップにおける）フォワード走査値を得ることを含んでもよい。フォワード収束領域は、フォワードトレリス走査において収束を得るために使用される。
【００９３】
フォワード走査において、ある時間ステップにおけるフォワード走査値は、次の時間ステップにおけるフォワード走査値を演算するために使用される。このフォワード収束領域上でのフォワード走査値は、時間ステップ指数が増加するとともに収束する（すなわち、良好になる）と見なされる。（この値は、フォワード収束領域の始端より終端に向かって良好となる）。フォワード収束領域後のフォワード走査値は満足のゆく品質であると見なされ、関連情報ビットに対する軟推定を演算するために使用されてもよい。ただし、フォワード収束領域上のフォワード走査値は捨ててもよい。すなわち、軟推定を演算するためには使用されない。
【００９４】
いくつかの実施形態において、処理２０’および処理２５の複数の反復のうちの現在完了している反復の数に応じて、フォワード収束領域の長さは減少させてもよい。
【００９５】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つはバックワード収束領域を含む。（例えば、一実施形態において、サブシーケンスのうちの最後のサブシーケンスを除くサブシーケンスのそれぞれは、対応するバックワード収束領域を含む）。処理２０’は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分に対してバックワードトレリス走査を実行して、第１のトレリスの対応部分の各時間指数における（すなわち、シンボルデータシーケンスＹの対応サブシーケンス内の時間ステップにおける）バックワード走査値を得ることを含んでもよい。バックワード収束領域は、バックワードトレリス走査において収束を得るために使用される。
【００９６】
バックワード走査において、時間指数のある値におけるバックワード走査値は、時間指数の次に小さな値におけるバックワード走査値を演算するために使用される。このバックワード収束領域上でのバックワード走査値は、時間指数が減少するとともに収束する（すなわち、良好になる）と見なされる。バックワード収束領域後（左側）のバックワード走査値は満足のゆく品質であると見なされ、関連情報ビットに対する軟推定を演算するために使用されてもよい。ただし、バックワード収束領域上のバックワード走査値は捨ててもよい。すなわち、軟推定を演算するためには使用されない。
【００９７】
いくつかの実施形態において、処理２０’および処理２５の前記複数の反復のうちの現在完了している反復の数に応じて、バックワード収束領域の長さは減少させてもよい
【００９８】
いくつかの実施形態において、処理２０’は、関連情報ビットに関する内部情報および外部情報の生成を含む。第１の組の各プロセッサは、内部情報と外部情報との混合情報に基づいて関連情報ビットに対する軟推定を生成する。処理２０’および処理２５の複数回の反復のうちの現在完了している反復の数に応じて、混合情報に含まれる内部情報の量は増加させる。例えば、混合情報は初めのいくつかの反復に対して外部情報のみを含み、以降の反復に対しては、例えば、線形スケジュールまたは何らかの非線形スケジュール（例えば、多項式関数に基づく）にしたがって、その後徐々に内部情報を混合情報に加えてもよい。
【００９９】
いくつかの実施形態において、処理２５は、符号化ビットに関する内部情報および外部情報の生成を含む。第２の組の各プロセッサは、内部情報と外部情報との混合情報に基づいて符号化ビットに対する軟推定を生成する。処理２０’および処理２５の複数の反復のうちの現在完了している反復の数に応じて、混合情報に含まれる内部情報の量は増加させる。例えば、混合情報は初めのいくつかの反復に対して外部情報のみを含み、以降の反復に対しては、例えば、線形スケジュールまたは何らかの非線形スケジュール（例えば、多項式関数に基づく）にしたがって、その後徐々に内部情報を混合情報に加えてもよい。
【０１００】
いくつかの実施形態において、関連情報ビットの軟推定をデインターリーブしたものを、関連情報ビットの軟推定に対してデパンクチャおよびデインターリーブを実行することによって生成してもよい。このデパンクチャは、あらかじめ演算された値を出力シーケンスのパンクチャ位置に投入することを含む。あらかじめ演算された値は、処理２５の前の反復において第２の組のプロセッサによって演算された符号化ビットに対する軟推定のうちで指定されたものである。出力シーケンスは、その後デインターリーブされて、関連情報ビットの軟推定をデインターリーブしたものを生成する。このデインターリーブおよびデパンクチャは、１つ以上のプロセッサからなる第３の組によって実行されてもよい。
【０１０１】
いくつかの実施形態において、処理２０’は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含む。第１の組のプロセッサの所与の（任意または各）プロセッサに対して、フォワードパスは、所与のシンボル位置におけるアルファベクトル（上記で「フォワード走査値」と呼ばれる）を算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数、すなわち値１／Ｎｓｔａｔｅｓと等しい。Ｎｓｔａｔｅｓとは、時間指数のある所与の値におけるトレリスの数である。算出されたベータベクトルが零ベクトルに等しい場合は、同様の方法をバックワードパスにおいても使用可能である。（「パス」とは、「走査」の同義語として本明細書では使用されている）。
【０１０２】
いくつかの実施形態において、処理２５’は、第２の組のプロセッサのうちの各プロセッサが第２のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含む。第２の組のプロセッサの所与の（任意または各）プロセッサに対して、フォワードパスは、所与のデータ位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は小さな正の数と等しい。算出されたベータベクトルが零ベクトルに等しい場合は、同様の方法をバックワードパスにおいても使用可能である。
【０１０３】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、２つ以上のプロセッサからなる第２の組と同一である。そのような一実施形態において、処理２０’の各反復は、第１のプログラムコードを、第１の組のプロセッサのうちの各プロセッサの命令メモリに読み込むことを含む。処理２５の各反復は、第２のプログラムコードを、第１の組のプロセッサのうちの各プロセッサの命令メモリに読み込むことを含む。第１のプログラムコードは、第１の組の各プロセッサによって実行されると、プロセッサに、シンボルデータシーケンスＹの対応サブシーケンスおよび符号化ビットに対する軟推定をインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。第２のプログラムコードは、第１の組の各プロセッサによって実行されると、プロセッサに、関連情報ビットに対する軟推定をデインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。したがって、この実施形態において、命令メモリに対して、第１のプログラムコードと第２のプログラムコードとが交互に読み込まれる。各プロセッサの命令メモリが両プログラムを一度に読み込むには容量が小さい場合に、この実施形態を使用してもよい。
【０１０４】
１組の実施形態において、システムは、チャンネルから受信したシンボルデータシーケンスＹを処理するために、以下のように構成されてもよい。この場合、シンボルデータシーケンスＹは、送信機によってチャンネル上に送出されたシンボルデータシーケンスＸに対応する。ここで、シンボルデータシーケンスＸは、関連情報ビットに基づいて送信機によって生成される。前記システムは、それぞれ第１のプログラムコードで構成された２つ以上のプロセッサからなる第１の組を含んでもよい。この場合、第１のプログラムコードは、第１の組のプロセッサによって実行されると、第１の組のプロセッサに、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスを並行して処理（ａ）させる。ここで、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応する。第１のトレリスは、シンボルデータシーケンスＹにおける冗長性を示す。この並行動作によって、関連情報ビットに対する軟推定が生成される。この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成できる。
【０１０５】
第１の組のプロセッサのうちの各プロセッサは、対応する命令メモリと、命令メモリに格納されたプログラム命令を実行するための回路リソースとを含む。したがって、各プロセッサは、プログラム可能なプロセッサである。
【０１０６】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、プロセッサ列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する。同様に、２つ以上のプロセッサからなる第２の組は、プロセッサ列から選択される。そのような一実施形態において、このプロセッサ列は、Ｈｙｐｅｒ−Ｘアーキテクチャにしたがって構成される。
【０１０７】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサによって実行されると、第１の組のプロセッサが複数の受信シンボルデータシーケンスに対して実行する（ａ）ようにする。
【０１０８】
また、いくつかの実施形態において、前記システムは、前記受信シンボルデータシーケンスの少なくとも１つに対してシンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整し、それに応じて第１の組のプロセッサの数を調整する手段を備える。この手段は、第１の組ではないプロセッサを含んでもよい。例えば、上述した列のプロセッサまたは列以外のプロセッサを含んでもよい。シンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整する動作は、例えば、様々に上述したように、受信シンボルデータシーケンスの長さに基づいて実行されてもよい。
【０１０９】
また、いくつかの実施形態において、前記システムは、前記受信シンボルデータシーケンスの少なくとも１つに対してシンボルデータシーケンスの前記２つ以上の重複サブシーケンス間の重複量を調整する手段を備えてもよい。この手段は、第１の組ではないプロセッサを含んでもよい。例えば、上述した列のプロセッサまたは列以外のプロセッサを含んでもよい。
【０１１０】
いくつかの実施形態において、シンボルデータシーケンスＸは、関連情報ビットの畳込み符号化に基づいて生成される。第１のトレリスは畳込み符号化に基づく構造を有する。そのような一実施形態において、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行する動作は、例えば上述したように、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスのそれぞれのビタビ復号化を実現することを含んでもよい。
【０１１１】
前記システムのいくつかの実施形態において、第１のトレリスは、例えば上述したように、シンボルデータシーケンスＹとシンボルデータシーケンスＸとの所与の線形関係に基づいた構造を有する。シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる第１の組が並行して実行する上述の動作は、例えば上述したように、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスに対して復調処理を並行して実行し、シンボルデータシーケンスＹの２つ以上の重複サブシーケンスのそれぞれのビタビ等化を実現することを含んでもよい。
【０１１２】
いくつかの実施形態において、送信機は、元の情報ビットの畳込み符号化によって符号化ビットを得て、その符号化ビットをインターリーブすることによって関連情報ビットを生成するものとする。その場合、動作（ａ）は、２つ以上のプロセッサからなる第１の組が符号化ビットに対する軟推定をインターリーブしたものの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作することを含む。さらに、前記システムは、第２のプログラムコードで構成された２つ以上のプロセッサからなる第２の組を含む。第２のプログラムコードは、第２の組の各プロセッサに実行されると、第２の組の各プロセッサは、（ｂ）関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作する。デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応する。第２のトレリスは、畳込み符号化に対応する構造を有する。デインターリーブしたもののうちの２つ以上の重複サブシーケンスに対して並行して動作すると、符号化ビットに対する軟推定が生成される。
【０１１３】
２つ以上のプロセッサからなる第１の組および２つ以上のプロセッサからなる第２の組は、（ａ）および（ｂ）を複数回交互にそれぞれ実行するようにプログラムされている。もしくは、第１の組および第２の組以外のプロセッサ（または制御ユニット）は、第１の組および第２の組が（ａ）および（ｂ）を複数回交互にそれぞれ実行するようにプログラムされている。
【０１１４】
いくつかの実施形態において、２つ以上のプロセッサからなる第２の組は、それぞれ追加のプログラムコードで構成される。その場合、第２のプログラムコードは、第２の組の各プロセッサによって実行されると、第２の組の各プロセッサは、関連情報ビットに対する軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作して、元の情報ビットに対する軟推定を生成する。
【０１１５】
いくつかの実施形態において、動作（ａ）は受信シンボルデータシーケンスの復調を実現し、動作（ｂ）は、関連情報ビットに対する軟推定をデインターリーブしたものの復号化を実現し、（ａ）および（ｂ）を複数回交互に実行する動作は、シンボルデータシーケンスＹのターボ等化を実現する。
【０１１６】
いくつかの実施形態において、動作（ａ）は受信シンボルデータシーケンスの復号化を実現し、動作（ｂ）は、関連情報ビットの軟推定をデインターリーブしたものの復号化を実現し、（ａ）および（ｂ）を複数回交互に実行する動作は、シンボルデータシーケンスＹのターボ復号化を実現する。
【０１１７】
いくつかの実施形態において、第１の組の各プロセッサおよび第２の組の各プロセッサは、例えば上述のように、符号化ビットの軟推定および関連情報ビットの軟推定が所定の閾値を超えた場合に前記（ａ）および（ｂ）を複数回交互に実行することを停止するようにプログラムされている。
【０１１８】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサによって実行されると、例えば様々に上述のように、第１の組のプロセッサが、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整するようにする。そのような一実施形態において、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整する動作は、（ａ）および（ｂ）の複数回の実行の少なくとも１つに対して実行される。
【０１１９】
いくつかの実施形態において、第２のプログラムコードは、第２の組のプロセッサによって実行されると、例えば様々に上述のように、第２の組のプロセッサが、関連情報ビットの軟推定の前記デインターリーブしたものの２つ以上の重複サブシーケンスの重複量を調整するようにする。そのような一実施形態において、デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量を調整する動作は、（ａ）および（ｂ）の複数回の実行の少なくとも１つに対して実行される。
【０１２０】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含む。動作（ａ）は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分に対してフォワードトレリス走査を実行して第１のトレリスの対応部分の各時間ステップにおけるフォワード走査値を得ることを含む。この場合、フォワード収束領域は、フォワードトレリス走査における収束を得るために使用される。そのような一実施形態において、第１のプログラムコードは、第１の組のプロセッサによって実行されると、第１の組のプロセッサが（ａ）および（ｂ）の前記複数回の実行のうち現在完了している実行の数の関数としてフォワード収束領域の長さを減少させるようにする。
【０１２１】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、バックワード収束領域を含む。動作（ｂ）は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分に対してバックワードトレリス走査を実行して第１のトレリスの対応部分の各時間指数におけるバックワード走査値を得ることを含む。この場合、バックワード収束領域は、バックワードトレリス走査における収束を得るために使用される。そのような一実施形態において、第２のプログラムコードは、第２の組のプロセッサによって実行されると、第２の組のプロセッサが（ａ）および（ｂ）の前記複数回の実行のうち現在完了している実行の数の関数としてバックワード収束領域の長さを減少させるようにする。
【０１２２】
いくつかの実施形態において、動作（ａ）は、関連情報ビットに関する内部情報および外部情報の生成を含む。第１のプログラムコードは、第１の組の各プロセッサによって実行されると、第１の組の各プロセッサが内部情報と外部情報との混合情報に基づいて関連情報ビットに対する軟推定を並行して生成する。（ａ）および（ｂ）の前記複数回の実行のうちの現在完了している実行の数に応じて、混合情報に含まれる内部情報の量を増加させる。
【０１２３】
いくつかの実施形態において、動作（ｂ）は、符号化ビットに関する内部情報および外部情報の生成を含む。第２のプログラムコードは、第２の組の各プロセッサによって実行されると、第２の組の各プロセッサが内部情報と外部情報との混合情報に基づいて符号化ビットに対する軟推定を生成するようにする。（ａ）および（ｂ）の前記複数回の実行のうちの現在完了している実行の数に応じて、混合情報に含まれる内部情報の量を増加させる。
【０１２４】
いくつかの実施形態において、前記システムは、前記関連情報ビットの軟推定をデインターリーブしたものを、関連情報ビットの軟推定に対してデパンクチャおよびデインターリーブを実行することによって生成するように構成された１つ以上のプロセッサからなる第３の組を含んでもよい。このデパンクチャの動作は、あらかじめ演算された値を出力シーケンスのパンクチャ位置に投入することを含む。あらかじめ演算された値とは、（ｂ）の前の実行において第２の組のプロセッサによって演算された符号化ビットに対する軟推定のうちで指定されたものである。出力シーケンスは、その後デインターリーブされて、関連情報ビットの軟推定をデインターリーブしたものを得てもよい。
【０１２５】
いくつかの実施形態において、動作（ａ）は、第１の組のプロセッサのうちの各プロセッサが第１のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含む。第１の組のプロセッサのうちの所与のプロセッサに対して、フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。この場合、ベクトルＥの全成分は小さな正の数と等しい。
【０１２６】
いくつかの実施形態において、動作（ｂ）は、第２の組のプロセッサのうちの各プロセッサが第２のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含む。第２の組のプロセッサの所与のプロセッサに対して、フォワードパスは、所与のデータ位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。この場合、ベクトルＥの全成分は小さな正の数と等しい。
【０１２７】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、２つ以上のプロセッサからなる第２の組と同一である。第１の組のプロセッサのうちの各プロセッサは、（ａ）の各実行の前に第１のプログラムコードを読み込み、（ｂ）の各実行の前に第２のプログラムコードを読み込むようにプログラムされている。第１のプログラムコードは、第１の組の各プロセッサによって実行されると、第１の組の各プロセッサが、シンボルデータシーケンスＹの対応サブシーケンスおよび符号化ビットに対する軟推定をインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行するようにする。第２のプログラムコードは、第２の組の各プロセッサによって実行されると、第２の組の各プロセッサが関連情報ビットに対する軟推定をデインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行するようにする。
【０１２８】
いくつかの実施形態において、２つ以上のプロセッサからなる第１の組は、元の情報ビットの軟推定に基づく受信メッセージを形成するようにプログラムされている。
【０１２９】
１組の実施形態において、ターボ等化を実行する方法は、以下の動作を含んでもよい。
（１）シンボルデータシーケンスがチャンネルから受信される。このシンボルデータシーケンスは、チャンネル上に送出されたシンボルデータシーケンスＸに対応する。シンボルデータシーケンスＹは、元の情報ビットに基づいて生成される。（２）２つ以上のプロセッサからなる第１の組は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して、フィードバック情報をインターリーブしたものの２つ以上の対応サブシーケンスを用いて復調処理を並行して実行して、フィードフォワード情報を生成する。
（３）２つ以上のプロセッサからなる第２の組は、フィードフォワード情報をデインターリーブしたものの２つ以上の重複サブシーケンスに対して、復号化処理を並行して実行して、フィードバック情報を生成する。
（４）（２）および（３）を含む動作の組は、例えば終了条件が満たされるまで繰り返されてもよい。
（５）２つ以上のプロセッサからなる第３の組は並行して動作して、フィードフォワード情報のデインターリーブしたものの２つ以上の重複サブシーケンスから元の情報ビットに対する軟推定を生成する。この軟推定は、元の情報ビットに対応する受信メッセージを形成するのに使用可能である。
【０１３０】
いくつかの実施形態において、第３の組のプロセッサは、第２の組のプロセッサと同一である。
【０１３１】
いくつかの実施形態において、第１の組の各プロセッサと第２の組の各プロセッサとは、互いに素の組である。他の実施形態において、第１の組の各プロセッサは第２の組の各プロセッサと同一である。
【０１３２】
本発明の実施形態は、様々な種類のトレリスベースの方法に対する並列処理技術に関するものでもよい。以下、本発明の典型的な実施形態を説明する。以下のトレリスベースの方法はターボ等化である。ただし、本発明の実施形態は、以下で説明するターボ等化の実施形態に限定されるものではなく、本発明の実施形態は様々なトレリスベースの技術とともに使用される。
【０１３３】
１組の実施形態において、図２に示すように、通信システム１００は、送信機１１０と受信機１２０とを含んでもよい。送信機１１０は、情報源からバイナリビットのストリーム｛ａk｝を受信して、送信信号を生成する。送信機１１０は、送信信号をチャンネル１１５上に送出する。受信機１２０は、ノイズを含む送信信号を表す受信信号を受信する。受信機１２０は受信信号に対して動作して、ソースストリーム｛ａk｝の各ビットａkに対する推定Ａkを生成する。受信機１２０は、ラジオ、コードレス電話機、携帯電話機などのデータ通信装置などの様々な種類のワイヤレス装置を含んでもよい。例えば、受信機１２０は、例えば、兵士の無線の波形（Ｓｏｌｄｉｅｒ Ｒａｄｉｏ Ｗａｖｅｆｏｒｍ：ＳＲＷ）を用いて軍の職員によって使用されることを意図した通信装置でもよい。一実施形態において、受信機は、ワイヤレスポータブルテレビなどのテレビなどの映像表示装置でもよい。
【０１３４】
いくつかの実施形態において、送信機１１０は図３に示す構造を有する。送信機１１０は、畳込みエンコーダ２１０と、インターリーバ２２０と、パンクチャ部４２０と、マッピング部２４０とを含む。畳込みエンコーダ２１０は、情報源からのビット｛ａk｝のストリームに対して動作して符号化ビットストリーム｛ｂk｝を生成する。インターリーバ２２０は、所定の順列にしたがって符号化ビットストリーム中のデータの各ブロックをインターリーブして、インターリーブビットストリームを生成する。パンクチャ部２３０は、インターリーブビットストリームをパンクチャして、パンクチャビットストリーム｛ｃk｝を得る。パンクチャは、所定のパターンにしたがって、インターリーブビットストリームにおける情報のある部分を捨てる処理である。教育的な例として、中間ビットストリーム：（ｚ１、ｚ２、ｚ３、ｚ４、ｚ５、ｚ６、ｚ７、ｚ８、ｚ９・・・）→（ｚ１、ｚ２、ｚ４、ｚ５、ｚ６、ｚ７・・・）のビットを２つおきに捨てる場合もある。幅広いパンクチャパターンが考えられる。
【０１３５】
一実施形態において、パンクチャおよびインターリーブのパターンは、Ｍｏｄｅｍ Ｓｐｅｃｉｆｉｃａｔｉｏｎ ｆｏｒ ＳＬＩＣＥ Ｉｎｃ．２、ＩＴＴＤＯＣＵＭＥＮＴ ＃８２２３０３８ ＲＥＶＩＳＩＯＮ（２００６年１１月発行）と一致する。その内容は、ここで引用したことにより、その全体が本願にも含まれるものとする。
【０１３６】
マッピング部２４０は、パンクチャビットストリームをシンボル組から取り出されたシンボルのシーケンス｛ｘk｝に対応づける。（上記シンボル組は、複素平面または実数直線のサブセットでもよい）。幅広い種類のシンボル組を使用できる。
【０１３７】
送信機１１０は、シンボルシーケンス｛ｘk｝に基づいて、（様々な形態の変調を用いて）キャリア信号を変調し、変調信号をチャンネルに送出できる。受信機１２０は、その送信信号を受信して復調して、シンボルシーケンス｛ｙk｝を復活させる。シンボルシーケンス｛ｙk｝は、本明細書において「受信」シンボルシーケンスと呼ばれる。送信シンボルシーケンス｛ｘk｝と受信シンボルシーケンス｛ｙk｝との関係は以下によって表すことができる。
【数２】
0005406369.tif 000003
ｙk＝ｖk＋ｎk
ここで、ｎkはノイズ、｛ｈj｝は既知のインパルス応答である。すなわち、受信シンボルシーケンスは、ノイズｎkと送信シンボルシーケンス｛ｘk｝に対して動作する線形フィルタの出力ｖkとの合計と解釈できる。上記受信機は、受信シンボルシーケンス｛ｙk｝に基づく元のビットストリーム｛ａk｝のビットに対する推定を生成する。
【０１３８】
いくつかの実施形態において、受信機１２０は、例えば、ソフトウェアラジオ、ハードウェアラジオ、または部分的にソフトウェアラジオかつ部分的にハードウェアラジオであるラジオなどのラジオでもよい。ただし、非ラジオの実施形態も同様に考えられる。
【０１３９】
いくつかの実施形態において、受信機１２０は、兵士のレベルの統合通信環境（Ｓｏｌｄｉｅｒ−Ｌｅｖｅｌ Ｉｎｔｅｇｒａｔｅｄ Ｃｏｍｍｕｎｉｃａｔｉｏｎｓ Ｅｎｖｉｒｏｎｍｅｎｔ）（ＳＬＩＣＥ Ｉｎｃｒｅｍｅｎｔ２．１、以下ＳＬＩＣＥ２．１と呼ぶ）において使用される兵士の無線の波形（Ｓｏｌｄｉｅｒ Ｒａｄｉｏ Ｗａｖｅｆｏｒｍ（ＳＲＷ））を実現するように設計される。以下の説明は、ＳＬＩＣＥ２．１を前提としている。なお、本明細書において開示される新規の原理は、当然ながら様々な状況に対して幅広く適用される。
【０１４０】
いくつかの実施形態において、受信機１２０は、反復的メッセージパッシング方法にしたがって復調および復号化を実行できる。メッセージパッシング方法（ＭＰＭ）は、フィードバックと連携した復調処理および復号化処理を含む。復調処理は、復号化処理によって提供されたフィードバック情報と同様に、受信シンボル情報を用いて動作する。復号化処理は、復調処理によって提供されたフィードフォワード情報に基づいて動作する。ＭＰＭは、復調処理と復号化処理とを交互に実行することを含む。この場合、これらの処理が、それぞれ、正しい復調および復号化の解に収束することを前提としている。
【０１４１】
受信機１２０は、ＭＰＭを実行するようにプログラムされたハードウェアを備える。いくつかの実施形態において、このハードウェアは、例えば上述した米国特許第７，４１５，５９４号に記載されているマルチプロセッサアーキテクチャの１つなどのマルチプロセッサ演算システムを含む。
【０１４２】
図４は、受信機１２０によって実行される、１組の実施形態による処理動作のブロック図３００を示す。図３００は、フィルタモジュール３１０と、ＰＤＦモジュール３１５と、復調処理３２０と、デインターリーブ／デパンクチャ処理３２５と、復号化処理３３０と、インターリーブ／パンクチャ処理３３５と、決定モジュール３４０とを含む。フィルタモジュール３１０は、アナログ−デジタル変換処理を実行して無線フロントエンドから再生した複合サンプルのストリーム｛ｒk｝に対して動作して、受信シンボルシーケンス｛ｙk｝を生成する。ＰＤＦモジュール３１５はこの受信シンボルシーケンス｛ｙk｝に動作して、シンボル確率情報を生成する。復調処理３２０と、デインターリーブ／デパンクチャ処理３２５と、復号化処理３３０と、インターリーブ／パンクチャ処理３３５とは協働して、ＰＤＦモジュール３１５によって提供されたシンボル確率情報に基づいて、ＭＰＭ（メッセージパッシング方法）を実行する。ＭＰＭはターボ等化器の種類に属すると解釈でき、それによってソフト確率推定（例えば、ＬＬＲ）は復調処理３２０と復号化処理３３０との間でやりとりされる。
【０１４３】
いくつかの実施形態において、パンクチャおよびデパンクチャは含まれない。それらの実施形態において、処理３２５はデパンクチャを行わないデインターリーブ処理と解釈される。処理３３５はパンクチャを行わないインターリーブ処理と解釈される。
【０１４４】
フィルタモジュール３１０は、ストリーム｛ｒk｝をフィルタリングして、受信シンボルストリーム｛ｙk｝を生成する。フィルタモジュール３１０は低域フィルタでもよい。いくつかの実施形態において、フィルタモジュール３１０は、２の倍数でサンプリングレートを減少させるために使用される線形位相、ＦＩＲ、かつ低域のフィルタである。フィルタモジュール３１０は、多相構造で構成された２つのＦＩＲフィルタ（１つは実サンプル用、もう１つは虚サンプル用）を備えてもよい。一実施形態において、上記２つのＦＩＲフィルタは、それぞれ４９個のタップを有する。ただし、フィルタタップの数は、他の様々な値を用いてもよい。いくつかの実施形態において、上記２つのＦＩＲフィルタの係数は、パークスマクレランアルゴリズムを用いて設計される。図５は、一実施形態による、フィルタモジュール３１０の周波数特性を示す。フィルタモジュール３１０の出力は、シンボル毎に１つのサンプルを生成するようにサブサンプリングされてもよい。
【０１４５】
ＰＤＦモジュール３１５は、受信シンボルシーケンス｛ｙk｝の各シンボルｙkに対して動作して確率値｛ｐ（ｙk｜ｖi,j）｝の対応組を生成する。この場合ｖi,jは、復調トレリスにおいて状態ｉから状態ｊへの遷移に関連した出力である。
【０１４６】
復調処理３２０は、ＰＤＦモジュール３１５によって提供された確率値と、インターリーブ／パンクチャ処理３３５によって提供された事前確率に対して動作し、それによってフィードフォワード情報を生成する。フィードフォワード情報は、処理３２５へ供給される。処理３２５はこのフィードフォワード情報に対してデパンクチャおよびデインターリーブを実行して、中間情報を生成する。この中間情報は復号化処理３３０に提供される。復号化処理３３０は中間情報に対して動作してフィードバック情報を生成する。このフィードバック情報は処理３３５に提供される。処理３３５はこのフィードバック情報に対してインターリーブおよびパンクチャを実行して、事前確率を生成する。
【０１４７】
ＭＰＭは反復的に動作する。すなわち、復調処理３２０が動作し、その後復号化処理３３０が動作する。その後、復調処理３２０がまた動作して、その後復号化処理３３０がまた動作する。これが周期的に行われる。図において各周期を「反復」と呼ぶ。反復が進むと、２つの処理間でやりとりされた情報は、望ましくは正しい答、すなわち元の送信ビット｛ａk｝と一致した答に向かって収束を始める。反復は、許容可能なビット信頼性が得られるまで続けられる。（受信シンボルのベクトルｙは一連の反復を通して一定である）。復調処理３２０と復号化処理３３０との間でやりとりされる情報はメッセージと解釈されるため、この反復処理は「メッセージパッシング」方法と呼ばれる。
【０１４８】
復調処理３２０と復号化処理３３０との間でやりとりされる情報は軟情報であって、硬判定ではない。（「硬」はバイナリの同義語である）。したがって、処理３２０および３３０のそれぞれは、軟入力軟出力（ＳＩＳＯ）モジュールと呼ぶことができる。
【０１４９】
図４に戻って参照すると、処理３３５は、復号化処理３３０によって生成された軟情報（フィードバックＬＬＲなど）に対してインターリーブおよびパンクチャを実行する。この場合のインターリーブは、インターリーバ２２０によって使用されるものと同一のパターンに基づく。また、パンクチャはパンクチャ部２３０によって使用されるものと同一のパターンに基づく。ただし、処理３３５は復号化処理３３０によって生成される軟情報（例えばＬＬＲなど）に対して動作する一方、インターリーバ２２０およびパンクチャ部３３５はビットに対して動作する。インターリーバ／パンクチャ部３３５は、マッピング部２４０から来るシンボルの順番と同一の順番で復号化処理３３０からのフィードバックＬＬＲを並び替える。
【０１５０】
処理３２５は、復調処理３２０によって生成された軟情報（シンボルＬＬＲなど）に対してデパンクチャおよびデインターリーブを実行する。デパンクチャは、パンクチャ部２３０によって使用されるパンクチャパターンの疑似逆に基づく。パンクチャパターンが情報を捨てる場合、疑似逆は零を投入する。例えば、パンクチャパターンが２つおきに要素を捨てる場合、疑似逆は
（ｓ 1，ｓ２，ｓ３，ｓ４，ｓ５，ｓ６，・・・）→（ｓ1，ｓ２，０，ｓ３，ｓ４，０，ｓ５，ｓ６，０，・・・）
のようになる。所与のシンボルに対する対数尤度比（ＬＬＲ）が零に等しい場合、シンボルが−１に等しくなる確率は、シンボルが＋１に等しくなる確率と定義上等しくなる。したがって、零ＬＬＲ値を所与のシンボル位置に投入すると、シンボル位置から元々捨てられたシンボルの値に関して全く無視する状態となる。
【０１５１】
いくつかの実施形態において、零を投入する代わりに、デパンクチャ動作が復号化処理３３０よってあらかじめ算出された値を投入する。このより洗練された形態のデパンクチャによって収束速度は高まる。すなわち、収束を得るために必要な反復の数を減らすことができる。
【０１５２】
処理３２５の一部として実行されるデインターリーブ動作は、インターリーバ２２０によって使用されるパターンの逆に基づく。したがって、このデインターリーブ動作によって、畳込みエンコーダ２１０から来るビット順に対応する順番にＬＬＲを並び替えられる。
【０１５３】
復調処理３２０は、基本のトレリスに基づいて動作する。基本のトレリスとは、例えば、以下によって与えられる線形フィルタと関連づけられたトレリスである。
【数３】
0005406369.tif 000004
ここで、各係数｛ｈj｝は、実値（または複素数値である可能性が高い）である。シンボル組の時間指数ｋの各値と各シンボルｘに対して、復調処理３２０は、送信シンボルｘkが受信シンボルベクトルｙによって与えられたｘに等しかった確率を算出してもよい。シンボル組が｛＋１，−１｝（例えば、ＱＢＬ−ＭＳＫまたはバイナリＰＳＫ）の場合、復調処理３２０は、送信シンボルが＋１であった確率と送信シンボルが−１であった確率とを算出してもよい。
【０１５４】
復調処理３２０はフォワード／バックワードアルゴリズムを実行してもよい。このフォワード／バックワードアルゴリズムは、フォワードパスと、バックワードパスと、統合動作とを含む。フォワードパスは、各時間ステップにおける「アルファ」値のベクトルを計算するフォワード方向に復調トレリス上を移動する。バックワードパスは、各時間ステップにおける「ベータ」値のベクトルを計算するバックワード方向に復調トレリス上を移動する。（このフォワードパスおよびバックワードパスは、必要に応じて並行して実行されてもよい）。統合動作は、アルファ値とベータ値とを合成して、各時間指数における送信シンボルに対する対数尤度比（ＬＬＲ）、例えば対数尤度比Ｌ（ｘk｜ｙ）を形成する。このフォワードパス、バックワードパスおよび統合動作は、それぞれ「ガンマ」値組を使用する。このガンマ値は、局所確率情報（シンボル観測ベクトルｙに基づく）と復号化処理３３０によって生成された事前確率とを包含する。フォワード／バックワードアルゴリズムについての詳細は、記事「ターボ復調」（ＲａＩｆ Ｋｏｅｔｔｅｒ等、ＩＥＥＥ Ｓｉｇｎａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｍａｇａｚｉｎｅ、２００４年１月発行）を参照するとよい。
【０１５５】
いくつかの実施形態において、所与の時間ｎにおける復調トレリスの状態Ｓnは以下によって与えられる。
Ｓn＝｛θn，Ｘn-1，Ｘn-2，Ｘn-3｝
【数４】
0005406369.tif 000005
ここで、｛Ｘn-1，Ｘn-2，Ｘn-3｝は、前の３つのシンボルを表す。ｈfは変調指数である。Ｌは、受信機における位相整形フィルタのインパルス応答の長さ（シンボル周期毎）である。変調指数ｈfは、変調位相が非変調参照値：ｈf＝Δθに対して変化する範囲を示す。Δθは、ピーク位相変化を表す。
【０１５６】
いくつかの実施形態において、受信機はＭＳＫ型変調に特化している。そのような一実施形態において、ｘn∈｛−１，＋１｝かつｈf＝１／２、Ｌ＝４である。ｈf＝１／２のため、その位相に対して以下の４つの可能な値が存在する。
【数５】
0005406369.tif 000006
【０１５７】
したがって、状態空間は、図６の状態表に示すように４×２×２×２＝３２の状態を含む。位相遷移、すなわち現在の位相θnから次の位相θn＋１への位相は以下によって与えられる。
【数６】
0005406369.tif 000007
【０１５８】
復号化処理３３０は、フォワード／バックワードアルゴリズムを用いて、処理３２５によって提供された入力ＬＬＲ（Ｌ（ｂk｜ｙ）｝に対して動作して、フィードバックＬＬＲ（Ｌ（ｂk｜ｐ））を生成する。ここで、
ｐ＝（Ｐ（ｂ1｜ｙ），（Ｐ（ｂ2｜ｙ），．．．（Ｐ（ｂN｜ｙ））T
である。さらに、ＭＰＭの最後の反復において、復号化処理３３０は、元のビットストリームのビットａk毎に出力ＬＬＲＬ（ａk）を算出してもよい。復号化処理３３０は、ハードリミッタ３４０に対して出力ＬＬＲ｛Ｌ（ａk）｝を提供する。ハードリミッタは、以下の規則にしたがってビットａk毎に推定Ａkを生成する。
ＬＬＲ（ａk）＞０ならば、Ａk＝１、その他の場合はＡk＝０
【０１５９】
いくつかの実施形態において、復号化処理３３０は、ＭＡＰデコーダの種類に属する。ただし、他の実施形態も考えられる。
【０１６０】
復号化処理３３０は、畳込みエンコーダ２１０の構造に対応するトレリスに基づいて動作してもよい。一実施形態において、畳込みエンコーダ２１０は、図７に示す構造を有する。ただし、その他の様々な構造が可能である。
【０１６１】
図７に示した畳込みエンコーダ２１０は、率１／２でＫ＝５である。（畳込みエンコーダの率とは、入力ビット数対出力ビット数の比率である。パラメータＫはエンコーダの制約長で、出力ビットに影響する現在の入力を含むビット数を示す）。各加算部は、２を法とする加算をバイナリ演算子に対して実行するように構成される。「Ｄ」とされている部材は、遅延部である。
【０１６２】
図示のエンコーダの所与の時間における状態は、４つの遅延素子Ｄの内容によって定義される。図７の表記において、状態は４タプル（Ｓ1，Ｓ2，Ｓ3，Ｓ4）によって与えられる。４つの遅延素子が入力に対して直列に接続されているため、状態は（ａk-4，ａk-3，ａk-3，ａk-i）の形状を有する。ここで、ａk-1、ａk-2、ａk-3、ａk-4は、バイナリ入力シーケンス｛ａk｝の前の値である。したがって、１６の異なる状態が存在する。
【０１６３】
復号化処理３３０は、以下の関係に基づいて、入力ＬＬＲ値（Ｌ（ｂk｜ｙ））を確率に変換する。
【数７】
0005406369.tif 000008
【０１６４】
ルックアップテーブル（ＬＵＴ）を使用して、各入力ＬＬＲを確率値に変換してもよい。減算によって、相補確率値が得られる。これによって、入力ＬＬＲ毎に２つの確率値が得られる。各対（ｂ2k-1，ｂ2k）に対して、以下の確率積がフォワード／バックワード演算において使用される。
Ｐ（ｂ2k-1＝０｜ｙ）Ｐ（ｂ2k＝０｜ｙ）
Ｐ（ｂ2k-1＝０｜ｙ）Ｐ（ｂ2k＝１｜ｙ）
Ｐ（ｂ2k-1＝１｜ｙ）Ｐ（ｂ2k＝０｜ｙ）
Ｐ（ｂ2k-1＝１｜ｙ）Ｐ（ｂ2k＝１｜ｙ）
【０１６５】
フォワード／バックワードアルゴリズムの結果として得られた確率値Ｐ（ｂj＝０｜ｐ）とＰ（ｂj＝１｜ｐ）は、例えば対数関数のルックアップテーブルを用いてＬＬＲ値に変換される。これらのＬＬＲ値（「フィードバックＬＬＲ」）は、インターリーブ／パンクチャ処理３３５に与えられる。
【０１６６】
１組の実施形態において、受信機１２０は、図４に示す処理動作を実行するようにプログラムされたマルチプロセッサ演算システムを備える。このマルチプロセッサ演算システムは、相互接続して格子を形成するセルアレイを含んでもよい。各セルは、処理要素（ＰＥ）と１つ以上の「データメモリ／ルーティングユニット」（ＤＭＲ）を備えてもよい。図８は、マルチプロセッサ演算システムの一実施形態を示し、４×８のセルアレイを有する。分散制御ロジック（ＤＣＬ）７１０は、例えばプログラムコードやデータをアレイ中の各ＰＥに送ることによって、アレイの動作を制御してもよい。さらに、ＤＣＬ７１０は、ＰＥ（またはＰＥのサブセット）から結果を回収し、その結果を受信機１２０内の他の処理手段に渡してもよい。各ＰＥは、自分の命令メモリを有し、それによって必要に応じて独自のタスクを実行するようにプログラムされてもよい。ＤＣＬ７１０は、アレイの最初の行にのみ接続されているように図示されている。しかしながら、ＤＣＬ７１０をアレイに接続する方法に対して他の様々な実施形態が考えられる。
【０１６７】
いくつかの実施形態において、上記マルチプロセッサ演算システムは、アレイ中のＰＥの第１のサブセットに対してフィルタモジュール３１０を実行し、アレイ中のＰＥの第２のサブセットに対してＰＤＦモジュール３１５を実行し、アレイ中のＰＥの第３のサブセットに対して復調処理３２０を実行し、アレイ中のＰＥの第４のサブセットに対してデインターリーブ／デパンクチャ処理３２５を実行し、アレイ中のＰＥの第５のサブセットに対して復号化処理３３０を実行し、アレイ中のＰＥの第６のサブセットに対してインターリーブ／パンクチャ処理３３５を実行するようにプログラムされてもよい。ここで、第１、第２、第３、第４、第５、第６のサブセットは、アレイ中のＰＥの互いに素なサブセットである。そのような一実施形態を図９に示し、以下で説明する。
【０１６８】
図９は、図４の処理動作をパイプライン化および並列化したものを示す。ここで、マルチプロセッサ演算システムは、少なくとも７１個の処理要素（ＰＥ）と７８個のデータメモリを有するものとする。パイプラインの各段は、Ｎ単位時間動作するように構成されてもよい。第１の段は、入力処理３０５と、フィルタモジュール３１０とを含む。フィルタモジュール３１０は、１つの処理要素（ＰＥ）と２つのデータメモリとを用いて実行されてもよい。第２の段は、ＰＤＦモジュール３１５を含む。ＰＤＦモジュール３１５は２つのＰＥと８つのＤＭＲとを用いて実行されてもよい。２つのＰＥは、パケット中のシンボルデータの対応部分に対して並行して動作してもよい。
【０１６９】
第３の段は、復調処理３２０と、デインターリーブ／デパンクチャ処理３２５と、復号化処理３３０と、インターリーブ／パンクチャ処理３３５とを含む。復調処理３２０は、パケット中のシンボルデータの対応部分に並行して動作する３２個のＰＥ／ＤＭＲ対を用いて実行されてもよい。デインターリーブ／デパンクチャ処理３２５は、２つのＰＥと２つのＤＭＲとを用いて実行されてもよい。復号化処理３３０は、処理３２５によって提供された軟情報の対応部分に並行して動作する３２個のＰＥ／ＤＭＲ対を用いて実行されてもよい。インターリーブ／パンクチャ処理３３５は、２つのＰＥと２つのＤＭＲとを用いて実行されてもよい。対応する処理間での通信効率を上げるように、様々なサブセットのＰＥを地理的に配置してもよい。
【０１７０】
終段は、ハードリミッティングを実行して元の情報ビットａkに対する推定Ａkを決定する出力処理３４０を含む。
【０１７１】
図１０は、マルチプロセッサ演算システム上の図４の処理動作をパイプライン化および並列化した別のものを示す。本実施形態において、復調処理３２０および復号化処理３３０は、ブロック９１０に示す３２個のＰＥ／ＤＭＲ対からなる同一組に対して実行される。さらに、デインターリーブ／デパンクチャ処理３２５およびインターリーブ／パンクチャ処理３３５は、ブロック９２０に示す２つのＰＥ／ＤＭＲ対からなる同一組に対して実行される。
【０１７２】
いくつかの実施形態において、各ＰＥの命令メモリは小容量のため、復調プログラム全体および復号化プログラム全体を同時に格納できない。したがってそれらの実施形態において、マルチプロセッサ演算システムの分散および制御ロジックは、復調プログラムおよび復号化プログラムをブロック９１０の３２個のＰＥそれぞれの命令メモリに交互に読み込むように構成してもよい。
【０１７３】
図８および図９は、パイプライン段の処理モジュールにおけるＰＥおよびＤＭＲの数に対する特定の値に関して説明しているが、各値は他の様々な値をとってもよい。そのため、図８および図９は、幅広く実現可能なものの中の２つの特定のものとして解釈されるものである。
【０１７４】
いくつかの実施形態において、シーケンスＸkの各シンボルを、送信機１１０による送信前に、トレーニングシンボルとともにパケットに読み込む。一実施形態において、パケットは、図１１に示すパケットを有する。パケットは、ペイロードシーケンスと交互にトレーニングシーケンス（「連続プローブ」とも呼ばれる）を含む。各トレーニングシーケンスの長さは、３２シンボル。各ペイロードシーケンスの長さは３２８シンボルである。シンボル１４４１からシンボル１４７２までのトレーニングシーケンスは、次のパケットの最初の連続プローブ（すなわち、シンボル１からシンボル３２）として再利用される。したがって、事実上パケット毎に１４４０シンボルがある。本明細書に記載される発明原理は、パケット長、パケット毎のペイロードシーケンスの数、ペイロードシーケンス毎のシンボルの数、またはトレーニングシーケンス毎のシンボルの数に依存するものではない。それらの各パラメータは、幅広く様々な値をとることができる。
【０１７５】
受信パケット中の各ペイロードシーケンスに対して、復調処理３２０は、ペイロードシーケンスに対応する各送信シンボルのＭＡＰ推定を演算してもよい。ペイロードシーケンス全体に対してフォワード／バックワードアルゴリズムを実行する代わりに、ペイロードシーケンスの重複部分を１組のプロセッサに分散してもよい。例えば上述のように、それらのプロセッサは、フォワード／バックワードアルゴリズムを各部に対して並行して実行してもよい。したがって、ペイロードシーケンス全体に対するフォワード／バックワードアルゴリズムの正味の影響を、非常に短時間で得られる。本明細書において、ペイロードシーケンスの重複部分をウィンドウと呼ぶ。
【０１７６】
図１２は、受信パケットの最初のペイロードシーケンスにわたる８つの重複ウィンドウの例を示す。このデータの８つのウィンドウは、８つのプロセッサに対してそれぞれ分散されて、並列して実行されてもよい。パケットの残りの３つのペイロードシーケンスのそれぞれは、８つのウィンドウによって同様に網羅されてもよい。それによって、パケット中の全ペイロードデータは、３２個ウィンドウで網羅できる。３２個のウィンドウは、例えば上述のように、３２個のプロセッサにそれぞれ分散して、並行して処理してもよい。各プロセッサは、３２個のウィンドウの指定された１つに対してフォワード／バックワードアルゴリズムを実行してもよい。図１２は、各ウィンドウの構造化の一例として解釈されるべきものである。幅広く様々なその他の実施形態は、ペイロードシーケンス毎のウィンドウの数に対して異なる数を有することも考えられる。
【０１７７】
図１２に示すように、第１のペイロードシーケンスのウィンドウ＃１（下から２番目のウィンドウ）は、シンボル位置７３からシンボル位置１３２まで延びている。図１３Ａは、ウィンドウ＃１に対するフォワード演算間隔、すなわち、一実施形態にしたがって、フォワードパス演算が実行されるシンボル位置の間隔を示す。また、フォワード「助走」間隔（本明細書では「フォワード収束間隔」とも呼ばれる）、すなわち、フォワードパス演算が収束の処理を行っている最初の間隔を示す。助走間隔において算出されたアルファベクトルは、信頼できない（または信頼に十分に足らない）と見なされるため、出力ＬＬＲの演算に使用されない。助走間隔の後（右）に算出されたアルファベクトルは、信頼できる（すなわち有効）と見なされる。フォワード助走間隔後のフォワード演算間隔の部分は、本明細書においてフォワード有効間隔と呼ばれる。
【０１７８】
図１３Ｂは、ウィンドウ＃１に対するバックワード演算間隔、すなわち、バックワードパス演算が実行されるシンボル位置の間隔を示す。また、バックワード「助走」間隔（本明細書では「バックワード収束間隔」とも呼ばれる）、すなわち、バックワードパス演算が収束の処理をまだ行っている最初の間隔を示す。バックワード助走間隔において算出されたベータベクトルは、信頼できない（または信頼に十分に足らない）と見なされるため、出力ＬＬＲの演算に使用されない。助走間隔の後に算出されたベータベクトルは、信頼できる（すなわち有効）と見なされる。バックワード助走間隔後（すなわち左）のバックワード演算間隔の部分は、本明細書においてバックワード有効間隔と呼ばれる。
【０１７９】
フォワード助走間隔およびバックワード助走間隔は、図１３Ａおよび１３Ｂにおいて１０シンボルの長さであると示しているが、幅広く様々な他の長さも可能である。所与の実施形態において選択される長さの値は、Ｓ／Ｎ比に依存してもよい。Ｓ／Ｎ比が高い環境は、Ｓ／Ｎ比が低い環境よりも小さな助走長を必要とする場合がある。また、フォワード助走間隔およびバックワード助走間隔が同一の長さでなくてもよい。長さが異なる場合の実施形態も考えられる。
【０１８０】
出力ＬＬＲは、フォワード有効間隔およびバックワード有効間隔の交差点に対応するシンボル位置に対して演算される。したがって、図１３Ａおよび１３Ｂに示す例において、出力ＬＬＲは、シンボル位置８３から１２２に対して演算される。
【０１８１】
図１４は、２つの連続ウィンドウ、すなわちウィンドウ＃１および＃２に対する助走間隔と出力領域との関係を示す。２つのウィンドウに対する出力領域は互いに素であり、その間にギャップがないことがわかる。ウィンドウ＃１の出力領域は、位置８３から位置１２２までである。ウィンドウ＃２の出力領域は、位置１２３から位置１６２までである。同様に、８つのウィンドウすべての出力領域は互いに素であり、ペイロードシーケンスの全範囲を網羅する。
【０１８２】
ウィンドウ＃０（図１２下部のウィンドウ）とウィンドウ＃７（図１２上部のウィンドウ）とは、ペイロードシンボルに加えてトレーニングシンボルも含む点で異なる。ウィンドウ＃０の最初のシンボルはトレーニングシンボルである。ウィンドウ＃７の最後の数シンボルはトレーニングシンボルである。フォワードパス演算が既知のトレーニングシンボルに基づいて開始できるため、ウィンドウ＃０に対するフォワードパスは助走間隔を必要としない。同様に、バックワードパス演算が既知のトレーニングシンボルデータに基づいて開始できるため、ウィンドウ＃７はバックワード助走間隔を必要としない。
【０１８３】
各送信シンボルの初期事前確率は、シンボルが＋１に等しい確率の場合０．５に設定され、シンボルが−１に等しい確率の場合０．５に設定される。各トレーニングシーケンスが既知の場合、トレーニングシーケンス中の各シンボルのシンボル確率は、適宜、１および０に設定される。各３２シンボルトレーニングシーケンスの最初のシンボルは送信データに依存しており、したがって受信機では不明である。そのため、その確率は１／２に設定される。
【０１８４】
復号化処理３３０は、フォワード／バックワードアルゴリズムを使用して、元のビットストリーム｛ｂj｝の各ビットｂjに対するフィードバック確率Ｐ（ｂj＝０｜ｐ）およびＰ（ｂj＝１｜ｐ）を演算してもよい。これを受けて、復調処理３２０と関連して上述のように、トレーニング情報がなくても、重複ウィンドウストラテジを用いて復号化処理３３０は実行されてもよい。したがって、デインターリーブ／デパンクチャ処理３２５によって生成された入力ＬＬＲ｛Ｌ（ｂj｜ｙ）｝を分散して重複ウィンドウを設定してもよい。例えば、図８および図９を参照して上述したように、フォワード／バックワードアルゴリズムは各ウィンドウに対して並行して実行してもよい。いくつかの実施形態において、復号化処理３３０によって使用されたウィンドウは、復号化ウィンドウがトレーニング情報を含まないことを除いて、復調処理３２０によって使用されたウィンドウに対応する。
【０１８５】
いくつかの実施形態において、受信機１２０は、復調処理３２０と復号化処理３３０との間でやりとりされる軟情報（ＬＬＲ）に含まれる内部情報の量を段階的に増加させる機構を使用してもよい。内部情報の量は、（外部情報と比べて）パスメトリックにおける信頼度が改善するにつれて段階的に増加させてもよい。内部情報が直接フィードバックを構成するため、この機構を「段階的直接フィードバック」と呼ぶ。許容可能なビットエラーの動作を実現するために必要とされる反復の数に関連して、やりとりされるメッセージに内部情報を挿入することは、収束を加速化する上で有効である。しかしながら、この内部情報は収束を誤った結果に導く可能性がある。したがって、内部情報は最初の反復か２回の反復において無視し、ビット信頼性が高まるにつれて、可変乗数λ∈［０，１］を用いて段階的に挿入するとよい。（表記［ａ，ｂ］は、｛実数直線上のｘ：ａ≦ｘ≦ｂ｝の閉じた間隔を表す）。例えば、復調処理３２０によって生成された出力ＬＬＲ｛Ｌ（ｘk｜ｙ）｝は以下の規則で判断される。
Ｌ（ｘk｜ｙ）＝Ｌext（ｘk｜ｙ）＋λiＬint（ｘk｜ｙ）
λi＝（ｉ−１）／Ｎ
ここで、Ｌext（ｘk｜ｙ）は、受信シンボルベクトルｙによって与えられたシンボルｘkの外部ＬＬＲ、Ｌint（ｘk｜ｙ）は受信シンボルベクトルｙによって与えられたシンボルｘkの内部ＬＬＲ、ｉは１からＮまで実行される反復指数である。
【０１８６】
同様に、復号化処理３３０によって生成された出力ＬＬＲ｛Ｌ（ｂk｜ｐ）｝は、以下の規則によって判断されてもよい。
Ｌ（ｂk｜ｐ）＝Ｌext（ｂk｜ｐ）＋λiＬint（ｂk｜ｐ）
λi＝（ｉ−１）／Ｎ
【０１８７】
変数λと反復指数ｉとの間には、幅広く様々な関数関係が可能である。上記で与えられた線形関係は短時間で演算されるが、幅広く様々な他の実施形態も考えられる。
【０１８８】
１組の実施形態において、受信シンボルを処理して送信情報を再生する方法は、図１５Ａに示すように実行されてもよい。図９および図中に記載の説明は、本方法の一実施形態として解釈されてよい。
【０１８９】
１４１０において、シンボルデータシーケンスが受信されてもよい。例えば、このシンボルデータシーケンスは、図３や図９を参照して上述したように、フィルタモジュール３１０によって提供されてもよい。
【０１９０】
１４１５において、２つ以上のプロセッサからなる第１の組が、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスの２つ以上の対応サブシーケンスに対して復調処理を並行して実行し、フィードフォワード情報の２つ以上の対応ブロックを生成する。例えば、図９のブロック３２０を参照するとよい。
【０１９１】
１４２０において、１つ以上のプロセッサからなる第２の組が、フィードフォワード情報の２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデパンクチャおよびデインターリーブを実行して、修正データシーケンスを生成する。例えば、図９のブロック３２５を参照するとよい。
【０１９２】
１４２５において、２つ以上のプロセッサからなる第３の組が、修正データシーケンスの２つ以上の対応サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成する。例えば図９のブロック３３０を参照するとよい。
【０１９３】
１４３０において、１つ以上のプロセッサからなる第４の組が、フィードバック情報の２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブおよびパンクチャを実行して、フィードバックデータシーケンスを生成する。例えば図９のブロック３３５を参照するとよい。
【０１９４】
１４３５において、１４１５、１４２０、１４２５、および１４３０を含む処理の組を、複数回繰り返してもよい。一実施形態において、反復の回数は所定数Ｎmaxである。別の実施形態において、反復の数は、所定の最小閾値に対するシンボル確率の大きさによって決定されてもよい。
【０１９５】
１４４０において、２つ以上のプロセッサからなる第３の組のプロセッサは並行して動作し、修正データシーケンスの２つ以上の対応サブシーケンスに基づいて元の情報ビットに対して、軟推定（例えば、ＬＬＲ）を生成する。
【０１９６】
いくつかの実施形態において、追加の処理を実行して、軟推定に基づく受信メッセージを形成してもよい。例えば、この軟推定に対してハードリミッティングが実行されて、元の情報ビットに対する硬推定を得てもよい。この硬推定はユーザへの出力として提供されたり、ネットワーク上に送出されたり、将来的な使用のために保存されてもよい。
【０１９７】
いくつかの実施形態において、この硬推定を使用して出力信号を生成し、その出力信号をユーザデータのパケットを作成するために使用してもよい。
【０１９８】
いくつかの実施形態において、第１、第２、第３および第４の組のプロセッサは、プロセッサの列から選択される。この場合、プロセッサ列のプロセッサは相互接続されて、平面矩形格子（または高次元格子）を形成する。第１、第２、第３および第４の組のプロセッサは、互いに素の組であることが望ましい。アレイのうちのプロセッサは、独立してプログラム可能であってもよい。
【０１９９】
いくつかの実施形態において、第１の組のプロセッサによって実行された復調処理によって、送信シンボルに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードフォワード情報のブロックを作成する。例えば上述のように、この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【０２００】
いくつかの実施形態において、第３の組のプロセッサによって実行された復号化処理によって、符号化ビットに関する内部情報および外部情報が作成される。また、第３の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードバック情報のブロックを作成する。例えば上述のように、この混合情報に含まれる内部情報の量は、前記組の動作の現在までに完了した反復数の関数として増加してもよい。
【０２０１】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含む。このフォワード収束領域は、復調処理のフォワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。例えば、図１３Ａを参照した上記説明を参照するとよい。一実施形態において、例えば図１２に示すようにシンボルデータシーケンスの２つ以上のサブシーケンスのそれぞれは、サブシーケンスのうちの最初のサブシーケンスを除いて、フォワード収束領域を含む。
【０２０２】
いくつかの実施形態において、フォワード収束領域の長さを、動作の組のうちで現在までに完了した反復数の関数として減少させる。
【０２０３】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、バックワード収束領域を含む。このバックワード収束領域は、復調処理のバックワードトレリスの走査において収束を得るために使用されるが、フィードバックワード情報の対応ブロックを作成するために使用されない。例えば、図１３Ｂを参照した上記説明を参照するとよい。一実施形態において、例えば図１２に示すようにシンボルデータシーケンスの２つ以上のサブシーケンスのそれぞれは、サブシーケンスのうちの最後のサブシーケンスを除いて、バックワード収束領域を含む。
【０２０４】
いくつかの実施形態において、バック収束領域の長さを、動作の組のうちで現在までに完了した反復数の関数として減少させる。
【０２０５】
いくつかの実施形態において、デパンクチャの動作は、修正データシーケンスのパンクチャ位置にあらかじめ演算された値を投入することを含む。この場合、あらかじめ演算された値は、動作の組の前の反復における（復号化処理で）演算されたフィードバック情報のブロックにおける対応位置からの指定要素（ＬＬＲ成分）である。例えば、シーケンス｛Ｌ（ｂk｜ｙ）｝のパンクチャ位置には、前の反復の復号化処理で演算されたフィードバックシーケンス｛Ｌ（ｂk｜ｐ）｝における対応位置からの値が投入（充填）されてもよい。
【０２０６】
いくつかの実施形態において、前記復調処理は、第１の組の各プロセッサが対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は、値１／Ｎs1などの小さな正の数と等しい。Ｎs1は復調トレリスにおける状態数である。
【０２０７】
いくつかの実施形態において、前記復号化処理は、第３の組の各プロセッサが対応する復号化トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第３の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のデータ位置でアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は、値１／Ｎs2などの小さな正の数と等しい。Ｎs2は復号化トレリスにおける状態数である。
【０２０８】
１組の実施形態において、システム１４５０は、図１５Ｂに示すように構成されてもよい。前記システム１４５０は、制御ユニット１４５５と、２つ以上のプロセッサからなる第１の組１４６０と、２つ以上のプロセッサからなる第２の組１４７０とを備えてもよい。図７および図８を参照して上述された前記システムは、システム１４５０の実施形態として解釈されてもよい。
【０２０９】
２つ以上のプロセッサからなる第１の組１４６０は、第１のプログラムコードで構成されてもよい。この場合、第１のプログラムコードは、第１の組のプロセッサに実行されると、第１の組のプロセッサがフィードバックデータシーケンスの対応部分を用いて、受信シンボルシーケンスの重複部分に対して復調処理を並行して実行するようにして、フィードフォワード情報を得てもよい。第１の組の各プロセッサは、第１のプログラムコードを格納する命令メモリを備えてもよい。
【０２１０】
２つ以上のプロセッサからなる第２の組１４７０は、第２のプログラムコードで構成されてもよい。この場合、第２のプログラムコードは、第２の組のプロセッサに実行されると、第２の組のプロセッサが、フィードフォワード情報にデインターリーブおよびデパンクチャを実行したものの重複部分に対して復号化処理を並行して実行するようにして、フィードバック情報を得てもよい。フィードバックデータシーケンスは、フィードバック情報にインターリーブおよびパンクチャを実行したものである。第２の組の各プロセッサは、第２のプログラムコードを格納する命令メモリを備えてもよい。
【０２１１】
制御ユニット１４５５は、交互に第１の組の各プロセッサに第１のプログラムコードを実行させ、第２の組の各プロセッサに第２のプログラムコードを実行させるように構成されてもよい。例えば、制御ユニットは、制御プロセッサとメモリとを備えてもよい。ここで、メモリは制御プロセッサによって実行可能なプログラム命令を格納する。実行されると、プログラム命令は制御ユニットに第１の組の各プロセッサと第２の組の各プロセッサとを交代させるようにする。
【０２１２】
プロセッサの第２の組１４７０は、例えば様々に上述のように、フィードフォワード情報にデインターリーブおよびデパンクチャを実行したものの重複部分に対して並行して動作して、元の情報ビットに対する推定を生成するように構成されてもよい。
【０２１３】
いくつかの実施形態において、例えば様々に上述のように、プロセッサの第１の組１４６０は、復調処理および復号化処理を含む１組の動作の現在までに完了した反復数の関数として、フィードフォワード情報に含まれる内部情報の量を増加させるように構成されてもよい。さらに、例えば様々に上述のように、プロセッサの第２の組１４７０は、現在までに完了した反復数の関数として、フィードバック情報に含まれる符号化ビットに関する内部情報の量を増加させるように構成されてもよい。
【０２１４】
例えば図１３Ａを参照して上述したように、いくつかの実施形態において、受信シンボルシーケンスの重複部分の少なくとも所与の一部はフォワード演算間隔を含む。第１の組のプロセッサのうちの所与のプロセッサは、復調処理の一部としてフォワード演算間隔において、（その命令メモリ内に格納されている第１のプログラムコードによって）フォワードパス演算を実行するように構成される。フォワード演算間隔の最初の部分は、フォワードパス演算の収束を得るために使用されるが、フィードフォワード情報の判断のためには使用されない。例えば、図１３Ａを参照して説明したフォワード助走間隔を参照するとよい。
【０２１５】
いくつかの実施形態において、例えば様々に上述のように、上記所与のプロセッサは、復調処理および復号化処理を含む１組の動作の現在までに完了した反復数の関数として、フォワード演算間隔の最初の分の長さを減少させるように構成されてもよい。
【０２１６】
例えば図１３Ｂを参照して上述したように、いくつかの実施形態において、受信シンボルシーケンスの重複部分の所与の一部はバックワード演算間隔を含む。第１の組のプロセッサのうちの所与のプロセッサは、復調処理の一部としてバックワード演算間隔において、（その命令メモリに格納されている第１のプログラムコードによって）バックワードパス演算を実行するように構成される。バックワード演算間隔の最初の部分は、バックワードパス演算の収束を得るために使用されるが、フィードフォワード情報の判断のためには使用されない。例えば、図１３Ｂを参照して説明したバックワード助走間隔を参照するとよい。
【０２１７】
いくつかの実施形態において、システム１４５０は、フィードフォワード情報にデパンクチャおよびデインターリーブを実行して修正データシーケンスを得るように構成された１つ以上のプロセッサからなる第３の組１４６５を含んでもよい。このデパンクチャの動作は、あらかじめ演算された値を修正データシーケンスのパンクチャ位置に投入することを含んでもよい。あらかじめ演算された値とは、例えば様々に上述のように、復号化処理の一部として第２の組の各プロセッサによってあらかじめ演算された値である。
【０２１８】
いくつかの実施形態において、システム１４５０は、例えば様々に上述のように、フィードバック情報にインターリーブおよびパンクチャを実行して修正フィードバックシーケンスを得るように構成された１つ以上のプロセッサからなる第４の組１４７５を含んでもよい。
【０２１９】
いくつかの実施形態において、同一の組の各プロセッサは、インターリーブ／パンクチャおよびデインターリーブ／デパンクチャの両方を司ってもよい。
【０２２０】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサのうちの所与のプロセッサ（任意のプロセッサなど）によって実行されると、所与のプロセッサが、復調処理の一部として対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行するようにする。この場合、フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は、小さな正の数と等しい。
【０２２１】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサのうちの所与のプロセッサ（任意のプロセッサなど）によって実行されると、所与のプロセッサが、復調処理の一部として対応する復調トレリスを介してフォワードパスおよびバックワードパスを実行するようにする。この場合、バックワードパスは、所与のシンボル位置におけるベータベクトルを算出し、ベータベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいベータベクトルを設定することを含む。ここで、ベクトルＥの全成分は、小さな正の数と等しい。
【０２２２】
１組の実施形態において、図１６Ａに示すように、受信シンボルを処理して送信情報を再生する方法を実行してもよい。図１０および図中に記載の説明は、本方法の一実施形態として解釈されてよい。
【０２２３】
１５１０において、シンボルデータシーケンスが受信されてもよい。例えば、このシンボルデータシーケンスは、図３や図１０を参照して上述したように、フィルタモジュール３１０によって提供されてもよい。
【０２２４】
１５１５において、２つ以上のプロセッサからなる第１の組は、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、シンボルデータシーケンスの２つ以上の対応サブシーケンスに対して復調処理を並行して実行し、フィードフォワード情報の２つ以上の対応ブロックを生成する。例えば、図１０のブロック９１０を参照するとよい。
【０２２５】
１５２０において、１つ以上のプロセッサからなる第２の組が、フィードフォワード情報の２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデパンクチャおよびデインターリーブを実行して、修正データシーケンスを生成する。例えば、図１０のブロック９２０を参照するとよい。
【０２２６】
１５２５において、２つ以上のプロセッサからなる第１の組が、修正データシーケンスの２つ以上の対応サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成する。例えば図１０のブロック９１０を参照するとよい。
【０２２７】
１５３０において、１つ以上のプロセッサからなる第２の組が、フィードバック情報の２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブおよびパンクチャを実行して、フィードバックデータシーケンスを生成する。例えば図１０のブロック９２０を参照するとよい。
【０２２８】
１５３５において、１５１５、１５２０、１５２５、および１５３０を含む処理の組を複数回繰り返してもよい。一実施形態において、反復の回数は所定数Ｎmaxである。別の実施形態において、反復の数は、所定の最小閾値に対するシンボル確率の大きさによって決定されてもよい。
【０２２９】
１５４０において、２つ以上のプロセッサからなる第１の組のプロセッサは並行して動作し、修正データシーケンスの２つ以上の対応サブシーケンスに基づいて元の情報ビットに対して、軟推定（例えば、ＬＬＲ）を生成する。
【０２３０】
いくつかの実施形態において、追加の処理を実行して、軟推定に基づく受信メッセージを形成してもよい。例えば、この軟推定に対してハードリミッティングが実行されて、元の情報ビットに対する硬推定を得てもよい。この硬推定はユーザへの出力として提供されたり、ネットワーク上に送出されたり、将来的な使用のために保存されてもよい。
【０２３１】
いくつかの実施形態において、この硬推定を使用して出力信号を生成し、その出力信号をユーザデータのパケットを作成するために使用してもよい。
【０２３２】
いくつかの実施形態において、第１および第２の組のプロセッサは、プロセッサの列から選択される。この場合、例えば上述するように、プロセッサ列のプロセッサは相互接続されて、平面矩形格子（または高次元格子）を形成する。第１および第２の組のプロセッサは、互いに素の組であることが望ましい。プロセッサ列のプロセッサは、独立してプログラム可能であってもよい。
【０２３３】
いくつかの実施形態において、復調処理によって、送信シンボルに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードフォワード情報のブロックを作成する。例えば上述のように、この混合情報に含まれる内部情報の量は、動作の組のうちで現在までに完了した反復数の関数として増加してもよい。
【０２３４】
いくつかの実施形態において、復号化処理によって、符号化ビットに関する内部情報および外部情報が作成される。また、第１の組のプロセッサは、内部情報と外部情報との混合情報に基づいてフィードバック情報のブロックを作成する。例えば上述のように、この混合情報に含まれる内部情報の量は、前記組の動作の現在までに完了した反復数の関数として増加してもよい。
【０２３５】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含む。このフォワード収束領域は、復調処理のフォワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。例えば、図１３Ａを参照した上記説明を参照するとよい。
【０２３６】
いくつかの実施形態において、シンボルデータシーケンスの２つ以上のサブシーケンスの少なくとも１つは、バックワード収束領域を含む。このバックワード収束領域は、復調処理のバックワードトレリスの走査において収束を得るために使用されるが、フィードフォワード情報の対応ブロックを作成するために使用されない。例えば、図１３Ｂを参照した上記説明を参照するとよい。
【０２３７】
いくつかの実施形態において、デパンクチャの動作は、修正データシーケンスのパンクチャ位置にあらかじめ演算された値を投入することを含む。この場合、あらかじめ演算された値は、動作の組の前の反復における復号化処理で演算されたフィードバック情報のブロックの対応位置からの指定要素である。例えば、シーケンス｛Ｌ（ｂk｜ｙ）｝のパンクチャ位置には、前の反復の復号化処理で演算されたフィードバックシーケンス｛Ｌ（ｂk｜ｐ）｝における対応位置からの値が投入（充填）されてもよい。
【０２３８】
いくつかの実施形態において、前記復調処理は、第１の組の各プロセッサが復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は、小さな正の数と等しい。例えば、小さな正の数は値１／Ｎs1でもよい。Ｎs1は復調トレリスにおける状態数である。
【０２３９】
いくつかの実施形態において、前記復号化処理は、第１の組の各プロセッサが復調トレリスを介してフォワードパスおよびバックワードパスを実行することを含む。この場合、第１の組のプロセッサのうちの所与のプロセッサにおいて、フォワードパスは、所与のデータ位置でアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含む。ここで、ベクトルＥの全成分は、小さな正の数と等しい。例えば、小さな正の数は値１／Ｎs2でもよい。Ｎs2は復号化トレリスにおける状態数である。
【０２４０】
いくつかの実施形態において、動作１５１５の反復は、復調プログラムを第１の組のプロセッサのうちの各プロセッサの命令メモリへ読み込むことを含む。この場合、復調プログラムは、第１の組の各プロセッサによって実行されると、プロセッサに、対応シンボルデータサブシーケンスおよびフィードバックデータシーケンスの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。動作１５２５の各反復は、復号化プログラムを第１の組のプロセッサのうちの各プロセッサの命令メモリへ読み込むことを含む。この場合、復号化プログラムは、第１の組の各プロセッサによって実行されると、プロセッサに、修正データシーケンスの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる。これらの実施形態は、例えば、各プロセッサの命令メモリが小容量で復調プログラム全体および復号化プログラム全体の両方を格納できない場合に使用してもよい。
【０２４１】
１組の実施形態において、システム１５５０は、図１６Ｂに示すように構成されてもよい。システム１５５０は、制御ユニット１５５５と、プロセッサの第１の組１５６０とを含んでもよい。図８および図９を参照して説明した前記システムは、システム１５５０の一実施形態として解釈されてもよい。
【０２４２】
２つ以上のプロセッサからなる第１の組１５６０は、少なくとも第１の計算位相時の第１のプログラムコードと、少なくとも第２の計算位相時の第２のプログラムコードとで構成されてもよい。第１のプログラムコードは、例えば様々に上述のように、第１の組のプロセッサに実行されると、第１の組のプロセッサがフィードバックデータシーケンスの対応部分を用いて、受信シンボルシーケンスの重複部分に対して復調処理を並行して実行するようにして、フィードフォワード情報を得てもよい。第２のプログラムコードは、例えば様々に上述のように、第１の組のプロセッサに実行されると、第１の組のプロセッサがフィードフォワード情報にデインターリーブおよびデパンクチャを実行したものの重複部分に対して復号化処理を並行して実行するようにして、フィードバック情報を得てもよい。フィードバックデータシーケンスは、フィードバック情報にインターリーブおよびパンクチャを実行したものである。
【０２４３】
制御ユニット１５５５は、交互に第１の組の各プロセッサに第１のプログラムコードおよび第２のプログラムコードを実行させるように構成されてもよい。例えば、制御ユニットは、制御プロセッサとメモリとを備えてもよい。ここで、メモリは制御プロセッサによって実行可能なプログラム命令を格納する。実行されると、プログラム命令は制御ユニットに第１の組の各プロセッサと第２の組の各プロセッサとを交代させるようにする。
【０２４４】
プロセッサの第１の組１５６０は、例えば様々に上述のように、フィードフォワード情報にデインターリーブおよびデパンクチャを実行したものの重複部分に対して並行して動作して、元の情報ビットに対する推定を生成するように構成されてもよい。
【０２４５】
いくつかの実施形態において、例えば様々に上述のように、プロセッサの第１の組１５６０は、復調処理および復号化処理を含む１組の動作の現在までに完了した反復数の関数として、フィードフォワード情報に含まれる内部情報の量を増加させるように構成されてもよい。さらに、例えば様々に上述のように、プロセッサの第１の組は、現在までに完了した反復数の関数として、フィードバック情報に含まれる内部情報の量を増加させるように構成されてもよい。
【０２４６】
例えば図１３Ａを参照して上述したように、いくつかの実施形態において、受信シンボルシーケンスの重複部分の少なくとも所与の一部はフォワード演算間隔を含む。第１の組のプロセッサのうちの所与のプロセッサは、復調処理の一部としてフォワード演算間隔において、（例えば、上記所与のプロセッサの命令メモリに格納されている第１のプログラムコードによって）フォワードパス演算を実行するように構成されてもよい。図１３Ａを参照して説明したように、フォワード演算間隔の最初の部分は、フォワードパス演算の収束を得るために使用されるが、フィードフォワード情報の判断のためには使用されない。
【０２４７】
いくつかの実施形態において、例えば様々に上述のように、上記所与のプロセッサは、復調処理および復号化処理を含む１組の動作の現在までに完了した反復数の関数として、フォワード演算間隔の最初の分の長さを減少させるように構成されてもよい。
【０２４８】
例えば図１３Ｂを参照して上述したように、いくつかの実施形態において、受信シンボルシーケンスの重複部分の所与の一部はバックワード演算間隔を含む。第１の組のプロセッサのうちの所与のプロセッサは、復調処理の一部としてバックワード演算間隔において、（上記所与のプロセッサの命令メモリに格納されている第１のプログラムコードによって）バックワードパス演算を実行するように構成されてもよい。図１３Ｂを参照して説明したように、バックワード演算間隔の最初の部分は、バックワードパス演算の収束を得るために使用されるが、フィードフォワード情報の判断のためには使用されない。
【０２４９】
いくつかの実施形態において、例えば様々に上述のように、システム１５５０は、また、フィードフォワード情報にデパンクチャおよびデインターリーブを実行して修正データシーケンスを得るように構成された１つ以上のプロセッサからなる第２の組を含んでもよい。このデパンクチャの動作は、あらかじめ演算された値を修正データシーケンスのパンクチャ位置に投入することを含んでもよい。あらかじめ演算された値とは、復号化処理の一部として第１の組の各プロセッサによってあらかじめ演算された値である。
【０２５０】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサのうちの所与のプロセッサ（任意のプロセッサなど）によって実行されると、所与のプロセッサが、復調処理の一部として復調トレリスを介してフォワードパスおよびバックワードパスを実行するようにする。フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含んでもよい。ここで、ベクトルＥの全成分は、小さな正の数と等しい。
【０２５１】
いくつかの実施形態において、第１のプログラムコードは、第１の組のプロセッサのうちの所与のプロセッサ（任意のプロセッサなど）によって実行されると、所与のプロセッサが、復調処理の一部として復調トレリスを介してフォワードパスおよびバックワードパスを実行するようにする。バックワードパスは、所与のシンボル位置におけるベータベクトルを算出し、ベータベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいベータベクトルを設定することを含んでもよい。ここで、ベクトルＥの全成分は、小さな正の数と等しい。
【０２５２】
いくつかの実施形態において、受信機１２０は、並列プロセッサアーキテクチャ（例えば、Ｈｙｐｅｒ−Ｘアーキテクチャなど）を用いて上述の重複ウィンドウ法を実行してもよい。重複ウィンドウ法は、例えば様々に上述のように、受信パケットのいくつかの重複ウィンドウ（サブシーケンス）に対する反復的メッセージパッシングアルゴリズムを並列化する。ウィンドウは受信パケットと比べてサイズが小さいため、待ち時間は大幅に減少し、中間パスメトリックに対するメモリ要件も大幅に縮小する。これによって、助走間隔で演算されたデータが破棄されるため、処理オーバーヘッドはあるものの、メッセージパッシングアルゴリズムが受信パケット全体（各ウィンドウが適宜初期化された場合）に対して実行された場合に得られるものと同様の結果が得られる。
【０２５３】
いくつかの実施形態において、各ＰＥ（処理要素）の命令メモリは、復調プログラムおよび復号化プログラムの両方を格納するのに十分な容量を有する。したがって、ブロック９１０（図１０参照）の各ＰＥは、各半反復の終わりに、プログラムコードを再読み込みするために発生しているウェイト（待ち）内において復調プログラムと復号化プログラムとの間で即座に飛び越しができる。
【０２５４】
他の実施形態において、各ＰＥの命令メモリは容量が小さくて、復調プログラムおよび復号化プログラムを同時に格納できない。そのため、並列プロセッサアーキテクチャの制御ユニットは、各半反復の間に命令メモリを再読み込みしてもよい。すなわち、各半反復の終わりに、復調プログラムの読み込みと復号化プログラムの読み込みを交代させてもよい。なお、各関数が最小限のオーバーレイで直接コードを再利用できるように、プログラムコードをパラメータ化すると、各プログラム全体を格納する必要性は軽減する。
【０２５５】
上述のように、デインターリーブ／デパンクチャユニット３２５は、パンクチャ部２３０がデータを破棄した場所へ零値を挿入してもよい。代替の実施形態において、デインターリーブ／デパンクチャ処理３２５は、零を投入するかわりにメッセージパッシングアルゴリズムの前の反復において復号化処理３３０によって算出された適切なＬＬＲ値Ｌ（ｂk｜ｐ）を投入してもよい。本明細書において、デパンクチャ処理においてあらかじめ演算された情報を用いる方法を、「遡及デパンクチャ」と呼ぶ。連続した各反復のデパンクチャビット位置が、前の反復の各ビット位置に対して求められた推定を再度確認する機会が与えられるコールドスタートから初期化される必要がないため、遡及デパンクチャのねらいは収束を加速することにある。
【０２５６】
上述のように、復調処理および復号化処理の両方がフォワード演算とバックワード演算とを実行する。固定小数点実装において、フォワード演算の結果、全零状態、すなわち、所与のシーケンス位置で算出されたアルファベクトルが零ベクトルに等しい状態になる可能性がある。この状態が起きた場合、何も行わなければ、後続の全アルファベクトルは零に等しくなる（あるアルファベクトルと次のアルファベクトルとの間の関係の線形特性のため）。バックワード演算についても同様である。したがって、フォワード演算の結果、零ベクトルに等しいアルファベクトルとなった場合、アルファベクトルは、成分がすべてεに等しい（εは小さな値）ベクトルＥに等しく設定される。例えば、一実施形態において、ε＝１／Ｎsである。ここでＮsは使用トレリスの状態数である。アルファベクトルの全成分が非負であるため、全零状態の検査は、アルファベクトルの全成分を合計するだけで実行できる。合計が零に等しい場合、全零状態が発生している。（合計が零に等しくない場合、合計を使用してアルファベクトルを正規化してもよい。正規化によって、フォワード演算は、アルファベクトル成分が使用可能な動的領域を確実に有効利用できるようになる）。
【０２５７】
同様に、バックワード演算の結果、ベータベクトルが零ベクトルに等しくなった場合、ベータベクトルはベクトルＥに等しく設定される。この場合も、全零状態発生の検査は、ベータベクトルの成分を合計することによって実行可能である。（合計が零に等しくない場合は、合計を使用してベータベクトルを正規化してもよい）。
【０２５８】
受信機１２０のいくつかの実施形態は、ＳＬＩＣＥ２．１の兵士の無線の波形（Ｓｏｌｄｉｅｒ Ｒａｄｉｏ Ｗａｖｅｆｏｒｍ（ＳＲＷ）を実現するように構成されてもよい。１組の実施形態において、受信機１２０は、２．６４（ＣＰＭ）および０．９３６（ＱＢＬ−ＭＳＫ）Ｍｂ／ｓのいずれか一方ＣＣ Ｍｏｄｅ非拡散データレートで動作するように構成されてもよい。実施形態の別の組において、受信機１２０は、１１２．５および５２．２５ｋｂ／ｓ（ＤＢＰＳＫ）のいずれか一方のＣＣ Ｍｏｄｅ拡散データレートで動作するように構成されてもよい。なお、受信機１２０は、上記または他のデータレートの有限集合に限定されない。
【０２５９】
いくつかの実施形態において、受信機１２０はＳＬＩＣＥ２．１リンク条件を満たすように設計された大規模システムの一部として使用される。図１７は、１組の実施形態による、ＣＣ Ｍｏｄｅデータレートに対するＳ／Ｎ比の表である。変数Ｅbは、ビット毎のエネルギーを表す。変数Ｅsはシンボル毎のエネルギーを表す。変数Ｎ0はノイズパワースペクトル密度を表す。Ｅb／Ｎ0は、ピット毎に正規化された信号対ノイズ比の測定単位である。「Ｃｏｎｖｃｏｄｅ」は、用語「畳込みコード」の縮約形である。
【０２６０】
図１８は、図４の前記方法を並列化するために使用可能な処理システムの一実施形態を示すブロック図である。例えば、この処理システムは、図３、図８、図９、図１４および図１５に開示された方法など、本明細書において開示された方法を実行するために使用可能である。本説明において、処理システムは数学的行列アルゴリズムプロセッサ（ｍａｔｈｅｍａｔｉｃａｌ ｍａｔｒｉｘ ａｌｇｏｒｉｔｈｍ ｐｒｏｃｅｓｓｏｒ：ＭＭＡＰ）と呼ばれる場合がある。ただし、この名称の使用によって、本発明の範囲を限定する意図はない。図示の実施形態において、ＭＭＡＰ１７１０は、複数の動的設定可能なプロセッサ（Ｄｙｎａｍｉｃａｌｌｙ Ｃｏｎｆｉｇｕｒａｂｌｅ  ｐｒｏｃｅｓｓｏｒ：ＤＣＰ）と複数の動的設定通信器（動的に構成可能な通信装置：ＤＣＣ、「動的設定可能通信素子」とも呼ばれる）とを備える。各ＤＣＰおよび各ＤＣＣは、データおよび命令を互いに伝達するために接続されている。本明細書で使用されるように、ＤＣＰはＤＣＰノードとも呼ばれ、ＤＣＣはＤＣＣノードとも呼ばれる。いくつかの実施形態において、ＤＣＰは図１４および図１５を参照して上述したプロセッサの役割を果たす。ＤＣＣは図１４および図１５を参照して上述したＤＭＲの役割を果たす。
【０２６１】
処理システム１７１０は、汎用マイクロコンピュータ（ＧＰＭＣ）、ＤＳＰ、ＦＰＧＡ、またはＡＳＩＣが現在使用される様々なシステムおよびアプリケーションで使用可能である。したがって、例えば、処理システム１７１０は、様々な種類のコンピュータシステムまたはその他の演算を必要とする装置において使用可能である。
【０２６２】
一実施形態において、ＤＣＰは、データを処理するために構成された１つ以上の算術論理演算ユニット（ＡＬＵ）と、ＡＬＵを制御するために構成された１つ以上の命令処理ユニット（ＩＰＵ）と、命令またはデータを保持するために構成された１つ以上のメモリと、様々な種類のマルチプレクサおよびデコーダとを備えてもよい。そのような実施形態は、複数のポート（「プロセッサポート」）を含んでもよく、そのポートの一部はＤＣＣとの接続のために構成され、他は他のＤＣＰとの接続のために構成されることができる。図２０はＤＣＰの一実施形態のブロック図であり、以下で説明する。
【０２６３】
一実施形態において、ＤＣＣは、データおよび命令を保持するように構成された１つ以上のランダムアクセスメモリ（ＲＡＭ）と、構成可能なコントローラと、クロスバースイッチなどのネットワークスイッチと、レジスタと、マルチプレクサとを備えてもよい。そのような実施形態は、複数のポート（「プロセッサポート」）を含んでもよく、そのポートの一部はＤＣＰとの接続のために構成され（本明細書でＤＣＰ型ポートと呼ばれる）、他は他のＤＣＣとの接続のために構成される（本明細書でＤＣＣ型ポートと呼ばれる）ことができる。図２１は、ＤＣＣの一実施形態のブロック図であり、以下で説明する。なお、ＤＣＣまたはＤＣＰと接続されているにかかわらず、所与のポートに対して、特定のクロック周期でその所与のポートを介して転送可能なデータ量は、様々な実施形態において変化する。例えば、一実施形態において、所与のポートは、クロック周期毎に１ワードのデータを転送するように構成されてもよい。別の実施形態において、所与のポートはクロック周期毎に複数のワードのデータを転送するように構成されてもよい。さらに別の実施形態において、所与のポートは時分割多量化などの技術を用いて、複数のクロック周期で１ワードのデータを転送し、それによってポートを備える物理接続の数を減らしてもよい。
【０２６４】
ＭＭＡＰ１７１０の一実施形態において、各ＤＣＰは命令を格納するための小ローカルメモリを含んでもよく、さらに微小ローカルデータ記憶装置を含んでもよい。そのような実施形態において、各ＤＣＰの近接ＤＣＣは、所与のＤＣＰに対してオペランドを提供するように構成されてもよい。特定の実施形態において、多くのＤＣＰ命令に対して、所与のＤＣＰが近接ＤＣＣからオペランドを読み込んでＡＬＵ動作を実行し、１クロック周期において、ＡＬＵ結果を所与の近接ＤＣＣに格納してもよい。それによって、実行直後のクロック周期において、１ＤＣＰからのＡＬＵ結果が他のＤＣＰでも使用可能となる。このように結果を生成することによって、近接ＤＣＰの実行が密接に連携し合う、または「密着」することが可能となる。本明細書において、このような連携を連携処理と呼ぶ。
【０２６５】
本明細書で使用しているように、所与のＤＣＣまたはＤＣＰからみると、近接ＤＣＣまたはＤＣＰは、特定の待ち時間なしに所与のＤＣＣまたはＤＣＰがアクセス可能なＤＣＣまたはＤＣＰを指す。いくつかの実施形態において、この近接関係の範囲を定義する待ち時間は、例えばクロック速度などの要素に応じて変化する場合がある。さらに、いくつかの実施形態において、複数の近接度を定義してもよい。この場合、近接度は様々なアクセス待ち時間に対応してもよい。例えば、一実施形態において、「最近接」は、要求された同一クロック周期中にデータを供給できる装置として定義してもよい。「次最近接」は、要求後の１クロック周期内でデータを供給できる装置として定義してもよい。以下同様である。別の実施形態において、近接関係を定量化するために他の測定基準を使用することも考えられる。
【０２６６】
所与のＭＭＡＰ実施形態において、あるＤＣＣおよびＤＣＰは、他のＤＣＣおよびＤＣＰに論理的に隣接してもよい。本明細書で使用するように、「論理的隣接」は、例えば、あるＤＣＣと別のＤＣＣ、またはあるＤＣＣとあるＤＣＰなど、２つの装置間の関係を指し、それによって１つの装置の１つ以上のポートが他の装置のそれぞれのポートに対して介在ＤＣＣまたはＤＣＰを通過せずに直接接続される。さらに、所与のＭＭＡＰ実施形態において、あるＤＣＣおよびＤＣＰは他のＤＣＣおよびＤＣＰに対して物理的に隣接してよい。本明細書で使用するように「物理的隣接」は、例えば、あるＤＣＣと別のＤＣＣ、またはあるＤＣＣとあるＤＣＰなど、２つの装置間の関係を指し、それによってそれ以外のＤＣＣまたはＤＣＰが２つの装置間に物理的に配置される。
【０２６７】
いくつかのＭＭＡＰ実施形態において、論理的や物理的に近接したＤＣＣやＤＣＰなどの装置も近接している、または近接装置である。ただし、いくつかの実施形態において、所与の装置間の論理的／物理的隣接度は近接関係、または特定の近接関係度を必要としない。例えば、一実施形態において、あるＤＣＣが非常に遠くに配置された別のＤＣＣに直接接続されてもよい。そのような対は論理的に近接しているが物理的に近接していない場合があり、ＤＣＣ間の信号伝搬時間が長すぎて近接装置の待ち時間条件を満たさない場合がある。同様に、一実施形態において、あるＤＣＣが別のＤＣＣに物理的に近接しているが直接接続されず、したがって論理的に近接していない場合がある。あるＤＣＣから別のＤＣＣへのアクセスは、１つ以上の中間ノードをトラバースし、結果的に発生した伝送遅延が大きくなりすぎて近接装置の待ち時間条件を満たさない場合がある。
【０２６８】
ＭＭＡＰ１７１０の所与の実施形態の技術および実装に応じて、ＤＣＣＲＡＭのサイズとともにＤＣＣの複数のポートのうちの特定数のポートは、ＤＣＣの所望の実行速度およびサイズ全体に対してバランスがとられることも可能である。例えば、あるＤＣＣ実施形態は、４つのＤＣＰ型ポートと、４つのＤＣＣ型ポートと、４千ワードのメモリとを備えてもよい。このＤＣＣ実施形態は、ダイレクトメモリアクセス（ＤＭＡ）機構を提供するように構成されてもよい。ＤＭＡ機構によって、ＤＣＰが結果を演算している間に、所与のＤＣＣが他のＤＣＣ間またはＭＭＡＰ１７１０外部の場所間でデータをコピーしたりできる。
【０２６９】
ＭＭＡＰ１７１０の一実施形態において、データおよび命令は様々な方法でＤＣＣ間で転送可能である。シリアルバスをＭＭＡＰ１７１０中の全メモリに対して提供してもよい。そのようなバスは、外部メモリからＭＭＡＰ１７１０を初期化したり、ＭＭＡＰデータ構造の検査をサポートするために使用可能である。短距離の転送に対しては、所与のＤＣＰは、近隣ＤＣＣとデータを直接移動するようにプログラムされてもよい。データまたは命令を長距離において転送するには、ＤＣＣのネットワークおいて通信パスウェイを動的に作成および破壊してもよい。
【０２７０】
上記のような長距離データ転送を目的として、ＭＭＡＰ１７１０内で相互接続されているＤＣＣネットワークは、通信パスウェイに対して交換ルーティング構造（ｓｗｉｔｃｈｅｄ ｒｏｕｔｉｎｇ ｆａｂｒｉｃ：ＳＲＦ）を形成してもよい。そのような実施形態において、ＳＲＦにおいて通信パスウェイを管理する少なくとも２つの方法がある。第１の方法はグローバルプログラミングである。グローバルプログラミングにおいて、パスはソフトウェア制御によって（例えば、人間のプログラマまたはルーティング機能をもったコンパイラのいずれかによって）選択される。命令はＤＣＣ構成コントローラに対してコードされ、クロスバーを適宜プログラムする。パスウェイを作るには、パスウェイに沿った各ＤＣＣを特定のルーティング機能で明確にプログラムされてもよい。パスウェイが頻繁に作成および破壊される動的な環境では、大量のクロスバー構成コードが必要とされる場合があり、それによって、その記憶装置も潜在的に制限されたＤＣＣＲＡＭリソースを消費してしまう場合がある。
【０２７１】
通信パスウェイを管理する第２の方法は「ワームホールルーティング」と呼ばれる。ワームホールルーティングを実行するためには、各ＤＣＣがワームと呼ばれる言葉のシーケンスの進行をＳＲＦを介して停止および再スタートするステアリング機能および機構の組を備えてもよい。ステアリング機能は全通信パスウェイによって共通して使用され再利用されることが可能なため、ＤＣＣＲＡＭを占有する構成コードの量は上述のグローバルプログラミング法に比べて非常に小さい。このワームホールルーティング法において、パスウェイによって使用される特定のリンクを選択するためには、ソフトウェア制御を依然として使用してもよい。ただし、パスウェイ作成（本明細書ではセットアップとも呼ぶ）の処理と破壊／リンク解放（本明細書ではテアダウンとも呼ぶ）は、最小限のソフトウェアの介在で、ハードウェア上で実行されてもよい。
【０２７２】
パスウェイ上でのデータワードの潜在的な損失を防ぐために、ＭＭＡＰ１７１０の実施形態は、パスウェイに沿って受信機と送信機との間でフロー制御を実行してもよい。フロー制御とは、対応する受信機がデータを受信しなくなった場合に送信機を停止でき、対応する受信機がデータを受信可能な状態になったときに送信機を再起動させる機構である。パスウェイ上のデータのフローの停止および再スタートはワームホールルーティングにおけるワームの進行の停止および再スタートとの類似点が非常に多いため、上記２つの方法は統合した形態で組み合わせることができる。
【０２７３】
一実施形態において、ＭＭＡＰ１７１０は複数のＤＣＰおよびＤＣＣを備えてもよく、それぞれのＤＣＰは同一でよく、それぞれのＤＣＣは同一でよく、均一なアレイにおいて互いに接続される。均一なアレイにおいて、大部分のＤＣＰは同一で、大部分のＤＣＰのそれぞれはＤＣＣに対して同一の接続数を有してもよい。また、均一なアレイにおいて、大部分のＤＣＣは同一で、大部分のＤＣＣのそれぞれは他のＤＣＣおよびＤＣＰに対して同一の接続数を有してもよい。一ＭＭＡＰ実施形態のＤＣＰおよびＤＣＣは、ほぼ一様に分散している。本明細書で用いるように、ほぼ一様な分散とは、アレイの小領域の大部分においてＤＣＰ対ＤＣＣの比率が一貫性がある配列を指す。
【０２７４】
ほぼ一様に配置された均一なアレイは、予測可能な相互接続パターンを実現したり、アレイ全体でのソフトウェアモジュール再利用を可能とするなど、有益な特性を有する場合がある。一実施形態において、均一なアレイはＤＣＰおよびＤＣＣの少数のインスタンスの設計および検査を可能とする場合がある。したがって、ＤＣＣおよびＤＣＰからなるユニットを組み立ててから、そのユニットを複数回反復および「傾けて」システムを組み立てることが可能である。この方法は、一般的なシステム要素を再利用することによって、設計と検査のコストを下げることができる。
【０２７５】
なお、ＤＣＰおよびＤＣＣの構成可能な特性によって、幅広く様々な不均一のふるまいをプログラムして、均一アレイ上で物理的に発生させることができる。ただし、代替の実施形態において、ＭＭＡＰ１７１０は不均一なＤＣＣおよびＤＣＰユニットで形成することもできる。この場合、不均一なＤＣＣおよびＤＣＰユニットは規則的なまたは不規則的なアレイにおいて接続したり、さらにランダムに接続してもよい。一実施形態において、ＤＣＰとＤＣＣとの相互接続は、例えば、集積回路（ＩＣ）、セラミック基板、またはプリント回路基板（ＰＣＢ）上の回路トレースとして実現されてもよい。ただし、代替の実施形態において、そのような相互接続は、電磁エネルギー（すなわち、電波または光エネルギー）、無線（すなわち、無誘導）エネルギー、粒子（電子ビームなど）、または分子上の電位などの導波路など、様々な微小通信リンクでもよい。
【０２７６】
ＭＭＡＰ１７１０は、単一の集積回路上に実装されてもよい。一実施形態において、複数のＭＭＡＰ集積回路を組み合わせて大規模システムを構築してもよい。ＭＭＡＰ１７１０の所与の実施形態は、シリコン集積回路（Ｓｉ−ＩＣ）技術を用いて実装されてもよく、様々な機能を用いてその技術の特定の特性を実現してもよい。例えば、Ｓｉ−ＩＣチップ上の複数の回路を薄板に実装してもよい。それに対応して、ＭＭＡＰ１７１０の所与の実施形態は、図１８に示すようなＤＣＰとＤＣＣの平面アレイを用いてもよい。ただし、ＤＣＰおよびＤＣＣの異なる配置を含む代替のＭＭＡＰ実施形態も考えられる。
【０２７７】
さらに、Ｓｉ−ＩＣチップ上で使用可能な配線密度はチップ間よりも高く、各チップは、オンチップ信号とオフチップ信号とをインタフェースで接続する専用入力／出力（Ｉ／Ｏ）回路の周囲長を有してもよい。それに対応して、ＭＭＡＰ１７１０の所与の実施形態は、チップの中心にＤＣＰおよびＤＣＣの均一なアレイと、チップの周囲長に沿った修正ＤＣＰ／ＤＣＣユニットからなる多少不均一なアレイを用いてもよい。ただし、均一なＤＣＰ／ＤＣＣユニットと修正ＤＣＰ／ＤＣＣユニットの様々な配置および組み合わせを含む代替のＭＭＡＰ実施形態が考えられる。
【０２７８】
また、Ｓｉ−ＩＣ回路によって実行される演算動作は熱を発生させ、その熱がＩＣパッケージングによって除去される場合がある。ＩＣパッケージングが増えると追加の空間が必要となる場合があり、ＩＣパッケージングの中および周辺の相互接続によってパス長に比例した遅延が発生する場合がある。したがって、上述のように、複数のチップを相互接続することによって非常に大規模なＭＭＡＰを構築可能である。そのような複数チップのＭＭＡＰ実施形態のプログラミングにおいては、チップ間の信号遅延がチップ内の信号遅延よりも非常に長いということを考慮する場合がある。
【０２７９】
所与のＳｉ−ＩＣＭＭＡＰ１７１０の実施形態において、単一のチップ上に実装可能なＤＣＰおよびＤＣＣの最大数を、所与のＳｉ−ＩＣ技術によって可能となる小型化と各ＤＣＰおよびＤＣＣの複雑度によって決定してもよい。そのようなＭＭＡＰの実施形態において、演算スループットの目標レベルを達成することを条件として、ＤＣＰおよびＤＣＣの回路複雑度を最小化してもよい。そのようなＤＣＰおよびＤＣＣの最小化を、本明細書においてストリームライン化と呼ぶ場合がある。ＭＭＡＰ１７１０の一実施形態において、ＤＣＰに対するスループットの目標レベルは、同様のＳｉ−ＩＣ技術で製作された最高のデジタル信号プロセッサ（ＤＳＰ）からなる演算実行ユニットのものに匹敵することが可能である。ただし、目標ＤＣＰスループットに対する代替の基準が用いられた他のＭＭＡＰ実施形態も考えられる。
【０２８０】
いくつかの実施形態において、ＭＭＡＰ１７１０はＤＳＰおよびＦＰＧＡアーキテクチャの最高の機能を使用できる。ＤＳＰにように、ＭＭＡＰ１７１０は、複数の処理ユニットとオンチップメモリとを備えるプログラム可能なチップである。しかしながら、ＤＳＰと比較すると、ＭＭＡＰ処理ユニットはストリームライン化しており、より多く存在する場合があり、チップの内外のデータ移動とともにチップ間のデータ移動の帯域幅を最大限にするように相互接続される場合がある。ＤＳＰより処理ユニットが多いと、ＭＭＡＰ１７１０は単位時間により多くの乗算を行うことができ、ストリームライン化した処理ユニットはエネルギー使用を最小限に抑えることができる。内部並列処理を有する多くのＤＳＰはバス指向アーキテクチャの場合がある。いくつかの実施形態において、ＭＭＡＰ１７１０はバスを備えない場合もあり、むしろバス指向アーキテクチャよりも非常に高い総帯域幅を実現できるＳＲＦに埋め込まれた近接共有ローカルメモリをＤＣＣなどに備える場合がある。
【０２８１】
ＦＰＧＡ法と比較すると、いくつかのＭＭＡＰ実施形態はあまり細分化されていない。例えば、ＭＭＡＰの一実施形態において、動作は自然語長（例えば、１６ビット）を有しており、自然語長の倍数であるデータを用いて実行すると、演算は最も効率的となる場合がある。ＭＭＡＰのいくつかの実施形態において、ＤＣＰおよびＤＣＣはＦＰＧＡで実現される等価構造よりも密度が高い。その結果、平均配線長は短くなり、配線容量やエネルギー使用量が減少する。ＦＰＧＡ実装とは対照的に、ＭＭＡＰのいくつかの実施形態において、ＭＭＡＰの各ＡＬＵはプロセッサ（すなわちＤＣＰ）の一部の場合があり、それによって、オペランドの設定やＤＣＣにおける周辺の高速メモリに対する結果送信を容易にすることができる。
【０２８２】
図１８に示すＭＭＡＰ１７１０は、図示するようにＤＣＣをＤＣＰ間に分散させることによって高速メモリに対する十分な接続をＤＣＰに提供できる。そのような配置によって、分離（すなわち非分散）配置に比べて、所与のＤＣＰがＤＣＣのメモリにアクセスするのに必要な時間を減らすことができる。そのような配置を本明細書において分散格子配置と呼ぶ。図１８の実施形態において、ＤＣＰ対ＤＣＣの比率は１：１である。ただし、異なるＤＣＰ対ＤＣＣの比率を有する場合がある他のＭＭＡＰ実施形態も考えられる。
【０２８３】
より多くの接続方式が存在するため、図１８ではＤＣＣとＤＣＰとの間の接続を明確に示していない。所与のＭＭＡＰ実施形態に対するいくつかの可能な接続方式を以下に挙げる。
【０２８４】
１．ＰｌａｎａｒＡ−本方式では、各ＤＣＰは４つの近接ＤＣＣに対して各近接ＤＣＣ上のＤＣＰ型ポートを介して接続できる。また各ＤＣＣは、４つの近接ＤＣＣに対して各近接ＤＣＣ上のＤＣＣ型ポートを介して接続できる。各接続型は並列回路トレースまたは配線の組からなる。均一なアレイにおいて、接続型における配線数はアレイ全体において一定である。
【０２８５】
２．ＰｌａｎａｒＢ−直列記憶装置から初期状態を読み込むために、シリアルバスを用いてＤＣＣとＤＣＰとをさらに接続できる点を除いて、本方式はＰｌａｎａｒＡと同じである。
【０２８６】
３．ＰｌａｎａｒＣ−アレイの多くの行および列によって分離されたＤＣＣ間に追加の並列接続がなされている点を除いて、本方式はＰｌａｎａｒＢと同じである。そのような追加の接続は帯域幅を高め、遠く離れたＤＣＣ間の待ち時間を減らすことができる。
【０２８７】
４．ＰｌａｎａｒＤ−本方式はＰｌａｎａｒＣのサブセットで、追加の接続は各ＤＣＣが超立方体の頂点である超立方体のへりを表す。
【０２８８】
５．ＰｌａｎａｒＥ−本方式はＰｌａｎａｒＣのサブセットで、２つのアレイが密結合できるように、多くの接続で第１のチップに接続された第２のチップに対して追加の接続がなされる。
【０２８９】
６．ＳｔａｃｋｅｄＡ−本方式はＰｌａｎａｒＣのサブセットで、追加の接続によって三次元行列が可能となる。
【０２９０】
なお、異なる種類と数の接続を用いて異なる接続形態でＤＣＣとＤＣＰとが接続できる追加接続の方法が考えられる。
【０２９１】
図１８は、ＭＭＡＰ接続方式の一実施形態を示すブロック図である。ＭＭＡＰ接続方式１８２０は、複数のＤＣＣおよびＤＣＰを含み、図１８のＭＭＡＰの一部を例証する。ＭＭＡＰ接続方式１８２０において、各ＤＣＰは４つの近接ＤＣＣに接続される。各ＤＣＣは、４つの近接ＤＣＣとともに４つの近接ＤＣＰに接続される。したがって、ＭＭＡＰ接続方式１８２０は上述のＰｌａｎａｒＡ接続方式を例証するものである。
【０２９２】
ＭＭＡＰ接続方式１８２０における高帯域幅ポートに対応するために、ポート間（ＤＣＰ−ＤＣＣ間、またはＤＣＣ−ＤＣＣ間）の接続は短く（すなわち、近隣に限定されている）、ワード全体である。すなわち、これは接続のデータ部分における導電体（線）の数は、ＡＬＵオペランドで使用されるビット数と同じであることを意味している。ＤＣＰ−ＤＣＣ間接続はアドレスラインを含んでもよい。ＤＣＣ−ＤＣＣ間接続は必ずしもアドレスラインを含まなくてよいが、フロー制御用のラインを有してもよい。
【０２９３】
ＤＣＰノードを単純に保つことによって、大規模なアレイ（例えば、一ＭＭＡＰ実施形態において、１６行×１６列＝２５６ＤＣＰ）をわずかな費用で単一のＶＬＳＩＩＣ上に配置してもよい。適したＶＬＳＩ技術は、シリコンのバイポーラトランジスタまたは他の半導体を備えた、またはそれを備えていない相補型ＭＯＳ（ＣＭＯＳ）電界効果トランジスタを備えてもよいが、それに限定されない。
【０２９４】
いくつかのＭＭＡＰ実施形態において、ノード間の通信はプログラムマの制御下にあってもよい。ＭＭＡＰにおいて、各ＤＣＰは近接ＤＣＣと、また任意でそのＤＣＣを介して他のＤＣＣおよびＤＣＰとデータ／命令をやりとりする。データの小ブロックを移動するために、ＤＣＰを連携的に使用して、一連の転送によってアレイ上でデータを一度に１ワードずつＤＣＰ毎に移動してもよい。このような方法において、発信元ノードから宛先ノードへのパスにおける第１のＤＣＰは、クロック周期の読み出し位相中に近接ＤＣＣメモリから読み込み、クロック周期の書き込み位相中に別の近接ＤＣＣに書き込んでもよい。そのパスにおける第２のＤＣＰは同様にデータの読み込みおよび書き出しを行い、データが宛先ノードに到着するまでこの処理は継続してよい。また、宛先ノードへの経路に沿って伝搬する際に、所与のＤＣＰによってデータはスケール変換または正規化されてもよい。この方法を使用すると、プログラミングによってアレイ上にバケツリレーラインとツリーが設定でき、必要に応じてデータを移動できる。ただし長距離および大量のデータに対しては、データ搬送のために多くの移動が必要となり、したがって多くのＤＣＰが、有効な演算を実行するかわりに、データを移動するだけに周期の大部分を使用することになってしまう場合がある。
【０２９５】
長距離のブロック移動に対して、いくつかのＭＭＡＰ実施形態はＤＣＰを含まないＤＣＣ間のメモリ間転送の手段を提供してもよい。ＤＣＰは、ＤＣＣ型ポートと関連づけられた特定のＲＡＭアドレスを介して近接ＤＣＣのＤＣＣ型ポートにアクセスしてもよい。これによって、ＤＣＰはワームを送信する新規のパスウェイを作成でき、その後そのパスウェイを分解（テアダウン）する、もしくはワームを受信できる。また、ＤＣＰは、転送されるデータのブロックを近接ＤＣＣのＲＡＭに保存してから、近接ＤＣＣがＤＭＡ動作と関連づけられている特定のＲＡＭアドレスを介してＤＭＡ動作を開始するように指示できる。これによって、近接ＤＣＣがデータのＤＭＡ転送を調整している間に、ＤＣＰは他のタスクを進めることができる。
【０２９６】
ＭＭＡＰの様々な実施形態は、有効なアルゴリズムを実行する有益な環境を提供できる。そのようなアルゴリズム（例えば、図４の方法）はＡＬＵのフロー図に分割できる。各フロー図は、複数のフィードバック／フィードフォワードパスを含むツリー、格子、または任意のネットワークとして、ＭＭＡＰアレイ上にマッピングされる。数ＤＣＰおよび数ＤＣＣを組み合わせることによって、複数ワードの正確な結果が得られるように１ＡＬＵの有限精度を拡張できる。フロー図をＭＭＡＰにマッピングすると、ノード間の距離に比例するＤＣＰ／ＤＣＣノード間の通信遅延は増加する。また、通信キューが大きい場合または頻繁に再構成が行われる場合、マッピングのために各ノードでより大きなメモリが必要となる。そのような要素は、通信遅延、待ち時間、再構成を考慮して慎重にプログラミングを行うことで補うことができる。
【０２９７】
一ＭＭＡＰ実施形態は、チップ毎の多くのプロセッサと、ＳＩＭＤシステムや分散ＭＩＭＤシステムなどの他の種類のシステムの動作をまねるように構成可能なＭＩＭＤアーキテクチャとを有してもよい。いくつかの実施形態において、ＭＭＡＰは、同時にチップの異なる領域で異なるアルゴリズムを実行させてもよい。また、省電力のため、いくつかの実施形態において、プログラマは、少なくともいくつかのＤＣＰおよびＤＣＣに対するクロックを選択的にイネーブルおよびディセーブルとすることができ、使用されていないＤＣＰおよびＤＣＣをディセーブルとすることができる。
【０２９８】
図２０は、動的に構成可能なプロセッサ（ＤＣＰ）の一実施形態を示すブロック図である。ＤＣＰ１９００は、図１８および図１９に示すＤＣＰを例証する。ＤＣＰ１９００は、少なくとも１つの数値演算ユニット（ＡＬＵ）１９２０を制御するように接続された命令処理ユニット（ＩＰＵ）１９１０を備える。また、ＤＣＰ１９００は、複数のマルチプレクサ（本明細書においてｍｕｘとも呼ぶ）に接続された複数のデータ入力ポート１９０１を備える。この複数のマルチプレクサは順に接続されて、命令処理ユニット１９１０に対するプログラム読込パスのデータを選択するとともに、ＡＬＵ１９２０に対する少なくとも第１および第２のオペランド入力を選択する。さらに、ＤＣＰ１９００は、ＡＬＵ１９２０からの結果データを受信するためにｍｕｘを介して接続された複数のデータ出力ポート１９０２と、命令処理ユニット１９１０からアドレスデータを受信するために接続された複数のアドレスポート１９０３とを備える。
【０２９９】
アドレスポート１９０３は、近接した動的に構成可能な通信装置（ＤＣＣ）に含まれたＲＡＭデータを読み込みおよび書き込みするためのアドレスを伝達するように構成されてもよい。データ入力ポート１９０１およびデータ出力ポート１９０２は、近接ＤＣＣとデータのやりとりをするように構成されてもよい。同時動作モードにおいて、１クロック周期においてデータ出力ポート１９０２を介して近接ＤＣＣに書き込まれるデータは、さらなる遅延または調整オーバーヘッドがない直後のクロック周期において近接ＤＣＰ１９００のデータ入力ポート１９０１を介して読み込むことができる。
【０３００】
ＤＣＰ１９００の図示の実施形態において、データ入力ポート１９０１、データ出力ポート１９０２、およびアドレスポート１９０３のそれぞれは４つのポートを備える。また、単一のＡＬＵ１９２０を図示する。ただし、他の数のデータ入力ポート、データ出力ポート、またはアドレスポートが提供されたり、異なる数のＡＬＵが備えられる代替の実施形態も考えられる。図１８に示すＭＭＡＰ実施形態など、矩形アレイにＤＣＰ１９００の複数のインスタンスを含むＭＭＡＰ実施形態において、様々なポートを各ＤＣＰノードの４つの側の周辺に均等に分散してもよい。
【０３０１】
ＤＣＰ１９００は、データワードに対して数値演算ユニット動作を実行するように構成されてもよい。この場合、選択動作は、ＩＰＵ１９１０によって処理されている現在の命令によって決まる。柔軟なプログラミングを可能にするため、ＩＰＵ１９１０は、複数のアドレス指定可能な記憶場所を含む少なくとも１つの命令メモリ１９１２と、命令デコーダ１９１４と、アドレスジェネレータ１９１６とを備えてもよく、それぞれは様々な相互接続機構を介して相互接続される。他の実施形態において、ＩＰＵ１９１０が１つより多い命令メモリを含んでもよく、または追加の機能を含んでもよいことが考えられる。さらに、他の実施形態において、ＩＰＵ１９１０に図示した機能は、様々な種類の機能ユニットに分割したり、単一の機能ユニットに実装されたりしてもよいことが考えられる。
【０３０２】
ＩＰＵ１９１０は、データ入力ポート１９０１に接続されたプログラム読込パスを介して、命令メモリ１９１２の記憶装置に対するプログラムデータを受信するように構成されてもよい。命令メモリ１９１２は、グローバルシリアルバス（不図示）を介して書き込みおよび読み出しを行うことができる。命令デコーダ１９１２による特定の命令の復号化に応じて、ＩＰＵ１９１０はデータ入力ポート１９０１およびデータ出力ポート１９０２に接続された様々なｍｕｘを制御して、データを近接ＤＣＣへ、または近接ＤＣＣから誘導するように構成されてもよい。ＩＰＵ１９１０は、アドレスジェネレータ１９１６によって生成されたアドレスをアドレスポート１９０３を介して近接ＤＣＣへ運んで、例えば、そこの配置されているＲＡＭに対して読み出しまたは書き込みを行うように構成されてもよい。また、アドレスジェネレータ１９１６は、命令メモリ１９１２から取り出されて命令デコーダ１９１４によって復号化される次の命令アドレスを生成するように構成されたプログラムカウンタレジスタ（不図示）を備えてもよい。
【０３０３】
一実施形態において、ＤＣＰ１９００は、データレジスタファイル、データキャッシュ、またはデータオペランドまたは結果データ用にローカル記憶装置を備えなくてもよい。そのような実施形態において、ＤＣＰ１９００は、データオペランドの読み出しおよび結果データの書き込みが行われる高速記憶媒体として、ＤＣＰ１９００が直接接続されるＤＣＣに備えられるメモリを使用するように構成されてもよい。いくつかの実施形態において、所与のＤＣＰは同時または異なる時間に異なる近接ＤＣＣから異なるデータを得てもよい。より詳細に後述するように、いくつかの実施形態において、所与のＤＣＰの遠隔ＤＣＣから近接ＤＣＣまでパスウェイを構築することによって、所与のＤＣＰが、所与のＤＣＰが直接接続されていないＤＣＣに対してデータの読み出しおよび書き込みを行うように構成されてもよい。
【０３０４】
ＤＣＰ１９００によって実行される命令は、メタ命令とともに、数値演算動作に対応してもよい。ＤＣＰ命令は、２つのオペランドおよび１つの結果に対するアドレスメモリに対して十分なビット長を有してよく、それによってそれらの値が１クロック周期で読み出しおよび書き込みできる。一実施形態において、ＤＣＰ１９００は以下の命令を実行できる。
Ａｄｄ（加算）（オペランド−アドレス、オペランド−アドレス、結果−アドレス）、Ｓｕｂｔｒａｃｔ（減算）（オペランド−アドレス、オペランド−アドレス、結果−アドレス）、Ｍｕｌｔｉｐｌｙ（乗算）（オペランド−アドレス、オペランド−アドレス、結果−アドレス）、Ｍｕｌｔｉｐｌｙ ａｎｄ Ａｄｄ ｔｏ ｌａｓｔ Ｒｅｓｕｌｔ（最終結果まで乗算および加算）（オペランド−アドレス、結果−アドレス）、Ｍｕｌｔｉｐｌｙ ａｎｄ Ｓｕｂｔｒａｃｔ ｆｒｏｍ ｌａｓｔ Ｒｅｓｕｌｔ（最終結果からの乗算および減算）（オペランド−アドレス、結果−アドレス）、Ｎｅｇａｔｅ ａ ｎｕｍｂｅｒ（数の取消）（タイプ、オペランドアドレス、結果−アドレス）、Ａｂｓｏｌｕｔｅ ｖａｌｕｅ ｏｆ ａ ｎｕｍｂｅｒ（数の絶対値）（タイプ、オペランドアドレス、結果アドレス）、Ｓｈｉｆｔ（シフト）（タイプ、オペランドアドレス、結果アドレス）、ＸＯＲ（マスクアドレス、オペランドアドレス、結果アドレス）、Ｉｎｖｅｒｔ（反転）（マスクアドレス、オペランドアドレス、結果アドレス）；Ｊｕｍｐ（ジャンプ）（条件、刻み幅、ＰＣ−送信先）、Ｒｅｐｅａｔ（反復）（開始、停止、刻み幅）、Ｌｏｏｐ（ループ）（回数、ＰＣ−ブロック始端）、Ｂｒａｎｃｈ−ｏｎ−Ｃｏｎｄｉｔｉｏｎ（条件分岐）（テスト、宛先）。
【０３０５】
プレ命令は、アドレスジェネレータでインデックス作成レジスタを設定するための専用な命令である。
Ｓｔｏｒｅ−ｉｎｄｅｘ（指標名、値）
Ｓｔｒｉｄｅ−ｉｎｄｅｘ（指標名、値）
【０３０６】
なお、ＤＣＰ１９００が追加の命令または異なる命令組を実行してもよい他の実施形態も考えられる。いくつかの実施形態において、１つ以上のデータオペランドを必要とする所与の命令の実行中に、所与のＤＣＰは、要求されたオペランドにアクセスするために近接ＤＣＣのメモリに直接アクセスするように構成されてもよい。
【０３０７】
ＤＣＰ１９００は、メタ命令を実行するように構成されてもよい。本明細書において用いるように、メタ命令は、命令メモリ１９１２などのＤＣＰ命令メモリに格納された命令に対して動作を実行してもよい命令を指す。基本メタ命令は、近接ＤＣＣのＲＡＭから命令メモリ１９１２を読み込んでもよい（すなわち、オーバーレイを読み込んでもよい）。ＤＣＣメモリから命令メモリを読み込むことによって、データと命令との間でメモリを分割することは、ソフトウェアプログラミングによって決定される。したがって、アプリケーションプログラマは、使用可能なメモリを最大限に活用できるようソフトウェアを最適化するとよい。いくつかの実施形態において、ＤＣＰ１９００は、ＩＰＵ命令メモリを修正したり、テストやエラー解析、エラー回復などのためにＤＣＣメモリに命令メモリを保存したりする他のメタ命令を含んでもよい。
【０３０８】
ＡＬＵ１９２０は、ＤＣＰ１９００の特定の実施形態で支援する命令によって定義される動作を含む、少なくとも固定小数点システムに対する演算を実行するように構成されてもよい。例えば、一実施形態において、ＡＬＵ１９２０は、固定小数点の加算、減算、乗算、乗算累算、論理およびシフトの動作を実行するように構成されてもよい。いくつかの実施形態において、ＡＬＵ１９２０は、精度が高められた演算を支援するために、前の演算からのキャリービット結果を保持するように構成されてもよい。他の実施形態において、ＡＬＵ１９２０は、浮動小数点演算または特定アルゴリズム実行のために選択された専用動作を実行するように構成されてもよい。
【０３０９】
図２１は、動的に構成可能な通信装置（ＤＣＣ）の一実施形態を図示したブロック図である。なお、「動的に構成可能な通信装置」および「動的に構成可能な通信素子」とは、本明細書において交換可能に使用できる。ＤＣＣ２０００は、図１８および図１９に図示したＤＣＣを例証するものでよい。ＤＣＣ２０００は、ＳＲＡＭ制御２０１５に接続された複数のｍｕｘを介してマルチポートスタティックＲＡＭ（ＳＲＡＭ）２０２５に接続された複数のＤＣＰ入力ポート２００１を備える。マルチポートＳＲＡＭ２０２５は、ＳＲＡＭ制御２０１５および複数のＤＣＰ出力ポート２００２とともに、複数のアドレスデコーダ２０２０に接続される。アドレスデコーダ２０２０は、複数のＤＣＣポートデコーダ２０１０およびＳＲＡＭ制御２０１５に接続された複数のｍｕｘを介してＳＲＡＭアドレスを受信するように接続される。ＤＣＣポートデコーダ２０１０は、複数のＤＣＰアドレスポート２００３からＳＲＡＭアドレスを受信するように接続される。
【０３１０】
ＤＣＣ２０００は、複数のｍｕｘおよび複数の入力レジスタ２０５４を介してクロスバー２０５０およびルーティングロジック２０３５に接続される複数のＤＣＣ入力ポート２００４をさらに備える。クロスバー２０５０は、ルーティングロジック２０３５に接続され、ルーティングロジック２０３５は通信コントローラ２０３０に接続される。通信コントローラ２０３０は、複数のｍｕｘを介してアドレスデコーダ２０２０に、プログラム読込パスを介してマルチポートＳＲＡＭ２０２５に接続される。クロスバー２０５０は、複数の出力レジスタ２０５５を介して複数のＤＣＣ出力ポート２００５にさらに接続される。
【０３１１】
出力レジスタ２０５５は、複数のｍｕｘを介してマルチポートＳＲＡＭ２０２５に接続される。ＤＣＰ入力ポート２００１およびマルチポートＳＲＡＭ２０２５は、それぞれルーティングロジック２０３５に対して入力レジスタ２０５４によって接続された複数のｍｕｘを介してクロスバー２０５０に接続される。また、ルーティングロジック２０３５は、ＤＣＣポートデコーダ２０１０および出力レジスタ２０５５に接続される。
【０３１２】
ＤＣＰ入力ポート２００１およびＤＣＰ出力ポート２００２は、ＤＣＣ２０００の近接ＤＣＰからデータを受信し、データを送信するように構成されてもよい。ＤＣＰアドレスポート２００３は、ＤＣＣ２０００の近接ＤＣＰからアドレスを受信するように構成されてもよい。ＤＣＣ入力ポート２００４およびＤＣＣ出力ポート２００５は、ＤＣＣ２０００の近接ＤＣＣからデータを受信し、データを送信するように構成されてもよい。ＤＣＣ２０００の図示の実施形態において、ＤＣＰ入力ポート２００１、ＤＣＰ出力ポート２００２、アドレスポート２００３、ＤＣＣ入力ポート２００４、およびＤＣＣ出力ポート２００５は、それぞれ４つのポートを備える。ただし、他の数のＤＣＰ入力ポート、ＤＣＰ出力ポート、アドレスポート、ＤＣＣ入力ポート、またはＤＣＣ出力ポートが提供される代替の実施形態も考えられる。
【０３１３】
マルチポートＳＲＡＭ２０２５は、複数のアドレス指定可能な記憶場所を含んでもよく、近接ＤＣＰに対する高帯域幅データ転送を提供するように構成されてもよい。それによって、マルチポートＳＲＡＭ２０２５はＤＣＣ２０００に接続された各近接ＤＣＰに対する共有レジスタファイルとしての役割を効果的に果たすことができる。さらに、マルチポートＳＲＡＭ２０２５は、複数の読出ポート、書込ポートおよびアドレスポートを介した複数の同時読み出しおよび書き込みアクセスに対応するように構成されてもよい。特定の一実施形態において、マルチポートＳＲＡＭ２０２５は、複数のアドレス指定可能な記憶場所に格納された複数の値を複数の近接ＤＣＰに対してほぼ同時に提供し、複数の近接ＤＣＰから受信した複数の値を複数のアドレス指定可能な記憶場所にほぼ同時に書き込むように構成されてもよい
【０３１４】
アドレスデコーダ２０２０は、所与のアクセスのアドレスを高速でマルチポートＳＲＡＭ２０２５とインタフェース接続するのに適したフォーマット、例えば完全デコードの行および列アドレスなどに復号化するように構成されてもよい。ＳＲＡＭ制御２０１５は、適切な読出および書込ポートをイネーブルにするなどして、読出および書込中のマルチポートＳＲＡＭ２０２５のふるまいを制御するように構成されてもよい。ＳＲＡＭ制御２０１５は、マルチポートＳＲＡＭ２０２５に提示されたアドレスおよびデータの送信元を制御するように構成されてもよい。マルチポートＳＲＡＭ２０２５の所与のアドレスポートに対して、ＳＲＡＭ制御２０１５は、ＤＣＣポートデコーダ２０１０を介してアドレスポート２００３によって供給されたアドレスまたは通信コントローラ２０３０によって供給されたアドレスのいずれかを使用するように、アドレスデコーダ２０２０に対して指示してもよい。同様に、マルチポートＳＲＡＭ２０２５の所与の書込ポートに対して、ＳＲＡＭ制御２０１５は、ＤＣＰ入力ポート２００１または出力レジスタ２０５５のいずれかからのデータを選択するようにマルチポートＳＲＡＭ２０２５に指示してもよい。
【０３１５】
図示する実施形態において、ＤＣＣ２０００は単一のマルチポートＳＲＡＭ２０２５を備える。他の実施形態において、１つより多いマルチポートＳＲＡＭが提供されてもよく、さらにスタティックＲＡＭ以外メモリ技術を用いてよいと考えられる。様々な実施形態において、マルチポートＳＲＡＭ機能は、あらゆる数のメモリ構造組織を用いて実現されてもよい。例えば、一実施形態において、メモリの複数のバンクを使用してもよい。この場合、各バンクは１つ以上のポートを含む。別の実施形態において、複数のＳＲＡＭメモリをＤＣＣにおいて使用してもよい。この場合、各ＳＲＡＭは異なる数のポートを有してもよい。また、一実施形態において、ＤＣＣ２０００は、マルチポートＳＲＡＭ２０２５を読み込む、または読み込まないように構成されてもよい低帯域幅シリアルポート（不図示）を備えてもよい。そのようなシリアルポートは、例えば、ブートローダ、テスト、デバッグなどに対して有効な場合ある。
【０３１６】
クロスバー２０５０は、複数の入力ポートと、複数の出力ポートとを備えてもよく、データを入力ポートから１つ以上の出力ポートにルーティングするように構成されてもよい。クロスバー２０５０によって実行される特定のデータルーティングは、備えられているクロスバー構成レジスタ（ＣＣＲ）２０５１の状態によって決定してもよい。クロスバー構成レジスタ（ＣＣＲ）２０５１は、所与の時間において事実上特定のルーティング機能に応じてルーティングロジック２０３５によってプログラムされてもよい。通信コントローラ２０３０は、特定のルーティング機能を実行するようにルーティングロジック２０３５をプログラムするように構成されてもよい。本明細書において、通信コントローラ２０３０およびルーティングロジック２０３５の機能は、集合的にルーティングエンジンと呼ぶ場合がある。図示の実施形態のように、階層的にルーティングエンジンを実行すると、ルーティングロジック２０３５によって実行されるルーティング機能は高速で動作することが可能となり（例えば、クロック周期のわずかな時間）、通信コントローラ２０３０は複数のクロック周期おいてルーティングパラメータを変更する柔軟性を提供してもよい。
【０３１７】
一実施形態において、ＣＣＲ２０５１をビット群に分割してもよく、クロスバー２０５０の出力ポート毎に１ビット群としてもよい。ビット群のうちのビットの数は、クロスバー入力ポートの１つを選択するのに少なくとも十分であればよい。選択された出力レジスタ２０５０がマルチプレクサを通り抜けると（例えば、複数のＤＣＣリンクのうちから選択するため）、マルチプレクサを構成する（すなわち、特定のリンクを選択する）ために、ビット群毎の追加のビットが必要とされる。出力レジスタ２０５５のトランスペアレンシを設定するために、少なくともビット群毎に追加の１ビットが提供されてもよい。出力レジスタ２０５５のトランスペアレンシは、ルーティングロジック２０３５から出力レジスタ２０５５へ運ばれた出力ラッチ信号によって制御されてもよく、ＤＣＣ２０００全体に伝搬するデータワードの遅延を減少させるために使用されてもよい。また、入力レジスタ２０５４のトランスペアレンシは、ルーティングロジック２０３５から入力レジスタ２０５４へ運ばれた入力ラッチ信号によって制御されてもよく、ＭＭＡＰにおけるフロー制御のための方法を提供するために使用してもよい。一実施形態において、ＣＣＲ２０５１は、各出力レジスタ２０５５に対して１トランスペアレンシビットを含んでもよい。そのような実施形態において、ＣＣＲ２０５１は、各出力レジスタ２０５５を入力レジスタ２０５４のうちの対応するものにマッピングしてもよく、各出力レジスタ２０５５のトランスペアレンシ状態は対応する入力レジスタ２０５４と関連づけられてもよい。
【０３１８】
ＣＣＲ２０５１は、クロック周期の各フェーズと同じ頻度で更新されてもよい。ＣＣＲ２０５１は、プログラム読込パスを介してマルチポートＳＲＡＭ２０２５に接続される通信コントローラ２０３０を用いて確定的にプログラムされてもよい。もしくは、ＣＣＲ２０５１のプログラミングは、ルーティングロジック２０３５に接続されたＤＣＣ入力ポート２００４を通って到着した専用制御ワードによって決定されてもよい。この制御ワードは、ルーティングロジック２０３５として解釈されてもよく、通信コントローラ２０３０に対しても与えられてもよい。
【０３１９】
通信コントローラ２０３０は、１つ以上のＤＣＣ入力ポート２００４から１つ以上のＤＣＣ出力ポート２００５にデータをルーティングするようにクロスバー２０５０に指示してもよく、それによってデータをＭＭＡＰアレイにおいてパスに沿って中継してもよい。ＤＣＣ２０００は、データに対する追加の通信パスを提供してもよい。図示の実施形態において、マルチポートＳＲＡＭ２０２５は、複数のｍｕｘまたはマルチプレクサを介してＤＣＰ入力ポート２００１または出力レジスタ２０５５のいずれかから書込ポートにおいてデータを受信してもよい。このマルチプレクサによって、通信コントローラ２０３０は、マルチポートＳＲＡＭ２０２５がアイドル状態であるときにマルチポートＳＲＡＭ２０２５にアクセスできるようになる。通信コントローラ２０３０は、マルチポートＳＲＡＭ２０２５から１つのＤＣＣ出力ポート２００２へデータが送信されるように誘導したり、汎用マイクロコンピュータ（ＧＰＭＣ）の直接メモリアクセス（ＤＭＡ）と類似した方法で、１つのＤＣＣ入力ポート２００４から読み出されたデータをクロスバー２０５０を介してルーティングして、マルチポートＳＲＡＭ２０２５に書き込むように誘導したりするようにプログラムされてもよい。プログラム読込パスによって、通信コントローラ２０３０はプログラムオーバーレイをマルチポートＳＲＡＭ２０２５から通信コントローラ２０３０内部の命令ＲＡＭ（不図示）に動的に読み込むことができる。
【０３２０】
さらに、図示の実施形態において、ＤＣＰがルーティングロジック２０３５に対するＤＣＣ出力ポートアクセス要求を書いたことを検出するために、ＤＣＣポートデコーダ２０１０は使用されてもよい。それによって１つのＤＣＣ出力ポート２００５が要求された場合、ルーティングロジック２０３５は、ＤＣＰ入力ポート２００１を介して要求ＤＣＰから受信したデータワードを複数のマルチプレクサを介してクロスバー２０５０へ誘導する。この機能によって、所与のＤＣＰは、マルチポートＳＲＡＭ２０２５にデータワードをまず格納するのではなく、ＤＣＣ出力ポート２００５を介して他のＤＣＣへデータを送信できるようになる。
【０３２１】
以下の節は、本発明の典型的な実施形態を説明するものである。
【０３２２】
１．（ａ）シンボルデータシーケンスをチャンネルから受信し、前記シンボルデータシーケンスは、送信機によってチャンネル上に送出された第２のシンボルデータシーケンスに対応し、前記第２のシンボルデータシーケンスは、関連情報ビットに基づいて前記送信機によって生成され、（ｂ）２つ以上のプロセッサからなる第１の組は、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作し、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応し、第１のトレリスは、シンボルデータシーケンスにおける冗長性を示し、前記動作が関連情報ビットに対する軟推定を生成し、この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成できる方法。
２．２つ以上のプロセッサからなる前記第１の組は、プロセッサ列から選択され、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する請求項１記載の方法。
３．前記方法は、さらに、複数の受信シンボルデータシーケンスのそれぞれに対して（ａ）および（ｂ）を実行し、前記受信シンボルデータシーケンスの少なくとも１つに対して、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整することを含む請求項１記載の方法。
４．前記シンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整することは、前記受信シンボルデータシーケンスの長さに基づいて実行される請求項３記載の方法。
５．前記受信シンボルデータシーケンスの少なくとも１つに対して、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項３記載の方法、
６．請求項１記載の方法において、前記第２のシンボルデータシーケンスは関連情報ビットの畳込み符号化に基づいて生成され、第１のトレリスは畳込み符号化に基づく構造を有し、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる第１の組が並行して実行する前記動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ復号化を実現することを含む方法。
７．請求項１記載の方法において、前記第１のトレリスは、前記シンボルデータシーケンスと第２のシンボルデータシーケンスとの所与の線形関係に基づいた構造を有し、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して２つ以上のプロセッサからなる前記第１の組が並行して実行する前記の動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復調処理を並行して実行し、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ等化を実現することを含む方法。
８．請求項１記載の方法において、前記送信機は元の情報ビットの畳込み符号化によって符号化ビットを得て、その符号化ビットをインターリーブすることによって関連情報ビットを生成し、（ｂ）は、２つ以上のプロセッサからなる第１の組が符号化ビットに対する軟推定をインターリーブしたものの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作することを含み、前記方法はさらに（ｃ）２つ以上のプロセッサからなる第２の組は、関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作し、デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応し、前記第２のトレリスは畳込み符号化に対応する構造を有し、前記デインターリーブしたものの２つ以上の重複サブシーケンスに対する前記並行動作は符号化ビットに対する軟推定を生成する方法。
９．（ｄ）（ｂ）および（ｃ）を複数回反復することをさらに含む請求項８記載の方法。
１０．請求項９記載の方法は、前記２つ以上のプロセッサからなる第２の組が、前記関連情報ビットに対する軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作して、元の情報ビットに対する軟推定を生成することを含む方法。
１１．（ｂ）は復調処理を表し、（ｃ）は復号化処理を表し、（ｄ）は前記シンボルデータシーケンスのターボ等化を実現する請求項９記載の方法。
１２．（ｂ）は第１の復号化処理を表し、（ｃ）は第２の復号化処理を表し、（ｄ）は前記シンボルデータシーケンスのターボ復号化を実現する請求項９記載の方法。
１３．前記（ｂ）および（ｃ）の反復は、所定の閾値を超える前記符号化ビットの軟推定および関連情報ビットの軟推定に基づいて停止される請求項９記載の方法。
１４．複数の受信シンボルデータシーケンスのそれぞれに対して（ａ）〜（ｄ）を実行し、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対する２つ以上のプロセッサからなる前記第１の組の数を調整することをさらに含む請求項９記載の方法。
１５．複数の受信シンボルデータシーケンスのそれぞれに対して（ａ）〜（ｄ）を実行し、複数の受信シンボルデータシーケンスのうちの少なくとも１つに対する２つ以上のプロセッサからなる前記第２の組の数を調整することをさらに含む請求項９記載の方法。
１６．請求項９記載の方法は、複数の受信シンボルデータシーケンスのそれぞれに対して（ａ）〜（ｄ）を実行し、受信シンボルデータシーケンスの少なくとも１つに対して前記シンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整し、受信シンボルデータシーケンスの少なくとも１つに対して関連情報ビットの軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスの数を調整することをさらに含む方法。
１７．請求項１６記載の方法において、前記のシンボルデータシーケンスの２つ以上の重複サブシーケンスの数を調整することと、前記のデインターリーブしたものの２つ以上の重複サブシーケンスの数を調整することは、受信シンボルデータシーケンスの現在の１つの長さを受信シンボルデータシーケンスの前の１つと比べた変化に基づいて実行する方法。
１８．前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項９記載の方法。
１９．前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量の前記調整は、前記（ｂ）および（ｃ）の複数の反復の少なくとも１つに対して実行される請求項１８記載の方法。
２０．関連情報ビットの軟推定の前記デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項９記載の方法。
２１．前記デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量の前記調整は、前記（ｂ）および（ｃ）の複数の反復の少なくとも１つに対して実行される請求項２０記載の方法。
２２．前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整し、関連情報ビットの軟推定の前記デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量を調整することをさらに含む請求項９記載の方法。
２３．請求項２２記載の方法において、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量の前記調整は、前記（ｂ）および（ｃ）の複数の反復の少なくとも１つに対して実行され、前記デインターリーブしたものの２つ以上の重複サブシーケンス間の重複量の前記調整は、前記（ｂ）および（ｃ）の複数の反復の少なくとも１つに対して実行される方法。
２４．請求項９記載の方法において、前記シンボルデータシーケンスの前記２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含み、（ｂ）は第１の組のプロセッサのうちの各プロセッサが前記第１のトレリスの対応部分に対してフォワードトレリス走査を実行して、前記第１のトレリスの対応部分の各時間ステップにおけるフォワード走査値を得て、前記フォワード収束領域を使用して前記フォワードトレリス走査における収束を得る方法。
２５．請求項２４記載の方法は、前記フォワード収束領域の長さを（ｂ）および（ｃ）の前記複数の反復のうち現在までに完了した反復の数の関数として減少させることをさらに含む方法。
２６．請求項９記載の方法において、前記シンボルデータシーケンスの前記２つ以上のサブシーケンスの少なくとも１つはバックワード収束領域を含み、（ｂ）は、前記第１の組のプロセッサのうちの前記プロセッサのそれぞれが前記第１のトレリスの対応部分に対してバックワードトレリス走査を実行して、前記第１のトレリスの対応部分の各時間指数におけるバックワード走査値を得ることを含み、前記バックワード収束領域は、前記バックワードトレリス走査において収束を得るために使用される方法。
２７．請求項２６記載の方法は、前記バックワード収束領域の長さを（ｂ）および（ｃ）の前記複数の反復のうち現在までに完了した反復の数の関数として減少させることをさらに含む方法。
２８．請求項９記載の方法において、（ｂ）は、前記関連情報ビットに関する内部情報および外部情報の生成を含み、前記第１の組の各プロセッサは、前記内部情報と前記外部情報との混合情報に基づいて前記関連情報ビットに対する軟推定を生成し、（ｂ）および（ｃ）の複数回の反復のうちの現在完了している反復の数に応じて、前記混合情報に含まれる内部情報の量を増加させる方法。
２９．請求項９記載の方法において、（ｃ）は、前記符号化ビットに関する内部情報および外部情報の生成を含み、前記第２の組の各プロセッサは、前記内部情報と前記外部情報との混合情報に基づいて前記符号化ビットに対する軟推定を生成し、（ｂ）および（ｃ）の複数回の反復のうちの現在完了している反復の数に応じて、前記混合情報に含まれる内部情報の量を増加させる方法。
３０．請求項９記載の方法は、前記関連情報ビットの軟推定をデインターリーブしたものを、前記関連情報ビットの前記軟推定に対してデパンクチャおよびデインターリーブを実行することによって生成することをさらに含み、前記デパンクチャは、あらかじめ演算された値を出力シーケンスのパンクチャ位置に投入することを含み、前記あらかじめ演算された値は、（ｃ）の前の反復において前記第２の組のプロセッサによって演算された符号化ビットに対する軟推定のうちで指定されたものである方法。
３１．請求項９記載の方法において、（ｂ）は、第１の組のプロセッサのうちの前記プロセッサのそれぞれが前記第１のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含み、前記第１の組のプロセッサの所与のプロセッサに対して、前記フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、前記アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含み、前記ベクトルＥの全成分は小さな正の数と等しい方法。
３２．請求項９記載の方法において、（ｂ）は、第２の組のプロセッサのうちの前記プロセッサのそれぞれが前記第２のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含み、前記第２の組のプロセッサの所与のプロセッサに対して、前記フォワードパスは、所与のデータ位置におけるアルファベクトルを算出し、前記アルファベクトルが零ベクトルに等しいという判断に応じて前記ベクトルＥに等しいアルファベクトルを設定することを含み、前記ベクトルＥの全成分は小さな正の数と等しい方法。
３３．請求項９記載の方法において、２つ以上のプロセッサからなる前記第１の組は、２つ以上のプロセッサからなる前記第２の組と同一であり、（ｂ）の各反復は、第１のプログラムコードを、前記第１の組のプロセッサのうちの各プロセッサの命令メモリに読み込むことを含み、前記第１のプログラムコードは、前記第１の組の各プロセッサによって実行されると、前記プロセッサに、前記シンボルデータシーケンスの対応サブシーケンスおよび前記符号化ビットに対する軟推定をインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させ、（ｃ）の各反復は第２のプログラムコードを前記第１の組のプロセッサのうちの各プロセッサの前記命令メモリに読み込み、前記第２のプログラムコードは、前記第１の組の各プロセッサによって実行されると、前記プロセッサに、前記関連情報ビットに対する軟推定をデインターリーブしたものの対応サブシーケンスに対してフォワード／バックワードアルゴリズムを実行させる方法。
３４．前記元の情報ビットの軟推定に基づく受信メッセージを形成することをさらに含む請求項１記載の方法。
３５．前記受信メッセージを用いて出力装置を駆動することをさらに含む請求項３４記載の方法。
３６．チャンネルから受信したシンボルデータシーケンスに対して動作するシステムであって、前記シンボルデータシーケンスは、送信機によってチャンネル上に送出された第２のシンボルデータシーケンスに対応し、前記第２のシンボルデータシーケンスは、関連情報ビットに基づいて生成され、前記システムは、それぞれが第１のプログラムコードで構成される２つ以上のプロセッサからなる第１の組を備え、前記第１のプログラムコードは、前記第１の組のプロセッサによって実行されると、前記第１の組のプロセッサがシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作するようにし（ａ）、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれは、第１のトレリスの各部に対応し、第１のトレリスは、シンボルデータシーケンスにおける冗長性を示し、前記動作が関連情報ビットに対する軟推定を生成し、この軟推定を使用して、関連情報ビットに対応する受信メッセージを形成できるシステム。
３７．２つ以上のプロセッサからなる前記第１の組は、プロセッサ列から選択され、プロセッサ列のプロセッサは相互接続されて、平面格子を形成する請求項３６記載のシステム。
３８．前記受信シンボルデータシーケンスの少なくとも１つに対して、前記シンボルデータシーケンスの２つ以上の重複サブシーケンス間の重複量を調整する手段をさらに備える請求項３６記載のシステム。
３９．請求項３６記載のシステムにおいて、前記第２のシンボルデータシーケンスは関連情報ビットの畳込み符号化に基づいて生成され、第１のトレリスは畳込み符号化に基づく構造を有し、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して実行する前記動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ復号化を実現することを含むシステム。
４０．請求項３６記載のシステムにおいて、前記第１のトレリスは、前記シンボルデータシーケンスと第２のシンボルデータシーケンスとの所与の線形関係に基づいた構造を有し、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して実行する前記の動作は、シンボルデータシーケンスの２つ以上の重複サブシーケンスに対して復調処理を並行して実行し、シンボルデータシーケンスの２つ以上の重複サブシーケンスのそれぞれのビタビ等化を実現することを含むシステム。
４１．請求項３６記載のシステムにおいて、前記送信機は元の情報ビットの畳込み符号化によって符号化ビットを得て、その符号化ビットをインターリーブすることによって関連情報ビットを生成し、（ａ）は２つ以上のプロセッサからなる第２の組が符号化ビットに対する軟推定をインターリーブしたものの２つ以上の各重複サブシーケンスを用いてシンボルデータシーケンスの２つ以上の重複サブシーケンスに対して並行して動作することを含み、前記システムは、第２のプログラムコードで構成される２つ以上のプロセッサからなる第２の組をさらに備え、前記第２のプログラムコードは、前記第２の組の前記プロセッサのそれぞれによって実行されると、前記第２の組の前記プロセッサのそれぞれが関連情報ビットの軟推定をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作（ｂ）し、デインターリーブしたものの２つ以上の重複サブシーケンスのそれぞれは、第２のトレリスの各部に対応し、前記第２のトレリスは畳込み符号化に対応する構造を有し、デインターリーブしたものの２つ以上の重複サブシーケンスに対する前記並行動作は符号化ビットに対する軟推定を生成するシステム。
４２．前記２つ以上のプロセッサからなる第１の組および前記２つ以上のプロセッサからなる第２の組は、（ａ）および（ｂ）を複数回交互に実行するようにプログラムされる請求項４１記載のシステム。
４３．請求項４２記載のシステムにおいて、前記２つ以上のプロセッサからなる第２の組はそれぞれ追加プログラムコードで構成され、前記追加プログラムコードは、前記第２の組の前記プロセッサのそれぞれによって実行されると、前記第２の組の各プロセッサが前記関連情報ビットに対する軟推定のデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して動作するようにして元の情報ビットに対する軟推定を生成するシステム。
４４．請求項４２記載のシステムにおいて、前記第１の組の各プロセッサおよび前記第２の組の各プロセッサは、前記符号化ビットの軟推定に応じておよび前記関連情報ビットの軟推定が所定の閾値を超えた場合に、前記（ａ）および（ｂ）を複数回交互に実行することを停止するようにプログラムされているシステム。
４５．請求項４２記載のシステムにおいて、前記シンボルデータシーケンスの前記２つ以上のサブシーケンスの少なくとも１つは、フォワード収束領域を含み、（ａ）は第１の組のプロセッサのうちの各プロセッサが前記第１のトレリスの対応部分に対してフォワードトレリス走査を実行して、前記第１のトレリスの対応部分の各時間ステップにおけるフォワード走査値を得ることを含み、前記フォワード収束領域を使用して、前記フォワードトレリス走査における収束を得るシステム。
４６．請求項４５記載のシステムにおいて、前記第１のプログラムコードは、第１の組のプロセッサによって実行されると、前記第１の組の各プロセッサに前記フォワード収束領域の長さを（ａ）および（ｂ）の前記複数の実行のうち現在までに完了した実行数の関数として減少させるシステム。
４７．請求項４２記載のシステムにおいて、前記シンボルデータシーケンスの前記２つ以上のサブシーケンスの少なくとも１つはバックワード収束領域を含み、（ｂ）は、前記第１の組のプロセッサのうちの前記プロセッサのそれぞれが前記第１のトレリスの対応部分に対してバックワードトレリス走査を実行して、前記第１のトレリスの対応部分の各時間指数におけるバックワード走査値を得ることを含み、前記バックワード収束領域は、前記バックワードトレリス走査において収束を得るために使用されるシステム。
４８．請求項４７記載のシステムにおいて、前記第２のプログラムコードは、第２の組のプロセッサによって実行されると、前記第２の組の各プロセッサに前記バックワード収束領域の長さを（ａ）および（ｂ）の前記複数の実行のうち現在までに完了した実行数の関数として減少させるシステム。
４９．請求項４２記載のシステムにおいて、（ａ）は、前記関連情報ビットに関する内部情報および外部情報の生成を含み、前記第１のプログラムコードは、前記第１の組の各プロセッサによって実行されると、前記第１の組の各プロセッサが前記内部情報と前記外部情報との混合情報に基づいて前記関連情報ビットに対する軟推定を並行して生成するようにし、（ａ）および（ｂ）の前記複数回の実行のうちの現在完了している実行の数に応じて、前記混合情報に含まれる内部情報の量を増加させるシステム。
５０．請求項４２記載のシステムにおいて、（ｂ）は、前記符号化ビットに関する内部情報および外部情報の生成を含み、前記第２のプログラムコードは、前記第２の組の各プロセッサによって実行されると、前記第２の組の各プロセッサが、前記内部情報と前記外部情報との混合情報に基づいて前記符号化ビットに対する軟推定を生成するようにし、（ａ）および（ｂ）の前記複数回の実行のうちの現在完了している実行の数に応じて、前記混合情報に含まれる内部情報の量を増加させるシステム。
５１．請求項４２記載のシステムは、前記関連情報ビットの軟推定をデインターリーブしたものを、前記関連情報ビットの前記軟推定に対してデパンクチャおよびデインターリーブを実行することによって生成するように構成された１つ以上のプロセッサからなる第３の組をさらに含み、前記デパンクチャは、あらかじめ演算された値を出力シーケンスのパンクチャ位置に投入することを含み、前記あらかじめ演算された値は、（ｂ）の前の実行において前記第２の組のプロセッサによって演算された符号化ビットに対する軟推定のうちで指定されたものである。
５２．請求項４２記載のシステムにおいて、（ａ）は、第１の組のプロセッサのうちの前記プロセッサのそれぞれが前記第１のトレリスの対応部分を介して、フォワードパスおよびバックワードパスを実行することを含み、前記第１の組のプロセッサの所与のプロセッサに対して、前記フォワードパスは、所与のシンボル位置におけるアルファベクトルを算出し、前記アルファベクトルが零ベクトルに等しいという判断に応じてベクトルＥに等しいアルファベクトルを設定することを含み、前記ベクトルＥの全成分は小さな正の数と等しいシステム。
５３．請求項４２記載のシステムにおいて、２つ以上のプロセッサからなる前記第１の組は、２つ以上のプロセッサからなる前記第２の組と同一であり、前記第１の組のプロセッサのうちの各プロセッサは（ａ）の各実行前に前記第１のプログラムコードを読み込み、（ｂ）の各実行前に前記第２のプログラムコードを読み込むようにプログラムされたシステム。
５４．（ａ）チャンネルからシンボルデータシーケンスを受信し、前記シンボルデータシーケンスは、前記チャンネル上に送出された第２のシンボルデータシーケンスに対応し、前記第２のシンボルデータシーケンスは、元の情報ビットに基づいて生成され、
（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバック情報をインターリーブしたものの２つ以上の対応サブシーケンスを用いて、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスに並行して復調処理を実行して、フィードフォワード情報を生成し、
（ｃ）２つ以上のプロセッサからなる第２の組が、前記フィードフォワード情報をデインターリーブしたものの２つ以上の重複サブシーケンスに対して並行して復号化処理を実行して、前記フィードバック情報を生成し、
（ｄ）（ｂ）および（ｃ）を含む処理の組を繰り返し、
（ｅ）２つ以上のプロセッサからなる第３の組が並行して動作し、前記フィードフォワード情報のデインターリーブしたものの２つ以上の重複サブシーケンスの非重複部分から元の情報ビットに対する軟推定を生成する
ことを含む方法であって、
前記軟推定は、前記元の情報ビットに対応する受信メッセージを形成するのに使用可能である方法。
５５．前記第３の組の各プロセッサは前記第２の組の各プロセッサと同一である請求項５４記載の方法。
５６．前記第１の組の各プロセッサは前記第２の組の各プロセッサと同一である請求項５４記載の方法。
５７．（ａ）チャンネルを介してシンボルデータシーケンスを受信し、前記シンボルデータシーケンスは、前記チャンネル上に送出された第２のシンボルデータシーケンスに対応し、前記第２のシンボルデータシーケンスは、元の情報ビットに基づいて生成され、
（ｂ）２つ以上のプロセッサからなる第１の組が、フィードバックデータシーケンスの２つ以上の対応サブシーケンスを用いて、前記シンボルデータシーケンスの２つ以上の重複サブシーケンスに並行して復調処理を実行して、フィードフォワード情報の２つ以上の対応ブロックを生成し、
（ｃ）１つ以上のプロセッサからなる第２の組がフィードフォワード情報の前記２つ以上のブロックから組み立てられた第１の合成シーケンスに対してデインターリーブを実行して、修正データシーケンスを生成し、
（ｄ）２つ以上のプロセッサからなる第３の組が、前記修正データシーケンスの２つ以上の重複サブシーケンスに対して復号化処理を並行して実行して、フィードバック情報の２つ以上の対応するブロックを生成し、
（ｅ）１つ以上のプロセッサからなる第４の組が、フィードバック情報の前記２つ以上のブロックから組み立てられた第２の合成シーケンスに対してインターリーブを実行して、フィードバックデータシーケンスを生成し、
（ｆ）（ｂ）、（ｃ）、（ｄ）および（ｅ）を含む処理の組を繰り返し、
（ｇ）２つ以上のプロセッサからなる前記第３の組が並行して動作して、前記修正データシーケンスの前記２つ以上の対応サブシーケンスの非対応領域から前記元の情報ビットに対する軟推定を生成する
ことを含む方法であって、
前記軟推定は、前記元の情報ビットに対応する受信メッセージを形成するのに使用可能である方法。
５８．前記第１、第２、第３および第４の組のプロセッサは、プロセッサの列から選択され、前記プロセッサ列のプロセッサは相互接続されて、平面格子を形成する請求項５７記載の方法。
５９．プロセッサの前記第１、第２、第３および第４の組は互いに素の組である請求項５７記載の方法。
６０．２つ以上のプロセッサからなる第１の組は前記２つ以上のプロセッサからなる第３の組と同一である請求項５７記載の方法。
６１．前記１つ以上のプロセッサからなる第２の組は前記１つ以上のプロセッサからなる第４の組と同一である請求項５７記載の方法。
【０３２３】
上記実施形態について非常に詳細に説明したが、上記開示が十分に理解されれば、数多くの変形および修正が当業者には明らかである。以下の特許請求の範囲の記載はそのような変形および修正を包含するように解釈されることを意図している。
【図１Ａ】
0005406369.tif 000009
【図１Ｂ】
0005406369.tif 000010
【図２】
0005406369.tif 000011
【図３】
0005406369.tif 000012
【図４】
0005406369.tif 000013
【図５】
0005406369.tif 000014
【図６】
0005406369.tif 000015
【図７】
0005406369.tif 000016
【図８】
0005406369.tif 000017
【図９】
0005406369.tif 000018
【図１０】
0005406369.tif 000019
【図１１】
0005406369.tif 000020
【図１２】
0005406369.tif 000021
【図１３Ａ】
0005406369.tif 000022
【図１３Ｂ】
0005406369.tif 000023
【図１４】
0005406369.tif 000024
【図１５Ａ】
0005406369.tif 000025
【図１５Ｂ】
0005406369.tif 000026
【図１６Ａ】
0005406369.tif 000027
【図１６Ｂ】
0005406369.tif 000028
【図１７】
0005406369.tif 000029
【図１８】
0005406369.tif 000030
【図１９】
0005406369.tif 000031
【図２０】
0005406369.tif 000032
【図２１】
0005406369.tif 000033