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
Generated on Mon Jan 7 22:28:57 2008 for IT++ by Doxygen 1.5.4