An$(n,k)$recoverable property array code is composed of$m\times n$arrays such that any$k$out of$n$columns suffice to retrieve all the information symbols, where$n > k$. Note that maximum distance separable (MDS) array code is a special$(n,k)$recoverable property array code of size$m\times n$with the number of information symbols being$km$. Expanded-Blaum-Roth (EBR) codes and Expanded-Independent-Parity (EIP) codes are two classes of$(n,k)$recoverable property array codes that can repair any one symbol in a column by locally accessing some other symbols within the column, where the number of symbols$m$in a column is a prime number. By generalizing the constructions of EBR and EIP codes, we propose new$(n,k)$recoverable property array codes, such that any one symbol can be locally recovered and the number of symbols in a column can be not only a prime number but also a power of an odd prime number. Also, we present an efficient encoding/decoding method for the proposed generalized EBR (GEBR) and generalized EIP (GEIP) codes based on the LU factorization of a Vandermonde matrix. We show that the proposed decoding method has less computational complexity than existing methods. Furthermore, we show that the proposed GEBR codes have both a larger minimum symbol distance and a larger recovery ability of erased lines for some parameters when compared to EBR codes. We also present a necessary and sufficient condition of enabling EBR codes to recover any$r$erased lines of a slope for any parameter$r$, which was an open problem. Moreover, we show that EBR codes can recover any$r$consecutive erased lines of any slope for any parameter$r$.

The traditional definition of Integrated Interleaved (II) codes generally assumes that the component nested codes are either Reed-Solomon (RS) or shortened Reed-Solomon codes. By taking general classes of codes, we present a recursive construction of Extended Integrated Interleaved (EII) codes into multiple layers, a problem that brought attention in literature for II codes. The multiple layer approach allows for a hierarchical scheme where each layer of the code provides for a different locality. In particular, we present the erasure-correcting capability of the new codes and we show that they are ideally suited as Locally Recoverable codes (LRC) due to their hierarchical locality and the small finite field required by the construction. Properties of the multiple layer EII codes, like their minimum distance and dimension, as well as their erasure decoding algorithms, parity-check matrices and performance analysis, are provided and illustrated with examples. Finally, we will observe that the parity-check matrices of high layer EII codes have low density.

Modern storage systems consist of many hardware and software components. The core of these systems are server drawers containing data, where at least one of such drawers consists of parity (a special case is two mirrored drawers). We analyze the failure rate of two such systems both based on hyper-converged architectures: one centralized, in which the drawers share the metadata server, and one parallel, in which each drawer has its own metadata server. Inherently the parallel systems will have greater reliability. However, the new CXL and Gen-Z architectures are enabling a centralized approach where resources from multiple servers are combined to make a single virtual server. In this paper we analyze what techniques can make the probability of failure of the centralized approach approximate the probability of failure of the parallel approach. We identified the probability of Dual In-Line Memory Modules (DIMMs) failure as the key differentiator between the probability of failure of the centralized and parallel systems, and we suggest methods to compensate for DIMMs with high probability of failure.

Integrated Interleaved (II) and Extended Integrated Interleaved (EII) codes are a versatile alternative for Locally Recoverable (LRC) codes, since they require fields of relatively small size. II and EII codes are generally defined over Reed-Solomon type of codes. A new comprehensive definition of EII codes is presented, allowing for EII codes over any field, and in particular, over the binary field GF(2) . The traditional definition of II and EII codes is shown to be a special case of the new definition. Improvements over previous constructions of LRC codes, in particular, for binary codes, are given, as well as cases meeting an upper bound on the minimum distance. Properties of the codes are presented as well, in particular, an iterative decoding algorithm on rows and columns generalizing the iterative decoding algorithm of product codes. Two applications are also discussed: one is finding a systematic encoding of EII codes such that the parity symbols have a balanced distribution on rows, and the other is the problem of ordering the symbols of an EII code such that the maximum length of a correctable burst is achieved.

In general, array codes consist of m × n arrays and in many cases, the arrays satisfy parity constraints along lines of different slopes (generally with a toroidal topology). Such codes are useful for RAID type of architectures, since they allow to replace finite field operations by XORs. We present expansions to traditional array codes of this type, like Blaum-Roth (BR) and extended EVENODD codes, by adding parity on columns. This vertical parity allows for recovery of one or more symbols in a column locally, i.e., by using the remaining symbols in the column without invoking the rest of the array. Properties and applications of the new codes are discussed, in particular to Locally Recoverable (LRC) codes.

Partial MDS (PMDS) codes are a class of erasurecorrecting array codes that combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O (max{m, nr+s}s) is presented for the case where r = O(1), s = O(1).

A new class of codes, Extended Product (EPC) Codes, consisting of a product code with a number of extra parities added, is presented and applications for erasure decoding are discussed. An upper bound on the minimum distance of EPC codes is given, as well as constructions meeting the bound for some relevant cases. A special case of EPC codes, Extended Integrated Interleaved (EII) codes, which naturally unify Integrated Interleaved (II) codes and product codes, is defined and studied in detail. It is shown that EII codes often improve the minimum distance of II codes with the same rate, and they enhance the decoding algorithm by allowing decoding on columns as well as on rows. It is also shown that EII codes allow for encoding II codes with an uniform distribution of the parity symbols.

Partial MDS (PMDS) codes are a class of erasure-correcting array codes which combine local correction of the rows with global correction of the array. An m × n array code is called an (r; s) PMDS code if each row belongs to an [n, n - r, r + 1] MDS code and the code can correct erasure patterns consisting of r erasures in each row together with s more erasures anywhere in the array. While a recent construction by Calis and Koyluoglu generates (r; s) PMDS codes for all r and s, its field size is exponentially large. In this paper, a family of PMDS codes with field size O(max{m, nr+s}s) is presented.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while sector-disk (SD) codes are erasure codes that address the mixed failure mode of current redundant arrays of independent disk (RAID) systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

Partial MDS (PMDS) codes are erasure codes combining local (row) correction with global additional correction of entries, while Sector-Disk (SD) codes are erasure codes that address the mixed failure mode of current RAID systems. It has been an open problem to construct general codes that have the PMDS and the SD properties, and previous work has relied on Monte-Carlo searches. In this paper, we present a general construction that addresses the case of any number of failed disks and in addition, two erased sectors. The construction requires a modest field size. This result generalizes previous constructions extending RAID 5 and RAID 6.

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.

Traditionally, when storage systems employ erasure codes, they are designed to tolerate the failures of entire disks. However, the most common types of failures are latent sector failures, which only affect individual disk sectors, and block failures which arise through wear on SSD’s. This article introduces SD codes, which are designed to tolerate combinations of disk and sector failures. As such, they consume far less storage resources than traditional erasure codes. We specify the codes with enough detail for the storage practitioner to employ them, discuss their practical properties, and detail an open-source implementation.

A family of codes with a natural 2-D structure is presented, inspired by an application of redundant arrays of independent disks (RAID) type of architectures whose units are solid-state drives (SSDs). Arrays of SSDs behave differently from arrays of hard disk drives, since hard errors in sectors are common and traditional RAID approaches (like RAID 5 or RAID 6) may be either insufficient or excessive. An efficient solution to this problem is given by the new codes presented, called partial maximum distance separable (PMDS) codes.

We introduce a technique for constructing codes for bursts of errors that have some known structure; for example bursts of length at most b and Hamming weight at most t. This technique is based on modifying existing codes for generic bursts by replacing a portion of their check matrix with a more efficient one, in light of the additional constraints on the burst. We illustrate this procedure by modifying the Fire, Burton and Gilbert codes to address bursts with maximum Hamming weight, bursts with solid errors, or bursts with internal “mini-bursts”. We provide evidence that the redundancy of the codes we construct can be very good through examples, one of which is optimal within the class of cyclic codes.

Nowadays, satisfying the global throughput targets of each application in High Performance Computing systems is a difficult task because of the high number of architectural configurations having a considerable impact on the overall system performance, such as the number of storage servers, features of the communication links, number of CPU cores per node, etc. In this paper we have performed a thorough study of the compared performance of scaling up HPC cluster architectures using a checkpointing application model. This study is specifically focused on multi-core HPC clusters and the scaling process is oriented towards the three main resources: computing power, communications and storage. The main goal of this work is to evaluate and analyze how evolves both scalability and bottlenecks existent on different HPC multi-core architectures using different architectural configurations. In order to achieve this goal, a set of simulation experiments has been achieved using a simulation framework, called SIMCAN, specifically designed for modeling and simulating HPC architectures. The results obtained show that the computing power is well suited thanks to the multi-core processors, while the problems are found on the storage and on the communications channels, being the storage network the main bottleneck.

In a previous work [5] it was shown that the best measure for the efficiency of a single burst-correcting code is obtained using the Gallager bound as opposed to the Reiger bound. In this paper, an algorithm that optimizes the search for the best (shortened) cyclic burst-correcting codes is presented. The use of Gray codes in the algorithm optimizes the search, in the sense that no repeated syndromes are computed.

A new coding framework is established for channels whose outputs are overlapping pairs of symbols. Such channels are motivated by storage applications in which the spatial resolution of the reader may be insufficient to isolate adjacent symbols. Reading symbols as pairs changes the coding-theoretic error model from the standard bounded number of symbol errors to a bounded number of pair errors. Starting from the most basic coding-theoretic questions, the paper studies codes that protect against pair-errors. It provides answers on pair-error correctability conditions, code construction and decoding, and lower and upper bounds on code sizes. Asymptotic analysis of pair-error correction shows that there exist pair-error codes with rates that are strictly higher than the best known codes in the Hamming metric.

A new coding framework is established for channels whose outputs are overlapping pairs of symbols. Such channels are motivated by storage applications in which the spatial resolution of the reader may be lower than that of the process that was used to store the data. Reading symbols as pairs changes the error model from the standard bounded number of symbol errors to a bounded number of pair errors. Starting from the most basic coding-theoretic questions, the paper studies codes that protect against pair-errors. It provides answers on pair-error correctability, code construction and decoding, and lower and upper bounds on code sizes.

Shortened cyclic codes that are capable of correcting up to a single burst of errors are considered. The efficiency of such codes has been analized by how well they approximate the Reiger bound, i.e., by the burst-correcting efficiency of the code. Although the efficiency is still an important parameter, it is shown that this one is not necessarily the most important consideration when choosing a single-burst-correcting code. It is shown that in some natural practical applications (like in a Gilbert–Elliot channel), it is more important to optimize the rate of the code with respect to its guard space, a goal closely related to the Gallager bound. The concepts of all-around, non-all around and partial all-around single-burst-correcting codes are introduced and illustrated with examples, some from existing constructions and some from new ones. Tables are presented showing that in many cases the new codes have better parameters than the existing ones for the same burst-correcting capability.

Parity is a popular form of data protection in redundant arrays of inexpensive/independent disks (RAID) . RAID5 dedicates one out of N disks to parity to mask single disk failures, that is, the contents of a block on a failed disk can be reconstructed by exclusive-ORing the corresponding blocks on surviving disks. RAID5 can mask a single disk failure, and it is vulnerable to data loss if a second disk failure occurs. The RAID5 rebuild process systematically reconstructs the contents of a failed disk on a spare disk, returning the system to its original state, but the rebuild process may be unsuccessful due to unreadable sectors. This has led to two disk failure tolerant arrays (2DFTs) , such as RAID6 based on Reed-Solomon (RS) codes. EVENODD, RDP (Row-Diagonal-Parity), the X-code, and RM2 (Row-Matrix) are 2DFTs with parity coding. RM2 incurs a higher level of redundancy than two disks, while the X-code is limited to a prime number of disks. RDP is optimal with respect to the number of XOR operations at the encoding, but not for short write operations. For small symbol sizes EVENODD and RDP have the same disk access pattern as RAID6, while RM2 and the X-code incur a high recovery cost with two failed disks. We describe variations to RAID5 and RAID6 organizations, including clustered RAID, different methods to update parities, rebuild processing, disk scrubbing to eliminate sector errors, and the intra-disk redundancy (IDR) method to deal with sector errors. We summarize the results of recent studies of failures in hard disk drives. We describe Markov chain reliability models to estimate RAID mean time to data loss (MTTDL) taking into account sector errors and the effect of disk scrubbing. Numerical results show that RAID5 plus IDR attains the same MTTDL level as RAID6, while incurring a lower performance penalty. We conclude with a survey of analytic and simulation studies of RAID performance and tools and benchmarks for RAID performance evaluation.

We present a reverse concatenation (RC) architecture with maximum transition run (MTR) modulation codes and Reed-Solomon (RS) error-correction codes (ECCs). The scheme employs a high-rate primary (pre-RS) MTR code and a secondary (post-RS) MTR code, which controls error propagation. The two modulation codes are designed in such a way to maximize the overall code rate and maintain simple hardware implementation. Simulation results demonstrate superior performance compared to reverse concatenation with non-MTR codes, especially at a relatively high recording density.

Generalized Concatenation (GC) of Reed-Solomon (RS) Codes is a powerful technique to enhance the error-correcting capability of RS codes without resorting to large finite fields. However, interleaving a GC scheme in the standard column-wise way significantly reduces the burst-correcting capability of such scheme. In this paper, we present techniques that optimize the burst-correcting capability of some GC schemes.

A reverse concatenation scheme based on an efficient modulation encoder satisfying non-uniform constraints, a systematic Reed-Solomon encoder and a partial symbol interleaver is presented. This architecture achieves very tight modulation constraints and minimizes error propagation and rate loss. The modulation constraints considered are of the same type as the constraints that have been used in generalized partial-response maximum-likelihood (PRML) detection systems. A class of codes that is based on serial concatenation of a prefix-constrained code and two interleaved enumerative codes with non-uniform constraints is proposed. Specific rate-199/200 PRML(G, I) codes are constructed.

We present techniques for reducing error propagation in modulation encoded data. Error propagation is reduced by using Fibonacci modulation codes that have limited span at certain positions. Errors occurring in bit positions of an encoded sequence that correspond to the limited span elements do not propagate beyond the span of those elements in the decoded sequence. Simulation results show that the proposed variable span modulation codes yield improved sector error rates when used instead of fixed span codes in magnetic recording systems.

In this correspondence, the combinatorial properties of traceability codes constructed from error-correcting codes are studied. Necessary and sufficient conditions for traceability codes constructed from maximum-distance separable (MDS) codes are provided. The known sufficient conditions for a traceability code are proven to be also necessary for linear MDS codes

We propose new systematic constructions of Gray codes that improve reliability of the track identification field in the servo portion of a magnetic recording disk. In this application, it is beneficial to obtain good distance properties within a certain range of neighboring Gray codewords, because the servo positioning system typically gives a good estimate of the range of interest. With proposed Gray codes, we provide a high separation range between non-adjacent Gray codewords at Hamming distance one, which guarantees error detection within this range. In addition, we provide a certain level of separation between Gray codewords at Hamming distance two, which can be utilized for error correction.

In P. Corbett et a. (2004), the authors present a row-diagonal parity scheme with two parity columns for a (p - 1) times (p + 1) array, p a prime, that recovers any two erased columns. The code minimizes the number of XORs at the encoding. It was left as an open problem generalizing this scheme to multiple parities. In this paper, we present such a generalization. In particular, when we have three parity columns, the new code recovers any three erased columns. Efficient encoding and decoding algorithms are presented

We consider a particular family of Gray codes having the property that codewords ciand ci+2differ in a burst of length exactly two. These codes can be applied in the servo track-identification field to identify the correct track during seeks. We call these codes skew-tolerant Gray codes (STGC) and we present explicit constructions

Disk mirroring or RAID level 1 (RAID1) is a popular paradigm to achieve fault tolerance and a higher disk access bandwidth for read requests. We consider four RAID1 organizations: basic mirroring, group rotate declustering, interleaved declustering, and chained declustering, where the last three organizations attain a more balanced load than basic mirroring when disk failures occur. We first obtain the number of configurations, A(n, i), which do not result in data loss when i out of n disks have failed. The probability of no data loss in this case is A(n, i)/matrix of(n, i). The reliability of each RAID1 organization is the summation over 1 les i les n/2 of A(n, i)rn-i(1 - r)i, where r denotes the reliability of each disk. A closed-form expression for A(n, i) is obtained easily for the first three organizations. We present a relatively simple derivation of the expression for A(n, i) for the chained declustering method, which includes a correctness proof. We also discuss the routing of read requests to balance disk loads, especially when there are disk failures, to maximize the attainable throughput

Array codes are error-correcting codes of very low complexity that were initially used for burst and erasure correction in redundant arrays of inexpensive disks (RAID) architectures and other storage applications. The structure of these codes allows a very simple encoding and decoding mechanism. Although they are very high-rate codes, they do not achieve the maximum possible rate given their design constraints. In fact Hamming codes maximize the possible rate given these design constraints. This paper compares the rate and complexity of array codes when compared to Hamming codes.

In this paper, the multiple burst-correcting shortened cyclic codes are proposed which is optimal in terms of redundancy. We consider linear binary codes and Reed-Solomon codes for correcting shortened cyclic codes.

A method of equalization using a data sequence always present on tape is described. This data sequence is part of the standard LTO format. The equalizer calculation is based on the Levinson Toeplitz matrix inversion method and utilizes cosine pulse symmetrization to achieve results independent of the target-signal phase delay.

We present a family of maximum-distance separable (MDS) array codes of size (p-1)×(p-1), p a prime number, and minimum criss-cross distance 3, i.e., the code is capable of correcting any row or column in error, without a priori knowledge of what type of error occurred. The complexity of the encoding and decoding algorithms is lower than that of known codes with the same error-correcting power, since our algorithms are based on exclusive-OR operations over lines of different slopes, as opposed to algebraic operations over a finite field. We also provide efficient encoding and decoding algorithms for errors and erasures.

We provide a new definition for the concept of skew in parallel asynchronous communications introduced by Blaum and Bruck (1993). The new definition extends and strengthens previously known results on skew. We give necessary and sufficient conditions for codes that can tolerate a certain amount of skew under the new definition. We also extend the results to codes that can tolerate a certain amount of skew and detect a larger amount of skew when the tolerating threshold is exceeded.

Let F/sub q/ denote the finite field GF(q) and let h be a positive integer. MDS (maximum distance separable) codes over the symbol alphabet F/sub q//sup b/ are considered that are linear over F/sub q/ and have sparse ("low-density") parity-check and generator matrices over F/sub q/ that are systematic over F/sub q//sup b/. Lower bounds are presented on the number of nonzero elements in any systematic parity-check or generator matrix of an F/sub q/-linear MDS code over F/sub q//sup b/, along with upper bounds on the length of any MDS code that attains those lower bounds. A construction is presented that achieves those bounds for certain redundancy values. The building block of the construction is a set of sparse nonsingular matrices over F/sub q/ whose pairwise differences are also nonsingular. Bounds and constructions are presented also for the case where the systematic condition on the parity-check and generator matrices is relaxed to be over F/sub q/, rather than over F/sub q//sup b/.

We present coding methods for protecting against tampering of write-once optical disks, which turns them into a secure digital medium for applications where critical information must be stored in a way that prevents or allows detection of an attempt at falsification. Our method involves adding a small amount of redundancy to a modulated sector of data. This extra redundancy is not used for normal operation, but can be used for determining, say, as a testimony in court, that a disk has not been tampered with.

We present two-dimensional and three-dimensional interleaving techniques for correcting two- and three-dimensional bursts (or clusters) of errors, where a cluster of errors is characterized by its area or volume. Correction of multidimensional error clusters is required in holographic storage, an emerging application of considerable importance. Our main contribution is the construction of efficient two-dimensional and three-dimensional interleaving schemes. The proposed schemes are based on t-interleaved arrays of integers, defined by the property that every connected component of area or volume t consists of distinct integers. In the two-dimensional case, our constructions are optimal: they have the lowest possible interleaving degree. That is, the resulting t-interleaved arrays contain the smallest possible number of distinct integers, hence minimizing the number of codewords required in an interleaving scheme. In general, we observe that the interleaving problem can be interpreted as a graph-coloring problem, and introduce the useful special class of lattice interleavers. We employ a result of Minkowski, dating back to 1904, to establish both upper and lower bounds on the interleaving degree of lattice interleavers in three dimensions. For the case t/spl equiv/0 mod 6, the upper and lower bounds coincide, and the Minkowski lattice directly yields an optimal lattice interleaver. For t/spl ne/0 mod 6, we construct efficient lattice interleavers using approximations of the Minkowski lattice.

A common method of constructing t-error correcting/all unidirectional error detecting (t-EC/AUED) codes is to choose a t-EC code and then to append a tail such that the new code can detect all unidirectional errors. The tail is a function of the weight of the codeword. We present a technique to reduce the weight distribution of the t-EC code so that the tail needed will be shorter in some cases. The weight distribution span of the code is reduced by eliminating the all-zero codeword and replacing it with a codeword of weight greater than 2t+1.

A new family of maximum distance separable (MDS) array codes is presented. The code arrays contain p information columns and r independent parity columns, each column consisting of p-1 bits, where p is a prime. We extend a previously known construction for the case r=2 to three and more parity columns. It is shown that when r=3 such extension is possible for any prime p. For larger values of r, we give necessary and sufficient conditions for our codes to be MDS, and then prove that if p belongs to a certain class of primes these conditions are satisfied up to r/spl les/8. One of the advantages of the new codes is that encoding and decoding may be accomplished using simple cyclic shifts and XOR operations on the columns of the code array. We develop efficient decoding procedures for the case of two- and three-column errors. This again extends the previously known results for the case of a single-column error. Another primary advantage of our codes is related to the problem of efficient information updates. We present upper and lower bounds on the average number of parity bits which have to be updated in an MDS code over GF (2/sup m/), following an update in a single information bit. This average number is of importance in many storage applications which require frequent updates of information. We show that the upper bound obtained from our codes is close to the lower bound and, most importantly, does not depend on the size of the code symbols.

In holographic storage, two-dimensional arrays of binary data is optically recorded in a medium via an interference process. To ensure optimum operation of a holographic recording system, it is desirable that the patterns of 1s (light) and 0s (no light) in the recorded array satisfy the following modulation constraint: in each row and column of the array there are at least t transitions of the type 1/spl rarr/0 or 0/spl rarr/1, for a prescribed integer t. A two-dimensional array with this property is said to be a conservative array of strength t. In general, an n-dimensional conservative array of strength t is a binary array having at least t transitions in each column, extending in any of the n dimensions of the array. We present an algorithm for encoding unconstrained binary data into an n-dimensional conservative array of strength t. The algorithm employs differential coding and error-correcting codes. Using n binary codes-one per dimension-with minimum Hamming distance d/spl ges/2t-3, we apply a certain transformation to an arbitrary information array which ensures that the number of transitions in each dimension is determined by the minimum distance of the corresponding code.

Consider a communication channel that consists of several subchannels transmitting simultaneously and asynchronously. As an example of this scheme, we can consider a board with several chips. The subchannels represent wires connecting between the chips where differences in the lengths of the wires might result in asynchronous reception. In current technology, the receiver acknowledges reception of the message before the transmitter sends the following message. Namely, pipelined utilization of the channel is not possible. Our main contribution is a scheme that enables transmission without an acknowledgment of the message, therefore enabling pipelined communication and providing a higher bandwidth. However, our scheme allows for a certain number of transitions from a second message to arrive before reception of the current message has been completed, a condition that we call skew. We have derived necessary and sufficient conditions for codes that can tolerate a certain amount of skew among adjacent messages (therefore, allowing for continuous operation) and detect a larger amount of skew when the original skew is exceeded. These results generalize previously known results. We have constructed codes that satisfy the necessary and sufficient conditions, studied their optimality, and devised efficient decoding algorithms. To the best of our knowledge, this is the first known scheme that permits efficient asynchronous communications without acknowledgment. Potential applications are in on-chip, on-board, and board to board communications, enabling much higher communication bandwidth.>

We present a novel method, that we call EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. This redundant storage is optimal, in the sense that two failed disks cannot be retrieved with less than two redundant disks. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The most commonly used scheme that employes optimal redundant storage (i.e., two extra disks) is based on Reed-Solomon (RS) error-correcting codes. This scheme requires computation over finite fields and results in a more complex implementation. For example, we show that the complexity of implementing EVENODD in a disk array with 15 disks is about 50% of the one required when using the RS scheme. The new scheme is not limited to RAID architectures: it can be used in any system requiring large symbols and relatively short codes, for instance, in multitrack magnetic recording. To this end, we also present a decoding algorithm for one column (track) in error.>

Several techniques for constructing practical codes for noisy modulation channels represented by (d,k) constraints, such as in magnetic and optical recording, are analyzed. Concatenated schemes based on inner sliding-window codes are compared with concatenated schemes based on inner block codes in terms of efficiency and reliability. The performance of the schemes is investigated in detail for (1,7) constrained channels with different error characteristics. It is shown that for such channels, concatenated schemes based on inner sliding-window codes have higher code rates than concatenated schemes based on inner block codes for typical applications. However, if the channels are very noisy or extremely small decoding error probabilities are required, then the latter schemes tend to have higher code rates than the former ones.

Presents a novel method, called EVENODD, for tolerating up to two disk failures in RAID architectures. EVENODD is the first known scheme for tolerating double disk failures that is optimal with regard to both storage and performance. EVENODD employs the addition of only two redundant disks and consists of simple exclusive-OR computations. A major advantage of EVENODD is that it only requires parity hardware, which is typically present in standard RAID-5 controllers. Hence, EVENODD can be implemented on standard RAID-5 controllers without any hardware changes. The only previously known scheme that employs optimal redundant storage (i.e. two extra disks) is based on Reed-Solomon (RS) error-correcting codes, requires computation over finite fields and results in a more complex implementation. For example, the authors show that the number of exclusive-OR operations involved in implementing EVENODD in a disk array with 15 disks is about 50% of the number required when using the RS scheme.>

J.W. Schwartz and J.K. Wolf (ibid., vol. 39, no. 11, pp. 1403-1404, Nov. 1990) gave a parity check matrix for a systematic (12,8) binary code that corrects all single errors and detects eight of the nine double adjacent errors within any of the three 4-bit nibbles. We present a parity check matrix for a systematic (12,8) binary code that corrects all single errors and detects any pair of errors within a nibble.>

Assume that information is transmitted in parallel among many lines in such a way that an electrical transition represents a 1 and an absence of a transition represents a 0. The propagation delay in the wires varies and results in asynchronous reception. The challenge is to find an efficient communication scheme that will be delay-insensitive. One of the common solutions to this problem is to use a handshake mechanism. Namely, the transmitter sends the next vector only after getting an acknowledgment that the current vector was received. A natural question is: how does the receiver know that reception of the current vector is complete? This problem was solved by Verhoeff (1988) by using the so-called unordered codes. However, in practice, it is common that the communication lines are arranged in pairs (double-rail) such that the propagation delay on the lines within a pair is identical. In general, the lines can be arranged in groups (of size larger than 1) where transmission within a group is synchronized. The authors have created a few delay-insensitive schemes that take advantage of partial synchronization within groups. To achieve that, they have generalized to arbitrary alphabets the following known results: Sperner's theorem on unordered sets, Henry-Knuth's (Henry, 1982; Knuth, 1986) construction of balanced codes, and Berger's (1961) construction of unordered codes. Finally, they have focused on practice, and constructed a code that uses double-rail channels but has the advantage that it is a rate 3/4 code as opposed to the rate 1/2 double-rail code (that is the common code being used in real systems).>

A communication channel consisting of several subchannels transmitting simultaneously and asynchronously is considered, an example being a board with several chips, where the subchannels are wires connecting the chips and differences in the lengths of the wires can result in asynchronous reception. A scheme that allows transmission without an acknowledgment of the message, therefore permitting pipelined communication and providing a higher bandwidth, is described. The scheme allows a certain number of transitions from a second message to arrive before reception of the current message has been completed, a condition called skew. Necessary and sufficient conditions for codes that can detect skew as well as for codes that are skew-tolerant, i.e. can correct the skew and allow continuous operation, are derived. Codes that satisfy the necessary and sufficient conditions are constructed, their optimality is studied, and efficient decoding algorithms are devised. Potential applications of the scheme are in on-chip, on-board, and board to board communications, enabling much higher communication bandwidth.>

The paradigm of skew-tolerant parallel asynchronous communication was introduced by Blaum and Bruck (see ibid., vol. 39, 1993) along with constructions for codes that can tolerate or detect skew. Some of these constructions were improved by Khachatrian (1991). In this paper these constructions are improved upon further, and the authors prove that the new constructions are, in a certain sense, optimal.>

A new approach for encoding any string of information bits into a sequence having bounded running digital sum is presented. The results improve previously known values of the running digital sum for the same rate. Also discussed are ways of incorporating an error-correcting capability into these codes. Some general constructions are given and tables are constructed for specific cases.>

An optimal family of array codes over GF(q) for correcting multiple phased burst errors and erasures, where each phased burst corresponds to an erroneous or erased column in a code array, is introduced. As for erasures, these array codes have an efficient decoding algorithm which avoids multiplications (or divisions) over extension fields, replacing these operations with cyclic shifts of vectors over GF(q). The erasure decoding algorithm can be adapted easily to handle single column errors as well. The codes are characterized geometrically by means of parity constraints along certain diagonal lines in each code array, thus generalizing a previously known construction for the special case of two erasures. Algebraically, they can be interpreted as Reed-Solomon codes. When q is primitive in GF(q), the resulting codes become (conventional) Reed-Solomon codes of length P over GF(q/sup p-1/), in which case the new erasure decoding technique can be incorporated into the Berlekamp-Massey algorithm, yielding a faster way to compute the values of any prescribed number of errors.>

Two new techniques for constructing t-EC/AUED (error correcting/all unidirectional error detection) codes are presented. The first technique modifies the t-EC/AUED code in such a way that the weight distribution of the original code is reduced. So, a smaller tail is needed. Frequently, this technique gives less overall redundancy than the best available t-EC/AUED codes. The second technique improves the parameters of the tails with respect to previous results.>

A technique for combining error correcting codes (ECCs) with modulation codes of the block type is described. Its performance is analyzed with respect to the traditional method in magnetic recording, which involves the concatenation of error-correcting code with a convolutional modulation code. Conditions are established under which the new method is superior to the concatenated scheme. For a fixed number of information bits, the total redundancy with the two methods is calculated and conditions are established under which the redundancy of the new method is smaller than the redundancy of the traditional method. In particular, performance with respect to the

A family of binary burst correcting array codes that are defined as follows is discussed: consider an n/sub 1/*nn/sub 2/ array with n/sub 1/=4u+ nu +2 and n/sub 2/=6u+2 nu +5, u>or=1, nu >or=0, nu not=1 where each row and column has even parity. The bits are read diagonally starting from the upper-left corner. The columns are viewed cyclically, i.e. the array is a cylinder. If one diagonal has been read out, one proceeds with the second diagonal preceding it. It is proven that the codes of this type can correct any burst of length up to n/sub 1/. The burst-correcting efficiency of this family tends to 4/5 as u to infinity . As a comparison, the burst-correcting efficiency of other families of array codes tends to 2/3; the same is true for Fire codes. A simple decoding algorithm for the codes is also presented.>

A decoding algorithm, based on Venn diagrams, for decoding the (23, 12, 7) Golay code is presented. The decoding algorithm is based on the design properties of the parity sets of the code. As for other decoding algorithms for the Golay code, decoding can be easily done by hand.>

The authors present families of binary systematics codes that can correct t random errors and detect more than t unidirectional errors. The first step of the construction is encoding the k information symbols into a codeword of an (n', k, 2t+1) error-correcting code. The second step involves adding more bits to this linear error-correcting code in order to obtain the detection capability of all unidirectional errors. Asymmetric error-correcting codes turn out to be a powerful tool in the proposed construction. The resulting codes significantly improve previous results. Asymptotic estimates and decoding algorithms are presented.>

Several ways of relating the concept of error-correcting codes to the concept of neural networks are presented. Performing maximum-likelihood decoding in a linear block error-correcting code is shown to be equivalent to finding a global maximum of the energy function of a certain neural network. Given a linear block code, a neural network can be constructed in such a way that every codeword corresponds to a local maximum. The connection between maximization of polynomials over the n-cube and error-correcting codes is also investigated; the results suggest that decoding techniques can be a useful tool for solving such maximization problems. The results are generalized to both nonbinary and nonlinear codes.>

A class of convolutional codes called cross parity check (CPC) codes, which are useful for the protection of data stored on magnetic tape, is described and analyzed. CPC codes are first explained geometrically; their construction is described in terms of constraining data written onto a tape in such a way that when lines of varying slope are drawn across the tape, the bits falling on those lines sum to zero modulo two. This geometric interpretation is then formalized by the construction of canonical parity check matrices and systematic generator matrices for CPC codes and by computing their constraint lengths. The distance properties of CPC codes are analyzed, and it is shown that these codes are maximum distance separable convolutional codes. In addition, examples are given of both error and erasure decoding algorithms that take advantage of the geometric regularity of CPC codes. The technique of parity check matrix reduction, which is useful for reducing the inherent decoding delay of CPC codes, is described. The technique consists of dividing each term of the parity check matrix by some polynomial and retaining only the remainder. A class of polynomials that are particularly attractive for this purpose if identified.>

Results are presented on families of balanced binary error-correcting codes that extend those in the literature. The idea is to consider balanced blocks as symbols over an alphabet and to construct error-correcting codes over that alphabet. Encoding and decoding procedures are presented. Several improvements to the general construction are discussed.>

Families of systematic unidirectional burst-detecting codes are presented. When the number of information bits is large enough, the codes can detect longer bursts than previously known codes. Encoding and decoding procedures are indicated.>

The lifetimes of computer memories which are protected with single-error-correcting-double-error-detecting (SEC-DED) codes are studies. The authors assume that there are five possible types of memory chip failure (single-cell, row, column, row-column and whole chip), and, after making a simplifying assumption (the Poisson assumption), have substantiated that experimentally. A simple closed-form expression is derived for the system reliability function. Using this formula and chip reliability data taken from published tables, it is possible to compute the mean time to failure for realistic memory systems.>

A (2n, k, l, c, d) DC free binary block code is a code of length 2n, constant weight n, 2/sup k/ codewords, maximum runlength of a symbol l, maximum accumulated charge c, and minimum distance d. The purpose of this code is to achieve DC freeness and error correction at the same time. The goal is to keep the rate k/2n and d large and l and c small. Of course, these are conflicting goals. H.C. Ferreira (IEEE Trans. Magn., vol.MAG-20, no.5, p.881-3, 1984) presented a (16, 8, 8, 5, 4) DC free code. Here, a (16, 9, 6, 5, 4) DC free code is presented. Easy encoding and decoding algorithms are also given.>

Two families of binary linear multiple-burst-correcting array codes are presented. The codes consist of all possible n/sub 1/*n/sub 2/ arrays over GF(2), where the columns have even parity and the rows belong to any given code of length n/sub 2/ and minimum distance 2t. It is shown that if the bits are read out diagonally instead of horizontally, each diagonal followed by the preceding one (viewed cyclically), then the code can correct up to t bursts of lengthor=tn/sub 1/+1. If each diagonal is followed by the next one, the code can correct up to t bursts of lengthor=2t(n-2)+1. For t=1 some of these results are already known. Decoding algorithms are presented, and the case t=1 is discussed in more detail.>

The usual(k_{2} + 1) \times (k_{1} + 1)array code, in which the last row and the last column contain redundant bits, can correct any single error. However, if the bits are read diagonally instead of horizontally, the code can correct bursts of errors. It is shown that the(_{k}2 + 1) \times (k_{1} + 1)array code with diagonal readout can correct any burst of length up tok_{1}if and only ifk_{2} \geq 2(k_{1} - 1).

Patel and Hong have constructed a code that can correct any track error or two track erasures in a9-track magnetic tape. Here the construction is extended to a code that can correct a track error and a track erasure or three track erasures. A generalization is given.