Title of Invention

A METHOD AND APPARATUS FOR DETECTING A SIGNAL

Abstract Method and apparatus for detecting a signal are disclosed, wherein first set of symbols represents a signal received in a receiver. A second set of symbols is estimated, representing the signal transmitted at a transmitter using a sphere decoding technique. The estimation may employ at least two modulation schemes. Reliability information relating to bits forming a symbol may be determined for at least one symbol of the second set. Furthermore, reliability information relating to the signal may be taken into account in estimating at least one symbol of the second set.
Full Text Signal detection using sphere decoding technique BACKGROUND OF THE INVENTION
FIELD OF THE INVENTION”
The present invention relates in general to signal detection. In particular the present invention relates to signal detection using sphere decoding techniques.
DESCRIPTION OF THE RELATED ART
Recently in the area of communications systems, multiple input multiple output (MIMO) technology has gained a lot of attention in the research community. An important and interesting research area of MIMO systems, and also in connection with other systems, is the detection of the received signals.
Detection of received signal refers to determining which signals were sent based on received signal. Using a vector notation, where in the case of a MIMO system each vector component xj of a sent signal x represents a signal (symbol) sent from one MIMO antenna, the aim in signal decoding is to determine a sent signal x based on and channel knowledge and a received signal r. A symbol xi needs to be a valid symbol of the modulation scheme used in the transmission. In principle, the modulation scheme symbol appearing due to channel distortions to be nearest to the received symbol ri- is determined to be the sent symbol xi. Calculation of distances to all possible symbols is an extremely complicated task, so in practice the nearest symbol within a certain search area is selected as the sent symbol xi The difficulty is to find this modulation scheme symbol nearest to the received symbol ri, or candidates for this nearest symbol, in an efficient way.
Different algorithms have been proposed, discussed and tested for signal detection. One of these signal detection algorithms is called a Sphere Decoder, and it has been proposed by E. Viterbo and J. Boutros in, “A Universal Lattice Code Decoder for Fading Channels”, IEEE Transactions on Information Theory, Vol.45, No.5, July 1999, pp. 1639-1642. The Sphere Decoder is originally presented for decoding a coded signal, but it is applicable also in signal detection. A sphere decoder is a sub-optimal maximum likelihood method with fee advantage of low complexity. In the sphere coding, the signal components xi are determined one by one by searching a nearest valid modulation scheme symbol for a received symbol ri within a search area.

2
The basic idea in a Sphere Decoder is to process vectors and matrices representing the received symbols sad channel knowledge so that interference between the sent symbols x1, x2,…..xN caused by a channel is taken into account and at the same time it is possible 10 determine a first symbol xN independently of the other symbols. Using fee first determined symbol xN it is possible to determine symbol xN and so on, resulting in. a vector x containing symbols x. The first determined
xN-1symbol is denoted here with the index N, because the calculations in a Sphere Decoder typically involve upper-triangular matrices.
When information is transmitted and distorted in a noisy channel, the data becomes fuzzy and any decision made in the receiver side may lead to errors and lost of information. Soft detection has the target of keeping some reliability information on a detected symbol and making a “hard” decision as late as possible in the receiver. The known sphere decoders are designed as a “hard” output detector, returning as the sent signal x the vector of constellation symbols with the shortest Euclidean distance to the received signal r. Furthermore, it is possible that there is available some a priori information relating to the sent signal. This a priori information could enhance the accuracy of determining the sent signal x.
In many communication systems there are defined a number of modulation schemes, which can be used. The modulation scheme in use may vary from user to user, depending for example on the transmission rate relating to each user. Current sphere detection methods are not able to decode signals relating to different modulation schemes simultaneously.
There is thus a need for more versatile signal detection methods. The aim of the embodiments of this invention is to provide signal detection using sphere decoding for various purposes.
It is appreciated that although problems relating to signal detection using sphere decoding have been discussed in connection with MIMO systems: they may be relevant also in other communications systems.
SUMMARY OF THE INVENTION
A first aspect of the present invention relates to a method for detecting a signal, said method comprising

3
receiving a first set of symbols representing a signal received in a receiver, and
estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein the estimation, employs at least two modulation schemes.
A second aspect of the present invention relates to a method for detecting a signal,
said method comprising
receiving a first set of symbols representing a signal received at a receiver, estimating a second set of symbols representing said signal transmitted at a
transmitter using a sphere decoding technique, and
determining reliability information relating to bits forming a symbol for at
least one symbol of said second set.
A third aspect of fee present invention relates to a method for detecting a signal, said method comprising
receiving a first sex of symbols representing a signal received at a receiver, and
estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of .the second set.
A fourth aspect of the present invention relates to an apparatus for detecting a signal, said apparatus configured to
receive a first set of symbols representing a signal received at a receiver antenna, and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding .technique, wherein the estimation employs at least two modulation schemes.
A fifth aspect of the present invention relates to an apparatus for detecting a signal, said apparatus configured to
receive a first set of symbols representing a signal received at a receiver antenna, and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, and

4
determine reliability information. relating to bits forming a symbol for at least one symbol of said second set
A sixth aspect of the present invention relates to an apparatus for detecting a signal, said apparatus configured to
receive a first set of symbols representing a signal received at a receiver antenna, and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein reliability information ) relating to said signal is taken into account in estimating at least one symbol of the second set
A seventh aspect of the present invention relates to a system for detecting a signal, the system comprising:
A receiving means for receiving a first set of symbols representing a signal
received in a receiver: and
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein the estimating means employs at least two modulation schemes.
An eighth aspect of the present invention relates to a system for detecting a signal, the system comprising:
receiving means for receiving a first set of symbols representing a signal received at a receiver;
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique; and
determining means for determining reliability information relating to bits forming a symbol for at least one symbol of said second set of symbols.
A ninth aspect of the present invention relates to a system for detecting a signal, the system comprising:
receiving means for receiving a first set of symbols representing a signal received at a receiver, and
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of the second set of symbols.

5
BRIEF DESCRIPTOR OF THE DRAWINGS
Embodiments of the present invention will now be described by way of example only with reference to the accompanying drawings, in which: Figure 1 shows schematically a MIMO communication system with which embodiments of the invention can be used;
Figure 2 shows graphically the concept of a Sphere Decoder for signal detection:
Figure 3 A shows a simplified flowchart of a Sphere Decoder for signal detection
in accordance with an embodiment of the invention,
Figure 3B shows a simplified flowchart of a Sphere Decoder for signal detection
in accordance with a first embodiment of the invention,
Figure 3C shows a simplified flowchart of a Sphere Decoder for signal detection
in accordance with a second embodiment of the invention,
Figure 3D shows a simplified flowchart of a Sphere Decoder for signal detection
in accordance with a third embodiment of the invention.
Figure 4 shows schematically a Sphere Decoder and an apparatus for signal
detection in accordance with an embodiment of the invention,
Figure 5 shows, as an example, a flowchart of a Mixed 4-QAM/16-QAM Sphere
Decoder for signal detection in accordance with the first embodiment of the
invention,
Figure 6 shows, as an example, a 4-QAM constellation with Gray Mapping
showing the distances from a received point to closest constellation points where
the first bit is 0 and 1,
Figure 7 shows, as an example, bit likelihood creation for the first bit of a
received symbol r\ in a 4-QAM system with one transmitter/receiver antenna,
Figure 8 shows a 16-QAM constellation with Gray Mapping which is used as an
Example,
Figure 9 shows, as an example, steps for obtaining distances d0 and d\ for the first
bit of a received symbol ri in a 16-QAM system with one transmitter/receiver
antenna,
Figure 10 shows, as an example, a flowchart for a 16-QAM Soft Output Sphere
Decoder for signal detection in accordance with the second embodiment of the
invention,
Figure 11 shows, as an example, weighted candidates for a Soft Additional input”
Sphere Decoder for a 4-QAM system in accordance with the third embodiment
of the invention^

6
Figure 12 shows, as an example weighted candidates for a Soft Additional Input
Sphere Decoder for a 16-QAMsjsiem. in accordance with the third embodiment
of the invention,
Figure 13A shows, as an example. a. first part of a flowchart for a 16-QAM Soft
Additional Input Sphere Decode- for signal detection in accordance with the third
embodiment of the invention, and
Figure 13B shows the second part of the flowchart in Figure 13A.
DETAILED DESCRIPTION OF THE PREFERRED EMBODIMEATS
In the following description, reference is often made to a multiple-input-multiple-output (WMO) system. The present invention is, however, not limited to decoding signals of a MIMO system. Other systems, where the present invention may be applicable, are discussed below.
In the following description. reference is made to a Sphere Decoder for keeping the naming hi line with me original Sphere Decoder. It is appreciated, however, that signal detection using a Sphere Decoder concentrates on signal detection and does not imply the presence of any coding in the received signal. The information carried by the received signal may be coded or it may be uncoded.
Figure 1 shows schematically a MEMO communications system as an example of a communications system where embodiments of the invention can. be used. The MTMO communications system in Figure 1 contains a transmit antenna array containing Nt transmit antennas and a receive antenna array containing Nr receive antennas. In the following, the symmetry constraint Nt = Nr is considered. The vector transmitted during, each time period is denoted as x = [x1, x2,……,. XN ] where
each component is an independent choice, as an example, from a complex M-QAM (Quadrature Amplitude Modulation) constellation. The transmitted signal is created as x = vL, whereL is the lattice generator matrix with basis {m1,m2>.-.,m3,},and {v= v1,v2…,.vN} is the integer component vector to which
the information bits are mapped
The received signal is represented, by r = Hx + n 5 where the matrix H is a channel matrix and n represents noise. In connection with the MTMO system, a channel matrix H represents channels of a multiple-input-multiple-output system and x,-represents a symbol transmitted by one of the antennas of the multiple-input





9
It is appreciated that although above reference is made to determining symbols xi
one by one, it may be possible 10 determine fee symbols in groups by using different matrix manipulation techniques.
The Sphere decoder algorithm may be modified to reduce the complexity during the search for the best point inside the sphere. The original sphere decoder starts the search in the surface of the sphere and 'zigzags towards the center looking for the closest lattice point to the received one. In contrast, the reduced complexity algorithm proposed by C.P. Schnorr and M. Euchner, in “Lattice basis reduction: improved practical algorithms and solving subset sum problems”, Mathematical Programming, Vol.66, 1994, pp. 181-191, proposes to start the search from the center of the sphere and move outwards. Once a valid lattice point is found inside the sphere, its radius is decreased to the distance of the newly discovered lattice point from the center and the search moves to the next point. Also A.M, Chan and I. Lee discuss a reduced sphere decoder in “A New Reduced-Complexity Sphere Decoder For Multiple Antenna Systems”, IEEE International conference on Communications ICC ‘02, Vol.1, No.28, May 2002, pp. 460-464.
By starting from the center of the sphere, the sphere decoder can be expected to find the closest symbol in less number of operations than when starting from the boundary. Two main additions to the original sphere decoder have to be considered in order to reduce its complexity. First, for each, lower and upper
bound of the ith coordinate the candidate symbols of x within them are sorted in


an ascending order according to the metric ½ yij-Si½ and stored in a vector Zi

Here yi, is a vector with elements [yi,1, yi,2 .,.], containing all the constellation points between IBi and UBi. This forces the algorithm to search the coordinates closest to the middle of the interval defined by the bounds rather than search the coordinates near the lower bound first. Secondly, every time a lattice point £ is found within the sphere, the vector T in Equation 10 and all the, lower and upper bounds in Equations 7 and 8 are updated. These updates eliminate some of the candidate coordinates at the rightmost ends of the zi- vector by reducing the length of the possible symbols. As shown in Figure 5, tee vector zi contains sorted components of vectors y-, and vector p, which is the received signal with the channel inverted. The rest of the algorithm, remains unchanged, and the iterations continue until a set of symbols is stored in x. Embodiments of the present invention may use the reduced complexity sphere decoder concept

10
Figure 3A shows a simplified flowchart of a Sphere Decoder signal detection method 300 in accordance with an embodiment of the invention. For simplicity, a symmetric case, where the number of transmitter and receiver antennas is equal to N-. Furthermore, the sent and received signals are assumed to have real values and only the main features of determining iteratively sent symbols xi are shown. In step 301, a counter i is initialised to value Nt. A symbol xi is determined in step 302, in a way discussed above, using for example the relevant steps of the reduced complexity Sphere Decoder or steps of the original Sphere Decoder. Step 302 contains two sub-steps. ID step 302a, the modulation of the sent symbol x, is taken into account in determining the symbol x,-. In step 302b, a priori information is taken into account in determining the sent symbol Xi. After fee symbol x has been determined, the value of the counter is checked in step 303. If all symbols xs have not been determined, the counter value is decreased in step 304 and the method proceeds to determine the next symbol xi. if all symbols xi have been determined, the vector s is output in step 305. In step 306, reliability information relating to bits forming symbols is determined for the vector x.
In Figure 3A, step 302a allows detection of symbols xi of different modulation schemes. The modulation scheme of xi;- typically affects the search area for symbol Xi. Step 302b allows taking into account soft a priori information. This a priori information is typically used in weighting the candidate symbols within the search area. The a priori information pertaining to at least some information.bits or symbols may be any reliability information relating to the sent or received signal. It may be obtained, for example, from a channel decoder or an error detector following a Sphere Decoder Detector or from previously detected symbols within the Sphere Decoder detector. Other examples include a priori information coming from any external source, such as the channel decoder or error detector of other information streams belonging to another user or service.
The vector x in step 305 is typically a hard output in that sense that although soft a priori information may have been used in step 302. the output contains only a set of symbols i,-. Step 306, in turn, reliability information relating to bits forming symbols is determined at least for one symbol, but typically for all symbols xi This reliability information relating to bits forming symbols may be used for calculating soft information for symbols, if needed.
It is appreciated that an alternative to the flowchart shown in Figure 3 A is to have the step 306 inside step 302. This means that a soft value for symbol x,- is

11
determined before determining the nest symbol xi-_I. In this case the mathematic operations relating to steps 3G_-b and 506 are typically carried out together.
It is possible that only one of steps 302a. 302b and 306 is present in method 300. This examples are illustrates in Figures 3B: 3C and 3D, which show flowcharts for methods 310, 320 and 330. Alternatively any two of these steps may be present. Furthermore, as Figure 3A shows, all steps 302a, 302b and 306 may be present in method 300.
In the following three embodiments of the invention are discussed hi more detail. A first embodiment of the invention relates to detecting symbols of different modulation schemes simultaneously. A Sphere Decoder for signal detection in accordance with, the first embodiment is here called a Mixed Sphere Decoder for signal detection. A second embodiment of the invention relates to obtaining soft values hi the output of a Sphere Decoder. A Sphere Decoder for signal detection in accordance with the second embodiment is here called a Soft Output Sphere Decoder for signal detection. A third embodiment of the invention is directed to receiving soft additional a priori information, typically in form of probabilities. A Sphere Decoder for signal detection in accordance with the third embodiment is here called a Soft Additional Input Sphere Decoder for signal detection.
Figure 4 shows schematically a Sphere Decoder 404 for signal detection and a device 400 in accordance with an embodiment of the invention. The device 400 contains, as an example, a set of antennas 401a, 401b, and 401c. As an example, this device 400 relates to spread spectrum system. Each antenna 401 is connected to a RF/despreading unit 402. The RF/despreading units 402 are connected to a channel estimator 403, which is responsible for determining the channel matrix H and the received symbols r. From the channel estimator 403 information about the received symbols and about the channel properties is fed to the Sphere Decoder 404 for signal detection. The Sphere Decoder 404 for signal detection may be a Mixed Sphere Decoder, a Soft Additional Input Sphere Decoder, and/or a Soft Output Sphere Decoder. The output of the Sphere Decoder 404 is connected to a channel code decoder 405. As one example of a source of a priori information, Figure 4 shows how information from the channel code decoder 405 is fed back to the Sphere Detector 404 for signal detection.
The Sphere Decoder 404 for signal detection may be implemented as suitable programming code for a programmable processor. Alternatively, the Sphere

12
Decoder 400 may be implemented as hardware specially designed for sphere decoding.
The device 400 may be a portable communications device. It may be, for example, user equipment, a mobile telephone, a mobile station, a personal digital assistant, or a laptop computer. The device 400 may alternatively be a fixed device. Furthermore, the device 400 may be a network element for a communications network. It may be. for example, a transceiver network element for a cellular communications system.
It is appreciated that the RF part of a receiver is formed of the RF and despreading units 402. The base band part of a receiver is formed of the channel estimator 403, the signal detector 404 using a Sphere Decoder, and the channel code decoder 405. The base band part of a receiver need not contain a channel code decoder 405, but typically signals sent over a radio interface are channel coded.
The first embodiment of the invention relates to detecting symbols of different modulation schemes simultaneously. As an example, a Mixed Sphere Decoder with Ns transmit antennas and _V, = N, receive antennas is considered, capable of detecting 4-QAM and 16-QAM symbols transmitted simultaneously in different antennas.
It is appreciated that although this specific example relates to detecting symbols sent using known different modulation schemes or modulation alphabets, it is possible that the receiver is not aware of the modulation scheme used for a symbol. The receiver may try to detect a symbol using a number of possible modulation alphabets and then select the correct modulation alphabet using some predefined criteria.
The known Sphere decoding algorithms are valid only for signal detection with real constellations. To employ sphere decoding for signal detection with complex constellations, the incoming vector r and the channel matrix H should be decomposed in real and imaginary parts prior to their use in the Sphere Decoder. These decompositions are shown in below:
r dagger=[ Real®
Image®]= and H dagger= [Real(H)-Image(H)
Image(H) Real(H)

]



14
detection simply requires that for each, symbol i the' appropriate set of comparisons are used depending on the value of schi. This way the search volume of the Sphere Decoder is adjusted based on the (known or guessed) modulation of
With these conditions, the algorithm of the Mixed 4-QAM7] 6-QAM Sphere Decoder is created as shown in Figure 5, where either the vector L4QAM or the vector L16QAM should he used in the calculation of LBi and VBX. In Figure 5, the symbol enum() denotes the set of candidates of the i th symbol, given by the upper ) and lower limits of xt; the symbol length() gives the number of symbols
contained in this set keeping the value in N& and the symbol sort() sorts the 1set in
2 ascending order, according to| yij--Si| 2 for1≤j≤

Ni In step 501, variable ntx is set equal to the number of columns of the upper-diagonal matrix U (in other words, to 2Nt). In step 501, values for qn and qij are also set as discussed above in connection with Equation 5. In step 502, T^
dbest and S are initialised. In step 503, variable ix, which corresponds to the index . i, is initialized to be equal to the number of columns of the upper-diagonal matrix U. Steps 504 to 511 relate to finding a valid lattice point as a candidate for i. The lattice points within the search range between LBix and UBix are stored in vector Zjx of length Nix Nix is a number of found lattice points within the search range, Xix- is an index within the vector Zix and elements within zix are sorted according to how close they are to the center of the sphere. In step 504, the upper limit UB^ and the lower limit LBix are calculated in accordance with Equations 7 and 8, Vectors Zix and zix and also index Xix in step 504 relate to the reduced complexity sphere decoder algorithm, as discussed above. Index Xix is initialised to zero in step 504 and increased by one in step 505, for starting the search from the center of the sphere. Step 506 relates to keeping the search within the search sphere.. In step 507 it is checked, whether all symbols for a lattice point have been determined If not, steps 508 to 511 are carried out and steps 504 to 507 are repeated- Steps 508 and 509 relate to Equations 9 and 10. In step 510 a counter is updated; this counter relates to counting the number of iterations within the sphere decoder algorithm. In step 511, the variable ix is decreased so that in the next round steps 504 to 509 relate to the next received symbol 2Nt - 1.

15
When a valid lattice point has been found, the algorithm continues to step 512, where the squared distance between the found lattice point and the received point is determined. If the squared distance is smaller for the latest found lattice point than earlier found lattice points step 513). the algorithm proceeds to step 514. This step 514 the sphere radius is reduced, the upper and lower boundaries are updated, and the found lattice point is stored in vector x in accordance with the reduced complexity sphere decoder algorithm. The algorithm then continues via step 515 to find a next valid lattice point starting from step 505. If the reduced complexity algorithm has already proceeded to the surface of the search sphere, the search radius is increased in step 516. Thereafter it is checked hi step 517, whether a valid lattice point has been stored to vector i. If a valid lattice point has been stored to x , the algorithm outputs this lattice point. Otherwise, the algorithm restarts at step 502 with the bigger search sphere radius.
Steps 518 to 520 relate to finding no valid lattice symbol for a current received symbol corresponding to index i for the considered Xix then the method steps back (that is, ix=ix+l) and continues with the next candidate from z. In the case, if the current received symbol corresponds to i = 2Nt, the algorithm continues
with a bigger search radius (via steps 515, 516 and 517 to step 502). Otherwise, the algorithm goes back to index: -H (step 520) and continues from step 505 using a different candidate symbol corresponding to index i +1. It is appreciated that although the Mixed Sphere Decoder for signal detection is discussed above in connection with 4-QAM and 16-QAM modulation schemes, it is not restricted to these modulation schemes nor to this specific combination. Based on the presented algorithm it is clear to one skilled in the art how to modify the algorithm for decoding symbols relating to more than two different modulation schemes. It is appreciated that application, for example, to M-PSK (Phase Shift Keying) is possible to one skilled in the art.
It is also appreciated that although the symmetric example of JV, = Nr is discussed above, the Mixed Sphere Decoder for signal detection may be modified to cope with other cases. This is true also for any Sphere Decoder for signal detection, including Soft Output Sphere Decoder and Soft Additional Input Sphere Decoder discussed in this description. Cases where JV, Nf the Cholesky decomposition, which is used above to find U, fails since there is not a positive definitive matrix anymore. More than that, in this case the system is
















22
These matrices, as well as vectors in Equation 19. depend on the Gray mapping choise which can vary, for example. 25 disked by the user. An observation should be made here to say that any Gray mapping will work for the decoupling method just described.
This method to create bit likelihoods is a simple way to create soft values, but the results are, however, not optimal. In order to create optimum results a Maximum Likelihood optimum detection method should be used, in. which the soft values are created from the best vector of all possible. The drawback of a Maximum Likelihood optimum method are, as mentioned above, complexity. One example of Maximum Likelihood approach is discussed, by BJVT. Hochwald and S.T, Brink in “Achieving Near-Capacity on a Multiple-Antenna Channel”, IEEE Transactions on Communications. VoL51. Issue 3, March 2003, pp. 389-399. Also S. Baro, J. Hagenauer, and M. Witzke discuss soft values in “Iterative Detection of MIMO Transmission Using a List-Sequential (LISS) Detector”, IEEE International Conference on Communications ICC'03, Vol.4, 2003, pp. 2653-2657.
A Soft Output Sphere Decoder for signal detection in accordance with the second embodiment provides extra handling of hard results obtained by a hard Sphere Decoder. This way it is possible to keep the important characteristics of the Sphere Decoder, namely reduction in the sphere radius per iteration and
searching inside a sphere. As mentioned above in connection with Figure 3, it is alternatively possible to determine soft values in determining xi and then make soft decisions regarding the nest xi_i. As some examples, the hard Sphere Decoder may be a Soft Additional Input Decoder in accordance with, the third embodiment of the invention and/or a Mixed Sphere Decoder. The hard Sphere Decoder may alternatively be any known hard Sphere Decoder.
The proposed extra handling of the hard results obtained by a hard Sphere Decoder has the following steps.
1. Take the results of the execution of a hard Sphere Decoder stored in vector i.
2. Go through each of the X2Nt, X2Nt-I xi symbols searching for the closest
constellation symbols in which each one of its c\ bits in turn is either 1 or 0 ,
saving the Euclidean distances in each iteration.
3. Go also through the elements of vector p = [p2jv >P2N -i>—- P\\ which is the
received vector with the channel inverted. Make me same comparisons searching

23
for the closest constellation points to this vector in which the bit in use is either 1 or 0. and save the Euclidean distances.
4. Weight the Euclidean distances found from comparing vector X, for example, by a factor 22Nt -1 and the ones found from vector p, for example, by one.
5. Calculate the likelihoods from the additions of both weighted distances to return as the output.
A flowchart for this algorithm, for 16-QAM constellations, is presented in Figure 10 .The flowchart in Figure 10 has as input the symbols in vectors р and x from
the output of the Mixed Sphere Decoder shown in Figure 5, A point to notice is the use of matrices L1 and 'L0 defined in Equation 21, which is given, as an input parameter. It is appreciated that these matrices can vary depend on the (Gray) mapping used in the transmitter.
As mentioned above, for a 16-QAM constellation, there are two different vectors cd1 and cd2. Step 1001 in Figure 10 relates to selecting vector cd1 for calculation . In step 1002 the index is is initialized. Steps 1003, 1004 and 1005 relate to
selecting the constellation axis that does not relate to the bit in consideration. and also to weighting the channel inverted received point pr- and the estimation xi
mentioned above. In step 1006, the closest point of the selected constellation. axis. is determined. The distance to this closest point is denoted above with dp. Step.-. 1007,1008 and 1009 relate to determining the distances to the closest points from the pair of constellation axis, where the bit in consideration takes the logical value of 1 (step 1008) and 0 (step 1009), These distances are denoted above with d’0 . and d’1. In step 1030 the bit likelihoods are calculated using Equations 11 and 12. In step 1011a counter is updated; this counter relates to counting the number of; iterations within the sphere decoder algorithm. In step 1012 index ix is update c for determining bit likelihoods for a next symbol. In step 1013 it is checked whether all components of a received point have been processed using vector cdl. If all components of the received point have not yet been processed, the algorithm. continues from step 1003. If ail components of the received point nave aire been processed, vector z& is taken into use in steps 1014 and 1015 and _algorithm continues from step 1002- When all components of the received point have been processed using also vector cd2 this is noticed in step 1015 and the algorithm outputs vector x and the determined bit likelihoods.
For the 4-QAM case the matrices L1 and L0 are vectors, and instead of having tv-. vectors cd there is only one. Therefore, hi order to make this algorithm work v-i;

24
4-QAM constellations, the variable cd in tile algorithm of Figure 10 should always be one. L1 and L0 should be treated as vectors, and the vector LI6QAM should be replaced by L16QAM-
The third embodiment of the invention is directed to processing soft additional a priori information, typically in form of probabilities. This additional a priori information may improve symbol detection. To be able to receive and process soft a priori information, internal operation of the Sphere Decoder is modified. As discussed above, original Sphere Decoder makes hard decisions during iterations. A Sphere Decoder for signal detection in accordance with the second embodiment of the invention generates soft outputs based on the outcome of a Sphere Decoder making hard decisions. In the third embodiment, the aim is to create soft symbols during iterations of the Sphere Decoder. While creating a soft symbol, any a priori information may be processed. Typically the soft a priori information is used to weight and possibly correct the symbol.
For processing a priori informtion per bit it is possible to introduce a new vector pap containing probabilities or other a priori reliability information. Probabilities are used here as an example of a priori information. The probabilities may relate, for example, to the transmitted bits being equal to 1 .The vector pap contains, as an example and to be in line with the description above, 2Nt elements for 4-QAM constellations and 4 Nt elements for 16-QAM constellations. The elements are typically arranged according to the real and imaginary decomposition of the vector r representing the received signal, in a similar way than described by the vector cd in Equations 13 and 20. As a specific example, 4-QAM and 16-QAM systems with JV, = 2 are considered where the vectors pap are given for 4-QAM by
Pap,16QAM, =[Pap.4QAM=p(c12=1)]
[p(c12=1)]

[p(c12=1)]
[p(c12=1)]

and for 16-QAM by
Pap,16QAM,l =[Pap.4QAM=p(c12=1)] Pap,16QAM,2 =[Pap.4QAM=p(c12=1)]
[p(c12=1)]

[p(c12=1)]
[p(c12=1)]
[p(c12=1)]

[p(c12=1)]
[p(c12=1)]


25
where cij denotes the/* bit of the ith symbol P(cij=1) refers to the probability that bit cij has the logical value andcij refers to the MSB of symbol i. In the
case when there is not a prior informtion the vector(s) pap may be filled with zeros.
The method to create soft symbols during the iterations consists of weighting the candidate symbols by the ratio of the Euclidean distances between the received symbol r{ and the axis coordinates, in which the bit in consideration has the value of 1 or 0 given by vectors 1^ and holt is appreciated that although this specific example relates to weighting candidate symbols, in other words weighting the lattice, it is alternatively possible to weight the received symbol. It is also possible to weight both the lattice and the received symbol. It is furthermore appreciated that weighting is here used as an example of any modification of the lattice or received symbol based on a priori information.
In the following a soft additional input Sphere Detector for signal detection is constructed based on a Soft Output Sphere Decoder in accordance with the second embodiment of the invention. It is, however, appreciated, that it is possible alternatively to construct a Soft Additional Input Sphere Detector where the output symbols are hard.
As an example, consider the 4-QAM Soft Output Sphere Detector for signal detection. Each element of the decomposed received vector r represents one bit, as explained by Equation 13 for 4-QAM with Nt = 1. Starting from the last element of the received signal r and going backwards, a probability that bit c, ' is 1 is created. The probability is calculated with the distance between. Pр,cj2Nt=1and
the closest constellation symbol in which the considered bit is 0 or 1 as described in Figure 6 and Equation 12. The bit probability is saved in Pр,cj2Nt=1
The average of this probability and the a priori probability contained in pap for the same bit c ■ ( is calculated and stored as
P 2JV, , ±P_ 2A'; ,
Pc2Nt=1=pcf' =р,cj2Nt=1+ Pр,cj2Nt=1
2







29
where the bit in consideration takes tae logical value of 0. After step 1009b the algorithm in Figure 13B continues similarly as the algorithm in Figure 10.
In step 1306, 1308, 1311, 3314 and I317 it can be observed how Euclidean distance are weighted by a factor 9. This is to assure that the weighted symbols do not always tend to the value 1 of the axis. The number 9 is chosen to compensate for the square distance of the axis value 3.
The flowcharts in Figures 13A and 13B describe the.16-QAM case. For 4-QAM constellations the algorithm is simplified with vectors for L-x and Lo instead of matrices, and the use of only one bit probability to weight each candidate.
Although preferred embodiments of the apparatus and method embodying the present invention have been illustrated in the accompanying drawings and described in the foregoing detailed description, it will be understood that the invention is not limited to &e embodiments disclosed, but is capable of numerous rearrangements, modifications and substitutions without departing from the spirit of the invention as set forth and defined by the following claims.


Claims
1. A method for detecting a signal sad method comprising: receiving a first set of symbols representing a signal received in a receiver;
and
estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein said estimating step employs at least two modulation schemes,
2. A method as defined in claim 1, wherein said estimating the second set of symbols step comprises adjusting a search volume of the sphere decoding technique based on said at least two modulation schemes.
3. A method as defined in claim 1 or 2, wherein said estimating the second set of symbols step comprises determining a modulation scheme of a symbol of said second set of symbols.
4. A method as defined in claim 3, wherein said estimating the second set of symbols comprises defining a search region for said symbol of said second set of symbols using the modulation scheme of said symbol.
5. A method as defined in any preceding claim, wherein said at least two modulation schemes comprise at least two different quadrature amplitude modulation schemes.
6. A method as defined hi any one of claims 1-5, wherein said at least two modulation schemes, comprise at least two different phase shift keying modulation schemes.
7. A method as defined in any preceding claim, further comprising determining reliability information relating to bits forming a symbol for at least one symbol of said second set of symbols.
8. A method as defined in any preceding claim, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of the second set of symbols.

31
9. A method for detecting a signal method comprising: receiving a first set of symbols representing a signal received at a receiver; estimating a second set of symbols representing said signal transmitted at a
transmitter using a sphere decoding techniques; sad
5 determining reliability information relating to bits forming a symbol for at
least one symbol of said second set of symbols.
10. A method as defined in claim 9, wherein said second set of symbols is estimated before said reliability information is determined.
)
11. A method as defined in claim 9, wherein reliability information for at least a first symbol of said second set of symbols is determined before estimating a second symbol of the second set of symbols.
; 12. A method as defined in claim 11, said estimating the second set of
symbols step comprising using Ins reliability information relating to said first symbol of said second set of symbols in estimating said second symbol of said second set of symbols.
13. A method as defined in any one of claims 9 to 12, comprising determining a symbol constellation defining a relationship between a plurality of symbols and a plurality of bit sequences.
14. A method as defined in claim 13, comprising
determining a first sub-constellation of symbols relating to a given bit of a bit sequence having a value of 1, and
determining a second sub-constellation of symbols relating to said given bit of a bit sequence having a value of 0.
15. A method as defined in claim 14, comprising
determining a smallest first distance between a symbol of said first set of symbols and said first sub-constellation of symbols, and
determining a smallest second distance between said symbol of said first set of symbols and said second sub-constellation of symbols.
16. A method as defined in claim 15, wherein said determining the reliability information step comprises using at least said smallest first distance and said second smallest distance for determining said reliability information.

32
17. A method as defined in any one of claims 9 to 16, comprising determining probability information per sir.
5 18. A method as defined in claim 17, comprising determining
log-likelihood probabilities per bit.
19. A method as defined in any one of claims 9 to 18, wherein reliability information relating to said signal is taken into account in estimating the at least one symbol of the second set of symbols.
20. A method for detecting a signal, said method comprising: receiving a first set of symbols representing a signal received at a receiver;
and
i estimating a second set of symbols representing said signal transmitted at a
transmitter using a sphere decoding technique, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of the second set of symbols.
I 21. A method as defined in claim 20, comprising receiving said reliability
information relating to said signal.
22. A method as defined in claim 20 or 21, comprising
determining the reliability information relating to said signal for a first symbol of said second set of symbols based on at least a second symbol of said second set of symbols.
23. A method as defined in any one of claims 20 to 22, wherein said estimating said second set of symbols step comprises modifying candidate symbols based on at least said reliability information..
24. A method as defined in claim 23, wherein said modifying the candidate symbols step comprises modifying the candidate symbols that belong to a search region defined for estimating a symbol of said second set of symbols.
25. A method as defined in any one of claims 20 to 24, wherein said estimating said second set of symbols step comprises modifying a symbol of said first set of symbols based on at least said reliability information.

33
26. A method as defined in claim 25. wherein said modifying step comprises 'weighting.
27. A method as defined in any one of claims 20 to 26, wherein said
reliability information comprises a priori hit probabilities.
28. A method as defined in any one of claims 20 to 27, wherein said estimating said second set of symbols step comprises determining bit
probabilities for a symbol of said second set of symbols given a respective symbol of said first set of symbols.
29. A method as defined in any one of claims 20 to 28, wherein said estimating said second set of symbols step comprises determining averaged
probabilities of a priori bit probabilities comprised in said reliability information and bit probabilities given symbols of said first set of symbols.
30. A method as defined in any preceding claim, comprising representing the first set of symbols using a linear transformation of the second set of symbols.

31. A method as defined hi claim 30, wherein said linear transformation relates to channels of a multiple-input-multiple-output system, and each symbol of said second set of symbols represents a symbol transmitted by an antenna of the multiple-input -multiple-output system.
32. A method as defined hi claim 30s wherein said linear transformation relates to multiple paths in a time division system, and said second set of symbols represents sequential symbols of a user of the time division system.
33. A method as defined hi claim 30, wherein said linear transformation relates to different codes of a code division system, and each symbol of said second set of symbols relates to a different code.
34. An apparatus for detecting a signal, said apparatus configured to: receive a first set of symbols representing a signal received at a receiver
antenna; and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique,

34
wherein said apparatus is configured to employ at least two modulation schemes in estimating said second set of symbols.
35. An apparatus as defined in claim 54. configured to determine reliability information relating to bits forming a symbol for at least one symbol of said second set of symbols.
36. AD apparatus as defined in claim 34 or 35, configured to take into account reliability information relating to said signal in estimating at least one symbol of the second set.
37. An apparatus for detecting a signal, said apparatus configured to-, receive a first set of symbols representing a signal received at a receiver
antenna; and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique: and
determine reliability information relating TO bits forming a symbol for at least one symbol of said second set of symbols.
38. An apparatus as defined in claim 37, configured to take into account reliability information relating to said signal in estimating the at least one symbol of the second set of symbols.
39. An apparatus for detecting a signal, said apparatus configured to: receive a first set of symbols representing a signal received at a receiver
antenna; and
estimate a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of the second set of symbols.
40. An apparatus as defined in any one of claims 34 to 39, comprising a receiver block.
41. An apparatus as defined in any one of claims 34 to 39, comprising a communications device.

35
42. An apparatus as defined in any toe of claims 34- to 39. comprising a network; element for a communication system
43. A system for detecting a signal the system comprising-, receiving means for receiving a first set of symbols representing a signal
received in a receiver; and
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein the estimating means employs at least two modulation schemes.
44. A system for detecting a signal, the system comprising: receiving means for receiving a first set of symbols representing a signal
received at a receiver;
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique; and
determining means for dsi3iniz»nig reliability information relating to bits forming a symbol for at least one symbol of said second set of symbols.
45. A system for detecting a signal the system comprising:
receiving means for receiving a first set of symbols representing a signal received at a receiver; and
estimating means for estimating a second set of symbols representing said signal transmitted at a transmitter using a sphere decoding technique, wherein reliability information relating to said signal is taken into account in estimating at least one symbol of the second set of symbols.




Documents:

3254-CHENP-2006 CORRESPONDENCE OTHERS.pdf

3254-CHENP-2006 CORRESPONDENCE PO.pdf

3254-CHENP-2006 FORM-18.pdf

3254-CHENP-2006 FORM-2.pdf

3254-CHENP-2006 AMANDED CLAIMS 09-02-2010.pdf

3254-CHENP-2006 EXAMINATION REPORT REPLY RECEIVED 09-02-2010.pdf

3254-CHENP-2006 FORM-2 09-02-2010.pdf

3254-CHENP-2006 FORM-3 09-02-2010.pdf

3254-CHENP-2006 OTHER PATENT DOCUMENT 09-02-2010.pdf

3254-chenp-2006-abstract.pdf

3254-chenp-2006-claims.pdf

3254-chenp-2006-correspondnece-others.pdf

3254-chenp-2006-description(complete).pdf

3254-chenp-2006-drawings.pdf

3254-chenp-2006-form 1.pdf

3254-chenp-2006-form 26.pdf

3254-chenp-2006-form 3.pdf

3254-chenp-2006-form 5.pdf

3254-chenp-2006-pct.pdf


Patent Number 239215
Indian Patent Application Number 3254/CHENP/2006
PG Journal Number 12/2010
Publication Date 19-Mar-2010
Grant Date 10-Mar-2010
Date of Filing 07-Sep-2006
Name of Patentee NOKIA CORPORATION
Applicant Address Keilalahdentie 4, FI-02150 Espoo, Finland.
Inventors:
# Inventor's Name Inventor's Address
1 NEFEDOV, Nikolai SCHWANDELSTASSES 24, 8800 THALWIL SWITZRELAND
2 RAMIREZ MONTALVO, Manuel, Enrique SETEENKAARI 3D69,02100 ESPOO FINLAND
3 HOTTINEN, Ari Ristiniementie 4 as. 30, FI-02320 Espoo
PCT International Classification Number H04B1/707
PCT International Application Number PCT/FI2005/000024
PCT International Filing date 2005-01-17
PCT Conventions:
# PCT Application Number Date of Convention Priority Country
1 10/860,327 2004-06-04 U.S.A.
2 10/860,327 2004-02-09 U.S.A.
3 20040196 2004-02-09 U.S.A.