Batch codes from Hamming and Reed-Muller codes
Batch codes from Hamming and Reed-Muller codes
Batch codes, introduced by Ishai 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.
___
- [1] E. F. Assmus, J. D. Key, Designs and Their Codes, volume 103 of Cambridge Tracts in Mathematics,
Cambridge University Press, Cambridge, 1992.
- [2] S. Bhattacharya, S. Ruj, B. Roy, Combinatorial batch codes: A lower bound and optimal constructions,
Adv. Math. Commun. 6(2) (2012) 165–174.
- [3] C. Bujtás, Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math.
Notes 12(1) (2011) 11–23.
- [4] A. G. Dimakis, K. Ramchandran, Y. Wu, C. Suh, A survey on network codes for distributed storage,
Proc. IEEE 99(3) (2011) 476–489.
- [5] P. Huang, E. Yaakobi, H. Uchikawa, P. H. Siegel, Binary linear locally repairable codes, IEEE Trans.
Inform. Theory 62(11) (2016) 6268–6283.
- [6] Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Batch codes and their applications, Proc. 36th
Annu. ACM Symp. Theory Comput. (2004) 262–271.
- [7] H. Lipmaa, V. Skachek, Linear batch codes, In Coding Theory and Applications, CIM Series in
Mathematical Sciences 3 (2015) 245–253.
- [8] F. J. MacWilliams, N. J. A. Sloane. The Theory of Error–correcting Codes, North–Holland Publishing
Co., Amsterdam–New York–Oxford, 1977.
- [9] M. B. Paterson, D. R. Stinson, R. Wei, Combinatorial batch codes, Adv. Math. Commun. 3(1) (2009)
13–27.
- [10] A.–E. Riet, V. Skachek, E. K. Thomas, Asynchronous batch and PIR codes from hypergraphs,
preprint, 2018, arXiv:1806.00592.
- [11] N. Silberstein, A. Gál, Optimal combinatorial batch codes based on block designs, Des. Codes Cryptogr.
78(2) (2016) 409–424.
- [12] V. Skachek, Batch and PIR codes and their connections to locally repairable codes, In Network
Coding and Subspace Designs, Signals Commun. Technol., Springer, Cham, (2018) 427–442.
- [13] E. K. Thomas, V. Skachek, Constructions and bounds for batch codes with small parameters, In
Coding Theory and Applications, Springer, Cham, (2017) 283–295.