Search

This paper studies the problem of constructing codes correcting deletions in arrays. Under this model, it is assumed that an $n \times n$ array can experience deletions of rows and columns. These deletion errors are referred to as $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletions if ${t_{\mathrm {r}}}$ rows and ${t_{\mathrm {c}}}$ columns are deleted, while a code correcting these deletion patterns is called a $({t_{\mathrm {r}}}, {t_{\mathrm {c}}})$ -criss-cross deletion correction code. The definitions for criss-cross insertions are similar. It is first shown that when $t_{r}=t_{c}$ the problems of correcting criss-cross deletions and criss-cross insertions are equivalent. The focus of this paper lies on the case of (1, 1)-criss-cross deletions. A non-asymptotic upper bound on the cardinality of (1, 1)-criss-cross deletion correction codes is shown which assures that the redundancy is at least $2n-3+2\log n$ bits. A code construction with an existential encoding and an explicit decoding algorithm is presented. The redundancy of the construction is at most $2n+4 \log n + 7 +2 \log e$. A construction with explicit encoder and decoder is presented. The explicit encoder adds an extra $5\log n + 5$ bits of redundancy to the construction. [ABSTRACT FROM AUTHOR]

This paper investigates the problem of correcting multiple criss-cross insertions and deletions in arrays. More precisely, we study the unique recovery of $n \times n$ arrays affected by ${t}$ -criss-cross deletions defined as any combination of ${t_{\mathrm {r}}}$ row and ${t_{\mathrm {c}}}$ column deletions such that ${t_{\mathrm {r}}}+ {t_{\mathrm {c}}}= {t}$ for a given $t$. We show an equivalence between correcting ${t}$ -criss-cross deletions and ${t}$ -criss-cross insertions and show that a code correcting ${t}$ -criss-cross insertions/deletions has redundancy at least ${t} n + {t}\log n - \log ({t}!)$. Then, we present an existential construction of a ${t}$ -criss-cross insertion/deletion correcting code with redundancy bounded from above by ${t} n + \mathcal {O}({t}^{2} \log ^{2} n)$. The main ingredients of the presented code construction are systematic binary ${t}$ -deletion correcting codes and Gabidulin codes. The first ingredient helps locating the indices of the inserted/deleted rows and columns, thus transforming the insertion/deletion-correction problem into a row/column erasure-correction problem which is then solved using the second ingredient. [ABSTRACT FROM AUTHOR]

In this paper we consider the problem of encoding data into repeat-free sequences in which sequences are imposed to contain any k-tuple at most once (for predefined k). First, the capacity of the repeat-free constraint are calculated. Then, an efficient algorithm, which uses two bits of redundancy, is presented to encode length-n sequences for k = 2 + 2 log (n). This algorithm is then improved to support any value of k of the form k = a log (n), for 1 < a, while its redundancy is o(n). We also calculate the capacity of repeat-free sequences when combined with local constraints which are given by a constrained system, and the capacity of multi-dimensional repeat-free codes. [ABSTRACT FROM AUTHOR]

We propose a list-decoding scheme for reconstruction codes in the context of uniform-tandem-duplication noise, which can be viewed as an application of the associative memory model to this setting. We find the uncertainty associated with m > 2 strings (where a previous paper considered m = 2) in asymptotic terms, where code-words are taken from an error-correcting code. Thus, we find the trade-off between the design minimum distance, the number of errors, the acceptable list size and the resulting uncertainty, which corresponds to the required number of distinct retrieved outputs for successful reconstruction. It is therefore seen that by accepting list-decoding one may decrease coding redundancy, or the required number of reads, or both. [ABSTRACT FROM AUTHOR]

Consider two remote nodes (encoder and decoder), each with a binary sequence. The encoder’s sequence X differs from the decoder’s sequence Y by a small number of edits (deletions and insertions). The goal is to construct a message M, to be sent via a one-way error free link, such that the decoder can reconstruct X using M and Y. In this paper, we devise a coding scheme for this one-way synchronization model. The scheme is based on multiple layers of Varshamov-Tenengolts (VT) codes combined with off-the-shelf linear error-correcting codes, and uses a list decoder. We bound the expected list size of the decoder under certain assumptions, and validate its performance via numerical simulations. We also consider an alternative decoder that uses only the constraints from the VT codes (i.e., does not require a linear code), and has a smaller redundancy at the expense of a slightly larger average list size. [ABSTRACT FROM AUTHOR]

Multiple cell upsets (MCU) is an issue that has to be dealt with when designing electronics for working in a radiated environment. Furthermore, the constant evolution of ICs integration density causes an increment in the MCUs span. These issues are typical in aviation applications, where, additionally, fault-tolerant (FT) performance is required. FT systems are typically based on a redundancy concept for storing and retrieving healthy information, for example, with a triple modular redundancy (TMR) scheme. The main issue with redundancy is design oversizing. On the other hand, reconfiguration-based techniques allow error scrubbing with a limited overhead. The main drawback here is overhead vulnerability to radiation, which is invalid for FT requirements. This paper proposes a new hybrid architecture that takes advantage of the optimized performance of reconfiguration-based techniques supported on extremely compressed redundant information nonvulnerable to radiation, referred to in this paper as hardwired seed bits (HSB). It also includes different known techniques, such as interleaving, error detection and correction (EDAC) algorithms, etc., for optimizing the final architecture as much as possible. As a result, the proposed approach meets FT requirements thanks to nonvulnerable tiny redundant information combined with an optimized performance through EDAC-based implementation. [ABSTRACT FROM AUTHOR]

In this paper, we study two families of codes with availability, namely, private information retrieval (PIR) codes and batch codes. While the former requires that every information symbol has $k$ mutually disjoint recovering sets, the latter imposes this property for each multiset request of $k$ information symbols. The main problem under this paradigm is to minimize the number of redundancy symbols. We denote this value by $r_{P}(n,k)$ and $r_{B}(n,k)$ , for PIR codes and batch codes, respectively, where $n$ is the number of information symbols. Previous results showed that for any constant $k$ , $r_{P}(n,k) = \Theta (\sqrt {n})$ and $r_{B}(n,k)= {\mathcal{ O}}(\sqrt {n}\log (n))$. In this paper, we study the asymptotic behavior of these codes for non-constant $k$ and specifically for $k=\Theta (n^\epsilon)$. We also study the largest value of $k$ such that the rate of the codes approaches 1 and show that for all $\epsilon < 1$ , $r_{P}(n,n^\epsilon) = o(n)$ and $r_{B}(n,n^\epsilon) = o(n)$. Furthermore, several more results are proved for the case of fixed $k$. [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]

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

The rank-modulation scheme has been recently proposed to write and store data in flash memories efficiently. In this paper, a new construction of systematic error-correcting codes for permutations is presented under the Chebyshev distance. By constructing a subgroup code and using its coset codes to partition the set of information permutations, the proposed code construction can achieve much larger code cardinality and hence higher code rates. To facilitate the encoding and decoding of the constructed codes, we also investigate the concepts of ranking and unranking for permutations, and generalize them to $M$ -ranking and $M$ -unranking for multi-permutations. Examples are provided to demonstrate the relevant concepts and the encoding/decoding algorithms. [ABSTRACT FROM AUTHOR]

Additional check bits, which are commonly attached to the message’s input data, are normally used to minimize the error during data transmission. The receiver system implements a checking algorithm to determine if an error was occurred in the received data. This algorithm will correct a corrupted bit and recover the original message. An enhanced error detection correction code was presented to better detect and correct the corrupted conveyed bits. It improves the existing limitations of utilizing cyclic redundancy checking (CRC), Hamming code, and other checksum techniques. Also, it reduced the length of the redundancy bits which exists in CRC, the overhead of interspersing of the redundancy bits in a typical Hamming code, and the system resources such as processor time and bandwidth in checksum techniques. This paper was synthesized and simulated using the Xilinx Spartan 6 (XC7Z020-2CLG4841) FPGA. Results show that the resource utilization of the designed memory architecture using EEDC is lower compared to CRC, Hamming, and Checksum algorithms. [ABSTRACT FROM AUTHOR]

Maximum distance separable (MDS) array codes are widely used in storage systems due to their computationally efficient encoding and decoding procedures. An MDS code with $r$ redundancy nodes can correct any $r$ node erasures by accessing (reading) all the remaining information in the surviving nodes. However, in practice, $e$ erasures are a more likely failure event, for some $1 \le e < r$ . Hence, a natural question is how much information do we need to access in order to rebuild $e$ storage nodes. We define the rebuilding ratio as the fraction of remaining information accessed during the rebuilding of $e$ erasures. In our previous work, we constructed MDS codes, called zigzag codes, that achieve the optimal rebuilding ratio of $1/r$ for the rebuilding of any systematic node when $e=1$ ; however, all the information needs to be accessed for the rebuilding of the parity node erasure. The (normalized) repair bandwidth is defined as the fraction of information transmitted from the remaining nodes during the rebuilding process. For codes that are not necessarily MDS, Dimakis et al. proposed the regenerating codes framework where any $r$ erasures can be corrected by accessing some of the remaining information, and any $e=1$ erasure can be rebuilt from some subsets of surviving nodes with optimal repair bandwidth. In this paper, we present three results on rebuilding of codes: 1) we show a fundamental outer bound on the storage size of the node and the repair bandwidth similar to the regenerating codes framework, and show that zigzag codes achieve the optimal rebuilding ratio of $e/r$ for systematic nodes of MDS codes, for any $1 \le e \le r$ ; 2) we construct systematic codes that achieve optimal rebuilding ratio of $1/r$ , for any systematic or parity node erasure; and 3) we present error correction algorithms for zigzag codes, and in particular demonstrate how these codes can be corrected beyond their minimum Hamming distances. [ABSTRACT FROM AUTHOR]

Generalized integrated interleaved codes refer to two-level Reed-Solomon codes, such that each code of the nested layer belongs to different subcode of the first-layer code. In this paper, we first devise an efficient decoding algorithm by ignoring first-layer miscorrection and by intelligently reusing preceding results during each iteration of a decoding attempt. Neglecting first-layer miscorrection also enables to explicitly and neatly formulate the decoding failure probability. We next derive an erasure correcting algorithm for redundant arrays of independent disks systems. We further construct an algebraic systematic encoding algorithm, which had been open. Analogously, we propose a novel generalized integrated interleaving scheme over binary Bose-Chaudhuri–Hocquenghem codes, reveal a lower bound on the minimum distance, and derive a similar encoding and decoding algorithm as those of Reed-Solomon codes. [ABSTRACT FROM AUTHOR]

Multi-permutations and in particular permutations appear in various applications in an information theory. New applications, such as rank modulation for flash memories, have suggested the need to consider error-correcting codes for multi-permutations. In this paper, we study systematic error-correcting codes for multi-permutations in general and for permutations in particular. For a given number of information symbols k , and for any integer t , we present a construction of (k+r,k) systematic t -error-correcting codes, for permutations of length $k+r$ , where the number of redundancy symbols $r$ is relatively small. In particular, for a given $t$ and for sufficiently large $k$ , we obtain $r=t+1$ , while a lower bound on the number of redundancy symbols is shown to be $t$ . The same construction is also applied to obtain related systematic error-correcting codes for any types of multi-permutations. [ABSTRACT FROM AUTHOR]

This paper studies secure communication based on incremental redundancy (INR) secure hybrid automatic retransmission request (HARQ) protocol over block-fading wiretap channels. The transmitter has no instantaneous channel state information (CSI) available from either main channel or the eavesdropper channel, hence the coding rates cannot be adapted to instantaneous channel conditions. We investigate the outage performance for two schemes of INR secure HARQ protocols: case 1) when there exists two reliable multibit feedback channels from both legitimate receiver and eavesdropper to the transmitter carrying a function of outdated CSI, and case 2) when there is a multibit feedback channel only from legitimate receiver. In both cases, we demonstrate that using the information carried via multibit feedback channels, the transmitter can adapt the coding rates in order to achieve a better secrecy throughput using a smaller number of transmissions comparing to the ACK/NACK feedback channel model. For some parameters, our rate adaptation protocol achieves a strictly positive secrecy throughput whereas it is equal to zero for the protocol with ACK/NACK feedback. We show that for some set of parameters, the loss of secrecy throughput between case 1 and case 2 is very small compared to the gain provided by both protocols. [ABSTRACT FROM PUBLISHER]

The rank-modulation scheme has been recently proposed for efficiently storing data in nonvolatile memories. In this paper, we explore $[n,k,d]$ systematic error-correcting codes for rank modulation. Such codes have length $n$ , $k$ information symbols, and minimum distance $d$ . Systematic codes have the benefits of enabling efficient information retrieval in conjunction with memory-scrubbing schemes. We study systematic codes for rank modulation under Kendall’s $\tau $ -metric as well as under the $\ell _\infty $ -metric. In Kendall’s $\tau $ -metric, we present $[k+2,k,3]$ systematic codes for correcting a single error, which have optimal rates, unless systematic perfect codes exist. We also study the design of multierror-correcting codes, and provide a construction of $[k+t+1,k,2t+1]$ systematic codes, for large-enough $k$ . We use nonconstructive arguments to show that for rank modulation, systematic codes achieve the same capacity as general error-correcting codes. Finally, in the $\ell _\infty $ -metric, we construct two $[n,k,d]$ systematic multierror-correcting codes, the first for the case of $d=O(1)$ and the second for $d=\Theta (n)$ . In the latter case, the codes have the same asymptotic rate as the best codes currently known in this metric. [ABSTRACT FROM PUBLISHER]