Quantum low-density parity-check (QLDPC) codes with asymptotically non-zero rates are prominent candidates for achieving fault-tolerant quantum computation, primarily due to the low operational depth of their syndrome-measurement circuits. Numerous studies advocate the necessity of fast decoders to fully harness the capabilities of QLDPC codes, thus driving the focus towards designing low-complexity iterative decoders. However, empirical investigations indicate that such iterative decoders are susceptible to having a high error floor when decoding QLDPC codes. The main objective of this paper is to analyze the decoding failures of thehypergraph-product(HGP) andlifted-product(LP) codes and to design decoders that mitigate these failures, thus achieving a reduced error floor. The suboptimal performance of these codes can predominantly be ascribed to two structural phenomena: (1) stabilizer-induced trapping sets (TS), which correspond to stabilizer-induced subgraphs in the Tanner graphs, and (2) classical trapping sets (TS), which originate from the classical codes used in the construction of HGP and LP codes. The dynamics of stabilizer-induced TSs are examined, and a straightforward modification of iterative decoders is proposed to circumvent these TSs. Moreover, this work proposes a systematic methodology for designing decoders that can circumvent the classical TSs in both HGP and LP codes by deriving them from decoders capable of avoiding the TSs in the parent classical LDPC codes. When decoders that can avoid stabilizer-induced TSs are run in parallel with those that can mitigate the effect of classical TSs, the logical error rate improves significantly in the error-floor region.

In this paper, we propose a novel message-passing decoding approach that leverages the degeneracy of quantum low-density parity-check codes to enhance decoding performance, eliminating the need for serial scheduling or post-processing. Our focus is on two-block Calderbank-Shor-Steane (CSS) codes, which are composed of symmetric stabilizers that hinder the performance of conventional iterative decoders with uniform update rules. Specifically, our analysis shows that, under the isolation assumption, the min-sum decoder fails to converge when constant-weight errors are applied to symmetric stabilizers, as variable-to-check messages oscillate in every iteration. To address this, we introduce a decoding technique that exploits this oscillatory property by applying distinct update rules: variable nodes in one block utilize messages from previous iterations, while those in the other block are updated conventionally. Logical error-rate results demonstrate that the proposed de-coder significantly outperforms the normalized min-sum decoder and achieves competitive performance with belief propagation enhanced by order-zero ordered statistics decoding, all while maintaining linear complexity in the code's block length.

This paper explores the application of reinforcement learning techniques to improve the performance of bit-flipping decoders and finding their optimal decisions. We begin by providing an overview of bit-flipping based decoders and reinforcement learning algorithms. We then outline the methodology for mapping the iterative decoding process into Markov Decision Processes (MDPs). We propose a feedback-based method to exploit and enhance the performance of existing well-established decoders by applying reinforcement learning algorithms after a selected decoder. In essence, we modify the MDP to reduce the number of states, making reinforcement learning algorithms feasible for low-rate and long-length codes. In addition, focusing on the correction of dominant error patterns of a selected decoder improves its error correction capability. Finally, we present experimental results for the Binary Symmetric Channel (BSC) to demonstrate the efficiency of the proposed methods.

Quantum low-density parity-check (QLDPC) codes have been proven to achieve higher minimum distances at higher code rates than surface codes. However, this family of codes must cope with the stringent latency constraints imposed by quantum technology and tends to exhibit poor performance under iterative decoding, especially when the variable degree is low. In this work, we improve both the error correction performance and decoding latency of variable degree-3 ($d_{v}$-3) QLDPC codes under iterative decoding. Firstly, we perform a detailed analysis of the structure of a well-known family of QLDPC codes, i.e., hypergraph product-based codes. Then, we propose a decoding approach that stems from the knowledge of harmful configurations apparent in these codes. Our decoding scheme is based on applying a modified version of bit flipping (BF) decoding, namely two-bit bit flipping (TBF) decoding, which adds more degrees of freedom to BF decoding. The granularity offered by TBF decoding helps us design sets of decoders that operate in parallel and can collectively decode error patterns appearing in harmful configurations of the code, thus addressing both the latency and performance requirements. Finally, simulation results demonstrate that the proposed decoding scheme surpasses other iterative decoding approaches for various$d_{v}$-3 QLDPC codes.

Topological quantum codes, such as toric and surface codes, are excellent candidates for hardware implementation due to their robustness against errors and their local interactions between qubits. However, decoding these codes efficiently remains a challenge: existing decoders often fall short of meeting requirements such as having low computational complexity (ideally linear in the code’s blocklength), low decoding latency, and low power consumption. In this paper we propose a novel bit-flipping (BF) decoder tailored for toric and surface codes. We introduce the proximity vector as a heuristic metric for flipping bits, and we develop a new subroutine for correcting degenerate multiple errors on adjacent qubits. Our algorithm has quadratic complexity growth and it can be efficiently implemented as it does not require operations on dynamic memories, as do state-of-art decoding algorithms such as minimum weight perfect matching or union find. The proposed decoder shows a decoding threshold of 7.5% for the 2D toric code and 7% for the rotated planar code over the binary symmetric channel.

We propose a novel bit-flipping (BF) decoder tailored for toric codes. We introduce the proximity vector as a heuristic metric for flipping bits, and we develop a new subroutine for correcting a particular class of harmful degenerate errors. Comparing to other decoders, our algorithm is particularly suitable for efficient hardware implementation as it does not require operations on dynamic memories. The proposed decoder shows a decoding threshold of 7.5% for the 2D toric code over the binary symmetric channel.

This paper proposes two approaches for reducing the impact of the error floor phenomenon when decoding quantum low-density parity-check codes with belief propagation based algorithms. First, a low-complexity syndrome-based linear programming (SB- LP) decoding algorithm is proposed, and second, the proposed SB-LP is applied as a post-processing step after syndrome-based min-sum (SB-MS) decoding. For the latter case, a new early stopping criterion is introduced to decide when to activate the SB- LP algorithm, avoiding executing a predefined maximum number of iterations for the SB-MS decoder. Simulation results show, for a sample hypergraph code, that the proposed decoder can lower the error floor by two to three orders of magnitude compared to SB-MS for the same total number of decoding iterations.

Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on thedecoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.

We introduce a low-complexity message-passing quantum error correction algorithm for decoding Quantum Low-Density Parity-Check (QLDPC) stabilizer codes. The proposed decoder operates on the quaternary stabilizer graph but only exchanges binary messages. This leads to a significantly reduced complexity compared to other quaternary belief propagation (BP) algorithms that pass floating-point messages. The efficacy of the proposed decoder is evaluated by providing decoding examples, performance metrics using Monte-Carlo simulations, and complexity analysis. Despite its reduced complexity, the performance loss of the proposed decoder is modest compared to floating-point parallel quaternary decoders for a Calderbank-Shor-Steane (CSS) code family. In particular, experiments obtained over the [[1054, 140, 20]] lifted product (LP) Tanner code demonstrated that for low error rates (< 0.01), the proposed quaternary-binary message-passing decoder approaches the performance of quaternary BP by converging in almost the same number of iterations while requiring less complex operations. Additionally, for non-CSS codes, our decoder performs similarly as quaternary floating-point decoders despite its lower complexity.

Machine learning based approaches are being increasingly used for designing decoders for next generation communication systems. One widely used framework is neural belief propagation (NBP), which unfolds the belief propagation (BP) iterations into a deep neural network and the parameters are trained in a data-driven manner. NBP decoders have been shown to improve upon classical decoding algorithms. In this paper, we investigate the generalization capabilities of NBP decoders. Specifically, the generalization gap of a decoder is the difference between empirical and expected bit-error-rate(s). We present new theoretical results which bound this gap and show the dependence on the decoder complexity, in terms of code parameters (blocklength, message length, variable/check node degrees), decoding iterations, and the training dataset size. Results are presented for both regular and irregular parity-check matrices. To the best of our knowledge, this is the first set of theoretical results on generalization performance of neural network based decoders. We present experimental results to show the dependence of generalization gap on the training dataset size, and decoding iterations for different codes.

Iterative decoders for finite length quantum low-density parity-check (QLDPC) codes are impacted by short cycles, detrimental graphical configurations known as trapping sets (TSs) present in a code graph as well as symmetric degeneracy of errors. In this paper, we develop a systematic methodology by which quantum trapping sets (QTSs) can be defined and categorized according to their topological structure. Conventional definition of a TS from classical error correction is generalized to address the syndrome decoding scenario for QLDPC codes. We show that QTS information can be used to design better QLDPC code and decoder. For certain finite-length QLDPC codes, frame error rate improvements of two orders of magnitude in the error floor regime are demonstrated without needing any post-processing steps.

In his pioneering work on LDPC codes, Gallager dismissed codes with parity-check matrices of weight two after proving that their minimum Hamming distances grow at most logarithmically with their code lengths. In spite of their poor minimum Hamming distances, it is shown that quasi-cyclic LDPC codes with parity-check matrices of column weight two have good capability to correct phased bursts of erasures which may not be surpassed by using quasi-cyclic LDPC codes with parity-check matrices of column weight three or more. By modifying the parity-check matrices of column weight two and globally coupling them, the erasure correcting capability can be further enhanced. Quasi-cyclic LDPC codes with parity-check matrices of column weight three or more that can correct phased bursts of erasures and perform well over the AWGN channel are also considered. Examples of such codes based on Reed-Solomon and Gabidulin codes are presented.

In this paper, we present a deliberate bit flipping (DBF) coding scheme for binary two-dimensional (2-D) channels, where specific patterns in channel inputs are the significant cause of errors. The idea is to eliminate a constrained encoder and, instead, embed a constraint into an error correction codeword that is arranged into a 2-D array by deliberately flipping the bits that violate the constraint. The DBF method relies on the error correction capability of the code being used so that it should be able to correct both deliberate errors and channel errors. Therefore, it is crucial to flip minimum number of bits in order not to overburden the error correction decoder. We devise a constrained combinatorial formulation for minimizing the number of flipped bits for a given set of harmful patterns. The generalized belief propagation algorithm is used to find an approximate solution for the problem. We evaluate the performance gain of our proposed approach on a data-dependent 2-D channel, where 2-D isolated-bits patterns are the harmful patterns for the channel. Furthermore, the performance of the DBF method is compared with classical 2-D constrained coding schemes for the 2-D no isolated-bits constraint on a memoryless binary symmetric channel.

In this paper, we present a computationally efficient method for estimating error floors of low-density parity-check (LDPC) codes over the binary symmetric channel (BSC) without any prior knowledge of its trapping sets (TSs). Given the Tanner graph G of a code, and the decoding algorithm V, the method starts from a list of short cycles in G, and expands each cycle by including its sufficiently large neighborhood in G. Variable nodes of the expanded sub-graphs EXP are then corrupted exhaustively by all possible error patterns, and decoded by V operating on EXP. Union of support of the error patterns for which V fails on each EXP defines a subset of variable nodes that is a TS. The knowledge of the minimal error patterns and their strengths in each TSs is used to compute an estimation of the frame error rate. This estimation represents the contribution of error events localized on TSs, and therefore serves as an accurate estimation of the error floor performance of V at low BSC cross-over probabilities. We also discuss trade-offs between accuracy and computational complexity. Our analysis shows that in some cases the proposed method provides a million-fold improvement in computational complexity over standard Monte-Carlo simulation.

In this paper, we propose a new approach to design finite alphabet iterative decoders (FAIDs) for Low-Density Parity Check (LDPC) codes over binary symmetric channel (BSC) via recurrent quantized neural networks (RQNN). We focus on the linear FAID class and use RQNNs to optimize the message update look-up tables by jointly training their message levels and RQNN parameters. Existing neural networks for channel coding work well over Additive White Gaussian Noise Channel (AWGNC) but are inefficient over BSC due to the finite channel values of BSC fed into neural networks. We propose the bit error rate (BER) as the loss function to train the RQNNs over BSC. The low precision activations in the RQNN and quantization in the BER cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We leverage straight-through estimators as surrogate gradients to tackle this issue and provide a joint training scheme. We show that the framework is flexible for various code lengths and column weights. Specifically, in high column weight case, it automatically designs low precision linear FAIDs with superior performance, lower complexity, and faster convergence than the floating-point belief propagation algorithms in waterfall region.

In this paper, we introduce a method of using quantized neural networks (QNN) to design finite alphabet message passing decoders (FAID) for Low-Density Parity Check (LDPC) codes. Specifically, we construct a neural network with low precision activations to optimize a FAID over Additive White Gaussian Noise Channel (AWGNC). The low precision activations cause a critical issue that their gradients vanish almost everywhere, making it difficult to use classical backward propagation. We introduce straight-through estimators (STE) to avoid this problem, by replacing zero derivatives of quantized activations with surrogate gradients in the chain rules. We present a systematic approach to train such networks while minimizing the bit error rate, which is a widely used and accurate metric to measure the performance of iterative decoders. Examples and simulations show that by training a QNN, a FAID with 3-bit of message and 4-bit of channel output can be obtained, which performs better than the more complex floating-point minsum decoding algorithm. This methodology is promising in the sense that it facilitates designing low-precision FAID for LDPC codes while maintaining good error performance in a flexible and efficient manner.

Quantum low-density parity check (QLDPC) codes are promising in realization of scalable, fault tolerant quantum memory for computation. Many of the QLDPC codes constructions suffer from unavoidable short cycles in their Tanner graph which degrade the decoding performance of the belief propagation (BP) algorithm. In this paper, we propose a syndrome based generalized belief propagation (GBP) algorithm for decoding of quantum LDPC codes and analyze how the proposed algorithm escapes from short cycle trapping sets effectively compared to the BP algorithm. Simulation results show improved decoding performance of the GBP algorithm over BP for the dual containing Calderbank, Shor and Steane (CSS) codes when cycles of length 4 are considered in the region based approach.

This paper presents designs and constructions of two classes of binary quasi-cyclic LDPC codes for correcting multiple random phased-bursts of erasures over the binary erasure channel. The erasure correction of codes in both classes is characterized by the cycle and adjacency structure of their Tanner graphs. Erasure correction of these codes is a very simple process which requires only modulo-2 additions. The codes in the second class are capable of correcting locally and globally distributed phased-bursts of erasures with a two-phase iterative erasure-correction process.

Designs and constructions of quasi-cyclic (QC) LDPC codes for the AWGN channel are presented. The codes are constructed based on the conventional parity-check matrices of Reed-Solomon (RS) codes and are referred to as RS-QC-LDPC codes. Several classes of RS-QC-LDPC codes are given. Cycle structural properties of the Tanner graphs of codes in these classes are analyzed and specific methods for constructing codes with girth at least eight and reducing their short cycles are presented. The designed codes perform well in both waterfall and low error-rate regions.

In this paper, we present how the decoding performance of layered decoder can be analyzed using trapping sets. Surprisingly, a simple horizontal layered Gallager-B decoder breaks all weight-3 error patterns on a (5,3) trapping set successfully, resulting in a steeper slope in frame error rate (FER) curves compared to a flooding schedule decoder. Theoretical validation of the results is also done using a semi- analytical method for computing the error floors of LDPC codes on a binary symmetric channel decoded using layered Gallager-B algorithm.

Low-density parity check (LDPC) codes are an attractive error correction scheme for ensuring data integrity in new generation of NAND flash memories. A quick assessment of the iterative decoders for LDPC codes reveals a wide range of varying complexities. The simple Bit-Flipping (BF) and binary-message-passing algorithms such as the Gallager A/B algorithms occupy one end of the spectrum, while Belief Propagation (BP) and A Posteriori Probability (APP) decoders lie at the other end. The gamut of existing decoders filling the intermediate space can simply be understood as the implementation of BP (and its variants, such as the min-sum algorithm) at different levels of message precision. Decoders with low-precision messages are desirable because of their low complexity and power efficiency, but in such decoders it is highly nontrivial to prevent performance degradation known to as error floor and to guarantee fast convergence to a codeword. In this paper we present our results on a new class of low-complexity iterative decoders for flash memory channels. They involve two main innovations: global computation and randomness. Our decoding algorithm, Probabilistic Gradient Descent Bit-Flipping (PGDBF) is motivated by the analogy between Tanner graphs and the graphical models used in statistical mechanics, and prescribe a rule for flipping a bit based on the so-called energy function and a binary random sequence associated to that bit. Energy function is computationally simple, but involves all the bits. We present the PGDBF algorithm analysis, explain how it benefits from global computation and randomness, and present the hardware synthesis results as well as comparisons with the state-of-the-art decoders.

Two-dimensional magnetic recording (TDMR) is an emerging storage technology that aims to achieve areal densities on the order of 10 Tb/in2, mainly driven by innovative channels engineering with minimal changes to existing head/media designs within a systems framework. Significant additive areal density gains can be achieved by using TDMR over bit patterned media (BPM) and energy-assisted magnetic recording (EAMR). In TDMR, the sectors are inherently 2-D with reduced track pitch and bit widths, leading to severe 2-D intersymbol interference (ISI). This necessitates the development of powerful 2-D signal processing and coding algorithms for mitigating 2-D ISI, timing artifacts, jitter, and electronics noise resulting from irregular media grain positions and read-head electronics. The algorithms have to be eventually realized within a read/write channel architecture as a part of a system-on-chip (SoC) within the disk controller system. In this work, we provide a wide overview of TDMR technology, channel models and capacity, signal processing algorithms (detection and timing recovery), and error-correcting codes attuned to 2-D channels. The innovations and advances described not only make TDMR a promising future technology, but may serve a broader engineering audience as well.

Lowering the power supply of a circuit can induce transient errors in the memory cells and timing errors in the computation units. In this paper, we consider the Taylor-Kuznetsov (TK) memory architecture with transient errors in the memory cells and with timing errors in the correction circuit. We provide a theoretical analysis of the performance of TK memories under transient errors and timing errors. Our study is based on the analysis of the computation trees of the equivalent Gallager B decoders with and without timing errors. As a main result, we show that as the number of iterations goes to infinity, the error probability of the decoder with timing errors converges to the error probability of the decoder without timing errors. Monte Carlo simulations confirm this result even for moderate code lengths.

We introduce a stochastic resonance based decoding paradigm for quantum codes using an error correction circuit made of a combination of noisy and noiseless logic gates. The quantum error correction circuit is based on iterative syndrome decoding of quantum low-density parity check codes, and uses the positive effect of errors in gates to correct errors due to decoherence. We analyze how the proposed stochastic algorithm can escape from short cycle trapping sets present in the dual containing Calderbank, Shor and Steane (CSS) codes. Simulation results show improved performance of the stochastic algorithm over the deterministic decoder.

Flash memories are gaining prominence for utilizing in large scale data centers (DCs) due to their high memory density, low power consumption and heat dissipation, and high access speed characteristics. The rate of degradation for a flash memory is largely affected by the amount and frequency of the erase/write operations, which is a challenge in the DC context that serves dynamically changing workloads. Adaptive Error Correction Code (AECC) schemes have been introduced for changing the error correction algorithm based on the reliability state of the flash. In this study we show that hard decision (bit-flipping) and soft decision decoding (Belief Propagation) class of algorithms for Low Density Parity Check (LDPC) decoders complement each other for utilizing in the flash based DCs in order to meet the dynamically changing reliability level. We propose a new family of ECC to improve the reliability of flash memory. Our Monte-Carlo simulations and Field Programmable Gate Array (FPGA) based hardware implementation analysis show that LDPC decoders are suitable for balancing the throughput, decoding performance and reliability requirements in DCs.

The Probabilistic Gradient Descent Bit-Flipping (PGDBF) decoder has been proposed as a very promising hard-decision Low-Density Parity-Check (LDPC) decoder with a large gain in error correction. However, this impressive decoding gain is reported to come along with a non-negligible extra complexity due to the additional Perturbation Block (PB) required on top of the Gradient Descent Bit-Flipping (GDBF) decoder. In this paper, an efficient solution to implement this PB is introduced which is shown to keep the decoding gain as good as the theoretical PGDBF decoder while requiring a very small hardware overhead compared to the non-probabilistic GDBF. The proposed architecture is designed basing on a statistical analysis conducted to find the key features of the randomness needed to maintain the decoding gain and to reveal the simplification directions. The efficiency of our proposed method is confirmed by the synthesis results of decoder implementations on ASIC with 65nm CMOS technology and performance simulations.

A majority logic decoder made of unreliable logic gates, whose failures are transient and data-dependent, is analyzed. Based on a combinatorial representation of fault configurations a closed-form expression for the average bit error rate for a one-step majority logic decoder is derived, for a regular low-density parity-check (LDPC) code ensemble and the proposed failure model. The presented analysis framework is then used to establish bounds on the one-step majority logic decoder performance under the simplified probabilistic gate-output switching model. Based on the expander property of Tanner graphs of LDPC codes, it is proven that a version of the faulty parallel bit-flipping decoder can correct a fixed fraction of channel errors in the presence of data-dependent gate failures. The results are illustrated with numerical examples of finite geometry codes.

We propose a novel approach to modulation coding using the Generalized Belief Propagation (GBP) algorithm. The idea is to completely eliminate a constrained encoder and, instead, embed a constraint into an error correction codeword by deliberately flipping the bits that violate the constraint. The GBP algorithm is used to keep the number of flipped bits small in order not to overburden the decoder. We incorporate our method to impose the two-dimensional (2D) no isolated bit constraint on a low-density parity check (LDPC) coded 2D data array. Furthermore, we show that the number of flipped bits can be optimized so that it is not beyond the error correcting capability of the code. Applied to Two Dimensional Magnetic Recording (TDMR) systems, our approach results in an order of magnitude gain in the frame error rate.

In this paper we analyze the effect of hardware unreliability to performance of bit-flipping decoders of low-density parity-check (LDPC) codes. We apply expander arguments to show that the simple parallel bit flipping decoder, built partially from faulty gates, can correct a linear fraction of worst case channel errors, when gate failures are correlated and dependent on the switching activity of logic gates. In addition, we provide a lower bound on the guaranteed error correction of LDPC codes with left degree of at least eight.

We propose an iterative decoder made of a combination of faulty and perfect logic gates that is capable of correcting more channel errors than its counterpart made completely of perfect logic gates. We present an error probability analysis based on absorbing Markov chains, and explain how the randomness in the check node update function helps a decoder to escape to local minima associated with trapping sets. For the (155, 64) Tanner low-density parity check code, we provide a range of gate failure probabilities for which imperfect decoders perform better.

Two dimensional magnetic recording (TDMR) achieves high areal densities by reducing the size of a bit comparable to the size of the magnetic grains resulting in two dimensional (2D) inter symbol interference (ISI) and very high media noise. Therefore, it is critical to handle the media noise along with the 2D ISI detection. In this paper, we tune the generalized belief propagation (GBP) algorithm to handle the media noise seen in TDMR. We also provide an intuition into the nature of hard decisions provided by the GBP algorithm. The performance of the GBP algorithm is evaluated over a Voronoi based TDMR channel model where the soft outputs from the GBP algorithm are used by a belief propagation (BP) algorithm to decode low-density parity check (LDPC) codes.

The digital universe is doubling every two years and expected to reach an unwieldy 44 zettabytes into the next decade. To cope with the ever increasing need for storing, transmitting and retrieving huge amounts of data, cloud storage, data centers and other massively distributed storage networks have emerged. These rely on efficient memory technologies at the physical level for speed, reliability and energy efficiency.

We give an architecture of a storage system consisting of a storage medium made of unreliable memory elements and an error correction circuit made of a combination of noisy and noiseless logic gates that is capable of retaining the stored information with the lower probability of error than a storage system with a correction circuit made completely of noiseless logic gates. Our correction circuit is based on the iterative decoding of low-density parity check codes, and uses the positive effect of errors in logic gates to correct errors in memory elements. In the spirit of Marcus Tullius Cicero's Clavus clavo eicitur (one nail drives out another), the proposed storage system operates on the principle: error errore eicitur-one error drives out another. The randomness that is present in the logic gates makes these classes of decoders superior to their noiseless counterparts. Moreover, random perturbations do not require any additional computational resources as they are inherent to unreliable hardware itself. To utilize the benefits of logic gate failures, our correction circuit relies on two key novelties: a mixture of reliable and unreliable gates and decoder rewinding. We present a method based on absorbing Markov chains for the probability of error analysis, and explain how the randomness in the variable and check node update function helps a decoder to escape to local minima associated with trapping sets.

In this paper, we estimate the Mutual Information Rate (MIR) for Two-Dimensional Magnetic Recording (TDMR) channel with input constraints by using the Generalized Belief Propagation (GBP) algorithm. The Voronoi channel model is considered in this paper. Since the main source of media noise in the TDMR channel is the boundary distortion of the bit area which is manifested in presence of transitions of the input data, the constraints utilized for TDMR systems limit the number of transitions in the input patterns. In [1], we showed that constrained coding can provide performance gain in the bit error rate (BER). However, BER is not a proper figure of merit to compare various input distributions for a fixed channel since the rate loss due to using constrained input is not accounted for. On the other hand, computing MIR for different input distributions can lead us to the limits of the channel capacity.

We propose an improved version of probabilistic gradient descent bit flipping algorithm for decoding low density parity check codes, based on MUltiple Decoding attempts and Random re-Initializations (MUDRI). The proposed algorithm significantly increases the probability of correcting error patterns uncorrectable by the existing variants of bit-flipping algorithm. The performance of the algorithm implemented in noisy hardware is analyzed for various code types and codeword lengths, and shown to be superior compared to other hard decision algorithms. The MUDRI decoder is mostly insensitive to the failures in registers and logic gates and therefore represents a desirable solution for implementation in unreliable hardware.

In this paper, several implementations of the recently introduced PGDBF decoder for LDPC codes are proposed. In [2], the authors show that using randomness in bit-flipping decoders can greatly improve the error correction performance. In this paper, two models of random generators are proposed and compared through hardware implementation and performance simulation. A conventional implementation of the random generator through LFSR as a first design, and a new approach using binary sequences that are produced by the LDPC decoder, named IVRG, as second design. We show that both implementation of the PGDBF improve greatly the error correction performance, while maintaining the same large throughtput. However, the performance gain requires a large hardware overhead in the case of LFSR-PGDBF, while the overhead is limited to only 10% in the case of the IVRG-PGDBF.

In this paper, we propose a predictive method to construct regular column-weight-three LDPC codes with girth g = 8 so that their Tanner graphs contain a minimum number of small trapping sets. Our construction is based on improvements of the Progressive Edge-Growth (PEG) algorithm. We first show how to detect the smallest trapping sets (5; 3) and (6; 4) in the computation tree spread from variable nodes during the edge assignment. A precise and rigorous characterization of trapping sets (5; 3) and (6; 4) are given, and we then derive a modification of the Randomized Progressive Edge-Growth (RandPEG) algorithm [1] to take into account a new cost function that allows to build regular column-weight dv= 3, girth 8 LDPC codes free of (5,3) and with a minimization of (6,4). We present the construction and the performance results in the context of quasi-cyclic LDPC (QC-LDPC) codes.

In this paper, we propose a method for estimating the Symmetric Information Rate (SIR) for Two Dimensional Magnetic Recording (TDMR) channel by using the Generalized Belief Propagation (GBP) algorithm. We consider the Voronoi model as the channel model of a TDMR system. The dominant component of noise in TDMR caused by the imperfections of the medium is called “media noise”. The nature of the media noise is data-dependent, however, the media noise can be closely approximated by additive white Gaussian noise (AWGN) with variance and mean dependent on channel bits written on the magnetic medium. Lower and upper bounds on the SIR are obtained by using the GBP algorithm. In addition, it is shown that the accuracy of the SIR estimation can be adjusted for sufficient size of the magnetic medium. Finally, the bit aspect ratio of a TDMR system is optimized by maximizing the SIR per unit area.

This paper addresses the problem of designing low-density parity check decoders robust to transient errors introduced by faulty hardware. We assume that the faulty hardware introduces errors during the message-passing updates, and we propose a general framework for the definition of the message update faulty functions. Within this framework, we define symmetry conditions for the faulty functions and derive two simple error models used in the analysis. With this analysis, we propose a new interpretation of the functional density evolution threshold introduced by Kameni et al. in the recent literature and show its limitations in the case of highly unreliable hardware. However, we show that under restricted decoder noise conditions, the functional threshold can be used to predict the convergence behavior of finite alphabet iterative decoders (FAIDs) under faulty hardware. In particular, we reveal the existence of robust and nonrobust FAIDs and propose a framework for the design of robust decoders. We finally illustrate robust- and nonrobust-decoder behaviors of finite-length codes using Monte Carlo simulations.

In this paper, we propose two-dimensional (2D) constraints for mitigating media noise in two-dimensional magnetic recording (TDMR) systems with generalized belief propagation (GBP) detectors. By imposing restrictions on 2D input patterns, we forbid patterns harmful to the GBP detector. Such 2D constraints result in an order of magnitude improvement in the bit error rate. This improvement is demonstrated on TDMR systems with realistic grain, bit, track and head dimensions. We also estimate the capacities of locally defined 1D and 2D low-pass constraints using the GBP-based method.

In this paper we present analysis of one-step majority logic decoders made of unreliable components in the presence of data-dependent gate failures. Gate failures are modeled by a Markov chain, and based on the combinatorial representation of the fault configurations, a closed-form expression for the average bit error rate is derived for a regular LDPC code ensemble. Presented analysis framework is then used for obtaining upper bounds on decoding performance under timing errors.

Two dimensional magnetic recording (TDMR) is a new paradigm in data storage which envisions densities up to 10 Tb/in2as a result of drastically reducing bit to grain ratio. In order to reach this goal aggressive write (shingled writing) and read process are used in TDMR. Kavcic et al. proposed a simple magnetic grain model called the granular tiling model which captures the essence of read/write process in TDMR. Capacity bounds for this model indicate that 0.6 user bit per grain densities are possible, however, previous attempt to reach capacities are not close to the channel capacity. In this paper, we provide a truly two-dimensional detection scheme for the granular tiling model based on generalized belief propagation (GBP). Factor graph interpretation of the detection problem is provided and formulated in this paper. Then, GBP is employed to compute marginal a posteriori probabilities for the constructed factor graph. Simulation results show huge improvements in detection. A lower bound on the symmetric information rate (SIR) is also derived for this model based on GBP detector.

In this paper, we propose a new approach to constructing a class of check-hybrid generalized low-density parity-check (GLDPC) codes which are free of small trapping sets. This approach is based on converting selected checks of an LDPC code involving a trapping set to super checks corresponding to a shorter error correcting component code. In particular, we follow two goals in constructing the check-hybrid GLDPC codes: First, the super checks are replaced based on the knowledge of trapping sets of the global LDPC code. We show that by converting only some single checks to super checks the decoder corrects the errors on a trapping set and hence eliminates the trapping set. Second, the number of super checks required for eliminating certain trapping sets is minimized to reduce the rate-loss. We first give an algorithm to find a set of critical checks in a trapping set of an LDPC code and then we provide some upper bounds on the minimum number of critical checks needed to eliminate certain trapping sets in the parity-check matrix of an LDPC code. A possible fixed set for a class of check-hybrid codes is also given.

This issue consists of 22 high-caliber papers with contributions from both academia and industry. The papers are organized into the following six sections: (i) Channel Modeling and Signal Processing Algorithms for Emerging Memory Technologies, (ii) Error Control Coding Techniques for Flash Memories, (iii) Algebraic Methods with Applications to Non- Volatile Memories, (iv) Polar Codes with Application to Storage, (v) Performance Limits of Storage Systems, and (vi)Codes for Distributed Network Storage.

A new class of bit flipping algorithms for low-density parity-check codes over the binary symmetric channel is proposed. Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its "strength." The introduction of this additional bit allows an increase in the guaranteed error correction capability. An additional bit is also employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis and selection of two-bit bit flipping algorithms is provided. The main component of this framework is the (re)definition of trapping sets, which are the most "compact" Tanner graphs that cause decoding failures of an algorithm. A recursive procedure to enumerate trapping sets is described. This procedure is the basis for selecting a collection of algorithms that work well together. It is demonstrated that decoders which employ a properly selected group of the proposed algorithms operating in parallel can offer high speed and low error floor decoding.

We address the problem of detection in a multiple-beam orbital angular momentum (OAM)-based free-space optical communication link. Based on experimental channel observations, we extract a statistical model for the coaxial multimode OAM channel affected by atmospheric turbulence. We employ solutions to least square problems to compensate for the interference among optical modes. A solution based on Fincke-Pohst Enumeration Algorithm for least square problems is presented. In addition, Moore-Penrose based analytical solutions are considered (e.g. Zero Forcing). Finally, we provide bit error rate analysis for the channel under investigation.

Low-density parity-check (LDPC) codes are adopted in many applications due to their Shannon-limit approaching error-correcting performance. Nevertheless, belief-propagation (BP) based decoding of these codes suffers from the error-floor problem. Recently, a new type of decoders termed finite alphabet iterative decoders (FAIDs) were introduced. The FAIDs use simple Boolean maps for variable node processing. With very short word length, they can surpass the BP-based decoders in the error floor region. This paper develops a low-complexity implementation architecture for FAIDs by making use of their properties. Particularly, an innovative bit-serial check node unit is designed for FAIDs, and the symmetric Boolean maps for variable node processing lead to small silicon area. An optimized data scheduling scheme is also proposed to increase the hardware utilization efficiency. From synthesis results, the proposed FAID implementation needs only 52% area to reach the same throughput as one of the most efficient Min-sum decoders for an example (7807, 7177) LDPC code, while achieving better error-correcting performance in the error-floor region.

In this letter, we propose a compressive sensing scheme for the mixture estimation problem in spectroscopy. We show that by applying an appropriate measurement matrix on the chemical mixture spectrum, we obtain an overall measurement matrix which is sparse. This enables the use of a low-complexity iterative reconstruction algorithm, called the interval-passing algorithm, to estimate the concentration of each chemical present in the mixture. Simulation results for the proportion of correct reconstructions show that chemical mixtures with a large number of chemicals present can be recovered.

Recently, we introduced a new class of finite alphabet iterative decoders (FAIDs) for low-density parity-check (LDPC) codes. These decoders are capable of surpassing belief propagation (BP) in the error floor region on the binary symmetric channel (BSC) with much lower complexity. In this paper, we introduce a novel scheme with the objective of guaranteeing the correction of a given and potentially large number of errors on column-weight-three LDPC codes. The proposed scheme uses a plurality of FAIDs which collectively correct more error patterns than a single FAID on a given code. The collection of FAIDs utilized by the scheme is judiciously chosen to ensure that individual decoders have different decoding dynamics and correct different error patterns. Consequently, they can collectively correct a diverse set of error patterns, which is referred to as decoder diversity. We provide a systematic method to generate the set of FAIDs for decoder diversity on a given code based on the knowledge of the most harmful trapping sets present in the code. Using the well-known column-weight-three (155,64) Tanner code with dmin= 20 as an example, we describe the method in detail and show, by means of exhaustive simulation, that the guaranteed error correction capability on short length LDPC codes can be significantly increased with decoder diversity.

We introduce a new paradigm for finite precision iterative decoding on low-density parity-check codes over the binary symmetric channel. The messages take values from a finite alphabet, and unlike traditional quantized decoders which are quantized versions of the belief propagation (BP) decoder, the proposed finite alphabet iterative decoders (FAIDs) do not propagate quantized probabilities or log-likelihoods and the variable node update functions do not mimic the BP decoder. Rather, the update functions are maps designed using the knowledge of potentially harmful subgraphs that could be present in a given code, thereby rendering these decoders capable of outperforming the BP in the error floor region. On certain column-weight-three codes of practical interest, we show that there exist {FAIDs that surpass the floating-point BP decoder in the error floor region while requiring only three bits of precision for the representation of the messages}. Hence, FAIDs are able to achieve a superior performance at much lower complexity. We also provide a methodology for the selection of FAIDs that is not code-specific, but gives a set of candidate FAIDs containing potentially good decoders in the error floor region for any column-weight-three code. We validate the code generality of our methodology by providing particularly good three-bit precision FAIDs for a variety of codes with different rates and lengths.

We propose a blind watermarking scheme for 3D meshes that combines sparse quantization index modulation (QIM) with deletion correction codes. The QIM operates on the vertices in rough concave regions of the surface thus ensuring impeccability, while the deletion correction code recovers the data hidden in the vertices, which is removed by mesh optimization and/or simplification. The proposed scheme offers two orders of magnitude better performance in terms of recovered watermark bit error rate compared to the existing schemes of similar payloads and fidelity constraints.

We present an artificial Boolean network exhibiting the behaviour similar to that of the cell cycle: three phases and checkpoints between them. The phases follow the increase of the cell mass, while checkpoints ensure that internal errors are corrected before moving to the next phase. The network can tolerate up to one gene mutation and one transient error in gene expressions. It has only 6 genes and is the smallest and simplest network with such behavior. It is based on a special type of error correction codes, resulting in an elegant and symmetric network topology and highly symmetric attractor basin.

A class of two-bit bit flipping algorithms for decoding low-density parity-check codes over the binary symmetric channel was proposed in [1]. Initial results showed that decoders which employ a group of these algorithms operating in parallel can offer low error floor decoding for high-speed applications. As the number of two-bit bit flipping algorithms is large, designing such a decoder is not a trivial task. In this paper, we describe a procedure to select collections of algorithms that work well together. This procedure relies on a recursive process which enumerates error configurations that are uncorrectable by a given algorithm. The error configurations uncorrectable by a given algorithm form its trapping set profile. Based on their trapping set profiles, algorithms are selected so that in parallel, they can correct a fixed number of errors with high probability.

Finite alphabet iterative decoders (FAIDs) for LDPC codes were recently shown to be capable of surpassing the Belief Propagation (BP) decoder in the error floor region on the Binary Symmetric channel (BSC). More recently, the technique of decimation which involves fixing the values of certain bits during decoding, was proposed for FAIDs in order to make them more amenable to analysis while maintaining their good performance. In this paper, we show how decimation can be used adaptively to further enhance the guaranteed error correction capability of FAIDs that are already good on a given code. The new adaptive decimation scheme proposed has marginally added complexity but can significantly improve the slope of the error floor performance of a particular FAID. We describe the adaptive decimation scheme particularly for 7-level FAIDs which propagate only 3-bit messages and provide numerical results for column-weight three codes. Analysis suggests that the failures of the new decoders are linked to stopping sets of the code.

We introduce a generic approach, called FAID diversity, for improving the error correction capability of regular low-density parity check codes, beyond the belief propagation performance. The method relies on operating a set of finite alphabet iterative decoders (FAID). The message-passing update rules are interpreted as discrete dynamical systems, and are judiciously chosen to ensure that decoders have different dynamics on a specific finite-length code. An algorithm is proposed which uses random jumps in the iterative message passing trajectories, such that the system is not trapped in periodic attractors. We show by simulations that the FAID diversity approach with random jumps has the potential of approaching the performance of maximum-likelihood decoding for finite-length regular, column-weight three codes.

We introduce a class of finite systems models of gene regulatory networks exhibiting behavior of the cell cycle. The model is an extension of a Boolean network model. The system spontaneously cycles through a finite set of internal states, tracking the increase of an external factor such as cell mass, and also exhibits checkpoints in which errors in gene expression levels due to cellular noise are automatically corrected. We present a 7-gene network based on Projective Geometry codes, which can correct, at every given time, one gene expression error. The topology of a network is highly symmetric and requires using only simple Boolean functions that can be synthesized using genes of various organisms. The attractor structure of the Boolean network contains a single cycle attractor. It is the smallest nontrivial network with such high robustness. The methodology allows construction of artificial cell cycle gene regulatory networks with the number of phases larger than in natural cell cycle.

We present a method to construct low-density parity-check (LDPC) codes with low error floors on the binary symmetric channel. Codes are constructed so that their Tanner graphs are free of certain small trapping sets. These trapping sets are selected from the trapping set ontology for the Gallager A/B decoder. They are selected based on their relative harmfulness for a given decoding algorithm. We evaluate the relative harmfulness of different trapping sets for the sum–product algorithm by using the topological relations among them and by analyzing the decoding failures on one trapping set in the presence or absence of other trapping sets. We apply this method to construct structured LDPC codes. To facilitate the discussion, we give a new description of structured LDPC codes whose parity-check matrices are arrays of permutation matrices. This description uses Latin squares to define a set of permutation matrices that have disjoint support and to derive a simple necessary and sufficient condition for the Tanner graph of a code to be free of four cycles.

We study communication over atmospheric turbulence channels based on LDPC-coded signaling using multidimensional orbital angular momentum (OAM) signal constellations. Multidimensional signal constellation is obtained as the N-dimensional Cartesian product of a one-dimensional signal constellation originating from non-negative pulse-amplitude modulation. This scheme represents an energy efficient alternative, since a larger number of bits per symbol can be transmitted using a given bandwidth. We evaluate the performance of this scheme by determining conditional symbol probability density functions (PDFs) from numerical propagation data. Two cases are considered: (i) when conditional PDFs are known on the receiver side, and (ii) when conditional PDFs are not known and Gaussian approximation is used instead. We show that the OAM modulation is more sensitive to atmospheric turbulence as the number of dimensions increases. We also describe several applications of interest ranging from indoor wireless communications to intersatellite communications.

Bit-patterned media is a novel technology for magnetic data storage that is poised to increase recording density beyond 1 Tb/sq. in. However, a significant concern in BPMR is the stringent requirements for synchronization between write clock and island position, errors in which may manifest as insertions and deletions. In this paper, we introduce a method for compensating for synchronization errors by using conventional error-correcting codes. We present a numerical study that provides bounds on achievable coding rates. We also perform a simulation study to demonstrate the applicability of the proposed scheme in practical systems.

In this paper, we propose a new class of bit flipping algorithms for low-density parity-check (LDPC) codes over the binary symmetric channel (BSC). Compared to the regular (parallel or serial) bit flipping algorithms, the proposed algorithms employ one additional bit at a variable node to represent its “strength.” The introduction of this additional bit increases the guaranteed error correction capability by a factor of at least 2. An additional bit can also be employed at a check node to capture information which is beneficial to decoding. A framework for failure analysis of the proposed algorithms is described. These algorithms outperform the Gallager A/B algorithm and the min-sum algorithm at much lower complexity. Concatenation of two-bit bit flipping algorithms show a potential to approach the performance of belief propagation (BP) decoding in the error floor region, also at lower complexity.

Finite alphabet iterative decoders (FAID) with multilevel messages that can surpass BP in the error floor region for LDPC codes on the BSC were previously proposed in [1]. In this paper, we propose decimation-enhanced decoders. The technique of decimation which is incorporated into the message update rule, involves fixing certain bits of the code to a particular value. Under appropriately chosen rules, decimation can significantly reduce the number of iterations required to correct a fixed number of errors, while maintaining the good performance of the original decoder in the error floor region. At the same time, the algorithm is much more amenable to analysis. We shall provide a simple decimation scheme for a particularly good 7-level FAID for column-weight three codes on the BSC, that helps to correct a fixed number of errors in fewer iterations, and provide insights into the analysis of the decoder. We shall also examine the conditions under which the decimation-enhanced 7-level FAID performs at least as good as the 7-level FAID.

Recently new message passing decoders for LDPC codes, called finite alphabet iterative decoders (FAIDs) were proposed. The messages belong to a finite alphabet and the update functions are simple boolean maps different from the functions used for the belied propagation (BP) decoder. The maps can be chosen using the knowledge of potential trapping sets such that the decoders surpass the BP decoder in the error floor. In this paper, we address the issue of selecting good FAIDs which perform well in the error floor for column weight three codes. We introduce the notion of noisy trapping set which is a generalization based on analyzing the local dynamic behaviour of a given FAID on a trapping set. Using this notion as the core, we provide an iterative greedy algorithm that outputs a set of candidate FAIDs containing potentially good decoders for any given code. To illustrate the appliance of the methodology on several codes, we show that the set of candidate FAIDs contains particularly good FAIDs for different codes with different rates and lengths.

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not equal to the transmitted codeword. We design an efficient algorithm termed the Instanton Search Algorithm (ISA) which generates an error vector called the BSC-instanton. We prove that: (a) the LP decoder fails for any error pattern with support that is a superset of the support of an instanton; (b) for any input, the ISA outputs an instanton in the number of steps upper-bounded by twice the number of errors in the input error vector. We then find the number of unique instantons of different sizes for a given LDPC code by running the ISA sufficient number of times.

As the CMOS semiconductor technology enters nanometer regime, interconnect processes must be compatible with device roadmaps and meet manufacturing targets at the specified wafer size. The resulting ubiquitous process variations cause errors in data delivering through interconnects. This paper proposes an Information Theory based design method to accommodate process variations. Different from the traditional delay based design metric, the current approach uses achievable rate to relate interconnect designs directly to communication applications. More specifically, the data communication over a typical interconnect, a bus, subject to process variations (“uncertain” bus), is defined as a communication problem under uncertainty. A data rate, called the achievable rate, is computed for such a bus, which represents the lower bound on the maximal data rate attainable over the bus. When a data rate applied over the bus is smaller than the achievable data rate, a reliable communication can be guaranteed regardless of process variations, i.e., a bit error rate arbitrarily close to zero is achievable. A single communication strategy to combat the process variations is proposed whose code rate is equal to the computed achievable rate. The simulations show that the variations in the interconnect resistivity could have the most harmful effect regarding the achievable rate reduction. Also, the simulations illustrate the importance of taking into account bus parasitic parameters correlations when measuring the influence of the process variations on the achievable rates.

This paper studies the performance of a serial turbo code on two simplified rectangular-grain models of recording media for two dimensional magnetic recording at a density of more than 0.5 bits/grain. We derive one-dimensional (1D) and two-dimensional (2D) rectangular-grain media models and from these present finite-state-machine (FSM) representations. From the FSM for the 1D model we computed achievable information rates assuming independent and uniformly distributed (i.u.d.) binary inputs. From the (approximate) FSM for the 2D model, we present a detector. We then present a serial turbo code architecture with constituent convolutional codes that is capable of achieving 80\% of i.u.d. capacity for the 1D model and 65\% of the average of published upper and lower bounds on capacity for the 2D model.

We consider the Linear Programming (LP) solution of the Compressed Sensing (CS) problem over reals, also known as the Basis Pursuit (BasP) algorithm. The BasP allows interpretation as a channel-coding problem, and it guarantees error-free reconstruction with a properly chosen measurement matrix and sufficiently sparse error vectors. In this manuscript, we examine how the BasP performs on a given measurement matrix and develop an algorithm to discover the sparsest vectors for which the BasP fails. The resulting algorithm is a generalization of our previous results on finding the most probable error-patterns degrading performance of a finite size Low-Density Parity-Check (LDPC) code in the error-floor regime. The BasP fails when its output is different from the actual error-pattern. We design a CS-Instanton Search Algorithm (ISA) generating a sparse vector, called a CS-instanton, such that the BasP fails on the CS-instanton, while the BasP recovery is successful for any modification of the CS-instanton replacing a nonzero element by zero. We also prove that, given a sufficiently dense random input for the error-vector, the CS-ISA converges to an instanton in a small finite number of steps. The performance of the CS-ISA is illustrated on a randomly generated 120 × 512 matrix. For this example, the CS-ISA outputs the shortest instanton (error vector) pattern of length 11.

In this paper, we propose a new class of quantized message-passing decoders for LDPC codes over the BSC. The messages take values (or levels) from a finite set. The update rules do not mimic belief propagation but instead are derived using the knowledge of trapping sets. We show that the update rules can be derived to correct certain error patterns that are uncorrectable by algorithms such as BP and min-sum. In some cases even with a small message set, these decoders can guarantee correction of a higher number of errors than BP and min-sum. We provide particularly good 3-bit decoders for 3-left-regular LDPC codes. They significantly outperform the BP and min-sum decoders, but more importantly, they achieve this at only a fraction of the complexity of the BP and min-sum decoders.

This paper introduces a class of structured low-density parity-check (LDPC) codes whose parity check matrices are arrays of permutation matrices. The permutation matrices are obtained from Latin squares and form a finite field under some matrix operations. They are chosen so that the Tanner graphs do not contain subgraphs harmful to iterative decoding algorithms. The construction of column-weight-three codes is presented. Although the codes are optimized for the Gallager A/B algorithm over the binary symmetric channel (BSC), their error performance is very good on the additive white Gaussian noise channel (AWGNC) as well.

Since the inception of direct access magnetic storage about 55 years ago, data storage has both benefited from and given rise to extraordinary progress in many technological areas, including materials science, tribology, servo control and actuation, and signal processing and coding. The number of data bits that can be stored in a unit area - the areal recording density - has increased by eight orders of magnitude for harddisk magnetic storage, with compound annual growth rates at times exceeding 100%. Moreover, the cost of this form of storage has dropped by about seven orders of magnitude. For this reason, data storage has been one of the main enablers of the information technology revolution. According to a recent estimation by the technology analysis firm IDC, the amount of data created worldwide has now started to exceed the capacity of storage that is physically available. This so-called digital universe is forecasted to grow explosively and reach more than 1021bytes (1 ZB) in 2011.

The relation between the girth and the guaranteed error correction capability of¿-left-regular low-density parity-check (LDPC) codes when decoded using the bit flipping (serial and parallel) algorithms is investigated. A lower bound on the size of variable node sets which expand by a factor of at least3 ¿/4is found based on the Moore bound. This bound, combined with the well known expander based arguments, leads to a lower bound on the guaranteed error correction capability. The decoding failures of the bit flipping algorithms are characterized using the notions of trapping sets and fixed sets. The relation between fixed sets and a class of graphs known as cage graphs is studied. Upper bounds on the guaranteed error correction capability are then established based on the order of cage graphs. The results are extended to left-regular and right-uniform generalized LDPC codes. It is shown that this class of generalized LDPC codes can correct a linear number of worst case errors (in the code length) under the parallel bit flipping algorithm when the underlying Tanner graph is a good expander. A lower bound on the size of variable node sets which have the required expansion is established.

The relation between the girth and the error correction capability of column-weight-three LDPC codes under the Gallager A algorithm is investigated. It is shown that a column-weight-three LDPC code with Tanner graph of girthg¿ 10 can correct all error patterns with up to(g/2-1) errors in at mostg/2 iterations of the Gallager A algorithm. For codes with Tanner graphs of girthg¿ 8, it is shown that girth alone cannot guarantee correction of all error patterns with up to(g/2-1) errors under the Gallager A algorithm. Sufficient conditions to correct(g/2-1) errors are then established by studying trapping sets.

In this paper, we propose a linear programming (LP) decoding scheme for binary error-erasure channel for use in two-dimensional magnetic recording. We compare the performance of this decoding scheme with other decoding schemes like LP decoding for BSC and belief-propagation decoding. Also, we compare the effect of variance of grain-area in the medium on the bit-error rates of various decoding schemes.

We consider the problem of joint detection and decoding of low-density parity-check (LDPC) coded signals over partial response (PR) channels. A method to graphically represent the constraints imposed by the channel and the code on the channel output sequence is introduced. This enables the design of a detector and decoder that estimates a posteriori probabilities of noiseless channel output symbols rather than binary channel inputs. By running the sum-product algorithm (SPA) on this graph, a joint decoder is obtained that is shown to perform significantly better than the turbo-equalizer, at the cost of increased computational complexity.

A class of two-bit message passing decoders for decoding column-weight-four LDPC codes over the binary symmetric channel is proposed. The thresholds for various decoders in this class are derived using density evolution. For a specific decoder, the sufficient conditions for correcting all error patterns with up to three errors are derived.

We consider linear programming (LP) decoding of a fixed low-density parity-check (LDPC) code over the binary symmetric channel (BSC). The LP decoder fails when it outputs a pseudo-codeword which is not a codeword. We propose an efficient algorithm termed the instanton search algorithm (ISA) which, given a random input, generates a set of flips called the BSC-instanton and prove that: (a) the LP decoder fails for any set of flips with support vector including an instanton; (b) for any input, the algorithm outputs an instanton in the number of steps upper-bounded by twice the number of flips in the input. We obtain the number of unique instantons of different sizes by running the ISA sufficient number of times. We then use the instanton statistics to predict the performance of the LP decoding over the BSC in the error floor region. We also propose an efficient semi-analytical method to predict the performance of LP decoding over a large range of transition probabilities of the BSC.

We describe a family of instanton-based optimization methods developed recently for the analysis of the error floors of low-density parity-check (LDPC) codes. Instantons are the most probable configurations of the channel noise which result in decoding failures. We show that the general idea and the respective optimization technique are applicable broadly to a variety of channels, discrete or continuous, and variety of sub-optimal decoders. Specifically, we consider: iterative belief propagation (BP) decoders, Gallager type decoders, and linear programming (LP) decoders performing over the additive white Gaussian noise channel (AWGNC) and the binary symmetric channel (BSC). The instanton analysis suggests that the underlying topological structures of the most probable instanton of the same code but different channels and decoders are related to each other. Armed with this understanding of the graphical structure of the instanton and its relation to the decoding failures, we suggest a method to construct codes whose Tanner graphs are free of these structures, and thus have less significant error floors.

In this paper, the error-correction capability of column-weight-three low-density parity-check (LDPC) codes when decoded using the Gallager A algorithm is investigated. It is proved that a necessary condition for a code to correct all error patterns with up to k ges 5 errors is to avoid cycles of length up to 2k in its Tanner graph. As a consequence of this result, it is shown that given any alpha > 0, exist N such that forall n > N, no code in the ensemble of column-weight-three codes can correct all alphan or fewer errors. The results are extended to the bit flipping algorithms.

We investigate the relation between the girth and the guaranteed error correction capability of gamma-left regular LDPC codes when decoded using the bit flipping (serial and parallel) algorithms. A lower bound on the number of variable nodes which expand by a factor of at least 3gamma/4 is found based on the Moore bound. An upper bound on the guaranteed correction capability is established by studying the sizes of smallest possible trapping sets.

In this paper, we provide necessary and sufficient conditions for a column-weight-three LDPC code to correct all patterns up to three errors when decoded using Gallager A algorithm. We then provide a construction technique which results in a code satisfying the above conditions. We also provide numerical assessment of code performance via simulation results.

We discuss error floor asympotics and present a method for improving the performance of low-density parity-check (LDPC) codes in the high SNR (error floor) region. The method is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. The proposed method can be modified to construct convolutional LDPC codes also. The method is illustrated by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm. Decoding results on AWGN channel are also presented to illustrate that optimizing codes for one channel/decoding algorithm can lead to performance improvement on other channels.

We describe a multiple optical sources - multiple detectors scheme, based on either repetition MIMO or space-time coding and low-density parity-check (LDPC) codes. The proposed scheme is able to operate under strong atmospheric turbulence and provides excellent coding gains. The LDPC codes are designed using the concept of pairwise-balanced designs. Bit-error rates and achievable information rates are reported assuming non-ideal photodetection. To improve the spectral efficiency we employ the concept of bit-interleaved LDPC-coded modulation based on pulse-amplitude modulation.

In this work we use a new approach to model error events in long-haul optical fiber transmission systems. Existing approaches for obtaining probability density functions (PDFs) rely on numerical simulations or analytical approximations. Numerical simulations make far tails of the PDFs difficult to obtain, while analytical approximations are often inaccurate, as they neglect nonlinear interaction between pulses and noise. Our approach combines the instanton method from statistical mechanics, to model far tails of the PDFs, with numerical simulations to refine the middle part of the PDFs. We combine the two methods by using an orthogonal polynomial expansion constructed specifically for this problem. We demonstrate the approach on an example of a specific submarine transmission system.

We present a method for lowering the error floor of low-density parity check (LDPC) codes. It is based on Tanner graph covers that do not have trapping sets from the original code. The advantages of the method are that it is universal, as it can be applied to any LDPC code/channel model/decoding algorithm and it improves performance at the expense of increasing the code length, without losing the code regularity, without changing the decoding algorithm, and, under certain conditions, without lowering the code rate. We illustrate the method by modifying Tanner, MacKay and Margulis codes to improve performance on the binary symmetric channel (BSC) under the Gallager B decoding algorithm.

In this paper, we present a combinatorial algorithm to calculate the exact bit error rate performance of regular low-density parity check codes under one-step majority logic decoding. Majority logic decoders have regained importance in nano-scale memories due to their resilience to both memory and logic gate failures. This result is an extension of the work of Rudolph on error correction capability of majority-logic decoders.

A novel rate-optimal rate allocation algorithm is proposed for parallel transmission of scalable images in multi-channel systems. Scalable images are transmitted via fixed-length packets. The proposed algorithm selects a subchannel as well as a channel code rate for each packet, based on the signal-to-noise ratios (SNR) of the subchannels. The resulting scheme provides unequal error protection of source bits. Applications to JPEG2000 transmission show that significant UEP gains are achieved over equal error protection (EEP) schemes.

A fast rate-optimal rate allocation algorithm is proposed for parallel transmission of scalable images in multichannel systems. Scalable images are transmitted via fixed-length packets. The proposed algorithm selects a subchannel, as well as a channel code rate for each packet, based on the signal-to-noise ratios (SNRs) of the subchannels. The resulting scheme provides unequal error protection of source bits and significant gains are obtained over equal error protection schemes. An application of the proposed algorithm to JPEG2000 transmission shows the advantages of exploiting differences in SNRs between subchannels. Multiplexing of multiple sources is also considered, and additional gains are achieved by exploiting information diversity among the sources.

A framework is proposed for iterative joint source-channel decoding of JPEG2000 codestreams. At the encoder, JPEG2000 is used to perform source coding with certain error-resilience (ER) modes, and LDPC codes are used to perform channel coding. During decoding, the source decoder uses the ER modes to identify corrupt sections of the codestream and provides this information to the channel decoder. Decoding is carried out jointly in an iterative fashion. Experimental results indicate that the proposed method requires fewer iterations and improves overall system performance.

Several classes of low-density parity-check (LDPC) codes are proposed as an error control coding (ECC) scheme for a non-linear satellite system with the phase-shift keying (PSK) signaling. The bit-error rate (BER) performance of LDPC codes is determined by means of an advanced simulator that takes into account all major impairments in the transmission link between fixed ground stations over a non-regenerative geostationary (GEO) satellite. Our analysis includes the following impairments: the degradations caused by simultaneous influences of cross- polarization effects, undesired signals from neighboring satellite systems or terrestrial radio-relay links and phase noise produced by local oscillator at the satellite station and reference signal extractor at the receiving ground station. The proposed LDPC codes are compared against standard ECC schemes employed in modern satellite communication systems.

In this paper, we analyze storage circuits constructed from unreliable memory components. We propose a memory construction, using low-density parity-check codes, based on a construction originally made by Taylor. The storage circuit consists of unreliable memory cells along with a correcting circuit. The correcting circuit is also constructed from unreliable logic gates along with a small number of perfect gates. The modified construction enables the memory device to perform better than the original construction. We present numerical results supporting our claims.

An iterative soft decoding scheme suitable for highspeed long-haul optical transmission is proposed. The approach is based on a combination of the method of optimal fluctuations (instantons) and a modification of a method, originally proposed in the context of magnetic media, which incorporates the BCJR algorithm and Low-Density Parity-Check (LDPC) codes. The proposed scheme can achieve target bit error rates at longer distances than conventional error correcting approaches.

In this paper, we propose a semi-analytical method to compute error floors of LDPC codes on the binary symmetric channel decoded iteratively using the Gallager B algorithm. The error events of the decoder are characterized using combinatorial objects called trapping sets, originally defined by Richardson. In general, trapping sets are characteristic of the graphical representation of a code. We study the structure of trapping sets and explore their relation to graph parameters such as girth and vertex degrees. Using the proposed method, we compute error floors of regular structured and random LDPC codes with column weight three.

Transmitter and receiver configurations suitable for M-ary DPSK/differential QAM noncoherent optical transmission are proposed. It is shown that multilevel coding based on lowdensity parity-check codes as component codes is an efficient approach to achieve high-spectrally efficient noncoherent optical transmission. The multilevel coding scheme with 2 bits/s/Hz spectral efficiency based on block-circulant component codes provides the coding gain of 12.3 dB compared to uncoded 8-DPSK, and 8.3 dB compared to uncoded QDPSK.

This paper considers a distribution/aggregation network that employs optical code division multiple access (OCDMA) to transmit information to a head-end node in a metropolitan area network. The head-end node transmits synchronization pulses and the nodes employ ranging techniques to offset the propagation delay, resulting in a quasi-synchronous reception at the receiver. The paper develops a methodology to design orthogonal OCDMA codes for such quasi-synchronous communication systems. The paper also describes the receiver design and computes the bit error rate of such systems.

In this paper we propose an analytical method to evaluate the performance of one step majority logic decoders constructed from faulty gates. We analyze the decoder under the assumption that the gates fail independently. We calculate the average bit error probability of such a decoder and apply the method to the special case of projective geometry codes. The method, however, applies to any regular low-density parity-check code of girth at least six but the calculations are much simpler for the projective geometry codes. We present results for the bit error rate performance of four codes from projective planes

A method for estimation of achievable information rates of high-speed optical transmission systems is proposed. This method consists of two steps: (i) approximating probability density functions for energy of pulses, which is done by instanton approach; (ii) estimating achievable information rates by a modification of a method originally proposed by Arnold and Pfitser. Numerical results for a specific optical transmission system (submarine system at transmission rate 40Gb/s) are reported.

The paper gives a survey of spectrum shaping codes used for digital recording systems. This class of codes belongs to the broader class of modulation codes, which are widely used in recording systems for adjusting the source characteristics to the characteristics of the recording channel. The Shannon noiseless capacities of recording channels are considered, as well as the spectra of maxentropic sequences of M-ary recording constraints. In addition, some practical encoding and decoding schemes are discussed.

This paper presents an unequal error protection scheme based on the Plotkin construction for channel (error control) codes. The resulting codes offer the novel ability of using one long channel codeword to protect an entire image, yet still allowing progressive decoding. Progressive quality improvements occur in two ways: the first is the usual progressive refinement, where image quality is improved as more data are received; the second is that residual error rates of earlier received data are reduced as more data are received.

It is widely accepted that short cycles in Tanner graphs deteriorate the performance of message-passing algorithms. This discourages the use of these algorithms on Tanner graphs (TGs) of well-known algebraic codes such as Hamming codes, Bose-Chaudhuri-Hocquenghem codes, and Reed-Solomon codes. Yedidia et al. presented a method to generate code representations suitable for message-passing algorithms. This method does not guarantee a representation free of four-cycles. In this correspondence, we present an algorithm to convert an arbitrary linear block into a code with orthogonal parity-check equations. A combinatorial argument is used to prove that the algorithm guarantees a four-cycle free representation for any linear code. The effects of removing four-cycles on the performance of a belief propagation decoder for the binary erasure channel are studied in detail by analyzing the structures in different representations. Finally, we present bit-error rate (BER) and block-error rate (BLER) performance curves of linear block codes under belief propagation algorithms for the binary erasure channel and the additive white Gaussian noise (AWGN) channel in order to demonstrate the improvement in performance achieved with the help of the proposed algorithm.

It is well known that random-like low-density parity-check (LDPC) codes over the extension fields GF(2/sup m/) of GF(2), for m>1, tend to outperform their binary counterparts of comparable length and rate. At the same time, structured LDPC codes offer the advantage of reduced implementation and storage complexity, so that it is of interest to investigate mathematical design methods for codes on graphs over fields of large order. We propose a new class of combinatorially developed codes obtained by properly combining Reed-Solomon (RS) type parity-check matrices and sparse parity-check matrices based on permutation matrices. The proposed codes have large girth and minimum distance. In order to further reduce the decoding complexity of the proposed scheme, we introduce a new decoding algorithm based on matrix representations of the underlying field, which trades performance for complexity. The particular field representation described in this abstract is based on a power basis generated by a companion matrix of a primitive polynomial of the field GF(2/sup m/). It is observed that the choice of the primitive polynomial influences the cycle distribution of the code graph.

We present a theoretical tool for evaluation of error code performance on graphs. The method is known under the name of instanton calculus and is common in theoretical physics. We introduce the instanton calculus for linear block codes, and give a closed form expression for the bit error rate for a class of codes whose graphical model is approximated locally by a tree.

The aim of this paper is to describe a new class of problems and some new results in coding theory arising from the analysis of the composition and functionality of the genetic code. The major goal of the proposed work is to initiate research on investigating possible connections between the regulatory network of gene interactions (RNGI) and the proofreading (error-control) mechanism of the processes of the central dogma of genetics. New results include establishing a direct relationship between Boolean network (BN) models of RNGI and Gallager's LDPC decoding algorithms. The proposed research topics and described results are expected to have a two-fold impact on coding theory and genetics research. Firstly, they may provide a different setting in which to analyze standard LDPC decoding algorithms, by using dynamical systems and Boolean function theory. Secondly, they may be of use in establishing deeper relationships between the DNA proofreading mechanism, RNGI, and their joint influence on the development and possible treatment of genetic diseases like cancer.

This letter introduces a combinatorial construction of girth-eight high-rate low-density parity-check codes based on integer lattices. The parity-check matrix of a code is defined as a point-line incidence matrix of a 1-configuration based on a rectangular integer lattice, and the girth-eight property is achieved by a judicious selection of sets of parallel lines included in a configuration. A class of codes with a wide range of lengths and column weights is obtained. The resulting matrix of parity checks is an array of circulant matrices.

This paper introduces several new combinatorial constructions of low-density parity-check (LDPC) codes, in contrast to the prevalent practice of using long, random-like codes. The proposed codes are well structured, and unlike random codes can lend themselves to a very low-complexity implementation. Constructions of regular Gallager codes based on cyclic difference families, cycle-invariant difference sets, and affine 1-configurations are introduced. Several constructions of difference families used for code design are presented, as well as bounds on the minimal distance of the codes based on the concept of a generalized Pasch configuration.

FEC scheme based on LDPC codes is presented in this paper. We show that LDPC codes provide a significant system performance improvement with respect to the state-of-the-art FEC schemes, such as turbo BCH and RS codes, employed in optical communications systems. The system performance is further improved by a code design that eliminates short cycles in a graph employed in iterative decoding. As opposed to additive white Gaussian noise (AWGN) model for optical fiber channel, which is used very often in the analysis of error controlling schemes, our model takes into account all major impairments in a long-haul optical transmission such as amplifier spontaneous emission (ASE) noise, pulse distortion due to fiber nonlinearities, chromatic dispersion, crosstalk, intersymbol-interference, etc.

In this paper, we propose a novel approach to modulation and error control coding. The idea is to completely eliminate a constrained code and, instead, impose the constraint by the deliberate introduction of bit errors before transmission. The redundancy that would have been used for imposing the constraint is used in our scheme to strengthen the error control code (ECC), in such a way that the ECC becomes capable of correcting both deliberate errors as well as channel errors that occurs during the detection. The proposed ECC-modulation scheme is based on iterative decoding of low-density parity-check codes (LDPC) and a runlength constraint.

We investigate the computational complexity of the A* algorithm with reliability reordering, applied to maximum-likelihood (ML) decoding of block codes. Extensive computer simulations show that A* decoding with reliability reordering offers good average computational performance, but up to date there is no accurate analytical description of the decoding complexity. By using the theory of order statistics, we derive asymptotic bounds for the maximum decoding complexity as well as approximations for the average decoding complexity of the algorithm for large noise levels. The analysis shows that reordering is a key feature of the algorithm that allows for substantial computational savings.

We introduce a combinatorial construction of regular low-density parity check codes based on balanced incomplete block designs whose bipartite graphs have girth six. Our construction employs a special type of anti-Pasch affine geometry that result in codes having minimum distance of at least six. We are primarily concerned with very high-rate codes and low column weights, but the proposed construction can be used to generate long codes as well as codes of arbitrary column weight.

This paper introduces a combinatorial construction of a class of iteratively decodable codes, an approach diametrically opposed to the prevalent practice of using large, random-like codes. Our codes are well-structured and, unlike random codes, can lend themselves to a very low complexity implementation. A systematic way of constructing codes based on Steiner systems and the Z/sub /spl nu//, group is presented, and a hardware efficient encoding algorithm is proposed. A substantial performance improvement of high-rate Steiner codes over the existing schemes used in magnetic recording systems is demonstrated.

In partial response systems with maximum likelihood sequence estimation a short list of error events dominate. In this paper we introduce a graph-based construction of high rate codes capable of correcting errors from a given list. We define a directed graph describing a universe of error-event-detecting codes, and construct a code by tracing a path through the graph that gives the best probability of error. We demonstrate a substantial SNR gain when these codes are used in a scheme which combines the error event detection and the list soft decoding.

Constrained coding is used in recording systems to translate an arbitrary sequence of input data to a channel sequence with special properties required by the physics of the medium. Very often, more than one constraint is imposed on a recorded sequence; typically, a run-length constraint is combined with a spectral-null constraint. We introduce a low-complexity encoder structure for composite constraints, based on loose multimode codes. The first channel constraint is imposed strictly, and the second constraint is imposed in a probabilistic fashion. Relaxing the second constraint is beneficial because it enables higher code rates and simplifies the encoder. To control the second constraint a multimode encoder is used. We represent a set of multimode coded sequences by a weighted trellis and propose using a limited trellis search to select optimal output. Using this method, we modify the EFM+ code used in digital versatile disk (DVD). We combine EFM+'s run-length constraint with the first- and second-order spectral-null constraints. The resulting EFM++ code gives more than 10-dB improvement in suppression of low-frequency spectral content in the servo bandwidth over the original EFM+ code with the same complexity.

We introduce a new enumerative encoding method for (d,k) codes. The encoding algorithm, which is based on enumeration of multiset permutations, is conceptually simpler and computationally less expensive than other algorithms proposed thus far. We also describe a new application of enumerative encoding methods for phrase length distribution shaping of run-length-limited (RLL) sequences. We demonstrate that by reducing the probability of occurrence of long phrases in maxentropic RLL sequences, the frequency of patterns that account for most of the errors in magnetic recording systems can be decreased.

The problem of calculating the power spectral density of a constrained maxentropic vector sequence {a/sup n/}, a/sup n/=[a/sub i//sup n/]/sub 0/spl les/i/spl les/N-1/, is considered. The constraints of the constituent sequences {a/sub i//sup n/} are defined by the sofic systems S/sub i/ presented by the directed graphs G/sub i/, 0/spl les/i/spl les/N-1, but the vector sequence itself is constrained additionally, and given by a function /spl phi/ of constituent graphs (G=/spl phi/(G/sub 0/, /spl middot//spl middot//spl middot/, G/sub N-1/)). This class of vector constraints is met in parallel multitrack recording. The general case of a simultaneous recording on N tracks is considered, assuming that the common vector constraint is track-invariant.

We consider multiamplitude, multitrack runlength-limited (d, k) constrained channels with and without clock redundancy. We calculate the Shannon capacities of these channels and present some simple 100% efficient codes. To compute capacity a constraint graph equivalent to the usual runlength-limited constraint graph is used. The introduced graph model has the vertex labeling independent of number of tracks to be written on (in parallel), which provides computational savings when the number of tracks is large. We show that increasing the number of tracks written on in parallel provides significant increase of per-track capacity for the more restrictive clocking constraint case, i.e., when k

Run-length-limited or (d,k) recording codes are widely used in digital storage systems with peak detection. The channel capacities of the redundant multitrack (d,k) constraint are calculated and tabulated for k