Decodierung algebraischer Codes über die halbe Mindestdistanz und Listencodierung
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)
- A link between guruswami–sudan’s list-decoding and decoding of interleaved reed–solomon codes. In IEEE International Symposium on Information Theory (ISIT), pages 1198–1202, Austin, USA, 2010
Alexander Zeh and Christian Senger
(Siehe online unter https://doi.org/10.1109/ISIT.2010.5513427) - Decoding reed-solomon codes up to the sudan radius with the euclidean algorithm. In International Symposium on Information Theory and its Applications (ISITA), October 2010
Alexander Zeh and Wenhui Li
(Siehe online unter https://doi.org/10.1109/ISITA.2010.5649520) - Decoding reed–solomon codes up to the sudan radius with the euclidean algorithm. In International Symposium On Information Theory & Its Applications (ISITA), pages 986–990, Taichung, Taiwan, 2010
Alexander Zeh and Wenhui Li
(Siehe online unter https://doi.org/10.1109/ISITA.2010.5649520) - On reformulated multi-sequence problems. In 12th International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), September 2010
Alexander Zeh and Wenhui Li
- An interpolation procedure for list decoding reed–solomon codes based on generalized key equations. IEEE Transactions on Information Theory, 57(9):5946–5959, September 2011
Alexander Zeh, Christian Gentner, and Daniel Augot
(Siehe online unter https://doi.org/10.1109/TIT.2011.2162160) - Bounds on Collaborative Decoding of Interleaved Hermitian Codes with a Division Algorithm and Virtual Extension. In 3rd International Castle Meeting on Coding Theory and Applications (3ICMCTA), September 2011
Sabine Kampf
- Fast multi-sequence shift-register synthesis with the euclidean algorithm. Advances in Mathematics of Communications, 5(4):667—680, November 2011
Alexander Zeh and Antonia Wachter
(Siehe online unter https://doi.org/10.3934/amc.2011.5.667) - Generalized Minimum Distance Decoding with Arbitrary Error/Erasure Tradeoff. PhD thesis, University of Ulm, Ulm, Germany, 2011
Christian Senger
- Optimal threshold-based multi-trial error/erasure decoding with the guruswami-sudan algorithm. In Information Theory Proceedings (ISIT), 2011 IEEE International Symposium on, pages 845–849, July 2011
Christian Senger, Vladimir Sidorenko, Martin Bossert, and Viktor V. Zyablov
(Siehe online unter https://doi.org/10.1109/ISIT.2011.6034255) - Solving the Key Equation for Hermitian Codes with a Division Algorithm. In IEEE International Symposium on Information Theory 2011 (ISIT 2011), August 2011
Sabine Kampf, Martin Bossert, and Irene Bouw
(Siehe online unter https://doi.org/10.1109/ISIT.2011.6033681) - A new bound on the minimum distance of cyclic codes using small-minimum-distance cyclic codes. Designs, Codes and Cryptography, pages 1–18, July 2012
Alexander Zeh and Sergey Bezzateev
(Siehe online unter https://doi.org/10.1007/s10623-012-9721-3) - A new error and erasure decoding approach for cyclic codes. In International Workshop on Algebraic and Combinatorial Coding Theory (ACCT), Pomorie, Bulgaria, 2012
Alexander Zeh and Sergey Bezzateev
- Adaptive end-to-end network coding based on algebraic codes. In Workshop on Performance Evaluation and Modeling in Wireless Networks, Tunis, Nov. 2012
Senger Christian, Zeh Alexander, Yu Fan, and Schober Steffen
- Asymptotic single-trial strategies for gmd decoding with arbitrary error-erasure tradeoff. Problems of Information Transmission, 48(4):324–333, 2012
Jos H. Weber, Vladimir Sidorenko, Christian Senger, and Khaled A.S. Abdel-Ghaffar
(Siehe online unter https://doi.org/10.1134/S0032946012040023) - Decoding cyclic codes up to a new bound on the minimum distance. IEEE Transactions on Information Theory, 58(6):3951–3960, June 2012
Alexander Zeh, Antonia Wachter-Zeh, and Sergey V. Bezzateev
(Siehe online unter https://doi.org/10.1109/TIT.2012.2185924) - Decoding Hermitian Codes -An Engineering Approach. PhD thesis, University of Ulm, Ulm, Germany, 2012
Sabine Kampf
- Decoding interleaved Reed- Solomon codes beyond their joint error-correcting capability. Designs, Codes and Cryptography, pages 1–21, July 2012
Antonia Wachter-Zeh, Alexander Zeh, and Martin Bossert
(Siehe online unter https://doi.org/10.1007/s10623-012-9728-9) - Describing a cyclic code by another cyclic code. In IEEE International Symposium on Information Theory (ISIT), pages 2896–2900, Boston, USA, July 2012
Alexander Zeh and Sergey Bezzateev
(Siehe online unter https://doi.org/10.1109/ISIT.2012.6284054) - On Syndrome Decoding of Chinese Remainder Codes. In The 13th Int. Workshop on Algebraic and Combinatorial Coding Theory, 2012
Wenhui Li
- On the error-erasure-decoder of the Chinese remainder codes. In Problems of Redundancy in Inform. and Control Systems, XIII Int. Symposium on, pages 37–40. IEEE, 2012
Wenhui Li and Vladimir Sidorenko
(Siehe online unter https://doi.org/10.1109/RED.2012.6338403) - Unambiguous decoding of generalized ReedSolomon codes beyond half the minimum distance. In International Zurich Seminar (IZS), page 6366, Zurich, Switzerland, 2012
Alexander Zeh, Antonia Wachter, and Martin Bossert
(Siehe online unter https://doi.org/10.3929/ethz-a-007052646) - A unified view on known algebraic decoding algorithms and new decoding concepts. Information Theory, IEEE Transactions on, 59(11):7320–7336, Nov 2013
Martin Bossert and Sergey Bezzateev
(Siehe online unter https://doi.org/10.1109/TIT.2013.2274454) - Algebraic Soft- and Hard-Decision of Generalized Reed–Solomon and Cyclic Codes. PhD thesis, University of Ulm and Ecole Polytechnique ParisTech, Ulm, Germany and Paris, France, 2013
Alexander Zeh
(Siehe online unter https://doi.org/10.18725/OPARU-2512) - Decoding Interleaved Reed–Solomon and Hermitian Codes with Generalized Divisions. In Systems, Communication and Coding (SCC), Proc. 9th International ITG Conference on, pages 1–6. VDE, January 2013
Sabine Kampf and Wenhui Li
- Generalizing bounds on the minimum distance of cyclic codes using cyclic product codes. In IEEE International Symposium on Information Theory (ISIT), Istanbul, Turkey, July 2013
Alexander Zeh, Antonia Wachter-Zeh, Maximilien Gadouleau, and Sergey Bezzateev
(Siehe online unter https://doi.org/10.1109/ISIT.2013.6620201) - Multi-trial Guruswami–Sudan decoding for generalised Reed–Solomon codes. In International Workshop on Coding and Cryptography (WCC), 2013
Johan S. R. Nielsen and Alexander Zeh
- On Decoding Interleaved Chinese Remainder codes. In Information Theory Proceedings (ISIT), 2013 IEEE International Symposium on, pages 1052–1056. IEEE, July 2013
Wenhui Li, Vladimir Sidorenko, and Johan S. R. Nielsen
(Siehe online unter https://doi.org/10.1109/ISIT.2013.6620387) - On transform-domain decoding of gabidulin codes. In Int. Workshop Coding Cryptogr(WCC), pages 33–56, 2013
Wenhui Li, Vladimir Sidorenko, and Di Chen
- Bounds on collaborative decoding of interleaved hermitian codes and virtual extension. Designs, Codes and Cryptography, 70(1-2):9–25, 2014
Sabine Kampf
(Siehe online unter https://doi.org/10.1007/s10623-012-9625-2) - Efficient burst error correction by hermitian codes. In 21st International Symposium on Mathematical Theory of Networks and Systems, Groningen, The Netherlands, 2014
Wenhui Li, Xiaozhou Wang, and Vladimir Sidorenko
- Efficient burst error correction by hermitian codes. In The 21st International Symposium on Mathematical Theory of Networks and Systems (MTNS), 2014
Wenhui Li, Vladimir Sidorenko, and Xiaozhou Wang
- Fast skew-feedback shift-register synthesis. Designs, Codes and Cryptography, 70(1-2):55–67, 2014
Vladimir Sidorenko and Martin Bossert
(Siehe online unter https://doi.org/10.1007/s10623-012-9663-9) - On transform-domain error and erasure correction by gabidulin codes. Designs, Codes and Cryptography, 73(2):571–586, 2014
Wenhui Li, Vladimir Sidorenko, and Danilo Silva
(Siehe online unter https://doi.org/10.1007/s10623-014-9954-4) - Power Decoding of Reed–Solomon Codes Revisited. In 4th International Castle Meeting on Coding Theory and Applications, September 2014
Johan S.R. Nielsen
(Siehe online unter https://doi.org/10.1007/978-3-319-17296-5_32) - Power decoding Reed–Solomon codes up to the johnson radius. In ACCT, Svetlogorsk, 2014
Johan S.R. Nielsen
- Reduced list decoding of reed–solomon codes using reliability information. In 21st International Symposium on Mathematical Theory of Networks and Systems, Groningen, The Netherlands, 2014
Mostafa H. Mohamed, Johan S.R. Nielsen, and Martin Bossert
