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 Thu Apr 24 13:39:00 2008 for IT++ by Doxygen 1.5.5