IT++ Logo
galois.h
Go to the documentation of this file.
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
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Sat Jul 9 2011 15:21:31 for IT++ by Doxygen 1.7.4