[Commit-gnuradio] r3313 - gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib

[anastas]

Author: anastas
Date: 2006-08-16 11:12:15 -0600 (Wed, 16 Aug 2006)
New Revision: 3313

Added:
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.cc
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.h
Modified:
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/Makefile.am
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.cc
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.h
   gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.i
Log:
Added fsm constructor for generating FSM directly from the
generator matrix of binary convolutional codes.
Added functionality to fsm class to compute the best way to
go from any state to any other state (useful for termination)



Property changes on: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib
___________________________________________________________________
Name: svn:ignore
   - Makefile
Makefile.in
.la
.lo
.deps
.libs
*.la
*.lo
*.pyc
trellis.cc
trellis.py

   + Makefile
Makefile.in
.la
.lo
.deps
.libs
*.la
*.lo
*.pyc
trellis.cc
trellis.py
wip


Modified: 
gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/Makefile.am
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/Makefile.am     
2006-08-16 17:06:33 UTC (rev 3312)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/Makefile.am     
2006-08-16 17:12:15 UTC (rev 3313)
@@ -65,6 +65,7 @@
        trellis.cc                      \
         fsm.cc                         \
         quicksort_index.cc             \
+        base.cc                                \
         interleaver.cc                 \
         trellis_calc_metric.cc         \
         trellis_permutation.cc         \
@@ -88,6 +89,7 @@
 grinclude_HEADERS =                    \
         fsm.h                          \
         quicksort_index.h              \
+        base.h                         \
         interleaver.h                  \
         trellis_metric_type.h          \
         trellis_calc_metric.h          \

Added: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.cc
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.cc         
                (rev 0)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.cc 
2006-08-16 17:12:15 UTC (rev 3313)
@@ -0,0 +1,92 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2002 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 2, 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., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#include <cstdio>
+#include <stdexcept>
+#include <cmath>
+#include "base.h"
+
+
+bool dec2base(unsigned int num, int base, std::vector<int> &s)
+{
+  int l = s.size();
+  unsigned int n=num;
+  for(int i=0;i<l;i++) {
+    s[l-i-1] = n % base; //MSB first
+    n /= base;
+  }
+  if(n!=0) {
+    printf("Number %d requires more than %d digits.",num,l);
+    return false;
+  }
+  else
+    return true;
+}
+
+
+unsigned int base2dec(const std::vector<int> &s, int base)
+{
+  int l = s.size();
+  unsigned int num=0;
+  for(int i=0;i<l;i++)
+      num=num*base+s[i];
+  return num;
+}
+
+
+bool dec2bases(unsigned int num, const std::vector<int> &bases, 
std::vector<int> &s)
+{
+  int l = s.size();
+  unsigned int n=num;
+  for(int i=0;i<l;i++) {
+      s[l-i-1] = n % bases[l-i-1];
+      n /= bases[l-i-1];
+  }
+  if(n!=0) {
+    printf("Number %d requires more than %d digits.",num,l);
+    return false;
+  }
+  else
+    return true;
+}
+
+
+
+unsigned int bases2dec(const std::vector<int> &s, const std::vector<int> 
&bases)
+{
+  int l = s.size();
+  unsigned int num=0;
+  for(int i=0;i<l;i++)
+      num = num * bases[i] + s[i];
+  return num;
+}
+
+
+
+
+
+
+
+
+
+
+

Added: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.h
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.h          
                (rev 0)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/base.h  
2006-08-16 17:12:15 UTC (rev 3313)
@@ -0,0 +1,38 @@
+/* -*- c++ -*- */
+/*
+ * Copyright 2002 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 2, 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., 59 Temple Place - Suite 330,
+ * Boston, MA 02111-1307, USA.
+ */
+
+#ifndef INCLUDED_TRELLIS_BASE_H
+#define INCLUDED_TRELLIS_BASE_H
+
+#include <vector>
+
+/*!
+ * \brief  change base
+ */
+
+
+bool dec2base(unsigned int num, int base, std::vector<int> &s);
+bool dec2bases(unsigned int num, const std::vector<int> &bases, 
std::vector<int> &s);
+unsigned int base2dec(const std::vector<int> &s, int base);
+unsigned int bases2dec(const std::vector<int> &s, const std::vector<int> 
&bases);
+
+#endif

Modified: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.cc
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.cc  
2006-08-16 17:06:33 UTC (rev 3312)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.cc  
2006-08-16 17:12:15 UTC (rev 3313)
@@ -23,8 +23,10 @@
 #include <cstdio>
 #include <stdexcept>
 #include <cmath>
+#include "base.h"
 #include "fsm.h"
 
+
 fsm::fsm()
 {
   d_I=0;
@@ -34,6 +36,8 @@
   d_OS.resize(0);
   d_PS.resize(0);
   d_PI.resize(0);
+  d_TMi.resize(0);
+  d_TMl.resize(0);
 }
 
 fsm::fsm(const fsm &FSM)
@@ -45,6 +49,8 @@
   d_OS=FSM.OS();
   d_PS=FSM.PS();
   d_PI=FSM.PI();
+  d_TMi=FSM.TMi();
+  d_TMl=FSM.TMl();
 }
 
 fsm::fsm(int I, int S, int O, const std::vector<int> &NS, const 
std::vector<int> &OS)
@@ -54,19 +60,9 @@
   d_O=O;
   d_NS=NS;
   d_OS=OS;
-  d_PS.resize(d_I*d_S);
-  d_PI.resize(d_I*d_S);
-  
-  // generate the PS, PI tables for later use
-  for(int i=0;i<d_S;i++) {
-    int j=0;
-    for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
-      if(d_NS[ii*d_I+jj]!=i) continue;
-      d_PS[i*d_I+j]=ii;
-      d_PI[i*d_I+j]=jj;
-      j++;
-    }
-  }
+ 
+  generate_PS_PI();
+  generate_TM();
 }
 
 //######################################################################
@@ -84,14 +80,12 @@
   FILE *fsmfile;
 
   if((fsmfile=fopen(name,"r"))==NULL) 
-    throw std::runtime_error ("file open error in fsm()");
+    throw std::runtime_error ("fsm::fsm(const char *name): file open error\n");
     //printf("file open error in fsm()\n");
   
   fscanf(fsmfile,"%d %d %d\n",&d_I,&d_S,&d_O);
   d_NS.resize(d_I*d_S);
   d_OS.resize(d_I*d_S);
-  d_PS.resize(d_I*d_S);
-  d_PI.resize(d_I*d_S);
 
   for(int i=0;i<d_S;i++) {
     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_NS[i*d_I+j]));
@@ -99,19 +93,122 @@
   for(int i=0;i<d_S;i++) {
     for(int j=0;j<d_I;j++) fscanf(fsmfile,"%d",&(d_OS[i*d_I+j]));
   }
+ 
+  generate_PS_PI();
+  generate_TM();
+}
+
+
+
+
+//######################################################################
+//# Automatically generate the FSM from the generator matrix
+//# of a (n,k) binary convolutional code
+//######################################################################
+fsm::fsm(int k, int n, const std::vector<int> &G)
+{
+
+  // calculate maximum memory requirements for each input stream
+  std::vector<int> max_mem_x(k,-1);
+  int max_mem = -1;
+  for(int i=0;i<k;i++) {
+    for(int j=0;j<n;j++) {
+      int mem = -1;
+      if(G[i*n+j]!=0)
+        mem=(int)(log(G[i*n+j])/log(2.0));
+      if(mem>max_mem_x[i])
+        max_mem_x[i]=mem;
+      if(mem>max_mem)
+        max_mem=mem;
+    }
+  }
   
-  // generate the PS, PI tables for later use
-  for(int i=0;i<d_S;i++) {
-    int j=0;
-    for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
-      if(d_NS[ii*d_I+jj]!=i) continue;
-      d_PS[i*d_I+j]=ii;
-      d_PI[i*d_I+j]=jj;
-      j++;
+//printf("max_mem_x\n");
+//for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
+
+  // calculate total memory requirements to set S
+  int sum_max_mem = 0;
+  for(int i=0;i<k;i++)
+    sum_max_mem += max_mem_x[i];
+
+//printf("sum_max_mem = %d\n",sum_max_mem);
+
+  d_I=1<<k;
+  d_S=1<<sum_max_mem;
+  d_O=1<<n;
+ 
+  // binary representation of the G matrix
+  std::vector<std::vector<int> > Gb(k*n);
+  for(int j=0;j<k*n;j++) {
+    Gb[j].resize(max_mem+1);
+    dec2base(G[j],2,Gb[j]);
+//printf("Gb\n");
+//for(int m=0;m<Gb[j].size();m++) printf("%d ",Gb[j][m]); printf("\n");
+  }
+
+  // alphabet size of each shift register 
+  std::vector<int> bases_x(k);
+  for(int j=0;j<k ;j++) 
+    bases_x[j] = 1 << max_mem_x[j];
+//printf("bases_x\n");
+//for(int j=0;j<max_mem_x.size();j++) printf("%d ",max_mem_x[j]); printf("\n");
+
+  d_NS.resize(d_I*d_S);
+  d_OS.resize(d_I*d_S);
+
+  std::vector<int> sx(k);
+  std::vector<int> nsx(k);
+  std::vector<int> tx(k);
+  std::vector<std::vector<int> > tb(k);
+  for(int j=0;j<k;j++)
+    tb[j].resize(max_mem+1);
+  std::vector<int> inb(k);
+  std::vector<int> outb(n);
+
+
+  for(int s=0;s<d_S;s++) {
+    dec2bases(s,bases_x,sx); // split s into k values, each representing on of 
the k shift registers
+//printf("state = %d \nstates = ",s);
+//for(int j=0;j<sx.size();j++) printf("%d ",sx[j]); printf("\n");
+    for(int i=0;i<d_I;i++) {
+      dec2base(i,2,inb); // input in binary
+//printf("input = %d \ninputs = ",i);
+//for(int j=0;j<inb.size();j++) printf("%d ",inb[j]); printf("\n");
+
+      // evaluate next state
+      for(int j=0;j<k;j++)
+        nsx[j] = (inb[j]*bases_x[j]+sx[j])/2; // next state (for each shift 
register) MSB first
+      d_NS[s*d_I+i]=bases2dec(nsx,bases_x); // collect all values into the new 
state
+
+      // evaluate transitions
+      for(int j=0;j<k;j++)
+        tx[j] = inb[j]*bases_x[j]+sx[j]; // transition (for each shift 
register)MSB first
+      for(int j=0;j<k;j++) {
+        dec2base(tx[j],2,tb[j]); // transition in binary
+//printf("transition = %d \ntransitions = ",tx[j]);
+//for(int m=0;m<tb[j].size();m++) printf("%d ",tb[j][m]); printf("\n");
+      }
+
+      // evaluate outputs
+      for(int nn=0;nn<n;nn++) {
+        outb[nn] = 0;
+        for(int j=0;j<k;j++) {
+          for(int m=0;m<max_mem+1;m++)
+            outb[nn] = (outb[nn] + Gb[j*n+nn][m]*tb[j][m]) % 2; // careful: 
polynomial 1+D ir represented as 110, not as 011
+//printf("output %d equals %d\n",nn,outb[nn]);
+        }
+      }
+      d_OS[s*d_I+i] = base2dec(outb,2);
     }
   }
+
+  generate_PS_PI();
+  generate_TM();
 }
 
+
+
+
 //######################################################################
 //# Automatically generate an FSM specification describing the 
 //# ISI for a channel
@@ -125,8 +222,6 @@
 
   d_NS.resize(d_I*d_S);
   d_OS.resize(d_I*d_S);
-  d_PS.resize(d_I*d_S);
-  d_PI.resize(d_I*d_S);
 
   for(int s=0;s<d_S;s++) {
     for(int i=0;i<d_I;i++) { 
@@ -135,8 +230,20 @@
       d_OS[s*d_I+i] = t;
     }
   }
-  
-  // generate the PS, PI tables for later use
+ 
+  generate_PS_PI();
+  generate_TM();
+}
+
+
+//######################################################################
+//# generate the PS and PI tables for later use
+//######################################################################
+void fsm::generate_PS_PI()
+{
+  d_PS.resize(d_I*d_S);
+  d_PI.resize(d_I*d_S);
+
   for(int i=0;i<d_S;i++) {
     int j=0;
     for(int ii=0;ii<d_S;ii++) for(int jj=0;jj<d_I;jj++) {
@@ -147,3 +254,70 @@
     }
   }
 }
+
+
+//######################################################################
+//# generate the termination matrices TMl and TMi for later use
+//######################################################################
+void fsm::generate_TM()
+{
+  d_TMi.resize(d_S*d_S);
+  d_TMl.resize(d_S*d_S);
+
+  for(int i=0;i<d_S*d_S;i++) {
+    d_TMi[i] = -1; // no meaning
+    d_TMl[i] = d_S; //infinity: you need at most S-1 steps
+    if (i/d_S == i%d_S)
+      d_TMl[i] = 0;
+  }
+
+  for(int s=0;s<d_S;s++) {
+    bool done = false;
+    int attempts = 0;
+    while (done == false && attempts < d_S-1) {
+      done = find_es(s);
+      attempts ++;
+    }
+    if (done == false)
+      //throw std::runtime_error ("fsm::generate_TM(): FSM appears to be 
disconnected\n");
+      printf("fsm::generate_TM(): FSM appears to be disconnected\n");
+  }
+}
+
+
+// find a path from any state to the ending state "es"
+bool fsm::find_es(int es)
+{
+  bool done = true;
+  for(int s=0;s<d_S;s++) {
+    if(d_TMl[s*d_S+es] < d_S) 
+      continue;
+    int minl=d_S;
+    int mini=-1;
+    for(int i=0;i<d_I;i++) {
+      if( 1 + d_TMl[d_NS[s*d_I+i]*d_S+es] < minl) {
+        minl = 1 + d_TMl[d_NS[s*d_I+i]*d_S+es];
+        mini = i;
+      }
+    }
+    if (mini != -1) {
+      d_TMl[s*d_S+es]=minl;
+      d_TMi[s*d_S+es]=mini;
+    }
+    else
+      done = false;
+  }
+  return done;
+}
+
+
+
+
+
+
+
+
+
+
+
+

Modified: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.h
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.h   
2006-08-16 17:06:33 UTC (rev 3312)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.h   
2006-08-16 17:12:15 UTC (rev 3313)
@@ -37,11 +37,17 @@
   std::vector<int> d_OS;
   std::vector<int> d_PS;
   std::vector<int> d_PI;
+  std::vector<int> d_TMi;
+  std::vector<int> d_TMl;
+  void generate_PS_PI ();
+  void generate_TM ();
+  bool find_es(int es);
 public:
   fsm();
   fsm(const fsm &FSM);
   fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> 
&OS);
   fsm(const char *name);
+  fsm(int k, int n, const std::vector<int> &G);
   fsm(int mod_size, int ch_length);
   int I () const { return d_I; }
   int S () const { return d_S; }
@@ -50,6 +56,8 @@
   const std::vector<int> & OS () const { return d_OS; }
   const std::vector<int> & PS () const { return d_PS; }
   const std::vector<int> & PI () const { return d_PI; }
+  const std::vector<int> & TMi () const { return d_TMi; }
+  const std::vector<int> & TMl () const { return d_TMl; }
 };
 
 #endif

Modified: gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.i
===================================================================
--- gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.i   
2006-08-16 17:06:33 UTC (rev 3312)
+++ gnuradio/branches/developers/anastas/wip/gr-trellis/src/lib/fsm.i   
2006-08-16 17:12:15 UTC (rev 3313)
@@ -29,11 +29,16 @@
   std::vector<int> d_OS;
   std::vector<int> d_PS;
   std::vector<int> d_PI;
+  std::vector<int> d_TMi;
+  std::vector<int> d_TMl;
+  void generate_PS_PI ();
+  void generate_TM ();
 public:
   fsm();
   fsm(const fsm &FSM);
   fsm(int I, int S, int O, const std::vector<int> &NS, const std::vector<int> 
&OS);
   fsm(const char *name);
+  fsm(int k, int n, const std::vector<int> &G);
   fsm(int mod_size, int ch_length);
   int I () const { return d_I; }
   int S () const { return d_S; }
@@ -42,8 +47,7 @@
   const std::vector<int> & OS () const { return d_OS; }
   const std::vector<int> & PS () const { return d_PS; }
   const std::vector<int> & PI () const { return d_PI; }
+  const std::vector<int> & TMi () const { return d_TMi; }
+  const std::vector<int> & TMl () const { return d_TMl; }
 };
 
-
-
-