Batch codes from Hamming and Reed-Muller codes
DOI:
https://doi.org/10.13069/jacodesmath.466634Keywords:
Batch codes, Hamming codes, Reed-Muller codesAbstract
Batch codes, introduced by Ishai \textit{et al.}, encode a string $x \in \Sigma^{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-Muller codes. We look at locality and availability properties of first order Reed-Muller codes over any finite field. We then show that binary first order Reed-Muller codes are optimal batch codes when the number of users is 4 and generalize our study to the family of binary Reed-Muller codes which have order less than half their length.
Received: 24 October 2017 Accepted: 5 September 2018Downloads
References
E. F. Assmus and J. D. Key, Designs and Their Codes, Cambridge Tracts in Mathematics, vol. 103, Cambridge University Press, Cambridge, 1992.
S. Bhattacharya, S. Ruj, and B. Roy, Combinatorial batch codes: A lower bound and optimal constructions, Adv. Math. Commun. 6(2) (2012) 165–174.
C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes 12(1) (2011) 11–23.
A. G. Dimakis, K. Ramchandran, Y. Wu, and C. Suh, A survey on network codes for distributed storage, Proc. IEEE 99(3) (2011) 476–489.
P. Huang, E. Yaakobi, H. Uchikawa, and P. H. Siegel, Binary linear locally repairable codes, IEEE Trans. Inform. Theory 62(11) (2016) 6268–6283.
Y. Ishai, E. Kushilevitz, R. Ostrovsky, and A. Sahai, Batch codes and their applications, In: Proc. Thirty-Sixth Annual ACM Symposium on Theory of Computing (STOC '04), ACM, New York (2004) 262–271.
H. Lipmaa and V. Skachek, Linear batch codes, In: Á. Barbero et al. (Eds.), Coding Theory and Applications, CIM Series in Mathematical Sciences, vol. 3, Springer, Cham (2015) 245–253.
F. J. MacWilliams and N. J. A. Sloane, The Theory of Error-Correcting Codes, North-Holland Publishing Co., Amsterdam, 1977.
M. B. Paterson, D. R. Stinson, and R. Wei, Combinatorial batch codes, Adv. Math. Commun. 3(1) (2009) 13–27.
A.–E. Riet, V. Skachek, and E. K. Thomas, Asynchronous batch and PIR codes from hypergraphs, In: 2018 IEEE Information Theory Workshop (ITW), Guangzhou, China (2018) 1–5.
N. Silberstein and A. Gál, Optimal combinatorial batch codes based on block designs, Des. Codes Cryptogr. 78(2) (2016) 409–424.
V. Skachek, Batch and PIR codes and their connections to locally repairable codes, In: M. Greferath et al. (Eds.), Network Coding and Subspace Designs, Signals and Communication Technology, Springer, Cham (2018) 427–442.
E. K. Thomas and V. Skachek, Constructions and bounds for batch codes with small parameters, In: E. Martínez-Moro (Ed.), Coding Theory and Applications, Lecture Notes in Comput. Sci., vol. 10495, Springer, Cham (2017) 283–295.
