git.gag.com Git - debian/gnuradio/blob - gr-trellis/doc/gr-trellis.html

   1 <html><head><meta http-equiv="Content-Type" content="text/html; charset=ISO-8859-1"><title>Trellis-based algorithms for GNU Radio</title><meta name="generator" content="DocBook XSL Stylesheets V1.65.1"><meta name="description" content="This document provides a description of the
   2 Finite State Machine (FSM) implementation and the related
   3 trellis-based encoding and decoding algorithms
   4 for GNU Radio.
   5 "></head><body bgcolor="white" text="black" link="#0000FF" vlink="#840084" alink="#0000FF"><div class="article" lang="en"><div class="titlepage"><div><div><h1 class="title"><a name="id2931733"></a>Trellis-based algorithms for GNU Radio</h1></div><div><div class="author"><h3 class="author"><span class="firstname">Achilleas</span> <span class="surname">Anastasopoulos</span></h3><div class="affiliation"><div class="address"><p><br>
   6            <tt class="email">&lt;<a href="mailto:anastas@umich.edu">anastas@umich.edu</a>&gt;</tt><br>
   7         </p></div></div></div></div><div><div class="revhistory"><table border="1" width="100%" summary="Revision history"><tr><th align="left" valign="top" colspan="2"><b>Revision History</b></th></tr><tr><td align="left">Revision v0.0</td><td align="left">2006-08-03</td></tr><tr><td align="left" colspan="2">
   8     First cut.
   9   </td></tr></table></div></div><div><div class="abstract"><p class="title"><b>Abstract</b></p><p>This document provides a description of the
  10 Finite State Machine (FSM) implementation and the related
  11 trellis-based encoding and decoding algorithms
  12 for GNU Radio.
  13 </p></div></div></div><div></div><hr></div><div class="toc"><p><b>Table of Contents</b></p><dl><dt><span class="sect1"><a href="#intro">Introduction</a></span></dt><dt><span class="sect1"><a href="#fsm">The FSM class</a></span></dt><dt><span class="sect1"><a href="#tcm">TCM: A Complete Example</a></span></dt><dt><span class="sect1"><a href="#future">Future Work</a></span></dt></dl></div><div class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="intro"></a>Introduction</h2></div></div><div></div></div><p>....</p><p>
  14 The basic goal of the implementation is to have a generic way of
  15 describing an FSM that is decoupled from whether it describes a
  16 convolutional
  17 code (CC), a trellis code (TC), an inter-symbol interference (ISI)
  18 channel, or any
  19 other communication system that can be modeled with an FSM.
  20 To achieve this goal, we need to separate the pure FSM descrition from the
  21 rest of the model details. For instance, in the case of a rate 2/3 TC,
  22 the FSM should not involve details about the modulation used (it can
  23 be an 8-ary PAM, or 8-PSK, etc). Similarly, when attempting maximum likelihood
  24 sequence detection (MLSD)--using for instance the Viterbi algorithm (VA)--
  25 the VA implementation should not be concerned with the channel details
  26 (such as modulations, channel type, hard or soft inputs, etc).
  27 Clearly, having generality as the primary goal implies some penalty
  28 on the code efficiency, as compared to fully custom implementations.
  29 </p><p>
  30 We will now describe the implementation of the basic ingedient, the FSM.
  31 </p></div><div class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="fsm"></a>The FSM class</h2></div></div><div></div></div><p>An FSM describes the evolution of a system with inputs
  32 x<sub>k</sub>, states s<sub>k</sub> and outputs y<sub>k</sub>. At time k the FSM state is s<sub>k</sub>.
  33 Upon reception of a new input symbol x<sub>k</sub>, it outputs an output symbol
  34 y<sub>k</sub> which is a function of both x<sub>k</sub> and s<sub>k</sub>.
  35 It will then move to a next state s<sub>k+1</sub>.
  36 An FSM has a finite number of states, input and output symbols.
  37 All these are formally described as follows:
  38 </p><div class="itemizedlist"><ul type="disc"><li><p>The input alphabet A<sub>I</sub>={0,1,2,...,I-1}, with cardinality I, so that x<sub>k</sub> takes values in A<sub>I</sub>.</p></li><li><p>The state alphabet A<sub>S</sub>={0,1,2,...,S-1}, with cardinality S, so that s<sub>k</sub> takes values in A<sub>S</sub>.</p></li><li><p>The output alphabet A<sub>O</sub>={0,1,2,...,O-1}, with cardinality O, so that y<sub>k</sub> takes values in A<sub>O</sub></p></li><li><p>The "next-state" function NS: A<sub>S</sub> x A<sub>I</sub> --&gt; A<sub>S</sub>,
  39 with the meaning
  40 s<sub>k+1</sub> = NS(s<sub>k</sub>, x<sub>k</sub>)</p></li><li><p>The "output-symbol" function OS: A<sub>S</sub> x A<sub>I</sub> --&gt; A<sub>S</sub>,
  41 with the meaning
  42 y<sub>k</sub> = OS(s<sub>k</sub>, x<sub>k</sub>)</p></li></ul></div><p>
  43 Thus, a complete description of the FSM is given by the
  44 the five-tuple (I,S,O,NS,OS).
  45 Observe that implementation details are hidden
  46 in how the outside world interprets these input and output
  47 integer symbols.
  48 Here is an example of an FSM describing the (2,1) CC
  49 with constraint length 3 and generator polynomial matrix
  50 (1+D+D<sup>2</sup>   1+D<sup>2</sup>)
  51 from Proakis-Salehi pg. 779.
  52 </p><div class="example"><a name="cc_ex"></a><p class="title"><b>Example 1. (2,1) CC with generator polynomials (1+D+D<sup>2</sup>   1+D<sup>2</sup>)</b></p><p>
  53 This CC accepts 1 bit at a time, and outputs 2 bits at a time.
  54 It has a shift register storing the last two input bits.
  55 In particular,
  56 b<sub>k</sub>(0)=x<sub>k</sub>+
  57 x<sub>k-1</sub>+x<sub>k-2</sub>, and
  58 b<sub>k</sub>(1)=x<sub>k</sub>+
  59 x<sub>k-2</sub>, where addition is mod-2.
  60 We can represent the state of this system
  61 as s<sub>k</sub> = (x<sub>k-1</sub> x<sub>k-2</sub>)<sub>10</sub>. In addition we can represent its
  62 output symbol as y<sub>k</sub> = (b<sub>k</sub>(1) b<sub>k</sub>(0))<sub>10</sub>.
  63 Based on the above assumptions, the input alphabet A<sub>I</sub>={0,1}, so I=2;
  64 the state alphabet A<sub>S</sub>={0,1,2,3}, so S=4; and
  65 the output alphabet A<sub>O</sub>={0,1,2,3}, so O=4.
  66 The "next-state" function NS(,) is given by
  67 </p><pre class="programlisting">
  68 s<sub>k</sub>   x<sub>k</sub>   s<sub>k+1</sub>
  69 0       0       0
  70 0       1       2
  71 1       0       0
  72 1       1       2
  73 2       0       1
  74 2       1       3
  75 3       0       1
  76 3       1       3
  77 </pre><p>
  78 The "output-symbol" function OS(,) can be given by
  79 </p><pre class="programlisting">
  80 s<sub>k</sub>       x<sub>k</sub>       y<sub>k</sub>
  81 0       0       0
  82 0       1       3
  83 1       0       3
  84 1       1       0
  85 2       0       1
  86 2       1       2
  87 3       0       2
  88 3       1       1
  89 </pre><p>
  90 </p><p>
  91 Note that although the CC outputs 2 bits per time period, following
  92 our approach, there is only one (quaternary) output symbol per
  93 time period (for instance, here we use the decimal representation
  94 of the 2-bits). Also note that the modulation used is not part of
  95 the FSM description: it can be BPSK, OOK, BFSK, QPSK with or without Gray mapping, etc;
  96 it is up to the rest of the program to interpret the meaning of
  97 the symbol y<sub>k</sub>.
  98 </p></div><p>
  99 The C++ implementation of the FSM class keeps private information about
 100 I,S,O,NS,OS and public methods to read and write them. The NS
 101 and OS matrices are implemented as STL 1-dimensional vectors.
 102 </p><pre class="programlisting">
 103 class fsm {
 104 private:
 105   int d_I;
 106   int d_S;
 107   int d_O;
 108   std::vector&lt;int&gt; d_NS;
 109   std::vector&lt;int&gt; d_OS;
 110   std::vector&lt;int&gt; d_PS;
 111   std::vector&lt;int&gt; d_PI;
 112 public:
 113   fsm();
 114   fsm(const fsm &amp;FSM);
 115   fsm(const int I, const int S, const int O, const std::vector&lt;int&gt; &amp;NS, const std::vector&lt;int&gt; &amp;OS);
 116   fsm(const char *name);
 117   fsm(const int mod_size, const int ch_length);
 118   int I () const { return d_I; }
 119   int S () const { return d_S; }
 120   int O () const { return d_O; }
 121   const std::vector&lt;int&gt; &amp; NS () const { return d_NS; }
 122   const std::vector&lt;int&gt; &amp; OS () const { return d_OS; }
 123   const std::vector&lt;int&gt; &amp; PS () const { return d_PS; }
 124   const std::vector&lt;int&gt; &amp; PI () const { return d_PI; }
 125 };
 126 </pre><p>
 127 As can be seen, other than the trivial and the copy constructor,
 128 there are three additional
 129 ways to construct an FSM.
 130 </p><div class="itemizedlist"><ul type="disc"><li><p>Supplying the parameters I,S,O,NS,OS:</p><pre class="programlisting">
 131   fsm(const int I, const int S, const int O, const std::vector&lt;int&gt; &amp;NS, const std::vector&lt;int&gt; &amp;OS);
 132 </pre></li><li><p>Giving a filename containing all the FSM information:</p><pre class="programlisting">
 133   fsm(const char *name);
 134 </pre><p>This information has to be in the following format</p><pre class="programlisting">
 135 I S O
 136
 137 NS(0,0)   NS(0,1)   ...  NS(0,I-1)
 138 NS(1,0)   NS(1,1)   ...  NS(1,I-1)
 139 ...
 140 NS(S-1,0) NS(S-1,1) ...  NS(S-1,I-1)
 141
 142 OS(0,0)   OS(0,1)   ...  OS(0,I-1)
 143 OS(1,0)   OS(1,1)   ...  OS(1,I-1)
 144 ...
 145 OS(S-1,0) OS(S-1,1) ... OS(S-1,I-1)
 146 </pre><p>For instance, the file containing the information for the example mentioned above is of the form</p><pre class="programlisting">
 147 2 4 4
 148
 149 0 2
 150 0 2
 151 1 3
 152 1 3
 153
 154 0 3
 155 3 0
 156 1 2
 157 2 1
 158 </pre></li><li><p>The third 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.....
 159 </p><pre class="programlisting">
 160   fsm(const int mod_size, const int ch_length);
 161 </pre></li></ul></div><p>
 162 Finally, as can be seen from the above description, there are
 163 two more variables included in the FSM class implementation,
 164 the PS and the PI matrices. These are computed internally
 165 when an FSM is instantiated and their meaning is as follows.
 166 Sometimes (eg, in the traceback operation of the VA) we need
 167 to trace the history of the state or the input sequence.
 168 To do this we would like to know for a given state s<sub>k</sub>, what are the possible previous states s<sub>k-1</sub>
 169 and what input symbols x<sub>k-1</sub> will get us from
 170 s<sub>k-1</sub> to s<sub>k</sub>. This information can be derived from NS; however we want to have it ready in a
 171 convenient format.
 172 In the following we assume that for any state,
 173 the number of incoming transitions is the same as the number of
 174 outgoing transitions, ie, equal to I. All applications of interest
 175 have FSMs satisfying this requirement.
 176
 177 If we arbitrarily index the incoming transitions to the current state
 178 by "i", then  as i goes from 0 to I-1, PS(s<sub>k</sub>,i)
 179 gives all previous states s<sub>k-1</sub>,
 180 and PI(s<sub>k</sub>,i) gives all previous inputs x<sub>k-1</sub>.
 181 In other words, for any given s<sub>k</sub> and any index i=0,1,...I-1, starting from
 182 s<sub>k-1</sub>=PS(s<sub>k</sub>,i)
 183 with input
 184 x<sub>k-1</sub>=PI(s<sub>k</sub>,i)
 185 will get us to the state s<sub>k</sub>.
 186 More formally, for any i=0,1,...I-1 we have
 187 s<sub>k</sub> = NS(PS(s<sub>k</sub>,i),PI(s<sub>k</sub>,i)).
 188
 189 </p></div><div class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="tcm"></a>TCM: A Complete Example</h2></div></div><div></div></div><p>
 190 We now discuss through a concrete example how
 191 the above FSM model can be used in GNU Radio.
 192
 193 The communication system that we want to simulate
 194 consists of a source generating the
 195 input information in packets, a CC encoding each packet separately,
 196 a memoryless modulator,
 197 an additive white Gaussian noise (AWGN) channel, and
 198 the VA performing MLSD.
 199 The program source is as follows.
 200 </p><pre class="programlisting">
 201 #!/usr/bin/env python
 202
 203 from gnuradio import gr
 204 from gnuradio import audio
 205 from gnuradio import trellis
 206 from gnuradio import eng_notation
 207 import math
 208 import sys
 209 import random
 210 import fsm_utils
 211
 212 def run_test (f,Kb,bitspersymbol,K,dimensionality,constellation,N0,seed):
 213     fg = gr.flow_graph ()
 214
 215
 216     # TX
 217     src = gr.lfsr_32k_source_s()
 218     src_head = gr.head (gr.sizeof_short,Kb/16) # packet size in shorts
 219     s2fsmi = gr.packed_to_unpacked_ss(bitspersymbol,gr.GR_MSB_FIRST) # unpack shorts to symbols compatible with the FSM input cardinality
 220     enc = trellis.encoder_ss(f,0) # initial state = 0
 221     mod = gr.chunks_to_symbols_sf(constellation,dimensionality)
 222
 223
 224     # CHANNEL
 225     add = gr.add_ff()
 226     noise = gr.noise_source_f(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
 227
 228
 229     # RX
 230     metrics = trellis.metrics_f(f.O(),dimensionality,constellation,trellis.TRELLIS_EUCLIDEAN) # data preprocessing to generate metrics for Viterbi
 231     va = trellis.viterbi_s(f,K,0,-1) # Put -1 if the Initial/Final states are not set.
 232     fsmi2s = gr.unpacked_to_packed_ss(bitspersymbol,gr.GR_MSB_FIRST) # pack FSM input symbols to shorts
 233     dst = gr.check_lfsr_32k_s();
 234
 235
 236     fg.connect (src,src_head,s2fsmi,enc,mod)
 237     fg.connect (mod,(add,0))
 238     fg.connect (noise,(add,1))
 239     fg.connect (add,metrics)
 240     fg.connect (metrics,va,fsmi2s,dst)
 241
 242
 243     fg.run()
 244
 245     # A bit of cheating: run the program once and print the
 246     # final encoder state..
 247     # Then put it as the last argument in the viterbi block
 248     #print "final state = " , enc.ST()
 249
 250     ntotal = dst.ntotal ()
 251     nright = dst.nright ()
 252     runlength = dst.runlength ()
 253     return (ntotal,ntotal-nright)
 254
 255
 256
 257
 258 def main(args):
 259     nargs = len (args)
 260     if nargs == 3:
 261         fname=args[0]
 262         esn0_db=float(args[1]) # Es/No in dB
 263         rep=int(args[2]) # number of times the experiment is run to collect enough errors
 264     else:
 265         sys.stderr.write ('usage: test_tcm.py fsm_fname Es/No_db  repetitions\n')
 266         sys.exit (1)
 267
 268     # system parameters
 269     f=trellis.fsm(fname) # get the FSM specification from a file (will hopefully be automated in the future...)
 270     Kb=1024*16  # packet size in bits (make it multiple of 16 so it can be packed in a short)
 271     bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
 272     K=Kb/bitspersymbol # packet size in trellis steps
 273     modulation = fsm_utils.psk4 # see fsm_utlis.py for available predefined modulations
 274     dimensionality = modulation[0]
 275     constellation = modulation[1]
 276     if len(constellation)/dimensionality != f.O():
 277         sys.stderr.write ('Incompatible FSM output cardinality and modulation size.\n')
 278         sys.exit (1)
 279     # calculate average symbol energy
 280     Es = 0
 281     for i in range(len(constellation)):
 282         Es = Es + constellation[i]**2
 283     Es = Es / (len(constellation)/dimensionality)
 284     N0=Es/pow(10.0,esn0_db/10.0); # noise variance
 285
 286
 287
 288     tot_s=0
 289     terr_s=0
 290     for i in range(rep):
 291         (s,e)=run_test(f,Kb,bitspersymbol,K,dimensionality,constellation,N0,-long(666+i)) # run experiment with different seed to get different noise realizations
 292         tot_s=tot_s+s
 293         terr_s=terr_s+e
 294         if (i%100==0):
 295             print i,s,e,tot_s,terr_s, '%e' % ((1.0*terr_s)/tot_s)
 296     # estimate of the (short) error rate
 297     print tot_s,terr_s, '%e' % ((1.0*terr_s)/tot_s)
 298
 299
 300 if __name__ == '__main__':
 301     main (sys.argv[1:])
 302 </pre><p>
 303 The program is called by
 304 </p><pre class="programlisting">
 305 ./test_tcm.py fsm_fname Es/No_db repetitions
 306 </pre><p>
 307 where "fsm_fname" is the file containing the FSM specification of the
 308 tested TCM code, "Es/No_db" is the SNR in dB, and "repetitions"
 309 are the number of packets to be transmitted and received in order to
 310 collect sufficient number of errors for an accurate estimate of the
 311 error rate.
 312 </p><p>
 313 The FSM is first intantiated in "main" by
 314 </p><pre class="programlisting">
 315     f=trellis.fsm(fname)
 316 </pre><p>
 317 Each packet has size Kb bits
 318 (we choose Kb to be a multiple of 16 so that all bits fit nicely into shorts and can be generated by the lfsr GNU Radio).
 319 Assuming that the FSM input has cardinality I, each input symbol consists
 320 of bitspersymbol=log<sub>2</sub>( I ). The Kb/16 shorts are now
 321 unpacked to K=Kb/bitspersymbol input
 322 symbols that will drive the FSM encoder.
 323 </p><pre class="programlisting">
 324     Kb=1024*16  # packet size in bits (make it multiple of 16 so it can be packed in a short)
 325     bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
 326     K=Kb/bitspersymbol # packet size in trellis steps
 327 </pre><p>
 328 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, N-dimensional
 329 modulation is completely specified by a set of M, N-dimensional real vectors. In "fsm_utils.py" file we give a number of useful modulations with the following format: modulation = (N,constellation), where
 330 constellation=[c11,c12,...,c1N,c21,c22,...,c2N,...,cM1,cM2,...cMN].
 331 The meaning of the above is that every constellation point c_i
 332 is an N-dimnsional vector c_i=(ci1,ci2,...,ciN)
 333 For instance, 4-ary PAM is represented as
 334 (1,[-3, -1, 1, 3]), while QPSK is represented as
 335 (2,[1, 0, 0, 1, 0, -1, -1, 0]). In our example we choose QPSK modulation.
 336 Clearly, M should be equal to the cardinality of the FSM output, O.
 337 Finally the average symbol energy and noise variance are calculated.
 338 </p><pre class="programlisting">
 339     modulation = fsm_utils.psk4 # see fsm_utlis.py for available predefined modulations
 340     dimensionality = modulation[0]
 341     constellation = modulation[1]
 342     if len(constellation)/dimensionality != f.O():
 343         sys.stderr.write ('Incompatible FSM output cardinality and modulation size.\n')
 344         sys.exit (1)
 345     # calculate average symbol energy
 346     Es = 0
 347     for i in range(len(constellation)):
 348         Es = Es + constellation[i]**2
 349     Es = Es / (len(constellation)/dimensionality)
 350     N0=Es/pow(10.0,esn0_db/10.0); # noise variance
 351 </pre><p>
 352 Then, "run_test" is called with a different "seed" so that we get
 353 different noise realizations.
 354 </p><pre class="programlisting">
 355         (s,e)=run_test(f,Kb,bitspersymbol,K,dimensionality,constellation,N0,-long(666+i)) # run experiment with different seed to get different noise realizations
 356 </pre><p>
 357 Let us examine now the "run_test" function.
 358 First we set up the transmitter blocks.
 359 The Kb/16 shorts are first unpacked to
 360 symbols consistent with the FSM input alphabet.
 361 The FSm encoder requires the FSM specification,
 362 and an initial state (which is set to 0 in this example).
 363 </p><pre class="programlisting">
 364     # TX
 365     src = gr.lfsr_32k_source_s()
 366     src_head = gr.head (gr.sizeof_short,Kb/16) # packet size in shorts
 367     s2fsmi = gr.packed_to_unpacked_ss(bitspersymbol,gr.GR_MSB_FIRST) # unpack shorts to symbols compatible with the FSM input cardinality
 368     enc = trellis.encoder_ss(f,0) # initial state = 0
 369 </pre><p>
 370 The "chunks_to_symbols_sf" is essentially a memoryless mapper which
 371 for each input symbol y_k
 372 outputs a sequence of N numbers ci1,ci2,...,ciN  representing the
 373 coordianates of the constellation symbol c_i with i=y_k.
 374 </p><pre class="programlisting">
 375     mod = gr.chunks_to_symbols_sf(constellation,dimensionality)
 376 </pre><p>
 377 The channel is AWGN with appropriate noise variance.
 378 For each transmitted symbol c_k=(ck1,ck2,...,ckN) we receive a noisy version
 379 r_k=(rk1,rk2,...,rkN).
 380 </p><pre class="programlisting">
 381     add = gr.add_ff()
 382     noise = gr.noise_source_f(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
 383 </pre><p>
 384 Part of the design methodology was to decouple the FSM and VA from
 385 the details of the modulation, channel, receiver front-end etc.
 386 In order for the VA to run, we only need to provide it with
 387 a number representing a cost associated with each transition
 388 in the trellis. Then the VA will find the sequence with
 389 the smallest total cost through the trellis.
 390 The cost associated with a transition (s_k,x_k) is only a function
 391 of the output y_k = OS(s_k,x_k), and the observation
 392 vector r_k. Thus, for each time period, k,
 393 we need to label each of the SxI transitions with such a cost.
 394 This means that for each time period we need to evaluate
 395 O such numbers (one for each possible output symbol y_k).
 396 This is done
 397 in "metrics_f". In particular, metrics_f is a memoryless device
 398 taking N inputs at a time and producing O outputs. The N inputs are
 399 rk1,rk2,...,rkN.
 400 The O outputs
 401 are the costs associated with observations rk1,rk2,...,rkN and
 402 hypothesized output symbols c_1,c_2,...,c_M. For instance,
 403 if we choose to perform soft-input VA, we need to evaluate
 404 the Euclidean distance between r_k and each of c_1,c_2,...,c_M,
 405 for each of the K transmitted symbols.
 406 Other options are available as well; for instance, we can
 407 do hard decision demodulation and feed the VA with
 408 symbol Hamming distances, or even bit Hamming distances, etc.
 409 These are all implemented in "metrics_f".
 410 </p><pre class="programlisting">
 411     # RX
 412     metrics = trellis.metrics_f(f.O(),dimensionality,constellation,trellis.TRELLIS_EUCLIDEAN) # data preprocessing to generate metrics for Viterbi
 413 </pre><p>
 414 Now the VA can run once it is supplied by the initial and final states.
 415 The initial state is known to be 0; the final state is usually
 416 forced to some value by padding the information sequence appropriately.
 417 In this example, we always send the the same info sequence (we only randomize noise) so we can evaluate off line the final state and then provide it to the VA (a value of -1 signifies that there is no fixed initial
 418 or final state). The VA outputs the estimates of the symbols x_k which
 419 are then packed to shorts and compared with the transmitted sequence.
 420 </p><pre class="programlisting">
 421     va = trellis.viterbi_s(f,K,0,-1) # Put -1 if the Initial/Final states are not set.
 422     fsmi2s = gr.unpacked_to_packed_ss(bitspersymbol,gr.GR_MSB_FIRST) # pack FSM input symbols to shorts
 423     dst = gr.check_lfsr_32k_s();
 424 </pre><p>
 425 The function returns the number of shorts and the number of shorts in error. Observe that this way the estimated error rate refers to
 426 16-bit-symbol error rate.
 427 </p><pre class="programlisting">
 428 return (ntotal,ntotal-nright)
 429 </pre></div><div class="sect1" lang="en"><div class="titlepage"><div><div><h2 class="title" style="clear: both"><a name="future"></a>Future Work</h2></div></div><div></div></div><div class="itemizedlist"><ul type="disc"><li><p>
 430 Improve the documentation :-)
 431 </p></li><li><p>
 432 automate fsm generation from generator polynomials
 433 (feedforward or feedback form).
 434 </p></li><li><p>
 435 Optimize the VA code.
 436 </p></li><li><p>
 437 Provide implementation of soft-input soft-output (SISO) decoders for
 438 potential use in concatenated systems. Also a host of suboptimal
 439 decoders, eg, sphere decoding, M- and T- algorithms, sequential decoding, etc.
 440 </p></li><li><p>
 441 Although turbo decoding is rediculously slow in software,
 442 we can design it in pronciple. The question is, should
 443 we use the FSM and SISO abstractions and cnnect them
 444 through GNU radio or should we implement turbo-decoding
 445 as a single block (issues with buffering between blocks).
 446 </p></li></ul></div></div></div></body></html>