Paul H. Siegel

Distinguished Professor, Department of Electrical and Computer Engineering
Endowed Chair, Center for Memory and Recording Research

Phone:   (858) 534-6210
Fax:         (858) 534-8059
Email:     psiegel@ucsd.edu
Office:   CMRR Room 305
Mailing Address:
Center for Memory and Recording Research
9500 Gilman Drive, Mail Code 0401
University of California, San Diego
La Jolla, CA 92093-0401

• Publications
• Selected Presentations
• Course - Coding for Storage Systems

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

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)

1. 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
2. Theory of non-negative matrices
• Irreducible and primitive matrices
• Perron-Frobenius Theorem
• Shannon capacity formula
• Connections to Markov chain theory
3. Finite-state encoders for constrained systems
• Properties of encoder graphs
• Approximate eigenvectors and Franaszek algorithm
• The state-splitting algorithm
• Sliding-block decoders
4. Other constructions and complexity bounds
• Constructions for runlength-limited codes
• Codes with unconstrained positions
• Encoder/decoder implementation bounds
5. Spectral-null constraints
• Spectral analysis of constrained systems and codes
• Codes with simple spectral nulls
• Codes with multiple spectral nulls
6. 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
7. 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
8. 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.