Sarit Buzaglo – Systematic error correcting codes for rank modulation


Event Details

  • Date:

Flash memory is one of the most widely used non-volatile technology.
In flash memories, cells usually represent multiple levels, which correspond to the amount of electrons trapped in each cell.
Currently, one of the main challenges in flash memory cells is to program each cell exactly to its designated level.
Rank modulation is a new scheme that was proposed in order to overcome this difficulty.
In this setup, the information is carried by the relative values between the cells rather than by their absolute levels.
Thus, every group of cells induces a permutation, which is derived by the ranking of the level of each cell in the group.
Error correcting codes in this model were mostly studied by using the Kendall’s tau-metric.
Zhou et al. [ISIT12] proposed the concept of systematic codes for rank modulation and studied systematic error-correcting codes with the Kendall’s tau-metric.
In an (n,k) systematic code for permutations on n elements, each permutation on a given set of k symbols is a sub-permutation of exactly one codeword.

In this talk I will present our construction of systematic error-correcting codes for permutations in the Kendall’s tau-metric.
For most parameters our codes have better redundancy than the redundancy of the known constructions.
In particular, for a given t and for sufficiently large k we obtain (n,k) systematic t-error-correcting codes with redundancy t+1.