Research Article
BibTex RIS Cite
Year 2018, , 153 - 165, 08.10.2018
https://doi.org/10.13069/jacodesmath.466634

Abstract

References

  • [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.

Batch codes from Hamming and Reed-Muller codes

Year 2018, , 153 - 165, 08.10.2018
https://doi.org/10.13069/jacodesmath.466634

Abstract

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.

References

  • [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.
There are 13 citations in total.

Details

Primary Language English
Subjects Engineering
Journal Section Articles
Authors

Travis Baumbaugh This is me 0000-0002-3539-9758

Yariana Diaz This is me 0000-0003-0603-9750

Sophia Friesenhahn This is me 0000-0001-8847-8962

Felice Manganiello This is me 0000-0002-5764-569X

Alexander Vetter This is me 0000-0003-2539-9815

Publication Date October 8, 2018
Published in Issue Year 2018

Cite

APA Baumbaugh, T., Diaz, Y., Friesenhahn, S., Manganiello, F., et al. (2018). Batch codes from Hamming and Reed-Muller codes. Journal of Algebra Combinatorics Discrete Structures and Applications, 5(3), 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. October 2018;5(3):153-165. doi:10.13069/jacodesmath.466634
Chicago Baumbaugh, Travis, Yariana Diaz, Sophia Friesenhahn, Felice Manganiello, and Alexander Vetter. “Batch Codes from Hamming and Reed-Muller Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications 5, no. 3 (October 2018): 153-65. https://doi.org/10.13069/jacodesmath.466634.
EndNote Baumbaugh T, Diaz Y, Friesenhahn S, Manganiello F, Vetter A (October 1, 2018) Batch codes from Hamming and Reed-Muller codes. Journal of Algebra Combinatorics Discrete Structures and Applications 5 3 153–165.
IEEE T. Baumbaugh, Y. Diaz, S. Friesenhahn, F. Manganiello, and A. Vetter, “Batch codes from Hamming and Reed-Muller codes”, Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 5, no. 3, pp. 153–165, 2018, doi: 10.13069/jacodesmath.466634.
ISNAD Baumbaugh, Travis et al. “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.
JAMA 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:153–165.
MLA Baumbaugh, Travis et al. “Batch Codes from Hamming and Reed-Muller Codes”. Journal of Algebra Combinatorics Discrete Structures and Applications, vol. 5, no. 3, 2018, pp. 153-65, doi:10.13069/jacodesmath.466634.
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):153-65.