Error-Correcting Coding Strategies for Data Storage and Networks

数据存储和数据传输已成为我们现代日常生活中不可或缺的一部分。然而，存储介质和传输系统非常容易受到错误的影响，这些错误往往会阻碍数据恢复过程，有时甚至使其无法恢复。本项目的目标是借助代数编码理论，使数据存储和数据传输更加可靠和高效。特别是，我们考虑了纠错码的三种现代应用：网络编码、存储器编码和分布式数据存储编码。在像因特网这样的网络中，错误例如由于与其他用户的干扰而发生，或者由于拥塞而丢失分组。像闪存(用于USB闪存驱动器或固态驱动器)这样的数据存储介质受到制造缺陷、磨损和波动的读/写错误的影响。在分布式数据存储(如云存储系统)中，最常见的问题是服务器故障，其任务是高效地重建丢失的数据。在网络编码方面，我们想要构造新的编码来分配网络节点上的线性组合的系数以及用于纠错。这尤其包括减少必要的字段大小和具有准线性时间复杂度的新的解码策略。项目的第二部分考虑非易失性存储器(例如，闪存)的编码。这里，我们将考虑存储单元(部分)卡住的问题。如果单元格不能更改其值或仅接受某些值，则该单元格(部分)被卡住。目标是在解码器不知道粘连单元的位置的假设下，在包含缺陷单元的存储器中存储尽可能多的信息。此外，我们将考虑对新的存储技术进行编码，例如3D闪存。第三个工作包涉及分布式数据存储系统的编码。特别是，我们将研究一类局部可修码(LRC)。这些代码旨在最大限度地减少在恢复故障服务器时必须从其下载数据的服务器数量。新码的构造和LRC的高效译码将是该项目的重要目标。

Data storage and data transmission has become an essential part of our modern every-day life. However, storage media and transmission systems are highly susceptible to errors which often hinder the data recovery process and sometimes even make it impossible. The goal of this project is to make data storage and data transmission more reliable and efficient by means of algebraic coding theory. In particular, we consider three modern applications of error-correcting codes: network coding, coding for memories, and coding for distributed data storage. In networks like the internet, errors occur, e.g., due to interference with other users, or packets are lost due to congestion.Data storage media like flash memories (used in USB flash drives or solid state drives) suffer from manufacturing imperfections, wearout, and fluctuating read/write errors. In distributed data storage (necessary, e.g., for cloud storage systems), the most common problem are failures of servers and the task is to reconstruct the lost data efficiently.In the area of network coding, we want to construct new codes for the assignment of the coefficients of the linear combinations at the nodes of the network as well as for error-correction. This includes in particular the reduction of the necessary field size and new decoding strategies with quasi-linear time complexity.The second part of the project considers coding for non-volatile memories (e.g., flash memories). Here, we will consider the problem of (partially) stuck memory cells. A cell is (partially) stuck if it cannot change its value or only take certain values. The goal is to store as much information as possible in memories that contain defect cells under the assumption that the decoder does not know the positions of the stuck cells. Further, we will consider coding for new storage technologies such as 3-D flash memories.The third work package deals with coding for distributed data storage systems. In particular, we will work on the class of locally repairable codes (LRCs). These codes are designed to minimize the number of servers from which data has to be downloaded when recovering a failed server. The construction of new codes and the efficient decoding of LRCs will be an important objective of this project.