Binary self-dual sequences have been considered and analyzed throughout the years, and they have been used for various applications. Motivated by a construction for single-track Gray codes, we examine the structure and recursive constructions for binary and non-binary self-dual sequences. The feedback shift registers that generate such sequences are discussed. The connections between these sequences and maximum period single-track codes are also discussed. Maximum period non-binary single-track Gray codes of length $p^t$ and period $p^{p^t}$ are constructed. These are the first infinite families of maximum period codes presented in the literature.

pseudo-random array is a two-dimensional array in which eachn1×n2nonzero matrix is contained exactly once as a window in the array. The pseudo-random arrays we consider have many desirable properties in addition, such as the shift-and-add-property, i.e., the addition of the array to any of its nontrivial shifts is another nontrivial shift of the array. A pseudorandom array code is a linear code ofr1×r2arrays in which eachn1×n2nonzero matrix is contained exactly once as a window in one of the arrays. In this paper, new parameters for pseudo-random arrays are presented, and their construction is generalized to pseudo-random array codes. Our constructions of pseudo-random array codes are based on the folding of sequences. Two techniques to verify whether an array or a set of arrays constructed by folding is a pseudo-random array or a pseudo-random array code, respectively, are presented. These verification techniques can also be used for VLSI testing.

Nearly perfect covering codes are covering codes that meet the van Wee lower bound on their size. This work studies such codes with covering radius 1. It is shown that the set of these codes can be partitioned into three families, depending on the distribution of the Hamming distances between neighboring codewords. General properties of these code families are presented, including a characterization of their weight and distance distributions. Constructions of codes for each of the families are presented. Finally, extended perfect covering codes are considered. Their punctured codes yield a variety of nearly perfect covering codes.

Pseudo-random arrays are the two-dimensional analog of M-sequences. Pseudo-random array codes are the twodimensional analog of sequences generated by a product of irreducible polynomials with the same exponent. The union of the arrays in such a code has the window property and the shift-and-add property, implying that these codes are linear. The folding technique is the most basic one for forming such arrays and codes. A new criterion for generating pseudo-random arrays based on folding is given. This new criterion yields pseudo-random arrays with new parameters. A general construction for such array codes is given. It appears that the arrays generated in this construction can be constructed by folding the nonzero sequences generated by a product of irreducible polynomials of the same degree and the same exponent. Two hierarchies of the pseudo-random array codes are provided. In one hierarchy codewords of one code with smaller windows are contained in codewords of another code which stands above him in the hierarchy. The second hierarchy is a partition of the pseudo-random array codes generated by folding into classes based on the polynomial types which participate in their construction.

Abstract An ( n , R )-covering sequence is a cyclic sequence whose consecutive n -tuples form a code of length n and covering radius R . Using several construction methods improvements of the upper bounds on the length of such sequences for $$n \le 20$$ n ≤ 20 and $$1 \le R \le 3$$ 1 ≤ R ≤ 3 , are obtained. The definition is generalized in two directions. An ( n , m , R )-covering sequence code is a set of cyclic sequences of length m whose consecutive n -tuples form a code of length n and covering radius R . The definition is also generalized to arrays in which the $$m \times n$$ m × n sub-matrices form a covering code with covering radius R . We prove that asymptotically there are covering sequences that attain the sphere-covering bound up to a constant factor.

Nearly perfect packing codes are those codes that meet the Johnson upper bound on the size of errorcorrecting codes. This bound is an improvement to the sphere-packing bound. A related bound for covering codes is known as the van Wee bound. Codes that meet this bound will be called nearly perfect covering codes. In this paper, such codes with covering radius one will be considered. It will be proved that these codes can be partitioned into three families depending on the smallest distance between neighboring codewords. Some of the codes contained in these families will be completely characterized. Other properties of these codes will be considered too. Construction for codes for each such family will be presented, the weight distribution and the distance distribution of codes from these families are characterized. Finally, extended nearly perfect covering code will be considered and unexpected equivalence classes of codes of the three types will be defined based on the extended codes.

Temperature control is of utmost importance in transmission systems. In this paper, a binary channel model is considered in which the transmission of a one causes a temperature increase while communicating a zero causes a temperature drop. By putting constraints on the input sequences, it is guaranteed that the channel temperature will not exceed a certain pre-determined maximum. In the asymptotic regime, the capacity of such a channel is studied. For the non-asymptotic regime, fixed-length codes are presented, with the property that codewords can be freely cascaded without violating the temperature constraint. Optimization of the code size is investigated and codewords are enumerated using generating functions.

A de Bruijn array code is a set of$r \times s$binary doubly-periodic arrays such that each binary$n \times m$matrix is contained exactly once as a window in one of the arrays. Such a set of arrays can be viewed as a two-dimensional generalization of a perfect factor in the de Bruijn graph. Necessary conditions for the existence of such codes are proved. Several direct constructions and recursive constructions for such arrays are presented. A framework for a theory of two-dimensional feedback shift registers which is akin to (one-dimensional) feedback shift registers is suggested in the process.

Enzymatic DNA labeling is a powerful tool with applications in biochemistry, molecular biology, biotechnology, medical science, and genomic research. This paper contributes to the evolving field of DNA-based data storage by presenting a formal framework for modeling DNA labeling in strings, specifically tailored for data storage purposes. Our approach involves a known DNA molecule as a template for labeling, employing patterns induced by a set of designed labels to represent information. One hypothetical implementation can use CRISPR-Cas9 and gRNA reagents for labeling. Various aspects of the general labeling channel, including fixed-length labels, are explored, and upper bounds on the maximal size of the corresponding codes are given. The study includes the development of an efficient encoder-decoder pair that is proven optimal in terms of maximum code size under specific conditions.

Motivated by distributed algorithms for fuzzy joins, the concept of pair-covering${}^{\prime\prime}$codes is defined. This definition is a generalization of the well-known concept of covering codes. Basic properties and bounds for the pair-covering codes with comparison to the associated properties and bounds for covering codes, are provided. In particular, the sphere covering bound and normal codes are generalized.

To measure repair latency at helper nodes, we introduce a new metric called skip cost that quantifies the number of contiguous sections accessed on a disk. We provide explicit constructions of zigzag codes and fractional repetition codes that incur zero skip cost.

An$(m, n, R)-\mathbf{de}$Bruijn covering array (dBCA) is a doubly periodic$M\times N$array over an alphabet of size$q$such that the set of all its$m\times n$windows form a covering code with radius$R$. An upper bound of the smallest array area of an$(m, n, R)-\mathbf{dBCA}$is provided using a probabilistic technique which is similar to the one that was used for an upper bound on the length of a de Bruijn covering sequence. A folding technique to construct a dBCA from a de Bruijn covering sequence or de Bruijn covering sequences code is presented. Several new constructions that yield shorter de Bruijn covering sequences and$(m, n, R)-\mathbf{dBCAs}$with smaller areas are also provided. These constructions are mainly based on sequences derived from cyclic codes, self-dual sequences, primitive polynomials, an interleaving technique, folding, and mutual shifts of sequences with the same covering radius. Finally, constructions of de Bruijn covering sequences codes are also discussed.

The thermal-aware channel has been studied recently to control the temperature of some electronic devices for better performance and longer lifetime. In this work, we consider a thermal-aware channel model where multiple wires are available to the user. The user can use one wire or several wires to write an information word. Particularly, we study the two extreme cases. In the first case, only one wire is permitted for writing the information. The other extreme case is that we are allowed to write information on all the wires in parallel. In the first case, when we send a message through a wire that reaches the highest allowed temperature, we switch to another available wire. We determine the minimum number of wires required to send any arbitrary message. Given the number of wires, our second task is to determine the constrained codewords that can be sent through these wires. We compute the maximum information rate achieved and provide some constructions of codes satisfying these constraints. In the second case when all the wires are available for writing many, interesting questions arise and we briefly describe one of them and its solutions.

Pseudo-random arrays and perfect maps are the two-dimensional analogs of M-sequences and de Bruijn sequences, respectively. We modify the definitions to be applied to codes. These codes are also the two-dimensional analogs of certain factors in the de Bruijn graph. These factors are called zero factors and perfect factors in the de Bruijn graph. We apply a folding technique to construct pseudo-random array codes and examine the minimum distance of the constructed codes. The folding is applied on sequences generated from irreducible polynomials or a product of irreducible polynomials with the same degree and the same exponent. Direct and recursive constructions for de Bruijn array codes are presented and discussed.

We generalize the problem of recovering a lost/erased symbol in a Reed-Solomon code to the scenario in which some side information about the lost symbol is known. The side information is represented as a set$S$of linearly independent combinations of the sub-symbols of the lost symbol. When$S=\varnothing$, this reduces to the standard problem of repairing a single codeword symbol. When$S$is a set of sub-symbols of the erased one, this becomes the repair problem with partially lost/erased symbol. We first establish that the minimum repair bandwidth depends on$\vert S\vert$and not the content of$S$and construct a lower bound on the repair bandwidth of a linear repair scheme with side information$S$We then consider the well-known subspace-polynomial repair schemes and show that their repair bandwidths can be optimized by choosing the right subspaces. Finally, we demonstrate several parameter regimes where the optimal bandwidths can be achieved for full-length Reed-Solomon codes.

One of the primary sequencing methods gaining prominence in DNA storage is nanopore sequencing, attributed to various factors. In this work, we consider a simplified model of the sequencer, characterized as a channel. This channel takes a sequence and processes it using a sliding window of length$\ell$, shifting the window by$\delta$characters each time. The output of this channel, which we refer to as the read vector, is a vector containing the sums of the entries in each of the windows. The capacity of the channel is defined as the maximal information rate of the channel. Previous works have already revealed capacity values for certain parameters$\ell$and$\delta$. In this work, we show that when$\delta < \ell < 2\delta$, the capacity value is given by$\frac{1}{\delta}\log_{2}\frac{1}{2}(\ell+1+ \sqrt{(\ell+1)^{2}-4(\ell-\delta)(\ell-\delta+1)})$. Additionally, we construct an upper bound when$2\delta < \ell$. Finally, we extend the model to the two-dimensional case and present several results on its capacity.

Recovery sets for vectors and subspaces are important in the construction of distributed storage system codes. These concepts are also interesting in their own right. In this paper, we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets for each recovered element? The recovered elements in this work ared-dimensional subspaces of ak-dimensional vector space over$\mathbb {F}_{q}$. Each server stores one representative for each distinct one-dimensional subspace of thek-dimensional vector space, or equivalently a distinct point of PG$(k-1,q)$. As column vectors, the associated vectors of the stored one-dimensional subspaces form the generator matrix of the$[(q^{k} -1)/(q-1),k,q^{k-1}]$simplex code over$\mathbb {F}_{q}$. Lower bounds and upper bounds on the maximum number of such recovery sets are provided. It is shown that generally, these bounds are either tight or very close to being tight.

The Invertible Bloom Lookup Table (IBLT) is a probabilistic data structure for set representation, with applications in network and traffic monitoring. It is known for its ability to list its elements, an operation that succeeds with high probability for sufficiently large table. However, listing can fail even for relatively small sets. This paper extends recent work on the worst-case analysis of IBLT, which guarantees successful listing for all sets of a certain size, by introducing more general IBLT schemes. These schemes allow for greater freedom in the implementation of the insert, delete, and listing operations and demonstrate that the IBLT memory can be reduced while still maintaining successful listing guarantees. The paper also explores the time-memory trade-off of these schemes, some of which are based on linear codes and Bh-sequences over finite fields.

High temperatures in electronic devices have a negative effect on their performance. Various techniques have been proposed and studied to address and combat this thermal challenge. To guarantee that the peak temperature of the devices will be bounded by some maximum temperature, the transmitted signal has to satisfy some constraints.With this motivation, we study the constrained channel that only accepts sequences that satisfy prescribed thermal constraints. The main goal in this paper is to compute the capacity of this channel. We provide the exact capacity of the channel with some certain parameters and we also present some bounds on the capacity in various cases.Finally, we consider the model that multiple wires are available to use and find out the smallest number of wires required to satisfy the thermal constraints.

The rapid development of DNA storage has brought the deletion and insertion channel to the front line of research. When the number of deletions is equal to the number of insertions, theFixed Length Levenshtein(FLL) metric is the right measure for the distance between two words of the same length. Similar to any other metric, the size of a ball is one of the most fundamental parameters. In this work, we consider the minimum, maximum, and average size of a ball with radius one, in the FLL metric. The related minimum and the maximum size of a maximal anticode with diameter one are also considered.

Balanced sequences and balanced codes have attracted a lot of research in the last seventy years due to their diverse applications in information theory as well as other areas of computer science and engineering. There have been some methods to classify balanced sequences. This work suggests two new different hierarchies to classify these sequences. The first one is based on the largest$\ell $for which each$\ell $-tuple is contained the same amount of times in the sequence. This property is a generalization for the property required for de Bruijn sequences. The second hierarchy is based on the number of balanced derivatives of the sequence. Enumeration for each such family of sequences and efficient encoding and decoding algorithms are provided in this paper.

de Bruijn sequences of order ℓ, i.e., sequences that contain each ℓ-tuple as a window exactly once, have found many diverse applications in information theory and most recently in DNA storage. This family of binary sequences has asymptotic rate of 1/2. To overcome this low rate, we study ℓ-tuples covering sequences, which impose that each ℓ-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that ℓ is a function of the sequence length n. Lower and upper bounds on the asymptotic rate of this family are given. Moreover, we study an upper bound for ℓ such that the redundancy of the set of ℓ-tuples covering sequences is at most a single symbol. We present an efficient encoding and decoding schemes for ℓ-tuples covering sequences that meet this bound.

Diameter perfect codes form a natural generalization for perfect codes. They are based on the code-anticode bound which generalizes the sphere-packing bound. The code-anticode bound was proved by Delsarte for distance-regular graphs and it holds for some other metrics too. In this paper we prove the bound for non-binary constant-weight codes with the Hamming metric and characterize the diameter perfect codes and the maximum size anticodes for these codes. We distinguish between six families of non-binary diameter constant-weight codes and four families of maximum size non-binary constant-weight anticodes. Each one of these families of diameter perfect codes raises some different questions. We consider some of these questions and leave lot of ground for further research. Finally, as a consequence, some$t$-intersecting families related to the well-known Erdös-Ko-Rado theorem, are constructed.

The rapid development of DNA storage has brought the deletion and insertion channel, once again, to the front line of research. When the number of deletions is equal to the number of insertions, the Fixed Length Levenshtein$(FLL)$metric is the right measure for the distance between two words of the same length. The size of a ball is one of the most fundamental parameters in any metric. The size of the ball with radius one in the FLL metric depends on the number of runs and the length of the alternating segments of the given word. In this work, we find the minimum, maximum, and average size of a ball with radius one, in the FLL metric. The related minimum and maximum sizes of a maximal anticode with diameter one are also calculated.

A multiset combinatorial batch code (MCBC) over vector space consists of a set of subspaces of$\mathbb{F}_{q}^{n}$, each corresponding to a server, such that requests consisting of$t$dimensional subspaces, can be retrieved from the servers. The code is said to be regular if all the subspaces in the code have the same dimension. The aim is to find the minimum number of total storage, and also the minimum number of servers in the regular case, fixing other parameters. In this paper, we provide bounds and constructions for this new class of batch codes.

The de Bruijn graph and its sequences have found many diverse applications in information theory as well as other areas of computer science and engineering such as interconnection networks, VLSI decomposition, and most recently in DNA storage. Binary balanced sequences have also been a subject to a large research during the last forty years with various applications and a lot of interest in information theory. There have been some works on classification of balanced sequences mainly based on their spectral-null order. This work generalizes the concept of de Bruijn sequences, based on the de Bruijn graph of order$\ell$, where each edge is multiplied to a fixed number of multiple edges. This implies that in the sequences derived from the generalized graph each l-tuple has the same multiplicity. Using this generalization we form an interesting hierarchy between balanced sequences. Furthermore, another hierarchy is given by the derivatives of balanced sequences. Enumeration for each such family of sequences and efficient encoding and decoding algorithms are also provided.

Thede Bruijn graph, its sequences, and their various generalizations, have found many applications in information theory, including many new ones in the last decade. In this paper, motivated by a coding problem for emerging memory technologies, a set of sequences which generalize the window property of de Bruijn sequences, on its shorter subsequences, are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be calledlocally-constrained de Bruijn sequencesand a set of such sequences will be called alocally-constrained de Bruijn code. Several properties and alternative definitions for such codes are examined and they are analyzed as generalized sequences in the de Bruijn graph (and its generalization) and as constrained sequences. Various enumeration techniques are used to compute the total number of sequences for any given set of parameters. A construction method of such codes from the theory of shift-register sequences is proposed. Finally, we show how these locally-constrained de Bruijn sequences and codes can be applied in constructions of codes for correcting synchronization errors in the$\ell $-symbol read channel and in the racetrack memory channel. For this purpose, these codes are superior in their size to previously known codes.

Aprivate proximity retrieval(PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance$r$from the user’s record$x$. The user’sprivacyat each server is given by the fraction of the record$x$that is kept private. In this paper, this research is initiated and protocols that offer trade-offs between privacy, computational complexity, and storage are studied. In particular, we assume that each server stores a copy of the database and study the required minimum number of servers by our protocol which provides a given privacy level. Each server receives a query in the protocol and the set of queries forms a code. The main focus in the paper is dedicated to studying the family of codes generated by the set of queries. These codes will be shown to satisfy a specific covering property and will be calledprivate proximity retrieval intersection covering codes. In particular, since the query every server receives is a codeword, the goal is to minimize the number of codewords in such a code which is the minimum number of servers required by the protocol. These codes are closely related to a family of codes known ascovering designs. We introduce several lower bounds on the sizes of such codes as well as several constructions. This work focuses on the case when the records are binary vectors together with the Hamming distance. Other metrics such as the Johnson metric are also investigated.

The linear complexity of a sequence s is one of the measures of its predictability. It represents the smallest degree of a linear recursion which the sequence satisfies. There are several algorithms to find the linear complexity of a periodic sequence s of length N (where N is of some given form) over a finite field Fqin O(N) symbol field operations. The first such algorithm is The Games-Chan Algorithm which considers binary sequences of period 2n, and is known for its extreme simplicity. We generalize this algorithm and apply it efficiently for several families of binary sequences. Our algorithm is very simple, it requires βN bit operations for a small constant β, where N is the period of the sequence. We make an analysis on the number of bit operations required by the algorithm and compare it with previous algorithms. In the process, the algorithm also finds the recursion for the shortest linear feedback shift-register which generates the sequence. Some other interesting properties related to shift-register sequences, which might not be too surprising but generally unnoted, are also consequences of our exposition.

Recovery sets for vectors and subspaces are important in constructions of distributed storage system codes. These concepts are also interesting in their own right. In this paper we consider the following very basic recovery question: what is the maximum number of possible pairwise disjoint recovery sets if the recovered element is a d-dimensional subspace and the elements stored are the one-dimensional subspaces of an n-dimensional vector space over GF(q). Lower and upper bounds on the number of such recovery sets are provided. It is shown that generally these bounds are either tight or very close of being tight.

Minimal multicast networks are fascinating and efficient combinatorial objects, where the removal of a single link makes it impossible for all receivers to obtain all messages. We study the structure of such networks, and prove some constraints on their possible solutions. We then focus on the combination network, which is one of the simplest and most insightful network in network-coding theory. Of particular interest are minimal combination networks. We study the gap in alphabet size between vector-linear and scalar-linear network-coding solutions for such minimal combination networks and some of their sub-networks. For minimal multicast networks with two source messages we find the maximum possible gap. We define and study sub-networks of the combination network, which we call Kneser networks, and prove that they attain the upper bound on the gap with equality. We also prove that the study of this gap may be limited to the study of sub-networks of minimal combination networks, by using graph homomorphisms connected with the q -analog of Kneser graphs. Additionally, we prove a gap for minimal multicast networks with three or more source messages by studying Kneser networks. Finally, an upper bound on the gap for full minimal combination networks shows nearly no gap, or none in some cases. This is obtained using an MDS-like bound for subspaces over a finite field.

In a bus with n wires, each wire has two states, `0' or `1', representing one bit of information. Whenever the state transitions from `0' to `1', or `1' to `0', joule heating causes the temperature to rise, and high temperatures have adverse effects on on-chip bus performance. Recently, the class of low-power cooling (LPC) codes was proposed to control such state transitions during each transmission. As suggested in earlier work, LPC codes may be used to control simultaneously both the peak temperature and the average power consumption of on-chip buses. Specifically, an (n, t, w)-LPC code is a coding scheme over n wires that (i) avoids state transitions on the t hottest wires (thus preventing the peak temperature from rising); and (ii) allows at most w state transitions in each transmission (thus reducing average power consumption). In this paper, for any fixed value of w, several constructions are presented for large LPC codes that can be encoded and decoded in time O(n log2(n/w)) along with the corresponding encoding/decoding schemes. In particular, we construct LPC codes of size (n/w)w-1, which are asymptotically optimal. We then modify these LPC codes to also correct errors in time O(n3). For the case where w is proportional to n, we further present a different construction of large LPC codes, based on a mapping from cooling codes to LPC codes. Using this construction, we obtain two families of LPC codes whose encoding and decoding complexities are O(n3).

A functional k-Private Information Retrieval (k-PIR) code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers. The goal is to find the minimum number of servers for given k and s. We provide lower bounds on the minimum number of servers and constructions which yield upper bounds on this number. For k ≤ 4, exact bounds on this number are proved. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known PIR problem based on a coded database to reduce the storage overhead, when each linear combination contains exactly one information symbol. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functionalk-batch code. A functional k-batch code is a functional k-PIR code, where all the k linear combinations in the multiset are equal. We provide some bounds on the minimum number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, Write-Once Memory (WOM) codes, and Random I/O (RIO) codes.

The combination network is one of the simplest and insightful networks in coding theory. The vector network coding solutions for this network and some of its sub-networks are examined. For a fixed alphabet size of a vector network coding solution, an upper bound on the number of nodes in the network is obtained. This bound is an MDS bound for subspaces over a finite field. A family of sub-networks of combination networks is defined. It is proved that for this family of networks, which are minimal multicast networks, there is a gap in the minimum alphabet size between vector network coding solutions and scalar network coding solutions. This gap is obtained for any number of messages and is based on coloring of the q-Kneser graph and a new hypergraph generalization for it.

A sequence s = (s1,⋯,sn) is called a (b, h)-constrained de Bruijn sequence if all substrings of length h starting within b consecutive positions are distinct. A set of (b, h)-constrained de Bruijn sequences is called a (b, h)-constrained de Bruijn code. A (b, h)-constrained de Bruijn sequence was constructed and used as a component of a code correcting multiple limited-shift-errors in racetrack memories. In this work, we show that a (b, h)-constrained de Bruijn code can correct deletions and sticky-insertions and also can determine the locations of these errors in an ℓ-symbol read channel. We also show that it is possible to use sequences from a (b, h)-constrained de Bruijn code to construct a code correcting shift-errors in racetrack memories. As a consequence, we improve the rates on previous known codes.It is shown in this work that a (b, h)-constrained de Bruijn code is a constrained code avoiding a set of specific patterns. Finally, we present some techniques to compute the maximum asymptotic rate and find some efficient encoding/decoding algorithms for (b, h)-constrained de Bruijn codes.

A private proximity retrieval (PPR) scheme is a protocol which allows a user to retrieve the identities of all records in a database that are within some distance r from the user's record x. The user's privacy at each server is given by the fraction of the record x that is kept private. The distortion of a PPR scheme measures how accurately the user can calculate the identities of the desired files. We assume that each server stores a copy of the database. This paper studies protocols that offer trade-offs between perfect privacy and low computational complexity and storage.In this paper, this study is initiated. The work focuses on the case when the records are binary vectors together with the Hamming distance. In particular, for a given privacy level, we investigate the minimum number of servers that guarantee a prescribed distortion value. The collusions of pairs of servers as well as other distance measures are investigated.

Private information retrieval has been reformulated in an information-theoretic perspective in recent years. The two most important parameters considered for a PIR scheme in a distributed storage system are the storage overhead and PIR rate. The complexity of the computations done by the servers for the various tasks of the distributed storage system is an important parameter in such systems which didn't get enough attention in PIR schemes. As a consequence, we take into consideration a third parameter, the access complexity of a PIR scheme, which characterizes the total amount of data to be accessed by the servers for responding to the queries throughout a PIR scheme. We use a general covering codes approach as the main tool for improving the access complexity. With a given amount of storage overhead, the ultimate objective is to characterize the tradeoff between the rate and access complexity of a PIR scheme. This covering codes approach raises a new interesting coding problem of generalized coverings similarly to the well-known generalized Hamming weights.

A functional k-PIR code of dimension s consists of n servers storing linear combinations of s linearly independent information symbols. Any linear combination of the s information symbols can be recovered by k disjoint subsets of servers (the reason for this somehow abused definition will be explained in the sequel). The goal is to find the smallest number of servers for given k and s. We provide lower bounds on the number of servers and constructions which yield upper bounds. For k ≤ 4 we provide exact bounds on the number of servers. Furthermore, we provide some asymptotic bounds. The problem coincides with the well known private information retrieval problem based on a coded database to reduce the storage overhead. If any multiset of size k of linear combinations from the linearly independent information symbols can be recovered by k disjoint subset of servers, then the servers form a functional k-batch code. A functional k-batch code is also a functional k-PIR, where all the k linear combinations in the multiset are equal. We provide some bounds on the number of servers for functional k-batch codes. In particular we present a random construction and a construction based on simplex codes, WOM codes, and RIO codes.

There has been much recent interest in private information retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being a simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy, and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient PIR protocols. In this paper, we are interested in designing PIR array codes. We consider the case when we have m servers, with each server storing a fraction (1/s) of the bits of the database; here s is a fixed rational number with s > 1. A PIR array code with the k-FIR property enables a k-server PIR protocol (with k ≤ m) to be emulated on m servers, with the overall storage requirements of the protocol being reduced. The communication complexity of a PIR protocol reduces as k grows, so the virtual server rate, defined to be k/m, is an important parameter. We study the maximum virtual server rate of a PIR array code with the k-PIR property. We present upper bounds on the achievable virtual server rate, some constructions, and ideas how to obtain the PIR array codes with the highest possible virtual server rate. In particular, we present constructions that asymptotically meet our upper bounds and the exact largest virtual server rate is obtained when 1 <; s ≤ 2. A k-PIR code (and similarly a k-PIR array code) is also a locally repairable code with symbol availability k-1. Such a code ensures k parallel reads for each information symbol. So the virtual server rate is very closely related to the symbol availability of the code when used as a locally repairable code. The results of this paper are discussed also in this context where subspace codes also have an important role.

Grassmannian codes are known to be useful in error correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. The multicast networks which were used for this purpose are generalized combination networks. In both the scalar and the vector network coding solutions, the subspace distance is used as the distance measure for the codes which solve the network coding problem in the generalized combination networks. In this paper, we show that the subspace distance can be replaced with two other possible distance measures which generalize the subspace distance. These two distance measures are shown to be equivalent under an orthogonal transformation. It is proved that the Grassmannian codes with the new distance measures generalize the Grassmannian codes with the subspace distance and the subspace designs with the strength of the design. Furthermore, optimal Grassmannian codes with the new distance measures have minimal requirements for the network coding solutions of some generalized combination networks. The coding problems related to these two distance measures, especially with respect to network coding, are discussed. Finally, by using these new concepts, it is proved that the codes in the Hamming scheme form a subfamily of the Grassmannian codes.

We study array codes which are based on subspaces of a linear space over a finite field, using spreads, q-Steiner systems, and subspace transversal designs. We present several constructions of such codes which are q-analogs of some known block codes, such as the Hamming and simplex codes. We examine the locality and availability of the constructed codes. In particular, we distinguish between two types of locality and availability: node versus symbol. The resulting codes have distinct symbol/node locality/availability, allowing a more efficient repair process for a single symbol stored in a storage node of a distributed storage system, compared with the repair process for the whole node.

A class of low-power cooling (LPC) codes, to control simultaneously both the peak temperature and the average power consumption of interconnects, were introduced recently. An (n,t,w)-LPC code is a coding scheme over n wires that (A) avoids state transitions on the t hottest wires (cooling), and (B) limit the number of transitions to w in each transmission (low-power). A few constructions for large LPC codes that have efficient encoding and decoding schemes, are given. In particular, when w is fixed, we construct LPC codes of size (n/w)w-1and show that these LPC codes can be modified to correct errors efficiently. We further present a construction for large LPC codes based on a mapping from cooling codes to LPC codes.

Subspace codes are known to be useful in error-correction for random network coding. Recently, they were used to prove that vector network codes outperform scalar linear network codes, on multicast networks, with respect to the alphabet size. In both cases, the subspace distance is used as the distance measure. In this work we show that we can replace the subspace distance with two other possible distance measures which generalize the subspace distance. We prove that each code with the largest number of codewords and the generalized distance, given the other parameters, has the minimum requirements needed to solve a given multicast network with a scalar linear code. We discuss lower and upper bounds on the sizes of the related codes.

High temperatures have dramatic negative effects on interconnect performance and, hence, numerous techniques have been proposed to reduce the power consumption of on-chip buses. However, existing methods fall short of fully addressing the thermal challenges posed by high-performance interconnects. In this paper, we introduce new efficient coding schemes that make it possible to directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. We also reduce the average power consumption by making sure that the total number of state transitions on all the wires is below a prescribed threshold. We show how each of these two features can be coded for separately or, alternatively, how both can be achieved at the same time. In addition, error-correction for the transmitted information can be provided while controlling the peak temperature and/or the average power consumption. In general, our cooling codes use n > k wires to encode a given k-bit bus. One of our goals herein is to determine the minimum possible number of wires n needed to encode k bits while satisfying any combination of the three desired properties. We provide full theoretical analysis in each case. In particular, we show that n = k+t +1 suffices to cool the t hottest wires, and this is the best possibility. Moreover, although the proposed coding schemes make use of sophisticated tools from combinatorics, discrete geometry, linear algebra, and coding theory, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

Given a finite directed graph with n vertices, we define a metric dG on Fnq, where Fq is the finite field with q elements. The weight of a word is defined as the number of vertices that can be reached by a directed path from a vertex within the support of the vector. Two canonical forms, which do not affect the metric, are given to each graph. Based on these forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield different metrics. Efficient algorithms to check if a set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the metric. Furthermore, we give a complete description of the group of linear isometries of the graph metrics and a characterization of the graphs for which every linear code admits a G-canonical decomposition. Considering those graphs, we are able to derive an expression of the packing radius of linear codes in such metric spaces. Finally, given a directed graph which determines a hierarchical poset, we present sufficient and necessary conditions to ensure the validity of the MacWilliams identity and the MacWilliams extension property.

There has been much recent interest in Private information Retrieval (PIR) in models where a database is stored across several servers using coding techniques from distributed storage, rather than being simply replicated. In particular, a recent breakthrough result of Fazelli, Vardy and Yaakobi introduces the notion of a PIR code and a PIR array code, and uses this notion to produce efficient protocols. In this paper we are interested in designing PIR array codes. We consider the case when we have m servers, with each server storing a fraction (1/s) of the bits of the database; here s is a fixed rational number with s > 1. We study the maximum PIR rate of a PIR array code with the k-PIR property (which enables a k-server PIR protocol to be emulated on the m servers), where the PIR rate is defined to be k/m. We present upper bounds on the achievable rate, some constructions, and ideas how to obtain PIR array codes with the highest possible PIR rate. In particular, we present constructions that asymptotically meet our upper bounds, and the exact largest PIR rate is obtained when 1 <; s ≤ 2.

In the classical model for (information theoretically secure) Private Information Retrieval (PIR) due to Chor, Goldreich, Kushilevitz and Sudan, a user wishes to retrieve one bit of a database that is stored on a set of n servers, in such a way that no individual server gains information about which bit the user is interested in. The aim is to design schemes that minimise the total communication between the user and the servers. More recently, there have been moves to consider more realistic models where the total storage of the set of servers, or the per server storage, should be minimised (possibly using techniques from distributed storage), and where the database is divided into R-bit records with R 1, and the user wishes to retrieve one record rather than one bit. When R is large, downloads from the servers to the user dominate the communication complexity and so the aim is to minimise the total number of downloaded bits. Work of Shah, Rashmi and Ramchandran shows that at least R + 1 bits must be downloaded from servers in the worst case, and provides PIR schemes meeting this bound. Sun and Jafar have considered the download cost of a scheme, defined as the ratio of the message length R and the total number of bits downloaded. They determine the best asymptotic download cost of a PIR scheme (as R → ∞) when a database of k messages is stored by n servers. This paper provides various bounds on the download complexity of a PIR scheme, generalising those of Shah et al. to the case when the number n of servers is bounded, and providing links with classical techniques due to Chor et al. The paper also provides a range of constructions for PIR schemes that are either simpler or perform better than previously known schemes. These constructions include explicit schemes that achieve the best asymptotic download complexity of Sun and Jafar with significantly lower upload complexity, and general techniques for constructing a scheme with good worst case download complexity from a scheme with good download complexity on average.

High temperatures have dramatic negative effects on interconnect performance. Numerous techniques have been proposed to reduce the power dissipation of on-chip buses but they fall short of fully addressing the thermal challenges posed by high-performance interconnects. We introduce new efficient coding schemes that directly control the peak temperature of a bus by effectively cooling its hottest wires. This is achieved by avoiding state transitions on the hottest wires for as long as necessary until their temperature drops off. At the same time, we reduce the average power consumption by ensuring that the total number of state transitions on all the wires is bounded. Our solutions call for redundancy: we use n > k wires to encode a given k-bit bus. Therefore, it is important to determine the minimum possible number of wires n needed to encode k bits while satisfying the desired properties. We provide full analysis in each case, and show that the number of additional wires required to cool the t hottest wires is negligible when k is large. Moreover, the resulting encoders and decoders are fully practical. They do not require significant computational overhead and can be implemented without sacrificing a large circuit area.

Ever-increasing amounts of data are created and processed in internet-scale companies such as Google, Facebook, and Amazon. The efficient storage of such copious amounts of data has thus become a fundamental and acute problem in modern computing. No single machine can possibly satisfy such immense storage demands. Therefore, distributed storage systems (DSS), which rely on tens of thousands of storage nodes, are the only viable solution. Such systems are broadly used in all modern internet-scale systems. However, the design of a DSS poses a number of crucial challenges, markedly different from single-user storage systems. Such systems must be able to reconstruct the data efficiently, to overcome failure of servers, to correct errors, etc. Lots of research was done in the last few years to answer these challenges and the research is increasing in parallel to the increasing amount of stored data. The main goal of this paper is to consider codes which have two of the most important features of distributed storage systems, namely, locality and availability. Our codes are array codes which are based on subspaces of a linear space over a finite field. We present several constructions of such codes which are q-analog to some of the known block codes. Some of these codes possess independent intellectual merit. We examine the locality and availability of the constructed codes. In particular we distinguish between two types of locality and availability, node vs. symbol, locality and availability. To our knowledge this is the first time that such a distinction is given in the literature.

A novel technique for construction of minimum storage regenerating (MSR) codes is presented. Based on this technique, three explicit constructions of MSR codes are given. The first two constructions provide access-optimal MSR codes, with two and three parities, respectively, which attain the sub-packetization bound for access-optimal codes. The third construction provides longer MSR codes with three parities (i.e., codes with larger number of systematic nodes). This improvement is achieved at the expense of the access-optimality and the field size. In addition to a minimum storage in a node, all three constructions allow the entire data to be recovered from a minimal number of storage nodes. That is, given storage ℓ in each node, the entire stored data can be recovered from any 2 log2ℓ for two parity nodes, and either 3 log3ℓ or 4 log3ℓ for three parities. Second, in the first two constructions, a helper node accesses the minimum number of its symbols for repair of a failed node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, in the first construction a field size of at least 6 log3ℓ +1 (or 3 log3ℓ +1 for fields with characteristic 2) is sufficient, and in the second construction the field size is larger, yet linear in log3ℓ. Both constructions with three parities provide a significant improvement over previous works due to either decreased field size or lower subpacketization.

Given a finite directed graph G with n vertices, the metric m(G) is naturally defined over Fqn, where the weight of a word which has its nonzero entries in positions i1,..., ir, is equal to the number of vertices in all the directed paths starting in the vertices vi1,..., vir. Two canonical forms, which do not affect the metric, are given to each graph. Based on these canonical forms we characterize each such metric. We further use these forms to prove that two graphs with different canonical forms yield two different metrics. Efficient algorithms to check if a given set of metric weights define a metric based on a graph are given. We provide tight bounds on the number of metric weights required to reconstruct the whole metric. Finally, we discuss the group of linear isometries of the graph metrics and the connection of the work to coding theory.

This paper considers vector network coding based on rank-metric codes and subspace codes. Our main result is that vector network coding can significantly reduce the required field size compared to scalar linear network coding in the same multicast network. The achieved gap between the field size of scalar and vector network coding is in q(h-2)t2/h+o(t)for any q ≥ 2 and any even h ≥ 4, where t denotes the dimension of the vector solution and h the number of messages. If h ≥ 5 is odd, then the achieved gap of the field size between the scalar network coding solution and the vector network coding solution is q(h-3)t2/(h-1)+o(t). Previously, only a gap of constant size had been shown. This implies also the same gap between the field size in linear and non-linear scalar network coding for multicast networks. The results are obtained by considering several multicast networks which are variations of the well-known combination network.

This paper presents a new construction of high-rate minimum storage regenerating codes. In addition to a minimum storage in a node, these codes have the following two important properties: first, given storage ℓ in each node, the entire stored data can be recovered from any 2 log2ℓ (any 3 log3ℓ) nodes for two parities (for three parities, respectively); second, a helper node accesses the minimum number of its symbols for repair of a failed systematic node (access-optimality). The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. The generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. For two parities, the field size is reduced by a factor of two for access-optimal codes compared to previous constructions. For three parities, the field size is 6 log3ℓ+1 (or 3 log3ℓ+1 for fields with characteristic 2), where only non-explicit constructions with exponential field size (in log3ℓ) were known so far.

Subspace codes have received an increasing interest recently due to their application in error correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper, we consider such cyclic codes and provide constructions of optimal codes for which their codewords do not have full orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes, which are cyclic and analyze their parameters.

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.

Optimal rank-metric codes in Ferrers diagrams are considered. Such codes consist of matrices having zeros at certain fixed positions and can be used to construct good codes in the projective space. First, we consider rank-metric anticodes and prove a code-anticode bound for Ferrers diagram rank-metric codes. The size of optimal linear anticodes is given. Four techniques and constructions of Ferrers diagram rank-metric codes are presented, each providing optimal codes for different diagrams and parameters for which no optimal solution was known before. The first construction uses maximum distance separable codes on the diagonals of the matrices, the second one takes a subcode of a maximum rank distance code, and the last two combine codes in small diagrams to a code in a larger diagram. The constructions are analyzed and compared, and unsolved diagrams are identified.

Subspace codes have received an increasing interest recently due to their application in error-correction for random network coding. In particular, cyclic subspace codes are possible candidates for large codes with efficient encoding and decoding algorithms. In this paper we consider such cyclic codes. We provide constructions of optimal cyclic codes for which their codewords do not have full length orbits. We further introduce a new way to represent subspace codes by a class of polynomials called subspace polynomials. We present some constructions of such codes which are cyclic and analyze their parameters.

Distributed storage systems based on intersecting constant dimension (equidistant) codes are presented. These intersecting codes are constructed using the Plücker embedding, which is essential in the repair and the reconstruction algorithms. These systems possess several useful properties such as high failure resilience, minimum bandwidth, low overall storage, simple algebraic repair and reconstruction algorithms, good locality, and compatibility with small fields.

Fractional repetition (FR) codes is a family of codes for distributed storage systems (DSS) that allow uncoded exact repairs with minimum repair bandwidth. In this work, we consider a bound on the maximum amount of data that can be stored using an FR code. Optimal FR codes which attain this bound are presented. The constructions of these FR codes are based on families of regular graphs, such as Turán graphs and graphs with large girth; and on combinatorial designs, such as transversal designs and generalized polygons. In addition, based on a connection between FR codes and batch codes, we propose a new family of codes for DSS, called fractional repetition batch codes, which allow uncoded efficient exact repairs and load balancing which can be performed by several users in parallel.

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.

In this paper, code decompositions (a.k.a. code nestings) are used to design binary polarization kernels. The proposed kernels are in general nonlinear. They provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, nonlinear kernels of dimensions 14, 15, and 16 are constructed and are shown to have optimal asymptotic error-correction performance. The optimality is proved by showing that the exponents of these kernels achieve a new upper bound that is developed in this paper.

Fractional repetition (FR) codes is a family of codes for distributed storage systems (DSSs) that allow for uncoded exact repairs having the minimum repair bandwidth. However, in contrast to minimum bandwidth regenerating (MBR) codes, where an arbitrary set of a certain size of available nodes is used for a node repair, the repairs with FR codes are table based. This usually allows to store more data compared with MBR codes. In this paper, we consider bounds on the FR capacity, which is the maximum amount of data that can be stored using an FR code. Optimal FR codes which attain these bounds are presented. The constructions of these FR codes are based on combinatorial designs and on families of regular and biregular graphs. These constructions of FR codes for given parameters raise some interesting questions in graph theory. These questions and some of their solutions are discussed in this paper. In addition, based on a connection between FR codes and batch codes, we propose a new family of codes for DSS, namely, FR batch codes, which have the properties of batch codes and FR codes simultaneously. These are the first codes for DSS which allow for uncoded efficient exact repairs and load balancing which can be performed by several users in parallel. Other concepts related to FR codes are also discussed.

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.

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.

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For 03, but the proofs will become more complicated. The enumeration problem is presented also as a purely combinatorial problem. Finally, we prove the conjecture that the size of a constant weight (1, 2, n)-LRM Gray code with weight two is at most 2n.

Snake-in-the-box code is a Gray code, which is capable of detecting a single error. Gray codes are important in the context of the rank modulation scheme, which was suggested recently for representing information in flash memories. For a Gray code in this scheme, the codewords are permutations, two consecutive codewords are obtained using the push-to-the-top operation, and distance measure is defined on permutations. In this paper, the Kendall's T-metric is used as the distance measure. We present a general method for constructing such Gray codes. We apply the method recursively to obtain a snake of length M2n+1= ((2n + 1)(2n) - 1)M2n-1for permutations of S2n+1, from a snake of length M2n-1for permutations of S2n-1. Thus, we have lim;n→∞ M2n+1/S2n+1≈0.4338, improving on the previous known ratio of lim;n→∞ 1/√(πn). Using the general method, we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length (2n + 1)!/2-2n + 1 for permutations of S2n+1. The direct construction was applied successfully for S7and S9, and hence lim;n→∞ M2n+1/S2n+1≈0.4743.

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.

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 one is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second one 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 into a shape inscribed in a small cube.

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.

Lifted maximum rank distance (MRD) codes, which are constant dimension codes, are considered. It is shown that a lifted MRD code can be represented in such a way that it forms a block design known as a transversal design. A slightly different representation of this design makes it similar to a$q$-analog of a transversal design. The structure of these designs is used to obtain upper bounds on the sizes of constant dimension codes which contain a lifted MRD code. Codes that attain these bounds are constructed. These codes are the largest known constant dimension codes for the given parameters. These transversal designs can also be used to derive a new family of linear codes in the Hamming space. Bounds on the minimum distance and the dimension of such codes are given.

In the above titled paper (ibid., vol. 59, no. 2, pp. 1004-1017, Feb. 2013), the matrix in Example 7 (p. 1014) is incorrect. The correct matrix is presented here.

This paper has two goals. The first one is to discuss two related packing problems in the Lee and Manhattan metrics. One is to find good codes for error-correction (i.e., packings of Lee spheres) and the other is to transform the space in a way that volumes are preserved and each Lee sphere (or scaled cross-polytope) will be transformed into a shape inscribed in a small cube. The second goal is to consider weighing matrices for some of these coding problems. Weighing matrices have been used 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.

The iterated Johnson bound is the best known upper bound on the size of an error-correcting code in the GrassmannianGq(n,k). The iterated Schönheim bound is the best known lower bound on the size of a covering code inGq(n,k). We prove that both bounds are asymptotically attained for fixedkand fixed radius, asnapproaches infinity. Our methods rely on results from the theory of quasi-random hypergraphs which are proved using probabilistic techniques. We also determine the asymptotics of the size of the best Grassmannian codes and covering codes whenn-kand the radius are fixed, asnapproaches infinity.

A simple method to generate a 2-D binary grid pattern, which allows for absolute and accurate self-location in a finite planar region, is proposed. The pattern encodes position information in a local way so that reading a small number of its black or white pixels at any place provides sufficient data from which the location can be decoded both efficiently and robustly.

Sidon sequences and their generalizations have found during the years and especially recently various applications in coding theory. One of the most important applications of these sequences is in the connection of synchronization patterns. A few constructions of two-dimensional synchronization patterns are based on these sequences. In this paper we present sufficient conditions that a two-dimensional synchronization pattern can be transformed into a Sidon sequence. We also present a new construction for Sidon sequences over an alphabet of size q(q - 1), where q is a power of a prime.

The lifted maximum rank distance codes are considered. It is shown that these codes form structures which are transversal designs and also have some similarity to q-analog of transversal designs. Upper bounds on the sizes of codes which contain the lifted maximum rank distance codes are derived. A new construction for codes which attain one of these upper bounds is given. Low density parity check codes are derived from the lifted maximum rank distance codes and some of these codes are quasi-cyclic codes attaining the Griesmer bound.

Folding a sequenceBinto a multidimensional box is a well-known method which is used as a multidimensional coding technique. The operation of folding is generalized in a way that the sequenceBcan be folded into various shapes and not just a box. The novel definition of folding is based on a lattice tiling for the given shapeSand a direction in theD-dimensional integer grid. Necessary and sufficient conditions that a lattice tiling forScombined with a direction define a folding of a sequence intoSare derived. The immediate and most impressive applications are some new lower bounds on the number of dots in two-dimensional synchronization patterns. Asymptotically optimal such patterns were known only for rectangular shapes. We show asymptotically optimal such patterns for a large family of hexagons. This is also generalized for multidimensional synchronization patterns. The best known patterns, in terms of dots, for circles and other polygons are also given. The technique and its application for two-dimensional synchronization patterns, raises some interesting problems in discrete geometry. We will also discuss these problems. It is also shown how folding can be used to construct multidimensional error-correcting codes. Finally, by using the new definition of folding, new types of multidimensional pseudo-random arrays with various shapes are generated.

A well-known conjecture of Golomb and Welch is that the only nontrivial perfect codes in the Lee and Manhattan metrics have length two or minimum distance three. This problem and related topics were subject for extensive research in the last 40 years. In this paper, two product constructions for perfect Lee codes and diameter perfect Lee codes are presented. These constructions yield a large number of nonlinear perfect codes and nonlinear diameter perfect codes in the Lee and Manhattan metrics. A short survey and other related problems on perfect codes in the Lee and Manhattan metrics are also discussed.

The projective space of ordernover the finite field \BBFq, denoted here asPq(n), is the set of all subspaces of the vector space \BBFqn. The projective space can be endowed with the distance functiond(U,V) = dimU+ dimV-2 dim(U∩V) which turnsPq(n) into a metric space. With this, an (n,M,d) code \BBC in projective space is a subset ofPq(n) of sizeMsuch that the distance between any two codewords (subspaces) is at leastd. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n,M,d) code can correcttpacket errors and ρ packet erasures introduced (adversarially) anywhere in the network as long as 2t+ 2ρd. This motivates our interest in such codes. In this paper, we investigate certain basic aspects of “coding theory in projective space.” First, we present several new bounds on the size of codes inPq(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. We also present several specific constructions of codes and code families inPq(n). Finally, we prove that nontrivial perfect codes inPq(n) do not exist.

The Grassmannian space Gq(n, k) is the set of all k-dimensional subspaces of the vector space Fqn. Recently, codes in the Grassmannian have found an application in network coding. The main goal of this paper is to present efficient enumerative encoding and decoding techniques for the Grassmannian. These coding techniques are based on two different orders for the Grassmannian induced by different representations of k-dimensional subspaces of Fqn. One enumerative coding method is based on a Ferrers diagram representation and on an order for Gq(n, k) based on this representation. The complexity of this enumerative coding is O(k5/2(n - k)5/2) digit operations. Another order of the Grassmannian is based on a combination of an identifying vector and a reduced row echelon form representation of subspaces. The complexity of the enumerative coding, based on this order, is O(nk(n - k) log n log log n) digit operations. A combination of the two methods reduces the complexity on average by a constant factor.

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.

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.

A two-dimensional (2-D) grid with dots is called aconfiguration with distinct differencesif any two lines which connect two dots are distinct either in their length or in their slope. These configurations are known to have many applications such as radar, sonar, physical alignment, and time-position synchronization. Rather than restricting dots to lie in a square or rectangle, as previously studied, we restrict the maximum distance between dots of the configuration; the motivation for this is a new application of such configurations to key distribution in wireless sensor networks. We consider configurations in the hexagonal grid as well as in the traditional square grid, with distances measured both in the Euclidean metric, and in the Manhattan or hexagonal metrics. We note that these configurations are confined inside maximal anticodes in the corresponding grid. We classify maximal anticodes for each diameter in each grid. We present upper bounds on the number of dots in a pattern with distinct differences contained in these maximal anticodes. Our bounds settle (in the negative) a question of Golomb and Taylor on the existence of honeycomb arrays of arbitrarily large size. We present constructions and lower bounds on the number of dots in configurations with distinct differences contained in various 2-D shapes (such as anticodes) by considering periodic configurations with distinct differences in the square grid.

A distinct difference configuration is a set of points in$\BBZ ^{2}$with the property that the vectors (difference vectors) connecting any two of the points are all distinct. Many specific examples of these configurations have been previously studied: the class of distinct difference configurations includes both Costas arrays and sonar sequences, for example. Motivated by an application of these structures in key predistribution for wireless sensor networks, we define the$k$-hop coverage of a distinct difference configuration to be the number of distinct vectors that can be expressed as the sum of$k$or fewer difference vectors. This is an important parameter when distinct difference configurations are used in the wireless sensor application, as this parameter describes the density of nodes that can be reached by a short secure path in the network. We provide upper and lower bounds for the$k$-hop coverage of a distinct difference configuration with$m$points, and exploit a connection with$B_{h}$sequences to construct configurations with maximal$k$-hop coverage. We also construct distinct difference configurations that enable all small vectors to be expressed as the sum of two of the difference vectors of the configuration, an important task for local secure connectivity in the application.

This paper studies the error linear complexity spectrum of binary sequences with period2n. A precise categorization of those sequences having two distinct critical points in their spectra, as well as an enumeration of these sequences, is given. An upper bound on the maximum number of distinct critical points that the spectrum of a sequence can have is proved, and a construction which yields a lower bound on this number is given. In the process simpler proofs of some known results on the linear complexity andk-error linear complexity of sequences with period2nare provided.

Coding in the projective space has received recently a lot of attention due to its application in network coding. Reduced row echelon form of the linear subspaces and Ferrers diagram can play a key role for solving coding problems in the projective space. In this paper, we propose a method to design error-correcting codes in the projective space. We use a multilevel approach to design our codes. First, we select a constant-weight code. Each codeword defines a skeleton of a basis for a subspace in reduced row echelon form. This skeleton contains a Ferrers diagram on which we design a rank-metric code. Each such rank-metric code is lifted to a constant-dimension code. The union of these codes is our final constant-dimension code. In particular, the codes constructed recently by Koetter and Kschischang are a subset of our codes. The rank-metric codes used for this construction form a new class of rank-metric codes. We present a decoding algorithm to the constructed codes in the projective space. The efficiency of the decoding depends on the efficiency of the decoding for the constant-weight codes and the rank-metric codes. Finally, we use puncturing on our final constant-dimension codes to obtain large codes in the projective space which are not constant-dimension.

We present several methods and constructions to generate binary codes for correction of a multidimensional 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 a 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. This construction 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 a D -dimensional cluster-error of various shapes. 3) A transformation of the D -dimensional space into another D -dimensional space in a way that a D -dimensional Lee sphere is transformed into a shape located in a D-dimensional box of a relatively small size. 4) Applying the coloring method to correct more efficiently a two-dimensional error whose shape is a Lee sphere. 5) A construction of D -dimensional codes capable to correct a D -dimensional cluster-error of size b in which the number of erroneous positions is relatively small compared to b. 6) We present a code which corrects a D -dimensional arbitrary cluster-error with relatively small redundancy.

A constant-rate encoder–decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable.

This paper studies the error linear complexity profiles of binary sequences with period 2n. We give a precise categorization of those sequences having 2 distinct critical points in their profiles, as well as an enumeration of these sequences. We also give an upper bound on the maximum number of distinct critical points that the profile of a sequence can have, along with several constructions for sequences having many distinct critical points.

The projective space of order n over the finite field Fq, denoted Pq(n), is the set of all subspaces of the vector space Fnq. The distance function d(U,V) = dim U + dim V - 2 dim(UcapV) turns Pq(n) into a metric space. With this, an (n, M, d) code C in projective space is a subset of Pq(n) of size M such that the distance between any two codewords (subspaces) is at least d. Koetter and Kschischang recently showed that codes in projective space are precisely what is needed for error-correction in networks: an (n, M, d) code can correct t packet errors and rho packet erasures introduced (adversarially) anywhere in the network as long as 2t + 2pq(n), which may be thought of as counterparts of the classical bounds in coding theory due to Johnson, Delsarte, and Gilbert-Varshamov. Some of these are stronger than all the previously known bounds, at least for certain code parameters. Next, we examine the fundamental concepts of "linear codes" and "complements" in the context of Pq(n). These turn out to be considerably more involved than their classical counterparts. In particular, we construct linear codes of size 2nand conjecture that larger linear codes do not exist. We also present several specific constructions of codes and code families in Pq(n). Finally, we prove that nontrivial perfect codes in Pq(n) do not exist.

Let $\cal C$ be a code of length n over an alphabet of size q. A word $\mathbf{d}$ is a descendant of a pair of codewords $\mathbf{x},\mathbf{y} \in \cal C$ if $d_i \in \{x_i ,y_i \}$ for $1 \leq i \leq n$. A code $\cal C$ is an identifiable parent property (IPP) code if the following property holds. Whenever we are given $\cal C$ and a descendant $\mathbf{d}$ of a pair of codewords in $\cal C$, it is possible to determine at least one of these codewords. The paper introduces the notion of a prolific IPP code. An IPP code is prolific if all $q^n$ words are descendants. It is shown that linear prolific IPP codes fall into three infinite (“trivial”) families, together with a single sporadic example which is ternary of length 4. There are no known examples of prolific IPP codes which are not equivalent to a linear example: the paper shows that for most parameters there are no prolific IPP codes, leaving a relatively small number of parameters unsolved. In the process the paper obtains upper bounds on the size of a (not necessarily prolific) IPP code which are better than previously known bounds.

A construction for D-dimensional binary codes of size n1timesn2timeshelliptimesnDcorrecting a single D-dimensional box error is presented. If the size of the box error is b1timesb2timeshelliptimesbD, biodd, 1les i les D, and B = PiiD=1bi, then the redundancy of the code is at most [log2(n1n2hellip nD)] +B + (D-2)[log2B] + [log2b1]. For a two-dimensional binary array of size n times n we present a code correcting an error whose shape is a Lee sphere with radius R. The redundancy of the code is at most [log2n2] + 2R2+ 2R + [2log2(2R+1)]+1. This is also the redundancy of a binary code which corrects an arbitrary two-dimensional cluster-error of size 2R+1. A generalization for D-dimensional code which corrects either D-dimensional error whose shape is a Lee sphere or an arbitrary cluster-error is also given.

A binary sequence satisfies a one-dimensional (d, k) constraint if every run of zeroes has length at least d and at most k. A binary two-dimensional array satisfies a (d, k) constraint if every run of zeroes, in each one of the array directions, has length at least d and at most k. Few models have been proposed in the literature to handle two dimensional data: the diamond model, the square model, the hexagonal model, and the triangular model. The constraints in the different directions might be asymmetric and hence many kind of constraints are defined depending on the number of directions in the model. For example, a two-dimensional array in the diamond model satisfies a (d1, k1, d2, k2) constraint if it satisfies the one-dimensional (d1,k1) constraint horizontally and the one-dimensional (d2,k2) constraint vertically. In this paper we examine the region in which the capacity of the constraints is zero or positive in the various models. We consider asymmetric constraints in the diamond model and symmetric constraints in the other models. In particular we provide an almost complete solution for asymmetric constraints in the diamond model

A constant-rate encoder-decoder pair is presented for a fairly large family of two-dimensional (2-D) constraints. Encoding and decoding is done in a row-by-row manner, and is sliding-block decodable. Essentially, the 2-D constraint is turned into a set of independent and relatively simple one-dimensional (1-D) constraints; this is done by dividing the array into fixed-width vertical strips. Each row in the strip is seen as a symbol, and a graph presentation of the respective 1-D constraint is constructed. The maxentropic stationary Markov chain on this graph is next considered: a perturbed version of the corresponding probability distribution on the edges of the graph is used in order to build an encoder which operates in parallel on the strips. This perturbation is found by means of a network flow, with upper and lower bounds on the flow through the edges. A key part of the encoder is an enumerative coder for constant-weight binary words. A fast realization of this coder is shown, using floating-point arithmetic

In his pioneering work, from 1973, on algebraic approach to codes in association schemes, Dlesarte has conjectured that there are no nontrivial perfect codes in the Johnson schemes. Many attempts were made during the last 30 years to solve this conjecture. These attempts used Lloyd polynomials, anticodes in the Johnson schemes, designs, and number theory. We will survey all the known results and outline directions for solving the problem.

A binary sequence satisfies a one-dimensional (d,k) constraint if every run of zeros (with possible exception of the first and the last runs) has length at least d and at most k. A binary two-dimensional array satisfies a (d,k) constraint if each row and each column satisfies the one-dimensional (d,k) constraint. Few models have been proposed in the literature to handle two-dimensional data: the diamond model, the square model, the hexagonal model, and the triangular model. The constraints in the different directions might be asymmetric and hence many kind of constraints are defined depending on the number of directions in the model. For example, a two-dimensional array in the diamond model satisfies a (d1,k1,d2,k2) constraint if it satisfies the one-dimensional (d1,k1) constraint horizontally and the one-dimensional (d2,k2) constraint vertically. In this correspondence, the region in which the capacity is zero or positive, in the various models, is examined. Asymmetric constraints in the diamond model and symmetric constraints in the other models are considered. In particular, an almost complete solution for asymmetric constraints in the diamond model is provided

The stopping redundancy of the code is an important parameter which arises from analyzing the performance of a linear code under iterative decoding on a binary erasure channel. In this paper, we will consider the stopping redundancy of Reed-Muller codes and related codes. Let R(lscr,m) be the Reed-Muller code of length 2mand order lscr. Schwartz and Vardy gave a recursive construction of parity-check matrices for the Reed-Muller codes, and asked whether the number of rows in those parity-check matrices is the stopping redundancy of the codes. We prove that the stopping redundancy of R(m-2,m), which is also the extended Hamming code of length 2m, is 2m-1 and thus show that the recursive bound is tight in this case. We prove that the stopping redundancy of the simplex code equals its redundancy. Several constructions of codes for which the stopping redundancy equals the redundancy are discussed. We prove an upper bound on the stopping redundancy of R(1,m). This bound is better than the known recursive bound and thus gives a negative answer to the question of Schwartz and Vardy

Upper bounds on the maximum number of codewords in a binary code of a given length and minimum Hamming distance are considered. New bounds are derived by a combination of linear programming and counting arguments. Some of these bounds improve on the best known analytic bounds. Several new record bounds are obtained for codes with small lengths

For $z_1,z_2,z_3\in\Z^2$, the tristance $d_3(z_1,z_2,z_3)$ is a generalization of the $L_1$-distance on $\mathbb{Z}^2$ to a quality that reflects the relative dispersion of three points rather than two. In this paper we prove that at least 3k 2 colors are required to color the points of $\mathbb{Z}^2$, such that the tristance between any three distinct points, colored with the same color, is at least 4k. We prove that 3k 2 +3k+1 colors are required if the tristance is at least 4k+2. For the first case we show an infinite family of colorings with colors and conjecture that these are the only colorings with 3k 2 colors.

The main purpose of this paper is to give bounds on the length of the shortest and longest binary quasi-perfect codes with a given Hamming distance, covering radius, and redundancy. We consider codes with Hamming distance 4 and 5 and covering radius 2 and 3, respectively. We discuss the blockwise direct sum (BDS) construction which has an important role in finding these bounds.

A binary sequence satisfies a one-dimensional (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/) runlength constraint if every run of zeros has length at least d/sub 1/ and at most k/sub 1/ and every run of ones has length at least d/sub 2/ and at most k/sub 2/. A two-dimensional binary array is (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)-constrained if it satisfies the one-dimensional (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/) runlength constraint horizontally and the one-dimensional (d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) runlength constraint vertically. For given d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/,d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/, the two-dimensional capacity is defined as C(d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) = lim/m,n/spl rarr//spl infin/ log/sub 2/ N(m,n|d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)/mn where N(m,n|d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)denotes the number of m/spl times/n binary arrays that are (d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/)-constrained. Such constrained systems may have applications in digital storage applications. We consider the question for which values of d/sub i/ and k/sub i/ is the capacity C(d/sub 1/,k/sub 1/,d/sub 2/,k/sub 2/;d/sub 3/,k/sub 3/,d/sub 4/,k/sub 4/) positive and for which values is the capacity zero. The question is answered for many choices of the d/sub i/ and the k/sub i/.

We consider two-dimensional error-correcting codes capable of correcting a single arbitrary cluster of errors of size b. We provide optimal 2-cluster-correcting codes in several connectivity models, as well as optimal, or nearly optimal, 2-cluster-correcting codes in all dimensions. We also construct 3-cluster-correcting codes and b-straight-cluster-correcting codes. We conclude by improving the Reiger bound for two-dimensional cluster-correcting codes.

We consider two-dimensional error-correcting codes capable of correcting unrestricted bursts of size b. We construct optimal 2-burst-correcting codes in three connectivity models: the rectangular grid with 4 or 8 neighbors, and the hexagonal graph. We also give optimal, or nearly optimal, 2-burst-correcting codes in all dimensions. We then construct 3-burst-correcting codes with 3 redundancy bits above the sphere-packing bound, followed by b-straight-burst-correcting codes with b-2 redundancy bits above the sphere-packing bound. We conclude by improving the Reiger bound for two-dimensional unrestricted-burst-correcting codes

The main purpose of this paper is to give bounds on the length of the shortest and longest binary quasiperfect codes with a given Hamming distance, covering radius, and redundancy. We consider codes with Hamming distance 4 and 5 and covering radius 2 and 3, respectively.

For z/sub 1/, z/sub 2/, z/sub 3/ /spl isin/ Z/sup 2/, the tristance d/sub 3/(z/sub 1/, z/sub 2/, z/sub 3/) is a generalization of the L/sub 1/-distance on Z/sup 2/ to a quality that reflects the relative dispersion of three points rather than two. We prove that at least 3k/sup 2/ colors are required to color the points of Z/sup 2/, such that the tristance between any three distinct points, colored with the same color, is at least 4k. We also prove that 3k/sup 2/+3k+1 colors are required if the tristance is at least 4k+2. For the first case we show an infinite family of colorings with 3k/sup 2/ colors and conjecture that these are the only colorings with 3k/sup 2/ colors.

In his pioneering work from 1973, Delsarte conjectured that there are no nontrivial perfect codes in the Johnson scheme. Many attempts were made, during the years which followed, to prove Delsarte's conjecture, but only partial results have been obtained. We survey all these attempts, and prove some new results having the same flavor. We also present a new method, taking a different approach, which we hope can lead to the settling of this conjecture. We show how this new method rules out sets of parameters as well as specific given parameters.

Two-dimensional interleaving schemes with repetitions are considered. These schemes are required for the correction of two-dimensional bursts (or clusters) of errors in applications such as optical recording and holographic storage. We assume that a cluster of errors may have an arbitrary shape, and is characterized solely by its area t. Thus, an interleaving scheme A(t,r) of strength t with r repetitions is an (infinite) array of integers defined by the property that every integer appears no more than r times in any connected component of area t. The problem is to minimize, for a given t and r, the interleaving degree deg A(t,r), which is the total number of distinct integers contained in the array. Optimal interleaving schemes for r=1 (no repetitions) have been devised in earlier work. Here, we consider interleaving schemes for r/spl ges/2. Such schemes reduce the overall redundancy, yet are considerably more difficult to construct and analyze. To this end, we generalize the concept of L/sub 1/-distance and introduce the notions of tristance, quadristance, and more generally r-dispersion. We focus on the special class of interleaving schemes, called lattice interleavers, that is akin to the class of linear codes in coding theory. We construct efficient lattice interleavers for r=2,3,4 and some higher values of r. For r=2,3 we show that these lattice interleavers are either optimal for all t or asymptotically optimal for t/spl rarr//spl infin/. We present the results of an extensive computer search that yields the optimal lattice interleavers for r=2,3,4,5,6 and t up to about 1000. Finally, we consider an alternative connectivity model for clusters, where two elements in an array are connected if they are adjacent horizontally, vertically, or diagonally. We establish relations between interleavers for this model and interleavers for the standard horizontal/vertical connectivity model, and show that these models become equivalent for t/spl rarr//spl infin/. We conclude with some conjectures and open problems.

Let A(n,d) denote the maximum possible number of codewords in a binary code of length n and minimum Hamming distance d. For large values of n, the best known upper bound, for fixed d, is the Johnson bound. We give a new upper bound which is at least as good as the Johnson bound for all values of n and d, and for each d there are infinitely many values of n for which the new bound is better than the Johnson bound. For small values of n and d, the best known method to obtain upper bounds on A(n,d) is linear programming. We give new inequalities for the linear programming and show that with these new inequalities some of the known bounds on A(n,d) for n/spl les/28 are improved.

In this correspondence, we present two constructions. In the first construction, we show how to generate perfect linear codes of length 2/sup r-1/, r/spl ges/5, and redundancy r, which correct a single burst of length 2. In the second construction, we show how to generate perfect linear codes organized in bytes of length 2/sup r-1/, r/spl ges/5, with redundancy divisible by r, which correct a single burst of length 2 within the bytes.

In certain memory systems the most common error is a single error and the next most common error is two errors in positions which are stored physically adjacent in the memory. In this correspondence we present optimal codes for recovering from such errors. We correct single errors and detect double adjacent errors. For detecting adjacent errors we consider codes which are byte-organized. In the binary case, it is clear that the length of the code is at most 2/sup r/-r-1, where r is the redundancy of the code. We summarize the known results and some new ones in this case. For the nonbinary case we show an upper bound, called "the pairs bound," on the length of such code. Over GF(3) codes with bytes of size 2 which attain the bound exist if and only if perfect codes with minimum Hamming distance 5 over GF(3) exist. Over GF(4) codes which attain the bound with byte size 2 exist for all redundancies. For most other parameters we prove the nonexistence of codes which attain the bound.

The linear complexity of a de Bruijn sequence is the degree of the shortest linear recursion which generates the sequence. It is well known that the complexity of a binary de Bruijn sequence of length 2/sup n/ is bounded below by 2/sup n-1/+n and above by 2/sup n-/1 for n/spl ges/3. We briefly survey the known knowledge in this area. Some new results are also presented, in particular, it is shown that for each interval of length 2/sup [log n]+1/ in the above range, there exist binary de Bruijn sequences of length 2/sup n/ with linear complexity in the interval.

If a linear block code C of length n has a Tanner graph without cycles, then maximum-likelihood soft-decision decoding of C can be achieved in time O(n/sup 2/). However, we show that cycle-free Tanner graphs cannot support good codes. Specifically, let C be an (n,k,d) linear code of rate R=k/n that can be represented by a Tanner graph without cycles. We prove that if R/spl ges/0.5 then d/spl les/2, while if R<0.5 then C is obtained from a code of rate /spl ges/0.5 and distance /spl les/2 by simply repeating certain symbols. In the latter case, we prove that d/spl les/[n/k+1]+[n+1/k+1]<2/R. Furthermore, we show by means of an explicit construction that this bound is tight for all values of n and k. We also prove that binary codes which have cycle-free Tanner graphs belong to the class of graph-theoretic codes, known as cut-set codes of a graph. Finally, we discuss the asymptotics for Tanner graphs with cycles, and present a number of open problems for future research.

Single-track Gray codes are cyclic Gray codes with codewords of length n, such that all the n tracks which correspond to the n distinct coordinates of the codewords are cyclic shifts of the first track. We investigate the structure of such binary codes and show that there is no such code with 2/sup n/ codewords when n is a power of 2. This implies that the known codes with 2/sup n/-2n codewords. when n is a power of 2, are optimal. This result is then generalized to codes over GF(p), where p is a prime. A subclass of single-track Gray codes, called single-track Gray codes with k-spaced heads, is also defined. All known systematic constructions for single-track Gray codes result in codes from this subclass. We investigate this class and show it has a strong connection with two classes of sequences, the full-order words and the full-order self-dual words. We present an iterative construction for binary single-track Gray codes which are asymptotically optimal if an infinite family of asymptotically optimal seed-codes exists. This construction is based on an effective way to generate a large set of distinct necklaces and a merging method for cyclic Gray codes based on necklaces representatives.

Efficient encoding algorithms are presented for two types of constraints on two-dimensional binary arrays. The first constraint considered is that of t-conservative arrays, where each row and each column has at least t transitions of the form '0'/spl rarr/'1' or '1'/spl rarr/'0.' The second constraint is that of two-dimensional DC-free arrays, where in each row and each column the number of '0's equals the number of '1's.

Although nontrivial perfect binary codes exist only for length n = 2 m -1 with $m \ge 3$ and for length n=23, many interesting problems concerning these codes remain unsolved. Herein, we present solutions to some of these problems. In particular, we show that the smallest nonempty intersection of two perfect codes of length 2 m -1 consists of two codewords, for all $m \ge 3$. We also provide a complete solution to the intersection number problem for Hamming codes. Furthermore, we prove that for $m \ge 3$, a perfect code of length 2 m-1 -1 is embedded in a perfect code $\Bbb{C}$ of length 2 m -1 if and only if ${\Bbb C}$ is not of full rank. This result implies the existence of distinct generalized Hamming weights for perfect codes, and we determine completely the generalized Hamming weights of all perfect codes that do not contain embedded full-rank perfect codes. We further explore the close ties between perfect codes and tilings: we prove that full-rank tilings of ${\Bbb F}_{2}^n$ exist for all $n \geq 14$ and show that the existence of full-rank tilings for other n is closely related to the existence of full-rank perfect codes with kernels of high dimension. We briefly survey the present state of knowledge on perfect binary codes and list several interesting and important open problems concerning perfect codes and tilings.

We present a few new constructions for perfect linear single byte-correcting codes. These constructions generate some perfect single byte-correcting codes with new parameters, and some perfect single byte-correcting codes with known parameters and simpler presentation and implementation over the known codes. It is also shown that nonequivalent perfect linear single byte-correcting codes exist when all the bytes have the same size.

Many of the fundamental coding problems can be represented as graph problems. These problems are often intrinsically difficult and unsolved even if the code length is relatively small. With the motivation to improve lower bounds on the sizes of constant weight codes and asymmetric codes, we suggest a few greedy algorithms and other heuristic methods, which result in new, record-breaking codes. Some of the heuristics used are based on tabu search and evolutionary algorithms. Tables of new codes are presented.

An efficient algorithm is presented for encoding unconstrained information sequences into a third-order spectral-null code of length n and redundancy 9log/sub 2/ n+O(log log n). The encoding can be implemented using O(n) integer additions and O(nlog n) counter increments.

Runlength-limited sequences and arrays have found applications in magnetic and optical recording. While the constrained sequences are well studied, little is known about constrained arrays. In this correspondence we consider the question of how to cascade two arrays with the same runlength constraints horizontally and vertically, in such a way that the runlength constraints will not be violated. We consider binary arrays in which the shortest run of a symbol in a row (column) is d/sub 1/(d/sub 2/) and the longest run of a symbol in a row (column) is k/sub 1/(k/sub 2/). We present three methods to cascade such arrays. If k/sub 1/>4d/sub 1/-2 our method is optimal, and if k/sub 1//spl ges/d/sub 1/+1 we give a method which has a certain optimal structure. Finally, we show how cascading can be applied to obtain runlength-limited error-correcting array codes.

We apply the well-known operator of sequences, the derivative D, on codewords of linear codes. The depth of a codeword c is the smallest integer i such that D/sup i/c (the derivative applied i consecutive times) is zero. We show that the depth distribution of the nonzero codewords of an [n, k] linear code consists of exactly k nonzero values, and its generator matrix can be constructed from any k nonzero codewords with distinct depths. Interesting properties of some linear codes, and a way to partition equivalent codes into depth-equivalence classes are also discussed.

We construct a set of $q^{q^{cn} } $ nonequivalent q-ary perfect single error-correcting codes of length n over $GF( q )$ for sufficiently large n and a constant $c = \frac{1}{q} - \epsilon $. The construction is based on a small subcode A of the q-ary Hamming code of length n for which A and $q - 1$ of its cosets $A_1 , \ldots ,A_{q - 1} $ cover the same subset V. We show a few isomorphic and nonisomorphic ways in which A can be chosen, and we prove the uniqueness of these ways to choose A.

Although it was conjectured by Delsarte in 1973 that no nontrivial perfect codes exist in the Johnson scheme, only very partial results are known. In this paper we considerably reduce the range in which perfect codes in the Johnson scheme can exist; e.g., we show that there are no nontrivial perfect codes in the Johnson graph $J(2w + P,w )$, p prime. We give theorems about the structure of perfect codes if they exist. This involved structure gives more evidence in support of the belief that no nontrivial perfect codes exist in the Johnson scheme.

Single-track Gray codes are a special class of Gray codes which have advantages over conventional Gray codes in certain quantization and coding applications. The problem of constructing high period single-track Gray codes is considered. Three iterative constructions are given, along with a heuristic method for obtaining good seed-codes. In combination, these yield many families of very high period single-track Gray codes. In particular, for m/spl ges/3, length n=2/sup m/, period 2/sup n/-2n codes are obtained.

We present two related methods of construction for de Bruijn (1946) sequences, both based on interleaving "smaller" de Bruijn sequences. Sequences obtained using these construction methods have the advantage that they can be "decoded" very efficiently, i.e., the position within the sequence of any particular "window" can be found very simply. Sequences with simple decoding algorithms are of considerable practical importance in position location applications.

A cyclically permutable code is a binary code whose codewords are cyclically distinct and have full cyclic order. An important class of these codes are the constant weight cyclically permutable codes. In a code of this class all codewords have the same weight w. These codes have many applications, in. Eluding in optical code-division multiple-access communication systems and in constructing protocol-sequence sets for the M-active-out-of-T users collision channel without feedback. In this paper we construct optimal constant weight cyclically permutable codes with length n, weight w, and a minimum Hamming distance 2w-2. Some of these codes coincide with the well-known design called a difference family. Some of the constructions use combinatorial structures with other applications in coding.>

Properties of nonlinear perfect binary codes are investigated and several new constructions of perfect codes are derived from these properties. An upper bound on the cardinality of the intersection of two perfect codes of length n is presented, and perfect codes whose intersection attains the upper bound are constructed for all n. As an immediate consequence of the proof of the upper bound the authors obtain a simple closed-form expression for the weight distribution of a perfect code. Furthermore, they prove that the characters of a perfect code satisfy certain constraints, and provide a sufficient condition for a binary code to be perfect. The latter result is employed to derive a generalization of the construction of Phelps (1983), which is shown to give rise to some perfect codes that are nonequivalent to the perfect codes obtained from the known constructions. Moreover, for any m/spl ges/4 the authors construct full-rank perfect binary codes of length 2/sup m/-1. These codes are obviously nonequivalent to any of the previously known perfect codes. Furthermore the latter construction exhibits the existence of full-rank perfect tilings. Finally, they construct a set of 2(2/sup cn/) nonequivalent perfect codes of length n, for sufficiently large n and a constant c=0.5-/spl epsiv/. Precise enumeration of the number of codes in this set provides a slight improvement over the results reported by Phelps.>

A construction for an infinite family of perfect mixed codes with covering radius 2 is presented. These are the first known nontrivial perfect mixed codes with covering radius greater than 1. Based on mixed codes, constructions for binary covering codes that lead to a considerable improvement of upper bounds on the sizes of covering codes are presented. These codes and some other codes can be obtained by the blockwise direct sum construction. Two infinite families of codes are of special interest. They are quasi-perfect, nonlinear, union of their disjoint translates covers the space, and their density as covering codes is remarkably low.>

It is proved that codes of length n, covering radius R, and minimum Hamming distance 2R-1 are normal if R does not divide n. Constructions for abnormal codes with covering radius R and minimum Hamming distance at least R-1 are given.>

Abstract In this paper, we present a construction of Euler circuits for some circular multistage interconnection networks, which have a uniform structure between consecutive stages.

A graph with unique path property (UPP) has 2/sup n/ vertices and a unique path of length n between every two vertices. These graphs are very important in the design of architectures and algorithms for interconnection networks. Given two UPP graphs, an algorithm is introduced to determine isomorphism between the graphs. A construction is given for nonisomorphic UPP graphs and a lower bound of 2/sup x/, where x=(2/sup n+1/-3-2)/9, nonisomorphic graphs with 2/sup n/ vertices is shown. UMFA (uniform minimal full access) networks are multistage interconnection networks that use the same interconnection pattern between every two consecutive stages. These networks are derived from UPP graphs, and the most known network of this type is the Omega network. The problem of rearrangeability of UMFA networks is discussed.>

Optimal codes that correct single errors and detect double errors within nibbles of power of two length are presented. For each n, a code of length n with the largest possible dimension which corrects single errors and detects double adjacent errors is presented. The problem of constructing optimal codes which correct single errors and detect double adjacent errors within nibbles of length l is discussed.>

Let $D( v )$ be the number of pairwise disjoint Steiner quadruple systems. A simple counting argument shows that $D( v )\leqq v - 3$. In this paper it is proved that $D( 2^k n )\geqq ( 2^k - 1 ) n,k\geqq 2$, if there exists a set of $3n$ pairwise disjoint Steiner quadruple systems of order $4n$ with a certain structure. This implies that $D( v )\geqq v - o( v )$ for infinitely many values of v. New lower bounds on $D( v )$ for many values of v that are not divisible by 4 are also given, and it is proved that $D( v )\geqq 2$ for all $v \equiv 2$ or $4(\bmod 6 ),v\geqq 8$.

New lower bounds on the sizes of asymmetric codes and unidirectional codes are presented. Various methods are used, three of them of special interest. The first is a partitioning method that is a modification of a method used to construct constant weight codes. The second is a combining codes method that is used to obtain a new code from a few others. The third method is shortening by weights that is applied on symmetric codes or on codes generated by the combining codes method. Tables for the sizes of codes of length n>

Two DC-free codes are presented with distance 2d, b>or=1 length 2n+2r(d-1) for d3, where r is the least integer >or=log/sub 2/ (2n+1). For the first code l=4, c=2, and the asymptotic rate of this code is 0.7925. For the second code l=6, c=3, and the asymptotic rate of this code is 0.8858. Asymptotically, these rates achieve the channel capacity. For small values of n these codes do not achieve the best rate. As an example of codes of short length with good rate, the author presents a (30, 10, 6, 4) DC-free block code with 2/sup 21/ codewords. A construction is presented for which from a given code C/sub 1/ of length n, even weight, and distance 4, the author obtains a (4n, l, c, 4) DC-free block code C/sub 2/, where l is 4, 5 or 6, and c is not greater than n+1 (but usually significantly smaller). The codes obtained by this method have good rates for small lengths. The encoding and decoding procedures for all the codes are discussed.>

Some new lower bounds are given for A(n,4,w), the maximum number of codewords in a binary code of length n, minimum distance 4, and constant weight w. In a number of cases the results significantly improve on the best bounds previously known.>

A construction of perfect maps, i.e. periodic r*v binary arrays in which each n*m binary matrix appears exactly once, is given. A similar construction leads to arrays in which only the zero n*m matrix does not appear and to a construction in which only a few n*m binary matrices do not appear. A generalization to the nonbinary case is given. The constructions involve an interesting problem in shift-register theory. The solution is given for almost all the case of this problem.>

This paper presents an algorithm for generating all the permutations defined by linear transformations on a shuffle-exchange network of $2^n $ processors in $2n - 1$ passes. The proposed algorithm generates any such permutation in $O(n\log ^2 n)$ elementary steps. The subclass of bit-permutations is generated in $O(n)$ steps.

It is shown that the number of de Bruijn sequences of ordernand linear complexitycis not a multiple of four for everynandc.

Two algorithms are presented for the generation of full-length shift-register cycles, also referred to as de Bruijn sequences. The first algorithm generates2^{k \cdot g(n,k)full cycles of length2^{n}, using3n + k \cdot g(n, k)bits of storage, wherekis a free parameter in the range1 \leq k \leq 2^{((n-4)/2)}, andg(n, k)is of the order ofn - 2 \log k. The second algorithm generates about2^{n^{2}/4}full cycles of length2^{n}, using aboutn^{2}/2bits of storage. In both algorithms, the time required to produce the next bit from the lastnbits is close ton. A possible application to the construction of stream ciphers is indicated.

The distribution\gamma (c, n)of de Bruijn sequences of ordernand linear complexitycis investigated. It is shown that forn \geq 4, \gamma (2^{n} - 1, n) \equiv 0 \pmod{8}, and fork \geq 3, \gamma (2^{2k} - 1,2k) \equiv 0 \pmod{l6}. It is also shown that\gamma (c, n) \equiv 0 \pmod{4}for allc, andn \geq 3such thatcnis even.

It is well known that the linear complexity of a de Bruijn sequenceSof length2^{n}is bounded below by2^{n- 1} + nforn \geq 3. It is shown that this lower bound is attainable for alln.