We study the performance of 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 add
s 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 distribution of the two channels coincides, in the limit of large blocklengths. 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.
Recently, Martinez-Penas 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 lineari
zed Reed-Solomon codes. Compared to the construction by Martinez-Penas-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.
A new protograph-based framework for message passing (MP) decoding of low density parity-check (LDPC) codes with Hamming weight amplifiers (HWAs), which are used e.g. in the NIST post-quantum crypto candidate LEDAcrypt, is proposed. The scheme exploi
ts the correlations in the error patterns introduced by the HWA using a turbo-like decoding approach where messages between the decoders for the outer code given by the HWA and the inner LDPC code are exchanged. Decoding thresholds for the proposed scheme are computed using density evolution (DE) analysis for belief propagation (BP) and ternary message passing (TMP) decoding and compared to existing decoding approaches. The proposed scheme improves upon the basic approach of decoding LDPC code from the amplified error and has a similar performance as decoding the corresponding moderate-density parity-check (MDPC) code but with a significantly lower computational complexity.
We address the problem of decoding Gabidulin codes beyond their unique error-correction radius. The complexity of this problem is of importance to assess the security of some rank-metric code-based cryptosystems. We propose an approach that introduce
s row or column erasures to decrease the rank of the error in order to use any proper polynomial-time Gabidulin code error-erasure decoding algorithm. This approach improves on generic rank-metric decoders by an exponential factor.
An efficient decoding algorithm for horizontally u-interleaved LRPC codes is proposed and analyzed. Upper bounds on the decoding failure rate and the computational complexity of the algorithm are derived. It is shown that interleaving reduces the dec
oding failure rate exponentially in the interleaving order u whereas the computational complexity grows linearly.
In this paper, ensembles of quasi-cyclic moderate-density parity-check (MDPC) codes based on protographs are introduced and analyzed in the context of a McEliece-like cryptosystem. The proposed ensembles significantly improve the error correction cap
ability of the regular MDPC code ensembles that are currently considered for post-quantum cryptosystems without increasing the public key size. The proposed ensembles are analyzed in the asymptotic setting via density evolution, both under the sum-product algorithm and a low-complexity (error-and-erasure) message passing algorithm. The asymptotic analysis is complemented at finite block lengths by Monte Carlo simulations. The enhanced error correction capability remarkably improves the scheme robustness with respect to (known) decoding attacks.
Recently, it has been shown how McEliece public-key cryptosystems based on moderate-density parity-check (MDPC) codes allow for very compact keys compared to variants based on other code families. In this paper, classical (iterative) decoding schemes
for MPDC codes are considered. The algorithms are analyzed with respect to their error-correction capability as well as their resilience against a recently proposed reaction-based key-recovery attack on a variant of the MDPC-McEliece cryptosystem by Guo, Johansson and Stankovski (GJS). New message-passing decoding algorithms are presented and analyzed. Two proposed decoding algorithms have an improved error-correction performance compared to existing hard-decision decoding schemes and are resilient against the GJS reaction-based attack for an appropriate choice of the algorithms parameters. Finally, a modified belief propagation decoding algorithm that is resilient against the GJS reaction-based attack is presented.
Staircase codes play an important role as error-correcting codes in optical communications. In this paper, a low-complexity method for resolving stall patterns when decoding staircase codes is described. Stall patterns are the dominating contributor
to the error floor in the original decoding method. Our improvement is based on locating stall patterns by intersecting non-zero syndromes and flipping the corresponding bits. The approach effectively lowers the error floor and allows for a new range of block sizes to be considered for optical communications at a certain rate or, alternatively, a significantly decreased error floor for the same block size. Further, an improved error floor analysis is introduced which provides a more accurate estimation of the contributions to the error floor.
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 $Rin[0,1]$. An efficient interpolation-based decoding algorithm for t
his 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 $sleq 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.
