Balanced and sparse Tamo-Barg codes

Wael Halbawi, Iwan Duursma, Hoang Dau, Babak Hassibi

Research output: Chapter in Book/Report/Conference proceedingConference contribution

2 Scopus citations

Abstract

We construct balanced and sparse generator matrices for Tamo and Barg's Locally Recoverable Codes (LRCs). More specifically, for a cyclic Tamo-Barg code of length n, dimension k and locality r, we show how to deterministically construct a generator matrix where the number of nonzeros in any two columns differs by at most one, and where the weight of every row is d + r - 1, where d is the minimum distance of the code. Since LRCs are designed mainly for distributed storage systems, the results presented in this work provide a computationally balanced and efficient encoding scheme for these codes. The balanced property ensures that the computational effort exerted by any storage node is essentially the same, whilst the sparse property ensures that this effort is minimal. The work presented in this paper extends a similar result previously established for Reed-Solomon (RS) codes, where it is now known that any cyclic RS code possesses a generator matrix that is balanced as described, but is sparsest, meaning that each row has d nonzeros.
Original languageEnglish (US)
Title of host publication2017 IEEE International Symposium on Information Theory (ISIT)
PublisherInstitute of Electrical and Electronics Engineers (IEEE)
Pages1018-1022
Number of pages5
ISBN (Print)9781509040964
DOIs
StatePublished - Aug 29 2017
Externally publishedYes

Fingerprint Dive into the research topics of 'Balanced and sparse Tamo-Barg codes'. Together they form a unique fingerprint.

Cite this