convolution_rcv.c

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

/***************************************************************************
 *    _rcv.c  -  Software Radio convolutional decoder module
 ***************************************************************************/

/***************************************************************************
 *                                                                         *
 *   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.                                   *
 *                                                                         *
 ***************************************************************************/


/**
 * For description also refer to convolution.c
 *
 * This module is the receiver part (decoder) of the convolution code.
 *
 * Besides the configuration parameters described in convolution.c, the
 * following decoder specific parameters must be set:
 *
 * trunclength 	Indicates the length of the trellis which will never be exceeded.
 *   This Parameter must always be > 2, large values produce better error correction
 *   but reduce decoder speed performance and increase memory consumption
 */

#include "math.h"
#include "spc.h"
#include "library.h"

#define DBG_LVL 0


typedef struct {
  // The number of output bits (output bits per input bit)
  int n; // 2

  // The number of input bits (number of input bits to generate n output bits)
  int k; // 1

  // Number of memory registers used
  // (limited to 32 because of use of unsigned int to define a state)
  int m; // 8

  // array of polynome-definitions.
  // The array has length n, and holds one REG_STATUS value for each polynome.
  // The bits of a value define if this term should be added to the result or not.
  // Of each value, only the m LSB are relevant. All others should be set to 0.
  // Be aware that the LSB (bit 0) represents the term d^m,
  // while the bit m represent the term d^0.
  // E.g. A polynome which calculates the result as the latest, 4th latest and the 5th latest bits
  // p=1+d^3+d^4 has value=0b00000000 00000000 00000000 00011001 = 0x000000019
  REG_STATUS *polys; // 0x37,0x73

  // length of state-history of trellis. The trellis is truncated whenever it exceeds
  // this size
  int trunclength; // 100

  // indicates how many trellis-steps should be truncated in one truncate operation
  int truncblock; // 50
}
config_t;

typedef struct {
  // Stores the total time spent in the decoding
  double total_time_decode;
  // Stores the total time spent in truncating the code
  double time_truncate;
  // Stores the total time spent in calculating the trellis
  double time_calcsucc;
}
stats_t;

typedef struct {
  //copy of config->n
  int n;

  //copy of config->k
  int k;

  //copy of config->m
  int m;

  //copy of config->trunclength
  int trunclength;

  //copy of config->truncblock
  int truncblock;

  //copy of config->polys. Not only the pointer but the full array is copied
  REG_STATUS *polys;

  //number of valid input combination which are possible for one decoding iteration
  //=2^k
  int numValidInputs;

  //Number of possible states =2^m
  int numStates;

  //Array of dimension (length) numStates * numValidInputs.
  //It contains the new state which results if for a given state a given valid input is received.
  //
  //calculate idx by origState*numStates+validData
  //--> contains successor state
  REG_STATUS* newStateLookup;

  //Array of dimension (length) numStates * numStates.
  //It contains the valid input which is needed to switch from one state to another state.
  //This is a sparse matrix because only a few transitions are actually possible.
  //
  //calculate idx by origState*numStates+successorState
  //--> contains valid input needed for transition
  int* transitionLookup;

  //Array of dimension (length) numStates * trunclength.
  //It defines the metric for each node in the trellis.
  //If a node is invalid (there is no path to the node), this value is set to METRIC_UNDEFINED
  //calculate idx by step*numStates+state to metric of state at trellis step
  int* metrics;

  //Array of dimension (length) numStates * trunclength.
  //It defines the preceeding state for each node in the trellis.
  //If a node is invalid (there is no path to the node), this value is undefined.
  //calculate idx by step*numStates+state to find preceeding state at trellis step
  REG_STATUS* trellis;

  //The offset in the arrays trellis and metrics to define the start of the trellis, i.e.
  //the offset to which the trellis was truncated.
  //(Offsetting is used in order not to have to shift the trellis/metrics array whenever the
  //trellis is truncated.)
  int idx_start_trellis;

  //The offset in the arrays trellis and metrics to define the end of the trellis, i.e.
  //the offset to which the trellis was already defined.
  int idx_end_trellis;

  //Number of bits which are still unused in the byte which is currently written to the
  //out array
  int unusedOutBits;

  // Counts the number of bytes already written to the out array
  // The byte at out[outByteCounter] is the byte which is currently generated
  // (only 8-unusedOutBits bits of this byte are already valid)
  int outByteCounter;


  //Number of bits which are not yet processed in the byte which is currently read from the
  //in array
  int unconsumed;

  //Counts the number of bytes already processed in the in array
  //The byte at in[inByteCounter] is the byte which is currently processed
  //(only unconsumed bits of this byte are still unprocessed)
  int inByteCounter;

  //A mask containing 1's in its n LSB and 0's otherwise.
  int mask_n;

}
private_t;

//A default polynome definition which is used for initialization
REG_STATUS default_polys_rcv[]={0x37,0x73};

/*
 * The initialisation function, or constructor,
 * is called the first time this module is instantiated.
 */
int rcv_init( swr_sdb_t *context ) {
  // Begin system-definitions {
  config_t *config;
  stats_t *stats;
  MOD_INC_USE_COUNT;

  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

  //init stats
  stats->time_truncate=0;
  stats->total_time_decode=0;
  stats->time_calcsucc=0;

  //Init to null, for memory management
  private->polys = NULL;
  private->newStateLookup = NULL;
  private->transitionLookup = NULL;
  private->metrics = NULL;
  private->trellis = NULL;

  //Write default configurations
  config->n=2;
  config->k=1;
  config->m=8;
  config->trunclength = 100;
  config->truncblock = 50;
  config->polys=default_polys_rcv;

  // 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
}


/*
 * This is called when the output-sizes change.
 * It configures the inputs
 */
int rcv_configure_inputs( swr_sdb_t *context ) {
  // Definition of variables - don't touch
  config_t *config;
  //In-length in bits Li = ((Lo/k) + m) * n
  //Where Lo is output-length in bits
  double in=size_out(0)*8;

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

  in/=config->k;
  in+=config->m;
  in*=config->n;
  //convert to bytes. Require a little more input if output shouldnt fit in
  in/=8;
  size_in(0) = ceil(in);
  PR_DBG( 4, "receiver size_in is %f, (%d)\n",in,size_in(0));

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


/*
 * This is called when the input-sizes change
 * It configures the outputs
 */
int rcv_configure_outputs( swr_sdb_t *context ) {
  // Definition of variables - don't touch
  config_t *config;
  //Out-length in bits Lo = ((Li/n) - m) * k
  //Where Li is input-length in bits
  double out=size_in( 0 )*8;

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

  out/=config->n;
  out-=config->m;
  out*=config->k;
  //Convert to bytes. Cut down to byte, because obviously input was "inflated"
  out/=8;
  size_out( 0 ) = floor(out);
  PR_DBG( 3, "receiver size_out is %f, (%d)\n",out,size_out( 0 ));

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


/*
 * This function is called
 * every time a module from the outside changes the value of a configuration parameter,
 */

int rcv_reconfig( swr_sdb_t *context ) {
  // Definition of variables - don't touch
  config_t *config;
  //Calculate some temporary data in private structure which depends on configuration
  //Setup the mask which has n 1's in its lower bits
  int i;
  REG_STATUS origState;
  int origData;

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

  //Copy the configuration to the private structure
  private->n = config->n;
  private->k = config->k;
  private->m = config->m;
  private->trunclength = config->trunclength;
  private->truncblock = config->truncblock;

  private->mask_n=0x00;
  for (i=0;i<private->n;i++) {
    private->mask_n=(private->mask_n<<1)|0x01;
  }

  //copy the polynomes
  if ( private->polys ) {
    swr_free( private->polys );
  }
  private->polys = swr_malloc( private->n * sizeof( REG_STATUS ) );
  memcpy( private->polys, config->polys, private->n * sizeof( REG_STATUS ) );


  //Calculate the number of possible states (=2^m)
  private->numStates=0x01<<private->m;

  //Calculate the number of valid transmission bit-sequences (=2^k)
  private->numValidInputs=0x01<<private->k;

  //setup the transitionLookup and newStateLookup arrays
  if ( private->transitionLookup ) {
    swr_free( private->transitionLookup );
  }
  private->transitionLookup = swr_malloc( private->numStates *
                                          private->numStates *
                                          sizeof(int));

  if ( private->newStateLookup ) {
    swr_free( private->newStateLookup );
  }
  private->newStateLookup = swr_malloc( private->numStates *
                                        private->numValidInputs *
                                        sizeof(REG_STATUS));

  //iterate all original status
  for (origState=0x00000000;origState<private->numStates;origState++) {
    //iterate all combinations for valid data
    for (origData=0x00;origData<private->numValidInputs;origData++) {
      //See what status will be created when feeding the origData into the origStatus
      REG_STATUS newState= (origState >> private->k)
	|(origData << (private->m - private->k));
      private->newStateLookup[ origState * private->numValidInputs
			       + origData] = newState;
      private->transitionLookup[ origState * private->numStates
				 + newState] = origData;
    }
  }

  // Definition - don't touch
  swr_sdb_free_config_struct( context->id, (void**)&config );

  return 0;
}

/**
 * Checks recursively if the trellis node at check_step and check_status originates in
 * another trellis node at origin_step and origin_status.
 * If a checked state is invalid, false is returned
 * @param check_step The index in the trellis at which the possible successor node is
 * @param check_status The status at index step in the trellis which is the possible successor node
 * @param origin_step The index in the trellis at which the possible predecessor node is
 * @param origin_status The status at index step in the trellis
 * which is the possible predecessor node
 *
 * @return true if there is a path from origin node to check node
 */
int originatesIn(swr_sdb_t *context,int check_step,REG_STATUS check_status,int origin_step,REG_STATUS origin_status) {
  //Check if state is valid
  if (private->metrics[check_step*private->numStates+check_status] == METRIC_UNDEFINED) {
    //state is invalid-->return false
    return 0;
  }
  if (check_step==origin_step) {
    //return true if nodes are identic
    return (check_status==origin_status);
  } else {
    //recursively check for predecessor node
    REG_STATUS predecessor=private->trellis[check_step*private->numStates+check_status];
    int prevStep=check_step-1;
    if (prevStep<0){
      prevStep+=private->trunclength;
    }
    return originatesIn( context, prevStep, predecessor, 
			 origin_step, origin_status );
  }
}

/**
 * This method outputs the trellis for dubug purposes
 */
void showTrellis (swr_sdb_t *context) {
  int i,j;

  //Just for debug
  if (DBG_LVL<4)
    return;

  for (i=0;i<private->numStates;i++) {
    PR("State %x",i);
    for (j = private->idx_start_trellis ;
         j != private->idx_end_trellis ;
         j = (j+1) % private->trunclength) {
      PR("  S%2x M%2x",	private->trellis[j * private->numStates + i],
         private->metrics[j * private->numStates + i] == METRIC_UNDEFINED ?
         0xff :
         private->metrics[j*private->numStates+i]
        );
    }
    PR("\n");
  }

  //Write the 0 sequence so far (assuming there is only one, when data was transmitted correctly)
  PR("0-metrics path: ");
  for (j = private->idx_start_trellis;
       j != private->idx_end_trellis;
       j = (j+1) % private->trunclength) {
    for (i=0; i< private->numStates ; i++) {
      if (private->metrics[j * private->numStates + i] == 0) {
        REG_STATUS prevstate=private->trellis[j * private->numStates + i];
        PR(" S%2x D%2x ",
           i,
           private->transitionLookup[prevstate*private->numStates+i]
          );
        break;
      }
    }
  }
  PR("\n");
}


/**
 * Writes k bits to out array.
 * The bits are written in the unusedOutBits of the byte at out array index outByteCounter.
 * If more bits are to be written, the outByteCounter is incremented and remaining bits are written
 * to the next byte.
 * @param outValue Contains the bits to write in its k LSB
 * @param *out The pointer to the out-array.
 */
void rcv_writeBits(swr_sdb_t *context,int outValue,U8* out) {
  int bitsToWrite=private->k;
  int writeNow;
  
  while (bitsToWrite>0) {

    //check outByteCounter if out-buffer is too small. Dont write in that case
    //This could happen if input is a little too long because there are a few more flush
    //bits present (because n/k is not divisible by 8)
    if (private->outByteCounter >= size_out(0)) {
      PR_DBG(3, "Cant rcv all because outputbuffer too small. Truncating.\n");
      return;
    }

    //calculate how many bits to write into the current byte
    //=min(unusedOutBits,bitsToWrite)
    writeNow = private->unusedOutBits > bitsToWrite ? 
      bitsToWrite : private->unusedOutBits;

    PR_DBG( 4, "BitsToWrite=%d, private->unusedOutBits=%d, writeNow=%d\n",
            bitsToWrite,
            private->unusedOutBits,
            writeNow);

    //write new bits into the bits "left" of the already used bits
    out[private->outByteCounter] |= outValue <<( 8 - private->unusedOutBits);