IT++ Logo Newcom Logo

galois.h

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

Generated on Thu Apr 19 14:43:44 2007 for IT++ by Doxygen 1.5.1