Maths – Page 3 – Daniel Estévez

Testing LDPC code erasure decoding performance

In my previous post I talked about the RFC5170 LDPC codes used in Outernet. There I explained in some detail the pseudorandom construction of the LDPC codes and the simple erasure decoding algorithm used both in free-outernet and in the official closed-source receiver.

The Outernet LDPC codes follow what I call the “identity scheme”. This is different from the staircase and triangle schemes introduced in the RFC. The identity scheme already appeared in the literature, but it did not make it into the RFC. See, for instance, the report by Roca and Neumann Design, Evaluation and Comparison of Four Large Block FEC Codecs, LDPC, LDGM, LDGM Staircase and LDGM Triangle, plus a Reed-Solomon Small Block FEC Codec, especially Section 2, where it is called “LDGM”.

I also commented that erasure decoding for an LDPC code (or any other linear code) amounts to solving a linear system. This can be done using any algebraic method, such as Gaussian elimination. However, the simple decoding algorithm used in Outernet is as follows: try to find an equation with only one unknown, solve for that unknown, and repeat until the system is solved. Clearly this algorithm can fail even if the system can be solved (see my previous post for some examples and formal results). I will refer to this algorithm as iterative decoding, as it is done in the RFC.

With these two things in mind, I wondered about the performance of the LDPC codes used in Outernet and the iterative decoding algorithm. I’ve done some simulations and here I present my results.

Outernet LDPC code revisited

I have been preparing the slides for my future talk about reverse-engineering Outernet at FAQin 2018. While doing this, I have been re-reading some of the material about the work done on LDPC code and FEC in Outernet by George Hopkins in January 2017. One of the things I didn’t do back then was to read carefully the LDPC decoding function implemented by George.

In my post I explained that the LDPC code used in Outernet followed RFC5170, and I wondered whether it used the staircase scheme or the triangle scheme. I also commented that erasure decoding with an LDPC code (or any other linear code, actually) was mathematically equivalent to solving a linear system where the unknowns correspond to the erased symbols. I observed that the decoding function looked very different from this mathematical procedure, but should do more or less the same thing. Now I have read the decoder implementation carefully and I have the answer to both questions.

About critical damping

Having to deal with DSP texts written by engineers, I have sometimes to work a bit to get a good grasp of the concepts, which many times are not explained clearly from their mathematical bases. Often, a formula is just used without much motivation. Lately, I’ve been trying to understand critically damped systems, in the context of PLL loop filters.

The issue is as follows. In a second order filter there is a damping parameter \(\zeta > 0\). The impulse response of the filter is an exponentially decaying sinusoid if \(\zeta < 1\) (underdamped system), a decaying exponential if \(\zeta > 1\) (overdamped system) and something of the form \(C t e^{-\lambda t}\) if \(\zeta = 1\) (critically damped system). Critical damping is desirable in many cases because it maximizes the exponential decay rate of the impulse response. However, many engineering texts just go and choose \(\zeta = \sqrt{2}/2\) without any justification and even call this critical damping. Here I give some motivation starting with the basics and explain what is special about \(\zeta = \sqrt{2}/2\) and why one may want to choose this value in applications.

An erasure code based on Vandermonde matrices

I’ve been looking at an erasure code by Luigi Rizzo which is based on Vandermonde matrices, since this code is used in Outernet. In fact, it is the code implemented by the zfec library. Luigi Rizzo describes his code in a paper from 1997, but the paper can be very confusing and misleading because it describes the mathematics in very little detail. I needed to go to the source code to understand how it works. Actually, the idea behind this code is very simple. Here I do a mathematical description of the code and show that it is the same as a Reed-Solomon code. This is rather weird, because Luigi Rizzo makes no mention of Reed-Solomon codes, which were first described in 1960.

How hard is it to decode 3CAT-2?

In a previous post, I looked at the telemetry packets transmitted by the satellite 3CAT-2. This satellite transmits 9600bps AX.25 BPSK packets in the Amateur 2m band. As far as I know, it is the only satellite that transmits fast BPSK without any form of forward error correction. LilacSat-2 uses a concatenated code with a (7, 1/2) convolutional inner code and a (255, 223) Reed-Solomon outer code. The remaining BPSK satellites transmit at 1200bps, either using AX.25 without FEC (the QB50p satellites, for instance), or with strong FEC (Funcube, for example). Therefore, I remark that 3CAT-2’s packets will be a bit difficult to decode without errors. But how difficult? Here I look at how to use the theory to calculate this, without resorting to simulations.

Scramblers and their implementation in GNUradio

A scrambler is a function that is applied to a sequence of data before transmitting with the goal of making this data more “random-like”. For instance, scrambling avoids long runs of the bits 0 or 1 only, which may make the receiver loose synchronization or cause spectral concentration of the signal. The receiver applies the inverse function, which is called descrambler, to recover the original data. The documentation for the scrambler blocks in GNUradio is not very good and one may need to take a look at the implementation of these blocks to get their parameters right. Here, I’ll try to explain a bit of the mathematics behind scramblers and the peculiarities of their implementation in GNUradio.

Estimation of the contribution of the frontend to the total noise figure

In a radio receiver composed of two stages, the total noise factor \(F\) can be computed using Friis’s formula as\[F = F_1 + \frac{F_2 – 1}{G_1},\]where \(F_1\) is the noise factor of the first block, \(G_1\) is the gain of the first stage and \(F_2\) is the noise factor of the second stage. If \(G_1\) is large enough, then the contribution of the second factor is small and the total noise factor of the whole system is essentially the same as the noise factor of the first stage. This is the reason why a low noise amplifier is useful as a frontend, because it has a low noise factor \(F_1\) and high gain \(G_1\).

If \(F_2\) and \(G_1\) are known (perhaps only approximately), then it is easy to check if the contribution of the frontend to the total noise figure is large enough so that the total noise figure is determined by the noise figure such frontend alone. However, it may happen that one or both of \(F_2\) and \(G_1\) are not known. In email communication, Leif Åsbrink mentioned that there is an easy way of checking the contribution of the frontend without knowing these parameters. The method is to switch off the frontend and note the drop in the noise floor. He gave the following estimates: if the noise floor drops by more than 10dB, then the total noise figure is the same as the noise figure of the frontend up to 1dB; if the noise floor drops by more than 17dB, then the total noise figure is the same as the noise figure of the frontend up to 0.1dB. Here I present the maths behind these kind of estimates.

Another look at recursive quadrature oscillators

In a recent post, we looked at which \(2\times 2\) Toeplitz real matrices \(T\) gave useful quadrature oscillators by the recurrence \(x_{n+1}=T x_n\). There, we computed their eigenvalues and solved the recurrence in terms of them. Of course, there are many other ways to approach this problem. Here we look at another approach that gives a good geometric picture of what happens, can be applied to general \(2\times 2\) matrices, and may be used as a starting point for the \(n\times n\) case.

A look at a new digital quadrature oscillator

Two sinusoidal signals are said to be in quadrature if they have a constant phase difference of 90º. Quadrature signals are widely used in signal processing. A digital quadrature oscillator is just an algorithm that computes the sequence \(x_n = (\cos(\omega n), \sin(\omega n))\), \(n\geq 0\), or a similar sequence of sinusoids in quadrature. Here \(\omega\) is the oscillator frequency in radians per sample. Direct computation of this sequence is very time consuming, because the trigonometric functions have to be evaluated for each sample. Therefore, it is a good idea to use a linear recurrence scheme to compute \(x_n\). Using basic trigonometric identities, we see that\[x_{n+1} = A x_n,\quad x_0=\begin{pmatrix}1\\0\end{pmatrix},\]with\[A = \begin{pmatrix}\alpha_1 & -\alpha_2\\\alpha_2 & \alpha_1\end{pmatrix},\quad \alpha_1 = \cos(\omega),\ \alpha_2=\sin(\omega).\]

However, to actually perform these computations in a digital processor, one has to quantize \(\alpha_1,\alpha_2\), meaning that one has to replace \(\alpha_1,\alpha_2\) by approximations. It is easy to see that if one replaces \(\alpha_1,\alpha_2\) by some perturbation, then the eigenvalues of \(A\) are no longer in the unit circle, so the oscillation can grow or decay exponentially and one would need to apply an AGC scheme to keep this method stable.

Here we will look at a new quadrature oscillator by Martin Vicanek that has appeared recently and solves this problem.