Códigos y grafos sobre anillos de enteros complejos


Author

Martínez Fernández, María del Carmen

Director

Beivide Palacio, Ramón

Date of defense

2007-03-26

ISBN

9788469099049

Legal Deposit

SA.965-2007



Department/Institute

Universidad de Cantabria. Departamento de Matemáticas, Estadística y Computación

Abstract

El objetivo de esta tesis es definir códigos perfectos sobre diferentes espacios de señal multidimensionales. Para resolver este problema, esta memoria presenta una relación original entre las Teorías de Grafos, Números y Códigos. Uno de nuestros principales resultados es la propuesta de una métrica adecuada sobre constelaciones de señal de tipo cuadrático, hexagonal y cuatro-dimensional. Esta métrica es la distancia entre los vértices de una nueva clase de grafos de Cayley definidos sobre diferentes anillos de enteros, en concreto, los enteros de Gauss, Eisenstein-Jacobi y Lipschitz. <br/><br/>Así, resolvemos el problema de Teoría de Grafos conocido como el cálculo del conjunto perfecto dominante sobre las familias de grafos definidas en esta memoria. Para cada caso, daremos una condición suficiente para obtener dicho conjunto. La obtención de estos conjuntos de dominación implica directamente la construcción de códigos perfectos sobre los alfabetos que se consideran.<br/><br/>Además, se obtendrán algunos resultados de isomorfía y embebimiento de grafos. En particular, se establecerán las relaciones entre grafos circulantes, toroidales y los que se presentan en este trabajo. Más concretamente, se mostrará que siempre existen órdenes para los cuales un grafo Toro puede ser embebido en un grafo Gaussiano, de Esenstein-Jacobi o de Lipschitz. Esto implica que la conocida distancia de Lee es un caso particular de las métricas presentadas en este trabajo.


The aim of this work is to define perfect codes for different multidimensional signal spaces. To solve this problem, this thesis presents an original relationship among the fields of Graph Theory, Number Theory and Coding Theory. One of our main findings is the proposal of a suitable metric over quadratic, hexagonal and four-dimensional constellations of signal points. This metric is the distance among vertices of a new class of Cayley graphs defined over integer rings, namely Gaussian integers, the Eisenstein-Jacobi integers and the Lipschitz integers.<br/><br/>A problem in Graph Theory known as the perfect dominating set calculation is solved over the families of graphs defined in this memory. A sufficient condition for obtaining such a set is given for each case. The obtention of these sets of domination directly yields to the construction of perfect codes for the alphabets under consideration. <br/><br/>In addition, some isomorphism and graph embedding results are going to be obtained. Specially, the relations between circulant, toroidal and the graphs presented in this work are stated. In particular, there always exist orders for which a Torus graph can be embedded in Gaussian, Eisenstein-Jacobi and Lipschitz graphs. This implies that the well-known Lee distance is a subcase of the metrics presented in this research.

Keywords

multidimensional signal constellations; constelaciones de señal multidimensionales; perfect codes; codigos perfectos; Cayley graphs; grafos de Cayley; anillos de enteros; integer rings

Subjects

004 - Computer science and technology. Computing. Data processing; 511 - Number theory; 519.1 - Combinatorial analysis. Graph theory

Knowledge Area

Matemáticas

Documents

TesisCMF.pdf

836.1Kb

 

Rights

ADVERTENCIA. El acceso a los contenidos de esta tesis doctoral y su utilización debe respetar los derechos de la persona autora. Puede ser utilizada para consulta o estudio personal, así como en actividades o materiales de investigación y docencia en los términos establecidos en el art. 32 del Texto Refundido de la Ley de Propiedad Intelectual (RDL 1/1996). Para otros usos se requiere la autorización previa y expresa de la persona autora. En cualquier caso, en la utilización de sus contenidos se deberá indicar de forma clara el nombre y apellidos de la persona autora y el título de la tesis doctoral. No se autoriza su reproducción u otras formas de explotación efectuadas con fines lucrativos ni su comunicación pública desde un sitio ajeno al servicio TDR. Tampoco se autoriza la presentación de su contenido en una ventana o marco ajeno a TDR (framing). Esta reserva de derechos afecta tanto al contenido de la tesis como a sus resúmenes e índices.

This item appears in the following Collection(s)