Brevet FR2784525A1 — publié le 20000414

Procédé d'allocation de codes orthogonaux dans un système de radiocommunications mobiles du type à accès multiple par répartition de codes utilisant des codes de longueur variable La présente invention concerne d'une manière générale les systèmes de communication dits à étalement de spectre, c'est-à-dire dans lesquels un étalement de spectre d'une séquence de données à transmettre est réalisé, en émission, au moyen d'un code d'étalement, et inversement, un désétalement est réalisé en réception, afin de retrouver la séquence d'origine. L'étalement d'une séquence de données incidente de N symboles, notée _0 (dl, d2,..., dN), par un code de longueur (ou facteur d'étalement) Q, noté cQ=(cl, c2,..., cQ), fournit une séquence de longueur Q.N, qui peut être représentée par: (dl.cl, dl.c2,..., dl.cQ, d2.cl, d2.c2,..., dN.cQ) o dl.cl représente la multiplication de dl par cl. Une représentation alternative de la séquence étalée de longueur Q.N est (dl.cQ, d2.CQ,... dN.cQ) o dl.cQ représente le produit du symbole dl par le code d'étalement CQ. Une approche plus générale de l'étalement consiste à avoir un code d'étalement différent pour chaque symbole de la séquence d'entrée, la séquence étalée résultante pouvant s'exprimer sous la forme: (dl.cQQ),d2. c2),...,dN.c())) Cl() étant le code d'étalement associé au symbole dl. De manière préférentielle, tous les codes d'étalement ont la même longueur Q afin que la séquence étalée résultante ait la longueur Q.N. La figure 1 rappelle le principe de l'étalement, TS désignant la période élémentaire (ou période symbole) d'une séquence non étalée, et Tc la période élémentaire (appelée aussi période "chip") d'une séquence étalée, Ts et Tc étant liés par la relation Ts = Q.Tc. Sur cette figure dn et dn+l correspondent à deux symboles successifs d'une séquence incidente non étalée, et d'l et d'l+l correspondent à deux symboles élémentaires (ou "chips") successifs d'un même symbole étalé de la séquence incidente. Un des intérêts de ces systèmes est de permettre à plusieurs utilisateurs de partager une même bande de fréquences, en allouant des codes distincts à ces différents utilisateurs. Une application importante est constituée par les systèmes cellulaires de radiocommunications mobiles dits à accès multiple par répartition de codes (ou AMRC, ou encore CDMA en anglais, pour "Code Division Multiple Access"). Dans ces systèmes, les codes sont avantageusement choisis orthogonaux deux à deux à l'intérieur d'une cellule, afin de réduire les interférences entre utilisateurs dans cette cellule (les interférences entre cellules pouvant par ailleurs être réduites suivant d'autres techniques connues). Des outils mathématiques ont été développés pour la génération de codes orthogonaux. On connaît ainsi les fonctions dites de Walsh, qui permettent de générer de façon récursive des codes orthogonaux de longueur Q à partir de codes orthogonaux de longueur Q/2, Q/4,...etc. Plus précisément, deux codes orthogonaux de longueur q sont obtenus à partir d'un code de longueur q/2, en juxtaposant à ce code de longueur q/2, respectivement ce code, et le code complémentaire. Dans les systèmes utilisant des codes orthogonaux de longueur Q fixe, l'allocation de codes orthogonaux peut alors être une opération relativement simple, consistant à sélectionner, parmi Q codes orthogonaux possibles de longueur Q, un code non utilisé à l'instant considéré. Un besoin existe par ailleurs dans les systèmes cellulaires de radiocommunications mobiles, qui est de transmettre des données de débit variable, notamment parce que le débit de l'utilisateur est lui-même variable (par exemple dans le cas de transmission de données de type multimedia), ou encore parce que, suivant les conditions de propagation des signaux radioélectriques, une redondance plus ou moins importante est à introduire dans les données à transmettre, en vue d'obtenir une protection plus ou moins grande contre les erreurs de transmission. Il est connu, pour permettre une augmentation de débit des données à transmettre par un utilisateur, pour une même bande de fréquences allouée (c'est- à-dire pour une même durée Tc), de réduire la longueur du code alloué à cet utilisateur afin qu'il continue à n'émettre que sur un code. Le principe d'une telle technique est rappelé sur la figure 2, qui utilise le même type de représentation que la figure 1, mais pour deux débits différents de la séquence incidente, repérés respectivement par des indices 1 et 2, en l'occurrence pour trois symboles successifs dn, dn+l et dn+2 de la séquence incidente, la période symbole correspondant à Tsl pour le symbole dn, et à Ts2 pour les symboles dn+l et dn+2, et la longueur de code correspondant à Ql pour le symbole dn, et à Q2 pour les symboles dn+l1 et dn+2. Ainsi sont connus des systèmes de radiocommunications mobiles utilisant des codes de longueur variable, typiquement des codes de Walsh, de longueur Q, Q/2, Q/4,...etc. On peut alors représenter ces différents codes sous forme d'arbre, chaque code donnant naissance, à l'intérieur de cet arbre, à deux codes de longueur double, de la manière rappelée plus haut. Un tel arbre est illustré sur la figure 3, o les différents codes sont notés Co), o Q représente la longueur du code et h le rang de ce code dans l'ensemble des différents codes possibles de longueur Q. Ainsi, sur la figure 3, les différents codes peuvent être notés de la façon suivante: hi=0 c= = (1) Q=I Ch=O C-= = ( 1,) h=l 1 5 C Q==4 =( l, l C-= = (1,-1) c-g=2 1.5 ch: = (1,1,1,1) Q=4 _h:l (1,1,-1,1) = (1,-1,1,- 1) h=3 Q=4 CQ= 4, 250 CQo = (1,-1,-11,1), h:2 Q=8 (,1,-1,-1,-1,-1) C Q=8 ó=3 (1,,-1,-1,-1,-1,1,],1) etc. Dans un tel arbre, l'orthogonalité entre codes de longueur différente n'est préservée qu'à la condition de respecter certaines règles d'allocation. Ainsi, un code donné ne peut pas être alloué à un instant donné s'il est lié de manière récursive à un code déjà alloué. Dans les systèmes utilisant des codes de longueur variable, l'allocation de codes orthogonaux constitue donc une opération relativement plus complexe que dans les systèmes utilisant des codes de longueur fixe. C Q=8 I :6 2 5 C Q=8,-t h:7 Q=s (, ,,,1 etc. Dans un tel arbre, I'orthogonalité entre codes de longueur différente n'est préservée qu'à la condition de respecter certaines règles d'allocation. Ainsi, un code donné ne peut pas être alloué à un instant donné s'il est lié de manière récursive à un code déjà alloué. Dans les systèmes utilisant des codes de longueur variable, l'allocation de codes orthogonaux constitue donc une opération relativement plus complexe que dans les systèmes utilisant des codes de longueur fixe. Le document US 5,751,761 enseigne ainsi d'établir, à chaque nouvelle demande d'allocation d'un code de longueur donnée, une liste comportant d'une part les codes déjà alloués à cet instant, d'autre part les codes qui leur sont liés de manière récursive, le code à allouer étant alors choisi comme un des codes ne figurant pas dans cette liste. Une telle solution a notamment pour inconvénient que l'établissement d'une telle liste est une opération longue et qui entraîne de multiples opérations d'écriture, dont le nombre croît par ailleurs avec la profondeur de l'arbre, c'est-à- dire avec la longueur maximale de code permise. La présente invention a notamment pour but d'éviter cet inconvénient. Un des objets de la présente invention consiste ainsi dans un procédé d'allocation de codes orthogonaux dans un système de radiocommunications mobiles du type à accès multiple par répartition de codes utilisant des codes de longueur variable dont le mode de génération est tel qu'ils' peuvent être représentés sous forme d'arbre, ce procédé étant essentiellement caractérisé en ce qu'il comporte, en réponse à une demande d'allocation de code, une étape, dite première étape, destinée à déterminer, en fonction de la capacité d'arbre utilisée, correspondant aux codes déjà alloués, et de la capacité d'arbre requise, correspondant à l'allocation de code demandée, si une telle allocation est possible. Suivant une autre caractéristique, si une telle allocation est déterminée possible à l'issue de ladite première étape, ledit procédé d'allocation comporte une étape, dite deuxième étape, de recherche de code à allouer. Suivant une autre caractéristique, si une telle allocation est déterminée possible à l'issue de ladite première étape, et si aucun code à allouer n'est trouvé à l'issue de ladite deuxième étape, ledit procédé comporte une étape, dite troisième étape, de ré-arrangement de codes alloués au sein dudit arbre. Ainsi, contrairement au cas du document cité précédemment, il n'est pas nécessaire d'établir à chaque nouvelle demande d'allocation la liste complète de tous les codes indisponibles, et notamment de rechercher tous les codes liés de manière récursive aux codes déjà alloués. Il suffit de rechercher si un code ayant la longueur souhaitée est disponible ou peut être rendu disponible par ré- arrangement de codes alloués au sein de l'arbre; dans le cas o un tel code est disponible ou peut être rendu disponible par un tel réarrangement, la recherche de code à allouer est effectuée en recherchant un code non déjà alloué et non lié de manière récursive à un code déjà alloué. Ainsi l'opération d'allocation est rendue moins complexe et plus rapide, d'o une simplification et une amélioration de la qualité de service. Contrairement aux systèmes utilisant des codes de longueur fixe, la notion de capacité prend ici en compte le fait que l'allocation d'un code donné rend ensuite indisponible, non seulement ce code, mais tous les codes qui lui sont liés de manière récursive au sein dudit arbre; c'est ce qui est ici entendu par l'expression " capacité d'arbre >>. Un autre objet de l'invention consiste dans une méthode particulièrement simple et rapide pour déterminer une telle capacité d'arbre, utilisée ou requise. Suivant une autre caractéristique, la capacité d'arbre, utilisée ou requise par un code de longueur Q, correspond à l'utilisation de (1/Q) ième de la capacité d'arbre totale. Avantageusement, suivant une autre caractéristique, ladite première étape comporte une comparaison de la somme S de la capacité d'arbre utilisée et de la capacité d'arbre requise, à un seuil de capacité T, correspondant à une capacité maximale susceptible d'être allouée. Suivant une autre caractéristique, ladite somme S s'exprime avantageusement sous la forme S= +Q o Nq désigne le nombre de codes déjà alloués de longueur q comprise entre 1 et QMox( Q,1, étant la longueur maximale de code permise), et Q désigne la longueur de code dont l'allocation est demandée(cette somme pouvant en outre être limitée à un sous-ensemble des entiers q compris entre 1 et QMoX, par exemple les q de cet ensemble qui sont une puissance de 2). Ainsi, ladite première étape consistant à déterminer si une allocation demandée est possible peut être effectuée de manière particulièrement simple et rapide. Avantageusement, ledit seuil peut être choisi adaptatif en fonction de divers paramètres caractéristiques du système considéré. De tels paramètres peuvent inclure notamment le niveau d'interférence mesuré ou estimé dans une cellule, le type de communications (circuit ou paquet) dans cette cellule, la qualité de service requise,...etc. Eventuellement ledit seuil peut être choisi de manière à ne jamais aboutir à la capacité maximale dudit arbre, notamment suivant les spécificités propres aux systèmes cellulaires de type CDMA, en termes de limitations du nombre d'utilisateurs acceptable (notamment en fonction du niveau d'interférence maximum entre cellules et de stabilité de contrôle de puissance). Suivant une autre caractéristique, I'allocation de certains codes et de leurs sous-arbres est interdite et ledit seuil s'exprime alors sous la forme T o QMo. désigne la longueur maximale de code permise. Suivant une autre caractéristique, ladite deuxième étape de recherche d'un code à allouer de longueur donnée, comporte elle-même: - une étape, dite première sous-étape, de recherche de trajet libre à l'intérieur de tout ou partie dudit arbre, de la racine de l'arbre jusqu'à un code ayant ladite longueur donnée, ce trajet libre ne devant comporter aucun autre code déjà alloué, - une étape, dite deuxième sous-étape, permettant de vérifier si aucun code n'est déjà alloué dans le sous- arbre ayant pour racine le code trouvé à l'issue de ladite première sous-étape. Avantageusement, un code étant repéré à l'intérieur dudit arbre par sa longueur de code et par le rang de ce code dans l'ensemble des différents codes ayant cette longueur de code, lesdites première et deuxième sous-étapes comportent un parcours de tout ou partie dudit arbre suivant une combinaison de longueurs de codes croissantes et de rangs variant suivant une loi prédéterminée, notamment croissante. Avantageusement encore, lesdites première et deuxième sous-étapes utilisent une numérotation binaire desdits rangs. D'autres objets et caractéristiques de la présente invention apparaîtront à la lecture de la description suivante d'un exemple de réalisation, faite en relation avec les dessins ci-annexés, dans lesquels: - la figure 1 est destinée à rappeler le principe de l'étalement de spectre, dans le cas de code d'étalement de longueur fixe, - la figure 2 est destinée à rappeler le principe de l'étalement de spectre, dans le cas de code d'étalement de longueur variable, - la figure 3 est destinée à illustrer la représentation de codes de longueur variable sous forme d'arbre, - la figure 4 est destinée à illustrer un procédé d'allocation de code suivant l'invention, - la figure 5 est destinée à illustrer un exemple de codes alloués, avant ladite étape de ré-arrangement de codes alloués au sein dudit arbre, - la figure 6 est destinée à illustrer un exemple de codes alloués, après ladite étape de ré- arrangement de codes alloués au sein dudit arbre, -la figure 7 est destinée à illustrer un exemple de réalisation de ladite étape de recherche de code à allouer, - la figure 8 est destinée à illustrer, sur un premier exemple, l'étape de recherche de code suivant la figure 7, - la figure 9 est destinée à illustrer, sur un deuxième exemple, l'étape de recherche de code suivant la figure 7, - la figure 10 est destinée à illustrer, sur un troisième exemple, I'étape de recherche de code suivant la figure 7. Suivant l'invention, telle qu'illustrée sur la figure 4, en réponse à une demande d'allocation d'un code de longueur donnée,notée A, on détermine, selon une première étape notée 20, en fonction de la capacité d'arbre utilisée, notée Cu, correspondant aux codes déjà alloués, et de la capacité d'arbre requise, notée Cr, correspondant à l'allocation de code demandée, si une telle allocation est possible. Si une telle allocation est possible, on recherche, suivant une deuxième étape, notée 21, un code à allouer. Si une telle allocation n'est pas possible, aucun code ne peut être alloué à l'instant considéré; la demande d'allocation peut éventuellement être renouvelée ultérieurement (ce qui a été illustré en pointillés sur la figure). Si une telle allocation est possible et si un code est trouvé à l'issue de ladite recherche, ce code constitue le code alloué. Si une telle allocation est possible et si aucun code à allouer n'est trouvé à l'issue de ladite recherche, un ré-arrangement de codes alloués est opéré au sein dudit arbre, selon une étape notée 22, avant de procéder à une nouvelle recherche de code à allouer, selon l'étape 21. Avantageusement, I'étape 20 correspond à la comparaison de la somme Cu + Cr, notée S, à un seuil noté T, correspondant à une capacité maximale susceptible d'être allouée. Avantageusement la valeur S s'exprime sous la forme S= (QN± o Nq désigne le nombre de codes déjà alloués de longueur q comprise entre 1 et QMox ( Q., étant la longueur maximale de code permise), et Q désigne la longueur de code dont l'allocation est demandée. Par exemple, si un seul code est déjà alloué, de longueur 4, et si l'allocation d'un code de longueur 8 est demandée, on obtient: S= -± 4 8 soit: S= -. Si la valeur seuil T a été choisie égale à 1 par exemple, alors, la valeur S étant inférieure à la valeur seuil T, cela signifie qu'un code de longueur Q égale à 8 peut être alloué. Par exemple encore, si deux codes de longueur 4 sont déjà alloués, et si l'allocation d'un code de longueur 8 est demandée, on obtient S 1+ 1! 4 4 8 soit $ S= -. De même, si la valeur seuil est égale à l, un code de longueur 8 peut alors être alloué. Par exemple encore, si trois codes de longueur 4 sont déjà alloués, et si l'allocation d'un code de longueur 8 est demandée, on obtient S =l+ 1+ 1 + 1 S =-±- 4 4 4 8 soit: = 7 De même, si la valeur seuil est égale à 1, un code de longueur 8 peut alors être alloué. Par contre, si par exemple un code de longueur 2 et deux codes de longueur 4 sont déjà alloués, et si l'allocation d'un code de longueur 8 est demandée, on obtient: 1 1 1 1 S = 1-+1+1+ 2 4 4 8 soit: S 9 La valeur S étant dans ce cas supérieure à la valeur seuil T, la demande d'allocation ne peut être satisfaite. Comme indiqué précédemment, la valeur seuil T pourrait aussi être 0 choisie inférieure à 1, notamment pour tenir compte des spécificités propres aux systèmes cellulaires de type CDMA. Egalement comme indiqué précédemment, la valeur seuil T pourrait aussi être choisie adaptative en fonction de divers paramètres caractéristiques du système considéré. La figure 5 illustre un exemple de codes déjà alloués, avant mise en oeuvre de ladite étape de ré-arrangement de codes alloués au sein dudit arbre. A titre d'exemple, les codes c4 et cQ=24sont déjà alloués, ces codes étant pour cela barrés sur cette figure. Dans ce cas, bien qu'en réponse à une demande d'allocation d'un code de longueur 2, ladite première étape indique qu'une telle allocation est possible, aucun code ne peut être trouvé à l'issue de ladite deuxième étape de recherche de code à allouer. La figure 6 illustre un exemple de codes déjà alloués, après mise en ceuvre de ladite étape de ré-arrangement de codes alloués au sein dudit arbre. A titre d'exemple, les codes déjà alloués sont maintenant constitués par les codes ch==4 et CQ=4, ces codes étant pour cela barrés sur cette figure. Dans ce cas, en réponse à une demande d'allocation d'un code de longueur 2, ladite première étape indique qu'une telle allocation est possible, et un code peut être trouvé à l'issue de ladite deuxième étape de recherche de code à allouer. On décrit maintenant, en relation avec la figure 7, une méthode avantageuse de recherche de code à allouer de longueur donnée. Suivant cette méthode, ladite recherche comporte les étapes suivantes: une étape, dite première sous- étape, de recherche de trajet libre à l'intérieur dudit arbre, de la racine de l'arbre jusqu'à un code ayant ladite longueur donnée, ce trajet libre ne devant comporter aucun autre code déjà alloué, - une étape, dite deuxième sous-étape, permettant de vérifier si aucun autre code n'est déjà alloué dans le sous-arbre ayant pour racine le code trouvé à l'issue de ladite première sous-étape. Un code ch peut être repéré à l'intérieur dudit arbre par sa longueur q et par son rang h parmi l'ensemble des codes possibles de longueur q. Dans ce qui suit, on utilise une représentation binaire pour la variable h, soit: h = (b, b2..be.) avec q=22, q Soit par ailleurs Q (avec Q=2E) la longueur de code à allouer. Une telle recherche comporte avantageusement, comme illustré sur la figure 7, les étapes suivantes: - Etape 1 d'initialisation des variables e (ou q) et b,: e= 1 ( c'est-à-dire q=2), et b1=0. - Etape 2 au cours de laquelle on détermine si le code c(bb2-b,)est utilisé. - Si le code c(bIb2-te)est déterminé non utilisé à l'issue de l'étape 2: q Etape 3 au cours de laquelle on détermine si e est inférieur à E. - Si e est déterminé inférieur à E à l'issue de l'étape 3: -- Etape 4 au cours de laquelle on incrémente e de 1 et on met la valeur beà 0. -- Retour à l'étape 2. - Si e n'est pas déterminé inférieur à E à l'issue de l'étape 3 (c'est-à- dire si e=E): -- Etape 8 d'initialisation e=E+1 et [bE+,bE+2...be]=0 -- Etape 9 au cours de laquelle on détermine si c(,bb2 -b)est utilisé. q - Si c(b'b2-b) est déterminé non utilisé à l'issue de l'étape 9 qEtape 10 au cours de laquelle on détermine si e réinitialise [bE+, bE+2...be] à 0. -- Retour à l'étape 9 - Si e n'est pas déterminé inférieur à Emax (c'està-dire si e= Emox ), à l'issue de l'étape 10: -- un code disponible est trouvé (étape notée 12) - Si le code c(bb2"b)est déterminé utilisé à l'issue de l'étape 9: --étape 13 consistant à déterminer si b, = 1 Vi = 1,..., E. - Si 3 i e t 1,..., Et tel que bi É1 à l'issue de l'étape 13: -Etape 1 4 consistant à effectuer (blb2...bE) = (bb2...bE) + (0...0]) puis à mettre e à la valeur maximale de i pour laquelle bi:0 (avec i compris entre 1 et E). -- Retour à l'étape 9. - Si b = l V i = 1,..., E à l'issue de l'étape 13: Un réarrangement de codes est nécessaire à l'intérieur de 3 o l'arbre (étape 15). - Si le code c(bb2-b) est déterminé utilisé à l'issue de l'étape 2 q --étape 5 au cours de laquelle on détermine si b, =1 V i = 1,..., e. - Si bi 1 Vi = 1,..., e à l'issue de l'étape 5: -- étape 6 au cours de laquelle on effectue: (b, b2...b0) (bb2...b) + (O...01) puis on met e à la valeur maximale de i pour laquelle bi 0 (avec i compris entre 1 et e) --retour à l'étape 2. -Si 3 i e 1,..., ES tel que bi É1 à l'issue de l'étape 5 -- un réarrangement de codes à l'intérieur dudit arbre est nécessaire (étape notée 7). Ainsi les étapes 1 à 6 constituent ladite première sous-étape de recherche de trajet libre à l'intérieur dudit arbre, de la racine de l'arbre jusqu'à un code ayant ladite longueur donnée. Les étapes 8 à 14 constituent ladite deuxième sous-étape permettant de vérifier si aucun autre code n'est déjà alloué dans le sous-arbre ayant pour racine le code trouvé à l'issue de ladite première sous-étape. Un premier exemple de mise en oeuvre d'une telle méthode de recherche 0 de code à allouer est illustré sur la figure 8. Cet exemple correspond au cas o un code de longueur 4 est déjà alloué, par exemple le code c,==: (ce code étant pour cela barré sur cette figure), et o un code de longueur Q égale à 8 est à allouer. Dans ce cas les codes qui sont envisagés successivement au cours de ladite recherche de trajet libre sont les suivants: c=,: (non utilisé), ch" (utilisé), cQ'4 (non utilisé), cQ=2 (non utilisé). c o2 c Q=4 Q: Q: Sur la figure 8 est illustré en traits renforcés le trajet libre trouvé à l'intérieur _ h=0 dudit arbre, à partir de la racine c:, et en l'occurrence jusqu'au code c ==ce Q=l = trajet libre passant en l'occurrence par les codes có- 2 et c=4 Sur la figure 8 est également illustré en traits renforcés le sous-arbre ayant pour racine le code c et formé des codes ch=46 et ch=56.En l'occurrence, aucun Q=8 Q:16 etcQ=1 code n'étant déjà alloué dans ce sous-arbre, le code c=-:8 peut bien être alloué. Un deuxième exemple est illustré sur la figure 9. Suivant ce deuxième exemple, les codes chQ4 et CQ='4 sont déjà alloués (ces codes étant pour cela barrés sur cette figure) et l'allocation d'un code de longueur égale à 8 est recherchée. Dans ce cas les différents codes qui sont successivement considérés au cours de ladite recherche de trajet libre sont les suivants: c'=2 (non utilisé), C24 (utilisé), ch=4 (utilisé), ch='2 (non utilisé), c:24 (non Q=2 co: o4 utilisé), c=48 (non utilisé). Sur la figure 9 est également illustré en traits renforcés le trajet libre trouvé à l'intérieur dudit arbre, à partir de la racine c=, et en l'occurrence jusqu'au code c:ce trajet libre passant en l'occurrence par les codes cQ2' et cQ=4. Sur la figure 9 est également illustré en traits renforcés le sous-arbre ayant pour racine le code cQ=4 et formé des codes chs6 et c,.En l'occurrence, aucun code n'étant déjà alloué dans ce sous-arbre, le code Ch=4 peut bien être alloué. Un troisième exemple est illustré sur la figure 10. Suivant ce troisième exemple, les codes cQ:4, chQ'l4, et ch='2 sont déjà alloués (ces codes étant pour cela barrés sur cette figure) et l'allocation d'un code de longueur égale à 8 est recherchée. Dans ce cas les différents codes qui sont successivement considérés au cours de ladite recherche de trajet libre sont les suivants: c2 ui (non utilisé), CQ4 (utlsé) CQ'4 h2(utilisé), C(non é Sur la figure 10 est également illustré en traits renforcés le trajet libre trouvé à l'intérieur dudit arbre, à partir de la racine c , et en l'occurrence jusqu'au code C(=ts, ce trajet libre passant en l'occurrence par les codes c:2het h=3 Q=4 Sur la figure 10 est également illustré en traits renforcés le sous-arbre ayant pour racine le code cu6 et formé des codes CQ=I2, et ch!3.En l'occurrence, aucun code n'étant déjà alloué dans ce sous-arbre, le code cs peut bien être alloué. On note ainsi que la numérotation binaire utilisée pour repérer les codes à l'intérieur de l'arbre par leur rang h permet, lors de ladite recherche de trajet libre, de parcourir l'arbre de façon méthodique, suivant une combinaison de longueurs de codes croissantes et de rangs croissants (bien que lesdits rangs pourraient aussi être considérés suivant une autre loi que croissante, par exemple décroissante). Outre le fait que cet algorithme peut ainsi être implémenté de façon relativement simple, ceci permet également d'allouer les codes de façon méthodique, ce qui évite des problèmes de saturation trop rapide de capacité, qui pourraient résulter d'une allocation effectuée de façon plus aléatoire. Un autre avantage est que l'utilisation du critère S (c'est-à-dire de la première étape) permet de déterminer a priori s'il est possible de trouverun code de longueur souhaitée. Si la réponse au test est négative, il est possible de rejeter la requête sans avoir à effectuer un re procédure de parcours de l'arbre. Sinon le parcours de l'arbre permet de trouver un code disponible, si besoin après réarrangement en cas d'un premier parcours infructueux. L'approche dans le document précédemment mentionné (brevet US ,751,761) ne permettait pas de répondre à ce besoin: en l'absence de critère de disponibilité, la recherche des codes non disponibles indiquait une impossibilité, mais il était impossible de savoir si un réarrangement permettait de libérer un tel code, d'o une procédure plus longue, avec un risque d'échec au bout. Il est par ailleurs possible d'interdire l'allocation de certains codes et de leurs sous-arbres, par exemple la moitié des codes pour lesquels b = 1i avec la notation utilisée ci-dessus. Dans ce cas le seuil T utilisé doit être adapté en conséquence: sa valeur est au plus celle de la capacité maximale susceptible d'être allouée, avec la nouvelle containte Tmax = 1- nombre de codes interdits de longueur Qmax T peut tre plus petit que max. 1- Qa; T peut être plus petit que Imax. Qmax Revendications 1 Procédé d'allocation de codes orthogonaux dans un système de radiocommunications mobiles du type à accès multiple par répartition de codes utilisant des codes de longueur variable dont le mode de génération est tel qu'ils peuvent être représentés sous forme d'arbre, ce procédé étant caractérisé en ce qu'il comporte, en réponse à une demande (A) d'allocation de code, une étape (20), dite première étape, destinée à déterminer,en fonction de la capacité d'arbre utilisée (Cu), correspondant aux codes déjà alloués, et de la capacité d'arbre requise (Cr), correspondant à l'allocation de code demandée, si une telle allocation est possible. 2 Procédé selon la revendication 1, caractérisé en ce que dans le cas o une telle allocation est déterminée possible à l'issue de ladite première étape, il comporte une étape (21), dite deuxième étape, de recherche de code à allouer. 3 Procédé selon la revendication 2, caractérisé en ce que dans le cas o une telle allocation est déterminée possible à l'issue de ladite première étape, et dans le cas o aucun code à allouer n'est trouvé à l'issue de ladite deuxième étape, il comporte une étape (22), dite troisième étape, de ré-arrangement de codes alloués au sein dudit arbre. 4 Procédé selon l'une des revendications 1 à 3, caractérisé en ce que la capacité d'arbre, utilisée ou requise, correspondant à un code de longueur Q est déterminée comme correspondant à (1/Q) ième de la capacité d'arbre totale. Procédé selon l'une des revendications 1 à 4, caractérisé en ce que ladite première étape (20) comporte une comparaison de la somme S de la capacité d'arbre utilisée Cu et de la capacité d'arbre requise Cr, à un seuil de capacité T, correspondant à une capacité maximale susceptible d'être allouée. 6 Procédé selon les revendications 4 et 5, caractérisé en ce que ladite somme S s'exprime sous la forme ( QM- Nq =l q) Q o Nq désigne le nombre de codes déjà alloués de longueur q comprise entre 1 et Q Mox ( Q M,, étant la longueur maximale de code permise), et Q désigne la longueur de code dont l'allocation est demandée. 7 Procédé selon l'une des revendications 4 à 6, caractérisé en ce que ledit seuil (T) est choisi adaptatif en fonction de divers paramètres caractéristiques dudit système. 8 Procédé selon l'une des revendications 4 à 7, caractérisé en ce que ledit seuil (T) est choisi de manière à ne jamais aboutir à la capacité maximale dudit arbre. 9 Procédé selon l'une des revendications 4 à 7, caractérisé en ce que l'allocation de certains codes et de leurs sous-arbres est interdite et en ce que ledit seuil (T) s'exprime alors sous la forme T Avec: T MAX =1- QMax O Q MX désigne la longueur maximale de code permise. Procédé selon l'une des revendications 2 à 9, caractérisé en ce que ladite deuxième étape de recherche d'un code à allouer de longueur donnée comporte elle-même: - une première sous- étape (1 à 6) de recherche de trajet libre à l'intérieur dudit arbre, de la racine de l'arbre jusqu'à un code ayant ladite longueur donnée, ce trajet libre ne devant comporter aucun autre code déjà alloué, - une deuxième sous-étape (8 à 14) permettant de vérifier si aucun code n'est déjà alloué dans le sous-arbre ayant pour racine le code trouvé à l'issue de ladite première sous-étape. h 11 Procédé selon la revendication 10, caractérisé en ce que, un code CQ étant repéré à l'intérieur dudit arbre par sa longueur de code Q et par le rang h de ce code dans l'ensemble des différents codes ayant cette longueur de code, lesdites première et deuxième sous-étapes comportent un parcours de tout ou partie dudit arbre suivant une combinaison de longueurs de codes Q croissantes et de rangs h variant suivant une loi prédétermineé, notamment croissante. 1 2 Procédé selon l'une des revendications 1 O et 1 1, caractérisé en ce que lesdites première et deuxième sous-étapes utilisent une numérotation binaire desdits rangs h.