Algebraische Ansätze für Verteilte Datenspeicherung

• Antragsteller: Dr.-Ing. Alexander Zeh
• Fachliche Zuordnung: Elektronische Halbleiter, Bauelemente und Schaltungen, Integrierte Systeme, Sensorik, Theoretische Elektrotechnik
• Förderung: Förderung von 2013 bis 2016
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 250295321

• Erstellungsjahr: 2017

Zusammenfassung der Projektergebnisse

The goal of distributed storage systems is to store data in a network, which consists of several nodes. Two main challenges in the development of such systems are the reliability of the data availability and the efficiency of the data storage. Further, the required amount of traffic in the network when repairing node failures or updating stored data, should be minimized. Modeling the stored information per node as symbols (over a finite field) allows the application of error-correcting codes which are typically used in magnetic or optic storage systems and to ensure the reliability of communication systems. During this fellowship new error-correcting codes were constructed and efficient decoding methods with focus on distributed storage systems were developed. In particular we considered long cyclic codes over GF(4) and GF(8) which are better than BCH codes in the highrate region. We proved their minimum Hamming distance and gave a polynomial-time list decoding approach for a new family of cyclic codes. Furthermore, we analyzed quasi-cyclic product codes. Key results were an explicit expression for the generator polynomial in function of the generator polynomials of the component codes (for certain cases) and a syndrome-based decoding approach. Efficient decoding methods for error-correcting codes suited for distributed storage systems help to reduce energy and space. Among others, we developed an improved erasure list decoding approach of locally repairable codes using alphabet-dependent list recovery. We gave several explicit constructions and illustrated our improvement for several examples (and certain parameter ranges). Another result obtained during this fellowship was a new lower bound on the minimum Hamming distance of cyclic codes using small-minimum-distance cyclic codes. Beside the proof of the new bound, we show certain properties of cyclic codes with small minimum distance. An efficient multi-trial polynomial-time list decoding algorithm for generalised Reed-Solomon codes was developed at the beginning of the fellowship. We performed a complexity analysis of the algorithm and identified the cases were our approach is beneficial.

Projektbezogene Publikationen (Auswahl)

• A new bound on the minimum distance of cyclic codes using small-minimum-distance cyclic codes. Des. Codes Cryptography 71(2): 229-246 (2014)
  Alexander Zeh, Sergey Bezzateev
  
• Decoding interleaved Reed-Solomon codes beyond their joint error-correcting capability. Des. Codes Cryptography 71(2): 261-281 (2014)
  Antonia Wachter-Zeh, Alexander Zeh, Martin Bossert
  
• Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes. Des. Codes Cryptography 73(2): 507-527 (2014)
  Johan S. R. Nielsen, Alexander Zeh
  
• Improved erasure list decoding locally repairable codes using alphabet-dependent list recovery. IEEE International Symposium on Information Theory 2016: 1581-1585
  Alexander Zeh, Antonia Wachter-Zeh
  
• Spectral Analysis of Quasi-Cyclic Product Codes. IEEE Trans. Information Theory 62(10): 5359-5374 (2016)
  Alexander Zeh, San Ling
  
• Long Cyclic Codes Over GF(4) and GF(8) Better Than BCH Codes in the High-Rate Region. IEEE Trans. Information Theory 63(1): 150-158 (2017)
  Ron M. Roth, Alexander Zeh