Effect of DFE Error Propagation on the Performance of Reed-Solomon Codes

Short introduction to Reed Solomon codes

Reed Solomon codes are a class of non-binary linear block codes that are defined over finite fields GF(q), where q is a power of a prime, usually 2. Ignoring (a lot of) details, this means:

Block: Data stream is encoded in fixed size chunks, called blocks, as opposed to continuos encoding for convolution codes.
Linear: Sum (over GF(q)) of two codewords is another codeword.
Non-binary: The code is defined over multi-bit digits (symbols) from GF(2^m), as opposed to binary codes which work over symbols from GF(2), i.e., binary digits.
- In simple terms, this means that each symbol is m bits.

RS(n, k) code over GF(2^m):

Reed Solomon codes are usually speciefied by three parameters m, n, and k, where:

m : symbol size in bits
k : message (inoformation word) size in symbols
n : codeword size in symbols, n <= 2^m - 1.

Reed Solomon Encoder

A RS (systematic) encoder takes a k symbol block and appends n-k parity symbols to it, forming a n symbol codeword.

Characteristics of Reed Solomon Codes

Reed Solomon codes (all codes, infact) are characterized by dmin
dmin is the smallest Hamming distance (number of digits that differ) between any two codewords.
A code width minimum distance dmin can correct any pattern of upto t = (dmin - 1)/2 errors.
Also, dmin <= n - k + 1, i.e. maximum distance possible = parity_size + 1
RS codes are maximum distance separable (MDS) codes because dmin = n - k + 1.

Take for example RS(15, 9) over GF(2^4):

m = 4 => 4 bit symbols
n = 15 => codeword size is 15 symbols
k = 9 => message is 9 symbols
dmin = 15 - 9 + 1 = 7
t = (7 - 1)/2 = 3 => code can correct any pattern of upto 3 errors

Other codes in use:

RS(528, 514) used for IEE803.2bj PAM-2 standard => t = 7
RS(544, 514) used for IEE803.2bj PAM-4 standard => t = 15
RS(255, 223) used by NASA => t = 16

Reed Solomon Decoder

Bounded distance decoding is the standard (most commonly used) approach.
This is equivalent to maximum likihood decoding.

Let,

v = transmitted codeword, and
e = be the error pattern,
then the received vector is, r = v + e

The decoder tries to find a minimum weight error pattern e', such that v' = r - e' is a valid codeword.

Let t' be the actual number of errors. Then there are three possibilities:

Correct decoding when r is within the decoding sphere of v, i.e., t' <= t.
- Decoder action: send out the corrected codeword.
Decoding failure when t' > t but r does not fall within the decoding sphere of of some other codeword.
- Decoder action: send out the uncorrected codeword and set a failure flag.
Decoding error (mis-decode) when t' > t and r falls within the decoding sphere of v' != v.
- Decoder action: send out the mis-corrected codeword.

Decoding error is thus a silent failure. Fortunately, for practical codes, it is very rare. Additional CRC in upper protocol layers also help.

Performance of Reed Solomon Codes

Consider RS(n, k), with t = (n - k)/2.

Let, $X$ = number of (symbol) errors in the codeword (0 <= X <= n), and

$P_X(x)$ = PMF of X = $Pr\{X = x\}$

Also, let $Y$ = number of (symbol) errors in the codeword (0 <= Y <= n) post FEC.

Then, the probability of not-decoding-correctly is

$$ P_{ndc} = Pr\{X >= t + 1\} = \sum_{x = t+1}^{n} P_X(x) $$

Also, the expected number of symbols errors is

$$ \begin{aligned} E[X] &= \sum_{x = 0}^{n} x \cdot P_X(x) \\ E[Y] &= \sum_{y = t+1}^{n} y \cdot P_X(y) \end{aligned} $$

The pre and post FEC symbol-error rates and bit error rates can be calculated as $$ BER_{pre} = \frac{pe}{pe + 1 - pb}, \qquad SER_{pre} = \frac{E[X]}{n}, \qquad SER_{post} = \frac{E[Y]}{n}, \qquad BER_{post} = \frac{BER_{pre} * SER_{post}}{SER_{pre}}. $$



In [1]:

    
import numpy as np
import matplotlib.pyplot as plt
from scipy.misc import factorial
from errsim import *
%matplotlib inline
import matplotlib.pylab as pylab
pylab.rcParams['figure.figsize'] = 12, 10



In [6]:

    
# Error PMF, P(x, n) = Prob{x symbol errors in a block of n symbols}
# pe = Prob. of bit error in normal/good state
# pb = Prob. of bit error in burst/bad state
# m = Number of bits per symbol
# n = Number of symbols per block

# Simulated PMF: pe=1e-2, pb=0.5, m=4, n=15, nblks=1e6
np.random.seed(1)
spmf_1em2_0p5_4_15 = errhist(1e-2, 0.5, 4, 15, int(1e6)) / 1e6

# Analytical PMF: pe=1e-2, pb=0.5, m=4, n=15
apmf_1em2_0p5_4_15 = errpmf(1e-2, 0.5, 4, 15)



In [7]:

    
x = np.arange(16)
plt.semilogy(x, apmf_1em2_0p5_4_15[x], 'b-',   label='Analytical 1e-2, 0.5, 4, 15')
plt.semilogy(x, spmf_1em2_0p5_4_15[x], 'ro--', label='Simulation 1e-2, 0.5, 4, 15')
plt.title('P(x, n) = Prob{x symbol errors in n symbol block}')
plt.xlabel('Symbols, x')
plt.ylabel('Probability')
plt.legend()
plt.grid()



In [ ]: