46 for (i = 0; i <= degree - 1; i += 2) {
56 m(in_m), t(in_t), b(in_b), systematic(sys)
61 it_assert( (
b >= 0) && (
b <
n),
"Reed_Solomon::Reed_Solomon: narrow-sense parameter restricted to 0 <= b <= n.");
62 GFX x(
q, (
char *)
"-1 0");
64 g.
set(
q, (
char *)
"0");
65 for (
int i = 1; i <= 2 *
t; i++) {
66 alphapow(0) =
b + i - 1;
67 g *= (x -
GFX(
q, alphapow));
73 int i, j, iterations =
floor_i(static_cast<double>(uncoded_bits.length())
77 GFX uncoded_shifted(
n + 1,
n);
79 bvec mbit(
k * m), cbit(m);
81 coded_bits.set_size(iterations *
n * m,
false);
84 for (i = 0; i <
n -
k; i++)
85 uncoded_shifted[i] =
GF(
n + 1, -1);
87 for (i = 0; i < iterations; i++) {
89 for (j = 0; j <
k; j++) {
90 mpow.
set(
q, uncoded_bits.mid((i * m * k) + (j * m), m));
94 uncoded_shifted[j +
n -
k] = mx[j];
100 for (j = k; j <
n; j++) {
107 for (j = 0; j <
n; j++) {
108 cbit = cx[j].get_vectorspace();
109 coded_bits.replace_mid((i * n * m) + (j * m), cbit);
117 encode(uncoded_bits, coded_bits);
121 bool Reed_Solomon::decode(
const bvec &coded_bits,
const ivec &erasure_positions, bvec &decoded_message, bvec &cw_isvalid)
123 bool decoderfailure, no_dec_failure;
124 int j, i, kk, l, L, foundzeros, iterations =
floor_i(static_cast<double>(coded_bits.length()) / (
n *
m));
126 decoded_message.set_size(iterations * k * m,
false);
127 cw_isvalid.set_length(iterations);
129 GFX rx(
q,
n - 1), cx(
q,
n - 1), mx(
q, k - 1), ex(
q,
n - 1), S(
q, 2 *
t), Xi(
q, 2 *
t), Gamma(
q), Lambda(
q),
130 Psiprime(
q), OldLambda(
q), T(
q), Omega(
q);
131 GFX dummy(
q), One(
q, (
char*)
"0"), Omegatemp(
q);
132 GF delta(
q), tempsum(
q), rtemp(
q), temp(
q), Xk(
q), Xkinv(
q);
135 if ( erasure_positions.length() ) {
136 it_assert(
max(erasure_positions) < iterations*
n,
"Reed_Solomon::decode: erasure position is invalid.");
139 no_dec_failure =
true;
140 for (i = 0; i < iterations; i++) {
141 decoderfailure =
false;
143 for (j = 0; j <
n; j++) {
144 rtemp.set(
q, coded_bits.mid(i * n * m + j * m, m));
150 ivec alphapow = -
ones_i(2);
152 for (j = 0; j < erasure_positions.length(); j++) {
153 rx[erasure_positions(j)] = rtemp;
154 alphapow(1) = erasure_positions(j);
155 Gamma *= (One -
GFX(
q, alphapow));
159 for (j = 1; j <= 2 *
t; j++) {
160 S[j] = rx(
GF(
q,
b + j - 1));
163 Xi = Gamma * (One + S) - One;
165 if (Xi.get_true_degree() >= 1) {
170 T =
GFX(
q, (
char*)
"-1 0");
174 for (l = 1; l <= L; l++) {
175 tempsum += Lambda[l] * Xi[kk - l];
177 delta = Xi[kk] - tempsum;
178 if (delta !=
GF(
q, -1)) {
183 T = OldLambda / delta;
186 T =
GFX(
q, (
char*)
"-1 0") * T;
189 errorpos.set_size(Lambda.get_true_degree());
191 for (j =
q - 2; j >= 0; j--) {
192 if (Lambda(
GF(
q, j)) ==
GF(
q, -1)) {
193 errorpos(foundzeros) = (n - j) % n;
195 if (foundzeros >= Lambda.get_true_degree()) {
200 if (foundzeros != Lambda.get_true_degree()) {
201 decoderfailure =
true;
206 Omegatemp = Lambda * (One + Xi);
207 for (j = 0; j <= 2 *
t; j++) {
208 Omega[j] = Omegatemp[j];
212 errorpos =
concat(errorpos, erasure_positions);
214 for (j = 0; j < errorpos.length(); j++) {
215 Xk =
GF(
q, errorpos(j));
216 Xkinv =
GF(
q, 0) / Xk;
219 ex[errorpos(j)] = (Xk * Omega(Xkinv)) / Psiprime(Xkinv);
221 int correction_exp = ( errorpos(j)*(1-
b) ) %
n;
222 ex[errorpos(j)] *=
GF(
q, correction_exp + ( (correction_exp < 0) ? n : 0 ));
231 for (j = 1; j <= 2 *
t; j++) {
232 S[j] = cx(
GF(
q,
b + j - 1));
234 if (S.get_true_degree() >= 1) {
235 decoderfailure =
true;
241 decoderfailure =
false;
245 if (decoderfailure ==
false) {
246 if (cx.get_true_degree() >= 1) {
248 for (j = 0; j <
k; j++) {
255 for (j = 0; j <= mx.get_true_degree(); j++) {
256 mbit.replace_mid(j * m, mx[j].get_vectorspace());
265 mbit = coded_bits.mid(i * n * m, k * m);
270 no_dec_failure =
false;
272 decoded_message.replace_mid(i * m * k, mbit);
273 cw_isvalid(i) = (!decoderfailure);
275 return no_dec_failure;
281 return decode(coded_bits, erasures, decoded_message, cw_isvalid);
288 if (!
decode(coded_bits, erasures, decoded_bits, cw_isvalid)) {
289 for (
int i = 0; i < cw_isvalid.length(); i++) {
290 if (!cw_isvalid(i)) {
291 decoded_bits.replace_mid(i *
k *
m,
zeros_b(
k * m));
300 decode(coded_bits, decoded_bits);
308 it_error(
"Reed_Solomon::decode(): Soft-decision decoding not implemented");
313 it_error(
"Reed_Solomon::decode(): Soft-decision decoding not implemented");