3
\$\begingroup\$

I am selfstudying error correction block codes and has a confusion about their performance.

Suppose we have \$r\$ information bits and we make \$k\$ coding bits in addition. I am given to understand that, for the same amount of energy per information bit, the coded system performs better compared to an uncoded system, where the channel is additive white Gaussian noise (AWGN) and modulation is BPSK.

This is demonstrated in a simulation, where the bit error rate (BER) is plotted against energy per information bit.

My question is, how does this come to be? When we code the \$r\$ bits, we in fact spread the energy over \$r+k\$ bits. Where as in uncoded case all the energy is used on \$r\$ bits alone. On the other hand the coded bit stream has \$r+k\$ dimensions whereas uncoded steam has \$r\$ dimensions.

Can someone please explain, mathematically, where the BER improvement comes from?

\$\endgroup\$
1

2 Answers 2

3
\$\begingroup\$

Think about the probability of an uncorrectable error occurring in each message. If you just send r bits, all errors are uncorrectable, so the chance of a successfully sent message is $$(1-P(bitError))^r$$ (in other words, all bits have to pass through with no error.) Now, say you spread the energy just a little to add k error correction bits, such that you can correct a single bit error. Then the chance of a single bit error does go up due to the weaker signal, but the chance of a successfully sent message becomes something like $$(1-P(higherBitError))^{r+k} + (r+k)(P(higherBitError)(1-P(higherBitError))^{r+k-1})$$ (In other words, it's successful if all bits pass through with no error as before. But it's also successful in the (r+k) possible situations where 1 bit has an error and the other r+k-1 bits don't.)

I'm not 100% sure my probability formulation is exactly correct, but you can see the idea: there are now more possible situations where you win. Depending on the values of r, k and how much the bit error probability increases, the error correction will often result in a higher probability of a successfully sent message.

\$\endgroup\$
0
\$\begingroup\$

When transmitting over a noisy channel, the mutual information between the input and the output depends on the chosen input ensemble[1]. One can choose an input ensemble to maximize this mutual information. When one has done so, the resulting maximum mutual information is known as the capacity of the channel. [2] The transformation that maps high-entropy data to that optimal input distribution is the error correcting code.

[1] An ensemble is an "alphabet" of possible input symbols along with associated probabilities (which do not have to be uniform)

[2] In the case of an Additive Gaussian White Noise channel, this capacity is given by the Shannon–Hartley theorem.

\$\endgroup\$
3
  • \$\begingroup\$ Thanks for the explanation. Could you please explain how coding can make the input ensemble look Gaussian (I read that Gaussian is the capacity achieving input)? \$\endgroup\$
    – seek
    Sep 21, 2014 at 19:21
  • \$\begingroup\$ MacKay explains it better than I can - chapter 11 of cs.toronto.edu/~mackay/itprnn/book.pdf (but you may need to read some of the other chapters for background) \$\endgroup\$ Sep 22, 2014 at 2:25
  • \$\begingroup\$ Note also that practical error correcting codes do not achieve the channel capacity. Most commonly-used ones are quite far from capacity, but some recently-developed codes (e.g. Turbo codes and LDPC) can come extremely close to the capacity. \$\endgroup\$ Sep 22, 2014 at 2:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.