IT++ Logo
ldpc.h
Go to the documentation of this file.
00001 
00029 #ifndef LDPC_H
00030 #define LDPC_H
00031 
00032 #include <iostream>
00033 #include <itpp/base/gf2mat.h>
00034 #include <itpp/base/random.h>
00035 #include <itpp/base/sort.h>
00036 #include <itpp/comm/llr.h>
00037 #include <itpp/comm/channel_code.h>
00038 
00039 namespace itpp
00040 {
00041 
00042 // ---------------------------------------------------------------------------
00043 // LDPC_Parity
00044 // ---------------------------------------------------------------------------
00045 
00070 class LDPC_Parity
00071 {
00072   friend class LDPC_Code;
00073 public:
00075   LDPC_Parity(): init_flag(false) {}
00076 
00078   LDPC_Parity(int ncheck, int nvar);
00079 
00091   LDPC_Parity(const std::string& filename, const std::string& format);
00092 
00094   LDPC_Parity(const GF2mat_sparse_alist& alist);
00095 
00097   virtual ~LDPC_Parity() {}
00098 
00100   void initialize(int ncheck, int nvar);
00101 
00103   GF2mat_sparse get_H(bool transpose = false) const {
00104     return (transpose ? Ht : H);
00105   }
00106 
00108   Sparse_Vec<bin> get_col(int c) const { return H.get_col(c); }
00109 
00111   Sparse_Vec<bin> get_row(int r) const { return Ht.get_col(r); }
00112 
00114   int get_nvar() const {
00115     it_assert_debug(H.cols() == nvar,
00116                     "LDPC_Parity::get_nvar(): Internal error");
00117     it_assert_debug(Ht.rows() == nvar,
00118                     "LDPC_Parity::get_nvar(): Internal error");
00119     return nvar;
00120   }
00121 
00123   int get_ncheck() const {
00124     it_assert_debug(H.rows() == ncheck,
00125                     "LDPC_Parity::get_ncheck(): Internal error");
00126     it_assert_debug(Ht.cols() == ncheck,
00127                     "LDPC_Parity::get_ncheck(): Internal error");
00128     return ncheck;
00129   }
00130 
00132   void set(int i, int j, bin value);
00133 
00135   bin get(int i, int j) const {
00136     it_assert_debug(H(i, j) == Ht(j, i), "LDPC_Parity::get(): Internal error");
00137     return H(i, j);
00138   }
00139 
00141   bin operator()(int i, int j) const {
00142     it_assert_debug(H(i, j) == Ht(j, i),
00143                     "LDPC_Parity::operator(): Internal error");
00144     return H(i, j);
00145   }
00146 
00148   virtual void display_stats() const;
00149 
00151   double get_rate() const {
00152     return (1.0 - static_cast<double>(ncheck) / nvar);
00153   }
00154 
00156   void import_alist(const GF2mat_sparse_alist& H_alist);
00157 
00159   GF2mat_sparse_alist export_alist() const;
00160 
00162   void load_alist(const std::string& alist_file);
00163 
00165   void save_alist(const std::string& alist_file) const;
00166 
00167 protected:
00169   bool init_flag;
00171   static const int Nmax = 200;
00173   GF2mat_sparse H;
00175   GF2mat_sparse Ht;
00177   int nvar;
00179   int ncheck;
00181   ivec sumX1;
00183   ivec sumX2;
00184 
00200   int check_for_cycles(int L) const;
00201 
00245   int check_connectivity(int from_m, int from_n, int to_m, int to_n,
00246                          int g, int L) const;
00247 
00248   //      inline int get_cmax() const {   return (max(sumX1));  }
00249   //      inline int get_vmax() const {   return (max(sumX2));  }
00250   //      ivec get_coldegree() const;
00251   //      ivec get_rowdegree() const;
00252 };
00253 
00254 
00255 // ----------------------------------------------------------------------
00256 // LDPC_Parity_Unstructured
00257 // ----------------------------------------------------------------------
00258 
00274 class LDPC_Parity_Unstructured : public LDPC_Parity
00275 {
00276 public:
00278   virtual void display_stats() const = 0;
00279 
00298   int cycle_removal_MGW(int L);
00299 
00300 protected:
00302   void generate_random_H(const ivec& C, const ivec& R, const ivec& cycopt);
00303 
00317   void compute_CR(const vec& var_deg, const vec& chk_deg, const int Nvar,
00318                   ivec &C, ivec &R);
00319 
00320 };
00321 
00322 
00323 // ----------------------------------------------------------------------
00324 // LDPC_Parity_Irregular
00325 // ----------------------------------------------------------------------
00326 
00331 class LDPC_Parity_Irregular : public LDPC_Parity_Unstructured
00332 {
00333 public:
00335   LDPC_Parity_Irregular() {}
00337   LDPC_Parity_Irregular(int Nvar, const vec& var_deg, const vec& chk_deg,
00338                         const std::string& method = "rand",
00339                         const ivec& options = "200 6");
00340 
00379   void generate(int Nvar, const vec& var_deg, const vec& chk_deg,
00380                 const std::string& method = "rand",
00381                 const ivec& options = "200 6");
00382 
00384   void display_stats() const { LDPC_Parity::display_stats(); }
00385 };
00386 
00387 
00388 // ----------------------------------------------------------------------
00389 // LDPC_Parity_Regular
00390 // ----------------------------------------------------------------------
00391 
00396 class LDPC_Parity_Regular : public LDPC_Parity_Unstructured
00397 {
00398 public:
00400   LDPC_Parity_Regular() {}
00402   LDPC_Parity_Regular(int Nvar, int k, int l,
00403                       const std::string& method = "rand",
00404                       const ivec& options = "200 6");
00405 
00424   void generate(int Nvar, int k, int l,
00425                 const std::string& method = "rand",
00426                 const ivec& options = "200 6");
00427 
00429   void display_stats() const { LDPC_Parity::display_stats(); }
00430 };
00431 
00432 // ----------------------------------------------------------------------
00433 // BLDPC_Parity
00434 // ----------------------------------------------------------------------
00435 
00460 class BLDPC_Parity : public LDPC_Parity
00461 {
00462 public:
00464   BLDPC_Parity(): LDPC_Parity(), Z(0), H_b(), H_b_valid(false) {}
00465 
00467   BLDPC_Parity(const imat &base_matrix, int exp_factor);
00468 
00470   BLDPC_Parity(const std::string &filename, int exp_factor);
00471 
00473   void expand_base(const imat &base_matrix, int exp_factor);
00474 
00476   int get_exp_factor() const;
00477 
00479   imat get_base_matrix() const;
00480 
00482   bool is_valid() const { return H_b_valid && init_flag; }
00483 
00485   void set_exp_factor(int exp_factor);
00486 
00488   void load_base_matrix(const std::string &filename);
00489 
00491   void save_base_matrix(const std::string &filename) const;
00492 
00493 private:
00494   int Z;   
00495   imat H_b;   
00496   bool H_b_valid;  
00497 
00499   void calculate_base_matrix();
00500 };
00501 
00502 
00503 // ----------------------------------------------------------------------
00504 // LDPC_Generator
00505 // ----------------------------------------------------------------------
00506 
00522 class LDPC_Generator
00523 {
00524   friend class LDPC_Code;
00525 public:
00527   LDPC_Generator(const std::string& type_in = ""): init_flag(false),
00528       type(type_in) {}
00530   virtual ~LDPC_Generator() {}
00531 
00533   virtual void encode(const bvec &input, bvec &output) = 0;
00534 
00536   std::string get_type() const { return type; }
00537 
00538 protected:
00539   bool init_flag;  
00540   std::string type;  
00541 
00543   virtual void save(const std::string& filename) const = 0;
00545   virtual void load(const std::string& filename) = 0;
00546 };
00547 
00548 
00549 // ----------------------------------------------------------------------
00550 // LDPC_Generator_Systematic
00551 // ----------------------------------------------------------------------
00552 
00564 class LDPC_Generator_Systematic : public LDPC_Generator
00565 {
00566 public:
00568   LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
00570   LDPC_Generator_Systematic(LDPC_Parity* const H,
00571                             bool natural_ordering = false,
00572                             const ivec& ind = "");
00573 
00575   virtual ~LDPC_Generator_Systematic() {}
00576 
00578   virtual void encode(const bvec &input, bvec &output);
00579 
00613   ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
00614                  const ivec& ind = "");
00615 
00616 protected:
00618   virtual void save(const std::string& filename) const;
00620   virtual void load(const std::string& filename);
00621 
00622 private:
00623   GF2mat G; // the matrix is stored in transposed form
00624 };
00625 
00626 
00627 // ----------------------------------------------------------------------
00628 // BLDPC_Generator
00629 // ----------------------------------------------------------------------
00630 
00638 class BLDPC_Generator : public LDPC_Generator
00639 {
00640 public:
00642   BLDPC_Generator(const std::string type = "BLDPC"):
00643       LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
00645   BLDPC_Generator(const BLDPC_Parity* const H,
00646                   const std::string type = "BLDPC");
00647 
00649   int get_exp_factor() const { return Z; }
00650 
00652   void encode(const bvec &input, bvec &output);
00653 
00655   void construct(const BLDPC_Parity* const H);
00656 
00657 protected:
00659   void save(const std::string &filename) const;
00661   void load(const std::string &filename);
00662 
00663   GF2mat H_enc;  
00664   int N;   
00665   int M;       
00666   int K;   
00667   int Z;   
00668 };
00669 
00670 
00671 // ----------------------------------------------------------------------
00672 // LDPC_Code
00673 // ----------------------------------------------------------------------
00674 
00725 class LDPC_Code : public Channel_Code
00726 {
00727 public:
00729   LDPC_Code();
00730 
00737   LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00738 
00744   LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);
00745 
00747   virtual ~LDPC_Code() {}
00748 
00749 
00757   void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00758 
00772   void load_code(const std::string& filename, LDPC_Generator* const G = 0);
00773 
00782   void save_code(const std::string& filename) const;
00783 
00784 
00793   void set_decoding_method(const std::string& method);
00794 
00808   void set_exit_conditions(int max_iters,
00809                            bool syndr_check_each_iter = true,
00810                            bool syndr_check_at_start = false);
00811 
00813   void set_llrcalc(const LLR_calc_unit& llrcalc);
00814 
00815 
00816   // ------------ Encoding  ---------------------
00817 
00827   virtual void encode(const bvec &input, bvec &output);
00829   virtual bvec encode(const bvec &input);
00830 
00831 
00832   // ------------ Decoding  ---------------------
00833 
00835   virtual void decode(const bvec &, bvec &) {
00836     it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00837   }
00839   virtual bvec decode(const bvec &) {
00840     it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00841     return bvec();
00842   }
00843 
00845   virtual void decode(const vec &llr_in, bvec &syst_bits);
00847   virtual bvec decode(const vec &llr_in);
00848 
00850   void decode_soft_out(const vec &llr_in, vec &llr_out);
00852   vec decode_soft_out(const vec &llr_in);
00853 
00876   int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);
00877 
00886   bool syndrome_check(const QLLRvec &LLR) const;
00887 
00889   bool syndrome_check(const bvec &b) const;
00890 
00891   // ------------ Basic information gathering functions ------
00892 
00894   double get_rate() const {
00895     return (1.0 - static_cast<double>(ncheck) / nvar);
00896   }
00897 
00899   int get_nvar() const { return nvar; }
00900 
00902   int get_ncheck() const { return ncheck; }
00903 
00905   int get_ninfo() const { return nvar - ncheck; }
00906 
00908   std::string get_decoding_method() const { return dec_method; }
00909 
00911   int get_nrof_iterations() const { return max_iters; }
00912 
00914   LLR_calc_unit get_llrcalc() const { return llrcalc; }
00915 
00917   friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00918 
00919 protected:
00920   bool H_defined;  
00921   bool G_defined;  
00922   int nvar;   
00923   int ncheck;   
00924   LDPC_Generator *G;  
00925 
00926   // decoder parameters
00927   std::string dec_method; 
00928   int max_iters;  
00929   bool psc;   
00930   bool pisc;   
00931   LLR_calc_unit llrcalc; 
00932 
00934   void decoder_parameterization(const LDPC_Parity* const H);
00935 
00937   void integrity_check();
00938 
00940   void setup_decoder();
00941 
00942 private:
00943   // Parity check matrix parameterization
00944   ivec C, V, sumX1, sumX2, iind, jind;
00945 
00946   // temporary storage for decoder (memory allocated when codec defined)
00947   QLLRvec mvc, mcv;
00948 
00950   static const int max_cnd = 200;
00951 };
00952 
00953 
00958 std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00959 }
00960 
00961 #endif
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines
SourceForge Logo

Generated on Wed Jul 27 2011 16:27:05 for IT++ by Doxygen 1.7.4