polar: SC and SC List decoder implemented in C++

author: Johannes Demel <ufcsy@student.kit.edu> 2015-06-18 12:14:32 +0200
committer: Johannes Demel <ufcsy@student.kit.edu> 2015-09-21 10:45:12 +0200
commit: 13592802e792a417b1db511dbb1d0445ff4955c8 (patch)
tree: 4ecb7d8f8527f9d501a22d871fcca5e0c4b3f838 /gr-fec/python
parent: 87670ad6f14e61bf4bde6c6e5b18d19b262fe33f (diff)
8 files changed, 358 insertions, 41 deletions
diff --git a/gr-fec/python/fec/polar/channel_construction_bec.py b/gr-fec/python/fec/polar/channel_construction_bec.py
index cd61f463f6..4d3654d010 100644
--- a/gr-fec/python/fec/polar/channel_construction_bec.py
+++ b/gr-fec/python/fec/polar/channel_construction_bec.py
@@ -87,6 +87,12 @@ def get_frozen_bit_indices_from_capacities(chan_caps, nfrozen):
     return np.sort(indexes)
 
 
+def get_bec_frozen_indices(nblock, kfrozen, eta):
+    bec_caps = calculate_bec_channel_capacities(eta, nblock)
+    positions = get_frozen_bit_indices_from_capacities(bec_caps, kfrozen)
+    return positions
+
+
 def bec_channel_contruction_tests():
     n = 2 ** 10
     k = n // 2
diff --git a/gr-fec/python/fec/polar/channel_construction_bsc.py b/gr-fec/python/fec/polar/channel_construction_bsc.py
index 8cee7ceac5..2263bf0091 100755
--- a/gr-fec/python/fec/polar/channel_construction_bsc.py
+++ b/gr-fec/python/fec/polar/channel_construction_bsc.py
@@ -23,23 +23,6 @@ from helper_functions import *
 import matplotlib.pyplot as plt
 
 
-# def bit_reverse(value, n):
-#     # is this really missing in NumPy???
-#     bits = np.zeros(n, type(value))
-#     for index in range(n):
-#         mask = 1
-#         mask = np.left_shift(mask, index)
-#         bit = np.bitwise_and(value, mask)
-#         bit = np.right_shift(bit, index)
-#         bits[index] = bit
-#     bits = bits[::-1]
-#     result = 0
-#     for index, bit in enumerate(bits):
-#         bit = np.left_shift(bit, index)
-#         result += bit
-#     return result
-
-
 def get_Bn(n):
     # this is a bit reversal matrix.
     lw = int(np.log2(n))  # number of used bits
diff --git a/gr-fec/python/fec/polar/decoder.py b/gr-fec/python/fec/polar/decoder.py
index d74f1f9e1a..ef7d70081f 100644
--- a/gr-fec/python/fec/polar/decoder.py
+++ b/gr-fec/python/fec/polar/decoder.py
@@ -122,16 +122,27 @@ class PolarDecoder(PolarCommon):
             u = np.append(u, ui)
         return u
 
+    def _llr_retrieve_bit(self, llr, pos):
+        f_index = np.where(self.frozen_bit_position == pos)[0]
+        if not f_index.size == 0:
+            ui = self.frozenbits[f_index][0]
+        else:
+            ui = self._llr_bit_decision(llr)
+        return ui
+
     def _butterfly_decode_bits(self, pos, graph, u):
+        bit_num = u.size
         llr = graph[pos][0]
-        ui = self._llr_bit_decision(llr)
+        ui = self._llr_retrieve_bit(llr, bit_num)
+        # ui = self._llr_bit_decision(llr)
         u = np.append(u, ui)
         lower_right = pos + (self.N // 2)
         la = graph[pos][1]
         lb = graph[lower_right][1]
         graph[lower_right][0] = self._llr_even(la, lb, ui)
         llr = graph[lower_right][0]
-        ui = self._llr_bit_decision(llr)
+        # ui = self._llr_bit_decision(llr)
+        ui = self._llr_retrieve_bit(llr, u.size)
         u = np.append(u, ui)
         return graph, u
 
diff --git a/gr-fec/python/fec/polar/helper_functions.py b/gr-fec/python/fec/polar/helper_functions.py
index ffa4fc17dc..213f3cb7c0 100644
--- a/gr-fec/python/fec/polar/helper_functions.py
+++ b/gr-fec/python/fec/polar/helper_functions.py
@@ -19,6 +19,7 @@
 #
 
 import numpy as np
+from channel_construction_bec import get_bec_frozen_indices
 
 
 def is_power_of_two(num):
@@ -72,7 +73,8 @@ def pack_byte(bits):
 
 def get_frozen_bit_positions(directory, n, k, p):
     import glob, os
-    os.chdir(directory)
+    if not os.getcwd().endswith(directory):
+        os.chdir(directory)
     prefix = 'frozen_bit_positions_'
     prefix_len = len(prefix)
     for file in glob.glob("*.npy"):
@@ -90,7 +92,7 @@ def get_frozen_bit_positions(directory, n, k, p):
         pstr = float(pstr[0][1:])
         if n == nstr and k == kstr:
             return np.load(filename)
-    return np.arange(k)
+    return get_bec_frozen_indices(n, k, p)
 
 
 def main():
diff --git a/gr-fec/python/fec/polar/testbed.py b/gr-fec/python/fec/polar/testbed.py
index 4ace91ee47..bdf9ae437c 100755
--- a/gr-fec/python/fec/polar/testbed.py
+++ b/gr-fec/python/fec/polar/testbed.py
@@ -67,6 +67,24 @@ def approx_value(la, lb):
     return np.sign(la) * np.sign(lb) * np.minimum(np.abs(la), np.abs(lb))
 
 
+def path_metric_exact(last_pm, llr, ui):
+    return last_pm + np.log(1 + np.exp(-1. * llr * (1 - 2 * ui)))
+
+
+def path_metric_approx(last_pm, llr, ui):
+    if ui == int(.5 * (1 - np.sign(llr))):
+        return last_pm
+    return last_pm + np.abs(llr)
+
+
+def calculate_path_metric_vector(metric, llrs, us):
+    res = np.zeros(llrs.size)
+    res[0] = metric(0, llrs[0], us[0])
+    for i in range(1, llrs.size):
+        res[i] = metric(res[i - 1], llrs[i], us[i])
+    return res
+
+
 def test_1024_rate_1_code():
     # effectively a Monte-Carlo simulation for channel polarization.
     ntests = 10000
@@ -135,11 +153,12 @@ def main():
     # frozenbitposition = np.array((0, 1, 2, 3, 4, 5, 8, 9), dtype=int)
     # print frozenbitposition
 
-    test_enc_dec_chain()
+    # test_enc_dec_chain()
 
     # test_1024_rate_1_code()
 
-    # channel_analysis()
+    channel_analysis()
+
 
 if __name__ == '__main__':
     main()
 \ No newline at end of file
diff --git a/gr-fec/python/fec/qa_polar_decoder_sc.py b/gr-fec/python/fec/qa_polar_decoder_sc.py
new file mode 100644
index 0000000000..f26bf9a91a
--- /dev/null
+++ b/gr-fec/python/fec/qa_polar_decoder_sc.py
@@ -0,0 +1,152 @@
+#!/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 Crypto.Cipher._AES import block_size
+
+from gnuradio import gr, gr_unittest, blocks
+import fec_swig as fec
+from _qa_helper import _qa_helper
+import numpy as np
+import os
+
+from extended_encoder import extended_encoder
+from extended_decoder import extended_decoder
+from polar.encoder import PolarEncoder
+from polar.decoder import PolarDecoder
+from polar.helper_functions import get_frozen_bit_positions
+# from polar.helper_functions import bit_reverse_vector
+
+# print('PID:', os.getpid())
+# raw_input('tell me smth')
+
+class test_polar_decoder_sc(gr_unittest.TestCase):
+
+    def setUp(self):
+        self.tb = gr.top_block()
+
+    def tearDown(self):
+        self.tb = None
+
+    def test_001_setup(self):
+        is_packed = False
+        block_size = 16
+        num_info_bits = 8
+        frozen_bit_positions = np.arange(block_size - num_info_bits)
+        frozen_bit_values = np.array([],)
+
+        polar_decoder = fec.polar_decoder_sc.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+
+        self.assertEqual(num_info_bits, polar_decoder.get_output_size())
+        self.assertEqual(block_size, polar_decoder.get_input_size())
+        self.assertFloatTuplesAlmostEqual((float(block_size) / num_info_bits, ), (polar_decoder.rate(), ))
+        self.assertFalse(polar_decoder.set_frame_size(10))
+
+    def test_002_one_vector(self):
+        print "test_002_one_vector"
+        is_packed = False
+        block_power = 8
+        block_size = 2 ** block_power
+        num_info_bits = 2 ** (block_power - 1)
+        num_frozen_bits = block_size - num_info_bits
+        frozen_bit_positions = get_frozen_bit_positions('polar', block_size, num_frozen_bits, 0.11)
+        frozen_bit_values = np.array([0] * num_frozen_bits,)
+        print frozen_bit_positions
+
+        python_decoder = PolarDecoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+
+        bits = np.ones(num_info_bits, dtype=int)
+        # bits = np.random.randint(2, size=num_info_bits)
+        encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+        data = encoder.encode(bits)
+        # data = np.array([0, 1, 1, 0, 1, 0, 1, 0], dtype=int)
+        gr_data = -2.0 * data + 1.0
+
+        polar_decoder = fec.polar_decoder_sc.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+        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)
+
+        ref = python_decoder.decode(data)
+
+        print("input:", data)
+        print("res  :", res)
+        print("ref  :", ref)
+
+        self.assertTupleEqual(tuple(res), tuple(ref))
+
+    def test_003_stream(self):
+        print "test_002_stream"
+        nframes = 3
+        is_packed = False
+        block_power = 8
+        block_size = 2 ** block_power
+        num_info_bits = 2 ** (block_power - 1)
+        num_frozen_bits = block_size - num_info_bits
+        frozen_bit_positions = get_frozen_bit_positions('polar', block_size, num_frozen_bits, 0.11)
+        frozen_bit_values = np.array([0] * num_frozen_bits,)
+        print frozen_bit_positions
+
+        python_decoder = PolarDecoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+        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):
+            b = np.random.randint(2, size=num_info_bits)
+            d = encoder.encode(b)
+            bits = np.append(bits, b)
+            data = np.append(data, d)
+        # bits = np.ones(num_info_bits, dtype=int)
+        # bits = np.random.randint(2, size=num_info_bits)
+        # data = encoder.encode(bits)
+        # data = np.array([0, 1, 1, 0, 1, 0, 1, 0], dtype=int)
+        gr_data = -2.0 * data + 1.0
+
+        polar_decoder = fec.polar_decoder_sc.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+        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)
+
+        # ref = python_decoder.decode(data)
+
+        print("input:", data)
+        print("res  :", res)
+        # print("ref  :", ref)
+
+        self.assertTupleEqual(tuple(res), tuple(bits))
+
+
+if __name__ == '__main__':
+    gr_unittest.run(test_polar_decoder_sc)
+
+
diff --git a/gr-fec/python/fec/qa_polar_decoder_sc_list.py b/gr-fec/python/fec/qa_polar_decoder_sc_list.py
new file mode 100644
index 0000000000..f698a4e01c
--- /dev/null
+++ b/gr-fec/python/fec/qa_polar_decoder_sc_list.py
@@ -0,0 +1,157 @@
+#!/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
+import os
+
+from extended_encoder import extended_encoder
+from extended_decoder import extended_decoder
+from polar.encoder import PolarEncoder
+from polar.decoder import PolarDecoder
+from polar.helper_functions import get_frozen_bit_positions
+# from polar.helper_functions import bit_reverse_vector
+#
+# print('PID:', os.getpid())
+# raw_input('tell me smth')
+
+class test_polar_decoder_sc_list(gr_unittest.TestCase):
+
+    def setUp(self):
+        self.tb = gr.top_block()
+
+    def tearDown(self):
+        self.tb = None
+
+    def test_001_setup(self):
+        is_packed = False
+        block_size = 16
+        num_info_bits = 8
+        max_list_size = 4
+        frozen_bit_positions = np.arange(block_size - num_info_bits)
+        frozen_bit_values = np.array([],)
+
+        polar_decoder = fec.polar_decoder_sc_list.make(max_list_size, block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+
+        self.assertEqual(num_info_bits, polar_decoder.get_output_size())
+        self.assertEqual(block_size, polar_decoder.get_input_size())
+        self.assertFloatTuplesAlmostEqual((float(block_size) / num_info_bits, ), (polar_decoder.rate(), ))
+        self.assertFalse(polar_decoder.set_frame_size(10))
+
+    def test_002_one_vector(self):
+        print "test_002_one_vector"
+        is_packed = False
+        expo = 6
+        block_size = 2 ** expo
+        num_info_bits = 2 ** (expo - 1)
+        max_list_size = 2 ** (expo - 2)
+        num_frozen_bits = block_size - num_info_bits
+        frozen_bit_positions = get_frozen_bit_positions('polar', block_size, num_frozen_bits, 0.11)
+        frozen_bit_values = np.array([0] * num_frozen_bits,)
+        print(frozen_bit_positions)
+
+        python_decoder = PolarDecoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+
+        # data = np.ones(block_size, dtype=int)
+        bits = np.random.randint(2, size=num_info_bits)
+        # bits = np.ones(num_info_bits, dtype=int)
+        encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+        data = encoder.encode(bits)
+        # data = np.array([0, 1, 1, 0, 1, 0, 1, 0], dtype=int)
+        gr_data = -2.0 * data + 1.0
+
+        polar_decoder = fec.polar_decoder_sc_list.make(max_list_size, block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+        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)
+
+        ref = python_decoder.decode(data)
+
+        print("input:", data)
+        print("res  :", res)
+        print("ref  :", ref)
+        print("bits :", bits)
+
+        self.assertTupleEqual(tuple(res), tuple(ref))
+
+    def test_003_stream(self):
+        print "test_003_stream"
+        nframes = 5
+        is_packed = False
+        expo = 8
+        block_size = 2 ** expo
+        num_info_bits = 2 ** (expo - 1)
+        max_list_size = 2 ** (expo - 2)
+        num_frozen_bits = block_size - num_info_bits
+        frozen_bit_positions = get_frozen_bit_positions('polar', block_size, num_frozen_bits, 0.11)
+        frozen_bit_values = np.array([0] * num_frozen_bits,)
+        print(frozen_bit_positions)
+
+        encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
+
+        # data = np.ones(block_size, dtype=int)
+        ref = np.array([], dtype=int)
+        data = np.array([], dtype=int)
+        for i in range(nframes):
+            b = np.random.randint(2, size=num_info_bits)
+            d = encoder.encode(b)
+            data = np.append(data, d)
+            ref = np.append(ref, b)
+
+        # bits = np.ones(num_info_bits, dtype=int)
+        # data = encoder.encode(bits)
+        # data = np.array([0, 1, 1, 0, 1, 0, 1, 0], dtype=int)
+        gr_data = -2.0 * data + 1.0
+
+        polar_decoder = fec.polar_decoder_sc_list.make(max_list_size, block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
+        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)
+
+
+        print("input:", data)
+        print("res  :", res)
+        print("ref  :", ref)
+
+        self.assertTupleEqual(tuple(res), tuple(ref))
+
+
+
+
+if __name__ == '__main__':
+    gr_unittest.run(test_polar_decoder_sc_list)
+
+
+
diff --git a/gr-fec/python/fec/qa_polar_encoder.py b/gr-fec/python/fec/qa_polar_encoder.py
index 03629354f0..4af193e2d4 100644
--- a/gr-fec/python/fec/qa_polar_encoder.py
+++ b/gr-fec/python/fec/qa_polar_encoder.py
@@ -22,14 +22,11 @@
 
 from gnuradio import gr, gr_unittest, blocks
 import fec_swig as fec
-from _qa_helper import _qa_helper
 import numpy as np
 
 from extended_encoder import extended_encoder
-from extended_decoder import extended_decoder
 from polar.encoder import PolarEncoder
 from polar.helper_functions import get_frozen_bit_positions
-from polar.helper_functions import bit_reverse_vector
 
 
 class test_polar_encoder(gr_unittest.TestCase):
@@ -61,21 +58,17 @@ class test_polar_encoder(gr_unittest.TestCase):
         frozen_bit_values = np.array([0] * num_frozen_bits,)
         python_encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values)
 
-        is_packed = False
+        is_packed = True
         polar_encoder = fec.polar_encoder.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed)
 
         data = np.ones(num_info_bits, dtype=int)
         src = blocks.vector_source_b(data, False)
-        packer = blocks.pack_k_bits_bb(8)
         enc_block = extended_encoder(polar_encoder, None, '11')
-        unpacker = blocks.unpack_k_bits_bb(8)
         snk = blocks.vector_sink_b(1)
 
-        if is_packed:
-            self.tb.connect(src, packer, enc_block, unpacker, snk)
-        else:
-            self.tb.connect(src, enc_block, snk)
+        self.tb.connect(src, enc_block, snk)
         self.tb.run()
+        print(self.tb.edge_list())
 
         res = np.array(snk.data()).astype(dtype=int)
         penc = python_encoder.encode(data)
@@ -85,7 +78,7 @@ class test_polar_encoder(gr_unittest.TestCase):
         self.assertTupleEqual(tuple(res), tuple(penc))
 
     def test_003_big_input(self):
-        is_packed = False
+        is_packed = True
         num_blocks = 30
         block_size = 256
         num_info_bits = 128
@@ -106,19 +99,13 @@ class test_polar_encoder(gr_unittest.TestCase):
 
 
         src = blocks.vector_source_b(data, False)
-        packer = blocks.pack_k_bits_bb(8)
         enc_block = extended_encoder(polar_encoder, None, '11')
-        unpacker = blocks.unpack_k_bits_bb(8)
         snk = blocks.vector_sink_b(1)
 
-        if is_packed:
-            self.tb.connect(src, packer, enc_block, unpacker, snk)
-        else:
-            self.tb.connect(src, enc_block, snk)
+        self.tb.connect(src, enc_block, snk)
         self.tb.run()
 
         res = np.array(snk.data()).astype(dtype=int)
-        # penc = python_encoder.encode(data)
 
         print(res)
         print(ref)
author	Johannes Demel <ufcsy@student.kit.edu>	2015-06-18 12:14:32 +0200
committer	Johannes Demel <ufcsy@student.kit.edu>	2015-09-21 10:45:12 +0200
commit	13592802e792a417b1db511dbb1d0445ff4955c8 (patch)
tree	4ecb7d8f8527f9d501a22d871fcca5e0c4b3f838 /gr-fec/python
parent	87670ad6f14e61bf4bde6c6e5b18d19b262fe33f (diff)