Module rs 

Reed–Solomon codes over $\mathrm{GF}(2^{m})$: systematic encoding, errors-and-erasures decoding, shortening.

Model

In the field $\mathrm{GF}(2^{m})$ of comnum_math::gf2m (primitive element $\alpha$, root of the chosen primitive polynomial), the $t$-error-correcting Reed–Solomon code has the generator polynomial

$$ g(x) = \prod_{i=0}^{2t-1} \left(x - \beta^{b+i}\right), \qquad \beta = \alpha^{c}, $$

with a first consecutive root $b$ (1 in the textbooks, 0 in DVB and QR codes, 112 in CCSDS) and a root step $c$ coprime with $2^{m} - 1$ (1 everywhere but CCSDS, whose roots are the powers of $\beta = \alpha^{11}$). The code of length $2^{m} - 1$ and minimum distance $2t + 1$ is shortened to $n$ symbols by fixing its first information symbols to zero; a codeword carries $k = n - 2t$ information symbols. The symbols are u16 values below $2^{m}$ ($m \le 16$); pack_symbols and unpack_symbols convert them to and from bits ($m$ per symbol, most significant first), so that the code also works on bits like the other codes of the crate (ReedSolomon::encode, ReedSolomon::decode and the BlockCode interface on $km$ and $nm$ bits).

The encoder is systematic: the $k$ message symbols (the highest degree first, in transmission order), then the $2t$ coefficients of $x^{2t} u(x) \bmod g(x)$. The decoder is the classical one:

1. the syndromes $S_{j} = r(\beta^{b+j})$, $j = 0, \dots, 2t - 1$;
2. with $s$ erased positions of locators $Z_{l}$, the erasure locator $\Gamma(x) = \prod_{l} (1 - Z_{l} x)$ and the modified syndromes $T(x) = S(x)\Gamma(x) \bmod x^{2t}$ (Forney 1965);
3. the error locator $\Lambda(x)$ by the Berlekamp–Massey algorithm on $T_{s}, \dots, T_{2t-1}$, of degree at most $\lfloor (2t - s)/2 \rfloor$;
4. the roots of $\Psi(x) = \Lambda(x)\Gamma(x)$ by a Chien search over the $n$ positions;
5. the values by Forney’s formula, with $\Omega(x) = S(x)\Psi(x) \bmod x^{2t}$,

$$ Y_{l} = \frac{Z_{l}^{1-b}, \Omega!\left(Z_{l}^{-1}\right)}{\Psi’!\left(Z_{l}^{-1}\right)}. $$

It corrects $e$ errors and $s$ erasures whenever $2e + s \le 2t$ and reports a failure (None) when the locator has the wrong degree, fewer roots than its degree, or gives a zero error value: the word then has more errors than the code corrects. Beyond $t$ errors a bounded-distance decoder either fails or lands on another codeword, so the closed forms word_error_probability, symbol_error_probability and bit_error_probability count every word with more than $t$ symbol errors as lost.

The symbols here are polynomial-basis values; the dual-basis (Berlekamp) symbols of CCSDS 131.0-B-5 (Sec. 4.3.9), its interleaved codeblocks and virtual fill are crate::ccsds::CcsdsRs, built on this code with the CCSDS field, roots and root step.

Examples

use comnum_fec::rs::ReedSolomon;
// the (255, 223) code over GF(256), t = 16
let code = ReedSolomon::new(8, 16)?;
assert_eq!((code.n_symbols(), code.k_symbols()), (255, 223));
let msg: Vec<u16> = (0..223).map(|i| (i * 7 % 256) as u16).collect();
let mut c = code.encode_symbols(&msg)?;
for i in [0, 5, 100, 254] {
    c[i] ^= 0x5A;                                     // four symbol errors
}
c[200] = 0;                                           // and one erasure
assert_eq!(code.decode_erasures(&c, &[200])?, (msg.clone(), Some(5)));
// on bits: 223 × 8 information bits in, 255 × 8 coded bits out
let bits = vec![1u8; 223 * 8];
let coded = code.encode(&bits)?;
assert_eq!(coded.len(), 255 * 8);
assert_eq!(code.decode(&coded)?, (bits, Some(0)));

References

1. I. S. Reed and G. Solomon, “Polynomial codes over certain finite fields,” J. SIAM, 8(2), 300–304, 1960.
2. S. Lin and D. J. Costello, Error Control Coding, 2nd ed., Pearson, 2004, ch. 7 (Sec. 7.3: the generator polynomial, Sec. 7.4: the Berlekamp algorithm).
3. G. D. Forney, “On decoding BCH codes,” IEEE Trans. Inf. Theory, 11(4), 549–557, 1965 (the error values and the erasures).
4. J. L. Massey, “Shift-register synthesis and BCH decoding,” IEEE Trans. Inf. Theory, 15(1), 122–127, 1969.
5. S. B. Wicker, Error Control Systems for Digital Communication and Storage, Prentice Hall, 1995, ch. 9 (errors-and-erasures decoding).
6. J. G. Proakis and M. Salehi, Digital Communications, 5th ed., McGraw-Hill, 2008, Sec. 7.5.2 (the block and bit error probabilities of hard-decision decoding).
7. B. Sklar, Digital Communications: Fundamentals and Applications, 2nd ed., Prentice Hall, 2001, Sec. 8.1.2 (the bit error probability of Reed–Solomon codes).

Structs

ReedSolomon

A (shortened) Reed–Solomon code over $\mathrm{GF}(2^{m})$ (see the module).

Functions

bit_error_probability

The bit error probability after decoding of a code over $\mathrm{GF}(2^{m})$: a wrong symbol carries on average $2^{m-1}/(2^{m} - 1)$ wrong bits per bit (Sklar, Sec. 8.1.2),

pack_symbols

Pack bits into symbols of m bits, the most significant first.

symbol_error_probability

The symbol error probability after decoding, the usual approximation that a word of $i > t$ errors keeps its $i$ wrong symbols (Proakis & Salehi, Sec. 7.5.2; Sklar, Sec. 8.1.2),

unpack_symbols

Unpack symbols of m bits (1 to 16) into bits, the most significant first; the bits of a symbol above $2^{m}$ are dropped.

word_error_probability

The word error probability of a bounded-distance decoder of a $t$-error-correcting code of $n$ symbols over a memoryless channel of symbol error probability $p_{s}$ (Proakis & Salehi, Sec. 7.5.2),