IT++ Logo

ldpc.h

Go to the documentation of this file.
00001 
00030 #ifndef LDPC_H
00031 #define LDPC_H
00032 
00033 #include <iostream>
00034 #include <itpp/base/gf2mat.h>
00035 #include <itpp/base/random.h>
00036 #include <itpp/base/sort.h>
00037 #include <itpp/comm/llr.h>
00038 #include <itpp/comm/channel_code.h>
00039 
00040 namespace itpp
00041 {
00042 
00043 // ---------------------------------------------------------------------------
00044 // LDPC_Parity
00045 // ---------------------------------------------------------------------------
00046 
00071 class LDPC_Parity
00072 {
00073   friend class LDPC_Code;
00074 public:
00076   LDPC_Parity(): init_flag(false) {}
00077 
00079   LDPC_Parity(int ncheck, int nvar);
00080 
00092   LDPC_Parity(const std::string& filename, const std::string& format);
00093 
00095   LDPC_Parity(const GF2mat_sparse_alist& alist);
00096 
00098   virtual ~LDPC_Parity() {}
00099 
00101   void initialize(int ncheck, int nvar);
00102 
00104   GF2mat_sparse get_H(bool transpose = false) const {
00105     return (transpose ? Ht : H);
00106   }
00107 
00109   Sparse_Vec<bin> get_col(int c) const { return H.get_col(c); }
00110 
00112   Sparse_Vec<bin> get_row(int r) const { return Ht.get_col(r); }
00113 
00115   int get_nvar() const {
00116     it_assert_debug(H.cols() == nvar,
00117                     "LDPC_Parity::get_nvar(): Internal error");
00118     it_assert_debug(Ht.rows() == nvar,
00119                     "LDPC_Parity::get_nvar(): Internal error");
00120     return nvar;
00121   }
00122 
00124   int get_ncheck() const {
00125     it_assert_debug(H.rows() == ncheck,
00126                     "LDPC_Parity::get_ncheck(): Internal error");
00127     it_assert_debug(Ht.cols() == ncheck,
00128                     "LDPC_Parity::get_ncheck(): Internal error");
00129     return ncheck;
00130   }
00131 
00133   void set(int i, int j, bin value);
00134 
00136   bin get(int i, int j) const {
00137     it_assert_debug(H(i, j) == Ht(j, i), "LDPC_Parity::get(): Internal error");
00138     return H(i, j);
00139   }
00140 
00142   bin operator()(int i, int j) const {
00143     it_assert_debug(H(i, j) == Ht(j, i),
00144                     "LDPC_Parity::operator(): Internal error");
00145     return H(i, j);
00146   }
00147 
00149   virtual void display_stats() const;
00150 
00152   double get_rate() const {
00153     return (1.0 - static_cast<double>(ncheck) / nvar);
00154   }
00155 
00157   void import_alist(const GF2mat_sparse_alist& H_alist);
00158 
00160   GF2mat_sparse_alist export_alist() const;
00161 
00163   void load_alist(const std::string& alist_file);
00164 
00166   void save_alist(const std::string& alist_file) const;
00167 
00168 protected:
00170   bool init_flag;
00172   static const int Nmax = 200;
00174   GF2mat_sparse H;
00176   GF2mat_sparse Ht;
00178   int nvar;
00180   int ncheck;
00182   ivec sumX1;
00184   ivec sumX2;
00185 
00201   int check_for_cycles(int L) const;
00202 
00246   int check_connectivity(int from_m, int from_n, int to_m, int to_n,
00247                          int g, int L) const;
00248 
00249   //      inline int get_cmax() const {   return (max(sumX1));  }
00250   //      inline int get_vmax() const {   return (max(sumX2));  }
00251   //      ivec get_coldegree() const;
00252   //      ivec get_rowdegree() const;
00253 };
00254 
00255 
00256 // ----------------------------------------------------------------------
00257 // LDPC_Parity_Unstructured
00258 // ----------------------------------------------------------------------
00259 
00275 class LDPC_Parity_Unstructured : public LDPC_Parity
00276 {
00277 public:
00279   virtual void display_stats() const = 0;
00280 
00299   int cycle_removal_MGW(int L);
00300 
00301 protected:
00303   void generate_random_H(const ivec& C, const ivec& R, const ivec& cycopt);
00304 
00318   void compute_CR(const vec& var_deg, const vec& chk_deg, const int Nvar,
00319                   ivec &C, ivec &R);
00320 
00321 };
00322 
00323 
00324 // ----------------------------------------------------------------------
00325 // LDPC_Parity_Irregular
00326 // ----------------------------------------------------------------------
00327 
00332 class LDPC_Parity_Irregular : public LDPC_Parity_Unstructured
00333 {
00334 public:
00336   LDPC_Parity_Irregular() {}
00338   LDPC_Parity_Irregular(int Nvar, const vec& var_deg, const vec& chk_deg,
00339                         const std::string& method = "rand",
00340                         const ivec& options = "200 6");
00341 
00380   void generate(int Nvar, const vec& var_deg, const vec& chk_deg,
00381                 const std::string& method = "rand",
00382                 const ivec& options = "200 6");
00383 
00385   void display_stats() const { LDPC_Parity::display_stats(); }
00386 };
00387 
00388 
00389 // ----------------------------------------------------------------------
00390 // LDPC_Parity_Regular
00391 // ----------------------------------------------------------------------
00392 
00397 class LDPC_Parity_Regular : public LDPC_Parity_Unstructured
00398 {
00399 public:
00401   LDPC_Parity_Regular() {}
00403   LDPC_Parity_Regular(int Nvar, int k, int l,
00404                       const std::string& method = "rand",
00405                       const ivec& options = "200 6");
00406 
00425   void generate(int Nvar, int k, int l,
00426                 const std::string& method = "rand",
00427                 const ivec& options = "200 6");
00428 
00430   void display_stats() const { LDPC_Parity::display_stats(); }
00431 };
00432 
00433 // ----------------------------------------------------------------------
00434 // BLDPC_Parity
00435 // ----------------------------------------------------------------------
00436 
00461 class BLDPC_Parity : public LDPC_Parity
00462 {
00463 public:
00465   BLDPC_Parity(): LDPC_Parity(), Z(0), H_b(), H_b_valid(false) {}
00466 
00468   BLDPC_Parity(const imat &base_matrix, int exp_factor);
00469 
00471   BLDPC_Parity(const std::string &filename, int exp_factor);
00472 
00474   void expand_base(const imat &base_matrix, int exp_factor);
00475 
00477   int get_exp_factor() const;
00478 
00480   imat get_base_matrix() const;
00481 
00483   bool is_valid() const { return H_b_valid && init_flag; }
00484 
00486   void set_exp_factor(int exp_factor);
00487 
00489   void load_base_matrix(const std::string &filename);
00490 
00492   void save_base_matrix(const std::string &filename) const;
00493 
00494 private:
00495   int Z;   
00496   imat H_b;   
00497   bool H_b_valid;  
00498 
00500   void calculate_base_matrix();
00501 };
00502 
00503 
00504 // ----------------------------------------------------------------------
00505 // LDPC_Generator
00506 // ----------------------------------------------------------------------
00507 
00523 class LDPC_Generator
00524 {
00525   friend class LDPC_Code;
00526 public:
00528   LDPC_Generator(const std::string& type_in = ""): init_flag(false),
00529       type(type_in) {}
00531   virtual ~LDPC_Generator() {}
00532 
00534   virtual void encode(const bvec &input, bvec &output) = 0;
00535 
00537   std::string get_type() const { return type; }
00538 
00539 protected:
00540   bool init_flag;  
00541   std::string type;  
00542 
00544   virtual void save(const std::string& filename) const = 0;
00546   virtual void load(const std::string& filename) = 0;
00547 };
00548 
00549 
00550 // ----------------------------------------------------------------------
00551 // LDPC_Generator_Systematic
00552 // ----------------------------------------------------------------------
00553 
00565 class LDPC_Generator_Systematic : public LDPC_Generator
00566 {
00567 public:
00569   LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
00571   LDPC_Generator_Systematic(LDPC_Parity* const H,
00572                             bool natural_ordering = false,
00573                             const ivec& ind = "");
00574 
00576   virtual ~LDPC_Generator_Systematic() {}
00577 
00579   virtual void encode(const bvec &input, bvec &output);
00580 
00614   ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
00615                  const ivec& ind = "");
00616 
00617 protected:
00619   virtual void save(const std::string& filename) const;
00621   virtual void load(const std::string& filename);
00622 
00623 private:
00624   GF2mat G; // the matrix is stored in transposed form
00625 };
00626 
00627 
00628 // ----------------------------------------------------------------------
00629 // BLDPC_Generator
00630 // ----------------------------------------------------------------------
00631 
00639 class BLDPC_Generator : public LDPC_Generator
00640 {
00641 public:
00643   BLDPC_Generator(const std::string type = "BLDPC"):
00644       LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
00646   BLDPC_Generator(const BLDPC_Parity* const H,
00647                   const std::string type = "BLDPC");
00648 
00650   int get_exp_factor() const { return Z; }
00651 
00653   void encode(const bvec &input, bvec &output);
00654 
00656   void construct(const BLDPC_Parity* const H);
00657 
00658 protected:
00660   void save(const std::string &filename) const;
00662   void load(const std::string &filename);
00663 
00664   GF2mat H_enc;  
00665   int N;   
00666   int M;       
00667   int K;   
00668   int Z;   
00669 };
00670 
00671 
00672 // ----------------------------------------------------------------------
00673 // LDPC_Code
00674 // ----------------------------------------------------------------------
00675 
00723 class LDPC_Code : public Channel_Code
00724 {
00725 public:
00727   LDPC_Code();
00728 
00735   LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00736 
00742   LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);
00743 
00745   virtual ~LDPC_Code() {}
00746 
00747 
00755   void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00756 
00770   void load_code(const std::string& filename, LDPC_Generator* const G = 0);
00771 
00780   void save_code(const std::string& filename) const;
00781 
00782 
00791   void set_decoding_method(const std::string& method);
00792 
00806   void set_exit_conditions(int max_iters,
00807                            bool syndr_check_each_iter = true,
00808                            bool syndr_check_at_start = false);
00809 
00811   void set_llrcalc(const LLR_calc_unit& llrcalc);
00812 
00813 
00814   // ------------ Encoding  ---------------------
00815 
00825   virtual void encode(const bvec &input, bvec &output);
00827   virtual bvec encode(const bvec &input);
00828 
00829 
00830   // ------------ Decoding  ---------------------
00831 
00833   virtual void decode(const bvec &, bvec &) {
00834     it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00835   }
00837   virtual bvec decode(const bvec &) {
00838     it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00839     return bvec();
00840   }
00841 
00843   virtual void decode(const vec &llr_in, bvec &syst_bits);
00845   virtual bvec decode(const vec &llr_in);
00846 
00848   void decode_soft_out(const vec &llr_in, vec &llr_out);
00850   vec decode_soft_out(const vec &llr_in);
00851 
00874   int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);
00875 
00884   bool syndrome_check(const QLLRvec &LLR) const;
00885 
00887   bool syndrome_check(const bvec &b) const;
00888 
00889   // ------------ Basic information gathering functions ------
00890 
00892   double get_rate() const {
00893     return (1.0 - static_cast<double>(ncheck) / nvar);
00894   }
00895 
00897   int get_nvar() const { return nvar; }
00898 
00900   int get_ncheck() const { return ncheck; }
00901 
00903   std::string get_decoding_method() const { return dec_method; }
00904 
00906   int get_nrof_iterations() const { return max_iters; }
00907 
00909   LLR_calc_unit get_llrcalc() const { return llrcalc; }
00910 
00912   friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00913 
00914 protected:
00915   bool H_defined;  
00916   bool G_defined;  
00917   int nvar;   
00918   int ncheck;   
00919   LDPC_Generator *G;  
00920 
00921   // decoder parameters
00922   std::string dec_method; 
00923   int max_iters;  
00924   bool psc;   
00925   bool pisc;   
00926   LLR_calc_unit llrcalc; 
00927 
00929   void decoder_parameterization(const LDPC_Parity* const H);
00930 
00932   void integrity_check();
00933 
00935   void setup_decoder();
00936 
00937 private:
00938   // Parity check matrix parameterization
00939   ivec C, V, sumX1, sumX2, iind, jind;
00940 
00941   // temporary storage for decoder (memory allocated when codec defined)
00942   QLLRvec mvc, mcv;
00943 };
00944 
00945 
00950 std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00951 }
00952 
00953 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Wed Feb 9 2011 13:47:16 for IT++ by Doxygen 1.7.3