IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
where
h = T r HH y : 2
For the case h
> 0 which occurs with probability 1, set
9i = 8hi ;
i = 1; 2; . . . Q:
Then the f9i g form a set of orthonormal matrices and the received matrix can be expressed as
= p t h
si 9i + N: i The optimum receiver would project the received matrix Y onto the ith coordinate, 9i , to detect si , i.e., would compute Y
p
yi := hY; 9i i = t hsi + ni
(25)
where ni := hN; 9i i and use only the projection yi to make a decision regarding symbol si . This explains the simplicity and linear nature of the optimum receiver. It also leads to the following closed-form expression for the symbol-error probability of these codes: 1 1 0 P Q01 2k 1 0 2 k P (s1 ! s2 ) = (26) k 2 4 k=0 where
=
t js1 0 s2 j2 : t js1 0 s2 j2 + 4
2757
[13] M. Ionescu, “New results on space-time code design criteria,” in Proc. IEEE Wireless Communications and Networking Conf., New Orleans, LA, 1999, pp. 684–687. [14] A. R. H. Jr., P. V. Kumar, A. R. Calderbank, N. J. A. Sloane, and P. Solè, “The -linearity of Kerdock, Preparata, Goethals, and related codes,” IEEE Trans. Inform. Theory, vol. 40, pp. 301–319, Mar. 1994. [15] B. L. Hughes, “Differentual space-time modulation,” IEEE Trans. Inform. Theory, vol. 46, pp. 2567–2578, Nov. 2000. [16] H. Jafarkhani and V. Tarokh, “Multiple transmit antenna differential detection from generalized orthogonal designs,” IEEE Trans. Inform. Theory, vol. 47, pp. 2626–2631, Sept. 2001. [17] T. L. Marzetta and B. M. Hochwald, “Capacity of a mobile multiple-antenna communication link in rayleigh flat fading,” IEEE Trans. Inform. Theory, vol. 45, pp. 139–157, Jan. 1999. [18] F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1977. [19] G. Ganesan and P. Stoica, “Space–time block codes: A maximum SNR approach,” IEEE Trans. Inform. Theory, vol. 47, pp. 1650–1656, May 2001. [20] H. F. Lu, “Design and performance of space-time codes,” Ph.D. dissertation, USC., Los Angeles, CA, 2003.
Maximum Rank Distance Codes as Space–Time Codes Paul Lusina, Member, IEEE, Ernst Gabidulin, and Martin Bossert, Senior Member, IEEE
REFERENCES [1] 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. IEEE Vehicular Technology Conf (VTC’96), 2000, pp. 136–140. [2] V. Tarokh, N. Seshadri, and A. R. Calderbank, “Space-time codes for high data rate wireless communi-cation: Performance criterion and code construction,” IEEE Trans. Inform. Theory, vol. 44, pp. 744–765, Mar. 1998. [3] J. W. Craig, “A new, simple and exact result for calculating the probability of error for two-dimensional signal constellations,” in IEEE MILCOM ’91 Conf. Rec., Boston, MA, 1991, pp. 25.5.1–25.5.5. [4] B. M. Hochwald, T. L. Marzetta, and B. Hassibi, “Space-time autocoding,” IEEE Trans. Inform. Theory, vol. 47, pp. 2761–2781, Nov. 2001. [5] B. M. Hochwald and T. L. Marzetta, “Unitary space-time modulation for multiple-antenna communications in rayleigh flat fading,” in IEEE Trans. Inform. Theory, vol. 46, Mar 2000, pp. 543–564. [6] M. K. Simon and M.-S. Alouini, Communication over Fading Channels: A Unified Approach to Performance Analysis. New York: Wiley, 2000. [7] V. Tarokh, H. Jafarkhani, and A. R. Calderbank, “Space-time block codes from orthogonal designs,” IEEE Trans. Inform. Theory, vol. 45, pp. 1456–1467, July 1999. [8] W. H. Sheen and G. L. Stüber, “MLSE equalization and decoding for multipath-fading channels,” IEEE Trans. Commun., vol. 39, pp. 1455–1464, Oct.. [9] M. K. Simon, “Evaluation of average bit error probability for space-time coding based on a simpler exact evaluation of pariwise error probability,” Int. J. Commun. and Networks, vol. 3, no. 3, pp. 257–264, Sept. 2001. [10] M. Brehler and M. Varanasai, “Asymptotic error probability analysis of quadratic receivers in rayleigh fading with applications to the unified analysis of coherent and noncoherent space-time receivers,” IEEE Trans. Inform. Theory, vol. 47, pp. 2383–2399, Sept. 2001. [11] M. Fitz, J. Grimm, and S. Siwamogsatham, “A new view of performance analysis techniques in correlated rayleigh fading,” in Proc. IEEE Wireless Communications and Networking Conf., New Orleans, LA, 1999, pp. 139–144. [12] G. Taricco and E. Biglieri, “Exact pairwise error probability of space-time codes,” IEEE Trans. Inform. Theory, vol. 48, pp. 510–513, Feb. 2002.
Abstract—The critical design criterion for space–time codes in asymptotically good channels is the minimum rank between codeword pairs. Rank codes are a two-dimensional matrix code construction where by the rank is the metric of merit. In the following, we look at the application of rank codes to space–time code design. In particular, we provide construction methods of full-rank codes over different complex signal constellations, for arbitrary numbers of antennas, and codeword periods. We also derive a Singleton-type bound on the rate of a code for the rank metric, and we show that rank codes satisfy this bound with equality. Index Terms—Block codes, diversity, Gaussian integers, multiple-input multiple-output (MIMO) channel, rank codes.
I. CHANNEL MODEL AND DESIGN CRITERIA For the derivation of the space–time code design criteria, we assume a quasi-static optimum interleaved Rayleigh-fading channel with independent and identically distributed spatial paths between transmitter and receiver antennas, and one independent additive white Gaussian noise source per receiver [1]. All symbols arrive at the receiver simultaneously, and there is one received path per transmit antenna. The receiver has perfect channel state information. Ntx and Nrx are the number of transmit and receive antennas, respectively. The power of the system is normalized at the transmitter such that the average signal energy per timeslot is unity. The transmitted codewords Manuscript received November 1, 2002; revised June 17, 2003. This work was supported by DFG Bo 867/10. P. Lusina and M. Bossert are with the Department for Telecommunications and Applied Information Theory (TAIT), University of Ulm, D 89081 Ulm, Germany (e-mail:
[email protected]; martin.bossert@e-technik. uni-ulm.de). E. Gabidulin is with the Department of Radio Engineering, Moscow Institute of Physics and Technology, 141700 Dolgoprudnyi, Russia (e-mail:
[email protected]). Communicated by B. Hassibi, Associate Editor for Communications. Digital Object Identifier 10.1109/TIT.2003.818023
0018-9448/03$17.00 © 2003 IEEE
2758
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
S consist of matrices of size Ntx 2 Nt with symbols from a complex signal constellation A with cardinality q . The rate of a space–time code is given by
Rst =
log2
M
Ntx Nt
where M is the cardinality of the code. Note that this is different than the definition often given in the literature, which is independent of the spatial dimension Ntx . Based on this channel model, Tarokh et al. [1] derived the following design criteria for high signal-to-noise-ratio (SNR) channels. Criterion 1 (Rank Criterion for Diversity Gain): The minimum rank of the matrix j(S 0 S 0 )j2 over all possible codeword pairs defines the space–time code diversity gain. Criterion 2 (Geometric Distance Criterion for Coding Gain): The smallest nonzero product of eigenvalues of the matrix j(S 0 S 0 )j2 over all codeword pairs gives the space–time code coding gain. This value is defined as the geometric distance. Design Criterion 1 can be described as the rank distance metric between codeword pairs. In particular, the function rank1: M ! f0; 1; . . . ; Ntx g defines a norm for a set of matrices M since all the norm axioms are satisfied [2]. Analogous to the Hamming distance metric for vector channel codes, we can also define a maximum bound for the tradeoff between rate and rank distance for matrix codes. This results in the following lemma which is also valid for matrix codes with complex elements. The proof is given in [2]. Lemma (Singleton-Type Bound for Rank Distance [2]): Let C be a code of rank distance dr . Then
Rst
1
r01 0 ddr (max)
log2 q =
1
0 drN0tx 1
log2 q:
A code C is known as maximum rank distance (MRD) if it satisfies the Singleton-type bound with equality. For the case of full-rank MRD codes, the cardinality is M = jCj = q N and the code rate Rst (C ) = N1 log2 q . Conceptually, we see full-rank MRD codes may be interpreted as a type of spatial repetition code. Practically, this means that if any path from the transmitter to the receiver can be correctly recovered, then the entire information sequence can be recovered. Furthermore, we see that according to the temporal definition of rate, full-rank MRD codes are full rate, i.e., they have one information symbol per time slot. We define quadratic MRD codes of size Ntx as component MRD codes. It is evident that the direct sum of component MRD codes is also MRD and has length l 1 Ntx , for l an integer. Extended MRD codes of any length may be constructed using the diresct sum principle combined with the results of the following lemma from [3]. The proof is evident. Lemma 2: Let C be an MRD code of square Ntx 2 Ntx matrices of maximal rank distance Ntx . Then the code C 0 of Ntx 2 Next matrices is constructed by puncturing Ntx 0 Next columns of each Ntx 2 Ntx full-rank MRD codeword C 2 C . This code is MRD with maximal rank distance Next . II. MRD CODE CONSTRUCTION Let M be an Ntx 2 Ntx matrix over the field GF (q ). One can consider column entries as a representation of an element of the extended field GF (q N ) by any basis of over GF (q ). This defines a one-to-one mapping M () m where m is a vector of length Ntx with elements in GF (q N ). The rank of m is defined as the maximal number of coordinates which are linearly independent over the base field GF (q ). Note
that this rank is equal to the rank of matrix M . Therefore, one can construct MRD codes of vectors, and later map them onto matrices. A general construction of a matrix from a vector is as follows. Let g1 ; g2 ; . . . ; gN be linearly independent elements of the field GF (q N ). Let the generator matrix of a finite-field linear code C be defined as follows:
g1
G=
g2
.. .
g3
.. .
.. .
1 1 1 gN .. .
.. .
: q 1 1 1 gN 1 2 3 This code C is MRD with rank distance dr = Ntx 0 k + 1. In particular, the code with maximal distance Ntx is MRD and is defined by the vector (g1 ; g2 ; . . . ; gN ) and all its multiples. A special case for a full-rank MRD code construction is when we define a codeword as c = (1; ; 2 ; . . . ; N 01 ), where is a primitive element of GF (q N ). All elements of this vector are independent over GF (q ), and the code is given by the set of q N vectors C := f0; i 1 c; i = 0 1 1 1 qN 0 2g. The corresponding matrix code can be obtained by replacing the elements of c by their column representation over GF (q ). This special form of rank MRD codes is degq
gq
gq
scribed by the companion matrix given by 0
C=
1
.. .
111
0
.. .
.. .
.. .
0
..
0
.. .
.
0 0 0 111 0 1 0b 0b 0b 1 1 1 0bN 0 0bN 0 0
1
2
2
c = [ ; ; . . . N ]T : irreducible polynomial f (x) determines
1
2
The primitive bi 2 GF (q) and gives the code C
f (x) = xN
coefficients
01 xN 01 + bN 02 xN 02 + (1) 1 1 1 + b1 x + b0 C := f0; C ; C 2 ; . . . ; C q 02C q 01 g: (2) The resulting Ntx 2 Ntx matrices of C define a linear MRD code of cardinality q N with rank distance Ntx . The companion matrix is ac+ bN
tually a matrix representation of a field [4, p. 106]. For this reason, the selection of f (x) will not affect the code properties of the MRD code. The codewords of C may be used to construct systematic MRD codes, as will be shown in Example 2. MRD codes over finite fields cannot be used directly as space–time codes since processing of the received signals is carried out over the signal constellation in the complex field. This also has the consequence that MRD codes over signal constellations are no longer linear. In the following, we present two methods of constructing space–time codes over complex signal constellations. In order to use a finite MRD code as a template for space–time codes, we define a mapping from the set of Galois field elements AGF (q) to the complex field. Let A be a complex signal constellation of size q . Define a one-to-one mapping AGF(q) () A . Next, consider a finite MRD code C of Ntx 2 Ntx matrices with rank distance Ntx generated by (2). We replace every element from GF(q ) by the corresponding element from the constellation A using the defined mapping. This gives the code S with codewords S over the constellation A . For a given finite field, there is no general method known for selecting an arbitrary signal constellation which will guarantee full rank over the infinite complex field. It was proven in [5] that the mapping from GF(2) ! BPSK preserves the rank distribution of a code over the complex field. Further results in [5] and [6] tried to extend this concept to phase-shift keying (PSK) and quadrature amplitude modulation (QAM) constellations, respectively. However, in both cases, subsets of
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
2759
(a)
(b)
Fig. 1. Code performance for selected parameters. (a) Quadrature phase-shift keying (QPSK), 2
codewords must be checked for full rank, and the rank distribution of the code was not preserved. As published in [7], finite-field codes mapped to the Gaussian integer prime numbers field [8], [9] always preserved their rank distribution for any matrix code. A Gaussian integer w is a complex number with integer valuespfor the real and imaginary components w = a +jb; a; b 2 ; j = 01: It is known from number theory that every prime number p of the form p 1 mod 4 can be written as p = (u + jv)(u 0 jv) = u2 + v2 . The number 5 = u + jv is known as a Gaussian prime number where u; v 2 . The mapping from the Galois integer field f0; 1; . . . ; P 0 1g = GF(p) to the set of Gaussian integers f1 ; 2 ; . . . ; p01 g = G5 (p) is given by (1)
(i) = i = i mod 5 = i 0
i53
553 5
(3)
where [1] performs the operation of rounding to the nearest Gaussian number. If we replace all the entries of a finite-field code by unique elements of the Gaussian constellation we will have for the modified code S
det(S i ) 6= 0 mod 5; det(S i 0 S j ) 6= 0 mod 5
and
det(S i ) 6= 0;
det(S i 0 S j ) 6= 0:
Therefore, using Gaussian integer primes, we can construct MRD codes having arbitrary code parameters. Furthermore, the signal constellations for particular Gaussian primes (i.e., p = 5; 13) are similar to QAM constellations, and, therefore, have a good spectral efficiency. Example 1: We design an MRD code with the parameters
((qs )N = ((22 )2 ; Ntx = 2; k = 2; dr = 2). We choose the extension field primitive polynomial to be f (x) = x2 0 x 0 ; 2 GF(22 ). The first codeword in companion matrix form is
C=
0 1 1
:
The primitive polynomial over the extension field GF(22 ) is p(x) = 2 x + x + 1. Then an MRD code C over the field GF(4) is defined by 16 matrices
C = f0; C i mod 4; i = 1; . . . ; 15g; An MRD code is obtained when the GF(4) elements are mapped to the standard 4-PSK constellation.
2 matrix codewords. (b)
(5), 3
3 matrix codewords.
Example 2: We construct a component systematic square Ntx = 3 full-rank MRD space–time code over the extended Galois field GF(p)3 , where p = 5 is a Gaussian integer prime. First, we construct the companion matrix for these parameters based on the primitive extension field polynomial f (x) = x3 + 3x + 2. There are a total of M = 53 = 125 possible matrix codewords. We construct these codewords in systematic form where ~i = [i0 ; i1 ; i2 ]
C= and
0 1 0 0 0 1 3 2 0
C2 =
0 0 1 3 2 0 0 3 2
i1C C (i) = i 1 C 2 i 1 C3
=
C3 =
3 2 0 0 3 2 1 4 3
C 0 (i) C 1 (i) : C 2 (i)
The representation of the Galois field prime number p = 5 as a Gaussian integer prime number for G5 (p) is 5 = u + jv = 2 + j. We may now use the Gaussian integer modulo mapping (3) to convert the codewords from GF(5) ! G2+j (5). The resulting code S has parameters (q s = 53 ; Ntx = 3; k = 3; dr = 3) and is MRD. III. SIMULATION RESULTS For the following simulation results, we consider the channel model presented in Section I and restrict our investigation to Nrx = 1. Fig. 1(a) compares the rank MRD code from Example 1 with the 2 2 2 orthogonal space–time code [10] and the diagonal algebraic space–time (DAST) code design [11] which is optimized for this signal constellation. All codes have a parallel slope indicating the same diversity performance. However, the rank MRD code has a better coding gain than the DAST code. This result is supported by the better minimum geometric distance of the rank MRD code which is 4 as compared to the DAST code value of 3:2. The pairwise distribution of the Euclidean distance between codewords influences the performance at low SNR. This is also better for the rank MRD code over the DAST code as shown in Fig. 2(a). The orthogonal code is slightly better than the rank MRD code. Fig. 1(b) shows the performance comparison of the MRD and DAST codes for the case of Ntx = 3 over the Gaussian prime signal constellation G2+j (5). The DAST code design for Ntx = 3 has not been proven to have full rank in general [11], but the statistical analysis of our example showed that Design Criterion 1 was satisfied. The spreading
2760
IEEE TRANSACTIONS ON INFORMATION THEORY, VOL. 49, NO. 10, OCTOBER 2003
(a) Fig. 2. Code statistics for selected parameters. (a) QPSK, 2
(b) 2 matrix codewords. (b)
matrix for the DAST code was chosen to be a unitary complex orthogonal matrix. There is no quadratic full rate complex orthogonal code design for tx = 3. In the region simulated, the rank MRD code has reached its asymptotic diversity performance, while the DAST code has not. The rank MRD code had a significant coding gain over the DAST code.1 The minimum geometric distance of the MRD code was 1:95 as compared to the DAST code value of 1:08 which supports qualitatively the better rank MRD code performance according to Criterion 2. Fig. 2(b) shows the distribution of the pairwise Euclidean distance between codewords is also better for the rank MRD code construction which confirms theoretically its better performance for low SNR.
N
IV. CONCLUSION In this work, we presented MRD code theory, and applied it to the problems of constructing space–time codes. A bound on the rate with respect to the rank of a code was also given. This bound is similar to the Singleton bound for channel codes. Codes which achieve this bound with equality were termed maximum rank distance (MRD) codes. Rank codes were shown to satisfy the MRD criterion over finite fields, and a simple construction method was given for these codes. The finitefield rank MRD codewords were used as a template for the mapping of elements of GF(q ) to a complex signal constellation of cardinality q . In general, this mapping does not preserve the rank properties of the finite field, however, we showed that for the special case of Gaussian primes the rank metric is always preserved. Simulation performance comparison of rank MRD codes to the DAST code construction showed that the rank MRD codes had a better performance for the parameters investigated. This result was supported by the statistical analysis of both codes which showed that the rank MRD codes have a better geometric distance according to Design Criterion 2. Full rate orthogonal code designs are limited to the case where Ntx = 2, however, for this case the orthogonal code had a marginally better performance than the rank MRD code for the 4-QAM signal constellation. As with most space–time code designs, the rank MRD codes require maximum-likelihood decoding in order to achieve a performance gain. The good algebraic structure, and similarity of rank MRD codes to
1We note that there are several parameters of the DAST code that could be adjusted to affect the performance difference.
(5), 3
3 matrix codewords.
Reed–Solomon codes may offer the potential of developing efficient algebraic decoding algorithms. Furthermore, from the design of rank codes, it is possible to trade off rank distance for Euclidean distance in the code design. This would offer the potential of designing non-MRD codes for low-SNR channels, or of increasing the information rate when the full diversity performance gain is not required. REFERENCES [1] V. Tarohk, H. Seshadri, and A. R. Calderbank, “Space-time codes for high data rate wireless communication: Performance criterion and code construction,” IEEE Trans. Inform. Theory, vol. 44, pp. 744–765, Mar. 1998. [2] E. Gabidulin, “Theory of codes with maximum rank distance,” Probl. Inform. Transm., vol. 21, no. 1, pp. 3–14, 1985. [3] M. Bossert, E. Gabidulin, and P. Lusina, “Space-time codes based on rank matrices,” in Proc. IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000, p. 284. [4] F. MacWilliams and N. Sloane, The Theory of Error Correcting Codes. Amsterdam, The Netherlands: North-Holland, 1993. [5] A. R. Hammons and H. El Gamal, “On the theory of space-time codes for MPSK modulation,” IEEE Trans. Inform. Theory, vol. 46, pp. 524–542, Mar. 2000. [6] Y. Liu, M. P. Fitz, and O. Y. Takeshita, “A rank criterion for qam space-time codes,” IEEE Trans. Inform. Theory, vol. 48, pp. 3062–3079, Dec. 2002. [7] M. Bossert, E. Gabidulin, and P. Lusina, “Space-time codes based on Gaussian integers,” in Proc. IEEE Int. Symp. Information Theory, Lausanne, Switzerland, June 2002, p. 273. [8] M. Bossert, Channel Coding for Telecommunications. Chichester, U.K.: Wiley, 1999. [9] K. Huber, “Codes over Gaussian integers,” IEEE Trans. Inform. Theory, vol. 40, pp. 207–216, Jan. 1994. [10] S. M. Alamouti, “A simple transmit diversity technique for wireless communications,” IEEE J. Select. Areas Commun., vol. 16, pp. 1451–1458, Oct. 1998. [11] M. O. Damen, K. Abed-Meraim, and J. C. Belfiore, “Diagonal algebraic space-time block codes,” IEEE Trans. Inform. Theory., vol. 48, pp. 628–636, Mar. 2002.
