No description available.

We study the Hamming distance and the structure of repeated-root cyclic codes, and their generalizations to constacyclic and polycyclic codes, over finite fields and Galois rings. We develop a method to compute the Hamming distance of these codes. Our computation gives the Hamming distance of constacyclic codes of length $np^s$ in many cases. In particular, we determine the Hamming distance of all constacyclic, and therefore cyclic and negacyclic, codes of lengths p^s and 2p^s over a finite field of characteristic $p$. It turns out that the generating sets for the ambient space obtained by torsional degrees and strong Groebner basis for the ambient space are essentially the same and one can be obtained from the other. In the second part of the thesis, we study matrix product codes. We show that using nested constituent codes and a non-constant matrix in the construction of matrix product codes with polynomial units is a crucial part of the construction. We prove a lower bound on the Hamming distance of matrix product codes with polynomial units when the constituent codes are nested. This generalizes the technique used to construct the record-breaking examples of Hernando and Ruano. Contrary to a similar construction previously introduced, this bound is not sharp and need not hold when the constituent codes are not nested. We give a comparison of this construction with a previous one. We also construct new binary codes having the same parameters, of the examples of Hernando and Ruano, but non-equivalent to them.

Two standard graph representations for linear codes are the Tanner graph and the tailbiting trellis. Such graph representations allow the decoding problem for a code to be phrased as a computational problem on the corresponding graph and yield graph theoretic criteria for good codes. When a Tanner graph for a code is used for communication across a binary erasure channel (BEC) and decoding is performed using the standard iterative decoding algorithm, the maximum number of correctable erasures is determined by the stopping distance of the Tanner graph. Hence the computational problem of determining the stopping distance of a Tanner graph is of interest. In this thesis it is shown that computing stopping distance of a Tanner graph is NP hard. It is also shown that there can be no (1 + є ) approximation algorithm for the problem for any є > 0 unless P = NP and that approximation ratio of 2(log n)1- є for any є > 0 is impossible unless NPCDTIME(npoly(log n)). One way to construct Tanner graphs of large stopping distance is to ensure that the graph has large girth. It is known that stopping distance increases exponentially with the girth of the Tanner graph. A new elementary combinatorial construction algorithm for an almost regular LDPC code family with provable Ώ(log n) girth and O(n2) construction complexity is presented. The bound on the girth is close within a factor of two to the best known upper bound on girth. The problem of linear time exact maximum likelihood decoding of tailbiting trellis has remained open for several years. An O(n) complexity approximate maximum likelihood decoding algorithm for tail-biting trellises is presented and analyzed. Experiments indicate that the algorithm performs close to the ideal maximum likelihood decoder.

Made available in DSpace on 2015-05-15T11:45:58Z (GMT). No. of bitstreams: 1 arquivototal.pdf: 634504 bytes, checksum: ce035cc957832598c53dda96372e7cb7 (MD5) Previous issue date: 2011-02-24 / Coordenação de Aperfeiçoamento de Pessoal de Nível Superior - CAPES / In this work, based on algebraic function fields, we give constructions of disjoint linear codes. In addition,we study the asymptotic behavior of disjoint linear codes from our constructions. / Neste trabalho, baseados em corpos de funções algébricas, forneceremos construções de códigos lineares disjuntos. Além disso, nós estudaremos comportamentos assintóticos de códigos lineares disjuntos a partir da nossa construção.

Employing an error control code is one of the techniques to reduce the Peak-to-Average Power Ratio (PAPR) in an Orthogonal Frequency Division Multiplexing system; a well known class of such codes being the cosets of Reed-Muller codes. In this thesis, classes of such coset-codes of arbitrary linear codes are considered. It has been proved that the size of such a code can be doubled with marginal/no increase in the PAPR. Conditions for employing this method iteratively have been enunciated. In fact this method has enabled to get the optimal coset-codes. The PAPR of the coset-codes of the extended codes is obtained from the PAPR of the corresponding coset-codes of the parent code. Utility of a special type of lengthening is established in PAPR studies

Un graphe métrique G(X;D) est un graphe dont l’ensemble des sommets est l’ensemble X des points d’un espace métrique (X; d), et dont les arêtes relient les paires fx; yg de sommets telles que d(x; y) 2 D. Dans cette thèse, nous considérons deux problèmes qui peuvent être interprétés comme des problèmes de graphes métriques dans Rn. Premièrement, nous nous intéressons au célèbre problème d’empilements de sphères, relié au graphe métrique G(Rn; ]0; 2r[) pour un rayon de sphère r donné. Récemment, Venkatesh a amélioré d’un facteur log log n la meilleure borne inférieure connue pour un empilement de sphères donné par un réseau, pour une suite infinie de dimensions n. Ici nous prouvons une version effective de ce résultat, dans le sens où l’on exhibe, pour la même suite de dimensions, des familles finies de réseaux qui contiennent un réseaux dont la densité atteint la borne de Venkatesh. Notre construction met en jeu des codes construits sur des corps cyclotomiques, relevés en réseaux grâce à un analogue de la Construction A. Nous prouvons aussi un résultat similaire pour des familles de réseaux symplectiques. Deuxièmement, nous considérons le graphe distance-unité G associé à une norme k_k. Le nombre m1 (Rn; k _ k) est défini comme le supremum des densités réalisées par les stables de G. Si la boule unité associée à k _ k pave Rn par translation, alors il est aisé de voir que m1 (Rn; k _ k) > 1 2n . C. Bachoc et S. Robins ont conjecturé qu’il y a égalité. On montre que cette conjecture est vraie pour n = 2 ainsi que pour des régions de Voronoï de plusieurs types de réseaux en dimension supérieure, ceci en se ramenant à la résolution de problèmes d’empilement dans des graphes discrets. / A distance graph G(X;D) is a graph whose set of vertices is the set of points X of a metric space (X; d), and whose edges connect the pairs fx; yg such that d(x; y) 2 D. In this thesis, we consider two problems that may be interpreted in terms of distance graphs in Rn. First, we study the famous sphere packing problem, in relation with thedistance graph G(Rn; (0; 2r)) for a given sphere radius r. Recently, Venkatesh improved the best known lower bound for lattice sphere packings by a factor log log n for infinitely many dimensions n. We prove an effective version of this result, in the sense that we exhibit, for the same set of dimensions, finite families of lattices containing a lattice reaching this bound. Our construction uses codes over cyclotomic fields, lifted to lattices via Construction A. We also prove a similar result for families of symplectic lattices. Second, we consider the unit distance graph G associated with a norm k _ k. The number m1 (Rn; k _ k) is defined as the supremum of the densities achieved by independent sets in G. If the unit ball corresponding with k _ k tiles Rn by translation, then it is easy to see that m1 (Rn; k _ k) > 1 2n . C. Bachoc and S. Robins conjectured that the equality always holds. We show that this conjecture is true for n = 2 and for several Voronoï cells of lattices in higher dimensions, by solving packing problems in discrete graphs.

This thesis deals with the problem of code design in the setting of distributed storage systems consisting of multiple storage nodes, storing many different data les. A primary goal in such systems is the efficient repair of a failed node. Regenerating codes and codes with locality are two classes of coding schemes that have recently been proposed in literature to address this goal. While regenerating codes aim to minimize the amount of data-download needed to carry out node repair, codes with locality seek to minimize the number of nodes accessed during node repair. Our focus here is on linear codes with locality, which is a concept originally introduced by Gopalan et al. in the context of recovering from a single node failure. A code-symbol of a linear code C is said to have locality r, if it can be recovered via a linear combination of r other code-symbols of C. The code C is said to have (i) information-symbol locality r, if all of its message symbols have locality r, and (ii) all-symbol locality r, if all the code-symbols have locality r. We make the following three contributions to the area of codes with locality. Firstly, we extend the notion of locality, in two directions, so as to permit local recovery even in the presence of multiple node failures. In the first direction, we consider codes with \local error correction" in which a code-symbol is protected by a local-error-correcting code having local-minimum-distance 3, and thus allowing local recovery of the code-symbol even in the presence of 2 other code-symbol erasures. In the second direction, we study codes with all-symbol locality that can recover from two erasures via a sequence of two local, parity-check computations. When restricted to the case of all-symbol locality and two erasures, the second approach allows, in general, for design of codes having larger minimum distance than what is possible via the rst approach. Under both approaches, by studying the generalized Hamming weights of the dual codes, we derive tight upper bounds on their respective minimum distances. Optimal code constructions are identified under both approaches, for a class of code parameters. A few interesting corollaries result from this part of our work. Firstly, we obtain a new upper bound on the minimum distance of concatenated codes and secondly, we show how it is always possible to construct the best-possible code (having largest minimum distance) of a given dimension when the code's parity check matrix is partially specified. In a third corollary, we obtain a new upper bound for the minimum distance of codes with all-symbol locality in the single erasure case. Secondly, we introduce the notion of codes with local regeneration that seek to combine the advantages of both codes with locality as well as regenerating codes. These are vector-alphabet analogues of codes with local error correction in which the local codes themselves are regenerating codes. An upper bound on the minimum distance is derived when the constituent local codes have a certain uniform rank accumulation (URA) property. This property is possessed by both the minimum storage regenerating (MSR) and the minimum bandwidth regenerating (MBR) codes. We provide several optimal constructions of codes with local regeneration, where the local codes are either the MSR or the MBR codes. The discussion here is also extended to the case of general vector-linear codes with locality, in which the local codes do not necessarily have the URA property. Finally, we evaluate the efficacy of two specific coding solutions, both possessing an inherent double replication of data, in a practical distributed storage setting known as Hadoop. Hadoop is an open-source platform dealing with distributed storage of data in which the primary aim is to perform distributed computation on the stored data via a paradigm known as Map Reduce. Our evaluation shows that while these codes have efficient repair properties, their vector-alphabet-nature can negatively a affect Map Reduce performance, if they are implemented under the current Hadoop architecture. Specifically, we see that under the current architecture, the choice of number processor cores per node and Map-task scheduling algorithm play a major role in determining their performance. The performance evaluation is carried out via a combination of simulations and actual experiments in Hadoop clusters. As a remedy to the problem, we also pro-pose a modified architecture in which one allows erasure coding across blocks belonging to different les. Under the modified architecture, the new coding solutions will not suffer from any Map Reduce performance-loss as seen in the original architecture, while retaining all of their desired repair properties

Orientador: Prof. Dr. Armando Caputi / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Mestrado Profissional em Matemática em Rede Nacional - PROFMAT, Santo André, 2018. / Nesta dissertação, apresentamos os dígitos que verificam erros em códigos numéricos e os códigos que identificam e corrigem erros em informações transmitidas ou armazenadas. Em relação aos dígitos que verificam erros, enfocamos os sistemas modulares, os principais erros que podem ser cometidos na digitação de sequências numéricas e a eficiência do dígito para detectar sua presença. Já em códigos corretores de erros, denotamos os conceitos de um código e sua utilidade em um sistema de comunicação, mostramos como codificar uma informação e depois como decodificá-la corrigindo erros, caso existam. Finalmente, explicitamos algumas aplicações dos dígitos verificadores e códigos corretores de erros para o Ensino Fundamental e Médio. / In this dissertation, we present the digits that verify errors in numerical codes and the codes that identify and correct errors in transmitted or stored information. Regarding the digits that verify errors, we focus on the modular systems, the main errors that can be presented during the typing of numerical sequences and the efficiency of the digit to detect their presence. As for theerror-correcting codes, we denote the concepts of a code and its use in a communication system, we show how to code pieces of information and then how to decode it correcting errors, in case they exist. Finally, we described in details some applications of the verifier digits and error correction codes for Elementary and Middle School.

In this thesis, three problems have been considered and new coding schemes have been devised for each of them. The first is related to distributed function computation, the second to coding for distributed storage and the final problem is based on locally correctable codes. A common theme of the first two problems considered is distributed computation. The first problem is motivated by the problem of distributed function computation considered by Korner and Marton, where the goal is to compute XOR of two binary sources at the receiver. It has been shown that linear encoders give better sum rates for some source distributions as compared to the usual Slepian-Wolf scheme. We generalize this distributed function computation setting to the case of more than two sources and the receiver is interested in computing multiple linear combinations of the sources. Consider `m' random variables each of which takes values from a finite field and are associated with a certain joint probability distribution. The receiver is interested in the lossless computation of `s' linear combinations of the m random variables. By considering the set of all linear combinations of m random variables as a vector space V , this problem can be interpreted as a subspace-computation problem. For this problem, we develop three increasingly refined approaches, all based on linear encoders. The first two approaches which are termed as common code approach and selected subspace approach, use a common matrix to encode all the sources. In the common code approach, the desired subspace W is computed at the receiver, whereas in the selected subspace approach, possibly a larger subspace U which contains the desired subspace is computed. The larger subspace U which gives the minimum sum rate itself is based on a decomposition of vector space V into a chain of subspaces. The chain of subspaces is determined by the joint probability distribution of m random variables and a notion of normalized measure of entropy. The third approach is a nested code approach, where all the encoding matrices are nested and the same subspace U which is identified in the selected subspace approach is computed. We characterize the sum rates under all the three approaches. The sum rate under nested code approach is no larger than both selected subspace approach and Slepian-Wolf approach. For a large class of joint distributions and subspaces W , the nested code scheme is shown to improve upon Slepian-Wolf scheme. Additionally, a class of source distributions and subspaces are identified, for which the nested code approach is sum-rate optimal. In the second problem, we consider a distributed storage network, where data is stored across nodes in a network which are failure-prone. The goal is to store data reliably and efficiently. For a required level of reliability, it is of interest to minimise storage overhead and also of interest to perform node repair efficiently. Conventionally replication and maximum distance separable (MDS) codes are employed in such systems. Though replication is very efficient in terms of node repair, the storage overhead is high. MDS codes have low storage overhead but even the repair of a single failed node requires contacting a large number of nodes and downloading all their data. We consider two coding solutions that have recently been proposed, which enable efficient node repair in case of single node failure. The first solution called regenerating codes seeks to minimize the amount of data downloaded for node repair, while codes with locality attempt to minimize the number of helper nodes accessed. We extend these results in two directions. In the first one, we introduce the notion of codes with locality where the local codes have minimum distance more than 2 and hence can recover a code symbol locally even in the presence of multiple erasures. These codes are termed as codes with local erasure correction. We say that a code has information locality if there exists a set of message symbols, each of which is covered by local codes. A code is said to have all-symbol locality if all the code symbols are covered by local codes. An upper bound on the minimum distance of codes with information locality is presented and codes that are optimal with respect to this bound are constructed. We make a connection between codes with local erasure correction and concatenated codes. The second direction seeks to build codes that combine the advantages of both codes with locality as well as regenerating codes. These codes, termed here as codes with local regeneration, are codes with locality over a vector alphabet, in which the local codes themselves are regenerating codes. There are two well known classes of regenerating codes known as minimum storage regenerating (MSR) codes and minimum bandwidth regenerating (MBR) codes. We derive two upper bounds on the minimum distance of vector-alphabet codes with locality, one for the case when the local codes are MSR codes and the second for the case when the local codes are MBR codes. We also provide several optimal constructions of both classes of codes which achieve their respective minimum distance bounds with equality. The third problem deals with locally correctable codes. A block code of length `n' is said to be locally correctable, if there exists a randomized algorithm such that any one of the coordinates of the codeword can be recovered by querying at most `r' coordinates, even in presence of some fraction of errors. We study the local correctability of linear codes whose duals contain 4-designs. We also derive a bound relating `r' and fraction of errors that can be tolerated, when each instance of the randomized algorithm is `t'-error correcting instead of simple parity computation.

Historically, wireless communication security solutions have heavily relied on computational methods, such as cryptographic algorithms implemented in the upper layers of the network stack. Although these methods have been effective, they may not always be sufficient to address all security threats. An alternative approach for achieving secure communication is the physical layer security approach, which utilizes the physical properties of the communication channel through appropriate coding and signal processing. The goal of this Ph.D. dissertation is to leverage the foundations of information-theoretic security to develop innovative and secure schemes, as well as code design techniques, that can enhance security and reliability in wireless communication networks. This dissertation includes three main phases of investigation. The first investigation analyzes the finite blocklength coding problem for the wiretap channel model which is equipped with the cache. The objective was to develop and analyze a new wiretap coding scheme that can be used for secure communication of sensitive data. Secondly, an investigation was conducted into information-theoretic security solutions for aeronautical mobile telemetry (AMT) systems. This included developing a secure coding technique for the integrated Network Enhanced Telemetry (iNET) communications system, as well as examining the potential of post-quantum cryptography approaches as future secrecy solutions for AMT systems. The investigation focused on exploring code-based techniques and evaluating their feasibility for implementation. Finally, the properties of nested linear codes in the wiretap channel model have been explored. Investigation in this phase began by exploring the duality relationship between equivocation matrices of nested linear codes and their corresponding dual codes. Then a new coding algorithm to construct the optimum nested linear secrecy codes has been invented. This coding algorithm leverages the aforementioned duality relationship by starting with the worst nested linear secrecy codes from the dual space. This approach enables us to derive the optimal nested linear secrecy code more efficiently and effectively than through a brute-force search for the best nested linear secrecy codes directly.