Coding for Storage Systems (236520)

 


2017 Spring Semester


When: Wednesday, 14:30–16:30
Where: Taub 5
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

  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,
    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.