DocumentCode :
77373
Title :
On List-Decodability of Random Rank Metric Codes and Subspace Codes
Author :
Yang Ding
Author_Institution :
Dept. of Math., Shanghai Univ., Shanghai, China
Volume :
61
Issue :
1
fYear :
2015
fDate :
Jan. 2015
Firstpage :
51
Lastpage :
59
Abstract :
Codes in rank metric have a wide range of applications. To construct such codes with better list-decoding performance explicitly, it is of interest to investigate the listdecodability of random rank metric codes. It is shown that if n/m = b is a constant, then for every rank metric code in Fm×n q with rate R and list-decoding radius ρ must obey the Gilbert-Varshamov bound, that is, R ≤ (1-ρ)(1-bρ). Otherwise, the list size can be exponential and hence no polynomial-time list decoding is possible. On the other hand, for arbitrary 0 <; ρ <; 1 and E > 0, with E and ρ being independent of each other, with high probability, a random rank metric code with rate R = (1 - ρ)(1 - bρ) - can be efficiently list-decoded up to a fraction ρ of rank errors with constant list size O(1/E). We establish similar results for constant-dimension subspace codes. Moreover, we show that, with high probability, the list-decoding radius of random Fq-linear rank metric codes also achieve the Gilbert-Varshamov bound with constant list size O(exp(1/E)).
Keywords :
codes; probability; Gilbert-Varshamov bound; list-decoding performance; probability; random rank metric codes; subspace codes; Decoding; Educational institutions; Manganese; Measurement; Polynomials; Reed-Solomon codes; Vectors; Constant-dimension subspace codes; Gilbert- Varshamov bound; Gilbert-Varshamov bound; Singleton bound; constant-dimension subspace codes; list decoding; rank metric codes; sphere-covering bound;
fLanguage :
English
Journal_Title :
Information Theory, IEEE Transactions on
Publisher :
ieee
ISSN :
0018-9448
Type :
jour
DOI :
10.1109/TIT.2014.2371915
Filename :
6975226
Link To Document :
بازگشت