Batch Codes from Hamming and Reed-Muller Codes

Journal of Algebra Combinatorics Discrete Structures and Applications

article

Travis Alan Baumbaugh¹  Yariana Diaz¹  Sophia Friesenhahn²  Felice Manganiello³  Alexander Vetter⁴ 

[1] Clemson University;The University of Iowa;Willamette University;VillanovaUniversity

关键词: Batch codes;    Hamming codes;    Reed-Muller codes;   

DOI  :  10.13069/jacodesmath.466634

学科分类：社会科学、人文和艺术（综合）

来源: Yildiz Technical University

【 摘 要 】

Batch codes, introduced by Ishai et al., encode a string x ∈ Σkinto an m-tuple of strings, calledbuckets. In this paper we consider multiset batch codes wherein a set of t-users wish to access onebit of information each from the original string. We introduce a concept of optimal batch codes. Wefirst show that binary Hamming codes are optimal batch codes. The main body of this work providesbatch properties of Reed-Muller codes. We look at locality and availability properties of first orderReed-Muller codes over any finite field. We then show that binary first order Reed-Muller codes areoptimal batch codes when the number of users is 4 and generalize our study to the family of binaryReed-Muller codes which have order less than half their length.

【 授权许可】

CC BY