Merged r8195:8205 from jcorgan/ecc into trunk. Adds convolutional encoder

and decoder corresponding to the R=1/2, K=7 CCSDS standard ("Voyager").

This code is a GNU Radio wrapper around a 1995-era KA9Q portable-C 
implementation, and is designed for continuous streaming data, not packets.

The encoder takes MSB packed bytes and outputs channel symbols 0 or 1.

The decoder uses soft-decision Viterbi decoding on a floating point stream of
(possibly noise corrupted) [1.0, 1.0] symbols, and outputs MSB packed
decoded bytes.

Benchmarking on a 2.16 GHz Intel Core 2 Duo shows 4.7 Mbps decoding rate at 
100% CPU usage (single core).  (There is a newer KA9Q library that implements 
SIMD speed ups with correspondingly faster performance.)

The KA9Q library is placed into src/lib/viterbi.  It could use some cleanup,
file/function renaming, and refactoring, or even replacement with the newer
libfec code that is available.



git-svn-id: http://gnuradio.org/svn/gnuradio/trunk@8206 221aa14e-8319-0410-a670-987f0aec2ac5

8 files changed, 361 insertions, 3 deletions

diff --git a/gnuradio-core/src/lib/general/Makefile.am b/gnuradio-core/src/lib/general/Makefile.am
index 5a12a739a..b499ee670 100644
--- a/gnuradio-core/src/lib/general/Makefile.am
+++ b/gnuradio-core/src/lib/general/Makefile.am
@@ -59,12 +59,14 @@ libgeneral_la_SOURCES = 		\
 	gr_crc32.cc			\
 	gr_ctcss_squelch_ff.cc		\
 	gr_dd_mpsk_sync_cc.cc		\
+	gr_decode_ccsds_27_fb.cc	\
 	gr_deinterleave.cc		\
 	gr_delay.cc			\
 	gr_diff_decoder_bb.cc		\
 	gr_diff_encoder_bb.cc		\
 	gr_diff_phasor_cc.cc		\
 	gr_dpll_bb.cc			\
+	gr_encode_ccsds_27_bb.cc	\
 	gr_fake_channel_coder_pp.cc	\
 	gr_fast_atan2f.cc		\
 	gr_feedforward_agc_cc.cc	\
@@ -174,8 +176,6 @@ libgeneral_qa_la_SOURCES = 		\
 	qa_gr_fxpt_vco.cc		\
 	qa_gr_math.cc
 
-
-
 grinclude_HEADERS = 			\
 	gr_agc_cc.h                 	\
 	gr_agc_ff.h                 	\
@@ -199,15 +199,17 @@ grinclude_HEADERS = 			\
 	gr_costas_loop_cc.h		\
 	gr_count_bits.h			\
 	gr_cpfsk_bc.h			\
-    	gr_crc32.h			\
+	gr_crc32.h			\
 	gr_ctcss_squelch_ff.h		\
 	gr_dd_mpsk_sync_cc.h		\
+	gr_decode_ccsds_27_fb.h		\
 	gr_diff_decoder_bb.h		\
 	gr_diff_encoder_bb.h		\
 	gr_deinterleave.h		\
 	gr_delay.h			\
 	gr_diff_phasor_cc.h		\
 	gr_dpll_bb.h			\
+	gr_encode_ccsds_27_bb.h		\
 	gr_expj.h			\
 	gr_fake_channel_coder_pp.h	\
 	gr_feedforward_agc_cc.h		\
@@ -358,12 +360,14 @@ swiginclude_HEADERS =			\
 	gr_crc32.i			\
 	gr_ctcss_squelch_ff.i		\
 	gr_dd_mpsk_sync_cc.i		\
+	gr_decode_ccsds_27_fb.i		\
 	gr_diff_decoder_bb.i		\
 	gr_diff_encoder_bb.i		\
 	gr_diff_phasor_cc.i		\
 	gr_dpll_bb.i			\
 	gr_deinterleave.i		\
 	gr_delay.i			\
+	gr_encode_ccsds_27_bb.i		\
 	gr_fake_channel_coder_pp.i	\
 	gr_feedforward_agc_cc.i		\
 	gr_feval.i			\
diff --git a/gnuradio-core/src/lib/general/general.i b/gnuradio-core/src/lib/general/general.i
index 724ea0316..21bbdb2c5 100644
--- a/gnuradio-core/src/lib/general/general.i
+++ b/gnuradio-core/src/lib/general/general.i
@@ -131,6 +131,8 @@
 #include <gr_peak_detector2_fb.h>
 #include <gr_repeat.h>
 #include <gr_cpfsk_bc.h>
+#include <gr_encode_ccsds_27_bb.h>
+#include <gr_decode_ccsds_27_fb.h>
 %}
 
 %include "gr_nop.i"
@@ -242,3 +244,5 @@
 %include "gr_peak_detector2_fb.i"
 %include "gr_repeat.i"
 %include "gr_cpfsk_bc.i"
+%include "gr_encode_ccsds_27_bb.i"
+%include "gr_decode_ccsds_27_fb.i"
diff --git a/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.cc b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.cc
new file mode 100644
index 000000000..add036f20
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.cc
@@ -0,0 +1,86 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gr_decode_ccsds_27_fb.h>
+#include <gr_io_signature.h>
+
+gr_decode_ccsds_27_fb_sptr 
+gr_make_decode_ccsds_27_fb()
+{
+  return gr_decode_ccsds_27_fb_sptr(new gr_decode_ccsds_27_fb());
+}
+
+gr_decode_ccsds_27_fb::gr_decode_ccsds_27_fb()
+  : gr_sync_decimator("decode_ccsds_27_fb",
+		      gr_make_io_signature(1, 1, sizeof(float)),
+		      gr_make_io_signature(1, 1, sizeof(char)),
+		      2*8)  // Rate 1/2 code, unpacked to packed translation
+{
+    float RATE = 0.5;
+    float ebn0 = 12.0;
+    float esn0 = RATE*pow(10.0, ebn0/10);
+
+    gen_met(d_mettab, 100, esn0, 0.0, 256);
+    viterbi_chunks_init(d_state0);
+}
+
+gr_decode_ccsds_27_fb::~gr_decode_ccsds_27_fb()
+{
+}
+
+int 
+gr_decode_ccsds_27_fb::work(int noutput_items,
+			    gr_vector_const_void_star &input_items,
+			    gr_vector_void_star &output_items)
+{
+  const float *in = (const float *)input_items[0];
+  unsigned char *out = (unsigned char *)output_items[0];
+
+  for (int i = 0; i < noutput_items*16; i++) {
+    // Translate and clip [-1.0..1.0] to [28..228]
+    float sample = in[i]*100.0+128.0;
+    if (sample > 255.0)
+	sample = 255.0;
+    else if (sample < 0.0)
+	sample = 0.0;
+    unsigned char sym = (unsigned char)(floor(sample));
+    
+    d_viterbi_in[d_count % 4] = sym;
+    if ((d_count % 4) == 3) {
+      // Every fourth symbol, perform butterfly operation
+      viterbi_butterfly2(d_viterbi_in, d_mettab, d_state0, d_state1);
+      
+      // Every sixteenth symbol, read out a byte
+      if (d_count % 16 == 11) {
+	// long metric = 
+	viterbi_get_output(d_state0, out++);
+	// printf("%li\n", *(out-1), metric);
+      }
+    }
+    
+    d_count++;
+  }
+
+  return noutput_items;
+}
diff --git a/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.h b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.h
new file mode 100644
index 000000000..50a6c9d89
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.h
@@ -0,0 +1,77 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+#ifndef INCLUDED_GR_DECODE_CCSDS_27_FB_H
+#define INCLUDED_GR_DECODE_CCSDS_27_FB_H
+
+#include <gr_sync_decimator.h>
+
+extern "C" {
+#include "../viterbi/viterbi.h"
+}
+
+class gr_decode_ccsds_27_fb;
+
+typedef boost::shared_ptr<gr_decode_ccsds_27_fb> gr_decode_ccsds_27_fb_sptr;
+
+gr_decode_ccsds_27_fb_sptr gr_make_decode_ccsds_27_fb();
+
+/*! \brief A rate 1/2, k=7 convolutional decoder for the CCSDS standard
+ * \ingroup ecc
+ *  
+ * This block performs soft-decision convolutional decoding using the Viterbi
+ * algorithm.
+ *  
+ * The input is a stream of (possibly noise corrupted) floating point values 
+ * nominally spanning [-1.0, 1.0], representing the encoded channel symbols 
+ * 0 (-1.0) and 1 (1.0), with erased symbols at 0.0.
+ *
+ * The output is MSB first packed bytes of decoded values.
+ *
+ * As a rate 1/2 code, there will be one output byte for every 16 input symbols.
+ *
+ * This block is designed for continuous data streaming, not packetized data.
+ * The first 32 bits out will be zeroes, with the output delayed four bytes
+ * from the corresponding inputs.
+ */
+
+class gr_decode_ccsds_27_fb : public gr_sync_decimator
+{
+private:
+  friend gr_decode_ccsds_27_fb_sptr gr_make_decode_ccsds_27_fb();
+
+  gr_decode_ccsds_27_fb();
+
+  // Viterbi state
+  int d_mettab[2][256];
+  struct viterbi_state d_state0[64];
+  struct viterbi_state d_state1[64];
+  unsigned char d_viterbi_in[16];
+
+  int d_count;
+      
+public:
+  ~gr_decode_ccsds_27_fb();
+
+  int work (int noutput_items,
+	    gr_vector_const_void_star &input_items,
+	    gr_vector_void_star &output_items);
+};
+
+#endif /* INCLUDED_GR_DECODE_CCSDS_27_FB_H */
diff --git a/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.i b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.i
new file mode 100644
index 000000000..f05a0141b
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.i
@@ -0,0 +1,31 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 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.
+ */
+
+GR_SWIG_BLOCK_MAGIC(gr,decode_ccsds_27_fb);
+
+gr_decode_ccsds_27_fb_sptr gr_make_decode_ccsds_27_fb ();
+
+class gr_decode_ccsds_27_fb : public gr_sync_decimator
+{
+private:
+  gr_decode_ccsds_27_fb();
+};
diff --git a/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.cc b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.cc
new file mode 100644
index 000000000..76b8091f7
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.cc
@@ -0,0 +1,62 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2004,2008 Free Software Foundation, Inc.
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+
+#ifdef HAVE_CONFIG_H
+#include "config.h"
+#endif
+
+#include <gr_encode_ccsds_27_bb.h>
+#include <gr_io_signature.h>
+
+extern "C" {
+#include <../viterbi/viterbi.h>
+}
+
+gr_encode_ccsds_27_bb_sptr 
+gr_make_encode_ccsds_27_bb()
+{
+  return gr_encode_ccsds_27_bb_sptr(new gr_encode_ccsds_27_bb());
+}
+
+gr_encode_ccsds_27_bb::gr_encode_ccsds_27_bb()
+  : gr_sync_interpolator("encode_ccsds_27_bb",
+		         gr_make_io_signature(1, 1, sizeof(char)),
+		         gr_make_io_signature(1, 1, sizeof(char)),
+			 16)  // Rate 1/2 code, packed to unpacked conversion
+{
+  d_encstate = 0;
+}
+
+gr_encode_ccsds_27_bb::~gr_encode_ccsds_27_bb()
+{
+}
+
+int 
+gr_encode_ccsds_27_bb::work(int noutput_items,
+			    gr_vector_const_void_star &input_items,
+			    gr_vector_void_star &output_items)
+{
+  unsigned char *in = (unsigned char *)input_items[0];
+  unsigned char *out = (unsigned char *)output_items[0];
+
+  d_encstate = encode(out, in, noutput_items/16, d_encstate);
+
+  return noutput_items;
+}
diff --git a/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.h b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.h
new file mode 100644
index 000000000..86832ee05
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.h
@@ -0,0 +1,63 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 Free Software Foundation, Inc.
+ * 
+ * GNU Radio is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License as published by
+ * the Free Software Foundation; either version 3, or (at your option)
+ * any later version.
+ * 
+ * GNU Radio is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU General Public License for more details.
+ * 
+ * You should have received a copy of the GNU General Public License
+ * along with GNU Radio; see the file COPYING.  If not, write to
+ * the Free Software Foundation, Inc., 51 Franklin Street,
+ * Boston, MA 02110-1301, USA.
+ */
+#ifndef INCLUDED_GR_ENCODE_CCSDS_27_BB_H
+#define INCLUDED_GR_ENCODE_CCSDS_27_BB_H
+
+#include <gr_sync_interpolator.h>
+
+class gr_encode_ccsds_27_bb;
+
+typedef boost::shared_ptr<gr_encode_ccsds_27_bb> gr_encode_ccsds_27_bb_sptr;
+
+gr_encode_ccsds_27_bb_sptr gr_make_encode_ccsds_27_bb();
+
+/*! \brief A rate 1/2, k=7 convolutional encoder for the CCSDS standard
+ * \ingroup ecc
+ *  
+ * This block performs convolutional encoding using the CCSDS standard
+ * polynomial ("Voyager").
+ *  
+ * The input is an MSB first packed stream of bits.
+ *
+ * The output is a stream of symbols 0 or 1 representing the encoded data.
+ *
+ * As a rate 1/2 code, there will be 16 output symbols for every input byte.
+ *
+ * This block is designed for continuous data streaming, not packetized data.
+ * There is no provision to "flush" the encoder.
+ */
+
+class gr_encode_ccsds_27_bb : public gr_sync_interpolator
+{
+private:
+  friend gr_encode_ccsds_27_bb_sptr gr_make_encode_ccsds_27_bb();
+
+  gr_encode_ccsds_27_bb();
+  unsigned char d_encstate;
+  
+ public:
+  ~gr_encode_ccsds_27_bb();
+
+  int work (int noutput_items,
+	    gr_vector_const_void_star &input_items,
+	    gr_vector_void_star &output_items);
+};
+
+#endif /* INCLUDED_GR_ENCODE_CCSDS_27_BB_H */
diff --git a/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.i b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.i
new file mode 100644
index 000000000..d4bda41cc
--- /dev/null
+++ b/gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.i
@@ -0,0 +1,31 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2008 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.
+ */
+
+GR_SWIG_BLOCK_MAGIC(gr,encode_ccsds_27_bb);
+
+gr_encode_ccsds_27_bb_sptr gr_make_encode_ccsds_27_bb ();
+
+class gr_encode_ccsds_27_bb : public gr_sync_interpolator
+{
+private:
+  gr_encode_ccsds_27_bb();
+};