convolution_rcv.c

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

    //remove the written bits from the value to write, decrement counters
    outValue >>= writeNow;
    bitsToWrite -= writeNow;
    private->unusedOutBits -= writeNow;

    //check if a new byte is needed for next write
    if (private->unusedOutBits == 0) {
      PR_DBG( 1, "Decoded byte is: %x\n",out[private->outByteCounter]);
      private->outByteCounter++;
      private->unusedOutBits = 8;
    }
  }
}



/**
 * This method is called if the trellis is too long and must be truncated.
 * The truncation is made iteratively, i.e. only the very first step is truncated.
 * First, the ML path identified and backtraced to its first node. The corresponding data
 * is then written to the decoded data, and all those node in the last trellis step, which
 * do not root in the selected first node will be set to invalid, because these nodes can
 * no longer be reached from the selected node.
 *
 * The truncation is quite costly, because intense tree analysing is required. This could be
 * accelerated by not only truncating one step each time but e.g. by truncating trellis to half.
 * However, this would also reduce error detection capability.
 * *param out The array to which decoded data must be written
 */
void truncateTrellis(swr_sdb_t *context,stats_t *stats, U8* out) {
  double start = get_time_usec();
  //the (so far) best (lowest) metric found in the last step
  int bestMetric = METRIC_UNDEFINED;
  //the status of the best metric
  REG_STATUS bestState = 0;
  int s;
  //trace back bestState to beginning of trellis
  int step = private->idx_end_trellis;
  //will indicate the "end" of the ML path
  REG_STATUS state;
  //will indicate the mlPath
  REG_STATUS* mlPath;
  REG_STATUS from_state;
  int outValue;


  PR_DBG( 3, "Truncating\n");
  //find the status with best (lowest) metric in the last step
  for ( s=0; s<private->numStates; s++ ) {
    if( private->metrics[private->idx_end_trellis * private->numStates + s] < 
	bestMetric) {
      //found a better state
      bestState=s;
      bestMetric=private->metrics[private->idx_end_trellis * private->numStates + bestState];
    }
  }
  PR_DBG( 4, "best metric=%d, found for last state %2x\n",bestMetric,bestState);

  state = bestState;
  mlPath=swr_malloc(private->trunclength * sizeof(REG_STATUS));

  //While persuing the path, we memorize the ML path in an array
  while (step != private->idx_start_trellis) {
    mlPath[step]=state;
    //find predecessor
    state = private->trellis[step * private->numStates + state];
    step--;
    //modulo operation on trellis indices
    if (step<0)
      step=private->trunclength+step;
  }

  //mlPath now contains all states excepts the very first (at idx_start_trellis entry is not set)

  //write out truncsize times what leads from predecessor to next state
  step=private->idx_start_trellis;
  do {
    step=(step+1) % private->trunclength;

    state=mlPath[step];
    //find predecessor state from trellis (cannot be from mlPath[x-1] because its first
    //value is invalid)
    from_state=private->trellis[step * private->numStates + state];

    //find valid input bits responsible for state transition from_state to state.
    outValue = private->transitionLookup[from_state * private->numStates + state];
    PR_DBG( 2, "Writing out decoded data: %x\n",outValue);
    rcv_writeBits(context,outValue,out);

  } while (step != (private->idx_start_trellis + private->truncblock) % private->trunclength);

  //It was now decided that the first truncblock transitions from ML Path
  //were all correct.
  //Thus all pathes which remain valid need to originate in the truncblock-th node of ML Path.
  //Set these nodes in last step to undefined which do not have their origin in the
  //that node, so do no longer pursue their pathes

  //step/state currently indicate this last step (as result of last while)
  for (s=0;s<private->numStates;s++) {
    if (!originatesIn(context,
                      private->idx_end_trellis,
                      s,
                      step,
                      state)) {
      PR_DBG( 3, "Deleting end-node which became obsolete\n");
      private->metrics[private->idx_end_trellis * private->numStates + s] = METRIC_UNDEFINED;
    }
  }
  //this actually truncates the table (cuts off first truncblock entries)
  private->idx_start_trellis
    = (private->idx_start_trellis + private->truncblock)	% private->trunclength;

  swr_free(mlPath);

  //we dont need to mutex the stats, as this is already done in pdata
  stats->time_truncate += (get_time_usec()-start)/ 1000;

}

/**
* reads n bits from the input, or a flush bits if input does not provide more
* @param in The array to read from
* @return A value containing the read bits as its n LSB.
*/
int rcv_readBits(swr_sdb_t *context,U8* in) {
  int input=0x00;
  int bitsToRead=private->n;
  int temp;
  int consumeNow;

  while (bitsToRead>0) {	//we want to read n bits
    PR_DBG( 4, "processing input: %x, unconsumed:%d, bitsToRead:%d\n",
            in[private->inByteCounter],
            private->unconsumed,
            bitsToRead);

    if (private->inByteCounter < size_in(0)) {
      //cut off consumed part
      temp=in[private->inByteCounter] >> (8 - private->unconsumed);
    } else {
      //flush-input
      temp=0x00;
    }

    //number of bits to consume in this iteration
    //=min(unconsumed,bitsToRead)
    consumeNow = private->unconsumed > bitsToRead ? bitsToRead : private->unconsumed;

    //put the new bits to the input
    input=input | (temp << (private->n - bitsToRead));
    //and cut off unused bits
    input=input& private->mask_n;	//remove the bits which should not be here

    //decrement counters
    bitsToRead-=consumeNow;
    private->unconsumed-=consumeNow;

    //check if current byte completely consumed
    if (private->unconsumed==0) {
      private->inByteCounter++;
      private->unconsumed=8;
    }
  }

  PR_DBG( 4, "read the following incoming bits: %x\n",input);
  return input;
}

/**
* calculates possible successors and their metric for all defined states
* @param input The received bits (to calculate metrics, hammingDistance)
*/
void calculateSuccessors(swr_sdb_t *context,stats_t *stats,int input) {
  double start=get_time_usec();
  int idx_next_trellis=(private->idx_end_trellis+1)%private->trunclength;
  //mark all new as not yet calculated
  int s;
  int origData;
  int p;
  int validInput;
  REG_STATUS adder;
  int ctr;
  int newMetrics;
  int oldMetrics;

  for (s=0;s<private->numStates;s++) {
    private->metrics[idx_next_trellis*private->numStates+s]=METRIC_UNDEFINED;
  }

  //Calculate for all possible states
  for (s=0;s<private->numStates;s++) {
    if (private->metrics[private->idx_end_trellis * private->numStates + s]
        != METRIC_UNDEFINED) {
      //This state s is actually reached by a path. Calculate successors
      REG_STATUS oldStatus=s;

      //iterate over all original data
      for (origData=0x00 ; origData < private->numValidInputs ; origData++) {
        REG_STATUS newStatus = private->newStateLookup[oldStatus * private->numValidInputs
                               + origData];

        //calculate a validInput applying the polynom sum to newStatus
	validInput=0x00;
        for (p = private->n-1 ; p>=0 ; p--) {
	  adder=(private->polys)[p] & newStatus;
	  ctr=countOnes(adder,private->m);	//counts the 1's

          PR_DBG(4,"New Status %x, poly[%d] is %x, added is %x, #ones is %d\n",
                 newStatus,p,(private->polys)[p],adder,ctr);

          validInput<<=1;	//make space for a bit
          if (ctr%2!=0) {
            validInput|=0x01;
          }
        }
        PR_DBG(4,"Status %x -> %x: Input was:%x, valid Input was:%x, hamming Dist is:%d\n",
               oldStatus,newStatus,input,validInput,hammingDistance(input,validInput,private->m));

	newMetrics = private->metrics[private->idx_end_trellis * private->numStates
				      + oldStatus]
	  +hammingDistance(input,validInput,private->m);
	oldMetrics = private->metrics[idx_next_trellis * private->numStates
				      + newStatus];
        //check if to this node another path was already calculated with lower metric
        if (newMetrics < oldMetrics) {
          //update metrics
          private->metrics[idx_next_trellis * private->numStates + newStatus]=newMetrics;
          //set predecessor
          private->trellis[idx_next_trellis * private->numStates + newStatus]=oldStatus;
        }
      }
    }
  }
  //we dont need to mutex the stats, as this is already done in pdata
  stats->time_calcsucc += (get_time_usec()-start)/ 1000;
}

/*
 * 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 ) {
  // Definition of variables - don't touch
  stats_t *stats;
  U8 *out;
  U8 *in;
  double start=get_time_usec();
  int i;
  int m;
  int input;
  int idx_next_trellis;

  in = buffer_in(0);	//Buffer of U8
  out = buffer_out(0);	//Buffer of U8

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

  //allocate memory for trellis and metrics
  if ( private->trellis ) {
    swr_free( private->trellis );
  }
  private->trellis=swr_malloc(private->trunclength*private->numStates*sizeof(REG_STATUS));

  if ( private->metrics ) {
    swr_free( private->metrics );
  }
  private->metrics =swr_malloc(private->trunclength*private->numStates*sizeof(int));

  //Fill metrics array with undefined
  for (m=0;m<private->numStates*private->trunclength;m++) {
    private->metrics[m]=METRIC_UNDEFINED;
  }

  //Set current trellis span from step 0 to step 0
  private->idx_start_trellis=0;
  private->idx_end_trellis=0;


  //init predecessor of first = 0-state
  private->trellis[private->idx_end_trellis * private->numStates + 0]=0;
  //init first state as 0 (set metrics to 0)
  private->metrics[private->idx_end_trellis * private->numStates + 0]=0;

  private->inByteCounter=0;
  private->unconsumed=8;

  private->outByteCounter=0;
  private->unusedOutBits=8;

  //init the out-array to 0 to be sure
  for (i=0;i<size_out(0);i++) {
    out[i]=0x00;
  }

  //generate until out-buffer is full.
  //empty flush-bytes will be used if in-buffer does not provide sufficient bytes

  PR_DBG( 4, "size_out(0):%d\n: ",size_out(0));

  while(private->outByteCounter<size_out(0)) {
    input=rcv_readBits(context,in);
    idx_next_trellis=(private->idx_end_trellis+1)%private->trunclength;

    PR_DBG( 4, "idx_start_trellis=%d, idx_next_trellis=%d, tunclength=%d\n",
            private->idx_start_trellis,
            idx_next_trellis,
            private->trunclength);

    //if idx_next_trellis==idx_start_trellis : we had one full cycle and need to truncate first!
    if (idx_next_trellis==private->idx_start_trellis) {
      PR_DBG( 4, "truncation needed. \n");
      truncateTrellis(context,stats,out);
    }

    //Calculate successors for all possible states
    calculateSuccessors(context,stats,input);

    //set end to now calculated step
    private->idx_end_trellis=idx_next_trellis;

    //display trellis for debug
    showTrellis(context);
  }


  stats->total_time_decode += (get_time_usec()-start)/ 1000;

  PR_DBG( 3, "secs in decode  : %f\n",stats->total_time_decode / 1000);
  PR_DBG( 3, "secs in truncate: %f\n",stats->time_truncate / 1000);
  PR_DBG( 3, "secs in calcsucc: %f\n",stats->time_calcsucc / 1000);

  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 ) {
  if ( private->polys ) {
    swr_free( private->polys );
  }
  if ( private->transitionLookup ) {
    swr_free( private->transitionLookup );
  }
  if ( private->newStateLookup ) {
    swr_free( private->newStateLookup );
  }
  if ( private->trellis ) {
    swr_free( private->trellis );
  }
  if ( private->metrics ) {
    swr_free( private->metrics );
  }

  if ( sizeof( private_t ) > 0 )
    swr_free( private );
  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 SPM
   * Give the following parameters:
   * Input-ports, output-ports, config-params, stat-params
   */
  desc = swr_spc_get_new_desc( 1, 1, 6, 3 );
  if ( !desc ) {
    PR_DBG( 0, "Can't initialise the module. This is BAD!\n" );
    return -1;
  }

  UM_STATS_DOUBLE( "total_time_decode" );
  UM_STATS_DOUBLE( "time_truncate" );
  UM_STATS_DOUBLE( "time_calcsucc" );

  /**
   * 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,DOUBLE_COMPLEX,STRING128,POINTER}( "name" );
   * UM_STATS_{INT,DOUBLE,DOUBLE_COMPLEX,STRING128,POINTER,BLOCK,IMAGE}( "name" );
   */
  UM_CONFIG_INT( "cfg_n" );
  UM_CONFIG_INT( "cfg_k" );
  UM_CONFIG_INT( "cfg_m" );
  UM_CONFIG_POINTER( "cfg_polys" );
  UM_CONFIG_INT( "cfg_trunclength" );
  UM_CONFIG_INT( "cfg_truncblock" );

  /**
   * 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,DOUBLE_{,COMPLEX}}, 0 );
   * UM_OUTPUT( SIG_{U8,SYMBOL_{S16,COMPLEX,MMX},SAMPLE_S12,S32,DOUBLE_{,COMPLEX}}, 0 );
   */
  UM_INPUT( SIG_U8, 0 );
  //SIG_U8 is what was encoded
  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_configure_inputs  = rcv_configure_inputs;
  desc->fn_configure_outputs = rcv_configure_outputs;
  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, "convolution_rcv" );
  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" );
  }
}