Maximum-likelihood decoding of Reed-Solomon codes is NP-hard

被引：45

作者：

Guruswami, V ^{[1
]}

Vardy, A

机构：

[1] Univ Washington, Dept Comp Sci & Engn, Seattle, WA 98195 USA

[2] Univ Calif San Diego, Dept Elect & Comp Engn, La Jolla, CA 92093 USA

[3] Univ Calif San Diego, Dept Comp Sci, La Jolla, CA 92093 USA

[4] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA

来源：

IEEE TRANSACTIONS ON INFORMATION THEORY | 2005年 / 51卷 / 07期

基金：

美国国家科学基金会;

关键词：

linear codes; maximum-likelihood decoding; NP-hard problems; Reed-Solomon codes;

D O I：

10.1109/TIT.2005.850102

中图分类号：

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

学科分类号：

0812 ;

摘要：

Maximum-likelihood decoding is one of the central algorithmic problems in coding theory. It has been known for over 25 years that maximum-likelihood decoding of general linear codes is NP-hard. Nevertheless, it was so far unknown whether maximum-likelihood decoding remains hard for any specific family of codes with nontrivial algebraic structure. In this paper, we prove that maximum-likelihood decoding is NP-hard for the family of Reed-Solomon codes. We moreover show that maximum-likelihood decoding of Reed-Solomon codes remains hard even with unlimited preprocessing, thereby strengthening a result of Bruck and Naor.

引用

页码：2249 / 2256

页数：8

共 24 条

[1]

[Anonymous], 1979, Computers and Intractablity: A Guide to the Theoryof NP-Completeness

[2] The hardness of approximate optima in lattices, codes, and systems of linear equations [J].

Arora, S ;

Babai, L ;

Stern, J ;

Sweedyk, Z .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 1997, 54 (02) :317-331

[3]

BARG A, 1994, PROBL PEREDACHI INF, V30, P23

[4] INHERENT INTRACTABILITY OF CERTAIN CODING PROBLEMS [J].

BERLEKAMP, ER ;

MCELIECE, RJ ;

VANTILBORG, HCA .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1978, 24 (03) :384-386

[5] THE HARDNESS OF DECODING LINEAR CODES WITH PREPROCESSING [J].

BRUCK, J ;

NAOR, M .

IEEE TRANSACTIONS ON INFORMATION THEORY, 1990, 36 (02) :381-385

[6]

Cohen G, 1997, COVERING CODES

[7] The parametrized complexity of some fundamental problems in coding theory [J].

Downey, RG ;

Fellows, MR ;

Vardy, A ;

Whittle, G .

SIAM JOURNAL ON COMPUTING, 1999, 29 (02) :545-570

[8] Hardness of approximating the minimum distance of a linear code [J].

Dumer, I ;

Micciancio, D ;

Sudan, M .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2003, 49 (01) :22-37

[9] The inapproximability of lattice and coding problems with preprocessing [J].

Feige, U ;

Micciancio, D .

JOURNAL OF COMPUTER AND SYSTEM SCIENCES, 2004, 69 (01) :45-67

[10] HIGHLY RESILIENT CORRECTORS FOR POLYNOMIALS [J].

GEMMELL, P ;

SUDAN, M .

INFORMATION PROCESSING LETTERS, 1992, 43 (04) :169-174

← 1 2 3 →