Construction and decoding of evaluation codes in hamming and rank metric
| Autor: | Puchinger, Sven |
|---|---|
| Přispěvatelé: | Bossert, Martin, Høholdt, Tom |
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Bar coding
Interleaved codes Reed-Solomon codes One-point Hermitian codes Hermitescher Operator Data_CODINGANDINFORMATIONTHEORY Hermitian operators Decodierung Kanalcodierung Codierungstheorie Gabidulin codes Evaluation codes Nachrichtentechnik DDC 620 / Engineering & allied operations Telecommunications engineers Coding theory ddc:620 RS-Code Rank-Metric codes Computer Science::Information Theory |
| DOI: | 10.18725/oparu-9446 |
| Popis: | This dissertation considers constructions and decoders of several evaluation codes in Hamming and rank metric. Codes in Hamming metric have been studied since the 1950s and the known codes considered in this thesis have found many applications, e.g., satellite communication, CDs, DVDs, BluRays, RAID systems, QR codes, code-based cryptography, and modern storage systems. Rank-metric codes were first introduced in 1978 and have recently become an active research area due to their possible applications in network coding, cryptography, distributed storage systems, low-rank matrix recovery, and space-time coding. In Hamming metric, we propose new partial unique decoding algorithms for decoding interleaved Reed-Solomon and interleaved one-point Hermitian codes beyond half the minimum distance. The algorithms combine ideas of collaborative decoding of interleaved codes and power decoding. For interleaved Reed-Solomon codes, we achieve the same maximal decoding radius as the previous best decoder, but at a better complexity. Our decoder for interleaved one-point Hermitian codes improves upon the previous best maximal decoding radius at all rates. Simulation results for various parameters indicate that both algorithms achieve their maximal decoding radii with high probability for random errors. Inspired by a recent rank-metric code construction by Sheekey, called twisted Gabidulin codes, we present a new code class in Hamming metric: Twisted Reed-Solomon codes. The class contains many maximum distance separable (MDS) codes that are inequivalent to Reed-Solomon codes. We study the duals and Schur squares of the new codes and propose a list decoder that is efficient for many parameters. Furthermore, we single out two subclasses of long non-Reed-Solomon MDS codes and show that there is a subclass resisting some known structural attacks on the McEliece code-based cryptosystem. In rank metric, we present the first sub-quadratic runtime half-the-minimum-distance decoding algorithm for Gabidulin codes, a well-known class of maximum rank distance (MRD) codes that can be seen as the rank-metric analog of Reed-Solomon codes. The result is achieved by accelerating many operations over skew polynomial rings that occur in a known decoding algorithm. Further, we show that the core steps of several known decoding algorithms for interleaved Gabidulin codes, both key-equation- and interpolation-based, can be implemented using row reduction of skew polynomial matrices. By adapting well-known row-reduction algorithms over ordinary polynomial rings to skew polynomials, we achieve conceptually simple and in some cases faster decoding algorithms. The approach is inspired by several recent publications that found a unified description of various decoders of Reed-Solomon, one-point Hermitian, and their interleaved codes. Finally, we propose a generalization of Sheekey's twisted Gabidulin codes, using similar methods as for our twisted Reed-Solomon codes. The new code class contains many MRD codes that are inequivalent to both Gabidulin codes and the original twisted Gabidulin codes. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|