In spite of their broad popularity, blockchain systems are increasingly facing issues related to large storage overhead and computational cost. A commonly proposed solution to blockchain scalability is the inclusion of so-called light nodes. Light nodes are resource-constrained users who do not routinely download the full block of transaction data; rather, they rely on full nodes to broadcast fraud proofs if any transaction in a block is invalid. While this approach allows resource-constrained nodes to participate in a blockchain, it also exposes them to a so-called Data Availability (DA) attack. A DA attack is described by an event in which an adversarial block producer creates a block containing invalid transactions to be hidden from the rest of the network. Error-correcting codes are a promising solution to DA attacks by forcing the adversary to withhold a larger portion of the block (that holds invalid transactions), thus making adversarial actions easier to be discovered by honest nodes in the network. In a previous work by Al Bassam et al., it was recognized that 2D Reed-Solomon codes are a promising code construction due to their small fraud proof sizes. In this work, we develop new light node sampling strategies, tailored for 2D Reed-Solomon codes, that increase the resilience of the system against DA attacks. We compare our solution to the naive random sampling without replacement and demonstrate significant gains.

High-dimensional quantum key distribution (QKD) is a popular protocol that provides information theoretically secure keys to multiple parties. Two important steps of QKD are 1) the information reconciliation (IR) step, where parties reconcile mismatches in generated keys through classical communication, and 2) the privacy amplification (PA) step, where parties distill their common key into a new secure key that the adversary has little to no information about. In general, these two steps have been abstracted as two distinct problems. In this work, we design our IR protocol to be aware of the PA step and utilize sampling to relax the requirement on the IR step without sacrificing the final key length of the PA step, allowing for more bits generated in key creation utilizing practical decoders. We provide a novel PA-aware LDPC code construction known as Block-MDS QC-LDPC codes that can utilize the relaxed requirement. We demonstrate through simulations that our technique of sampling can provide notable gains in successfully creating secret keys.

In this paper, we present a novel variation of the coded matrix multiplication problem which we refer to as fully private grouped matrix multiplication (FPGMM). In FPGMM, a master wants to compute a group of matrix products between two matrix libraries that can be accessed by all workers while ensuring that any number of prescribed colluding workers learn nothing about which matrix products the master desires, nor the number of matrix products. We present an achievable scheme using a variant of Cross-Subspace Alignment (CSA) codes that offers flexibility in communication and computation cost. Additionally, we demonstrate how our scheme can outperform naive applications of schemes used in a related privacy focused coded matrix multiplication problem.

International audience

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a convolutional manner. The number of partitioned components determines the memory of SC codes. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. While adopting higher memories results in improved SC code performance, obtaining finite-length, high-performance SC codes with high memory is known to be computationally challenging. We break this computational bottleneck by developing a novel probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low-complexity optimization algorithms that minimize the number of detrimental objects to construct high-memory, high-performance quasi-cyclic SC codes. We apply our framework to various objects of interest, from the simplest short cycles, to more sophisticated objects such as concatenated cycles aiming at finer-grained optimization. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and optimized SC codes with uniform partitioning. The performance gain is shown to be universal over a variety of channels, from canonical channels such as additive white Gaussian noise and binary symmetric channels, to practical channels underlying flash memory and magnetic recording systems.

Light nodes in blockchain systems are known to be vulnerable to data availability (DA) attacks where they accept an invalid block with unavailable portions. Previous works have used LDPC and 2-D Reed Solomon (2D-RS) codes with Merkle Trees to mitigate DA attacks. While these codes have demonstrated improved performance across a variety of metrics such as DA detection probability, they are difficult to apply to blockchains with large blocks due to generally intractable code guarantees for large codelengths (LDPC), large decoding complexity (2D-RS), or large coding fraud proof sizes (2D-RS). We address these issues by proposing the novel Polar Coded Merkle Tree (PCMT) which is a Merkle Tree built from the encoding graphs of polar codes and a specialized polar code construction called Sampling-Efficient Freezing (SEF). We demonstrate that the PCMT with SEF polar codes performs well in detecting DA attacks for large block sizes.

Light nodes in blockchains improve the scalability of the system by storing a small portion of the blockchain ledger. In certain blockchains, light nodes are vulnerable to adata availability(DA) attack where a malicious node makes the light nodes accept an invalid block by hiding the invalid portion of the block from the nodes in the system. Recently, a technique based on LDPC codes called Coded Merkle Tree (CMT) was proposed by Yuet al.that enables light nodes to detect a DA attack by randomly requesting/sampling portions of the block from the malicious node. However, light nodes fail to detect a DA attack with high probability if a malicious node hides a small stopping set of the LDPC code. To mitigate this problem, Yuet al.used random LDPC codes that achieve large minimum stopping set size with high probability. Although effective, these codes are not necessarily optimal for this application, especially at short code lengths, which are relevant for low latency systems, IoT blockchains, etc.. In this paper, we focus on short code lengths and demonstrate that a suitable co-design of specialized LDPC codes and the light node sampling strategy can improve the probability of detection of DA attacks. We consider different adversary models based on their computational capabilities of finding stopping sets in LDPC codes. For a weak adversary model, we devise a new LDPC code construction termed as theentropy-constrainedPEG (EC-PEG) algorithm whichconcentratesstopping sets to a small group of variable nodes. We demonstrate that the EC-PEG algorithm coupled with a greedy sampling strategy improves the probability of detection of DA attacks. For stronger adversary models, we provide a co-design of a sampling strategy calledlinear-programming-sampling(LP-sampling) and an LDPC code construction calledlinear-programming-constrainedPEG (LC-PEG) algorithm. The new co-design demonstrates a higher probability of detection of DA attacks compared to approaches in earlier literature.

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. The recent rise of the blockchain technology is also moving various information systems towards decentralization to achieve high privacy at low costs. While codes with hierarchical locality have been intensively studied in the context of centralized cloud storage due to their effectiveness in reducing the average reading time, those for decentralized storage networks (DSNs) have not yet been discussed. In this paper, we propose a joint coding scheme where each node receives extra protection through the cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. This work extends and subsumes our prior work on coding for centralized cloud storage. In particular, our proposed construction not only preserves desirable properties such as scalability and flexibility, which are critical in dynamic networks, but also adapts to arbitrary topologies, a property that is essential in DSNs but has been overlooked in existing works.

In this paper, we introduce the Variable Coded Distributed Batch Matrix Multiplication (VCDBMM) problem which tasks a distributed system to perform batch matrix multiplication where matrices are not necessarily distinct among batch jobs. Most coded matrix-matrix computation work has broadly focused in two directions: matrix partitioning for computing a single computation task and batch processing of multiple distinct computation tasks. While these works provide codes with good straggler resilience and fast decoding for their problem spaces, these codes would not be able to take advantage of the natural redundancy of re-using matrices across batch jobs. Inspired by Cross-Subspace Alignment codes, we develop Flexible Cross-Subspace Alignments (FCSA) codes that are flexible enough to utilize this redundancy. We provide a full characterization of FCSA codes which allow for a wide variety of system complexities including good straggler resilience and fast decoding. We theoretically demonstrate that, under certain practical conditions, FCSA codes are within a factor of two of the optimal solution when it comes to straggler resilience; our simulations demonstrate that our codes achieve even better optimality gaps in practice.

Spatially-coupled (SC) codes, known for their threshold saturation phenomenon and low-latency windowed decoding algorithms, are ideal for streaming applications and data storage systems. SC codes are constructed by partitioning an underlying block code, followed by rearranging and concatenating the partitioned components in a “convolutional” manner. The number of partitioned components determines the “memory” of SC codes. While adopting higher memories results in improved SC code performance, obtaining optimal SC codes with high memory is known to be hard. In this paper, we investigate the relation between the performance of SC codes and the density distribution of partitioning matrices. We propose a probabilistic framework that obtains (locally) optimal density distributions via gradient descent. Starting from random partitioning matrices abiding by the obtained distribution, we perform low complexity optimization algorithms over the cycle properties to construct high memory, high performance quasi-cyclic SC codes. Simulation results show that codes obtained through our proposed method notably outperform state-of-the-art SC codes with the same constraint length and codes with uniform partitioning.

A popular method of improving the throughput of blockchain systems is by running smaller side blockchains that push the hashes of their blocks onto a trusted blockchain. Side blockchains are vulnerable to stalling attacks where a side blockchain node pushes the hash of a block to the trusted blockchain but makes the block unavailable to other side blockchain nodes. Recently, Shenget al. proposed a data availability oracle based on LDPC codes and a data dispersal protocol as a solution to the above problem. While showing improvements, the codes and dispersal protocol were designed disjointly which may not be optimal in terms of the communication cost associated with the oracle. In this paper, we provide a tailored dispersal protocol and specialized LDPC code construction based on the Progressive Edge Growth (PEG) algorithm, called the dispersal-efficient PEG (DE-PEG) algorithm, aimed to reduce the communication cost associated with the new dispersal protocol. Our new code construction reduces the communication cost and, additionally, is less restrictive in terms of system design. Full paper version [1]: https://arxiv.org/pdf/2105.06004.pdf

There are few mathematicians whose contributions go beyond named conjectures and theorems: Vladimir Iosifovich Levenshtein (, 1935–2017) is one such true exception. During the five decades of his active research career, he enriched combinatorics, coding, and information theory with elegant problem formulations, ingenious algorithmic solutions, and highly original proof techniques. However, his work accomplished much more—it paved the way for the creation and advancement of new scientific disciplines, such as natural language processing, metagenomics, sequence alignment, and reference-based genome assembly, as well as DNA-based data storage, to name a few. A crucial concept behind sequence alignment algorithms used in phylogeny, comparative, and cancer genomics, as well as in natural language processing is the Levenshtein (edit) distance and its extension, termed the Damerau–Levenshtein distance between strings. The Levenshtein distance equals the smallest number of insertions, deletions, or substitutions required to convert one string into another. Levenshtein introduced this metric in 1965 [item 1) in the Appendix], followed by the notion of deletion and insertion error-correcting codes that have since been used in a myriad of systems presented with synchronization errors [items 1) and 2) in the Appendix]. Levenshtein’s work also inspired the introduction of the trace reconstruction problem [items 3) and 4) in the Appendix] which has since sparked substantial interest in the field of DNA-based data storage.

Crossbar resistive memory with 1 Selector 1 Resistor (181R) structure is attractive for low-cost and high-density nonvolatile memory applications. As technology scales down to the single-nm regime, the increasing resistivity of wordline/bitline becomes a limiting factor to device reliability. This paper presents write/read communication channels while considering the line resistance and device variabilities by statistically relating the degraded write/read margins and the channel parameters. Binary asymmetric channel (BAC) models are proposed for the write/read operations. Simulations based on these models suggest that the bit-error rate of devices are highly non-uniform across the memory array. These models provide quantitative tools for evaluating the trade-offs between memory reliability and design parameters, such as array size, technology nodes, and aspect ratio, and also for designing coding-theoretic solutions that would be most effective for crossbar memory.

SC-LDPC codes with sub-block locality can be decoded locally at the level of sub-blocks that are much smaller than the full code block, thus providing fast access to the coded information. The same code can also be decoded globally using the entire code block, for increased data reliability. In this paper, we pursue the analysis and design of such codes from both finite-length and asymptotic lenses. This mixed approach has rarely been applied in designing SC codes, but it is beneficial for optimizing code graphs for local and global performance simultaneously. Our proposed framework consists of two steps: 1) designing the local code for both threshold and cycle counts, and 2) designing the coupling of local codes for the best cycle count in the global design.

In this paper, we propose a non-uniform windowed decoder for multi-dimensional spatially-coupled LDPC (MD-SCLDPC) codes over the binary erasure channel. An MD-SC-LDPC code is constructed by connecting together several SC-LDPC codes into one larger code that provides major benefits over a variety of channel models. In general, SC codes allow for lowlatency windowed decoding. While a standard windowed decoder can be naively applied, such an approach does not fully utilize the unique structure of MD-SC-LDPC codes. In this paper, we propose and analyze a novel non-uniform decoder to provide more flexibility between latency and reliability. Our theoretical derivations and empirical results show that our non-uniform decoder greatly improves upon the standard windowed decoder in terms of design flexibility, latency, and complexity.

The continuous rise of the blockchain technology is moving various information systems towards decentralization. Blockchain-based decentralized storage networks (DSNs) offer significantly higher privacy and lower costs to customers compared with centralized cloud storage associated with specific vendors. Coding is required to retrieve data stored on failing components. While coding solutions for centralized storage have been intensely studied, those for DSNs have not yet been discussed. In this paper, we propose a coding scheme where each node receives extra protection through cooperation with nodes in its neighborhood in a heterogeneous DSN with any given topology. Our scheme can achieve faster recovery speed compared with existing network coding methods, and can correct more erasure patterns compared with our previous work.

In certain blockchain systems, light nodes are clients that download only a small portion of the block. Light nodes are vulnerable to data availability (DA) attacks where a malicious node hides an invalid portion of the block from the light nodes. Recently, a technique based on erasure codes called Coded Merkle Tree (CMT) was proposed by Yu et al. that enables light nodes to detect a DA attack with high probability. The CMT is constructed using LDPC codes for fast decoding but can fail to detect a DA attack if a malicious node hides a small stopping set of the code. To combat this, Yu et al. used well-studied techniques to design random LDPC codes with high minimum stopping set size. Although effective, these codes are not necessarily optimal for this application. In this paper, we demonstrate a more specialized LDPC code design to improve the security against DA attacks. We achieve this goal by providing a deterministic LDPC code construction that focuses on concentrating stopping sets to a small group of variable nodes rather than only eliminating stopping sets. We design these codes by modifying the Progressive Edge Growth algorithm into a technique called the entropy-constrained PEG (EC-PEG) algorithm. This new method demonstrates a higher probability of detecting DA attacks and allows for good codes at short lengths.

Resistive random-access memory (ReRAM) with the crossbar structure is one promising candidate to be used as a next generation non-volatile memory device. In a crossbar ReRAM, in which a memristor is positioned on each row-column intersection, the sneak-path problem is one of the main challenges for a reliable readout. The sneak-path problem can be solved with additional selection devices. When some selection devices fail short, the sneak-path problem re-occurs. The re-occurred sneak-path problem is addressed in this paper. The re-occurred sneak-path event can be described combinatorially and its adverse effect can be modeled as a parallel interference. Based on a simple pilot construction, we probabilistically characterize the inter-cell dependency of the re-occurred sneak-path events. Utilizing this dependency, we propose adaptive thresholding schemes for resistive memory readout using side information provided by pilot cells. This estimation theoretic approach effectively reduces the bit-error rate while maintaining low redundancy overhead and low complexity.

Because of their capacity-approaching performance and their complexity/latency advantages, spatially-coupled (SC) codes are among the most attractive error-correcting codes for use in modern dense data storage systems. SC codes are constructed by partitioning an underlying block code and coupling the partitioned components. Here, we focus on circulant-based SC codes. Recently, the optimal overlap (OO), circulant power optimizer (CPO) approach was introduced to construct high performance SC codes for additive white Gaussian noise (AWGN) and Flash channels. The OO stage operates on the protograph of the SC code to derive the optimal partitioning that minimizes the number of graphical objects that undermine the performance of SC codes under iterative decoding. Then, the CPO optimizes the circulant powers to further reduce this number. Since the nature of detrimental objects in the graph of a code critically depends on the characteristics of the channel of interest, extending the OO-CPO approach to construct SC codes for channels with intrinsic memory is not a straightforward task. In this paper, we tackle one relevant extension; we construct high performance SC codes for practical 1-D magnetic recording channels, i.e., partial-response (PR) channels. Via combinatorial techniques, we carefully build and solve the optimization problem of the OO partitioning, focusing on the objects of interest in the case of PR channels. Then, we customize the CPO to further reduce the number of these objects in the graph of the code. SC codes designed using the proposed OO-CPO approach for PR channels outperform prior state-of-the-art SC codes by up to around 3 orders of magnitude in frame error rate (FER) and 1.1 dB in signal-to-noise ratio (SNR). More intriguingly, our SC codes outperform structured block codes of the same length and rate by up to around 1.8 orders of magnitude in FER and 0.4 dB in SNR. The performance advantage of SC codes designed using the devised OO-CPO approach over block codes of the same parameters is not only pronounced in the error floor region, but also in the waterfall region.

In order to accommodate the ever-growing data from various, possibly independent, sources and the dynamic nature of data usage rates in practical applications, modern cloud data storage systems are required to be scalable, flexible, and heterogeneous. Codes with hierarchical locality have been intensively studied due to their effectiveness in reducing the average reading time in cloud storage. In this paper, we present the first codes with hierarchical locality that achieve scalability and flexibility in heterogeneous cloud storage using small field size. We propose a double- level construction utilizing so-called Cauchy Reed-Solomon codes. We then develop a triple-level construction based on this double-level code; this construction can be easily generalized into any hierarchical structure with a greater number of layers since it naturally achieves scalability in the cloud storage systems.

Motivated by the sequence reconstruction problem from traces in DNA-based storage, we consider the problem of designing codes for the deletion channel when multiple observations (or traces) are available to the decoder. We propose simple binary and non-binary codes based on Varshamov-Tenengolts (VT) codes. The proposed codes split the codeword in blocks and employ a VT code in each block. The availability of multiple traces helps the decoder to identify deletion-free copies of a block, and to avoid mis-synchronization while decoding. The encoding complexity of the proposed scheme is linear in the codeword length; the decoding complexity is linear in the codeword length, and quadratic in the number of deletions and the number of traces. The proposed scheme offers an explicit low-complexity technique for correcting deletions using multiple traces.

Spatially-coupled (SC) LDPC codes have recently emerged as an excellent choice for error correction in modern data storage and communication systems due to their outstanding performance. It has long been known that irregular graph codes offer performance advantage over their regular counterparts. In this paper, we present a novel combinatorial framework for designing finite-length irregular SC LDPC codes. Our irregular SC codes have the desirable properties of regular SC codes thanks to their structure while offering significant performance benefits that come with the node degree irregularity. Coding constructions proposed in this work contribute to the existing portfolio of finite-length graph code designs.

Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention, thanks to their capacity approaching performance and low decoding latency. An SC code is constructed by partitioning an underlying block code into a number of components and coupling their copies together. In this paper, we first introduce a general approach for the enumeration of detrimental combinatorial objects in the graph of finite-length SC codes. Our approach is general in the sense that it effectively works for SC codes with various partitioning schemes, column weights, and memories. Next, we present a two-stage framework for the construction of high performance binary SC codes optimized for the additive white Gaussian noise channels; we aim at minimizing the number of detrimental combinatorial objects in the error floor region. In the first stage, we deploy a novel partitioning scheme, called the optimal overlap partitioning, to produce the optimal partitioning corresponding to the smallest number of detrimental objects. In the second stage, we apply a new circulant power optimizer to further reduce the number of detrimental objects in the lifted graph. SC codes constructed by our new framework have up to two orders of magnitude error floor performance improvement and up to 0.6 dB SNR gain compared to prior state-of-the-art SC codes.

Non-binary (NB) low-density parity-check (LDPC) codes are graph-based codes that are increasingly being considered as a powerful error correction tool for modern dense storage devices. Optimizing NB-LDPC codes to overcome their error floor is one of the main code design challenges facing storage engineers upon deploying such codes in practice. Furthermore, the increasing levels of asymmetry incorporated by the channels underlying modern dense storage systems, e.g., multi-level Flash systems, exacerbate the error floor problem by widening the spectrum of problematic objects that contribute to the error floor of an NB-LDPC code. In a recent research, the weight consistency matrix (WCM) framework was introduced as an effective combinatorial NB-LDPC code optimization methodology that is suitable for modern Flash memory and magnetic recording (MR) systems. The WCM framework was used to optimize codes for asymmetric Flash channels, MR channels that have intrinsic memory, in addition to canonical symmetric additive white Gaussian noise channels. In this paper, we provide an in-depth theoretical analysis needed to understand and properly apply the WCM framework. We focus on general absorbing sets of type two (GASTs) as the detrimental objects of interest. In particular, we introduce a novel tree representation of a GAST called the unlabeled GAST tree, using which we prove that the WCM framework is optimal in the sense that it operates on the minimum number of matrices, which are the WCMs, to remove a GAST. Then, we enumerate WCMs and demonstrate the significance of the savings achieved by the WCM framework in the number of matrices processed to remove a GAST. Moreover, we provide a linear-algebraic analysis of the null spaces of WCMs associated with a GAST. We derive the minimum number of edge weight changes needed to remove a GAST via its WCMs, along with how to choose these changes. In addition, we propose a new set of problematic objects, namely oscillating sets of type two (OSTs), which contribute to the error floor of NB-LDPC codes with even column weights on asymmetric channels, and we show how to customize the WCM framework to remove OSTs. We also extend the domain of the WCM framework applications by demonstrating its benefits in optimizing column weight 5 codes, codes used over Flash channels with additional soft information, and spatially coupled codes. The performance gains achieved via the WCM framework range between 1 and nearly 2.5 orders of magnitude in the error floor region over interesting channels.

A common way to protect data stored in DRAM and related memory systems is through the use of an error-correcting code such as the extended Hamming code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In this paper, we focus on unequal message protection (UMP), in which a subset of messages is deemed as special, and is afforded additional error-correction protection while maintaining the same number of redundancy bits as the baseline code. UMP is a powerful approach when the special messages are chosen based on the knowledge of data patterns in context. Our objective is to construct deterministic, algebraic codes with guaranteed UMP properties, derive their cardinality bounds using novel combinatorial techniques, and to demonstrate their efficacy for realistic memory benchmarks. We first introduce a UMP alternative to the single-bit parity-check code, and then we generalize to a broader UMP code family, including a UMP alternative to the extended Hamming code, offering full double-error correction protection to special messages. Our UMP constructions, applied to main memory in high-performance computing applications, could lead to significant system-level benefits such as less frequent checkpoints in supercomputers and decreased risk of catastrophic failure from erroneous special messages.

Permutation codes have recently garnered substantial research interest due to their potential in various applications, including cloud storage systems, genome resequencing, and flash memories. In this paper, we study the theoretical bounds and constructions of permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation and subsumes previously studied error types, including transpositions and translocations, without imposing restrictions on the lengths and positions of the translocated segments. Based on the so-called breakpoint analysis method proposed by Chee and Vu, we first present a coding framework that leads to order-optimal constructions, thus improving upon the existing constructions that are not order-optimal. We then use this framework to also develop an order-optimal coding scheme that is additionally explicit and systematic.

In this paper we tackle the problem of file deduplication for efficient data storage. We consider the case where the deduplication is performed on files that are modified by edit errors relative to the original version. We propose a novel block-level deduplication algorithm with variable-lengths in the case of non-binary alphabets. Compared to hash-based deduplication algorithms where file deduplication depends on the content of the hash keys or to brute force methods that compare files symbol-by- symbol, our algorithm significantly reduces the number of symbol comparisons and achieves high deduplication ratios. We present a theoretical analysis on the cost of the algorithm compared to naive methods and experimental results to evaluate the efficiency of our deduplication algorithm.

Spatially-coupled (SC) codes are among the most attractive error-correcting codes for use in modern storage devices. SC codes are constructed by partitioning an underlying block code and coupling the partitioned components. Here, we focus on circulant-based SC codes. Recently, the optimal overlap (OO), circulant power optimizer (CPO) approach was introduced to construct high performance SC codes for AWGN and Flash channels. The OO partitioning stage operates on the protograph of the SC code, while the CPO optimizes the circulant powers, in order to minimize the number of detrimental objects. Since the nature of detrimental objects in the graph of a code critically depends on the characteristics of the channel of interest, extending the OO-CPO approach to construct SC codes for channels with intrinsic memory is not a straightforward task. In this paper, we tackle one relevant extension; we construct high performance SC codes for practical 1-D magnetic recording channels, i.e., partial-response (PR) channels. Via combinatorial techniques, we carefully build and solve the optimization problem of the OO partitioning, focusing on the objects of interest in the case of PR channels. Then, we customize the CPO to further reduce the number of these objects in the graph of the code. SC codes designed using the OO-CPO approach for PR channels outperform prior state-of-the-art SC codes by around 3 orders of magnitude in FER and 1.1 dB in SNR, and more intriguingly, outperform structured block codes of the same length by around 1.6 orders of magnitude in FER and 0.4 dB in SNR.

In this paper, we study intrinsic locality properties of non-systematic Reed Solomon (RS) codes. We demonstrate that for RS codes encoding 4 or 5 symbols, the locality of a subset of input symbols can be strictly improved by a judicious choice of elements (and their powers) that constitute the standard RS encoding matrix, without giving up any MDS properties of the code.

In crossbar resistive memory, in which a memristor is positioned on each row-column intersection, the sneak-path problem is one of the main challenges for reliable readout. The sneak-path event can be described combinatorially and its adverse effect can be modeled as a parallel interference. In this paper, based on a high-rate coding scheme, we characterize the inter-cell dependency of sneak-path events probabilistically. Utilizing this dependency, we propose adaptive thresholding schemes for resistive memory readout using side information provided by precoded bits. This estimation theoretic approach effectively reduces the bit-error rate while maintaining low redundancy overhead and low complexity.

Error correction and detection are the core components of all modern memory systems. Current computing memory systems use simple coding schemes to simultaneously meet the resiliency and latency requirements. In this paper, we review our recent results on context-aware coding for computing memories, an approach that explicitly takes into account various intrinsic side information for improved robustness to faults. We discuss both error correction and detection, codes' theoretical properties, and provide examples of how these solutions can be implemented in practice. We explicitly describe the special case of the error localization codes. We also discuss promising future directions and connections with classical information theoretic concepts.

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.

Enabled by new storage mediums, Computation-in-Memory is a novel architecture that has shown great potential in reducing the burden of massive data processing by bypassing the communication and memory access bottleneck. Suggested by Cassuto and Crammer, allowing for ultra-fast Hamming distance computations to be performed in resistive memory with low-level conductance measurements has the potential to drastically speed up many modern machine learning algorithms. Meanwhile, Hamming distance Computation-in-Memory remains a challenging task as a result of the non-negligible device variability in practical resistive memory. In this paper, build upon the work of Cassuto and Crammer, we study memristor variability due to two distinct sources: resistance variation, and the non-deterministic write process. First, we introduce a technique for estimating the Hamming distance under resistance variation alone. Then, we propose error-detection and error-correction schemes to deal with non-ideal write process. We then combine these results to concurrently address both sources of memristor variabilities. In order to preserve the low latency property of Computation-in-Memory, all of our approaches rely on only a single vector-level conductance measurement. We use so-called inversion coding as a key ingredient in our solutions and we prove the optimality of this code given the restrictions on bit-accessible information. Finally, we demonstrate the efficacy of our approaches on the k-nearest neighbors classifier.

Spatially-coupled (SC) codes are a family of graph-based codes that have attracted significant attention thanks to their capacity approaching performance. An SC code is constructed by partitioning an underlying block code into a number of components, and coupling their copies together. The number of components is determined by the memory parameter. In this paper, we study a finite length construction for the circulant-based SC codes. We introduce a new partitioning scheme, which we call minimum overlap partitioning, that outperforms previous methods. We also present a general approach for the enumeration of problematic objects in the error-floor regime that can be applied to any circulant-based SC code and to a variety of partitioning schemes. Compared to the uncoupled block codes, an SC code constructed by the new approach has more than 1.5 and 3 orders of magnitude performance improvement for the memory 1 and 2, respectively. Additionally, it outperforms the existing method of partitioning via cutting vectors by at least half an order of magnitude; this performance advantage becomes more pronounced for SC codes with higher memories.

Modern dense Flash memory devices operate at very low error rates, which require powerful error correcting coding (ECC) techniques. An emerging class of graph-based ECC techniques that has broad applications is the class of spatially-coupled (SC) codes, where a block code is partitioned into components that are then rewired multiple times to construct an SC code. Here, our focus is on SC codes with the underlying circulant-based structure. In this paper, we present a three-stage approach for the design of high performance non-binary SC (NB-SC) codes optimized for practical Flash channels; we aim at minimizing the number of detrimental general absorbing sets of type two (GASTs) in the graph of the designed NB-SC code. In the first stage, we deploy a novel partitioning mechanism, called the optimal overlap partitioning, which acts on the protograph of the SC code to produce optimal partitioning corresponding to the smallest number of detrimental objects. In the second stage, we apply a new circulant power optimizer to further reduce the number of detrimental GASTs. In the third stage, we use the weight consistency matrix framework to manipulate edge weights to eliminate as many as possible of the GASTs that remain in the NB-SC code after the first two stages (that operate on the unlabeled graph of the code). Simulation results reveal that NB-SC codes designed using our approach outperform state-of-the-art NB-SC codes when used over Flash channels.

A common way to protect data stored in DRAM and related memory systems is through the use of a single-error-correcting/double-error-detecting (SECDED) code. Traditionally, these error-correcting codes provide equal protection guarantees to all messages. In a recent work, we demonstrated enhanced error correction capabilities for SECDED codes by taking into account contextual side-information about the data. This paper is concerned with a closely related scenario: unequal message protection (UMP), where a subset of special messages is afforded additional error-correction ability. UMP is relevant to computing systems where certain messages are critical and failures cannot be tolerated. We study practical UMP constructions where messages are guaranteed either one or two bit-error-correction. We provide upper and lower bounds on the number of special messages. We introduce an explicit and practical code construction based on BCH subcodes and demonstrate the efficacy of our technique on data from the AxBench and SPEC CPU2006 benchmark suites.

Permutation codes have recently garnered substantial research interest. In this paper, we study the permutation codes in the generalized Cayley metric. The generalized Cayley metric captures the number of generalized transposition errors in a permutation, and subsumes existing error types including transpositions and translocations without imposing restrictions on the lengths and positions of the translocated segments. Relying on the breakpoint analysis proposed by Chee and Vu, we construct a new class of permutation codes without interleaving. Our coding scheme, although it is non-constructive, has an order-optimal rate, and in certain circumstances, the rate is higher than that of existing codes based on interleaving.

Every bit of information in a storage or memory device is bound by a multitude of performance specifications, and is subject to a variety of reliability impediments. At the other end, the physical processes tamed to remember our bits offer a constant source of risk to their reliability. These include a variety of noise sources, access restrictions, intercell interferences, cell variabilities, and many more issues. Tying together this vector of performance figures with that vector of reliability issues is a rich matrix of emerging coding tools and techniques. Channel coding schemes ensure target reliability and performance and have been at the core of memory systems since their nascent age. In this survey, we first overview the fundamentals of channel coding and summarize well-known codes that have been used in nonvolatile memories (NVMs). Next, we demonstrate why the conventional coding approaches ubiquitously based on symmetric channel models and optimization for the Hamming metric fail to address the needs of modern memories. We then discuss several recently proposed innovative coding schemes. Behind each coding scheme lies an interesting theoretical framework, building on deep ideas from mathematics and the information sciences. We also survey some of the most fascinating bridges between deep theory and storage performance. While the focus of this survey is primarily on the pervasive multilevel NAND Flash, we envision that other benefiting memory technologies will include phase change memory, resistive memories, and others.

Recent studies on noisy decoding for LDPC codes rely on the assumption that the noise in each component is independent and perpetual. This paper examines a noisy decoding model that generalizes this approach: the noise is due to multi-state channels, where the channel states are governed by queue-like processes. This model is inspired by errors in decoders that are due to the high levels of radiation. This is an important problem, as modern non-volatile memories (NVMs) must perform well in high-radiation environments if they are to be used for deep space applications. High levels of radiation have a significant impact on floating gate-based NVMs, such as flash, and therefore, require well-tuned, powerful error-correcting codes for reliable data storage along with the decoders capable of handling radiation-induced noisy components. We introduce a noisy LDPC decoding model subsuming certain previously studied models. This model is better suited to represent transient errors-in both variable nodes and check nodes-and allows for a more refined analysis compared with older, coarser models. We perform a density evolution-like theoretical evaluation, applicable to both regular and irregular codes, optimize the voting threshold for a Gallager B/E-decoder, and analyze the resulting evaluation. We also examine the finite block length case.

IoT devices need reliable hardware at low cost. It is challenging to efficiently cope with both hard and soft faults in embedded scratchpad memories. To address this problem, we propose a two-step approach: FaultLink and Software-Defined Error-Localizing Codes (SDELC). FaultLink avoids hard faults found during testing by generating a custom-tailored application binary image for each individual chip. During software deployment-time, FaultLink optimally packs small sections of program code and data into fault-free segments of the memory address space and generates a custom linker script for a lazy-linking procedure. During run-time, SDELC deals with unpredictable soft faults via novel and inexpensive Ultra-Lightweight Error-Localizing Codes (UL-ELCs). These require fewer parity bits than single-error-correcting Hamming codes. Yet our UL-ELCs are more powerful than basic single-error-detecting parity: they localize single-bit errors to a specific chunk of a codeword. SDELC then heuristically recovers from these localized errors using a small embedded C library that exploits observable side information (SI) about the application’s memory contents. SI can be in the form of redundant data (value locality), legal/illegal instructions, etc. Our combined FaultLink+SDELC approach improves min-VDD by up to 440 mV and correctly recovers from up to 90% (70%) of random single-bit soft faults in data (instructions) with just three parity bits per 32-bit word.

This paper studies problems in data reconstruction, an important area with numerous applications. In particular, we examine the reconstruction of binary and nonbinary sequences from synchronization (insertion/deletion-correcting) codes. These sequences have been corrupted by a fixed number of symbol insertions (larger than the minimum edit distance of the code), yielding a number of distinct traces to be used for reconstruction. We wish to know the minimum number of traces needed for exact reconstruction. This is a general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding an upper bound on the number of distinct traces necessary to guarantee exact reconstruction. Without specific knowledge of the code words, this upper bound is tight. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT code word pairs achieve the worst case number of outputs needed for exact reconstruction. We also consider extensions to other channels, such as adversarial deletion and insertion/deletion channels and probabilistic channels.

Transmission channels underlying modern memory systems, e.g., Flash memories, possess a significant amount of asymmetry. While existing LDPC codes optimized for symmetric, AWGN-like channels are being actively considered for Flash applications, we demonstrate that, due to channel asymmetry, such approaches are fairly inadequate. We propose a new, general, combinatorial framework for the analysis and design of non-binary LDPC (NB-LDPC) codes for asymmetric channels. We introduce a refined definition of absorbing sets, which we call general absorbing sets (GASs), and an important subclass of GASs, which we refer to as general absorbing sets of type two (GASTs). Additionally, we study the combinatorial properties of GASTs. We then present the weight consistency matrix (WCM), which succinctly captures key properties in a GAST. Based on these new concepts, we then develop a general code optimization framework, and demonstrate its effectiveness on the realistic highly-asymmetric normal-Laplace mixture (NLM) Flash channel. Our optimized codes enjoy over one order (resp., half of an order) of magnitude performance gain in the uncorrectable BER (UBER) relative to the unoptimized codes (resp. the codes optimized for symmetric channels).

We study the problem of perfectly reconstructing sequences from traces. The sequences are codewords from a deletion/insertion-correcting code and the traces are the result of corruption by a fixed number of symbol insertions (larger than the minimum edit distance of the code.) This is the general version of a problem tackled by Levenshtein for uncoded sequences. We introduce an exact formula for the maximum number of common supersequences shared by sequences at a certain edit distance, yielding a tight upper bound on the number of distinct traces necessary to guarantee exact reconstruction. We apply our results to the famous single deletion/insertion-correcting Varshamov-Tenengolts (VT) codes and show that a significant number of VT codeword pairs achieve the worst-case number of outputs needed for exact reconstruction.

File synchronization is a critical component of many modern data sharing applications. File synchronization is particularly challenging when different versions of a file that need to be synchronized differ in some number of edits. Several recent works have studied exact synchronization under edit errors. In this paper, we extend the available analytical toolbox of file synchronization by focusing on a previously unaddressed case of approximate synchronization wherein the reconstructed file need not be the same as the original file, but rather only be within some predetermined distortion. We study the case when a binary file undergoes symbol-level deletion errors with some small deletion rate (so that the total number of deletions is linear in file length). We derive a simple upper bound on the optimal rate of information that the transmitter (owner of the original file) needs to provide to the receiver (owner of the edited file) to allow the receiver to reconstruct the original file to within a predefined target distortion. We then create an approximate synchronization algorithm based on interactive communication between the transmitter and the receiver, and analyze the expected normalized communication bandwidth of our algorithm for various target distortion levels. Lastly, we implement our algorithm and provide experimental results on the approximate synchronization of a noisy image.

Transmission channels underlying modern dense storage systems, e.g., Flash memory and magnetic recording (MR) systems, significantly differ from canonical channels, like additive white Gaussian noise (AWGN) channels. While existing low-density parity-check (LDPC) codes optimized for symmetric, AWGN-like channels are being actively considered for Flash applications, we demonstrate that, due to channel asymmetry, such approaches are inadequate. We introduce a refined definition of absorbing sets, which we callgeneral absorbing sets of type two (GASTs), and study the combinatorial properties of GASTs. We then present theweight consistency matrix (WCM), which succinctly captures key properties in a GAST. Furthermore, we show how to customize the WCM definition such that it suits other special subclasses of GASTs. Based on these new concepts, we then develop a new, general combinatorial code optimization framework, which we call theWCM framework, and demonstrate its effectiveness on the realistic highly-asymmetric normal-Laplace mixture (NLM) Flash channel. Moreover, we show that our framework can be customized to optimize non-binary LDPC (NB-LDPC) codes for other asymmetric channels, channels with memory (incorporated in MR systems), and canonical symmetric channels. For all the channels we have simulated NB-LDPC codes over, the codes optimized using the WCM framework enjoy at least 1 order, and up to nearly 2 orders of magnitude performance gain in the uncorrectable bit error rate (UBER) or the frame error rate (FER) relative to the unoptimized codes. Our simulations also show that codes optimized for symmetric channels are not the best choice for asymmetric channels.

In this paper, we characterize the finite-length performance of separable circulant-based spatially-coupled (SCB-SC) LDPC codes for transmission over the additive white Gaussian noise channel. For a general class of finite-length graph-based codes, it is known that the existence of small absorbing sets causes a performance degradation in the error floor regime. We first present the mathematical conditions for the existence of absorbing sets in binary SCB-SC codes. This analysis enables us to find the exact number of absorbing sets as a function of the design parameters. In particular, our results show that the choice of the cutting vector affects the number of absorbing sets and, therefore, the error floor performance of the code. For a fixed column weight, we find provably optimal cutting vectors that result in the least number of absorbing sets. Furthermore, we extend our analysis to nonbinary SCB-SC codes, where we show that the choice of the cutting vector is not as critical as in the binary case. We provide an algorithm which provably removes the problematic nonbinary absorbing sets from nonbinary SCB-SC codes by informed selection of edge labels. Our simulation results show the superior error floor performance of our designed binary and nonbinary SCB-SC codes compared with binary unstructured and nonbinary quasi-cyclic SC codes available in the open literature.

In this paper, we provide a comprehensive analysis of the error floor along with code optimization guidelines for structured and regular non-binary low-density parity-check (NB-LDPC) codes in magnetic recording (MR) applications. While the topic of the error floor performance of binary LDPC codes over additive white Gaussian noise (AWGN) channels has recently received considerable attention, very little is known about the error floor performance of NB-LDPC codes over other types of channels, despite the early results demonstrating superior characteristics of NB-LDPC codes relative to their binary counterparts. We first show that, due to the outer looping between the detector and the decoder in the receiver, the error profile of NB-LDPC codes over partial-response (PR) channels is qualitatively different from the error profile over AWGN channels—this observation motivates us to introduce new combinatorial objects aimed at capturing decoding errors that dominate the PR channel error floor region. We call these objects balanced absorbing sets (BASs), which are viewed as a special subclass of previously introduced absorbing sets (ASs). Aided by these new objects (BASs), we develop a method that combines analytical equations and biased simulations to predict the error floor performance of NB-LDPC codes over PR channels without the need to execute extensive Monte Carlo (MC) simulations. We show that explicitly incorporating the inter-symbol interference of MR channels into our prediction method makes the accuracy of the error floor estimate within 0.2 of an order of magnitude from the traditional MC simulation. In addition, we prove that, due to the more restrictive definition of BASs (relative to the more general class of ASs), an additional degree of freedom can be exploited in the code design for PR channels. We then demonstrate that the proposed code optimization aimed at removing dominant BASs offers performance improvements in the frame error rate in the error floor region by up to 2.5 orders of magnitude over the unoptimized designs. Our code optimization technique carefully, yet provably, removes BASs from the code while preserving its overall structure (node degree, quasi-cyclic property, regularity, and so forth). The resulting codes outperform the existing binary and NB-LDPC solutions for PR channels by about 2.5 and 1.25 orders of magnitude, respectively.

Developing efficient algorithms to synchronize between different versions of files is an important problem with numerous applications. We consider the interactive synchronization protocol introduced by Yazdi and Dolecek, based on an earlier synchronization algorithm by Venkataramanan et al. Unlike preceding synchronization algorithms, Yazdi and Dolecek's algorithm is specifically designed to handle a number of deletions linear in the length of the file. We extend this algorithm in three ways. First, we handle nonbinary files. Second, these files contain symbols chosen according to nonuniform distributions. Finally, the files are modified by both insertions and deletions. We take into consideration the collision entropy of the source and refine the matching graph developed by Yazdi and Dolecek by appropriately placing weights on the matching graph edges. We compare our protocol with the widely used synchronization software rsync, and with the synchronization protocol by Venkataramanan et al. In addition, we provide tradeoffs between the number of rounds of communication and the total amount of bandwidth required to synchronize the two files under various implementation choices of the baseline algorithm. Finally, we show the robustness of the protocol under imperfect knowledge of the properties of the edit channel, which is the expected scenario in practice.

Error-correcting codes for permutations have received considerable attention in the past few years, especially in applications of the rank modulation scheme for flash memories. While codes over several metrics have been studied, such as the Kendall τ, Ulam, and Hamming distances, no recent research has been carried out for erasures and deletions over permutations. In rank modulation, flash memory cells represent a permutation, which is induced by their relative charge levels. We explore problems that arise when some of the cells are either erased or deleted. In each case, we study how these erasures and deletions affect the information carried by the remaining cells. In particular, we study models that are symbol-invariant, where unaffected elements do not change their corresponding values from those in the original permutation, or permutation-invariant, where the remaining symbols are modified to form a new permutation with fewer elements. Our main approach in tackling these problems is to build upon the existing works of error-correcting codes and leverage them in order to construct codes in each model of deletions and erasures. The codes we develop are in certain cases asymptotically optimal, while in other cases, such as for codes in the Ulam distance, improve upon the state of the art results.

In this paper, we analyze and optimize non- binary low-density parity-check (NB-LDPC) codes for magnetic recording applications. While the topic of the error floor performance of binary LDPC codes over additive white Gaussian noise (AWGN) channels has recently received considerable attention, very little is known about the error floor performance of NB-LDPC codes over other types of channels, despite the early results demonstrating superior characteristics of NB-LDPC codes relative to their binary counterparts. We first show that, due to outer looping between detector and decoder in the receiver, the error profile of NB-LDPC codes over partial-response (PR) channels is qualitatively different from the error profile over AWGN channels - this observation motivates us to introduce new combinatorial definitions aimed at capturing decoding errors that dominate PR channel error floor region. We call these errors (or objects) balanced absorbing sets (BASs), which are viewed as a special subclass of previously introduced absorbing sets (ASs). Additionally, we prove that due to the more restrictive definition of BASs (relative to the more general class of ASs), an additional degree of freedom can be exploited in code design for PR channels. We then demonstrate that the proposed code optimization aimed at removing dominant BASs offers improvements in the frame error rate (FER) in the error floor region by up to 2.5 orders of magnitude over the uninformed designs. Our code optimization technique carefully yet provably removes BASs from the code while preserving its overall structure (node degree, quasi-cyclic property, regularity, etc.). The resulting codes outperform existing binary and NB-LDPC solutions for PR channels by about 2.5 and 1.5 orders of magnitude, respectively.

In the infinite blocklength regime, spatially-coupled LDPC codes are capable of achieving capacity-approaching performance under message-passing decoding. In the finite blocklength regime, it is known that absorbing sets compete with the codewords to be the output of sub-optimal message-passing decoders: the existence of such sets in the Tanner graph of LDPC codes causes performance degradation in the low error rate region. This paper presents a mathematical approach to finding the exact number of absorbing sets in array-based spatially-coupled (AB-SC) codes. Our analysis is universal in the sense that it is in principle applicable to absorbing sets of any size. Moreover, all design parameters of AB-SC codes such as the coupling length, the circulant size, and the cutting vector are considered in the presented count. Based on our analysis, we present an approach to find provably minimal cutting vectors, with respect to the number of absorbing sets, for the construction of AB-SC codes with various circulant sizes. Simulation results show the superior error floor performance of AB-SC codes with the minimal cutting vector compared to AB-SC codes with randomly-selected cutting vectors. We also provide the average number of non-binary absorbing sets in the Tanner graph of non-binary AB-SC codes constructed by uninformed (random) assignment of edge weights to a binary AB-SC code.

With scaling of process technologies and increase in process variations, embedded memories will be inherently unreliable. In this paper, we propose redundancy-free adaptive error-correcting codes for the noisy min-sum decoder subject to memory errors. We consider the popular memory error model with a binary symmetric channel. We first revisit the density evolution analysis proposed by Balatsoukas-Stimming and Burg for the noisy min-sum decoder. Two important consequences of the density evolution analysis are: (a) after a large enough number of iterations, most of the messages have large magnitudes, and the residual errors are mostly from the sign bit flips due to memory failures, and (b) errors in the least significant bits in large-magnitude messages have a negligible effect on the residual error rate. We thus propose adaptive error-correcting codes to protect sign bits by least significant bits when the messages have large magnitudes. The proposed coding scheme does not require any further data storage (i.e., this code is redundancy-free). Density evolution analysis for the noisy min-sum decoder implementing the proposed coding scheme is derived, demonstrating that the proposed decoder achieves a residual error rate that is on the order of the square of the residual error rate achieved by the nominal min-sum decoder. Simulation results on the finite block length LDPC code also agree with this density evolution analysis.

Although the insertion/deletion problem has been studied for more than fifty years, many results still remain elusive. The goal of this work is to present three novel theorems with a combinatorial flavor that shed further light on the structure and nature of insertions/deletions. In particular, we give an exact result for the maximum number of common supersequences between two sequences, extending older work by Levenshtein. We then generalize this result for sequences that have different lengths. Finally, we compute the exact neighborhood size for the binary circular (alternating) string Cn= 0101 ... 01. In addition to furthering our understanding of the insertion/deletion channel, these theorems can be used as building blocks in other applications. One such application is developing improved lower bounds on the sizes of insertion/deletion-correcting codes.

Research works exploring coding for Flash memories typically seek to correct errors taking place during normal device operation. In this paper, we study the design of codes that protect Flash devices dealing with the unusual class of errors caused by exposure to large radiation dosages. Significant radiation exposure can take place, for example, when Flash is used as on-board memory in satellites and space probes. We introduce an error model that captures the effects of radiation exposure. Such errors are asymmetric, with the additional feature that the degree (and direction) of asymmetry depends on the stored sequence. We develop an appropriate distance and an upper bound on the sizes of codes which correct such errors. We introduce and analyze several simple code constructions.

Error-correcting codes are a critical need for modern flash memories. Such codes are typically designed under the assumption that the voltage threshold distributions in flash cells are Gaussian. This assumption, however, is not realistic. This is particularly the case late in the lifetime of flash devices. A recent work by Parnell et al. provides a parameterized model of MLC (2-bit cell) flash which accurately represents the voltage threshold distributions for an operating period up to 10 times longer than the device's specified lifetime. We analyze this model from an information-theoretic perspective and compute capacity for the resulting channel. We extrapolate the channel from an MLC to a TLC (3-bit cell) model and we characterize the resulting errors. We show that errors under the improved model are highly asymmetric. We introduce a code construction explicitly designed to exploit the asymmetric nature of these errors, and measure its improvement against existing codes at large P/E cycle counts.

The wide recognition that emerging nano-devices will be inherently unreliable motivates the evaluation of information processing algorithms running on noisy hardware as well as the design of robust schemes for reliable performance against hardware errors of varied characteristics. In this paper, we investigate the performance of a popular statistical inference algorithm, belief propagation (BP) on probabilistic graphical models, implemented on noisy hardware, and we propose two robust implementations of the BP algorithm targeting different computation noise distributions. We assume that the BP messages are subject to zero-mean transient additive computation noise. We focus on graphical models satisfying the contraction mapping condition that guarantees the convergence of the noise-free BP. We first upper bound the distances between the noisy BP messages and the fixed point of (noise-free) BP as a function of the iteration number. Next, we propose two implementations of BP, namely, censoring BP and averaging BP, that are robust to computation noise. Censoring BP rejects incorrect computations to keep the algorithm on the right track to convergence, while averaging BP takes the average of the messages in all iterations up to date to mitigate the effects of computation noise. Censoring BP works effectively when, with high probability, the computation noise is exactly zero, and averaging BP, although having a slightly larger overhead, works effectively for general zero-mean computation noise distributions. Sufficient conditions on the convergence of censoring BP and averaging BP are derived. Simulations on the Ising model demonstrate that the two proposed implementations successfully converge to the fixed point achieved by noise-free BP. Additionally, we apply averaging BP to a BP-based image denoising algorithm and as a BP decoder for LDPC codes. In the image denoising application, averaging BP successfully denoises an image even when nominal BP fails to do so in the presence of computation noise. In the BP LDPC decoder application, the power of averaging BP is manifested by the reduction in the residual error rates compared with the nominal BP decoder.

With scaling of process technologies and increase in process variations, embedded memories will be inherently unreliable. Approximate computing is a new class of techniques that relax the accuracy requirement of computing systems. In this paper, we present the Adaptive Coding for approximate Computing (ACOCO) framework, which provides us with an analysis-guided design methodology to develop adaptive codes for different computations on the data read from faulty memories. In ACOCO, we first compress the data by introducing distortion in the source encoder, and then add redundant bits to protect the data against memory errors in the channel encoder. We are thus able to protect the data against memory errors without additional memory overhead so that the coded data have the same bit-length as the uncoded data. We design the source encoder by first specifying a cost function measuring the effect of the data compression on the system output, and then design the source code according to this cost function. We develop adaptive codes for two types of systems under ACOCO. The first type of systems we consider, which includes many machine learning and graph-based inference systems, is the systems dominated by product operations. We evaluate the cost function statistics for the proposed adaptive codes, and demonstrate its effectiveness via two application examples: max-product image denoising and naïve Bayesian classification. Next, we consider another type of systems: iterative decoders with min operation and sign-bit decision, which are widely applied in wireless communication systems. We develop an adaptive coding scheme for the min-sum decoder subject to memory errors. A density evolution analysis and simulations on finite length codes both demonstrate that the decoder with our adaptive code achieves a residual error rate that is on the order of the square of the residual error rate achieved by the nominal min-sum decoder.

With the wide recognition that modern nanoscale devices will be error-prone, characterization of reliability of information processing systems built out of unreliable components has become an important topic. In this paper, we analyze the performance of orthogonal matching pursuit (OMP), a popular sparse recovery algorithm, running on faulty circuits. We identify sufficient conditions for correct recovery of the signal support and express these conditions in terms of the relationship among signal magnitudes, sparsity, and the mutual incoherence of the measurement matrix. We study both the effects of additive errors in arithmetic computations and logical errors in comparators. We find that the additive errors in the OMP computations have an impact on the overall performance comparable to that of the additive noise in the input measurements. We also show that parallel structures are more robust to logical errors than serial structures in the implementation of a noisy arg max operation, and thus lead to a better OMP performance.

The goal of this paper is to present constructions of high-rate nonbinary write-once memory (WOM) codes for multilevel flash memories. The constructions provided here are all based on the basic idea of mapping high-rate binary codebooks to nonbinary codebooks. The proposed codes maintain the same length and encoding complexity as their underlying binary constituents. We begin by presenting some elementary, yet rate-efficient constructions. Afterward, we consider a high-rate two-write WOM-code defined over an alphabet of size four. In addition, we consider the application of our constructions to the creation of fixed-rate WOM codes. The constructions presented in this paper improve upon the best-known code constructions for certain code lengths.

This paper studies new bounds and code constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin-Rao codes) can correct a single grain-error. In many cases of interest, our results improve upon the currently best known bounds and constructions. Some of the approaches adopted in the context of grain-errors may have application to related channel models.

Non-binary low-density parity-check (NB-LDPC) codes exhibit excellent error correction performance at the cost of high computational complexity of the decoding algorithm. A logarithmic quantization scheme is proposed to reduce the VLSI implementation cost of the Min-Max decoding algorithm, by scaling down the complexity of the check node calculations that are the prime bottleneck in NB-LDPC decoding. The proposed scheme is also shown to be robust against certain types of errors, and thus enables excellent error correction capabilities even for aggressively reduced wordlengths, relative to traditional, uniform quantization schemes that exhibit either poor waterfall region performance or high error floors for a similar number of bits. The proposed scheme is directly applicable to existing architectures with few modifications and is shown to reduce the computational complexity by up to 40%, especially for large field orders.

Motivated by the rank modulation scheme for flash memories, we consider an information representation system with relative values (permutations) and study codes for correcting deletions. In contrast to the case of a deletion in a regular (with absolute values) representation system, a deletion in this new paradigm results in a new permutation over the remaining symbols. For example, the deletion of 3 (or 2) from (1, 3, 2, 4) yields (1, 2, 3); while the deletion of 1 yields (2, 1, 3). Codes for correcting deletions in permutations were studied by Levenshtein under a different model, however, he considered absolute values where the deletions are missing symbols. We study the single deletion relative-values model and prove that a code can correct a single deletion if and only if it can correct a single insertion. Using the concept of a signature of a permutation, we construct single-deletion correcting codes and prove that they are asymptotically optimal with respect to an upper bound that we derive. Finally, we describe an efficient decoding algorithm.

Absorbing sets are combinatorially defined objects existing in the Tanner graph of a low-density parity-check (LDPC) code that have been shown to cause failures in the iterative message-passing decoder when transmission occurs over the additive white Gaussian noise channel. In this paper, we study the absorbing set properties of a class of high-rate array-based spatially coupled LDPC (SC-LDPC) codes that are constructed by coupling together L array-based LDPC block codes. We prove that the smallest absorbing sets existing in the Tanner graph of the SC-LDPC code have the same size as those in the corresponding uncoupled LDPC codes, and the number of such sets grow linearly with L. We show that spatial coupling greatly reduces the average number (per symbol) of minimal sets compared to the uncoupled codes, and we explain that this reduction is due to many absorbing sets and small cycles being `broken' by the coupling process. The large reduction in the number of minimal absorbing sets suggests that array-based SC-LDPC codes will have significantly improved decoding performance in the high signal-to-noise ratio regime compared to the corresponding uncoupled LDPC codes.

Codes based on multiset permutations, or multipermutations, have attracted recent attention due to their applications to non-volatile memories. Most of the literature studying multipermutations is focused on codes capable of correcting errors in the Kendall tau and Ulam metrics. In this work, we make a first effort towards studying synchronization errors over multipermutations. We begin by defining the concept of multipermutation deletions. We characterize the nature and effects of such errors. We provide an expression for the number of multipermutations formed by a single multipermutation deletion. Finally, we introduce code constructions which correct one or more multipermutation deletions.

Non-binary quasi-cyclic (NB-QC) codes are a class of graph-based codes with high performance and implementation-friendly structure. In this paper, we introduce a new method for designing NB-QC codes with improved performance in the low error-rate region. Specifically, we propose a construction which reduces the number of non-binary absorbing sets, which are known to cause errors when decoding non-binary LDPC codes. Our construction is based on a careful selection of the code design parameters. Simulation results demonstrate the superior performance of codes designed according to our technique compared to existing state-of-the-art NB-QC codes.

The development of good codes which are capable of correcting more than a single deletion remains an elusive task. Recent papers, such as that by Kulkarni and Kiyavash [3], instead focus on the more tractable problem of deriving upper bounds on the cardinalities of such codes. In the present work, we develop Gilbert-Varshamov-type lower bounds on the cardinalities of deletion-correcting codes. Our approach is based on the application of results from extremal graph theory. We give several bounds for the cases of binary and non-binary single- and multiple-error correcting codes. We introduce a bound that is, to the best of our knowledge, the strongest existing lower bound on the sizes of deletion-correcting codes. Our work also reveals some structural properties of the underlying Levenshtein graph.

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.

In this work, we first provide the definition of absorbing sets for linear channel codes over non-binary alphabets. In a graphical representation of a non-binary channel code, an absorbing set can be described by a collection of topological and edge labeling conditions. In the non-binary case, the equations relating neighboring variable and check nodes are over a non-binary field, and the edge weights are given by the non-zero elements of that non-binary field. As a consequence, it becomes more difficult for a given structure to satisfy the absorbing set constraints compared to the binary case. This observation in part explains the superior performance of non-binary codes over their binary counterparts. We show that the conditions in the non-binary absorbing set definition can be simplified in the case of non-binary elementary absorbing sets. Based on these simplified conditions, we provide design guidelines for finite-length non-binary codes free of small non-binary elementary absorbing sets. These guidelines demonstrate that even under the preserved topology, the performance of a non-binary graph-based code in the error floor region can be substantially improved by manipulating edge weights so as to avoid small absorbing sets. Our various simulation results suggest that the proposed non-binary absorbing set definition is useful for a range of code constructions and decoders. Finally, by using both insights from graph theory and combinatorial techniques, we establish the asymptotic distribution of non-binary elementary absorbing sets for regular code ensembles.

This paper studies the performance of a noisy Gallager B decoder for regular LDPC codes. We assume that the noisy decoder is subject to both transient processor errors and permanent memory errors. We permit different error rates at different functional components. In addition, for the sake of generality, we allow asymmetry in the permanent error rates of component outputs, and thus we model error propagation in the decoder via a suitable asymmetric channel. We then develop a density evolution-type analysis on this asymmetric channel. The recursive expression for the bit error probability is derived as a function of the code parameters (node degrees), codeword weight, transmission error rate, and the error rates of the permanent and the transient errors. Based on this analysis, we then derive the residual error of the Gallager B decoder for the regime where the transmission error rate and the processing error rates are small. In this regime, we further observe that the residual error rate can be well approximated by a suitable combination of the transient error rate and the permanent error rate at variable nodes, provided that the check node degree is large enough. Based on this insight, we then propose and analyze a scheme for detecting permanent errors and correcting detected residual errors. The scheme exploits the parity check equations of the code and reuses the existing hardware to locate permanent errors in memory blocks. Performance analysis and simulation results show that, with high probability, the detection scheme discovers correct locations of permanent memory errors, while, with low probability, it mislabels the functional memory as being defective. The proposed error detection-and-correction scheme can be implemented in-circuit and is useful in combating failures arising from aging.

This paper provides a comprehensive analysis of nonbinary low-density parity check (LDPC) codes built out of protographs. We consider both random and constrained edge-weight labeling, and refer to the former as the unconstrained nonbinary protograph-based LDPC codes (U-NBPB codes) and to the latter as the constrained nonbinary protograph-based LDPC codes (C-NBPB codes). Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codewords, trapping sets, stopping sets, and pseudocodewords are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. An EXIT chart tool for computing the iterative decoding thresholds of protograph-based LDPC codes is presented, followed by several examples of finite-length U-NBPB and C-NBPB codes with high performance. Throughout this paper, we provide accompanying examples, which demonstrate the advantage of nonbinary protograph-based LDPC codes over their binary counterparts and over random constructions. The results presented in this paper advance the analytical toolbox of nonbinary graph-based codes.

In this paper, we consider a synchronization problem between nodes A and B that are connected through a two-way communication channel. Node A contains a binary file X of length n and node B contains a binary file Y that is generated by randomly deleting bits from X, by a small deletion rate β. The location of deleted bits is not known to either node A or node B. We offer a deterministic, polynomial-time synchronization scheme between nodes A and B that needs a total of O(n βlog 1/β) transmitted bits and reconstructs X at node B with probability of error that is exponentially low in the size of X. Orderwise, the rate of our scheme matches the optimal rate for this channel.

It is widely recognized that emerging hardware technologies will be inherently unreliable. In this paper, we study the performance of finite-alphabet iterative decoders when implemented on noisy hardware built out of unreliable components. We derive a recursive expression for the error probability in terms of both the transmission noise and processing errors. We allow different components of the decoding algorithm associated with certain computational units (i.e., bit and check nodes of varying degrees in the underlying graph) to be implemented using a collection of processors with varying levels of processing error rates. Performance analysis and optimal resource allocation of a noisy Gallager E decoder is presented as an application example of our general derivation. Simulations demonstrate that the implementation of a noisy iterative decoder according to the proposed analysis-guided optimal resource allocation outperforms implementations based on uninformed resource allocation under the common resource budget.

This work provides a generalization of absorbing sets for linear channel codes over non-binary alphabets. In a graphical representation of a non-binary channel code, an absorbing set can be described by a collection of topological and edge labeling conditions. In the non-binary case the equations relating neighboring variable and check nodes are over a non-binary field, and the edge weights are given by the non-zero elements of that non-binary field. As a consequence, it becomes more difficult for a given structure to satisfy the absorbing set constraints. This observation in part explains the superior performance of non-binary codes over their binary counterparts. We first show that, as the field order size increases, the ratio of trapping sets that satisfy the structural conditions of absorbing sets decreases. This suggests that a trapping set-only performance estimation of non-binary codes may not be as accurate in the error floor/high reliability regime. By using both insights from graph theory and combinatorial techniques, we establish the asymptotic distribution of non-binary elementary absorbing sets for regular code ensembles. Finally, we provide design guidelines for finite-length non-binary codes free of small absorbing sets.

We study the problem of synchronizing two files X and Y at two distant nodes A and B that are connected through a two-way communication channel. We assume that file Y at node B is obtained from file X at node A by inserting and deleting a small fraction of symbols in X. More specifically, we consider the case where X is a non-binary non-uniform string, and deletions and insertions happen uniformly with rates β d and β i , respectively. We propose a synchronization protocol between node A and node B that needs to transmit O(q/H 2 (β d +β i )n log 1/β d +β i ) bits (where n is the length of X, q is the alphabet size and H 2 is the collision entropy of X) and reconstructs X at node B with error probability exponentially low in n. This protocol readily generalizes the recent result by Tabatabaei Yazdi and Dolecek that dealt with synchronization from binary uniform source and under only deletion errors.

This paper studies new bounds and constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. The main theme of the paper is that codes capable of correcting grain-errors are related to codes that correct insertions/deletions and codes that correct asymmetric errors. Using this insight, new bounds on the maximum cardinality of a grain-error correcting code are derived and constructions of codes that correct grain-errors are considered. It is also demonstrated that permutations of the classical group codes can correct a single grain-error. In several cases of interest, our results improve upon the currently best known bounds and constructions.

In this paper, the performance of a noisy Gallager B decoder used to decode regular LDPC codes is studied. We assume that the noisy decoder is subject to both transient processor errors and permanent memory errors. Due to the asymmetric nature of permanent errors, we model error propagation in the decoder via a suitable asymmetric channel. We then develop a density evolution type analysis on this asymmetric channel. The recursive expression for the bit error probability is derived as a function of the code parameters (node degrees), codeword weight, transmission error rate and the error rates of the permanent and the transient errors. Based on this analysis, we then derive the residual error of the Gallager B decoder for the regime where the transmission error rate and the processing error rates are small. In this regime, we further observe that the residual error can be well approximated by the sum of suitably combined transient errors and permanent errors, provided that the check node degree is large enough. Based on this insight we then propose and analyze a simple scheme for detecting permanent errors. The scheme exploits the parity check equations of the code itself and reuses the existing hardware to locate permanent errors in memory blocks. With high probability, the detection scheme discovers correct locations of permanent memory errors, while, with low probability, it mislabels the functional memory as being defective.

Synchronization channels, which can remove codeword symbols or introduce extraneous symbols, pose additional difficulties when compared to the commonly-studied substitution channel. A traditional problem in this area is to count the number of sequences formed when deleting a fixed number of symbols from a sequence. This work contains our first effort towards solving a similar, yet previously unexplored, problem: deriving bounds on the number of sequences obtained by deleting and inserting a fixed number of symbols.

We study the competing goals of utility and privacy as they arise when a provider delegates the processing of its personal information to a recipient who is better able to handle this data. We formulate our goals in terms of the inferences which can be drawn using the shared data. A whitelist describes the inferences that are desirable, i.e., providing utility. A blacklist describes the unwanted inferences which the provider wants to keep private. We formally define utility and privacy parameters using elementary information-theoretic notions and derive a bound on the region spanned by these parameters. We provide constructive schemes for achieving certain boundary points of this region. Finally, we improve the region by sharing data over aggregated time slots.

Rank modulation schemes for non-volatile memories (NVMs) represent information by the relative rankings of cell charge levels. This approach has several benefits; in particular, the scheme resolves the “write-asymmetry” limitation that NVMs suffer from. However, cell writing is still affected by a common NVM problem: inter-cell coupling, which can result in inadvertently increasing the charge level of neighboring cells. This is a potential source of error in the rank modulation scheme. In this paper, we explore the idea of constrained coding over permutations. These constraints minimize the impact of inter-cell coupling while still allowing the use of the rank modulation scheme. We study various constraints and their resulting rates, capacities, and other properties, and introduce an explicit constrained rank modulation code construction.

Microelectronic circuits exhibit increasing variations in performance, power consumption, and reliability parameters across the manufactured parts and across use of these parts over time in the field. These variations have led to increasing use of overdesign and guardbands in design and test to ensure yield and reliability with respect to a rigid set of datasheet specifications. This paper explores the possibility of constructing computing machines that purposely expose hardware variations to various layers of the system stack including software. This leads to the vision of underdesigned hardware that utilizes a software stack that opportunistically adapts to a sensed or modeled hardware. The envisioned underdesigned and opportunistic computing (UnO) machines face a number of challenges related to the sensing infrastructure and software interfaces that can effectively utilize the sensory data. In this paper, we outline specific sensing mechanisms that we have developed and their potential use in building UnO machines.

It is well recognized that low-density parity-check (LDPC) codes can suffer from an error floor when decoded iteratively. This performance degradation is often attributed to the class of objects known as trapping sets. Past work has focused on characterizing the distribution of trapping sets for a variety of code ensembles, including regular, irregular and structured LDPC codes. As a subset of the trapping set collection, there exists a class of graphical structures called the absorbing sets. An absorbing set is a combinatorially-defined object; in particular a fully absorbing set is stable under bit-flipping decoding. By construction, there can exist trapping sets that are not stable under such a decoder. As a result, for finite-precision, iterative decoding algorithms used over additive channels, absorbing sets can describe decoding errors more accurately than the broader class of trapping sets. In this paper, we compute the normalized logarithmic asymptotic distributions of absorbing sets and fully absorbing sets, including elementary (fully) absorbing sets. The calculations are based on the trapping set enumeration method proposed by Milenkovic, Soljanin, and Whiting in [1]. We compare distributions of absorbing and trapping sets for representative code parameters of interest, and quantify the (lack of) discrepancies between the two. Good absorbing set properties are implied for known structured LDPC codes, including repeat accumulate codes and protograph-based constructions. Establishing the distribution of fully absorbing sets (especially when the discrepancy with the trapping set distribution is significant) allows one to further refine the estimates of the error rates under bit-flipping and related decoders.

In non-volatile memories, reading stored data is typically done through the use of predetermined fixed thresholds. However, due to problems commonly affecting such memories, including voltage drift, overwriting, and inter-cell coupling, fixed threshold usage often results in significant asymmetric errors. To combat these problems, Zhou, Jiang, and Bruck recently introduced the notion of dynamic thresholds and applied them to the reading of binary sequences. In this paper, we explore the use of dynamic thresholds for multi-level cell (MLC) memories. We provide a general scheme to compute and apply dynamic thresholds and derive performance bounds. We show that the proposed scheme compares favorably with the optimal thresholding scheme. Finally, we develop limited-magnitude error-correcting codes tailored to take advantage of dynamic thresholds.

Conventional communications theory assumes that the data transmission is noisy but the processing at the receiver is entirely error-free. Such assumptions may have to be revisited for advanced (silicon) technologies in which hardware failures are a major concern at the system-level. Hence, it is important to characterize the performance of a communication system with both noisy processing components and noisy data transmission. Coding systems based on low-density parity check (LDPC) codes are widely used for a variety of applications. In this paper, we focus on probabilistic analysis of the LDPC Gallager B decoder built out of faulty components. Using the density evolution technique, we find approximations for the optimal threshold of the decoder and the symbol error rate (SER) of the decoded sequence as functions of both the channel error rate and error rates of the decoder components, for both binary and non-binary regular LDPC codes. Furthermore, we study the convergence of the output SER and the decoding threshold of the decoder for different ranges of error rates. We verify our results using MATLAB simulations and hardware emulation of noisy decoders. Results presented in this paper can serve as systematic design guidelines in resource allocation for noisy decoders. Informed resource allocation is of particular relevance to emerging data storage and processing applications that need to maintain high levels of reliability despite hardware errors in advanced technologies.

Flash memory is a promising new storage technology. Supported by empirical data collected from a Flash memory device, we propose a class of codes that exploits the asymmetric nature of the error patterns in a Flash device using tensor product operations. We call these codes graded bit-error-correcting codes. As demonstrated on the data collected from a Flash chip, these codes significantly delay the onset of errors and therefore have the potential to prolong the lifetime of the memory device.

For low-density parity-check (LDPC) codes operating over additive white Gaussian noise channels and decoded using message-passing decoders with limited precision, absorbing sets have been shown to be a key factor in error floor behavior. Focusing on this scenario, this paper introduces the cycle consistency matrix (CCM) as a powerful analytical tool for characterizing and avoiding absorbing sets in separable circulant-based (SCB) LDPC codes. SCB codes include a wide variety of regular LDPC codes such as array-based LDPC codes as well as many common quasi-cyclic codes. As a consequence of its cycle structure, each potential absorbing set in an SCB LDPC code has a CCM, and an absorbing set can be present in an SCB LDPC code only if the associated CCM has a nontrivial null space. CCM-based analysis can determine the multiplicity of an absorbing set in an SCB code, and CCM-based constructions avoid certain small absorbing sets completely. While these techniques can be applied to an SCB code of any rate, lower rate SCB codes can usually avoid small absorbing sets because of their higher variable-node degree. This paper focuses attention on the high-rate scenario in which the CCM constructions provide the most benefit. Simulation results demonstrate that under limited-precision decoding the new codes have steeper error-floor slopes and can provide one order of magnitude of improvement in the low-frame-error-rate region.

This brief presents a technique to evaluate the timing variation of static random access memory (SRAM). Specifically, a method called loop flattening, which reduces the evaluation of the timing statistics in the complex highly structured circuit to that of a single chain of component circuits, is justified. Then, to very quickly evaluate the timing delay of a single chain, a statistical method based on importance sampling augmented with targeted high-dimensional spherical sampling can be employed. The overall methodology has shown 650× or greater speedup over the nominal Monte Carlo approach with 10.5% accuracy in probability. Examples based on both the large-signal and small-signal SRAM read path are discussed, and a detailed comparison with state-of-the-art accelerated statistical simulation techniques is given.

Today's mainstream electronic systems typically assume that transistors and interconnections operate correctly over their useful lifetime. For coming generations of silicon technologies, several causes of hardware failures, such as erratic bit errors, transient (soft) errors, and process variations, are becoming significant. In contrast to the traditional redundancy-based reliability solutions, the aim of a probabilistic design is to achieve high quality results and efficiency using erroneous or imperfect components along with a judicious allocation of resources. In this paper we focus on a probabilistic analysis of an LDPC Gallager B decoder made out of unreliable hardware components. Our analysis reveals the dependencies between the final BER at the output of the decoder and the errors in the components of the decoder. We demonstrate that a system design guided by our analysis can produce higher quality results compared to an arbitrary resource allocation. This resource allocation is of particular relevance to emerging storage applications that need to maintain extremely high levels of reliability even as the underlying technology scales deep into the nano-regime.

This paper introduces a novel class of non-binary graph-based codes, built upon graph covers of non-binary protograph LDPC codes. This new ensemble is more restrictive than previously considered constructions, but in turn is much simpler to design and implement. The simplifications in design allow for the enumeration of codeword weight, trapping set size, stopping set size, and pseudo codeword weights, both as exact quantities in the finite-length regime and as corresponding growth rates in the asymptotic setting. The presented construction and the accompanying enumerations enhance the analytical toolbox of non-binary LDPC codes.

Flash memory is a promising new storage technology. To fully utilize future multi-level cell Flash memories, it is necessary to develop error correction coding schemes attuned to the underlying physical characteristics of Flash. Based on a careful inspection of fine-grained, experimentally-collected error patterns of TLC (three bits per cell) Flash, we propose a mathematical model that captures the intracell variability, which is manifested by certain patterns of bit-errors. Error correction codes are constructed for this model based upon generalized tensor product codes. For fixed levels of redundancy, these codes are shown to exhibit substantially lower bit error rates than existing error correction schemes.

Importance sampling is a popular approach to estimate rare event failures of SRAM cells. We propose to improve importance sampling by probability collectives. First, we use "Kullback-Leibler (KL) distance" to measure the distance between the optimal sampling distribution and the original sampling distribution of variable process parameters. Further, the probability collectives (PC) technique using immediate sampling is adapted to analytically minimize the KL distance and to obtain a sampling distribution as close to the optimal as possible. The proposed algorithm significantly accelerates the convergence of importance sampling. Experiments demonstrate that proposed algorithm is 5200X faster than the Monte Carlo approach and achieves more than $40X$ speedup over other existing state-of-the-art techniques without compromising estimation accuracy.

This paper presents two complementary constructions of finite-length non-binary protograph-based codes with the focus on the short block-length regime. The first class is based on the existing approaches of applying the copy-and-permute operations to the constituent protograph with unweighted edges, followed by assigning non-binary scales to the edges of the derived graph. The second class is novel and is based on the so-called graph cover of a non-binary protograph: the original protograph has fixed edge scalings and copy-and-permute operations are applied to the edge-weighted protograph. The second class is arguably more restrictive, but in turn it offers simpler design and implementation. We provide design and construction of these non-binary codes for short block-lengths. Performance, cycle distribution and the minimum distance of the binary image of selected codes over AWGN is provided for information block-lengths as low as 64 bits.

In this paper we address the problem of statistical spectrum sensing attacks, where misbehaving nodes falsify their sensing reports with a certain probability in order to artificially increase or reduce the throughput of a cognitive network. Instead of trying to identify unreliable nodes and exclude them from the decision process, we propose a novel approach where spectrum sensing and estimation of type/probability of the attacks are performed jointly. Our method is based on a Bayesian formulation and is implemented using belief propagation on factor graphs. The performance of the proposed method is then evaluated by analytical results and by simulations.

Regular LDPC codes tend to have better error-floor behavior than irregular LDPC codes. However, for moderate block lengths and high rates, the error floor remains a concern even for regular LDPC codes. This is especially the case for applications such as memory media that require very low frame error rates (FERs). This paper focuses on a class of regular LDPC codes: separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix and include array-based LDPC codes as well as many common quasi-cyclic codes. SCB codes retain standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with existing high-throughput hardware implementations. This paper introduces a cycle consistency matrix (CCM) for each possible absorbing set in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Using this novel observation, a new code construction approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. Simulation results demonstrate that the new codes have steeper error-floor slopes and provide at least one order of magnitude of improvement in the low FER region. Identifying absorbing-set-spectrum equivalence classes within the family of SCB codes with a specified circulant matrix significantly reduces the search space of possible code matrices.

In this paper we propose a computationally-efficient, iterative decoding algorithm that is well-suited for storage systems with very stringent reliability constraints and low redundancy/high code rate requirements. The proposed Dual-Scaling Min-Sum (DS-MSA) overcomes certain deficiencies of the Min-Sum approximation when used for decoding graph-based codes. We observe that a small but non-negligible fraction of check-to-variable messages is underestimated by the Normalized Min-Sum algorithm in the low error rate region. By carefully adjusting the scaling factor for the variable-to-check message with the smallest magnitude, we develop the DS-MSA algorithm characterized by two scaling parameters. The proposed algorithm (1) outperforms Sum-Product and (Normalized) Min-Sum algorithms in the very low error rate regime, (2) maintains the low-complexity feature of the Min-Sum, and (3) can be easily combined with existing decoder implementations.

This paper considers the ensemble enumerators of protograph-based nonbinary (PB NB) LDPC codes. Equipped with combinatorial definitions extended to the nonbinary domain, ensemble enumerators of codeword weight, trapping set size and stopping set size are calculated. The exact enumerators are presented in the finite-length regime, and the corresponding growth rates are calculated in the asymptotic regime. Our results can provide useful analytical tools for a range of communication and storage applications employing nonbinary LDPC codes.

This work investigates the structure of capacity achieving write once memory codes with particular attention to the case where each cell of the flash memory device is capable of representing more than one bit. These results are used to characterize the rates achieved across generations for capacity achieving codes as well to construct a high rate ternary two write code. Additionally, the problem of maximizing the sum rate for two writes given that both writes encode at the same rate is considered.

This paper focuses on controlling the absorbing set spectrum for a class of regular LDPC codes known as separable, circulant-based (SCB) codes. For a specified circulant matrix, SCB codes all share a common mother matrix, examples of which are array-based LDPC codes and many common quasi-cyclic codes. SCB codes retain the standard properties of quasi-cyclic LDPC codes such as girth, code structure, and compatibility with efficient decoder implementations. In this paper, we define a cycle consistency matrix (CCM) for each absorbing set of interest in an SCB LDPC code. For an absorbing set to be present in an SCB LDPC code, the associated CCM must not be full column-rank. Our approach selects rows and columns from the SCB mother matrix to systematically eliminate dominant absorbing sets by forcing the associated CCMs to be full column-rank. We use the CCM approach to select rows from the SCB mother matrix to design SCB codes of column weight 5 that avoid all low-weight absorbing sets (4; 8), (5; 9), and (6; 8). Simulation results demonstrate that the newly designed code has a steeper error-floor slope and provides at least one order of magnitude of improvement in the low error rate region as compared to an elementary array-based code.

This paper presents a method for evaluating pseudocodeword weight enumerators of nonbinary LDPC codes built out of protographs. The ensemble enumerators are evaluated for both the finite-length and infinite-length regimes. Results of this type can be particularly useful for designing structured non-binary LDPC codes with good properties under message passing or linear programming decoding.

A Write-Once Memory (WOM)-code is a coding scheme that allows information to be written in a memory block multiple times, but in a way that the stored values are not decreased across writes. This work studies non-binary WOM-codes with applications to flash memory. We present two constructions of non-binary WOM-codes that leverage existing high sum-rate WOM-codes defined over smaller alphabets. In many instances, these constructions provide the highest known sum-rates of the non-binary WOM-codes. In addition, we introduce a new class of codes, called level distance WOM-codes, which mitigate the difficulty of programming a flash memory cell by eliminating all small-magnitude level increases. We show how to construct such codes and state an upper bound on their sum-rate.

The impact of process variation in deep-submicron technologies is especially pronounced for SRAM architectures which must meet demands for higher density and higher performance at increased levels of integration. Due to the complex structure of SRAM, estimating the effect of process variation accurately has become very challenging. In this paper, we address this challenge in the context of estimating SRAM timing variation. Specifically, we introduce a method called loop flattening that demonstrates how the evaluation of the timing statistics in the complex, highly structured circuit can be reduced to that of a single chain of component circuits. To then very quickly evaluate the timing delay of a single chain, we employ a statistical method based on importance sampling augmented with targeted, high-dimensional, spherical sampling. Overall, our methodology provides an accurate estimation with 650X or greater speed-up over the nominal Monte Carlo approach.

The method for a design of a multiplierless CIC compensation filter is presented. The proposed filter compensates the CIC passband droop in the passband region defined by the passband frequency ωp=π/2M. Using a multirate identity this filter can be moved to a low rate thus becoming a second order filter. In the proposed filter design, the maximum value of the passband deviation is limited to be less than 0.4 dB.

In this paper we study the problem of finding maximally sized subsets of binary strings (codes) of equal length that are immune to a given number r of repetitions, in the sense that no two strings in the code can give rise to the same string after r repetitions. We propose explicit number theoretic constructions of such subsets. In the case of $r=1$ repetition, the proposed construction is asymptotically optimal. For $r\geq1$, the proposed construction is within a constant factor of the best known upper bound on the cardinality of a set of strings immune to r repetitions. Inspired by these constructions, we then develop a prefixing method for correcting any prescribed number r of repetition errors in an arbitrary binary linear block code. The proposed method constructs for each string in the given code a carefully chosen prefix such that the resulting strings are all of the same length and such that despite up to any r repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. In this construction, the prefix length is made to scale logarithmically with the length of strings in the original code. As a result, the guaranteed immunity to repetition errors is achieved while the added redundancy is asymptotically negligible.

The class of low-density parity-check (LDPC) codes is attractive, since such codes can be decoded using practical message-passing algorithms, and their performance is known to approach the Shannon limits for suitably large block lengths. For the intermediate block lengths relevant in applications, however, many LDPC codes exhibit a so-called “error floor,” corresponding to a significant flattening in the curve that relates signal-to-noise ratio (SNR) to the bit-error rate (BER) level. Previous work has linked this behavior to combinatorial substructures within the Tanner graph associated with an LDPC code, known as (fully) absorbing sets. These fully absorbing sets correspond to a particular type of near-codewords or trapping sets that are stable under bit-flipping operations, and exert the dominant effect on the low BER behavior of structured LDPC codes. This paper provides a detailed theoretical analysis of these (fully) absorbing sets for the class of$C_{p, \gamma}$array-based LDPC codes, including the characterization of all minimal (fully) absorbing sets for the array-based LDPC codes for$\gamma = 2,3,4$, and moreover, it provides the development of techniques to enumerate them exactly. Theoretical results of this type provide a foundation for predicting and extrapolating the error floor behavior of LDPC codes.

Motivated by the recent emergence of large online social networks, we seek to understand the effects the underlying social network (graph) structure and the information dynamics have on the creation of influence of an individual. We examine a natural model for information dynamics under two important temporal scales: a first impression setting and a long- term or equilibrated setting. We obtain a characterization of relevant network structures under these temporal aspects, thereby allowing us to formalize the existence of influential agents. Specifically, we find that the existence of an influential agent corresponds to: (a) strictly positive information theoretic capacity over an infinite-sized noisy broadcast tree network in the first impression case, and (b) positive recurrent property of an appropriate (countable state space) Markov chain in the long-term case. As an application of our results, we evaluate the parameter space of the popular ldquosmall worldrdquo network model to identify when the network structure supports the existence of influential agents.

The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding algorithms, is known to be close to Shannon limits for codes with suitably large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a deterministic method of predicting error floors, based on high signal-to-noise ratio (SNR) asymptotics, applied to absorbing sets within structured LDPC codes. The approach is illustrated using a class of array-based LDPC codes, taken as exemplars of high-performance structured LDPC codes. The results are in very good agreement with a stochastic method based on importance sampling which, in turn, matches the hardware-based experimental results. The importance sampling scheme uses a mean-shifted version of the original Gaussian density, appropriately centered between a codeword and a dominant absorbing set, to produce an unbiased estimator of the FER with substantial computational savings over a standard Monte Carlo estimator. Our deterministic estimates are guaranteed to be a lower bound to the error probability in the high SNR regime, and extend the prediction of the error probability to as low as 10-30. By adopting a channel-independent viewpoint, the usefulness of these results is demonstrated for both the standard Gaussian channel and a channel with mixture noise.

Many classes of high-performance low-density parity-check (LDPC) codes are based on parity check matrices composed of permutation submatrices. We describe the design of a parallel-serial decoder architecture that can be used to map any LDPC code with such a structure to a hardware emulation platform. High-throughput emulation allows for the exploration of the low bit-error rate (BER) region and provides statistics of the error traces, which illuminate the causes of the error floors of the (2048, 1723) Reed-Solomon based LDPC (RS-LDPC) code and the (2209, 1978) array-based LDPC code. Two classes of error events are observed: oscillatory behavior and convergence to a class of non-codewords, termed absorbing sets. The influence of absorbing sets can be exacerbated by message quantization and decoder implementation. In particular, quantization and the log-tanh function approximation in sum-product decoders

A class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity-check (LDPC) decoders at low error rates. Past experiments have shown that a class of (8,8) absorbing sets determines the error floor performance of the (2048,1723) Reed-Solomon based LDPC code (RS-LDPC). A postprocessing approach is formulated to exploit the structure of the absorbing set by biasing the reliabilities of selected messages in a message-passing decoder. The approach converges quickly and can be efficiently implemented with minimal overhead. Hardware emulation of the decoder with postprocessing shows more than two orders of magnitude improvement in the very low bit error rate performance and error- floor-free operation below a BER of 10-12.

With process variation becoming a growing concern in deep submicron technologies, the ability to efficiently obtain an accurate estimate of failure probability of SRAM components is becoming a central issue. In this paper we present a general methodology for a fast and accurate evaluation of the failure probability of memory designs. The proposed statistical method, which we call importance sampling through norm minimization principle, reduces the variance of the estimator to produce quick estimates. It builds upon the importance sampling, while using a novel norm minimization principle inspired by the classical theory of Large Deviations. Our method can be applied for a wide class of problems, and our illustrative examples are the data retention voltage and the read/write failure tradeoff for 6T SRAM in 32 nm technology. The method yields computational savings on the order of 10000x over the standard Monte Carlo approach in the context of failure probability estimation for SRAM considered in this paper.

We develop a prefixing method for correcting any prescribed number r of repetition errors in an arbitrary binary block code. The proposed method constructs a prefix for each codeword such that the resulting strings are all of the same length and despite any r repetitions in the concatenation of the prefix and the codeword, the original codeword can be recovered. Further, the prefix length scales logarithmically with the blocklength of the original code, so the added redundancy is asymptotically negligible.

Abstract — The error-correcting performance of low-density parity check (LDPC) codes, when decoded using practical iterative decoding, is known to approach Shannon limits in the asymptotic limit of large blocklengths. A substantial limitation to the use of finite-length LDPC codes is the presence of an error floor in the low frame error rate (FER) region. This paper develops a method, based on importance sampling and high SNR asymptotics as applied to suitably defined absorbing structures within the LDPC code, to predict error floors. Our results are in very close agreement with hardware-based experimental results, and moreover extend the prediction of the error probability to even lower regions. We compute both importance sampling estimates of error probabilities and deterministic estimates that are guaranteed to lower bound the error probability in the high SNR regime. I.

Low density parity check codes (LDPC) are known to perform very well under iterative decoding. However, these codes also exhibit a change in the slope of the bit error rate (BER) vs. signal to noise ratio (SNR) curve in the very low BER region. In our earlier work using hardware emulation in this deep BER regime we argue that this behavior can be attributed to specific structures within the Tanner graph associated with an LDPC code, called absorbing sets. In this paper we provide a detailed theoretical analysis of absorbing sets for array-based LDPC codes Cp.gamma. Specifically, we identify and enumerate all the smallest absorbing sets for these array-based LDPC codes with gamma = 2,3,4 with standard parity check matrix. Experiments carried out on the emulation platform show excellent agreement with our theoretical results.

A. class of combinatorial structures, called absorbing sets, strongly influences the performance of low-density parity- check (LDPC) decoders. In particular, the quantization scheme strongly affects which absorbing sets dominate in the error-floor region. Absorbing sets may be characterized as weak or strong. They are a characteristic of the parity check matrix of a code. Conventional quantization schemes applied to a (2209,1978) array-based LDPC code can induce low-weight weak absorbing sets and, as a result, elevate the error floor. Adaptive quantization schemes alleviate the effects of weak absorbing sets, and, as a result, only the strong ones dominate the error floor of an optimized decoder implementation. Another benefit of an adaptive quantization scheme is that it performs well even in very few iterations.

In this paper we revisit previously proposed techniques for constructing some families of subsets of binary strings (codes) that are immune to multiple repetition errors. In particular, we discuss a technique to construct single repetition error correcting codes and use number theoretic methods to give an explicit formula for the cardinalities of these codes. This approach results in codes the ratio of whose cardinality to the best upper bounds approaches unity in the increasing codelength limit (asymptotic optimality). We also discuss a somewhat different technique to construct multiple repetition error correcting codes. Here the cardinalities are asymptotically within a fixed constant of the best known upper bounds. Our constructions are asymptotically better by a constant factor than the best previously known such constructions, due to Levenshtein.

We analyze the performance of a Reed–Muller RM$\,(1, m)$code over a channel that, in addition to substitution errors, permits either the repetition of a single bit or the deletion of a single bit; the latter feature is used to model synchronization errors. We first analyze the run-length structure of this code. We enumerate all pairs of codewords that can result in the same sequence after the deletion of a single bit, and propose a simple way to prune the code by dropping one information bit such that the resulting linear subcode has good post-deletion and post-repetition minimum distance. A bounded distance decoding algorithm is provided for the use of this pruned code over the channel. This algorithm has the same order of complexity as the usual fast Hadamard transform based decoder for the RM$\,(1, m)$code.

Several high performance LDPC codes have parity-check matrices composed of permutation submatrices. We design a parallel-serial architecture to map the decoder of any structured LDPC code in this large family to a hardware emulation platform. A peak throughput of 240 Mb/s is achieved in decoding the (2048,1723) Reed-Solomon based LDPC (RS-LDPC) code. Experiments in the low bit error rate (BER) region provide statistics of the error traces, which are used to investigate the causes of the error floor. In a low precision implementation, the error floors are dominated by the fixed-point decoding effects, whereas in a higher precision implementation the errors are attributed to special configurations within the code, whose effect is exacerbated in a fixed-point decoder. This new characterization leads to an improved decoding strategy and higher performance.

We describe a method for enhancing the synchronization error correction properties of an array-based low density parity check (LDPC) code. The proposed method uses code expurgation: a linear subcode is retained for message encoding and additional input bits are used for protection against synchronization errors. The method is easy to implement and incurs minimal loss in rate