Balanced and sparse Tamo-Barg codes

Wael Halbawi; Iwan Duursma; Hoang Dau; Babak Hassibi

doi:10.1109/isit.2017.8006682

Balanced and sparse Tamo-Barg codes

Wael Halbawi, Iwan Duursma, Hoang Dau, Babak Hassibi

Research output: Chapter in Book/Report/Conference proceeding › Conference 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 language	English (US)
Title of host publication	2017 IEEE International Symposium on Information Theory (ISIT)
Publisher	Institute of Electrical and Electronics Engineers (IEEE)
Pages	1018-1022
Number of pages	5
ISBN (Print)	9781509040964
DOIs	https://doi.org/10.1109/isit.2017.8006682
State	Published - Aug 29 2017
Externally published	Yes

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: The work of Wael Halbawi was supported by the Qatar Foundation-Research Division. The work of Iwan Duursma was supported in part by the NSF grant CCF 1619189. The work of Hoang Dau has been supported in part by the NSF grant CCF 1526875 and the Center for Science of Information under the grant NSF 093937. The work of Babak Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology.
This publication acknowledges KAUST support, but has no KAUST affiliated authors.

Access to Document

10.1109/isit.2017.8006682

Cite this

@inproceedings{89e13f730fb345aa8da36f0b6435c974,

title = "Balanced and sparse Tamo-Barg codes",

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.",

author = "Wael Halbawi and Iwan Duursma and Hoang Dau and Babak Hassibi",

note = "KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The work of Wael Halbawi was supported by the Qatar Foundation-Research Division. The work of Iwan Duursma was supported in part by the NSF grant CCF 1619189. The work of Hoang Dau has been supported in part by the NSF grant CCF 1526875 and the Center for Science of Information under the grant NSF 093937. The work of Babak Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology. This publication acknowledges KAUST support, but has no KAUST affiliated authors.",

year = "2017",

month = aug,

day = "29",

doi = "10.1109/isit.2017.8006682",

language = "English (US)",

isbn = "9781509040964",

pages = "1018--1022",

booktitle = "2017 IEEE International Symposium on Information Theory (ISIT)",

publisher = "Institute of Electrical and Electronics Engineers (IEEE)",

}

TY - GEN

T1 - Balanced and sparse Tamo-Barg codes

AU - Halbawi, Wael

AU - Duursma, Iwan

AU - Dau, Hoang

AU - Hassibi, Babak

N1 - KAUST Repository Item: Exported on 2020-10-01 Acknowledgements: The work of Wael Halbawi was supported by the Qatar Foundation-Research Division. The work of Iwan Duursma was supported in part by the NSF grant CCF 1619189. The work of Hoang Dau has been supported in part by the NSF grant CCF 1526875 and the Center for Science of Information under the grant NSF 093937. The work of Babak Hassibi was supported in part by the National Science Foundation under grants CNS-0932428, CCF-1018927, CCF-1423663 and CCF-1409204, by a grant from Qualcomm Inc., by NASAs Jet Propulsion Laboratory through the President and Directors Fund, by King Abdulaziz University, and by King Abdullah University of Science and Technology. This publication acknowledges KAUST support, but has no KAUST affiliated authors.

PY - 2017/8/29

Y1 - 2017/8/29

N2 - 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.

AB - 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.

UR - http://hdl.handle.net/10754/626676

UR - http://ieeexplore.ieee.org/document/8006682/

UR - http://www.scopus.com/inward/record.url?scp=85034115147&partnerID=8YFLogxK

U2 - 10.1109/isit.2017.8006682

DO - 10.1109/isit.2017.8006682

M3 - Conference contribution

SN - 9781509040964

SP - 1018

EP - 1022

BT - 2017 IEEE International Symposium on Information Theory (ISIT)

PB - Institute of Electrical and Electronics Engineers (IEEE)

ER -

Balanced and sparse Tamo-Barg codes

Abstract

Bibliographical note

Access to Document

Other files and links

Fingerprint

Cite this