Yıl 2018, Cilt 5, Sayı 3, Sayfalar 153 - 165 2018-10-08
| | | |

## Batch codes from Hamming and Reed-Muller codes

#### Travis Baumbaugh [1] , Yariana Diaz [2] , Sophia Friesenhahn [3] , Felice Manganiello [4] , Alexander Vetter [5]

##### 14 45

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.
Batch codes, Hamming codes, Reed-Muller codes
• [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.
Birincil Dil en Mühendislik Makaleler Orcid: 0000-0002-3539-9758Yazar: Travis Baumbaugh (Sorumlu Yazar) Orcid: 0000-0003-0603-9750Yazar: Yariana Diaz Orcid: 0000-0001-8847-8962Yazar: Sophia Friesenhahn Orcid: 0000-0002-5764-569XYazar: Felice Manganiello Orcid: 0000-0003-2539-9815Yazar: Alexander Vetter
 Bibtex @araştırma makalesi { jacodesmath466634, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {Yıldız Teknik Üniversitesi}, year = {2018}, volume = {5}, pages = {153 - 165}, doi = {10.13069/jacodesmath.466634}, title = {Batch codes from Hamming and Reed-Muller codes}, key = {cite}, author = {Diaz, Yariana and Baumbaugh, Travis and Friesenhahn, Sophia and Manganiello, Felice and Vetter, Alexander} } APA Baumbaugh, T , Diaz, Y , Friesenhahn, S , Manganiello, F , Vetter, A . (2018). Batch codes from Hamming and Reed-Muller codes. Journal of Algebra Combinatorics Discrete Structures and Applications, 5 (3), 153-165. DOI: 10.13069/jacodesmath.466634 MLA Baumbaugh, T , Diaz, Y , Friesenhahn, S , Manganiello, F , Vetter, A . "Batch codes from Hamming and Reed-Muller codes". Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018): 153-165 Chicago Baumbaugh, T , Diaz, Y , Friesenhahn, S , Manganiello, F , Vetter, A . "Batch codes from Hamming and Reed-Muller codes". Journal of Algebra Combinatorics Discrete Structures and Applications 5 (2018): 153-165 RIS TY - JOUR T1 - Batch codes from Hamming and Reed-Muller codes AU - Travis Baumbaugh , Yariana Diaz , Sophia Friesenhahn , Felice Manganiello , Alexander Vetter Y1 - 2018 PY - 2018 N1 - doi: 10.13069/jacodesmath.466634 DO - 10.13069/jacodesmath.466634 T2 - Journal of Algebra Combinatorics Discrete Structures and Applications JF - Journal JO - JOR SP - 153 EP - 165 VL - 5 IS - 3 SN - -2148-838X M3 - doi: 10.13069/jacodesmath.466634 UR - http://dx.doi.org/10.13069/jacodesmath.466634 Y2 - 2018 ER - EndNote %0 Journal of Algebra Combinatorics Discrete Structures and Applications Batch codes from Hamming and Reed-Muller codes %A Travis Baumbaugh , Yariana Diaz , Sophia Friesenhahn , Felice Manganiello , Alexander Vetter %T Batch codes from Hamming and Reed-Muller codes %D 2018 %J Journal of Algebra Combinatorics Discrete Structures and Applications %P -2148-838X %V 5 %N 3 %R doi: 10.13069/jacodesmath.466634 %U 10.13069/jacodesmath.466634 ISNAD Baumbaugh, Travis , Diaz, Yariana , Friesenhahn, Sophia , Manganiello, Felice , Vetter, Alexander . "Batch codes from Hamming and Reed-Muller codes". Journal of Algebra Combinatorics Discrete Structures and Applications 5 / 3 (Ekim 2018): 153-165. http://dx.doi.org/10.13069/jacodesmath.466634