Servicenavigation

Detailseite

Zurück

Projekt Druckansicht

Decodierung algebraischer Codes über die halbe Mindestdistanz und Listencodierung

Fachliche Zuordnung Elektronische Halbleiter, Bauelemente und Schaltungen, Integrierte Systeme, Sensorik, Theoretische Elektrotechnik
Förderung Förderung von 2009 bis 2015
Projektkennung Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 142255864
 
Erstellungsjahr 2014

Zusammenfassung der Projektergebnisse

The main goals of the project have been as follows: 1. Algorithms for decoding Reed–Solomon (RS) codes of any rate beyond half the minimum distance. 2. Generalization of these decoding algorithms for Algebraic Geometry (AG) codes, Gabidulin codes and Goppa codes. 3. Design, analysis and decoding of Gabidulin codes for coding in communication networks (Network Coding). In the project we propose algorithms for decoding beyond half the minimum distance of the most popular evaluation codes and their interleaving. The following code classes are included in the project: Reed– Solomon codes, Chinese Remainder codes, Hermitian codes, and Gabidulin codes. We propose efficient decoding algorithms and analyze decoding radii, decoding complexity, and decoding failure probabilities. Gabidulin codes are decoded in rank metric, which is required by random linear network coding. We correct errors and erasures for Gabidulin codes. Other codes are decoded in Hamming metric, for which we propose hard decision decoding algorithms correcting errors and erasures. For Reed–Solomon codes we also suggest soft decision decoding methods including generalized minimum distance (GMD) decoding. In contrast to interpolation-factorization Guruswami–Sudan list-decoder, we use simple syndrome based unique-decoding algorithms which have the same decoding radii. Some results for general cyclic codes were also obtained. The stated goals of the project have been achieved. A summary of the main results obtained is as follows: 1. For hard decision decoding of Reed–Solomon codes of arbitrary rate beyond half their minimum distance an efficient algorithm was proposed. This unique-decoder generalizes our method of power decoding for codes of arbitrary rate and has the same decoding radius as the Guruswami– Sudan list-decoder. 2. New efficient algorithms were suggested for soft decoding of Reed–Solomon codes and their interleaving. The first proposed approach is based on the Wu algorithm and has performance compao rable to the K¨ tter-Vardy algorithm but having much lower complexity. The second decoder uses the Forney’s idea of multitrial (GMD) decoding and in case of interleaved Reed–Solomon codes dramatically decrease the number of necessary trials. 3. New efficient algorithms were proposed for unique decoding Chinese remainder codes and their interleaving. We reduce the decoding problem to find a short vector in a Z-lattice, which can be done using the LLL algorithm, resulting in the decoder with nearly linear complexity and decoding radius beyond half the minimum distance. 4. For general class of cyclic codes new bounds for the code distance d were obtained and efficient decoders correcting up to d/2 errors were proposed. The new bound improve the BCH and Hartmann-Tzeng bounds. 5. For decoding Hermitian codes and their interleaving up to half their minimum distance and beyond we proposed new efficient algorithms based on the Euclidean algorithm. To correct bursts of errors we propose an algorithm having subquadratic complexity. This algorithm reduces decoding of Hermitian codes to decoding of interleaved Reed–Solomon codes. 6. Previous results were obtained for the Hamming metric. To decode Gabidulin codes in rank metric (required e.g. for random linear network coding) we proposed new fast algorithms correcting errors and erasures. Several open problems remain after or arose through the project and are described in the following. The theoretical proof of the decoding radius and the failure probability for power decoding up to the Sudan radius and up to the Johnson radius. In the context of efficient decoding of Gabidulin codes, there are still open problems for accelerating the decoding process. Moreover, it is interesting to analyze fast decoding of Gabidulin codes in the context of network coding. One challenge of decoding Gabidulin codes is decoding beyond half the minimum rank distance using decoding of interleaved Gabidulin codes, or using the list–decoding Guruswami–Sudan principle. Power decoding for high rate Chinese remainder codes is an open problem.

Projektbezogene Publikationen (Auswahl)

 
 

Zusatzinformationen

© 2025 DFG Kontakt / Impressum / Datenschutz

Textvergrößerung und Kontrastanpassung