Batch Codes from Hamming and Reed-Muller Codes
| Autor: | Sophia Friesenhahn, Yariana Diaz, Alexander Vetter, Travis Baumbaugh, Felice Manganiello |
|---|---|
| Jazyk: | angličtina |
| Rok vydání: | 2018 |
| Předmět: |
Discrete mathematics
Multiset Algebra and Number Theory lcsh:Mathematics String (computer science) Order (ring theory) Binary number Reed–Muller code Data_CODINGANDINFORMATIONTHEORY lcsh:QA1-939 Set (abstract data type) Finite field Computer Science::Emerging Technologies Discrete Mathematics and Combinatorics Hamming code Mathematics |
| Zdroj: | Journal of Algebra Combinatorics Discrete Structures and Applications, Vol 5, Iss 3 (2018) |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|