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
Generated on Sun Apr 20 12:40:06 2008 for IT++ by Doxygen 1.5.5