Show simple item record

AuthorPuchinger, Svendc.contributor.author
Date of accession2018-08-30T15:12:55Zdc.date.accessioned
Available in OPARU since2018-08-30T15:12:55Zdc.date.available
Year of creation2018dc.date.created
Date of first publication2018-08-30dc.date.issued
AbstractThis 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.dc.description.abstract
Languageen_USdc.language.iso
PublisherUniversität Ulmdc.publisher
LicenseStandarddc.rights
Link to license texthttps://oparu.uni-ulm.de/xmlui/license_v3dc.rights.uri
KeywordRank-Metric codesdc.subject
KeywordOne-point Hermitian codesdc.subject
KeywordEvaluation codesdc.subject
KeywordGabidulin codesdc.subject
KeywordInterleaved codesdc.subject
Dewey Decimal GroupDDC 620 / Engineering & allied operationsdc.subject.ddc
LCSHCoding theorydc.subject.lcsh
LCSHTelecommunications engineersdc.subject.lcsh
LCSHReed-Solomon codesdc.subject.lcsh
LCSHBar codingdc.subject.lcsh
LCSHHermitian operatorsdc.subject.lcsh
TitleConstruction and decoding of evaluation codes in hamming and rank metricdc.title
Resource typeDissertationdc.type
Date of acceptance2018-06-25dcterms.dateAccepted
RefereeBossert, Martindc.contributor.referee
RefereeHøholdt, Tomdc.contributor.referee
DOIhttp://dx.doi.org/10.18725/OPARU-9446dc.identifier.doi
PPN1030478260dc.identifier.ppn
URNhttp://nbn-resolving.de/urn:nbn:de:bsz:289-oparu-9503-9dc.identifier.urn
GNDHermitescher Operatordc.subject.gnd
GNDCodierungstheoriedc.subject.gnd
GNDKanalcodierungdc.subject.gnd
GNDDecodierungdc.subject.gnd
GNDRS-Codedc.subject.gnd
GNDNachrichtentechnikdc.subject.gnd
FacultyFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.affiliationGeneral
InstitutionInstitut für Nachrichtentechnikuulm.affiliationSpecific
Grantor of degreeFakultät für Ingenieurwissenschaften, Informatik und Psychologieuulm.thesisGrantor
DCMI TypeTextuulm.typeDCMI
CategoryPublikationenuulm.category


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record