Abstract – A general algebraic method for decoding all cyclic codes up to their actual minimum distance d is presented. Full error-correcting capabilities t = [(d − 1)/2] of the codes are therefore achieved. In contrast to the decoding method recently suggested by Chen et. al., our method uses for the first time characteristic sets instead of Gröbner bases as the algebraic tool to solve the system of multivariate syndrome equations. The characteristic sets method is generally faster than the Gröbner bases method.

A new strategy called “Fill-Holes” method is also presented. It uses Gröbner bases or characteristic sets to find certain unknown syndromes and then combines the computational methods with the well-implemented BCH decoding algorithm.

Keywords – Coding theory, cyclic codes, decoding, ideal theory, Gröbner bases, characteristic sets.

INTRODUCTION

One important objective in coding theory has always been the construction of algebraic algorithms, that are capable of decoding all cyclic codes up to their actual minimum distance. Full error-correcting capabilities of the codes can only be achieved when such algorithms are available. For many years, algebraic decoding of cyclic codes has been constrained by the lower bound on the minimum distance of the codes. For example, the commonly used Berlekamp-Massey algorithm is known to be restricted within the BCH bound when it is used to decode all cyclic codes. Such restrictions can be traced to the fact that the algorithm requires syndromes to be contiguous in the Newton's identities.

ABSTRACT. We present a survey of recent work of the authors in which sequences of quasirandom points are constructed by new methods based on global function fields. These methods yield significant improvements on all earlier constructions. The most powerful of these methods employ global function fields with many rational places, or equivalently algebraic curves over finite fields with many rational points. With the help of class field theory for global function fields, it can be shown that our constructions are best possible in the sense of the order of magnitude of quality parameters. The paper contains also a new construction of sequences of quasirandom points and new facts about the earlier constructions designed by the authors.

Introduction

The motivation for the work that we want to present here stems from the theory of uniform distribution of sequences in number theory and from quasi-Monte Carlo methods in numerical analysis. A key problem in these areas is how to distribute points as uniformly as possible over an s-dimensional unit cube Is = [0, 1]s, s ≥ 1. A precise formulation of this problem will be given below. The essence of our work is that methods based on global function fields (or, equivalently, on algebraic curves over finite fields) yield excellent constructions of (finite) point sets and (infinite) sequences with strong uniformity properties. In fact, these methods are so powerful that they lead to constructions which are, in a sense to be explained later, best possible.

Abstract – Recently, a new direction in coding theory has been to apply the Gray map to codes that are linear over Z4 to obtain binary nonlinear codes better than comparable binary linear codes. The distance properties of these codes as well as the correlation properties of sequences obtained from Z4-linear codes depend in many cases on exponential sums over Galois rings. We present a survey of recent results on exponential sums over Galois rings and their applications to coding theory and sequence designs.

Keywords – Coding theory, cyclic codes, sequences, exponential sums, Galois rings, Z4-linear codes.

Introduction

In an important paper, Hammons et. al. show how to construct well known binary nonlinear codes like Kerdock codes and Delsarte-Goethals codes by applying the Gray map to linear codes over Z4. Further, they explain an old open problem in coding theory that the weight enumerators of the nonlinear Kerdock codes and Preparata codes satisfy the MacWilliams identities. Nechaev has shown that the Kerdock code punctured in two coordinates, is equivalent to a cyclic (but still nonlinear) code. The coordinate permutation that yields the binary cyclic code is identified by making a connection between the Kerdock code and a Z4-linear code. These discoveries lead to a strong interest in Z4-linear codes, and recently several other binary nonlinear codes which are better than comparable binary linear codes have been found using the Gray map on Z4-linear codes.

Many of the new codes are constructed from extended cyclic codes over Z4.

When can we embed one shift of finite type into another? When can we factor one shift of finite type onto another? The main results in this chapter, the Embedding Theorem and the Lower Entropy Factor Theorem, tell us the answers when the shifts have different entropies. For each theorem there is a simple necessary condition on periodic points, and this condition turns out to be sufficient as well. In addition, these periodic point conditions can be verified with relative ease.

We state and prove the Embedding Theorem in §10.1. The necessity of the periodic point condition here is easy. The sufficiency makes use of the fundamental idea of a marker set to construct sliding block codes. In §10.2 we prove the Masking Lemma, which shows how to represent embeddings in a very concrete form; we will use this in Chapter 11 to prove a striking application of symbolic dynamics to linear algebra. §10.3 contains the statement and proof of the Lower Entropy Factor Theorem, which is in a sense “dual” to the Embedding Theorem. The proof employs a marker construction similar to that of the Embedding Theorem. One consequence is an unequal entropy version of the Finite Equivalence Theorem.

The Embedding Theorem

Suppose that X and Y are irreducible shifts of finite type. When is there an embedding from X into Y? If the embedding is also onto, then X and Y are conjugate.

Invariants such as entropy, zeta function, and the dimension pair play an important role in studying shifts of finite type and sofic shifts. What values can these invariants take? Which numbers are entropies, which functions are zeta functions, which pairs are dimension pairs? Answers to these kinds of questions are called realization theorems.

In §11.1 we completely answer the entropy question. There is a simple algebraic description of the possible entropies of shifts of finite type and of sofic shifts. This amounts to characterizing the spectral radii of nonnegative integral matrices.

We focus on zeta functions in §11.2. Theorem 6.4.6 (see also Corollary 6.4.7) shows that the zeta function of an edge shift contains the same information as the nonzero spectrum of the adjacency matrix. Thus characterizing zeta functions of shifts of finite type is the same as characterizing the nonzero spectra of nonnegative integral matrices. We state an important partial result due to Boyle and Handelman [BoyH1].

The proof of this result is too complicated to include here, but we illustrate some of the main ideas involved by treating some special cases such as when all eigenvalues are integers. A remarkable feature of this work is that a significant theorem in linear algebra is proved by using important tools from symbolic dynamics: the Embedding Theorem and the Masking Lemma from Chapter 10. At the end of §11.2, we state a complete characterization of zeta functions of mixing sofic shifts [BoyH1].

In §2.5 we saw why it is useful to transform arbitrary binary sequences into sequences that obey certain constraints. In particular, we used Modified Frequency Modulation to code binary sequences into sequences from the (1,3) run-length limited shift. This gave a more efficient way to store binary data so that it is not subject to clock drift or intersymbol interference.

Different situations in data storage and transmission require different sets of constraints. Thus our general problem is to find ways to transform or encode sequences from the full n-shift into sequences from a preassigned sofic shift X. In this chapter we will describe one encoding method called a finite-state code. The main result, the Finite-State Coding Theorem of §5.2, says that we can solve our coding problem with a finite-state code precisely when h(X) ≥ log n. Roughly speaking, this condition simply requires that X should have enough “information capacity” to encode the full n-shift.

We will begin by introducing in §5.1 two special kinds of labelings needed for finite-state codes. Next, §5.2 is devoted to the statement and consequences of the Finite-State Coding Theorem. Crucial to the proof is the notion of an approximate eigenvector, which we discuss in §5.3. The proof itself occupies §5.4, where an approximate eigenvector is used to guide a sequence of state splittings that converts a presentation of X into one with out-degree at least n at every state.

Entropy measures the complexity of mappings. For shifts, it also measures their “information capacity,” or ability to transmit messages. The entropy of a shift is an important number, for it is invariant under conjugacy, can be computed for a wide class of shifts, and behaves well under standard operations like factor codes and products. In this chapter we first introduce entropy and develop its basic properties. In order to compute entropy for irreducible shifts of finite type and sofic shifts in §4.3, we describe the Perron–Frobenius theory of nonnegative matrices in §4.2. In §4.4 we show how general shifts of finite type can be decomposed into irreducible pieces and compute entropy for general shifts of finite type and sofic shifts. In §4.5 we describe the structure of the irreducible pieces in terms of cyclically moving states.

Definition and Basic Properties

Before we get under way, we review some terminology and notation from linear algebra.

Recall that the characteristic polynomial of a matrix A is defined to be χA(t) = det(tId – A), where Id is the identity matrix. The eigenvalues of A are the roots of χA(t). An eigenvector of A corresponding to eigenvalue λ is a vector v, not identically 0, such that Av = λv.

We say that a (possibly rectangular) matrix A is (strictly) positive if each of its entries is positive. In this case we write A > 0.