Signal Space Diversity: a power and bandwidth efficient diversity technique for the Rayleigh fading channel

J. Boutros^{∗}, E. Viterbo^{†}

Abstract The increasing need of high data rate transmissions over time or frequency selective fading channels has drawn attention to modulation schemes with high spectral efficiency such as QAM. With the aim of increasing the ‘diversity order’ of the signal set we consider the multidimensional rotated QAM constellations. Very high diversity orders can be achieved and this results in an almost Gaussian performance over the fading channel. This multidimensional modulation scheme is essentially uncoded and enables to trade diversity for system complexity, at no expense of power or bandwidth.

Key Words : QAM Modulation, fading, diversity, number fields, rotation, lattices.

I. Introduction

The rapidly growing need of high data rate transmissions over fading channels has stimulated the interest for AM-PM modulation schemes with high spectral efficiency (or throughput) [1], [2], [3]. The effectiveness of these transmission schemes basically relies on the good error correcting capabilities of a code. The price to pay for this gain is either a bandwidth expansion or an additional transmission power to accommodate the redundant bits.

In this paper we present a different approach. We consider uncoded multidimensional modulation schemes with an intrinsic diversity order, which achieve substantial coding gains over fading channels. The diversity order of a multidimensional signal set is the minimum number of distinct components between any two constellation points. In other words, the diversity order is the minimum Hamming distance between any two coordinate vectors of

∗Ecole Nationale Supérieure des Télécommunications, 46, rue Barrault, 75634 Paris Cedex 13, France

†Politecnico di Torino, C. Duca degli Abruzzi 24, I-10129 Torino, Italy

[figure: (a) 4-PSK; (b) 4-RPSK]

Fig. 1. How to increase diversity: (a) L = 1, (b) L = 2.

constellation points.

To distinguish from other well known types of diversity (time, frequency, space, code) we will talk about modulation diversity or signal space diversity. Throughout the paper we will use, for simplicity, only the term diversity and it will be denoted with the symbol L.

As we will show in the following, the key point to increase the modulation diversity is to apply a certain rotation to a classical signal constellation in such a way that any two points achieve the maximum number of distinct components. Figure 1 illustrates this idea on a 4-PSK. In fact, if we suppose that a deep fade hits only one of the components of the transmitted signal vector, then we can see that the ‘compressed’ constellation in (b) (empty circles) offers more protection against the effects of noise, since no two points collapse together as would happen with (a). A component interleaver/deinterleaver pair is required to assume that the in-phase and quadrature components of the received symbol are affected by independent fading. This simple operation already results in a gain of 8 dB at 10^{−3} over the traditional 4-PSK (see Fig. 11). We will show in this paper, that the increase in the dimensionality of the signal set produces significant gains in a fading channel, over the corresponding non-rotated signal set.

An interesting feature of the rotation operation is that the rotated signal set has exactly the same performance of the non rotated one when used over a pure AWGN channel. The rotated constellation when used over a Ricean fading channel will show a performance between the two extreme cases of Gaussian and Rayleigh fading channel.

We have used the term ‘uncoded’ since we are not adding any type of redundancy to the information bit stream. The information bits are grouped into blocks and directly mapped one-to-one onto the multidimensional constellation points. This means that the coding gain is obtained without spending additional power or bandwidth, but only increasing the complexity of the demodulation operation. In fact, demodulation must now be performed on blocks of consecutive symbols.

The scope of this paper is to analyze in detail all the methods devised to construct high diversity multidimensional QAM constellations carved from a rotated cubic lattice Z^{n}.

Most of the best known lattices for the Gaussian channel have the property of being integral, i.e. subsets of the cubic lattice Z^{n}, so this can be used to obtain convenient labelings. In the case of Rayleigh fading channel, no efficient labeling was found for the optimal lattices given in [4], thus limiting their practical use. The rotated multidimensional QAM constellations presented in this paper can be easily labeled by Gray mapping.

The paper is structured as follows. Sections II and III introduce the system model and review some elementary concepts of algebraic number theory. In Section IV it is proved that for large values of diversity the point error probability over a fading channel approaches the one over an AWGN channel. This property is verified through simulation and for values of modulation diversity larger than 12, the bit error rate curves are within 1-2dB from the corresponding Gaussian curve. Section V presents three different techniques we used to increase the diversity of multidimensional QAM-type signal constellations. Although the most important, diversity is not the only parameter which influences the system performance. It is also important to maximize the minimum product distance between any two points of the signal constellation. This problem is considered in Section VI. Finally we give our results and conclusions in Sections VII and VIII respectively.

II. The multidimensional QAM system

We now describe the system model shown in Figure 2. An n-dimensional QAM constellation is obtained as the Cartesian product of n/2 two-dimensional QAM signal sets. A block of m bits is mapped onto the constellation by applying the Gray mapping in each dimension.

We obtain an overall Gray mapping which results in a one bit change when moving from one constellation point to any one of its nearest neighbors.

Each group of m/n bits uniquely identifies one of the n components of the multidimensional QAM constellation vector u = (u_{1}, … u_{n}), where u_{i} = ±1, ±3, . . .. We will call u the integer component vector. We denote by η the system throughput measured as the number of bits per symbol (two dimensions), so we have m = ηn/2. In the case of odd dimension, one of the symbols should be split between two successive points. The total number of points in this cubic shaped constellations is 2^{m} and the average energy per bit is simply E_{b} = (2^{η} − 1)/3η.

We can view this constellation as carved from a translated and scaled (enlarged by a factor 2) version of the n-dimensional cubic lattice Z^{n}. In the following, for simplicity, we will consider only the constellations carved form Z^{n}, so that u_{i} = 0, ±1, ±2, . . .. By simple scaling and translation it is possible to revert to the multidimensional QAM constellation.

The point x of the rotated constellation is obtained by applying the rotation matrix M to u. The set of all points {x = uM, u ∈ Z^{n}} belongs to the n-dimensional cubic lattice Z_{n,L} with generator matrix M and diversity L. The two lattices Z^{n} and Z_{n,L} are equivalent in the sense of Section V-A, but exhibit a different modulation diversity. In the following we will identify the lattice with the corresponding finite constellation carved from the lattice.

The channel is modeled as an independent Rayleigh fading channel, separately operating on each component. Perfect phase recovery and CSI are assumed at the receiver. We also assume that the system is unaffected by inter-symbol interference.

To satisfy the assumption of independence we need to introduce a component interleaver which destroys the correlation among the in-phase and quadrature channel fading coefficients. It should be evident that the component interleaving is the key point in obtaining any gain in the example of Figure 1. An undesirable effect of the component interleaver is the fact that it produces non constant envelope transmitted signals [8].

As a result of the above assumptions we will write the received vector as r = α ⊙ x + n, where n = (n_{1}, n_{2}, … n_{n}) is a noise vector, whose real components n_{i} are zero mean, N_{0} variance Gaussian distributed independent random variables, α = (α_{1}, α_{2}, … α_{n}) are the Info Bits Gray Mapping

u Rotation ; M x

Component Interleaver

⊙ [figure]

α

+

[figure]

n

Component Deinterleaver

r

ML Detection x̂, û α

Fig. 2. System model

random fading coefficients with unit second moment and ⊙ represents the component-wise product. Signal demodulation is assumed to be coherent, so that the fading coefficients can be modeled after phase elimination, as real random variables with a Rayleigh distribution and unit second moment (E[α_{i}^{2}] = 1). The independence of the fading samples represents the situation where the components of the transmitted points are perfectly interleaved.

After de-interleaving the components of the received points, the maximum likelihood (ML) detection criterium with perfect CSI imposes the minimization of the following metric

m(x|r, α) = ∑_{i=1}^{n} |r_{i} − α_{i}x_{i}|^{2}  (1)

Using this criterium we obtain the decoded point x̂ and the corresponding integer component vector û from which the decoded bits can be extracted.

The minimization of (1) can be a very complex operation for an arbitrary signal set with a large number of points. It is shown in [7] how to apply the Universal lattice decoder [6] to obtain a more efficient ML detection of lattice constellations in fading channels.

In [4], using the Chernoff bounding technique, we have shown that the point error probability of a multidimensional signal set is essentially dominated by four factors. To improve performance it is necessary to

1. Minimize the average energy per constellation point.

2. Maximize the diversity L.

3. Maximize the minimum L-product distance

d_{p,min}^{(L)} = ∏_{x_{i}≠y_{i}}^{(L)} |x_{i} − y_{i}|

between any two points x and y in the constellation.

4. Minimize the product kissing number τ_{p} for the L-product distance i.e., the total number of points at the minimum L-product distance.

In this paper we have fixed the average energy of the constellations so we concentrate on the remaining items.

III. Algebraic number theory

The idea of rotating a two-dimensional QAM constellation was first presented in [10]. It was found that for a 16-QAM a rotation angle of π/8 gave a diversity of 2. The effect of this rotation is to spread the information contained in each component over both components of the constellation points. Pursuing a similar approach, the optimization of a four-dimensional rotation is found in [8]. The approach to determine such rotations is direct and can not be easily extended to multidimensional constellations.

A more sophisticated mathematical tool is needed to construct lattice multidimensional constellations with high diversity: algebraic number theory. A simple introduction to this theory is given in [4] together with a review of the known lattice constellations obtained from the canonical embedding of real and complex algebraic number fields.

Here we will briefly highlight some of the mathematical concepts in algebraic number theory, nevertheless we recommend some further readings on this topic [13], [14], [15].

An algebraic number field K = Q(θ) is the set of all possible algebraic combinations (+, −, ∗, /) of an algebraic number θ (real or complex, irrational and non transcendental) with the rational numbers of Q. This set has all the field properties and is related to an irreducible polynomial over Q, called the minimal polynomial, having θ as a root.

From elementary calculus we know that Q is dense in R, the set of real numbers. Then we could state that the set K is ‘a little bit denser’ in R if K is a real field, and ‘a little bit denser’ in C if K is a complex field.^{3} Using a particular mapping, called the canonical embedding, it is possible to uniquely represent each element of an algebraic number field with a point in an n-dimensional Euclidean space R^{n} just like we represent the elements of Q on the real line R. This set of points is now only ‘dense’ in R^{n} as Q was ‘dense’ in R. In fact we chose n so as to satisfy this condition. n is called the degree of the algebraic number field.

The parallel between Q and K can be further extended. In fact, within Q we find the set of relative integers Z which can be represented as a one dimensional lattice Z in R. In K there exists a subset O_{K}, called the ring of integers or integer ring of K, which is mapped by the canonical embedding to an n-dimensional lattice, i.e. a discrete group of R^{n}.

Finally, an ideal of Z can be viewed as a sub-lattice of Z, similarly an ideal of the ring of integers O_{K} is mapped by the canonical embedding into a sub-lattice of the lattice produced by O_{K}.

The interest in these lattices lies in the fact that they present a diversity which can be easily controlled by properly selecting the algebraic number field. A key result in [4] shows that it is possible to design lattice constellations with diversity ranging between n/2 and n according to the number of real (r_{1}) and complex (2r_{2}) roots of the minimal polynomial of the number field. In particular it is proven that L = r_{1} + r_{2}. It is then shown that only for L = n, the d_{p,min} is related to the particular field properties of K.

IV. Converting the Rayleigh fading channel into a Gaussian channel In this section, we show that the multidimensional QAM constellation becomes insensitive

to fading when the diversity L is large. This means that the point error probability is the same with or without fading. We focus the proof on the analysis of the pairwise point error probability P (x → y), which is the probability of the received point r to be closer to y than to x, assuming that x is transmitted. The detector selects y if m(x|r, α) ≤ m(y, r, α) and the conditional pairwise error probability is given by

P (x → y|α) = P (∑_{i=1}^{n} |r_{i} − α_{i}y_{i}|^{2} ≤ ∑_{i=1}^{n} |r_{i} − α_{i}x_{i}|^{2}) = P (X ≥ A)

3We note that this intuitive idea is mathematically unprecise since K has the same density of Q in R.

where X = ∑_{i=1}^{n} α_{i}(x_{i} − y_{i})n_{i} is a Gaussian random variable and A = \frac{1}{2} ∑_{i=1}^{n} α_{i}^{2}(x_{i} − y_{i})^{2} is a constant. The mean of X is zero and its variance is σ_{X}^{2} = 2N_{0}A. The conditional pairwise error probability can be written as P (x → y|α) = Q(A/σ_{X}) and we obtain

P (x → y|α) = Q (\sqrt{\frac{∑_{i=1}^{n} α_{i}^{2}(x_{i} − y_{i})^{2}}{4N_{0}}} )  (2)

We recall that the Gaussian tail function is defined as Q(x) = (2π)^{−1/2} ∫_{x}^{∞} exp(−t^{2}/2)dt. The pairwise error probability P (x → y) is obtained by averaging over the fadings α_{i},

P (x → y) = ∫ P (x → y|α)f(α)dα

where f(α) is the probability density function (p.d.f.) of the fading coefficients. The Hamming distance between x and y is at least L, since L is the modulation diversity of the constellation. For simplicity of notations and without loss of generality, we assume that |x_{i} − y_{i}| = 1 for the first L components and |x_{i} − y_{i}| = 0 for the other n − L components. The conditional pairwise error probability given by (2) becomes

P (x → y|α) = Q (\sqrt{\frac{∑_{i=1}^{L} α_{i}^{2}}{4N_{0}}} ) .  (3)

On a Gaussian channel, expression (3) simplifies to

P (x → y) = Q (\sqrt{\frac{L}{4N_{0}}} ) = Q (\frac{d_{E}(x, y)}{2σ})  (4)

where d_{E}^{2}(x, y) = L is the squared Euclidean distance between x and y and σ^{2} = N_{0} is the noise variance.

At first sight, one can say that ∑_{i=1}^{L} α_{i}^{2} acts as E[∑_{i=1}^{L} α_{i}^{2}] = L when L goes to infinity. This is the weak law of large numbers. It states that ∑_{i=1}^{L} α_{i}^{2}/L converges to 1 since the variance of the sum tends to zero. The probability that the difference is larger than a threshold in absolute value is small. The convergence is very weak and can be proved using the Chebychev inequality. It shows, roughly and intuitively, that (3) approaches (4) and thus the fading has no effect when L is very large.

The above discussion does not constitute a rigorous proof. The exact proof is found when applying the strong law of large numbers (convergence in the sense of probability laws), as done below.

First, let us rewrite the conditional pairwise error probability as

P (x → y|α) = Q (\sqrt{\frac{L(1 + Y)}{4N_{0}}} )  (5)

where Y = ^{\frac{∑_{i=1}^{L}(α_{i}^{2}−1)}{L}} = ∑_{i=1}^{L} Y_{i}. The random variables Y_{i} = (α_{i}^{2} − 1)/L have a central χ^{2} distribution [12] with 2 degrees of freedom, because α_{i}^{2} = a_{i}^{2} + b_{i}^{2} where a_{i} and b_{i} are two statistically independent and identically distributed Gaussian variables with zero mean and variance 1/2. The mean and the variance of Y_{i} are respectively E[Y_{i}] = 0 and E[Y_{i}^{2}] = 1/L^{2}. As a consequence of the statistical independence of the Y_{i}, their sum Y is a χ^{2} random variable with 2L degrees of freedom. Its mean and variance are respectively E[Y] = 0 and E[Y^{2}] = 1/L. The p.d.f. of Y is given by

f_{Y} (y) = \frac{L^{L}}{(L − 1)!}(y + 1)^{L−1}exp(−L(y + 1)),  y ≥ −1  (6)

Figure 3 shows the p.d.f. for L = 2, 4, 8, 12, 16 and 32. Clearly, we see that f_{Y} (y) tends to a Dirac impulse δ(y) when L goes to infinity. More precisely, it is easy to show that ∫_{−∞}^{∞} f_{Y} (y)g(y)dy → g(0) when L → ∞, for any function g of the class C^{∞}(−∞, ∞). From the definition of the Dirac distribution we can say that f_{Y} (y) → δ(y). Hence, the pairwise error probability

P (x → y) = ∫ Q (\sqrt{\frac{L(1 + Y)}{4N_{0}}} ) f_{Y} (y)dy

approaches the pairwise error probability of the Gaussian channel Q(\sqrt{\frac{L}{4N_{0}}} ).

An exact expression of P (x → y) can also be obtained by combining expressions (5) and (6). and directly computing the above integral. This yields P (x → y) as a function of the signal-to-noise ratio SNR = L/N_{0},

P (x → y) = (\frac{1 − μ}{2})^{L} × ∑_{k=0}^{L−1} ( \begin{matrix}L + k − 1 \\ k \end{matrix} ) (\frac{1 + μ}{2})^{k}  (7)

Fig. 3. Probability density function of Y

where μ is given by

μ = \sqrt{\frac{\frac{SNR}{8L}}{1 + \frac{SNR}{8L}}}

The pairwise error probability of (7) is plotted in Figure 4 for diversities L = 1, 4, 12 and 32 on the Rayleigh fading channel. We also plotted in Figure 4 the pairwise error probability of (4) on the additive white Gaussian noise channel (AWGN). Practically, the fading effect is reduced when diversity is larger or equal to 12, as shown by Figure 4 and confirmed by the simulation results in Section VII.

V. Rotating the integer lattice Z^{n}

This section collects the three techniques we have investigated to obtain a rotated multidimensional cubic lattice Z^{n} with high diversity. Following the notations of [4] we denote with Λ_{n,L} an n-dimensional lattice with diversity L.

Fig. 4. Pairwise error probability

We observe that the generator matrix M of the rotated lattice Z^{n} is actually a rotation matrix which transforms all the integer component vectors into a set of vectors with the required diversity.

The rotated cubic lattice constellation can be either used as an uncoded multidimensional modulation scheme or as a base modulation for further coding techniques. For example, we could apply these rotations to any known coding scheme based on QAM modulations to obtain the benefits of diversity together with the coding gain.

A. Construction of rotated Z^{n} lattices from known rotated integral lattices

In [4] the rotated versions of the lattices D_{4}, E_{6}, E_{8}, K_{12}, Λ_{16}, Λ_{24} are found for L equal to half the dimension. Since D_{4}, E_{6}, E_{8}, K_{12}, Λ_{16}, Λ_{24} are integral lattices (i.e., sub-lattices of Z^{n}) we expected to find the under-laying rotated Z^{n} lattice with the same diversity. In this section we will briefly discuss this problem.

We say that two lattices Λ_{1} and Λ_{2} are equivalent if they are equal up to a rotation and a scaling factor. The generator matrices M_{1} and M_{2} of two equivalent lattices are related by

M_{2} = αBM_{1}R  (8)

where α is the scaling factor, R is the rotation matrix (det(R) = ±1) and B is a lattice basis transformation matrix i.e., an integer matrix with det(B) = ±1. The matrix B is also known as an integer unimodular matrix.

Let us denote any one of the non rotated lattices D_{4}, E_{6}, E_{8}, K_{12}, Λ_{16}, Λ_{24} with Λ_{n,1} since it has diversity L = 1 and with Λ_{n,n/2} the corresponding rotated lattice with diversity L = n/2. The two lattices Λ_{n,1} and Λ_{n,n/2}, defined by the generator matrices M_{1} and M_{2}, are equivalent. If we determine the scaling factor α and the matrix B then we are able to obtain the desired rotation matrix R from (8).

Taking the absolute value of the determinant of both sides of (8) we obtain

α = (\frac{| det M_{2}|}{| det M_{1}|})^{1/n} .

Without loss of generality we can replace M_{2} by α^{−1}M_{2} and concentrate on finding B. Let us consider the Gram matrices G_{1} = M_{1}M_{1}^{T} and G_{2} = M_{2}M_{2}^{T}. Since M_{2} = RM_{1}B we have G_{2} = BG_{1}B^{T}. Instead of finding B we search directly for a generator matrix M_{1} of the non rotated lattice which results in G_{2} = G_{1} = M_{1}M_{1}^{T}, implying that B is the identity matrix.

The Gram matrix G_{2} is symmetric and its elements g_{ij} are the scalar products ⟨v_{i}, v_{j}⟩ of the lattice basis vectors corresponding to the rows of M_{1}. The diagonal elements g_{ii} correspond to the square norms of the basis vectors. The problem is then to determine the generator matrix M_{1} such that the lattice basis vectors satisfy the conditions on the scalar products imposed by G_{2}. By computer search we were able to find the generator matrices M_{1} and the desired rotation matrices R = M_{2}M_{1}^{−1}.

B. Algebraic construction of Z_{n,n/2} lattices

In this section we construct a family of orthogonal matrices with diversity L = n/2 for n = 2^{e_{1}}3^{e_{2}}, e_{1}, e_{2} = 0, 1, 2, … applying the canonical embedding to some totally complex cyclotomic number fields. For the mathematical details about algebraic number fields and the canonical embedding the reader can refer to [4].

The key points used in this section to find Z_{n,n/2} are the following :

• The vectors of the lattice basis are orthogonal.

• The minimal polynomial μ_{θ}(x) has integer coefficients.

• The minimal polynomial μ_{θ}(x) has n distinct complex roots.

• The lattice dimension is n = Φ(N)/2, where Φ(·) is the Euler function giving the number of integers prime with N [14].

Let us consider the cyclotomic field K = Q[j](θ), where θ = e^{2πj/N} is an N-th root of unity. K is an algebraic extension of Q[j] = {a + jb|a, b ∈ Q} of degree Φ(N)/2. We recall that this is a totally complex field with signature (r_{1} = 0, r_{2} = n/2) and minimal polynomial

μ_{θ}(x) = ∏_{(k,N)=1}(x − θ^{k})  (9)

where (k, N) is the greatest common divisor of k and N. The minimal polynomial over Z[j] is denoted by m(x) and defined later in this section.

Let us denote θ_{1} = θ, θ_{2}, … θ_{n/2} the complex roots of μ_{θ}(x) which define the n/2 distinct field Q-homomorphisms

σ_{1}(θ) = θ_{1}, σ_{2}(θ) = θ_{2}, … σ_{n/2}(θ) = θ_{n/2} .  (10)

To construct a complex lattice Λ of dimension n/2 we apply the canonical embedding to the ring of integers O_{K} = Z[j](θ) generated by (1, θ, θ^{2}, … θ^{n/2−1}). Its generator matrix is given by

M = ( \begin{matrix}1 & 1 & … & 1 \\ θ_{1} & θ_{2} & … & θ_{n/2} \\ ⋮ & ⋮ & & ⋮ \\ θ_{1}^{n/2−1} & θ_{2}^{n/2−1} & … & θ_{n/2}^{n/2−1} \end{matrix} ) = ( v_{1} ; v_{2} ; ⋮ ; v_{n/2} )  (11)

where the complex lattice basis vectors v_{i}, i = 1, 2, … n/2, correspond to the rows of M.

The corresponding real lattice of dimension n can be obtained by replacing each complex entry a + jb of M by a 2 × 2 matrix ( \begin{matrix}a & −b \\ b & a \end{matrix} ) . As proven in [4] this lattice has diversity

L = n/2 = r_{2}.

We are interested in selecting the roots θ_{i}, i = 1, 2, … n/2, or equivalently their minimal polynomial μ_{θ}(x), so that M becomes an orthogonal matrix i.e., a generator matrix for the complex integer lattice in dimension n/2. The orthogonality among the complex vectors implies the orthogonality among the corresponding real vectors. The complex inner product of any two rows v_{p+1} = (θ_{1}^{p}, θ_{2}^{p}, … θ_{n/2}^{p}) and v_{q+1} = (θ_{1}^{q}, θ_{2}^{q}, … θ_{n/2}^{q}), p, q = 0, 1, … n/2 − 1 of M must satisfy

⟨v_{p+1}, v_{q+1}⟩ = ∑_{k=1}^{n/2}(θ_{k})^{p}(θ_{k}^{∗})^{q} = \{ \begin{matrix}1 & p = q \\ 0 & p ≠ q \end{matrix}  (12)

For p > q, we have

⟨v_{p+1}, v_{q+1}⟩ = ∑_{k=1}^{n/2}(θ_{k}θ_{k}^{∗})^{q}(θ_{k})^{p−q} = ∑_{k=1}^{n/2} ∥θ_{k}∥^{q}(θ_{k})^{p−q} = 0  (13)

and since the complex roots θ_{i} are placed on the unit circle ∥θ_{k}∥ = 1

⟨v_{p+1}, v_{q+1}⟩ = ∑_{k=1}^{n/2}(θ_{k})^{m} = S_{m} = 0  m = 1, 2, , … n/2 − 1  (14)

In other words, the first n/2−1 power symmetric functions S_{m} of the roots of μ_{θ}(x) are null. The polynomial μ_{θ}(x), which we want to determine, can be factored into m(x)m^{∗}(x), where we assume that θ_{i}, i = 1, 2, … n/2 are the roots of the polynomial m(x) of degree n/2 over the ring of Gaussian integers Z[j], while m^{∗}(x) takes on the complex conjugate roots.

Applying Newton’s identities one easily observes that m(x) = (x − θ_{1}) ⋯ (x − θ_{n/2}) = x^{n/2} + P and m^{∗}(x) = x^{n/2} + P^{∗} so that

μ_{θ}(x) = x^{n} + (P + P^{∗})x^{n/2} + 1 .  (15)

Now that we have the general form of the minimal polynomial we still need to determine which of the n roots of unity must be chosen to apply the canonical embedding (11).

Let θ_{i} = e^{jϕ_{i}}, i = 1, 2, … n/2 be the unknown roots of m(x) which we want to determine. P is the product of the n/2 roots laying on the unit circle

P = e^{jψ}  − π ≤ ψ < π  (16)

thus

m(θ_{i}) = e^{jϕ_{i}n/2} + e^{jψ} = 0  (17)

and we obtain exactly n/2 distinct values of θ_{i} with

ϕ_{i} = 2\frac{ψ + π}{n} + \frac{4π(i − 1)}{n}  i = 1, 2, … n/2  (18)

Similarly, for the roots θ_{i+n/2} = e^{jϕ_{i+n/2}} of m^{∗}(x) satisfy

ϕ_{i+n/2} = 2\frac{π − ψ}{n} + \frac{4π(i − 1)}{n}  i = 1, 2, … n/2  (19)

In order to determine the value of ψ we consider the following conditions

• μ_{θ}(x) has exactly n distinct roots, so the roots of m(x) must be different from the roots

of m^{∗}(x)

2\frac{π + ψ}{n} ≠ 2\frac{π − ψ}{n} ⇒ ψ ≠ 0  (20)

• μ_{θ}(x) has only complex roots, so

ϕ_{i}, ϕ_{i+n/2} ≠ kπ ⇒ 2πi + π ± ψ ≠ \frac{n}{2}kπ ⇒ ψ ≠ 0  (21)

• μ_{θ}(x) has integer coefficients

P + P^{∗} = e^{jψ} + e^{−jψ} = 2 cos ψ ∈ Z  (22)

which implies ψ = ±π/3, ±π/2, ±2π/3.

The possible values for the roots of m(x) are summarized in Table I, where only the negative values of ψ were considered since the positive ones correspond to the roots of m^{∗}(x). The third column (the value of N) is derived from the second one by noting that ϕ_{1} = 2π/N since by definition θ = e^{2πj/N} = θ_{1} = e^{jϕ_{1}}.

\begin{matrix}ψ & ϕ_{i} = 2\frac{ψ+π}{n} + \frac{4π(i−1)}{n} & N \\ − \frac{π}{3} & \frac{4π}{3n} + \frac{4π(i−1)}{n} & \frac{3n}{2} \\ − \frac{π}{2} & \frac{π}{n} + \frac{4π(i−1)}{n} & 2n \\ − \frac{2π}{3} & \frac{2π}{3n} + \frac{4π(i−1)}{n} & 3n \end{matrix}

TABLE I The admissible values for the roots are θ_{i} = e^{jϕ_{i}}, i = 1, … n/2

Finally, we must solve Φ(N) = n for N = 3n/2, 2n, 3n, to obtain the admissible values of the dimension n of the real lattice. Equivalently we can solve Φ(N)/N = 1/K where N = Kn for K = 2, 3, 3/2. We recall that Φ(N)/N must have the largest prime dividing N as a factor in the denominator. Then for the above Ks the largest prime in N is at most 3 and we can write N = 2^{e_{1}}3^{e_{2}} for some e_{1}, e_{2} = 0, 1, 2, . . .. We distinguish the three cases: N = 3n/2 — Let N = 2^{e_{1}}3^{e_{2}} with e_{1} = 0, 1, 2, …, e_{2} = 1, 2, …, then Φ(3n/2) = n has no solutions. N = 2n — In this case the largest prime dividing N is at most 2, so that N = 2^{e_{1}} with e_{1} = 1, 2, …, then Φ(2n) = n has solutions for n = 2^{e_{1}}. N = 3n — Let N = 2^{e_{1}}3^{e_{2}} with e_{1} = 0, 1, 2, …, e_{2} = 1, 2, …, then Φ(3n) = n has solutions for n = 2^{e_{1}}3^{e_{2}}. We can conclude that the admissible values of ψ are −π/2 and −2π/3. They correspond to the polynomials of the type x^{n} + ϵx^{n/2} + 1 with ϵ = 0 or −1 and with N = 2n and 3n respectively. Thus, there exist Z_{n,n/2} lattices for all dimensions n = 2^{e_{1}}3^{e_{2}}, with e_{1} = 1, 2, … and e_{2} = 0, 1, 2, . . ..

C. Algebraic construction of Z_{n,n} lattices

This construction is based on the totally real algebraic number field Q(2 cos(2π/N)). By applying the canonical embedding to a particular ideal in this field we found the rotated cubic lattice Z_{n,n}. Since Q(2 cos(2π/N)) is a totally real field we know from [4] that the constellation has full diversity L = n. The choice of this family of number fields appears to be arbitrary but in the following section we will show that some of these rotated cubic lattices also maximize the product distance of the constellation.

We now describe the procedure we used to obtain Z_{n,n}. We know that the degree of Q(2 cos(2π/N)) is Φ(N)/2. This imposes some limitations on the lattice dimensions we can obtain (n = Φ(N)/2). All the even dimensions up to 32 do not lead to the desired integer lattice while the odd ones in Table II do. The procedure is the following:

1. Consider the number field K = Q(2 cos(2π/N)) with minimal polynomial μ_{θ}(x) (see Appendix A) and absolute discriminant d_{K}.

2. Let d_{K} = p^{m} be the prime factorization of the absolute discriminant.

3. Factor the principal ideal (p) into I^{n}, where I is a prime ideal.

4. For k = 0, … n apply the canonical embedding to the ideal I^{k} and check if the generator matrix is orthogonal i.e., the generator matrix of Z_{n,n}.

The last column of Table II gives the power of the ideal I which produces the full diversity Z_{n,n} lattice. The lattice is given by Z_{n,n} = σ(I^{k}), where σ is the canonical embedding defined by the n real roots of μ_{θ}(x). The fundamental volume of Z_{n,n} can be related to d_{K} and the algebraic norm N(I^{k}) = p^{k} by [4]

vol(Z_{n,n}) = N(I^{k}) ∗ \sqrt{|d_{K}|} .

If we introduce a scaling factor α = (p^{k} ∗ \sqrt{|d_{K}|})^{1/n}, we obtain the unit volume cubic lattice.

As an example, the full diversity cubic lattice Z_{5,5} is found from the field Q(2 cos(2π/11)). The absolute discriminant is d_{K} = 11^{4} and Z_{5,5} = σ(I^{3}). The prime ideal I is computed by factoring the principal ideal generated by 11: (11) = (11, θ + 2)^{5} and I = 11O_{K} + (θ + 2)O_{K}.

VI. Maximizing the product distance

In the previous section we have shown how to obtain rotated Z^{n} lattices which guarantee a certain degree of diversity. Although diversity appears to be the most relevant design parameter we are also interested in maximizing the minimal product distance d_{P,min} between

n N  μ_{θ}(x)  d_{K} k
3 7, 14  x^{3} + x^{2} − 2x − 1  7^{2} 2
9, 18  x^{3} − 3x + 1  3^{4} 1
5 11, 22  x^{5} + x^{4} − 4x^{3} − 3x^{2} + 3x + 1  11^{4} 3
9 19, 38  x^{9} + x^{8} − 8x^{7} − 7x^{6} + 21x^{5}
+15x^{4} − 20x^{3} − 10x^{2} + 5x + 1  19^{8} 5
11 23, 46 x^{11} + x^{10} − 10x^{9} − 9x^{8} + 36x^{7} + 28x^{6} 23^{10} 6
−56x^{5} − 35x^{4} + 35x^{3} + 15x^{2} − 6x − 1
15 31, 62 x^{15} + x^{14} − 14x^{13} − 13x^{12} + 78x^{11} + 66x^{10}− 31^{14} 8
220x^{9} − 165x^{8} + 330x^{7} + 210x^{6} − 252x^{5}−
126x^{4} + 84x^{3} + 28x^{2} − 8x − 1

TABLE II Full diversity Z_{n,n} lattices from ideals of the Q(2 cos(2π/N)).

any two points of the constellation. In this section we show a construction of Z_{n,n} lattices for some even n which aims at maximizing d_{P,min}.

Stating the problem in the the most general form, we need to determine an arbitrary rotation matrix, with the highest possible diversity order (L = n), which maximizes d_{P,min} of the corresponding signal constellation. This optimization problem becomes rapidly intractable due to the number of variables and the complexity of the constraints. For this reason we restrict our search to a smaller family of rotation matrices which can be parameterized with a reduced number of variables and result in simpler constraints.

We start with dimensions 2 and 3 and then move up to other dimensions of the type 2^{e_{1}}3^{e_{2}} applying a construction which recalls the one used for Hadamard matrices.

It is important to remind that whenever we are dealing with lattices generated by canonical embedding of totally real number fields d_{P,min} is related to the field norm and is independent of the size of the finite constellation carved from the lattice [4]. In all other cases this is not

Fig. 5. d_{P,min} for a family of Z_{2,2} lattices

necessarily true.

In the following d_{P,min}-optimizing construction we limited the size of the constellations to the case of η = 4 bits/symbol. In all cases (except for the three-dimensional one, where it is proven to be true) we verified experimentally that d_{P,min} does not depend on the size of the constellation. We conjecture that in all these cases we are dealing with some lower dimensional sections of a lattice generated by canonical embedding of totally real number fields of higher degree.

A. Dimension 2 All two-dimensional orthogonal matrices have the following structure

M = ( \begin{matrix}a & b \\ −b & a \end{matrix} )

with the constraint a^{2} + b^{2} = 1.

We parameterize this orthogonal matrix as a function of the single variable λ as follows

a = 1/\sqrt{1 + λ^{2}} b = λa .

Note that the rows of M are the normalized orthogonal lattice basis vectors. Figure 5 shows the values of d_{P,min} as a function of λ for a finite constellation (η = 4 bits/symbol), carved from the lattice generated by M. Only positive values of λ were considered due to the symmetry about the origin and the values of λ resulting in L = 1 diversity constellation were skipped. d_{P,min} was computed by exhaustive search through the points of the finite constellation using a small step for λ (e.g. 0.005). In the same figure we also plot the following upper bounds to d_{P,min} (functions of λ)

d_{P,min} ≤ \{ \begin{matrix}|a b| & (1, 0) \\ |a^{2} − b^{2}| & (1, 1) \\ |(2a − b)(a + 2b)| & (2, 1) \\ |(a − 2b)(2a + b)| & (1, 2) \end{matrix}  (23)

corresponding to the product distances between the origin and the points with the integer components reported in the second column of (23). The curve of d_{P,min} could, in principle, be obtained as the minimum of all the bounds of the type (23) for all the points of the constellation.

In Figure 5 we observe that the highest peaks are found at the intersection of the first and second bound in (23) that is for

λ_{o,2} = \frac{1 ± \sqrt{5}}{2}  d_{P,min}^{o,2} = \frac{\sqrt{5}}{5} < 0.5 .  (24)

The upper bound of 0.5 to d_{P,min} is obtained by assuming that there exists a constellation containing a unit norm vector with all equal components.

A few considerations about the optimal matrix are appropriate here. λ_{o,2} is the root of the polynomial λ^{2} + λ − 1 i.e., it belongs to a totally real number field of degree 2. The entries a and b of M then belong to a number field of degree 4. In this case we are not using the canonical embedding lattice but probably some two-dimensional section of it, which gives us a Z^{2} lattice constellation with diversity L = 2 and maximal d_{P,min}. The two dimensional case is the only one where we have obtained the absolute maximum d_{P,min} among all possible rotation matrices.

B. Dimension 3 The family of three-dimensional orthogonal matrices we consider here is

M = ( \begin{matrix}a & b & c \\ b & c & a \\ −c & −a & −b \end{matrix} )

with the constraints a^{2} + b^{2} + c^{2} = 1 and ab + bc + ac = 0.

We parameterize this orthogonal matrix as a function of the single variable λ as follows

a = \frac{1 + λ}{1 + λ + λ^{2}} b = λa c = \frac{−λ}{1 + λ}a .  (25)

As before the rows of M form the orthonormal lattice basis vectors of a rotated version of Z^{3}.

Figure 6 shows the values of d_{P,min} as a function of λ, for a finite constellation with η = 4 bits/symbol, carved from the lattice generated by M. d_{P,min} was computed by exhaustive search through the points of the finite constellation for each value of λ. In this case the values of λ were taken in the range (−4, 4) since the d_{P,min} rapidly vanishes outside this interval. The values of λ resulting in diversity less than 3 were skipped. In Figure 6 we also plot the following upper bounds to d_{P,min}

d_{P,min} ≤ \{ \begin{matrix}|a b c| & (1, 0, 0) \\ |(a − b)(b − c)(c − a)| & (1, 0, 1) \\ |(a + b − c)(b + c − a)(c + a − b)| & (1, 1, 1) \end{matrix}  (26)

corresponding to the product distances between the origin and the points with the integer components reported in the second column of (26).

Fig. 6. d_{P,min} for a family of Z_{3,3} lattices

In Figure 6, we identify the highest peaks at the intersection of the first and second bound in (26), that is at the roots of the polynomials

p_{1}(λ) = λ^{3} + 2λ^{2} − λ − 1
p_{2}(λ) = λ^{3} + λ^{2} − 2λ − 1 .

Surprisingly, these two polynomials happen to be equivalent minimal polynomials of the totally real algebraic number field Q(2 cos(2π/7)). The values λ_{o,3} of the roots of the above polynomials have the simple expressions:

p_{1} : [2 cos(4π/7)]^{−1} = −2.24698, [2 cos(6π/7)]^{−1} = −0.55496, [2 cos(2π/7)]^{−1} = 0.80194
p_{2} : 2 cos(6π/7) = −1.80194, 2 cos(4π/7) = −0.44504, 2 cos(2π/7) = 1.24698 .

The values of a(λ_{o,3}), b(λ_{o,3}) and c(λ_{o,3}) to replace in M can be either computed directly by substitution in equations (25) or by applying the field properties of Q(2 cos(2π/7)). This second method is preferable since it results in simple polynomial expressions:

a(λ_{o,3}) = [\frac{1 + λ}{1 + λ + λ^{2}} mod p_{i}(λ)]_{λ=λ_{o,3}} = \frac{1}{7}(5 + λ_{o,3} − λ_{o,3}^{2})
b(λ_{o,3}) = [\frac{λ + λ^{2}}{1 + λ + λ^{2}} mod p_{i}(λ)]_{λ=λ_{o,3}} = \frac{1}{7}(−1 + 4λ_{o,3} + 3λ_{o,3}^{2})
c(λ_{o,3}) = [\frac{−λ}{1 + λ + λ^{2}} mod p_{i}(λ)]_{λ=λ_{o,3}} = \frac{1}{7}(3 − 5λ_{o,3} − 2λ_{o,3}^{2}) (i = 1, 2) .

Similarly, we can compute the optimal value d_{P,min}^{o,3}:

d_{P,min}^{o,3} = [|a b c| mod p_{i}(λ)]_{λ=λ_{o,3}} = [\frac{λ^{2}(1 + λ)^{2}}{(1 + λ + λ^{2})^{3}} mod p_{i}(λ)]_{λ=λ_{o,3}} = \frac{1}{7} < \frac{1}{3} (i = 1, 2)

By direct inspection we find that all these lattices are equivalent to the lattices Z_{3,3a} and Z_{3,3b} of Section 3.3.

C. Construction in higher dimensions

In the two previous subsections we have found the basic building blocks of the rotation matrices we will present here. This construction is based on the special structure of some orthogonal matrices similar to the one used to construct Hadamard matrices. We will illustrate this construction in some detail for dimension 4. The other rotation matrices for dimensions 6, 8 and 12 are obtained by iterating the same construction.

C.1 Dimension 4 The family of four-dimensional orthogonal matrices we consider here is

M = ( \begin{matrix}a & b & −c & −d \\ −b & a & d & −c \\ c & d & a & b \\ −d & c & −b & a \end{matrix} ) = ( \begin{matrix}M_{1} & −M_{2} \\ M_{2} & M_{1} \end{matrix} )

Let U^{2} = a^{2} + b^{2} + c^{2} + d^{2} be the normalization factor.

If the 2 × 2 sub-matrix M_{1} is fixed to be one of the optimal two-dimensional matrices, then the orthogonality constraints reduce to ad − bc = 0. The other 2 × 2 sub-matrix M_{2} is

Fig. 7. d_{P,min} for a family of Z_{4,4} lattices

dependent on the parameter λ. The basis vectors are finally normalized by U giving

a = \frac{1}{U\sqrt{1 + λ_{o,2}^{2}}} b = \frac{λ_{o,2}}{U\sqrt{1 + λ_{o,2}^{2}}} c = \frac{λ}{Uλ_{o,2}} d = \frac{λ}{U}

where

U = \frac{\sqrt{λ_{o,2}^{2} + λ^{2} + λ_{o,2}^{2}λ^{2}}}{λ_{o,2}} .

Figure 7 shows the values of d_{P,min} as a function of λ for a finite constellation (η = 4 bits/symbol), carved from the lattice generated by M. d_{P,min} was computed by exhaustive search through the points of the finite constellation. The values of λ are shown, with steps of 0.005, in the range (0, 3), since the d_{P,min} rapidly vanishes outside this interval and the curve is symmetric about the origin. The values of λ resulting in diversity less than 4 were skipped. In Figure 7 we also plot the following upper bounds to d_{P,min} (functions of λ)

d_{P,min} ≤ \{ \begin{matrix}|a b c d| & (1, 0, 0, 0) \\ |(a^{2} − c^{2})(b^{2} − d^{2})| & (1, 0, 1, 0) \\ |(a − d)^{2}(b + c)^{2}| & (1, 0, 0, 1) \\ |(a + d)^{2}(b − c)^{2}| & (0, 1, 1, 0) \\ |(−b + c − d)(a + d + c)(d + a − b)(−c + b + a)| & (0, 1, 1, 1) \end{matrix}  (27)

corresponding to the product distances between the origin and the points with the given integer components.

In Figure 7 we find identify the two highest peaks at the intersection of the first and third bound in (27)

λ_{o,4}^{(1)} = \frac{1}{10}(\sqrt{2} − 1)\sqrt{50 + 10\sqrt{2}} = 0.3523511

and at the intersection of the first and fourth bound in (27)

λ_{o,4}^{(2)} = \frac{1}{10}(\sqrt{2} + 1)\sqrt{50 + 10\sqrt{2}} = 2.0536527 .

These values can be obtained in a closed form since they are roots of a polynomial of degree 4. The corresponding optimal value for d_{P,min} is 1/40. Other two lower peaks are found at the intersection of the second and third bound in (27) (λ_{so,4}^{(1)} = 0.6641681) and at the intersection of the second and fourth bound in (27) (λ_{so,4}^{(4)} = 1.0894935). The corresponding sub-optimal value for d_{P,min} is 1/85. Closed form values of λ_{so}, can also be found.

C.2 Dimension 6

By a similar procedure we can build the six-dimensional orthogonal matrices starting from the optimal three-dimensional one. This is the highest dimension where closed-form solutions can be computed and we find one optimal value 1/(7^{2} 5 \sqrt{5}) for d_{P,min}.

The first row of the rotation matrix is reported in Table III. The entire matrix can be easily obtained by the construction given in the previous section.

n index  d_{P,min}
3 1–3 -0.3199 0.7189 0.5765
4–6 -0.0590 0.1326 0.1654  1.825 10^{−3}
8 1–4 0.0583 -0.0943 0.1407 -0.2277
5–8 0.1926 -0.3116 0.4649 -0.7522 3.685 10^{−6}
12 1–4 -0.1517 0.3409 -0.2734 0.0938
5–8 -0.2107 0.1690 0.2751 0.4721
9–12 0.0333 -0.0869 0.2317 0.5860 1.528 10^{−10}

TABLE III First rows of the generator matrices of Z_{6,6}, Z_{8,8} and Z_{12,12}

C.3 Other dimensions

In all the previous cases we were able to obtain the closed form expressions for the optimal rotation matrices. If we further increase the dimension a greater number of constraints become non linear and the degree of the polynomial equations giving the optimal values of λ becomes greater than four, which is the ultimate limit for closed form solutions.

In these cases we adopt a purely numerical approach to find the peek values of d_{P,min}. Unfortunately we are not able to guarantee the absolute optimality of the rotations. We report in Table III the numerical values of the first row of the rotation matrix for dimensions 8 and 12. The entire matrices can be easily reconstructed by iterating the construction given in the previous sections.

VII. Simulation results

In this section we give a complete presentation of the performance curves of the rotated constellations that we have constructed in the previous sections.

We first consider a throughput of η = 4 bit/symbol so that we will compare the performance with a traditional 16-QAM modulation scheme. In all the figures we plot the BER

Fig. 8. Bit error rates for the family of Z_{n,n/2} constellations (η = 4)

curve of the 16-QAM over the Gaussian channel and over the independent Rayleigh fading channel. These two curves bound the region of potential gain over the fading channel, when the rotated multidimensional uncoded schemes are used.

The first family of curves (Fig. 8) corresponds to constellations in dimensions n up to 32 and diversity L = n/2 (Sec. V-B). As the diversity increases the bit error rate curves approach the one for the Gaussian channel. For the largest value of diversity the gap to the Gaussian BER curve is only about 1.5 dB between 10^{−3} and 10^{−4}. These constellations can be easily constructed for any dimension n = 2^{e_{1}}3^{e_{2}}, e_{1}, e_{2} = 0, 1, 2 . . .. The only limitation in going beyond dimension 32 is the decoder complexity.

The second family of curves (Fig. 9) corresponds to constellations in dimensions n up to 15 and diversity L = n (Sec. V-C). As the diversity increases (L = 3, 5, 9, 11, 15) the bit error rate curves approach the one for the Gaussian channel. For the largest value of diversity the gap to the Gaussian BER curve is about 3 dB between 10^{−3} and 10^{−4}. If we compare

Fig. 9. Bit error rates for the family of Z_{n,n} constellations from Q(2 cos(2π/N)) (η = 4)

these curves with the previous ones we observe that for similar dimensions (e.g. 15 and 16) the performance is similar. This shows that the doubling of the diversity is not sufficient to increase the performance. We have verified experimentally that for these constellations the product kissing number τ_{p} is much larger and we believe that this is the limiting factor to improving the performance by simply increasing the diversity.

The third family of curves (Fig. 10) corresponds to constellations in dimensions n up to 12 and full diversity L = n (Sec. VI). As the diversity increases (L = 3, 4, 6, 8, 12) the bit error rate curves approach the one for the Gaussian channel. For the largest value of diversity the gap to the Gaussian BER curve is about 4dB between 10^{−3} and 10^{−4}. The computational complexity of finding these rotations is the limiting factor in increasing dimension. Having optimized the minimum product distance we expected a performance improvement. Unfortunately, the product kissing number is again the limiting factor. For the four-dimensional case we have plotted the curves for two distinct rotations corresponding to

Fig. 10. Bit error rates for the family of Z_{n,n} constellations which maximize the minimum product distance (η = 4)

different values of the minimum product distance (see Section VI-C.1). In this case doubling d_{p,min} only improves by a few tenths of a dB.

Finally we show in Figure 11 the case of η = 2 bits/symbol which can be compared to the traditional 4-PSK modulation scheme. We considered the case of Z_{n,n/2} rotations. In this case the gap to the Gaussian BER curve is less than 1 dB between 10^{−3} and 10^{−4}.

This figure is also useful for comparison with the coded system proposed in [8] with 2 bits/symbol. There, a rate 1/2 trellis coded rotated 16-QAM is used and BER of 10^{−4} is achieved with E_{b}/N_{0} = 19 dB. Our uncoded system provides the same performance using only a four-dimensional constellation and greater gains can be obtained by increasing the dimension.

VIII. Conclusions

In this paper we have analyzed an alternative diversity technique and we have constructed high diversity modulation schemes which exhibit an almost Gaussian performance over the

Fig. 11. Bit error rates for the family of Z_{n,n/2} constellations (η = 2)

fading channel.

The great advantage of this type of diversity is that it is traded only for a higher demodulator complexity. No additional power or bandwidth is required, since no type of redundancy is added.

We have verified that the diversity order L and the minimum product distance d_{p,min} are not the only important design parameters. The product kissing number τ_{p} is also a critical design parameter. The constellation design which takes into account τ_{p} is still an open problem.

Using the Universal lattice decoder the ML detection complexity is independent of the system throughput η: only increasing the number of dimensions slows down the demodulation operation.

Future developments of this work include the analysis of additional error control coding techniques, the effects of imperfect CSI estimation, performance analysis with correlated fading channels.

IX. Acknowledgments

The authors are grateful to Prof. Michele Elia and to Dr. Olivier Rioul for suggesting the two different proofs in the appendix. They would also like to thank the reviewers for the valuable suggestions and comments which greatly helped in improving the first version of the paper.

Appendix I. The minimal polynomial of 2 cos(2π/N)

This appendix gives two different methods to compute the minimal polynomials μ(x) of 2 cos(2π/N) for any N.

Proof 1 – Let m(x) be the minimal polynomial of θ = e^{2πj/N} (i.e., the cyclotomic polynomial of degree ϕ(N)) and let x = 2 cos(2π/N) = θ + 1/θ then

θ^{2} − xθ + 1 = 0 and θ_{1,2} = \frac{x ± \sqrt{x^{2} − 4}}{2}

We now consider the polynomial with integer coefficients g(x) = m(θ_{1})m(θ_{2}). This polynomial has degree Φ(N) and must contain a factor of degree Φ(N)/2 which is the minimal polynomial we are looking for. This implies that g(x) = μ(x)^{2} so that the minimal polynomial can be obtained using Euclid’s algorithm to compute the greatest common divisor between g(x) and its derivative g′(x) = 2μ(x)μ′(x).

Proof 2 – Let m(x) = ∑_{k=0}^{n} a_{k}x^{k} be the minimal polynomial of θ = e^{2πj/N} i.e., the cyclotomic polynomial of degree n = ϕ(N).

Using the fact that m(x) is reciprocal since it also admits θ^{−1} as a root, we can write the relation θ^{−n/2}m(θ) = 0 as

∑_{k=0}^{n/2} a′_{n/2−k}(θ^{k} + θ^{−k}) = 0

where a′_{k} = a_{k} except a′_{n/2} = a_{n/2}/2. Noting that (θ^{k} + θ^{−k}) = 2 cos(2πk/N) = T_{k}(cos 2π/N) where T_{k}(x) is the k-th Chebychev polynomial of the first kind, we obtain

μ(x) = ∑_{k=0}^{n/2} a′_{n/2−k}T_{k}(x) = 0 .

To show that μ(x) is the minimal polynomial of x = 2 cos(2π/N) it is enough to show

that it is irreducible. Indeed, if it were reducible, then going backwards from the relation

μ(x) = 0 gives a non trivial factorization of Φ_{N}(θ) over Q, which is impossible.

We can conclude that the minimal polynomial of x over Q is given above and has degree

n/2.

Using the above proof it is easy to show that if N is odd, since Φ_{2N}(θ) = Φ_{N}(−θ),

μ_{2N}(x) = μ_{N}(−x): the minimal polynomial for x = cos 2π/2N is obtained from the minimal

polynomial of x = cos 2π/N by changing the sign of x.

References

[1] S. Sampei, T. Sunaga: “Rayleigh fading compensation for QAM in land mobile radio communications,” IEEE Trans. on Veh. Technol., vol. 42, no. 2, May 1993, pp. 137–147.

[2] J. Du, B. Vucetic: “Trellis coded 16-QAM for fading channels,” European Trans. Telecom., vol. 4, no. 3, May-June 1993, pp. 335–341.

[3] D. Subasinghe-Dias, K. Feher: “A coded 16-QAM scheme for fast fading mobile radio channels,” IEEE Trans. Commun., vol. 43, no. 5, May 1995, pp. 1906–1916.

[4] J. Boutros, E. Viterbo, C. Rastello, J. C. Belfiore: “Good lattice constellations for both Rayleigh fading and Gaussian channel,” IEEE Trans. on Information Theory, vol. 42, no. 2, March 1996, pp. 502–518.

[5] J. Boutros, M. Yubero: “Converting the Rayleigh fading channel into a Gaussian channel,” Mediterranean Workshop on Coding and Information Integrity, Palma, Feb. 1996.

[6] E. Viterbo, E. Biglieri:“A universal lattice decoder,” 14-ème Colloque GRETSI, Juan-les-Pins, Sept. 1993.

[7] E. Viterbo, J. Boutros:“A universal lattice code decoder for fading channels,” submitted to IEEE Trans. on Information Theory, April 1996.

[8] B. D. Jeličić, S. Roy: “Design of a trellis coded QAM for flat fading and AWGN channels,” IEEE Trans. on Vehicular technology, vol. 44, n. 1, Feb. 1995.

[9] J. H. Conway, N. J. Sloane: Sphere packings, lattices and groups, 2nd ed., 1993, Springer-Verlag, New York.

[10] K. Boullé, J. C. Belfiore: “Modulation scheme designed for the Rayleigh fading channel,” CISS’92, Princeton, March 1992.

[11] J.G. Proakis: Digital communications, New York, McGraw Hill, 3rd edition, 1995.

[12] A. Papoulis: Probability, random variables, and stochastic processes, New York, McGraw Hill, 3rd edition, 1991.

[13] P. Samuel: Algebraic theory of numbers, Paris: Hermann 1971.

[14] S. Lang: Algebraic Number Fields, Addison Wesley, 1971.

[15] H. Hasse: Number Theory, Springer Verlag, 1980.

Biographies

Joseph Boutros (IEEE Member) was born in Beirut, Lebanon, in 1967. After his studies at Saint Joseph University (Beirut) he joined the Ecole Nationale Supérieure des Télécommunications (ENST), Paris, France, where he received an Electrical Engineering degree in 1992 and a Ph.D. degree in 1996. Since September 1996, he is with the Communications Department at ENST as an Associate Professor. His fields of interest are lattice sphere packings, algebraic number theory, parallel concatenated codes, and multicarrier transmissions. Dr. J. Boutros is a member of URA-820 of the French National Scientific Research Center (CNRS).

Emanuele Viterbo (M’95) was born in Torino, Italy, in 1966. He received his degree (Laurea) in Electrical Engineering in 1989 and his Ph.D. in 1995 in Electrical Engineering, both from the Politecnico of Torino, Torino, Italy.

From 1990 to 1992 he was with the European Patent Office, The Hague, The Netherlands, as a patent examiner in the field of dynamic recording and in particular in the field of error-control coding. Between 1995 and 1997 he held a post-doctoral position in the Dipartimento di Elettronica of the Politecnico di Torino in Communications Techniques over Fading Channels. He is currently a visting researcher in the Information Sciences Research Center of AT&T Research, Florham Park, NJ.

Dr. Emanuele Viterbo was awarded a NATO Advanced Fellowship in 1997 from the Italian National Research Council. His current research interests are in lattice codes for the Gaussian and fading channels, algebraic coding theory, digital terrestrial television broadcasting, and digital magnetic recording.

List of Figures

1 How to increase diversity: (a) L = 1, (b) L = 2. . . . . . . . . . . . . . . . . . 2 2 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 3 Probability density function of Y . . . . . . . . . . . . . . . . . . . . . . . . . . 10 4 Pairwise error probability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 5 d_{P,min} for a family of Z_{2,2} lattices . . . . . . . . . . . . . . . . . . . . . . . . . 19 6 d_{P,min} for a family of Z_{3,3} lattices . . . . . . . . . . . . . . . . . . . . . . . . . 22 7 d_{P,min} for a family of Z_{4,4} lattices . . . . . . . . . . . . . . . . . . . . . . . . . 24 8 Bit error rates for the family of Z_{n,n/2} constellations (η = 4) . . . . . . . . . . . 27 9 Bit error rates for the family of Z_{n,n} constellations from Q(2 cos(2π/N)) (η = 4) 28 10 Bit error rates for the family of Z_{n,n} constellations which maximize the minimum

product distance (η = 4) . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 11 Bit error rates for the family of Z_{n,n/2} constellations (η = 2) . . . . . . . . . . . 30

List of Tables

I The admissible values for the roots are θ_{i} = e^{jϕ_{i}}, i = 1, … n/2 . . . . . . . . . 16 II Full diversity Z_{n,n} lattices from ideals of the Q(2 cos(2π/N)). . . . . . . . . . . 18 III First rows of the generator matrices of Z_{6,6}, Z_{8,8} and Z_{12,12} . . . . . . . . . . . 26

Footnote on page 7

We note that this intuitive idea is mathematically unprecise since K has the same density of Q in R.