List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques

DOI10.1007/S10623-014-9953-5zbMATH Open1335.94104OpenAlexW1999418148MaRDI QIDQ398965FDOQ398965

Authors Antonia Wachter-Zeh, Alexander Zeh

Publication date 18 August 2014

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1404.6048

zbMATH Keywords

list decoding(interleaved) Gabidulin codesinterpolation-based decodingrank-metric codes

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: A new interpolation-based decoding principle for interleaved Gabidulin codes is presented. The approach consists of two steps: First, a multi-variate linearized polynomial is constructed which interpolates the coefficients of the received word and second, the roots of this polynomial have to be found. Due to the specific structure of the interpolation polynomial, both steps (interpolation and root-finding) can be accomplished by solving a linear system of equations. This decoding principle can be applied as a list decoding algorithm (where the list size is not necessarily bounded polynomially) as well as an efficient probabilistic unique decoding algorithm. For the unique decoder, we show a connection to known unique decoding approaches and give an upper bound on the failure probability. Finally, we generalize our approach to incorporate not only errors, but also row and column erasures.

Recommendations

• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
• Algebraic decoding of folded Gabidulin codes
• A module minimization approach to Gabidulin decoding via interpolation
• Improved syndrome decoding of lifted \(L\)-interleaved Gabidulin codes
• Coding and Cryptography

Cites work

• scientific article; zbMATH DE number 424718 (Why is no real title available?)
• scientific article; zbMATH DE number 922674 (Why is no real title available?)
• A Random Linear Network Coding Approach to Multicast
• A Rank-Metric Approach to Error Control in Random Network Coding
• Bilinear forms over a finite field, with applications to coding theory
• Bounds for projective codes from semidefinite programming
• Bounds on List Decoding of Rank-Metric Codes
• Coding and Cryptography
• Coding for Errors and Erasures in Random Network Coding
• Decoding of Reed Solomon codes beyond the error-correction bound
• Error and erasure correcting algorithms for rank codes
• Error-Correcting Codes in Projective Space
• Error-Correcting Codes in Projective Spaces Via Rank-Metric Codes and Ferrers Diagrams
• Improved decoding of Reed-Solomon and algebraic-geometry codes
• Johnson type bounds on constant dimension codes
• Linear authentication codes: bounds and constructions
• Linear-Algebraic List Decoding for Variants of Reed–Solomon Codes
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• Maximum-rank array codes and their application to crisscross error correction
• Network information flow
• Recursive Code Construction for Random Networks
• Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes
• Structural attacks for public key cryptosystems based on Gabidulin codes
• Theory of codes with maximum rank distance

Cited in

(13)

• LIGA: a cryptosystem based on the hardness of rank-metric list and interleaved decoding
• Improved syndrome decoding of lifted \(L\)-interleaved Gabidulin codes
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• On the geometry of balls in the Grassmannian and list decoding of lifted Gabidulin codes
• On transform-domain error and erasure correction by Gabidulin codes
• Rank-metric codes and their applications
• A module minimization approach to Gabidulin decoding via interpolation
• Decoding interleaved Gabidulin codes using Alekhnovich's algorithm
• Algebraic decoding of folded Gabidulin codes
• Row reduction applied to decoding of rank-metric and subspace codes
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory
• Fast decoding of lifted interleaved linearized Reed-Solomon codes for multishot network coding

This page was built for publication: List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q398965)