Seminar on Coding for Non-Volatile Memories – 048704/236803

Spring 2015

Instructors: Eitan Yaakobi (CS) and Yuval Cassuto (EE)

Lecture: Wednesdays, 9:30-11:30

Location: Taub 3

(starts March 18, 2015)

In brief:

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 strength of coding is that it can provide flexible and guaranteed performance parameters, and often show optimality of these parameters given the storage efficiency. A few very promising coding techniques have emerged as having potential to improve real-world performance of non-volatile storage. The course will concentrate on these key research areas, in addition to techniques that are in a more preliminary stage of research.

Specific topics:

  1. Re-write codes, WOM codes
  2. Rank modulation and data representation with permutations
  3. Error-correcting codes
  4. Constrained codes
  5. Memristor crossbar codes
  6. Emerging performance-boosting codes

Acedemic information:

2 Units. Graduate course, open to excellent undergraduates in their last year upon instructor approval.

The course has a strong mathematical scope, and designed for students with good mathematical skill and interest. Please see pre-requisites below.

A large part of the course will consist of lectures by the students. Each week a student will be assigned a research paper to present in class after reading it thoroughly. The paper will be selected in coordination with the instructors from the reference list below, or other related papers. The same paper will be read by all students, and each will submit a summary before the lecture.

Grading policy:

paper summaries 30%

class presentation 60%

discussion participation 10%

 

Pre-requisities: at least one of:

236309 Introduction to Coding Theory 046205 Introduction to Coding Theory in Communication 236315 Algebraic Methods in Computer Science 046733 Information Theory 236520 Coding for Storage Systems 048934 Coded Communications

Office hours:

Yuval: Tuesdays 16:00-17:00 (appointment recommended) -or- after class -or- by email.

Eitan: Wednesdays 11:30-12:30

Slides:

Lecture 1, 18/3/15: part1 (historical backround), part2 (NVM coding survey)

Lecture 2, 25/3/15: part1 (linear codes), part2 (WOM codes, rank modulation)

Lecture 3, 1/4/15: part1 (asymmetric limited-magnitude errors), part2 (rank modulation: constructions and perfect codes)

Lecture 4, 15/4/15: part1 (balanced codes,floating codes), part2 (resistive memories: the sneak-path problem)

Lecture 5, 29/4/15: Roman Shor: presentation of “Rank Modulation for Flash Memories”

Lecture 6, 6/5/15: part1 (flash memory architecture), part2 (“Threshold Read Algorithms, guest lecture by Evyatar Hemo)

Lecture 7, 13/5/15: Yuval Ben Hur: presentation of “Low Complexity Two-Dimensional Weight-Constrained Codes”

Lecture 8, 20/5/15: Ran Koretzki: presentation of “Codes for Asymmetric Limited-Magnitude Errors with Application to Multi-Level Flash Memories”

Lecture 9, 27/5/15: Gali Glam: presentation of “Quasi-cross Lattice Tilings with Applications to Flash Memory”

Lecture 10, 3/6/15: Erez Fridman: presentation of “Codes for High Performance Write and Read Processes in Multi-Level NVMs”

Lecture 11, 10/6/15: Gili Yavneh: presentation of “Codes in Permutations and Error Correction for Rank Modulation”

Lecture 12, 24/6/15: guest lecture by Dr. Sarit Buzaglo: “Coding Schemes for Inter-Cell Interference in Flash Memory”

Assignments:

 

Students are asked to read the paper upcoming for presentation each week, and submit a questionnaire on it. The questionnaire is due on Tuesdays by 17:00, and should include answers to the following questions:

  • What is the coding model? Specify all the parameters of the model, and briefly explain what each represents.
  • What is the motivation for the developed coding scheme?
  • Identify the main result of the paper, and explain it in words.
  • Evaluation: how strong the results are? (The strength of results is expressed in being 1) tight with respect to bounds, 2) general, covering large parameter ranges, 3) deep in the tools used in the proofs, 4) any additional subjective criterion by the reader.

References:

  1.  A. Jiang, V. Bohossian and J. Bruck, Rewriting Codes for Joint Information Storage in Flash Memories, in IEEE Transactions on Information Theory, vol. 56, no. 10, pp. 5300-5313, October 2010.
  2.  Eitan Yaakobi, Scott Kayser, Paul H. Siegel, Alexander Vardy, and Jack K. Wolf, Codes for Write-Once Memories, IEEE Transactions on Information Theory, vol. 58, no. 9, pp. 5985 –5999, September 2012.
  3. Eitan Yaakobi, Hessam Mahdavifar, Paul H. Siegel, Alexander Vardy, and Jack K. Wolf, Rewriting Codes for Flash Memories, IEEE Transactions on Information Theory, vol. 60, no. 2, pp. 964 –975, February 2014.
  4.  Yuval Cassuto and Eitan Yaakobi, Short Q-ary Fixed-Rate WOM Codes for Guaranteed Re-writes and with Hot/Cold Write Differentiation, IEEE Transactions on Information Theory, vol. 60, no. 7, pp. 3942 –3958, July 2014
  5. A. Jiang, M. Schwartz and J. Bruck, Correcting Charge-constrained Errors in The Rank Modulation Scheme, in IEEE Transactions on Information Theory, vol. 56, no. 5, pp. 2112-212-, May 2009
  6. A. Jiang, R. Mateescu, M. Schwartz and J. Bruck, Rank Modulation for Flash Memories, in IEEE Transactions on Information Theory, vol. 55, no. 6, pp. 2659-2673, June 2009.
  7. Alexander Barg, Arya Mazumdar, Codes in Permutations and Error Correction for Rank Modulation, IEEE Transactions on Information Theory, Vol. 56, Issue 7, pp. 3158-3165, July 2010.
  8. Y. Cassuto, M. Schwartz, V. Bohossian and J. Bruck, Codes for Asymmetric Limited-Magnitude Errors with Application to Multi-Level Flash Memories, IEEE Transactions on Information Theory, 04/2010
  9. Sarit Buzaglo and Tuvi Etzion, Tiling with n-Dimensional Chairs and Their Applications to Asymmetric Codes, in IEEE Transections on Information Theory, vol. 59, no. 3, pp. 1573-1582, March 2013.
  10. Moshe Schwartz, Quasi-cross lattice tilings with applications to flash memory, IEEE Trans. On Inform. Theory, 58 (4), pp. 2397-2405, April 2012.
  11. A. Sharov and R.M. Roth, New Upper Bounds for Grain-Correcting and Grain-Detecting Codes , in Proc. IEEE Symp. Inform. Theory, Honolulu, HI, 2014, pp. 1121–1125.
  12. Yuval Cassuto, Shahar Kvatinsky, and Eitan Yaakobi, Sneak-path constraints in memristor crossbar arrays, Proc. IEEE International Symposium on Information Theory, pp. 156 –160 , Istanbul, Turkey, July 2013 .
  13. E. Hemo and Y. Cassuto,  Codes for High Performance Write and Read Processes in Multi-Level NVMs, IEEE International Symposium on Information Theory, ISIT 2014.
  14. Ravi Motwani and Eitan Yaakobi, Construction of Random Input-Output Codes with Moderate Block Lengths, Proc. IEEE Information Theory Workshop , Hobart, Tasmania, Australia, November 2014.
  15. E. Ordentlich and R.M Roth, Low Complexity Two-Dimensional Weight-Constrained Codes. IEEE Trans. On Inform. Theory, 58 (6), pp. 3892–3899, June 2012.