00001 00030 #ifndef GALOIS_H 00031 #define GALOIS_H 00032 00033 #include <itpp/base/vec.h> 00034 #include <itpp/base/array.h> 00035 #include <itpp/base/binary.h> 00036 #include <itpp/base/converters.h> 00037 00038 00039 namespace itpp 00040 { 00041 00074 class GF 00075 { 00076 public: 00078 GF() { m = 0; } 00080 GF(int qvalue) { 00081 m = 0; 00082 if (qvalue == 0) // qvalue==0 gives the zeroth element 00083 value = -1; 00084 else set_size(qvalue); 00085 } 00087 GF(int qvalue, int inexp) { m = 0; set(qvalue, inexp); } 00089 GF(const GF &ingf) { m = ingf.m; value = ingf.value; } 00090 00092 void set(int qvalue, int inexp) { 00093 set_size(qvalue); 00094 it_assert_debug(inexp >= -1 && inexp < qvalue - 1, "GF::set, out of range"); 00095 value = inexp; 00096 } 00102 void set(int qvalue, const bvec &vectorspace); 00104 void set_size(int qvalue); 00106 int get_size() const { return ((m != 0) ? q[m] : 0); } 00112 bvec get_vectorspace() const; 00114 int get_value() const; 00116 int operator==(const GF &ingf) const; 00118 int operator!=(const GF &ingf) const; 00119 00121 void operator=(const GF &ingf); 00123 void operator=(const int inexp); 00125 void operator+=(const GF &ingf); 00127 GF operator+(const GF &ingf) const; 00129 void operator-=(const GF &ingf); 00131 GF operator-(const GF &ingf) const; 00133 void operator*=(const GF &ingf); 00135 GF operator*(const GF &ingf) const; 00137 void operator/=(const GF &ingf); 00139 GF operator/(const GF &ingf) const; 00141 friend std::ostream &operator<<(std::ostream &os, const GF &ingf); 00142 protected: 00143 private: 00144 char m; 00145 int value; 00146 static Array<Array<int> > alphapow, logalpha; 00147 static ivec q; 00148 }; 00149 00150 class GFX; 00151 00153 GFX operator*(const GF &ingf, const GFX &ingfx); 00155 GFX operator*(const GFX &ingfx, const GF &ingf); 00157 GFX operator/(const GFX &ingfx, const GF &ingf); 00158 00162 class GFX 00163 { 00164 public: 00166 GFX(); 00168 GFX(int qvalue); 00170 GFX(int qvalue, int indegree); 00172 GFX(int qvalue, const ivec &invalues); 00174 GFX(int qvalue, char *invalues); 00176 GFX(int qvalue, std::string invalues); 00178 GFX(const GFX &ingfx); 00180 int get_size() const; 00182 int get_degree() const; 00186 void set_degree(int indegree); 00188 int get_true_degree() const; 00190 void set(int qvalue, const char *invalues); 00192 void set(int qvalue, const std::string invalues); 00194 void set(int qvalue, const ivec &invalues); 00196 void clear(); 00198 GF operator[](int index) const { 00199 it_assert_debug(index<=degree, "GFX::op[], out of range"); 00200 return coeffs(index); 00201 } 00203 GF &operator[](int index) { 00204 it_assert_debug(index<=degree, "GFX::op[], out of range"); 00205 return coeffs(index); 00206 } 00208 void operator=(const GFX &ingfx); 00210 void operator+=(const GFX &ingfx); 00212 GFX operator+(const GFX &ingfx) const; 00214 void operator-=(const GFX &ingfx); 00216 GFX operator-(const GFX &ingfx) const; 00218 void operator*=(const GFX &ingfx); 00220 GFX operator*(const GFX &ingfx) const; 00222 GF operator()(const GF &ingf); 00224 friend GFX operator*(const GF &ingf, const GFX &ingfx); 00226 friend GFX operator*(const GFX &ingfx, const GF &ingf); 00228 friend GFX operator/(const GFX &ingfx, const GF &ingf); 00229 00231 friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx); 00232 protected: 00233 private: 00234 int degree, q; 00235 Array<GF> coeffs; 00236 }; 00237 00238 //-------------- Help Functions ------------------ 00245 GFX divgfx(const GFX &c, const GFX &g); 00246 00251 GFX modgfx(const GFX &a, const GFX &b); 00252 00253 00254 // --------------- Inlines ------------------------ 00255 // --------------- class GF ----------------------- 00256 00257 inline void GF::set(int qvalue, const bvec &vectorspace) 00258 { 00259 set_size(qvalue); 00260 it_assert_debug(vectorspace.length() == m, "GF::set, out of range"); 00261 value = logalpha(m)(bin2dec(vectorspace)); 00262 } 00263 00264 inline bvec GF::get_vectorspace() const 00265 { 00266 bvec temp(m); 00267 if (value == -1) 00268 temp = dec2bin(m, 0); 00269 else 00270 temp = dec2bin(m, alphapow(m)(value)); 00271 return temp; 00272 } 00273 00274 inline int GF::get_value() const 00275 { 00276 return value; 00277 } 00278 00279 inline int GF::operator==(const GF &ingf) const 00280 { 00281 if (value == -1 && ingf.value == -1) 00282 return true; 00283 if (m == ingf.m && value == ingf.value) 00284 return true; 00285 else 00286 return false; 00287 } 00288 00289 inline int GF::operator!=(const GF &ingf) const 00290 { 00291 GF tmp(*this); 00292 return !(tmp == ingf); 00293 } 00294 00295 inline void GF::operator=(const GF &ingf) 00296 { 00297 m = ingf.m; 00298 value = ingf.value; 00299 } 00300 00301 inline void GF::operator=(const int inexp) 00302 { 00303 it_assert_debug(m > 0 && inexp >= -1 && inexp < (q[m] - 1), "GF::op=, out of range"); 00304 value = inexp; 00305 } 00306 00307 inline void GF::operator+=(const GF &ingf) 00308 { 00309 if (value == -1) { 00310 value = ingf.value; 00311 m = ingf.m; 00312 } 00313 else if (ingf.value != -1) { 00314 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00315 value = logalpha(m)(alphapow(m)(value) ^ alphapow(m)(ingf.value)); 00316 } 00317 } 00318 00319 inline GF GF::operator+(const GF &ingf) const 00320 { 00321 GF tmp(*this); 00322 tmp += ingf; 00323 return tmp; 00324 } 00325 00326 inline void GF::operator-=(const GF &ingf) 00327 { 00328 (*this) += ingf; 00329 } 00330 00331 inline GF GF::operator-(const GF &ingf) const 00332 { 00333 GF tmp(*this); 00334 tmp -= ingf; 00335 return tmp; 00336 } 00337 00338 inline void GF::operator*=(const GF &ingf) 00339 { 00340 if (value == -1 || ingf.value == -1) 00341 value = -1; 00342 else { 00343 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00344 value = (value + ingf.value) % (q[m] - 1); 00345 } 00346 } 00347 00348 inline GF GF::operator*(const GF &ingf) const 00349 { 00350 GF tmp(*this); 00351 tmp *= ingf; 00352 return tmp; 00353 } 00354 00355 inline void GF::operator/=(const GF &ingf) 00356 { 00357 it_assert(ingf.value != -1, "GF::operator/: division by zero element"); // no division by the zeroth element 00358 if (value == -1) 00359 value = -1; 00360 else { 00361 it_assert_debug(ingf.m == m, "GF::op+=, not same field"); 00362 value = (value - ingf.value + q[m] - 1) % (q[m] - 1); 00363 } 00364 } 00365 00366 inline GF GF::operator/(const GF &ingf) const 00367 { 00368 GF tmp(*this); 00369 tmp /= ingf; 00370 return tmp; 00371 } 00372 00373 // ------------------ class GFX -------------------- 00374 inline GFX::GFX() 00375 { 00376 degree = -1; 00377 q = 0; 00378 } 00379 00380 inline GFX::GFX(int qvalue) 00381 { 00382 it_assert_debug(qvalue >= 0, "GFX::GFX, out of range"); 00383 q = qvalue; 00384 } 00385 00386 inline void GFX::set(int qvalue, const ivec &invalues) 00387 { 00388 it_assert_debug(qvalue > 0, "GFX::set, out of range"); 00389 degree = invalues.size() - 1; 00390 coeffs.set_size(degree + 1, false); 00391 for (int i = 0;i < degree + 1;i++) 00392 coeffs(i).set(qvalue, invalues(i)); 00393 q = qvalue; 00394 } 00395 00396 inline void GFX::set(int qvalue, const char *invalues) 00397 { 00398 set(qvalue, ivec(invalues)); 00399 } 00400 00401 inline void GFX::set(int qvalue, const std::string invalues) 00402 { 00403 set(qvalue, invalues.c_str()); 00404 } 00405 00406 inline GFX::GFX(int qvalue, int indegree) 00407 { 00408 it_assert_debug(qvalue > 0 && indegree >= 0, "GFX::GFX, out of range"); 00409 q = qvalue; 00410 coeffs.set_size(indegree + 1, false); 00411 degree = indegree; 00412 for (int i = 0;i < degree + 1;i++) 00413 coeffs(i).set(q, -1); 00414 } 00415 inline GFX::GFX(int qvalue, const ivec &invalues) 00416 { 00417 set(qvalue, invalues); 00418 } 00419 00420 inline GFX::GFX(int qvalue, char *invalues) 00421 { 00422 set(qvalue, invalues); 00423 } 00424 00425 inline GFX::GFX(int qvalue, std::string invalues) 00426 { 00427 set(qvalue, invalues.c_str()); 00428 } 00429 00430 inline GFX::GFX(const GFX &ingfx) 00431 { 00432 degree = ingfx.degree; 00433 coeffs = ingfx.coeffs; 00434 q = ingfx.q; 00435 } 00436 00437 inline int GFX::get_size() const 00438 { 00439 return q; 00440 } 00441 00442 inline int GFX::get_degree() const 00443 { 00444 return degree; 00445 } 00446 00447 inline void GFX::set_degree(int indegree) 00448 { 00449 it_assert_debug(indegree >= -1, "GFX::set_degree, out of range"); 00450 coeffs.set_size(indegree + 1); 00451 degree = indegree; 00452 } 00453 00454 inline int GFX::get_true_degree() const 00455 { 00456 int i = degree; 00457 while (coeffs(i).get_value() == -1) { 00458 i--; 00459 if (i == -1) 00460 break; 00461 } 00462 return i; 00463 } 00464 00465 inline void GFX::clear() 00466 { 00467 it_assert_debug(degree >= 0 && q > 0, "GFX::clear, not set"); 00468 for (int i = 0;i < degree + 1;i++) 00469 coeffs(i).set(q, -1); 00470 } 00471 00472 inline void GFX::operator=(const GFX &ingfx) 00473 { 00474 degree = ingfx.degree; 00475 coeffs = ingfx.coeffs; 00476 q = ingfx.q; 00477 } 00478 00479 inline void GFX::operator+=(const GFX &ingfx) 00480 { 00481 it_assert_debug(q == ingfx.q, "GFX::op+=, not same field"); 00482 if (ingfx.degree > degree) { 00483 coeffs.set_size(ingfx.degree + 1, true); 00484 // set new coefficients to the zeroth element 00485 for (int j = degree + 1; j < coeffs.size(); j++) { coeffs(j).set(q, -1); } 00486 degree = ingfx.degree; 00487 } 00488 for (int i = 0;i < ingfx.degree + 1;i++) { coeffs(i) += ingfx.coeffs(i); } 00489 } 00490 00491 inline GFX GFX::operator+(const GFX &ingfx) const 00492 { 00493 GFX tmp(*this); 00494 tmp += ingfx; 00495 return tmp; 00496 } 00497 00498 inline void GFX::operator-=(const GFX &ingfx) 00499 { 00500 (*this) += ingfx; 00501 } 00502 00503 inline GFX GFX::operator-(const GFX &ingfx) const 00504 { 00505 GFX tmp(*this); 00506 tmp -= ingfx; 00507 return tmp; 00508 } 00509 00510 inline void GFX::operator*=(const GFX &ingfx) 00511 { 00512 it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field"); 00513 int i, j; 00514 Array<GF> tempcoeffs = coeffs; 00515 coeffs.set_size(degree + ingfx.degree + 1, false); 00516 for (j = 0; j < coeffs.size(); j++) 00517 coeffs(j).set(q, -1); // set coefficients to the zeroth element (log(0)=-Inf=-1) 00518 for (i = 0;i < degree + 1;i++) 00519 for (j = 0;j < ingfx.degree + 1;j++) 00520 coeffs(i + j) += tempcoeffs(i) * ingfx.coeffs(j); 00521 degree = coeffs.size() - 1; 00522 } 00523 00524 inline GFX GFX::operator*(const GFX &ingfx) const 00525 { 00526 GFX tmp(*this); 00527 tmp *= ingfx; 00528 return tmp; 00529 } 00530 00531 inline GFX operator*(const GF &ingf, const GFX &ingfx) 00532 { 00533 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field"); 00534 GFX temp(ingfx); 00535 for (int i = 0;i < ingfx.degree + 1;i++) 00536 temp.coeffs(i) *= ingf; 00537 return temp; 00538 } 00539 00540 inline GFX operator*(const GFX &ingfx, const GF &ingf) 00541 { 00542 return ingf*ingfx; 00543 } 00544 00545 inline GFX operator/(const GFX &ingfx, const GF &ingf) 00546 { 00547 it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op/, Not same field"); 00548 GFX temp(ingfx); 00549 for (int i = 0;i < ingfx.degree + 1;i++) 00550 temp.coeffs(i) /= ingf; 00551 return temp; 00552 } 00553 00554 inline GF GFX::operator()(const GF &ingf) 00555 { 00556 it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field"); 00557 GF temp(coeffs(0)), ingfpower(ingf); 00558 for (int i = 1; i < degree + 1; i++) { 00559 temp += coeffs(i) * ingfpower; 00560 ingfpower *= ingf; 00561 } 00562 return temp; 00563 } 00564 00565 } // namespace itpp 00566 00567 #endif // #ifndef GALOIS_H
Generated on Wed Mar 2 2011 22:05:01 for IT++ by Doxygen 1.7.3