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);
210 int j, i, degree, kk, foundzeros, cisvalid;
211 int iterations =
floor_i(static_cast<double>(coded_bits.length()) / n);
212 bvec rbin(n), mbin(k);
213 decoded_bits.set_size(iterations*k,
false);
215 GFX r(n + 1, n - 1), c(n + 1, n - 1), m(n + 1, k - 1), S(n + 1, 2*t), Lambda(n + 1),
216 OldLambda(n + 1), T(n + 1), Ohmega(n + 1), One(n + 1, (
char*)
"0");
220 for (i = 0; i < iterations; i++) {
222 rbin = coded_bits.mid(i * n, n);
223 for (j = 0; j < n; j++) {
224 degree =
static_cast<int>(rbin(n - j - 1)) - 1;
226 r[j] =
GF(n + 1, degree);
229 S[0] =
GF(n + 1, -1);
230 for (j = 1; j <= 2*t; j++) {
231 S[j] = r(
GF(n + 1, j));
233 if (S.get_true_degree() >= 1) {
236 Lambda =
GFX(n + 1, (
char*)
"0");
237 T =
GFX(n + 1, (
char*)
"0");
239 Ohmega = Lambda * (S + One);
240 delta = Ohmega[2*kk+1];
242 Lambda = OldLambda + delta * (
GFX(n + 1, (
char*)
"-1 0") * T);
243 if ((delta ==
GF(n + 1, -1)) || (OldLambda.get_true_degree() > kk)) {
244 T =
GFX(n + 1, (
char*)
"-1 -1 0") * T;
247 T = (
GFX(n + 1, (
char*)
"-1 0") * OldLambda) / delta;
252 errorpos.set_size(Lambda.get_true_degree(),
true);
254 for (j = 0; j <= n - 1; j++) {
255 if (Lambda(
GF(n + 1, j)) ==
GF(n + 1, -1)) {
256 errorpos(foundzeros) = (n - j) % n;
258 if (foundzeros >= Lambda.get_true_degree()) {
264 for (j = 0; j < foundzeros; j++) {
265 rbin(n - errorpos(j) - 1) += 1;
268 for (j = 0; j < n; j++) {
269 degree =
static_cast<int>(rbin(n - j - 1)) - 1;
270 c[j] =
GF(n + 1, degree);
273 S[0] =
GF(n + 1, -1);
274 for (j = 1; j <= 2*t; j++) {
275 S[j] = c(
GF(n + 1, j));
277 if (S.get_true_degree() <= 0) {
290 if (c.get_true_degree() > 1) {
292 for (j = 0; j < k; j++)
299 for (j = 0; j <= m.get_true_degree(); j++) {
300 if (m[j] ==
GF(n + 1, 0)) {
307 m =
GFX(n + 1, (
char*)
"-1");
312 m =
GFX(n + 1, (
char*)
"-1");
314 decoded_bits.replace_mid(i*k, mbin);
322 decode(coded_bits, decoded_bits);
331 it_error(
"BCH::decode(): Soft-decision decoding is not implemented");
336 it_error(
"BCH::decode(): Soft-decision decoding is not implemented");