Column operations in LDPC generator matrix I'm trying to produce a generator matrix from a starting low density parity check matrix. There are lots of references on the topic (including this Signal Processing Stack Overflow answer here). They make sense, with the exception of one problem I'm having.

My resource is the book Error Correction Coding: Mathematical Methods and Algorithms by Todd K. Moon. In it, there is a section that describes this that I will replicate below, and then highlight the part I'm stuck on.


  For a code specified by a parity check matrix $A$, it is expedient for encoding purposes
  to determine the corresponding generator matrix $G$. A systematic generator matrix may
  be found as follows. Using Gaussian elimination with column pivoting as necessary (with
  binary arithmetic) determine an $M$ x $M$ matrix $A^{-1}$ so that
  
  $$H = A_p^{-1} A = [I \quad A_2].$$
  
  (If such a matrix $A$, does not exist, then $A$ is rank deficient, $r = \mathrm{rank}(A) &lt; M$. In this
  case, form $H$ by truncating the linearly dependent rows from $A_p^{-1} A$. The corresponding
  code has $R = K/N &gt; (N - M)/N$, so it is a higher rate code than the dimensions of $A$
  would suggest.) Having found $H$, form
  
  $$G=\begin{bmatrix}A_2 \\ I\end{bmatrix}.$$
  
  Then $H G = 0$, so $A_p H G = A G = 0$, so $G$ is a generator matrix for $A$. While $A$ may be
  sparse (as discussed below), neither the systematic generator $G$ nor $H$ is necessarily sparse. 


Here's the problem I'm running into:
I start with $A$ and do Gauss-Jordan elimination in $\mathbb{G_2}$ to get it into reduced row echelon form.

Sometimes the matrix I've been given (I'm not designing it, have to use what I'm given) can't be put into that form with solely row operations.

It requires actually swapping the order of some columns (is that what he means by "column-pivoting" in the reference above?). Everything in me screams that's wrong, but it turns out if I just do the same thing on the decoding side it works out.

But then I'm left with the conundrum that when I go to decode something encoded with this parity check matrix I have to know how the matrix columns were reordered on the transmit side.

Basically I have to re-do the generator matrix, which is by far the slowest part of my process (I'm going to make some improvements there though, using the QC-LDPC structure of the parity matrix).

It seems bizarre to me that a designed system would put in a parity check matrix that requires column reordering to work.

Is there something I'm missing? For what it's worth I also have the example matlab code from the aforementioned book and this is what he does (column reordering and then re-applying that re-orderying on the decode side).
Everything in me screams that's wrong, but it turns out if I just do the same thing on the decoding side it works out.


Why? That just means you reorder some bits. On the other end, when you revert that reordering, that's an operation that changes nothing about the code itself.

In fact, your system almost certainly has an interleaver, anyway, so you such reordering operations are absolutely integral to how it works!


  the conundrum that when I go to decode something encoded with this parity check matrix I have to know how the matrix columns were reordered on the transmit side.


What's surprising about that? Your receiver needs to have a decoder matching the encoder.

Don't forget that swapping columns is just a permutation matrix that you apply your data. Done!


  It seems bizarre to me that a designed system would put in a parity check matrix that requires column reordering to work.


Why? You say that, but you don't argue based on anything about that. In fact, many coding-theory proofs are based on random codes...

Again, imagine your reordering operations as permutation matrices that you just use after / before applying the parity check / generator matrix.