# Coding for Storage Systems (236520)

## 2022 Spring Semester

 When: Wednesday, 14:30–16:30 Where: TBD Instructor: Ronny Roth, Taub Building 637, ronny(at)cs.technion.ac.il Teaching assistant: TBD (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

1. 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
2. Perron–Frobenius Theory
• Irreducible and primitive matrices
• Perron–Frobenius Theorem
• Capacity in terms of Perron eigenvalue
3. Finite-state encoders for constrained systems
• Encoder graphs
• Anticipation
• Approximate eigenvectors
• The state-splitting algorithm
4. 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,