Binary Batch Codes With Improved Redundancy
Rina Polyanskaya, Nikita Polyanskii, Ilya Vorobyev · IEEE Transactions on Information Theory · 2020
A primitive k-batch code encodes a string x of length n into a stringy of length N, such that each multiset of k symbols from x has k mutually disjoint recovering sets from y. In this paper, we discuss new constructions of binary primitive batch codes. First, we develop novel explicit and random coding constructions of linear primitive batch codes based on finite geometries. Second, a new explicit coding construction of binary primitive batch codes based on bivariate lifted multiplicity codes is provided. For any k = nεwith ε ∈ (0, 0.47) \ {1/5, 1/4}, our proposed codes have a better trade-off between the redundancy and the parameters k, n than previously known batch codes.