(57)【特許請求の範囲】
【請求項１】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する複数の呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調方法であって、
ａ）到来する呼リクエストに分配されるコードの所望のビットレートを認知し、
ｂ）所望のビットレートを持つコードの使用可能性を判断し、
ｃ）所望のビットレートの使用可能なコードが１つある場合に、該所望のビットレートの使用可能な１つのコードを前記到来する呼リクエストに分配し、
ｄ）所望の使用可能なビットレートのうち２以上のコードがある場合、使用可能な高速ビットレートのコードの総数を可能な限り多く保ってコードを優先順位付けし、将来高速ビットレートのコードを解放する可能性が最大となるように、所定の規則に従い、１つのコードを分配することを含み、
コードの優先順位付けは、
ｅ）所望のビットレートの使用可能な空きコードに連結する、長さのより短いコードの使用不可度合いを判断し、
ｆ）最も使用不可度合いが高い連結された長さのより短いコードを有する空きコードの中から、１セットのコードを選択し、
ｇ）ルートコードに達するまで、連結された長さのより短いコードに対し前段のステップをくり返し、その結果得られる１セットのコードから１つのコードを最終的に選択することにより行われる方法。
【請求項２】
伝送容量を超過する場合には、到来したリクエストを別のコード構造に割り当てることをさらに含む請求項１に記載の方法。
【請求項３】
前記到来する呼リクエストにより伝送容量を超過する場合には、到来する呼リクエストをブロックすることをさらに含む請求項１に記載の方法。
【請求項４】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調方法であって、
ａ）到来する呼リクエストに分配されるコードのレートを認知し、
ｂ）所望されるビットレートを持つ単数又は複数のコードの使用可能性を判断し、
ｃ）所望されるビットレートのコードが使用可能でない場合、到来するリクエストを使用不可コードに割り当て、連結された使用済みの低速ビットレートを再分配することによってコードの再分配を実施し、割り当て済みの使用不可コードを解放することを含み、
再分配に好ましい使用不可コードとして、そのサブツリー内に最少の割り当て済みの低速ビットレートのコードを有するものを選択し、そのような使用不可コードが複数ある場合は、そのうち使用不可度合いが最も低いものを選択することをさらに含む方法。
【請求項５】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する複数の呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調システムであって、
ａ）到来する呼リクエストに分配されるコードの所望のビットレートを認知する手段と、
ｂ）所望のビットレートを持つコードの使用可能性を判断する手段と、
ｃ）所望のビットレートの使用可能なコードが１つある場合に、該所望のビットレートの使用可能な１つのコードを前記到来する呼リクエストに分配する手段と、
ｄ）所望の使用可能なビットレートの複数のコードがある場合、使用可能な高速ビットレートコードの総数を可能な限り多く保ってコードを優先順位付けし、将来高速ビットレートコードを解放する可能性が最大となるように、所定の規則に従い、１つのコードを分配する手段と、
を具備し、
ｅ）所望のビットレートの使用可能な空きコードに連結する、長さのより短いコードの使用不可度合いを判断する手段と、
ｆ）最も使用不可度合いが高い連結された長さのより短いコードを有する空きコードの中から、１セットのコードを選択する手段と、
を含むコードを優先順位付けする手段をさらに具備し、
前記選択手段は、ルートコードに達するまで、連結された長さのより短いコードを有する空きコードの中から、１セットのコードを選択し、その結果得られる１セットのコードから１つのコードを最終的に選択するシステム。
【請求項６】
伝送容量を超過する場合に、到来するリクエストを別のコード構造に割り当てる手段をさらに具備する請求項５に記載のシステム。
【請求項７】
前記到来する呼リクエストにより伝送容量を超過する場合に、到来する呼リクエストをブロックする手段をさらに具備する請求項５に記載のシステム。
【請求項８】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する複数の呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調システムであって、
ａ）到来する呼リクエストに分配されるコードの所望のビットレートを認知する手段と、
ｂ）所望のビットレートを持つコードの使用可能性を判断する手段と、
ｃ）所望のビットレートのコードが使用できない場合に、到来するリクエストを使用不可コードに割り当てることによって再分配を実施し、使用済みの連結された低ビットレートコードを再分配し、割り当て済みの使用不可コードを解放する手段と、
を具備し、
再分配に好ましい使用不可コードとして、そのサブツリー内で割り当て済みの低速ビットレートのコードの数が最少であるものを選択し、そのような使用不可コードが複数ある場合は、そのうち使用不可度合いが最も低いものを選択する手段をさらに具備するシステム。
【請求項９】
ユーザ信号の識別を行う変調に拡散コードを使用する電気通信システムにおいて使用されるコンピュータプログラムを記憶した記録媒体であって、該コードは可能な限り多数の高速ビットレートのコードが残されるように異なるレベルの１セットのコード群から分配され、
ａ）到来した呼リクエストに分配されるコードの所望のビットレートを認知し、
ｂ）所望のビットレートを持つ異なるコードの使用可能性を判断し、
ｃ）所望のビットレートの使用可能なコードが１つある場合に、該所望のビットレートの使用可能な１つのコードを前記到来する呼リクエストに分配し、
ｄ）使用可能な所望のビットレートのコードが複数ある場合に、分配されるコードを選択して使用可能な高速ビットレートコードの総数を可能な限り多く保ってコードを優先順位付けし、将来高速ビットレートコードを解放する可能性が最大となるように、所定の規則に従い、１つのコードを分配することを、
実行するように具現化され、
さらに、コードの優先順位付けは、
ｅ）所望のビットレートの使用可能な空きコードに連結する、長さのより短いコードの使用不可度合いを判断し、
ｆ）最も使用不可度合いが高い連結された長さのより短いコードを有する空きコードの中から、１セットのコードを選択し、
ｇ）ルートコードに達するまで、連結された長さのより短いコードに対し前段のステップをくり返し、その結果得られる１セットのコードから１つのコードを最終的に選択することを実行するようにコードが具現化される計算可能で読み取り可能なコードを有するコンピュータで使用可能な媒体を含むコンピュータプログラムを記憶した記録媒体。
【請求項１０】
さらに、伝送容量を超過する場合に、到来したリクエストを別のコード構造に割り当てることを実行するようにコードが具現化される請求項９に記載のコンピュータプログラムを記憶した記録媒体。
【請求項１１】
さらに、前記到来する呼リクエストにより伝送容量を超過する場合には、到来する呼リクエストをブロックすることを実行するようにコードが具現化される請求項９に記載のコンピュータプログラムを記憶した記録媒体。
【請求項１２】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する複数の呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調装置であって、
到来する呼リクエストに分配されるコードのレートを通知し、
所望のビットレートを有するコードの使用可能性を判断し、
所望のビットレートの使用可能なコードがない場合に、到来するリクエストを使用不可コードに割り当ることにより再分配し、使用済みの連結された低速ビットレートコードを再分配して割り当てられた使用不可コードを解放することを実施するように構成された電子回路を具備し、
さらに、再分配に好ましい使用不可コードとして、コードサブツリー内で割り当て済みの低速ビットレートコードの数が最少になるものを選択し、そのような使用不可コードが複数ある場合は、そのうち使用不可度合いが最も低いものを選択するように、電子回路が構成された装置。
【請求項１３】
ユーザ信号の識別に複数の拡散コードを使用し、異なるビットレートのコードを有する単数或いは複数のコード構造から選択することにより、到来する複数の呼リクエストに前記複数の拡散コードを分配する、電気通信システムにおける情報信号の変調システムであって、
到来する呼リクエストに分配されるコードの所望のビットレートを認知し、
所望のビットレートを持つコードの使用可能性を判断し、
所望のビットレートの使用可能なコードが１つある場合に、該所望のビットレートの１つの使用可能なコードを分配し、
所望のビットレートの使用可能なコードが複数ある場合に、使用可能な高速ビットレートコードの総数を可能な限り多く保ってコードを優先付けし、将来高速ビットレートコードを解放する可能性が最大となるように、所定の規則に従ってコードを分配するように構成された電子回路を具備し、
さらに、コードの優先順位付けは、
所望のビットレートの使用可能な空きコードに連結する、長さのより短いコードの使用不可度合いを判断し、
最も使用不可度合いが高い連結された長さのより短いコードを有する空きコードの中から、１セットのコードを選択し、
ルートコードに達するまで、連結された長さのより短いコードに対し前段のステップをくり返し、その結果得られる１セットのコードから１つのコードを最終的に選択するシステム。
【発明の詳細な説明】
【０００１】
【技術分野】
本発明は概して、異なるビットレートのコードを使用したＣＤＭＡシステムにおけるコード分配のための、電気通信システムにおける情報信号の変調方法とシステムに関する。本発明はまた、本発明の方法を実行するコンピュータプログラムにも関する。
【０００２】
さらに詳細には、本発明は電気通信システムにおける情報信号の変調方法とシステムに関し、そこではユーザ信号の識別にコード拡散を使用し、該コードは到来した呼のリクエストに対し、異なるビットレートの単数または複数のコード構造から選択することにより分配される。
【０００３】
【従来の技術】
ディジタル信号の送受信には、複数のチャネルアクセス法が存在する。ＴＤＭＡ（Time Division Multiple Access；  時分割多元接続）では、一つのチャネルが同一周波を一定の間隔に区切った周期的列にタイムスロットを有する。ＦＤＭＡ（Frequency Division Multiple Access；  周波数分割多元接続）では、一つのコミュニケーションチャネルが単一の無線周波数帯である。隣接するチャネルとの混線は、特定の周波数帯の信号エネルギーのみを通過させる帯域フィルタの使用により制限できる。これに対し、ＣＤＭＡ（Code division Multiple Access；  コード分割多元接続）は、時間帯及び周波数双方の共有を可能にする。従って、複数のＣＤＭＡ信号が同一の周波数帯を共有することができ、またＣＤＭＡ受信機は複数の周波数帯で動作することができる。
【０００４】
従ってＣＤＭＡの技術範囲では、同時接続に共通周波数帯を利用できる。選択、つまり所望の信号とその他の信号の識別は、その他の信号とは別のコードでコード化された所望の信号に基づき、適合する信号を処理することにより行われる。従って、ＣＤＭＡシステムの無線チャネルはチャネル毎に複数の異なったコードを使用することにより獲得される。一般的には、チャネルは２進ＰＮコードシーケンスを使用することにより獲得される。
【０００５】
ＣＤＭＡの無線信号で伝送される情報は、送信器側で特定の拡散コードによってコード化（拡散）される。受信器側では、特定の同一拡散コードを再び相関するか、または受信した情報を整合フィルタにかけることにより、コード化された情報を複合する。
【０００６】
ＩＳ−９５などのＣＤＭＡが使われている第二世代のモバイルネットワークシステムは、主として音声信号の伝送のために設計された。そのようなシステムで使用されるＣＤＭＡは、第三世代のモバイルシステムで使用される広帯域ＣＤＭＡであるＷＣＤＭＡや、ビットレートの広拡散を持つ信号により音声、ビデオその他といったサービスを伝送するＵＭＴＳに比較すると、周波数帯が制限されている。
【０００７】
ＷＣＤＭＡシステムにおいては、ユーザチャネルに対し、各チャネルのデータ転送速度に基づいて、可変長の２進コードを割り当てることができる。これにより、例えば音声、ビデオ、データなど様々なサービスが可能になる。直交コードは与えられたタイムオフセットに互いに相関しないコードである。そのためそのようなコードの使用により所望のチャネルが識別され、直交コードの使用により混線が減少する。通常、時間のばらつきが要因となって直交コードでコード化された信号間の直交性が部分的に破壊されるなどの理由により、混線は完全には排除されない。
【０００８】
システムで使用可能な全てのコードを、通常はそれらがビットレートを提供した後に整える、異なったコード構造が存在する。ＷＣＤＭＡで使用されるコード構造システムの例として、例えばＯＶＳＦ（Orthogonal Variable Spreading Factor；  直交可変拡散率）コードを挙げることができ、以下に説明する。ＯＶＳＦコードを生成する一つの方法として、異なる長さのウォルシュ（Walsh）コード、つまり異なる拡散率を使用するものがある。
【０００９】
国際公開公報ＷＯ  ９５０３６５２号において、ユーザチャネルは、各チャネルのデータ転送速度に基づき可変長の２進ウォルシュコードシーケンスを割り当てられる。
【００１０】
そのようなコードの最下位の順位（つまり第一位）はルートコードと呼ばれる。ルートコードは１ビットのコード長を有し、「０」に等しい場合がある。ウォルシュシーケンスのツリーとは、それぞれ２本の枝を持ち、相互に連結したノードの１セットであって、全てのノードからルートノードに遡ることができる。ルートノードから伸びる２本の枝は、ウォルシュシーケンスにより「００」または「０１」で定義される２つのノードに接続している。この過程は、ノード「００」をノード「００００」及び「００１１」へ、ノード「０１」を「０１０１」及び「０１１０」といったように第三位コードに拡張していくことでウォルシュ関数行列を導くことにより続けられる。任意のノードから伸びるツリーのノードを定義するウォルシュシーケンスは、該ノードに関するウォルシュシーケンスに直交ではない。そのため、異なった順位の連結ノードはチャネルを識別せず、枝に連結したコードは同時に使用されるものではない。該ノードに連結しないノードを定義する他のウォルシュシーケンスはすべて、他のモバイルチャネルを定義するためのコードとして同時に使用することができる。
【００１１】
従って、特定のコード長に使用できるコードの数は数学的に限界があるため、分配されるコードの量は制限される。ＯＶＳＦコードはＷＣＤＭＡに使用されるダウンリンクのチャネライゼーションコードで、異なる速度及び拡散率を持つチャネル間の直交性を保つ。図１にＯＶＳＦコードのコード構造をコードツリー構造により記載し、後述に詳細に説明する。コードツリー構造において、例えば音声のような長いコードを必要とするサービスはツリーの右側にあり、これに対しビデオのように必須要件（例えば高いデータレート）の多いサービスは短いコードを必要とし、ツリーの左側に示されている。様々な種類のサービスを提供できるセルにおいては、それぞれのサービスに応じて異なる拡散率を持つコード及び率が必要となる。
【００１２】
音声などのサービスを提供することができ、そこでは割り当てるコードが体系的に選択されるようなＣＤＭＡシステムにおけるコード分配のための従来技術は、知られている限り存在しない。もし、単に最初に使用可能なツリーコードにサインするだけでその後の規則が無くてもコード分配が実行されれば、それはそのようなコード要求を分配する最も簡潔な方法であり、いわゆる順序配列モードを意味する。
【００１３】
そのような順序配列式コード分配方法を複数のコードレベル（順位）を使用する広帯域システムで使用する上での問題は、古い呼が終了する際に使用済みのコードを解放するときに発生し、頻繁に使用されるコードのコード構造に穴をつくる。使用可能な最大総ビットレートに達していない場合でさえ、（つまりまだ幾つかの使用可能コードが残っていたとしても、）使用済みの低速ビットレートのコードを再分配することによって要求されたレベルのもっと高いビットレートを持つコードを解放しない限り、新しい高速ビットレートの呼リクエストは処理されない。再分配には基地局と関与するモバイル局間の信号が必要になるので、高負荷状態では危険な状況が発生する可能性がある。
【００１４】
国際公開公報ＷＯ  ９５／０３６５２号（QUALCOMM INCORPORATED）は、広帯域ＣＤＭＡシステムのコード分配システムを提案してこの問題を論じており、使用に適さない短いコードの数を最小化する案を提供している。該出願は、ツリーの断片化を最小化するために使用頻度の高いコードに連結するコードを割り当てる機会を論じ、利用できない高速コードに連結する低速コードを分配することを提案している。さらに、高速コードの利用度を高めるために再分配が提案されている。しかしながら、この結果を達成するための正確なアルゴリズムは示されておらず、将来的な可用性の問題も考慮されていない。従って、そのようなアルゴリズムが必要とされる。
【００１５】
本発明の目的は、多速度システムにおいてコード分配を行う際のシステム内の信号を最小化する方法を開発することである。
【００１６】
別の目的は、新規呼を分配する際のセットアップ遅延を減らすことである。
【００１７】
第３番目の目的は、異なるレベルで使用可能な空きコードの数を最大化することである。
【００１８】
第４番目の目的は、利用できる空きコードが無いときに再分配を行う方法を開発し、一方そのような再分配の必要を最小化することである。
【００１９】
第５番目の目的は、本発明による分配を実行するアルゴリズムを使用することにより、使用不可能な高速コードを最小限に抑える方法を開発することである。
【００２０】
【発明の概要】
本発明の方法とシステムは、到来したリクエストに分配されたコードのビットレートを認知する段階と、所望のビットレートを持つ複数のコードの可用性を判定する段階と、所定の規則に従い、コード構造を最適に使用するよう複数のコードの可用性を考慮することによりコードを分配する段階と、それぞれの段階を行う手段を有することを特徴とする。
【００２１】
本発明による装置は本発明の方法を実行する手段を有する。
【００２２】
本発明のアルゴリズムは、特定の規則に従うコンピュータプログラムの形式で、本発明の分配方法を実行する。
【００２３】
任意のサービスリクエストに分配されるコードもまた、通信状態、使用可能なコードの数及び要求されるコードのビットレートに依存する。
【００２４】
コード分配の条件は、分配を行ってもシステムの最大伝送容量を超過しない通信状態にあることである。利用できる伝送容量を持つコードシステムが無い場合、入ってくるリクエストはブロックされる。
【００２５】
要求されたレベルのコードが１つ存在する場合は、そのコードがリクエストに分配される。
【００２６】
要求されたレベルのコードが２つ以上存在する場合は、コード分配に本発明のアルゴリズムを使用し、優先順位を決めた所定の規則に従って分配するコードを決定する。
【００２７】
しかしながら、その際に要求されたレベルの空きコードが無いものの、システムに特定のサービスリクエストのための十分な伝送容量が残されている場合（複数の空きコード）、本発明の再分配アルゴリズムが実行され、既に割り当ての済んだコードを要求されたレベルの空きコードに再分配する。この場合、到来したリクエストは１つのコードに割り当てられ、それは連結する長い使用済みコードのため使用できない。これらの使用済みの既に割り当ての済んだコードの再分配が、新規到来コードの分配と同じ規則に従って次に実行される。
【００２８】
到来するリクエストは、例えば音声、データ、ビデオなど、ＷＣＤＭＡで使用されるどのようなサービスでもよい。
【００２９】
本発明は、通信状態の統計値を入力することにより、新しいコードを割り当てるために再分配が必要になる回数及び既に分配の済んだコードの総変更回数を最小化するアルゴリズムを提供する。結果として、システム内の信号総数が減少する。
【００３０】
以下に、ブロック図により本発明を記載する。ブロック図と例証を用い、コードの優先順位を決める規則を説明するものである。しかしながら、本発明は以下の記載に限定されるものではなく、以下の記載は例証としての目的でのみ提示される。本明細書の図表にはＯＶＳＦという特定の構造が記載されているが、請求の範囲に規定される本発明の概念は、例えば異なるレベルのコードを定義するＯＶＳＦコードツリー以外のコードシシテム構造に拡張することが可能である。
【００３１】
【詳細な説明】
ＯＶＳＦコードは、図１に例示したコード構造によって定義される。ツリーの各ノードは、１つのコードに対応し、その拡散率（ＳＦ）及びビットレートはそのＳＦレベル１、２、４、８または１６により定義される。また、後述する説明を簡単にするために、コードレベルはレベルｋと表される。ＳＦレベルとｋレベルの関係は、ｋレベル０、１、２、３、４のそれぞれに、ＳＦレベル１、２、４、８及び１６が対応している。一つのレベルのコードは特定の長さを持ち、従って特定の拡散率とビットレートに対応している。最下位のＳＦレベル、最高速のビットレート及び最下位のｋレベルに対応するノードは、図１で最も左側に位置し、ルートと称される。
【００３２】
任意のコードをルートとして伸びるサブツリーの枝にあるノードのいずれも使用中でない場合、該コードは空いており、到来した呼に割り当てられる。
【００３３】
１つのコード（ノード）に対し、占有の異なる度合いを定義することが可能である。コードは占有の程度に応じて、「使用中」、「使用不可」或いは「空き」に分類することができる。
【００３４】
任意のコードそれ自体或いは該コードからルートまでの経路上に位置する、該コードより高速のビットレートを有するコードが既にダウンリンク接続に割り当てられている場合、該コードは「使用中」である。ダウンリンク接続に直接割り当てられた場合、使用中のコードは「使用済み」とされる。
【００３５】
任意のコードのサブツリー中の、単数または複数のコードが使用中である場合、該コードは「使用不可」である。この場合、占有または使用不可の度合いは用済みのコードに割り当てられたサブツリーの総ビットレートの端数と定義することができる。サブツリー全体が使用済みである場合、完全に使用不可能なコードは使用中と考えることができる。
【００３６】
使用中でも使用不可でもない残りのコードすべてが「空き」である。
【００３７】
任意のコードから該コードの２倍の長さのコードが２つ下降している場合、該コードを「父」、下降した２つのコードを「子」と称す。父コードは長さが短く、ビットレートが速い。同じ父を持つコードは「兄弟」コードである。
【００３８】
コードツリー構造は、音声のように長いコードを必要とするサービスはコードツリーの右側に位置し、それに対し、ビデオのようにさらに必須要件の大きなサービスは、短いコード、つまり高速のビットレートを必要とし、コードツリーの左側に位置することを意味すると考えられる。
【００３９】
下記に述べる図表を用いた記載をさらに深く理解するために、次に従来技術の欠点とそれを排除するための本発明による方法について簡単にまとめる。
【００４０】
分配に関する問題は、古い呼が終了し、使用済みのコードが解放されて使用中のコードのツリーに穴が発生するときに生じる。
【００４１】
そのような場合、最大総ビットレートに達していない場合であっても、使用中のコードが再分配により対応するレベルのサブツリーが解放されない限り、高速ビットレートの新規呼リクエストは処理されない。
【００４２】
再分配にはＢＳと関連するＭＳ間に信号が必要になるので、高負荷状態で起こる危機的状況を避けるためにはその回数を可能な限り低く抑えなければならない。
【００４３】
本発明は、上述の背景に配慮し、通信状態の統計値を入力することで新しいコードを割り当てるための再分配が必要になる回数を最小化する、分配アルゴリズムの利点の実現に基づく。同様に、１回の再分配が決定された場合に、実際のコード変更の総数を最小化するアルゴリズムを見つけることは有利である。
【００４４】
本発明に従い、このコード再分配のための新しいアルゴリズムは、上位レベルの使用可能コードの総数を可能な限り多く保つことを目的とする。複数の選択が可能である場合、将来上位レベルのコードを解放する可能性が最も大きいコードが選ばれる。
【００４５】
アルゴリズムは以下の規則に基づいている。
【００４６】
レベルｋのコードが割り当てられ、ｋ＝ｌｏｇ２（ＳＦ）が拡散率の基数２のロガリズムであると仮定する。
【００４７】
割り当てられるコードは明らかにレベルｋの空きコードの１セットに属する。
【００４８】
このセットの中で、父の使用不可の度合いが高いコードが好ましい。
【００４９】
これにより、適応するコードが含まれているであろう新規のサブセットが決定する。該セットが２つ以上のコードを含む場合、祖父コード、つまり親の親の使用不可度合いがチェックされ、ここでも使用不可度合いの高いものが選択される。
【００５０】
１セットに含まれるコードが１つになるまで、或いはルートコードにたどり着くまでこの過程が繰り返される。後者の場合、最後のセットの最初のコードが選択される。
【００５１】
到来する呼によりルートコードの最大ビットレートが超過してしまう場合、該呼はブロックされるか、別のコードに割り当てられる。ＣＤＭＡにおいては、これは別の同一のＢＳに割り当てられた別のスクランブルコードにより行われる。
【００５２】
最大総ビットレートを超過せず、レベルｋに空きコードが存在しない場合、再分配が必要になる。
【００５３】
再分配の最も容易な方法は、第一の適応コード（完全に使用不可でも使用中でもなく、使用中の祖先を持たないコード）を見つけ、それを新規呼に分配することである。分配アルゴリズムにより、通常そのサブツリー中の使用中コードが次に到来する呼に分配される。
【００５４】
本発明が提案する再分配アルゴリズムはさらに、必要な再分配の回数を最小化することを目的とする。再分配の回数とは、継続中の接続が割り当てられているコードの変更回数と定義され、再分配処理の結果再分配されて移転したコードの数に等しい。
【００５５】
第１段階として、新規リクエストが使用不可ではあるが使用中ではないコードに割り当てられる。このコードが使用中（使用済み）となると、その使用済みの子孫が再分配されることになる。空きコードだけが到来する呼に割り当てられるので、この処理は論理的に実際の分配に先行する。
【００５６】
新規分配に選択されるコードとは、そのサブツリー中の使用済みコードの数が最も少ないコードである。つまり、再分配の数が最小に抑えられる、子孫の数が最小のコードである。
【００５７】
１つ以上のサブツリーにおいて使用済みの子孫の数が最少である場合、将来の再分配の可能性がないツリーに組み込まれる可能性が最も高くなる、低速のビットレートのコードを動かさねばならないので、使用不可度合いの最も低いコードが選択される。
【００５８】
次に、新規呼に適用された規則に従いサブツリーコードの実際の再分配（コードの変換）が実行される。対応するレベルの空きコードが存在する場合は分配アルゴリズムに従い、空きコードが存在しない場合は再分配アルゴリズムに従い実行される。
【００５９】
コードは分配に使用された方法と同じ方法によって再分配されるので、次々に枝分かれしていく再分配を引き起こす。
【００６０】
ツリーの（ビットレートの）総容量を超過しない限り、分配及び再分配によりすべての新規コードリクエストが処理されることは注目すべきである。
【００６１】
図２（ａ）及び２（ｂ）は、本発明の基本理念を説明する、それぞれフロー図とシステムのブロック図である。ステップ１では、拡散情報信号のためのコード分配のリクエストがシステムのセクション１２で受信され、新規呼リクエストとなる。ステップ２で注目されるべきは、システムのセクション１３において、呼リクエストのコードレベルと、信号コードの望ましいレベルｋ又はビットレートを認知することである。典型的にセルラー無線システムのセルに使用される最下位のコード、つまりツリーのルートコードは、該セルの、大伝送容量を決定する。最大伝送容量を超過することはできない。総最大ビットレートを超過すると、いくつかのコード間の直交性が失われ、その結果それらコードが劣化することになる。既に使用済みの総ビットレートと新規呼のビットレートの和がツリーの総ビットレートを超過すると、呼リクエストはブロックされるか、別のコードツリーに割り当てられる。
【００６２】
ステップ３では、新規リクエストの超過ビットレートを判定するシステムのセクション１４において、到来したリクエストのコード分配がコードツリーのルートコードの総ビットレートを超過するかどうかが決定される。超過する場合、ステップ４において、システムのセクション１５がリクエストのブロックを実行、またはシステムに他に使用できるツリーがある場合は該他のツリーへの割り当てを実行する。超過しない場合、つまりステップ３において最大総ビットレートは超過しないと判断された場合、フローはステップ５及び要求されているレベルの空きコードを決定するシステムのセクション１６に進む。
【００６３】
ステップ５では、上述のように、要求されたレベルｋが存在するかどうかを判断する。存在しない場合、ステップ６のシステムのセクション１７により、要求されたレベルの使用不可コードに新規リクエストを割り当てることにより行われる再分配が必要になる。このため、ステップ７及びシステムセクション１８において、連結する上位レベルコードを再分配し、使用不可コードを解放する。すなわち、使用不可コードに関して既に割り当ての済んだサブツリーコードを変換し、要求されたレベルｋのコードを解放しなければならない。ここでフローはステップ５並びにシステムのセクション１６に戻る。
【００６４】
本発明による再分配処理により、到来するリクエストは、所定の規則に従い、選択された、使用不可ではあるが使用中ではないコードに割り当てられ、その後該コードのサブツリー内の使用済みコードは再分配される。
【００６５】
好適には再分配は必要な再分配の数を最小化することを目的とするアルゴリズムにより行われる。これらの再分配は割り当ての済んだ接続中のコードの変更、または、再分配処理の結果、再分配のために転移されたコードの数と定義される。
【００６６】
本発明の実施例によると、ステップ６のシステムセクション１７により割り当てられるのに望ましい使用不可コードとは、再分配、つまりは割り当ての済んでいる接続中のコードの変更を最小限に抑えることができる、そのサブツリーにおいて割り当て済みコードの数が最も少ないコード、つまり、それに連結する上位レベルｋのコードの数が最も少ないコードである。別の実施例によると、望ましい使用不可コードとはまた、そのサブツリーに関して、使用不可度合いが最も低いコードである。
【００６７】
最適のモデルにおいては、望ましい使用不可コードはサブツリー中の割り当て済みコードの数が最も低いコードであり、必要な再分配の回数を最少に抑えることができる。
【００６８】
次に、到来した新規リクエストに適用した規則に従い、サブツリーコードの再分配がステップ５−１１により行われる。つまり、適応するレベルの空きコードが存在する場合は分配アルゴリズムを使用して、存在しない場合は再分配アルゴリズムを使用して行われる。
【００６９】
ステップ５においてシステムのセクション１６が要求されたビットレートの空きコードが存在すると判断すると、そのコードが割り当てられる。要求されたレベルのコードが複数存在する場合は、システムのセクション１９のステップ８で、要求されたレベルのコードについて使用可能性を判定する。
【００７０】
コードを選択するため、ステップ８の後、ステップ９のシステムセクション２０により所定の規則に従ってコードの優先順位付けが行われる。それらの規則に従い、出来るだけ多くの、下位レベルｋの使用可能なコードがステップ１０で保たれる。複数の選択が可能な場合、将来的に下位レベルコードの解放の可能性を最大にするべくステップ１１のシステムのセクション２２により選択が行われる。これは、ステップ９においてあらかじめ選択した規則に従い実行することができる。
【００７１】
ステップ１０において行われる、下位レベルに出来るだけ多数の空きコードを保つようなコードの優先順位付けは、例えば、使用不可度合いの最も高い父を持つ使用可能なコードの１セットを決定し、その１世代前のコードレベルに前段のステップを行うことを繰り返してルートコードに到達し、最後に得られたサブセットからコードを選択することにより実行してもよい。
【００７２】
ビットレートの点でツリーの総容量を超過しない限り、分配及び再分配により、新規コードリクエストがすべて処理されることは注目に値する。
【００７３】
【実施例】
以下の実施例１−５により、本発明を幾つかの典型的な状況（ケース１−４）と関連させて説明する。図３−７のすべてにおいて、黒丸は使用済みのコードを表し、灰色の丸は使用中ではあるが使用済みではないコードを表す。リクエストが割り当てられるとコードは使用済みとなる。使用されていなくても、その祖先の１つが使用済みであるとコードは使用不可となる。
【００７４】
実施例１（使用可能、ケース１）
図３では、ＯＶＳＦコードを到来したリクエストに分配する状況を仮定している。５つのコードレベルｋ、つまり０、１、２、３、及び４が図３に示されている。上位レベルの空きコードが大文字のアルファベットＡ−Ｍで表されている。
【００７５】
ここで、図２（ａ）のステップ１及び２に従い、図３のコードツリーにおいてｋ＝４のレベルを有するリクエストを想定する。ステップ３において最大総ビットレートまたはコードツリーの伝送容量が超過されないと判断され、かつステップ５において要求されたレベルの空きコードが存在すると判断された場合、ステップ８において本発明のアルゴリズムは各空きコードの父の使用不可度合いを検討する。その結果、Ｃの使用不可度合いは１／２で、それ以外のすべてのコードの使用不可の度合いは０である。これにより、ステップ１０において目的にかなうコードとしてＣが割り当てに選択され、該目的に従い可能な限り多数の下位レベルの使用可能コードが保存される。より高速のビットレートの空きコードを残すという点に関し、これが最良の解決策であり、これにより図３において、ｋ＝３のレベルに６つの空きコードが、ｋ＝２のレベルに２つの空きコードが、ｋ＝１のレベルに１つの空きコードが残る。Ｆ−Ｍの中で上位のレベルｋを有するコードを選択する可能性を残すために、Ｋ＝３のレベルに５つの空きコードが、ｋ＝２のレベルに１つの空きコードがあり、ｋ＝１のレベルには１つもない。Ａ−Ｂの割り当てについては、ｋ＝３のレベルに５つの空きコードがあり、ｋ＝２のレベルに２つの空きコードがあり、ｋ＝１のレベルに１つの空きコードがある。
【００７６】
実施例２（将来的使用可能性、ケース２）
図４は、ＯＶＳＦコードを到来受信したリクエストに分配する別の状況を仮定している。５つのコードレベルｋ、つまり０、１、２、３、及び４が示されている。上位レベルの空きコードが大文字のアルファベットＡ−Ｅで表されている。
【００７７】
図２（ａ）のステップ１及び２に従い、ｋ＝４のレベルを有するリクエストを想定する。ステップ３において最大総ビットレートまたはコードツリーの伝送容量が超過されないと判断され、かつステップ５において要求されたレベルの空きコードが存在すると判断された場合、ステップ８において本発明のアルゴリズムは各空きコードの父の使用不可の度合いを検討する。図４のＯＶＳＦツリーは、ｋ＝４のレベルに５つの空きコードが存在することを示しており、それらはＡ、Ｂ、Ｃ、Ｄ及びＥである。コードＣ及びＤは空き（使用不可の度合いが０）の父を有しているので、ステップ１０の選択においてできるだけ多数の高速ビットレートのコードが空きとして残るよう放棄される。
【００７８】
コードＡ、Ｂ及びＥは、使用不可の度合いが１／２である父を有しており、そのためアルゴリズムは祖父の使用不可の度合いを検討する。コードＡ及びＥの使用不可の度合いは３／４であり、コードＢの使用不可の度合いは１／４である。故に、ステップ１０においてコードＢは放棄される。次に、曽祖父（ｋ＝１）を検討する。コードＡの曽祖父の使用不可の度合いは４／８であり、一方コードＥの曽祖父の使用不可の度合いは７／８である。そこで、ステップ１１においてコードＥが到来したリクエストに分配される。
【００７９】
最上位レベルのコードの可用性に関して言えば、コードＡ、Ｂ及びＥは等価であることは、各割り当てから同数の上位レベルコードの空きコードが残るという意味で注目に値する。本発明の１つの好適な実施例では、ステップ１１において下位レベルのコードを解放する可能性が最も高くなるようコード分配が行われる。したがって、コードＡ、Ｂ及びＥの違いは、現在使用不可である下位レベルのコードの短期的な解放の可能性に関し、その可能性はステップ１１において提案される選択により最大化される。
【００８０】
実施例３（再分配の実施例１、ケース３−１）
図５は、ＯＶＳＦコードを到来したリクエストに分配するまた別の状況を仮定している。図２（ａ）のステップ１及び２に従い、ｋ＝１のレベルを有するリクエストを想定する。ステップ３において最大総ビットレートまたはコードツリーの伝送容量が超過されないと判断された場合、ステップ５において要求されたレベルのコードの使用可能性の度合いを判断する。本ケースにおいては使用可能な空きコードが１つも無いため、再分配アルゴリズムが実行され、それに従って２つの使用不可コード、すなわちＡまたはＢ、のうち１つが、ステップ６において到来したリクエストに割り当てるコードとして選択される。コードＡは２つの使用済み子孫Ｄ及びＥをｋ＝４のレベルに有し、一方コードＢはｋ＝２のレベルに唯一の使用済みコードとしてＣを有するだけである。従って、再分配は既に分配されたコードの変更を最少化し、また好適な使用不可コードとは連結する上位レベルの割り当て済みコードの数が最も少ないコードであるという本発明の規則に従い、コードＢが選択される。
【００８１】
コードＢが選択されると、上位レベルにあるコードＣは再分配されなければならない。この状況を図６に示している。ｋ＝２のレベルにあるコードＣの再分配を実行するための再分配のリクエストは到来するリクエストと同様に処理される。つまり、リクエストは図２（ａ）のステップ７からステップ５に進む。
【００８２】
空きコードがないため、更にまた再分配処理が始まり、ｋ＝２のレベルにある２つの使用不可コードのうちの１つが選択される。この場合、２つの使用不可コードの使用不可度合いは同じであるので、選択は無作為に行われる。次に、ｋ＝４のレベルにある連結コードの一つが割り当てられたコードのサブツリーから移され、代わりに到来する通常のリクエストに分配されなけばならない。この最後の割り当てにおいて、ｋ＝４のレベルにあるコードの分配は、それらがどちらもｋ＝２のレベルに関して同一の、再分配されたコードＣには連結しないサブツリーに属するように行われる。また望ましくは、ｋ＝３のレベルに空きコードを１つ残すよう、ｋ＝３のレベルに関しても同一のツリーに属するように行われる。
【００８３】
実施例４（再分配の実施例１、ケース３−２）
実施例３と同様の状況について、実施例３の再分配法を用いずに、別の再分配処理を適用する。
【００８４】
ここで想定する再分配は、使用不可度合いの低いサブツリーを選択する。Ａの使用不可度合いは２／８であり、Ｂの使用不可度合いは１／２である（図５参照）。この場合、コードＢではなくコードＡが選択され、その結果コードＤ及びＥの再分配のほかには再分配の必要がなくなる。
【００８５】
しかしながら、前例と同様に２つのコード変更（再分配）が必要になり、そのため間接的再分配処理により付加的なセットアップ遅延が起きないと想定すると（この想定は、基地局が内部で必要な再分配をすべて行い、最後に実際のコード変更命令を関連する移動局に発する可能性がある以上妥当である）、図３及び４において２つの再分配アルゴリズムを実行することは同じである。
【００８６】
実施例５（再分配の実施例２、ケース４）
本発明による再分配法の２つ目の実施例を図７に示す状況に使用する。
【００８７】
本実施例に従う再分配は、実施例３で行ったように、負荷のかかっていない分配済みコードの数によるのではなく、使用不可度合いに基づいて行った。ここでは、コードＡの使用不可度合いが３／８で、コードＢの１／２より低いので、ＢではなくＡが再度選択される。これにより、再分配の実施例１（実施例３）で使用した、本発明が提案する負荷のかかっていないコードに基づくアルゴリズムを使用してコードＢを選択した場合にコード変更が２つだけで済むのに対し、３つのコードの変更（コードＤ、Ｅ及びＦの変更）が余儀なくされるので、本実施例の方が実際に良い判断とは言えない。
【００８８】
上記２つの実施例は、サブツリーの使用済みコードの数に基づき、本発明が提案するアルゴリズムがどのように働くかを説明する目的で記載されており、実施例３の状況において同じように実施可能な（代わりにサブツリーの使用不可度合いに基づいた）別のアルゴリズムは、実施例４でみるように、時に不要なコード変更を余分に発生させることがあることを示している。
【００８９】
満足のゆく解決策とは、使用済みコードの数が最も少ないサブツリーを選択することであり、２つ以上のサブツリーにおいて使用済みのコードの数が最少である場合、サブセットの中から使用不可度合いが最小のものを選ぶことである。
【００９０】
【評価】
本発明による解決法のコード分配性能の向上を評価するため、シミュレーションを実行した。
【００９１】
拡散率が４（３８４ｋｂｐｓ  ＬＣＤ（Long Constrained Delay Data）及び２０４８ｋｂｐｓ  ＵＤＤ（Unconstrained Delay Data））から１２８（８ｋｂｐｓ音声）の範囲にわたる、複数の異なるサービスを考慮した。シミュレーション時間（１００００ｓ）中の通信状態の統計値を表１に示す。
【００９２】
分配及び再分配アルゴリズムの５つの異なる組み合わせを幾つかの通信状態の統計値を使用してテストした。以下、本発明の解決策を「本案」と呼び、また「従来の技術」の項で言及した従来技術の順序配列的コード分配法を引用し、従来技術による解決策を「順序配列」と呼ぶ。表２、３、４及び５は、それぞれ、どちらも順序配列による分配と再分配、順序配列による分配と本案による再分配、本案による分配と順序配列による再分配、どちらも本案による分配と再分配を使用した場合の、（サービス毎の）シミュレーションの結果を示している。順序配列による分配の方法では、以降の規則に関係なく１番目の使用可能な空きコードが割り当てられる。
【００９３】
１番目の項目は、ツリーの空きスペースが不足しているためにブロックされた再分配の数を示している。次の項目は、最終的に再分配により処理されたリクエストの数を示す。いずれのリクエストも、（空きコードがどのように散らばっているかに関係なく）ツリーに理論上の空きがある場合のみ処理され、また同じ通信状態の統計値を使用している（乱発生に同じシードを使用している）ため、ブロックされた数及び受け入れられた数はすべてのケースにおいて同一である。異なるアルゴリズムのシミュレーションは、統計値の観点だけでなくツリー操作正確さにおいても点でも同一の条件で実行された。３番目の項目は、再分配処理の数を示す。最後に、４番目の項目は必要とされた再分配の総数を表す。
【００９４】
再分配処理の数は、新規コードリクエストがツリーから直接１つの空きコードを選ぶことでは処理されず、従って再分配アルゴリズムへの呼が避けられなかった回数を表す。
【００９５】
他のすべてのパラメータを一定に保てば、分配処理の性能が向上するに従いこの値は減少する。
【００９６】
システムの観点から言えば、再分配処理の数は、コード変更による到来する呼の平均セットアップ遅延を決定する。
【００９７】
一方、すべてのコード変更を同時に行うことができると仮定すると、総再分配数は余分に発生した信号に比例する。
【００９８】
表６及び７は異なるアルゴリズムの組み合わせを使用した場合の、再分配処理数の比較と総再分配数を示す。
【００９９】
本案のアルゴリズムにより、再分配処理の回避数（セットアップ遅延の平均値が低下する）と、コード変更回避数（余分な信号が減少する）両面において明らかに改善がみられる。
【０１００】
本発明の解決策は、どちらも本発明のアルゴリズムを使用して分配及び再分配を行った場合、（Ｐ．Ａ．Ｐ．Ｒ．を使用）順序配列による分配と再分配を行う従来技術に比較して、再分配処理を４５％減少させ（約４５００から約２５００へ）、それに応じてコード変更も７４％減少させる（約１３５００から約３５００へ）。
【０１０１】
本発明が提案する分配及び再分配アルゴリズムは、本発明を適用したシステムにおいて（従来技術による単純な順序配列による処理に比較して）コード変更の数を２５％まで減少させ、それに応じて信号メッセージも減少させる。これは表８のＳ．Ａ．Ｓ．Ｒ．（合計１３４８７）とＰ．Ａ．Ｐ．Ｒ．（合計３５０７）を比較することにより明らかである。
【０１０２】
同様に、必要とされる再分配処理の数は約半分まで減少し、コード変更により生じるセットアップ遅延を改善する。本発明の解決策に要するコストへの影響は、基地局ではいずれにせよコード分配に何らかのアルゴリズムを使用しなければならないのであるが、基地局で必要とされるコンピュータが多少複雑になることのみである。
【０１０３】
【表１】
0004707912.tif 000002
【０１０４】
【表２】
0004707912.tif 000003
【０１０５】
【表３】
0004707912.tif 000004
【０１０６】
【表４】
0004707912.tif 000005
【０１０７】
【表５】
0004707912.tif 000006
【０１０８】
【表６】
0004707912.tif 000007
【０１０９】
【表７】
0004707912.tif 000008
【０１１０】
【図面の簡単な説明】
本発明は、以下の図を参照してより詳細に説明される。
【図１】  図１はＯＶＳＦコードツリー構造の一例を示す。
【図２】  図２（ａ）は本発明のステップを説明するフロー図であり、図２（ｂ）はシステムセクションのブロック図である。
【図３】  図３は１つの仮定状況における本発明によるアルゴリズムの適用例である。
【図４】  図４は別の仮定状況における本発明によるアルゴリズムの適用例である。
【図５】  図５は別の仮定状況における本発明によるアルゴリズムの適用例である。
【図６】  図６は別の仮定状況における本発明によるアルゴリズムの適用例である。
【図７】  図７は別の仮定状況における本発明によるアルゴリズムの適用例である。
【図１】
0004707912.tif 000009
【図２】
0004707912.tif 000010
0004707912.tif 000011
【図３】
0004707912.tif 000012
【図４】
0004707912.tif 000013
【図５】
0004707912.tif 000014
【図６】
0004707912.tif 000015
【図７】
0004707912.tif 000016