do linear block code codewords need to contain the original k bits?

228 Views Asked by At

In standard form, the Generator matrix of a linear block code will contain the Identity matrix. However, the generator matrix need not be in standard form. However, is it the case that k of the n codeword bits will be the original k message bits? That is to say, will it always be the case that there will be k different columns in the Generator matrix with a single 1 in them?

In particular I'm interested in Golay codes, but a more general statement would also be helpful.

My guess is "no", because you could in theory just take a Golay code in standard form, flip every bit in every codeword and have an equivalent code, but I'm not sure if my reasoning is faulty here

Possibly related: Can all linear code be adapted so that the first bits of the encoded message are the bits from the original message?

1

There are 1 best solutions below

2
On BEST ANSWER

Well, actually you kind-of answered the question yourself. However, your two questions are not equivalent. Your first question: "Is it the case that $k$ of the $n$ codeword bits will be the original $k$ message bits?" is not equivalent to your second question "Will it always be the case that there will be k different columns in the Generator matrix with a single 1 in them?" The answer to both questions is no.

For the first one, pick my stupid code with generator matrix $\left[\begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}\right]$ and data $\left[\begin{array}{cc} 1 \\ 1 \end{array}\right]^T$ to get the codeword $\left[\begin{array}{cc} 1 \\ 1 \end{array}\right]^T\left[\begin{array}{cc} 1 & 1 \\ 0 & 1 \end{array}\right] = \left[\begin{array}{cc} 1 \\ 0 \end{array}\right]^T$. This vector does not contain all the entries of your data you wish to transmit.

I guess you know the answer to your second question. A code does not have to be in its standard form "to work."

So why does all of the codes that we are interested in can be put into the standard form? As otherwise, $G$ would contain a $0$-row, which means you are not encoding one of your data bits (obviously this does not make sense, you may then improve your coding rate by throwing out that bit without sacrificing performance).

Another relevant question is why would want to use the non-standard form of a generator matrix. The reason is that sometimes encoding using the non-standard form of the generator matrix may result in a better performance if your decoding algorithm is non-maximum-likelihood.