(57)【要約】  ＭＡＰ復号器は、又は構成要素となるＭＡＰ復号器を有するターボ復号器は、双方向スライディングウィンドウで構成される。スライディングウィンドウアーキテクチャは、Ｎ個の時間ステップを有するトレリスを有する符号化されたデータブロックの順方向状態メトリック（ＦＳＭ）計算に適用される。データブロックは、より小さなサブブロックに分割され、サブブロックのうちの２つ以上の順方向再帰が並列に行われて、ＦＳＭが取得される。各サブブロックは、前のサブブロックとｋ個の時間ステップだけオーバーラップし、ここで、ｋは０よりも大きな整数値である。これによって、サブブロックの時間ステップｋ＋ｔにおけるＦＳＭの良好な近似が提供される。最初のサブブロック以外の各サブブロックの最初のｋ個の時間ステップに関連付けられているＦＳＭは廃棄される。各サブブロックの逆方向再帰も行われて、そのサブブロックの逆方向状態メトリック（ＲＳＭ）が取得される。次に、ＦＳＭ及びＲＳＭに基づいて尤度比が計算される。
2009525009.tif 000002
【特許請求の範囲】
【請求項１】
復号器であって、
スライディングウィンドウアーキテクチャを使用してデータブロックを複数のサブブロックに分割するブロック分割器と、
前記ブロック分割器に結合されて、前記複数のサブブロックを受信する第１の復号器であって、前記複数のサブブロックのうちの少なくとも２つの状態メトリックの第１のセットを並列に求める複数の並列復号器を含む、第１の復号器と、
前記第１の復号器に結合されて、前記第１の復号器から前記複数のサブブロックを受信すると共に前記複数のサブブロックの状態メトリックの第２のセットを計算する第２の復号器と
を備える、復号器。
【請求項２】
前記第１の復号器及び前記第２の復号器は、最大事後確率（ＭＡＰ）アルゴリズムを実施して前記データブロックのエラーを訂正する、請求項１に記載の復号器。
【請求項３】
前記第１の復号器は、前記データブロックのトレリスの順方向状態メトリックを求める、請求項１に記載の復号器。
【請求項４】
各サブブロックは、直前のサブブロックと前記トレリスのｋ個の時間ステップだけオーバーラップし、ここで、ｋは、０よりも大きな整数値である、請求項３に記載の復号器。
【請求項５】
最初のサブブロックより後の各サブブロックの最初のｋ個の時間ステップに関連付けられている前記メトリックは、状態メトリックの前記第１のセットから廃棄される、請求項４に記載の復号器。
【請求項６】
前記第２の復号器は、前記データブロックの前記トレリスの逆方向状態メトリックを求める、請求項３に記載の復号器。
【請求項７】
サブブロックの長さは、復号時間制約によって決定される、請求項１に記載の復号器。
【請求項８】
サブブロックの個数は、前記第１の復号器の並列復号器の個数を決定する、請求項１に記載の復号器。
【請求項９】
前記データブロックは、ターボ符号で符号化されている、請求項１に記載の復号器。
【請求項１０】
前記第１の復号器の前記並列復号器は、各サブブロックの順方向状態メトリックを計算する再帰的復号器である、請求項１に記載の復号器。
【請求項１１】
前記第２の復号器は、前記第１の復号器から受信した各サブブロックを複数のより小さなセグメントにさらに分割し、前記複数のより小さなセグメントに対してスライディングウィンドウアーキテクチャを使用して、状態メトリックの前記第２のセットを計算する、請求項１に記載の復号器。
【請求項１２】
状態メトリックの前記第１のセットを記憶するストレージデバイスをさらに備える、請求項１に記載の復号器。
【請求項１３】
各サブブロックは複数のセグメントを含み、現在のセグメント及び前のセグメントのメトリックの前記第１のセットは、いずれの時点においても前記ストレージデバイスに記憶されている、請求項１２に記載の復号器。
【請求項１４】
セグメントのメトリックの前記第１のセットは、前記セグメントの尤度比が計算されると、前記ストレージデバイスから廃棄される、請求項１３に記載の復号器。
【請求項１５】
状態メトリックの前記第１のセット及び状態メトリックの前記第２のセットは、前記データブロックのデータの尤度比の計算に使用される、請求項１に記載の復号器。
【請求項１６】
前記第２の復号器は複数の並列復号器を含み、前記第２の復号器の各並列復号器は、前記第１の復号器の前記複数の並列復号器のうちの１つに対応する、請求項１に記載の復号器。
【請求項１７】
各サブブロックは複数のセグメントを含み、前記第２の復号器は、前記第１の復号器がセグメントの状態メトリックの前記第１のセットを計算すると、そのセグメントの状態メトリックの前記第２のセットを計算するように構成される、請求項１に記載の復号器。
【請求項１８】
符号化されたブロックの情報を再帰的に復号する方法であって、
前記符号化されたデータブロックを複数のより小さなサブブロックに分割することであって、各サブブロックは複数のより小さなセグメントを含む、分割することと、
前記サブブロックのうちの２つ以上の順方向状態メトリックを並列に取得することと、
順方向状態メトリックがセグメントについて取得されると、そのセグメントの逆方向状態メトリックを取得することと
を含む、方法。
【請求項１９】
サブブロックは、既知のバイナリ状態を有する最初の時間ステップで開始する、請求項１８に記載の方法。
【請求項２０】
各サブブロックが、前のサブブロックと、前記符号化されたブロックのトレリスのｋ個の時間ステップだけオーバーラップするように、スライディングウィンドウアーキテクチャが前記符号化されたブロックの分割に使用され、ここで、ｋは、０よりも大きな整数値である、請求項１８に記載の方法。
【請求項２１】
最初のサブブロックより後の各サブブロックの最初のｋ個の時間ステップに関連付けられている前記順方向状態メトリックを廃棄することをさらに含む、請求項２０に記載の方法。
【請求項２２】
Ｎ個の時間ステップを有するトレリスを有する情報の前記符号化されたブロックを受信することと、
前記符号化されたブロックをＮ／Ｌ個のサブブロックに分割することであって、ここで、Ｌは、０よりも大きな整数値である、分割することと、
前記Ｎ／Ｌ個のサブブロックの順方向状態メトリックを並列に計算することと
をさらに含む、請求項１８に記載の方法。
【請求項２３】
状態メトリックの前記第１のセット及び前記第２のセットに基づいて、前記データブロックのデータの尤度比を取得することをさらに含む、請求項１８に記載の方法。
【請求項２４】
サブブロックの前記順方向状態メトリックを取得することを含み、開始ステップは、同等に確からしい状態メトリックを有する未知の状態である、請求項１８に記載の方法。
【請求項２５】
各サブブロックの最初のセグメントのメトリックの前記第１のセットを記憶することと、
前記最初のセグメントの前記第１の状態メトリック及び前記第２の状態メトリックに基づいて前記最初のセグメントの尤度比を取得することと、
前記最初のセグメントの尤度比が取得されると、各サブブロックの前記最初のセグメントのメトリックの前記第１のセットを廃棄することと
をさらに含む、請求項１８に記載の方法。
【請求項２６】
復号器であって、
符号化されたデータブロックを複数のサブブロックに分割する手段であって、前記符号化されたデータブロックはＮ個の時間ステップを有するトレリスを有し、ここで、Ｎは、０よりも大きな整数である、分割する手段と、
前記サブブロックのうちの２つ以上の順方向状態メトリックを並列に再帰的に取得する手段と、
前記サブブロックのうちの２つ以上の逆方向状態メトリックを並列に再帰的に取得する手段と
を備える、復号器。
【請求項２７】
各サブブロックは、前のサブブロックと、前記符号化されたブロックの前記トレリスのｋ個の時間ステップだけオーバーラップし、ここで、ｋは、０よりも大きな整数値であり、最初のサブブロックより後の各サブブロックの最初のｋ個の時間ステップに関連付けられている前記順方向状態メトリックは廃棄される、請求項２６に記載の復号器。
【請求項２８】
各サブブロックは複数のセグメントを含み、前記逆方向状態メトリックは、セグメントの前記順方向状態メトリックが取得されると、そのセグメントについて取得される、請求項２６に記載の復号器。
【請求項２９】
前記順方向状態メトリック及び前記逆方向状態メトリックに基づいてセグメントの尤度比を取得する手段をさらに備える、請求項２６に記載の復号器。
【請求項３０】
処理デバイスであって、
Ｎ個の時間ステップを有する状態トレリスを有する符号化されたデータブロックを受信することであって、ここで、Ｎは、２よりも大きな正の整数である、受信することと、
前記符号化されたデータブロックを再帰的に復号することであって、
前記符号化されたブロックを複数のサブブロックに分割すること、及び
前記サブブロックのうちの２つ以上の順方向メトリックを並列に取得すること
による、復号することと
を制御するように構成される、処理デバイス。
【請求項３１】
再帰的に復号することは、前記サブブロックのうちの２つ以上の逆方向状態メトリックを取得することをさらに含む、請求項３０に記載の処理デバイス。
【請求項３２】
各サブブロックは複数のセグメントを含み、逆方向状態メトリックは、セグメントの前記順方向状態メトリックが取得されると、そのセグメントについて取得される、請求項３１に記載の処理デバイス。
【請求項３３】
最初のサブブロックより後の各サブブロックは、前のサブブロックと、前記トレリスのｋ個の時間ステップだけオーバーラップし、ここで、ｋは、０よりも大きな整数値であり、
前記処理デバイスは、最初のサブブロックより後の各サブブロックの最初のｋ個の時間ステップに関連付けられている前記順方向状態メトリックを廃棄するようにさらに構成され、ここで、ｋは、０よりも大きな整数である、請求項３０に記載の処理デバイス。
【請求項３４】
符号化されたブロックの情報を再帰的に復号するための命令を含む機械可読媒体であって、
前記命令は、
前記符号化されたデータブロックを複数のより小さなサブブロックに分割し、各サブブロックは複数のより小さなセグメントを含み、
前記サブブロックのうちの２つ以上の順方向状態メトリックを並列に取得し、
順方向状態メトリックがセグメントについて取得されると、そのセグメントの逆方向状態メトリックを取得する
ように構成される、機械可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
<米国特許法第１１９条に基づく優先権の主張>
本特許出願は、２００６年１月２７日に出願された「MAP Decoder with Bi-Directional Sliding Window Architecture」という発明の名称の仮出願第６０／７６２，７６４号の優先権を主張する。この仮出願は、本特許出願の譲受人に譲渡され、この記載によって、参照により本明細書に明示的に援用される。
【０００２】
［背景］
<分野>
本発明のさまざまな実施の形態は、通信システムに関し、より詳細には、デジタル通信システムにおいてデータを復号するデバイス及び／又は方法に関する。
【０００３】
<背景>
通信システムは、多数の技法を使用して、転送される情報量を増加させると同時に、伝送エラーを最小にする。これらの通信システムでは、情報は、通常、フレームと呼ばれるバイナリビットのシーケンス又はビットのブロックとして表される。バイナリ情報は、信号波形に変調され、通信チャネルによって送信される。通信チャネルは、送信信号を破損する雑音及び干渉を持ち込む傾向がある。受信機では、受信された情報は破損されているおそれがあり、送信バイナリ情報の推定である。ビットエラー数又はフレームエラー数は、通信チャネルの雑音及び干渉の量に依存する。
【０００４】
伝送チャネルの破損の影響に対抗するために、デジタル通信システムでは、多くの場合、エラー訂正符号化が使用されて、デジタル情報が雑音及び干渉から保護され、ビットエラー数／フレームエラー数が低減される。チャネル符号化は、通常、送信情報ストリーム内に冗長ビットを選択的に導入することによって行われる。これらの追加ビットによって、受信したデータストリーム内のビットエラーの検出及び訂正が可能になり、それによって、より信頼性のある伝送が提供される。
【０００５】
１つのタイプのエラー訂正符号は、ターボ符号として知れられており、シャノン限界に近いエラー訂正性能を有する。ターボ符号化の基本は、チャネルを通じて送信されるデータに冗長性を導入することである。冗長データは、受信したデータからオリジナルデータを回復するのに役立つ。ターボ符号は、シャノンのチャネル容量の約１ｄＢ内までの伝送性能を達成することができる。
【０００６】
通信理論の既知の原理は、十分に大きなブロック長ｎを有するランダムに選ばれた符号は、シャノンのチャネル容量限界に近づくことができるというものである。しかしながら、このような符号の復号は、復号が物理的に実現不可能となる点までｎと共に増加する。
【０００７】
ターボ符号の１つのタイプの復号器として、事後確率(A Posteriori Probability)（ＡＰＰ）アルゴリズムとしても既知である、最大事後(Maximum A Posteriori)（ＭＡＰ）アルゴリズムがある。ＭＡＰアルゴリズムは、ブロックのバイナリトレリスツリーの順方向再帰（forward recursion）を行い、次に、逆方向再帰（reverse recursion）を行うことによってブロックを復号し、トレリスの状態ごとに一対の状態メトリックを取得する。トレリスツリーの順方向再帰は順方向にブロックを復号して、情報シーケンスの第１の推定値（順方向状態メトリック（forward state metric））を取得する。トレリスツリーの逆方向再帰（後方再帰（backward recursion）とも呼ばれる）は、逆方向にブロックを復号して、情報シーケンスの第２の推定値（逆方向状態メトリック（reverse state metric））を取得する。従来のＭＡＰアルゴリズムの実施において、１つの問題は、制限長及び符号ブロック長を控えめにした場合であっても、順方向状態メトリック及び逆方向状態メトリックを記憶するには、並外れたメモリ量を要する可能性があるということである。
【０００８】
従来のＭＡＰアルゴリズムに関するもう１つの問題は、逐次処理（すなわち、順方向再帰及び逆方向再帰）が、復号時間に対する制約を満たすことができない場合があるということである。具体的には、ブロックのバイナリトレリスの順方向再帰を行い、次に、逆方向再帰を行うことは、レートの影響を受けやすいアプリケーションによって許容可能な時間よりも長い時間を要する場合がある。データブロックの復号は、レートの影響を受けやすいアプリケーションによって予想されるよりも長くかかる場合がある。
【０００９】
［概要］
一態様では、復号器は、スライディングウィンドウアーキテクチャを使用してデータブロックを複数のサブブロックに分割するブロック分割器と、ブロック分割器に結合されて、複数のサブブロックを受信する第１の復号器であって、複数のサブブロックのうちの少なくとも２つの状態メトリックの第１のセットを並列に求める複数の並列復号器を含む第１の復号器と、第１の復号器に結合されて、第１の復号器から複数のサブブロックを受信すると共に複数のサブブロックの状態メトリックの第２のセットを計算する第２の復号器とを備える。第１の復号器及び第２の復号器は、最大事後確率（ＭＡＰ）アルゴリズムを実施してデータブロックのエラーを訂正することができる。第１の復号器及び／又は第２の復号器は、データブロックのトレリスの順方向状態メトリックを求めることができる。第２の復号器は、第１の復号器から受信した各サブブロックを複数のより小さなセグメントにさらに分割し、複数のより小さなセグメントに対してスライディングウィンドウアーキテクチャを使用して、状態メトリックの第２のセットを計算することができる。第２の復号器は、複数の並列復号器を含むことができ、第２の復号器の各並列復号器は第１の復号器の複数の並列復号器のうちの１つに対応する。各サブブロックは複数のセグメントを含むことができ、第２の復号器は、第１の復号器がセグメントの状態メトリックの第１のセットを計算すると、そのセグメントの状態メトリックの第２のセットを計算するように構成することができる。
【００１０】
別の態様では、符号化されたブロックの情報を再帰的に復号する方法は、符号化されたデータブロックを複数のより小さなサブブロックに分割することであって、各サブブロックは複数のより小さなセグメントを含む、分割することと、サブブロックのうちの２つ以上の順方向状態メトリックを並列に取得することと、順方向状態メトリックがセグメントについて取得されると、そのセグメントの逆方向状態メトリックを取得することとを含む。この方法は、Ｎ個の時間ステップを有するトレリスを有する情報の符号化されたブロックを受信することと、符号化されたブロックをＮ／Ｌ個のサブブロックに分割することであって、ここで、Ｌは０よりも大きな整数値である、分割することと、Ｎ／Ｌ個のサブブロックの順方向状態メトリックを並列に計算することとをさらに含むことができる。或いは、この方法は、各サブブロックの最初のセグメントのメトリックの第１のセットを記憶することと、最初のセグメントの第１の状態メトリック及び第２の状態メトリックに基づいて最初のセグメントの尤度比を取得することと、最初のセグメントの尤度比が取得されると、各サブブロックの最初のセグメントのメトリックの第１のセットを廃棄することとをさらに含むことができる。
【００１１】
上記復号器及び方法において、各サブブロックは、前のサブブロックと、トレリスのｋ個の時間ステップだけオーバーラップすることができ、ここで、ｋは、０よりも大きな整数値である。最初のサブブロックより後の各サブブロックの最初のｋ個の時間ステップに関連付けられているメトリックは、状態メトリックの第１のセットから廃棄することができる。サブブロックの長さは、復号時間制約によって決定することができる。データブロックは、ターボ符号で符号化することができる。セグメントのメトリックの第１のセットは、そのセグメントの尤度比が計算されると、ストレージデバイスから廃棄することができる。状態メトリックの第１のセット及び状態メトリックの第２のセットは、データブロックのデータの尤度比を計算する際に使用することができる。
【００１２】
説明したような復号器及び／又は方法は、その復号器及び／又は方法の１つ又は複数の機能を実行するように構成されるプロセッサによって実施することができることに留意すべきである。同様に、説明したような復号器及び／又は方法は、命令を含む機械可読媒体によって実施することができ、命令は、復号器及び／又は方法の１つ又は複数の機能を実行するように構成される。
【００１３】
［詳細な説明］
以下の説明では、実施形態の徹底した理解を提供するために具体的な詳細が与えられている。しかしながら、実施形態は、これらの特定の詳細がなくても実施することができることが当業者には理解されよう。たとえば、実施形態を不必要に詳しくして分かりにくくすることがないように、回路は、ブロック図で示される場合がある。
【００１４】
また、実施形態は、フローチャート、フロー図、構造図、又はブロック図として描かれるプロセスとして説明することができることに留意されたい。フローチャートは、逐次プロセスとしてオペレーションを記述する場合があるが、オペレーションの多くは、並列又は同時に行うことができる。加えて、オペレーションの順序は、並べ替えることができる。プロセスは、そのオペレーションが完了するときに終了する。プロセスは、メソッド、関数、プロシージャ、サブルーチン、サブプログラム等に対応することができる。プロセスが関数に対応するとき、その終了は、その関数がコール側関数又はメイン関数に戻ることに対応する。
【００１５】
さらに、ストレージ媒体は、データを記憶する１つ又は複数のデバイスを表すことができる。このデバイスには、読み出し専用メモリ（ＲＯＭ）、ランダムアクセスメモリ（ＲＡＭ）、磁気ディスクストレージ媒体、光ストレージ媒体、フラッシュメモリデバイス、及び／又は情報を記憶する他の機械可読媒体が含まれる。「機械可読媒体」という用語には、ポータブルストレージデバイス又は固定ストレージデバイス、光ストレージデバイス、ワイヤレスチャネル、命令（複数可）及び／若しくはデータを記憶、収容、又は搬送することができる他のさまざまな媒体が含まれるが、これらに限定されるものではない。
【００１６】
さらに、実施形態は、ハードウェア、ソフトウェア、ファームウェア、ミドルウェア、マイクロコード、又はそれらの組み合わせによって実施することができる。ソフトウェア、ファームウェア、ミドルウェア、又はマイクロコードで実施される場合、必要なタスクを行うためのプログラムコード又はコードセグメントを、ストレージ媒体や他のストレージ手段等の機械可読媒体に記憶することができる。プロセッサが、これらの必要なタスクを実行することができる。コードセグメントは、プロシージャ、関数、サブプログラム、プログラム、ルーチン、サブルーチン、モジュール、ソフトウェアパッケージ、クラス、又は、命令、データ構造体、若しくはプログラム命令文の組み合わせを表すことができる。コードセグメントは、情報、データ、引数、パラメータ、若しくはメモリコンテンツを渡し且つ／又は受信することによって、別のコードセグメント又はハードウェア回路に結合することができる。情報、引数、パラメータ、データ等は、適切な手段を介して渡すか、転送するか、又は送信することができる。適切な手段には、中でも、メモリ共有、メッセージパッシング、トークンパッシング、及びネットワーク送信が含まれる。
【００１７】
一般的には、双方向スライディングウィンドウを有する、ＭＡＰ復号器を有するターボ復号器が開示される。または、双方向スライディングウィンドウを有する、構成要素となるＭＡＰ復号器（たとえば、再帰的な順方向復号器（forward decoder）及び逆方向復号器（reverse decoder））を有するターボ復号器が開示される。順方向復号器へのデータブロックはサブブロックに再分割され、それらのサブブロックの順方向再帰が並列に行われる。この手法は、順方向状態メトリックを計算する順方向再帰を、トレリスの最初の時間ステップから開始する必要がないことを認める。その代わり、スライディングウィンドウアーキテクチャが順方向状態メトリック計算に適用される。これによって、順方向状態メトリックに使用されるストレージ空間を（従来のアルゴリズムを上回って）削減することができる。また、順方向状態メトリックが並列に計算されるため、復号時間も削減することができる。
【００１８】
加えて、逆方向復号器では、順方向復号器からのサブブロックをさらに再分割することができる。逆方向状態メトリック計算用のスライディングウィンドウアーキテクチャも、サブブロック（又は順方向スライディングウィンドウ）のそれぞれに適用することができ、したがって、順方向状態メトリックに使用されるストレージが削減される。
【００１９】
図１は、本発明の１つ又は複数の特徴を実施することができる一例の通信システムのブロック図を示している。この通信システムは、第１のデバイス１０２を含む。第１のデバイス１０２は、通信チャネル１０４によって第２のデバイス１０６へ送信する情報を符号化する。第２のデバイス１０６はその情報を復号する。第１のデバイス１０２は、データを受信してエラー訂正符号で符号化する符号化器１０８を含む。符号化されたデータは、その後、情報を搬送波信号上に変調する変調器１１０へ送られる。この搬送波信号は、その後、送信機１１２によって送信される。通信チャネル１０４は、有線、ワイヤレス、無線、衛星、又はそれらの組み合わせを含めて、符号化された情報を受信側の第２のデバイス１０６へ搬送する任意の媒体とすることができる。第２のデバイス１０６は、受信機１１４及び復調器１１６を含む。復調器１１６は、受信信号を復調し、データのパケット、フレーム、又はブロックを復号器１１８に提供する。復号器１１８は、情報を復号してデータ出力を提供する。復号器１１８は、最大事後（ＭＡＰ）アルゴリズム（事後確率（ＡＰＰ）アルゴリズムも呼ばれる）を実施するように構成することができる。
【００２０】
図２は、データを復号するように構成される一例の受信デバイス２０２を示すブロック図である。受信デバイス２０２は、情報を運ぶ信号を通信チャネルから受信する通信インターフェースを含む。この通信インターフェース２０４は、その後、受信された、情報を運ぶ信号を処理システム２０６へ送る。処理システム２０６は、受信信号内の情報を復号するように構成される。
【００２１】
処理システム２０６は、ＭＡＰ復号器として、又は、構成要素となるＭＡＰ復号器（たとえば、再帰的な順方向復号器及び逆方向復号器）を有するターボ復号器として機能すると共に、復号器の順方向再帰パス及び逆方向再帰パスの双方でスライディングウィンドウを実施するように構成される。通信インターフェース２０４から受信した情報はより小さなブロック（すなわち、サブブロック）に再分割され、順方向再帰関数がそれらのサブブロックのうちの２つ以上に対して並列に実行される。この目的のため、処理システム２０６は、並列に動作するように構成される１つ又は複数のプロセッサ、特定用途向け集積回路（ＡＳＩＣ）、及び／又は復号デバイスを含むことができる。順方向復号器は、サブブロックの開始から終了へ状態メトリックを計算する一方、逆方向復号器は、サブブロックの終了から開始へメトリックを計算する。メモリデバイス２０８は、復号プロセス中に生成される順方向状態メトリック及び／又は逆方向状態メトリックを記憶するために処理システム２０６に結合することができる。
【００２２】
追加の特徴は、処理システム２０６が、再分割されたより小さなブロックのそれぞれの逆方向状態メトリック計算用のスライディングウィンドウアーキテクチャを有する逆方向復号器を実施するようにも構成されることを可能にする。逆方向復号器を実施すると、順方向復号器からの再分割されたより小さなブロックをさらに再分割することができ、スライディングウィンドウアーキテクチャは、順方向状態メトリック計算機のサブブロックのそれぞれに並列に適用される。したがって、開示した特徴によって、順方向状態メトリック及び／又は逆方向状態メトリックに使用されるストレージが削減され、さらに、順方向復号器及び／又は逆方向復号器に対する並列復号によって復号時間も削減される。
【００２３】
いくつかの実施態様では、順方向状態メトリック計算機のサブブロックに対して順方向状態計算が完了する前であっても、そのサブブロックに対して、逆方向状態メトリック計算用のスライディングウィンドウアーキテクチャが適用される。すなわち、逆方向状態メトリック計算用のスライディングウィンドウアーキテクチャは、或るサブブロックのセグメントの順方向状態メトリック計算が完了すると、逆方向状態メトリック計算が上記セグメントに対して行われることを意味する。したがって、或るサブブロックのセグメントの逆方向状態メトリック計算は、そのサブブロックの他のセグメントの順方向状態メトリック計算がまだ行われている間に行うことができる。これによって、サブブロックのすべての順方向状態計算が完了するまで待つ必要がないため、全体の計算が促進される。いくつかの実施態様では、セグメントの順方向メトリックが最初に計算され、その後、同じセグメントの逆方向状態メトリックの計算が続く。他の実施態様では、セグメント又はサブブロックの逆方向状態メトリックが最初に計算され、その後、そのサブブロック又はセグメントの順方向状態メトリックの計算が続く。さらに他の実施態様では、セグメントの順方向メトリック及び逆方向メトリックは、ほぼ同時に計算される。例の中には、これらのシーケンスのうちの１つを示すことができるものもあれば、示すことができないものもあるが、本発明は、この発明から逸脱することなく、これらの構成のいずれにも適用することができることが理解されるべきである。
【００２４】
次に、順方向状態メトリック及び逆方向状態メトリックは、サブブロックの尤度比（たとえば、対数尤度比）を計算するのに使用される。一実施態様では、順方向状態メトリックの現在のセット及び計算された対数尤度比は、メモリ２０８に記憶される。対数尤度比は逆方向状態メトリックと共に計算されるため、逆方向状態メトリックを記憶する必要はない。
【００２５】
図３は、順方向復号器にスライディングウィンドウアーキテクチャ及び並列復号を有する一例の復号器３００を示すブロック図である。復号器３００は、ＭＡＰアルゴリズムを実施する復号器として動作することができる。復号器３００は、通信チャネルからバイナリ情報を受信するフレームバッファ３０２を含む。受信されたバイナリ情報は、順方向復号器３０４へデータブロックとして送られる。このデータブロック（たとえば、ウィンドウ）は、より小さなデータブロック（たとえば、サブブロック又はスライディングウィンドウ）に再分割される。これらのより小さなデータブロックは、次に、順方向復号器３０４によって並列に処理される。すなわち、順方向復号器３０４は、サブブロックのバイナリトレリスの順方向再帰を行う。トレリスを通る各パスは、経時的状態（state in time）の一意のバイナリシーケンスを表す。ここで、各経時的状態には、確率が割り当てられる。上記確率は、経時的な特定のバイナリ状態が１であるのか、又は０であるのかの尤度を指定する。これらの確率は順方向状態メトリックとして記憶される。次に、逆方向復号器３０６が、逆方向でトレリスをトラバースし、逆方向状態メトリックとして確率の別のセットを生成する。次に、尤度比計算機３０８が、順方向状態メトリック及び逆方向状態メトリックに基づいて、対数尤度比又は事後確率（ＡＰＰ）を計算する。
【００２６】
順方向状態メトリック計算は、以前の時間ステップからの順方向状態メトリックに基づく再帰関数である。時間ステップｔにおけるすべての可能な状態について同程度の確率を有する未知の状態から開始して、ｋ個の時間ステップを通しての順方向状態メトリック計算は、時間ステップｔ＋ｋにおいて、順方向状態メトリックの良好な近似値を生成する。ここで、ｋは、符号の制限長に依存する。次に、時間ｔ＋ｋにおける近似値から開始して、次の順方向状態メトリックを計算することができる。トレリスのいずれの点から開始しても、順方向状態メトリックの良好な近似値を確立することが可能であるため、スライディングウィンドウアーキテクチャは、順方向状態メトリック計算に適用することができ、順方向状態メトリック計算用のすべてのスライディングウィンドウを並列に処理することができる。
【００２７】
図４は、符号化された情報ブロック４０２、４０４、及び４０６が、順方向復号器のスライディングウィンドウアーキテクチャで、より小さなサブブロック４０８、４１０、及び４１２にどのように分割されるのかの一例を示している。順方向復号器のスライディングウィンドウの長さＬは、復号時間制約に基づいて選択される。復号時間制約は、アプリケーションデータレートに基づいている。アプリケーションデータレートが高いほど、復号要件は速くなり、これは、スライディングウィンドウがより小さな長さＬを有することを意味する。
【００２８】
ブロック４０４は、そのトレリスにＮ個の時間ステップを有し、Ｎ／Ｌ個のサブブロック４０８、４１０、及び４１２に分割される。Ｎ／Ｌ個のサブブロック４０８、４１０、及び４１２の順方向状態メトリックは、並列に計算される。最初のサブブロック４０８は、長さＬを有する。このサブブロックは、（ブロックＢ４０４）の最初の時間ステップから開始し、且つ、オールゼロ状態（既知の状態）から開始する。他のサブブロック４１０及び４１２は長さＬ＋ｋを有し、各サブブロックは、直前のサブブロックとはトレリスのｋ個の時間ステップだけオーバーラップしている。たとえば、サブブロック−１  ４０８に続くサブブロック−２  ４１０は、サブブロック−１  ４０８からの最後のｋ個の時間ステップを含む。ｎ番目のサブブロック（ここで、ｎ>１）は、同等に確からしい状態を有する（（ｎ−１）Ｌ＋１−ｋ）番目の時間ステップから開始する。ｎ番目のサブブロックをｋ個の時間ステップだけ「早く」開始することによって、そのサブブロックの時間ステップｋ＋ｔにおける順方向状態メトリックの良好な近似を取得することができる（ここで、ｔは０以上の整数である）。最初のウィンドウ以外のすべてのスライディングウィンドウにおける最初のｋ個の時間ステップの順方向状態メトリックは、その後、廃棄される。
【００２９】
逆方向状態メトリック計算を行うために、サブブロックは、より小さなサブブロック、すなわち、セグメント４１４、４１６、及び４１８にさらに再分割することができる。次に、これらのセグメント４１４、４１６、及び４１８に対して、逆方向状態メトリック計算が行われる。トレリスの対数尤度比の全体的な計算を促進するために、セグメントの逆方向状態メトリック計算は、対応するサブブロック全体の順方向状態メトリック計算が完了する前であっても開始することができる。したがって、順方向状態メトリック計算が、あるセグメントに対応するサブブロックの部分について完了すると、そのセグメントに対して逆方向状態メトリック計算を開始することができる。他の実施態様では、逆方向状態メトリック計算は、本発明から逸脱することなく、順方向状態メトリック計算の前に又は順方向状態メトリック計算とほぼ同時に行うことができることに留意されたい。
【００３０】
図５は、複数の並列復号器を有する一例の復号器構造のブロック図を示している。フレームバッファ５０２は、通信チャネルからバイナリデータ又はバイナリシンボルを受信する。ブロック分割器５０４は、データブロックを複数のより小さなデータサブブロックに分割する。一実施態様では、スライディングウィンドウアーキテクチャが、データブロックの複数の順方向状態メトリック（ＦＳＭ）サブブロックへの分割に使用される。各ＦＳＭサブブロックは、前のＦＳＭサブブロックとｋ個の時間ステップだけオーバーラップしている。次に、複数のＦＳＭサブブロックは、複数の並列復号器（たとえば、プロセッサ、ＡＳＩＣ等）５１０、５１２、及び５１４を有する順方向復号器５０６へ送られる。順方向状態メトリックを並列に生成することによって、順方向復号器５０６はより少ない時間でメトリックを生成する。
【００３１】
順方向復号器５０６からのＦＳＭサブブロックは、より小さなサブブロック、すなわちセグメント（たとえば、図４のセグメント４１４、４１６、及び４１８）にさらに再分割することができる。逆方向状態メトリック計算は、これらのより小さなセグメントに対して行われる。逆方向復号器５０８は、複数の逆方向状態メトリック（ＲＳＭ）セグメント復号器５１６、５１８、及び５２０を含む。これらの複数の逆方向状態メトリックセグメント復号器５１６、５１８、及び５２０は、対応するＦＳＭサブブロック復号器５１０、５１２、及び５１４からのサブブロックのセグメントの逆方向状態メトリックを生成する。しかしながら、逆方向状態メトリックの計算は、順方向状態メトリックから独立していることに留意することが重要である。順方向復号器は、サブブロック又はセグメントの開始から終了へメトリックを計算する一方、逆方向復号器は、サブブロックの終了から開始へメトリックを計算する。順方向復号器５０６及び逆方向復号器５０８は、それらのそれぞれの計算を互いに独立して行う。双方の復号器は、受信されたデータ及び共通のトレリス構造を使用する。尤度比の全体的な計算を促進するために、ＲＳＭセグメント復号器５１６、５１８、及び／又は５２０による逆方向状態メトリック計算は、ＦＳＭサブブロック復号器５１０、５１２、及び／又は５１４による対応するサブブロックの順方向状態メトリック計算が完了する前であっても開始することができる。したがって、順方向状態メトリック計算が、あるセグメントに対応するサブブロックの部分について完了すると、そのセグメントに対して、逆方向状態メトリック計算を開始することができる。
【００３２】
ストレージデバイス５２２を順方向復号器５０６に結合して、順方向状態メトリックを記憶すると共に上記メトリックを尤度比計算機５２４へ渡すことができる。尤度比計算機５２４は、記憶された順方向状態メトリック、及び逆方向復号器５０８から受信した逆方向状態メトリックに基づいて尤度比を計算する。一実施態様では、順方向状態メトリックの現在のセット及び計算された尤度比は、メモリ２０８（図２）に記憶される。尤度比は逆方向状態メトリックと共に計算されるため、逆方向状態メトリックを記憶する必要はない。
【００３３】
いくつかの実施態様では、順方向復号器５０６及び逆方向復号器５０８は、同時に（又はほぼ同時に）サブブロックを復号することができる。すなわち、逆方向復号器５０８は、符号のセグメントが順方向復号器５０６によって復号されるまで待つことはしない。このような実施態様では、順方向メトリック及び逆方向メトリックの双方を、尤度比を計算するためにメモリに記憶することができる。たとえば、サブブロックの最初の半分の順方向メトリックを、サブブロックの他の半分の逆方向メトリックと共に記憶することができる。次に、サブブロックの順方向状態メトリック及び逆方向状態メトリックが完了すると尤度比を計算することができる。
【００３４】
図６は、順方向復号器及び逆方向復号器によるデータブロックの分割及び処理を示す一例の表である。概要として、データブロックがＦＳＭサブブロックに分割され、ＦＳＭサブブロックは順方向状態メトリック計算のために並列に処理され、各サブブロックは、逆方向状態メトリック計算のために、より小さなＲＳＭサブブロック又はセグメントにさらに分割することができる。この例では、ＦＳＭサブブロックは長さ６×Ｗを有し、ＲＳＭセグメントは長さＷを有する。順方向状態メトリック計算機（ＦＳＭＣ）は、時間Ｔ０において開始される。最初のＷ個の順方向状態メトリックが計算されると、ＦＳＭＣは、時間Ｔ１において、セグメント２×Ｗ（Ｗから２Ｗ−１へ）の順方向状態メトリックを計算する。ほぼ時間Ｔ１において、逆方向状態メトリック計算機（ＲＳＭＣ）は、最初のセグメントＷから逆方向メトリックを計算する（逆の順序でＷ−１から０へ計算する）。次の時間期間Ｔ２において、ＦＳＭＣは次のセグメント３×Ｗ（２Ｗから３Ｗ−１へ）に移り、ＲＳＭＣはセグメント２×Ｗに移る（逆の順序で２Ｗ−１からＷへ計算する）。このプロセスは、順方向状態メトリック及び逆方向状態メトリックが１つのＦＳＭサブブロックについて完了するまで続く。
【００３５】
ＲＳＭＣが各セグメントの逆方向状態メトリックを計算するにつれ、そのセグメントの対数尤度比（ＬＬＲ）（又は他の尤度比）も計算されて、メモリに記憶される。いくつかの実施形態によれば、順方向状態メトリックを記憶するのに利用されるメモリストレージの量は、記憶される順方向状態メトリックの個数がより少なくなることによって削減されることに留意されたい。たとえば、現在のセグメント（たとえば、２×Ｗ）及び以前のセグメント（たとえば、Ｗ）の順方向状態メトリック（たとえば、Ａ0,2W-1）が記憶される。この、以前のセグメント（たとえば、Ｗ）の順方向状態メトリック（Ａ0,W-1）は、時刻Ｔ１で開始するＬＬＲを計算するのに使用される。このプロセスは、ＬＬＲがサブブロック全体について計算されるまで続く。或るセグメントのＬＬＲが計算されると、その直前のセグメントの順方向状態メトリックを廃棄することができる。サブブロックの順方向状態メトリックが完了する前に、セグメントの逆方向状態メトリックを処理することによって、いずれの時点においても、記憶される順方向状態メトリックの個数（たとえば、２つのセグメントのメトリック）はより少なくなることに留意されたい。
【００３６】
図７は、順方向復号パス及び逆方向復号パスにおいてスライディングウィンドウで再帰的復号を実施する一例の方法を示すフロー図である。さまざまな実施態様において、本方法を、ＭＡＰ復号器又は対数ＭＡＰ復号器を使用する異なる復号アルゴリズムに適用することができることに留意されたい。これらの複合アルゴリズムは、２つ以上の逐次復号ステージ又は並列復号ステージ（たとえば、内部復号器及び外部復号器等）を有するものを含む。データブロック（たとえば、ビットシーケンス、シンボルシーケンス等）が、通信チャネルから受信される（７０２）。このデータブロックは、より小さなサブブロックに分割される（７０６）。いくつかの実施態様では、最初のサブブロックの後、後続の各サブブロックは、前のサブブロックとトレリスのｋ個の時間ステップだけオーバーラップしている。順方向復号は、サブブロックのうちの２つ以上に対して並列に行われ（７０８）、各サブブロックの順方向状態メトリックが取得される。各サブブロックの順方向状態メトリックは、結合されると、データブロックのトレリスの順方向状態メトリックを構成する。さまざまな実施態様では、順方向復号は、データブロックのすべてのサブブロックで行われる。オプションとして、順方向状態メトリック（たとえば、トレリスの各時間ステップの確率）を各サブブロックについて記憶することができる（７１０）。
【００３７】
いくつかの実施態様では、サブブロックは、後続の復号ステージによる処理のために、より小さなセグメントにさらに分割することができる（７１２）。逆方向復号（たとえば、トレリスに沿った後ろ向きパス）が、２つ以上のセグメントに対して並列に行われ（７１４）、各セグメントの逆方向状態メトリックが取得される。いくつかの実施態様は、逆方向復号７１２及び７１４を順方向復号と並列に行うことによって復号時間を削減することができ且つ／又はストレージ空間を節約することができる。特に、サブブロックのセグメントの順方向状態メトリックが取得されるときに、サブブロックのそれらのセグメントの逆方向復号を開始することができる。したがって、逆方向復号の開始前に、サブブロック全体の順方向状態メトリックが完了されるまで待つ必要はない。他の実施態様では、順方向復号及び逆方向復号を逐次的に行うことができる。
【００３８】
順方向状態メトリック及び逆方向状態メトリックに基づいて尤度比が計算される（７１６）。尤度比は、オリジナルの送信データの推定値として出力することができる（７１８）。
【００３９】
さまざまな実施態様では、サブブロックについて又はサブブロックのセグメントについて、順方向状態メトリック及び逆方向状態メトリックをほぼ同時に計算することも逐次的に計算することもできる（たとえば、順方向状態メトリックの後に逆方向状態メトリックが続くか、又は、その逆）。
【００４０】
例の中には、これらのシーケンスのうちの１つを示すことができるものもあれば、示すことができないものもあるが、本発明は、この発明から逸脱することなく、これらの構成のいずれにも適用することができることが理解されるべきである。
【００４１】
図８は、受信されたデータブロックを２ステージ復号器で分割する一例の方法を示すフロー図である。サブブロック（たとえば、スライディングウィンドウ）の長さＬが、復号時間制約に基づいて選択される（８０２）。復号時間制約は、アプリケーションデータレートに基づいている。アプリケーションデータレートが高いほど、復号要件は速くなり、これは、スライディングウィンドウがより小さな長さＬを有することを意味する。長さＬは、さまざまな実施態様においてビット、シンボル、又はトレリス時間ステップで測定することができる。さまざまな実施態様では、長さＬ及び／又は時間制約は、オペレーション中に動的に求めるか、ユーザによって構成可能とするか、又は通信デバイス／システムのハードウェア及び／又はソフトウェアの設計中に構成可能とすることができる。
【００４２】
データブロックは、長さＬのより小さな２つ以上のサブブロックに分割される（８０４）。ブロックは、そのトレリスにおけるＮ個の時間ステップを有することができ、Ｎ／Ｌ個のサブブロックに分割される。次に、それが最初のサブブロックであるかどうかが判断される（８０６）。通常、最初のサブブロックは、ゼロ状態（既知の状態）から開始する。最初のサブブロックでない場合には、サブブロックからの最後のｋ個の時間ステップが、次のサブブロックに追加される（８０８）。したがって、最初のサブブロックを除いて、すべての後続のサブブロックは長さＬ＋ｋを有し、各サブブロックは前のサブブロックとトレリスのｋ個の時間ステップだけオーバーラップしている。次に、２つ以上のサブブロック（たとえば、２つ若しくはすべてのサブブロック又はスライディングウィンドウ）の順方向状態メトリックが、並列に求められる（計算される）（８１０）。次に、最初のサブブロックより後の各サブブロックにおける最初のｋ個の時間ステップの順方向状態メトリックが廃棄される（８１２）。次に、オプションであるステップにおいて、サブブロックを２つ以上のより小さなセグメントに分割することができる（８１４）。次に、２つ以上のセグメントの逆方向状態メトリックが求められる（計算される）（８１６）。順方向状態メトリック及び逆方向状態メトリックに基づいて、尤度比が計算される（８１８）。
【００４３】
いくつかの実施態様によれば、セグメントの逆方向状態メトリックは、対応するサブブロックの他の部分の順方向状態メトリックが求められている間に計算される。たとえば、順方向メトリック及び逆方向メトリックは、図６に示すものと同様のシーケンスで計算することができる。
【００４４】
このアルゴリズムのメモリ使用量は、逆方向状態メトリック計算のみについてスライディングウィンドウアーキテクチャを適用するメモリ使用量のＮ／Ｌ倍であることに留意されたい。加えて、復号時間は、データブロックのサブブロックへの分割及び順方向復号パス上での並列処理によってＮ／Ｌ倍に削減される。
【００４５】
したがって、ＭＡＰ復号器は、又は構成要素となるＭＡＰ復号器を有するターボ復号器は、双方向スライディングウィンドウで構成することができる。スライディングウィンドウアーキテクチャは、Ｎ個の時間ステップを有するトレリスを有する符号化されたデータブロックの順方向状態メトリック（ＦＳＭ）計算に適用することができる。データブロックは、より小さなサブブロックに分割され、これらのサブブロックのうちの２つ以上の順方向再帰が並列に行われて、ＦＳＭが取得される。各サブブロックは、前のサブブロックとｋ個の時間ステップだけオーバーラップしている。ここで、ｋは０よりも大きな整数値である。これによって、そのサブブロックの時間ステップｋ＋ｔにおけるＦＳＭの良好な近似値が提供される。最初のサブブロック以外の各サブブロックの最初のｋ個の時間ステップに関連付けられているＦＳＭは廃棄される。各サブブロックの逆方向再帰も行われて、そのサブブロックの逆方向状態メトリック（ＲＳＭ）が取得される。次に、ＦＳＭ及びＲＳＭに基づいて尤度比が計算される。
【００４６】
本明細書で説明した装置、方法、及びアルゴリズムは、ターボ符号又は畳み込み符号を使用する高データレートシステムに特によく適している。また、これは、復号器の速度があまりにも遅いために所望のデータレートを達成することができないシステムにとっても良好な解決策である。並列の復号器を追加することによって、データレートが効果的に増加される。
【００４７】
さまざまな実施態様によれば、図１、図２、図３、図４、図５、及び／又は図６の装置は、図７及び／又は図８に開示した方法のうちの１つ又は複数と共に実施することができる。
【００４８】
図１、図２、図３、図４、図５、図６、図７、及び／又は図８に示す構成要素、ステップ、及び／若しくは機能のうちの１つ又は複数は、本発明から逸脱することなく、並べ替えることができ、且つ／又は、単一の構成要素、ステップ、若しくは機能に結合することができ、又は、いくつかの構成要素、ステップ、若しくは機能で実施することができる。追加の要素、構成要素、ステップ、及び／又は機能を、本発明から逸脱することなく追加することもできる。図１、図２、図３、図４、図５、及び／又は図６に示す装置、デバイス、及び／又は構成要素は、本明細書で開示した方法、特徴、又はステップのうちの１つ又は複数を行うように構成することができる。
【００４９】
上記実施形態は、例にすぎず、本発明を限定するものとして解釈されるべきでないことに留意すべきである。たとえば、復号器は、符号化されたデータブロックを複数のサブブロックに分割する手段であって、符号化されたデータブロックが、Ｎ個の時間ステップを有するトレリスを有し、ここで、Ｎは０よりも大きな整数である、分割する手段と、サブブロックのうちの２つ以上の順方向状態メトリックを並列に再帰的に取得する手段と、サブブロックのうちの２つ以上の逆方向状態メトリックを並列に再帰的に取得する手段とを備えることができる。ここで、分割する手段は、図９の装置９００に示すような分割器モジュール９１０で構成することができる。装置９００に示すように、順方向状態メトリックを再帰的に取得する手段は、順方向状態メトリックモジュール９２０で構成することができ、逆方向状態メトリックを再帰的に取得する手段は、逆方向状態メトリックモジュール９３０で構成することができる。
【００５０】
或いは、装置９００の１つ又は複数の要素は、それらの１つ又は複数の要素の機能を制御及び／又は実行するように構成されるプロセッサによって実施することができる。同様に、装置９００の１つ又は複数の要素は、１つ又は複数の要素の機能を実行するように構成される命令を含む機械可読媒体によって実施することができる。
【００５１】
したがって、実施形態の説明は、例示であるように意図されており、特許請求の範囲の範囲を限定するように意図されていない。したがって、本教示は他のタイプの装置に容易に適用することができ、多くの代替形態、変更形態、及び変形形態が当業者には明らかであろう。
【図面の簡単な説明】
【００５２】
【図１】本発明の１つ又は複数の特徴を実施することができる一例の通信システムのブロック図である。
【図２】データ復号を行うように構成される一例の受信デバイスを示すブロック図である。
【図３】本発明の１つの特徴による、順方向復号器にスライディングウィンドウアーキテクチャ及び並列復号を有する一例の復号器を示すブロック図である。
【図４】情報のブロックが、順方向復号器のスライディングウィンドウアーキテクチャで、より小さなサブブロックにどのように分割されるのかの一例を示す図である。
【図５】複数の並列復号器を有する一例の復号器構造のブロック図である。
【図６】順方向復号器及び逆方向復号器によるデータブロックの分割及び処理を示す一例の表である。
【図７】順方向復号パス及び逆方向復号パスにおいてスライディングウィンドウで再帰的復号を実施する一例の方法を示すフロー図である。
【図８】受信されたデータブロックを２ステージ復号器で復号する一例の方法を示すフロー図である。
【図９】復号する別の一例の装置である。
【図１】
2009525009.tif 000003
【図２】
2009525009.tif 000004
【図３】
2009525009.tif 000005
【図４】
2009525009.tif 000006
【図５】
2009525009.tif 000007
【図６】
2009525009.tif 000008
【図７】
2009525009.tif 000009
【図８】
2009525009.tif 000010
【図９】
2009525009.tif 000011
【国際調査報告】
2009525009.tif 000012
2009525009.tif 000013
2009525009.tif 000014
2009525009.tif 000015