Pierre Viland
email: pierre.viland@insa-rennes.fr

Gheorghe Zaharia

Jean-François Hélard

Improved Balanced 2 n -PSK STTCs for Several Transmit Antennas from a New and General Design Method

Keywords: space-time trellis codes, balanced codes, MIMO systems, design method

Recently, it has been established that the best spacetime trellis codes (STTCs) belong to a specific class of codes. These codes are called "balanced STTCs" because they use the points of the MIMO constellation with the same probability. Therefore, the search of the best codes can be reduced to this class. This paper presents a new and general method to design 2 n -PSK balanced STTCs for any number of transmit antennas. This method is simpler than the first method, which was described only for 4-PSK modulation and can be generalized for any configuration of the space-time trellis encoder. Simulation results of new 4-PSK and 8-PSK balanced codes prove the importance of this class.

INTRODUCTION

The concept of space-time trellis codes (STTCs) was proposed in 1998 by Tarokh et al. [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF] by combining timeconvolution coding with multiple transmit antennas to improve the data rate and the reliability of wireless communication. In [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], the rank and the determinant criteria were proposed to design STTC in the case of slow fading channel. It was shown in [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] that, for a great product of the number of transmit and receive antennas, the performance for a slow fading channel is determined by the trace criterion.

Based on the above criteria, many codes for 2, 3 and 4 transmit antennas have been proposed [START_REF] Firmanto | Space-time TCM with improved performance on fast fading channels[END_REF][START_REF] Baro | Improved codes for space-time trellis-coded modulation[END_REF][START_REF] Hong | New Space-Time Trellis Codes for Slow Fading Channels[END_REF][START_REF] Jung | Improved space-time trellis codes using expanded signal set in slow Rayleigh fading channels[END_REF][START_REF] Chen | Space-time trellis codes for 4-PSK with three and four transmit antennas in quasi-static flat fading channels[END_REF] after a systematic search to decrease the bit and frame error rate. In [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF], it has been remarked that the codes achieving the best performance have the same property: the used points of multiple input multiple output (MIMO) constellation are generated with the same probability. Therefore, these codes are referred to as "Balanced space-time trellis codes: B-STTCs" [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF][START_REF] Ngo | Balanced QPSK space-time trellis codes[END_REF][START_REF] Viland | An improved method to design QPSK Balanced Space-Time Trellis Codes[END_REF].

The aim of this paper is to present a general method to design the class of balanced 2 n -PSK STTCs which offers the best performance. Therefore, the systematic search for good codes can be reduced to this class. The rest of this paper is organised as follows. In section 2, the encoder is briefly described. The performance criteria of STTCs are presented in section 3. Section 4 presents the main properties of the balanced codes. In section 5, the general method to design balanced codes is described for any number of transmit antennas and for 2 n -PSK modulations. Some examples to design balanced codes for specific configurations are given. Finally, some new balanced codes which outperform the best known codes are proposed for 4-PSK and 8-PSK modulations.

SPACE TIME TRELLIS CODING

We consider the general case of the 2 n -PSK space-time trellis encoder. Fig. 1 shows the encoder for n=2. This encoder has one input block of n bits and ν memory blocks of n bits. At each time t ∈ ℤ , the n bits of a block are replaced by the n bits of the previous block. Usually, the state of the encoder is defined by the binary values of ν memory blocks of n bits. The th i bit

M M 1 t x mod 4 ∑ 1 t y 1 1,1 g 1 2,1 g Input 1,1 k g 2,1 k g 1,2 k g 2,2 k g 1, 1 k v g + 2, 1 k v g + 2 t x 1 1,2 g 1 2,2 g 1 2 t x - 2 t v x - 1 1, 1 v g + 1 2, 1 v g + 1 t v x - 1 1 t x - Memory mod 4 ∑ k t y 1,1 T n g 2,1 T n g 1,2 T n g 2,2 T n g 1, 1 T n v g + 2, 1 T n v g +
1 t j i x -+ , i = 1. . . n, of the th j block, j=1...(ν+1), is associated to n T multiplier coefficients , 2 n k i j g ∈ ℤ , k = 1. . . n T ,
where n T is the number of transmit antennas. A space-time trellis encoder is thus usually defined by its generator matrix G of n T × n(ν + 1) coefficients

1 1 1 1 1,1 , 1 1, 1 , 1 1,1 ,1 1, 1 , 1 1,1 ,1 1, 1 , 1 .
G T T T T n v n v k k k k n v n v n n n n n v n v g g g g g g g g g g g g + + + + + +         =         ⋮ ⋮ ⋮ ⋮ (1)
The encoder outputs for the k th antenna are computed as

+ + - + -   - - -     =   - -   -   (3)
Let us defined n R the number of receive antennas. In order to achieve the minimum error probability, if min(rank(A))n R ≤ 3 and for slow fading channels, we should maximize the minimum rank and the minimum determinant of the matrix A computed for all pairs of coded frames (E t , S t ) [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF].

In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], Chen proposed a new criterion which is valid for slow and fast Rayleigh fading channels if min(rank(A))n R > 3. Under this assumption, the PEP is minimized if the sum of all the eigenvalues of the product matrix A is maximized. Because A is a square matrix, the sum of all the eigenvalues k λ is equal to the trace of the matrix A

2 1 1 1 0 ( ) A f T T L n n k k k t q t q k k q tr e s λ - + + = = =     = = -       ∑ ∑ ∑ (4)
For each pair of coded frames, the matrix A and then tr(A) can be computed. The minimum trace is the minimum of all these values tr(A). When the product min(rank(A))n R > 3, the minimization of the PEP amounts to use a code which has the maximum value of the minimum trace.

BALANCED CODES

What is a "balanced code"?

The concept of "balanced codes" has been proposed in [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF][START_REF] Ngo | Balanced QPSK space-time trellis codes[END_REF][START_REF] Viland | An improved method to design QPSK Balanced Space-Time Trellis Codes[END_REF]. It is based on the observation that the best STTCs proposed in the literature present the same property: the generated symbols of the MIMO constellation are equally probable.

The binary input data are supposed to be generated by a memory less binary source S b = {0, 1} with equally probable symbols and 2 n -PSK modulation are considered. From a given extended-state X= [ ]

1 2 2 ... ∈ ℤ T L L x x x
of the L = n(ν + 1) length shift register realized by the input block of n bits followed by the v blocks of n bits, the MIMO symbol

1 2 2 ... Y T n T T n n y y y   = ∈   ℤ
generated by the space time trellis encoder shown in Fig. 1 is

Y = G X ( 5
)
where G is the generator matrix (1). This is a deterministic relation. Therefore, the STTC is defined by a map :

T n n L Φ → ℤ ℤ (6)
which associates to the extended-state X a unique codeword Y.

Note that ) mod 2 / {0,1}

T n j L n n j j j j x G x = =     ∈ =       ∑ ℤ (7)
where G j is the j th column of the generator matrix G. In this case:

2 2 ( ) Φ = ℤ ℤ T n n L .
Due to the random memory less source S b = {0, 1}, with p(0)=p(1)=1/2, from a given extended-state X, the encoder has only 2 n equally probable next states. The matrix T of the transition probabilities between these states corresponds to a Markov chain. Due to the symmetry of the matrix T, the steady-state probabilities of the extended-states X are all equal. For a balanced code, by using (5), the generated codewords Y are also equally-probable. In other words, the generated symbols of the MIMO constellation are equally probable.

Properties of balanced STTC

1 2 0 2 T n n C - = ℤ is a subgroup of 2 T n n ℤ such as [ ] 0 v v, v C . = -∀ ∈
In the case of 4-PSK modulation, each

element [ ] 0 v C ∈ can be written as 2 v p = , with 2 . T n p ∈ ℤ The coset [ ] [ ] 0 p C p C = + is called "relative to v ". So, it is possible to write: [ ] 1 4 0 T n C E = ℤ ∪ where E 1 is the set of the cosets [ ] [ ] 0 p C C ≠ . In the case of 8-PSK modulation, each element [ ] 2 0 T n v C 4 ∈ = ℤ can be written as 2 v p = , with 2 2 .
T n p ∈ ℤ For 8-PSK, we note by E 1 the set of cosets which can be written as [ ] [ ]

0 p C p C = + with [ ] { } 2 2 \ 0 0 T T n p ∈ ℤ . So, each coset [ ] [ ] 1 0 p C p C E = + ∈ is called "relative to v ", with [ ] 0 2 v p C . = ∈ Each element 1 q E
∈ can be written as q=2r,

with 4 2 \ 2 T T n n r ∈ ℤ ℤ and a new set E 2 of cosets [ ] [ ] 0 r C r C = +
can be created. Thus, each coset of E 2 is also "relative to an element of E 1 ". Therefore, it is possible to write:

[ ] 1 2 8 0 T n C E E = ℤ ∪ ∪ .
5. A NEW METHOD TO DESIGN 2 n -PSK STTC WITH SEVERAL TRANSMIT ANTENNAS In [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF][START_REF] Ngo | Balanced QPSK space-time trellis codes[END_REF], a first method to design fully balanced codes has been presented for several transmit antennas and 4-PSK STTC. In [START_REF] Viland | An improved method to design QPSK Balanced Space-Time Trellis Codes[END_REF], a simpler method to design balanced 4-PSK STTC was presented. The general method described in this paper which is based on the method of [START_REF] Viland | An improved method to design QPSK Balanced Space-Time Trellis Codes[END_REF] allows an easier design of balanced codes for any number of transmit antennas and for any 2 n -PSK modulation. Due to Property 2, it is enough to design fully balanced codes with L = L min . This general method respects two rules:

• Rule 1: The first no null column G 1 must belong to 0 C     . Due to the theorem 4, G 1 = -G 1 , so { } 1 1 , H 0 G = is a subgroup of 2 T n n ℤ . • Rule 2: Each new chosen column of G must create a new subgroup H i+1 of 2 T n n ℤ with card(H i+1 ) = 2card(H i ).
Thus, in order to obtain a fully balanced STTC, this general algorithm is as follows:

if i<L min columns of G have been already chosen in

2 T n n ℤ and { } 1 mod 2 / 0,1 i n j j j i j x G x H =     ∈ =       ∑ is a subgroup of 2 T n n ℤ , then the column G i+1 of G must belong to 2 \ T n n i H ℤ
and must be selected in the cosets relative to the vectors which belong to H i or in the coset [ ] 0 C . This method ensures that 1 1 ( )

i i i i H H H G + + = + ∪ is a subgroup of 2 T n n ℤ .
The algorithm ends when i+1=L min . The obtained matrix G corresponds to a fully balanced code with n 0 =1. If necessary, more columns can be added to G to create a fully balanced code with n 0 >1.

In order to obtain balanced codes (not necessary fully balanced) the algorithm can be ended when H i0 is created with i 0 ≤ L min -2 columns. One can add a new column ℤ (elements that must not be further selected). Thus, this new method to design the B-STTC is simpler than the method described in [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF][START_REF] Ngo | Balanced QPSK space-time trellis codes[END_REF].

T n 0 0 n i 1 i 2 G \ H . + ∈ ℤ Once again,

Design of fully balanced 4-PSK STTC with 2 transmit antennas

In this case, each generated element belongs to 2 4 ℤ . It is possible to make the partition in cosets:

0 p C p C         = + with 2 2 0 2 C     = ℤ and 2 2
p ∈ ℤ . Thanks to this partition, to generate a balanced code with L min =4 columns, we can proceed as follows:

• In agreement with rule 1, the first column

G 1 of G must be selected in [ ] 0 C (but 1 0 0 G   ≠     ), because [ ] 0 C contains the vectors with the property : i i G G = -. Therefore, a subgroup of 2 4 ℤ is generated: { } 1 1 0, H G = . • The second element G 2 has to create a new subgroup 2 1 2 1 2 {0, , , } H G G G G = + , where 1 G -, 2 G - and 1 2 ( ) G G - + are included in 2 H . There are two solutions to choose G 2 : -If [ ] 2 1 0 \ G C H ∈ , then 2 2 G G -= , -(G 1 +G 2 ) = G 1 +G 2 and [ ] 2 1 2 1 2 0 {0, , , } H G G G G C = + = is a subgroup of 2 4
ℤ . This type of code is called [START_REF] Ngo | A new class of balanced 4-PSK STTC for two and three transmit antennas[END_REF][START_REF] Viland | An improved method to design QPSK Balanced Space-Time Trellis Codes[END_REF] ℤ and thus a fully balanced space-time trellis code for 4-PSK modulation and 2 transmit antennas is obtained.

2 3 4 0 \ G C ∈ ℤ , 3 [0] [0] 3 ( ) H C C G = + ∪ is a new subgroup of 2 4 ℤ . Finally, if 2 4 4 3 \ G H ∈ ℤ , then 2 4 3 3 4 4 ( ) H H H G = + = ∪ ℤ . -If [ ] 1 2 p G C ∈ with 1 1 2p G = , then 1 2 2 G G G + = - and 2 1 2 1 2 {0, , , } H G G G G = + is a subgroup of 2 4 ℤ . If no more vector is selected in [ ] 0 C ,

Design of fully balanced 8-PSK STTC with n T transmit antennas

For 8-PSK STTC with 2 transmit antennas, each generated element belongs to 8 .

T n

ℤ

In agreement with theorem 4, it is possible to make the partition of the set of the cosets:

[ ] 1 2 8 0 T n C E E = ℤ ∪ ∪
where each coset of E 2 is relative to one element of E 1 and each coset of E 1 is relative to one element of [ ] 0 C . Thanks to this partition, in order to generate a balanced code, we can proceed as follows:

• In agreement with rule 1, the first column

G 1 of G must be selected in [ ] 0 C (but [ ] 1 0 0 T G ≠ ⋯ ), because [ ] 0 C
contains the vectors with the property :

i i G G = -.
Therefore, a subgroup of 2 4 ℤ is generated:

{ } 1 1 0, H G = . • The i th column G i (i>1) can be selected either : -in [ ] 1 0 \ i C H -.
-or in the coset [ ]

1 1 \ i p C E H - ∈ if and only if 1 2 i p H - ∈ .
-or in the coset [ ]

2 1 \ i q C E H - ∈
if and only if i q H - ∈ . Thus, each new selected column creates a new subgroup with twice more elements than the previous subgroup.

PERFORMANCE OF NEW CODES

In Table 1, the minimum trace of some new balanced codes are compared to the minimum trace of Chen's codes with 3 and 4 transmit antennas. These codes have 32 and 64 states. The new codes have higher values of the minimum trace than the traces of Chen's equivalent codes. The codes noted by 'B' are balanced, those by 'FB' are fully balanced and those noted by 'NB' are not balanced. Each new code is balanced and its trace is greater than the trace of Chen's corresponding code.

          FB 24 New 1 2 1 2 3 2 3 0 2 2 3 0 2 2 1 0 0 2 1 2 1 0 0 0 2           FB 26
64 Chen [START_REF] Chen | Space-time trellis codes for 4-PSK with three and four transmit antennas in quasi-static flat fading channels[END_REF][START_REF] Vucetic | Space-Time Coding[END_REF] 0 2 3 2 3 0 3 2 2 2 1 2 3 0 2 0 2 0 0 2 2 3 1 1

          B 28 New 2 2 3 2 3 2 1 2 1 0 2 0 2 2 3 0 2 2 1 0 2 2 3 2 1           FB 32 4 32 Chen [7, 11] 0 2 2 1 1 2 0 2 2 2 3 2 2 3 0 0 2 0 3 2 2 1 0 0 2 1 2 0 1 0 0 2               NB 36 New 3 2 3 2 1 2 1 0 2 0 2 2 1 2 3 0 3 2 3 2 3 0 0 0 2 2 1 0 2 2 1 0 0               B 36
64 Chen [START_REF] Chen | Space-time trellis codes for 4-PSK with three and four transmit antennas in quasi-static flat fading channels[END_REF][START_REF] Vucetic | Space-Time Coding[END_REF] 0 2 3 2 3 0 3 2 2 2 1 2 3 0 2 0 2 0 0 2 2 3 1 1

1 2 2 0 2 1 3 2               NB 38 New 4 1 2 2 0 3 2 1 2 3 2 3 2 2 0 3 2 2 0 1 2 3 2 3 2 1 2 2 0 2 0 2 0               FB 40
In Table 2, 8-PSK Chen's codes and new corresponding codes are shown for 3 transmit antennas/16 states and 4 transmit antennas/8 states. The two new codes have higher values of the minimum trace than the traces of Chen's equivalent codes.

The performance of each code is evaluated by simulation in a slow Rayleigh fading channel. The channel fading coefficients are independent samples of a complex Gaussian process with zero mean and variance 0.5 per dimension. These channel coefficients are assumed to be known at the decoder. Each frame consists of 130 4-PSK symbols or 198 8-PSK symbols. For the simulation, there are 2 receive antennas. The decoding is performed by the Viterbi's algorithm. Figure 2 shows the performance of the 4-PSK 32 states and 64 states codes for 3 transmit antennas given in Table 1. In the same way, the performance of 4-PSK STTC with 32 states and 64 states for 4 transmit antennas is shown in figure 3. Figure 4 shows the performance of the new 8-PSK and the corresponding Chen's codes of Table 2.

             
17.17

Fig. 1 . 4 -

 14 Fig. 1. 4-PSK space time trellis encoder with nT transmit antennas

1 (

 1 By definition, a STTC is balanced if and only if each generated codeword Y The number of different codewords generated by relation (5) is given by 2 ( ( )) L card Φ ℤ which is a power of 2. The code is fully balanced if 2

Theorem 1 :Theorem 2 :

 12 If a STTC is fully balanced then min . . Let us consider a fully balanced MIMO code with a ℤ the resulting generator matrix G'=[G G L+1 ] corresponds to a new fully balanced code. Theorem 3: If G is the matrix of a balanced code, each permutation of its columns or/and lines generates the matrix of a new balanced code. Theorem 4: [ ]

1

 1

2

 2

Fig. 2 .Fig. 3 .Fig. 2 .

 232 Fig. 2. Performance of 4-PSK STTC with 3 Tx / 2 Rx antennas

= E t -S t .

									k t y		1 1 + = = ∑∑ 1 n v i j =	1 -+ t j i x	g	, k i j	mod 2 n	(2)
			Each encoder output k t y is mapped onto a 2 n -PSK signal
	given by:	k t s	=	exp	  	j	1 -π 2 n	k t y	  	.	Each output signal k t s is send
	to the k th transmit antenna. The modulated streams of all
	antennas are then transmitted simultaneously.
													3. DESIGN CRITERIA
			Several design criteria have been proposed in [1, 2] to
	exploit the spatial diversity and to offer optimal coding gain.
	The case of slow Rayleigh fading propagation channels is
	mainly considered in this paper. The n T dimension transmitted
	symbols	t s	 = 	1 2 t t s s s ... T n t	 	T	, where [•] T denotes the transpose
	operator, are assumed to be grouped in a frame of length L f .
	Traditionally, criteria are derived from the minimization of the
	pairwise error probability (PEP), i.e. the probability of
	transmitting the n T × L f dimension coded frame
	S	t	 = 	t t+1 s s ...s	f t+ L -1	 	and deciding erroneously in favour of
	another		n T			×	L f	dimension	coded	frame
	E	t	 = 	t t+1 e e ...e	f t+ L -1	 	. The n T × n T product matrix A = BB * * * *
	is introduced, where B * * * * denotes the hermitian of the n T × L f
	difference matrix B 1 1 1 1 1 ... ... t L t q t q t t e e s e s + -1 f + +	1 t L s + -1 f
				B			... ...	...	...	...
								T n t e			T n t s	...	T n t q e +	T n t q s	...	T n t L e	f	1	T n t L s	f	1

TABLE 1 :

 1

				4-PSK Balanced STTCs
			with 3 and 4 transmit antennas
	nT	States	Code	G	Trace
				0 2 2 1 1 2 0 2
	3	32	Chen [7, 11]	2 2 3 2 2 3 0 0 2 0 3 2 2 1 0 0

TABLE 2 :

 2

				8-PSK Balanced STTCs
			with 3 and 4 transmit antennas
	nT States	Code	G	Trace
	3	16	Chen [11]


Pierre Viland
email: pierre.viland@insa-rennes.fr

Gheorghe Zaharia

Jean-Francois Hélard

Design of the best space-time trellis codes based on coset partitioning

INTRODUCTION

The MIMO systems use antenna arrays at both sides of a radio link to drastically improve the reliability and/or the data rate of the wireless communication. In order to exploit the performance of the MIMO systems, several channel coding techniques have been proposed. For example, the STTCs combine the spatial diversity and time diversity in order to combat efficiently the signal fading. The STTCs have been proposed by Tarokh et al. in [START_REF] Tarokh | Spacetime codes for high data rate wireless communication: Performance criterion and code construction[END_REF], where the analytic bound and the first design criteria have been obtained. The rank and the determinant criteria have been proposed to design good codes in the case of slow Rayleigh fading channels. For fast Rayleigh fading channels, the product distance and the Hamming distance criteria have been proposed. In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], Vucetic et al. proposed the trace criterion for a slow Rayleigh fading channel. Based on the Euclidean distance, this criterion governs the performance for a great product of the number of transmit and receive antennas.

Thanks to these criteria, many 4-PSK and 8-PSK codes have been proposed to decrease the bit and frame error rate [START_REF] Tarokh | Spacetime codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF][START_REF] Chen | Spacetime trellis codes with two, three and four transmit antennas in quasi-static flat fading channels[END_REF][START_REF] Baro | Improved codes for space-time trellis-coded modulation[END_REF][START_REF] Abdool-Rassool | Search for space -time trellis codes: novel codes for rayleigh fading channels[END_REF]. However, a systematic search has been required to find these codes. The aim of this paper is to propose a new method to design the best 2 n -PSK codes with n T transmit antennas. This method is an extension of the set partitioning proposed by Ungerboeck [START_REF] Ungerboeck | Channel coding with multilevel/phase signals[END_REF][START_REF] Ungerboeck | Trellis-coded modulation with redundant signal sets part I: Introduction[END_REF][START_REF] Ungerboeck | Trellis-coded modulation with redundant signal sets part II: State of the art[END_REF]. In fact, he states the following rules to design a trellis-coded modulation (TCM):

1. Each point of the constellation has the same number of occurrences.

2. In the trellis, transitions originating from the same state or merging into the same state should be assigned subsets which contain signal points separated by the largest Euclidean distance.

3. Parallel paths should be assigned signal points separated by the largest Euclidean distance. Since there are no parallel paths in the STTCs, this rule is not important for the new design of the STTCs.

Thanks to this new method called 'coset partitioning', it is possible to design the best STTCs without an exhaustive search. The paper is organised as follows. Section II describes the representations of space-time codes and the existing design criteria. In section III, the new method is presented. In the last section, new 4-PSK and 8-PSK are given and their performance is compared to the best known codes.

SYSTEM MODEL

Representation of the space-time trellis encoder

We consider a 2 n -PSK space-time trellis encoder with n T transmit antennas and n R receive antennas. For n = 2, the encoder is shown in Fig. 1.

Fig. 1. Space-time trellis encoder for 4-PSK and n T transmit antennas

The encoder is composed of one input block of n bits and ν memory blocks of n bits. The state is defined by the binary values of the ν memory blocks of n bits. At each time t ∈ Z, all the bits of a block are replaced by the n bits of the previous block. The i th bit of the j th block x t-j+1 i , with i = 1 . . . n and j = 1 . . . ν + 1, is associated to n T multiplier coefficients g k i,j ∈ Z 2 n , k = 1 . . . n T , where n T is the number of transmit antennas. With these n T × n(ν + 1) coefficients, we define a generator matrix G G G with n T lines and ν + 1 blocks of n columns:

G G G = [G 1 1 ...G 1 n |...|G ν+1 1 ...G ν+1 n ] (1)
with

G j i = [g 1 i,j ...g n T i,j ] T ∈ Z n T 2 n .
At each time t, the encoder output y y y

x t = y t 1 y t 2 ... y t n T T ∈ Z n T 2 n is given by y y y x t = G G Gx x x t (2)
where

x x x t = [x t 1,1 ...x t 1,n ..x t ν+1,1 ...x t ν+1
,n ] T is the extendedstate at time t of the L = n(ν+1) length shift register realized by the input block followed by the ν memory blocks of n bits.

Each encoder output y t k is mapped onto a 2 n -PSK signal given by: s t k = exp(j π 2 n-1 y t k ). Each output signal s t k is sent to the k th transmit antenna. At each time t, the set of symbols transmited simultaneously over the fading MIMO channel is given by s s s

t = s t 1 s t 2 ...s t n T
T .

An encoder can also be represented by a trellis, as shown in Fig. 2 for 4-PSK 4 states STTC.

STATES x t 2,1 , x t 2,2 x t+1 2,1 , x t+1 2,2

Fig. 2. 4-PSK 4 states STTC

In the trellis, the states are described by the points and the transitions between the states by the lines. Each transition corresponds to an extended-state. The vector y y y i ∈ Z n T 4 represents the MIMO symbol associated to an extended-state. The index i is computed as the decimal value of this extendedstate, where x t 1,1 is the least significant bit. In this example, the trellis representation corresponds to the generator matrix

G G G = [y 1 y 2 |y 4 y 8 ].
In the general case, for a 2 n -PSK STTC, there are 2 n transitions originating from the same state or merging into the same state. Each MIMO symbol belongs to Z n T 2 n .

Design criteria

The main design criteria have been established in [START_REF] Tarokh | Spacetime codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] in order to decrease the bit and frame error rate. In this paper, only the case of slow fading channels is considered. Hence, the fading coefficients are constant during one frame of L f symbols. Besides, we assume that the decoder uses a maximum likelihood to estimate the transmitted symbols.

The main goal of this method is to reduce the pairwise error probability (PEP) which is the probability that the decoder selects an erroneous sequence. It is possible to represent the L f length transmitted frame beginning at time t = 0 by a n T × L f dimension matrix S S S = [s s s 0 s s s 1 ...s s s The product rn R ≤ 3: two criteria have been proposed [START_REF] Tarokh | Spacetime codes for high data rate wireless communication: Performance criterion and code construction[END_REF][START_REF] Liao | Improved code design criteria for space-time codes over quasi-static flat fading channels[END_REF] to reduce the PEP. A A A has to be a full rank for any pair (E E E, S S S) and the coding gain given by η = d N (d)d -n R must be minimized. N (d) is defined as the average number of error events with determinant d = det(A).

The product rn R ≥ 4: it has been shown in [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF] that the PEP is minimized if the minimum trace of A A A computed for all pairs (E E E, S S S) with E E E = S S S is maximized.

In this paper we consider the case rn R ≥ 4 which is obtained if the rank of the generator matrix G G G is greater than 1 and if there are at least 2 receive antennas.

COSET PARTITIONING FOR SPACE-TIME TRELLIS CODES

Coset decomposition

The MIMO symbols belong to the group Z n T 2 n . This group can be decomposed in cosets as in [START_REF] Colemann | Coset decomposition in lattices yields sample-block number systems[END_REF]:

Z n T 2 n = g∈[Z n T 2 n /C0] (g + C 0 ) (3)
where

C 0 = 2 n-1 Z n T 2 is a normal subgroup of Z n T 2 n such as ∀v ∈ C 0 , v = -v. [Z n T 2 n /C 0 ]
denotes a set of cosets representatives, one for each coset. In this paper, the coset representatives are

[Z n T 2 n /C 0 ] = Z n T 2 n-1 mod 2. So, the group Z n T 2 n is decomposed in 2 n T (n-1) cosets.
Besides, it is possible to create n sets of these cosets. For a 2 n -PSK modulation and n T transmit antennas, the first set of cosets is

E 0 = C 0 = 2 n-1 Z n T 2 .
The other sets E i of cosets with 1 ≤ i ≤ n -1 are defined by

E i = gi (g i + C 0 ), with g i ∈ 2 n-i-1 Z n T 2 i \2 n-i Z n T 2 i-1 (4) Each coset C p = p + C 0 ∈ E i with 0 ≤ i ≤ n -2 is called 'relative to q = 2p ∈ E i-1 '.

Coset partitioning

Calderbank et al. give an alternative to the set partitioning. It is based on the observation that the points of the constellation of a convolutional encoder can be regarded as a finite set of points from a group [START_REF] Calderbank | New trellis codes based on lattices and cosets[END_REF]. The group is partitioned into cosets. The Euclidean distances between the elements of the cosets are maximized. The coder selects at each time one coset. In each coset, it selects one element. It is possible to adapt the works of Ungerboeck and Calderbank et al. for the STTCs. In fact, the MIMO constellation can be seen as a finite subgroup of Z n T 2 n . The goal of this method is that all the MIMO symbols originating from or merging to the same state belong to the same coset. The elements of these cosets must be separated by the largest Euclidean distances. Thus, for a 2 n -PSK STTC with 2 nν states, the generator matrix G G G is constituted by ν + 1 blocks of n columns. To design the STTCs with the coset partitioning, each block i must generate a subgroup. Thus, the following rules must be respected:

• For each block k, its first column G k 1 must belong to C 0 with 1 ≤ k ≤ ν + 1.
• The columns G k i with 2 ≤ i ≤ n and 1 ≤ k ≤ ν + 1 must belong to the cosets relative to an element generated by the first (i -1) columns or in C 0 .

After the choice of all columns of G G G, it is possible to permute the columns and the lines of each block to obtain codes which respect the coset partitioning. Many subgroups exist and we show in the next section how to select the optimal elements to create the best generator matrices G G G.

Design example: 4-PSK 4 states STTC with n T transmit antennas

The MIMO symbols belong to Z n T 4 . This group can be divided in 2 subsets:

E 0 = C 0 and E 1 = (g i + C 0 ) with g i ∈ Z n T 2 \[0...0] T . The generator matrix G G G has 2 blocks of 2 columns: B 1 = [G 1 1 , G 1 2 ] and B 2 = [G 2 1 , G 2 2 ] which give G G G = [G 1 1 G 1 2 |G 2 1 G 2 2 ].
If the coset partitioning is used to design a STTC, the columns of each block of G G G generates a subgroup of Z n T 4 . We note Λ ν+1 the set of MIMO symbols generated by the coder. It is possible to represent it with the trellis form. Fig. 3 shows the 4-PSK 4 states STTC where Λ F 1 = {y y y 0 , y y y 1 , y y y 2 , y y y 3 = y y y 1 + y y y 2 mod 4} and Λ M 1 = {y y y 0 , y y y 4 , y y y 8 , y y y 12 = y y y 4 + y y y 8 mod 4} are subgroups of Z n T 4 . Each coset of Λ ν+1 /Λ F 1 or of Λ ν+1 /Λ M 1 corresponds respectively to the set of MIMO symbols originating from the same state and the set of MIMO symbols merging into the same state. Thus, the generator matrix is G G G = [y y y 1 y y y 2 |y y y 4 y y y 8 ]. The rule 2 of Ungerboeck's method is: transitions originating from the same state or merging into the same state in the trellis should be assigned subsets which contain signal points separated by the largest Euclidean distances. In order to exploit the coset partitioning, the Euclidean distances between the elements of respectively Λ F 1 and Λ M 1 must be maximized thanks to the selection of {y 1 , y 2 } and {y 4 , y 8 }. 2 n , the rule 1 of Ungerboeck's method is respected.

Λ F 1 +Λ M 1 } Λ F 1 Λ F 1 Λ F 1 00 01 10 11 STATES x t 2,1 , x t 2,2 x t+1 2,1 , x t+1

Design example: 4-PSK 16 states STTC with n T transmit antennas

The MIMO symbols belong to Z n T 4 . This group can be divided in 2 sets of cosets:

E 0 = C 0 , E 1 = (g i + C 0 ) with g i ∈ Z n T 2 \[0...0] T . The matrix G G G has 3 blocks of 2 columns: B 1 = [G 1 1 , G 1 2 ], B 2 = [G 2 1 , G 2 2 ] and B 3 = [G 3 1 , G 3 2 ] which give G G G = [G 1 1 G 1 2 |G 2 1 G 2 2 |G 3 1 G 3 2 ].
In the case of a 4-PSK 16 states STTC designed with coset partitioning, the trellis can be represented as shown in Fig. 4.

STATES x t 3,1 , x t 3,2
x t+1 3,1 , x t+1 It is possible to make a chain partition with the MIMO symbols merging into the different levels of states:

Λ ν+1 /Λ M 2 /Λ M 1 .
Each element of Λ ν+1 /Λ M 2 corresponds to one coset of MIMO symbols merging into a same state of level 2. As shown in Fig. 5,Λ M 2 is given by:

Λ M 2 = Λ M 1 + Λ F 1 . Thus, Λ M
2 is already defined by the previous selections.

At the end, we permute the elements of each block to find the codes with the best trace.

Design example: 8-PSK 8 states STTC with 4 transmit antennas

The MIMO symbols generated by the 8-PSK 8 states STTCs with 4 transmit antennas belong to Z 4 8

= E 0 ∪ E 1 ∪ E 2 . E 0 = C 0 = 4Z 4 2 , E 1 = (g + C 0 ) with g ∈ 2Z 4 \[0 0 0 0] T and E 2 = (h + C 0 ) with h ∈ Z 4 4 \2Z 4
2 . The generator matrix G G G is constituted by 2 blocks of 3 columns. To generate G G G we can proceed as follows. We must select 3 elements of Z 4 8 for the 2 blocks which create subgroups of Z 4 8 . The minimum Euclidean distance between two different elements of each group must be maximized. In fact, these two subgroups correspond to the transitions originating from the same state and to the transitions merging into the same state. An 'optimal' subgroup of Z 4 8 is generated thanks to one element of C 0 = E 0 , one element of E 1 and one element of E 2 . After the selection of two good blocks, we search the code with the optimal trace. We obtain: G G G =



 . Remark 1: Some codes may have first i null columns in the (ν + 1) th block with 0 < i < n. The number of states is 2 nν-i . In this case, the columns which generate the subgroup Λ M 1 (MIMO symbols which merge into a same state) are the first i columns of ν th blocks and the last ni columns of the (ν + 1) th block.

NEW CODES AND PERFORMANCE ANALYSIS

In Table 1, Chen's 4-PSK codes and new corresponding codes are shown for 3 transmit antennas/32 states and 4 transmit antennas/64 states. The new code with 4 transmit antennas has a higher value of the minimum trace than that of the Chen's equivalent code. The new code with 3 transmit antennas has a trace equal to the trace of the Chen's corresponding code, but, the minimum Euclidean distance between two differents elements generated by each block of the new code are higher. In Table 2, Chen's 8-PSK 8 states codes and new corresponding codes are shown for 3 and 4 transmit antennas. The new code with 3 transmit antennas has a trace equal to the trace of the Chen's corresponding code and the code with 4 transmit antennas has a trace lower than the Chen's corresponding code. We compute the minimum Euclidean distance between the elements generated by each block. Their minimum value is higher than that of the Chen's corresponding code. The performance of each code is evaluated by simulation in a slow Rayleigh fading channel. The channel fading coefficients are independent samples of a complex Gaussian process with zero mean and variance 0.5 per dimension. These channel coefficients are assumed to be known at the decoder. Each frame consists of 130 4-PSK or 8-PSK symbols. For the simulation, there are 2 receive antennas. The decoding is

  L f -1 ]. An error occurs if the decoder decides that an another frame E E E = [e e e 0 e e e 1 ...e e e L f -1 ] is transmitted. Let us define the n T × L f difference matrix B B B = E E E -S S S. The n T × n T product matrix A A A = B B BB B B * is introduced, where B B B * denotes the hermitian of B B B. We define r = min(rank(B B B)) where B B B is computed for all pairs of different coded frames (E E E, S S S). The design criteria depend on the value of the product rn R .

2 , 2 Fig. 3 . 4 -

 2234 Fig. 3. 4-PSK 4 states STTC with cosets Since each block of n (n = 2 for 4-PSK) of G G G generates a subgroup of Z n T2 n , the rule 1 of Ungerboeck's method is respected.

3 , 2 Fig. 5 .

 325 Fig. 5. Simplification of trellis 4-PSK 16 states STTC with cosets

Table 1 .

 1 New 4-PSK code based on the Euclidean distance criteria

	n T	2 νn	Code					G G G						Trace
					0	2	2	1	1	2	0	2
	3	32	Chen		2 2	2 0	3 3	2 2	2 2	3 1	0 0	0 0		24
					0	2	2	1	2	1	0	1
			New 1		2 2	1 1	2 2	1 3	0 2	2 1	0 0	2 3		24
					0	2	3	2	3	0	3	2	
	4	64	Chen		1 2 2	2 2 0	2 1 0	0 2 2	2 3 2	1 0 3	3 2 1	2 0 1		38
					2	3	0	2	2	3	0	2	
			New 2		0 2	2 3	2 0	1 2	2 0	1 2	2 2	3 3		40
					2	1	2	1	2	3	2	1

Code G G G

Trace

• The first step is to select the elements of the first and the last block. The first block and the last block of each generator matrix generate respectively the subgroups Λ F 1 = {y y y 0 , y y y 1 , y y y 2 , y y y 3 = y y y 1 + y y y 2 mod 4} and Λ M 1 = {y y y 0 , y y y 16 , y y y 32 , y y y 48 = y y y 16 + y y y 32 mod 4}. Each coset of Λ ν+1 /Λ F 1 and of Λ ν+1 /Λ M 1 corresponds to the transitions originating from the same state and the transitions merging into the same state. The Euclidean distances between the elements of each subgroup created by the columns of these blocks must be maximized.

• The second step is the selection of B 2 . The vectors of B 2 must also generate a subgroup. So, it is possible to represent a simplified trellis as shown in Fig. 5 where the new points x 3,1 x 3,2 = {00, 01, 10, 11} of Fig. 5

(with y y y 4 + y y y 8 = y y y 12 mod 4). Thus, a partition chain is obtained:

The choice of y 4 and y 8 must maximimize the minimum Euclidean distance between two different elements of Λ F 2 . performed by the Viterbi's algorithm. Fig. 6 shows the performance of the 4-PSK 64 states codes for 3 and 4 transmit antennas given in Table 1. Similary, Fig. 7 shows the performance of the new 8-PSK codes and the corresponding Chen's codes of Table 2.

CONCLUSION

A new and fast method to design easily the best 2 n -PSK STTCs with n T transmit antennas has been presented in this paper. This method reduces significantly the number of possible codes which must be analysed with an exhaustive search.

The proposed method is based on the set partitioning proposed by Ungerboeck and an extension of the work proposed by Calderbank. This method is called 'coset partitioning'. Thanks to this method, new 4-PSK and 8-PSK codes are obtained. It is shown that these new codes outperform the best known codes.


Pierre Viland
email: pierre.viland@insa-rennes.fr

Gheorghe Zaharia

Jean-Francois Hélard

Coset Partitioning for the 4-PSK Space-Time Trellis Codes

In this paper, we present a simple method to design the best 4-PSK space-time trellis codes (STTCs) for any number of transmit antennas. This method called "coset partitioning" is based on the set partitioning proposed by Ungerboeck for the multiple input multiple output (MIMO) systems. Thanks to this method, an exhaustive search is no more required to find the best codes. Thus, new 4-PSK codes are designed and compared with good known codes. The simulation results show that these new codes outperform the existing best codes.

I. INTRODUCTION

The use of multiple transmit and receive antennas is a powerful solution to reduce the effect of multipath fading in wireless communications. In [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], Tarokh et al. propose the concept of space-time trellis coding to exploit the potential of MIMO systems. The STTC which combines the spatial diversity and time diversity allows to improve the error performance of the MIMO systems. In [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF], the analytic bound and the first design criteria have been derived to obtain good codes. In the case of slow Rayleigh fading channels, the rank and the determinant criteria have been presented to design optimal codes. For fast Rayleigh fading channels, the product distance and the Hamming distance criteria have been proposed. In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], Chen et al. proposed the trace criterion for slow Rayleigh fading channels. Based on the Euclidean distance, this criterion governs the performance for a great product of the number of transmit and receive antennas. However, good codes can be obtained only after the exhaustive search. Thus, the time used to search the best codes increases drastically with the number of transmit antennas.

In this paper, we propose to design the best STTCs with an adaptation of the set partitioning called "coset partitioning". The method of set partitioning has been presented by Ungerboeck in [3]- [START_REF]Trellis-coded modulation with redundant signal sets part II: State of the art[END_REF]. It allows to design efficiently the trellis encoder in the case of single input and single output systems. Calderbank et al. proposed an alternative to Ungerboeck's method which is simpler when the code complexity increases [START_REF] Calderbank | New trellis codes based on lattices and cosets[END_REF].

Ungerboeck enonciates his method with the three following rules :

1) Each constellation point has the same number of occurrences.

2) Transitions originating from the same state or merging into the same state in the trellis should be assigned subsets which contain signal points with the largest Euclidean distance. 3) Parallel paths should be assigned points of the constellation separated by the largest Euclidean distance. As there are no parallel paths in the STTCs, this rule is not important for the new design of STTCs. The proposed method is an extension of set partitioning for the STTCs which allows to create easily the best space-time trellis codes without the exhaustive search.

The rest of the paper is organised as follows. In Section II, we present the space-time trellis encoder and the design criteria. Section III describes the method called "coset partitioning". The last section shows new 4-PSK codes obtained with the coset partitioning.

II. SYSTEM MODEL A. Representation of the space-time trellis encoder

We consider a MIMO system with n T transmit antennas and n R receive antennas using a 2 n -PSK modulation. For n = 2, the 4-PSK space-time trellis encoder is presented in Fig. 1. The encoder has one input block of n bits and ν memory blocks of n bits. The encoder state is defined by the binary value of the ν memory blocks of n bits. At each time t ∈ Z, all the bits of a block are replaced by the n bits of the previous block. The i th bit of the j th block x t-j+1 i , with i = 1 . . . n and j = 1 . . . ν + 1, is associated to n T multiplier coefficients

g k i,j ∈ Z 2 n , k = 1 . . . n T ,
where n T is the number of transmit antennas. With these n T × n(ν + 1) coefficients, we obtain the generator matrix G G G with n T lines and ν + 1 blocks of n columns:

G G G = [G 1 1 ...G 1 n |...|G ν+1 1 ...G ν+1 n ] (1)
where

G j i = [g 1 i,j ...g nT i,j ] T ∈ Z nT 2 n . At each time t, the encoder output y y y x t = y t 1 y t 2 ... y t nT T ∈ Z nT 2 n is given by y y y x t = G G Gx x x t (2)
where

x x x t = [x t 1,1 ...x t 1,n ..x t ν+1,1 ...x t ν+1
,n ] T is the extendedstate at time t of the L = n(ν +1) length shift register realized by the n input bits followed by the ν memory blocks of n bits.

In general, each encoder output y t k is mapped onto a 2 n -PSK signal given by:

s t k = exp(j π 2 n-1 y t k ) (3)
Each output signal s t k is sent to the k th transmit antenna. At each time t, the set of symbols transmitted simultaneously over a fading channel is given by s s s

t = s t 1 s t 2 ...s t nT T .
An encoder can also be represented by a trellis, as shown in Fig. 2 for 4-PSK 4 states STTC. In the trellis, the states are represented by the points and the transitions between the states by the lines. Each transition corresponds to an extended-state. The vector y y y i ∈ Z nT 4 represents the MIMO symbol associated to an extended-state. The index i is computed as the decimal value of this extendedstate with x t 1,1 the least significant bit. In this example, the trellis corresponds to the generator matrix G G G = [y 1 y 2 |y 4 y 8 ].

In the general case, for 2 n -PSK STTCs, there are 2 n transitions originating from the same state or merging into the same state. Each MIMO symbol belongs to Z nT 2 n . The number of states is given by the number of points on one column of the trellis.

B. Design criteria

The main goal of the following design criteria is to find the codes which reduce the pairwise error probability (PEP) which is the probability that the decoder selects an erroneous sequence. It is possible to represent the transmitted frame with L f MIMO symbols beginning at time t = 0 by a n T × L f dimension matrix S S S = [s s s 0 s s s 1 ...s s s L f -1 ]. An error occurs if the decoder decides that another frame E E E = [e e e 0 e e e 1 ...e e e L f -1 ] is transmitted. Let define the n T × L f difference matrix B B B = E E E -S S S:

B B B =    e 0 1 -s 0 1 . . . e L f -1 1 -s L f -1 1 . . . . . . . . . e 0 nT -s 0 nT . . . e L f -1 nT -s L f -1 nT    (4)
The n T ×n T product matrix A A A = B B BB B B * is introduced, where B B B * denotes the hermitian of B B B. We define r = min(rank(B B B)) where B B B is computed for all pairs of coded frames (E E E, S S S). The design criteria depend on the value of the product rn R .

The product rn R ≤ 3: In this case, for a slow Rayleigh fading channel, two criteria have been proposed [START_REF] Tarokh | Space-time codes for high data rate wireless communication: Performance criterion and code construction[END_REF] to reduce the PEP.

• A A A has to be a full rank matrix for any codewords E E E, S S S.

• For any codewords, the determinant of A A A must be maximized. The product rn R ≥ 4: In [START_REF] Chen | Improved space-time trellis coded modulation scheme on slow fading channels[END_REF], it is shown that for rn R ≥ 4, the PEP is minimized if the sum of all the eigenvalues of the matrix A A A is maximized. Since A A A is a square matrix, the sum of all the eigenvalues is equal to the trace of the matrix A A A:

tr(A A A) = nT k=1 λ k = nT k=1   L f -1 q=0 e k t+q -s k t+q 2   (5)
In other words, the trace corresponds to the Euclidean distance between the frames E E E and S S S. Thus, in order to reduce the bit rate (BER) and the frame error rate (FER), we must maximize the Euclidean distance. In this paper, we consider only this design criterion.

III. COSET PARTITIONING FOR 4-PSK STTCS WITH n T

TRANSMIT ANTENNAS

A. Coset decomposition of Z nT 4

We consider the case of a 4-PSK 2 2ν states STTC with n T transmit antennas. Each MIMO symbol belongs to the group Z nT 4 . This group can be decomposed in two sets of cosets. Each coset is defined by

C p = p + C 0 with p ∈ Z nT 2 and C 0 = 2Z nT 2 . • The first set is E 0 = C 0 . This set is a normal subgroup of Z nT 4 with the property v = -v, ∀v ∈ E 0 . • The other set is E 1 = (p+C 0 ) with p ∈ Z nT 2 \[0 • • • 0] T . Each coset p+C 0 ∈ E 1 is relative to the element v = 2p ∈ E 0 .

B. Coset partitioning

The main goal of the coset partitioning is to design easily and quickly the best STTCs thanks to the first two rules of the set partitioning. The third rule of the set partitioning is not used to design the STTCs because there are no parallel paths in the STTCs. The first rule of the Ungerboeck's method specifies that each point of the MIMO constellation has the same number of occurrences. In [START_REF] Ngo | 4-PSK Balanced STTC with Two Transmit Antennas[END_REF], [START_REF] Viland | A new method to design balanced space-time trellis codes for several transmit antennas[END_REF], it has been observed that the first rule is verified by each good STTC. The STTCs verifying this first rule are called balanced codes. The coset partitioning allows to design balanced STTCs which respect also the second rule of the set partitioning: the Euclidean distance between the signals originating from the same state and merging into the same state must be maximized.

In [START_REF] Calderbank | New trellis codes based on lattices and cosets[END_REF], Calerbank et al. give an alternative to the set partitioning. The MIMO constellation can be seen as a finite subgroup of Z nT 2 n . This group is partitioned in cosets. The goal of this method is that all the transitions originating from or merging into the same state belong to the same coset. The elements of these cosets must be separated by the largest Euclidean distances.

For a 4-PSK 2 2ν states STTC, the generator matrix has ν +1 blocks of 2 columns. To design the STTCs with the coset partitioning, we propose that the 2 columns of each block can generate a subgroup of Z nT 4 . Therefore, for each block k, the following rule must be respected:

• The first column G k 1 must belong to C 0 with 1 ≤ k ≤ ν + 1.
• The column G k 2 with 1 ≤ k ≤ ν + 1 must belong to the coset relative to the first column G k 1 or to C 0 . After these choices, it is possible to the columns and the lines within each block to obtain codes which respect the coset partitioning. Further on, we search the codes with the best trace. new codes for 32/64 states with 3 transmit antennas and 4/8/64 states with 4 transmit antennas. Their minimum traces are compared to the traces of corresponding Chen's codes proposed in [START_REF] Chen | Space-time trellis codes with two, three and four transmit antennas in quasi-static flat fading channels[END_REF]. For each new code, the Euclidean distances between the MIMO symbols merging into or originating from the same state respectively are better than the corresponding Chen's codes.

n T 2 2ν Code G G G Trace 3 32 Chen et al.    0 2 2 1 1 2 0 2 2 2 3 2 2 3 0 0 2 0 3 2 2 1 0 0    24 New 1    0 2 2 1 2 1 0 1 2 1 2 1 0 2 0 2 2 1 2 3 2 1 0 3    24 64 Chen et al.    0 2 3 2 3 0 3 2 2 2 1 2 3 0 2 0 2 0 0 2 2 3 1 1    28 New 2    3 2 1 2 1 2 2 0 3 2 2 0 1 2 1 2 2 0 2 0 1 2 3 2    32 4 4 Chen et al.      0 2 1 2 2 3 2 0 2 3 3 2 0 2 2 1      20 New 3      0 2 2 1 2 1 2 3 2 3 2 3 2 1 0 2      20 8 Chen et al.      2 2 2 1 0 0 2 0 1 2 0 2 2 1 1 0 0 2 2 3 2 3 0 1      26 New 4      2 3 2 1 0 1 2 1 2 1 0 1 2 1 2 1 0 3 0 2 2 3 0 3      26 64 Chen et al.      0 2 3 2 3 0 3 2 2 2 1 2 3 0 2 0 2 0 0 2 2 3 1 1 1 2 2 0 2 1 3 2      38 New 5      2 3 2 1 2 3 0 2 0 2 2 1 2 3 2 1 2 3 2 3 0 2 2 1 2 1 0 2 2 1 2 1     

TABLE I NEW 4-PSK CODES BASED ON THE EUCLIDEAN DISTANCE CRITERIA

For the simulation, two receive antennas are considered. The channel is a slow Rayleigh fading channel and each frame has 130 MIMO symbols. The channel coefficients are assumed to be known at the decoder. The decoding is performed by the Viterbi's algorithm. We observe the performance of a 4-PSK 32 states STTC with 3 transmit antennas and 64 states STTCs with 3/4 transmit antennas in Fig. 5 and4-PSK 4/8 states STTCs with 4 transmit antennas in Fig. 6. Each new code outperforms slightly the corresponding Chen's code.

V. CONCLUSION

In this paper, an efficient method to design the best 4-PSK STTCs with n T transmit anntennas has been presented. This new method is based on the set partitioning proposed by Ungerboeck and an alternative of this work proposed by Calderbank. Based on this new design method, new 4-PSK STTCs with 3 and 4 transmit antennas have been proposed.

Fig. 1 .

 1 Fig. 1. Space-time trellis encoder for 4-PSK and n T transmit antennas

Fig. 2 .

 2 Fig. 2. 4 states 4-PSK STTC

Fig. 5 .Fig. 6 .

 56 Fig. 5. Performance of 4-PSK STTCs with 3/4 transmit antennas

C. Example of a 4-PSK 16 states STTC with n T transmit antennas

the case of a 4-PSK 16 states STTC with n T transmit antennas, the matrix G G G has 3 blocks of 2 columns:

. Each column belongs to the group Z nT 4 . The first step to design the code with the coset partitioning is to select the cosets originating from the same state and merging into the same state, i.e. the elements of the blocks B 1 and B 3 . These blocks of the generator matrix must generate respectively the subgroups Λ F 1 = {y y y 0 , y y y 1 , y y y 2 , y y y 3 = y y y 1 + y y y 2 mod 4} and Λ M 1 = {y y y 0 , y y y 16 , y y y 32 , y y y 48 = y y y 16 +y y y 32 mod 4}. The set Λ ν+1 of generated MIMO symbols can be decomposed into two sets of cosets Λ ν+1 /Λ F 1 and Λ ν+1 /Λ M 1 where each coset corresponds to the set of transitions originating from the same state and the transitions merging into the same state respectively. The trellis given in Fig. 3 corresponds to a 4-PSK 16 states STTC designed with the coset partitioning.

The second step is the selection of the columns G 2 1 and G 2

2 . These vectors must also generate a subgroup. Thus, it is possible to represent a simplified trellis, as shown in Fig. 4.

In this case, the points x 3,1 x 3,2 ∈ {00, 01, 10, 11} of Fig. 4 are defined as the 'states of level 2'. Each state of level 2 x 3,1 x 3,2 is constituted by 4 real states

The new lines correspond to the 'transitions of level 2' which are constituted

Fig. 3. 16 states 4-PSK STTC with cosets

2 n (with y y y 4 + y y y 8 = y y y 12 mod 4). Thus, a partition chain is obtained:

The Euclidean distances between the elements of Λ F 2 must be maximized to obtain good codes thanks to the choice of y y y 4 and y y y 8 . We can also make a chain partition with the MIMO symbols merging into the different levels of states:

Each element of Λ ν+1 /Λ M 2 corresponds to one coset of MIMO symbols merging into a same state of level 2. As shown in Fig. 4,Λ M 2 is given by: Λ

Thus, Λ M 2 is already defined by the previous selections.

Finally, we permute the columns of each block to find the codes with the best trace.

Remark: Some codes have their first i null columns in the (ν + 1) th block with 0 < i < n. The number of states is 2 nν-i . In this case, the columns which generate the subgroup Λ M 1 are the i first columns of the ν th block and the last n -i columns of the (ν + 1) th block.

IV. NEW CODES AND THEIR PERFORMANCE

Using the proposed design method, new 4-PSK codes are obtained for 3 and 4 transmit antennas. Table I shows these


Didier Guyomarc'h

Gaëtan Hagel

Cédric Zumsteg

Martina Knoop

Some aspects of simulation and realization of an optical reference cavity

Keywords: numbers: 42.60.Da Resonators, cavities, amplifiers, arrays, and rings, 42.62. Laser applications, 07.05.Fb Design of experiments

. We have designed a comparable vertical cavity with an overall length of 150 mm resulting in a Free Spectral Range of 1GHz. Optimisation of the cavity design has been carried out with a Finite-Elements Method, leading to expected relative length variations below 10 -14 under the influence of gravity acceleration (1 g). The variation of different geometric parameters has been studied. The analysis of the different noise sources shows that, for a regime superior to a tenth of a hertz, the fast linewidth of the laser will not be limited by the cavity characteristics.

I. VIBRATION INSENSITIVE OPTICAL REFERENCE CAVITY

Frequency metrology in the optical domain is made by locking a spectrally pure laser source to the ultra-narrow transition of an ensemble of atoms or a single trapped ion. The recording time of the error signal which is fed back onto the laser, which serves as local oscillator, depends on the interrogated system, it can be of the order of a second for single ions. For all times shorter than that this laser should be stable to better than one atomic linewidth which is of the order of one Hertz for the various systems.

Extremely well isolated, high-finesse optical cavities are used as frequency references to assure the stability of visible lasers for timescales up to one second, they also allow to reduce the laser's linewidth to the order of the hertz [2]. Recently, new geometries and mounting configurations have been proposed for these cavities in order to reduce vibrational effects which tend to deform the cavity and thus can shift its resonance frequencies [1,3,4,5].

In this work, we consider a vertically mounted cavity. Minimal length variations of the cavity can be achieved by choosing a tapered form for the cavity spacer. The gain with respect to a horizontally mounted, cylindric cavity can be as large as two orders of magnitude and with less stringent machining conditions [1,6]. Vibrationally insensitive mounting is made by supporting the cavity near its midplane. As a matter of fact, under upward acceleration the upper part of the cavity will be compressed while the lower part tends to expand. An ideally supported cavity will show a perfect compensa- * Electronic address: Martina.Knoop@univ-provence.fr tion of both effects. Optimisation of the geometry and appropriate choice of the supporting points can be made by numerical simulation of the cavity using a finite element analysis (FEA).

Here, we present details of the FEA, which has been carried out in a similar way to the one described in [6]. In particular, Chen et al. have also demonstrated that the simulation in the range below some tens of kHz can be made by a static approach, as the wavelength of the excited eigenfrequencies is estimated to be an order of magnitude larger than the dimensions of the cavity. In the present work, we have investigated the influence of different aspects of the spacer's geometry, as there are the variation of the cone angle, the position and the angle of the evacuation bores, as well as the influence of chamfers. Furthermore, we have estimated the overall thermal noise of the designed cavity, and derived its limit frequencies fluctuations at a time scale of one second. Different noise sources, as well as limitations in the stabilization method, will determine the final linewidth of the laser locked onto this cavity. In the present work, we concentrate on contributions which are due to the cavity's mechanical or thermal properties only. This gives a lower limit for the estimate of the final laser linewidth, with the goal to design a cavity which will be not the limiting factor in the final laser stabilisation stage.

Our application is the interrogation of a single Calcium ion stored in a miniature trap for metrological applications [7]. Excitation of the ultra-narrow electrical quadrupole transition at 729 nm has been made by a broadarea laser in an extended cavity set-up [8,9], before using the actual set-up of a lab-built titanium-sapphire laser at 729 nm which will be locked by the Pound-Drever-Hall method [10] onto a high-finesse (F ≃ 10 5 ), fixed-length optical reference cavity. We aim an inherent stability of better than 1 Hz/ √ Hz for the clock laser. For practi- To guarantee a high degree of mechanical as well as thermal stability the cavity spacer is made of ultralow expansion glass (Corning ULE ), whereas the mirror substrates are from fused silica [11]. The optimized design of this reference cavity is the subject of this paper.

II. FINITE ELEMENT SIMULATION

We have chosen the vertically mounted, tapered cavity geometry which has been shown to be vibrationally insensitive [1,6]. The geometry of the designed cavity is shown in Figure 1, it has been machined from a single piece of Corning ULE . The mirrors are optically contacted to the spacer, they have a diameter of 25.4 mm and a thickness of 6 mm. The FEA takes into account two plane fused silica mirrors, even though one of them has a radius of curvature of 1 m, the minimal geometrical difference is negligible. The central bore has a diameter of 10 mm, giving ample space for the cavities' TEM00 mode which has a calculated waist diameter on the mirrors below 0.5 mm. Three bore holes in the upper part of the cavity allow evacuation of the inner part for the cavity which is destined to be mounted in a vacuum vessel. The cavity is held vertically by three ceramic posts which support the central collar. The aim is to support the cavity in a plane which corresponds to the vibrational "neutral fiber" of the piece, and to therefore minimize its sensitivity to vertical vibrations.

FEA has been used to optimize the geometry of the ULE spacer as well as to exactly determine the position of the equilibrium support plane. This latter has been determined in a two-step procedure. In a first phase, simulations of the cavity geometry have been carried out to determine the optimal shape and dimensions, for a fixed overall length of 150 mm. The cavity has then been machined, and on the finished spacer all dimensions have been measured interferometrically to a hundredth of a millimeter. In a second step, the cavity has been updated numerically with the measured values, and the FEA carried out once again to precisely determine the equilibrium plane of support.

All finite element simulations have been carried out using the Cosmos module of the Solidworks software [12] on a personal computer. The present analysis fixes the plane of support and calculates the deformation of the cavity under vertical acceleration of 1 g. This acceleration is assumed uniform and constant in the relevant frequency range up to 10 kHz. Chen et al. [6] have shown that for a tapered cavity spacer the influence of horizontal acceleration is at least two orders of magnitude lower than vertical acceleration. A grid of probe points on crucial parts of the cavity (essentially on the mirror surfaces, see figure 1) has been defined. Their positional deviation allows to measure the deformations of the cavity spacer in a quantitative way.

To determine the optimal support plane C e with precision, two points C 1 , C 2 (see figure 1) sufficiently apart are chosen, then the respective length variation of the spacer is calculated. The results are linearly interpolated to determine the equilibrium support plane C e , corresponding to a zero theoretical length variation. Throughout simulations, the collected fractional length variations are inferior to 3 × 10 -12 (down to values of 5 × 10 -13 ). In terms of vertical acceleration sensitivity this corresponds to a domain below 1.2 kHz/g at 729 nm.

III. SIMULATION RESULTS

A first series of simulations has determined an optimized tapered cavity with a length of 150 mm, and an outside cone angle α/2 of 14 degree (see Figure 1), we will use this geometry as a starting point in the following.

Our aim is to investigate the dependence of the cavity geometry on different geometrical aspects, in order to choose a cavity design with a reduced sensitivity to machining uncertainties. For a quantitative study of the sensitivity of the geometry to the variation of a given geometric parameter, a parameter S has been defined to be S = |(∆L 2 -∆L 1 )/(C 2 -C 1 )|, where small changes in the height of the probe points C i give rise to length variations of the spacer ∆L i . We have chosen to vary C i for ±0.01 mm and ±0.1 mm.

In order to optimize computing ressources, the cavity is cut along its symmetry axes, and only one third of it is simulated. Computer performance and memory limit the minimum mesh size to 1 mm. Convergence of simulations to a hundredth millimeter can be obtained with mesh sizes as large as 3 mm by manually forcing a tightened mesh distribution insisting on critical aspects as for example the support points, and the evacuation bores.

The cone angle α/2 is the outside angle of the two halves of the spacer with respect to the central bore. A cylindrical cavity would have an angle of 0 • . Figure 2 shows the variation of position of the equilibrium plane as a function of the outside cone angle. Lower cone angles tend to show a smaller sensitivity, a result which is in agreement with the findings of [6], but the overall variation is very small. The differential minimal displacement of the mirrors can be made to reach values below 10 -11 . The realisation of the ULE cavity by a milling machine inevitably creates rough edges on the inflexion points of the complex shape. In glass machining, beveling is often made by hand, making it difficult to estimate the influence of the different chamfers. We have tested the influence of chamfers 0.6×0.6 mm 2 on the precision of the proposed simulation. Suppressing chamfers in the simulation of a cavity results in a theoretical displacement of the equilibrium plane of 36 µm with respect to the cavity where the chamfers are taken into account. This tiny value is of course negligible compared to the machining precision of 0.1 mm.

Figure 3 shows the effect of position and angle of the three evacuation bores on sensitivity and reference plane. The left part of the figure represents the angle of the holes with respect to the central reference plane, 0 degree corresponds to holes perpendicular to the central bore, an angle of 14 degree corresponds to holes which are drilled in a right angle to the outside of the cone. The observed sensitivity is of the same order of magnitude for both configurations. This is also true for the variation of the height of the evacuation bore (with 0 angle). Nevertheless, it is evident that the absolute value of the equilibrium plane C e varies for these different geometries.

In conclusion, among the studied geometric parameters, the variation of the cone angle is the most critical parameter during realization of the cavity spacer. The obtained simulations give very precise results, and metrology of the cavity will result in values precise to a hundredth of a mm. However, the machining process of the glass spacer and mirrors is limited to a precision of a tenth of a mm. Moreover, cone angles or angled bores are often realized with less precision.

In order to minimize errors during the machining process, and to be able to achieve the aimed precisions, an optimized realization protocol would first drill all the bores along axes or perpendicular to axes on a cylindrical spacer. The outside angle of the spacer would only be machined in a consecutive step. Precise metrology of the spacer would then allow to calculate the ideal support plane with precision, before milling it in a last step.

IV. ESTIMATION OF THE LIMIT LINEWIDTH

Considering the cavity only, without a laser-beam introduced, a major part of the noise is due to inherent mechanical thermal fluctuations. We have estimated the thermal noise limit which affects the ultimate response of the designed cavity. Following the study by Numata et al. [11], the configuration to reach minimal thermal noise has been chosen, which consists of an ULE spacer with fused silica mirror substrates. The thermal noise limit can then be estimated by the sum of the spectral noise density contributions coming from the spacer body (G sp ), the mirror substrates (G sub ), and the mirror coatings (G c )

G total (f ) = G sp (f ) + 2 [G sub (f ) + G c (f )] (1) = - 4k B T 2πf L 3πR 2 E sp Φ sp + 2(1 -σ 2 ) √ πω 0 E sub Φ sub + (1 -2σ)(1 + σ) 4d πω 2 0 E c Φ c ( 2
)
where T is the temperature, chosen to be 300 K, d the diameter of the mirror substrate and ω 0 the waist of the cavity mode. The non-cylindrical geometry of the cavity spacer leads us to choose conservative values for the spacer length, L=0.15m, and radius R=0.03m. Young's modulus, E, and the Poisson ratio, σ, describe the elastic and compressional behaviour, they depend on the chosen material just as the mechanical loss factor, Φ, independent of frequency. For ULE these values are E ULE = 6.76 × 10 10 P a, σ ULE = 0.17 and Φ ULE = 1/(6×10 4 ), the values for fused silica are slightly different with E F S = 7.27 × 10 10 P a, σ F S = 0.16 and Φ F S = 10 -6 [13]. The resulting value for the complete cavity is G total (f ) = 2.5 × 10 -17 m/ √ Hz, where by far the largest contributions come from the mirror coatings and substrates.

We have checked that all other noise sources in the laser stabilisation are negligible to the presented values. Variations of the refractive index of air due to pressure fluctuations are largely reduced as the cavity is mounted in a vacuum vessel. At a residual pressure of 10 -6 mbar, they will contribute to the noise spectral density by less than 10 -23 / √ Hz (10 -8 Hz/ √ Hz fractional). The shot noise spectral density of a photodiode (required for the electronic lock) is below 8×10 -5 Hz/ √ Hz for a collected input power of P = 1mW and a typical quantum efficiency of 0.9. And finally, the intensity fluctuations of a laser coupled into a cavity of finesse 10 5 will give rise to thermal effects in the mirror coatings as well as a radiation pressure shift. While the first effect is negligible small due to very low absorption values, the second term sums up to a frequency fluctuation of 0.05 Hz for 1 mW of laser power fluctuating less than 1% [START_REF] Bergquist | Proceedings of the Int. School of Physics "Enrico Fermi[END_REF].

Assuming that the contributions of equation 2 are the limiting noise factors for the performances of the reference cavity we can use Halford's theorem [START_REF] Halford | Proceedings Frequency Standards and Metrology Seminar[END_REF] +∞ ∆ν/2

G total (f ) f 2 df = 2 π (3)
to estimate the limit laser linewidth ∆ν from the frequencies' spectral noise density G total (f ). The above-cited values correspond to a limit linewidth of 120 mHz.

Recent works on highly stabilized visible lasers discuss the lock onto ULE cavities with the aim to work at the material's thermal expansion's inflexion point in order to minimize thermal drifts [5,[START_REF] Alnis | [END_REF]17]. Active thermal stabilisation of the overall set-up allows to approach this inflexion point with a typical accuracy of about 10 mK. The resulting thermal drift is of the order of 2-4 Hz/mK. Three additional stages of passive thermal shielding allow to integrate temperature fluctuations on the cavity to reach an stability of the order of 10 µK per second. The corresponding linewidth fluctuations are thus much smaller than the above discussed thermal noise features due to mechanical loss.

V. CONCLUSION

In this presentation of the design of a vibrationalinsensitive, high-finesse optical reference cavity, we have investigated the sensitivity of the cavities' geometry to some conceptual details. With respect to the design of the cavity, the outside angle of the spacer (determining the shape) is the most sensitive parameter among those studied here. The presented cavity has a thermal noise limit corresponding to a linewidth of ∆ν = 0.12 Hz, if the cavities' temperature can be stabilized to within 10 mK of its CTE inflexion point. This critical value is often shifted to very low or even negative temperatures for a cavity with fused silica mirrors, making the temperature stabilisation a more complex operation. The addition of an ULE-ring on the mirror substrates is a means to shift the operational temperature into an easily accessible domain [18].

The presented values have to be compared to the spectral linewidth of the cavities' Airy peaks of a few kHz. Advanced frequency control methods have their maximum of gain in the spectral bandwidth of the cavity peak, they allow linewidth reductions of more than three orders of magnitude for the realisation of 1Hz-linewidth lasers [1,3,10,[START_REF] Bergquist | Proceedings of the Int. School of Physics "Enrico Fermi[END_REF]19]. The presented linewidth estimation is only one order of magnitude below these results, demonstrating that the cavity is not the limiting factor. However, this illustrates the importance of the choice of mirror and spacer materials as well as the careful design of the cavity.

Fig. 1 :

 1 Fig. 1: Typical geometry of the simulated cavity. Only a third of the spacer is modeled, the simulations take into account the symmetry of the spacer. For detailed explanations see text

Fig. 2 :

 2 Fig. 2: (Color online) Variation of the half cone angle of the spacer body. The upper part of the image shows the modification of the spacer's shape with increasing cone angle. The lower part represents the sensitivity S (bullets, right axis) to the variation of the cone angle and is of the order of 10 -11 , different points represent a different Ci in the simulation. The resulting variation of the height of the support plane (triangles, left axis) is inferior to a tenth of mm.

Fig. 3 :

 3 Fig. 3: (Color online) Variation of the angle (left graph) and position (right graph) of the evacuation bores. Triangles indicate the calculated position of the equilibrium plane on the outside ordinate (the line is a guide to the eye), while the spherical points display the calculated sensitivity for the different Ci on the central ordinate.