On Rational Interpolation-Based List-Decoding and List-Decoding Binary Goppa Codes

被引：13

作者：

Beelen, Peter ^{[1
]}

Hoholdt, Tom ^{[1
]}

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

Wu, Yingquan ^{[2
]}

机构：

[1] Tech Univ Denmark, Dept Appl Math & Comp Sci, DK-2800 Lyngby, Denmark

[2] Sandforce Inc, Milpitas, CA 95035 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2013年 / 59卷 / 06期

基金：

新加坡国家研究基金会; 美国国家科学基金会;

关键词：

Goppa code; Johnson radius; list decoding; list size; rational interpolation; Reed-Solomon code; REED-SOLOMON CODES; POLYNOMIALS; EQUIVALENCE; ALGORITHMS; BERLEKAMP; EQUATIONS;

D O I：

10.1109/TIT.2013.2243800

中图分类号：

TP [自动化技术、计算机技术];

学科分类号：

0812 ;

摘要：

We derive the Wu list-decoding algorithm for generalized Reed-Solomon (GRS) codes by using Grobner bases over modules and the Euclidean algorithm as the initial algorithm instead of the Berlekamp-Massey algorithm. We present a novel method for constructing the interpolation polynomial fast. We give a new application of the Wu list decoder by decoding irreducible binary Goppa codes up to the binary Johnson radius. Finally, we point out a connection between the governing equations of the Wu algorithm and the Guruswami-Sudan algorithm, immediately leading to equality in the decoding range and a duality in the choice of parameters needed for decoding, both in the case of GRS codes and in the case of Goppa codes.

引用

页码：3269 / 3281

页数：13

共 31 条

[1]

Aho A. V., 1974, The design and analysis of computer algorithms

[2] 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

[3] A Parametric Approach to List Decoding of Reed-Solomon Codes Using Interpolation [J].

Ali, Mortuza ;

Kuijper, Margreta .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2011, 57 (10) :6718-6728

[4]

[Anonymous], 1978, The Theory of Error-Correcting Codes

[5]

[Anonymous], 2003, Modern Computer Algebra

[6]

Augot D., 2010, LIST DECODING BINARY

[7] 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

[8]

BERLEKAMP E., 2015, Algebraic Coding Theory

[9]

Bernstein D., 2011, SIMPLIFIED HIGH SPEE

[10]

Blahut R., 1983, Theory and Practice of Error Control Codes

← 1 2 3 4 →