Can somebody please explain to me how the generator matrix is obtained when we are given the codewords of the binary code in the examples attached.
I tried arranging the codes in a matrix with each row being a codeword , I then reduced to row echelon form and hence found basis of the code. I then Tried to construct the generator matrix using the basis but it does not work out. Please help!
Best Answer
Given a set $\mathcal{C}$ of codewords, before we can construct a generator matrix, we need to verify that $\mathcal{C}$ is a linear subspace - ie, the sum (and also scalar multiples in the non-binary case) of any two codewords must be a codeword. In the link given, the subsets $\mathcal{C}$ given are all subspaces. The rows of the generator matrix $G$ can be taken to be any subset of $\mathcal{C}$ that forms a maximal linearly independent set. If $|\mathcal{C}|=8$, then $G$ would have 3 rows. In general, if $|C|=2^k$ for some $k$, then $\mathcal{C}$ is a $k$-dimensional subspace and has a basis consisting of $k$ vectors. So $G$ would have $k$ rows.
A simple algorithm that picks codewords from $\mathcal{C}$ to form the $k$ rows of $G$ is as follows. Take the first nonzero codeword in $\mathcal{C}$ and put it as the first row of $G$. For $i = 1, 2, \ldots, k-1$, after adding the $i$th row to $G$, remove from $\mathcal{C}$ all linear combinations of the first $i$ rows of $G$. This leaves a subset $\mathcal{C}_i \subseteq \mathcal{C}$ containing codewords outside the $i$-dimensional subspace spanned by the $i$ rows of $G$. Choose any vector from $\mathcal{C}_i$ for the $(i+1)$-th row of $G$.