Workshop on Coding for Emerging Memories and Storage Technologies
Date(s) - 03/05/2015
Categories No Categories
Workshop on Coding for Emerging Memories and Storage Technologies
Presentations Now Available
The demand for massive amounts of high-performance storage has driven the continuous scaling of fast non-volatile memory technologies. It has now become very challenging to continue the density scaling without significant compromises to performance. Therefore, there is great need to develop new schemes that will guarantee high-density storage simultaneously with high performance. An essential part of these schemes is coding, which optimizes the representation of data within the storage device to the performance requirements of the hosting systems.
The workshop will focus on coding in general and for memories and storage technologies in particular.
The workshop will offer a setup for exchange of fresh ideas with high leading researchers in the field of coding and information theory
8:30-9:15 Coffee get together 9:15-9:30 Opening remarks 9:30-10:30 Session I Row-by-row coding for mitigation of bitline inter-cell interference in MLC flash memories – PDF
Paul Siegel, Viterbi Visiting Faculty Chair, UC San Diego
Reliable data storage: A broader approach and its opportunities – PDF
Andrew Jiang, Texas A&M University
10:30-10:50 Coffee break 10:50-11:50 Session II Between Shannon and Hamming: Codes against limited adversaries – PDF
Sidharth Jaggi, The Chinese University of Hong Kong
Converses in channel coding –
Sergio Verdu, Princeton University
11:50-13:10 Lunch 13:10-14:10 Session III Spatial coupling vs. block coding: A comparison – PDF
Dan Costello, University of Notre Dame
On the size of permutation balls under the infinity norm – PDF
Moshe Schwartz, Ben Gurion University
14:10-14:30 Coffee break 14:30-15:30 Session IV New results on locally repairable codes and matroids – PDF
Camilla Hollanti, Aalto University
Lower bounds for locally recoverable codes – PDF
Itzhak Tamo, Tel Aviv University
15:30-16:00 Break 16:00-17:00
students/postdocs presentations: Netanel Raviv, Antonia Wachter-Zeh –
Antonia Wachter-Zeh- PDF
Netanel Raviv – PDF
Viterbi Visiting Faculty Chair
Row-by-row coding for mitigation of bitline inter-cell interference in MLC flash memories
Inter-cell interference (ICI) is a significant cause of errors in flash memories. In two-level (SLC) flash memory, ICI arises when 1, 0, 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by use of conventional constrained codes that forbid the 1, 0, 1 pattern. This approach does not address the problem of vertical ICI, however. In this work, we present a row-by-row coding technique that eliminates vertical 1, 0, 1 patterns while preserving the sequential wordline programming order. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a relaxed constraint on vertical 1, 0, 1 patterns with a systematic error correcting code, that can mitigate vertical ICI errors while achieving a higher overall code rate, provided that the vertical ICI error probability is sufficiently small.
Reliable data storage: A broader approach and its opportunities
Error-correcting codes are reaching channel capacities, so it is important to explore new approaches in order to further improve data reliability. In conventional error correction, information bits are typically assumed to be redundancy-free. However, for “intelligent” data such as languages, there is usually plenty of redundancy left in the information bits even after compression. It is of great value to combine the two fundamental error correction approaches: by adding external redundancy to data (as ECCs do), and by exploring the internal redundancy in data. It is consistent with the spirit of error correction: use all the knowledge we have to recover the original information. In this talk, we discuss this broader approach for error correction, and show how it presents new opportunities for research.
Between Shannon and Hamming: Codes against limited adversaries
An adversary wishes to corrupt stored (or transmitted) data, but operates in an information-limited manner. Examples of such limitations may include only viewing some subset of the data, viewing those subsets causally, or with the encoder getting feedback about the corruption. We determine the capacity of some classes of such channels (in particular over "large alphabets").
This is an overview of a long line of classical results, and also work done over the last few years (with an emphasis on a flurry of recent results) in collaboration with Bikash Kumar Dey, Anand Dilip Sarwate, Michael Langberg, Zitan Chen, Mayank Bakshi, Qiaosheng Zhang (Eric), Alex Sprintson, and Swanand Kadhe.
Converses in Channel Coding
Converse results give relationships between size and error probability that must be satisfied by every code. The talk will include a brief survey of converse methods in data transmission including some recent results.
Spatial coupling vs. block coding: A comparison
In this talk, we compare spatially coupled LDPC codes to LDPC block codes from several different perspectives. First, asymptotic ensemble average properties are considered, including bothiterative decoding thresholds and minimum distance growth rates. Protograph-based code ensembles form the basis for this comparison. Next, finite-length code properties, such as bit-error-rate performance, decoding latency, and decoding complexity are compared. With window decoding, we see that spatially coupled codes achieve a performance advantage compared to block codes for fixed decoding latency and practical block (window) lengths. Decoding complexity comparisons are also presented for both binary and non-binary codes. Finally, the performance advantages of spatially coupled codes are shown to also hold when puncturing is employed to achieve higher code
On the size of permutation balls under the infinity norm
One of the main goals of coding theory is to study problems of ball-packing in different metric spaces. Recently, motivated by applications to flash memories, the symmetric group, S_n, endowed with the infinity norm, has gained interest. Surprisingly, unlike most other spaces, our knowledge on the size of balls is lacking, and the lower and upper bounds are far apart.
In this talk I will describe a couple of results on the subject. The first will be an exact solution for the case of a fixed radius, and n tending to infinity. The other will be a study of the case of radius r linear in n. In the latter case, while we're still not able to match the lower and upper bounds, we reduce the gap in rate by a factor of approximately 10.
New results on locally repairable codes and matroids
In this talk, we study linear locally repairable codes (LRCs) from a geometric viewpoint. Generalizing to almost affine codes, LRC have a very nice matroid representation, where all local and global parameters of the code occur as invariants of the matroid. We show how the known Singleton-type bounds for LRCs are valid for all matroids, and how to determine for which values of the local and global parameters one can find matroids meeting this bound. Finally, we survey some results about the representability of matroids, providing conditions for when the matroids have a representation as linear codes. This is joint work with Thomas Westerbäck, Ragnar Freij, and Toni Ernvall.
Lower Bounds for Locally Recoverable Codes
Locally Recoverable (LRC) codes are codes that enable recovery from a single symbol erasure in a local fashion, i.e., by accessing a relatively small number of other codeword symbols. This class of codes currently forms an active area of research. In this talk we address the problem of asymptotic lower (achievability) bounds on the parameters of LRC codes. Using expander graph arguments, we prove existence of asymptotically good LRC codes with any number t of recovering sets and large minimum distance. We also derive asymptotic GV-type bounds for LRC codes for codes with one and two recovering sets.
Joint work with Alexander Barg (University of Maryland) and Alexey Frolov (IITP, Russian Academy of Sciences).
Access-optimal MSR codes with optimal sub-packetization over small fields
This work presents a new construction of access-optimal minimum storage regenerating codes which attain the sub-packetization bound. These distributed storage codes provide the minimum storage in a node, and in addition have the following two important properties: first, a helper node accesses the minimum number of its symbols to repair a failed node; second, given storage in each node, the entire stored data can be recovered from any 2log (3log , respectively) for 2 parity nodes (3 parity nodes, respectively). The goal of this work is to construct such optimal codes over the smallest possible finite fields. The field size required for our construction is significantly smaller when compared to previously known codes.
Codes for Partially Stuck-at Memory Cells
In this work, we study a new model of defect memory cells, called partially stuck-at memory cells, which is motivated by the behavior of multi-level cells in non-volatile memories such as flash memories and phase change memories. If a cell can store the q levels 0, 1,…,q-1, we say that it is partially stuck-at level s, where 1 \leq s \leq q-1, if it can only store values which are at least s. We follow the common setup where the encoder knows the positions and levels of the partially stuck-at cells whereas the decoder does not.
Our main contribution in the paper is the study of codes for masking u partially stuck-at cells. We first derive lower bounds on the redundancy of such codes and upper bounds by two trivial constructions. We then present three code constructions over an alphabet of size q, by first considering the case where the cells are partially stuck-at level s=1. The first construction works for u<q and is asymptotically optimal if u+1 divides q. The second construction uses the reduced row Echelon form of matrices to generate codes for the case u\geq q, and the third construction solves the case of arbitrary u by using codes which mask binary stuck-at cells. We then show how to generalize all constructions for arbitrary levels. Furthermore, we study the dual defect model in which cells cannot reach higher levels, and show that codes for partially stuck-at cells can be used to mask this type of defects as well. Lastly, we analyze the capacity of the partially stuck-at memory channel and study how far our constructions are from the capacity.