IT++ Logo Newcom Logo

gf2mat.h

Go to the documentation of this file.
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
SourceForge Logo

Generated on Fri Jun 8 02:08:51 2007 for IT++ by Doxygen 1.5.2