Orientadores: Sueli Irene Rodrigues Costa, João Eloir Strapasson

Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica

Resumo: O conteúdo desta tese reside na interface entre Matemática Discreta (particularmente reticulados) e Teoria da Informação. Dividimos as contribuições originais do trabalho em quatro capítulos, de modo que os dois primeiros são relativos a resultados teóricos acerca de duas importantes classes...

Resumo: O conteúdo desta tese reside na interface entre Matemática Discreta (particularmente reticulados) e Teoria da Informação. Dividimos as contribuições originais do trabalho em quatro capítulos, de modo que os dois primeiros são relativos a resultados teóricos acerca de duas importantes classes de reticulados (os reticulados q-ários e os reticulados projeção), e os dois últimos referem-se a aplicações em codificação contínua fonte-canal. Nos primeiros capítulos, exibimos resultados sobre decodificação de reticulados q-ários e sobre ladrilhamentos associados a códigos corretores de erros perfeitos na norma l_p. No que tange a reticulados projeção, nossas contribuições incluem o estudo de sequências de projeção de um dado reticulado n-dimensional convergindo para qualquer reticulado k-dimensional fixado, k < n, incluindo uma análise de convergência de tais sequências. Esses novos resultados relativos a projeções estendem e aprimoram recentes trabalhos no tema e são elementos de base para as aplicações consideradas no restante da tese. Nos dois últimos capítulos, consideramos o problema de transmitir uma fonte com alfabeto contínuo através de um canal gaussiano no caso em que a dimensão da fonte, k, é menor que a dimensão do canal, n. Para fontes unidimensionais, exibimos códigos baseados em curvas na superfície de toros planares com performance significativamente superior aos propostos anteriormente na literatura no que diz respeito ao erro quadrático médio atingido. Para k > 1, mostramos como aplicar projeções de reticulados para obter códigos cujo erro quadrático médio possui decaimento ótimo com respeito à relação sinal-ruído do canal (chamados de assintoticamente ótimos). Através de técnicas provenientes da bela teoria de dissecção de poliedros, apresentamos as primeiras construções de códigos assintoticamente ótimos para fontes com dimensão maior do que 1

Abstract: The contents of this thesis lie in the interface between Discrete Mathematics (particularly lattices) and Information Theory. The original contributions of this work are organized so that the first two chapters are devoted to theoretical results on q-ary and projection lattices, whereas...

Abstract: The contents of this thesis lie in the interface between Discrete Mathematics (particularly lattices) and Information Theory. The original contributions of this work are organized so that the first two chapters are devoted to theoretical results on q-ary and projection lattices, whereas the last ones are related to the construction of continuous source-channel codes. In the first chapters, we exhibit results on decoding q-ary lattices and on finding tilings associated to perfect error-correcting codes in the l_p norm. Regarding projection lattices, our contributions include the study of sequences of projections of a given n-dimensional lattice converging to any k-dimensional target lattice, as well as a convergence analysis of such sequences. These new results on projections extend and improve recent works on the topic and serve as building blocks for the applications to be developed throughout the last part of the thesis. In the last two chapters, we consider the problem of constructing mappings for the transmission of a continuous alphabet source over a Gaussian channel, when the channel dimension, n, is strictly greater than the source dimension, k. For one-dimensional sources, we exhibit codes based on curves on flat tori with performance significantly superior to the previous proposals in the literature with respect to the mean squared error achieved. For k > 1, we show how to apply projections of lattices to obtain codes whose mean squared error decays optimally with respect to the signal-to-noise ratio of the channel (referred to as asymptotically optimal codes). Through techniques from the rich theory of dissections of polyhedra, we present the first constructions of provenly asymptotically optimal codes for sources with dimension greater than 1