decodehelpers.c

This a framework to test new ideas in transmission technology. Actual development is a LDPC-coder in

#include "decodehelpers.h"
#include "lookup.h"
#define DBG_LVL 0

/*
  #define MAXMESSAGE 20
  #define EXPMAXMESSAGE 485165000
  #define EXPNEGMAXMESSAGE 0.00000000206115
*/

#define MAXMESSAGE 25
#define EXPMAXMESSAGE 7.20049e10
#define EXPNEGMAXMESSAGE 1.38879e-11

/************************************
 * copy the received values into the *
 * appropriate places in the graph   *
 ************************************/
void initializegraph(graphs *graph)
{
  int node, socket;

  /* set all messages to zero */
  for (node=0; node<(*graph).vnodenum; node++)
    for (socket=0; socket<vnodedegree; socket++)
      vnodeedge.message=0.0;
  for (node=0; node<(*graph).cnodenum; node++)
    for (socket=0; socket<cnodedegree; socket++)
      cnodeedge.message=0.0;
}


/**********************************
 * make decisions on current graph *
 **********************************/
void makedecisions(graphs *graph, int *decisions)   {
  int node, socket;
  double sum;

  for (node=0; node<(*graph).vnodenum; node++)
    {
      /* take sum over all inputs */
      sum=vnodevalue;
      for (socket=0; socket<vnodedegree; socket++)
	sum+=vnodeedge.message;

      /*            if (sum>0)
       *(decisions+node)=1.0;
       else
       *(decisions+node)=-1.0;*/
      if (sum>0)
	*(decisions+node)=0.0;
      else
	*(decisions+node)=1.0;
    }
}

/************************************
 * message map at the variable nodes *
 * schedule can be used if we want   *
 * the decoder to be time variant    *
 * currently it is not used          *
 ************************************/
void variablemessagemap(graphs *graph)   {
  int node, socket;
  int tonode, tosocket;
  double sum, newmessage;

  for (node=0; node<(*graph).vnodenum; node++)
    {
      /* take sum over all inputs */
      sum=vnodevalue;
      for (socket=0; socket<vnodedegree; socket++)
	sum+=vnodeedge.message;

      /* now determine all the outgoing messages */
      for (socket=0; socket<vnodedegree; socket++)
	{
	  tonode=vnodeedge.dest;
	  tosocket=vnodeedge.socket;
	  newmessage=(sum-vnodeedge.message);

	  /* bound the size of the messages */
	  if (fabs(newmessage)>MAXMESSAGE)
	    {
	      if (newmessage>0)
		cnodetoedge.message=EXPMAXMESSAGE;
	      else
		cnodetoedge.message=EXPNEGMAXMESSAGE;
	    }
	  else
	    cnodetoedge.message=exp(newmessage);
	}
    }
}

/*********************************
 * message map at the check nodes *
 *********************************/
void checkmessagemap(graphs *graph)   {
  int node, socket;
  int tonode, tosocket;
  int erasurenum;
  //   int unreliable, pos;
  double prod, x;
  //   double shift, rel1, rel2, mes, mesrel, messign;

  for (node=0; node<(*graph).cnodenum; node++)
    {
      /* combine all non-erasure inputs */
      prod=EXPMAXMESSAGE;
      erasurenum=0;
      for (socket=0; socket<cnodedegree; socket++)
	{
	  if (cnodeedge.message!=1.0)
	    prod=(1.0+prod*cnodeedge.message)/(prod+cnodeedge.message);
	  else
	    erasurenum++;
	}

      switch (erasurenum)
	{
	case 0:
	  /* now determine all outgoing messages */
	  for (socket=0; socket<cnodedegree; socket++)
	    {
	      tonode=cnodeedge.dest;
	      tosocket=cnodeedge.socket;
	      if ( prod - cnodeedge.message != 0 ){
		x = (1.0-prod*cnodeedge.message)/(prod-cnodeedge.message);
		if ( x > 0 ){
		  vnodetoedge.message=log((1.0-prod*cnodeedge.message)/(prod-cnodeedge.message));
		    
		} else {
		  PR_DBG( 2, "x <= 0!\n" );
		}
	      } else {
		PR_DBG( 2, "prod - cnodeedge.message == 0!\n" );
	      }

	      /* check overflow */
	      if (fabs(vnodetoedge.message)>20.0) {
		if (vnodetoedge.message>0)
		  vnodetoedge.message=20.0;
		else
		  vnodetoedge.message=-20.0;
	      }
	    }
	  break;
	case 1:
	  /* if there is exactly on erasure input then */
	  /* then all but one output is an erasure     */
	  for (socket=0; socket<cnodedegree; socket++)
	    {
	      tonode=cnodeedge.dest;
	      tosocket=cnodeedge.socket;

	      if (cnodeedge.message!=1.0)
		vnodetoedge.message=0.0;
	      else
		{
		  if ( prod > 0 ){
		    vnodetoedge.message=log(prod);
		  } else {
		    PR_DBG( 2, "prod <= 0!\n" );
		  }

		  /* check overflow */
		  if (fabs(vnodetoedge.message)>20.0) {
		    if (vnodetoedge.message>0)
		      vnodetoedge.message=20.0;
		    else
		      vnodetoedge.message=-20.0;
		  }
		}
	    }
	  break;
	default:
	  /* if we have two or more erasure inputs */
	  /* then all outputs are erasures         */
	  for (socket=0; socket<cnodedegree; socket++)
	    {
	      tonode=cnodeedge.dest;
	      tosocket=cnodeedge.socket;
	      vnodetoedge.message=0.0;
	    }
	  break;
	}
    }
}


/********************************
 * Does one iteration on the
 * left-fold
 *******************************/
void leftfoldmap( graphs *graph ){
  int node, n, socket, ig, il, i;
  double L[graph->bits_per_left_checknode], a[graph->bits_per_left_checknode], 
    b[graph->bits_per_left_checknode], g, c, *f;

  // The main loop that goes over all the variable nodes
  // graph->bits_per_left_checknode at a time

  for (node=0; node<graph->vnodenum; node += graph->bits_per_left_checknode){
    // Do the loop we've discussed. The L_n's are
    // graph->vnodelist[node + n].value
    // The respectives f_b's are
    // graph->f[node * ( 1 << graph->bits_per_left_checknode ) + b ]
    for ( n=0; n<graph->bits_per_left_checknode; n++ ){
      L[n] = 0;
      for (socket=0; socket<graph->vnodelist[node+n].degree; socket++){
	L[n] += graph->vnodelist[node + n].edgelist[socket].message;
      }
    }
    
    // PR_DBG( 4, "node: %i: L is %g %g %g %g\n",
    //    node, L[0], L[1], L[2], L[3] );
    

    // Now L[0]..L[graph->bits_per_left_checknode - 1] are initialised
    // Calculate outgoing Ls
    
    
    // Set to zero a and b ?? Needed?
    for(il=0; il< graph->bits_per_left_checknode; il++){
      a[il] = 0;
      b[il] = 0;
    }
    
    // The main loop according to the algorithm discussed with Linus
    // This points to the beginning of the interesting block in private->graph->f
    f = graph->f + node / graph->bits_per_left_checknode * 
      ( 1 << graph->bits_per_left_checknode );
    for (ig=0; ig < (1 << graph->bits_per_left_checknode) - 1; ig++ ){
      g = 0;
      for (i=0; i <  graph->bits_per_left_checknode; i++){
	g += (((1<<i)&ig)>0) * L[i];
      }

      PR_DBG( 4, "node: %i: g is %g\n",
	      node, g );

      c = max( exp( g + f[ig] ), 1e-10 );

      PR_DBG( 4, "node: %i: c is %g\n",
	      node, c );

      for(il=0; il< graph->bits_per_left_checknode; il++){
	if (!((1<<il)&ig)){
	  a[il] += c;
	  b[il] += max( exp( g + f[(1<<il)+ig] ), 1e-10 );
	}
      }
    }
    
    // Main loop ended
    // Next we compute the outgoing messages
    for (i=0; i < graph->bits_per_left_checknode; i++){
      L[i]=b[i]/a[i];

      PR_DBG( 4, "node: %i: L is %g %g %g %g\n",
	      node, L[0], L[1], L[2], L[3] );
      PR_DBG( 4, "node: %i: a is %g %g %g %g\n",
	      node, a[0], a[1], a[2], a[3] );
      PR_DBG( 4, "node: %i: b is %g %g %g %g\n",
	      node, b[0], b[1], b[2], b[3] );
    }
    
    // Write them to graph->vnodelist[node + n].value
    for ( n=0; n<graph->bits_per_left_checknode; n++ ){
      graph->vnodelist[node+n].value = log( L[n] );
    }
    PR_DBG( 4, "node: %i: L is %g %g %g %g\n",
	    node, log( L[0] ), log( L[1] ), log( L[2] ), log( L[3] ) );
  }
}