Dissertations / Theses on the topic 'Algebraic Coding Theory'

Cette thèse étudie un problème de calcul formel qui a des applications et conséquences importantes sur la théorie des codes correcteurs algébriques : la reconstruction rationnelle simultanée (RRS). En effet, une analyse rigoureuse de ce problème amène à des résultats intéressants dans ce deux domaines scientifiques.Plus précisément, la reconstruction simultanée de fractions rationnelles est le problème de la reconstruction d’un vecteur de fractions rationnelles ayant le même dénominateur étant donné ses évaluations (ou plus généralement étant donné ses restes modulo de polynômes différents). La particularité de ce problème consiste dans le fait que la contrainte du dénominateur commun réduit le nombre de points d’évaluation nécessaires pour garantir l’existence d’une solution, au prix d’une éventuelle perte d’unicité. Une des principales contributions de ce travail consiste à prouver que l’unicité est garantie pour quasiment tous les instances de ce problème.Ce résultat a été obtenu par l’élaboration des résultats et techniques précédents dérivées des applications du probleme RRS, depuis la résolution de systèmes linéaires polynomiaux jusqu’au décodage de codes Reed-Solomon entrelacés.Dans ce travail, nous avons aussi étudié et présenté une autre application du problème SRFR, concernant le problème de la construction d’algorithmes tolérants aux fautes : des algorithmes résistants aux erreurs de calcul. Ces algorithmes sont construits en introduisant une redondance et en utilisant des outils de codes correcteurs d’erreurs pour détecter et éventuellement corriger les erreurs qui se produisent pendant les calculs. Dans ce contexte d’application, nous améliorons une technique existante de tolérance aux fautes pour la résolution de systèmes linéaires polynomiaux par interpolation-évaluation, avec une attention particulière aux problème RRS correspondant
This dissertation deals with a Computer Algebra problem which has significant consequencesin Algebraic Coding Theory and Error Correcting Codes: the simultaneous rationalfunction reconstruction. Indeed, an accurate analysis of this problem leads to interestingresults in both these scientific domains.More precisely, the simultaneous rational function reconstruction is the problem of reconstructinga vector of rational functions with the same denominator given its evaluations(or more generally given its remainders modulo different polynomials). The peculiarity ofthis problem consists in the fact that the common denominator constraint reduces the numberof evaluation points needed to guarantee the existence of a solution, possibly losing theuniqueness. One of the main contribution of this work consists in the proof that uniquenessis guaranteed for almost all instances of this problem.This result was obtained by elaborating some other contributions and techniques derivedby the applications of SRFR, from the polynomial linear system solving to the decoding ofInterleaved Reed-Solomon codes.In this work, we will also study and present another application of the SRFR problem,concerning the problem of constructing fault-tolerant algorithms: algorithms resilientsto computational errors. These algorithms are constructed by introducing redundancy andusing error correcting codes tools to detect and possibly correct errors which occur duringcomputations. In this application context, we improve an existing fault-tolerant techniquefor polynomial linear system solving by interpolation-evaluation, by focusing on the SRFRproblem related to it

En 1978, McEliece introduit un schéma de chiffrement à clé publique issu de la théorie des codes correcteurs d’erreurs. L’idée du schéma de McEliece est d’utiliser un code correcteur dont lastructure est masquée, rendant le décodage de ce code difficile pour toute personne ne connaissant pas cette structure. Le principal défaut de ce schéma est la taille de la clé publique. Dans ce contexte, on se propose d'étudier l'utilisation de codes dont on connaît une représentation compacte, en particulier le cas de codes quais-cyclique ou quasi-dyadique. Les deux familles de codes qui nous intéressent dans cette thèse sont: la famille des codes alternants et celle des sous--codes sur un sous--corps de codes géométriques. En faisant agir un automorphisme $sigma$ sur le support et le multiplier des codes alternants, on saitqu'il est possible de construire des codes alternants quasi-cycliques. On se propose alors d'estimer la sécurité de tels codes à l'aide du textit{code invariant}. Ce sous--code du code public est constitué des mots du code strictement invariant par l'automorphisme $sigma$. On montre ici que la sécurité des codes alternants quasi-cyclique se réduit à la sécurité du code invariant. Cela est aussi valable pour les sous—codes sur un sous--corps de codes géométriques quasi-cycliques. Ce résultat nous permet de proposer une analyse de la sécurité de codes quasi-cycliques construit sur la courbe Hermitienne. En utilisant cette analyse nous proposons des clés compactes pour la schéma de McEliece utilisant des sous-codes sur un sous-corps de codes géométriques construits sur la courbe Hermitienne. Le cas des codes alternants quasi-dyadiques est aussi en partie étudié. En utilisant le code invariant, ainsi que le textit{produit de Schur}et le textit{conducteur} de deux codes, nous avons pu mettre en évidence une attaque sur le schéma de McEliece utilisant des codes alternants quasi-dyadique de degré $2$. Cette attaque s'applique notamment au schéma proposé dans la soumission DAGS, proposé dans le contexte de l'appel du NIST pour la cryptographie post-quantique
In 1978, McEliece introduce a new public key encryption scheme coming from errors correcting codes theory. The idea is to use an error correcting code whose structure would be hidden, making it impossible to decode a message for anyone who do not know a specific decoding algorithm for the chosen code. The McEliece scheme has some advantages, encryption and decryption are very fast and it is a good candidate for public-key cryptography in the context of quantum computer. The main constraint is that the public key is too large compared to other actual public-key cryptosystems. In this context, we propose to study the using of some quasi-cyclic or quasi-dyadic codes. In this thesis, the two families of interest are: the family of alternant codes and the family of subfield subcode of algebraic geometry codes. We can construct quasi-cyclic alternant codes using an automorphism which acts on the support and the multiplier of the code. In order to estimate the securtiy of these QC codes we study the em{invariant code}. This invariant code is a smaller code derived from the public key. Actually the invariant code is exactly the subcode of code words fixed by the automorphism $sigma$. We show that it is possible to reduce the key-recovery problem on the original quasi-cyclic code to the same problem on the invariant code. This is also true in the case of QC algebraic geometry codes. This result permits us to propose a security analysis of QC codes coming from the Hermitian curve. Moreover, we propose compact key for the McEliece scheme using subfield subcode of AG codes on the Hermitian curve. The case of quasi-dyadic alternant code is also studied. Using the invariant code, with the em{Schur product} and the em{conductor} of two codes, we show weaknesses on the scheme using QD alternant codes with extension degree 2. In the case of the submission DAGS, proposed in the context of NIST competition, an attack exploiting these weakness permits to recover the secret key in few minutes for some proposed parameters

Orientadores: Fernando Eduardo Torres Orihuela, Cícero Fernandes de Carvalho
Tese (doutorado) - Universidade Estadual de Campinas, Instituto de Matemática, Estatística e Computação Científica
Made available in DSpace on 2018-08-19T03:11:40Z (GMT). No. of bitstreams: 1 Peixoto_Rafael_D.pdf: 876847 bytes, checksum: ae0f5d0ea0f2c3e3d550bc60eb1ac66a (MD5) Previous issue date: 2011
Resumo: Definidas sobre uma F-álgebra, os conceitos de função peso e função peso fraco foram introduzidos de forma a simplificar a teoria dos códigos corretores de erros que utilizam ferramentas da geometria algébrica. Porém, todos os códigos suportados por estes conceitos estão intimamente ligados à códigos provenientes de curvas algébricas, ou seja, os códigos geométricos de Goppa. Uma modificação da noção de função peso foi apresentada permitindo assim construir códigos lineares sobre variedades algébricas. Nesta tese, apresentamos uma generalização da teoria de funções pesos fracos que possibilitou a construção de códigos sobre variedades de dimensão arbitrária. Determinamos uma cota para a distância mínima destes códigos, e finalmente, apresentamos uma caracterização tanto para as álgebras munidas de funções pesos quanto para as álgebras munidas de um conjunto especial de funções pesos fracos
Abstract: Defined on a F-algebra, the concepts of weight and near weight function were introduced to simplify the theory of error correcting codes using tools from algebraic geometry. However, all codes supported by these theories are geometric Goppa codes. The concept of weight function was generalized and used to construct linear codes on algebraic varieties. In this thesis, we present a generalization of near weights theory able to construct codes on higher dimensional varieties, and we define a formula for the minimum distance of such codes. Finally, we characterize the algebras with a weight function and the algebras admitting a special set of two near weight functions
Doutorado
Matematica
Doutor em Matemática

Orientadores: Paulo Roberto Brumatti, Fernando Eduardo Torres Orihuela
Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Computação Cientifica
Made available in DSpace on 2018-08-05T23:44:44Z (GMT). No. of bitstreams: 1 Melo_Nolmar_M.pdf: 705654 bytes, checksum: b8ecfe0cc3ffd2dd2f63bc813a9c4a8d (MD5) Previous issue date: 2006
Resumo: O objetivo central desta dissertação foi o de apresentar os Códigos Geométricos de Goppa via métodos elementares que foram introduzidos por J. H. van Lint, R. Pellikaan e T. Hfhold por volta de 1998. Numa primeira parte da dissertação são apresentados os conceitos fundamentais sobre corpos de funções racionais de uma curva algébrica na direção de se definir os códigos de Goppa de maneira clássica, neste estudo nos baseamos principalmente no livro ¿Algebraic Function Fields and Codes¿ de H. Stichtenoth. A segunda parte inicia-se com a introdução dos conceitos de funções peso, grau e ordem que são fundamentais para o estudo dos Códigos de Goppa via métodos elementares de álgebra linear e de semigrupos, tal estudo foi baseado em ¿Algebraic geometry codes¿ de J. H. van Lint, R. Pellikaan e T. Hfhold.A dissertação termina com a apresentação de exemplos que ilustram os métodos elementares que nos referimos acima
Abstract: The central objective of this dissertation was to present the Goppa Geometry Codes via elementary methods which were introduced by J. H. van Lint, R. Pellikaan and T. Hfhold about 1998. On the first past of such dissertation are presented the fundamental concepts about fields of rational functions of an algebraic curve in the direction as to define the Goppa Codes on a classical manner. In this study we based ourselves mainly on the book ¿Algebraic Function Fields and Codes¿ of H. Stichtenoth. The second part is initiated with an introduction about the functions weight, degree and order which are fundamental for the study of the Goppa Codes throught elementary methods of linear algebra and of semigroups and such study was based on ¿Algebraic Geometry Codes¿ of J. h. van Lint, R. Pellikaan and T. Hfhold. The dissertation ends up with a presentation of examples which illustrate the elementary methods that we have referred to above
Mestrado
Algebra
Mestre em Matemática

Petri nets were introduced by C.A. Petri as a theoretical model of concurrency in which the causal relationship between actions, rather than just their temporal ordering, can be represented. As a theoretical model of concurrency, Petri nets have been widely successful. Moreover, Petri nets are popular with practitioners, providing practical tools for the designer and developer of real concurrent and distributed systems. However, it is from this second context that perhaps the most widely voiced criticism of Petri nets comes. It is that Petri nets lack any algebraic structure or modularity, and this results in large, unstructured models of real systems, which are consequently often intractable. Although this is not a criticism of Petri nets per se, but rather of the uses to which Petri nets are put, the criticism is well taken. We attempt to answer this criticism in this work. To do this we return to the view of Petri nets as a model of concurrency and consider how other models of concurrency counter this objection. The foremost examples are then the synchronisation trees of Milner, and the traces of Hoare, (against which such criticism is rarely, if ever, levelled). The difference between the models is clear, and is to be found in the richness of the algebraic characterisations which have been made for synchronisation trees in Milner's Calculus of Communicating Systems (CCS), and for traces in Hoare's Communicating Sequential Processes (CSP). With this in mind we define, in this thesis, a class of high level Petri nets, High Level Petri Boxes, and provide for them a very general algebraic description language, the High Level Petri Box Algebra, with novel ideas for synchronisation, and including both refinement and recursion among its operators. We also begin on the (probably open-ended task of the) algebraic characterisation of High Level Petri Boxes. The major contribution of this thesis is a full behavioural characterisation of the High Level Petri Boxes which form the semantic domain of the algebra. Other contributions are: a very general method of describing communication protocols which extend the synchronisation algebras of Winskel; a recursive operator that preserves finiteness of state (the best possible, given the generality of the algebra); a refinement operator that is syntactic in nature, and for which the recursive construct is a behavioural fix-point; and a notion of behavioural equivalence which is a congruence with respect to a major part of the High Level Petri Box Algebra.

In coding theory we wish to find as many codewords as possible, while simultaneously maintaining high distance between codewords to ease the detection and correction of errors. For linear codes, this translates to finding high-dimensional subspaces of a given metric space, where the induced distance between vectors stays above a specified minimum. In this work I describe the recent advances of this problem in the contexts of lexicodes and Ferrers diagram rank-metric codes. In the first chapter, we study lexicodes. For a ring R, we describe a lexicographic ordering of the left R-module Rn. With this ordering we set up a greedy algorithm which sequentially selects vectors for which all linear combinations satisfy a given property. The resulting output is called a lexicode. This process was discussed earlier in the literature for fields and chain rings. We describe a generalization of the algorithm to finite principal ideal rings. In the second chapter, we investigate Ferrers diagram rank-metric codes, which play a role in the construction of subspace codes. A well-known upper bound for dimension of these codes is conjectured to be sharp. We describe several solved cases of the conjecture, and further contribute new ones. In addition, probabilities for maximal Ferrers diagram codes and MRD codes are investigated in a new light. It is shown that for growing field size, the limiting probability depends highly on the Ferrers diagram.

Cette thèse, à la frontière entre les mathématiques et l'informatique, est consacrée en partie à l'étude des paramètres et des propriétés des codes de Goppa sur les surfaces de Hirzebruch. D'un point de vue arithmétique, la théorie des codes correcteurs a ravivé la question du nombre de points rationnels d'une variété définie sur un corps fini, qui semblait résolue par la formule de Lefschetz. La distance minimale de codes géométriques donne un majorant du nombre de points rationnels d'une hypersurface d'une variété donnée et de classe de Picard fixée. Ce majorant étant le plus souvent atteint pour les courbes très réductibles, il est naturel de se concentrer sur les courbes irréductibles pour affiner les bornes. On présente une stratégie globale pour majorer le nombre de points d'une variété en fonction de son ambiant et d'invariants géométriques, notamment liés à la théorie de l'intersection. De plus, une méthode de ce type pour les courbes d'une surface torique est développée en adaptant l'idée de F.J Voloch et K.O. Sthör aux variétés toriques. Enfin, on s'intéresse aux protocoles de Private Information Retrivial, qui visent à assurer qu'un utilisateur puisse accéder à une entrée d'une base de données sans révéler d'information sur l'entrée au propriétaire de la base de données. Un protocole basé sur des codes sur des plans projectifs pondérés est proposé ici. Il améliore les protocoles existants en résistant à la collusion de serveurs, au prix d'une grande perte de capacité de stockage. On pallie ce problème grâce à la méthode du lift qui permet la construction de familles de codes asymptotiquement bonnes, avec les mêmes propriétés locales
A part of this thesis, at the interface between Computer Science and Mathematics, is dedicated to the study of the parameters ans properties of Goppa codes over Hirzebruch surfaces. From an arithmetical perspective, the question about number of rational points of a variety defined over a finite field, which seemed dealt with by Lefchetz formula, regained interest thanks to error correcting codes. The minimum distance of an algebraic-geometric codes provides an upper bound of the number of rational points of a hypersurface of a given variety and with a fixed Picard class. Since reducible curves are most likely to reach this bound, one can focus on irreducible curves to get sharper bounds. A global strategy to bound the number of points on a variety depending on its ambient space and some of its geometric invariants is exhibited here. Moreover we develop a method for curves on toric surfaces by adapting F.J. Voloch et K.O. Sthör's idea on toric varieties. Finally, we interest in Private Information Retrivial protocols, which aim to ensure that a user can access an entry of a database without revealing any information on it to the database owner. A PIR protocol based on codes over weighted projective planes is displayed here. It enhances other protocols by offering a resistance to servers collusions, at the expense of a loss of storage capacity. This issue is fixed by a lifting process, which leads to asymptotically good families of codes, with the same local properties

In this thesis the relationship between Gröbner bases and algebraic coding theory is investigated, and especially applications towards linear codes, with Reed-Müller codes as an illustrative example. We prove that each linear code can be described as a binomial ideal of a polynomial ring, and that a systematic encoding algorithm for such codes is given by the remainder of the information word computed with respect to the reduced Gröbner basis. Finally we show how to apply the representation of a code by its corresponding polynomial ring ideal to construct a class of codes containing the so called primitive Reed-Müller codes, with a few examples of this result.

In 1981 V.D. Goppa [9] used the evaluation of rational functions on algebraic curves to define a new and exciting class of error correcting codes now known as geometric Goppa codes. As with any other error correcting code however, this construction procedure alone was only the beginning of what was need in order that these codes could be used in practice. Procedures needed to be found to aid in both the explicit construction of certain geometric Goppa codes and the creation of efficient decoding algorithms. The problems surrounding these concerns have since motivated many coding theorists to become actively involved in the study of algebraic curves and have equally sparked the interests of algebraic geometers. In this paper I introduce the topic of coding theory and highlight the successes and failures that have occurred in the attempt to bring geometric Goppa codes to their full stage of implementation. In the first two chapters, I give a basic introduction to the theory of error correcting codes, assuming no previous knowledge of the subject. Chapter 3 is concerned with the construction of rational geometric Goppa codes for which no knowledge of algebraic curves is necessary. Various positive and negative aspects of these codes are discussed which motivates the introduction of the general class of geometric Goppa codes in the following two chapters. For the material in Chapters 4 and 5, I will assume that the reader is familiar with divisors and linear systems on non-singular projective curves. After I define the class of geometric Goppa codes, I go on to discuss the advances that have been made in the search for explicit constructions of some of the best codes in this class. Finally, I present some basic decoding algorithms for both rational and general geometric Goppa codes. These algorithms demonstrate how easy it is to develop efficient decoders in both of these cases.

Yeung Wai Ling Winnie.
Thesis (M.Phil.)--Chinese University of Hong Kong, 2006.
Includes bibliographical references (leaves 99-100).
Abstracts in English and Chinese.
Chapter 1 --- Introduction --- p.1
Chapter 2 --- Finite Fields --- p.4
Chapter 2.1 --- Basic Properties of Finite Fields --- p.4
Chapter 2.2 --- Existence and Uniqueness of Finite Fields --- p.8
Chapter 2.3 --- Algorithms in Factoring Polynomials --- p.11
Chapter 2.3.1 --- Factorization of xn ´ؤ 1 --- p.11
Chapter 2.3.2 --- Berlekamp Algorithm for Factorizing an Arbitrary Polynomial --- p.13
Chapter 3 --- Algebraic Curves --- p.17
Chapter 3.1 --- Affine and Projective Curves --- p.17
Chapter 3.2 --- Local Properties and Intersections of Curves --- p.19
Chapter 3.3 --- Linear Systems of Curves and Noether's Theorem --- p.24
Chapter 3.4 --- Rational Function and Divisors --- p.29
Chapter 3.5 --- Differentials on a Curve --- p.34
Chapter 3.6 --- Riemann-Roch Theorem --- p.36
Chapter 4 --- Coding Theory --- p.46
Chapter 4.1 --- Introduction to Coding Theory --- p.46
Chapter 4.1.1 --- Basic Definitions for Error-Correcting Code --- p.46
Chapter 4.1.2 --- Geometric Approach to Error-Correcting Capabilities of Codes --- p.48
Chapter 4.2 --- Linear Codes --- p.49
Chapter 4.2.1 --- The Dual of a Linear Code --- p.54
Chapter 4.2.2 --- Syndrome Decoding --- p.57
Chapter 4.2.3 --- Extension of Basic Field --- p.60
Chapter 4.3 --- The Main Problem in Coding Theory --- p.62
Chapter 4.3.1 --- "Elementary Results on Aq(n, d)" --- p.63
Chapter 4.3.2 --- "Lower Bounds on Aq(n, d)" --- p.63
Chapter 4.3.3 --- "Upper Bounds on Aq(n,d)" --- p.65
Chapter 4.3.4 --- Asymptotic Bounds --- p.67
Chapter 4.4 --- Rational Codes --- p.68
Chapter 4.4.1 --- Hamming Codes --- p.68
Chapter 4.4.2 --- Codes on an Oval --- p.69
Chapter 4.4.3 --- Codes on a Twisted Cubic Curve --- p.78
Chapter 4.4.4 --- Normal Rational Codes --- p.82
Chapter 4.5 --- Goppa Codes --- p.84
Chapter 4.5.1 --- Classical Goppa Codes --- p.85
Chapter 4.5.2 --- Geometric Goppa Codes --- p.88
Chapter 4.5.3 --- Good Codes from Algebraic Geometry --- p.91
Chapter 4.6 --- A Recent Non-linear Code Improving the Tsfasman- Vladut-Zink Bound --- p.93
Bibliography --- p.99

by Yan Cho Hung.
Thesis (M.Phil.)--Chinese University of Hong Kong, 1998.
Includes bibliographical references (leaves 122-124).
Abstract also in Chinese.
Chapter 1 --- Complex algebraic curves --- p.6
Chapter 1.1 --- Foundations --- p.6
Chapter 1.1.1 --- Hilbert Nullstellensatz --- p.6
Chapter 1.1.2 --- Complex algebraic curves in C2 --- p.9
Chapter 1.1.3 --- Complex projective curves in P2 --- p.11
Chapter 1.1.4 --- Affine and projective curves --- p.13
Chapter 1.2 --- Algebraic properties of complex projective curves in P2 --- p.16
Chapter 1.2.1 --- Intersection multiplicity --- p.16
Chapter 1.2.2 --- Bezout's theorem and its applications --- p.18
Chapter 1.2.3 --- Cubic curves --- p.21
Chapter 1.3 --- Topological properties of complex projective curves in P2 --- p.23
Chapter 1.4 --- Riemann surfaces --- p.26
Chapter 1.4.1 --- Weierstrass &-function --- p.26
Chapter 1.4.2 --- Riemann surfaces and examples --- p.27
Chapter 1.5 --- Differentials on Riemann surfaces --- p.28
Chapter 1.5.1 --- Holomorphic differentials --- p.28
Chapter 1.5.2 --- Abel's Theorem for tori --- p.31
Chapter 1.5.3 --- The Riemann-Roch theorem --- p.32
Chapter 1.6 --- Singular curves --- p.36
Chapter 1.6.1 --- Resolution of singularities --- p.37
Chapter 1.6.2 --- The topology of singular curves --- p.45
Chapter 2 --- Coding theory --- p.48
Chapter 2.1 --- An introduction to codes --- p.48
Chapter 2.1.1 --- Efficient noiseless coding --- p.51
Chapter 2.1.2 --- The main coding theory problem --- p.56
Chapter 2.2 --- Linear codes --- p.58
Chapter 2.2.1 --- Syndrome decoding --- p.63
Chapter 2.2.2 --- Equivalence of codes --- p.65
Chapter 2.2.3 --- An introduction to cyclic codes --- p.67
Chapter 2.3 --- Special linear codes --- p.71
Chapter 2.3.1 --- Hamming codes --- p.71
Chapter 2.3.2 --- Simplex codes --- p.72
Chapter 2.3.3 --- Reed-Muller codes --- p.73
Chapter 2.3.4 --- BCH codes --- p.75
Chapter 2.4 --- Bounds on codes --- p.77
Chapter 2.4.1 --- Spheres in Zn --- p.77
Chapter 2.4.2 --- Perfect codes --- p.78
Chapter 2.4.3 --- Famous numbers Ar (n，d) and the sphere-covering and sphere packing bounds --- p.79
Chapter 2.4.4 --- The Singleton and Plotkin bounds --- p.81
Chapter 2.4.5 --- The Gilbert-Varshamov bound --- p.83
Chapter 3 --- Algebraic curves over finite fields and the Goppa codes --- p.85
Chapter 3.1 --- Algebraic curves over finite fields --- p.85
Chapter 3.1.1 --- Affine varieties --- p.85
Chapter 3.1.2 --- Projective varieties --- p.37
Chapter 3.1.3 --- Morphisms --- p.89
Chapter 3.1.4 --- Rational maps --- p.91
Chapter 3.1.5 --- Non-singular varieties --- p.92
Chapter 3.1.6 --- Smooth models of algebraic curves --- p.93
Chapter 3.2 --- Goppa codes --- p.96
Chapter 3.2.1 --- Elementary Goppa codes --- p.96
Chapter 3.2.2 --- The affine and projective lines --- p.98
Chapter 3.2.3 --- Goppa codes on the projective line --- p.102
Chapter 3.2.4 --- Differentials and divisors --- p.105
Chapter 3.2.5 --- Algebraic geometric codes --- p.112
Chapter 3.2.6 --- Codes with better rates than the Varshamov- Gilbert bound and calculation of parameters --- p.116
Bibliography

The study of codes, classically motivated by the need to communicate information reliably in the presence of error, has found new life in fields as diverse as network communication, distributed storage of data, and even has connections to the design of linear measurements used in compressive sensing. But in all contexts, a code typically involves exploiting the algebraic or geometric structure underlying an application. In this thesis, we examine several problems in coding theory, and try to gain some insight into the algebraic structure behind them.

The first is the study of the entropy region - the space of all possible vectors of joint entropies which can arise from a set of discrete random variables. Understanding this region is essentially the key to optimizing network codes for a given network. To this end, we employ a group-theoretic method of constructing random variables producing so-called "group-characterizable" entropy vectors, which are capable of approximating any point in the entropy region. We show how small groups can be used to produce entropy vectors which violate the Ingleton inequality, a fundamental bound on entropy vectors arising from the random variables involved in linear network codes. We discuss the suitability of these groups to design codes for networks which could potentially outperform linear coding.

The second topic we discuss is the design of frames with low coherence, closely related to finding spherical codes in which the codewords are unit vectors spaced out around the unit sphere so as to minimize the magnitudes of their mutual inner products. We show how to build frames by selecting a cleverly chosen set of representations of a finite group to produce a "group code" as described by Slepian decades ago. We go on to reinterpret our method as selecting a subset of rows of a group Fourier matrix, allowing us to study and bound our frames' coherences using character theory. We discuss the usefulness of our frames in sparse signal recovery using linear measurements.

The final problem we investigate is that of coding with constraints, most recently motivated by the demand for ways to encode large amounts of data using error-correcting codes so that any small loss can be recovered from a small set of surviving data. Most often, this involves using a systematic linear error-correcting code in which each parity symbol is constrained to be a function of some subset of the message symbols. We derive bounds on the minimum distance of such a code based on its constraints, and characterize when these bounds can be achieved using subcodes of Reed-Solomon codes.

This work has reached several results. The first is, that it was possible to find a new, algebraic frame in which we can formulate stabilizer codes and show, that the choice of generators of a stabilizer algebra corresponds to choosing a representation of finitely many Rademacher functions in a matrix algebra. The second part of this work was to develop a quantum coding theory as a quantum analogue of classical coding theory. We do this by using a systematical view of quantum probability theory that was introduced by Kümmerer [1]. We follow this way of algebraization and develop analogously a quantum coding theory. Our result differs in some points from what has been developed so far, mainly because we are working not only with pure but also arbitrary states as well as infinitely many coupled qubits. We were able to integrate the common examples of quantum codes into our theory. The third main result is that we were able to show that the most important quantum algorithms, including stabilizer codes and the Shor algorithm, are in some sense commutative and thus classical. This could be done as quantum algorithms fit into the notion of quantum measurements, and our calculations imply that they can be represented as a coupling to a classical Bernoulli shift. [1] B. Kümmerer, Markov Dilations on W*-Algebras, Journal Functional Analysis, 63:139-177, 1985.

by Ho Kin Ming.
Thesis (M.Phil.)--Chinese University of Hong Kong, 1999.
Includes bibliographical references (leaves 68-69).
Abstracts in English and Chinese.
Chapter 0 --- Introduction --- p.5
Chapter 1 --- Introduction to Coding Theory --- p.9
Chapter 1.1 --- Definition of a code --- p.10
Chapter 1.2 --- Maximum Likelihood Decoding --- p.11
Chapter 1.3 --- Syndrome Decoding --- p.12
Chapter 1.4 --- Two Kinds of Errors and Concatenated Code --- p.14
Chapter 2 --- Basic Knowledge of Algebraic Curve --- p.16
Chapter 2.1 --- Affine and Projective Curve --- p.16
Chapter 2.2 --- Regular Functions and Maps --- p.17
Chapter 2.3 --- Divisors and Differential forms --- p.19
Chapter 2.4 --- Riemann-Roch Theorem --- p.21
Chapter 3 --- Construction of Algebraic Geometric Code --- p.23
Chapter 3.1 --- L-construction --- p.23
Chapter 3.2 --- Ω -construction --- p.24
Chapter 3.3 --- Duality --- p.26
Chapter 4 --- Basic Error Processing --- p.28
Chapter 4.1 --- Error Locators and Syndromes --- p.28
Chapter 4.2 --- Finding an Error Locator --- p.29
Chapter 5 --- Full Error Processing for Code on Curve of Genus1 --- p.34
Chapter 5.1 --- Syndrome table --- p.34
Chapter 5.2 --- Syndrome table --- p.36
Chapter 5.3 --- The algorithm of Full Error Processing --- p.38
Chapter 5.4 --- A simple Example --- p.40
Chapter 6 --- General Full Error Processing --- p.47
Chapter 6.1 --- Row Candidate and Column Candidate --- p.47
Chapter 6.2 --- Consistency --- p.49
Chapter 6.3 --- Majority voting --- p.50
Chapter 6.4 --- Example --- p.53
Chapter 7 --- Application of Algebraic Geometric Code --- p.60
Chapter 7.1 --- Communication --- p.60
Chapter 7.2 --- Cryptosystem --- p.62
Bibliography

Tradicionalmente la Teoría de Códigos se ocupó de construir y analizar códigos sobre cuerpos finitos. Con el tiempo, también comenzaron a considerarse códigos sobre estructuras algebraicas más generales, como anillos, módulos y grupos. Esto llevó a la necesidad de considerar nuevas métricas, además de la clásica métrica de Hamming, más adecuadas para cada una de esas estructuras. En este trabajo, estudiaremos el espacio de métricas sobre grupos y anillos, en base a equivalencias, de las cuales podremos obtener propiedades generales de métricas especificas de interés para la Teoría de Códigos. Además estudiaremos los grupos de simetrías de métricas, los cuales nos permitirán decidir la existencia o no de isometrías entre espacios con estructuras distintas, obteniendo generalizaciones del conocido mapa de Gray. En particular, estudiaremos las métricas poset; y en el caso de posets jerárquicos, daremos una descripción de su grupo de simetrías, sus identidades de MacWilliams respectivas y describiremos algunas nuevas isometrías obtenidas.

As parallel and distributed systems scale to hundreds of thousands of cores and beyond, fault tolerance becomes increasingly important -- particularly on systems with limited I/O capacity and bandwidth. Error correcting codes (ECCs) are used in communication systems where errors arise when bits are corrupted silently in a message. Error correcting codes can detect and correct erroneous bits. Erasure codes, an instance of error correcting codes that deal with data erasures, are widely used in storage systems. An erasure code addsredundancy to the data to tolerate erasures.

In this thesis, erasure coded computations are proposed as a novel approach to dealing with processor faults in parallel and distributed systems. We first give a brief review of traditional fault tolerance methods, error correcting codes, and erasure coded storage. The benefits and challenges of erasure coded computations with respect to coding scheme, fault models and system support are also presented.

In the first part of my thesis, I demonstrate the novel concept of erasure coded computations for linear system solvers. Erasure coding augments a given problem instance with redundant data. This augmented problem is executed in a fault oblivious manner in a faulty parallel environment. In the event of faults, we show how we can compute the true solution from potentially fault-prone solutions using a computationally inexpensive procedure. The results on diverse linear systems show that our technique has several important advantages: (i) as the hardware platform scales in size and in number of faults, our scheme yields increasing improvement in resource utilization, compared to traditional schemes; (ii) the proposed scheme is easy to code as the core algorithm remains the same; (iii) the general scheme is flexible to accommodate a range of computation and communication trade-offs.

We propose a new coding scheme for augmenting the input matrix that satisfies the recovery equations of erasure coding with high probability in the event of random failures. This coding scheme also minimizes fill (non-zero elements introduced by the coding block), while being amenable to efficient partitioning across processing nodes. Our experimental results show that the scheme adds minimal overhead for fault tolerance, yields excellent parallel efficiency and scalability, and is robust to different fault arrival models and fault rates.

Building on these results, we show how we can minimize, to optimality, the overhead associated with our problem augmentation techniques for linear system solvers. Specifically, we present a technique that adaptively augments the problem only when faults are detected. At any point during execution, we only solve a system with the same size as the original input system. This has several advantages in terms of maintaining the size and conditioning of the system, as well as in only adding the minimal amount of computation needed to tolerate the observed faults. We present, in details, the augmentation process, the parallel formulation, and the performance of our method. Specifically, we show that the proposed adaptive fault tolerance mechanism has minimal overhead in terms of FLOP counts with respect to the original solver executing in a non-faulty environment, has good convergence properties, and yields excellent parallel performance.

Based on the promising results for linear system solvers, we apply the concept of erasure coded computation to eigenvalue problems, which arise in many applications including machine learning and scientific simulations. Erasure coded computation is used to design a fault tolerant eigenvalue solver. The original eigenvalue problem is reformulated into a generalized eigenvalue problem defined on appropriate augmented matrices. We present the augmentation scheme, the necessary conditions for augmentation blocks, and the proofs of equivalence of the original eigenvalue problem and the reformulated generalized eigenvalue problem. Finally, we show how the eigenvalues can be derived from the augmented system in the event of faults.

We present detailed experiments, which demonstrate the excellent convergence properties of our fault tolerant TraceMin eigensolver in the average case. In the worst case where the row-column pairs that have the most impact on eigenvalues are erased, we present a novel scheme that computes the augmentation blocks as the computation proceeds, using the estimates of leverage scores of row-column pairs as they are computed by the iterative process. We demonstrate low overhead, excellent scalability in terms of the number of faults, and the robustness to different fault arrival models and fault rates for our method.

In summary, this thesis presents a novel approach to fault tolerance based on erasure coded computations, demonstrates it in the context of important linear algebra kernels, and validates its performance on a diverse set of problems on scalable parallel computing platforms. As parallel systems scale to hundreds of thousands of processing cores and beyond, these techniques present the most scalable fault tolerant mechanisms currently available.

Sun, Qifu.
Thesis (Ph.D.)--Chinese University of Hong Kong, 2009.
Includes bibliographical references (leaves 95-99).
Electronic reproduction. Hong Kong : Chinese University of Hong Kong, [2012] System requirements: Adobe Acrobat Reader. Available via World Wide Web.
Abstract also in Chinese.

Cooperative relay communication is a promising means of wireless communication in which cooperation is used to create a virtual transmit array between the source and the destination, thereby providing spatial diversity for combating the fading channel. In this thesis we develop cooperative communication protocols namely the orthogonal amplify-and-forward (OAF), non-orthogonal and orthogonal selection decode-and-forward (NSDF and OSDF) protocols. The diversity-multiplexing gain tradeoff (DMT) of the three protocols is determined and DMT-optimal distributed space-time code constructions are provided. The code construction is based on Cyclic Division Algebras. The codes constructed are sphere decodable and in some instances incur minimum possible delay. Included in our results is the perhaps surprising finding that the OAF and NAF protocols have identical DMT when the time durations of the broadcast and cooperative phases are optimally chosen to suit the respective protocol. Two variants of the NSDF protocol are considered: fixed-NSDF and variable-NSDF protocol. In the variable-NSDF protocol, the fraction of time occupied by the broadcast phase is allowed to vary with multiplexing gain. In the two-relay case, the variable-NSDF protocol is shown to improve on the DMT of the best previously-known static protocol for higher values of multiplexing gain. Our results also establish that the fixed-NSDF protocol has a better DMT than the NAF protocol for any number of relays.

It is well known that communication systems employing multiple transmit and multiple receive antennas provide high data rates along with increased reliability. Some of the design criteria of the space-time block codes (STBCs) for multiple input multiple output (MIMO)communication system are that these codes should attain large transmit diversity, high data-rate, low decoding-complexity, low decoding –delay and low peak-to-average power ratio (PAPR). STBCs based on real orthogonal designs (RODs) and complex orthogonal designs (CODs) achieve full transmit diversity and in addition, these codes are single-symbol maximum-likelihood (ML) decodable. It has been observed that the data-rate (in number of information symbols per channel use) of the square CODs falls exponentially with increase in number of antennas and it has led to the construction of rectangular CODs with high rate. We have constructed a class of maximal-rate CODs for n transmit antennas with rate if n is even and if n is odd. The novelty of the above construction is that they 2n+1 are constructed from square CODs. Though these codes have a high rate, this is achieved at the expense of large decoding delay especially when the number of antennas is 5or more. Moreover the rate also converges to half as the number of transmit antennas increases. We give a construction of rate-1/2 CODs with a substantial reduction in decoding delay when compared with the maximal- rate codes. Though there is a significant improvement in the rate of the codes mentioned above when compared with square CODs for the same number of antennas, the decoding delay of these codes is still considerably high. For certain applications, it is desirable to construct codes which are balanced with respect to both rate and decoding delay. To this end, we have constructed high rate and low decoding-delay RODs and CODs from Cayley-Dickson Algebra. Apart from the rate and decoding delay of orthogonal designs, peak-to-average power ratio (PAPR) of STBC is very important from implementation point of view. The standard constructions of square complex orthogonal designs contain a large number of zeros in the matrix result in gin high PAPR. We have given a construction for square complex orthogonal designs with lesser number of zero entries than the known constructions. When a + 1 is a power of 2, we get codes with no zero entries. Further more, we get complex orthogonal designs with no zero entry for any power of 2 antennas by introducing co- ordinate interleaved variables in the design matrix. These codes have significant advantage over the existing codes in term of PAPR. The only sacrifice that is made in the construction of these codes is that the signaling complexity (of these codes) is marginally greater than the existing codes (with zero entries) for some of the entries in the matrix consist of co-ordinate interleaved variables. Also a class of maximal-rate CODs (For mathematical equations pl see the pdf file)