Search

In this paper, we define expanded LRPC codes from LRPC codes with a decoding algorithm using the one of the underlying LRPC codes. Next, we propose to use these codes for cryptography by deriving two cryptosystems in a McEliece setting. in order to reduce the key sizes, we use a generator matrix in systematic form for the first scheme, and an m − order quasi-cyclic LRPC code that we define for the second scheme. The obtained code has a very poor structure and is more likely to be a random linear code. Next, we give some security parameters and compare the key sizes of our public key with the key sizes of some cryptosystems. [ABSTRACT FROM AUTHOR]

Many families of binary nonlinear codes (e.g., Kerdock, Goethals, Delsarte–Goethals, Preparata) can be very simply constructed from linear codes over the Z 4 ring (ring of integers modulo 4), by applying the Gray map to the quaternary symbols. Generalized Kerdock codes represent an extension of classical Kerdock codes to the Z 2 S ring. In this paper, we develop two novel soft-input decoders, designed to exploit the unique structure of these codes. We introduce a novel soft-input ML decoding algorithm and a soft-input soft-output MAP decoding algorithm of generalized Kerdock codes, with a complexity of O (N S log 2 N) , where N is the length of the Z 2 S code, that is, the number of Z 2 S symbols in a codeword. Simulations show that our novel decoders outperform the classical lifting decoder in terms of error rate by some 5 dB. [ABSTRACT FROM AUTHOR]

The residual belief propagation (RBP) algorithm, which is the most classic informed dynamic scheduling strategy, achieves outstanding performance in error correction and can drastically accelerate convergence speed. However, the greedy algorithmic property of this iterative decoding will inevitably cause loss of decoding performance. To address this, a novel algorithm called the partial average bundle residual belief propagation (PABRBP) is proposed in this paper. According to the construction characteristics of a base matrix of protograph‐LDPC codes, informed dynamic scheduling (IDS) strategies are applied to an edge bundle of base matrices for the first time. This edge bundle of the base matrix can be applied to a corresponding cyclic permutation matrix. Furthermore, the update level of each bundle is determined by the value of the Partially Average Bundle Residual (PABR). Therefore, the edge message with the maximum residual in each bundle is updated in order, and the process of iterative decoding is less likely to become trapped in a local optimum. Additionally, the generation of silent nodes is reduced as much as possible. To further improve the PABRBP decoding performance for medium and long codes over the fading channel, the adjusted compensation term is periodically introduced. Analysis and simulation results show that PABRBP demonstrates a notable convergence quality and decoding performance improvement over the fading channels compared to existing state‐of‐art IDS algorithms. [ABSTRACT FROM AUTHOR]

A key component of many graph neural networks (GNNs) is the pooling operation, which seeks to reduce the size of a graph while preserving important structural information. However, most existing graph pooling strategies rely on an assignment matrix obtained by employing a GNN layer, which is characterized by trainable parameters, often leading to significant computational complexity and a lack of interpretability in the pooling process. In this paper, we propose an unsupervised graph encoder–decoder model to detect abnormal nodes from graphs by learning an anomaly scoring function to rank nodes based on their degree of abnormality. In the encoding stage, we design a novel pooling mechanism, named LCPool, which leverages locality-constrained linear coding for feature encoding to find a cluster assignment matrix by solving a least-square optimization problem with a locality regularization term. By enforcing locality constraints during the coding process, LCPool is designed to be free from learnable parameters, capable of efficiently handling large graphs, and can effectively generate a coarser graph representation while retaining the most significant structural characteristics of the graph. In the decoding stage, we propose an unpooling operation, called LCUnpool, to reconstruct both the structure and nodal features of the original graph. We conduct empirical evaluations of our method on six benchmark datasets using several evaluation metrics, and the results demonstrate its superiority over state-of-the-art anomaly detection approaches. [ABSTRACT FROM AUTHOR]

In this paper we review existing hard-decision decoding algorithms for product codes along with different post-processing techniques used in conjunction with the iterative decoder for product codes. We improve the decoder by Reddy and Robinson and use it to create a new post-processing technique. The performance of this new post-processing technique is evaluated through simulations, and these suggest that our new post-processing technique outperforms previously known post-processing techniques which are not tailored for specific codes. The cost of using the new post-processing technique is that the algorithm becomes more complex. However, the post-processing is applied very rarely unless the channel is very noisy, and hence the increase in computational complexity is negligible for most choices of parameters. Finally, we propose a new algorithm that combines existing techniques in a way that avoids the error floor with short relatively high rate codes. The algorithm should also avoid the error floor with long high rate codes, but further work is needed to confirm this. [ABSTRACT FROM AUTHOR]

Linear codes with complementary duals, shortly named LCD codes, are linear codes whose intersection with their duals is trivial. In this paper, we outline a construction for LCD codes over finite fields from the adjacency matrices of two-class association schemes. These schemes consist of either strongly regular graphs (SRGs) or doubly regular tournaments (DRTs). Under certain conditions, the method yields formally self-dual codes. Further, we propose a decoding algorithm that can be feasible for the LCD codes obtained using one of the given methods. [ABSTRACT FROM AUTHOR]

As a subclass of linear codes, cyclic codes have efficient encoding and decoding algorithms, so they are widely used in many areas such as consumer electronics, data storage systems and communication systems. In this paper, we give a general construction of optimal p-ary cyclic codes which leads to three explicit constructions. In addition, another class of p-ary optimal cyclic codes are presented. [ABSTRACT FROM AUTHOR]

Due to efficient encoding and decoding algorithms, BCH codes have many applications in data storage systems and satellite communications. Meanwhile, one advantage of BCH codes is to construct quantum codes. In this paper, we assume that q ≡ 1 mod m , where m is a positive integer. We first study a class of q - ary quantum codes of length r (q m - 1) q - 1 by CSS construction, where r ∣ q - 1 . Then, we construct two families of q - ary quantum codes of length r (q 2 m - 1) q 2 - 1 by Hermitian construction. These constructions produce new quantum codes with larger dimensions. [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]

An $(n,r,h,a,q)$ -Local Reconstruction Code (LRC) is a linear code over $\mathbb {F}_{q}$ of length $n$ , whose codeword symbols are partitioned into $n/r$ local groups each of size $r$. Each local group satisfies ‘ $a$ ’ local parity checks to recover from ‘ $a$ ’ erasures in that local group and there are further $h$ global parity checks to provide fault tolerance from more global erasure patterns. Such an LRC is Maximally Recoverable (MR), if it offers the best blend of locality and global erasure resilience—namely it can correct all erasure patterns whose recovery is information-theoretically feasible given the locality structure (these are precisely patterns with up to ‘ $a$ ’ erasures in each local group and an additional $h$ erasures anywhere in the codeword). Random constructions can easily show the existence of MR LRCs over very large fields, but a major algebraic challenge is to construct MR LRCs, or even show their existence, over smaller fields, as well as understand inherent lower bounds on their field size. We give an explicit construction of $(n,r,h,a,q)$ -MR LRCs with field size $q$ bounded by $\left ({O\left ({\max \{r,n/r\}}\right)}\right)^{\min \{h,r-a\}}$. This significantly improves upon known constructions in many practically relevant parameter ranges. Moreover, it matches the lower bound from Gopi et al. (2020) in an interesting range of parameters where $r=\Theta (\sqrt {n})$ , $r-a=\Theta (\sqrt {n})$ and $h$ is a fixed constant with $h \leqslant a+2$ , achieving the optimal field size of $\Theta _{h}(n^{h/2})$. Our construction is based on the theory of skew polynomials. We believe skew polynomials should have further applications in coding and complexity theory; as a small illustration we show how to capture algebraic results underlying list decoding folded Reed-Solomon and multiplicity codes in a unified way within this theory. [ABSTRACT FROM AUTHOR]

We propose the first non-trivial generic decoding algorithm for codes in the sum-rank metric. The new method combines ideas of well-known generic decoders in the Hamming and rank metric. For the same code parameters and number of errors, the new generic decoder has a larger expected complexity than the known generic decoders for the Hamming metric and smaller than the known rank-metric decoders. Furthermore, we give a formal hardness reduction, providing evidence that generic sum-rank decoding is computationally hard. As a by-product of the above, we solve some fundamental coding problems in the sum-rank metric: we give an algorithm to compute the exact size of a sphere of a given sum-rank radius, and also give an upper bound as a closed formula; and we study erasure decoding with respect to two different notions of support. [ABSTRACT FROM AUTHOR]

We were able to classify all 1-error correcting [5, 3] codes over GF(5) in paper [1] and [5, 2] ternary codes in paper [2]. Now, our focus is an equivalence based classification of error correcting linear codes of length 6 over GF(5). In paper [3], we investigated the equivalence of [6,3,4] codes of length 6 and dimension 3 over GF(4). In this paper we classify the [6,3,4] codes over GF(5). We explore the weight distribution of these codes as well as their duals. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems and communication systems as they have efficient encoding and decoding algorithms. In this paper, by investigating the solutions of certain equations over finite fields, we make progress towards three conjectures about optimal ternary cyclic codes which were proposed by Ding and Helleseth. [ABSTRACT FROM AUTHOR]

Constant dimension codes, a specialized subclass of subspace codes, have garnered significant attention in recent years due to their applications in random network coding. Among these codes, large cyclic constant dimension codes, endowed with optimal minimum distance, offer efficient solutions for encoding and decoding algorithms. This paper is dedicated to the design of cyclic constant dimension codes that achieve the dual goals: maximizing code size while maintaining optimal minimum distance. We first explore a new form of Sidon spaces and employ this new form to construct several families of cyclic subspace codes. Our codes have optimal minimum distances and have more codewords than previous constructions in the literature. [ABSTRACT FROM AUTHOR]

Previous algorithms for decoding AG codes up to the designed distance all assumed existence of an extra rational place on the base algebraic curve. The place is used to solve the decoding problem by linear algebra over the base field of the curve. The rationality of the place is essential, and therefore AG codes supported by all rational places on the curve are excluded from the domain of applicability of the decoding algorithms. This paper presents a decoding algorithm for those AG codes using an extra place of higher degree. Hence finally all AG codes, as Goppa defined 40 years ago, are equipped with a fast decoding algorithm. [ABSTRACT FROM AUTHOR]

Designs and methods for nested lattice codes using Construction D’ lattices for coding and convolutional code lattices for shaping are described. Two encoding methods and a decoding algorithm for Construction D’ coding lattices that can be used with shaping lattices for power-constrained channels are given. We construct nested lattice codes with good coding properties, high shaping gain, and low-complexity encoding and decoding. Convolutional code generator polynomials for Construction A lattices with the greatest shaping gain are given, as a result of an extensive search. It is shown that rate 1/3 convolutional codes provide a more favorable performance-complexity trade-off than rate 1/2 convolutional codes. Tail-biting convolutional codes have higher shaping gain than that of zero-tailed convolutional codes. A design for quasi-cyclic low-density parity-check (QC-LDPC) codes to form Construction D’ lattices which have efficient encoding and indexing is presented. The resulting QC-LDPC Construction D’ lattices are evaluated using four shaping lattices: the $E_{8}$ lattice, the $BW_{16}$ lattice, the Leech lattice and our best-found convolutional code lattice, showing a shaping gain of approximately 0.65 dB, 0.86 dB, 1.03 dB and 1.25 dB at dimension 2304. [ABSTRACT FROM AUTHOR]

It is well-known that cyclic codes have efficient encoding and decoding algorithms. In recent years, antiprimitive BCH codes have attracted a lot of attention. The objective of this paper is to study BCH codes of this type over finite fields and analyse their parameters. Some lower bounds on the minimum distance of antiprimitive BCH codes are given. The BCH codes presented in this paper have good parameters in general, containing many optimal linear codes. In particular, two open problems about the minimum distance of BCH codes of this type are partially solved in this paper. [ABSTRACT FROM AUTHOR]

In this article, we consider Schubert codes, linear codes associated to Schubert varieties, and discuss minimum weight codewords for dual Schubert codes. The notion of lines in Schubert varieties is looked closely at, and it has been proved that the supports of the minimum weight codewords of the dual Schubert codes lie on lines and any three points on a line in the Schubert variety correspond to the support of some minimum weight parity check for the Schubert code. We use these lines in Schubert varieties to construct orthogonal parity checks for certain Schubert codes and use them for majority logic decoding. In some special cases, we can correct approximately up to $\lfloor (d-1)/2\rfloor $ many errors where $d$ is the minimum distance of the code. [ABSTRACT FROM AUTHOR]

List-decoding and list-recovery are important generalizations of unique decoding and receive considerable attention over the years. We study the optimal trade-off among the list-decoding (resp. list-recovery) radius, the list size, and the code rate, when the list size is constant and the alphabet size is large (both compared with the code length). We prove a new Singleton-type bound for list-decoding, which, for a wide range of parameters, is asymptotically tight up to a 1 + o (1) factor. We also prove a Singleton-type bound for list-recovery, which is the first such bound in the literature. We apply these results to obtain near optimal lower bounds on the list size for list-decodable and list-recoverable codes with rates approaching capacity. Moreover, we show that under some indivisibility condition of the parameters and over a sufficiently large alphabet, the largest list-decodable nonlinear codes can have much more codewords than the largest list-decodable linear codes. Such a large gap is not known to exist in unique decoding. We prove this by a novel connection between list-decoding and the notion of sparse hypergraphs in extremal combinatorics. Lastly, we show that list-decodability or recoverability implies in some sense good unique decodability. [ABSTRACT FROM AUTHOR]

The design and implementation of error correcting codes has long been informed by two fundamental results: Shannon’s 1948 capacity theorem, which established that long codes use noisy channels most efficiently; and Berlekamp, McEliece, and Van Tilborg’s 1978 theorem on the NP-completeness of decoding linear codes. These results shifted focus away from creating code-independent decoders, but recent low-latency communication applications necessitate relatively short codes, providing motivation to reconsider the development of universal decoders. We introduce a scheme for employing binarized symbol soft information within Guessing Random Additive Noise Decoding, a universal hard detection decoder. We incorporate codebook-independent quantization of soft information to indicate demodulated symbols to be reliable or unreliable. We introduce two decoding algorithms: one identifies a conditional Maximum Likelihood (ML) decoding; the other either reports a conditional ML decoding or an error. For random codebooks, we present error exponents and asymptotic complexity, and show benefits over hard detection. As empirical illustrations, we compare performance with majority logic decoding of Reed-Muller codes, with Berlekamp-Massey decoding of Bose-Chaudhuri-Hocquenghem codes, with CA-SCL decoding of CA-Polar codes, and establish the performance of Random Linear Codes, which require a universal decoder and offer a broader palette of code sizes and rates than traditional codes. [ABSTRACT FROM AUTHOR]

A large class of MDS linear codes is constructed. These codes are endowed with an efficient decoding algorithm. Both the definition of the codes and the design of their decoding algorithm only require from Linear Algebra methods, making them fully accessible for everyone. Thus, the first part of the paper develops a direct presentation of the codes by means of parity-check matrices, and the decoding algorithm rests upon matrix and linear maps manipulations. The somewhat more sophisticated mathematical context (non-commutative rings) needed for the proof of the correctness of the decoding algorithm is postponed to the second part. A final section locates the Reed-Solomon skew-differential codes introduced here within the general context of codes defined by means of skew polynomial rings. [ABSTRACT FROM AUTHOR]

In this paper we address the problem of list decoding of linear codes over an integer residue ring Z q , where q is a power of a prime p. The proposed procedure exploits a particular matrix representation of the linear code over Z p r , called the standard form, and the p -adic expansion of the to-be-decoded vector. In particular, we focus on the erasure channel in which the location of the errors is known. This problem then boils down to solving a system of linear equations with coefficients in Z p r . From the parity-check matrix representations of the code we recursively select certain equations that a codeword must satisfy and have coefficients only in the field p r − 1 Z p r . This yields a step by step procedure obtaining a list of the closest codewords to a given received vector with some of its coordinates erased. We show that such an algorithm actually computes all possible erased coordinates, that is, the provided list is minimal. [ABSTRACT FROM AUTHOR]

It is well known that constructing codes with good parameters is one of the most important and fundamental problems in coding theory. Though a great many of good codes have been produced, most of them are defined over alphabets of sizes equal to prime powers. In this article, we provide a new explicit construction of $(q+1)$ -ary nonlinear codes via rational function fields, where $q$ is a prime power. Our codes are constructed by evaluations of rational functions at all rational places (including the place of “infinity”) of the rational function field. Compared to the rational algebraic geometry codes, the main difference is that we allow rational functions to be evaluated at pole places. After evaluating rational functions from a union of Riemann-Roch spaces, we obtain a family of nonlinear codes with length $q+1$ over the alphabet $\mathbb {F}_{q}\cup \{\infty \}$. As a result, our codes have reasonable parameters as they are rather close to the Singleton bound. Furthermore, our codes have better parameters than those obtained from MDS codes via code alphabet restriction or extension. Amazingly, an efficient decoding algorithm can be provided for our codes. [ABSTRACT FROM AUTHOR]

Thanks to its superior features of fast read/write speed and low power consumption, spin-torque transfer magnetic random access memory (STT-MRAM) has become a promising non-volatile memory (NVM) technology that is suitable for many applications. However, the reliability of STT-MRAM is seriously affected by the variation of the memory fabrication process and the working temperature, and the later will lead to an unknown offset of the channel. Hence, there is a pressing need to develop more effective error correction coding techniques to tackle these imperfections and improve the reliability of STT-MRAM. In this work, we propose, for the first time, the application of deep-learning (DL)-based algorithms and techniques to improve the decoding performance of linear block codes with short codeword lengths for STT-MRAM. We formulate the belief propagation (BP) decoding of linear block code as a neural network (NN) and propose a novel neural normalized-offset reliability-based min-sum (RB-MS) (NNORB-MS) decoding algorithm. We successfully apply our proposed decoding algorithm to the STT-MRAM channel through channel symmetrization to overcome the channel asymmetry. We also propose an NN-based soft information generation method (SIGM) to take into account the unknown offset of the channel. Simulation results demonstrate that our proposed NNORB-MS decoding algorithm can achieve significant performance gain over both the hard-decision decoding (HDD) and the regular RB-MS decoding algorithm, for cases without and with the unknown channel offset. Moreover, the decoder structure and time complexity of the NNORB-MS algorithm remain similar to those of the regular RB-MS algorithm. [ABSTRACT FROM AUTHOR]

It is known that Z p s -linear codes, which are the Gray map image of Z p s -additive codes (linear codes over Z p s ), are systematic and a systematic encoding has been found. This makes Z p s -linear codes suitable to apply the permutation decoding method. This technique is also based on the existence of r -PD-sets, which are subsets of the permutation automorphism group of the code. In this paper, we study the permutation automorphism group of Z p s -linear generalized Hadamard codes of type (n ; t 1 , ... , t s) and show how to construct r -PD-sets of size r + 1 , for all r up to an upper bound, in order to be able to perform a partial permutation decoding for these codes. [ABSTRACT FROM AUTHOR]

Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems due to their efficient encoding and decoding algorithms. Inspired by the recent work on binary cyclic codes published in Tang and Ding (2022) [26] and the works in Liu et al. (2023) [15] and Liu et al. (2023) [16] , the objectives of this paper are the construction and analysis of four infinite families of ternary cyclic codes with length n = 3 m − 1 for odd m and dimension k ∈ { n / 2 , (n + 2) / 2 } whose minimum distances have a square-root-like lower bound. Their duals have parameters [ n , k ⊥ , d ⊥ ] , where k ⊥ ∈ { n / 2 , (n − 2) / 2 } and d ⊥ also has a square-root-like lower bound. These families of codes and their duals contain distance-optimal cyclic codes. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have wide applications in data storage systems, communication systems and consumer electronics due to their efficient encoding and decoding algorithms. Let p ≥ 5 be an odd prime and m be a positive integer. Let C (1 , e , s) denote the p -ary cyclic code with three nonzeros α , α e , and α s , where α is a generator of F p m ⁎ , s = p m − 1 2 , and 2 ≤ e ≤ p m − 2. In this paper, by analyzing the solutions of certain equations over finite fields, we present four classes of optimal p -ary cyclic codes C (1 , e , s) with parameters [ p m − 1 , p m − 2 m − 2 , 4 ]. Some known results on optimal quinary cyclic codes with parameters [ 5 m − 1 , 5 m − 2 m − 2 , 4 ] are special cases of our constructions. In addition, by analyzing the irreducible factors of certain polynomials over F 5 m , we present two classes of optimal quinary cyclic codes C (1 , e , s). [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems and communication systems as they have efficient encoding and decoding algorithms. In 2013, Ding, et al. presented nine open problems about optimal ternary cyclic codes. The first two and the 6th problems were completely solved, and the third and last three problems were partially solved. In this paper, we focus on the 7th problem. By determining the root set of some special polynomials over finite fields, we give an incomplete answer and then present a counterexample. Furthermore, we construct two new classes of optimal ternary cyclic codes with respect to the Sphere Packing Bound by studying some special polynomials over finite fields. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems, and communication systems as they have efficient encoding and decoding algorithms. In this paper, two classes of cyclic codes whose duals have two zeros are presented. The weight distributions of these cyclic codes are settled with the help of Gaussian periods. The duals of one class of cyclic codes are also studied. Some of the cyclic codes presented in this paper are optimal in the sense that they meet some bounds of linear codes. [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]

Erasure codes play an important role in storage systems to prevent data loss. In this work, we study a class of erasure codes called Multi-Erasure Locally Recoverable Codes (ME-LRCs) for storage arrays. Compared to previous related works, we focus on the construction of ME-LRCs over small fields. Our main contribution is a general construction of ME-LRCs based on generalized tensor product codes, and an analysis of their erasure-correcting properties. A decoding algorithm tailored for erasure recovery is given, and correctable erasure patterns are identified. We then prove that our construction yields optimal ME-LRCs with a wide range of code parameters, and present some explicit ME-LRCs over small fields. Next, we show that generalized integrated interleaving (GII) codes can be treated as a subclass of generalized tensor product codes, thus defining the exact relation between these codes. Finally, ME-LRCs are investigated in a probabilistic setting. We prove that ME-LRCs based upon a generalized tensor product construction can achieve the capacity of a compound erasure channel consisting of a family of erasure product channels. [ABSTRACT FROM AUTHOR]

Rate-compatible error-correcting codes (ECCs), which consist of a set of extended codes, are of practical interest in both wireless communications and data storage. In this work, we first study the lower bounds for rate-compatible ECCs, thus proving the existence of good rate-compatible codes. Then, we propose a general framework for constructing rate-compatible ECCs based on cosets and syndromes of a set of nested linear codes. We evaluate our construction from two points of view. From a combinatorial perspective, we show that we can construct rate-compatible codes with increasing minimum distances, and we discuss decoding algorithms and correctable patterns of errors and erasures. From a probabilistic point of view, we prove that we are able to construct capacity-achieving rate-compatible codes, generalizing a recent construction of capacity-achieving rate-compatible polar codes. Applications of rate-compatible codes to data storage are considered. We design two-level rate-compatible codes based on Bose-Chaudhuri-Hocquenghem (BCH) and low-density parity-check (LDPC) codes which are two popular codes widely used in the data storage industry, and then we evaluate the performance of these codes in multi-level cell (MLC) flash memories. We also examine code performance on binary and $q$ -ary symmetric channels. Finally, we briefly discuss two variations of our main construction and their relative performance. [ABSTRACT FROM AUTHOR]

In this paper, upper bound on the probability of maximum a posteriori (MAP) decoding error for systematic binary linear codes over additive white Gaussian noise (AWGN) channels is proposed. The proposed bound on the bit error probability is derived with the framework of Gallager's first bounding technique (GFBT), where the Gallager region is defined to be an irregular high-dimensional geometry by using a list decoding algorithm. The proposed bound on the bit error probability requires only the knowledge of weight spectra, which is helpful when the input-output weight enumerating function (IOWEF) is not available. Numerical results show that the proposed bound on the bit error probability matches well with the maximum-likelihood (ML) decoding simulation approach especially in the high signal-to-noise ratio (SNR) region, which is better than the recently proposed Ma bound. [ABSTRACT FROM AUTHOR]

Low density parity check (LDPC) code is a kind of linear block code with excellent performance which is proposed by Dr. Gallager. It overcomes the shortcomings of other error correcting codes and it is the nearest channel code from Shannon limit at the present discover. The decoding algorithms of LDPC code can reduce the decoding delay by the parallel decoding structure, so this has caused great concern in many fields. In recent years more and more scholars begin to study LDPC code, this makes the coding and decoding algorithms of LDPC code improved continuously. LDPC code has been widely used in many fields such as optical fiber communication, digital watermarking, underwater communication and deep space communication because of its excellent performance. Non-binary LDPC code has better performance compared with binary LDPC code. In this paper, FFT-BP decoding algorithm of non-binary LDPC code is studied, and on this basis, we proposed an improved FFT-BP algorithm. The improved decoding algorithm can effectively reduce the average iteration number. Finally, we achieved encode and decode algorithm of non-binary LDPC code with FPGA. [ABSTRACT FROM AUTHOR]

McEliece public-key crypto system is a public-key cryptosystem based on coding theory. Its security can be reduced to the general linear code decoding problem and it can resist quantum attack. This paper proposed an improved McEliece variant scheme based on QC-MDPC code and QC-LDPC code. The main improvement was that it combined the parity check matrices of QC-LDPC code and QC-MDPC code as a private key, and applied the concatenated codewords generated to the McEliece variant scheme, then gave out an improved decoding algorithm. The analysis shows that under the 80 bit security parameter, it has small system key and low-implement complexity. In addition, this system can resist the recently proposed key recovery attacks on QC-MDPC and QC-LDPC respectively. [ABSTRACT FROM AUTHOR]

Cyclic codes are a subclass of linear codes and have applications in consumer electronics, data storage systems and communication systems as they have efficient encoding and decoding algorithms. In this paper, we settle an open problem about a class of optimal ternary cyclic codes which was proposed by Ding and Helleseth [5]. Let C (1 , e) be a cyclic code of length 3 m − 1 over GF (3) with two nonzeros α and α e , where m and e are given integers, and α is a generator of GF (3 m) ⁎. It is shown that C (1 , e) is optimal with parameters [ 3 m − 1 , 3 m − 1 − 2 m , 4 ] if one of the following conditions is met. 1) m ≡ 0 (mod 4) , m ≥ 4 , and e = 3 m 2 + 5. 2) m ≡ 2 (mod 4) , m ≥ 6 , and e = 3 m + 2 2 + 5. [ABSTRACT FROM AUTHOR]

Multishot network coding is considered in a worst-case adversarial setting in which an omniscient adversary with unbounded computational resources may inject erroneous packets in up to $t$ links, erase up to $\rho $ packets, and wire-tap up to $\mu $ links, all throughout $\ell $ shots of a linearly-coded network. Assuming no knowledge of the underlying linear network code (in particular, the network topology and underlying linear code may be random and change with time), a coding scheme achieving zero-error communication and perfect secrecy is obtained based on linearized Reed-Solomon codes. The scheme achieves the maximum possible secret message size of $\ell n^\prime - 2t - \rho - \mu $ packets for coherent communication, where $n^\prime $ is the number of outgoing links at the source, for any packet length $m \geq n^\prime $ (largest possible range). By lifting this construction, coding schemes for non-coherent communication are obtained with information rates close to optimal for practical instances. The required field size is $q^{m} $ , where $q > \ell $ , thus $q^{m} \approx \ell ^{n^\prime } $ , which is always smaller than that of a Gabidulin code tailored for $\ell $ shots, which would be at least $2^{\ell n^\prime } $. A Welch-Berlekamp sum-rank decoding algorithm for linearized Reed-Solomon codes is provided, having quadratic complexity in the total length $n = \ell n^\prime $ , and which can be adapted to handle not only errors but also erasures, wire-tap observations and non-coherent communication. Combined with the obtained field size, the given decoding complexity is of $\mathcal {O}(n^{\prime 4} \ell ^{2} \log (\ell)^{2}) $ operations in $\mathbb {F}_{2} $ , whereas the most efficient known decoding algorithm for a Gabidulin code has a complexity of $\mathcal {O}(n^{\prime 3.69} \ell ^{3.69} \log (\ell)^{2}) $ operations in $\mathbb {F}_{2} $ , assuming a multiplication in a finite field $\mathbb {F} $ costs about $\log (|\mathbb {F}|)^{2} $ operations in $\mathbb {F}_{2} $. [ABSTRACT FROM AUTHOR]

In this paper, we analyze the tradeoff between coding rate and asymptotic performance of a class of generalized low-density parity-check (GLDPC) codes constructed by including a certain fraction of generalized constraint (GC) nodes in the graph. The rate of the GLDPC ensemble is bounded using classical results on linear block codes, namely, Hamming bound and Varshamov bound. We also study the impact of the decoding method used at GC nodes. To incorporate both bounded-distance (BD) and maximum likelihood (ML) decoding at GC nodes into our analysis without resorting on multi-edge type of degree distributions (DDs), we propose the probabilistic peeling decoding (P-PD) algorithm, which models the decoding step at every GC node as an instance of a Bernoulli random variable with a successful decoding probability that depends on both the GC block code and its decoding algorithm. The P-PD asymptotic performance over the BEC can be efficiently predicted using standard techniques for LDPC codes such as density evolution (DE) or the differential equation method. Furthermore, for a class of GLDPC ensembles, we demonstrate that the simulated P-PD performance accurately predicts the actual performance of the GLPDC code under ML decoding at GC nodes. We illustrate our analysis for GLDPC code ensembles with regular and irregular DDs. In all cases, we show that a large fraction of GC nodes is required to reduce the original gap to capacity, but the optimal fraction is strictly smaller than one. We then consider techniques to further reduce the gap to capacity by means of random puncturing, and the inclusion of a certain fraction of generalized variable nodes in the graph. [ABSTRACT FROM AUTHOR]

Cyclic codes are an interesting type of linear codes and have wide applications in communication and storage systems due to their efficient encoding and decoding algorithms. Inspired by the recent work on binary cyclic codes published in Tang and Ding (2022) [14] , the objectives of this paper are the construction and analyses of five infinite families of binary cyclic codes with parameters [ n , k ] and (n − 6) / 3 ≤ k ≤ 2 (n + 6) / 3. Three of the five families of binary cyclic codes and their duals have a very good lower bound on their minimum distances and contain distance-optimal codes. The other two families of binary cyclic codes are composed of binary duadic codes with a square-root-like lower bound on their minimum distances. As a by-product, two infinite families of self-dual binary codes with a square-root-like lower bound on their minimum distances are obtained. [ABSTRACT FROM AUTHOR]

In this paper, we describe a correspondence between a fuzzy linear code and a family of nested linear codes. We also describe the arithmetic of fuzzy linear codes. As a special class of nested linear codes, we consider a family of nested self-orthogonal codes. A linear code is self-orthogonal if it is contained in its dual and self-dual if it is equal to its dual. We introduce a definition of fuzzy self-dual or self-orthogonal codes which include classical self-dual or self-orthogonal codes. As examples, we construct several interesting classes of fuzzy linear codes including fuzzy Hamming codes, fuzzy Golay codes, and fuzzy Reed-Muller codes. We also give a general decoding algorithm for fuzzy linear codes. [ABSTRACT FROM AUTHOR]

An [ n , k , d ] linear code is said to be maximum distance separable (MDS) or almost maximum distance separable (AMDS) if d = n − k + 1 or d = n − k , respectively. If a code and its dual code are both AMDS, then the linear code is called a near maximum distance separable (NMDS) code. NMDS codes correspond to some interesting objects in finite geometry and have nice applications in cryptography. The NMDS codes constructed from elliptic curves are referred as elliptic curve NMDS codes. In this paper, by adding two suitable columns to the generator matrices of famous Reed-Solomon codes, we can obtain two families of NMDS codes with parameters [ q + 3 , 4 , q − 1 ] q (q is a prime power with gcd ⁡ (q − 1 , 3) = 1) and [ 2 m + 3 , 5 , 2 m − 2 ] 2 m respectively. These NMDS codes are shown to be linearly inequivalent to elliptic curve NMDS codes. Besides, the weight enumerators and locality of these NMDS codes are completely determined. It turns out that the resultant NMDS codes and their dual codes are mostly distance-optimal and dimension-optimal locally recoverable codes. [ABSTRACT FROM AUTHOR]

Twisted generalized Reed-Solomon codes are the generalization of generalized Reed-Solomon codes, due to their good algebraic structure and applications in cryptography, which have been widely studied in recent years. As a general algebraic decoding method for linear codes, the error-correcting pair exists in many classical linear codes. In this paper, we extend the error-correcting pair to twisted generalized Reed-Solomon codes. For twisted generalized Reed-Solomon codes with twist 1 or 2, we constructively show that the existence of the error-correcting pair. Moreover, we introduce the corresponding decoding procedure of twisted generalized Reed-Solomon codes by ℓ -error-correcting pairs and give several examples. [ABSTRACT FROM AUTHOR]

Our aim is the design of an efficient decoding algorithm in group codes. The algorithm is inspired by the well known syndrome decoding algorithm for linear codes and uses the decomposition of a semisimple group algebra K G as a direct sum of two-sided ideals, each of them generated by a central idempotent of K G. When G is an abelian group the algorithm can be modified to make it very simple and efficient. Some illustrative examples are presented. [ABSTRACT FROM AUTHOR]

Evaluating the block error rate of a digital communication system is usually done using the Monte Carlo (MC) simulation method. The main drawback of the Monte Carlo method is the need of a huge sample size for estimating low error rates. Other methods commonly used are the importance sampling technique and the quasi-analytical method. This paper introduces the metric star domain decoder model and shows that many practical decoders fall into this category. The main result is the introduction of a novel SNR-invariant quasi-analytical technique for estimating the block error rate of a communication link over the geodesic channel model (a generalization of a vast number of commonly used channels, including binary symmetric channel, BEC, and AWGN channel) with a metric star domain decoder used at the receiver. This technique outperforms the Monte Carlo and importance sampling methods in both accuracy and speed. It is shown that our quasi-analytical method is at least $10^{3}$ times faster than MC and 10 times faster than IS for the same accuracy. [ABSTRACT FROM AUTHOR]

A method is provided for constructing upper triangular square matrices over the univariate polynomial ring over a finite field, under certain constraints on the eigenvalues of the matrices. In some cases of interest, the degree of the determinant of such matrices is shown to be the smallest possible. The method is then applied to construct generator polynomial matrices of quasi-cyclic codes for correcting phased burst errors. Finally, an interpolation-based list decoding algorithm is presented for these codes, which, for a wide range of code parameters, is shown to outperform existing list decoding schemes. [ABSTRACT FROM AUTHOR]

Low density parity check code (LDPC) is a linear block code whose performance is close to Shannon's limit. Compared with other decoding algorithms, it has low decoding complexity and flexible structure. So it becomes people's research hotspots. In recent years, LDPC code codec algorithm has been improved, and is widely used in deep space communications, optical fiber communications, mobile communications and underwater and other fields. Using chaotic sequence single-layer mapping plus pixel scrambling can complete chaotic image encryption, because some chaotic sequence is poor robust, in the process of channel transmission, it is difficult to ensure that the information can be destroyed after the attack In this paper, LDPC codes are introduced, and in the chaotic image encryption, block coding is used to form error protection to improve the stability of the image transmission process and improve the transmission quality. [ABSTRACT FROM AUTHOR]

It has been discovered that linear codes may be described by binomial ideals. This makes it possible to study linear codes by commutative algebra and algebraic geometry methods. In this paper, we give a decoding algorithm for binary linear codes by utilizing the Groebner bases of the associated ideals. [ABSTRACT FROM AUTHOR]

Algorithms for secure encryption in a post-quantum world are currently receiving a lot of attention in the research community. One of the most promising such algorithms is the code-based scheme called QC-MDPC, which has excellent performance and a small public key size. In this paper, we present a very efficient key recovery attack on the QC-MDPC scheme using the fact that decryption uses an iterative decoding step, and this can fail with some small probability. We identify a dependence between the secret key and the failure in decoding. This can be used to build what we refer to as a distance spectrum for the secret key, which is the set of all distances between any two ones in the secret key. In a reconstruction step, we then determine the secret key from the distance spectrum. The attack has been implemented and tested on a proposed instance of QC-MDPC for 80-bit security. It successfully recovers the secret key in minutes. A slightly modified version of the attack can be applied on proposed versions of the QC-MDPC scheme that provides IND-CCA security. The attack is a bit more complex in this case, but still very much below the security level. The reason why we can break schemes with proved CCA security is that the model for these proofs typically does not include the decoding error possibility. At last, we present several algorithms for key reconstruction from an empirical distance spectrum. We first improve the naïve algorithm for key reconstruction by a factor of about 3 0000, when the parameters for 80-bit security are implemented. We further develop the algorithm to deal with errors in the distance spectrum. This ultimately reduces the requirement on the number of ciphertexts that need to be collected for a successful key recovery. [ABSTRACT FROM AUTHOR]

The interest in polar codes has been increasing significantly since their adoption for use in the 5th generation wireless systems standard. Successive cancellation (SC) decoding algorithm has low implementation complexity, but yields mediocre error-correction performance at the code lengths of interest. SC-Flip algorithm improves the error-correction performance of SC by identifying possibly erroneous decisions made by SC and re-iterates after flipping one bit. It was recently shown that only a portion of bit-channels are most likely to be in error. In this paper, we investigate the average log-likelihood ratio (LLR) values and their distribution related to the erroneous bit-channels, and develop the Thresholded SC-Flip (TSCF) decoding algorithm. We also replace the LLR selection and sorting of SC-Flip with a comparator to reduce the implementation complexity. Simulation results demonstrate that for practical code lengths and a wide range of rates, TSCF shows negligible loss compared with the error-correction performance obtained when all single-errors are corrected. At matching maximum iterations, TSCF has an error-correction performance gain of up to 0.45 dB compared with SC-Flip decoding. At matching error-correction performance, the computational complexity of TSCF is reduced by up to 40% on average and requires up to $5\times $ lower maximum number of iterations. [ABSTRACT FROM AUTHOR]