Coding for Storage Systems

Politecnico di Torino
May 2 - 26, 2006

When:	Tuesday, Wednesday, Thursday 10.30 - 12.30
Where:	Room Buzano - Department of Mathematics
Instructor:	Paul H. Siegel
	Professor, Electrical and Computer Engineering Director, Center for Magnetic Recording Research University of California, San Diego La Jolla, CA 92093-0401

Course Description

This course provides a thorough introduction to the theory and
application of constrained coding, widely used in digital data
storage devices, such as magnetic disk drives found in desktop
computers, portable computers, and consumer electronics devices;
magnetic tape drives used in data backup and archiving systems;
and optical disk drives that record and play CD’s and DVD’s.

Additional topics to be covered (time-permitting) include the
information-theoretic analysis of noisy digital recording
channels and the design of concatenated coding schemes that
can, in principle, approach the channel capacity. The course
will conclude with an overview of recent results on coding for
page-oriented storage devices, such as two-dimensional optical
storage and holographic recording.

Topics covered in this course include:

Recording channel models and coding requirements
Representation and information-theoretic properties of constrained sequences
Design of encoders and decoders for constrained systems
Integration of constrained codes and error control codes

If time permits, the following topics will be introduced:

Information-theoretic analysis of noisy intersymbol-interference channels
Capacity-approaching concatenated coding schemes
Coding for page-oriented (two-dimensional) recording channels

Prerequisites

The course requires familiarity with basic concepts in linear algebra, probability theory, and linear systems analysis.
Knowledge of elementary information theory, communication theory, and error-correction coding will be helpful, but is not required.

Syllabus (topics selected from the following list)

Introduction to constrained systems
- Runlength-limited systems and charge-constrained systems
- Graph presentations
- Irreducible systems
- Finite-type and almost-finite-type systems
- Capacity of constrained systems
Theory of non-negative matrices
- Irreducible and primitive matrices
- Perron-Frobenius Theorem
- Shannon capacity formula
- Connections to Markov chain theory
Finite-state encoders for constrained systems
- Properties of encoder graphs
- Approximate eigenvectors and Franaszek algorithm
- The state-splitting algorithm
- Sliding-block decoders
Other constructions and complexity bounds
- Constructions for runlength-limited codes
- Codes with unconstrained positions
- Encoder / decoder implementation bounds
Spectral-null constraints
- Spectral analysis of constrained systems and codes
- Codes with simple spectral nulls
- Codes with multiple spectral nulls
Combined constrained and error control coding
- Distance properties of constrained systems
- Partial response channels
- Error-event characterization
- Distance-enhancing constraints
  (RLL, matched-spectral-null, MTR, time-varying MTR)
- Constrained parity codes
Capacity of partial response channels
- Information rates of noisy intersymbol-interference (ISI) channels
- Simulation-based estimation of capacity
- Capacity-approaching coding for partial response channels
Coding for page-oriented storage devices
- Capacity of two-dimensional constraints
- Bit-stuffing bounds
- Construction of block and finite-state codes
- Information rates and coding for noisy two-dimensional ISI channels

Primary course text

B.H. Marcus, R.M. Roth, and P.H. Siegel, An Introduction to Coding for Constrained Systems
(draft version downloadable) .

This is a revised and expanded version of :
B.H. Marcus, R. M. Roth, and P.H. Siegel,"Constrained systems and coding for recording channels,"
Chapter 20 in Handbook of Coding Theory, V. Pless and W.C. Huffman (editors),
Elsevier Press, Amsterdam, 1998, pp. 1635-1764.

Other useful references

K.A. Schouhamer Immink, Codes for Mass Data Storage Systems, Second Edition,
Shannon Foundation Publishers, The Netherlands, 2004.
(See also the earlier edition, Coding Techniques for Digital Recorders,
Prentice Hall, New York, 1991.)
D. Lind, B.H. Marcus, An Introduction to Symbolic Dynamics and Coding,
Cambridge University Press, Cambridge, 1995.
K.C. Pohlmann, The Compact Disc Handbook,Second Edition,
A-R Editions, Madison, Wisconsin, 1992.

Home Page

Last Updated: 9/18/06