IT++ Logo

galois.h

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

Generated on Tue Feb 2 09:33:30 2010 for IT++ by Doxygen 1.6.2