- Semidefinite code bounds based on quadruple distances
- IEEE Transactions on Information Theory
- Volume | Issue number
- 58 | 5
- Pages (from-to)
- Document type
- Faculty of Science (FNWI)
- Korteweg-de Vries Institute for Mathematics (KdVI)
Let A(n,d) be the maximum number of 0, 1 words of length n , any two having Hamming distance at least d. It is proved that A(20,8)=256, which implies that the quadruply shortened Golay code is optimal. Moreover, it is shown that A(18,6) ≤ 673, A(19,6) ≤ 1237, A(20,6) ≤ 2279, A(23,6) ≤ 13674, A(19,8) ≤ 135, A(25,8) ≤ 5421, A(26,8) ≤ 9275, A(27,8) ≤ 17099, A(21,10) ≤ 47, A(22,10) ≤ 84, A(24,10) ≤ 268, A(25,10) ≤ 466, A(26,10) ≤ 836, A(27,10) ≤ 1585, A(28,10) ≤ 2817, A(25,12) ≤ 55, and A(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 A(n,d). 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 n and d.
- go to publisher's site
If you believe that digital publication of certain material infringes any of your rights or (privacy) interests, please let the Library know, stating your reasons. In case of a legitimate complaint, the Library will make the material inaccessible and/or remove it from the website. Please Ask the Library, or send a letter to: Library of the University of Amsterdam, Secretariat, Singel 425, 1012 WP Amsterdam, The Netherlands. You will be contacted as soon as possible.