Linearized Reed–Solomon (LRS) codes are sum-rank-metric codes that generalize both Reed–Solomon and Gabidulin codes. We study vertically and horizontallyinterleavedLRS (VILRS and HILRS) codes whose codewords consist of a fixed number of stacked or concatenated codewords of a chosen LRS code, respectively. Our unified presentation of results for horizontalandvertical interleaving is novel and simplifies the recognition of resembling patterns. This paper’s main results are syndrome-based decoders for both VILRS and HILRS codes. We first consider an error-only setting and then present more general error-erasure decoders, which can handle full errors, row erasures, and column erasures simultaneously. Here, an erasure means that parts of either the row space or the column space of the error are already known before decoding. We incorporate this knowledge directly into Berlekamp–Massey-like key equations and thus decode all error types jointly. The presented error-only and error-erasure decoders have an average complexity inO(sn2) andÕ(sn2) in most scenarios, respectively, wheresis the interleaving order andndenotes the length of the component code. Errors of sum-rank weight τ =tF+tR+tCconsist oftFfull errors,tRrow erasures, andtCcolumn erasures. Their successful decoding can be guaranteed fortF≤ 1/2 (n−k−tR−tC), where n and k represent the length and the dimension of the component LRS code. Moreover, probabilistic decoding beyond the unique-decoding radius is possible with high probability whentF≤s/s+1 (n−k−tR−tC) holds for interleaving orders. We give an upper bound on the failure probability for probabilistic unique decoding and showcase its tightness via Monte Carlo simulations.

Abstract The sum-rank metric is a hybrid between the Hamming metric and the rank metric and suitable for error correction in multishot network coding and distributed storage as well as for the design of quantum-resistant cryptosystems. In this work, we consider the construction and decoding of folded linearized Reed–Solomon (FLRS) codes, which are shown to be maximum sum-rank distance (MSRD) for appropriate parameter choices. We derive an efficient interpolation-based decoding algorithm for FLRS codes that can be used as a list decoder or as a probabilistic unique decoder. The proposed decoding scheme can correct sum-rank errors beyond the unique decoding radius with a computational complexity that is quadratic in the length of the unfolded code. We show how the error-correction capability can be optimized for high-rate codes by an alternative choice of interpolation points. We derive a heuristic upper bound on the decoding failure probability of the probabilistic unique decoder and verify its tightness by Monte Carlo simulations. Further, we study the construction and decoding of folded skew Reed-Solomon codes in the skew metric. Up to our knowledge, FLRS codes are the first MSRD codes with different block sizes that come along with an efficient decoding algorithm.

Codes in the sum-rank metric have various applications in error control for multishot network coding, distributed storage and code-based cryptography. Linearized Reed-Solomon (LRS) codes contain Reed-Solomon and Gabidulin codes as subclasses and fulfill the Singleton-like bound in the sum-rank metric with equality. We propose the first known error-erasure decoder for LRS codes to unleash their full potential for multishot network coding by incorporating erasures into the known syndrome-based Berlekamp-Massey-like decoder. This allows to correct tFfull errors, tRrow erasures and tCcolumn erasures up to $2{t_F} + {t_R} + {t_C} \leq n - k$ in the sum-rank metric requiring at most $\mathcal{O}\left( {{n^2}} \right)$ operations in ${\mathbb{F}_{{q^m}}},$ where n is the code’s length and k its dimension. We show how the proposed decoder can be used to correct errors in the sum-subspace metric that occur in (noncoherent) multishot network coding.