Coding for Storage Systems (236520)

2011 Spring Semester

When:	Monday, 14:30-16:30
Where:	Taub 3
Instructor:	Ronny Roth, Taub Building 637, ronny@cs.technion.ac.il
Teaching assistant:	Artyom Sharov, Taub Building 638, sharov@cs.technion.ac.il
	(There is no frontal recitation class in this course)
Web site:	http://www.cs.technion.ac.il/~ronny/constrained.html

Scope

The course will concentrate on the theory and application of coding methods used in common storage devices, such as disks, magnetic tapes, and optical devices (CD's, DVD's, and Blu-ray discs). A widely-used model for describing the read/write requirements of such storage devices is the so-called "constrained system." A constrained system is presented by a graph which is similar to a state diagram of a finite-state automaton (or a finite-state machine). The topics to be covered include the following:

Presentation and analysis of constrained systems
Construction methods of encoders for constrained systems
Bounds on the complexity of encoders for constrained systems
Decoding techniques for constrained systems
Combining constrained codes with error-correcting codes

Prerequisites

The course will be mainly of theoretical nature, and the following background is assumed: linear algebra (eigenvalues and eigenvectors), probability theory, and digital systems (044145 or 234145).

Topics

Introduction to constrained systems
- Runlength-limited systems and charge-constrained systems
- Deterministic and lossless presentations
- Irreducible systems
- Systems of finite memory
- Capacity of constrained systems
Perron-Frobenius Theory
- Irreducible and primitive matrices
- Perron-Frobenius Theorem
- Capacity in terms of Perron eigenvalue
Finite-state encoders for constrained systems
- Encoder graphs
- Anticipation
- Approximate eigenvectors
- The state-splitting algorithm
Selected topics from the following
- Markov chains
- Enumerative coding
- Variable-length encoders
- Bounds on the number of states in encoders
- Existence of good error-correcting constrained codes
- Two-dimensional constrained coding

Books and tutorials

D. Lind, B.H. Marcus, An Introduction to Symbolic Dynamics and Coding, Cambridge University Press, Cambridge, 1995.
B.H. Marcus, R.M. Roth, P.H. Siegel, Constrained Systems and Coding for Recording Channels, Second Edition, TR 0929, Computer Science Department, Technion, 1998.
(Also in Handbook of Coding Theory, V.S. Pless and W.C. Huffman (Editors), Elsevier, Amsterdam, 1998, pp. 1635-1764.)
K.C. Pohlmann, The Compact Disc Handbook, Second Edition, A-R Editions, Madison, Wisconsin, 1992.
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.)

Lecture notes

Bibliography

Home assignments

Home Assignment 1: Problems: 2.13, 2.21, 2.24, 3.1, 3.2. Due date: 11 April 2011.
Home Assignment 2: Problems: 3.10 (parts 1-3), 3.21, 3.22, 3.28. Due date: 02 May 2011.
Home Assignment 3: Problems: 3.30, 4.1, 4.2, 4.3. Due date: 23 May 2011.
Home Assignment 4: Problems: 5.8, 5.9, 5.13, 5.15. Due date: 06 June 2011.

Administration

There will be four home assignments which will constitute 20% of the final grade. A final exam, which will take the form of a home exam, will determine the remaining 80% of the final grade.
The home exam will start on Monday, 13 June 2011, at 16:30, right after the last lecture in the course. The questionnaires will be handed, in person, in Artyom's office (Taub 638). The exam will end on Thursday, 16 June 2011, at 16:30. The answer sheets should be handed in person to Artyom by that time.
A MOED B in this course will be held only upon request, and, if held, will take the form of a regular (class) exam. Undergraduate students who wish to take a MOED B in this course should notify Ronny or Artyom by e-mail no later than 26 August 2011.
Make-up lecture: There will be a make-up lecture on Wednesday, 27 April 2011, at 14:30-16:30, in Taub 201. This lecture will replace the one on 20 June 2011.

To the Computer Science Department home page