New lower bounds on aperiodic crosscorrelation of binary codes
V.I. Levenshtein · IEEE Transactions on Information Theory · 1999
For the minimum aperiodic crosscorrelation /spl theta/(n,M) of binary codes of size M and length n over the alphabet {1,-1} there exists the celebrated Welch bound /spl theta//sup 2/(n,M)/spl ges/(M-1)n/sup 2//2Mn-N-1 which was published in 1974 and remained in this form up to now. In the article this bound is strengthened for all M/spl ges/4 and n/spl ges/2. In particular, it is proved that /spl theta//sup 2/(n,M)/spl ges/n-2n//spl radic/3M, M/spl ges/3 and /spl theta//sup 2/(n,M)/spl ges/n-[/spl pi/n//spl radic/8M], M/spl ges/5. In the asymptotic process when M tends to infinity as n/spl rarr//spl infin/, these bounds are twice as large as the Welch bound and coincide with the corresponding asymptotic bound on the square of the minimum periodic crosscorrelation of binary codes. The main idea of the proof is a new sufficient condition for the mean value of a nonnegative definite matrix over the code to be greater than or equal to the average over the whole space. This allows one to take into account weights of cyclic shifts of code vectors and solve the problem of their optimal choice.