CONTENTS

Foreword

Preface

PART 1 . OVERVIEWS

An introduction to the analysis of iterative coding
systems	1
 Tom Richardson and Rüdiger Urbanke

Connections between linear systems and convolutional codes
Joachim Rosenthal
Multi-dimensional symbolic dynamical systems	67
 Klaus Schmidt

PART 2. CODES ON GRAPHS

Linear-congruence constructions of low-density
parity-check codes		83
 J.	Bond, S. Hui, and H. Schmidt

On the effective weights of pseudocodewords for
codes defined on graphs with cycles	101
 G. David Forney, Jr., RaIf Koetter,
 Frank R. Kschischang, and Alex Reznik

Evaluation of Gallager codes for short block
length and high rate applications	113
 David J. C. MacKay and Matthew G. Davey
Two small Gallager codes	131
 David J. C. MacKay and Matthew C. Davey
Mildly non-linear codes	135
 Alan Parks
Capacity-achieving sequences	153
 M.A.
Hypertrellis:	A generalization of trellis and factor
graph	16
  Wai Ho Mow

PART 3: DECODING TECHNIQUES

BSC thresholds for code ensembles based on
“typical pairs” decoding	1
 Srinivas Aji, Hui Jin, Aamod Khandekar,
 David J. C. MacKay, and Robert J. McEliece
Properties of the tailbiting BCJR decoder	21
John B. Anderson and Kemal E. Tepe

Iterative decoding of tail-biting trellises and
connections with symbolic dynamics	2
 G. David Forney, Jr., Frank R. Kschischang,
 Brian Marcus, and Selim Tuncel
Algorithms for decoding and interpolation	2
 Margreet Kuijper

An algebraic description of iterative decoding schemes	2 Elke Offer and Emina Soljanin

Recursive construction of Gröbner bases for the
solution of polynomial congruences	2
 Henry 0 ‘Keeffe and Patrick Fitzpatrick
On iterative decoding of cycle codes of graphs	3
 Gilles Zémor

PART 4. CONVOLUTIONAL CODES AND CODES OVER RINGS

Convolutional codes over finite Abelian groups:
Some basic results	3
 Fabio Fagnani and Sandro Zampieri
Symbolic dynamics and convolutional codes	3
  Bruce Kitchens
Linear codes and their duals over artinian rings	3
  Thomas Mittelholzer
Unit memory convolutional codes with maximum
distance	381
 Roxana Smarandache

Basic properties of multidimensional convolutional codes
Paul Weiner

PART 5. SYMBOLIC DYNAMICS AND AUTOMATA THEORY
Length distributions and regular sequences	415
Frédérique Bassino, Marie-Pierre Béal,
and Dominique Perrin

Handelman’s theorem on polynomials with positive
multiples	439
 Valerio de Angelis and Selim Tuncel
Topological dynamics of cellular automata	447
 Petr Kurka
A spanning tree invariant for Markov shifts	487
 Douglas Lind and Selim Tuncel
List of workshop participants	499