ldpc_decode.c

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

/***************************************************************************
 *    ldpc_decode.c  - LDPC decoding
 *                           -------------------
 *   begin                :  01/2003
 *   authors              :  Bernhard Bruhn
 *   emails               :  [e-mail]
 ***************************************************************************/

/***************************************************************************
 *                                Changes
 *                                -------
 * date - name - description
 * 03/04/25 - ineiti - added snr to the stats, so that one can check what
 *                     snr has been used when decoding
 * 03/05/09 - ineiti - added a done-stats to know when it's finished
 * 03/07/14 - Gaurav Gupta and Y.Srinivasulu - modified the structure of the
 * 	      graph and changed all the messages to short 
 * 	      integers. decoding achieved in 24 ms.
 * 04/03/03 - ineiti - kicked activate out again, as well as stats->done
 * 04/03/05 - ineiti - adjusted description
 **************************************************************************/

/***************************************************************************
 *                                                                         *
 *   This program is free software; you can redistribute it and/or modify  *
 *   it under the terms of the GNU General Public License as published by  *
 *   the Free Software Foundation; either version 2 of the License, or     *
 *   (at your option) any later version.                                   *
 *                                                                         *
 ***************************************************************************/


/**
 * This is the optimised part of the LDPC - the decoder. It uses quite
 * a sophisticated scheme to get all out of the SSE2-extension.
 * Nevertheless, it still takes too long for a real-time, 5MHz bandwith
 * QPSK decoding...
 */
#include "spc.h"
#include "graphcreate.h"
#include "decodehelpers.h"
#include "std.h"
#include "lookup.h"
#define DBG_LVL 0
#define IN_BLOCKS 1
#define MAXDEGREE 30
#include "sse2mmx.h"

typedef struct {
  // Number of iterations
  int iterations; // 30
  // The index of the ldpc-code. For the moment, three codes
  // are implemented:
  // 1 - rate .25, size 4000
  // 2 - rate .5, size 3992
  // 3 - rate .75, size 3992
  int ldpc_code_id; // 1
  // The type of the channel: 
  // 1:BSC
  // 2:AWGN
  int channel_type; // 1
  // either 'p' for a BSC channel or 'a/variance' for a AWGN
  double channel_param; // 0.07
  // Define the matched filter to calculate the correct a/variance.
  // If this is defined, channel_param won't be used.
  int mafi; // -1
}
config_t;

typedef struct {
  // The calculated SNR
  double snr;
}
stats_t;

typedef struct {
  // ADD HERE anything you want!
  graphstemp *graph;
  int *iphi;
  int gap;
  int ldpc_code_id;
  int bits_per_symbol;
  int iterations;
  int channel_type;	// 1:BSC          2:AWGN
  double channel_param; // either 'p' or 'a/variance'
  int mafi;
}
private_t;


/*
 * The initialisation function, or constructor,
 * is called the each time this module is instantiated.
 */

int rcv_init( swr_sdb_t *context ) {
  // Begin system-definitions {
  int i;
  config_t *config;
  stats_t *stats;
  MOD_INC_USE_COUNT;
  lower=(float **) swr_malloc(sizeof(float *)*MAXDEGREE);
  higher=(float **) swr_malloc(sizeof(float *)*MAXDEGREE);
  prod=(short int *)swr_malloc(sizeof(short int)*8);
  for(i=0;i<MAXDEGREE;i++) {
    lower[i]=(float *)swr_malloc(sizeof(float )*4);
    higher[i]=(float *)swr_malloc(sizeof(float )*4);
  }
  if ( sizeof( private_t ) > 0 )
    context->private_data = swr_malloc( sizeof( private_t ) );
  swr_sdb_get_config_struct( context->id, (void**)&config );
  swr_sdb_get_stats_struct( context->id, (void**)&stats );
  // } End of system-definitions


  config->ldpc_code_id	= -1;
  config->iterations	= 100;
  config->channel_type	= 1;
  config->channel_param	= 0.07;
  config->mafi = -1;
  stats->snr = -2.3;
  private->bits_per_symbol= 2;
  private->ldpc_code_id = -1;

  //allocate memory for graph
  private->graph=(graphstemp *)swr_malloc(sizeof(graphstemp));
  private->graph->vnodenum=0;
  private->graph->cnodenum=0;


  // Begin system-definitions
  swr_sdb_free_stats_struct( context->id, (void**)&stats );
  swr_sdb_free_config_struct( context->id, (void**)&config );
  return 0;
  // End system-definitions
}


/*
 * Every time modules from the outside change the value of a configuration parameter,
 * this function is called.
 */

int rcv_reconfig( swr_sdb_t *context ) {
  // Definition of variables - don't touch
  config_t *config;
  stats_t *stats;
  int vnodenum=0, cnodenum=0;

  swr_sdb_get_config_struct( context->id, (void**)&config );
  swr_sdb_get_stats_struct( context->id, (void**)&stats );

  // Put you code here
  // ADD HERE

  // put new code into private->graph if config->ldpc_code_id has changed
  if(config->ldpc_code_id!=-1 && private->ldpc_code_id!=config->ldpc_code_id) {
    PR_DBG( 2, "loading ldpc code with ID %i\n", config->ldpc_code_id );
    if(private->ldpc_code_id!=-1)
      freeGraphtemp(private->graph, private->iphi);
    private->ldpc_code_id = config->ldpc_code_id;
    if ( getGraphtemp(private->ldpc_code_id, private->graph, &(private->gap), &(private->iphi)) ) {
      private->ldpc_code_id = -1;
    } else {
      vnodenum=(*private->graph).vnodenum;
      cnodenum=(*private->graph).cnodenum;
      size_out(0) = ( vnodenum - cnodenum ) / 8;
      PR_DBG( 2, "Put output-size to %i bytes\n", size_out(0) );
    }
  }
  private->iterations	=config->iterations;
  private->channel_type	=config->channel_type;
  private->channel_param=config->channel_param;
  private->mafi         =config->mafi;

  // Definition - don't touch
  swr_sdb_free_stats_struct( context->id, (void**)&stats );
  swr_sdb_free_config_struct( context->id, (void**)&config );
  return 0;
}


/*
 * This is the function that implements the `main method' of the class
 * Every class has got just ONE method/working-mode.
 */
int rcv_pdata( swr_sdb_t *context ) {
  double loglkhdratio;
  long int start,stop,ctime=0,vtime=0;
  stats_t *stats;
  SYMBOL_COMPLEX *in;
  U8 *in_demod,*out;

  int vnodenum=0, cnodenum=0, dnodenum=0;
  int *decisions;
  double *dec_in, mid_amp=10, noise_var=10, flip_prob=0;
  int i,j,bits,index=0;

  // If we have a matched-filter, then get the correct values
  if ( private->mafi >= 0 ) {
    flip_prob = swr_sdb_get_stats_double( private->mafi, "flip_prob" );
    mid_amp = (double)swr_sdb_get_stats_int( private->mafi, "mid_amp" );
    noise_var = (double)swr_sdb_get_stats_int( private->mafi, "noise_var" );
  }
  if ( !data_available( 0 ) ) {
    PR_DBG( 2, "Missing data on port %i\n", 0 );
    return 0;
  }

  in=buffer_in(0);
  out=buffer_out(0);

  vnodenum=(*private->graph).vnodenum;
  cnodenum=(*private->graph).cnodenum;
  // d is data nodes
  dnodenum=vnodenum - cnodenum;

  PR_DBG(3, "vnodenum=%d, cnodenum=%d, size_in=%d bytes\n", vnodenum, cnodenum, size_in(0));

  PR_DBG( 2,"allocating %i decisions, dec_in\n", vnodenum);
  decisions=(int*)swr_malloc(sizeof(int)*vnodenum);
  dec_in=(double*)swr_malloc(sizeof(double)*size_in(0)*2);

  PR_DBG( 4,"channel type (1:BSC, 2:AWGN): %d\n",private->channel_type);
  switch(private->channel_type) {
  case 1:
    //BSC -> do demodulation
    // If there is a valid matched-filter id, we get the flip-probability
    if ( private->mafi >= 0 ) {
      private->channel_param = flip_prob;
      PR_DBG( 2, "New flip-probability * 100: %i\n",
              (int)private->channel_param * 100 );
    }

    in_demod=(U8*)swr_malloc(sizeof(U8)*size_in(0)*2);
    for ( i=0; i<size_in(0)*2; i++) {
      in_demod[i]=0;
    }
    j = -1;
    for ( i=0; i<size_in(0)*2; i += private->bits_per_symbol, in++ ) {
      if ( !( i % 8 ) ) {
        // Prepare the next byte
        j++;
        in_demod[j] = 0;
      }
      // If the QPSK is done right, this should work out well...
      bits = ( in->real > 0 ) + ( in->imag > 0 ) * 2;
      in_demod[j] += bits << ( i % 8 );
    }

    PR_DBG(4, "size_in_demod=size_in/2=%d, size_out=%d \n", size_in(0)/2,size_out(0));
    PR_DBG(4, "demodulated input: %s\n", in_demod );

    //copy bytes from 'in_demod' to bits in 'dec_in' {+-1*loglikelyhood}
    loglkhdratio =log((1.0-private->channel_param)/private->channel_param);
    if( size_in(0)*2 >= vnodenum ) {
      for( i=0; i<size_in(0)*2; i++ ) {
        if ( !(i%8) )
          index = in_demod[ i/8 ];
        dec_in[i]=((-2)*(index&1)+1)*loglkhdratio;
        index/=2;
        if ( i < 10 ) {
          PR_DBG( 4, "dec_in[%i] = %f\n", i, dec_in[i] );
        }
      }
    } else {
      PR_DBG( 0, "size_in(0)*2<vnodenum ( %i*2<%i ) => unable to decode\n",
              size_in(0),vnodenum );
      return 0;
    }
    swr_free (in_demod);
    break;
  case 2:
    //AWGN Channel
    // If there is a valid matched-filter id, we calculate the a/variance
    if ( private->mafi >= 0 ) {
      private->channel_param = mid_amp / noise_var;
      PR_DBG( 1, "New a/variance: %g\n", private->channel_param );
    }

    //compute LLRs for symbols from 'in' to the decoder input vector 'dec_in'
    if( size_in(0)*2 >= vnodenum ) {
      for( i=0; i<size_in(0)*2; i+=2, in++ ) {
        dec_in[i]=-2*(in->real)*(private->channel_param);
        dec_in[i+1]=-2*(in->imag)*(private->channel_param);
        dec_in[i]=restrict(dec_in[i],MAX_VALUE);
        dec_in[i+1]=restrict(dec_in[i+1],MAX_VALUE);
        /*if ( i < 10 ){
          PR_DBG( 4, "dec_in[%i] = %f\n", i, dec_in[i] );
          PR_DBG( 4, "dec_in[%i] = %f\n", i+1, dec_in[i+1] );
        }*/
      }
    } else {
      PR_DBG( 0, "size_in(0)*2<vnodenum ( %i*2<%i ) => unable to decode\n",
              size_in(0),vnodenum );
      return 0;
    }
    break;
  default:
    PR_DBG( 0,"channel type neither set to 1 (BSC) nor to 2 (AWGN)\n");
    return(0);
  }
  init(T);		//this is used to limit in variablemessagemap,makedecisions..

  initializegraph(private->graph, dec_in);
  for ( i=0; i<private->iterations; i++ ) {
    start = gettime();
    variablemessagemap(private->graph);
    stop = gettime();
    vtime += stop - start;
    checkmessagemap(private->graph);
    start = gettime();
    ctime += start - stop;
  }
  makedecisions(private->graph, decisions);
  PR_DBG(1," \nThe time for vnodes is %ld us and time for cnodes is %ld us\n",vtime,ctime);
  //copy decoded data to output
  j=-1;
  if( size_out(0)*8 < dnodenum ) {
    PR_DBG( 1,"output too small: decoded information (%i) does not fit in %i\n",
            dnodenum, size_out(0) * 8 );
  }
  for ( i=0; i<min( dnodenum, size_out(0)*8 ); i++ ) {
    if ( !( i % 8 ) ) {
      j++;
      out[j] = 0;
    }
    out[j] += decisions[i] << ( i % 8 );
  }

  for ( i=dnodenum; i<size_out(0)*8; i++ ) {
    if ( !( i % 8 ) ) {
      j++;
      out[j] = 0;
    }
  }

  // Clean up
  swr_free (decisions);
  swr_free (dec_in);

  // And calculate the snr for further use
  swr_sdb_get_stats_struct( context->id, (void**)&stats );
  if ( private->mafi >= 0 ) {
    if ( ( mid_amp > 0 ) && ( noise_var > 0 ) ) {
      stats->snr = 10 * ( log10( mid_amp ) * 2 - log10( noise_var ) );
    } else {
      PR_DBG( 0, "Can't take log of mid_amp:%s%i.%i or noise_var:%s%i.%i\n",
              swr_ftosii( mid_amp ), swr_ftosii( noise_var ) );
    }
  } else {
    stats->snr = -2.3;
  }
  swr_sdb_free_stats_struct( context->id, (void**)&stats );

  return(0);
}

/**
 * User messages
 */
int rcv_custom_msg( swr_sdb_t *context, swr_usr_msg_t *data, swr_msgq ret ) {
  return 0;
}

/*
 * This is the `destructor'.
 */
int rcv_finalize( swr_sdb_t *context ) {
  int i;
  swr_free( private->graph );
  if ( sizeof( private_t ) > 0 )
    swr_free( private );
  for(i=0;i<8;i++) {
    swr_free(lower[i]);
    swr_free(higher[i]);
  }
  swr_free(lower);
  swr_free(higher);
  swr_free(prod);
  MOD_DEC_USE_COUNT;
  return 0;
}


/*
 * This function is called upon "insmod" and is used to register the
 * different parts of the module to the SPM.
 */
swr_spc_id_t rcv_id;
int rcv_module_init(void) {
  swr_spc_desc_t *desc;

  /**
   * Get a description-part from CDB
   * Give the following parameters:
   * Input-ports, output-ports, config-params, stat-params
   */
  desc = swr_spc_get_new_desc( 1, 1, 5, 1 );
  if ( !desc ) {
    PR_DBG( 0, "Can't initialise the module. This is BAD!\n" );
    return -1;
  }

  /**
   * Define the different parts of config and stats. You have to define
   * them in the same order as they appear in the structures. The names
   * can be freely chosen.
   *
   * UM_CONFIG_{INT,DOUBLE,STRING128,POINTER}( "name" );
   * UM_STATS_{INT,DOUBLE,STRING128,POINTER,BLOCK}( "name" );
   */
  UM_CONFIG_INT( "iterations" );
  UM_CONFIG_INT( "ldpc_code_id" );
  UM_CONFIG_INT( "channel_type" );
  UM_CONFIG_DOUBLE( "channel_param" );
  UM_CONFIG_INT( "mafi" );
  UM_STATS_DOUBLE( "snr" );
  /**
   * The in- and outputs have also to be defined in the right order. First
   * port first. The additional flag is not used yet, but it will...
   *
   * UM_INPUT( SIG_{U8,SYMBOL_{S16,COMPLEX,MMX},SAMPLE_S12,S32}, 0 );
   * UM_OUTPUT( SIG_{U8,SYMBOL_{S16,COMPLEX,MMX},SAMPLE_S12,S32}, 0 );
   */

  UM_INPUT( SIG_SYMBOL_COMPLEX, 0 );
  UM_OUTPUT( SIG_U8, 0 );

  // Initialise the callback-functions. Delete the ones you don't use
  desc->fn_init              = rcv_init;
  desc->fn_reconfigure       = rcv_reconfig;
  desc->fn_process_data      = rcv_pdata;
  desc->fn_custom_msg        = rcv_custom_msg;
  desc->fn_finalize          = rcv_finalize;

  // And register the module in the SPM. Change the name!
  rcv_id = swr_cdb_register_spc( &desc, "ldpc_decode_sse2" );
  if ( rcv_id == SWR_SPM_INVALID_ID ) {
    swr_spc_free_desc( desc );
    PR_DBG( 0, "Couldn't register the module!\n" );
    return 1;
  }
  PR_DBG( 4, "Ready\n" );
  return 0;
}


/*
 * This is called upon rmmod
 */
void rcv_module_exit( void ) {
  PR_DBG( 4, "Freeing id: %i\n", rcv_id );
  if ( swr_cdb_unregister_spc( rcv_id ) < 0 ) {
    PR_DBG( 0, "Still in use somewhere\n" );
  }
}