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

article

Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes

Authors:

Alexander Barg,

Sreechakra Goparaju,

Robert CalderbankAuthors Info & Claims

International Journal of Information and Coding Theory, Volume 3, Issue 4

Pages 345 - 364

https://doi.org/10.1504/IJICOT.2016.079496

Published: 01 January 2016 Publication History

Abstract

We consider linear cyclic codes with the locality property or locally recoverable codes LRC codes. A family of LRC codes that generalises the classical construction of Reed-Solomon codes was constructed in a recent paper by Tamo and Barg IEEE Transactions on Information Theory, No. 8, 2014. In this paper, we focus on distance-optimal cyclic codes that arise from this construction. We give a characterisation of these codes in terms of their zeros and observe that there are many equivalent ways of constructing optimal cyclic LRC codes over a given field. We also study subfield subcodes of cyclic LRC codes BCH-like LRC codes and establish several results about their locality and minimum distance. The locality parameter of a cyclic code is related to the dual distance of this code, and we phrase our results in terms of upper bounds on the dual distance.

References

[1]

Cadambe, V. and Mazumdar, A. (2015) 'Upper bounds on the size of locally recoverable codes', IEEE Transactions on Information Theory, Vol. 61, No. 8, pp.5787-5794.

[2]

Delsarte, P. (1975) 'On subfield subcodes of modified Reed-Solomon codes', IEEE Transactions on Information Theory, Vol. 21, No. 5, pp.575-576.

[3]

Ding, C. and Yang, J. (2013) 'Hamming weights in irreducible cyclic codes', Discrete Mathematics, Vol. 313, No. 4, pp.434-446.

[4]

Gopalan, P., Huang, C., Simitci, H. and Yekhanin, S. (2011) 'On the locality of codeword symbols', IEEE Transactions on Information Theory, Vol. 58, No. 11, pp.6925-6934.

[5]

Goparaju, S. and Calderbank, R. (2014) 'Binary cyclic codes that are locally repairable', Proc. 2014 IEEE Int. Sympos. Inform. Theory, Honolulu, HI, pp.676-680.

[6]

Hu, S., Tamo, I. and Barg, A. (2016) 'Combinatorial and LP bounds for LRC codes', Proc. 2016 IEEE International Symposium on Information Theory, Barcelona, Spain, July 10-15, 2016, pp.1008-1012.

[7]

Kamath, G.M., Prakash, N., Lalitha, V. and Kumar, P.V. (2014) 'Codes with local regeneration and erasure correction', IEEE Transactions on Information Theory, Vol. 60, No. 8, pp.4637-4660.

[8]

McEliece, R.J. (1974) 'Irreducible cyclic codes and Gauss sums', Combinatorics (Proc. NATO Advanced Study Inst., Breukelen, 1974), Part 1: Theory of designs, finite geometry and coding theory, Math. Centre Tracts, Math. Centrum, Amsterdam, No. 55, pp.179-196.

[9]

Papailiopoulos, D.S. and Dimakis, A.G. (2012) 'Locally repairable codes', Proc. 2012 IEEE Int. Sympos. Inform. Theory, Boston, MA, pp.2771-2775.

[10]

Pellikaan, R. (1996) 'The shift bound for cyclic, Reed-Muller, and geometric Goppa codes', in Pellikaan, R., Perret, M. and Vladut, S.G. (Eds.): Arithmetic, Geometry and Coding Theory 4, Luminy 1993, Walter de Gruyter, Berlin, pp.155-174.

[11]

Prakash, N., Kamath, G.M., Lalitha, V. and Kumar, P.V. (2012) 'Optimal linear codes with a local-error-correction property', Proc. 2012 IEEE Internat. Sympos. Inform. Theory, Boston, MA, pp.2776-2780.

[12]

Rawat, A.S., Koyluoglu, O., Silberstein, N. and Vishwanath, S. (2014) 'Optimal locally repairable and secure codes for distributed storage systems', IEEE Transactions on Information Theory, Vol. 60, No. 1, pp.212-236.

Digital Library

[13]

Tamo, I. and Barg, A. (2014) 'A family of optimal locally recoverable codes', IEEE Transactions on Information Theory, Vol. 60, No. 8, pp.4661-4676.

[14]

Tamo, I., Barg, A. and Frolov, A. (2016) 'Bounds on the parameters of locally recoverable codes', IEEE Transactions on Information Theory, Vol. 62, No. 6, pp.3070-3083.

Digital Library

[15]

Tamo, I., Barg, A., Goparaju, S. and Calderbank, R. (2015) 'Cyclic LRC codes and their subfield subcodes', Proc. 2015 IEEE International Symposium on Information Theory, Hong Kong, China, 14-19 June 2015, pp.1262-1266.

[16]

Tamo, I., Papailiopoulos, D.S. and Dimakis, A.G. (2013) 'Optimal locally repairable codes and connections to matroid theory', Proc. 2013 IEEE Internat. Sympos. Inform. Theory, Istanbul, Turkey, pp.1814-1818.

[17]

van Lint, J.H. (1992) Introduction to Coding Theory, Vol. 86, Springer-Verlag, Berlin.

[18]

van Lint, J.H. and Wilson, R.M. (1986) 'On the minimum distance of cyclic codes', IEEE Transactions on Information Theory, Vol. 32, No. 1, pp.23-40.

Digital Library

[19]

Wang, A. and Zhang, Z. (2015) 'An integer programming based bound for locally repairable codes', IEEE Transactions on Information Theory, Vol. 61, No. 11, pp.5280-5294.

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
Qiu JFang WFu F(2024)New Lower Bounds for the Minimum Distance of Cyclic Codes and Applications to Locally Repairable CodesIEEE Transactions on Information Theory10.1109/TIT.2024.334956070:7(4968-4982)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3349560
Hao JXia SShum KChen BFu FYang Y(2024)Optimal ternary locally repairable codesDesigns, Codes and Cryptography10.1007/s10623-024-01409-792:9(2685-2704)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10623-024-01409-7
Show More Cited By

Cyclic LRC codes, binary LRC codes, and upper bounds on the distance of cyclic codes
1. Mathematics of computing
  1. Information theory
2. Security and privacy
  1. Cryptography

Recommendations

Projective two-weight irreducible cyclic and constacyclic codes

After several remarks on two-weight irreducible cyclic codes, we introduce a family of projective two-weight cyclic codes and a family of projective two-weight constacyclic codes and we discuss the existence of such codes.
Cyclic R-additive codes

Bierbrauer (2012) developed the theory of q-linear cyclic codes over (Fq)m and he obtained a parametric description of such codes by cyclotomic cosets. Recently, Cao et al. (2015) obtained the structure of cyclic additive codes over the Galois ring GR(p,...
Binary divisible codes of maximum dimension

Divisible codes were introduced by H.N. Ward in 1981. A divisible code is a linear code over a finite field whose codewords all have weights divisible by some integer Δ > 1, where Δ is called a divisor of the code. A binary linear code is ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image International Journal of Information and Coding Theory

International Journal of Information and Coding Theory Volume 3, Issue 4

January 2016

137 pages

ISSN:1753-7703

EISSN:1753-7711

Issue’s Table of Contents

Publisher

Inderscience Publishers

Geneva 15, Switzerland

Publication History

Published: 01 January 2016

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

18
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 20 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
Qiu JFang WFu F(2024)New Lower Bounds for the Minimum Distance of Cyclic Codes and Applications to Locally Repairable CodesIEEE Transactions on Information Theory10.1109/TIT.2024.334956070:7(4968-4982)Online publication date: 4-Jan-2024
https://dl.acm.org/doi/10.1109/TIT.2024.3349560
Hao JXia SShum KChen BFu FYang Y(2024)Optimal ternary locally repairable codesDesigns, Codes and Cryptography10.1007/s10623-024-01409-792:9(2685-2704)Online publication date: 1-Sep-2024
https://dl.acm.org/doi/10.1007/s10623-024-01409-7
Cai HSchwartz M(2023)A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain ItIEEE Transactions on Information Theory10.1109/TIT.2022.322595369:4(2240-2260)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TIT.2022.3225953
Chen BZhang GLi W(2023)New Optimal Linear Codes With Hierarchical LocalityIEEE Transactions on Information Theory10.1109/TIT.2022.321828069:3(1544-1550)Online publication date: 1-Mar-2023
https://dl.acm.org/doi/10.1109/TIT.2022.3218280
Cai HSchwartz M(2022)A Bound on the Minimal Field Size of LRCs, and Cyclic MR Codes That Attain It2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834854(2625-2630)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834854
Qiu JFang WFu F(2022)Optimal and Almost Optimal Cyclic (r,δ)-LRCs With Large Code Lengths2022 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT50566.2022.9834361(3126-3131)Online publication date: 26-Jun-2022
https://dl.acm.org/doi/10.1109/ISIT50566.2022.9834361
Xu LZhou ZZhang JMesnager S(2022)Optimal quaternary -locally recoverable codes: their structures and complete classificationDesigns, Codes and Cryptography10.1007/s10623-022-01165-691:4(1495-1526)Online publication date: 27-Dec-2022
https://dl.acm.org/doi/10.1007/s10623-022-01165-6
Rajput CBhaintwal M(2022)On the locality of quasi-cyclic codes over finite fieldsDesigns, Codes and Cryptography10.1007/s10623-022-01009-390:3(759-777)Online publication date: 1-Mar-2022
https://dl.acm.org/doi/10.1007/s10623-022-01009-3
Hao JShum KXia SFu FYang Y(2021)On Optimal Quaternary Locally Repairable Codes2021 IEEE International Symposium on Information Theory (ISIT)10.1109/ISIT45174.2021.9518245(3267-3272)Online publication date: 12-Jul-2021
https://dl.acm.org/doi/10.1109/ISIT45174.2021.9518245
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents