Semidefinite Code Bounds Based on Quadruple Distances
Semidefinite Code Bounds Based on Quadruple Distances
复制标题
基于四倍距离的半定码界
DOI：
--
复制
发表时间：
2010
影响因子：
2.5
通讯作者：
A. Schrijver
中科院分区：
文献类型：
--
作者：
D. Gijswijt;H. Mittelmann;A. Schrijver
设<i>A</i>（<i>n</i>，<i>d</i>）是长度为n的0，1字的最大数目，任何两个具有至少<i>d</i>的汉明距离。<i></i>证明了<i>A</i>（20，8）=256，这意味着四倍缩短Golay码是最优的。此外，它表明，<i>A</i>（18，6）≤ 673，<i>A</i>（19，6）≤ 1237，<i>A</i>（20，6）≤ 2279，<i>A</i>（23，6）≤ 13674，<i>A</i>（19，8）≤ 135，<i>A</i>（25，8）≤ 5421，<i>A</i>（26，8）≤ 9275，<i>A</i>（27，8）≤ 17099，<i>A</i>（21，10）≤ 47，<i>A</i>（22，10）≤ 84，<i>A</i>（24，10）≤ 268，<i>A</i>（25，10）≤ 466，A（26，10）≤ 836，<i>A</i>（27，10）≤ 1585，<i>A</i>（28，10）≤ 2817，<i>A</i>（25，12）≤ 55，<i>A</i>（26，12）≤ 96。<i></i>该方法是基于正半定矩阵的四元组的话。这可以作为半定规划中的约束，其最优值是<i>A</i>（<i>n</i>，<i>d</i>）的上界。所涉及的矩阵的阶数是巨大的。然而，半定规划是高度对称的，它的可行域可以被限制为在这种对称下不变的矩阵代数。通过将该代数块对角化，矩阵的阶将被降低，从而使得程序在上述<i>n</i>和<i>d</i>的值范围内可以用半定编程软件求解。
Let <i>A</i>(<i>n</i>,<i>d</i>) be the maximum number of 0, 1 words of length <i>n</i> , any two having Hamming distance at least <i>d</i>. It is proved that <i>A</i>(20,8)=256, which implies that the quadruply shortened Golay code is optimal. Moreover, it is shown that <i>A</i>(18,6) ≤ 673, <i>A</i>(19,6) ≤ 1237, <i>A</i>(20,6) ≤ 2279, <i>A</i>(23,6) ≤ 13674, <i>A</i>(19,8) ≤ 135, <i>A</i>(25,8) ≤ 5421, <i>A</i>(26,8) ≤ 9275, <i>A</i>(27,8) ≤ 17099, <i>A</i>(21,10) ≤ 47, <i>A</i>(22,10) ≤ 84, <i>A</i>(24,10) ≤ 268, <i>A</i>(25,10) ≤ 466, <i>A</i>(26,10) ≤ 836, <i>A</i>(27,10) ≤ 1585, <i>A</i>(28,10) ≤ 2817, <i>A</i>(25,12) ≤ 55, and <i>A</i>(26,12) ≤ 96. The method is based on the positive semidefiniteness of matrices derived from quadruples of words. This can be put as constraint in a semidefinite program, whose optimum value is an upper bound for <i>A</i>(<i>n</i>,<i>d</i>). The order of the matrices involved is huge. However, the semidefinite program is highly symmetric, by which its feasible region can be restricted to the algebra of matrices invariant under this symmetry. By block diagonalizing this algebra, the order of the matrices will be reduced so as to make the program solvable with semidefinite programming software in the above range of values of <i>n</i> and <i>d</i>.