[prev in list] [next in list] [prev in thread] [next in thread]
List: gnuradio-patch
Subject: [Patch-gnuradio] patch for gr_noise_source and previously submitted patch for gr_trellis
From: "Tim Meehan" <meehandsp () gmail ! com>
Date: 2007-03-16 12:42:36
Message-ID: 2c1129ca0703160542x36c3740fge982b685cfe3d2eb () mail ! gmail ! com
[Download RAW message or body]
Hello,
Please see attached patch for gr_noise_source and qa code. Also
included in this patch is previousle submitted patch for gr_trellis
and docs
Problem: gr_noise_source returns the same sequence for all positive
seeds. This is probably not the expected result and will likely lead
to confusion.
Reason: gr_noise_source calls function derived from well known ran1()
function that sets all positive value seeds to 1.
from gr_random.c gr_random::ran1()
...
if (d_seed <= 0 || !d_iy) {
if (-d_seed < 1)
d_seed=1;
proposed fix: Mod gr_noise_source to call gr_random with a negative
value if called with a positive seed.
Tim
["gr_trellis_and_gr_noise_source.patch" (text/x-patch)]
Index: gr-trellis/doc/gr-trellis.xml
===================================================================
--- gr-trellis/doc/gr-trellis.xml (revision 4763)
+++ gr-trellis/doc/gr-trellis.xml (working copy)
@@ -52,7 +52,7 @@
code (CC), a trellis code (TC), an inter-symbol interference (ISI)
channel, or any
other communication system that can be modeled with an FSM.
-To achieve this goal, we need to separate the pure FSM descrition from the
+To achieve this goal, we need to separate the pure FSM description from the
rest of the model details. For instance, in the case of a rate 2/3 TC,
the FSM should not involve details about the modulation used (it can
be an 8-ary PAM, or 8-PSK, etc). Similarly, when attempting maximum likelihood
@@ -64,7 +64,7 @@
</para>
<para>
-We will now describe the implementation of the basic ingedient, the FSM.
+We will now describe the implementation of the basic ingredient, the FSM.
</para>
</sect1>
@@ -176,8 +176,8 @@
int d_O;
std::vector<int> d_NS;
std::vector<int> d_OS;
- std::vector<int> d_PS;
- std::vector<int> d_PI;
+ std::vector< std::vector<int> > d_PS;
+ std::vector< std::vector<int> > d_PI;
std::vector<int> d_TMi;
std::vector<int> d_TMl;
void generate_PS_PI ();
@@ -199,6 +199,8 @@
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; }
+ void write_trellis_svg(std::string filename ,int number_stages);
+ void write_fsm_txt(std::string filename);
};
</programlisting>
@@ -258,7 +260,7 @@
<listitem>
<para>
-The third way is specific to FSMs representing binary (n,k) conolutional codes. \
These FSMs are specified by the number of input bits k, the number of output bits n, \
and the generator matrix, which is a k x n matrix of integers +The third way is \
specific to FSMs representing binary (n,k) convolutional codes. These FSMs are \
specified by the number of input bits k, the number of output bits n, and the \
generator matrix, which is a k x n matrix of integers G = \
[g<subscript>i,j</subscript>]<subscript>i=1:k, j=1:n</subscript>, given as an \
one-dimensional STL vector. Each integer g<subscript>i,j</subscript> is the decimal \
representation of the polynomial g<subscript>i,j</subscript>(D) (e.g., \
g<subscript>i,j</subscript>= 6 = 110<subscript>2</subscript> is interpreted as \
g<subscript>i,j</subscript>(D)=1+D) describing the connections from the sequence \
x<subscript>i</subscript> to @@ -272,7 +274,7 @@
<listitem>
<para>
-The fourth way is specific to FSMs resulting from shift registers, and the output \
symbol being the entire transition (ie, current_state and current_input). These FSMs \
are usefull when describibg ISI channels. In particular the state is comprised of the \
input symbols x(k-1), x(k-2),...,x(k-L), where L = ch_length-1 and each x(i) belongs \
to an alphabet of size mod_size. The output is taken to be x(k), x(k-1), \
x(k-2),...,x(k-L) (in decimal format) +The fourth way is specific to FSMs resulting \
from shift registers, and the output symbol being the entire transition (ie, \
current_state and current_input). These FSMs are useful when describing ISI channels. \
In particular the state is comprised of the input symbols x(k-1), x(k-2),...,x(k-L), \
where L = ch_length-1 and each x(i) belongs to an alphabet of size mod_size. The \
output is taken to be x(k), x(k-1), x(k-2),...,x(k-L) (in decimal format) </para>
<programlisting>
fsm(const int mod_size, const int ch_length);
@@ -289,14 +291,19 @@
when an FSM is instantiated and their meaning is as follows.
Sometimes (eg, in the traceback operation of the VA) we need
to trace the history of the state or the input sequence.
-To do this we would like to know for a given state s<subscript>k</subscript>, what \
are the possible previous states s<subscript>k-1</subscript> +To do this we would \
like to know for a given state s<subscript>k</subscript>, +what are the possible \
previous states s<subscript>k-1</subscript> and what input symbols \
x<subscript>k-1</subscript> will get us from
-s<subscript>k-1</subscript> to s<subscript>k</subscript>. This information can be \
derived from NS; however we want to have it ready in a +s<subscript>k-1</subscript> \
to s<subscript>k</subscript>. This information can be +derived from NS; however we \
want to have it ready in a convenient format.
In the following we assume that for any state,
the number of incoming transitions is the same as the number of
outgoing transitions, ie, equal to I. All applications of interest
-have FSMs satisfying this requirement.
+have FSMs satisfying this requirement. The algorithm has been
+modified to support the non standard trellis where the number of
+incoming transitions is not equal to the number of outgoing
+transitions.
If we arbitrarily index the incoming transitions to the current state
by "i", then as i goes from 0 to I-1, PS(s<subscript>k</subscript>,i)
@@ -326,7 +333,21 @@
</para>
+<para>
+There are two public methods in the FSM class.
+<programlisting>
+void write_trellis_svg(std::string filename ,int number_stages);
+</programlisting>
+and
+<programlisting>
+void write_fsm_txt(std::string filename);
+</programlisting>
+The first method writes out a graphical representation of the FSM as an SVG file. \
This file can be +viewed in any tool capable of reading an SVG file, such as \
Inkscape.
+The second method writes out on description in the same format that can be passed to \
the constructor. +</para>
+
</sect1>
@@ -351,12 +372,13 @@
<para>
The <methodname>trellis.viterbi_X(FSM, K, S0, SK)</methodname> block instantiates a \
Viterbi decoder for a sequence of K trellis steps generated by the given FSM and \
with initial and final states set to S0 and SK, respectively (S0 and/or SK are set to \
-1
-if the corresponding states are not fixed/known at the receiver side).
+if the corresponding states are not fixed/known at the receiver side). The method \
is overloaded such that S0 and SK may also be a a vector of +initial states and \
final states respectively. The output of this block is a sequence of K bytes, shorts \
or integers representing the estimated input (i.e., uncoded) sequence. The input is \
a sequence of K x FSM.O( ) floats, where the k x K + i float represents the cost \
associated with the k-th step in the trellis and the i-th FSM output.
-Observe that these inputs are generated externally and thus the Viterbi block is not \
informed of their meaning (they can be genarated as soft or hard inputs, etc); the \
only requirement is that they represent additive costs. +Observe that these inputs \
are generated externally and thus the Viterbi block is not informed of their meaning \
(they can be generated as soft or hard inputs, etc); the only requirement is that \
they represent additive costs. </para>
</sect2>
@@ -384,7 +406,7 @@
||r<subscript>k</subscript>-c<subscript>i</subscript>||<superscript>2</superscript> \
= sum<subscript>j=1</subscript><superscript>D</superscript> \
|r<subscript>k,j</subscript>-c<subscript>i,j</subscript>|<superscript>2</superscript> \
</para> <para>
-for each of the O hypothesized ouput
+for each of the O hypothesized output
symbols c<subscript>i</subscript> = \
(c<subscript>i,1</subscript>,c<subscript>i,2</subscript>,...,c<subscript>i,D</subscript>) \
defined in the vector TABLE, where TABLE[i * D + j] = c<subscript>i,j</subscript>.
</para></listitem>
@@ -437,12 +459,12 @@
Although the separation of metric calculation and Viterbi algorithm blocks
is consistent with our goal of providing general blocks that can be easily
reused, this separation might result in large input/output buffer sizes
-betwen blocks. Indeed for an FSM with a large output alphabet, the
+between blocks. Indeed for an FSM with a large output alphabet, the
output of the metric block/input of the Viterbi block is FSM.O( ) floats for
each trellis step. Sometimes this results in buffer overflow even for
moderate sequence lengths.
To overcome this problem we provide a block that incorporates the metric calculation \
and Viterbi algorithm into a single GNU Radio block, namely
-<methodname>trellis.viterbi_combined_X( FSM, K, S0, SK, D, TABLE, TYPE)</methodname> \
where the arguments are exactly those used in the aforementioned two blocks. \
+<methodname>trellis.viterbi_combined_X( FSM, K, S0, SK, D, TABLE, TYPE)</methodname> \
where the arguments are exactly those used in the aforementioned two blocks. NOTE: \
for this method S0 and SK must currently be integers (no vector support) </para>
</sect2>
@@ -484,7 +506,7 @@
</para>
<para>
-The FSM is first intantiated in "main" by
+The FSM is first instantiated in "main" by
</para>
<programlisting>
62 f=trellis.fsm(fname) # get the FSM specification from a file
@@ -513,11 +535,11 @@
<para>
-The FSM will produce K output symbols (remeber the FSM produces always one output \
symbol for each input symbol). Each of these symbols needs to be modulated. Since we \
are simulating the communication system, we need not simulate the actual waveforms. \
An M-ary, D-dimensional +The FSM will produce K output symbols (remember the FSM \
produces always one output symbol for each input symbol). Each of these symbols needs \
to be modulated. Since we are simulating the communication system, we need not \
simulate the actual waveforms. An M-ary, D-dimensional modulation is completely \
specified by a set of M, D-dimensional real vectors. In "fsm_utils.py" file we give a \
number of useful modulations with the following format: modulation = \
(D,constellation), where \
constellation=[c11,c12,...,c1D,c21,c22,...,c2D,...,cM1,cM2,...cMD]. The meaning of \
the above is that every constellation point c_i
-is an D-dimnsional vector c_i=(ci1,ci2,...,ciD)
+is an D-dimensional vector c_i=(ci1,ci2,...,ciD)
For instance, 4-ary PAM is represented as
(1,[-3, -1, 1, 3]), while QPSK is represented as
(2,[1, 0, 0, 1, 0, -1, -1, 0]). In our example we choose QPSK modulation.
@@ -915,7 +937,7 @@
<listitem>
<para>
-Although turbo decoding is rediculously slow in software,
+Although turbo decoding is ridiculously slow in software,
we can design it in principle. One question is, whether we should
use the encoder, and SISO blocks and connect them
through GNU radio or we should implement turbo-decoding
Index: gr-trellis/src/lib/trellis_viterbi_X.cc.t
===================================================================
--- gr-trellis/src/lib/trellis_viterbi_X.cc.t (revision 4763)
+++ gr-trellis/src/lib/trellis_viterbi_X.cc.t (working copy)
@@ -30,7 +30,7 @@
#include <gr_io_signature.h>
#include <assert.h>
#include <iostream>
-
+
static const float INF = 1.0e9;
@SPTR_NAME@
@@ -40,14 +40,48 @@
int S0,
int SK)
{
+ const std::vector<int> S0v(1,S0);
+ const std::vector<int> SKv(1,SK);
+ return @SPTR_NAME@ (new @NAME@ (FSM,K,S0v,SKv));
+}
+
+@SPTR_NAME@
+trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
+ int SK)
+{
+ const std::vector<int> SKv(1,SK);
+ return @SPTR_NAME@ (new @NAME@ (FSM,K,S0,SKv));
+}
+
+@SPTR_NAME@
+trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ int S0,
+ const std::vector<int> &SK)
+{
+ const std::vector<int> S0v(1,S0);
+ return @SPTR_NAME@ (new @NAME@ (FSM,K,S0v,SK));
+}
+
+@SPTR_NAME@
+trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
+ const std::vector<int> &SK)
+{
return @SPTR_NAME@ (new @NAME@ (FSM,K,S0,SK));
}
@NAME@::@NAME@ (
const fsm &FSM,
int K,
- int S0,
- int SK)
+ const std::vector<int> &S0,
+ const std::vector<int> &SK)
: gr_block ("@BASE_NAME@",
gr_make_io_signature (1, -1, sizeof (float)),
gr_make_io_signature (1, -1, sizeof (@TYPE@))),
@@ -82,7 +116,7 @@
const std::vector< std::vector<int> > &PS,
const std::vector< std::vector<int> > &PI,
int K,
- int S0,int SK,
+ const std::vector<int> &S0,const std::vector<int> &SK,
const float *in, @TYPE@ *out)//,
//std::vector<int> &trace)
{
@@ -94,12 +128,12 @@
int st;
- if(S0<0) { // initial state not specified
+ if(S0[0] <0) { // initial state not specified
for(int i=0;i<S;i++) alpha[0*S+i]=0;
}
else {
for(int i=0;i<S;i++) alpha[0*S+i]=INF;
- alpha[0*S+S0]=0.0;
+ for(unsigned int i=0;i<S0.size();i++) alpha[0*S+S0[i]]=0;
}
alphai=0;
@@ -122,7 +156,7 @@
alphai=(alphai+1)%2;
}
- if(SK<0) { // final state not specified
+ if(SK[0] < 0) { // final state not specified
minm=INF;
minmi=0;
for(int i=0;i<S;i++)
@@ -130,7 +164,11 @@
st=minmi;
}
else {
- st=SK;
+ minm=INF;
+ minmi=0;
+ for(unsigned int i=0;i<SK.size();i++)
+ if((mm=alpha[alphai*S+SK[i]])<minm) minm=mm,minmi=SK[i];
+ st=minmi;
}
for(int k=K-1;k>=0;k--) { // traceback
Index: gr-trellis/src/lib/trellis_viterbi_X.h.t
===================================================================
--- gr-trellis/src/lib/trellis_viterbi_X.h.t (revision 4763)
+++ gr-trellis/src/lib/trellis_viterbi_X.h.t (working copy)
@@ -34,38 +34,74 @@
@SPTR_NAME@ trellis_make_@BASE_NAME@ (
const fsm &FSM,
int K,
+ const std::vector<int> &S0,
+ const std::vector<int> &SK);
+
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
+ int SK);
+
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
int S0,
int SK);
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ int S0,
+ const std::vector<int> &SK);
+
class @NAME@ : public gr_block
{
fsm d_FSM;
int d_K;
- int d_S0;
- int d_SK;
+ std::vector<int> d_S0;
+ std::vector<int> d_SK;
//std::vector<int> d_trace;
friend @SPTR_NAME@ trellis_make_@BASE_NAME@ (
const fsm &FSM,
int K,
- int S0,
+ const std::vector<int> &S0,
+ const std::vector<int> &SK);
+
+ friend @SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
int SK);
+ friend @SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ int S0,
+ const std::vector<int> &SK);
- @NAME@ (
+ friend @SPTR_NAME@ trellis_make_@BASE_NAME@ (
const fsm &FSM,
int K,
int S0,
int SK);
+ @NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
+ const std::vector<int> &SK);
+
+
public:
fsm FSM () const { return d_FSM; }
int K () const { return d_K; }
- int S0 () const { return d_S0; }
- int SK () const { return d_SK; }
+ int S0 () const { return d_S0[0]; }
+ int SK () const { return d_SK[0]; }
//std::vector<int> trace () const { return d_trace; }
void forecast (int noutput_items,
gr_vector_int &ninput_items_required);
Index: gr-trellis/src/lib/trellis_viterbi_X.i.t
===================================================================
--- gr-trellis/src/lib/trellis_viterbi_X.i.t (revision 4763)
+++ gr-trellis/src/lib/trellis_viterbi_X.i.t (working copy)
@@ -25,25 +25,43 @@
GR_SWIG_BLOCK_MAGIC(trellis,@BASE_NAME@);
@SPTR_NAME@ trellis_make_@BASE_NAME@ (
- const fsm &FSM,
+ const fsm &FSM,
int K,
+ const std::vector<int> &S0,
+ const std::vector<int> &SK);
+
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ const std::vector<int> &S0,
+ int SK);
+
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
int S0,
int SK);
+@SPTR_NAME@ trellis_make_@BASE_NAME@ (
+ const fsm &FSM,
+ int K,
+ int S0,
+ const std::vector<int> &SK);
+
class @NAME@ : public gr_block
{
private:
@NAME@ (
const fsm &FSM,
int K,
- int S0,
- int SK);
+ const std::vector<int> &S0,
+ const std::vector<int> &SK);
public:
fsm FSM () const { return d_FSM; }
int K () const { return d_K; }
- int S0 () const { return d_S0; }
- int SK () const { return d_SK; }
+ int S0 () const { return d_S0[0]; }
+ int SK () const { return d_SK[0]; }
//std::vector<short> trace () const { return d_trace; }
};
Index: gnuradio-core/src/python/gnuradio/gr/qa_noise.py
===================================================================
--- gnuradio-core/src/python/gnuradio/gr/qa_noise.py (revision 4763)
+++ gnuradio-core/src/python/gnuradio/gr/qa_noise.py (working copy)
@@ -33,7 +33,21 @@
def test_001(self):
# Just confirm that we can instantiate a noise source
op = gr.noise_source_f(gr.GR_GAUSSIAN, 10, 10)
+ # now do a sanity check that two consecutive seeds do not generate the same \
sequence + noise = {}
+ head = {}
+ sink = {}
+ seeds = [-10, -9, -8, 4,5,6]
+ for ii in range(0,len(seeds)):
+ noise[ii] = gr.noise_source_f(gr.GR_GAUSSIAN, 10, seeds[ii]) # seeds of \
(-2,-1,0,1,2) + head[ii] = gr.head(gr.sizeof_float, 4)
+ sink[ii] = gr.vector_sink_f()
+ self.fg.connect(noise[ii],head[ii],sink[ii])
+ self.fg.run()
+ for ii in range(0,len(seeds)-1):
+ assert(sink[ii].data() != sink[ii+1].data())
+
if __name__ == '__main__':
gr_unittest.main ()
Index: gnuradio-core/src/lib/gengen/gr_noise_source_X.cc.t
===================================================================
--- gnuradio-core/src/lib/gengen/gr_noise_source_X.cc.t (revision 4763)
+++ gnuradio-core/src/lib/gengen/gr_noise_source_X.cc.t (working copy)
@@ -43,7 +43,8 @@
gr_make_io_signature (1, 1, sizeof (@TYPE@))),
d_type (type),
d_ampl (ampl),
- d_rng (seed)
+ // for ran1() positive values for seed all return same sequence
+ d_rng ((seed < 0)?seed:-seed)
{
}
[prev in list] [next in list] [prev in thread] [next in thread]
Configure |
About |
News |
Add a list |
Sponsored by KoreLogic