Search

In this paper, we provide an analysis of the performance of concatenation of polar codes with outer cyclic redundancy check (CRC) codes, separated by an interleaver, in the short and moderate block length regimes. The analysis addresses maximum likelihood decoding as a proxy to the code performance under successive cancellation list decoding. The analysis is carried out by introducing the concatenated polar code (CPC) ensembles, whose distance properties can be analyzed (for sufficiently short block lengths) by means of the uniform interleaver approach. At moderate block lengths, we resort to the Monte Carlo simulations. Results show that if the inner polar code possesses a low minimum distance and the outer CRC code has a sufficiently large amount of redundancy, then the choice of the outer code generator polynomial and the interleaver may yield to a large variability in the performance of the resulting CPC. [ABSTRACT FROM AUTHOR]

In this paper, we show how the presence of locality within a binary cyclic code can be exploited to improve decoding performance and to reduce decoding complexity. We pursue two approaches. Under the first approach, we show how the ordered statistics decoding (OSD) method can be modified by inserting a simple single round belief-propagation step at the start that involves only the local codes. The resultant locality-aware OSD algorithm yields an appreciable signal-to-noise ratio (SNR) gain for a given level of reliability and essentially the same level of decoder complexity. Under the second, trellis decoding approach, we show that the careful introduction of locality results in the creation of a cyclic subcode that possesses lower maximum state complexity. In addition, we present a simple means of deriving an upper bound to the state complexity profile of any cyclic code that is based only on the zeros of the code. Furthermore, we show how the decoding speed of either locality-aware OSD or trellis decoding can be significantly increased in the presence of locality, in the moderate-to-high SNR regime, by making the use of a quick-look decoder that often returns the maximum likelihood code word. [ABSTRACT FROM AUTHOR]

Locally repairable codes (LRCs) are introduced in distributed storage systems due to their low repair overhead. An LRC is called optimal if its minimum distance attains the Singleton-like upper bound. Chen et al. (2018) recently studied the constructions of optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ , where many classes of optimal cyclic constructions were obtained. In this paper, by employing constacyclic MDS codes, we construct seven classes of optimal $(r, \delta)$ -LRCs with new parameters. After adding these new optimal LRCs via constacyclic codes, we have completely obtained all optimal $(r, \delta)$ -LRCs with length $n \mid (q+1)$ and $(r+\delta -1) \mid n$ for all possible parameters for the completeness in the coding theory. It is worth noting that the optimal constacyclic LRCs with new parameters provide more alternatives to cyclic LRCs in the practical demands of distributed storage systems, where specific values of $n$ , $k$ , $r$ , and $\delta $ are required. Moreover, constacyclic LRCs also possess the encoding and decoding efficiency as cyclic LRCs. [ABSTRACT FROM AUTHOR]

The Fletcher checksum (FC) is a means of error detection that is analogous to cyclic redundancy checking but easier to implement in software. Now FC actually has two versions, one is Fletcher’s original paper version termed as FC and the other is RFC1146 version termed as FC-RFC. This paper shows that the FC is a cyclic code. This is done by introducing a cyclic code known as the cyclic Fletcher code (CFC) and then showing that the CFC is equivalent to the FC. The clear algebraic structure of cyclic codes is used to analyze the code block length and code distance, and then the single error correction, double error detection, and burst error detection of the CFC are analyzed. Also given is the mathematical relationship between the CFC and a modified FC. Finally, the issue of implementation is considered, and a new scheduling for the CFC is proposed to prevent data hazards. A simulation shows that the proposed scheduling offers improvements of at least 46% in throughput for the CFC and FC-RFC. [ABSTRACT FROM AUTHOR]

A linear network (LN) code can be described by either global encoding kernels (GEKs) or local encoding kernels (LEKs). In the literature, the multicast property of an LN code is described using GEKs, so the design algorithms for multicast LN codes employ GEKs to check this property. In this paper, a criterion is developed so that LEKs rather than GEKs can be used to check the multicast maximum distance separable (MDS) property of linear network error correction (LNEC) codes on erroneous networks. Further, it is used to develop a design algorithm for multicast MDS LNEC codes on erroneous cyclic networks. This algorithm is more efficient than the algorithm that uses GEKs when the number of edges is high and the interconnection of these edges is low. [ABSTRACT FROM AUTHOR]

Some nonlinear codes, such as Kerdock and Preparata codes, can be represented as binary images under the Gray map of linear codes over rings. This paper introduces MAP decoding of Kerdock and Preparata codes by working with their quaternary representation (linear codes over $\mathbb {Z}_{4}$) with the complexity of $\mathcal {O}(N^{2}\log _{2} N)$ , where N is the code length in $\mathbb {Z}_{4}$. A sub-optimal bitwise APP decoder with good error-correcting performance and complexity of $\mathcal {O}(N\log _{2} N)$ that is constructed using the decoder lifting technique is also introduced. This APP decoder extends upon the original lifting decoder by working with likelihoods instead of hard decisions and is not limited to Kerdock and Preparata code families. Simulations show that our novel decoders significantly outperform several popular decoders in terms of error rate. [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, compared with linear block codes. In this paper, seven classes of three-weight cyclic codes over \gf(p) whose duals have two zeros are presented, where p is an odd prime. The weight distributions of the seven classes of cyclic codes are settled. Some of the cyclic codes are optimal in the sense that they meet certain bounds on linear codes. The application of these cyclic codes in secret sharing is also considered. [ABSTRACT FROM AUTHOR]

The problem of identifying the channel code from a received sequence of noise-affected codewords is known as the blind reconstruction of channel codes. Blind reconstruction of channel codes is an important problem in military surveillance applications to identify the channel code used by an adversary. In this paper, we consider the problem of the blind reconstruction of the binary cyclic codes of unknown length from an unsynchronized bitstream (i.e., when the location of codeword boundaries is not known). For the blind reconstruction of cyclic codes, it is sufficient to identify the correct synchronization, the length, and the factors of the generator polynomial of the code. Toward this, we study the distribution of the syndromes (remainders) of the received polynomials with respect to a candidate factor of the generator polynomial. We prove that the probability of zero syndrome is maximum when all the parameters are correct. Using this result, the problem of the blind reconstruction of cyclic codes is formulated and solved as a hypothesis testing problem. [ABSTRACT FROM AUTHOR]

Many studies were carried out for the construction of low density parity-check (LDPC) codes. They usually focused on introducing the construction methods for good LDPC codes instead of a general method for code optimization. This paper proposes a method with high versatility, called the parallel vector message passing-based edge exchange (PMPE), for optimizing a type of graph-based LDPC codes, without changing the code parameters of mother codes, such as the code length, code rate, and degree distribution. With the approximately nearest codewords searching approach, we find the optimization method can increase the Hamming distance of the LDPC codes. For the quasi-cyclic (QC) LDPC codes, an optimization method, called the parallel vector message passing oriented-to the QC-LDPC codes (QC-PMP), is further suggested, with which the quasi-cyclic characteristics of QC-LDPC codes can remain unchanged in the optimization. To evaluate the performance of the parity-check matrix corresponding to a Tanner graph, a very simple metric, the cycles metric, is introduced to work with the proposed PMPE and QC-PMP algorithms. The experimental results show that the performance of the LDPC codes optimized with the proposed PMPE can be improved significantly at low BER range compared with the mother codes of the random codes, including the regular MacKay code of rate 0.5 and the regular PEG code of rate 0.9. For the case of the regular and irregular QC-LDPC codes with different code lengths and code rates, the optimized LDPC codes with the proposed QC-PMP algorithm significantly outperform the mother codes. [ABSTRACT FROM AUTHOR]

By introducing several levels of recoverability for locally recoverable codes (LRCs), LRCs with hierarchical locality (H-LRCs) are defined for correcting different numbers of erasures. There are two major ingredients in this paper. The first is to investigate some properties and existence conditions of optimal H-LRCs with respect to a generalized Singleton-like bound for H-LRCs. The second ingredient is to propose several constructions of optimal H-LRCs by employing cyclic codes. Notably, the parameters of these optimal H-LRCs are flexible. [ABSTRACT FROM AUTHOR]

The algebraic decoding of a $p$ -ary cyclic code consists of four steps: 1) computation of the known syndromes using the received word; 2) computation of the unknown syndromes from the known syndromes; 3) computation of the error positions by a use of the Berlekamp-Massey (BM) algorithm and Chien’s search; and 4) computation of the error values by solving a linear system. This paper addresses two problems of determining the error positions and computing the unknown syndromes. To solve the first problem, a new matrix, together with Gaussian elimination instead of the BM algorithm and Chien’s search, is proposed. In this new simplified decoder, finding an error-locator polynomial is completely avoided. A main advantage of the presented decoding method is when the Bose-Chaudhuri–Hocquenghem bound is unequal to the minimum distance of the code. Some cyclic codes, which do not have $2t$ consecutive known syndromes, can be decoded up to their actual minimum distance by using the presented matrix once. To solve the second problem, two algorithms for different square matrices reported recently by Lee et al. are also provided to calculate the value of an unknown syndrome. Finally, an algebraic decoding of the $(47,23,15)$ ternary cyclic code is given. [ABSTRACT FROM AUTHOR]

In this paper, we devise new scalable decoder architectures for Reed–Solomon (RS) codes, comprising three parts: error-only decoding, error-erasure decoding, and their decoding for singly extended RS codes. New error-only decoders are devised through algorithmic transformations of the inversionless Berlekamp–Massey algorithm (IBMA). We first generalize the Horiguchi–Koetter formula to evaluate error magnitudes using the error locator polynomial $\Lambda(x)$ and the auxiliary polynomial $B(x) $ produced by IBMA, which effectively eliminates the computation of error evaluator polynomial. We next devise an enhanced parallel inversionless Berlekamp–Massey algorithm (ePIBMA) that effectively takes advantage of the generalized Horiguchi–Koetter formula. The derivative ePIBMA architecture requires only $2t+1$ ( $t$ denotes the error correction capability) systolic cells, in contrast with $3t$ or more cells of the existing regular architectures based on IBMA or the Euclidean algorithm. Moreover, it may literally function as a linear-feedback-shift-register encoder. New error-erasure decoders are devised through algorithmic transformations of the inversionless Blahut algorithm (IBA) . The proposed split parallel inversionless Blahut algorithm (SPIBA) yields merely $2t+1$ systolic cells, which is the same number as the error-only decoder ePIBMA. The task is partitioned into two separate steps, computing the complementary error erasure evaluator polynomial followed by computing error-erasure locator polynomial, both utilizing SPIBA. Surprisingly, it has exactly the same number of cells and literally the same complexity and throughput as the proposed error-only decoder architecture ePIBMA; it employs 33% less hardware and at the same time achieves more than twice faster throughput, than the serial architecture IBA. we further propose a unified parallel inversionless Blahut algorithm (UPIBA) by incorporating the key virtues of the error-only decoder ePIBMA into SPIBA. The complexity and throughput of the rderivative UPIBA architecture are literally the same as ePIBMA and SPIBA, while performing almost equally efficiently as ePIBMA on error-only decoding and as SPIBA on error-erasure decoding. UPIBA also inherits the dynamic power saving feature of ePIBMA and SPIBA. Indeed, UPIBA renders highly attractive for on-the-fly implementation of error-erasure decoding. We finally demonstrate that the proposed decoders, i.e., ePIBMA, SPIBA, and UPIBA, can be magically migrated to decode singly extended RS codes, with negligible add-ons, except that an extra multiplexer is added to their critical paths. To the author's best knowledge, this is the first time that a high-throughput decoder for singly extended RS codes is explored. [ABSTRACT FROM PUBLISHER]

Two-dimensional (2D) cyclic codes are presented which correct any single occurrence of known 2D error patterns within a 2D array of bits. Applications for this type of codes include storage and display devices. The code construction begins with a generation of distinct syndrome sets for all targeted 2D error patterns. A method to refine the syndrome sets is then presented for making each syndrome set to contain distinct members, thereby guaranteeing full correction capability for the given list of known error patterns. Using an example construction, the effectiveness of the proposed coding approach is demonstrated versus the maximum-distance-separable (MDS) random-error-correcting code and known 2D burst-correcting codes for a 2D intersymbol interference (ISI) channel that yields a few dominant, but relatively large error patterns. [ABSTRACT FROM PUBLISHER]

Reed-Muller (RM) codes have recently regained some interest in the context of low latency communications and due to their relation to polar codes. RM codes can be constructed based on the Plotkin construction. In this work, we consider concatenated codes based on the Plotkin construction, where extended Bose-Chaudhuri-Hocquenghem (BCH) codes are used as component codes. This leads to improved code parameters compared to RM codes. Moreover, this construction is more flexible concerning the attainable code rates. Additionally, new soft-input decoding algorithms are proposed that exploit the recursive structure of the concatenation and the cyclic structure of the component codes. First, we consider the decoding of the cyclic component codes and propose a low complexity hybrid ordered statistics decoding algorithm. Next, this algorithm is applied to list decoding of the Plotkin construction. The proposed list decoding approach achieves near-maximum-likelihood performance for codes with medium lengths. The performance is comparable to state-of-the-art decoders, whereas the complexity is reduced. [ABSTRACT FROM AUTHOR]

Two new iterative soft decision decoding methods for Reed-Solomon (RS) codes are proposed. These methods are based on bit level belief propagation (BP) decoding. In order to make BP decoding effective for RS codes, we use an extended binary parity check matrix with a lower density and reduced number of 4-cycles compared to the original binary parity check matrix of the code. In the first proposed method, we take advantage of the cyclic structure of RS codes. Based on this property, we can apply the belief propagation algorithm on any cyclically shifted version of the received symbols with the same binary parity check matrix. For each shifted version of received symbols, the distribution of reliability values will change and deterministic errors can be avoided. This method results in considerable performance improvement of RS codes compared to hard decision decoding. The performance is also superior to some popular soft decision decoding methods. The second method is based on information correction in BP decoding. It means that we determine least reliable bits and by changing their channel information, the convergence of the decoder is improved. Compared to the first method, this method needs less BP iterations (less complexity) but its performance is not as good. [ABSTRACT FROM AUTHOR]