Linear Programming Bounds for Codes via a Covering Argument
Linear Programming Bounds for Codes via a Covering Argument
复制标题
通过覆盖参数的代码线性规划界限
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Alex Samorodnitsky
中科院分区：
文献类型：
--
作者：
M. Navon;Alex Samorodnitsky
通过一个覆盖引理，我们得到了McEliess，Rodemich，Rumsey和Welch关于二元纠错码和设计的第一个线性规划界。如果一个码的距离很大，那么它的对偶就有一个小的覆盖半径，因此是大的，这是可能的，适当地解释下面的概念。该方法属于Delsarte线性规划方法的一般框架，其主要技术成分是Hamming立方体的傅里叶对偶.特别地，我们不直接涉及Delsarte的线性规划或正交多项式理论。
We recover the first linear programming bound of McEliece, Rodemich, Rumsey, and Welch for binary error-correcting codes and designs via a covering argument. It is possible to show, interpreting the following notions appropriately, that if a code has a large distance, then its dual has a small covering radius and, therefore, is large. This implies the original code to be small.We also point out that this bound is a natural isoperimetric constant of the Hamming cube, related to its Faber–Krahn minima.While our approach belongs to the general framework of Delsarte’s linear programming method, its main technical ingredient is Fourier duality for the Hamming cube. In particular, we do not deal directly with Delsarte’s linear program or orthogonal polynomial theory.