2026 Spring Semester
| When: | Wednesday, 14:30–16:30 |
| Where: | Taub 4 |
| Instructor: | Ronny Roth, Taub Building 637, ronny(at)cs.technion.ac.il |
| Teaching assistant: | Avital Boruchovsky |
| (There is no frontal recitation class in this course) | |
| WebCourse site: | http://webcourse.cs.technion.ac.il/02360520/ |
Scope
The course will concentrate on the theory and application of coding methods used in common storage devices, such as disks and optical devices (CD’s, DVD’s, and Blu-ray discs), as well as in bar codes (QR code, PDF417). 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 (00440252).
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
- B.H. Marcus, R.M. Roth, P.H. Siegel,
An Introduction to Coding for Constrained Systems.
Lecture notes that serve as the course textbook.
Available online. - D. Lind, B.H. Marcus,
An Introduction to Symbolic Dynamics and Coding,
Second Edition, Cambridge University Press, Cambridge, 2021. - K.A. Schouhamer Immink,
Codes for Mass Data Storage Systems,
Second Edition, Shannon Foundation Publishers, The Netherlands, 2004.
Available online. - K.C. Pohlmann,
The Compact Disc Handbook,
Second Edition, A-R Editions, Madison, Wisconsin, 1992.
Lecture notes
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 take place during the semester (namely, before the examination period; the exact date will be scheduled at the beginning of the semester). MOED B, if any, will be in the form of a class exam.