10#ifndef INCLUDED_DVBS2RX_GF_H
11#define INCLUDED_DVBS2RX_GF_H
14#include <unordered_map>
44 return x & (
static_cast<T
>(1) << i_bit);
69 const uint32_t m_two_to_m_minus_one;
70 std::vector<T> m_table;
71 std::vector<T> m_table_nonzero;
72 std::unordered_map<T, uint32_t> m_exp_table;
88 T
operator[](uint32_t index)
const {
return m_table[index]; }
99 T
get_alpha_i(uint32_t i)
const {
return m_table_nonzero[i % m_two_to_m_minus_one]; }
110 uint32_t
get_exponent(
const T& beta)
const {
return m_exp_table.at(beta); }
171 uint8_t
get_m()
const {
return m_m; };
182 return (
sizeof(T) * 8 - 1);
205 static constexpr int m_max_degree = get_max_gf2_poly_degree<T>();
274 bool is_zero()
const {
return m_degree == -1; }
293template <
typename Ta,
typename Tb>
298 throw std::runtime_error(
"Remainder of division by a zero polynomial");
304 int b_degree = b.
degree();
307 for (
int i = a.
degree(); i >= b_degree; i--) {
309 remainder ^= b_coefs << (i - b_degree);
314template <
typename Ta,
typename Tb>
317 static_assert(
sizeof(Tb) >=
sizeof(Ta),
318 "Divisor type must be larger or equal than dividend type");
321template <
typename Tb>
324 static_assert(
sizeof(Tb) * 8 >=
bitset256_t().size(),
325 "Divisor type must be larger or equal than dividend type");
328template <
typename Ta>
331 static_assert(
bitset256_t().size() >=
sizeof(Ta) * 8,
332 "Divisor type must be larger or equal than dividend type");
352 std::vector<T> m_poly;
355 std::vector<uint32_t> m_nonzero_coef_idx;
357 std::vector<uint32_t> m_nonzero_coef_exp;
359 size_t m_n_nonzero_coef;
379 void set_coef_exponents();
396 template <
typename Y>
402 m_poly.push_back((*gf)[1]);
404 m_poly.push_back((*gf)[0]);
408 set_coef_exponents();
502 uint32_t max_roots = std::numeric_limits<uint32_t>::max())
const;
509 const std::vector<T>&
get_poly()
const {
return m_poly; }
Galois Field GF(2^m).
Definition gf.h:66
gf2_poly< T > get_min_poly(const T &beta) const
Compute the minimal polynomial associated with element beta.
uint8_t get_m() const
Get the dimension m of the GF(2^m) field.
Definition gf.h:171
T inverse(const T &beta) const
Get the inverse beta^-1 from a GF(2^m) element beta.
T divide(const T &a, const T &b) const
Divide two elements from GF(2^m).
T get_alpha_i(uint32_t i) const
Get the i-th power of the primitive element (alpha^i).
Definition gf.h:99
T multiply(const T &a, const T &b) const
Multiply two elements from GF(2^m).
std::set< T > get_conjugates(const T &beta) const
Get the conjugates of element beta.
T inverse_by_exp(uint32_t i) const
Get the inverse from a GF(2^m) element alpha^i given by its exponent i.
T operator[](uint32_t index) const
Get the GF(2^m) element at a given index on the elements table.
Definition gf.h:88
galois_field(const gf2_poly< T > &prim_poly)
Construct a new Galois field object.
uint32_t get_exponent(const T &beta) const
Get the exponent i of a given element beta = alpha^i.
Definition gf.h:110
Polynomial over GF(2).
Definition gf.h:203
gf2_poly< T > operator*(bool x) const
Multiplication by a GF(2) scalar.
Definition gf.h:236
gf2_poly< T > operator*(const gf2_poly< T > &x) const
Multiplication by another GF(2) polynomial.
int degree() const
Get the polynomial degree.
Definition gf.h:267
bool operator==(const gf2_poly< T > &x) const
Equal comparator.
Definition gf.h:252
const T & get_poly() const
Get the polynomial coefficients.
Definition gf.h:259
gf2_poly(const T &coefs)
Construct a new GF(2) polynomial object.
gf2_poly< T > operator+(const gf2_poly< T > &x) const
GF(2) polynomial addition.
Definition gf.h:228
bool is_zero() const
Test if the polynomial is the zero polynomial.
Definition gf.h:274
Polynomial over GF(2^m).
Definition gf.h:349
T eval_by_exp(uint32_t i) const
Evaluate the polynomial for an element alpha^i given by its exponent i.
const std::vector< T > & get_poly() const
Get the polynomial coefficients.
Definition gf.h:509
int degree() const
Get the polynomial degree.
Definition gf.h:517
gf2m_poly< T > operator*(const gf2m_poly< T > &x) const
Multiplication by another GF(2^m) polynomial.
gf2m_poly< T > operator*(T x) const
Multiplication by a scalar.
gf2m_poly(const galois_field< T > *const gf, std::vector< T > &&coefs)
Construct a new polynomial over GF(2^m).
gf2_poly< T > to_gf2_poly() const
Convert the polynomial to a GF(2) polynomial.
T eval(T x) const
Evaluate the polynomial for a given GF(2^m) element.
gf2m_poly(const galois_field< T > *const gf, const gf2_poly< Y > &gf2_poly)
Construct a polynomial over GF(2^m) from a polynomial over GF(2).
Definition gf.h:397
T operator[](uint32_t index) const
Access a polynomial coefficient.
Definition gf.h:449
gf2m_poly< T > operator+(const gf2m_poly< T > &x) const
GF(2^m) polynomial addition.
bool operator==(const gf2m_poly< T > &x) const
Equal comparator.
Definition gf.h:441
std::vector< uint32_t > search_roots_in_exp_range(uint32_t i_start, uint32_t i_end, uint32_t max_roots=std::numeric_limits< uint32_t >::max()) const
Search roots by evaluating the polynomial for elements in a given range.
#define DVBS2RX_API
Definition include/gnuradio/dvbs2rx/api.h:19
gf2_poly< Tb > operator%(const gf2_poly< Ta > a, const gf2_poly< Tb > b)
Compute the remainder of the division between two GF(2) polynomials.
Definition gf.h:294
bool is_bit_set(const T &x, int i_bit)
Test if bit is set.
Definition gf.h:42
void check_rem_types(const gf2_poly< Ta > a, const gf2_poly< Tb > b)
Definition gf.h:315
gf2_poly< uint64_t > gf2_poly_u64
Definition gf.h:533
constexpr size_t get_max_gf2_poly_degree()
Get the maximum degree a GF2 polynomial can have with type T.
Definition gf.h:180
constexpr size_t get_max_gf2_poly_degree< bitset256_t >()
Definition gf.h:189
gf2_poly< bitset256_t > gf2_poly_b256
Definition gf.h:534
gf2_poly< uint32_t > gf2_poly_u32
Definition gf.h:532
std::bitset< 256 > bitset256_t
Definition gf.h:26
gf2_poly< uint16_t > gf2_poly_u16
Definition gf.h:531
Fixed-length double-ended queue with contiguous volk-aligned elements.
Definition gr_bch.h:22