Codes and Rings: Theory and Practice

By Minjia Shi, Adel Alahmadi and Patrick Solé

Codes and Rings: Theory and Practice is a systematic review of literature that focuses on codes over rings and rings acting on codes. Since the breakthrough works on quaternary codes in the 1990s, two decades of research have moved the field far beyond its original periphery. This book fills this gap by consolidating results scattered in the literature, addressing classical as well as applied aspects of rings and coding theory.

New research covered by the book encompasses skew cyclic codes, decomposition theory of quasi-cyclic codes and related codes and duality over Frobenius rings. Primarily suitable for ring theorists at PhD level engaged in application research and coding theorists interested in algebraic foundations, the work is also valuable to computational scientists and working cryptologists in the area.

• Consolidates 20+ years of research in one volume, helping researchers save time in the evaluation of disparate literature
• Discusses duality formulas in the context of Frobenius rings
• Reviews decomposition of quasi-cyclic codes under ring action
• Evaluates the ideal and modular structure of skew-cyclic codes
• Supports applications in data compression, distributed storage, network coding, cryptography and across error-correction

• Language: English
• Publisher: Academic Press
• Release date: Jun 12, 2017
• ISBN: 9780128133910

Minjia Shi

Minjia Shi is an Associate Professor of Mathematics in the School of Mathematical Sciences of Anhui University since 2012, P. R. China. He is the author of more than 60 journal papers and one book. He is interested in algebraic coding, cryptography and related fields.

Book preview

Professor."

Introduction

Rings form an important topic in Algebra, both pure and applied, from Number Theory to Algebraic Geometry. Coding theory, on the other hand, is present in our daily lives, from mobile phones to flash memories. It is the art of protecting messages from natural noise, by a redundant arithmetic representation, a code. Rings can interact with codes in two fundamental ways. Firstly, the alphabet of the codes can have a ring structure, a finite field, for instance. Secondly, the code itself can be an ideal of, or a module over, some ring. This interplay justifies the project to write a book entitled Codes and Rings.

The first way, for rings that are not fields, has been well documented since the 1990s when cyclic codes over the integers modulo 4 appeared, in the wake of -codes that improve on the Preparata Goethals family, and use them to produce pseudo-random sequences. In most of the present book, however, we have tried to extend the class of alphabets considered, beyond Galois rings, to chain rings and Frobenius rings. We did not cover the structure of cyclic codes over chain rings and the duality theory over Frobenius rings which have received thorough expositions in the book [7]. We have chapters on, respectively, few weight codes, self-dual codes, and linear codes. The combinatorics of two-weight codes for the homogeneous metric builds on the distance chapter, which studies the three most fundamental distances for codes over rings: Lee, homogeneous, and Hamming. The existence problem for self-dual codes over chain rings and Frobenius rings raises interesting arithmetical questions. Even the analogue over rings of the systematic form of the generator matrix is a nontrivial result, especially for nonlocal rings.

The second way has been known explicitly or implicitly since the 1960s, when cyclic codes and quasicyclic codes (QC) were introduced. The former are ideals in a polynomial ring and the latter are modules over the same ring. In the present century, in a series of papers, a structure theory for QC codes has been developed, based on decomposition theorems for this polynomial ring [3–6]. More recently, a similar study appeared for the class of quasitwisted (QT) codes, that generalizes both constacyclic and quasicyclic codes [10]. The chapters on QC and QT codes survey these developments, for the first time in book form. Another recent generalization of cyclic codes is the class of skew cyclic codes, which replaces polynomial rings in the definition by skew polynomial rings. This trend is treated for the first time in book form, in the chapter on skew cyclic codes.

, for m a prime, but can easily be rewritten at the level of chain rings.

To justify the second part of the title (Theory and Practice) we can say that in Coding Theory the most abstract algebraic developments can be motivated by, or can lead to, engineering applications. Some of these are sketched in Chapter 1, called Motivation: low correlation sequences, Euclidean lattices, combinatorial designs. More can be found in the last section of Chapter 11, on skew cyclic codes, namely space–time coding. Even more diverse applications to pseudo-random sequences, and more generally, to signal processing appear in the last section of the last chapter.

There are many topics we could not accommodate due to lack of time, space, or competence. For instance, there are many papers, by many authors, dealing with the decoding of codes over rings, for various metrics, and this topic would deserve another book. Similarly, we avoided the topic of Goppa codes over rings, which is well-covered in [1], and requires a deep background in algebraic and arithmetic geometry.

To conclude, we would like to thank the hospitality of several hosting institutions. MS would like thank Telecom ParisTech, Comelec department, where he stayed during the months of July–August 2016. PS would like to thank Anhui University Mathematics Department, where he stayed during the months of September–October 2016.

We also thanks the various friends and colleagues who have helped us in this project: S. Dougherty, D. Glynn, Y. Guan, S. Jitman, S. Ling, L. Qian, M. El Oued, and J. Yan.

References

[1] K. Bartley, J. Walker, Algebraic geometric codes over rings, In: E. Martinez-Moro, C. Munuera, D. Ruano, eds. Advances in Algebraic Geometry Codes. Series on Coding Theory and Cryptography. World Scientific; 2008:323–361.

-linearity of Kerdock, Preparata, Goethals and related codes, IEEE Trans. Inf. Theory 1994;40:301–319.

[3] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes I: finite fields, IEEE Trans. Inf. Theory 2001;47:2751–2760.

[4] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes II: chain rings, Des. Codes Cryptogr. 2003;30:113–130.

[5] S. Ling, P. Solé, On the algebraic structure of quasi-cyclic codes III: generator theory, IEEE Trans. Inf. Theory 2005;51:2692–2700.

[6] S. Ling, H. Niederreiter, P. Solé, On the algebraic structure of quasi-cyclic codes IV: repeated roots, Des. Codes Cryptogr. 2006;38(3):337–361.

[7] P. Solé, Codes over Rings. World Scientific; 2008.

[8] Z.-X. Wan, Quaternary Codes. World Scientific; 1997.

[9] Z.-X. Wan, Lectures on Finite Fields and Galois Rings. World Scientific; 2003.

[10] J. Yan, On quasi-twisted codes over finite fields, Finite Fields Appl. 2012;18(2):237–257.

Chapter 1

Motivation

Abstract

Gray map is sketched.

Keywords

Low correlation sequences; Euclidean lattices; Combinatorial designs; Gray map

1.1 The Geometry of Codes

A linear code of length n over a ring R is an R. For historical reasons, the ring R is called the alphabet and the elements of C are called codewords. We assume the existence of a metric d satisfying the three following axioms:

,

,

.

Classical coding theory is concerned with R the Hamming metric, namely

The so-called fundamental problem of coding theory , the maximum size of a code of length n over an alphabet of size q, such that the minimum pairwise distance between distinct codewords is at least δ. While the field structure plays no role in the definition of this abstract combinatorial function it is, however, essential in algebraic constructions. Generalizing this function from fields to rings, it is natural to define, for a given distance d, which is the maximum size of a code of length n over R such that the minimum pairwise distance between distinct codewords is at least δand d= the Lee distance (see Chapter 3 for a definition) this remains, at the time of this writing, a challenging open problem. The following sections will motivate some usual examples of R and d. It will be sometimes useful to define first a weight w satisfying the axioms:

,

,

. The axioms for the distance d then follow immediately. In the following sections we shall consider two types of weights:

1.  Lee weights (§1.4)

2.  Euclidean weights (§1.3)

The first weight function is obtained by taking the Hamming weight of an image of the vector in some finite field. The second weight function is obtained by taking the Euclidean weight of an image of the factor in a real space. The performance of a code for constructing low correlation sequences (§) derived from a weight.

1.2 Sequences

Assume that M users are speaking at the same time on the same channel. To recover who said what and when a digital signature of T digits is attributed to each user, and using phase modulation and complex correlators, the receiver can expect to understand something provided that

1.  The autocorrelation of each sequence assumes the shape of a Dirac function;

2.  The cross-correlation between any pair of distinct sequences is as flat as can be.

To construct such sequences which should be as pseudo-random as possible, we use linear recurrenceswith values in R with ω being a primitive complex kth root of unity. Another deterministic criterion for randomness of a sequence is the linear complexity: the length of the shortest Linear Feedback Shift Register (LFSR) that can generate it. For use of that criterion in a cryptographic perspective, see [25,26].

1.2.1 Periodic Correlation

denote two sequences of period T with values in

i.e., the set of qth complex roots of unity. The periodic correlation at time lag ℓ, say, of sequences x and y is defined as the Hermitian scalar product over a period of x and y shifted ℓ times, that is,

the indices being understood modulo T, it is called autocorrelation, and cross-correlation .

denote a family of M and all time lags ℓis usually denoted by

Sidelnikov proved in 1971 that when M and T ) we have

) we can merely ascertain that

The first bound was proved to be tight early on in 1967 (for so-called Gold sequences) but the status of the second bound remained unclear till 1988 ? We need to estimate from above the modulus of character sums of the type

where P is a polynomial and ω , that is, when the Galois ring is a Galois field, these are handled by Weil inequalities, or a special case thereof, known as Carlitz–Uchiyama bounds [19]. A nontrivial generalization of this type of bound to the p-adic situation at hand can be found in [18]. The case of a hybrid sum (that is, containing both additive and multiplicative characters) is partially treated in [22].

1.3 Lattices

An n, for instance. Lattices are useful in communications as group codes for the Gaussian channel and as codebooks for vector quantization of a lattice, which is fundamental for physicists studying crystal diffraction, and for number theorists involved with modular forms:

Since the 1970s there is a dictionary between codes and lattices as shown in the following table:

This analogy is materialized by construction A, which associates to a binary code C through the following formula:

. But construction A limits the norm of the lattice to 2. For dimensions larger than 8, a more sophisticated construction is needed, namely construction B. For instance, to construct the very dense and very symmetric Leech lattice (no less than three finite sporadic simple groups are built from it) John Leech in 1965 used the extended Golay code, construction B, which associates a lattice to a quaternary code by the formula

The first benefit is a simple interpretation of construction B is the single parity check code of length n, the repetition code of length 8, yields the celebrated Gosset lattice. This approach yields a simple proof for many theta series identities, old and new [24]. The above table becomes

, and 4. The so-called Lee weight enumerator or symmetrized weight enumerator is the trivariate generating function associated to this weight. Type II codes are self-dual codes containing the all-one vector and with Euclidean weights being multiples of 8 is defined in [6] as

denotes a code of length n into Type II lattices [6, Corollary 2.6].

1.4 Maps

1.4.1 Prehistory

of a linear code C with respect to the standard scalar product, namely

This is proved in . The matrix

and α has the simple weight distribution

, which would be cumbersome to obtain directly.

Nordstrom–Robinson code in 1967, nonlinear and still formally self-dual for the MacWilliams relation, followed in 1968 and 1972 [19] by the discovery of two finite families of nonlinear codes, the Preparata and Kerdock codes, respectively, whose weight enumerators are MacWilliams duals of each other and which were until [15] an unexplained phenomenon. The unsuccessful efforts of many distinguished researchers on that notoriously difficult problem [19] led one of them to declare [17] that it was merely a coincidence.

1.4.2 History

defined by

in the natural way. The key property is that the map

code of length 8 and minimum Lee distance 6. Seeing the parity-check matrix of that code

Neil Sloane identified this code with the octacode .

1.4.3 Present

The codes in [15] are quaternary analogues of the binary BCH codes. This line of research leads to an interesting code of length 64 in [5], which shows also, unfortunately, that an analogue of the BCH bound is hopeless. An algorithm for the decoding of the Goethals code, similar in spirit to the algorithm in [15] for the decoding of the Preparata code, is given in [16]. An improvement on the Delsarte–Goethals series of codes is contained in [21]. The next natural analogue was the quadratic residue codes and in particular the Golay code developed in [2,3,7,20]. The approach in [2,7] (in particular the derivation of the idempotents) is deliberately top-down while [20] is bottom-up and might be easier to read for a beginner. Very recently, analogues of doubly-circulant codes were derived [8]. All the codes developed in [3,8,11] and the motivation, Gray mapping aside, involve the study of Euclidean lattices. The problem of counting up to isometry all self-dual quaternary codes, which is open in [11], is solved in [13]. In the next table we indicate nonlinear binary codes obtained by Gray mapping with parameters as good or better than linear codes.

1.5 Designs

design is a family B of k-subsets of a v-set Ω such that each t-subset of Ω is included in exactly λ elements of B. For instance, a projective plane of order n design. Given a t-transitive group on Ω, it is known that orbits of G on k-sets constitute a