Search

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]

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]

Maximum distance separable (MDS) codes are optimal error-correcting codes in the sense that they provide the maximum failure tolerance for a given number of parity nodes. Suppose that an MDS code with $k$ information nodes and r=n-k$ parity nodes is used to encode data in a distributed storage system. It is known that if h$ out of the n$ nodes are inaccessible and d$ surviving (helper) nodes are used to recover the lost data, then we need to download at least h/(d+h-k)$ fraction of the data stored in each of the helper nodes (Dimakis et al., 2010 and Cadambe et al., 2013). If this lower bound is achieved for the repair of any h$ erased nodes from any d$ helper nodes, we say that the MDS code has the (h,d)$ -optimal repair property. We study high-rate MDS array codes with the optimal repair property (also known as minimum storage regenerating codes, or MSR codes). Explicit constructions of such codes in the literature are only available for the cases where there are at most three parity nodes, and these existing constructions can only optimally repair a single node failure by accessing all the surviving nodes. In this paper, given any r$ and n$ , we present two explicit constructions of MDS array codes with the (h,d) . The encoding, decoding, repair of failed nodes, and update procedures of these codes all have low complexity. Codes in the second family have the optimal access property and can be constructed over any base field $F$ as long as $|F|\ge n+1$ . Moreover, both code families have the optimal error resilience capability when repairing failed nodes. We also construct several other related families of MDS codes with the optimal repair property. [ABSTRACT FROM PUBLISHER]

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]

This paper introduces a new family of error-correction unordered (ECU) codes for global communication, called Zero-Sum. They combine the timing-robustness of delay-insensitive (i.e., unordered) codes with the fault-tolerance of error-correcting codes (providing 1-bit error correction or 2-bit detection). Two key features of the codes are that they are systematic, allowing direct extraction of data, and weighted, where the check field is computed as the sum of data index weights. A wide variety of weight assignments is shown to be feasible. Two practical enhancements are also proposed. The Zero\-Sum^+ code extends error detection to 3-bit errors, or alternatively handles 2-bit detection and 1-bit correction. The Zero\-Sum^\ast code supports heuristic 2-bit correction, while still guaranteeing 2-bit detection, under different strategies of weight assignment. Detailed hardware implementations of the supporting components (encoder, completion detection, error corrector) are given, as well as an outline of the system microarchitecture. In comparison to the best alternative systematic ECU code, the basic Zero-Sum code provided better or comparable coding efficiency, with a 5.74%–18.18% reduction in average number of wire transitions for most field sizes. Several Zero\-Sum^\ast codes were also evaluated for their 2-bit error correction coverage; initial results are promising, where the best strategy corrected 52.92%–71.16% of all 2-bit errors for most field sizes, with only a moderate decrease in coding efficiency and increase in wire transitions. Technology-mapped pre-layout implementations of the supporting Zero-Sum code hardware were synthesized with the UC Berkeley ABC tool using a 90 nm industrial standard cell library. Results indicate that they have moderate area and delay overheads. In comparison, supporting hardware for the best nonsystematic ECU codes have 3.82\--10.44\times greater area for larger field sizes. [ABSTRACT FROM PUBLISHER]