4 Cyclic division algebras.

This chapter is devoted to the mathematical background necessary for building codes from cyclic division algebras. While introducing the definitions and results that we need, we keep in mind to emphasize the coding applications, alternating the theory with examples. The fist section aims at introducing the notion of division algebra, the key concept for Space Time coding, since it gives a way of building fully-diverse Space-Time codes. The Alamouti code is used as an illustration. In order to increase the throughput of the codes, we introduce algebras over number fields. Number fields will be shown to allow encoding of QAM and HEX constellations. Then a particular family of algebras, namely cyclic algebras built over number fields, will yield, for n transmit antennas, n x n Space-Time codewords that send [n.sup.2] information symbols encoded into [n.sup.2] signals. We further exploit the algebraic properties of a number field, and work in its ring of integers, which results, in terms of coding, in the non-vanishing determinant property. Finally, rings of integers of number fields can be used to build algebraic lattices. The lattice structure helps us to control the transmitted energy when encoding the Space-Time codes.

4.1 Fields and Algebras

The goal of this fist section is to provide definitions and examples for algebraic structures such as ring and field, so as to end up with the notion of algebra. We end the section by describing the algebra of Hamilton's quaternions, which will be an example of division algebra.

4.1.1 Commutative and Non-Commutative Fields

Let Z be the set of rational integers { ..., -2,-1,0,1,2 .... }, Q be the set of rational numbers Q = {a/b a, b [not equal to] 0 [member of] Z}, R denote the real numbers, and C the complex numbers.

Definition 4.1. Let A be a set endowed with two internal operations denoted by + and .

A x A [right arrow] A (a, b) [right arrow] a + b and

and

A x A [right arrow] A (a,b) [right arrow] a * b

The set (A, +, -) is a ring if

(1) (A,+) is an Abelian (or commutative) group,

(2) the operation * is associative, i.e., a * (b * c) = (a * b) * c for all a, b, c [member of] A and has a neutral element 1 such that 1 * a = a * 1 for all a [member of] A,

(3) the operation * is distributive over +, i.e., a * (b + c) = a - b + a * c and (a+b) * c = a * c + b * c for all a,b,c [member of] A.

The ring A is commutative if a * b = b * a for all a, b [member of] A. The set of elements of A that are invertible for the operation * is called the set of units of A, and is denoted by A *.

The set Z is easily checked to be a ring. Its units are Z* = {1, -1}.

Definition 4.2. Let A be a ring such that A* = A\{0}. Then A is said to be a skew field or division algebra. If A is moreover commutative, it is said to be a field.

Looking the other way round, a division algebra is a non-commutative field. Division algebras will be our object of study for the rest of this chapter.

4.1.2 Algebras and Division Algebras

The most well known examples of fields are the sets Q, R, and C. They are all commutative. In this section, we will present a non-commutative field, the Hamilton's quaternions, which will be used to build the Alamouti code.

Combining the more familiar notion of vector space with the one of ring, we arrive at the notion of algebra.

Definition 4.3. An algebra A is a set over a field K with operations of addition, multiplication, and multiplication by elements of K that have the following properties:

(1) A is a vector space with respect to addition and multiplication by elements of the field.

(2) A is a ring with respect to addition and multiplication.

(3) ([lambda]a)b = a([lambda]b) = [lambda](ab) for any [lambda] [member of] K, a, b [member of] A.

The set [M.sub.n] (R) of n x n matrices with entries in R is an algebra over R. It is a vector space of dimension [n.sup.2] over R. It is a non-commutative ring with respect to the usual addition and multiplication of matrices.

The rest of this section is devoted to the most famous example of non-commutative field, the Hamilton's quaternions. It also has a structure of algebra, and will fist be presented as such. Let {1,i,j,k} be a basis for a vector space of dimension 4 over R. These elements satisfy the rules [i.sup.2] = -1, [j.sup.2] = -1, [k.sup.2] = -1, and k = ij = -ji. The Hamilton's quaternions is the set H defined by

H = {x + yi + zj + wk | x,y,z,w [member of] R}.

It has a structure of ring, since addition and multiplication are well-defined, though one has to be careful about the non-commutativity when doing computations! See Table 4.1 for the multiplication table.

Let us now prove that the Hamilton's quaternions are a division algebra, that is, every nonzero element q E H is invertible. Like for complex numbers, one can define the conjugate of a quaternion q = x + yi + zj + wk as

[bar.q] = x - yi - zj - wk.

It is a straightforward computation to check that

q[bar.q] = [x.sup.2] + [y.sup.2] + [z.sup.2] + [w.sup.2].

We call [bar.q]q = q[bar.q] = |g|2 = N(q) the norm of a quaternion. Since x, y, z, w [member of] R, q[bar.q] > 0, unless x = y = z = w = 0. Thus the inverse of a quaternion q is given by

[q.sup.-1] = [bar.q]/q[bar.q],

and all nonzero elements have an inverse.

We end this section by motivating why algebraic structures such as Hamilton's quaternions are of interest for coding purposes. Since coding for multiple antennas involves sending matrices, let us fist see that there is a natural correspondence between elements of H and 2 x 2 matrices with coefficients in C.

Note that any quaternion q - x + yi + zj + wk can be written as

(x + yi) + (zj - wji) = [[alpha].sub.q] + j[[beta].sub.q.

where [[alpha].sub.q] = x + yi [member of] C, [[beta].sub.q] = z - wi [member of] C. Thus H is a right C-vector space (that is scalars multiply on the right), with C-basis {1, j}. In this basis, q = ([[alpha].sub.q],[[beta].sub.q]). Note that H is not a C-algebra. Consider the left multiplication by v, that is [m.sub.v](q) = vq. In the basis {1, j}, we have

[m.sub.i] = (i 0 0 -i), [m.sub.j] = (0 -1 1 0), [m.sub.k] = (0 -i -i 0).

Check for example how k multiplies (on the left) the basis elements {1,j}

k(1,j) = (k,kj) = (ij, ijj) = (-ji,-i) = (1, j) (0 -i -i 0).

More generally, if x, y [member of] R, we have

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE ASCII.]

Thus, for a general quaternion v = [[alpha].sub.v] + j[[beta].sub.v] ([[alpha].sub.v], [[beta].sub.v] [member of] C) we have

[m.sub.v] = ([[alpha.sub.v] -[[beta].sub.v] [[beta].sub.v] [[bar.[alpha].sub.v] (4.1)

This construction gives a correspondence between an element v in the Hamilton's quaternions and a 2 x 2 matrix with coefficients in C of the form (4.1).

Example 4.1 (The Alamouti code). Let C be the following set of matrices

[MATHEMATICAL EXPRESSION NOT REPRODUCIBLE IN ASCII.]

It corresponds to the codewords of the Alamouti code, introduced in Section 3.4.3, where the code has been shown to be fully-diverse. The full-diversity can also be derived from the Hamilton's quaternions being a division algebra as follows.

Let v = [alpha] + j[beta][member of] H. If X = [m.sub.v] [member of] C, then det(X) = [|[alpha]|.sup.2] + [|[beta]|.sup.2] = N(v),

the norm of the quaternion v. Thus N(v) = 0 [left and right arrow] v = 0.

4.2 Algebras on Number Fields

In the previous section, we gave as example of algebra the Hamilton's quaternions, which are based on the field R. In this section, we are interested in building algebras over number fields.

4.2.1 Introducing Number Fields

Consider the set of rational numbers Q, which is easily checked to be a field. Other fields can be built starting from Q. Take for example the element i, such that [i.sup.2] = -1, which is not an element of Q. One can build a new field "adding" i to Q, the same way i is added to R to create C. Note that in order to make this new set a field, we have to add all the multiples and powers of i. We thus get a new field that contains both Q and i, and only Q-linear combination of i, that we denote by Q(i). We call it a field extension of Q. Note that we can iterate this procedure, and start with the field Q(i). Then, adding for example the element [square root of (5)] (which does not belong to Q(i)), its multiples and powers, we get a new field, denoted by (Q(i, [square root of (5)]). Thus (Q(i, [square root of (5)]) is an extension of Q(i), which is itself an extension of Q. Let us formalize this procedure.

Definition 4.4. Let K and L be two fields. If K [subset] L, we say that L is a field extension of K. We denote it by L/K.

It is useful to note that if L/K is a field extension, then L has a natural structure of vector space over K, where vector addition is addition in L and scalar multiplication of a [member of] K on v [member of] L is just a v [member of] L. For example, an element x [member of] Q(i) can be written as x = a + ib, where {1, i} are the basis "vectors" and a, b [member of] Q are the scalars. The dimension of Q(i) as vector space over Q is two. Similarly, an element of (Q(i, [square root of (5)]) can be written w = x + y [square root of (5)], with x, y [member of] Q(i), or also w = (a + ib) + [square root of (5)] (c + id), a, b, c, d [member of] Q. Thus, (Q(i, [square root of (5)]) is a vector space of dimension two over Q(i), or of dimension four over Q. It is often useful to draw a picture to see the hierarchy of fields (see Figure 4.1).