4
$\begingroup$

The Gilbert-Varshamov bound provides a lower bound for codes of length $n$ with minimum pairwise distance (say $\frac{n}8$). If we wish for the codes to also have pairwise distances bounded above (say by $\frac{n}2$), is there an analogous result?

As an explicit example, what are the maximum number of codes, such that any two codes have pairwise distance between $\frac{n}8$ and $\frac{n}2$?

$\endgroup$
6
  • 1
    $\begingroup$ There are equidistant codes $\endgroup$ Commented Nov 1, 2023 at 1:54
  • $\begingroup$ I find myself a little confused about what we are trying to bound here. Could you possibly state it explicitly? $\endgroup$ Commented Nov 1, 2023 at 2:45
  • 1
    $\begingroup$ We can always consider codewords where the second half of the bits are all zero, reducing to "the largest code of length $n/2$ with minimum distance $n/4$." I wonder how much better is possible? $\endgroup$
    – usul
    Commented Nov 7, 2023 at 12:37
  • 1
    $\begingroup$ I am a bit curious. What kind of an application would want a code like this? It is in some case, easy to have a large set of words bounded from above by $n/2$. For example, take any binary linear code with a decent minimum distance such that the all ones word $\mathbf{1}$ is in there (= the class of self-complementary codes). Then for each word $x$ either $x$ or $x+\mathbf{1}$ has weight at most $n/2$, so one half of the codewords would be included. Of course, pairwise distances then won't be bounded. $\endgroup$ Commented Jan 1 at 12:39
  • 1
    $\begingroup$ (cont'd) In some applications complementary pairs of words are used to transmit one bit, and the rest is for scrambling or multiple access (like CDMA). Some channels (like optical fibre) require all the codewords to have a low weight, because the channel doesn't really add the signals together but rather bitise ORs them, and a high weight word, would ruin it for the other users. Anyway, I have been out of the research scene, so my imagination has been going down hill :-) $\endgroup$ Commented Jan 1 at 12:42

1 Answer 1

1
$\begingroup$

Instead of $\{0,1\}^n$, you may take as your code space a subset $S\subseteq\{0,1\}^n$ of diameter $D$. This will guarantee that, whatever code you define in $S$, its codewords will be at distance $\leq\! D$.

The usual Gilbert-Varshamov bound states that the cardinality of an optimal code of minimum distance $d$ in $\{0,1\}^n$ is lower-bounded by $$\frac{2^n}{B_n(d-1)},$$ where $$B_n(r)=\sum_{t=0}^r \binom{n}{t}$$ is the cardinality of (any) ball of radius $r$ in the Hamming space $\{0,1\}^n$. Note that, in your restricted space $S$, not all balls have the same cardinality, so it is not obvious how to directly apply the GV bound. However, there is a generalization of the GV bound stating that the cardinality of an optimal code in $S$ is lower-bounded by $$\frac{|S|}{\overline{B_n(d-1)}},$$ where $\overline{B_n(r)}$ is the average cardinality of a ball of radius $r$ in $S$. Now the problem is down to estimating the latter quantity, which in some cases can be done exactly (see for example the works citing the above-mentioned paper by Gu and Fuja, some of them quite recent).

Note: To maximize the code size, you may want to take for $S$ the largest possible set of diameter $D$ (i.e., a maximal anticode), which is a ball of radius $D/2$ for even $D$, or a union of two balls of radius $\lfloor D/2 \rfloor$ centered at neighboring points for odd $D$. In this case, assuming for simplicity that $D$ is even, you would have $$|S|=\sum_{t=0}^{D/2} \binom{n}{t}.$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .