A codificação distribuída de vídeo constitui um novo paradigma em compressão de vídeo frente aos codificadores híbridos da família MPEG-x e H.26x. Nesses codificadores, a estimação de movimento é a principal etapa do processo de compressão do sinal de vídeo. Desta forma, a codificação demanda um alto custo computacional exigindo desempenho do codificador. Neste trabalho é apresentado um codec de vídeo baseado na teoria da codificação distribuída com perdas. O compressor apresentado codifica os quadros ímpares e os quadros pares separadamente utilizando códigos turbo e a transformada wavelet. O processo de decodificação é feito de forma iterativa e explora a dependência estatística entre os quadros da seqüência de vídeo original. Esta abordagem permite uma redução bastante significativa no tempo de processamento envolvido na compressão do sinal de vídeo, tornando viável a implementação deste tipo de codificador em dispositivos com recursos escassos de processamento e memória. Os resultados obtidos em simulações comprovam o bom desempenho do codec proposto em relação ao padrão estado da arte em compressão de vídeo, o H.264/AVC; Distributed video coding is a new paradigm for video compression in opposition over the existing video coding standards like MPEG-x and H.26x families. These codecs make use of motion estimation algorithms...

A dissertação "Polinômios de Permutação e Palavras Balanceadas" tem como principal objetivo estudar a influência dos polinômios de permutação na teoria de códigos mediante o conceito de palavra balanceada. A base do trabalho é o artigo "Permutacion polynomials and aplications to coding theory" de Yann Laigke-Chapuy. Expomos os conceitos básicos de polinômios de permutação como algumas de suas características, exemplos e métodos para identificação dos mesmos. Em seguida trataremos dos códigos lineares com ênfase nos binários explorando particularmente a conjectura de Helleseth.; The main goal in writing this dissertation is the study of the influence of the Theory of Permutation Polynomials in the context of Coding Theory via the concept of balanced word. Our basic reference is the paper "Permutation polynomials and applications to coding theory" by Y. Laigke- Chapury. Our plan is to introduce the basic concepts in Coding Theory, Permutation Polynomials; then we mainly consider the long-standing open Helleseth¿s conjecture.

The goal of this thesis is to apply an approach due to Elkies to study the distribution of rational point counts for certain families of curves and surfaces over finite fields. A vector space of polynomials over a fixed finite field gives rise to a linear code, and the weight enumerator of this code gives information about point count distributions. The MacWilliams theorem gives a relation between the weight enumerator of a linear code and the weight enumerator of its dual code. For certain codes C coming from families of varieties where it is not known how to determine the distribution of point counts directly, we analyze low-weight codewords of the dual code and apply the MacWilliams theorem and its generalizations to gain information about the weight enumerator of C. These low-weight dual codes can be described in terms of point sets that fail to impose independent conditions on this family of varieties. Our main results concern rational point count distributions for del Pezzo surfaces of degree 2, and for certain families of genus 1 curves. These weight enumerators have interesting geometric and coding theoretic applications for small q.; Mathematics

A Esteganografi a é um assunto que ganhou importância rapidamente no contexto da segurança da informação. Ao ser relacionada com a Teoria dos Códigos, que já estava mais desenvolvida, a pesquisa neste mérito ganhou volume. Neste trabalho, introduziremos Esteganografi a e mostraremos como a Teoria dos Códigos pode facilitar seu estudo; Códigos perfeitos serão associados a um tipo de protocolo esteganográfico e veremos o efeito de código em papel molhado na Esteganogra fia. ______________________________________________________________________________ ABSTRACT; Steganography is a subject that became very important in the study of information security. When it was related to Coding Theory, which was well developed, the research on this matter rapidly increased. In this work, we will introduce Steganography and we will show how the Coding Theory an help in its study; perfect codes will be related to a kind of stegoscheme and we will see the e ffect of wet paper codes in Steganography.; Dissertação (mestrado)-Universidade Federal de Uberlândia, Faculdade de Matemática, Programa de pós-graduação em Matemática, 2014.

Este trabalho apresenta algumas contribuições para um melhor entendimento do emaranhamento quântico e suas aplicações. Com o propósito de obter a classificação de estados quânticos puros arbitrários em separáveis ou emaranhados, apresentamos um critério de separabilidade do qual tal classificação decorre. Este critério está baseado em uma interpretação homológicageométrica, que nos permitiu formalizar algumas conclusões acerca da quantificação do emaranhamento em estados puros arbitrários com três qubits. A partir desta interpretação, foi possível também associar a descriçãao do conteúdo dos kets de um estado puro arbitrário a conceitos de teoria da codificação clássica. Tendo como base esta associação, propomos uma forma bastante simplificada para determinar a descrição matemática de estados puros arbitrários que satisfazem o máximo emaranhamento global. De acordo com conceitos da teoria da codificação, analisamos os estados de máximo emaranhamento global com relaçãoo `a proteção contra erros que esses estados possuem. Neste contexto, apresentamos uma nova classe de estados que ainda Não havia sido mencionada na literatura; In this thesis we present some contributions to a better understanding of quantum entanglement and its applications. With the purpose of obtaining a classification of the arbitrary pure quantum states as separable or entangled...

Volume estimates of metric balls in manifolds find diverse applications in information and coding theory. In this paper, some new results for the volume of a metric ball in unitary group are derived via various tools from random matrix theory. The first result is an integral representation of the exact volume, which involves a Toeplitz determinant of Bessel functions. The connection to matrix-variate hypergeometric functions and Szeg\H{o}'s strong limit theorem lead independently from the finite size formula to an asymptotic one. The convergence of the limiting formula is exceptionally fast due to an underlying mock-Gaussian behavior. The proposed volume estimate enables simple but accurate analytical evaluation of coding-theoretic bounds of unitary codes. In particular, the Gilbert-Varshamov lower bound and the Hamming upper bound on cardinality as well as the resulting bounds on code rate and minimum distance are derived. Moreover, bounds on the scaling law of code rate are found. Lastly, a closed-form bound on diversity sum relevant to unitary space-time codes is obtained, which was only computed numerically in literature.; Comment: 23 pages

These are the notes for a set of lectures delivered by the two authors at the Les Houches Summer School on `Complex Systems' in July 2006. They provide an introduction to the basic concepts in modern (probabilistic) coding theory, highlighting connections with statistical mechanics. We also stress common concepts with other disciplines dealing with similar problems that can be generically referred to as `large graphical models'. While most of the lectures are devoted to the classical channel coding problem over simple memoryless channels, we present a discussion of more complex channel models. We conclude with an overview of the main open challenges in the field.; Comment: Lectures at Les Houches Summer School on `Complex Systems', July 2006, 44 pages, 25 ps figures

The Kneser-Hecke-operator is a linear operator defined on the complex vector space spanned by the equivalence classes of a family of self-dual codes of fixed length. It maps a linear self-dual code $C$ over a finite field to the formal sum of the equivalence classes of those self-dual codes that intersect $C$ in a codimension 1 subspace. The eigenspaces of this self-adjoint linear operator may be described in terms of a coding-theory analogue of the Siegel $\Phi $-operator.

This chapter introduces and elaborates on the fruitful interplay of coding theory and algebraic combinatorics, with most of the focus on the interaction of codes with combinatorial designs, finite geometries, simple groups, sphere packings, kissing numbers, lattices, and association schemes. In particular, special interest is devoted to the relationship between codes and combinatorial designs. We describe and recapitulate important results in the development of the state of the art. In addition, we give illustrative examples and constructions, and highlight recent advances. Finally, we provide a collection of significant open problems and challenges concerning future research.; Comment: 33 pages; handbook chapter, to appear in: "Selected Topics in Information and Coding Theory", ed. by I. Woungang et al., World Scientific, Singapore, 2010

The rise of machine-to-machine communications has rekindled the interest in random access protocols and their use to support a massive number of uncoordinatedly transmitting devices. The classic ALOHA approach is developed under a collision model, where slots that contain collided packets are considered as waste. However, if the common receiver (e.g., base station) is capable to store the collision slots and use them in a transmission recovery process based on successive interference cancellation, the design space for access protocols is radically expanded. We present the paradigm of coded random access, in which the structure of the access protocol can be mapped to a structure of an erasure-correcting code defined on graph. This opens the possibility to use coding theory and tools for designing efficient random access protocols, offering markedly better performance than ALOHA. Several instances of coded random access protocols are described, as well as a case study on how to upgrade a legacy ALOHA wireless system using the ideas of coded random access.; Comment: 9 pages, 4 figures; submitted to IEEE Communications Magazine

In this note we try to bring out the ideas of Hamming's classic paper on coding theory in a form understandable by undergraduate students of mathematics.; Comment: 4 pages

We investigate a certain well-established generalization of the Davenport constant. For $j$ a positive integer (the case $j=1$, is the classical one) and a finite Abelian group $(G,+,0)$, the invariant $\Dav_j(G)$ is defined as the smallest $\ell$ such that each sequence over $G$ of length at least $\ell$ has $j$ disjoint non-empty zero-sum subsequences. We investigate these quantities for elementary $2$-groups of large rank (relative to $j$). Using tools from coding theory, we give fairly precise estimates for these quantities. We use our results to give improved bounds for the classical Davenport constant of certain groups.

This thesis is interested in the application of statistical physics methods and inference to sparse linear estimation problems. The main tools are the graphical models and approximate message-passing algorithm together with the cavity method. We will also use the replica method of statistical physics of disordered systems which allows to associate to the studied problems a cost function referred as the potential of free entropy in physics. It allows to predict the different phases of typical complexity of the problem as a function of external parameters such as the noise level or the number of measurements one has about the signal: the inference can be typically easy, hard or impossible. We will see that the hard phase corresponds to a regime of coexistence of the actual solution together with another unwanted solution of the message passing equations. In this phase, it represents a metastable state which is not the true equilibrium solution. This phenomenon can be linked to supercooled water blocked in the liquid state below its freezing critical temperature. We will use a method that allows to overcome the metastability mimicing the strategy adopted by nature itself for supercooled water: the nucleation and spatial coupling. In supercooled water...

In this work we have considered formal power series and partial differential equations, and their relationship with Coding Theory. We have obtained the nature of solutions for the partial differential equations for Cycle Poisson Case. The coefficients for this case have been simulated, and the high tendency of growth is shown. In the light of Complex Analysis, the Hadamard Multiplication's Theorem is presented as a new approach to divide the power sums relating to the error probability, each part of which can be analyzed later.; Comment: 17 pages, 16 figures

In this paper, we are interested in the number of fixed points of functions $f:A^n\to A^n$ over a finite alphabet $A$ defined on a given signed digraph $D$. We first use techniques from network coding to derive some lower bounds on the number of fixed points that only depends on $D$. We then discover relationships between the number of fixed points of $f$ and problems in coding theory, especially the design of codes for the asymmetric channel. Using these relationships, we derive upper and lower bounds on the number of fixed points, which significantly improve those given in the literature. We also unveil some interesting behaviour of the number of fixed points of functions with a given signed digraph when the alphabet varies. We finally prove that signed digraphs with more (disjoint) positive cycles actually do not necessarily have functions with more fixed points.

Crowdsourcing systems often have crowd workers that perform unreliable work on the task they are assigned. In this paper, we propose the use of error-control codes and decoding algorithms to design crowdsourcing systems for reliable classification despite unreliable crowd workers. Coding-theory based techniques also allow us to pose easy-to-answer binary questions to the crowd workers. We consider three different crowdsourcing models: systems with independent crowd workers, systems with peer-dependent reward schemes, and systems where workers have common sources of information. For each of these models, we analyze classification performance with the proposed coding-based scheme. We develop an ordering principle for the quality of crowds and describe how system performance changes with the quality of the crowd. We also show that pairing among workers and diversification of the questions help in improving system performance. We demonstrate the effectiveness of the proposed coding-based scheme using both simulated data and real datasets from Amazon Mechanical Turk, a crowdsourcing microtask platform. Results suggest that use of good codes may improve the performance of the crowdsourcing task over typical majority-voting approaches.; Comment: 20 pages...

Shannon's seminal 1948 work gave rise to two distinct areas of research: information theory and mathematical coding theory. While information theory has had a strong influence on theoretical neuroscience, ideas from mathematical coding theory have received considerably less attention. Here we take a new look at combinatorial neural codes from a mathematical coding theory perspective, examining the error correction capabilities of familiar receptive field codes (RF codes). We find, perhaps surprisingly, that the high levels of redundancy present in these codes does not support accurate error correction, although the error-correcting performance of RF codes "catches up" to that of random comparison codes when a small tolerance to error is introduced. On the other hand, RF codes are good at reflecting distances between represented stimuli, while the random comparison codes are not. We suggest that a compromise in error-correcting capability may be a necessary price to pay for a neural code whose structure serves not only error correction, but must also reflect relationships between stimuli.; Comment: 26 pages, 8 figures

In this paper, we consider the problem of distributed inference in tree based networks. In the framework considered in this paper, distributed nodes make a 1-bit local decision regarding a phenomenon before sending it to the fusion center (FC) via intermediate nodes. We propose the use of coding theory based techniques to solve this distributed inference problem in such structures. Data is progressively compressed as it moves towards the FC. The FC makes the global inference after receiving data from intermediate nodes. Data fusion at nodes as well as at the FC is implemented via error correcting codes. In this context, we analyze the performance for a given code matrix and also design the optimal code matrices at every level of the tree. We address the problems of distributed classification and distributed estimation separately and develop schemes to perform these tasks in tree networks. The proposed schemes are of practical significance due to their simple structure. We study the asymptotic inference performance of our schemes for two different classes of tree networks: fixed height tree networks, and fixed degree tree networks. We show that the proposed schemes are asymptotically optimal under certain conditions.; Comment: 16 pages...

We propose an approach to Longobardi's parametric comparison method (PCM) via the theory of error-correcting codes. One associates to a collection of languages to be analyzed with the PCM a binary (or ternary) code with one code words for each language in the family and each word consisting of the binary values of the syntactic parameters of the language, with the ternary case allowing for an additional parameter state that takes into account phenomena of entailment of parameters. The code parameters of the resulting code can be compared with some classical bounds in coding theory: the asymptotic bound, the Gilbert-Varshamov bound, etc. The position of the code parameters with respect to some of these bounds provides quantitative information on the variability of syntactic parameters within and across historical-linguistic families. While computations carried out for languages belonging to the same family yield codes below the GV curve, comparisons across different historical families can give examples of isolated codes lying above the asymptotic bound.; Comment: 11 pages, LaTeX

Esta tesis doctoral se centra en esquemas de codificación de red sistemáticos (SNC por sus siglas en inglés para systematic network coding) a nivel de paquete para proporcionar resistencia a la pérdida de paquetes en redes lineales con pérdidas. En la teoría, la codificación de red ( network coding ) es conocida por la mejora en rendimiento y fiabilidad en redes con pérdidas. Sin embargo, la traducción de la teoría del network coding en soluciones prácticas comprende algunos desafíos críticos. Esta tesis aborda estos desafíos e investiga soluciones de network coding que puedan ser usadas en la práctica para diferentes instancias de redes lineales con pérdidas. Los objetivos principales de esta tesis doctoral son: 1) desarrollar un modelo matricial que permita el tratamiento analítico de network coding para redes con pérdidas, 2) investigar de manera semi-analítica el rendimiento alcanzable y la fiabilidad para redes lineales, un simple pero útil modelo de red conceptual, 3) desarrollar esquemas prácticos de network coding para redes lineales que superen significativamente el rendimiento del estado del arte en esquemas basados puramente en la correción de borrado hacia adelante (FEC por sus siglas en ingles para forward erasure correction)...