Field of the invention

[0001] The present invention relates to communications of a plurality of user entities of multiple-access communication systems. Particularly, it relates to discriminating between signals, communications sessions or connections to/from various user entities in such systems by means of signature sequences.

Background of the invention [0002] Spectrum spreading of information symbols is a common method of achieving frequency diversity over a multipath frequency-selective fading propagation channel. It is also a method for providing simultaneous multiple-access to a number of users (user entities) using a shared communication channel. Spread-spectrum communication systems with multiple-access capability based on user-specific spreading codes are usually called Code-Division Multiple-Access (CDMA) systems (spreading codes are also commonly referred to as spreading signatures or signature sequences, but in the following "signature sequence (s)" is used as a generic term for such codes/sequences/signatures) .

[0003] Multiple-access capability is based on low (ideally zero) cross-correlation between the signature sequences. Multipath propagation, however, deteriorates the performance of CDMA systems, as the multiple reflections of each signature sequence element result in a distortion of the transmitted signature sequences. The cross-correlations of the received, distorted signature sequences deviate from the designed minimized values.

[0004] Orthogonal Frequency-Division Multiplexing (OFDM) transmission systems provide alternative transmission methods for simultaneous multiple-access communication. OFDM systems use a transmitted cyclic prefix for each block of transmitted symbols to make the multipath fading channel appear as a single-path channel on each of the orthogonal detected subcarriers in the receiver. This allows for less complex receivers than receivers used in single carrier-systems.

[0005] OFDM systems, however, cannot directly exploit the potential diversity gain of the multipath fading channel. Therefore so-called MC-CDMA, or Spread-OFDM, systems have been developed as a compromise between, on the one hand, the diversity gain and multiple-access capability of CDMA systems, and, on the other hand, receiver simplicity pertained to OFDM systems. These systems employ a method wherein each information symbol (possibly obtained by error-correction encoding) is multiplied with a user-specific signature consisting of a sequence of m spreading symbols (often referred to as chips) . The information symbols are then transmitted over m orthogonal subcarriers, where each chip of the spread information symbol modulates a dedicated subcarrier. Similar to an OFDM system, a cyclic prefix is transmitted for each block of transmitted information symbols.

[0006] Although MC-CDMA systems posses good properties of both CDMA and OFDM, such systems also inherit one of the drawbacks of CDMA systems: multiple-access inter-symbol interference in case of multipath propagation channels.

[0007] The (receiver) detector that minimizes the symbol error probability in such systems is the maximum a posteriori probability (MAP) detector. This detector, however, is often too complex for practical use, and therefore various suboptimal multi-user detection (MUD) methods have been developed. All such suboptimal MUD methods, however, are, in one way or another, approximations of the optimal, joint maximum likelihood (ML) detection. MUD receivers are typically still very complex, the complexity increasing exponentially with the length of signatures.

[0008] Traditionally, MUD methods have been independent of the signature design. The only aspect that typically influences MUD implementation complexity is the number of signatures. However, MUD complexity can also be reduced by specially designed signatures .

[0009] One such attempt includes Low-Density Spreading (LDS) signatures. An LDS signature of length m is a sequence of m spreading symbols (chips) such that w _c chips are not equal to zero, while m-w _c are equal to zero, while fulfilling w _c « m.

[0010] In one prior art example, the set of n LDS signatures are obtained from a single generic signature, consisting of w _c consecutive BPSK symbols followed by m-w _c zeros. The remaining n-1 signatures are obtained as cyclic shifts of the generic signature .

[0011] Once all the cyclic shifts are generated, the chips of all signatures are permuted (interleaved) in the same way, according to a single, common permutation vector to improve the diversity gain on the fading channel by placing the nonzero elements of each signature in the set as far apart as possible. The received signal is inversely permuted and then equalised, despread, using a MAP detector. [0012] A further prior art example of iterative multi-user detection based on LDS signatures is based on the belief propagation (BP) algorithm. This MUD algorithm aims at approximating the MAP detector by iterating belief values and assumes that a signature-sequence matrix is a low-density matrix of so-called Low-Density Parity-Check (LDPC) type. The belief propagation algorithm is of considerably lower complexity than the MAP detector and still, although depending on the particular signature-sequences being used, its performance can be close to that of the MAP detector.

[0013] Consequently, there are existing signature-sequence matrices that are constructed such that the signature sequences contain many zeros. The values of the non-zero elements of prior art are generated randomly. (Each column of the LDS indicator matrix is multiplied by a unit-envelope complex number with random, user-specific phase.) Summary of the invention

[0014] There exists a need for a communication system, and method and apparatus therefore, wherein signature sequences can be generated in a more explicit manner than is the case according to prior art, in particular with regard to the overloaded case.

[0015] It is an object of preferred embodiments of the present invention to provide a multiple-access communication system and method that eliminates or at least mitigates some prior art problem. [0016] Also, it is an object of an embodiment of the invention to at least mitigate problems in prior art associated with instantaneous and time-varying load of a communications system.

[0017] By restricting the various possible constellations of the elements of a signature-sequence matrix S, a technical solution is provided by means of which it is, e.g., considerably simpler to establish signature sequences resulting in satisfactory system performance as compared to the prior art.

[0018] Further characteristics of the present invention, and advantages thereof, will be evident from the following detailed description of preferred embodiments and appended drawings, which are given by way of example only, and are not to be construed as limiting in any way.

Brief description of the drawings

[0019] Figure 1 discloses an exemplary multiple-access communication system in which the present invention can be utilized.

[0020] Figure 2 discloses an example of a low density signature sequence matrix of a multiple access system based on OFDM.

[0021] Figs 3a-c disclose performance examples according to an embodiment of the present invention.

[0022] Figs 4a-c disclose performance examples according to a second embodiment of the present invention.

[0023] Figure 5 discloses a performance example according to another embodiment of the present invention.

Detailed description of the embodiments

[0024] To generate signature sequences, a straightforward solution is to generate n user-specific phases either once by a computer trial-and-error search producing the lowest information transmission error rate, or on-the-fly where a transmitter generates a new random signature sequence each time a user transmits data. This is typically done in a pseudo random way such that the receiver at any time knows the signature sequence.

[0025] A problem associated with the performance of system employing such low-density signature sequences designed for detection with the BP detector, however, is that such random or trial-and-error generation of signature sequences results in unpredictable performance, with the result that different users might experience different performances depending on the signature sequence constellation and the particular structure of the matrix.

[0026] In an overloaded situation there are more signature sequences than chips. In this case no orthogonal signature sets exist and interference is inherent.

[0027] In an example situation, each user may employ a single signature-set, typically allocated during the establishment of a connection, independently of the instantaneous number of concurrently used signatures by other users. [0028] It would be beneficial if a structured, deterministic approach could be used in the generation of low-density signature sequences. Further, it would be desirable with a deterministic approach resulting in a system that performs as close as possible to the single user bound when detected with the BP detector, also in overloaded scenarios.

[0029] The restriction of using a signature-sequence matrix wherein non-zero elements of any single row constitute distinct elements increases the probability of achieving unique decodability, i.e., that a received message can be decoded into a single unique possible interpretation, in particular with regard to overloaded systems.

[0030] As soon as a system becomes overloaded, i.e. the number of simultaneous users exceeds the number of available signature sequences, further requirements are imposed on the receiver end. Application of BP detection in an (overloaded) multiple-access system in general requires that the number of used signatures is equal to the number of columns of the signature matrix S, i.e., that all the signatures are transmitted all the time. In many practical systems, however, the number of users and the users' data rates are variable, implying that, if the BP detector is used in such systems, there should be a separate, i.e. different signature matrix for each possible number of simultaneous users/data rates. This would require that each time the number of used signatures in the system changes a new signature matrix is allocated and signalled to all involved user entities. Clearly, the control signalling in such systems would consume significant parts of the resources.

[0031] Use of a signature sequence matrix according to present invention, however, allows use of any number of the signature sequences provided by the matrix, i.e. it is not required that all sequences are used all the time. That is, LDS-CDMA systems based on the BP detector using the present invention support a variable number of users and/or data rates with only one signature matrix.

[0032] As was mentioned above, signature sequences consist of a plurality of symbols (chips) . These signature sequence symbols, or coefficients, are beneficially represented by columns of a matrix, since this allows use of the relatively simple system description described below. For the sake of simplicity, signature sequences are therefore described as columns of a signature-sequence matrix in the following description and claims. Naturally, signature sequences can be described in various other ways, e.g. by rows of a matrix, or as individual column or row vectors. Such variations, however, can be rewritten to a matrix as used herein in a straight-forward manner, and are therefore to be included in the signature sequence matrix definition used in the following description and claims .

[0033] Further, the term "set" as used herein follows the definition of the well-known set theory, i.e. every element of a set is unique and no two elements of the set are identical. Consequently, when a set includes e.g. W elements in the following description and claims, it follows from the above that the set includes W elements that are distinct.

[0034] An example of a simplified architecture of a multiple- access communication system 100 according to the present invention is shown in fig. 1. Although applicable in various kinds of multiple-access communication systems employing signature (spreading) sequences, such as single-carrier communication systems (e.g. WCDMA system) the present invention will be described in the following with reference to a system utilizing OFDM structure.

[0035] As can be seen from the figure, a plurality of user entities 102-109, such as mobile phones, smartphones or handheld computers having communication capabilities, are communicating with a stationary radio access node, such as a radio base station 101. The user entities 107 preferably comprises communications means including transmitter circuitry 1071 or receiver circuitry 1072, not excluding both. For the processing, such as signal processing or logic processing, also processing circuitry 1073 is included in the figure. In case of e.g. mobile phones of a radio communications system, transmit circuitry 1071 or receive circuitry 1072 should include radio frequency circuitry. For non-radio frequency systems, e.g. optical systems, other carrier frequencies than radio frequencies may be of interest and circuitry for corresponding frequencies then be included. The radio access node is responsible for physical-layer processing such as modulation and spreading, and, depending on the particular communication system, the radio access node is denoted, e.g., base station, NodeB or eNodeB. The radio base station 101 preferably comprises communications means, including transmitter circuitry 1011 or receiver circuitry 1012, not excluding both. For the processing, also processing circuitry 1013 is included in the figure. In case of a radio base station transmit circuitry 1011 or receive circuitry 1012 should include radio frequency circuitry. For non-radio frequency systems, other carrier frequencies than radio frequencies may be of interest and circuitry for corresponding frequencies then be included. A communication network consists of, in general, a radio access network (RAN) and a core network. For the sake of simplicity, however, only (part of) the radio access network is, schematically, disclosed. The core network will not be described further. Although only one radio access node is disclosed in the figure, a multi-access communication system in general comprises a plurality of radio access nodes to provide user entity mobility. Typically, a radio access node handles communication over a radio interface in a certain coverage area.

[0036] The communication between the user entities 102-109 and the radio access node employ signature sequences (spreading codes) in uplink and/or downlink to discriminate between signals to/from different users. [0037] As is typical in CDMA systems, either a base station, such as base station 101, acts as a resource manager and assigns signature sequences to users (user entities), for instance at the time a connection is established, or a standardized procedure assures that a unique certain signature sequence is used by a user without explicit prior communication between the base station and the user.

[0038] Although applicable in single-carrier communication systems, the signature sequences according to the present invention will be described with reference to an OFDM system in the following exemplary embodiment. The use of signature sequences in OFDM-type systems allows for subcarrier use by more than one simultaneous user. [0039] With regard to the system of fig. 1, and communication systems employing signature sequences to discriminate signals from different users in general, a signal model can be defined according to the following. If the system contains n signatures, and each signature consists of m elements, (chips), a matrix S having m rows and n columns (i.e. a matrix of dimension mxn) can be defined where the n columns define the n signature sequences (transmitted by the user equipments UE ₁ , / = 0,...,n-l .

[0040] Further, if the information symbols associated with each of the n signature sequences X ₁ ,l = 0,...,n-l , are arranged in a column vector form x, the received signal vector r consisting of n received chip-values, after passing through an additive white Gaussian noise (AWGN) channel, can be written as: r = Sx+n (1) , where n represents complex-valued white additive Gaussian noise. (In case of transmission over a fading channel, each chip is multiplied by a corresponding channel coefficient.)

[0041] If the number u of simultaneous users is equal to or is less than the number of chips m of the signature sequences, an orthogonal signature-sequence set can always be found, thereby providing for low (zero in the case of an AWGN channel) inter- user interference.

[0042] With regard to an overloaded system, on the other hand, that is, the situation where u>m, there are more signature sequences than chips, and in this case no orthogonal signature sets exists and interference is inherent.

[0043] As was stated above, this makes detection of a desired signal more difficult which, in general, imposes additional requirements of the detector. These requirements, however, can, at least to some extent, be alleviated by careful selection of the signature sequences being used. Preferably the detector complexity should be as low as possible, for example, the BP- detection method fulfils such relatively low complexity and is applicable to any choice of the actual values of the signature sequences . [0044] The present invention is related to such selection of signature sequences, and more specifically to signature sequences that can be written as a low density (sparse) matrix, that is, a matrix populated primarily with zeros, and in particular a matrix wherein the number of non-zero elements of any row of said matrix is substantially smaller than the number of zero elements of the said row, and wherein the number of non-zero elements of any column of said matrix is substantially smaller than the number of zero elements of the said column. Further, at least one element of each row and column must constitute a non-zero element.

[0045] Figure 2 discloses an example of the concept of a low density signature sequence matrix of an OFDM based system. This means that instead of using the signature sequences for spreading symbols of an individual user entity over the whole channel frequency spectrum as in, e.g., WCDMA, the signature sequences are used to modulate which subcarriers a particular user entity will use in the communication with the radio access node. According to the disclosed example, the filled (non-blank) positions in the matrix in figure 2 represent non-zero elements. Further, according to the exemplary matrix disclosed in figure 2, there are 24 signature sequences, each modulating 2 subcarriers out of a total of 24 subcarriers, i.e. the system supports simultaneous transmission of up to 24 user entities using only 12 subcarriers. It is, of course, possible to use signature sequences that consist of different number of nonzero elements, i.e. one signature sequence may employ a single non-zero element, while another employs three, four or more non-zero elements.

[0046] As was mentioned above, the performance of systems utilizing such matrices depend to a large extent on the particular values to which the non-zero elements of the signature sequences are set.

[0047] The low-density signature sequences according to the present invention are columns of a deterministically constructed signature matrix. The columns of S are then signatures used by the transmitting and receiving device.

[0048] According to the present invention, the signature matrix S is constructed as follows: as was mentioned above, S is of the low-density type. For example, S can be constructed in a manner such that it has non-zero entries only in positions indicated by a low-density parity-check (LDPC) indicator matrix. The design of this kind of matrices have been subject to extensive research over the past years in a completely different context (channel coding theory) . The number of columns in S is the total number of signature sequences available in the cell, or system, and the number of rows in S is the number of chips over which all transmitted information can be spread.

[0049] According to the present invention, it has been realized that the performance of the system can be improved by assigning values to the non-zero elements of the matrix S in a manner such that no two non-zero elements on a single row are the same, i.e. all elements on a single row are distinct. Further, the values of the non-zero elements of matrix S are elements of a finite complex-valued constellation set C, i.e. the values are selected from a limited number of possible values. Examples of such constellation sets will be given below. [0050] As was mentioned above, the restriction of using a matrix wherein non-zero elements of any single row of constitute distinct elements has the advantage that decodability properties of the system are improved, in particular with regard to overloaded systems. Also, it is considerably simpler to establish signature sequences resulting in satisfactory- system performance as compared to the prior art.

[0051] The above can also be restricted such that the choice of the non-zero values of S are further limited in the sense that not only must all non-zero elements of each row in S be distinct, but the signature constellation set C also being chosen such that its size equals the maximum number of non-zero elements that appear in a single row of S .

[0052] With regard to the unique decodability, this can be verified according to the following:

[0053] Row-wise unique decodability: the sums of non-zero elements in each row of S, where each non-zero row element is modulated with an arbitrary information symbol from the constellation of q information symbols, are all distinct for distinct vectors of modulating information symbols. (All vectors Sx are distinct in each element) .

[0054] If this condition is fulfilled, then the sums of all columns of S, modulated with arbitrary information symbols, from the constellation of q information symbols, are all distinct for distinct vectors of modulating information symbols. (When all vectors Sx are distinct in each element the vectors are all distinct.) In other words, if S is row-wise uniquely decodable, S will also be uniquely decodable.

[0055] Assuming that the above condition is fulfilled, the sums of an arbitrary number of non-zero elements in each row, where each non-zero row element is modulated with an arbitrary information symbol, from the constellation of q information symbols, are all distinct for distinct vectors of modulating information symbols. This makes it probable that the sums of an arbitrary number of columns of S , modulated with arbitrary information symbols from the constellation of q information symbols, are all distinct for distinct vectors of modulating information symbols, with the result that S is uniquely decodable for any number of active users, so it can be used in scalable systems. [0056] The property of a signature sequence matrix S being uniquely decodable can be tested through a search over all possible combinations of transmitted data in vectors x .

[0057] In the following the signature-sequence constellation fulfilling one or more of the above criteria will be described. [0058] The size of the signature constellation set is preferably as small as possible while still satisfying the abovementioned lower-bound. That is, a size of the signature constellation set C that is at least equal to the maximum number of non-zero elements that can appear in a row of S . [0059] One way of defining the elements of said set of elements C are elements being describable by values of a mathematical expression constituting a periodical or substantially periodical function.

[0060] This is, for example, fulfilled by a signature constellation set C constituting a (partial) PSK-constellation according to:

, where W is the number of elements of the signature constellation set C, e.g. the maximum number of non-zero elements occurring in a row of S . [0061] If S is constructed using these properties, significantly better performance is obtained as compared to the random (trial-and-error) prior art signature sequences. As will be shown in the following, this is true in particular when the system is overloaded, that is, when the number of columns in said signature sequence matrix S is strictly larger than the number of rows.

[0062] For overloaded scenarios, the performance of the system can typically be measured as the gap to the single-user bound (the performance of a system employing only one user, hence free from inter-user interference) . Depending on the choice of the set of signature sequences this gap may be smaller or larger (even for the MAP detector) .

[0063] In noise-free conditions, both with the MAP and BP detection algorithms, it should be possible to unambiguously detect the information symbols that modulate the different LDS signatures. This is possible if the modulated signatures represent a uniquely decodable code.

[0064] If P in eq. (2) is chosen large enough, sequences are likely to be uniquely decodable. On the other hand, it is desirable that P is as small as possible because signature constellation points are then spread out over the unit circle, which can be beneficial for the minimum distance properties of the transmitted signal alternatives. Consequently, the non-zero elements of the matrix S can all advantageously consist of unit-modulus elements, or at least substantially unit modulus elements. Use of elements having the same or substantially the same modulus is beneficial from power control point of view. This means that in this embodiment the choice of non-zero values is limited to relatively restricted signature constellation. [0065] For example , P in ( 2 ) can be chosen as :

1 . P = q ^w ( 3 )

2 . P = q W ( 4 )

3. _{P = q} ^. _W ≡^^- ( 5 ) gcd(q,W) where q is the largest information constellation size employed by said active users, that is, the number of symbol alternatives provided by the particular modulation scheme being used, e.g. 2 for BPSK, 4 for QPSK etc. (the information constellation can, for example, be any from the group: M-PSK, M-QAM) . Further, min(q,W) is the smallest of the numbers q and W, and gcd(q,W) is the greatest integer dividing both q and W without remainder.

[0066] In many practical communication systems, the number of users is variable, i.e., the systems are scalable. In, for instance, the uplink of a mobile communication system multiple users concurrently transmit signals to the same base station. The number of concurrently received signals, although variable, is always known at the base station receiver. Furthermore, in synchronous mobile systems, like LTE, the synchronicity allows the use of BP detection.

[0067] A signature sequence according to the present invention allows use of any number of columns of S to be used as signature sequences, i.e. it is not required that all signature sequences are always being simultaneously used. This further has the advantage that a signature sequence need be assigned only once at the time of establishment of the connection between said user entity and communication system to be maintained for the duration of said connection.

[0068] As was mentioned above, use of BP detection has advantages, and in order to make BP detection feasible in a scalable communication system using LDS signature sequences, it has to be ensured that the signature sequences are uniquely decodable in an arbitrary scaled system (see above) . Secondly, the belief-propagation receiver has to support the system scalability. Prior art does not offer any solution to these two problems. The present invention, however, does.

[0069] Construction of S with the above choices of P has been verified by simulations to typically be uniquely decodable for a large class of LDPC indicator matrices. [0070] In a further embodiment, said signature-sequence matrix S is further restricted such that also non-zero elements of any single column of said matrix S constitute distinct elements of said finite set of elements C.

[0071] In figure 3a-c, 4a-c and figure 5 simulation results are given for the signature sequence designs (3) and (4) and for the scenario where all users are always transmitting data. The performance is given in terms of the probability of a symbol error averaged over all the u users in the system.

[0072] Figures 3a-c show the BPSK-performance for a 150% loaded system with a signature matrix of size 10x15, 14x21, and 16x24, respectively.

[0073] The performance of signature sequence design (3) and (4) outperform the randomly chosen signature sequences from the prior art and approach the single user bound within tenths of a decibel.

[0074] Figures 4a-c show three QPSK-scenarios with a 150% load and with a signature matrix of size 10x15, 14x21, and 16x24, respectively. The performance of signature sequence design (4) outperforms the randomly chosen signature sequences from the prior art by many decibels at higher SNRs. [0075] From the QPSK simulation results it is clear that the users experience a performance loss compared to the single user performance. This leads to a reduction of the data throughput for individual users. On the other hand, there are 50% more users in the system and hence, the cell throughput, the sum of all users' throughputs increases.

[0076] Figure 5 illustrates the performance of the (10,15) system with QPSK modulation for the case where only 10 of the 15 possible codes are used instantaneously, that is a scaled system performance of QPSK, 150%-load (10,15) system with instantaneous load of 100%. In the simulations, there are 5 (randomly chosen) signature sequences that are not used by any user. This is one example illustrating the strength of signature sequences according to the present invention for scaled system scenarios.

[0077] While the invention has been described in connection with specific embodiments or features thereof, it will be understood that it is capable of modifications. This specification is intended to cover any variations, uses, adaptations or implementations of the invention; not excluding software enabled units and devices, processing in different sequential order where non-critical, or mutually non-exclusive combinations of features or embodiments; within the scope of subsequent claims following, in general, the principles of the invention as would be obvious to a person skilled in the art to which the invention pertains.

[0078] As a non-exclusive example, although the invention has been disclosed in connection with a spread-OFDM system above, the invention is equally applicable in any system utilizing signature sequences to discriminate between users.