1
$\begingroup$

I have found many different methods for generating a parity check matrix for LDPC codes and I have implemented some of them (e.g. the original Gallager ensemble, this method and some more).

I have found, that all of them share one problem: The resulting matrix is not always a valid parity check matrix.

As an example, this is a matrix I got from the Gallager ensemble (just a small example, chose bad values for the algorithm): $$\begin{pmatrix}1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0\\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1\\ 0 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 1 & 0\\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1\\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0\\ 0 & 0 & 1 & 0 & 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}$$ This matrix got generated through the Gallager ensemble, obviously. But it also is not a valid parity check matrix, because it can't be turned into an equivalent systematic LDPC code matrix, i.e. the determinant of its "right part" $$\begin{pmatrix}1 & 0 & 0 & 0 & 0 & 0\\ 0 & 1 & 1 & 1 & 1 & 1\\ 1 & 0 & 0 & 0 & 1 & 0\\ 0 & 1 & 1 & 1 & 0 & 1\\ 0 & 0 & 0 & 1 & 1 & 0\\ 1 & 1 & 1 & 0 & 0 & 1\end{pmatrix}$$ is equal to $0$.

My problem is, that actually most matrices I generate using these algorithms turn out to be invalid.

So, my question is, if there is a modification to all these generator algorithms to always return a valid parity check matrix or if I really have to do a while(invalid) {//generate another one} to always get a valid matrix.

$\endgroup$
5
  • 1
    $\begingroup$ Linear codes $C_1$ and $C_2$ are equivalent, if a generator matrix $G_1$ of $C_1$ can be turned into a generator matrix $G_2$ of $C_2$ by permuting the columns. Notice the indefinite article. The same applies to check matrices. By linear algebra any full rank check matrix has a full size non-zero determinant, but we don't necessarily know which set of columns that corresponds to. In coding theory language: there is no reason to assume that row operations would turn a given check matrix into a systematic check matrix. $\endgroup$
    – Jyrki Lahtonen
    Oct 31, 2020 at 4:42
  • $\begingroup$ In yet other words, there are no guarantees that the set of parity check bits would be at the end of the block. What's more, a matrix drawn from an ensemble described by combinatorial properties need not have full rank. When that happens one or more of the parity checks are redundant in the sense that they are linear combinations of others, and the code has higher than predicted rank. $\endgroup$
    – Jyrki Lahtonen
    Oct 31, 2020 at 4:48
  • $\begingroup$ My somewhat limited experience in actually using LDPC codes suggests that it is usually not practical to manipulate the check matrix into a form where that identity block shows up. The reason is that doing that typically destroys the low density. For example in the LDPC codes used DVB standard (=digit video broadcast) there is a staircase block there instead of identity matrix. That way encoding becomes more efficient when each row of a 43200 x 64800 matrix has, say, approximately twelve bits set instead of a random amount. $\endgroup$
    – Jyrki Lahtonen
    Oct 31, 2020 at 4:56
  • $\begingroup$ In other words, I doubt the wisdom of finding that identity block in the first place. Just analyze it enough to determine a set of information positions, and then fill in the check bits any which way you can. $\endgroup$
    – Jyrki Lahtonen
    Oct 31, 2020 at 4:58
  • $\begingroup$ In some paper, they recommended using the procedure with applying row operations to get the identity matrix and so on. In this answer on stackoverflow: stackoverflow.com/questions/43887951/… they are using an equivalent procedure. However, both don't work as long as the matrix doesn't have full rank (many if not most matrices that the Gallager ensemble and the other algorithms produce don't have full rank). So, what should I do about that? $\endgroup$
    – ThexXTURBOXx
    Nov 1, 2020 at 10:35

1 Answer 1

Reset to default
1
$\begingroup$

I'm not an expert on this, so please take everything I say with an adequate amount of salt. I do have a little of practical experience implementing LDPC-codes (from a very limited family), so I will share my impressions and an example from my lecture notes introducing these ideas at the end of a course (the course is concentrating on convolutional codes, and this is just an addition for a bit of extras).

A practical $(n,k)$ LDPC-code has largish parameters. The length $n$ and the rank $k$ are typically in thousands, as is the number $r=n-k$ of check bits. This means that it may not be prudent to store that huge check matrix anywhere, let alone multiply input vectors with it. This is the case in particular, when the elementary row operations required to bring it into a row echelon form (possibly with the echelon at the right end) will destroy the low density-property. You really don't want to use check equations (or rows of a generator matrix) with the expected number $\approx k/2$ bits defining a single check bit instead of, say $12$, bits as would be the case in the low density version.

Instead, you can record procedures for generating the check bits using a low density parity check equation. Consider the following check matrix $$ H=\left(\begin{array}{cccccccccc} 1&1&1&1&0&0&0&0&0&0\\ 1&0&0&0&1&1&1&0&0&0\\ 0&1&0&0&1&0&0&1&1&0\\ 0&0&1&0&0&1&0&1&0&1\\ 0&0&0&1&0&0&1&0&1&1 \end{array}\right). $$ This is highly symmetric in that all the columns have weight two, and all the ten possibilities appear as columns. Observe that the rank of this matrix is four, so it fits into your other concern of having a check matrix that is not full rank. More precisely, the last row is the sum of the other four. By design, as all the columns have weight two!

Anyway, only the top four rows are relevant for the purposes of encoding (the last check equation can still be used in Belief Propagation decoding, but that is a separate decision). You see that they have the useful property that the last $1$s on the four top rows fall on distinct columns. This is all we need! We can declare that the positions of those last bits of checks, here the positions $4$, $7$, $9$ and $10$ are the check bits, but the other six positions are payload. Of course, it is trivial to shuffle the columns in such a way that the check positions move to the right end.

The encoding procedure is then trivial. Simply flood the remaining positions (here $1,2,3,5,6,8$) with the information bits. Then run a single iteration of belief propagation to fill in the check positions: the first check calculates position $4$, the second will fill position $7$ et cetera. Observe that only original parity checks are needed to do this as long as we arranged them to have distinct "last participating symbols". This toy example hides some aspects:

  • $4$ out of $10$ is not truly "low density", but hopefully you see the idea
  • Above matrix was exceptional in that the other bits participating in the top four equations where ALL payload bits, and a single iteration of belief propagation was sufficient. It is possible (read very likely) that with large parameters $(n,k)$ THIS IS NOT THE CASE. You absolutely don't want to run belief propagation here in those cases. But, if each row of the check matrix has a fixed small number, say $w$, $1$s, then you simply calculate the check bit as a sum of $w-1$ earlier bits, some of which are likely to be check bits themselves.
  • To make this clear: You need to XOR $w-1$ bits for each of the check bits for a total of $(w-1)r$ operations. Observe that by design $w\ll k$. If you manipulated the check matrix to have that identity block at the end, then you would get check equations with a "random number" of bits participating, and consequently using the check matrix (or the generator matrix) in the usual way would require a random number of operations ($\approx (k/2)$) per check bit instead of $w-1$.

Still, in a practical system the number of information bits is given to you as a system constant. To get full rank matrices from a given ensemble some extra structure is often imposed.

  • the check matrices defining the LDPC-codes in 2nd generation standard for DVB impose a staircase structure in the check bit area, as well as a cyclically repeating structure elsewhere
  • IIRC the LDPC-codes in the MediaFlo standard use a structure with circulant blocks with a single $1$ per row within a block.

In both cases the extra properties imposed on the check matrices make it possible to control the full rank property as well as the related Tanner graph. That last property is important in practical systems. Your hardware engineers will be pulling their hair, if you want them to implement a totally random Tanner graph on hardware. The routing of all those messages in the Belief Propagation becomes then very complicated. Cyclically repeating structures simplify that, and enable parallelism in the hardware (many messages running in parallel without disturbing each other).

$\endgroup$
2
  • $\begingroup$ The same concern appears elsewhere when using long blocks. Wtith a convolutional code you use the convolutional encode instead of a generator matrix to produce the coded bits with a small number of operatios per bit. If you use a long cyclic code, you use the generator matrix rather than a generator matrix to same end. $\endgroup$
    – Jyrki Lahtonen
    Nov 4, 2020 at 14:36
  • $\begingroup$ Thank you for your very elaborated answer! I think, most of my questions have been answered here then. However, I do have one more: If I take this matrix (I know, it is very small, but I could find a bigger one easily), then I can't encode 101 for example, because of a contradiction in row 2 and 3. Do you by chance know a way to "detect" such contradictions easily? $\endgroup$
    – ThexXTURBOXx
    Nov 8, 2020 at 21:08

You must log in to answer this question.

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