0
$\begingroup$

Given a linear code C with generator matrix G and parity matrix H. Would permuting rows and/or columns of these matricies produce a different linear code? I am under the impression that the resulting linear code would be equivalent to the original linear code. However when using Sage Maths, the set of codewords generated by the generator matrix seem to be different. Could anyone explain what is going?

$\endgroup$

2 Answers 2

1
$\begingroup$

Some of this is going to depend on what definitions you are using. Hill, A First Course in Coding Theory, page 49, says a generator matrix for a linear code is a matrix whose rows form a basis for the code. With that definition, if you permute the rows of a generator matrix, you do not affect the code, but if you permute the columns then in general you will get a different code.

But you also use the word, "equivalent," in your question. Two codes can be different, but still be equivalent. Indeed, on the next page of Hill, Theorem 5.4 asserts that whether you permute the rows or the columns, you still get an equivalent code.

$\endgroup$
4
  • $\begingroup$ How do you define equivalent? When i permute the rows, I get the same set of codewords, however if i permute the columns, I get very different sets of codewords $\endgroup$
    – MarkE
    Mar 5, 2016 at 23:34
  • $\begingroup$ Hill says "two linear codes over GF$(q)$ are called equivalent if one can be obtained from the other by a combination of operations of the following types: (A) permutation of the positions of the code; (B) multiplication of the symbols appearing in a fixed position by a non-zero scalar." $\endgroup$ Mar 5, 2016 at 23:41
  • $\begingroup$ In order to obtain a parity check matrix from a generator, it is required to first put the generator in the standard form [I _k | P], then it follows the parity check matrix is [-P^T | I_n-k]. Should the conversion to standard form be done using purely row operations to preserve the code? Would column operations lead to an incorrect parity check matrix? $\endgroup$
    – MarkE
    Mar 6, 2016 at 0:06
  • $\begingroup$ Column operations would (in general) lead to a different code. A parity check matrix for one code can't be a parity check matrix for a different code, can it? But if you have more questions, you should post them as questions, not as comments on an answer. $\endgroup$ Mar 6, 2016 at 0:10
0
$\begingroup$

Consider the (rather silly) generator matrix $G=\pmatrix{ 1 &0 &0 \\ 0 & 1 & 0}$. This corresponds to a $(3,2)$ linear code, which has 4 codewords of length 3. These codewords correspond to all the posible 2-binary tuples, plus a trailing zero.

If you permute the rows (or, also, make a linear combination), the resulting code is the same? Well, the mapping of raw inputs to codewords is not the same (in this same, it's not the same code), but the set of codewords (the codebook) is the same (in this sense, it's the same code: usually these are called "equivalent" codes).

What if you permute the columnsof $G$? This reflects on a permutation of the bits positions in the codewords. So the codebooks are different, and the codes are not "equivalent". However, many properties of the code (eg, distance) are the same, the permutation is like a relabelling of the coordinates axis. For a channel without memory (the time index does not matter), the codes could still be consider equivalent. In general, they are not considered equivalent. (For example, column permutation would not preserve cyclically; and burst errors detection would be altered)

$\endgroup$
2
  • $\begingroup$ According to the definition given in the Hill textbook, as quoted in a comment on my answer, permuting the columns does yield an equivalent code. But I'm not up-to-date on these things, and perhaps Hill's is a minority opinion. $\endgroup$ Mar 6, 2016 at 21:49
  • $\begingroup$ Thanks for the explanation! From what you say, does this imply that not all Codes / codebooks have a standard form generator matrix? i.e. a matrix [I_k | P] where I_k is the k-by-k identity matrix $\endgroup$
    – MarkE
    Mar 6, 2016 at 22:48

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .