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
    Feb 20, 2015 at 1:36
  • $\begingroup$ @Turbo: only in the special case I answered can you make this argument. $\endgroup$
    – kodlu
    Feb 20, 2015 at 5:43
  • $\begingroup$ I do not understand. Your answer seems to work for general $q$? $\endgroup$
    – Turbo
    Feb 20, 2015 at 5:55
  • $\begingroup$ ..upto some quadratic factors. $\endgroup$
    – Turbo
    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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.