Let $V$ be a vector space over $F$, where $\dim(V) = n$. Then $|V| = |F|^{n}$. This is intuitive for me in abstract settings. Consider the standard basis for $V$, $\{e_1,e_2,...,e_n\}$. There are $n$ non-zero entries, and $|F|$ possible elements for each entry, so $|V| = |F|^{n}$.

I'm currently taking a coding theory course. Let $C$ be a $q$-ary linear code over $F$ (in other words $|F| = q$,) with dimension $k$ and length $n$. $C$ has a generator matrix $G = \begin{bmatrix} c_{1}^{T} \\ c_{2}^{T} \\ \vdots \\ c_k^T \end{bmatrix} = \begin{bmatrix} c_{11} & c_{12} & \dots & c_{1n} \\ c_{21} & c_{22} & \dots & c_{2n} \\ \vdots \\ c_{k1} & c_{k2} & \dots & c_{kn} \\ \end{bmatrix}$ which of course has the additional structure $G = [I_{k}|A]$.

Now, $C \subseteq F^{n}$. (I mean by $F^{n}$ the $n$-tuples of elements of $F$, sorry if that's not standard notation) Clearly $|F^{n}| = |F|^{n} = q^{n}$. $C$ also consists of $n$-tuples of elements of $F$, but not necessarily all of them.

I guess my question is can I apply the standard basis intuition I used in the abstract setting to linear codes? i.e although $\{c_{1}^{T}, c_{2}^T, \dots, c_k^T\}$ is a basis for $C$, can I choose a basis of $k$ vectors by taking $e_1, \dots e_k$ and extending them with 0's until they have length $n$? Maybe this isn't the exact technique needed but my idea is to construct some basis where there are $k$ non zero entries, 1 in each of the basis vectors. I'm confused because I have a $k$ dimensional vector space whose elements are vectors of length $n$.

Let me know if anything isn't clear, and thank you!

Edit: it is a given result in my book that $|C| = q^{\dim(C)}$, so I "know" the result and this post is an effort to better understand it.


You asked : can I choose a basis of $k$ vectors by taking $e_1, \dots e_k$ and extending them with 0's until they have length $n$?

No, you should not just fill up the remaining $n-k$ components just by zeros. The whole idea of the linear code is to to use the first $k$ components in each vector to encode information and to fill up the remaining $n-k$ components with redundant information.

If during transmission one (or more components) of the transmitted vector changed its value (due to noise) the redundant part should be chosen so that you can you can easily guess the original vector - or at least diagnose that the received vector was not the one which had been sent.

If you would just choose the $n-k$ components to be always zero, then this would not result in a very smart usage of the redundant part. At least, when all $n-k$ should be always zero, and you would receive a vector having a non-zero in part where zeroes are expected, then you could conclude that some noise malformed the transmission.

| cite | improve this answer | |
  • $\begingroup$ So in a generator matrix $G = [I_k|A]$, $I_k$ should contain encoded information while $A$ provides redundancy for error detecting and correction? Interesting and seems quite important haha. I'm not taking this course in my native language so I think some things are slipping past me. But in analyzing the cardinality of $C$, the naive basis I constructed by filling the $n-k$ remaining components with 0's is still a valid basis for $C$, correct? Although it's perhaps not a useful one. $\endgroup$ – CFlaherty Apr 23 '19 at 13:32
  • $\begingroup$ Filling the $n-k$ components with $0$ is equivalent to having $A$ as $0$ matrix. In that way it fits in the framework you mentioned above. In this sense your question could be answered in an affirmative way. $\endgroup$ – Maksim Apr 23 '19 at 14:31

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.