2023 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/236520/ |
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), 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 (044252 or 044145/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
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.