Based on a recently proposed fast Fourier transform by Lin, Chung, and Han, this paper presents two fast erasure decoding algorithms for Reed–Solomon (RS) codes over binary extension fields of lengthNand dimensionK. The first algorithm applies to low-rate RS codes (i.e.,K/N≤ 0:5) and achieves a complexity ofO(N log K). The second algorithm applies to high-rate RS codes (i.e.,K/N≥ 0:5) and achieves a complexity ofO(N log(N–K)). Compared to recent state-of-the-art algorithms, both proposed algorithms achieve the best complexity, resulting in significant throughput improvements in Single Instruction Multiple Data (SIMD) based simulations. Besides yielding new fast algorithms for RS codes, this paper also presents a new interpolation formula, as well as related results, which may be of independent interest.

In this paper, we present a fast Chinese remaindering transform (FCRT) over finite fields by exploring Lin-Chung-Han (LCH)-FFT. We take a new approach to LCHFFT by formulating it as a procedure to compute a remainder tree. It is demonstrated that by adopting the Cantor basis for the underlying field$\mathbb{F}_{2} Q$of LCH-FFT, a special set of moduli$\left\{M_{i}(x): 0 \leq i \leq n-1\right\}$, termed “FFT-moduli”, can be picked from the remainder tree, satisfying that they reside in a subfield$\mathbb{F}_{2^{q}}$, specifically$M_{i}(x) \in \mathbb{F}_{2^{q}}[x]$, and that their degrees sum up to$N=\sum_{i=0}^{n-1} \operatorname{deg} M_{i}(x)=2^{Q}$. The FCRT is defined as taking a polynomial$f(x) \in \mathbb{F}_{2^{q}}[x]$of degree less than$N$as input and computing the remainders$\left\{f(x) \bmod M_{i}(x): 0 \leq i \leq n-1\right\}$as output. Since the FCRT realizes a subfield subtree within LCH-FFT, it requires$O(N \log N)$operations over$\mathbb{F}_{2 q}$. Potential applications in coding and secret sharing are also discussed.

Recently, Huang and Zhang [1], [2] introduced the derivative as a fundamental structure of cyclic codes, based on which the derivative decoding was further presented. It is well known that some cyclic codes constructed based on finite geometries form a special class of low-density parity-check (LDPC) codes, which perform well under the sum-product algorithm. In this paper, we study the derivative structure of Euclidean geometry (EG) codes, with a special interest in EG-LDPC codes. It is proved that for µ = m −2, the derivative ascendant of the extended (µ,s)th-order EG code of length 2msis the extended (µ+1,s)th-order twofold EG code of length 2ms. As a subcode of EG-LDPC code, the derivative descendant of the extend (1,s)th-order twofold EG code is characterized in terms of the roots of the generator polynomial. The new code relationship suggests that the twofold EG code can leverage the sum-product decoding of the derivative descendant for its derivative decoding.

Polar codes have been proven to be capable of achieving the optimal rate for the lossless compression problem. However, their finite-length performance is not satisfactory due to the insufficient polarization effect. In this work, we combine source polarization with several entropy coding techniques to improve the compression efficiency while keeping the additional complexity negligible. In our framework, the standard encoding of polar codes can be treated as a pre-transform on the source data, and only a small proportion of the transformed data needs further compression thanks to the source polarization. We show that our framework is compatible with the mainstream entropy coding schemes such as Huffman coding, arithmetic coding, and asymmetric number system (ANS). To optimize performance, an iterative algorithm is proposed for the set partitioning of the transformed data. Simulation results show that the improved scheme is superior to the original polar source coding.

In this paper, a new soft-decision decoding for extended Bose-Chaudhuri-Hocquenghem (eBCH) codes, referred to as CPC-SCL, is proposed, and it can achieve error-correction performance close to that of polarization-adjusted convolutional (PAC) codes in [1] when the code length n and dimension k are 128 and 64, respectively. Specifically, this paper first decomposes the eBCH code into a concatenated structure comprising an outer code and a Reed-Muller inner code. The outer code has a parity-check matrix characterized by a special block structure, which reveals that the positions of all frozen bits (including frozen zero bits and dynamic frozen bits) in the eBCH code are closely related to the index weights of elements from the perspective of the polar code. Subsequently, the CPC-SCL decoding of the eBCH codes is proposed by utilizing the cyclic property of codewords and parity-check-aided successive cancellation list (PC-SCL) decoding. Simulations also demonstrate that, over an additive white Gaussian noise (AWGN) channel with binary phase-shift keying (BPSK) modulation, the proposed decoding can achieve near maximum-likelihood (ML) performance at n = 64, k = 24 or 45.

Cyclic redundancy check-aided tail-biting convolutional code (CRC-TBCC) is considered as a competitive candidate for ultra-reliable and low-latency communications (URLLC) in short-length transmission scenarios. This paper focuses on designing efficient list decoders for CRC-TBCC and constructing rate-compatible CRC-TBCC (RC-CRC-TBCC). To reduce decoding complexity, we introduce a serial list Viterbi algorithm (SLVA) based on sectionalized trellises (ST), referred to as ST-SLVA. Comparative analysis reveals that ST-SLVA significantly lowers the decoding complexity. We then propose to use selectively multiplicative repetition (SMR) to construct high-performance rate-compatible CRC-TBCC. The resulting family of codes, called SMR-CRC-TBCCs, can be decoded with the same ST-SLVA. In SMR-CRC-TBCC, adjacent coded bits of CRC-TBCC are treated as symbols of a given finite field for multiplicative repetition, with priority given to the repetition of CRC-related symbols. Simulation results demonstrate that SMR-CRC-TBCC delivers excellent performance across various coding rates. Particularly, it performs better than CRC-aided Polar (CA-Polar) codes, LTE-Turbo codes, and parallel concatenated convolutional-block (PCCB) codes. These results strengthen the competitiveness of CRC-TBCC for 6G short-length communications.

This paper presents new variants of the Welch-Berlekamp algorithm that are favorable to hardware implementation. First, we derive the parallel Welch-Berlekamp (PWB) algorithm in a constructive manner based on the properties of solutions to the rational interpolation problem. The algorithm features the simultaneously performed discrepancy computation and polynomial update. Second, we explore the early-termination mechanism of the PWB algorithm for decoding of Reed-Solomon (RS) codes. By introducing the concept of incomplete error locator polynomial, we show that if$e \leq t$(whereeis the number of errors andtis the error correction capability), the PWB algorithm can be terminated at latest at the completion of the$(t+ e)$-th iteration. This leads to the early-terminating PWB (EPWB) algorithm. Finally, we develop frequency-domain versions of the PWB and EPWB algorithms, namely, FPWB and FEPWB. The key point toward the two algorithms is to replace the update of polynomial coefficients with the update of polynomial evaluations. It is worth noting that the FEPWB algorithm applies only to shortened RS codes. Furthermore, an efficient systolic architecture for the FPWB algorithm is designed, which is easily adapted for the FEPWB algorithm.

In this paper, we present an efficient decoding algorithm for a class of Reed-Solomon (RS) codes over Fermat field$\mathbb{F}_{2^{r}+1}$. We show that the Fermat number transform can be used to speed up the syndrome computation and the Chien search. The implementation architectures are designed for the two blocks. The key equation is then derived. When using the RS code in practice, there arises the issue that a$(2^{r}+1)$-ary symbol is less efficiently represented by a tuple of$(r+1)$bits. We present a nested coding scheme based on RS code and single parity-check (SPC) code to harness the inefficiency. A modified Wagner algorithm is proposed for decoding the inner (nonlinear) code and is proved to be an ML decoding over the BPSK-modulated AWGN channel. Simulation results show that the proposed RS-SPC nested coding scheme yields a considerable performance gain compared to the stand-alone RS coding scheme.

In this paper, we present a Reformulated Euclidean Algorithm (REA) and its optimized architecture for Reed-Solomon decoding. Through algorithm transformations on a modified Euclidean algorithm by Berlekamp et al., the REA is derived, featuring free of inversion operations. It has a fixed number 2$t$of iterations (t is the error-correction capability), and owns a very simple description. By generalizing the Horiguchi-Koetter formula and exploring the early termination mechanism, we present the optimized reformulated Euclidean algorithm (OREA). The derivative architecture is a systolic one, consisting of 2t + 1 processing elements (PEs) with the critical path of one multiplier and one adder. Complexity comparisons show that the proposed OREA saves 30% resources over sDCMEA, the state-of-art architecture based on Euclidean algorithm, and has almost the same (actually slight lower) complexity as ePIBMA, the state-of-art architecture based on Berlekamp-Massey algorithm. Thus this work fills an important gap for the hardware implementation between two RS decoding algorithms.

The Berlekamp-Massey algorithm is a primary algorithm for decoding Reed-Solomon codes. As an inherent property of the algorithm, the early termination can effectively reduce the latency and power of decoding. It has been known that the algorithm can be terminated at the completion of the$(t+e)$-th iteration (where$e$is the number of errors and$t$is the error-correction capability of the code). In this paper, we explore a new mechanism for the early termination. Specifically, assuming$e\leq t$, we present a detection method that can identify the$2e$-th iteration. Since the error locator polynomial will have been found at the completion of the$2e$-th iteration, we can terminate the algorithm at this point based on the proposed method. As an application, a hardware-friendly algorithm variant, dubbed Reformulated Early-Terminating Parallel Inversionless Berlekamp-Massey (RETPIBM) algorithm, is presented, which yields a systolic architecture. The derivative architecture consists of$3t+1$processing elements (PEs) and has the critical path of one multiplier and one adder. To the best of the authors' knowledge, this is literally the first architecture that achieves the early termination for Berlekamp-Massey algorithm.

In this paper, we present fast encoding algorithms for Hermitian codes based on the Lin-Chung-Han fast Fourier transform (LCH-FFT). For non-systematic encoding, we extend the LCH basis to the bivariate polynomial space and develop a two-dimensional FFT algorithm. For systematic encoding, we propose a modified partial FFT algorithm and present a procedure for computing the unknown intermediates. For a Hermitian code of length $n$, the computational complexity of the presented non-systematic and systematic encoding algorithms are both $O(n{\text{log}}n)$, improving upon the currently best-known encoding complexity $O\left( {n{\text{lo}}{{\text{g}}^2}n{\text{loglog}}n} \right)$.

This paper presents an early-termination method for the Welch-Berlekamp algorithm. Specifically, if e ≤ t (where e is the number of errors and t is the error correction capability), the Welch–Berlekamp algorithm can be terminated at latest at the completion of the (t + e)-th iteration. Based on the early-termination mechanism, a new variant of the Welch–Berlekamp algorithm called eFDMA is presented, and a systolic architecture is designed for the eFDMA algorithm. This provides an efficient implementation for the key equation solver for a new class of Reed–Solomon codes recently proposed by Lin et al. [9].

This paper presents a new erasure decoding algorithm for low-rate Reed–Solomon codes (rate ≤ 0.5) based on a recently proposed FFT known as LCH-FFT. The algorithm requires O(n log k) finite field operations, where n and k are the code’s length and dimension, respectively. Experiments based on the Intel AVX2 Instructions show that notable improvements in the throughput are achieved compared with the best-known algorithm with complexity O(n log n) (also based on LCH-FFT), and new speed records are created.

In this paper, we investigate the properties of the novel polynomial basis proposed by Lin, Chung, and Han over Cantor-constructed binary extension finite fields and propose an improved truncated LCH transform for discrete intervals. Incorporating these results leads us to the development of efficient encoding/decoding algorithms of (n,k) Reed-Solomon erasure codes with time complexity O(nlog(T)) and O (1) space complexity, where T < n. We also propose its performance-tuned variation of the decoding algorithm when only recovery of message symbols is concerned. Our experiment in the production environment indicates a performance gain of ×1 on average and ×2 at most towards the original decoder algorithm.

In this paper, we concentrate on one algebraic-based quasi-cyclic low-density parity-check (QC-LDPC) code constructed from two subsets of a finite field and generalize it to propose a class of variable-rate QC-LDPC (VR-QC-LDPC) codes, whose parity-check matrices are nested horizontally and have constant number of rows. Thus the proposed codes are significant at least in terms of storage complexity and can be simply implemented. The constructed codes also inherit the original algebraic-based QC-LDPC codes and their exponent matrices can be obtained from two subsets of the given finite field. We hereby analyze the structural properties from the isomorphism perspective, and present some rules to significantly prune the size of search space and determine the non-isomorphic exponent matrices. By distinguishing the smaller quantities of non-isomorphic matrices with cycle property metric, we can easily construct a series of nested exponent matrices with better cycle distributions and obtain the VR-QC-LDPC codes. Numerical results demonstrate that the constructed codes have better iterative decoding performance within a range of code rates and decoding iterations.

We study a class of finite geometry codes referred to as finite hyperplane codes, which are constructed based on hyperplanes and flats of a lower dimension in a finite geometry over the finite field F2s. We will determine the minimum distance for this class of codes and reveal a special property of them. In particular, we will show that for a finite geometry code based on flats of two non-consecutive dimensions, the error-correction capability guaranteed by Rudolph's one-step majority-logic decoding algorithm is less than or equal to that guaranteed by Reed-Massey's multi-step majority-logic decoding algorithm, with equality if and only if the code is a finite hyperplane code. In addition, both decoding algorithms can achieve the error-correction capability of finite hyperplane codes.

Let Xi, i E V form a Markov random field (MRF) represented by an undirected graph G = (V, E), and V' be a subset of V. We determine the smallest graph that can always represent the subfield Xi, i E V' as an MRF. Based on this result, we obtain a necessary and sufficient condition for a subfield of a Markov tree to be also a Markov tree. When G is a path so that Xi, i E V form a Markov chain, it is known that the I-Measure is always nonnegative (Kawabata and Yeung in 1992). We prove that Markov chain is essentially the only MRF such that the I-Measure is always nonnegative. By applying our characterization of the smallest graph representation of a subfield of an MRF, we develop a recursive approach for constructing information diagrams for MRFs. Our work is built on the set-theoretic characterization of an MRF (Yeung et al. in 2002).

Linear programming decoding with the alternating direction method of multipliers (ADMM) is a promising decoding technique for low-density parity-check (LDPC) codes, where the computational complexity of Euclidean projections onto check polytopes becomes a prominent problem. In this paper, the problem is circumvented by building lookup tables (LUTs) and quantizing the inputs to approach approximate Euclidean projections at low computational complexities. To challenge the huge memory cost of LUTs, we first propose two commutative compositions of Euclidean projection and self-map, and show the existence of a small quantization range which does not alter the Euclidean projection. Then, we investigate the design and simplification of the LUTs by exploiting the commutative compositions and check node decomposition techniques. An efficient algorithm for the LUT-based projection is demonstrated by using one simplification method. Simulation results show that for both the regular and irregular LDPC codes, the ADMM decoding using LUT-based projection can substantially reduce the decoding time while maintaining the error rate performance at a comparatively large memory cost.

A (v,g)-cage is a (not necessarily unique) smallest v-regular graph of girth g. On such a graph, a nonbinary (2,v)-regular low-density parity-check (LDPC) code can be defined such that the Tanner graph has girth 2g and the code length achieves the minimum possible. In this paper, we focus on two aspects of this class of codes, structural property and code optimization. We find that, in addition to those found previously, many cages can be used to construct structured LDPC codes. We show that all cages with even girth can be structured as protograph-based codes, many of which have block-circulant Tanner graphs. We also find that four cages with odd girth can be structured as protograph-based codes with block-circulant Tanner graphs. For code optimization, we develop an ontology-based approach. All possible inter-connected cycle patterns that lead to low symbol-weight codewords are identified to put together the ontology. By doing so, it becomes handleable to estimate and optimize distance spectrum of equivalent binary image codes. We further analyze some known codes from the Consultative Committee for Space Data Systems recommendation and design several new codes. Numerical results show that these codes have reasonably good minimum bit distance and perform well under iterative decoding.

For cyclic LDPC codes, we propose to use their automorphism groups to improve the iterative decoding performance. The basic idea is to construct nonequivalent parity-check matrices via column permutations. Three types of iterative decoders are devised to take advantage of the code's automorphism group. In this paper we focus on cyclic LDPC codes defined by a circulant parity-check matrix and consider two known subgroups of the automorphism group of a cyclic code. For the large class of idempotent-based cyclic LDPC codes in the literature, we show that the two subgroups only provide equivalent parity-check matrices and thus cannot be harnessed for iterative decoding. Towards exploiting the automorphism group of a code, we propose a new class of cyclic LDPC codes based on pseudo-cyclic MDS codes with two information symbols, for which nonequivalent parity-check matrices are obtained. Simulation results show that for our constructed codes of short lengths, the automorphism group can significantly enhance the iterative decoding performance.

Based jointly on idempotents and modular Golomb rulers, we construct a class of nonbinary cyclic low-density parity-check (LDPC) codes. The defining parity-check matrix is a sparse circulant, on which we put two constraints: 1) the characteristic polynomial is an idempotent, 2) the nonzero elements of the first row are located on a modular Golomb ruler. We show that the second constraint forms a necessary and sufficient condition for the Tanner graph to have no cycles of length 4. The minimum distance of the code is proved equal to the column weight of the parity-check matrix plus one. A search algorithm is presented, with which we obtain some high rate codes with large minimum distances. The issue of code equivalence is also discussed. Simulation results show that the obtained codes perform well under iterative decoding.

In this paper, we first propose a general framework for constructing quasi-cyclic low-density parity-check (QC-LDPC) codes based on a two-dimensional (2-D) maximum distance separable (MDS) code. Two classes of QC-LDPC codes are defined, whose parity-check matrices are transposes of each other. We then use a 2-D generalized Reed-Solomon (GRS) code to give a concrete construction. The decoding parity-check matrices have a large number of redundant parity-check equations while their Tanner graphs have a girth of at least 6. The minimum distances of the codes are very respectable as far as LDPC codes are concerned. We further show that many existing constructions of QC-LDPC codes based on finite fields in the literature can be unified under this construction. Experimental studies show that the constructed QC-LDPC codes perform well with the sum-product algorithm (SPA).