GNU Radio's DVBS2RX Package
bch.h
Go to the documentation of this file.
1/* -*- c++ -*- */
2/*
3 * Copyright (c) 2023 Igor Freire.
4 *
5 * This file is part of gr-dvbs2rx.
6 *
7 * SPDX-License-Identifier: GPL-3.0-or-later
8 */
9#ifndef INCLUDED_DVBS2RX_BCH_H
10#define INCLUDED_DVBS2RX_BCH_H
11
12#include "gf.h"
13#include "gf_util.h"
15#include <array>
16#include <cstdint>
17
18namespace gr {
19namespace dvbs2rx {
20
21/**
22 * @brief BCH coder/decoder.
23 *
24 * @tparam T Base type for the Galois Field elements.
25 * @tparam P Base type for the GF(2) generator polynomial.
26 */
27template <typename T, typename P>
29{
30private:
31 const galois_field<T>* m_gf; // Galois field
32 uint8_t m_t; // error correction capability
33 gf2_poly<P> m_g; // generator polynomial
34 uint32_t m_n; // codeword length
35 uint32_t m_s; // code shortening
36 uint32_t m_k; // message length
37 uint32_t m_parity; // number of parity bits
38 uint32_t m_n_bytes; // codeword length in bytes
39 uint32_t m_k_bytes; // message length in bytes
40 uint32_t m_parity_bytes; // number of parity bytes
41 T m_msg_mask; // mask used to enforce k bits per message
42 std::array<P, 256> m_gen_poly_rem_lut; // Remainder LUT for the generator polynomial
43 bool m_gen_poly_lut_generated; // Whether the generator polynomial remainder LUT has
44 // been generated already
45 std::vector<T> m_quadratic_poly_lut; // LUT to solve quadratic error-loc polynomials
46
47public:
48 /**
49 * @brief Construct a new BCH coder/decoder object
50 *
51 * @param gf Reference Galois field.
52 * @param t Target error correction capability.
53 * @param n Target codeword length in bits.
54 * @note The default codeword length is n=(2^m - 1), where m is the dimension of the
55 * GF(2^m) Galois Field, so the codeword length is inferred from the gf parameter.
56 * Alternatively, a codeword length lower than (2^m - 1) and greater than the
57 * generator polynomial's degree can be specified through parameter n. In this case,
58 * the constructor attempts to construct a shortened (n - s, k - s) BCH code, with
59 * parameter s equal to (2^m - 1) - n.
60 */
61 bch_codec(const galois_field<T>* const gf, uint8_t t, uint32_t n = 0);
62
63 /**
64 * @brief Encode an input message.
65 *
66 * @param msg k-bit input message.
67 * @return T Resulting codeword.
68 * @note The parity digits are placed at the least significant (lower order) n - k bit
69 * positions, whereas the original (systematic) message is placed at the most
70 * significant k bit positions, from bit n-1 to bit n-k.
71 * @note Only use this implementation if the message type T can hold n bits.
72 * Otherwise, use the implementation based on an array of bytes.
73 */
74 T encode(const T& msg) const;
75
76 /**
77 * @overload
78 * @param msg Pointer to the input message with k/8 bytes.
79 * @param codeword Pointer to the codeword buffer with space for n/8 bytes.
80 * @note Since the code is systematic, the first k/8 bytes of the resulting codeword
81 * hold the original message, whereas the remaining bytes contain the parity digits. A
82 * serializer should read the codeword from the first byte to the last byte to
83 * preserve the order.
84 * @note The caller should make sure the pointers point to memory regions with enough
85 * data and space.
86 * @note This bytes-based encoding is only supported when n and k are multiples of 8.
87 */
88 void encode(u8_cptr_t msg, u8_ptr_t codeword) const;
89
90 /**
91 * @brief Compute the syndrome of a received codeword.
92 *
93 * @param codeword Received codeword.
94 * @return std::vector<T> Syndrome as a vector with 2t GF(2^m) elements or an empty
95 * vector when the codeword is error-free.
96 * @note An empty vector is returned for an error-free codeword for CPU efficiency.
97 * The caller should check the size of the returned vector to determine whether the
98 * codeword is error-free or not.
99 */
100 std::vector<T> syndrome(const T& codeword) const;
101
102 /**
103 * @overload
104 * @param codeword Pointer to u8 array with the received codeword.
105 */
106 std::vector<T> syndrome(u8_cptr_t codeword) const;
107
108 /**
109 * @brief Compute the error-location polynomial.
110 *
111 * The error-location polynomial is a polynomial over GF(2^m) whose roots indicate the
112 * location of bit errors. The implementation for finding this polynomial is based on
113 * the simplified Berlekamp's iterative algorithm, which works for binary BCH codes.
114 *
115 * @param syndrome Syndrome vector with 2t elements.
116 * @return gf2m_poly<T> Error-location polynomial, a polynomial over GF(2^m).
117 */
118 gf2m_poly<T> err_loc_polynomial(const std::vector<T>& syndrome) const;
119
120 /**
121 * @brief Compute the error-location numbers.
122 *
123 * The error-location numbers are the numbers from GF(2^m) corresponding to the
124 * reciprocal of the roots of the error-location polynomial. An error-location number
125 * alpha^j indicates there is an error in the j-th bit of the received codeword.
126 *
127 * @param sigma Error location polynomial.
128 * @return std::vector<T> Error location numbers, a vector of elements from GF(2^m).
129 */
130 std::vector<T> err_loc_numbers(const gf2m_poly<T>& sigma) const;
131
132 /**
133 * @brief Decode an input codeword.
134 *
135 * @param codeword n-bit input codeword.
136 * @return T Decoded message.
137 */
138 T decode(T codeword) const;
139
140 /**
141 * @overload
142 * @param codeword Pointer to the received codeword with n/8 bytes.
143 * @param decoded_msg Pointer to the decoded message buffer with space for k/8 bytes.
144 * @return int Number of bit errors corrected by the decoder. Set to 0 when the
145 * message is error-free and -1 when the decoding fails to correct all errors such
146 * that the decoded message has residual bit errors.
147 * @note The caller should make sure the pointers point to memory regions with enough
148 * data and space.
149 * @note This bytes-based decoding is only supported when n and k are multiples of 8.
150 */
151 int decode(u8_cptr_t codeword, u8_ptr_t decoded_msg) const;
152
153 /**
154 * @brief Get the generator polynomial object.
155 *
156 * @return const gf2_poly<P>& Generator polynomial.
157 */
158 const gf2_poly<P>& get_gen_poly() const { return m_g; };
159
160 /**
161 * @brief Get the codeword length n.
162 *
163 * @return uint16_t Codeword length.
164 */
165 uint16_t get_n() const { return m_n; };
166
167 /**
168 * @brief Get the message length k.
169 *
170 * @return uint16_t Message length.
171 */
172 uint16_t get_k() const { return m_k; };
173};
174
175} // namespace dvbs2rx
176} // namespace gr
177#endif
BCH coder/decoder.
Definition bch.h:29
int decode(u8_cptr_t codeword, u8_ptr_t decoded_msg) const
T encode(const T &msg) const
Encode an input message.
T decode(T codeword) const
Decode an input codeword.
gf2m_poly< T > err_loc_polynomial(const std::vector< T > &syndrome) const
Compute the error-location polynomial.
std::vector< T > syndrome(u8_cptr_t codeword) const
uint16_t get_k() const
Get the message length k.
Definition bch.h:172
void encode(u8_cptr_t msg, u8_ptr_t codeword) const
std::vector< T > err_loc_numbers(const gf2m_poly< T > &sigma) const
Compute the error-location numbers.
std::vector< T > syndrome(const T &codeword) const
Compute the syndrome of a received codeword.
const gf2_poly< P > & get_gen_poly() const
Get the generator polynomial object.
Definition bch.h:158
uint16_t get_n() const
Get the codeword length n.
Definition bch.h:165
bch_codec(const galois_field< T > *const gf, uint8_t t, uint32_t n=0)
Construct a new BCH coder/decoder object.
Galois Field GF(2^m).
Definition gf.h:66
Polynomial over GF(2).
Definition gf.h:203
Polynomial over GF(2^m).
Definition gf.h:349
#define DVBS2RX_API
Definition include/gnuradio/dvbs2rx/api.h:19
unsigned char * u8_ptr_t
Definition gf_util.h:23
const unsigned char * u8_cptr_t
Definition gf_util.h:24
Fixed-length double-ended queue with contiguous volk-aligned elements.
Definition gr_bch.h:22