Search

International audience; What is Shannon’s information theory (IT)? Despite its continued impact on our digital society, Claude Shannon’s life and work is still unknown to numerous people. In this tutorial, we review many aspects of the concept of entropy and information from a historical and mathematical point of view. The text is structured into small, mostly independent sections, each covering a particular topic. For simplicity we restrict our attention to one-dimensional variables and use logarithm and exponential notations log and exp without specifying the base. We culminate with a simple exposition of a recent proof (2017) of the entropy power inequality (EPI), one of the most fascinating inequalities in the theory.

Orientador: Marcelo Firer Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática Estatística e Computação Científica 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 Doutorado Matemática Aplicada Doutor em Matemática Aplicada CAPES

Position Paper; International audience; Shannon’s information theory, since its first introduction in 1948, has received much attention and successful applications in many domains. Apart from Fitts’ law and Hick’s law, which came out when experimental psychologists were enthusiastic about applying information theory to various areas of psychology, the relation of information theory to human-computer interaction (HCI) has not been clear. Even the two above-mentioned “laws” remain controversial in both psychology and HCI. On the other hand, in recent years, information theory has started to directly inspire or contribute to HCI research.