+ 48 return (ntotal,ntotal-nright)
+</programlisting>
+
+</sect1>
+
+
+
+
+
+
+
+
+
+
+
+
+
+<!--=====================================================-->
+<sect1 id="isi"><title>Another Complete Example: Viterbi Equalization</title>
+
+<para>
+We now discuss through another concrete example how
+the above FSM model can be used in GNU Radio.
+
+The communication system that we want to simulate
+consists of a source generating the
+input information in packets, an ISI channel with
+additive white Gaussian noise (AWGN), and
+the VA performing MLSD.
+The program source is as follows.
+</para>
+
+&test_viterbi_equalization1_listing;
+
+<para>
+The program is called by
+<literallayout>
+./test_viterbi_equalization1.py Es/No_db repetitions
+</literallayout>
+where
+"Es/No_db" is the SNR in dB, and "repetitions"
+are the number of packets to be transmitted and received in order to
+collect sufficient number of errors for an accurate estimate of the
+error rate.
+</para>
+
+
+<para>
+Each packet has size Kb bits.
+The modulation is chosen to be 4-PAM in this example and the channel is chosen
+to be one of the test channels defined in fsm_utils.py
+</para>
+<programlisting>
+ 71 Kb=2048 # packet size in bits
+ 72 modulation = fsm_utils.pam4 # see fsm_utlis.py for available predefined modulations
+ 73 channel = fsm_utils.c_channel # see fsm_utlis.py for available predefined test channels
+</programlisting>
+
+<para>
+The FSM is instantiated in
+</para>
+<programlisting>
+ 74 f=trellis.fsm(len(modulation[1]),len(channel)) # generate the FSM automatically
+</programlisting>
+<para>
+and generated automatically given the channel length and the modulation size.
+Since in this example the channel has length 5 and the modulation is 4-ary, the corresponding FSM has 4<superscript>5-1</superscript>=256 states and
+4<superscript>5</superscript>=1024 outputs (see the documentation on FSM for more explanation).
+</para>
+
+<para>
+Assuming that the FSM input has cardinality I, each input symbol consists
+of bitspersymbol=log<subscript>2</subscript>( I ) bits, and thus correspond to K = Kb/bitspersymbol symbols.
+</para>
+<programlisting>
+ 75 bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
+ 76 K=Kb/bitspersymbol # packet size in trellis steps
+</programlisting>
+
+
+
+<para>
+The overall system with input the 4-ary input symbols
+x<subscript>k</subscript>, modulated to the
+4-PAM symbols s<subscript>k</subscript> and passed through the ISI channel to produce the
+noise-free observations
+z<subscript>k</subscript> =
+sum<subscript>j=0</subscript><superscript>L-1</superscript> c<subscript>j</subscript> s<subscript>k-j</subscript> (where L is the channel length)
+can be modeled as a FSM followed by a memoryless modulation.
+In particular, the FSM input is the sequence
+x<subscript>k</subscript>
+and its output is the "combined" symbol
+y<subscript>k</subscript>=
+(x<subscript>k</subscript>,x<subscript>k-1</subscript>,...,x<subscript>k-L+1</subscript>) (actually its decimal representation).
+The memoryless modulator maps every "combined" symbol
+y<subscript>k</subscript> to
+z<subscript>k</subscript> =
+sum<subscript>j=0</subscript><superscript>L-1</superscript> c<subscript>j</subscript> s<subscript>k-j</subscript>
+Clearly this modulation is memoryless since
+each z<subscript>k</subscript> depends only on y<subscript>k</subscript>; the memory inherent in the ISI is hidden in the FSM structure.
+This memoryless modulator is automatically generated by a helper function in
+fsm_utils.py given the channel and modulation as in line 78, and has the
+familiar format tot_channel=(dimensionality,tot_constellation) as described in the TCM example.
+This is exactly what the metrics block (or the viterbi_combined block) require in order to evaluate the VA metrics from the noisy observations.
+</para>
+<programlisting>
+ 78 tot_channel = fsm_utils.make_isi_lookup(modulation,channel,True) # generate the lookup table (normalize energy to 1)
+ 79 dimensionality = tot_channel[0]
+ 80 tot_constellation = tot_channel[1]
+ 81 N0=pow(10.0,-esn0_db/10.0); # noise variance
+ 82 if len(tot_constellation)/dimensionality != f.O():
+ 83 sys.stderr.write ('Incompatible FSM output cardinality and lookup table size.\n')
+ 84 sys.exit (1)
+</programlisting>
+
+
+
+<para>
+Then, "run_test" is called with a different "seed" so that we get
+different data and noise realizations.
+</para>
+<programlisting>
+ 91 (s,e)=run_test(f,Kb,bitspersymbol,K,channel,modulation,dimensionality,tot_constellation,N0,-long(666+i)) # run experiment with different seed to get different data and noise realizations
+</programlisting>
+
+
+
+<para>
+Let us examine now the "run_test" function.
+First we set up the transmitter blocks.
+We generate a packet of K random symbols and add a head and a tail of L zeros,
+L being the channel length. This is sufficient to drive the initial and final states to 0.
+</para>
+<programlisting>
+ 14 L = len(channel)
+ 15
+ 16 # TX
+ 17 # this for loop is TOO slow in python!!!
+ 18 packet = [0]*(K+2*L)
+ 19 random.seed(seed)
+ 20 for i in range(len(packet)):
+ 21 packet[i] = random.randint(0, 2**bitspersymbol - 1) # random symbols
+ 22 for i in range(L): # first/last L symbols set to 0
+ 23 packet[i] = 0
+ 24 packet[len(packet)-i-1] = 0
+ 25 src = gr.vector_source_s(packet,False)
+ 26 mod = gr.chunks_to_symbols_sf(modulation[1],modulation[0])
+</programlisting>
+
+
+<para>
+The modulated symbols are filtered by the ISI channel and AWGN with appropriate noise variance is added.
+</para>
+<programlisting>
+ 28 # CHANNEL
+ 29 isi = gr.fir_filter_fff(1,channel)
+ 30 add = gr.add_ff()
+ 31 noise = gr.noise_source_f(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
+</programlisting>
+
+
+
+<para>
+Since the output alphabet of the equivalent FSM is quite large (1024) we chose to utilize the combined metrics calculator and Viterbi algorithm block.
+also note that the first L observations are irrelevant and tus can be skipped.
+</para>
+<programlisting>
+ 33 # RX
+ 34 skip = gr.skiphead(gr.sizeof_float, L) # skip the first L samples since you know they are coming from the L zero symbols
+ 35 #metrics = trellis.metrics_f(f.O(),dimensionality,tot_constellation,trellis.TRELLIS_EUCLIDEAN) # data preprocessing to generate metrics for Viterbi
+ 36 #va = trellis.viterbi_s(f,K+L,0,0) # Put -1 if the Initial/Final states are not set.
+ 37 va = trellis.viterbi_combined_s(f,K+L,0,0,dimensionality,tot_constellation,trellis.TRELLIS_EUCLIDEAN) # using viterbi_combined_s instead of metrics_f/viterbi_s allows larger packet lengths because metrics_f is complaining for not being able to allocate large buffers. This is due to the large f.O() in this application...
+ 38 dst = gr.vector_sink_s()
+</programlisting>
+
+<para>
+Now the VA can run once it is supplied by the initial and final states.
+In this example both the initial and final states are set to 0.
+The VA outputs the estimates of the input symbols which
+are then compared with the transmitted sequence.
+</para>
+<programlisting>
+ 49 data = dst.data()
+ 50 ntotal = len(data) - L
+ 51 nright=0
+ 52 for i in range(ntotal):
+ 53 if packet[i+L]==data[i]:
+ 54 nright=nright+1
+ 55 #else:
+ 56 #print "Error in ", i
+</programlisting>
+
+
+<para>
+The function returns the number of symbols and the number of symbols in error. Observe that this way the estimated error rate refers to
+2-bit-symbol error rate.
+</para>
+<programlisting>
+ 58 return (ntotal,ntotal-nright)