×

Anticode-based locally repairable codes with high availability. (English) Zbl 1412.94251

Summary: This paper presents constructions of new families of locally repairable codes (LRCs) with small locality and high availability, where each code symbol can be recovered by using many (exponential in the dimension of the code) disjoint small sets (of size 2 or 3) of other code symbols. Following the method of Farrell, the generator matrices of our LRCs are obtained by deleting certain columns from the generator matrix of the simplex code, where the deleted columns form different anticodes. Most of the resulting codes, defined over any finite field and in particular over the binary field, are optimal either with respect to the Griesmer bound, or with respect to the Cadambe-Mazumdar bound for LRCs, or both.

MSC:

94B60 Other types of codes
11T71 Algebraic coding theory; cryptography (number-theoretic aspects)

Software:

Hadoop
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Beutelspacher A.: Blocking sets and partial spreads in finite projective spaces. Geom. Dedic. 9(4), 425-449 (1980). · Zbl 0377.50007 · doi:10.1007/BF00181559
[2] Blake I.F., Mullin R.C.: An Introduction to Algebraic and Combinatorial Coding Theory. Academic Press, New York (1976). · Zbl 0449.94012
[3] Cadambe V.R., Mazumdar A.: Bounds on the size of locally recoverable codes. IEEE Trans. Inf. Theory 61(11), 5787-5794 (2015). · Zbl 1359.94679 · doi:10.1109/TIT.2015.2477406
[4] Dimakis A., Godfrey P., Wu Y., Wainwright M., Ramchandran K.: Network coding for distributed storage systems. IEEE Trans. Inf. Theory 56(9), 4539-4551 (2010). · Zbl 1410.68117 · doi:10.1109/TIT.2010.2054295
[5] Dimakis A., Ramchandran K., Wu Y., Suh C.: A survey on network codes for distributed storage. Proc. IEEE 99(3), 476-489 (2011). · doi:10.1109/JPROC.2010.2096170
[6] Farrell P.: Linear binary anticodes. Electron. Lett. 6(13), 419-421 (1970). · doi:10.1049/el:19700293
[7] Gopalan P., Huang C., Simitci H., Yekhanin S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925-6934 (2012). · Zbl 1364.94603 · doi:10.1109/TIT.2012.2208937
[8] Gopalan P., Huang C., Jenkins B., Yekhanin S.: Explicit maximally recoverable codes with locality. IEEE Trans. Inf. Theory 60(9), 5245-5256 (2014). · Zbl 1360.94373 · doi:10.1109/TIT.2014.2332338
[9] Goparaju S., Calderbank R.: Binary cyclic codes that are locally repairable. In: IEEE International Symposium on Information Theory (ISIT), pp. 676-680 (2014). · Zbl 1360.94377
[10] Griesmer J.: A bound for error-correcting codes. IBM J. Res. Dev. 4(5), 532-542 (1960). · Zbl 0234.94009 · doi:10.1147/rd.45.0532
[11] Hamada N., Helleseth T., Ytrehus Ø.: A new class of nonbinary codes meeting the Griesmer bound. Discret. Appl. Math. 47(3), 219-226 (1993). · Zbl 0786.94016 · doi:10.1016/0166-218X(93)90127-A
[12] Huang P., Yaakobi E., Uchikawa H., Siegel P.H.: Cyclic linear binary cocally repairable codes. In: IEEE Information Theory Workshop (ITW), Jerusalem, Israel, pp. 1-5 (2015). · Zbl 0786.94016
[13] Huang P., Yaakobi E., Uchikawa H., Siegel P.H.: Linear locally repairable codes with availability. In: IEEE International Symposium on Information Theory (ISIT), pp. 1871-1875 (2015). · Zbl 0234.94009
[14] Kadhe S., Sprintson A.: Codes with unequal locality. arXiv:1601.06153 (2016). · Zbl 1364.94603
[15] Kamath G., Silberstein N., Prakash N., Rawat A., Lalitha V., Koyluoglu O., Kumar P., Vishwanath S.: Explicit MBR all-symbol locality codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 504-508 (2013). · Zbl 1364.94603
[16] Kamath G., Prakash N., Lalitha V., Kumar P.: Codes with local regeneration and erasure correction. IEEE Trans. Inf. Theory 60(8), 4637-4660 (2014). · Zbl 1360.94377 · doi:10.1109/TIT.2014.2329872
[17] Kuijper M., Napp D.: Erasure codes with simplex locality. arXiv:1403.2779 (2014). · Zbl 1364.94603
[18] MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North Holland, New York (1988). · Zbl 0369.94008
[19] Pamies-Juarez L., Hollmann H., Oggier F.: Locally repairable codes with multiple repair alternatives. In: IEEE International Symposium on Information Theory (ISIT), pp. 892-896 (2013).
[20] Papailiopoulos D.S., Dimakis A.G.: Locally repairable codes. IEEE Trans. Inf. Theory 60(10), 5843-5855 (2014). · Zbl 1360.94458 · doi:10.1109/TIT.2014.2325570
[21] Prakash N., Kamath G.M., Lalitha V., Kumar P.V.: Optimal linear codes with a local-error-correction property. In: IEEE International Symposium on Information Theory (ISIT), pp. 2776-2780 (2012).
[22] Prakash N., Lalitha V., Kumar P.: Codes with locality for two erasures. In: IEEE International Symposium on Information Theory (ISIT), pp. 1962-1966 (2014). · Zbl 1360.94385
[23] Rawat A., Koyluoglu O., Silberstein N., Vishwanath S.: Optimal locally repairable and secure codes for distributed storage systems. IEEE Trans. Inf. Theory 60(1), 212-236 (2014). · Zbl 1456.94137 · doi:10.1109/TIT.2013.2288784
[24] Rawat A., Papailiopoulos D., Dimakis A., Vishwanath S.: Locality and availability in distributed storage. In: IEEE International Symposium on Information Theory (ISIT), pp. 681-685 (2014). · Zbl 1359.68061
[25] Roth R.M.: Introduction to Coding Theory. Cambridge University Press, New York (2006). · Zbl 1092.94001 · doi:10.1017/CBO9780511808968
[26] Silberstein N., Etzion T.: Codes and designs related to lifted MRD codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 2288-2292 (2011). · Zbl 1364.94597
[27] Silberstein N., Zeh A.: Optimal binary locally repairable codes via anticodes. In: IEEE International Symposium on Information Theory (ISIT), pp. 1247-1251 (2015).
[28] Silberstein N., Rawat A., Koyluoglu O., Vishwanath S.: Optimal locally repairable codes via rank-metric codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 1819-1823 (2013). · Zbl 1360.94377
[29] Shahabinejad M., Khabbazian M., Ardakani M.: An efficient binary locally repairable code for hadoop distributed file system. IEEE Commun. Lett. 18(8), 1287-1290 (2014). · doi:10.1109/LCOMM.2014.2332491
[30] Tamo I., Barg A.: Bounds on locally recoverable codes with multiple recovering sets. In: IEEE International Symposium on Information Theory (ISIT), pp. 691-695 (2014).
[31] Tamo I., Barg A.: A family of optimal locally recoverable codes. IEEE Trans. Inf. Theory 60(8), 4661-4676 (2014). · Zbl 1360.94385 · doi:10.1109/TIT.2014.2321280
[32] Wang A., Zhang Z.: Repair locality with multiple erasure tolerance. IEEE Trans. Inf. Theory 60(11), 6979-6987 (2014). · Zbl 1360.94135 · doi:10.1109/TIT.2014.2351404
[33] Wang A., Zhang Z., Liu M.: Achieving arbitrary locality and availability in binary codes. In: IEEE International Symposium on Information Theory (ISIT), pp. 1866-1870 (2015).
[34] Westerback T., Ernvall T., Hollanti C.: Almost affine locally repairable codes and matroid theory. In: IEEE Information Theory Workshop (ITW), pp. 621-625 (2014).
[35] Zeh A., Yaakobi E.: Optimal linear and cyclic locally repairable codes over small fields. In: IEEE Information Theory Workshop (ITW), Jerusalem, Israel, pp. 1-5 (2015).
[36] Zeh A., Yaakobi E.: Bounds and constructions of codes with multiple localities. In: IEEE International Symposium on Information Theory (ISIT), pp. 640-644 (2016). · Zbl 0377.50007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.