(57)【要約】【課題】  この発明は、数値の集合から、最大値または最小値を算出する方法に関し、比較演算の実行後において、その結果が、最大値または最小値自身および／またはそれに対応するインデックスから構成される、最大値または最小値を算出する方法を提示することを課題とする。【解決手段】  この課題は、この発明にもとづき、最初の措置において、比較値毎に、この比較値とこれに対応するインデックスとから構成される一つの比較ワードｘ(k) を生成する形で、各比較値に対して、一つのインデックスを割り当てて、これらの比較ワードｘ(k) の集合から、最大値または最小値を算出し、それに続いて少なくとも、この最大値または最小値に対応するインデックスを出力することにより解決される。
2006505017.tif 000002
【特許請求の範囲】
【請求項１】
比較値の集合から、最大値または最小値を算出するための方法において、
最初の措置において、比較値毎に、この比較値（１）とこれに対応するインデックス（２）とから構成される一つの比較ワードｘ(k) （３）を生成する形で、各比較値（１）に対して、一つのインデックス（２）を割り当てて、これらの比較ワードｘ(k) （３）の集合から、最大値または最小値を算出し、それに続いて少なくとも、この最大値または最小値に対応するインデックス（２）を出力することを特徴とする方法。
【請求項２】
比較ワードｘ(k) （３）は、二進数の形式で、規則ｘ(k) ＝２m ＊ｃ(k) ＋ｋにもとづき生成され、その際ｃ(k) は、比較値（１）であり、ｋは、比較値（１）のインデックス（２）であり、ｎは、比較値（１）の数値であり、ｍは、シフトさせる桁数であり、そして関係式２m ≧ｎが成り立つことを特徴とする請求項１に記載の方法。
【請求項３】
生成されたすべての比較ワード（３）による比較演算の結果において、最大値または最小値のインデックス（２）が、比較ワードｘ(k) （３）の下位のｍビットに含まれており、そこから読み出されることを特徴とする請求項１または２に記載の方法。
【請求項４】
当該の最大値または最小値が、インデックスを付与されているすべての比較値をソートしたシーケンスから算出されることを特徴とする請求項１または２に記載の方法。
【請求項５】
当該のソートしたシーケンスが、出力されることを特徴とする請求項４に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、比較値の集合から最大値または最小値を算出する方法に関する。
【背景技術】
【０００２】
数の極値、すなわち数値の集合の最大値または最小値は、基本的に二つの異なる観点にもとづき算出することができる。
【０００３】
一つには、特許文献１に記載されているとおり、この目的のために特別に設計された回路構造を用いて、ハードウェアにより、この算出を実現することができる。
【０００４】
この回路構造は、８つの要素から成る比較値の集合における最大値と最小値を同時に算出することを実現している。
【０００５】
この構造では、互いに平行に配置された第一段のスイッチの各々に、二つの比較値が供給される。比較演算の結果、比較値の中のそれぞれより大きいものがスイッチの最大値の出力端子に、それぞれより小さいものが最小値の出力端子に置かれる。
【０００６】
これらの第一段の出力値は、示されている接続に応じて、第二段に示されているスイッチに対する入力値となる。
【０００７】
この点において、この構造は、複数のスイッチの多段接続である。
【０００８】
第二段においても、各スイッチでは、置かれている両方の入力値の比較とその結果の第三段への相応の伝達が行われ、その際スイッチ毎に、単に最小値または最大値だけが、それに続く第三段の二つのスイッチの入力に送られる。
【０００９】
第三段の出力において、一方には最大値が、他方には最小値が取り出される。
【００１０】
最大値または最小値を算出する第二の方法は、ソフトウェアにより実現することである。この場合、各ハードウェアに適合した比較および／またはソートアルゴリズムが利用される。
【００１１】
この範疇の方法は、例えば以下のとおり実現される。処理ユニットの二つの入力レジスタに、比較値集合の中の最初の二つの比較値を読み込む。処理ユニットにより、二つの値の比較が行われる。最大値を算出する場合、より大きい方の値が出力レジスタに置かれる。次に、大きさに従って配置する形で、二つの比較値の順序テーブルへの登録を行う。
【００１２】
その次の措置において、前述した出力レジスタの値を、処理ユニットの第一入力レジスタに読み込む。第二入力レジスタには、比較のために待機していた第三の値が書き込まれる。これに続いて、二つの値を処理ユニットで比較して、それまでの最大値に対して、第三の比較値がどのような関係にあるのかが決定される。
【００１３】
第三の比較値が、新しい最大値として算出された場合には、既に順序テーブルに書き込まれている比較値の位置を一つずつ後ろにずらすとともに、第三の比較値を第一位のテーブル位置に書き込むことが行われる。
【００１４】
第三の比較値が、それまでに算出された最大値より小さい場合には、別の比較措置において、順序テーブルに書き込まれている第二位の値に対して、第三の比較値がどのような関係にあるのかを調べなければならない。
【００１５】
比較の結果において、第三の比較値がより大きいことが確定した場合、テーブルに登録されている第二位の値と場合によってはそれに続く値を後ろにずらして、その空いたテーブル位置に第三の比較値を登録しなければならない。
【００１６】
比較により、第三の比較値がより小さいという結果が出た場合、第三位の位置にまだ何も値が登録されていない時には、その値の第三位のテーブル位置への登録が行われる。このテーブル位置への登録が存在する際には、登録しようとしている値の登録されている値との比較が再度行われて、その比較結果に応じた措置が必要となる。
【００１７】
この比較が完了した場合、第一入力レジスタには、その時点の最大値が、第二入力レジスタには、第四の比較値が読み込まれて、前述したとおり、比較とソートが新たにスタートする。
【００１８】
最大値または最小値以外に、その他のすべての比較値も、順序テーブル内において、常にアクセス可能な状態にしておかなければならないので、この方法は、純粋な最大値または最小値計算と比べて負担がより大きい。
【００１９】
この方法は、シリアル法と呼ぶことができ、その方法では、比較値の数が増えるほどに、比較とソートの負担が益々増大する。そのような方法での比較は、しばしば所謂「If-Then-Else」分岐を用いて実現される。これに必要な一連の分岐は、現在の信号プロセッサにおける情報処理を著しく非効率なものとしてしまう。
【００２０】
別のソフトウェアにより実現する方法は、並列処理ユニットを用いたプロセッサ構成に関する方法として、例えば特許文献２で知られている。
【００２１】
この方法では、すべての並列に配置された処理ユニットの入力レジスタには、最初の比較値ペアが書き込まれる。それに続く処理ユニットの比較演算、例えば最大値の算出では、二つの比較値の中の、それぞれより大きいものが出力レジスタに書き込まれる。
【００２２】
１回目の比較における比較結果は、再度比較値ペアとして組み合わされて、処理ユニットの入力レジスタに書き込まれ、その際この二回目の比較措置に対して必要な処理ユニットの数が半減している。
【００２３】
それに続く演算においては、再び二つの比較値の中の最大値が算出されて、それぞれ出力レジスタに書き込まれる。
【００２４】
この場合、各比較演算により、比較値の数は半減して行く、すなわち前述したとおり、確定的な最大値が算出されるまで、比較演算を、絶えず繰り返されなければならない。そのように、例えば８個の並列処理ユニットと１６個の比較値との構成の場合、結果を算出するには、順々に連続する４回の比較演算が必要である。
【００２５】
スペクトル拡散技術（例えば、ワイヤレスＬＡＮ、ＣＤＭＡ、ＵＭＴＳ／３ＧＰＰ）に準拠する伝送方式に対する受信機では、復調の際に、通常先ず受信信号の既知のシーケンスとの相関が取られて、それに続いてこれらの相関の中の最大値の算出が行われる。この場合、最大値の値よりは、むしろその位置またはインデックスに関心が寄せられ、それは、それらによって、最も良く適合するシーケンスとそれによって伝送された情報を検出することができるためである。
【００２６】
これらの記載したすべての方法では、結果として、最大値または最小値が出力される。しかし、比較方法の終了後において、最大値または最小値のインデックスは、提供されていない。
【特許文献１】特開平４−１２３１２８号公報
【特許文献２】ドイツ特許公開第１９８３５２１６号明細書
【発明の開示】
【発明が解決しようとする課題】
【００２７】
そのため、この発明の課題は、比較演算を実行した後において、その結果が最大値または最小値自身および／またはそれに対応するインデックスから構成される、最大値または最小値を算出する方法を提示することである。
【課題を解決するための手段】
【００２８】
この課題は、この発明にもとづき、最初の措置において、比較値毎に、この比較値とこれに対応するインデックスとから構成される一つの比較ワードｘ(k) を生成する形で、各比較値に対して、一つのインデックスを割り当てて、これらの比較ワードｘ(k) の集合から、最大値または最小値を算出し、それに続いて少なくとも、この最大値または最小値に対応するインデックスを出力することにより解決される。
【００２９】
従来の技術において行われているとおり、比較段階または比較演算に対して、比較値だけが提供される場合、その結果には、確かに比較の最大値または最小値は存在するが、当初の位置または比較値のインデックスに関する指標は存在しない。これを提示可能とするためには、本来の比較に影響を与えることなく、異なる比較段階または比較演算に渡って、インデックスを持ち回らなければならない。最大値または最小値の算定が行われた後に、再び比較値からインデックスを分離するようにすることができる。
【００３０】
インデックスの比較値とのリンケージを実現するために、この発明では、二つの部分から成る比較ワードを生成している。この比較ワードは、一つの部分に比較値自身を、その他の部分に、それに対応するインデックスを有する。
【００３１】
この方法の有利な実施形態においては、比較ワードｘ(k) は、二進法で、規則ｘ(k) ＝２m ＊ｃ(k) ＋ｋにもとづき生成されるものと規定され、その際ｃ(k) は、比較値であり、ｋは、比較値のインデックスであり、ｎは、比較値の数値であり、ｍは、シフトさせる桁数であり、そして関係式２m ≧ｎが成り立つ。
【００３２】
この比較ワードの特別な表記形式は、プロセッサレベルでのデータ処理の記述に対して好適な二進形式である。この比較ワードは、二つの構成部分から構成されている。比較ワードの上位の部分には、比較値が、下位の部分には、それに対応したインデックスが格納されている。こうすることによって、各部分に必要なビット桁数を、比較値の集合、比較値の精度およびプロセッサシステムの処理ビット長に適合させることができる。比較ワードｘ(k) の生成は、最初の措置において、この比較ワードを所定のビット桁数ｍだけ左にシフトする形で、前記の式に従って実行される。この演算に対しては、式の第一項が関係する。次に、第二の措置では、比較値のインデックスが、同じく２進数の形で加算される。
【００３３】
この発明の有利な実施構成においては、生成されたすべての比較ワードによる比較演算の結果において、最大値または最小値のインデックスは、比較ワードｘ(k) の下位のｍビットに含まれており、そこから読み出されるものと規定される。
【００３４】
比較値のインデックスは、比較ワードｘ(k) の生成後には、下位のｍビットに含まれている。これらのインデックスの位置は、比較方法によって損なわれることがなく、その結果最大値または最小値の算定後に、下位のｍビットを、比較ワードｘ(k) から分離して、結果として出力することができる。
【００３５】
この方法の別の有利な実施形態においては、最大値または最小値は、インデックスを付与されているすべての比較値をソートしたシーケンスから算出するものと規定する。
【００３６】
従来の技術に記載されている、ソフトウェアにもとづくソート方法を用いて、インデックスを付与されている比較値を、昇順または降順で順序テーブルに登録することができる。このテーブルから、最初のまたは最後の比較ワードが、すなわちインデックスを付与されている最大値または最小値が出力される。
【００３７】
この方法の別の有利な実施構成においては、ソートされたシーケンスを出力するものと規定される。
【００３８】
インデックスを付与されている最大値または最小値を出力すること以外に、所定の数の比較ワードを順序テーブルから出力することもできる。この場合、比較ワードの代わりに、比較値だけまたはインデックスだけを出力することも可能である。
【発明を実施するための最良の形態】
【００３９】
以下においては、実施例にもとづき、この発明をより詳しく説明する。添付図面には、比較ワードの生成法が、個々の措置毎に描かれている。
【００４０】
スペクトル拡散技術により動作する受信機段（例えば、ＲＡＫＥ受信機）では、先行するプロセスにおいて、符号セットの可能なすべてのシンボルと受信シンボルとの比較が行われる。この比較により、ＲＡＫＥ受信機の出力値として、所謂相関値または比較値が生成される。この一致検査後には、相関における最大値を算出しなければならず、その場合その値は、受信したシンボルと最大の一致を示すとともに、受信シンボル自身の推定を可能とするものである。
【００４１】
そのために、比較値１とそれに対応するインデックス２から、比較ワード３を生成する。最初の措置において、二進数の比較値ｃ(k) １（図１ａ）が、ｍビット左にシフトされ、その際ｍは、インデックス２に対して必要なビット桁数と定められ、例えば４である。シフト操作の実行後には、図１ｂに描かれている暫定的な比較ワード３が生成される。
【００４２】
次の措置においては、従属請求項２の生成式にもとづき、例えば４桁の、対応する二進数のインデックス２が、それまでの比較ワード３に加算される。この生成例では、インデックスは、値３（二進数で００１１）を有する。下位の４つのビット桁は、すべて零なので、この加算は、これらのビット桁にインデックス２を単に投入するものと解釈することもできる。
【００４３】
このようにして、比較ワード３が生成される。上位のビット桁に含まれる比較値１は、これらのビット桁がより大きな重みを持っていることにより、比較演算の結果を決定付けるものなので、これに続く比較は、インデックス２を下位のビット桁に付加することによって影響を受けることはない。
【００４４】
比較演算自体は、例えば８つの処理ユニットを並列に配置したプロセッサー構成を用いて実現することができる。各処理ユニットは、２つの入力レジスタを有し、これらのレジスタには、合計１６個の比較ワード３が書き込まれる。これに続く比較措置において、各処理ユニットが、置かれている比較ワードペアの最大値を決定して、より大きな比較ワード３を出力レジスタに書き込む。この比較措置の後では、最大値に関して対象となっている比較ワード３の数が半減している。次の措置では、８つの中間的な最大値から、比較ワードペアが新たに生成されて、これらは、再び処理ユニットの入力レジスタに書き込まれる。これに続く比較演算に関しては、僅かに４つの処理ユニットだけが必要である。その結果、これらのペアの中のより大きな比較ワード３が生成されて、これらは、再び出力レジスタに書き込まれる。これらの比較演算は、最終的な最大値が確定するまで行われる。
【００４５】
比較演算の終了後には、比較値１の中の最大値が、比較ワード３の形式で決定される。この比較ワード３から、下位の４つのビット桁が、読み出されて、これに続く受信機の一連の作業または情報決定に対するインデックス２として提供される。
【図面の簡単な説明】
【００４６】
【図１】比較ワードの生成に関する個々の措置の図
【符号の説明】
【００４７】
１    比較値ｃ(k) 
２    比較値ｃ(k) のインデックス
３    比較ワードｘ(k) 
【図１ａ】
2006505017.tif 000003
【図１ｂ】
2006505017.tif 000004
【図１ｃ】
2006505017.tif 000005
【図１ｄ】
2006505017.tif 000006
【手続補正書】
【提出日】平成16年8月24日(2004.8.24)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
スペクトル拡散技術の分野での通信受信機において、比較値の集合から、最大値または最小値を算出するための方法であって、この方法では、受信信号から、スペクトル拡散技術を用いて符号化されている受信シンボルを復号化して、受信機の符号セットと比較し、そして各比較の結果において、比較値が生成され、その際比較値毎に、この比較値（１）とこれに対応するインデックス（２）とから構成される一つの比較ワードｘ(k) （３）を生成する形で、各比較値（１）に対して、一つのインデックス（２）を割り当てて、これに続いて、これらの比較ワードｘ(k) （３）の集合から、最大値または最小値を算出する方法において、最大値または最小値を算出した後に、これらのインデックス（２）を用いて、この符号セットの中から、この最大値または最小値を生成する元となったシンボルを出力することを特徴とする方法。
【請求項２】
比較ワードｘ(k) （３）は、二進数の形式で、規則ｘ(k) ＝２m ＊ｃ(k) ＋ｋにもとづき生成され、その際ｃ(k) は、比較値（１）であり、ｋは、比較値（１）のインデックス（２）であり、ｎは、比較値（１）の数値であり、ｍは、シフトさせる桁数であり、そして関係式２m ≧ｎが成り立つことを特徴とする請求項１に記載の方法。
【請求項３】
生成されたすべての比較ワード（３）による比較演算の結果において、最大値または最小値のインデックス（２）が、比較ワードｘ(k) （３）の下位のｍビットに含まれており、そこから読み出されることを特徴とする請求項１または２に記載の方法。
【請求項４】
当該の最大値または最小値が、インデックスを付与されているすべての比較値をソートしたシーケンスから算出されることを特徴とする請求項１または２に記載の方法。
【請求項５】
当該のソートしたシーケンスが、出力されることを特徴とする請求項４に記載の方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】      明細書
【技術分野】
【０００１】
この発明は、スペクトル拡散技術の分野での通信受信機において、比較値の集合から最大値または最小値を算出する方法に関し、この発明の方法では、受信信号から、スペクトル拡散技術を用いて符号化されている受信シンボルを復号化して、受信機の符号セットと比較し、そして各比較の結果において、比較値が生成され、その際比較値毎に、この比較値とこれに対応するインデックスとから構成される一つの比較ワードを生成する形で、各比較値に対して、一つのインデックスを割り当てて、これに続いてこれらの比較ワードの集合から、最大値または最小値を算出している。
【背景技術】
【０００２】
数の極値、すなわち数値の集合の最大値または最小値は、基本的に二つの異なる観点にもとづき算出することができる。
【０００３】
一つには、特許文献１に記載されているとおり、この目的のために特別に設計された回路構造を用いて、ハードウェアにより、この算出を実現することができる。
【０００４】
この回路構造は、８つの要素から成る比較値の集合における最大値と最小値を同時に算出することを実現している。
【０００５】
この構造では、互いに平行に配置された第一段のスイッチの各々に、二つの比較値が供給される。比較演算の結果、比較値の中のそれぞれより大きいものがスイッチの最大値の出力端子に、それぞれより小さいものが最小値の出力端子に置かれる。
【０００６】
これらの第一段の出力値は、示されている接続に応じて、第二段に示されているスイッチに対する入力値となる。
【０００７】
この点において、この構造は、複数のスイッチの多段接続である。
【０００８】
第二段においても、各スイッチでは、置かれている両方の入力値の比較とその結果の第三段への相応の伝達が行われ、その際スイッチ毎に、単に最小値または最大値だけが、それに続く第三段の二つのスイッチの入力に送られる。
【０００９】
第三段の出力において、一方には最大値が、他方には最小値が取り出される。
【００１０】
最大値または最小値を算出する第二の方法は、ソフトウェアにより実現することである。この場合、各ハードウェアに適合した比較および／またはソートアルゴリズムが利用される。
【００１１】
この範疇の方法は、例えば以下のとおり実現される。処理ユニットの二つの入力レジスタに、比較値集合の中の最初の二つの比較値を読み込む。処理ユニットにより、二つの値の比較が行われる。最大値を算出する場合、より大きい方の値が出力レジスタに置かれる。次に、大きさに従って配置する形で、二つの比較値の順序テーブルへの登録を行う。
【００１２】
その次の措置において、前述した出力レジスタの値を、処理ユニットの第一入力レジスタに読み込む。第二入力レジスタには、比較のために待機していた第三の値が書き込まれる。これに続いて、二つの値を処理ユニットで比較して、それまでの最大値に対して、第三の比較値がどのような関係にあるのかが決定される。
【００１３】
第三の比較値が、新しい最大値として算出された場合には、既に順序テーブルに書き込まれている比較値の位置を一つずつ後ろにずらすとともに、第三の比較値を第一位のテーブル位置に書き込むことが行われる。
【００１４】
第三の比較値が、それまでに算出された最大値より小さい場合には、別の比較措置において、順序テーブルに書き込まれている第二位の値に対して、第三の比較値がどのような関係にあるのかを調べなければならない。
【００１５】
比較の結果において、第三の比較値がより大きいことが確定した場合、テーブルに登録されている第二位の値と場合によってはそれに続く値を後ろにずらして、その空いたテーブル位置に第三の比較値を登録しなければならない。
【００１６】
比較により、第三の比較値がより小さいという結果が出た場合、第三位の位置にまだ何も値が登録されていない時には、その値の第三位のテーブル位置への登録が行われる。このテーブル位置への登録が存在する際には、登録しようとしている値の登録されている値との比較が再度行われて、その比較結果に応じた措置が必要となる。
【００１７】
この比較が完了した場合、第一入力レジスタには、その時点の最大値が、第二入力レジスタには、第四の比較値が読み込まれて、前述したとおり、比較とソートが新たにスタートする。
【００１８】
最大値または最小値以外に、その他のすべての比較値も、順序テーブル内において、常にアクセス可能な状態にしておかなければならないので、この方法は、純粋な最大値または最小値計算と比べて負担がより大きい。
【００１９】
この方法は、シリアル法と呼ぶことができ、その方法では、比較値の数が増えるほどに、比較とソートの負担が益々増大する。そのような方法での比較は、しばしば所謂「If-Then-Else」分岐を用いて実現される。これに必要な一連の分岐は、現在の信号プロセッサにおける情報処理を著しく非効率なものとしてしまう。
【００２０】
別のソフトウェアにより実現する方法は、並列処理ユニットを用いたプロセッサ構成に関する方法として、例えば特許文献２で知られている。
【００２１】
この方法では、すべての並列に配置された処理ユニットの入力レジスタには、最初の比較値ペアが書き込まれる。それに続く処理ユニットの比較演算、例えば最大値の算出では、二つの比較値の中の、それぞれより大きいものが出力レジスタに書き込まれる。
【００２２】
１回目の比較における比較結果は、再度比較値ペアとして組み合わされて、処理ユニットの入力レジスタに書き込まれ、その際この二回目の比較措置に対して必要な処理ユニットの数が半減している。
【００２３】
それに続く演算においては、再び二つの比較値の中の最大値が算出されて、それぞれ出力レジスタに書き込まれる。
【００２４】
この場合、各比較演算により、比較値の数は半減して行く、すなわち前述したとおり、確定的な最大値が算出されるまで、比較演算を、絶えず繰り返されなければならない。そのように、例えば８個の並列処理ユニットと１６個の比較値との構成の場合、結果を算出するには、順々に連続する４回の比較演算が必要である。
【００２５】
スペクトル拡散技術（例えば、ワイヤレスＬＡＮ、ＣＤＭＡ、ＵＭＴＳ／３ＧＰＰ）に準拠する伝送方式に対する受信機では、復調の際に、通常先ず受信信号の既知のシーケンスとの相関が取られて、それに続いてこれらの相関の中の最大値の算出が行われる。この場合、最大値の値よりは、むしろその位置またはインデックスに関心が寄せられ、それは、それらによって、最も良く適合するシーケンスとそれによって伝送された情報を検出することができるためである。
【００２６】
これらの記載したすべての方法では、結果として、最大値または最小値が出力される。しかし、比較方法の終了後において、最大値または最小値のインデックスは、提供されていない。
特許文献３により、ソート技法による方法が開示されており、その方法は、プログラムの実行の際に、比較または分岐ステートメントを必要とせず、特に複数の並列機能ユニットを有するコンピュータに好適である。
比較および／または分岐ステートメントに代わって、算術ステートメントを用いて、二つの数値または二つの二進数の文字ストリングのソートを実現している。これによって、スーパースカラプロセッサおよびＶＬＩＷを処理するプロセッサの処理能力を改善することができる。
更に、ＲＩＳＣプロセッサの縮小命令セットを利用した場合、このソート技法により、浮動小数点型計算をより良好に使用することができる。このソート技法では、二進数の文字ストリングをソートするために、データの浮動小数点型表示と浮動小数点型ステートメントが許されている。
請求項１にもとづき、二つの数値ａとｂの最大値／最小値を算出するために、最初の措置において、中間的な結果ｅとｆを生成している。
これらの中間的な結果ｅとｆは、それに続いて加法演算および減法演算に供給され、これらの演算によって、結果がそれぞれ半減している。そのため、加法演算の結果は、比較対象の二つの数値ａとｂの中の最大値を示しており、その際減法演算の結果は、比較値の中の最小値を提供している。
二進数の文字ストリングのインデックスを保持しつつ、このソート方法で処理することを望む場合には、処理しようとしている浮動小数点型ワード内に、このインデックスを格納することができる。そのために使用する技法が、図４に描かれている。
「内部ビット（il-Bits ）」の領域は、インデックス情報をマッピングするために利用される。「５１内部ビット」の上位の領域には、ソートしようとしている二進数の文字ストリングの保存が行われている。低位のビットは、明細書の部分において、別に前述されているとおり、零に設定される。
インデックス情報は、浮動小数点型ワードの低位の部分にマッピングされるので、本来のソートプロセスは、このことによって影響を受けることはない。しかし、他方では、少なくとも付加されるインデックス情報が相違するために、ソートしようとしている文字ストリングが同等であるケースが排除されてしまう。このようにして、ソート処理後において、最大値／最小値のインデックスを算出できる可能性もある。
二進数の文字ストリングが一致する場合、ソート処理の結果は、インデックス値によって決定される。より小さなインデックスを持つ浮動小数点型ワードは、「ｃ」を割り振られて、最小値を示す一方、より大きなインデックスを持つ浮動小数点型ワードは、「ｄ」を、そのため最大値に選定される。このような順位原則は、文字ストリングが同等であるケースに対して望ましいものである。
確かに、この方法は、比較値に対応するインデックスを考慮しつつ、最大値または最小値の算出を実現しているが、依然として受信シンボルを推定することを可能とするものではない。
【特許文献１】  特開平４−１２３１２８号公報
【特許文献２】  ドイツ特許公開第１９８３５２１６号明細書
【特許文献３】  米国特許第５，７５２，０７２号明細書
【発明の開示】
【発明が解決しようとする課題】
【００２７】
そのため、この発明の課題は、比較演算を実行した後において、その結果が最大値または最小値自身および／またはそれに対応するインデックスから構成され、それによって受信シンボルを算出する、通信受信機において、比較値の集合から最大値または最小値を算出する方法を提示することである。
【課題を解決するための手段】
【００２８】
この課題は、この発明にもとづき、最初の措置において、比較値毎に、この比較値とこれに対応するインデックスとから構成される一つの比較ワードｘ(k) を生成する形で、各比較値に対して、一つのインデックスを割り当てて、これらの比較ワードｘ(k) の集合から、最大値または最小値を算出し、それに続いて少なくとも、この最大値または最小値に対応するインデックスを出力することにより解決される。
【００２９】
従来の技術において行われているとおり、比較段階または比較演算に対して、比較値だけが提供される場合、その結果には、確かに比較の最大値または最小値は存在するが、当初の位置または比較値のインデックスに関する指標は存在しない。これを提示可能とするためには、本来の比較に影響を与えることなく、異なる比較段階または比較演算に渡って、インデックスを持ち回らなければならない。最大値または最小値の算定が行われた後に、再び比較値からインデックスを分離するようにすることができる。
【００３０】
インデックスの比較値とのリンケージを実現するために、この発明では、二つの部分から成る比較ワードを生成している。この比較ワードは、一つの部分に比較値自身を、その他の部分に、それに対応するインデックスを有する。
【００３１】
この方法の有利な実施形態においては、比較ワードｘ(k) は、二進法で、規則ｘ(k) ＝２m ＊ｃ(k) ＋ｋにもとづき生成されるものと規定され、その際ｃ(k) は、比較値であり、ｋは、比較値のインデックスであり、ｎは、比較値の数値であり、ｍは、シフトさせる桁数であり、そして関係式２m ≧ｎが成り立つ。
【００３２】
この比較ワードの特別な表記形式は、プロセッサレベルでのデータ処理の記述に対して好適な二進形式である。この比較ワードは、二つの構成部分から構成されている。比較ワードの上位の部分には、比較値が、下位の部分には、それに対応したインデックスが格納されている。こうすることによって、各部分に必要なビット桁数を、比較値の集合、比較値の精度およびプロセッサシステムの処理ビット長に適合させることができる。比較ワードｘ(k) の生成は、最初の措置において、この比較ワードを所定のビット桁数ｍだけ左にシフトする形で、前記の式に従って実行される。この演算に対しては、式の第一項が関係する。次に、第二の措置では、比較値のインデックスが、同じく２進数の形で加算される。
【００３３】
この発明の有利な実施構成においては、生成されたすべての比較ワードによる比較演算の結果において、最大値または最小値のインデックスは、比較ワードｘ(k) の下位のｍビットに含まれており、そこから読み出されるものと規定される。
【００３４】
比較値のインデックスは、比較ワードｘ(k) の生成後には、下位のｍビットに含まれている。これらのインデックスの位置は、比較方法によって損なわれることがなく、その結果最大値または最小値の算定後に、下位のｍビットを、比較ワードｘ(k) から分離して、結果として出力することができる。
【００３５】
この方法の別の有利な実施形態においては、最大値または最小値は、インデックスを付与されているすべての比較値をソートしたシーケンスから算出するものと規定する。
【００３７】
従来の技術に記載されている、ソフトウェアにもとづくソート方法を用いて、インデックスを付与されている比較値を、昇順または降順で順序テーブルに登録することができる。このテーブルから、最初のまたは最後の比較ワードが、すなわちインデックスを付与されている最大値または最小値が出力される。
【００３８】
この方法の別の有利な実施構成においては、ソートされたシーケンスを出力するものと規定される。
【００３９】
インデックスを付与されている最大値または最小値を出力すること以外に、所定の数の比較ワードを順序テーブルから出力することもできる。この場合、比較ワードの代わりに、比較値だけまたはインデックスだけを出力することも可能である。
【発明を実施するための最良の形態】
【００４０】
以下においては、実施例にもとづき、この発明をより詳しく説明する。添付図面には、比較ワードの生成法が、個々の措置毎に描かれている。
【００４１】
スペクトル拡散技術により動作する受信機段（例えば、ＲＡＫＥ受信機）では、先行するプロセスにおいて、符号セットの可能なすべてのシンボルと受信シンボルとの比較が行われる。この比較により、ＲＡＫＥ受信機の出力値として、所謂相関値または比較値が生成される。この一致検査後には、相関における最大値を算出しなければならず、その場合その値は、受信したシンボルと最大の一致を示すとともに、受信シンボル自身の推定を可能とするものである。
【００４２】
そのために、比較値１とそれに対応するインデックス２から、比較ワード３を生成する。最初の措置において、二進数の比較値ｃ(k) １（図１ａ）が、ｍビット左にシフトされ、その際ｍは、インデックス２に対して必要なビット桁数と定められ、例えば４である。シフト操作の実行後には、図１ｂに描かれている暫定的な比較ワード３が生成される。
【００４３】
次の措置においては、従属請求項２の生成式にもとづき、例えば４桁の、対応する二進数のインデックス２が、それまでの比較ワード３に加算される。この生成例では、インデックスは、値３（二進数で００１１）を有する。下位の４つのビット桁は、すべて零なので、この加算は、これらのビット桁にインデックス２を単に投入するものと解釈することもできる。
【００４４】
このようにして、比較ワード３が生成される。上位のビット桁に含まれる比較値１は、これらのビット桁がより大きな重みを持っていることにより、比較演算の結果を決定付けるものなので、これに続く比較は、インデックス２を下位のビット桁に付加することによって影響を受けることはない。
【００４５】
比較演算自体は、例えば８つの処理ユニットを並列に配置したプロセッサー構成を用いて実現することができる。各処理ユニットは、２つの入力レジスタを有し、これらのレジスタには、合計１６個の比較ワード３が書き込まれる。これに続く比較措置において、各処理ユニットが、置かれている比較ワードペアの最大値を決定して、より大きな比較ワード３を出力レジスタに書き込む。この比較措置の後では、最大値に関して対象となっている比較ワード３の数が半減している。次の措置では、８つの中間的な最大値から、比較ワードペアが新たに生成されて、これらは、再び処理ユニットの入力レジスタに書き込まれる。これに続く比較演算に関しては、僅かに４つの処理ユニットだけが必要である。その結果、これらのペアの中のより大きな比較ワード３が生成されて、これらは、再び出力レジスタに書き込まれる。これらの比較演算は、最終的な最大値が確定するまで行われる。      【００４６】
比較演算の終了後には、比較値１の中の最大値が、比較ワード３の形式で決定される。この比較ワード３から、下位の４つのビット桁が、読み出されて、これに続く受信機の一連の作業または情報決定に対するインデックス２として提供される。
【図面の簡単な説明】
【００４７】
【図１】  比較ワードの生成に関する個々の措置の図
【符号の説明】
【００４８】
１    比較値ｃ(k) 
２    比較値ｃ(k) のインデックス
３    比較ワードｘ(k) 
【国際調査報告】
2006505017.tif 000007
2006505017.tif 000008
2006505017.tif 000009
2006505017.tif 000010