comnum.ReedSolomonCode#

class comnum.ReedSolomonCode(m, t, *, n=None, first_root=1, root_step=1, poly=None)#

A Reed–Solomon code over GF(2^m) (symbols of m bits) correcting t symbols per word, with systematic encoding, errors-and-erasures decoding (Berlekamp–Massey, Chien search, Forney 1965) and shortening (Lin & Costello 2004, ch. 7).

The generator polynomial has the roots β^b, …, β^(b+2t-1) with β = α^c for the primitive element α of the field of the primitive polynomial poly: first_root is b (1 in the textbooks, 0 in DVB, 112 in CCSDS) and root_step is c (11 in CCSDS). The code of length 2^m - 1 symbols is shortened to n_symbols; a word carries k_symbols = n_symbols - 2t information symbols.

The code works on symbols (encode_symbols, decode_symbols) and on bits, m per symbol, the most significant first. As for every code of the package, n and k count bits (n = m n_symbols, k = m k_symbols): encode and decode take whole blocks of k bits and n LLRs (hard decisions), decode_bits one block of n hard bits with the number of corrections.

Parameters:

  • m (int) – bits per symbol, 2 to 16.

  • t (int) – symbol errors corrected per word.

  • n (int | None) – word length in symbols, n_symbols (2^m - 1 by default, less for a shortened code).

  • first_root (int) – exponent b of the first root of the generator.

  • root_step (int) – exponent c of β = α^c, coprime with 2^m - 1.

  • poly (int | None) – the primitive polynomial of the field, bit i the coefficient of x^i (the conventional one of Lin & Costello, Table 2.7, by default: 0x11D for m = 8).

Raises:

ValueError – for an invalid parameter (the message names it).

Examples

The RS(204, 188) outer code of DVB-T and DVB-S (ETSI EN 300 744 V1.6.1, Sec. 4.3.2; EN 300 421, Sec. 4.4): t = 8, roots λ^0, …, λ^15 over the field of x^8 + x^4 + x^3 + x^2 + 1, shortened from (255, 239):

>>> import comnum, numpy as np
>>> dvb = comnum.ReedSolomonCode(8, 8, n=204, first_root=0)
>>> (dvb.n_symbols, dvb.k_symbols, dvb.t, dvb.n, dvb.k)
(204, 188, 8, 1632, 1504)
>>> msg = np.arange(188) % 256
>>> c = dvb.encode_symbols(msg)
>>> c[[3, 50, 200]] ^= 0x5A
>>> decoded, corrected = dvb.decode_symbols(c)
>>> bool(np.array_equal(decoded, msg)), corrected
(True, 3)

The RS(255, 223) code of CCSDS 131.0-B-5, Sec. 4.2: t = 16 over the field of x^8 + x^7 + x^2 + x + 1 with the roots α^(11 j), j = 112, …, 143:

>>> ccsds = comnum.ReedSolomonCode(8, 16, poly=0x187, first_root=112, root_step=11)
>>> (ccsds.n_symbols, ccsds.k_symbols, round(ccsds.rate, 4))
(255, 223, 0.8745)
>>> g = ccsds.generator
>>> bool(np.array_equal(g, g[::-1]))  # self-reciprocal
True
decode(llr)#

Decode whole blocks of LLRs by their signs (hard decisions); a block whose decoding fails keeps its message bits as received.

Parameters:

llr (array_like) – a multiple of n LLRs (positive for a 0).

Returns:

k bits per block (uint8).

Return type:

numpy.ndarray

Raises:

ValueError – for an invalid parameter or input (the message names it).

Examples

>>> import comnum, numpy as np
>>> code = comnum.ReedSolomonCode(4, 2)
>>> b = comnum.bits(code.k, comnum.Rng(1))
>>> c = code.encode(b)
>>> c[[0, 9]] ^= 1  # two wrong bits, in two symbols
>>> bool(np.array_equal(code.decode(1.0 - 2.0 * c), b))
True
decode_bits(bits)#

Decode one block of hard bits.

Parameters:

bits (array_like) – n received bits.

Returns:

the k message bits and the number of corrected symbols (None for a detected decoding failure).

Return type:

tuple[numpy.ndarray, int | None]

Raises:

ValueError – for an invalid parameter or input (the message names it).

decode_symbols(received, *, erasures=None)#

Decode a word of received symbols, some positions known to be unreliable. The decoder corrects e errors and s erasures whenever 2e + s <= 2t.

Parameters:

  • received (array_like) – the n_symbols received symbols.

  • erasures (array_like, optional) – the erased positions (0 to n_symbols - 1).

Returns:

the k_symbols message symbols and the number of corrected symbols (erasures included), None for a detected decoding failure (the message symbols are then returned as received).

Return type:

tuple[numpy.ndarray, int | None]

Raises:

ValueError – for an invalid parameter or input (the message names it).

encode(bits)#

Encode whole blocks of bits (m per symbol, most significant first).

Parameters:

bits (array_like) – a multiple of k bits.

Returns:

n coded bits per block (uint8).

Return type:

numpy.ndarray

Raises:

ValueError – for an invalid parameter or input (the message names it).

Examples

>>> import comnum
>>> code = comnum.ReedSolomonCode(4, 2)
>>> code.encode(comnum.bits(2 * code.k, comnum.Rng(1))).size
120
encode_symbols(msg)#

The word of a message of symbols: the message, then the 2t parity symbols.

Parameters:

msg (array_like) – k_symbols message symbols, below 2^m.

Returns:

the n_symbols symbols of the word (int64).

Return type:

numpy.ndarray

Raises:

ValueError – for an invalid parameter or input (the message names it).

first_root#

Exponent of the first root of the generator.

Type:

int

generator#

The generator polynomial g(x), lowest degree first (2t + 1 symbols, int64).

Type:

numpy.ndarray

k#

Information bits per word, m k_symbols, as for every code.

Type:

int

k_symbols#

Information symbols per word, n_symbols - 2t.

Type:

int

m#

Bits per symbol.

Type:

int

n#

Coded bits per word, m per symbol (m n_symbols), as for every code.

Type:

int

n_symbols#

Word length in symbols.

Type:

int

poly#

The primitive polynomial of the field, bit i the coefficient of x^i.

Type:

int

rate#

Code rate k / n.

Type:

float

root_step#

Exponent c of β = α^c.

Type:

int

t#

Symbol errors corrected per word.

Type:

int