Reduced complexity detection and decoding for a receiver in a communication system

0001The present application claims priority to provisional <patcit id="pcit0001" dnum="US73815905P"><text>U.S. Application Serial No. 60/738,159</text></patcit>, entitled "REDUCED COMPLEXITY INTERATIVE DETECTION AND DECODING FOR MIMO-OFDM SYSTEMS," filed November 18, 2005, assigned to the assignee hereof and incorporated herein by reference.

BACKGROUND

I. Field

0002The present disclosure relates generally to communication, and more specifically to techniques for performing detection and decoding at a receiver in a communication system.

II. Background

0003A multiple-input multiple-output (MIMO) communication system employs multiple (T) transmit antennas at a transmitter and multiple (R) receive antennas at a receiver for data transmission. A MIMO channel formed by the T transmit antennas and the R receive antennas may be decomposed into M spatial channels, where M ≤ min {T, R}. The M spatial channels may be used to transmit data in a manner to achieve higher overall throughput and/or greater reliability.

0004The transmitter may encode and transmit M data streams in parallel via the T transmit antennas. The receiver obtains R received symbol streams via the R receive antennas, performs MIMO detection to separate out the M data streams, and performs decoding on the detected symbol streams to recover the transmitted data streams. To achieve optimal performance, the receiver would need to evaluate many hypotheses for all possible sequences of data bits that might have been transmitted based on all of the information available at the receiver. Such an exhaustive search is computationally intensive and is prohibitive for many applications.

0005There is therefore a need in the art for techniques to perform detection and decoding with reduced complexity while achieving good performance.

SUMMARY

0006Techniques for performing detection and decoding with reduced complexity while achieving good performance are described herein. These techniques are embodied in various reduced complexity detection schemes described below.

0007In one reduced complexity detection scheme, a receiver obtains R received symbol streams for M data streams transmitted by a transmitter, performs receiver spatial processing (or spatial matched filtering) on the received symbols to obtain detected symbols, performs log-likelihood ratio (LLR) computation independently for each of D "best" data streams, and performs LLR computation jointly for the M-D remaining data streams, where in general M > D ≥ 1 and M > 1. The D best data streams may be selected based on signal-to-noise-and-interference ratio (SNR) and/or other criteria. In another reduced complexity detection scheme, the receiver performs LLR computation independently for each of the D best data streams, performs LLR computation jointly for the M - D remaining data streams, and reduces the number of hypotheses to consider for the joint LLR computation by performing a search for candidate hypotheses using list sphere detection, Markov chain Monte Carlo, or some other search technique.

0008For both detection schemes, dimensionality is reduced from M to M - D by performing per-stream LLR computation for the D best data streams. The reduction in dimensionality may substantially reduce the number of hypotheses to consider for the joint LLR computation for the M - D remaining data streams. The number of hypotheses may be further reduced by performing a search for candidate hypotheses. These detection schemes may be used for (1) a single-pass receiver that performs detection and decoding once and (2) an iterative receiver that performs detection and decoding iteratively. These and other detection schemes are described in detail below.

0009Various aspects and embodiments of the invention are also described in further detail below.

BRIEF DESCRIPTION OF THE DRAWINGS

0010The features and nature of the present invention will become more apparent from the detailed description set forth below when taken in conjunction with the drawings in which like reference characters identify correspondingly throughout.

0011<figref idref="f0001">FIG. 1</figref> shows a block diagram of a transmitter and a receiver.

0012<figref idref="f0002">FIG. 2</figref> shows a block diagram of a transmit (TX) data processor and a TX spatial processor at the transmitter.

0013<figref idref="f0003">FIG. 3</figref> shows a block diagram of a receive (RX) spatial processor and an RX data processor for a single-pass receiver.

0014<figref idref="f0004">FIG. 4</figref> shows a block diagram of an RX spatial processor and an RX data processor for an iterative receiver.

0015<figref idref="f0005">FIG. 5</figref> shows a flow diagram for a reduced dimensionality detection scheme.

0016<figref idref="f0006">FIG. 6</figref> shows an apparatus for the reduced dimensionality detection scheme.

0017<figref idref="f0007">FIG. 7</figref> shows an exemplary search tree for list sphere detection.

0018<figref idref="f0008">FIG. 8</figref> shows a flow diagram for a reduced order detection scheme.

0019<figref idref="f0009">FIG. 9</figref> shows an apparatus for the reduced order detection scheme.

DETAILED DESCRIPTION

0020The word "exemplary" is used herein to mean "serving as an example, instance, or illustration." Any embodiment or design described herein as "exemplary" is not necessarily to be construed as preferred or advantageous over other embodiments or designs.

0021The detection and decoding techniques described herein may be used for various communication systems in which multiple data streams are transmitted in parallel via a communication channel. For example, these techniques may be used for a MIMO system with a single frequency subband, a MIMO system with multiple subbands, a Code Division Multiple Access (CDMA) system, a Frequency Division Multiple Access (FDMA) system, a Time Division Multiple Access (TDMA) system, and so on. Multiple subbands may be obtained with orthogonal frequency division multiplexing (OFDM), single-carrier frequency division multiple access (SC-FDMA), or some other modulation technique. OFDM and SC-FDMA partition the overall system bandwidth into multiple (L) orthogonal subbands, which are also called subcarriers, tones, bins, and so on. Each subband is associated with a subcarrier that may be independently modulated with data. In general, modulation symbols are sent in the frequency domain with OFDM and in the time domain with SC-FDMA. For clarity, much of the description below is for a MIMO system that utilizes OFDM.

0022<figref idref="f0001"><b>FIG. 1</b></figref> shows a block diagram of an embodiment of a transmitter 110 and a receiver 150 in a MIMO system 100. Transmitter 110 is equipped with multiple (T) antennas, and receiver 150 is equipped with multiple (R) antennas. For downlink (or forward link) transmission, transmitter 110 may be part of, and may contain some or all of the functionality of, a base station, an access point, a Node B, and so on. Receiver 150 may be part of, and may contain some or all of the functionality of, a mobile station, a user terminal, a user equipment, and so on. For uplink (or reverse link) transmission, transmitter 110 may be part of a mobile station, a user terminal, a user equipment, and so on, and receiver 150 may be part of a base station, an access point, a Node B, and so on.

0023At transmitter 110, a TX data processor 120 receives traffic data from a data source 112 and processes (e.g., formats, encodes, interleaves, and symbol maps) the traffic data to generate data symbols, which are modulation symbols for traffic data. A TX spatial processor 130 multiplexes the data symbols with pilot symbols, which are modulation symbols for pilot. A pilot is a transmission that is known <i>a priori</i> by both the transmitter and receiver and may also be referred to as a training signal, a reference, a preamble, and so on. TX spatial processor 130 performs transmitter spatial processing and provides T streams of transmit symbols to T transmitter units (TMTR) 132a through 132t. Each transmitter unit 132 processes (e.g., OFDM modulates, converts to analog, filters, amplifies, and upconverts) its transmit symbol stream and generates a modulated signal. T modulated signals from transmitter units 132a through 132t are transmitted from antennas 134a through 134t, respectively.

0024At receiver 150, R antennas 152a through 152r receive the T modulated signals, and each antenna 152 provides a received signal to a respective receiver unit (RCVR) 154. Each receiver unit 154 processes its received signal in a manner complementary to the processing performed by transmitter units 132 to obtain received symbols, provides received symbols for traffic data to an RX spatial processor 160, and provides received symbols for pilot to a channel processor 194. Channel processor 194 estimates the response of the MIMO channel from transmitter 110 to receiver 150 based on the received symbols for pilot (and possibly the received symbols for traffic data) and provides channel estimates to RX spatial processor 160. RX spatial processor 160 performs detection on the received symbols for traffic data with the channel estimates and provides soft decisions, which may be represented by LLRs as described below. An RX data processor 170 further processes (e.g., deinterleaves and decodes) the soft decisions and provides decoded data to a data sink 172. The detection and decoding may be performed with a single pass through processors 160 and 170 or iteratively between processors 160 and 170.

0025Receiver 150 may send feedback information to assist transmitter 110 in controlling the data transmission to receiver 150. The feedback information may indicate a particular transmission mode to use for transmission, a particular rate or packet format to use for each data stream, acknowledgments (ACKs) and/or negative acknowledgments (NAKs) for packets decoded by receiver 150, channel state information, and so on, or any combination thereof. The feedback information is processed (e.g., encoded, interleaved, and symbol mapped) by a TX signaling processor 180, multiplexed with pilot symbols and spatially processed by a TX spatial processor 182, and further processed by transmitter units 154a through 154r to generate R modulated signals, which are transmitted via antennas 152a through 152r.

0026At transmitter 110, the R modulated signals are received by antennas 134a through 134t, processed by receiver units 132a through 132t, spatially processed by an RX spatial processor 136, and further processed (e.g., deinterleaved and decoded) by an RX signaling processor 138 to recover the feedback information. A controller/processor 140 controls the data transmission to receiver 150 based on the received feedback information. A channel processor 144 may estimate the response of the MIMO channel from receiver 150 to transmitter 110 and may derive spatial mapping matrices used by TX spatial processor 130.

0027Controllers/processors 140 and 190 control the operation at transmitter 110 and receiver 150, respectively. Memories 142 and 192 store data and program codes for transmitter 110 and receiver 150, respectively.

0028<figref idref="f0002"><b>FIG. 2</b></figref> shows a block diagram of an embodiment of TX data processor 120 and TX spatial processor 130 at transmitter 110. For this embodiment, a common coding scheme is used for all data streams, and a separate code rate and a separate modulation scheme may be used for each data stream. For clarity, the following description assumes that M data streams are sent on M spatial channels.

0029Within TX data processor 120, an encoder 220 encodes traffic data in accordance with a coding scheme and generates code bits. The coding scheme may include a convolutional code, a Turbo code, a low density parity check (LDPC) code, a cyclic redundancy check (CRC) code, a block code, and so on, or a combination thereof. A demultiplexer (Demux) 222 demultiplexes (or parses) the code bits into M streams and provides the M code bit streams to M sets of processing units. Each set includes a puncture unit 224, a channel interleaver 226, and a symbol mapper 228. Each puncture unit 224 punctures (or deletes) code bits, as necessary, to achieve a code rate selected for its stream and provides the retained code bits to an associated channel interleaver 226. Each channel interleaver 226 interleaves (or reorders) its code bits based on an interleaving scheme and provides interleaved bits to an associated symbol mapper 228. The interleaving may be performed separately for each data stream (as shown in <figref idref="f0002">FIG. 2</figref>) or across some or all data streams (not shown in <figref idref="f0002">FIG. 2</figref>).

0030Each symbol mapper 228 maps its interleaved bits in accordance with a modulation scheme selected for its stream and provides a stream of data symbols {<i>s_m</i>}. The symbol mapping for stream <i>m</i> may be achieved by (1) grouping sets of Q<i>_m</i> bits to form Q<i>_m</i>-bit values, where Q<i>_m</i> ≥ 1, and (2) mapping each Q<i>_m</i>-bit value to one of 2^Q<i>_m</i> points in a signal constellation for the selected modulation scheme. Each mapped signal point is a complex value and corresponds to a data symbol. The symbol mapping may be based on Gray mapping or non-Gray mapping. With Gray mapping, neighboring points in the signal constellation (in both the horizontal and vertical directions) differ by only one out of Q<i>_m</i> bit positions. Gray mapping reduces the number of bit errors for more likely error events, which correspond to a received symbol being mapped to a location near the correct location, in which case only one coded bit would be detected in error. With non-Gray mapping, neighboring points may differ by more than one bit position. Non-Gray mapping may result in more independence between the coded bits and may improve performance for iterative detection and decoding.

0031Within TX spatial processor 130, a multiplexer (Mux) 230 receives the M data symbol streams from symbol mappers 228a through 228m and maps the data symbols and pilot symbols to the proper subbands in each symbol period. A matrix multiplier 232 multiplies the data and/or pilot symbols for each subband <i>l</i> with a spatial mapping matrix <b><u>P</u></b>(<i>l</i>) and provides transmit symbols for that subband. Different spatial mapping matrices may be used for different transmission modes, and different spatial mapping matrices may be used for different subbands for some transmission modes, as described below.

0032<figref idref="f0002">FIG. 2</figref> shows an embodiment in which a common coding scheme and separate code rates and modulation schemes may be used for the M data streams. Different code rates may be achieved for the M data streams by using different puncture patterns for these streams. In another embodiment, a common coding scheme and a common code rate are used for all data streams, and separate modulation schemes may be used for the M data streams. In yet another embodiment, a common coding scheme, a common code rate, and a common modulation scheme are used for all M data streams. In still yet another embodiment, each data stream is processed based on a coding and modulation scheme selected for that data stream. In general, the same or different coding schemes, the same or different code rates, and the same or different modulation schemes may be used for the M data streams. Furthermore, the same or different coding schemes, the same or different code rates, and the same or different modulation schemes may be used across the subbands.

0033Transmitter 110 typically encodes each packet separately. In an embodiment, the M data streams are jointly encoded so that a single packet may be sent on multiple (e.g., all M) spatial channels. In another embodiment, the M data streams are independently encoded so that each packet is sent on one spatial channel. In yet another embodiment, some data streams are jointly encoded while remaining data streams are independently encoded.

0034For clarity, the following description assumes that one data stream is sent on each spatial channel. The terms "data stream" and "spatial channel" are thus interchangeable for much of the description below. The number of data streams may be configurable and may be selected based on channel conditions and/or other factors. For clarity, the following description assumes that M data streams are sent on M spatial channels.

0035<figref idref="f0003"><b>FIG. 3</b></figref> shows a block diagram of an RX spatial processor 160a and an RX data processor 170a for a single-pass receiver. Processors 160a and 170a are an embodiment of processors 160 and 170, respectively, at receiver 150 in <figref idref="f0001">FIG. 1</figref>. For this embodiment, processors 160a and 170a perform detection and decoding with a single pass through each of processors 160a and 170a.

0036Within RX spatial processor 160a, a spatial filter matrix computation unit 308 receives the channel estimates from channel processor 194 and derives spatial filter matrices based on the channel estimates and the spatial mapping matrices used by transmitter 110, as described below. A MIMO detector 310 obtains the received symbols from R receiver units 154a through 154r, the channel estimates from channel processor 194, and the spatial filter matrices from unit 308. MIMO detector 310 performs detection as described below and provides K soft decisions for K code bits of M data symbols sent on each subband in each symbol period used for data transmission. A soft decision is a multi-bit value that is an estimate of a transmitted code bit. The soft decisions may be represented as LLRs and may be referred to as extrinsic LLRs. If M data symbols are sent on one subband in one symbol period, then K may be computed as <maths id="math0001" num=""><math display="inline"><mi mathvariant="normal">K</mi><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>1</mn></mrow><mi mathvariant="normal">M</mi></munderover></mstyle><msub><mi mathvariant="normal">Q</mi><mi>m</mi></msub><mo>,</mo></math><img file="EP2262129A2_D0001.tif" /></maths> where Q<i>_m</i> is the number of code bits used to form a data symbol for stream <i>m</i>. If the same modulation scheme is used for all M data streams, then K may be computed as K = M · Q , where Q is the number of code bits for each data symbol.

0037Within RX data processor 170a, channel deinterleavers 316a through 316m receive the extrinsic LLRs for the M data streams. Each channel deinterleaver 316 deinterleaves the extrinsic LLRs for its stream in a manner complementary to the interleaving performed by channel interleaver 226 for that stream. A multiplexer 318 multiplexes (or serializes) the deinterleaved LLRs from channel deinterleavers 316a through 316m. A decoder 320 decodes the deinterleaved LLRs and provides decoded data. The detection and decoding are described in detail below.

0038<figref idref="f0004"><b>FIG. 4</b></figref> shows a block diagram of an RX spatial processor 160b and an RX data processor 170b for an iterative receiver. Processors 160b and 170b are another embodiment of processors 160 and 170, respectively, at receiver 150. For this embodiment, processors 160b and 170b perform detection and decoding iteratively.

0039Within RX spatial processor 160b, a unit 408 derives spatial filter matrices based on the channel estimates and the spatial mapping matrices used by transmitter 110. A MIMO detector 410 obtains the received symbols from R receiver units 154a through 154r, the channel estimates from channel processor 194, the spatial filter matrices from unit 408, and <i>a priori</i> LLRs from a decoder 420. The <i>a priori</i> LLRs are denoted as <i>L_a</i>(<i>b_k</i>) and represent <i>a priori</i> information from decoder 420. MIMO detector 410 performs detection as described below and provides K detector LLRs for K code bits of M data symbols sent on each subband in each symbol period used for data transmission. The detector LLRs are denoted as <i>L</i>(<i>b_k</i>). K summers 412a through 412k subtract the <i>a priori</i> LLRs from the detector LLRs and provide extrinsic LLRs, which are denoted as <i>L_e</i>(<i>b_k</i>). The extrinsic LLRs represent extrinsic or new information from MIMO detector 410 to decoder 420.

0040Within RX data processor 170b, an M-stream channel deinterleaver 416 deinterleaves the extrinsic LLRs for each stream in a manner complementary to the interleaving performed by channel interleaver 226 for that stream. Channel deinterleaver 416 may include M channel deinterleavers 316a through 316m shown in <figref idref="f0003">FIG. 3</figref>. A multiplexer 418 serializes the deinterleaved LLRs, which are denoted as <maths id="math0002" num=""><math display="inline"><msubsup><mi>L</mi><mi>e</mi><mi>D</mi></msubsup><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mn>.</mn></math><img file="EP2262129A2_D0002.tif" /></maths> A decoder 420 decodes the deinterleaved LLRs and provides decoder LLRs. A summer 422 subtracts the deinterleaved LLRs from the decoder LLRs and provides <i>a priori</i> LLRs, which represent extrinsic information from decoder 420 to MIMO detector 410 for the next iteration. The <i>a priori</i> LLRs for MIMO detector 410 are demultiplexed into M streams by a demultiplexer 424. An M-stream channel interleaver 426 interleaves the <i>a priori</i> LLRs for each stream in the same manner performed by channel interleaver 226 for that stream. Channel interleaver 426 may include M channel interleavers 226a through 226m shown in <figref idref="f0002">FIG. 2</figref>. Channel interleaver 426 provides the interleaved <i>a priori</i> LLRs for the next iteration to MIMO detector 410.

0041RX spatial processor 160b and RX data processor 170b may perform any number of iterations. In an embodiment, processors 160b and 170b perform a predetermined number of iterations (e.g., 4, 6, 8 or more iterations). In another embodiment, processors 160b and 170b perform one iteration, then check if a packet is decoded correctly and/or if a decoder reliability metric is sufficiently high, and perform another iteration if the packet is decoded in error or if the decoder reliability metric is low. The error detection may be achieved with a CRC and/or some other error detection code. Processors 160b and 170b may thus perform a fixed number of iterations or a variable number of iterations up to some maximum number of iterations. The iterative detection and decoding is described in detail below.

0042The received symbols at receiver 150 may be expressed as: <maths id="math0003" num="eq (1)"><math display="block"><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>=</mo><msub><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>ch</mi></msub><mfenced><mi>l</mi></mfenced><mo>⋅</mo><munder><mi mathvariant="bold">P</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>⋅</mo><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>=</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>⋅</mo><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder><mfenced><mi>l</mi></mfenced><mo>,</mo><mspace width="2em" /><mi>for</mi><mspace width="1em" /><mi>l</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi mathvariant="normal">L</mi><mo>,</mo></math><img file="EP2262129A2_D0003.tif" /></maths><ul id="ul0001" list-style="none" compact="compact"><li>where <b><u>s</u></b>(<i>l</i>) is an M×1 vector with M data symbols sent on subband <i>l</i>;</li><li><b><u>P</u></b>(<i>l</i>) is a T×M spatial mapping matrix used by transmitter 110 for subband <i>l</i>;</li><li><b><u>H</u></b>_ch(<i>l</i>) is an R xT MIMO channel response matrix for subband <i>l</i>;</li><li><b><u>H</u></b>(<i>l</i>) = <b><u>H</u></b>_ch(<i>l</i>)·<b><u>P</u></b>(<i>l</i>) is an R×M effective MIMO channel response matrix for subband <i>l</i>;</li><li><b><u>y</u></b>(<i>l</i>) is an R×1 vector with R received symbols for subband <i>l</i>; and</li><li><b><u>n</u></b>(<i>l</i>) is an R×1 vector of noise for subband <i>l</i>.</li></ul> The noise may be assumed to be additive white Gaussian noise (AWGN) with a zero mean vector and a covariance matrix of <maths id="math0004" num=""><math display="inline"><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup><mn>.</mn></math><img file="EP2262129A2_D0004.tif" /></maths> where <maths id="math0005" num=""><math display="inline"><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></math><img file="EP2262129A2_D0005.tif" /></maths> is the variance of the noise and <b><u>I</u></b> is the identity matrix. The effective MIMO channel response <b><u>H</u></b>(<i>l</i>) includes the actual MIMO channel response <b><u>H</u></b>_ch(<i>l</i>) and the spatial mapping matrix <b><u>P</u></b>(<i>l</i>) used by transmitter 110.

0043In an embodiment, a MIMO detector (e.g., MIMO detector 310 or 410) performs detection separately for each subband based on the received symbols and the channel estimate for that subband and, if available, the <i>a priori</i> LLRs for the data symbols sent on that subband. In another embodiment, the MIMO detector performs detection jointly for multiple subbands. A decoder (e.g., decoder 320 or 420) performs decoding on a sequence of LLRs for a packet, which may be transmitted on one or multiple subbands. For clarity, subband index I is omitted in the following description.

0044A packet may be partitioned into multiple blocks, with each block containing K code bits. The K code bits for each block may be mapped to M data symbols, as follows: <maths id="math0006" num="eq (2)"><math display="block"><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo mathvariant="normal">=</mo><mi>map</mi><mfenced><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder></mfenced><mo>,</mo></math><img file="EP2262129A2_D0006.tif" /></maths><ul id="ul0002" list-style="none" compact="compact"><li>where <b><u>s</u></b> = [<i>s</i>₁<i>s</i>₂ ... <i>s</i>_M] is a vector with M data symbols; <maths id="math0007" num=""><math display="inline"><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>=</mo><mfenced open="[" close="]" separators=""><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mn>1</mn></msub><mspace width="1em" /><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mn>2</mn></msub><mspace width="1em" /><mo>…</mo><mspace width="1em" /><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mi mathvariant="normal">M</mi></msub></mfenced><mo>=</mo><mfenced open="[" close="]" separators=""><munder><munder><mrow><msub><mi>b</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub><mspace width="1em" /><mo>…</mo><msub><mrow><mspace width="1em" /><mi>b</mi></mrow><mrow><mn>1</mn><mo>,</mo><msub><mi mathvariant="normal">Q</mi><mn>1</mn></msub></mrow></msub></mrow><mo>︸</mo></munder><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mn>1</mn></msub></munder><mspace width="1em" /><munder><munder><mrow><msub><mi>b</mi><mrow><mn>2</mn><mo>,</mo><mn>1</mn></mrow></msub><mspace width="1em" /><mo>…</mo><msub><mrow><mspace width="1em" /><mi>b</mi></mrow><mrow><mn>2</mn><mo>,</mo><msub><mi mathvariant="normal">Q</mi><mn>2</mn></msub></mrow></msub></mrow><mo>︸</mo></munder><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mn>2</mn></msub></munder><mo>⋯</mo><mspace width="1em" /><munder><munder><mrow><msub><mi>b</mi><mrow><mi mathvariant="normal">M</mi><mo>,</mo><mn>1</mn></mrow></msub><mspace width="1em" /><mo>…</mo><msub><mrow><mspace width="1em" /><mi>b</mi></mrow><mrow><mi mathvariant="normal">M</mi><mo>,</mo><msub><mi mathvariant="normal">Q</mi><mi mathvariant="normal">M</mi></msub></mrow></msub></mrow><mo>︸</mo></munder><msub><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mstyle mathvariant="normal"><mi>M</mi></mstyle></msub></munder></mfenced><mo>=</mo><mfenced open="[" close="]" separators=""><msub><mi>b</mi><mn>1</mn></msub><mspace width="1em" /><msub><mi>b</mi><mn>2</mn></msub><mspace width="1em" /><mo>…</mo><mspace width="1em" /><msub><mi>b</mi><mi mathvariant="normal">K</mi></msub></mfenced></math><img file="EP2262129A2_D0007.tif" /></maths>is a vector with K code bits for one block;</li><li><b><u>b</u></b><i>_m</i> is a vector with Q<i>_m</i> code bits used to form data symbol <i>s_m</i> for stream m;</li><li><i>b_m,q</i>, for <i>m</i> = 1, ..., M and <i>q</i> =1, ..., Q<i>_m</i>, is the <i>q</i>-th code bit in vector <b><u>b</u></b><i>_m</i>; and</li><li><i>b_k</i>, for <i>k</i> = 1, ..., K , is the <i>k</i>-th code bit in vector <b><u>b</u></b>.</li></ul> There is a one-to-one mapping between a given bit vector <b><u>b</u></b> and a corresponding data vector <b><u>s</u></b>. In general, Q may be the same or different for the M data symbols sent on a given subband, and K may be the same or different for the L subbands.

0045An optimal receiver for the transmission scheme shown in equation (1) is a maximum likelihood (ML) sequence receiver that performs detection and decoding jointly for an entire packet. This optimal receiver would make joint decisions on all data bits in the packet using knowledge of the correlation introduced by the coding scheme across the blocks, subbands, and OFDM symbols for the packet. The optimal receiver would perform an exhaustive search over all possible sequences of data bits that might have been transmitted for the packet to find the sequence that is most likely to have been transmitted. This optimal receiver would be prohibitively complex.

0046A receiver that performs detection and decoding iteratively, e.g., as shown in <figref idref="f0004">FIG. 4</figref>, can achieve near-optimal performance with lower complexity. The detector and decoder compute soft decisions on the code bits and exchange this information in an iterative manner, which increases the reliability of the soft decisions with the number of iterations performed. The MIMO detector and decoder may each be implemented in various manners.

0047In an embodiment, the MIMO detector is a maximum <i>a posteriori</i> probability (MAP) detector that minimizes the error probability for each code bit and provides a soft decision for each code bit. The MAP detector provides soft decisions in the form of <i>a posteriori</i> probabilities (APPs) that are often expressed as LLRs. The detector LLR for code bit <i>b_k</i>, <i>L</i>(<i>b_k</i>), may be expressed as: <maths id="math0008" num="eq (3)"><math display="block"><mi>L</mi><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>=</mo><mi>ln</mi><mo>⁢</mo><mfrac><mrow><mi>P</mi><mfenced open="{" close="}" separators=""><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>+</mo><mn>1</mn><mrow><mo>|</mo></mrow><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder></mfenced></mrow><mrow><mi>P</mi><mfenced open="{" close="}" separators=""><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>-</mo><mn>1</mn><mrow><mo>|</mo></mrow><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder></mfenced></mrow></mfrac><mo>,</mo><mspace width="1em" /><mi>for</mi><mspace width="1em" /><mi>k</mi><mo>=</mo><mn>1</mn><mo>,</mo><mo>…</mo><mo>,</mo><mi mathvariant="normal">K</mi><mo>,</mo></math><img file="EP2262129A2_D0008.tif" /></maths><ul id="ul0003" list-style="none" compact="compact"><li>where <i>P</i>{<i>b_k</i> = +1|<b><u>y</u></b>} is the probability of code bit <i>b_k</i> being +1 given received vector <b><u>y</u></b>; and</li><li><i>P</i>{<i>b_k</i> = -1|<b><u>y</u></b>} is the probability of code bit <i>b_k</i> being -1 given received vector <b><u>y</u></b>,</li></ul>

0048The detector LLR may be separated into two parts, as follows: <maths id="math0009" num="eq (4)"><math display="block"><mi>L</mi><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>=</mo><msub><mi>L</mi><mi>a</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>+</mo><msub><mi>L</mi><mi>e</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>,</mo></math><img file="EP2262129A2_D0009.tif" /></maths> where <i>L_a</i>(<i>b_k</i>) is the <i>a priori</i> LLR for code bit <i>b_k</i> provided by the decoder or possibly other sources to the MIMO detector and <i>L_e</i>(<i>b_k</i>) is the extrinsic LLR for code bit <i>b_k</i> provided by the MIMO detector to the decoder. The <i>a priori</i> LLR for code bit <i>b_k</i> may be expressed as: <maths id="math0010" num="eq (5)"><math display="block"><msub><mi>L</mi><mi>a</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>=</mo><mi>ln</mi><mo>⁢</mo><mfrac><mrow><mi>P</mi><mfenced open="{" close="}" separators=""><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>+</mo><mn>1</mn></mfenced></mrow><mrow><mi>P</mi><mfenced open="{" close="}" separators=""><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>-</mo><mn>1</mn></mfenced></mrow></mfrac><mo>,</mo></math><img file="EP2262129A2_D0010.tif" /></maths><ul id="ul0004" list-style="none" compact="compact"><li>where <i>P</i>{<i>b_k</i> = +1} is the probability of code bit <i>b_k</i> being +1; and</li><li><i>P</i>{<i>b_k</i> = -1} is the probability of code bit <i>b_k</i> being -1.</li></ul>

0049The MAP detector may be a log-MAP detector, a max-log-MAP detector, or some other type of MAP detector. The extrinsic LLR from a log-MAP detector, which is called a log-MAP LLR, may be computed as: <maths id="math0011" num="eq (6)"><math display="block"><msub><mi>L</mi><mi>e</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>=</mo><mi>ln</mi><mo>⁢</mo><mfrac><mrow><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>+</mo><mn>1</mn></mrow></munder></mstyle><mo>-</mo><mfrac><mn>1</mn><mrow><mn>2</mn><mo>⁢</mo><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mrow></mfrac><mo>⋅</mo></mstyle><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>⋅</mo><mi>exp</mi><mfenced separators=""><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced></mrow><mrow><mstyle displaystyle="false"><mstyle displaystyle="true"><munder><mo>∑</mo><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>+</mo><mn>1</mn></mrow></munder></mstyle><mo>-</mo><mfrac><mn>1</mn><mrow><mn>2</mn><mo>⁢</mo><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mrow></mfrac><mo>⋅</mo></mstyle><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>⋅</mo><mi>exp</mi><mfenced separators=""><mfrac><mn>1</mn><mn>2</mn></mfrac><mo>⁢</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced></mrow></mfrac><mo>,</mo></math><img file="EP2262129A2_D0011.tif" /></maths><ul id="ul0005" list-style="none" compact="compact"><li>where <b><u>b̃</u></b> and <b><u>s̃</u></b> are vectors that are hypothesized to have been transmitted;</li><li><b><u>b̃</u></b>_[<i>k</i>] is a vector with all code bits in vector <b><u>b̃</u></b> except for code bit <i>b_k</i>;</li><li><b><u>L</u></b>_<i>a</i>,[k] is a vector with <i>a priori</i> LLRs for all code bits in <b><u>b̃</u></b>_[<i>k</i>];</li><li>∥<b><u>y</u></b>-<b><u>H</u></b>·<b><u>s̃</u></b>∥² represents a Euclidean distance cost function; and</li><li>"<i>^T</i>" denotes a transpose.</li></ul>

0050Equation (6) shows one expression for the extrinsic LLR from the log-MAP detector. The extrinsic LLR may also be expressed in other forms. The receiver typically derives <b><u>Ĥ</u></b>, which is an estimate of the effective MIMO channel response matrix <b><u>Ĥ</u></b>, and uses <b><u>Ĥ</u></b> in the LLR computation. For simplicity, the description herein assumes no channel estimation error, so that <b><u>Ĥ</u></b> = <b><u>H</u></b>.

0051Equation (6) is evaluated for each code bit in the transmitted bit vector <b><u>b</u>.</b> For each code bit <i>b_k</i>, 2^K hypothesized bit vectors <b><u>b̃</u></b> for all possible sequences of code bits {<i>b</i>₁ ... <i>b</i>_K} (or all possible combinations of code bit values) that might have been transmitted for vector <b><u>b</u></b> are considered. 2^K-1 hypothesized bit vectors <b><u>b̃</u></b> have <i>b_k</i> = +1, and the other 2^K-1 hypothesized bit vectors <b><u>b̃</u></b> have <i>b_k</i> =-1. Each hypothesized bit vector <b><u>b̃</u></b> has a corresponding hypothesized data vector <b><u>s̃</u></b>. The expression within the summation is computed for each hypothesized bit vector <b><u>b̃</u></b> to obtain a result for that bit vector. The results for the 2^K-1 hypothesized bit vectors <b><u>b̃</u></b> with <i>b_k</i> =+1 are summed to obtain a total result for the numerator. The results for the 2^K-1 hypothesized bit vectors <b><u>b̃</u></b> with <i>b_k</i> = -1 are summed to obtain a total result for the denominator. The log-MAP LLR for code bit <i>b_k</i> is equal to the natural logarithm (In) of the total result for the numerator divided by the total result for the denominator.

0052A max-log-MAP detector approximates the log-MAP LLR in equation (6) and provides a max-log-MAP LLR, as follows: <maths id="math0012" num="eq (7)"><math display="block"><msub><mi>L</mi><mi>e</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>≈</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>+</mo><mn>1</mn></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mfrac><mo>⋅</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced><mo>-</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msub><mi>b</mi><mi>k</mi></msub><mo>=</mo><mo>-</mo><mn>1</mn></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mfrac><mo>⋅</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced><mn>.</mn></math><img file="EP2262129A2_D0012.tif" /></maths> The max-log-MAP approximation in equation (7) replaces the summations in equation (6) with max{ } operations. Only a small degradation in performance typically results from using the max-log-MAP approximation. Other approximations of the log-MAP LLR in equation (6) may also be used.

0053The log-MAP detector in equation (6) and the max-log-MAP detector in equation (7) make joint decisions on the received symbols in vector <b><u>y</u></b> and compute extrinsic LLRs for the code bits associated with these received symbols. In order to compute the extrinsic LLRs optimally, each MAP detector performs an exhaustive search over all possible combinations of data symbols that might have been transmitted for vector <b><u>s</u></b>. This exhaustive search is computationally intensive and may be prohibitive for many applications. The complexity of the LLR computation is exponential in the number of bits (K) in the transmitted bit vector <b><u>b</u></b> for both the log-MAP and max-log-MAP detectors. In particular, 2^K hypotheses are considered by both MAP detectors for each code bit <i>b_k</i>. Various detection schemes with reduced complexity are described below.

0054To reduce computational complexity, the receiver may perform receiver spatial processing (or spatial matched filtering) on the received symbols to obtain detected symbols and may then perform LLR computation independently for each detected symbol. The detected symbols are estimates of the data symbols transmitted by the transmitter. The receiver may perform receiver spatial processing based on a zero-forcing (ZF) technique, a minimum mean square error (MMSE) technique, a maximal ratio combining (MRC) technique, or some other technique. A spatial filter matrix may be derived based on the ZF, MMSE, or MRC technique, as follows: <maths id="math0013" num="eq (8)"><math display="block"><msub><munder><mi mathvariant="bold">M</mi><mo>̲</mo></munder><mi mathvariant="italic">zf</mi></msub><mo mathvariant="normal">=</mo><msup><mfenced open="[" close="]" separators=""><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi mathvariant="italic">H</mi></msup><mo mathvariant="normal">⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder></mfenced><mrow><mo mathvariant="normal">-</mo><mn mathvariant="normal">1</mn></mrow></msup><mo mathvariant="normal">⋅</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi mathvariant="italic">H</mi></msup><mo mathvariant="normal">,</mo></math><img file="EP2262129A2_D0013.tif" /></maths><maths id="math0014" num="eq (9)"><math display="block"><msub><munder><mi mathvariant="bold">M</mi><mo>̲</mo></munder><mi mathvariant="italic">mmse</mi></msub><mo>=</mo><msub><munder><mi mathvariant="bold">D</mi><mo>̲</mo></munder><mi mathvariant="italic">mmse</mi></msub><mo>⋅</mo><msup><mfenced open="[" close="]" separators=""><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>+</mo><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup><mo>⋅</mo><mi mathvariant="bold">I</mi></mfenced><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⋅</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>,</mo></math><img file="EP2262129A2_D0014.tif" /></maths><maths id="math0015" num="eq (10)"><math display="block"><msub><munder><mi mathvariant="bold">M</mi><mo>̲</mo></munder><mi mathvariant="italic">mrc</mi></msub><mo>=</mo><msub><munder><mi mathvariant="bold">D</mi><mo>̲</mo></munder><mi mathvariant="italic">mrc</mi></msub><mo>⋅</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>,</mo></math><img file="EP2262129A2_D0015.tif" /></maths><ul id="ul0006" list-style="none" compact="compact"><li>where <maths id="math0016" num=""><math display="inline"><msub><munder><mi mathvariant="bold">D</mi><mo>̲</mo></munder><mi mathvariant="italic">mmse</mi></msub><mo>=</mo><mi>diag</mi><mo>⁢</mo><msup><mfenced open="{" close="}" separators=""><msup><mfenced open="[" close="]" separators=""><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>+</mo><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup><mo>⋅</mo><munder><mi mathvariant="bold">I</mi><mo>̲</mo></munder></mfenced><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>⋅</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder></mfenced><mrow><mo>-</mo><mn>1</mn></mrow></msup><mo>;</mo></math><img file="EP2262129A2_D0016.tif" /></maths></li><li><b><u>D</u></b><i>_mrc</i> = diag[<b><u>H</u></b><i>^H ·</i><b><u>H</u></b>]^-1 ;</li><li><b><u>M</u></b><i>_zf</i> , <b><u>M</u></b><i>_mmse</i> and <b><u>M</u></b><i>_mrc</i> are MxR spatial filter matrices for the ZF, MMSE, and MRC techniques, respectively; and</li><li>"<i>^H</i>" denotes a conjugate transpose.</li></ul>

0055The receiver spatial processing may be expressed as: <maths id="math0017" num="eq (11)"><math display="block"><mover><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>^</mo></mover><mo>=</mo><munder><mi mathvariant="bold">M</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>,</mo></math><img file="EP2262129A2_D0017.tif" /></maths><ul id="ul0007" list-style="none" compact="compact"><li>where <b><u>M</u></b> may be equal to <b><u>M</u></b><i>_zf</i> , <b><u>M</u></b><i>_mmse</i> or <b><u>M</u></b><i>_mrc</i>; and</li><li><b><u>ŝ</u></b> is an M×1 vector of detected symbols and is an estimate of data vector <b><u>s</u></b>.</li></ul>

0056LLR computation may be performed independently for each detected symbol. The extrinsic LLRs may be computed for the <i>Q_m</i> code bits of each detected symbol <i>ŝ_m</i> with the max-log-MAP detector, as follows: <maths id="math0018" num="eq (12)"><math display="block"><msub><mi>L</mi><mi>e</mi></msub><mfenced><msub><mi>b</mi><mrow><mi>m</mi><mo>,</mo><mi>q</mi></mrow></msub></mfenced><mo>≈</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><msub><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mi>m</mi></msub><mo>:</mo><msub><mi>b</mi><mrow><mi>m</mi><mo>,</mo><mi>q</mi></mrow></msub><mo>=</mo><mo>+</mo><mn>1</mn></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msup><mi>σ</mi><mn>2</mn></msup></mfrac><mo>⋅</mo><msup><mfenced open="|" close="|" separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mi>m</mi></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mi>m</mi></msub></mfenced><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mrow><mi>m</mi><mo>,</mo><mfenced open="[" close="]"><mi>q</mi></mfenced></mrow><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mi>m</mi><mo>,</mo><mfenced open="[" close="]"><mi>q</mi></mfenced></mrow></msub></mfenced><mo>-</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><msub><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mi>m</mi></msub><mo>:</mo><msub><mi>b</mi><mrow><mi>m</mi><mo>,</mo><mi>q</mi></mrow></msub><mo>=</mo><mo>-</mo><mn>1</mn></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msup><mi>σ</mi><mn>2</mn></msup></mfrac><mo>⋅</mo><msup><mfenced open="|" close="|" separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mi>m</mi></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mi>m</mi></msub></mfenced><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mrow><mi>m</mi><mo>,</mo><mfenced open="[" close="]"><mi>q</mi></mfenced></mrow><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mi>m</mi><mo>,</mo><mfenced open="[" close="]"><mi>q</mi></mfenced></mrow></msub></mfenced><mn>.</mn></math><img file="EP2262129A2_D0018.tif" /></maths><ul id="ul0008" list-style="none" compact="compact"><li>where <i>ŝ_m</i> is the <i>m</i>-th element of <b><u>ŝ</u></b>;</li><li><i>s̃_m</i> is a hypothesized data symbol for transmitted data symbol <i>s_m</i>;</li><li><b><u>b̃</u></b>_{<i>m</i>,[<i>q</i>]} is a vector with all code bits for data symbol <i>s_m</i> except for code bit <i>b_m,q</i>;</li><li><b>L</b>_{<i>a</i>,<i>m</i>,[<i>q</i>]} is a vector with <i>a priori</i> LLRs for all code bits in <b><u>b̃</u></b>_{<i>m</i>,[<i>q</i>]}; and</li><li><i>L_e</i>(<i>b_m,q</i>) is the extrinsic LLR for code bit <i>b_m,q.</i></li></ul>

0057Equation (12) is evaluated for each code bit in each transmitted bit vector <b><u>b</u></b><i>_m</i>, for <i>m</i> = 1, ..., M. For each code bit <i>b_m,q</i> in bit vector <b><u>b</u></b><i>_m</i>, 2^Q<i>m</i> hypothesized bit vectors <b><u>b̃</u></b><i>_m</i> for all possible sequences of code bits {<i>b</i>_<i>m</i>,1 ... <i>b</i>_{<i>m</i>,Q<sub2>m</sub2>} } that might have been transmitted for vector <b><u>b</u></b><i>_m</i> are considered. Each hypothesized bit vector <b><u>b̃</u></b><i>_m</i> has a corresponding hypothesized data symbol <b><i>s̃</i></b><i>_m</i>. The expression within the max{} operation is computed for each hypothesized bit vector <b><u>b̃</u></b><i>_m</i> to obtain a result for that vector. The results for the 2^Q<i>_m</i>-1 hypothesized bit vectors <b><u>b̃</u></b><i>_m</i> with <i>b_m,q</i> = +1 are used in the first max{ } operation. The results for the 2^Q<i>_m</i>-1 hypothesized bit vectors <b><u>b̃</u></b><i>_m</i> with <i>b_m,q</i> = -1 are used in the second max{ } operation.

0058The complexity of the receiver spatial processing is linear in the number of data streams (M) and is not dependent on the signal constellation size. Computing the extrinsic LLRs on a per-stream basis reduces the number of hypotheses to evaluate from 2^M·Q to M·2^Q, assuming that the same modulation scheme is used for all M data streams. The per-stream LLR computation may substantially reduce computational complexity but may result in higher performance degradation than desired.

0059In an aspect, the receiver performs receiver spatial processing on the received symbols to obtain detected symbols, performs LLR computation independently for each of D best detected symbols, and performs LLR computation jointly for the M - D remaining detected symbols, where M > D ≥ 1. The D best detected symbols may be for the D data streams with the highest SNRs, the D data streams with the smallest SNR variation, the D data streams with the most robust coding, and so on. This detection scheme is referred to as a reduced dimensionality detection scheme and may be used for the single-pass receiver shown in <figref idref="f0003">FIG. 3</figref> and the iterative receiver shown in <figref idref="f0004">FIG. 4</figref>.

0060The receiver may perform receiver spatial processing on the R received symbols to obtain the D best detected symbols (instead of all M detected symbols). A reduced spatial filter matrix <b><u>M</u></b>_D of dimension D×R may be derived based on a reduced channel response matrix <b><u>H</u></b>_D. Matrix <b><u>H</u></b>_D has dimension of R×D and includes D columns of <b><u>H</u></b> corresponding to the D best detected symbols. The receiver spatial processing for the D best detected symbols is less computationally complex.

0061The receiver may perform LLR computation independently for each of the D best detected symbols, e.g., based on the max-log-MAP detector shown in equation (12) or some other type of detector. The receiver may perform joint LLR computation for the M - D remaining detected symbols in various manners.

0062In one embodiment, the receiver performs joint LLR computation for the remaining detected symbols by considering the D best detected symbols. For this embodiment, hard decisions are made on the D best detected symbols. A hard decision <i>s̅_m</i> for a given detected symbol <i>ŝ_m</i> is a modulation symbol that is closest in distance to <i>ŝ_m</i> from among all modulation symbols in the signal constellation used for <i>ŝ_m</i>. The receiver then computes extrinsic LLRs for the code bits for the remaining detected symbols, e.g., based on the max-log-MAP detector shown in equation (7) or some other type of detector. For this LLR computation, the D best detected symbols are constrained or fixed to the hard decisions determined for these detected symbols. Hence, the number of hypotheses to evaluate is reduced from <maths id="math0019" num=""><math display="inline"><msup><mn>2</mn><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>1</mn></mrow><mi mathvariant="normal">M</mi></munderover><msub><mi mathvariant="normal">Q</mi><mi>m</mi></msub></mrow></msup></math><img file="EP2262129A2_D0019.tif" /></maths> to <maths id="math0020" num=""><math display="inline"><msup><mn>2</mn><mrow><munderover><mo>∑</mo><mrow><mi>m</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi mathvariant="normal">M</mi><mo>-</mo><mi mathvariant="normal">D</mi></mrow></munderover><msub><mi mathvariant="normal">Q</mi><mi>m</mi></msub></mrow></msup><mo>,</mo></math><img file="EP2262129A2_D0020.tif" /></maths> assuming that the D best detected symbols have indices of <i>m</i> = M - D + 1, ..., M.

0063In another embodiment, the receiver performs joint LLR computation for the remaining detected symbols without considering the D best detected symbols. For this embodiment, the receiver forms reduced vectors for <b><u>b̃</u></b>, <b><u>s̃</u></b>, <b><u>L</u></b>_{<i>a</i>,[<i>k</i>]} and <b><u>b̃</u></b>_[<i>k</i>] as well as a reduced matrix for <b><u>H</u></b>. The reduced vectors and matrix include only elements corresponding to the remaining detected symbols. The receiver then computes extrinsic LLRs for the code bits for the remaining detected symbols, e.g., based on the max-log-MAP detector shown in equation (7) or some other type of detector. The reduced vectors and matrix are used for the LLR computation. Hence, the number of hypotheses to evaluate and the computation for each hypothesis are both reduced.

0064In an embodiment, D is a fixed value that may be selected based on a tradeoff between complexity, performance, and/or other considerations. In another embodiment, D is a configurable value that may be selected based on the selected transmission mode, the channel conditions (e.g., the SNRs for the data streams) and/or other factors. D may be adaptive and may be selected per packet, per frame, per subband, or in some other manner.

0065The reduced dimensionality detection scheme may provide good performance with less complexity than the exhaustive detection scheme shown in equations (6) and (7). The reduced dimensionality detection scheme may be well suited for a data transmission in which some data streams observe high SNRs and/or low frequency selectivity and the remaining data streams observe lower SNRs and/or greater frequency selectivity. Frequency selectivity refers to variation in channel gains across frequency, which results in SNR variation across frequency. The reduced dimensionality detection scheme takes advantage of the high SNRs and/or low frequency selectivity for the D best data streams to reduce computational complexity. Near optimal detection is performed on the remaining data streams with lower SNRs and/or greater frequency selectivity to improve performance over a detection scheme that performs per-stream LLR computation for all M data streams.

0066<figref idref="f0005"><b>FIG. 5</b></figref> shows a process 500 for performing detection and decoding based on the reduced dimensionality detection scheme. Receiver spatial processing is performed on received symbols for multiple data streams (e.g., based on the zero-forcing or MMSE technique) to obtain detected symbols (block 512). Detection is performed independently for each of at least one data stream to obtain soft decisions for the stream (block 514). Detection is performed jointly for the remaining data streams to obtain soft decisions for these streams (block 516). The soft decisions (e.g., extrinsic LLRs) for each of the at least one data stream may be derived independently based on the detected symbols and <i>a priori</i> information (e.g., <i>a priori</i> LLRs) from the decoder, if any, for that stream. The soft decisions for the remaining data streams may be derived jointly based on the received symbols and the <i>a priori</i> information, if any. The soft decisions for the multiple data streams may be decoded to obtain <i>a priori</i> information for the detector (block 518).

0067A determination is then made whether to perform another iteration of detection and decoding (block 520). The answer for block 520 is 'No' after one iteration for a single-pass receiver and is also 'No' for an iterative receiver if a termination condition is encountered. If the answer is 'Yes' for block 520, then the <i>a priori</i> information is used for detection in the next iteration (block 522), and the process returns to block 514. Otherwise, the soft decisions from the detector are further processed to obtain decoded data (block 524). The soft decisions may also be decoded prior to block 520, and the result of the decoding may be used in block 520 to determine whether or not to perform another iteration.

0068A packet may be encoded and demultiplexed into multiple subpackets that may be sent on the multiple data streams. A CRC may be used for each subpacket or each data stream. In this case, the CRC for each detected data stream may be checked after block 514, and the subsequent processing may be terminated if the CRC fails for any of the data stream(s) detected in block 514.

0069<figref idref="f0006"><b>FIG. 6</b></figref> shows an apparatus 600 for performing detection and decoding based on the reduced dimensionality detection scheme. Apparatus 600 includes means for performing receiver spatial processing on received symbols for multiple data streams to obtain detected symbols (block 612), means for performing detection independently for each of at least one data stream to obtain soft decisions for the stream (block 614), means for performing detection jointly for the remaining data streams to obtain soft decisions for these streams (block 616), means for decoding the soft decisions for the multiple data streams to obtain <i>a priori</i> information (block 618), means for performing an additional iteration of detection and decoding, if applicable, using the <i>a priori</i> information (block 620), and means for processing the soft decisions to obtain decoded data (block 622).

0070The number of hypotheses to consider in the joint LLR computation may be reduced by performing a search for candidate hypotheses using list sphere detection (LSD), which is also referred to as sphere decoding, spherical decoding, and so on. List sphere detection may be used to reduce complexity for the log-MAP detector in equation (6), the max-log-MAP detector in equation (7), and other types of detector. List sphere detection seeks to reduce the search space of the detector by discarding less likely hypotheses based on a cost function. As an example, the log-MAP and max-log-MAP detectors may consider only hypotheses that satisfy the following condition: <maths id="math0021" num="eq (13)"><math display="block"><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>≤</mo><msup><mi>r</mi><mn>2</mn></msup><mo>,</mo></math><img file="EP2262129A2_D0021.tif" /></maths> where ∥<b><u>y</u></b>-<b><u>H</u></b>·<b><u>s̃</u></b>∥² is the cost function and <i>r</i>² is a sphere radius or threshold used to retain or discard hypotheses from consideration.

0071The cost function in equation (13) may be expanded, as follows: <maths id="math0022" num="eq (14)"><math display="block"><mtable columnalign="left"><mtr><mtd><mi>J</mi><mfenced><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced></mtd><mtd><mo>=</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>=</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>=</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><msup><mfenced open="[" close="]" separators=""><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder></mfenced><mi>H</mi></msup><mo>⋅</mo><mfenced open="[" close="]" separators=""><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mo>+</mo><munder><mi mathvariant="bold">n</mi><mo>̲</mo></munder></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><msup><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mi>H</mi></msup><mo>⋅</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mo>+</mo><mi>C</mi></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd><mtd><mo>=</mo><msup><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mi>H</mi></msup><mo>⋅</mo><msup><munder><mi mathvariant="bold">R</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">R</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><munder><mi mathvariant="bold">s</mi><mo>̲</mo></munder><mo>-</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder></mfenced><mo>+</mo><mi>C</mi></mtd></mtr></mtable></math><img file="EP2262129A2_D0022.tif" /></maths><ul id="ul0009" list-style="none" compact="compact"><li>where <b><u>R</u></b> is an upper-triangular matrix obtained from QR decomposition of <b><u>H</u></b>; and</li><li>C is a constant, which may be omitted since it is not a function of <b><u>s̃</u></b>.</li></ul>

0072QR decomposition may be performed on the effective MIMO channel response matrix <b><u>H</u></b> to obtain an orthonormal matrix <b><u>Q</u></b> and an upper triangular matrix <b><u>R</u></b>, or <b><u>H</u></b> = <b><u>Q</u></b>·<b><u>R</u></b> where <b><u>Q</u><i>^H ·</i><u>Q</u></b> = <b><u>I</u></b>. The upper triangular matrix <b><u>R</u></b> contains zeros below the main diagonal. The fourth equality in equation (14) may be obtained based on the following: <b><u>H</u><i>^H</i>·<u>H</u>=[<u>Q</u>·<u>R</u>]<i>^H</i>·<u>Q</u>·<u>R</u>=<u>R</u><i>^H</i>·<u>Q</u><i>^H</i>·<u>Q</u>·<u>R</u>=<u>R</u><i>^H</i>·<u>R</u>.</b>

0073For the cost function in equation (14), the detected symbols may be used as the center point for the search. The cost function may then be expressed as: <maths id="math0023" num="eq (15)"><math display="block"><mi>J</mi><mfenced><mover><munder><mi mathvariant="normal">s</mi><mo>̲</mo></munder><mo>˜</mo></mover></mfenced><mo>=</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">R</mi><mo>̲</mo></munder><mo>⋅</mo><mfenced separators=""><mover><munder><mi mathvariant="normal">s</mi><mo>̲</mo></munder><mo>^</mo></mover><mo>-</mo><mover><munder><mi mathvariant="normal">s</mi><mo>̲</mo></munder><mo>˜</mo></mover></mfenced><mo>‖</mo></mrow><mn>2</mn></msup><mo>,</mo></math><img file="EP2262129A2_D0023.tif" /></maths> where <b><u>ŝ</u></b> may be obtained from equation (11) based on any receiver spatial processing technique (e.g., zero-forcing or MMSE). The cost function in equation (15) may be computed for 2^K hypothesized data vectors <b><u>s̃</u></b> that might have been transmitted for vector <b><u>s</u></b> to obtain 2^K cost values for these 2^K hypotheses. The hypothesized data vectors with cost values that are less than or equal to <i>r</i>² may be considered for LLR computation, e.g., in equation (6) or (7).

0074The structure of the upper triangular matrix <b><u>R</u></b> may be exploited to reduce the number of hypotheses for which to compute the cost function. Equation (15) may be expanded as follows: <maths id="math0024" num="eq (16)"><math display="block"><mi>J</mi><mo>=</mo><msup><mrow><mo>‖</mo><mfenced open="[" close="]"><mtable><mtr><mtd><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub></mtd><mtd><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>2</mn></mrow></msub></mtd><mtd><mo>⋯</mo></mtd><mtd><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mi mathvariant="normal">M</mi></mrow></msub></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><msub><mi>r</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msub></mtd><mtd><mo>⋯</mo></mtd><mtd><msub><mi>r</mi><mrow><mn>2</mn><mo>,</mo><mi mathvariant="normal">M</mi></mrow></msub></mtd></mtr><mtr><mtd><mo>⋮</mo></mtd><mtd><mo>⋮</mo></mtd><mtd><mo>⋱</mo></mtd><mtd><mo>⋮</mo></mtd></mtr><mtr><mtd><mn>0</mn></mtd><mtd><mn>0</mn></mtd><mtd><mo>⋯</mo></mtd><mtd><msub><mi>r</mi><mrow><mi mathvariant="normal">M</mi><mo>,</mo><mi mathvariant="normal">M</mi></mrow></msub></mtd></mtr></mtable></mfenced><mo>⋅</mo><mfenced open="[" close="]"><mtable><mtr><mtd><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>1</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>1</mn></msub></mfenced></mtd></mtr><mtr><mtd><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>2</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>2</mn></msub></mfenced></mtd></mtr><mtr><mtd><mspace width="1em" /></mtd></mtr><mtr><mtd><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mi mathvariant="normal">M</mi></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mi mathvariant="normal">M</mi></msub></mfenced></mtd></mtr></mtable></mfenced><mo>‖</mo></mrow><mn>2</mn></msup><mn>.</mn></math><img file="EP2262129A2_D0024.tif" /></maths>

0075For M = 4, equation (16) may be expressed as: <maths id="math0025" num="eq (17)"><math display="block"><mi>J</mi><mo>=</mo><msub><mi>T</mi><mn>1</mn></msub><mo>+</mo><msub><mi>T</mi><mn>2</mn></msub><mo>+</mo><msub><mi>T</mi><mn>3</mn></msub><mo>+</mo><msub><mi>T</mi><mn>4</mn></msub><mo>,</mo></math><img file="EP2262129A2_D0025.tif" /></maths> where <maths id="math0026" num=""><math display="block"><msub><mi>T</mi><mn>1</mn></msub><mo>=</mo><msup><mfenced open="|" close="|" separators=""><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>1</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>1</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>1</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>2</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>2</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>2</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>3</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>3</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>1</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>4</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>4</mn></msub></mfenced></mfenced><mn>2</mn></msup><mo>,</mo></math><img file="EP2262129A2_D0026.tif" /></maths><maths id="math0027" num=""><math display="block"><msub><mi>T</mi><mn>2</mn></msub><mo>=</mo><msup><mfenced open="|" close="|" separators=""><msub><mi>r</mi><mrow><mn>2</mn><mo>,</mo><mn>2</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>2</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>2</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>2</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>3</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>3</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>2</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>4</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>4</mn></msub></mfenced></mfenced><mn>2</mn></msup><mo>,</mo></math><img file="EP2262129A2_D0027.tif" /></maths><maths id="math0028" num=""><math display="block"><msub><mi>T</mi><mn>3</mn></msub><mo>=</mo><msup><mfenced open="|" close="|" separators=""><msub><mi>r</mi><mrow><mn>3</mn><mo>,</mo><mn>3</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>3</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>3</mn></msub></mfenced><mo>+</mo><msub><mi>r</mi><mrow><mn>3</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>4</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>4</mn></msub></mfenced></mfenced><mn>2</mn></msup><mo>,</mo></math><img file="EP2262129A2_D0028.tif" /></maths> and <maths id="math0029" num=""><math display="block"><msub><mi>T</mi><mn>4</mn></msub><mo>=</mo><msup><mfenced open="|" close="|" separators=""><msub><mi>r</mi><mrow><mn>4</mn><mo>,</mo><mn>4</mn></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mn>4</mn></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mn>4</mn></msub></mfenced></mfenced><mn>2</mn></msup><mn>.</mn></math><img file="EP2262129A2_D0029.tif" /></maths>

0076Equation (17) may be generalized for any value of M, as follows: <maths id="math0030" num="eq (18)"><math display="block"><mi>J</mi><mo>=</mo><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mi mathvariant="normal">M</mi></mrow><mn>1</mn></munderover></mstyle><msub><mi>T</mi><mi>i</mi></msub><mo>,</mo></math><img file="EP2262129A2_D0030.tif" /></maths> where <maths id="math0031" num="eq (19)"><math display="block"><msub><mi>T</mi><mi>i</mi></msub><mo>=</mo><msup><mfenced open="|" close="|" separators=""><mstyle displaystyle="true"><munderover><mo>∑</mo><mrow><mi>j</mi><mo>=</mo><mi>i</mi></mrow><mi>M</mi></munderover></mstyle><msub><mi>r</mi><mrow><mi>i</mi><mo>,</mo><mi>j</mi></mrow></msub><mo>⋅</mo><mfenced separators=""><msub><mover><mi>s</mi><mo>^</mo></mover><mi>j</mi></msub><mo>-</mo><msub><mover><mi>s</mi><mo>˜</mo></mover><mi>j</mi></msub></mfenced></mfenced><mn>2</mn></msup><mn>.</mn></math><img file="EP2262129A2_D0031.tif" /></maths>

0077As shown in equations (18) and (19), the cost function may be decomposed into a sum of M terms <i>T</i>₁ through <i>T</i>_M. Term <i>T</i>_M is only dependent on detected symbol <i>ŝ</i>_M for stream M, term <i>T</i>_M-1 is dependent on detected symbols <i>ŝ</i>_M-1 and <i>ŝ</i>_M for streams M-1 and M, and so on, and term <i>T</i>₁ is dependent on detected symbols <i>ŝ</i>₁ through <i>ŝ</i>_M for all M streams.

0078The cost function may be computed incrementally in M levels, one term <i>T_i</i> for each level, starting with the last term <i>T</i>_M for the first level. This is indicated by the reverse summation for <i>J</i> in equation (18), which starts with <i>i</i> = M. For each level, <i>T_i</i> is computed for all hypotheses applicable for that level, and the cost function is updated.

0079The cost function may be computed by considering one additional symbol at a time, starting with <i>ŝ</i>_M and ending with <i>ŝ</i>₁. To improve search performance, the streams may be sorted such that <i>ŝ</i>_M corresponds to the best stream (e.g., with the highest SNR) and <i>ŝ</i>₁ corresponds to the worst stream (e.g., with the lowest SNR). The received vector <b><u>y</u></b> and the channel response matrix <b><u>H</u></b> may be reordered to achieve the desired ordering for the detected vector <b><u>ŝ</u></b>.

0080The LSD search may be performed in various manners. In a first embodiment, all hypotheses with cost values equal to or less than <i>r</i>² are retained, and all other hypotheses are discarded. In a second embodiment, only B best hypotheses are retained at each level, and all other hypotheses are discarded. For both embodiments, the total number of hypotheses to consider is reduced by discarding hypotheses with high cost values.

0081The LSD search may be performed as follows. For the first level, a list <b>P</b>_M is formed with 2^{Q<sub2>M</sub2>} hypothesized data symbols <i>s̃</i>_M that might have been transmitted for data symbol <i>s</i>_M. <i>T</i>_M is computed for the 2^{Q<sub2>M</sub2>} hypothesized data symbols <i>s̃</i>_M in list <b>P</b>_M as shown in equation (19) to obtain 2^{Q<sub2>M</sub2>} cost values. For the first embodiment, all hypothesized data symbols with cost values less than or equal to <i>r</i>² are retained and stored in a candidate list <b>C</b>_M. For the second embodiment, up to B hypothesized data symbols with the lowest cost values that are smaller than or equal to <i>r</i>² are retained and stored in candidate list <b>C</b>_M. For the second embodiment, hypothesized data symbols with cost values smaller than or equal to <i>r</i>² may be discarded if these cost values are not among the B lowest cost values. For both embodiments, all other hypothesized data symbols are discarded, which has the effect of pruning all hypothesized data vectors <b><u>s̃</u></b> containing the discarded symbols.

0082For the second level, a list <b>P</b>_M-1 is formed with 2^{Q<sub2>M</sub2>-1} hypothesized data symbols <i>s̃</i>_M-1 that might have been transmitted for data symbol <i>s</i>_M-1. <i>T</i>_M-1 is computed for all valid hypothesized symbol pairs (<i>s̃</i>_M-1, <i>s̃</i>_M) and summed with <i>T</i>_M to obtain cost values for these hypothesized symbol pairs. The valid hypothesized symbol pairs include all possible combinations of each symbol in candidate list <b>C</b>_M with each symbol in list <b>P</b>_M-1. The updated cost values may be computed as: <i>J</i>_M-1 = <i>T</i>_M-1 + <i>T</i>_M. For the first embodiment, all hypothesized symbol pairs with cost values smaller than or equal to <i>r</i>² are retained and stored in a candidate list <b>C</b>_M-1. For the second embodiment, up to B hypothesized symbol pairs with the lowest cost values that are smaller than or equal to <i>r</i>² are retained and stored in candidate list <b>C</b>_M-1. For both embodiments, all other hypothesized symbol pairs are discarded.

0083Each of the remaining levels may be evaluated in similar manner. A list <b>P_i</b> is formed with 2^Q<i>_i</i> hypothesized data symbols <i>s̃_i</i> that might have been transmitted for data symbol <i>s_i</i>. <i>T_i</i> is computed for all valid hypothesized symbol sets (<i>s̃_i</i>,..., <i>s̃</i>_M) and summed with <i>T</i>_<i>i</i>+1 through <i>T</i>_M to obtain cost values for these hypothesized symbol sets. The valid hypothesized symbol sets include all possible combinations of each hypothesis in candidate list <b>C</b>_<i>i</i>+1 with each symbol in list <b>P</b><i>_i</i>. The updated cost values may be computed as: <i>J_i</i> = <i>T_l</i> + ... + <i>T</i>_M. For the first embodiment, all hypothesized symbol sets with cost values smaller than or equal to <i>r</i>² are retained and stored in a candidate list <b>C</b><i>_i</i>. For the second embodiment, up to B hypothesized symbol sets with the lowest cost values that are smaller than or equal to <i>r</i>² are retained and stored in candidate list <b>C<i>_i</i></b>. For both embodiments, all other hypothesized symbol sets are discarded.

0084After all M levels have been evaluated, extrinsic LLRs may be computed for all hypotheses stored in candidate list <b>C</b>₁, e.g., based on the max-log-MAP detector, as follows: <maths id="math0032" num="eq (20)"><math display="block"><msub><mi>L</mi><mi>e</mi></msub><mfenced><msub><mi>b</mi><mi>k</mi></msub></mfenced><mo>≈</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msubsup><mi mathvariant="bold">C</mi><mi>k</mi><mo>+</mo></msubsup></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mfrac><mo>⋅</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced><mo>-</mo><mstyle displaystyle="false"><mfrac><mn>1</mn><mn>2</mn></mfrac></mstyle><munder><mi>max</mi><mrow><munder><mover><mi mathvariant="bold">b</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>:</mo><msubsup><mi mathvariant="bold">C</mi><mi>k</mi><mo>-</mo></msubsup></mrow></munder><mfenced open="{" close="}" separators=""><mo>-</mo><mfrac><mn>1</mn><msubsup><mi>σ</mi><mi>n</mi><mn>2</mn></msubsup></mfrac><mo>⋅</mo><msup><mrow><mo>‖</mo><munder><mi mathvariant="bold">y</mi><mo>̲</mo></munder><mo>-</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mover><mi mathvariant="bold">s</mi><mo>˜</mo></mover><mo>̲</mo></munder><mo>‖</mo></mrow><mn>2</mn></msup><mo>+</mo><msubsup><mover><munder><mi mathvariant="bold">b</mi><mo>̲</mo></munder><mo>˜</mo></mover><mfenced open="[" close="]"><mi>k</mi></mfenced><mi>T</mi></msubsup><mo>⋅</mo><msub><munder><mi mathvariant="bold">L</mi><mo>̲</mo></munder><mrow><mi>a</mi><mo>,</mo><mfenced open="[" close="]"><mi>k</mi></mfenced></mrow></msub></mfenced><mn>.</mn></math><img file="EP2262129A2_D0032.tif" /></maths><ul id="ul0010" list-style="none"><li>where <maths id="math0033" num=""><math display="inline"><msubsup><mi mathvariant="bold">C</mi><mi>k</mi><mo>+</mo></msubsup></math><img file="EP2262129A2_D0033.tif" /></maths> is a subset of candidate list <b>C</b>₁ and contains hypotheses for which <i>b_k</i> = +1; and</li><li><maths id="math0034" num=""><math display="inline"><msubsup><mi mathvariant="bold">C</mi><mi>k</mi><mo>-</mo></msubsup></math><img file="EP2262129A2_D0034.tif" /></maths> is a subset of candidate list <b>C</b>₁ and contains hypotheses for which <i>b_k</i> = -1.</li></ul>

0085The extrinsic LLRs may also be computed based on the log-MAP detector or some other type of detector. The cost values already computed for the candidate hypotheses may be used to compute the extrinsic LLRs for these hypotheses. For clarity, the description above uses different candidate lists for different levels. A single candidate list <b>C</b> may be used for all M levels and may be updated at each level.

0086<figref idref="f0007"><b>FIG. 7</b></figref> shows an exemplary search tree for the second embodiment, which retains the B best hypotheses at each level. For this example, M = 4, four terms <i>T</i>₁ through <i>T</i>₄ are computed, B = 2, and the candidate list <b>C</b> contains up to two best hypotheses at each level. For the first level with <i>i</i> = 4, <i>T</i>₄ is computed for 2^{Q<sub2>4</sub2>} hypotheses for 2^{Q<sub2>4</sub2>} possible data symbols that might have been transmitted for data symbol <i>s</i>₄, which are denoted as <i>s̃</i>₄(1) through <i>s̃</i>₄(2^{Q<sub2>4</sub2>}) in <figref idref="f0007">FIG. 7</figref>. The two best hypotheses are shown with black filled nodes. For the second level with <i>i</i> = 3, <i>T</i>₃ is computed for B - 2^{Q<sub2>3</sub2>} hypotheses for B·2^{Q<sub2>3</sub2>} possible symbol pairs that might have been transmitted for data symbols <i>s</i>₃ and <i>s</i>₄. The two best hypotheses are shown with black filled nodes. For the third level with <i>i</i> = 2, <i>T</i>₂ is computed for B·2^{Q<sub2>2</sub2>} hypotheses for B·2^{Q<sub2>2</sub2>} possible symbol sets that might have been transmitted for data symbols <i>s</i>₂, <i>s</i>₃ and <i>s</i>₄. The two best hypotheses are shown with black filled nodes. For the last level with <i>i</i> = 1, <i>T</i>₁ is computed for B·2^{Q<sub2>1</sub2>} hypotheses for B·2^{Q<sub2>1</sub2>} possible symbol sets that might have been transmitted for data symbols <i>s</i>₁, <i>s</i>₂, <i>s</i>₃ and <i>s</i>₄. The two best hypotheses are shown with black filled nodes. The set of symbols that yields the lowest cost value is shown by the heavy line.

0087In an embodiment, the number of candidate hypotheses to store in list <b>C</b> is a fixed value that may be selected based on a tradeoff between detection performance, complexity, and/or other considerations. This fixed value (B) may be for each level, as described above. This fixed value may also be for each node of a given level, in which case B^M-i·2^{Q<sub2>i</sub2>} hypotheses are considered per level. In another embodiment, the number of candidate hypotheses is configurable and may be selected based on signal constellation size, iteration number, detection performance, complexity, and/or other considerations. For example, B may be a function of signal constellation size so that more candidate hypotheses are stored for larger signal constellations to ensure sufficient accuracy in the LLR computation. B may also be constrained to be equal to or larger than some minimum value (e.g., B_min = 2), which ensures that at least B_min candidate hypotheses are stored at each level.

0088Two embodiments for computing cost for list sphere detection have been described above. The cost computation may also be performed in other manners.

0089List sphere detection is one search technique for reducing the number of hypotheses to consider for LLR computation. Other techniques may also be used to reduce the number of hypotheses for LLR computation. In another embodiment, a Markov chain Monte Carlo (MCMC) technique is used to generate a list of candidate hypotheses. The MCMC technique considers the M elements in data vector <b><u>s</u></b> in a sequential manner, evaluates one hypothesis for each element, and cycles through these M elements for multiple iterations. The list sphere detection and MCMC techniques are known in the art and described in various papers.

0090In another aspect, the receiver performs LLR computation independently for each of D best detected symbols, performs LLR computation jointly for the M - D remaining detected symbols, and reduces the number of hypotheses to consider for the joint LLR computation by performing a search using LSD, MCMC, or some other search technique. This detection scheme is referred to as a reduced order detection scheme and may be used for the single-pass receiver shown in <figref idref="f0003">FIG. 3</figref> and the iterative receiver shown in <figref idref="f0004">FIG. 4</figref>. For the reduced order detection scheme, dimensionality is reduced from M to M - D by performing per-stream LLR computation for the D best streams, and the number of hypotheses to consider for the M - D remaining streams may be reduced from an upper bound of <maths id="math0035" num=""><math display="inline"><msup><mn>2</mn><mrow><munderover><mo>∑</mo><mrow><mi>i</mi><mo>=</mo><mn>1</mn></mrow><mrow><mi mathvariant="normal">M</mi><mo>-</mo><mi mathvariant="normal">D</mi></mrow></munderover><msub><mi mathvariant="normal">Q</mi><mi>i</mi></msub></mrow></msup></math><img file="EP2262129A2_D0035.tif" /></maths> by performing a search. D may be adaptively selected based on channel conditions (e.g., SNRs) and/or some other factors. The SNR information may be readily obtained from the receiver spatial processing that provides the detected symbols used for the center point of an LSD search.

0091<figref idref="f0008"><b>FIG. 8</b></figref> shows a process 800 for performing detection and decoding based on the reduced order detection scheme. Receiver spatial processing is performed on a set of received symbols (e.g., vector <b><u>y</u></b>) to obtain a set of detected symbols (e.g., vector <b><u>ŝ</u></b>) for a set of data symbols (e.g., vector <b><u>s</u></b>) transmitted via a MIMO channel (block 812). Extrinsic LLRs are computed independently for each of at least one data symbol based on a corresponding detected symbol and <i>a priori</i> LLRs, if any, from the decoder (block 814). A list of candidate hypotheses is determined for the remaining data symbols, e.g., by performing a search using LSD, MCMC, or some other technique (block 816). Each candidate hypothesis corresponds to a different combination of symbols hypothesized to have been transmitted for the remaining data symbols. Extrinsic LLRs are then computed jointly for the remaining data symbols with the list of candidate hypotheses (block 818). The extrinsic LLRs for all data symbols are decoded to obtain <i>a priori</i> LLRs for the detector (block 820).

0092A determination is then made whether to perform another iteration of detection and decoding (block 822). If the answer is 'Yes', then <i>a priori</i> LLRs are computed to be used for LLR computation in the detector in the next iteration (block 824), and the process returns to block 814. Otherwise, the extrinsic LLRs from the detector are processed to obtain decoded data (block 826).

0093<figref idref="f0009"><b>FIG. 9</b></figref> shows an apparatus 900 for performing detection and decoding based on the reduced order detection scheme. Apparatus 900 includes means for performing receiver spatial processing on a set of received symbols to obtain a set of detected symbols for a set of data symbols transmitted via a MIMO channel (block 912), means for computing extrinsic LLRs independently for each of at least one data symbol based on a corresponding detected symbol and <i>a priori</i> LLRs, if any, from the decoder (block 914), means for determining a list of candidate hypotheses for the remaining data symbols by performing a search (block 916), means for computing extrinsic LLRs jointly for the remaining data symbols with the list of candidate hypotheses (block 918), means for decoding the extrinsic LLRs for all data symbols to obtain <i>a priori</i> LLRs (block 920), means for performing an additional iteration of LLR computation and decoding, if applicable, using the <i>a priori</i> LLRs (block 922), and means for processing the extrinsic LLRs from the detector to obtain decoded data (block 924).

0094For the iterative receiver, the search for candidate hypotheses may be performed in various manners. In an embodiment, the search is performed for only the first iteration to obtain a list of candidate hypotheses, and this candidate list is used for all subsequent iterations. For this embodiment, the extrinsic LLRs for each subsequent iteration are computed with the <i>a priori</i> LLRs from the decoder and for the candidate hypotheses determined in the first iteration. In another embodiment, the search is performed for each iteration. In yet another embodiment, the search is performed for each iteration until a termination condition is encountered. This termination condition may be triggered, e.g., after a predetermined number of iterations has been completed, if the search provides the same list of candidate hypotheses for two consecutive iterations, and so on. For the embodiments in which the search is performed for multiple iterations, the threshold (e.g., the sphere radius) may be a fixed value for all iterations or may be a configurable value that may be set for each iteration based on, e.g., the <i>a priori</i> information from the decoder.

0095For the reduced order detection scheme, the reduction in complexity relative to the optimal log-MAP or max-log-MAP detector is dependent on the complexity of the search. For an LSD search, the complexity is determined by the number of nodes visited in the search tree, which in turn is dependent on various factors such as the number of hypotheses to store at each level (e.g., the value for B), the sphere radius <i>r</i>², the specific channel response matrix <b><u>H</u></b>, the SNR, and so on.

0096In another reduced complexity detection scheme, the receiver performs (1) per-stream LLR computation for all M streams for the first iteration and (2) joint LLR computation for the M - D worst streams or all M streams for a subsequent iteration, if needed, e.g., if the packet is decoded in error.

0097For the iterative receiver, the channel estimates may be updated during the iterative detection and decoding process to obtain improved channel estimates. For example, if pilot symbols are received and monitored multiple times during the iterative process, then the effective SNR of the channel estimates may be improved over time by performing averaging and/or other processing. The improved channel estimates may be used for receiver spatial processing, e.g., as shown in equations (8) through (10), for LLR computation, e.g., as shown in equations (6), (7) and (12), for cost computation for a search of candidate hypotheses, e.g., as shown in equations (18) and (19).

0098Various reduced complexity detection schemes have been described above. These schemes reduce the number of hypotheses to consider for the LLR computation while achieving good error rate performance that is close to the performance of the optimal detector.

0099Decoder 320 in <figref idref="f0003">FIG. 3</figref> and decoder 420 in <figref idref="f0004">FIG. 4</figref> may be implemented in various manners depending on the coding scheme(s) used at transmitter 110. Decoder 420 receives soft decision inputs and generates soft decision outputs for MIMO detector 410 and may be a soft-output Viterbi algorithm (SOVA) decoder if a convolutional code is used at transmitter 110, a Turbo decoder if a parallel or serial concatenated Turbo code is used, and so on. Decoder 320 may be a Viterbi decoder or a SOVA decoder for a convolutional code, a Turbo decoder for a Turbo code, and so on. A Turbo decoder may be a MAP decoder that may implement a BCJR soft-input soft-output MAP algorithm or a lower complexity derivative. These various types of decoder are known in the art and described in various literatures. For example, the SOVA decoder is described by <nplcit id="ncit0001" npl-type="s"><text>J. Hagenauer et al. in a paper entitled "A Viterbi Algorithm with Soft-Decision Outputs and its Applications," IEEE Globecom, 1989, pp. 47.1.1-47.1.7</text></nplcit>. The MAP decoder is described by<nplcit id="ncit0002" npl-type="s"><text> L. R. Bahl et al. in a paper entitled "Optimal Decoding of Linear Codes for Minimizing Symbol Error Rate," IEEE Transaction on Information Theory, March 1974, vol. 20, pp. 284-287</text></nplcit>.

0100The detection and decoding techniques described herein may be used for various MIMO transmission schemes, which may also be referred to as transmission modes, spatial modes, and so on. Table 1 lists some exemplary transmission modes and their short descriptions. The steered mode may also be called a beamforming mode, an eigensteering mode, a MIMO mode with beamforming, and so on. The unsteered mode may also be called a basic MIMO mode. The spatial spreading mode may also be called a pseudo-random transmit steering mode, a spatial expansion mode, and so on,

0101<tables id="tabl0001" num="0001"><table frame="all"><title>Table 1</title><tgroup cols="2"><colspec colnum="1" colname="col1" colwidth="35mm" /><colspec colnum="2" colname="col2" colwidth="131mm" /><thead><row><entry align="center" valign="middle"><b>Transmission Mode</b></entry><entry align="center" valign="middle"><b>Description</b></entry></row></thead><tbody><row><entry align="center" valign="middle">Steered</entry><entry valign="middle">Multiple data streams are transmitted on multiple orthogonal spatial channels (or eigenmodes) of a MIMO channel.</entry></row><row><entry align="center" valign="middle">Unsteered</entry><entry valign="middle">Multiple data streams are transmitted on multiple spatial channels (e.g., from multiple transmit antennas).</entry></row><row><entry align="center" valign="middle">Spatial spreading</entry><entry valign="middle">Multiple data streams are spatially spread across the spatial channels to achieve similar performance for all data streams.</entry></row></tbody></tgroup></table></tables>

0102Each transmission mode has different capabilities and requirements. The steered mode typically provides better performance but requires spatial processing at transmitter 110 and receiver 150. The unsteered mode requires no spatial processing at transmitter 110. For example, transmitter 110 may transmit one data stream from each transmit antenna. The spatial spreading mode transmits M data streams with different spatial mapping matrices so that these data streams observe an ensemble of effective channels and achieve similar performance. A suitable transmission mode may be selected based on the availability of channel state information, the capabilities of the transmitter and receiver, and so on.

0103For the steered mode, data is transmitted on up to M eigenmodes of the MIMO channel, which may be obtained by diagonalizing the MIMO channel response matrix <b><u>H</u></b> via singular value decomposition of <b><u>H</u></b> or eigenvalue decomposition of a correlation matrix of <b><u>H</u></b>, which is <b><u>A</u></b> = <b><u>H</u></b><i>^H</i>·<b><u>H</u></b>. The eigenvalue decomposition of <b><u>A</u></b> may be expressed as: <maths id="math0036" num="eq (21)"><math display="block"><munder><mi mathvariant="bold">A</mi><mo>̲</mo></munder><mo>=</mo><msup><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>⋅</mo><munder><mi mathvariant="bold">H</mi><mo>̲</mo></munder><mo>=</mo><munder><mi mathvariant="bold">E</mi><mo>̲</mo></munder><mo>⋅</mo><munder><mi>Λ</mi><mo>̲</mo></munder><mo>⋅</mo><msup><munder><mi mathvariant="bold">E</mi><mo>̲</mo></munder><mi>H</mi></msup><mo>,</mo></math><img file="EP2262129A2_D0036.tif" /></maths><ul id="ul0011" list-style="none" compact="compact"><li>where <b><u>E</u></b> is a T×T unitary matrix of eigenvectors of <b><u>A</u></b> ; and</li><li>Λ is a T×T diagonal matrix of eigenvalues of <b><u>A</u></b> .</li></ul> Transmitter 110 may perform spatial processing with the eigenvectors in <b><u>E</u></b> to transmit data on the M eigenmodes of <b><u>H</u></b>. The diagonal matrix Λ contains possible non-negative real values along the diagonal and zeros elsewhere. These diagonal entries are referred to as eigenvalues of <b><u>A</u></b> and represent the power gains for the M eigenmodes.

0104Table 2 shows the transmitter spatial processing for the three transmission modes and the effective MIMO channel response matrix for each transmission mode. In Table 2, the subscript "es" denotes the steered mode (or eigensteering), "us" denotes the unsteered mode, and "ss" denotes the spatial spreading mode. <tables id="tabl0002" num="0002"><table frame="all"><title>Table 2</title><tgroup cols="4"><colspec colnum="1" colname="col1" colwidth="30mm" /><colspec colnum="2" colname="col2" colwidth="26mm" /><colspec colnum="3" colname="col3" colwidth="30mm" /><colspec colnum="4" colname="col4" colwidth="31mm" /><thead><row><entry align="center" valign="middle" /><entry align="center" valign="middle"><b>Steered mode</b></entry><entry align="center" valign="middle"><b>Unsteered mode</b></entry><entry align="center" valign="middle"><b>Spatial spreading</b></entry></row></thead><tbody><row><entry align="center" valign="middle">Transmitter</entry><entry align="center" valign="middle"><b><u>x</u>_es</b> = <b><u>E</u></b>·<b><u>s</u></b></entry><entry align="center" valign="middle"><b><u>x</u></b>_us = <b><u>s</u></b></entry><entry align="center" valign="middle"><b><u>x</u>_ss</b> = <b><u>V</u></b>·<b><u>s</u></b></entry></row><row><entry align="center" valign="middle">Effective Channel</entry><entry align="center" valign="middle"><b><u>H</u></b>_es = <b><u>H</u></b>_ch·<b><u>E</u></b></entry><entry align="center" valign="middle"><b><u>H</u></b>_us = <b><u>H</u></b>_ch</entry><entry align="center" valign="middle"><b><u>H</u></b>_ss = <b><u>H</u></b>_ch·<b><u>V</u></b></entry></row></tbody></tgroup></table></tables>

0105For a MIMO system with multiple subbands, the transmitter spatial processing shown in Table 2 may be performed for each subband <i>l</i>. In equation (1), <b><u>P</u></b>(<i>l</i>) = <b><u>E</u></b>(<i>l</i>) for the steered mode, <b><u>P</u></b>(<i>l</i>) = <b><u>I</u></b> for the unsteered mode, and <b><u>P</u></b>(<i>l</i>) = <b><u>V</u></b>(<i>l</i>) for the spatial spreading mode. <b><u>V</u></b>(<i>l</i>) is a T×T spatial mapping matrix used for spatial spreading and may be generated based on a Hadamard matrix, a Fourier matrix, and so on.

0106For a MIMO system with multiple subbands, the M eigenvalues for each subband <i>l</i> may be ordered from largest to smallest, so that the eigenmodes of <b><u>H</u></b>(<i>l</i>) are ranked from highest SNR to lowest SNR. Wideband eigenmode <i>m</i> may be formed with the <i>m</i>-th eigenmode for each of the L subbands. The principal wideband eigenmode (with <i>m</i> = 1) is associated with the largest eigenvalues for all L subbands, the second wideband eigenmode (with <i>m</i> = 2) is associated with the second largest eigenvalues for all L subbands, and so on. M data streams may be sent on the M wideband eigenmodes.

0107The principal wideband eigenmode has the highest average SNR and typically also has less SNR variability across time and frequency. Conversely, the weakest wideband eigenmode has the lowest average SNR and typically has more SNR variability. The techniques described herein may be used for data transmission on the M wideband eigenmodes. In an embodiment, the receiver may perform per-stream LLR computation for one or more of the strongest wideband eigenmodes and joint LLR computation for the remaining wideband eigenmodes. The number of hypotheses to consider for the joint LLR computation may be reduced by performing a search using LSD, MCMC, or some other search technique.

0108The detection and decoding techniques described herein may be implemented by various means. For example, these techniques may be implemented in hardware, firmware, software, or a combination thereof. For a hardware implementation, the processing units used to perform detection and decoding may be implemented within one or more application specific integrated circuits (ASICs), digital signal processors (DSPs), digital signal processing devices (DSPDs), programmable logic devices (PLDs), field programmable gate arrays (FPGAs), processors, controllers, micro-controllers, microprocessors, electronic devices, other electronic units designed to perform the functions described herein, or a combination thereof.

0109For a firmware and/or software implementation, the techniques may be implemented with modules (e.g., procedures, functions, and so on) that perform the functions described herein. The software codes may be stored in a memory (e.g., memory 192 in <figref idref="f0001">FIG. 1</figref>) and executed by a processor (e.g., processor 190). The memory may be implemented within the processor or external to the processor.

0110The previous description of the disclosed embodiments is provided to enable any person skilled in the art to make or use the present invention. Various modifications to these embodiments will be readily apparent to those skilled in the art, and the generic principles defined herein may be applied to other embodiments without departing from the spirit or scope of the invention. Thus, the present invention is not intended to be limited to the embodiments shown herein but is to be accorded the widest scope consistent with the principles and novel features disclosed herein.

FURTHER SUMMARY OF THE INVENTION

0111<ol id="ol0001" ol-style=""><li>1. An apparatus comprising: <ul id="ul0012" list-style="none" compact="compact"><li>at least one processor configured to perform detection independently for each of at least one data stream selected from among multiple data streams, and to perform detection jointly for remaining data streams among the multiple data streams; and</li><li>a memory coupled to the at least one processor.</li></ul></li><li>2. The apparatus of 1, wherein the at least one processor is configured to derive soft decisions independently for each of the at least one data stream, and to derive soft decisions jointly for the remaining data streams.</li><li>3. The apparatus of 1, wherein the at least one processor is configured to perform receiver spatial processing for the at least one data stream to obtain at least one detected symbol stream, and to derive soft decisions independently for each of the at least one detected symbol stream.</li><li>4. The apparatus of 3, wherein the at least one processor is configured to perform receiver spatial processing based on a zero-forcing (ZF) technique or a minimum mean square error (MMSE) technique.</li><li>5. The apparatus of 1, wherein the at least one processor is configured to compute log-likelihood ratios (LLRs) for code bits for each of the at least one data stream independent of other data streams, and to compute LLRs for code bits for the remaining data streams jointly.</li><li>6. The apparatus of 5, wherein the at least one processor is configured to compute the LLRs based on a maximum <i>a posteriori</i> probability (MAP) detector.</li><li>7. The apparatus of 2, wherein the at least one processor is configured to decode the soft decisions for the multiple data streams to obtain <i>a priori</i> information, and to perform detection for an additional iteration using the <i>a priori</i> information.</li><li>8. The apparatus of 2, wherein the at least one processor is configured to decode the soft decisions based on a soft-output Viterbi algorithm (SOVA) decoder or a maximum <i>a posteriori</i> probability (MAP) decoder.</li><li>9. The apparatus of 1, wherein the at least one processor is configured to check each of the at least one data stream after the independent detection, and to perform detection jointly for the remaining data streams if the at least one data stream passes the check.</li><li>10. The apparatus of 1, wherein the at least one data stream has highest signal-to-noise-and-interference ratios (SNRs) among SNRs for the multiple data streams.</li><li>11. A method comprising: <ul id="ul0013" list-style="none" compact="compact"><li>performing detection independently for each of at least one data stream selected from among multiple data streams; and</li><li>performing detection jointly for remaining data streams among the multiple data streams.</li></ul></li><li>12. The method of 11, wherein the performing detection independently comprises deriving soft decisions independently for each of the at least one data stream, and wherein the performing detection jointly comprises deriving soft decisions jointly for the remaining data streams.</li><li>13. The method of 12, further comprising: <ul id="ul0014" list-style="none" compact="compact"><li>decoding the soft decisions for the multiple data streams to obtain <i>a priori</i> information; and</li><li>performing detection for an additional iteration using the <i>a priori</i> information.</li></ul></li><li>14. An apparatus comprising: <ul id="ul0015" list-style="none" compact="compact"><li>means for performing detection independently for each of at least one data stream selected from among multiple data streams; and</li><li>means for performing detection jointly for remaining data streams among the multiple data streams.</li></ul></li><li>15. The apparatus of 14, wherein the means for performing detection independently comprises means for deriving soft decisions independently for each of the at least one data stream, and wherein the means for performing detection jointly comprises means for deriving soft decisions jointly for the remaining data streams.</li><li>16. The apparatus of 15, further comprising: <ul id="ul0016" list-style="none" compact="compact"><li>means for decoding the soft decisions for the multiple data streams to obtain <i>a priori</i> information; and</li><li>means for performing detection for an additional iteration using the <i>a priori</i> information.</li></ul></li><li>17. An apparatus comprising: <ul id="ul0017" list-style="none" compact="compact"><li>at least one processor configured to compute log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel, and to compute LLRs jointly for remaining data symbols in the set of data symbols; and</li><li>a memory coupled to the at least one processor.</li></ul></li><li>18. The apparatus of 17, wherein the at least one processor is configured to compute the LLRs for the remaining data symbols by using fixed values for the at least one data symbol.</li><li>19. The apparatus of 17, wherein the at least one processor is configured to compute the LLRs for the remaining data symbols by excluding the at least one data symbol.</li><li>20. The apparatus of 17, wherein the at least one processor is configured to compute the LLRs based on a maximum <i>a posteriori</i> probability (MAP) detector.</li><li>21. The apparatus of 1, wherein the at least one processor is configured to decode the LLRs for the set of data symbols to obtain <i>a priori</i> LLRs, and to jointly compute the LLRs for the remaining data symbols for an additional iteration using the <i>a priori</i> LLRs.</li><li>22. The apparatus of 17, wherein the at least one processor is configured to perform receiver spatial processing on a set of received symbols to obtain at least one detected symbol for the at least one data symbol, and to compute the LLRs for each of the at least one detected symbol.</li><li>23. The apparatus of 17, wherein the at least one processor is configured to derive a channel estimate based on a channel response matrix for the MIMO channel and a spatial mapping matrix used to transmit the set of data symbols, to derive a spatial filter matrix based on the channel estimate, to perform receiver spatial processing on a set of received symbols based on the spatial filter matrix to obtain at least one detected symbol, and to compute the LLRs for each the at least one detected symbol.</li><li>24. The apparatus of 17, wherein the at least one processor is configured to compute LLRs separately for each of multiple sets of data symbols transmitted via the MIMO channel on multiple frequency subbands.</li><li>25. A method comprising: <ul id="ul0018" list-style="none" compact="compact"><li>computing log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel; and</li><li>computing LLRs jointly for remaining data symbols in the set of data symbols.</li></ul></li><li>26. The method of 25, further comprising: <ul id="ul0019" list-style="none" compact="compact"><li>decoding the LLRs for the set of data symbols to obtain <i>a priori</i> LLRs; and</li><li>jointly computing the LLRs for the remaining data symbols for an additional iteration using the <i>a priori</i> LLRs.</li></ul></li><li>27. The method of 25, further comprising: <ul id="ul0020" list-style="none" compact="compact"><li>computing LLRs separately for each of multiple sets of data symbols transmitted via the MIMO channel on multiple frequency subbands.</li></ul></li><li>28. An apparatus comprising: <ul id="ul0021" list-style="none" compact="compact"><li>means for computing log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel; and</li><li>means for computing LLRs jointly for remaining data symbols in the set of data symbols.</li></ul></li><li>29. The apparatus of 28, further comprising: <ul id="ul0022" list-style="none" compact="compact"><li>means for decoding the LLRs for the set of data symbols to obtain <i>a priori</i> LLRs; and</li><li>means for jointly computing the LLRs for the remaining data symbols for an additional iteration using the <i>a priori</i> LLRs.</li></ul></li><li>30. The apparatus of 28, further comprising: <ul id="ul0023" list-style="none" compact="compact"><li>means for computing LLRs separately for each of multiple sets of data symbols transmitted via the MIMO channel on multiple frequency subbands.</li></ul></li><li>31. An apparatus comprising: <ul id="ul0024" list-style="none" compact="compact"><li>at least one processor configured to perform detection independently for each of at least one data stream selected from among multiple data streams, to perform detection jointly for remaining data streams among the multiple data streams, to perform decoding for the multiple data streams, and to perform detection independently for each of the at least one data stream, to perform detection jointly for the remaining data streams, and to perform decoding for the multiple data streams for at least one additional iteration; and</li><li>a memory coupled to the at least one processor.</li></ul></li><li>32. An apparatus comprising: <ul id="ul0025" list-style="none" compact="compact"><li>at least one processor configured to compute log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel, to determine a list of candidate hypotheses for remaining data symbols in the set of data symbols, and to compute LLRs jointly for the remaining data symbols with the list of candidate hypotheses; and</li><li>a memory coupled to the at least one processor.</li></ul></li><li>33. The apparatus of 32, wherein the at least one processor is configured to determine the list of candidate hypotheses using list sphere detection.</li><li>34. The apparatus of 32, wherein the at least one processor is configured to determine the list of candidate hypotheses using Markov chain Monte Carlo technique.</li><li>35. The apparatus of 32, wherein the at least one processor is configured to select one of the remaining data symbols at a time for consideration and, after selecting each remaining data symbol, to determine the list of candidate hypotheses for all selected remaining data symbols based on a cost function.</li><li>36. The apparatus of 35, wherein the list of candidate hypotheses includes at most B best hypotheses for the selected remaining data symbols, where B ≥ 1.</li><li>37. The apparatus of 35, wherein the selected remaining data symbols correspond to a plurality of nodes in a search tree, and wherein the list of candidate hypotheses includes at most B best hypotheses for each of the plurality of nodes, where B ≥ 1.</li><li>38. The apparatus of 36, wherein B is selected based on a modulation scheme used for the set of data symbols.</li><li>39. The apparatus of 35, wherein the list of candidate hypotheses includes at a minimum B_min best hypotheses for the selected remaining data symbols, where B_min ≥ 1.</li><li>40. The apparatus of 35, wherein the list of candidate hypotheses includes all hypotheses with cost values less than or equal to a threshold.</li><li>41. The apparatus of 40, wherein the threshold is determined based on information from a decoder.</li><li>42. The apparatus of 32, wherein the at least one processor is configured to perform receiver spatial processing on a set of received symbols to obtain a set of detected symbols, to derive an upper triangular matrix based on a channel estimate, and to determine the set of candidate hypotheses based on a cost function of the set of detected symbols and the upper triangular matrix.</li><li>43. A method comprising: <ul id="ul0026" list-style="none" compact="compact"><li>computing log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel;</li><li>determining a list of candidate hypotheses for remaining data symbols in the set of data symbols; and</li><li>computing LLRs jointly for the remaining data symbols with the list of candidate hypotheses.</li></ul></li><li>44. The method of 43, wherein the determining the list of candidate hypotheses comprises determining the list of candidate hypotheses for the remaining data symbols using list sphere detection.</li><li>45. The method of 43, further comprising: <ul id="ul0027" list-style="none" compact="compact"><li>performing receiver spatial processing on a set of received symbols to obtain a set of detected symbols; and</li><li>deriving an upper triangular matrix based on a channel estimate, and</li><li>wherein the determining the list of candidate hypotheses comprises determining the set of candidate hypotheses based on a cost function of the set of detected symbols and the upper triangular matrix.</li></ul></li><li>46. An apparatus comprising: <ul id="ul0028" list-style="none" compact="compact"><li>means for computing log-likelihood ratios (LLRs) independently for each of at least one data symbol in a set of data symbols transmitted via a multiple-input multiple-output (MIMO) channel;</li><li>means for determining a list of candidate hypotheses for remaining data symbols in the set of data symbols; and</li><li>means for computing LLRs jointly for the remaining data symbols with the list of candidate hypotheses.</li></ul></li><li>47. The apparatus of 46, wherein the means for determining the list of candidate hypotheses comprises means for determining the list of candidate hypotheses for the remaining data symbols using list sphere detection.</li><li>48. The apparatus of 46, further comprising: <ul id="ul0029" list-style="none" compact="compact"><li>means for performing receiver spatial processing on a set of received symbols to obtain a set of detected symbols; and</li><li>means for deriving an upper triangular matrix based on a channel estimate, and</li><li>wherein the means for determining the list of candidate hypotheses comprises means for determining the set of candidate hypotheses based on a cost function of the set of detected symbols and the upper triangular matrix.</li></ul></li></ol>