trouble understanding calculation of signal-to-noise for ldpc codes

Question

My apologies if the answer to this question is too easy. I am a mathematics student and the subject of low density parity check codes is new to me.

In many papers on LDPC codes, there are plots showing BER (bit error rate) vs SNR (signal to noise ratio). I have designed some codes and I want to show their performance by giving one of these plots.

I noticed that most softwares which test these codes on the white gaussian noise channel take the code, max number of iterations, and the noise standard deviation as inputs, and then give the BER as an output.

My question is, how do I calculate the SNR (Eb/N0) given the code, max number of iterations, and noise standard deviation for making the plot?

For example, there is software that can be downloaded from: http://www.cs.toronto.edu/~radford/ftp/LDPC-2012-02-11/index.html which can build random LDPC codes and then test their performance on the white gaussian noise channel. The following is an example of some inputs for that software which comes included with the software. Before each test, it states the noise standard deviation, and then the corresponding snr value Eb/N0:\

#!/bin/sh

# Example of a (10000,5000) LDPC code with 3 checks per bit and 6 bits per 
# check, tested on Additive White Gaussian Noise channels with noise standard 
# deviations varying from 0.80 to 0.95.
#
# Testing is done by transmitting random messages, with pipes used so that
# intermediate files are avoided.  Decoding is done using a maximum of 250
# iterations of probability propagation.

set -e  # Stop if an error occurs
set -v  # Echo commands as they are read

make-ldpc ex-ldpc36-5000a.pchk 5000 10000 2 evenboth 3 no4cycle
make-gen  ex-ldpc36-5000a.pchk ex-ldpc36-5000a.gen dense
rand-src  ex-ldpc36-5000a.src 1 5000x100

# NOISE STANDARD DEVIATION 0.80, Eb/N0 = 1.94 dB

encode      ex-ldpc36-5000a.pchk ex-ldpc36-5000a.gen ex-ldpc36-5000a.src - \
 | transmit - - 1 awgn 0.80 \
 | decode   ex-ldpc36-5000a.pchk - - awgn 0.80 prprp 250 \
 | verify   ex-ldpc36-5000a.pchk - ex-ldpc36-5000a.gen ex-ldpc36-5000a.src

# NOISE STANDARD DEVIATION 0.85, Eb/N0 = 1.41 dB

encode      ex-ldpc36-5000a.pchk ex-ldpc36-5000a.gen ex-ldpc36-5000a.src - \
 | transmit - - 1 awgn 0.85 \
 | decode   ex-ldpc36-5000a.pchk - - awgn 0.85 prprp 250 \
 | verify   ex-ldpc36-5000a.pchk - ex-ldpc36-5000a.gen ex-ldpc36-5000a.src

# NOISE STANDARD DEVIATION 0.90, Eb/N0 = 0.92 dB

encode      ex-ldpc36-5000a.pchk ex-ldpc36-5000a.gen ex-ldpc36-5000a.src - \
 | transmit - - 1 awgn 0.90 \
 | decode   ex-ldpc36-5000a.pchk - - awgn 0.90 prprp 250 \
 | verify   ex-ldpc36-5000a.pchk - ex-ldpc36-5000a.gen ex-ldpc36-5000a.src

# NOISE STANDARD DEVIATION 0.95, Eb/N0 = 0.45 dB

encode      ex-ldpc36-5000a.pchk ex-ldpc36-5000a.gen ex-ldpc36-5000a.src - \
 | transmit - - 1 awgn 0.95 \
 | decode   ex-ldpc36-5000a.pchk - - awgn 0.95 prprp 250 \
 | verify   ex-ldpc36-5000a.pchk - ex-ldpc36-5000a.gen ex-ldpc36-5000a.src

But the program takes the noise standard deviation as an input and not the snr value. I want to know how, given the code, max number of iterations, and noise standard deviation, how to calculate the snr value.

i.e. in the comments of the code given above, its says that when the noise standard deviation is .8, the value for Eb/N0 is 1.94. How is this correspondence made?

Thanks in advance.

Answer 1

its says that when the noise standard deviation is .8, the value for Eb/N0 is 1.94. How is this correspondence made?

Well, assuming a normalized signal ($x=\pm 1$) [*] and calling $z$ the noise, we have

$$\frac{\sigma_x^2}{\sigma_z^2}=\frac{1}{(0.8)^2}=1.5625$$

Which in db is $10 \log_{10} 1.5625 =1.9382$ dB

---

Update: [*] Why assume $x=\pm 1$? Just guessing. If you are told that you are adding a noise of given standard variation, then you are supposed to know the amplitude of your signal (assumed discrete) -and, here, binary.

An important thing to notice here: "a noise of given standard variation" implies we are speaking here of a time-discrete binary channel, not of "real" (continuos time) channel. To understand the relationship of both kind of (Gaussian) channels, read eg. MacKay chap 11 (*).

Because we are speaking of time-discrete things, our "signal/noise powers" are actually just variances (I changed the notation to make this clear). Hence it makes really not sense to speak of $N_0$ here, directly (that's a parameter of the time-continous gaussian noise, a spectrum).

If we look into the docs of your software all this seems confirmed: we have time-discrete signals, awgn is just the standard deviation of a gaussian, and the signal is assumed encoded as $\pm 1$.

So, what's the relationship between $\sigma_x^2/\sigma_z^2$ and $E_b/N_0$? Again, that's explained in the bibliography. Here's a summary - it if feels too long, go straight to equation $(2)$

---

First it's known that, under certain standard assumptions, a time-continuos gaussian noise $z_t$ of density spectrum $N_0$ (which, to add confusion, alludes to a value of the spectrum equal to $N_0/2$, so the total power of a signal with bandwith $[-W,W]$ is $ N_0 W$)... corresponds to a time-discrete gaussian white noise $z[n]$ of variance $N_0/2$ (why? not obvious at all; see eg. MacKay eq 11.10).

Further, regarding the signal: a continuous signal $x_t$ of (real) power $P$ trasmitted over a bandwidth $[-W,W]$ can be put in correspondence with a discrete signal $x[n]$ ($2W$ samples per second) with $\sigma_x^2=P/2W$

$$ \begin{array}{c c c} {\rm discrete}& &{\rm continuos}\\ \hline z[n]& {\rm (noise) }& z_t \\ N(0,\sigma_z^2) & \sigma^2_z=\frac{N_0}{2} &S_z(\omega)=N_0/2\\ \hline x[n]& {\rm (signal) }& x_t \\ \text{samples per second: } 2W & \sigma_x^2=\frac{P}{2W}& \text{power: } P \text{ total bandwidth: } 2W \\ \end{array} $$

Then, because we trasmit $2W$ samples (here, bits - because we have a binary trasmission!) per second, the total (real) energy per bit is

$$ E=\frac{P}{2W}=\sigma_x^2 \tag{1}$$

(not a surprise, but not obvious!). But we are interested in $E_b$, which is the energy per information bit (not per trasmitted bit). Then $E_b=\frac{E}{R}$ and (the key equation)

$$ \frac{E_b}{N_0}=\frac{\sigma_x^2}{2 \sigma_z^2 R} \tag{2}$$

---

In our case, $R=5000/10000=1/2$ so the factor $2$ vanishes (but this is just a coincidence!) hence

$$ \frac{E_b}{N_0}=\frac{\sigma_x^2}{\sigma_z^2}=\frac{1}{\sigma_z^2} \tag{3}$$ or in $dB$ (remember to multiply the $\log_{10}$ by $10$ if using variances, by $20$ if using deviations)

$$ \frac{E_b}{N_0}(dB)=10 \log_{10} (1/\sigma_z^2)$$

Answer 2

My educated guess is that you cannot calculate the points on such plots - they are results of extensive simulations. So you need to:

1. Implement a decoding algorithm. In the case of LDPC-codes you need to implement the belief-propagation algorithm.
2. Select a modulation scheme (BPSK, N-QAM, whatever). You also need to know how to calculate the LLRs of individual bits given a channel model (Gaussian with a known SNR, Rayleigh fading with a known SNR,...)
3. Set the parameters of your noise generator to match that of the SNR you want to work on.
4. Generate $N$ random codewords in a loop. Within a loop you modulate, add noise, run the decoder, and observe the number of bit errors by comparing the decoder output to the original codeword. Collect the necessary data (number of errorneous bits vs. N*blocklength) to estimate the BER. Observe that N should be large enough so that you get at least a hundred codewords with errors (with SNR in the waterfall region the required N goes up quite fast as SNR grows). The rule of thumb is that 200 error events give you a single significant digit in the BER value.
5. Store the estimated (SNR, BER) pair. That gives you a single point on the curve. Then increment SNR, and go back to Step 3.

Been there, done that. Armed with a single CPU laptop and DOS-Pascal development environment I recall having needed to let the simulation run overnight to get a single point at around BER 1E-7. Give or take +1 in the exponent. I'm not a good programmer, but I had to do everything from scratch myself to have full control of everything.

Mind you, the LDPC gurus have more efficient ways of predicting the location of the waterfall as a function of the weight distributions of both variable and check nodes in the Tanner graph. All that without actually generating a code - they just assume a kilometer long random code with the prescribed weight distributions as above. Don't ask me how they do that - it goes over my head. IIRC they cannot get the BER/SNR curve of a code of a finite length.

---

When you reach the error floor you will get the urge to cheat on the number of iterations, and call your estimate good after 10-20 error events. To an extent that is ok. But it will show as "jaggies" on the BER-curve.