Merge remote-tracking branch 'tom/socis/master'

author: Johnathan Corgan <johnathan@corganlabs.com> 2015-09-23 07:25:23 -0700
committer: Johnathan Corgan <johnathan@corganlabs.com> 2015-09-23 07:25:23 -0700
commit: 45faa98d307f84c6000fe32d69f6c12eb8efd180 (patch)
tree: c9d1ec5f869028b5eca99bc6a49da825083d3395 /gr-fec/lib
parent: ffbd9d9c6c9d8c122d90462a96fc0f0f92a3c2b8 (diff)
parent: ad3a02f6c829e9b3ba9ebaef437e1a6087978855 (diff)
8 files changed, 1070 insertions, 1 deletions
diff --git a/gr-fec/lib/CMakeLists.txt b/gr-fec/lib/CMakeLists.txt
index 2c116fe726..0343ce3cfc 100644
--- a/gr-fec/lib/CMakeLists.txt
+++ b/gr-fec/lib/CMakeLists.txt
@@ -80,7 +80,13 @@ list(APPEND gnuradio_fec_sources
   alist.cc
   tpc_common.cc
   tpc_decoder.cc
-  tpc_encoder.cc 
+  tpc_encoder.cc
+  polar_encoder.cc
+  polar_decoder_sc.cc
+  polar_common.cc
+  polar_decoder_sc_list.cc
+  polar_decoder_common.cc
+  scl_list.cc
 )
 
 #Add Windows DLL resource file if using MSVC
diff --git a/gr-fec/lib/polar_common.cc b/gr-fec/lib/polar_common.cc
new file mode 100644
index 0000000000..ff78d3428e
--- /dev/null
+++ b/gr-fec/lib/polar_common.cc
@@ -0,0 +1,136 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gnuradio/io_signature.h>
+#include <gnuradio/fec/polar_common.h>
+
+#include <gnuradio/blocks/pack_k_bits.h>
+#include <gnuradio/blocks/unpack_k_bits.h>
+
+#include <cmath>
+#include <stdexcept>
+#include <iostream>
+#include <vector>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      polar_common::polar_common(int block_size, int num_info_bits,
+                                 std::vector<int> frozen_bit_positions,
+                                 std::vector<char> frozen_bit_values) :
+        d_frozen_bit_positions(frozen_bit_positions), d_frozen_bit_values(frozen_bit_values),
+        d_block_size(block_size), d_block_power((int) log2(float(block_size))),
+        d_num_info_bits(num_info_bits)
+      {
+        if(pow(2, d_block_power) != d_block_size){
+          throw std::runtime_error("block_size MUST be a power of 2!");
+        }
+
+        unsigned int num_frozen_bits = d_block_size - d_num_info_bits;
+        if(num_frozen_bits != d_frozen_bit_positions.size()){
+          throw std::runtime_error(
+                                   "number of frozen bit positions must equal block_size - num_info_bits");
+        }
+
+        // According to papers frozen bits default to '0'.
+        while(d_frozen_bit_values.size() < num_frozen_bits){
+          d_frozen_bit_values.push_back(0);
+        }
+        initialize_info_bit_position_vector();
+
+        d_unpacker = new gr::blocks::kernel::unpack_k_bits(8);
+      }
+
+      void
+      polar_common::initialize_info_bit_position_vector()
+      {
+        int num_frozen_bit = 0;
+        int frozen_pos = d_frozen_bit_positions.at(num_frozen_bit);
+        for(int i = 0; i < d_block_size; i++) {
+          if(i != frozen_pos) {
+            d_info_bit_positions.push_back((int) i);
+          }
+          else {
+            num_frozen_bit++;
+            num_frozen_bit = std::min(num_frozen_bit, (int) (d_frozen_bit_positions.size() - 1));
+            frozen_pos = d_frozen_bit_positions.at(num_frozen_bit);
+          }
+        }
+
+        if((int) d_info_bit_positions.size() != num_info_bits()) {
+          throw std::runtime_error("polar_common: number of info bit positions MUST equal num_info_bits (K)!");
+        }
+      }
+
+      polar_common::~polar_common()
+      {
+        delete d_unpacker;
+      }
+
+      long
+      polar_common::bit_reverse(long value, int active_bits) const
+      {
+        long r = 0;
+        for(int i = 0; i < active_bits; i++) {
+          r <<= 1;
+          r |= value & 1;
+          value >>= 1;
+        }
+        return r;
+      }
+
+      void
+      polar_common::print_packed_bit_array(const unsigned char* printed_array,
+                                           const int num_bytes) const
+      {
+        int num_bits = num_bytes << 3;
+        unsigned char* temp = new unsigned char[num_bits];
+        d_unpacker->unpack(temp, printed_array, num_bytes);
+
+        std::cout << "[";
+        for(int i = 0; i < num_bits; i++) {
+          std::cout << (int) *(temp + i) << " ";
+        }
+        std::cout << "]" << std::endl;
+
+        delete [] temp;
+      }
+
+      void
+      polar_common::print_unpacked_bit_array(const unsigned char* bits,
+                                             const unsigned int num_bytes) const
+      {
+        std::cout << "( ";
+        for(unsigned int i = 0; i < num_bytes; i++){
+          std::cout << (int) *bits++ << ", ";
+        }
+        std::cout << ")" << std::endl;
+      }
+
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/polar_decoder_common.cc b/gr-fec/lib/polar_decoder_common.cc
new file mode 100644
index 0000000000..8fc2e37fb7
--- /dev/null
+++ b/gr-fec/lib/polar_decoder_common.cc
@@ -0,0 +1,193 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gnuradio/io_signature.h>
+#include <gnuradio/fec/polar_decoder_common.h>
+#include <volk/volk.h>
+
+#include <cstdio>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      polar_decoder_common::polar_decoder_common(int block_size, int num_info_bits,
+                                                 std::vector<int> frozen_bit_positions,
+                                                 std::vector<char> frozen_bit_values) :
+        polar_common(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values),
+        d_frozen_bit_counter(0)
+      {
+      }
+
+      polar_decoder_common::~polar_decoder_common()
+      {
+      }
+
+      void
+      polar_decoder_common::initialize_decoder(unsigned char* u, float* llrs, const float* input)
+      {
+        volk_32f_s32f_multiply_32f(llrs + block_size() * block_power(), input, D_LLR_FACTOR, block_size());
+        memset(u, 0, sizeof(unsigned char) * block_size() * block_power());
+        d_frozen_bit_counter = 0;
+      }
+
+      float
+      polar_decoder_common::llr_odd(const float la, const float lb) const
+      {
+        return copysignf(1.0f, la) * copysignf(1.0f, lb) * std::min(fabs(la), fabs(lb));
+      }
+
+      float
+      polar_decoder_common::llr_even(const float la, const float lb, const unsigned char f) const
+      {
+        switch(f){
+        case 0:
+          return lb + la;
+        default:
+          return lb - la;
+        }
+      }
+
+      void
+      polar_decoder_common::butterfly(float* llrs, unsigned char* u, const int stage,
+                                      const int u_num, const int row)
+      {
+        butterfly_volk(llrs, u, stage, u_num, row);
+      }
+
+      void
+      polar_decoder_common::butterfly_generic(float* llrs, unsigned char* u, const int stage,
+                                              const int u_num, const int row)
+      {
+        const int next_stage = stage + 1;
+        const int half_stage_size = 0x01 << stage;
+        const int stage_size = half_stage_size << 1;
+        const bool is_upper_stage_half = row % stage_size < half_stage_size;
+
+        //      // this is a natural bit order impl
+        float* next_llrs = llrs + block_size(); // LLRs are stored in a consecutive array.
+        float* call_row_llr = llrs + row;
+
+        const int section = row - (row % stage_size);
+        const int jump_size = ((row % half_stage_size) << 1) % stage_size;
+
+        const int next_upper_row = section + jump_size;
+        const int next_lower_row = next_upper_row + 1;
+
+        const float* upper_right_llr_ptr = next_llrs + next_upper_row;
+        const float* lower_right_llr_ptr = next_llrs + next_lower_row;
+
+        if(!is_upper_stage_half){
+          const int u_pos = u_num >> stage;
+          const unsigned char f = u[u_pos - 1];
+          *call_row_llr = llr_even(*upper_right_llr_ptr, *lower_right_llr_ptr, f);
+          return;
+        }
+
+        if(block_power() > next_stage){
+          unsigned char* u_half = u + block_size();
+          odd_xor_even_values(u_half, u, u_num);
+          butterfly(next_llrs, u_half, next_stage, u_num, next_upper_row);
+
+          even_u_values(u_half, u, u_num);
+          butterfly(next_llrs, u_half, next_stage, u_num, next_lower_row);
+        }
+
+        *call_row_llr = llr_odd(*upper_right_llr_ptr, *lower_right_llr_ptr);
+      }
+
+      void
+      polar_decoder_common::butterfly_volk(float* llrs, unsigned char* u, const int stage,
+                                           const int u_num, const int row)
+      {
+        volk_32f_8u_polarbutterfly_32f(llrs, u, block_size(), block_power(), stage, u_num, row);
+      }
+
+
+      void
+      polar_decoder_common::even_u_values(unsigned char* u_even, const unsigned char* u,
+                                          const int u_num)
+      {
+        u++;
+        for(int i = 1; i < u_num; i += 2){
+          *u_even++ = *u;
+          u += 2;
+        }
+      }
+
+      void
+      polar_decoder_common::odd_xor_even_values(unsigned char* u_xor, const unsigned char* u,
+                                                const int u_num)
+      {
+        for(int i = 1; i < u_num; i += 2){
+          *u_xor++ = *u ^ *(u + 1);
+          u += 2;
+        }
+      }
+
+      const bool
+      polar_decoder_common::is_frozen_bit(const int u_num) const
+      {
+        return d_frozen_bit_counter < d_frozen_bit_positions.size() && u_num == d_frozen_bit_positions.at(d_frozen_bit_counter);
+      }
+
+
+      const unsigned char
+      polar_decoder_common::next_frozen_bit()
+      {
+        return d_frozen_bit_values[d_frozen_bit_counter++];
+      }
+
+      void
+      polar_decoder_common::extract_info_bits(unsigned char* output, const unsigned char* input) const
+      {
+        unsigned int frozenbit_num = 0;
+        for(int i = 0; i < block_size(); i++){
+          if(frozenbit_num < d_frozen_bit_positions.size() && d_frozen_bit_positions.at(frozenbit_num) == i){
+            frozenbit_num++;
+          }
+          else{
+            *output++ = *input;
+          }
+          input++;
+        }
+      }
+
+      void
+      polar_decoder_common::print_pretty_llr_vector(const float* llr_vec) const
+      {
+        for(int row = 0; row < block_size(); row++) {
+          std::cout << row << "->" << int(bit_reverse(row, block_power())) << ":\t";
+          for(int stage = 0; stage < block_power() + 1; stage++) {
+            printf("%+4.2f, ", llr_vec[(stage * block_size()) + row]);
+          }
+          std::cout << std::endl;
+        }
+      }
+
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/polar_decoder_sc.cc b/gr-fec/lib/polar_decoder_sc.cc
new file mode 100644
index 0000000000..c4ac8877ec
--- /dev/null
+++ b/gr-fec/lib/polar_decoder_sc.cc
@@ -0,0 +1,97 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gnuradio/io_signature.h>
+#include <gnuradio/fec/polar_decoder_sc.h>
+#include <volk/volk.h>
+
+#include <cmath>
+#include <cstdio>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      generic_decoder::sptr
+      polar_decoder_sc::make(int block_size, int num_info_bits,
+                             std::vector<int> frozen_bit_positions,
+                             std::vector<char> frozen_bit_values)
+      {
+        return generic_decoder::sptr
+          (new polar_decoder_sc(block_size, num_info_bits,
+                                frozen_bit_positions,
+                                frozen_bit_values));
+      }
+
+      polar_decoder_sc::polar_decoder_sc(int block_size, int num_info_bits,
+                                         std::vector<int> frozen_bit_positions,
+                                         std::vector<char> frozen_bit_values) :
+        polar_decoder_common(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+      {
+        d_llr_vec = (float*) volk_malloc(sizeof(float) * block_size * (block_power() + 1), volk_get_alignment());
+        memset(d_llr_vec, 0, sizeof(float) * block_size * (block_power() + 1));
+        d_u_hat_vec = (unsigned char*) volk_malloc(block_size * (block_power() + 1), volk_get_alignment());
+        memset(d_u_hat_vec, 0, sizeof(unsigned char) * block_size * (block_power() + 1));
+      }
+
+      polar_decoder_sc::~polar_decoder_sc()
+      {
+        volk_free(d_llr_vec);
+        volk_free(d_u_hat_vec);
+      }
+
+      void
+      polar_decoder_sc::generic_work(void* in_buffer, void* out_buffer)
+      {
+        const float *in = (const float*) in_buffer;
+        unsigned char *out = (unsigned char*) out_buffer;
+
+        initialize_decoder(d_u_hat_vec, d_llr_vec, in);
+        sc_decode(d_llr_vec, d_u_hat_vec);
+        extract_info_bits(out, d_u_hat_vec);
+      }
+
+      void
+      polar_decoder_sc::sc_decode(float* llrs, unsigned char* u)
+      {
+        for(int i = 0; i < block_size(); i++){
+          butterfly(llrs, u, 0, i, i);
+          u[i] = retrieve_bit_from_llr(llrs[i], i);
+        }
+      }
+
+      unsigned char
+      polar_decoder_sc::retrieve_bit_from_llr(float llr, const int pos)
+      {
+        if(is_frozen_bit(pos)){
+          return next_frozen_bit();
+        }
+        return llr_bit_decision(llr);
+      }
+
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/polar_decoder_sc_list.cc b/gr-fec/lib/polar_decoder_sc_list.cc
new file mode 100644
index 0000000000..903b9413da
--- /dev/null
+++ b/gr-fec/lib/polar_decoder_sc_list.cc
@@ -0,0 +1,123 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gnuradio/io_signature.h>
+#include <gnuradio/fec/polar_decoder_sc_list.h>
+#include <volk/volk.h>
+#include <scl_list.h>
+
+#include <cmath>
+#include <algorithm>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      generic_decoder::sptr
+      polar_decoder_sc_list::make(int max_list_size, int block_size, int num_info_bits,
+                                  std::vector<int> frozen_bit_positions,
+                                  std::vector<char> frozen_bit_values)
+      {
+        return generic_decoder::sptr
+          (new polar_decoder_sc_list(max_list_size, block_size, num_info_bits,
+                                     frozen_bit_positions,
+                                     frozen_bit_values));
+      }
+
+      polar_decoder_sc_list::polar_decoder_sc_list(int max_list_size, int block_size,
+                                                   int num_info_bits,
+                                                   std::vector<int> frozen_bit_positions,
+                                                   std::vector<char> frozen_bit_values)
+        : polar_decoder_common(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+      {
+        d_scl = new polar::scl_list(max_list_size, block_size, block_power());
+      }
+
+      polar_decoder_sc_list::~polar_decoder_sc_list()
+      {
+        delete d_scl;
+      }
+
+      void
+      polar_decoder_sc_list::generic_work(void* in_buffer, void* out_buffer)
+      {
+        const float *in = (const float*) in_buffer;
+        unsigned char *out = (unsigned char*) out_buffer;
+
+        initialize_list(in);
+        const unsigned char* temp = decode_list();
+        extract_info_bits(out, temp);
+      }
+
+      void
+      polar_decoder_sc_list::initialize_list(const float* in_buf)
+      {
+        polar::path* init_path = d_scl->initial_path();
+        initialize_decoder(init_path->u_vec, init_path->llr_vec, in_buf);
+      }
+
+      const unsigned char*
+      polar_decoder_sc_list::decode_list()
+      {
+        for(int u_num = 0; u_num < block_size(); u_num++){
+          decode_bit(u_num);
+        }
+        return d_scl->optimal_path()->u_vec;
+      }
+
+      void
+      polar_decoder_sc_list::decode_bit(const int u_num)
+      {
+        calculate_llrs_for_list(u_num);
+        set_bit_in_list(u_num);
+      }
+
+      void
+      polar_decoder_sc_list::calculate_llrs_for_list(const int u_num)
+      {
+        for(unsigned int i = 0; i < d_scl->active_size(); i++){
+          polar::path* current_path = d_scl->next_active_path();
+          butterfly(current_path->llr_vec, current_path->u_vec, 0, u_num, u_num);
+        }
+      }
+
+      void
+      polar_decoder_sc_list::set_bit_in_list(const int u_num)
+      {
+        // 1. if frozen bit, update with known value
+        if(is_frozen_bit(u_num)){
+          const unsigned char frozen_bit = next_frozen_bit();
+          d_scl->set_frozen_bit(frozen_bit, u_num);
+        }
+        // 2. info bit
+        else{
+          d_scl->set_info_bit(u_num);
+        }
+      }
+
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/polar_encoder.cc b/gr-fec/lib/polar_encoder.cc
new file mode 100644
index 0000000000..350f490487
--- /dev/null
+++ b/gr-fec/lib/polar_encoder.cc
@@ -0,0 +1,234 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gnuradio/io_signature.h>
+#include <gnuradio/fec/polar_encoder.h>
+#include <cmath>
+#include <stdexcept>
+#include <volk/volk.h>
+
+#include <gnuradio/blocks/pack_k_bits.h>
+#include <gnuradio/blocks/unpack_k_bits.h>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      generic_encoder::sptr
+      polar_encoder::make(int block_size, int num_info_bits,
+                          std::vector<int> frozen_bit_positions,
+                          std::vector<char> frozen_bit_values, bool is_packed)
+      {
+        return generic_encoder::sptr
+          (new polar_encoder(block_size, num_info_bits,
+                             frozen_bit_positions,
+                             frozen_bit_values,
+                             is_packed));
+      }
+
+      polar_encoder::polar_encoder(int block_size, int num_info_bits,
+                                   std::vector<int>& frozen_bit_positions,
+                                   std::vector<char>& frozen_bit_values, bool is_packed) :
+        polar_common(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values),
+        d_is_packed(is_packed)
+      {
+        setup_frozen_bit_inserter();
+        setup_volk_vectors();
+      }
+
+      void
+      polar_encoder::setup_frozen_bit_inserter()
+      {
+        d_frozen_bit_prototype = (unsigned char*) volk_malloc(block_size() >> 3,
+                                                              volk_get_alignment());
+        memset(d_frozen_bit_prototype, 0, block_size() >> 3);
+
+        for(unsigned int i = 0; i < d_frozen_bit_positions.size(); i++) {
+          int rev_pos = (int) bit_reverse((long) d_frozen_bit_positions.at(i), block_power());
+          unsigned char frozen_bit = (unsigned char) d_frozen_bit_values.at(i);
+          insert_unpacked_bit_into_packed_array_at_position(d_frozen_bit_prototype, frozen_bit,
+                                                            rev_pos);
+        }
+
+        for(unsigned int i = 0; i < d_info_bit_positions.size(); i++){
+          d_info_bit_reversed_positions.push_back((int) bit_reverse((long) d_info_bit_positions.at(i), block_power()));
+        }
+
+        if((int) d_info_bit_reversed_positions.size() != num_info_bits()) {
+          throw std::runtime_error("polar_encoder: number of info bit positions MUST equal num_info_bits (K)!");
+        }
+      }
+
+      void
+      polar_encoder::setup_volk_vectors()
+      {
+        int nfrozen = block_size() - num_info_bits();
+        d_temp = (unsigned char*) volk_malloc(sizeof(unsigned char) * block_size(), volk_get_alignment());
+        d_frozen_bit_mask = (unsigned char*) volk_malloc(sizeof(unsigned char) * block_size(), volk_get_alignment());
+        d_frozen_bits = (unsigned char*) volk_malloc(sizeof(unsigned char) * nfrozen, volk_get_alignment());
+        for(int i = 0; i < nfrozen; i++){
+          d_frozen_bits[i] = d_frozen_bit_values[i];
+        }
+
+        int nfbit = 0;
+        for(int i = 0; i < block_size(); i++){
+          unsigned char m = 0x00;
+          if(d_frozen_bit_positions[nfbit] == i){
+            m = 0xFF;
+            nfbit++;
+          }
+          d_frozen_bit_mask[i] = m;
+        }
+      }
+
+      polar_encoder::~polar_encoder()
+      {
+        volk_free(d_frozen_bit_prototype);
+
+        volk_free(d_temp);
+        volk_free(d_frozen_bit_mask);
+        volk_free(d_frozen_bits);
+      }
+
+      void
+      polar_encoder::generic_work(void* in_buffer, void* out_buffer)
+      {
+        const unsigned char *in = (const unsigned char*) in_buffer;
+        unsigned char *out = (unsigned char*) out_buffer;
+
+        if(d_is_packed){
+          insert_packed_frozen_bits_and_reverse(out, in);
+          encode_vector_packed(out);
+        }
+        else{
+          volk_encode(out, in);
+        }
+      }
+
+      void
+      polar_encoder::volk_encode(unsigned char* out_buf, const unsigned char* in_buf)
+      {
+        volk_8u_x3_encodepolar_8u_x2(out_buf, d_temp, d_frozen_bit_mask, d_frozen_bits, in_buf, block_size());
+      }
+
+      void
+      polar_encoder::encode_vector_packed(unsigned char* target) const
+      {
+        encode_vector_packed_subbyte(target);
+        encode_vector_packed_interbyte(target);
+      }
+
+      void
+      polar_encoder::encode_vector_packed_subbyte(unsigned char* target) const
+      {
+        int num_bytes_per_block = block_size() >> 3;
+        while(num_bytes_per_block) {
+          encode_packed_byte(target);
+          ++target;
+          --num_bytes_per_block;
+        }
+      }
+
+      void
+      polar_encoder::encode_packed_byte(unsigned char* target) const
+      {
+        // this method only produces correct results if block_size > 4.
+        // this is assumed to be the case.
+        *target ^= 0xaa & (*target << 1);
+        *target ^= 0xcc & (*target << 2);
+        *target ^= *target << 4;
+      }
+
+      void
+      polar_encoder::encode_vector_packed_interbyte(unsigned char* target) const
+      {
+        int branch_byte_size = 1;
+        unsigned char* pos;
+        int n_branches = block_size() >> 4;
+        int byte = 0;
+        for(int stage = 3; stage < block_power(); ++stage) {
+          pos = target;
+
+          for(int branch = 0; branch < n_branches; ++branch) {
+
+            byte = 0;
+            while(byte < branch_byte_size) {
+              *pos ^= *(pos + branch_byte_size);
+              ++pos;
+              ++byte;
+            }
+
+            pos += branch_byte_size;
+          }
+
+          n_branches >>= 1;
+          branch_byte_size <<= 1;
+        }
+      }
+
+      void
+      polar_encoder::insert_packed_frozen_bits_and_reverse(unsigned char* target,
+                                                           const unsigned char* input) const
+      {
+        memcpy(target, d_frozen_bit_prototype, block_size() >> 3);
+        const int* info_bit_reversed_positions_ptr = &d_info_bit_reversed_positions[0];
+        int bit_num = 0;
+        unsigned char byte = *input;
+        int bit_pos;
+        while(bit_num < num_info_bits()) {
+          bit_pos = *info_bit_reversed_positions_ptr++;
+          insert_packet_bit_into_packed_array_at_position(target, byte, bit_pos, bit_num % 8);
+          ++bit_num;
+          if(bit_num % 8 == 0) {
+            ++input;
+            byte = *input;
+          }
+        }
+      }
+
+      void
+      polar_encoder::insert_unpacked_bit_into_packed_array_at_position(unsigned char* target,
+                                                                       const unsigned char bit,
+                                                                       const int pos) const
+      {
+        int byte_pos = pos >> 3;
+        int bit_pos = pos & 0x7;
+        *(target + byte_pos) ^= bit << (7 - bit_pos);
+      }
+
+      void
+      polar_encoder::insert_packet_bit_into_packed_array_at_position(unsigned char* target,
+                                                                     const unsigned char bit,
+                                                                     const int target_pos,
+                                                                     const int bit_pos) const
+      {
+        insert_unpacked_bit_into_packed_array_at_position(target, (bit >> (7 - bit_pos)) & 0x01,
+                                                          target_pos);
+      }
+
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/scl_list.cc b/gr-fec/lib/scl_list.cc
new file mode 100644
index 0000000000..ab6e81d317
--- /dev/null
+++ b/gr-fec/lib/scl_list.cc
@@ -0,0 +1,193 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#include <scl_list.h>
+#include <cstring>
+#include <iostream>
+#include <algorithm>
+#include <volk/volk.h>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+      namespace polar {
+
+        scl_list::scl_list(const unsigned int size,
+                           const unsigned int block_size,
+                           const unsigned int block_power):
+          d_list_size(size), d_block_size(block_size), d_block_power(block_power),
+          d_num_buff_elements(block_size * (block_power + 1))
+        {
+          for(unsigned int i = 0; i < 2 * size; i++){
+            d_path_list.push_back(new path());
+          }
+
+          for(unsigned int i = 0; i < size; i++){
+            d_path_list[i]->llr_vec = (float*) volk_malloc(sizeof(float) * d_num_buff_elements, volk_get_alignment());
+            memset(d_path_list[i]->llr_vec, 0, sizeof(float) * d_num_buff_elements);
+            d_path_list[i]->u_vec = (unsigned char*) volk_malloc(sizeof(unsigned char) * d_num_buff_elements, volk_get_alignment());
+            memset(d_path_list[i]->u_vec, 0, sizeof(unsigned char) * d_num_buff_elements);
+            d_path_list[i]->owns_vectors = true;
+          }
+
+          d_path_list[0]->is_active = true;
+          d_active_path_counter = 1;
+          d_active_pos = 0;
+        }
+
+        scl_list::~scl_list()
+        {
+          for(unsigned int i = 0; i < d_path_list.size(); i++){
+            delete d_path_list[i];
+          }
+        }
+
+
+        const path*
+        scl_list::optimal_path()
+        {
+          const path* temp = *std::min_element(d_path_list.begin(), d_path_list.begin() + d_active_path_counter, path_compare);
+          reset();
+          return temp;
+        }
+
+        void
+        scl_list::reset()
+        {
+          // leave 0th element active for next iteration
+          d_path_list[0]->path_metric = 0.0f;
+          for(unsigned int i = 1; i < d_path_list.size(); i++){
+            d_path_list[i]->is_active = false;
+            d_path_list[i]->path_metric = 0.0f;
+          }
+          d_active_path_counter = 1;
+          d_active_pos = 0;
+        }
+
+        void
+        scl_list::set_info_bit(const int bit_pos)
+        {
+          if(d_active_path_counter < d_list_size) {
+            const int offset = d_active_path_counter;
+            for(int i = 0; i < offset; i++) {
+              duplicate_path(d_path_list[i + offset], d_path_list[i]);
+              d_path_list[i]->path_metric = update_path_metric(d_path_list[i]->path_metric,
+                                                               d_path_list[i]->llr_vec[bit_pos], 0);
+              d_path_list[i + offset]->path_metric = update_path_metric
+                (d_path_list[i + offset]->path_metric, d_path_list[i + offset]->llr_vec[bit_pos], 1);
+              d_path_list[i]->u_vec[bit_pos] = 0;
+              d_path_list[i + offset]->u_vec[bit_pos] = 1;
+            }
+          }
+          else {
+
+            for(unsigned int i = 0; i < d_list_size; i++) {
+              branch_paths(d_path_list[i + d_list_size], d_path_list[i], d_path_list[i]->llr_vec[bit_pos]);
+            }
+            std::sort(d_path_list.begin(), d_path_list.end(), path_compare);
+
+            for(unsigned int i = 0; i < d_list_size; i++) {
+              if(!d_path_list[i]->owns_vectors) {
+                int t_pos = d_list_size;
+                while(!d_path_list[t_pos]->owns_vectors) {
+                  t_pos++;
+                }
+                steal_vector_ownership(d_path_list[i], d_path_list[t_pos]);
+                d_path_list[i]->u_vec[bit_pos] = 1;
+              }
+              else{
+                d_path_list[i]->u_vec[bit_pos] = 0;
+              }
+            }
+          }
+          d_active_pos = 0;
+        }
+
+        void
+        scl_list::branch_paths(path* target, path* original, const float llr)
+        {
+          target->path_metric = update_path_metric(original->path_metric, llr, 1);
+          original->path_metric = update_path_metric(original->path_metric, llr, 0);
+          target->llr_vec = original->llr_vec;
+          target->u_vec = original->u_vec;
+        }
+
+        void
+        scl_list::steal_vector_ownership(path* target, path* original)
+        {
+          memcpy(original->llr_vec, target->llr_vec, sizeof(float) * d_num_buff_elements);
+          memcpy(original->u_vec, target->u_vec, sizeof(unsigned char) * d_num_buff_elements);
+          target->llr_vec = original->llr_vec;
+          target->u_vec = original->u_vec;
+          target->owns_vectors = true;
+          original->owns_vectors = false;
+        }
+
+        void
+        scl_list::duplicate_path(path* target, const path* original)
+        {
+          memcpy(target->llr_vec, original->llr_vec, sizeof(float) * d_num_buff_elements);
+          memcpy(target->u_vec, original->u_vec, sizeof(unsigned char) * d_num_buff_elements);
+          target->path_metric = original->path_metric;
+          d_active_path_counter++;
+          target->is_active = true;
+        }
+
+        float
+        scl_list::update_path_metric(const float last_pm, const float llr,
+                                     const float ui) const
+        {
+          if((ui == 0 && llr > 0.0f) || (ui == 1 && llr < 0.0f)){
+            //        if(ui == (unsigned char) (0.5 * 1 - copysignf(1.0f, llr))){
+            return last_pm;
+          }
+          return last_pm + fabs(llr);
+        }
+
+        void
+        scl_list::set_frozen_bit(const unsigned char frozen_bit, const int bit_pos)
+        {
+          for(unsigned int i = 0; i < d_active_path_counter; i++){
+            d_path_list[i]->u_vec[bit_pos] = frozen_bit;
+            d_path_list[i]->path_metric = update_path_metric(d_path_list[i]->path_metric,
+                                                             d_path_list[i]->llr_vec[bit_pos],
+                                                             frozen_bit);
+          }
+          d_active_pos = 0;
+        }
+
+        path::path():
+          path_metric(0.0f), owns_vectors(false), is_active(false), llr_vec(NULL), u_vec(NULL)
+        {
+        }
+
+        path::~path(){
+          if(owns_vectors){
+            volk_free(llr_vec);
+            volk_free(u_vec);
+          }
+        }
+
+      } /* namespace polar */
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
diff --git a/gr-fec/lib/scl_list.h b/gr-fec/lib/scl_list.h
new file mode 100644
index 0000000000..8f3fa66ac1
--- /dev/null
+++ b/gr-fec/lib/scl_list.h
@@ -0,0 +1,87 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2015 Free Software Foundation, Inc.
+ *
+ * This file is part of GNU Radio
+ *
+ * GNU Radio 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 3, or (at your option)
+ * any later version.
+ *
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifndef INCLUDED_FEC_SCL_LIST_H
+#define INCLUDED_FEC_SCL_LIST_H
+
+#include <vector>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+      namespace polar {
+
+        struct path {
+          path();
+          ~path();
+          float path_metric;
+          bool owns_vectors;
+          bool is_active;
+          float* llr_vec;
+          unsigned char* u_vec;
+        };
+
+        /*!
+         * \brief List implementation for Successive Cancellation List decoders
+         *
+         */
+        class scl_list{
+          const unsigned int d_list_size;
+          const unsigned int d_block_size;
+          const unsigned int d_block_power;
+          const unsigned int d_num_buff_elements;
+          std::vector<path*> d_path_list;
+          unsigned int d_active_path_counter;
+          unsigned int d_active_pos;
+
+          float update_path_metric(const float last_pm, const float llr, const float ui) const;
+          void duplicate_path(path* target, const path* original);
+          void branch_paths(path* target, path* original, const float llr);
+          void steal_vector_ownership(path* target, path* original);
+          void reset();
+
+          // comparator for std::sort
+          static bool path_compare(path* first, path* second) {
+            return first->path_metric < second->path_metric;
+          };
+
+        public:
+          scl_list(const unsigned int list_size, const unsigned int block_size,
+                   const unsigned int block_power);
+          virtual
+          ~scl_list();
+          const unsigned int size() const {return d_list_size;};
+          const unsigned int active_size() const {return d_active_path_counter;};
+
+          path* initial_path() const {return d_path_list[0];};
+          path* next_active_path(){return d_path_list[d_active_pos++];};
+          void set_frozen_bit(const unsigned char frozen_bit, const int bit_pos);
+          void set_info_bit(const int bit_pos);
+          const path* optimal_path();
+        };
+
+      } /* namespace polar */
+    } /* namespace code */
+  } /* namespace fec */
+} /* namespace gr */
+
+#endif /* INCLUDED_FEC_SCL_LIST_H */
author	Johnathan Corgan <johnathan@corganlabs.com>	2015-09-23 07:25:23 -0700
committer	Johnathan Corgan <johnathan@corganlabs.com>	2015-09-23 07:25:23 -0700
commit	45faa98d307f84c6000fe32d69f6c12eb8efd180 (patch)
tree	c9d1ec5f869028b5eca99bc6a49da825083d3395 /gr-fec/lib
parent	ffbd9d9c6c9d8c122d90462a96fc0f0f92a3c2b8 (diff)
parent	ad3a02f6c829e9b3ba9ebaef437e1a6087978855 (diff)