- 14:40 Multiset combinatorial batch codes
Hui Zhang (Technion - Israel Institute of
Technology, Israel); Eitan Yaakobi (Technion, Israel); Natalia
Silberstein (Yahoo! Labs, Israel)
Batch codes, first introduced by Ishai,
Kushilevitz, Ostrovsky, and Sahai, mimic a distributed storage of a set
of $n$ data items on $m$ servers, in such a way that any batch of $k$
data items can be retrieved by reading at most some $t$ symbols from
each server. Combinatorial batch codes, are replication-based
batch codes in which each server stores a subset of the data items.
In this paper, we propose a generalization of combinatorial batch codes,
called multiset combinatorial batch codes (MCBC), in
which $n$ data items are stored in $m$ servers, such that any multiset
request of $k$ items, where any item is requested at most $r$ times, can
be retrieved by reading at most $t$ items from each server. The setup
of this new family of codes is motivated by recent work on codes which
enable high availability and parallel reads in distributed storage
systems. The main problem under this paradigm is to minimize the number
of items stored in the servers, given the values of $n,m,k,r,t$, which
is denoted by $N(n,k,m,t;r)$. We first give a necessary and sufficient
condition for the existence of MCBCs. Then, we present several bounds on
$N(n,k,m,t;r)$ and constructions of MCBCs. In particular, we determine
the value of $N(n,k,m,1;r)$ for any $n\geq
\left\lfloor\frac{k-1}{r}\right\rfloor{m\choose k-1}-(m-k+1)A(m,4,k-2)$,
where $A(m,4,k-2)$ is the maximum size of a binary constant weight code
of length $m$, distance four and weight $k-2$. We also determine the
exact value of $N(n,k,m,1;r)$ when $r\in\{k,k-1\}$ or $k=m$.
pp. 2188-2192
- 15:00 Structured Spherical Codes With Asymptotically Optimal Distance Distributions
Robert M. Taylor, Jr. and Lamine Mili (Virginia
Tech, USA); Amir I Zaghloul (US Army Research Laboratory & Virginia
Tech, USA)
We introduce a new geometric construction of
cyclic group codes in odd-dimensional spaces formed by intersecting
even-dimensional constant curvature curves with hyperplanes of one less
dimension. This allows us to recast the cyclic group code as a uniform
sampling of a constant curvature curve whereby the design of the
constant curvature curve controls code performance. Using a tool from
knot theory known as the circumradius function, we derive properties of
cyclic group codes from properties of the constant curvature curve
passing through every point of the spherical code. By relating the
distribution of the squared circumradius function of the connecting
curve to the distribution of the pairwise distances of the cyclic group
code, we show that the distance spectrum of cyclic group codes achieves
optimality in the sense of matching the random spherical code distance
distribution bound as the block length grows large.
pp. 2193-2197
- 15:20 Weight Spectrum of Quasi-Perfect Binary Codes with Distance 4
Valentin Afanassiev (Intitute Problems of
Information Transmission, Russia); Alexander Davydov (Institute for
Information Transmission Problem, Russia)
We consider the weight spectrum of a class of
quasi-perfect binary linear codes with code distance 4. For example,
extended Hamming code and Panchenko code are the known members of this
class. Also, it is known that in many cases Panchenko code has the
minimal number of weight 4 codewords. We give exact recursive formulas
for the weight spectrum of quasi-perfect codes and their dual codes. As
an example of application of the weight spectrum we derive a lower
estimate for the conditional probability of correction of erasure
patterns of high weights (equal to or greater than code distance).
pp. 2198-2202
- 15:40 Kronecker Product and Tiling of Permutation Arrays for Hamming Distances
Sergey Bereg, Luis Gerardo Mojica de la Vega, Linda Morales and I. Hal Sudborough (University of Texas at Dallas, USA)
We give improved lower bounds for M(n,d), for
various positive integers d and n with d<n, where M(n,d) is the
largest number of permutations on n symbols with pairwise Hamming
distance at least d. Permutation arrays are used for constructing error
correcting permutation codes, which have been proposed for power-line
communications. We describe two techniques, which use Kronecker products
and a "tiling" operation. Our techniques improve the size of
permutation arrays, and improve lower bounds on M(n,d), for infinitely
many n and d, d<n.
pp. 2203-2207
- 16:00 Performance of Spinal Codes with Sliding Window Decoding
Weiqiang Yang (Xidian University, P.R. China);
Ying Li (University of Xidian, P.R. China); Xiaopu Yu (Xidian
University, P.R. China)
In this paper, we focus on the finite-length
performance of spinal codes with a sliding window decoder over binary
erasure channel. An expression of the error probability of spinal codes
is derived. Particularly, we also derive an expression of the error
probability of spinal codes with some known tail bits, which can improve
the error-control performance. Moreover, easier-to-compute upper and
lower bounds on the error probability are also provided. Simulation
results show that the error-control performance can be improved by
introducing known tail bits and the performance becomes better with the
increase of the maximum window length. Finally, the derived bounds can
well evaluate the error performance of spinal codes.
pp. 2208-2212