(57)【特許請求の範囲】
【請求項１】
ステークの状態メトリックスが次の反復において後方再帰又は前方再帰の開始点として使用されるスライディングウィンドウアルゴリズムを使用して入力符号化信号を反復して復号化するように機能し、前記ステークの状態メトリックスがメモリに蓄積されるデコーダであって、
ステークの状態メトリックスが損失性圧縮形式で蓄積され、
特定の状態メトリックスを選択し、且つ、ステーク内における前記特定状態メトリックスの位置のみを蓄積することによって、状態メトリックスを圧縮することを特徴とするデコーダ。
【請求項２】
前記特定状態メトリックスは、ステークの全状態メトリックスの最低のコストを表わす状態メトリックスであることを特徴とする請求項１に記載のデコーダ。
【請求項３】
前記特定状態メトリックスの蓄積された位置によって指示されるステークの状態メトリックスに、ゼロのコストを表わす状態メトリックスを割り当て、且つ、ステークの他の総ての状態メトリックスには所定の等価な非ゼロのコストを割り当てることによって、デコーダがステークを復元することを特徴とする請求項２に記載のデコーダ。
【請求項４】
前記特定状態メトリックスの蓄積された位置によって指示されるステークの状態メトリックスに、ゼロのコストを表わす状態メトリックスを割り当て、且つ、ステークの他の総ての状態メトリックスには所定の非等価のコストを割り当てることによって、デコーダがステークを復元することを特徴とする請求項２に記載のデコーダ。
【請求項５】
選択された、関連付けられたコードワードで後方再帰を行って、数回の後方再帰ステップの後に、各状態のコストが、再帰ステップ中と二つの連続再帰ステップ間とにおいて他の状態に対して相対的に同一のままで、さらに後方再帰がその状態の可能な限り最低のコストに帰着することによって、前記所定の非等価のコストが決定されることを特徴とする請求項４に記載のデコーダ。
【請求項６】
最初の状態を通過し且つ無ノイズである符号化されたワードを復号化することによって、及び、前記特定状態メトリックスの蓄積された位置により指示されるゼロに等しい状態メトリックスによりステークを復元するために、最初の復号化される状態のために見出されるゼロに等しい状態メトリックスを持つ最初の状態メトリックスベクトルを選択することによって、前記所定の非等価のコストが決定されることを特徴とする請求項４に記載のデコーダ。
【請求項７】
入力信号の信号対ノイズ比に基づいてコストが見積もられることを特徴とする請求項３，４，５及び６のいずれかに記載のデコーダ。
【請求項８】
前記所定のコストが、永久記憶装置に蓄積されることを特徴とする請求項５，６，７，８及び９のいずれかに記載のデコーダ。
【請求項９】
請求項１乃至８のいずれかに記載のデコーダを備えている通信受信器。
【請求項１０】
請求項９に記載の通信受信器を備えている移動電話。
【請求項１１】
請求項９に記載の通信受信器を備えているマルチメディア装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、将来の反復において後方再帰のための開始点として将来に使用するためにステークの状態メトリックスが蓄積され、ある信号対ノイズ比を持つ入力符号化信号をスライディングウィンドウアルゴリズムを使って復号化する機能を有する反復デコーダに関する。
【０００２】
本発明はさらに、将来の反復において後方再帰のための開始点として将来に使用するためにステークの状態メトリックスが蓄積され、ある信号対ノイズ比を持つ入力符号化信号をスライディングウィンドウアルゴリズムを使って復号化する方法に関する。
【０００３】
【従来の技術】
そのような反復デコーダは、文書「Organisation de la memoire dans un turbo decodeur utilisant l'algorithme SUB-MAP」、Adod Dingninou, Fathi Raouafi及びClaude Berrou著、Departement d'electronique, ENST Bretagne, BP 832, 29285 Brest Cedex, Franceによって開示されている。
【０００４】
この文書は、スライディングウィンドウアルゴリズムを使う反復ターボデコーダを開示する。スライディングウィンドウアルゴリズムを使ってデータブロックを復号化するために、デコーダは、データブロックの最初及び最後の状態メトリックスベクトルの状態メトリックスの良好な評価に到達するため、データブロックの前及び／又は後の特定数のトレリスステップの復号化を開始する。これは、トレリスにおける状態メトリックスの収束特性により可能である。仮定される開始状態メトリックスにかかわらず、状態メトリックスは、データワードの符号化に用いるコードの結果として、数トレリスステップ後には正しい解に向かって収束するであろう。従って、状態メトリックスベクトルを形成する、１トレリスステップの中に２ｕ個の状態があり得るシステムでは、ターボデコーダは、復号化されるべきデータブロックの最初と最後とにおいて状態メトリックスの妥当な評価を与えるために状態メトリックスが十分に収束したと仮定して、データブロックの約５ｕトレリスステップ前及び／又は５ｕトレリスステップ後のところで始動する。データブロックの最初及び最後のところの状態メトリックスベクトルは、ステークと呼ばれる。スライディングウィンドウアルゴリズムでは、データブロックの前及び／又は後の５ｕトレリスステップが反復のたびに計算される。
【０００５】
スライディングウィンドウアルゴリズムへの改良として、文書「Organisation de la memoire dans un turbo decodeur utilisat l'algorithme SUB-MAP」は、反復デコーダが、次の反復での使用のためにステークを蓄積すると有利であると開示する。
【０００６】
これはメモリ使用量を増加させる一方で、データブロックの５ｕステップ外側でトレリスを開始する必要性を低減するので、結果的に処理要求は低減する。なぜなら、前の反復から得られるステークは既にデータブロックの最初及び最後における状態のかなり正確な評価であり、トレリスの５ｕステップ外側で始まる繰り返しの前方及び後方再帰からは、データブロックの最初及び最後の状態メトリックスの、格段により正確な評価は生じないからである。ステークの状態メトリックスは、ただ蓄積されることを必要とするのみである。
【０００７】
これにより、各メトリックスにつき８状態及び１０ビットをともなうシステムにおいては、ステーク当たり８０ビットの蓄積要求になる。
【０００８】
全部で５０００トレリスステップで、４０トレリスステップごとに１ステークの場合、メモリ要求量は１２５＊８＊１０＝１０キロビットである。
【０００９】
【発明が解決しようとする課題】
このデコーダの問題は、通常のスライディングウィンドウアルゴリズムに比較して、追加のメモリ要求量が望ましくないことである。
【００１０】
【課題を解決するための手段】
本発明は、損失性圧縮を使ってステークの状態メトリックスを圧縮することを特徴とするデコーダを提供することによって、この問題を解決する。
【００１１】
ステークの状態メトリックスを圧縮することによって、所要メモリ量はさらに低減される。
【００１２】
これは、損失性圧縮を使うことによってステークにおける状態メトリックスの一部の情報は失われるが、その結果として生じるエラーが、データの５ｕ外側で開始した後方再帰から生じるエラーと同程度なら、後方再帰はこの損失から不利益をこうむらないとする認識に基づく。従って、無損失のステークの状態メトリックスを蓄積する必要はない。
【００１３】
本発明の実施の形態は、反復デコーダが、特定の状態を選び、ステークの中でのその特定状態の位置だけを蓄積することによって状態メトリックスを圧縮できることを特徴とする。
【００１４】
一つのトレリスステップの中では、特定の状態に到達するコストを指示する、種々の状態の相対的重みだけが意味を持つ。最も有意義な状態の位置だけを蓄積すれば、蓄積要求は大いに低減される。上記の例において、最も有意義な状態の位置の蓄積を要するのは３ビットだけであり、メモリ要求量は１０キロビットから１２５＊３＝３７５ビットまで低減される。
【００１５】
本発明のさらなる実施の形態は、特定の状態が、ステークの全状態の中で最低コストを持つ状態となることを特徴とする。
【００１６】
ステークの最も見込みがある状態は、最低コストを反映するメトリックスに結合される。最低コストに結合されるメトリックスとともに状態のステークの中における位置だけを蓄積することによって、メトリックスの値は失われ、トレリスの中で最も見込みがある状態はどれかという情報だけが残る。上記の例において、メモリ要求量は４キロビットから１２５＊３＝３７５ビットまで低減されるが、情報の最有用部分、即ち、最も見込みがある状態の位置は保持される。これはメモリ要求量の著しい低減であると同時に、後方再帰のための適切な開始点はなお提供される。
【００１７】
本発明のさらなる実施の形態は、特定状態の蓄積された位置によって指示されるステークの状態にゼロのコストを割り当て、ステークの他の総ての状態には所定の等価で非ゼロのコストを割り当てることによって、反復デコーダがステークを復元できることを特徴とする。
【００１８】
ステークの復元は、入手可能の情報、即ち、最低コストを表わすメトリックスを持つ状態のステークにおける位置に基づく。他の状態の状態メトリックスはどれも同じ値に設定され、この復元されたステークはその後、後方再帰の開始点として次の反復で使われる。
【００１９】
本発明のさらなる実施の形態は、最初の状態を通過し且つ無ノイズである符号化されたワードを復号化すること、及び、上記特定状態メトリックスの蓄積された位置により指示されるゼロに等しい状態メトリックスによってステークを復元するための最初の復号化された状態のために見出されるゼロに等しい状態メトリックスを持つ最初の状態メトリックスベクトルを選択することによって所定の非等価コストが決定されることを特徴とする。
【００２０】
ステークを復元するための最適状態メトリックスは、ワードを符号化し、そのワードを復号化し、その間にワードがなお無ノイズであることを保証することによって決定される。エンコーダが、データワードを符号化している最中に、位置ｘで、ある状態、例えば状態２を通過する場合、デコーダは、コードワードが無ノイズであれば、同じ場所で、状態２が最低コストを持つことを見出す。このようにして見つかった状態メトリックスベクトルの状態メトリックスは、この例では、状態２に関連付けられ、定数とみなすことができ、例えば永久メモリの中に蓄積することができる。前の反復で蓄積された位置によって何らかの状態が指示された状況でデコーダがステークを復元するときには、同状態に関連付けられている、永久メモリに蓄積されたその状態メトリックスベクトルが選択される。
【００２１】
例えば、前の反復のときに蓄積された位置が状態２を指示するなら、デコーダは、状態２に関連付けられている状態メトリックスベクトルをメモリから引き出すことによってステークを復元し、それらの状態メトリックスを次の反復で使用する。
【００２２】
本発明のさらなる実施の形態は、コストが入力信号の信号対ノイズ比に基づいて見積もられることを特徴とする。
【００２３】
トレリス状態の状態メトリックスの絶対値は、その状態に到達するコストを反映する。従って、信号が高い信号対ノイズ比を持つときは、状態の見込みは、信号が低い信号対ノイズ比を持つときよりも異なるだろう。その結果、信号対ノイズ比が高いシステムでも、状態メトリックスによって反映される、ある状態に達するためのコストは、状態メトリックスベクトルの中でさらに異なるだろう。高い信号対ノイズ比を持つ信号には明らかにより見込みが高い一つの状態が存在するだろうし、他のあり得る状態に到達するためのコストはより高くなるだろう。
【００２４】
信号対ノイズ比が低い信号では、どの状態もより見込みがあるものとして傑出することはなく、どの状態でも到達するコストはほぼ同じになるだろう。従って、本発明は、信号の信号対ノイズ比を反映するため、ステークの総ての状態の総てのメトリックスに適用される、コストのスケール率を導入する。
【００２５】
【発明の実施の形態】
これより、本発明を図面によって説明する。
【００２６】
図１は、デコーダによってデータワードに実行される２連続反復のためのスライディングウィンドウアルゴリズムの概念を示している。
【００２７】
ウィンドウの内側、データワード７上に置かれたデータブロック１が復号化される。このためデコーダは、データブロック１の最初及び／又は最後から５ｕ離れた距離３、５で復号化を開始する。データブロック１の最初及び／又は最後において再帰が状態メトリックスベクトル９、１１に達するとき、状態メトリックスベクトル９、１１の評価はかなり正確である。これらの状態メトリックスベクトル９、１１は、データブロック１を復号化するための開始点として使用できる。
【００２８】
次の反復で前記のプロセスは繰り返され、デコーダは、データブロック１９の最初及び／又は最後から５ｕ離れた距離で復号化を開始する。データブロック１９の最初及び／又は最後においてトレリスが状態メトリックスベクトル１５、１７に達するとき、前の反復の結果としてデータワード１３の正確さは向上するので、状態メトリックスベクトル１５、１７の評価はかなり正確であり、結果的に、現在の反復で見出される状態メトリックスベクトル１５、１７は前の反復のときといくぶん異なる。状態メトリックスベクトル９、１１、１５、１７は蓄積されず、それらは必要なときにその都度計算される。このため計算要求は増加するが、それと同時に、反復間に状態メトリックスベクトルを蓄積するための追加のメモリは必要ない。
【００２９】
図２は、計算を低減するためにメモリ使用量を犠牲にしてステークを蓄積する概念を示している。最初の反復では、データワード２５が基礎的スライディングウィンドウアルゴリズムを使って復号化される。このためデコーダは、データブロック２７の最初及び／又は最後から５ｕ離れた距離２９、３１で復号化を開始する。データブロック２７の最初及び／又は最後において再帰が状態メトリックスベクトル３３、３５に到達するとき、状態メトリックスベクトルの評価はかなり正確である。このときデータブロックは復号化され、データブロック２７の前方及び後方の再帰によって、状態メトリックスベクトル３３及び３５の正確さはさらに向上する。状態メトリックスベクトル３３、３５をステークは、称される。状態メトリックスベクトル３３及び／又は３５はステークとして蓄積されて次の反復で使用される。データブロック２７の最初における状態メトリックスベクトル３３は、データブロック３９で次の前方再帰を開始するための状態メトリックスベクトル３７として使われる。データブロック２７の最後における状態メトリックスベクトル３５は、データブロック３９で次の後方再帰を開始するための状態メトリックスベクトル３８として使われる。
【００３０】
それゆえ、データブロックの最初及び／又は最後から５ｕ離れたところで復号化を開始する必要はそれ以上なく、蓄積要求の増大という犠牲によって計算要求は減る。
【００３１】
図３は、ステークの損失性圧縮と復元とを示している。
【００３２】
図２において説明したように、反復の中で見つかるステーク４３は、次の反復で使用するために保存される。蓄積要求を低減するために、ステーク４３の状態メトリックス４５、４７、４９、５１の総てが蓄積されるわけではない。特定の状態メトリックス４５、４７、４９、５１の位置のみが蓄積される。これは、総ての状態メトリックス４５、４７、４９、５１の値がその過程で失われることを意味する。図３は、４つのあり得る状態を含むシステムのステーク４３を示している。状態メトリックス４５が特定の状態となるべく選ばれる場合、例えばそれがこの状態にたどりつく最低コストに関連付けられていることを理由に選ばれる場合、記憶装置５３には、ステーク４３における状態メトリックス４５の位置だけが蓄積され、この例においてはその位置は位置０であり、値０だけが蓄積される。４状態のシステムにおいては、一つの位置を蓄積するために各ステークにつき２ビットだけ必要であり、８状態のシステムでは各ステークにつき３ビットだけ必要である。
【００３３】
次の反復においては、デコーダが記憶装置５３から位置を引き出し、復元手段６３が、記憶装置５３と記憶装置６５とから引き出した情報に基づいてステーク６７を復元する。記憶装置６５には、システムのあり得る各状態につき状態メトリックスベクトル５５、５７、５９、６１が蓄積される。復元手段６３は、記憶装置５３から引き出した位置によって指示されるシステムの同じ状態に関連付けられた状態メトリックスベクトル５５、５７、５９、６１を記憶装置６５から選択し、選択した状態メトリックスベクトル５５、５７、５９、６１から復元するステーク６７まで、適切な状態メトリックス０、Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ、Ｇ、Ｈ、Ｉ、Ｊ、Ｋ、Ｌをコピーすることによってステークを復元する。
【００３４】
このようにしてメモリ要求量は大いに低減され、それと同時に、スライディングウィンドウアルゴリズムの利点と図２の概念による計算要求の低減とが維持される。
【００３５】
図４は、ステークの復元に用いる状態メトリックスベクトルの決定を示している。
【００３６】
図４において、エンコーダ４２は、データワードを符号化する間に、時刻Ｔに状態４８を通過する。これは、無ノイズチャネル４４を介した転送後に、データワードがデコーダ４６によって復号化される際に、デコーダが、状態５８が時刻Ｔに最低コストを持つことを見出すことを意味する。このとき、関連付けられた状態メトリックスベクトル５２は、状態５８について典型的とみなすことができる。エンコーダ４２が総ての状態６２、４８、６４を確実に通過することによって、各状態５６、５８、６０につき典型的状態メトリックスベクトル５０、５２、５４が得られる。この操作は一度だけ実行すればよく、獲得した状態メトリックスベクトル５０、５２、５４は将来に使うために蓄積できる。４つのあり得る状態があるシステムの場合、４つの典型的状態メトリックスベクトルが得られる。これらの状態メトリックスベクトルは実際、図３の記憶装置６５に蓄積される状態メトリックスベクトル５５、５７、５９、６１になる。デコーダ４６が反復の前にステークを復元するときには、前の反復時に蓄積された位置が、復元するステークのための状態を指示する。そして、デコーダ４６は、蓄積された状態メトリックスベクトル５５、５７、５９、６１を選択し、選択した状態メトリックスベクトルから復元するステークまで、状態メトリックスをコピーすることによってステークを復元する。
【００３７】
図５は、４つの状態を持つシステムのトレリスと、ステークの復元時に用いる状態メトリックスベクトルの決定とを示している。
【００３８】
４つの状態があり得るシステムにおいて、デコーダがＭＡＸ−ＬＯＧ−ＭＡＰタイプの場合、状態メトリックスベクトルＳ０、Ｓ１、Ｓ２、Ｓ３を計算する式は次のとおりである。
S0(k+1)=min(S0(k)+0, S1+2A)
S1(k+1)=min(S2+A, S3+A)=A+min(S2, S3)
S2(k+1)=min(S0+2A, S1+0)
S3(k+1)=min(S2+A, S3+A)=A+min(S2, S3)
これらの式を解くと、ゼロコードワードの状態メトリックスベクトルＳＭＶ０＝（０、３Ａ、２Ａ、３Ａ）が導出される。
【００３９】
図４に記述されたように、他の３つの状態メトリックスベクトルＳＭＶ１、ＳＭＶ２、ＳＭＶ３は状態メトリックスベクトルＳＭＶ０から導き出される。
【００４０】
状態メトリックスベクトルＳＭＶ０で始まり、トレリスの中である状態から別の状態に進むのにともなうコストは、トレリスにおける移行経路沿いの０、Ａ及び２Ａによって指示される。例えば、状態０の状態メトリックスベクトル、ＳＭＶ０は値（０、３Ａ、２Ａ、３Ａ）を持つ（Ｓ０、Ｓ１、Ｓ２、Ｓ３）である。状態０から状態２に移行するには、状態メトリックスベクトルＳＭＶ０の状態メトリックスにトレリスステップのコストを加えなければならない。これにより、状態メトリックス（２Ａ、３Ａ、０、３Ａ）を持つ新しい状態メトリックスベクトルＳＭＶ２が得られる。同じ要領で、状態３の状態メトリックスベクトルＳＭＶ３と状態１の状態メトリックスベクトルＳＭＶ１とは連続的に得られる。前の反復で蓄積された、関連付けられた状態に達する最低コスト（０によって指示）を指示する状態メトリックスの位置が、たとえば状態２を指示している場合、ステークの復元に用いる選択された状態メトリックスベクトルは、状態メトリックス（２Ａ、３Ａ、０、３Ａ）を持つ状態メトリックスベクトルＳＭＶ２である。図５の例で、状態メトリックスベクトルＳＭＶ０から始まり、状態０から状態２に進むときにエンコーダによって生成されるコードビット「１１」によって、状態メトリックスベクトルＳＭＶ０から状態メトリックスベクトルＳＭＶ２まで、デコーダは変化する。
【００４１】
そこで、状態メトリックスベクトルＳＭＶ２、ＳＭＶ３及びＳＭＶ１については、以下の状態メトリックスが得られる。
SMV2=(2A, 3A, 0, 3A)
SMV3=(3A, 2A, 3A, 0)
SMV1=(3A, 0, 3A, 2A)
これらの状態メトリックスベクトルＳ０、Ｓ１、Ｓ２及びＳ３は、復元手段６３によるステークの復元時に使用する状態メトリックスベクトル５５、５７、５９、６１として、図３の記憶装置６５に蓄積することができる。これらは事前に決定できるので、これらの状態メトリックスＳ０、Ｓ１、Ｓ２及びＳ３は、永久の記憶装置６５に蓄積できる。
【図面の簡単な説明】
【図１】  スライディングウィンドウアルゴリズムの概念を示す。
【図２】  計算を減らすためにメモリ使用量を犠牲にしてステークを蓄積する概念を示す。
【図３】  ステークの損失性圧縮と復元とを示す。
【図４】  ステークの復元に用いる状態メトリックスベクトルの決定を示す。
【図５】  ４状態を含むシステムのトレリスと、ステークの復元時に用いる状態メトリックスベクトルの決定とを示す。
【図１】
0004834863.tif 000002
【図２】
0004834863.tif 000003
【図３】
0004834863.tif 000004
【図４】
0004834863.tif 000005
【図５】
0004834863.tif 000006