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 00726 class LDPC_Code : public Channel_Code 00727 { 00728 public: 00730 LDPC_Code(); 00731 00738 LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0); 00739 00745 LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0); 00746 00748 virtual ~LDPC_Code() {} 00749 00750 00758 void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0); 00759 00773 void load_code(const std::string& filename, LDPC_Generator* const G = 0); 00774 00783 void save_code(const std::string& filename) const; 00784 00785 00794 void set_decoding_method(const std::string& method); 00795 00809 void set_exit_conditions(int max_iters, 00810 bool syndr_check_each_iter = true, 00811 bool syndr_check_at_start = false); 00812 00814 void set_llrcalc(const LLR_calc_unit& llrcalc); 00815 00816 00817 // ------------ Encoding --------------------- 00818 00828 virtual void encode(const bvec &input, bvec &output); 00830 virtual bvec encode(const bvec &input); 00831 00832 00833 // ------------ Decoding --------------------- 00834 00836 virtual void decode(const bvec &, bvec &) { 00837 it_error("LDPC_Code::decode(): Hard input decoding not implemented"); 00838 } 00840 virtual bvec decode(const bvec &) { 00841 it_error("LDPC_Code::decode(): Hard input decoding not implemented"); 00842 return bvec(); 00843 } 00844 00846 virtual void decode(const vec &llr_in, bvec &syst_bits); 00848 virtual bvec decode(const vec &llr_in); 00849 00851 void decode_soft_out(const vec &llr_in, vec &llr_out); 00853 vec decode_soft_out(const vec &llr_in); 00854 00877 int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout); 00878 00887 bool syndrome_check(const QLLRvec &LLR) const; 00888 00890 bool syndrome_check(const bvec &b) const; 00891 00892 // ------------ Basic information gathering functions ------ 00893 00895 double get_rate() const { 00896 return (1.0 - static_cast<double>(ncheck) / nvar); 00897 } 00898 00900 int get_nvar() const { return nvar; } 00901 00903 int get_ncheck() const { return ncheck; } 00904 00906 std::string get_decoding_method() const { return dec_method; } 00907 00909 int get_nrof_iterations() const { return max_iters; } 00910 00912 LLR_calc_unit get_llrcalc() const { return llrcalc; } 00913 00915 friend std::ostream &operator<<(std::ostream &os, const LDPC_Code &C); 00916 00917 protected: 00918 bool H_defined; 00919 bool G_defined; 00920 int nvar; 00921 int ncheck; 00922 LDPC_Generator *G; 00923 00924 // decoder parameters 00925 std::string dec_method; 00926 int max_iters; 00927 bool psc; 00928 bool pisc; 00929 LLR_calc_unit llrcalc; 00930 00932 void decoder_parameterization(const LDPC_Parity* const H); 00933 00935 void integrity_check(); 00936 00938 void setup_decoder(); 00939 00940 private: 00941 // Parity check matrix parameterization 00942 ivec C, V, sumX1, sumX2, iind, jind; 00943 00944 // temporary storage for decoder (memory allocated when codec defined) 00945 QLLRvec mvc, mcv; 00946 }; 00947 00948 00953 std::ostream &operator<<(std::ostream &os, const LDPC_Code &C); 00954 } 00955 00956 #endif
Generated on Wed Jan 20 23:03:05 2010 for IT++ by Doxygen 1.6.2