Skip to content

Design Strategies AC7TD

Jan Schiefer edited this page Apr 6, 2017 · 11 revisions

Towards a Reference Design

from Jan Schiefer, ac7td, @jschiefer

Purpose

Jan is working on a reference design in order to better understand LDPC.

I am putting together a little toy LDPC decoder (without any regards to performance), to understand how it works.

This will be a big step forward in teaching LDPC, as easily-accessible implementations seem to be thin on the ground.

Introduction

These are some travel notes from the journey to understanding LDPC decoding. This is one of the more intimidating parts of the DVB-S2x standard (to me at least). It is also one of the more processing-intensive parts of the receiver, so the implementation is more challenging at the required performance point, and will require more than just software. Probably, a realistic implementation on low-cost hardware will require some more advanced technologies, like implementations on GPU, FPGA or other special-purpose hardware.

This raises a lot of questions:

Could an LDPC decoder implemented on an FPGA? How many logic elements? Could the Parallella's Epiphany III co-processor do it? Or how about the 2 PRUs (Programmable Real-Time Units) you find on a BeagleBone Black, might they be sufficient? Do you need floating point arithmetic to do this? How do you answer these questions? Where do you even start?

I have decided to start by implementing a "thin slice" of the simplest possible decoder I can think of, and then build on that. How simple? Very simple:

  1. Get a single frame of test data created by the gnuradio DVB-S2x LDPC encoder
  2. For the MODCOD used in this data frame, find the relevant parts of the standard and implement those parts, nothing else.
  3. Implement a first simple decoder that decodes this one frame. As there are no bit errors, the assumption is that this should require only a single iteration.
  4. Play with introducing errors and see how many iterations it takes.
  5. Play with and understand different optimized algorithms as described in literature.

Here are some non-requirements:

  • Performance, memory consumption, throughput, latency – none of them matter
  • Yes, we have floating point, and we are not afraid to use it.
  • It's OK to throw this code away when it is done. In fact, that is the expectation.
  • Clarity of thought and implementation is paramount. I will use a mix of C and F# (on .NET Core) on Linux for the initial prototype.

So let's get started.

Creating test data

The next thing we will need is some test data that we can use to experiment with decoding. Reasonably current versions of GNU Radio (>= 3.7.7, I believe) include DVB-S2 support, courtesy of @drmpeg (find source code for these blocks here). Anyway, the encoder that comes with this code has been well tested and can serve us as a reference encoder, so this is a great place to start. There is an example DVB-S2 transmit flowgraph included in the the file examples/dtv/dvbs2_tx.grc of your GNU radio installation. It reads an example data file (transport stream), which you can download from here (and if you want to know what it contains, you can play it with VLC!).

A naïve first attempt

The flowgraph from dvbs2_tx.grc is designed to play out the encoded video stream through some real hardware, a USRP for example. This isn't really what we are trying to do, so instead, let's lop off the end of the transmitter chain after the LDPC encoder, and write the resulting output to a file. We'll end up with something that looks like this (code is here):

This looks simple enough: The transport stream has some BB headers added, gets interleaved, the BCH coding is added and the result is run through the LDPC encoder. What comes out of the LDPC encoder is written to a file.

Running this flow graph yields a somewhat surprising result: The original 221 MB of transport stream results in 2 GB worth of encoded data! Why is this? It turns out that the gnuradio data stream gets expanded by the BBHeader block to use a whole byte to represent a single bit. This is responsible for most of the growth in file size. The rest is caused by the addition of headers, BCH checksums, and of course the LDPC parity bits.

Using a whole byte to represent a single bit is a nice implementation convenience, and for the purpose of the investigation, we are going to stick with this approach, as it makes the resulting code a lot simpler.
And did I mention before that performance doesn't matter just yet?

But is this the right thing to do? Turns out, it is not! While one might think that the bits are all that we need, that is only half the battle. LDPC decoding is a soft-decision decoder, which means that it needs more than just bits on its input. With each bit (or group of bits, depending on the type of modulation), the decoder also expects an initial estimate of the reliability of each bit. Intuitively this makes sense: If something in the receiver can tell me that bit 59 is absolutely totally guaranteed to be a 0, but it isn't quite so sure about bits 72-79, shouldn't the decoder make use of this information to inform its decoding? Turns out, this is exactly what a soft-decision decoder does, which is why they typically perform better than their hard-decision counterparts.

How is this reliability estimate delivered to the decoder? Typically as an LLR (log-likelihood ratio), but don't worry about that just yet, we'll get there.

So what does that mean for our test data? Well, in addition to providing the bits, we should also provide some measure of error, in order to evaluate what it takes to decode in the presence of errors.

Let's add some error

The simplest modulation in DVB-S2 is QPSK, in which each constellation point represents two bits. The DVB-S2 Standard defines the bit mapping into the QPSK constellation in section 5.4.1., which we can easily translate to the symbols table of a GNU radio Chunks to Symbols symbol-mapping block. As for the errors I promised earlier, the satellite downlink channel is typically an AWGN channel (Additional White Gaussian Noise), so let's add some noise: A Fast Noise Source block with the noise configured as Gaussian is added to the QPSK symbols, and voilà, we have a noisy signal. The flowgraph is here, and below is an image of the flowgraph and a snapshot of the resulting signal:

This example shows a very modest amount of error, which should make life pretty easy for our LDPC decoder. Let's start simple and progress to the more interesting cases over time.

This is the point where we will switch from GNU Radio flowgraphs to code, and deepen our understanding with an example implementation of an LDPC decoder. The output of our GNU Radio graph is written to an output file, so we will need to figure out how to read this. The file format is a sequence of complex numbers, which we will slurp into our code and attempt to decode.

[to be continued]