diff options
| -rw-r--r-- | gr-fec/examples/polar_ber_curve_gen.grc | 10 | ||||
| -rw-r--r-- | gr-fec/examples/polar_encoder_decoder_chain.grc | 115 | ||||
| -rw-r--r-- | gr-fec/include/gnuradio/fec/polar_decoder_common.h | 4 | ||||
| -rw-r--r-- | gr-fec/include/gnuradio/fec/polar_encoder.h | 15 | ||||
| -rw-r--r-- | gr-fec/lib/polar_common.cc | 7 | ||||
| -rw-r--r-- | gr-fec/lib/polar_decoder_common.cc | 60 | ||||
| -rw-r--r-- | gr-fec/lib/polar_decoder_sc.cc | 4 | ||||
| -rw-r--r-- | gr-fec/lib/polar_decoder_sc_list.cc | 2 | ||||
| -rw-r--r-- | gr-fec/lib/polar_encoder.cc | 102 | ||||
| -rw-r--r-- | gr-fec/python/fec/polar/channel_construction.py | 194 | ||||
| -rwxr-xr-x | gr-fec/python/fec/polar/channel_construction_bsc.py | 3 | ||||
| -rw-r--r-- | gr-fec/python/fec/polar/helper_functions.py | 77 | ||||
| -rwxr-xr-x | gr-fec/python/fec/polar/testbed.py | 4 | ||||
| -rw-r--r-- | gr-fec/python/fec/qa_polar_decoder_sc.py | 62 | ||||
| -rw-r--r-- | gr-fec/python/fec/qa_polar_encoder.py | 73 |
15 files changed, 507 insertions, 225 deletions
diff --git a/gr-fec/examples/polar_ber_curve_gen.grc b/gr-fec/examples/polar_ber_curve_gen.grc index 01fed838c4..b4e2f879eb 100644 --- a/gr-fec/examples/polar_ber_curve_gen.grc +++ b/gr-fec/examples/polar_ber_curve_gen.grc @@ -1,5 +1,5 @@ <?xml version='1.0' encoding='utf-8'?> -<?grc format='1' created='3.7.8'?> +<?grc format='1' created='3.7.8rc1'?> <flow_graph> <timestamp>Fri Jul 17 15:23:09 2015</timestamp> <block> @@ -13,6 +13,10 @@ <value></value> </param> <param> + <key>window_size</key> + <value>1920,1080</value> + </param> + <param> <key>category</key> <value>Custom</value> </param> @@ -68,10 +72,6 @@ <key>title</key> <value>polar code BER curve generator</value> </param> - <param> - <key>window_size</key> - <value>1920,1080</value> - </param> </block> <block> <key>variable</key> diff --git a/gr-fec/examples/polar_encoder_decoder_chain.grc b/gr-fec/examples/polar_encoder_decoder_chain.grc index 69fb68bcfe..f2501b998c 100644 --- a/gr-fec/examples/polar_encoder_decoder_chain.grc +++ b/gr-fec/examples/polar_encoder_decoder_chain.grc @@ -13,6 +13,10 @@ <value></value> </param> <param> + <key>window_size</key> + <value>1920, 1080</value> + </param> + <param> <key>category</key> <value>Custom</value> </param> @@ -25,10 +29,9 @@ tb.start() tb.wait() stop_time = time.time() - samps = 2 ** 22 diff = stop_time - start_time throughput = tb.head_samps / diff - print("exe time:", diff, ", with ", tb.head_samps, "samps, throughput: ", throughput)</value> + print("execution time: {0:.6f} for {1:e} samples with throughput: {2:,.2f} Sps".format(diff, tb.head_samps, throughput))</value> </param> <param> <key>description</key> @@ -48,7 +51,7 @@ </param> <param> <key>generate_options</key> - <value>qt_gui</value> + <value>no_gui</value> </param> <param> <key>id</key> @@ -78,9 +81,32 @@ <key>title</key> <value>POLAR Encoder and Decoder</value> </param> + </block> + <block> + <key>variable</key> <param> - <key>window_size</key> - <value>1920, 1080</value> + <key>comment</key> + <value></value> + </param> + <param> + <key>_enabled</key> + <value>True</value> + </param> + <param> + <key>_coordinate</key> + <value>(704, 35)</value> + </param> + <param> + <key>_rotation</key> + <value>0</value> + </param> + <param> + <key>id</key> + <value>block_size</value> + </param> + <param> + <key>value</key> + <value>2 ** 11</value> </param> </block> <block> @@ -107,18 +133,45 @@ </param> <param> <key>value</key> - <value>2 ** 22</value> + <value>2 ** 32# encoder: 32, decoder: 23</value> + </param> + </block> + <block> + <key>variable</key> + <param> + <key>comment</key> + <value></value> + </param> + <param> + <key>_enabled</key> + <value>True</value> + </param> + <param> + <key>_coordinate</key> + <value>(792, 35)</value> + </param> + <param> + <key>_rotation</key> + <value>0</value> + </param> + <param> + <key>id</key> + <value>n_info_bits</value> + </param> + <param> + <key>value</key> + <value>block_size / 2</value> </param> </block> <block> <key>variable_polar_code_configurator</key> <param> <key>num_info_bits</key> - <value>128</value> + <value>n_info_bits</value> </param> <param> <key>block_size</key> - <value>256</value> + <value>block_size</value> </param> <param> <key>channel</key> @@ -134,7 +187,7 @@ </param> <param> <key>_coordinate</key> - <value>(600, 139)</value> + <value>(704, 99)</value> </param> <param> <key>_rotation</key> @@ -146,22 +199,22 @@ </param> <param> <key>design_snr</key> - <value>2.0</value> + <value>-1.0</value> </param> <param> <key>mu</key> - <value>16</value> + <value>32</value> </param> </block> <block> <key>variable_polar_decoder_sc_def</key> <param> <key>num_info_bits</key> - <value>128</value> + <value>n_info_bits</value> </param> <param> <key>block_size</key> - <value>256</value> + <value>block_size</value> </param> <param> <key>comment</key> @@ -181,11 +234,11 @@ </param> <param> <key>frozen_bit_positions</key> - <value>range(128)</value> + <value>polar_config['positions']</value> </param> <param> <key>frozen_bit_values</key> - <value>[0] * 128</value> + <value>polar_config['values']</value> </param> <param> <key>_coordinate</key> @@ -212,11 +265,11 @@ <key>variable_polar_encoder_def</key> <param> <key>num_info_bits</key> - <value>128</value> + <value>n_info_bits</value> </param> <param> <key>block_size</key> - <value>256</value> + <value>block_size</value> </param> <param> <key>comment</key> @@ -236,11 +289,11 @@ </param> <param> <key>frozen_bit_positions</key> - <value>range(128)</value> + <value>polar_config['positions']</value> </param> <param> <key>frozen_bit_values</key> - <value>[0] * 128</value> + <value>polar_config['values']</value> </param> <param> <key>_coordinate</key> @@ -256,7 +309,7 @@ </param> <param> <key>is_packed</key> - <value>True</value> + <value>False</value> </param> <param> <key>ndim</key> @@ -267,11 +320,11 @@ <key>variable_polar_decoder_sc_list_def</key> <param> <key>num_info_bits</key> - <value>128</value> + <value>n_info_bits</value> </param> <param> <key>block_size</key> - <value>256</value> + <value>block_size</value> </param> <param> <key>comment</key> @@ -401,7 +454,7 @@ </param> <param> <key>_enabled</key> - <value>True</value> + <value>0</value> </param> <param> <key>_coordinate</key> @@ -495,7 +548,7 @@ </param> <param> <key>_enabled</key> - <value>True</value> + <value>0</value> </param> <param> <key>_coordinate</key> @@ -601,7 +654,7 @@ </param> <param> <key>_coordinate</key> - <value>(1160, 464)</value> + <value>(1152, 465)</value> </param> <param> <key>_rotation</key> @@ -648,7 +701,7 @@ </param> <param> <key>_enabled</key> - <value>True</value> + <value>0</value> </param> <param> <key>_coordinate</key> @@ -699,7 +752,7 @@ </param> <param> <key>_enabled</key> - <value>False</value> + <value>1</value> </param> <param> <key>encoder_list</key> @@ -750,7 +803,7 @@ </param> <param> <key>_coordinate</key> - <value>(968, 32)</value> + <value>(1208, 19)</value> </param> <param> <key>_rotation</key> @@ -1178,4 +1231,10 @@ <source_key>0</source_key> <sink_key>0</sink_key> </connection> + <connection> + <source_block_id>fec_extended_encoder_0</source_block_id> + <sink_block_id>blocks_head_0</sink_block_id> + <source_key>0</source_key> + <sink_key>0</sink_key> + </connection> </flow_graph> diff --git a/gr-fec/include/gnuradio/fec/polar_decoder_common.h b/gr-fec/include/gnuradio/fec/polar_decoder_common.h index 50003b6863..61a6564cc6 100644 --- a/gr-fec/include/gnuradio/fec/polar_decoder_common.h +++ b/gr-fec/include/gnuradio/fec/polar_decoder_common.h @@ -60,7 +60,9 @@ namespace gr { // preparation for decoding void initialize_llr_vector(float* llrs, const float* input); // basic algorithm methods - void butterfly(float* llrs, const int stage, unsigned char* u, const int u_num); + void butterfly(float* llrs, unsigned char* u, const int stage, const int u_num, const int row); + void butterfly_volk(float* llrs, unsigned char* u, const int stage, const int u_num, const int row); + void butterfly_generic(float* llrs, unsigned char* u, const int stage, const int u_num, const int row); void even_u_values(unsigned char* u_even, const unsigned char* u, const int u_num); void odd_xor_even_values(unsigned char* u_xor, const unsigned char* u, const int u_num); void demortonize_values(unsigned char* u); diff --git a/gr-fec/include/gnuradio/fec/polar_encoder.h b/gr-fec/include/gnuradio/fec/polar_encoder.h index 85208bf49a..20ff5dc3b1 100644 --- a/gr-fec/include/gnuradio/fec/polar_encoder.h +++ b/gr-fec/include/gnuradio/fec/polar_encoder.h @@ -51,23 +51,17 @@ namespace gr { const char* get_output_conversion(){return is_packed() ? "packed_bits" : "none";}; private: - 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_encoder(int block_size, int num_info_bits, std::vector<int>& frozen_bit_positions, std::vector<char>& frozen_bit_values, bool is_packed); std::vector<int> d_frozen_bit_positions; std::vector<int> d_info_bit_positions; std::vector<char> d_frozen_bit_values; - // for unpacked bits an 'easier-to-grasp' algorithm. - void insert_frozen_bits(unsigned char* target, const unsigned char* input); - void bit_reverse_vector(unsigned char* target, const unsigned char* input); - void encode_vector(unsigned char* target); - // c'tor method for packed algorithm setup. void setup_frozen_bit_inserter(); // methods insert input bits and frozen bits into packed array for encoding unsigned char* d_block_array; // use for encoding unsigned char* d_frozen_bit_prototype; // packed frozen bits are written onto it and later copies are used. - void insert_unpacked_frozen_bits_and_reverse(unsigned char* target, const unsigned char* input) const; void insert_packed_frozen_bits_and_reverse(unsigned char* target, const unsigned char* input) const; void insert_unpacked_bit_into_packed_array_at_position(unsigned char* target, const unsigned char bit, const int pos) const; void insert_packet_bit_into_packed_array_at_position(unsigned char* target, const unsigned char bit, const int target_pos, const int bit_pos) const; @@ -78,8 +72,13 @@ namespace gr { void encode_packed_byte(unsigned char* target) const; void encode_vector_packed_interbyte(unsigned char* target) const; + // VOLK methods + void setup_volk_vectors(); + void volk_encode(unsigned char* out_buf, const unsigned char* in_buf); + unsigned char* d_temp; + unsigned char* d_frozen_bit_mask; + unsigned char* d_frozen_bits; }; - } // namespace fec } // namespace gr diff --git a/gr-fec/lib/polar_common.cc b/gr-fec/lib/polar_common.cc index c76f5301a5..19caedf00c 100644 --- a/gr-fec/lib/polar_common.cc +++ b/gr-fec/lib/polar_common.cc @@ -77,16 +77,21 @@ namespace gr 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 < block_size(); i++) { - int frozen_pos = d_frozen_bit_positions.at(num_frozen_bit); 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() diff --git a/gr-fec/lib/polar_decoder_common.cc b/gr-fec/lib/polar_decoder_common.cc index bcb70fc0f2..2263795451 100644 --- a/gr-fec/lib/polar_decoder_common.cc +++ b/gr-fec/lib/polar_decoder_common.cc @@ -30,8 +30,6 @@ #include <cstdio> -#define INT_BIT_MASK 0x80000000 - namespace gr { namespace fec { @@ -73,40 +71,60 @@ namespace gr { } void - polar_decoder_common::butterfly(float* llrs, const int stage, unsigned char* u, const int u_num) + 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) { -// if(!(block_power() > stage)){ -// return; -// } const int next_stage = stage + 1; - const int stage_half_block_size = block_size() >> next_stage; - -// // this is a natural bit order impl - float* next_llrs = llrs + block_size(); // LLRs are stored in an consecutive array. - float* call_row_llr = llrs + u_num; - const int upper_right = u_num >> 1; // floor divide by 2. - const float* upper_right_llr_ptr = next_llrs + upper_right; - const float* lower_right_llr_ptr = upper_right_llr_ptr + stage_half_block_size; - - if(u_num % 2){ - const unsigned char f = u[u_num - 1]; -// const unsigned char f = fetch_bit_at_pos(u, u_num - 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) { + if(block_power() > next_stage){ unsigned char* u_half = u + block_size(); odd_xor_even_values(u_half, u, u_num); - butterfly(next_llrs, next_stage, u_half, upper_right); + butterfly(next_llrs, u_half, next_stage, u_num, next_upper_row); even_u_values(u_half, u, u_num); - butterfly(next_llrs + stage_half_block_size, next_stage, u_half, upper_right); + 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, diff --git a/gr-fec/lib/polar_decoder_sc.cc b/gr-fec/lib/polar_decoder_sc.cc index e4f64b5e99..7a290a8563 100644 --- a/gr-fec/lib/polar_decoder_sc.cc +++ b/gr-fec/lib/polar_decoder_sc.cc @@ -80,10 +80,8 @@ namespace gr d_frozen_bit_counter = 0; memset(u, 0, sizeof(unsigned char) * block_size() * block_power()); for(int i = 0; i < block_size(); i++){ - butterfly(llrs, 0, u, i); + butterfly(llrs, u, 0, i, i); u[i] = retrieve_bit_from_llr(llrs[i], i); -// const unsigned char bit = retrieve_bit_from_llr(llrs[i], i); -// insert_bit_at_pos(u, bit, i); } } diff --git a/gr-fec/lib/polar_decoder_sc_list.cc b/gr-fec/lib/polar_decoder_sc_list.cc index 9340e305d3..67b20f216d 100644 --- a/gr-fec/lib/polar_decoder_sc_list.cc +++ b/gr-fec/lib/polar_decoder_sc_list.cc @@ -115,7 +115,7 @@ namespace gr void polar_decoder_sc_list::calculate_next_llr(polar::path* current_path, int u_num) { - butterfly(current_path->llr_vec, 0, current_path->u_vec, u_num); + butterfly(current_path->llr_vec, current_path->u_vec, 0, u_num, u_num); } } /* namespace fec */ } /* namespace gr */ diff --git a/gr-fec/lib/polar_encoder.cc b/gr-fec/lib/polar_encoder.cc index 7187ea6120..40ffb05484 100644 --- a/gr-fec/lib/polar_encoder.cc +++ b/gr-fec/lib/polar_encoder.cc @@ -48,8 +48,8 @@ namespace gr } 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) : + 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, is_packed), d_frozen_bit_positions(frozen_bit_positions), d_frozen_bit_values(frozen_bit_values) @@ -61,6 +61,7 @@ namespace gr } setup_frozen_bit_inserter(); + setup_volk_vectors(); } void @@ -84,7 +85,29 @@ namespace gr } if((int) d_info_bit_positions.size() != num_info_bits()) { - throw std::runtime_error("number of info bit positions MUST equal num_info_bits (K)!"); + 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; } } @@ -92,6 +115,10 @@ namespace gr { volk_free(d_block_array); volk_free(d_frozen_bit_prototype); + + volk_free(d_temp); + volk_free(d_frozen_bit_mask); + volk_free(d_frozen_bits); } void @@ -105,14 +132,14 @@ namespace gr encode_vector_packed(out); } else { - insert_unpacked_frozen_bits_and_reverse(d_block_array, in); - encode_vector_packed(d_block_array); - unpacker()->unpack(out, d_block_array, block_size() >> 3); + volk_encode(out, in); } + } -// insert_frozen_bits(d_block_array, in); -// bit_reverse_vector(out, d_block_array); -// encode_vector(out); + 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 @@ -171,20 +198,6 @@ namespace gr } void - polar_encoder::insert_unpacked_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_positions_ptr = &d_info_bit_positions[0]; - const unsigned char* end_input = input + num_info_bits(); - int bit_pos = 7; - while(input < end_input) { - insert_packet_bit_into_packed_array_at_position(target, *input++, *info_bit_positions_ptr++, - bit_pos); - } - } - - void polar_encoder::insert_packed_frozen_bits_and_reverse(unsigned char* target, const unsigned char* input) const { @@ -223,48 +236,5 @@ namespace gr insert_unpacked_bit_into_packed_array_at_position(target, (bit >> (7 - bit_pos)) & 0x01, target_pos); } - - void - polar_encoder::insert_frozen_bits(unsigned char* target, const unsigned char* input) - { - int frozen_num = 0; - int num_frozen_bits = block_size() - num_info_bits(); - int info_num = 0; - for(int i = 0; i < block_size(); i++) { - if(frozen_num < num_frozen_bits && d_frozen_bit_positions.at(frozen_num) == i) { - target[i] = d_frozen_bit_values.at(frozen_num); - frozen_num++; - } - else { - target[i] = input[info_num]; - info_num++; - } - } - } - - void - polar_encoder::bit_reverse_vector(unsigned char* target, const unsigned char* input) - { - for(int i = 0; i < block_size(); i++) { - target[bit_reverse(long(i), block_power())] = input[i]; - } - } - - void - polar_encoder::encode_vector(unsigned char* target) - { - for(int stage = 0; stage < block_power(); stage++) { - int n_branches = pow(2, stage); - int branch_elements = block_size() / (2 * n_branches); - for(int branch = 0; branch < n_branches; branch++) { - for(int e = 0; e < branch_elements; e++) { - int pos = branch * branch_elements * 2 + e; - target[pos] ^= target[pos + branch_elements]; - } - } - } - } - } /* namespace fec */ } /* namespace gr */ - diff --git a/gr-fec/python/fec/polar/channel_construction.py b/gr-fec/python/fec/polar/channel_construction.py index f971ce4f61..9c38d3a7e6 100644 --- a/gr-fec/python/fec/polar/channel_construction.py +++ b/gr-fec/python/fec/polar/channel_construction.py @@ -28,6 +28,7 @@ import numpy as np from channel_construction_bec import calculate_bec_channel_capacities from channel_construction_bec import design_snr_to_bec_eta from channel_construction_bsc import tal_vardy_tpm_algorithm +from helper_functions import * import matplotlib.pyplot as plt @@ -39,7 +40,7 @@ def get_frozen_bit_indices_from_capacities(chan_caps, nfrozen): while indexes.size < nfrozen: index = np.argmin(chan_caps) indexes = np.append(indexes, index) - chan_caps[index] = 1.0 + chan_caps[index] = 2.0 # make absolutely sure value is out of range! return np.sort(indexes) @@ -109,19 +110,200 @@ def load_z_parameters(block_size, design_snr, mu): return z_params +def prepare_merger(frozen_mask): + mask = [] + for e in frozen_mask: + mask.append([e, ]) + return np.array(mask, dtype=int) + + +def merge_first_stage(init_mask): + merged_frozen_mask = [] + for e in range(0, len(init_mask), 2): + v = [init_mask[e]['value'][0], init_mask[e + 1]['value'][0]] + s = init_mask[e]['size'] * 2 + if init_mask[e]['type'] == init_mask[e + 1]['type']: + t = init_mask[e]['type'] + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + else: + t = 'RPT' + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + return merged_frozen_mask + + +def merge_second_stage(init_mask): + merged_frozen_mask = [] + for e in range(0, len(init_mask), 2): + if init_mask[e]['type'] == init_mask[e + 1]['type']: + t = init_mask[e]['type'] + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + elif init_mask[e]['type'] == 'ZERO' and init_mask[e + 1]['type'] == 'RPT': + t = init_mask[e + 1]['type'] + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + elif init_mask[e]['type'] == 'RPT' and init_mask[e + 1]['type'] == 'ONE': + t = 'SPC' + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + else: + merged_frozen_mask.append(init_mask[e]) + merged_frozen_mask.append(init_mask[e + 1]) + return merged_frozen_mask + + +def merge_stage_n(init_mask): + merged_frozen_mask = [] + n_elems = len(init_mask) - (len(init_mask) % 2) + for e in range(0, n_elems, 2): + if init_mask[e]['size'] == init_mask[e + 1]['size']: + if (init_mask[e]['type'] == 'ZERO' or init_mask[e]['type'] == 'ONE') and init_mask[e]['type'] == init_mask[e + 1]['type']: + t = init_mask[e]['type'] + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + elif init_mask[e]['type'] == 'ZERO' and init_mask[e + 1]['type'] == 'RPT': + t = init_mask[e + 1]['type'] + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + elif init_mask[e]['type'] == 'SPC' and init_mask[e + 1]['type'] == 'ONE': + t = init_mask[e]['type'] + v = init_mask[e]['value'] + v.extend(init_mask[e + 1]['value']) + s = init_mask[e]['size'] * 2 + merged_frozen_mask.append({'value': v, 'type': t, 'size': s}) + else: + merged_frozen_mask.append(init_mask[e]) + merged_frozen_mask.append(init_mask[e + 1]) + else: + merged_frozen_mask.append(init_mask[e]) + merged_frozen_mask.append(init_mask[e + 1]) + if n_elems < len(init_mask): + merged_frozen_mask.append(init_mask[-1]) + return merged_frozen_mask + + +def print_decode_subframes(subframes): + for e in subframes: + print(e) + + +def find_decoder_subframes(frozen_mask): + stages = power_of_2_int(len(frozen_mask)) + frame_size = 2 ** stages + + lock_mask = np.zeros(frame_size, dtype=int) + sub_mask = [] + + for e in frozen_mask: + if e == 1: + sub_mask.append(0) + else: + sub_mask.append(1) + sub_mask = np.array(sub_mask, dtype=int) + + for s in range(0, stages): + stage_size = 2 ** s + mask = np.reshape(sub_mask, (-1, stage_size)) + lock = np.reshape(lock_mask, (-1, stage_size)) + for p in range(0, (frame_size // stage_size) - 1, 2): + l0 = lock[p] + l1 = lock[p + 1] + first = mask[p] + second = mask[p + 1] + print(l0, l1) + print(first, second) + if np.all(l0 == l1): + for eq in range(2): + if np.all(first == eq) and np.all(second == eq): + mask[p].fill(eq) + mask[p + 1].fill(eq) + lock[p].fill(s) + lock[p + 1].fill(s) + + if np.all(first == 0) and np.all(second == 2): + mask[p].fill(2) + mask[p + 1].fill(2) + lock[p].fill(s) + lock[p + 1].fill(s) + + if np.all(first == 3) and np.all(second == 1): + mask[p].fill(3) + mask[p + 1].fill(3) + lock[p].fill(s) + lock[p + 1].fill(s) + + if s == 0 and np.all(first == 0) and np.all(second == 1): + mask[p].fill(2) + mask[p + 1].fill(2) + lock[p].fill(s) + lock[p + 1].fill(s) + + if s == 1 and np.all(first == 2) and np.all(second == 1): + mask[p].fill(3) + mask[p + 1].fill(3) + lock[p].fill(s) + lock[p + 1].fill(s) + + sub_mask = mask.flatten() + lock_mask = lock.flatten() + + words = {0: 'ZERO', 1: 'ONE', 2: 'RPT', 3: 'SPC'} + ll = lock_mask[0] + sub_t = sub_mask[0] + for i in range(len(frozen_mask)): + v = frozen_mask[i] + t = words[sub_mask[i]] + l = lock_mask[i] + # if i % 8 == 0: + # print + if not l == ll or not sub_mask[i] == sub_t: + print('--------------------------') + ll = l + sub_t = sub_mask[i] + print('{0:4} lock {1:4} value: {2} in sub {3}'.format(i, 2 ** (l + 1), v, t)) + + + def main(): + np.set_printoptions(precision=3, linewidth=150) print 'channel construction Bhattacharyya bounds by Arikan' - n = 8 + n = 10 m = 2 ** n k = m // 2 design_snr = -1.59 mu = 32 - # ztv = tal_vardy_tpm_algorithm(m, design_snr, mu) - z_params = load_z_parameters(m, design_snr, mu) - plt.plot(z_params) - plt.show() + # plt.plot(z_params) + # plt.show() + frozen_indices = get_frozen_bit_indices_from_z_parameters(z_params, k) + + frozen_mask = np.zeros(m, dtype=int) + frozen_mask[frozen_indices] = 1 + # frozen_mask = np.reshape(frozen_mask, (-1, 32)) + # for p in frozen_mask: + # print(p) + # if np.all(p == 1): + # print("zero rate") + # elif np.all(p == 0): + # print("ONE rate") + # elif p[0] == 1 and np.all(p[1:] == 0): + # print("SPC code") + # elif np.all(p[0:-1] == 1) and p[-1] == 0: + # print("REPETITION code") + + find_decoder_subframes(frozen_mask) + diff --git a/gr-fec/python/fec/polar/channel_construction_bsc.py b/gr-fec/python/fec/polar/channel_construction_bsc.py index fddad2e755..69acea861d 100755 --- a/gr-fec/python/fec/polar/channel_construction_bsc.py +++ b/gr-fec/python/fec/polar/channel_construction_bsc.py @@ -315,7 +315,7 @@ def normalize_q(q, tpm): def main(): print 'channel construction BSC main' - n = 8 + n = 10 m = 2 ** n k = m // 2 design_snr = 0.5 @@ -323,6 +323,7 @@ def main(): z_params = tal_vardy_tpm_algorithm(m, design_snr, mu) + print(z_params) plt.plot(z_params) plt.show() diff --git a/gr-fec/python/fec/polar/helper_functions.py b/gr-fec/python/fec/polar/helper_functions.py index e93fa9a507..72501beae3 100644 --- a/gr-fec/python/fec/polar/helper_functions.py +++ b/gr-fec/python/fec/polar/helper_functions.py @@ -20,6 +20,7 @@ import numpy as np import time, sys +import copy def power_of_2_int(num): @@ -119,24 +120,72 @@ def main(): for i in range(8): print(i, 'is power of 2: ', is_power_of_two(i)) - n = 2 ** 6 - k = n // 2 + n = 6 + m = 2 ** n + k = m // 2 eta = 0.3 - # frozen_bit_positions = get_frozen_bit_positions('.', 256, 128, 0.11) - # print(frozen_bit_positions) + pos = np.arange(m) + rev_pos = bit_reverse_vector(pos, n) + print(pos) + print(rev_pos) + + bound = 16 + num_lanes = m // bound + + + lanes = np.zeros((num_lanes, bound), dtype=int) + for i in range(0, num_lanes): + p = i * bound + part = rev_pos[p: p + bound] + lanes[i] = part + + print('reved lanes') + print(lanes) + + # SHUFFLE! + shuffle_pos = bit_reverse_vector(np.arange(bound), 4) + for i in range(num_lanes): + lane = lanes[i] + lanes[i] = lanes[i, shuffle_pos] + print('\nshuffled lanes') + print(lanes) + + # SORT HALVES + hb = bound // 2 + for i in range(num_lanes // 2): + l0 = lanes[i] + l1 = lanes[i + (num_lanes // 2)] + l0p = copy.deepcopy(l0[hb:]) + l0[hb:] = l1[0:hb] + l1[0:hb] = l0p + lanes[i] =l0 + lanes[i + (num_lanes // 2)] = l1 + print('\nsort halves') + print(lanes) + + # 'MELT' SHUFFLE INTERLEAVE! + melt_pos = np.arange(bound, dtype=int) + melt_pos = np.reshape(melt_pos, (2, -1)).T.flatten() + for i in range(num_lanes): + lanes[i] = lanes[i, melt_pos] + print('\nmelt lanes') + print(lanes) + + + + for i in range(0, m, bound): + print("\nlook at this part") + part = pos[i: i + bound] + rev = bit_reverse_vector(part, n) + sorted_rev = np.sort(rev) + print(part) + print(rev) + print(sorted_rev) + sorted_part = rev[shuffle_pos] + print(sorted_part) - print(np.arange(16)) - print bit_reverse_vector(np.arange(16), 4) - ntotal = 99 - for i in range(ntotal): - show_progress_bar(i, ntotal) - time.sleep(0.1) - - # sys.stdout.write('Hello') - # time.sleep(1) - # sys.stdout.write('\rMomy ') if __name__ == '__main__': main() diff --git a/gr-fec/python/fec/polar/testbed.py b/gr-fec/python/fec/polar/testbed.py index bdf9ae437c..c35b62099c 100755 --- a/gr-fec/python/fec/polar/testbed.py +++ b/gr-fec/python/fec/polar/testbed.py @@ -153,11 +153,11 @@ 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__': diff --git a/gr-fec/python/fec/qa_polar_decoder_sc.py b/gr-fec/python/fec/qa_polar_decoder_sc.py index 966a9f169a..1e7cd25e26 100644 --- a/gr-fec/python/fec/qa_polar_decoder_sc.py +++ b/gr-fec/python/fec/qa_polar_decoder_sc.py @@ -32,7 +32,7 @@ from extended_decoder import extended_decoder from polar.encoder import PolarEncoder from polar.decoder import PolarDecoder import polar.channel_construction as cc -# from polar.helper_functions import bit_reverse_vector +from polar.helper_functions import bit_reverse_vector # print('PID:', os.getpid()) # raw_input('tell me smth') @@ -62,22 +62,14 @@ class test_polar_decoder_sc(gr_unittest.TestCase): def test_002_one_vector(self): print "test_002_one_vector" is_packed = False - block_power = 8 + block_power = 10 block_size = 2 ** block_power num_info_bits = 2 ** (block_power - 1) num_frozen_bits = block_size - num_info_bits frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0) 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 + bits, gr_data = self.generate_test_data(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, 1, True) 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) @@ -90,16 +82,14 @@ class test_polar_decoder_sc(gr_unittest.TestCase): res = np.array(snk.data()).astype(dtype=int) - ref = python_decoder.decode(data) - - print("input:", data) + print("input:", gr_data.astype(dtype=int)) + print("ref :", bits) print("res :", res) - print("ref :", ref) - self.assertTupleEqual(tuple(res), tuple(ref)) + self.assertTupleEqual(tuple(res), tuple(bits)) def test_003_stream(self): - print "test_002_stream" + print "test_003_stream" nframes = 3 is_packed = False block_power = 8 @@ -108,23 +98,8 @@ class test_polar_decoder_sc(gr_unittest.TestCase): num_frozen_bits = block_size - num_info_bits frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0) 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 + bits, gr_data = self.generate_test_data(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, nframes, False) 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) @@ -137,14 +112,27 @@ class test_polar_decoder_sc(gr_unittest.TestCase): res = np.array(snk.data()).astype(dtype=int) - # ref = python_decoder.decode(data) - - print("input:", data) + print("input:", gr_data.astype(dtype=int)) + print("ref :", bits) print("res :", res) - # print("ref :", ref) self.assertTupleEqual(tuple(res), tuple(bits)) + def generate_test_data(self, block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, nframes, onlyones): + 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(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) diff --git a/gr-fec/python/fec/qa_polar_encoder.py b/gr-fec/python/fec/qa_polar_encoder.py index b4f26e4017..90190cd719 100644 --- a/gr-fec/python/fec/qa_polar_encoder.py +++ b/gr-fec/python/fec/qa_polar_encoder.py @@ -28,6 +28,10 @@ from extended_encoder import extended_encoder 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_encoder(gr_unittest.TestCase): @@ -50,54 +54,45 @@ class test_polar_encoder(gr_unittest.TestCase): self.assertFloatTuplesAlmostEqual((float(num_info_bits) / block_size, ), (polar_encoder.rate(), )) self.assertFalse(polar_encoder.set_frame_size(10)) - def test_002_work_function(self): - block_size = 256 - num_info_bits = 128 - num_frozen_bits = block_size - num_info_bits - frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0) - frozen_bit_values = np.array([0] * num_frozen_bits,) - python_encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values) - + def test_002_work_function_packed(self): is_packed = True - polar_encoder = fec.polar_encoder.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed) + block_size = 256 + num_info_bits = block_size // 2 - data = np.ones(num_info_bits, dtype=int) + data, ref, polar_encoder = self.get_test_data(block_size, num_info_bits, 1, is_packed) src = blocks.vector_source_b(data, False) enc_block = extended_encoder(polar_encoder, None, '11') snk = blocks.vector_sink_b(1) 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) - - print(res) - print(penc) - self.assertTupleEqual(tuple(res), tuple(penc)) + self.assertTupleEqual(tuple(res), tuple(ref)) - def test_003_big_input(self): - is_packed = True - num_blocks = 30 + def test_003_work_function_unpacked(self): + is_packed = False block_size = 256 - num_info_bits = 128 - num_frozen_bits = block_size - num_info_bits - frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0) - frozen_bit_values = np.array([0] * num_frozen_bits,) - python_encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values) + num_info_bits = block_size // 2 - polar_encoder = fec.polar_encoder.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed) + data, ref, polar_encoder = self.get_test_data(block_size, num_info_bits, 1, is_packed) + src = blocks.vector_source_b(data, False) + enc_block = extended_encoder(polar_encoder, None, '11') + snk = blocks.vector_sink_b(1) - data = np.array([], dtype=int) - ref = np.array([], dtype=int) + self.tb.connect(src, enc_block, snk) + self.tb.run() - for i in range(num_blocks): - d = np.random.randint(2, size=num_info_bits) - data = np.append(data, d) - ref = np.append(ref, python_encoder.encode(d)) + res = np.array(snk.data()).astype(dtype=int) + self.assertTupleEqual(tuple(res), tuple(ref)) + def test_004_big_input(self): + is_packed = False + num_blocks = 30 + block_size = 1024 + num_info_bits = block_size // 8 + data, ref, polar_encoder = self.get_test_data(block_size, num_info_bits, num_blocks, is_packed) src = blocks.vector_source_b(data, False) enc_block = extended_encoder(polar_encoder, None, '11') snk = blocks.vector_sink_b(1) @@ -111,6 +106,22 @@ class test_polar_encoder(gr_unittest.TestCase): print(ref) self.assertTupleEqual(tuple(res), tuple(ref)) + def get_test_data(self, block_size, num_info_bits, num_blocks, is_packed): + num_frozen_bits = block_size - num_info_bits + frozen_bit_positions = cc.frozen_bit_positions(block_size, num_info_bits, 0.0) + frozen_bit_values = np.array([0] * num_frozen_bits,) + python_encoder = PolarEncoder(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values) + + data = np.array([], dtype=int) + ref = np.array([], dtype=int) + for i in range(num_blocks): + d = np.random.randint(2, size=num_info_bits) + data = np.append(data, d) + ref = np.append(ref, python_encoder.encode(d)) + polar_encoder = fec.polar_encoder.make(block_size, num_info_bits, frozen_bit_positions, frozen_bit_values, is_packed) + return data, ref, polar_encoder + + |