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   // LDPC_Parity
00044   // ---------------------------------------------------------------------------
00045 
00070   class LDPC_Parity {
00071     friend class LDPC_Code;
00072   public:
00074     LDPC_Parity(): init_flag(false) {}
00075 
00077     LDPC_Parity(int ncheck, int nvar);
00078 
00090     LDPC_Parity(const std::string& filename, const std::string& format);
00091 
00093     LDPC_Parity(const GF2mat_sparse_alist& alist);
00094 
00096     virtual ~LDPC_Parity() {}
00097 
00099     void initialize(int ncheck, int nvar);
00100 
00102     GF2mat_sparse get_H(bool transpose = false) const {
00103       return (transpose ? Ht : H);
00104     }
00105 
00107     Sparse_Vec<bin> get_col(int c) const { return H.get_col(c); }
00108 
00110     Sparse_Vec<bin> get_row(int r) const { return Ht.get_col(r); }
00111 
00113     int get_nvar() const {
00114       it_assert_debug(H.cols() == nvar,
00115                       "LDPC_Parity::get_nvar(): Internal error");
00116       it_assert_debug(Ht.rows() == nvar,
00117                       "LDPC_Parity::get_nvar(): Internal error");
00118       return nvar;
00119     }
00120 
00122     int get_ncheck() const {
00123       it_assert_debug(H.rows() == ncheck,
00124                       "LDPC_Parity::get_ncheck(): Internal error");
00125       it_assert_debug(Ht.cols() == ncheck,
00126                       "LDPC_Parity::get_ncheck(): Internal error");
00127       return ncheck;
00128     }
00129 
00131     void set(int i, int j, bin value);
00132 
00134     bin get(int i, int j) const {
00135       it_assert_debug(H(i,j) == Ht(j,i), "LDPC_Parity::get(): Internal error");
00136       return H(i,j);
00137     }
00138 
00140     bin operator()(int i, int j) const {
00141       it_assert_debug(H(i,j) == Ht(j,i),
00142                       "LDPC_Parity::operator(): Internal error");
00143       return H(i,j);
00144     }
00145 
00147     virtual void display_stats() const;
00148 
00150     double get_rate() const {
00151       return   (1.0 - static_cast<double>(ncheck) / nvar);
00152     }
00153 
00155     void import_alist(const GF2mat_sparse_alist& H_alist);
00156 
00158     GF2mat_sparse_alist export_alist() const;
00159 
00161     void load_alist(const std::string& alist_file);
00162 
00164     void save_alist(const std::string& alist_file) const;
00165 
00166   protected:
00168     bool init_flag;
00170     static const int Nmax = 200;
00172     GF2mat_sparse H;
00174     GF2mat_sparse Ht;
00176     int nvar;
00178     int ncheck;
00180     ivec sumX1;
00182     ivec sumX2;
00183 
00199     int check_for_cycles(int L) const;
00200 
00244     int check_connectivity(int from_m, int from_n, int to_m, int to_n,
00245                            int g, int L) const;
00246 
00247     //      inline int get_cmax() const {   return (max(sumX1));  }
00248     //      inline int get_vmax() const {   return (max(sumX2));  }
00249     //      ivec get_coldegree() const;
00250     //      ivec get_rowdegree() const;
00251   };
00252 
00253 
00254   // ----------------------------------------------------------------------
00255   // LDPC_Parity_Unstructured
00256   // ----------------------------------------------------------------------
00257 
00273   class LDPC_Parity_Unstructured : public LDPC_Parity {
00274   public:
00276     virtual void display_stats() const = 0;
00277 
00296     int cycle_removal_MGW(int L);
00297 
00298   protected:
00300     void generate_random_H(const ivec& C, const ivec& R, const ivec& cycopt);
00301 
00315     void compute_CR(const vec& var_deg, const vec& chk_deg, const int Nvar,
00316                     ivec &C, ivec &R);
00317 
00318   };
00319 
00320 
00321   // ----------------------------------------------------------------------
00322   // LDPC_Parity_Irregular
00323   // ----------------------------------------------------------------------
00324 
00329   class LDPC_Parity_Irregular : public LDPC_Parity_Unstructured {
00330   public:
00332     LDPC_Parity_Irregular() {}
00334     LDPC_Parity_Irregular(int Nvar, const vec& var_deg, const vec& chk_deg,
00335                           const std::string& method = "rand",
00336                           const ivec& options = "200 6");
00337 
00376     void generate(int Nvar, const vec& var_deg, const vec& chk_deg,
00377                   const std::string& method = "rand",
00378                   const ivec& options = "200 6");
00379 
00381     void display_stats() const { LDPC_Parity::display_stats(); }
00382   };
00383 
00384 
00385   // ----------------------------------------------------------------------
00386   // LDPC_Parity_Regular
00387   // ----------------------------------------------------------------------
00388 
00393   class LDPC_Parity_Regular : public LDPC_Parity_Unstructured {
00394   public:
00396     LDPC_Parity_Regular() {}
00398     LDPC_Parity_Regular(int Nvar, int k, int l,
00399                         const std::string& method = "rand",
00400                         const ivec& options = "200 6");
00401 
00420     void generate(int Nvar, int k, int l,
00421                   const std::string& method = "rand",
00422                   const ivec& options = "200 6");
00423 
00425     void display_stats() const { LDPC_Parity::display_stats(); }
00426   };
00427 
00428   // ----------------------------------------------------------------------
00429   // BLDPC_Parity
00430   // ----------------------------------------------------------------------
00431 
00456   class BLDPC_Parity : public LDPC_Parity {
00457   public:
00459     BLDPC_Parity(): LDPC_Parity(), Z(0), H_b(), H_b_valid(false) {}
00460 
00462     BLDPC_Parity(const imat &base_matrix, int exp_factor);
00463 
00465     BLDPC_Parity(const std::string &filename, int exp_factor);
00466 
00468     void expand_base(const imat &base_matrix, int exp_factor);
00469 
00471     int get_exp_factor() const;
00472 
00474     imat get_base_matrix() const;
00475 
00477     bool is_valid() const { return H_b_valid && init_flag; }
00478 
00480     void set_exp_factor(int exp_factor);
00481 
00483     void load_base_matrix(const std::string &filename);
00484 
00486     void save_base_matrix(const std::string &filename) const;
00487 
00488   private:
00489     int Z;                      
00490     imat H_b;                   
00491     bool H_b_valid;             
00492 
00494     void calculate_base_matrix();
00495   };
00496 
00497 
00498   // ----------------------------------------------------------------------
00499   // LDPC_Generator
00500   // ----------------------------------------------------------------------
00501 
00517   class LDPC_Generator {
00518     friend class LDPC_Code;
00519   public:
00521     LDPC_Generator(const std::string& type_in = ""): init_flag(false),
00522                                                      type(type_in) {}
00524     virtual ~LDPC_Generator() {}
00525 
00527     virtual void encode(const bvec &input, bvec &output) = 0;
00528 
00530     std::string get_type() const { return type; }
00531 
00532   protected:
00533     bool init_flag;             
00534     std::string type;           
00535 
00537     virtual void save(const std::string& filename) const = 0;
00539     virtual void load(const std::string& filename) = 0;
00540   };
00541 
00542 
00543   // ----------------------------------------------------------------------
00544   // LDPC_Generator_Systematic
00545   // ----------------------------------------------------------------------
00546 
00558   class LDPC_Generator_Systematic : public LDPC_Generator {
00559   public:
00561     LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
00563     LDPC_Generator_Systematic(LDPC_Parity* const H,
00564                               bool natural_ordering = false,
00565                               const ivec& ind = "");
00566 
00568     virtual ~LDPC_Generator_Systematic() {}
00569 
00571     virtual void encode(const bvec &input, bvec &output);
00572 
00606     ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
00607                    const ivec& ind = "");
00608 
00609   protected:
00611     virtual void save(const std::string& filename) const;
00613     virtual void load(const std::string& filename);
00614 
00615   private:
00616     GF2mat G; // the matrix is stored in transposed form
00617   };
00618 
00619 
00620   // ----------------------------------------------------------------------
00621   // BLDPC_Generator
00622   // ----------------------------------------------------------------------
00623 
00631   class BLDPC_Generator : public LDPC_Generator {
00632   public:
00634     BLDPC_Generator(const std::string type = "BLDPC"):
00635       LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
00637     BLDPC_Generator(const BLDPC_Parity* const H,
00638                     const std::string type = "BLDPC");
00639 
00641     int get_exp_factor() const { return Z; }
00642 
00644     void encode(const bvec &input, bvec &output);
00645 
00647     void construct(const BLDPC_Parity* const H);
00648 
00649   protected:
00651     void save(const std::string &filename) const;
00653     void load(const std::string &filename);
00654 
00655     GF2mat H_enc;               
00656     int N;                      
00657     int M;                   
00658     int K;                      
00659     int Z;                      
00660   };
00661 
00662 
00663   // ----------------------------------------------------------------------
00664   // LDPC_Code
00665   // ----------------------------------------------------------------------
00666 
00714   class LDPC_Code : public Channel_Code {
00715   public:
00717     LDPC_Code();
00718 
00725     LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00726 
00732     LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);
00733 
00735     virtual ~LDPC_Code() {}
00736 
00737 
00745     void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00746 
00760     void load_code(const std::string& filename, LDPC_Generator* const G = 0);
00761 
00770     void save_code(const std::string& filename) const;
00771 
00772 
00781     void set_decoding_method(const std::string& method);
00782 
00796     void set_exit_conditions(int max_iters,
00797                              bool syndr_check_each_iter = true,
00798                              bool syndr_check_at_start = false);
00799 
00801     void set_llrcalc(const LLR_calc_unit& llrcalc);
00802 
00803 
00804     // ------------ Encoding  ---------------------
00805 
00815     virtual void encode(const bvec &input, bvec &output);
00817     virtual bvec encode(const bvec &input);
00818 
00819 
00820     // ------------ Decoding  ---------------------
00821 
00823     virtual void decode(const bvec &coded_bits, bvec &decoded_bits)
00824     {
00825       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00826     }
00828     virtual bvec decode(const bvec &coded_bits)
00829     {
00830       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00831       return bvec();
00832     }
00833 
00835     virtual void decode(const vec &llr_in, bvec &syst_bits);
00837     virtual bvec decode(const vec &llr_in);
00838 
00840     void decode_soft_out(const vec &llr_in, vec &llr_out);
00842     vec decode_soft_out(const vec &llr_in);
00843 
00866     int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);
00867 
00876     bool syndrome_check(const QLLRvec &LLR) const;
00877 
00879     bool syndrome_check(const bvec &b) const;
00880 
00881     // ------------ Basic information gathering functions ------
00882 
00884     double get_rate() const
00885     {
00886       return (1.0 - static_cast<double>(ncheck) / nvar);
00887     }
00888 
00890     int get_nvar() const { return nvar; }
00891 
00893     int get_ncheck() const { return ncheck; }
00894 
00896     std::string get_decoding_method() const { return dec_method; }
00897 
00899     int get_nrof_iterations() const { return max_iters; }
00900 
00902     LLR_calc_unit get_llrcalc() const { return llrcalc; }
00903 
00905     friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00906 
00907   protected:
00908     bool H_defined;             
00909     bool G_defined;             
00910     int nvar;                   
00911     int ncheck;                 
00912     LDPC_Generator *G;          
00913 
00914     // decoder parameters
00915     std::string dec_method;     
00916     int max_iters;              
00917     bool psc;                   
00918     bool pisc;                  
00919     LLR_calc_unit llrcalc;      
00920 
00922     void decoder_parameterization(const LDPC_Parity* const H);
00923 
00925     void integrity_check();
00926 
00928     void setup_decoder();
00929 
00930   private:
00931     // Parity check matrix parameterization
00932     ivec C, V, sumX1, sumX2, iind, jind;
00933 
00934     // temporary storage for decoder (memory allocated when codec defined)
00935     QLLRvec mvc, mcv;
00936   };
00937 
00938 
00943   std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00944 }
00945 
00946 #endif
SourceForge Logo

Generated on Sat Apr 19 10:41:56 2008 for IT++ by Doxygen 1.5.5