共 42 条
Asymptotic improvement of the Gilbert-Varshamov bound on the size of binary codes
被引:51
|作者:
Jiang, T
[1
]
Vardy, A
机构:
[1] Miami Univ, Dept Math & Stat, Oxford, OH 45056 USA
[2] Univ Calif San Diego, Dept Elect & Comp Engn, Dept Comp Sci & Engn, La Jolla, CA 92093 USA
[3] Univ Calif San Diego, Dept Math, La Jolla, CA 92093 USA
基金:
美国国家科学基金会;
关键词:
Ajtai-Komlos-Szemeredi bound;
asymptotic constructions;
binary codes;
constant-weight codes;
Gilbert-Varshamov bound;
locally sparse graphs;
nonlinear codes;
D O I:
10.1109/TIT.2004.831751
中图分类号:
TP [自动化技术、计算机技术];
学科分类号:
0812 ;
摘要:
Given positive integers n and d, let A(2) (n, d) denote the maximum size of a binary code of length n and minimum distance d. The well-known Gilbert-Varshamov bound asserts that A(2) (n, d) greater than or equal to 2(n)/V (n, d - 1), where V (n, d) = Sigma(i=0)(d) (7) is the volume of a Hamming sphere of radius d. We show that, in fact, there exists a positive constant c such that A(2) (n, d) greater than or equal to c 2(n) / V(n, d-1) log(2) V(n, d-1) whenever d/n less than or equal to, 0.499. The result follows by recasting the Gilbert-Varshamov bound into a graph-theoretic framework and using the fact that the corresponding graph is locally sparse. Generalizations and extensions of this result are briefly discussed.
引用
收藏
页码:1655 / 1664
页数:10
相关论文