Search

The process of DNA-based data storage (DNA storage for short) can be mathematically modelled as a communication channel, termed DNA storage channel, whose inputs and outputs are sets of unordered sequences. To design error correcting codes for DNA storage channel, a new metric, termed the sequence-subset distance, is introduced, which generalizes the Hamming distance to a distance function defined between any two sets of unordered vectors and helps to establish a uniform framework to design error correcting codes for DNA storage channel. We further introduce a family of error correcting codes, referred to as sequence-subset codes, for DNA storage and show that the error-correcting ability of such codes is completely determined by their minimum distance. We derive some upper bounds on the size of the sequence-subset codes including a tight bound for a special case, a Singleton-like bound and a Plotkin-like bound. We also propose some constructions, including an optimal construction for that special case, which imply lower bounds on the size of such codes. [ABSTRACT FROM AUTHOR]

Limited magnitude asymmetric error model is well suited for flash memory. In this paper, we consider the construction of asymmetric codes correcting single error over $\mathbb {Z}_{2^{k}r}$ which is based on so called $B_{1}[{4}](2^{k}r)$ set. In fact, we reduce the construction of a maximal size $B_{1}[{4}](2^{k}r)$ set for $k\geq 3$ to the construction of a maximal size $B_{1}[{4}](2^{k-3}r)$ set. Finally, we give an explicit formula of a maximal size $B_{1}[{4}](4r)$ set and some lower bounds of a maximal size $B_{1}[{4}](2r)$ set. By computer searching up to $q\leq 106$ , we conjecture that those lower bounds are tight. [ABSTRACT FROM AUTHOR]

To equip DNA-based data storage with random-access capabilities, Yazdi et al. (2018) prepended DNA strands with specially chosen address sequences called primers and provided certain design criteria for these primers. We provide explicit constructions of error-correcting codes that are suitable as primer addresses and equip these constructions with efficient encoding algorithms. Specifically, our constructions take cyclic or linear codes as inputs and produce sets of primers with similar error-correcting capabilities. Using certain classes of BCH codes, we obtain infinite families of primer sets of length $n$ , minimum distance $d$ with $(d+1) \log _{4}\,\,n +O(1)$ redundant symbols. Our techniques involve reversible cyclic codes (1964), an encoding method of Tavares et al. (1971) and Knuth’s balancing technique (1986). In our investigation, we also construct efficient and explicit binary balanced error-correcting codes and codes for DNA computing. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

We consider binary error correcting codes when errors are deletions. A basic challenge concerning deletion codes is determining ${p}_{0}^{(adv)}$ , the zero-rate threshold of adversarial deletions, defined to be the supremum of all $p$ for which there exists a code family with rate bounded away from 0 capable of correcting a fraction $p$ of adversarial deletions. A recent construction of deletion-correcting codes shows that ${p}_{0}^{(adv)} \ge \sqrt {2}-1$ , and the trivial upper bound, ${p}_{0}^{(adv)}\le {1}/{2}$ , is the best known. Perhaps surprisingly, we do not know whether or not ${p}_{0}^{(adv)} = 1/2$. In this work, to gain further insight into deletion codes, we explore two related error models: oblivious deletions and online deletions, which are in between random and adversarial deletions in power. In the oblivious model, the channel can inflict an arbitrary pattern of ${pn}$ deletions, picked without knowledge of the codeword. We prove the existence of binary codes of positive rate that can correct any fraction ${p} < 1$ of oblivious deletions, establishing that the associated zero-rate threshold ${p}_{0}^{(obliv)}$ equals 1. For online deletions, where the channel decides whether to delete bit ${x}_{{i}}$ based only on knowledge of bits ${x}_{1}{x}_{2} {\dots }{x}_{{i}}$ , define the deterministic zero-rate threshold for online deletions ${p}_{0}^{(on,{d})}$ to be the supremum of $p$ for which there exist deterministic codes against an online channel causing ${pn}$ deletions with low average probability of error. That is, the probability that a randomly chosen codeword is decoded incorrectly is small. We prove ${p}_{0}^{(adv)}={1}/{2}$ if and only if ${p}_{0}^{(on,{d})}={1}/{2}$. [ABSTRACT FROM AUTHOR]

We consider the decoding of linear and array codes from errors when we are only allowed to download a part of the codeword. More specifically, suppose that we have encoded $k$ data symbols using an $(n,k)$ code with code length $n$ and dimension $k$. During storage, some of the codeword coordinates might be corrupted by errors. We aim to recover the original data by reading the corrupted codeword with a limit on the transmission bandwidth, namely, we can only download an $\alpha $ proportion of the corrupted codeword. For a given $\alpha $ , our objective is to design a code and a decoding scheme such that we can recover the original data from the largest possible number of errors. A naive scheme is to read $\alpha n$ coordinates of the codeword. This method used in conjunction with MDS codes guarantees recovery from any $\lfloor (\alpha n-k)/2\rfloor $ errors. In this paper we show that we can instead download an $\alpha $ proportion from each of the codeword’s coordinates. For a well-designed MDS code, this method can guarantee recovery from $\lfloor (n-k/\alpha)/2 \rfloor $ errors, which is $1/\alpha $ times more than the naive method, and is also the maximum number of errors that an $(n,k)$ code can correct by downloading only an $\alpha $ proportion of the codeword. We present two families of such optimal constructions and decoding schemes of which one is based on Interleaved Reed-Solomon codes and the other on Folded Reed-Solomon codes. We further show that both code constructions attain asymptotically optimal list decoding radius when downloading only a part of the corrupted codeword. We also construct an ensemble of random codes that with high probability approaches the upper bound on the number of correctable errors when the decoder downloads an $\alpha $ proportion of the corrupted codeword. [ABSTRACT FROM AUTHOR]

Performing active quantum error correction to protect fragile quantum states highly depends on the correctness of measured error syndromes. To obtain reliable error syndromes using imperfect physical circuits, we propose syndrome measurement (SM) and quantum data-syndrome (DS) codes. SM codes protect syndrome with linearly dependent redundant stabilizer measurements. DS codes generalize this idea for simultaneous correction of both data qubits and syndrome bits errors. We study fundamental properties of quantum DS codes, including split weight enumerators, generalized MacWilliams identities, and linear programming bounds. In particular, we derive Singleton and Hamming-type upper bounds on the minimum distance of degenerate quantum DS codes. Then we study random DS codes and show that random DS codes with a relatively small additional syndrome measurements achieve the Gilbert-Varshamov bound of stabilizer codes. Finally, we propose a family of CSS-type quantum DS codes based on classical cyclic codes, which include the Steane code and the quantum Golay code. [ABSTRACT FROM AUTHOR]

With technology scaling, burst errors or clustered errors are becoming increasingly common in different types of memories. Multiple bit upsets due to particle strikes, write disturbance errors, and magnetic field coupling are a few of the mechanisms which cause clustered errors. In this article, a new class of single burst error correcting codes are presented which correct a single burst of any size b within a codeword. A code construction methodology is presented which enables us to construct the proposed scheme from existing codes, e.g., Hamming codes. A new single step decoding methodology for the proposed class of codes is also presented which enables faster decoding. Different code constructions using Hamming codes, and BCH codes have been presented in this paper and a comparison is made with existing schemes in terms of decoding complexity and data redundancy. The proposed scheme in all cases reduces the decoder complexity for little to no increase in data redundancy, specifically for higher burst error sizes. [ABSTRACT FROM AUTHOR]

We present a new class of linear error-correcting codes taking numerical data into codewords with numerical symbols. These codes can correct large random numerical errors added to codewords. The goal is for numerical data to be protected directly as numbers whether in storage or transmission. The coding structures are based on discrete Fourier transform (DFT) codes, defined by parity-check matrices where rows are consecutively indexed DFT vectors. The new tensor codes use the Kronecker product of two parity-check DFT matrices of shorter length codes. We construct all necessary processing matrices. Error correction methods involve two levels of syndromes and use several stochastic Berlekamp-Massey Algorithms (sBMA) to find big syndromes, locate and evaluate large errors. Decoding is done in two stages with stage one producing corrected syndromes. Stage two determines errors within a well-defined segment for the codewords. Tensor codes have simpler and more efficient decoding operations. The characteristics of the tensor codes are compared to standard DFT codes of equal length. The processing operations are significantly less for the tensor codes but the standard DFT codes sometimes have better correcting performance. Nevertheless, tensor product codes can have acceptable levels of correction, more efficiently. [ABSTRACT FROM AUTHOR]

We construct error-correcting write-once memory (WOM) codes that guarantee correction of any specified number of errors in $q$ -level memories. The constructions use suitably designed short $q$ -ary WOM codes and concatenate them with outer error-correcting codes over different alphabets using suitably designed mappings. With a new storage-efficiency measure, we call EC-rate and show that for common error types the codes save redundancy and implementation complexity over straightforward concatenation. In addition to constructions for guaranteed error correction, we extend the error-correcting WOM scheme to binary multi-level coding for random errors, and toward soft-decision decoding provide an efficient way to extract reliability information without using higher-precision readout. [ABSTRACT FROM AUTHOR]

In the conventional index coding problem, the messages transmitted by the source to satisfy the demands of the receivers are error-free. However, in practice, the messages may be error prone which led to the introduction of error-correcting index codes. An error-correcting index code is an encoding scheme which enables every receiver to decode its demanded message even in the presence of certain number of transmission errors. Formally, an index code capable of correcting at most $\delta $ errors at all its receivers is defined as a $\delta $ -error-correcting index code. In this paper, we explore the connections between vector linear error-correcting index codes and discrete polymatroids. This is motivated from the connections between linear network error-correcting codes and matroids. It is shown that a vector linear error-correcting index code exists if and only if there exists a representable discrete polymatroid satisfying certain conditions. Differential error-correcting index codes which allow different receivers to have different error-correcting capabilities are also studied. Note that the $\delta $ -error-correcting code is a special case of a differential error-correcting index code. Error correction at a subset of receivers is another special case which is discussed. [ABSTRACT FROM AUTHOR]

Hamming code is a linear error-correcting code widely used in memory and telecommunication. For the first time, here we put forth an approach to analyzing Hamming codes in hardware using networks consisting of memristors. Such networks are capable of detecting and correcting potential bit errors in Hamming codes in a high-speed and energy-efficient way, where the parity-check matrix is stored in the memristor crossbar array and the syndrome vector is represented by the states of the output unipolar memristors whose resistance flipping naturally implements vector-matrix multiplication with modulo 2. Our experimental results demonstrate that the output syndrome vector is able to correctly represent the position of the bit error whenever it exists, and subsequent correction can thus be applied by flipping the bit identified. The energy consumption using the present network has decreased by >100 times compared with GPU while >1000 times compared with CPU. [ABSTRACT FROM AUTHOR]

In recent years, flash memory has been widely used in embedded systems, portable devices, and high-performance storage products due to its nonvolatility, shock resistance, low power consumption, and high performance natures. To reduce the product cost, multi-level-cell (MLC) flash memory has been proposed; compared with the traditional single-level-cell (SLC) flash memory that only stores one bit of data per cell, each MLC cell can store two or more bits of data. Thus MLC can achieve a larger capacity and reduce the cost per unit. However, MLC also suffers from the degradation in both performance and reliability. In this paper, we try to enhance the reliability and reduce the product cost of flash-memory-based solid-state drive (SSD) from a totally different perspective. We propose the half-level-cell (HLC) scheme to manage and reuse the worn-out space in SSD; through our management scheme, the system can treat two bad pages as a normal page without sacrificing performance and reliability. The proposed scheme is purely on software/firmware-level, thus there is no need to change the hardware. The experiment results show that the lifetime of SSD with our proposed HLC scheme can be extended to 50.56% under the Windows workload and up to 65.45% under the multimedia workload. When we apply the HLC scheme to flash-memory cache of hybrid storage systems, the response time can be improved up to 20.57%. [ABSTRACT FROM AUTHOR]

Cache vulnerability due to soft errors is one of the reliability concerns in embedded systems. Dynamic reconfiguration techniques are widely studied for improving cache energy without considering the implications of cache vulnerability. Maintaining a useful data longer in the cache can be beneficial for energy improvement due to reduction in miss rates, however, longer data retention negatively impacts the vulnerability due to soft errors. This paper studies the tradeoff between energy efficiency improvement and reduction in cache vulnerability during cache reconfiguration. We propose a heuristic approach for both intertask and intratask cache reconfiguration in multitasking systems. Experimental results demonstrate that our proposed approach can significantly improve both vulnerability (25% on average) and energy efficiency (21% on average) for data cache without violating real-time constraints. [ABSTRACT FROM AUTHOR]

Motivated by communication channels in which the transmitted sequences are subjected to random permutations, as well as by certain DNA storage systems, we study the error control problem in settings where the information is stored/transmitted in the form of multisets of symbols from a given finite alphabet. A general channel model is assumed in which the transmitted multisets are potentially impaired by insertions, deletions, substitutions, and erasures of symbols. Several constructions of error-correcting codes for this channel are described, and bounds on the size of optimal codes correcting any given number of errors are derived. The construction based on the notion of Sidon sets in finite Abelian groups is shown to be optimal, in the sense of the asymptotic scaling of code redundancy, for any error radius and alphabet size. It is also shown to be optimal in the stronger sense of maximal code cardinality in various cases. [ABSTRACT FROM AUTHOR]

In this paper, new index coding problems are studied, where each receiver has erroneous side information. Although side information is a crucial part of index coding, the existence of erroneous side information has not been considered yet. We study an index code with receivers that have erroneous side information symbols in the error-free broadcast channel, which is called an index code with side information errors (ICSIE). The encoding and decoding procedures of the ICSIE are proposed, based on the syndrome decoding. Then, we derive the bounds on the optimal codelength of the proposed index code with erroneous side information. Furthermore, we introduce a special graph for the proposed index coding problem, called a \delta s -cycle whose properties are similar to those of the cycle in the conventional index coding problem. Properties of the ICSIE are also discussed in the \delta s -cycle and clique. Finally, the proposed ICSIE is generalized to an index code for the scenario having both additive channel errors and side information errors, called a generalized error correcting index code. [ABSTRACT FROM AUTHOR]

We construct error-correcting codes over permutations under the infinity-metric, which are also Gray codes in the context of rank modulation, i.e., are generated as simple circuits in the rotator graph. These errors model limited-magnitude or spike errors, for which only single-error-detecting Gray codes are currently known. Surprisingly, the error-correcting codes we construct achieve a better asymptotic rate than that of presently known constructions not having the Gray property, and exceed the Gilbert-Varshamov bound. Additionally, we present efficient ranking and unranking procedures, as well as a decoding procedure that runs in linear time. Finally, we also apply our methods to solve an outstanding issue with error-detecting rank-modulation Gray codes (also known in this context as snake-in-the-box codes) under a different metric, the Kendall $\tau $ -metric, in the group of permutations over an even number of elements S_{2n} , where we provide asymptotically optimal codes. [ABSTRACT FROM AUTHOR]

We consider the problem of computing a binary linear transformation when all circuit components are unreliable. Two models of unreliable components are considered: probabilistic errors and permanent errors. We introduce the “ENCODED” technique that ensures that the error probability of the computation of the linear transformation is kept bounded below a small constant independent of the size of the linear transformation even when all logic gates in the computation are noisy. By deriving a lower bound, we show that in some cases, the computational complexity of the ENCODED technique achieves the optimal scaling in error probability. Further, we examine the gain in energy-efficiency from the use of a “voltage-scaling” scheme, where gate-energy is reduced by lowering the supply voltage. We use a gate energy-reliability model to show that tuning gate-energy appropriately at different stages of the computation (“dynamic” voltage scaling), in conjunction with ENCODED, can lead to orders of magnitude energy-savings over the classical “uncoded” approach. Finally, we also examine the problem of computing a linear transformation when noiseless decoders can be used, providing upper and lower bounds to the problem. [ABSTRACT FROM AUTHOR]

We describe a general method for turning quantum circuits into sparse quantum subsystem codes. The idea is to turn each circuit element into a set of low-weight gauge generators that enforce the input–output relations of that circuit element. Using this prescription, we can map an arbitrary stabilizer code into a new subsystem code with the same distance and number of encoded qubits but where all the generators have constant weight, at the cost of adding some ancilla qubits. With an additional overhead of ancilla qubits, the new code can also be made spatially local. Applying our construction to certain concatenated stabilizer codes yields families of subsystem codes with constant-weight generators and with minimum distance d = n^1- \epsilon , where \epsilon = O(1/\sqrt \log n) . For spatially local codes in D dimensions, we nearly saturate a bound due to Bravyi and Terhal and achieve d = n^{1- \epsilon -1/D} . Previously the best code distance achievable with constant-weight generators in any dimension, due to Freedman, Meyer, and Luo, was O(\sqrt {n\log n})$ for a stabilizer code. [ABSTRACT FROM PUBLISHER]

We give an infinite family of maximum rank distance (MRD) codes, which covers properly the largest known linear MRD code family. Our family contains infinite families of non-linear MRD codes, which are the first non-linear examples for most of the parameters. We also give explicit examples and a table that demonstrates the proportion of linear and non-linear families for some small parameters. [ABSTRACT FROM PUBLISHER]

In this paper, list decoding of crisscross errors in arrays over finite fields is considered. For this purpose, the so-called cover metric is used, where the cover of a matrix is a set of rows and columns which contains all non-zero elements of the matrix. A Johnson-like upper bound on the maximum list size in the cover metric is derived, showing that the list of codewords has polynomial size up to a certain radius. Furthermore, a simple list decoding algorithm for a known optimal code construction is presented, which decodes errors in the cover metric up to our upper bound. These results reveal significant differences between the cover metric and the rank metric and show that the cover metric is more suitable for correcting crisscross errors. [ABSTRACT FROM PUBLISHER]

We consider codes over fixed alphabets against worst case symbol deletions. For any fixed k \ge 2 , we construct a family of codes over alphabet of size k with positive rate, which allow efficient recovery from a worst case deletion fraction approaching 1-(2/(k+\sqrt k)) . In particular, for binary codes, we are able to recover a fraction of deletions approaching 1/(\sqrt 2 +1)=\sqrt 2-1 \approx 0.414 . Previously, even non-constructively, the largest deletion fraction known to be correctable with positive rate was 1-\Theta (1/\sqrt k) , and around 0.17 for the binary case. Our result pins down the largest fraction of correctable deletions for $k$ -ary codes as 1-\Theta (1/k)$ , since 1-1/k$ is an upper bound even for the simpler model of erasures where the locations of the missing symbols are known. Closing the gap between and 1/2 for the limit of worst case deletions correctable by binary codes remains a tantalizing open question. [ABSTRACT FROM PUBLISHER]

We study error correction codes for multimedia streaming applications where a stream of source packets must be transmitted in real-time, with in-order decoding, and strict delay constraints. In our setup, the encoder observes a stream of source packets in a sequential fashion, and $M$ channel packets must be transmitted between the arrival of successive source packets. Each channel packet can depend on all the source packets observed up to and including that time, but not on any future source packets. The decoder must reconstruct the source stream with a delay of $T$ packets. We consider a class of packet erasure channels with burst and isolated erasures, where the erasure patterns are locally constrained. Our proposed model provides a tractable approximation to statistical models, such as the Gilbert–Elliott channel, for capacity analysis. When $M=1$ , i.e., when the source-packet arrival and channel-packet transmission rates are equal, we establish upper and lower bounds on the capacity, that are within one unit of the decoding delay $T$ . We also establish necessary and sufficient conditions on the column distance and column span of a convolutional code to be feasible, and in turn establish a fundamental tradeoff between these. Our proposed codes—maximum distance and span codes—achieve a near-optimal tradeoff between the column distance and column span, and involve a layered construction. When $M>1$ , we establish the capacity for the burst-erasure channel and an achievable rate in the general case. Extensive numerical simulations over Gilbert–Elliott and Fritchman channel models suggest that our codes also achieve significant gains in the residual loss probability over statistical channel models. [ABSTRACT FROM PUBLISHER]

Error-correcting output coding (ECOC) is one of the most widely used strategies for dealing with multi-class problems by decomposing the original multi-class problem into a series of binary sub-problems. In traditional ECOC-based methods, binary classifiers corresponding to those sub-problems are usually trained separately without considering the relationships among these classifiers. However, as these classifiers are established on the same training data, there may be some inherent relationships among them. Exploiting such relationships can potentially improve the generalization performances of individual classifiers, and, thus, boost ECOC learning algorithms. In this paper, we explore to mine and utilize such relationship through a joint classifier learning method, by integrating the training of binary classifiers and the learning of the relationship among them into a unified objective function. We also develop an efficient alternating optimization algorithm to solve the objective function. To evaluate the proposed method, we perform a series of experiments on eleven datasets from the UCI machine learning repository as well as two datasets from real-world image recognition tasks. The experimental results demonstrate the efficacy of the proposed method, compared with state-of-the-art methods for ECOC-based multi-class classification. [ABSTRACT FROM PUBLISHER]

We propose binary discrete parametric channel models for multi-level cell (MLC) flash memories that provide accurate error-correcting code (ECC) performance estimation by modeling the empirically observed error characteristics under program/erase cycling stress. Through a detailed empirical error characterization of 1X-nm and 2Y-nm MLC flash memory chips from two different vendors, we observe and characterize the overdispersion phenomenon in the number of bit errors per ECC frame. A well-studied channel model, such as the binary asymmetric channel model, is unable to provide accurate ECC performance estimation. Hence, we propose a channel model based on the beta-binomial probability distribution [2-beta-binomial (2-BBM) channel model], which is a good fit for the overdispersed empirical error characteristics, and show through statistical tests and simulation results for BCH, low density parity check, and polar codes, that the 2-BBM channel model provides accurate ECC performance estimation in MLC flash memories. [ABSTRACT FROM AUTHOR]

Error correction code (ECC) and built-in self-repair (BISR) techniques by using redundancies have been widely used for improving the yield and reliability of embedded memories. The target faults of these two schemes are soft errors and permanent (hard) faults, respectively. In recent works, there are also some techniques integrating ECC and BISR to deal with soft errors and hard defects simultaneously. However, this will compromise reliability, since some of the ECC protection capability is used for repairing single hard faults. To cure this dilemma, we propose an ECC-enhanced BISR (EBISR) technique, which uses ECC to repair single permanent faults first and spares for the remaining faults in the production/power-ON test and repair stage. However, techniques are proposed to maintain the original reliability during the online test and repair stage. We also propose the corresponding hardware architecture for the EBISR scheme. A simulator is implemented to evaluate the hardware overhead (HO), repair rate, reliability, and performance penalty. Experimental results show that the proposed EBISR scheme can improve yield and reliability significantly with negligible HO and performance penalty. [ABSTRACT FROM PUBLISHER]

The code design of non-binary low-density parity-check codes for the erasure channel, under maximum a posteriori decoding, is addressed. In particular, a partially structured ensemble of codes, characterized by a careful control of the amount and of the connectivity of the variable nodes of small degrees, is proposed. The identified ensemble of codes is analyzed in terms of asymptotic thresholds and weight distribution and it is shown that codes from the ensemble provide a remarkable trade-off between waterfall performance, error floor, and decoding complexity. As an example, the performance curve of a short (256,128) code on the memoryless 16-ary erasure channel tightly approaches the Singleton bound at least down to a codeword error rate of 10^-9, at low decoding complexity. [ABSTRACT FROM AUTHOR]

Polar codes, as the first provable capacity-achieving error-correcting codes, have received much attention in recent years. However, the decoding performance of polar codes with traditional successive-cancellation (SC) algorithm cannot match that of the low-density parity-check or Turbo codes. Because SC list (SCL) decoding algorithm can significantly improve the error-correcting performance of polar codes, design of SCL decoders is important for polar codes to be deployed in practical applications. However, because the prior latency reduction approaches for SC decoders are not applicable for SCL decoders, these list decoders suffer from the long-latency bottleneck. In this paper, we propose a multibit-decision approach that can significantly reduce latency of SCL decoders. First, we present a reformulated SCL algorithm that can perform intermediate decoding of 2 b together. The proposed approach, referred as 2-bit reformulated SCL (2b-rSCL) algorithm, can reduce the latency of SCL decoder from ( 3n-2 ) to ( 2n-2 ) clock cycles without any performance loss. Then, we extend the idea of 2-b-decision to general case, and propose a general decoding scheme that can perform intermediate decoding of any 2^K bits simultaneously. This general approach, referred as \textit 2^K -bit reformulated SCL ( 2^K b-rSCL) algorithm, can reduce the overall decoding latency to as short as n/2^K-2-2 cycles. Furthermore, on the basis of the proposed algorithms, very large-scale integration architectures for 2b-rSCL and 4b-rSCL decoders are synthesized. Compared with a prior SCL decoder, the proposed (1024, 512) 2b-rSCL and 4b-rSCL decoders can achieve 21% and 60% reduction in latency, 1.66 and 2.77 times increase in coded throughput with list size 2, and 2.11 and 3.23 times increase in coded throughput with list size 4, respectively. [ABSTRACT FROM PUBLISHER]

This brief lays out cyclic redundancy check-based encoding scheme and presents an efficient implementation of the encoding algorithm in field programmable gate array (FPGA) prototype for both the binary Golay code ( G\mathrm {\mathbf {23}} ) and extended binary Golay code ( G\mathrm {\mathbf {24}} ). High speed with low-latency architecture has been designed and implemented in Virtex-4 FPGA for Golay encoder without incorporating linear feedback shift register. This brief also presents an optimized and low-complexity decoding architecture for extended binary Golay code (24, 12, 8) based on an incomplete maximum likelihood decoding scheme. The proposed architecture for decoder occupies less area and has lower latency than some of the recent work published in this area. The encoder module runs at 238.575 MHz, while the proposed architecture for decoder has an operating clock frequency of 195.028 MHz. The proposed hardware modules may be a good candidate for forward error correction in communication link, which demands a high-speed system. [ABSTRACT FROM AUTHOR]

Improved lower and upper bounds on the size and the rate of grain-correcting codes are presented. The lower bound is Gilbert–Varshamov-like combined with a construction by Gabrys et al., and it improves on the previously best known lower bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval [0,0.0668] . One of the two newly presented upper bounds improves on the best known upper bounds on the asymptotic rate of \lceil \tau n \rceil -grain-correcting codes of length n on the interval \tau \in (0,{1}/{8}] and meets the lower bound of {1}/{2} for \tau \geq 1/8 . Moreover, in a nonasymptotic regime, both upper bounds improve on the previously best known results on the largest size of t -grain-correcting codes of length $n$ , for certain values of n$ and t$ . Constructions of 1-grain-correcting codes based on a partitioning technique are presented for lengths up to 18. Finally, a lower bound of on the minimum redundancy of $\infty $ -grain-detecting codes of length $n$ is presented. [ABSTRACT FROM PUBLISHER]

Random network coding recently attracts attention as a technique to disseminate information in a network. This paper considers a noncoherent multishot network, where the unknown and time-variant network is used several times. In order to create dependence between the different shots, particular convolutional codes in rank metric are used. These codes are so-called (partial) unit memory ((P)UM) codes, i.e., convolutional codes with memory one. First, distance measures for convolutional codes in rank metric are shown and two constructions of (P)UM codes in rank metric based on the generator matrices of maximum rank distance codes are presented. Second, an efficient error-erasure decoding algorithm for these codes is presented. Its guaranteed decoding radius is derived and its complexity is bounded. Finally, it is shown how to apply these codes for error correction in random linear and affine network coding. [ABSTRACT FROM AUTHOR]

We present new constructions of codes for asymmetric channels for both binary and nonbinary alphabets, based on methods of generalized code concatenation. For the binary asymmetric channel, our methods construct nonlinear single-error-correcting codes from ternary outer codes. We show that some of the Varshamov–Tenengol’ts–Constantin–Rao codes, a class of binary nonlinear codes for this channel, have a nice structure when viewed as ternary codes. In many cases, our ternary construction yields even better codes. For the nonbinary asymmetric channel, our methods construct linear codes for many lengths and distances which are superior to the linear codes of the same length capable of correcting the same number of symmetric errors. [ABSTRACT FROM AUTHOR]

Quantum synchronizable error-correcting codes are special quantum error-correcting codes that are designed to correct both the effect of quantum noise on qubits and misalignment in block synchronization. It is known that, in principle, such a code can be constructed through a combination of a classical linear code and its subcode if the two are both cyclic and dual-containing. However, finding such classical codes that lead to promising quantum synchronizable error-correcting codes is not a trivial task. In fact, although there are two families of classical codes that are proved to produce quantum synchronizable codes with good minimum distances and highest possible tolerance against misalignment, their code lengths have been restricted to primes and Mersenne numbers. In this paper, examining the incidence vectors of projective spaces over the finite fields of characteristic 2, we give quantum synchronizable codes from cyclic codes whose lengths are not primes or Mersenne numbers. These projective geometric codes achieve good performance in quantum error correction and possess the best possible ability to recover synchronization, thereby enriching the variety of good quantum synchronizable codes. We also extend the current knowledge of cyclic codes in classical coding theory by explicitly giving generator polynomials of the finite geometric codes and completely characterizing the minimum weight nonzero codewords. In addition to the codes based on projective spaces, we carry out a similar analysis on the well-known cyclic codes from Euclidean spaces that are known to be majority logic decodable and determine their exact minimum distances. [ABSTRACT FROM PUBLISHER]

A new architecture for matching the data protected with an error-correcting code (ECC) is presented in this brief to reduce latency and complexity. Based on the fact that the codeword of an ECC is usually represented in a systematic form consisting of the raw data and the parity information generated by encoding, the proposed architecture parallelizes the comparison of the data and that of the parity information. To further reduce the latency and complexity, in addition, a new butterfly-formed weight accumulator (BWA) is proposed for the efficient computation of the Hamming distance. Grounded on the BWA, the proposed architecture examines whether the incoming data matches the stored data if a certain number of erroneous bits are corrected. For a (40, 33) code, the proposed architecture reduces the latency and the hardware complexity by \sim32\% and 9%, respectively, compared with the most recent implementation. [ABSTRACT FROM AUTHOR]

Error correction codes (ECCs) are commonly used to protect memories from errors. As multibit errors become more frequent, single error correction codes are not enough and more advanced ECCs are needed. The use of advanced ECCs in memories is, however, limited by their decoding complexity. In this context, one-step majority logic decodable (OS-MLD) codes are an interesting option as the decoding is simple and can be implemented with low delay. Orthogonal Latin squares (OLS) codes are OS-MLD and have been recently considered to protect caches and memories. The main advantage of OLS codes is that they provide a wide range of choices for the block size and the error correction capabilities. In this brief, a method to extend OLS codes is presented. The proposed method enables the extension of the data block size that can be protected with a given number of parity bits thus reducing the overhead. The extended codes are also OS-MLD and have a similar decoding complexity to that of the original OLS codes. The proposed codes have been implemented to evaluate the circuit area and delay needed for different block sizes. [ABSTRACT FROM AUTHOR]

In this paper, a new class of (N,K) near-optimal partial Hadamard codebooks is proposed. The construction of the proposed codebooks from Hadamard matrices is based on binary row selection sequences, which are generated by quadratic residue mapping of p -ary m -sequences. The proposed codebooks have parameters and K=({p-1}/{2p})(N+\sqrt{N})+1 for an odd prime p$ and an even positive integer $n$ . We prove that the maximum magnitude of inner products between the code vectors of the proposed codebooks asymptotically achieves the Welch bound equality for sufficiently large $p$ and derive their inner product distribution. [ABSTRACT FROM PUBLISHER]

Motivated by distributed storage applications, we investigate the degree to which capacity achieving codes can be efficiently updated when a single information symbol changes, and the degree to which such codes can be efficiently repaired when a single encoded symbol is lost. Specifically, we first develop conditions under which optimum error-correction and update-efficiency are possible. We establish that the number of encoded bits that should change in response to a change in a single information bit must scale logarithmically in the block-length of the code, if we are to achieve any nontrivial rate with vanishing probability of error over the binary erasure or binary symmetric channels. Moreover, we show that there exist capacity-achieving codes with this scaling. With respect to local repairability, we develop tight upper and lower bounds on the number of remaining encoded bits that are needed to recover a single lost encoded bit. In particular, we show that when the rate of an optimal code is ε below capacity, the maximum number of codeword symbols required to recover one lost symbol must scale as log1/ε. Several variations on—and extensions of—these results are also developed, including to the problem of rate-distortion coding. [ABSTRACT FROM PUBLISHER]

In this work, we consider high-rate error-control systems for storage devices using multi-level per cell (MLC) NAND flash memories. Aiming at achieving a strong error-correcting capability, we propose error-control systems using block-wise parallel/serial concatenations of short Bose-Chaudhuri-Hocquenghem (BCH) codes with two iterative decoding strategies, namely, iterative hard-decision decoding (IHDD) and iterative reliability based decoding (IRBD). It will be shown that a simple but very efficient IRBD is possible by taking advantage of a unique feature of the block-wise concatenation. For tractable performance analysis and design of IHDD and IRBD at very low error rates, we derive semi-analytic approaches. The proposed error-control systems are compared with various error-control systems with well-known coding schemes such as a product code, multiple BCH codes, a single long BCH code, and low-density parity-check codes in terms of page error rates, which confirms our claim: the proposed error-control systems achieve good tradeoffs between error-performance and complexity as compared to the traditional schemes and is also very favorable for implementation. [ABSTRACT FROM PUBLISHER]

Pulse position modulation (PPM) is a popular signal modulation technique which converts signals into M-ary data by means of the position of a pulse within a time interval. While PPM and its variations have great advantages in many contexts, this type of modulation is vulnerable to loss of synchronization, potentially causing a severe error floor or throughput penalty even when little or no noise is assumed. Another disadvantage is that this type of modulation typically offers no error correction mechanism on its own, making them sensitive to intersymbol interference and environmental noise. In this paper, we propose a coding theoretic variation of PPM that allows for significantly more efficient symbol and frame synchronization as well as strong error correction. The proposed scheme can be divided into a synchronization layer and a modulation layer. This makes our technique compatible with major existing techniques such as standard PPM, multipulse PPM, and expurgated PPM as well in that the scheme can be realized by adding a simple synchronization layer to one of these standard techniques. We also develop a generalization of expurgated PPM suited for the modulation layer of the proposed self-synchronizing modulation scheme. This generalized PPM can also be used as stand-alone error-correcting PPM with a larger number of available symbols. [ABSTRACT FROM AUTHOR]