Report

Teaser, summary, work performed and final results

Periodic Reporting for period 1 - DaRe (Data Reliability in Networks and Storage Memories)

Teaser

Data networks and storage media play a key role in our modern every-day life. However, these systems are highly susceptible to errors which makes successful reception/retrieval of the transmitted/stored data impossible. In data networks, errors occur due to interference with...

Summary

Data networks and storage media play a key role in our modern every-day life. However, these systems are highly susceptible to errors which makes successful reception/retrieval of the transmitted/stored data impossible. In data networks, errors occur due to interference with other users, due to multipath propagation of the signal, or due to component noise of the receiver. Data storage media like flash memories suffer from manufacturing imperfections, wearout, and fluctuating read/write errors. In order to transmit and store data reliably, high-performance error-correcting codes and efficient decoding algorithms are hence a necessary means. The objective of this project was to provide novel and superior approaches for reliability in data networks and storage media. By means of error-correcting codes and information-theoretic analyses, we made data transmission and storage more reliable against errors of different types. The first part of this project dealt with the construction of better and more efficient coding schemes for networks. In particular, we constructed subspace codes with high cardinality and low decoding complexity, and improved the reliability of multi-source networks. The second part of this project analysed the physical error model of non-volatile storage memories like flash memories and developed coding strategies which correct these errors and mask defect cells of the memory.

Work performed

1.) Good Network Codes---By Ferrers Diagram Rank-Metric Codes
In random linear network coding (RLNC), each node
forwards random linear combinations of all packets received so
far. The data packets can be seen as vectors over a finite field and the internal network structure is assumed to
be unknown. However, due to the linear combinations, one
single erroneous packet can propagate widely throughout the whole network and can render the whole transmission
useless. This makes error-correcting codes in RLNC essential to guarantee reliability.
It was shown in by Kötter and Kschischang that
subspace codes are highly suitable for this purpose.
The multi-level construction by Etzion and Silberstein is one of the
constructions providing codes with the largest known cardinality
for subspace codes. This construction is based on the union of several lifted rank-metric codes,
which are constructed in Ferrers diagrams.

In this project, we have investigated and constructed optimal rank-metric codes in Ferrers diagrams.
First, we have considered rank-metric anticodes and proved a code-anticode bound for Ferrers diagram rank-metric codes.
Four techniques and constructions of Ferrers diagram rank-metric
codes were presented, each providing optimal codes for different
diagrams and parameters for which no optimal solution was known before.

2.) Good Network Codes---Investigation of List Decodability of Gabidulin Codes
Subspace codes can be applied for error-correction in network coding.
A special class of almost-optimal subspace codes can be constructed
by lifting rank-metric codes.
Gabidulin codes can be seen as the rank-metric
equivalent of Reed–Solomon codes.
In this project, subspace codes were used to prove two bounds
on the list size in decoding certain Gabidulin codes. The first
bound is an existential one, showing that exponentially-sized
lists exist for codes with specific parameters. The second bound
presents exponentially-sized lists explicitly, for a different set of
parameters. Both bounds rule out the possibility of efficiently
list decoding several families of Gabidulin codes for any radius
beyond half the minimum distance. Such a result was known so
far only for non-linear rank-metric codes, and not for Gabidulin
codes.

These results reveal a significant difference in list decoding
Gabidulin and Reed–Solomon codes, although the definitions
of these code classes strongly resemble each other.

3.) Codes for Partially Stuck-at Memory Cells
In this project, we have studied 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.
Our main contribution in the project is the study of codes for
masking u partially stuck-at cells. We have first derived lower and upper
bounds on the redundancy of such codes. We have then presented three code
constructions over an alphabet of size q.
Furthermore, we have studied the dual defect model in
which cells cannot reach higher levels, and shown that codes for
partially stuck-at cells can be used to mask this type of defects
as well. Lastly, we have analyzed the capacity of the partially stuck-at
memory channel.

Final results

1.) Good Network Codes---By Ferrers Diagram Rank-Metric Codes
Before, only optimal codes for very special parameters were known.
This work has already received significant attention at conferences and many
researchers from other universities showed their interest in using these
codes in applications.
In future, we will investigate the impact on network coding of these
constructions and perform simulations to demonstrate the performance
gain.
These results were also presented at conferences for the COST Action IC-1104,
and therefore disseminated to the European network codingcommunity.
Also, it is a collaboration of the Technion with the University of
Neuchatel in Switzerland and therefore a basis for a future collaboration
between these two groups. Before this project, there was no collaboration
between these two groups.

2.) Good Network Codes---Investigation of List Decodability of Gabidulin Codes
This works proves that several classes of Gabidulin codes cannot be
list decoded beyond the unique decoding radius.
This was a fundamental open question in theoretical coding theory
and our results gained a lot of attention from famous researchers.
We have presented these results at the IEEE International Symposium
on Information Theory 2015.
Meanwhile this work was cited several times amongst others by Guruswami and his group
who is one of the top researchers in coding theory and we have communicated
extensively with him and his group about our results.
Therefore, these results have increased my international visibility
significantly and I have established new collaborations with renown
researchers and their groups.
Further, based on my ideas, I have guided the PhD student
Netanel Raviv to achieve these results. This has therefore
contributed to my supervision skills.

3.) Codes for Partially Stuck-at Memory Cells

Within in this project, together with Eitan Yaakobi, we were the first
researchers who investigated the problem of partially stuck cells
from a coding point of view.
It is therefore the first work which considers the practically quite
relevant model of partially stuck cells and develops good (sometimes even optimal) code constructions.
The significance of these code constructions was also already recognized
by industry.
I have presented these results at SanDisk Israel, and they want to implement our
constructions in hardware to see how good they perform.
My talk and secondment and SanDisk have further contributed
to establish a long-lasting collaboration between SanDisk and
Prof. Eitan Yaakobi at the Technion.
This is a significant step in establishing research on memories in
Israel and Europe since so far, most of the research was done in the US.

Website & more info

More info: http://antonia.codingtheory.eu.