Hierarchical erasure correction of linear codes

DOI10.1016/J.FFA.2020.101743MaRDI QIDQ1994962zbMATH OpenOpenAlexFDO

Authors Netanel Raviv, Moshe Schwartz, Rami Cohen, Yuval Cassuto

Publication date 18 February 2021

Published in Finite Fields and their Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1802.02265

zbMATH Keywords

erasure-correcting codeshierarchical erasureslinear codes

Mathematics Subject Classification ID

Algebraic coding theory; cryptography (number-theoretic aspects) (11T71) Linear codes (general theory) (94B05)

Abstract: Linear codes over finite extension fields have widespread applications in theory and practice. In some scenarios, the decoder has a sequential access to the codeword symbols, giving rise to a hierarchical erasure structure. In this paper we develop a mathematical framework for hierarchical erasures over extension fields, provide several bounds and constructions, and discuss potential applications in distributed storage and flash memories. Our results show intimate connection to Universally Decodable Matrices, as well as to Reed-Solomon and Gabidulin codes.

Review text

Let \(q\) be a prime power and let \(\mathbf{F}_{q^\alpha}\) be a field extension of \(\mathbf{F}_{q}.\) Codes in \(\mathbf{F}_{q^\alpha}^n\) are useful when the decoder receives each codeword sequentially where codeword symbols are viewed as vectors over the field \(\mathbf{F}_{q}.\) The authors give several constructions of codes in this setting and give the value of \(t\) for which the code is a \(t\)-error correcting code. They show that Gabidulin codes, which are a well-known family of rank metric codes, can be used in this setting to protect against a large family of erasure patterns. Additionally, they give several possible applications for these codes.

Recommendations

• Recovering erasures by using MDS codes over extension alphabets
• Efficient erasure correcting codes
• Infinite families of optimal linear codes and their applications to distributed storage systems
• Linearized decomposition codes and finite integer set coverings
• Codes correcting restricted errors

Cites work

• Approximately universal codes over slow-fading channels
• Codes for the \(m\)-metric
• scientific article; zbMATH DE number 3174791 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• Introduction to Coding Theory
• Iterative Decoding of LDPC Codes Over the <inline-formula> <tex-math notation="LaTeX">$q$ </tex-math> </inline-formula>-Ary Partial Erasure Channel
• LDPC Codes Over the $q$ -ary Multi-Bit Channel
• On linear ordered codes
• On sets of vectors of a finite vector space in which every subset of basis size is a basis
• On sets of vectors of a finite vector space in which every subset of basis size is a basis. II
• On the Existence of Universally Decodable Matrices
• On universally decodable matrices for space-time coding
• Repairing Algebraic Geometry Codes
• Repairing Reed-Solomon Codes

Cited in

(3)

• Erasure correction by low-density codes
• Linearized decomposition codes and finite integer set coverings
• Recovering erasures by using MDS codes over extension alphabets

This page was built for publication: Hierarchical erasure correction of linear codes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1994962)