Perfect codes on graphs
Perfect codes on graphs
复制标题
DOI：
10.1109/isit.1997.613389
复制
发表时间：
1997-06
期刊：
影响因子：
--
通讯作者：
Paul Cull
中科院分区：
文献类型：
--
作者：
Paul Cull
标准纠错码的码字集合可以被视为超立方体的顶点的子集。当两个顶点的汉明距离为1时，超立方体中的两个顶点恰好是相邻的。如果没有两个码字相邻，且每个非码字恰好与一个码字相邻，则这样的码是完美的1-纠错码。由于完美码只能使用顶点和邻接来描述，所以该定义适用于一般图，而不仅仅适用于超立方体。如何判断一个图是否支持完美的1纠错码？显示这样的代码存在的最明显的方法是显示代码。另一方面，似乎很难证明一个图不支持这样的代码。我们通过证明判定一个图是否有完美的1-纠错码是一个NP-完全问题来证明这一直觉是正确的。
The set of codewords for a standard error-correcting code can be viewed as a subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. Such a code is a perfect 1-error-correcting code if no two codewords are adjacent, and if every non-codeword is adjacent to exactly one codeword. Since a perfect code can be described using only vertices and adjacency, the definition applies to general graphs rather than only to hypercubes. How does one decide if a graph can support a perfect 1-error-correcting code? The obvious way to show that such a code exists is to display the code. On the other hand, it seems difficult to show that a graph does not support such a code. We show that this intuition is right by showing that to determine if a graph has a perfect 1-error-correcting code is an NP-complete problem.