REGISTER  |  SIGN IN
United States Patent Application20040146014
Kind CodeA1
Hammons, A. Roger JR. ; et al.July 29, 2004
Method and constructions for space-time codes for PSK constellations for spatial diversity in multiple-element antenna systems
Abstract
General binary design criteria for PSK-modulated space-time codes are provided. For linear binary PSK (BPSK) codes and quadrature PSK (QPSK) codes, the rank (i.e., binary projections) of the unmodulated code words, as binary matrices over the binary field, is used as a design criterion. Fundamental code constructions for both quasi-static and time-varying channels are provided.
Inventors:Hammons; A. Roger JR. (North Potomac, MD), Gamal; Hesham El  (Laurel, MD)
Correspondence Name and Address:Patent Docket Administration Bldg. 1, Mail Stop A109 P.O. Box 956
Hughes Electronics Corporation
El Segundo
CA
90245-0956
US
Series Code:755981
Filed:January 13, 2004
U.S. Current Class:370/320; 370/342; 370/334
U.S. Class at Publication:370/320; 370/342; 370/334
Intern'l Class:H04Q 007/00; H04B 007/216
Claims

What is claimed is:
1. A communication system comprising: a framer for segmenting transmit data blocks into fixed frame lengths for generating information symbols from a discrete alphabet of symbols; a plurality of antenna links; a channel encoder for encoding the generated information symbols with an error control code for producing code word symbols; a spatial formatter for parsing the produced code word symbols to allocate the symbols to a presentation order among said plurality of antenna links; and a phase shift keying modulator for mapping the parsed code word symbols onto constellation points from a discrete complex-valued signaling constellation according to binary projections to achieve spatial diversity.

2. A communication system as recited in claim 1 comprising data terminal equipment (DTE) coupled to said framer for communicating digital cellular data blocks.

3. A communication system as recited in claim 2 wherein said digital cellular data terminal equipment comprises Code Division Multiple Access (CDMA) systems.

4. A communication system as recited in claim 2 wherein said digital cellular data terminal equipment comprises Time Division Multiple Access (TDMA) systems.

5. A communication system as recited in claim 1 wherein said channel encoder comprises a mobile channel encoder producing the code word symbols having length of a multiple N of the number of said plurality of antenna links L.

6. A communication system as recited in claim 5 wherein said spatial formatter parses the length N of the produced code word symbols among L antennas.

7. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein the combination of channel encoder and spatial formatter are chosen from the class of space-time codes satisfying a binary rank criteria.

8. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein the combination of channel encoder and spatial formatter are provided with a stacking space-time code construction.

9. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein binary phase shift keying (BPSK) modulation is used and the space-time code is based on formatting the output of convolutional channel encoder for presentation across the transmit antennas.

10. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein a concatenated space-time code is used in which the outer code is used to satisfy a binary rank criteria and multiple inner codes are used to encode the transmitted information from the multiple transmit antennas.

11. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein a concatenated space-time code is used in which the inner code is composed of a channel encoder and a spatial formatter designed to satisfy a binary rank criteria.

12. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein the combination of channel encoder and spatial formatter are covered by a multi-stacking construction.

13. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein quadrature phase shift keying (QPSK) modulation is used and the space-time code is covered by a stacking, multi-stacking, or de-stacking constructions for QPSK.

14. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein QPSK modulation is used and the space-time code is based on formatting the output of a linear convolutional code over the ring of integers modulo 4 for presentation across the multiple transmit antennas.

15. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein QPSK modulation is used and the space-time code employs a dyadic construction.

16. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein multi-level coded modulation and multi-stage decoding are used and the binary space-time code employed in each level belongs to the class of codes that satisfy the binary rank criterion or any of the constructions.

17. A communication system as recited in claim 2 comprising two transmit antennas wherein M-ary P5K modulation, M=8 or more, is used and the space-time code belongs to a class satisfying the binary rank criteria or any of the constructions.

18. A communication system as recited in claim 2 comprising a plurality of transmit antennas, wherein graphical space-time codes are designed such that the code generating matrix satisfies the stacking, multi-stacking, or de-stacking construction.

19. A communications method comprising: generating information symbols for data block frames of fixed length; encoding the generated information symbols with an underlying error control code to produce the code word symbols; parsing the produced code word symbols to allocate the symbols in a presentation order to a plurality of antenna links; mapping the parsed code word symbols onto constellation points from a discrete complex-valued signaling constellation; transmitting the modulated symbols across a communication channel with the plurality of antenna links; providing a plurality of receive antennas at a receiver to collect incoming transmissions; and decoding received baseband signals with a space-time decoder.

20. A method as recited in claim 19 wherein said encoding and parsing steps are performed with a space-time encoder having a channel encoder and a space-time formatter.

21. A communications system comprising: means for generating information symbols for data block frames of fixed length; means for encoding the generated information symbols with an 5 underlying error control code to produce the code word symbols; means for parsing the produced code word symbols to allocate the symbols in a presentation order to a plurality of antenna links; means for mapping the parsed code word symbols onto constellation points from a discrete complex-valued signaling constellation; means for transmitting the modulated symbols across a communication channel with the plurality of antenna links; means for providing a plurality of receive antennas at a receiver to collect incoming transmissions; and means for decoding received base band signals with a space-time decoder.

22. A communication system as recited in claim 21 wherein said encoding means comprises a mobile channel encoder producing the codeword symbols having length of a multiple N of the number of said plurality of antenna links L.

23. A communication system as recited in claim 22 wherein said parsing means comprises a spatial formatter for parsing the length N of the produced code word symbols among L antennas.

24. A communication system as recited in claim 21 wherein said encoding and parsing means comprise a space-time encoder having a channel encoder and a space-time formatter.

25. A communication system as recited in claim 24 comprising receiving means for collecting incoming transmissions demodulated with a phase shift keying demodulator and a space-time decoder to demodulate the code word symbols.
Description


[0001] This application claims priority to U.S. Provisional patent application Serial No. 60/101,029, filed Sep. 18, 1998 for "Method and Constructions for Space-Time Codes for PSK Constellations", and U.S. Provisional patent application Serial No. 60/144,559, filed Jul. 16, 1999
for "Method and Constructions for Space-Time, Codes for PSK Constellations II", both of which were filed by A. Roger Hammons, Jr. and Hesham El Gamal.

FIELD OF THE INVENTION

[0002] The invention relates generally to PSK-modulated space-time codes and more specifically to using fundamental code constructions for quasi-static and time-varying channels to provide full spatial diversity for an arbitrary number of transmit antennas.

BACKGROUND OF THE INVENTION

[0003] Recent advances in coding theory include space-time codes which provide diversity in multi-antenna systems over fading channels with channel coding across a small number of transmit antennas. For wireless communication systems, a number of challenges arise from the harsh RF propagation environment characterized by channel fading and co-channel interference (CCI). Channel fading can be attributed to diffuse and specular multipath, while CCI arises from reuse of radio resources. Interleaved coded modulation on the transmit side of the system and multiple antennas on the receive side are standard methods used in wireless communication systems to combat time-varying fading and to mitigate interference. Both are examples of diversity techniques.

[0004] Simple transmit diversity schemes (in which, for example, a delayed replica of the transmitted signal is retransmitted through a second, spatially-independent antenna and the two signals are coherently combined at the receiver by a channel equalizer) have also been considered within the wireless communications industry as a method to combat multipath fading. From a coding perspective, such transmit diversity schemes amount to repetition codes and encourage consideration of more sophisticated code designs. Information-theoretic studies have demonstrated that the capacity of multi-antenna systems significantly exceeds that of conventional single-antenna systems for fading channels. The challenge of designing channel codes for high capacity multi-antenna systems has led to the development of "space-time codes," in which coding is performed across the spatial dimension (e.g, antenna channels) as well as time. The existing body of work on space-time codes relates to trellis codes and a block coded modulation scheme based on orthogonal designs. Example code designs that achieve full diversity for systems with only a small number of antennas (L=2 and 3) are known for both structures, with only a relatively small number of space-time codes being known. Thus, a need exists for a methodology of generating and using code constructions which allow systematic development of powerful space-time codes such as general constructions that provide full diversity in wireless systems with a large number of antennas.

[0005] The main concepts of space-time coding for quasi-static, flat Rayleigh fading channels and the prior knowledge as to how to design them will now be discussed. For the purpose of discussion, a source generates k information symbols from the discrete alphabet x, which are encoded by the error control code C to produce code words of length N=nL.sub.t over the symbol alphabet y. The encoded symbols are parsed among L.sub.t transmit antennas and then mapped by the modulator into constellation points from the discrete complex-valued signaling constellation .OMEGA. for transmission across a channel. The modulated streams for all antennas are transmitted simultaneously. At the receiver, there are L.sub.r receive antennas to collect the incoming transmissions. The received baseband signals are subsequently decoded by the space-time decoder. Each spatial channel (the link between one transmit antenna and one receive antenna) is assumed to experience statistically independent flat Rayleigh fading. Receiver noise is assumed to be additive white Gaussian noise (AWGN). A space-time code consists as discussed herein perferably of an underlying error control code together with the spatial parsing format.

[0006] Definition 1 An L.times.n space-time code C of size M consists of an (Ln,M) error control code C and a spatial parser a that maps each code word vector {overscore (c)}.epsilon.C to an L.times.n matrix c whose entries are a rearrangement of those of {overscore (c)}. The space-time code C is said to be linear if both C and .sigma. are linear.

[0007] Except as noted to the contrary, a standard parser is assumed which maps

{overscore (c)}=(c.sub.1.sup.1, c.sub.1.sup.2, . . . , c.sub.1.sup.L.sup..sub.t, c.sub.2.sup.1, c.sub.2.sup.2, . . . , c.sub.2.sup.L.sup..sub.t, . . . , c.sub.n.sup.1, c.sub.n.sup.2, . . . , c.sub.n.sup.L.sup..sub.t).epsilon.C

[0008] to the matrix 1 c = [ c 1 1 c 2 1 c n 1 c 1
2 c 2 2 c n 2 c 1 L t c 2 L t c n L t ] .

[0009] In this notation, it is understood that c.sub.t.sup.i is the code symbol assigned to transmit antenna i at time t.

[0010] Let f:y.fwdarw..OMEGA. be the modulator mapping function. Then s=f(c) is the baseband version of the code word as transmitted across the channel. For this system, the following baseband model of the received signal is presented: 2 y t j = i = 1 L t ij s t i E s + n t j , ( 1 )

[0011] where y.sub.t.sup.j is the signal received at antenna j at time t; .alpha..sub.ij is the complex path gain from transmit antenna i to receive antenna j; s.sub.t.sup.i=f(c.sub.t.sup.i) is the transmitted constellation point corresponding to c.sub.t.sup.i; and n.sub.t.sup.j is the AWGN noise sample for receive antenna j at time t. The noise samples are independent samples of a zero-mean complex Gaussian random variable with variance N.sub.0/2 per dimension. The fading channel is quasi-static in the sense that, during the transmission of n code word symbols across any one of the links, the complex path gains do not change with time t, but are independent from one code word transmission to the next. In matrix notation,

{overscore (Y)}={square root}{square root over (E)}.sub.s{overscore (A)}D.sub.c+{overscore (N)}, (2)

[0012] where

[0013] {overscore (Y)}=[y.sub.1.sup.1y.sub.2.sup.1 . . . y.sub.n.sup.1y.sub.1.sup.2y.sub.2.sup.2 . . . y.sub.n.sup.2 . . . y.sub.1.sup.L.sup..sub.ry.sub.2.sup.L.sup..sub.r . . . y.sub.n.sup.L.sup..sub.r],

[0014] {overscore (N)}=[n.sub.1.sup.1n.sub.2.sup.1 . . . n.sub.n.sup.1n.sub.1.sup.2n.sub.2.sup.2 . . . n.sub.n.sup.2 . . . n.sub.1.sup.L.sup..sub.rn.sub.2.sup.L.sup..sub.r . . . n.sub.n.sup.L.sup..sub.r],

[0015] {overscore (A)}=[.alpha..sub.11.alpha..sub.21 . . . .alpha..sub.L.sub..sub.t.sub.1.alpha..sub..sub.12.alpha..sub.22 . . . .alpha..sub.L.sub..sub.t.sub.2 . . . .alpha..sub.1L.sub..sub.r.alpha..sub- .2L.sub..sub.r . . . .alpha..sub.L.sub..sub.t.sub.L.sub..sub.r], 3 D c = [ f ( c ) 0 0 0 f ( c ) 0
0 0 0 f ( c ) ] L r L t .times. L r n .

[0016] Let code word c be transmitted. Then the pairwise error probability that the decoder prefers the alternate code word e to c is given by

P(c.fwdarw.e.vertline.{.alpha..sub.ij})=P(V<0.vertline.{.alpha..sub.ij}- ),

[0017] where V=.parallel.{overscore (A)}(D.sub.c-D.sub.e)+{overscore (N)}.parallel..sup.2-.parallel.{overscore (N)}.parallel..sup.2 is a Gaussian random variable with mean E{V}=.parallel.{overscore (A)}(D.sub.c-D.sub.e).parallel..sup.2 and variance Var{V}=2N.sub.0E{V}. Thus, 4 P ( V < 0 { ij } ) = Q ( ; A _ ( D c - D e ) r; 2 N 0 ) ( 3 ) 1 2
exp { - 1 4 N 0 ; A _ ( D c - D e ) r; 2
} . ( 4 )

[0018] For the quasi-static, flat Rayleigh fading channel, equation (4) can be manipulated to yield the fundamental bound: 5 P ( c -> { ij } ) ( 1 .PI. i = 1 r ( 1 + i E s / 4
N 0 ) ) L r ( 5 ) ( E s 4 N 0 ) - L r , ( 6 )

[0019] where r=rank(f(c)-f(e)) and .eta.=(.lambda..sub.1.lambda..sub.2 . . . .lambda..sub.r).sup.1/r is the geometric mean of the nonzero eigenvalues of A=(f(c)-f(e))(f(c)-f(e)).sup.H.

[0020] This leads to the rank and equivalent product distance criteria for space-time codes.

[0021] (1) Rank Criterion: Maximize the diversity advantage r=rank(f(c)-f(e)) over all pairs of distinct code words c, e.epsilon.C; and

[0022] (2) Product Distance Criterion: Maximize the coding advantage .eta.=(.lambda..sub.1.lambda..sub.2 . . . .lambda..sub.r).sup.1/r over all pairs of distinct code words c, e.epsilon.C.

[0023] The rank criterion is the more important of the two criteria as it determines the asymptotic slope of the performance curve as a function of E.sub.s/N.sub.0. The product distance criterion is preferably of secondary importance and is ideally optimized after the diversity advantage is maximized. For an L.times.n space-time code C, the maximum possible rank is L. Consequently, full spatial diversity is achieved if all baseband difference matrices corresponding to distinct code words in C have full rank L.

[0024] Simple design rules for space-time trellis codes have been proposed for L=2 spatial diversity as follows:

[0025] Rule 1. Transitions departing from the same state differ only in the second symbol.

[0026] Rule 2. Transitions merging at the same state differ only in the first symbol.

[0027] When these rules are followed, the code word difference matrices are of the form 6 f ( c ) - f ( e ) = [ x 1
0 0 x 2 ]

[0028] with x.sub.1, x.sub.2 nonzero complex numbers. Thus, every such difference matrix has full rank, and the space-time code achieves 2-level spatial diversity. Two good codes that satisfy these design rules, and a few others that do not, have been handcrafted using computer search methods.

[0029] The concept of "zeroes symmetry" has been introduced as a generalization of the above-referenced design rules for higher levels of diversity L.gtoreq.2. A space-time code has zeroes symmetry if every baseband code word difference f(c)-f(e) is upper and lower triangular (and has appropriate nonzero entries to ensure full rank). The zeroes symmetry property is sufficient for full rank but not necessary; nonetheless, it is useful in constraining computer searches for good space-time codes.

[0030] Results of a computer search undertaken to identify full diversity space-time codes with best possible coding advantage have been presented. A small table of short constraint length space-time trellis codes that achieve full spatial diversity (L=2, 3, and 5 for BPSK modulation; L=2
for QPSK modulation) is available. Difficulties, however, are encountered when evaluating diversity and coding advantages for general space-time trellis codes. As a general space-time code construction, delay diversity schemes are known to achieve full diversity for all L.gtoreq.2 with the fewest possible number of states.

[0031] A computer search similar to the above-referenced computer search has identified optimal L=2 QPSK space-time trellis codes of short constraint length. The results agree with the previous results regarding the optimal product distances but the given codes have different generators, indicating that, at least for L=2, there is a multiplicity of optimal codes.

[0032] A simple transmitter diversity scheme for two antennas has been introduced whcih provides 2-level diversity gain with modest decoder complexity. In this scheme, independent signalling constellation points x.sub.1, x.sub.2 are transmitted simultaneously by different transmit antennas during a given symbol interval. On the next symbol interval, the conjugated signals -x.sub.2* and x.sub.1* are transmitted by the respective antennas. This scheme has the property that the two transmissions are orthogonal in both time and the spatial dimension.

[0033] The Hurwitz-Radon theory of real and complex orthogonal designs are a known generalization this scheme to multiple transmit antennas. Orthogonal designs, however, are not space-time codes as defined herein since, depending on the constellation, the complex conjugate operation that is essential to these designs may not have a discrete algebraic interpretation. The complex generalized designs for L=3 and 4 antennas also involve division by {square root}{square root over (2)}.

[0034] To summarize, studies on the problem of signal design for transmit diversity systems have led to the development of the fundamental performance parameters for space-time codes over quasi-static fading channels such as: (1) diversity advantage, which describes the exponential decrease of decoded error rate versus signal-to-noise ratio (asymptotic slope of the performance curve on a log-log scale); and (2) coding advantage, which does not affect the asymptotic slope but results in a shift of the performance curve. These parameters are, respectively, the minimum rank and minimum geometric mean of the nonzero eigenvalues among a set of complex-valued matrices associated with the differences between baseband modulated code words. A small number of interesting, handcrafted trellis codes for two antenna systems have been presented which provide maximum 2-level diversity advantage and good coding advantage.

[0035] One of the fundamental difficulties of space-time codes, which has so far hindered the development of more general results, is the fact that the diversity and coding advantage design criteria apply to the complex domain of baseband modulated signals, rather than to the binary or discrete domain in which the underlying codes are traditionally designed. Thus, a need also exists for binary rank criteria for generating BPSK and QPSK-modulated space-time codes.

SUMMARY OF THE INVENTION

[0036] The present invention overcomes the disadvantages of known trellis codes generated via design rules having very simple structure. In accordance with the present invention, more sophisticated codes are provided using a method involving design rules selected in accordance with the preferred embodiment of the present invention. These codes are straightforward to design and provide better performance than the known codes. The present invention also provides a significant advance in the theory of space-time codes, as it provides a code design method involving a powerful set of design rules in the binary domain. Current design criteria are in the complex baseband domain, and the best code design rules to date are ad hoc with limited applicability.

[0037] The present invention further provides a systematic method, other than the simple delay diversity, of designing space-time codes to achieve full diversity for arbitrary numbers of antennas. The performance of space-time codes designed in accordance with the methodology and construction of the present invention exceed that of other known designs.

[0038] Briefly summarized, the present invention relates to the design of space-time codes to achieve full spatial diversity over fading channels. A general binary design criteria for phase shift keying or PSK-modulated space-time codes is presented. For linear binary PSK (BPSK) codes and quadrature PSK (QPSK) codes, the rank (i.e., binary projections) of the unmodulated code words, as binary matrices over the binary field, is a design criterion. Fundamental code constructions for both quasi-static and time-varying channels are provided in accordance with the present invention.

[0039] A communication method in accordance with an embodiment of the present invention comprises the steps of generating information symbols for data block frames of fixed length, encoding the generated information symbols with an underlying error control code to produce the code word symbols, parsing the produced code word symbols to allocate the symbols in a presentation order to a plurality of antenna links, mapping the parsed code word symbols onto constellation points from a discrete complex-valued signaling constellation, transmitting the modulated symbols across a communication channel with the plurality of antenna links, providing a plurality of receive antennas at a receiver to collect incoming transmissions and decoding received baseband signals with a space-time decoder.

BRIEF DESCRIPTION OF THE DRAWINGS

[0040] The 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:

[0041] FIG. 1 is a block diagram of an exemplary digital cellular Direct Sequence Code Division Multiple Access (DS-CDMA) base-station-to-mobile-s- tation (or forward) link;

[0042] FIG. 2 is a block diagram of a system for a digital cellular system which implements space-time encoding and decoding in accordance with an embodiment of the present invention;

[0043] FIG. 3 is a block diagram illustrating space-time encoding and decoding in accordance with an embodiment of the present invention;

[0044] FIG. 4 is a block diagram of a full-diversity space-time concatenated encoder constructed in accordance with an embodiment of the present invention; and

[0045] FIGS. 5a, 5b, 5c and 5d illustrate how known space-time codes for QPSK modulation over slow fading channels complies with general design rules selected in accordance with an embodiment of the present invention.

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

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

[0047] Referring to FIG. 1, by way of an example, a conventional digital cellular Direct Sequence Code Division Multiple Access (DSCDMA) base-station-to-mobile-station (or forward) link 10 is shown using a conventional convolutional encoder and Viterbi decoder. FIG. 1 also illustrates the mobile-station-to-base-station (or reverse) link.

[0048] At the transmit end, the system 10 in FIG. 1 comprises a data segmentation and framing module 16 where user information bits are assembled into fixed length frames from transmit data blocks 12. The N bits per frame are input to the base station's convolutional encoder 18
of rate r, which produces N/r code symbols at the input of the channel interleaver 20. The channel interleaver 20 performs pseudo-random shuffling of code symbols, and outputs the re-arranged symbols to the spread spectrum modulator 22. The spread spectrum modulator 22 uses a user-specific transmit PN-code generator 24 to produce a spread spectrum signal which is carried on a RF carrier to the transmitter 26, where a high power amplifier coupled to the transmit antenna 28 radiates the signal to the base station. The techniques of spread spectrum modulation and RF transmission are well known art to one familiar with spread spectrum communications systems.

[0049] The signal received at the mobile station antenna 30 is amplified in the RF receiver 32 and demodulated by the spread spectrum demodulator 34, which uses the same PN-code generator 36 as used by the base station transmitter to de-spread the signal. The demodulated symbols are de-interleaved by the channel de-interleaver 38 and input to the Viterbi decoder 40. The decoded information bits are reconstructed using data block reconstruction 42 into receive data blocks 14 and forwarded to the data terminal equipment at the receive end.

[0050] With reference to FIG. 2, a digital cellular base-station-to-mobile-station link is shown to illustrate the implementation of space-time encoding and decoding in accordance with an embodiment of the present invention. While CDMA system is used as an example, one familiar with the art would consider the present invention applicable to other types of wireless systems, which can employ other types of multiple access methods such as time division multiple access (TDMA).

[0051] Transmit data blocks 52 from the data terminal equipment are segmented and framed 56 into fixed frame length and applied to the mobile's channel space-time encoder 58. The output from a channel encoder 60 is fed to the space-time formatter 62 which determines the parsing (allocation and presentation order) of the coded symbols to the various transmit antennas 70a, 70b, 70c. The spatial formatter output is applied to the spread spectrum modulator 64 which uses a user specific PN-code generator 66 to create spread spectrum signals, carried on a RF carrier via base RF transmitter 68, to the mobile station transmitter. The transmitter, with high power amplifier coupled to the Transmit antenna, radiates the signals via separate transmit antennas to the mobile station.

[0052] The signal received at one or more mobile station antenna(s) 72 is amplified in the mobile RF receiver 74 and demodulated in a phase shift keying demodulator 76, which uses the same PN-code generator 78 as used by the base station transmitter, to de-spread the signal. The demodulated symbols are processed at space-time decoder 80 by the space-time de-formatter 82 and input to the channel decoder 84. The decoded information bits are reconstructed 86 into receive data blocks 54 and forwarded to the data terminal equipment at the receive end. Based on the space-time code used, the de-formatter 82 and the decoder 84 can be grouped in a single maximum likelihood receiver.

[0053] FIG. 3 illustrates an exemplary communication system 90 having a path 92 from a source and a path 94 to a sink and which can be a system other than a cellular system. The system 90 has a space-time encoder 96
that is similar to the encoder 58 depicted in FIG. 2 in that it comprises a channel encoder 98 and a spatial formatter 100. Plural modulators 102a, 102b, 102c, and so on, are also provided. At the receiver end, a space-time demodulator 104 and a space-time decoder 106 are provided.

[0054] With continued reference to FIG. 3, the source generates k information symbols from a discrete alphabet X on the path 92 which are encoded by an error control code C by the space-time encoder 96. The space-time encoder 96 produces code words of length N over the symbol alphabet Y. The encoded symbols are mapped by the modulators 102a, 102b, 102c, and so on, onto constellation points from a discrete, complex-valued signaling constellation for transmission across the channel. The modulated radio frequency signals for all of the L transmit antennas 102a, 102b, 102c, and so on, are transmitted at the same time to the receiver space-time demodulator 104. The space-time channel decoder 106 decodes the signals to the received data path 94. As shown, the receiver provides M receive antennas to collect the incoming transmissions. The received baseband signals are subsequently decoded by the space-time decoder 106. The space-time code preferably includes an underlying error control code, together with the spatial parsing format as discussed below.

[0055] FIG. 4 depicts an exemplary concatenated space-time encoder 110 for implementing a full-diversity space-time concatenated coding sequence. The coding sequence employs an outer code 112 which provides signals to a spatial formatter 114. Signals from the spatial formatter 114 are separated for coding at inner code 116a, 116b, 116c, and so on, which provide signals that are modulated, respectively, by modulators 118a, 118b, 118c, and so on, for transmission via antennas 120a, 120b, 120c, and so on. A convolutional encoder applying the binary rank criterion for QPSK modulated space-time codes is shown in block diagram form in FIGS. 5a through 5d in which known trellis space-time codes proposed for QPSK modulation are shown to comply with the general design rules of the present invention. Space-time trellis codes are shown in FIGS. 5a through 5d, respectively, for 4, 8, 16, and 32 states which achieve full spatial diversity. As shown, the delay structures 122, 124, 126, and 128 provided for each respective code design are enough to ensure that L=2 diversity is achieved. In the text below, a number of known codes are shown to be special cases of the general constructions presented in accordance with the present invention. In addition, the present invention provides new delay diversity schemes and constructions such as examples of new BPSK space-time codes for L.gtoreq.2 and new QPSK space-time codes for L.gtoreq.2.

[0056] The present invention is concerned primarily with the design of space-time codes rather than the signal processing required to decode them. In most cases, the decoding employs known signal processing used for maximum likelihood reception.

[0057] The derivation of space-time codes from codes on graphs is a primary feature of the present invention, that is, to define constraints on matrices for linear codes based on graphs to provide full spatial diversity as space-time codes and therefore to design graphical codes for space-time applications. The matrices can be obtained using the present invention. Graphical codes designed in this manner can be decoded using soft-input, soft-output techniques. Thus, performance is close to the Shannon limit. Accordingly, the code constructions or designs of the present invention define the state-of-the-art performance of space-time codes. An improvement of iterative soft-input, soft-output decoding for a space-time channel is marginalization since the receiver need only access the sum of the transmission from the L transmit antennas. This marginalization is improved via iteration.

[0058] A general stacking construction for BPSK and QPSK codes in quasi-static fading channels is presented as another novel feature of the present invention. Examples of this construction are given by the rate 1/L binary convolutional codes for BPSK modulation. A preferred class of QPSK modulated codes is the linear rate 1/L convolutional codes over the integers modulo 4. Specific examples of selected block and concatenated coding schemes for L=2 and L=3 antennas with BPSK and QPSK modulation are provided below. In addition, a dyadic construction for QPSK signals using two binary full rank codes is also described below.

[0059] Another example is provided below of an expurgated, punctured version of the Golay code G.sub.23 that can be formatted as a BPSK-modulated space-time block code achieving full L=2 spatial diversity and maximum bandwidth efficiency (rate 1 transmission). For L=3
diversity, an explicit rate 1 space-time code is derived below which achieves full spatial diversity for BPSK and QPSK modulation. By contrast, known space-time block codes derived from complex, generalized orthogonal designs provide no better bandwidth efficiency than rate 3/4.

[0060] The de-stacking construction is a method of obtaining good space-time overlays for existing systems for operation over time-varying fading channels. The key advantage of these systems is that of robustness because they exploit time and space diversity. There is coding gain both spatially (from the space-time "stacking") and temporally (conventional coding gain achieved by "de-stacking"). The system is not dependent entirely on the spatial diversity, which may not be available under all deployment and channel circumstances. Examples of these are obtained from de-stacking the rate 1/L convolution codes (BPSK) and (QPSK).

[0061] Multi-level code constructions with multi-stage decoding also follow the design criteria of the present invention. Since binary decisions are made at each level, the BPSK design methodology of the present invention applies. For 8-PSK, the binary rank criteria developed for BPSK and QPSK cases also apply for the special case of L=2 antennas. This allows more sophisticated L=2 designs for PSK than is currently commercially available.

[0062] The design of space-time codes in accordance with the present invention will now be described. In Section 1, binary rank criteria for BPSK and QPSK-modulated space-time codes are discussed which are selected in accordance with the present invention. Sections 2 and 3 expand on the use of these criteria to develop comprehensive design criteria in accordance with the present invention. In Section 2, new fundamental constructions for BPSK modulation are provided in accordance with the present invention that encompass such special cases as transmit delay diversity schemes, rate 1/L convolutional codes, and certain concatenated coding schemes. The general problem of formatting existing binary codes into full-diversity space-time codes is also discussed. Specific space-time block codes of rate 1 for L=2 and L=3 antennas are given that provide coding gain, as well as achieve full spatial diversity. In Section 3, .sub.4 analogs of the binary theory are provided in accordance with the present invention. It is also shown that full diversity BPSK designs lift to full diversity QPSK designs. In Section 4, the existing body of space-time trellis codes is shown to fit within the code design criteria of the present invention. Extension of the design criteria to time-varying channels is discussed in Section 5, which describes how multi-stacking constructions in accordance with the present invention provide a general class of "smart-greedy" space-time codes for such channels. Finally, Section 6 discusses the applicability of the binary rank criteria to multi-level constructions for higher-order constellations.

[0063] 1 Binary Rank Criteria for Space-Time Codes

[0064] The design of space-time codes is hampered by the fact that the rank criterion applies to the complex-valued differences between the baseband versions of the code words. It is not easy to transfer this design criterion into the binary domain where the problem of code design is relatively well understood. In section 1, general binary design criteria are provided that are sufficient to guarantee that a space-time code achieves full spatial diversity.

[0065] In the rank criterion for space-time codes, the sign of the differences between modulated code word symbols is important. On the other hand, it is difficult to see how to preserve that information in the binary domain. In accordance with the present invention, what can be said in the absence of such specific structural knowledge is investigated by introducing the following definition.

[0066] Definition 2 Two complex matrices r.sub.1 and r.sub.2 is said to be .omega.-equivalent if r.sub.1 can be transformed into r.sub.2 by multiplying any number of entries of r.sub.1 by powers of the complex number .omega..

[0067] Interest primiarily lies in the .omega.-equivalence of matrices when .omega. is a generator for the signalling constellation .OMEGA.. Since BPSK and QPSK are of particular interest, the following special notation is introduced:

[0068] BPSK (.omega.=-1): r.sub.i{dot over (=)}r.sub.2 denotes that r.sub.1 and r.sub.2 are (-1)-equivalent.

[0069] QPSK (.omega.=i={square root}{square root over (-1)}): r.sub.1{umlaut over (=)}r.sub.2 denotes that r.sub.1 and r.sub.2 are i-equivalent.

[0070] Using this notion, binary rank criteria for space-time codes are derived that depend only on the unmodulated code words themselves. The binary rank criterion provides a complete characterization for BPSK-modulated codes (under the assumption of lack of knowledge regarding signs in the baseband differences). It provides a highly effective characterization for QPSK-modulated codes that, although not complete, provides a fertile new framework for space-time code design.

[0071] The BPSK and QPSK binary rank criteria simplify the problem of code design and the verification that full spatial diversity is achieved. They apply to both trellis and block codes and for arbitrary numbers of transmit antennas. In a sense, these results show that the problem of achieving full spatial diversity is relatively easy. Within the large class of space-time codes satisfying the binary rank criteria, code design is reduced to the problem of product distance or coding advantage optimization.

[0072] 1.1 BPSK-Modulated Codes

[0073] For BPSK modulation, the natural discrete alphabet is the field ={0,1} of integers modulo 2. Modulation is performed by mapping the symbol x.epsilon. to the constellation point s=f(x).epsilon.{-1,1} according to the rule s=(-1).sup.x. Note that it is possible for the modulation format to include an arbitrary phase offset e.sup.i.phi., since a uniform rotation of the constellation will not affect the rank of the matrices f(c)-f(e) nor the eigenvalues of the matrices A=(f(c)-f(e))(f(c)-f(e)).sup.H. Notationally, the circled operator .sym. is used to distinguish modulo 2 addition from real- or complex-valued (+,-) operations. It will sometimes be convenient to identify the binary digits 0,1.epsilon. with the complex numbers 0,1.epsilon.. This is done herein without special comment or notation.

[0074] Theorem 3 Let C be a linear L.times.n space-time code with n.gtoreq.L. Suppose that every non-zero binary code word c.epsilon.C has the property that every real matrix (-1)-equivalent to c is of full rank L. Then, for BPSK transmission, C satisfies the space-time rank criterion and achieves full spatial diversity L.

[0075] Proof: It is enough to note that [(-1).sup.c.sup..sub.1-(-1).sup.c.- sup..sub.2]/2{dot over (=)}c.sub.1.sym.c.sub.2.

[0076] It turns out that (-1)-equivalence has a simple binary interpretation. The following lemma is used.

[0077] Lemma 4 Let M be a matrix of integers. Then the matrix equation M{overscore (x)}=0 has non-trivial real solutions if and only if it has a non-trivial integral solution {overscore (x)}=[d.sub.1, d.sub.2, . . . , d.sub.L] in which the integers d.sub.1, d.sub.2, . . . , d.sub.L are jointly relatively prime--that is, gcd(d.sub.1, d.sub.2, . . . , d.sub.L)=1.

[0078] Proof: Applying Gaussian elimination to the matrix M yields a canonical form in which all entries are rational. Hence, the null space of M has a basis consisting of rational vectors. By multiplying and dividing by appropriate integer constants, any rational solution can be transformed into an integral solution of the desired form.

[0079] Theorem 5 The L.times.n, (n.gtoreq.L), binary matrix c=[{overscore (c)}.sub.1{overscore (c)}.sub.2 . . . {overscore (c)}.sub.L].sup.T has full rank L over the binary field if and only if every real matrix r=[{overscore (r)}.sub.1 {overscore (r)}.sub.2 . . . {overscore (r)}.sub.L].sup.T that is (-1)-equivalent to c has full rank L over the real field .

[0080] Proof: () Suppose that r is not of full rank over . Then there exist real .alpha..sub.1, .alpha..sub.2, . . . , .alpha..sub.L, not all zero, for which .alpha..sub.1{overscore (r)}.sub.1+.alpha..sub.2{overscor- e (r)}.sub.2+ . . . +.alpha..sub.L{overscore (r)}.sub.L=0. By the lemma, .alpha..sub.i are assumed to be integers and jointly relatively prime. Given the assumption on r and c, {overscore (r)}.sub.i={overscore (c)}.sub.i(mod 2). Therefore, reducing the integral equation modulo 2
produces a binary linear combination of the {overscore (c)}.sub.i that sums to zero. Since the .alpha..sub.i are not all divisible by 2, the binary linear combination is non-trivial. Hence, c is not of full rank over .

[0081] () Suppose that c is not of full rank over . Then there are rows {overscore (c)}.sub.i.sub..sub.1, {overscore (c)}.sub.i.sub..sub.2, . . . , {overscore (c)}.sub.i.sub..sub.v such that {overscore (c)}.sub.i.sub..sub.1.sym.{overscore (c)}.sub.i.sub..sub.2.sym. . . . .sym.{overscore (c)}.sub.i.sub..sub.v={overscore (0)}. Each column of c therefore contains an even number of ones among these v rows. Hence, the + and - signs in each column can be modified to produce a real-valued summation of these v rows that is equal to zero. This modification produces a real-valued matrix that is (-1)-equivalent to c but is not of full rank.

[0082] The binary criterion for the design and selection of linear space-time codes in accordance with the present invention now follows.

[0083] Theorem 6 (Binary Rank Criterion) Let C be a linear L.times.n space-time code with n.gtoreq.L. Suppose that every non-zero binary code word c.epsilon.C is a matrix of full rank over the binary field . Then, for BPSK transmission, the space-time code C achieves full spatial diversity L.

[0084] The binary rank criterion makes it possible to develop algebraic code designs for which full spatial diversity can be achieved without resorting to time consuming and detailed verification. Although the binary rank criterion and of the present invention associated theorems are stated for linear codes, it is clear from the proofs that they work in general, even if the code is nonlinear, when the results are applied to the modulo 2 differences between code words instead of the code words themselves.

[0085] 1.2 QPSK-Modulated Codes

[0086] For QPSK modulation, the natural discrete alphabet is the ring .sub.4={0, .+-.1, 2} of integers modulo 4. Modulation is performed by mapping the symbol x.epsilon..sub.4 to the constellation point s.epsilon.{.+-.1,.+-.i} according to the rule s=i.sup.x, where i={square root}{square root over (-1)}. Again, the absolute phase reference of the QPSK constellation can be chosen arbitrarily without affecting the diversity advantage or coding advantage of a .sub.4-valued space-time code. Notationally, subscripts are used to distinguish modulo 4
operations (.sym..sub.4,.crclbar..sub.4) from binary (.sym.) and real- or complex-valued (+,-) operations.

[0087] For the .sub.4-valued matrix c, the binary component matrices .alpha.(c) and .beta.(c) are defined to satisfy the expansion

c=.beta.(c)+2.alpha.(c).

[0088] Thus, .beta.(c) is the modulo 2 projection of c and .alpha.(c)=[c.crclbar..sub.4.beta.(c)]/2.

[0089] The following special matrices are now introduced which are useful in the analysis of QPSK-modulated space-time codes:

[0090] (1) Complex-valued .zeta.(c)=c+i.beta.(c); and

[0091] (2) Binary-valued indicant projections: (c) and .PSI.(c).

[0092] The indicant projections are defined based on a partitioning of c into two parts, according to whether the rows (or columns) are or are not multiples of two, and serve to indicate certain aspects of the binary structure of the .sub.4 matrix in which multiples of two are ignored.

[0093] A .sub.4-valued matrix c of dimension L.times.n is of type 1.sup.l2.sup.L-l.times.1.sup.m2.sup.n-m if it consists of exactly l rows and m columns that are not multiples of two. It is of standard type 1.sup.l2.sup.L-l.times.1.sup.m2.sup.n-m if it is of type 1.sup.l2.sup.L-l.times.1.sup.m2.sup.n-m and the first l rows and first m columns in particular are not multiples of two. When the column (row) structure of a matrix is not of particular interest, the matrix is of row type 1.sup.l.times.2.sup.L-l (column type 1.sup.m.times.2.sup.n-m) or, more specifically, standard row (column) type.

[0094] Let c be a .sub.4-valued matrix of type 1.sup.l2.sup.L-l.times.1.su- p.m2.sup.n-m. Then, after suitable row and column permutations if necessary, it has the following row and column structure: 7 c = [ c - 1 c - 2 c - l 2 c _ l + 1 ' 2 c _ l + 2 ' 2 c _ L ' ] = [ h _ 1 T h _ 2 T h _ m T 2 h _ m + 1 ' T 2
h _ m + 2 ' T 2 h _ n ' T ] .

[0095] Then the row-based indicant projection (-projection) is defined as 8 ( c ) = [ ( c - 1 ) ( c - 2 ) ( c - l ) ( c _ l + 1 ' ) ( c _ l + 2 ' ) ( c _ L ' ) ] .

[0096] and the column-based indicant projection (.PSI.-projection) is defined as

.PSI.(c)=[.beta.({overscore (h)}.sub.1.sup.T) .beta.({overscore (h)}.sub.2.sup.T) . . . .beta.({overscore (h)}.sub.m.sup.T) .beta.({overscore (h)}.sub.m+1'.sup.T)/({overscore (h)}.sub.m+2'.sup.T) . . . ({overscore (h)}.sub.n'.sup.T)].

[0097] Note that

[.PSI.(c)].sup.T=(c.sup.T). (7)

[0098] The first result shows that the baseband difference of two QPSK-modulated code words is directly related to the .sub.4-difference of the unmodulated code words.

[0099] Proposition 7 Let C be a .sub.4 space-time code. For x, y.epsilon.C, let i.sup.x-i.sup.y denote the baseband difference of the corresponding QPSK-modulated signals. Then,

i.sup.x-i.sup.y{umlaut over (=)}.zeta.(x.crclbar..sub.4y).

[0100] Furthermore, any complex matrix z=r+is that is (-1)-equivalent to i.sup.x-i.sup.y has the property that

r.ident.s.ident..beta.(x.crclbar..sub.4y).ident.x.sym.y(mod 2).

[0101] Proof: Any component of i.sup.x-i.sup.y can be written as

i.sup.x-i.sup.y=-i.sup.y.multidot.(1-i.sup..delta.),

[0102] where .delta.=x.crclbar..sub.4y. Since 9 1 - i = { 0 , = 0 1 - i = - i ( 1 + i ) , = 1
2 , = 2 1 + i = - i ( - 1 + i ) , = - 1 ,

[0103] the entry i.sup.x-i.sup.y can be turned into the complex number (x.crclbar..sub.4y)+i(x.sym.y) by multiplying by .+-.1 or .+-.i as necessary. Thus,

i.sup.x-i.sup.y{umlaut over (=)}(x.crclbar..sub.4y)+i(x.sym.y)=.zeta.(x.cr- clbar..sub.4y),

[0104] as claimed.

[0105] For (-1)-equivalence, multiplication by .+-.i is not allowed. Under this restriction, it is no longer possible to separate z into the terms x.crclbar..sub.4y and x.sym.y so cleanly; the discrepancies, however, amount to additions of multiples of 2. Hence, if z=r+is{dot over (=)}i.sup.x-i.sup.y, then r.ident.x.crclbar..sub.4y (mod 2) and s.ident.x.sym.y (mod 2).

[0106] Theorem 8 Let C a linear, L.times.n (n.gtoreq.L) space-time code over .sub.4. Suppose that every non-zero code word c.epsilon.C has the property that every complex matrix i-equivalent to .zeta.(c) is of full rank L. Then, for QPSK transmission, C satisfies the space-time rank criterion and achieves full spatial diversity L.

[0107] Proof: Since C is linear, the .sub.4-difference between any two code words is also a code word. The result then follows immediately from the previous proposition.

[0108] The indicant projections of the .sub.4-valued matrix c provide a significant amount of information regarding the singularity of .zeta.(c) and any of its i-equivalents. Thus, the indicants provide the basis for our binary rank criterion for QPSK-modulated space-time codes.

[0109] Theorem 9 Let c=[{overscore (c)}.sub.1{overscore (c)}.sub.2 . . . {overscore (c)}.sub.L].sup.T be an .sub.4-valued matrix of dimension L.times.n, (n.gtoreq.L). If the row-based indicant (c) or the column-based indicant .PSI.(c) has full rank L over , then every complex matrix z that is i-equivalent to .zeta.(c) has full rank L over the complex field .

[0110] Proof: Proof for the row-based indicant will now be provided. The proof for the column-based indicant is similar.

[0111] By rearranging the rows of c if necessary, any row that is a multiple of 2 can be assumed to appear as one of the last rows of the matrix. Thus, there is an l for which .vertline.({overscore (c)}.sub.i).noteq.0 whenever 1.ltoreq.i.ltoreq.l and .beta.({overscore (c)}.sub.i)=0 for l<i.ltoreq.L. The first l rows is called the 1-part of c; the last L-l rows is called the 2-part.

[0112] Suppose that 10 z = [ z - 1 z - 2 z - L ] = [ r - 1 + i s _ 1 r - 2 + i s _ 2 r - L + i s _ L ]

[0113] is singular and is i-equivalent to .zeta.(c). Then there exist complex numbers .alpha..sub.1=a.sub.1+ib.sub.1, .alpha..sub.2=a.sub.2+ib.- sub.2, . . . , .alpha..sub.L=a.sub.L+ib.sub.L, not all zero, for which 11
1 z _ 1 + 2 z _ 2 + + L z _ L = i = 1 L ( a i r _ i - b i s _ i ) + i i = 1 L ( b i r _ i + a i s _ i ) = 0. ( 8 )

[0114] Without loss of generality, the a.sub.i, b.sub.i are assumed to be integers having greatest common divisor equal to 1. Hence, there is a nonempty set of coefficients having real or imaginary part an odd integer. The coefficient as is said to be even or odd depending on whether two is or is not a common factor of a.sub.i and b.sub.i. It is said to be of homogeneous parity if a.sub.i and b.sub.i are of the same parity; otherwise, it is said to be of heterogeneous parity.

[0115] There are now several cases to consider based on the nature of the coefficients applied to the 1-part and 2-part of z.

[0116] Case (i): There is an odd coefficient of heterogeneous parity applied to the 1-part of z.

[0117] In this case, taking the projection of (8) modulo 2, 12 i = 1
l ( ( a i ) ( b i ) ) ( c _ i ) = 0 ,

[0118] since .beta.({overscore (r)}.sub.i)=.beta.({overscore (s)}.sub.i)=.beta.({overscore (c)}.sub.i) by the proposition. By assumption, at least one of the binary coefficients .beta.(a.sub.i).sym..beta.(b.sub.i) is nonzero. Hence, this is a non-trivial linear combination of the first l rows of (c), and so (c) is not of full rank over .

[0119] Case (ii): All of the nonzero coefficients applied to the 1-part of z are homogeneous and at least one is odd; all of the coefficients applied to the 2-part of z are homogeneous (odd or even).

[0120] In this case, equation (8) is multiplied by .alpha.*/2=(a-ib)/2, where .alpha.=a+ib is one of the coefficients applied to the 1-part of z having a and b both odd. Note that .alpha.*.alpha..sub.i is even if .alpha..sub.i is homogeneous (odd or even) and is odd homogeneous if .alpha..sub.i is heterogeneous. Hence, this produces a new linear combination, all coefficients of which still have integral real and imaginary parts. In this linear combination, one of the new coefficients is .vertline..alpha..vertline..sup.2/2=(a.sup.2+b.sup.2)/2, which is an odd integer. The argument of case (i) now applies.

[0121] Case (iii): All of the nonzero coefficients applied to the 1-part of z are homogeneous and at least one is odd; there is a heterogeneous coefficient applied to the 2-part of z.

[0122] In this case, normalization occurs as in case (ii), using one of the odd homogeneous coefficients from the 1-part of z, say .alpha.=a+ib. Thus, normalization produces the equation

{tilde over (.alpha.)}.sub.1{overscore (z)}.sub.1+ . . . +{tilde over (.alpha.)}.sub.l{overscore (z)}.sub.l+{tilde over (.alpha.)}.sub.l+1{over- score (z)}.sub.l+1+ . . . +{tilde over (.alpha.)}.sub.L{overscore (z)}.sub.L'=0, (9)

[0123] where {tilde over (.alpha.)}.sub.i=.alpha.*.alpha..sub.i/2 for i.ltoreq.l and {tilde over (.alpha.)}.sub.i=.alpha.*.alpha..sub.i for i>l.

[0124] Taking the projection modulo 2 of the real (or imaginary) part of equation (9) yields 13 0 = i = 1 l [ ( a
 
Copyright 2006-2008 Patent Looker, LLC