Search

This letter constructs the hard reliability from the syndromes to decode low/moderate-density parity-check codes in an ordered statistic way. For regular codes with our proposed decoding algorithm, the error-correction capability can be determined by the column weight and the maximum column intersection of their parity-check matrices. Then, an upper bound is derived to verify their decoding performance in ultra-low region, which may be required by some applications, e.g., McEliece public key cryptosystem and optical communications. It allows us to reduce the size of McEliece public keys with strong security levels due to its good error-correction capability. [ABSTRACT FROM AUTHOR]

This paper analyzes and explicitly constructs quasi-cyclic (QC) codes for correcting multiple bursts via matrix transformations. Our analysis demonstrates that the multiple-burst-correction capability of QC codes is determined by sub-matrices in the diagonal of their transformed parity-check matrices. By well designing these sub-matrices, the proposed QC codes are able to achieve optimal or asymptotically optimal multiple-burst-correction capability. Moreover, it proves that these codes can be QC low-density parity-check (QC-LDPC) codes, if the diagonal sub-matrices of their transformed parity-check matrices are Hadamard powers of base matrices. Analysis and simulation results show that our QC-LDPC codes perform well over not only random symbol error/erasure channels, but also burst channels. [ABSTRACT FROM AUTHOR]

This paper addresses binary message-passing (MP) decoding for nonbinary low-density parity-check (NB-LDPC) codes based on the binary image of Galois field symbols. The parity-check matrix of NB-LDPC codes in binary form is used to perform MP. The corresponding nonbinary check node (CN) update and variable node (VN) update can thus be decomposed to a set of binary sub-CN updates and sub-VN updates with much lower computational complexity. In particular, we start from adapting the binary parity-check matrix with Gaussian elimination. Then, we add redundant rows to the parity-check matrix instead of adaptation to further improve the performance. A min-max operation based on the expanded matrix is proposed for the CN update. It not only decreases the computational complexity incurred by Gaussian elimination but also improves the error performance. Simulation results show that the bit-level decoding with min-max operation can achieve similar error performance as the extended min-sum algorithm, but the computational complexity can be lower than the min-sum algorithm for binary LDPC codes. [ABSTRACT FROM AUTHOR]

Piggybacking is an efficient framework to reduce the repair bandwidth of distributed storage systems, especially, when the systems meet the settings–maximum distance separable (MDS), high code rate, and a small number of substripes. Through an analysis on the repair ratio of a piggybacking construction, this paper reveals that the proportion $p_{p}$ of piggybacking protected stripes is the key to significantly decrease the repair bandwidth. Based on this analysis, this paper proposes a repair efficient coding under piggybacking framework (REPB) by considering various piggybacking protected stripes and MDS only protected stripes. The repair ratio of REPB tends to 0 and is close to theoretical cut-set bound, as the proportion $p_{p}$ is no longer fixed at 1/2. Furthermore, the proposed REPB codes enjoy low computational complexity in repair operation. [ABSTRACT FROM AUTHOR]

Extensive studies have demonstrated the effectiveness and the flexibility of constructing capacity-approaching codes by block Markov superposition transmission (BMST). However, to achieve high performance, BMST codes typically require large encoding memories and large decoding window sizes, which result in high decoding complexity and high decoding latency. To address these issues, we introduce the recursive BMST (rBMST), in which the block-oriented feedback convolutional code is used instead of the block-oriented feedforward convolutional code of BMST. We propose to use a modified extrinsic information transfer chart analysis, which relates the mutual information to the bit error rate, to study the convergence behaviors of rBMST codes. On one hand, rBMST code shares most merits of BMST code, including near-capacity performance, low-complexity encoding, and flexible construction. On the other hand, compared with BMST code, rBMST code requires a smaller encoding memory, hence a lower decoding complexity, to approach the capacity. In particular, both analytical and simulation results show that rBMST code with encoding memory three reveals a lower error floor than the BMST code with encoding memory twelve. Furthermore, we show by analysis and simulations that rBMST with fixed encoding memory ( $m = 3$ ) and fixed decoding delay ( $d = 12$ ) can be used to construct capacity-approaching multiple-rate codes. Finally, the comparison between rBMST codes and spatially coupled low-density parity-check codes is carried out, which shows the advantages of rBMST codes in terms of performances and decoding complexities. [ABSTRACT FROM AUTHOR]

This letter discusses a secrecy transmission scheme based on 2-D polar coding over block fading wiretap channels. Unlike the previous approaches using 1-D polar coding, we propose to encode the secret bits in two dimensions to adapt to variation of the instantaneous secrecy capacity. In the proposed scheme, intra-block coding in one dimension is used to guarantee reliability, and cross-block coding in the other dimension is used to combat eavesdropping. Theoretical analysis demonstrates that our scheme is able to achieve the maximum perfect secrecy rate asymptotically. Simulation results show that the equivocation rate of eavesdropper is close to the secrecy capacity of the system with finite codelength. [ABSTRACT FROM PUBLISHER]

In the check node (CN) update of non-binary message-passing algorithms, each element of reliability vectors takes the same computational complexity. However, our analysis indicates that various elements in the same vector have various correct probabilities, thus have different contributions to error performance. In order to match computational complexity with correct probability, all elements in a vector are partitioned into different sets. For the extended min-sum (EMS) decoding, various strategies are applied for sets according to their correct probability. For the trellis-based EMS decoding, it is interesting that set partition only involves fixed paths, thus it does not need to search over the whole trellis of a CN. Complexity analysis and simulation results show that the proposed algorithms efficiently decode non-binary low-density parity-check codes, including ultra-sparse ones. [ABSTRACT FROM PUBLISHER]

This paper constructs an objective function for symbol flipping decoding algorithms, considering not only soft reliability, but also hard reliability. The maximization of this objective function indicates that the flipping metric should involve both the information before and after symbol flipping, while the existing algorithms consider the information before symbol flipping. Theoretical analysis shows that such prediction mechanism, together with hard reliability, can significantly improve the error performance of symbol flipping algorithms. Simulation results show that the proposed algorithms provide effective tradeoff between error performance and complexity for decoding non-binary LDPC codes. [ABSTRACT FROM PUBLISHER]

This paper presents two packings derived from balanced incomplete block designs to construct quasi-cyclic spatially coupled LDPC convolutional codes (SC-LDPC-CCs). The construction gives time-invariant codes, since the sub-blocks corresponding to each time instant of the parity-check matrix are identical. Moreover, it provides flexible design rates and constraint lengths. Simulation results show that the proposed packing-based SC-LDPC-CCs outperform the existing time-invariant codes and perform closely to the time-varying protograph-based codes. [ABSTRACT FROM AUTHOR]

In the soft-input soft-output Viterbi algorithm (SOVA), the log-likelihood ratio (LLR) of each bit is determined by the minimum metric difference between the ML path and its competitive paths. This paper proposes to trim large metric differences in order to reduce the complexity of SOVA. By trimming the metric differences, only a small number of backtracking operations are carried out, while many LLRs may be omitted as the result of the lack of metric differences. By revealing the relationship among neighboring LLRs, the omitted LLRs are estimated from its neighoring LLRs as well as intrinsic information. The extrinsic information transfer chart analysis demonstrates that the proposed algorithm has similar convergence behavior as the Log-MAP algorithm, if the trimming factor $M$ is moderate. Other analyses verify that our approach provides good LLR quality with only at most $1/M$ backtracking operations of SOVA. Simulation results show that it outperforms SOVA and performs as well as its variants and the Log-MAP algorithm. [ABSTRACT FROM AUTHOR]

The weighted bit-reliability-based (wBRB) algorithm for nonbinary LDPC codes suffers certain loss of symbol-reliability. Thus, this paper enhances its soft-decision version by passing multiple symbol-reliability instead of bit-reliability. Furthermore, it demonstrates that plurality robustly indicates symbol-reliability of extrinsic information-sums. Thus, this paper enhances the hard-decision version by introducing symbol-reliability from plurality. Analysis results show that these two enhanced decoding algorithms significantly outperform the wBRB algorithm with reasonable overhead. [ABSTRACT FROM PUBLISHER]

Message-passing decoders typically perform well for nonbinary low-density parity-check (NB-LDPC) codes with large computational complexity. As another type of simplified decoders, symbol-reliability-based decoders further reduce the computational complexity. However, the previously proposed algorithms suffer severe error performance degradation for NB-LDPC codes with low column weights. In this paper, a weighted bit-reliability based (wBRB) decoder for NB-LDPC codes is developed and implemented with efficient layered partial-parallel structure. It not only balances the tradeoff between complexity and error performance, but also reduces the memory usage significantly. Furthermore, to enhance the performance of the wBRB decoder, a full bit-reliability-based (FBRB) decoder is proposed. The FBRB decoder is derived based on the binary matrix representation of the nonzero entries in the parity-check matrix. Since more bit-reliability values are passed through the edges of the Tanner graph, the FBRB decoder can achieve better error performance and faster convergence rate than the wBRB decoder. Both of the decoders are implemented on a Xilinx Virtex-5 XC5VLX155T FPGA device for a (403,226) code over GF($2^5$). The results shows that they achieve 118.98 and 95.73 Mbps throughput with 15 iterations, respectively. [ABSTRACT FROM AUTHOR]

RS-LDPC codes, constructed based on the codewords of Reed-Solomon (RS) codes with two information symbols, are an important class of LDPC codes. In this paper, we present two representations, namely, quasi-cyclic (QC) representation and vector representation, for RS-LDPC codes. Under the first representation, most part of the parity-check matrix of a full-length RS-LDPC code consists of circulant permutation matrices and zero matrices. As a result, the class of codes can enjoy the advantages in hardware implementation as QC-LDPC codes. In addition, the base matrix under the QC representation of an RS-LDPC code can be explicitly given such that the rank of its parity-check matrix can be analyzed combinatorially. Under the second representation, each permutation matrix in the parity-check matrix of an RS-LDPC code is defined by a nonbinary vector, whose entries are a permutation of entries in the field from which the RS code is constructed. Then, the “affine invariance” property is proved for full-length RS-LDPC codes, which can facilitate the structural analysis of the codes. [ABSTRACT FROM PUBLISHER]

This paper presents bit-reliability based majority-logic decoding (MLgD) algorithms for non-binary LDPC codes. The proposed algorithms pass only one Galois field element and its reliability along each edge of the Tanner graph of a non-binary LDPC code. Since their reliability updates are in terms of bits rather than symbols, they are more efficient than traditional MLgD based decoding algorithms. By weighting the soft reliability of the extrinsic information-sums based on their hard reliability, the proposed algorithms can achieve good error performance for non-binary LDPC codes with various column weights. Moreover, their computational complexity and memory consumption are remarkably reduced compared with existing MLgD based decoding algorithms. As a result, they provide effective tradeoffs between error performance and complexity for decoding of non-binary LDPC codes. [ABSTRACT FROM AUTHOR]

This paper is concerned with construction and structural analysis of both cyclic and quasi-cyclic codes, particularly low-density parity-check (LDPC) codes. It consists of three parts. The first part shows that a cyclic code given by a parity-check matrix in circulant form can be decomposed into descendant cyclic and quasi-cyclic codes of various lengths and rates. Some fundamental structural properties of these descendant codes are developed, including the characterization of the roots of the generator polynomial of a cyclic descendant code. The second part of the paper shows that cyclic and quasi-cyclic descendant LDPC codes can be derived from cyclic finite-geometry LDPC codes using the results developed in the first part of the paper. This enlarges the repertoire of cyclic LDPC codes. The third part of the paper analyzes the trapping set structure of regular LDPC codes whose parity-check matrices satisfy a certain constraint on their rows and columns. Several classes of finite-geometry and finite-field cyclic and quasi-cyclic LDPC codes with large minimum distances are shown to have no harmful trapping sets of size smaller than their minimum distances. Consequently, their error-floor performances are dominated by their minimum distances. [ABSTRACT FROM PUBLISHER]

Codes constructed based on finite geometries form a large class of cyclic codes with large minimum distances which can be decoded with simple majority-logic decoding in one or multiple steps. In 2001, Kou, Lin and Fossorier showed that the one-step majority-logic decodable finite geometry codes form a class of cyclic LDPC codes whose Tanner graphs are free of cycles of length 4. These cyclic finite geometry LDPC codes perform very well over the AWGN channel using iterative decoding based on belief propagation (IDBP) and have very low error-floors. However, the standard IDBP is not effective for decoding other cyclic finite geometry codes because their Tanner graphs contain too many short cycles of length 4 which severely degrade the decoding performance. This paper investigates iterative decoding of two-step majority-logic decodable finite geometry codes. Three effective algorithms for decoding these codes are proposed. These algorithms are devised based on the orthogonal structure of the parity-check matrices of the codes to avoid or reduce the degrading effect of the short cycles of length 4. These decoding algorithms provide significant coding gains over the standard IDBP using either the sum-product or the min-sum algorithms. [ABSTRACT FROM AUTHOR]

Quasi-cyclic LDPC codes are the most promising class of structured LDPC codes due to their ease of implementation and excellent performance over noisy channels when decoded with message-passing algorithms as extensive simulation studies have shown. In this paper, an approach for constructing quasi-cyclic LDPC codes based on Latin squares over finite fields is presented. By analyzing the parity-check matrices of these codes, combinatorial expressions for their ranks and dimensions are derived. Experimental results show that, with iterative decoding algorithms, the constructed codes perform very well over the AWGN and the binary erasure channels. [ABSTRACT FROM PUBLISHER]

This paper presents two low-complexity reliability-based message-passing algorithms for decoding LDPC codes over non-binary finite fields. These two decoding algorithms require only finite field and integer operations and they provide effective trade-off between error performance and decoding complexity compared to the non-binary sum product algorithm. They are particularly effective for decoding LDPC codes constructed based on finite geometries and finite fields. [ABSTRACT FROM PUBLISHER]