LDPC Decoders
Iterative belief propagation over a sparse bipartite Tanner graph
Motivation
I recently remembered my undergrad information theory course — it’s one of my favourite courses I studied whilst at university, and I think back quite fondly on it now. It was a difficult course, and although I scored fairly well on the exam, I still feel like I didn’t quite get as firm a grasp on the material as I maybe could have. The field of information theory is absolutely littered with proofs and derivations that can mask the real insight behind the theory, as Grant from 3Blue1Brown shows in this fantastic video
This has motivated me to dive back into the field, and review my notes from a few years ago. I’d like to get some more insight, specifically, into low-density parity check (LDPC) codes and the algorithms used to decode such codes. To bring things alive, I’d also like to implement an LDPC decoder on some modern hardware. I’ve been meaning to mess around with the Qualcomm Hexagon DSP chip, so that’s what I’ll use.
Linear Block Codes
Lets start with what an LPDC code actually is, and what problem it tries to address.
An LDPC code is a type of error-correction channel code. These allow you to define codewords over a vocabulary to send over a noisy channel, over which errors are possible. A bitstream sent over such a channel is likely to accumulate errors, and so we need some way of adding redundancy to recover errors. The most famous ECC is the Hamming code, which is a type of linear block code. This means, they can be described by two matrices: the generator matrix $G$ and its associated parity check matrix $H$. For example, the Hamming (7, 4) code has:
!image.png
This code is defined over symbols of input length 4, and output codeword length 7, i.e., it adds 3 bits of redundancy. To get a codeword $\mathbf{c} \in [0,1]^7$ from an input symbol $\mathbf{x} \in [0,1]^4$ we simply do
\[\mathbf{c} = G^T\mathbf{x}\]The parity check matrix is more interesting. It satisfies the property,
\[H\mathbf{c}^T = \mathbf{0}\]so that every valid codeword produces the all-zero vector when acted on by the parity-check matrix. We will come back to this, as it ends up being a useful property for LDPC codes.
Inspecting the generator matrix for the Hamming (7, 4) code in a bit more detail, we can see that 4 of the 7 rows are just picking out bits of the codeword (these are rows 2, 4, 5 and 6). Whereas rows 0, 1 and 3 give us extra parity bits:
\[G^T\mathbf{x} = \begin{bmatrix} x_0 + x_1 + x_3 \\ x_0 + x_2 + x_3 \\ x_0 \\ x_1 + x_2 + x_3 \\ x_1 \\ x_2 \\ x_3 \end{bmatrix}\]and this is the source of structured redundancy.
At this point, it is useful to know whether this is a good code. A good channel code can detect and correct more errors. However, taking this to its limit means we could just add more redundancy (i.e., a repetition code), and so there is another factor to trade-off — the rate $R$ of the code.
The number of errors a code can detect/correct is determined by something called its hamming distance, which is just the number of bits that are different between two codewords.
Specifically, we care about the minimum hamming distance $d_{min}$.
\[d_{min} = \min_{\mathbf{c}_i\neq\mathbf{c}_j} d_H(\mathbf{c}_i, \mathbf{c}_j)\]The maximum number of errors a code can detect is exactly $d_{min} - 1$. This should be intuitive: once we have a codeword with $d_{min}$ errors in it, it is entirely possible for it to have turned into another codeword. Note that it is not necessarily the case, i.e., it may well turn into something that is not a valid codeword in our vocabulary, but we cannot make strong guarantees about this.
Correction is harder. In order to correct a codeword, the number of errors must be small enough that it cannot be confused for any other codeword. This may seem like the same thing as detection, but consider a code with $d_{min} = 3$. Here, if there are 2 errors, we will know about it, since the received bits cannot be a valid codeword (say 1001). However, this could have been produced by two separate original codewords, e.g., (0101 → 1001 or 1010 → 1001). These are equally likely, and thus it becomes impossible to identify a unique decoding. In general, the maximum number of errors we can correct is roughly half the number we can detect:
\[t = \left\lfloor\frac{d_{min}-1}{2}\right\rfloor\]Geometrically, this can be thought of as the maximum radius of spheres around valid codewords, such that these spheres never overlap.
It turns out that all Hamming codes have a $d_{min} =3$, and the rate $R = k/n$ depends on the specific type of Hamming code used. For a (7, 4) code, this is $R = 4/7 \approx 0.57$, which is kind of terrible. Larger Hamming codes achieve higher rates, but their error-correcting capability never improves. We are therefore motivated to ask whether we can construct linear block codes with both large minimum distance and high rate, allowing reliable communication with relatively little redundancy and operation close to the Shannon limit.
LDPC Codes
In designing LDPC codes, the first step is to take note of a paradigm shift. Previously, we were interested in designing a code such that there is no possibility of error, i.e., codes with as high $d_{min}$ as possible. It turns out that this is not a sustainable way of generating codes with rates close to the channel capacity. Instead, we aim to minimise the error probability, accepting that a few errors are possible here and there.
Implementation
1. Naïve C implementation
My naive implementation of an LDPC decoder is entirely run on the CPU, in about 300 lines of C code. The main decode loop is a simple implementation of min-sum,
int decode(ldpc_code_t *code, ldpc_decoder_t *decoder, int *bits, int max_iters)
{
for(int i = 0; i < code->E; i++) {
decoder->c2v[i] = 0;
}
for (int it = 1; it <= max_iters; it++) {
check_update(code, decoder);
decode_hard(code, decoder, bits);
int bad = check_syndrome(code, bits);
DPRINTF("iter %i: %i unsatisfied checks\n", it, bad);
if (bad == 0) {
region_free(&c2v_region, &arena);
region_free(&v2c_region, &arena);
return it; // converged to a valid codeword
}
var_update(code, decoder);
}
region_free(&c2v_region, &arena);
region_free(&v2c_region, &arena);
return -1;
}
Besides using an arena allocator to avoid malloc overhead in allocating memory for the check/variable node messages, the algorithm is really not very optimised. Visual Studio’s profiler (yes I’m doing this on Windows, it will be clear later why) tells me that the hot path is very much in this decode loop, mostly in the check_update() function.
!image.png
This is not particularly surprising, as it involves the highest number of mathematical operations. It took us about 13 seconds to run a simulation harness. This specific test involves decoding 100k blocks for 8 different values of $E_b/N_0$. The $H$ matrix we chose here was 96.3.963 from David Mackay’s library.
This code has $n = 96, m=48$ and $288$ edges. As codes go, its big but not huge. The final goal is to decode this monster with $n=20000$. Naturally, my current decoder is very unhappy with this