## 2018 Spring Semester

When: |
Wednesday, 14:30–16:30 |

Where: |
TBD |

Instructor: |
Ronny Roth, Taub Building 637, ronny(at)cs.technion.ac.il |

Teaching assistant: |
Rachel Berman, Taub Building 316, rberman(at)cs.technion.ac.il |

(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 (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

## 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).