Explicit List-Decodable Rank-Metric and Subspace Codes via Subspace Designs
Authors:
- 21 March 2016
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 62 (5) , 2707-2718
Abstract
We construct an explicit family of Fh-linear rankmetric codes over any field Fh that enables efficient list-decoding up to a fraction p of errors in the rank metric with a rate of 1 - ρ - e, for any desired ρ ∈ (0, 1) and e > 0. This is the first explicit construction of positive rate rank-metric codes for efficient list-decoding beyond the unique decoding radius. Our codes are explicit subcodes of the well-known Gabidulin codes, which encode linearized polynomials of low degree via their values at a collection of linearly independent points. The subcode is picked by restricting the message polynomials to an Fh-subspace that evades the structured subspaces over an extension field Fht that arise in our linear-algebraic list decoder for Gabidulin codes. This subspace is obtained by combining subspace designs constructed by Guruswami and Kopparty (FOCS'13) with subspace-evasive varieties due to Dvir and Lovett (STOC'12). We establish a similar result for subspace codes, which have received much attention recently in the context of network coding. We also give explicit subcodes of folded Reed-Solomon (RS) codes with small folding order, which are list-decodable (in the Hamming metric) with optimal redundancy, motivated by the fact that listdecoding RS codes reduces to list-decoding such folded RS codes. However, as we only list-decode a subcode of these codes, the Johnson radius continues to be the best known error fraction for list-decoding RS codes.Keywords
Funding Information
- National Science Foundation within the Division of Computing and Communication Foundations (CCF-0963975)
This publication has 28 references indexed in Scilit:
- Explicit Subspace Designs2013
- Bounds on List Decoding of Rank-Metric CodesIEEE Transactions on Information Theory, 2013
- List decoding reed-solomon, algebraic-geometric, and gabidulin subcodes up to the singleton bound2013
- Linear-Algebraic List Decoding for Variants of Reed–Solomon CodesIEEE Transactions on Information Theory, 2013
- Folded codes from function field towers and improved optimal rate list decoding2012
- List decoding subspace codes from insertions and deletions2012
- Skew-Feedback Shift-Register Synthesis and Decoding Interleaved Gabidulin CodesIEEE Transactions on Information Theory, 2011
- A Rank-Metric Approach to Error Control in Random Network CodingIEEE Transactions on Information Theory, 2008
- Explicit Codes Achieving List Decoding Capacity: Error-Correction With Optimal RedundancyIEEE Transactions on Information Theory, 2008
- Ideals over a Non-Commutative Ring and their Application in Cryptology2001