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.