Codes, Systems, and Graphical Models

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. Front Matter....Pages i-xi Front Matter....Pages xiii-xiii An Introduction to the Analysis of Iterative Coding Systems....Pages 1-37 Connections Between Linear Systems and Convolutional Codes....Pages 39-66 Multi-Dimensional Symbolic Dynamical Systems....Pages 67-82 Front Matter....Pages N1-N1 Linear-Congruence Constructions of Low-Density Parity-Check Codes....Pages 83-100 On the Effective Weights of Pseudocodewords for Codes Defined on Graphs with Cycles....Pages 101-112 Evaluation of Gallager Codes for Short Block Length and High Rate Applications....Pages 113-130 Two Small Gallager Codes....Pages 131-133 Mildly Non-Linear Codes....Pages 135-151 Capacity-Achieving Sequences....Pages 153-166 Hypertrellis: A Generalization of Trellis and Factor Graph....Pages 167-194 Front Matter....Pages N3-N3 BSC Thresholds for Code Ensembles Based on “Typical Pairs” Decoding....Pages 195-210 Properties of the Tailbiting BCJR Decoder....Pages 211-238 Iterative Decoding of Tail-Biting Trellises and Connections with Symbolic Dynamics....Pages 239-264 Algorithms for Decoding and Interpolation....Pages 265-282 An Algebraic Description of Iterative Decoding Schemes....Pages 283-298 Recursive Construction of GrÖbner Bases for the Solution of Polynomial Congruences....Pages 299-309 On Iterative Decoding of Cycle Codes of Graphs....Pages 311-326 Front Matter....Pages N5-N5 Convolutional Codes Over Finite Abelian Groups: Some Basic Results....Pages 327-346 Symbolic Dynamics and Convolutional Codes....Pages 347-360 Linear Codes and Their Duals Over Artinian Rings....Pages 361-379 Front Matter....Pages N5-N5 Unit Memory Convolutional Codes with Maximum Distance....Pages 381-396 Basic Properties of Multidimensional Convolutional Codes....Pages 397-414 Front Matter....Pages N7-N7 Length Distributions and Regular Sequences....Pages 415-437 Handelman’s Theorem on Polynomials with Positive Multiples....Pages 439-445 Topological Dynamics of Cellular Automata....Pages 447-485 A Spanning Tree Invariant for Markov Shifts....Pages 487-497 Back Matter....Pages 499-513

Coding theory, system theory, and symbolic dynamics have much in common. 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.