00001 00046 /* 00047 TODO: 00048 00049 - There is probably potential for improving the efficiency of some 00050 of the matrix/vector multiplication operators. (See specific 00051 comments in the code.) 00052 00053 - Make the data representation dynamic to account for the 00054 possibility (?) that a short integer can store more than 16 bits. 00055 Or use "int" or "long int"? 00056 00057 - Implement a general GF(2)-matrix class which offers the user a 00058 transparent interface (user does not need to know whether the 00059 sparse or the dense representation is used)? 00060 */ 00061 00062 #ifndef GF2MAT_H 00063 #define GF2MAT_H 00064 00065 #include <itpp/base/vec.h> 00066 #include <itpp/base/mat.h> 00067 #include <itpp/base/svec.h> 00068 #include <itpp/base/smat.h> 00069 #include <itpp/base/itfile.h> 00070 00071 00072 /* 00073 An "unsigned short int" is used to represent the data 00074 structure. Note that, an unsigned short int has at least 16 bits, 00075 possibly more depending on the implementation. Here 16 bits is 00076 assumed. 00077 00078 Note: the data structure is implemented as unsigned int because 00079 some operations rely on right shifting (for signed integers the 00080 right shift operator is implementation defined). 00081 */ 00082 00083 // log2(number of bits in one "short int"). This is used to perform 00084 // division. 00085 #define lImax 4 00086 // (1 << (lImax - 1)). This is used as mask for (1 << lImax), when 00087 // computing remainder 00088 #define mImax 15 00089 00090 namespace itpp { 00091 00093 typedef Sparse_Vec<bin> GF2vec_sparse; 00094 00096 typedef Sparse_Mat<bin> GF2mat_sparse; 00097 00116 class GF2mat { 00117 public: 00118 00119 // ----------- Constructors ----------- 00120 00122 GF2mat(); 00123 00125 GF2mat(int m, int n); 00126 00128 GF2mat(const GF2mat_sparse &X); 00129 00131 GF2mat(const GF2mat_sparse &X, int m1, int n1, int m2, int n2); 00132 00134 GF2mat(const GF2mat_sparse &X, ivec &columns); 00135 00144 GF2mat(const bvec &x, bool rc=1); 00145 00147 GF2mat(const bmat &X); 00148 00150 GF2mat_sparse sparsify(); 00151 00153 bvec bvecify(); 00154 00155 // ----------- Elementwise manipulation and simple functions ------------- 00156 00158 inline bin get(int i, int j) const; 00159 00161 inline bin operator()(int i, int j) const { return get(i,j); }; 00162 00164 inline void set(int i, int j, bin s); 00165 00167 inline void addto_element(int i, int j, bin s); 00168 00170 void set_col(int j, bvec x); 00171 00173 void set_row(int i, bvec x); 00174 00176 bool is_zero(); 00177 00179 void swap_rows(int i, int j); 00180 00182 void swap_cols(int i, int j); 00183 00190 void permute_rows(ivec &perm, bool I); 00191 00197 void permute_cols(ivec &perm, bool I); 00198 00200 GF2mat transpose() const; 00201 00203 GF2mat get_submatrix(int m1, int n1, int m2, int n2); 00204 00206 GF2mat concatenate_horizontal(const GF2mat &X); 00207 00209 GF2mat concatenate_vertical(const GF2mat &X); 00210 00212 bvec get_row(int i); 00213 00215 bvec get_col(int j); 00216 00218 double density() const; 00219 00221 inline int rows() { return nrows; } 00222 00224 inline int cols() { return ncols; } 00225 00227 void add_rows(int i, int j); 00228 00229 // ---------- Linear algebra -------------- 00230 00236 GF2mat inverse(); 00237 00239 int row_rank(); 00240 00253 int T_fact(GF2mat &T, GF2mat &U, ivec &P); 00254 00274 int T_fact_update_bitflip(GF2mat &T, GF2mat &U, ivec &P, int rank, int r, int c); 00275 00295 int T_fact_update_addcol(GF2mat &T, GF2mat &U, ivec &P, bvec newcol); 00296 00297 // ----- Operators ----------- 00298 00300 void operator=(const GF2mat &X); 00301 00303 bool operator==(const GF2mat &X) const; 00304 00305 // ----- Friends ------ 00306 00308 friend GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00309 00311 friend bvec operator*(const GF2mat &X, const bvec &y); 00312 00317 friend GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00318 00320 friend std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00321 00323 friend it_file &operator<<(it_file &f, const GF2mat &X); 00324 00326 friend it_ifile &operator>>(it_ifile &f, GF2mat &X); 00327 00329 friend GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00330 00331 private: 00332 int nwords; // number of bytes used 00333 int nrows, ncols; // number of rows and columns of matrix 00334 Mat<unsigned short int> data; // data structure 00335 }; 00336 00337 00338 // ============ RELATED FUNCTIONS ============================ 00339 00344 it_file &operator<<(it_file &f, const GF2mat &X); 00345 00350 it_ifile &operator>>(it_ifile &f, GF2mat &X); 00351 00356 GF2mat operator*(const GF2mat &X, const GF2mat &Y); 00357 00362 bvec operator*(const GF2mat &X, const bvec &y); 00363 00368 GF2mat operator+(const GF2mat &X, const GF2mat &Y); 00369 00374 std::ostream &operator<<(std::ostream &os, const GF2mat &X); 00375 00380 GF2mat gf2dense_eye(int m); 00381 00385 GF2mat mult_trans(const GF2mat &X, const GF2mat &Y); 00386 00387 // ================= INLINE IMPLEMENTATIONS ======================= 00388 00389 inline void GF2mat::addto_element(int i, int j, bin s) 00390 { 00391 it_assert0(i>=0 && i<nrows,"GF2mat::addto_element()"); 00392 it_assert0(j>=0 && j<ncols,"GF2mat::addto_element()"); 00393 if (s==1) { 00394 int col = j>>lImax; 00395 char bit = j&mImax; 00396 data(i,col) ^= (1<<bit); 00397 } 00398 } 00399 00400 inline bin GF2mat::get(int i, int j) const 00401 { 00402 it_assert0(i>=0 && i<nrows,"GF2mat::get_element()"); 00403 it_assert0(j>=0 && j<ncols,"GF2mat::get_element()"); 00404 int col = j>>lImax; 00405 char bit = j&mImax; 00406 return ((data(i,col) >> bit) & 1); // NB data must be unsigned for this to be well defined 00407 } 00408 00409 inline void GF2mat::set(int i, int j, bin s) 00410 { 00411 it_assert0(i>=0 && i<nrows,"GF2mat::set_element()"); 00412 it_assert0(j>=0 && j<ncols,"GF2mat::set_element()"); 00413 it_assert0(s==0 || s==1,"GF2mat::set_element()"); 00414 int col = j>>lImax; 00415 char bit = j&mImax; 00416 // int oldvalue = (data(i,col) >> bit) & 1; 00417 if (s==1) { // set bit to one 00418 data(i,col) |= (1<<bit); 00419 } else { // set bit to zero 00420 data(i,col) &= ((~0) ^ (1<<bit)); 00421 } 00422 } 00423 00424 } // namespace itpp 00425 00426 #endif // #ifndef GF2MAT_H
Generated on Sat Aug 25 23:37:27 2007 for IT++ by Doxygen 1.5.2