Friday, April 3, 2020
Lexicographic Indexing
Robert Calderbank, Duke University
11:00am [Host: Hamid]

Data storage densities have increased by a factor 10,000 over the past 20 years, as coding theorists have developed new methods of signal processing that take full advantage of new physical substrates. The data storage industry relies on error correction techniques that combine constrained codes, designed to avoid problematic patterns, and low-density parity check (LDPC) codes specified by graphs, designed to correct the errors that remain.

In 1948, Shannon introduced the notion of capacity, and analyzed the maximum data rate supported by constrained sequences. In the 1990s, connections between constrained binary sequences and symbolic dynamics led to methods of encoding and decoding at or very close to this achievable rate. However, it is not clear how these methods work for modern non-binary physical substrates such as M/T/Q Flash cells, and how to adapt solutions when problematic patterns change with time.

This talk will construct constrained codes based on lexicographic indexing rather than symbolic dynamics. We will describe lexicographically ordered constrained codes (LOCO codes) that combine capacity-achieving rates with simple, reconfigurable encoding and decoding. We will present families of LOCO codes that forbid specific patterns in order to reduce inter-symbol interference in magnetic recording systems, and inter-cell interference in emerging Flash systems. When these LOCO codes are used to protect parity bits in a graph-based code, we demonstrate significant density gains on industry models.

Robert Calderbank directs the Rhodes Information Initiative at Duke University, where he is Professor of Electrical and Computer Engineering.  Dr. Calderbank is well known for contributions to voiceband modem technology, to quantum information theory, and for co-invention of space-time codes for wireless communication. His research papers have been cited more than 50,000 times and his inventions are found in billions of consumer devices. Professor Calderbank was elected to the National Academy of Engineering in 2005 and has received a number of awards, including the 2013 IEEE Hamming Medal for his contributions to information transmission, and the 2015 Claude E. Shannon Award.