Please use this identifier to cite or link to this item: http://repositorio.unicamp.br/jspui/handle/REPOSIP/325081
Type: TESE DIGITAL
Title: Geometry of communication channels = Geometria de canais de comunicação
Title Alternative: Geometria de canais de comunicação
Author: Lucas D'Oliveira, Rafael Gregorio, 1988-
Advisor: Firer, Marcelo, 1961-
Abstract: Resumo: Abordamos os canais de comunicação a partir de um ponto de vista geométrico. Mostramos que a decodificação por máxima verossimilhança e a decodificação por mínima distância são um caso particular de uma forma mais geral de decodificação que pode ser definida para qualquer matriz. Com base nisso, definimos uma equivalência de decodificação e mostramos que ela divide o espaço de matrizes em classes de equivalência que são regiões generalizadas de um arranjo de hiperplanos bem conhecido. Em seguida, definimos uma distância entre essas regiões que mede a probabilidade de um código aleatório ser decodificado incorretamente. Mostramos que esta distância é uma versão ponderada da distância de Kendall tau. Com isso, obtemos uma distância entre canais. Se para um canal existe uma métrica de modo que os decodificadores por máxima verossimilhança e mínima distância coincidem, o canal é metrizavel. Damos caracterizações para um canal ser metrizavel e apresentamos um algoritmo que constrói uma métrica nesse caso. Mostramos também que qualquer métrica, a menos de uma equivalência de decodificação, pode ser mergulhada isometricamente no hipercubo com a métrica de Hamming e, portanto, em termos de decodificação, a métrica de Hamming é universal. Apresentamos um algoritmo que, para qualquer métrica invariante por translação, dá um limite superior na dimensão mínima de tal mergulho. Encontramos também limitantes inferiores e superiores para essa dimensão. No apêndice, apresentamos uma contribuição teórica feita a um trabalho de navegação de mapas

Abstract: We approach communication channels from a geometrical viewpoint. We show that maximum likelihood decoding and minimum distance decoding are a particular case of a more general form of decoding which can be defined for any matrix. Based on this we define a decoding equivalence and show that it partitions the space of matrices into equivalence classes which are generalized regions of a well known hyperplane arrangement: the braid arrangement. We then define a distance between these regions which measures the probability of a random code being decoded incorrectly. It is shown that this distance is a weighted variation of the Kendall tau distance. With this, we obtain a distance between channels. If for a channel there exists a metric such that the maximum likelihood and minimum distance decoders coincide, the channel is metrizable. We give characterizations for a channel to be metrizable and present an algorithm which constructs a metric in such a case. We also show that any metric, up to decoding equivalence, can be isometrically embedded into the hypercube with the Hamming metric, and thus, in terms of decoding, the Hamming metric is universal. We then present an algorithm which for any translation invariant metric gives an upper bound on the minimum dimension of such an embedding. We also give lower and upper bounds for this embedding dimension over the set of all such metrics. In the appendix we present the theoretical contribution made to a work on multi-scale navigation
Subject: Teoria da informação
Códigos corretores de erros (Teoria da informação)
Mergulhos (Matemática)
Decodificação por máxima verossimilhança
Decodificação por mínima distância
Language: Inglês
Editor: [s.n.]
Date Issue: 2017
Appears in Collections:IMECC - Tese e Dissertação

Files in This Item:
File SizeFormat 
D'Oliveira_RafaelGregorioLucas_D.pdf1.24 MBAdobe PDFView/Open


Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.