 Author
 Year
 2012
 Title
 Semidefinite code bounds based on quadruple distances
 Journal
 IEEE Transactions on Information Theory
 Volume  Issue number
 58  5
 Pages (fromto)
 26972705
 Document type
 Article
 Faculty
 Faculty of Science (FNWI)
 Institute
 Kortewegde Vries Institute for Mathematics (KdVI)
 Abstract

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.
 URL
 go to publisher's site
 Language
 English
 Permalink
 http://hdl.handle.net/11245/1.378217
Disclaimer/Complaints regulations
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.