git.gag.com Git - debian/gnuradio/blob - gr-error-correcting-codes/src/lib/libecc/code_metrics.cc

   1 /* -*- c++ -*- */
   2 /*
   3  * Copyright 2006 Free Software Foundation, Inc.
   4  *
   5  * This file is part of GNU Radio
   6  *
   7  * GNU Radio is free software; you can redistribute it and/or modify
   8  * it under the terms of the GNU General Public License as published by
   9  * the Free Software Foundation; either version 2, or (at your option)
  10  * any later version.
  11  *
  12  * GNU Radio is distributed in the hope that it will be useful,
  13  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  14  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15  * GNU General Public License for more details.
  16  *
  17  * You should have received a copy of the GNU General Public License
  18  * along with GNU Radio; see the file COPYING.  If not, write to
  19  * the Free Software Foundation, Inc., 51 Franklin Street,
  20  * Boston, MA 02110-1301, USA.
  21  */
  22
  23 #ifdef HAVE_CONFIG_H
  24 #include "config.h"
  25 #endif
  26
  27 #include <code_metrics.h>
  28 #include <iostream>
  29 #include <math.h>
  30 #include <assert.h>
  31
  32 template<typename pdf_fcn_io_t>
  33 code_metrics_table<pdf_fcn_io_t>*
  34 libecc_code_metrics_create_table
  35 (pdf_fcn_io_t (*pdf_fcn_0_bit) (pdf_fcn_io_t),
  36  pdf_fcn_io_t (*pdf_fcn_1_bit) (pdf_fcn_io_t),
  37  size_t n_samples,
  38  pdf_fcn_io_t min_sample,
  39  pdf_fcn_io_t max_sample,
  40  int sample_precision)
  41 {
  42   if (! pdf_fcn_0_bit) {
  43     std::cerr << "libecc_code_metrics_create_table: Error: "
  44       "pdf_fcn_0_bit must be a non-null pointer to function.\n";
  45     assert (0);
  46   }
  47   if (! pdf_fcn_1_bit) {
  48     std::cerr << "libecc_code_metrics_create_table: Error: "
  49       "pdf_fcn_0_bit must be a non-null pointer to function.\n";
  50     assert (0);
  51   }
  52   if (n_samples < 2) {
  53     std::cerr << "libecc_code_metrics_create_table: Error: "
  54       "n_samples must be at least 2.\n";
  55     assert (0);
  56   }
  57   if (min_sample >= max_sample) {
  58     std::cerr << "libecc_code_metrics_create_table: Error: "
  59       "min_sample must be less than max_sample.\n";
  60     assert (0);
  61   }
  62   if ((sample_precision < 0) | (sample_precision > 32)) {
  63     std::cerr << "libecc_code_metrics_create_table: Error: "
  64       "sample_precision must be between 0 and 32.\n";
  65     assert (0);
  66   }
  67
  68   code_metrics_table<pdf_fcn_io_t>* t_code_metrics_table;
  69
  70   if (sample_precision == 0) {
  71     // float
  72     t_code_metrics_table = new code_metrics_table_work
  73       <pdf_fcn_io_t, float>(pdf_fcn_0_bit,
  74                             pdf_fcn_1_bit,
  75                             n_samples,
  76                             min_sample,
  77                             max_sample);
  78   } else if (sample_precision <= 8) {
  79     // use char
  80     t_code_metrics_table = new code_metrics_table_work
  81       <pdf_fcn_io_t, unsigned char>(pdf_fcn_0_bit,
  82                                     pdf_fcn_1_bit,
  83                                     n_samples,
  84                                     min_sample,
  85                                     max_sample,
  86                                     sample_precision);
  87   } else if (sample_precision <= 16) {
  88     // use short
  89     t_code_metrics_table = new code_metrics_table_work
  90       <pdf_fcn_io_t, unsigned short>(pdf_fcn_0_bit,
  91                                      pdf_fcn_1_bit,
  92                                      n_samples,
  93                                      min_sample,
  94                                      max_sample,
  95                                      sample_precision);
  96   } else {
  97     // use long
  98     t_code_metrics_table = new code_metrics_table_work
  99       <pdf_fcn_io_t, unsigned long>(pdf_fcn_0_bit,
 100                                     pdf_fcn_1_bit,
 101                                     n_samples,
 102                                     min_sample,
 103                                     max_sample,
 104                                     sample_precision);
 105   }
 106
 107   return (t_code_metrics_table);
 108 }
 109
 110 template<typename pdf_fcn_io_t>
 111 code_metrics_table<pdf_fcn_io_t>::code_metrics_table
 112 (pdf_fcn_t pdf_fcn_0_bit,
 113  pdf_fcn_t pdf_fcn_1_bit,
 114  size_t n_samples,
 115  pdf_fcn_io_t min_sample,
 116  pdf_fcn_io_t max_sample)
 117 {
 118   // internally, all samples are taken as pdf_fcn_io_t initially, and
 119   // only converted to other values by their specific constructors.
 120
 121   d_n_samples = n_samples;
 122   d_max_sample = max_sample;
 123   d_min_sample = min_sample;
 124   d_delta = (max_sample - min_sample) / ((pdf_fcn_io_t) n_samples);
 125   d_pdf_fcn_0_bit = pdf_fcn_0_bit;
 126   d_pdf_fcn_1_bit = pdf_fcn_1_bit;
 127
 128   // use a sub-sample by 100 to better determine the actual "bin"
 129   // probability values for each actual sample.  Each "bin" is 100
 130   // delta's less than the min_sample up to the min_sample+delta; then
 131   // each delta; then from the max_sample-delta to 100 delta's more
 132   // than the max sample.  Once normalized, these give a reasonable
 133   // interpretation of the PDF function.
 134
 135   pdf_fcn_io_t d_sub_delta = d_delta / ((pdf_fcn_io_t) 100);
 136   pdf_fcn_io_t d_sub_min_sample = d_min_sample - ((pdf_fcn_io_t) 100)*d_delta;
 137   pdf_fcn_io_t d_sup_max_sample = d_max_sample + ((pdf_fcn_io_t) 100)*d_delta;
 138
 139   d_pdf_fcn_0_samples.assign (d_n_samples, 0);
 140   d_pdf_fcn_1_samples.assign (d_n_samples, 0);
 141
 142   pdf_fcn_io_t t_val, t_sum_0, t_sum_1, t_max_0, t_max_1, t_min_0, t_min_1;
 143   t_sum_0 = t_sum_1 = t_max_0 = t_max_1 = t_min_0 = t_min_1 = 0;
 144   size_t m = 0;
 145   t_val = d_sub_min_sample;
 146   for (; m < (d_n_samples - 1); m++) {
 147     pdf_fcn_io_t t_sample_0 = 1;
 148     pdf_fcn_io_t t_sample_1 = 1;
 149     for (; t_val < (d_min_sample+d_delta); t_val += d_sub_delta) {
 150       t_sample_0 += ((*d_pdf_fcn_0_bit)(t_val));
 151       t_sample_1 += ((*d_pdf_fcn_1_bit)(t_val));
 152     }
 153     d_pdf_fcn_0_samples[m] = t_sample_0;
 154     d_pdf_fcn_0_samples[m] = t_sample_1;
 155     t_sum_0 += t_sample_0;
 156     t_sum_1 += t_sample_1;
 157     if (m == 0) {
 158       t_max_0 = t_min_0 = t_sample_0;
 159       t_max_1 = t_min_1 = t_sample_1;
 160     } else {
 161       if (t_max_0 < t_sample_0)
 162         t_max_0 = t_sample_0;
 163       else if (t_min_0 > t_sample_0)
 164         t_min_0 = t_sample_0;
 165       if (t_max_1 < t_sample_1)
 166         t_max_1 = t_sample_1;
 167       else if (t_min_1 > t_sample_1)
 168         t_min_1 = t_sample_1;
 169     }
 170   }
 171
 172   pdf_fcn_io_t t_sample_0 = 1;
 173   pdf_fcn_io_t t_sample_1 = 1;
 174   for (; t_val < d_sup_max_sample; t_val += d_sub_delta) {
 175     t_sample_0 += ((*d_pdf_fcn_0_bit)(t_val));
 176     t_sample_1 += ((*d_pdf_fcn_1_bit)(t_val));
 177   }
 178   d_pdf_fcn_0_samples[m] = t_sample_0;
 179   d_pdf_fcn_0_samples[m] = t_sample_1;
 180   t_sum_0 += t_sample_0;
 181   t_sum_1 += t_sample_1;
 182   if (t_max_0 < t_sample_0)
 183     t_max_0 = t_sample_0;
 184   else if (t_min_0 > t_sample_0)
 185     t_min_0 = t_sample_0;
 186   if (t_max_1 < t_sample_1)
 187     t_max_1 = t_sample_1;
 188   else if (t_min_1 > t_sample_1)
 189     t_min_1 = t_sample_1;
 190
 191   // normalize to the sum, so that these are "real" probabilities.
 192
 193   for (m = 0; m < d_n_samples; m++) {
 194     d_pdf_fcn_0_samples[m] /= t_sum_0;
 195     d_pdf_fcn_1_samples[m] /= t_sum_1;
 196   }
 197   t_max_0 /= t_sum_0;
 198   t_min_0 /= t_sum_0;
 199   t_max_1 /= t_sum_1;
 200   t_min_1 /= t_sum_1;
 201
 202   // take the logf so that metrics can add
 203
 204   for (m = 0; m < d_n_samples; m++) {
 205     d_pdf_fcn_0_samples[m] = logf (d_pdf_fcn_0_samples[m]);
 206     d_pdf_fcn_1_samples[m] = logf (d_pdf_fcn_1_samples[m]);
 207   }
 208   t_max_0 = logf (t_max_0);
 209   t_min_0 = logf (t_min_0);
 210   t_max_1 = logf (t_max_1);
 211   t_min_1 = logf (t_min_1);
 212
 213   // higher (less negative) log-probabilities mean more likely; lower
 214   // (more negative) mean less likely.  Want metrics which are 0 when
 215   // most likely and more positive when less likely.  So subtract the
 216   // max, then negate and normalize to the min (new max) so that the
 217   // max value is 1 and the min value is 0.
 218
 219   for (m = 0; m < d_n_samples; m++) {
 220     d_pdf_fcn_0_samples[m] = ((d_pdf_fcn_0_samples[m] - t_max_0) /
 221                               (t_min_0 - t_max_0));
 222     d_pdf_fcn_1_samples[m] = ((d_pdf_fcn_1_samples[m] - t_max_1) /
 223                               (t_min_1 - t_max_1));
 224   }
 225
 226   // correct the delta to the lookup computations
 227
 228   d_delta = (max_sample - min_sample) / ((pdf_fcn_io_t)(n_samples-1));
 229 }
 230
 231 template<typename pdf_fcn_io_t, typename metric_t>
 232 code_metrics_table_work<pdf_fcn_io_t,metric_t>::code_metrics_table_work
 233 (pdf_fcn_t pdf_fcn_0_bit,
 234  pdf_fcn_t pdf_fcn_1_bit,
 235  size_t n_samples,
 236  pdf_fcn_io_t min_sample,
 237  pdf_fcn_io_t max_sample,
 238  int sample_precision)
 239   : code_metrics_table<pdf_fcn_io_t>
 240     (pdf_fcn_0_bit,
 241      pdf_fcn_1_bit,
 242      n_samples,
 243      min_sample,
 244      max_sample)
 245 {
 246   code_metrics_table<pdf_fcn_io_t>::d_out_item_size_bytes = sizeof (metric_t);
 247   code_metrics_table<pdf_fcn_io_t>::d_sample_precision = sample_precision;
 248
 249   // get the scale factor for converting from float to
 250   // sample_precision maps: 0 -> 0, 1 -> (2^sample_precision)-1 for
 251   // integers; there is no need for a mapping for float types, since
 252   // those are already in [0,1].
 253
 254   pdf_fcn_io_t t_mult = ((sample_precision == 0) ? 1 :
 255                          ((pdf_fcn_io_t)((2^sample_precision)-1)));
 256
 257   // convert the 0 bit metrics from float to integer
 258
 259   d_metric_table_0_bit.assign (n_samples, 0);
 260   for (size_t m = 0; m < n_samples; m++) {
 261     d_metric_table_0_bit[m] =
 262       (metric_t)((code_metrics_table<pdf_fcn_io_t>::d_pdf_fcn_0_samples[m]) *
 263                  t_mult);
 264   }
 265
 266   // clear the old float sample vectors to free memory
 267
 268   code_metrics_table<pdf_fcn_io_t>::d_pdf_fcn_0_samples.resize (0);
 269
 270   // convert the 1 bit metrics from float to integer
 271
 272   d_metric_table_1_bit.assign (n_samples, 0);
 273   for (size_t m = 0; m < n_samples; m++) {
 274     d_metric_table_1_bit[m] =
 275       (metric_t)((code_metrics_table<pdf_fcn_io_t>::d_pdf_fcn_1_samples[m]) *
 276                  t_mult);
 277   }
 278
 279   // clear the old float sample vectors to free memory
 280
 281   code_metrics_table<pdf_fcn_io_t>::d_pdf_fcn_1_samples.resize (0);
 282 }
 283
 284 template<typename pdf_fcn_io_t, typename metric_t>
 285 void
 286 code_metrics_table_work<pdf_fcn_io_t,metric_t>::lookup
 287 (pdf_fcn_io_t sym,
 288  void* bit_0,
 289  void* bit_1)
 290 {
 291   metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0;
 292   metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1;
 293
 294   if (sym <= code_metrics_table<pdf_fcn_io_t>::d_min_sample) {
 295     *l_bit_0 = d_metric_table_0_bit[0];
 296     *l_bit_1 = d_metric_table_1_bit[0];
 297     return;
 298   }
 299   if (sym >= code_metrics_table<pdf_fcn_io_t>::d_max_sample) {
 300     *l_bit_0 = d_metric_table_0_bit.back ();
 301     *l_bit_1 = d_metric_table_1_bit.back ();
 302     return;
 303   }
 304
 305   size_t l_ndx = (size_t) round
 306     ((double)((sym - code_metrics_table<pdf_fcn_io_t>::d_min_sample) /
 307               code_metrics_table<pdf_fcn_io_t>::d_delta));
 308   *l_bit_0 = d_metric_table_0_bit[l_ndx];
 309   *l_bit_1 = d_metric_table_1_bit[l_ndx];
 310 }
 311
 312 template<typename pdf_fcn_io_t, typename metric_t>
 313 void
 314 code_metrics_table_work<pdf_fcn_io_t,metric_t>::convert
 315 (size_t n_syms,
 316  pdf_fcn_io_t* sym,
 317  void* bit_0,
 318  void* bit_1)
 319 {
 320   metric_ptr_t l_bit_0 = (metric_ptr_t) bit_0;
 321   metric_ptr_t l_bit_1 = (metric_ptr_t) bit_1;
 322
 323   for (size_t m = n_syms; m > 0; m--)
 324     lookup (*sym++, (void*) l_bit_0++, (void*) l_bit_1++);
 325 }
 326
 327 // force the compiler to instantiate a particular version of the
 328 // templated super-class, for <float> PDF function precision because
 329 // all code_metrics classes are created by this function, this is the
 330 // only one which is required to instantaite.
 331
 332 template
 333 code_metrics_table<float>*
 334 libecc_code_metrics_create_table<float>
 335 (float (*pdf_fcn_0_bit) (float),
 336  float (*pdf_fcn_1_bit) (float),
 337  size_t n_samples,
 338  float min_sample,
 339  float max_sample,
 340  int sample_precision);
 341
 342 #if 0
 343   // for compute_all_outputs
 344
 345   d_n_code_outputs = n_code_outputs;
 346
 347   in_l[0].resize (d_n_code_outputs);
 348   in_l[1].resize (d_n_code_outputs);
 349   in_f[0].resize (d_n_code_outputs);
 350   in_f[1].resize (d_n_code_outputs);
 351
 352
 353
 354   if (n_code_outputs == 0) {
 355     std::cerr << "code_metrics::create: Error: # of code outputs "
 356       "must be positive.\n";
 357     assert (0);
 358   }
 359
 360
 361 template<typename pdf_fcn_io_t>
 362 void
 363 code_metrics<pdf_fcn_io_t>::compute_all_outputs
 364 (pdf_fcn_io_t* syms,
 365  std::vector<unsigned long>& out)
 366 {
 367   // use the first 'n_code_output' symbols, convert them into metrics,
 368   // then compute all possible (summation) combinations of them and
 369   // return those in the provided vector.
 370
 371   convert (d_n_code_outputs, syms,
 372            (void*)(&(in_l[0][0])), (void*)(&in_l[1][0]));
 373
 374   // assign the starting minimum metric to 0.  This is safe because
 375   // metrics are always non-negative.
 376
 377   unsigned long min_metric = 0;
 378   for (size_t m = 0; m < (((size_t)2) << d_n_code_outputs); m++) {
 379     size_t t_out_ndx = m;
 380     unsigned long t_metric = 0;
 381     for (size_t n = 0; n < d_n_code_outputs; n++, t_out_ndx >>= 1)
 382       t_metric += in_l[t_out_ndx&1][n];
 383     if (t_metric < min_metric)
 384       min_metric = t_metric;
 385     out[m] = t_metric;
 386   }
 387
 388   // normalize so that the minimum metric equals 0
 389
 390   for (size_t m = 0; m < d_n_code_outputs; m++)
 391     out[m] -= min_metric;
 392 }
 393
 394 template<typename pdf_fcn_io_t>
 395 void
 396 code_metrics<pdf_fcn_io_t>::compute_all_outputs
 397 (pdf_fcn_io_t* syms,
 398  std::vector<float>& out)
 399 {
 400   // use the first 'n_code_output' symbols, convert them into metrics,
 401   // then compute all possible (summation) combinations of them and
 402   // return those in the provided vector.
 403
 404   convert (d_n_code_outputs, syms,
 405            (void*)(&(in_f[0][0])), (void*)(&in_f[1][0]));
 406
 407   // assign the starting minimum metric to 0.  This is safe because
 408   // metrics are always non-negative.
 409
 410   float min_metric = 0;
 411   for (size_t m = 0; m < (((size_t)2) << d_n_code_outputs); m++) {
 412     size_t t_out_ndx = m;
 413     float t_metric = 0;
 414     for (size_t n = 0; n < d_n_code_outputs; n++, t_out_ndx >>= 1)
 415       t_metric += in_f[t_out_ndx&1][n];
 416     if (t_metric < min_metric)
 417       min_metric = t_metric;
 418     out[m] = t_metric;
 419   }
 420
 421   // normalize so that the minimum metric equals 0
 422
 423   for (size_t m = 0; m < d_n_code_outputs; m++)
 424     out[m] -= min_metric;
 425 }
 426 #endif