00001 00029 #ifndef GALOIS_H 00030 #define GALOIS_H 00031 00032 #include <itpp/base/vec.h> 00033 #include <itpp/base/array.h> 00034 #include <itpp/base/binary.h> 00035 #include <itpp/base/converters.h> 00036 00037 00038 namespace itpp 00039 { 00040 00073 class GF 00074 { 00075 public: 00077 GF() { m = 0; } 00079 GF(int qvalue) { 00080 m = 0; 00081 if (qvalue == 0) // qvalue==0 gives the zeroth element 00082 value = -1; 00083 else set_size(qvalue); 00084 } 00086 GF(int qvalue, int inexp) { m = 0; set(qvalue, inexp); } 00088 GF(const GF &ingf) { m = ingf.m; value = ingf.value; } 00089 00091 void set(int qvalue, int inexp) { 00092 set_size(qvalue); 00093 it_assert_debug(inexp >= -1 && inexp < qvalue - 1, "GF::set, out of range"); 00094 value = inexp; 00095 } 00101 void set(int qvalue, const bvec &vectorspace); 00103 void set_size(int qvalue); 00105 int get_size() const { return ((m != 0) ? q[m] : 0); } 00111 bvec get_vectorspace() const; 00113 int get_value() const; 00115 int operator==(const GF &ingf) const; 00117 int operator!=(const GF &ingf) const; 00118 00120 void operator=(const GF &ingf); 00122 void operator=(const int inexp); 00124 void operator+=(const GF &ingf); 00126 GF operator+(const GF &ingf) const; 00128 void operator-=(const GF &ingf); 00130 GF operator-(const GF &ingf) const; 00132 void operator*=(const GF &ingf); 00134 GF operator*(const GF &ingf) const; 00136 void operator/=(const GF &ingf); 00138 GF operator/(const GF &ingf) const; 00140 friend std::ostream &operator<<(std::ostream &os, const GF &ingf); 00141 protected: 00142 private: 00143 char m; 00144 int value; 00145 static Array<Array<int> > alphapow, logalpha; 00146 static ivec q; 00147 }; 00148 00149 class GFX; 00150 00152 GFX operator*(const GF &ingf, const GFX &ingfx); 00154 GFX operator*(const GFX &ingfx, const GF &ingf); 00156 GFX operator/(const GFX &ingfx, const GF &ingf); 00157 00161 class GFX 00162 { 00163 public: 00165 GFX(); 00167 GFX(int qvalue); 00169 GFX(int qvalue, int indegree); 00171 GFX(int qvalue, const ivec &invalues); 00173 GFX(int qvalue, char *invalues); 00175 GFX(int qvalue, std::string invalues); 00177 GFX(const GFX &ingfx); 00179 int get_size() const; 00181 int get_degree() const; 00185 void set_degree(int indegree, bool copy = false); 00187 int get_true_degree() const; 00189 void set(int qvalue, const char *invalues); 00191 void set(int qvalue, const std::string invalues); 00193 void set(int qvalue, const ivec &invalues); 00195 void clear(); 00197 GF operator[](int index) const { 00198 it_assert_debug(index<=degree, "GFX::op[], out of range"); 00199 return coeffs(index); 00200 } 00202 GF &operator[](int index) { 00203 it_assert_debug(index<=degree, "GFX::op[], out of range"); 00204 return coeffs(index); 00205 } 00207 void operator=(const GFX &ingfx); 00209 void operator+=(const GFX &ingfx); 00211 GFX operator+(const GFX &ingfx) const; 00213 void operator-=(const GFX &ingfx); 00215 GFX operator-(const GFX &ingfx) const; 00217 void operator*=(const GFX &ingfx); 00219 GFX operator*(const GFX &ingfx) const; 00221 GF operator()(const GF &ingf); 00223 friend GFX operator*(const GF &ingf, const GFX &ingfx); 00225 friend GFX operator*(const GFX &ingfx, const GF &ingf); 00227 friend GFX operator/(const GFX &ingfx, const GF &ingf); 00228 00230 friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx); 00231 protected: 00232 private: 00233 int degree, q; 00234 Array<GF> coeffs; 00235 }; 00236 00237 //-------------- Help Functions ------------------ 00244 GFX divgfx(const GFX &c, const GFX &g); 00245 00250 GFX modgfx(const GFX &a, const GFX &b); 00251 00252 00253 // --------------- Inlines ------------------------ 00254 // --------------- class GF ----------------------- 00255 00256 inline void GF::set(int qvalue, const bvec &vectorspace) 00257 { 00258 set_size(qvalue); 00259 it_assert_debug(vectorspace.length() == m, "GF::set, out of range"); 00260 value = logalpha(m)(bin2dec(vectorspace)); 00261 } 00262 00263 inline bvec GF::get_vectorspace() const 00264 { 00265 bvec temp(m); 00266 if (value == -1) 00267 temp = dec2bin(m, 0); 00268 else 00269 temp = dec2bin(m, alphapow(m)(value)); 00270 return temp; 00271 } 00272 00273 inline int GF::get_value() const 00274 { 00275 return value; 00276 } 00277 00278 inline int GF::operator==(const GF &ingf) const 00279 { 00280 if (value == -1 && ingf.value == -1) 00281 return true; 00282 if (m == ingf.m && value == ingf.value) 00283 return true; 00284 else 00285 return false; 00286 } 00287 00288 inline int GF::operator!=(const GF &ingf) const 00289 { 00290 GF tmp(*this); 00291 return !(tmp == ingf); 00292 } 00293 00294 inline void GF::operator=(const GF &ingf) 00295 { 00296 m = ingf.m; 00297 value = ingf.value; 00298 } 00299 00300 inline void GF::operator=(const int inexp) 00301 { 00302 it_assert_debug(m > 0 && inexp >= -1 && inexp < (q[m] - 1), "GF::op=, out of range"); 00303 value = inexp; 00304 } 00305 00306 inline void GF::operator+=(const GF &ingf) 00307 { 00308 if (value == -1) { 00309 value = ingf.value; 00310 m = ingf.m; 00311 } 00312 else if (ingf.value != -1) { 00313 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00314 value = logalpha(m)(alphapow(m)(value) ^ alphapow(m)(ingf.value)); 00315 } 00316 } 00317 00318 inline GF GF::operator+(const GF &ingf) const 00319 { 00320 GF tmp(*this); 00321 tmp += ingf; 00322 return tmp; 00323 } 00324 00325 inline void GF::operator-=(const GF &ingf) 00326 { 00327 (*this) += ingf; 00328 } 00329 00330 inline GF GF::operator-(const GF &ingf) const 00331 { 00332 GF tmp(*this); 00333 tmp -= ingf; 00334 return tmp; 00335 } 00336 00337 inline void GF::operator*=(const GF &ingf) 00338 { 00339 if (value == -1 || ingf.value == -1) 00340 value = -1; 00341 else { 00342 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00343 value = (value + ingf.value) % (q[m] - 1); 00344 } 00345 } 00346 00347 inline GF GF::operator*(const GF &ingf) const 00348 { 00349 GF tmp(*this); 00350 tmp *= ingf; 00351 return tmp; 00352 } 00353 00354 inline void GF::operator/=(const GF &ingf) 00355 { 00356 it_assert(ingf.value != -1, "GF::operator/: division by zero element"); // no division by the zeroth element 00357 if (value == -1) 00358 value = -1; 00359 else { 00360 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00361 value = (value - ingf.value + q[m] - 1) % (q[m] - 1); 00362 } 00363 } 00364 00365 inline GF GF::operator/(const GF &ingf) const 00366 { 00367 GF tmp(*this); 00368 tmp /= ingf; 00369 return tmp; 00370 } 00371 00372 // ------------------ class GFX -------------------- 00373 inline GFX::GFX() 00374 { 00375 degree = -1; 00376 q = 0; 00377 } 00378 00379 inline GFX::GFX(int qvalue) 00380 { 00381 it_assert_debug(qvalue >= 0, "GFX::GFX, out of range"); 00382 q = qvalue; 00383 } 00384 00385 inline void GFX::set(int qvalue, const ivec &invalues) 00386 { 00387 it_assert_debug(qvalue > 0, "GFX::set, out of range"); 00388 degree = invalues.size() - 1; 00389 coeffs.set_size(degree + 1, false); 00390 for (int i = 0;i < degree + 1;i++) 00391 coeffs(i).set(qvalue, invalues(i)); 00392 q = qvalue; 00393 } 00394 00395 inline void GFX::set(int qvalue, const char *invalues) 00396 { 00397 set(qvalue, ivec(invalues)); 00398 } 00399 00400 inline void GFX::set(int qvalue, const std::string invalues) 00401 { 00402 set(qvalue, invalues.c_str()); 00403 } 00404 00405 inline GFX::GFX(int qvalue, int indegree) 00406 { 00407 it_assert_debug(qvalue > 0 && indegree >= 0, "GFX::GFX, out of range"); 00408 q = qvalue; 00409 coeffs.set_size(indegree + 1, false); 00410 degree = indegree; 00411 for (int i = 0;i < degree + 1;i++) 00412 coeffs(i).set(q, -1); 00413 } 00414 inline GFX::GFX(int qvalue, const ivec &invalues) 00415 { 00416 set(qvalue, invalues); 00417 } 00418 00419 inline GFX::GFX(int qvalue, char *invalues) 00420 { 00421 set(qvalue, invalues); 00422 } 00423 00424 inline GFX::GFX(int qvalue, std::string invalues) 00425 { 00426 set(qvalue, invalues.c_str()); 00427 } 00428 00429 inline GFX::GFX(const GFX &ingfx) 00430 { 00431 degree = ingfx.degree; 00432 coeffs = ingfx.coeffs; 00433 q = ingfx.q; 00434 } 00435 00436 inline int GFX::get_size() const 00437 { 00438 return q; 00439 } 00440 00441 inline int GFX::get_degree() const 00442 { 00443 return degree; 00444 } 00445 00446 inline void GFX::set_degree(int indegree, bool copy) 00447 { 00448 it_assert_debug(indegree >= -1, "GFX::set_degree, out of range"); 00449 coeffs.set_size(indegree + 1, copy); 00450 degree = indegree; 00451 } 00452 00453 inline int GFX::get_true_degree() const 00454 { 00455 int i = degree; 00456 while (coeffs(i).get_value() == -1) { 00457 i--; 00458 if (i == -1) 00459 break; 00460 } 00461 return i; 00462 } 00463 00464 inline void GFX::clear() 00465 { 00466 it_assert_debug(degree >= 0 && q > 0, "GFX::clear, not set"); 00467 for (int i = 0;i < degree + 1;i++) 00468 coeffs(i).set(q, -1); 00469 } 00470 00471 inline void GFX::operator=(const GFX &ingfx) 00472 { 00473 degree = ingfx.degree; 00474 coeffs = ingfx.coeffs; 00475 q = ingfx.q; 00476 } 00477 00478 inline void GFX::operator+=(const GFX &ingfx) 00479 { 00480 it_assert_debug(q == ingfx.q, "GFX::op+=, not same field"); 00481 if (ingfx.degree > degree) { 00482 coeffs.set_size(ingfx.degree + 1, true); 00483 // set new coefficients to the zeroth element 00484 for (int j = degree + 1; j < coeffs.size(); j++) { coeffs(j).set(q, -1); } 00485 degree = ingfx.degree; 00486 } 00487 for (int i = 0;i < ingfx.degree + 1;i++) { coeffs(i) += ingfx.coeffs(i); } 00488 } 00489 00490 inline GFX GFX::operator+(const GFX &ingfx) const 00491 { 00492 GFX tmp(*this); 00493 tmp += ingfx; 00494 return tmp; 00495 } 00496 00497 inline void GFX::operator-=(const GFX &ingfx) 00498 { 00499 (*this) += ingfx; 00500 } 00501 00502 inline GFX GFX::operator-(const GFX &ingfx) const 00503 { 00504 GFX tmp(*this); 00505 tmp -= ingfx; 00506 return tmp; 00507 } 00508 00509 inline void GFX::operator*=(const GFX &ingfx) 00510 { 00511 it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field"); 00512 int i, j; 00513 Array<GF> tempcoeffs = coeffs; 00514 coeffs.set_size(degree + ingfx.degree + 1, false); 00515 for (j = 0; j < coeffs.size(); j++) 00516 coeffs(j).set(q, -1); // set coefficients to the zeroth element (log(0)=-Inf=-1) 00517 for (i = 0;i < degree + 1;i++) 00518 for (j = 0;j < ingfx.degree + 1;j++) 00519 coeffs(i + j) += tempcoeffs(i) * ingfx.coeffs(j); 00520 degree = coeffs.size() - 1; 00521 } 00522 00523 inline GFX GFX::operator*(const GFX &ingfx) const 00524 { 00525 GFX tmp(*this); 00526 tmp *= ingfx; 00527 return tmp; 00528 } 00529 00530 inline GFX operator*(const GF &ingf, const GFX &ingfx) 00531 { 00532 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field"); 00533 GFX temp(ingfx); 00534 for (int i = 0;i < ingfx.degree + 1;i++) 00535 temp.coeffs(i) *= ingf; 00536 return temp; 00537 } 00538 00539 inline GFX operator*(const GFX &ingfx, const GF &ingf) 00540 { 00541 return ingf*ingfx; 00542 } 00543 00544 inline GFX operator/(const GFX &ingfx, const GF &ingf) 00545 { 00546 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op/, Not same field"); 00547 GFX temp(ingfx); 00548 for (int i = 0;i < ingfx.degree + 1;i++) 00549 temp.coeffs(i) /= ingf; 00550 return temp; 00551 } 00552 00553 inline GF GFX::operator()(const GF &ingf) 00554 { 00555 it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field"); 00556 GF temp(coeffs(0)), ingfpower(ingf); 00557 for (int i = 1; i < degree + 1; i++) { 00558 temp += coeffs(i) * ingfpower; 00559 ingfpower *= ingf; 00560 } 00561 return temp; 00562 } 00563 00564 } // namespace itpp 00565 00566 #endif // #ifndef GALOIS_H
Generated on Sat Jul 9 2011 15:21:31 for IT++ by Doxygen 1.7.4