Fast decoding of interleaved linearized Reed–Solomon codes and variants

Hannes Bartz; Sven Puchinger

doi:10.3934/amc.2025035

Article Contents

2026, Volume 20: 151-198. Doi: 10.3934/amc.2025035

This volume Previous Article Balanced Boolean functions with few-valued Walsh spectra parameterized by $ P(x^2+x) $ Next Article Novel CRT-based asymptotically ideal disjunctive hierarchical secret sharing scheme

Fast decoding of interleaved linearized Reed–Solomon codes and variants

Hannes Bartz^1, , and
Sven Puchinger^2,

1.
Institute of Communications and Navigation, German Aerospace Center (DLR), Wessling, Germany
2.
Hensoldt Sensors GmbH, Ulm, Germany

^*Corresponding author: Hannes Bartz
^*Corresponding author: Hannes Bartz

Received: August 2024

Revised: April 2025

Early access: July 30, 2025

Published online: July 30, 2025

Abstract / Introduction Full Text(HTML) Figure(5) / Table(1) Related Papers Cited by

Abstract

We construct $ s $-interleaved linearized Reed–Solomon (ILRS) codes and variants and propose efficient decoding schemes that can correct errors beyond the unique decoding radius in the sum-rank metric. The proposed interpolation-based scheme for ILRS codes can be used as a list decoder or as a probabilistic unique decoder that corrects errors of sum-rank up to $ t\leq\frac{ s}{ s+1}(n-k) $, where $ s $ is the interleaving order, $ n $ the length, and $ k $ the dimension of the code. Upper bounds on the list size and the decoding failure probability are given, where the latter is based on a novel Loidreau–Overbeck-like (LO-like) decoder for ILRS codes. We show how the proposed decoding schemes can be used to decode errors beyond the unique decoding radius in the skew metric by using an isometry between the sum-rank metric and the skew metric.

We generalize fast minimal approximant basis interpolation techniques to obtain efficient decoding schemes for ILRS codes (and variants) with subquadratic complexity in the code length.

Up to our knowledge, the presented decoding schemes are the first being able to correct errors beyond the unique decoding region in the sum-rank and skew metric. The performance of the proposed decoding schemes and the tightness of the upper bound on the decoding failure probability are validated via Monte Carlo simulations.

Keywords:

Interleaved linearized Reed–Solomon codes,
sum-rank metric,
skew metric,
interpolation-based decoding,
interleaving,
minimal approximant bases.

Mathematics Subject Classification: Primary: 94B35, 94B05.

Citation:

Full Text(HTML)

Figure 1. Illustration of the structure of a codeword matrix from an ILRS code

Download: Full-size image PowerPoint slide

Figure 2. Illustration of the transformed received matrices $ \tilde{ \boldsymbol{R}}^{(i)} = \boldsymbol{R}^{(i)} \boldsymbol{D}^{(i)} $. The red part is corrupted by an error of rank $ t_i $, whereas the green part corresponds to the last (rightmost) $ n_i-t_i $ columns of the transformed codeword matrix $ \tilde{ \boldsymbol{C}}( \boldsymbol{f})^{(i)} = \boldsymbol{C}^{(i)}( \boldsymbol{f}) \boldsymbol{D}^{(i)} $ that is obtained by evaluating $ \boldsymbol{f} $ at the transformed code locators $ \boldsymbol{\beta}^{(i)} \boldsymbol{D}^{(i)} $

Download: Full-size image PowerPoint slide

Figure 3. Qualitative illustration of the transformed received matrix $ \tilde{\boldsymbol{R}} $. The red parts correspond to the corrupted columns whereas the green parts correspond to the non-corrupted columns

Download: Full-size image PowerPoint slide

Figure 4. Normalized decoding radius $ \tau $ of ILRS codes over the code rate $ R $ for interleaving orders $ s\in\{2,5,10\} $

Download: Full-size image PowerPoint slide

Figure 5. Result of a Monte Carlo simulation of the code $ \text{ILRS}[{ \boldsymbol{\beta}, \boldsymbol{a}, \ell = 2, s = 4;n = 8,k = 3}] $ over $ \mathbb{F}_{3^4} $ transmitted over a sum-rank error channel with overall $ t\in\{3,4\} $

Download: Full-size image PowerPoint slide

Table 1. Overview of new decoding regions. Parameters: code length $ n $, interleaving order $ s $ (usually $ s \ll n $), error weight (in resp. metric) $ t $, and $ t_{\max} : = \frac{ s}{ s+1}(n-k) $. $ \mathcal{M}({n}) $ is the cost (in operations in $ \mathbb{F}_{q^m} $) of multiplying two skew polynomials of degree at most $ n $, and $ \omega $ is the matrix multiplication exponent. For the complexity, the lowest of the referenced decoding algorithms is always given

Code/Decoder	Metric	Decoding Region	Complexity	Reference(s)

LRS Codes unique decoder	sum-rank	$ t<\frac{1}{2}(n\!-\!k\!+\!1) $	$ \widetilde{O}({\mathcal{M}({n})}) $	[8,12,49]
ILRS Codes list decoder	sum-rank	$ t<\frac{ s}{ s+1}(n\!-\!k\!+\!1) $	$ \widetilde{O}({ s^\omega\mathcal{M}({n})}) $	Thm. 3.10 Sec. 3.4.3
ILRS Codes prob. unique	sum-rank	$ t\leq\frac{ s}{ s+1}(n\!-\!k) $	$ \widetilde{O}({ s^\omega\mathcal{M}({n})}) $	Thm. 3.4 & 3.16 Sec. 3.3 & 3.4.4

SRS Codes unique decoder	skew	$ t<\frac{1}{2}(n\!-\!k\!+\!1) $	$O({n^2})$	[7,49]
ISRS Codes list decoder	skew	$ t<\frac{ s}{ s+1}(n\!-\!k\!+\!1) $	$\widetilde{O}({ s^\omega\mathcal{M}({n})})$	Thm. 3.10, Prop. 3.17, Sec. 3.6
ISRS Codes prob. unique	skew	$ t\leq\frac{ s}{ s+1}(n\!-\!k) $	$\widetilde{O}({ s^\omega\mathcal{M}({n})})$	Thm. 3.4 & 3.16, Prop. 3.17, Sec. 3.6

| Show Table

DownLoad: CSV

Related Papers

Cited by

References

[1]	W. W. Adams and P. Loustaunau, An Introduction to Gröbner Bases, Grad. Stud. Math., 3, American Mathematical Society, Providence, RI, 1994. doi: 10.1090/gsm/003.
[2]	H. Bartz, Algebraic Decoding of Subspace and Rank-Metric Codes, PhD thesis, Technische Universität München, 2017.
[3]	H. Bartz, T. Jerkovits, S. Puchinger and J. Rosenkilde, Fast decoding of codes in the rank, subspace, and sum-rank metric, IEEE Transactions on Information Theory, 67 (2021), 5026-5050.
[4]	H. Bartz, T. Jerkovits, S. Puchinger and J. Rosenkilde, Fast root finding for interpolation-based decoding of interleaved gabidulin codes, in 2019 IEEE Information Theory Workshop (ITW), IEEE, 2019, 1-5. doi: 10.1109/ITW44776.2019.8989290.
[5]	H. Bartz, T. Jerkovits and J. Rosenkilde, Fast Kötter–Nielsen–Høholdt interpolation over skew polynomial rings, its application in coding theory, IFAC-PapersOnLine, 55 2022), 1-6. doi: 10.1016/j.ifacol.2022.11.019.
[6]	D. Bleichenbacher, A. Kiayias and M. Yung, Decoding of interleaved Reed–Solomon codes over noisy data, in International Colloquium on Automata, Languages, and Programming, Springer, 2719 (2003), 97-108. doi: 10.1007/3-540-45061-0_9.
[7]	D. Boucher, An algorithm for decoding skew Reed–Solomon codes with respect to the skew metric, Workshop on Coding and Cryptography, 88 (2020), 1991-2005. doi: 10.1007/s10623-020-00789-w.
[8]	D. Boucher and F. Ulmer, Linear codes using skew polynomials with automorphisms and derivations, Designs, Codes and Cryptography, 70 (2014), 405-431. doi: 10.1007/s10623-012-9704-4.
[9]	A. Brown, L. Minder and A. Shokrollahi, Probabilistic decoding of interleaved RS-codes on the q-ary symmetric channel, in IEEE International Symposium on Information Theory (ISIT), 2004,326-326.
[10]	A. Brown, L. Minder and A. Shokrollahi, Improved decoding of interleaved AG codes, in IMA International Conference on Cryptography and Coding, Springer, 3796 (2005), 37-46. doi: 10.1007/11586821_3.
[11]	E. Byrne, H. Gluesing-Luerssen and A. Ravagnani, Fundamental properties of sum-rank-metric codes, IEEE Transactions on Information Theory, 67 (2021), 6456-6475.
[12]	X. Caruso, Residues of skew rational functions and linearized Goppa codes, arXiv preprint, arXiv: 1908.08430.
[13]	X. Caruso and J. Le Borgne, A new faster algorithm for factoring skew polynomials over finite fields, Journal of Symbolic Computation, 79 (2017), 411-443. doi: 10.1016/j.jsc.2016.02.016.
[14]	X. Caruso and J. Le Borgne, Fast multiplication for skew polynomials, ISSAC'17-Proceedings of the 2017 ACM International Symposium on Symbolic and Algebraic Computation, Association for Computing Machinery (ACM), New York, 2017, 77-84.
[15]	H. Cohn and N. Heninger, Approximate common divisors via lattices, The Open Book Series, 1 (2013), 271-293. doi: 10.2140/obs.2013.1.271.
[16]	D. Coppersmith and M. Sudan, Reconstructing curves in three (and higher) dimensional space from noisy data, in ACM Symposium on the Theory of Computing, 2003,136-142.
[17]	J.-M. Couveignes and R. Lercier, Elliptic periods for finite fields, Finite Fields and Their Applications, 15 (2009), 1-22. doi: 10.1016/j.ffa.2008.07.004.
[18]	T. Cover, Enumerative source encoding, IEEE Transactions on Information Theory, 19 (1973), 73-77. doi: 10.1109/TIT.1973.1054929.
[19]	E. M. Gabidulin, Theory of codes with maximum rank distance, Probl. Inf. Transm., 21 (1985), 3-16.
[20]	H. Gluesing-Luerssen, Introduction to skew-polynomial rings and skew-cyclic codes, in Concise Encyclopedia of Coding Theory, CRC Press, Boca Raton, FL, 2021,151-180.
[21]	F. Hörmann and H. Bartz, Fast Gao-like decoding of horizontally interleaved linearized Reed–Solomon codes, Lecture Notes in Computer Science, 14311 (2023), 14-34. doi: 10.1007/978-3-031-46495-9_2.
[22]	F. Hörmann and H. Bartz, Interpolation-based decoding of folded variants of linearized and skew Reed–Solomon codes, Designs, Codes and Cryptography, 92 (2024), 553-586. doi: 10.1007/s10623-023-01214-8.
[23]	F. Hörmann and H. Bartz, Syndrome-based error-erasure decoding of interleaved linearized Reed–Solomon codes, Submitted to: IEEE Transactions on Information Theory, arXiv: 2411.19101.
[24]	F. Hörmann and H. Bartz, Efficient decoding of folded linearized Reed–Solomon codes in the Sum-Rank metric, in International Workshop on Coding and Cryptography (WCC), 2022.
[25]	F. Hörmann, H. Bartz and A.-L. Horlemann, Security considerations for McEliece-like cryptosystems based on linearized Reed-Solomon codes in the sum-rank metric, International Workshop on Code-Based Cryptography (CBCrypto).
[26]	T. Jerkovits, F. Hörmann and H. Bartz, On decoding high-order interleaved sum-rank- and skew-metric codes, International Workshop on Code-Based Cryptography (CBCrypto).
[27]	W. K. Kadir and C. Li, On decoding additive generalized twisted Gabidulin codes, Cryptography and Communications, 12 (2020), 987-1009. doi: 10.1007/s12095-020-00449-9.
[28]	W. K. Kadir, C. Li and F. Zullo, On interpolation-based decoding of a class of maximum rank distance codes, in 2021 IEEE International Symposium on Information Theory (ISIT), IEEE, 2021, 31-36.
[29]	W. K. Kadir, C. Li and F. Zullo, Encoding and decoding of several optimal rank metric codes, Cryptography and Communications, 14 (2022), 1281-1300. doi: 10.1007/s12095-022-00578-3.
[30]	S. Kampf, Bounds on collaborative decoding of interleaved hermitian codes and virtual extension, Designs, Codes and Cryptography, 70 (2014), 9-25. doi: 10.1007/s10623-012-9625-2.
[31]	R. Koetter and F. R. Kschischang, Coding for errors and erasures in random network coding, IEEE Transactions on Information Theory, 54 (2008), 3579-3591. doi: 10.1109/TIT.2008.926449.
[32]	V. Y. Krachkovsky and Y. X. Lee, Decoding for iterative Reed–Solomon coding schemes, IEEE Transactions on Magnetics, 33 (1997), 2740-2742. doi: 10.1109/20.617715.
[33]	V. Y. Krachkovsky and Y. X. Lee, Decoding of parallel Reed–Solomon codes with applications to product and concatenated codes, in IEEE ISIT, 1998.
[34]	T.-Y. Lam, A general theory of Vandermonde matrices, Exposition. Math., 4 (1986), 193-215.
[35]	T.-Y. Lam and A. Leroy, Vandermonde and Wronskian matrices over division rings, Journal of Algebra, 119 (1988), 308-336. doi: 10.1016/0021-8693(88)90063-4.
[36]	F. Le Gall, Powers of tensors and fast matrix multiplication, in International Symposium on Symbolic and Algebraic Computation (ISSAC), 2014,296-303.
[37]	A. Leroy et al., Pseudolinear transformations and evaluation in Ore extensions, Bulletin of the Belgian Mathematical Society-Simon Stevin, 2 (1995), 321-347. doi: 10.36045/bbms/1103408724.
[38]	C. Li, Interpolation-based decoding of nonlinear maximum rank distance codes, in 2019 IEEE International Symposium on Information Theory (ISIT), IEEE, 2019, 2054-2058.
[39]	S. Liu, F. Manganiello and F. R. Kschischang, Kötter interpolation in skew polynomial rings, Designs, Codes and Cryptography, 72 (2014), 593-608. doi: 10.1007/s10623-012-9784-1.
[40]	S. Liu, F. Manganiello and F. R. Kschischang, Construction and decoding of generalized skew-evaluation codes, in 2015 IEEE 14th Canadian Workshop on Information Theory (CWIT), IEEE, 2015, 9-13.
[41]	P. Loidreau and R. Overbeck, Decoding rank errors beyond the error-correction capability, International Workshop on Algebraic and Combinatorial Coding Theory (ACCT).
[42]	H.-f. Lu and P. V. Kumar, A unified construction of space-time codes with optimal rate-diversity tradeoff, IEEE Transactions on Information Theory, 51 (2005), 1709-1730. doi: 10.1109/TIT.2005.846403.
[43]	U. Martínez-Peñas, On the similarities between generalized rank and Hamming weights and their applications to network coding, IEEE Transactions on Information Theory, 62 (2016), 4081-4095. doi: 10.1109/TIT.2016.2570238.
[44]	U. Martínez-Peñas, Skew and linearized Reed–Solomon codes and maximum sum rank distance codes over any division ring, Journal of Algebra, 504 (2018), 587-612. doi: 10.1016/j.jalgebra.2018.02.005.
[45]	U. Martínez-Peñas, Private information retrieval from locally repairable databases with colluding servers, in IEEE International Symposium on Information Theory (ISIT), IEEE, 2019, 1057-1061.
[46]	U. Martínez-Peñas, Sum-rank BCH codes and cyclic-skew-cyclic codes, IEEE Transactions on Information Theory, 67 (2021), 5149-5167. doi: 10.1109/TIT.2021.3088712.
[47]	U. Martínez-Peñas, A general family of MSRD codes and PMDS codes with smaller field sizes from extended Moore matrices, SIAM Journal on Discrete Mathematics, 36 (2022), 1868-1886. doi: 10.1137/20M1386001.
[48]	U. Martínez-Peñas, Doubly and triply extended MSRD codes, Finite Fields and Their Applications, 91 (2023), 102272. doi: 10.1016/j.ffa.2023.102272.
[49]	U. Martínez-Peñas and F. R. Kschischang, Reliable and secure multishot network coding using linearized Reed-Solomon codes, IEEE Transactions on Information Theory, 65 (2019), 4785-4803. doi: 10.1109/TIT.2019.2912165.
[50]	U. Martínez-Peñas and F. R. Kschischang, Universal and dynamic locally repairable codes with maximal recoverability via Sum-Rank codes, IEEE Transactions on Information Theory.
[51]	U. Martínez-Peñas, M. Shehadeh and F. R. Kschischang, Codes in the sum-rank metric: Fundamentals and applications, Foundations and Trends in Communications and Information Theory, 19 (2022), 814-1031. doi: 10.1561/0100000120.
[52]	D. Napp, R. Pinto, J. Rosenthal and P. Vettori, MRD rank metric convolutional codes, in IEEE International Symposium on Information Theory (ISIT), IEEE, 2017, 2766-2770.
[53]	D. Napp, R. Pinto, J. Rosenthal and P. Vettori, Faster decoding of rank metric convolutional codes, in 23rd International Symposium on Mathematical Theory of Networks and Systems, 2018.
[54]	A. Neri, Twisted linearized Reed–Solomon codes: A skew polynomial framework, Journal of Algebra, 609 (2022), 792-839. doi: 10.1016/j.jalgebra.2022.06.027.
[55]	A. Neri, P. Santonastaso and F. Zullo, The geometry of one-weight codes in the sum-rank metric, Journal of Combinatorial Theory, Series A, 194 (2023), Paper No. 105703, 41 pp. doi: 10.1016/j.jcta.2022.105703.
[56]	J. S. Nielsen, Generalised multi-sequence shift-register synthesis using module minimisation, in IEEE International Symposium on Information Theory (ISIT), 2013,882-886.
[57]	R. W. Nóbrega and B. F. Uchôa-Filho, Multishot codes for network coding using rank-metric codes, in 2010 Third IEEE International Workshop on Wireless Network Coding, IEEE, 2010, 1-6.
[58]	O. Ore, On a special class of polynomials, Transactions of the American Mathematical Society, 35 (1933), 559-584. doi: 10.1090/S0002-9947-1933-1501703-0.
[59]	O. Ore, Theory of non-commutative polynomials, Annals of Mathematics, 34 (1933), 480-508.
[60]	R. Overbeck, Public key cryptography based on coding theory, PhD thesis, Technische Universität, 2007.
[61]	R. Overbeck, Structural attacks for public key cryptosystems based on Gabidulin codes, Journal of Cryptology, 21 (2008), 280-301. doi: 10.1007/s00145-007-9003-9.
[62]	F. Parvaresh, Algebraic list-decoding of error-correcting codes, PhD thesis, University of California, San Diego, 2007.
[63]	F. Parvaresh and A. Vardy, Multivariate interpolation decoding beyond the Guruswami–Sudan radius, in Allerton Conference on Communication, Control and Computing, 2004.
[64]	S. Puchinger, S. Müelich, D. Mödinger, J. Rosenkilde né Nielsen and M. Bossert, Decoding interleaved Gabidulin codes using Alekhnovich's algorithm, Electronic Notes in Discrete Mathematics, 57 (2017), 175-180. doi: 10.1016/j.endm.2017.02.029.
[65]	S. Puchinger, J. Renner and J. Rosenkilde, Generic decoding in the sum-rank metric, IEEE Transactions on Information Theory, 68 (2022), 5075-5097. doi: 10.1109/TIT.2022.3167629.
[66]	S. Puchinger and J. Rosenkilde, Bounds on list decoding of linearized Reed–Solomon codes, in 2021 IEEE International Symposium on Information Theory (ISIT), IEEE, 2021,154-159.
[67]	S. Puchinger, J. Rosenkilde and I. Bouw, Improved power decoding of interleaved one-point hermitian codes, Designs, Codes and Cryptography, 87 (2019), 589-607. doi: 10.1007/s10623-018-0577-z.
[68]	S. Puchinger and J. Rosenkilde né Nielsen, Decoding of interleaved Reed–Solomon codes using improved power decoding, in IEEE International Symposium on Information Theory (ISIT), 2017.
[69]	S. Puchinger, J. Rosenkilde né Nielsen, W. Li and V. Sidorenko, Row reduction applied to decoding of rank-metric and subspace codes, Designs, Codes and Cryptography, 82 (2017), 389-409. doi: 10.1007/s10623-016-0257-9.
[70]	S. Puchinger and A. Wachter-Zeh, Fast operations on linearized polynomials and their applications in coding theory, Journal of Symbolic Computation, 89 (2018), 194-215. doi: 10.1016/j.jsc.2017.11.012.
[71]	I. S. Reed and G. Solomon, Polynomial codes over certain finite fields, Journal of the Society for Industrial and Applied Mathematics, 8 (1960), 300-304. doi: 10.1137/0108018.
[72]	P. Santonastaso and J. Sheekey, On MSRD codes, $h$-designs and disjoint maximum scattered linear sets, Journal of Combinatorial Designs, 33 (2025), 137-155. doi: 10.1002/jcd.21972.
[73]	P. Santonastaso and F. Zullo, On subspace designs, EMS Surveys in Mathematical Sciences, 11 (2024), 1-62. doi: 10.4171/emss/77.
[74]	G. Schmidt, V. Sidorenko and M. Bossert, Enhancing the correcting radius of interleaved Reed–Solomon decoding using syndrome extension techniques, in IEEE International Symposium on Information Theory (ISIT), 2007, 1341-1345.
[75]	G. Schmidt, V. R. Sidorenko and M. Bossert, Collaborative decoding of interleaved Reed–Solomon codes and concatenated code designs, IEEE Transactions on Information Theory, 55 (2009), 2991-3012. doi: 10.1109/TIT.2009.2021308.
[76]	V. Sidorenko and M. Bossert, Decoding interleaved Gabidulin codes and multisequence linearized shift-register synthesis, in IEEE International Symposium on Information Theory (ISIT), 2010, 1148-1152.
[77]	V. Sidorenko and M. Bossert, Fast skew-feedback shift-register synthesis, Designs, Codes and Cryptography, 70 (2014), 55-67. doi: 10.1007/s10623-012-9663-9.
[78]	V. Sidorenko, L. Jiang and M. Bossert, Skew-feedback shift-register synthesis and decoding interleaved Gabidulin codes, IEEE Transactions on Information Theory, 57 (2011), 621-632. doi: 10.1109/TIT.2010.2096032.
[79]	A. Wachter, V. R. Sidorenko, M. Bossert and V. V. Zyablov, On (partial) unit memory codes based on Gabidulin codes, Problems of Information Transmission, 47 (2011), 117-129. doi: 10.1134/S0032946011020049.
[80]	A. Wachter-Zeh, Bounds on list decoding of rank-metric codes, IEEE Trans. Inform. Theory, 59 (2013), 7268-7277. doi: 10.1109/TIT.2013.2274653.
[81]	A. Wachter-Zeh, Decoding of block and convolutional codes in rank metric, PhD thesis, Ulm University and Université Rennes 1, 2013.
[82]	A. Wachter-Zeh and V. Sidorenko, Rank-metric convolutional codes for random linear network coding, in 2012 International Symposium on Network Coding (NetCod), IEEE, 2012, 1-6.
[83]	A. Wachter-Zeh, M. Stinner and V. Sidorenko, Convolutional codes in rank metric with application to random network coding, IEEE Transactions on Information Theory, 61 (2015), 3199-3213. doi: 10.1109/TIT.2015.2424930.
[84]	A. Wachter-Zeh and A. Zeh, List and unique error-erasure decoding of interleaved Gabidulin codes with interpolation techniques, Designs, Codes and Cryptography, 73 (2014), 547-570. doi: 10.1007/s10623-014-9953-5.
[85]	A. Wachter-Zeh, A. Zeh and M. Bossert, Decoding interleaved Reed–Solomon codes beyond their joint error-correcting capability, Designs, Codes and Cryptography, 71 (2014), 261-281. doi: 10.1007/s10623-012-9728-9.
[86]	J.-H. Yu and H.-A. Loeliger, Simultaneous partial inverses and decoding interleaved Reed–Solomon codes, IEEE Transactions on Information Theory, 64 (2018), 7511-7528.