Abstract:
General algebraic space-time code constructions are presented for Gray-mapped 2 K -PSK, 2 K -PAM, and 4 K -QAM constellations. The space-time codes achieve the rate-diversity tradeoff—i.e., they allow the transmission of information at the maximum rate possible for the given signaling constellation and the achieved transmit diversity level. New codes created by applying a nonsingular linear or affine transformation to the constellation labels retain the optimality of the original codes with respect to the rate-diversity tradeoff. Extensions to p K -PSK, p K -PAM, p 2K -QAM, and related constellations, for p prime, are also given.

Description:
CROSS-REFERENCE TO RELATED APPLICATIONS 
   This application claims the benefit of prior filed U.S. provisional Application No. 60/729,522, filed on Oct. 24, 2005, and incorporated fully herein by reference. 

   STATEMENT OF GOVERNMENTAL INTEREST 
   This invention was made with Government support under National Science Foundation Grant No. CCR-0325781. The Government has certain rights in the invention. 

   BACKGROUND OF THE INVENTION 
   1. Field of the Invention 
   This invention relates to the field of space-time codes for linearly labelled constellations, and more particularly, to a method, system, and computer program product for constructing space-time codes for linearly labelled constellations using Gray mapping. 
   2. Description of the Related Art 
   I. Introduction 
   Recent advances in coding theory include space-time codes which provide diversity in multiple-input multiple-output (MIMO) antenna systems over fading channels with channel coding across a small number of transmit antennas. For wireless communication systems, a number of challenges arise from the harsh RF propagation environment characterized by channel fading and co-channel interference (CCI). Channel fading can be attributed to diffuse and specular multipath, while CCI arises from reuse of radio resources. Interleaved coded modulation on the transmit side of the system and multiple antennas on the receive side are standard methods used in wireless communication systems to combat time-varying fading and to mitigate interference. Both are examples of diversity techniques. 
   Simple transmit diversity schemes (in which, for example, a delayed replica of the transmitted signal is retransmitted through a second, spatially-independent antenna and the two signals are coherently combined at the receiver by a channel equalizer) have also been considered within the wireless communications industry as a method to combat multipath fading. From a coding perspective, such transmit diversity schemes amount to repetition codes and encourage consideration of more sophisticated code designs. Information-theoretic studies have demonstrated that the capacity of multi-antenna systems significantly exceeds that of conventional single-antenna systems for fading channels. The challenge of designing channel codes for high capacity multi-antenna systems has led to the development of “space-time codes,” in which coding is performed across the spatial dimension (e.g, antenna channels) as well as time. 
   Space-time codes are designed for MIMO communication systems that employ multiple transmit antennas to achieve spatial diversity. The modulated code words are often presented as complex-values M×T matrices in which the (m,t)-th entry sm,t represents the discrete baseband signal transmitted from the m-th transmit antenna at time t. The initial work on space-time codes by Guey et al. and Tarokh et al. showed that the transmit diversity achieved by a space-time code is equal to the minimum rank among the set of matrices produced as differences between distinct modulated code words. There is a tradeoff between achievable transmission rate and achievable transmit diversity level for space-time codes. Full-rank space-time codes can achieve transmission rates no greater than one symbol per transmission interval. For rank d space-time codes, the maximum transmission rate is M−d+1 symbols per transmission interval. Equivalently, the size of an M×T rank-d space-time code cannot exceed qT(M−d+1), where q is the size of the signaling constellation. Codes meeting this upper limit are referred to as maximal. 
   Let C be a linear error-correcting code of length MT, with M≦T, over the discrete alphabet Ω. The code words of C are presented as M×T matrices in which the (m,t)-th entry a m,t εΩ represents the information symbol that is modulated and transmitted from the m-th transmit antenna at transmission interval t. If all of the modulated code word matrices have rank at least d over            , then the space-time code is called an M×T rank-d code. In the special case that all of the modulated code words are of full rank M, the space-time code is called an M×T full-rank code. There is a tradeoff between achievable transmission rate and achievable transmit diversity level as dictated by the Singleton Bound. For rank d space-time codes, the maximum transmission rate is M−d+1 symbols per transmission interval.
   In U.S. Pat. No. 6,678,263, Hammons and El Gamal developed the so-called binary rank criteria that allowed, for the first time, the algebraic design of space-time codes achieving maximal spatial diversity of all orders. From the binary rank criteria, they developed the general stacking construction for full-diversity space-time codes, examples of which include block codes derived from Galois fields and rings and rate 1/M convolutional codes of optimal d free . The binary rank criteria showed that the algebraically-designed, full-rank, BPSK-modulated space-time codes could be lifted to full-rank, QPSK-modulated space-time codes. In particular, Hammons and El Gamal showed that, if the linear binary codes A and B produce full-rank space-time codes when BPSK modulated, then the quaternary code C=A+2B produces a full-rank space-time code under QPSK modulation. They referred to this construction as the dyadic construction. 
   Building on the Hammons-El Gamal framework, Lu and Kumar showed that the dyadic construction extends to 2 m -PSK modulation in the natural way—i.e., if the linear binary codes A 0 , A 1 , . . . , A m−1  produce full-rank space-time codes under BPSK modulation, then the 2 m -ary code 
           ??   =       ∑     i   =   0       m   -   1       ⁢       2   i     ⁢     ??   i               
produces a full-rank space-time code under 2 m -PSK modulation. They showed that similar results apply to codes of rank d≦M. Furthermore, Lu and Kumar developed a unified space-time code construction that generalizes the basic 2 m -PSK dyadic construction to produce space-time codes for 2 m -PAM, 4 m -QAM, and other exotic higher-order constellations that achieve the rate-diversity tradeoff. The Lu/Kumar construction of space-time codes are optimal for rate-diversity tradeoff but do not use Gray labeled constellations. Since Gray labeled 2 K -PAM, 2 K -PSK, and 4 K -QAM is the usual practice in communication systems (because for most channels this labeling minimizes the BER at high SNR), the Lu/Kumar construction has deficiencies.
 
   In U.S. Pat. No. 6,678,263, Hammons and El Gamal showed also that the BPSK and QPSK space-time code constructions admit certain binary transformations that preserve the rank properties of the modulated space-time codes. 
   SUMMARY OF THE INVENTION 
   In this application, it is shown that similar results apply to the Lu/Kumar basic constructions for 2 K -PSK, 2 K -PAM, and 4 K -QAM space-time codes. In particular, this refinement provides new algebraic space-time codes that are suitable for use when, as in the usual practice, Gray mapping is used to label the signaling constellations. 
   This invention shows how to construct space-time codes for 2 K -PAM, 2 K -PSK, and 4 K -QAM modulation that are suitable for different labelings of the constellation points. One way this is done is by introducing transformation into basic space-time code constructions by Lu/Kumar. Details of the new construction are set forth below. The present invention, as set forth herein, establishes that any linear transformation will preserve the codes&#39; optimal rate-vs-diversity properties. Explicit transformations are given to produce new codes suitable for Gray labeled 2 K -PAM, 2 K -PSK, and 4 K -QAM. 

   
     BRIEF DESCRIPTION OF THE DRAWINGS 
     The various aspects, advantages and novel features of the present invention will be more readily comprehended from the following detailed description when read in conjunction with the appended drawings in which: 
       FIG. 1  is a block diagram of an exemplary digital cellular Direct Sequence Code Division Multiple Access (DS-CDMA) base-station-to-mobile-station (or forward) link; 
       FIG. 2  is a block diagram of a system for a digital cellular system which implements space-time encoding and decoding in accordance with an embodiment of the present invention; and 
       FIG. 3  is a block diagram illustrating space-time encoding and decoding in accordance with an embodiment of the present invention. 
   

   DETAILED DESCRIPTION 
   Referring to  FIG. 1 , by way of an example, a conventional digital cellular Direct Sequence Code Division Multiple Access (DSCDMA) base-station-to-mobile-station (or forward) link  10  is shown using a conventional convolutional encoder and Viterbi decoder.  FIG. 1  also illustrates the mobile-station-to-base-station (or reverse) link. 
   At the transmit end, the system  10  in  FIG. 1  comprises a data segmentation and framing module  16  where user information bits are assembled into fixed length frames from transmit data blocks  12 . The N bits per frame are input to the base station&#39;s convolutional encoder  18  of rate r, which produces N/r code symbols at the input of the channel interleaver  20 . The channel interleaver  20  performs pseudo-random shuffling of code symbols, and outputs the re-arranged symbols to the spread spectrum modulator  22 . The spread spectrum modulator  22  uses a user-specific transmit PN-code generator  24  to produce a spread spectrum signal which is carried on a RF carrier to the transmitter  26 , where a high power amplifier coupled to the transmit antenna  28  radiates the signal to the base station. The techniques of spread spectrum modulation and RF transmission are well known art to one familiar with spread spectrum communications systems. 
   The signal received at the mobile station antenna  30  is amplified in the RF receiver  32  and demodulated by the spread spectrum demodulator  34 , which uses the same PN-code generator  36  as used by the base station transmitter to de-spread the signal. The demodulated symbols are de-interleaved by the channel de-interleaver  38  and input to the Viterbi decoder  40 . The decoded information bits are reconstructed using data block reconstruction  42  into receive data blocks  14  and forwarded to the data terminal equipment at the receive end. 
   With reference to  FIG. 2 , a digital cellular base-station-to-mobile-station link is shown to illustrate the implementation of space-time encoding and decoding in accordance with an embodiment of the present invention. While CDMA system is used as an example, one familiar with the art would consider the present invention applicable to other types of wireless systems, which can employ other types of multiple access methods such as frequency division multiple access (FDMA), time division multiple access (TDMA), and hybrid methods. 
   Transmit data blocks  52  from the data terminal equipment are segmented and framed  56  into fixed frame length and applied to the mobile&#39;s channel space-time encoder  58 . The output from a channel encoder  60  is fed to the space-time formatter  62  which determines the parsing (allocation and presentation order) of the coded symbols to the various transmit antennas  70   a ,  70   b ,  70   c . The spatial formatter output is applied to the spread spectrum modulator  64  which uses a user specific PN-code generator  66  to create spread spectrum signals, carried on a RF carrier via base RF transmitter  68 , to the mobile station transmitter. The transmitter, with high power amplifier coupled to the Transmit antenna, radiates the signals via separate transmit antennas to the mobile station. 
   The signal received at one or more mobile station antenna(s)  72  is amplified in the mobile RF receiver  74  and demodulated in a phase shift keying demodulator  76 , which uses the same PN-code generator  78  as used by the base station transmitter, to de-spread the signal. The demodulated symbols are processed at space-time decoder  80  by the space-time de-formatter  82  and input to the channel decoder  84 . The decoded information bits are reconstructed  86  into receive data blocks  54  and forwarded to the data terminal equipment at the receive end. Depending on the space-time code used, the de-formatter  82  and the decoder  84  can be grouped in a single maximum likelihood receiver. 
     FIG. 3  illustrates an exemplary communication system  90  having a path  92  from a source and a path  94  to a sink and which can be a system other than a cellular system. The system  90  has a space-time encoder  96  that is similar to the encoder  58  depicted in  FIG. 2  in that it comprises a constituent encoder  98  and a spatial formatter  100 . Plural modulators  102   a ,  102   b ,  102   c , and so on, are also provided. At the receiver end, a space-time demodulator  104  and a space-time decoder  106  are provided. 
   With continued reference to  FIG. 3 , the source generates k information symbols from a discrete alphabet X on the path  92  which are encoded by an error control code C by the space-time encoder  96 . The space-time encoder  96  produces code words of length N over the symbol alphabet Y. The encoded symbols are mapped by the modulators  102   a ,  102   b ,  102   c , and so on, onto constellation points from a discrete, complex-valued signaling constellation for transmission across the channel. The modulated radio frequency signals for all of the L transmit antennas  102   a ,  102   b ,  102   c , and so on, are transmitted at the same time to the receiver space-time demodulator  104 . The space-time channel decoder  106  decodes the signals to the received data path  94 . As shown, the receiver provides M receive antennas to collect the incoming transmissions. The received baseband signals are subsequently decoded by the space-time decoder  106 . 
   The present invention is concerned primarily with the design of space-time codes rather than the signal processing required to decode them. In most cases, the decoding employs known signal processing for maximum likelihood detection. 
   In the following discussion, notation is established and certain key ideas of the Lu-Kumar approach, upon which the novel space-time code constructions of the present invention are built, are explained. Following the discussion of the Lu-Kumar approach, new constructions of space-time codes for applying linear and affine transformations to the space-time code constructions proposed by Lu and Kumar, in accordance with the present invention, are described. As described, the proper choice of transformation yields new algebraic space-time codes that are compatible with Gray labelling. 
   II. Preliminaries 
   We consider algebraic space-time code design based on the ring            [θ] of algebraic integers with θ a complex root of unity. The connection between modulated space-time codes, with entries from          [θ]⊂         , and binary codes over          ={0, 1} is through the isomorphism          [θ]/(1−θ)≅         . We will let μ:          [θ]→          denote the corresponding projection modulo 1−θ. The following results from Lu and Kumar underlie the space-time code constructions.
   Proposition 1 Let θ be a complex, primitive 2 ν -th root of unity. For 0≦l&lt;ν, let Δs=θ 2     l     m −θ 2     l     n , where m and n are integers. Then, (1−θ 2     l   )|Δs in          [θ]. Furthermore,   

                 Δ   ⁢           ⁢   s       1   -     θ     2   ℓ           ≡       m   _     ⊕       n   _     ⁢           ⁢     (       mod   ⁢           ⁢   1     -   θ     )           ,         
where  m  and  n  denote the modulo 2 projections of m and n, respectively, and ⊕ denotes modulo 2 addition.
     Proposition 2 Let C be complex M×T matrix, (M≦T), with entries from          [θ]. If the binary projection μ(C) is of rank d over          , then C is of rank at least d over          .   
   The following notation will be used. The set of M×T matrices over an alphabet Ω will be denoted by Ω M×T . When A=[ i,j ] is a matrix with entries in              2     K   , we write θ A  for the matrix whose (i,j)-th entry is θ a     i,j   . For matrices A and B, the matrix A⊙B is their Hermitian (i.e., componentwise) product.
   III. New Space-Time Code Constructions 
   Let τ:              ν →           ν  be a linear transformation. We can extend this map to a linear transformation τ: (           M×T ) ν →(           M×T ) ν , acting on ν-tuples of M×T binary matrices, as follows. Let Ā=(A 0 , A 1 , . . . , A ν−1 )ε(           M×T ) ν , where A i  is an M×T matrix whose (m, t)-th entry is a m,t   (i) . Then τ(Ā) is the matrix whose (m, t)-th entry is τ(a m,t   (0) , a m,t   (1) , . . . , a m,t   (ν−1) . The component mappings τ 0 : τ 1 , . . . , τ ν−1  of τ are defined by the relationship τ(Ā)=(τ 0 (Ā), τ 1 (Ā), . . . , τ 84-1 (Ā)). The following straightforward properties of τ are worth special note.
   Lemma 3 The linear transformation τ is nonsingular over            ν  if and only if its extension is nonsingular over (           M×T ) ν ,   Lemma 4 If A is a linear binary code, then τ(A ν )⊂A ν .   When ν=KU, we will use A KU  and   

               ??   K     ×   ??   ×   …   ×     ??   K         ︷     U   ⁢           ⁢   times             
interchangeably as convenient.
 
   A. 2 K -PSK Modulation 
   The 2 K -PSK constellation consists of the points
 
 s=θ   a     0     +2a     1     + . . . +2     K−1     a     k−1   ,  (1)
 
for ā=(a 0 , a 1 , . . . , a K−1 )ε             K , where θ is a complex, primitive 2 K -th root of unity.

   For Āε             M×T , let the notation θ(Ā) be shorthand for θ A     0     +2A     1     + . . . +2     K−1     A     K−1   . From the dyadic construction, we know that S={θ(Ā): ĀεA K } is an M×T space-time code achieving the rate-diversity tradeoff. The following theorem provides a generalization of the PSK dyadic construction.
   Theorem 5 Let θ be a complex, primitive 2 K -th root of unity. Let A be a linear binary M×T maximal rank d code, and let τ:            K →           K  be a nonsingular linear transformation. Then S τ ={θ(τ(Ā)): ĀεA K } is an M×T space-time code that achieves the rate-diversity tradeoff for 2 K -PSK modulation.   

   Proof: That S τ  achieves the proper transmission rate follows immediately from the fact that A is maximal. It therefore suffices to show that the difference between distinct code words in S τ  has rank at least d. 
   Let Ā, Ā′εA K  with Ā≠Ā′. By Lemma 3, since τ is nonsingular over (             M×T ) K , we have τ(Ā)≠τ(Ā′). Let l be the first index i for which τ i (Ā)≠τ i (Ā′). Then, by Proposition 1,
                       θ   ⁡     (     τ   ⁡     (     A   _     )       )       -     θ   ⁡     (     τ   ⁡     (       A   _     ′     )       )           1   -     θ     2   ℓ           ≡         τ   ℓ     ⁡     (     A   _     )       ⊕         τ   ℓ     ⁡     (       A   _     ′     )       ⁢           ⁢       (       mod   ⁢           ⁢   1     -   θ     )     .                 (   2   )               
Since τ l (Ā), τ l (Ā′)εA by Lemma 4 and A is a maximal rank d code, we have τ l (Ā)⊕τ l (Ā′) is of rank at least d over            . Hence, by Proposition 2, θ(τ(Ā))−θ(τ(Ā′)) is of rank at least d over          , which completes the proof.

   B. 2 K -PAM Modulation 
   The 2 K -PAM constellation consists of the points 
                   s   =       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       (     -   1     )       a   k             ,           (   3   )               
for ā=(a 0 , a 1 , . . . , a K−1 )ε             K . With this representation, Lu and Kumar showed that a PAM-modulated space-time code with optimal rate-diversity tradeoff is produced when each parameter a k  is replaced with a code word A k εA, where A is a linear binary maximal rank d code. The following result is a generalization of this basic PAM construction.
   Theorem 6 Let A be a linear binary M×T maximal rank d code, and let τ:            K →           K  be a nonsingular linear transformation. Then   
             ??   τ     =     {         ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       (     -   1     )         τ   k     ⁡     (     A   _     )         ⁢     :     ⁢           ⁢     A   _         ∈     ??   K       }           
is an M×T space-time code that achieves the rate-diversity tradeoff for 2 K -PAM modulation.
     Proof: Let Ā, Ā′εA K  with Ā≠Ā′. Consider the difference ΔS=S−S′, where S=Σ k=0   K−1 2 k (−1) τ     k     (Ā)  and S′=Σ k=0   K−1 2 k (−1) τ     k     (Ā′) .   
   By Lemma 3, τ(Ā)≠τ(Ā′). Let l be the first index i for which τ i (Ā)≠τ i (Ā′). Then 
   
     
       
         
           
             
               
                 
                   
                     
                       Δ?? 
                       
                         2 
                         
                           ℓ 
                           + 
                           1 
                         
                       
                     
                     = 
                     
                       
                         
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               
                                 τ 
                                 ℓ 
                               
                               ⁡ 
                               
                                 ( 
                                 A 
                                 ) 
                               
                             
                           
                           - 
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               
                                 τ 
                                 ℓ 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   A 
                                   ′ 
                                 
                                 ) 
                               
                             
                           
                         
                         2 
                       
                       + 
                       D 
                     
                   
                   , 
                   
                     
 
                   
                   ⁢ 
                   where 
                 
                 ⁢ 
                 
                   
 
                 
                 ⁢ 
                 D 
                 = 
                 
                   
                     ∑ 
                     
                       k 
                       = 
                       1 
                     
                     
                       K 
                       - 
                       ℓ 
                       - 
                       1 
                     
                   
                   ⁢ 
                   
                     
                       
                         2 
                         
                           k 
                           - 
                           1 
                         
                       
                       ⁡ 
                       
                         [ 
                         
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               
                                 τ 
                                 
                                   ℓ 
                                   + 
                                   k 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 A 
                                 ) 
                               
                             
                           
                           - 
                           
                             
                               ( 
                               
                                 - 
                                 1 
                               
                               ) 
                             
                             
                               
                                 τ 
                                 
                                   ℓ 
                                   + 
                                   k 
                                 
                               
                               ⁡ 
                               
                                 ( 
                                 
                                   A 
                                   ′ 
                                 
                                 ) 
                               
                             
                           
                         
                         ] 
                       
                     
                     . 
                   
                 
               
             
             
               
                 ( 
                 4 
                 ) 
               
             
           
         
       
     
       
       Applying Proposition 1 with ν=1 and θ=1 to (4), we find 
     
  
   
     
       
         
           
             Δ?? 
             
               2 
               
                 ℓ 
                 + 
                 1 
               
             
           
           ≡ 
           
             
               
                 τ 
                 ℓ 
               
               ⁡ 
               
                 ( 
                 
                   A 
                   _ 
                 
                 ) 
               
             
             ⊕ 
             
               
                 
                   τ 
                   ℓ 
                 
                 ⁡ 
                 
                   ( 
                   
                     
                       A 
                       _ 
                     
                     ′ 
                   
                   ) 
                 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   ( 
                   
                     mod 
                     ⁢ 
                     
                         
                     
                     ⁢ 
                     2 
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
       
       By Lemma 4, τ l (Ā)⊕τ l (Ā′)εA. Hence, by Proposition 2 and choice of A as a rank d binary code, ΔS has rank at least d over          . 
     
  
   C. 4 K -QAM Modulation 
   The 4 K -QAM constellation consists of the points 
                   s   =       (     1   +   i     )     ⁢       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     i       a   k     +     2   ⁢     b   k                   ,           (   5   )               
for ā=(a 0 , a 1 , . . . , a K−1 ) and  b =(b 0 , b 1 , . . . , b K−1 ) in              K . With this representation, Lu and Kumar [?] showed that a QAM-modulated space-time code with optimal rate-diversity tradeoff is produced when the parameters a k  and b k  are replaced with code words A k , B k εA, where A is a linear binary maximal rank d code. This basic 4 K -QAM construction is generalized by the following result.
   Theorem 7 Let A be a linear binary M×T maximal rank d code. Let τ:            2K →           2k  be a nonsingular linear transformation, with α(  x ), β(  x )ε           K  denoting the left and right halves of τ(  x ), respectively. Then   
             ??   τ     =     {         (     1   +   i     )     ⁢       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     i         α   k     ⁡     (       A   _     ,     B   _       )       +     2   ⁢       β   k     ⁡     (       A   _     ,     B   _       )             ⁢     :     ⁢           ⁢     (       A   _     ,     B   _       )           ∈       ??   K     ×     ??   K         }           
is an M×T space-time code that achieves the rate-diversity tradeoff for 4 K -QAM modulation.
     Proof: Let S=(1+i)Σ u=0   K−1 2 k     i     α     k     +2β     k    and S′=(1+i)Σ u=0   K−1 2 k     i     α′     k     +2β′     k    be distinct code words in S τ , where with some abuse of notation α k  denotes α k (Ā,  B ), α′ k  denotes α k (Ā′,  B ′), etc. Since τ is nonsingular, there is some k for which either α k ≠α′ k  or β k ≠β′ k . Let l denote the first index for which one of these inequalities occurs.
 
Case (i): α l ≠α′ l .
   
   Note that 
   
     
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               S 
             
             = 
             
               
                 S 
                 - 
                 
                   S 
                   ′ 
                 
               
               = 
               
                 
                   2 
                   ℓ 
                 
                 ⁢ 
                 
                   
                     ( 
                     
                       1 
                       + 
                       i 
                     
                     ) 
                   
                   ⁡ 
                   
                     [ 
                     
                       
                         ( 
                         
                           
                             i 
                             
                               
                                 α 
                                 ℓ 
                               
                               + 
                               
                                 2 
                                 ⁢ 
                                 
                                   β 
                                   ℓ 
                                 
                               
                             
                           
                           - 
                           
                             i 
                             
                               
                                 α 
                                 ℓ 
                                 ′ 
                               
                               + 
                               
                                 2 
                                 ⁢ 
                                 
                                   β 
                                   ℓ 
                                   ′ 
                                 
                               
                             
                           
                         
                         ) 
                       
                       + 
                       
                         2 
                         ⁢ 
                         D 
                       
                     
                     ] 
                   
                 
               
             
           
           , 
           
             
 
           
           ⁢ 
           where 
         
       
     
     
       
         
           D 
           = 
           
             
               ∑ 
               
                 i 
                 = 
                 0 
               
               
                 K 
                 - 
                 ℓ 
                 - 
                 2 
               
             
             ⁢ 
             
               
                 2 
                 i 
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       i 
                       
                         
                           α 
                           
                             ℓ 
                             + 
                             i 
                             + 
                             1 
                           
                         
                         + 
                         
                           2 
                           ⁢ 
                           
                             β 
                             
                               ℓ 
                               + 
                               i 
                               + 
                               1 
                             
                           
                         
                       
                     
                     - 
                     
                       i 
                       
                         
                           α 
                           
                             ℓ 
                             + 
                             i 
                             + 
                             1 
                           
                           ′ 
                         
                         + 
                         
                           2 
                           ⁢ 
                           
                             β 
                             
                               ℓ 
                               + 
                               i 
                               + 
                               1 
                             
                             ′ 
                           
                         
                       
                     
                   
                   ) 
                 
                 . 
                 
                   
 
                 
                 ⁢ 
                 So 
               
             
           
         
       
     
     
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               S 
             
             
               
                 2 
                 ℓ 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   + 
                   i 
                 
                 ) 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   - 
                   i 
                 
                 ) 
               
             
           
           = 
           
             
               ( 
               
                 
                   
                     i 
                     
                       
                         α 
                         ℓ 
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                           β 
                           ℓ 
                         
                       
                     
                   
                   - 
                   
                     i 
                     
                       
                         α 
                         ℓ 
                         ′ 
                       
                       + 
                       
                         2 
                         ⁢ 
                         
                           β 
                           ℓ 
                           ′ 
                         
                       
                     
                   
                 
                 
                   1 
                   - 
                   i 
                 
               
               ) 
             
             + 
             
               
                 ( 
                 
                   2 
                   
                     1 
                     - 
                     i 
                   
                 
                 ) 
               
               ⁢ 
               
                 D 
                 . 
               
             
           
         
       
     
       
       Applying Proposition 1 with ν=2, we have 
     
  
   
     
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               S 
             
             
               
                 2 
                 ℓ 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   + 
                   i 
                 
                 ) 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   - 
                   i 
                 
                 ) 
               
             
           
           ≡ 
           
             
               α 
               ℓ 
             
             ⊕ 
             
               
                 α 
                 ℓ 
                 ′ 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       mod 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       1 
                     
                     - 
                     i 
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
       
       Since α l ⊕α′ l εA, we have by Proposition 2 that ΔS has rank at least d over          .
 
Case (ii): α l =α′ l  but β l ≠β′ l .
 
     
  
   In this case, 
   
     
       
         
           
             
               
                 Δ 
                 ⁢ 
                 
                     
                 
                 ⁢ 
                 S 
               
               
                 
                   2 
                   ℓ 
                 
                 ⁢ 
                 
                   ( 
                   
                     1 
                     + 
                     i 
                   
                   ) 
                 
                 ⁢ 
                 
                   ( 
                   
                     1 
                     - 
                     
                       i 
                       2 
                     
                   
                   ) 
                 
               
             
             ⁢ 
             
               
                 i 
                 
                   α 
                   ℓ 
                 
               
               ⊙ 
               
                 ( 
                 
                   
                     
                       i 
                       
                         2 
                         ⁢ 
                         
                           β 
                           ℓ 
                         
                       
                     
                     - 
                     
                       i 
                       
                         2 
                         ⁢ 
                         
                           β 
                           ℓ 
                           ′ 
                         
                       
                     
                   
                   
                     1 
                     - 
                     
                       i 
                       2 
                     
                   
                 
                 ) 
               
             
           
           + 
           
             
               ( 
               
                 2 
                 
                   1 
                   - 
                   
                     i 
                     2 
                   
                 
               
               ) 
             
             ⁢ 
             
               D 
               . 
             
           
         
       
     
       
       Applying Proposition 1 with ν=2, 
     
  
   
     
       
         
           
             
               Δ 
               ⁢ 
               
                   
               
               ⁢ 
               S 
             
             
               
                 2 
                 ℓ 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   + 
                   i 
                 
                 ) 
               
               ⁢ 
               
                 ( 
                 
                   1 
                   - 
                   
                     i 
                     2 
                   
                 
                 ) 
               
             
           
           ≡ 
           
             
               β 
               ℓ 
             
             ⊕ 
             
               
                 β 
                 ℓ 
                 ′ 
               
               ⁢ 
               
                   
               
               ⁢ 
               
                 
                   ( 
                   
                     
                       mod 
                       ⁢ 
                       
                           
                       
                       ⁢ 
                       1 
                     
                     - 
                     i 
                   
                   ) 
                 
                 . 
               
             
           
         
       
     
       
       Since β l ⊕β′ l εA, we have by Proposition 2 that ΔS has rank at least d over          . 
     
  
   IV. Application to Gray Mapping 
   One may interpret the mapping τ in Theorems 5 through 7 as changing the way the constellation is labelled. In this section, we show that the proper choice of τ enables the use of Gray labelling, which is common practice for these constellations. 
   For 2 K -PSK and 2 K -PAM, the constellation points have a natural ordering with parameterization by the integers L=0, 1, 2, . . . , 2 K −1. For 2 K -PSK, the L-th constellation point is s L =θ L ; for 2 K -PAM, s L =2L−(2 K −1). Therefore, it is natural to assign K-bit labels to these constellation points by labelling s L  with the binary expansion of L. Since 4 K -QAM consists of two 2 K -PAM constellations in quadrature, its natural labelling is the cross product of the constituent PAM labellings. 
   For signaling purposes, however, the natural labelling is usually not optimal. Over typical channels, the predominant symbol errors at sufficiently high signal-to-noise ratios are those in which the transmitted constellation point is mistaken for one of its adjacent neighbors. Under these conditions, the demodulated bit error rate depends asymptotically on the distribution of Hamming distances between labels of adjacent constellation points. The usual practice is to label 2 K -PSK, 2 K -PAM, and 4 K -QAM constellations using a Gray mapping. A Gray mapping is a function that maps the natural constellation labels to a new set having the property that all adjacent labels differ in exactly one bit position. With Gray labelling, the demodulated bit error rate will then be asymptotically equal to the symbol error rate. 
   Consider the transformation ζ:              K →           k  in which the natural label b K−1  . . . b 1 b 0  is mapped to the new label a K−1  . . . a 1 a 0 , with
             a   k     =     {               b   k     ⊕     b     k   +   1         ,             if   ⁢           ⁢   k     &lt;     K   -   1                   b     K   -   1       ,             if   ⁢           ⁢   k     =     K   -   1.                     
This transformation is a Gray mapping and is a nonsingular linear transformation over              K . Its inverse ζ −1  is defined by

             b   k     =     {               ∑     i   =   k       K   -   1       ⁢       a   i     ⁢           ⁢     (     mod   ⁢           ⁢   2     )         ,             if   ⁢           ⁢   k     &lt;     K   -   1                   a     K   -   1       ,               if   ⁢           ⁢   k     =     K   -   1.       ⁢                           
For the PSK dyadic space-time code construction, the implicit constellation labelling is the natural one as given by equation (1). Therefore, by application of Theorem 5, we have the following result.
     Corollary 8 Let A be a linear binary maximal rank d code, and let τ=ζ −1  be the inverse Gray mapping. Then the space-time code S τ  described in Theorem 5 achieves the optimal rate-diversity tradeoff for the 2 K -PSK constellation with Gray labelling.   
   For the basic PAM space-time code construction, the labelling is implicitly determined by equation (3). Note that 
                           ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       (     -   1     )       a   k           =     -       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     (       2   ⁢     a   k       -   1     )                       =     -     [       2   ⁢     (       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     a   k         )       -     (       2   K     -   1     )       ]                     =     -     s   L         ,                       (   6   )                                               (   7   )                               (   8   )                     
where L=Σ k=0   K−1 2 k a k . Thus, the implicit constellation labelling used in (3) is the ones-complement of the natural labelling. This leads to the following result.
     Corollary 9 Let A be a linear binary maximal rank d code, and let τ=ζ −1  be the inverse Gray mapping. Then the space-time code S τ  described in Theorem 6 achieves the optimal rate-diversity tradeoff for a Gray-coded 2 K -PAM constellation.   
   For the basic QAM space-time code construction, the labelling is implicitly determined by equation (5), from which we derive equations for the two PAM quadrature components. Note that 
                           (     1   +   i     )     ⁢       ∑     k   ⁢           =           ⁢   0               ⁢     K   ⁢           -           ⁢   1         ⁢       2             ⁢   k       ⁢     i             ⁢       α   k     ⁢           +           ⁢     2   ⁢           ⁢     b   k                   =       ⁢       [         ∑       a   k     =   0       ⁢       2   k     ⁢       (     -   1     )       b   k           -       ∑       a   k     =   1       ⁢       2   k     ⁢       (     -   1     )       b   k             ]     +                     ⁢     i   ⁡     [         ∑       a   k     =   0       ⁢       2   k     ⁢       (     -   1     )       b   k           -       ∑       a   k     =   1       ⁢       2   k     ⁢       (     -   1     )       b   k             ]                     (   9   )                       ⁢     =         ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       (     -   1     )         a   k     ⊕     b   k             +     i   ⁢       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢         (     -   1     )       b   k       .                       (   10   )               
Comparing (8) and (10) leads to the following result.
     Corollary 10 Let A be a linear binary maximal rank d code. Let τ be the linear transformation mapping ā|  b ε           2K  to ζ −1 (ā)⊕ζ −1 (  b )|ζ −1 (  b )ε           2K . Then the space-time code S τ  described in Theorem 7 achieves the optimal rate-diversity tradeoff for a Gray-coded 4 K -QAM constellation.   
   V. Extensions 
   Lu and Kumar developed a general space-time code construction unifying the algebraic constructions for 2 m -PAM, 2 m -PSK, and 4 m -QAM constellations. This unified framework was further generalized by Hammons to provide space-time codes for other common AM-PSK modulation formats, which codes also achieve the rate-diversity trade-off. The theorems of section III likewise generalize to the unified frameworks. Application to the Lu-Kumar unified construction is addressed in this paper, whereas generalization to the AM-PSK cases will be presented separately. 
   A. Unification of PAM, PSK, and QAM Results 
   The constellation points for 2 m -PAM, 2 m -PSK, and 4 m -QAM may be produced by the common formula 
                 s   =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢       2   u     ⁢     θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     a     u   ,   k                           (   11   )               
through proper choice of parameters. Here K is a complex non-zero scalar, K and U are integers, θ is a primitive K-th root of unity, and ā=(a 00 , a 01 , . . . , a U−1,K−1 )ε             KU  indexes the constellation points. For PAM, one chooses K=1, U=m, θ=−1, κ=1; for QAM, one chooses K=2, U=m, θ=i=√{square root over (−1)}, κ=1+i; one chooses K=m, U=1, θ=e 2πi/2     m   , κ=1. Different choices give other more exotic constellations.

   Substituting maximal rank-d binary codes A u,k  for parameters a u,k  in (11) yields a general construction of space-time codes that achieve the rate-diversity trade-off. 
   We again introduce the linear transformation τ:              ν →           ν , this time with ν=KU. In addition to the scalar components of τ defined previously, we also define its subvector components through the action
 
τ:  x ε           KU           (τ 0 (  x ),τ 1 (  x ), . . . , τ U−1 (  x ))ε           K × . . . ×           K .
 
In this notation, the scalar components of τ are then indexed by the pairs (u, k) so that
 
τ u (    x   )=(τ u,0 (    x   ),τ u,1 (    x   ), . . . , τ u,K−1 (    x   )).

   The following result generalizes Theorems 5, 6, and 7.
     Theorem 11 Let A be a maximal M×T rank-d binary code. Let K and U be positive integers. Let κ be a non-zero complex number, θ be a complex primitive 2 K -th root of unity, and η be a non-zero element of 2         [θ]. Let τ:            KU →           KU  be a nonsingular linear transformation.   

   Then the modulated space-time code defined by 
                   S   τ     =     {             S   =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢       η   u     ⁢     θ   ⁡     (       τ   u     ⁡     (     A   ~     )       )       ⁢     :             ⁢                         A   ~     =         (         A   _     0     ,       A   _     1     ,   …   ⁢           ,       A   _       U   -   1         )     ∈       ??   K     ×   …   ×     ??   K         =     ??   KU               }             (   12   )               
achieves transmit diversity d and transmission rate R=(KU)(M−d+1) bits per channel use, the maximum possible rate.
 
   Proof: Let S=κΣ u=0   U−1 η u θ(τ u (Ã)) and S′=κΣ u=0   U−1 η u θ(τ u (Ã′)) be distinct code words in S. Let (u*, k*) denote the lexographically first index pair (u, k) for which τ u,k (Ã)≠τ u,k (Ã′). Then 
                       Δ   ⁢           ⁢   S     =       S   -     S   ′       =         κη     u   *       ⁢       θ   P     ⊙     (       θ       2     k   *       ⁢   Q       -     θ       2     k   *       ⁢     Q   ′           )         +       κη       u   *     +   1       ⁢   E           ,     
     ⁢   where     ⁢     
     ⁢       P   =       ∑     i   =   0         k   *     -   1       ⁢       2   i     ⁢       τ       u   *     ,   i       ⁡     (     A   ~     )             ,     
     ⁢     Q   =       ∑     i   =   0       K   -     k   *     -   1       ⁢       2   i     ⁢       τ       u   *     ,       k   *     +   i         ⁡     (     A   ~     )             ,     
     ⁢       Q   ′     =       ∑     i   =   0       K   -     k   *     -   1       ⁢       2   i     ⁢     τ       u   *     ,       k   *     +   i         ⁢     (       A   ′     ~     )           ,     
     ⁢   and     ⁢     
     ⁢     E   =       ∑     i   =   0       U   -     u   *     -   2       ⁢         η   i     ⁡     [       θ   ⁡     (       τ       u   *     +   i   +   1       ⁡     (     A   ~     )       )       -     θ   ⁡     (       τ       u   *     +   i   +   1       ⁡     (       A   ~     ′     )       )         ]       .     
     ⁢   Then                 (   13   )                   Δ   ⁢           ⁢   S         κη     u   *       ⁡     (     1   -     θ     2     k   *           )         =         θ   P     ⊙     (         θ       2     k   *       ⁢   Q       -     θ       2     k   *       ⁢     Q   ′             1   -     θ     2     k   *             )       +       (     η     1   -     θ     2     k   *             )     ⁢     E   .                 (   14   )               
The terms in parentheses on the right hand side are either scalars in            [θ] or matrices with entries in          [θ]. The rightmost summand is congruent to 0 (mod 1−θ). Hence,

                     Δ   ⁢           ⁢   S         κη     u   *       ⁡     (     1   -     θ     2     k   *           )         ≡         τ       u   *     ,     k   *         ⁡     (     A   ~     )       ⊕         τ       u   *     ,     k   *         ⁡     (       A   ~     ′     )       ⁢           ⁢       (       mod   ⁢           ⁢   1     -   θ     )     .                 (   15   )               
Both τ u*,k* (Ã) and τ u*,k* (Ã′) are code words in A; hence, their sum has rank at least d over            . By Corollary 2, ΔS is of rank at least d over          , which completes the proof.

   B. Affine Mappings 
   Consider the affine mapping σ:              ν →           ν  given by σ(  x )=τ(  x )+ā, where τ is the linear part of σ and āε           ν  is a constant. For ν=KU, the subvector components of σ are given by σ u (  x )=τ u (  x )+  a u   .
   The following result generalizes Theorem 11.
     Theorem 12 Let A be a maximal M×T rank-d binary code. Let K and U be positive integers. Let κ be a non-zero complex number, θ be a complex primitive 2 K -th root of unity, and η be a non-zero element of 2         [θ]. Let σ:            KU →           KU  be an affine transformation whose linear part is nonsingular.   

   Then the modulated space-time code defined by 
                   S   σ     =     {           S   =       κ   ⁢       ∑     u   =   0               ⁢     U   -   1         ⁢       η             ⁢   u       ⁢   θ   ⁢     (       σ   u     ⁢     (     A   ~     )       )           :                   A   ~     =         (         A   _     0     ,       A   _     1     ,   …   ⁢           ,       A   _       U   -   1         )     ∈       ??   K     ×   …   ×     ??   K         =     ??   KU               }             (   16   )               
achieves transmit diversity d and transmission rate R (KU)(M−d+1) bits per channel use, the maximum possible rate.
 
   Proof: Let S and S′ be distinct code words in S. Then 
                 S   =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢       η   u     ⁢     θ       ∑     k   =   0               ⁢     K   -   1         ⁢       2   k     ⁢       σ     u   ,   k       ⁡     (     A   ~     )                               =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢       η   u     ⁢     θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     (         τ     u   ,   k       ⁡     (     A   ~     )       +     a     u   ,   k       M   ×   T         )                               =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢     [       η   u     ⁢       θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     a     u   ,   k       M   ×   T             ⊙     θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       τ     u   ,   k       ⁡     (     A   ~     )                 ]           ,               
where a u,k    M×T  denotes the constant M×T matrix whose every entry is a u,k . Similarly,
 
             S   ′     =     κ   ⁢       ∑     u   =   0       U   -   1       ⁢       [       η   u     ⁢       θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢     a     u   ,   k       M   ×   T             ⊙     θ       ∑     k   =   0       K   -   1       ⁢       2   k     ⁢       τ     u   ,   k       ⁡     (       A   ~     ′     )                 ]     .               
Letting (u*, k*) denote the lexographically first index pair (u, k) for which σ u,k (Ã)≠σ u,k (Ã′), we have
 
   
     
       
         
           
             
               
                 
                   
                     
                       
                         Δ 
                         ⁢ 
                         
                             
                         
                         ⁢ 
                         S 
                       
                       ⁢ 
                       
                           
                       
                       = 
                       
                         
                           S 
                           - 
                           
                             S 
                             ′ 
                           
                         
                         = 
                         
                           
                             
                               κη 
                               
                                 u 
                                 * 
                               
                             
                             ⁢ 
                             
                               
                                 θ 
                                 R 
                               
                               ⊙ 
                               
                                 θ 
                                 P 
                               
                               ⊙ 
                               
                                 ( 
                                 
                                   
                                     θ 
                                     
                                       
                                         2 
                                         
                                           k 
                                           * 
                                         
                                       
                                       ⁢ 
                                       Q 
                                     
                                   
                                   - 
                                   
                                     θ 
                                     
                                       
                                         2 
                                         
                                           k 
                                           * 
                                         
                                       
                                       ⁢ 
                                       
                                           
                                       
                                       ⁢ 
                                       
                                         Q 
                                         ′ 
                                       
                                     
                                   
                                 
                                 ) 
                               
                             
                           
                           + 
                           
                             
                               κη 
                               
                                 
                                   u 
                                   * 
                                 
                                 + 
                                 1 
                               
                             
                             ⁢ 
                             
                               E 
                               ′ 
                             
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     where 
                   
                   ⁢ 
                   
                     
 
                   
                   ⁢ 
                   
                     
                       R 
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             K 
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             2 
                             i 
                           
                           ⁢ 
                           
                             a 
                             
                               
                                 u 
                                 * 
                               
                               , 
                               i 
                             
                             
                               M 
                               × 
                               T 
                             
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     
                       P 
                       ⁢ 
                       
                           
                       
                       = 
                       
                           
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             
                               k 
                               * 
                             
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             2 
                             i 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               τ 
                               
                                 
                                   u 
                                   * 
                                 
                                 , 
                                 i 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 A 
                                 ~ 
                               
                               ) 
                             
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     
                       Q 
                       ⁢ 
                       
                           
                       
                       = 
                       
                           
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             K 
                             - 
                             
                               k 
                               * 
                             
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             2 
                             i 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             
                               τ 
                               
                                 
                                   u 
                                   * 
                                 
                                 , 
                                 
                                     
                                 
                                 ⁢ 
                                 
                                   
                                     k 
                                     * 
                                   
                                   + 
                                   i 
                                 
                               
                             
                             ⁡ 
                             
                               ( 
                               
                                 A 
                                 ~ 
                               
                               ) 
                             
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         Q 
                         ′ 
                       
                       ⁢ 
                       
                           
                       
                       = 
                       
                           
                       
                       ⁢ 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             K 
                             - 
                             
                               k 
                               * 
                             
                             - 
                             1 
                           
                         
                         ⁢ 
                         
                           
                             2 
                             i 
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             τ 
                             
                               
                                 u 
                                 * 
                               
                               , 
                               
                                 
                                   k 
                                   * 
                                 
                                 + 
                                 i 
                               
                             
                           
                           ⁢ 
                           
                               
                           
                           ⁢ 
                           
                             ( 
                             
                               
                                 A 
                                 ′ 
                               
                               ~ 
                             
                             ) 
                           
                         
                       
                     
                     , 
                     
                       
 
                     
                     ⁢ 
                     
                       
                         and 
                         ⁢ 
                         
                           
 
                         
                         ⁢ 
                         
                           E 
                           ′ 
                         
                       
                       = 
                       
                         
                           ∑ 
                           
                             i 
                             = 
                             0 
                           
                           
                             U 
                             - 
                             
                               u 
                               * 
                             
                             - 
                             2 
                           
                         
                         ⁢ 
                         
                           
                             
                               η 
                               i 
                             
                             ⁡ 
                             
                               [ 
                               
                                 
                                   θ 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         σ 
                                         
                                           
                                             u 
                                             * 
                                           
                                           + 
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           A 
                                           ~ 
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                                 - 
                                 
                                   θ 
                                   ⁡ 
                                   
                                     ( 
                                     
                                       
                                         σ 
                                         
                                           
                                             u 
                                             * 
                                           
                                           + 
                                           i 
                                           + 
                                           1 
                                         
                                       
                                       ⁡ 
                                       
                                         ( 
                                         
                                           
                                             A 
                                             ~ 
                                           
                                           ′ 
                                         
                                         ) 
                                       
                                     
                                     ) 
                                   
                                 
                               
                               ] 
                             
                           
                           . 
                         
                       
                     
                   
                 
                 ⁢ 
                 
                     
                 
               
             
             
               
                 ( 
                 17 
                 ) 
               
             
           
         
       
     
   
   Comparing (17) with (13), we see that the proof of Theorem 12 still applies. 
   C. Non-binary Alphabets 
   The constructions also generalize in a straightforward manner to the case of p K -PAM, p K -PSK, p 2K -QAM, and related constellations, when p≧2 is prime. The underlying algebra is essentially the same. If θ is a complex primitive p ν -th root of unity, then            [θ]/(1−θ)≅           p ; and, for 0≦l&lt;ν,
                   θ       p   ℓ     ⁢   m       -     θ       p   ℓ     ⁢   n           1   -     θ     p   ℓ           ≡       m   _     ⁢     ⊕   p     ⁢       n   _     ⁢           ⁢     (       mod   ⁢           ⁢   1     -   θ     )           ,         
where  m  and  n  denote the modulo p projections of m and n, respectively, and ⊕ p  denotes modulo p addition. Thus, Propositions 1 and 2 extend naturally.
 
   Theorem 12 therefore generalizes to the nonbinary case as follows.
     Theorem 13 Let p≧2 be prime. Let A be a maximal M×T rank-d code over the alphabet            p . Let K and U be positive integers. Let κ be a non-zero complex number, θ be a complex primitive p K -th root of unity, and η be a non-zero element of p         [θ]. Let σ:            p   KU →           p   KU  be an affine transformation whose linear part is nonsingular.   

   Then the modulated space-time code defined by 
                   S   σ     =     {           S   =     κ   ⁢       ∑     u   =   0               ⁢     U   -   1         ⁢       η             ⁢   u       ⁢       θ       ∑     k   =   0       K   -   1       ⁢       p   k     ⁢       σ     u   ,   k       ⁡     (     A   ~     )             :                         A   ~     =         (         A   _     0     ,       A   _     1     ,   …   ⁢           ,       A   _       U   -   1         )     ∈       ??   K     ×   …   ×     ??   K         =     ??   KU               }             (   18   )               
achieves transmit diversity d and transmission rate R=(KU)(M−d+1)log 2 p bits per channel use, the maximum possible rate.
 
   Proof: Straightforward adaptation of the proof of Theorem 12 to the non-binary case. 
   VI. Conclusion 
   We have shown that certain linear and affine transformations can be applied to the algebraic space-time code constructions by Lu and Kumar, while preserving their optimal rate-diversity trade-off property. The use of these transformations amounts to changing the way in which the modulator labels the constellation points. For 2 K -PAM, 2 K -PSK, and 4 K -QAM, the proper choice of transformation yields new algebraic space-time codes that are compatible with Gray labelling. 
   The above-described steps can be implemented using standard well-known programming techniques. The novelty of the above-described embodiment lies not in the specific programming techniques but in the use of the steps described to achieve the described results. Software programming code which embodies the present invention is typically stored in permanent storage. In a client/server environment, such software programming code may be stored with storage associated with a server. The software programming code may be embodied on any of a variety of known media for use with a data processing system, such as a diskette, or hard drive, or CD ROM. The code may be distributed on such media, or may be distributed to users from the memory or storage of one computer system over a network of some type to other computer systems for use by users of such other systems. The techniques and methods for embodying software program code on physical media and/or distributing software code via networks are well known and will not be further discussed herein. 
   It will be understood that each element of the illustrations, and combinations of elements in the illustrations, can be implemented by general and/or special purpose hardware-based systems that perform the specified functions or steps, or by combinations of general and/or special-purpose hardware and computer instructions. 
   These program instructions may be provided to a processor to produce a machine, such that the instructions that execute on the processor create means for implementing the functions specified in the illustrations. The computer program instructions may be executed by a processor to cause a series of operational steps to be performed by the processor to produce a computer-implemented process such that the instructions that execute on the processor provide steps for implementing the functions specified in the illustrations. Accordingly, specification and claims support combinations of means for performing the specified functions, combinations of steps for performing the specified functions, and program instruction means for performing the specified functions. 
   While there has been described herein the principles of the invention, it is to be understood by those skilled in the art that this description is made only by way of example and not as a limitation to the scope of the invention. Accordingly, it is intended by the appended claims, to cover all modifications of the invention which fall within the true spirit and scope of the invention.