On the Hardness of Decoding the Gale–Berlekamp Code
On the Hardness of Decoding the Gale–Berlekamp Code
复制标题
论盖尔-伯勒坎普码的破译难度
DOI：
10.1109/isit.2007.4557411
复制
发表时间：
2007
影响因子：
2.5
通讯作者：
K. Viswanathan
中科院分区：
文献类型：
--
作者：
R. Roth;K. Viswanathan
Gale-Berlekamp(简称GB)码是二进制乘积码的对偶码，其中水平和垂直分量码都是奇偶码。结果表明，判定在给定接收字的规定距离内是否存在国标码的码字是NP完全问题。这个问题仍然很难(在明确定义的意义上)，即使解码器被允许进行仅依赖于代码长度的无限预处理。虽然Bruck和Naor、Lobstein以及Guruswami和Vardy已经证明了特定代码的最大似然译码(MLD)的难解性，但这里的结果似乎是第一个显示了对于“自然”代码的难度(尤其是，没有对代码的定义或参数进行任何调整以适应硬度证明)。相反，对于任何交叉概率小于1/2的无记忆二进制对称信道(BSC)，除了以消失概率出现的部分错误事件外，对于所有错误事件，MLD都可以在线性时间内实现。
The Gale-Berlekamp (in short, GB) code is the dual code of the binary product code in which the horizontal and vertical constituent codes are both the parity code. It is shown that the problem of deciding whether there is a codeword of the GB code within a prescribed distance from a given received word, is NP-complete. The problem remains hard (in a well-defined sense) even if the decoder is allowed unlimited preprocessing that depends only on the code length. While the intractability of maximum-likelihood decoding (MLD) for specific codes has already been shown by Bruck and Naor, Lobstein, and Guruswami and Vardy, the result herein seems to be the first that shows hardness for a "natural" code (in particular, without any tailoring of the definition or the parameters of the code to suit the hardness proof). In contrast, it is also shown that, with respect to any memoryless binary-symmetric channel (BSC) with crossover probability less than 1/2, MLD can be implemented in linear time for all error events except for a portion that occurs with vanishing probability.