Xrfgtjtk

Note: We are talking about binary codes.

Definition 1: For integers $1 ≤ d ≤ n$, a code $C$ is an $(n, d)$-code if it has length $n$ and minimum distance $d_H (C) ≥ d$. An $(n, M, d)$-code is an $(n,d)$-code of size $M$.

Definition 2: For integers $1 ≤ d ≤ n$, let $A(n,d)$ be the largest $M$ such that there exists an $(n, M, d)$-code. An $(n, d)$-code is optimal if has size $A(n, d)$.

Prove that for any integer $n ≥ 2$ and $1 ≤ d ≤ n$, we have $$A(n, d) ≤ 2A(n − 1, d)$$.

What I did: It suffices to prove that given $C$, a $(n,d)$-code, we can find $C'$, a $(n-1,d)$-code, such that $|C| leq 2|C'|.$

Next what I think is that we have to truncate $C$ by deleting the last bit of every codeword. This will make $C'$ a code of length $n-1$ but doing so will affect the minimum distance as we might delete the bits where the two codes are distinct. Any Idea how to proceed?

Proof

Let $C$ be an $(n,d)$-code.

Let $n(0)$ and $n(1)$ denote the number of codewords in $C$ ending with $0$ and $1$, respectively.

We claim that either $n(0)$ or $n(1)$ $geq |C|/2.$

Proof of claim:

If either $n(0)$ or $n(1) = |C|/2$, we are done.

Assume $ n(1) < |C|/2$. We need to show $n(0)> |C|/2.$
$$|C|=n(0)+n(1)< n(0)+|C|/2.$$
So, $$n(0)> |C|/2.$$
This proves the claim.

Now, WOLG, assume $n(0) geq |C|/2.$

Consider $C^* subset C $ containing only codes ending with $0$, i.e, we have $|C^*|=n(0).$

Define $C'$ to be a code obtained by deleting the last bit of codewords in $C^*$.

Note that $d_H(C')=d_H(C) geq d$, $C'$ is a code of lenght $n-1$, and $|C'|=|C^*|$.

Moreover, from the claim, $$|C'|=|C^*|=n(0) geq |C|/2.$$

This proves that given any $C$, a $(n,d)$-code, we can find $C'$, a $(n-1,d)$-code such that $$|C| leq 2|C'|.$$

Hence, for $n geq 2$, and $1leq d leq n$, $$A(n,d)≤2A(n−1,d).$$