|
| | | | |
| | | |
| Stat |
Members: 3645
Articles: 2'500'096
Articles rated: 2609
18 April 2024 |
|
| | | | |
|
Article overview
| |
|
|
Asymptotic Improvement of the Gilbert-Varshamov Bound on the Size of Binary Codes | | Tao Jiang
; Alexander Vardy
; | | Date: |
19 Apr 2004 | | Journal: | IEEE TRANSACTIONS ON INFORMATION THEORY, vol. 50, No. 8, pp. 1655-1664, August 2004 (http://www.ieeexplore.ieee.org/iel5/18/29198/01317112.pdf) DOI: 10.1109/TIT.2004.831751 | | Subject: | Combinatorics; Commutative Algebra; Information Theory MSC-class: 05C90, 94B65 (Primary) 05A16, 05C69 (secondary) | math.CO cs.IT math.AC | | Abstract: | 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) geq 2^n/V(n,d-1)$, where $V(n,d) = sum_{i=0}^{d} {n choose i}$ 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) geq c frac{2^n}{V(n,d-1)} log_2 V(n,d-1) $$ whenever $d/n le 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. | | Source: | arXiv, math.CO/0404325 | | Services: | Forum | Review | PDF | Favorites | |
|
|
No review found.
Did you like this article?
Note: answers to reviews or questions about the article must be posted in the forum section.
Authors are not allowed to review their own article. They can use the forum section.
browser claudebot
|
| |
|
|
|
|
News, job offers and information for researchers and scientists:
| |
REGISTER