We consider the repair problem for Reed–Solomon (RS) codes, evaluated on an$\mathbb {F}_{q}$-linear subspace$U\subseteq \mathbb {F}_{q^{m}} $of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb {F}_{q}$is the Galois field of size$q$. For$q>2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}$,$s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb {F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least$1/3$) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme. Our result extend the construction of Dau–Milenkovic to the range$r < m-s$, for a wide range of parameters.

We consider the repair problem for Reed-Solomon (RS) codes, evaluated on an$\mathbb{F}_{q}$-linear subspace$U \subseteq \mathbb{F}_{q^{m}}$of dimension$d$, where$q$is a prime power,$m$is a positive integer, and$\mathbb{F}_{q}$is the Galois field of size$q$. For$q > 2$, we show the existence of a linear repair scheme for the RS code of length$n=q^{d}$and codimension$q^{s}, s < d$, evaluated on$U$, in which each of the$n-1$surviving nodes transmits only$r$symbols of$\mathbb{F}_{q}$, provided that$ms\geq d(m-r)$. For the case$q=2$, we prove a similar result, with some restrictions on the evaluation linear subspace$U$. Our proof is based on a probabilistic argument, however the result is not merely an existence result; the success probability is fairly large (at least 1/3) and there is a simple criterion for checking the validity of the randomly chosen linear repair scheme.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch is required to write n incoming packets and read k outgoing packets while using m memory banks, each able to write and read one packet per time unit. Each set of n packets written to the switch simultaneously is called a generation. The objective is to store the packets in the banks such that every request of k packets, which can belong to previous generations, can be handled by reading at most one packet from every bank. In this paper, we study a new type of switch codes that can simultaneously deliver large packet request and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model, we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. For binary codes, we also study an intermediate model in which a coded packet is formed by the XOR operations of at most two input packets. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Finally, we introduce a construction of conventional switch codes, which improves upon the best known results for the case n = k.

Defined through a certain 2 × 2 matrix called Arikan's kernel, polar codes are known to achieve the symmetric capacity of binary-input discrete memoryless channels under the successive cancellation (SC) decoder. Yet, for short block-lengths, polar codes fail to deliver a compelling performance under the low complexity SC decoding scheme. Recent studies provide evidence for improved performance when Arikan's kernel is replaced with larger kernels that have smaller scaling exponents. However, for ℓ×ℓ kernels the time complexity of the SC decoding increases by a factor of 2ℓ. In this paper we study a special type of kernels called permuted kernels. The advantage of these kernels is that the SC decoder for the corresponding polar codes can be viewed as a permuted version of the SC decoder for the conventional polar codes that are defined through Arikan's kernel. This permuted successive cancellation (PSC) decoder outputs its decisions on the input bits according to a permuted order of their indices. We introduce an efficient PSC decoding algorithm and show simulations for two 16 × 16 permuted kernels that have better scaling exponents than Arikan's kernel.

A constrained code is a set of finite-length codewords that entirely avoid the occurrences of certain patterns. In some applications, it may be preferable to merely limit the number of occurrences of certain patterns in codewords rather than to completely forbid them. Constrained codes that involve such weaker constraints are called weakly constrained codes. In this paper we construct capacity-achieving weakly constrained codes. The construction is based on a row-by-row coding scheme in which messages are encoded into the rows of a 2-dimensional array in which the frequency of occurrence of patterns along columns is controlled.

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In single-level cell (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by applying conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this paper, a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order is presented. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a weak constraint on vertical 1 0 1 patterns with a systematic error-correcting code, that can mitigate vertical ICI errors while achieving a higher overall coding rate, provided that the vertical ICI error probability is sufficiently small. Some extensions for multi-level cell (MLC) flash memory are discussed as well.

Switch codes, first proposed by Wang et al., are codes that are designed to increase the parallelism of data writing and reading processes in network switches. A network switch consists of n input ports, k output ports, and m banks which store new arriving packets from the input ports in each time slot, called a generation. The objective is to store the packets in the banks such that every request of k packets by the output ports, which can be from previous generations, can be handled by reading at most one packet from every bank. In this paper we study a new type of switch codes that can simultaneously deliver large symbol requests and good coding rate. These attractive features are achieved by relaxing the request model to a natural sub-class we call consecutive requests. For this new request model we define a new type of codes called consecutive switch codes. These codes are studied in both the computational and combinatorial models, corresponding to whether the data can be encoded or not. We present several code constructions and prove the optimality of one family of these codes by providing the corresponding lower bound. Lastly, we introduce a construction of switch codes for the case n = k, which improves upon the best known results for this case.

Motivated by the rank modulation scheme, a recent study by Sala and Dolecek explored the idea 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 lowlevel cells. A permutation σ ∈ Snsatisfies the single-neighbor k-constraint if |σ(i + 1) - σ (i)| ≤ k for all 1 ≤ i ≤ n - 1. In this paper, this model is extended into two constraints. A permutation σ ∈ Snsatisfies the two-neighbor k-constraint if for all 2 ≤ i ≤ n-1, |σ(i)-σ(i-1)| ≤ k or |σ(i + 1)-σ(i)|≤k, and it satisfies the asymmetric two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1, σ(i - 1) - σ(i)ϵ) and the capacity of the second constraint is 1 regardless for any positive k. We also extend our results and study the capacity of these two constraints combined with error-correcting codes in the Kendall τ-metric.

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.

Inter-cell interference (ICI) is a significant cause of errors in flash memories. In two-level (SLC) flash memory, ICI arises when 1 0 1 patterns are programmed either in the horizontal or vertical directions. Since data pages are written sequentially in horizontal wordlines, one can mitigate the effects of horizontal ICI by use of conventional constrained codes that forbid the 1 0 1 pattern. This approach does not address the problem of vertical ICI, however. In this work, we present a row-by-row coding technique that eliminates vertical 1 0 1 patterns while preserving the sequential wordline programming order. This scheme, though efficient, necessarily suffers a rate loss of almost 20%. We therefore propose another coding scheme, combining a relaxed constraint on vertical 1 0 1 patterns with a systematic error correcting code, that can mitigate vertical ICI errors while achieving a higher overall code rate, provided that the vertical ICI error probability is sufficiently small.

The rank modulation scheme has been proposed for efficient writing and storing data in nonvolatile memory storage. Error correction in the rank modulation scheme is done by considering permutation codes. In this paper, we consider codes in the set of all permutations on n elements, Sn, using the Kendall τ-metric. The main goal of this paper is to derive new bounds on the size of such codes. For this purpose, we also consider perfect codes, diameter perfect codes, and the size of optimal anticodes in the Kendall τ-metric, structures which have their own considerable interest. We prove that there are no perfect single-error-correcting codes in Sn, where n>4 is a prime or 4≤n≤10 . We present lower bounds on the size of optimal anticodes with odd diameter. As a consequence, we obtain a new upper bound on the size of codes in Snwith even minimum Kendall τ-distance. We present larger single-error-correcting codes than the known ones in S5and S7.

The rank modulation scheme has been proposed for efficient writing and storing data in non-volatile memory storage. Error-correction in the rank modulation scheme is done by considering permutation codes. In this paper we consider codes in the set of all permutations on n elements, Sn, using the Kendall's τ-metric. We prove that there are no perfect single-error-correcting codes in Sn, where n > 4 is a prime or 4 ≤ n ≤ 10. We also prove that if such a code exists for n which is not a prime then the code should have some uniform structure. We define some variations of the Kendall's τ-metric and consider the related codes and specifically we prove the existence of a perfect single-error-correcting code in S5. Finally, we examine the existence problem of diameter perfect codes in Snand obtain a new upper bound on the size of a code in Snwith even minimum Kendall's τ-distance.

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 σ ∈ Snsatisfies the two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1 either |σ(i - 1) - σ(i)| ≤ k or |σ(i) - σ(i + 1)| ≤ k, and it satisfies the asymmetric two-neighbor k-constraint if for all 2 ≤ i ≤ n - 1, either σ(i-1)-σ(i)ε) 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.

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 Sk+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.

Multipermutations appear in various applications in information theory. New applications such as rank modulation for flash memories and voting have suggested the need to consider error-correcting codes for multipermutations. The construction of codes is challenging when permutations are considered and it becomes even a harder problem for multipermutations. In this paper we discuss the general problem of error-correcting codes for multipermutations. We present some tight bounds on the size of error-correcting codes for several families of multipermutations. We find the capacity of the channels of multipermutations and characterize families of perfect codes in this metric which we believe are the only such perfect codes.

The existence question for tiling of the $n$-dimensional Euclidian space by crosses is well known. A few existence and nonexistence results are known in the literature. Of special interest are tilings of the Euclidian space by crosses with arms of length one, also known as Lee spheres with radius one. Such a tiling forms a perfect code. In this paper crosses with arms of length half are considered. These crosses are scaled by two to form a discrete shape. A tiling with this shape is also known as a perfect dominating set. We prove that an integer tiling for such a shape exists if and only if $n=2^t-1$ or $n=3^t-1$, where $t>0$. A strong connection of these tilings to binary and ternary perfect codes in the Hamming scheme is shown.

Ann-dimensional chair consists of ann-dimensional box from which a smallern-dimensional box is removed. A tiling of ann-dimensional chair has two nice applications in some memories using asymmetric codes. The first one is in the design of codes that correct asymmetric errors with limited magnitude. The second one is in the design ofncellsq-ary write-once memory codes. We show an equivalence between the design of a tiling with an integer lattice and the design of a tiling from a generalization of splitting (or of Sidon sequences). A tiling of ann-dimensional chair can define a perfect code for correcting asymmetric errors with limited magnitude. We present constructions for such tilings and prove cases where perfect codes for these type of errors do not exist.

Let P be a set of n points in the plane and let C be a family of simple closed curves in the plane each of which avoids the points of P. For every curve C ∈ C we denote by disc(C) the region in the plane bounded by C. Fix an integer s > 0 and assume that every two curves in C intersect at most s times and that for every two curves C,C' ∈ C the intersection disc(C) ∩ disc(C') is a connected set. We consider the family F = {P ∩ disc(C) | C ∈ C}. When s is even, we provide sharp bounds, in terms of n, s, and k, for the number of sets in F of cardinality k, assuming that ∩C ∈Cdisc(C) is nonempty. In particular, we provide sharp bounds for the number of halving pseudo-parabolas for a set of n points in the plane. Finally, we consider the VC-dimension of F and show that F has VC-dimension at most s+1.