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 @@ -We will now describe the implementation of the basic ingedient, the FSM. +We will now describe the implementation of the basic ingredient, the FSM. @@ -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); }; @@ -258,7 +260,7 @@ -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 = [gi,j]i=1:k, j=1:n, given as an one-dimensional STL vector. Each integer gi,j is the decimal representation of the polynomial gi,j(D) (e.g., gi,j= 6 = 1102 is interpreted as gi,j(D)=1+D) describing the connections from the sequence xi to @@ -272,7 +274,7 @@ -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) 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 sk, what are the possible previous states sk-1 +To do this we would like to know for a given state sk, +what are the possible previous states sk-1 and what input symbols xk-1 will get us from -sk-1 to sk. This information can be derived from NS; however we want to have it ready in a +sk-1 to sk. 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(sk,i) @@ -326,7 +333,21 @@ + +There are two public methods in the FSM class. + +void write_trellis_svg(std::string filename ,int number_stages); + +and + +void write_fsm_txt(std::string filename); + +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. + + @@ -351,12 +372,13 @@ The trellis.viterbi_X(FSM, K, S0, SK) 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. @@ -384,7 +406,7 @@ ||rk-ci||2 = sumj=1D |rk,j-ci,j|2 -for each of the O hypothesized ouput +for each of the O hypothesized output symbols ci = (ci,1,ci,2,...,ci,D) defined in the vector TABLE, where TABLE[i * D + j] = ci,j. @@ -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 -trellis.viterbi_combined_X( FSM, K, S0, SK, D, TABLE, TYPE) where the arguments are exactly those used in the aforementioned two blocks. +trellis.viterbi_combined_X( FSM, K, S0, SK, D, TABLE, TYPE) 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) @@ -484,7 +506,7 @@ -The FSM is first intantiated in "main" by +The FSM is first instantiated in "main" by 62 f=trellis.fsm(fname) # get the FSM specification from a file @@ -513,11 +535,11 @@ -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 @@ -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 #include #include - + static const float INF = 1.0e9; @SPTR_NAME@ @@ -40,14 +40,48 @@ int S0, int SK) { + const std::vector S0v(1,S0); + const std::vector SKv(1,SK); + return @SPTR_NAME@ (new @NAME@ (FSM,K,S0v,SKv)); +} + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + const std::vector &S0, + int SK) +{ + const std::vector SKv(1,SK); + return @SPTR_NAME@ (new @NAME@ (FSM,K,S0,SKv)); +} + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + int S0, + const std::vector &SK) +{ + const std::vector S0v(1,S0); + return @SPTR_NAME@ (new @NAME@ (FSM,K,S0v,SK)); +} + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + const std::vector &S0, + const std::vector &SK) +{ return @SPTR_NAME@ (new @NAME@ (FSM,K,S0,SK)); } @NAME@::@NAME@ ( const fsm &FSM, int K, - int S0, - int SK) + const std::vector &S0, + const std::vector &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 > &PS, const std::vector< std::vector > &PI, int K, - int S0,int SK, + const std::vector &S0,const std::vector &SK, const float *in, @TYPE@ *out)//, //std::vector &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=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@ address@hidden@ ( const fsm &FSM, int K, + const std::vector &S0, + const std::vector &SK); + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + const std::vector &S0, + int SK); + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, int S0, int SK); address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + int S0, + const std::vector &SK); + class @NAME@ : public gr_block { fsm d_FSM; int d_K; - int d_S0; - int d_SK; + std::vector d_S0; + std::vector d_SK; //std::vector d_trace; friend @SPTR_NAME@ address@hidden@ ( const fsm &FSM, int K, - int S0, + const std::vector &S0, + const std::vector &SK); + + friend @SPTR_NAME@ address@hidden@ ( + const fsm &FSM, + int K, + const std::vector &S0, int SK); + friend @SPTR_NAME@ address@hidden@ ( + const fsm &FSM, + int K, + int S0, + const std::vector &SK); - @NAME@ ( + friend @SPTR_NAME@ address@hidden@ ( const fsm &FSM, int K, int S0, int SK); + @NAME@ ( + const fsm &FSM, + int K, + const std::vector &S0, + const std::vector &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 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@ address@hidden@ ( - const fsm &FSM, + const fsm &FSM, int K, + const std::vector &S0, + const std::vector &SK); + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + const std::vector &S0, + int SK); + address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, int S0, int SK); address@hidden@ address@hidden@ ( + const fsm &FSM, + int K, + int S0, + const std::vector &SK); + class @NAME@ : public gr_block { private: @NAME@ ( const fsm &FSM, int K, - int S0, - int SK); + const std::vector &S0, + const std::vector &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 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) { }