I am following the book Essential Coding Theory, by professor Madhu Sudan. It is freely available in the following link: https://cse.buffalo.edu/faculty/atri/courses/coding-theory/book/
In page 49, a comment in bracket puzzled me. It states the dimension of a binary linear code $C_{H,r}$ is
$$k = n – O(\log _2 n)$$
I do not understand why.
I tried to prove it using the following path:
By definition:
$$k = \log _q |C|$$
Since we have binary code, $q=2$. Then, to reach the desired equality above, linearity should allow me to reach the following equality:
$$|C| = \frac{2^n}{O(n)}$$
I fail to understand how linearity gives me this.
More directions:
- I know that for general codes, $|C| \le 2^n$.
- From linearity, I know that $C$ is the nullspace of $H$, where $H$ is the parity check matrix. Thus, $C = \{c \in \ \mathbb{F}_{q}^n | Hc = 0\}$. This means that $|C| = dim(\text{ker}(H))$. Considering Linear Algebra, I know that $dim(\text{V})=n$, and that $dim(\text{ker}(H)) = dim(V) – dim(\text{im}(H))$. But what is $\text{im}(H)$ ? And how does this direction lead me into something with $\log_2 n$, or, alternatively, a ratio of the form $\frac{2^n}{O(n)}$?
Edit: Thank you for answering my question. Associating linear codes with linear spaces confused me because of the notational overhead from associating codewords with vectors (and codes with matrices).
Best Answer
It's simpler than you think.
In the Hamming code for word length $n=2^r - 1$ which has dimension $2^r - r -1= n -r$ just note that $r = O(\log_2(n))$ (by the definition of $\log_2$) so that indeed the dimension equals $n-r = n - O(\log_2(n))$ as claimed. Nothing fancy.