How is a generator matrix built?

787 Views Asked by At

If I'm given a set of codewords (i.e. the codewords are known) and I know that the code is linear, how can I find the matrix $G$ of that code?

I believe that $G$ is defined as $$G = \left[ P_{k\times (n-k)} \ I_{k\times k}\right]$$

where $I$ is the identity matrix. But I don't know what $P$ is. I don't know how te calculate it either. In this site I've read that $P$ is built as a column of all $1$s, but I don't understand why.

So that's the question: how can one find a generator matrix $G$ given the codewords?

1

There are 1 best solutions below

8
On BEST ANSWER

$P_{k\times(n-k)}$ is the parity check matrix for the code.

In this site I've read that $P$ is built as a column of all $1$s, but I don't understand why.

It is not always a column of $1$'s, it just is for that particular code because the parity check matrix makes sure that the sum of all the digits in the codeword are $0$.

So, if you know your parity check matrix, this is an easy way to construct a generator matrix. (It should also be noted that this formula is written for codes for finite fields of characteristic $2$. You need a negative sign in front of $P$ to make it work for all finite fields.)

So that's the question: how can one find a generator matrix $G$ given the codewords?

If you have your codewords in hand, then there is no reason to go through the formula above. You can just search your codewords for a set of $k$ linearly independent codewords, where $k$ is the dimension of your code. You can use these as the rows (or columns, depending on your choice of representation) of a generator matrix.