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
Generated on Thu Apr 19 14:18:30 2007 for IT++ by Doxygen 1.5.1