summaryrefslogtreecommitdiff
path: root/viterbi-detector
diff options
context:
space:
mode:
Diffstat (limited to 'viterbi-detector')
-rw-r--r--viterbi-detector/test.cpp717
-rw-r--r--viterbi-detector/viterbi_detector_lh4.cpp552
2 files changed, 1269 insertions, 0 deletions
diff --git a/viterbi-detector/test.cpp b/viterbi-detector/test.cpp
new file mode 100644
index 0000000..7a1775b
--- /dev/null
+++ b/viterbi-detector/test.cpp
@@ -0,0 +1,717 @@
+#include <stdio.h>
+/*
+** viterbi_detector:
+** This part does the detection of received sequnece.
+** Employed algorithm is viterbi Maximum Likehood Sequence Estimation.
+** At this moment it gives hard decisions on the output, but
+** it was designed with soft decisions in mind.
+**
+** SYNTAX: void viterbi_detector(
+** const gr_complex * input,
+** unsigned int samples_num,
+** gr_complex * rhh,
+** unsigned int start_state,
+** const unsigned int * stop_states,
+** unsigned int stops_num,
+** float * output)
+**
+** INPUT: input: Complex received signal afted matched filtering.
+** samples_num: Number of samples in the input table.
+** rhh: The autocorrelation of the estimated channel
+** impulse response.
+** start_state: Number of the start point. In GSM each burst
+** starts with sequence of three bits (0,0,0) which
+** indicates start point of the algorithm.
+** stop_states: Table with numbers of possible stop states.
+** stops_num: Number of possible stop states
+**
+**
+** OUTPUT: output: Differentially decoded hard output of the algorithm:
+** -1 for logical "0" and 1 for logical "1"
+**
+** SUB_FUNC: none
+**
+** TEST(S): Tested with real world normal burst.
+*/
+
+#include <gnuradio/gr_complex.h>
+#define BURST_SIZE 148
+#define PATHS_NUM 16
+
+void viterbi_detector(const gr_complex * input, unsigned int samples_num, gr_complex * rhh, unsigned int start_state, const unsigned int * stop_states, unsigned int stops_num, float * output)
+{
+ float increment[8];
+ float path_metrics1[16];
+ float path_metrics2[16];
+ float * new_path_metrics;
+ float * old_path_metrics;
+ float * tmp;
+ float trans_table[BURST_SIZE][16];
+ float pm_candidate1, pm_candidate2;
+ bool real_imag;
+ float input_symbol_real, input_symbol_imag;
+ unsigned int i, sample_nr;
+
+/*
+* Setup first path metrics, so only state pointed by start_state is possible.
+* Start_state metric is equal to zero, the rest is written with some very low value,
+* which makes them practically impossible to occur.
+*/
+ for(i=0; i<PATHS_NUM; i++){
+ path_metrics1[i]=(-10e30);
+ }
+ path_metrics1[start_state]=0;
+
+/*
+* Compute Increment - a table of values which does not change for subsequent input samples.
+* Increment is table of reference levels for computation of branch metrics:
+* branch metric = (+/-)received_sample (+/-) reference_level
+*/
+ increment[0] = -rhh[1].imag() -rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[1] = rhh[1].imag() -rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[2] = -rhh[1].imag() +rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[3] = rhh[1].imag() +rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[4] = -rhh[1].imag() -rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[5] = rhh[1].imag() -rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[6] = -rhh[1].imag() +rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[7] = rhh[1].imag() +rhh[2].real() +rhh[3].imag() +rhh[4].real();
+
+
+/*
+* Computation of path metrics and decisions (Add-Compare-Select).
+* It's composed of two parts: one for odd input samples (imaginary numbers)
+* and one for even samples (real numbers).
+* Each part is composed of independent (parallelisable) statements like
+* this one:
+* pm_candidate1 = old_path_metrics[0] - input_symbol_real - increment[7];
+* pm_candidate2 = old_path_metrics[8] - input_symbol_real + increment[0];
+* if(pm_candidate1 > pm_candidate2){
+* new_path_metrics[0] = pm_candidate1;
+* trans_table[sample_nr][0] = -1.0;
+* }
+* else{
+* new_path_metrics[0] = pm_candidate2;
+* trans_table[sample_nr][0] = 1.0;
+* }
+* This is very good point for optimisations (SIMD or OpenMP) as it's most time
+* consuming part of this function.
+*/
+ printf("# name: path_metrics_test_result\n# type: matrix\n# rows: 148\n# columns: 16\n");
+ sample_nr=0;
+ old_path_metrics=path_metrics1;
+ new_path_metrics=path_metrics2;
+ while(sample_nr<samples_num){
+ //Processing imag states
+ real_imag=1;
+ input_symbol_imag = input[sample_nr].imag();
+
+ pm_candidate1 = old_path_metrics[0] + input_symbol_imag - increment[2];
+ pm_candidate2 = old_path_metrics[8] + input_symbol_imag + increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[0] = pm_candidate1;
+ trans_table[sample_nr][0] = -1.0;
+ }
+ else{
+ new_path_metrics[0] = pm_candidate2;
+ trans_table[sample_nr][0] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[0] - input_symbol_imag + increment[2];
+ pm_candidate2 = old_path_metrics[8] - input_symbol_imag - increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[1] = pm_candidate1;
+ trans_table[sample_nr][1] = -1.0;
+ }
+ else{
+ new_path_metrics[1] = pm_candidate2;
+ trans_table[sample_nr][1] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] + input_symbol_imag - increment[3];
+ pm_candidate2 = old_path_metrics[9] + input_symbol_imag + increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[2] = pm_candidate1;
+ trans_table[sample_nr][2] = -1.0;
+ }
+ else{
+ new_path_metrics[2] = pm_candidate2;
+ trans_table[sample_nr][2] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] - input_symbol_imag + increment[3];
+ pm_candidate2 = old_path_metrics[9] - input_symbol_imag - increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[3] = pm_candidate1;
+ trans_table[sample_nr][3] = -1.0;
+ }
+ else{
+ new_path_metrics[3] = pm_candidate2;
+ trans_table[sample_nr][3] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] + input_symbol_imag - increment[0];
+ pm_candidate2 = old_path_metrics[10] + input_symbol_imag + increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[4] = pm_candidate1;
+ trans_table[sample_nr][4] = -1.0;
+ }
+ else{
+ new_path_metrics[4] = pm_candidate2;
+ trans_table[sample_nr][4] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] - input_symbol_imag + increment[0];
+ pm_candidate2 = old_path_metrics[10] - input_symbol_imag - increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[5] = pm_candidate1;
+ trans_table[sample_nr][5] = -1.0;
+ }
+ else{
+ new_path_metrics[5] = pm_candidate2;
+ trans_table[sample_nr][5] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] + input_symbol_imag - increment[1];
+ pm_candidate2 = old_path_metrics[11] + input_symbol_imag + increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[6] = pm_candidate1;
+ trans_table[sample_nr][6] = -1.0;
+ }
+ else{
+ new_path_metrics[6] = pm_candidate2;
+ trans_table[sample_nr][6] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] - input_symbol_imag + increment[1];
+ pm_candidate2 = old_path_metrics[11] - input_symbol_imag - increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[7] = pm_candidate1;
+ trans_table[sample_nr][7] = -1.0;
+ }
+ else{
+ new_path_metrics[7] = pm_candidate2;
+ trans_table[sample_nr][7] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] + input_symbol_imag - increment[6];
+ pm_candidate2 = old_path_metrics[12] + input_symbol_imag + increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[8] = pm_candidate1;
+ trans_table[sample_nr][8] = -1.0;
+ }
+ else{
+ new_path_metrics[8] = pm_candidate2;
+ trans_table[sample_nr][8] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] - input_symbol_imag + increment[6];
+ pm_candidate2 = old_path_metrics[12] - input_symbol_imag - increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[9] = pm_candidate1;
+ trans_table[sample_nr][9] = -1.0;
+ }
+ else{
+ new_path_metrics[9] = pm_candidate2;
+ trans_table[sample_nr][9] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] + input_symbol_imag - increment[7];
+ pm_candidate2 = old_path_metrics[13] + input_symbol_imag + increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[10] = pm_candidate1;
+ trans_table[sample_nr][10] = -1.0;
+ }
+ else{
+ new_path_metrics[10] = pm_candidate2;
+ trans_table[sample_nr][10] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] - input_symbol_imag + increment[7];
+ pm_candidate2 = old_path_metrics[13] - input_symbol_imag - increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[11] = pm_candidate1;
+ trans_table[sample_nr][11] = -1.0;
+ }
+ else{
+ new_path_metrics[11] = pm_candidate2;
+ trans_table[sample_nr][11] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] + input_symbol_imag - increment[4];
+ pm_candidate2 = old_path_metrics[14] + input_symbol_imag + increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[12] = pm_candidate1;
+ trans_table[sample_nr][12] = -1.0;
+ }
+ else{
+ new_path_metrics[12] = pm_candidate2;
+ trans_table[sample_nr][12] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] - input_symbol_imag + increment[4];
+ pm_candidate2 = old_path_metrics[14] - input_symbol_imag - increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[13] = pm_candidate1;
+ trans_table[sample_nr][13] = -1.0;
+ }
+ else{
+ new_path_metrics[13] = pm_candidate2;
+ trans_table[sample_nr][13] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] + input_symbol_imag - increment[5];
+ pm_candidate2 = old_path_metrics[15] + input_symbol_imag + increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[14] = pm_candidate1;
+ trans_table[sample_nr][14] = -1.0;
+ }
+ else{
+ new_path_metrics[14] = pm_candidate2;
+ trans_table[sample_nr][14] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] - input_symbol_imag + increment[5];
+ pm_candidate2 = old_path_metrics[15] - input_symbol_imag - increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[15] = pm_candidate1;
+ trans_table[sample_nr][15] = -1.0;
+ }
+ else{
+ new_path_metrics[15] = pm_candidate2;
+ trans_table[sample_nr][15] = 1.0;
+ }
+
+ for(i=0; i<16; i++){
+ printf(" %0.6f", new_path_metrics[i]);
+ }
+ printf("\n");
+
+ tmp=old_path_metrics;
+ old_path_metrics=new_path_metrics;
+ new_path_metrics=tmp;
+
+ sample_nr++;
+ if(sample_nr==samples_num)
+ break;
+
+ //Processing real states
+ real_imag=0;
+ input_symbol_real = input[sample_nr].real();
+
+ pm_candidate1 = old_path_metrics[0] - input_symbol_real - increment[7];
+ pm_candidate2 = old_path_metrics[8] - input_symbol_real + increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[0] = pm_candidate1;
+ trans_table[sample_nr][0] = -1.0;
+ }
+ else{
+ new_path_metrics[0] = pm_candidate2;
+ trans_table[sample_nr][0] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[0] + input_symbol_real + increment[7];
+ pm_candidate2 = old_path_metrics[8] + input_symbol_real - increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[1] = pm_candidate1;
+ trans_table[sample_nr][1] = -1.0;
+ }
+ else{
+ new_path_metrics[1] = pm_candidate2;
+ trans_table[sample_nr][1] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] - input_symbol_real - increment[6];
+ pm_candidate2 = old_path_metrics[9] - input_symbol_real + increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[2] = pm_candidate1;
+ trans_table[sample_nr][2] = -1.0;
+ }
+ else{
+ new_path_metrics[2] = pm_candidate2;
+ trans_table[sample_nr][2] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] + input_symbol_real + increment[6];
+ pm_candidate2 = old_path_metrics[9] + input_symbol_real - increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[3] = pm_candidate1;
+ trans_table[sample_nr][3] = -1.0;
+ }
+ else{
+ new_path_metrics[3] = pm_candidate2;
+ trans_table[sample_nr][3] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] - input_symbol_real - increment[5];
+ pm_candidate2 = old_path_metrics[10] - input_symbol_real + increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[4] = pm_candidate1;
+ trans_table[sample_nr][4] = -1.0;
+ }
+ else{
+ new_path_metrics[4] = pm_candidate2;
+ trans_table[sample_nr][4] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] + input_symbol_real + increment[5];
+ pm_candidate2 = old_path_metrics[10] + input_symbol_real - increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[5] = pm_candidate1;
+ trans_table[sample_nr][5] = -1.0;
+ }
+ else{
+ new_path_metrics[5] = pm_candidate2;
+ trans_table[sample_nr][5] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] - input_symbol_real - increment[4];
+ pm_candidate2 = old_path_metrics[11] - input_symbol_real + increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[6] = pm_candidate1;
+ trans_table[sample_nr][6] = -1.0;
+ }
+ else{
+ new_path_metrics[6] = pm_candidate2;
+ trans_table[sample_nr][6] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] + input_symbol_real + increment[4];
+ pm_candidate2 = old_path_metrics[11] + input_symbol_real - increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[7] = pm_candidate1;
+ trans_table[sample_nr][7] = -1.0;
+ }
+ else{
+ new_path_metrics[7] = pm_candidate2;
+ trans_table[sample_nr][7] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] - input_symbol_real - increment[3];
+ pm_candidate2 = old_path_metrics[12] - input_symbol_real + increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[8] = pm_candidate1;
+ trans_table[sample_nr][8] = -1.0;
+ }
+ else{
+ new_path_metrics[8] = pm_candidate2;
+ trans_table[sample_nr][8] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] + input_symbol_real + increment[3];
+ pm_candidate2 = old_path_metrics[12] + input_symbol_real - increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[9] = pm_candidate1;
+ trans_table[sample_nr][9] = -1.0;
+ }
+ else{
+ new_path_metrics[9] = pm_candidate2;
+ trans_table[sample_nr][9] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] - input_symbol_real - increment[2];
+ pm_candidate2 = old_path_metrics[13] - input_symbol_real + increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[10] = pm_candidate1;
+ trans_table[sample_nr][10] = -1.0;
+ }
+ else{
+ new_path_metrics[10] = pm_candidate2;
+ trans_table[sample_nr][10] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] + input_symbol_real + increment[2];
+ pm_candidate2 = old_path_metrics[13] + input_symbol_real - increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[11] = pm_candidate1;
+ trans_table[sample_nr][11] = -1.0;
+ }
+ else{
+ new_path_metrics[11] = pm_candidate2;
+ trans_table[sample_nr][11] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] - input_symbol_real - increment[1];
+ pm_candidate2 = old_path_metrics[14] - input_symbol_real + increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[12] = pm_candidate1;
+ trans_table[sample_nr][12] = -1.0;
+ }
+ else{
+ new_path_metrics[12] = pm_candidate2;
+ trans_table[sample_nr][12] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] + input_symbol_real + increment[1];
+ pm_candidate2 = old_path_metrics[14] + input_symbol_real - increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[13] = pm_candidate1;
+ trans_table[sample_nr][13] = -1.0;
+ }
+ else{
+ new_path_metrics[13] = pm_candidate2;
+ trans_table[sample_nr][13] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] - input_symbol_real - increment[0];
+ pm_candidate2 = old_path_metrics[15] - input_symbol_real + increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[14] = pm_candidate1;
+ trans_table[sample_nr][14] = -1.0;
+ }
+ else{
+ new_path_metrics[14] = pm_candidate2;
+ trans_table[sample_nr][14] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] + input_symbol_real + increment[0];
+ pm_candidate2 = old_path_metrics[15] + input_symbol_real - increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[15] = pm_candidate1;
+ trans_table[sample_nr][15] = -1.0;
+ }
+ else{
+ new_path_metrics[15] = pm_candidate2;
+ trans_table[sample_nr][15] = 1.0;
+ }
+
+ for(i=0; i<16; i++){
+ printf(" %0.6f", new_path_metrics[i]);
+ }
+ printf("\n");
+
+ tmp=old_path_metrics;
+ old_path_metrics=new_path_metrics;
+ new_path_metrics=tmp;
+
+ sample_nr++;
+ }
+
+/*
+* Find the best from the stop states by comparing their path metrics.
+* Not every stop state is always possible, so we are searching in
+* a subset of them.
+*/
+ unsigned int best_stop_state;
+ float stop_state_metric, max_stop_state_metric;
+ best_stop_state = stop_states[0];
+ max_stop_state_metric = old_path_metrics[best_stop_state];
+ for(i=1; i< stops_num; i++){
+ stop_state_metric = old_path_metrics[stop_states[i]];
+ if(stop_state_metric > max_stop_state_metric){
+ max_stop_state_metric = stop_state_metric;
+ best_stop_state = stop_states[i];
+ }
+ }
+
+/*
+* This table was generated with hope that it gives a litle speedup during
+* traceback stage.
+* Received bit is related to the number of state in the trellis.
+* I've numbered states so their parity (number of ones) is related
+* to a received bit.
+*/
+ static const unsigned int parity_table[PATHS_NUM] = { 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, };
+
+/*
+* Table of previous states in the trellis diagram.
+* For GMSK modulation every state has two previous states.
+* Example:
+* previous_state_nr1 = prev_table[current_state_nr][0]
+* previous_state_nr2 = prev_table[current_state_nr][1]
+*/
+ static const unsigned int prev_table[PATHS_NUM][2] = { {0,8}, {0,8}, {1,9}, {1,9}, {2,10}, {2,10}, {3,11}, {3,11}, {4,12}, {4,12}, {5,13}, {5,13}, {6,14}, {6,14}, {7,15}, {7,15}, };
+
+/*
+* Traceback and differential decoding of received sequence.
+* Decisions stored in trans_table are used to restore best path in the trellis.
+*/
+ sample_nr=samples_num;
+ unsigned int state_nr=best_stop_state;
+ unsigned int decision;
+ bool out_bit=0;
+
+ while(sample_nr>0){
+ sample_nr--;
+ decision = (trans_table[sample_nr][state_nr]>0);
+
+ if(decision != out_bit)
+ output[sample_nr]=-trans_table[sample_nr][state_nr];
+ else
+ output[sample_nr]=trans_table[sample_nr][state_nr];
+
+ out_bit = out_bit ^ real_imag ^ parity_table[state_nr];
+ state_nr = prev_table[state_nr][decision];
+ real_imag = !real_imag;
+ }
+}
+int main()
+{
+ gr_complex rhh[5];
+ gr_complex input[BURST_SIZE];
+ float output[BURST_SIZE];
+ float path_metrics[16];
+ unsigned int i;
+
+ rhh[0] = gr_complex(6681134.2347451737,0.0000000000);
+ rhh[1] = gr_complex(4315167.0637422213,-860367.8252039659);
+ rhh[2] = gr_complex(935284.8973972955,-371780.5098627206);
+ rhh[3] = gr_complex(-51462.6871850645,50393.6755332753);
+ rhh[4] = gr_complex(-7439.8044847587,8028.1598971039);
+ input[0] = gr_complex(7977179.5758423340,-2764222.4174382309);
+ input[1] = gr_complex(6856794.8374158992,4865869.9717015224);
+ input[2] = gr_complex(9811374.7624817826,5183732.8837238941);
+ input[3] = gr_complex(6679440.9549223864,-4428971.3826953433);
+ input[4] = gr_complex(-4696701.8298753574,-5933567.0446173064);
+ input[5] = gr_complex(-6541783.9135319907,4653341.9806263465);
+ input[6] = gr_complex(2084689.1360897610,10178136.3338905703);
+ input[7] = gr_complex(6147479.6545689385,8874496.3001975510);
+ input[8] = gr_complex(5904918.0852984637,8800690.9255027324);
+ input[9] = gr_complex(6748883.3597641187,8777701.9989523701);
+ input[10] = gr_complex(6778221.8454960939,8045655.9501006966);
+ input[11] = gr_complex(6364128.8660152592,8022191.0277904849);
+ input[12] = gr_complex(8722069.2811547928,4776436.4937707158);
+ input[13] = gr_complex(10932320.6634155307,-1558217.3467115229);
+ input[14] = gr_complex(8712591.8296174519,-1858753.9812126879);
+ input[15] = gr_complex(2379782.5548789091,2932506.6217711852);
+ input[16] = gr_complex(-5444416.7791099474,5946987.8123247186);
+ input[17] = gr_complex(-5424576.3013667949,8041132.5497372206);
+ input[18] = gr_complex(4060723.5737396451,5559136.6484692302);
+ input[19] = gr_complex(9867910.7169802599,-1816506.5368241861);
+ input[20] = gr_complex(9116570.9774469398,-6509021.2122100489);
+ input[21] = gr_complex(5005755.5616738033,-8815847.5133575164);
+ input[22] = gr_complex(-2234914.8963576080,-10346435.2929649707);
+ input[23] = gr_complex(-7202255.9594532764,-9713796.9845253937);
+ input[24] = gr_complex(-9190470.4906416610,-4700539.2048025727);
+ input[25] = gr_complex(-10344677.5631833095,3164735.0763911339);
+ input[26] = gr_complex(-8144676.0358214928,3689244.8448072611);
+ input[27] = gr_complex(-2187512.8785404381,-2405086.8007661770);
+ input[28] = gr_complex(4192422.7355999672,-2302450.1948127761);
+ input[29] = gr_complex(7246362.6484694732,4298058.7434391864);
+ input[30] = gr_complex(6556902.8967612814,8229181.3319309540);
+ input[31] = gr_complex(6142925.0144970221,8026586.9547691522);
+ input[32] = gr_complex(8129663.3146255473,4033126.4267871310);
+ input[33] = gr_complex(5840297.4751724107,-4620492.6748427916);
+ input[34] = gr_complex(-1914675.1103647740,-10020347.7468968201);
+ input[35] = gr_complex(-2940115.4495635680,-8372239.2818623800);
+ input[36] = gr_complex(4008522.1739267618,-6826920.4027512996);
+ input[37] = gr_complex(8135500.9140075976,-7047328.2304275325);
+ input[38] = gr_complex(8405763.8657652065,-6931698.9773707138);
+ input[39] = gr_complex(8929684.6084167603,-6179537.9078161716);
+ input[40] = gr_complex(8180060.2347036134,-2186703.0895569432);
+ input[41] = gr_complex(3091335.4318671110,4054954.8339853790);
+ input[42] = gr_complex(-4295697.1578283813,7927174.1333465036);
+ input[43] = gr_complex(-8473978.8917866647,8708279.0942377765);
+ input[44] = gr_complex(-8307511.0194505267,8912587.7116757408);
+ input[45] = gr_complex(-3924398.3662469061,9788935.7640386801);
+ input[46] = gr_complex(3578818.1363314060,9475507.7755236719);
+ input[47] = gr_complex(7878887.0608754344,8305521.6216092538);
+ input[48] = gr_complex(7661073.4441334298,8193166.0088053150);
+ input[49] = gr_complex(7711201.6565008871,8476321.8633535057);
+ input[50] = gr_complex(8106392.3937723571,8574168.6601282097);
+ input[51] = gr_complex(4338938.6736003347,8161180.2535219444);
+ input[52] = gr_complex(-2892764.5596533259,7908598.1890047276);
+ input[53] = gr_complex(-7361426.2291188771,8354406.9966570400);
+ input[54] = gr_complex(-7399748.1998513071,9027400.1381105371);
+ input[55] = gr_complex(-2985443.1269021751,10343848.6311076693);
+ input[56] = gr_complex(4056164.2682814910,10098505.0940024592);
+ input[57] = gr_complex(3662304.4839048819,7612823.1212739553);
+ input[58] = gr_complex(-3973366.8165788800,7937078.9175711880);
+ input[59] = gr_complex(-4235798.1452934938,10334281.0868006106);
+ input[60] = gr_complex(3036808.0689534992,9898067.6488185041);
+ input[61] = gr_complex(7473543.5356334411,7807926.3775777007);
+ input[62] = gr_complex(9079322.0398128927,3406424.4956655651);
+ input[63] = gr_complex(9858644.6258316785,-3257437.0358347511);
+ input[64] = gr_complex(8880394.8906779401,-7679278.0091405679);
+ input[65] = gr_complex(3363837.0022190632,-9429173.7162515502);
+ input[66] = gr_complex(-5976744.0335793961,-5385450.6034509651);
+ input[67] = gr_complex(-9557981.0088688023,3050312.8082751348);
+ input[68] = gr_complex(-7022882.0701328497,3640309.4189949362);
+ input[69] = gr_complex(-6956342.7005542396,-3448204.4347535190);
+ input[70] = gr_complex(-7352343.4183843154,-7661573.7851171279);
+ input[71] = gr_complex(-2991151.1712345490,-7200411.9186981265);
+ input[72] = gr_complex(2885118.0445274930,-2984883.7704812000);
+ input[73] = gr_complex(7032828.1064425148,3581754.7941750460);
+ input[74] = gr_complex(10088763.7540586796,3662867.8467899580);
+ input[75] = gr_complex(10564181.4445688296,-3225930.1012457302);
+ input[76] = gr_complex(8350222.2591632884,-3732983.7871769890);
+ input[77] = gr_complex(7833973.7142023239,2987993.6910825032);
+ input[78] = gr_complex(9706408.6739433222,3052094.8092914429);
+ input[79] = gr_complex(9745006.6094854400,-3935102.0540104648);
+ input[80] = gr_complex(7816404.5637982106,-8252538.7267344501);
+ input[81] = gr_complex(2986277.6633892348,-9487975.5299777929);
+ input[82] = gr_complex(-5695845.6292771958,-5169515.8120368905);
+ input[83] = gr_complex(-10054151.1938444097,3411496.4582903101);
+ input[84] = gr_complex(-8051379.2657383084,2941255.2196879322);
+ input[85] = gr_complex(-3549464.5857489500,-3756761.7516137050);
+ input[86] = gr_complex(2758228.0974008231,-3356159.6927887732);
+ input[87] = gr_complex(3030904.7997136060,2423714.1793336859);
+ input[88] = gr_complex(-4312484.6648249906,6565622.5327912308);
+ input[89] = gr_complex(-8292628.1023570709,7907719.3416422373);
+ input[90] = gr_complex(-7526932.9695930025,8014555.7987554707);
+ input[91] = gr_complex(-7845877.0589824449,7739528.8884838661);
+ input[92] = gr_complex(-8621562.5281414296,7418568.3737750174);
+ input[93] = gr_complex(-8417158.0598517433,7181224.2163500283);
+ input[94] = gr_complex(-8512688.8578708004,7987622.6814399734);
+ input[95] = gr_complex(-4394195.2836061195,9949034.4722546078);
+ input[96] = gr_complex(5266129.2915991358,6195329.6856880505);
+ input[97] = gr_complex(10194253.6950446907,-2784736.7088111811);
+ input[98] = gr_complex(8824963.8092368357,-7786593.4880886609);
+ input[99] = gr_complex(3396738.8080786392,-9691138.5840958729);
+ input[100] = gr_complex(-5722550.5051566781,-5556953.7173151653);
+ input[101] = gr_complex(-5714701.2187169204,5472711.9084113399);
+ input[102] = gr_complex(3332017.2621497451,9704527.7971289307);
+ input[103] = gr_complex(7342514.5288135549,7753950.5122191338);
+ input[104] = gr_complex(6818048.9879954616,8189460.3032278512);
+ input[105] = gr_complex(3394201.9642735380,7945062.7654534997);
+ input[106] = gr_complex(-4167885.5119835120,6895554.1659005154);
+ input[107] = gr_complex(-8619065.5479442235,6801211.7162556173);
+ input[108] = gr_complex(-7427938.6338890027,2908143.9905314222);
+ input[109] = gr_complex(-6703266.9973377967,-4149571.8933691182);
+ input[110] = gr_complex(-7397979.4083190663,-8091927.8271739502);
+ input[111] = gr_complex(-8023643.3861837359,-8148580.2711619306);
+ input[112] = gr_complex(-9593984.7424030975,-3401373.7567658830);
+ input[113] = gr_complex(-9949905.4782167133,3693487.8505923129);
+ input[114] = gr_complex(-7643884.0559280366,3256209.4725131588);
+ input[115] = gr_complex(-2697566.6721224338,-3206105.0871117339);
+ input[116] = gr_complex(3377896.5469162161,-3637995.9373872238);
+ input[117] = gr_complex(7053276.0410971297,2764169.1462154472);
+ input[118] = gr_complex(8628643.1609179415,3396969.9720182270);
+ input[119] = gr_complex(8591483.6933623832,-3571890.2316942490);
+ input[120] = gr_complex(7631932.3620410990,-7892583.3345261374);
+ input[121] = gr_complex(3523270.0499849520,-9235294.6299457569);
+ input[122] = gr_complex(-5210049.1886767643,-5470018.0261554671);
+ input[123] = gr_complex(-5729032.9836538611,4597120.7055899110);
+ input[124] = gr_complex(4722045.6474561440,5593554.0462966477);
+ input[125] = gr_complex(9943005.2302960120,-3058974.8321727011);
+ input[126] = gr_complex(7338276.2722858489,-3095524.7280114950);
+ input[127] = gr_complex(6924101.7894357592,4679671.4725222811);
+ input[128] = gr_complex(9394305.4008450378,4311128.9848157102);
+ input[129] = gr_complex(9835558.7182324342,-3667900.0077023208);
+ input[130] = gr_complex(8223108.7120001484,-8579057.2975662407);
+ input[131] = gr_complex(2845955.6588687100,-9157587.9910129588);
+ input[132] = gr_complex(-5965686.3459505001,-4635464.3736052224);
+ input[133] = gr_complex(-9515672.9792508632,3206974.9185256958);
+ input[134] = gr_complex(-8344649.1418864401,7073463.4248667136);
+ input[135] = gr_complex(-8254731.1990081621,7048210.7404652704);
+ input[136] = gr_complex(-7504645.1065991390,3469527.9779098351);
+ input[137] = gr_complex(-6905884.6544481078,-4071500.7763075172);
+ input[138] = gr_complex(-7265828.0211983416,-8724546.7090917714);
+ input[139] = gr_complex(-3159001.5446096850,-7599002.0958460663);
+ input[140] = gr_complex(4820872.7249604221,-7688968.4836491412);
+ input[141] = gr_complex(4538964.4842799734,-10655536.8874594998);
+ input[142] = gr_complex(-4627802.4763165191,-6342339.7226147177);
+ input[143] = gr_complex(-5229789.9845531741,4793436.5098953182);
+ input[144] = gr_complex(3023641.9008085518,9426626.5553139690);
+ input[145] = gr_complex(3151170.4858403988,7510483.1565964483);
+ input[146] = gr_complex(-3112381.9596595298,6480539.7998312227);
+ input[147] = gr_complex(-3526072.3028905988,4305425.6301188134);
+ unsigned int stop_states[1] = { 4, };
+
+ viterbi_detector(input, BURST_SIZE, rhh, 3, stop_states, 1, output);
+ printf("# name: output\n# type: matrix\n# rows: 1\n# columns: 148\n");
+ for(i=0; i<BURST_SIZE ; i++){
+ printf(" %d\n", output[i]>0);
+ }
+ printf("\n");
+
+}
diff --git a/viterbi-detector/viterbi_detector_lh4.cpp b/viterbi-detector/viterbi_detector_lh4.cpp
new file mode 100644
index 0000000..45da39d
--- /dev/null
+++ b/viterbi-detector/viterbi_detector_lh4.cpp
@@ -0,0 +1,552 @@
+/***************************************************************************
+ * Copyright (C) 2008 by Piotr Krysik *
+ * pkrysik@stud.pw.edu.pl *
+ * *
+ * This program 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 2 of the License, or *
+ * (at your option) any later version. *
+ * *
+ * This program 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 this program; if not, write to the *
+ * Free Software Foundation, Inc., *
+ * 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. *
+ ***************************************************************************/
+
+/*
+** viterbi_detector:
+** This part does the detection of received sequnece.
+** Employed algorithm is viterbi Maximum Likehood Sequence Estimation.
+** At this moment it gives hard decisions on the output, but
+** it was designed with soft decisions in mind.
+**
+** SYNTAX: void viterbi_detector(
+** const gr_complex * input,
+** unsigned int samples_num,
+** gr_complex * rhh,
+** unsigned int start_state,
+** const unsigned int * stop_states,
+** unsigned int stops_num,
+** float * output)
+**
+** INPUT: input: Complex received signal afted matched filtering.
+** samples_num: Number of samples in the input table.
+** rhh: The autocorrelation of the estimated channel
+** impulse response.
+** start_state: Number of the start point. In GSM each burst
+** starts with sequence of three bits (0,0,0) which
+** indicates start point of the algorithm.
+** stop_states: Table with numbers of possible stop states.
+** stops_num: Number of possible stop states
+**
+**
+** OUTPUT: output: Differentially decoded hard output of the algorithm:
+** -1 for logical "0" and 1 for logical "1"
+**
+** SUB_FUNC: none
+**
+** TEST(S): Tested with real world normal burst.
+*/
+
+#include <gnuradio/gr_complex.h>
+#define BURST_SIZE 148
+#define PATHS_NUM 16
+
+void viterbi_detector(const gr_complex * input, unsigned int samples_num, gr_complex * rhh, unsigned int start_state, const unsigned int * stop_states, unsigned int stops_num, float * output)
+{
+ float increment[8];
+ float path_metrics1[16];
+ float path_metrics2[16];
+ float * new_path_metrics;
+ float * old_path_metrics;
+ float * tmp;
+ float trans_table[BURST_SIZE][16];
+ float pm_candidate1, pm_candidate2;
+ bool real_imag;
+ float input_symbol_real, input_symbol_imag;
+ unsigned int i, sample_nr;
+
+/*
+* Setup first path metrics, so only state pointed by start_state is possible.
+* Start_state metric is equal to zero, the rest is written with some very low value,
+* which makes them practically impossible to occur.
+*/
+ for(i=0; i<PATHS_NUM; i++){
+ path_metrics1[i]=(-10e30);
+ }
+ path_metrics1[start_state]=0;
+
+/*
+* Compute Increment - a table of values which does not change for subsequent input samples.
+* Increment is table of reference levels for computation of branch metrics:
+* branch metric = (+/-)received_sample (+/-) reference_level
+*/
+ increment[0] = -rhh[1].imag() -rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[1] = rhh[1].imag() -rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[2] = -rhh[1].imag() +rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[3] = rhh[1].imag() +rhh[2].real() -rhh[3].imag() +rhh[4].real();
+ increment[4] = -rhh[1].imag() -rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[5] = rhh[1].imag() -rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[6] = -rhh[1].imag() +rhh[2].real() +rhh[3].imag() +rhh[4].real();
+ increment[7] = rhh[1].imag() +rhh[2].real() +rhh[3].imag() +rhh[4].real();
+
+
+/*
+* Computation of path metrics and decisions (Add-Compare-Select).
+* It's composed of two parts: one for odd input samples (imaginary numbers)
+* and one for even samples (real numbers).
+* Each part is composed of independent (parallelisable) statements like
+* this one:
+* pm_candidate1 = old_path_metrics[0] - input_symbol_real - increment[7];
+* pm_candidate2 = old_path_metrics[8] - input_symbol_real + increment[0];
+* if(pm_candidate1 > pm_candidate2){
+* new_path_metrics[0] = pm_candidate1;
+* trans_table[sample_nr][0] = -1.0;
+* }
+* else{
+* new_path_metrics[0] = pm_candidate2;
+* trans_table[sample_nr][0] = 1.0;
+* }
+* This is very good point for optimisations (SIMD or OpenMP) as it's most time
+* consuming part of this function.
+*/
+ sample_nr=0;
+ old_path_metrics=path_metrics1;
+ new_path_metrics=path_metrics2;
+ while(sample_nr<samples_num){
+ //Processing imag states
+ real_imag=1;
+ input_symbol_imag = input[sample_nr].imag();
+
+ pm_candidate1 = old_path_metrics[0] + input_symbol_imag - increment[2];
+ pm_candidate2 = old_path_metrics[8] + input_symbol_imag + increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[0] = pm_candidate1;
+ trans_table[sample_nr][0] = -1.0;
+ }
+ else{
+ new_path_metrics[0] = pm_candidate2;
+ trans_table[sample_nr][0] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[0] - input_symbol_imag + increment[2];
+ pm_candidate2 = old_path_metrics[8] - input_symbol_imag - increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[1] = pm_candidate1;
+ trans_table[sample_nr][1] = -1.0;
+ }
+ else{
+ new_path_metrics[1] = pm_candidate2;
+ trans_table[sample_nr][1] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] + input_symbol_imag - increment[3];
+ pm_candidate2 = old_path_metrics[9] + input_symbol_imag + increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[2] = pm_candidate1;
+ trans_table[sample_nr][2] = -1.0;
+ }
+ else{
+ new_path_metrics[2] = pm_candidate2;
+ trans_table[sample_nr][2] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] - input_symbol_imag + increment[3];
+ pm_candidate2 = old_path_metrics[9] - input_symbol_imag - increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[3] = pm_candidate1;
+ trans_table[sample_nr][3] = -1.0;
+ }
+ else{
+ new_path_metrics[3] = pm_candidate2;
+ trans_table[sample_nr][3] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] + input_symbol_imag - increment[0];
+ pm_candidate2 = old_path_metrics[10] + input_symbol_imag + increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[4] = pm_candidate1;
+ trans_table[sample_nr][4] = -1.0;
+ }
+ else{
+ new_path_metrics[4] = pm_candidate2;
+ trans_table[sample_nr][4] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] - input_symbol_imag + increment[0];
+ pm_candidate2 = old_path_metrics[10] - input_symbol_imag - increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[5] = pm_candidate1;
+ trans_table[sample_nr][5] = -1.0;
+ }
+ else{
+ new_path_metrics[5] = pm_candidate2;
+ trans_table[sample_nr][5] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] + input_symbol_imag - increment[1];
+ pm_candidate2 = old_path_metrics[11] + input_symbol_imag + increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[6] = pm_candidate1;
+ trans_table[sample_nr][6] = -1.0;
+ }
+ else{
+ new_path_metrics[6] = pm_candidate2;
+ trans_table[sample_nr][6] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] - input_symbol_imag + increment[1];
+ pm_candidate2 = old_path_metrics[11] - input_symbol_imag - increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[7] = pm_candidate1;
+ trans_table[sample_nr][7] = -1.0;
+ }
+ else{
+ new_path_metrics[7] = pm_candidate2;
+ trans_table[sample_nr][7] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] + input_symbol_imag - increment[6];
+ pm_candidate2 = old_path_metrics[12] + input_symbol_imag + increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[8] = pm_candidate1;
+ trans_table[sample_nr][8] = -1.0;
+ }
+ else{
+ new_path_metrics[8] = pm_candidate2;
+ trans_table[sample_nr][8] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] - input_symbol_imag + increment[6];
+ pm_candidate2 = old_path_metrics[12] - input_symbol_imag - increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[9] = pm_candidate1;
+ trans_table[sample_nr][9] = -1.0;
+ }
+ else{
+ new_path_metrics[9] = pm_candidate2;
+ trans_table[sample_nr][9] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] + input_symbol_imag - increment[7];
+ pm_candidate2 = old_path_metrics[13] + input_symbol_imag + increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[10] = pm_candidate1;
+ trans_table[sample_nr][10] = -1.0;
+ }
+ else{
+ new_path_metrics[10] = pm_candidate2;
+ trans_table[sample_nr][10] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] - input_symbol_imag + increment[7];
+ pm_candidate2 = old_path_metrics[13] - input_symbol_imag - increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[11] = pm_candidate1;
+ trans_table[sample_nr][11] = -1.0;
+ }
+ else{
+ new_path_metrics[11] = pm_candidate2;
+ trans_table[sample_nr][11] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] + input_symbol_imag - increment[4];
+ pm_candidate2 = old_path_metrics[14] + input_symbol_imag + increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[12] = pm_candidate1;
+ trans_table[sample_nr][12] = -1.0;
+ }
+ else{
+ new_path_metrics[12] = pm_candidate2;
+ trans_table[sample_nr][12] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] - input_symbol_imag + increment[4];
+ pm_candidate2 = old_path_metrics[14] - input_symbol_imag - increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[13] = pm_candidate1;
+ trans_table[sample_nr][13] = -1.0;
+ }
+ else{
+ new_path_metrics[13] = pm_candidate2;
+ trans_table[sample_nr][13] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] + input_symbol_imag - increment[5];
+ pm_candidate2 = old_path_metrics[15] + input_symbol_imag + increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[14] = pm_candidate1;
+ trans_table[sample_nr][14] = -1.0;
+ }
+ else{
+ new_path_metrics[14] = pm_candidate2;
+ trans_table[sample_nr][14] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] - input_symbol_imag + increment[5];
+ pm_candidate2 = old_path_metrics[15] - input_symbol_imag - increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[15] = pm_candidate1;
+ trans_table[sample_nr][15] = -1.0;
+ }
+ else{
+ new_path_metrics[15] = pm_candidate2;
+ trans_table[sample_nr][15] = 1.0;
+ }
+ tmp=old_path_metrics;
+ old_path_metrics=new_path_metrics;
+ new_path_metrics=tmp;
+
+ sample_nr++;
+ if(sample_nr==samples_num)
+ break;
+
+ //Processing real states
+ real_imag=0;
+ input_symbol_real = input[sample_nr].real();
+
+ pm_candidate1 = old_path_metrics[0] - input_symbol_real - increment[7];
+ pm_candidate2 = old_path_metrics[8] - input_symbol_real + increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[0] = pm_candidate1;
+ trans_table[sample_nr][0] = -1.0;
+ }
+ else{
+ new_path_metrics[0] = pm_candidate2;
+ trans_table[sample_nr][0] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[0] + input_symbol_real + increment[7];
+ pm_candidate2 = old_path_metrics[8] + input_symbol_real - increment[0];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[1] = pm_candidate1;
+ trans_table[sample_nr][1] = -1.0;
+ }
+ else{
+ new_path_metrics[1] = pm_candidate2;
+ trans_table[sample_nr][1] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] - input_symbol_real - increment[6];
+ pm_candidate2 = old_path_metrics[9] - input_symbol_real + increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[2] = pm_candidate1;
+ trans_table[sample_nr][2] = -1.0;
+ }
+ else{
+ new_path_metrics[2] = pm_candidate2;
+ trans_table[sample_nr][2] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[1] + input_symbol_real + increment[6];
+ pm_candidate2 = old_path_metrics[9] + input_symbol_real - increment[1];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[3] = pm_candidate1;
+ trans_table[sample_nr][3] = -1.0;
+ }
+ else{
+ new_path_metrics[3] = pm_candidate2;
+ trans_table[sample_nr][3] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] - input_symbol_real - increment[5];
+ pm_candidate2 = old_path_metrics[10] - input_symbol_real + increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[4] = pm_candidate1;
+ trans_table[sample_nr][4] = -1.0;
+ }
+ else{
+ new_path_metrics[4] = pm_candidate2;
+ trans_table[sample_nr][4] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[2] + input_symbol_real + increment[5];
+ pm_candidate2 = old_path_metrics[10] + input_symbol_real - increment[2];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[5] = pm_candidate1;
+ trans_table[sample_nr][5] = -1.0;
+ }
+ else{
+ new_path_metrics[5] = pm_candidate2;
+ trans_table[sample_nr][5] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] - input_symbol_real - increment[4];
+ pm_candidate2 = old_path_metrics[11] - input_symbol_real + increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[6] = pm_candidate1;
+ trans_table[sample_nr][6] = -1.0;
+ }
+ else{
+ new_path_metrics[6] = pm_candidate2;
+ trans_table[sample_nr][6] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[3] + input_symbol_real + increment[4];
+ pm_candidate2 = old_path_metrics[11] + input_symbol_real - increment[3];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[7] = pm_candidate1;
+ trans_table[sample_nr][7] = -1.0;
+ }
+ else{
+ new_path_metrics[7] = pm_candidate2;
+ trans_table[sample_nr][7] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] - input_symbol_real - increment[3];
+ pm_candidate2 = old_path_metrics[12] - input_symbol_real + increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[8] = pm_candidate1;
+ trans_table[sample_nr][8] = -1.0;
+ }
+ else{
+ new_path_metrics[8] = pm_candidate2;
+ trans_table[sample_nr][8] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[4] + input_symbol_real + increment[3];
+ pm_candidate2 = old_path_metrics[12] + input_symbol_real - increment[4];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[9] = pm_candidate1;
+ trans_table[sample_nr][9] = -1.0;
+ }
+ else{
+ new_path_metrics[9] = pm_candidate2;
+ trans_table[sample_nr][9] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] - input_symbol_real - increment[2];
+ pm_candidate2 = old_path_metrics[13] - input_symbol_real + increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[10] = pm_candidate1;
+ trans_table[sample_nr][10] = -1.0;
+ }
+ else{
+ new_path_metrics[10] = pm_candidate2;
+ trans_table[sample_nr][10] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[5] + input_symbol_real + increment[2];
+ pm_candidate2 = old_path_metrics[13] + input_symbol_real - increment[5];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[11] = pm_candidate1;
+ trans_table[sample_nr][11] = -1.0;
+ }
+ else{
+ new_path_metrics[11] = pm_candidate2;
+ trans_table[sample_nr][11] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] - input_symbol_real - increment[1];
+ pm_candidate2 = old_path_metrics[14] - input_symbol_real + increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[12] = pm_candidate1;
+ trans_table[sample_nr][12] = -1.0;
+ }
+ else{
+ new_path_metrics[12] = pm_candidate2;
+ trans_table[sample_nr][12] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[6] + input_symbol_real + increment[1];
+ pm_candidate2 = old_path_metrics[14] + input_symbol_real - increment[6];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[13] = pm_candidate1;
+ trans_table[sample_nr][13] = -1.0;
+ }
+ else{
+ new_path_metrics[13] = pm_candidate2;
+ trans_table[sample_nr][13] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] - input_symbol_real - increment[0];
+ pm_candidate2 = old_path_metrics[15] - input_symbol_real + increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[14] = pm_candidate1;
+ trans_table[sample_nr][14] = -1.0;
+ }
+ else{
+ new_path_metrics[14] = pm_candidate2;
+ trans_table[sample_nr][14] = 1.0;
+ }
+
+ pm_candidate1 = old_path_metrics[7] + input_symbol_real + increment[0];
+ pm_candidate2 = old_path_metrics[15] + input_symbol_real - increment[7];
+ if(pm_candidate1 > pm_candidate2){
+ new_path_metrics[15] = pm_candidate1;
+ trans_table[sample_nr][15] = -1.0;
+ }
+ else{
+ new_path_metrics[15] = pm_candidate2;
+ trans_table[sample_nr][15] = 1.0;
+ }
+ tmp=old_path_metrics;
+ old_path_metrics=new_path_metrics;
+ new_path_metrics=tmp;
+
+ sample_nr++;
+ }
+
+/*
+* Find the best from the stop states by comparing their path metrics.
+* Not every stop state is always possible, so we are searching in
+* a subset of them.
+*/
+ unsigned int best_stop_state;
+ float stop_state_metric, max_stop_state_metric;
+ best_stop_state = stop_states[0];
+ max_stop_state_metric = old_path_metrics[best_stop_state];
+ for(i=1; i< stops_num; i++){
+ stop_state_metric = old_path_metrics[stop_states[i]];
+ if(stop_state_metric > max_stop_state_metric){
+ max_stop_state_metric = stop_state_metric;
+ best_stop_state = stop_states[i];
+ }
+ }
+
+/*
+* This table was generated with hope that it gives a litle speedup during
+* traceback stage.
+* Received bit is related to the number of state in the trellis.
+* I've numbered states so their parity (number of ones) is related
+* to a received bit.
+*/
+ static const unsigned int parity_table[PATHS_NUM] = { 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, };
+
+/*
+* Table of previous states in the trellis diagram.
+* For GMSK modulation every state has two previous states.
+* Example:
+* previous_state_nr1 = prev_table[current_state_nr][0]
+* previous_state_nr2 = prev_table[current_state_nr][1]
+*/
+ static const unsigned int prev_table[PATHS_NUM][2] = { {0,8}, {0,8}, {1,9}, {1,9}, {2,10}, {2,10}, {3,11}, {3,11}, {4,12}, {4,12}, {5,13}, {5,13}, {6,14}, {6,14}, {7,15}, {7,15}, };
+
+/*
+* Traceback and differential decoding of received sequence.
+* Decisions stored in trans_table are used to restore best path in the trellis.
+*/
+ sample_nr=samples_num;
+ unsigned int state_nr=best_stop_state;
+ unsigned int decision;
+ bool out_bit=0;
+
+ while(sample_nr>0){
+ sample_nr--;
+ decision = (trans_table[sample_nr][state_nr]>0);
+
+ if(decision != out_bit)
+ output[sample_nr]=-trans_table[sample_nr][state_nr];
+ else
+ output[sample_nr]=trans_table[sample_nr][state_nr];
+
+ out_bit = out_bit ^ real_imag ^ parity_table[state_nr];
+ state_nr = prev_table[state_nr][decision];
+ real_imag = !real_imag;
+ }
+}
personal git repositories of Harald Welte. Your mileage may vary