EP1069722A2

Wireless communication system and method having a space-time architecture, and receiver for multi-user detection

Abstract

A threaded space-time (TST) architecture in a multiple antenna wireless communication system uses the coded transmission in each layer of a transmission resource array as a space-time code. Each layer of a layer set is active during all available symbol transmission intervals, and each of the transmit antennas are used equally often, such that layers each transmit a symbol using a different antenna during each symbol transmission interval. A receiver is provided for multi-user reception using an iterative, soft-input/soft-output (SISO) multi-user detection algorithm based on minimum mean square error (MMSE) criterion, among other methods.

EP1069722A2, drawing sheet 1 — Sheet 1 of 227

Term

Term ended

Projected expiry passed 12 July 2020, 6.2 years ago.

24 claims: 4 independent, 20 dependent

1
A method of transmitting symbols (12) in a multi-user wireless communication system (10) have a plurality of transmit antennas (18) and a plurality of receive antennas (24), the method comprising the steps of. dividing a data stream into multiple threads (62), each of said threads comprising said symbols (60);and transmitting one of said symbols (60) from each of said threads (62) from respective ones of said plurality of transmit antennas (18) during a symbol transmission interval.
9
An apparatus (14) for transmitting symbols in a multi-user wireless communication system (10) comprising:a plurality of transmit antennas (18);and a processing device operable to divide a data stream into multiple threads (62), each of said threads comprising said symbols (60), and to transmit one of said symbols from each of said threads from respective ones of said plurality of transmitter antennas during a symbol transmission interval.
13
The apparatus 9, wherein said processing device is further operable to interleave each of said threads (62).
18
A method of multi-user detection of symbols transmitted using space-time codes from a plurality of transmit antennas (18) to a plurality of receive antennas (24) that can be subject to spatial interference, the method comprising the steps of:receiving streams from said plurality of transmit antennas (18);generating estimates of said streams using a soft input/soft output detector (44);decoding respective said streams using corresponding soft input/soft output decoders (48): and refining processing by said soft input/soft output detector using soft outputs generated by said soft input/soft output decoders.

Independent claims4

168 paragraphs, as filed

0001This application claims the benefit of provisional U.S. application Serial No. 60/143,293, filed July 12, 1999.

Cross Reference to Related Applications

0002Related subject matter is disclosed in U.S. patent application Serial No. 09/397,896, filed September 17, 1999, and U.S patent application of A. Roger Hammons et al for "Method of Generating Space-Time Codes for Generalized Layered Space-Time Architectures", filed even date herewith (Attorney's docket PD-9900238), the entire contents of both of said applications being expressly incorporated herein by reference.

Field of the Invention

0003The invention relates generally to a method of symbol transmission employing space-time codes in a multiple antenna wireless communication system. The invention also relates to a method and apparatus for space-time signal processing and multi-user detection and decoding in a multiple antenna wireless communication system.

Background of the Invention

0004Unlike the Gaussian channel, the wireless channel suffers from multi-path fading. In such fading environments, reliable communication is made possible only through the use of diversity techniques in which the receiver is afforded multiple replicas of the transmitted signal under varying channel conditions. Recently, information theoretic studies have shown that spatial diversity provided by multiple transmit and/or receive antennas allows for a significant increase in the capacity of wireless communication systems operated in a Rayleigh fading environment. Following this research, two approaches for exploiting this spatial diversity have been proposed.

0005In accordance with one approach, channel coding is performed across the spatial dimension, as well as time, to benefit from the spatial diversity provided by using multiple transmit antennas. Accordingly, the term "space-time codes" is used in connection with this coding scheme. One potential drawback of this scheme is that the complexity of the maximum likelihood (ML) decoder is exponential in the number of transmit antennas.

0006A second approach relies on complex signal processing techniques at the receiver to achieve performance asymptotically close to the outage capacity. In this approach, no effort is made to optimize the channel coding scheme. Conventional single-dimensional channel codes are used to minimize complexity. This approach is referred to as the layered space-time (LST) architecture. The LST architecture involves formulating the problem as a multi-user detection problem at the receiver and, hence, capitalizing on existing multi-user detection techniques in the receiver design. A proposed algorithm is based on a combination of decision feedback interference cancellation and zero-forcing interference avoidance. One drawback of the LST architecture is that the number of receive antennas must be at least equal to the number of transmit antennas. The LST signal processing does not gain the maximum diversity advantage that space-time coding offers. At low signal-to-noise ratios, this approach may suffer from error propagation resulting from the decision feedback cancellation.

Summary of the Invention

0007In accordance with the present invention, novel solutions to problems associated with designing multiple antenna wireless systems are presented.

0008In accordance with an aspect of the present invention, a receiver is provided for multi-user reception. The receiver provides for joint detection and decoding.

0009In accordance with another aspect of the present invention, a set of lower complexity reception techniques based on the turbo processing architecture is presented. These techniques provide a trade-off between complexity and performance. Joint detection and decoding algorithms based on the iterative soft-input-soft-output (SISO) approaches are provided. These algorithms avoid the limitations of the LST signal processing techniques, including the need for equal number of transmit and receive antennas.

0010In accordance with yet another aspect of the present invention, a transmitter employs space-time coding to improve the efficiency of multiple antenna systems. A general architecture that combines efficient algebraic code design with advanced signal processing techniques is employed and is referred to as the threaded space-time (TST) architecture. The TST architecture also allows for exploiting the temporal diversity provided by the time varying fading channel. The existing scheme for combined array processing and space-time coding described above, which likewise addresses some of the problems encountered with LST, relies upon a zero forcing group interference suppression technique and shows performance that is 6 - 9 dB from the outage capacity. The TST architecture and signal processing of the present invention, however, improves performance to less than 3 dB from the outage capacity. It also provides greater flexibility in terms of the trade-off between power efficiency, bandwidth efficiency, and receiver complexity.

Brief Description of the Drawings

0011The various aspects, advantages and novel features of the present invention will be more readily comprehended from the following detailed description when read in conjunction with the appended drawings, in which. <ul id="ul0001" list-style="none"><li>Figure 1 is a block diagram of a multiple antenna wireless communication system constructed in accordance with an embodiment of the present invention;</li><li>Figure 2 illustrates a code word matrix encoded and transmitted in accordance with a known layered space-time architecture;</li><li>Figure 3 illustrates space-time codes transmitted in accordance with a known multi-layered space-time architecture;</li><li>Figure 4 is a block diagram of a receiver constructed in accordance with an embodiment of the present invention;</li><li>Figure 5 is a block diagram of a receiver constructed in accordance with an embodiment of the present invention;</li><li>Figures 6 illsutrates a threaded code word matrix constructed using a threaded space-time architecture in accordance with an embodiment of the present invention;</li><li>Figures 7 and 8 are graphs illustrating the performance of a receiver constructed in accordance with an embodiment of the present invention; and</li><li>Figures 9, 10 and 11 are graphs illustrating the performance of a threaded space-time architecture implemented in accordance with an embodiment of the present invention.</li></ul>

0012Throughout the drawing figures, like reference numerals will be understood to refer to like parts and components.

Detailed Description of the Preferred Embodiments

0013The description below shall be organized as follows: the system description and a brief review of previous work on the design of space-time modems are presented in Section 1. In Section 2, the optimal receiver for joint detection and decoding is identified, and a set of iterative receivers that provide a trade-off between complexity and performance is presented. The application of iterative receivers to the layered space-time architecture is discussed in Section 2.3. In Section 3, a novel approach for joint space-time transmitter/receiver design is presented that combines efficient multi-user detection with space-time coding. Algebraic space-time code constructions for the new architecture are provided in Section 3.2. Comparisons of the various layered architectures in terms of efficiency and achievable diversity order are presented in Section 4, while simulation results are compared in Section 5. Finally, Section 6 presents conclusions.

1. Overview of Space-Time Concepts

0014In this section, the basic concepts for space-time signal design and signal processing are described. Important concepts involved in space-time codes, that is, layered space-time processing; and another proposed hybrid multi-layered approach, are briefly explained.

1.1 Signal Model

0015A multiple antenna communication system 10 with n transmit antennas 18 and m receive antennas 14 as shown in Figure 1. In this system 10, the channel encoder 20 in the transmitter 14 accepts input from an information source 12 and outputs a coded stream of higher redundancy suitable for error correction processing at the receiver 16. The encoded output stream is modulated via a spatial modulator 22 and distributed among the n antennas 18. The transmissions from each of the n transmit antennas 18 are simultaneous and synchronous. The signal received at each antenna 24 is therefore a superposition of the n transmitted signals corrupted by additive white Gaussian noise and multiplicative fading. The signal is processed by a demodulator 26 and a decoder 28 and provided to an information sink 30.

0016Assume that the transmitter 14 is capable of an aggregate transmission rate of nRs symbols per second (i.e., a transmission rate of Rs symbols per second per transmit antenna). Then, over a transmission time of T seconds, the transmitter 14 may transmit up to <maths id="math0001" num=""><math display="inline"><mrow><mtext>ℓ = </mtext><msub><mrow><mtext mathvariant="italic">R</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub><mtext mathvariant="italic">T</mtext></mrow></math><img file="EP1069722A2_D0001.tif" /></maths> channel symbols per antenna. The space-time transmission resources may therefore be viewed as an n × ℓ array whose (i, t)-th entry represents the t-th symbol interval available on the i-th antenna. The dimension indexed by i is referred to as the spatial dimension, whereas the dimension indexed by t is called the temporal dimension.

0017In Figure 1, the channel encoder 20 is a generic function and, in many cases of interest, can be decomposable into a set of multiple, independent channel encoders processing separate substreams from the information source 12. When the channel encoder 20 is decomposable, there is a corresponding partitioning of the spatial modulating function that is of interest. The components of such a partitioning are referred to as layers or multi-layers.

0018At the receiver 16, the signal r<maths id="math0002" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">j</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0002.tif" /></maths> received by antenna j at time t is given by<maths id="math0003" num=""><img file="EP1069722A2_D0003.tif" /></maths> where √<maths id="math0004" num=""><math display="inline"><mrow><mover accent="true"><mrow><msub><mrow><mtext mathvariant="italic">E</mtext></mrow><mrow><mtext mathvariant="italic">s</mtext></mrow></msub></mrow><mo>¯</mo></mover></mrow></math><img file="EP1069722A2_D0004.tif" /></maths> is the energy per transmitted symbol; α<maths id="math0005" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">ij</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0005.tif" /></maths> is the complex path gain from transmit antenna i to receive antenna j at time t; c<maths id="math0006" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">i</mtext></mrow><mrow><mtext mathvariant="italic">τ</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0006.tif" /></maths> is the symbol transmitted from antenna i at time t; n<maths id="math0007" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext mathvariant="italic">j</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0007.tif" /></maths> is the additive white Gaussian noise sample for receive antenna j at time t. The noise samples are independent samples of zero-mean complex Gaussian random variable with variance N0/2 per dimension. The different path gains α<maths id="math0008" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">ij</mtext><mtext>)</mtext></mrow><mrow><mtext>t</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0008.tif" /></maths> are assumed to be statistically independent. The fading model of primary interest is that of a block flat Rayleigh fading process in which the code word encompasses B fading blocks. The complex fading gains are constant over one fading block but are independent from block to block. The quasi-static fading model has been studied which is a special case of the block fading model in which B = 1.

0019The received signal can be expressed in vector notation as<maths id="math0009" num=""><img file="EP1069722A2_D0009.tif" /></maths> where rt is the m × 1 received vector at time t; Sτ is the m × n complex signature matrix whose ith column corresponds to the path gains for the ith antenna; cτ is the n × 1 transmitted vector at time t; nτ is the m x 1 white Gaussian noise vector.

0020The system 10 provides not one, but nm, communication links between sender and receiver, corresponding to each distinct transmit/receive antenna pairing. The objective of space-time system design is to use these statistically independent, but mutually interfering, communication links to increase system throughput and quality of service by exploiting the spatial and temporal diversity available in the system.

1.2 Space-Time Channel Codes

0021For space-time channel code design, assume that the channel encoder 20 of Figure 1 is indecomposable. The primary design objective is therefore to provide channel codes that exploit the full transmission resource array and provide the highest level of spatial diversity at the receiver 16.

0022In the concept of a space-time code, the channel encoding, modulation, and distribution of symbols across antennas are intrinsically connected. Given a set X, the space of 1 × m row vectors and the space of n × m matrices taking values in X will be denoted by Xm and Xn×m, respectively. Then, a block code of length N over the discrete symbol alphabet <img file="EP1069722A2_D0010.tif" /> is a subset C of the N-dimensional space <img file="EP1069722A2_D0010.tif" />N. Usually, the number of code words in C is a power of the alphabet size,<maths id="math0010" num=""><img file="EP1069722A2_D0011.tif" /></maths> so that there is a one-to-one mapping, γ : <img file="EP1069722A2_D0010.tif" />k → C, of information k-tuples onto code words. The mapping γ is an encoder for C. In this paper, we will be primarily interested in the case in which C is a binary linear code-i.e., <img file="EP1069722A2_D0010.tif" /> is the elementary binary field<maths id="math0011" num=""><img file="EP1069722A2_D0012.tif" /></maths>

0023The baseband modulation mapping µ : <img file="EP1069722A2_D0010.tif" />b → Ω assigns to each b-tuple of alphabet symbols a unique point in the discrete, complex-valued signaling constellation Ω, which is assumed not to contain the point zero. Conversely, the inverse map µ-1 provides a b-symbol labeling of the constellation points. By extension, µ(x) denotes the modulated version of the vector x ∈ <img file="EP1069722A2_D0010.tif" />N. In this case, it is understood that N must be a multiple of b and that the blocking of symbols into b-tuples for the modulator is performed left to right.

0024Let <maths id="math0012" num=""><math display="inline"><mrow><msup><mrow><mtext>Ω</mtext></mrow><mrow><mtext>+</mtext></mrow></msup><mtext> = Ω∪{0}</mtext></mrow></math><img file="EP1069722A2_D0013.tif" /></maths> denote the expanded constellation. Then, the spatial modulator is a mapping f : <img file="EP1069722A2_D0010.tif" />N → (Ω+)n×ℓ that sends the vector x to an n x ℓ complex-valued matrix<maths id="math0013" num=""><img file="EP1069722A2_D0014.tif" /></maths> whose non-zero entries are a rearrangement of the entries of µ(x). Specifically, c is the baseband version of the code word x as transmitted across the channel. Thus, in the notation of equation (1), the matrix c has (i, t)-th entry equal to c<maths id="math0014" num=""><math display="inline"><mrow><mfrac linethickness="0"><mrow><mtext>i</mtext></mrow><mrow><mtext>τ</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0015.tif" /></maths> . Note that, in this formulation, it is expressly allowed that no symbol be transmitted by a given antenna at a given signaling interval; thus, <maths id="math0015" num=""><math display="inline"><mrow><mtext mathvariant="italic">N/b</mtext><mtext> ≤ </mtext><mtext mathvariant="italic">n</mtext><mtext>ℓ</mtext></mrow></math><img file="EP1069722A2_D0016.tif" /></maths>. n and ℓ are referred to, respectively, as the spatial span and temporal span of f.

0025Finally, for convenience, let<maths id="math0016" num=""><img file="EP1069722A2_D0017.tif" /></maths> denote the n × bℓ matrix in which each constellation point is replaced by its b-symbol label and any zero entry is replaced by a b-tuple of special blank symbols. The map σ : x → <maths id="math0017" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">c</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP1069722A2_D0018.tif" /></maths> is called the spatial formatter.

0026Definition 1A space-time code C consists of an underlying channel code C together with the spatial modulator functionf.

0027The fundamental performance parameters for space-time codes are the following; (1) diversity advantage, which describes the exponential decrease of decoded error rate versus signal-to-noise ratio (asymptotic slope of the performance curve in a log-log scale); and (2) coding advantage which does not affect the asymptotic slope but results in a shift in the performance curve. The diversity advantage is the more critical of the two performance metrics as it determines the asymptotic slope of the performance curve. Ideally, the coding advantage should be optimized after the diversity advantage is maximized.

0028For quasi-static fading channels, it has been shown that the spatial diversity advantage of the code, assuming ML decoding, is the product of the number of receive antennas 24 and the minimum rank among the set of complex valued matrices associated with the difference between baseband modulated code words. It is clear that full spatial diversity nm will be achieved if and only if all the difference matrices have full rank. Based on this design criterion, simple design rules have been proposed for space-time trellis codes for 2-level spatial diversity. <ul id="ul0002" list-style="none"><li>Rule 1. Transitions departing from the same state differ only in the second symbol</li><li>Rule 2. Transitions merging at the same state differ only in the first symbol.</li></ul> When these rules are followed, the code word difference matrices are of the form<maths id="math0018" num=""><img file="EP1069722A2_D0019.tif" /></maths> with δ1, δ2 nonzero complex numbers. Thus, every such difference matrix has full rank, and the space-time code achieves 2-level spatial diversity. Two good trellis codes that satisfy these design rules, and several others that do not, were handcrafted using computer search methods.

0029The fact that this design criterion applies to the complex domain, rather than the discrete domain in which the codes are designed, has hindered the development of more general results. The following binary rank criterion for BPSK-modulated, binary space-time codes have also been developed:

0030Theorem 2 (Binary Rank Criterion)Let C be a linear n × ℓ space-time code with underlyingbinary code C of length<maths id="math0019" num=""><math display="inline"><mrow><mtext mathvariant="italic">N</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext>ℓ</mtext></mrow></math><img file="EP1069722A2_D0020.tif" /></maths>where ℓ ≥ n. Suppose that every non-zero code word<maths id="math0020" num=""><math display="inline"><mrow><mover accent="true"><mrow><mtext mathvariant="bold">c</mtext></mrow><mo>^</mo></mover></mrow></math><img file="EP1069722A2_D0021.tif" /></maths>is a matrix of full rank over the binary field<img file="EP1069722A2_D0022.tif" />. Then, for BPSK transmission over the quasi-static fading channel, the space-time code C achieves full spatial diversity nm.

0031Using the binary rank criterion, the following construction for space-rime codes is proposed which is referred to as the stacking construction.

0032Theorem 3 (Stacking Construction)LetM1, M2,..., Mn be binary matrices of dimension k × ℓ, ℓ ≥ k, and let C be the n × ℓ space-time code of dimension k consisting of the code word matrices<maths id="math0021" num=""><img file="EP1069722A2_D0023.tif" /></maths>wherexdenotes an arbitrary k-tuple of information bits and n ≤ ℓ. Then C satisfies the binary rank criterion, and thus, for BPSK transmission over the quasi-static fading channel, achieves full spatial diversity nm, if and only ifM1, M2,..., Mn have the property that<maths id="math0022" num=""><img file="EP1069722A2_D0024.tif" /></maths>

0033It is clear that this construction is general for any number of antennas and, generalized in the obvious fashion, applies to trellis, as well as block codes. This constriction, and a similar version for QPSK transmission (in which case<maths id="math0023" num=""><img file="EP1069722A2_D0025.tif" /></maths> the integers modulo 4, and b = 1), have been shown to encompass, as special cases, transmit delay diversity, the afore-mentioned hand-crafted trellis codes, rate 1/n convolutional codes, and certain block and concatenated coding schemes. The generator polynomials for rate 1/n convolutional codes with the best minimum distance that achieve full spatial diversity are discussed in the above-referenced patent application Serial No. 09/397,896.

1.3 Layered Space-Time Architectures

0034In the layered space-time processing approach, the channel encoder 20 of Figure 1 is composite, and the multiple, independent coded streams are distributed throughout the transmission resource array in layers. The primary design objective is to design the layering architecture and associated signal processing so that the receiver can efficiently separate the individual layers from one another and can decode each of the layers effectively. In these schemes, there is no spatial interference among symbols transmitted within a layer (unlike the space-time code design approach); hence, conventional channel codes can be used while the effects of spatial interference are addressed primarily in the signal processor design.

0035Different layering schemes are provided for the proposed Bell Laboratories Layered Space-Time (BLAST) architecture. In the simplest variation, the code words are transmitted in horizontal layers. The preferred scheme, however, involves the transmission of code words in diagonal layers. The notion of a layer is generalized herein as a section of the transmission resources array having the property that each symbol interval within the section is allocated to at most one antenna. This property ensures that all spatial interference experienced by the layer comes from outside the layer. A layer has the further structural property that a set of spatial and/or temporal cyclic shifts of the layer within the transmission resource array provides a partitioning of the transmission resource array. This allows for a simple repeated use of the layer pattern for transmission of multiple, independent coded streams.

0036Formally, a layer in an n × ℓ transmission resource array may be identified by an indexing set<img file="EP1069722A2_D0026.tif" />⊂ In × Iℓ having the property that the t-th symbol interval on antenna a belongs to the layer if and only if (a, t) ∈ L. Then, a layer requires that, if (a, t) ∈ <img file="EP1069722A2_D0026.tif" /> and (a', t') ∈ L, then either t ≠ t' or <maths id="math0024" num=""><math display="inline"><mrow><mtext mathvariant="italic">a</mtext><mtext> = </mtext><mtext mathvariant="italic">a'</mtext></mrow></math><img file="EP1069722A2_D0027.tif" /></maths>-i.e., that a is a function of t.

0037Now, consider a composite channel encoder γ consisting of n constituent encoders γ1, γ2,..., γn operating on independent information streams. Let<maths id="math0025" num=""><img file="EP1069722A2_D0028.tif" /></maths> so that <maths id="math0026" num=""><math display="inline"><mrow><mtext mathvariant="italic">k</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> + ··· + </mtext><msub><mrow><mtext mathvariant="italic">k</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub></mrow></math><img file="EP1069722A2_D0029.tif" /></maths> and <maths id="math0027" num=""><math display="inline"><mrow><mtext mathvariant="italic">N</mtext><mtext> = </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> + ··· + </mtext><msub><mrow><mtext mathvariant="italic">N</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub></mrow></math><img file="EP1069722A2_D0030.tif" /></maths>. Then, there is a partitioning <maths id="math0028" num=""><math display="inline"><mrow><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><mtext> = </mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> | </mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> | ··· | </mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><msub><mrow><mtext></mtext></mrow><mrow><mtext>-1</mtext></mrow></msub></mrow></math><img file="EP1069722A2_D0031.tif" /></maths> of the composite information vector u ∈ <img file="EP1069722A2_D0010.tif" />k into a set of disjoint component vectors ui, of length<img file="EP1069722A2_D0032.tif" /> and a corresponding partitioning <maths id="math0029" num=""><math display="inline"><mrow><mtext>γ(</mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext>) = γ</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>(</mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext>1</mtext></mrow></msub><msub><mrow><mtext>) | γ</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext>(</mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext>2</mtext></mrow></msub><msub><mrow><mtext>) | ··· | γ</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><mtext>(</mtext><munder accentunder="true"><mrow><mtext mathvariant="italic">u</mtext></mrow><mo>̲</mo></munder><msub><mrow><mtext></mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0033.tif" /></maths> of the composite code word γ(u) into a set of constituent code words<img file="EP1069722A2_D0034.tif" /> of length<img file="EP1069722A2_D0035.tif" /> In the layered architecture approach, the space-time transmitter assigns each of the constituent code words<img file="EP1069722A2_D0036.tif" /> to one of a set of n disjoint layers. For simpicity, consider the case in which the constituent codes are all of the same rate and have the same code word length:<maths id="math0030" num=""><img file="EP1069722A2_D0037.tif" /></maths> and<maths id="math0031" num=""><img file="EP1069722A2_D0038.tif" /></maths> for all i.

0038There is a corresponding decomposition of the spatial modulating function that is induced by the layering. Let<img file="EP1069722A2_D0039.tif" /> denote the component spatial modulating function, associated with layer<img file="EP1069722A2_D0040.tif" /> which agrees with the composite spatial modulator f regarding the modulation and formatting of the layer elements but which sets all off-layer elements to complex zero. Then<maths id="math0032" num=""><img file="EP1069722A2_D0041.tif" /></maths>

0039In the V-BLAST architecture, the transmitter uses n conventional channel encoders and permanently assigns the output of each encoder to one of the n transmit antennas. This corresponds to a partitioning of the transmission resource array into the horizontal layers<maths id="math0033" num=""><img file="EP1069722A2_D0042.tif" /></maths> where <maths id="math0034" num=""><math display="inline"><mrow><mtext>ℓ = </mtext><mtext mathvariant="italic">N</mtext><mtext>/(</mtext><mtext mathvariant="italic">nb</mtext><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0043.tif" /></maths>. Better performance is achieved by the preferred D-BLAST architecture in which the output of each encoder is distributed among the n antennas along the diagonal layers<maths id="math0035" num=""><img file="EP1069722A2_D0044.tif" /></maths> where <maths id="math0036" num=""><math display="inline"><mrow><mtext mathvariant="italic">w</mtext><mtext> = </mtext><mtext mathvariant="italic">N</mtext><mtext>/(</mtext><msup><mrow><mtext mathvariant="italic">n</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext mathvariant="italic">b</mtext><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0045.tif" /></maths> is the width of the diagonal, <maths id="math0037" num=""><math display="inline"><mrow><mtext>ℓ = (2</mtext><mtext mathvariant="italic">n</mtext><mtext> - 1)</mtext><mtext mathvariant="italic">w</mtext></mrow></math><img file="EP1069722A2_D0046.tif" /></maths> is the temporal span, and <img file="EP1069722A2_D0047.tif" />·<img file="EP1069722A2_D0048.tif" />n denotes the function returning the integer part of a real-valued input reduced modulo n.

0040The BLAST receiver uses a multi-user detection strategy based on a combination of interference cancellation and avoidance. In D-BLAST, each diagonal layer constitutes a complete code word, so decoding is performed layer by layer. Consider the code word matrix 32 shown in Figure 2. The entries below the first diagonal layer 34 are zeros. To decode the first diagonal 34, the receiver generates a soft decision statistic for each entry in that diagonal. In doing so, the interference from the upper diagonals is avoided by projecting the received signal onto the null-space of the upper interference The soft statistics are then used by the corresponding channel decoder to decode this diagonal. The decoder output is then fed back to cancel the first diagonal contribution in the interference while decoding the next diagonal. The receiver then proceeds to decode the next diagonal in the same manner.

0041This zero-forcing strategy is only possible if the number of receive antennas m is at least as large as the number of transmit antennas n. Zero-forcing also results in a loss in achievable diversity order that depends on the number of interferers to be avoided. For example, the symbol in the uppermost position will have the maximum diversity order m, whereas the symbol in the lowermost position will have the minimum diversity order 1. Thus, the diagonal layering of the encoded stream is necessary to achieve equal performance for all coded streams. Due to the interference cancellation mechanism, errors can also propagate spatially.

1.4 Multi-Layered Space-Time Architectures

0042Multi-layered space-time processing is a hybrid approach involving use of both space-time channel codes and layered processing, as illustrated in Figure 3. Space-time codes 36a through 36n are used in a conventional manner; however, the number of antennas is limited to facilitate group processing. Since code words are no longer transmitted in a single layer, there is spatial interference among transmitted symbols within a given code word that should be addressed as part of the channel code design.

0043The group interference suppression technique is proposed. In this scheme, the input stream is divided, for example, into n/n' substreams. The different substreams are encoded using n'-level diversity component trellis codes C1,..., Cn/n'. Each component code is then transmitted from n' antennas (horizontal n'-layering). At the receiver, each component code is decoded separately while suppressing signals from other component codes. The group interference suppression strategy is based on the zero-forcing principle and requires that <maths id="math0038" num=""><math display="inline"><mrow><mtext mathvariant="italic">m</mtext><mtext> ≥ </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">n'</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0049.tif" /></maths>. In quasi-static fading channel, the spatial diversity gain achieved by C1 is <maths id="math0039" num=""><math display="inline"><mrow><mtext mathvariant="italic">n'</mtext><mtext> × (</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + </mtext><mtext mathvariant="italic">n'</mtext><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0050.tif" /></maths>. Assuming correct decoding of C1, its contribution is subtracted from signals at different receive antennas. This gives a communication system with n - n' transmit and m receive antennas. Hence, the space time code C2 affords a diversity gain of <maths id="math0040" num=""><math display="inline"><mrow><mtext mathvariant="italic">n'</mtext><mtext> × (</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 2</mtext><mtext mathvariant="italic">n'</mtext><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0051.tif" /></maths>, and so on. Using the fact that the diversity gain increases with each decoding stage, unequal power levels are allocated to the different component codes. Because all of the aforementioned space-time codes were 2-level diversity codes, except for the delay diversity, known examples were limited to n' = 2.

0044The performance of this architecture was shown to be within 6 - 9 dB from the outage capacity at frame error rate of 10-1.

2. Multi-User Detection for Space-Time Applications

0045In accordance with the present invention, the problem of space-time signal processing is considered to be a multi-user detection problem. Iterative multi-user detection algorithms are provided and their advantages over zero-forcing strategies in layered and multi-layered space-time architectures will be discussed below.

2.1 Optimal Multi-User Detection

0046Consider the layered space-time architecture in which n binary channel encoders of rate r and constraint length v are used, and each encoder output is assigned to a different layer. It is clear that this system is equivalent to a synchronous code division multiple access (CDMA) system with n user and m spreading gain, where the complex fading coefficients constitute the equivalent spreading sequences. In general, m < n corresponds to an overloaded CDMA system. In such a scenario, the optimum receiver for joint detection and decoding combines the trellises of both the multi-user detector and the channel decoder. This receiver can be realized using a Viterbi algorithm whose complexity is of exponential order <img file="EP1069722A2_D0052.tif" />(2nv) in the product of the number of antennas and the code constraint length. For some systems, the exponential increase in implementation complexity may make the optimal receiver impractical for even a relatively small number of antennas. Thus, there is a need for alternate receiver architectures that are less complex but still efficient.

2.2 Iterative Multi-User Detection

0047In this section, the turbo-processing principle is used to derive a set of iterative multi-user detection algorithms that allow trade-offs to be made between performance and complexity. A block diagram of the iterative receiver 40 is shown in Figure 4. For simplicity, horizontal layering with binary channel codes (n binary channel encoders coupled to n transmit antennas) and BPSK modulation are assumed. Extension to nonbinary codes and to the multi-layered architecture is straightforward.

0048With reference to Figure 4, a receive signal is processed by a matched filter bank 42, and an estimation module 52. A soft-input/soft-output (SISO) multi-user detector module 44 provides joint soft-decision estimates of the n streams of data. Each of the detected streams are decoded by the separate SISO channel decoders 48a through 48n associated with the component channel codes. The detected streams are deinterleaved, as indicated at 46, prior to decoding. The output of the decoder is interleaved again, as indicated at 50a through 50n, to facilitate interleave processing by the multi-user detector. After each decoding iteration, the soft outputs from the channel decoders 48a through 48n are used to refine the processing performed by the SISO multi-user detector 44. In the iterative receiver 40, each of the streams is independently interleaved to facilitate convergence. This aspect of the receiver 40 also influences channel code design.

0049The SISO channel decoders 48a though 48n can employ any of the following algorithms: (1) the maximum a-posteriori (MAP) approach, which is optimal in the sense that it minimizes the probability of bit error at the decoder output; (2) the (log-MAP) approach, which is a lower complexity, additive version of the (MAP) rule that operates in the log-domain; or (3) the soft output Viterbi algorithm (SOVA). The choice of the decoding technique depends on the available processing power at the receiver 40.

0050The overall complexity of the iterative receiver 40 depends primarily on the algorithm used by the multi-user detector 44. Therefore, three SISO, multi-user detection algorithms that provide a trade-on between performance and complexity are developed. The first is based on the maximum a-posteriori (MAP) probability rule; the second is based on the minimum mean square error (MMSE) criterion; and the third can be viewed a suboptimal approximation of the iterative MMSE receiver.

0051In all cases, the derivations require an assumption of statistical independence of the spatial soft decision information. This assumption is sufficiently satisfied in practice by requiring that the transmissions from each of the antennas be independently interleaved.

2.2.1 Iterative MAP Receiver

0052In this case, the SISO multi-user detector 44 computes the symbol-by-symbol maximum a posteriori (MAP) statistics defined by<maths id="math0041" num=""><img file="EP1069722A2_D0053.tif" /></maths> Specifically, the soft decision statistic for<img file="EP1069722A2_D0054.tif" /> is updated iteratively via the following rule:<maths id="math0042" num=""><img file="EP1069722A2_D0055.tif" /></maths> where<img file="EP1069722A2_D0056.tif" /> is the conditional multivariate complex Gaussian distribution of the received vector;<img file="EP1069722A2_D0057.tif" /> is the joint a-priori probability distribution of the transmitted symbols; and<maths id="math0043" num=""><img file="EP1069722A2_D0058.tif" /></maths>

0053The computation of the joint distribution<img file="EP1069722A2_D0059.tif" /> is intractable in general without further assumptions If statistical independence is assumed, then<maths id="math0044" num=""><img file="EP1069722A2_D0060.tif" /></maths> In the first iteration, one takes<maths id="math0045" num=""><img file="EP1069722A2_D0061.tif" /></maths> In subsequent iterations, the a-priori probabilities are re-computed based on the previous iteration's extrinsic information,<img file="EP1069722A2_D0062.tif" /> corresponding to the symbol transmitted from the j-th antenna at time t:<maths id="math0046" num=""><img file="EP1069722A2_D0063.tif" /></maths>

0054Note that, while the fading is assumed independent for each transmit-receive antenna pair, the extrinsic information is generally correlated. The independence assumption is therefore invalidated, unless the separate antenna transmissions are independently interleaved. When different interleaving is used for each antenna transmission, however, the independence assumption is reasonably well approximated.

0055The MAP approach is used for CDMA applications. For the iterative MAP decoder, the number of terms in each of the summations is preferably 2n-1. Hence, the complexity of the MAP detector per iteration is <img file="EP1069722A2_D0052.tif" /> (n2n), and the overall complexity of the receiver, per iteration, is <img file="EP1069722A2_D0052.tif" />(n [2n + 2v]).

2.2.2 Iterative MMSE Receiver

0056In this scheme, the SISO multi-user detection module 44 is based on the MMSE criterion. After each decoding iteration via 48a through 48n, the soft outputs are used to update the a-priori probabilities of the transmitted symbols. These updated probabilities are then used to calculate the MMSE filter feed-forward and feedback weights in the multi-user detection module, as indicated at 44a and 44b, respectively, in Figure 5. The feedback connections 44b represent the subtractive interference cancellation part of the receiver, while the feed-forward weights 44a serve to suppress any residual interference.

0057The set of equations describing the filter coefficients used for generating the soft decision statistic corresponding to<img file="EP1069722A2_D0064.tif" /> will be derived. The subscript t is omitted for convenience. Hence, the MMSE estimate<img file="EP1069722A2_D0065.tif" /> of the i-th antenna symbol at time t is given by<maths id="math0047" num=""><img file="EP1069722A2_D0066.tif" /></maths> where<img file="EP1069722A2_D0067.tif" /> is the m × 1 optimized feed-forward coefficients vector and<img file="EP1069722A2_D0068.tif" /> is a single coefficient that represents the soft cancellation part.<img file="EP1069722A2_D0069.tif" /> are obtained through minimizing the mean square value of the error<maths id="math0048" num=""><img file="EP1069722A2_D0070.tif" /></maths> between the data symbol and its estimate. Hence<maths id="math0049" num=""><img file="EP1069722A2_D0071.tif" /></maths> where S(i) is the m × 1 complex signature vector of the ith transmit antenna;<img file="EP1069722A2_D0072.tif" /> is the <maths id="math0050" num=""><math display="inline"><mrow><mtext mathvariant="italic">m</mtext><mtext> × (</mtext><mtext mathvariant="italic">n</mtext><mtext> - 1)</mtext></mrow></math><img file="EP1069722A2_D0073.tif" /></maths> matrix composed of the complex signature vectors of the other n - 1 transmit antennas 18;<img file="EP1069722A2_D0074.tif" /> is the (n - 1) × 1 transmitted data vector from the other n - 1 transmit antennas 18. Using standard minimization techniques, it is easily shown that the MMSE solutions for<img file="EP1069722A2_D0075.tif" /> and<img file="EP1069722A2_D0076.tif" /> satisfy the relations:<maths id="math0051" num=""><img file="EP1069722A2_D0077.tif" /></maths> where<maths id="math0052" num=""><img file="EP1069722A2_D0078.tif" /></maths>

0058At this point, statistical independence is assumed once again. This assumption is justified through the different interleaving used by each transmit antenna 18. Then<maths id="math0053" num=""><img file="EP1069722A2_D0079.tif" /></maths> Here Im×m is the identity matrix of order m;<img file="EP1069722A2_D0080.tif" /> is the (n - 1) × 1 vector of the expected values of the transmitted symbols from the other n - 1 antennas. The a-priori probabilities used to evaluate these expected values are obtained from the previous decoding iteration soft outputs, through the component-wise relation (9).

0059To simplify notation, the following definitions are made:<maths id="math0054" num=""><img file="EP1069722A2_D0081.tif" /></maths> Solving (12) and (13) for the optimum filter feed-forward and feedback coefficients, the following coefficients are obtained<maths id="math0055" num=""><img file="EP1069722A2_D0082.tif" /></maths><maths id="math0056" num=""><img file="EP1069722A2_D0083.tif" /></maths> The log-likelihood ratio is now given by<maths id="math0057" num=""><img file="EP1069722A2_D0084.tif" /></maths>

0060In the first decoding iteration, the transmitted symbols are assumed to have a uniform distribution; hence,<img file="EP1069722A2_D0085.tif" /> The feed-forward filter coefficients vector, w<maths id="math0058" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">i</mtext><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">f</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0086.tif" /></maths> , in this iteration is given by similar relations to MMSE equations derived the real domain. The relations of the present invention, however, are in the complex domain because of the complex spreading codes, and the feedback coefficient<img file="EP1069722A2_D0087.tif" /> After each iteration,<img file="EP1069722A2_D0088.tif" /> are recalculated using the decoders soft outputs. c(n/i) are then used to generate the new set of filter coefficients as described. In the asymptotic case, when<img file="EP1069722A2_D0089.tif" /> the receiver is equivalent to the subtractive interference canceler. This is expected, since<img file="EP1069722A2_D0090.tif" /> means that the previous iteration decisions, for the other antenna symbols, are error free. Under this assumption, the subtractive interference canceler becomes the optimum solution.

0061The direct implementation of the receiver 16 employing iterative MMSE requires a complexity of polynomial order in the number of transmit antennas 18. Adaptive techniques can be used to reduce implementation complexity.

2.2.3 Iterative Soft Interference cancellation

0062The main source of complexity in the iterative MMSE approach is the matrix inversion operation required to compute the filter feed-forward coefficients(21). This observation motivates the following suboptimal approach. y(i) can be rewitten as<maths id="math0059" num=""><img file="EP1069722A2_D0091.tif" /></maths> Then, if the matched filter<maths id="math0060" num=""><img file="EP1069722A2_D0092.tif" /></maths> is used, the need for the matrix inversion operation in (??) is eliminated. The resulting receiver has a linear complexity, per iteration, in the number of transmit antennas.

2.2.4 Trade-Offs

0063The receiver 16 employing iterative MAP offers a substantial reduction in complexity compared to the optimal receiver, but its complexity is exponential and could be prohibitive for systems with medium to large numbers of antennas. The receiver 16 employing iterative MMSE has polynomial complexity. The soft interference cancellation method is the least complex.

0064The receiver 16 employing iterative MMSE has an important advantage over the other two iterative approaches in that it can suppress the interference from other space-time users without the need to decode all of the signals. In the iterative MAP and the soft interference cancellation techniques, undecoded signals are treated as white Gaussian noise. Hence, both approaches can have a near-far problem from undecoded space-time users. In the iterative MMSE, the other users' interference can be suppressed by the feed-forward filter coefficients without the need to actually decode the other users' signals. Prior knowledge of the other users' spreading codes, that is, path gains, is needed; although, an adaptive algorithm based on a combination of iterative cancellation and adaptive subspace projection can be used.

2.3 Application to Layered Space-Time Architectures

0065The iterative multi-user techniques can be implemented for either of the layered or multilayered transmission formats described above provided that the transmitter 18 is modified so that the output of each channel encoder 20 is interleaved independently before transmission. The principal advantages of the iterative techniques in both settings are briefly discussed below. In Section 3, a generalized layered architecture with optimized channel coding is presented that more effectively exploits the diversity available in the system 10.

2.3.1 Layered Architecture

0066The iterative techniques of the present invention offer several advantages over the detection technique proposed in the LST. First, unlike LST, neither iterative approach requires that m ≥ n. Second, the probability of error propagation is reduced in the presented algorithms through the feedback of soft information instead of hard decisions. More importantly, the iterative approach of the present invention strives to suppress interference from other layers with minimal loss in achieved diversity order. Therefore, these techniques achieve a better performance than LST.

0067Assuming error-free feedback, the capacity of the LST with <maths id="math0061" num=""><math display="inline"><mrow><mtext mathvariant="italic">m</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1069722A2_D0093.tif" /></maths> is<maths id="math0062" num=""><img file="EP1069722A2_D0094.tif" /></maths> where ρ is the signal-to noise ratio at the input of each receive antennas, and χ<maths id="math0063" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>2</mtext></mrow><mrow><mtext>2</mtext><mtext mathvariant="italic">k</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0095.tif" /></maths> are independent chi-squared random variables with 2k degrees of freedom. The lower bound converges at high enough signal-to-noise ratios to the actual system capacity, so that LST achieves capacity asymptotically.

0068With the proposed iterative multi-user detection algorithms of the present invention, the ideal performance under error-free feedback is close to the upper bound<maths id="math0064" num=""><img file="EP1069722A2_D0096.tif" /></maths> At low signal-to noise ratios, the difference between the two bounds is considerable, indicating the superiority of the iterative techniques at small to medium signal-to noise ratios. The simulation results in Section 5 show that the iterative MMSE receiver 16 achieves more than 3 dB gain over the LST detection algorithm at 1% frame error rate.

2.3.2 Multi-Layered Architecture

0069The main advantage of the existing multi-layered scheme over the existing BLAST architecture is the use of space-time component codes rather than conventional channel codes. Space-time codes have the advantage of exploiting the diversity provided by the multiple transmit antennas but have the disadvantage that the complexity of the ML decoder is exponential in the number of transmit antennas used by each component code. The design of space-time codes for use in conjunction with the proposed iterative MAP and MMSE detection algorithms, however, is made more complicated by the use of independent interleaving of each antenna transmission. Random interleaving applied to each antenna stream may reduce the diversity advantage achieved by the space-time code. In the case of the space-time trellis codes, it appears a difficult task to verify that an interleaved version would still achieve full spatial diversity since the codes are handcrafted. A straightforward method has been proposed for analyzing the original codes and demonstrating that they achieve full spatial diversity, but the method is not readily extensible to the interleaved case. No systematic method for designing interleaved versions that retain full spatial diversity is known.

0070The iterative MAP and MMSE algorithms of the present invention can be applied, however, to the algebraic space-time code designs for BPSK or QPSK modulation. Assume BPSK transmission and a fixed code rate 1/n' where n' divides n. The input stream is divided into n/n' streams. Each stream is then independently encoded using the natural space-time code produced by a rate 1/n' convolutional encoder. The generator polynomials for full spatial diversity codes of this type are listed in Table I in Serial No. 09/397,896, for different code constraint lengths and numbers of transmit antennas n' 18. Each output arm from each encoder is independently interleaved and transmitted from a different antenna. In order to ensure that the resulting space-time code retains full spatial diversity, it is enough to verify that the generator matrices corresponding to the interleaved branches of the convolutional code satisfy the stacking construction condition in Theorem 3. A random search strategy is very efficient in finding interleavers that satisfy the stacking construction.

0071The direct computation of the diversity order d achieved by the soft iterative decoder is a daunting task. Heuristically, the approximate bounds are as follows:<maths id="math0065" num=""><img file="EP1069722A2_D0097.tif" /></maths> The upper bound corresponds to the maximum diversity achievable by a single space-time component code using n' transmit antennas assuming ML decoding in the absence of competing transmissions from the other component codes on the remaining antennas (the ideal case). The lower bound corresponds to the diversity achieved by a receiver that uses zero-forcing to detect the signal transmitted from its antennas (assuming m ≥ n) and ML component decoders. Its use as an approximate lower bound for the iterative techniques is justified by the fact that the iterative MMSE receiver 16 with a single iteration achieves the same asymptotic performance at high signal-to-noise ratios as the zero-forcing receiver and should outperform the zero-forcing receiver at low signal-to-noise ratios since the MMSE criterion seeks to maximize total signal-to-noise-and-interference ratio. The bound also applies to the iterative MAP algorithm since it outperforms the MMSE technique.

0072Guided by the excellent performance of the iterative MMSE receiver in CDMA applications, the achieved diversity is close to the upper bound of n'm. The approximate bounds are compared to the <maths id="math0066" num=""><math display="inline"><mrow><mtext>2(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 2)</mtext></mrow></math><img file="EP1069722A2_D0098.tif" /></maths> diversity advantage achieved by the joint trellis space-time coding and group interference suppression.

0073The architecture just described suffers from two main drawbacks. First, it is not applicable to arbitrary constellation. This is due to the limited applicability of the binary rank criteria to BPSK and QPSK constellations. Second, it does not efficiently exploit the temporal diversity embedded in the block fading channel. These limitations are avoided in the new approach presented in the next section

3. The Threaded Space-Time Approach

0074In this section, a generic approach for space-time transmitter/receiver design is presented in accordance with the present invention which combines efficient algebraic code design with iterative multi-user detection. In the proposed approach, an input data stream is divided into multiple threads. Each thread is encoded and interleaved separately. At each point of time, only one symbol 60 is transmitted from each thread 62, as shown in Figure 6. At the receiver 16, the iterative multi-user detector serves to separate the different threads 62a, 62b, and so on with minimal loss in performance. The encoding, interleaving, and distribution of thread symbols among different antennas is optimized to maximize spatial diversity, temporal diversity, and coding gain for a given transmission rate, assuming no interference from the other threads. Meanwhile, interleaving is performed in such a way to maximize the efficiency of the iterative receiver. While threads can be presented by a diagonal in the matrix 64, as depicted in Figure 6, the symbols in a thread need not be transmitted by adjacent antennas in respective symbol transmission intervals.

3.1 Threaded Space-Time Architecture

0075As in the generic layered architecture, the transmitter has available a disjoint set of layers,<maths id="math0067" num=""><img file="EP1069722A2_D0099.tif" /></maths> and transmits the composite code word<maths id="math0068" num=""><img file="EP1069722A2_D0100.tif" /></maths> by sending<img file="EP1069722A2_D0101.tif" /> in layer Li.

0076The layer set <img file="EP1069722A2_D0102.tif" /> is designed so that each layer is active during all of the available symbol transmission intervals and, over time, uses each of the n antennas equally often. Thus, during each symbol transmission interval, the layers each transmit a symbol using a different antenna; and, in terms of antenna usage, all of the layers are equivalent. A layer satisfying these constraints is referred to as a thread of spatial span n. The simplest example of threaded layering of temporal span ℓ is the set <img file="EP1069722A2_D0102.tif" /> in which<maths id="math0069" num=""><img file="EP1069722A2_D0103.tif" /></maths>

0077Unlike the layered architectures of described above, the design approach of the present invention treats the coded transmission in each layer as a bona fide space-time code, constructions for which are given in the next section. Looking at the space-time coding performed on a single layer in isolation, this construction appears to reduce throughput as a result of silence periods imposed on the different antennas; however, in the overall threaded transmission scheme, the silent periods on antennas that are not used by a given layer are filled with the transmissions from the other component space-time codes. Signal processing at the receiver, which is necessary to remove or suppress spatial interference among the threaded layers, allows high throughput to be achieved. One innovation of the new architecture is that, under the assumption of error-free interference cancellation, the component space-time codes can be designed to achieve full spatial diversity without degradation in overall system throughput.

0078The space-time architecture of the present invention is not a multi-layer approach since the transmit positions occupied by the modulated code symbols for a particular thread constitute a single layer. Yet, the architecture of the present invention is not a layered architecture in the same sense as the BLAST architecture. This is because the threaded layering is a more general type of layering well-suited for iterative multi-user techniques, and the channel coding design in the new approach is two-dimensional based on space-time coding principles designed to exploit both the spatial and temporal diversity. To distinguish this new approach, the architecture of the present invention is referred to as the threaded space-time (TST) architecture. The three architectures are compared in more detail in Section 4 below.

0079The efficiency of the threaded architecture depends on the ability of the receiver to eliminate the interference coming from the other space-time component codes. In principle, any multi-user detection technique can be used in this context. The iterative MMSE receiver is used in accordance with the present invention because of its reasonable complexity and its ability to achieve performance close to the interference-free scenario under different conditions. This approach is applicable to arbitrary constellations with binary (or non-binary) codes.

3.2 Design of Threaded Space-Time Codes

0080In this section, the design of the component space-time codes used in the threaded archtecture is discussed. The design of these codes follows an algebraic approach introduced in the above-referenced application Serial No. 09/397,896. The layering provided by the threaded architecture allows the algebraic formulation to be extended to arbitrary signalling constellations. Importantly, the requirement for independent interleaving in the iterative multi-user receiver is easily accommodated in these code designs.

0081Consider a single threaded layer<img file="EP1069722A2_D0104.tif" /> and the corresponding component space-time code Ci associated with encoder<img file="EP1069722A2_D0105.tif" /> The spatially modulated code words of Ci are the <maths id="math0070" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> × (</mtext><mtext mathvariant="italic">N</mtext><mtext>/</mtext><mtext mathvariant="italic">b</mtext><mtext>)</mtext></mrow></math><img file="EP1069722A2_D0106.tif" /></maths> complex matrices<img file="EP1069722A2_D0107.tif" /> To simplify notation, the indices are not used, letting<maths id="math0071" num=""><img file="EP1069722A2_D0108.tif" /></maths> and<maths id="math0072" num=""><img file="EP1069722A2_D0109.tif" /></maths> Let f<img file="EP1069722A2_D0110.tif" /> denote the component spatial modulator function associated with layer <img file="EP1069722A2_D0026.tif" />. Unsubscripted vectors such as x or y are used herein to refer to the information stream

0082For the design of the space-time code C associated with thread L, the following stacking construction using binary matrices for the quasi-static fading channel is employed.

0083Theorem 4 (Threaded Stacking Construction)Let L be a threaded layer of spatial span n. Given binary matricesM1, M2,..., Mn of dimension k × bℓ, let C be the binary code of dimension k consisting of all code words of the form<maths id="math0073" num=""><img file="EP1069722A2_D0111.tif" /></maths>wherexdenotes an arbitrary k-tuple of information bits Letf<img file="EP1069722A2_D0110.tif" />denote the spatial modulator having the property that<maths id="math0074" num=""><img file="EP1069722A2_D0112.tif" /></maths>is transmitted in the ℓ symbol intervals of L that are assigned to antenna i.

0084Then, as the space-time code in a communication system with n transmit antennas and mreceive antennas, the space-time code C consisting of C andfL achieves spatial diversity dm in a quasi-static fading channel if and only if d is the largest integer such thatM1, M2,..., Mn have the property that<maths id="math0075" num=""><img file="EP1069722A2_D0113.tif" /></maths>

0085Proof: Due to the lack of spatial interference within a layer, the baseband rank criterion is straightforward to apply. In particular, note that the baseband difference f<img file="EP1069722A2_D0110.tif" />(g(x)) - fL(g(y)) has rank d if and only if it has precisely d non-zero rows.

0086Now suppose that, for some a1, a2,..., an ∈ <img file="EP1069722A2_D0022.tif" />satisfying <maths id="math0076" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> + ··· + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0114.tif" /></maths>, then<maths id="math0077" num=""><img file="EP1069722A2_D0115.tif" /></maths> is singular. Then, there exist x, y ∈ <img file="EP1069722A2_D0022.tif" />k, x ≠ y, such that<maths id="math0078" num=""><img file="EP1069722A2_D0116.tif" /></maths> In this case, fL(g(x)) - fL(g(y)) has an all-zero row for every non-zero coefficient<img file="EP1069722A2_D0117.tif" /> Since there are <maths id="math0079" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0118.tif" /></maths> non-zero coefficients, f<img file="EP1069722A2_D0110.tif" />(g(x)) - fL(g(y)) has rank less than d. Thus, C does not achieve dm-level diversity.

0087Conversely, suppose C does not achieve dm-level diversity. Then, there exist x, y ∈ <img file="EP1069722A2_D0022.tif" />k, x ≠ y, such that the baseband difference fL(g(x)) - f<img file="EP1069722A2_D0110.tif" />(g(y)) has rank less than d. It must therefore have at least <maths id="math0080" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0119.tif" /></maths> all-zero rows. Let I denote a set of indices for <maths id="math0081" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0120.tif" /></maths> such rows, and set<img file="EP1069722A2_D0121.tif" /> for i ∈ I and<img file="EP1069722A2_D0122.tif" /> otherwise. Then, the matrix<maths id="math0082" num=""><img file="EP1069722A2_D0123.tif" /></maths> is singular since<maths id="math0083" num=""><img file="EP1069722A2_D0124.tif" /></maths>

0088Corollary 5Full spatial diversity nm is achieved if and only ifM1, M2,..., Mn are of rank k over the binary field.

0089A space-time code that achieves dm-level spatial diversity in a communication system with n transmit and m receive antennas over the quasi-static fading channel is called a d-space-time code

0090Corollary 6The maximum transmission rate for a communication system using the threaded layering architecture with n transmit antennas, a signaling constellation of size 2b, and component codes achieving d-level transmit spatial diversity constellation is<maths id="math0084" num=""><math display="inline"><mrow><mtext mathvariant="italic">b</mtext><mtext>(</mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1)</mtext></mrow></math><img file="EP1069722A2_D0125.tif" /></maths>bits/sec/Hz.

0091Proof: By Theorem 4, in order for the code to achieve d-level spatial diversity, the number of columns in Mj must satisfy <maths id="math0085" num=""><math display="inline"><mrow><mtext mathvariant="italic">b</mtext><mtext>ℓ ≥ </mtext><mtext mathvariant="italic">k</mtext><mtext>/(</mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1)</mtext></mrow></math><img file="EP1069722A2_D0126.tif" /></maths>. Then the code rate for C is <maths id="math0086" num=""><math display="inline"><mrow><mtext mathvariant="italic">k</mtext><mtext>/(</mtext><mtext mathvariant="italic">nb</mtext><mtext>ℓ) ≤ (</mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1)/</mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1069722A2_D0127.tif" /></maths>. Therefore, the maximum transmission rate of each thread is <maths id="math0087" num=""><math display="inline"><mrow><mtext mathvariant="italic">br</mtext><mtext> ≤ </mtext><mtext mathvariant="italic">b</mtext><mtext>(</mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1)/</mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1069722A2_D0128.tif" /></maths> bits per signaling interval. Then, the total transmission rate of the n threads is <maths id="math0088" num=""><math display="inline"><mrow><mtext mathvariant="italic">b</mtext><mtext>(</mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">d</mtext><mtext> + 1)</mtext></mrow></math><img file="EP1069722A2_D0129.tif" /></maths>. A different proof can be obtained using the maximum lossless compression transmission rate.

0092The following result is facilitates the design of space-time threaded codes that allow for exploiting the temporal diversity and maximizing the efficiency of the iterative multi-user detector.

0093Theorem 7Let C be a d-space-time code consisting of the binary code C whose code words are of the form<maths id="math0089" num=""><img file="EP1069722A2_D0130.tif" /></maths>wherexdenotes an arbitrary k-tuple of information bits, and the spatial modulatorfL in which<img file="EP1069722A2_D0131.tif" />is assigned to antenna i along threaded layer L. Given the linear vector-space transformations<img file="EP1069722A2_D0132.tif" />a new space-time code is constructed by assigning Ti (xMi) to antenna i along threaded layer<img file="EP1069722A2_D0026.tif" />. Then, the new space time code achieves the same spatial diversity order dm if T1,..., Tnare nonsingular.

0094In particular, the linear transformation Ti of the previous theorem is an arbitrary permutation<img file="EP1069722A2_D0133.tif" /> Then, the interleaved space-time code resulting from assigning<img file="EP1069722A2_D0134.tif" /> to antenna i along threaded layer L achieves the same level of diversity as the non-interleaved space-time code C.

0095Consider the special case of designing space-time trellis codes for the threaded architecture. The natural space-time codes discussed in application Serial No. 09/397,896 and associated with binary, rate 1/n, convolutional codes with periodic bit interleaving are attractive candidates for the threaded space-time architecture as they can be easily formatted to satisfy the threaded stacking construction. Each output arm from the encoder is transmitted from a separate antenna. There is no restriction on the interleaving employed by each antenna (i.e, different interleaving can be used by the different antennas without violating the generalized stacking condition). As discussed earlier, this feature allows for the design of efficient iterative multi-user receivers. These convolutional codes can be used for a similar application, that is, the block erasure channel. The main advantage of such codes is the availability of computationally efficient, soft-input/soft-output decoding algorithms.

0096For space-time trellis codes treats, only the case in which the underlying code has rate 1/n matched to the number of transmit antennas has been considered. For the threaded space-time code design of the present invention, the more general case in which the convolutional code has rate greater than 1/n is used. The treatment includes the case of rate k/n convolutional codes constructed by puncturing an underlying rate 1/n convolutional code.

0097Let C be a binary convolutional code of rate k/n. The encoder processes k binary input sequences x1(t), x2(t),..., xk(t) and produces n coded output sequences y1(t), y2(t),..., yn(t) which are multiplexed together to form the output code word.

0098For quasi-static fading channels, the input and output sequences of interest are of fixed finite length. In the more general case, however, the sequences are semi-infinite indexed by t = 0, 1, 2,.... Let <img file="EP1069722A2_D0022.tif" />∞ denote the space of all such binary sequences. A sequence {x(t)}<maths id="math0090" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>∞</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext><mtext>=0</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0135.tif" /></maths> ∈ <img file="EP1069722A2_D0022.tif" />∞ is often represented by the formal series <maths id="math0091" num=""><math display="inline"><mrow><mtext mathvariant="italic">X</mtext><mtext>(</mtext><mtext mathvariant="italic">D</mtext><mtext>) = </mtext><mtext mathvariant="italic">x</mtext><mtext>(0) + </mtext><mtext mathvariant="italic">x</mtext><mtext>(1)</mtext><mtext mathvariant="italic">D</mtext><mtext> + </mtext><mtext mathvariant="italic">x</mtext><mtext>(2)</mtext><msup><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext>2</mtext></mrow></msup><mtext> + ···</mtext></mrow></math><img file="EP1069722A2_D0136.tif" /></maths>. Refer to {x(t)} ↔ X(D) as a D-transform pair. The space <img file="EP1069722A2_D0022.tif" />[[D]] of all formal series is an integral domain whose invertible elements are those that are not multiples of D.

0099The action of the binary convolutional encoder is linear and is characterized by the so-called impulse responses<img file="EP1069722A2_D0137.tif" /> associating ouput yj(t) with input xi(τ). Specifically,<maths id="math0092" num=""><img file="EP1069722A2_D0138.tif" /></maths> where * denotes discrete convolution. Then the D-transform of the j-th output of the convolutional encoder is given by<maths id="math0093" num=""><img file="EP1069722A2_D0139.tif" /></maths> Thus, the encoder action is summarized by the matrix equation<maths id="math0094" num=""><img file="EP1069722A2_D0140.tif" /></maths> where<maths id="math0095" num=""><img file="EP1069722A2_D0141.tif" /></maths> and<maths id="math0096" num=""><img file="EP1069722A2_D0142.tif" /></maths>

0100Consider the natural space-time formatting of C in which the output sequence corresponding to Yj(D) is assigned to the j-th transmit antenna. Characterize the spatial diversity that can be achieved by this scheme. A preferred algebraic analysis technique considers the rank of matrices formed by concatenating the column vectors<maths id="math0097" num=""><img file="EP1069722A2_D0143.tif" /></maths> Specifically, for a1, a2,..., an ∈ <img file="EP1069722A2_D0022.tif" />, let<maths id="math0098" num=""><img file="EP1069722A2_D0144.tif" /></maths> Then the following theorem relating the spatial diversity of the space-time code C in the quasi-static fading channel to the rank of these matrices over <img file="EP1069722A2_D0022.tif" />[[D]] is considered.

0101Theorem 8Let C denote the threaded space-time code consisting of the binary convolutional code C, whose k × n transfer function matrix is<maths id="math0099" num=""><img file="EP1069722A2_D0145.tif" /></maths>and the spatial modulatorfL in which the output<maths id="math0100" num=""><img file="EP1069722A2_D0146.tif" /></maths>is assigned to antenna j along threaded layer L. Let v be the smallest integer having the property that, whenever<maths id="math0101" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>2</mtext></mrow></msub><mtext> + · · + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">v</mtext></mrow></math><img file="EP1069722A2_D0147.tif" /></maths>, the k × n matrixF(a1, a2,···, an) has full rank k over<img file="EP1069722A2_D0022.tif" />[[D]]. Then the space-time code C achieves d-level spatial transmit diversity over the quasi-static fading channel where<maths id="math0102" num=""><math display="inline"><mrow><mtext mathvariant="italic">d</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">v</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0148.tif" /></maths>and v ≥ k.

0102Proof: All of the code words of C are of the form<maths id="math0103" num=""><img file="EP1069722A2_D0149.tif" /></maths> Under the stipulated conditions of the theorem and following the argument of Theorem ?? (threaded stacking construction), only the all-zero code word has v or more all-zero rows, so the spatial transmit diversity of C is at least <maths id="math0104" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">v</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0150.tif" /></maths>. On the other hand, since v is the smallest integer having the stated property, there is some information sequence X(D) resulting in a code word with v - 1 all-zero rows. Hence, the spatial transmit diversity of C is precisely <maths id="math0105" num=""><math display="inline"><mrow><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">v</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0151.tif" /></maths>.

0103Rate 1/n' convolutional codes with n' < n can also be put into this framework. Let C be a binary convolutional code with transfer function matrix<maths id="math0106" num=""><img file="EP1069722A2_D0152.tif" /></maths> The coded bits are to be distributed among n transmit antennas. For simplicity, consider the case in which <maths id="math0107" num=""><math display="inline"><mrow><mtext mathvariant="italic">s</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext>/</mtext><mtext mathvariant="italic">n'</mtext></mrow></math><img file="EP1069722A2_D0153.tif" /></maths> is an integer and the coded bits are assigned to the antennas periodically. Thus, for each of the coded bit streams Yi(D) ↔ {yi(t)}, the subsequence yi(0), yi(s), yi(2s),... is assigned to antenna si; the subsequence<img file="EP1069722A2_D0154.tif" /> is assigned to antenna si + 1; and so on. Alternate assignments such as symbol based demultiplexing would also be possible and can be analyzed using the same framework.

0104In general, partition the series X(D) corresponding to {x(t)} into its modulo s components Xj(D) corresponding to the subsequences {x(st + j)}<maths id="math0108" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>∞</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext><mtext>=0</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0155.tif" /></maths> (j = 0, 1, 2,..., s - 1). Then<maths id="math0109" num=""><img file="EP1069722A2_D0156.tif" /></maths> Similarly, partition Gi(D) into components<img file="EP1069722A2_D0157.tif" /> and<img file="EP1069722A2_D0158.tif" /> into components<img file="EP1069722A2_D0159.tif" /> The space-time code C under consideration therefore consists of the binary code C together with a spatial modulator function in which<img file="EP1069722A2_D0160.tif" /> is assigned to antenna si + j.

0105By multiplying the expansions for X(D) and<img file="EP1069722A2_D0161.tif" /> and collecting terms, it can be shown that the coded bit stream assigned to antenna si + j is given by<maths id="math0110" num=""><img file="EP1069722A2_D0162.tif" /></maths> where<maths id="math0111" num=""><img file="EP1069722A2_D0163.tif" /></maths> In matrix form,<maths id="math0112" num=""><img file="EP1069722A2_D0164.tif" /></maths> which is the dot product of row vector<maths id="math0113" num=""><img file="EP1069722A2_D0165.tif" /></maths> and column vector<maths id="math0114" num=""><img file="EP1069722A2_D0166.tif" /></maths>

0106The theorem now applies directly. The spatial transmit diversity achieved by C is given by <maths id="math0115" num=""><math display="inline"><mrow><mtext mathvariant="italic">d</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">v</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0167.tif" /></maths>, where v is the smallest integer having the property that, whenever <maths id="math0116" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">0</mtext></mrow></msub><mtext> + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext> + ··· + </mtext><msub><mrow><mtext mathvariant="italic">a</mtext></mrow><mrow><mtext mathvariant="italic">n</mtext><mtext>-1</mtext></mrow></msub><mtext> = </mtext><mtext mathvariant="italic">v</mtext></mrow></math><img file="EP1069722A2_D0168.tif" /></maths>, the s × n matrix F(a0, a1, ···, an-1) has full rank s. In particular, the best possible spatial transmit diversity is <maths id="math0117" num=""><math display="inline"><mrow><mtext mathvariant="italic">d</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext><mtext> - </mtext><mtext mathvariant="italic">s</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0169.tif" /></maths>. When <maths id="math0118" num=""><math display="inline"><mrow><mtext mathvariant="italic">n'</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1069722A2_D0170.tif" /></maths>, s = 1 so that full spatial transmit diversity <maths id="math0119" num=""><math display="inline"><mrow><mtext mathvariant="italic">d</mtext><mtext> = </mtext><mtext mathvariant="italic">n</mtext></mrow></math><img file="EP1069722A2_D0171.tif" /></maths> is possible as expected.

0107Example. Consider the optimal dfree = 5 convolutional code with generators <maths id="math0120" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>0</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">D</mtext><mtext>) = 1 + </mtext><msup><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></math><img file="EP1069722A2_D0172.tif" /></maths> and <maths id="math0121" num=""><math display="inline"><mrow><msub><mrow><mtext mathvariant="italic">G</mtext></mrow><mrow><mtext>1</mtext></mrow></msub><mtext>(</mtext><mtext mathvariant="italic">D</mtext><mtext>) = 1 + </mtext><mtext mathvariant="italic">D</mtext><mtext> + </mtext><msup><mrow><mtext mathvariant="italic">D</mtext></mrow><mrow><mtext>2</mtext></mrow></msup></mrow></math><img file="EP1069722A2_D0173.tif" /></maths>. In the case of two transmit antennas, it is clear that the natural threaded space-time code achieves d = 2 level diversity.

0108In the case of four transmit antennas, note that the rate 1/2 code can be written as a rate 2/4 convolutional code with generator matrix:<maths id="math0122" num=""><img file="EP1069722A2_D0174.tif" /></maths> By inspection, every pair of columns is linearly independent over <img file="EP1069722A2_D0022.tif" />[[D]]. Hence, the natural periodic distribution of the code across four transmit antennas produces a threaded space-time code achieving the maximum d = 3 transmit spatial diversity.

0109For six transmit antennas, express the code as a rate 3/6 code with generator matrix;<maths id="math0123" num=""><img file="EP1069722A2_D0175.tif" /></maths> Every set of three columns in the generator matrix has full rank over <img file="EP1069722A2_D0022.tif" />[[D]], so the natural space-time code achieves maximum d = 4 transmit diversity.

0110Thus far, the design of threaded space-time codes that exploit the spatial diversity over quasi-static fading channels has been considered. One of the advantages of the threaded architecture, however, is its ability to jointly exploit the spatial diversity, provided by the multiple transmit and receive antennas, and the temporal diversity, provided by the time variations in the block fading channel. In fact, the results obtained for threaded space-time code design for the quasi-static fading channel are easily extended to the more general block fading channel.

0111In the absence of interference from other threads, the quasi-static fading channel under consideration can be viewed as a block fading channel with receive diversity, where each fading block is represented by a different antenna. For the threaded architecture with n transmit antennas and a quasi-static fading channel, there are n independent and non-interfering fading links per code word that can be exploited for transmit diversity by proper code design. In the case of the block fading channel, there is a total of nB such links, where B is the number of independent fading blocks per code word per antenna. Thus, the problem of block fading code design for the threaded architecture is addressed by simply replacing parameter n by nB.

0112For example, the following "multi-stacking construction" is a direct generalization of Theorem 4 to the case of a block fading channel.

0113Theorem 9 (Threaded Multi-Stacking Construction)Let<img file="EP1069722A2_D0026.tif" />be a threaded layer of spatial span n. Given binary matricesM1,1, M2,1,..., Mn,1,..., M1,B, M2,B,..., Mn,B of dimension k × l, let C be the binary code of dimension k consisting of all code words of the form<maths id="math0124" num=""><img file="EP1069722A2_D0176.tif" /></maths>wherexdenotes an arbitrary k-tuple of information bits, and B is the number of independent fading blocks spanning one code word. LetfL denote the spatial modulator having the property that µ (xMj,v) is transmitted in the symbol intervals of<img file="EP1069722A2_D0026.tif" />that are assigned to antenna j in the fading block v.

0114Then, as the space-time code in a communication system with n transmit antennas and m receive antennas, the space-time code C consisting of C andfL achieves spatial diversity dm in a B-block fading channel if and only if d is the largest integer such thatM1,1, M2,1,..., Mn,Bhave the have the property that<maths id="math0125" num=""><img file="EP1069722A2_D0177.tif" /></maths>

0115Proof: This result is immediate from the equivalent quasi-static model with nB transmit antennas.

3.3 Performance Bound

0116In this section, the diversity advantage achieved by the threaded architecture when the iterative MMSE algorithm is used is investigated.

0117Proposition 10Let C be a d-diversity code used in each thread in a setting with n transmit and m receive antenna, then the zero-forcing receiver achieves spatial diversity<maths id="math0126" num=""><math display="inline"><mrow><mtext mathvariant="italic">d'</mtext><mtext> = </mtext><mtext mathvariant="italic">d</mtext><mtext> · (</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1)</mtext></mrow></math><img file="EP1069722A2_D0178.tif" /></maths>

0118Proof: To detect the signal transmitted from the n-th antenna, the zero forcing receiver projects the received signal on the null space of S(n/i). Let <img file="EP1069722A2_D0179.tif" />i be the null space of<img file="EP1069722A2_D0180.tif" /> and<img file="EP1069722A2_D0181.tif" /> be a <maths id="math0127" num=""><math display="inline"><mrow><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1) × </mtext><mtext mathvariant="italic">m</mtext></mrow></math><img file="EP1069722A2_D0182.tif" /></maths> matrix whose rows are orthonormal vectors of<img file="EP1069722A2_D0183.tif" /> then the <maths id="math0128" num=""><math display="inline"><mrow><mtext>(</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1) × 1</mtext></mrow></math><img file="EP1069722A2_D0184.tif" /></maths> output vector corresponding to c<maths id="math0129" num=""><math display="inline"><mrow><mfrac linethickness="0" numalign="left" denomalign="left"><mrow><mtext>(</mtext><mtext mathvariant="italic">i</mtext><mtext>)</mtext></mrow><mrow><mtext mathvariant="italic">t</mtext></mrow></mfrac></mrow></math><img file="EP1069722A2_D0185.tif" /></maths> is computed as<maths id="math0130" num=""><img file="EP1069722A2_D0186.tif" /></maths> The elements of<img file="EP1069722A2_D0187.tif" /> are independent Gaussian random variables with<img file="EP1069722A2_D0188.tif" /> Note that, in general<img file="EP1069722A2_D0189.tif" /> Hence, at the output of the zero forcing filter, the channel is equivalent to an interference-free correlated block fading channel with n blocks and <maths id="math0131" num=""><math display="inline"><mrow><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1</mtext></mrow></math><img file="EP1069722A2_D0190.tif" /></maths> receive antennas. Since the different equivalent Gaussian fading gains are linearly independent, the channel correlation matrix is of full rank. Thus, the diversity order is <maths id="math0132" num=""><math display="inline"><mrow><mtext mathvariant="italic">d</mtext><mtext> · (</mtext><mtext mathvariant="italic">m</mtext><mtext> - </mtext><mtext mathvariant="italic">n</mtext><mtext> + 1)</mtext></mrow></math><img file="EP1069722A2_D0191.tif" /></maths>.

0119Let<img file="EP1069722A2_D0192.tif" /> denote the signal-to-interference-plus-noise ratio (SIR) for a symbol transmitted from the i-th antenna after the j-th iteration of the iterative MMSE algorithm. Then, conditioning on the set of path gains,<maths id="math0133" num=""><img file="EP1069722A2_D0193.tif" /></maths> where wj is the vector of feed-forward filter coefficients used in the j-th iteration.

0120Proposition 11Let C be a d-diversity code used in each thread in a setting with n transmit and m receive antenna. The SIR at the output of the iterative MMSE detector after j iterations is at least as large as the SIR after one iteration. Furthermore, output SIR is at least as large as that produced by the zero-forcing detector.

0121Proof: If<img file="EP1069722A2_D0194.tif" /> denotes the SIR at the output of the zero-forcing detector, then it follows from the definition of the MMSE receiver that<img file="EP1069722A2_D0195.tif" /> Also, from the definition of the MMSE filter, it follows that<maths id="math0134" num=""><img file="EP1069722A2_D0196.tif" /></maths> as was to be shown.

0122The output of the MMSE receiver can be tightly approximated by a Gaussian random variable in additive white Gaussian noise (AWGN) channels. In the space-time code setting, the channel is AWGN when conditioned an the path gains. Thus, the diversity advantage achieved by the iterative MMSE receiver for the threaded architecture is approximately lower bounded by the performance achieved by the zero-forcing receiver. Consequently, in a threaded architecture using d-space-time codes, the iterative MMSE receiver can achieve diversity d' satisfying<maths id="math0135" num=""><img file="EP1069722A2_D0197.tif" /></maths> This lower bound justifies the approach to code design for the threaded architecture in accordance with the present invention. In particular, the design criteria developed in Theorems 4 and 9 for optimizing the channel coding for each thread in the absence of interference also serves to maximize a lower bound on the diversity advantage when the iterative MMSE detector is used to mitigate the interference from other threads. The simulation results of Section 5 suggest that the lower bound is in fact a pessimistic estimate of the performance of the threaded architecture with iterative MMSE multi-user detection.

4. System Comparisons

0123A high-level comparison, of the various architectures is shown in Table I below. As shown in the table, all of the transmission formats achieve comparable efficiency. Here, efficiency refers to the number of information symbols per vector channel use. For example, in the horizontal layering scheme, there are n layers each containing a code word of length ℓb and rate r. Thus, successful use of all transmission resources provides a total of n · (rℓb) information symbols. Normalizing by the total number of symbol transmission intervals ℓ gives an efficiency of nrb information symbols per transmitted symbol interval. For the diagonal-layering, the efficiency is somewhat less since the diagonal layers cannot utilize a portion of the transmission resources (the result in the table assumes the width of the diagonal w = 1).

0124The diversity orders achieved by time various architectures in both quasi-static and block fading channels are also indicated in Table I. In the different approaches, the channel coding schemes are assumed to achieve the maximum possible diversity level for rate r codes. Since no attempt has been made to optimize the coding for the diagonal layering architecture, the results reported in the table are on a per-symbol basis. In the prior architectures, the diversity order is variable. Table I shows the range of values (minimum value : maximum value) and notes whether the variation is from layer to layer or from symbol to symbol. In the case of the threaded architecture, the diversity order is not variable in this way. Since the exact value is unknown, Table I gives upper and lower bounds. For the block fading channel, the parameter B denotes the number of fading blocks per code word.

0125The threaded layering is similar to V-BLAST in that each transmitted symbol in a thread is subject to interference from n - 1 other layers, but better spatial diversity is achieved through more efficient transmit diversity and multi-user detection signal processing. The threaded layering is similar to D-BLAST in that all of the transmit antennas are used equally by each component coded transmission. Threaded layering, however, more fully exploits the available temporal diversity since temporal interleaving is allowed across each transmit antenna. Furthermore, unlike D-BLAST, the threaded layering with space-time code design and iterative multi-user detection algorithms provide uniform spatial diversity from symbol to symbol. Unlike the horizontal multi-layering approach with group interference suppression, the threaded architecture provides uniform performance from one component space-time code to the next. Each component space-time code therefore can, under the ideal interference cancellation assumption, achieve full spatial and temporal diversity. <tables id="tabl0001" num="0001"><img file="EP1069722A2_D0198.tif" /></tables><tables id="tabl0002" num="0002"><img file="EP1069722A2_D0199.tif" /></tables>

5. Performance Comparisons

0126In this section, the performance of iterative multi-user detection applied to layered space-time architectures is investigated by means of simulation. The first study considers the conventional layered architecture and demonstrates the advantage of the iterative methods of the present invention over existing zero-forcing techniques. The second study looks at the threaded space-time architecture, in which the layering and channel coding are optimized for iterative multi-user detection, and demonstrates that significant performance improvements can be achieved by this new approach.

0127Throughout the simulation study rate 1/2 convolutional codes are used. The results are obtained by averaging the bit and frame error rates of all the component codes. The channel decoder is based on the soft output Viterbi algorithm (SOVA). The frame length is 100 bits. The iterative MMSE receiver is considered in more detail because it provides a compromise between complexity and performance among the three presented iterative receivers.

0128While, in essence no restrictions were imposed on the number of receive antennas, the performance of the threaded space-time architecture can be expected to degrade if m << n. The reason is that in practice a reasonably large number of receive antennas is required to remove the interference. In the next section, it is shown that excellent performance can be achieved for the case of m - n, showing substantial gain over the group suppression multi-layering approach.

5.1 Layered Space-Time Architecture

0129Figure 7 illustrates the performance of the iterative MMSE receiver with single-dimensional channel codes. The number of transmit and receive antennas is 4 and the bandwidth efficiency of this system is 2 bits/sec/hz (i.e. BPSK modulation). For comparison purposes, a lower bound on the frame error rate of the LST approach is included, as well as the performance of the single user systems which assumes the presence of only one transmit antenna and 4 receive antennas. The LST lower bound assumes error-free decision feedback. The other bound is a lower bound on the performance achieved by the optimum receiver.

0130It can be seen that the performance of the proposed iterative MMSE receiver 40 is within a fraction of a decibel of the interference-free performance. This is 2 dB better than the best possible performance of LST. In fact, while the performance of the LST is expected to be close to the lower bound at high signal-to noise ratios, the bound is expected to be loose at low signal-to-noise ratio due to error propagation. Hence, the relative advantage of the iterative MMSE receiver is larger.

0131The combination of space-time codes with iterative decoding techniques can be even more potent. In Figure 8, the performance of the combined space-time coding and iterative MMSE reception scheme (Iterative MMSE + STC) described above is illustrated where the output of each component convolutional code is distributed among two antennas. It is shown that this scheme provides a gain of about 1 dB over the iterative MMSE receiver combined with single dimensional coding. It is quite remarkable that this gain comes without any additional complexity at either the transmitter or the receiver. Overall, the gain provided by the combined architecture compared with the LST is more than 3 dB in this scenario. This gain increases with the number of antennas because of the superior ability of the present invention to exploit the diversity advantage provided by the multiple transmit and receive antennas.

0132Figure 8 illustrates another advantage of the Iterative MMSE + STC scheme. In this figure, the case with 4 transmit and 2 receive antennas is considered As discussed earlier, the LST receiver architecture cannot be used in tins scenario because m < n This system is equivalent to space-time multiple access channel with 2 space-time users. The two space-time users have equal energy and use two antennas for their transmission. It was been shown that with 2 receive antennas, the performance of this system is same as a space-time multiple access channel with one space-time user and one receive antenna using the interference cancellation technique (i.e, the second receive antenna is used to remove the interference of the other space-time user). To compare this result with the scheme of the present invention, the performance of 2 transmit/1 receive and 2 transmit/2 receive antennas which transmit 1 bit/sec/hz (i.e, equivalent to one space-time user) was also depicted in the Figure. It is shown that by jointly decoding the two space-time users, using the iterative MMSE technique, a 3 - 4 dB gain is achieved over the blind interference cancellation scheme which was shown to be equivalent to the 2 transmit/1 receive scenario.

5.2 Threaded Space-Time Architecture

0133In this section, the performance of the threaded space-time (TST) architecture of the present invention and the combined group interference suppression and space-time coding (TNSC) architecture are compared.

0134Figures 9, 10 and 11 compare the performance of the two schemes for the case of 4 transmit/4 receive and 8 transmit/8 receive antennas, respectively. In the TST architecture, periodic bit interleaving was used to distribute the symbols. QPSK modulation with Gray mapping was used to map the binary input to each antenna to a complex constellation. Hence, the spectral efficiency is 4 bits/sec/hz and 8 bits/sec/hz, respectively. From the figures, the significant gain provided by the TST over the TNSC scheme is clear. Indeed, the TST approach shows a gain of 3-7 dB over the TNSC scheme. The TST results are within 2-3 dB of the outage capacity.

0135Two main reasons contribute to this advantage. First, the ability of the iterative MMSE receiver 40 of the present invention to eliminate the interference with only a minor loss in the diversity advantage. Second, the generalized stacking construction coupled with the use of convolutional codes with the best minimum distance provide a better coding advantage over the hand-crafted trellis code used by the TNSC architecture. Note also that 8 state codes are used while, in the TNSC architecture, a 32 states codes were used. The gain in diversity advantage achieved by the TST architecture can be seen in the steeper asymptotic slope of the performance curve. It is also shown that the gain provided by the TST increases with the number of antennas, again due to the better exploitation of the diversity in the system.

6. Conclusions

0136In accordance with the present invention, the design problem for multiple antenna systems operating over the fading channel is addressed. The problem was addressed herein from both a signal processing and a space-time coding perspective. From the signal processing side, a set of iterative algorithms for joint decoding and detection are presented that provide a trade-off between performance and complexity. Simulation results are provided for the iterative MMSE receiver, establishing its ability to approach the interference-free performance lower bound within a fraction of a dB. From the space-time coding perspective, the BPSK modulation scenario was considered. Under this assumption, convolutional based, space-time codes were presented that exploit the spatial diversity provided by both the transmit and receive antennas. The new scheme avoids some of the limitations of the layered space-time architecture. Then, the more general case of arbitrary non-zero complex constellation was considered and a new scheme, the threaded space-time architecture, as presented in accordance with the present invention. This new approach was shown through simulation to achieve a significant gain over combined array processing and space-time coding.

0137As a final remark, in the absence of interference from other threads, the fading channel is equivalent to the block fading channel with receive diversity, where each fading block is represented by a different antenna. The algebraic framework developed for threaded space-time code design is therefore also useful in the study of code design for block fading channels and is applicable to both block and trellis-based codes.

0138Although the present invention has been described with reference to a preferred embodiment thereof, it will be understood that the invention is not limited to the details thereof. Various modifications and substitutions have been suggested in the foregoing description, and others will occur to those of ordinary skill in the art. All such substitutions are intended to be embraced within the scope of the invention as defined in the appended claims.

Every citation, both ways

Citations
Document	Relation	Office	Cited during
US7453922B2	Cited by	United States of America	Applicant
EP1453262A1	Cited by	European Patent Office (EPO)	Search report
US11552660B2	Cited by	United States of America	Applicant
US7292658B2	Cited by	United States of America	Applicant
GB2407007A	Cited by	United Kingdom	Search report
US7043638B2	Cited by	United States of America	Applicant
CN104618082A	Cited by	China	Search report
WO2005025118A1	Cited by	World Intellectual Property Organization (WIPO)	International search
US7164706B2	Cited by	United States of America	Applicant
US7376175B2	Cited by	United States of America	Applicant
US12395198B2	Cited by	United States of America	Applicant
EP1643657A1	Cited by	European Patent Office (EPO)	Search report
US7210062B2	Cited by	United States of America	Applicant
US7139306B2	Cited by	United States of America	Applicant
FR2859328A1	Cited by	France	Search report
US7218668B2	Cited by	United States of America	Applicant
WO03058844A1	Cited by	World Intellectual Property Organization (WIPO)	International search
US7684525B2	Cited by	United States of America	Applicant
WO2004008680A1	Cited by	World Intellectual Property Organization (WIPO)	International search
CN1310458C	Cited by	China	Search report
US7636407B2	Cited by	United States of America	Applicant
FR2841068A1	Cited by	France	Search report
GB2407007B	Cited by	United Kingdom	Search report
US7376175B2	Cited by	United States of America	Applicant
US7110440B2	Cited by	United States of America	Applicant
US8908496B2	Cited by	United States of America	Applicant
EP1959600A1	Cited by	European Patent Office (EPO)	Search report
WO2005074147A1	Cited by	World Intellectual Property Organization (WIPO)	International search
JP2022065536A	Cited by	Japan	Search report
US7110437B2	Cited by	United States of America	Applicant
US11916581B2	Cited by	United States of America	Applicant
US7110431B2	Cited by	United States of America	Applicant
US7177344B2	Cited by	United States of America	Applicant
WO2005025118A1	Cited by	World Intellectual Property Organization (WIPO)	International search
US7760828B2	Cited by	United States of America	Applicant
EP3985892A1	Cited by	European Patent Office (EPO)	Search report
WO03107582A2	Cited by	World Intellectual Property Organization (WIPO)	International search
US7099374B2	Cited by	United States of America	Applicant
KR20030068782A	Cited by	Republic of Korea	Search report
EP1643657A1	Cited by	European Patent Office (EPO)	Search report
US7327780B2	Cited by	United States of America	Applicant
CN114374585A	Cited by	China	Search report
WO2005074147A1	Cited by	World Intellectual Property Organization (WIPO)	International search
US7327780B2	Cited by	United States of America	Applicant
GB2394389A	Cited by	United Kingdom	Search report
FR2859328A1	Cited by	France	Search report
US7248623B2	Cited by	United States of America	Applicant
CN100399733C	Cited by	China	Search report
GB2394389B	Cited by	United Kingdom	Search report
WO03107582A3	Cited by	World Intellectual Property Organization (WIPO)	International search

2 members in 2 offices

This recordMember, by publication datePriority claim

Priority claims4

Priority claims
Document	Office	Kind	Date
14329399	United States of America	P	1999-07-12
143293P	United States of America	–	1999-07-12
US19990143293P	–	–	–
143293P	–	–	–

Members2

Family members, oldest first
Document	Office	Kind
EP1069722A2This record	European Patent Office (EPO)	A2	2001-01-17
US6898248B1	United States of America	B1	2005-05-24

5 legal events, as the office reported them to INPADOC

Over the term

Point at a mark for the event

Events

Legal events, newest first
	Event	Code
2005-08-10	Application deemed to be withdrawnWithdrawn18D	18D
2005-06-24	Information on the status of an ep patent application or granted ep patentGrantedSTATUS: THE APPLICATION IS DEEMED TO BE WITHDRAWNSTAA	STAA
2001-01-17	Designated contracting statesAK	AK
2001-01-17	Request for extension of the european patentAL;LT;LV;MK;RO;SIAX	AX
2000-12-01	Public reference made under article 153(3) epc to a published international application that has entered the european phaseORIGINAL CODE: 0009012PUAI	PUAI

Wireless communication system and method having a space-time architecture, and receiver for multi-user detection

Abstract

Term

Priority claims4

Members2

Over the term

Events

Numbers

Titles3

Classification

Designated states25