More Web Proxy on the site http://driver.im/

research-article

New Constructions of Optimal Locally Recoverable Codes via Good Polynomials

Authors:

Sihem Mesnager,

Lusheng ChenAuthors Info & Claims

IEEE Transactions on Information Theory, Volume 64, Issue 2

Pages 889 - 899

https://doi.org/10.1109/TIT.2017.2713245

Published: 01 February 2018 Publication History

Abstract

In recent literature, a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality) is presented. The key ingredient for constructing such optimal linear LRC codes is the so-called \(r\)-good polynomials, where \(r\) is equal to the locality of the LRC code. However, given a prime \(p\), known constructions of \(r\)-good polynomials over some extension field of \(\mathbb {F}_{p}\) exist only for some special integers \(r\), and the problem of constructing optimal LRC codes over small field for any given locality is still open. In this paper, by using function composition, we present two general methods of designing good polynomials, which lead to three new constructions of \(r\)-good polynomials. Such polynomials bring new constructions of optimal LRC codes. In particular, our constructed polynomials as well as the power functions yield optimal \((n,k,r)\) LRC codes over \(\mathbb {F}_{q}\) for all positive integers \(r\) as localities, where \(q\) is near the code length \(n\).

References

[1]

V. R. Cadambe and A. Mazumdar, “ Bounds on the size of locally recoverable codes,” IEEE Trans. Inf. Theory, vol. Volume 61, no. Issue 11, pp. 5787–5794, 2015.

Digital Library

[2]

L. Carlitz, “ Explicit evaluation of certain exponential sums,” Math. Scandin., vol. Volume 44, no. Issue 1, pp. 5–16, 1979.

[3]

T. Ernvall, T. Westerbäck, and C. Hollanti, “ Constructions of optimal and almost optimal locally repairable codes,” in Proc. 4th Int. Conf. Wireless Commun., Veh. Technol., Inf. Theory Aerosp. Electron. Syst. (VITAE), May 2014, pp. 1–5.

[4]

P. Gopalan, C. Huang, H. Simitci, and S. Yekhanin, “ On the locality of codeword symbols,” IEEE Trans. Inf. Theory, vol. Volume 58, no. Issue 11, pp. 6925–6934, 2012.

Digital Library

[5]

S. Goparaju and R. Calderbank, “ Binary cyclic codes that are locally repairable,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun./Jul. 2014, pp. 676–680.

[6]

X.-D. Hou, “ Explicit evaluation of certain exponential sums of binary quadratic functions,” Finite Fields Appl., vol. Volume 13, no. Issue 4, pp. 843–868, 2007.

Digital Library

[7]

P. Huang, E. Yaakobi, H. Uchikawa, and P. H. Siegel, “ Cyclic linear binary locally repairable codes,” in Proc. IEEE Inf. Theory Workshop (ITW), Apr./May 2015, pp. 1–5.

[8]

P. Huang, E. Yaakobi, H. Uchikawa, and P. H. Siegel, “ Linear locally repairable codes with availability,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1871–1875.

[9]

R. Lidl and H. Niederreiter, Finite Fields (Encyclopedia of Mathematics and its Applications), vol. Volume 20 . Cambridge, U.K.: Cambridge Univ. Press, 1997.

Digital Library

[10]

F. Oggier and A. Datta, “ Self-repairing homomorphic codes for distributed storage systems,” in Proc. IEEE INFOCOM, Apr. 2011, pp. 1215–1223.

[11]

D. S. Papailiopoulos and A. G. Dimakis, “ Locally repairable codes,” IEEE Trans. Inf. Theory, vol. Volume 60, no. Issue 10, pp. 5843–5855, 2014.

[12]

N. Prakash, G. M. Kamath, V. Lalitha, and P. V. Kumar, “ Optimal linear codes with a local-error-correction property,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2012, pp. 2776–2780.

[13]

M. Shahabinejad, M. Khabbazian, and M. Ardakani, “ An efficient binary locally repairable code for Hadoop distributed file system,” IEEE Commun. Lett., vol. Volume 18, no. Issue 8, pp. 1287–1290, 2014.

[14]

N. Silberstein, A. S. Rawat, O. O. Koyluoglu, and S. Vishwanath, “ Optimal locally repairable codes via rank-metric codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2013, pp. 1819–1823.

[15]

N. Silberstein and A. Zeh, “ Optimal binary locally repairable codes via anticodes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1247–1251.

[16]

W. Song, S. H. Dau, C. Yuen, and T. J. Li, “ Optimal locally repairable linear codes,” IEEE J. Sel. Areas Commun., vol. Volume 32, no. Issue 5, pp. 1019–1036, 2014.

[17]

I. Tamo and A. Barg, “ A family of optimal locally recoverable codes,” IEEE Trans. Inf. Theory, vol. Volume 60, no. Issue 8, pp. 4661–4676, 2014.

[18]

I. Tamo, A. Barg, S. Goparaju, and R. Calderbank, “ Cyclic LRC codes and their subfield subcodes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1262–1266.

[19]

I. Tamo, A. Barg, S. Goparaju, and R. Calderbank. (2016). “ Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes .” {Online}. Available: http://arxiv.org/abs/1603.08878

Digital Library

[20]

I. Tamo, D. S. Papailiopoulos, and A. G. Dimakis, “ Optimal locally repairable codes and connections to matroid theory,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jul. 2013, pp. 1814–1818.

[21]

A. Wang, Z. Zhang, and M. Liu, “ Achieving arbitrary locality and availability in binary codes,” in Proc. IEEE Int. Symp. Inf. Theory (ISIT), Jun. 2015, pp. 1866–1870.

[22]

T. Westerbäck, T. Ernvall, and C. Hollanti, “ Almost affine locally repairable codes and matroid theory,” in Proc. IEEE Inf. Theory Workshop (ITW), Nov. 2014, pp. 621–625.

[23]

A. Zeh and E. Yaakobi, “ Optimal linear and cyclic locally repairable codes over small fields,” in Proc. IEEE Inf. Theory Workshop (ITW), Apr./May 2015, pp. 1–5.

Cited By

Kong X(2024)Locally Repairable Convertible Codes With Optimal Access CostsIEEE Transactions on Information Theory10.1109/TIT.2024.343534670:9(6239-6257)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3435346
Galindo CHernando FMartín-Cruz H(2024)Optimal -LRCs from monomial-Cartesian codes and their subfield-subcodesDesigns, Codes and Cryptography10.1007/s10623-024-01403-z92:9(2549-2586)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10623-024-01403-z
Dukes AMicheli GPallozzi Lavorante V(2023)Optimal Locally Recoverable Codes With Hierarchy From Nested F-Adic ExpansionsIEEE Transactions on Information Theory10.1109/TIT.2023.329840169:11(6981-6988)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3298401
Show More Cited By

New Constructions of Optimal Locally Recoverable Codes via Good Polynomials
1. Mathematics of computing
  1. Mathematical analysis
    1. Numerical analysis

Recommendations

Constructions of optimal locally recoverable codes via Dickson polynomials
Abstract
In 2014, Tamo and Barg have presented in a very remarkable paper a family of optimal linear locally recoverable codes (LRC codes) that attain the maximum possible distance (given code length, cardinality, and locality). The key ingredients for ...
Constructions of near MDS codes which are optimal locally recoverable codes
Abstract
A linear code with length n, dimension k and minimum distance n − k is said to be almost maximum distance separable (AMDS for short). An AMDS code whose dual is also AMDS is referred to as a near maximum distance separable (NMDS for ...
On Good Polynomials over Finite Fields for Optimal Locally Recoverable Codes
Codes, Cryptology and Information Security
Abstract
[This is an extended abstract of the paper [3]] A locally recoverable (LRC) code is a code that enables a simple recovery of an erased symbol by accessing only a small number of other symbols. LRC codes currently form one of the rapidly developing ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Information Theory

IEEE Transactions on Information Theory Volume 64, Issue 2

February 2018

734 pages

ISSN:0018-9448

Issue’s Table of Contents

Copyright © 2018.

Publisher

IEEE Press

Publication History

Published: 01 February 2018

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

14
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 19 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Kong X(2024)Locally Repairable Convertible Codes With Optimal Access CostsIEEE Transactions on Information Theory10.1109/TIT.2024.343534670:9(6239-6257)Online publication date: 29-Jul-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3435346
Galindo CHernando FMartín-Cruz H(2024)Optimal -LRCs from monomial-Cartesian codes and their subfield-subcodesDesigns, Codes and Cryptography10.1007/s10623-024-01403-z92:9(2549-2586)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10623-024-01403-z
Dukes AMicheli GPallozzi Lavorante V(2023)Optimal Locally Recoverable Codes With Hierarchy From Nested F-Adic ExpansionsIEEE Transactions on Information Theory10.1109/TIT.2023.329840169:11(6981-6988)Online publication date: 1-Nov-2023
https://dl.acm.org/doi/10.1109/TIT.2023.3298401
Ma SWu SLi CXu Y(2022)Repair-Optimal Data Placement for Locally Repairable Codes with Optimal Minimum Hamming DistanceProceedings of the 51st International Conference on Parallel Processing10.1145/3545008.3545038(1-11)Online publication date: 29-Aug-2022
https://dl.acm.org/doi/10.1145/3545008.3545038
Li FChen HLao HLyu S(2022)New upper bounds and constructions of multi-erasure locally recoverable codesCryptography and Communications10.1007/s12095-022-00618-y15:3(513-528)Online publication date: 2-Dec-2022
https://dl.acm.org/doi/10.1007/s12095-022-00618-y
Dukes AFerraguti AMicheli G(2022)Optimal selection for good polynomials of degree up to fiveDesigns, Codes and Cryptography10.1007/s10623-022-01046-y90:6(1427-1436)Online publication date: 1-Jun-2022
https://dl.acm.org/doi/10.1007/s10623-022-01046-y
Chen RMesnager SZhao C(2021)Good polynomials for optimal LRC of low localityDesigns, Codes and Cryptography10.1007/s10623-021-00886-489:7(1639-1660)Online publication date: 1-Jul-2021
https://dl.acm.org/doi/10.1007/s10623-021-00886-4
Kolosov OYadgar GLiram MTamo IBarg A(2020)On Fault Tolerance, Locality, and Optimality in Locally Repairable CodesACM Transactions on Storage10.1145/338183216:2(1-32)Online publication date: 22-May-2020
https://dl.acm.org/doi/10.1145/3381832
Hao JXia SShum KChen BFu FYang Y(2020)Bounds and Constructions of Locally Repairable Codes: Parity-Check Matrix ApproachIEEE Transactions on Information Theory10.1109/TIT.2020.302170766:12(7465-7474)Online publication date: 20-Nov-2020
https://dl.acm.org/doi/10.1109/TIT.2020.3021707
Liu JMesnager STang D(2020)Constructions of optimal locally recoverable codes via Dickson polynomialsDesigns, Codes and Cryptography10.1007/s10623-020-00731-088:9(1759-1780)Online publication date: 1-Sep-2020
https://dl.acm.org/doi/10.1007/s10623-020-00731-0
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents