Error-Correcting Coding Strategies for Data Storage and Networks

• Applicant: Professorin Dr.-Ing. Antonia Wachter-Zeh
• Subject Area: Electronic Semiconductors, Components and Circuits, Integrated Systems, Sensor Technology, Theoretical Electrical Engineering
• Term: from 2016 to 2021
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 317311578

• Final Report Year: 2022

Final Report Abstract

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 was to make data storage and data transmission more reliable and efficient by means of algebraic coding theory. In particular, we considered three modern applications of errorcorrecting 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 have constructed 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 dealt with 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. The third work package dealt with coding for distributed data storage systems. In particular, we worked 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 was an important objective of this project. Further, we have considered Partial MDS (PMDS) codes where we have constructed codes with strong locality and regenerating properties. During this work, we have also set a focus on Private Information Retrieval (PIR), i.e., the task of downloading files from a server without revealing the file index to the server.

Publications

• Vector network coding based on subspace codes outperforms scalar linear network coding. IEEE Transactions on Information Theory, 64(4):2460–2473, 2018
  Tuvi Etzion and Antonia Wachter-Zeh
  
• Bounds and Code Constructions for Partially Defect Memory Cells. In International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), October 2020
  Haider Al Kim, Sven Puchinger, and Wachter-Zeh, Antonia
  
• Network-coding solutions for minimal combination networks and their sub-networks. IEEE Transactions on Information Theory, 66(11):6786–6798, 2020
  Han Cai, Johan Chrisnata, Tuvi Etzion, Moshe Schwartz, and Antonia Wachter-Zeh
  
• Private streaming with convolutional codes. IEEE Transactions on Information Theory, 66(4):2417–2429, 2020
  Lukas Holzbaur, Ragnar Freij-Hollanti, Antonia Wachter-Zeh, and Camilla Hollanti
  
• Secrecy and accessibility in distributed storage. In IEEE Global Communications Conference (GLOBECOM), pages 1–6, 2020
  Lukas Holzbaur, Stanislav Kruglik, Alexey Frolov, and Antonia Wachter-Zeh
  
• Almost affinely disjoint subspaces. Finite Fields and Their Applications, 75:101879, 2021
  Hedongliang Liu, Nikita Polyanskii, Ilya Vorobyev, and Antonia Wachter-Zeh
  
• Error decoding of locally repairable and partial MDS codes. IEEE Transactions on Information Theory, 67(3):1571–1595, 2021
  Lukas Holzbaur, Sven Puchinger, and Antonia Wachter-Zeh
  
• On the gap between scalar and vector solutions of generalized combination networks. IEEE Transactions on Information Theory, 67(8):5580–5591, 2021
  Hedongliang Liu, Hengjia Wei, Sven Puchinger, Antonia Wachter-Zeh, and Moshe Schwartz
  
• Partial MDS codes with regeneration. IEEE Transactions on Information Theory, 67(10):6425–6441, 2021
  Lukas Holzbaur, Sven Puchinger, Eitan Yaakobi, and Antonia Wachter-Zeh
  
• Secure codes with accessibility for distributed storage. IEEE Transactions on Information Forensics and Security, 16:5326–5337, 2021
  Lukas Holzbaur, Stanislav Kruglik, Alexey Frolov, and Antonia Wachter-Zeh