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

被引：41
|
作者：
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
相关论文
共 50 条
  • [11] COMPLEXITY OF DECODING REED-SOLOMON CODES
    JUSTESEN, J
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1976, 22 (02) : 237 - 238
  • [12] THE DECODING OF EXTENDED REED-SOLOMON CODES
    DUR, A
    DISCRETE MATHEMATICS, 1991, 90 (01) : 21 - 40
  • [13] On Fractional Decoding of Reed-Solomon Codes
    Santos, Welington
    2019 IEEE INTERNATIONAL SYMPOSIUM ON INFORMATION THEORY (ISIT), 2019, : 1552 - 1556
  • [14] MAXIMUM-LIKELIHOOD DECODING OF CERTAIN REED-MULLER CODES
    SEROUSSI, G
    LEMPEL, A
    IEEE TRANSACTIONS ON INFORMATION THEORY, 1983, 29 (03) : 448 - 450
  • [15] Analysis of iterated hard decision decoding of product codes with Reed-Solomon component codes
    Justesen, Jorn
    Hoholdt, Tom
    2007 IEEE INFORMATION THEORY WORKSHOP, VOLS 1 AND 2, 2007, : 174 - +
  • [16] Soft Reed-Solomon decoding for concatenated codes
    Panigrahi, S
    Szczecinski, LL
    Labeau, F
    CCECE 2003: CANADIAN CONFERENCE ON ELECTRICAL AND COMPUTER ENGINEERING, VOLS 1-3, PROCEEDINGS: TOWARD A CARING AND HUMANE TECHNOLOGY, 2003, : 1643 - +
  • [17] Iterative soft decoding of Reed-Solomon codes
    Jiang, J
    Narayanan, KR
    IEEE COMMUNICATIONS LETTERS, 2004, 8 (04) : 244 - 246
  • [18] Power Decoding of Reed-Solomon Codes Revisited
    Nielsen, Johan S. R.
    CODING THEORY AND APPLICATIONS, 4TH INTERNATIONAL CASTLE MEETING, 2015, 3 : 297 - 305
  • [19] Soft decision decoding of Reed-Solomon codes
    Ponnampalam, V
    Vucetic, B
    IEEE TRANSACTIONS ON COMMUNICATIONS, 2002, 50 (11) : 1758 - 1768
  • [20] Unique Decoding of Certain Reed-Solomon Codes
    Shen, Lin-Zhi
    Fu, Fang-Wei
    Guang, Xuan
    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES, 2015, E98A (12): : 2728 - 2732
12345