**Are you an EPFL student looking for a semester project?**

Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.

Publication# Algebraic methods for channel coding

Abstract

This work is dedicated to developing algebraic methods for channel coding. Its goal is to show that in different contexts, namely single-antenna Rayleigh fading channels, coherent and non-coherent MIMO channels, algebraic techniques can provide useful tools for building efficient coding schemes. Rotated lattice signal constellations have been proposed as an alternative for transmission over the single-antenna Rayleigh fading channel. It has been shown that the performance of such modulation schemes essentially depends on two design parameters: the modulation diversity and the minimum product distance. Algebraic lattices, i.e., lattices constructed by the canonical embedding of an algebraic number field, or more precisely ideal lattices, provide an efficient tool for designing such codes, since the design criteria are related to properties of the underlying number field: the maximal diversity is guaranteed when using totally real number fields and the minimum product distance is optimized by considering fields with small discriminant. Furthermore, both shaping and labelling constraints are taken care of by constructing Zn-lattices. We present here the construction of several families of such n-dimensional lattices for any n, and compute their performance. We then give an upper bound on their minimal product distance, and show that with respect to this bound, existing lattice codes are optimal in the sense that no further significant coding gain could be reached. Cyclic division algebras have been introduced recently in the context of coherent Space-Time coding. These are non-commutative algebras which naturally yield families of invertible matrices, or in other words, linear codes that fulfill the rank criterion. In this work, we further exploit the algebraic structures of cyclic algebras to build Space-Time Block codes (STBCs) that satisfy the following properties: they have full rate, full diversity, non-vanishing constant minimum determinant for increasing spectral efficiency, uniform average transmitted energy per antenna and good shaping. We give algebraic constructions of such STBCs for 2, 3, 4 and 6 antennas and show that these are the only cases where they exist. We finally consider the problem of designing Space-Time codes in the noncoherent case. The goal is to construct maximal diversity Space-Time codewords, subject to a fixed constellation constraint. Using an interpretation of the noncoherent coding problem in terms of packing subspaces according to a given metric, we consider the construction of non-intersecting subspaces on finite alphabets. Techniques used here mainly derive from finite projective geometry.

Official source

This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.

Related concepts

Loading

Related publications

Loading

Related publications (7)

Loading

Loading

Loading

Related concepts (25)

Algebraic geometry

Algebraic geometry is a branch of mathematics which classically studies zeros of multivariate polynomials. Modern algebraic geometry is based on the use of abstract algebraic techniques, mainly fro

Algebra

Algebra () is the study of variables and the rules for manipulating these variables in formulas; it is a unifying thread of almost all of mathematics.
Elementary algebra deals with the manipulation

Commutative algebra

Commutative algebra, first known as ideal theory, is the branch of algebra that studies commutative rings, their ideals, and modules over such rings. Both algebraic geometry and algebraic number the

This thesis is concerned with computations of bounds for two different arithmetic invariants. In both cases it is done with the intention of proving some algebraic or arithmetic properties for number fields. The first part is devoted to computations of lower bounds for the Lenstra's constant. For a number field K the Lenstra's constant is denoted Λ(K) and defined as the length of the largest exceptional sequence in K. An exceptional sequence is a set of units in K such that for any two among them their difference is a unit as well. H.W. Lenstra showed that if Λ(K) is large enough – bigger than a constant depending on the degree and the discriminant of K – then the ring of integers of K is Euclidean with respect to the norm. Using computer software PARI/GP and some algorithms from graph theory we construct exceptional sequences in number fields having a small discriminant. These exceptional sequences yield lower bounds for Lenstra's constant which are large enough to prove the existence of 42 new Euclidean number fields of degree 8 to 12. The aim of the second part of this thesis is proving upper bounds for the torsion part of the K-groups of a number field ring of integers. A method due to C. Soulé yields bounds for the torsion of these K-groups depending on an invariant of hermitian lattices over number fields. Firstly we describe some properties of rank one hermitian lattices, especially of ideal lattices. Secondly we apply these properties to arbitrary rank hermitian lattices and this implies a significant improvement of the upper bounds for their invariants and accordingly for the torsion of K-groups. The progress mainly achieves much lower contributions of the number field attributes, particularly the degree and the absolute discriminant.

This thesis deals with the study of ideal lattices over number fields. Let K be a number field, which is assumed to be CM or totally real. An ideal lattice over K is a pair (I,b), where I is a fractional ideal of K and b : I × I → R is a symmetric positive definite bilinear form such that b(x, y) = Tr(αxy) for a totally positive α ∈ K ⊗ R. The ideal lattice defined previously will be denoted by (I,α). In the first part, we will focus on constructing modular lattices over number fields. In particular the case of cyclotomic fields will be treated more carefully. A modular lattice is a lattice which is similar to its dual lattice. H.-G. Quebbemann introduced this notion in 1995 and in 1997, and he also defined a notion of analytic extremality for these lattices. It seemed promising to look for ideal lattices which were modular. This investigation led to the introduction of Arakelov modular lattices. This notion has turned out to be very interesting. If K = Q(ζn ) is a cvclotomic field, then the set of levels ℓ for which there exists an Arakelov modular lattice of level ℓ over Q(ζn ) is explicitly given in this thesis. Moreover, assume that K is a CM field, and that we are given an Arakelov modular lattice (I,α) of level ℓ over K. Under an assumption on K (which is satisfied for cyclotomic fields), we describe a way to compute all the Arakelov modular lattices of level ℓ over K. In the second part of this thesis, a construction is introduced which enables us to associate a totally real field K' to a given CM-field K. This field K' has the following property : if (I,α) is an ideal lattice over K. where I is an ambiguous ideal, then there exists an ideal lattice over K' isometric (as a lattice) to (I,α). This leads to the construction of several classic lattices over totally real fields. It also enables us to bound the Euclidean minimum of the field K' with respect to that of the field K.

K-Theory was originally defined by Grothendieck as a contravariant functor from a subcategory of schemes to abelian groups, known today as K0. The same kind of construction was then applied to other fields of mathematics, like spaces and (not necessarily commutative) rings. In all these cases, it consists of some process applied, not directly to the object one wants to study, but to some category related to it: the category of vector bundles over a space, of finitely generated projective modules over a ring, of locally free modules over a scheme, for instance. Later, Quillen extracted axioms that all these categories satisfy and that allow the Grothendieck construction of K0. The categorical structure he discovered is called today a Quillen-exact category. It led him not only to broaden the domain of application of K-theory, but also to define a whole K-theory spectrum associated to such a category. Waldhausen next generalized Quillen's notion of an exact category by introducing categories with weak equivalences and cofibrations, which one nowadays calls Waldhausen categories. K-theory has since been studied as a functor from the category of suitably structured (Quillen-exact, Waldhausen, symmetric monoidal) small categories to some category of spectra1. This has given rise to a huge field of research, so much so that there is a whole journal devoted to the subject. In this thesis, we want to take advantage of these tools to begin studying K-theory from another perspective. Indeed, we have the impression that, in the generalization of topological and algebraic K-theory that has been started by Quillen, something important has been left aside. K-theory was initiated as a (contravariant) functor from the various categories of spaces, rings, schemes, …, not from the category of Waldhausen small categories. Of course, one obtains information about a ring by studying its Quillen-exact category of (finitely generated projective) modules, but still, the final goal is the study of the ring, and, more globally, of the category of rings. Thus, in a general theory, one should describe a way to associate not only a spectrum to a structured category, but also a structured category to an object. Moreover, this process should take the morphisms of these objects into account. This gives rise to two fundamental questions. What kind of mathematical objects should K-theory be applied to? Given such an object, what category "over it" should one consider and how does it vary over morphisms? Considering examples, we have made the following observations. Suppose C is the category that is to be investigated by means of K-theory, like the category of topological spaces or of schemes, for instance. The category associated to an object of C is a sub-category of the category of modules over some monoid in a monoidal category with additional structure (topological, symmetric, abelian, model). The situation is highly "fibred": not only morphisms of C induce (structured) functors between these sub-categories of modules, but the monoidal category in which theses modules take place might vary from one object of C to another. In important cases, the sub-categories of modules considered are full sub-categories of "locally trivial" modules with respect to some (possibly weakened notion of) Grothendieck topology on C . That is, there are some specific modules that are considered sufficiently simple to be called trivial and locally trivial modules are those that are, locally over a covering of the Grothendieck topology, isomorphic to these. In this thesis, we explore, with K-theory in view, a categorical framework that encodes these kind of data. We also study these structures for their own sake, and give examples in other fields. We do not mention in this abstract set-theoretical issues, but they are handled with care in the discussion. Moreover, an appendix is devoted to the subject. After recalling classical facts of Grothendieck fibrations (and their associated indexed categories), we provide new insights into the concept of a bifibration. We prove that there is a 2-equivalence between the 2-category of bifibrations over a category ℬ and a 2-category of pseudo double functors from ℬ into the double category of adjunctions in CAT. We next turn our attention to composable pairs of fibrations , as they happen to be fundamental objects of the theory. We give a characterization of these objects in terms of pseudo-functors ℬop → FIBc into the 2-category of fibrations and Cartesian functors. We next turn to a short survey about Grothendieck (pre-)topologies. We start with the basic notion of covering function, that associate to each object of a category a family of coverings of the object. We study separately the saturation of a covering function with respect to sieves and to refinements. The Grothendieck topology generated by a pretopology is shown to be the result of these two steps. We define then, inspired by Street [89], the notion of (locally) trivial objects in a fibred category P : ℰ → ℬ equipped with some notion of covering of objects of the base ℬ. The trivial objects are objects chosen in some fibres. An object E in the fibre over B ∈ ℬ is locally trivial if there exists a covering {fi : Bi → B}i ∈ I such the inverse image of E along fi is isomorphic to a trivial object. Among examples are torsors, principal bundles, vector bundles, schemes, locally constant sheaves, quasi-coherent and locally free sheaves of modules, finitely generated projective modules over commutative rings, topological manifolds, … We give conditions under which locally trivial objects form a subfibration of P and describe the relationship between locally trivial objects with respect to subordinated covering functions. We then go into the algebraic part of the theory. We give a definition of monoidal fibred categories and show a 2-equivalence with monoidal indexed categories. We develop algebra (monoids and modules) in these two settings. Modules and monoids in a monoidal fibred category ℰ → ℬ happen to form a pair of fibrations . We end this thesis by explaining how to apply this categorical framework to K-theory and by proposing some prospects of research. ______________________________ 1 Works of Lurie, Toën and Vezzosi have shown that K-theory really depends on the (∞, 1)-category associated to a Waldhausen category [94]. Moreover, topological K-theory of spaces and Banach algebras takes the fact that the Waldhausen category is topological in account [62, 70].