00001 00042 #ifndef GF2MAT_H 00043 #define GF2MAT_H 00044 00045 #include <itpp/base/vec.h> 00046 #include <itpp/base/mat.h> 00047 #include <itpp/base/svec.h> 00048 #include <itpp/base/smat.h> 00049 #include <itpp/base/itfile.h> 00050 00051 00052 namespace itpp 00053 { 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 { 00086 public: 00088 GF2mat_sparse_alist() : data_ok(false) {} 00090 GF2mat_sparse_alist(const std::string &fname); 00091 00093 void read(const std::string &fname); 00095 void write(const std::string &fname) const; 00096 00103 GF2mat_sparse to_sparse(bool transpose = false) const; 00104 00112 void from_sparse(const GF2mat_sparse &mat, bool transpose = false); 00113 00114 protected: 00116 bool data_ok; 00118 int M; 00120 int N; 00122 imat mlist; 00124 imat nlist; 00126 ivec num_mlist; 00128 ivec num_nlist; 00130 int max_num_m; 00132 int max_num_n; 00133 }; 00134 00135 00136 // ---------------------------------------------------------------------- 00137 // Dense GF(2) matrix class 00138 // ---------------------------------------------------------------------- 00139 00157 class GF2mat 00158 { 00159 public: 00160 00161 // ----------- Constructors ----------- 00162 00164 GF2mat(); 00165 00167 GF2mat(int m, int n); 00168 00170 GF2mat(const GF2mat_sparse &X); 00171 00176 GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2); 00177 00186 GF2mat(const GF2mat_sparse &X, const ivec &columns); 00187 00195 GF2mat(const bvec &x, bool is_column = true); 00196 00198 GF2mat(const bmat &X); 00199 00201 void set_size(int m, int n, bool copy = false); 00202 00204 GF2mat_sparse sparsify() const; 00205 00207 bvec bvecify() const; 00208 00209 // ----------- Elementwise manipulation and simple functions ------------- 00210 00212 inline bin get(int i, int j) const; 00213 00215 inline bin operator()(int i, int j) const { return get(i, j); }; 00216 00218 inline void set(int i, int j, bin s); 00219 00221 inline void addto_element(int i, int j, bin s); 00222 00224 void set_col(int j, bvec x); 00225 00227 void set_row(int i, bvec x); 00228 00230 bool is_zero() const; 00231 00233 void swap_rows(int i, int j); 00234 00236 void swap_cols(int i, int j); 00237 00244 void permute_rows(ivec &perm, bool I); 00245 00253 void permute_cols(ivec &perm, bool I); 00254 00256 GF2mat transpose() const; 00257 00259 GF2mat get_submatrix(int m1, int n1, int m2, int n2) const; 00260 00262 GF2mat concatenate_horizontal(const GF2mat &X) const; 00263 00265 GF2mat concatenate_vertical(const GF2mat &X) const; 00266 00268 bvec get_row(int i) const; 00269 00271 bvec get_col(int j) const; 00272 00274 double density() const; 00275 00277 int rows() const { return nrows; } 00278 00280 int cols() const { return ncols; } 00281 00289 void add_rows(int i, int j); 00290 00291 // ---------- Linear algebra -------------- 00292 00298 GF2mat inverse() const; 00299 00301 int row_rank() const; 00302 00319 int T_fact(GF2mat &T, GF2mat &U, ivec &P) const; 00320 00342 int T_fact_update_bitflip(GF2mat &T, GF2mat &U, 00343 ivec &P, int rank, int r, int c) const; 00344 00366 bool T_fact_update_addcol(GF2mat &T, GF2mat &U, 00367 ivec &P, bvec newcol) const; 00368 00369 // ----- Operators ----------- 00370 00372 void operator=(const GF2mat &X); 00373 00375 bool operator==(const GF2mat &X) const; 00376 00377 // ----- Friends ------ 00378 00380 friend GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00381 00383 friend bvec operator*(const GF2mat &X, const bvec &y); 00384 00389 friend GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00390 00392 friend std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00393 00395 friend it_file &operator<<(it_file &f, const GF2mat &X); 00396 00398 friend it_ifile &operator>>(it_ifile &f, GF2mat &X); 00399 00401 friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00402 00403 private: 00404 int nrows, ncols; // number of rows and columns of matrix 00405 int nwords; // number of bytes used 00406 Mat<unsigned char> data; // data structure 00407 00408 // This value is used to perform division by bit shift and is equal to 00409 // log2(8) 00410 static const unsigned char shift_divisor = 3; 00411 00412 // This value is used as a mask when computing the bit position of the 00413 // division remainder 00414 static const unsigned char rem_mask = (1 << shift_divisor) - 1; 00415 }; 00416 00417 00418 // ---------------------------------------------------------------------- 00419 // GF2mat related functions 00420 // ---------------------------------------------------------------------- 00421 00426 it_file &operator<<(it_file &f, const GF2mat &X); 00427 00432 it_ifile &operator>>(it_ifile &f, GF2mat &X); 00433 00438 GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00439 00444 bvec operator*(const GF2mat &X, const bvec &y); 00445 00450 GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00451 00456 std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00457 00462 GF2mat gf2dense_eye(int m); 00463 00468 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00469 00470 00471 // ---------------------------------------------------------------------- 00472 // Inline implementations 00473 // ---------------------------------------------------------------------- 00474 00475 inline void GF2mat::addto_element(int i, int j, bin s) 00476 { 00477 it_assert_debug(i >= 0 && i < nrows, "GF2mat::addto_element()"); 00478 it_assert_debug(j >= 0 && j < ncols, "GF2mat::addto_element()"); 00479 if (s == 1) 00480 data(i, (j >> shift_divisor)) ^= (1 << (j & rem_mask)); 00481 } 00482 00483 inline bin GF2mat::get(int i, int j) const 00484 { 00485 it_assert_debug(i >= 0 && i < nrows, "GF2mat::get_element()"); 00486 it_assert_debug(j >= 0 && j < ncols, "GF2mat::get_element()"); 00487 return (data(i, (j >> shift_divisor)) >> (j & rem_mask)) & 1; 00488 } 00489 00490 inline void GF2mat::set(int i, int j, bin s) 00491 { 00492 it_assert_debug(i >= 0 && i < nrows, "GF2mat::set_element()"); 00493 it_assert_debug(j >= 0 && j < ncols, "GF2mat::set_element()"); 00494 if (s == 1) // set bit to one 00495 data(i, (j >> shift_divisor)) |= (1 << (j & rem_mask)); 00496 else // set bit to zero 00497 data(i, (j >> shift_divisor)) &= (~(1 << (j & rem_mask))); 00498 } 00499 00500 } // namespace itpp 00501 00502 #endif // #ifndef GF2MAT_H
Generated on Wed Jul 27 2011 16:27:04 for IT++ by Doxygen 1.7.4