Local correction of codes of high rate
Locally correctable codes (LCC) are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. LCCs have found numerous applications in complexity theory, cryptography and the theory of fault tolerant compu...
Saved in:
Main Author: | |
---|---|
Other Authors: | |
Format: | Theses and Dissertations |
Language: | English |
Published: |
2017
|
Subjects: | |
Online Access: | http://hdl.handle.net/10356/69693 |
Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Institution: | Nanyang Technological University |
Language: | English |
id |
sg-ntu-dr.10356-69693 |
---|---|
record_format |
dspace |
spelling |
sg-ntu-dr.10356-696932023-02-28T23:33:24Z Local correction of codes of high rate Wu, Liyasi Chee Yeow Meng Xing Chaoping School of Physical and Mathematical Sciences DRNTU::Science::Mathematics Locally correctable codes (LCC) are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. LCCs have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. In this work, we investigate the locally correctable codes of high rate. We are mainly interested in new constructions of high-rate locally correctable codes, local correction of multiple bits, and the inner connection between the lifted Reed-Solomon codes and the multiplicity codes. Firstly, we extend the techniques of lifted Reed-Solomon codes by lifting multivariate polyno- mials on curves, and generalize the “decoding on curve” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound. Furthermore, we take a deeper look into the method of multiplicities and provide a new con- struction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the multiplicity codes and lifted Reed Solomon Codes. At last, we generalize the concept of traditional local correction to local correction of multiple bits, and present a family of codes which allow multiple bits to be recovered with probability approaching 1 by visiting a small number of locations of the received word, even when a constant fraction of errors exist. Moreover, our codes are of high rate. Doctor of Philosophy (SPMS) 2017-03-20T02:46:50Z 2017-03-20T02:46:50Z 2017 Thesis Wu, L. (2017). Local correction of codes of high rate. Doctoral thesis, Nanyang Technological University, Singapore. http://hdl.handle.net/10356/69693 10.32657/10356/69693 en 97 p. application/pdf |
institution |
Nanyang Technological University |
building |
NTU Library |
continent |
Asia |
country |
Singapore Singapore |
content_provider |
NTU Library |
collection |
DR-NTU |
language |
English |
topic |
DRNTU::Science::Mathematics |
spellingShingle |
DRNTU::Science::Mathematics Wu, Liyasi Local correction of codes of high rate |
description |
Locally correctable codes (LCC) are error-correcting codes with efficient decoding schemes, which can recover any bit of a codeword by visiting a small number of locations of the codeword. LCCs have found numerous applications in complexity theory, cryptography and the theory of fault tolerant computation. In this work, we investigate the locally correctable codes of high rate. We are mainly interested in new constructions of high-rate locally correctable codes, local correction of multiple bits, and the inner connection between the lifted Reed-Solomon codes and the multiplicity codes. Firstly, we extend the techniques of lifted Reed-Solomon codes by lifting multivariate polyno- mials on curves, and generalize the “decoding on curve” algorithm from Reed-Muller codes to these lifted codes to provide correcting algorithms with success probability arbitrarily approaching 1. This gives a family of high rate locally correctable codes that is highly sound. Furthermore, we take a deeper look into the method of multiplicities and provide a new con- struction of locally correctable codes of rate approaching 1, which is also a theoretical connection between the multiplicity codes and lifted Reed Solomon Codes. At last, we generalize the concept of traditional local correction to local correction of multiple bits, and present a family of codes which allow multiple bits to be recovered with probability approaching 1 by visiting a small number of locations of the received word, even when a constant fraction of errors exist. Moreover, our codes are of high rate. |
author2 |
Chee Yeow Meng |
author_facet |
Chee Yeow Meng Wu, Liyasi |
format |
Theses and Dissertations |
author |
Wu, Liyasi |
author_sort |
Wu, Liyasi |
title |
Local correction of codes of high rate |
title_short |
Local correction of codes of high rate |
title_full |
Local correction of codes of high rate |
title_fullStr |
Local correction of codes of high rate |
title_full_unstemmed |
Local correction of codes of high rate |
title_sort |
local correction of codes of high rate |
publishDate |
2017 |
url |
http://hdl.handle.net/10356/69693 |
_version_ |
1759853371347435520 |