2
$\begingroup$

I'm new to stackoverflow so please bear with me. A tutorial question I got given was as follows:

You are given that $C \subseteq D \subseteq F^n_q$ where $|C| < |D|$ and $C$ is a perfect code. Show that $d(C) > 2d(D)$.

I have been using the fact that $C$ is a perfect code so it attains the Hamming bound then saying that it is less than the Hamming bound for $D$, but you get an inequality involving a binomial sum on both sides, which is really messy. I'm not really sure what other properties I can use to work this out. Any help would be really appreciated, thanks

|cite|improve this question
$\endgroup$
  • $\begingroup$ What function is $d$? $\endgroup$ – G. Bach Nov 6 '15 at 13:55
  • $\begingroup$ @G.Bach Minimal distance. $\endgroup$ – Yuval Filmus Nov 6 '15 at 14:02
  • 1
    $\begingroup$ Start with the definition of $C$. It practically states that this property holds. $\endgroup$ – Ran G. Nov 6 '15 at 14:07
  • $\begingroup$ @RanG. how? using the fact that $C$ is perfect? $\endgroup$ – shex95 Nov 6 '15 at 14:54
  • 2
    $\begingroup$ Yes. Maybe add to the question the definition of "perfect code" you are using (I saw several equivalent definitions; one of them was actually almost the statement of your question verbatim). $\endgroup$ – Ran G. Nov 6 '15 at 16:16
3
$\begingroup$

Guidelines for the future: start with reviewing the definitions.

According to Wolfram, a perfect code (with distance $d=2e+1$) is one such that "for every possible word $w_0$ of length $n$ with letters in $A$, there is a unique code word $w$ in $C$ in which at most $e$ letters of $w$ differ from the corresponding letters of $w_0$."

OK, but this is cheating.

So let's start with an equivalent definition:

A code $C$ is perfect if it attains the Hamming bound

what is this Hamming bound? Basically, it's a counting argument. If you have a word $w\in F^n_q$, how many words are there with in $F^n_q$ whose distance from $w$ is at most $e$? If you do the counting, you will get there are exactly $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ such words. [Why? If the distance is $i$, choose $i$ indices (out of the $n$ possible indices), each such index can get any of the $q-1$ different values from $w$ in that index.] The bound then says that if we split the universe into disjoint "balls" where each ball contains a center $w$ and all the $\sum_{i=0}^e \binom{n}{i} (q-1)^i$ words within distance $e$ from $w$, we will have at most $$\frac{|F^n_q|}{size(ball)} = \frac{q^n}{\sum_{i=0}^e \binom{n}{i} (q-1)^i}$$ such (disjoint) balls.

A code that attains the Hamming bound means that any word is within distance $e$ of some codeword. That is, if you think on each codeword in $C$ as a center of a ball with radius $e$, then the codewords cover the entire universe: no word in $F^n_q$ is left outside some ball. Note that the distance of this code is $2e+1$: two codewords belong to two different "balls", and each ball is of radius $e$ (in Hamming distance).

But if the entire space is covered with balls, it means that any word is within distance $e$ of some codeword. This is exactly the first definition I wrote in this post. Thus, if you take any other word and make it a codeword, this word already belongs to some ball, so it is within distance $e$ from the center of that ball, and the new code cannot have a minimal distance greater than $e$.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ thank you Ran G, youve made that very clear, i appreciate everyones help !! $\endgroup$ – shex95 Nov 7 '15 at 8:18
  • 1
    $\begingroup$ @shex95, if this answer solved your problem, you can click the "checkmark" / "tick mark" to the left of the answer to mark it as the accepted answer to your question -- that's the best way to thank the answerer. $\endgroup$ – D.W.♦ Nov 8 '15 at 4:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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