(57)【特許請求の範囲】
【請求項１】
通信システム受信機において複数のウォルシュ・インデックスをソートする方法であって、前記複数のウォルシュ・インデックスは複数のウォルシュ・シンボル内にあり、前記方法は：
前記複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを判定する段階；
前記各ウォルシュ・インデックスの判定されたエネルギを、前記１個のウォルシュ・シンボル内に存在する他の全ウォルシュ・インデックスと比較する段階；
前記判定されたエネルギを比較する段階に基づいて、他のウォルシュ・シンボル内にある他のウォルシュ・インデックスに対して後に行うエネルギ判定に使用するために、前記判定段階と並行して、前記１つのウォルシュシンボル内に存在する、最も大きなエネルギを有する所定の数のウォルシュ・インデックスをソートする段階；
および、ソートされたウォルシュ・インデックスに関連するデータを記憶する段階；
から成ることを特徴とする方法。
【請求項２】
前記判定段階は、前記複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを計算する段階を更に含むことを特徴とする請求項１記載の方法。
【請求項３】
前記ソートされたウォルシュ・インデックスに関連するデータは、ソートされたウォルシュ・インデックス毎に、蓄積インデックス・エネルギ，蓄積Ｉベクトル，蓄積Ｑベクトルおよび蓄積パス履歴を更に含むことを特徴とする請求項１記載の方法。
【請求項４】
前記複数のウォルシュ・シンボルの内、第２ウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを判定する段階；
前記所定数のウォルシュ・インデックスのエネルギを、前記第２ウォルシュ・シンボル内に存在する各ウォルシュ・インデックスの前記判定されたエネルギと結合する段階；
結合したエネルギを互いに比較する段階；
結合したエネルギを比較する段階に基づいてソートされたウォルシュ・インデックスを生成するために、他のウォルシュ・シンボル内に存在する他のウォルシュ・インデックスに対して後に行うエネルギ判定において使用するために、前記判定および結合段階と並行して、第２のウォルシュ・シンボル内に存在する、所定の数のウォルシュ・インデックスをソートする段階；
および、ソートされたウォルシュ・インデックスに関連するデータを蓄積する段階；
を更に含むことを特徴とする請求項１記載の方法。
【請求項５】
前記段階は、入力エネルギに応じて出力を制御する出力制御群の各ウォルシュ・シンボルに対して繰り返され、各出力制御群は複数のウォルシュ・シンボルを含み、各ウォルシュ・シンボルに対して最も高いエネルギを有すると判定されたウォルシュ・インデックスが、前記出力制御群の間に送信されたウォルシュ・シンボルを表わすことを特徴とする請求項４記載の方法。
【請求項６】
通信システム受信機において複数のウォルシュ・インデックスをソートする装置であって、前記複数のウォルシュ・インデックスは複数のウォルシュ・シンボル内にあり、前記装置は：
前記複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを判定する判定手段；
前記判定手段に結合され、前記各ウォルシュ・インデックスの判定されたエネルギを、前記１個のウォルシュ・シンボル内に存在する他の全ウォルシュ・インデックスと比較する比較手段；
前記比較手段に結合され、前記判定されたエネルギの比較に基づいてソートされたウォルシュ・インデックスを生成し、他のウォルシュ・シンボル内に存在する他のウォルシュ・インデックスに対して後に行うエネルギ判定に使用するために、最も大きなエネルギを有する所定の数のウォルシュ・インデックスをソートする手段；
および、ソートされたウォルシュ・インデックスに関連するデータを蓄積する手段；
から成ることを特徴とする装置。
【請求項７】
前記判定手段は、前記複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを計算する手段を更に含むことを特徴とする請求項６記載の装置。
【請求項８】
前記ソートされたウォルシュ・インデックスに関連するデータは、記憶されたインデックス毎に、蓄積インデックス・エネルギ，蓄積Ｉベクトル，蓄積Ｑベクトルおよび蓄積パス履歴を更に含むことを特徴とする請求項６記載の装置。
【請求項９】
符号分割多重アクセス（ＣＤＭＡ）通信システム受信機において複数のウォルシュ・インデックスをソートする装置であって、前記複数のウォルシュ・インデックスは複数のウォルシュ・シンボル内にあり、前記装置は：
前記複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを判定するプロセッサ；
前記プロセッサに結合され、前記各ウォルシュ・インデックスの判定されたエネルギを、前記１個のウォルシュ・シンボル内に存在する他の全ウォルシュ・インデックスと比較する比較回路；
および前記比較回路に結合され、前記判定されたエネルギの比較に基づいてソートされたウォルシュ・インデックスを生成し、エネルギの判定と平行して、他のウォルシュ・シンボル内に存在する他のウォルシュ・インデックスに対して後に行うエネルギ判定に使用するために、１つのウォルシュ・シンボルの内の所定の数のウォルシュ・インデックスに関連するソートされたウォルシュ・インデックスを記憶するレジスタ；
および、ソートされたウォルシュ・インデックスに関連するデータを蓄積する蓄積装置；
から成ることを特徴とする装置。
【請求項１０】
前記ウォルシュ・シンボルは、入力エネルギに応じて出力を制御する出力制御群のウォルシュ・シンボルから成ることを特徴とする請求項９記載の装置。
【発明の詳細な説明】
発明の分野
本発明は、一般的に通信分野に関し、更に特定すれば受信信号を復調する方法および受信機に関するものである。
発明の背景
ＩＳ−９５に記載されているもののような、直接シーケンス符号分割多重アクセス（ＤＳ／ＣＤＭＡ：Direct Sequence Code Division Multiple Access）は、自己干渉システム（self interference system）である。かかる通信システムにおいては、多数の移動機および／たは携帯機が、同一地理的領域では同一スペクトラムを使用する。加入者ユニットからの信号は、それらの拡散符号（即ち、ユーザのロング・コードＰＮシーケンスならびにＩおよびＱ  ＰＮシーケンス）に基づいて、互いに差分が取られる。かかるシステムの容量の限界は、システム内の自己干渉量に左右される。この点を例示するために用いられる比喩に、カクテル・パーティの会話がある。カクテル・パーティにいて隣の人に話しかける際、部屋には他に誰もいない場合、聞こえるようにするために大声で話す必要はない。幾人かの人が更に部屋に入ってきて会話し始めると、聞こえるようにするために声を大きくしてで話さなければならなくなる。言い換えれば、自己干渉が増大し、この干渉を克服するために、送信出力を増大しなければならない訳である。更に部屋の中で話す人々が増々多くなるに連れて、増々大声で話さなければならなくなり、部屋の中のその他の人々も、相手に聞こえるようにするためにそうする。結果的に、他の人々よりも聞こえるようにするために無限量の出力を要する点に到達する。これが容量の限界である。
このカクテル・パーティの比喩を拡大すると、部屋の中にいる各人に聴取が困難であると、各人が通常に聴取可能な場合よりも、他の招待客に対して高いレベルの干渉を開始する。このように、各人が聴取し易くなると、同時に行うことが可能な会話の数が増加する。即ち、システムの容量が増大することになる。その結果、ＤＳ／ＣＤＭＡシステムにおいて受信機の感度増大に大きな利点がある。受信機の感度上昇はいかなるものであれ、必要な送信機出力量、結果的に自己干渉量の直接的な低減に至る。セルラ・システムの容量を増大することにより、オペレータの収益（revenue）の増大、および加入者が受けるサービスの向上がもたらされる。
ＤＳ／ＣＤＭＡシステムにおける標準的な受信機は、非コヒーレント的（non-coherently）に送信信号を検出する。非コヒーレント検波は、２個の送信信号間の位相差を考慮に入れていない。標準的な非コヒーレント受信機は、まず受信信号をディスプレッド（despread）し（即ち、ＩおよびＱ  ＰＮシーケンス，およびユーザのロング・コードＰＮシーケンスを除去する）、データのウォルシュ・シンボルを蓄積する。ディスプレッドされた蓄積データに対して、高速ハダマード変換（ＦＨＴ：Fast Hadamard Transform）を行う。ＦＨＴは、本質的に、送信機が送出した可能性のある６４通りの可能なウォルシュ・シンボルに対して、ディスプレッド信号を相関付ける。次に、受信機は、エネルギが最も高いウォルシュ・シンボルを選択する（エネルギは、ＩおよびＱベクトルの二乗を加算することによって決定される）。非コヒーレント受信機はエネルギ検出器であり、送信信号の位相を使用しない。コヒーレント復調のビット・エラー・レート（ＢＥＲ）性能は、非コヒーレント変調よりも優れていることは既知である（Sklar, Digital Communications,ISBM 0-13-21 1939-0, Prentice Hall 1988, P. 161-164）。
ＤＳ／ＣＤＭＡシステムにおける標準的な受信機に対するある種の変更について、送信信号の疑似コヒーレント検出（pseudo-coherent detection）を本質的に与えるものが提案されている。例えば、"Near Maximum Likelihood Demodulation for M-ary Orthogonal Signals"（Rod WaltonおよびMark Wallace, IEEE Conf. on Vehicular Technology, pp. 5-8, May 18-20, 1993）では、著者は、個々のシンボルの非コヒーレント・ランクの使用により、検出器の性能向上を図ることを提案している。変更は、受信シンボルに対して、ほぼ最尤シーケンス（near maximum likelihood sequence）を形成し、以前の仮説的コヒーレント・エネルギに基づき、可能性のない仮設を破棄することによって、少数の残存インデックス（survivors）を残す。シンボルを処理するに連れて、生き残る仮説は、送信シーケンスの最良予測に収束する傾向がある。この方法は、著者が述べるように、リアル・タイムで実施するには実用的でない。何故なら、出力制御群の時間間隔の間に得られるサイクルの殆どが、遷移エネルギ・メトリック（transitional enrgy metrics）の計算の間にアルゴリズムによって消費されてしまうからである。尚、ここで言う時間間隔とは、残存パス間の可能な遷移各々のエネルギ、およびフィンガに対する親しいウォルシュ・シンボルの各点を計算しているときのことである。
したがって、ソート・プロセスを改良し、残存インデックスを決定する際に使用するサイクルが少なくてすみ、受信機の設計という観点から実用的な実施を実現する方法および装置に対する必要性がある。
【図面の簡単な説明】
第１図は、ＤＳ／ＣＤＭＡセルラ電話システムと互換性のある送信機のブロック図を概略的に示す。
第２図は、ＤＳ／ＣＤＭＡセルラ電話システムにおいて利用されるウォルシュ・マトリクスである。
第３図は、ＣＤＭＡタイム・フレーム間における種々のレートでの送信を概略的に示す。
第４図は、ＤＳ／ＣＤＭＡセルラ電話システムと互換性があり、本発明によるソート処理を実施可能な受信機のブロック図を概略的に示す。
第５図は、残存ソート処理を受ける、出力制御群の６個のウォルシュ・シンボルを概略的に示す。
第６図は、本発明による残存ソート処理を達成する、回路実施形態を概略的に示す。
実施例の詳細な説明
概略的に述べると、通信システム受信機は、潜在的可能があるウォルシュ・インデックス全体をソートし、以降の処理に使用するために残存インデックスを決定する。ソート・プロセスは、以降の処理と並行して実施されるので、記憶／ソート処理を実施するための大量のメモリは不要となる。本通信システム受信機は、このソート処理を少数のサイクルで実施することにより、サイクルを保存し、必要に応じて他のタスクに利用可能とするという利点がある。
より具体的には、通信システム受信機は、複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギを判定することにより、複数のウォルシュ・インデックス内に存在する複数のウォルシュ・インデックスのソート処理を行う。次に、通信システム受信機は、各ウォルシュ・インデックスの判定されたエネルギを、１個のウォルシュ・シンボル内に存在する他のウォルシュ・インデックス全てと比較する。次に、通信システム受信機は、エネルギの判定と並行して、所定数のウォルシュ・インデックスに関連するデータを記憶し、判定されたエネルギの比較に基づいて、他のウォルシュ・シンボル内に存在する他のウォルシュ・インデックスについて後に行うエネルギ判定に使用する。
好適実施例において、エネルギの判定は、複数のウォルシュ・シンボルの内１個のウォルシュ・シンボル内に存在する各ウォルシュ・インデックスのエネルギの計算によって実行される。記憶されるデータは、記憶されたインデックス毎に蓄積されたインデックス・エネルギ，蓄積されたＩベクトル，蓄積されたＱベクトル，および蓄積されたパス履歴に関連するデータである。記憶されるデータは、判定された最も高いエネルギに基づいて記憶される。このプロセスは、出力制御群を含む各ウォルシュ・シンボルに対して繰り返され（ることが重要であり）、各ウォルシュ・シンボルに対して最も高いエネルギを有すると判定されたウォルシュ・インデックスが、出力制御群の間に送信されたウォルシュ・シンボルを表わす。好適実施例の通信システムは、直接シーケンス符号分割多重アクセス（ＤＳ−ＣＤＭＡ）通信システムであるが、他の通信システムも考慮されており、本発明のソート処理を実施することによって恩恵を得ることができる。
ＤＳ−ＣＤＭＡセルラ電話システムと互換性のある送信機のブロック図を、概略的に第１図に示す。音声信号即ちデータ信号１２を符号化部１４に入力し、符号化信号１６を得る。符号化信号１６は、好ましくは１度に６シンボルで、６４進直交変調器（64-ary orthogonal modulator）１８によって、固有の６４進シンボルにマップされる。好適実施例では、６４進直交変調器は、第２図に示すウォルシュ・マトリクスである。６個の符号化シンボルは、式Ｃ0＋２Ｃ1＋４Ｃ2＋８Ｃ3＋１６Ｃ4＋３２Ｃ5＝ｉによってマップされる。Ｃ0ないしＣ5は符号化シンボルであり、ｉは出力ウォルシュ・シンボルのインデックスである。シンボルは１または０のいずれかであるので、この式は、６個のシンボルを６４個のウォルシュ・インデックスの唯１個のみにマップする。６４進変調器の出力は、６４個のウォルシュ・チップ（ウォルシュ・マトリクスの１行）で構成された、ウォルシュ・シンボルである。
変調器には加算器２０が接続されており、ロング疑似ランダム・ノイズ（ＰＮ）シーケンス２２をウォルシュ・チップと加算する。加算器２０の出力は、同相即ちＩチャネル２２と直交位相即ちＱチャネル２４とに分割される。Ｉチャネル２２は加算器２６を有し、加算器２０の出力をＩ  ＰＮシーケンス２８と加算する。Ｑチャネル２４は加算器３８を有し、加算器２０の出力とＱ  ＰＮシーケンス４０とを加算する。加算器３８は遅延素子４２に接続されている。次に、ＩおよびＱデータは、バンドパス・フィルタ３０，４４を通され、混合され（３２，４６）、加算されて（３４）、キャリア周波数信号を発生する。このキャリア周波数信号は、アンテナ３６を通じて送信される。この結果、入力データ・ストリームのオフセットＱＰＳＫ変調が得られる。
入力音声信号１２は、最大レート（９６００ｂｐｓ）１０４，半レート（４８００ｂｐｓ）１０６，１／４レート（２４００ｂｐｓ）１０８，または１／８レート（１２００ｂｐｓ）１１０のいずれかとすることができる。第３図は、ＣＤＭＡタイム・フレーム１００における、種々のレートによるデータ送信の例を示す。タイム・フレーム１００は、１６の出力制御群（ＰＣＧ）１２で構成されている。ＰＣＧ１０２は６個のウォルシュ・シンボル１１２で構成され、各ウォルシュ・シンボル１１２は、６４個のウォルシュ・チップ１１４によって規定される。最後に、各ウォルシュ・チップ１１４は、４個のＰＮチップ１１８を有する。入来するデータのレート（最大，半．．．）は、ユーザの音声活動（voice activity）によって決定される。ユーザが殆ど何も言わない期間は１／８レートでエンコードされ、連続的な早口の音声は最大レートでエンコードされる。タイム・フレーム１００の間にどの出力制御群がアクティブであるのかは、ロング・コード２２および音声活動によって決定される。
ＤＳ−ＣＤＭＡシステムと互換性があり、本発明によるソート処理を実施可能な受信機６０のブロック図を、概略的に第４図に示す。実際の実施形態では、使用する受信機は、４パス（即ち、４−「フィンガ」）ＲＡＫＥ受信機である。その概略的な構造は当技術では既知である。第４図に示すように、受信機６０は、上述の４−フィンガＲＡＫＥ受信機の内１個のフィンガのみを示す。第４図を参照すると、アンテナ６２が信号６１を受信し、次にＲＦダウンコンバータ／サンプラ６３に入力する。ＲＦダウンコンバータ／サンプラ６３は既知の技法を用いて受信信号６１を処理し、受信信号６１のオーバーサンプルされた（例えば、８倍にオーバーサンプルされた）ベースバンド表現６５を得る。ベースバンド表現６５は、ディスプレッダ（despreader）６４に入力され、当技術では既知のようにロング・コードＰＮシーケンスならびにＩおよびＱ  ＰＮシーケンスを用いて、オフセットＱＰＳＫプロセスを逆に行う。ディスプレッドされた信号６７は、高速ハダマード変換（ＦＨＴ）６６に入力され、６４個の受信ウォルシュ・インデックスの適切な群を、６４個の可能なウォルシュ・インデックスの各々に対して相関付ける。ＦＨＴ６６の出力は、近最尤シーケンス予測器（Ｎ−ＭＬＳＥ：Near-Maximum Likelihood Sequence Estimator）６８に有力され、ＰＣＧ１０２の各ウォルシュ・シンボル１１２に対して、どのウォルシュ・インデックスが送信されたのかについて（ＩおよびＱの大きさに基づいて）予測しようとする。Ｎ−ＭＬＳＥ６８によって出力される予測情報は、デコーダ７０に入力され、ここで送信信号３７内の情報が再構成される。デコーダ７０の出力データ７２は、更に処理を受け、最終的に、音声データ，ファックス・データ等の形状で、エンド・ユーザに提示される。
本発明によるソート処理を用いた、第４図のＮ−ＭＬＳＥブロック６８によって実行される、Ｎ−ＭＬＳＥ予測の技法については、第５図を参照すれば最良に説明される。第５図を参照すると、６個のウォルシュ・シンボル（ＷＳ０ないしＷＳ５）が、ＰＣＧ１０２において送信されたウォルシュ・シンボルを表わす（第３図に示したように）。ＰＣＧ１０２の最初のウォルシュ・シンボルＷＳ０について、高速ハダマ−ド変換（ＦＨＴ）を用いて６４進ウォルシュ・シンボルを変換し、（これも各ウォルシュ・シンボル０ないし６３について）Ｉ＆Ｑベクトルを二乗し、Ｉ2およびＱ2のベクトルとベクトル加算することによって、（各ウォルシュ・インデックス０ないし６３に対して）各ベクトルＩおよびＱのエネルギを計算する。次に、フィンガの（全ての可能なインデックスに対する）エネルギ・ベクトルを結合し、結合エネルギ・ベクトルから、１組の残存ウォルシュ・インデックスを選択する。好適実施例では、８個の残存ウォルシュ・インデックスに対するデータをセーブするが、いずれの数のウォルシュ・インデックスでも、残存インデックスとして使用可能である。セーブされた８個の残存ウォルシュ・インデックスに対するデータは、ＦＨＴによって変換された後のＩ＆Ｑの大きさ，および８個の最良のインデックスのウォルシュ・インデックスを含む。８個の最良のインデックスは、残存パス履歴を表わすものでもある。第５図を参照すると、（ＷＳ０に対する）８個の残存インデックスが、ＳＵＲＶ０と表記された列に記憶される。８個の残存インデックスのＩ＆Ｑの大きさは、ＲＡＫＥのフィンガ各々に対する、蓄積Ｉ＆Ｑベクトルであり、次のトレリス計算（trellis calculation）において使用される。
この時点において、ＰＣＧ１０２の未だ処理すべきウォルシュ・シンボル１１２（第５図に示すＷＳ１ないしＷＳ５）は、ベクトル回転され、あらゆる周波数オフセットを除去する。ＷＳ１のＩ＆Ｑデータを回転した後、（ＳＵＲＶ０からの）８個の残存Ｉ＆Ｑベクトルの各々を、ＷＳ１内に位置する回転６４進複素ベクトルの各インデックスの大きさと加算する。その結果は、８ｘ６４（即ち５１２）個の全エネルギを総計したエネルギの新しいリストとなる。これらのエネルギをソートし、（全５１２個の内）８個の最も大きなエネルギをＳＵＲＶ１にセーブする。
ベクトルを回転し、生き残ったＩ＆Ｑ値に回転したＩ＆Ｑベクトルを加算し、パス・エネルギを計算し、エネルギに基づいてソート処理を行うプロセスは、列ＳＵＲＶ２ないしＳＵＲＶ５が満たされるまで、ＷＳ２ないしＷＳ５に対して継続される。ＰＣＧ１０２の終端において、（残存する列ＳＵＲＶ０ないしＳＵＲＶ５の各々からの）エネルギが最も高いパスは、このＰＣＧの間に送信された６個のウォルシュ・シンボルを表わす。
先に述べたように、ブロック６８にＮ−ＭＬＳＥを実施するアルゴリズムは、遷移エネルギ・メトリックの計算の間、即ち、残存パス間の可能な遷移の各々のエネルギ、およびフィンガに対する新しいウォルシュ・シンボルの各インデックスを計算している時間間隔の間に、殆どのサイクルを消費する。
本発明による８個の残存インデックスに対するソート処理を達成するための回路実施形態を、第６図に概略的に示す。Ｎ−ＭＬＳＥアルゴリズムは、ＰＣＧ１０２の開始時に起動される。４個のフィンガ（４個の別個の受信機６０を用いて実施する）の各々に対する６４進Ｉ＆Ｑの大きさを、４個の６４進ＦＨＴベクトルＲＡＭ１４０に記憶する。Ｎ−ＭＬＳＥ復調の実施形態は、複合データ・パスを含む。複合パスの一方の分岐路１４１を第６図に示す。最初のウォルシュ・シンボル（ＷＳ０）１１２を処理し、第５図にＳＵＲＶ０として示す８個の残存インデックスが得られた後、これら８個の残存インデックスを第６図の残存ソータ１５８内に記憶する。６４進ＦＨＴベクトルＲＡＭ１４０のアドレシングを行い、インデックス（ｎ）に対するＦＨＴ変換後のＩ＆Ｑデータの符号付きの大きさを、ＲＡＫＥの４個のフィンガ全てについて読み出す。
新たなＰＣＧ１０２の最初の処理のために、インデックス（Ｏ）のＦＨＴ変換Ｉ＆Ｑデータを、ＲＡＫＥの４個のフィンガについて読み出す。４個のフィンガに対する中間蓄積ＩベクトルおよびＦＨＴ変換Ｉデータは、一時的に記憶部１４６に記憶される（Ｑに対する同一情報は記憶部１４８に記憶される）。中間蓄積パス履歴は、記憶部１５０に一時的に記憶される。（一時的）記憶時間は、ＲＡＫＥの４個のフィンガの結合エネルギを計算するのにかかる時間である。４個のＲＡＫＥの（残存インデックスおよび可能な６４個のインデックス間の可能な遷移の各々に対する）エネルギは、１１４に記憶されているウォルシュ・インデックスＩおよびＱの大きさ全体の、前述のＩおよびＱベクトルの加算から、ポイント１５３ないし１５６において計算する。この計算は、当業者が認めるような、マイクロプロセッサまたは特定用途集積回路（ＡＳＩＣ）によって実行することができる。インデックスに対する４個のエネルギを加算し、チップの結合エネルギを生成する。ＲＡＫＥの４個のフィンガに対するインデックスの結合エネルギは、残存ソータ１５８に提示される。
残存ソータ１５８は、レジスタ１６０および比較回路１６２を含む素子から成る。残存ソータ１５８の素子は、マルチポートＤフリップフロップまたはマルチポート・ラッチとして実施することができる。８個のレジスタ１６０は、そのウォルシュ・インデックス１１４に対するメトリック（例えば、蓄積パス、蓄積Ｉベクトル、蓄積Ｑベクトル、およびパス履歴のエネルギ）を含む。各ＰＣＧ１０２の開始において、メトリックはゼロとされる（リセット）。これは最初のエネルギ計算であるので、ソータは、新しい結合エネルギを、ソータ・アドレス０ないし７にある以前のエネルギと比較する。残存ソータ１５８は、当該残存ソータ１５８に記憶されている現結合エネルギよりも大きな最初のソータ・アドレスに、エネルギ，蓄積ＩおよびＱベクトル，ならびに蓄積パス履歴を記憶する。そのアドレスにおける現エネルギおよび残存ソータ１５８の内容（ならびに、それより低いアドレスにおけるエネルギおよびソータの内容）を、残存ソータ１５８内の１つ下のアドレスにプッシュする。ウォルシュ・シンボルの最初のインデックス１１４に対して、蓄積パス・エネルギ，蓄積Ｉベクトル，蓄積Ｑベクトル，および蓄積パス履歴があり、アドレス０のソータに記憶されている。このプロセスは、以下に述べるように、ＰＣＧ１０２の最初のウォルシュ・シンボル（ＷＳ０）の残り６３個のインデックスに対して継続される。
次の可能なインデックスに対するエネルギがレジスタ１５５に蓄積されている間に、レジスタ１５６内のエネルギを（比較器１６２によって）レジスタ１６０内に蓄積されている全てのエネルギと比較する。この比較の結果、残存ソータ１５８のどこに新しいメトリックを挿入すべきかを示すベクトルが得られる。例えば、レジスタ１５６内のエネルギがレジスタ１６０のレジスタｂ4ないしｂ7内の蓄積エネルギよりも大きい場合、０から７までの番号の比較器の出力との比較ベクトルは、例えば００００１１１１となる。比較ベクトルのビット０は、先頭が０であることを暗示していることを注記しておく。０値を有する比較ベクトルは、残存ソータ１５８の素子がその現内容を保持していることを示す。比較ベクトルビットｎ−１およびビットｎにおける０から１への遷移は、素子ｎを素子ｎ−１内の残存メトリックで更新すべきことを示す。最初のウォルシュ・シンボル（ＷＳ０）の終端において、８個の残存インデックス（最も高いエネルギを有するインデックス）およびそれらに関連するメトリックを、残存ソータ１５８においてランク順に並べ替える。この時点で、残存インデックスに対する蓄積Ｉベクトル，蓄積Ｑベクトル，および蓄積パス履歴は、残存ソータ１５８から記憶部１４２に転送される。
ＰＣＧ１０２の２番目のウォルシュ・シンボル（ＷＳ１）に対して、回転され変換されたＩ＆Ｑベクトルが、ＦＨＴベクトルＲＡＭ１４０に記憶される。８個の蓄積インデックスの各々に対して、蓄積ＩおよびＱベクトルを、フィンガ毎に、ＷＳ１の６４個の回転され変換されたＩ＆Ｑベクトルの各々と加算する。各フィンガに対して可能なパス各々のエネルギ、および可能なインデックス各々に対する結合エネルギを計算する。ＷＳ２の終端において、最も高い蓄積エネルギを有する８個のインデックスからのデータ（蓄積エネルギ，蓄積Ｉベクトル，蓄積Ｑベクトルおよび蓄積パス履歴）を、残存ソータ１５８内に記憶し、次いで記憶部１４２に転送する。
上述のプロセスは、ＰＣＧ１０２のウォルシュ・シンボルＷＳ２ないしＷＳ５に対して継続される。ＰＣＧ１０２の終了時において、最も大きな蓄積パス蓄積エネルギを有する残存経路は、残存ソータ１５８のアドレス０にある。この素子は、ＰＣＧ１０２の間に送信された６個のウォルシュ・シンボルのパスを含む。
残存ソータ１５８は、ＦＨＴブロック６６およびポイント１５２ないし１５６におけるエネルギの計算と（ほぼ）並列に動作し、本発明にしたがって少ないサイクルで効率的にソーティングを行い、比較および残存ソート処理は、Ｎ−ＭＬＳＥ６８を駆動する全体的な状態機械に同期する。この実施形態では、Ｎ−ＭＬＳＥパス（第６図のポイント１５５において見られるように）に対する新しい結合エネルギは、各４サイクル毎に計算することができる。残存ソータ処理には２サイクルを要するに過ぎない。即ち、比較器１６２における比較に１サイクルおよびレジスタ１６０における残存ソート処理に１サイクルである。その結果、全てのパス計算の終了時に追加のソート処理を行う必要はなく、データをソート処理のために記憶する追加のＲＡＭも不要となる。
以上本発明について、特定の実施例を参照しながら特定して示しかつ説明したが、本発明の精神および範囲から逸脱することなく、その形態および詳細において種々の変更が可能であることは、当業者には理解されよう。以下に記載する請求の範囲における全ての手段または段階プラス機能要素の対応する構造，材料，作用，および均等物は、具体的に特許請求する他の請求項の要素と組合わてその機能を行うためのあらゆる構造，材料，または行為を含むことを意図するものである。
【図１】
0003710821.tif 000002
【図４】
0003710821.tif 000003
【図２Ａ】
0003710821.tif 000004
【図２Ｂ】
0003710821.tif 000005
【図３】
0003710821.tif 000006
【図５】
0003710821.tif 000007
【図６】
0003710821.tif 000008