-
Previous Article
On some classes of constacyclic codes over polynomial residue rings
- AMC Home
- This Issue
-
Next Article
Codes on planar Tanner graphs
Combinatorial batch codes: A lower bound and optimal constructions
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 |
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].
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
[Back to Top]