Year 2018, Volume 5, Issue 3, Pages 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]

33 160

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.
Primary Language en
Subjects Engineering
Journal Section Articles
Authors

Orcid: 0000-0002-3539-9758
Author: Travis Baumbaugh (Primary Author)

Orcid: 0000-0003-0603-9750
Author: Yariana Diaz

Orcid: 0000-0001-8847-8962
Author: Sophia Friesenhahn

Orcid: 0000-0002-5764-569X
Author: Felice Manganiello

Orcid: 0000-0003-2539-9815
Author: Alexander Vetter

Dates

Publication Date: October 8, 2018

Bibtex @research article { jacodesmath466634, journal = {Journal of Algebra Combinatorics Discrete Structures and Applications}, issn = {}, eissn = {2148-838X}, address = {Yildiz Technical University}, year = {2018}, volume = {5}, pages = {153 - 165}, doi = {10.13069/jacodesmath.466634}, title = {Batch codes from Hamming and Reed-Muller codes}, key = {cite}, author = {Baumbaugh, Travis and Diaz, Yariana 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 <http://dergipark.org.tr/jacodesmath/issue/16096/466634>
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 - https://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 (October 2018): 153-165. https://doi.org/10.13069/jacodesmath.466634
AMA 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. 2018; 5(3): 153-165.
Vancouver 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. 2018; 5(3): 165-153.