Combinatorial batch codes: A lower bound and optimal constructions

Previous Article
On some classes of constacyclic codes over polynomial residue rings
AMC Home
This Issue
Next Article
Codes on planar Tanner graphs

May 2012, 6(2): 165-174. doi: 10.3934/amc.2012.6.165

Combinatorial batch codes: A lower bound and optimal constructions

Srimanta Bhattacharya ^1, , Sushmita Ruj ^2, and Bimal Roy ^1,

1.	Applied Statistics Unit, Indian Statistical Institute, 203 B T Road, Kolkata 700 108, India, India
2.	School of Information Technology and Engineering, University of Ottawa, Ottawa, K1N6N5, Canada

Received February 2011 Revised December 2011 Published April 2012

Abstract
Related Papers

Batch codes, introduced by Ishai et al. in [11], are methods for solving the following data storage problem: $n$ data items are to be stored in $m$ servers in such a way that any $k$ of the $n$ items can be retrieved by reading at most $t$ items from each server, and that the total number of items stored in $m$ servers is $N$. A combinatorial batch code (CBC) is a batch code where each data item is stored without change, i.e., each stored data item is a copy of one of the $n$ data items.
One of the basic yet challenging problems is to find optimal CBCs, i.e., CBCs for which total storage ($N$) is minimal for given values of $n$, $m$, $k$, and $t$. In [13], Paterson et al. exclusively studied CBCs and gave constructions of some optimal CBCs.
In this article, we give a lower bound on the total storage ($N$) for CBCs. We give explicit construction of optimal CBCs for a range of values of $n$. For a different range of values of $n$, we give explicit construction of optimal and almost optimal CBCs. Our results partly settle an open problem of [13].

Keywords: binary constant weight codes., Combinatorial batch codes, Hall's theorem.

Mathematics Subject Classification: Primary: 05D05, 68P30; Secondary: 68P2.

Citation: Srimanta Bhattacharya, Sushmita Ruj, Bimal Roy. Combinatorial batch codes: A lower bound and optimal constructions. Advances in Mathematics of Communications, 2012, 6 (2) : 165-174. doi: 10.3934/amc.2012.6.165

References:

[1]	E. Agrell, A. Vardy and K. Zeger, Upper bounds for constant-weight codes, IEEE Trans. Inform. Theory, 46 (2000), 2373-2395. doi: 10.1109/18.887851.
[2]	B. Bollobas, "Combinatorics,'' Cambridge University Press, 1986.
[3]	A. E. Brouwer and T. Etzion, Some new distance-4 constant weight codes, Adv. Math. Commun., 5 (2011), 417-424. doi: 10.3934/amc.2011.5.417.
[4]	A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Theory, 36 (1990), 1334-1380. doi: 10.1109/18.59932.
[5]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431. doi: 10.3934/amc.2010.4.419.
[6]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Erratum: Combinatorial batch codes and transversal matriods, Adv. Math. Commun., 4 (2010), 597-597. doi: 10.3934/amc.2010.4.597.
[7]	C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.
[8]	C. Bujtás and Z. Tuza, Optimal batch codes: many items or low retrieval requirement, Adv. Math. Commnun., 5 (2011), 529-541. doi: 10.3934/amc.2011.5.529.
[9]	R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 26 (1980), 37-43. doi: 10.1109/TIT.1980.1056141.
[10]	W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, 2003.
[11]	Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing,'' 36 (2004), 262-271. doi: 10.1145/1007352.1007396.
[12]	T. Klove, A lower bound for $A(n, 4, w)$, IEEE Trans. Inform. Theory, 27 (1981), 257-258. doi: 10.1109/TIT.1981.1056318.
[13]	M. B. Patterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.
[14]	D. H. Smith, L. A. Hughes and S. Perkins, A new table of constant weight codes of length greater than $28$, Electr. J. Combin., 13 (2006), Article A2.
[15]	C. L. M. Van Pul and T. Etzion, New lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 35 (1989), 1324-1329. doi: 10.1109/18.45293.

show all references

References:

[1]	E. Agrell, A. Vardy and K. Zeger, Upper bounds for constant-weight codes, IEEE Trans. Inform. Theory, 46 (2000), 2373-2395. doi: 10.1109/18.887851.
[2]	B. Bollobas, "Combinatorics,'' Cambridge University Press, 1986.
[3]	A. E. Brouwer and T. Etzion, Some new distance-4 constant weight codes, Adv. Math. Commun., 5 (2011), 417-424. doi: 10.3934/amc.2011.5.417.
[4]	A. E. Brouwer, J. B. Shearer, N. J. A. Sloane and W. D. Smith, A new table of constant weight codes, IEEE Trans. Inform. Theory, 36 (1990), 1334-1380. doi: 10.1109/18.59932.
[5]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Combinatorial batch codes and transversal matroids, Adv. Math. Commun., 4 (2010), 419-431. doi: 10.3934/amc.2010.4.419.
[6]	R. A. Brualdi, K. P. Kiernan, S. A. Meyer and M. W. Schroeder, Erratum: Combinatorial batch codes and transversal matriods, Adv. Math. Commun., 4 (2010), 597-597. doi: 10.3934/amc.2010.4.597.
[7]	C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.
[8]	C. Bujtás and Z. Tuza, Optimal batch codes: many items or low retrieval requirement, Adv. Math. Commnun., 5 (2011), 529-541. doi: 10.3934/amc.2011.5.529.
[9]	R. L. Graham and N. J. A. Sloane, Lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 26 (1980), 37-43. doi: 10.1109/TIT.1980.1056141.
[10]	W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, 2003.
[11]	Y. Ishai, E. Kushilevitz, R. Ostrovsky and A. Sahai, Batch codes and their applications, in "Proceedings of the Thirty-Sixth Annual ACM Symposium on Theory of Computing,'' 36 (2004), 262-271. doi: 10.1145/1007352.1007396.
[12]	T. Klove, A lower bound for $A(n, 4, w)$, IEEE Trans. Inform. Theory, 27 (1981), 257-258. doi: 10.1109/TIT.1981.1056318.
[13]	M. B. Patterson, D. R. Stinson and R. Wei, Combinatorial batch codes, Adv. Math. Commun., 3 (2009), 13-27. doi: 10.3934/amc.2009.3.13.
[14]	D. H. Smith, L. A. Hughes and S. Perkins, A new table of constant weight codes of length greater than $28$, Electr. J. Combin., 13 (2006), Article A2.
[15]	C. L. M. Van Pul and T. Etzion, New lower bounds for constant weight codes, IEEE Trans. Inform. Theory, 35 (1989), 1324-1329. doi: 10.1109/18.45293.

[1]	M. B. Paterson, D. R. Stinson, R. Wei. Combinatorial batch codes. Advances in Mathematics of Communications, 2009, 3 (1) : 13-27. doi: 10.3934/amc.2009.3.13
[2]	JiYoon Jung, Carl Mummert, Elizabeth Niese, Michael Schroeder. On erasure combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (1) : 49-65. doi: 10.3934/amc.2018003
[3]	Richard A. Brualdi, Kathleen P. Kiernan, Seth A. Meyer, Michael W. Schroeder. Combinatorial batch codes and transversal matroids. Advances in Mathematics of Communications, 2010, 4 (3) : 419-431. doi: 10.3934/amc.2010.4.419
[4]	Yuebo Shen, Dongdong Jia, Gengsheng Zhang. The results on optimal values of some combinatorial batch codes. Advances in Mathematics of Communications, 2018, 12 (4) : 681-690. doi: 10.3934/amc.2018040
[5]	Olof Heden, Martin Hessler. On linear equivalence and Phelps codes. Addendum. Advances in Mathematics of Communications, 2011, 5 (3) : 543-546. doi: 10.3934/amc.2011.5.543
[6]	Andries E. Brouwer, Tuvi Etzion. Some new distance-4 constant weight codes. Advances in Mathematics of Communications, 2011, 5 (3) : 417-424. doi: 10.3934/amc.2011.5.417
[7]	Michael Braun. On lattices, binary codes, and network codes. Advances in Mathematics of Communications, 2011, 5 (2) : 225-232. doi: 10.3934/amc.2011.5.225
[8]	Liying Pan, R. Julian R. Abel, Jinhua Wang. Constructions of optimal multiply constant-weight codes MCWC$ (3,n_1;1,n_2;1,n_3;8)s $. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022025
[9]	Fengwei Li, Qin Yue, Fengmei Liu. The weight distributions of constacyclic codes. Advances in Mathematics of Communications, 2017, 11 (3) : 471-480. doi: 10.3934/amc.2017039
[10]	Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
[11]	Andreas Klein, Leo Storme. On the non-minimality of the largest weight codewords in the binary Reed-Muller codes. Advances in Mathematics of Communications, 2011, 5 (2) : 333-337. doi: 10.3934/amc.2011.5.333
[12]	Joe Gildea, Adrian Korban, Adam M. Roberts, Alexander Tylyshchak. Binary self-dual codes of various lengths with new weight enumerators from a modified bordered construction and neighbours. Advances in Mathematics of Communications, 2022 doi: 10.3934/amc.2022021
[13]	J. D. Key, T. P. McDonough, V. C. Mavron. Codes from hall planes of odd order. Advances in Mathematics of Communications, 2017, 11 (1) : 179-185. doi: 10.3934/amc.2017011
[14]	Cuiling Fan, Koji Momihara. Unified combinatorial constructions of optimal optical orthogonal codes. Advances in Mathematics of Communications, 2014, 8 (1) : 53-66. doi: 10.3934/amc.2014.8.53
[15]	Petr Lisoněk, Layla Trummer. Algorithms for the minimum weight of linear codes. Advances in Mathematics of Communications, 2016, 10 (1) : 195-207. doi: 10.3934/amc.2016.10.195
[16]	Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020 doi: 10.3934/amc.2020124
[17]	Alexander Barg, Arya Mazumdar, Gilles Zémor. Weight distribution and decoding of codes on hypergraphs. Advances in Mathematics of Communications, 2008, 2 (4) : 433-450. doi: 10.3934/amc.2008.2.433
[18]	Alexander A. Davydov, Stefano Marcugini, Fernanda Pambianco. On the weight distribution of the cosets of MDS codes. Advances in Mathematics of Communications, 2021 doi: 10.3934/amc.2021042
[19]	Joaquim Borges, Ivan Yu. Mogilnykh, Josep Rifà, Faina I. Solov'eva. Structural properties of binary propelinear codes. Advances in Mathematics of Communications, 2012, 6 (3) : 329-346. doi: 10.3934/amc.2012.6.329
[20]	Anna-Lena Trautmann. Isometry and automorphisms of constant dimension codes. Advances in Mathematics of Communications, 2013, 7 (2) : 147-160. doi: 10.3934/amc.2013.7.147

2020 Impact Factor: 0.935

Tools

Metrics

Other articles
by authors

on AIMS
Srimanta Bhattacharya Sushmita Ruj Bimal Roy
on Google Scholar
Srimanta Bhattacharya Sushmita Ruj Bimal Roy

[Back to Top]