Computer Science – Information Theory
Scientific paper
2011-06-30
Computer Science
Information Theory
To be presented at 3ICMCTA, the 3rd International Castle Meeting on Coding Theory and Applications, Sept. 11-15, 2011
Scientific paper
The Gilbert-Varshamov (GV) lower bound on the maximum cardinality of a q-ary code of length n with minimum Hamming distance at least d can be obtained by application of Turan's theorem to the graph with vertex set {0,1,..,q-1}^n in which two vertices are joined if and only if their Hamming distance is at least d. We generalize the GV bound by applying Turan's theorem to the graph with vertex set C^n, where C is a q-ary code of length m and two vertices are joined if and only if their Hamming distance at least d. We asymptotically evaluate the resulting bound for n-> \infty and d \delta mn for fixed \delta > 0, and derive conditions on the distance distribution of C that are necessary and sufficient for the asymptotic generalized bound to beat the asymptotic GV bound. By invoking the Delsarte inequalities, we conclude that no improvement on the asymptotic GV bound is obtained. By using a sharpening of Turan's theorem due to Caro and Wei, we improve on our bound. It is undecided if there exists a code C for which the improved bound can beat the asymptotic GV bound.
No associations
LandOfFree
A generalisation of the Gilbert-Varshamov bound and its asymptotic evaluation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with A generalisation of the Gilbert-Varshamov bound and its asymptotic evaluation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A generalisation of the Gilbert-Varshamov bound and its asymptotic evaluation will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-35108