(57)【特許請求の範囲】
【請求項１】
ブロック長Ｎの格子によって表される信号の受信畳込み符号化シーケンスを復号する方法（２００）であって：
ａ）前記格子を窓に分割する段階（２０２）；
ｂ）前記格子の長さＬの窓を選択する段階（２０４）；
ｃ）前記窓の最初より前の点Ｐ１から、順方向で前記窓の最初まで、順方向帰納を利用して、前記格子の一部を復号する段階（２０６）であって、Ｐ１は、前記順方向帰納が前記窓の最初における既知の状態メトリックを判定するように、前記窓の最初から十分離れた距離で選択される、段階（２０６）；
ｄ）前記窓の最後より後の点Ｐ２から、逆方向で前記窓の最後まで、逆方向帰納を利用して、前記格子の一部を復号する段階（２０８）であって、Ｐ２は、前記逆方向帰納が前記窓の最後における既知の状態メトリックを判定するように、前記窓の最後から十分離れた距離で選択される、段階（２０８）；
ｅ）前記窓の開始における既知の状態から開始する段階ｃ）で定義された順方向帰納、および前記窓の最後における既知の状態から開始する段階ｄ）で定義された逆方向帰納を用いて前記窓内にある前記格子の前記一部を復号する段階（２１０）；および
ｆ）各状態における、段階ｃ）で定義された前記順方向帰納メトリック，段階ｄ）で定義された前記逆方向帰納メトリック，および各状態での分岐メトリックを利用して、前記窓のソフト出力を計算し、その状態に対する前記ソフト出力を出力する段階（２１２）；
によって構成されることを特徴とする方法。
【請求項２】
段階ｃ）（２０６）および段階ｄ）（２０８）は、長さＬよりも小さいもしくは等しい各長さＰ１およびＰ２を含むことを特徴とする請求項１記載の方法。
【請求項３】
段階ｃ）（２０６）は、それぞれ前記畳込み符号の制約長の複数倍である長さＰ１およびＰ２を含み、段階ａ（２０２））は、前記畳込み符号の制約長から独立した長さＬを含むことを特徴とする請求項１記載の方法。
【請求項４】
請求項１記載の前記方法は：
ｇ）ブロック全長Ｎが復号されるまで、段階ｂ）ないし段階ｆ）（２０４，２０６，２０８，２１０，２１２）を反復する段階であって、反復される前記選択する段階は、次の窓を無作為に選択する段階（２０４）を含み、反復される前記段階ｂ）ないしｅ）（２０４，２０６，２０８，２１０）は、それぞれ現在の段階ｃ）ないしｆ）（２０６，２０８，２１０，２１２）と同時に行われる、段階；
をさらに含んで構成されることを特徴とする請求項１記載の方法。
【請求項５】
ソフト判定出力デコーダ（１１０，１１２，１１４，１１６）によってフレーム・バッファ（１０８）において長さＬの窓に分割されるブロック長Ｎの格子によって表される信号の畳込み符号化シーケンスを処理する、受信機（１０４）および復調器（１０６）を具備する無線電話（１００）であって、前記出力デコーダは：
前記窓の最初より前の点Ｐ１から、順方向で前記窓の最初まで、順方向帰納を利用して、前記格子の一部を復号する順方向帰納プロセッサ（１１０）であって、Ｐ１は、順方向帰納が前記窓の最初における既知の状態メトリックを判定するように、前記窓の最初から十分離れた距離で選択される、順方向帰納プロセッサ；
前記窓の最後より後の点Ｐ２から、逆方向で前記窓の最後まで、逆方向帰納を利用して、前記格子の一部を復号する逆方向帰納プロセッサ（１１２）であって、Ｐ２は、逆方向帰納が前記窓の最後における既知の状態メトリックを判定するように、前記窓の最後から十分離れた距離で選択される、逆方向帰納プロセッサ；
前記逆方向帰納プロセッサ（１１２）は、前記窓の最後における前記既知の状態から開始して、逆方向で前記窓の開始まで、逆方向帰納を利用して、前記窓内の前記格子の一部をその後復号して、前記窓内の既知の逆方向帰納状態メトリックのセットを定め；
前記順方向帰納プロセッサ（１１０）は、前記窓の最初における前記既知の状態から開始して、順方向で前記窓の最初まで、順方向帰納を利用して、前記窓内の前記格子の一部をその後復号して、前記窓内の既知の順方向帰納状態メトリックのセットを定め；および
各状態における、前記順方向帰納メトリック，前記逆方向帰納メトリック，および分岐メトリックを利用して、前記窓の各状態におけるソフト出力を計算し、その状態に対する前記ソフト出力を出力するデコーダ（１１６）；
によって構成されることを特徴とする無線電話。
【請求項６】
前記長さＰ１およびP２は、前記長さＬよりも小さいもしくは等しいことを特徴とする請求項５記載の無線電話。
【請求項７】
前記長さＰ１およびP２は、それぞれ前記畳込み符号の制約長の複数倍であり、前記長さＬは、前記畳込み符号の制約長から独立していることを特徴とする請求項５記載の無線電話。
【請求項８】
各窓に対し追加の順方向および逆方向プロセッサを含み、全ての前記順方向帰納プロセッサおよび逆方向帰納プロセッサは並行して全窓のブロックを復号するために動作することを特徴とする請求項５記載の無線電話。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、一般に、通信システムに関し、さらに詳しくは、畳込み符号通信システムの受信機で用いられるソフト出力デコーダに関する。
【０００２】
【関連出願】
なお、本出願は、発明者DesalおよびClassonによる米国特許出願第０９／５００，８１９号，発明者Classon, Schaffner, Desai, BakerおよびFriendによる米国特許出願第０９／５０２，１３２号および発明者ClassonおよびSchaffnerによる米国特許出願第０９／５０１，９２２号に関する。関連出願は、本出願と同一日付にて出願され、本出願の譲受人に譲渡され、この参照により本明細書に全体が含まれるものとする。
【０００３】
【従来の技術】
畳込み符号は、送信情報をエラーから保護するためにデジタル通信システムで用いられる場合が多い。送信機では、発信符号ベクトルは格子図(trellis diagram)を利用して記述でき、その複雑さはエンコーダの制約長(constraint length)によって決定される。演算的な複雑さは制約長の増加とともに増加するが、符号化の堅牢性(robustness)も制約長とともに増加する。
【０００４】
受信機では、当技術分野で周知なようなビタビ・デコーダ(Viterbi decoder)などの実際的なソフト判定デコーダは、格子構造を利用して、最尤送信符号ベクトルについて最適な検索を行う。しかし、ビタビ・アルゴリズムは演算的に複雑であり、その複雑さは制約長の増加とともに指数関数的に増加する。実質的にこのことは、ビタビ・デコーダは、大きな制約長では、畳込み符号について大量のメモリおよび処理能力を必要とすることを意味する。
【０００５】
直接シーケンス符号分割多元接続（ＤＳ−ＣＤＭＡ：Direct Sequence Code Division Multiple Access）規格ＩＳ−９５や、ＧＳＭ(Global System for Mobile Communications)などのさまざまな通信システム用のコーダは、このような大きな制約長を有する。例えば、ＧＳＭハーフ・レート制約長はＫ＝７であり、ＩＳ−９５制約長はＫ＝９である。
【０００６】
ビタビ・デコーダの別の欠点は、送信中に発生した実際のエラーの数に関係なく、各符号ベクトルについて固定数の演算を実行しなければならないことである。従って、ビタビ・デコーダは、わずかな送信エラーや、まったくエラーのない受信信号についても、多くのエラーを有する受信信号と同じ数の演算を利用して処理する。
【０００７】
近年、従来の符号化方法よりも優れたターボ符号(turbo codes)が開発されている。一般に、ターボ符号とは、２つまたはそれ以上の畳込み符号と、ターボ・インタリーバ(turbo interleaver)とによって構成される。ターボ復号(turbo decoding)は反復的で、ソフト出力デコーダを利用して個別の畳込み符号を復号する。ソフト出力デコーダは、各ビット位置に関する情報を与え、これはソフト出力デコーダが他の畳込み符号を復号するのを助ける。ソフト出力デコーダは、通常ＭＡＰ(maximum a posteriori)デコーダであり、ソフト出力を判定するために逆方向および順方向復号を必要とする。しかし、メモリ，処理および演算的なトレードオフのため、一般にＭＡＰ復号は最適以下の近似(sub-optimal approximation)に制限される。これらの変形例も全て、ブロック上で順方向および逆方向復号を必要とする。
【０００８】
３ＧＰＰ(third generation partnership project for wireless systems)などの将来の規格について、ブロック長Ｎ＝５１２０を有する８状態ターボ符号(8-state turbo code)は、４０９６０ワード分の中間格納を必要とし、これは受け入れ難い。将来のシステム（より大きなフレームおよびより多くの数の状態）は、さらに多くのメモリを必要とする。逆に、Ｎ＝５１２０の８状態格子についてソフト出力を生成しないビタビ・デコーダは、１００ワード未満の中間格納しか必要としない。
【０００９】
【発明が解決しようとする課題】
従って、従来のターボ・デコーダおよびＭＡＰデコーダによって課せられる制限なしに、畳込み符号を復号するための全体的なメモリおよび処理条件を低減するソフト出力デコーダが必要とされる。
【００１０】
【実施例】
本発明は、ビタビ・デコーダに比べてわずかな演算量の増加だけで、従来のターボ・デコーダからメモリ条件を大幅に低減する。全体では、これはより効率的なデコーダを提供する。さらに、本発明は、従来のターボ・デコーダおよびＭＡＰデコーダの制限を最小限に抑える。
【００１１】
一般に、ブロック符号，畳込み符号，ターボ符号などは、図１に示すように格子としてグラフ表現される。ＭＡＰ(maximum a posteriori)タイプのデコーダ（対数(log)ＭＡＰ，ＭＡＰ，最大対数(max-log)ＭＡＰ，定数対数(constant-log)ＭＡＰなど）は、当技術分野で周知なように、ソフト出力を与えるために、格子上で順方向および逆方向一般化ビタビ帰納(generalized Viterbi recursions)を利用する。ＭＡＰデコーダは、全受信ビットに基づいて、各情報ビットについて復号ビット・エラー確率を最小限に抑える。典型的な従来のＭＡＰデコーダは、復号で用いるためのメモリを必要とする。
【００１２】
符号化シーケンスのマルコフ特性(Markov nature)（ここで、以前の状態は未来の状態または未来の出力分岐に影響を及ぼしえない）のため、ＭＡＰビット確率は、過去（格子の開始から現在状態まで），現在状態（現在値の分岐メトリック(branch metric)）および未来（格子の最後から現在値まで）に分けることができる。具体的には、ＭＡＰデコーダは現在状態まで順方向および逆方向帰納を実行し、ここで過去および未来の確率は現在の分岐メトリックとともに用いられて、出力判定を生成する。ハードおよびソフト出力判定を与える原理は当技術分野で周知であり、上記の復号方法のいくつかの変形例が存在する。
【００１３】
ターボ符号用に検討されるソフト入力／ソフト出力ＳＩＳＯデコーダのほとんどは、L.R. Bahl, J. Cocke, F. Jelinek, J. Raviv による論文 "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate", IEEE Transactions on Information Theory, Vol. IT-20, March 1974, pp.284-7（ＢＣＪＲアルゴリズム）における従来のＭＡＰアルゴリズムに基づいている。図１は、ターボ符号で利用できる、８状態畳込み符号用のこのアルゴリズムの格子図を示す。これからわかるように、一般に系統的畳込み符号(systematic convolutional code)であるが、ブロック符号でもよい成分符号(constituent codes)とインターリーバによって、ターボ・コーダは構築される。ＭＡＰアルゴリズムは、受信シーケンスについて情報ビットのエラー確率を最小限に抑えるだけでなく、受信シーケンスについて情報ビットが１または０である確率を与える。ＢＣＪＲアルゴリズムは、各ビット位置（格子セクション）についてソフト出力判定を与え、ここでブロック内のソフト入力の影響は、過去（以前のソフト入力(earlier soft inputs)）からの寄与と、現在のソフト入力からの寄与と、未来（以降のソフト入力(later soft inputs)）からの寄与とに分けられる。このデコーダ・アルゴリズムは、各格子セクション（ステージ）について最適なソフト出力を導くために、格子上で順方向および逆方向一般化ビタビ帰納を必要とする。これらの帰納的確率、より一般的には、確率の対数尤度比（ＬＬＲ：log-likelihood ratio）は、反復的ターボ復号におけるＳＩＳＯ復号ステップ間で渡される。情報ビットｕtのＬＬＲは、復号済みシーケンス内の全ビットについて次式の通りである（ｔ＝１〜Ｎ）。
【００１４】
【数１】
0003741616.tif 000002
数式１において、受信シーケンスについて復号済みビットが格子内で１（または０）に等しい確率は、符号のマルコフ特性により項の積からなる。マルコフ特性は、現在が与えられると、過去および未来は独立であるというものである。現在(t（ｎ，ｍ）は、時間ｔにて状態ｍであり、また時間ｔ−１にて直前の状態がｎであるとき、シンボルｙtを生成する確率である。現在は、分岐メトリックの関数をである。過去(t（ｍ）は、受信シーケンス｛ｙ1，．．．，ｙt｝で時間ｔにて状態ｍである確率であり、未来(t（ｍ）は、時間ｔにて状態ｍから受信シーケンス｛ｙt+1，．．．ｙN｝を生成する確率である。確率(t（ｍ）は、(t-1（ｍ）と(t（ｎ，ｍ）の関数として表すことができ、順方向帰納という。
【００１５】
【数２】
0003741616.tif 000003
ここで、Ｍは状態の数である。(t+1（ｎ）および(t（ｎ，ｍ）から確率(t（ｎ）を計算するための逆方向帰納は次式の通りである。
【００１６】
【数３】
0003741616.tif 000004
数式１における全体的な帰納的確率は、ｕt＝１（または０）に対応する格子1（Ｂ0）における分岐上で加算することによって算出される。
【００１７】
数式１におけるＬＬＲは、時間ｔにて順方向帰納および逆方向帰納の両方が利用可能であることを必要とする。この条件を満たすＢＣＪＲ方法は、逆方向帰納全体を算出・格納して、(t-1および(tを利用してｔ＝１からｔ＝Ｎまで(t（ｍ）および(tを帰納的に算出する。
【００１８】
このデコーダの欠点は、Ｎステージのブロック全体を最初にメモリに格納してから、処理しなければならないことである。これは大量のメモリ（Ｎセクション(Ｍ状態(状態当りのビット数）を必要とするだけでなく、情報を出力する前に長さＮの信号遅延を生じさせる。Ｗ−ＣＤＭＡシステム（Ｎ〜５０００，Ｍ＝８，１３ビット）では、必要なメモリは約０．５Ｍビットである。ｃｄｍａ２０００システムでは、Ｎは約２００００であり、これは約２Ｍビットのメモリを必要とする。小さいシーケンス長では、メモリ利用は一般に問題にならない。しかし、ターボ符号が最良の性能を発揮する大きなＮでは、メモリ利用は重要になる。
【００１９】
複雑さの点では、ＢＣＪＲ方法は逆方向帰納についてＮＭ状態更新を必要とし（格子セクション当りＭ状態更新，符号内のＮ格子セクション）、最適な性能を与える。実際には、（図１に示すように）ブロック全体で逆方向帰納がプロセッサによって実行され、メモリに格納される。次に、順方向帰納がプロセッサによって実行され、その結果は現在状態および格納済み未来状態とともに用いられ、各ステージのソフト出力判定を得る。この場合、プロセッサは各状態に対して二度処理する、すなわち、逆方向帰納状態を格納するために一度処理し、順方向帰納処理中に一度処理する（スループットは１／２）。
【００２０】
メモリ利用問題に対処するために、スライド窓(sliding window)および同様な変形例が開発された。図２に示すように（以降の図面において、実線矢印は、帰納ありで格納なしの出力を表し、点線矢印は、出力なしで格納なしの学習期間(learning period)を表し、中空矢印は、出力なしの格納済み帰納を表し、矢印の方向は順方向または逆方向帰納を示す）、S. Benedetto, D. Divsalar, G. Montorsi, F. Pollaraによる論文 "Algorithm for continuous decoding of turbo codes," Electronics Letters, Vol. 32, Feb. 15, 1996, pp. 315-5に記述されるスライド窓方法では、時間ｔ＋Ｐにおける全ての状態は等しく確かである（あるいは未知である）という仮定が逆方向帰納について用いられる。この仮定を用いる場合、学習期間Ｐは、ほぼ最適な性能を与えるために、成分符号のいくつかの制約長でなければならない。学習期間を小さくしすぎると、従来のビタビ・アルゴリズムにおける「有限(finite)」トレースバック(traceback)の効果と同様な、顕著な性能劣化が生じることがある。
【００２１】
スライド窓方法はメモリを必要としないが、演算的に複雑である。つまり、逆方向帰納全体が実行・格納される代わりに、各状態を判定するために部分的な逆方向帰納のみが実行される（そして格納されない）。各現在状態について、アルゴリズムは、初期状態が未知のままで、現剤状態から離れた学習期間Ｐにて未来帰納を初期化する。未来確率は、格子の既知の端部からではなく、未知の将来の点から逆方向に計算される。長さＰ（学習期間）は、部分的な逆方向帰納が現在状態に達するときまでに、未来確率が正しいことが最もありそうであるように設定される。Ｐは、符号のレートおよび制約長と、期待チャネル状態とに依存する。例えば、１／２レート畳込み符号を有する８状態デコーダでは、Ｐは一般に１６〜３２であり、ここでＰは制約長の倍数である。このデコーダの欠点は、部分的な逆方向帰納が等しく同様な（未知の状態）から開始され、現在の窓(present window)に達するまで反復することが許されることである。これは、スライド窓は従来のビタビ・アルゴリズムにおける有限トレースバックの効果と同様な、真のＭＡＰ性能からの劣化を生じさせ、復号ビット・エラーの確率を増加させるので、最適以下のアルゴリズムである。また、プロセッサは各状態に対してＰ回処理し（スループットは１／Ｐ）、出力遅延Ｐを有する。さらに、このアルゴリズムはＰ倍の複雑さを必要とし、これは更なる処理を追加することでしか軽減できない。
【００２２】
スライド窓方法は、ｔ＝１〜Ｎについて、時間ｔ＋Ｐから時間ｔまでの逆方向帰納を計算し、(t-1（ｍ）および(tから(t（ｍ）および(tを計算するものとして要約できる。スライド窓方法は、ＢＣＪＲ方法で必要とされるＮＭから、帰納のために必要なわずかなメモリ量まで、メモリ条件を軽減する。ダブル・バッファを想定すると、メモリ量はわずか２Ｍであり、解析において安全に無視できる。
【００２３】
しかし、このメモリ節約を達成するためには、逆方向帰納の演算的複雑さはＰ倍増加する。また、スライド窓方法は、「有限」窓サイズのため最適以下である。
【００２４】
Viterbiらによる米国特許第５，９３３，４６２号（また同様に、S. Pietrobon, S. Barbulescuの論文 "A Simplification of the Modified Bahl et al. Decoding Algorithm for systematic Convolutional Codes," Int. Symp. On Inform. Theory and its Applications, Sydney, Australia, pp. 1073-7, Nov. 1994, revised Jan. 4, 1996およびS. Pietrobonの論文 "Efficient Implementation of Continuous MAP Decoders and a Synchronisation Technique for Turbo Decoders," Int. Symp. On Inform. Theory and its Applications, Victoria, B.C., Canada, pp. 586-9, September 1996）において記載される別の従来のデコーダは、図３に示すような別のスライド窓方法を記述する。
【００２５】
従来のスライド窓方法の演算的複雑さの大幅な増加を低減するビタビ・スライド窓方法は、処理をブロック単位で実行する。逆方向帰納は時間ｔ＋２Ｌから開始し、逆方向帰納値は時間ｔ＋Ｌから時間ｔまで格納される。順方向帰納および出力尤度計算は、時間ｔから時間ｔ＋Ｌのブロックで実行される。メモリはＮＭからＬＭまで軽減され、演算複雑さは二倍にしかならない。未知の状態で帰納を開始するという重要な知見は、スライド窓方法と同じである。
【００２６】
この方法はある程度メモリを必要とし、依然として演算的に複雑である。デコーダは、一度に１シンボルではなく、ブロック単位で順方向にスライドする窓を与えることにより、前述のスライド窓方法とは異なる。具体的には、スライド窓は長さＬを有するものと定義され、この長さＬは前述の学習期間Ｐに等しい。また、Ｌは全格子長Ｎの倍数であり、窓は長さＬの単位で格子の開始から最後までスライドする。このように、格子全体が格納される従来のデコーダで必要とされるメモリは、ＮからＮ／Ｌ（Ｌ＝３２とすると、ｃｄｍａ２０００およびＷ−ＣＤＭＡでは一般に３キロビット）まで低減される。
【００２７】
また、このデコーダは未知の未来状態から開始する学習期間を利用し、そのため前述のように最適以下である。具体的には、順方向帰納は、プロセッサによって、第１窓Ｌの開始における既知の状態から開始して、第１窓の長さ（Ｌ）において実行される。これらの順方向帰納状態は格納される。次に、プロセッサは、第１窓の最後における既知の状態を定めるために、順方向帰納が開始したところから２Ｌ離れた点にて開始する未知の状態から、逆方向帰納を実行する。次に、プロセッサは、第１窓の最後における既知の状態から開始して、現在状態まで、第２逆方向帰納を実行し、逆方向帰納および格納済み順方向帰納状態からの情報は、ソフト出力を生成するために用いられる。第１窓の全ての出力が判定されると、窓は量Ｌだけ順方向にスライドし、第１窓の最後にて判定された状態からプロセスは繰り返される。
【００２８】
このデコーダの欠点は、学習期間Ｌにおける第１逆方向帰納が等しくありそうな（未知の状態）から開始され、長さＬにおいて反復することが許されることであり、これは前述のように最適以下である。また、プロセッサは各状態に対して３回処理するが、１／２のスループットが得られるように、順方向および逆方向プロセッサを同時に実行することができる。デコーダは、２Ｌの出力遅延を生じる。さらに、逆方向帰納は２倍の複雑さを必要とし、これは更なる処理を追加することでしか軽減できない（あるいはスループットを増加できない）。さらに、このデコーダは逆の順序でソフト出力を生成し、これは出力する前に追加のメモリにバッファする必要がある。
【００２９】
図４は、時間成分を追加した、図３のグラフの拡大図である。動作時に、時間０において、順方向プロセッサは、位置０からＬまでの第１窓にて順方向帰納を実行して、情報を格納し、一方、同じ期間中に、逆方向プロセッサは位置２ＬからＬまで逆方向帰納を実行して、位置Ｌ，時間Ｌにて第１窓の最後における既知の状態を定める。その後、第２逆方向帰納は、位置Ｌから０において、時間Ｌから２Ｌまで動作し、第１窓におけるソフト出力を定める。このとき、ソフト判定を反転して、順番に出力でき（明らかに、これは２Ｌの遅延以降に生じる）、メモリはクリアされ、窓位置は長さＬだけ順方向にスライドし、プロセスは反復する。あるいは、追加の逆方向帰納プロセッサおよびメモリがあれば、スループットを増加できる。
【００３０】
図５は、追加の逆方向プロセッサを利用した、図３のグラフの別の結果を示す。動作時に、時間０において、順方向プロセッサは、位置０からＬまでの第１窓にて順方向帰納を実行して、情報を格納し、一方、同じ期間中に、逆方向プロセッサは位置２ＬからＬまで逆方向帰納を実行して、位置Ｌ，時間Ｌにて第１窓の最後における既知の状態を定める。その後、第２逆方向帰納プロセッサは、位置Ｌから０において、時間Ｌから２Ｌまで動作し、第１窓におけるソフト判定を定める。同時に、順方向および追加の逆方向プロセッサは、第２窓の情報（位置Ｌから２Ｌまで）の処理を開始することによって第２サイクルを開始する。時間２Ｌにて、第１窓のソフト判定が出力され、一方、第２窓の順方向帰納および逆方向学習期間はすでに完了している。次に、第２窓の第２逆方向帰納が実行され、第２窓のソフト出力を得る。これからわかるように、この方法はスループットを２倍にする。第２窓の順方向帰納が格納される際に、第１窓の順方向帰納の情報が利用されるので、２倍のメモリが必要になる。
【００３１】
上記のデコーダ（特に図４および図５）には、ソフト出力は順番が狂って生成されるという問題があり、出力する前にこれらのソフト出力を反転する必要がある。これは、追加のバッファ・メモリを必要とし、出力を反転するために余分な遅延が生じる。
【００３２】
本発明は、新規な方法でこの問題を解決する。加えて、本発明は、多くのMｂｐｓを処理するために要求される将来のブロードバンド通信システムに必要とされる高スループットを提供する。図６は、本発明による畳込み復号を利用する格子図を示す。格子符号は、図７において簡略化されるような通信システムにおいて長さＮの格子によって表される信号の畳込み符号化シーケンスから得られる。無線電話１００において、信号は、当技術分野で周知なように、アンテナ１０２を介して受信機１０４および復調器１０６に移動する。信号は、フレーム・バッファ１０８にロードされる。順方向帰納プロセッサ１１０および逆方向帰納プロセッサ１１２は、ブロックに対して処理する。
【００３３】
本発明は、従来技術でなされるような窓から窓へ渡される状態情報に頼らないで独立して復号され得る窓を提供することにおいて、図３ないし図５の前述のスライド窓方法とは異なる。窓サイズは格子全体で等しくする必要はないが、この説明に限り窓サイズは等しいと想定する。特に、窓は、Ｌのある倍数が全格子長Ｎに等しくなるような長さＬを有するものと定義される。距離P1の順方向学習期間は、未知の過去の状態から開始し、窓の開始で順方向状態メトリックを定義するために用いられ、また距離P２の逆方向学習期間は、未知の将来の状態から開始し、窓の最後で逆方向状態メトリックを定義するために用いられる。本発明は、学習期間および状態推定が用いられるので、前述したように副次的である。学習期間はこの説明に限り等しいと想定されるが、学習期間は全て等しい必要はない。例えば、符号が格子のある端部にて別の端部に比べてより破壊(puncture)している場合,これは等しい性能を得るためにより長い学習期間を必要とする。
【００３４】
具体的には、順方向学習帰納は、長さＰ１である未知の状態から始まって窓の開始で既知状態を推定および定義するために窓の開始前で窓の開始まで、順方向プロセッサ１１０によって実行され、そして逆方向学習帰納は、長さＰ２である未知の状態から始まってその窓の終端で既知状態を推定および定義するために第1窓の後方へかつ窓の終端を越えて、逆方向プロセッサ１１２によって実行される。順方向および逆方向学習期間は、Lにあるいは互いに等しくなる必要はない。さらに、学習期間は、制約長の少なくとも数倍に等しいけれど、窓の長さは必要とされない。好ましくは、Ｐ１＝Ｐ２および両者がＬより十分小さくてもよい。
【００３５】
窓内で、順方向および逆方向帰納は従来技術に従って実行され、窓内の全ての状態メトリックスを定義する。典型的には、逆方向帰納および順方向帰納からの情報は、メモリ１１４に格納されるが、デコーダ１１６内の現在の分岐メトリックスとともに用いられ、ソフト出力判定を生成する。デコーダ１１６からのソフト出力判定は、上記引用されたBahl等の論文（BCJRアルゴリズム）に示されたような、既知のターボ符号化技術に従って生成される。
【００３６】
窓を処理する最後で、他のどの窓も最初として処理されるために選択され得ることができ、各窓に対する終端情報が隣接する窓から転送される前もって定義された状態情報に依存しないで再推定される。結果として、好適な実施例では、全ての窓が同時に別々のプロセッサによって独立して処理され、従来のデコーダのスループットに比べ約N/L倍のデコーダ・スループットを実現する。もちろん、ブロックの最初と最後が通常すでに知られているので第1窓と最終窓に対する例外はある。従って、これらに対応する学習期間が必要とされない。
【００３７】
本発明の利点は、窓が順番に処理される必要がなくかつ並行に処理できることで、N/Lのオーダで効率を向上させる点である。メモリ条件は、窓の中でどの復号化方法を用いるかに依存する。
【００３８】
図８は、本発明に従って、ブロック長Ｎの格子によって表される信号の受信畳込み符号化シーケンスを復号する方法２００を表すフローチャートを示す（図６も参照）。格子図は、当技術分野で周知である。第１ステップ２０２は、格子を長さＬの窓に分割する。次のステップ２０４は、格子の窓を選択する。次のステップ２０６は、窓の最初より前の点Ｐ１から、順方向で窓の最初まで、順方向帰納を利用して、格子の一部を復号し、ここでＰ１は、順方向帰納が窓の最初における既知の状態メトリックを判定するように、窓の最初から十分離れた距離で選択される。次のステップ２０８は、窓の最後の後にある点P２から窓の最後へ逆方向帰納を用いて格子の部分を復号し、上記の復号ステップにおいて定められた窓の最後における既知の状態から、逆方向で窓の開始まで、逆方向帰納を利用して、窓内の格子の部分を復号し、ここでＰ２は、逆方向帰納が窓の最後における既知の状態メトリックを判定するように、窓の最後から十分離れた距離で選択される。一般に、点P１およびP２での状態メトリックは未知であり、一般化されたビタビ・アルゴリズムを用いる帰納は高い確率をもって窓の既知の状態に集中するであろう。P１およびP２は、畳み込み符号の制約長の複数倍である。P１およびP２の双方は、長さLより短く、好ましい実施例では、P１はP２に等しい。次のステップ２１０は、一般化されたビタビ・アルゴリズムを用いて、窓内の格子の部分を復号する。次のステップ２１２は、順方向帰納状態メトリックと、分岐メトリックと、格納済み逆方向帰納状態メトリックとを利用して、順方向帰納プロセスの各状態またはステージにおいてソフト出力を計算し、このステージのソフト出力を出力する。好ましくは、帰納更新およびソフト出力は、ＭＡＰアルゴリズムもしくはＭＡＰの派生アルゴリズムのうちの一つ（すなわち、対数(log)ＭＡＰ，最大対数(max-log)ＭＡＰ，定数対数(constant-log)ＭＡＰなど）を利用して算出される。
【００３９】
窓が完全に復号されると、他の窓が復号化するために選択される。このプロセスはブロック内の全ての窓が複合化されるまで繰り返される。最初と最後の窓は、ブロックの開始と最後が一般に畳込み符号の既知の状態にあるという点で、特殊な場合である。従って、最初の窓を処理する場合、逆方向学習期間のみが要求され、最後の窓を処理する場合、順方向学習期間のみが要求される。
【００４０】
好適な実施例では、N/Lメモリ・サイズの増加およびN/Lスループットの増加に従って、N/Lソフト出力デコーダを用いて並行に処理される。
【００４１】
表１は、本発明の方法とともに、３つの従来の方法のメモリ，スループットおよび演算条件を概略的にまとめたものである。括弧内の項目は、追加の逆方向プロセッサを利用する。演算の複雑さは順方向および逆方向処理の双方に含む。本発明は、格子をN/Lのセクションに分割し、各セクション内で窓の長さＡを有する双方向ソフト出力デコーダを使用する。
【００４２】
【表１】
0003741616.tif 000005
これらの方法の相違点を示すため、表２はシーケンス長（Ｎ＝５０００），状態の数（Ｍ＝８），窓サイズ（Ｌ＝３２）およびセクション（N/L＝４）の代表値を用いた場合の結果を示す。
【００４３】
【表２】
0003741616.tif 000006
表２が示すように、本発明のメモリ条件は、ＢＣＪＲ方法よりも少なくてすむ。スライド窓法は、本発明よりもっと低いスループットをもつ。最後に、回路での実施では、Ｎ/Ｌセクション中の格子を処理するために要求されるゲート数は非常に合理的である。また、演算の複雑さの指数は大きいけれども、特別のハードウェアが有効である特定用途向けIC（非DSP ASIC）を用いる場合、それは非合理的ではない。
【００４４】
本発明は、わずかな複雑さの増加だけで、スループットを増加し、ターボ・デコーダで必要なメモリを大幅に軽減する。３ＧＰＰ規格内のターボ符号では、４０９６０ワードの中間格納は約１５００ワード以下に容易に低減できる。対照的に、従来のスライド窓技術は、特性を劣化させるだけでなく、本発明より１０ないし１５倍の演算の複雑さを要求する。
【００４５】
畳込み符号用のソフト出力デコーダの特定の構成要素および機能について説明してきたが、当業者であれば、本発明の広い範囲内で、さらに少ないあるいは追加の機能を採用できよう。本発明は、特許請求の範囲によってのみ制限されるものとする。
【図面の簡単な説明】
【図１】第１の従来のソフト出力デコーダ方法の格子図を示す。
【図２】第２の従来のソフト出力デコーダ方法の格子図を示す。
【図３】第３の従来のソフト出力デコーダ方法の格子図を示す。
【図４】図３の図の拡大グラフを示す。
【図５】図３の図の別の拡大グラフを示す。
【図６】本発明によるソフト出力デコーダ方法の格子図を示す。
【図７】本発明によるソフト出力デコーダのブロック図を示す。
【図８】本発明によるソフト出力デコーダ方法のフローチャートを示す。
【符号の説明】
１００  無線電話
１０２  アンテナ
１０４  受信機
１０６  復調器
１０８  フレーム・バッファ
１１０  順方向帰納プロセッサ
１１２  逆方向帰納プロセッサ
１１４  メモリ
１１６  デコーダ
１１８  追加の逆方向プロセッサ
【図１】
0003741616.tif 000007
【図２】
0003741616.tif 000008
【図３】
0003741616.tif 000009
【図４】
0003741616.tif 000010
【図５】
0003741616.tif 000011
【図６】
0003741616.tif 000012
【図７】
0003741616.tif 000013
【図８】
0003741616.tif 000014