IT++ Logo
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Macros Groups Pages
galois.h
Go to the documentation of this file.
1 
29 #ifndef GALOIS_H
30 #define GALOIS_H
31 
32 #include <itpp/base/vec.h>
33 #include <itpp/base/array.h>
34 #include <itpp/base/binary.h>
35 #include <itpp/base/converters.h>
36 
37 
38 namespace itpp
39 {
40 
73 class GF
74 {
75 public:
77  GF() { m = 0; }
79  GF(int qvalue) {
80  m = 0;
81  if (qvalue == 0) // qvalue==0 gives the zeroth element
82  value = -1;
83  else set_size(qvalue);
84  }
86  GF(int qvalue, int inexp) { m = 0; set(qvalue, inexp); }
88  GF(const GF &ingf) { m = ingf.m; value = ingf.value; }
89 
91  void set(int qvalue, int inexp) {
92  set_size(qvalue);
93  it_assert_debug(inexp >= -1 && inexp < qvalue - 1, "GF::set, out of range");
94  value = inexp;
95  }
101  void set(int qvalue, const bvec &vectorspace);
103  void set_size(int qvalue);
105  int get_size() const { return ((m != 0) ? q[m] : 0); }
111  bvec get_vectorspace() const;
113  int get_value() const;
115  int operator==(const GF &ingf) const;
117  int operator!=(const GF &ingf) const;
118 
120  void operator=(const GF &ingf);
122  void operator=(const int inexp);
124  void operator+=(const GF &ingf);
126  GF operator+(const GF &ingf) const;
128  void operator-=(const GF &ingf);
130  GF operator-(const GF &ingf) const;
132  void operator*=(const GF &ingf);
134  GF operator*(const GF &ingf) const;
136  void operator/=(const GF &ingf);
138  GF operator/(const GF &ingf) const;
140  friend std::ostream &operator<<(std::ostream &os, const GF &ingf);
141 protected:
142 private:
143  char m;
144  int value;
145  static Array<Array<int> > alphapow, logalpha;
146  static ivec q;
147 };
148 
149 class GFX;
150 
152 GFX operator*(const GF &ingf, const GFX &ingfx);
154 GFX operator*(const GFX &ingfx, const GF &ingf);
156 GFX operator/(const GFX &ingfx, const GF &ingf);
157 
161 class GFX
162 {
163 public:
165  GFX();
167  GFX(int qvalue);
169  GFX(int qvalue, int indegree);
171  GFX(int qvalue, const ivec &invalues);
173  GFX(int qvalue, char *invalues);
175  GFX(int qvalue, std::string invalues);
177  GFX(const GFX &ingfx);
179  int get_size() const;
181  int get_degree() const;
185  void set_degree(int indegree, bool copy = false);
187  int get_true_degree() const;
189  void set(int qvalue, const char *invalues);
191  void set(int qvalue, const std::string invalues);
193  void set(int qvalue, const ivec &invalues);
195  void clear();
197  GF operator[](int index) const {
198  it_assert_debug(index<=degree, "GFX::op[], out of range");
199  return coeffs(index);
200  }
202  GF &operator[](int index) {
203  it_assert_debug(index<=degree, "GFX::op[], out of range");
204  return coeffs(index);
205  }
207  void operator=(const GFX &ingfx);
209  void operator+=(const GFX &ingfx);
211  GFX operator+(const GFX &ingfx) const;
213  void operator-=(const GFX &ingfx);
215  GFX operator-(const GFX &ingfx) const;
217  void operator*=(const GFX &ingfx);
219  GFX operator*(const GFX &ingfx) const;
221  GF operator()(const GF &ingf);
223  friend GFX operator*(const GF &ingf, const GFX &ingfx);
225  friend GFX operator*(const GFX &ingfx, const GF &ingf);
227  friend GFX operator/(const GFX &ingfx, const GF &ingf);
228 
230  friend std::ostream &operator<<(std::ostream &os, const GFX &ingfx);
231 protected:
232 private:
233  int degree, q;
234  Array<GF> coeffs;
235 };
236 
237 //-------------- Help Functions ------------------
244 GFX divgfx(const GFX &c, const GFX &g);
245 
250 GFX modgfx(const GFX &a, const GFX &b);
251 
252 
253 // --------------- Inlines ------------------------
254 // --------------- class GF -----------------------
255 
256 inline void GF::set(int qvalue, const bvec &vectorspace)
257 {
258  set_size(qvalue);
259  it_assert_debug(vectorspace.length() == m, "GF::set, out of range");
260  value = logalpha(m)(bin2dec(vectorspace));
261 }
262 
263 inline bvec GF::get_vectorspace() const
264 {
265  bvec temp(m);
266  if (value == -1)
267  temp = dec2bin(m, 0);
268  else
269  temp = dec2bin(m, alphapow(m)(value));
270  return temp;
271 }
272 
273 inline int GF::get_value() const
274 {
275  return value;
276 }
277 
278 inline int GF::operator==(const GF &ingf) const
279 {
280  if (value == -1 && ingf.value == -1)
281  return true;
282  if (m == ingf.m && value == ingf.value)
283  return true;
284  else
285  return false;
286 }
287 
288 inline int GF::operator!=(const GF &ingf) const
289 {
290  GF tmp(*this);
291  return !(tmp == ingf);
292 }
293 
294 inline void GF::operator=(const GF &ingf)
295 {
296  m = ingf.m;
297  value = ingf.value;
298 }
299 
300 inline void GF::operator=(const int inexp)
301 {
302  it_assert_debug(m > 0 && inexp >= -1 && inexp < (q[m] - 1), "GF::op=, out of range");
303  value = inexp;
304 }
305 
306 inline void GF::operator+=(const GF &ingf)
307 {
308  if (value == -1) {
309  value = ingf.value;
310  m = ingf.m;
311  }
312  else if (ingf.value != -1) {
313  it_assert_debug(ingf.m == m, "GF::op+=, not same field");
314  value = logalpha(m)(alphapow(m)(value) ^ alphapow(m)(ingf.value));
315  }
316 }
317 
318 inline GF GF::operator+(const GF &ingf) const
319 {
320  GF tmp(*this);
321  tmp += ingf;
322  return tmp;
323 }
324 
325 inline void GF::operator-=(const GF &ingf)
326 {
327  (*this) += ingf;
328 }
329 
330 inline GF GF::operator-(const GF &ingf) const
331 {
332  GF tmp(*this);
333  tmp -= ingf;
334  return tmp;
335 }
336 
337 inline void GF::operator*=(const GF &ingf)
338 {
339  if (value == -1 || ingf.value == -1)
340  value = -1;
341  else {
342  it_assert_debug(ingf.m == m, "GF::op+=, not same field");
343  value = (value + ingf.value) % (q[m] - 1);
344  }
345 }
346 
347 inline GF GF::operator*(const GF &ingf) const
348 {
349  GF tmp(*this);
350  tmp *= ingf;
351  return tmp;
352 }
353 
354 inline void GF::operator/=(const GF &ingf)
355 {
356  it_assert(ingf.value != -1, "GF::operator/: division by zero element"); // no division by the zeroth element
357  if (value == -1)
358  value = -1;
359  else {
360  it_assert_debug(ingf.m == m, "GF::op+=, not same field");
361  value = (value - ingf.value + q[m] - 1) % (q[m] - 1);
362  }
363 }
364 
365 inline GF GF::operator/(const GF &ingf) const
366 {
367  GF tmp(*this);
368  tmp /= ingf;
369  return tmp;
370 }
371 
372 // ------------------ class GFX --------------------
373 inline GFX::GFX()
374 {
375  degree = -1;
376  q = 0;
377 }
378 
379 inline GFX::GFX(int qvalue)
380 {
381  it_assert_debug(qvalue >= 0, "GFX::GFX, out of range");
382  q = qvalue;
383 }
384 
385 inline void GFX::set(int qvalue, const ivec &invalues)
386 {
387  it_assert_debug(qvalue > 0, "GFX::set, out of range");
388  degree = invalues.size() - 1;
389  coeffs.set_size(degree + 1, false);
390  for (int i = 0;i < degree + 1;i++)
391  coeffs(i).set(qvalue, invalues(i));
392  q = qvalue;
393 }
394 
395 inline void GFX::set(int qvalue, const char *invalues)
396 {
397  set(qvalue, ivec(invalues));
398 }
399 
400 inline void GFX::set(int qvalue, const std::string invalues)
401 {
402  set(qvalue, invalues.c_str());
403 }
404 
405 inline GFX::GFX(int qvalue, int indegree)
406 {
407  it_assert_debug(qvalue > 0 && indegree >= 0, "GFX::GFX, out of range");
408  q = qvalue;
409  coeffs.set_size(indegree + 1, false);
410  degree = indegree;
411  for (int i = 0;i < degree + 1;i++)
412  coeffs(i).set(q, -1);
413 }
414 inline GFX::GFX(int qvalue, const ivec &invalues)
415 {
416  set(qvalue, invalues);
417 }
418 
419 inline GFX::GFX(int qvalue, char *invalues)
420 {
421  set(qvalue, invalues);
422 }
423 
424 inline GFX::GFX(int qvalue, std::string invalues)
425 {
426  set(qvalue, invalues.c_str());
427 }
428 
429 inline GFX::GFX(const GFX &ingfx)
430 {
431  degree = ingfx.degree;
432  coeffs = ingfx.coeffs;
433  q = ingfx.q;
434 }
435 
436 inline int GFX::get_size() const
437 {
438  return q;
439 }
440 
441 inline int GFX::get_degree() const
442 {
443  return degree;
444 }
445 
446 inline void GFX::set_degree(int indegree, bool copy)
447 {
448  it_assert_debug(indegree >= -1, "GFX::set_degree, out of range");
449  coeffs.set_size(indegree + 1, copy);
450  degree = indegree;
451 }
452 
453 inline int GFX::get_true_degree() const
454 {
455  int i = degree;
456  while (coeffs(i).get_value() == -1) {
457  i--;
458  if (i == -1)
459  break;
460  }
461  return i;
462 }
463 
464 inline void GFX::clear()
465 {
466  it_assert_debug(degree >= 0 && q > 0, "GFX::clear, not set");
467  for (int i = 0;i < degree + 1;i++)
468  coeffs(i).set(q, -1);
469 }
470 
471 inline void GFX::operator=(const GFX &ingfx)
472 {
473  degree = ingfx.degree;
474  coeffs = ingfx.coeffs;
475  q = ingfx.q;
476 }
477 
478 inline void GFX::operator+=(const GFX &ingfx)
479 {
480  it_assert_debug(q == ingfx.q, "GFX::op+=, not same field");
481  if (ingfx.degree > degree) {
482  coeffs.set_size(ingfx.degree + 1, true);
483  // set new coefficients to the zeroth element
484  for (int j = degree + 1; j < coeffs.size(); j++) { coeffs(j).set(q, -1); }
485  degree = ingfx.degree;
486  }
487  for (int i = 0;i < ingfx.degree + 1;i++) { coeffs(i) += ingfx.coeffs(i); }
488 }
489 
490 inline GFX GFX::operator+(const GFX &ingfx) const
491 {
492  GFX tmp(*this);
493  tmp += ingfx;
494  return tmp;
495 }
496 
497 inline void GFX::operator-=(const GFX &ingfx)
498 {
499  (*this) += ingfx;
500 }
501 
502 inline GFX GFX::operator-(const GFX &ingfx) const
503 {
504  GFX tmp(*this);
505  tmp -= ingfx;
506  return tmp;
507 }
508 
509 inline void GFX::operator*=(const GFX &ingfx)
510 {
511  it_assert_debug(q == ingfx.q, "GFX::op*=, Not same field");
512  int i, j;
513  Array<GF> tempcoeffs = coeffs;
514  coeffs.set_size(degree + ingfx.degree + 1, false);
515  for (j = 0; j < coeffs.size(); j++)
516  coeffs(j).set(q, -1); // set coefficients to the zeroth element (log(0)=-Inf=-1)
517  for (i = 0;i < degree + 1;i++)
518  for (j = 0;j < ingfx.degree + 1;j++)
519  coeffs(i + j) += tempcoeffs(i) * ingfx.coeffs(j);
520  degree = coeffs.size() - 1;
521 }
522 
523 inline GFX GFX::operator*(const GFX &ingfx) const
524 {
525  GFX tmp(*this);
526  tmp *= ingfx;
527  return tmp;
528 }
529 
530 inline GFX operator*(const GF &ingf, const GFX &ingfx)
531 {
532  it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op*, Not same field");
533  GFX temp(ingfx);
534  for (int i = 0;i < ingfx.degree + 1;i++)
535  temp.coeffs(i) *= ingf;
536  return temp;
537 }
538 
539 inline GFX operator*(const GFX &ingfx, const GF &ingf)
540 {
541  return ingf*ingfx;
542 }
543 
544 inline GFX operator/(const GFX &ingfx, const GF &ingf)
545 {
546  it_assert_debug(ingf.get_size() == ingfx.q, "GFX::op/, Not same field");
547  GFX temp(ingfx);
548  for (int i = 0;i < ingfx.degree + 1;i++)
549  temp.coeffs(i) /= ingf;
550  return temp;
551 }
552 
553 inline GF GFX::operator()(const GF &ingf)
554 {
555  it_assert_debug(q == ingf.get_size(), "GFX::op(), Not same field");
556  GF temp(coeffs(0)), ingfpower(ingf);
557  for (int i = 1; i < degree + 1; i++) {
558  temp += coeffs(i) * ingfpower;
559  ingfpower *= ingf;
560  }
561  return temp;
562 }
563 
564 } // namespace itpp
565 
566 #endif // #ifndef GALOIS_H
SourceForge Logo

Generated on Fri Mar 21 2014 17:14:13 for IT++ by Doxygen 1.8.1.2