Search

One important innovation in information and coding theory is polar code, which delivers capacity attaining error correction performance varying code rates and block lengths. In recent times, polar codes are preferred to offer channel coding in the physical control channels of the 5G (5th Generation) wireless standard by 3GPP (Third Generation Partnership Project) New Radio (NR) group. Being a part of the physical layer, Channel coding plays key role in deciding latency and reliability of a communication system. However, the error correction performance degrades with decreased message lengths. 5G NR requires channel codes with low rates, very low error floors with short message lengths and low latency in coding process. In this work, Distributed Cyclic Redundancy Check Aided polar (DCA-polar) code along with Cyclic Redundancy Check Aided polar (CA-polar) code, the two variant of polar codes have been proposed which provide significant error-correction performance in the regime of short block lengths and enable early termination of decoding processes. While CRC bits improve the performance of SCL (successive cancellation list) decoding by increasing distance properties, distributed CRC bits permit path trimming and early-termination of the decoding process. The design can reduce the decoding latency and energy consumption of hardware, which is crucial for mobile applications like 5G. The work also considers the performance analysis of NR polar codes over AWGN (Additive White Gaussian Noise) for short information block lengths at low code rates in the uplink and downlink control channels using SNR (Signal to Noise Ratio) and FAR (False Alarm Rate) as the performance measures. Simulation results illustrate different trade-offs between error-correction and detection performances comparing proposed NR polar coding schemes. [ABSTRACT FROM AUTHOR]

This paper studies the cardinality of codes correcting insertions and deletions. We give improved upper and lower bounds on code size. Our upper bound is obtained by utilizing the asymmetric property of list decoding for insertions and deletions and can be seen as analogous to the Elias bound in the Hamming metric. Our non-asymptotic bound is better than the existing bounds when the minimum Levenshtein distance is relatively large. The asymptotic bound exceeds the Elias and the MRRW bounds adapted from the Hamming-metric bounds for the binary and the quaternary cases. Our lower bound improves on the bound by Levenshtein, but its effect is limited and vanishes asymptotically. [ABSTRACT FROM AUTHOR]

We show new and improved list decoding properties of folded Reed--Solomon (RS) codes and multiplicity codes. Both of these families of codes are based on polynomials over finite fields, and both have been the source of recent advances in coding theory: folded RS codes were the first known explicit construction of capacity-achieving list decodable codes [V. Guruswami and A. Rudra, IEEE Trans. Inform. Theory, 54 (2008), pp. 135--150], and multiplicity codes were the first construction of high-rate locally decodable codes [S. Kopparty, S. Saraf, and S. Yekhanin, J. ACM, 61 (2014), 28]. In this work, we show that folded RS codes and multiplicity codes are in fact better than previously known in the context of list decoding and local list decoding. Our first main result shows that folded RS codes achieve list decoding capacity with constant list sizes, independent of the block length. Prior work with constant list sizes first obtained list sizes that are polynomial in the block length and relied on pre-encoding with subspace evasive sets to reduce the list sizes to a constant [V. Guruswami and C. Wang, IEEE Trans. Inform. Theory, 59 (2013), pp. 3257--3268], [Z. Dvir and S. Lovett, Proc. 44th STOC, ACM, 2012, 351--358]. The list size we obtain is (1/\varepsilon)O(1/\varepsilon) where \varepsilon is the gap to capacity, which matches the list size obtained by pre-encoding with subspace evasive sets. For our second main result, we observe that univariate multiplicity codes exhibit similar behavior, and we use this, together with additional ideas, to show that multivariate multiplicity codes are locally list decodable up to their minimum distance. By known reductions, this gives, in turn, capacity-achieving locally list decodable codes with query complexity exp(\~ O((logN)5/6)). This improves on the tensor-based construction of [B. Hemenway, N. Ron-Zewi, and M. Wootters, SIAM J. Comput., 49 (2019), pp. 157--195], which gave capacity-achieving locally list decodable codes of query complexity N \~ O(1/\mathrm{l}\mathrm{o}\mathrm{g} \mathrm{l}\mathrm{o}\mathrm{g}N), and is close to the best known query complexity of exp(\~ O(\surd logN)) for high-rate locally (uniquely) decodable codes [S. Kopparty et al., J. ACM, 64 (2017), 11]. [ABSTRACT FROM AUTHOR]

An improved Singleton-type upper bound is presented for the list decoding radius of linear codes, in terms of the code parameters $[n,k,d]$ and the list size $L$. $L$ -MDS codes are then defined as codes that attain this bound (under a slightly stronger notion of list decodability), with 1-MDS codes corresponding to ordinary linear MDS codes. Several properties of such codes are presented; in particular, it is shown that the 2-MDS property is preserved under duality. Finally, explicit constructions for 2-MDS codes are presented through generalized Reed–Solomon (GRS) codes. [ABSTRACT FROM AUTHOR]

The successive cancellation (SC) process in which symbols are decoded sequentially by processing some intermediate information is an essential component of various decoding algorithms used for polar codes and their variants. In some decoding schemes, we may need to redo this process from some specific symbol or from the first symbol. This operation is called rewinding. Rewinding the SC process seems trivial if we have access to all intermediate log-likelihood ratios (LLRs) and partial sums. However, as the block length increases, retaining all of the intermediate information becomes inefficient and impractical. Rewinding the SC process in a memory-efficient way is a problem that we address in this paper. As we store a fraction of all the intermediate information in the memory-efficient scheme, we may not be able to rewind the SC process to the target symbol index. The reason is that some of the stored intermediate information needed to decode the target symbol may have been overwritten. To recompute the lost information, we may need to rewind the process further. Before proposing the formal scheme for the rewinding process, we explore the known properties of the SC process based on the binary representation of the bit indices. Then, we introduce a new operator used for grouping the bit indices. This special grouping helps us in finding the closest bit index to the target index for rewinding. We also analytically prove that this approach gives access to the untouched intermediate information stored in the memory which is essential in resuming the SC process. Finally, we adapt the proposed approach to multiple rewinds and apply it to SC-flip decoding and shifted-pruning-based list decoding. The numerical evaluation of the proposed solution shows a significant reduction of ≥50% in the complexity of the additional decoding attempts at medium and high SNR regimes for SC-flip decoding and less for shifted-pruning based list decoding. [ABSTRACT FROM AUTHOR]

Polar codes are one of the most recent additions to the family of forward error correction (FEC) codes, having recently been adopted in the 5G New Radio (NR) standard for the control channel. However, the stringent requirements introduced by the 5G standard in terms of block length and code rate flexibility, along with low end-to-end latency and high error correction performance represent a major challenge for their hardware implementation. In this context, we study the impact of main code and decoder design parameters on the latency, throughput, and the hardware complexity of semi-parallel decoding architectures. The impact of these parameters on the hardware efficiency of semi-parallel architectures is significant. Therefore, we propose two multi-frame decoding approaches that increase the throughput and improve the utilisation rate of the processing units of these architectures. Detailed analytical and logic synthesis results are provided and compared for a large range of values in order to constitute a reference for the implementation of flexible, yet efficient FEC decoders for polar codes.

This work presents a fast successive-cancellation list flip (Fast-SCLF) decoding algorithm for polar codes that addresses the high latency issue associated with the successive-cancellation list flip (SCLF) decoding algorithm. We first propose a bit-flipping strategy tailored to the state-of-the-art fast successive-cancellation list (FSCL) decoding that avoids tree-traversal in the binary tree representation of SCLF, thus reducing the latency of the decoding process. We then derive a parameterized path selection error model to accurately estimate the bit index at which the correct decoding path is eliminated from the initial FSCL decoding. The trainable parameter is optimized online based on an efficient supervised learning framework. Simulation results show that for a polar code of length 512 with 256 information bits, with similar error-correction performance and memory consumption, the proposed Fast-SCLF decoder reduces up to 73.4% of the average decoding latency of the SCLF decoder with the same list size at the frame error rate of 10−4, while incurring a maximum computational complexity overhead of 27.6%. For the same polar code of length 512 with 256 information bits and at practical signal-to-noise ratios, the proposed decoder with list size 4 reduces 89.3% and 43.7% of the average complexity and decoding latency of the FSCL decoder with list size 32 (FSCL-32), respectively, while also reducing 83.2% of the memory consumption of FSCL-32. The significant improvements of the proposed decoder come at the cost of 0.07 dB error-correction performance degradation compared with FSCL-32.

In the successive cancellation (SC) list decoding, the tree pruning operation retains the L best paths with respect to a metric at every decoding step. However, the correct path might be among the L worst paths due to the imposed penalties. In this case, the correct path is pruned and the decoding process fails. shifted pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by κ ≤ L paths over certain bit positions. A special case of the shifted pruning scheme where κ = L is known as SCL-flip decoding, which was independently proposed in 2019. In this work, a new metric that performs better in particular for medium and long codes is proposed, and nested shift-pruning schemes are suggested for improving the average complexity. [ABSTRACT FROM AUTHOR]

For fixed integers $n$ and $b\geq k$ , let $A(b,k,n)$ the largest size of a subset of $\{1,2,\ldots,b\}^{n}$ such that, for any $k$ distinct elements in the set, there is a coordinate where they all differ. Bounding $A(b,k,n)$ is a problem of relevant interest in information theory and computer science, relating to the zero-error capacity with list decoding and to the study of $(b, k)$ -hash families of functions. It is known that, for fixed $b$ and $k$ , $A(b,k,n)$ grows exponentially in $n$. In this paper, we determine new exponential upper bounds for different values of $b$ and $k$. A first bound on $A(b,k,n)$ for general $b$ and $k$ was derived by Fredman and Komlós in the ’80s and improved for certain $b\neq k$ by Körner and Marton and by Arikan. Only very recently better bounds were derived for general $b$ and $k$ by Guruswami and Riazanov, while stronger results for small values of $b=k$ were obtained by Arikan, by Dalai, Guruswami and Radhakrishnan, and by Costa and Dalai. In this paper, we strengthen the bounds for some specific values of $b$ and $k$. Our contribution is a new computational method for obtaining upper bounds on the values of a quadratic form defined over discrete probability distributions in arbitrary dimensions, which emerged as a central ingredient in recent works. The proposed method reduces an infinite-dimensional problem to a finite one, which we manage to further simplify by means of a series of optimality conditions. [ABSTRACT FROM AUTHOR]

Although long polar codes with successive cancellation decoding can asymptotically achieve channel capacity, the performance of short blocklength polar codes is far from optimal. Recently, Arıkan proposed employing a convolutional pre-transformation before the polarization network, called polarization-adjusted convolutional (PAC) codes. In this paper, we focus on improving the performance of short PAC codes concatenated with a cyclic redundancy check (CRC) outer code, CRC-PAC codes, since error detection capability is essential in practical applications, such as the polar coding scheme for the control channel. We propose an enhanced adaptive belief propagation (ABP) decoding algorithm with the assistance of CRC bits for PAC codes. We also derive joint parity-check matrices of CRC-PAC codes suitable for iterative BP decoding. The proposed CRC-aided ABP (CA-ABP) decoding can effectively improve error performance when partial CRC bits are used in the decoding. Meanwhile, the error detection ability can still be guaranteed by the remaining CRC bits and adaptive decoding parameters. Moreover, compared with the conventional CRC-aided list (CA-List) decoding, our proposed scheme can significantly reduce computational complexity, to achieve a better trade-off between the performance and complexity for short PAC codes. [ABSTRACT FROM AUTHOR]

We propose a new concept of secure list decoding, which is related to bit-string commitment. While the conventional list decoding requires that the list contains the transmitted message, secure list decoding requires the following additional security conditions to work as a modification of bit-string commitment. The first additional security condition is the receiver’s uncertainty for the transmitted message, which is stronger than the impossibility of the correct decoding, even though the transmitted message is contained in the list. The other additional security condition is the impossibility for the sender to estimate another element of the decoded list except for the transmitted message. The first condition is evaluated by the equivocation rate. The asymptotic property is evaluated by three parameters, the rates of the message and list sizes, and the equivocation rate. We derive the capacity region of this problem. We show that the combination of hash function and secure list decoding yields the conventional bit-string commitment. Our results hold even when the input and output systems are general probability spaces including continuous systems. When the input system is a general probability space, we formulate the abilities of the honest sender and the dishonest sender in a different way. [ABSTRACT FROM AUTHOR]

This paper investigates the decoding of a remarkable set of lattices: We treat in a unified framework the Leech lattice in dimension 24, the Nebe lattice in dimension 72, and the Barnes-Wall lattices. A new interesting lattice, named $L_{3\cdot 24}$ , is constructed as a simple application of the single parity check on the Leech lattice. The common aspect of these lattices is that they can be obtained via a single parity check or via the $k$ -ing construction. We exploit these constructions to introduce a new efficient paradigm for decoding. This leads to efficient list decoders and quasi-optimal decoders on the Gaussian channel. Both theoretical and practical performance (point error probability and complexity) of the new decoders are provided. [ABSTRACT FROM AUTHOR]

We revise the proof of low-rate upper bounds on the reliability function of discrete memoryless channels for ordinary and list-decoding schemes, in particular Berlekamp and Blinovsky’s zero-rate bound, as well as Blahut’s bound for low rates. The available proofs of the zero-rate bound devised by Berlekamp and Blinovsky are somehow complicated in that they contain in one form or another some “non-standard” procedures or computations. Here we follow Blinovsky’s idea of using a Ramsey-theoretic result by Komlós, and we complement it with some missing steps to present a proof which is rigorous and easier to inspect. Furthermore, we show how these techniques can be used to fix an error that invalidated the proof of Blahut’s low-rate bound, which is here presented in an extended form for list decoding and for general channels. [ABSTRACT FROM AUTHOR]

Wachter-Zeh (IEEE Trans Inf Theory 59(11):7268–7276, 2013), and later together with Raviv (IEEE Trans Inf Theory 62(4):1605–1615, 2016), proved that Gabidulin codes cannot be efficiently list decoded for any radius τ , providing that τ is large enough. Also, they proved that there are infinitely many choices of the parameters for which Gabidulin codes cannot be efficiently list decoded at all. Subsequently, in Trombetti and Zullo (IEEE Trans Inf Theory 66(9):5379–5386, 2020) these results have been extended to the family of generalized Gabidulin codes and to further family of MRD-codes. In this paper, we provide bounds on the list size of rank-metric codes containing generalized Gabidulin codes in order to determine whether or not a polynomial-time list decoding algorithm exists. We detect several families of rank-metric codes containing a generalized Gabidulin code as subcode which cannot be efficiently list decoded for any radius large enough and families of rank-metric codes which cannot be efficiently list decoded. These results suggest that rank-metric codes which are F q m -linear or that contains a (power of) generalized Gabidulin code cannot be efficiently list decoded for large values of the radius. [ABSTRACT FROM AUTHOR]

We present an explicit and efficient algebraic construction of capacity-achieving list decodable codes with both constant alphabet and constant list sizes. More specifically, for any $R \in (0,1)$ and $\epsilon >0$ , we give an algebraic construction of an infinite family of error-correcting codes of rate $R$ , over an alphabet of size $(1/\epsilon)^{O(1/\epsilon ^{2})}$ , that can be list decoded from a $(1-R-\epsilon)$ -fraction of errors with list size at most $\exp (\mathrm {poly}(1/ \epsilon))$. Moreover, the codes can be encoded in time $\mathrm {poly}(1/ \epsilon,n)$ , the output list is contained in a linear subspace of dimension at most $\mathrm {poly}(1/ \epsilon)$ , and a basis for this subspace can be found in time $\mathrm {poly}(1 /\epsilon, n)$. Thus, both encoding and list decoding can be performed in fully polynomial-time $\mathrm {poly}(1/ \epsilon,n)$ , except for pruning the subspace and outputting the final list which takes time $\exp (\mathrm {poly}(1/ \epsilon)) \cdot \mathrm {poly} (n)$. In contrast, prior explicit and efficient constructions of capacity-achieving list decodable codes either required a much higher complexity in terms of $1/ \epsilon $ (and were additionally much less structured), or had super-constant alphabet or list sizes. Our codes are quite natural and structured. Specifically, we use algebraic-geometric (AG) codes with evaluation points restricted to a subfield, and with the message space restricted to a (carefully chosen) linear subspace. Our main observation is that the output list of AG codes with subfield evaluation points is contained in an affine shift of the image of a block-triangular-Toeplitz (BTT) matrix, and that the list size can potentially be reduced to a constant by restricting the message space to a BTT evasive subspace, which is a large subspace that intersects the image of any BTT matrix in a constant number of points. We further show how to explicitly construct such BTT evasive subspaces, based on the explicit subspace designs of Guruswami and Kopparty (Combinatorica, 2016), and composition. [ABSTRACT FROM AUTHOR]

The recently introduced polar codes constitute a breakthrough in coding theory due to their capacity-achieving property. This goes hand in hand with a quasilinear construction, encoding, and successive cancellation list decoding procedures based on the Plotkin construction. The decoding algorithm can be applied with slight modifications to Reed-Muller or eBCH codes, that both achieve the capacity of erasure channels, although the list size needed for good performance grows too fast to make the decoding practical even for moderate block lengths. The key ingredient for proving the capacity-achieving property of Reed-Muller and eBCH codes is their group of symmetries. It can be plugged into the concept of Plotkin decomposition to design various permutation decoding algorithms. Although such techniques allow to outperform the straightforward polar-like decoding, the complexity stays impractical. In this paper, we show that although invariance under a large automorphism group is valuable in a theoretical sense, it also ensures that the list size needed for good performance grows exponentially. We further establish the bounds that arise if we sacrifice some of the symmetries. Although the theoretical analysis of the list decoding algorithm remains an open problem, our result provides an insight into the factors that impact the decoding complexity. [ABSTRACT FROM AUTHOR]

We consider a set of security and privacy problems under reliability and storage constraints that can be tackled by using codes and particularly focus on the secret-key agreement problem. Polar subcodes (PSCs) are polar codes (PCs) with dynamically-frozen symbols and have a larger code minimum distance than PCs with only statically-frozen symbols. A randomized nested PSC construction, where the low-rate code is a PSC and the high-rate code is a PC, is proposed for successive cancellation list (SCL) and sequential decoders. This code construction aims to perform lossy compression with side information, i.e., Wyner-Ziv (WZ) coding. Nested PSCs are used in the key agreement problem with physical identifiers and two terminals since WZ-coding constructions significantly improve on Slepian-Wolf coding constructions such as fuzzy extractors. Significant gains in terms of the secret-key vs. storage rate ratio as compared to nested PCs with the same list sizes are illustrated to show that nested PSCs significantly improve on all existing code constructions. The performance of the nested PSCs is shown to improve with larger list sizes, unlike the nested PCs considered. A design procedure to efficiently construct nested PSCs and possible improvements to the nested PSC designs are also provided. [ABSTRACT FROM AUTHOR]

We give a complete answer to the following basic question: “What is the maximal fraction of deletions or insertions tolerable by $q$ -ary list-decodable codes with non-vanishing information rate?” This question has been open even for binary codes, including the restriction to the binary insertion-only setting, where the best-known result was that a $\gamma \leq 0.707$ fraction of insertions is tolerable by some binary code family. For any desired $\varepsilon > 0$ , we construct a family of binary codes of positive rate which can be efficiently list-decoded from any combination of $\gamma $ fraction of insertions and $\delta $ fraction of deletions as long as $\gamma + 2\delta \leq 1 - \varepsilon $. On the other hand, for any $\gamma, \delta $ with $\gamma + 2\delta = 1$ list-decoding is impossible. Our result thus precisely characterizes the feasibility region of binary list-decodable codes for insertions and deletions. We further generalize our result to codes over any finite alphabet of size $q$. Surprisingly, our work reveals that the feasibility region for $q>2$ is not the natural generalization of the binary bound above. We provide tight upper and lower bounds that precisely pin down the feasibility region, which turns out to have a $(q-1)$ -piece-wise linear boundary whose $q$ corner-points lie on a quadratic curve. The main technical work in our results is proving the existence of code families of sufficiently large size with good list-decoding properties for any combination of $\delta,\gamma $ within the claimed feasibility region. We achieve this via an intricate analysis of codes introduced by [Bukh and Ma, 2014]. Finally, we give a simple yet powerful concatenation scheme for list-decodable insertion-deletion codes which transforms any such (non-efficient) code family (with vanishing information rate) into an efficiently decodable code family with constant rate. [ABSTRACT FROM AUTHOR]

This paper proposes the Guruswami-Sudan (GS) list decoding algorithm for one-point elliptic codes, in which the interpolation is realized by the module basis reduction (BR). Elliptic codes are a kind of algebraic-geometric (AG) codes with a genus of one. Over the same finite field, they have a greater codeword length than Reed-Solomon (RS) codes, capable of correcting more errors. The GS decoding consists of interpolation and root-finding, while the former that determines the interpolation polynomial $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ dominates the decoding complexity. By defining the Lagrange interpolation function over an elliptic function field, a basis of the interpolation module can be constructed. The desired Gröbner basis that contains $\mathcal {Q}(\text {x}, \text {y}, \text {z})$ can be determined by reducing the constructed basis. This is namely the BR interpolation and it requires less finite field arithmetic operations than the conventional Kötter’s interpolation, facilitating the GS decoding. Re-encoding transform (ReT) is further introduced to facilitate the BR interpolation. This work also shows that both the BR interpolation and its ReT variant will have a lower complexity as the code rate ${k}/{n}$ increases, where n and ${k}$ are the length and dimension of the code, respectively. Our numerical results demonstrate the complexity advantage of the BR interpolation over Kötter’s interpolation, and the performance advantage of elliptic codes over RS codes. [ABSTRACT FROM AUTHOR]

We present a list decoding algorithm for -linear codes that generalize the Reed–Solomon -codes. [ABSTRACT FROM AUTHOR]

The aim of the paper is to revive and develop results of an unpublished manuscript of A.G. D'yachkov. We consider a discrete memoryless channel (DMC) and prove a theorem on the exponential expurgation bound for list decoding with fixed list size . This result is an extension of the classical exponential error probability bound for optimal codes over a DMC to the list decoding model over a DMC. As applications of this result, we consider a memoryless binary symmetric channel (BSC) and a memoryless binary asymmetric channel (Z-channel). For the both channels, we derive a lower bound on the fraction of correctable errors for zero-rate transmission over the corresponding channels under list decoding with a fixed list size at the channel output. For the Z-channel, we obtain this bound for an arbitrary input alphabet distribution ; we also find the optimum value of the obtained bound and prove that the fraction of errors correctable by an optimal code tends to 1 as the list size tends to infinity. [ABSTRACT FROM AUTHOR]

Reed–Muller (RM) codes are known for their good maximum likelihood (ML) performance in the short block-length regime. Despite being one of the oldest classes of channel codes, finding a low complexity soft-input decoding scheme is still an open problem. In this work, we present a versatile decoding architecture for RM codes based on their rich automorphism group. The decoding algorithm can be seen as a generalization of multiple-bases belief propagation (MBBP) and may use any polar or RM decoder as constituent decoders. We provide extensive error-rate performance simulations for successive cancellation (SC)-, SC-list (SCL)- and belief propagation (BP)-based constituent decoders. We furthermore compare our results to existing decoding schemes and report a near-ML performance for the RM(3,7)-code (e.g., 0.04 dB away from the ML bound at BLER of 10−3) at a competitive computational cost. Moreover, we provide some insights into the automorphism subgroups of RM codes and SC decoding and, thereby, prove the theoretical limitations of this method with respect to polar codes. [ABSTRACT FROM AUTHOR]

We give an explicit construction of length- $n$ binary codes capable of correcting the deletion of two bits that have size $2^{n}/n^{4+o(1)}$. This matches up to lower order terms the existential result, based on an inefficient greedy choice of codewords, that guarantees such codes of size $\Omega (2^{n}/n^{4})$. Our construction is based on augmenting the classic Varshamov-Tenengolts construction of single deletion codes with additional check equations. We also give an explicit construction of binary codes of size $\Omega (2^{n}/n^{3+o(1)})$ that can be list decoded from two deletions using lists of size two. Previously, even the existence of such codes was not clear. [ABSTRACT FROM AUTHOR]

A key result of classical information theory states that if the rate of a randomly generated codebook is less than the mutual information between the channel’s input and output, then the probability that that codebook has negligible error goes to one as the blocklength goes to infinity. In an attempt to bridge the gap between the probabilistic world of classical information theory and the combinatorial world of zero-error information theory, this work derives necessary and sufficient conditions on the rate so that the probability that a randomly generated codebook operated under list decoding (for any fixed list size) has zero error probability goes to one as the blocklength goes to infinity. Furthermore, this work extends the classical birthday problem to an information-theoretic setting, which results in the definition of a “noisy” counterpart of Rényi entropy, analogous to how mutual information can be considered a noisy counterpart of Shannon entropy. [ABSTRACT FROM AUTHOR]

We give a linear-time erasure list-decoding algorithm for expander codes. More precisely, let r > 0 be any integer. Given an inner code C0 of length d, and a d-regular bipartite expander graph G with n vertices on each side, we give an algorithm to list-decode the code C = C(G, C0) of length nd from approximately δ δr nd erasures in time n ⋅ poly (d2r/δ), where δ and δr are the relative distance and the r’th generalized relative distance of C0, respectively. To the best of our knowledge, this is the first linear-time algorithm that can list-decode expander codes from erasures beyond their (designed) distance of approximately δ2nd. To obtain our results, we show that an approach similar to that of (Hemenway and Wootters, Information and Computation, 2018) can be used to obtain such an erasure-list-decoding algorithm with an exponentially worse dependence of the running time on r and δ; then we show how to improve the dependence of the running time on these parameters. [ABSTRACT FROM AUTHOR]

In this paper, we consider the list decoding property of codes under insertion and deletion errors (insdel for short). Firstly, we analyse the list decodability of random insdel codes. Our result provides a more complete picture on the list decodability of insdel codes when both insertion and deletion errors happen. Secondly, we construct a family of insdel codes along with their efficient encoding and decoding algorithms through concatenation method which provides a Zyablov-type bound for insdel metric codes. [ABSTRACT FROM AUTHOR]

For polar codes, the statistical breakdown of belief propagation (BP) decoding errors is firstly proposed by Sun et al. The errors are classified into three categories: unconverged errors, false converged errors and oscillation errors, which are corrected by three different post-processing methods. As for the BP List (BPL) decoding, we discover that one type of error can be transformed to another type by different factor graphs in the failed BP decoding. Besides, false converged error is usually easier to be detected and modified. Therefore, we only target false converged error to detect and correct. In this work, we propose a two-level detection rule for false converged errors and its corresponding post-processing algorithm to modify these errors in order to improve the performance of the BPL decoding. Numerical results show that the error-correction performance of the proposed decoder is more than 0.85dB better than that of the permuted BPL (PBPL) decoder with slight extra computation complexity at the frame error rate (FER) of $10^{-5}$ for 5G (1024,512) polar code. [ABSTRACT FROM AUTHOR]

In the successive cancellation (SC) list decoding, the tree pruning operation retains the L best paths with respect to a metric at every decoding step. However, the correct path might be among the L worst paths due to the imposed penalties. In this case, the correct path is pruned and the decoding process fails. shifted pruning (SP) scheme can recover the correct path by additional decoding attempts when decoding fails, in which the pruning window is shifted by κ≤L paths over certain bit positions. A special case of the shifted pruning scheme where κ=L is known as SCL-flip decoding, which was independently proposed in 2019. In this work, a new metric that performs better in particular for medium and long codes is proposed, and nested shift-pruning schemes are suggested for improving the average complexity.

Although long polar codes with successive cancellation decoding can asymptotically achieve channel capacity, the performance of short blocklength polar codes is far from optimal. Recently, Arıkan proposed employing a convolutional pre-transformation before the polarization network, called polarization-adjusted convolutional (PAC) codes. In this paper, we focus on improving the performance of short PAC codes concatenated with a cyclic redundancy check (CRC) outer code, CRC-PAC codes, since error detection capability is essential in practical applications, such as the polar coding scheme for the control channel. We propose an enhanced adaptive belief propagation (ABP) decoding algorithm with the assistance of CRC bits for PAC codes. We also derive joint parity-check matrices of CRC-PAC codes suitable for iterative BP decoding. The proposed CRC-aided ABP (CA-ABP) decoding can effectively improve error performance when partial CRC bits are used in the decoding. Meanwhile, the error detection ability can still be guaranteed by the remaining CRC bits and adaptive decoding parameters. Moreover, compared with the conventional CRC-aided list (CA-List) decoding, our proposed scheme can significantly reduce computational complexity, to achieve a better trade-off between the performance and complexity for short PAC codes.

We consider sparse regression codes (SPARCs) over complex AWGN channels. Such codes can be efficiently decoded by an approximate message passing (AMP) decoder, whose performance can be predicted via so-called state evolution in the large-system limit. In this paper, we mainly focus on how to use concatenation of SPARCs and cyclic redundancy check (CRC) codes on the encoding side and use list decoding on the decoding side to improve the finite-length performance of the AMP decoder for SPARCs over complex AWGN channels. Simulation results show that such a concatenated coding scheme works much better than SPARCs with the original AMP decoder and results in a steep waterfall-like behavior in the bit-error rate performance curves. Furthermore, we apply our proposed concatenated coding scheme to spatially coupled SPARCs. Besides that, we also introduce a novel class of design matrices, i.e., matrices that describe the encoding process, based on circulant matrices derived from Frank or from Milewski sequences. This class of design matrices has comparable encoding and decoding computational complexity as well as very close performance with the commonly-used class of design matrices based on discrete Fourier transform (DFT) matrices, but gives us more degrees of freedom when designing SPARCs for various applications. [ABSTRACT FROM AUTHOR]

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m > 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both. [ABSTRACT FROM AUTHOR]

The Levenshtein’s channel model for substitution errors is relevant in information retrieval where information is received through many noisy channels. In each of the channels there can occur at most t errors and the decoder tries to recover the information with the aid of the channel outputs. Recently, Yaakobi and Bruck considered the problem where the decoder provides a list instead of a unique output. If the underlying code C ⊆ F2n has error-correcting capability e, we write t = e + ℓ, (ℓ ≥ 1). In this paper, we provide new (constant) bounds on the size of the list. In particular, we give using the Sauer-Shelah lemma the upper bound ℓ + 1 on the list size for large enough n provided that we have a sufficient number of channels. We also show that the bound ℓ + 1 is the best possible. Most of our other new results rely on constant weight codes. [ABSTRACT FROM AUTHOR]

We propose the new rank-metric code-based cryptosystem LIGA which is based on the hardness of list decoding and interleaved decoding of Gabidulin codes. LIGA is an improved variant of the Faure–Loidreau (FL) system, which was broken in a structural attack by Gaborit, Otmani, and Talé Kalachi (GOT, 2018). We keep the FL encryption and decryption algorithms, but modify the insecure key generation algorithm. Our crucial observation is that the GOT attack is equivalent to decoding an interleaved Gabidulin code. The new key generation algorithm constructs public keys for which all polynomial-time interleaved decoders fail—hence LIGA resists the GOT attack. We also prove that the public-key encryption version of LIGA is IND-CPA secure in the standard model and the key encapsulation mechanisms version is IND-CCA2 secure in the random oracle model, both under hardness assumptions of formally defined problems related to list decoding and interleaved decoding of Gabidulin codes. We propose and analyze various exponential-time attacks on these problems, calculate their work factors, and compare the resulting parameters to NIST proposals. The strengths of LIGA are short ciphertext sizes and (relatively) small key sizes. Further, LIGA guarantees correct decryption and has no decryption failure rate. It is not based on hiding the structure of a code. Since there are efficient and constant-time algorithms for encoding and decoding Gabidulin codes, timing attacks on the encryption and decryption algorithms can be easily prevented. [ABSTRACT FROM AUTHOR]

We strengthen the notion of double samplers, first introduced by Dinur and Kaufman ["High dimensional expanders imply agreement expanders," in Proc. 58th IEEE Symp. on Foundations of Comp. Science, IEEE, 2017, pp. 974-985], which are samplers with additional combinatorial properties, and whose existence we prove using high-dimensional expanders. The ABNNR code construction [N. Alon et al., IEEE Trans. Inform. Theory, 38 (1992), pp. 509-516] achieves large distance by starting with a base code C with moderate distance, and then amplifying the distance using a sampler. We show that if the sampler is part of a larger double sampler, then the construction has an efficient list-decoding algorithm. Our algorithm works even if the ABNNR construction is not applied to a base code C but rather to any string. In this case the resulting code is approximate-list-decodable, i.e., the output list contains an approximation to the original input. Our list-decoding algorithm works as follows: It uses a local voting scheme from which it constructs a unique games constraint graph. The constraint graph is an expander, so we can solve unique games efficiently. These solutions are the output of the list-decoder. This is a novel use of a unique games algorithm as a subroutine in a decoding procedure, as opposed to the more common situation in which unique games are used for demonstrating hardness results. Double samplers and high-dimensional expanders are akin to pseudorandom objects in their utility, but they greatly exceed random objects in their combinatorial properties. We believe that these objects hold significant potential for coding theoretic constructions and view this work as demonstrating the power of double samplers in this context. [ABSTRACT FROM AUTHOR]

Polarization-adjusted convolutional (PAC) codes are special concatenated codes in which we employ a one-to-one convolutional transform as a pre-coding step before the polar transform. In this scheme, the polar transform (as a mapper) and the successive cancellation process (as a demapper) present a synthetic vector channel to the convolutional transformation. The numerical results show that this concatenation improves the Hamming distance properties of polar codes. Motivated by the fact that the parallel list Viterbi algorithm (LVA) sorts the candidate paths locally at each trellis node, in this work, we adapt the trellis, path metric, and the local sorter of LVA to PAC codes and show how the error correction performance moves from the poor performance of the Viterbi algorithm (VA) to the superior performance of list decoding by changing the constraint length, list size, and the sorting strategy (local sorting and global sorting) in the LVA. Also, we analyze the complexity of the local sorting of the paths in LVA relative to the global sorting in the list decoding and we show that LVA has a significantly lower sorting complexity compared with list decoding. [ABSTRACT FROM AUTHOR]

In this work it is shown that locally repairable codes (LRCs) can be list-decoded efficiently beyond the Johnson radius for a large range of parameters by utilizing the local error-correction capabilities. The corresponding decoding radius is derived and the asymptotic behavior is analyzed. A general list-decoding algorithm for LRCs that achieves this radius is proposed along with an explicit realization for LRCs that are subcodes of Reed–Solomon codes (such as, e.g., Tamo–Barg LRCs). Further, a probabilistic algorithm of low complexity for unique decoding of LRCs is given and its success probability is analyzed. The second part of this work considers error decoding of LRCs and partial maximum distance separable (PMDS) codes through interleaved decoding. For a specific class of LRCs the success probability of interleaved decoding is investigated. For PMDS codes, it is shown that there is a wide range of parameters for which interleaved decoding can increase their decoding radius beyond the minimum distance such that the probability of successful decoding approaches 1 when the code length goes to infinity. [ABSTRACT FROM AUTHOR]

There has been a great deal of work establishing that random linear codes are as list-decodable as uniformly random codes, in the sense that a random linear binary code of rate $1 - {H}(\text {p}) - \epsilon $ is $({p},\text {O}(1/\epsilon))$ -list-decodable with high probability. In this work, we show that such codes are $({p}, {H}({p})/\epsilon + 2)$ -list-decodable with high probability, for any $ {p} \in (0, 1/2)$ and $\epsilon > 0$. In addition to improving the constant in known list-size bounds, our argument—which is quite simple—works simultaneously for all values of p, while previous works obtaining $ {L} = \text {O}(1/\epsilon)$ patched together different arguments to cover different parameter regimes. Our approach is to strengthen an existential argument of (Guruswami, Håstad, Sudan and Zuckerman, IEEE Trans. IT, 2002) to hold with high probability. To complement our upper bound for random linear codes, we also improve an argument of (Guruswami, Narayanan, IEEE Trans. IT, 2014) to obtain an essentially tight lower bound of $1/\epsilon $ on the list size of uniformly random codes; this implies that random linear codes are in fact more list-decodable than uniformly random codes, in the sense that the list sizes are strictly smaller. To demonstrate the applicability of these techniques, we use them to (a) obtain more information about the distribution of list sizes of random linear codes and (b) to prove a similar result for random linear rank-metric codes. [ABSTRACT FROM AUTHOR]

Abstract The network coding can spread a single original error over the whole network. The simulation shows that the propagated error mostly all the time pollute just 100% of the received packets at the sink if Hamming distance is adopted. If subspace codes are adopted, usually the propagated error will not pollute 100% of the received packets in the sense of subspace distance. However, it also usually pollutes 90% of received packets which is a high error ratio. Even if the rank code and the subspace code are adopted, these existing schemes based on traditional block codes can correct corrupted errors no more than C/2 because of the limitation of the block coding where C is the max flow min cut. It is an agent to find a dense error correction method in random network coding. List decoding of subspace codes can correct Ck‐1 $$ \frac{C}{k}\hbox{-} 1 $$ errors where k is the size of information. When Ck $$ \frac{C}{k} $$ is big, many errors in the sense of subspace distance can be corrected. However, the solution of list decoding is not unique. John Wright proposed a dense error correction technique based on L1 minimization, which can recover nearly 100% of the corrupted observations. In our proposal, the original packets are coded with John Wright’s coding matrix, and then, the coded message is coded again with subspace codes. In the sink, the decoding procedures about list decoding of subspace codes and John Wright’s scheme are performed. At last, the unique solution is achieved even though there are dense propagated errors in random network coding.

Comparing with hard decision decoding algorithms, soft decoding has a lower probability of bit error but a higher computational complexity. As a maximum-likelihood soft decoding method, the A* algorithm is the most basic and widely used to minimize bit error probability. However, its average computational complexity strongly depends on a seed codeword and a heuristic function utilized during the decoding process. To efficiently reduce the computational complexity while maintaining the decoding accuracy theoretically and practically, this paper proposes an improved A* decoding algorithm consisting of two phases. The first phase applies the greedy list decoding to the linear block code to obtain a seed codeword. According to the seed, the second phase applies the improved A* algorithm to obtain the final decoding output. The heuristic function used in the A* algorithm is modified in two aspects: (1) use more information of partial decoded symbols to improve the accuracy of the function and (2) take advantage of Hamming distance to reduce the search space. Simulations on the RM(5, 2) Reed-Muller codes and [128, 64] binary extended BCH code show that this improved A* algorithm is more efficient in average decoding complexity than many other algorithms while maintaining the decoding accuracy.

Simulation results show that the performance of polar codes is improved vastly by using polar codes as inner codes in serially concatenated coding schemes. Furthermore, this performance improvement is achieved using a relatively short cyclic redundancy check as the outer code and a practically implementable successive cancellation list decoder for decoding the overall code. This paper offers a theoretical analysis of such schemes by employing a random-coding method on the selection of the outer code and assuming that the channel is memoryless. It is shown that the probability of error for the concatenated coding scheme decreases exponentially in the code block length at any fixed rate below the symmetric capacity. Applications of this result include the design of polar codes for communication systems that require high reliability at small to moderate code lengths, such as control channels in wireless systems and machine-type communications for industrial automation.

In this work, we study the problem of list decoding of insertions and deletions. We present a Johnson-type upper bound on the maximum list size. The bound is meaningful only when insertions occur. Our bound implies that there are binary codes of rate $\Omega (1)$ that are list-decodable from a 0.707-fraction of insertions. For any $\tau _{\mathsf {I}} \geq 0$ and $\tau _{\mathsf {D}} \in [0,1)$ , there exist $q$ -ary codes of rate $\Omega (1)$ that are list-decodable from a $\tau _{\mathsf {I}}$ -fraction of insertions and $\tau _{\mathsf {D}}$ -fraction of deletions, where $q$ depends only on $\tau _{\mathsf {I}}$ and $\tau _{\mathsf {D}}$. We also provide efficient encoding and decoding algorithms for list-decoding from $\tau _{\mathsf {I}}$ -fraction of insertions and $\tau _{\mathsf {D}}$ -fraction of deletions for any $\tau _{\mathsf {I}} \geq 0$ and $\tau _{\mathsf {D}} \in [0,1)$. Based on the Johnson-type bound, we derive a Plotkin-type upper bound on the code size in the Levenshtein metric. [ABSTRACT FROM AUTHOR]

Let $k,n,m \in {\mathbb Z} ^{+}$ be integers such that $k\leq n \leq m$ , let $\mathrm {G}_{n,k}\in {\mathbb F} _{q^{m}}^{n}$ be a Delsarte-Gabidulin code. Recently, Wachter-Zeh proved that codes belonging to this family cannot be efficiently list decoded for any radius $\tau $ , providing $\tau $ is large enough. This achievement essentially relies on proving a lower bound for the list size of some specific words in ${\mathbb F}_{q^{m}}^{n}$. Some years later, Raviv and Wachter-Zeh improved this bound in a special case, i.e. when $n\mid m$. As a consequence, they were able to detect infinite families of Delsarte-Gabidulin codes that cannot be efficiently list decoded at all. In this article we determine similar lower bounds for Maximum Rank Distance codes belonging to a wider class of examples, containing Generalized Gabidulin codes, Generalized Twisted Gabidulin codes, and examples recently described by Trombetti and Zhou. By exploiting arguments such as those used by Raviv and Wachter-Zeh, when $n\mid m$ , we also show infinite families of generalized Gabidulin codes that cannot be list decoded efficiently at any radius greater than or equal to $\left \lfloor{ \frac {d-1}2 }\right \rfloor +1$ , where $d$ is its minimum distance. Nonetheless, in all the examples belonging to above mentioned class, we detect infinite families that cannot be list decoded efficiently at any radius greater than or equal to $\left \lfloor{ \frac {d-1}2 }\right \rfloor +2$ , where $d$ is its minimum distance. In particular, this leads to show infinite families of Gabidulin codes, with underlying parameters not already covered by the result of Raviv and Wachter-Zeh, having this decodability defect. Finally, relying on the properties of a set of subspace trinomials recently presented by McGuire and Mueller, we are able to prove our main result, that is any rank-metric code of ${\mathbb F}_{q^{m}}^{n}$ of order $q^{kn}$ with $n$ dividing $m$ , such that $4n-3$ is a square in $\mathbb {Z}$ and containing $\mathrm {G}_{n,2}$ , is not efficiently list decodable at some values of the radius $\tau $. [ABSTRACT FROM AUTHOR]

We show that the tensor product of a high-rate globally list recoverable code is (approximately) locally list recoverable. List recovery has been a useful building block in the design of list decodable codes, and our motivation is to use the tensor construction as such a building block. In particular, instantiating this construction with known constructions of high-rate globally list recoverable codes, and using appropriate transformations, we obtain the first capacity-achieving locally list decodable codes (over a large constant size alphabet), and the first capacity-achieving globally list decodable codes with nearly linear time list decoding algorithms. Our techniques are inspired by an approach of Gopalan, Guruswami, and Raghavendra [SIAM J. Comput., 40 (2011), pp. 1432-1462] for list decoding tensor codes. [ABSTRACT FROM AUTHOR]

We prove a new upper bound on the size of codes $C \subseteq \{1,2,3,4\}^{n}$ with the property that every four distinct codewords in $C$ have a coordinate where they all differ. Specifically, we provide a self-contained proof that such codes have size at most $2^{6n/19 + o(n)}$ , that is, rate bounded asymptotically by 6/19 ≤ 0.3158 (measured in bits). This improves the previous best upper bound of 0.3512 due to (Arikan 1994), which in turn improved the 0.375 bound that followed from general bounds for perfect hashing due to (Fredman and Komlós, 1984) and (Körner and Marton, 1988). Finally, using a combination of our approach with a simple idea which exploits powerful bounds on the minimum distance of codes in the Hamming space, we further improve the upper bound to 0.31477. [ABSTRACT FROM AUTHOR]

We study a two-stage identification problem with pre-processing to enable efficient data retrieval and reconstruction. In the enrollment phase, users’ data are stored into the database in two layers. In the identification phase an observer obtains an observation, which originates from an unknown user in the enrolled database through a memoryless channel. The observation is sent for processing in two stages. In the first stage, the observation is pre-processed, and the result is then used in combination with the stored first layer information in the database to output a list of compatible users to the second stage. Then the second step uses the information of users contained in the list from both layers and the original observation sequence to return the exact user identity and a corresponding reconstruction sequence. The rate-distortion regions are characterized for both discrete and Gaussian scenarios. Specifically, for a fixed list size and distortion level, the compression-identification trade-off in the Gaussian scenario results in three different operating cases characterized by three auxiliary functions. While the choice of the auxiliary random variable for the first layer information is essentially unchanged when the identification rate is varied, the second one is selected based on the dominant function within those three. Due to the presence of a mixture of discrete and continuous random variables, the proof for the Gaussian case is highly non-trivial, which makes a careful measure theoretic analysis necessary. In addition, we study a connection of the previous setting to a two observer identification and a related problem with a lower bound for the list size, where the latter is motivated from privacy concerns. [ABSTRACT FROM AUTHOR]

Polar codes have gained extensive attention during the past few years and recently they have been selected for the next generation of wireless communications standards (5G). Successive-cancellation-based (SC-based) decoders, such as SC list (SCL) and SC flip (SCF), provide a reasonable error performance for polar codes at the cost of low decoding speed. Fast SC-based decoders, such as Fast-SSC, Fast-SSCL, and Fast-SSCF, identify the special constituent codes in a polar code graph off-line, produce a list of operations, store the list in memory, and feed the list to the decoder to decode the constituent codes in order efficiently, thus increasing the decoding speed. However, the list of operations is dependent on the code rate and as the rate changes, a new list is produced, making fast SC-based decoders not rate-flexible. In this paper, we propose a completely rate-flexible fast SC-based decoder by creating the list of operations directly in hardware, with low implementation complexity. We further propose a hardware architecture implementing the proposed method and show that the area occupation of the rate-flexible fast SC-based decoder in this paper is only $\text{38}{\%}$ of the total area of the memory-based base-line decoder when 5G code rates are supported. [ABSTRACT FROM AUTHOR]

This letter proposes successive cancellation list (SCL) decoding of product codes with Reed–Muller (RM) component codes. SCL decoding relies on a product code description based on the $2\times 2$ Hadamard kernel, which enables interpreting the code as an RM subcode. The focus is on a class of product codes considered in wireless communication systems, based on single parity-check and extended Hamming component codes. For short product codes, it is shown that SCL decoding with a moderate list size performs as well as (and, sometimes, outperforms) belief propagation (BP) decoding. Furthermore, by concatenating a short product code with a high-rate outer code, SCL decoding outperforms BP decoding by up to 1.4 dB. [ABSTRACT FROM AUTHOR]

In this paper, we provide two distinct list decoding algorithms tailored for specific classes of maximal order number field codes. The first algorithm focuses on the unit codes, while the second algorithm is dedicated to the Arakelov divisor-based number field codes. These codes were originally introduced by Maire and Oggier. To achieve our decoding goals, we utilize the list decoding algorithm for general number field codes proposed by Biasse and Quintin. Our approach involves carefully calculating the required parameter B from Biasse and Quintin's algorithm, and adjusting the returned list to satisfy the desired conditions. For unit codes, we consider two cases: when the underlying number field is totally real and when it has an arbitrary signature. We separate these cases because the parameter B can be improved in the totally real scenario. Additionally, we present our list decoding algorithm for Arakelov divisor-based number field codes, focusing on number fields with arbitrary signatures. [ABSTRACT FROM AUTHOR]