Multi-trial Guruswami-Sudan decoding for generalised Reed-Solomon codes

被引：6

作者：

Nielsen, Johan S. R. ^{[1
]}

Zeh, Alexander ^{[1
,2
]}

机构：

[1] Univ Ulm, Inst Commun Engn, D-89069 Ulm, Germany

[2] Ecole Polytech, Res Ctr INRIA Saclay Ile de France, F-75230 Paris, France

来源：

DESIGNS CODES AND CRYPTOGRAPHY | 2014年 / 73卷 / 02期

关键词：

Guruswami-Sudan; List decoding; Multi-trial; Reed-Solomon codes; Re-encoding transformation; POLYNOMIALS; EQUATIONS;

D O I：

10.1007/s10623-014-9951-7

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

An iterated refinement procedure for the Guruswami-Sudan list decoding algorithm for Generalised Reed-Solomon codes based on Alekhnovich's module minimisation is proposed. The method is parametrisable and allows variants of the usual list decoding approach. In particular, finding the list of closest codewords within an intermediate radius can be performed with improved average-case complexity while retaining the worst-case complexity. We provide a detailed description of the module minimisation, reanalysing the Mulders-Storjohann algorithm and drawing new connections to both Alekhnovich's algorithm and Lee-O'Sullivan's. Furthermore, we show how to incorporate the re-encoding technique of Kotter and Vardy into our iterative algorithm.

引用

页码：507 / 527

页数：21

共 50 条

[41] Fast Error and Erasure Decoding Algorithm for Reed-Solomon Codes [J].

Tang, Nianqi ;

Chen, Chao ;

Han, Yunghsiang S. .

IEEE COMMUNICATIONS LETTERS, 2024, 28 (04) :759-762

[42] Decoding Reed-Solomon codes using Euclid’s algorithm [J].

Priti Shankar .

Resonance, 2007, 12 (4) :37-51

[43] Recovering Reed-Solomon Codes Privately [J].

Kruglik, Stanislav ;

Kiah, Han Mao ;

Dau, Son Hoang ;

Yaakobi, Eitan .

IEEE TRANSACTIONS ON INFORMATION FORENSICS AND SECURITY, 2025, 20 :2807-2821

[44] Efficient List-Decoding of Reed-Solomon Codes with the Fundamental Iterative Algorithm [J].

Zeh, Alexander ;

Gentner, Christian ;

Bossert, Martin .

2009 IEEE INFORMATION THEORY WORKSHOP (ITW 2009), 2009, :130-134

[45] Linear diophantine equations over polynomials and soft decoding of Reed-Solomon codes [J].

Alekhnovich, M .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2005, 51 (07) :2257-2265

[46] Key equations for list decoding of Reed-Solomon codes and how to solve them [J].

Beelen, Peter ;

Brander, Kristian .

JOURNAL OF SYMBOLIC COMPUTATION, 2010, 45 (07) :773-786

[47] Explicit Subcodes of Reed-Solomon Codes That Efficiently Achieve List Decoding Capacity [J].

Berman, Amit ;

Shany, Yaron ;

Tamo, Itzhak .

IEEE Transactions on Information Theory, 2025, 71 (08) :5898-5911

[48] Improved probabilistic decoding of interleaved Reed-Solomon codes and folded Hermitian codes [J].

Ozbudak, Ferruh ;

Yayla, Oguz .

THEORETICAL COMPUTER SCIENCE, 2014, 520 :111-123

[49] Multistage list decoding of generalized Reed-Solomon codes over Galois rings [J].

Armand, MA ;

de Taisne, O .

IEEE COMMUNICATIONS LETTERS, 2005, 9 (07) :625-627

[50] Combinatorial List-Decoding of Reed-Solomon Codes beyond the Johnson Radius [J].

Chong Shangguan ;

Tamo, Itzhak .

PROCEEDINGS OF THE 52ND ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING (STOC '20), 2020, :538-551

← 1 2 3 4 5 →