JP2007519281A - Signal decoding method and apparatus - Google Patents

Abstract

The present invention generally relates to a method, apparatus and processor control code for decoding a signal, particularly by sphere decoding. A method for decoding a signal generated by having one value out of a plurality of values encoded as a symbol string using a plurality of symbols and then received through a channel. One or more symbol sequence candidates that are sequences of symbol candidates are searched by searching for symbol candidates in a certain area of the determined multidimensional lattice, and the lattice corresponds to each symbol of the symbol sequence. The region is defined by a distance from the received signal, and includes decoding the symbol sequence by selecting one or more candidate symbol sequences for the received signal; The symbol candidate search selects a candidate value of the transmitted symbol, and the lattice defined by the selected candidate is a boundary from the received signal. The method comprising testing whether the inside of the distance, the search and limited that signal decoding method comprising for a function to stop the candidate symbol number after testing.
[Selection] Figure 4

Description

  The present invention relates generally to a method, apparatus and processor control code for decoding a signal, and more particularly to processor control code with sphere decoding.

  Sphere decoding is a technique having various application ranges in the field of signal processing. Here, a specific reference will be made to the signal received on a MIMO (Multiple Input Multiple Output) channel and the application of the technique to space-time decoding. However, embodiments of the invention described herein can be applied to related systems, such as multi-user systems, and other similar decoding, eg, multi-user determinators in CDMA (Code Division Multiple Access) systems. .

  There is an ongoing need for improved data transmission rates and, equivalently, means for more efficiently using available bandwidth at a constant transmission rate. Currently, wireless local area networks (WLANs) such as Hiperlan / 2 (in Europe) and IEEE 802.11a (in the United States) offer data transmission rates of up to 54 Mbit / s. The use of multiple transmit / receive antennas can significantly increase these data transmission rates, but one receive antenna receives signals from all transmit antennas, so it decodes the signals received on the MIMO channel. It is difficult. Although symbols transmitted on different channels are uncorrelated, a similar problem occurs in multi-user systems. Therefore, there is a need for improved decoding techniques for MIMO systems. These technologies have applicability in wireless LANs, possibly in fourth generation mobile telephone networks, or in many other communication system types.

  FIG. 1 shows a typical MIMO data communication system 100. Data source 102 provides data (including information bits or symbols) to channel encoder 104. Channel encoders typically comprise a convolutional encoder such as a recursive systematic convolutional (RSC) encoder, or a more powerful so-called turbo encoder (including an interleaver). More bits than the input bits are output, and generally the coding rate is mainly 1/2 or 1/3. Channel encoder 104 is followed by channel interleaver 106, and in the example shown, space-time encoder 108. The space-time encoder 108 encodes input symbols (single or multiple symbols) as multiple code symbols for simultaneous transmission from multiple transmit antennas 110.

  Space-time coding is described as one of the encoders and is described by a coding matrix that operates on the data to provide space and time transmission diversity; this is a coding symbol for transmission. Follow the modulator to provide. Space-frequency coding is used in addition (or instead). Thus, in a broad sense, input symbols are distributed in a grid having space and time and / or frequency coordinates for increased diversity. Where space-frequency coding is used, individual frequency channels are modulated onto OFDM (orthogonal frequency division multiplexing) carriers, and a cyclic prefix is added to each transmission symbol to mitigate the effects of channel dispersion.

  The encoded transmission signal propagates via the MIMO channel 112 to the receive antenna 114, which provides multiple inputs to the space-time (and / or frequency) decoder 116. The decoder has the task of removing the effects of encoder 108 and MIMO channel 112 and is implemented by a sphere decoder. The output of decoder 116 includes multiple signal streams, one for each transmit antenna, each carrying so-called soft output, or likelihood data, based on the probability of a transmission symbol having a particular value. This data is provided to a channel deinterleaver 118 that inverts the result of the channel interleaver 106 and to a channel decoder 120 such as a Viterbi decoder that decodes the convolutional code. In general, the channel decoder 120 is an SISO (soft-in soft-out) decoder, which is likelihood data of a received symbol (or bit), and has a higher accuracy as an output than a hard decision decoder. Provide data. The output of channel decoder 120 is provided to data sink 122 for further processing of the data in some desired manner.

  In some communication systems, so-called turbo decoding is applied and the soft output from the channel decoder 120 is provided to the same channel interleaver 124 as the channel interleaver 106, which is an iterative space-time (and / or frequency) and channel. Soft output (likelihood) data is sequentially provided to the decoder 116 for decoding. When iterative decoding is applied in this way, it is effective that the presence or absence of an error can be transmitted to the decoder by including an error check bit.

  It is understood that both channel coding and space-time coding provide time diversity in the communication system described above, and thus this diversity follows the law of diminishing return in the additional signal-to-noise ratio gain terms that can be achieved. Will be done. Thus, when considering the convenience provided by certain space-time / frequency decoders, these are best considered in the context of systems involving channel coding.

  One of the most difficult tasks in the communication system 100 is the space-time (or frequency) block code (STBC) decoding performed by the decoder 116, which transmits transmission symbols that are interfering with each other at the receiver. This is because separation is included. The optimal STBC decoder is an a posteriori probability (APP) decoder, which performs an exhaustive search for all possible transmission symbols. Such a decoder considers every possible signal point for all transmit antennas and actually compares these with the received signal by calculating all possible received signals and is most likely The signal having the closest Euclidean distance is selected as a solution. However, the number of combinations to consider is enormous, even with a small number of antennas, modulation schemes such as 16QAM (Quadrature Amplitude Modulation), and relatively short time dispersion, and the complexity of the approach is exponential with data transmission rate. Increase. Suboptimal approaches are therefore technically and commercially important.

  Some common choices for space-time block decoding include linear estimators such as zero forcing and minimum mean square error (MMSE) estimators. The zero forcing scheme is applied to directly calculate an estimate of the sequence of transmitted symbols, or the estimated symbol is a “sequential interference suppression” method that subtracts the effect of the previously calculated symbol before the next is determined. It is decided one by one. In this method, for example, the most reliable symbol can be calculated first.

  Sphere decoding or demodulation broadly represents the search space as a lattice (depending on the matrix channel response and / or space-time encoder) and is located within a hypersphere of a given radius centered on the received signal By searching for the best estimated value for the transmission symbol sequence only on the possible symbol sequences that generate the grid points to be performed, the load can be greatly limited and the performance of the APP decoder can be approached. The maximum likelihood solution is a transmission signal that takes into account the influence of the channel closest to the corresponding received signal when corrected by the channel. In fact, matrix channel responses and / or space-time encoders tend to distort the input point space from a rectangular grid, and conceptually the search area in the input point space is an ellipsoid rather than a sphere.

  Since the search space is reduced from the entire lattice to just a small portion of the lattice, the number of computations required for the search is greatly reduced compared to an APP decoder and similar characteristics can be obtained. However, there are several problems in the practical application of such a procedure. First of all, it must be checked whether the grid points are within the required distance of the received signal. This is a relatively simple procedure and is outlined below. However, secondly you have to decide what radius to adopt. This is important for the speed of the search, and several but not too many grid points must be chosen so that they are found within the radius. The radius is adjusted according to the noise level and optionally according to the channel. However, there is a more subtle problem that the number of searches is not fixed even if the search radius is determined, and in a practical system, it is the time required to calculate the sphere decoding calculation (and hence the available data rate). Means cannot be determined. This is one problem addressed by embodiments of the invention.

Background prior art on sphere decoding can be found at:
E. Agrell, T. Eriksson, A.M. Vardy and K. Zeger, “Closest Point Search in Lattices”, IEEE Trans. On Information Theory, vol. 48, no. 8, Aug. 2000; Viterbo and J. Boutros, “A universal lattice code decoder for fading channels”, IEEE Trans. Inform, Theory, vol. 45, no. 5, pp. 1639-1642, Jul. 1999; Damen, A. Chkeif and J. C. Belfiore, “Lattice code decoder for space-time codes”, IEEE Comms. Letter, vol. 4, no. 5, pp. 161-163, May 2000; M. Hochwald and S. T. Brink, “Achieving near capacity on a multiple-antenna channel”, http://mars.bell-labs.com/cm/ms/what/papers/listsphere/, December 2002; “On the expected complexity of sphere decoding”, in Conference Record of the Thirty-Fifth Asimolar Conference on Signal, Systems and Computers, 2001, vol. 2, pp. 1051-1055; Hassibi and H. Vikalo, “Maximum-Likelihood Decoding and Integer Least-Squares: The Expected Complexity”, in Multiantenna Channels: Capacity, Coding and Signal Processing (J. Foschini and S. Verdu), http://www.its.caltech.edu/ ~ Hvika1o / dimacs.ps; M. Chan, “A New Reduced-Complexity Sphere Decoder For Multiple Antenna System”, IEEE International Conference on Communications, 2002, vol. 1, April-May 2002; Brunel, J.H. J. Boutros, “Lattice decoding for joint detection in direct-sequence CDMA systems”, IEEE Transactions on Information Theory, Volume: 49, Issue: 4, April 2003, pp. 1030-1037; Wiesel, X. Mestre, A. Pages and J. R. Fonollosa, “Efficient Implementation of Sphere Demodulation” Proceedings of IV IEEE Signal Processing Advances in Wireless Communications, pp. 535, Rome, June 15-18, 2003; US Patent Application Number US 2003 / 0076890B. M. Hochwald and S. Ten Brink, filed July 26, 2002, “Method and apparatus for detection and decoding of signals received from a linear propagation channel”, to Lucent Technologies; US Patent Application Number US2002 / 0114410L. Brunel, filed August 22, 2002, “Multiuser detection method and device in DS-CDMA mode”, to Mitsubishi; Vikalo, “Sphere Decoding Algorithms for Digital Communications”, PhD Thesis, Stanford University, 2003; Hassibi and H. Vikalo, “Maximum-Likelihood Decoding and Integer Least-Squares: The Expected Complexity”, in Multiantenna Channels: Capacity, Coding and Signal Processing, (editors J. Foschini and S. Verdu).

For example, Agrell et al. Describe a closest-point search for an infinite lattice whose input is an arbitrary m-dimensional integer, ie, x∈Z ^m , and the basic concepts of lattice decoding and search methods are described. Although outlined, it merely describes how to provide a hard decision output. Most of the other papers require evaluation of search area boundaries, and nevertheless do not guarantee the computation of bounded complexity.

ここで、Ｋは軟出力を推定するために必要なシンボルの所定の数、例えば５０、である。初期探索半径はＫシンボルが見出されるまで無限大に設定される。そのリストが一杯になるとき、即ちＫシンボルが見出されたとき、探索半径はリストにおける最大距離メトリックに設定される。候補のリストが可能な限りのＫ最短距離メトリックを持つように、多数の並べ替え（sort）が候補リストを並べ替える効率的な方法として提案される。これは効果的に設定処理手順の役割を果たす。しかしながら再び、チャネル統計に依存してこの方法の計算量は境界を限定しない。

Here, K is a predetermined number of symbols necessary for estimating the soft output, for example, 50. The initial search radius is set to infinity until K symbols are found. When the list is full, ie when K symbols are found, the search radius is set to the maximum distance metric in the list. Multiple sorts are proposed as an efficient way to sort the candidate list so that the candidate list has the K shortest distance metric possible. This effectively serves as a setting procedure. But again, depending on the channel statistics, the complexity of this method does not limit the boundaries.

  Other decoders or determinators (where both terms are meant to solve a similar problem of detecting the originally transmitted data, so the terms are used interchangeably) Sub-optimal performance such as trellis decoders such as Viterbi decoders (with exponential complexity), and V-BLAST (Bell labs Layered Space Time) decoders and block decision feedback equalizers. Includes a reduced complexity determiner.

  In this regard, it is helpful to provide an overview of the operation of the sphere decoding procedure. For a sequence of N transmitted symbols, an N-dimensional lattice is searched, starting with the Nth dimensional layer (corresponding to the first symbol in the sequence). A symbol from all signal points that can be transmitted is selected as a signal in this hierarchy, and the distance of the generated grid point from the received signal is examined. If the grid point is within this distance, the procedure selects the value for the next symbol in the column and examines the distance of the generated grid point from the received signal in N-1 dimensions. The procedure continues to examine each successive symbol in sequence, and if everything is in range, it eventually converges to a grid point in one dimension. If the symbol is outside the selected radius, the procedure returns to the next higher hierarchy and selects the next possible symbol in that layer (dimension) for inspection. In this way, the procedure creates a tree with the lowest nodes corresponding to the complete sequence of symbols, and the number of nodes at the nth level of the tree is the grid point inside the associated nth dimension sphere. Corresponds to the number of.

  When a complete symbol string candidate is found, the distance between the received signal and the grid point generated from the symbol string is found. In the search for the maximum likelihood solution, since a more optimal solution exists at a point closer to the received signal than this distance, the initial radius can be reduced to this distance. When the tree is completed, the decoder can be used to provide a hard output, ie, a maximum likelihood solution, by selecting the closest grid point to the received signal. Alternatively, the soft output can be determined using a plurality of grid points closest to the received signal, eg, using each of these distances from the received signal as an associated likelihood value. A number of permutations have been proposed to select a subset of candidates with grid points that have the shortest distance metric in the received signal, as further described below. Also proposed is a method using a subset of signal candidates that sets a fixed search radius through search and provides a distance metric smaller than the fixed search radius.

  A method for decoding a signal that is transmitted after being encoded as a symbol string using a plurality of symbols and having been generated by having one value among a plurality of values and received through a channel is proposed. The method searches for one or more symbol sequence candidates, which are sequences of symbol candidates, by searching for symbol candidates in a certain region of a multi-dimensional lattice determined by a channel, and the lattice includes each symbol sequence. It has one dimension corresponding to a symbol, and the region is defined by a distance from the received signal, and the symbol sequence is decoded by selecting one or more candidate symbol sequences for the received signal. The symbol candidate search selects a candidate value of the transmitted symbol, and the lattice defined by the selected candidate is the The method comprising testing whether the inside of the boundary distance from Shin signal, said search includes functionality to stop after testing the candidate symbols of the limited number of times.

  According to the embodiment, the upper limit of the computation load is determined by terminating the symbol candidate test (and / or candidate distance determination) a limited number of times, and there is a risk that the decoding solution is lacking. And enables decoding of signals transmitted at a constant rate. Testing is to determine whether the selected candidate, or more precisely, the grid point or layer generated by the selected candidate is within the boundary distance from the received signal. In an embodiment, the candidate symbol test includes a test that determines whether the symbol is inside or outside the boundary distance, or whether the symbol is the last symbol in the estimated transmission sequence. Therefore, the number of cases in each of these three categories is counted and searching is stopped after reaching a predetermined limit count.

  In an embodiment, the (initial) boundary distance or radius will still have an effect on the decoding process if this affects the tree constructed by, for example, the planned number of candidate symbol tests. For this reason, the boundary distance or radius may be adaptively changed depending on, for example, noise or noise variance and / or channel response.

  The procedure tries to test the candidate values for each symbol in the column, but depending on the channel and the received signal, a complete tree with at least one complete set of candidate symbols for the column is not constructed at the end node of the tree It may be. When the search fails to locate a candidate symbol sequence, a linear, preferably zero-forcing estimate may be provided as the output of the decoding procedure. In addition, any linear estimation value such as successive interference suppression and MMSE solution may be adopted. In general, each symbol is defined by one or more bits, so a sequence of symbols defines a sequence of bits. Decoding may then include (or further include) providing a probability value for each bit of the bit string. When no candidate symbol sequence is located, the symbols estimated by zero forcing can be used to calculate the soft output of each such bit.

  Decoding may provide a hard output by selecting a minimum distance candidate for the symbol sequence as an output, or a plurality of symbol sequences with values related to probabilities, eg, grid points and received signals calibrated by the symbol sequence May provide a so-called soft output. In the search, a candidate for a symbol string that forms a lattice point in a region having a multidimensional lattice determined by the channel response is searched. The soft output may be calculated using all (probabilities) of candidate symbol sequences found by the search to avoid the need for reordering in practice. In general, each symbol is associated with one or more transmitted bits, and decoding is configured to output the probability of each bit calculated based on all (at least one) candidate symbol sequences found. It doesn't matter. The probability value of a bit is the likelihood for a bit having first and second logic levels based on the set of symbols (in the confirmed candidate sequence) where the bit has first and second logic values, respectively. May be determined by taking a ratio of values. Here, for any bit, if no symbol in the candidate sequence has such a value, or these values and such a ratio cannot be calculated, the default probability value of the bit may be different logic, for example. May be provided based on a minimum distance metric for the value or including a default maximum value such as 50.

  In the preferred embodiment, the search for candidate symbols is a distance from the zero-forcing estimate of the transmitted signal (or another linear or simple estimate to calculate), eg, determined from the received signal and channel response. Proceed to increase. This approach can be applied to the constellation reliability at the searched layer and / or at a certain layer (dimension) or tree node (eg, so that the search can start with a reliable symbol in the symbol sequence). You may make it select in order with high.

  The sequence of symbols is transmitted by multiple transmit antennas in a symbol transmitted from multiple users in a multi-user communication system or in a MIMO communication system (in each case a channel including a matrix / channel form) and A sequence of symbols received by two multiple receive antennas. In a MIMO communication system, a symbol sequence is a space-time block code (STBC) symbol, a space-time trellis code (STTC) symbol, a space-frequency code symbol, or a space-time / frequency code symbol. May include. The space-frequency coded signal is encoded across multiple frequency channels, for example in an OFDM (Orthogonal Frequency Division Multiplexing) system with multiple carriers, in which case the decoder comprises a serial-to-parallel converter and It may be preprocessed by a fast Fourier transformer, followed by an inverse Fourier transformer and a parallel-serial converter.

It will be appreciated that the method described above may be employed, for example, in a turbo decoder with interleaved block code decoding and channel decoding.
The invention further provides a decoder configured to implement the method described above, and a receiver including such a decoder.

  Accordingly, in a further aspect of the invention, a symbol generated by having one value among a plurality of values is encoded as a symbol string using a plurality of symbols, and then transmitted and decoded through a channel. A decoder is provided, and the decoder searches for one or more symbol sequence candidates that are sequences of symbol candidates by searching for candidate symbols in a region of a multidimensional lattice determined by a channel, The lattice has one dimension corresponding to each symbol of the symbol sequence, the region is defined by a distance from the received signal, and selects one or more symbol sequence candidates for the received signal. Decoding the symbol sequence, wherein the symbol candidate search selects a candidate value of the transmitted symbol and the selected candidate The method comprising testing whether more defined the grid is inside the boundary distance from the received signal, said search includes functionality to stop after testing the candidate symbols of the limited number of times.

In the above aspect of the invention, the multi-dimensional lattice may additionally or alternatively be determined by the adopted space-time code or other code at the transmitter.
In another related aspect, the invention provides a decoder that decodes a received signal that includes a sequence of symbols transmitted on a MIMO channel, where the decoder is a distance from the received signal in the received signal space of candidate symbols for the sequence. By searching for a transmitted symbol string candidate within the radius of the received signal, the sphere decoder that provides the decoded data output, and a distance determination circuit are counted and searched in response to the count A sphere decoder controller that controls the sphere decoder to stop it.

  Preferably, the decoder includes a symbol estimator that determines an initial estimate of the transmitted symbol, and the sphere decoder starts with the initial estimate and determines a grid point in the radius of the received signal by determining a distance metric. It may search for transmission symbol sequence candidates to be generated.

  One skilled in the art will recognize that the above-described methods and decoders are implemented using processor control code and / or embodied in processor control code. Thus, in a further aspect, the invention relates to a recording medium such as a disc, CD-ROM or DVD-ROM, or a programmed memory such as a read-only memory or an optical or electrical signal carrier. Provide such a code on a simple data carrier. Embodiments of the invention are implemented on a DSP (Digital Signal Processor), ASIC (Application Specific Integrated Circuit) or FPGA (Field Programmable Gate Array). Thus, the code includes conventional program code or code that sets or controls, for example, an ASIC or FPGA. In some embodiments, the code includes code relating to a hardware description language such as Verilog ™ or Very High Speed integrated circuit Hardware Description Language (VHDL). Those skilled in the art will appreciate that the processor control code for embodiments of the present invention may be distributed among a plurality of interconnected components.

  These and other aspects of the present invention will now be further described, by way of example only, with reference to the accompanying drawings.

  The embodiment of the invention solves the problem of the sphere decoding principle that the amount of computation is not uniquely determined, and in particular by limiting the number of searches performed to find possible candidates for transmission symbols, Set the upper limit of computational complexity. Moreover, embodiments of the invention provide a method for obtaining a soft output that approximates the likelihood for maximum a posteriori probability decoding even when sufficient signal candidates are not found. Embodiments of the invention are discussed with respect to space-time decoding or determination, but are not limited thereto.

Consider a space-time transmission scheme using n _T transmission signals and n _R reception signals (or equivalently, transmission and reception signals having n _T and n _R components, respectively). The 1 × n _R received signal vector at time k is:

例えば、トレーニング系列は各送信アンテナから順に送信され、（干渉問題を回避するため）送信アンテナから受信アンテナへのチャネルを特化するため全ての受信アンテナ上で受信を行う。これは大きな諸経費をかける必要がなく、データ伝送速度はトレーニングの間では高く、そして例えば、室内チャネルなど変動がゆるやかな場合、データ伝送速度はチャネルの変動に対して十分速く、トレーニングは例えば０．１秒毎に実行すれば十分である。その他、干渉問題が起こるのでトレーニングの複雑さを増大させるけれども、直交系列を全ての送信アンテナから同時に伝送してもよい。

For example, the training sequence is transmitted in order from each transmit antenna and receives on all receive antennas to specialize the channel from transmit antenna to receive antenna (to avoid interference problems). This does not require a large overhead, the data transmission rate is high during training, and if the fluctuations are slow, eg indoor channels, the data transmission rate is fast enough for channel fluctuations and the training is eg 0 It is sufficient to run every second. In addition, although an interference problem occurs and training complexity is increased, orthogonal sequences may be transmitted simultaneously from all transmitting antennas.

All linear space-time block coded transmission schemes can be written in the form of Equation 1.
For example, BLAST (GJ Foschini, “Layered space-time architecture for wireless communication in a fading environment when using multi-element antennas”, Bell Labs. Tech. J. vol. 1, no. 2, pp. 41- 59, 1996) use transmit antennas to transmit hierarchical signals, so n _T represents the number of transmit antennas, n _R represents the number of receive antennas,

他の例は直交系列（S．M．Alamouti、「A simple transmitter diversity scheme for wireless communications」） 、ＩＥＥＥ Ｊ．Ｓｅｌ．Ａｒｅａ Ｃｏｍｍ．pp.１４５１〜１４５８、Oct.１９９８；and V．Tarokh、H．Jafarkhani and A．R．Calderbank、「Space-time block codes from orthogonal designs」、IEEE Trans. Info. Theory., vol.４５、pp.１４５６〜１４６７、July １９９９）and linear dispersive codes B．Hassibi and B．Hochwald、「High-rate codes that are linear in space and time」、IEEE Trans. Info. Theory., vol.４８、pp.１８０４〜１８２４、Jul.２００２）を含み、

Other examples are orthogonal sequences (SM Alamouti, “A simple transmitter diversity scheme for wireless communications”), IEEE J. Sel. Area Comm. pp. 1451 to 1458, Oct. 1998; Tarokh, H.H. Jafarkhani and A. R. Calderbank, “Space-time block codes from orthogonal designs”, IEEE Trans. Info. Theory., Vol. 45, pp. 1456 to 1467, July 1999) and linear dispersive codes Hassibi and B. Hochwald, “High-rate codes that are linear in space and time”, IEEE Trans. Info. Theory., Vol. 48, pp. 1804-1824, Jul. 2002)

表記を簡略化するため、時間インデックスkを無視し、

To simplify the notation, ignore the time index k,

ｘ^ｎ＝［ｘ_１ ^ｎ ・・・ｘ_ｑ ^ｎ］ 式３
はｑビットの伝送データ・ビットを持つベクトルで、ｑはシンボル当たりのビットの数である。

x ⁿ = [x ₁ ⁿ ... x _q ⁿ ] Equation 3
Is a vector with q bits of transmitted data bits and q is the number of bits per symbol.

従って、伝送されるビットの（ｑ・ｎ_Ｔ）‐長のベクトルは

Therefore, the (q · n _T ) -length vector of transmitted bits is

ｎ＝１，・・・，ｎ_Ｔ ｊ＝１，・・・，ｑ
及びＬ_Ｅ（・）項は

n = 1,..., n _T j = 1,.
And L _E (

によって近似することができる。ここでｘは伝送される可能性のあるビットの系列であり、ｘ_{［ｎ，j］}はその要素ｘ_ｊ ^ｎを省略することによって得られたｘの部分ベクトルであり、そしてＬ_{Ａ，［ｎ，j］}はまたビットに対応する要素ｘ_ｊ ^ｎを省略して、全てのＬ_Ａ‐値のベクトルを示す；

Can be approximated by Where x is a sequence of bits that may be transmitted, x _{[n, j]} is a subvector of x obtained by omitting its element x _j ⁿ , and L _{A, [n , J]} also denotes a vector of all L _A ^-values , omitting the elements x _j ⁿ corresponding to the bits;

Ｘ_ｎ，ｊ ^＋１＝｛ｘ｜ｘ_ｊ ^ｎ＝＋１｝
及び
Ｘ_ｎ，ｊ ^−１＝｛ｘ｜ｘ_ｊ ^ｎ＝−１｝
である。
云換えれば、例えば式６の分子における和はビットｘ_ｊ ^ｎ＝＋１を持つ全てのシンボルに亘るものである。

^{_{X n, j +1 = {x}} | x j n = + 1}
And X _{n, j} ⁻¹ = {x | x _j ⁿ = −1}
It is.
In other words, for example, the sum in the numerator of Equation 6 is over all symbols with bits x _j ⁿ = + 1.

関数Ｌ_P（・）、Ｌ_Ａ（・）及びＬ_Ｅ（・）は事後、事前及び外部尤度をそれぞれ表す。事前尤度Ｌ_Ａ（・）は、例えば、チャネル符号器からの（例えば、反復ターボ復号における）事前入力から導かれるか、或いはゼロに設定もしくは初期化される（０のログ尤度比Ｌ（・）は＋１及び−１が同確率であることを意味する）。式６は最適の最大事後確率（ＭＡＰ）解であり、そして式７はＭＡＰ解の最大対数近似を提供する（しばしばmax-log‐ＭＡＰ解と呼ばれる）。発明の実施例は式６と式７の両方の解の近似を提供する事ができる。

The functions L _P (•), L _A (•) and L _E (•) represent the a posteriori, the a priori and the external likelihood, respectively. The prior likelihood L _A (•) is derived, for example, from a prior input from a channel encoder (eg, in iterative turbo decoding), or is set or initialized to zero (log likelihood ratio L (0) -) Means that +1 and -1 have the same probability). Equation 6 is the optimal maximum posterior probability (MAP) solution, and Equation 7 provides a maximum logarithmic approximation of the MAP solution (often called the max-log-MAP solution). Embodiments of the invention can provide approximations of the solutions of both Equation 6 and Equation 7.

ＡＰＰ判定の計算量はシンボル当たりのビットの数ｑ及び空間‐多重される送信シンボルの数ｎ_Ｔと共に指数的に増加する。式６を近似する１つの方法は集合Ｘ^＋１及びＸ^−１において

Computational complexity of APP determining the number q and space bits per symbol - exponentially increases with the number n _T of multiplexed is transmitted symbols. One way to approximate Equation 6 is in the sets X ^{+ 1} and X- ¹ .

である候補のみを含めることである。ここで式８ａは事前知識なしであり、式８ｂは事前知識によるものであり、ρはｓｐｈｅｒｅ復号器の限界半径である。
この近似は式８ａ及び８ｂによって定義された範囲外の距離メトリックを提供する候補がＡＰＰ判定への大きな寄与をしないことを仮定している（式６参照）。ｓｐｈｅｒｅ復号アルゴリズムは式８ａか８ｂのいずれかを満たす候補のリストを素早く見出す処理手順を提供する。

Is to include only those candidates. Here, Equation 8a is without prior knowledge, Equation 8b is with prior knowledge, and ρ is the limit radius of the sphere decoder.
This approximation assumes that candidates that provide distance metrics outside the range defined by Equations 8a and 8b do not make a significant contribution to the APP decision (see Equation 6). The sphere decoding algorithm provides a procedure for quickly finding a list of candidates that satisfy either of the equations 8a or 8b.

  The original sphere decoder, also known as the lattice decoder (Viterbo and Boutros, ibid.), Provides maximum likelihood estimation, which is a hard output of transmission symbols for real constellations and channels, representing the communication system as a lattice. Here, based on this original idea, we describe a specific embodiment of a soft input / soft output sphere decoder suitable for a multiple antenna system.

To obtain a grid representation of a multi-antenna system, the complex matrix representation of Equation 1 (ignoring the time index k) can be changed to a real matrix representation with twice the dimensions of the original system as follows:
r = sH + v Equation 9
here

我々はｓｐｈｅｒｅ復号器の以下の記述で式９乃至式13の実数表現を使用する。格子理論において使用される専門用語法を使用すると、チャネルＨの実数表現は格子の生成行列であり、チャネル入力（伝送信号）ｓは格子の入力点であり、そして雑音のないチャネル出力項ｓＨは格子点を定義する。

We use the real representation of Equations 9 through 13 in the following description of the sphere decoder. Using the terminology used in lattice theory, the real representation of channel H is the generator matrix of the lattice, the channel input (transmission signal) s is the input point of the lattice, and the channel output term sH without noise is Define grid points.

  An n-dimensional lattice can be decomposed into (n-1) -dimensional lattice layers. An n-dimensional lattice search algorithm can be recursively described as a finite number of (n-1) -dimensional search algorithms. Viterbo and Boutros (ibid) described the search algorithm for three different states, or cases of search:

チャネル行列のＱＲ分解またはコレスキー分解（時折、行列の平方根を取ることを意味する）から導かれる下三角行列Ｕ^Ｔが格子のための生成行列として使用されれば、探索処理手順は単純化される。例えば、ＱＲ分解が使用されれば（例えば、G．H．Golub and C．F．von Loan、「Matrix Computations」、John Hopkins University Press, １９８３、参照）、下三角行列Ｕ^Ｔ（及び上三角のＵ）は次のように定義される：
Ｕ^ＴＵ＝Ｈ^ＴＨ 式１４

QR decomposition or Cholesky decomposition of the channel matrix if the lower triangular matrix U ^T derived from (occasionally refers to taking the square root of the matrix) is used as a generator matrix for the lattice, the search procedure is simplified The For example, if QR decomposition is used (see, eg, GH Golub and C. F. von Loan, “Matrix Computations”, John Hopkins University Press, 1983), the lower triangular matrix U ^T (and the upper triangular U) is defined as:
U ^T U = H ^T H Formula 14

さらに探索アルゴリズムによって使用される距離メトリックについて説明するため、我々は生成行列が下三角行列であることをここで仮定する。

To further explain the distance metric used by the search algorithm, we now assume that the generator matrix is a lower triangular matrix.

ｎ＋１次元目の格子探索において距離メトリックは見出されたｎ＋１番目の伝送シンボルによって異なるので、ｎ‐次元目の格子探索において使用される範囲は次のように更新される：
ρ_ｎ ^２＝ρ_ｎ＋１ ^２−ｄ_ｎ ^２ 式１７
探索アルゴリズムで使用される距離メトリックを述べてきたので、探索される集団シンボルの順序付けについて以下に説明する。距離メトリックは（今、実数値表現を使用して）次のように書くことができる：

Since the distance metric in the n + 1 dimensional lattice search depends on the n + 1 th transmission symbol found, the range used in the n-dimensional lattice search is updated as follows:
_{^{ρ n 2 = ρ n + 1}} 2 -d n 2 Equation 17
Having described the distance metrics used in the search algorithm, the ordering of the collective symbols to be searched will be described below. The distance metric can now be written as follows (using a real-valued representation):

但し、

However,

は伝送シンボルｓの非制約最尤推定値で、またゼロフォーシング解として知られている。従って、式８で与えられた範囲を次のように再定義することができる：

Is an unconstrained maximum likelihood estimate of the transmission symbol s, also known as a zero forcing solution. Thus, the range given by Equation 8 can be redefined as follows:

例えば、シンボル集団が４ＰＡＭ（Pulse Amplitude Modulation）、即ち、Ｃ_ｒｅａｌ＝｛−３，−１，＋１，＋３｝で、且つｎ番目のレベル探索におけるゼロフォーシング解がｓ”^ｎ＝−１．１であれば、探索されるべきシンボルは｛−１，−３，＋１，＋３｝として順序付けされる。この結果、探索上限及び下限の明らかに必要のない計算を回避する事ができる。

For example, the symbol group is 4PAM (Pulse Amplitude Modulation), that is, C _real = {− 3, −1, + 1, + 3}, and the zero forcing solution in the nth level search is s ″ ⁿ = −1.1. If so, the symbols to be searched are ordered as {-1, -3, +1, +3}, thus avoiding calculations that clearly do not require the search upper and lower limits.

そして、探索は次の探索階層またはレベルに進む。順序付けは全ての可能な組合せを記憶する索引表を参照する事によって実現することができる。例えば、ｃ×Ｍ行列Φ（但し、ｃ＝２Ｍはシンボル探索組合せの数で、Ｍは可能な信号点の数である）が与えられと、ゼロフォーシング解ｓ"^ｎに関する並べ替えベクトル slist はΦのｉ番目の行として次のように与えられる ：

The search then proceeds to the next search hierarchy or level. Ordering can be achieved by referencing an index table that stores all possible combinations. For example, given a c × M matrix Φ, where c = 2M is the number of symbol search combinations and M is the number of possible signal points, the permutation vector slist for the zero forcing solution s ″ ⁿ is Φ Is given as the i-th row of:

広い意味では、この技術はAgrell等（同書）で述べられたSchnorr-Euchner戦略の修正版を含む。
索引表を用いて探索されるシンボルを順序付けする方法は、A．Wiesel、X．Mestre、A．Pages and J．R．Fonollosa、「Efficient Implementation of Sphere Demodulation」、ＩＶ ＩＥＥＥ Signal Processing Advances in Wireless Communications、pp.５３５、Rome、June15-18,２００３、にさらに詳細に記述され、これによって引用文献として組込まれている。

In a broad sense, this technique includes a modified version of the Schnorr-Euchner strategy described by Agrell et al.
A method for ordering symbols to be searched using an index table is as follows. Wiesel, X. Mestre, A. Pages and J. R. Fonollosa, “Efficient Implementation of Sphere Demodulation”, IV IEEE Signal Processing Advances in Wireless Communications, pp. 535, Rome, June 15-18, 2003, which is hereby incorporated by reference.

探索半径は雑音及び／またはチャネル状態に応じて設定することができる。軟出力が必要とされるところでは、下で述べられるように、並べ替えアルゴリズムの複雑さが加わることを回避するために、見出された全てのシンボルが軟出力評価に利用される。

The search radius can be set according to noise and / or channel conditions. Where soft output is required, all symbols found are used for soft output evaluation to avoid adding the complexity of the reordering algorithm, as described below.

In short, the processing procedure includes three main processes:
i) Conversion of multiple-input multiple-output (MIMO) channel to lattice representation.
ii) A search processing procedure for searching for a lattice point closest to the received signal in the case of a hard decision and searching for a set of lattice points around the received signal in the case of a soft decision. Where soft input is available, given a prior probability of the transmitted signal or codeword, this can be used to aid the search (see also, for example, H. Vikalo and B. Hassibi, “ Low-Complexity Iterative Detection and Decoding of Multi-Antenna Systems Employing Channel and Space-Time Codes, Conference Record of the Thirty-Sixth Asilomar Conference on Signals, Systems and Computers, vol.1, Nov. 3-6, 2002, pp 294-298, and H. Vikalo and B. Hassibi, “Towards Closing the Capacity Gap on Multiple Antenna Channels”, ICASSP '02, vol. 3, pp. III-2385 to III-2388).
iii) Where soft output is required, provide soft output based on the soft input and the set of grid points found in the search area (this is unnecessary for hard decision sphere decoders).

As previously mentioned, known sphere decoders suffer from variable complexity depending on the statistical properties of the channel and the type of space-time code used, but the complexity is not bounded by boundaries And it is not uniquely determined. However, since the many distance metric d _n calculations required for the search determine the actual complexity, we now set or limit the maximum number of searches performed to allow the sphere decoder to Limit the amount of computation.

A flowchart of a sphere decoder that performs such a procedure is shown in FIG. In FIG. 3, based on the normal sphere decoding procedure with modifications, the generator matrix of the lattice H (F = H ⁻¹ , where F is a triangular matrix) is the lattice representation of the communication system and the received signal is r (Preprocessed in the same way as the generator matrix for the search procedure). The output of the procedure is s _ML , symbollist and distlist. The output _sML is a lattice input (transmitted signal) corresponding to the lattice point closest to the received signal r, and is the maximum likelihood solution. The output symbollist is a list of grid inputs corresponding to the grid points found in the search area. The output distlist is a list of distance metrics corresponding to the grid inputs in symbollist.

The search area is defined by the search radius ρ ² . The function SortedList (e _{n, n} ) provides an ordered list of possible symbols to be searched according to increasing distance from the signal e _{n, n} . Therefore, slist _n is a vector of length M (since slist is an N × M matrix), and step _n has a count of 1 to M. The notation slist _{n, I} refers to the I-th element of the vector slist _n . The zero forcing solution in the nth dimension search is given by e _n : = rF. The unknown number (the length of the sequence of symbols to be estimated) is N (noting that I and Q components should be estimated, there are two unknowns per symbol, so the unknown doubles ), The number of possible symbols searched (in the constellation) is M.

There are three cases A, B, and C as described above; generally the procedure initializes n = N and until all are tested (all symbols in slist _n are tested in the nth dimension search) (Examined_all becomes true) Tests symbols in slist order, moves up one level when outside the search radius ρ ² (case C), and returns to the top of the tree (n == N) When finished. The total number of tested cases (A, B or C) were tested, i.e., the number of the determined distance metrics d _n is counted by the variable N_searched (initialized to zero at the start), the procedure limits max_n_searched Stop when you exceed.

  This is summarized in Figure 4, which divides the search procedure into three different processing blocks according to different states or cases for the search (see Table 1), according to cases A, B or C as confirmed by the data multiplexer. , Multiplex data into process A, B or C. The count is maintained during each iteration of the loop (or each multiplexing operation) and the procedure is stopped when a limited value is reached. The limit may be preset or selected according to the application or data transmission rate. Each processing block (A, B, C) evaluates the distance metric of the grid point, or which hierarchy is currently being processed, evaluates the state of the search, and next grid point to be searched (Or layer). Data flows and processing blocks are selected according to conditions or cases that define the state of the search. Therefore, the maximum number of search “iterations” can be the value required to implement a discriminator, the maximum number of valid (eg, predetermined) flops (floating point operations per second), speed or data throughput. Set according to (Data bits per second). By limiting the number of searches, the computational amount of the sphere decoder is thereby set to an upper limit.

  In general, in an embodiment of the invention, the sphere decoder has a maximum complexity bounded or limited by defining the maximum number of searches performed by the sphere decoding procedure. This provides the stability of the procedure to be defined according to the transmission rate and throughput of data expected for or from the application, or a predetermined amount of computation (or flop).

Additional features of the preferred sphere decoder configuration are described below. One or more of these may be performed separately in a normal decoder, otherwise in conjunction with the above search limiting procedure.
If no candidate is found, that is, a data symbol or code is found in the search area for a predetermined maximum number of points to be tested or searched (or for a predetermined size of the search area) If it is not an n-dimensional grid point, a zero forcing solution (or another linear solution such as an MMSE solution) may be provided as an estimated n-dimensional transmission sequence symbol or codeword. The zero forcing solution may be obtained by a first search or may be a zero forcing solution re-estimated in each search hierarchy where the effect of previously discovered symbols is offset. In this latter case, “cancellation” may be performed in the order of “strongest” signal to “weakest” signal. This ordered zero-forcing solution may be obtained by preprocessing the grid generator matrix using a QR permutation with column permutation (eg D. Wubben, R. Bohnke, J. Rinas, V. Kuhn and KDKammeyer “Efficient algorithm for decoding layered space-time codes” IEEE Electronics Letters, vol. 37, pp. 1348-1350, incorporated herein by reference). The choice of zero forcing solution may be chosen depending on the entire application.

  Soft output information may be obtained from the zero forcing solution s "(or another linear solution) shown below in Equation 23 or 24.

または、Ｍａｘ-Ｌｏｇ-ＭＡＰ近似を使用して:

Or using the Max-Log-MAP approximation:

ここに、s”ⁿは式19で与えられるゼロフォーシングベクトルのn番目の要素であり、sはqビット長のビットベクトルxⁿから写像するシンボル、すなわち、sⁿ=map（xⁿ）である。組Y⁺¹ _n,jおよびY^-1 _n,jはそれぞれxⁿ _j=+1およびxⁿ _j=-1を有するビットベクトルxⁿの２^(q-1)通りの集合である。硬判定において、ゼロフォーシングベクトルs”が出力として提供されるかもしれない。

Here, s ” ⁿ is the nth element of the zero forcing vector given by Equation 19, and s is a symbol mapped from the bit vector x ⁿ of q-bit length, that is, s ⁿ = map (x ⁿ ) The sets Y ⁺¹ _{n, j} and Y ⁻¹ _{n, j} are 2 ^(q−1) different sets of bit vectors x ⁿ with x ⁿ _j = + 1 and x ⁿ _j = −1, respectively. In the determination, a zero forcing vector s ″ may be provided as an output.

シンボル列の少なくとも１つの候補が発見されるところでは、次にビット尤度値(例えば対数尤度比、ＬＬＲ、値)によって構成される軟出力が以下の式27を使用して決定されてもよい。事実上、与えられたビットが+1と-1の値を持っている複数の候補シンボル列上(発見されたところで)で平均されることにより、ビット値が決定されるので、最も尤度が高いビット値が最も尤度が高いシンボル列におけるシンボルに対応するというわけではないことが認識されるであろう。与えられたビットが、式27において分子(または、分母)あるいはゼロに対応している、+1(または、-1)の値を持って発見されるどんな候補列もないとき、このアプローチに困難があることが認識されるであろう。この困難は以下で説明されるように処理することができる。

Where at least one candidate symbol sequence is found, a soft output composed of bit likelihood values (eg, log likelihood ratio, LLR, value) can then be determined using Equation 27 below: Good. In fact, the bit value is determined by averaging over a number of candidate symbol sequences (where found) where the given bit has values of +1 and -1. It will be appreciated that high bit values do not correspond to symbols in the most likely symbol sequence. This approach is difficult when there is no candidate sequence found with a value of +1 (or -1) that corresponds to the numerator (or denominator) or zero in Equation 27 in Equation 27 It will be recognized that there is. This difficulty can be dealt with as described below.

The case where each bit x ⁿ _j = + 1 and x ⁿ _j = list of any which corresponds to the candidate containing -1 L ⁺¹ or L ^-1 is found empty, the default LLR value other non Given according to the number of symbols found in the empty list and / or its distance metric. For example, if L ⁻¹ is empty and the minimum distance metric found in the list L ⁺¹ is d ² _min , then the incidental LLR is approximated as follows:

代わりに、非空リストが候補のかなり大きい数(即ち閾値数よりも大きい)を持っていて、発見されていない候補が大きい距離メトリックを有すると仮定されるならば(探索の距離メトリックの最大許容数が計算してあるので)、デフォルト最大ＬＬＲ値L_MAXが提供されるかもしれない。例えば、

Instead, if the non-empty list has a fairly large number of candidates (i.e. greater than the threshold number) and it is assumed that the undiscovered candidates have a large distance metric (the maximum allowed distance metric for search) Since the number has been calculated), a default maximum LLR value L _MAX may be provided. For example,

硬判定の場合では、デフォルトＬＬＲ値は式26でL_MAX=１と決定されるかもしれない。デフォルトＬＬＲ値がいかに評価されるのかの選択は総合的なシステム設計に依存する。
我々は次に探索戦略を説明する。式8に示されるように、受信信号または出力空間でｓｐｈｅｒｅ半径によって定義される特定の球体探索領域に関して、伝送信号または入力空間に対応する探索規制がある。発明の実施例では、探索規制の下限および上限の明白な計算は、第n次元における第１の探索層が入力空間のゼロフォーシング解の第n要素であるように探索される層を順序付けることにより回避される。その後の探索は、探索されるべき層の順序が入力空間のゼロフォーシング解から距離を増加するようにするのが望ましい。探索される第n次元層が受信信号に関してｓｐｈｅｒｅ半径より大きい累積距離メトリックを有するとき、探索された第n層は現在の探索階層構造の入力境界と考えられ、格子探索は次の探索階層構造で実行される。

In the case of a hard decision, the default LLR value may be determined by Equation 26 as L _MAX = 1. The choice of how the default LLR value is evaluated depends on the overall system design.
We next explain the search strategy. As shown in Equation 8, for a particular sphere search region defined by the sphere radius in the received signal or output space, there is a search constraint corresponding to the transmitted signal or input space. In an embodiment of the invention, the explicit calculation of the lower and upper limits of the search restriction orders the layers searched so that the first search layer in the nth dimension is the nth element of the zero-forcing solution in the input space. Is avoided by Subsequent searches are preferably such that the order of layers to be searched increases the distance from the zero-forcing solution in the input space. When the searched nth dimension layer has a cumulative distance metric with respect to the received signal that is greater than the sphere radius, the searched nth layer is considered the input boundary of the current search hierarchy, and the lattice search is the next search hierarchy Executed.

Turning now to bit probability values, the distance metric obtained from the search procedure of the sphere decoder may be passed to the soft output information computation block that provides the soft output from the decoder. Recalling Equation 6 again, the soft output for the a posteriori LLR of the decoded or detected bits x ⁿ _j subject to the received channel vector r can be estimated as follows:

ここに、sはビットベクトルxの空間-時間シンボルであり、HはＭＩＭＯチャネル行列であり、項σ²は実成分あたりの雑音分散であり、L⁺¹はビットxⁿ _j=+1を含んでいる要素に対して探索手順で発見されたシンボルのリストに対応するビットベクトルxの集合であり、x_[n,j]はビットxⁿ _jを省略することにより得られるxのサブベクトルを表し、L_A,[n,j]はまたxⁿ _jのＬＬＲを表す要素を省略してすべての事前ＬＬＲL_Aのベクトルを表す。

Where s is the space-time symbol of bit vector x, H is the MIMO channel matrix, term σ ² is the noise variance per real component, and L ⁺¹ contains bits x ⁿ _j = + 1 Is a set of bit vectors x corresponding to the list of symbols found in the search procedure for the elements that are, and x _{[n, j]} represents a subvector of x obtained by omitting bits x ⁿ _j , L _{A, [n, j]} also represents all the prior LLLR _A vectors, omitting elements representing the LLR of x ⁿ _j .

  The noise variance may be obtained in any convenient way, depending on the overall system design. For example, noise variance may be obtained during the training period where the channel impulse response is estimated. During the training period, the transmission symbol sequence is known. A “no-noise” received signal is obtained with an estimated channel impulse response. Noise variance may be estimated from evaluating the noise statistic of the sequence of signals received during the “training period”, knowing the sequence of received signals “no noise”.

The term d _x ² is a distance metric obtained from the search algorithm corresponding to the symbol s obtained from the space-time symbol mapping of the bit vector x. The prior LLRL _A may be obtained from a soft input to the sphere decoder. Section L _E is an external LLR. The pre-LLLR _A is obtained from an external component such as a channel decoder or another space-time decoder. The prior LLRL _A may also be an outer LLRL _E from the previous iteration decoding if an iterative decoding structure is employed. Whether the soft output is provided after the fact or from an external LLR depends on the application.

The logarithm of the sum in Equation 27 is known as the conventional Jacobian logarithmic relationship (also known as the “sam-log” approximation (eg, P. Robertson, E. Villebrun and P. Hoher, “A comparison of optimal and sub-optimal MAP decoding algorithm operating in the log domain ”), in IEEE Intern. Conf. On Commun. 1995 pp. 1009-1013), or“ maximum-log ”approximation. As previously discussed, one or both of the lists L ⁺¹ and L ^-1 are found to be empty, or any symbol corresponds to x ⁿ _j = + 1 and / or x ⁿ _j = -1. For cases where no default is found, the default LLR value may be given according to the number of symbols found in other non-empty lists. If both lists are empty, a normal LLR value based on the soft output of the soft zero forcing solution may be provided.

Equations 27 and 23 correspond to the occupancy of lists L ^{+ 1} and L- ¹ (i.e., the number of candidate solutions found (grid points) having a given bit value of + 1 / -1). The selection of the output from the decoder based on / 24 or Equation 25/26 is summarized in the flowchart of FIG.
As shown in Fig. 5, this is reached before the sphere decoding algorithm is known to have reached the closest lattice point for the received signal (we have for example completed the (partial) tree described above. If the sphere decoding algorithm is stopped, the closest point found so far may or may not be the closest in fact. This is the left branch of the decision box in FIG. In this case, there is an alternative to what is shown in FIG. 5, which uses a zero forcing (ZF) solution, or a less complex linear determiner to determine the solution, such as using default values. is there.

  As described above, the reliability of the soft output obtained from the candidate where the sphere radius defining the range of the search area is found or the lattice point close to the received signal is determined. The sphere radius can be set to a fixed value to obtain a list of grid point candidates that contribute significantly to the APP detection shown in FIG. 6, or the sphere radius can be adjusted, eg, in response to reception conditions. it can. However, for hard decision output, the sphere radius may be reduced to the distance between the last found grid point and the received signal.

FIG. 6 shows a receiver 300 incorporating a decoder configured to implement an embodiment of the processing procedure of the method described above.
The receiver 300 includes one or more receive antennas 302a, b (two of which are shown in the illustrated embodiment), each connected to a respective RF front end 304a, b, From there, they are connected to respective analog-to-digital converters 306a, b and a digital signal processor (DSP) 308. The DSP 308 will typically include one or more processors 308a and working memory 308b. The DSP 308 has a data output 310 and an address, data and control bus 312 that connects the DSP to a permanent program memory 314 such as flash RAM or ROM. Permanent program memory 314 stores code and optionally data structures or data structure definitions for DSP 308.

  As illustrated, program memory 314 performs lattice generation code (from matrix channel estimates), zero-forcing estimation code, tree-forming / search code, iteration when performing implementations corresponding to the functions described above in DSP 308. It includes a restriction code and a sphere decoder code 314a that includes a soft information evaluation code for the soft output decoder. The program memory 314 also includes a MIMO channel estimation code 314b that provides a MIMO channel estimate H, and optionally a deinterleaver code 314c, an interleaver code 314d, and a channel decoder code 314e. The implementation of deinterleaver code, interleaver code, and channel decoder code is well known to those skilled in the art. Optionally, code in permanent program memory 314 is provided on an optical or electrical signal carrier or carrier such as a floppy disk 316 as illustrated in FIG.

Data output 310 from DSP 308 is further provided to data processing elements of receiver 300 (not shown in FIG. 6) as desired. These are baseband data processors for implementing high level protocols.
The receiver front-end is typically implemented in hardware, while one or more ASICs and / or FPGAs are also used, but the receiver processing is at least partially implemented in software. Those skilled in the art will recognize that all functions of the receiver can be performed in hardware, and that the exact scoring criteria by which signals are digitized in software defined radios is generally determined by cost / complexity / power consumption choices. Will do.

In other embodiments, the decoder is provided as a signal processing module that implements, for example, a soft input / soft output space-time decoder.
In summary, embodiments of the invention define the maximum number of iterations in the data flow as shown in FIGS. 3 and 4, i.e., the number of searches performed to locate possible transmission symbol candidates. By limiting, a method with an upper limit of calculation amount is implemented. The search algorithm can be broken down into three partial processes (or processing blocks) that are associated with three different cases or search states. Each processing block evaluates the distance metric of the grid point or which hierarchy is executing the process, evaluates the state of the search, and selects the next grid point or layer to be searched. Data flows and processing blocks are selected according to conditions or cases that define the state of the search (see Table 1). A linear solution, such as a zero forcing solution, when no grid points are found by the search procedure reaching the maximum number of iterations / searches (no enough candidates are found), or when there are no grid points within the search boundary. May be provided as default decision symbols or codewords. Because of the soft decision, a soft output is obtained from the soft output of the soft zero forcing solution. For cases where one of the lists L ^{+ 1} and L- ¹ is found to be empty, a default LLR value is provided, for example according to the number of symbols found in other non-empty lists and / or their distance metrics The Where both of these lists are in the population, one or more stored distance metrics of the grid points found in the search region are passed to the process of evaluating the soft output bit probability.

FIG. 7 shows a block diagram of a transmitter with a concatenated channel encoder; the frequency selective channel can be considered an “encoder”. In FIG. 7, encoder 2 includes a conventional channel encoder, and encoder 1 is an STBC encoder combined with a channel.
FIG. 8 shows a block diagram of a receiver with a concatenated channel decoder and a determiner suitable for use with the transmitter of FIG. In FIG. 8, the determiner or decoder 1 includes the space-time sphere decoder described above, and the decoder 2 includes a conventional channel decoder. FIG. 9 shows a modified block diagram of the receiver of FIG. 8 with a concatenated decoder or determiner using iterative or “turbo” decoding. FIG. 10 shows a block diagram of a receiver including two cases of decoder 1, which includes, for example, a space-time decoder. In FIG. 10, the output of one decoder provides prior knowledge about the other decoder. In this way, the decoder component repeatedly and effectively exchanges soft information with itself to improve the reliability of the decision data. The received signal is provided to both decoders and is optionally interleaved (depending on the interleaving arrangement of the transmitter) in one case.

FIG. 11 shows coded and uncoded BER (bit error rate) versus signal-to-noise ratio (dB) per receive antenna for a 4 × 4 16QAM (Quadrature Amplitude Modulation) MIMO system, and uncorrelated flat Rayleigh fading (Rayleigh -faded) Repeated computations in various circuits as described above for uncoded (curves 800, 802, 804, 806) and coded (curves 801, 803, 805, 807) transmission signals under channel conditions The characteristics of the sphere decoder (curves 802 to 807) and the maximum likelihood (ML) detector (curves 800 and 801) are shown. The result is obtained by simulation of 500 data blocks, and the sphere decoder is limited to 250 (curves 802, 803), 500 (curves 804, 805), and 1000 (curves 806, 807) distance metric calculations, respectively. Yes. The squared sphere radius value was equal to:
5 x (Noise variance) x (Number of receiving antennas) / (Average signal power per transmitting antenna)
The ML determiner requires measurement of 8 × 16 ⁴ = 524288 distance metrics per received symbol, so that a sphere decoder performing 250, 500, and 1000 calculations is at least approximately 1/2000, 1/1000 and The calculation amount is reduced to 1/500.

  The technique described above can be applied to what we have called a max-log-MAPsphere decoder. It is a UK patent application no. No. 0323211.3, filed Oct. 3, 2003 (and also the corresponding application claiming priority from this UK application), the contents of which specifically provide limitations on the sphere decoder evaluation of Equation 11 of that document , All of which are incorporated herein by reference.

  Embodiments of the invention have many types of communication system applications including, for example, MIMO and multi-user systems for wireless computer or telephone networks. In multi-user systems, for example, a generator matrix, or equivalent channel matrix, represents a combination of spreading and channel effects for the user (eg, L. Brunel, “Optimum Multiuser Detection for MC-, incorporated herein by reference). CDMA Systems Using Sphere Decoding ", 12th IEEE International Symposium on Personal, Indoor and Mobile Radio Communications, volume 1, 30 Sept.-3 Oct. 2001 pages A16-A20).

  In some applications, the decoder can be used as a block equalizer for frequency selective fading. Here, the channel model in Equation 9 is modified to take into account channel memory as shown below:

及びＴは等化されるシンボル・ブロックの長さ、Ｈ_ｉ，ｉ＝１，・・・，Ｌはｉ番目のＭＩＭＯチャネル・タップであり、ここにLはチャネルインパルス応答(シンボル期間における)の最大長さの推定値である。

And T is the length of the symbol block to be equalized, H _i , i = 1,..., L is the i th MIMO channel tap, where L is the channel impulse response (in the symbol period) This is an estimate of the maximum length.

本発明の実施例はチャネル符号器が線形生成行列Ｇによって表されるところでチャネル復号器として適用することができる。その例は、符号語ｘがｘ＝ｓＧを通して情報ビットｓから生成行列Ｇによって生成され、ベクトルｓが情報ビットを含むところのハミング符号（Hamming code）及び低密度パリティ検査（Low Density Parity Check：ＬＤＰＣ）符号化といったブロックチャネル符号である（「Digital Communications: Fundamentals and Applications、Bernard Sklar、Prentice Hall International Editions、１９９９、０‐１３‐２１２７１３‐Ｘ」、参照）。ＬＤＰＣについて、例えば、生成行列Ｇは直交条件ＧＨ^Ｔ＝０を満たすパリティ検査行列Ｈから得られ、或る正当な符号語はｘＨ^Ｔ＝０を満足させるであろう。ここで、情報及び符号語ブロック、ｓ及びｘ、それぞれは２進数、即ち１及び０から成り、行列演算は２値領域にある。

Embodiments of the present invention can be applied as channel decoders where the channel encoder is represented by a linear generator matrix G. An example of this is that a codeword x is generated from a generator matrix G from information bits s through x = sG, and a Hamming code and Low Density Parity Check (LDPC) where the vector s contains information bits. ) Coding, which is a block channel code (see “Digital Communications: Fundamentals and Applications, Bernard Sklar, Prentice Hall International Editions, 1999, 0-13-212713-X”). For LDPC, for example, the generator matrix G is derived from a parity check matrix H that satisfies the orthogonal condition GH ^T = 0, and some valid codeword will satisfy xH ^T = 0. Here, the information and codeword blocks, s and x, each consist of binary numbers, ie 1 and 0, and the matrix operation is in the binary domain.

  Embodiments of the invention provide maximum likelihood codewords or soft outputs based on Equation 7. In an exemplary embodiment, a sphere decoder using input r and using G as a generator matrix determines the distance between received signal r and each of the possible transmission codewords in the search. The codeword with the smallest distance is the maximum likelihood codeword. This employs the translation of information and codeword blocks from the binary field {0, 1} to the encoded value {-1, +1}, so mathematical operations are used.

In general, the above embodiment of the sphere decoding technique can be applied to any system that can be represented by a (preferably linear) generator matrix.
Those skilled in the art will recognize that the above-described techniques may be used, for example, in base stations, access points and / or mobile terminals. In general, embodiments of the invention facilitate an inexpensive receiver without loss of performance, or a corresponding increase in data transmission rate without increasing complexity and cost. Embodiments of the invention may also find potential application in non-wireless systems, eg, disk drives having multiple read heads and multiple data recording layers that operate like a multiple transmitter in nature.

  Of course, many other effective options will occur to those skilled in the art. It will be understood that the invention is not limited to the described embodiments, but includes modifications apparent to those skilled in the art which are within the spirit and scope of the claims appended hereto.

2 shows an example of a MIMO space-time coded communication system using a sphere decoder. Figure 2 shows an illustrative example of a tree search for a sphere decoder. FIG. 6 is a flowchart of a sphere decoding procedure embodying aspects of the present invention. FIG. 4 is an overview diagram of the procedure of FIG. 3. 6 shows a flowchart of a sphere decoding post-processing procedure according to an embodiment of an aspect of the present invention. FIG. 4 illustrates a receiver incorporating a sphere decoder configured to operate in accordance with an embodiment of the present invention. 1 shows a block diagram of a transmitter using a concatenated encoder. FIG. 8 shows a block diagram of a receiver having a concatenated decoder for use with the transmitter of FIG. FIG. 8 shows a block diagram of a receiver with concatenated decoder and iterative decoding for use with the transmitter of FIG. FIG. 4 shows a block diagram of a receiver employing iterative feedback between two equivalent decoders. The bit error rate relative to the received signal-to-noise ratio compared to the maximum a posteriori probability (MAP) for decoding the embodiment of the decoder according to the invention with or without a channel code Indicates.

Claims (18)

A method for decoding a signal generated by having one value among a plurality of values encoded as a symbol string using a plurality of symbols and received through a channel,
By searching for candidate symbols in a certain region of the multidimensional lattice determined by the channel, one or more candidate symbol sequences are searched, and the lattice corresponds to each symbol in the symbol sequence. And the region is defined by a distance from the received signal,
Decoding the symbol sequence by selecting one or more candidate symbol sequences for the received signal;
The symbol candidate search includes selecting a candidate value of the transmitted symbol and testing whether the grid defined by the selected candidate is within a boundary distance from the received signal. ,
A signal decoding method comprising a function of stopping the search after testing a limited number of candidate symbols.   The candidate symbol test includes a first category in which the portion of the grid determined by a symbol is inside the boundary distance, a second portion in which the portion of the lattice determined by a symbol is outside the boundary distance. And a test to determine which of the three categories of the third category is the last symbol of the estimated symbol sequence and to which the candidate symbol belongs. Method.   3. The method according to claim 1, further comprising a function of outputting a linear estimation result of the transmission symbol sequence when the decoding fails to determine the symbol sequence candidate.   4. The method of claim 3, wherein the linear estimate is a zero forcing estimate.   Each symbol of the symbol sequence includes one or more bits, and the decoding provides a soft output that includes a likelihood value for each bit of each symbol of the symbol sequence, and a method further includes: 5. A method according to claim 3 or 4, comprising determining a likelihood value of.   The decoding provides a soft output determined in response to a distance metric for a selected one of the symbol string candidates, the distance metric depending on the distance between the received signal and the symbol string candidates. The method according to claim 1 or 2.   7. The method of claim 6, wherein the soft output is determined in response to a distance metric of all the symbol string candidates found by the search.   3. The symbols further comprising: each symbol having one or more bits, whereby the symbol sequence defines a sequence of bits, and the decoding further provides a probability value for each bit of the sequence of bits. 8. The method according to any one of 6 and 7.   The probability value of the bit includes a first set of one or more candidate symbol sequences in which the bit has a first logical value, and a second logical value in which the bit is different from the first logical value. Determined by using a second set of one or more symbol sequence candidates and taking a ratio of the first and second likelihood values determined using the first and second sets of symbols 9. The method of claim 8, further comprising providing a default probability value for the bit when one of the first and second sets is empty.   10. A method according to any one of the preceding claims, wherein the search for candidate symbols proceeds to increase the distance from the initial estimate.   11. The method of claim 1, wherein the sequence of symbols is transmitted on a MIMO (Multiple Input Multiple Output) channel using multiple transmit antennas, and the received signal is received by multiple receive antennas. The method described in 1.   12. A method according to any one of the preceding claims, wherein the signal is encoded using a space-time block code.   A processor control code that, when activated, implements the method of any one of claims 1-12.   A carrier carrying the processor control code of claim 13. A decoder that decodes a signal that is transmitted after being encoded as a symbol string using a plurality of symbols and having been generated through having one value among a plurality of values and received through a channel,
By searching for candidate symbols in a certain region of the multidimensional lattice determined by the channel, one or more candidate symbol sequences are searched, and the lattice corresponds to each symbol in the symbol sequence. And the region is defined by a distance from the received signal,
Decoding the symbol sequence by selecting one or more candidate symbol sequences for the received signal;
The symbol candidate search includes selecting a candidate value of the transmitted symbol and testing whether the lattice defined by the selected candidate is within a boundary distance from the received signal. A decoder having a function of stopping the search after testing a limited number of candidate symbols.   16. A receiver comprising the decoder of claim 15. A decoder for decoding a received signal including a symbol sequence transmitted on a channel,
Sphere decoding that searches for candidates of transmitted symbol sequences within a radius of the received signal and provides a decoded data output by determining the distance of the candidate symbol from the received signal in the received signal space for the sequence And
A decoder including a sphere decoder controller that counts the distance determination and controls a sphere decoder to stop searching in response to the count.   The decoder of claim 17, wherein the channel is a MIMO channel.

Images