Please use this identifier to cite or link to this item: https://hdl.handle.net/10356/81744
Full metadata record
DC FieldValueLanguage
dc.contributor.authorDing, Yangen
dc.contributor.authorJin, Lingfeien
dc.contributor.authorXing, Chaopingen
dc.date.accessioned2016-01-12T06:14:59Zen
dc.date.accessioned2019-12-06T14:39:38Z-
dc.date.available2016-01-12T06:14:59Zen
dc.date.available2019-12-06T14:39:38Z-
dc.date.issued2014en
dc.identifier.citationDing, Y., Jin, L., & Xing, C. (2014). Erasure List-Decodable Codes From Random and Algebraic Geometry Codes. IEEE Transactions on Information Theory, 60(7), 3889-3894.en
dc.identifier.issn0018-9448en
dc.identifier.urihttps://hdl.handle.net/10356/81744-
dc.description.abstractErasure list decoding was introduced to correct a larger number of erasures by outputting a list of possible candidates. In this paper, we consider both random linear codes and algebraic geometry codes for list decoding from erasures. The contributions of this paper are twofold. First, for arbitrary 0 < R < 1 and ϵ > 0 (R and ϵ are independent), we show that with high probability a q-ary random linear code of rate R is an erasure list-decodable code with constant list size qO(1/ϵ) that can correct a fraction 1 - R - ϵ of erasures, i.e., a random linear code achieves the information-theoretic optimal tradeoff between information rate and fraction of erasures. Second, we show that algebraic geometry codes are good erasure list-decodable codes. Precisely speaking, a q-ary algebraic geometry code of rate R from the Garcia-Stichtenoth tower can correct 1 - R - (1/√q - 1) + (1/q) - ϵ fraction of erasures with list size O(1/ϵ). This improves the Johnson bound for erasures applied to algebraic geometry codes. Furthermore, list decoding of these algebraic geometry codes can be implemented in polynomial time. Note that the code alphabet size q in this paper is constant and independent of ϵ.en
dc.description.sponsorshipASTAR (Agency for Sci., Tech. and Research, S’pore)en
dc.format.extent7 p.en
dc.language.isoenen
dc.relation.ispartofseriesIEEE Transactions on Information Theoryen
dc.rights© 2014 IEEE. Personal use of this material is permitted. Permission from IEEE must be obtained for all other uses, in any current or future media, including reprinting/republishing this material for advertising or promotional purposes, creating new collective works, for resale or redistribution to servers or lists, or reuse of any copyrighted component of this work in other works. The published version is available at: [http://dx.doi.org/10.1109/TIT.2014.2314468].en
dc.subjectErasure codes; list decoding; algebraic geometry codes; generalized Hamming weightsen
dc.titleErasure List-Decodable Codes From Random and Algebraic Geometry Codesen
dc.typeJournal Articleen
dc.contributor.schoolSchool of Physical and Mathematical Sciencesen
dc.identifier.doi10.1109/TIT.2014.2314468en
dc.description.versionAccepted versionen
item.fulltextWith Fulltext-
item.grantfulltextopen-
Appears in Collections:SPMS Journal Articles
Files in This Item:
File Description SizeFormat 
Erasure List-Decodable Codes from Random and Algebraic Geometry Codes.pdf279.88 kBAdobe PDFThumbnail
View/Open

SCOPUSTM   
Citations 50

5
Updated on Jun 6, 2024

Web of ScienceTM
Citations 50

4
Updated on Oct 30, 2023

Page view(s) 50

602
Updated on Jun 13, 2024

Download(s) 20

202
Updated on Jun 13, 2024

Google ScholarTM

Check

Altmetric


Plumx

Items in DR-NTU are protected by copyright, with all rights reserved, unless otherwise indicated.