polar: systematic decoder added

Conflicts: gr-fec/grc/fec_block_tree.xml gr-fec/include/gnuradio/fec/CMakeLists.txt gr-fec/swig/fec_swig.i
author: Johannes Demel <ufcsy@student.kit.edu> 2015-10-13 13:46:01 +0200
committer: Johannes Demel <ufcsy@student.kit.edu> 2015-12-07 11:00:14 +0100
commit: 9ac7203fffb37fd456b82b737a71d4c7a1607b06 (patch)
tree: 05aeb10aa5604dcaa1516a6739f4ff321ce6ff12 /gr-fec
parent: e86d80c1402bffe32cc3addde0feee553f2d7c1c (diff)
10 files changed, 384 insertions, 5 deletions
diff --git a/gr-fec/grc/CMakeLists.txt b/gr-fec/grc/CMakeLists.txt
index 2b472ea4ad..27cb5af854 100644
--- a/gr-fec/grc/CMakeLists.txt
+++ b/gr-fec/grc/CMakeLists.txt
@@ -20,4 +20,3 @@
 ########################################################################
 file(GLOB xml_files "*.xml")
 install(FILES ${xml_files} DESTINATION ${GRC_BLOCKS_DIR} COMPONENT "fec_python")
-
diff --git a/gr-fec/grc/fec_block_tree.xml b/gr-fec/grc/fec_block_tree.xml
index 7c47bc7a78..5efc144cbd 100644
--- a/gr-fec/grc/fec_block_tree.xml
+++ b/gr-fec/grc/fec_block_tree.xml
@@ -15,9 +15,10 @@
       <block>variable_ldpc_decoder_def</block>
       <block>variable_ldpc_bit_flip_decoder_def</block>
       <block>variable_tpc_decoder_def</block>
+      <block>variable_dummy_decoder_def</block>
       <block>variable_polar_decoder_sc_def</block>
       <block>variable_polar_decoder_sc_list_def</block>
-      <block>variable_dummy_decoder_def</block>
+      <block>variable_polar_decoder_sc_systematic_def</block>
     </cat>
     <cat>
       <name>Encoders</name>
diff --git a/gr-fec/grc/variable_polar_decoder_sc_systematic.xml b/gr-fec/grc/variable_polar_decoder_sc_systematic.xml
new file mode 100644
index 0000000000..cefc7e237d
--- /dev/null
+++ b/gr-fec/grc/variable_polar_decoder_sc_systematic.xml
@@ -0,0 +1,68 @@
+<?xml version="1.0"?>
+<block>
+  <name>systematic POLAR Decoder SC Definition</name>
+  <key>variable_polar_decoder_sc_systematic_def</key>
+  <import>from gnuradio import fec</import>
+  <var_make>#if int($ndim())==0 #
+self.$(id) = $(id) = fec.polar_decoder_sc_systematic.make($block_size, $num_info_bits, $frozen_bit_positions) #slurp
+#else if int($ndim())==1 #
+self.$(id) = $(id) = map((lambda a: fec.polar_decoder_sc_systematic.make($block_size, $num_info_bits, $frozen_bit_positions)), range(0, $dim1) ) #slurp
+#else
+self.$(id) = $(id) = map((lambda b: map((lambda a: fec.polar_decoder_sc_systematic.make($block_size, $num_info_bits, $frozen_bit_positions)), range(0, $dim2))), range(0, $dim1)) #slurp
+#end if</var_make>
+  <var_value>fec.polar_decoder_sc_systematic.make($block_size, $num_info_bits, $frozen_bit_positions)</var_value>
+  <make></make>
+
+  <param>
+    <name>Parallelism</name>
+    <key>ndim</key>
+    <value>0</value>
+    <type>enum</type>
+    <option>
+      <name>0</name>
+      <key>0</key>
+    </option>
+    <option>
+      <name>1</name>
+      <key>1</key>
+    </option>
+    <option>
+      <name>2</name>
+      <key>2</key>
+      </option>
+  </param>
+
+  <param>
+    <name>Dimension 1</name>
+    <key>dim1</key>
+    <value>1</value>
+    <type>int</type>
+    <hide>#if (int($ndim()) >= 1) then 'none' else 'all' #</hide>
+  </param>
+
+  <param>
+    <name>Dimension 2</name>
+    <key>dim2</key>
+    <value>4</value>
+    <type>int</type>
+    <hide>#if (int($ndim()) >= 2) then 'none' else 'all' #</hide>
+  </param>
+
+  <param>
+    <name>Block size (N)</name>
+    <key>block_size</key>
+    <type>int</type>
+  </param>
+
+  <param>
+    <name>#Info Bits (K)</name>
+    <key>num_info_bits</key>
+    <type>int</type>
+  </param>
+
+  <param>
+    <name>Frozen Bit Positions</name>
+    <key>frozen_bit_positions</key>
+    <type>int_vector</type>
+  </param>
+</block>
diff --git a/gr-fec/include/gnuradio/fec/CMakeLists.txt b/gr-fec/include/gnuradio/fec/CMakeLists.txt
index fce5ff9367..aca8c8da84 100644
--- a/gr-fec/include/gnuradio/fec/CMakeLists.txt
+++ b/gr-fec/include/gnuradio/fec/CMakeLists.txt
@@ -54,8 +54,8 @@ install(FILES
     polar_common.h
     polar_decoder_sc_list.h
     polar_decoder_common.h
-	polar_encoder_systematic.h
-    DESTINATION ${GR_INCLUDE_DIR}/gnuradio/fec
+    polar_encoder_systematic.h
+    polar_decoder_sc_systematic.h DESTINATION ${GR_INCLUDE_DIR}/gnuradio/fec
     COMPONENT "fec_devel"
 )
 
diff --git a/gr-fec/include/gnuradio/fec/polar_decoder_sc_systematic.h b/gr-fec/include/gnuradio/fec/polar_decoder_sc_systematic.h
new file mode 100644
index 0000000000..36a0dc6ec4
--- /dev/null
+++ b/gr-fec/include/gnuradio/fec/polar_decoder_sc_systematic.h
@@ -0,0 +1,82 @@
+/* -*- 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_POLAR_DECODER_SC_SYSTEMATIC_H
+#define INCLUDED_FEC_POLAR_DECODER_SC_SYSTEMATIC_H
+
+#include <gnuradio/fec/api.h>
+#include <gnuradio/fec/polar_decoder_common.h>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      /*!
+       * \brief Standard systematic successive cancellation (SC) decoder for POLAR codes
+       *
+       * \details
+       * It expects float input with bits mapped 1 --> 1, 0 --> -1
+       * Or: f = 2.0 * bit - 1.0
+       *
+       * Systematic encoding indicates that the info bit values are present in the codeword.
+       * 'info_bit_positions' may be obtained by ordering all non frozen_bit_positions in increasing order.
+       * One may extract them at their positions after a bit reversal operation.
+       * encoder -> decoder chain would need additional bit-reversal after encoding + before decoding.
+       * This is unnecessary.
+       */
+    class FEC_API polar_decoder_sc_systematic : public polar_decoder_common
+    {
+    public:
+      /*!
+       * \param block_size codeword size. MUST be a power of 2.
+       * \param num_info_bits represents the number of information
+       *        bits in a block. Also called frame_size. <= block_size
+       * \param frozen_bit_positions is an integer vector which
+       *        defines the position of all frozen bits in a block.
+       *        Its size MUST be equal to block_size - num_info_bits.
+       *        Also it must be sorted and every position must only
+       *        occur once.
+       */
+      static generic_decoder::sptr make(int block_size, int num_info_bits,
+                                        std::vector<int> frozen_bit_positions);
+
+      ~polar_decoder_sc_systematic();
+
+      // FECAPI
+      void generic_work(void *in_buffer, void *out_buffer);
+    private:
+      polar_decoder_sc_systematic(int block_size, int num_info_bits, std::vector<int> frozen_bit_positions);
+      float* d_llr_vec;
+      unsigned char* d_u_hat_vec;
+      unsigned char* d_frame_vec;
+      unsigned char retrieve_bit_from_llr(float llr, const int pos);
+      void sc_decode(float* llrs, unsigned char* u);
+      void extract_info_bits_reversed(unsigned char* outbuf, const unsigned char* inbuf);
+    };
+
+    } /* namespace code */
+  } // namespace fec
+} // namespace gr
+
+#endif /* INCLUDED_FEC_POLAR_DECODER_SC_SYSTEMATIC_H */
+
diff --git a/gr-fec/include/gnuradio/fec/polar_encoder_systematic.h b/gr-fec/include/gnuradio/fec/polar_encoder_systematic.h
index 990b7bb0aa..8dd734df71 100644
--- a/gr-fec/include/gnuradio/fec/polar_encoder_systematic.h
+++ b/gr-fec/include/gnuradio/fec/polar_encoder_systematic.h
@@ -40,6 +40,12 @@ namespace gr {
        * \details
        * expects values with MSB first. It needs a full information word and encodes it in one pass.
        * Output is a codeword of block_size.
+       *
+       * Systematic encoding indicates that the info bit values are present in the codeword.
+       * 'info_bit_positions' may be obtained by ordering all non frozen_bit_positions in increasing order.
+       * One may extract them at their positions after a bit reversal operation.
+       * encoder -> decoder chain would need additional bit-reversal after encoding + before decoding.
+       * This is unnecessary.
        */
       class FEC_API polar_encoder_systematic: public generic_encoder, public polar_common
       {
diff --git a/gr-fec/lib/CMakeLists.txt b/gr-fec/lib/CMakeLists.txt
index ed73afee99..bda98016b0 100644
--- a/gr-fec/lib/CMakeLists.txt
+++ b/gr-fec/lib/CMakeLists.txt
@@ -88,6 +88,7 @@ list(APPEND gnuradio_fec_sources
   polar_decoder_common.cc
   scl_list.cc
     polar_encoder_systematic.cc
+    polar_decoder_sc_systematic.cc
 )
 
 #Add Windows DLL resource file if using MSVC
diff --git a/gr-fec/lib/polar_decoder_sc_systematic.cc b/gr-fec/lib/polar_decoder_sc_systematic.cc
new file mode 100644
index 0000000000..c65c80f7aa
--- /dev/null
+++ b/gr-fec/lib/polar_decoder_sc_systematic.cc
@@ -0,0 +1,101 @@
+/* -*- 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_systematic.h>
+#include <volk/volk.h>
+
+namespace gr {
+  namespace fec {
+    namespace code {
+
+      generic_decoder::sptr
+      polar_decoder_sc_systematic::make(int block_size, int num_info_bits,
+                                        std::vector<int> frozen_bit_positions)
+      {
+        return generic_decoder::sptr(
+            new polar_decoder_sc_systematic(block_size, num_info_bits, frozen_bit_positions));
+      }
+
+      polar_decoder_sc_systematic::polar_decoder_sc_systematic(
+          int block_size, int num_info_bits, std::vector<int> frozen_bit_positions) :
+              polar_decoder_common(block_size, num_info_bits, frozen_bit_positions, std::vector<char>())
+      {
+        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));
+        d_frame_vec = (unsigned char*) volk_malloc(block_size, volk_get_alignment());
+        memset(d_frame_vec, 0, sizeof(unsigned char) * block_size);
+      }
+
+      polar_decoder_sc_systematic::~polar_decoder_sc_systematic()
+      {
+      }
+
+      void
+      polar_decoder_sc_systematic::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);
+        volk_encode_block(d_frame_vec, d_u_hat_vec);
+        extract_info_bits_reversed(out, d_frame_vec);
+      }
+
+      void
+      polar_decoder_sc_systematic::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_systematic::retrieve_bit_from_llr(float llr, const int pos)
+      {
+        if(is_frozen_bit(pos)){
+          return next_frozen_bit();
+        }
+        return llr_bit_decision(llr);
+      }
+
+      void
+      polar_decoder_sc_systematic::extract_info_bits_reversed(unsigned char* outbuf,
+                                                              const unsigned char* inbuf)
+      {
+        for(int i = 0; i < num_info_bits(); i++){
+          *outbuf++ = inbuf[d_info_bit_positions_reversed[i]];
+        }
+      }
+
+    } // namespace code
+  } /* namespace fec */
+} /* namespace gr */
+
diff --git a/gr-fec/python/fec/qa_polar_decoder_sc_systematic.py b/gr-fec/python/fec/qa_polar_decoder_sc_systematic.py
new file mode 100644
index 0000000000..fb2381e069
--- /dev/null
+++ b/gr-fec/python/fec/qa_polar_decoder_sc_systematic.py
@@ -0,0 +1,117 @@
+#!/usr/bin/env python
+#
+# 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.
+#
+
+from gnuradio import gr, gr_unittest, blocks
+import fec_swig as fec
+
+import numpy as np
+from extended_decoder import extended_decoder
+from polar.encoder import PolarEncoder
+import polar.channel_construction as cc
+
+# import os
+# print('PID:', os.getpid())
+# raw_input('tell me smth')
+
+
+class test_polar_decoder_sc_systematic(gr_unittest.TestCase):
+
+    def setUp(self):
+        self.tb = gr.top_block()
+
+    def tearDown(self):
+        self.tb = None
+
+    def test_001_setup(self):
+        block_size = 16
+        num_info_bits = 8
+        frozen_bit_positions = np.arange(block_size - num_info_bits)
+
+        polar_decoder = fec.polar_decoder_sc_systematic.make(block_size, num_info_bits, frozen_bit_positions)
+
+        self.assertEqual(num_info_bits, polar_decoder.get_output_size())
+        self.assertEqual(block_size, polar_decoder.get_input_size())
+        self.assertFloatTuplesAlmostEqual((float(num_info_bits) / block_size, ), (polar_decoder.rate(), ))
+        self.assertFalse(polar_decoder.set_frame_size(10))
+
+    def test_002_one_vector(self):
+        block_power = 4
+        block_size = 2 ** block_power
+        num_info_bits = block_size // 2
+        frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0)
+
+        bits, gr_data = self.generate_test_data(block_size, num_info_bits, frozen_bit_positions, 1, False)
+
+        polar_decoder = fec.polar_decoder_sc_systematic.make(block_size, num_info_bits, frozen_bit_positions)
+        src = blocks.vector_source_f(gr_data, False)
+        dec_block = extended_decoder(polar_decoder, None)
+        snk = blocks.vector_sink_b(1)
+
+        self.tb.connect(src, dec_block)
+        self.tb.connect(dec_block, snk)
+        self.tb.run()
+
+        res = np.array(snk.data()).astype(dtype=int)
+        self.assertTupleEqual(tuple(res), tuple(bits))
+
+    def test_003_stream(self):
+        nframes = 3
+        block_power = 8
+        block_size = 2 ** block_power
+        num_info_bits = block_size // 2
+        frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0)
+
+        bits, gr_data = self.generate_test_data(block_size, num_info_bits, frozen_bit_positions, nframes, False)
+
+        polar_decoder = fec.polar_decoder_sc_systematic.make(block_size, num_info_bits, frozen_bit_positions)
+        src = blocks.vector_source_f(gr_data, False)
+        dec_block = extended_decoder(polar_decoder, None)
+        snk = blocks.vector_sink_b(1)
+
+        self.tb.connect(src, dec_block)
+        self.tb.connect(dec_block, snk)
+        self.tb.run()
+
+        res = np.array(snk.data()).astype(dtype=int)
+        self.assertTupleEqual(tuple(res), tuple(bits))
+
+    def generate_test_data(self, block_size, num_info_bits, frozen_bit_positions, nframes, onlyones):
+        frozen_bit_values = np.zeros(block_size - num_info_bits, dtype=int)
+        encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+        bits = np.array([], dtype=int)
+        data = np.array([], dtype=int)
+        for n in range(nframes):
+            if onlyones:
+                b = np.ones(num_info_bits, dtype=int)
+            else:
+                b = np.random.randint(2, size=num_info_bits)
+            d = encoder.encode_systematic(b)
+            bits = np.append(bits, b)
+            data = np.append(data, d)
+        gr_data = 2.0 * data - 1.0
+        return bits, gr_data
+
+
+if __name__ == '__main__':
+    gr_unittest.run(test_polar_decoder_sc_systematic)
+
+
diff --git a/gr-fec/swig/fec_swig.i b/gr-fec/swig/fec_swig.i
index 3a2f082fe8..2641931cda 100644
--- a/gr-fec/swig/fec_swig.i
+++ b/gr-fec/swig/fec_swig.i
@@ -58,6 +58,8 @@
 #include "gnuradio/fec/puncture_bb.h"
 #include "gnuradio/fec/puncture_ff.h"
 #include "gnuradio/fec/depuncture_bb.h"
+#include "gnuradio/fec/ldpc_encoder.h"
+#include "gnuradio/fec/ldpc_decoder.h"
 #include "gnuradio/fec/tpc_encoder.h"
 #include "gnuradio/fec/tpc_decoder.h"
 #include "gnuradio/fec/polar_encoder.h"
@@ -65,7 +67,8 @@
 #include "gnuradio/fec/polar_common.h"
 #include "gnuradio/fec/polar_decoder_sc_list.h"
 #include "gnuradio/fec/polar_decoder_common.h"
-#include "gnuradio/fec/ldpc_encoder.h"
+#include "gnuradio/fec/polar_encoder_systematic.h"
+#include "gnuradio/fec/polar_decoder_sc_systematic.h"
 %}
 
 %include "gnuradio/fec/generic_decoder.h"
@@ -98,6 +101,7 @@
 %include "gnuradio/fec/polar_decoder_sc_list.h"
 %include "gnuradio/fec/polar_decoder_common.h"
 %include "gnuradio/fec/polar_encoder_systematic.h"
+%include "gnuradio/fec/polar_decoder_sc_systematic.h"
 %include "gnuradio/fec/ldpc_encoder.h"
author	Johannes Demel <ufcsy@student.kit.edu>	2015-10-13 13:46:01 +0200
committer	Johannes Demel <ufcsy@student.kit.edu>	2015-12-07 11:00:14 +0100
commit	9ac7203fffb37fd456b82b737a71d4c7a1607b06 (patch)
tree	05aeb10aa5604dcaa1516a6739f4ff321ce6ff12 /gr-fec
parent	e86d80c1402bffe32cc3addde0feee553f2d7c1c (diff)