Dimension and cardinality of vector spaces in Coding Theory

296 Views Asked by At

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.

1

There are 1 best solutions below

2
On

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.