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 
00073   class GF {
00074   public:
00076     GF() { m=0; }
00078     GF(int qvalue) { m=0; if (qvalue==0) // qvalue==0 gives the zeroth element
00079                             value=-1; else set_size(qvalue); }
00081     GF(int qvalue, int inexp) { m=0; set(qvalue,inexp); }
00083     GF(const GF &ingf) { m=ingf.m; value=ingf.value; }
00084 
00086     void set(int qvalue, int inexp) {
00087       set_size(qvalue); it_assert_debug(inexp>=-1 && inexp<qvalue-1, "GF::set, out of range"); value=inexp; }
00093     void set(int qvalue, const bvec &vectorspace);
00095     void set_size(int qvalue);
00097     int get_size() const { return ( (m != 0) ? q[m] : 0 ); }
00103     bvec get_vectorspace() const;
00105     int  get_value() const;
00107     int operator==(const GF &ingf) const;
00109     int operator!=(const GF &ingf) const;
00110 
00112     void operator=(const GF &ingf);
00114     void operator=(const int inexp);
00116     void operator+=(const GF &ingf);
00118     GF operator+(const GF &ingf) const;
00120     void operator-=(const GF &ingf);
00122     GF operator-(const GF &ingf) const;
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     friend std::ostream &operator<<(std::ostream &os, const GF &ingf);
00133   protected:
00134   private:
00135     char m;
00136     int value;
00137     static Array<Array<int> > alphapow,logalpha;
00138     static ivec q;
00139   };
00140 
00141   class GFX;
00142 
00144   GFX  operator*(const GF &ingf, const GFX &ingfx);
00146   GFX  operator*( const GFX &ingfx, const GF &ingf);
00148   GFX  operator/(const GFX &ingfx, const GF &ingf);
00149 
00153   class GFX {
00154   public:
00156     GFX();
00158     GFX(int qvalue);
00160     GFX(int qvalue, int indegree);
00162     GFX(int qvalue, const ivec &invalues);
00164     GFX(int qvalue, char *invalues);
00166     GFX(int qvalue, std::string invalues);
00168     GFX(const GFX &ingfx);
00170     int get_size() const;
00172     int get_degree() const;
00176     void set_degree(int indegree);
00178     int get_true_degree() const;
00180     void set(int qvalue, const char *invalues);
00182     void set(int qvalue, const std::string invalues);
00184     void set(int qvalue, const ivec &invalues);
00186     void clear();
00188     GF operator[](int index) const {
00189       it_assert_debug(index<=degree, "GFX::op[], out of range"); return coeffs(index); }
00191     GF &operator[](int index) {
00192       it_assert_debug(index<=degree, "GFX::op[], out of range"); return coeffs(index); }
00194     void operator=(const GFX &ingfx);
00196     void operator+=(const GFX &ingfx);
00198     GFX operator+(const GFX &ingfx) const;
00200     void operator-=(const GFX &ingfx);
00202     GFX operator-(const GFX &ingfx) const;
00204     void operator*=(const GFX &ingfx);
00206     GFX operator*(const GFX &ingfx) const;
00208     GF operator()(const GF &ingf);
00210     friend GFX  operator*(const GF &ingf, const GFX &ingfx);
00212     friend GFX  operator*( const GFX &ingfx, const GF &ingf);
00214     friend GFX  operator/(const GFX &ingfx, const GF &ingf);
00215 
00217     friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
00218   protected:
00219   private:
00220     int degree, q;
00221     Array<GF> coeffs;
00222   };
00223 
00224   //-------------- Help Functions ------------------
00231   GFX divgfx(const GFX &c, const GFX &g);
00232 
00237   GFX modgfx(const GFX &a, const GFX &b);
00238 
00239 
00240   // --------------- Inlines ------------------------
00241   // --------------- class GF -----------------------
00242 
00243   inline void GF::set(int qvalue, const bvec &vectorspace)
00244   {
00245     set_size(qvalue);
00246     it_assert_debug(vectorspace.length() == m, "GF::set, out of range");
00247     value=logalpha(m)(bin2dec(vectorspace));
00248   }
00249 
00250   inline bvec GF::get_vectorspace() const
00251   {
00252     bvec temp(m);
00253     if (value == -1)
00254       temp=dec2bin(m,0);
00255     else
00256       temp=dec2bin(m,alphapow(m)(value));
00257     return temp;
00258   }
00259 
00260   inline int  GF::get_value() const
00261   {
00262     return value;
00263   }
00264 
00265   inline int GF::operator==(const GF &ingf) const
00266   {
00267     if (value == -1 && ingf.value == -1)
00268       return true;
00269     if (m==ingf.m && value==ingf.value)
00270       return true;
00271     else
00272       return false;
00273   }
00274 
00275   inline int GF::operator!=(const GF &ingf) const
00276   {
00277     GF tmp(*this);
00278     return !(tmp==ingf);
00279   }
00280 
00281   inline void GF::operator=(const GF &ingf)
00282   {
00283     m=ingf.m;
00284     value=ingf.value;
00285   }
00286 
00287   inline void GF::operator=(const int inexp)
00288   {
00289     it_assert_debug(m>0 && inexp>=-1 && inexp<(q[m]-1), "GF::op=, out of range");
00290     value=inexp;
00291   }
00292 
00293   inline void GF::operator+=(const GF &ingf)
00294   {
00295     if (value == -1) {
00296       value=ingf.value;
00297       m=ingf.m;
00298     }
00299     else if (ingf.value != -1) {
00300       it_assert_debug(ingf.m == m, "GF::op+=, not same field");
00301       value=logalpha(m)(alphapow(m)(value)^alphapow(m)(ingf.value));
00302     }
00303   }
00304 
00305   inline GF GF::operator+(const GF &ingf) const
00306   {
00307     GF tmp(*this);
00308     tmp+=ingf;
00309     return tmp;
00310   }
00311 
00312   inline void GF::operator-=(const GF &ingf)
00313   {
00314     (*this)+=ingf;
00315   }
00316 
00317   inline GF GF::operator-(const GF &ingf) const
00318   {
00319     GF tmp(*this);
00320     tmp-=ingf;
00321     return tmp;
00322   }
00323 
00324   inline void GF::operator*=(const GF &ingf)
00325   {
00326     if (value == -1 || ingf.value == -1)
00327       value=-1;
00328     else {
00329       it_assert_debug(ingf.m == m, "GF::op+=, not same field");
00330       value=(value+ingf.value)%(q[m]-1);
00331     }
00332   }
00333 
00334   inline GF GF::operator*(const GF &ingf) const
00335   {
00336     GF tmp(*this);
00337     tmp*=ingf;
00338     return tmp;
00339   }
00340 
00341   inline void GF::operator/=(const GF &ingf)
00342   {
00343     it_assert(ingf.value !=-1, "GF::operator/: division by zero element"); // no division by the zeroth element
00344     if (value == -1)
00345       value=-1;
00346     else {
00347       it_assert_debug(ingf.m == m, "GF::op+=, not same field");
00348       value=(value-ingf.value+q[m]-1)%(q[m]-1);
00349     }
00350   }
00351 
00352   inline GF GF::operator/(const GF &ingf) const
00353   {
00354     GF tmp(*this);
00355     tmp/=ingf;
00356     return tmp;
00357   }
00358 
00359   // ------------------ class GFX --------------------
00360   inline GFX::GFX()
00361   {
00362     degree=-1;
00363     q=0;
00364   }
00365 
00366   inline GFX::GFX(int qvalue)
00367   {
00368     it_assert_debug(qvalue>=0, "GFX::GFX, out of range");
00369     q=qvalue;
00370   }
00371 
00372   inline void GFX::set(int qvalue, const ivec &invalues)
00373   {
00374     it_assert_debug(qvalue>0, "GFX::set, out of range");
00375     degree=invalues.size()-1;
00376     coeffs.set_size(degree+1, false);
00377     for (int i=0;i<degree+1;i++)
00378       coeffs(i).set(qvalue,invalues(i));
00379     q=qvalue;
00380   }
00381 
00382   inline void GFX::set(int qvalue, const char *invalues)
00383   {
00384     set(qvalue,ivec(invalues));
00385   }
00386 
00387   inline void GFX::set(int qvalue, const std::string invalues)
00388   {
00389     set(qvalue,invalues.c_str());
00390   }
00391 
00392   inline GFX::GFX(int qvalue, int indegree)
00393   {
00394     it_assert_debug(qvalue>0 && indegree>=0, "GFX::GFX, out of range");
00395     q=qvalue;
00396     coeffs.set_size(indegree+1, false);
00397     degree=indegree;
00398     for (int i=0;i<degree+1;i++)
00399       coeffs(i).set(q,-1);
00400   }
00401   inline GFX::GFX(int qvalue, const ivec &invalues)
00402   {
00403     set(qvalue,invalues);
00404   }
00405 
00406   inline GFX::GFX(int qvalue, char *invalues)
00407   {
00408     set(qvalue,invalues);
00409   }
00410 
00411   inline GFX::GFX(int qvalue, std::string invalues)
00412   {
00413     set(qvalue,invalues.c_str());
00414   }
00415 
00416   inline GFX::GFX(const GFX &ingfx)
00417   {
00418     degree=ingfx.degree;
00419     coeffs=ingfx.coeffs;
00420     q=ingfx.q;
00421   }
00422 
00423   inline int GFX::get_size() const
00424   {
00425     return q;
00426   }
00427 
00428   inline int GFX::get_degree() const
00429   {
00430     return degree;
00431   }
00432 
00433   inline void GFX::set_degree(int indegree)
00434   {
00435     it_assert_debug(indegree>=-1, "GFX::set_degree, out of range");
00436     coeffs.set_size(indegree+1);
00437     degree=indegree;
00438   }
00439 
00440   inline int GFX::get_true_degree() const
00441   {
00442     int i=degree;
00443     while(coeffs(i).get_value()==-1) {
00444       i--;
00445       if (i==-1)
00446         break;
00447     }
00448     return i;
00449   }
00450 
00451   inline void GFX::clear()
00452   {
00453     it_assert_debug(degree>=0 && q>0, "GFX::clear, not set");
00454     for(int i=0;i<degree+1;i++)
00455       coeffs(i).set(q,-1);
00456   }
00457 
00458   inline void GFX::operator=(const GFX &ingfx)
00459   {
00460     degree=ingfx.degree;
00461     coeffs=ingfx.coeffs;
00462     q=ingfx.q;
00463   }
00464 
00465   inline void GFX::operator+=(const GFX &ingfx)
00466   {
00467     it_assert_debug(q == ingfx.q, "GFX::op+=, not same field");
00468     if (ingfx.degree > degree) {
00469       coeffs.set_size(ingfx.degree+1, true);
00470       // set new coefficients to the zeroth element
00471       for (int j=degree+1; j<coeffs.size(); j++){ coeffs(j).set(q,-1); }
00472       degree=ingfx.degree;
00473     }
00474     for (int i=0;i<ingfx.degree+1;i++) { coeffs(i)+=ingfx.coeffs(i); }
00475   }
00476 
00477   inline GFX GFX::operator+(const GFX &ingfx) const
00478   {
00479     GFX tmp(*this);
00480     tmp+=ingfx;
00481     return tmp;
00482   }
00483 
00484   inline void GFX::operator-=(const GFX &ingfx)
00485   {
00486     (*this)+=ingfx;
00487   }
00488 
00489   inline GFX GFX::operator-(const GFX &ingfx) const
00490   {
00491     GFX tmp(*this);
00492     tmp-=ingfx;
00493     return tmp;
00494   }
00495 
00496   inline void GFX::operator*=(const GFX &ingfx)
00497   {
00498     it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field");
00499     int i,j;
00500     Array<GF> tempcoeffs=coeffs;
00501     coeffs.set_size(degree+ingfx.degree+1, false);
00502     for (j=0; j<coeffs.size(); j++)
00503       coeffs(j).set(q,-1); // set coefficients to the zeroth element (log(0)=-Inf=-1)
00504     for (i=0;i<degree+1;i++)
00505       for (j=0;j<ingfx.degree+1;j++)
00506         coeffs(i+j)+=tempcoeffs(i)*ingfx.coeffs(j);
00507     degree=coeffs.size()-1;
00508   }
00509 
00510   inline GFX GFX::operator*(const GFX &ingfx) const
00511   {
00512     GFX tmp(*this);
00513     tmp*=ingfx;
00514     return tmp;
00515   }
00516 
00517   inline GFX operator*(const GF &ingf, const GFX &ingfx)
00518   {
00519     it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field");
00520     GFX temp(ingfx);
00521     for (int i=0;i<ingfx.degree+1;i++)
00522       temp.coeffs(i)*=ingf;
00523     return temp;
00524   }
00525 
00526   inline GFX  operator*( const GFX &ingfx, const GF &ingf)
00527   {
00528     return ingf*ingfx;
00529   }
00530 
00531   inline GFX  operator/(const GFX &ingfx, const GF &ingf)
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 GF GFX::operator()(const GF &ingf)
00541   {
00542     it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field");
00543     GF temp(coeffs(0)), ingfpower(ingf);
00544     for (int i=1; i<degree+1; i++) {
00545       temp+=coeffs(i)*ingfpower;
00546       ingfpower*=ingf;
00547     }
00548     return temp;
00549   }
00550 
00551 } // namespace itpp
00552 
00553 #endif // #ifndef GALOIS_H
SourceForge Logo

Generated on Sun Dec 9 17:26:18 2007 for IT++ by Doxygen 1.5.4