From a52f9a19581901beabc9111917965b9817231014 Mon Sep 17 00:00:00 2001 From: jcorgan Date: Tue, 15 Apr 2008 21:31:29 +0000 Subject: [PATCH] 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 --- config/grc_gnuradio_core.m4 | 2 + gnuradio-core/src/lib/Makefile.am | 3 +- gnuradio-core/src/lib/general/Makefile.am | 10 +- gnuradio-core/src/lib/general/general.i | 4 + .../src/lib/general/gr_decode_ccsds_27_fb.cc | 86 +++++ .../src/lib/general/gr_decode_ccsds_27_fb.h | 77 ++++ .../src/lib/general/gr_decode_ccsds_27_fb.i | 31 ++ .../src/lib/general/gr_encode_ccsds_27_bb.cc | 62 +++ .../src/lib/general/gr_encode_ccsds_27_bb.h | 63 ++++ .../src/lib/general/gr_encode_ccsds_27_bb.i | 31 ++ gnuradio-core/src/lib/viterbi/Makefile.am | 41 ++ gnuradio-core/src/lib/viterbi/decode.cc | 88 +++++ gnuradio-core/src/lib/viterbi/encode.cc | 54 +++ gnuradio-core/src/lib/viterbi/metrics.c | 119 ++++++ gnuradio-core/src/lib/viterbi/tab.c | 57 +++ gnuradio-core/src/lib/viterbi/viterbi.c | 355 ++++++++++++++++++ gnuradio-core/src/lib/viterbi/viterbi.h | 49 +++ .../src/python/gnuradio/gr/Makefile.am | 1 + .../src/python/gnuradio/gr/qa_ecc_ccsds_27.py | 50 +++ 19 files changed, 1179 insertions(+), 4 deletions(-) create mode 100644 gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.cc create mode 100644 gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.h create mode 100644 gnuradio-core/src/lib/general/gr_decode_ccsds_27_fb.i create mode 100644 gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.cc create mode 100644 gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.h create mode 100644 gnuradio-core/src/lib/general/gr_encode_ccsds_27_bb.i create mode 100644 gnuradio-core/src/lib/viterbi/Makefile.am create mode 100644 gnuradio-core/src/lib/viterbi/decode.cc create mode 100644 gnuradio-core/src/lib/viterbi/encode.cc create mode 100644 gnuradio-core/src/lib/viterbi/metrics.c create mode 100644 gnuradio-core/src/lib/viterbi/tab.c create mode 100644 gnuradio-core/src/lib/viterbi/viterbi.c create mode 100644 gnuradio-core/src/lib/viterbi/viterbi.h create mode 100755 gnuradio-core/src/python/gnuradio/gr/qa_ecc_ccsds_27.py diff --git a/config/grc_gnuradio_core.m4 b/config/grc_gnuradio_core.m4 index 09ac12fb..24432a28 100644 --- a/config/grc_gnuradio_core.m4 +++ b/config/grc_gnuradio_core.m4 @@ -46,6 +46,7 @@ AC_DEFUN([GRC_GNURADIO_CORE],[ -I\${abs_top_srcdir}/gnuradio-core/src/lib/filter \ -I\${abs_top_builddir}/gnuradio-core/src/lib/filter \ -I\${abs_top_srcdir}/gnuradio-core/src/lib/reed-solomon \ +-I\${abs_top_srcdir}/gnuradio-core/src/lib/viterbi \ -I\${abs_top_srcdir}/gnuradio-core/src/lib/io \ -I\${abs_top_srcdir}/gnuradio-core/src/lib/g72x \ -I\${abs_top_srcdir}/gnuradio-core/src/lib/swig \ @@ -90,6 +91,7 @@ AC_DEFUN([GRC_GNURADIO_CORE],[ gnuradio-core/src/lib/io/Makefile \ gnuradio-core/src/lib/missing/Makefile \ gnuradio-core/src/lib/reed-solomon/Makefile \ + gnuradio-core/src/lib/viterbi/Makefile \ gnuradio-core/src/lib/runtime/Makefile \ gnuradio-core/src/lib/swig/Makefile \ gnuradio-core/src/python/Makefile \ diff --git a/gnuradio-core/src/lib/Makefile.am b/gnuradio-core/src/lib/Makefile.am index f6693ddc..66567048 100644 --- a/gnuradio-core/src/lib/Makefile.am +++ b/gnuradio-core/src/lib/Makefile.am @@ -24,7 +24,7 @@ include $(top_srcdir)/Makefile.common ## Process this file with automake to produce Makefile.in # We've got to build . before swig -SUBDIRS = missing runtime filter general gengen g72x reed-solomon io . swig +SUBDIRS = missing runtime filter viterbi general gengen g72x reed-solomon io . swig # generate libgnuradio-core.la from the convenience libraries in subdirs @@ -39,6 +39,7 @@ libgnuradio_core_qa_la_LDFLAGS = $(NO_UNDEFINED) -version-info 0:0:0 \ libgnuradio_core_la_LIBADD = \ filter/libfilter.la \ g72x/libccitt.la \ + viterbi/libviterbi.la \ general/libgeneral.la \ gengen/libgengen.la \ io/libio.la \ diff --git a/gnuradio-core/src/lib/general/Makefile.am b/gnuradio-core/src/lib/general/Makefile.am index 5a12a739..b499ee67 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 724ea031..21bbdb2c 100644 --- a/gnuradio-core/src/lib/general/general.i +++ b/gnuradio-core/src/lib/general/general.i @@ -131,6 +131,8 @@ #include #include #include +#include +#include %} %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 00000000..add036f2 --- /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 +#include + +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 00000000..50a6c9d8 --- /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 + +extern "C" { +#include "../viterbi/viterbi.h" +} + +class gr_decode_ccsds_27_fb; + +typedef boost::shared_ptr 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 00000000..f05a0141 --- /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 00000000..76b8091f --- /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 +#include + +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 00000000..86832ee0 --- /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 + +class gr_encode_ccsds_27_bb; + +typedef boost::shared_ptr 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 00000000..d4bda41c --- /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(); +}; diff --git a/gnuradio-core/src/lib/viterbi/Makefile.am b/gnuradio-core/src/lib/viterbi/Makefile.am new file mode 100644 index 00000000..3eb1502b --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/Makefile.am @@ -0,0 +1,41 @@ +# +# 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. +# + +INCLUDES = -Wall -Werror +LIBS = -lm + +noinst_LTLIBRARIES = libviterbi.la + +libviterbi_la_SOURCES = \ + metrics.c \ + tab.c \ + viterbi.c + +noinst_HEADERS = \ + viterbi.h + +noinst_PROGRAMS = encode decode + +encode_SOURCES = encode.cc + +encode_LDADD = libviterbi.la + +decode_SOURCES = decode.cc + +decode_LDADD = libviterbi.la diff --git a/gnuradio-core/src/lib/viterbi/decode.cc b/gnuradio-core/src/lib/viterbi/decode.cc new file mode 100644 index 00000000..6580e4d6 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/decode.cc @@ -0,0 +1,88 @@ +/* -*- 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. + */ + +/* + * This is a minimal example demonstrating how to call the Viterbi decoder + * in continuous streaming mode. It accepts data on stdin and writes to + * stdout. + * + */ + +extern "C" { +#include "viterbi.h" +} + +#include +#include + +#define MAXCHUNKSIZE 4096 +#define MAXENCSIZE MAXCHUNKSIZE*16 + +int main() +{ + unsigned char data[MAXCHUNKSIZE]; + signed char syms[MAXENCSIZE]; + int count = 0; + + // Initialize metric table + int mettab[2][256]; + int amp = 100; + float RATE=0.5; + float ebn0 = 12.0; + float esn0 = RATE*pow(10.0, ebn0/10); + gen_met(mettab, amp, esn0, 0.0, 4); + + // Initialize decoder state + struct viterbi_state state0[64]; + struct viterbi_state state1[64]; + unsigned char viterbi_in[16]; + viterbi_chunks_init(state0); + + while (!feof(stdin)) { + unsigned int n = fread(syms, 1, MAXENCSIZE, stdin); + unsigned char *out = data; + + for (unsigned int i = 0; i < n; i++) { + + // FIXME: This implements hard decoding by slicing the input stream + unsigned char sym = syms[i] > 0 ? -amp : amp; + + // Write the symbol to the decoder input + viterbi_in[count % 4] = sym; + + // Every four symbols, perform the butterfly2 operation + if ((count % 4) == 3) { + viterbi_butterfly2(viterbi_in, mettab, state0, state1); + + // Every sixteen symbols, perform the readback operation + if ((count > 64) && (count % 16) == 11) { + viterbi_get_output(state0, out); + fwrite(out++, 1, 1, stdout); + } + } + + count++; + } + } + + return 0; +} diff --git a/gnuradio-core/src/lib/viterbi/encode.cc b/gnuradio-core/src/lib/viterbi/encode.cc new file mode 100644 index 00000000..01acb398 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/encode.cc @@ -0,0 +1,54 @@ +/* -*- 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. + */ + +/* + * This is a minimal example demonstrating how to call the ECC encoder + * in continuous streaming mode. It accepts data on stdin and writes to + * stdout. + * + * FIXME: This does not flush the final bits out of the encoder. + * + */ + +extern "C" { +#include "viterbi.h" +} + +#include + +#define MAXCHUNKSIZE 4096 +#define MAXENCSIZE MAXCHUNKSIZE*16 + +int main() +{ + unsigned char encoder_state = 0; + unsigned char data[MAXCHUNKSIZE]; + unsigned char syms[MAXENCSIZE]; + + while (!feof(stdin)) { + unsigned int n = fread(data, 1, MAXCHUNKSIZE, stdin); + encoder_state = encode(syms, data, n, encoder_state); + fwrite(syms, 1, n*16, stdout); + } + + return 0; +} diff --git a/gnuradio-core/src/lib/viterbi/metrics.c b/gnuradio-core/src/lib/viterbi/metrics.c new file mode 100644 index 00000000..74f8ce09 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/metrics.c @@ -0,0 +1,119 @@ +/* + * Copyright 1995 Phil Karn, KA9Q + * 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. + */ + +/* + * Generate metric tables for a soft-decision convolutional decoder + * assuming gaussian noise on a PSK channel. + * + * Works from "first principles" by evaluating the normal probability + * function and then computing the log-likelihood function + * for every possible received symbol value + * + */ + +/* Symbols are offset-binary, with 128 corresponding to an erased (no + * information) symbol + */ +#define OFFSET 128 + +#include +#include + +/* Normal function integrated from -Inf to x. Range: 0-1 */ +#define normal(x) (0.5 + 0.5*erf((x)/M_SQRT2)) + +/* Logarithm base 2 */ +#define log2(x) (log(x)*M_LOG2E) + +/* Generate log-likelihood metrics for 8-bit soft quantized channel + * assuming AWGN and BPSK + */ +void +gen_met(int mettab[2][256], /* Metric table, [sent sym][rx symbol] */ + int amp, /* Signal amplitude, units */ + double esn0, /* Es/N0 ratio in dB */ + double bias, /* Metric bias; 0 for viterbi, rate for sequential */ + int scale) /* Scale factor */ +{ + double noise; + int s,bit; + double metrics[2][256]; + double p0,p1; + + /* Es/N0 as power ratio */ + esn0 = pow(10.,esn0/10); + + noise = 0.5/esn0; /* only half the noise for BPSK */ + noise = sqrt(noise); /* noise/signal Voltage ratio */ + + /* Zero is a special value, since this sample includes all + * lower samples that were clipped to this value, i.e., it + * takes the whole lower tail of the curve + */ + p1 = normal(((0-OFFSET+0.5)/amp - 1)/noise); /* P(s|1) */ + + /* Prob of this value occurring for a 0-bit */ /* P(s|0) */ + p0 = normal(((0-OFFSET+0.5)/amp + 1)/noise); + metrics[0][0] = log2(2*p0/(p1+p0)) - bias; + metrics[1][0] = log2(2*p1/(p1+p0)) - bias; + + for(s=1;s<255;s++){ + /* P(s|1), prob of receiving s given 1 transmitted */ + p1 = normal(((s-OFFSET+0.5)/amp - 1)/noise) - + normal(((s-OFFSET-0.5)/amp - 1)/noise); + + /* P(s|0), prob of receiving s given 0 transmitted */ + p0 = normal(((s-OFFSET+0.5)/amp + 1)/noise) - + normal(((s-OFFSET-0.5)/amp + 1)/noise); + +#ifdef notdef + printf("P(%d|1) = %lg, P(%d|0) = %lg\n",s,p1,s,p0); +#endif + metrics[0][s] = log2(2*p0/(p1+p0)) - bias; + metrics[1][s] = log2(2*p1/(p1+p0)) - bias; + } + /* 255 is also a special value */ + /* P(s|1) */ + p1 = 1 - normal(((255-OFFSET-0.5)/amp - 1)/noise); + /* P(s|0) */ + p0 = 1 - normal(((255-OFFSET-0.5)/amp + 1)/noise); + + metrics[0][255] = log2(2*p0/(p1+p0)) - bias; + metrics[1][255] = log2(2*p1/(p1+p0)) - bias; +#ifdef notdef + /* The probability of a raw symbol error is the probability + * that a 1-bit would be received as a sample with value + * 0-128. This is the offset normal curve integrated from -Inf to 0. + */ + printf("symbol Pe = %lg\n",normal(-1/noise)); +#endif + for(bit=0;bit<2;bit++){ + for(s=0;s<256;s++){ + /* Scale and round to nearest integer */ + mettab[bit][s] = floor(metrics[bit][s] * scale + 0.5); +#ifdef notdef + printf("metrics[%d][%d] = %lg, mettab = %d\n", + bit,s,metrics[bit][s],mettab[bit][s]); +#endif + } + } +} diff --git a/gnuradio-core/src/lib/viterbi/tab.c b/gnuradio-core/src/lib/viterbi/tab.c new file mode 100644 index 00000000..1133c630 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/tab.c @@ -0,0 +1,57 @@ +/* + * Copyright 1995 Phil Karn, KA9Q + * 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. + */ + +/* 8-bit parity lookup table, generated by partab.c */ +unsigned char Partab[] = { + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, + 0, 1, 1, 0, 1, 0, 0, 1, + 0, 1, 1, 0, 1, 0, 0, 1, + 1, 0, 0, 1, 0, 1, 1, 0, +}; diff --git a/gnuradio-core/src/lib/viterbi/viterbi.c b/gnuradio-core/src/lib/viterbi/viterbi.c new file mode 100644 index 00000000..9f5c1e72 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/viterbi.c @@ -0,0 +1,355 @@ +/* + * Copyright 1995 Phil Karn, KA9Q + * 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. + */ + +/* + * Viterbi decoder for K=7 rate=1/2 convolutional code + * Some modifications from original Karn code by Matt Ettus + */ + +#include "viterbi.h" + +/* The two generator polynomials for the NASA Standard K=7 code. + * Since these polynomials are known to be optimal for this constraint + * length there is not much point in changing them. But if you do, you + * will have to regenerate the BUTTERFLY macro calls in viterbi() + */ +#define POLYA 0x6d +#define POLYB 0x4f + +/* The basic Viterbi decoder operation, called a "butterfly" + * operation because of the way it looks on a trellis diagram. Each + * butterfly involves an Add-Compare-Select (ACS) operation on the two nodes + * where the 0 and 1 paths from the current node merge at the next step of + * the trellis. + * + * The code polynomials are assumed to have 1's on both ends. Given a + * function encode_state() that returns the two symbols for a given + * encoder state in the low two bits, such a code will have the following + * identities for even 'n' < 64: + * + * encode_state(n) = encode_state(n+65) + * encode_state(n+1) = encode_state(n+64) = (3 ^ encode_state(n)) + * + * Any convolutional code you would actually want to use will have + * these properties, so these assumptions aren't too limiting. + * + * Doing this as a macro lets the compiler evaluate at compile time the + * many expressions that depend on the loop index and encoder state and + * emit them as immediate arguments. + * This makes an enormous difference on register-starved machines such + * as the Intel x86 family where evaluating these expressions at runtime + * would spill over into memory. + */ +#define BUTTERFLY(i,sym) { \ + int m0,m1;\ +\ + /* ACS for 0 branch */\ + m0 = state[i].metric + mets[sym]; /* 2*i */\ + m1 = state[i+32].metric + mets[3^sym]; /* 2*i + 64 */\ + if(m0 > m1){\ + next[2*i].metric = m0;\ + next[2*i].path = state[i].path << 1;\ + } else {\ + next[2*i].metric = m1;\ + next[2*i].path = (state[i+32].path << 1)|1;\ + }\ + /* ACS for 1 branch */\ + m0 = state[i].metric + mets[3^sym]; /* 2*i + 1 */\ + m1 = state[i+32].metric + mets[sym]; /* 2*i + 65 */\ + if(m0 > m1){\ + next[2*i+1].metric = m0;\ + next[2*i+1].path = state[i].path << 1;\ + } else {\ + next[2*i+1].metric = m1;\ + next[2*i+1].path = (state[i+32].path << 1)|1;\ + }\ +} + +extern unsigned char Partab[]; /* Parity lookup table */ + +/* Convolutionally encode data into binary symbols */ +unsigned char +encode(unsigned char *symbols, + unsigned char *data, + unsigned int nbytes, + unsigned char encstate) +{ + int i; + + while(nbytes-- != 0){ + for(i=7;i>=0;i--){ + encstate = (encstate << 1) | ((*data >> i) & 1); + *symbols++ = Partab[encstate & POLYA]; + *symbols++ = Partab[encstate & POLYB]; + } + data++; + } + + return encstate; +} + +/* Viterbi decoder */ +int +viterbi(unsigned long *metric, /* Final path metric (returned value) */ + unsigned char *data, /* Decoded output data */ + unsigned char *symbols, /* Raw deinterleaved input symbols */ + unsigned int nbits, /* Number of output bits */ + int mettab[2][256] /* Metric table, [sent sym][rx symbol] */ + ){ + unsigned int bitcnt = 0; + int mets[4]; + long bestmetric; + int beststate,i; + struct viterbi_state state0[64],state1[64],*state,*next; + + state = state0; + next = state1; + + /* Initialize starting metrics to prefer 0 state */ + state[0].metric = 0; + for(i=1;i<64;i++) + state[i].metric = -999999; + state[0].path = 0; + + for(bitcnt = 0;bitcnt < nbits;bitcnt++){ + /* Read input symbol pair and compute all possible branch + * metrics + */ + mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]]; + mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]]; + mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]]; + mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]]; + symbols += 2; + + /* These macro calls were generated by genbut.c */ + BUTTERFLY(0,0); + BUTTERFLY(1,1); + BUTTERFLY(2,3); + BUTTERFLY(3,2); + BUTTERFLY(4,3); + BUTTERFLY(5,2); + BUTTERFLY(6,0); + BUTTERFLY(7,1); + BUTTERFLY(8,0); + BUTTERFLY(9,1); + BUTTERFLY(10,3); + BUTTERFLY(11,2); + BUTTERFLY(12,3); + BUTTERFLY(13,2); + BUTTERFLY(14,0); + BUTTERFLY(15,1); + BUTTERFLY(16,2); + BUTTERFLY(17,3); + BUTTERFLY(18,1); + BUTTERFLY(19,0); + BUTTERFLY(20,1); + BUTTERFLY(21,0); + BUTTERFLY(22,2); + BUTTERFLY(23,3); + BUTTERFLY(24,2); + BUTTERFLY(25,3); + BUTTERFLY(26,1); + BUTTERFLY(27,0); + BUTTERFLY(28,1); + BUTTERFLY(29,0); + BUTTERFLY(30,2); + BUTTERFLY(31,3); + + /* Swap current and next states */ + if(bitcnt & 1){ + state = state0; + next = state1; + } else { + state = state1; + next = state0; + } + // ETTUS + //if(bitcnt > nbits-7){ + /* In tail, poison non-zero nodes */ + //for(i=1;i<64;i += 2) + // state[i].metric = -9999999; + //} + /* Produce output every 8 bits once path memory is full */ + if((bitcnt % 8) == 5 && bitcnt > 32){ + /* Find current best path */ + bestmetric = state[0].metric; + beststate = 0; + for(i=1;i<64;i++){ + if(state[i].metric > bestmetric){ + bestmetric = state[i].metric; + beststate = i; + } + } +#ifdef notdef + printf("metrics[%d] = %d state = %lx\n",beststate, + state[beststate].metric,state[beststate].path); +#endif + *data++ = state[beststate].path >> 24; + } + + } + /* Output remaining bits from 0 state */ + // ETTUS Find best state instead + bestmetric = state[0].metric; + beststate = 0; + for(i=1;i<64;i++){ + if(state[i].metric > bestmetric){ + bestmetric = state[i].metric; + beststate = i; + } + } + if((i = bitcnt % 8) != 6) + state[beststate].path <<= 6-i; + + *data++ = state[beststate].path >> 24; + *data++ = state[beststate].path >> 16; + *data++ = state[beststate].path >> 8; + *data = state[beststate].path; + //printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric); + *metric = state[beststate].metric; + return 0; +} + + +void +viterbi_chunks_init(struct viterbi_state* state) { + // Initialize starting metrics to prefer 0 state + int i; + state[0].metric = 0; + state[0].path = 0; + for(i=1;i<64;i++) + state[i].metric = -999999; +} + +void +viterbi_butterfly8(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1) +{ + unsigned int bitcnt; + int mets[4]; + + struct viterbi_state *state, *next; + state = state0; + next = state1; + // Operate on 16 symbols (8 bits) at a time + for(bitcnt = 0;bitcnt < 8;bitcnt++){ + // Read input symbol pair and compute all possible branch metrics + mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]]; + mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]]; + mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]]; + mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]]; + symbols += 2; + + // These macro calls were generated by genbut.c + BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2); + BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1); + BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2); + BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1); + BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0); + BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3); + BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0); + BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3); + + // Swap current and next states + if(bitcnt & 1){ + state = state0; + next = state1; + } else { + state = state1; + next = state0; + } + } +} + +void +viterbi_butterfly2(unsigned char *symbols, int mettab[2][256], struct viterbi_state *state0, struct viterbi_state *state1) +{ + //unsigned int bitcnt; + int mets[4]; + + struct viterbi_state *state, *next; + state = state0; + next = state1; + // Operate on 4 symbols (2 bits) at a time + + // Read input symbol pair and compute all possible branch metrics + mets[0] = mettab[0][symbols[0]] + mettab[0][symbols[1]]; + mets[1] = mettab[0][symbols[0]] + mettab[1][symbols[1]]; + mets[2] = mettab[1][symbols[0]] + mettab[0][symbols[1]]; + mets[3] = mettab[1][symbols[0]] + mettab[1][symbols[1]]; + + // These macro calls were generated by genbut.c + BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2); + BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1); + BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2); + BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1); + BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0); + BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3); + BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0); + BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3); + + state = state1; + next = state0; + + // Read input symbol pair and compute all possible branch metrics + mets[0] = mettab[0][symbols[2]] + mettab[0][symbols[3]]; + mets[1] = mettab[0][symbols[2]] + mettab[1][symbols[3]]; + mets[2] = mettab[1][symbols[2]] + mettab[0][symbols[3]]; + mets[3] = mettab[1][symbols[2]] + mettab[1][symbols[3]]; + + // These macro calls were generated by genbut.c + BUTTERFLY(0,0);BUTTERFLY(1,1);BUTTERFLY(2,3);BUTTERFLY(3,2); + BUTTERFLY(4,3);BUTTERFLY(5,2);BUTTERFLY(6,0);BUTTERFLY(7,1); + BUTTERFLY(8,0);BUTTERFLY(9,1);BUTTERFLY(10,3);BUTTERFLY(11,2); + BUTTERFLY(12,3);BUTTERFLY(13,2);BUTTERFLY(14,0);BUTTERFLY(15,1); + BUTTERFLY(16,2);BUTTERFLY(17,3);BUTTERFLY(18,1);BUTTERFLY(19,0); + BUTTERFLY(20,1);BUTTERFLY(21,0);BUTTERFLY(22,2);BUTTERFLY(23,3); + BUTTERFLY(24,2);BUTTERFLY(25,3);BUTTERFLY(26,1);BUTTERFLY(27,0); + BUTTERFLY(28,1);BUTTERFLY(29,0);BUTTERFLY(30,2);BUTTERFLY(31,3); +} + +unsigned char +viterbi_get_output(struct viterbi_state *state, unsigned char *outbuf) { + // Produce output every 8 bits once path memory is full + // if((bitcnt % 8) == 5 && bitcnt > 32) { + + // Find current best path + unsigned int i,beststate; + int bestmetric; + + bestmetric = state[0].metric; + beststate = 0; + for(i=1;i<64;i++) + if(state[i].metric > bestmetric) { + bestmetric = state[i].metric; + beststate = i; + } + *outbuf = state[beststate].path >> 24; + return bestmetric; +} + + +//printf ("BS = %d\tBSM = %d\tM0 = %d\n",beststate,state[beststate].metric,state[0].metric); +// In tail, poison non-zero nodes +//if(bits_out > packet_size-7) +// for(i=1;i<64;i += 2) +// state[i].metric = -9999999; + diff --git a/gnuradio-core/src/lib/viterbi/viterbi.h b/gnuradio-core/src/lib/viterbi/viterbi.h new file mode 100644 index 00000000..155b0d93 --- /dev/null +++ b/gnuradio-core/src/lib/viterbi/viterbi.h @@ -0,0 +1,49 @@ +/* + * 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. + */ + +/* The path memory for each state is 32 bits. This is slightly shorter + * than we'd like for K=7, especially since we chain back every 8 bits. + * But it fits so nicely into a 32-bit machine word... + */ +struct viterbi_state { + unsigned long path; /* Decoded path to this state */ + long metric; /* Cumulative metric to this state */ +}; + +int gen_met(int mettab[2][256], /* Metric table */ + int amp, /* Signal amplitude */ + double esn0, /* Es/N0 ratio in dB */ + double bias, /* Metric bias */ + int scale); /* Scale factor */ + +unsigned char +encode(unsigned char *symbols, unsigned char *data, + unsigned int nbytes,unsigned char encstate); + +void +viterbi_chunks_init(struct viterbi_state* state); + +void +viterbi_butterfly2(unsigned char *symbols, int mettab[2][256], + struct viterbi_state *state0, struct viterbi_state *state1); + +unsigned char +viterbi_get_output(struct viterbi_state *state, unsigned char *outbuf); diff --git a/gnuradio-core/src/python/gnuradio/gr/Makefile.am b/gnuradio-core/src/python/gnuradio/gr/Makefile.am index 5aaef254..7a317a1a 100644 --- a/gnuradio-core/src/python/gnuradio/gr/Makefile.am +++ b/gnuradio-core/src/python/gnuradio/gr/Makefile.am @@ -49,6 +49,7 @@ noinst_PYTHON = \ qa_agc.py \ qa_argmax.py \ qa_bin_statistics.py \ + qa_ecc_ccsds27.py \ qa_cma_equalizer.py \ qa_complex_to_xxx.py \ qa_constellation_decoder_cb.py \ diff --git a/gnuradio-core/src/python/gnuradio/gr/qa_ecc_ccsds_27.py b/gnuradio-core/src/python/gnuradio/gr/qa_ecc_ccsds_27.py new file mode 100755 index 00000000..f02c1a32 --- /dev/null +++ b/gnuradio-core/src/python/gnuradio/gr/qa_ecc_ccsds_27.py @@ -0,0 +1,50 @@ +#!/usr/bin/env python +# +# Copyright 2004,2007 Free Software Foundation, Inc. +# +# This file is part of GNU Radio +# +# GNU Radio is free software; you can redistribute it and/or modify +# it under the terms of the GNU General Public License as published by +# the Free Software Foundation; either version 3, or (at your option) +# any later version. +# +# GNU Radio is distributed in the hope that it will be useful, +# but WITHOUT ANY WARRANTY; without even the implied warranty of +# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the +# GNU General Public License for more details. +# +# You should have received a copy of the GNU General Public License +# along with GNU Radio; see the file COPYING. If not, write to +# the Free Software Foundation, Inc., 51 Franklin Street, +# Boston, MA 02110-1301, USA. +# + +from gnuradio import gr, gr_unittest + +class test_ccsds_27 (gr_unittest.TestCase): + + def setUp (self): + self.tb = gr.top_block () + + def tearDown (self): + self.tb = None + + def test_ccsds_27 (self): + src_data = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10) + expected = (0, 0, 0, 0, 1, 2, 3, 4, 5, 6) + src = gr.vector_source_b(src_data) + enc = gr.encode_ccsds_27_bb() + b2f = gr.char_to_float() + add = gr.add_const_ff(-0.5) + mul = gr.multiply_const_ff(2.0) + dec = gr.decode_ccsds_27_fb() + dst = gr.vector_sink_b() + self.tb.connect(src, enc, b2f, add, mul, dec, dst) + self.tb.run() + dst_data = dst.data() + self.assertEqual(expected, dst_data) + + +if __name__ == '__main__': + gr_unittest.main () -- 2.30.2