It has been shown that perturbations can improve the performance ofordered statistics decoding(OSD). In this paper, we focus on perturbations forderivative decoding based on OSD(DD-OSD) for cyclic codes, where the results of OSD in different derivative directions vote for the estimate of codewords. It reveals that thelocal maximum likelihood decoding (l-MLD) errors in derivative directions may trap DD-OSD. It proves that such traps can be detected by the null space of the derivative ascendants of cyclic codes, thereby guiding us to perform perturbations to avoid the traps. Simulation results show that perturbed DD-OSD with order-1 can achieve 1.3 dB gain over OSD with order-4 for extended BCH codes, and perform closely to maximum likelihood decoding with moderate complexity.

This paper proposes to construct binary array codes from nonbinary codes by binary matrix dispersion. Thanks to their low-density and quasi-cyclic generator matrices, thesebinary dispersed array codes(BDACs) enjoy low encoding complexity. Their reconstruction property is characterized through matrix transformation. Several explicit constructions of BDACs from minimum-bandwidth regenerating codes, piggybacking codes, and locally recoverable codes are presented, as well as their similar single-node repair strategies to their nonbinary counterparts.

It shows in [1], [2] that the performance of ordered statistics decoding (OSD) can be improved by derivative decoding (DD) for cyclic codes. Since error bits with high reliabilities may result in erroneous re-encoding, this paper proposes to further enhance DD-OSD by introducing perturbations on control band. Aided by the detection capability of cyclic codes on voted estimates of DD, the output decision is chosen sequentially from estimates given by different perturbations. Simulation results show that it can achieve 1.1 dB gain over DD-OSD for extended Bose-Chaudhuri-Hocquenghem codes, and performs closely to maximum likelihood decoding with moderate complexity.

This paper shows that projection-aggregation (PA) decoding of Reed-Muller (RM) codes can decode up to half the minimum distance d efficiently. By generalizing the false vote matrix from 1-dimensional to higher-dimensional subspaces, we prove that projecting onto disjoint subspaces, regardless of their dimensions, provides at most d/2 − 1 false votes for each codeword bit. Thus, d disjoint subspaces guarantee the correction for errors of d/2 − 1 or less. Moreover, the flexibility in subspace dimensions allows projecting into repetition codes directly, resulting in decoding efficiency. Finally, we prove that PA decoding with d disjoint subspaces decodes up to half the minimum distance in $O(n\sqrt n )$ for RM codes of length n and half rate or less.

MOTIVATION: Combinatorial pooling schemes have enabled the measurement of thousands of experiments in a small number of reactions. This efficiency is achieved by distributing the items to be measured across multiple reaction units called pools. However, current methods for the design of pooling schemes do not adequately address the need for balanced item distribution across pools, a property particularly important for biological applications. RESULTS: Here, we introduce balanced constant-weight Gray codes for detecting consecutive positives (DCP-CWGCs) for the efficient construction of combinatorial pooling schemes. Balanced DCP-CWGCs ensure uniform item distribution across pools, allow for the identification of consecutive positive items such as overlapping biological sequences, and enable error detection by ensuring a constant number of tests on each item and pair of consecutive items. For the efficient construction of balanced DCP-CWGCs, we have released an open-source python package codePUB, with implementations of the two core algorithms: a branch-and-bound algorithm (BBA) and a recursive combination with BBA (rcBBA). Simulations using codePUB show that our algorithms can construct long, balanced DCP-CWGCs that allow for error detection in tractable runtime. AVAILABILITY AND IMPLEMENTATION: The source code of codePUB is available at https://github.com/meyer-lab-cshl/codepub, with detailed documentation at https://codepub.readthedocs.io/.

This paper introduces theordered statistics decoding(OSD) without Gaussian elimination for affine-invariant codes based on theirderivative descendants(DDs). Based on the affine-invariant property, the reliable bits can be permuted into the information positions for re-encoding by an affine permutation. Moreover, it makes the information bits more reliable to perform the re-encoding process on not the original codes, but their DDs. Thanks to the much smaller dimension of our defined affine DDs, OSD can be carried out more efficiently. Simulation results show that the proposed ordered statistics derivative decoding can provide good performance without Gaussian elimination, even better than the conventional OSD with higher order.

Projection-aggregation decoding provides state-of-the-art performance for decoding Reed-Muller codes. This type of decoding relies on projecting onto subspaces, decoding the projections, and voting with the decoded projections. This paper investigates the decoding with a limited number of subspaces. By defining a false vote matrix, it demonstrates that this decoding suffers from coset error patterns, even when all projections are decoded successfully. These error patterns are of very small weights and thus induce a significant performance loss. Two rules are then proposed of which one reveals a trade-off between the subspace number and the error-correcting capability and the other provides a guideline for subspace selection. Simulation results verify that following the two rules alleviates the performance loss caused by the coset error patterns.

This paper proposes an integrated sensing and communications (ISAC) system based on affine frequency division multiplexing (AFDM) waveform. To this end, a metric set is designed according to not only the maximum tolerable delay/Doppler, but also the weighted spectral efficiency as well as the outage/error probability of sensing and communications. This enables the analytical investigation of the performance trade-offs of AFDM-ISAC system using the derived analytical relation among metrics and AFDM waveform parameters. Moreover, by revealing that delay and the integral/fractional parts of normalized Doppler can be decoupled in the affine Fourier transform-Doppler domain, an efficient estimation method is proposed for our AFDM-ISAC system, whose unambiguous Doppler can break through the limitation of subcarrier spacing. Theoretical analyses and numerical results verify that our proposed AFDM-ISAC system may significantly enlarge unambiguous delay/Doppler while possessing good spectral efficiency and peak-to-sidelobe level ratio in high-mobility scenarios.

This paper proposes to construct binary array codes from non-binary codes by binary matrix dispersion. Thanks to their low-density and quasi-cyclic (QC) generator matrices, the proposed codes enjoy low encoding complexity, about$1/(m+1)$of the XOR operations used in their counterparts over$\mathbf{G F}\left(2^m\right)$. Their maximum distance separable (MDS) property and repair can be efficiently analyzed via matrix transformation. The MDS property is ensured by introducing Vandermonde upper triangular form and pre-processing. Moreover, the efficient repair can be guaranteed by applying a matrix mapping called all-one superposition on the associated matrices. Analysis indicates that their code rate and repair ratio asymptotically approach those of their non-binary counterparts.

The recursive projection-aggregation (RPA) algorithm provides state-of-the-art performance for Reed-Muller (RM) codes. It relies on projecting onto subspaces, decoding projections and voting. This paper explores the error-correction capability of RPA with a limited number of subspaces. By constructing a false vote matrix, it demonstrates that RPA may fail to correct coset error patterns, even when all projections are decoded successfully. These patterns severely degrade the decoding performance due to their small weights. Thus, two rules on the subspace selection are derived to guarantee the error-correction capability of RPA. Simulation results verify that the two rules dominate the decoding performance of RPA.

This paper defines cyclic and minimal derivative descendants (DDs) of an extended cyclic code from the derivative of Mattson-Solomon polynomials. First, it demonstrates that the cyclic DDs are the same extended cyclic code. It allows us to efficiently decode extended cyclic codes based on their cyclic DDs. Second, since the minimal DDs are equivalent codes, it also allows us to perform soft-decision decoding based on the minimal DDs with permutations. Simulation result shows that our proposed derivative decoding can be close to the maximum likelihood decoding for certain extended cyclic codes, including some extended BCH codes.

In this paper, we consider a cooperative communication network where multiple low-Earth-orbit (LEO) satellites provide services to multiple ground users (GUs) cooperatively at the same time and on the same frequency. The multi-satellite cooperation has great potential in extending communication coverage and increasing spectral efficiency. Considering that the on-board radio-frequency circuit resources and computation resources on each satellite are restricted, we aim to propose a low-complexity yet efficient multi-satellite cooperative transmission framework. Specifically, we first propose a hybrid beamforming method consisting of analog beamforming for beam alignment and digital beamforming for interference mitigation. Then, to establish appropriate connections between the satellites and GUs, we propose a heuristic user scheduling algorithm which determines the connections according to the total spectral efficiency increment of the multi-satellite cooperative network. Next, considering the intrinsic connection between beamforming and user scheduling, a joint hybrid beamforming and user scheduling (JHU) scheme is proposed to dramatically improve the performance of the multi-satellite cooperative network. In addition to the single-connection scenario, we also consider the multi-connection case using the JHU scheme. Extensive simulations conducted over different LEO satellite constellations and across various GU locations demonstrate the superiority of the proposed schemes in both overall and per-user spectral efficiencies.

This paper defines minimal derivative descendants (DDs) of an extended cyclic code from the derivative of Mattson-Solomon polynomials. It proves that the minimal DDs in different directions are equivalent codes. This allows us to perform derivative decoding based on decodings for minimal DDs with cyclic shifting. In particular, the small dimension and the large minimum Hamming distance of minimal DDs make it attractive to perform derivative decoding based on the ordered statistics decoding (OSD). Simulation results show that the derivative decoding based on the OSD can provide considerable gain.

This paper considers the parity-check matrix of a maximum distance separable (MDS) array code as a superposition of two matrices, block diagonal matrix A and side matrix S. By matching their entries, the syndrome calculation of the matrix A can share computations with that of the side matrix S. Then, a low-complexity encoding, referred to as side encoding, is proposed to encode matched MDS array codes efficiently. Moreover, it can combine with the Reed-Muller transform-based (RMTB) Reed-Solomon encoding algorithm to reduce the encoding complexity further. The analysis indicates that for the MDS array code [1] with four parity nodes, the number of multiplications is reduced by 85.4% and 52.6% compared to the traditional encoding and only RMTB encoding, respectively.

In this paper, we consider a cooperative communication network where multiple satellites provide services for ground users (GUs) (at the same time and on the same frequency). The communication and computational resources on satellites are usually restricted and the satellite-GU link determination affects the communication performance significantly when multiple satellites provide services for multiple GUs in a collaborative manner. Therefore, considering the limitation of the on-board radio-frequency chains, we first propose a hybrid beamforming method consisting of analog beamforming for beam alignment and digital beamforming for interference mitigation. Then, to establish appropriate connections between satellites and GUs, we propose a heuristic user scheduling algorithm which determines the connections according to the total spectral efficiency (SE) increment of the multi-satellite cooperative network. Next, a joint hybrid beamforming and user scheduling scheme is proposed to dramatically improve the performance of the multi-satellite cooperative network. Moreover, simulations are conducted to compare the proposed schemes with representative baselines and analyze the key factors influencing the performance of the multi-satellite cooperative network. It is shown that the proposed joint beamforming and user scheduling approach can provide 47.2% SE improvement on average as compared with its non-joint counterpart.

Coded distributed computing can alleviate the communication load by leveraging the redundant storage and computation resources with coding techniques in distributed computing. In this paper, we study a MapReduce-type distributed computing framework over star topological network, where all the workers exchange information through a common access point. The optimal tradeoff among the normalized number of stored files (storage load), computed intermediate values (computation load), and transmitted bits in the uplink and downlink (communication loads) is characterized. A coded computing scheme is proposed to achieve the Pareto-optimal tradeoff surface, in which the access point only needs to perform simple chain coding between the signals it receives, and information- theoretical bound matching the surface is also provided.

Constructions of high-performance hard-decision decodable error correction codes are important for high-speed communication systems. In this paper, we present the generalized integrated interleaved (GII) zipper codes, in which multiple zipper codes are coupled together by the constraint of the GII code. The resulting codes are referred to as GII-zipper codes. Firstly, since the performances of GII-zipper codes are sensible to miscorrections, we propose an enhanced anchor decoder (AD) which uses the hard-decision results during the GII decoding to assign anchor reliability to reduce miscorrections. We then analyze the size and multiplicity of the minimum-sized stall patterns (MSSPs) of the GII-zipper codes. The analytical results show that the size of the MSSPs of the GII-zipper codes is larger that of the zipper codes. Finally, we present extensive simulation results to show the performance advantages of the GII-zipper codes. The results show that, when decoded with the original AD, the GII-zipper codes perform better than the comparable zipper codes and we can obtain further performance gain by the enhanced AD. Particularly, a GII-staircase code with a rate of 0.846 can achieve 0.74 dB from capacity at a bit error rate (BER) of 10−15.

To achieve various tradeoffs between storage and repair bandwidth, this article proposes to construct exact repair codes by grafting two codesC1andC2. By replacing certain nonzero entries in the generator matrix ofC1by zero, the repair bandwidth of the resulting grafting part decreases. However, it may no longer keep the maximum-distance-separable (MDS) property. As a result, the grafted codeC2takes these nonzero entries into account such that the entire graftage code can keep the MDS property. The relationship between the bandwidth reduction ofC1and the file size ofC2is derived to optimize graftage codes. Our analysis indicates that these graftage codes may provide better tradeoffs than space-sharing.

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.

Quantum secure direct communication (QSDC) is capable of direct confidential communications over a quantum channel, which is achieved by dispensing with the key agreement channel of the well-known quantum key distribution (QKD). However, to make QSDC a practical reality, we have to mitigate its reliance on quantum memory, its immediate communication interruption caused by eavesdropping and its low transmission reliability due to the heavy qubit losses. Hence a new QSDC protocol is proposed based on a sophisticated coded single-photon DL04 QSDC protocol to tackle the open challenges. In particular, quantum memory is dispensed with and a high-accuracy secrecy capacity estimate is derived for this protocol by conceiving dynamic joint encryption and error-control (JEEC) coding. We demonstrate that this quantum-memory-free DL04 QSDC (QMF-DL04 QSDC) protocol inches closer to the quantum channel's capacity and significantly improves the original DL04 QSDC's robustness. Moreover, a rate-compatible low-rate JEEC coding scheme is designed for the proposed framework, and the JEEC code advocated is shown to approach the secrecy capacity, despite tolerating an extremely high loss of qubits in the time-varying wiretap channel. Our simulations and experimental results demonstrate that the QMF-DL04 QSDC scheme significantly increases both the secure information rate and the communication distance of the original DL04 protocol.

In this paper, we introduce a novel method, called doubly-recursive block Markov superposition transmission (DrBMST), to construct high-performance spatially coupled codes. An important characteristic of DrBMST codes is that the degrees of the constraint nodes in their normal graphs are at most three. As a result, DrBMST codes can be decoded with low complexity. We first prove that the error probability of an enlarged DrBMST code ensemble can be made arbitrarily small under windowed maximum-likelihood decoding (MLD) by increasing the decoding window size. This result partially explains the superior performances of DrBMST codes. Then we propose to use the extrinsic information transfer (EXIT) chart analysis to estimate the iterative windowed decoding thresholds of DrBMST codes. The EXIT chart analyses show that, with such a simple structure, DrBMST codes are comparable to BMST codes with large encoding memories in terms of decoding thresholds. Finally, we carry out comparisons to validate the advantages of DrBMST codes in terms of error performances and decoding complexities. In particular, for a decoding latency of 20,000 bits, the DrBMST code performs better than the (4, 8)-regular spatially coupled low-density parity-check (SC-LDPC) code, but with lower computational complexity. Hence, DrBMST codes can be used in communication systems with limited computational resources. In addition, we show that DrBMST can be used to construct multiple-rate codes.

This paper shows that the error probability of a querying policy for noisy 20 questions is upper bounded by the minimum Hamming distance of its querying matrix. Following this distance principle, sparse querying matrices with the row-column constraint are constructed for the scenarios, where only limited areas can be detected at each querying round. It demonstrates that the row-column constraint promises a large minimum distance to ensure low error probability of queries. Moreover, the proposed sparse matrices with random block coding provide unequal error-protection capability to further improve the querying accuracy under the scenarios of detecting half of the areas. Simulation results verify that the quantized mean squared errors of our proposed policies outperform those of the existing policies under the above scenarios.

Recently, several remarkable works [1]-[5] constructed regenerating codes to offer intermediate tradeoffs between storage and bandwidth. Unlike regenerating codes, this paper proposes to graft codes together to provide various such intermediate tradeoffs. It shows that the linear relations in the generator matrices of grafting codes can be transferred to those of grafted codes without any loss of reconstruction capability. A construction based on minimum storage regenerating codes shows that the resulted graftage codes may provide better tradeoffs than space-sharing and approach cut-set bounds, with the cost of fixed access of helper nodes.

This paper proposes to construct a class of multiple-burst-correction quasi-cyclic (QC) codes via matrix transformations. Due to the diagonal structure of the transformed parity-check matrix of a QC code, multiple bursts can be corrected in the transform domain. By well designing the diagonal submatrices, the constructed QC codes are able to achieve optimal or asymptotically optimal multiple-burst-correction capability. In particular, a subclass of our constructed QC codes are QC low-density parity-check (QC-LDPC) codes which also perform very well over random channels. Simulation results show that our QC-LDPC codes outperform the existing QC-LDPC codes over burst channels.

In this paper, we introduce the doubly recursive block Markov superposition transmission (DrBMST) of short code. An important characteristic of DrBMST codes is that the degrees of the constraint nodes in their normal graphical realizations are at most three. As a result, DrBMST codes can be decoded with low complexity. We propose to use an enlarged code ensemble to analyze the performance of DrBMST under windowed maximum likelihood decoding. Further, the extrinsic information transfer (EXIT) chart analysis is used to study the iterative decoding thresholds of DrBMST code ensembles. The EXIT analysis shows that the iterative decoding thresholds of DrBMST code ensembles are comparable to those of the BMST codes. We have also compared the error performance and the decoding complexity of finite-length DrBMST codes with regular spatial-coupled low-density parity-check (SC-LDPC) codes under equal decoding latency. The comparison results show that the DrBMST code performs about 0.1 dB better than a (4, 8)-regular SC-LDPC code, but with lower computational complexity.

Recently, Lin, Chung, and Han presented an efficient additive fast Fourier transform based on a novel polynomial basis. This paper explains clearly and proves the convolution theorem of Lin-Chung-Han (LCH) transform. It demonstrates that the corresponding convolutions of LCH transform can be equivalent to cyclic convolutions by preprocessed modulo and polynomial bases conversion. As a result, this paper proposes a fast algorithm for the multiplication of a vector and a circulant matrix. It shows that the algorithm performs very efficient for the encoding of nonbinary quasi-cyclic codes. For an (ne, ke) quasi-cyclic code with circulant size of e, the encoding algorithm needs approximately 1/4n(e+1)log22(e+1)+k(n-k)(e+1) multiplications and additions, which is much less than the number (n-k)ke2of traditional encoding algorithm.

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 ppof 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 ppis no longer fixed at 1/2. Furthermore, the proposed REPB codes enjoy low computational complexity in repair operation.

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.

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.

Unreliable message storage severely degrades the performance of LDPC decoders. This paper discusses the various impacts of bit errors of finite-precision messages on LDPC decoders. Discrete density evolution indicates that the sign bits of finite-precision messages have the most influence on the decoding threshold. As a result, this paper proposes to protect the sign bits of messages by Hamming product codes. Simulation results show that the proposed scheme only has a degradation of 0.1 dB for the LDPC decoder with a storage error ratio of 0.001, which outperforms the traditional triple modular redundancy scheme.

Extensive studies have demonstrated the effectiveness 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 increased decoding complexity and decoding latency. To address this issue, we introduce the recursive BMST (rBMST), in which block-oriented feedback convolutional code is used instead of the block-oriented feedforward convolutional code. We propose to use a modified extrinsic information transfer (EXIT) chart analysis to study the convergence behavior 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, analytical results show that, rBMST code ensemble with encoding memory three reveals a lower error-floor than the BMST code ensemble with encoding memory twelve.

Linear index coding is generally more robust against channel variations as compared to the fixed-to-variable length coding. This paper proposes a novel multi-pass decoding approach to decode linear index coded images. In contrast to the typical one-pass decoding, the proposed scheme harnesses the information recovered in the first decoding pass with the source statistics and utilize it in the subsequent decoding passes. It is demonstrated that the linear index coded image transmitted from deep-space shows an improvement of up to 3.2 dB in terms of reconstructed peak signal to noise ratio by using multi-pass decoding.

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.

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.

Due to a production error, an equation in the above paper[1]appeared incorrectly. Below is the correct version.

This paper reduces the complexity of decoding non-binary low-density parity-check (LDPC) codes by set partition. In the check node update, the input vectors are partitioned into several sets such that different elements in the virtual matrix enjoy various computational strategies. As a result, the proposed algorithm achieves high computational efficiency by setting strategies according to the correct probability of these elements. Simulation results indicate that it significantly decreases the complexity of check node update with negligible performance loss.

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.

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(25). The results shows that they achieve 118.98 and 95.73 Mbps throughput with 15 iterations, respectively.

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.

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.

The traditional majority-logic decoding (MLgD) based algorithms suffer error-floors for decoding non-binary LDPC codes with small column weights. This paper presents a bit-reliability based MLgD (BRB-MLgD) algorithm with low error-floors for non-binary LDPC codes. The proposed algorithm is carried out based on the binary representations of non-binary symbols. The reliability update along each edge of the Tanner graph of a non-binary LDPC code is in terms of bits rather than symbols. Thus, its computational complexity and memory consumption are less than those of the existing MLgD based algorithms. Simulation results indicate that the proposed algorithm can significantly reduce error-floors with small performance degradation in the waterfall region.

This letter presents a robust solution for joint sparse recovery (JSR) under impulsive noise. The unknown measurement noise is endowed with the Student-t distribution, then a novel Bayesian probabilistic model is proposed to describe the JSR problem. To effectively recover the joint row sparse signal, variational Bayes (VB) method is introduced for Bayesian theory based JSR algorithms such that it overcomes the intractable integrations inherent. Simulation results verify that the proposed algorithm significantly outperforms the existing algorithms under impulsive noise.

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.

The efficient encoding of quasi‐cyclic (QC) low‐density parity‐check (LDPC) codes is based on generator matrices in systematic‐circulant (SC) form. The cost of the encoders of QC‐LDPC codes mainly depends on the number of non‐zero entries in the SC generator matrices. This study introduces a novel construction of SC generator matrices based on matrix transformations via Galois Fourier transform. By revealing the structure of SC generator matrices in the transform domain, an algorithm is proposed to reduce the density of the generator matrices of QC‐LDPC codes. Furthermore, a tight upper bound on ranks of QC matrices is derived. Based on the bound, rank distributions of parity‐check matrices and generator matrices in the transform domain illustrate the efficiency of the proposed algorithm. Simulation results show that the density of their SC generator matrices can be significantly decreased with moderate computational complexity.

This paper presents two novel low-complexity encoding algorithms for quasi-cyclic (QC) codes based on Galois Fourier transform. The key idea behind them is making use of the block diagonal structure of the transformed generator matrix. The first one, named encoding by Galois Fourier transform, is equivalent to the fast implementations of the traditional encoding by Galois Fourier transform. The second one, named encoding in the transform domain (ETD), requires much less computational complexity for encoding binary QC codes. It skips the first step of the first algorithm and applies post-processing to save a large number of Galois field multiplications. Its application to QC-LDPC codes is also studied in this paper. Particularly, the hardware cost of the ETD for RS-based LDPC codes can be greatly reduced by short linear-feedback shift registers.

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.

This paper presents a novel low-complexity encoding algorithm for binary quasi-cyclic (QC) codes based on matrix transformation. First, a message vector is encoded into a transformed codeword in the transform domain. Then, the transmitted codeword is obtained from the transformed codeword by the inverse Galois Fourier transform. Moreover, a simple and fast mapping is devised to post-process the transformed codeword such that the transmitted codeword is binary as well. The complexity of our proposed encoding algorithm is less than ek(n-k)log2e+ne(log22e+log2e)+ n/2 elog32e bit operations for binary codes. This complexity is much lower than its traditional complexity 2e2(n - k)k. In the examples of encoding the binary (4095, 2016) and (15500, 10850) QC codes, the complexities are 12.09% and 9.49% of those of traditional encoding, respectively.

This paper is concerned with general analysis on the rank and row-redundancy of an array of circulants whose null space defines a QC-LDPC code. Based on the Fourier transform and the properties of conjugacy classes and Hadamard products of matrices, tight bounds on rank and row-redundancy are derived, which make it possible to consider row-redundancy in constructions of QC-LDPC codes to achieve better performance. Moreover, a new construction of QC-LDPC codes from random partitions of finite fields, which has flexible code dimensions and is abundant in row-redundancy, is presented and analyzed.

A matrix-theoretic approach for studying quasi-cyclic codes based on matrix transformations via Fourier transforms and row and column permutations is developed. These transformations put a parity-check matrix in the form of an array of circulant matrices into a diagonal array of matrices of the same size over an extension field. The approach is amicable to the analysis and construction of quasi-cyclic low-density parity-check codes since it takes into account the specific parity-check matrix used for decoding with iterative message-passing algorithms. Based on this approach, the dimension of the codes and parity-check matrices for the dual codes can be determined. Several algebraic and geometric constructions of quasi-cyclic codes are presented as applications along with simulation results showing their performance over additive white Gaussian noise channels decoded with iterative message-passing algorithms.

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.

In this paper, a class of product codes based on low-density parity check (LDPC) constituent codes are constructed for multiple phased-burst erasure correction (MPBEC). These codes are shown to correct one large burst and/or a number of shorter bursts. A simple novel recursive erasure correction algorithm is proposed based on a recently discovered zero-span approach to linear block code analysis that can produce very powerful MPBEC capabilities. Analysis and data on how these codes work for additive white Gaussian noise (AWGN) channel are also presented.

Several classes of quasi-cyclic LDPC codes have been proposed in the literature and shown to have excellent performance over noisy channels when decoded with iterative message-passing algorithms. However, by and large, important properties of the codes, including their dimensions, are only given for specific codes based on computer programming. Using Fourier transforms, it is shown that the ranks of parity-check matrices of quasi-cyclic codes can be computed. From these ranks, the dimensions of the codes can be determined. The approach, which unifies most of the known algebraic constructions, is given in detail for three large classes of quasi-cyclic LDPC codes which appear in the literature.

THIS PAPER IS ELIGIBLE FOR THE STUDENT PAPER AWARD. This paper analyzes trapping set structure of binary regular LDPC codes whose parity-check matrices satisfy the constraint that no two rows (or two columns) have more than one place where they both have non-zero components, which is called row-column (RC) constraint. For a (γ,ρ)-regular LDPC code whose parity-check matrix satisfies the RC-constraint, its Tanner graph contains no (κ, τ) trapping set with size κ ≤ γ and number τ of odd degree check nodes less than γ. For several classes of RC-constrained regular LDPC codes constructed algebraically, we show that their Tanner graphs contain no trapping sets of sizes smaller than their minimum weights.

Error-floors are the main reason for excluding LDPC codes from applications requiring very low bit-error rate. They are attributed to a particular structure in the codes' Tanner graphs, known as trapping sets, which traps the message-passing algorithms commonly used to decode LDPC codes, and prevents decoding from converging to the correct codeword. A technique is proposed to break trapping sets while decoding. Based on decoding results leading to a decoding failure, some bits are identified in a previous iteration and flipped and decoding is restarted. This backtracking may enable the decoder to get out of the trapped state. A semi-analytical method is also proposed to predict the error-floor after backtracking. Simulation results indicate the effectiveness of the proposed technique in lowering the error-floor. The technique, which has moderate complexity overhead, is applicable to any code without requiring a prior knowledge of the structure of its trapping sets.

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.

Flash memory is a nonvolatile computer storage device which consists of blocks of cells. While increasing the voltage level of a single cell is fast and simple, reducing the level of a cell requires the erasing of the entire block containing the cell. Since block-erasures are costly, flash coding schemes have been developed to maximize the number of writes before a block-erasure is needed. A novel coding scheme based on error-correcting codes is presented that allows the cell levels to increase as evenly as possible and as a result, increases the number of writes before a block-erasure. The scheme is based on the premise that cells whose levels are higher than others need not be increased. This introduces errors in the recorded data which can be corrected by an error-correcting code provided that the number of erroneous cells is within the error-correcting capability of the code. The scheme is also capable of combating noise, causing additional errors and erasures, in flash memories in order to enhance data reliability. For added flexibility, the scheme can be combined with other flash codes to yield concatenated schemes of high memory rates.

Flash memory is a non-volatile computer storage device which consists of blocks of cells. While increasing the voltage level of a single cell is fast and simple, reducing the level of a cell requires the erasing of the entire block containing the cell. Since block erasures are costly, traditional flash coding schemes have been developed to maximize the number of writes before a block erasure is needed. A novel coding scheme based on error-correcting codes allows the cell levels to increase as evenly as possibly and as a result, increases the number of writes before a block erasure. The scheme is also capable of combating noise in flash memories in order to enhance data reliability.

This paper presents a novel low-complexity iterative reliability-based decoding algorithm for LDPC codes over q-ary finite fields. This proposed algorithm has low complexity and hence provides an effective trade-off between error performance and decoding complexity compared to q-ary sum product algorithm. This decoding algorithm is devised based on simple orthogonal concept of one-step majority-logic decoding for q-ary linear block codes. It requires only integer and finite field operations and converges very fast in decoding. It is particularly effective for decoding LDPC codes constructed based on finite geometries and finite fields.

This paper shows that a cyclic code can be put into quasi-cyclic form by decomposing a circular parity-check matrix through column and row permutations. Such a decomposition of a circular parity-check matrix of a cyclic code produces a group of shorter cyclic or quasi-cyclic codes and leads to a new method for constructing long cyclic codes from short cyclic codes. Also in this paper, new classes of cyclic and quasi-cyclic LDPC codes are derived from cyclic Euclidean geometry LDPC codes by decomposing their circular parity-check matrices. These new LDPC codes perform well and enlarge the repertoire of cyclic and quasi-cyclic LDPC codes.

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.

This paper presents two new large classes of QC-LDPC codes, one binary and one non-binary. Codes in these two classes are constructed by array dispersions of row-distance constrained matrices formed based on additive subgroups of finite fields. Experimental results show that codes constructed perform very well over the AWGN channel with iterative decoding based on belief propagation. Codes of a subclass of the class of binary codes have large minimum distances comparable to finite geometry LDPC codes and they offer effective tradeoff between error performance and decoding complexity when decoded with low-complexity reliability-based iterative decoding algorithms such as binary message passing decoding algorithms. Non-binary codes decoded with a Fast-Fourier Transform based sum-product algorithm achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with either the hard-decision Berlekamp-Massey algorithm or the algebraic soft-decision Kotter-Vardy algorithm. They have potential to replace Reed-Solomon codes in some communication or storage systems where combinations of random and bursts of errors (or erasures) occur.

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.

This paper presents two novel reliability-based iterative majority-logic decoding algorithms for LDPC codes. Both algorithms are binary message-passing algorithms and require only logical operations and integer additions. Consequently, they can be implemented with simple combinational logic circuits. They either outperform or perform just as well as the existing weighted bit-flipping or other reliability-based iterative decoding algorithms for LDPC codes in error performance with a faster rate of decoding convergence and less decoding complexity. Compared to the sum-product algorithm for LDPC codes, they offer effective trade-offs between performance and decoding complexity.

This paper presents two new algebraic constructions of high performance non-binary quasi-cyclic LDPC codes based on array dispersions of matrices over non-binary fields. Codes constructed perform well over the AWGN channel with iterative decoding using aFastFourierTransformbased sum-product algorithm. They achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with either the hard-decision Berlekamp-Massey algorithm or the algebraic soft-decision Koetter-Vardy algorithm. Due to their quasi-cyclic structure, they can be efficiently encoded using simple shift-registers with linear complexity. They have a potential to replace RS codes for some applications in communication and storage systems.

This paper presents algebraic methods for constructing high performance quasi-cyclic LDPC codes over non-binary fields. Experimental results show that codes constructed based on these methods perform well over the AWGN channel with iterative decoding using a fast Fourier transform based sum-product algorithm. They achieve significantly large coding gains over Reed-Solomon codes of the same lengths and rates decoded with the hard-decision Berlekamp-Massey algorithm, the algebraic soft-decision Kotter-Vardy algorithm, and the Jiang-Narayananpsilas adaptive belief propagation algorithm. Due to their quasi-cyclic structure, these LDPC codes can be efficiently encoded using simple shift-registers with linear complexity. They have a great potential to replace Reed-Solomon codes for some applications in communication or storage systems for combating mixed types of noise and interferences.