Partially supported by the National Security Agency

August 2-13, 1999

Organizers:

G. David Forney, Jr.
Massachusetts Institute of Technology
LUSE27@email.mot.com
forney@lids.mit.edu

Brian Marcus
IBM Almaden Research Center
marcus@almaden.ibm.com

Joachim Rosenthal
University of Notre Dame
rosen@nd.edu

Alexander Vardy
University of California, San Diego
vardy@ece.ucsd.edu

Note: The registration for this summer workshop has been closed due to an overwhelming response.

The invention of turbo codes and other capacity-approaching codes has led to an exciting cross-fertilization of ideas between researchers from different backgrounds.

The aim of the workshop is to bring together mathematicians, computer scientists, and electrical engineers in the area of coding theory, systems theory and symbolic dynamics so that the techniques from one area can be applied to problems in the other area. The two weeks of the workshop will be subdivided into two main focus areas:

  Week 1:
Codes on Graphs and Iterative Decoding
Week 2:
Connections Among Coding Theory, System Theory and Symbolic Dynamics  

Week 1

CODES ON GRAPHS AND ITERATIVE DECODING

Belief propagation in Bayesian networks has been extensively studied in artificial intelligence since the work of Pearl a decade ago, and turbo codes have recently become a subject of much research in coding theory. In the past year or two it has been recognized that the iterative decoding algorithm used for turbo codes and other capacity-approaching schemes are instances of belief propagation. This has led to an explosion of work devoted to understanding and exploiting this connection. A related problem is that of representing a given code by a graph, such as a Bayesian network. A central impetus of much of this work is to understand why iterative algorithms work so well empirically on graphs with cycles, where practically no theoretical results are known. Experts in the dynamics of algorithms have also begun to be drawn into this work. The major focus of week 1 of the IMA workshop will be to bring together researchers in these various fields to better understand these emerging connections. This will be a natural follow-on to a special session on this subject at the upcoming 1998 MTNS conference (Mathematical Theory of Networks and Systems, among the most mathematical of the systems theory conferences).

Topics for week 1 include: Codes defined on graphs, iterative decoding algorithms, factor graphs, turbo codes, connections with Bayesian networks.

 

Week 2

CONNECTIONS AMONG CODING THEORY, SYSTEM THEORY AND SYMBOLIC DYNAMICS

Coding Theory, System Theory and Symbolic Dynamics have much in common as evidenced by the following list of research topics that play a prominent role in each:

1. Construction of various types of finite- and finite-dimensional state representations of sequence spaces.
2. Investigation of fundamental structural properties of sequence spaces, such as observability and controllability.
3. Construction of input/output systems, i.e. mappings (or encoders) between sequence spaces.
4. Understanding the special role that algebraic structure (in particular, linearity and duality) plays in 1,2 and 3.

Yet these subjects have developed somewhat independently, and each has its own language and points of view. Until recently there has been very little communication among researchers in these subjects. A main purpose of week 2 of the IMA workshop is to further the communication among researchers and stimulate connections among these subjects. Week 2 will aim to continue a successful series of interdisciplinary meetings that has included an IEEE Information Theory Workshop on Coding, Systems and Symbolic Dynamics in 1993 (Mansfield, MA), a special invited session at the IEEE Conference on Decision and Control in 1995 (New Orleans), and two special sessions at the MTNS in 1998 (Padova).

Topics for week 2 include: Behavioral system theory, input/output mappings between spaces of sequences, state space representations, group codes, trellis codes, multi-dimensional systems and codes.

The organizers plan a number of invited tutorial lectures specifically for interspecialty communication. Leading workers in each field will also be invited to present surveys of current research, with less emphasis on solved problems than on open ones. Finally, there will be both invited and contributed papers presenting recent research results.

We expect the attendees to represent electrical engineering, mathematics and computer science departments in both academia and industry. As coding theory is the glue that holds the two weeks together, we expect that it will mostly be a subset of the coding theory participants who will attend both weeks.

WORKSHOP SCHEDULE

Week 1: August 2-6, 1999	Monday	Tuesday	Wednesday	Thursday	Friday
Week 2: August 9-13, 1999	Monday	Tuesday	Wednesday	Thursday	Friday

All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.

WEEK 1: CODES ON GRAPHS AND ITERATIVE DECODING August 2-6, 1999
SCHEDULE for MONDAY, AUGUST 2
HISTORY AND TUTORIALS Day G. David Forney, Jr. (chair)
8:30 am	Registration and Coffee	Reception Room EE/CS 3-176
9:10 am	Willard Miller, Fred Dulles, and G. David Forney	Introduction and Welcome
9:30 - 10:30 am	R. Michael Tanner University of California-Santa Cruz	Error-Correcting Codes and Graph-based Algorithms: Origins, Successes, the Current Quests
10:30 am	Coffee Break	Reception Room EE/CS 3-176
11:00 am - 12:00 pm	Stephen B. Wicker Cornell University	Markov Chains, Error Control, and the Advent of Turbo Coding
12:00 pm	Lunch
2:00-3:00 pm	Frank R. Kschischang University of Toronto	Factor Graphs and the Sum-Product Algorithm
4:00 pm	IMA Tea	IMA East, 400 Lind Hall A variety of appetizers and beverages will be served.
SCHEDULE for TUESDAY, AUGUST 3
LOW DENSITY PARITY CHECK CODES DAY R. Michael Tanner (chair)
9:15 am	Coffee	Reception Room EE/CS 3-176
9:30-10:30 am	David J.C. MacKay Cambridge University	Sparse Graph Codes
10:30 am	Coffee Break	Reception Room EE/CS 3-176
11:00 am - 12:00 pm	Robert J. McEliece California Institute of Technology	Some Simple Codes that Are Good in Both Theory and Practice
12:00 pm	Lunch
2:00 - 3:00 pm	Thomas J. Richardson (Lucent Bell Labs) Ruediger Urbanke (Lucent Bell Labs)	Analysis and Design of Iterative Decoding Systems
3:00 pm	Coffee Break	Reception Room EE/CS 3-176
Contributed Talks and Informal Discussions
3:30 pm	Amin Shokrollahi Bell Labs	Capacity Achieving Low-density Erasure Codes
4:00 pm	Gilles Zemor ENST, Paris	Iterative Decoding of Cycle Codes of Graphs
4:30 pm	Dakshi Agrawal University of Illinois-Urbana Champaign	On the Phase Trajectories of the Turbo Decoding Algorithm
SCHEDULE for WEDNESDAY, AUGUST 4
INFERENCE DAY Brendan J. Frey (chair)
9:15 am	Coffee	Reception Room EE/CS 3-176
9:30 - 10:30 am	Tommi Jaakkola Massachusetts Institute of Technology	Variational Methods for Inference
10:30 am	Coffee Break	Reception Room EE/CS 3-176
11:00 am - 12:00 pm	Radford M. Neal University of Toronto	Sparse Matrix Methods and Probabilistic Inference Algorithms
12:00 pm	Lunch
2:00 - 3:00 pm	Brendan J. Frey University of Waterloo Yair Weiss University of California at Berkeley	The Sum-Product Algorithm in Gaussian Networks with Cycles
3:00 am	Coffee Break	Reception Room EE/CS 3-176
Contributed Talks and Informal Discussions
3:30 pm	John B. Anderson University of Lund	Properties of the Tailbiting BCJR Decoder
4:00 pm	Amir Banihashemi Carleton University	Tanner Graphs for Group Block Codes and Lattices: Construction and Complexity
4:30 pm	Heeralal Janwa and Oscar Moreno University of Puerto Rico	New Constructions of Ramanujan Graphs and Good Expander Graphs from Codes, Exponential Sums and Sequences
SCHEDULE for THURSDAY, AUGUST 5
Robert J. McEliece (chair)
9:15 am	Coffee	Reception Room EE/CS 3-176
9:30 - 10:30 am	Randall E. Bryant Carnegie Mellon University	Symbolic Boolean Manipulation with Ordered Binary Decision Diagrams
10:30 am	Coffee Break	Reception Room EE/CS 3-176
11:00 am - 12:00 pm	John Lafferty Carnegie Mellon University	Trellises, Decision Diagrams, and Factor Graphs
12:00 pm	Lunch
2:00 - 3:00 pm	James L. Massey ETH Zurich and Lund University	Linear Systems over Fields and Rings, Linear Complexity, and Fourier Transforms
3:00 am	Coffee Break	Reception Room EE/CS 3-176
6:00 pm	Workshop Dinner	Bona Vietnamese Restaurant Located near the IMA and the Day's Inn at 802 Washington Avenue, the south side of Washington very near the intersection of Washington and Oak St. Phone: 612-331-5011
SCHEDULE for FRIDAY, AUGUST 6
CODING THEORY DAY Alexander Vardy (chair)
8:45 am	Coffee	Reception Room EE/CS 3-176
9:00 - 10:00 am	G. David Forney, Jr. Massachusetts Institute of Technology	Codes and Systems on Graphs: Generalized State Realizations
10:00 am	Coffee Break	Reception Room EE/CS 3-176
10:15 - 11:15 am	Ralf Koetter University of Illinois at Urbana-Champaign	Factor Graphs, Trellis Formations, and Generalized State Realizations
11:15 am	Coffee Break	Reception Room EE/CS 3-176
11:30 am	Hans-Andrea Loeliger Endora Tech AG, Switzerland	Decoding and Equalization: Iterative Algorithms and Analog Networks

Week 1: August 2-6, 1999	Monday	Tuesday	Wednesday	Thursday	Friday
Week 2: August 9-13, 1999	Monday	Tuesday	Wednesday	Thursday	Friday

All talks are in Lecture Hall EE/CS 3-180 unless otherwise noted.

WEEK 2: CONNECTIONS AMONG CODING THEORY, SYSTEM THEORY AND SYMBOLIC DYNAMICS August 9-13, 1999
SCHEDULE for MONDAY, AUGUST 9
8:30 am	Registration and Coffee	Reception Room EE/CS 3-176
9:10 am	Willard Miller, Fred Dulles, Joachim Rosenthal, and Brian Marcus	Introduction and Welcome
Automata and Systems Jorn Justesen (Chair)
9:30 am	Roger W. Brockett Harvard University	Dynamical Systems and their Associated Automata
10:30 am	Coffee Break	Reception Room EE/CS 3-176
11:00 am - 12:00 pm	Dominique Perrin Université de Marne-la-Vallée	Symbolic Dynamics and Automata
Algebra and Geometry Applied to Systems Ethan Coven (Chair)
1:30 pm	Paul A. Fuhrmann Ben Gurion University	A Polynomial Module Approach to Linear Systems Theory
2:30 pm	Clyde Martin Texas Tech University	Linear Systems as Vector Bundles on Spheres
3:30 pm	Coffee Break	Reception Room EE/CS 3-176
4:00 pm	M.S. Ravi Eastern Carolina University	An Algebraic Geometric Point of View to Linear Systems Theory
5:00 pm	IMA Tea	IMA East, 400 Lind Hall A variety of appetizers and beverages will be served.
SCHEDULE for TUESDAY, AUGUST 10
8:45 am	Coffee	Reception Room EE/CS 3-176
Convolutional Codes Karl Petersen (Chair)
9:00 am	Rolf Johannesson University of Lund	Woven Convolutional Codes: Encoder Properties and Error Exponents
10:00 am	Roxana Smarandache University of Notre Dame	Construction of Convolutional Codes with Large Free Distance
11:00 am	Coffee Break	Reception Room EE/CS 3-176
11:30 am	Fabio Fagnani Politecnico di Torino Joint talk with Sandro Zampieri Universita di Padova	On Convolutional Codes over Rings
Contributed Talks Joachim Rosenthal (Chair) All talks will be 25 minutes long, including questions.
2:00 pm	Thomas Mittelholzer IBM Zurich Research Laboratory	Duals over Artinian Rings and the MacWilliams Identity
2:30 pm	Sergio R. Lopez-Permouth Ohio University	Finite Fields, Permutations and Trellis
3:00 pm	Coffee Break	Reception Room EE/CS 3-176
3:30 pm	Danrun Huang St. Cloud State	Period Three, Chaos, and the Golden Mean Shift
4:00 pm	Dharmendra S. Modha IBM Almaden Research Center	Art of Constructing Low-complexity Encoders/Decoders for Constrained Block Codes
4:30 pm	Natasha Jonoska University of South Florida	On Encoding in DNA Words
SCHEDULE for WEDNESDAY, AUGUST 11
8:45 am	Coffee	Reception Room EE/CS 3-176
Multidimensional Systems Jon Hall (Chair)
9:00 am	Klaus Schmidt University of Vienna	Multi-dimensional Symbolic Dynamical Systems
10:00 am	Paul H. Siegel University of California-San Diego	Capacity of Constrained Systems in One and Two Dimensions
11:00 am	Coffee Break	Reception Room EE/CS 3-176
11:30 am	Paul A. Weiner Saint Mary's University of Minnesota	Multidimensional Convolutional Codes
Systems Theory Roy Adler (Chair)
2:00 pm	Jan C. Willems University of Groningen	Systems, States and their Representations
3:00 pm	Coffee Break	Reception Room EE/CS 3-176
3:30 pm	Sanjoy Mitter MIT	Path Space View of Probabilistic Systems
SCHEDULE for THURSDAY, AUGUST 12
8:45 am	Coffee	Reception Room EE/CS 3-176
Symbolic Dynamics and Applications Uwe Helmke (Chair)
9:00 am	M. Michael Boyle University of Maryland	Applications of Symbolic Dynamics to the Structure Theory of Nonnegative Matrices
10:00 am	Natasha Jonoska University of South Florida	Multiplicities of SFT Covers
11:30 am	Selim Tuncel University of Washington	Codings of Markov Chains and Weighted Graphs
Contributed Talks Brian Marcus (Chair)
2:00 pm	Marie-Pierre Béal Université de Marne-la-Vallée	A Finite State Version of the Kraft-McMillan Theorem
2:30 pm	Olivier Carton Université de Marne-la-Vallée	Asynchronous Sliding Block Maps
3:00 pm	Coffee Break	Reception Room EE/CS 3-176
3:30 pm	Christiane Frougny LIAFA	Deterministic Synchronization of Bounded Delay 2-tape Finite Automata
4:00-4:30 pm	Michael E. O'Sullivan University College Cork	The Key Equation for One-point Codes
4:30 - 5:00 pm	Fernando Guzmán Binghamton University	Ambiguity in Codes
6:00 pm	Workshop Dinner	Campus club Located on the 4th floor of Coffman Student Union and serves a wide-ranging buffet. Coffman Union is located on the opposite side of Washington Avenue from the IMA and slightly to the west.
SCHEDULE for FRIDAY, AUGUST 13
8:45 am	Coffee	Reception Room EE/CS 3-176
Decoding and Interpolation Zhe-Xian Wan (Chair)
9:00 am	Margreet Kuijper University of Melbourne	Algorithms for Decoding and Interpolation
10:00 am	Patrick Fitzpatrick National University of Ireland, Cork	Realization and Interpolation via Gröbner Bases
11:00 am	Coffee Break	Reception Room EE/CS 3-176
11:30 am	Brian M. Allen University of Notre Dame	Linear Systems Decoding of Convolutional Codes
Informal Contributed Talks Lind Hall 409 with an option to switch to Lecture Hall EE/CS 3-180 contingent on the participants size
2:00 pm	Karl Petersen University of North Carolina	Good Measures for Bad Codes between SFT's
2:30 pm	Ethan Coven Wesleyan University	The Symbolic Dynamics of Tiling the Integers
3:00 pm	Coffee Break	IMA East Lind Hall room 400
3:15 pm	Kimberly Johnson University of North Carolina	Automata, and Pumping Lemmas for Beta-shifts
3:45 pm	Paul Trow University of Memphis	Mappings between Group Shifts

Week 1: August 2-6, 1999	Monday	Tuesday	Wednesday	Thursday	Friday
Week 2: August 9-13, 1999	Monday	Tuesday	Wednesday	Thursday	Friday

Back to top of page