Valid LDPC parity check matrices 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.
 A: 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).
