(57)【要約】本発明は、ＯＶＳＦ符号割り当て、割り当て解除、及び符号木プルーニングのシステム及び方法を含む。本発明は、ＯＶＳＦ符号識別及び記憶スキームも含む。符号木プルーニング、符号割り当て、及び割り当て解除の実施形態が提供される。これら実施形態は、slottedＣＤＭＡシステム及びnon-slottedＣＤＭＡシステムに適用される。
2005533455.tif 000002
【特許請求の範囲】
【請求項１】
ＣＤＭＡ（code division multiple access）通信システムおけるＯＶＳＦ（orthogonal variable spreading factor）符号木の符号を再割り当てする方法であり、前記ＯＶＳＦ符号木が、異なる拡散率の複数の符号を有し、かつ、これら異なる拡散率の複数の符号の間にブランチを有し、仮に前記符号が割り当てられた場合には、当該符号とブランチを介して接続された符号のうちの拡散率がより小さい符号の割り当てをブロックし、仮に前記符号がブロックされた場合には、当該符号とブランチを介して接続された符号のうちの拡散率がより小さい符号の割り当てをブロックする方法であって、
第１の拡散率から開始し、
（ａ）当該拡散率を有する選択済み割り当て済み符号であって、前記ＯＶＳＦ符号木の所望の方向にある当該拡散率を有する他の符号に再割り当てをすることができる符号を決定するステップと、
（ｂ）前記選択済み割り当て済み符号を前記他の符号に再割り当てし、かつ、他の拡散率についてステップ（ａ）及び（ｂ）を繰り返すステップと
を備えたことを特徴とする方法。
【請求項２】
請求項１に記載の方法において、前記他の符号は、前記選択済み符号と同じタイムスロットにおける符号であることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、前記他の符号の少なくとも１つは、前記選択済み符号と異なるタイムスロットにおける符号であることを特徴とする方法。
【請求項４】
請求項１に記載の方法において、ステップ（ａ）及び（ｂ）は、仮に１つのタイムスロットにおいてブロックされている符号の数が閾値未満である場合にのみ、実施されることを特徴とする方法。
【請求項５】
請求項１に記載の方法において、前記再割り当て済み符号の数は、制限されることを特徴とする方法。
【請求項６】
請求項１に記載の方法において、前記第１の拡散率は、最大拡散率であることを特徴とする方法。
【請求項７】
ＲＲＭ（radio resource management）装置を有するＲＮＣ（radio network controller）であり、ＯＶＳＦ（orthogonal variable spreading factor）符号木の表現を記憶するためのメモリを有するＲＮＣであり、前記ＯＶＳＦ符号木が、異なる拡散率の複数の符号を有し、かつ、これら異なる拡散率の複数の符号の間にブランチを有し、仮に前記符号が割り当てられた場合には、当該符号とブランチを介して接続された符号のうちの拡散率がより小さい符号の割り当てをブロックし、仮に前記符号がブロックされた場合には、当該符号とブランチを介して接続された符号のうちの拡散率がより小さい符号の割り当てをブロックするＲＮＣであって、
最大拡散率から開始して、
（ａ）当該拡散率を有する選択済み割り当て済み符号であって、前記ＯＶＳＦ符号木の所望の方向にある当該拡散率を有する他の符号に再割り当てすることができる符号を決定し、
（ｂ）前記選択済み割り当て済み符号を前記他の符号に再割り当てし、かつ、他の拡散率について、上記（ａ）及び（ｂ）を繰り返す
ことを特徴とするＲＮＣ。
【請求項８】
請求項７に記載のＲＮＣにおいて、前記他の符号は、前記選択済み符号と同じタイムスロットにおける符号であることを特徴とするＲＮＣ。
【請求項９】
請求項７に記載のＲＮＣにおいて、前記他の符号の少なくとも１つは、前記選択済み符号と異なるタイムスロットにおける符号であることを特徴とするＲＮＣ。
【請求項１０】
請求項７に記載のＲＮＣにおいて、前記（ａ）及び（ｂ）は、仮に１つのタイムスロットにおいてブロックされている符号の数が閾値未満である場合にのみ、行われることを特徴とするＲＮＣ。
【請求項１１】
請求項７に記載のＲＮＣにおいて、前記再割り当て済み符号の数は、制限されることを特徴とするＲＮＣ。
【請求項１２】
請求項７に記載のＲＮＣにおいて、前記ＯＶＳＦ符号木の前記表現は、ベクトルとして記憶されることを特徴とするＲＮＣ。
【請求項１３】
請求項１２に記載のＲＮＣにおいて、前記ベクトルは、前記ＯＶＳＦ符号木の各符号ごとに順次１つの要素を含むことを特徴とするＲＮＣ。
【請求項１４】
請求項１３に記載のＲＮＣにおいて、同じ拡散率を有する前記ＯＶＳＦ符号の要素は、全て、連続していることを特徴とするＲＮＣ。
【請求項１５】
請求項１３に記載のＲＮＣにおいて、各要素は、２つのビットを有し、これら２つのビットの一方のビットは、その要素の前記符号がブロックされているか否かを示し、他方のビットは、その要素の前記符号により１つ又は複数の符号がブロックされているか否かを示すことを特徴とするＲＮＣ。
【請求項１６】
ＯＶＳＦ（orthogonal variable spreading factor）符号木の符号を、割り当て、割り当て解除、又は更新する方法であって、前記ＯＶＳＦは、階層構造を有し、隣り合う階層において下位の階層の拡散率が上位の階層の拡散率の２倍である方法であって、
前記ＯＶＳＦ符号木の隣り合う階層において下位の階層が上位の階層に対して少なくとも２倍となる数値を、前記符号にそれぞれ提供するステップと、
前記数値を有する符号を用いて、ＯＶＳＦ符号木の符号を、割り当て、割り当て解除、又は更新するステップと
を備えたことを特徴とする方法。
【請求項１７】
請求項１６に記載の方法において、前記符号にそれぞれ提供するステップは、各ノードがチャネル化符号を表し、各ノードに数値を提供する２分木を使用するステップを含み、
前記最小拡散率の数値は、１つであり、
その親ノードの２倍の数値か、又はその親ノードの２倍の数値に１を加えたものに等しい数値が、各親ノードの２つの子ノードに割り当てられる
ことを特徴とする方法。
【請求項１８】
請求項１６に記載の方法において、指定された符号の状態が変化したとき、前記指定された符号の符号数値の２倍の符号数値と、前記指定された符号に１を加えた符号数値の２倍の符号数値と、を有する符号を更新することを特徴とする方法。
【請求項１９】
請求項１６に記載の方法において、指定された符号の状態が変化したとき、前記指定された符号の符号数値の半分未満の整数の符号数値を有する符号を更新することを特徴とする方法。
【請求項２０】
請求項１６に記載の方法において、拡散率１の符号は、符号数値が１であり、拡散率２の符号は、符号数値が２及び３であり、拡散率４の符号は、符号数値が４、５、６、及び７であり、拡散率８の符号は、符号数値が８、９、１０、１１、１２、１３、１４、及び１５であり、拡散率１６の符号は、符号数値が１６、１７、１８、１９、２０、２１、２２、２３、２４、２５、２６、２７、２８、２９、３０、及び３１であることを特徴とする方法。
【請求項２１】
符号割り当てで使用するためＯＶＳＦ（orthogonal variable spreading factor）符号木おける符号を識別する方法であり、前記ＯＶＳＦ符号木が階層構造を有し、隣り合う階層において下位の階層の拡散率が上位の階層の拡散率の２倍である方法であって、
前記ＯＶＳＦ符号木において同じ拡散率を有する符号が連続するように各符号をシーケンシャルに番号付けするステップ
を備えたことを特徴とする方法。
【請求項２２】
請求項２１に記載の方法において、前記シーケンシャルに番号付けした番号は、最小拡散率を有する符号であって１と識別される符号から開始することを特徴とする方法。
【請求項２３】
符号割り当てで使用するためＯＶＳＦ（orthogonal variable spreading factor）符号木における各符号の利用可能性を示す方法であって、
各符号に識別子を割り当てるステップであって、前記識別子が、２つのビットを有し、これら２つのビットのうちの一方のビットが、前記符号が別の符号の使用によりブロックされているか否かを示し、他方のビットが、前記符号が１つ又は２つの符号によりブロックされているか否かを示すステップ
を備えたことを特徴とする方法。
【請求項２４】
請求項２３に記載の方法において、前記一方のビットは、前記符号がブロックされていないこと示す値である０を有し、前記符号がブロックされていることを示す値である１を有し、前記他方のビットは、前記符号が１つの符号によりブロックされていることを示す値である０を有し、前記符号が２つの符号によりブロックされていることを示す値である１を有することを特徴とする方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ワイヤレス通信システムに関する。特に、本発明は、このようなシステムでの符号割り当てに関する。
【背景技術】
【０００２】
ＣＤＭＡ（code division multiple access）通信システムでは、通信は共用周波数スペクトルを介して送信される。伝送信号間の相互干渉を最小化するため、直交符号が使用されている。直交符号を用い、理想ワイヤレスチャネルを介して送信される通信においては、相互符号相関（cross code correlation）はないが、実際には、マルチパスがあるため、当該符号の直交性が幾分損なわれる。
【０００３】
図１は、ＯＳＶＦ（orthogonal variable spreading factor）の符号木を示す図である。この符号木においては、最上位にある符号は、拡散率１の符号である。当該符号の１つ上位の符号は、その拡散率が当該符号の拡散率の２倍になっている。３ＧＰＰ（third generation partnership project）のＷＣＤＭＡ（wideband code division multiple access）通信システムのＴＤＤ（time division duplex）モードの符号木にあっては、最大拡散率は、図１に示すように１６である。他のシステムにおいては、最大拡散率を２５６又は５１２のような極めて大きな値とすることができる。
【０００４】
図１は最大拡散率が１６であるＯＶＳＦ符号木を示す。このＯＶＳＦ符号木においては、拡散率が１の符号が１つ存在し、値が「１」であるＣ１（１）がそうである。値が「１，１」であるＣ２（２）と、値が「１，−１」であるＣ２（１）との２つの符号は、拡散率が２の符号である。Ｃ４（４）からＣ４（１）までの４つの符号は、拡散率が４である。Ｃ８（８）からＣ８（１）までの８つの符号は、拡散率が８である。Ｃ１６（１６）からＣ１６（１）までの１６個の符号は、拡散率が１６である。
【０００５】
ＯＶＳＦ符号木において、ラインで接続されている符号どうしは、相互に直交していない符号である。当該符号より上位にある符号のみか又は下位にある符号のみが、ラインで接続されている場合には、これら符号は互いに直交していない。これを説明するに、符号Ｃ１６（１６）から符号Ｃ２（２）へは、符号Ｃ１６（１６）より上位にある各符号を３本のラインを辿って至るから、符号Ｃ１６（１６）は符号Ｃ２（２）と互いに直交していない。これに対して、符号Ｃ１６（１６）から符号Ｃ８（７）へは、まず、符号Ｃ１６（１６）からこの符号より上位の符号に２本のラインを辿って至り、次に、この符号から１本のラインを辿って下位のＣ８（７）に至るから、符号Ｃ１６（１６）と符号Ｃ８（７）は互いに直交していない。
【０００６】
通信間干渉を最小化するには、互に直交している符号のみを割り当てることが望ましい。また、最大数の直交符号が使用できるような最適な方式で、符号を割り当てることも望ましい。運用中のワイヤレス通信システムにあっては、符号割り当て及び割り当て解除において、システム容量が低減する不適正な符号割り当てが行われる。
【０００７】
図２Ａは不適正なＯＶＳＦ符号割り当てを示す図である。ＯＶＳＦ符号を使用する上での問題は、１つに、ＯＶＳＦ符号を効率的に使用する点にある。符号割り当て後及び割り当て解除後においても、符号Ｃ１６（１６）、符号Ｃ１６（１３）、符号Ｃ１６（９）、及び符号Ｃ１６（５）は、依然としてアクティブである。アクティブである符号は図において黒丸で示す。これらの符号に直交しない符号が割り当てられないように、これらの符号の上位にある符号、図においてＸで示す符号は、すべて、割り当てがブロックされる。したがって、Ｃ１６（５）が使用されれば、Ｃ８（３）、Ｃ４（２）、Ｃ２（１）、Ｃ１（１）の割り当てがブロックされる。図２Ａにおいては、Ｃ１（１）、Ｃ２（１）、Ｃ２（２）、Ｃ４（２）、Ｃ４（３）、Ｃ４（４）、Ｃ８（３）、Ｃ８（５）、Ｃ８（７）、及びＣ８（８）の合計１０個の符号が、割り当てがブロックされる。拡散率（ＳＦ）１６の４つの符号が割り当てられると、ＳＦ２の符号は使用できず、ＳＦ４の１つの符号のみが利用できることになる。したがって、ＳＦ２の符号か、又は複数のＳＦ４の符号を必要とするサービスを、サポートすることはできない。
【０００８】
図２ＢはＳＦ１６の４つの符号を効率的に割り当てた例を示す。符号Ｃ１６（１６）からＣ１６（１３）までが使用されている。このように割り当てると、Ｃ１（１）、Ｃ２（２）、Ｃ４（４）、Ｃ８（８）、及びＣ８（７）の５つの符号のみが、割り当てがブロックされる。その結果、追加のサービスをサポートするため、ＳＦ２の１つの符号が利用可能であり、かつＳＦ４の４つの符号が利用可能である。図２Ｂに示した割り当ては、図２Ａに比較して、符号割り当てに対する許容範囲が広い。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
したがって、符号割り当ての代替の手法を有することが望ましい。
【課題を解決するための手段】
【００１０】
本発明は、ＯＶＳＦ符号割り当てと、割り当て解除（de-allocation）と、符号木プルーニングとのシステム及び方法を含む。本発明は、ＯＶＳＦ符号識別及び格納方式も含む。符号木プルーニングと、符号割り当てと、割り当て解除との実施形態が提供される。これら実施形態は、slottedＣＤＭＡシステムにも、non-slottedＣＤＭＡシステムにも適用される。
【発明を実施するための最良の形態】
【００１１】
以下で、ＷＴＲＵ（wireless transmit/receiver unit）には、ＵＥ（user equipment）、移動局、固定若しくは移動加入者ユニット、ページャ、又はワイヤレス環境で動作する能力を有する他の種類のデバイスが、含まれるが、これらに限定されない。
【００１２】
図３は、ＯＳＶＦ符号割り当てを用いたワイヤレス通信システムを示す簡略図である。ＲＮＣ（radio network controller）２６は、符号の割り当て及び割り当て解除に使用されるＲＲＭ（radio resource management）装置４６を有している。ＲＲＭ装置４６は、符号割り当てその他の情報を格納するのに使用するため関連付けさられたメモリを有する。ノードＢは、ＲＲＭ装置４６からリソース割り当てを受け取る符号割り当て装置４２を有する。符号割り当て装置４２は、符号を、アップリンク（ＵＬ）、ダウンリンク（ＤＬ）、又はこれら両方の通信に割り当てる。送信機（ＴＸ）４０は、ワイヤレスインタフェース２２の１つまたは複数のダウンリンクチャネル３６を介して、通信を転送するため、ダウンリンク符号割り当てを使用する。受信機（ＲＸ）３８は、１つまたは複数のアップリンクチャネル３４を介して、通信を受信するため、アップリンク符号割り当てを使用する。ＷＴＲＵ２０は、アップリンク符号及びダウンリンク符号を割り当てる符号割り当て装置３２を有する。符号割り当てをＲＲＭ装置４６からＷＴＲＵ２０にシグナルすることができる。ＴＸ２８はアップリンク通信を送信するためアップリンク符号割り当てを使用し、ＲＸ３０はダウンリンク通信を受信するためダウンリンク符号割り当てを使用する。
【００１３】
以下に、ＯＳＶＦ符号の割り当て及び／又は再割り当ての実施形態を説明する。図４は符号木の符号を識別する好ましい技法を示す。図４においては、符号には識別用の連番が付してある。連番１が、拡散率１の符号であるＣ１（１）に付してある。拡散率２の符号については、連番２がＣ２（２）に、連番３がＣ２（１）に付してある。拡散率４の符号については、連番４がＣ４（４）に、連番５がＣ４（３）に、連番６がＣ４（２）に、連番７がＣ４（１）に、付してある。拡散率８の符号については、連番８がＣ８（８）に、連番９がＣ８（７）に、連番１０がＣ８（６）に、連番１１がＣ８（５）に、連番１２がＣ８（４）に、連番１３がＣ８（３）に、連番１４がＣ８（２）に、連番１５がＣ８（１）に、付してある。拡散率１６の符号については、連番１６がＣ１６（１６）に、連番１７がＣ１６（１５）に、連番１８がＣ１６（１４）に、連番１９がＣ１６（１３）に、連番２０がＣ１６（１２）に、連番２１がＣ１６（１１）に、連番２２がＣ１６（１０）に、連番２３がＣ１６（９）に、連番２４がＣ１６（８）に、連番２５がＣ１６（７）に、連番２６がＣ１６（６）に、連番２７がＣ１６（５）に、連番２８がＣ１６（４）に、連番２９がＣ１６（３）に、連番３０がＣ１６（２）に、連番３１がＣ１６（１）に、付してある。拡散率が１６を超えるＦＤＤ／ＣＤＭＡのようなシステムは、拡散率に応じて符号木を拡張することができる。図４に示す番号方式は１つの例であって、他の番号方式も使用することができる。符号木において、上位の階層から下位の階層に至る各階層の符号を右から左に、順次、連番を付すことができる。
【００１４】
これら連番は、図４の下段に示すように、拡散率順にグループ化することができる。例えば、符号識別子ＳＦ１６は、連番１６から連番３１までのグループ化されたものに付されている。このような符号識別子技法を使用すれば、符号割り当てを記憶するための記憶可能容量（storage space）を軽減させることができる。このように符号割り当てをした記憶空間の例を図５に示す。１から３１までの連番は、符号の現在のステータス、例えば「currently assigned（現在割り当てられている）」、「blocked（ブロックされている）」、又は「available（利用可能である）」を示すために関連付けされたビットまたはワードである、４８１から４８３１を有する。「blocked」符号とは、「currently assigned」符号が別にあるため割り当てることのできない符号をいう。例えば、Ｃ８（１）については、仮にＣ１６（１）、Ｃ１６（２）、Ｃ４（１）、Ｃ２（１）、又はＣ１（１）のいずれかが使用されている場合には、ステータスがblockedである。追加のステータス情報、例えば、blocked符号の数を示す標識も提供することができる。
【００１５】
この符号識別記憶アプローチによれば、リストまたはテーブルを利用しなくても、本質的に簡潔なベクトルが、符号割り当て情報を含むことができる。しかしながら、ベクトル、テーブル、リストその他の記憶技法と共に使用するため、次のような符号割り当てアプローチを使用し適合させることができる。
【００１６】
１つの好ましい符号ステータスワードは、２つのビット要素が使用されている。第１のビットは、その符号がブロックされているか否かを示すためのものである。「０」は、符号のステータスがblockedでないことを示し、「１」は、符号のステータスがblockedであることを示す。第２のビットは、符号が、その部分木中の１つの符号により、blockedであるか、あるいは、その部分木中の両方の符号により、blockedであることを示す。「０」は、１つの符号を示し、「１」は、２つの符号を示す。例えば、仮に符号８が使用され、符号９が空いている場合には、符号４は、１つの符号のみによりblockedとなるから、符号ステータスワードは「１０」となる。仮に符号８と符号９とが使用されている場合には、符号４は、その部分木中の両方の符号によりblockedとなるから、符号ステータスワードは「１１」となる。仮に符号がcurrently assignedである場合には、符号ステータスワードは「１１」となる。符号ステータスワードが「０１」であるときは、好ましくは、その符号をそのタイムスロット（ＴＳ）で使用することができないことを示す。
【００１７】
図６は、ＴＤＤ／ＣＤＭＡのようなslottedＣＤＭＡ通信システムにおいて使用するための好ましい木プルーニングアプローチである。木プルーニングとは、将来の符号割り当てをより柔軟に行うことができるようにするための符号再割り当てをいう。次に、左から右に符号プルーニングを行う例を説明するが、他の符号割り当て順序、例えば右から左に、行うこともできる。
【００１８】
新規のコール（call）があると、複数の符号がこのコールに割り当てられる（ステップ１００）。割り当て及び再割り当てを行うため、当該プルーニングが、タイムスロットセットの第１タイムスロットから開始される。例えば、スロット２、スロット３、スロット６、スロット１０を、アップリンク伝送のために使用することができるＴＤＤ／ＣＤＭＡシステムにおいては、スロット２を第１スロットと、スロット４を第２スロットと、等々と、考えることができる。タイムスロットセットの第１タイムスロットにおいて、最大拡散率（ＳＦ）を有する最左端のavailable符号を評価する（ステップ１０２）。仮にこの第１タイムスロットにおいて、このＳＦを有するavailable符号がない場合には、符号が見つかるまで、このタイムスロットセットの他のタイムスロットにおいて、サーチする。図６の流れ図においては、拡散率の処理を最大拡散率から最小拡散率に至る順番で行うが、拡散率の処理を、最小拡散率から最大拡散率に至る順番で、又は別の順番で、行うこともできる。
【００１９】
符号が見つかると、当該タイムスロットが、左方に移動できるタイムスロットであれば、当該タイムスロットにおいて最大ＳＦの符号を判定する（ステップ１０４）。判定した最大ＳＦの符号を左方にリロケート（relocate）する（ステップ１１０）。その他に左方に移動できる符号があれば、これらの符号もリロケートする（ステップ１１２）。リロケーション手順を、次のタイムスロットにおいて、繰り返す（ステップ１０６及び１０８）。仮に評価するタイムスロットがなくなった場合には、次に高い拡散率を、左方にリロケートする（ステップ１１４及び１１８）。最小拡散率、例えばＳＦ１に至るまで、このプロセスを繰り返す（ステップ１１６）。ＳＦが１である符号がリロケートされず、このプロセスが終了する、のが好ましい。
【００２０】
図６のアルゴリズムは新規のコールごとにインボークされるのが好ましい。要約すると、このアルゴリズムは、符号木プルーニングが、最下位の符号から開始され、最右端のタイムスロット及び符号から開始される。仮に、当該符号が左側の他の任意の場所にリロケートできる場合には、当該符号が移動される。最下位の全てのavailable符号が移動されると、アルゴリズムは、１つ上の階層に移動して同じ手順を繰り返す。この手順は、最上位から１つ下の階層に至るまで、続く（すなわち、ＴＤＤの場合には、典型的には、ＳＦ１の符号はリロケートする必要がない）。
【００２１】
図７に図示の別のアプローチにおいては、符号木プルーニングは、個々のタイムスロットにおいて行うものとする。この符号アプローチは、non-slottedシステムにも適用することができる。新規コールに符号を割り当てた（ステップ１２０）後で、最大ＳＦを有する最右端の符号を選択する（ステップ１２２）。最右端の最大ＳＦの符号を、左方にリロケートできる場合には（ステップ１２４）、この符号を左方にリロケートする（ステップ１３０）。別の最大ＳＦの符号を左方にリロケートできる場合には（ステップ１３２）、これら符号をリロケートする（ステップ１３０）。左方へのリロケートを、各拡散率について繰り返す（ステップ１２６）。最小ＳＦ、例えばＳＦ１に至ると（ステップ１２８）、この手順を終了する。
【００２２】
要約すると、新規にコールが到着するたびに、図７のアルゴリズムがインボークされる。このアルゴリズムによれば、最下位の階層の符号で最右端の符号から符号木プルーニングが開始される。仮に符号を左側の他の任意の場所にリロケートできる場合には、この符号を移動する。好ましいアプローチにおいては、各符号は可能な限り左側にリロケートされる。最下位の階層にある全てのavailable符号が移動されると、アルゴリズムは１つ上の階層に移動し、同じ手順を繰り返す。この手順を、最上位に至る１つ前の階層まで、続行する。
【００２３】
図８は符号木プルーニングの別の好ましいアルゴリズムを示す。このアルゴリズムにおいては、周期的に動作し、最大リロケート回数が制限される。このようなアプローチによれば、必要な全体処理が軽減される。再割り当てに伴うオーバーヘッドも低減される。このアルゴリズムにおいては、符号木の符号断片化も考察されている。符号木の断片化は、この符号木のblocked符号の数の尺度である。このアプローチについては、slottedＣＤＭＡシステムにおけるその好ましい適用例を用いて説明するが、これはnon-slottedシステムにも適用することができる。
【００２４】
ある数、例えば「Ｘ」のコールの到着があると（ステップ１３４）の後で、このアルゴリズムがインボークされる。このアルゴリズムは、まず、各タイムスロットにおいて、符号木の断片化をルック（look）する。仮に符号木の少なくとも１つの断片化が、ある閾値、例えばＴを超える場合には（ステップ１３６）、このアルゴリズムは、符号木プルーニングを、最下位の階層の符号から開始し、最右端のタイムスロット及び符号から開始する（ステップ１３８）。仮に符号を左方の他の任意の場所にリロケートできる場合には（ステップ１５０）、この符号を移動し、変数「Num_reall」によってトラッキングされるようなカウンタであって、リロケート回数をトラッキングできるカウンタを、更新する。最大リロケート回数になった場合には（ステップ１５２）、このアルゴリズムが終了する。他方、最大リロケート回数に到達しない場合には、このアルゴリズムは続行する。仮に最大拡散率の符号が可能な限り移動されると（ステップ１５４及び１４２）、このアルゴリズムは次に高い拡散率に移って、同じ手順を繰り返す（ステップ１４６及び１４８）。この手順を、最小拡散率に至るまで各拡散率について繰り返す（ステップ１４８、１５６）。
【００２５】
これら符号管理スキームを変形したものも使用することができる。小さいＳＦを有する符号は、右から左に割り当てることができるが、大きいＳＦを有する符号は、左から右に割り当てることができるから、同様のサービスのための符号が同一のタイムスロットに集中することになる。この符号木プルーニングアルゴリズムは、大きいＳＦ又は小さいＳＦのいずれかを要求する到着に、優先権を付与するため、この符号管理スキームを利用することができる。
【００２６】
図９はＯＶＳＦ符号を割り当てるための好ましいアルゴリズムを示す。このアルゴリズムは、ＴＤＤ／ＣＤＭＡのアップリンク符号割り当てにおいて、好ましい用途があるが、他の用途にも使用することができる。この好ましいアルゴリズムは、前述した２つのビット要素により構成されたステータス符号を有する符号ベクトルと、図４の符号木とを使用する。
【００２７】
まず、例えば変数「ｘ」をＱに設定する（ステップ２００）。ここに、Ｑは、割り当てを必要とする符号のＳＦである。符号木において、このＳＦを有する最初のノードがfree（ｖ（ｘ）＝「００」）か否かをチェックする（ステップ２０２）。最初のノードがfreeである場合には、親ノード（より小さい拡散率を有するノード）がblockedである（「１０」）か否かをチェックする（ステップ２０４）。この親ノードがblockedである場合には、ノードｘが割り当てられる（ステップ２１６）。この割り当てを表す変数「Ｓ」を、「ｘ」に設定し（ステップ２１８）、このアルゴリズムはステップ２２０に進む。
【００２８】
この親ノードがblockedでない場合には、この親ノードを割り当てることが、適正でない（「non_optimal」＝「ｘ」）可能性がある（ステップ２０６）。次のノードをチェックする（ｘ＝ｘ＋１）（ステップ２０８）。次のノードが同じＳＦ（ｘ＜２＊Ｑ）を有する場合には（ステップ２１０）、このアルゴリズムはステップ２０２に進んで、このノードが適正か否かを判定する。適正でない場合には、「non_optimal」ノードを、割り当てのために選択する（ステップ２１２）。変数「Ｓ」を「non_optimal」に設定し（ステップ２１４）、このアルゴリズムはステップ２２０に進む。
【００２９】
ノードＳの要素に、assigned（すなわち、ｖ（Ｓ）＝「１１」）とマーク付けされる（ステップ２２０）。assignedとマーク付けされたノードより小さいＳＦを有する接続されたノードが更新される（UpNode＝［ｓ／２］）（ステップ２２２）。UpNode＝０の場合、すなわち、すべてのノードが更新されている場合（ステップ２２４）、このアルゴリズムはステップ２３４に進む。他方、そうではなく、このノードがavailableであることを示すｖ（UpNode）＝「００」である場合には（ステップ２２６）、このノードはblockedにされる（ｖ（UpNode）＝「１０」）（ステップ２２８）。次に上位の（より小さいＳＦを有する）ノードをチェックする（UpNode＝［UpNode／２］）（ステップ２３０）。ｖ（UpNode）＝「１１」（そのノードが、１つの符号によりblockedとなったいたが、現在、２つの符号によりblockedになっていることを示す）（ステップ２３２）である場合には、符号木を上方に進む手順を終了する（ステップ２３４）。
【００３０】
このアルゴリズムは次に符号木を下方に向かって更新する（DownNode＝Ｓ＊２に初期設定する）（ステップ２３６）。現在のノードより下位のチェックされるノード数は２である（number_nodes＝２に初期設定する）（ステップ２３８）。このアルゴリズムは、符号木の最下位に至っていない（DownNode＜３２）ことをチェックする（ステップ２４０）。最下位に至っていた場合には、この更新が完了する（ステップ２５４）。他方、最下位に至っていない場合には、カウントが初期設定される（count＝０に初期設定する）（ステップ２４２）。カウントにより指示されるノードが、blockedにされる（ｖ（DownNode＋count）＝「１１」）（ステップ２４４）。このアルゴリズムはカウントをインクリメントし、次のノードに進む（count＝count＋１）（ステップ２４６）。count＜number_nodesである場合には（ステップ２４８）、このアルゴリズムは次のノードをチェックし、ステップ２４４に進む。他方、count≧number_nodesである場合には、このアルゴリズムは、符号木の１つ下の階層をチェックする（DownNode＝２＊DownNode）（ステップ２５０）。チェックされるノードの数が２倍にされる（number_nodes＝２＊number_nodes）（ステップ２５２）。
【００３１】
図１０は、符号が割り当て解除された（割り当て解除された）後で符号木を更新する好ましいアルゴリズムを示す。変数「Ｓ」が、割り当て解除されるノードの値に設定される（ステップ２５６）。このノードＳがfree（すなわち、ｖ（Ｓ）＝「００」）とマーク付けされる（ステップ２５８）。符号木のより上位のノードが更新される（UpNode＝［ｓ／２］）（ステップ２６０）。このアルゴリズムは、符号木の最上位に至ったか否か（UpNode＝０）をチェックする（ステップ２６２）。符号木の最上位に至った場合には、符号木の下位のノードがチェックされる（ステップ２７２）。他方、符号木の最上位に至っていない場合には、現在のノードが、１つの符号により、blockedにされ（ｖ（UpNode）＝「１０」）（ステップ２６４）、このノードがavailable（すなわち、ｖ（UpNode）＝「００」）とマーク付けされる（ステップ２６６）。このアルゴリズムは、引き続き、符号木の次に上位のノードのチェックに進み（UpNode＝［UpNode／２］）（ステップ２６８）、このノードをチェックする。このノードが２つの符号によりblockedである場合には、このノードを、１つのノードによりblockedである（ｖ（UpNode＝「１０」）と設定される（ステップ２７０）。
【００３２】
符号木の下方に向かって更新するため、「DownNode」変数が初期設定される（DownNode＝Ｓ＊２）（ステップ２７４）。当該ノードより下位のチェックされるノード数が初期設定される（number_nodes＝２）（ステップ２７６）。符号木の最下位に至った場合には（DownNode≧３２）、符号木は更新済みである（ステップ２９２）。そうでない場合には（DownNode＜３２）、カウントが初期設定される（count＝０）（ステップ２８０）。カウントにより指示されたノードが、割り当てのために解放される（ｖ（DownNode＋count）＝「００」）（ステップ２８２）。カウントがインクリメントされる（count＝count＋１）（ステップ２８４）。カウントが更新ノード数を超えていない場合には（count＜number_nodes）、次のカウントにおいて、更新が行われる（ステップ２８６）。カウントが更新ノード数を超えていた場合には（count≧number_nodes）、符号木の下方に向かって次の位がチェックされる（DownNode＝２＊DownNode）（ステップ２８８）。分析されるノードの数は、上位にあるノードの数の２倍であり（number_nodes＝２＊number_nodes）（ステップ２９０）、更新が繰り返される。
【００３３】
本発明の一実施形態は、３ＧＰＰ  Ｗ−ＣＤＭＡのＴＤＤモードのデフォルトミッドアンブル割り当てスキームでの符号割り当てに関するものである。ミッドアンブルは、ＴＤＤの物理チャネル構成の一部である。ＴＤＤには様々なミッドアンブル割り当てスキームが存在する。１つのスキームは、ＷＴＲＵ固有ミッドアンブル割り当てスキームであり、アップリンクとダウンリンクの両方に適用される。ＷＴＲＵ固有ミッドアンブル割り当てスキームでは、特定のユーザのすべての物理チャネルに特定のミッドアンブルが明示的に割り当てられる。別のスキームは、デフォルトミッドアンブル割り当てスキームであり、やはり、アップリンクとダウンリンク両方に適用される。このスキームでは、使用されるミッドアンブルは、ミッドアンブルと割り当てチャネル化符号との間の事前定義の関連付けにより決定される。
【００３４】
別のスキームは、共通（common）ミッドアンブル割り当てスキームであり、ダウンリンクのみに適用される。このスキームでは、共通ミッドアンブルが、特定のタイムスロットにおけるすべての物理チャネルに割り振られる。ＷＴＲＵ固有ミッドアンブルスキームと、共通ミッドアンブルスキームでは、符号は、ミッドアンブル割り当てを考慮せずにユーザに割り当てられ得る。
【００３５】
しかしながら、デフォルトミッドアンブルでは、ミッドアンブルとチャネル化符号との間の関連付けが、符号割り当てスキームで使用される。標準により定義されるバーストタイプ及びKcellの値に応じて、異なる関連付けが行われる。バーストタイプ及びKcellの値は、各タイムスロットごとに、ＲＮＣにおいて、例えば運用保守（Ｏ＆Ｍ）機能により個々に構成可能であり、あるいは、ＲＮＣ（radio network controller）の機能、例えばＲＲＭ（radio resource management）動的チャネル割り当て（ＤＣＡ）により個々に構成可能である。この構成は、ＲＲＣシグナリングによりＷＴＲＵにシグナルされるから、この関連付けはＷＴＲＵに知られる。
【００３６】
デフォルトミッドアンブル割り当てスキームにおいては、ミッドアンブルとチャネル化符号との間の関連付けによって、１次及び２次チャネル化符号が定義される。次のような規則が適用される。各２次チャネル化符号は単一の１次チャネル化符号と関連付けられる。各２次チャネル化符号は、それが関連付けられた１次チャネル化符号と同じミッドアンブルを使用する。２次符号は、それに関連付けられた１次符号も割り振られる場合に限り、割り振ることができる。同じミッドアンブルに関連付けられたすべてのチャネル化符号は、同じＷＴＲＵにのみ割り振ることができる。共通ミッドアンブル割り当てと、ＷＴＲＵ固有ミッドアンブル割り当てとでは、すべての符号が１次符号であるとみなすことができる。
【００３７】
デフォルトミッドアンブルスキームでの符号割り当てを実施するため、各符号には、フラグと、ミッドアンブル識別子と、タグと、が追加されるのが好ましく、このフラグにより、当該符号が、１次チャネル化符号又は２次チャネル化符号のいずれであるかが示され、このミッドアンブル指定（符号グループ指定ともいうことができる）は（例えば、０からKcell−１まで）の異なるKcell値の１つを有し、このタグはＷＴＲＵ関連付けに使用される。
【００３８】
図１１は、デフォルトミッドアンブルスキームでの符号割り当てに使用するため、図９のステップ２００〜２２０と置換するための流れ図である。このＷＴＲＵ関連付けに使用されるタグは、各符号がすでに所与のミッドアンブルと関連付けられているから、各チャネル化符号ごとか、又は単に各ミッドアンブルごとに、設けることができる。ＷＴＲＵのミッドアンブルと関連付けすれば、このＷＴＲＵとの関連付けが示唆される。
【００３９】
この手順は、所定のユーザ（ＷＴＲＵ）に適正なavailable符号（「００」とマーク付けされた符号）を見つけ出そうとする。第１（最も望ましい）選択は、既にユーザに関連付けられているミッドアンブルに関連付けられた２次符号である。この種の符号はクラス１符号と分類される。第２の選択は、１つの符号により既にblockedになっている親（「１０」とマーク付けされた親）を有する１次符号である。この符号はクラス２符号と分類される。第３の選択は、blockedになっていない親を有する１次符号であり、これはクラス３符号と分類される。２次符号は、異なるユーザに属するミッドアンブルに関連付けられた場合には、割り当ては考慮されない。
【００４０】
最も好ましいアルゴリズムは、符号木においてこの階層の最左端の符号から開始して、左から右に走査するが、他の走査方向も使用することができる。各available符号ごとに、もしあれば、それがどのクラスに属するかが決定される。仮にクラス１が見つかった場合には、直ちに割り当てが行われる。そうでない場合には、クラス２及び／又はクラス３の最左端の符号が記憶される。これは、クラス１符号を見つけ出されずに、に走査が終了した場合に、割り当てを可能にするためである。
【００４１】
好ましいアルゴリズムでは、次のような変数が使用される。すなわち、クラス２の符号にはOptimal_Primaryが、クラス３の符号にはNon_Optimal_Primaryが、使用される。変数ｘが拡散率の値、ｘ＝Ｑで、初期設定される（ステップ３００）。Ｑは割り当て済み符号のＳＦである。Optimal_Primary及びNon_Optimal_Primaryがゼロに設定される。変数ｖ（ｘ）が「００」に等しいか否か、すなわち、freeであるか否かをチェックする（ステップ３０２）。ｘが２次符号であり（ステップ３０４）、かつ符号ｘに関連付けられたミッドアンブルがユーザに割り当てられている場合には（ステップ３０６）、選択された符号Ｓがｘに設定される（Ｓ＝ｘ）（ステップ３０８）。そして、このアルゴリズムはステップ３３６に進む。
【００４２】
仮にｘが２次ではなく１次であり（ステップ３１０）、かつOptimal_Primary＝０である（適正符号はまだ適正でない）場合には（ステップ３１２）、２次符号が見つからなかった場合に後で使用するため、最左端の１次符号が適正として保存される。親符号の１つのみがblockedである（ｖ（ｘ／２）＝「１０」）か否かをチェックする（ステップ３１４）。blockedである場合には、Optimal_Primaryが現在のｘに設定され（Optimal_Primary＝０）（ステップ３１６）、次の符号がチェックされる（ｘ＝ｘ＋１）（ステップ３２２）。親がblockedである場合には、非適正１次が見つかったか否かをチェックする（Non_Optimal_Primary＝０）（ステップ３１８）。この後、次の符号がチェックされる（ｘ＝ｘ＋１）（ステップ３２２）。
【００４３】
次の符号が同じ拡散率内にある場合（ｘ＜２＊Ｑ）（ステップ３２４）、次の符号に対してこの手順が繰り返され、このアルゴリズムはステップ３０２に進む。次の符号が同じ拡散率内にない場合には、適正１次符号が見つかったか否かがチェックされる（Optimal_Primary＝０）（ステップ３２６）。適正１次が見つかった場合には、この符号が適正１次に設定される（Ｓ＝Optimal_Primary）（ステップ３２８）。割り当てられた符号Ｓのミッドアンブルがユーザに割り当てられる（ステップ３３０）。
【００４４】
非適正１次が見つかった場合には（Non_Optimal_Primary＝０）（ステップ３３２）、Ｓがこの非適正１次に設定される（Ｓ＝Non_Optimal_Primary）（ステップ３３４）。割り当てられた符号Ｓのミッドアンブルがユーザに割り当てられる（ステップ３３０）。ミッドアンブルが割り当てられた後で、割り当てられた符号がassignedとマーク付けされ（ｖ（Ｓ）＝「１１」）（ステップ３３６）、これに従って符号木が更新される（ステップ３３８）。２次符号も１次符号もavailableでない場合には、符号を割り当てることができない（ステップ３４０）。
【００４５】
割り当て解除手順は、単に、符号木を更新するだけであるから、デフォルトミッドアンブル割り当ての場合には、１つのステップを付加することにより、前述の符号割り当て解除の手順を使用することができる。１次符号の割り当て解除の完了後に、この符号に関連付けられたミッドアンブルが、このユーザ（ＷＴＲＵ）との関連付けが解除される。
【００４６】
好ましくは、どの符号を割り当て解除するかを判定した後にこの手順をインボークするエンティティ（例えば、ワイヤレスリソース管理機能）が、仮に全ての２次符号が割り当てられない場合に、１次符号が割り当て解除されることを、保証する。１次符号に関連付けされた２次符号がまだ割り当てられているときに、この１次符号が割り当て解除されないことをベリファイするステップを、任意選択であるが、割り当て解除手順の最初に付加することができる。任意の関連付けされた２次符号がまだ割り当てられている場合には、割り当て解除手順は、終了して、符号割り当てが失敗したことを示すことになる。
【図面の簡単な説明】
【００４７】
【図１】符号木を示す図である。
【図２Ａ】符号割り当て及びこの結果生じるブロックされた符号を示す図である。
【図２Ｂ】符号割り当て及びこの結果生じるブロックされた符号を示す図である。
【図３】符号割り当てシステムを示す簡略化した構成図である。
【図４】好ましい符号識別スキームを示す図である。
【図５】符号ベクトルを示す図である。
【図６】複数のタイムスロット上での符号符号木プルーニングを示す流れ図である。
【図７】符号符号木プルーニングを示す流れ図である。
【図８】周期的符号符号木プルーニングを示す流れ図である。
【図９Ａ】符号割り当て及び符号木更新手順を示す流れ図である。
【図９Ｂ】符号割り当て及び符号木更新手順を示す流れ図である。
【図１０Ａ】符号割り当て解除及び符号木更新手順を示す流れ図である。
【図１０Ｂ】符号割り当て解除及び符号木更新手順を示す流れ図である。
【図１１Ａ】デフォルトミッドアンブル符号割り当てスキームと共に使用するため、図
【図１１Ｂ】デフォルトミッドアンブル符号割り当てスキームと共に使用するため、図８を変更した流れ図である。
【図１】
2005533455.tif 000003
【図２Ａ】
2005533455.tif 000004
【図２Ｂ】
2005533455.tif 000005
【図３】
2005533455.tif 000006
【図４】
2005533455.tif 000007
【図５】
2005533455.tif 000008
【図６】
2005533455.tif 000009
【図７】
2005533455.tif 000010
【図８】
2005533455.tif 000011
【図９Ａ】
2005533455.tif 000012
【図９Ｂ】
2005533455.tif 000013
【図１０Ａ】
2005533455.tif 000014
【図１０Ｂ】
2005533455.tif 000015
【図１１Ａ】
2005533455.tif 000016
【図１１Ｂ】
2005533455.tif 000017
【国際調査報告】
2005533455.tif 000018