0
$\begingroup$

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) < M$. In this case, form $H$ by truncating the linearly dependent rows from $A_p^{-1} A$. The corresponding code has $R = K/N > (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).

$\endgroup$
1
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! I guess I was just hoping to be sure that I'm interpreting the process correctly. Just to respond to one of your comments, indeed there is interleaving and it's no problem to re-order bits. The issue is that the interleaver has a low cost, known equation. In this instance I need to know how the given parity check matrix must be re-ordered in order to decode. That seems pretty inefficient, given that the relationship isn't known a priori like with interleaving. Perhaps I can create a LUT or use memoization though. $\endgroup$ – Eric C. Feb 16 at 5:03
  • 1
    $\begingroup$ @EricC. $HG = 0 \iff A_p H G=AG=0$, both $H$ and $A$ are the parity check matrix of $G$. Just use your original parity check matrix. $\endgroup$ – AlexTP Feb 16 at 7:27
  • $\begingroup$ @AlexTP nice argument using the syndrome. $\endgroup$ – Marcus Müller Feb 16 at 8:59
  • $\begingroup$ @AlexTP There's something I'm still confused on though. I'm under the impression I can't represent column reordering via a left-multiplied matrix. Can't that only be done by a matrix multiplied on the right? That means that I can't actually get the systematic form of $A$ by a left multiplied $A_p^{-1}$ matrix. Second, when I tried just using the original parity check matrix I couldn't decode, I had to reorder the columns like I did on the transmit side. Third, that's what his example code does as well. $\endgroup$ – Eric C. Feb 16 at 17:36
  • $\begingroup$ In general, it is true that column permutation cannot be done with left multiplication: you can see it by using block presentation. For your second point, use this matlab code to generate $G$ matrix: H = H.'; numInfBits = size(H,2) - size(H,1); Hgf = gf(H); H1 = Hgf(:,1:numInfBits); H2 = Hgf(:,numInfBits+1:end); Pgf = (H2\(-H1))'; P = double(Pgf.x); G = [eye(numInfBits), P]; G = G.'; If this code fails, simply your $H$ is not a PCM for systematic code. ... $\endgroup$ – AlexTP Feb 16 at 20:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.