[Math] Get code words from generator matrix

coding-theorymatrices

I have some issue regarding the generator matrix. Please can some body can explain me "How to get Codebook from Generator matrix?"

Following is my issue

Generator matrix has 3 code words.
Then codebook should has 8 code words.

So for the codebook I already have 4 code words. (All zero vector and 3 vectors in G)

I can get another 3 by adding (1+2),(1+3), (2+3)

So now I have all together 7 code words.

How to get the Last???

Best Answer

So let's say your generator matrix is $G$, which you described as having three codewords (we'll say as rows) $c_1,c_2,c_3$ from top to bottom.

This thing is called the generator matrix because it produces every codeword as a result of multiplication by some vector in $\Bbb F_2^3$ on the left, like this: $xG=c$.

So, what are the possible inputs? From the context, I gather you are working over $\Bbb F_2$. So, the possible inputs are: $[0,0,0], [1,0,0], [0,1,0], [0,0,1],[1,1,0],[1,0,1],[0,1,1],[1,1,1]$.

The first seven correspond to words you already listed: $0, c_1,c_2,c_3,c_1+c_2,c_1+c_3,c_2+c_3$ in that order.

The codeword you were missing corresponds to the last one: $c_1+c_2+c_3$!


In general, if you have a code over $\Bbb F_2$ and a $k\times n$ generator matrix (that is, $k\leq n$, $n$ is the length of the code and $k$ is the dimension.) then all of the codewords will be given by multiplying by the vectors from $\Bbb F_2^k$. Since there are $2^k$ of these vectors, there will be $2^k$ codewords.

If instead you are over a larger finite field like $\Bbb F_q$, then the number of codewords will be $q^k$. Can you see why?