Method of allocating orthogonal codes in a code division multiple access mobile radio system using codes of variable length

[0002] The present invention is generally concerned with spread spectrum communication systems, i.e. systems in which spectrum spreading is applied to a sequence of data to be transmitted, on transmission, using a spreading code, and, conversely, despreading is effected on reception, in order to find the original sequence.

[0003] Spreading an incident data sequence of N symbols, denoted (d1, d2, . . . , dN), using a code of length (or spreading factor) Q, denoted c_Q=(c1, c2, . . , cQ), produces a sequence of length Q.N, which can be represented as follows:

[0004] (d1.c1, d1.c2, . . . , d1.cQ, d2.c1, d2.c2, . . . , dN.cQ)

[0005] where d1.c1 represents the multiplication of d1 by c1.

[0006] An alternative representation of the spread sequence of length Q.N is (d1.cQ, d2.c_Q, . . . cN.c_Q) where d1.c_Qrepresents the product of the symbol d1 by the spreading code c_Q.

[0007] A more general approach to spreading consists in having a different spreading code for each symbol of the input sequence, in which case the resulting spread sequence can be expressed in the form: (d1.c_Q⁽¹⁾,d2.c_Q⁽²⁾, . . . ,dN.c_Q^(N)), c_Q⁽¹⁾being the spreading code associated with the symbol d1. All the spreading codes preferably have the same length Q so that the resulting spread sequence has the length Q.N.

[0008] FIG. 1 outlines the principle of spreading, Ts designating the basic period (or symbol period) of a non-spread sequence and Tc designating the basic period (or chip, period) of a spread sequence, Ts and Tc being related by the equation Ts=Q.Tc. In the figure dn and dn+1 correspond to two successive symbols of a non-spread incoming sequence and d′l and d′l+1 correspond to two successive basic symbols (or “chips”) of the same spread symbol of the incoming sequence.

[0009] One benefit of the above systems is enabling a plurality of users to share the same frequency band by allocating different users different codes.

[0010] One important application is Code Division Multiple Access (CDMA) cellular mobile radio systems.

[0011] In the above systems, the codes are advantageously orthogonal two by two within a cell to reduce interference between users in that cell (interference between cells can also be reduced by other techniques known per se).

[0012] Mathematical tools have been developed for generating orthogonal codes. Walsh functions, which are known per se, generate orthogonal codes of length Q recursively from orthogonal codes of length Q/2, Q/4, etc. To be more precise, two orthogonal codes of length q are obtained from a code of length q/2 by juxtaposing with that code of length q/2, respectively that code, and the complementary code.

[0013] In systems using orthogonal codes of fixed length Q, the allocation of orthogonal codes can then be a relatively simple operation, consisting in selecting a code that is not being used at the time in question from Q possible orthogonal codes of length Q.

[0014] There is a need in these cellular mobile radio systems to be able to transmit data at a varying bit rate, in particular when the bit rate of the user itself varies (for example in the case of transmitting multimedia type data), or because, depending on the conditions for propagation of radio signals, a higher or lower degree of redundancy has to be introduced into the data to be transmitted in order to obtain a higher or lower degree of protection against transmission errors.

[0015] Increasing the bit rate of data to be transmitted by a user, for the same allocated frequency band (i.e. for the same duration Tc) by reducing the length of the code allocated to that user so that they continue to send on only one code is known per se. FIG. 2 shows the principle of a technique of this kind, and uses the same type of representation as FIG. 1, but for two different bit rates of the incoming sequence, respectively identified by the suffices 1 and 2, in this instance for three successive symbols dn, dn+1 and dn+2 of the incoming sequence, the symbol period corresponding to Ts1 for symbol dn and Ts2 for symbols dn+1 and dn+2 and the code length corresponding to Q1 for symbol dn and Q2 for symbols dn+1 and dn+2.

[0016] Mobile radio systems using codes of variable length, typically Walsh codes, of length Q, Q/2, Q/4, etc. are therefore known per se.

[0017] These codes can be represented in the form of a tree, each code giving rise within the tree to two codes of double the length, in the manner outlined above.

[0018] FIG. 3 shows a tree of the above kind in which the codes are denoted c_Q^h, where Q represents the length of the code and h represents the order of that code in the set of possible codes of length Q.

[0019] Accordingly, in FIG. 3, the various codes can be denoted as follows:

[0020] c_Q−1^h−0=(1)

[0021] c_Q=2^h=0(1,1)

[0022] c_Q=2^h=1(1,−1)

[0023] c_Q=4^h=0(1,1,1,1)

[0024] c_Q=4^h=1(1,1−1,−1)

[0025] c_Q=4^h=2(1,−1,1,−1)

[0026] c_Q=4^h=3(1,−1,−1,1)

[0027] c_Q=8^h=0(1,1,1,1,1,1,1,1)

[0028] c_Q=8^h=1(1,1,1,1,−1,−1−1,−1)

[0029] c_Q=8^h=2(1,1,−1,−1,1,1,−1−1)

[0030] c_Q=8^h=3(1,1,−1,−1,−1,−1,1,1)

[0031] c_Q=8^h=4(1,−1,1,−1,1,−1,1,−1)

[0032] c_Q=8^h=5(1,−1,1,−1,1,−1,1,−1)

[0033] c_Q=8^h=6(1,−1,−1,1,1,−1,−1,1)

[0034] c_Q=8^h=7(1,−1,−1,1,−1,1,1,−1)

[0035] In a tree of the above kind the orthogonal relationship between codes of different length is preserved only on condition that certain allocation rules are complied with. Accordingly, a given code cannot be allocated at a given time if it is recursively tied to a code that has already been allocated.

[0036] Allocating orthogonal codes therefore constitutes a relatively more complex operation in systems using codes of variable length than in systems using codes of fixed length.

[0037] Thus document U.S. Pat. No. 5,751,761 teaches, on each new request for allocation of a code of given length, drawing up a list including codes already allocated at that time and codes tied to them in a recursive manner, the code to be allocated then being a chosen one of the codes not appearing in the list.

[0038] A solution of the above kind has the particular drawback that establishing a list of the above kind is a lengthy operation and entails multiple write operations, the number of which increases with the depth of the tree, i.e. with the maximum permitted code length.

[0039] A particular aim of the present invention is to avoid this drawback.

[0040] Thus in one aspect the present invention consists in a method of allocating orthogonal codes in a code division multiple access mobile radio system using codes of variable length which are generated in such a way that they can be represented in the form of a tree, said method essentially including, in response to a code allocation request, a first step of determining, in accordance with the tree capacity used, corresponding to codes already allocated, and the tree capacity required, corresponding to the code allocation requested, if such allocation is possible.

[0041] In accordance with another feature, if such allocation is found to be possible at the end of said first step said allocation method includes a second step of searching for a code to allocate.

[0042] In accordance with another feature, if such allocation is found to be possible at the end of said first step and if no code to be allocated has been found at the end of said second step said allocation method includes a third step of rearranging allocated codes within said tree.

[0043] Accordingly, in contrast to the document cited previously, it is not necessary, on each new allocation request, to draw up a complete list of all the codes that are not available, and in particular to look for all the codes tied in a recursive manner to codes already allocated. All that is required is to see if a code having the required length is available or can be made available by rearranging the codes allocated within the tree; if a code of this kind is available or can be rendered available by rearrangement in this way, the search for the code to be allocated is effected by searching for a code that is not already allocated and is not tied in a recursive manner to a code already allocated.

[0044] The allocation operation is therefore made less complex and speeded up, which leads to a simplification and an improvement in quality of service.

[0045] In contrast to systems using fixed length codes, here the concept of capacity takes account of the fact that allocating a given code when it is not only that code that is unavailable thereafter, but also all codes that are tied to it in a recursive manner within said tree; this is what is meant in the present context by the expression “tree capacity”.

[0046] In another aspect the invention therefore consists in a particularly simple and fast method of determining a used or required tree capacity.

[0047] In accordance with another feature, the tree capacity used or required corresponding to a code of length Q is determined as corresponding to (1/Q)th of the total tree capacity.

[0048] In accordance with another feature, said first step advantageously includes comparing the sum S of the tree capacity used and of the tree capacity required to a capacity threshold T corresponding to a maximum capacity that can be allocated.

[0049] In accordance with another feature, said sum S is expressed in the form: $S=\left(\sum _{q=1}^{Q_{\mathrm{Max}}}\frac{N_q}{q}\right)+\frac{1}{Q}$

[0050] where N_qis the number of codes already allocated of length q between 1 and Q_Max(Q_Maxbeing maximum code length permitted) and Q is the length of the code whose allocation is requested (this sum can be limited to a subset of the integers q between 1 and Q_Max, for example the integers of the set that are a power of 2).

[0051] Accordingly, said first step of determining if a requested allocation is possible can be effected in a particularly simple and fast manner.

[0052] Said threshold can advantageously be determined in an adaptive manner in accordance with various parameters characteristic of the system concerned.

[0053] Such parameters can include in particular the measured or estimated level of interference in a cell, the type of call (circuit-switched or packet-switched) in that cell, the required quality of service, etc.

[0054] It may be possible to choose said threshold in such a manner that the maximum capacity of said tree is never reached, in particular in accordance with features specific to CDMA type cellular systems, in terms of limiting the acceptable number of users (in particular according to the maximum interference level between cells and of power control stability).

[0055] In accordance with another feature, allocation of certain codes and their sub-trees is prohibited and said threshold is then expressed in the form:

[0056] T≦T_Max

[0057] with: $T_{\mathrm{Max}}=1-\frac{\mathrm{number}\mathrm{of}\mathrm{prohibited}\mathrm{codes}\mathrm{of}\mathrm{length}{Q}_{\mathrm{Max}}}{Q_{\mathrm{Max}}}$

[0058] where Q_Maxis the maximum code length permitted.

[0059] In accordance with another feature, said second step of searching for a code to allocate of given length includes:

[0060] a first sub-step of searching for a free path within said tree, from the root of the tree as far as a code having said given length; this free path must not include any other code already allocated, and

[0061] a second sub-step for verifying if no code has already been allocated in the sub-tree whose root is the code found at the end of said first sub-step.

[0062] A code being identified within said tree by its code length and by the order of that code in the set of different codes having that code length, said first and second sub-steps advantageously include scanning all or part of said tree in accordance with a combination of increasing code lengths and orders varying in accordance with a predetermined law, in particular an increasing law.

[0063] Said first and second sub-steps advantageously use binary numbering of said orders.

[0064] The present invention also has for its object an entity for a mobile radiocommunication system, comprising means for performing a method of the above kind.

[0065] Other aims and features of the present invention will become apparent on reading the following description of one embodiment given with reference to the accompanying drawings, in which:

[0066] FIG. 1 outlines the principle of spectrum spreading, in the case of fixed length spreading codes,

[0067] FIG. 2 outlines the principle of spectrum spreading, in the case of variable length spreading codes,

[0068] FIG. 3 shows how variable length codes are represented in the form of a tree,

[0069] FIG. 4 shows a code allocation method in accordance with the invention,

[0070] FIG. 5 shows an example of codes allocated, before said step of rearranging allocated codes within said tree,

[0071] FIG. 6 shows an example of codes allocated, after said step of rearranging allocated codes within said tree,

[0072] FIG. 7 shows one embodiment of said step of searching for a code to allocate,

[0073] FIG. 8 shows a first example of the code searching step from FIG. 7,

[0074] FIG. 9 shows a second example of the code searching step from FIG. 7,

[0075] FIG. 10 shows a third example of the code searching step from FIG. 7.

[0076] In accordance with the invention, as shown in FIG. 4, in response to a request to allocate a code of given length, denoted A, in a first step 20, whether such allocation is possible or not is determined in accordance with the tree capacity used, denoted Cu, corresponding to codes already allocated, and the tree capacity required, denoted Cr, corresponding to the requested code allocation.

[0077] If such allocation is possible, a code to be allocated is searched for in a second step 21.

[0078] If such allocation is not possible, no code can be allocated at the time in question; the allocation request can possibly be repeated later (which is shown in dashed line in the figure).

[0079] If such allocation is possible and a code is found at the end of said search, then that code constitutes the allocated code.

[0080] If such allocation is possible and no code to allocate is found at the end of said search, the allocated codes are rearranged within said tree in step 22 before proceeding to a new search for a code to allocate in step 21.

[0081] Step 20 advantageously corresponds to comparing the sum S of Cu+Cr to a threshold T corresponding to a maximum capacity that can be allocated.

[0082] The value S is advantageously expressed in the form: $S=\left(\sum _{q=1}^{Q_{\mathrm{Max}}}\frac{N_q}{q}\right)+\frac{1}{Q}$

[0083] where N_qis the number of codes already allocated of length 8 between 1 and Q_Max(Q_Maxbeing the maximum code length permitted) and Q is the code length in respect of which allocation is requested.

[0084] For example, if only one code has already been allocated, of length 4, and if allocation of a code of length 8 is requested, we get:

[0085] S=¼+⅛

[0086] or:

[0087] S=⅜.

[0088] If the threshold value T is chosen as 1, for example, then because the value S is lower than the threshold value T a code of length Q equal to a can be allocated.

[0089] For example, if two codes of length 4 have already been allocated, and if allocation of a code of length 8 is requested, we get:

[0090] S=¼+¼+⅛

[0091] or

[0092] S=⅝.

[0093] Similarly, if the threshold value is equal to 1, a code of length 8 can be allocated.

[0094] For example, if three codes of length 4 have already been allocated, and if allocation of a code of length 8 is requested, we get:

[0095] S=¼+¼+¼+⅛

[0096] or:

[0097] S=⅞.

[0098] Similarly, if the threshold value is equal to 1, a code of length 8 can be allocated.

[0099] In contrast, if a code of length 2 and two codes of length 4 have already been allocated, for example, and if allocation of a code of length 8 is requested, we get:

[0100] S=½+¼+¼+⅛

[0101] or:

[0102] S={fraction (9/8)}.

[0103] Because the value S is greater than the threshold value T in this case, the allocation request cannot be satisfied.

[0104] As previously indicated, the threshold value T could also be chosen less than 1, in particular to allow for features specific to CDMA type cellular systems.

[0105] Also as previously indicated, the threshold value T could also be adaptive in accordance with various parameters characteristic of the system concerned.

[0106] FIG. 5 shows an example of codes already allocated, before said step of rearranging the allocated codes within said tree is executed. For example, the codes c_Q=4^h=0and c_Q=8^h=2have already been allocated, for which reason they are struck through in the figure.

[0107] In this case, although in response to a request for allocation of a code of length 2 said first step indicates that such allocation is possible, no code can be found at the end of said second step of searching for a code to be allocated.

[0108] FIG. 6 shows an example of codes already allocated after said step of rearranging the allocated codes within said tree has been executed. For example, the codes already allocated are now the codes c_Q=4^h=0and c_Q=4⁼¹, for which reason these codes are struck through in the figure.

[0109] In this case, in response to a request to allocate a code of length 2, said first step indicates that such allocation is possible and a code can be found at the end of said second step of searching for a code to allocate.

[0110] An advantageous method of searching for a code of given length to be allocated will now be described with reference to FIG. 7.

[0111] In this method, said search includes the following steps:

[0112] a first sub-step of searching for a free path within said tree, from the root of the tree to a code having said given length; this free path must not include any other code already allocated, and

[0113] a second sub-step for verifying if no other code has already been allocated in the sub-tree whose root is the code found at the end of said first sub-step.

[0114] A code c_q^hcan be identified within said tree by its length q and its order h among all possible codes of length q.

[0115] In the following description a binary representation is used for the variable h, thus:

[0116] h=(b₁b₂. . . b_e)

[0117] where q=2^e, q≦Q_Maxand ≦E_Maxis such that Q_Max=2^Emax.

[0118] Q (with Q=2^E) is the code length to be allocated.

[0119] As shown in FIG. 7, a search of the above kind advantageously includes the following steps:

[0120] Step 1 of initializing variables e (or q) and b₁:

[0121] e=1 (i.e. q=2), and b₁=0.

[0122] Step 2 during which it is determined if the code c_q^{(bb. . . b)}is used.

[0123] If the code c_q^(bbb)is found not to have been used at the end of step 2:

[0124] Step 3 during which it is determined if e is less than E.

[0125] If e is found to be less than E at the end of step 3:

[0126] Step 4 during which e is incremented by 1 and the value be is set to 0.

[0127] Return to step 2.

[0128] If is not less than E at the end of step 3 (i.e. if e=E):

[0129] Initialization step 8:

[0130] e=E+1 and [b_E+1b_E+2. . . b_e]=0

[0131] Step 9 during which it is determined if c_q^{(bb. . . b)}has been used.

[0132] If c_q^{(bb. . . b)}is found not to have been used at the end of step 9:

[0133] Step 10 during which it is determined if e<E_Max

[0134] If e is less than E_Max, at the end of step 10:

[0135] Step 11 during which it is determined if [b_E+1b_E+2. . . b_e] is less than 2^e−E−1

[0136] If [(b_E+1b_E+2. . . b_E] is less than 2^e−E−1,

[0137] step 11b during which:

[0138] If [(b_E+1b_E+2. . . b_e]=[b_E+1b_E+2. . . b_e]=1

[0139] If [b_E+1b_E+2. . . b_e] is found to be equal to 2^e−E−1, step 11a during which e is incremented by 1 and [b_E+1b_E+2. . . b_e] is reset to 0.

[0140] Return to step 9.

[0141] if e is not less than E_Max, (i.e. if e=E_Max), at the end of step 10:

[0142] an available code has been found (step 12).

[0143] If code c_q^bbb)is found to have been used at the end of step 9:

[0144] Step 13 consisting in determining if b_i=1∀=1, . . . , E.

[0145] If ∃iε{1, . . . E} such that b₁≠1 at the end of step 13:

[0146] Step 14 consisting in

[0147] (b₁b₂. . . b_E)=(b₁b₂. . . b_E)+(0 . . . 01)

[0148] then setting e to the maximum value of i for which b_i≠0 (with i between 1 and E).

[0149] Return to step 9.

[0150] If b₁=1∀=1, . . . , E at the end of step 13:

[0151] Rearrangement of codes is necessary within the tree (step 15).

[0152] If code c_q^(bbb)is found to have been used at the end of step 2:

[0153] Step 5 during which it is determined if b_i=1∀=1, . . , e.

[0154] If b_i≠1∀i=1, . . . , e at the end of step 5:

[0155] step 6 during which:

[0156] (b₁b₂. . . b_e)=(b₁b₂. . . b_e)+(0 . . . 01)

[0157] then e is set to the maximum value of i for which b_i≠0 (with i between 1 and e).

[0158] Return to step 2.

[0159] If ∃iε{1, . . . , E} such that b_i≠1 at the end of step 5:

[0160] Rearrangement of codes within said tree is necessary (step 7).

[0161] Thus steps 1 to 6 constitute a first sub-step of searching for a free path within said tree, from the root of the tree to a code having said given length. Steps 8 to 14 constitute said second sub-step for verifying if no other code has already been allocated in the sub-tree whose root is the code found at the end of said first sub-step.

[0162] FIG. 8 shows a first embodiment of a method of search for a code to allocate of the above kind.

[0163] This example corresponds to the situation in which a code of length 4 has already been allocated, for example the code c_Q=4^h=0(for which reason this code is struck through in the figure) and a code of length Q equal to 8 is to be allocated.

[0164] In this case the codes envisaged successively during said free path search are as follows:

[0165] c_Q=2^h=0(not used), c_Q=4^h=0(used), c_Q=4^h=1(not used), c_Q=8^h=2(not used).

[0166] In FIG. 8 thicker lines are used to show the free path found within said tree, from the root c_Q=1^h=0and in this instance as far as the code c_Q=8^h=2, this free path here passing through the codes c_Q=2^h=0and c_Q=4^h=1.

[0167] FIG. 8 also shows in thicker line the sub-tree whose root is the code c_Q=8^h=2and formed of the codes c_Q=16^h=4and c_Q=16^h=5. In this instance, no code having already been allocated in this sub-tree, the code c_Q=8^h=2can be allocated.

[0168] FIG. 9 shows a second example. In this second example the codes c_Q=4^h=0and c_Q=4^h=1have already been allocated (for which reason these codes are struck through in the figure) and the allocation of a code of length 8 has been requested.

[0169] In this case the codes that are successively considered during said free path search are as follows:

[0170] c_Q=2^h=0(not used), c_Q=4^h=0(used), c_Q=4^h=1(used), c_Q=2^h=1(not used), c_Q=4^h=2(not used), c_Q=8^h=4(not used).

[0171] FIG. 9 also shows in thicker line the free path found within said tree, from the root c_Q=1^h=0and in this instance as far as the code c_Q=1^h=0this tree path here passing through the codes c_Q=2^h=1and c_Q=4^h=2.

[0172] FIG. 9 also shows in thicker line the sub-tree whose root is the code c_Q=8^h=4and formed of the codes c_Q=16^h=8and c_Q=16^h=9. In this instance, no code having been already allocated in this sub-tree, the code c_Q=8^h=4can be allocated.

[0173] FIG. 10 shows a third example. In this third example the codes c_Q=4^h=0, c_Q=4^h=1and c_Q=4^h=2have already been allocated (for which reason these codes are struck through in the figure) and the allocation of a code of length 8 has been requested.

[0174] In this case the various codes that are successively considered during said free path search are as follows:

[0175] c_Q=2^h=0(not used), c_Q=4^h=0(used), c_Q=4^h=1(used), c_Q=2^h=1(not used), c_Q=4^h=2(used), c_Q=4^h=3(not used), c_Q=8^h=6(not used).

[0176] FIG. 10 also shows in thicker line the free path found within said tree, from the root c_Q=1^h=0and in this instance as far as the code c_Q=8^h=6, this free path passing here through the codes c_Q=2^h=1and c_Q=4^h=3.

[0177] FIG. 10 also shows in thicker line the sub-tree whose root is the code c_Q=8^h=6and formed of the codes c_Q=16^h=12et c_Q=16^h=13. In this instance, no code having already been allocated in this sub-tree, the code c_Q=8^h=6can be allocated.

[0178] Note also that the binary numbering scheme used to identify the codes within the tree by their order h enables methodical scanning of the tree during said free path search, using a combination of increasing code lengths and increasing orders (although said orders could be considered in accordance with a law other than an increasing law, for example a decreasing law). Apart from the fact that this algorithm can therefore be implemented in a relatively simple manner, this also enables methodical allocation of the codes, which avoids problems of excessively fast saturation of capacity that could result from allocation effected in a more random manner.

[0179] Another advantage is that using the criterion S (i.e. the first step) enables a priori determination if it is possible to find a code of required length. If the response to the test is in the negative, it is possible to reject the request without having to scan the tree at all. Otherwise scanning the tree finds an available code, if necessary after rearrangement if the first pass is unsuccessful.

[0180] The approach adopted in the document previously mentioned (U.S. Pat. No. 5,751,761) did not satisfy this requirement: in the absence of any availability criterion, the search for non-available codes indicated an impossibility, but it was impossible to know if rearrangement would free up a code, whence a longer procedure, with the risk of ultimate failure.

[0181] It is also possible to prohibit the allocation of certain codes and their sub-trees, for example half of the codes for which b_i=1, using the above notation. In this case the threshold T used must be adapted accordingly: its value is at most that of the maximal capacity that can be allocated, with the new constraint $T_{\mathrm{Max}}=1-\frac{\mathrm{number}\mathrm{of}\mathrm{prohibited}\mathrm{codes}\mathrm{of}\mathrm{length}{Q}_{\mathrm{Max}}}{Q_{\mathrm{Max}}};$

[0182] and T can be smaller than T_max.