ldpc.h

Go to the documentation of this file.

#ifndef LDPC_H
#define LDPC_H

#include <iostream>
#include <itpp/base/gf2mat.h>
#include <itpp/base/random.h>
#include <itpp/base/sort.h>
#include <itpp/comm/llr.h>
#include <itpp/comm/channel_code.h>
#include <itpp/itexports.h>

namespace itpp
{

// ---------------------------------------------------------------------------
// LDPC_Parity
// ---------------------------------------------------------------------------

class ITPP_EXPORT LDPC_Parity
{
  friend class LDPC_Code;
public:
  LDPC_Parity(): init_flag(false) {}

  LDPC_Parity(int ncheck, int nvar);

  LDPC_Parity(const std::string& filename, const std::string& format);

  LDPC_Parity(const GF2mat_sparse_alist& alist);

  virtual ~LDPC_Parity() {}

  void initialize(int ncheck, int nvar);

  GF2mat_sparse get_H(bool transpose = false) const {
    return (transpose ? Ht : H);
  }

  Sparse_Vec<bin> get_col(int c) const { return H.get_col(c); }

  Sparse_Vec<bin> get_row(int r) const { return Ht.get_col(r); }

  int get_nvar() const {
    it_assert_debug(H.cols() == nvar,
                    "LDPC_Parity::get_nvar(): Internal error");
    it_assert_debug(Ht.rows() == nvar,
                    "LDPC_Parity::get_nvar(): Internal error");
    return nvar;
  }

  int get_ncheck() const {
    it_assert_debug(H.rows() == ncheck,
                    "LDPC_Parity::get_ncheck(): Internal error");
    it_assert_debug(Ht.cols() == ncheck,
                    "LDPC_Parity::get_ncheck(): Internal error");
    return ncheck;
  }

  void set(int i, int j, bin value);

  bin get(int i, int j) const {
    it_assert_debug(H(i, j) == Ht(j, i), "LDPC_Parity::get(): Internal error");
    return H(i, j);
  }

  bin operator()(int i, int j) const {
    it_assert_debug(H(i, j) == Ht(j, i),
                    "LDPC_Parity::operator(): Internal error");
    return H(i, j);
  }

  virtual void display_stats() const;

  double get_rate() const {
    return (1.0 - static_cast<double>(ncheck) / nvar);
  }

  void import_alist(const GF2mat_sparse_alist& H_alist);

  GF2mat_sparse_alist export_alist() const;

  void load_alist(const std::string& alist_file);

  void save_alist(const std::string& alist_file) const;

protected:
  bool init_flag;
  static const int Nmax = 200;
  GF2mat_sparse H;
  GF2mat_sparse Ht;
  int nvar;
  int ncheck;
  ivec sumX1;
  ivec sumX2;

  int check_for_cycles(int L) const;

  int check_connectivity(int from_m, int from_n, int to_m, int to_n,
                         int g, int L) const;

  //      inline int get_cmax() const {   return (max(sumX1));  }
  //      inline int get_vmax() const {   return (max(sumX2));  }
  //      ivec get_coldegree() const;
  //      ivec get_rowdegree() const;
};


// ----------------------------------------------------------------------
// LDPC_Parity_Unstructured
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Parity_Unstructured : public LDPC_Parity
{
public:
  virtual void display_stats() const = 0;

  int cycle_removal_MGW(int L);

protected:
  void generate_random_H(const ivec& C, const ivec& R, const ivec& cycopt);

  void compute_CR(const vec& var_deg, const vec& chk_deg, const int Nvar,
                  ivec &C, ivec &R);

};


// ----------------------------------------------------------------------
// LDPC_Parity_Irregular
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Parity_Irregular : public LDPC_Parity_Unstructured
{
public:
  LDPC_Parity_Irregular() {}
  LDPC_Parity_Irregular(int Nvar, const vec& var_deg, const vec& chk_deg,
                        const std::string& method = "rand",
                        const ivec& options = "200 6");

  void generate(int Nvar, const vec& var_deg, const vec& chk_deg,
                const std::string& method = "rand",
                const ivec& options = "200 6");

  void display_stats() const { LDPC_Parity::display_stats(); }
};


// ----------------------------------------------------------------------
// LDPC_Parity_Regular
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Parity_Regular : public LDPC_Parity_Unstructured
{
public:
  LDPC_Parity_Regular() {}
  LDPC_Parity_Regular(int Nvar, int k, int l,
                      const std::string& method = "rand",
                      const ivec& options = "200 6");

  void generate(int Nvar, int k, int l,
                const std::string& method = "rand",
                const ivec& options = "200 6");

  void display_stats() const { LDPC_Parity::display_stats(); }
};

// ----------------------------------------------------------------------
// BLDPC_Parity
// ----------------------------------------------------------------------

class ITPP_EXPORT BLDPC_Parity : public LDPC_Parity
{
public:
  BLDPC_Parity(): LDPC_Parity(), Z(0), H_b(), H_b_valid(false) {}

  BLDPC_Parity(const imat &base_matrix, int exp_factor);

  BLDPC_Parity(const std::string &filename, int exp_factor);

  void expand_base(const imat &base_matrix, int exp_factor);

  int get_exp_factor() const;

  imat get_base_matrix() const;

  bool is_valid() const { return H_b_valid && init_flag; }

  void set_exp_factor(int exp_factor);

  void load_base_matrix(const std::string &filename);

  void save_base_matrix(const std::string &filename) const;

private:
  int Z;   
  imat H_b;   
  bool H_b_valid;  

  void calculate_base_matrix();
};


// ----------------------------------------------------------------------
// LDPC_Generator
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Generator
{
  friend class LDPC_Code;
public:
  LDPC_Generator(const std::string& type_in = ""): init_flag(false),
      type(new std::string(type_in)) {}
  virtual ~LDPC_Generator() {delete type;}

  virtual void encode(const bvec &input, bvec &output) = 0;

  std::string get_type() const { return *type; }

  void mark_initialized() {init_flag = true;};

  bool is_initialized() const {return init_flag;};
private:
  bool init_flag;  
  std::string* type;  
protected:
  virtual void save(const std::string& filename) const = 0;
  virtual void load(const std::string& filename) = 0;
};


// ----------------------------------------------------------------------
// LDPC_Generator_Systematic
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Generator_Systematic : public LDPC_Generator
{
public:
  LDPC_Generator_Systematic(): LDPC_Generator("systematic"), G() {}
  LDPC_Generator_Systematic(LDPC_Parity* const H,
                            bool natural_ordering = false,
                            const ivec& ind = "");

  virtual ~LDPC_Generator_Systematic() {}

  virtual void encode(const bvec &input, bvec &output);

  ivec construct(LDPC_Parity* const H, bool natural_ordering = false,
                 const ivec& ind = "");

protected:
  virtual void save(const std::string& filename) const;
  virtual void load(const std::string& filename);

private:
  GF2mat G; // the matrix is stored in transposed form
};


// ----------------------------------------------------------------------
// BLDPC_Generator
// ----------------------------------------------------------------------

class ITPP_EXPORT BLDPC_Generator : public LDPC_Generator
{
public:
  BLDPC_Generator(const std::string type = "BLDPC"):
      LDPC_Generator(type), H_enc(), N(0), M(0), K(0), Z(0) {}
  BLDPC_Generator(const BLDPC_Parity* const H,
                  const std::string type = "BLDPC");

  int get_exp_factor() const { return Z; }

  void encode(const bvec &input, bvec &output);

  void construct(const BLDPC_Parity* const H);

protected:
  void save(const std::string &filename) const;
  void load(const std::string &filename);

  GF2mat H_enc;  
  int N;   
  int M;       
  int K;   
  int Z;   
};


// ----------------------------------------------------------------------
// LDPC_Code
// ----------------------------------------------------------------------

class ITPP_EXPORT LDPC_Code : public Channel_Code
{
public:
  LDPC_Code();

    LDPC_Code(const LDPC_Parity* const H, LDPC_Generator* const G = 0, 
              bool perform_integrity_check = true);

  LDPC_Code(const std::string& filename, LDPC_Generator* const G = 0);

  virtual ~LDPC_Code() {delete dec_method;}


  void set_code(const LDPC_Parity* const H, LDPC_Generator* const G = 0, 
                bool perform_integrity_check = true);

  void load_code(const std::string& filename, LDPC_Generator* const G = 0);

  void save_code(const std::string& filename) const;


  void set_decoding_method(const std::string& method);

  void set_exit_conditions(int max_iters,
                           bool syndr_check_each_iter = true,
                           bool syndr_check_at_start = false);

  void set_llrcalc(const LLR_calc_unit& llrcalc);


  // ------------ Encoding  ---------------------

  virtual void encode(const bvec &input, bvec &output);
  virtual bvec encode(const bvec &input);


  // ------------ Decoding  ---------------------

  virtual void decode(const bvec &, bvec &) {
    it_error("LDPC_Code::decode(): Hard input decoding not implemented");
  }
  virtual bvec decode(const bvec &) {
    it_error("LDPC_Code::decode(): Hard input decoding not implemented");
    return bvec();
  }

  virtual void decode(const vec &llr_in, bvec &syst_bits);
  virtual bvec decode(const vec &llr_in);

  void decode_soft_out(const vec &llr_in, vec &llr_out);
  vec decode_soft_out(const vec &llr_in);

  int bp_decode(const QLLRvec &LLRin, QLLRvec &LLRout);

  bool syndrome_check(const QLLRvec &LLR) const;

  bool syndrome_check(const bvec &b) const;

  QLLRvec soft_syndrome_check(const QLLRvec &LLR) const;

  // ------------ Basic information gathering functions ------

  double get_rate() const {
    return (1.0 - static_cast<double>(ncheck) / nvar);
  }

  int get_nvar() const { return nvar; }

  int get_ncheck() const { return ncheck; }

  int get_ninfo() const { return nvar - ncheck; }

  std::string get_decoding_method() const { return *dec_method; }

  int get_nrof_iterations() const { return max_iters; }

  LLR_calc_unit get_llrcalc() const { return llrcalc; }

  friend ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);

protected:
  void decoder_parameterization(const LDPC_Parity* const H);

  void integrity_check();

  void setup_decoder();

private:
  bool H_defined;  
  bool G_defined;  
  int nvar;   
  int ncheck;   
  LDPC_Generator *G;  

  // decoder parameters
  std::string* dec_method; 
  int max_iters;  
  bool psc;   
  bool pisc;   
  LLR_calc_unit llrcalc; 
  // Parity check matrix parameterization
  ivec C, V, sumX1, sumX2, iind, jind;

  // temporary storage for decoder (memory allocated when codec defined)
  QLLRvec mvc, mcv;

  static const int max_cnd = 200;
};


ITPP_EXPORT std::ostream &operator<<(std::ostream &os, const LDPC_Code &C);
}

#endif