Codes With Locality in the Rank and Subspace Metrics

DOI10.1109/TIT.2019.2915539MaRDI QIDQ5211379zbMATH OpenOpenAlexFDO

Authors Swanand Kadhe, Salim El Rouayheb, Alex Sprintson, Iwan Duursma

Publication date 28 January 2020

Published in IEEE Transactions on Information Theory (Search for Journal in Brave)

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

zbMATH Keywords

array codes with locality constraints in rank metricsubspace metric

Mathematics Subject Classification ID

Source coding (94A29) Other types of codes (94B60)

Abstract: We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from designing codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from 'crisscross errors and erasures', which affect a limited number of rows and/or columns of the storage system. We also derive a Singleton-like upper bound on the minimum rank distance of (linear) codes with 'rank-locality' constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures.

Recommendations

• Locality and Availability of Array Codes Constructed From Subspaces
• Rank-metric codes and their applications
• Codes in the sum-rank metric: fundamentals and applications
• Codes with the rank metric and matroids
• Locality via partially lifted codes
• The minimum locality of linear codes
• Rank-metric codes as ideals for subspace codes and their weight properties
• Error-Correcting Regenerating and Locally Repairable Codes via Rank-Metric Codes
• Cyclic and Convolutional Codes With Locality
• Encoding and decoding of several optimal rank metric codes

Cited in

(5)

• Universal secure rank-metric coding schemes with optimal communication overheads
• On the locality of codeword symbols in non-linear codes
• Locality and Availability of Array Codes Constructed From Subspaces
• Rank-metric codes and their applications
• Multilayer crisscross error and erasure correction

This page was built for publication: Codes With Locality in the Rank and Subspace Metrics

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