00001 00043 #ifndef GF2MAT_H 00044 #define GF2MAT_H 00045 00046 #include <itpp/base/vec.h> 00047 #include <itpp/base/mat.h> 00048 #include <itpp/base/svec.h> 00049 #include <itpp/base/smat.h> 00050 #include <itpp/base/itfile.h> 00051 00052 00053 namespace itpp { 00054 00055 // ---------------------------------------------------------------------- 00056 // Sparse GF(2) matrix class 00057 // ---------------------------------------------------------------------- 00058 00060 typedef Sparse_Vec<bin> GF2vec_sparse; 00061 00063 typedef Sparse_Mat<bin> GF2mat_sparse; 00064 00065 00066 // ---------------------------------------------------------------------- 00067 // Alist parameterization of sparse GF(2) matrix class 00068 // ---------------------------------------------------------------------- 00069 00084 class GF2mat_sparse_alist { 00085 public: 00087 GF2mat_sparse_alist() : data_ok(false) {} 00089 GF2mat_sparse_alist(const std::string &fname); 00090 00092 void read(const std::string &fname); 00094 void write(const std::string &fname) const; 00095 00102 GF2mat_sparse to_sparse(bool transpose = false) const; 00103 00111 void from_sparse(const GF2mat_sparse &mat, bool transpose = false); 00112 00113 protected: 00115 bool data_ok; 00117 int M; 00119 int N; 00121 imat mlist; 00123 imat nlist; 00125 ivec num_mlist; 00127 ivec num_nlist; 00129 int max_num_m; 00131 int max_num_n; 00132 }; 00133 00134 00135 // ---------------------------------------------------------------------- 00136 // Dense GF(2) matrix class 00137 // ---------------------------------------------------------------------- 00138 00156 class GF2mat { 00157 public: 00158 00159 // ----------- Constructors ----------- 00160 00162 GF2mat(); 00163 00165 GF2mat(int m, int n); 00166 00168 GF2mat(const GF2mat_sparse &X); 00169 00174 GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2); 00175 00184 GF2mat(const GF2mat_sparse &X, const ivec &columns); 00185 00193 GF2mat(const bvec &x, bool is_column = true); 00194 00196 GF2mat(const bmat &X); 00197 00199 void set_size(int m, int n, bool copy = false); 00200 00202 GF2mat_sparse sparsify() const; 00203 00205 bvec bvecify() const; 00206 00207 // ----------- Elementwise manipulation and simple functions ------------- 00208 00210 inline bin get(int i, int j) const; 00211 00213 inline bin operator()(int i, int j) const { return get(i,j); }; 00214 00216 inline void set(int i, int j, bin s); 00217 00219 inline void addto_element(int i, int j, bin s); 00220 00222 void set_col(int j, bvec x); 00223 00225 void set_row(int i, bvec x); 00226 00228 bool is_zero() const; 00229 00231 void swap_rows(int i, int j); 00232 00234 void swap_cols(int i, int j); 00235 00242 void permute_rows(ivec &perm, bool I); 00243 00251 void permute_cols(ivec &perm, bool I); 00252 00254 GF2mat transpose() const; 00255 00257 GF2mat get_submatrix(int m1, int n1, int m2, int n2) const; 00258 00260 GF2mat concatenate_horizontal(const GF2mat &X) const; 00261 00263 GF2mat concatenate_vertical(const GF2mat &X) const; 00264 00266 bvec get_row(int i) const; 00267 00269 bvec get_col(int j) const; 00270 00272 double density() const; 00273 00275 int rows() const { return nrows; } 00276 00278 int cols() const { return ncols; } 00279 00287 void add_rows(int i, int j); 00288 00289 // ---------- Linear algebra -------------- 00290 00296 GF2mat inverse() const; 00297 00299 int row_rank() const; 00300 00317 int T_fact(GF2mat &T, GF2mat &U, ivec &P) const; 00318 00340 int T_fact_update_bitflip(GF2mat &T, GF2mat &U, 00341 ivec &P, int rank, int r, int c) const; 00342 00364 bool T_fact_update_addcol(GF2mat &T, GF2mat &U, 00365 ivec &P, bvec newcol) const; 00366 00367 // ----- Operators ----------- 00368 00370 void operator=(const GF2mat &X); 00371 00373 bool operator==(const GF2mat &X) const; 00374 00375 // ----- Friends ------ 00376 00378 friend GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00379 00381 friend bvec operator*(const GF2mat &X, const bvec &y); 00382 00387 friend GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00388 00390 friend std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00391 00393 friend it_file &operator<<(it_file &f, const GF2mat &X); 00394 00396 friend it_ifile &operator>>(it_ifile &f, GF2mat &X); 00397 00399 friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00400 00401 private: 00402 int nrows, ncols; // number of rows and columns of matrix 00403 int nwords; // number of bytes used 00404 Mat<unsigned char> data; // data structure 00405 00406 // This value is used to perform division by bit shift and is equal to 00407 // log2(8) 00408 static const unsigned char shift_divisor = 3; 00409 00410 // This value is used as a mask when computing the bit position of the 00411 // division remainder 00412 static const unsigned char rem_mask = (1 << shift_divisor) - 1; 00413 }; 00414 00415 00416 // ---------------------------------------------------------------------- 00417 // GF2mat related functions 00418 // ---------------------------------------------------------------------- 00419 00424 it_file &operator<<(it_file &f, const GF2mat &X); 00425 00430 it_ifile &operator>>(it_ifile &f, GF2mat &X); 00431 00436 GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00437 00442 bvec operator*(const GF2mat &X, const bvec &y); 00443 00448 GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00449 00454 std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00455 00460 GF2mat gf2dense_eye(int m); 00461 00466 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00467 00468 00469 // ---------------------------------------------------------------------- 00470 // Inline implementations 00471 // ---------------------------------------------------------------------- 00472 00473 inline void GF2mat::addto_element(int i, int j, bin s) 00474 { 00475 it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()"); 00476 it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()"); 00477 if (s == 1) 00478 data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask)); 00479 } 00480 00481 inline bin GF2mat::get(int i, int j) const 00482 { 00483 it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()"); 00484 it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()"); 00485 return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1; 00486 } 00487 00488 inline void GF2mat::set(int i, int j, bin s) 00489 { 00490 it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()"); 00491 it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()"); 00492 if (s == 1) // set bit to one 00493 data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask)); 00494 else // set bit to zero 00495 data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask))); 00496 } 00497 00498 } // namespace itpp 00499 00500 #endif // #ifndef GF2MAT_H
Generated on Sat Apr 19 10:41:55 2008 for IT++ by Doxygen 1.5.5