Workshop on Coding for Emerging Memories and Storage Technologies

  • Map Unavailable

    Date(s) - 03/05/2015
    All Day

    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

    Sponsored by:

    Yuval Cassuto, EE Technion
    Eitan Yaakobi, CS Technion


    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

    Session V 
    students/postdocs presentations: Netanel Raviv, Antonia Wachter-Zeh – 
    Antonia Wachter-Zeh- 
    Netanel Raviv – PDF



    Paul Siegel

    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.

    Andrew Jiang
    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. 

    Sidharth Jaggi
    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. 

    Sergio Verdu
    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.

    Dan Costello
    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

    Moshe Schwartz
    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.

    Camilla Hollanti
    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.

    Itzhak Tamo
    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).

    Students/Postdocs Session

    Netanel Raviv
    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.

    Antonia Wachter-Zeh
    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.