2017/10/20 by Baumbaugh, Travis, Diaz, Yariana, Friesenhahn, Sophia +2
#94B05 #94B60 (Primary) #94B65 (Secondary) #FOS: Computer and information sciences #Information Theory (cs.IT)
paper · doi:10.48550/arxiv.1710.07386
Batch codes, introduced by Ishai et al. encode a string x ∈ Σk into an m-tuple of strings, called buckets. In this paper we consider multiset batch codes wherein a set of t-users wish to access one bit of information each from the original string. We introduce a concept of optimal batch codes. We first show that binary Hamming codes are optimal batch codes. The main body of this work provides batch properties of Reed-Müller codes. We look at locality and availability properties of first order Reed-Müller codes over any finite field. We then show that binary first order Reed-Müller codes are optimal batch codes when the number of users is 4 and generalize our study to the family of binary Reed-Müller codes which have order less than half their length.