BZPEERPapers, people, evidence and research paths
Menu

Discover

SearchFind papers, people, topics, institutions and opportunities from one place.GraphSee how papers, authors, topics and evidence connect.

Research tools

HomeContinue from the papers, people and topics that matter now.CollectionsTurn saved papers into reading lists, evidence maps and shareable context.ResearchReconstruct the path that led you from search to paper to question.CollaborationMove from a paper, topic or expert request into a focused thread.PublishCreate full-text research articles with metadata, formulas and versions.

Network

ExpertsFind specialists whose work and reviews explain why they can help.CommunitiesJoin research groups organized around papers, topics and shared evidence.

Opportunities

ListingsBrowse roles, calls and collaborations connected to real research context.

Account

Log inReturn to your saved papers, graph views and active threads.Create accountStart saving papers, building a research trail and joining teams.
Log inCreate account

Source author record

Tuvi Etzion

Tuvi Etzion appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.

ResearcherUnclaimed source record
Information Theorymath.ITmath.CODiscrete Mathematics

Catalog footprint

What is connected

48works
4topics
4close collaborators

Actions

Connect this record

Log in to claim
Open graphBrowse works

Research graph

See the researcher in context

Open full explorer

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Published work

48 published item(s)

preprint2022arXiv

Bounds on the Size of Permutation Codes with the Kendall $τ$-Metric

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, $S_n$, 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 $S_n$, where $n>4$ is a prime or $4\leq n\leq 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 $S_n$ with even minimum Kendall $τ$-distance. We present larger single-error-correcting codes than the known ones in $S_5$ and $S_7$.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

Covering Sequences for $\ell$-Tuples

de Bruijn sequences of order $\ell$, i.e., sequences that contain each $\ell$-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 rate of $1/2$. To overcome this low rate, we study $\ell$-tuples covering sequences, which impose that each $\ell$-tuple appears at least once as a window in the sequence. The cardinality of this family of sequences is analyzed while assuming that $\ell$ 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 $\ell$ such that the redundancy of the set of $\ell$-tuples covering sequences is at most a single symbol. Lastly, we present efficient encoding and decoding schemes for $\ell$-tuples covering sequences that meet this bound.

0 citations0 reviewsNo code linkedOpen access
preprint2022arXiv

On the Size of Balls and Anticodes of Small Diameter under the Fixed-Length Levenshtein Metric

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, the Fixed 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.

0 citations0 reviewsNo code linkedOpen access
preprint2021arXiv

Block-avoiding point sequencings

Let $n$ and $\ell$ be positive integers. Recent papers by Kreher, Stinson and Veitch have explored variants of the problem of ordering the points in a triple system (such as a Steiner triple system, directed triple system or Mendelsohn triple system) on $n$ points so that no block occurs in a segment of $\ell$ consecutive entries (thus the ordering is locally block-avoiding). We describe a greedy algorithm which shows that such an ordering exists, provided that $n$ is sufficiently large when compared to $\ell$. This algorithm leads to improved bounds on the number of points in cases where this was known, but also extends the results to a significantly more general setting (which includes, for example, orderings that avoid the blocks of a design). Similar results for a cyclic variant of this situation are also established. We construct Steiner triple systems and quadruple systems where $\ell$ can be large, showing that a bound of Stinson and Veitch is reasonable. Moreover, we generalise the Stinson--Veitch bound to a wider class of block designs and to the cyclic case. The results of Kreher, Stinson and Veitch were originally inspired by results of Alspach, Kreher and Pastine, who (motivated by zero-sum avoiding sequences in abelian groups) were interested in orderings of points in a partial Steiner triple system where no segment is a union of disjoint blocks. Alspach~\emph{et al.}\ show that, when the system contains at most $k$ pairwise disjoint blocks, an ordering exists when the number of points is more than $15k-5$. By making use of a greedy approach, the paper improves this bound to $9k+O(k^{2/3})$.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Constrained de Bruijn Codes: Properties, Enumeration, Constructions, and Applications

The de 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 sequences in the de Bruijn graph are defined. These sequences can be also defined and viewed as constrained sequences. Hence, they will be called constrained de Bruijn sequences and a set of such sequences will be called a 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 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 on previously known codes.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Explicit Baranyai Partitions for Quadruples, Part I: Quadrupling Constructions

It is well known that, whenever $k$ divides $n$, the complete $k$-uniform hypergraph on $n$ vertices can be partitioned into disjoint perfect matchings. Equivalently, the set of $k$-subsets of an $n$-set can be partitioned into parallel classes so that each parallel class is a partition of the $n$-set. This result is known as Baranyai's theorem, which guarantees the existence of \emph{Baranyai partitions}. Unfortunately, the proof of Baranyai's theorem uses network flow arguments, making this result non-explicit. In particular, there is no known method to produce Baranyai partitions in time and space that scale linearly with the number of hyperedges in the hypergraph. It is desirable for certain applications to have an explicit construction that generates Baranyai partitions in linear time. Such an efficient construction is known for $k=2$ and $k=3$. In this paper, we present an explicit recursive quadrupling construction for $k=4$ and $n=4t$, where $t \equiv 0,3,4,6,8,9 ~(\text{mod}~12)$. In a follow-up paper (Part II), the other values of~$t$, namely $t \equiv 1,2,5,7,10,11 ~(\text{mod}~12)$, will be considered.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Large Sets with Multiplicity

Large sets of combinatorial designs has always been a fascinating topic in design theory. These designs form a partition of the whole space into combinatorial designs with the same parameters. In particular, a large set of block designs, whose blocks are of size $k$ taken from an $n$-set, is a partition of all the $k$-subsets of the $n$-set into disjoint copies of block designs, defined on the $n$-set, and with the same parameters. The current most intriguing question in this direction is whether large sets of Steiner quadruple systems exist and to provide explicit constructions for those parameters for which they exist. In view of its difficulty no one ever presented an explicit construction even for one nontrivial order. Hence, we seek for related generalizations. As generalizations, to the existence question of large sets, we consider two related questions. The first one to provide constructions for sets on Steiner systems in which each block (quadruple or a $k$-subset) is contained in exactly $μ$ systems. The second question is to provide constructions for large set of H-designs (mainly for quadruples, but also for larger block size). We prove the existence of such systems for many parameters using orthogonal arrays, perpendicular arrays, ordered designs, sets of permutations, and one-factorizations of the complete graph.

0 citations0 reviewsNo code linkedOpen access
preprint2020arXiv

Subspace Packings -- Constructions and Bounds

The Grassmannian $\mathcal{G}_q(n,k)$ is the set of all $k$-dimensional subspaces of the vector space $\mathbb{F}_q^n$. Kötter and Kschischang showed that codes in Grassmannian space can be used for error-correction in random network coding. On the other hand, these codes are $q$-analogs of codes in the Johnson scheme, i.e., constant dimension codes. These codes of the Grassmannian $\mathcal{G}_q(n,k)$ also form a family of $q$-analogs of block designs and they are called subspace designs. In this paper, we examine one of the last families of $q$-analogs of block designs which was not considered before. This family, called subspace packings, is the $q$-analog of packings, and was considered recently for network coding solution for a family of multicast networks called the generalized combination networks. A subspace packing $t$-$(n,k,λ)_q$ is a set $\mathcal{S}$ of $k$-subspaces from $\mathcal{G}_q(n,k)$ such that each $t$-subspace of $\mathcal{G}_q(n,t)$ is contained in at most $λ$ elements of $\mathcal{S}$. The goal of this work is to consider the largest size of such subspace packings. We derive a sequence of lower and upper bounds on the maximum size of such packings, analyse these bounds, and identify the important problems for further research in this area.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Constructions of High-Rate MSR Codes over Small Fields

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, which are not access-optimal, and do not necessarily attain the sub-packetization bound. 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 $\ell$ in each node, the entire stored data can be recovered from any $2\log_2 \ell$ for 2 parity nodes, and either $3\log_3\ell$ or $4\log_3\ell$ for 3 parity nodes. 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 generator matrix of these codes is based on perfect matchings of complete graphs and hypergraphs, and on a rational canonical form of matrices. The goal of this paper is to provide a construction of such optimal codes over the smallest possible finite fields. 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 the field size is $6\log_3 \ell+1$ (or $3\log_3 \ell+1$ for fields with characteristic 2), and in the second construction the field size is larger, yet linear in $\log_3\ell$. Both constructions with 3 parities provide a significant improvement over existing previous works, since only non-explicit constructions with exponential field size (in $\log_3\ell$) were known so far.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

PIR Array Codes with Optimal PIR Rates

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/\omegaR)$ of the bits of the database; here $\omegaR$ is a fixed rational number with $\omegaR > 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 < \omegaR \leq 2$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Regular Graphs with Forbidden Subgraphs of $K_n$ with $k$ Edges

In this paper we raise a variant of a classic problem in extremal graph theory, which is motivated by a design of fractional repetition codes, a model in distributed storage systems. For any feasible positive integers $d\geq 3$, $n \geq 3$, and $k$, where $n-1 \leq k \leq \binom{n}{2}$, what is the minimum possible number of vertices in a $d$-regular undirected graph whose subgraphs with $n$ vertices contain at most $k$ edges? The goal of this paper is to give the exact number of vertices for each instance of the problem and also to provide some bounds for general values of $n$, $d$, and $k$. A few general bounds with some exact values, for this Turán-type problem, are given. We present an almost complete solution for $3 \leq n \leq 5$.

0 citations0 reviewsNo code linkedOpen access
preprint2016arXiv

Vector Network Coding Based on Subspace Codes Outperforms Scalar Linear Network Coding

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 the order of $q^{(\ell-1)t^2/\ell}-q^t$, for any $q \geq 2$, where $t$ denotes the dimension of the vector solution, and the number of messages is $2 \ell$, ${\ell \geq 2}$. 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. Similar results are given for any number of odd messages greater than two. The results are obtained by considering several multicast networks which are variations of the well-known combination network.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Binary Polarization Kernels from Code Decompositions

In this paper, code decompositions (a.k.a. code nestings) are used to design binary polarization kernels. The proposed kernels are in general non-linear. They provide a better polarization exponent than the previously known kernels of the same dimensions. In particular, non-linear 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Equidistant Codes in the Grassmannian

Equidistant codes over vector spaces are considered. For $k$-dimensional subspaces over a large vector space the largest code is always a sunflower. We present several simple constructions for such codes which might produce the largest non-sunflower codes. A novel construction, based on the Plücker embedding, for 1-intersecting codes of $k$-dimensional subspaces over $\F_q^n$, $n \geq \binom{k+1}{2}$, where the code size is $\frac{q^{k+1}-1}{q-1}$ is presented. Finally, we present a related construction which generates equidistant constant rank codes with matrices of size $n \times \binom{n}{2}$ over $\F_q$, rank $n-1$, and rank distance $n-1$.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

On the Structure of the $q$-Fano Plane

The $q$-Fano plane is the $q$-analog of the Steiner system $S(2,3,7)$. For any given prime power $q$ it is not known whether the $q$-Fano plane exists or not. We consider the structure of the $q$-Fano plane for any given $q$ and conclude that most of its structure is known. Even so, we were unable to determine whether it exists or not. A special attention is given for the case $q=2$ which was considered by most researchers before.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Fractional Repetition Codes and Fractional Repetition Batch Codes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Optimal Fractional Repetition Codes based on Graphs and Designs

Fractional repetition (FR) codes is a family of codes for distributed storage systems that allow for uncoded exact repairs having the minimum repair bandwidth. However, in contrast to minimum bandwidth regenerating (MBR) codes, where a random 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 to MBR codes. In this work, we consider bounds on the fractional repetition 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 fractional repetition 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.

0 citations0 reviewsNo code linkedOpen access
preprint2015arXiv

Subspace Polynomials and Cyclic Subspace Codes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

A New Construction for Constant Weight Codes

A new construction for constant weight codes is presented. The codes are constructed from $k$-dimensional subspaces of the vector space $\F_q^n$. These subspaces form a constant dimension code in the Grassmannian space $\cG_q(n,k)$. Some of the constructed codes are optimal constant weight codes with parameters not known before. An efficient algorithm for error-correction is given for the constructed codes. If the constant dimension code has an efficient encoding and decoding algorithms then also the constructed constant weight code has an efficient encoding and decoding algorithms.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Constructions of Snake-in-the-Box Codes for Rank Modulation

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 by using the "push-to-the-top" operation, and the distance measure is defined on permutations. In this paper the Kendall's $τ$-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 $M_{2n+1}=((2n+1)(2n)-1)M_{2n-1}$ for permutations of $S_{2n+1}$, from a snake of length $M_{2n-1}$ for permutations of~$S_{2n-1}$. Thus, we have $\lim\limits_{n\to \infty} \frac{M_{2n+1}}{S_{2n+1}}\approx 0.4338$, improving on the previous known ratio of $\lim\limits_{n\to \infty} \frac{1}{\sqrt{πn}}$. By using the general method we also present a direct construction. This direct construction is based on necklaces and it might yield snakes of length $\frac{(2n+1)!}{2} -2n+1$ for permutations of $S_{2n+1}$. The direct construction was applied successfully for $S_7$ and $S_9$, and hence $\lim\limits_{n\to \infty} \frac{M_{2n+1}}{S_{2n+1}}\approx 0.4743$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Distributed Storage Systems based on Equidistant Subspace Codes

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

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Local Rank Modulation for Flash Memories II

Local rank modulation scheme was suggested recently for representing information in flash memories in order to overcome drawbacks of rank modulation. For $0 < s\leq t\leq n$ with $s$ divides $n$, an $(s,t,n)$-LRM scheme is a local rank modulation scheme where the $n$ cells are locally viewed cyclically through a sliding window of size $t$ resulting in a sequence of small permutations which requires less comparisons and less distinct values. The gap between two such windows equals to $s$. In this work, encoding, decoding, and asymptotic enumeration of the $(1,3,n)$-LRM scheme is studied. The techniques which are suggested have some generalizations for $(1,t,n)$-LRM, $t > 3$, 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$.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Perfect Permutation Codes with the Kendall's $τ$-Metric

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, $S_n$, using the Kendall's $τ$-metric. We prove that there are no perfect single-error-correcting codes in $S_n$, where $n>4$ is a prime or $4\leq n\leq 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 $S_5$. Finally, we examine the existence problem of diameter perfect codes in $S_n$ and obtain a new upper bound on the size of a code in $S_n$ with even minimum Kendall's $τ$-distance.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

Systematic Codes for Rank Modulation

The goal of this paper is to construct systematic error-correcting codes for permutations and multi-permutations in the Kendall's $τ$-metric. These codes are important in new applications such as rank modulation for flash memories. The construction is based on error-correcting codes for multi-permutations and a partition of the set of permutations into error-correcting codes. For a given large enough number of information symbols $k$, and for any integer $t$, we present a construction for ${(k+r,k)}$ systematic $t$-error-correcting codes, for permutations from $S_{k+r}$, with less redundancy symbols than the number of redundancy symbols in the codes of the known constructions. In particular, for a given $t$ and for sufficiently large $k$ we can obtain $r=t+1$. The same construction is also applied to obtain related systematic error-correcting codes for multi-permutations.

0 citations0 reviewsNo code linkedOpen access
preprint2014arXiv

The q-Analog of the Middle Levels Problem

The well-known middle levels problem is to find a Hammiltonian cycle in the graph induced from the binary Hamming graph $\cH_2(2k+1)$ by the words of weight $k$ or $k+1$. In this paper we define the $q$-analog of the middle levels problem. Let $n=2k+1$ and let $q$ be a power of a prime number. Consider the set of $(k+1)$-dimensional subspaces and the set of $k$-dimensional subspaces of $\F_q^n$. Can these subspaces be ordered in a way that for any two adjacent subspaces $X$ and $Y$, either $X \subset Y$ or $Y \subset X$? A construction method which yields many Hamiltonian cycles for any given $q$ and $k=2$ is presented.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Existence of $q$-Analogs of Steiner Systems

Let $\F_q^n$ be a vector space of dimension $n$ over the finite field $\F_q$. A $q$-analog of a Steiner system (briefly, a $q$-Steiner system), denoted $S_q[t,k,n]$, is a set $S$ of $k$-dimensional subspaces of $\F_q^n$ such that each $t$-dimensional subspace of $\F_q^n$ is contained in exactly one element of $S$. Presently, $q$-Steiner systems are known only for $t=1$, and in the trivial cases $t = k$ and $k = n$. Invthis paper, the first nontrivial $q$-Steiner systems with $t >= 2$ are constructed. Specifically, several nonisomorphic $q$-Steiner systems $S_2[2,3,13]$ are found by requiring that their automorphism groups contain the normalizer of a Singer subgroup of $\GL(13,2)$. This approach leads to an instance of the exact cover problem, which turns out to have many solutions.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Partial k-Parallelisms in Finite Projective Spaces

In this paper we consider the following question. What is the maximum number of pairwise disjoint $k$-spreads which exist in PG(n,q)? We prove that if k+1 divides n+1 and n>k then there exist at least two disjoint k-spreads in PG(n,q) and there exist at least $2^{k+1}-1$ pairwise disjoint $k$-spreads in PG(n,2). We also extend the known results on parallelism in a projective geometry from which the points of a given subspace were removed.

0 citations0 reviewsNo code linkedOpen access
preprint2013arXiv

Problems on q-Analogs in Coding Theory

The interest in $q$-analogs of codes and designs has been increased in the last few years as a consequence of their new application in error-correction for random network coding. There are many interesting theoretical, algebraic, and combinatorial coding problems concerning these q-analogs which remained unsolved. The first goal of this paper is to make a short summary of the large amount of research which was done in the area mainly in the last few years and to provide most of the relevant references. The second goal of this paper is to present one hundred open questions and problems for future research, whose solution will advance the knowledge in this area. The third goal of this paper is to present and start some directions in solving some of these problems.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Automorphisms of Codes in the Grassmann Scheme

Two mappings in a finite field, the Frobenius mapping and the cyclic shift mapping, are applied on lines in PG($n,p$) or codes in the Grassmannian, to form automorphisms groups in the Grassmanian and in its codes. These automorphisms are examined on two classical coding problems in the Grassmannian. The first is the existence of a parallelism with lines in the related projective geometry and the second is the existence of a Steiner structure. A computer search was applied to find parallelisms and codes. A new parallelism of lines in PG(5,3) was formed. A parallelism with these parameters was not known before. A large code which is only slightly short of a Steiner structure was formed.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Codes and Designs Related to Lifted MRD Codes

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 which attain these bounds are constructed. These codes are the largest known codes for the given parameters. These transversal designs can be also 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.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Coding for the Lee and Manhattan Metrics with Weighing Matrices

This paper has two goals. The first one is to discuss good codes for packing problems in the Lee and Manhattan metrics. The second one is to consider weighing matrices for some of these coding problems. Weighing matrices were considered as building blocks for codes in the Hamming metric in various constructions. In this paper we will consider mainly two types of weighing matrices, namely conference matrices and Hadamard matrices, to construct codes in the Lee (and Manhattan) metric. We will show that these matrices have some desirable properties when considered as generator matrices for codes in these metrics. Two related packing problems will be considered. The first is to find good codes for error-correction (i.e. dense packings of Lee spheres). The second is to transform the space in a way that volumes are preserved and each Lee sphere (or conscribed cross-polytope), in the space, will be transformed to a shape inscribed in a small cube.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Covering of Subspaces by Subspaces

Lower and upper bounds on the size of a covering of subspaces in the Grassmann graph $\cG_q(n,r)$ by subspaces from the Grassmann graph $\cG_q(n,k)$, $k \geq r$, are discussed. The problem is of interest from four points of view: coding theory, combinatorial designs, $q$-analogs, and projective geometry. In particular we examine coverings based on lifted maximum rank distance codes, combined with spreads and a recursive construction. New constructions are given for $q=2$ with $r=2$ or $r=3$. We discuss the density for some of these coverings. Tables for the best known coverings, for $q=2$ and $5 \leq n \leq 10$, are presented. We present some questions concerning possible constructions of new coverings of smaller size.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

q-Analogs of Steiner Systems

A Steiner structure $\dS = \dS_q[t,k,n]$ is a set of $k$-dimensional subspaces of $\F_q^n$ such that each $t$-dimensional subspace of $\F_q^n$ is contained in exactly one subspace of $\dS$. Steiner structures are the $q$-analogs of Steiner systems; they are presently known to exist only for $t = 1$, $t=k$, and\linebreak for $k = n$. The existence of nontrivial $q$-analogs of Steiner systems has occupied mathematicians for over three decades. In fact, it was conjectured that they do not exist. In this paper, we show that nontrivial Steiner structures do exist. First, we describe a general method which may be used to produce Steiner structures. The method uses two mappings in a finite field: the Frobenius map and the cyclic shift map. These maps are applied to codes in the Grassmannian, in order to form an automorphism group of the Steiner structure. Using this method, assisted by an exact-cover computer search, we explicitly generate a Steiner structure $\dS_2[2,3,13]$. We conjecture that many other Steiner structures, with different parameters, exist.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tilings by $(0.5,n)$-Crosses and Perfect Codes

The existence question for tiling of the $n$-dimensional Euclidian space by crosses is well known. A few existence and nonexistence results are known in the literature. Of special interest are tilings of the Euclidian space by crosses with arms of length one, known also 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. We prove that an integer tiling for such a shape exists if and only if $n=2^t-1$ or $n=3^t-1$, $t>0$. A strong connection of these tilings to binary and ternary perfect codes in the Hamming scheme is shown.

0 citations0 reviewsNo code linkedOpen access
preprint2012arXiv

Tilings with $n$-Dimensional Chairs and their Applications to Asymmetric Codes

An $n$-dimensional chair consists of an $n$-dimensional box from which a smaller $n$-dimensional box is removed. A tiling of an $n$-dimensional chair has two nice applications in coding for write-once memories. The first one is in the design of codes which correct asymmetric errors with limited-magnitude. The second one is in the design of $n$ cells $q$-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 an $n$-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.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Linearity and Complements in Projective Space

The projective space of order $n$ over the finite field $\Fq$, denoted here as $\Ps$, is the set of all subspaces of the vector space $\Fqn$. The projective space can be endowed with distance function $d_S(X,Y) = \dim(X) + \dim(Y) - 2\dim(X\cap Y)$ which turns $\Ps$ into a metric space. With this, \emph{an $(n,M,d)$ code $\C$ in projective space} is a subset of $\Ps$ 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 $ρ$ packet erasures introduced (adversarially) anywhere in the network as long as $2t + 2ρ< d$. This motivates new interest in such codes. In this paper, we examine the two fundamental concepts of \myemph{complements} and \myemph{linear codes} in the context of $\Ps$. These turn out to be considerably more involved than their classical counterparts. These concepts are examined from two different points of view, coding theory and lattice theory. Our discussion reveals some surprised phenomena of these concepts in $\Ps$ and leaves some interesting problems for further research.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

Product Constructions for Perfect Lee Codes

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 forty 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 the Manhattan metrics are also discussed.

0 citations0 reviewsNo code linkedOpen access
preprint2011arXiv

The asymptotic behavior of Grassmannian codes

The iterated Johnson bound is the best known upper bound on a size of an error-correcting code in the Grassmannian $\mathcal{G}_q(n,k)$. The iterated Schönheim bound is the best known lower bound on the size of a covering code in $\mathcal{G}_q(n,k)$. We use probabilistic methods to prove that both bounds are asymptotically attained for fixed $k$ and fixed radius, as $n$ approaches infinity. We also determine the asymptotics of the size of the best Grassmannian codes and covering codes when $n-k$ and the radius are fixed, as $n$ approaches infinity.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Dense Error-Correcting Codes in the Lee Metric

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Enumerative Coding for Grassmannian Space

The Grassmannian space $\Gr$ is the set of all $k-$dimensional subspaces of the vector space~\smash{$\F_q^n$}. 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 $\F_q^n$. One enumerative coding method is based on a Ferrers diagram representation and on an order for $\Gr$ based on this representation. The complexity of this enumerative coding is $O(k^{5/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)$ digits operations. A combination of the two methods reduces the complexity on average by a constant factor.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

High Dimensional Error-Correcting Codes

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.

0 citations0 reviewsNo code linkedOpen access
preprint2010arXiv

Large Constant Dimension Codes and Lexicodes

Constant dimension codes, with a prescribed minimum distance, have found recently an application in network coding. All the codewords in such a code are subspaces of $\F_q^n$ with a given dimension. A computer search for large constant dimension codes is usually inefficient since the search space domain is extremely large. Even so, we found that some constant dimension lexicodes are larger than other known codes. We show how to make the computer search more efficient. In this context we present a formula for the computation of the distance between two subspaces, not necessarily of the same dimension.

0 citations0 reviewsNo code linkedOpen access