39 BCH::BCH(
int in_n,
int in_k,
int in_t,
const ivec &genpolynom,
bool sys) :
40 n(in_n), k(in_k), t(in_t), systematic(sys)
43 ivec exponents =
zeros_i(n - k + 1);
44 bvec temp =
oct2bin(genpolynom, 0);
45 for (
int i = 0; i < temp.length(); i++) {
46 exponents(i) =
static_cast<int>(temp(temp.length() - i - 1)) - 1;
48 g.
set(n + 1, exponents);
52 n(in_n), t(in_t), systematic(sys)
58 int two_pow_m = 1 << m_tmp;
60 it_assert(two_pow_m == n + 1,
"BCH::BCH(): (in_n + 1) is not a power of 2");
61 it_assert((t > 0) && (2 * t < n),
"BCH::BCH(): in_t must be positive and smaller than n/2");
71 int curr_coset_idx = 0;
72 cyclo_sets(curr_coset_idx) =
zeros_i(1);
83 while ((!found) && (i <= curr_coset_idx)) {
85 while ((!found) && (j < cyclo_sets(i).
length())) {
86 if (cycl_element == cyclo_sets(i)(j)) {
95 while ((found) && (cycl_element <= 2 * t));
99 cyclo_sets(++curr_coset_idx).
set_size(m_tmp);
103 int element_index = 0;
104 cyclo_sets(curr_coset_idx)(element_index) = cycl_element - 1;
107 while ((((cyclo_sets(curr_coset_idx)(element_index) * 2) % n)
108 != cyclo_sets(curr_coset_idx)(0))
109 && (element_index < m_tmp - 1)) {
111 cyclo_sets(curr_coset_idx)(element_index)
112 = (cyclo_sets(curr_coset_idx)(element_index - 1) * 2) % n;
115 if (element_index + 1 < m_tmp - 1) {
116 cyclo_sets(curr_coset_idx).del(element_index + 1, m_tmp - 1);
120 while ((cycl_element <= 2 * t) && (curr_coset_idx <= 2 * t));
130 int max_coset_index = curr_coset_idx;
134 g.
set(two_pow_m, ivec(
"0"));
135 ivec min_poly_exp(2);
138 for (
int i = 1; i <= max_coset_index; i++) {
139 for (
int j = 0; j < cyclo_sets(i).
length(); j++) {
140 min_poly_exp(0) = cyclo_sets(i)(j);
141 g *=
GFX(two_pow_m, min_poly_exp);
153 int iterations =
floor_i(static_cast<double>(uncoded_bits.length()) / k);
157 GFX uncoded_shifted(n + 1, n);
158 coded_bits.set_size(iterations * n,
false);
159 bvec mbit(k), cbit(n);
162 for (i = 0; i < n - k; i++)
163 uncoded_shifted[i] =
GF(n + 1, -1);
165 for (i = 0; i < iterations; i++) {
167 mbit = uncoded_bits.mid(i * k, k);
168 for (j = 0; j < k; j++) {
169 degree =
static_cast<int>(mbit(k - j - 1)) - 1;
173 m[j] =
GF(n + 1, degree);
175 uncoded_shifted[j + n - k] = m[j];
180 r =
modgfx(uncoded_shifted, g);
181 c = uncoded_shifted - r;
189 for (j = 0; j < n; j++) {
190 if (c[j] ==
GF(n + 1, 0)) {
197 coded_bits.replace_mid(i * n, cbit);
204 encode(uncoded_bits, coded_bits);
208 bool BCH::decode(
const bvec &coded_bits, bvec &decoded_message, bvec &cw_isvalid)
210 bool decoderfailure, no_dec_failure;
211 int j, i, degree, kk, foundzeros;
213 int iterations =
floor_i(static_cast<double>(coded_bits.length()) / n);
214 bvec rbin(n), mbin(k);
215 decoded_message.set_size(iterations * k,
false);
216 cw_isvalid.set_length(iterations);
218 GFX r(n + 1, n - 1), c(n + 1, n - 1), m(n + 1, k - 1), S(n + 1, 2 * t), Lambda(n + 1),
219 OldLambda(n + 1), T(n + 1), Omega(n + 1), One(n + 1, (
char*)
"0");
222 no_dec_failure =
true;
223 for (i = 0; i < iterations; i++) {
224 decoderfailure =
false;
226 rbin = coded_bits.mid(i * n, n);
227 for (j = 0; j < n; j++) {
228 degree =
static_cast<int>(rbin(n - j - 1)) - 1;
230 r[j] =
GF(n + 1, degree);
234 for (j = 1; j <= 2 * t; j++) {
235 S[j] = r(
GF(n + 1, j));
237 if (S.get_true_degree() >= 1) {
240 Lambda =
GFX(n + 1, (
char*)
"0");
241 T =
GFX(n + 1, (
char*)
"0");
243 Omega = Lambda * (S + One);
244 delta = Omega[2 * kk + 1];
246 Lambda = OldLambda + delta * (
GFX(n + 1, (
char*)
"-1 0") * T);
247 if ((delta ==
GF(n + 1, -1)) || (OldLambda.get_true_degree() > kk)) {
248 T =
GFX(n + 1, (
char*)
"-1 -1 0") * T;
251 T = (
GFX(n + 1, (
char*)
"-1 0") * OldLambda) / delta;
256 errorpos.set_size(Lambda.get_true_degree());
258 for (j = 0; j <= n - 1; j++) {
259 if (Lambda(
GF(n + 1, j)) ==
GF(n + 1, -1)) {
260 errorpos(foundzeros) = (n - j) % n;
262 if (foundzeros >= Lambda.get_true_degree()) {
267 if (foundzeros != Lambda.get_true_degree()) {
268 decoderfailure =
true;
272 for (j = 0; j < foundzeros; j++) {
273 rbin(n - errorpos(j) - 1) += 1;
276 for (j = 0; j < n; j++) {
277 degree =
static_cast<int>(rbin(n - j - 1)) - 1;
278 c[j] =
GF(n + 1, degree);
282 for (j = 1; j <= 2 * t; j++) {
283 S[j] = c(
GF(n + 1, j));
285 if (S.get_true_degree() <= 0) {
286 decoderfailure =
false;
289 decoderfailure =
true;
295 decoderfailure =
false;
298 if (decoderfailure ==
false) {
299 if (c.get_true_degree() > 1) {
301 for (j = 0; j < k; j++)
308 for (j = 0; j <= m.get_true_degree(); j++) {
309 if (m[j] ==
GF(n + 1, 0)) {
316 m =
GFX(n + 1, (
char*)
"-1");
324 mbin = coded_bits.mid(i * n, k);
329 no_dec_failure =
false;
331 decoded_message.replace_mid(i * k, mbin);
332 cw_isvalid(i) = (!decoderfailure);
334 return no_dec_failure;
340 if (!
decode(coded_bits, decoded_bits, cw_isvalid)) {
341 for (
int i = 0; i < cw_isvalid.length(); i++) {
342 if (!cw_isvalid(i)) {
343 decoded_bits.replace_mid(i * k,
zeros_b(k));
352 decode(coded_bits, decoded_bits);
361 it_error(
"BCH::decode(): Soft-decision decoding is not implemented");
366 it_error(
"BCH::decode(): Soft-decision decoding is not implemented");
ITPP_EXPORT ivec zeros_i(int size)
A Int vector of zeros.
virtual void encode(const bvec &uncoded_bits, bvec &coded_bits)
Encode a bvec of indata.
ITPP_EXPORT bvec zeros_b(int size)
A Binary vector of zeros.
BCH(int in_n, int in_k, int in_t, const ivec &genpolynom, bool sys=false)
Initialize a (n,k)-code that can correct t errors.
#define it_assert(t, s)
Abort if t is not true.
int length(const Vec< T > &v)
Length of vector.
virtual bool decode(const bvec &coded_bits, bvec &decoded_message, bvec &cw_isvalid)
Decode the BCH code bits. Return false if there has been any decoding failure.
Definition of Array class (container)
int floor_i(double x)
The nearest smaller integer.
void set_size(int n, bool copy=false)
Resizing an Array.
int get_true_degree() const
Return true degree of GF(q)[x].
Definitions of special vectors and matrices.
GFX modgfx(const GFX &a, const GFX &b)
Modulo function of two GFX (local help function)
Polynomials over GF(q)[x], where q=2^m, m=1,...,16.
#define it_error(s)
Abort unconditionally.
GFX divgfx(const GFX &c, const GFX &g)
Division of two GFX (local help function)
Definition of a BCH encoder/decoder class.
ITPP_EXPORT bvec oct2bin(const ivec &octalindex, short keepzeros=0)
Convert ivec of octal form to bvec.
int int2bits(int n)
Calculate the number of bits needed to represent an integer n.
int length() const
Returns the number of data elements in the array object.
void set(int qvalue, const char *invalues)
Set the GF(q)[x] polynomial.