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[BITSPERLEFTCHECKNODE], a[BITSPERLEFTCHECKNODE], 
    b[BITSPERLEFTCHECKNODE], g, c, *f;

// The main loop that goes over all the variable nodes
// BITSPERLEFTCHECKNODE at a time

  for (node=0; node<graph->vnodenum; node += BITSPERLEFTCHECKNODE){
    // 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 << BITSPERLEFTCHECKNODE ) + b ]
    for ( n=0; n<BITSPERLEFTCHECKNODE; 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[BITSPERLEFTCHECKNODE - 1] are initialised
    // Calculate outgoing Ls
    
    
    // Set to zero a and b ?? Needed?
    for(il=0; il< BITSPERLEFTCHECKNODE; 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 / BITSPERLEFTCHECKNODE * ( 1 << BITSPERLEFTCHECKNODE );
    for (ig=0; ig < (1 << BITSPERLEFTCHECKNODE) - 1; ig++ ){
      g = 0;
      for (i=0; i <  BITSPERLEFTCHECKNODE; 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< BITSPERLEFTCHECKNODE; 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 < BITSPERLEFTCHECKNODE; 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<BITSPERLEFTCHECKNODE; 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] ) );
  }
}