Low density parity check (LDPC) codes with iterative decoding based on belief propagation achieve astonishing error performance close to Shannon limit. No algebraic or geometric method for constructing these codes has been reported and they are largely generated by computer search. As a result, encoding of long LDPC codes is in general very complex. This paper presents two classes of high rate LDPC codes whose constructions are based on finite Euclidean and projective geometries, respectively. These classes of codes a.re cyclic and have good constraint parameters and minimum distances. Cyclic structure adows the use of linear feedback shift registers for encoding. These finite geometry LDPC codes achieve very good error performance with either soft-decision iterative decoding based on belief propagation or Gallager's hard-decision bit flipping algorithm. These codes can be punctured or extended to obtain other good LDPC codes. A generalization of these codes is also presented.Kou, Yu and Lin, Shu and Fossorier, MarcGoddard Space Flight CenterEUCLIDEAN GEOMETRY; ALGORITHMS; DECODING; PARITY; ALGEBRA; INFORMATION THEORY; PROJECTIVE GEOMETRY; TWO DIMENSIONAL MODELS; COMPUTERIZED SIMULATION; ERRORS; BLOCK DIAGRAMS...

In this doctoral dissertation, two constructions of binary low-density parity-check (LDPC) codes with quasi-cyclic (QC) structures are presented. A general construction of RC-constrained arrays of circulant permutation matrices is introduced, then two specific construction methods based on Latin squares and cyclic subgroups are presented. Array masking is also proposed to improve the waterfall-region performance of the QC-LDPC codes. Also, by analyzing the parity check matrices of these codes, combinatorial expressions for their ranks and dimensions are derived. Experimental results show that, with iterative decoding algorithms, the constructed codes perform very well over both the additive white Gaussian noise (AWGN) and the binary erasure channels (BEC). Also presented in this dissertation are constructions of QC-LDPC codes based on two special classes of balanced incomplete block designs (BIBDs) derived by Bose. Codes are constructed for both the AWGN channel and the binary burst erasure channel (BBEC). Experimental results show that the codes constructed perform well not only over these two types of channels but also over the BEC. Finally, a two stage iterative decoding is presented to decode a class of cyclic Euclidean geometry codes. By exploiting the inherent geometry structure of the codes and avoiding the degrading effect of short cycles, the proposed algorithm provides good decoding performance of the codes.

A binary low-density parity-check (LDPC) code is a linear block code that is defined by a sparse parity-check matrix H, that is H has a low density of 1's. LDPC codes were originally presented by Gallager in his doctoral dissertation [9], but largely overlooked for the next 35 years. A notable exception was [29], in which Tanner introduced a graphical representation for LDPC codes, now known as Tanner graphs. However, interest in these codes has greatly increased since 1996 with the publication of [22] and other papers, since it has been realised that LDPC codes are capable of achieving near-optimal performance when decoded using iterative decoding algorithms. LDPC codes can be constructed randomly by using a computer algorithm to generate a suitable matrix H. However, it is also possible to construct LDPC codes explicitly using various incidence structures in discrete mathematics. For example, LDPC codes can be constructed based on the points and lines of finite geometries: there are many examples in the literature (see for example [18, 28]). These constructed codes can possess certain advantages over randomly-generated codes. For example they may provide more efficient encoding algorithms than randomly-generated codes. Furthermore it can be easier to understand and determine the properties of such codes because of the underlying structure. LDPC codes have been constructed based on incidence structures known as partial geometries [16]. The aim of this research is to provide examples of new codes constructed based on structures known as semipartial geometries (SPGs), which are generalisations of partial geometries. Since the commencement of this thesis [19] was published, which showed that codes could be constructed from semipartial geometries and provided some examples and basic results. By necessity this thesis contains a number of results from that paper. However, it should be noted that the scope of [19] is fairly limited and that the overlap between the current thesis and [19] is consequently small. [19] also contains a number of errors, some of which have been noted and corrected in this thesis.

This book discusses both the theory and practical applications of self-correcting data, commonly known as error-correcting codes. The applications included demonstrate the importance of these codes in a wide range of everyday technologies, from smartphones to secure communications and transactions. Written in a readily understandable style, the book presents the authors’ twenty-five years of research organized into five parts: Part I is concerned with the theoretical performance attainable by using error correcting codes to achieve communications efficiency in digital communications systems. Part II explores the construction of error-correcting codes and explains the different families of codes and how they are designed. Techniques are described for producing the very best codes. Part III addresses the analysis of low-density parity-check (LDPC) codes, primarily to calculate their stopping sets and low-weight codeword spectrum which determines the performance of th ese codes. Part IV deals with decoders designed to realize optimum performance. Part V describes applications which include combined error correction and detection, public key cryptography using Goppa codes, correcting errors in passwords and watermarking. This book is a valuable resource for anyone interested in error-correcting codes and their applications, ranging from non-experts to professionals at the forefront of research in their field. This book is open access under a CC BY 4.0 license.

This book constitutes the refereed proceedings of the 15th International Symposium on Applied Algebra, Algebraic Algorithms and Error-Correcting Codes, AAECC-15, held in Toulouse, France, in May 2003.The 25 revised full papers presented together with 2 invited papers were carefully reviewed and selected from 40 submissions. Among the subjects addressed are block codes; algebra and codes: rings, fields, and AG codes; cryptography; sequences; decoding algorithms; and algebra: constructions in algebra, Galois groups, differential algebra, and polynomials.