Skip to main content
main-content

Über dieses Buch

Coding theory, system theory, and symbolic dynamics have much in common. Among the central themes in each of these subjects are the construction of state space representations, understanding of fundamental structural properties of sequence spaces, construction of input/output systems, and understanding the special role played by algebraic structure. A major new theme in this area of research is that of codes and systems based on graphical models.
This volume contains survey and research articles from leading researchers at the interface of these subjects.

Inhaltsverzeichnis

Frontmatter

Overviews

Frontmatter

An Introduction to the Analysis of Iterative Coding Systems

Abstract
This paper is a tutorial on recent advances in the analysis of iterative coding systems as exemplified by low-density parity-check codes and turbo codes.
The theory described herein is composed of various pieces. The main components are concentration of system performance over the ensemble of codes and inputs, the existence of threshold phenomena in decoding performance, and the computational and/or analytical determination of thresholds and its implications in system design.
We present and motivate the fundamental ideas and indicate some technical aspects but proofs and many technical details have been omitted in deference to accessibility to the concepts. Low-density parity-check codes and parallel concatenated codes serve as contrasting examples and as vehicles for the development.
Tom Richardson, Rüdiger Urbanke

Connections Between Linear Systems and Convolutional Codes

Abstract
The article reviews different definitions for a convolutional code which can be found in the literature. The algebraic differences between the definitions are worked out in detail. It is shown that bi-infinite support systems are dual to finite-support systems under Pontryagin duality. In this duality the dual of a controllable system is observable and vice versa. Uncontrollability can occur only if there are bi-infinite support trajectories in the behavior, so finite and half-infinite-support systems must be controllable. Unobservability can occur only if there are finite support trajectories in the behavior, so bi-infinite and half-infinite-support systems must be observable. It is shown that the different definitions for convolutional codes are equivalent if one restricts attention to controllable and observable codes.
Joachim Rosenthal

Multi-Dimensional Symbolic Dynamical Systems

Abstract
The purpose of this note is to point out some of the phenomena which arise in the transition from classical shifts of finite type XA to multi-dimensional shifts of finite type XA d, d ≥ 2, where A is a finite alphabet. We discuss rigidity properties of certain multi-dimensional shifts, such as the appearance of an unexpected intrinsic algebraic structure or the scarcity of isomorphisms and invariant measures. The final section concentrates on group shifts with finite or uncountable alphabets, and with the symbolic representation of such shifts in the latter case.
Klaus Schmidt

Codes on Graphs

Frontmatter

Linear-Congruence Constructions of Low-Density Parity-Check Codes

Abstract
Low-Density Parity-Check codes (LDPCC) with Iterative Belief Propagation (Message Passing) decoding are attractive alternatives to Turbo codes. LDPCC previously discussed in the literature have involved matrices constructed using random techniques. In this paper, we discuss construction techniques for LDPCC involving multiple permutation matrices, each specified by a linear congruence. Construction options depend on the size of the parity-check matrix and the rate of the code. We relate desirable properties of the code to the parameters defining the linear congruences specifying the permutation matrices used to construct the code. For example, codes with few or no 4-cycles can be readily constructed. We summarize the construction options and describe selection processes for the parameters of the congruences. We then provide performance results for regular parity-check matrices constructed by random and the linear-congruence techniques for rate 1/2 transmit block-size 980 and rate 4/7 transmit block-size 847 codes. We introduce a symmetric channel model for decoding with the iterative belief propagation algorithm and describe its use as a heuristic for deciding whether a code is likely better or worse than most codes of the given rate and block size.
J. Bond, S. Hui, H. Schmidt

On the Effective Weights of Pseudocodewords for Codes Defined on Graphs with Cycles

Abstract
The behavior of an iterative decoding algorithm for a code defined on a graph with cycles and a given decoding schedule is characterized by a cycle-free computation tree. The pseudocodewords of such a tree are the words that satisfy all tree constraintsj pseudocodewords govern decoding performance. Wiberg [12] determined the effective weight of pseudocodewords for binary codewords on an AWGN channel. This paper extends Wiberg’s formula for AWGN channels to nonbinary codes, develops similar results for BSC and BEC channels, and gives upper and lower bounds on the effective weight. The 16-state tail-biting trellis of the Golay code [2] is used for exampIes. Although in this case no pseudocodeword is found with effective weight less than the minimum Hamming weight of the Golay code on an AWGN channel, it is shown by example that the minimum effective pseudocodeword weight can be less than the minimum codeword weight.
G. David Forney, Ralf Koetter, Frank R. Kschischang, Alex Reznik

Evaluation of Gallager Codes for Short Block Length and High Rate Applications

Abstract
Gallager codes with large block length and low rate (e.g., N ≃ 10,000–40,000, R ≃ 0.25–0.5) have been shown to have record-breaking performance for low signal-to-noise applications. In this paper we study Gallager codes at the other end of the spectrum. We first explore the theoretical properties of binary Gallager codes with very high rates and observe that Gallager codes of any rate offer runlength-limiting properties at no additional cost.
We then report the empirical performance of high rate binary and non-binary Gallager codes on three channels: the binary input Gaussian channel, the binary symmetric channel, and the 16-ary symmetric channel.
We find that Gallager codes with rate R = 8/9 and block length N = 1998 bits outperform comparable BCH and Reed-Solomon codes (decoded by a hard input decoder) by more than a decibel on the Gaussian channel.
David J. C. MacKay, Matthew C. Davey

Two Small Gallager Codes

Abstract
We present a pair of Gallager codes with rate R = 1/3 and transmitted blocklength N = 1920 as candidates for the proposed international standard for cellular telephones.
David J. C. MacKay, Matthew C. Davey

Mildly Non-Linear Codes

Abstract
We consider codes coming from systems of sparse linear equations. (These low-density parity check codes are examples of what are called Gallager codes.) We suggest how non-linear equations very elose to the given linear equations might be used to improve decoding properties while retaining the same level of coding and decoding complexity.
Alan Parks

Capacity-Achieving Sequences

Abstract
A capacity-achieving sequence of degree distributions for the erasure channel is, roughly speaking, a sequence of degree distributions such that graphs sampled uniformly at random satisfying those degree constraints lead to codes that perform arbitrarily close to the capacity of the erasure channel when decoded with a simple erasure decoder described in the paper. We will prove a necessary property called flatness for a sequence of degree distributions to be capacity-achieving, and will comment on possible applications to the design of capacity-achieving sequences on other communication channels.
M. A. Shokrollahi

Hypertrellis: A Generalization of Trellis and Factor Graph

Abstract
Factor graphs have recently been introduced as an efficient graphical model for codes to study iterative decoding algorithms. However, it is well-known that a factor graph generalizes only the time axis of a trellis, but omits the state transition representation. In this paper, a new graphical model, called the hypertrellis, is proposed to overcome this insufficiency of factor graphs. A hypertrellis is in essence a weighted hypergraph generalization of a traditional trellis. Its time topology, which extends the time axis of a trellis, can take the form of any factor graph. A key to this extension is the interpretation of a factor graph as a factor hypergraph. This is facilitated by introducing a “starfish” drawing representation for hypergraphs, which enhances the applicability of hypergraph models by enabling simpler drawing and easier visualization, relative to the traditional representation. The maximum likelihood decoding (MLD) problem is then formulated as a shortest hyperpath search on a hypertrellis. For hypertrellises with an acyclic time topology, a hyperpath-oriented MLD algorithm, called the one-way algorithm, is introduced. The one-way algorithm, as a hypertrellis generalization of the celebrated Viterbi algorithm, provides insights into efficient management of the surviving hyperpath history and various practical hyperpath-oriented simplifications. It is shown that as a MLD algorithm, the one-way algorithm has a lower minimal decoding delay. The computational complexity and the amount of storage needed are also bett er than with the well-known min-sum algorithm. Some connections between the hypertrellis and another recently proposed bipartite graph model, called the trellis formation, are also discussed.
Wai Ho Mow

Decoding Techniques

Frontmatter

BSC Thresholds for Code Ensembles Based on “Typical Pairs” Decoding

Abstract
In this paper, we develop a method for closely estimating noise threshold values for ensembles of binary linear codes on the binary symmetric channel. Our method, based on the “typical pairs” decoding algorithm pioneered by Shannon, completely decouples the channel from the code ensemble. In this, it resembles the classical union bound, but unlike the union bound, our method is powerful enough to prove Shannon’s theorem for the ensemble of random linear codes. We apply our method to find numerical thresholds for the ensembles of low-density parity-check codes, and “repeat-accumulate” codes.
Srinivas Aji, Hui Jin, Aamod Khandekar, David J. C. MacKay, Robert J. Mceliece

Properties of the Tailbiting BCJR Decoder

Abstract
The tailbiting BCJR algorithm extends the maximum a posteriori (MAP) decoder of Bahl et al. to the case of tailbiting trellis codes. The algorithm consists of forward and backward recursions that start from the left and right principal eigenvectors of the product of the trellis gamma matrices. The result is a slightly sub-optimal symbol-by-symbol MAP decoder that performs much less computation than the true MAP decoder. The decoder has both iterative and non-iterative realizations. We formally justify the algorithm and develop its properties. Storage of the entire recursion outcome is not required and we relate the needed length to the encoder memory and the encoder decision depth parameter. By tests of actual decoders, the bit error rate of the algorithm is compared to that of true MAP, maximum likelihood, and circular Viterbi decoders. For a given encoder, the BER of these decoders depends on the ratio of the tailbiting circle size to the encoder memory. We argue that there exists a certain practical optimum ratio of circle size to memory, and at this ratio the BER of the tailbiting BCJR decoder is essentially that of the true MAP decoder.
John B. Anderson, Kemal E. Tepe

Iterative Decoding of Tail-Biting Trellises and Connections with Symbolic Dynamics

Abstract
The sum-product and min-sum algorithms are used to decode codes defined by trellises. In this paper, we discuss the behavior of these and related algorithms on tail-biting (TB) trellises.
The convergence of the sum-product algorithm on tail-biting trellises was analyzed recently by Anderson and Hladik [2] and was shown to give approximate a posteriori probabilities.
We introduce and analyze generating function versions of both algorithms, each involving a parameter x. This involves the minwps graph, a tool borrowed from the symbolic dynamics of Markov chains. We determine the limiting behavior as x → 0 of the result of the generating-function sum-product algorithm and show how this relates to maximum-likelihood sequences and the generating-function min-sum algorithm.
G. David Forney, Frank R. Kschischang, Brian Marcus, Selim Tuncel

Algorithms for Decoding and Interpolation

Abstract
In this paper we consider various algorithms for decoding BCH/RS/ Goppa codes, in particular the euclidean algorithm, the Beriekamp-Massey algorithm and the Welch-Beriekamp algorithm. We focus on relationships of these algorithms with interpolation methods in system theory. We note that the problem statements in the two areas can be different: from a system theoretic point of view, rational interpolating functions with common factors between numerator and denominator are undesirable whereas common factors can be required in a decoding context.
The behavioral approach was introduced by Jan C. Willems into system theory in the eighties. It proposes the family of trajectories of a system as its central focus. This makes the approach attractive for coding theorists (most naturally in the context of convolutional codes where the family of trajectories corresponds to the code). In this paper we focus on a connection between behavioral modeling and the decoding of BCH/RS/Goppa codes. In this context, the behavioral modeling approach is attractive because it naturally generates solutions with common factors.
We present slight modifications of both the Berlekamp-Massey and the Welch-Berlekamp algorithm and give a derivation in terms of behavioral modeling. In particular, we derive the latter algorithm directly from Reed & Solomon’s original approach. We demonstrate the similarity of the two algorithms and show that they are special instances of one general iterative behavioral modeling procedure.
Margreet Kuijper

An Algebraic Description of Iterative Decoding Schemes

Abstract
Several popular, suboptimal algorithms for bit decoding of binary block codes such as turbo decoding, threshold decoding, and message passing for LDPC, were developed almost as a common sense approach to decoding of some specially designed codes. After their introduction, these algorithms have been studied by mathematical tools pertinent more to computer science than the conventional algebraic coding theory. We give an algebraic description of the optimal and suboptimal bit decoders and of the optimal and suboptimal message passing. We explain exactly how suboptimal algorithms approximate the optimal, and show how good these approximations are in some special cases.
Elke Offer, Emina Soljanin

Recursive Construction of GrÖbner Bases for the Solution of Polynomial Congruences

Abstract
A number of questions in systems theory and coding theory can be formulated as the solution of a system of polynomial congruences in one or more variables. We present a new generalised algorithm, based on Gröbner basis techniques, that recursively solves a wide class of such problems.
Henry O’keeffe, Patrick Fitzpatrick

On Iterative Decoding of Cycle Codes of Graphs

Abstract
We analyze iterative decoding of cycle codes of graphs for the erasure channel and the binary symmetric channel. Cycle codes can achieve vanishing error-probability after decoding: furthermore, threshold probabilities can be computed exactly. We also prove that, for these codes, the asymptotical performance of iterative decoding and maximum-likelihood decoding coincide.
Gilles ZÉmor

Convolutional Codes and Codes Over Rings

Frontmatter

Convolutional Codes Over Finite Abelian Groups: Some Basic Results

Abstract
Abelian groups provide the most natural structure to represent codes over phase modulation signals. Convolutional codes over finite Abelian groups are introduced and the properties of linear encoders for this class of codes are analyzed. Through the structure theorem for finitely generated Abelian groups this analysis can be reduced to the study of of convolutional codes over the ring Zn. We can in this way introduce the concept of encoding group and to compare it with the more classical input group introduced in [6]. In the last part of the paper the state space realization of a convolutional code and of a convolutional encoder is investigated.
Fabio Fagnani, Sandro Zampieri

Symbolic Dynamics and Convolutional Codes

Abstract
Convolutional codes and their encoders are examined in a symbolic dynamics setting. Two previously unrelated areas of dynamics are used. The first is the Adler-Coppersmith-Hassner formulation of the finite memory channel coding problem. The second is the Kitchens-Schmidt use of algebraic duality to define and examine algebraic dynamical systems. Convolutional codes and their encoders are seen as lying in the intersection of these two areas. Codes, encoders, memory, distances and other invariants are examined in this framework.
Bruce Kitchens

Linear Codes and Their Duals Over Artinian Rings

Abstract
Linear codes over commutative artinian rings R are considered. For a linear functional-based definition of duality, it is shown that the class of length-n linear block codes over R should consist of projective submodules of the free module R n. For this class, the familiar duality properties from the field case can be generalized to the ring case. In particular, the MacWilliams identity is derived for linear codes over any finite commutative ring. Duals of convolutional codes are also considered, and it is shown that for convolutional codes over commutative artinian rings, the duality property holds for a code and its dual as well as for the local description of the code by its canonical trellis section and its dual trellis section.
Thomas Mittelholzer

Unit Memory Convolutional Codes with Maximum Distance

Abstract
Unit memory codes and in particular, partial unit memory codes are reviewed. Conditions for the optimality of partial unit memory codes with degree k − 1 are given, where optimal codes are the codes having the maximum free distance among all codes of the same parameters k, n and degree µ. A binary construction of unit memory codes with µ = k − 1 is discussed for the cases that satisfy the optimality conditions. This construction is generalized for codes over fields of characteristic p > 2.
Roxana Smarandache

Basic Properties of Multidimensional Convolutional Codes

Abstract
Let \(\mathbb{F} \) be a finite field, and let \(\mathcal{D} = \mathbb{F}\left[ {{z_1}, \ldots ,{z_m}} \right]\) be a polynomial ring in m indeterminates over \(\mathbb{F} \). In this paper, we define an m-dimensional convolutional code of length n to be a D-submodule, C, of the free module D n. Using this point of view, a multidimensional convolutional code may be regarded as the row space of a polynomial matrix (the number of columns gives the length of the code).
We will consider some of the algebraic properties of multidimensional convolutional codes, seeing that their structure is different from the structure of one-dimensional convolutional codes.
We will also look at distance properties of multidimensional convolutional codes. In this regard, we will apply some ideas regarding monomial orders to give a code construction with a lower distance bound; additionally, we will show that for dimension 2 or higher, arbitrarily large distance may be achieved by convolutional codes that are the row spaces of 1 × 1 polynomial matrices.
Paul Weiner

Symbolic Dynamics and Automata Theory

Frontmatter

Length Distributions and Regular Sequences

Abstract
This paper presents a survey on length distributions of regular languages. The accent is on problems in coding theory and the relation with symbolic dynamics.
Frédérique Bassino, Marie-Pierre Béal, Dominique Perrin

Handelman’s Theorem on Polynomials with Positive Multiples

Abstract
For a polynomial p in several variables and a face F of its Newton polytope, let PF denote the polynomial consisting of the terms of P that lie in F , with the coefficients given by p. Handelman’s theorem states that p has a polynomial multiple with positive coefficients if and only if no PF has a zero with strictly positive coordinates. We give a short and self-contained account of its proof.
Valerio De Angelis, Selim Tuncel

Topological Dynamics of Cellular Automata

Abstract
This is an overview of some classical and recent results in topological dynamics of cellular automata on the space of twosided symbolic sequences. The concepts studied include surjectivity, transitivity, equicontinuity, closingness, openness, expansivity, attractors and the shadowing property.
Petr Kůrka

A Spanning Tree Invariant for Markov Shifts

Abstract
We introduce a new type of invariant of block isomorphism for Markov shifts, defined by summing the weights of all spanning trees for a presentation of the Markov shift. We give two proofs of invariance. The first uses the Matrix-Tree Theorem to show that this invariant can be computed from a known invariant, the stochastic zeta function of the shift. The second uses directly the definition to show invariance under state splitting, from which all block isomorphisms can be built.
Douglas Lind, Selim Tuncel

Backmatter

Weitere Informationen