Batch Codes from Hamming and Reed-Muller Codes

Travis Alan Baumbaugh, Yariana Diaz, Sophia Friesenhahn, Felice Manganiello, Alexander Vetter


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.

Full Text:



E. F. Assmus, J. D. Key, Designs and Their Codes, volume 103 of Cambridge Tracts in Mathematics, Cambridge University Press, Cambridge, 1992.

S. Bhattacharya, S. Ruj, B. Roy, Combinatorial batch codes: A lower bound and optimal constructions, Adv. Math. Commun. 6(2) (2012) 165–174.

C. Bujtás, 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, C. Suh, A survey on network codes for distributed storage, Proc. IEEE 99(3) (2011) 476–489.

P. Huang, E. Yaakobi, H. Uchikawa, P. H. Siegel, Binary linear locally repairable codes, IEEE Trans. Inform. Theory 62(11) (2016) 6268–6283.

Y. Ishai, E. Kushilevitz, R. Ostrovsky, A. Sahai, Batch codes and their applications, Proc. 36th Annu. ACM Symp. Theory Comput. (2004) 262–271.

H. Lipmaa, V. Skachek, Linear batch codes, In Coding Theory and Applications, CIM Series in Mathematical Sciences 3 (2015) 245–253.

F. J. MacWilliams, N. J. A. Sloane. The Theory of Error–correcting Codes, North–Holland Publishing Co., Amsterdam–New York–Oxford, 1977.

M. B. Paterson, D. R. Stinson, R. Wei, Combinatorial batch codes, Adv. Math. Commun. 3(1) (2009) 13–27.

A.–E. Riet, V. Skachek, E. K. Thomas, Asynchronous batch and PIR codes from hypergraphs, preprint, 2018, arXiv:1806.00592.

N. Silberstein, 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 Network Coding and Subspace Designs, Signals Commun. Technol., Springer, Cham, (2018) 427–442.

E. K. Thomas, V. Skachek, Constructions and bounds for batch codes with small parameters, In Coding Theory and Applications, Springer, Cham, (2017) 283–295.


  • There are currently no refbacks.

ISSN: 2148-838X