RE: [Discuss-gnuradio] How to decode the convolutional code, in the GRC

[intermilan]

Achilleas:
      Thanks for your last e-mail.That help me a lot.But there is another question about the value of the parameter symbol_table we set in the chunks_to_symbol block. After read the code and example,I think if we want to implement the TCM ,we should set the value follow the fsm_utlils.py. And if we just want to use the trellis_viterbi_combined block to decode the convolutional code,we can set any value we want to (should  follow the rules of the chunks_to_symbols block). Am I right about it?

inter.



> Date: Fri, 1 Apr 2011 09:59:46 -0400
> From: address@hidden
> To: address@hidden; address@hidden
> Subject: Re: [Discuss-gnuradio] How to decode the convolutional code, in the GRC
>
> The matrices PS and PI are documented in the fsm class and in the
> gr-trellis documentation: PS[s] is a vector of "previous states"
> that will result in state "s" and PI[s] is the corresponding vector of
> "input symbols" that will result in state "s" from a previous state.
> This is useful in the VA because you have this info precalculated (see
> the fsm.cc) and thus you don't need to do this backwards lookup every
> time in the VA execution--> saves time!
>
> The vector alpha is a temporary vector that holds the accumulated path
> metrics in the VA. You do not need to store ALL of them for a block of K
> steps, but only two of them and then alternate between the two: read
> from one/write to the other (this is what the variable alphai points to!)
>
> The function calc_metric(O, D, TABLE, &(in[k*D]), metric,TYPE)
> calculates the metrics required for the viterbi algorithm in each
> step: depending on the "TYPE" this can be Euclidean, Hamming etc.
> In the code, for every chunk of observation corresponding to step "k"
> in[k*D]...in[k*D+D-1]
> it evaluates the metric between this observation and EVERY possible
> output symbol of the trellis and puts the results in the vector
> "metric". Observe that there are "O" (this is a big o not a zero)
> possible output symbols for the fsm, and each one of them is translated
> to a signal through the D-dimensional lookup table TABLE, so :
> output symbol 0 will be translated (modulated) to TABLE[0]...TABLE[D-1]
> output symbol 1 will be translated (modulated) to TABLE[D]...TABLE[2D-1]
> ..
> output symbol O-1 will be translated (modulated) to
> TABLE[(O-1)D]...TABLE[OD-1]
>
> eg, in the case of euclidean metrics the calc_metric() will form O
> numbers, each being the euclidean distance between the input
> in[k*D]...in[k*D+D-1]
> and EACH of the translated signals:
> TABLE[0]...TABLE[D-1]
> TABLE[D]...TABLE[2D-1]
> ...
> TABLE[(O-1)D]...TABLE[OD-1]
>
> Regarding references, I am just implementing the standard (block)
> Viterbi algorithm...
>
> Achilleas
>
>
> On 4/1/2011 4:33 AM, intermilan wrote:
> > hi Achilleas:
> > I recently had read the code in the trellis_viterbi_combined_fb.cc want
> > to understand how you use the viterbi algorithm.But there is something
> > that I can not understand.
> > for(int k=0;k<K;k++) {
> > calc_metric(O, D, TABLE, &(in[k*D]), metric,TYPE); // calc metrics
> > norm=INF;
> > for(int j=0;j<S;j++) { // for each next state do ACS
> > minm=INF;
> > minmi=0;
> > for(unsigned int i=0;i<PS[j].size();i++) {
> > //int i0 = j*I+i;
> > if((mm=alpha[alphai*S+PS[j][i]]+metric[OS[PS[j][i]*I+PI[j][i]]])<! ;minm)
> > minm=mm,minmi=i;
> > }
> > trace[k*S+j]=minmi;
> > alpha[((alphai+1)%2)*S+j]=minm;
> > if(minm<norm) norm=minm;
> > }
> > for(int j=0;j<S;j++)
> > alpha[((alphai+1)%2)*S+j]-=norm; // normalize total metrics so they do
> > not explode
> > alphai=(alphai+1)%2;
> > }
> > I think above code perform the Add-Compare-Select operations.
> > I do not understand is the function of the matrix metric.I saw the code
> > in the calc_metric.cc,it is calculate the ! euclidean between
> > the data output the chunks_to_symbols block and the point in the
> > symbol_table.So what is the function of this metric in your viterbi
> > algorithm?
> > Besides,what is the function of the PS and PI which is generated by the
> > fsm file? and what is the function of the alpah[] in your code?
> > Is there some reference when you write these codes.if there is some
> > ,please tell me.I appreciate your hlep.
> > Thanks.
> >
> >
> > > Date: Mon, 14 Mar 2011 10:11:44 -0400
> > > From: address@hidden
> > > To: address@hidden; address@hidden
> > > Subject: Re: [Discuss-gnuradio] How to decode the convolutional code,
> > in the GRC
> > >
> > > inter,
> > >
> > > as i said in my previous email, you just have to consider the equivalent
> > > channel (the fact that it is noiseless is irrelevant in this discussion)
> > > from the output of the FSM encoder to the input of the VA.
> > > It seems you prefer to call it equivalent "modulato! r"; that's fine!
> > > Once you realize what this equivalent channel/modulator is
> > > (what is its input/output alphabet and what kind of symbols it
> > > inputs/outputs) then it will be strainghtforward to see what the viterbi
> > > decoder block should look like.
> > > If I were to guess from your description, i would say that your
> > > equivallent channel
> > > has input/output alphabet equal to the output alphabet of the FSM.
> > > Its input is a coded symbol from the FSM encoder and its output is also
> > > such a symbol from the packet decoder.
> > > So all you need is to do VA with symbol-wise hamming distance as your
> > > metric. You can achieve that using the viterbi_combined block with
> > > a trivial 1-D chunks to symbols block (identity) and the appropriate
> > > parameter for the metric_type.
> > >
> > >
> > > Achilleas
> > >
> > > On 3/14/2011 6:45 AM, intermilan wrote:
> > > > Achilleas:
> > > >
> > > &g! t; What I want to do is want to see the BER when the
> > convolutional code is
> > > > used in different modulator in the GRC,but I had not put the noise
> > > > source in the flow graph so there is no noise between the modulator
> > and
> > > > demodulator.
> > > > Besides,in my opinion, we can consider the packet_encoder and
> > > > packet_decoder block is part of the modulation.In other words,in the
> > > > flow graph I mentioned ,the data input the packet_encoder is the
> > same as
> > > > the packet_decoder block(because I did not put the noise block between
> > > > the modulator and demodulator ).
> > > > But I still not understand how to set the parameters in the viterbi
> > > > block in this case, particularly the parameter constellation if I
> > do not
> > > > use the chunks_to_symbols block.
> > > > Thanks for your help.
> > > >
> > > > inter
> > > >
> > > > > Date: Fri, 11 Mar 2011 17:33:25 -0500
> > > > > From: address@hidden
> > > > &g! t; To: address@hidden; di! address@hidden
> > > > > Subject: RE: [Discuss-gnuradio] How to decode the convolutional
> > code,
> > > > in the GRC
> > > > >
> > > > >
> > > > > inter,
> > > > >
> > > > > think of whatever is AFTER the trellis encoder and BEFORE the viterbi
> > > > > decoder as an equivalent channel.
> > > > >
> > > > > What is the equivalent channel in your case?
> > > > > What is its input alphabet? what is its output alphabet?
> > > > >
> > > > > From your description, it seems that the input alphabet is the
> > same as
> > > > > the output alphabet of your FSM.
> > > > >
> > > > > I am not familiar with the block "packet decoder" so i don't know
> > what
> > > > > it outputs, but whatever it is it should be the output alphabet
> > of your
> > > > > "equivalent" channel.
> > > > >
> > > >! ; > Once you figure out these things it will be straightforward to
> > see what
> > > > > the viterbi block should be...
> > > > > If you gather these pieces of information and still don't see how to
> > > > > implement the viterbi decoder let me know ! and i will provide
> > > > further help.
> > > > >
> > > > > Achilleas
> > >
> > > --
> > > _______________________________________________________
> > > Achilleas Anastasopoulos
> > > Associate Professor
> > > EECS Department Voice : (734)615-4024
> > > UNIVERSITY OF MICHIGAN Fax : (734)763-8041
> > > Ann Arbor, MI 48109-2122 E-mail: address@hidden
> > > URL: http://www.eecs.umich.edu/~anastas/
> > > _______________________________________________________
>
> --
> _______________________________________________________
> Achilleas Anastasopoulos
> Associate Professor
> EECS Department Voice : (734)615-4024
> UNIVERSITY OF MICHIGAN Fax : (734)763-8041
> Ann Arbor, MI 48109-2122 E-mail: address@hidden
> URL: http://www.eecs.umich.edu/~anastas/
> _______________________________________________________