American Institute of Mathematical Sciences

Advanced
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

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.  Google Scholar

[2]

B. Bollobas, "Combinatorics,'' Cambridge University Press, 1986.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

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.  Google Scholar

[2]

B. Bollobas, "Combinatorics,'' Cambridge University Press, 1986.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[7]

C. Bujtás and Z. Tuza, Optimal combinatorial batch codes derived from dual systems, Miskolc Math. Notes, 12 (2011), 11-23.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[10]

W. C. Huffman and V. Pless, "Fundamentals of Error-Correcting Codes,'' Cambridge University Press, 2003.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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]

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
[9]

Tim Alderson, Alessandro Neri. Maximum weight spectrum codes. Advances in Mathematics of Communications, 2019, 13 (1) : 101-119. doi: 10.3934/amc.2019006
[10]

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
[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]

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
[13]

Xiangrui Meng, Jian Gao. Complete weight enumerator of torsion codes. Advances in Mathematics of Communications, 2020  doi: 10.3934/amc.2020124
[14]

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
[15]

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
[16]

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
[17]

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
[18]

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
[19]

Natalia Silberstein, Tuvi Etzion. Large constant dimension codes and lexicodes. Advances in Mathematics of Communications, 2011, 5 (2) : 177-189. doi: 10.3934/amc.2011.5.177
[20]

Steven T. Dougherty, Esengül Saltürk, Steve Szabo. Codes over local rings of order 16 and binary codes. Advances in Mathematics of Communications, 2016, 10 (2) : 379-391. doi: 10.3934/amc.2016012

2020 Impact Factor: 0.935

Tools

Metrics

  • PDF downloads (117)
  • HTML views (0)
  • Cited by (15)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences