ldpc_2.h

关于Q元LDPC码的C++仿真程序

   message &operator<<(int l)
   {
      static message Aux;

      Aux.q = q;
      for (int i = 0; i < q; i++)
         Aux.Probs[i] = Probs[(i + l) % q];

      return Aux;
   }

   message &LLRShift(int k)
   {
      message Aux = *this;

      for (int i = 0; i < q; i++)
         Probs[i] = Aux[(i + k) % q] - Aux[k % q];

      return *this;
   }

   double AverageD()
   {
    message m = *this;

    m.Clip();
    m /= m[0];
    m.Clip();

    m[0] = 0;     // Don't count zero
    return m.sum() / (GFq::q - 1);
   }

   void operator<<=(int l)
   {
      *this = *this << l;
   }

   //   ~message()
   //      { if (Probs != NULL) delete Probs; }

   void Clip(double minval = EPSILON, double maxval = INF)
   {
      for (int i = 0; i < q; i++)
      {
         clip(Probs[i], maxval);
         if (Probs[i] < minval)
            Probs[i] = minval;
      }

   }

   int RandomSelectIndex();      // Select index at random based on probabilities in message
};



inline message &Convolve(message &M1, message &M2)
{
   static message Aux;

   Aux = M1;
   Aux.Convolve(M2);
   return Aux;
}



inline ostream &operator<<( ostream &s, message &m )
{
  s << ceil(m[0]*1000.)/1000.;
  for (int i = 1; i < m.q; i++)
    s << " " << ceil(m[i]*1000.)/1000.;
  
  return s;
}



inline message &operator-(message &m1, message &m2)
{
  static message aux;

  aux.q = m1.q;

  for (int i = 0; i < m1.q; i++)
     aux[i] = m1[i] - m2[i];
  
  return aux;
}



inline message &operator/(message &m, double d)
{
  static message aux;

  aux.q = m.q;

  for (int i = 0; i < m.q; i++)
     aux[i] = m[i]/d;
  
  return aux;
}





inline double pow(message &m, int l)
{
   double f = 0;

   for (int i = 0; i < m.q; i++)
      f += pow(m[i], l);

   return f;
}





inline double fabs(message &m)
{
   double f = 0;

   for (int i = 0; i < m.q; i++)
      f += fabs(m[i]);

   return f;
}





inline message &log(message &m)
{
   static message aux;

   aux.q = m.q;
   for (int i = 0; i < m.q; i++)
      aux[i] = mylog(m[i]);

   return aux;
}





inline message &exp(message &m)
{
   static message aux;

   aux.q = m.q;
   for (int i = 0; i < m.q; i++)
      aux[i] = exp(m[i]);

   return aux;
}





inline message &LLR(message &m)
{
   static message aux;

   aux.q = m.q;
   double log_m0 = mylog(m[0]);

   aux[0] = 0;
   for (int i = 1; i < m.q; i++)
      aux[i] = log_m0 - mylog(m[i]);

   return aux;
}





inline message &unLLR(message &m)
{
   static message aux;

   aux.q = m.q;

   aux[0] = 1;
   for (int i = 1; i < m.q; i++)
      aux[i] = exp(-m[i]);

   aux.Clip();
   aux.Normalize();
   aux.Clip();

   return aux;
}

/*****************************************************************************
 *
 * ArrayOfMessage
 *
 *****************************************************************************/

class ArrayOfMessage {
   message *Messages;
   int size;
public:

   int GetSize()
   {
      return size;
   }

   ArrayOfMessage() : 
      Messages(NULL), size(0)
      {}


   void Allocate(int p_Size)
   {
      if (size != p_Size)
      {
         deAllocate();
         size = p_Size;
         Messages = new message[size];
      }
   }


   void deAllocate()
   {
      if (Messages != NULL)
         delete Messages;

      Messages = NULL;
      size = 0;
   }

   
   ~ArrayOfMessage()
   {
      deAllocate();
   }


   message &operator[](int i)
   {
      return Messages[i];
   }
};


/*****************************************************************************
 *
 * Graphs
 *
 *****************************************************************************/

class edge;              // temporary declaration, to enable the use of the class in further declaration


class node
{
public:
  int id;   // number used for identification
  int degree;
  int AuxDegree;        // Auxiliary variable for use in encoder generator
  edge **edges;
  int MaxEdges;

public:

  void SetID(int p_id) { id = p_id; }
  int GetID() { return id; }

  node() : 
    degree(-1),
    edges(NULL)
    { }

  void Disconnect();  // Disconnect all edges

  void DisconnectEdge(edge *e)
  {
      int index = 0;
      for (; index < degree; index++)
         if (edges[index] == e) break;

      if (index == degree)
      {
         cout << "node::DisconnectEdge: Attempt to disconnect a nonexistent edge\n";
         exit(1);
      }

      for (int i = index + 1; i < degree; i++)
         edges[i - 1] = edges[i];

      degree--;
  }


  void add_edge(edge *e)
    {
      if (degree == -1)
      {
         cout << "Edges not yet allocated, aborting.  \n";
         exit(1);
      }

      edges[degree++] = e;

      if (degree > MaxEdges) 
   {
     cout << "MaxEdges exceeded! "
          << " degree = " << degree << " MaxEdges = " << MaxEdges << "\n";
   }
    }

  void AllocateEdges(edge **&EdgeStackPointer, int p_MaxEdges)
    {
      degree = 0;    // Indicate edges have been allocated
      edges = EdgeStackPointer;
      EdgeStackPointer += p_MaxEdges;        // Advance allocation pointer
      MaxEdges = p_MaxEdges;
    }

  int GetDegree()   { return degree; }
  edge &GetEdge(int index) { return *edges[index]; }

  virtual node &AdjacentNode(int index) = 0;
} ;




message &GenerateChannelMessage(GFq v,
                                channel &TransmitChannel, 
                                mapping &MapInUse,
                                double ChannelOut );




class variable_node : public node
{
public:
  GFq Symbol;     // Value - for encoding
  GFq v;          // coset vector - randomly selected at variable node
  double SourceData;
  mapping *MapInUse;

  // Auxiliary for Linear Programming method
  int *LCLP_Constraints;
  int CountConstraints;

public:
   message InitialMessage;
   message FinalEstimate;
   message AllImprovementsForChange;       // For use in greedy source coding
   
public:
   variable_node()
   {  
      v.val = uniform_random(GFq::q);  
   }
   void Allocate_LCLP_Constraints(int **ConstraintsStack);
   int Count_LCLP_Constraints();
   void Add_LCLP_Constraint(int variable_index);
   
   message &CalcRightboundMessage( int rightbound_index );
   void CalcAllRightboundMessages();
   void CalcFinalMessage();
   void Initialize(channel &TransmitChannel, double ChannelOut);
   void SetMapInUse(mapping &p_MapInUse)
   { MapInUse = &p_MapInUse; }
   double GetZeroSignal()
   { return MapInUse->map(v);  }

   // For use in greedy source coding

   BOOLEAN IsRightConnectedTo( node *n );
   BOOLEAN IsPath3ConnectedTo( node *n );  // Is connected by a path of at most 
   virtual node &AdjacentNode(int index);
};


class complex_vector;


message &CalcLeftboundMessage(message Vectors[], 
			      int left_index,
                              int degree);



class check_node : public node
{
public:
  void CalcAllLeftboundMessages( );
  BOOLEAN DoesFinalEstimateViolate();
  virtual node &AdjacentNode(int index);
  GFq &Element(int i);         // For use in encoding - treats check like row of matrix 
  GFq &Value();
};




class edge
{
private:
  variable_node *left_node;
  check_node *right_node;

public:
  message LeftBoundMessage, RightBoundMessage;
  GFq label;

public:
  variable_node &LeftNode() { return *left_node; }
  check_node &RightNode() { return *right_node; }

  edge()
  { label.RandomSelect();  }

  void set_nodes(variable_node *p_left_node, check_node *p_right_node)
    {
      left_node = p_left_node;
      right_node = p_right_node;
      left_node->add_edge(this);
      right_node->add_edge(this);
    }

  void Disconnect()
  {
     left_node->DisconnectEdge(this);
     right_node->DisconnectEdge(this);
  }
} ;




class bipartite_graph
{
public:
  int N;                                // Number of variable nodes
  int M;                                // Number of check nodes
  long E;                                // Number of edges

  variable_node *variable_nodes;
  check_node *check_nodes;
  edge *edges;

  edge **EdgeStack;                // Pointer used to manage allocation of memory to nodes
  static BOOLEAN ShouldPermuteLDPCVariables;
public:
  void Reset(int p_N,              // number of variable nodes
        int lambda_degs[],
        double lambda_wts[],
        int rho_degs[],
        double rho_wts[],
		mapping &MapInUse);

  bipartite_graph() :  N(0), M(0), E(0), variable_nodes(NULL), check_nodes(NULL), edges(NULL),
    EdgeStack(NULL) {}
    
  ~bipartite_graph() { Clear(); }

  void Clear()
    {
      if (variable_nodes != NULL) delete variable_nodes;
      if (check_nodes != NULL) delete check_nodes;
      if (edges != NULL) delete edges;
      if (EdgeStack != NULL) delete EdgeStack;
    }

  void PrintNodes(char *title = NULL)
    {
      if (title != NULL) cout << " --- " << title << "\n";
      cout << "Variable Nodes: ";
      for (int i = 0; i < N; i++)
         cout << variable_nodes[i].GetDegree() << " ";
      cout << "\n";

      cout << "Check Nodes: ";
      for (int i = 0; i < M; i++)
         cout << check_nodes[i].GetDegree() << " ";
      cout << "\n";
    }

  void SaveToFile(char *filename)
    {
      ofstream OutFile(filename);

      for (int i = 0; i < M; i++)
      {
         for(int j = 0; j < check_nodes[i].GetDegree(); j++)
         {
            if (j != 0) OutFile << " ";
            OutFile << check_nodes[i].GetEdge(j).LeftNode().GetID();
         }
         OutFile << "\n";
      }

    }
} ;





/************************************************************************
 *
 * TopList - for use in greedy
 *
 ************************************************************************/


class TopList
{
public:
   GFq *BestChange;
   int *VariableIndex;
   double *DistortionImprovement;

   int MaxSize, CurrentSize;
public:
   TopList() : MaxSize(-1), CurrentSize(-1)  {}

   ~TopList()
   {
      DeAllocate();
   }


   void DeAllocate()
   {
      if (MaxSize > -1)
      {
         delete BestChange;
         delete VariableIndex;
         delete DistortionImprovement;
      }
      MaxSize = -1;
   }


   void Init(int p_MaxSize)
   {
      if (MaxSize != p_MaxSize)
      {
         DeAllocate();

         BestChange = new GFq[p_MaxSize];
         VariableIndex = new int[p_MaxSize];
         DistortionImprovement = new double[p_MaxSize];
      }

      MaxSize = p_MaxSize;
      CurrentSize = 0;
   }

   void Add(GFq p_BestChange, int p_VariableIndex, double p_DistortionImprovement)
   {
      // Find place for new distortion
      int Place;
      for (Place = 0; Place < CurrentSize; Place++)
         if (p_DistortionImprovement > DistortionImprovement[Place])
            break;

      // Shift all the rest one place up
      if (CurrentSize < MaxSize) CurrentSize++;
      for (int i = CurrentSize - 1; i > Place; i--)
      {
         BestChange[i] = BestChange[i-1];
         VariableIndex[i] = VariableIndex[i-1];
         DistortionImprovement[i] = DistortionImprovement[i-1];
      }

      // Place new entry
      if (Place < CurrentSize)      // If not passed last place in TopList
      {
         BestChange[Place] = p_BestChange;
         VariableIndex[Place] = p_VariableIndex;
         DistortionImprovement[Place] = p_DistortionImprovement;
      }
   }
};




#endif