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   };
00302 
00303 
00304   // ----------------------------------------------------------------------
00305   // LDPC_Parity_Irregular
00306   // ----------------------------------------------------------------------
00307 
00312   class LDPC_Parity_Irregular : public LDPC_Parity_Unstructured {
00313   public:
00315     LDPC_Parity_Irregular() {}
00317     LDPC_Parity_Irregular(int Nvar, const vec& var_deg, const vec& chk_deg,
00318         const std::string& method = "rand",
00319         const ivec& options = "200 6");
00320 
00359     void generate(int Nvar, const vec& var_deg, const vec& chk_deg,
00360       const std::string& method = "rand",
00361       const ivec& options = "200 6");
00362 
00364     void display_stats() const { LDPC_Parity::display_stats(); }
00365   };
00366 
00367 
00368   // ----------------------------------------------------------------------
00369   // LDPC_Parity_Regular
00370   // ----------------------------------------------------------------------
00371 
00376   class LDPC_Parity_Regular : public LDPC_Parity_Unstructured {
00377   public:
00379     LDPC_Parity_Regular() {}
00381     LDPC_Parity_Regular(int Nvar, int k, int l,
00382       const std::string& method = "rand",
00383       const ivec& options = "200 6");
00384 
00397     void generate(int Nvar, int k, int l,
00398       const std::string& method = "rand",
00399       const ivec& options = "200 6");
00400 
00402     void display_stats() const { LDPC_Parity::display_stats(); }
00403   };
00404 
00405   // ----------------------------------------------------------------------
00406   // BLDPC_Parity
00407   // ----------------------------------------------------------------------
00408 
00433   class BLDPC_Parity : public LDPC_Parity {
00434   public:
00436     BLDPC_Parity(): LDPC_Parity(), Z(0), H_b(), H_b_valid(false) {}
00437 
00439     BLDPC_Parity(const imat &base_matrix, int exp_factor);
00440 
00442     BLDPC_Parity(const std::string &filename, int exp_factor);
00443 
00445     void expand_base(const imat &base_matrix, int exp_factor);
00446 
00448     int get_exp_factor() const;
00449 
00451     imat get_base_matrix() const;
00452 
00454     bool is_valid() const { return H_b_valid && init_flag; }
00455 
00457     void set_exp_factor(int exp_factor);
00458 
00460     void load_base_matrix(const std::string &filename);
00461 
00463     void save_base_matrix(const std::string &filename) const;
00464 
00465   private:
00466     int Z;      
00467     imat H_b;     
00468     bool H_b_valid;   
00469 
00471     bmat circular_eye_b(int size, int shift);
00472 
00474     void calculate_base_matrix();
00475   };
00476 
00477 
00478   // ----------------------------------------------------------------------
00479   // LDPC_Generator
00480   // ----------------------------------------------------------------------
00481 
00497   class LDPC_Generator {
00498     friend class LDPC_Code;
00499   public:
00501     LDPC_Generator(const std::string& type_in = ""): init_flag(false),
00502                  type(type_in) {}
00504     virtual ~LDPC_Generator() {}
00505 
00507     virtual void encode(const bvec &input, bvec &output) = 0;
00508 
00510     std::string get_type() const { return type; }
00511 
00512   protected:
00513     bool init_flag;   
00514     std::string type;   
00515 
00517     virtual void save(const std::string& filename) const = 0;
00519     virtual void load(const std::string& filename) = 0;
00520   };
00521 
00522 
00523   // ----------------------------------------------------------------------
00524   // LDPC_Generator_Systematic
00525   // ----------------------------------------------------------------------
00526 
00538   class LDPC_Generator_Systematic : public LDPC_Generator {
00539   public:
00541     LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
00543     LDPC_Generator_Systematic(LDPC_Parity* const H,
00544             bool natural_ordering = false,
00545             const ivec& ind = "");
00546 
00548     virtual ~LDPC_Generator_Systematic() {}
00549 
00551     virtual void encode(const bvec &input, bvec &output);
00552 
00586     ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
00587        const ivec& ind = "");
00588 
00589   protected:
00591     virtual void save(const std::string& filename) const;
00593     virtual void load(const std::string& filename);
00594 
00595   private:
00596     GF2mat G; // the matrix is stored in transposed form
00597   };
00598 
00599 
00600   // ----------------------------------------------------------------------
00601   // BLDPC_Generator
00602   // ----------------------------------------------------------------------
00603 
00611   class BLDPC_Generator : public LDPC_Generator {
00612   public:
00614     BLDPC_Generator(const std::string type = "BLDPC"):
00615       LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
00617     BLDPC_Generator(const BLDPC_Parity* const H,
00618         const std::string type = "BLDPC");
00619 
00621     int get_exp_factor() const { return Z; }
00622 
00624     void encode(const bvec &input, bvec &output);
00625 
00627     void construct(const BLDPC_Parity* const H);
00628 
00629   protected:
00631     void save(const std::string &filename) const;
00633     void load(const std::string &filename);
00634 
00635     GF2mat H_enc;   
00636     int N;      
00637     int M;         
00638     int K;      
00639     int Z;      
00640   };
00641 
00642 
00643   // ----------------------------------------------------------------------
00644   // LDPC_Code
00645   // ----------------------------------------------------------------------
00646 
00694   class LDPC_Code : public Channel_Code {
00695   public:
00697     LDPC_Code();
00698 
00705     LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00706 
00712     LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);
00713 
00715     virtual ~LDPC_Code() {}
00716 
00717 
00725     void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0);
00726 
00740     void load_code(const std::string& filename, LDPC_Generator* const G = 0);
00741 
00750     void save_code(const std::string& filename) const;
00751 
00752 
00761     void set_decoding_method(const std::string& method);
00762 
00776     void set_exit_conditions(int max_iters,
00777            bool syndr_check_each_iter = true,
00778            bool syndr_check_at_start = false);
00779 
00781     void set_llrcalc(const LLR_calc_unit& llrcalc);
00782 
00783 
00784     // ------------ Encoding  ---------------------
00785 
00795     virtual void encode(const bvec &input, bvec &output);
00797     virtual bvec encode(const bvec &input);
00798 
00799 
00800     // ------------ Decoding  ---------------------
00801 
00803     virtual void decode(const bvec &coded_bits, bvec &decoded_bits)
00804     {
00805       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00806     }
00808     virtual bvec decode(const bvec &coded_bits)
00809     {
00810       it_error("LDPC_Code::decode(): Hard input decoding not implemented");
00811       return bvec();
00812     }
00813 
00815     virtual void decode(const vec &llr_in, bvec &syst_bits);
00817     virtual bvec decode(const vec &llr_in);
00818 
00820     void decode_soft_out(const vec &llr_in, vec &llr_out);
00822     vec decode_soft_out(const vec &llr_in);
00823 
00846     int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);
00847 
00856     bool syndrome_check(const QLLRvec &LLR) const;
00857 
00859     bool syndrome_check(const bvec &b) const;
00860 
00861     // ------------ Basic information gathering functions ------
00862 
00864     double get_rate() const
00865     {
00866       return (1.0 - static_cast<double>(ncheck) / nvar);
00867     }
00868 
00870     int get_nvar() const { return nvar; }
00871 
00873     int get_ncheck() const { return ncheck; }
00874 
00876     std::string get_decoding_method() const { return dec_method; }
00877 
00879     int get_nrof_iterations() const { return max_iters; }
00880 
00882     LLR_calc_unit get_llrcalc() const { return llrcalc; }
00883 
00885     friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00886 
00887   protected:
00888     bool H_defined;   
00889     bool G_defined;   
00890     int nvar;     
00891     int ncheck;     
00892     LDPC_Generator *G;    
00893 
00894     // decoder parameters
00895     std::string dec_method; 
00896     int max_iters;    
00897     bool psc;     
00898     bool pisc;      
00899     LLR_calc_unit llrcalc;  
00900 
00902     void decoder_parameterization(const LDPC_Parity* const H);
00903 
00905     void integrity_check();
00906 
00908     void setup_decoder();
00909 
00910   private:
00911     // Parity check matrix parameterization
00912     ivec C, V, sumX1, sumX2, iind, jind;
00913 
00914     // temporary storage for decoder (memory allocated when codec defined)
00915     QLLRvec mvc, mcv;
00916   };
00917 
00918 
00923   std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
00924 }
00925 
00926 #endif
SourceForge Logo

Generated on Sun Dec 9 17:31:02 2007 for IT++ by Doxygen 1.5.4