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
Konular Mühendislik
Dergi Bölümü Makaleler
Yazarlar

Orcid: 0000-0002-3539-9758
Yazar: Travis Baumbaugh (Sorumlu Yazar)

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

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

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

Orcid: 0000-0003-2539-9815
Yazar: 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 <http://dergipark.gov.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 - 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