(57)【要約】トレリス・デコーダ・ネットワークにより作られる復号生き残りシーケンスを処理する際に使用されるメモリを管理する場合に使用する改善された全パス・トレースバック／フォワードトレース(APTFT)システムである。メモリサイズはT*Nに減少し、Tは所定の生き残りメモリの深さであり、Nはトレリスの状態数である。このシステムの待ち時間の値はTと等しい。メモリの要件と待ち時間の値は、先行技術のAPTFTシステムで作られた同様のパラメータの値において33%の減少を示す。既存のフォワードトレース／パス選択ユニット(17)は、復号システムを簡単にするために、フォワードトレース処理の本来の性質を利用するように変更される。一般化したAPTFTシステムは、特定の復号システムの要件を満たすために必要なメモリサイズと待ち時間の値の選択におけるより大きい柔軟性を可能にする。
2006511977.tif 000002
【特許請求の範囲】
【請求項１】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、トレリス復号データを提供する装置であって、
前記符号化データパケットに応じて、トレリスの状態変化に関連する決定データを生成する手段と、
トレリスの状態変化により決定されるように、前記決定データに応じて先行のトレリス状態のシーケンスを特定するトレースバック・ネットワークであって、前記先行のトレリス状態がデータパケットのシーケンスについて特定されるトレースバック・ネットワークと、
前記先行のトレリス状態から望ましいトレリス状態パスを選択する手段と、
それぞれの新しいトレリスのブランチで、望ましいトレリス状態パスを実質的に継続して更新する手段と、
前記特定された先行のトレリス状態のシーケンスに応じて、前記トレリス復号データを提供する手段と
を有する装置。
【請求項２】
請求項１に記載のシステムであって、
前記トレースバック・ネットワークが、
トレリスを通じて全パス・トレースバックを実行する手段と、
トレリスを通じて全パス・フォワードトレースを実行する手段と
を更に有するシステム。
【請求項３】
請求項２に記載のシステムであって、
前記決定データで先行のトレリス状態を特定することにより、フォワードトレースポインタでそれぞれの新しいトレリスのブランチの望ましいトレリス状態を継続的に特定する手段を更に有するシステム。
【請求項４】
請求項３に記載のシステムであって、
前記望ましいトレリス状態パスが、全てのトレリス状態の中で最小基準パスであるシステム。
【請求項５】
請求項３に記載のシステムであって、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタであって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチで更新される第１のポインタと、
トレリス状態パス毎の第２のポインタであって、第２のポインタの値を有し、前記第２の値がエポックの境界で更新される第２のポインタと
を更に有し、
各エポックがT/2であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項６】
請求項５に記載のシステムであって、
前記フォワードトレースポインタが、前記第１のポインタの値と前記第２のポインタの値の双方に継続的に応じて、それによってエポックの間に各トレリスのブランチで実質的に継続して更新されるシステム。
【請求項７】
請求項６に記載のシステムであって、
前記第２のポインタが、前記第１のポインタの値で各エポックの終了時に一度更新され、前記第１のポインタがその後にリセットされるシステム。
【請求項８】
請求項７に記載のシステムであって、
前記システムにより出力される各復号ビットが、Tの関連するメモリの深さを有するシステム。
【請求項９】
請求項８に記載のシステムであって、
前記フォワードトレースポインタが、それぞれの新しいトレリスのブランチで２つの以前のエポックから望ましいトレリス状態パスを継続的に特定するシステム。
【請求項１０】
請求項２に記載のシステムであって、
前記トレースバック・ネットワークが、
同時にエポックの間にデータ到着順に入力符号化データをバッファメモリユニットに書き込む手段と、
以後のエポックの間に前記バッファメモリユニットから前記データを読み取り、前記全パス・トレースバック・ユニットに前記データを送出する手段と、
全パス・トレースバック・ユニットが前記バッファメモリユニットから読み取られたデータでトレリスを通じてトレースバックすると、全パス・トレースバック・ユニットから復号シーケンスメモリ・ユニットに復号された出力を送出する手段と、
同時に１つのエポックで、到着の逆順に前記復号シーケンスメモリ・ユニットから復号データを読み取る手段と、
N個の復号シーケンスのうちの１つを選択するために、前記復号シーケンスメモリ・ユニットから復号データ出力を多重化する手段であって、Nがトレリスの状態の数である手段と、
フォワードトレースポインタの値に従って、マルチプレクサユニットを介して復号シーケンスメモリから復号データ出力のサンプルを選択する手段と
を更に有するシステム。
【請求項１１】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、
前記データに応じてトレリス状態変化に関連する決定データを生成するステップと、
前記決定データに応じてトレリスの状態変化に従って先行のトレリス状態のシーケンスを特定するステップと、
各トレリスのブランチの特徴に応じて、望ましいトレリス状態パスを選択するステップと、
先行のトレリス状態の前記特定されたシーケンスに応じて、前記トレリス復号データを提供するステップと
を有する装置。
【請求項１２】
請求項１１に記載のシステムであって、
エポックの境界の間で望ましいトレリス状態パスの選択を更新するステップを更に有し、
各エポックがT/2であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項１３】
請求項１２に記載のシステムであって、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで望ましいトレリス状態パスを更新及び選択するステップを更に有するシステム。
【請求項１４】
請求項１３に記載のシステムであって、
複数のトレリス復号データシーケンスを特定するステップと、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで更新された複合ポインタで前記複数のトレリス復号データシーケンスのうちの１つを特定するステップと
を更に有するシステム。
【請求項１５】
請求項１４に記載のシステムであって、
第１のポインタを用いて複数のトレリス復号データシーケンスを特定するステップと、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで前記第１のポインタに関連する値を更新するステップと、
第２のポインタを用いて複数のトレリス復号データシーケンスを特定するステップと、
前記第１又は前記第２のポインタに関連する値が更新されると常に、前記複合ポインタに関連する値を更新するステップと
を更に有するシステム。
【請求項１６】
請求項１５に記載のシステムであって、
各エポックの境界で、前記第２のポインタに関連する値を前記第１のポインタに関連する値と交換し、その後に前記第１のポインタをリセットするステップを更に有するシステム。
【請求項１７】
複数のトレリスのブランチとトレリス状態を有し、符号化シンボルを復号するトレリス・デコーダであって、
トレリス状態変化に関連する決定データを生成する手段と、
トレリスの状態変化によって決定されるように、遅延した決定データで複数の先行のトレリス状態シーケンスを特定することにより、複数のトレリス復号データシーケンスを提供する手段であって、前記状態変化のトレリスがN個の状態を有する手段と、
前記決定データで先行のトレリス状態を特定することにより更新されたポインタで、前記複数のトレリス復号データシーケンスのうちの１つを特定する手段と
を有し、前記ポインタが、各トレリスのブランチに関連するデータに応じて、エポックを通じて各トレリスのブランチで継続的に更新され、エポックがトレースバック間隔Tのサブ間隔であるトレリス・デコーダ。
【請求項１８】
請求項３に記載のシステムであって、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタP1であって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチの間に更新される第１のポインタと、
トレリス状態パス毎の更なるq-1個のポインタPj(j=2,3,...,q)であって、ポインタの値を有し、各ポインタの値がエポックの境界で更新されるポインタと
を更に有し、
各エポックがT/qの所要時間でのトレースバック間隔Tのサブ間隔であり、qが2以上の整数値であり、qがT以下であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項１９】
請求項１８に記載のシステムであって、
前記フォワードトレースポインタが、すべてのq個のポインタの値に継続的に応じて、それによってエポックの間に各トレリスのブランチで実質的に継続して更新されるシステム。
【請求項２０】
請求項１９に記載のシステムであって、
各ポインタPj(j=3,...,q)が、ポインタPj-1の値で各エポックの終了時に一度更新され、ポインタP2が、ポインタP1の値で各エポックの終了時に一度更新され、前記第１のポインタP1がその後にリセットされるシステム。
【請求項２１】
請求項２０に記載のシステムであって、
前記システムにより出力されるデータのシーケンス内にある各復号ビットが、Tの関連するメモリの深さを有するシステム。
【請求項２２】
請求項２１に記載のシステムであって、
前記フォワードトレースポインタが、それぞれの新しいトレリスのブランチでq個の前のエポックから望ましいトレリス状態パスを継続的に特定するシステム。
【請求項２３】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、トレリス復号データを提供する装置であって、
前記符号化データパケットに応じて、トレリスの状態変化に関連する決定データを生成する手段と、
トレリスの状態変化により決定されるように、前記決定データに応じて先行のトレリス状態のシーケンスを特定するトレースバック・ネットワークと、
前記先行のトレリス状態から望ましいトレリス状態パスを選択する手段と、
前記望ましいトレリス状態パスを更新する手段と、
前記特定された先行のトレリス状態のシーケンスに応じて、前記トレリス復号データを提供する手段と
を有し、
前記トレースバック・ネットワークが、
トレリスを通じて全パス・トレースバックを実行する手段と、
トレリスを通じて全パス・フォワードトレースを実行する手段とを更に有し、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタP1であって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチの間に更新される第１のポインタと、
トレリス状態パス毎の更なるq-1個のポインタPj(j=2,3,...,q)であって、ポインタの値を有し、各ポインタの値がエポックの境界で更新されるポインタとを更に有し、
各エポックがT/qの所要時間でのトレースバック間隔Tのサブ間隔であり、qが2以上の整数値であり、qがT以下であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項２４】
請求項２３に記載のシステムであって、
複合フォワードトレースポインタが、すべてのq個のポインタの値に応じ、前記複合フォワードトレースポインタが、各エポックの境界で更新されるシステム。
【請求項２５】
請求項２４に記載のシステムであって、
各ポインタPj(j=3,...,q)が、ポインタPj-1の値で各エポックの終了時に一度更新され、ポインタP2が、ポインタP1の値で各エポックの終了時に一度更新され、前記第１のポインタP1がその後にリセットされるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、2002年4月17日に出願された仮特許出願第60/373,246号の優先権を主張する。
【０００２】
本発明は、概してデジタル信号処理に関するものであり、特に選択されたシーケンスを格納するように設計された信号デコーダに関するものであり、その選択されたシーケンスから復号シーケンスが最終的に取り出される。
【背景技術】
【０００３】
高精細度テレビ(HDTV)のような通信システムは、特定の雑音源からの干渉に対して保護するために、トレリス(trellis)符号化を使用する。HDTVのトレリス符号の要件は、Advanced  Television  Systems  Committee(ATSC)により作成された1995年4月12日のDigital  Television  Standards  for  HDTV  Transmissionのセクション4.2.4-2.4.6(Annex  D)と、10.2.3.9と、19.2.3.10とその他のセクションに示されている。トレリス・デコーダは、信号処理アルゴリズムに従って最も正確と思われるもの(すなわち生き残りシーケンス(survivor  sequence))として受領シンボル・シーケンスを選択する。最も普及したトレリス復号アルゴリズムは、I.E.E.E  Transactions  on  Communications  Technologyの出版のvol.COM-19,  1971,  751-772ページのA.J.ViterbiによるConvolutional  Codes  and  Their  Performance  in  Communication  Systemsという題名の文献に記載されたビダビ(Viterbi)・アルゴリズムである。Viterbiアルゴリズムには、復号シーケンスが最終的に取り出される生き残りシーケンス(survivor  sequence)を格納するための２つの周知の技術が存在する。一方の技術はレジスタ交換として知られており、他方の技術はトレースバックとして知られている。トレースバック処理の背景の理論は、1993年3月のI.E.E.E  Transactions  on  Communications,  vol.41,  no.3の出版のG.Feygin他によるArchitectural  Tradeoffs  for  Survivor  Sequence  Memory  Management  in  Viterbi  Decodersに記載されている。比較的簡単ではあるが、レジスタ交換方法は、VLSI実装において大量の消費電力と大きい領域を必要とするため、小さい拘束長を有する符号に制限される。拘束長はK=v+kとして定められ、vはトレリス・エンコーダのメモリ要素の数であり、符号レートはR=k/nである。従って、トレースバックは、中程度から大きい拘束長のトレリス・デコーダの設計で好ましい方法である。
【０００４】
Hu他による1998年11月24日に公布されたCODE  SEQUENCE  DETECTION  IN  A  TRELLIS  DECODERという題名の米国特許第5,841,478号は、生き残りシーケンスの選択のために、全パス・トレースフォワード・ネットワークに結合された全パス・トレースバック・ネットワークを開示する。記載されたトレースバック処理は、所定の数の先行トレリス状態を特定するために、所定の深さT(トレースバックの深さ又は生き残りメモリ(survivor  memory)の深さ)まで実行される。実際に、トレースバック間隔Tは、マージ状態又は収束状態の識別を可能にするために十分な期間を提供するように選択される。マージ状態は、真に符号化されるデータとして最も高い可能性を有するデータを特定する。マージ状態は、いくつかの候補のシーケンスの中から選択され、最終出力データとして選択されたトレリス復号されたデータシーケンスである。このトレースバック処理は、エポック(epoch)として知られるT/2のトレースバック間隔により２段階で実行される。そのようなエポック(epoch)の選択又はトレースバック・サブ間隔は任意的であり、システム設計者により選択可能である。
【０００５】
Hu他の機構で必要な全メモリサイズは、3/2*T*Nであり、Tは所定の生き残りメモリの深さであり、Nがトレリス状態の数である。十分なデコーダ性能を達成するために、生き残りメモリの深さ又はトレースバックの深さ(又はトレースバック間隔)Tは、一般的に符号の拘束長の４から６倍である。Nの値は2vに等しく、vはエンコーダのメモリ要素の数である。Hu他のアルゴリズムに関連する待ち時間(又はデータ符号化遅延)は3/2*Tである。Hu他の装置は、12個のインターリーブ・デコーダを必要とするATSC  HDTVトレリス・デコーダに実装されているが、開示された技術は如何なるトレリス・デコーダにも適用され得る。残念ながら、Hu他のシステムは最も効率のよいトレースバック・アルゴリズムではなく、メモリサイズとデータ復号遅延(又は待ち時間)に関してレジスタ交換技術ほど効率的ではない。しかし、如何なるトレースバック・アルゴリズムに言えることであるが、消費電力と制御の複雑性ではレジスタ交換アルゴリズムより効率的である。
【０００６】
Hu他の全パス・トレースバック／フォワードトレース(APTFT:all-path  traceback/forward  trace)システムは、図１のブロックにより示され得る。システムへのデータ入力16は、トレリス状態毎及びトレリスのブランチ(trellis  branch)毎のトレリス・デコーダのAdd-Compare-Select(ACS)ユニットの出力(すなわちトレリスの以前の状態へのポインタ)で構成される。制御入力は、クロック信号、イネーブル信号、リセット信号、何らかの同期信号、及びトレリスのブランチ毎の最小状態で構成される。トレリスのブランチ毎の最小状態はまた、各トレリスのブランチで最小パス距離(値)を有する状態を特定するACS出力である。制御ユニットは、全ての制御信号と多様なメモリブロックの読取／書込アドレスを生成する。
【０００７】
バッファは、サイズ(T/2)*Nの後入れ先出し(LIFO)メモリであり、ACS出力を一時的に格納する。データは同時にN個の状態で到着順に書き込まれ、以降のエポック(epoch)の間に逆順に読み取られる。エポックは入力サンプル(トレリスのブランチ)(すなわちT/2サンプル)のバッファメモリのサイズにより特徴付けられる。エポック読取動作の後で、新しいデータ入力が同じ位置に書き込まれる。
【０００８】
全パス・トレースバック・ユニットは、格納の逆順に以前のエポックからバッファメモリを読み取り、同時にT/2サンプルの全体のエポックの間にトレリスを通じてトレースバックするように制御ユニットにより命令される。トレリスを通じてトレースバックするため、全パス・トレースバック・ユニットは、トレリスのN個の状態のそれぞれについて復号シーケンスメモリに復号された出力を送出する。従って、全パス・トレースバック・ユニットは、トレリスでN個の生き残りパスを特定するために、N個の状態ポインタを必要とする。N個の状態ポインタはブランチ毎に更新され、対応するパスの以前の状態を常に示す。全パス・トレースバック・ユニットが以前のエポックにバッファされたACSデータ16を読み取って処理するのと同時に、フォワードトレース・ユニットは、現在のエポックのACSデータ16でトレリスを通じてフォワードトレースする。
【０００９】
それぞれの新しいエポックの間の多様なユニットの活動が、図２のタイミング図に表されている。入力データはバッファメモリに通常の順方向の順序にバッファメモリに書き込まれ、逆順に全パス・トレースバック・ユニットに渡される。全パス・トレースバック・ユニットの復号された出力は、全てのトレリス状態について、復号シーケンスメモリに渡される。この復号情報は、逆順に２つのエポック分だけ遅れて復号シーケンスメモリから読み取られる。２つの逆の読取動作は相互に取り消し、最終的な復号データが正確な順方向の順序に現れることをもたらす。復号シーケンスメモリ・ユニットの２つのエポックの遅延は、必然的にT*Nのメモリサイズを必要とする。
【００１０】
各エポックの終わりに、パス選択ユニットは、ACSユニットにより送出された最小状態パスに関連するフォワードトレースポインタPの値を更新し、フリーズする。このポインタは、次の更新が生じるまで、１つのエポックの期間だけ使用される。エポックの境界で、フォワードトレースポインタは最小状態のパスを示し、２つのエポックだけ早いこのパスに関連する状態を提供する。しかし、エポックの終了が近づくと、フォワード状態のポインタは、以前のエポックの境界で最小状態のパスを示し、３つのエポックだけ早いこのパスに関連する状態を提供する。Hu他の装置は、状態パス毎に２つの内部ポインタ(P1とP2)を実際に有し、そのポインタは１つのエポックだけ相互に一時的にオフセットされる。この２つのポインタは、最終的にトレリス・復号ビット列を特定する役割を果たす。状態パスのポインタP1は、フォワードトレース情報でブランチ毎に更新され、ポインタ2は、エポック毎に１度だけ更新される。ポインタP1は現在のエポックのポインタであり、ポインタP2は直前のエポックのポインタである。
【００１１】
N個の状態はN個の生き残り状態のパスを有するため、フォワードトレース・ユニットに2*N個の内部ポインタが存在する。各エポックの終了時に各内部ポインタは、対応する生き残りパスの同じエポックの開始状態を示す。そのポインタは主要ポインタPを作ることに寄与する。エポックの終了時に、ポインタP2はポインタP1の値を受領し、P1がリセットされ、以降のエポックの間にトレリスを通じてフォワードトレースを開始する。マルチプレクサユニットは、復号シーケンスメモリからN個の復号シーケンスのうちの１つを選択し、選択された復号ビットをその出力として転送するために、フォワードトレースポインタPを使用する。
【００１２】
例えば、エポック3の終了時に、フォワードトレースポインタPは、最小パスでエポック2の開始に関連するトレリス状態を示す。ポインタP1は終了状態からエポック3の開始状態にポインタを移動し、ポインタP2は終了状態からエポック2の開始状態にポインタを移動する。次に、ポインタP2はポインタP1の値で更新され、ポインタP1はリセットされる。エポック4の間に、ポインタPの値が更新され、エポック2の開始状態にポインタを移動し、この値は図２の適切な復号シーケンスDD1を選択するためにマルチプレクサにより使用され、その復号シーケンスDD1はN個の可能なシーケンスからの復号シーケンスメモリから読み取られる。ポインタP2はエポック4の間にフリーズ又は不変であり、エポック3の開始状態にポインタを移動する。ポインタP1はエポック4の間にフォワードトレースで継続して更新される。同様に、エポック4の終了時に、フォワードトレースポインタPはエポック3の開始状態にポインタを移動するように更新され、ポインタP2はエポック4の開始時にポインタを移動するように更新され、ポインタP1がリセットされる。全体のエポック5の間に、ポインタPは図２の正確な復号シーケンスDD2を選択し、復号シーケンスDD2は復号シーケンスメモリから読み取られる。入力信号が処理されるように利用可能である限り、この処理が無限に続く。
【００１３】
図２を参照して理解される通り、フォワードトレースは、D1に関連するデータの復号を可能にするために(その復号データはエポック4の間に生じるDD1(エポック1からの復号データ)である)、データD3(エポック3のデータ)までデータを処理する。従って、最初のエポックの復号データDD1が出力信号として生成される前に、３つのエポックが完全に処理される(フォワードトレースによるエポック2と3、及びトレースバックによるエポック1)。同様に、DD2(エポック2からの復号データ)を出力するために、２つのエポック(エポック3と4)がフォワードトレースにより処理され、１つのエポック(エポック2)がトレースバックにより処理され、同時に３つのエポックのスライドウィンドウ(sliding  window)として処理が継続する。最初の復号ビットがエポック1の開始に関連し、ポインタPがエポック3の終了に関連するため、この処理は、DD1の最初のビットが３つのエポックの対応する生き残りメモリの深さ又は3/2*Tサンプルを有することを示す。対照的に、最後の復号ビットがエポック1の終了に関連し、ポインタPがエポック3の終了に関連するため、DD1の最後のビットは２つのエポックの生き残りメモリの深さ又はTを有する。同様に、DD2の最初のビットは3/2*Tの生き残りメモリの深さに関連し、DD2の最後のビットはTの生き残りメモリの深さに関連する。このことにより、何らかの復号シーケンスブロック(DD1、DD2、DD3等)が少なくともTの生き残りメモリの深さに関連することが保証される。
【００１４】
全パス・トレースバック/フォワードトレース(APTFT:All-Path  Traceback/Forward  Trace)プロセッサによりデータが処理されて復号されると、メモリサイズは、バッファメモリのT/2*Nと復号シーケンスメモリのT*Nで構成され、合計3/2*T*Nに一致する。更に、Hu他のアルゴリズムは、合計で3*N+1の状態ポインタ(全パス・トレースバック・ユニットのNとフォワードトレース・ユニットの2*N+1、すなわちPとN個のポインタP1とN個のポインタP2)を必要とする。Hu他の装置のデータ復号遅延又は待ち時間は、バッファメモリの１つのエポックの遅延(T/2サンプル)と、復号シーケンスメモリの２つのエポックの遅延(Tサンプル)を加えたものに帰する。従って、合計の待ち時間は３つのエポックの遅延又は3/2*Tサンプルである。
【発明の開示】
【発明が解決しようとする課題】
【００１５】
Tの生き残りメモリの深さでシーケンスを復号するために、効果的なアルゴリズムは、各ビットがTの関連する生き残りメモリの深さを有するという特徴を有する。既存のトレースバックのアルゴリズムは処理サイクル毎に全データブロックを復号する必要があり、データブロックの１ビットを除く全てに不要に大きい生き残りメモリの深さが存在する結果になる。従って、メモリサイズと待ち時間の値が減少する改善されたトレリス・デコーダのメモリ管理機構の必要性が存在する。
【課題を解決するための手段】
【００１６】
本発明は、先行技術のAPTFTアルゴリズムに関してメモリと待ち時間の要件を減少させる全パス・トレースバック/フォワードトレース(APTFT)アルゴリズムを使用するトレリス・デコーダシステムである。特に、本発明はT*Nのメモリサイズ(生き残りメモリの深さ×トレリス状態の数)とTの待ち時間を必要とするトレリス・デコーダシステム(制御の要件を増加することなく、同じ生き残りメモリの深さTを維持して、双方のパラメータの3分の1の削減を表す)を開示する。この改善により、APTFTアルゴリズムが最も効率的なトレースバック技術のうちの１つになることが可能になる。更に、APTFTアルゴリズムは、小さい拘束長を有する符号についてレジスタ交換アルゴリズムと競合できるようになる。本発明はまた、メモリサイズと待ち時間の選択で大きな柔軟性を可能にするAPTFTアルゴリズムの生成を有し、特定のシステムのニーズを満足する。
【００１７】
本発明は、復号又は組織化済の出力シーケンスを最終的に生成するために生き残りシーケンスを格納及び処理する必要のある、如何なるトレリス・デコーダシステム又は同様の信号処理技術にも適用可能である。前記システムは、１つ又は複数のデコーダ、連結又は非連結デコーダ、並列処理又は分散処理を備えたデコーダ、並列又は直列の複数のデコーダ、インターリーブ又は非インターリーブ・デコーダ、及び如何なる種類の同様の信号処理機構に一般化される。
【発明を実施するための最良の形態】
【００１８】
図１を参照すると、先行技術の全パス・トレースバック/フォワードトレース(APTFT)システムの簡単なブロック図が、本発明の理解を可能にする。図１に表された機能ブロックは、フォワードトレース及びパス選択ユニット17を除いて、本発明の目的と同様に実行する。本発明は、フォワードトレースの特徴を利用して、先行システムの動作を簡単にする。前述の通り、各エポックの終了時に、フォワードトレース及びパス選択ユニットは、フォワードトレースポインタPを更新及びフリーズし、そのフォワードトレースポインタPはAdd-Compare-Select(ACS)ユニットにより送出された最小トレリスのパス状態に関連する。次にポインタPは復号シーケンスメモリから最適の復号シーケンスを選択するために、エポックの全所要時間の間に使用される。その結果、エポックの最初の復号ビットは、3/2*Tの生き残りメモリの深さに関連し、最後の復号ビットは、Tの生き残りメモリの深さに関連する。
【００１９】
本発明では、各エポックの終了時に、フォワードトレースポインタPがフリーズされず、その代わりに復号処理を通じてその値が継続して更新されることが可能になる。前述の通り、ポインタP1はエポックの間にフォワードトレースにより継続的に更新され、ポインタP2はエポックの終了時にのみ更新される。ACSユニットから受領された最小パスの値と共に、トレリス状態毎のポインタP1とP2は、ポインタPの値を作ることに寄与する。データサンプル毎にポインタPを継続的に更新することにより、ポインタPの値はポインタP1の継続的に更新される値を反映し、それ故にトレリスを通じて継続的なフォワードトレース処理を反映する。このように、生き残りメモリの深さは、トレリスを通じて伝搬する一定のサイズTのスライディングウィンドウ(sliding  window)である。
【００２０】
ポインタPの値を継続的に更新する結果として、全てのトレリス状態について全パス・トレースバック・ユニット12から復号データシーケンスを受領する復号シーケンスメモリは、２つのエポックだけではなく、１つのエポックだけ遅くそのデータをマルチプレクサ14に利用可能にする必要がある。１つのエポックの遅延は、T*N(２つのエポックの遅延の場合) ではなく、(T/2)*Nのメモリサイズを必要とし、それによって復号シーケンスメモリ13のサイズで50%の減少が可能になる。
【００２１】
前述の変更されたAPTFTプロセッサによりデータ16が処理され、復号されると、メモリサイズは、バッファメモリ15に(T/2)*Nと、復号シーケンスメモリ13に(T/2)*Nとを加えたもので構成され、T*Nの全メモリの要件に一致する。更に、バッファメモリ15に帰する１つのエポックの遅延(T/2サンプル)と、復号シーケンスメモリ13に帰する１つのエポックの遅延(T/2サンプル)が存在し、結果として２つのエポックの遅延(Tサンプル)と等しい合計待ち時間になる。本発明の変更されたAPTFTプロセッサは、全パス・トレースバック・ユニット12のN個のポインタとフォワードトレース・ユニット17の2*N+1個のポインタ(すなわちポインタPと、N個のポインタP1と、N個のポインタP2)に基づいて、3*N+1個のトレリス状態ポインタを必要とする。
【００２２】
図３を参照すると、本発明のデータ処理ステップがわかる。ステップ1において、各エポックの開始の前に、同等の状態ポインタP1のデータでポインタP2の値が更新される。ステップ2で新しいエポックが開始した後に、ステップ3の現在の入力データがステップ4でバッファされて、ステップ7でフォワードトレースされる。同時に以前のエポックに対応するデータがバッファから取り出されてトレースバックされ、ステップ5で復号データを生成する。次にステップ6で復号データが復号シーケンスメモリに書き込まれる。ステップ７において現在のデータデ実行されたフォワードトレースは、ポインタP1の値を決定する。ステップ8において、ポインタP2の格納された値とACSからの最小パス状態の情報(acs_select)とともに、ポインタP1の値がポインタPの値を生成するために使用される。また、ステップ6において、最小のトレリスのパス状態に関連する２つの以前のエポックから復号データを特定するために、ポインタPの値が使用され、その最小のトレリスのパス状態は復号シーケンスメモリから取り出される。ステップ9において、復号データは次の段階に進められ、ステップ10において、全体のエポックについて処理(ステップ3から9)が繰り返される。エポックが終了すると、次のエポックについてステップ11がアルゴリズム(ステップ1から10)を再度開始する。
【００２３】
図４を参照すると、前記のアルゴリズムの動作から生じたタイミング関係がわかる。フォワードトレース動作は、セル18により示されるように、エポック2のデータまで完全なエポックを処理する。このことはデータD1(すなわちエポック1のデータ)の復号を可能にし、そのデータD1は、セル19のエポック3で読み取られるエポック1からの復号データDD1になる。従って、セル19からの出力として最初のエポックの復号データDD1が作られる前に、２つのエポック(すなわちフォワードトレースによるエポック2(セル18)と、トレースバックによるエポック1(セル20))が完全に処理される。フォワードトレースが、エポック3のブランチj(1＜j＜T/2)を処理している場合、ポインタP1は現在の状態からエポック3の開始状態にポインタを移動し、ポインタP2は終了からエポック2の開始状態にポインタを移動し、結果のポインタPが現在の状態からエポック2の開始状態にポインタを移動する。
【００２４】
同時に、復号データシーケンスDD1(セル19)がマルチプレクサの出力21で利用可能になる。ポインタP1とPがエポック3のフォワードトレース(セル22)を進むと、復号データビットの出力が、ブランチ1からT/2を進む。従って、生き残りメモリの深さのスライディングウィンドウの大きさはTの一定値になり、その値はエポック3のブランチjからエポック1のブランチjまでの大きさに等しく、1＜j＜T/2である。要約すると、Tの合計メモリサイズと、２つのエポックの合計待ち時間は、更なる制御の複雑性を有することなく、先行技術のAPTFTメモリ管理機構に対して33%の削減を示す。
【００２５】
本発明のAPTFTアルゴリズムは、トレースバック及びレジスタ交換アルゴリズムに既知の利点を達成する。従って、1999年3月のI.E.E.E.  Transactions  on  Communications,  vol.41,  no.3の出版のG.Feygin他によるArchitectural  Tradeoffs  for  Survivor  Sequence  Memory  Management  in  Viterbi  Decoderに記載された先行技術と比較することが有用である。
【００２６】
表１は、本発明のAPTFTアルゴリズムと先行技術のレジスタ交換アルゴリズムとのいくつかの差異点と類似点を表したものである。
【００２７】
【表１】
2006511977.tif 000003
双方のアルゴリズムは、同様の生き残りメモリの深さについて同じ待ち時間とメモリサイズを有し、このことは一般的に以前のトレースバック・アルゴリズムにより達成されていない。改善されたAPTFTプロトコルは、3*N+1個の状態ポインタの必要性により表されるように、トレースバック・ユニット12とフォワードトレース・ユニット17に更なる制御を必要とするが、各ポインタの相対的な複雑性は小さい。対照的に、レジスタ交換アルゴリズムの使用は、各メモリ要素に2対1マルチプレクサと、メモリ要素間の相互接続が必要であり、必要なメモリに更なる複雑性を導入する。更に、本発明はトレリスのブランチ毎に2*N個のみのメモリ要素に対して読み取りと書き込みを行うが、レジスタ交換アルゴリズムは、トレリスのブランチ毎に全てのN*T個のメモリ要素に対して読み取りと書き込みを行わなければならない。この後者の特徴は、レジスタ交換システムの大きな消費電力を結果として生じ、符号の拘束長が増加すると制限になる。本発明の追加の状態ポインタは、簡単なランダムアクセスメモリの使用と消費電力の減少との見返りに、許容範囲のコストを表す。要約すると、本発明は、小さい拘束長の符号についてレジスタ交換アルゴリズムと競合することができ、符号の拘束長が増加するとレジスタ交換システムより効率的になる。
【００２８】
表２は、本発明とその他のトレースバックシステム(いわゆるkポインタ偶数アルゴリズム(k-pointer  even  algorithm))のいくつかの差異を表したものである。そのkポインタ偶数アルゴリズムは、一般的な先行技術のトレースバックシステムの複雑性と効率性を例示するものである。kポインタ奇数アルゴリズム(k-pointer  odd  algorithm)として知られるその他のトレースバック技術は複雑性と効率性の面で類似しているため、明示的に記載されない。
【００２９】
【表２】
2006511977.tif 000004
kポインタ偶数アルゴリズムによって達成される最善の待ち時間とメモリサイズは、kの値がTに近づくときに生じ、本発明の対応する待ち時間とメモリサイズの約２倍である。kがその最小値であるk=2の場合、kポインタ偶数アルゴリズムの待ち時間とメモリサイズは、本発明の対応する値の４倍である。従って、本発明はメモリの使用と待ち時間のパラメータについて相当の利点を提供する。この改善は、追加のトレリス状態の更新ポインタの形式をとる特別の制御の要件で達成され、最終的には大きい拘束長の符号の制限を表す。
【００３０】
表３は、本発明の実装と先行技術の1ポインタ・アルゴリズム(one-pointer  algorithm)のいくつかの差異を表したものである。１ポインタ・アルゴリズムは、小さい待ち時間の小さいメモリサイズのトレースバック・アルゴリズムである。均一ハイブリッド・アルゴリズム(even-hybrid  algorithm)として知られるその他のフィードバック技術は複雑性と効率性の面で類似しているため、明示的に記載されない。
【００３１】
【表３】
2006511977.tif 000005
1ポインタ・アルゴリズムによって達成される最善の待ち時間とメモリサイズは、kの値がTの値に近づくときに生じ、本発明の待ち時間とメモリサイズとほぼ等しい。kの値がk=2で最小になると、1ポインタシステムの待ち時間とメモリサイズは、本発明のものの3倍の大きさになる。従って、kの値が大きいときに、1ポインタ・アルゴリズムが本発明の性能に近づく。1ポインタ・アルゴリズムの利点は、本発明の3*N+1個の状態ポインタに比べて唯一の状態ポインタが必要であることである。しかし、読取動作が書込み動作よりk倍の速さで生じるため、単一のポインタが必要であることは、相対的に複雑な読取／書込制御で達成される。kの値が大きいときに、すなわちkの値がTの値に近づくときに、1ポインタ・アルゴリズムのメモリ読取／書込動作の数は、前述のレジスタ交換システムにより実行される動作の数に近づき、同様に1ポインタシステムの大きな消費電力を結果として生じる。
【００３２】
元の(先行技術の)APTFTシステムの一般化した形式が図１を参照して理解できる。一般的な実施例は、エポックの記述からその名前を導く。特に、エポックがメモリの深さの半分(又はT/2)に等しいサイズに必ずしも制限されない。むしろ、エポックはT/qと等しいものとして一般的に定められることがあり、ここでqは不等式2＜q＜Tにより定められる値を有する整数値である。
【００３３】
T/qの一般的なエポックの値の場合、図２に表される元のAPTFTの関係はいくつかの点で変更される。まず、バッファ15のサイズが(T/2)*Nではなく、(T/q)*Nである。次に、復号シーケンスメモリ13は全てのトレリス状態について全パス・トレースバック・ユニット12から復号データシーケンスを受領し、2エポックの後ではなく、q個のエポックの後に復号データをマルチプレクサ14に利用可能にする。q個のエポックの遅延は、同じメモリサイズのT*Nを必要とする。
【００３４】
図５の参照により、一般化した元のAPTFTアルゴリズムで生じるタイミング関係の理解が可能になる。フォワードトレースポインタPは最小トレリスパスを示し、2エポックだけではなく、qエポック分だけ早く存在する最小パスに関連するトレリス状態を提供する。一般化した設計は、2個の内部ポインタではなく、フォワードトレースのトレリス状態毎にq個の内部ポインタを必要とし、その内部ポインタは１つのエポックの間隔だけ時間をオフセットする。１エポックの終了までに、各内部ポインタP1、P2、...Pqは、対応するエポックの開始状態とトレリス状態パスを示し、全ての内部ポインタが主要ポインタPを作るように寄与する。図５でわかるように、D1に関連するデータの復号を可能にするために、フォワードトレースはDq+1(セル24)までのデータを処理し、それ故にDD1(セル26)になり、復号がエポックq+2(セル25)で生じる。従って、最初のエポックの復号データDD1が出力(セル25)として提供される前に、q+1個のエポックが完全に処理される(フォワードトレースによるエポック2からq+1と、トレースバックによるエポック1)。何らかの復号シーケンスブロックDDの最初のビットは、(q+1)+T/qのメモリの深さに関連し、復号シーケンスブロックの最後のビットは、Tの生き残りメモリの深さに関連する。
【００３５】
一般化した元のAPTFTプロセッサによりデータが処理されると、メモリサイズは、バッファメモリのT/q*Nと、復号シーケンスメモリのT*Nとを加えたもので構成され、(q+1)/q*T*Nの合計メモリサイズに一致する。更に、一般化した元のAPTFTアルゴリズムは、合計(q+1)*N+1の状態ポインタを必要とする(トレースバック・ユニットにNと、フォワードトレース・ユニットにq*N+1)。バッファメモリの１つのエポックの遅延(T/q個のサンプル)と、復号シーケンスメモリのq個のエポックの遅延(T個のサンプル)を加えたものが存在し、(q+1)個のエポックの遅延又は(q+1)*T/qサンプルに一致する合計の遅延を結果として生じる。
【００３６】
一般化した元のAPTFTアルゴリズムでは、フォワードトレース・ユニットの追加の内部ポインタにより、qが増加するとメモリサイズと遅延が減少する。システムに応じて、全体の複雑性を最小化するqの適切な選択が見出され、内部ポインタの数がメモリサイズと待ち時間に比べて小さなコストになる。内部ポインタの数は拘束長に比例するが、メモリサイズは拘束長に指数関数的に増加するため、前記のことは一般的に当てはまる。待ち時間に関する限り最適な場合は、qがTと等しいときに生じ、T+1の待ち時間を生じ、これはそのようなシステムでは最も可能性が低い。メモリサイズは(T+1)*Nになり、内部ポインタの数は(T+1)*N+1になる。この場合、エポックは1つのみのサンプルで構成され、バッファメモリはN個のレジスタで構成される。
【００３７】
一般化した元のAPTFT技術は、有利には１つ以上の複数デコーダ、並列又は分散データ処理を備えたデコーダ、インターリーブであれ非インターリーブであれ、直列又は並列の複数デコーダ、及び如何なる種類の類似の信号処理用途を有する如何なるトレリス・デコーダシステムにも適用され得る。
【００３８】
改善されたAPTFTシステムの一般化した実施例はまた、T/qと等しいものとしてエポックを再定義することにより実現され、ここでqは不等式2＜q＜Tにより定められる値を有する整数値である。T/qの一般化したエポックの値の場合、改善されたAPTFTシステムへの変更点は、バッファ15のサイズを (T/2)*Nから(T/q)*Nに変更することを有する。復号シーケンスメモリ13は、全てのトレリス状態について全パス・トレースバック・ユニット12から復号データシーケンスを受領し、１つのエポックではなく、q-1個のエポックの後に復号データをマルチプレクサ14に利用可能にする。q-1個のエポックの遅延は、(q-1)/q*T*Nのメモリサイズを必要とする。
【００３９】
図６を参照すると、一般化した改善されたAPTFTで生じるタイミング関係を理解することが可能になる。フォワードトレースポインタPは最小トレリスパスを示し、1エポックだけではなく、q-1エポック分だけ早く存在する最小パスに関連するトレリス状態を提供する。一般化した設計は、2個の内部ポインタではなく、フォワードトレースのトレリス状態毎にq個の内部ポインタを必要とし、その内部ポインタは１つのエポックの間隔だけ時間をオフセットする。１エポックの終了までに、各内部ポインタP1、P2、...Pqは、対応するエポックの開始状態と状態パスを示し、全ての内部ポインタが主要ポインタPを作るように寄与する。P1以外の全ての内部ポインタは、エポックの終了時にのみ更新され、以降のエポックの間にその値が変更されずに留まる。ポインタP1は各エポックの開始時にリセットされ、フォワードトレースを通じて継続的に更新される。
【００４０】
図６でわかるように、D1に関連するデータの復号を可能にするために、フォワードトレースはDq(セル28)までのデータを処理し、それ故にDD1(セル29)になり、復号がエポックq+1(セル30)で生じる。従って、最初のエポックの復号データDD1が出力(セル30)として提供される前に、q個のエポックが完全に処理される(フォワードトレースによるエポック2からqと、トレースバックによるエポック1)。フォワードトレースがエポックq+1のブランチj(1＜j＜T/2)を処理しているときに、ポインタP1は現在の状態からエポックq+1の開始状態にポインタを移動する。ポインタP2は終了からエポックqの開始状態にポインタを移動し、ポインタqは終了からエポック2の開始状態にポインタを移動し、ポインタPは現在の状態からエポック2の開始状態にポインタを移動する。同時に、復号シーケンスDD1がマルチプレクサの出力21で利用可能になる。ポインタP1とPがエポックq+1nのフォワードトレースを進むと、複合出力ビットがブランチ1からT/2を進む。従って、生き残りメモリの深さのスライディングウィンドウの大きさが一定値のTになり、そのTはエポックq+1のブランチjからエポック1のブランチjの大きさに等しく、1＜j＜T/2である。
【００４１】
一般化した改善されたAPTFTプロセッサによりデータが処理されると、メモリサイズは、バッファメモリのT/q*Nと、復号シーケンスメモリの(q-1)/q*T*Nとを加えたもので構成され、T*Nの合計メモリサイズに一致する。更に、一般化した改善されたAPTFTアルゴリズムは、合計(q+1)*N+1の状態ポインタを必要とする(トレースバック・ユニットにNと、フォワードトレース・ユニットにq*N+1)。バッファメモリの１つのエポックの遅延(T/q個のサンプル)と、復号シーケンスメモリの(q-1)個のエポックの遅延((q-1)*T/q個のサンプル)を加えたものが存在し、q個のエポックの遅延又はTサンプルに一致する合計の遅延を結果として生じる。
【００４２】
一般化した改善されたAPTFTアルゴリズムでは、フォワードトレース・ユニットの追加の内部ポインタにより、qが増加するとメモリサイズと遅延が一定に留まる。従って、2より大きくqを増加させることについてコスト優位が存在しない。しかし、最適ではないが、q＞2の一般化した改善されたアルゴリズムは、例えばメモリサイズの制限から受ける異なるシステム要件を満足する柔軟性を提示する。
【００４３】
一般化した改善されたAPTFT技術は、有利には１つ以上の複数デコーダ、並列又は分散データ処理を備えたデコーダ、インターリーブであれ非インターリーブであれ、直列又は並列の複数デコーダ、及び如何なる種類の類似の信号処理用途を有する如何なるトレリス・デコーダシステムにも適用され得る。
【図面の簡単な説明】
【００４４】
【図１】先行技術の全パス・トレースバック/フォワードトレース(APTFT)システムの簡単なブロック図である。
【図２】図１に表された先行技術のAPTFTのタイミング図である。
【図３】本発明の原理によるメモリ管理アルゴリズム動作のフローチャートである。
【図４】図３のフローチャートに従って処理されるデータの関係を示したタイミング図である。
【図５】図１に表された元のAPTFTシステムの一般化した実施例に従って処理されるデータの関係を示したタイミング図である。
【図６】本発明の一般化した実施例に従って処理されるデータの関係を示したタイミング図である。
【図１】
2006511977.tif 000006
【図２】
2006511977.tif 000007
【図３】
2006511977.tif 000008
【図４】
2006511977.tif 000009
【図５】
2006511977.tif 000010
【図６】
2006511977.tif 000011
【手続補正書】
【提出日】平成17年2月4日(2005.2.4)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、トレリス復号データを提供する装置であって、
前記符号化データパケットに応じて、トレリスの状態変化に関連する決定データを生成する手段と、
トレリスの状態変化により決定されるように、前記決定データに応じて先行のトレリス状態のシーケンスを特定するトレースバック・ネットワークであって、前記先行のトレリス状態がデータパケットのシーケンスについて特定されるトレースバック・ネットワークと、
前記先行のトレリス状態から望ましいトレリス状態パスを選択する手段と、
それぞれの新しいトレリスのブランチで、望ましいトレリス状態パスを実質的に継続して更新する手段と、
前記特定された先行のトレリス状態のシーケンスに応じて、前記トレリス復号データを提供する手段と
を有する装置。
【請求項２】
請求項１に記載のシステムであって、
前記トレースバック・ネットワークが、
トレリスを通じて全パス・トレースバックを実行する手段と、
トレリスを通じて全パス・フォワードトレースを実行する手段と
を更に有するシステム。
【請求項３】
請求項２に記載のシステムであって、
前記決定データで先行のトレリス状態を特定することにより、フォワードトレースポインタでそれぞれの新しいトレリスのブランチの望ましいトレリス状態を継続的に特定する手段を更に有するシステム。
【請求項４】
請求項３に記載のシステムであって、
前記望ましいトレリス状態パスが、全てのトレリス状態の中で最小基準パスであるシステム。
【請求項５】
請求項３に記載のシステムであって、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタであって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチで更新される第１のポインタと、
トレリス状態パス毎の第２のポインタであって、第２のポインタの値を有し、前記第２の値がエポックの境界で更新される第２のポインタと
を更に有し、
各エポックがT/2であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項６】
請求項５に記載のシステムであって、
前記フォワードトレースポインタが、前記第１のポインタの値と前記第２のポインタの値の双方に継続的に応じて、それによってエポックの間に各トレリスのブランチで実質的に継続して更新されるシステム。
【請求項７】
請求項６に記載のシステムであって、
前記第２のポインタが、前記第１のポインタの値で各エポックの終了時に一度更新され、前記第１のポインタがその後にリセットされるシステム。
【請求項８】
請求項７に記載のシステムであって、
前記システムにより出力される各復号ビットが、Tの関連するメモリの深さを有するシステム。
【請求項９】
請求項８に記載のシステムであって、
前記フォワードトレースポインタが、それぞれの新しいトレリスのブランチで２つの以前のエポックから望ましいトレリス状態パスを継続的に特定するシステム。
【請求項１０】
請求項２に記載のシステムであって、
前記トレースバック・ネットワークが、
同時にエポックの間にデータ到着順に入力符号化データをバッファメモリユニットに書き込む手段と、
以後のエポックの間に前記バッファメモリユニットから前記データを読み取り、前記全パス・トレースバック・ユニットに前記データを送出する手段と、
全パス・トレースバック・ユニットが前記バッファメモリユニットから読み取られたデータでトレリスを通じてトレースバックすると、全パス・トレースバック・ユニットから復号シーケンスメモリ・ユニットに復号された出力を送出する手段と、
同時に１つのエポックで、到着の逆順に前記復号シーケンスメモリ・ユニットから復号データを読み取る手段と、
N個の復号シーケンスのうちの１つを選択するために、前記復号シーケンスメモリ・ユニットから復号データ出力を多重化する手段であって、Nがトレリスの状態の数である手段と、
フォワードトレースポインタの値に従って、マルチプレクサユニットを介して復号シーケンスメモリから復号データ出力のサンプルを選択する手段と
を更に有するシステム。
【請求項１１】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、
前記データに応じてトレリス状態変化に関連する決定データを生成するステップと、
前記決定データに応じてトレリスの状態変化に従って先行のトレリス状態のシーケンスを特定するステップと、
各トレリスのブランチの特徴に応じて、望ましいトレリス状態パスを選択するステップと、
先行のトレリス状態の前記特定されたシーケンスに応じて、前記トレリス復号データを提供するステップと
を有する方法。
【請求項１２】
請求項１１に記載のシステムであって、
エポックの境界の間で望ましいトレリス状態パスの選択を更新するステップを更に有し、
各エポックがT/2であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項１３】
請求項１２に記載のシステムであって、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで望ましいトレリス状態パスを更新及び選択するステップを更に有するシステム。
【請求項１４】
請求項１３に記載のシステムであって、
複数のトレリス復号データシーケンスを特定するステップと、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで更新された複合ポインタで前記複数のトレリス復号データシーケンスのうちの１つを特定するステップと
を更に有するシステム。
【請求項１５】
請求項１４に記載のシステムであって、
第１のポインタを用いて複数のトレリス復号データシーケンスを特定するステップと、
エポックの所要時間を通じて、それぞれの新しいトレリスのブランチで前記第１のポインタに関連する値を更新するステップと、
第２のポインタを用いて複数のトレリス復号データシーケンスを特定するステップと、
前記第１又は前記第２のポインタに関連する値が更新されると常に、前記複合ポインタに関連する値を更新するステップと
を更に有するシステム。
【請求項１６】
請求項１５に記載のシステムであって、
各エポックの境界で、前記第２のポインタに関連する値を前記第１のポインタに関連する値と交換し、その後に前記第１のポインタをリセットするステップを更に有するシステム。
【請求項１７】
複数のトレリスのブランチとトレリス状態を有し、符号化シンボルを復号するトレリス・デコーダであって、
トレリス状態変化に関連する決定データを生成する手段と、
トレリスの状態変化によって決定されるように、遅延した決定データで複数の先行のトレリス状態シーケンスを特定することにより、複数のトレリス復号データシーケンスを提供する手段であって、前記状態変化のトレリスがN個の状態を有する手段と、
前記決定データで先行のトレリス状態を特定することにより更新されたポインタで、前記複数のトレリス復号データシーケンスのうちの１つを特定する手段と
を有し、前記ポインタが、各トレリスのブランチに関連するデータに応じて、エポックを通じて各トレリスのブランチで継続的に更新され、エポックがトレースバック間隔Tのサブ間隔であるトレリス・デコーダ。
【請求項１８】
請求項３に記載のシステムであって、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタP1であって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチの間に更新される第１のポインタと、
トレリス状態パス毎の更なるq-1個のポインタPj(j=2,3,...,q)であって、ポインタの値を有し、各ポインタの値がエポックの境界で更新されるポインタと
を更に有し、
各エポックがT/qの所要時間でのトレースバック間隔Tのサブ間隔であり、qが2以上の整数値であり、qがT以下であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項１９】
請求項１８に記載のシステムであって、
前記フォワードトレースポインタが、すべてのq個のポインタの値に継続的に応じて、それによってエポックの間に各トレリスのブランチで実質的に継続して更新されるシステム。
【請求項２０】
請求項１９に記載のシステムであって、
各ポインタPj(j=3,...,q)が、ポインタPj-1の値で各エポックの終了時に一度更新され、ポインタP2が、ポインタP1の値で各エポックの終了時に一度更新され、前記第１のポインタP1がその後にリセットされるシステム。
【請求項２１】
請求項２０に記載のシステムであって、
前記システムにより出力されるデータのシーケンス内にある各復号ビットが、Tの関連するメモリの深さを有するシステム。
【請求項２２】
請求項２１に記載のシステムであって、
前記フォワードトレースポインタが、それぞれの新しいトレリスのブランチでq個の前のエポックから望ましいトレリス状態パスを継続的に特定するシステム。
【請求項２３】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、トレリス復号データを提供する装置であって、
前記符号化データパケットに応じて、トレリスの状態変化に関連する決定データを生成する手段と、
トレリスの状態変化により決定されるように、前記決定データに応じて先行のトレリス状態のシーケンスを特定するトレースバック・ネットワークと、
前記先行のトレリス状態から望ましいトレリス状態パスを選択する手段と、
前記望ましいトレリス状態パスを更新する手段と、
前記特定された先行のトレリス状態のシーケンスに応じて、前記トレリス復号データを提供する手段と
を有し、
前記トレースバック・ネットワークが、
トレリスを通じて全パス・トレースバックを実行する手段と、
トレリスを通じて全パス・フォワードトレースを実行する手段とを更に有し、
前記全パス・フォワードトレースを実行する手段が、
トレリス状態パス毎の第１のポインタP1であって、第１のポインタの値を有し、前記第１のポインタの値がエポックの所要時間を通じてそれぞれの新しいトレリスのブランチの間に更新される第１のポインタと、
トレリス状態パス毎の更なるq-1個のポインタPj(j=2,3,...,q)であって、ポインタの値を有し、各ポインタの値がエポックの境界で更新されるポインタとを更に有し、
各エポックがT/qの所要時間でのトレースバック間隔Tのサブ間隔であり、qが2以上の整数値であり、qがT以下であり、トレースバック間隔Tが、トレリス符号化データシーケンス内にある復号データシーケンスの生き残りメモリの深さを定めるシステム。
【請求項２４】
請求項２３に記載のシステムであって、
複合フォワードトレースポインタが、すべてのq個のポインタの値に応じ、前記複合フォワードトレースポインタが、各エポックの境界で更新されるシステム。
【請求項２５】
請求項２４に記載のシステムであって、
各ポインタPj(j=3,...,q)が、ポインタPj-1の値で各エポックの終了時に一度更新され、ポインタP2が、ポインタP1の値で各エポックの終了時に一度更新され、前記第１のポインタP1がその後にリセットされるシステム。
【請求項２６】
一群のトレリス符号化データパケットを有するデータを処理するシステムにおいて、
前記データに応じてトレリス状態変化に関連する決定データを生成するステップと、
前記決定データに応じてトレリスの状態変化に従って先行のトレリス状態のシーケンスを特定するステップと、
各トレリスのブランチの特徴に応じて、望ましいトレリス状態パスを選択するステップと、
それぞれの新しいトレリスのブランチで望ましいトレリス状態パスを実質的に継続して更新するステップと、
先行のトレリス状態の前記特定されたシーケンスに応じて、前記トレリス復号データを提供するステップと
を有する方法。
【国際調査報告】
2006511977.tif 000012