Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Anticode-based locally repairable codes with high availability

  • Published:
Designs, Codes and Cryptography Aims and scope Submit manuscript

Abstract

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.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1

Similar content being viewed by others

References

  1. Beutelspacher A.: Blocking sets and partial spreads in finite projective spaces. Geom. Dedic. 9(4), 425–449 (1980).

    Article  MathSciNet  MATH  Google Scholar 

  2. Blake I.F., Mullin R.C.: An Introduction to Algebraic and Combinatorial Coding Theory. Academic Press, New York (1976).

    MATH  Google Scholar 

  3. Cadambe V.R., Mazumdar A.: Bounds on the size of locally recoverable codes. IEEE Trans. Inf. Theory 61(11), 5787–5794 (2015).

    Article  MathSciNet  MATH  Google Scholar 

  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).

    Article  Google Scholar 

  5. Dimakis A., Ramchandran K., Wu Y., Suh C.: A survey on network codes for distributed storage. Proc. IEEE 99(3), 476–489 (2011).

    Article  Google Scholar 

  6. Farrell P.: Linear binary anticodes. Electron. Lett. 6(13), 419–421 (1970).

    Article  Google Scholar 

  7. Gopalan P., Huang C., Simitci H., Yekhanin S.: On the locality of codeword symbols. IEEE Trans. Inf. Theory 58(11), 6925–6934 (2012).

    Article  MathSciNet  MATH  Google Scholar 

  8. Gopalan P., Huang C., Jenkins B., Yekhanin S.: Explicit maximally recoverable codes with locality. IEEE Trans. Inf. Theory 60(9), 5245–5256 (2014).

    Article  MathSciNet  MATH  Google Scholar 

  9. Goparaju S., Calderbank R.: Binary cyclic codes that are locally repairable. In: IEEE International Symposium on Information Theory (ISIT), pp. 676–680 (2014).

  10. Griesmer J.: A bound for error-correcting codes. IBM J. Res. Dev. 4(5), 532–542 (1960).

    Article  MathSciNet  MATH  Google Scholar 

  11. Hamada N., Helleseth T., Ytrehus Ø.: A new class of nonbinary codes meeting the Griesmer bound. Discret. Appl. Math. 47(3), 219–226 (1993).

    Article  MathSciNet  MATH  Google Scholar 

  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).

  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).

  14. Kadhe S., Sprintson A.: Codes with unequal locality. arXiv:1601.06153 (2016).

  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).

  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).

    Article  MathSciNet  MATH  Google Scholar 

  17. Kuijper M., Napp D.: Erasure codes with simplex locality. arXiv:1403.2779 (2014).

  18. MacWilliams F.J., Sloane N.J.A.: The Theory of Error-Correcting Codes. North Holland, New York (1988).

    MATH  Google Scholar 

  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).

    Article  MathSciNet  MATH  Google Scholar 

  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).

  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).

    Article  Google Scholar 

  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).

  25. Roth R.M.: Introduction to Coding Theory. Cambridge University Press, New York (2006).

    Book  MATH  Google Scholar 

  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).

  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).

  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).

    Article  Google Scholar 

  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).

    Article  MathSciNet  MATH  Google Scholar 

  32. Wang A., Zhang Z.: Repair locality with multiple erasure tolerance. IEEE Trans. Inf. Theory 60(11), 6979–6987 (2014).

    Article  MathSciNet  MATH  Google Scholar 

  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).

Download references

Acknowledgements

The authors thank the anonymous reviewers for their valuable comments and suggestions that helped to improve the quality of the paper. A. Zeh has been supported by the German research council (Deutsche Forschungsgemeinschaft, DFG) under Grant Ze1016/1-1.

Author information

Author notes

  1. Natalia Silberstein

    Present address: Yahoo! Labs, Haifa, Israel

  2. Alexander Zeh

    Present address: Infineon Technologies AG, Neubiberg, Germany

Authors and Affiliations

  1. Department of Computer Science, Technion—Israel Institute of Technology, Haifa, Israel

    Natalia Silberstein & Alexander Zeh

  2. Department of Electrical and Computer Engineering, Ben-Gurion University of the Negev, Beer Sheva, Israel

    Natalia Silberstein

Authors
  1. Natalia Silberstein
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Alexander Zeh
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Natalia Silberstein.

Additional information

Parts of the presented work were published in the proceedings of the IEEE International Symposium Information Theory (ISIT) 2015, [27].

This is one of several papers published in Designs, Codes and Cryptography comprising the Special Issue on Network Coding and Designs.

Appendix

Appendix

Proof of Theorem 10

The length, dimension, and the minimum Hamming distance of \({\mathcal {C}_{\textsc {I}}^{\langle q \rangle }}\) directly follow from the Farrell construction. To prove the locality and the availability we calculate the number of disjoint pairs of columns in the generator matrix \({G_{\textsc {I}}^{\langle q \rangle }}\) of the constructed code \({\mathcal {C}_{\textsc {I}}^{\langle q \rangle }}\) which give the corresponding column g. For simplicity we consider only a systematic column g (a binary column of weight one), as it can be seen that for other columns the availability can be only larger (similarly to the binary case).

First, let q be an odd prime power. Then the element \(1\in \mathbb {F}_q\) can be obtained by \((q-1)/2\) disjoint pairs of nonzero elements from the field. This follows from the fact that for any nonzero \(\alpha \in \mathbb {F}_q\), such that \(\alpha \ne -1\), there exists a unique nonzero \(\beta =1+\alpha \) such that their linear combination gives 1. For \(\alpha =-1\), take \(\beta =1-\alpha \).

Now given such a pair \((\alpha ,\beta )\) of field elements there are at least \((q^{m-1}-1)/(q-1)-(s-1)\) normalized (starting from 1) vectors of length m which have \(\alpha \) in a given position and do not belong to the anticode’s columns. Note, that since these vectors are different from g they should have weight at least 2 (in a case the weight is exactly 2 and \(\alpha \) belongs to the last s coordinates then there are \(s-1\) columns which belong to the anticode and then should be removed) and if \(\alpha \) is on a first nonzero position of a column then the multiplication by the corresponding field elements is needed.

Therefore, the availability is at least

$$\begin{aligned} \left( \frac{q^{m-1}-1}{q-1}-(s-1)\right) \frac{q-1}{2}. \end{aligned}$$

Let q be an even prime power. There are \(q/2-1\) disjoint pairs of nonzero field elements such that their linear combination equals 1 and the additional pair (0, 1).

We distinguish between the two following cases. First, the nonzero entry of g is in one of the last s coordinates. Then, given a pair \((\alpha , \beta )\), \(\alpha \notin \{0,1\}\), there are at least \((q^{m-1}-1)/(q-1)-(s-1)\) columns of \({G_{\textsc {I}}^{\langle q \rangle }}\) which have \(\alpha \) in a given position. Given the pair (0, 1), there are at least \( \frac{q^{m-1}-1}{q-1}-(s-1)-(q-1)\left( {\begin{array}{c}s-1\\ 2\end{array}}\right) \) columns of \({G_{\textsc {I}}^{\langle q \rangle }}\) which have 1 in a given position. To see this, note that there are \((s-1)\) columns from the anticode which have 1 in the given coordinate and \((q-1)\left( {\begin{array}{c}s-1\\ 2\end{array}}\right) \) columns from the anticode which have 0 in a given coordinate (in the last s).

Thus, the availability for such g is at least

$$\begin{aligned}&\left( \frac{q^{m-1}-1}{q-1} -(s-1)\right) \left( \frac{q}{2}-1\right) +\frac{q^{m-1}-1}{q-1}-(s-1)-(q-1)\genfrac(){0.0pt}1{s-1}{2}\\&\quad =\left( \frac{q^{m-1}-1}{q-1}-(s-1)\right) \frac{q}{2}-(q-1)\genfrac(){0.0pt}1{s-1}{2}. \end{aligned}$$

If the nonzero entry of g is in one of the first \(m-s\) coordinates, then, given a pair \((\alpha , \beta )\), \(\alpha \notin \{0,1\}\), there are \((q^{m-1}-1)/(q-1)\) columns of \({G_{\textsc {I}}^{\langle q \rangle }}\) which have \(\alpha \) in a given position. Given the pair (0, 1), there are \((q^{m-1}-1)/(q-1)-(q-1)\left( {\begin{array}{c}s\\ 2\end{array}}\right) \) columns of \({G_{\textsc {I}}^{\langle q \rangle }}\) which have 1 in a given position. Thus, the availability for such g is at least

$$\begin{aligned} \left( \frac{q^{m-1}-1}{q-1}\right) \left( \frac{q}{2}-1\right) +\frac{q^{m-1}-1}{q-1}-(q-1)\genfrac(){0.0pt}1{s}{2} =\left( \frac{q^{m-1}-1}{q-1}\right) \frac{q}{2}-(q-1)\genfrac(){0.0pt}1{s}{2}. \end{aligned}$$

Since

$$\begin{aligned} \left( \frac{q^{m-1}-1}{q-1}-(s-1)\right) \frac{q}{2}-(q-1)\left( {\begin{array}{c}s-1\\ 2\end{array}}\right) \ge \left( \frac{q^{m-1}-1}{q-1}\right) \frac{q}{2}-(q-1)\left( {\begin{array}{c}s\\ 2\end{array}}\right) , \end{aligned}$$

the statement of Theorem 10 follows. \(\square \)

Proof of Theorem 12

The length, dimension, and the minimum Hamming distance of the code \({\mathcal {C}_{\textsc {II}}^{\langle q \rangle }}\) follow from Theorem 11 and the Farrell construction. To prove the locality and the availability of \({\mathcal {C}_{\textsc {II}}^{\langle q \rangle }}\) we consider, similarly to the proof of Theorem 10, a column g of the generator matrix, such that g is of weight one.

For odd q, the availability of \({\mathcal {C}_{\textsc {II}}^{\langle q \rangle }}\) is at least

$$\begin{aligned} \left( \frac{q^{m-1}-1}{q-1}-\frac{q^s-1}{q-1}+(q-1)^{s-2}\right) \frac{q-1}{2} \end{aligned}$$

since for every given pair of field elements \((\alpha , \beta )\) whose linear combination gives 1, there are

$$\begin{aligned} \left( \frac{q^{m-1}-1}{q-1}-\frac{q^s-1}{q-1}+(q-1)^{s-2}\right) \end{aligned}$$

columns in the new generator matrix which have \(\alpha \) in a given coordinate.

For even q, similarly to the proof Theorem 10 we consider two possible cases, where the one of g is contained in the last s coordinates and the case where it is contained in the first \(m-s\) coordinates. In the first case we have availability at least

$$\begin{aligned}&\left( \frac{q^{m-1}-1}{q-1}-\frac{q^{s-1}-1}{q-1}+(q-1)^{s-2}\right) \left( \frac{q}{2}-1\right) +\frac{q^{m-1}-1}{q-1}-\frac{q^{s-1}-1}{q-1} \\&\quad =\left( \frac{q^{m-1}-1}{q-1}-\frac{q^{s-1}-1}{q-1}\right) \frac{q}{2}+(q-1)^{s-2}\left( \frac{q}{2}-1\right) . \end{aligned}$$

In the second case we have availability at least

$$\begin{aligned}&\frac{q^{m-1}-1}{q-1}\left( \frac{q}{2}-1\right) +\left( \frac{q^{m-1}-1}{q-1}-\frac{q^s-1}{q-1}+(q-1)^{s-1}+s\right) \\&\quad = \frac{q^{m-1}-1}{q-1}\cdot \frac{q}{2}-\frac{q^s-1}{q-1}+(q-1)^{s-1}+s. \end{aligned}$$

Since the latter value is smaller than the former, we obtain the bound on the availability. \(\square \)

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Silberstein, N., Zeh, A. Anticode-based locally repairable codes with high availability. Des. Codes Cryptogr. 86, 419–445 (2018). https://doi.org/10.1007/s10623-017-0358-0

Download citation

  • Received:

  • Revised:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10623-017-0358-0

Keywords

Mathematics Subject Classification

Search

Navigation