-
When Do WOM Codes Improve the Erasure Factor in Flash Memories?
Authors:
Eitan Yaakobi,
Alexander Yucovich,
Gal Maor,
Gala Yadgar
Abstract:
Flash memory is a write-once medium in which reprogramming cells requires first erasing the block that contains them. The lifetime of the flash is a function of the number of block erasures and can be as small as several thousands. To reduce the number of block erasures, pages, which are the smallest write unit, are rewritten out-of-place in the memory. A Write-once memory (WOM) code is a coding s…
▽ More
Flash memory is a write-once medium in which reprogramming cells requires first erasing the block that contains them. The lifetime of the flash is a function of the number of block erasures and can be as small as several thousands. To reduce the number of block erasures, pages, which are the smallest write unit, are rewritten out-of-place in the memory. A Write-once memory (WOM) code is a coding scheme which enables to write multiple times to the block before an erasure. However, these codes come with significant rate loss. For example, the rate for writing twice (with the same rate) is at most 0.77.
In this paper, we study WOM codes and their tradeoff between rate loss and reduction in the number of block erasures, when pages are written uniformly at random. First, we introduce a new measure, called erasure factor, that reflects both the number of block erasures and the amount of data that can be written on each block. A key point in our analysis is that this tradeoff depends upon the specific implementation of WOM codes in the memory. We consider two systems that use WOM codes; a conventional scheme that was commonly used, and a new recent design that preserves the overall storage capacity. While the first system can improve the erasure factor only when the storage rate is at most 0.6442, we show that the second scheme always improves this figure of merit.
△ Less
Submitted 22 April, 2015;
originally announced April 2015.
-
Optimal Linear and Cyclic Locally Repairable Codes over Small Fields
Authors:
Alexander Zeh,
Eitan Yaakobi
Abstract:
We consider locally repairable codes over small fields and propose constructions of optimal cyclic and linear codes in terms of the dimension for a given distance and length. Four new constructions of optimal linear codes over small fields with locality properties are developed. The first two approaches give binary cyclic codes with locality two. While the first construction has availability one,…
▽ More
We consider locally repairable codes over small fields and propose constructions of optimal cyclic and linear codes in terms of the dimension for a given distance and length. Four new constructions of optimal linear codes over small fields with locality properties are developed. The first two approaches give binary cyclic codes with locality two. While the first construction has availability one, the second binary code is characterized by multiple available repair sets based on a binary Simplex code. The third approach extends the first one to q-ary cyclic codes including (binary) extension fields, where the locality property is determined by the properties of a shortened first-order Reed-Muller code. Non-cyclic optimal binary linear codes with locality greater than two are obtained by the fourth construction.
△ Less
Submitted 24 February, 2015;
originally announced February 2015.
-
Generalized Sphere Packing Bound
Authors:
Arman Fazeli,
Alexander Vardy,
Eitan Yaakobi
Abstract:
Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a co…
▽ More
Kulkarni and Kiyavash recently introduced a new method to establish upper bounds on the size of deletion-correcting codes. This method is based upon tools from hypergraph theory. The deletion channel is represented by a hypergraph whose edges are the deletion balls (or spheres), so that a deletion-correcting code becomes a matching in this hypergraph. Consequently, a bound on the size of such a code can be obtained from bounds on the matching number of a hypergraph. Classical results in hypergraph theory are then invoked to compute an upper bound on the matching number as a solution to a linear-programming problem.
The method by Kulkarni and Kiyavash can be applied not only for the deletion channel but also for other error channels. This paper studies this method in its most general setup. First, it is shown that if the error channel is regular and symmetric then this upper bound coincides with the sphere packing bound and thus is called the generalized sphere packing bound. Even though this bound is explicitly given by a linear programming problem, finding its exact value may still be a challenging task. In order to simplify the complexity of the problem, we present a technique based upon graph automorphisms that in many cases reduces the number of variables and constraints in the problem. We then apply this method on specific examples of error channels. We start with the $Z$ channel and show how to exactly find the generalized sphere packing bound for this setup. Next studied is the non-binary limited magnitude channel both for symmetric and asymmetric errors, where we focus on the single-error case. We follow up on the deletion and grain-error channels and show how to improve upon the existing upper bounds for single deletion/error. Finally, we apply this method for projective spaces and find its generalized sphere packing bound for the single-error case.
△ Less
Submitted 24 January, 2014;
originally announced January 2014.
-
Construction of Partial MDS (PMDS) and Sector-Disk (SD) Codes with Two Global Parity Symbols
Authors:
Mario Blaum,
James S. Plank,
Moshe Schwartz,
Eitan Yaakobi
Abstract:
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 p…
▽ More
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.
△ Less
Submitted 19 January, 2014;
originally announced January 2014.
-
Constrained Codes for Rank Modulation
Authors:
Sarit Buzaglo,
Eitan Yaakobi
Abstract:
Motivated by the rank modulation scheme, a recent work by Sala and Dolecek explored the study of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells.
In this paper, the model studied by Sala and Dolecek is extended into two constra…
▽ More
Motivated by the rank modulation scheme, a recent work by Sala and Dolecek explored the study of constraint codes for permutations. The constraint studied by them is inherited by the inter-cell interference phenomenon in flash memories, where high-level cells can inadvertently increase the level of low-level cells.
In this paper, the model studied by Sala and Dolecek is extended into two constraints. A permutation $σ\in S_n$ satisfies the \emph{two-neighbor $k$-constraint} if for all $2 \leq i \leq n-1$ either $|σ(i-1)-σ(i)|\leq k$ or $|σ(i)-σ(i+1)|\leq k$, and it satisfies the \emph{asymmetric two-neighbor $k$-constraint} if for all $2 \leq i \leq n-1$, either $σ(i-1)-σ(i) < k$ or $σ(i+1)-σ(i) < k$. We show that the capacity of the first constraint is $(1+ε)/2$ in case that $k=Θ(n^ε)$ and the capacity of the second constraint is 1 regardless to the value of $k$. We also extend our results and study the capacity of these two constraints combined with error-correction codes in the Kendall's $τ$ metric.
△ Less
Submitted 17 January, 2014;
originally announced January 2014.
-
Rank-Modulation Rewrite Coding for Flash Memories
Authors:
Eyal En Gad,
Eitan Yaakobi,
Anxiao,
Jiang,
Jehoshua Bruck
Abstract:
The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require…
▽ More
The current flash memory technology focuses on the cost minimization of its static storage capacity. However, the resulting approach supports a relatively small number of program-erase cycles. This technology is effective for consumer devices (e.g., smartphones and cameras) where the number of program-erase cycles is small. However, it is not economical for enterprise storage systems that require a large number of lifetime writes. The proposed approach in this paper for alleviating this problem consists of the efficient integration of two key ideas: (i) improving reliability and endurance by representing the information using relative values via the rank modulation scheme and (ii) increasing the overall (lifetime) capacity of the flash device via rewriting codes, namely, performing multiple writes per cell before erasure. This paper presents a new coding scheme that combines rank modulation with rewriting. The key benefits of the new scheme include: (i) the ability to store close to 2 bits per cell on each write with minimal impact on the lifetime of the memory, and (ii) efficient encoding and decoding algorithms that make use of capacity-achieving write-once-memory (WOM) codes that were proposed recently.
△ Less
Submitted 30 December, 2014; v1 submitted 3 December, 2013;
originally announced December 2013.
-
Systematic Codes for Rank Modulation
Authors:
Sarit Buzaglo,
Eitan Yaakobi,
Tuvi Etzion,
Jehoshua Bruck
Abstract:
The goal of this paper is to construct systematic error-correcting codes for permutations and multi-permutations in the Kendall's $τ$-metric. These codes are important in new applications such as rank modulation for flash memories. The construction is based on error-correcting codes for multi-permutations and a partition of the set of permutations into error-correcting codes. For a given large eno…
▽ More
The goal of this paper is to construct systematic error-correcting codes for permutations and multi-permutations in the Kendall's $τ$-metric. These codes are important in new applications such as rank modulation for flash memories. The construction is based on error-correcting codes for multi-permutations and a partition of the set of permutations into error-correcting codes. For a given large enough number of information symbols $k$, and for any integer $t$, we present a construction for ${(k+r,k)}$ systematic $t$-error-correcting codes, for permutations from $S_{k+r}$, with less redundancy symbols than the number of redundancy symbols in the codes of the known constructions. In particular, for a given $t$ and for sufficiently large $k$ we can obtain $r=t+1$. The same construction is also applied to obtain related systematic error-correcting codes for multi-permutations.
△ Less
Submitted 20 April, 2014; v1 submitted 27 November, 2013;
originally announced November 2013.
-
Correcting Grain-Errors in Magnetic Media
Authors:
Ryan Gabrys,
Eitan Yaakobi,
Lara Dolecek
Abstract:
This paper studies new bounds and constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin-Rao codes) can correct…
▽ More
This paper studies new bounds and constructions that are applicable to the combinatorial granular channel model previously introduced by Sharov and Roth. We derive new bounds on the maximum cardinality of a grain-error-correcting code and propose constructions of codes that correct grain-errors. We demonstrate that a permutation of the classical group codes (e.g., Constantin-Rao codes) can correct a single grain-error. In many cases of interest, our results improve upon the currently best known bounds and constructions. Some of the approaches adopted in the context of grain-errors may have application to other channel models.
△ Less
Submitted 30 April, 2018; v1 submitted 26 July, 2013;
originally announced July 2013.
-
Rewriting Codes for Flash Memories
Authors:
Eitan Yaakobi,
Hessam Mahdavifar,
Paul H. Siegel,
Alexander Vardy,
Jack K. Wolf
Abstract:
Flash memory is a non-volatile computer memory comprising blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes (or flash codes) and buffer codes - have been designed i…
▽ More
Flash memory is a non-volatile computer memory comprising blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes (or flash codes) and buffer codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure.
An (n,k,t)q flash code C is a coding scheme for storing k information bits in $n$ cells in such a way that any sequence of up to t writes can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of C, defined as δ(C) = n(q-1)-t, is a measure of how close the code comes to perfectly utilizing all these transitions. In this paper, we show a construction of flash codes with write deficiency O(qk\log k) if q \geq \log_2k, and at most O(k\log^2 k) otherwise.
An (n,r,\ell,t)q buffer code is a coding scheme for storing a buffer of r \ell-ary symbols such that for any sequence of t symbols it is possible to successfully decode the last r symbols that were written. We improve upon a previous upper bound on the maximum number of writes t in the case where there is a single cell to store the buffer. Then, we show how to improve a construction by Jiang et al. that uses multiple cells, where n\geq 2r.
△ Less
Submitted 28 October, 2012;
originally announced October 2012.
-
Coding for the Lee and Manhattan Metrics with Weighing Matrices
Authors:
Tuvi Etzion,
Alexander Vardy,
Eitan Yaakobi
Abstract:
This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conferenc…
▽ More
This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics. Two related packing problems will be considered. The first is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second is to transform the space in a way that volumes are preserved and each Lee sphere (or conscribed cross-polytope), in the space, will be transformed to a shape inscribed in a small cube.
△ Less
Submitted 11 December, 2012; v1 submitted 21 October, 2012;
originally announced October 2012.
-
Time-Space Constrained Codes for Phase-Change Memories
Authors:
Minghai Qin,
Eitan Yaakobi,
Paul H. Siegel
Abstract:
Phase-change memory (PCM) is a promising non-volatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells, to balance the heat both in time and space.
In this paper, we study the time…
▽ More
Phase-change memory (PCM) is a promising non-volatile solid-state memory technology. A PCM cell stores data by using its amorphous and crystalline states. The cell changes between these two states using high temperature. However, since the cells are sensitive to high temperature, it is important, when programming cells, to balance the heat both in time and space.
In this paper, we study the time-space constraint for PCM, which was originally proposed by Jiang et al. A code is called an \emph{$(α,β,p)$-constrained code} if for any $α$ consecutive rewrites and for any segment of $β$ contiguous cells, the total rewrite cost of the $β$ cells over those $α$ rewrites is at most $p$. Here, the cells are binary and the rewrite cost is defined to be the Hamming distance between the current and next memory states. First, we show a general upper bound on the achievable rate of these codes which extends the results of Jiang et al. Then, we generalize their construction for $(α\geq 1, β=1,p=1)$-constrained codes and show another construction for $(α= 1, β\geq 1,p\geq1)$-constrained codes. Finally, we show that these two constructions can be used to construct codes for all values of $α$, $β$, and $p$.
△ Less
Submitted 18 July, 2012;
originally announced July 2012.
-
Gaussian Content as a Laser Beam Quality Parameter
Authors:
Shlomo Ruschin,
Elad Yaakobi,
Eyal Shekel
Abstract:
We propose the Gaussian Content as an optional quality parameter for the characterization of laser beams. It is defined as the overlap integral of a given field with an optimally defined Gaussian. The definition is specially suited for applications where coherence properties are targeted. Mathematical definitions and basic calculation procedures are given along with results for basic beam profiles…
▽ More
We propose the Gaussian Content as an optional quality parameter for the characterization of laser beams. It is defined as the overlap integral of a given field with an optimally defined Gaussian. The definition is specially suited for applications where coherence properties are targeted. Mathematical definitions and basic calculation procedures are given along with results for basic beam profiles. The coherent combination of an array of laser beams and the optimal coupling between a diode laser and a single-mode fiber (SMF) are elaborated as application examples. The measurement of the Gaussian Content and its conservation upon propagation are experimentally confirmed.
△ Less
Submitted 8 May, 2011;
originally announced May 2011.
-
Dense Error-Correcting Codes in the Lee Metric
Authors:
Tuvi Etzion,
Alexander Vardy,
Eitan Yaakobi
Abstract:
Several new applications and a number of new mathematical techniques have increased the research on error-correcting codes in the Lee metric in the last decade. In this work we consider several coding problems and constructions of error-correcting codes in the Lee metric. First, we consider constructions of dense error-correcting codes in relatively small dimensions over small alphabets. The secon…
▽ More
Several new applications and a number of new mathematical techniques have increased the research on error-correcting codes in the Lee metric in the last decade. In this work we consider several coding problems and constructions of error-correcting codes in the Lee metric. First, we consider constructions of dense error-correcting codes in relatively small dimensions over small alphabets. The second problem we solve is construction of diametric perfect codes with minimum distance four. We will construct such codes over various lengths and alphabet sizes. The third problem is to transfer an n-dimensional Lee sphere with large radius into a shape, with the same volume, located in a relatively small box. Hadamard matrices play an essential role in the solutions for all three problems. A construction of codes based on Hadamard matrices will start our discussion. These codes approach the sphere packing bound for very high rate range and appear to be the best known codes over some sets of parameters.
△ Less
Submitted 2 April, 2010;
originally announced April 2010.
-
Storage Coding for Wear Leveling in Flash Memories
Authors:
Anxiao,
Jiang,
Robert Mateescu,
Eitan Yaakobi,
Jehoshua Bruck,
Paul H. Siegel,
Alexander Vardy,
Jack K. Wolf
Abstract:
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine b…
▽ More
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell is implemented as either NAND or NOR floating gate. NAND flash is currently the most widely used type of flash memory. In a NAND flash memory, every block of cells consists of numerous pages; rewriting even a single page requires the whole block to be erased and reprogrammed. Block erasures determine both the longevity and the efficiency of a flash memory. Therefore, when data in a NAND flash memory are reorganized, minimizing the total number of block erasures required to achieve the desired data movement is an important goal. This leads to the flash data movement problem studied in this paper. We show that coding can significantly reduce the number of block erasures required for data movement, and present several optimal or nearly optimal data-movement algorithms based upon ideas from coding theory and combinatorics. In particular, we show that the sorting-based (non-coding) schemes require at least O(nlogn) erasures to move data among n blocks, whereas coding-based schemes require only O(n) erasures. Furthermore, coding-based schemes use only one auxiliary block, which is the best possible, and achieve a good balance between the number of erasures in each of the n+1 blocks.
△ Less
Submitted 20 November, 2009;
originally announced November 2009.
-
High Dimensional Error-Correcting Codes
Authors:
Eitan Yaakobi,
Tuvi Etzion
Abstract:
In this paper we construct multidimensional codes with high dimension. The codes can correct high dimensional errors which have the form of either small clusters, or confined to an area with a small radius. We also consider small number of errors in a small area. The clusters which are discussed are mainly spheres such as semi-crosses and crosses. Also considered are clusters with small number o…
▽ More
In this paper we construct multidimensional codes with high dimension. The codes can correct high dimensional errors which have the form of either small clusters, or confined to an area with a small radius. We also consider small number of errors in a small area. The clusters which are discussed are mainly spheres such as semi-crosses and crosses. Also considered are clusters with small number of errors such as 2-bursts, two errors in various clusters, and three errors on a line. Our main focus is on the redundancy of the codes when the most dominant parameter is the dimension of the code.
△ Less
Submitted 26 April, 2010; v1 submitted 29 October, 2009;
originally announced October 2009.
-
A Nearly Optimal Construction of Flash Codes
Authors:
Hessam Mahdavifar,
Paul H. Siegel,
Alexander Vardy,
Jack K. Wolf,
Eitan Yaakobi
Abstract:
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maxi…
▽ More
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different values or levels. While increasing the cell level is easy, reducing the level of a cell can be accomplished only by erasing an entire block. Since block erasures are highly undesirable, coding schemes - known as floating codes or flash codes - have been designed in order to maximize the number of times that information stored in a flash memory can be written (and re-written) prior to incurring a block erasure. An (n,k,t)_q flash code C is a coding scheme for storing k information bits in n cells in such a way that any sequence of up to t writes (where a write is a transition 0 -> 1 or 1 -> 0 in any one of the k bits) can be accommodated without a block erasure. The total number of available level transitions in n cells is n(q-1), and the write deficiency of C, defined as δ(C) = n(q-1) - t, is a measure of how close the code comes to perfectly utilizing all these transitions. For k > 6 and large n, the best previously known construction of flash codes achieves a write deficiency of O(qk^2). On the other hand, the best known lower bound on write deficiency is Ω(qk). In this paper, we present a new construction of flash codes that approaches this lower bound to within a factor logarithmic in k. To this end, we first improve upon the so-called "indexed" flash codes, due to Jiang and Bruck, by eliminating the need for index cells in the Jiang-Bruck construction. Next, we further increase the number of writes by introducing a new multi-stage (recursive) indexing scheme. We then show that the write deficiency of the resulting flash codes is O(qk\log k) if q \geq \log_2k, and at most O(k\log^2 k) otherwise.
△ Less
Submitted 10 May, 2009;
originally announced May 2009.
-
Multidimensional Flash Codes
Authors:
Eitan Yaakobi,
Alexander Vardy,
Paul H. Siegel,
Jack K. Wolf
Abstract:
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different levels corresponding to the number of electrons it contains. Increasing the cell level is easy; however, reducing a cell level forces all the other cells in the same block to be erased. This erasing operation is undesirable and therefore has to be used as infrequently as possibl…
▽ More
Flash memory is a non-volatile computer memory comprised of blocks of cells, wherein each cell can take on q different levels corresponding to the number of electrons it contains. Increasing the cell level is easy; however, reducing a cell level forces all the other cells in the same block to be erased. This erasing operation is undesirable and therefore has to be used as infrequently as possible. We consider the problem of designing codes for this purpose, where k bits are stored using a block of n cells with q levels each. The goal is to maximize the number of bit writes before an erase operation is required. We present an efficient construction of codes that can store an arbitrary number of bits. Our construction can be viewed as an extension to multiple dimensions of the earlier work of Jiang and Bruck, where single-dimensional codes that can store only 2 bits were proposed.
△ Less
Submitted 3 April, 2009; v1 submitted 6 January, 2009;
originally announced January 2009.
-
Error-Correction of Multidimensional Bursts
Authors:
Tuvi Etzion,
Eitan Yaakobi
Abstract:
In this paper we present several constructions to generate codes for correcting a multidimensional cluster-error. The goal is to correct a cluster-error whose shape can be a box-error, a Lee sphere error, or an error with an arbitrary shape. Our codes have very low redundancy, close to optimal, and large range of parameters of arrays and clusters. Our main results are summarized as follows: 1) A…
▽ More
In this paper we present several constructions to generate codes for correcting a multidimensional cluster-error. The goal is to correct a cluster-error whose shape can be a box-error, a Lee sphere error, or an error with an arbitrary shape. Our codes have very low redundancy, close to optimal, and large range of parameters of arrays and clusters. Our main results are summarized as follows: 1) A construction of two-dimensional codes capable to correct a rectangular-error with considerably more flexible parameters from previously known constructions. Another advantage of this construction is that it is easily generalized for D dimensions. 2) A novel method based on D colorings of the D-dimensional space for constructing D-dimensional codes correcting D-dimensional cluster-error of various shapes. This method is applied efficiently to correct a D-dimensional cluster error of parameters not covered efficiently by previous onstructions. 3) A transformation of the D-dimensional space into another D-dimensional space such that a D-dimensional Lee sphere is transformed into a shape located in a D-dimensional box of a relatively small size. We use the previous constructions to correct a D-dimensional error whose shape is a D-dimensional Lee sphere. 4) Applying the coloring method to correct more efficiently a two-dimensional error whose shape is a Lee sphere. The D-dimensional case is also discussed. 5) A construction of one-dimensional codes capable to correct a burst-error of length b in which the number of erroneous positions is relatively small compared to b. This construction is generalized for D-dimensional codes. 6) Applying the constructions correcting a Lee sphere error and a cluster-error with small number of erroneous positions, to correct an arbitrary cluster-error.
△ Less
Submitted 26 December, 2007;
originally announced December 2007.