GB2350267A - Processing of codes in CDMA communication networks - Google Patents

Abstract

An orthogonal code tree has branches corresponding respectively to candidate "short" codes for use in spreading the spectra of respective data streams. A code-division multiple access communications method includes the steps of representing the positions in the tree of such branches by respective flag-words, manipulating the flag-words to systematically effect certain operations which result in an allocated code set, and using the codes in the resulting allocated code set to spread the spectra of the data streams to which those codes have been allocated respectively. The operations which may be effected by manipulation of the flag-words include initial allocation of a set of codes from amongst the candidate codes to respective data streams, addition to such a set of allocated codes of one or more further codes from amongst the candidate codes and removal from such a set of allocated codes of one or more of the allocated codes. The manipulation of the flag-words is always such that, in the resulting set of allocated codes, there is no code whose corresponding branch is a direct or indirect parent branch of the branch corresponding to any other code in that set. Such a code-division multiple access method can effect efficiently and systematically the allocation and amendment of a set of codes without requiring a large storage capacity.

Description

1% 2350267 -1 PROCESSING OF CODES IN CDMA COMMUNICATION NETWORKS The

present invention relates to processing of codes in CDMA communication networks. In particular, but not exclusively, the present invention relates to methods and apparatus for selecting and deselecting short codes for use in a mobile station or a base station of a cellular mobile communications system to spread the spectra of data streams to he transmitted.

In a cellular mobile communications system, it is necessary for a transmitter (at least a base station transmitter and probably also a mobile station transmitter) to be able to transmit a plurality of data streams simultaneously. For example, in the systems contemplated by the present ETSI (European Telecommunications Standards Institute) and ARIB (Association of Radio Industries and Business) Wideband CDMA (Code Division Multiple Access) proposals, a transmitter (i.e. a mobile station or a base station) combines a number of data streams and broadcasts a transmission signal embodying the combined data streams.

Incidentally, it should be noted that data streams are sometimes also referred to as "channels". However, the use of this term in this context should not be confused with the medium between the transmitter and the receiver which is also referred to as the "channel".

The data streams to be transmitted may carry user data and/or control information. In order for the receiver to be able to separate the data streams, each data stream is assigned a unique periodic signature or code sequence from a set of orthogonal code sequences before the data streams are combined in the transmission signal. For a set of codes to be orthogonal there must be no correlation between the codes, i.e. they are independent of each other.

Each data stream is multiplied by its assigned code sequence. This process is known as spreading. In a wideband CDMA mobile communications system, the code used in the spreading process is referred to as the llchannelisationll, "short" or "spreading" code.

Figure 1 of the accompanying drawings is a block diagram of parts of a transmitter for illustrating how data streams can be combined therein.

The Figure 1 apparatus comprises a set of n multipliers 21 to 2n, where n is the number of input data streams D, to Dn to be combined. Each multiplier 21 to 2n receives as inputs one of the data streams D, to Dn and a corresponding spreading code C.p, to Cspn assigned to that data stream.

is The Figure 1 apparatus further comprises an adder 4 and a further multiplier 6. Inputs of the adder 4 are coupled respectively to outputs of the multipliers 21 to 2n. An output of the adder 4 is coupled to a f irst input of the multiplier 6. A second input of the multiplier 6 receives another code sequence Csc known as the ',scrambling code". The output signal from the multiplier 6 is the combined data stream D. for transmission.

In operation of the Figure 1 apparatus the multipliers 21 to 2n multiply the data streams D, to Dn received at their respective f irst inputs by the assigned spreading codes Csc, to Cscn received respectively at their respective second inputs. The resulting spread data streams are then added (combined) together in the adder 4. Then, in the multiplier 6, the combined and spread data streams are multiplied by the scrambling code CSC1 The scrambling code is a unique code applied to each transmitter in order to separate it f rom other transmitters. Since there need to be enough scrambling codes to uniquely identify each transmitter, scrambling codes are usually very long codes. Scrambling codes can be selected from a set of orthogonal sequences known as "Gold Sequences".

Incidentally, it should be noted that the spreading codes, or short codes, separate the data streams of one particular transmitter while the scrambling codes, or long codes, separate different transmitters. In this way, an entire short-code set is available to each transmitter for spreading purposes.

The length of the spreading code assigned is equal to the required "spreading factor". The required spreading factor is defined as the ratio of the spreading code rate to that of the data stream. A higher-rate data stream is assigned a smaller spreading factor (shorter spreading code) than a lower-rate data stream, if the two spread data streams are to be combined together.

There are a variety of orthogonal code sets which exist and have been considered for the purpose of spreading. one example of such a code set is the one selected by both ETSI and ARIB which is known as the "orthogonal code tree". The codes in this code set are also sometimes referred to as Orthogonal Variable Spreading Factor (OVSF) codes. For example, ETSI document number UMTS (xx.05) VO.56.0 1999-1 provides some background information about OVSF codes.

Figure 2 of the accompanying drawings is a diagram illustrating the structure of the "orthogonal code tree". In this diagram, logic 0 and logic 1 are represented by 1 and -1 respectively.

The tree fans out from left to right starting with a main branch C, (1) at the first level of the tree, which branch has the code 1 of unit length. This main branch is the parent (either directly or indirectly) of all other branches. Each branch is the direct parent of a pair of branches (children) at the next level of the tree. For a given parent the two children will be referred to herein as first (upper in the Figure) and second (lower in the Figure) child branches of the parent branch. Each branch is an indirect parent of the children of its children, and their children and so on. For example, in Figure 2, the branch C2 (1) is an indirect parent of the branch C8 (2) whereas the branch C4 (1) is the direct parent Of C8 (2).

For a parent branch code Ck (n), the pair of children branch codes C2k (2n-1) and C2k (2n) are 1Ck (n) -Ck(n)] and [Ck(n),Ck(n)] respectively, where [x,yl represents concatenation of x and y and -x is the bitwise negation (inversion) of x. It should be noted that, in Ck (n), k is the length of the code (or spreading factor) and n is an index which distinguishes codes of the same length.

A careful consideration of the Figure 2 tree reveals that codes of length k, corresponding to a spreading factor of k, are members of the size-k Walsh set. A Walsh set of size k, where k is a positive integral power of 2, contains Ck (1), Ck (2), Ck (3),..., Ck(k). In Figure 2, the branches belonging to Walsh sets of size 2, 4 and 8 are distinguished by having different thicknesses.

Assuming code alignment, the elements of a size k Walsh set are orthogonal to each other and can be used to separate different services (data streams) of the same rate. It is also possible to maintain code orthogonality and support a multi-rate (using multi code and/or variable rate spreading) scenario where different rate services are transmitted together by selecting a code set from the Figure 1 tree such that no code is a direct or indirect parent of other codes in the set.

Even though the members of such an orthogonal code set have different lengths (the length of a code is always a power of two) the correlation between the members is zero. Accordingly, different-rate data streams may be transmitted simultaneously by the same transmitter without interference between the streams.

The elements of the orthogonal code set are chosen such that for all required data rates, the corresponding code words occupy a symbol/bit period.

This implies that although the chip rate is fixed for every available data rate, the code length changes from rate to rate. If the codes are chosen appropriately, the structure of the tree is such that the code orthogonality is maintained amongst the elements of the set even though they are of different lengths. For example, the code set ( C8 (8), C8 (7), C4 (3), C2 (1)) may be used to transmit data streams with required rates R, R, 2R and 4R respectively. As each code length should fill a data symbol/bit period, longer codes are allocated to lower rate data streams. The relationship between the code length and the transmit data rate may be used at the receiver to determine the rate of the received data.

For a given set of spreading factors, a set of codes needs to be selected f rom the code tree in an appropriate manner. Thus, methods of processing short codes that can operate efficiently, for example in a base station or a mobile station, without requiring large amounts of memory, are desired.

According to a first aspect of the present invention there is provided a code-division multiple access communications method, including the steps of:

in a code tree, having branches corresponding respectively to candidate codes for use in spreading the spectra of respective data streams, representing the positions in the tree of such branches by respective corresponding items of position information determined in accordance with a predetermined position information key; manipulating the items of position information corresponding respectively to branches of the tree to systematically effect one or more of the following operations: initial allocation of a set of codes from amongst the said candidate codes to respective data streams; addition to such a set of allocated codes of one or more further codes from amongst the said candidate codes; and removal from such a set of allocated codes of one or more of the allocated codes; the manipulation being such that, in the resulting set of codes after said operation, there is no code whose corresponding branch is a direct or indirect parent branch of the branch corresponding to any other code in that set; and using the codes of the allocated set to spread the spectra of the data streams is to which those codes have been allocated respectively.

According to a second aspect of the present invention there is provided a computer program which, when run on a computer, causes the computer to carry out a method according to the f irst aspect of the present invention.

According to a third aspect of the present invention there is provided code-division multiple access communications apparatus, including position information determining means operable, in a code tree having branches corresponding respectively to candidate codes for use in spreading the spectrum of respective data streams, to represent the positions in the tree of such branches by respective corresponding items of position information determined in accordance with a predetermined positioninformation key; position information manipulating means for manipulating the items of position information corresponding respectively to branches of the tree to systematically effect one or more of the following operations: initial allocation of a set of codes from amongst the said candidate codes to respective data streams; addition to such a set of allocated codes of one or more further codes from amongst the said candidate codes; and removal f rom such a set of allocated codes of one or more of the allocated codes; the manipulation being such that, in the resulting set of codes after said operation, there is no code whose corresponding branch is a direct or indirect parent branch of the branch corresponding to any other code in that set; and spreading means for using the codes of the allocated set to spread the spectra of the data streams to which those codes have been allocated respectively.

Such a method, computer program and apparatus can effect efficiently and systematically the allocation and amendment of a set of codes without requiring a large storage capacity.

It will be noted that a set of codes, as referred to herein, may contain just one code. For example, in the initial allocation operation, just one code could be allocated to a data stream.

Reference will now be made, by way of example, to the accompanying drawings, in which:

Figure 1, discussed hereinbefore, is a block diagram of parts of a transmitter for illustrating how data streams can be combined therein; Figure 2, discussed hereinbefore, of the accompanying drawings is a diagram illustrating an exemplary structure of an orthogonal code tree; Figure 3 is an example of a flag diagram corresponding to the orthogonal code tree shown in Figure 2; Figure 4 is a flowchart illustrating a process of initial short code assignment given a set of required spreading factors; Figure 5 is a flowchart illustrating a process for addition of short codes to an existing set; Figure 6 is a flowchart illustrating another process for addition of codes to an existing code set; and Figure 7 is a flowchart illustrating a process for removal from an existing code set of codes no longer required.

As discussed hereinbefore with reference to Figure 2, the codes at each level of the orthogonal code tree can be generated by concatenating a code at the immediate ly-preceding level (parent code) with an inverse or an exact copy of that parent code.

Figure 3 is an example of a flag diagram which can be constructed for the orthogonal code tree of Figure 2. In Figure 3, 0 and 1 f lags denote the inverting and copying functions respectively. The table below shows the f lags of Figure 3 in a truth table format.

Fl F2 F3 Decimal 0 0 0 0 0 0 1 1 0 1 0 2 0 1 1 3 0 0 4 0 1 5 1 0 6 1 1 7 SP=2 SF=4 SF=8 The leftmost column (11F111) of this table corresponds to generation of codes having a spreading f actor of 2. Assuming the code at the main branch C, (1) = 1, a 0 in the F1 column results in the generation of a short code of [l, -11 and a 1 generates a short code of [1, 11. The short code [1, -11 of spreading factor 2 thus corresponds to an item of position information (,,flag-word") of 11011 and the short code [ 1, 11, also of spreading factor 2, corresponds to a an item of position information (flag-word) of To generate codes with a spreading f actor of 4, starting from parent short code of [1, -11 a 0 in the F2 column corresponds to a short code of [1, -1, -1, 11 and a 1 in this column corresponds to a short code of [1, -1, 1, -11. The corresponding flagwords for these short codes are F1F2="0011 and F1F2=" 0111 respectively. Incidentally, the two further short codes available for spreading factor 4, namely and [1, 1, 1, 11, correspond respectively to the f lag words F1F2="1011 and F1F2="ll".

is The items of position information, or flag-words, represent the position of their corresponding branches relative to a reference position or branch, which in this example is the main branch at the f irst level. It can be seen that in this example, the item of position information has one symbol (i.e. one bit in this case) per unit change in level to reach the branch concerned from the main branch, and indicates whether the branch concerned is a first or second child branch of its parent branch and whether that parent branch in turn and any indirect parent branch in turn is also a f irst or second child branch.

Representing the positions of the branches using a position information key of the kind shown in Figure 3 has important technical effects, in particular in terms of reducing the memory requirements associated with short code selection and deselection and easing the manipulating of the short codes (by reducing the complexity of the manipulation operations to, for example, symbol- or bit-wise inversion, truncation operations).

of course, it will be appreciated that binary flag-words as illustrated in Figure 3 are just one particularly advantageous representation of position information which can be used in an embodiment of the present invention. Position information could also be represented, for example, by two-part alphanumeric codes in which one part represents the level in the tree and the other part represents the branch position within that level. However, binary representation is much more convenient for a micro-processor type implementation of a method embodying the present invention.

Figure 4 is a flowchart illustrating a process, according to an embodiment of the present invention, of initial short code assignment given a set of required is spreading factors. This set of required spreading factors in the present embodiment has one member per data stream requiring spreading. In other words, if n(=2 or more) data streams require the same spreading factor, the set of required spreading factors contains n members with the spreading factor concerned. The spreading factors are also placed in ascending order of spreading factor size in this embodiment.

In step S1 the maximum number of f lags Nmax in a flag-word is found. I'max is dependent on the maximum spreading factor SFmax as follows.

N - 1 SF max = 1092 max For each particular set of required spreading factors, it would be possible to calculate Nmax using the above formula (in this case SFmax is simply the maximum spreading factor in the required set of spreading factors). However, alternatively a preselected maximum allowed spreading factor SFmax is adopted that is independent of the particular set of required spreading factors called for by the current set of data streams to he transmitted. This reduces the algorithm complexity (and hence the implementation software or hardware (circuitry) complexity) since the value of Nmax can be preset.

As an example, if the maximum spreading factor SFmax is 256 then Nmax will be 8.

In step S2, a length r of the f irst f lag-word to be determined is found. In this embodiment, as the required spreading factors are prearranged in ascending order of spreading- factor size, the first flag-word to be assigned corresponds to the smallest spreading factor in the required set.

In step S3, an r-bit all-zero flag-word 000... 0 is formed. In step S4 the short code corresponding to the flag-word formed in S3 is evaluated and saved. This completes the generation of the first flag-word. In this evaluation step S4 a 2 r length short code is derived from the r-bit flag-word using the key that a zero bit in the flag word denotes concatenation of the parent short code and its reverse and a one bit denotes concatenation of the parent short code with a direct copy thereof. Hence, when the smallest spreading factor is 4, r for the first flag-word is 2 and that flag-word is set to 00 in step S3. In step S4 for example, the short code [1, -1, -1, 11 is formed for the flag-word 00.

Step S5 checks whether the next spreading factor in the spreading-factor set has the same spreading factor as the spreading factor just processed. If so, control moves to step S13, otherwise to step S6.

Step S13 takes the last flag-word formed (000... 0) and increments it by 1 to form the next flag-word (000... 1).

Step S14 checks whether there has been overflow, that is whether all of the 2 r possible r-bit flag-words have already been assigned. If overflow occurs, control moves to step S15 where, as no more codes may be selected, the process of code generation is terminated.

If overflow does not occur at step S14, the next step is S16. In step S16 the short code corresponding to the flag-word is evaluated and stored (as in step S4). Then, in step S17, it is checked to see if there are any more spreading factors in the spreading- factor set to be processed. If so, control loops back to step S5, otherwise it moves to step S18.

If in step S5 it is determined that the next spreading factor is different from the last-processed spreading factor, the next step is step SG. In step SG E"Tmax - r] 1 1 s are appended to the right of the f lag is word corresponding to the last-processed spreading factor, where r corresponds to the length of that f lag word (as calculated in step S2 or step S9 of a previous iteration) Referring to the flag tree diagram of Figure 3, the resulting flag-word corresponds to the last descendent of that branch of the tree corresponding to the last-determined flag-word i.e. the lowest branch at the highest (right-most) level of the tree which is descended from the branch corresponding to the last-determined flag-word.

Next, in step S7, the result generated in step SG is incremented by 1 and is called R. Provided that an overflow does not occur, the result of this, referring to the flag tree diagram of Figure 3, is to arrive at the uppermost branch in the highest (right-most) level of the tree that is not a child (indirect or direct) of any of the branches corresponding to already determined flag-words.

However, if there is overflow, which is checked for in step SS, there are no more codes available, as indicated in step S15, and processing ends.

If there is not overflow, then, in step S9, a new f lag-word length r for the next spreading factor to be assigned is determined.

In step S10, the r most significant bits of R are selected as the new flag-word. In Figure 3, this selection operation traverses the tree from right to left, as necessary to arrive at the level corresponding to the spreading factor currently under consideration.

In step S11 the short code corresponding to the flag-word generated in step S10 is evaluated and stored (as in step S4).

Step S12 checks to see whether there are any remaining short codes to be assigned and, if there are, control loops back to step SS, otherwise it moves to step S18.

is In step S18, which may be reached from step S12 or step S17, all of the short codes have been assigned.

The flag-word for the last short code assigned is saved as a reference. It may be used later, for example if more short codes need to be assigned. Then, in step S19, processing ends.

The following example considers the case when 2 codes with a spreading f actor of 4, and 3 codes with a spreading f actor of 8 are required. The spreading factor set in this case is therefore [4, 4, 8, 8, 81 In this example, the maximum spreading factor SFmax is 8, and therefore, in step SI, Nmax is set to 3.

In this example, the smallest spreading factor is 4. Hence, in step S2, the length r f or the f irst f lag word to be determined is calculated as 2.

Consequently, the first flag-word for the spreading factor of 4, obtained in step S3, is 00. This is evaluated as corresponding to the short code [1, -1, - 1, 1] in step S4.

In this example, a second short code to be assigned has the same spreading factor as the first, hence, the second flag-word will be calculated as 01 in step S13. Since there is no overflow, the corresponding short code is evaluated as [1, -1, 1, -1] in step S16.

The next short code to be assigned in this example has a different spreading factor, namely 8. Since Nmax is 3 and the current value of r is 2, a single 1 will be appended to the flag-word 01 in step S6, giving 011.

Adding 1 to this in step S7 makes R equal to 100.

In the case of a spreading f actor of 8, the new value of r will be 3. The 3 most signif icant bits of R, as selected in step Sio, will therefore be 100.

This, in step S12, corresponds to a short code of [1, 1, -1, -1, -1, -1, 1, 11.

In this example, the next, and final, 2 short is codes to be assigned have the same spreading factor as the last short code, Therefore 2 iterations through steps SS to S17 will generate f lag-words 101 and 110 which correspond to short codes of -11 and respectively.

The last f lag-word, 110 in this example, is saved as a reference in step S18 and processing ends.

Hence the code set generated for this example is It is not essential to start at the top of the code tree, as in the present embodiment, i.e. with a f lag-word made up of r zeros where r is the number of flags required for the smallest spreading factor. In another embodiment, the first f lag-word assigned is made up of r ones. In this embodiment, zeros are appended to the f lag-word in step S6 and the f lag-word is decremented by 1 in steps S7 and S13 as opposed to incremented.

It is also not necessary to assign the smallest spreading factor first. The largest spreading factor could be assigned first and then it would be possible to work systematically back from the children branches of the tree to their parents. In some situations it may be particularly advantageous, for example in terms of efficiency, to assign the codes in ascending order of level of branch in the tree (i. e. the smallest spreading f actor f irst) and in others in descending order of level of branch in the tree U. e. the largest spreading f actor first). For example, if the set of spreading f actors to be assigned contains a lot of comparatively low spreading factors, corresponding to higher-rate data streams, then assigning the codes in ascending order would probably be preferable. On the other hand, if the set of spreading factors to be assigned contains a lot of comparatively high spreading factors, corresponding to lower-rate data streams, then assigning the codes in descending order might be preferable. In one embodiment, the use of ascending or descending order may be predetermined in advance.

However, in another embodiment, the set of spreading factors could be examined and then a decision made accordingly as to whether to assign codes to those spreading factors in ascending or descending order.

In both uplinks and downlinks, a set of codes may be allocated to the initial data streams (data and control channels) during a call set-up period. In such an embodiment, a method as described hereinbefore with reference to Figure 4 may be used to allocate the required short codes. However, in some situations it may be desirable to allocate new, extra codes after the initial allocation of short codes has taken place. This could be useful in situations where the user needs to utilise additional data channels during an ongoing transmission. An example of this is in the uplink if the user wishes to send a data file during a voice transmission.

If new codes need to be added to an existing code set, it is not necessary to reallocate all of the codes from scratch. In a preferred embodiment of another aspect of the invention, as described below a procedure is used which utilises the remaining parts of the code tree to allocate the new codes.

The final flag-word, stored in step S18 of the flowchart of Figure 4, can be used as a reference flag word, for use in identifying which flag-words remain unallocated.

There are two possible scenarios to consider when adding new codes to an existing set.

The first is that the smallest required new spreading factor is greater or equal to that of the last code generated in the Figure 4 process. The is second is that the smallest required new spreading factor is smaller than that of the last code.

Figure 5 is a flowchart illustrating the addition of short codes to an existing set in the first scenario.

In this case, the new flag-words and the corresponding short codes are found using the reference flag-word as the starting point. The necessary condition at the start of the Figure 5 process is that each spreading factor in the set is greater than the spreading factor of the reference flag-word, (the "reference spreading factor"). In a preferred embodiment, the required spreading factors are arranged in ascending order and consequently this condition may be checked for all of the required spreading factors by comparing the first spreading factor in the group with the reference spreading factor.

In step S21, like in step S1, the largest required flag-word length, Nmax, is found. The length r of the reference flag-word is obtained in step S22. Then in step S23, the smallest new required spreading factor is compared with the spreading factor of the reference f lagword. The subsequent steps, SS to S19, are the same as described with reference to Figure 4. Thus, if the result of the comparison in step S23 is that the smallest new required spreading factor is different from the reference spreading factor, then control passes from step SS to step S6. Otherwise, control passes from step S5 to step S13. It should be noted that in this case in step S18, the reference flag-word is replaced by the final flag-word obtained in the addition process.

Figure 6 is a flowchart illustrating the addition of codes to an existing code set when the smallest required spreading factor is smaller than thatof the last short code assigned.

First of all, the required new spreading factors are divided into two groups. The first group contains the spreading factors that are greater to or equal to the spreading factor of the reference flag-word. Short codes may be allocated to this group according to the steps outlined with reference to Figure 5 and, as before, the reference flag-word is replaced by the final flag-word obtained.

The second group contains the spreading factors that satisfy the starting condition shown in Figure 6, that is they are smaller than the spreading factor of the last short code assigned. once short codes have been assigned to the f irst group, a short code is allocated to the smallest spreading factor in the second group according to the steps outlined below.

Once this short code has been generated, short codes can be assigned to the remaining spreading factors as before.

In step S31, the current reference flag-word (i.e.

the flag-word of the last short code assigned) is saved as 11sparell' for future use.

In steps S32, S33 and S34 the respective lengths n, Nmax and r of the reference flag-word, the largest required flag-word and the smallest required flag-word in the second group of spreading factors are found.

In step S35, the r most significant bits of the reference flag-word are selected and the result incremented by 1. Assuming there is no overflow, this produces a flag-word corresponding to the smallest spreading factor in the group and is referred to as R.

Step S36 cheeks for overflow. If there is overflow, then, according to step S37, there are no more codes available to be assigned and processing ends.

However, if there is no overflow, then the next step is S38. In step S38, the reference flag-word is replaced by R. Then in step S39, the short code corresponding to this flag-word R is generated and saved.

In step S40, (n-r) zeros are appended to the right of the flag-word R and the result saved as llspare211.

This is useful because the codes corresponding to flag words between (but excluding) 11sparell' and llspare211 remain unused and these codes and their children may be able to be used for future services.

If there are no more spreading factors in the group, then according to steps S41 and S42, processing is finished as all the required short codes have been assigned. However, otherwise, the remaining short codes can be assigned according to steps S5 to S19 as described with reference to Figure 4.

The following example considers the case where the flag-words 00 and 010 correspond to the current or existing code set and 5 short codes with respectively the spreading factors of 8, 32, 4, 4, and 4 need to be allocated. Note that in this example the current reference flag-word is 010.

In this example, the first group of spreading -19 factors will be {8, 32} and the second group will be {4, 4, 4}.

For the f irst group, GROUP1, Nmax is equal to 5.

The length r of the reference flag-word 010 is 3 and the reference spreading factor (8) is the same as the smallest member of GROUP1. Hence the first required flag-word, found in step S13 of Figure 5, will be 011.

This corresponds to a short code of 11. The flag-word 011 is also taken as the new reference flag-word.

The next member of GROUP1, 32, is different from the last spreading factor (8) considered. The result of appending [Nmax -r (=2)l is to the reference flag word, in step S6 of Figure 5, is 01111. After is incrementing this by 1, in step S7, the result is 10000.

Since for a spreading factor of 32, r is equal to 5, the next required flag-word will be 10000 and this is also taken as the new reference flag-word in step S18 of Figure 5.

Now considering the second group, GROUP2, the initial reference flag-word, stored in Step S18 of Figure 5, will be 10000. Hence, in step S31 of Figure 6, sparel is set to be 10000.

Next, according to steps S32, S33 and S34, the reference flag-word length n is 5, the longest required f lag-word in GROUP2 is Nmax = 2 and the length of the smallest required f lag-word in GROUP2 is r = 2.

So, using this information, R is found to be 11 in step S35. This is the flag-word corresponding to the first short code with the spreading factor 4 and becomes the new reference flag-word in step S38 of Figure 6. The corresponding short code, generated in step S39 is [1, 1, 1, 11. In step S40, spare2 is set to be 11000. Hence, codes corresponding to flag-words between 10000 and 11000 are unused and may be allocated in the future.

However, continuing with the current allocation (steps S41 and SS), the next spreading factor in GROUP2 is the same as that of the reference flag-word.

S Incrementing the reference flag-word in step S13 of Figure 6 results in 00 and an overflow in step S14.

Due to the overflow 00 is not a valid flag-word and no more codes may be generated.

In a preferred embodiment of another aspect of the invention it is possible to deselect codes no longer required by one or more channels and.reallocate them to other channels. Deselection corresponds to removing a service or user from a transmit signal. An example of when this may be desirable is when the transmission of is a file during a simultaneous file-voice transmission comes to an end. Another example is in the downlink (that is, base station to mobile stations), where signals for different users may be continually added and removed from the combined downlink transmit signal, and the efficient use of the available short codes is an important concern. In such situations, it is useful to be able to detect and reallocate the relevant short codes.

Figure 7 is a flowchart illustrating the removal of a deactivated code from a set of active codes.

Step S41 finds the length m of the flag-word corresponding to the deactivated short code ("the deactivated flag-word").

Then, in step S42, the least significant bit of the deactivated flag-word is inverted. That is, if it was a zero, it becomes a one and, if it was a one, it becomes a zero.

In step S43, the result of step S42 is compared with the m most significant bits of the flag-word of each member in turn of the active code set.

Step S44 checks whether there has been a match in S43. If there is a match, then, in step S45, the f lagword (as it was before least significant bit inversion in step S42) is saved for future use as, removed - i where i= 112,3 is a count value used for indexing the saved flag-words of deactivated codes. The count value i is incremented by 1, so that other deactivated codes may be saved, and in step S46, processing ends.

However, if a match is not found in step S44, the least significant bit of the deactivated flag-word is deleted in step S47. Then, in step S48, the deactivated flag-word is replaced by the result of step S47.

If, in step S49, the length of the result from S47 is zero, processing ends in step S50. Otherwise, however, control loops back to step S42.

The following example considers the removal of flag-words 01 and 1010 from the active flag-word set (00,01,100,1010).

In the case of 01, the inversion of the least significant bit in step S42 results in 00. As 00 is in the active set, a match will be found in steps S43 and S44. Therefore, in step S45, 01 will be saved as removed_1 for future use.

In the case of 1010, the result of the inversion in step S42 will be 1011. This does not match the flagword of any active code. Therefore in step S47 the least significant bit will be deleted to obtain 101.

The step S42 inversion of 101 gives the result 100. This is equal to one of the set of active f lag words and so, in step S45, removed - 2 will be set to 101 and will be kept for future use.

In the process of code allocation/deactivat ion, the code tree continuity may be lost. This happens when adding codes to the existing active code set, resulting in the generation of unused code segments, (e.g. a segment from "spare 111 to "spare 211) and when removing codes from the active code set, which leaves unallocated branches (a "removed-ill branch).

Such unused segments and branches are available for future code allocation. In a preferred embodiment, to improve the efficiency of the use of the available codes, these segments and branches are used first, that is before allocating the codes in the continuous part of the tree.

In an embodiment in which spare segments are allocated, it is possible to maintain code orthogonality provided the segment boundaries are not crossed during allocation. In an embodiment in which deactivated branches are reallocated, the codes corresponding to the branches and all their children may be used in a code allocation process as set out hereinbefore.

It will be appreciated that computer programs can be recorded on a variety of media, such as f loppy disks, hard disks, CD-ROMS, etc., or downloaded into a computer, for example from the Internet. It is intended that the attached claims should encompass a computer program by itself or in any other form.

It will also be appreciated that, although the embodiments described have used a code tree to select/deselect codes that are orthogonal (i.e. an orthogonal code tree), in other embodiments the invention could use code trees to select/deselect codes that are non-orthogonal, for example codes that have a limited degree of non-orthogonality. In this case there may be a little correlation between the codes, resulting in some degree of interference.

Claims (31)

CLAIMS:

1. A code-division multiple access communications method, including the steps of:

in a code tree, having branches corresponding respectively to candidate codes for use in spreading the spectra of respective data streams, representing the positions in the tree of such branches by respective corresponding items of position information determined in accordance with a predetermined position information key; manipulating the items of position information corresponding respectively to branches of the tree to systematically effect one or more of the following operations:

initial allocation of a set of codes from amongst the said candidate codes to respective data streams; addition to such a set of allocated codes of one or more further codes from amongst the said candidate codes; and removal from such a set of allocated codes of one or more of the allocated codes; the manipulation being such that, in the resulting set of codes.after said operation, there is no code whose corresponding branch is a direct or indirect parent branch of the branch corresponding to any other code in that set; and using the codes of the allocated set to spread the spectra of the data streams to which those codes have been allocated respectively.

2. A method as claimed in claim 1, wherein the said item of position information corresponding to a branch specifies a position of that branch relative to a predetermined reference position in the tree.

3. A method as claimed in claim 2, wherein the said predetermined reference position denotes the position of a reference branch of the said tree.

4. A method as claimed in claim 3, wherein the said reference branch is a branch at a first level of the tree.

5. A method as claimed in any preceding claim, wherein each level of the said orthogonal code tree corresponds to a different possible spreading factor of the said data streams.

G. A method as claimed in claim.5, wherein the spreading factor corresponding to the second level of the tree is double the spreading factor corresponding to the first level of the tree, and so on for each higher level of the tree.

7. A method as claimed in any preceding claim, wherein each branch in the tree, except for branches at the highest level of the tree, is a parent branch of respective first and second child branches at the next highest level of the tree, and the said item of position information corresponding to a particular branch includes information specifying whether that particular branch is the first or second child branch of its parent branch.

8. A method as claimed in claim 7, wherein the said item of position information corresponding to a particular branch further includes information specifying whether the parent branch of that particular branch is in turn the first or second child branch of its parent branch, and so on for all branches at lower levels of the tree back to the first level thereof that are indirect parent branches of the said particular branch.

9. A method as claimed in claim 7 or 8, wherein the said item of position information corresponding to a particular branch has one symbol per unit change in level from one level to the next required to reach the level of the said particular branch from the first level of the tree, which symbol indicates whether the branch at that next level is the first or second child branch of the parent branch at the said one level.

10. A method as claimed in claim 9, wherein the said symbol is a single bit having the value 11011 when the branch at the said next level is the first child branch and having the value 11111 when the branch at the said next level is the second child branch.

11. A method as claimed in any one of claims 7 to 10, wherein the code corresponding to one of the said first and second child branches of a particular parent branch is formed by concatenating the parent-branch code with the reverse of that parent-branch code, and the code corresponding to the other of the said first and second child branches of that particular parent branch is formed by concatenating the parent-branch code with a direct copy of that parent-branch code.

12. A method as claimed in any preceding claim, wherein the or each said operation is effected systematically by manipulating such items of position information to move sequentially through the said tree from one required branch thereof to the next required branch thereof.

13. A method as claimed in claim 12, wherein the movement from said one required branch to said next required branch in the tree is effected by manipulating such an item of position information corresponding to that one required branch to produce another such item of position information corresponding to the said next required branch.

14. A method as claimed in claim 12 or 13, wherein the sequential movement through the tree is carried out in order of level of branch.

15. A method as claimed in any one of claims 12 26- to 14, wherein the sequential movement through the tree is carried out within each level starting with the branch which is a first child branch of its direct parent branch and for which that direct parent branch in turn and any indirect parent branch in turn is also a first child branch.

16. A method as claimed in any one of claims 12 to 15, wherein, when the sequential movement from one required branch to the next required branch involves a change in level, the item of position information corresponding to the next required branch is derived from the item of position information corresponding to the said one required branch such that the position in its level of the next required branch is selected is according to the position in its level of the said one required branch.

17. A method as claimed in any preceding claim, wherein the said addition operation involves:

dividing respective required spreading factors of the further codes to be allocated into respective first and second groups of spreading factors, the first group containing spreading factors smaller than the spreading factor of the highest - spreading- factor code already allocated, and the second group containing spreading factors greater than or equal to the spreading factor of the said highest-spreading-factor code already allocated; and applying different processing to the said first and second groups.

18. A method as claimed in claim 17, wherein the said first group is processed after the said second group.

19. A method as claimed in claim 17 or 18, wherein 'the processing of the said first group includes:

checking whether the position, in the level corresponding to the highest spreading factor already allocated, of the last branch allocated in that level is such that no branch remains available for short-code allocation in the level corresponding to the smallest spreading factor in the said first group.

20. A method as claimed in any preceding claim, wherein the said deletion operation involves:

specifying the branch corresponding to the code to be deleted from the said set of allocated codes; in the case in which the specified branch is a first child branch of its parent branch, identifying the second child branch of that parent branch, and in the case in which the specified branch is a second is child branch of its parent branch, identifying the first child branch of that parent branch; if the identified child branch, or any branch at a higher level of the tree having the identified child branch as its direct or indirect parent branch, has its corresponding code allocated to a data stream, effecting just the deletion of the code corresponding to the specified branch; otherwise, moving back successively through lower levels of the tree to the direct parent branch and any indirect parent branch of the specified branch and deleting the code corresponding to that parent branch as well if, following deletion of the code corresponding to the specified branch, the parent branch concerned no longer has any child branch whose corresponding code is allocated to a data stream.

21. A method as claimed in any preceding claim, wherein the said resulting set of codes after said operation includes codes assigned to at least two data streams requiring different respective spreading factors.

22. A method as claimed in any preceding claim, further including the step of:

transmitting a signal in which the spread data streams are combined.

23. A method as claimed in any preceding claim, wherein the said initial allocation operation involves:

a) determining a spreading factor required for each data stream to be allocated a code in the operation and selecting initially the smallest spreading factor among the required spreading factors; b) identifying the level in the tree that corresponds to the selected spreading factor and forming a first item of position information corresponding to a predetermined start branch in that level; c) evaluating the code corresponding to the start branch and allocating that code to the, or if more than one to the first, data stream requiring that spreading factor; d) for each further data stream, if any, requiring that spreading factor, manipulating the said first item of position information to form further items of position information, as necessary, corresponding to respective further branches in the level corresponding to that spreading factor, so as to work through the branches in that level in a predetermined order of selection of the branches; e) evaluating the code corresponding to each such further branch in the level and allocating that code to the further data stream concerned; f) when the or each data stream requiring the presently-selected spreading factor has been allocated a code, reserving as a reference item the item of position information corresponding to the last branch processed in the level corresponding to that spreading factor, and selecting the next-highest required spreading factor amongst the data streams and identifying a new level in the tree corresponding to that spreading factor and manipulating the reserved reference item to form therefrom a new item of position information corresponding to a start branch in the new level, which start branch is the first branch, in a predetermined order of selection of branches at that level, that is not a child branch, directly or indirectly, of any branch at a lower level whose corresponding code has already been allocated to a data stream, and then carrying out the above steps (c) to (e) for the newly-selected spreading factor.

24. A method as claimed in any preceding claim, wherein the said code tree is an orthogonal code tree.

is

25. A computer program which, when running on a computer, causes the computer to carry out a method as claimed in any one of claims 1 to 24.

26. Code-division multiple access communications apparatus, including:

position information determining means operable, in a code tree having branches corresponding respectively to candidate codes for use in spreading the spectrum of respective data streams, to represent the positions in the tree of such branches by respective corresponding items of position information determined in accordance with a predetermined position information key; position information manipulating means for manipulating the items of position information corresponding respectively to branches of the tree to systematically effect one or more of the following operations:

initial allocation of a set of codes from amongst the said candidate codes to respective data streams; addition to such a set of allocated codes of one or more further codes from amongst the said candidate codes; and removal from such a set of allocated codes of one or more of the allocated codes; the manipulation being such that, in the resulting set of codes after said operation, there is no code whose corresponding branch is a direct or indirect parent branch of the branch corresponding to any other code in that set; and spreading means for using the codes of the allocated set to spread the spectra of the data streams to which those codes have been allocated respectively.

27. A base station, for use in a mobile communications network, including code-division is multiple access communications apparatus as claimed in claim 26.

28. A mobile station, for use in a mobile communications network, including code-division multiple access communications apparatus as claimed in claim 26.

29. A code-division multiple access communications method substantially as hereinbefore described with reference to the accompanying drawings.

30. Code-division multiple access communications apparatus substantially as hereinbefore described with reference to the accompanying drawings.

31. A computer program substantially as hereinbefore described with reference to the accompanying drawings.