Scope
The course will concentrate on the theory and application of coding methods used in common storage devices, such as magnetic disks, 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 (to be omitted in 2024)
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 (to be omitted in 2024)
- 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
Administration
- There will be three or 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.