Code with locality 

Description

A code with \((r,\delta)\) locality is a code that encodes each codeword coordinate into an \([r+\delta-1,r,\delta]\) MDS code [1; Sec. 31.3.4.5]. In other words, given a codeword \(c\) and coordinate \(c_i\), there exists a coordinate set \(S_i\) of size \(\leq r+\delta-1\) such that the restriction \(C_{|S_i}\) of the code to that set is a code with minimum distance \(\delta\).

Protection

There is a generalized Singleton minimum distance bound [2], \begin{align} d\leq n-k+1-(\left\lceil k/r\right\rceil -1)(\delta-1)~, \tag*{(1)}\end{align} with codes saturating this bound being optimal codes with locality. The \(\delta=2\) case recovers optimal LRCs.

Parent

Children

References

[1]
V. Ramkumar, M. Vajha, S. B. Balaji, M. Nikhil Krishnan, B. Sasidharan, P. Vijay Kumar, "Codes for Distributed Storage." Concise Encyclopedia of Coding Theory (Chapman and Hall/CRC, 2021) DOI
[2]
N. Prakash et al., “Optimal Linear Codes with a Local-Error-Correction Property”, (2012) arXiv:1202.2414
Page edit log

Your contribution is welcome!

on github.com (edit & pull request)— see instructions

edit on this site

Zoo Code ID: code_with_locality

Cite as:
“Code with locality”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/code_with_locality
BibTeX:
@incollection{eczoo_code_with_locality, title={Code with locality}, booktitle={The Error Correction Zoo}, year={2024}, editor={Albert, Victor V. and Faist, Philippe}, url={https://errorcorrectionzoo.org/c/code_with_locality} }
Share via:
Twitter | Mastodon |  | E-mail
Permanent link:
https://errorcorrectionzoo.org/c/code_with_locality

Cite as:

“Code with locality”, The Error Correction Zoo (V. V. Albert & P. Faist, eds.), 2024. https://errorcorrectionzoo.org/c/code_with_locality

Github: https://github.com/errorcorrectionzoo/eczoo_data/edit/main/codes/classical/properties/block/distributed_storage/lrc/code_with_locality.yml.