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.

The sum-rank metric generalizes the Hamming and rank metric by partitioning vectors into blocks and defining the total weight as the sum of the rank weights of these blocks, based on their matrix representation. In this work, we explore support-guessing algorithms for decoding sum-rank-metric codes. Support-guessing involves randomly selecting candidate supports and attempting to decode the error under the assumption that it is confined to these supports. While previous works have focused on worst-case scenarios, we analyze the average case and derive an optimal support-guessing distribution in the asymptotic regime. We show that this distribution also performs well for finite code lengths. Our analysis provides exact complexity estimates for unique decoding scenarios and establishes tighter bounds beyond the unique decoding radius. Additionally, we introduce a randomized decoding algorithm for linearized Reed–Solomon codes. This algorithm extends decoding capabilities beyond the unique decoding radius by leveraging an efficient error-and-erasure decoder. Instead of requiring the entire error support to be confined to the guessed support, the algorithm succeeds as long as there is sufficient overlap between the guessed support and the actual error support. As a result, the proposed method improves the success probability and reduces computational complexity compared to generic decoding algorithms. Our contributions offer more accurate complexity estimates than previous works and clarify how support-guessing methods behave under different assumptions on the code class, rank profile, and decoding radius. These estimates provide a codingtheoretic basis for future work on decoding algorithms and applications of the sum-rank metric.

Abstract Skew polynomials are a class of non-commutative polynomials that have several applications in computer science, coding theory and cryptography. In particular, skew polynomials can be used to construct and decode evaluation codes in several metrics, like e.g. the Hamming, rank, sum-rank and skew metric. We propose a fast divide-and-conquer variant of Kötter–Nielsen–Høholdt (KNH) interpolation algorithm: it inputs a list of linear functionals on skew polynomial vectors, and outputs a reduced Gröbner basis of their kernel intersection. We show, that the proposed KNH interpolation can be used to solve the interpolation step of interpolation-based decoding of interleaved Gabidulin codes in the rank-metric, linearized Reed–Solomon codes in the sum-rank metric and skew Reed–Solomon codes in the skew metric requiring at most $${\widetilde{O}}\left( s^\omega {\mathfrak {M}}(n)\right) $$ O ~ s ω M ( n ) operations in $${\mathbb {F}}_{q^m}$$ F q m , where n is the length of the code, $$s$$ s the interleaving order, $${\mathfrak {M}}(n)$$ M ( n ) the complexity for multiplying two skew polynomials of degree at most n, $$\omega $$ ω the matrix multiplication exponent and $${\widetilde{O}}\left( \cdot \right) $$ O ~ · the soft-O notation which neglects log factors. This matches the previous best speeds for these tasks, which were obtained by top–down minimal approximant bases techniques, and complements the theory of efficient interpolation over free skew polynomial modules by the bottom-up KNH approach. In contrast to the top–down approach the bottom-up KNH algorithm has no requirements on the interpolation points and thus does not require any pre-processing.

Abstract Martínez-Peñas and Kschischang (IEEE Trans. Inf. Theory 65(8):4785–4803, 2019) proposed lifted linearized Reed–Solomon codes as suitable codes for error control in multishot network coding. We show how to construct and decode lifted interleaved linearized Reed–Solomon (LILRS) codes. Compared to the construction by Martínez-Peñas–Kschischang, interleaving allows to increase the decoding region significantly and decreases the overhead due to the lifting (i.e., increases the code rate), at the cost of an increased packet size. We propose two decoding schemes for LILRS that are both capable of correcting insertions and deletions beyond half the minimum distance of the code by either allowing a list or a small decoding failure probability. We propose a probabilistic unique Loidreau–Overbeck-like decoder for LILRS codes and an efficient interpolation-based decoding scheme that can be either used as a list decoder (with exponential worst-case list size) or as a probabilistic unique decoder. We derive upper bounds on the decoding failure probability of the probabilistic-unique decoders which show that the decoding failure probability is very small for most channel realizations up to the maximal decoding radius. The tightness of the bounds is verified by 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.

Most low-density parity-check (LDPC) code constructions are considered over finite fields. In this work, we focus on regular LDPC codes over integer residue rings and analyze their performance with respect to the Lee metric. Their error-correction performance is studied over two channel models, in the Lee metric. The first channel model is a discrete memoryless channel, whereas in the second channel model an error vector is drawn uniformly at random from all vectors of a fixed Lee weight. It is known that the two channel laws coincide in the asymptotic regime, meaning that their marginal distributions match. For both channel models, we derive upper bounds on the block error probability in terms of a random coding union bound as well as sphere packing bounds that make use of the marginal distribution of the considered channels. We estimate the decoding error probability of regular LDPC code ensembles over the channels using the marginal distribution and determining the expected Lee weight distribution of a random LDPC code over a finite integer ring. By means of density evolution and finite-length simulations, we estimate the error-correction performance of selected LDPC code ensembles under belief propagation decoding and a low-complexity symbol message passing decoding algorithm and compare the performances. The analysis developed in this paper may serve to design regular low-density parity-check (LDPC) codes over integer residue rings for storage and cryptographic application.

In this paper we address the problem of decoding linearized Reed–Solomon (LRS) codes beyond their unique decoding radius. We analyze the complexity in order to evaluate if the considered problem is of cryptographic relevance, i.e., can be used to design cryptosystems that are computationally hard to break. We show that our proposed algorithm improves over other generic algorithms that do not take into account the underlying code structure.

We study the performance of nonbinary low-density parity-check (LDPC) codes over finite integer rings over two channels that arise from the Lee metric. The first channel is a discrete memory-less channel (DMC) matched to the Lee metric. The second channel adds to each codeword an error vector of constant Lee weight, where the error vector is picked uniformly at random from the set of vectors of constant Lee weight. It is shown that the marginal conditional distributions of the two channels coincide, in the limit of large block length. Random coding union bounds on the block error probability are derived for both channels. Moreover, the performance of selected LDPC code ensembles is analyzed by means of density evolution and finite-length simulations, with belief propagation decoding and with a low-complexity symbol message passing algorithm and it is compared to the derived bounds.

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.

Recently, Martínez-Peñas and Kschischang (IEEE Trans. Inf. Theory, 2019) showed that lifted linearized Reed-Solomon codes are suitable codes for error control in multishot network coding. We show how to construct and decode lifted interleaved linearized Reed-Solomon codes. Compared to the construction by Martínez-Peñas-Kschischang, interleaving allows to increase the decoding region significantly (especially w.r.t. the number of insertions) and decreases the overhead due to the lifting (i.e., increases the code rate), at the cost of an increased packet size. The proposed decoder is a list decoder that can also be interpreted as a probabilistic unique decoder. Although our best upper bound on the list size is exponential, we present a heuristic argument and simulation results that indicate that the list size is in fact one for most channel realizations up to the maximal decoding radius.

We speed up existing decoding algorithms for three code classes in different metrics: interleaved Gabidulin codes in the rank metric, lifted interleaved Gabidulin codes in the subspace metric, and linearized Reed-Solomon codes in the sum-rank metric. The speed-ups are achieved by new algorithms that reduce the cores of the underlying computational problems of the decoders to one common tool: computing left and right approximant bases of matrices over skew polynomial rings. To accomplish this, we describe a skew-analogue of the existing PM-Basis algorithm for matrices over ordinary polynomials. This captures the bulk of the work in multiplication of skew polynomials, and the complexity benefit comes from existing algorithms performing this faster than in classical quadratic complexity. The new algorithms for the various decoding-related computational problems are interesting in their own and have further applications, in particular parts of decoders of several other codes and foundational problems related to the remainder-evaluation of skew polynomials.

We show that the root-finding step in interpolation-based decoding of interleaved Gabidulin codes can be solved by finding a so-called minimal approximant basis of a matrix over a linearized polynomial ring. Based on existing fast algorithms for computing such bases over ordinary polynomial rings, we develop fast algorithms for computing them over linearized polynomials. As a result, root finding costs O~(ℓωM(n)) operations in Fqm, where ℓ is the interleaving degree, n the code length, Fqm the base field of the code, 2 ≤ ω ≤ 3 the matrix multiplication exponent, and M(n) ∈ O(n1.635) is the complexity of multiplying two linearized polynomials of degree at most n. This is an asymptotic improvement upon the previously fastest algorithm of complexity O(ℓ3n2), in some cases O(ℓ2n2).

We consider subspace codes obtained by lifting L-interleaved [n, k] Gabidulin codes. When used in networks with random linear coding, these codes are able to correct with high probability γ packet insertions and δ packet deletions provided that γ/L + δ ≤ n - k. We propose to use these subspace codes in the so called fountain mode. In this case we do not need to correct deletions and are able to correct with high probability a large number L(n - k) of packet insertions. We present a simplified decoder correcting insertions only.

A new class of folded subspace codes for noncoherent network coding is presented. The codes can correct insertions and deletions beyond the unique decoding radius for any code rate R ∈ [0, 1]. An efficient interpolation-based decoding algorithm for this code construction is given which allows to correct insertions and deletions up to the normalized radius s (1 - ((1/h + h)/(h - s + 1))R), where h is the folding parameter and s ≤ h is a decoding parameter. The algorithm serves as a list decoder or as a probabilistic unique decoder that outputs a unique solution with high probability. An upper bound on the average list size of (folded) subspace codes and on the decoding failure probability is derived. A major benefit of the decoding scheme is that it enables probabilistic unique decoding up to the list decoding radius.

Network coding allows nodes in a network to combine different packets using linear operations. In most instances, the encoding coefficients are chosen randomly and placed in the packet header. The ability to correct errors and erasures is critical, because a single malicious packet injected by a misbehaving node or the deletion of a single packet can corrupt multiple packets and jeopardize the entire information flow. Building on Rotter and Kschischang's theoretical work on subspace network codes, we propose a practical network coding protocol with in-built resilience against faults and active attacks. Also included is a low-complexity extended code construction for high-rate subspace Reed-Solomon like codes. The code maintains the distance properties that are key for error and erasure correction. Performance results show that throughput gains can be achieved with lower complexity and smaller field sizes.