IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO.

5, MAY 2003

1097

Universal SpaceTime Coding

AbstractA universal framework is developed for constructing full-rate and full-diversity coherent spacetime codes for systems with arbitrary numbers of transmit and receive antennas. The proposed framework combines spacetime layering concepts with algebraic component codes optimized for single-inputsingle-output (SISO) channels. Each component code is assigned to a thread in the spacetime matrix, allowing it thus full access to the channel spatial diversity in the absence of the other threads. Diophantine approximation theory is then used in order to make the different threads transparent to each other. Within this framework, a special class of signals which uses algebraic number-theoretic constellations as component codes is thoroughly investigated. The lattice structure of the proposed number-theoretic codes along with their minimal delay allow for polynomial complexity maximum-likelihood (ML) decoding using algorithms from lattice theory. Combining the design framework with the Cayley transform allows to construct full diversity differential and noncoherent spacetime codes. The proposed framework subsumes many of the existing codes in the literature, extends naturally to time-selective and frequency-selective channels, and allows for more flexibility in the tradeoff between power efficiency, bandwidth efficiency, and receiver complexity. Simulation results that demonstrate the significant gains offered by the proposed codes are presented in certain representative scenarios. Index TermsBlock codes, Diophantine approximation, diversity methods, maximum-likelihood (ML) decoding, multipleinputmultiple-output (MIMO) systems, number theory.

I. INTRODUCTION AROKH et al. coined the term spacetime codes to describe the two-dimensional signals used in multiple transmit antennas systems [4]. In the coherent scenario, where the channel state information (CSI) is available a priori only at the receiver, Guey et al. and Tarokh et al. derived the design criteria for full diversity spacetime codes in quasi-static fading channels [4], [5]. Subsequent works resulted in new trellis and graphical spacetime codes that exhibit better coding advantages [6][16], new block spacetime codes [17][22], and extensions to more realistic frequency-selective and time-selective channels [23][30]. Despite this recent progress,

Manuscript received January 2, 2002; revised November 19, 2002. The material in this paper was presented in part at the IEEE International Symposium on Information Theory, Lausanne, Switzerland, June/July 2002, the IEEE Symposium on Advanced Wireless Communications, Victoria, B.C., Canada, September 2002, the 40th Allerton Conference, Urbana, IL, October 2002, and the IEEE Information Theory Workshop, Bangalore, India, October 2002. H. El Gamal is with the Department of Electrical Engineering, The Ohio State University, Columbus, OH 43210 USA (e-mail: [email protected]). M. O. Damen is with the Department of Electrical and Computer Engineering, University of Alberta, ECERF W2-073, Edmonton, AB, T6G 2V4, Canada (e-mail: [email protected]). Communicated by G. Caire, Associate Editor for Communications. Digital Object Identifier 10.1109/TIT.2003.810644

the design of full-diversity, high-rate, and low-complexity spacetime codes for quasi-static channels remains an open problem. For example, it is known that the complexity of maximum-likelihood (ML) decoding for full diversity spacetime trellis codes grows exponentially with the transmission rate. On the other hand, the polynomial complexity linear dispersion codes proposed in [31] fail to achieve full diversity for high transmission rates. Similarly, the layered spacetime architectures in [32] achieve high transmission rates with low complexity receivers at the expense of reduced diversity advantages. Finally, the orthogonal spacetime codes in [18] and the diagonal algebraic spacetime (DAST) codes in [19][21] achieve full diversity and allow for a low-complexity receiver, but entail a significant loss in the transmission rates, in general. Only few sporadic examples of spacetime codes are known in the literature to achieve full rate and full diversity with a , polynomial complexity receiver; for with -quadrature amplitude modulation (QAM) constellation with all QAM and pulse in [34], [33], and for amplitude modulation (PAM) constellations in [22]. In this paper, we develop a universal framework for constructing multiple-inputmultiple-output (MIMO) spacetime codes using algebraic component codes optimized for singleinputsingle-output (SISO) channels. The new framework is based on the threaded layering concept and will be referred to as threaded algebraic spacetime (TAST)1 coding in the sequel. Within this framework, we recognize a special class of codes which use algebraic number-theoretic constellations as component codes. The lattice structure of these number-theoretic codes along with their minimal delay allow for polynomial complexity ML decoding using the sphere decoder. The TAST framework is, to the best of the authors knowledge, the first systematic approach for constructing full diversity, full rate,2 and low-complexity spacetime codes for systems with arbitrary numbers of transmit and receive antennas. We further extend the new framework to construct differential and noncoherent spacetime codes. The new framework subsumes many of the existing codes as special cases and extends naturally to exploit the additional temporal or frequency diversity available in selective fading channels. The rest of this paper is organized as follows. The system model is outlined in Section II. In Section III, we present the new framework for constructing spacetime codes for coherent quasi-static fading channels where the CSI is available only at the receiver. Some interesting properties of TAST codes are further developed in Section IV. The proposed framework is then
1Algebraic in TAST refers to the use of algebraic component codes and not only the thoroughly investigated algebraically rotated constellations from [19]; see Theorem 4. 2We will define full rate spacetime codes later in the sequel.

0018-9448/03$17.00 2003 IEEE

1098

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

utilized in Section IV-C to construct spacetime and spacefrequency codes for time-selective and frequency-selective channels, respectively. In Section V, we extend the TAST coding framework to noncoherent channels where high-rates full-diversity differential and noncoherent spacetime codes are constructed. Simulation results that compare the proposed codes with previously known spacetime codes are presented in Section VI. Finally, Section VII presents our conclusions. II. SYSTEM MODEL AND NOTATIONS In this work, boldface lower case letters will denote vectors and boldface capital letters will denote matrices. The character denotes a column vector, of a length convened by the context, with elements all equal to zero. Furthermore, , , , and denote, respectively, the ring of rational integers, the field of rational numbers, the field of real numbers, and the field of com. plex numbers. The imaginary number is denoted by denotes the ring of complex integers and deAlso, notes the field of complex rational numbers. Finally, the algebraic number field generated by the primitive element is de(see Appendixes for more details). noted by information In the system under consideration, the , which belongs to a given symbol vector , is mapped by a channel encoder into an alphabet output vector from the output alphabet (i.e., : ). A spacetime formatter then maps to an spacetime each encoded symbol vector , where encoded symbols block code are transmitted simultaneously from all . There is a transmit antennas at time one-to-one correspondence between the information symbol and . When there is no confusion one denotes vector the spacetime block code by . The transmitted power is so that the normalized by the number of transmit antennas total transmitted power is independent of . The transmission symbols per channel use. At time , the rate of code is signal at the th receive antenna is given by (1) is the fading coefficient between transmit antenna where and receive antenna . The fading coefficients are assumed to be independent and identically distributed (i.i.d.) zero-mean complex Gaussian random variables with a common variance per real dimension. Unless otherwise stated, the fading coefficients are assumed to be fixed during one codeword (i.e., time periods) and change independently from one codeword to are assumed the next (i.e., quasi-static fading). The scalars to be independent samples of a zero-mean complex Gaussian random variables with a common variance determined by the resignal-to-noise ratio (SNR) considered. Let be the channel matrix, and ceived signal matrix, be the be the noise matrix; then one has (2) The design of spacetime codes depends largely on the availability of CSI at the transmitter and/or receiver. One of the in-

novations of the proposed framework is that it allows for constructing full-rate and full-diversity spacetime codes for systems with or without receiver CSI. Our main results will be first developed for the coherent scenario where the CSI is available only at the receiver (R-CSI). The extension to the no CSI (N-CSI) scenario is then discussed in Section V.3 III. COHERENT SPACETIME CODING: (R-CSI) In the coherent scenario, the following design criteria were shown to minimize the maximum pairwise error probability given that has been (PEP) of the ML detection of sent [5], [4]. taken The rank criterion: The minimum rank of is the transmit diversity over all distinct codeword pairs gain and should be maximized. The determinant criterion: Let minimum of , then the

taken over all distinct codeword pairs, is the coding gain and , are the nonzero must be maximized, where , , with denoting the conjugate transpose eigenvalues of of matrix . It is clear that the maximum diversity advantage in a MIMO transmit and receive antennas quasi-static channel with . Spacetime codes that achieve the maximum diversity is advantage will be referred to as full diversity codes. A. SpaceTime Threading The proposed framework relies on the threaded spacetime architecture [35]. For the sake of self-completeness, we review briefly some notations from [35]. Formally, a layer in an transmission resource array is identified by an indexing set where and the th symbol interval . This on antenna belongs to the layer if and only if and indexing set must satisfy the requirement that if , then either or (i.e., that is a function of ). The pair of spatial and temporal spans of a layer is defined , where .A as layer with full spatial and temporal spans will be referred to as a is designed so thread [35]. Therefore, the set that each thread is active during all of the available symbol transantennas mission intervals and, over time, uses each of the equally often. Thus, during each symbol transmission interval, the threads each transmits a symbol using a different antenna; and, in terms of antenna usage, all of the threads are equivalent. and the number of In general, the number of threads antennas transmitting simultaneously at any point of time is .
3The extension of the TAST codes to the adaptive scenario (i.e., the CSI is available partially at the transmitter and fully at the receiver, TR-CSI) is rather straightforward based on [47], and is omitted here. It is, however, worth noting that significant improvement in the performances of the TAST codes can be obtained by exploiting partial transmitter CSI as shown in [47].

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1099

component codes, are then stated toward the end of this section. The DAST component codes also allow for the low-complexity decoding algorithm discussed in the next section. A DAST code is obtained by rotating an -dimensional (i.e., ) information symbol vector by an rotation , which maximizes the associated minimum defined as [36] product distance (4)
Fig. 1. The threaded layering in the coherent scenario M = L = 4. The spatial and temporal dimensions correspond to the vertical and horizontal axes, respectively. The numbers refer to the indexes of the threads (e.g., one refers to the first thread).

Without loss of generality, we focus on the threaded layering set (with the convention that time indices span ) for (3)

that satisfies all the threaded approach requirements, where denotes the modoperation. An example of this threaded set is shown in Fig. 1 for a system with four transmit antennas and four threads. The main advantage of spacetime threading is that it induces a partitioning of the spacetime code into multiple indeis first partipendent codes. The information vector of length tioned into a set of disjoint component vectors , . Each one of the component vector is then encoded independently using a constituent encoder : , , so that and . The composite channel encoder will, optherefore, consist of constituent encoders erating on independent information streams, and there is a corinto a responding partitioning of the composite codeword of length . A component set of constituent codewords spacetime formatter then assigns the constituent codeto the thread and sets all off-thread elements to word zero. For simplicity of presentation, we first consider the case in which the constituent codes are all of the same rate and have and for all the same codeword length: . B. Threaded Algebraic SpaceTime (TAST) Coding The challenge now is to construct the SISO constituent codes (i.e., the s) such that the composite spacetime block code achieves full spatial diversity. In this subsection, we present a new class of codes, TAST codes, that achieve this goal, along with the full rate property, for arbitrary MIMO channels. Let us first consider the special case with one thread (i.e., ). From (3), one can easily see that with and , transmissions occur only on the principle diagonal of the spacetime matrix. We first observe that constructing component codes that achieve full diversity in this scenario is necessary but not sufficient for achieving full diversity in the general case with arbitrary numbers of threads . To further simplify our presentation, we first investigate in some details the scenario where the full diversity DAST block codes [19] are used as component codes. The general result, with arbitrary

belong to the multidimensional constellation conwhere (complex or sidered (QAM or PAM). The rotation matrix with real) is constructed on an algebraic number field an algebraic number of degree . In this paper, we consider the locally optimal rotations from [36][38] (see the Appendixes for more details). One can easily verify that the DAST codes achieve full diversity, and their coding gains are proportional to the minimum product distances associated with the rotations used [19]. With an arbitrary number of threads, the TAST codes are constructed by transmitting a scaled DAST code in each thread, i.e., (5) is an real or is transmitted over thread , where complex rotation that achieves full diversity as a DAST code, , , are chosen to ensure and the numbers full diversity and maximize the coding gain for the composite code. In general, one can use different rotation matrices in different threads. In this section, we will first consider the sym. We will refer to metric scenario transmit antennas, layers, the symmetric TAST code with symbols per channel use, and component DAST codes as . One can easily see that the rate of symmetric TAST codes using full-rate algebraic rotations [37], [38] is symbols ) and per channel use (i.e.,

Some examples of asymmetric TAST will be discussed later. are referred to as In the sequel, the numbers Diophantine numbers since they will be chosen in a way such that their simultaneous Diophantine approximation by algebraic numbers is bad. The main idea is to assign the constituent code in each thread to a different algebraic subspace, through the proper choice of the Diophantine number , such that the threads are transparent to each other. This construction is formalized in the following theorem. using the Theorem 1: The symmetric TAST code full diversity algebraic rotation matrix , a QAM constellation , and the Diophantine numbers from

achieves full diversity if is an algebraic integer such that are algebraically independent over the that contains the elements of the algebraic number field rotation matrix .

1100

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

It is worth noting that requiring to be alis only a sufficient condigebraically independent over tion to ensure full diversity. In some special cases, as shown in algebraically indepenSection III-D, having but with dent over an algebraic number field contained in ) can be sufficient to ensure full dia smaller degree (e.g., is chosen to maximize versity. In general, the rotation matrix the product distance [19]. The next theorem offers another alternative for choosing the Diophantine numbers such that the corresponding TAST code achieves full diversity. using the Theorem 2: The symmetric TAST code full diversity algebraic rotation matrix , a QAM constellation , and the Diophantine numbers from

; then the coding gain is lower-bounded by

of the TAST code

(7) where is the maximum product distance of the rotation the constellation used. over

achieves full diversity if and number (i.e., is transcendental).

is an algebraic

The previous two constructions are based on observing that the coding gain expresses the simultaneous Diophantine apby other algebraic proximation of the numbers numbers, depending on the constellation used. This observation implies that optimizing the coding gain is equivalent to choosing these Diophantine numbers to be badly approximated by other algebraic numbers (please refer to the Appendixes for more details). Choosing the Diophantine numbers to be algebraic has the advantage of controlling their simultaneous approximation by other algebraic numbers. This leads to the following lower bound on the coding gains of the TAST codes. Theorem 3: If is an algebraic integer such that the alge, and braic number field generated by , are algebraically independent over the alge, then the coding gain of the braic number field is lower-bounded by TAST code (6)

A brief comment on the choice of the symmetric configuration is now in order. After multiplication by the Diophantine number, one can see that the resulting code in each thread is ob. The intuition behind tained by a different scaled rotation the symmetry of the component codes is that, in the absence of other threads, one should pick the best component code and use it in all threads. The Diophantine numbers then create structured asymmetry to separate the threads while preserving the nice properties of the best component code(s) used in the threads. This two-step design process, therefore, reduces the problem of designing codes for MIMO channels to the well-studied code optimization problem for SISO fading channels. While Theorems 13 treat the special case when using the DAST component codes,4 the following result generalizes the proposed framework to arbitrary block or trellis component codes. We refer to a component code as algebraic if it takes values in a Galois extension of (see Appendix I). Theorem 4: Let the algebraic component encoders

(8) , , , with such that a Galois extension of . Further, assume that these component codes have nonzero minimum product distances, i.e., the component codes achieve full diversity in the absence of the other threads. Then, the TAST code consisting of the encoder

and the parser that assign the th codeword, in (3) for , has a rate of thread symbols (from the alphabet ) per channel use, with

, to the

where depends only on the maximum absolute value of the constellation used (PAM or QAM), and is the degree of the algebraic number field . Although the lower bound on the coding gain in (6) is generally loose, it suggests that choosing to be an algebraic integer with the smallest degree that satisfies the condition in Theorem 1 maximizes the lower bound in (6). In other words, choosing the Diophantine numbers to be algebraic is useful in maximizing the coding gain of the TAST codes. An interesting special case of Theorem 3, which shows the importance of the lower bound (6), is stated in the following corollary. , the optimal real or complex Corollary 1: Let rotation maximizing the minimum product distance, and

and achieves full diversity if the Diophantine numbers are chosen such that and are algebraically independent over . Such choice includes transcendental or algebraic as in Theorems 13. One should note that the previous result applies to rectangular ) and extends to arbitrary diversity configurations (i.e., (i.e., through the proper choice of the advantages Diophantine numbers the resulting spacetime code enjoys the
4This is done mainly for the sake of presentation simplicity since DAST codes have been thoroughly investigated in [19] in addition to the availability of the moderate complexity ML sphere decoder discussed in the following section.

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1101

same diversity advantage as that of the component code in the absence of other threads). The main idea in the proofs of Theorems 14, which are deferred to Appendix II, is that threading will make the component codes separable (each thread, in the absence of the others, exploits all the channel spatial diversity), and multiplying by Diophantine numbers will make the threads transparent to each others (each thread will lie in a different algebraic subspace). It is also worth noting that a suitable class of SISO codes satisfying Theorem 4 contains the codes optimized for block-fading channels [25]. This is because by exploiting all the degrees of freedom in the MIMO channel, a thread transforms the quasi-static MIMO fading channel into a single-input multiple-output block-fading channel. Note also that the TAST codes constructed by Theorem 4 is more general than the linear dispersion codes [31] because of the possibility of using error-correcting codes constructed over finite fields as SISO components. We conclude this section with the following observation. The TAST constructions proposed thus far are general for arbitrary numbers of transmit antennas , receive antennas , layers , component codes, and constellation sizes. The judicious choice of and the component codes is, however, critical to facilitate low-complexity ML decoding as described in the next section. as full-rate codes.We We refer to codes with recall that achieving full diversity and full rate does not contradict the limits set by [4, Corollary 3.3.1], which, using the Singleton bound, states that the maximum achievable rate of a full diversity spacetime code is of one symbol per channel use from the output constellation. This is because in [4], the authors assume that the spacetime codes do not change the information symbol alphabet . This is not the case in general when using algebraic rotations, or other algebraic component codes for that matter, where the information symbols alphabet is expanded to where , which is due to the increase of the degree of the algebraic number field (see Appendixes). There is a priori no upper bound on the maximum achievable rates (in symbols from per channel use) when using algebraically rotated constellations; however, there symbols per channel use. is no benefit of sending more than This is because, on one hand, the capacity of the channel in[1],5 and on the other hand, one creases only with symcannot increase the coding gain by sending more than bols per channel use, since one can always set the additional symbols to zero in the coding gain expression which is due to the linearity of the code. For more details on the maximum achievable rates, the reader is referred to [19]. C. The Decoding Strategy Ultimately, the utility of any coding scheme depends largely on the availability of a corresponding decoding algorithm with reasonable complexity. To this end, we resort back to TAST codes constructed from component DAST codes (that are linear is used over over the complex field ). When the code

a quasi-static fading channel, the received signal can be written as

(9) , is the channel matrix as seen where permuted to fit the by thread , which has the elements of ). Let structure of the th thread (e.g., which arranges the matrix in one column vector by stacking its columns one after the other, and let (10) where that (11) Rearranging (11) yields is the th row of matrix . Finally, let , then it follows, from the TAST code structure,

(12) , with denoting the Kronecker matrix where is the new equivalent multiplication, and is channel matrix of the TAST code and vector containing all the information symbols of the an threads. The received signal in (12) represents an uncoded system with equations and with a new channel matrix unknowns. This motivates ML decoding using the sphere decoder6 [34], [41]. The sphere decoder computes the ML metric over all constellation points enclosed in a sphere of a given radius . Finding the closest constellation point to the received signal is done by enumerating the lattice points, with constraint to the constellation boundaries, . When a point is found, the sphere rasuch that is reduced, and the enumeration is restarted until one dius reaches an empty sphere. If the initial sphere contains no constellation points, one may choose a larger radius depending and the noise level [34], on the equivalent channel matrix [41]. When the number of unknowns is less than or equal to the ), the complexity of number of equations (i.e., the sphere decoder is exponential in and polynomial in the [42]. Therefore, in this scenario, the proper lattice rank will allow for a decoder with a choice of the initial radius (roughly cubic) at medium-topolynomial complexity in , one can still obtain large SNRs [41]. In general, when the ML decoding performance with less complexity than the exhaustive search by applying the generalized sphere decoder
6Suboptimal detectors based on the turbo principle suitable for large array sizes will be considered in a separate paper.

5Even when N > M , the ergodic capacity grows with M , and hence, the same principle of sending min(M; N ) threads still allows for exploiting all the degrees of freedom in the channel.

1102

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

[41], [43]. The generalized sphere decoder can be implemented via the quadratic-residue (QR) decomposition of the equivalent channel matrix and has an additional exponential complexity [41]. This observation suggests that by rein threads, one stricting the number of threads to ensures that ML decoding can be performed using the polynomial complexity sphere decoder [40], [34], [41]. This choice for the number of threads also agrees with the fact that the informa. tion-theoretic capacity of the system grows with While our TAST coding framework is general for an arbitrary number of threads, we will limit the rest of the paper to this choice for the number of threads for simplicity. In this case, transmit antennas is equal the rate of the TAST code over symbols per channel use. Note that the to same restriction was imposed on the linear dispersion codes in [31] to allow for a low-complexity decoder. Codes that achieve this transmission rate will be referred to as full-rate codes in the sequel. In summary, through a judicious choice of the number of and the use of DAST component threads codes, TAST codes enjoy full diversity, full rate, and low complexity for arbitrary numbers of transmit and receive antennas and arbitrary constellation sizes. An interesting avenue for future research is to investigate low-complexity decoding algorithms for TAST codes that utilize more powerful component codes. D. Code Design Examples To further clarify our general framework, some representative examples of full-diversity and full-rate TAST codes are given here. transmit antennas and receive Example 1: For antenna, the new codes, using algebraic rotated constellations as SISO components, are reduced to the DAST codes in [19]. In this case, the TAST codes achieve a rate of one symbol per channel use. transmit and Example 2: For tennas, the TAST code is given by receive an-

For

, the coding gain of

is given by (16)

where the minimum is computed over all the differences of distinct codewords belonging to the constellation used [4]. Note belong to QAM constellations, , that when , with for the optimal real rotation (14), and for for the optimal complex rotation (15). It follows from guar(16) that choosing to be algebraic of degree over . In antees full diversity over all constellations carved from to be a this special case, ensuring full diversity requires only, and not over the number field containing free set over or as required by Thethe algebraic rotation orem 1. This is due to the absence of the cross terms between different layers in the expression of the coding gain (16); thus, one can choose the Diophantine number with a degree smaller than the degree required by Theorem 1. Using similar arguments , of degree as in [33, Ch. 4], it can be proved that over , gives the optimal coding gain when using the complex rotation above with symbols from a 4-QAM constellation. subsumes the code We also observe that the TAST code [22] as a special case. transmit antennas, one can identify Example 3: For two additional special cases. receive antennas 1) (17) where

with belonging to the constellation considered, real [38] or complex rotation [36]. It can and the optimal guarantees be proved that the Diophantine number full diversity when used with these algebraic rotations. receive antennas 2) (18) where

(13) where and and the optimal belong to the constellation considered. For real rotation one has [38] (14)

with belonging to the constellation used. By using the algebraic rotations from [36], [38], and setting ( is a free set over the algebraic number field considered), it can be shown that the TAST achieves full diversity over constellations carved code (for the rotation in [38]) and from (for the from rotation in [36]). Example 4: We give here an interesting example for and , which allows us to combine Hadamard spreading sequences7 with the TAST codes which can be useful
7This

where

is the Golden mean. For the optimal complex rotation [36], one has (15)

can be done only when M=L equals 2 or a multiple of 4 [44, Ch. 7].

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1103

in a peak-power-limited system [19]. The symmetric TAST code is given by

resulting TAST code has a rate of symbols per channel use. This special case is formalized in the following result. , Theorem 5: The Asymmetric TAST code in using the full diversity algebraic rotation matrix threads and a repetition code in threads achieves full diversity if the Diophantine numbers are chosen such that where , with algebraic; 1) 2) is an algebraic integer ensuring that are algebraically independent over , where is the algebraic number field that contains the elements of the rotation matrix . In the latter case, the coding gain obeys the lower bound given in (6). The proof is deferred to Appendix II. and , then the TAST code is For example, let given by

(19)

where with belonging to the constellation considered, the optimal real [38] or complex rotation [36], and the that achieves full diversity. If Diophantine number one spreads the two layers by the Hadamard sequences of length , such that the first spreaded layer occupies that equal layers and in the new TAST code, and the second spreaded layer occupies layers and , as follows:

(20) then the determinant of equals

(21) , and , with where belonging to the constellation used. The Diophantine number is chosen in the same way as for the TAST code (13), and symbols per channel use. We have the rate of this code is maximizes the found that the Diophantine number coding gain in this scenario. When sending layers from with a repetition code, there are, in general, less restrictions on the degree of the Diophantine number because many crossing ; thus, terms in the determinant of the code (47) belong to one can separate them by Diophantine numbers with smaller degrees than required by Theorems 1 and 5. E. Existing Codes as Special Cases of the Proposed Framework Here, the proposed framework is shown to subsume many existing spacetime schemes as special cases. 1) The Alamouti Scheme: Alamouti proposed a simple, yet brilliant, spacetime block code over two transmit antennas that achieves full diversity while allowing for a simple linear processing ML decoder [17]. The Alamouti scheme is given by (22) belong to QAM, PAM, or phase-shift keying where (PSK) constellations. With a small modification, the Alamouti scheme can be written as follows: (23) It is straightforward to verify that the modified representation has the same properties as the original Alamouti scheme (22). The modified representation, however, clearly falls within the scope of the threaded coding framework with , , and the . Observe that the constituent Diophantine number

which is equal to the determinant of original TAST code in (19). Similarly, one can verify that the spreaded code exhibits the same distance spectrum as the original code. Therefore, the spreaded TAST code has the same performance as the original one, but has a reduced peak power since it has no zeros in the transmission matrix. The spreading with Hadamard sequences requires a small modification of the decoding scheme in Section III-C. Consider (11), then the channel seen by the first with a unilayer, spreaded on and , is matrix depending on and the Hadamard tary transformation. Similarly, the channel seen by the second layer, with a unitary spreaded on and , is matrix depending on and the Hadamard transformation. Thus, the decoding can be implemented by including the Hadamard sequences in the new channel matrix of each layer (as is done for the DAST codes in [19]), and then applying the scheme in Section III-C. This operation requires an additional computational cost that is linear in , which is negligible when compared to the cubic complexity required by the ML decoder. The following is an example of an asymmetric TAST code that offers more flexibility on the tradeoff between data rate and complexity. Example 5 (Asymmetric TAST Codes): Instead of the rotation matrices, one can employ repetition codes, however, with the proper Diophantine numbers, in some selected number of threads. In this approach, one sends information , each repeated times on threads symbols . This approach allows for fractional symbol rates while ensuring full diversity and reducing the complexity of the sphere decoder since less information symbols are sent. The

1104

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

encoders , , can be considered as scaled DAST codes, with the scaled rotation

already ensured by the rotation, within each layer, and expansion of the code temporal dimension . The latter expansion plays the same role as the Diophantine numbers in separating the different layers as formalized in the following theorem. Theorem 6: The D-BLAST system using DAST block codes within the layers with the Diophantine numbers achieves full diversity in a quasi-static fading environment. Proof: See Appendix II. Compared to the proposed TAST codes, one can easily see that the disadvantage of the full diversity D-BLAST codes is the transmission rate reduction entailed by the silence periods. These silence periods also imply an increase in the peak-to-mean envelope power ratios. While the asymmetric TAST codes in Section III-D, Example 5, have the advantage of trading rate versus complexity; we cannot see an advantage for the D-BLAST codes over the TAST codes. They have . In advantages, however, over the DAST codes when the context of this paper, the D-BLAST codes serve to highlight the utility and power of the proposed framework. IV. TAST CODES PROPERTIES A. Symmetric TAST Precoding The symmetric TAST codes can be coupled with outer codes to further enhance the performance of MIMO systems. In this scenario, the symmetric TAST codes can be considered as a part of the equivalent channel seen by the outer code. It is therefore interesting to investigate the information-theoretic loss entailed by symmetric TAST pecoders. One observes that the primary example of an information lossless precoder is the identity matrix. The utility of the symmetric TAST precoders is, however, evident in the transformation of the MIMO Rayleighfading channel into SISO approximately Gaussian channels by means of transmit and receive diversity. Thus, one would expect optimal error-correcting codes for the Gaussian channel to exhibit a good performance when concatenated with symmetric TAST inner codes in MIMO Rayleigh-fading channels. The design of outer codes will be discussed, however, in more details in a separate paper. We now attempt to quantify the information-theoretic loss incurred by TAST precoders in the ergodic (i.e., fast-fading) scenario. Definition 1: The information loss of a TAST code is given by the difference between the ergodic capacity of the equivalent uncoded system in (12) and the ergodic capacity of the original channel [31], [45]. From (12), the ergodic capacity of symmetric TAST precoded system with transmit and receive antennas is given by [31]

applied on the vectors , with and denoting the real and imaginary parts, respectively. In this . case, the product distance of this rotation equals Hence, having of degree over is sufficient to ensure the full diversity; however, since in this special setup the product , distance (algebraic norm) is the usual Euclidean norm of degree over such that the determichoosing nant is a sum of two positive norms, guarantees full diversity. In matrix renders the summary, the special structure of the conditions stipulated on the Diophantine numbers in Theorem 1 unnecessarily restrictive. : In [22], the following code, denoted by , is 2) Code reported to have a better performance than the Alamouti code when the number of receive antennas is greater than two (24) and . The optimal value of was found with which gives a coding gain of in [22] to be over the 4-QAM constellation. As mentioned in Section III-D, in (13) subsumes the code as a special case the code . illustrating the layered structure of Linear Dispersion Block Code: In [31], a 3) The linear dispersion spacetime block code was reported to have a smaller error probability than the Alamouti scheme at small-toreceive antennas. medium SNRs and high data rates with This code was shown in [22] to be a special case of the code with in (24), and hence, does not achieve full diverlinear dispersion code is, therefore, a special case sity. The of our TAST codes. The other linear dispersion codes, however, do not necessarily exhibit the layered structure [31]. 4) The Bell Labs Layered SpaceTime (BLAST) Family: One can easily see that the BLAST architectures proposed by Foschini in [32] are special cases of the generalized space time layering framework in Section III-A. For example, the horizontal BLAST (H-BLAST) architecture corresponds to the following layering set: for (25)

More importantly, the new coding framework allows for constructing full diversity codes for the diagonal BLAST , (D-BLAST) architecture. For example, for , the new code for the D-BLAST is given by (26) and as in (13). Note that in the D-BLAST with framework, the codes are not delay optimal and achieve a transsymbols per channel use. It is interesting mission rate of to note that in this scenario there is no need for the Diophantine numbers to achieve full diversity (i.e., without loss of gener). Full diversity is ality, one can set

(27) is the TAST precoder, is the covariance mawhere trix of the information symbol vector , and is the average

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1105

SNR. The maximization of (27) is achieved when which corresponds to i.i.d. Gaussian inputs [31]. This leads to

Comparing this with the determinant of the uncoded system which is given by with the same throughput (32) is zero over a larger set of one observes that than (30). This is because the set of that makes in (30) also makes in such that and , (32). In addition, all , make in (32), but not for in (30). Using a similar argument, one can explain the good performance of threaded trellis codes reported in [35]. At this point, we emphasize the fact that the proper choice of the Diophantine numbers is critical to good performance at large SNRs. This asymptotically superior performance can be attributed to the full diversity ensured by the proper choice of the Diophantine numbers. The importance of the Diophantine numbers will be highlighted in the simulation results section. C. Time-Selective and Frequency-Selective Channels One of the advantages of the threaded layering approach is that it allows for exploitation of the additional temporal diversity in time-selective fading channels. More specifically, we consider the block-fading channel where each codeword is commatrix). In this posed of blocks (i.e., is an model, the fading coefficients are assumed to be fixed across one fading block, but change independently from one block to the next. It is straightforward to see that full diversity codes will levels of diversity in this scenario. In [24], it achieve was shown that the diversity advantage of the space-time code is given by (33) is the th block of . Full diversity where is codes should then be constructed such that . The information full rank for every ) is now partitioned into vector (i.e., vectors , . The scaled DAST code (34) is then transmitted over each thread in the threaded layering , set in (3). An example for the threaded layering set for , and is shown in Fig. 2. The main difference in this scenario, compared to the quasi-static case, is that the rotation is a matrix. The rate of this code is the matrix same as in the quasi-static scenario (i.e., symbols per channel use). The complexity of the decoder, however, is polynomial in instead of in the quasi-static case. The reason is the increased dimensionality of the rotation matrix. One can easily verify that this generalized TAST code achieves full diversity for arbitrary number of blocks . We can utilize the duality between spacetime coding in timeselective channels and spacefrequency coding in frequencyselective channels to generalize this construction for frequencyselective channels. In this scenario, one employs an orthogonal

(28) One distinguishes between two different scenarios : It can be seen from (12) that the sym1) metric TAST code, in the ergodic case, makes full use of only transmit antennas. The capacity of the precoded system is thus equal to that of an uncoded system with transmit and re). The information loss incurred ceive antennas (i.e., . This suggests is, therefore, equal to , where that the worst case scenario corresponds to . In this the information loss is given by scenario, the TAST code transforms the multiple-inputsingleoutput (MISO) channel into a SISO channel. The advantage of the TAST code in this scenario is, however, evident in the fact that the equivalent precoded channel is very close to a nonfaded additive white Gaussian noise (AWGN) channel [19], [37], [38]. This transformation reduces the code design problem to the extensively studied AWGN channel paradigm.8 2) : Using (12) one can easily show that, in the ergodic scenario, the symmetric TAST code makes full use of antennas, and hence, incurs no information loss. the B. The Importance of Diophantine Numbers Setting all the Diophantine numbers to one will result in TAST codes that do not, in general, achieve full diversity. which degenerate the The number of codeword pairs is, however, relatively small. This rank of is a function of the is because the rank of product distances of the different rotated layers (as detailed in Appendix II), which reduces many cases where the rank is less than for compared of to the uncoded system. For example, one still has full rank for the situation where layers of the are equal, since in this case the TAST codewords and codes reduce to the DAST codes which have full rank. One would, therefore, expect the TAST codes to exhibit good performances, even without Diophantine numbers, for small to medium SNRs. As a simple example, consider the scenario with the optimal rotation and let . The is then given by determinant of

(29) which is zero if and only if (30) and (31)

for a large number of transmit antennas.

1106

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

A. Differential TAST Coding For MIMO differential signaling schemes, the information must first be embedded in a unitary matrix in order to ensure that the transmitted signal obeys the average power constraint. This can be accomplished through the following Cayley transform: (35) is the identity matrix, is the where is the spacetime block code matrix at block time , and output of the Cayley transform at time [54]. The division by denotes the multiplication by the matrix the matrix . The code matrix transmitted at time , , is then obtained from the information matrix and , , as follows: the transmitted matrix at (36) . where is uniThe Cayley transform ensures that the matrix is Hermitian [54]. It was tary if and only if the matrix further shown in [54] that the differential spacetime code defined by (35) and (36) achieves full diversity if and only if achieves full diversity. The challenge, the spacetime code therefore, is to construct full diversity Hermitian spacetime block codes for arbitrary MIMO channels and rates. To achieve this goal, we now modify the TAST coding framework to ensure . the Hermitian property of the code matrix We first observe that the Hermitian constraint imposes a loss of half the degrees of freedom as pointed out in [54]. This motivates restricting ourselves to PAM modulations instead of QAM modulations, real rotation matrices instead of the complex ones, and real Diophantine numbers instead of the complex ones. Note that the real Diophantine numbers required to separate the different layers have different absolute values. These real component codes are then embedded in the following threaded layering assignment: for (37) operation belongs to where the output of the . This threaded layering assignment is shown in Fig. 3 for a system with four transmit antennas and four threads. with First, we construct a symmetric TAST code , based on the layering in (37) and the real scaled DAST component codes. Then, we multiply all the above-di to obtain a new code matrix agonal elements by . The codeword matrix is finally obtained as

Fig. 2.

The threaded layering in the time-selective scenario M = L = 4, = 2. The spatial and temporal dimensions correspond to the vertical and

horizontal axes, respectively. The numbers refer to the indexes of the threads (e.g., one refers to the first thread).

frequency-division multiplexing (OFDM) front end(s) such that the channel seen by the TAST code can be well approximated by the block-fading model [26]. The previous TAST construction can then be used as a full diversity spacefrequency code. V. DIFFERENTIAL AND NONCOHERENT TAST CODES: (N-CSI) Here, we suppose that neither the transmitter nor the receiver has prior knowledge of the channel state information (N-CSI). Recent information-theoretic calculations suggest that high capacities are still possible with multiple-antenna systems in the noncoherent scenario if the channel coherence time is not very small (e.g., [3]). Follow-up works have investigated the signal design criterion for noncoherent spacetime signals (e.g., [48]). Two approaches for spacetime signal design in this scenario have been investigated. In the first approach, noncoherent spacetime codes have been proposed [49][51]. These codes assume that the channel is fixed over only one matrix symbol duration and can exploit the spatial diversity without the need of any training symbols. The second approach extends differential phase-shift keying (DPSK) modulation to the spacetime paradigm, where two-dimensional unitary spacetime codes are constructed to exploit the spatial diversity [52], [53]. In this approach, the symbols are first drawn from a group of unitary matrices, then differentially encoded before transmission across the channel. The differential coding approach assumes that the channel remains fixed over two consecutive matrix symbol durations. The receiver exploits the fact that the information is embedded in the rotation between two consecutive matrix symbols to facilitate decoding without knowing the CSI. Earlier works on differential spacetime coding have focused on systems with relatively small numbers of transmit antennas and low data rates [52], [53]. More recently, a novel approach based on the Cayley transform have been proposed [54]. The so-called Cayley differential (CD) codes allow for high transmission rates with reasonable receiver complexity. The proposed CD codes, however, fail to achieve full spatial diversity [54]. In the following, we first utilize the TAST coding framework and the Cayley transform to construct full diversity differential spacetime codes for arbitrary quasi-static MIMO channels and arbitrary transmission rates. We then demonstrate briefly how one can use the proposed TAST in the noncoherent scenario as well.

(38) is the diagonal matrix conwhere . The multiplicataining the diagonal elements of tion of the above-diagonal elements by ensures that the addi-

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1107

the

, which equals with . Second, one constructs the code matrix

(40)

Fig. 3. The threaded layering in the differential coding scenario M = L = 4. The spatial and temporal dimensions correspond to the vertical and horizontal axes, respectively. The numbers refer to the indexes of the threads (e.g., one refers to the first thread).

defined above is Hermitian It is clear that the code matrix ; therefore, and has a full rank when the differential TAST code obtained by applying the Cayley as in (35) and (36) achieves full diversity. transform on Remark 1: Polynomial complexity decoding of the proposed differential TAST codes is possible through applying the sphere decoder on the linearized system presented in [54]. We observed experimentally that the use of the real Diophantine numbers can be harmful in certain scenarios when using this suboptimal decoder. This may be attributed to the increased variance of the colored additive noise with the Diophantine numbers in these cases. We, however, hasten to stress that the full-diversity Diophantine numbers were found to be always beneficial when using the exhaustive search ML decoder. This observation will be explored further in the numerical results section. Remark 2: Applying the Cayley transform on the DAST ) gives a constant codes [19] (TAST codes with modulus differential spacetime codes which achieve full diversity and have a polynomial near-ML decoding complexity when using the sphere decoder of the linearized system. We have observed that the differential DAST codes give comparable performances to the differential modulations of Hochwald and Sweldens in [53] with the same number of transmit antennas; nonetheless, the advantage of the differential DAST codes is their availability for any number of transmit antennas without the need to resort to computer searches. Remark 3: The extension of the differential scenario to arbitrary algebraic component encoders with nonzero product distances is easily done using Theorem 4. Here again, the advantage of using the DAST codes as component codes is motivated by the availability of a moderate complexity near ML decoding algorithm (the sphere decoder) at our disposal. B. Noncoherent TAST Coding In the noncoherent scenario, the channel, unknown to both the transmitter and receiver, is assumed to be fixed across a single coherence interval of length and changes independently from one coherence interval to the next (i.e., we relax the overlapping constraint used for differential signaling). Here, we will consider the delay-limited case where the codeword has to be transmitted over a single coherence interval. In [55], it was shown that the maximum achievable diversity advantage in this sce. The design criterion for nario is given by unitary spacetime signals was further characterized as (we to difrefer to the codeword corresponding to input as ferentiate it from the coherent case) [55].

tion operation in (38) does not result in any zero entry in the , and hence, guarantees full diverdifference matrix sity for the differential TAST code as argued in the following result (with the proof given in Appendix II). be a full diversity algebraic real Theorem 7: Let rotation matrix, and let , with , denote the symmetric TAST code obtained by the threading of layers bearing information from PAM constellations and using the optimal real rotation , the layering (37), and the real Diophan. Then, the TAST code tine numbers achieves full diversity when using PAM constellations if the Diophantine numbers are chosen such that

where is a real algebraic integer and are , with the algebraic algebraically independent over number field that contains the elements of the rotation matrix . Moreover, the spacetime code defined in (38) is Hermitian, satisfies the threaded layering constrains, and achieves full diversity. The resulting unitary differential code obtained as deby applying the Cayley transform on the code matrix fined in (35) and (36), will, therefore, achieve full diversity over all PAM constellations. In the following, we clarify our construction of full diversity differential TAST codes by an example. , the differential TAST code is Example 6: For constructed as follows. First, let

(39)

, , is the where is the information symbol vector from PAM constellations, real rotation in (14), and is the Golden optimal mean given in (14). The choice of to be the Golden mean is motivated by the fact that the latter number is the irrational number which is worst approximated by rational numbers [22], [58]; thus, this choice maximizes the determinant of

1108

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

The Noncoherent Rank Criterion: The minimum rank of taken over all distinct codeword pairs is the transmit diversity gain and should be maximized.9 It is now straightforward to construct full-diversity noncousing the TAST framework. The herent codes for codeword corresponding to an input vector is given by (41) is the identity matrix and is obtained where as in the Cayley differential TAST codes. The identity matrix acts like a matrix pilot symbol and the information is contained .10 For channels where , one can achieve the in by using the same approach, diversity advantage of active transmit antennas. Letting however, with only be the number of active antennas, one can easily see that the transmission rate in this case is given by PAM symbols per channel use. This result implies a fundamental tradeoff between transmission rate and diversity advantage, especially in the case of a small number , of receive antennas. For example, when one can easily see that the transmission rate can be maximized . by setting the number of active transmit antennas This choice is, in fact, optimal in the ergodic scenario as argued by Zheng and Tse [49] from an information-theoretic point of view. In the delay-limited scenario, however, increasing the rate implies a price in the diversity advantage which is given . by The unitary constraint imposed on the transmission matrix entails a loss of half the degrees of freedom (i.e., from QAM to PAM symbols). In the differential scenario, the unitary constraint was necessary to ensure a constant average power after differential encoding. In the noncoherent scenario, however, one can relax this constraint to increase the transmission rate. The main complication now is that the pairwise probability of error analysis for nonunitary signaling becomes intractable [55]. Interestingly, the noncoherent rank criterion can be still motivated in this case using the following identifiability argument. Definition 2 (Generalized Diversity Advantage): We say that a noncoherent spacetime code achieves full diversity if its probability of error, with ML decoding, in the absence of ,11 where is the additive noise is given by cardinality of the code. This definition means that for full diversity noncoherent spacetime codes, one is able to identify the correct transmitted as well as the channel matrix from the observed signal where matrix , in the absence of additive noise, unless the decoding decision is made randomly. Proposition 1: A noncoherent spacetime code achieves full diversity in the sense of Definition 2 if and only if the minimum taken over all distinct codeword pairs rank of is equal to .
9With 10One

The proof is given in Appendix II. One of the implications of Proposition 1 is that, in the case of unitary modulations, the usual definition of full diversity based on the error probability of the generalized likelihood ratio test (GLRT) receiver [49], [55] coincides with the identifiability definition above. In addition, by in (41) where this proposition leads to replacing is now drawn from QAM constellations, where one can easily verify that if achieves full diversity in the coherent scenario then will achieve full diversity in the noncoherent scenario (in the sense established in Proposition 1). This modification results in doubling the transmission rate, in bits per channel use, and significant performance gains as shown in the next section. In fact, the simulation results in the next section show that the performance of TAST noncoherent codes match the best noncoherent codes found through exhaustive computer search [55] while avoiding the exponential decoding complexity. Finally, we remark that the proposed codes belong to the class of training-based schemes. The good performance of this class of schemes was recently, and independently, observed by Brehler and Varanasi [56]. VI. SIMULATION RESULTS Simulation results are presented for transmit receive antennas, R-CSI, and N-SCI antennas and Rayleigh quasi-static as well as time-selective fading channels. Comparisons are done with the codes from [31], [54] and the codes in [33], [34], at the same rates and SNRs. Unless specified otherwise, the Diophantine numbers are chosen to be algebraic integers with the smallest degrees such that the TAST code achieves full diversity. The rotations used are the complex ones12 from [36], and ML decoding is obtained by the sphere decoder [34]. The performances are plotted versus the total average SNRs from all transmit antennas (in a way similar to [31], [54], for example). and Fig. 4 reports the performance of the TAST code over a the linear dispersion code with quasi-static fading channel. It also presents the performance of in order the TAST code with the Diophantine number to shed light on the importance of optimizing the Diophantine numbers to ensure full diversity. It is shown that both TAST codes are better than the linear dispersion code; however, optimizing the Diophantine number significantly improves the performance at large SNRs as it allows the TAST code to achieve full diversity. Over the time-selective channel (thus, by duality, over frequency-selective channel as discussed in Section IV-C) the TAST code achieves a larger diversity advantage without rate reduction, at the expense of increased complexity. In Fig. 5, in a time-sethe performance of the modified TAST code is presented where it is shown that lective channel with . the modified TAST code achieves a diversity of and Fig. 6 shows the performance of the TAST code the linear dispersion code (due to Hassibi and Hochwald) from , , and , at the rate of 8 bits per [31] with channel use (using a 16-QAM constellation). Note that the code

N receive antennas, the overall diversity advantage is Nr.

can easily obtain a linearized system and extend the application of the sphere decoder to this scenario, as is done for CD codes. 11Obviously, in case of fading coefficients represented by continuous-valued random variables, identifiability means zero-error probability in the absence of noise.

12For more details on the advantages/disadvantages of the complex and real rotations when used with DAST codes, the reader is referred to [46].

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1109

Fig. 4. The performances of the codes T N = 2 receive antennas.

( = 1 and  =

), and the linear dispersion code (M = 2;

= 2), over quasi-static fading channel with

in [31] sends encoded symbols over symbol petransmit antennas; whereas at the same rate, riods and sends eight symbols during symbol pethe code transmit antennas. While both codes exhibit riods and similar performance at SNR less than 25 dB, the TAST code has the advantage of a smaller decoding complexity than the linear dispersion code from [31], since the former needs to jointly decode eight information symbols (with a complexity polynomial in ) and the latter needs to jointly decode 12 information symbols (with a complexity polynomial in ). It is also shown that at large SNR ( 25 dB), the TAST code has a better performance, since full diversity is ensured by construction, whereas this is not the case for the linear dispersion code [31]. The slopes of the curves predict that the gain of the TAST code over the linear dispersion code will increase for higher SNRs. In addition, the TAST code has a smaller baseband peak-to-average power ratio (PAPR), defined as the ratio of the maximum over the mean value of the output constellations squared norms over all transmit antennas. For example, when using the complex roin (20), which has tation in [36], the spreaded TAST code the same performance and decoding complexity as the TAST (19), has a PAPR of code

prohibitive because one needs to check the power envelope of matrices when using the 16-QAM constellation; however, with a limited computer search, a lower bound of (10.185 dB) was found. and Fig. 7 presents the performance of the TAST code , with , the code from [33], [34], denoted by and . In this case, both codes have the same decoding complexity since they both send 16 rotated information symtransmit antennas and symbol periods, bols over and have a rate of 8 bits per channel use (using a 4-QAM constellation). Also, both codes achieve full diversity by construction; however, one observes a coding gain of about 0.8 dB for , which can be attributed to the optimized the TAST code coding gain. The performance of the uncoded BLAST system, decoded by the sphere decoder [34], is also reported. Here again, ; the the TAST code enjoys a smaller PAPR than the code PAPR is of

(5.164 dB) for the TAST code, and of

(7.717 dB) when using 16-QAM constellation. Computing the PAPR of the linear dispersion code is computationally

(11.133 dB) for the code. Fig. 8 shows the performances of the uncoded V-BLAST with , the TAST code, (18) with the optimal

1110

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

Fig. 5. The performances of the codes T

( =

) over quasi-static (B = 1) and time-selective fading channel (B = 2) with N = 2 receive antennas.

Fig. 6. The performances of the codes T

and the linear dispersion code (M = 4;

= 6).

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1111

Fig. 7. The performances of the codes T

and the code

2.

Fig. 8. The performances of the TAST code T

and the HeathPaulraj code for

M = N = 3.

1112

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

Fig. 9. The performances of the differential TAST code T

and the differential code by Hassibi and Hochwald.

real rotation [38] and ,13 and the corresponding code from [57] when using a 4-QAM constellation, at the same rate and number of transmit and receive antennas.14 Here again, one notes the gain offered by the TAST code. In addition, and as in the preceding figures, the TAST code has a smaller peak power. Fig. 9 shows the performance of the differential TAST code with the exhaustive search ML decoder, the differential TAST code with the suboptimal linearized decoder, and that of the Hassibi and Hochwald code from [54]. When the exhaustive ML decoder is used, the Diophantine numbers are optimized to ensure full diversity, whereas, when the linearized decoder is used, the best performance is obtained when all the Diophantine numbers are equal to in this scenario. In all cases, we and 6 bits per channel use. One can assume easily observe the gain offered by the new code, with the ML or linearized decoder, compared with Hassibi and Hochwald code (for example, a gain of 5 and 4 dB is evident at a block error rate with the ML and linearized decoders, respectively). In of this setting, the complexity of the ML decoder is still reasonable ). due to the limited number of points in the search space (i.e., For larger array sizes and higher rates, the ML decoder complexity is expected to be prohibitive. The gain obtained by the optimized Diophantine numbers is apparent in the steeper slope facilitated by the higher diversity advantage. Fig. 10 shows the performances of the noncoherent TAST and the McCloud et al. noncoherent code code
13Which is of degree 3 over and is found to give a local optima of the coding gain for a 4-QAM constellation. 14A typographical error in the SNR scaling in the corresponding figure in [57] was corrected after consultation with the first author.

[55]15 at a rate of 2 bits per channel use. Both schemes have comparable performances (according to the authors knowledge, the code in [55] currently represents the state of the art). In addition, the TAST code has smaller coding and decoding complexity. The fact that the ML decoding complexity of our scheme is polynomial (that of [55] is exponential in the rate and number of antennas) further illustrates the advantage of our framework in rivaling the performance of the best noncoherent codes while avoiding the prohibitive exponential complexity. The performance of unitary TAST code, with in (41) as the Cayley transform of the corresponding signals, at the same rate (using 4-PAM constellations instead of 4-QAM) is also shown in Fig. 10, where one can observe the significant gain obtained by relaxing the unitary constraint. Finally, it is worth noting that the special cases of the TAST , outperform orthogonal design when codes, when as shown in [19], and when , the TAST code outperforms the Alamouti code as shown in [22]. VII. CONCLUSION AND FUTURE WORK In this paper, we developed a universal framework for constructing full-rate and full-diversity spacetime codes for systems with arbitrary numbers of transmit and receive antennas. Furthermore, the proposed framework extends naturally to time-selective and frequency-selective channels, and is
15We present here symbol error rate performances to be compatible with [54]; in addition, we note that compared to [55, Fig. 3] the performance of the McCloud et al. code is shifted 6 dB to the left due to power normalization as communicated by the authors [56].

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1113

Fig. 10.

The performances of the noncoherent spacetime codes for

M = N = 2.
Definition 3: Let , then is called an algebraic number such that . We if there exists a polynomial call an algebraic integer if, in addition, one can choose to be monic (i.e., with leading coefficient equal to ). For algebraic, there exists a unique irreducible polynomial with leading coefficient which has as a root. We call the minimal polynomial of . The degree of , , is defined to . If is complex, one can also define be the degree of (i.e., with complex rational its minimal polynomial over coefficients). Example 7: The cyclotomic numbers, which are the th , are algebraic integers [59]. The roots of unity over equals , the Euler -function [59], degree of and prime which represents the number of integers with . is Definition 4: The height of a polynomial defined as the maximum modulus of its coefficients. Suppose is the minimal polynomial of the algebraic that by the least common multiple number . If we multiply of the denominators of its coefficients, we obtain a primitive such that (a polynomial polynomial is called primitive if there is no integer greater than in which divides all of its coefficients). Then, the height of is . For algebraic, there exists an defined as the height of such that is algebraic integer. integer is a field conDefinition 5: An algebraic number field taining which, considered as a -vector space, is of a finite di-

suitable for adaptive,16 coherent, differentially coherent, and noncoherent scenarios. Within this framework, we identified a special class of signals based on number-theoretic component codes. The judicious choice of the number of threads and the lattice structure of the proposed number-theoretic TAST codes were shown to allow for polynomial complexity ML decoding using the sphere decoder. Simulation results that demonstrate the significant gains offered by the new codes were also presented. The coding framework proposed in this paper poses many interesting venues for future work. One can see the proposed TAST coding framework as an attempt for using codes optimized for SISO channels to construct full rate and full diversity spacetime codes for MIMO fading channels. One would expect that more sophisticated, and hopefully more efficient, spacetime codes can be developed in the future by leveraging the large body of work available on error-correcting codes for SISO channels. We hope that our first step will simulate further research in this direction. APPENDIX I PRELIMINARIES In this appendix, we summarize some key results and definitions from number theory which are relevant to our work. The interested reader is referred to [36] and [58][60].

16As

described in [47].

1114

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

mension; is called an extension of . The dimension of over is called the degree of over and is denoted by . It can be proved that given an algebraic number field of degree over , then there exists an algebraic number of degree such that . Such a number is generates called a primitive element. The set and is called a basis of . Each element has a unique representation with The roots of , gates of . The size of , are called the conjuis defined as

Recall that a norm over a vector space (defined over or over ), in the usual Euclidean sense, should have the following three properties [61]. 1) It is multiplicative, i.e., . , , and 2) For 3) The triangle inequality: . . , for or

The set of all algebraic integers in , , is a ring, and a free is defined over , module [59] of rank over if if is defined over . If is an algebraic or over is called an integral basis if integer, then , or . This property is important in our work since the PAM and QAM con, respectively. Finally, stellations are carved from and from is called free over if a set of number , the for any set of algebraic numbers implies that . equality is a basis of , defined as an Note that if ), then it is free over (reextension of (respectively, ). spectively, The following proposition is important to understanding the underlying ideas of the algebraic rotations in [36][38], and is essential to the development in the next section. Proposition 2: There are exactly embeddings of in

The algebraic norm defined in Proposition 2 is multiplica; however, it tive, and satisfies the relation can take on negative values. Nonetheless, the absolute value of defines an Euclidean norm and satisan algebraic norm fies the three properties above. The totally real (or totally complex) algebraic rotations constructed over Galois algebraic number fields in [36][38] guarantee that the associated product distance is the algebraic norm ; thus, it is nonzero as shown in the above proposition. with For example, the rotation in (15) is constructed over , with the embeddings defined by the conjugates of : . The mapping between and as(QAM sociates with each two-dimensional vector from , where the constellations) an algebraic integer associated algebraic norm (product distance) of (or ) equals, , , up to a normalization factor of , because the imaginary number is which is nonzero if , i.e., there is no such not a quadratic residue in that . is not algebraic it is called transcendental. , , and are transcendental; is algebraic [58, Ch. 2]. Definition 6: If Example 8: , but

Definition 7 (The Simultaneous Diophantine Approxima, , and an tion): Given rational numbers , decide if there exist integers and integer such that and for an integer . Since is everywhere dense in , it follows that the approximation in Definition 7 can be made as close as necessary. Thus, it makes sense to consider its relative closeness, and especially to answer the question: how small can we make the integer . A closely related problem is the following [60]. Definition 8 (The Small Linear Form Problem): Given ra, , and an integer , tional numbers , not all , such that for find integers and . The approximation of complex numbers by algebraic numbers can also be considered, which is our case of interest in the , consider with proposed framework. Given algebraic. Since the field of algebraic numbers is everywhere dense in [58], it follows that can be approximated arbitrarily closely by algebraic. The approximation theory pro, which depends on the vides the order of this closeness . The following theorem gives a algebraic number field

which are linear, and their images are called the conare jugate fields of , where the elements of algebraic numbers. If is (globally) invariant by the embed, ) it is called normal or dings (i.e., Galois extension of [59]. Note that an algebraic number field can be included in a Galois extension of [59]. These embedby sending dings define a mapping : to the -tuple , which is an additive homomorphism with trivial kernel. Hence, this mapping preserves the In addition, we have the following. additive structure in , the quantity For

is an algebraic norm over , If , and , Hence, for

. if if . is defined over is defined over .

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1115

lower bound on the simultaneous approximation of algebraic numbers by other algebraic numbers [58, p. 34]. are algebraic numTheorem 8: Suppose that bers, and is the minimal degree of an algebraic number field that contains these numbers. Then, for any polynomial with degree and , either or else height (42) with constant depending only on , (43) with as an integer such as , and is algebraic integer for

In other words, each additional layer adds a new term to the determinant, which is independent and separable from the other layers. The next lemma illustrates the use of the Diophantine numbers to separate the layers by putting each one in a different algebraic subspace, such that all the layers are transparent to each others. Lemma 2: Let be the Diophantine numbers used in the TAST code with and denoting the information symbols assigned to the th layer and then multiplied by the which is rotated by matrix ; then the determinant of matrix Diophantine number can be written as (47) where

with as the size of the algebraic number (see Definitions 35).

The following theorem concerning the behavior of transcendental numbers is due to Lindemann [58, pp. 5171]. are distinct algebraic numbers, Theorem 9: If are algebraic numbers not all equal to zero, and if then (44) Lindemann also showed that if is transcendental. then is an algebraic number , and , depends on the positions of layer in the matrix , and is called the signature of the layer . Proof: First, the determinant of the TAST code can be written as [62, p. 157] (48) , denote the entries of is a permutation of the numbers , is called the signature of and depends on the and number of exchanges in . Note that where , is the th components of the th thread as shown in (3) and , , for . Section III-B, and permutations, where each term The sum is taken over all entries , with each row and column repreis a product of sented once; i.e., each term corresponds to a path that goes down and uses each column once [62]. through the matrix Second, each thread of the TAST code occupies the column (respectively, row ) only once, by construction (3). We first need to prove that the exponents of in all the cross terms in (3) are integers. To this end, it suffices since assuming will to consider the case when
17For some special cases (e.g., T ), the crossing terms X ; . . . ; X may exhibit nice structures. However, these terms are, in general, complicated and it is not straightforward to find a structure for them. Looking more closely into the cross terms may be helpful in further optimizing the coding gain, which is the topic of current research.

the terms

contains the crossing terms17 of

APPENDIX II PROOFS In this appendix, we give the proofs of Theorems 17. First, the following lemmas establish the underlying ideas necessary to show that choosing the Diophantine numbers badly approximated by algebraic integers results in full diversity TAST codes. , with representing the information symbols . Let (or their differences) of the th layer Lemma 1: Let (45) then one has (46) , and where metric TAST. Proof: It is easily seen that in case of sym-

where is the scaled DAST code assigned to the th layer is the spatial formatter of the th layer as illustrated and in the general threading approach in Section III. Hence, setting implies the relation in (46).

1116

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

only zero-out some cross terms. In this scenario, the threaded assignment will result in

where spans the columns occupied by the th thread given in (3). In addition, when the permutation spans the th layer time indexes, one has

(49) denotes the exponent of in the term (for where example, one can easily verify this property in Fig. 1 after subtracting one from each entry). The exponent of in the term in (48) will be denoted by for simplicity. The threaded assignment further ensures that (50) , and denotes the where the convention that the output belongs to we have the following: operation with . Now Finally, denoting the signature of by when spans under the th thread, and using the closeness of the field addition and multiplication give the required result in (47). Lemma 3: When using algebraic rotations constructed on the with the symmetric TAST codes, the Galois number field in (47) are algebraic integers crossing terms . in , for ; Proof: First, recall that thus, when using the algebraic rotation constructed over from [36][38], , with the ring of algebraic . This is due to integers in the Galois algebraic number field is a Galois extension of , implying that the fact that which is an algebraic integer in the conjugate field , is also an algebraic integer of since , . Hence, and since the ring is closed under multiplications and are additions, the crossing terms coefficients . algebraic integers in Note that the coding gain of the TAST code equals

(51) . where one uses the relation The result in (51) proves that the exponents of all the cross terms s) are integers. (i.e., One can further observe that the smallest value of equals since the exponents of of the different threads are all positive. This value is attained when , which is satisfied only when all the are elements in the first thread; hence,

with the minimum taken over all differences of distinct codeword pairs. An important result of the above lemmas is that, in general, one cannot prevent the shrinking of the coding gain when the size of the constituent constellation increases. This is because the coding gain expresses the approximation of the Dioby other algebraic numphantine numbers bers, where the latter are everywhere dense in ; thus, the larger the constellation used, the closer is this approximation. In some special setups, where the determinant in (47) is a sum of positive norms, such as the Alamouti scheme (23), the coding gain is independent of the size of the constellation used. In the following, we present the proofs of our main results. Proof of Theorem 1: We suppose that is a free set over . Consider the determinant in (47) taken , with in the constellation at used. We prove that this determinant is nonzero by induction . over : In this case, , which is 1) maximizes the minimum product nonzero since the rotation distance. In order to have more insight on the proof, we prove . To this end, it suffices to compute that (52) , and with assumed to be free18 over
(i).
18Observe

spans the columns occupied by the first thread . The largest value of equals , and is only attained when all the are elements . in the th thread where In this case, one has

where

. On the one hand, is ; on the other hand, the product

that in this case, it is sufficient to assume that f1; g is free over

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1117

distances implies that posing that contradicts the hypothesis that 2) Assume that for all and suppose that

. Hence, sup, which .

To prove Corollary 1, it is sufficient to set in (52), ( over ) is sufficient where choosing of degree over to ensure full diversity. In this case, is the maximum product distance of the rotation used. Proof of Theorem 4: The theme in the proof is similar to that of Theorems 13, and thus, only a sketch is given here. .19 Therefore, one has an First, we further assume code matrix with algebraic SISO codes components in threads, separated by Diophantine numbers. Then, one simply submatrix of for , and takes a square proves that it is full rank. This is possible because one keeps the threaded structure (no spatial or temporal interference within a thread in a square matrix), required for Theorems 13 and submatrix which is easily Lemmas 13, by taking any seen from (3). Then, using the fact that partial product distances of the SISO encoders are nonzero means that one can always choose the square submatrix to have at least one thread whose elements are all nonzero. One can now use the algebraic nature of the component codes to complete the proof as done in Theorems 13. Proof of Theorem 5: First, note that the determinant of the asymmetric TAST code has the same form as in (47) where the are simply a repetition of elements of layers information symbols belonging to . Second, the proof follows by induction as in the proofs of Theorems 1 and 2, where one utilizes the fact that when a component of the equals zero, all the layers disappear from layers the determinant expression due to Lemma 1. Proof of Theorem 6: We prove Theorem 6 by induction over the number of layers. The proposed D-BLAST codes, with (26), send DAST codes over the principal spacetime matrix. We prove diagonals of an , with , that the rank of equals . : The code reduces to the DAST code [19], which 1) achieves the maximum diversity; thus, it has full rank. for 2) Suppose that the D-BLAST code has rank layers, and compute the rank of the TAST code when adding a new layer (DAST code) over the th principal diagonal of the matrix. Let , denote the th row of the code, and suppose that it has a rank ; it fol, for lows that there is a nontrivial combination not all zero. Let be the first nonzero . Since the new layer is added coefficient for on the th principal diagonal, supposing that the rank of the gives , which implies that due code is to the use of the algebraic rotation . Hence, all the coefficients of the th layer disappear from the linear combination , with among the rows of the code, resulting in the rows of the code with layers, which contradicts the induction hypothesis. Proof of Theorem 7: Similarly to Lemma 2, one proves that the determinant of the TAST code with the layering
T
19For
T < M

for a certain . Using (47), and the hypothesis that is a free set over , one concludes that

Since , and maximizes the minimum product dis. Substituting in (47), all the terms tance, it follows that disappear as shown by Lemma 1, containing components of and one has with ; which contradicts the infor all duction hypothesis. Hence, , and the TAST code achieves full diversity over all con. stellations carved from Proof of Theorem 2: Let be the Diophantine numbers used by . Assuming that with algebraic ( transcendental), it follows that are all distinct. Hence, using Lindemann are algebraically inTheorem 9, it follows that . The dependent, and consequently, forms a free set over rest of the proof follows by induction as in the proof of Theorem 1. Proof of Theorem 3: Let multinomial with coefficients from , such that in (47). First, by Lemma 3, one proves that the crossing terms in (47) are algebraic in, therefore, they are algebraic tegers in the number field that contains integers in the algebraic number field and . It follows that , over of considered as an extension of the basis of degree . Similarly, , since is an algebraic in, and its height teger. In addition, the degree of is . Second, by Theorem 2, , for ; thus, (43) in Theone has orem 8 gives (53) with the minimum of and if one defines ered, it follows that . Since the coding gain is over the constellation used, over the constellation consid(54) be an

(u) , where full transmit diversity in this case equals min (M;

, similar conclusion can be drawn by working on matrix T ).

1118

IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 5, MAY 2003

in (37) has the same form as in (47) because each thread in (37) occupies one column and one row at a time. This such that implies that choosing the Diophantine number are algebraically independent over the implies that the TAST number field containing the rotation code achieves full diversity over all constellations carved from , and consequently, over all PAM constellations. On the has a rank other hand, it is easily seen that if when , then in (38), obtained by multiplying the above diagonal elements by , has also a rank . It follows that the code matrix defined in (38) has a rank for all , and it is Hermitian by construction. Therefore, the differential TAST code obtained by applying the in (35) and (36) achieves full diversity Cayley transform on over all PAM constellations as shown in [54]. Proof of Proposition 1: Let denote the noncoherent spacetime code matrix corresponding to the codeword . One further assumes that the receiver does not know the channel realization . Under these assumptions, identifiability in the sense of Definition 2 means that the receiver should be able to identify the transmitted codeword and the channel matrix from the noiseless received signal, i.e., for arbitrary , , and . Therefore, identifiability for ,20 is equivalent to which is, in turn, equivalent to being full rank for all . ACKNOWLEDGMENT The authors are grateful to the anonymous reviewers for their helpful comments. REFERENCES
[1] I. E. Teletar, Capacity of multi-antenna Gaussian channels, Tech. Rep., AT&T-Bell Labs., June 1995. [2] G. J. Foschini and M. Gans, On the limits of wireless communication in a fading environment when using multiple antennas, Wireless Personal Commun., vol. 6, pp. 311335, Mar. 1998. [3] T. Marzetta and B. Hochwald, Capacity of a mobile multiple antenna communication link in Rayleigh flat fading, IEEE Trans. Inform. Theory, vol. 45, pp. 139158, Jan. 1999. [4] V. Tarokh, N. Seshadri, and A. R. Calderbank, Space-time codes for high data rate wireless communications: Performance criterion and code construction, IEEE Trans. Inform. Theory, vol. 44, pp. 744765, Mar. 1998. [5] J.-C. Guey, M. P. Fitz, M. R. Bell, and W.-Y. Kuo, Signal design for transmitter diversity wireless communication systems over Rayleigh fading channels, in Proc. Vehicular Technology Conf., Atlanta, GA, Apr. 1996. [6] A. R. Hammons, Jr. and H. El Gamal, On the theory of space-time codes for PSK modulation, IEEE Trans. Inform. Theory, vol. 46, pp. 524542, Mar. 2000. [7] S. Baro, G. Bauch, and A. Hansman, Improved codes for space-time trellis codes modulation, IEEE Commun. Lett., vol. 4, pp. 2022, Jan. 2000. [8] H. El Gamal and A. R. Hammons, Jr., On the design and performance of algebraic space-time codes for PSK and QPS modulation, IEEE Trans. Commun., vol. 50, pp. 907913, June 2002. [9] Q. Yan and R. Blum, Optimum space-time convolutional codes, in Proc. WCNC, Chicago, IL, Sept. 2000. [10] Y. Liu, M. P. Fitz, and O. Takeshita, Full rate space-time turbo codes, IEEE J. Select. Areas Commun., vol. 19, pp. 969980, May 2001.
20

H is the channel matrix realization and H 2

[11] A. Stefanov and T. Duman, Turbo coded modulation for systems with transmit and receive antenna diversity over block fading channels: System model, decoding approaches, and practical considerations, IEEE J. Select. Areas Commun., vol. 19, pp. 958958, May 2001. [12] K. R. Narayanan, Turbo decoding of concatenated space-time codes, in Proc. 37th Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, Sept. 1999. [13] J. Grimm, M. P. Fitz, and J. V. Krogmeier, Further results in space-time coding for Rayleigh fading, in Proc. 36th Annu. Allerton Conf. Communication, Control, and Computing, Monticello, IL, Sept. 1998, pp. 391400. [14] M. Ionescu, K. K. Mukkavilli, Z. Yan, and J. Lilleberg, Improved 8and 16-state space-time codes for 4-PSK with two transmit antennas, IEEE Commun. Lett., vol. 5, pp. 301303, July 2001, submitted for publication. [15] A. Guidi, A. Grant, and S. Pietrobon, Full diversity PSK space-time codes, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 150. [16] J. Grimm, Transmit diversity code design for achieving full diversity on Rayleigh fading channels, Ph.D. dissertation, Purdue Univ., West Lafayette, IN, Dec. 1998. [17] S. M. Alamouti, A simple transmit diversity technique for wireless communications, IEEE J. Select. Areas Commun., vol. 16, pp. 14511458, Oct. 1998. [18] V. Tarokh, H. Jafarkhani, and A. R. Calderbank, Space-time block codes from orthogonal designs, IEEE Trans. Inform. Theory, vol. 45, pp. 14561466, July 1999. [19] M. O. Damen, K. Abed-Meraim, and J.-C. Belfiore, Diagonal algebraic spacetime block codes, IEEE Trans. Inform. Theory, vol. 48, pp. 628636, Mar. 2002. [20] M. O. Damen, K. Abed-Meraim, and T. J. Lim, Transmit diversity as a combination of spatial and delay diversity, in Proc. 2000 IEEE 6th Int. Symp. Spread Spectrum Techniques and Applications (AS-SPCC), vol. 1, Sept. 2000, pp. 137140. [21] M. O. Damen, K. Abed-Meraim, and J.-C. Belfiore, Transmit diversity using rotated constellations with Hadamard transform, in Proc. 2000 Symp. Adaptive Systems for Signal Processing, Communications, and Control, AB, Canada, Oct. 2000, pp. 396401. [22] M. O. Damen, A. Tewfik, and J.-C. Belfiore, A construction of a spacetime code based on number theory, IEEE Trans. Inform. Theory, vol. 48, pp. 753760, Mar. 2002. [23] V. Tarokh, A. Naguib, N. Seshadri, and A. R. Calderbank, Space-time codes for high data rates wireless communications: Performance criteria in the presence of channel estimation errors, mobility and multiple paths, IEEE Trans. Commun., vol. 47, pp. 199207, Feb. 1999. [24] H. El Gamal and A. R. Hammons, Jr., Algebraic space-time codes for block fading channels, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 152. [25] R. Knopp and P. Humblet, On coding for block fading channels, IEEE Trans. Inform. Theory, vol. 46, pp. 189205, Jan. 2000. [26] H. El Gamal, A. R. Hammons Jr, Y. Liu, M. P. Fitz, and O. Takeshita, On the design of space-time and space-frequency codes for MIMO frequency selective fading channels, IEEE Trans. Inform. Theory, submitted for publication. [27] H. Blcskei and A. J. Paulraj, Space-frequency codes for broadband fading channels, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 219. [28] M. J. Borran, M. Memarzadeh, and B. Aazhang, Design of coded modulation schemes for orthogonal transmit diversity, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 339. [29] D. Agrawal, V. Tarokh, A. Naguib, and N. Seshadri, Space-time coded OFDM for high data rate wireless communications over wide-band channels, in Proc. 48th IEEE Vehicular Technology Conf., vol. 3, May 1998, pp. 22322236. [30] J. Geng, U. Mitra, and M. P. Fitz, Space-time block codes in multipath CDMA systems, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 151. [31] B. Hassibi and B. Hochwald, Linear dispersion codes, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 325. [32] G. J. Foschini, Layered space-time architecture for wireless communication in a fading environment when using multiple antennas, AT&T Bell Labs. Tech. J., vol. 1, no. 2, pp. 4159, 1996. [33] M. O. Damen, Joint coding/decoding in a multiple access system, application to mobile communications, Ph.D. dissertation, ENST, Paris, France. [Online]. Available: http://www.ee.ualberta.ca/~damen, Oct. 1999.

EL GAMAL AND DAMEN: UNIVERSAL SPACETIME CODING

1119

[34] M. O. Damen, A. Chkeif, and J.-C. Belfiore, Lattice codes decoder for space-time codes, IEEE Commun. Lett., vol. 4, pp. 161163, May 2000. [35] H. El Gamal and A. R. Hammons, Jr, A new approach to layered spacetime coding and signal processing, IEEE Trans. Inform. Theory, vol. 47, pp. 23212335, Sept. 2001. [36] X. Giraud, E. Boutillon, and J.-C. Belfiore, Algebraic tools to build modulation schemes for fading channels, IEEE Trans. Inform. Theory, vol. 43, pp. 938952, May 1997. [37] J.-C. Belfiore, X. Giraud, and J. Rodriguez-Guisantes, Optimal linear labeling for the minimization of both source and channel distortion, in Proc. IEEE Int. Symp. Information Theory, Sorrento, Italy, June 2000, p. 404. [38] J. Boutros and E. Viterbo, Signal space diversity: A power and bandwidth efficient diversity technique for the Rayleigh fading channel, IEEE Trans. Inform. Theory, vol. 44, pp. 14531467, July 1998. [39] G. Golub and C. V. Loan, Matrix Computations, 3rd ed. Baltimore, MD: John Hopkins Univ. Press, 1996. [40] E. Viterbo and J. Boutros, A universal lattice code decoder for fading channel, IEEE Trans. Inform. Theory, vol. 45, pp. 16391642, July 1999. [41] M. O. Damen, K. Abed-Meraim, and M. S. Lemdani, Further results on the sphere decoder, in Proc. Int. Symp. Information Theory, Washington, DC, June 2001, p. 333. [42] U. Fincke and M. Pohst, Improved methods for calculating vectors of short length in a lattice, including a complexity analysis, Math. Comput., vol. 44, pp. 463471, Apr. 1985. [43] M. O. Damen, K. Abed-Meraim, and J.-C. Belfiore, A generalized sphere decoder for asymmetrical space-time communication architecture, IEE Electron. Lett., p. 166, Jan. 2000. [44] A. S. Hedayat, N. J. A. Sloane, and J. Stufken, Orthogonal Arrays: Theory and Applications. New York: Springer-Verlag, 1999. [45] S. Sandhu and A. Paulraj, Space-time block codes: A capacity perspective, IEEE Commun. Lett., vol. 4, pp. 384386, Dec. 2000. [46] M. O. Damen and N. C. Beaulieu, On diagonal space-time codes using algebraic rotations, in Proc. European Wireless Conf., Florence, Italy, Feb. 2002. [47] H. El Gamal and M. Bourles, On the design of adaptive space-time codes, presented at the Information Theory Workshop, Cairns, Australia, Sept. 2001.

[48] B. Hochwald and T. Marzetta, Unitary spacetime modulation for multiple antenna communications in Rayleigh flat fading, IEEE Trans. Inform. Theory, pp. 543564, Mar. 2000. [49] L. Zheng and D. Tse, Sphere packing in Grassmann manifold: A geometric approach to noncoherent multi-antenna channels, in Proc. Int. Symp. Information Theory, Sorrento, Italy, June 2000, p. 364. [50] D. Agrawal, T. Richardson, and R. Urbanke, Multiple-antennas signaling constellations for fading channels, IEEE Trans. Inform. Theory, vol. 47, pp. 26182626, Sept. 2001. Also, [Online]. Available: http://mars.bell-labs.com. [51] B. Hochwald, T. Marzetta, T. Richardson, A. Shokrollahi, and R. Urbanke, Systematic design of unitary space-time constellations, IEEE Trans. Inform. Theory, vol. 46, pp. 19621973, Sept. 2000. Also, [Online]. Available: http://mars.bell-labs.com. [52] B. Hughes, Differential space-time modulation, IEEE Trans. Inform. Theory, vol. 46, pp. 25672578, Nov. 2000. [53] B. Hochwald and W. Sweldens, Differential unitary space-time modulation, IEEE Trans. Commun., vol. 46, pp. 19621973, Sept. 2000. [54] B. Hassibi and B. Hochwald, Cayley differential unitary space-time codes, IEEE Trans. Inform. Theory, vol. 48, pp. 14851503, Jnne 2002. [55] M. L. McCloud, M. Brehler, and M. K. Varanasi, Signal design and convolutional coding for noncoherent space-time communication on the block-Rayleigh-fading channel, IEEE Trans. Inform. Theory., vol. 48, pp. 11861194, May 2002. [56] M. Brehler and M. K. Varanasi, On signal design for the noncoherent multi-antenna block-Rayleigh-fading channel, preprint, May 2002. [57] R. W. Heath, Jr. and A. J. Paulraj, Linear dispersion codes for MIMO systems based on frame theory, IEEE Trans. Signal Processing, vol. 50, pp. 24292441, Oct. 2002. [58] A. B. Shidlovskii, Transcendental Numbers. New York: W. de Gruyter, 1989. [59] H. Cohen, A Course in Computational Algebraic Number Theory. Berlin, Germany: Springer-Verlag, 1993. [60] M. Grtschel, L. Lovsz, and A. Schrijver, Geometric Algorithms and Combinatorial Optimization. New York: Springer-Verlag, 1988. [61] W. Rudin, Functional Analysis, 2nd ed. Singapore: McGraw-Hill, 1991. [62] G. Strang, Linear Algebra and Its Applications. New York: Academic, 1970.