Is there an example of a code which is maximal but not optimal?


An $(n,M,d)$ code $C$ over $\mathbb{F}_q$ is maximal if $C$ is not contained in an $(n,M+1,d)$ code.

An $(n,M,d)$ code $C$ is optimal if $|C|=M=A_q(n,d)$, where $A_q(n,d)=\max \{M\mid\exists (n,M,d)\text{ code}\}$.

I know that each optimal code is maximal, but I do not really understand the difference between the two definitions.

Thank you for help,

Best regards


One way of attempting to get an optimal code $\mathcal C$ is to begin with $\mathcal C$ consisting of $\mathbf 0 \in \mathbb F_q^n$ , and then iteratively include in $\mathcal C$ an element of $\mathbb F_q^n-\mathcal C$ that is at distance $d$ or more from all of the already chosen codewords in $\mathcal C$. Note that beginning with $\mathcal C = \{\mathbf 0\}$ is not required; we could begin with any other element of $\mathbb F_q^n$ if we wish without affecting the results.

A maximal but non-optimal code $\mathcal C$ is defined to be the result achieved when $|\mathcal C| < A_q(n,d)$ but $\mathcal C$ cannot be enlarged any further in this manner -- that is, all the elements of $\mathbb F_q^n - \mathcal C$ are at distance smaller than $d$ from one or more of the codewords already chosen to be in $\mathcal C$. Note that the $\mathcal C$ that we have found is not a proper subset of a larger code with the same minimum distance $d$. If we want to arrive at an optimal code, we are blocked in this direction; and need to backtrack, that is, replace some of the previously chosen codewords for $\mathcal C$ by other choices that are also at distance $d$ or more from the codewords in $\mathcal C$ and then explore other subsets of $\mathbb F_q^n$ to find a code of cardinality $A_q(n,d)$.

If the value of $A_q(n,d)$ is known exactly, we can stop the search-and-include-and- backtrack-when-stuck process as soon as we find a $\mathcal C$ with $A_q(n,d)$ codewords in it, and this will be an optimal code, which, as you point out, is also maximal.

As an example, consider that with $q=2$, $n=3$, $d=2$, if we include codewords in $\mathcal C$ in order $000,~ 011, 101,~ 110$, we get an optimal code but had we begun with $000$ and then picked $111$ as our second choice, we would end up with the maximal but non-optimal code $\{000, 111\}$, all dressed up and nowhere to go, as the atheist's tombstone said.

  • 2
    $\begingroup$ Good example at the end there :) It is kind of like a packing problem. If you pack suboptimally, you are leaving extra gaps between items and eventually you might not be able to fit the maximal number of items in. Just like my recycling bin this morning... $\endgroup$ – rschwieb Jul 8 '13 at 20:23

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.