CN1701579A - Signal decoding methods and apparatus - Google Patents

Abstract

This invention is generally concerned with methods, apparatus and processor control code for decoding signals, in particular by means of sphere decoding. A sphere decoder configured to search for one or more strings of symbols less than a search bound from an input signal by establishing a value for each symbol in turn of a candidate the string by postulating values for each the symbol in turn of the candidate string and determining whether a postulated symbol value results in a distance metric dependent upon the search bound being satisfied, each the symbol of a candidate string for which values are postulated defining a level of the search. The sphere decoder includes a data structure configured to define, for each level of the search, a set of symbol values from which the postulated values are selected, the sets of symbol values being different at different levels of the search.

Description

Signal decoding method and equipment

Technical field

Relate generally to of the present invention is used for method, equipment and the processor control code to signal decoding, especially the mode by sphere decoding.

Background technology

Existence is to the transmission of the data rate that increases, and equivalently, to the lasting needs of more effective utilization of available bandwidth under the already present data rate.At present, for example WLAN (WLAN (wireless local area network)) standard of Hiperlan/2 (Europe) and IEEE802.11a (U.S.) provides data rate up to 54Mbit/s.A plurality of uses that transmit and receive antenna have the potentiality of very big these data rates of raising, but it is difficult that the signal that receives by MIMO (multiple-input and multiple-output) channel is decoded, because single receive antenna receives the signal from all transmitting antennas.Produce similar problem in the multi-user system, although the symbol of launching by different channels was incoherent at that time.Therefore need improved decoding technique to be used for mimo system.These technology have application in WLAN, have potential application in the 4th generation mobile telephone network, also have application in the communication system of a lot of other types.

A common problem in the signal processing field relates to signal from transmitter by Channel Transmission to receiver, and this problem will be determined to transmit from received signal.Received signal is subjected to the effect of channel impulse response or channel " memory ", and it can cause the interference between the symbol of continuous emission, and transmits and also may be encoded before transmission.The decoder at receiver place or detector have decoding or detect the original transmitted data and/or the problem of the initial data that has been encoded at the transmitter place.Optimum decoder is posterior probability (APP) decoder, it carries out search completely to all possible emission symbol (or emission symbol string), by channel response each is made amendment, to determine the set of the possible received signal of institute, select to have the one or more of nearest Euclidean distance with the actual reception signal in them then, as most probable emission and/or code signal.Yet the computation complexity of this method is along with the number (length of symbol string) of the bit number of the memory space of encoder, channel impulse response length, every symbol and the emission symbol considered is exponential increase.As mentioned above, these problems are blended in the mimo system.Therefore second best measure causes technical and coml interest.

Sphere decoding is a kind of technology that reduces complexity, and it can provide the performance near the APP decoder capabilities.Yet this technology suffers some problems, will further describe hereinafter, and these problems be embodiments of the invention at.

Sphere decoding has the application of certain limit in the field of signal processing.Present technique be will mention especially at this and the signal that receives by mimo channel and the application of multi-user system will be used to.Yet, the system that embodiments of the invention described herein also can be used to be correlated with, and the decoding that is used for other type.

The approximate of another kind reduction complexity to the APP scheme is that so-called max log is approximate.Broadly, determine that according to this method the bit likelihood value is included as two definite maximums, one of them correspondence has the bit of first logical value, be assumed to be+1, another correspondence has the bit of second logical value, is assumed to be-1.Expected, each correspondence that maximizes these to minimize and is used for the correlation distance tolerance that the candidate sends symbol string, preferably consider any priori that can be used as the soft input of this program, and expected, so present technique can use sphere decoder to implement.How we can be used to search for minimum this tolerance if will describing the sphere decoder that embodies each side of the present invention.

Fig. 1 shows typical MIMO data communication system 100.Data source 102 offers channel encoder 104 with data (comprising information bit or symbol).Channel encoder typically comprises convolution coder, for example recursive system convolution (RSC) encoder, or more powerful so-called turbo encoder (it comprises an interleaver).The bit of output is more than the bit of input, and typically, speed is 1/2nd or 1/3rd.After the channel encoder 104 is channel interleaver 106, and the Space Time Coding device 108 in this example.Space Time Coding device 108 is a plurality of code signs with the symbolic coding that enters, and each that is used for from a plurality of transmitting antennas 110 is launched simultaneously.

Space Time Coding can be described according to code machine, describes by encoder matrix, and it operates in data so that the room and time transmit diversity to be provided; Can follow a modulator after this, coded identification is used for emission to provide.Space-frequency coding (or coding of some other form) extraly (or as an alternative) be used.Therefore broadly, the symbol that enters is distributed in the grid with room and time and/or frequency coordinate, the diversity that is used to increase.When space-frequency coding was used, independent frequency channels can be modulated on OFDM (OFDM) carrier wave, and Cyclic Prefix is added into each emission symbol usually, to alleviate the influence of channel frequency dispersion.

Transmitting of having encoded is transmitted to reception antenna 114 by mimo channel 112, and it provides a plurality of inputs of (and/or frequently) decoder 116 when empty.This decoder has the task of the influence of eliminating encoder 108 and mimo channel 112, and can be implemented by sphere decoder.The output of decoder 116 comprises a plurality of signal flows, and each signal flow is represented a transmitting antenna, and each data flow is carried so-called soft or likelihood data, and these data are about the probability of emission symbol with particular value.These data are provided for channel deinterleaver 118, and the influence of its counter-rotating channel interleaver 106 then offers for example channel decoder 120 of Viterbi decoder, and it is decoded to convolution code.Typically, channel decoder 120 is SISO (soft inputting and soft output) decoders, its receiving symbol (or bit) likelihood data and similar likelihood data are provided, rather than for example make the data (though hard decision is just enough in some applications) of hard decision based on it, as output.The output of channel decoder 120 is provided for data sink 122, is used for other data processing in any required mode.

In some communication system, used so-called turbo decoding, wherein be provided for channel interleaver 124, (and/or frequently) and channel-decoding when it offers soft (likelihood) data decoder 116 successively and is used for iteration empty corresponding to channel interleaver 106 from the soft output of channel decoder 120.(will appreciate that in this configuration, channel decoder 120 provides complete emission symbol to decoder 116, promptly for example comprises detection bits.)

Will appreciate that in above-mentioned communication system, chnnel coding and Space Time Coding all provide time diversity, so this diversity is being followed return rate decline law aspect the extra snr gain that can obtain.Thereby when consider any specific when empty/during benefit that frequency decoder provides, preferably basis comprises that the situation of the system of chnnel coding considers them.

In the communication system 100 one of the most difficult task be by decoder 116 carry out empty the time (or frequently) coding decoding separate because it comprises the emission symbol of attempting the receiver place is interfered with each other.As mentioned before, the optimal solution device is posterior probability (APP) decoder, and it carries out thoroughly search to all possible emission symbol.Even yet for the antenna of number seldom, the modulation scheme of 16QAM (quadrature amplitude modulation) for example, and have the channel of frequency dispersion relatively in short-term, the combined number that consider also is huge, and the complexity of this method is exponential increase with data rate.

The selection commonly used of decoding that some are used for when empty (in this example piece) comprises the Linear Estimation device that for example pressure is made zero, and least mean-square error (MMSE) estimator.The pressure method of making zero can be applied to directly calculating the estimation to the emission symbol string, perhaps can determine an estimate symbol by " invalid and cancellation " method at every turn, and this method deducted the influence of the symbol that is before calculated before determining next symbol.For example by this way, having the maximum symbol of holding can at first be calculated.

Sphere decoding or demodulation provide the performance of remarkable improvement, it can be near the performance of APP decoder, broadly, by the search volume being expressed as grid (depending on matrix channel response and/or encoder), only being positioned at the received signal in generation then is the center, in the scope of the hypersphere of given radius with the possible symbol string of interior grid point, search is to the best estimate of emission symbol string.It is after being revised by channel that maximum likelihood is separated, and the most approaching corresponding received signal transmits.In fact it is crooked from the right angle grid that matrix channel response and/or Space Time Coding device tend to make input point (transmitting) space, and with method for expressing easily, region of search in the input point space becomes the ellipsoid of center initial estimation (pressure is made zero and separated), rather than spherical.

Because the search volume is reduced to the sub-fraction of having only grid from whole grid, search for required calculating number than the APP decoder required lack very manyly, still can obtain similar result.In order to use this program, must at first discern which grid point within required received signal distance.This relatively directly program is summarized hereinafter.Secondly, must decision use which kind of radius.This is vital to search speed, and should select to make some but not too much grid point may be found in this radius.Can adjust this radius according to noise level or according to channel.Even yet search radius is known, this search problem still is unmeasurable, in real system, this means sphere decoding calculate required in case of necessity between (and the available data rate that therefore obtains) can't be determined fully; Be used for describing to some extent, can carry out reference it at technology No. 0323208.9 UK Patent Application that submit to 3 days October in 2003 co-pending in the applicant of this problem.

The existing background technology that relates to sphere decoding can find in following document:

E.Agrell, T.Eriksson, " the Closest PointSearch in Lattices " of A.Vardy and K.Zeger, IEEE Trans.On Information Theory, the 48th volume, the 8th phase, in August, 2002; " the A universal latticecode decoder for fading channels " of E.Viterbo and J.Boutros, IEEE Trans.Inform.Theory, the 45th volume, the 5th phase, 1639-1642 page or leaf, in July, 1999; O.Damen, " the Lattice code decoder for space-time codes " of A.Chkeif and J.C.Belfiore, IEEEComms.Letter, the 4th volume, the 5th phase, 161-163 page or leaf, in May, 2000; " the Achieving near capacity on amultiple-antenna channel " of B.M.Hochwald and S.T.Brink, Httn: //mars.bell-labs.com/cm/ms/what/papers/listsphere/, in December, 2002; " On the expected complexity of sphere decoding ", ConferenceRecord of the Thirty-fifth Asimolar Conference on Signals, Systemsand Computers, calendar year 2001, the 2nd volume, the 1051-1055 page or leaf; " the Maximum-Likelihood Decoding and IntegerLeast-Squares:The Expected Complexity " of B.Hassibi and H.Vikalo, Multiantenna Channels:Capacity, Coding and Signal Processing, (J.Foschini and S.Verdu edit) Http:// www.its.caltech.edu/～hvikalo/dimacs.ps" the Anew Reduced-Complexity Sphere Decoder For Multiple AntennaSystem " of A.M.Chan, IEEE International Conference on Communications,, the 1st volume, in April, 2002-May in 2002; L.Brunel, " the Latticedecoding for joint detection in direct-sequence CDMA systems " of J.J.Boutros, IEEETransactions on Information Theory, the 49th volume, the 4th phase, in April, 2003,1030-1037 page or leaf; A.Wiesel, X.Mestre, " the Efficient Implementation of Sphere Demodulation " of A.Pages and J.R.Fonollosa, Proceedingsof IV IEEE Signal Processing Advances in Wireless Communications, the 535th page, Rome ,-18 days on the 15th June in 2003; The U.S. Patent application of submitting to by B.M.H0chwald and S.Ten Brink on July 26th, 2002 US2003/0076890 number, " Method and apparatus for detection and decoding of signals receivedfrom a linear propagation channel ", Lucent Technologies, Inc; " the Multiuser detection method and device in DS-CDMA mode " that the U.S. Patent application that L.Brunel submitted on August 22nd, 2002 is US2002/0114410 number, Mitsubishi; " the Sphere Decoding Algorithms for DigitalCommunications " of H.Vikalo, thesis for the doctorate, Standford University, 2003; " the Maximum-Likelihood Decoding and IntegerLeast-squares:The Expected Complexity " of B.Hassibi and H.Vikalo, in Multiantenna Channels:Capacity, Coding and Signal Processing, (editor J.Foschini and S.Verdu).

For example people's such as Agrell list of references has been described the nearest point searching method that is used for unlimited grid, and wherein input is any m dimension integer, i.e. x ∈ z ^m, looked back the basic conception and the searching method (but only having described the method that hard decision output is provided) of trellis decode.Yet this piece paper does not provide the solution to this detection or decoding problem, and wherein grid is limited, and the set (seeing below literary composition) of input set integer-valued symbol conformation of right and wrong or code word.

People such as Wiesel have described a kind of technology that is used for determining search radius, and this technology is set to K the intersymbol ultimate range tolerance that searching algorithm finds by radius

At this, K is the pre-number of symbols of determining of asking soft output required, for example 50.Initial search radius is set to infinite, and is found up to K symbol.When tabulation was full, promptly K symbol was found, the distance metric of maximum during then search radius is set to tabulate.Heapsort is proposed as a kind of effective method and is used for candidate list is sorted, and makes candidate list have the possible beeline tolerance of K kind.This shows as a kind of creation facilities program (CFP) effectively.

Other decoder or detector (are used with the free burial ground for the destitute basically at this this two speech, because all meaning, they attempt solving similar problem, promptly detect the original transmitted data) comprise for example decoder based on lattice shape of Viterbi decoder (it has the computation complexity of index), and the detector of the reduction complexity that sub-optimal performance is provided of Viterbi BLAST (layering of Bell laboratory empty time) decoder and piece DFF for example.

In this, it is helpful providing the summary review of the operation of sphere decoding program.For the symbol string of N emission symbol, search for a N dimension grid, start from the layer (corresponding to first symbol of this string) of N dimension.For this one deck, from employed conformation, select a symbol, and the grid point that produced of check is apart from the distance of received signal.If this grid point in this distance, value of this procedure Selection next symbol of being used for going here and there then, and the grid point that check is produced in the N-1 dimension is apart from the distance of received signal.This program continues to check successively each continuous symbol, and if all in inside, border, it will finally converge in one dimension on the grid point.If a symbol is outside selected radius, then this program is moved one deck (dimension) and is selected next possible symbol to be used for check in this layer (dimension) to travelling backwards.By this way, this program is set up one tree, the wherein minimum complete symbol string of node correspondence, and the corresponding corresponding n of the interstitial content of the n level that wherein should set ties up the number of the inner grid point of sphere.

When complete candidate symbol string is found, produce foundly apart from the distance of received signal from the grid point of this symbol string, and initial radium is reduced to this distance, makes to set up as this tree, only discerns the string of more separating near maximum likelihood.When this tree had been done, decoder can be used to by selecting to provide hard output near the grid point of received signal, and promptly maximum likelihood is separated.Can be for alternatively, can utilize selection that soft output is provided near the grid point of received signal, for example utilize each grid point apart from the distance of received signal as the likelihood value that is associated.Heapsort be proposed be used for selecting its grid point have subclass apart from the symbol string of the nearest distance metric of received signal (people such as Wiesel, as above); Another kind of method of being advised is provided with a fixing search radius in whole search, and select to provide symbol string subclass less than the distance of this fixing search radius (Hochwald and Brink, as above).

As illustrating hereinafter, a problem of conventional sphere decoding technology is, they only prove effective for real integer symbol conformation and square complex symbol conformation (by to reality and imaginary component decoupling zero), because this search utility is based on the searching grid point, wherein it is input as real integer.In other words broadly, because current sphere decoding technology is handled complex signal conformation (being the conformation that its value has reality and imaginary component) by isolating reality and imaginary component, when this separation can not effectively be carried out, these technology failures.For example when emission when the signal of a transmitting antenna depends on emission from the signal of another transmitting antenna (symbol is crossed over a plurality of antennas and is spatially encoded), perhaps when the signal a time emission depends on the signal of time emission more early, or above-mentioned situation can take place when being in the both.This mainly pay close attention to the former (space encoding), but embodiments of the invention also can be used to the latter's situation.Also have (we at) the third situation, wherein when emission when the symbol of an antenna can not rely on emission from the symbol of other transmitting antenna, emission from the signal of an antenna or transmitter be multidimensional or complex value.In this case, the sphere decoding program can be corresponding to an emission symbol more than a search level.

As seeing, described herein and technology that develop at these problems also has other to be used, for example in the communication system (bit of the different numbers of wherein every symbol is loaded on the mimo system of different transmit antennas) that loads with bit in multi-user system.

People such as Damen (as above) have described the sphere decoder that is applicable to compound shape conformation, but it can not be applied to the non-square conformation of 8PSK (phase shift keying) for example or star QAM (quadrature amplitude modulation).The list of references of Hochwald and Brink (as above) provides the multiple sphere decoder that for example is used in the symbol conformation of the formation fourth contact circle of PSK.It has used the search disk, and finds the scope of constellation points by the overlapping that solves search disk and conformation circle.Yet this multiple sphere decoder needs the sphere decoding in the rectangular coordinate, wherein needs trigonometric function in this program, and calculation cost is high.People such as Wiesel (as above) as previously mentioned, provide (based on look-up table) rearrangement or sort algorithm, make must be searched the symbol tabulation be arranged as apart from forcing to make zero and separate the order that distance increases.Yet this symbol tabulation that will be searched and rearrangement or sort algorithm are all based on integer value symbol conformation.

Summary of the invention

Broadly, the target of embodiments of the invention is by carrying out the mapping of symbol conformation or code word, and on the finite aggregate of symbol conformation or code word value rather than at limited integer set s ∈ z ^mLast execution search is at these shortcomings of prior art.

Therefore according to a first aspect of the invention, a kind of sphere decoder is provided, dispose it to search for apart from one or more symbol strings of input signal less than the search boundary, this search is to set up a value by each symbol that is followed successively by candidate's string, setting up a value for each symbol of candidate's string is by being followed successively by value of each symbol supposition of candidate's string, and determine whether the value of symbol of being supposed obtains a distance metric that depends on the search boundary and be satisfied, search level of each symbol definition of the value of being assumed to be of candidate's string, this sphere decoder comprises the data structure that is configured to a value of symbol set of each search level definition, the value of symbol of being supposed is selected from this value of symbol set, and it is different that these values of symbol are integrated into different search level.

In an embodiment, symbol string can be represented the assemble of symbol (promptly launching symbolic vector) of emission spontaneous emission antenna set in the mimo system, and/or assemble of symbol or the vector launched by different user in the multi-user system, and/or by the symbol of a period of time by one or more transmission antennas transmit.By selecting for this symbol string or from different assemble of symbol, selecting during the supposition candidate symbol, this sphere decoder can adapt to the different modulation schemes that is used by different transmit antennas, this different transmit antennas can be the antenna of different user in the multi-user system, or different transmitting antennas, or use and use the bit of different modulation schemes to load mimo system different transmit antennas.In one or more symbol strings, the target of this sphere encoder is identification (one is used for hard output, a plurality of be used for soft output) each transmitting antenna corresponding to one of string (or may be a plurality of) character position.

Under the situation of non-square multiple conformation that may symbol, in the string to its foundation, may rely on the symbol that has been established at a searched assemble of symbol in position at some values of symbol.The complex representation of supposing communication system is made it be represented as two times the real-valued expression that dimension is a primal system by decoupling zero, and there is dependence in emission between two real-valued symbols of a complex symbol of expression of an antenna.For example these symbols may be to encode by a plurality of transmitting antennas in the mimo system, and therefore emission has applied dependence from the value of symbol and the emission of an antenna between the value of symbol of another antenna in the mimo system antenna.Above-mentioned sphere decoder can (previously herein refer in the structure of candidate symbol string some more points of morning by depending on previous value for one or more other symbols in this string, and the symbol that unnecessary finger was launched in the time more early), select a glossary of symbols therefrom to select, and consider this dependence with specific location in symbol string.For example for the multidimensional symbol conformation, symbol can be by more than a real-valued expression, and therefore this search may depend on the string of the symbol that had before found.

Though embodiments of the invention will be described with reference to the coding of crossing over a plurality of transmitting antennas in the mimo system, will recognize that can use similar techniques, wherein symbol is encoded by the time and/or by frequency extraly or as an alternative.

By hereinafter to the more detailed discussion of sphere coding embodiment, will be understood that, in an embodiment, from one of value of symbol set, select a candidate transmitting symbol, so that (in the received signal space) grid point in the radius of received signal to be provided.Also will expect, not need (and generally not having) unique value of symbol set, because might reuse some assemble of symbol at the place not at the same level of search for each level of searching for level.Its example provides later.Yet symbol may depend on the rank of search level and the symbol that had before found from the value of symbol set of wherein selecting.This is because depend on conformation, the symbol that had before found may not influence the initial symbol that residue symbols one all in the string for example is used for a string and can select from full set that may symbol, after this, the symbol of some may be influenced by the selection of initial symbol, and may make another and independently select, from all possible symbol, select.This configuration can advantageously be implemented by the data structure that comprises a plurality of forms, the set of a possibility of each form definition value of symbol.Like this, the quantity of table is advantageously to being applied to the number of the required distinct symbols value set of different search level or level, perhaps considers the influence to required number of sets of the symbol that before found.In each table, value of symbol preferably is arranged according to the distance of the initial estimation of distance symbol string, and this initial estimation for example is linear or forces to make zero estimation, and for example symbol is by from closely to arrangement far away.Depend on the number of symbols in the set and depend on the scope of the value that they cover, a form can comprise a plurality of ordering symbols tabulations, and the initial estimation of the symbol in one of ordering tabulation response symbol string is selected.By this way, the symbol near initial estimation provides starting point for the sphere decoder search, and if this distance metric be not satisfied, can be detected apart from the symbol that the distance of initial estimation increases.

Above-mentioned technology also can be used to (or extending) and implement a kind of based on the bit formula decoded form approximate to the so-called max log of maximum a posteriori probability (APP) detector.This preferably understands with reference to the formula that provides hereinafter, but broadly, the inventor expects, sphere decoder can be modified with by the minimum distance metric of the specific bit in the restriction symbol string for the symbol of its first logic level and second binary logic level, determines that this specific bit has the likelihood value of one of binary value (1 or 0).This max log is approximate then to provide a kind of mode that merges these two kinds of distance metrics, perhaps utilizes other prior information, so that the estimation to the log-likelihood value of this bit to be provided.Therefore in order to further specify, consider for example to be somebody's turn to do first bit of string, sphere decoder only is restricted to, and this first bit of search is set to one symbol string or vector, to determine minimum distance metric, and then (or simultaneously), sphere decoder is searched in being limited to the scope of symbol string of another value that this first bit is set to its binary logical values, to find second minimum distance metric, and these two distance metrics can then be used for this bit and determine likelihood value, the log-likelihood value of saying so more accurately, promptly compare with another value of its binary value, this bit will have one of them possibility of its binary value.This as can be seen search utility will comprise the restriction sphere decoder to its some symbol of searching for (will expect, two or for a lot of bits, will carry out a plurality of search serially or concurrently or with both certain combinations).More specifically, in the example that has just provided, in these two search, first symbol of string only is confined to from first bit equals the symbol of logical one (or 0) and selects, although the symbol of back can not be subjected to this constraint and selected in this string.Therefore will recognize, and more than be used to define therefrom and to select the technology of the distinct symbols value set of the value of symbol supposed for different sphere decoder search level and be easy to be modified to above-mentioned bit formula sphere decoding process.Therefore in said procedure, one of value of symbol set only comprises the symbol corresponding to one of data bit with selected binary value.Use other details of this embodiment of this max log decoding technique of sphere decoder to submit to, be described in No. the 0323211.3rd, the UK Patent Application co-pending in the time of the applicant on October 3rd, 2003, at this by with reference to incorporating its content into.

Broadly, therefore this embodiment of the present invention as can be seen provides the sphere decoding technology, and their enforcement is direct relatively, and can deal with the multiple conformation of any kind, and for example can dealing with, or the symbol of uniting emission of different modulation schemes from different user or transmitting antenna.Embodiments of the invention also provide the method for the robust of carrying out sphere decoding, the original conformation of search symbol subclass wherein, for example in bit formula sphere decoding, wherein only corresponding to or the symbol conformation of a selected bits of one or zero searched.

Therefore in yet another aspect, the invention provides a kind of to comprising from a plurality of signal transmitters, the method that the input signal of the signal that receives by a plurality of communication channels is decoded, these a plurality of signal transmitters are launched a plurality of symbols, this coding/decoding method is searched for the symbol string of the estimation of one or more expression emission symbols, this decoding comprises each symbol that is followed successively by candidate's string and sets up a value, setting up a value for each symbol of candidate's string is by being followed successively by value of each symbol supposition of candidate's string, and determine whether the value of symbol of being supposed obtains a distance metric that depends on the search boundary and be satisfied, this region of search that depends on input signal of search boundary definition, search level of each symbol definition of the value of being assumed to be of candidate's string, this decoding also is included as value of symbol set of each search level definition, the value of symbol of being supposed is selected from this value of symbol set, and it is different that these values of symbol are integrated into different search level.

The present invention also provides the decoder that is configured to implement this method, and the receiver that comprises this decoder.

In another related fields, the invention provides a kind of decoder that is used for decoding to received signal, this received signal comprises a symbol string by the mimo channel emission, this decoder comprises: sphere decoder, with search candidate transmitting symbol string in the radius of received signal, and provide decoded data output; And the sphere decoding data structure, dispose it and think a plurality of different values of symbol set of this search definition, and wherein be used for this string each symbol candidate symbol according to they in the position of this string, can selection from different value of symbol set.

The technical staff will expect that said method and decoder can be implemented and/or embodiment with processor control code.Therefore in one aspect of the method, for example on the carrier media of for example disk, CD-or DVD-ROM, for example the memory that is programmed of read-only memory (firmware) perhaps provides this sign indicating number on the data medium of for example light or electrical signal carrier in the present invention.Embodiments of the invention can be gone up enforcement at DSP (digital signal processor), ASIC (application-specific integrated circuit (ASIC)) or FPGA (field programmable gate array).Therefore this sign indicating number can comprise the conventional programming sign indicating number, or microcode, or for example is used to set up or control the sign indicating number of ASIC or FPGA.In certain embodiments, this sign indicating number can comprise the sign indicating number of the hardware description language that is used for Verilog (registered trade mark) for example or VHDL (Very High Speed Integrated Circuit (VHSIC) hardware description language).To recognize that as the technical staff processor control code that is used for embodiments of the invention can be distributed between a plurality of coupling elements of communication each other.

These and others of the present invention are further described with way of example referring now to accompanying drawing.

The accompanying drawing summary

Fig. 1 and Fig. 2 show the communication system of the MIMO Space Time Coding that uses sphere decoder respectively, and the diagram of spherical encoder tree search;

Fig. 3 shows the block diagram of first example of max log decoder;

Fig. 4 and Fig. 5 show the block diagram of second and the 3rd example of max log decoder;

Fig. 6 and Fig. 7 show the conformation of 8PSK respectively, and are used for the conformation for Fig. 6, sphere decoder grid point/layer of searching at difference search level place;

Fig. 8 shows the flow chart that is fit to according to one embodiment of present invention sphere decoder that the general symbol conformation is decoded respectively to Figure 10, the receiver of having incorporated general symbol conformation sphere decoder into, and an example of the transmitter of the receiver of suitable Fig. 9.

Figure 11 shows the general block diagram of the transmitter with series encoder;

Figure 12 shows the block diagram of the receiver with series connection decoder that the transmitter that is used for Fig. 6 uses;

Figure 13 shows the block diagram of the receiver with series connection decoder and iterative decoding that the receiver that is used for Fig. 6 uses;

Figure 14 shows the block diagram that uses the receiver of iterative feedback between two equivalent decoders; And

Figure 15 shows and is used for according to the bit error rate of the embodiment of the sphere decoder of the present invention schematic diagram to signal to noise ratio (Eb/No).

The preferred embodiments of the present invention

Broadly, a preferred embodiment of sphere decoder can be described to a kind of decoder, this decoder is used for being encoded as symbol string and decoding as transmitting of receiving of received signal by channel, each emission symbol has one of a plurality of values, this decoder comprises: the device that is used to search for one or more candidate symbol strings, the candidate symbol string comprises a string candidate symbol, this search is by the candidate symbol of the described string of search in a zone of the multidimensional grid of being determined by described channel response, each dimension of described grid is associated with each described symbol of described string, and described zone is by the distance definition apart from described received signal; And be used for by selecting one or more described candidate symbol strings, be the decode device of described symbol string of described received signal; It is that described emission symbol is selected candidate value that the described device that wherein is used to search for candidate symbol is configured to, and check by the part of the described grid of selected described candidate's definition whether defining within the distance apart from described received signal.The multidimensional grid can be extraly or as an alternative by the transmitter place use empty the time or other coding determine.

This program is attempted the candidate value of each character check to this string, but depends on channel and received signal, and having at least one complete tree that is used for the complete candidate symbol set of a string may not be fabricated at the end-node place of tree.This search stops after being preferably in a limited number of candidate symbol check.When this search can't be located a candidate symbol string, linearity, preferably forcing makes zero estimates may be provided in the output of this decode procedure.Any Linear Estimation for example have the Linear Estimation of continuous interference eliminated, and MMSE separates and can be used.Usually, each symbol is by one or more bit definitions, so Bit String of this symbol string definition.So may comprising (or also comprising), this decoding provides probable value for each bit of this Bit String.When the candidate symbol string was not positioned, the symbol of separating of forcing to make zero can be used to calculate this soft bit values.

This decoding can provide hard output by selecting minimum range candidate symbol string to be used for output, so-called soft output perhaps can be provided, it in fact comprises a plurality of decoded symbol strings, each symbol string has a probability that is associated, for example depend on generation from the grid point of symbol string the distance apart from received signal.This search search candidate symbol string, it forms grid point in a zone of the determined multidimensional grid of described channel response.Soft output can in fact comprise all candidate symbol strings of being found by this search (probability), to avoid the needs to ordering.Each symbol is associated with one or more emission bits usually, and this decoding can also be included as these bits each probable value is provided, for example be determined based on all candidate symbol strings that found by this search, wherein at least one candidate symbol string is found.The probable value of a bit can be by having (candidate's string of having discerned) assemble of symbol of first and second logical value respectively based on this bit wherein, get this bit have first and second logic level likelihood value ratio and determine.When for a bit, do not have symbol to have one of these values (or other) in the candidate string, and this ratio can not be calculated, can be provided for the acquiescence probable value of this bit, for example, perhaps comprise the maximum of acquiescence based on the minimum distance metric that is used for another logical value.The search candidate symbol is preferably carried out according to the order apart from increasing of the estimation of making zero apart from the described pressure that transmits (or other linear or be easy to calculate estimation), and this estimation is for example determined by described received signal and described channel response.

Symbol string can comprise a plurality of users of emission in multi-user comm symbol, or in the MIMO communication system by a plurality of transmission antennas transmit and the symbol string that receives by second a plurality of reception antenna (this channel all comprises the form of matrix channel under two kinds of situations).In the MIMO communication system, this symbol string may comprise the symbol of space-time block code (STBC) or the symbol of space-time trellis codes (STTC), or the symbol of space-frequency coding, or when empty/and symbol that frequency encoded.The signal spans of the process space-frequency coding for example a plurality of frequency channels in multi-carrier OFDM (OFDM) system is encoded, in this case, configuration deserializer and fast fourier transformer before decoder, and contrary inverse fourier transformer of configuration afterwards and parallel-to-serial converter.

Will appreciate that spherical decoding method can be used to for example have in the turbo decoder of interlaced code and channel-decoding.

We also use description to the bit formula decoder of decoding to received signal, this received signal provides by comprising the transmitting of symbol string that sends by channel, each described symbol comprises one or more bits, described decoder comprises: a plurality of sphere decoder, each is configured to the distance metric relevant with bit of determining minimum into symbol string, a bit has the value that is defined in this symbol string, described distance metric depends on the distance of described received signal apart from estimated received signal, and this estimated received signal is determined by stating string and described channel response; And the bit likelihood estimator, it is coupled to each sphere decoder, and is configured to and depends on minimum distance metric, for each bit of described string is determined the bit likelihood value.

In a preferred configuration, one of sphere decoder is configured to determines the maximum likelihood distance metric, especially be definite (generally) distance metric of each bit of complete maximum likelihood sign string.Can provide another maximum likelihood detector for each bit of this symbol string, be used to corresponding bits to determine minimum distance metric, each of these maximum likelihood decoders is that the value that is different from this bit of the value of this bit in the maximum likelihood sign string is determined distance metric.Determine that this maximum likelihood sign string preferably considers the priori data relevant with this symbol string, especially therefore the prior probability value of each bit in the string is beneficial to and obtains soft output.Can for example initial search radius be set according to using the required log-likelihood ratio that is used to limit, perhaps one of sphere decoder can be used for another sphere decoder initial spherical radius is set, and perhaps is that a specific bit determines that the sphere decoder of (minimum) distance metric can make its initial radium be set to be inverted or be put upside down and given metric by its corresponding specific bit of maximum likelihood sign string.

The further detailed content that sphere decoder is prolonged above-mentioned thinking can find in the UK Patent Application co-pending No. 0323208.9 and No. 0323211.3 when submitting on October 3rd, 2003 this inventor, is incorporated in this by reference.

[sphere decoding-mathematical background]

Consider to have n now _TIndividual emission and n _RIndividual received signal (or equivalently, has n respectively _TIndividual and n _RIndividual component transmit and receive signal) empty the time transmission plan.Each is 1 * n constantly _RIndividual received signal vector provides as follows:

$\tilde{r}=\tilde{s}\tilde{H}+\stackrel{~}{\mathrm{<figure-callout\; id="1"\; label="v\; ~\; Formula"\; filenames="A20048000087000411.png,A20048000087000471.png"\; state="\{\{state\}\}">v</figure-callout>}}$ Formula 1

Wherein $\tilde{s}=\left[\begin{array}{ccc}{\tilde{s}}^1& \&CenterDot;\&CenterDot;\&CenterDot;& {\tilde{s}}^{n_T}\end{array}\right]$ The expression emission signal vector, its clauses and subclauses are from having M=2 ^qSelect among the multiple conformation C of individual possibility signaling point, wherein q is the bit number of each conformation symbol.AWGN (additive white Gaussian noise) vector Be that each real component variance is 1 * n of the multiple Gauss's clauses and subclauses of independent zero-mean of o2 _RVector.Mark Expression (one constantly place) N _T* n _RMany inputs/many output (MIMO) channel matrixes, suppose that it is known at the receiver place or is estimated, has the capable m row of n component h _{N, m}, n=1 ..., n _T, m=1 ..., n _RRepresent that n transmits and m received signal between flat decline the in arrowband.In symbol duration, channel fading can be assumed to be constant.

In receiver, mimo channel is estimated

Can utilize training sequence to obtain in a usual manner.For example can each time all reception antennas be monitored, to describe channel from each transmitting antenna training sequence of (for the problem of avoiding interference) emission successively from this transmitting antenna to reception antenna.The significant expense of this not pattern of wants, and data rate is very high between training, and also for example for changing indoor channel slowly, training can be carried out once in only for example per 0.1 second.Can be for alternatively, can be simultaneously from the sequence of all transmission antennas transmit quadratures, although owing to complexity that interference problem increases training can take place for this.

Formula 1 is blanket, and for example the launch scenario of all linear space-time block codings can be written as this form.For example, BLAST (" the Layered space-timearchitecture for wireless communication in a fading environmentwhen using multi-element antennas " of G.J.Focshini, Bell Labs.Tech.J., the 1st volume, the 2nd phase, the 41-59 page or leaf, 1996) used transmitting antenna to have the signal of hierarchy with transmission, and therefore n _TThe number of expression transmitting antenna, n _RThe number of expression reception antenna, and It is real mimo channel matrix.Another example comprises orthogonal design (" the A simple transmitter diversity scheme for wirelesscommunications " of S.M.Alamouti, IEEE J.Sel.Area Comm., 1451-1458 page or leaf, in October, 1998; And V.Tarokh, " the Space-time block codes from orthogonal designs " of H.Jafarkhanni and A.R.Calderbank, IEEE Trans.Info.Theory., the 45th volume, the 1456-1467 page or leaf, in July, 1999) and linear frequency dispersion sign indicating number (B.Hassibi and B.Hochwald, " High-rate codes that are linear in space andtime ", IEEE Trans.Info.Theory., the 48th volume, the 1804-1824 page or leaf, in July, 2002), wherein Be by the efficient channel that uses one or more real channels to derive.

Formula 1 can also be used to represent cdma system, and wherein multi-user detector is estimated the signal of emission from different user And

Expression was propagated and channel effect uniting of all users.

The emission symbol

N subdivision amount utilize following sign map function to obtain

${\tilde{s}}^n=\mathrm{map}\left(x^n\right),n=1,\&CenterDot;\&CenterDot;\&CenterDot;,{\mathrm{<figure-callout\; id="2"\; label="n\; T\; Formula"\; filenames="A20048000087000401.png,A20048000087000411.png"\; state="\{\{state\}\}">n</figure-callout>}}_T$ Formula 2

Wherein

$x^n=\left[\begin{array}{ccc}{x}_1^n& \&CenterDot;\&CenterDot;\&CenterDot;& x_q^n\end{array}\right]$ Formula 3

Be vector, and q is the bit number of each conformation symbol with q emission data bit.Yet (more generally, The symbol string that expression is encoded by space and/or time and/or frequency, and n travels through the length of this string).Therefore length is (qn _T) the emission bit vectors can be represented as

$x=\left[\begin{array}{ccc}{x}^1& \&CenterDot;\&CenterDot;\&CenterDot;& x^{{\mathrm{<figure-callout\; id="4"\; label="n\; T\; Formula"\; filenames="A20048000087000472.png"\; state="\{\{state\}\}">n</figure-callout>}}_T}& \\ \end{array},\right]$ Formula 4

And launching vectorial conformation can be written as

$\tilde{s}=\mathrm{map}\left(x\right)$ Formula 5

The received signal of transmission when being used for formula 1 empty For maximum a posteriori probability (APP) bit-detection of condition can be expressed as following likelihood ratio (LLR):

$L_P\left(x_j^n\right|\tilde{r})=\ln \frac{P(x_j^n=+1|\tilde{r})}{P(x_j^n=-1|\tilde{r})}$

$=L_A\left(x_j^n\right)$

Formula 6

And L _E() item can be approximately

Formula 7

Wherein x is the sequence that possible launch bit, x _{[n, j]}Expression is by ignoring the element x of x _j ⁿAnd the subvector of the x that obtains, and L _{A, [n, j]}Represent all L _AThe vector of value also omits corresponding bit x _j ⁿElement; And wherein in the summation of formula 6 each,  is provided by formula 5, and x is as the vector below the summation symbol, and wherein ‖ ‖ represents euclideam norm.Set X _{N, j} ^{+ 1}And X _{N, j} ^-1Be respectively 2 ^(qnT-1)Individual have $x_j^n=+1$ With $x_j^n=-1$ The set of bit vectors x, promptly

$X_{n,j}^{+1}=\left\{x\right|x_j^n=+1\}$

And

$X_{n,j}^{-1}=\left\{x\right|x_j^n=-1\}.$

In other words, for example the summation in the molecule of formula 6 travels through all and has bit $x_j^n=+1$ Symbol.

Noise variance σ ²Can obtain with any mode easily, depend on overal system design.For example, this noise variance can obtain at the training period that channel impulse response is estimated.At training period, the emission symbol sebolic addressing is known.In conjunction with estimated channel impulse response, obtain " nothing is made an uproar " received signal.This noise variance can pass through at " training period ", and known " nothing is made an uproar " received signal sequence asks the noise statistics amount of received signal sequence to estimate.

Symbol  is to launching the mapping of bit vectors x.Function L _p(), L _A() and L _E() represents posteriority, priori and outside likelihood respectively.Priori likelihood L _A() can be derived from for example priori input from (for example be used for iteration turbo decoding) channel encoder, perhaps can be set up or be initialised and for example be zero (log-likelihood ratio L () be 0 mean+1 and the-1st, equiprobable).Formula 6 is that MAP separates, and formula 7 provides the max log that MAP is separated approximate (being called max log MAP sometimes separates).We will describe the approximate technology of separating that formula 6 and formula 7 can be provided.

According to formula 6, APP detects needs none to omit ground to corresponding to set X ^{+ 1}And X ^-12 of middle element number ^QnTIndividual distance metric Evaluation.The computation complexity that APP detects is with the number q of the every bit of symbol and the number n of spatial reuse emission symbol _TBe exponential increase.A kind of method that is used for approximate expression 6 is only to comprise set X ^{+ 1}And X ^-1In candidate that following formula is set up

${\left|\right|\tilde{r}-\hat{s}\tilde{H}\left|\right|}^2\&le;{\mathrm{\&rho;}}^2$ Formula 8a

$\left|\right|r-\hat{s}H\left|\right|-{\mathrm{\&sigma;}}^2{x}^T\&CenterDot;$ $L_A\&le;{\mathrm{\&rho;}}^2$ Formula 8b

Its Chinese style 8a does not have priori, and formula 8b has priori, and wherein ρ is the border radius of sphere decoding.

Being somebody's turn to do approximate hypothesis provides the candidate by the distance metric beyond the border of formula 8a and formula 8b definition not provide effective contribution to APP detection (seeing formula 6).This sphere decoding algorithm provides and has found fast or satisfy formula 8a or satisfy the program of the candidate list of formula 8b.

Original sphere decoder is also referred to as grid decoder, and (Viterbo and Boutros as above) provide maximal possibility estimation, and it is the hard output that is used for the emission symbol of real conformation and channel, and communication system is expressed as grid.Yet we also are described in the soft input/soft output sphere decoder that is fit to multiaerial system in other application at this.

[sphere decoding that is used for square conformation]

Below describe based on the description in No. the 0323208.9th, the applicant's the UK Patent Application early.

In order to obtain to be used to implement the grid representation of the multiaerial system of sphere decoding program, it is that the real matrix of primal system twice is represented that the complex matrix representation of formula 1 can be transformed to dimension, as follows:

R=sH+v formula 9

Wherein

Formula 10

Formula 11

Formula 12

Formula 13

The wherein real component and the imaginary component of symbol R and I sensing amount respectively/matrix.

Yet this decomposition only proves effective to (quadrature amplitude modulation) square conformation of for example QAM, and is wherein identical with the set of the real-valued symbol that is used to search for of corresponding imaginary component of answering conformation effectively corresponding to the set of possible the real-valued symbol that is used to search for of the real component of multiple conformation.This be embodiments of the invention at a limitation.

Use used term in the netting theory, the real-valued expression H of channel is the generator matrix of grid, and channel input (transmitting) s is the input point of grid, and grid point of noiseless channel output item sH definition.

N dimension grid can be broken down into each layer of (n-1) dimension.The searching algorithm that is used for n dimension grid can recursively be described as a limited number of n-1 dimension searching algorithm.Viterbo and Boutros (as above) have described this searching algorithm according to the three kinds of different conditions or the situation of this search:

Table 1

Situation A	N dimension layer is in this search border: this layer is broken down into each layer of (n-1) dimension
		Situation B	This search successfully reaches the layer of zero dimension, and finds a grid point in this region of search
Situation C	N dimension layer is not in the search border: move up a step in the level of this search at each layer.

Will be below in greater detail as us, we consider a kind of modification of this base program at this, wherein at n search level, from will be by n symbol s of the symbol string of joint survey ⁿSearch for by sphere decoder.

If the lower triangular matrix U that QR decomposes or Cholesky decomposition (being called as the square root of getting matrix sometimes) is derived from channel matrix ^TThe generator matrix that is used as grid, this search utility can be simplified.For example, if use QR to decompose (seeing for example Matrix Computations of G.H.Golub and C.F.van Loan, John Hopkins UniversityPress, 1983), lower triangular matrix U ^T(with upper triangular matrix U) is defined as follows:

U ^TU=H ^TH formula 14

At this, grid search comprises general invalid and cancellation, wherein finds the vector that satisfies formula 8 One-component after, it adjust the distance tolerance contribution deducted.(yet different) with common invalid and cancellation heuristic,

Component fixing, found up to the whole vector that satisfies formula 8.Therefore, this algorithm is carried out the search to as shown in Figure 2 tree basically, and wherein the of tree _nThe corresponding subvector of node on the level

Further describe the used distance metric of this searching algorithm, we suppose that now generator matrix is a lower triangular matrix.N dimension grid search or search for n transmit during, received signal r to label is ${\hat{s}}^n\&Element;C_{\mathrm{real}}$ The orthogonal distance of layer be defined as follows, C wherein _RealBe that real-valued symbol conformation is represented:

$d_n=|\frac{{\hat{r}}^n}{h_{n,n}}-{\hat{s}}^n|\&CenterDot;\left|h_{n,n}\right|$

$=|e^{n,n}-{\hat{s}}^n|\&CenterDot;\left|h_{n,n}\right|$ Formula 15

Wherein Be n component of projection received signal in the n-dimensional space, found the emission symbol of higher level

(we suppose n in this example _T=n _R).Item e ^{N, n}Be according to this projection received signal, to the estimation of n emission symbol.The estimation of all the other emission symbols ${\hat{s}}^i,i=1,\&CenterDot;\&CenterDot;\&CenterDot;,n$ Can recursively be obtained following (see people such as Agrell, as above):

$e^{n,j}=e^{n+1,j}-\frac{d_{n+1}}{h_{i,n+1}}$ I=1 wherein ..., n formula 16

Therefore, distance metric d _nCan be according to the current emission symbol  that is searched for ⁿThe emission symbol  of the higher level that had before found ^N+1...  ^NTUpgrade.Because the distance metric during the n+1 dimension grid search is different with n+1 the emission symbol that is found, the used border of n dimension search can be updated as follows:

${\mathrm{\&rho;}}_{\mathrm{<figure-callout\; id="2"\; label="n"\; filenames="A20048000087000401.png,A20048000087000411.png"\; state="\{\{state\}\}">n</figure-callout>}}^2={\mathrm{\&rho;}}_{n+1}^2-{\mathrm{<figure-callout\; id="2"\; label="d\; n"\; filenames="A20048000087000401.png,A20048000087000411.png"\; state="\{\{state\}\}">d</figure-callout>}}_n^{}$ Formula 17

Described distance metric used in this searching algorithm, the ordering of the conformation symbol of searched will be described now.Distance metric (using real-valued expression now) can be written as follows:

‖r-H‖ ²＝(-s″) ^TH ^TH(-s″)

=r ^T(I-H (H ^TH) ^-1H ^T) r formula 18

Wherein

S "=(H ^TH) ^-1H ^TR formula 19

Be the not restrained maximal possibility estimation of s emission signal s, and also be known as to force to make zero and separate.Therefore, can redefine the border that provides in the formula 8 as follows:

(-s ⁿ) ^TH ^TH (-s ⁿ)≤ρ ²Formula 20

Observe, it " is that the center centers on that the scope that satisfies the  of formula 20 is separated s to force to make zero.Therefore will be at the searched symbol of n level ${\hat{s}}^n\&Element;C_{\mathrm{real}},$ And preferably separate s " according to making zero apart from the pressure of n level ⁿThe sequence arrangement that increases of distance.For example, the if symbol conformation is 4PAM (pulse amplitude modulation), i.e. C _Real=3 ,-1 ,+1 ,+3}, and make zero to separate in the pressure of n level search place and be s " ⁿ=-1.1, searched symbol be ordered as 1 ,-3 ,+1 ,+3}.This has been avoided the demonstration of search coboundary and lower boundary to calculate.According to the possible emission symbol of said sequence search, and when distance metric surpassed the border, the search at n level place was stopped, promptly for searched current sign  ⁿ,

$d_{\mathrm{<figure-callout\; id="2"\; label="n"\; filenames="A20048000087000401.png,A20048000087000411.png"\; state="\{\{state\}\}">n</figure-callout>}}^2>{\mathrm{\&rho;}}_{\mathrm{<figure-callout\; id="2"\; label="n"\; filenames="A20048000087000401.png,A20048000087000411.png"\; state="\{\{state\}\}">n</figure-callout>}}^2$ Formula 21

Advance and reconnoiter to next one search level or rank.This ordering can be finished by look-up table, all possible combination of this look-up table stores.For example, a given c * Metzler matrix Φ, the wherein number of c=2M is-symbol search combination, and M be possible signaling point number, be used for that forcing makes zero separates s " ⁿThe vectorial slist that is sorted by capable the providing of i of Φ, as follows:

Slist=Φ (i) wherein Formula 22

And

Expression rounds to infinitely-great direction.Broadly, this technology comprises the modification pattern of the described Schnorr-Euchner strategy of people such as Agrell (as above).

Utilize look-up table to the method for wanting searched symbol ordering at A.Wiesel, X.Mestre, " the Efficient Implementation ofSphere Demodulation " of A.Pages and J.R.Fonollosa, Proceedings of IV IEEE Signal ProcessingAdvances in Wireless Communications, the 535th page, Rome, 15-18 day in June, 2003, in be described in more detail, by with reference to being incorporated in this.

Pressure is made zero and is separated s " ⁿ(or other Linear Estimation) reappraised at each search level place, because the symbol  that finds in the prior searches ^N+1Be cancelled, to obtain to have the inferior integer least square solution problem (seeing formula 15 and formula 16) of falling of n unknown number.

Search radius can be set up in response to noise and/or channel condition.When needing soft output, as described below, the whole symbols that found can be used to soft output evaluation, to avoid the additional complexity of sort algorithm, with the most possible receiving symbol string of acquisition given number.

Briefly, this program comprises three main processes:

I) be grid representation with multiple-input and multiple-output (MIMO) channel conversion.

Ii) search utility, under hard situation about detecting its search apart from the nearest grid point of received signal, the perhaps grid point set around its search received signal under the situation of soft detection.But when the soft input time spent, the prior probability of emission symbol or code word is provided, it can be utilized with auxiliary this search (also sees for example " the Low-ComplexityIterative Detection and Decoding of Multi-Antenna SystemsEmploying Channel and Space-Time Codes " of H.Vikalo and B.Hassibi, Conference Record ofthe Thirty-Sixth Asilomar Conference on Signals, Systems andComputers, the 1st volume, 3-6 day in November, 2002, the 294-298 page or leaf; And H.Vikalo and B.Hassibi " Towards Closing the Capacity Gap on MultipleAntenna Channels ", ICASSP ' 02, the 3 volume, III-2385-III-2388 page or leaf).

Iii) when the soft output of needs, provide soft output (also unnecessary for the spherical encoder of hard detection) based on the grid point set of finding in soft input and the region of search.

[max log MAP decoder]

Through the simple notion of describing spherical encoder, we will describe it and how can be employed so that the decoder based on maximum MAP (maximum a posteriori probability) to be provided.Therefore we provide max log MAP to separate these two candidates that satisfy the max{} item in the formula 7 by search.Therefore, to each bit x _j ⁿCarry out this search utility, satisfy following optimized two candidates to find:

For bit $x_j^n=+1,$

${\hat{s}}^{+}=\underset{\hat{s}\&Element;X_{n,j}^{+}}{\min }\{{\left|\right|r-\hat{s}H\left|\right|}^2-{\mathrm{\&sigma;}}^2{x}^T\&CenterDot;L_A\}$

And for bit $x_j^n=-1,$

${\hat{s}}^{-}=\underset{\hat{s}\&Element;X_{n,j}^{-}}{\min }\{{\left|\right|r-\hat{s}H\left|\right|}^2-{\mathrm{\&sigma;}}^2{x}^T\&CenterDot;L_A\}$

N=1 wherein ..., n _TAnd j=1 ..., q (wherein in above formula, $\hat{s}\&Element;X_{n,j}^{\&PlusMinus;}$ The meaning be to have bit x _{N, j}=± 1 candidate symbol).Be these two candidate d _{N, j ,+} ²And d _{N, j ,-} ²Obtain corresponding distance metric, wherein

$d_{n,j+}^2={\left|\right|r-{\hat{s}}^{+}H\left|\right|}^2-{\mathrm{\&sigma;}}^2{x}^{+T}\&CenterDot;L_A^{+}$ Formula 23

And

$d_{n,j-}^2={\left|\right|r-{\hat{s}}^{-}H\left|\right|}^2-{\mathrm{\&sigma;}}^2{x}^{-T}\&CenterDot;L_A^{-}$ Formula 24

Vector x ⁺, x ^-And L _A ⁺, L _A ^-Corresponding symbol  ⁺And  ^-Bit sequence and prior information.

Therefore, the max log MAP of outside LLR (log-likelihood ratio) value of posteriority is approximate is provided by following formula:

Formula 25

L _PAnd L _EBetween relation by L _P=L _A+ L _EProvide.

With reference to figure 3, it shows the block diagram of max log MAP decoder 200, and this max log MAP decoder is configured to the approximate definite bit likelihood value of max log according to formula 25.This decoder comprises a plurality of hard detectors or decoder 202a-c, 204a-c, and each is configured to basis equation 23 and 24 separately, based on r, and H, if the input value of σ is and available L in addition _A(x), be identified for specific bit x _j ⁿThe distance metric d of probable value _{N, j ,+} ², d _{N, j ,-} ²,+1 is used for detector/decoder 202, and-1 is used for detector/decoder 204.In the present embodiment, n travels through transmitting antenna, and each bit of j traversal conformation symbol.Each of these detector/decoder 202,204 provides distance metric value d to output stage 206 _{N, j ,+} ², d _{N, j ,-} ², this output stage 206 is determined the bit likelihood value according to formula 25 for each bit of emission symbol string.This likelihood value can comprise " outside " and/or posteriority bit likelihood value.The technical staff will recognize that detector/decoder 202,204 can be implemented by serial, for example as the repetition of software process constantly, or parallel enforcement, or implement with the combination of serial and parallel procedure.

Detector/decoder 202,204 only needs to provide hard output, this output identification specific bit value x _j ⁿMost probable candidate for+1 or-1, and/or minimum distance metric d is provided _{N, j ,+} ²Or d _{N, j ,-} ²Therefore the technical staff will recognize that the configuration of Fig. 3 can be used any hard detector/decoder of maximum likelihood that suitable distance metric can be provided.Yet in a preferred embodiment, use one or more sphere decoder to implement hard detector/decoder 202,204.

For receiving vectorial r, candidate  ⁺Or  ^-Be maximal possibility estimation  _ML-be that maximum likelihood is separated bit value set x is provided _MLDistance metric d with correspondence _ML ²Therefore the maximum likelihood sphere decoding can at first be performed, and can carry out bit formula sphere decoding then to obtain distance metric d _{N, j,  ML} ², be used to not correspond to the bit value of maximum likelihood sign estimation.

Fig. 4 shows the block diagram of max log decoder 300, and this max log decoder 300 is configured to this mode determines the bit likelihood value, and uses sphere decoder as hard detector.In Fig. 4, detect the combination of piece 302a-c and output stage 306 corresponding detector/decoder 202 and 204 firmly, they correspond respectively to non-maximum likelihood bit arrangement set $x\&Element;X_{n,j}^{\&NotEqual;\mathrm{ML}}$ Output stage 206 with Fig. 3.Another hard detector 302, preferably sphere decoder is determined maximum likelihood sign string estimation  _ML, and demodulator 303 is converted to bit formula estimation x with this sign estimation _MLThe hard sphere decoder 302 that detects also provides corresponding bit likelihood value d _ML ²(to x _MLAll bits be common).

The further details of this decoder was submitted on October 3rd, 2003, be described in the applicant's the GB Patent Application No. 0323211.3, and among the PCT/GB20043/XXXXXX that requires priority from this Britain's application, be described, its content is incorporated in this by reference.

Fig. 5 shows the block diagram of the 3rd example of two stage max log MAP sphere decoder 310, wherein to Fig. 4 in similar unit indicate by same reference numerals.In the decoder of Fig. 5, phase I comprises two maximum likelihood decoders, be configured to first bit and determine minimum distance metric, each of these maximum likelihood decoders is to have first first bit with one of second logic level to determine distance metric.At this, corresponding symbol string than short distance tolerance provides maximum likelihood emission symbol.Second stage is included as each another maximum likelihood detector that bit disposed subsequently, and each of these maximum likelihood decoders is determined distance metric for the bit value that is different from its value in the maximum likelihood sign string.Any one or two stages can carry out with parallel processing in two stages of maximum likelihood detector.

[sphere decoding that is used for multi-user system and general conformation]

A difficulty that above decoding technique is applied to the general symbol conformation is that under normal conditions, a symbol of emission string may depend on another.For example, s ²May not be independent of s ¹, because s ¹And s ²May form an independent complex symbol.

Embodiments of the invention are introduced a kind of mapping function that is used for each search level, and it revises original spherical decoding technique to handle general complex symbol conformation.Each different search level n has its specific searched possible real-valued symbol of wanting and tabulates.(each search level search will be by one of symbol string of sphere decoder joint-detection.) therefore, current search level and real-valued symbol that will be searched have a kind of mapping between tabulating.

For real-valued system, embodiments of the invention map to each clathrum for this specific search level and want the searched real-valued conformation symbol or the set of code word.Therefore grid search is performed on the finite aggregate corresponding to the clathrum of symbol conformation or code word, rather than corresponding to grid input s ∈ z ^mThe infinite set of layer of integer label close and be performed.At this, real-valued symbol or code word can be different for difference search level.For example, under the situation that Multiuser Detection detects the data by three user's emissions, first and second user may use BPSK (binary phase shift keying) scheme, i.e. s ¹, s ²{ 1 ,+1} and third party may use 4PAM (pulse amplitude modulation) scheme, i.e. s to ∈ ³∈ 1.8974 ,-0.6325,0.6325,1.8974}.So first and second search level (their detect emission from first and second user's data) pair set s ¹, s ²∈ 1 ,+1} carries out, and the 3rd search level (they detect the data of emission from third party) pair set s ³{ 1.8974 ,-0.6352,0.6352,1.8974} carries out ∈.

For the situation of multiple conformation, the complex representation of communication system is by decoupling zero, and to be transformed to dimension be that two times real matrix of primal system is represented, and decoding program will searched clathrum be mapped as the reality or the imaginary component of symbol conformation or code word.Different search levels reuses wants searched different real-valued assemble of symbol, depends on this application.

The technical staff will be understood that the embodiment of similar manner of the present invention also can be used to use so-called bit to load and decode in mimo system.This transmission system is used the bit of (" loading ") different numbers to each symbol, be used for different transmit antennas, for example depend on the channel quality (mimo system is a target to have incoherent relatively each other different transmit receive antenna channels usually) that the transmitting antenna channel link is experienced.For example in 3 pairs 3 mimo system, first antenna may be launched BPSK, second antenna emission 16QAM, and three antenna emission QPSK.If use this bit loading scheme, technology described here helps the enforcement of the robustness of sphere decoder.Bit loads and has been proposed for example to be used for some following WLAN (WLAN (wireless local area network)) standard.

In some cases, the searched clathrum or the set of real-valued symbol is condition with layer or the real-valued symbol that finds in the prior searches, is condition with previous identification as the symbol of the formation part of candidate symbol string promptly.This has allowed the use of non-square complex symbol conformation, wherein needs two search levels to detect a complex symbol.At this, the mapping of the real-valued assemble of symbol that search for real component for example is performed according to the real-valued symbol of the corresponding imaginary component that had before found.The parameter of mapping is the label n of current search level and the symbol s that had before found ^N+1A look-up table is according to mapping parameters n and s ^N+1Provide and wanted searched possible assemble of symbol.

Fig. 6 shows the 8PSK conformation with possibility assemble of symbol:

$s\&Element;\left\{\begin{array}{c}1.6002+0.6628i,0.6628+1.6002i,\\ -1.6002+0.6628i,-0.6628+1.6002i,\\ 0.6628-1.6002i,1.6002-0.6628i,\\ -0.6628-1.6002i,-1.6002-0.6628i\end{array}\right\}$

In this case, the real matrix of 8PSK conformation represents it will will be input set s _Real=1.6002 ,-0.6628,0.6628,1.6002}.To there be four to want searched clathrum, corresponding four real-valued possible symbols.Because the conformation right and wrong are square, depend on the layer that finds in the prior searches level corresponding to real-valued actual layer set that may symbol.

Fig. 7 shows the situation for 2 couple's 2 who uses 8PSK mimo system, be n set of searching for searched input grid point of level or layer; At this one of each layer expression want decoded real-valued emission symbol (promptly as mentioned above, from complex value derived real-valued to).As can be seen, the set of variable that be searched depends on the Search Results of (n-1) level layer before.For example, if in the region of search at n=4 place, find symbol $s_{\mathrm{real}}^4=-1.6002,$ The incoming symbol set $s_{\mathrm{real}}^3\&Element;\{-\mathrm{0.6628,0.6628}\}$ In the grid search at n=3 place, be considered.Real-valued symbol s _Real ⁴And s _Real ³Corresponding complex symbol.Next search level will not rely on the symbol s that is found _Real ³If therefore $s_{\mathrm{real}}^3=-0.6628$ Be considered, wanting searched input grid point set at the n=2 place is whole set $s_{\mathrm{real}}^2=\{-1.6002,-\mathrm{0.6628,0.6628,1.6002}\}.$

Following table 2 has provided the look-up table that the symbol tabulation of wanting searched is provided, and it shows the symbol search look-up table that sphere decoder is used for two transmitting antenna 8PSK BLAST systems.

Table 2

The current search level, n	The symbol that had before found, s n+1	Want searched symbol tabulation
			4,2 (even numbers)	??-1.6002， ??-0.6628， ???0.6628， ???1.6002	??-1.6002， ??-0.6628， ???0.6628， ???1.6002
3,1 (odd number)	??-1.6002， ???1.6002	??-0.6628， ???0.6628
			3,1 (odd number)	??-0.6628， ???0.6628	??-1.6002， ???1.6602

Note, depend on the enforcement of program, the symbol s that had before found ^N+1Can be by label rather than symbol expression itself.

Want searched assemble of symbol preferably to separate s according to making zero apart from pressure _ZF=(H ^TH) ^-1H ^TThe order that the distance of r increases is sorted, and search is also similarly sorted.

The general look-up table represented by J * K matrix T is used to provide one or more symbol list collection with having superiority, so that this search order to be provided.The capable vector of look-up table provides a symbol tabulation, and it is sorted and makes each symbol apart from forcing to make zero to separate s _ZFDistance increase.J capable vector be presented select as follows, j=1 wherein ..., J:

Formula 26

Wherein K is the number of conformation symbol that will be searched at a search level place, s _MinBe the symbol of symbol tabulation intermediate value minimum that will be searched, s _MaxBe the symbol of the symbol tabulation intermediate value maximum of wanting searched, and a and b be respectively zoom factor and constant, so upper limit function Provide may symbol label, it makes zero near n pressure of searching for the level place and separates s _ZF ⁿAt this J is that definition is apart from forcing to make zero to separate s _ZFThe number of the required conformation symbol sebolic addressing that sorts of the possible collating sequence of the order that increases of distance (for example see T hereinafter ₁, wherein first row can be-0.6628 corresponding to the value of symbol that just is lower than 0.6628 then, and second row can be corresponding to just above 0.6628 value of symbol).This means that for example the row of first in this matrix starts from minimum symbol (probably $s_{\mathrm{ZF}}^n\&le;s_{\min }$ ) and last column to start from maximum symbol (very possible $s_{\mathrm{ZF}}^n\&GreaterEqual;s_{\min }).$

Utilize above given example, this 8PSK system has the form of following order or ordering, and (polarity of look-up table is to the s of negative value _ZF ⁿReverse, because the symbol conformation is symmetrical):

${\mathrm{<figure-callout\; id="1"\; label="T"\; filenames="A20048000087000411.png,A20048000087000471.png"\; state="\{\{state\}\}">T</figure-callout>}}_1=\left[\begin{array}{cccc}0.6628& -0.6628& 1.6002& -1.6002\\ 0.6628& 1.6002& -0.6628& -1.6002\\ 1.6002& 0.6628& -0.6628& -1.6002\end{array}\right],$

T ₂＝[0.6628?-0.6628]，

T ₃＝[1.6002?-1.6002]，

T wherein ₁, T ₂And T ₃Respectively to should search for level be n ∈ 2,4} and the symbol s that had before found ^N+1∈ 1.6002 ,-0.6628,0.6628,1.6002}, the search level be n ∈ 1,3} and the symbol s that had before found ^N+1∈ 1.6002,1.6002}, the search level be n ∈ 1,3} and the symbol s that had before found ^N+1∈ 0.6628, the permutation table during 0.6628}.

In this example, for all look-up table T ₁, T ₂, T ₃, used having determined provides the parameter of the row vector of the symbol table that sorts to be given as a=1, b=0, s in the formula 26 _Min=0.6628, s _Max=1.6002 (on the occasion of s _ZF ⁿ).Make zero for the pressure of negative value and to separate s _ZF ⁿ, s _ZF ⁿSymbol or polarity be left in the basket (promptly in formula 26, use | s _ZF ⁿ| rather than s _ZF ⁿ) vectorial with the correct row that look-up table is provided in formula 26, and element T in the look-up table ₁, T ₂, T ₃Polarity be inverted.

The technical staff will further understand, and the distortion of this program also can be used to aforesaid max log sphere decoding.In above-mentioned max log decoding program, be+1 to all given bits $(\hat{s}\&Element;X_{n,j}^{+1}=\{x|x_j^n=+1\})$ Or-1 $(\hat{s}\&Element;X_{n,j}^{-1}=\{x|x_j^n=-1\})$ Symbol string carried out search.This be equivalent to the constraint symbol searched in the particular search level, for example for ${\mathrm{<figure-callout\; id="1"\; label="x"\; filenames="A20048000087000411.png,A20048000087000471.png"\; state="\{\{state\}\}">x</figure-callout>}}_1^1=+1$ Retrain its first bit of first symbol of going here and there to be set to+1.Above-mentioned sign map helps this max log MAP sphere decoding, wherein only might the symbol conformation the subclass of emission bit of (or+1 or-1) is considered in search corresponding to being 1 or 0.

Therefore broadly, embodiments of the invention help to be used for the sphere decoding of the robust of ordinary circumstance symbol conformation, and especially when plural but be non-square symbols conformation when being used, sphere decoding becomes possibility.The example of this symbol conformation comprises star QAM, 8PSK and 16PSK.Embodiments of the invention also make when usage space multiplexed signals in the Space Time Coding system transmit, and/maybe when launching the signal use distinct symbols conformation of different user in cdma system, can use sphere decoding.An example of this system be have different pieces of information speed and/or have adaptive modulation and coding (AMC) scheme two users' cdma system, wherein first user may use for example QPSK modulation scheme, and second user may use for example 16QAM modulation scheme.

[sphere decoder embodiment]

Fig. 8 shows according to said procedure, is used for the flow chart of general symbol conformation sphere decoding.The technical staff will expect that the flow chart of Fig. 8 can be incorporated in hardware or software or the combination of the two, utilize that serial is implemented or parallel function, or the two all uses.The example of Fig. 8 shows the hard decision sphere decoder, but soft sphere decoding program also can be implemented with similar mode according to the above formula that provides.

The conventional sphere decoding program of in Fig. 8, revising based on existence, grid H (F=H ^-1, wherein F is a triangular matrix, and H for example uses QR to decompose the pretreated triangular matrix that is) generator matrix be the grid representation of communication system, and received signal is r.At this, the mode that r is identical with the generator matrix that is used for search utility is pretreated.For example, if

Be the original channel matrix, matrix

QR decompose and to provide $\stackrel{\&CenterDot;\&CenterDot;}{H}={\left(\mathrm{QR}\right)}^T,$ And so H=R ^TGiven primary reception signal vector is So pretreated received signal is by r=rQ ^TProvide.The output of this program is s _MLAnd d _MLOutput s _MLBe corresponding near the grid input (transmitting) of the grid point of received signal r, and be that maximum likelihood is separated.Output d _MLBe corresponding to grid input s _MLDistance metric.

The region of search is by search radius ρ ²Definition.(a b) provides vectorial suc as formula the row of 26 described general look-up table matrix T, wherein to function S ortedList $s_{\mathrm{ZF}}^n=a,$ And this provides for the look-up table matrix is independent of and formerly searches for the symbol b that finds in the level and make.Slist _nBe that length is the vector of M, wherein M is the number (equaling the K in the formula 26) of the possible symbol that search level n place will be searched, and step _nCount from 1 to M.Mark slist _{N, i}Sensing amount slist _nI element.The pressure of n dimension search place is made zero and is separated by e _n:=rF provides.The number of unknown number (wanting the length of estimative symbol string) is N.At this, for the system that uses the complex symbol conformation, wherein complex representation is that dimension is two times a real representation of primal system by decoupling zero, N=2n _T

Three kinds of situation A, B and C are as mentioned above; This procedure initialization n=N broadly, and with each symbol of sequence checking of slist, all be verified (as search place of n dimension, slist up to all _nIn all symbols be verified, it is real all being verified), when at search radius ρ ²Move one deck (situation C) in the time of in addition, and finish when the top of getting back to tree (n==N).If desired, the total number of situation about being verified (A, B or C) can be limited, this restriction is by determined distance metric is counted, and stops (further describing as institute in No. the 0323208.9th, the applicant's the UK Patent Application) when it surpasses maximum or limiting value.

Fig. 9 shows a kind of receiver 500, and it has incorporated the decoder that is configured to the embodiment that implements said procedure into.Figure 10 shows and is fit to and the common transmitter 550 that uses of the receiver of Fig. 9.

With reference to figure 9, receiver 500 comprises one or more reception antenna 502a, b (wherein two shown in the illustrated embodiment), each is coupled to separately rf front end 504a, b, and be coupled to separately analog to digital converter 506a, b, and to digital signal processor (DSP) 508 from this.DSP 508 will typically comprise one or more processor 508a and working storage 508b.DSP 508 has data output 510 and address, DCB 512, DSP is coupled to the permanent program memory 514 of flash memory ram for example or ROM.Permanent program memory 514 storage codes, and optionally, store data structure or be used for the data structure definition of DSP 508.

As shown in the figure, program storage 514 comprises sphere decoder sign indicating number 514a, and it comprises grid generated code (estimating from matrix/mimo channel), forces to make zero estimated code, tree foundation/searching code, and symbol tabulation search key.The soft output decoder device can comprise soft information evaluation sign indicating number; The max log decoder can comprise the max log sign indicating number, so that a plurality of hard sphere shape decoder execution modes of serial or parallel to be provided, and definite max log MAP function.When institute's stored program code is moved, implement aforesaid corresponding function on DSP 508.Program storage 514 also comprises mimo channel estimated code 514b, estimates H so that mimo channel to be provided, and optionally, deinterleaver sign indicating number 514c, interleaver sign indicating number 514d, channel decoder sign indicating number 514e, with group code search look-up table 514f, for example as discussed previously with reference to formula 26.The execution mode of deinterleaver sign indicating number, interleaver sign indicating number and channel decoder sign indicating number is well-known to one skilled in the art.Optionally, the sign indicating number in the permanent program register 514 for example can be provided on light or the signal of telecommunication or the carrier as the illustrated floppy disk 516 of Fig. 5.

If desired, be provided for other data processing unit (not shown in Figure 5) of receiver 500 from the data output 510 of DSP 508.They can be to be used to implement the more base station data processor of high-level protocol.

Receiver front end will be implemented in hardware usually, and receiver is handled and will be implemented in software at least in part usually simultaneously, although one or more ASIC and/or FPGA also can be used.The technical staff will expect that all functions of receiver can be performed in hardware, and signal is digitized really in software radio, and the point of contact will generally depend on cost/complexity/power consumption balance.

In other embodiments, decoder can be configured to signal processing module, for example implements soft input/soft output (or hard decision) decoder when empty.

Figure 11 shows the block diagram of the transmitter of the channel encoder with series connection; Frequency-selective channel can be considered to one " encoder ".Among Figure 11, encoder 2 can comprise the normal channel encoder, and encoder 1 can comprise the STBC encoder in conjunction with this channel.

Figure 12 shows the block diagram of the receiver of channel decoder with series connection or detector, is fit to use jointly with the transmitter of Fig. 4.In Figure 12, detector or decoder 1 can comprise aforesaid sphere decoder, and decoder 2 can comprise the normal channel decoder.Figure 13 shows the block diagram of distortion of the receiver of Figure 12, and the distortion of this receiver has the decoder or the detector of the series connection of using iteration or " turbo " decoding.Figure 14 shows the block diagram of the receiver of two examples that comprise decoder 1, and this receiver for example can comprise decoder when empty.In Figure 14, the output of a decoder provides the priori that is used for another decoder.By this way, decoder element iteratively in fact with self exchange soft information, to improve the reliability of decoded data.In one case, received signal is provided to two decoders, optionally (depends on the configuration that interweaves at receiver place) and is interleaved.

Figure 15 shows the 8PSK mimo system for 4 couple 4 on the constant irrelevant Rayleigh fading channel of piece, and bit error rate is with the curve chart of signal to noise ratio (Eb/No).Curve 1000 and 1002 shows the performance of aforesaid max log sphere decoder according to an embodiment of the invention, curve 1004 and 1006 show max log approximate MAP (posterior probability) decoder performance-as can be seen, their performance is identical basically.Curve 1000 and 1004 relates to uncoded system, and curve 1002 and 1006 relates to use half rate (5,7) _OctThe system of convolution code.

The technical staff will appreciate that embodiments of the invention have application in polytype communication system, comprises MIMO and multi-user system.Application comprises moves interruption, access point, and the base station, for example unlimited LAN, and in radio receiver design and the application in signal processor.Embodiments of the invention can also be sought potentially in non-RF system and use, and for example have in fact as a plurality of read heads of a plurality of transmitters and the disc driver of a plurality of data record layers.When non-square symbols conformation or Adaptive Modulation were used, embodiments of the invention were particularly useful.

In multi-user system, generator matrix (or equivalently, channel matrix) can represent to propagate with channel the combination of user's influence (is seen for example L.Brunel, " OptimumMultiuser Detection for MC-CDMA Systems Using SphereDecoding ", 12th IEEE International Symposium on Personal, Indoorand Mobile Radio Communications, the 1st volume, 30 days-October 3 September calendar year 2001, the A-16-A-20 page or leaf is incorporated in this by reference).

In some applications, sphere decoder can be applied to the block equalizers that is used for frequency selective fading.At this, channel model can be modified, and remembers to consider channel, and is as follows:

Wherein

And wherein T is by the length of the symbolic blocks of equilibrium, and H _iBe i mimo channel tap.This sphere decoder can be used to detect transmitting block

Embodiments of the invention can be applied to channel decoder, when channel encoder can be represented as linear generator matrix G.Example is that the piece channel code (is seen Bernard Sklar " DigitalCommunications:Fundamentals and Applications ", Pretice HallInternational Editions, 1999,0-13-212713-x), for example Hamming code and linear density parity check (LDPC) are encoded, wherein code word x is produced by x=sG from information bit s by generator matrix G, and wherein vectorial s comprises information bit.For the LDPC sign indicating number, for example, generator matrix G derives from parity check matrix H, to satisfy quadrature requirement GH ^T=0, and any legal-code xH that will satisfy condition ^T=0.At this, information and codeword block, s and x promptly 1 and 0 are made up of binary digit, and this matrix manipulation is in binary field.

Embodiments of the invention provide based on the maximum-likelihood code word of formula 7 or soft output.In the exemplary embodiment, have input r and use G and determine the distance between each possible emission code word in received signal r and its search as the sphere decoder of generator matrix.Code word with minimum range is the maximum likelihood code word.The conversion of its use information and codeword block, { 0, { 1 ,+1} uses arithmetical operation to 1} then to signed value from binary field.

Undoubtedly, for the technical staff, many other can occur and effectively supply the method for replacement.Will be understood that the present invention is not restricted to described embodiment, and be included in the essence and the interior conspicuous modification concerning those of skill in the art of scope of this appending claims.

Claims (17)

1. sphere decoder, dispose it to search for apart from one or more symbol strings of input signal less than the search boundary, this search is to set up a value by each symbol of the described string that is followed successively by the candidate, setting up a value for each symbol of candidate's described string is by being followed successively by each described symbol assumed value of described candidate's string, and determine whether the value of symbol of being supposed obtains one and depend on the distance metric that described search boundary is satisfied, the rank that each described symbol definition of the value of being assumed to be of described candidate's string should be searched for, this sphere decoder comprises the data structure that is configured to a value of symbol set of each described search level definition, the value of described supposition is selected from this value of symbol set, and it is different that described value of symbol is integrated into different search level.

2. sphere decoder as claimed in claim 1, wherein said input signal comprise uses a plurality of different modulation schemes encoded signals, and the set of wherein said value of symbol is provided for each different modulation scheme.

3. sphere decoder as claimed in claim 2, wherein said input signal comprise the signal that sends by a plurality of different communication channels that use described a plurality of different modulation schemes.

4. as claim 2 or 3 described sphere decoder, this sphere decoder is used in multi-user system signal decoding, wherein said input signal comprises the signal that receives from a plurality of users that use described a plurality of modulation schemes, and wherein said one or more symbol string comprises the symbol by described a plurality of user's emissions.

5. as claim 1,2,3 or 4 described sphere decoder, wherein said data structure comprises a plurality of value of symbol set that are used at least one described search level.

6. sphere decoder as claimed in claim 5, the value that also is configured to according to the previous foundation of the described symbol of described candidate string or symbol string is that a described search level is selected one of described a plurality of value of symbol set.

7. as sphere decoder as described in the claim 6, this sphere decoder is used at system's decoded signal, and data are encoded on a plurality of communication channels in this system, and wherein said input signal comprises the signal that receives by described a plurality of channels.

8. as any one described sphere decoder in the claim 1 to 7, wherein each described symbol is derived from one or more data bits, and one of wherein said value of symbol set only comprises the symbol corresponding to one of described data bit with selected binary value.

9. as any one described sphere decoder in the claim 1 to 8, wherein said data structure comprises a plurality of forms, and each form is used for a different value of symbol set.

10. sphere decoder as claimed in claim 9, the value of symbol of wherein said form sorts according to the distance of the initial estimation of the described symbol string of distance.

11. sphere decoder as claimed in claim 10, wherein at least one described form comprises a plurality of repetitions of value of symbol set, and each repetitive sequence is all different, and can carry out index by described initial estimation.

12. as any one described sphere decoder in the claim 1 to 11, this sphere decoder is used for the signal that is sent to a plurality of reception antennas from a plurality of transmitting antennas is decoded, wherein said symbol string is by described a plurality of transmission antennas transmit, and wherein said input signal is derived from the signal that is received by described a plurality of reception antennas.

13. method that input signal is decoded, this input signal comprises the signal that receives by a plurality of communication channels from a plurality of signal transmitters, described a plurality of signal transmitter is launched a plurality of symbols, this coding/decoding method is searched for the symbol string of the estimation of the described emission symbol of one or more expressions, this decoding comprises each symbol of the described string that is followed successively by the candidate and sets up a value, setting up a value for each symbol of candidate's described string is by being followed successively by each described symbol assumed value of described candidate's string, and determine whether the value of symbol of being supposed obtains one and depend on the distance metric that the search boundary is satisfied, this region of search that depends on described input signal of search boundary definition, a rank of the described search of each symbol definition of the value of being assumed to be of described candidate's string, described decoding also is included as value of symbol set of each described search level definition, the value of described supposition is selected from this value of symbol set, and it is different that described value of symbol is integrated into different described search level.

14. implement the processor control code of the method for claim 13 during operation.

15. load the carrier of the processor control code of claim 14.

16. comprise the receiver of the carrier of claim 15.

17. a decoder that is used for decoding to received signal, this received signal comprise the symbol string by the mimo channel emission, this decoder comprises:

Sphere decoder, search candidate transmitting symbol string in the radius of described received signal, and decoded data output is provided; And

The sphere decoder data structure disposes it and thinks that described search defines the set of a plurality of different values of symbol, and the candidate symbol that wherein is used for each symbol of described string can be selected from described different values of symbol set according to their position at described string.

Images