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

[Achilleas Anastasopoulos]

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/        
_______________________________________________________