I'm struggling with a problem that I'm kinda lost. Here it is:
A binary code $C$ with length $6$ is constructed as follows: for each tuple $(x_1,x_2,x_3)\in {\mathbb F}_2^3$ the code contains the word $(x_1, x_2, x_3, x_4, x_5, x_6) \in C$, where $x_4 = (x_1 + x_2 + x_3)$; $x_5 = (x_1 + x_3)$; $x_6 = (x_2 + x_3)$
a) Prove that $C$ is a linear code;
b) Find the parameters of $C$;
c) Find the generator and correction matrices for $C$
So as I generate my code C, I see, that it contains the words
000000
001111
010101
011010
100110
101001
110011
111100
which means, that the $C$ code in the $(n,M,d)$ form would have parameters $(6,8,3)$ (point b);
If I understand correctly in order to prove that the code is linear, I need to prove, that the sum or subtraction of any two words is also a word, which I think would be done by stating, that the first three bits are all possible binary permutations and any mod2 sum or subtraction of any of them is also a binary 3-bit long permutation and since the other 3 bits are functions of the first 3 bits, the sum/subtraction of any two words would result in a word. Therefore it's a linear code.
Now, $c.$ is where I bang my head against the wall all day long – I know that the generator matrix $G $is defined as follows: $G$ is a matrix $n \times m$, where n is the length of the words; $G=[I|P]$, where $I$ is an identity matrix of size $n$; $P$ is a a matrix that allows any given row to be linearly independent from any other. How do I do that? If I figure this out, I know how to generate my corrective matrix $H = [-P^t|I]$, but I need to find $P$ first.
Thanks in advance for all your help!
P.S. Didn't find how to format the field parameters inline here and one needs higher rating to embed a picture, so just adding a link instead – sorry.
Best Answer
I think you are confusing the parameters $k$ (length of raw messages) and $M$ (how many messages = how many codewords), which are related by $M=2^k$. Here $M=8$, $k=3$.
Now, the matrix $G$ allows to generate the codewords as $ v^{1\times n} = u^{1\times k} \, G^{k\times n}$, (I'm denoting the sizes as superscripts). Then $G$ have $k$ rows (not $M$ ), each of size $n$.
The recommended way of thinking of the rows $G$ is as a basis of the codebook. All codevectors $v$ are a linear combination of those rows. If you are given the codebook with the original messages, then to find $G$ you simply look for the "canonical" inputs $u_1=(1,0, \cdots 0)$ $u_2=(0, 1, \cdots 0) \cdots$ , the resulting codewords msut be the rows of $G$.
If instead, you are given the equations (as here) it's more easy to build it by hand. Given that you evidently have done your effort, I'll write that for you:
$$(x_1, x_2, x_3, x_4, x_5, x_6) = \pmatrix{ 1 & 0 & 0 & 1 & 1 & \times\\ 0 & 1 & 0 & 1 & 0 & \times\\ 0 & 0 & 1 & 1 & 1 & \times } (x_1, x_2, x_3, x_4) $$
I left the last column for you. Check, by evaluating the matrix product, that the codeword elements are ok, and find the last column (using the equation for $x_6$)
BTW: $G$ has the form $[I|P]$ only when the code is systematic - which is the case here, but not always.