Decoding interleaved Gabidulin codes using Alekhnovich's algorithm

DOI10.1016/J.ENDM.2017.02.029MaRDI QIDQ1743304zbMATH OpenOpenAlexFDO

Authors Sven Puchinger, Sven Müelich, David Mödinger, Johan Rosenkilde né Nielsen, Martin Bossert

Publication date 13 April 2018

Full work available at URL https://arxiv.org/abs/1604.05899, https://orbit.dtu.dk/en/publications/a8a97c51-61ae-4c98-ac9a-1defd47d78ff

zbMATH Keywords

low-rank matrix recoverycharacteristic zeroGabidulin codes

Mathematics Subject Classification ID

Linear codes (general theory) (94B05) Decoding (94B35)

Abstract: We prove that Alekhnovich's algorithm can be used for row reduction of skew polynomial matrices. This yields an $O(el{l}^3{n}^{(omega+1)/2}log(n))$ decoding algorithm for $ell$-Interleaved Gabidulin codes of length $n$, where $omega$ is the matrix multiplication exponent, improving in the exponent of $n$ compared to previous results.

Recommendations

• Row reduction applied to decoding of rank-metric and subspace codes
• Coding and Cryptography
• List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques
• Fast decoding of Gabidulin codes
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases

Cites work

• Fast skew-feedback shift-register synthesis
• Linear Diophantine Equations Over Polynomials and Soft Decoding of Reed–Solomon Codes
• Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin Codes

Cited in

(8)

• On decoding procedures of intertwining codes
• Efficient decoding of interleaved subspace and Gabidulin codes beyond their unique decoding radius using Gröbner bases
• Fast decoding of lifted interleaved linearized Reed-Solomon codes for multishot network coding
• Decoding of Interleaved Alternant Codes
• Row reduction applied to decoding of rank-metric and subspace codes
• Coding and Cryptography
• Improved power decoding of interleaved one-point Hermitian codes
• Fast Kötter-Nielsen-Høholdt interpolation over skew polynomial rings and its application in coding theory

This page was built for publication: Decoding interleaved Gabidulin codes using Alekhnovich's algorithm

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