3
$\begingroup$

I posted this question in https://math.stackexchange.com/questions/1142698/picking-codewords-that-are-close a week back.

Let $[n,k,d]$ be a linear code over $\Bbb F_q$ with minimum distance $d$ and number of minimum weight codewords $N_d$.

How many ways can you select codewords $c_1,\dots,c_T$ (assume $T\ll q^k$) such that there are two non-equal codewords in collection at a distance $d$ from each other ($c_i\neq c_j$, $|c_i-c_j|=d$)?

Presumably answer is $2^{\lambda T}$. If so what is correct estimate to $\lambda$?

Atleast could we say something when code is MDS (cases where weight enumerators known).

$\endgroup$

2 Answers 2

1
$\begingroup$

Edited:

@Turbo: You're right. I was assuming that the two codewords must be nonzero. In general, when one codeword is zero, one gets a weaker lower bound of the form $N_d {q^k \choose T}$ and the rest of the argument follows with a linear $N_d$ instead of a quadratic factor $N_d^2/2.$

A special case (original answer):

In the specific case of a binary linear code $C$ the nonzero values of the weight distribution coefficients $A_w=\#\{c \in C:wt(c)=w \}$ are $A_0=1,A_d=N_d,\ldots$. Now assume the code contains the all $1$ vector as a codeword. Then $A_{n-d}$ is also nonzero and $A_{n-d}\geq A_d=N_d$ since the sums (or differences) $(1,1,\ldots,1)+c$ are also codewords in $C.$

Thus there are at least $N_d(N_d-1)/2$ pairs $c_i,c_j$ in $C$ which satisfy $|c_i-c_j|=d$. For each one of these pairs, you can select the remaining $T-2$ codewords (assumed distinct) arbitrarily provided $T-2 \leq 2^k.$ So you have approximately

$$ (N_d^2/2) {2^k \choose T} \qquad (1)$$

which should be at least $O(2^k)$ provided $T$ is small enough compared to $2^k.$ Of course, if the code is also cyclic, then $N_d \geq n$ and this helps extend the validity regime of the lower bound. i seem to recall there are some sporadic linear codes with $N_d=3,$ and $n$ long, but can't think of the reference right now.

If you're interested in asymptotics, quite a few linear codes have weight distribution that is "asymptotically normal". This means that $$A_i/2^k \approx 2^{-n} {n \choose d}$$ and this should help refine the estimate in (1) above when you let $i=d$. See Chapter 9, especially section 10 of McWilliams and Sloane for more.

There should be obvious generalizations of this argument to nonbinary characteristic, such as assuming any Hamming weight $n$ codeword belongs to $C.$

$\endgroup$
4
  • $\begingroup$ So basically stackexchange could have answered this. Number of ways to choose $T$ codewords is $q^{kT}$. Number of ways to choose $T$ codewords so that atleast two of them are $d$ dist away is $f(d)q^{k(T-2)}$ where $f(d)$ is atleast quadratic in $N_d$. So $\lambda\approx k\log_2q$. $\endgroup$
    – Turbo
    Commented Feb 20, 2015 at 1:36
  • $\begingroup$ @Turbo: only in the special case I answered can you make this argument. $\endgroup$
    – kodlu
    Commented Feb 20, 2015 at 5:43
  • $\begingroup$ I do not understand. Your answer seems to work for general $q$? $\endgroup$
    – Turbo
    Commented Feb 20, 2015 at 5:55
  • $\begingroup$ ..upto some quadratic factors. $\endgroup$
    – Turbo
    Commented Feb 20, 2015 at 6:02
1
$\begingroup$

Number of ways to choose $T$ codewords is $q^{kT}$. Number of ways to choose $T$ codewords so that atleast two of them are $d$ dist away is $f(d)q^{k(T-2)}$ where $f(d)$ is atleast quadratic in $N_d$. So $\lambda\approx k\log_2q$.

$\endgroup$

You must log in to answer this question.

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