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     bmat circular_eye_b(int size, int shift);
00495 
00497     void calculate_base_matrix();
00498   };
00499 
00500 
00501   // ----------------------------------------------------------------------
00502   // LDPC_Generator
00503   // ----------------------------------------------------------------------
00504 
00520   class LDPC_Generator {
00521     friend class LDPC_Code;
00522   public:
00524     LDPC_Generator(const std::string& type_in = ""): init_flag(false),
00525                                                      type(type_in) {}
00527     virtual ~LDPC_Generator() {}
00528 
00530     virtual void encode(const bvec &input, bvec &output) = 0;
00531 
00533     std::string get_type() const { return type; }
00534 
00535   protected:
00536     bool init_flag;             
00537     std::string type;           
00538 
00540     virtual void save(const std::string& filename) const = 0;
00542     virtual void load(const std::string& filename) = 0;
00543   };
00544 
00545 
00546   // ----------------------------------------------------------------------
00547   // LDPC_Generator_Systematic
00548   // ----------------------------------------------------------------------
00549 
00561   class LDPC_Generator_Systematic : public LDPC_Generator {
00562   public:
00564     LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
00566     LDPC_Generator_Systematic(LDPC_Parity* const H,
00567                               bool natural_ordering = false,
00568                               const ivec& ind = "");
00569 
00571     virtual ~LDPC_Generator_Systematic() {}
00572 
00574     virtual void encode(const bvec &input, bvec &output);
00575 
00609     ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
00610                    const ivec& ind = "");
00611 
00612   protected:
00614     virtual void save(const std::string& filename) const;
00616     virtual void load(const std::string& filename);
00617 
00618   private:
00619     GF2mat G; // the matrix is stored in transposed form
00620   };
00621 
00622 
00623   // ----------------------------------------------------------------------
00624   // BLDPC_Generator
00625   // ----------------------------------------------------------------------
00626 
00634   class BLDPC_Generator : public LDPC_Generator {
00635   public:
00637     BLDPC_Generator(const std::string type = "BLDPC"):
00638       LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
00640     BLDPC_Generator(const BLDPC_Parity* const H,
00641                     const std::string type = "BLDPC");
00642 
00644     int get_exp_factor() const { return Z; }
00645 
00647     void encode(const bvec &input, bvec &output);
00648 
00650     void construct(const BLDPC_Parity* const H);
00651 
00652   protected:
00654     void save(const std::string &filename) const;
00656     void load(const std::string &filename);
00657 
00658     GF2mat H_enc;               
00659     int N;                      
00660     int M;                   
00661     int K;                      
00662     int Z;                      
00663   };
00664 
00665 
00666   // ----------------------------------------------------------------------
00667   // LDPC_Code
00668   // ----------------------------------------------------------------------
00669 
00717   class LDPC_Code : public Channel_Code {
00718   public:
00720     LDPC_Code();
00721 
00728     LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00729 
00735     LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);
00736 
00738     virtual ~LDPC_Code() {}
00739 
00740 
00748     void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00749 
00763     void load_code(const std::string& filename, LDPC_Generator* const G = 0);
00764 
00773     void save_code(const std::string& filename) const;
00774 
00775 
00784     void set_decoding_method(const std::string& method);
00785 
00799     void set_exit_conditions(int max_iters,
00800                              bool syndr_check_each_iter = true,
00801                              bool syndr_check_at_start = false);
00802 
00804     void set_llrcalc(const LLR_calc_unit& llrcalc);
00805 
00806 
00807     // ------------ Encoding  ---------------------
00808 
00818     virtual void encode(const bvec &input, bvec &output);
00820     virtual bvec encode(const bvec &input);
00821 
00822 
00823     // ------------ Decoding  ---------------------
00824 
00826     virtual void decode(const bvec &coded_bits, bvec &decoded_bits)
00827     {
00828       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00829     }
00831     virtual bvec decode(const bvec &coded_bits)
00832     {
00833       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00834       return bvec();
00835     }
00836 
00838     virtual void decode(const vec &llr_in, bvec &syst_bits);
00840     virtual bvec decode(const vec &llr_in);
00841 
00843     void decode_soft_out(const vec &llr_in, vec &llr_out);
00845     vec decode_soft_out(const vec &llr_in);
00846 
00869     int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);
00870 
00879     bool syndrome_check(const QLLRvec &LLR) const;
00880 
00882     bool syndrome_check(const bvec &b) const;
00883 
00884     // ------------ Basic information gathering functions ------
00885 
00887     double get_rate() const
00888     {
00889       return (1.0 - static_cast<double>(ncheck) / nvar);
00890     }
00891 
00893     int get_nvar() const { return nvar; }
00894 
00896     int get_ncheck() const { return ncheck; }
00897 
00899     std::string get_decoding_method() const { return dec_method; }
00900 
00902     int get_nrof_iterations() const { return max_iters; }
00903 
00905     LLR_calc_unit get_llrcalc() const { return llrcalc; }
00906 
00908     friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00909 
00910   protected:
00911     bool H_defined;             
00912     bool G_defined;             
00913     int nvar;                   
00914     int ncheck;                 
00915     LDPC_Generator *G;          
00916 
00917     // decoder parameters
00918     std::string dec_method;     
00919     int max_iters;              
00920     bool psc;                   
00921     bool pisc;                  
00922     LLR_calc_unit llrcalc;      
00923 
00925     void decoder_parameterization(const LDPC_Parity* const H);
00926 
00928     void integrity_check();
00929 
00931     void setup_decoder();
00932 
00933   private:
00934     // Parity check matrix parameterization
00935     ivec C, V, sumX1, sumX2, iind, jind;
00936 
00937     // temporary storage for decoder (memory allocated when codec defined)
00938     QLLRvec mvc, mcv;
00939   };
00940 
00941 
00946   std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00947 }
00948 
00949 #endif
SourceForge Logo

Generated on Mon Jan 7 22:28:57 2008 for IT++ by Doxygen 1.5.4