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
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="id2753996"></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"><<a href="mailto:anastas@umich.edu">anastas@umich.edu</a>></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">
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
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
17 code (CC), a trellis code (TC), an inter-symbol interference (ISI)
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.
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> --> A<sub>S</sub>,
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> --> A<sub>S</sub>,
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
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.
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>
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>
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>.
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">
108 std::vector<int> d_NS;
109 std::vector<int> d_OS;
110 std::vector<int> d_PS;
111 std::vector<int> d_PI;
114 fsm(const fsm &FSM);
115 fsm(const int I, const int S, const int O, const std::vector<int> &NS, const std::vector<int> &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<int> & NS () const { return d_NS; }
122 const std::vector<int> & OS () const { return d_OS; }
123 const std::vector<int> & PS () const { return d_PS; }
124 const std::vector<int> & PI () const { return d_PI; }
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<int> &NS, const std::vector<int> &OS);
132 </pre></li><li><p>Giving a filename containing all the FSM information:</p><pre class="programlisting">
133 fsm(const char *name);
135 This information has to be in the following format:
136 </p><pre class="programlisting">
139 NS(0,0) NS(0,1) ... NS(0,I-1)
140 NS(1,0) NS(1,1) ... NS(1,I-1)
142 NS(S-1,0) NS(S-1,1) ... NS(S-1,I-1)
144 OS(0,0) OS(0,1) ... OS(0,I-1)
145 OS(1,0) OS(1,1) ... OS(1,I-1)
147 OS(S-1,0) OS(S-1,1) ... OS(S-1,I-1)
150 For instance, the file containing the information for the example mentioned above is of the form:
151 </p><pre class="programlisting">
164 </p></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.....
165 </p><pre class="programlisting">
166 fsm(const int mod_size, const int ch_length);
167 </pre></li></ul></div><p>
168 Finally, as can be seen from the above description, there are
169 two more variables included in the FSM class implementation,
170 the PS and the PI matrices. These are computed internally
171 when an FSM is instantiated and their meaning is as follows.
172 Sometimes (eg, in the traceback operation of the VA) we need
173 to trace the history of the state or the input sequence.
174 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>
175 and what input symbols x<sub>k-1</sub> will get us from
176 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
178 In the following we assume that for any state,
179 the number of incoming transitions is the same as the number of
180 outgoing transitions, ie, equal to I. All applications of interest
181 have FSMs satisfying this requirement.
183 If we arbitrarily index the incoming transitions to the current state
184 by "i", then as i goes from 0 to I-1, PS(s<sub>k</sub>,i)
185 gives all previous states s<sub>k-1</sub>,
186 and PI(s<sub>k</sub>,i) gives all previous inputs x<sub>k-1</sub>.
187 In other words, for any given s<sub>k</sub> and any index i=0,1,...I-1, starting from
188 s<sub>k-1</sub>=PS(s<sub>k</sub>,i)
190 x<sub>k-1</sub>=PI(s<sub>k</sub>,i)
191 will get us to the state s<sub>k</sub>.
192 More formally, for any i=0,1,...I-1 we have
193 s<sub>k</sub> = NS(PS(s<sub>k</sub>,i),PI(s<sub>k</sub>,i)).
195 </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>
196 We now discuss through a concrete example how
197 the above FSM model can be used in GNU Radio.
199 The communication system that we want to simulate
200 consists of a source generating the
201 input information in packets, a CC encoding each packet separately,
202 a memoryless modulator,
203 an additive white Gaussian noise (AWGN) channel, and
204 the VA performing MLSD.
205 The program source is as follows.
206 </p><pre class="programlisting">
207 1 #!/usr/bin/env python
209 3 from gnuradio import gr
210 4 from gnuradio import audio
211 5 from gnuradio import trellis
212 6 from gnuradio import eng_notation
218 12 def run_test (f,Kb,bitspersymbol,K,dimensionality,constellation,N0,seed):
219 13 fg = gr.flow_graph ()
222 16 src = gr.lfsr_32k_source_s()
223 17 src_head = gr.head (gr.sizeof_short,Kb/16) # packet size in shorts
224 18 s2fsmi = gr.packed_to_unpacked_ss(bitspersymbol,gr.GR_MSB_FIRST) # unpack shorts to symbols compatible with the FSM input cardinality
225 19 enc = trellis.encoder_ss(f,0) # initial state = 0
226 20 mod = gr.chunks_to_symbols_sf(constellation,dimensionality)
230 24 noise = gr.noise_source_f(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
233 27 metrics = trellis.metrics_f(f.O(),dimensionality,constellation,trellis.TRELLIS_EUCLIDEAN) # data preprocessing to generate metrics for Viterbi
234 28 va = trellis.viterbi_s(f,K,0,-1) # Put -1 if the Initial/Final states are not set.
235 29 fsmi2s = gr.unpacked_to_packed_ss(bitspersymbol,gr.GR_MSB_FIRST) # pack FSM input symbols to shorts
236 30 dst = gr.check_lfsr_32k_s();
238 32 fg.connect (src,src_head,s2fsmi,enc,mod)
239 33 fg.connect (mod,(add,0))
240 34 fg.connect (noise,(add,1))
241 35 fg.connect (add,metrics)
242 36 fg.connect (metrics,va,fsmi2s,dst)
246 40 # A bit of cheating: run the program once and print the
247 41 # final encoder state.
248 42 # Then put it as the last argument in the viterbi block
249 43 #print "final state = " , enc.ST()
251 45 ntotal = dst.ntotal ()
252 46 nright = dst.nright ()
253 47 runlength = dst.runlength ()
254 48 return (ntotal,ntotal-nright)
258 52 nargs = len (args)
261 55 esn0_db=float(args[1]) # Es/No in dB
262 56 rep=int(args[2]) # number of times the experiment is run to collect enough errors
264 58 sys.stderr.write ('usage: test_tcm.py fsm_fname Es/No_db repetitions\n')
267 61 # system parameters
268 62 f=trellis.fsm(fname) # get the FSM specification from a file (will hopefully be automated in the future...)
269 63 Kb=1024*16 # packet size in bits (make it multiple of 16 so it can be packed in a short)
270 64 bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
271 65 K=Kb/bitspersymbol # packet size in trellis steps
272 66 modulation = fsm_utils.psk4 # see fsm_utlis.py for available predefined modulations
273 67 dimensionality = modulation[0]
274 68 constellation = modulation[1]
275 69 if len(constellation)/dimensionality != f.O():
276 70 sys.stderr.write ('Incompatible FSM output cardinality and modulation size.\n')
278 72 # calculate average symbol energy
280 74 for i in range(len(constellation)):
281 75 Es = Es + constellation[i]**2
282 76 Es = Es / (len(constellation)/dimensionality)
283 77 N0=Es/pow(10.0,esn0_db/10.0); # noise variance
287 81 for i in range(rep):
288 82 (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 86 print i,s,e,tot_s,terr_s, '%e' % ((1.0*terr_s)/tot_s)
293 87 # estimate of the (short) error rate
294 88 print tot_s,terr_s, '%e' % ((1.0*terr_s)/tot_s)
297 91 if __name__ == '__main__':
298 92 main (sys.argv[1:])
300 The program is called by
301 </p><div class="literallayout"><p><br>
302 ./test_tcm.py fsm_fname Es/No_db repetitions<br>
304 where "fsm_fname" is the file containing the FSM specification of the
305 tested TCM code, "Es/No_db" is the SNR in dB, and "repetitions"
306 are the number of packets to be transmitted and received in order to
307 collect sufficient number of errors for an accurate estimate of the
310 The FSM is first intantiated in "main" by
311 </p><pre class="programlisting">
312 62 f=trellis.fsm(fname) # get the FSM specification from a file (will hopefully be automated in the future...)
314 Each packet has size Kb bits
315 (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).
316 Assuming that the FSM input has cardinality I, each input symbol consists
317 of bitspersymbol=log<sub>2</sub>( I ). The Kb/16 shorts are now
318 unpacked to K=Kb/bitspersymbol input
319 symbols that will drive the FSM encoder.
320 </p><pre class="programlisting">
321 63 Kb=1024*16 # packet size in bits (make it multiple of 16 so it can be packed in a short)
322 64 bitspersymbol = int(round(math.log(f.I())/math.log(2))) # bits per FSM input symbol
323 65 K=Kb/bitspersymbol # packet size in trellis steps
325 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
326 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
327 constellation=[c11,c12,...,c1N,c21,c22,...,c2N,...,cM1,cM2,...cMN].
328 The meaning of the above is that every constellation point c_i
329 is an N-dimnsional vector c_i=(ci1,ci2,...,ciN)
330 For instance, 4-ary PAM is represented as
331 (1,[-3, -1, 1, 3]), while QPSK is represented as
332 (2,[1, 0, 0, 1, 0, -1, -1, 0]). In our example we choose QPSK modulation.
333 Clearly, M should be equal to the cardinality of the FSM output, O.
334 Finally the average symbol energy and noise variance are calculated.
335 </p><pre class="programlisting">
336 66 modulation = fsm_utils.psk4 # see fsm_utlis.py for available predefined modulations
337 67 dimensionality = modulation[0]
338 68 constellation = modulation[1]
339 69 if len(constellation)/dimensionality != f.O():
340 70 sys.stderr.write ('Incompatible FSM output cardinality and modulation size.\n')
342 72 # calculate average symbol energy
344 74 for i in range(len(constellation)):
345 75 Es = Es + constellation[i]**2
346 76 Es = Es / (len(constellation)/dimensionality)
347 77 N0=Es/pow(10.0,esn0_db/10.0); # noise variance
349 Then, "run_test" is called with a different "seed" so that we get
350 different noise realizations.
351 </p><pre class="programlisting">
352 82 (s,e)=run_test(f,Kb,bitspersymbol,K,dimensionality,constellation,N0,-long(666+i)) # run experiment with different seed to get different noise realizations
354 Let us examine now the "run_test" function.
355 First we set up the transmitter blocks.
356 The Kb/16 shorts are first unpacked to
357 symbols consistent with the FSM input alphabet.
358 The FSm encoder requires the FSM specification,
359 and an initial state (which is set to 0 in this example).
360 </p><pre class="programlisting">
362 16 src = gr.lfsr_32k_source_s()
363 17 src_head = gr.head (gr.sizeof_short,Kb/16) # packet size in shorts
364 18 s2fsmi = gr.packed_to_unpacked_ss(bitspersymbol,gr.GR_MSB_FIRST) # unpack shorts to symbols compatible with the FSM input cardinality
365 19 enc = trellis.encoder_ss(f,0) # initial state = 0
367 We now need to modulate the FSM output symbols.
368 The "chunks_to_symbols_sf" is essentially a memoryless mapper which
369 for each input symbol y_k
370 outputs a sequence of N numbers ci1,ci2,...,ciN representing the
371 coordianates of the constellation symbol c_i with i=y_k.
372 </p><pre class="programlisting">
373 20 mod = gr.chunks_to_symbols_sf(constellation,dimensionality)
375 The channel is AWGN with appropriate noise variance.
376 For each transmitted symbol c_k=(ck1,ck2,...,ckN) we receive a noisy version
377 r_k=(rk1,rk2,...,rkN).
378 </p><pre class="programlisting">
381 24 noise = gr.noise_source_f(gr.GR_GAUSSIAN,math.sqrt(N0/2),seed)
383 Part of the design methodology was to decouple the FSM and VA from
384 the details of the modulation, channel, receiver front-end etc.
385 In order for the VA to run, we only need to provide it with
386 a number representing a cost associated with each transition
387 in the trellis. Then the VA will find the sequence with
388 the smallest total cost through the trellis.
389 The cost associated with a transition (s_k,x_k) is only a function
390 of the output y_k = OS(s_k,x_k), and the observation
391 vector r_k. Thus, for each time period, k,
392 we need to label each of the SxI transitions with such a cost.
393 This means that for each time period we need to evaluate
394 O such numbers (one for each possible output symbol y_k).
396 in "metrics_f". In particular, metrics_f is a memoryless device
397 taking N inputs at a time and producing O outputs. The N inputs are
400 are the costs associated with observations rk1,rk2,...,rkN and
401 hypothesized output symbols c_1,c_2,...,c_M. For instance,
402 if we choose to perform soft-input VA, we need to evaluate
403 the Euclidean distance between r_k and each of c_1,c_2,...,c_M,
404 for each of the K transmitted symbols.
405 Other options are available as well; for instance, we can
406 do hard decision demodulation and feed the VA with
407 symbol Hamming distances, or even bit Hamming distances, etc.
408 These are all implemented in "metrics_f".
409 </p><pre class="programlisting">
411 27 metrics = trellis.metrics_f(f.O(),dimensionality,constellation,trellis.TRELLIS_EUCLIDEAN) # data preprocessing to generate metrics for Viterbi
413 Now the VA can run once it is supplied by the initial and final states.
414 The initial state is known to be 0; the final state is usually
415 forced to some value by padding the information sequence appropriately.
416 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
417 or final state). The VA outputs the estimates of the symbols x_k which
418 are then packed to shorts and compared with the transmitted sequence.
419 </p><pre class="programlisting">
420 28 va = trellis.viterbi_s(f,K,0,-1) # Put -1 if the Initial/Final states are not set.
421 29 fsmi2s = gr.unpacked_to_packed_ss(bitspersymbol,gr.GR_MSB_FIRST) # pack FSM input symbols to shorts
422 30 dst = gr.check_lfsr_32k_s();
424 The function returns the number of shorts and the number of shorts in error. Observe that this way the estimated error rate refers to
425 16-bit-symbol error rate.
426 </p><pre class="programlisting">
427 48 return (ntotal,ntotal-nright)
428 </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>
429 Improve the documentation :-)
431 automate fsm generation from generator polynomials
432 (feedforward or feedback form).
434 Optimize the VA code.
436 Provide implementation of soft-input soft-output (SISO) decoders for
437 potential use in concatenated systems. Also a host of suboptimal
438 decoders, eg, sphere decoding, M- and T- algorithms, sequential decoding, etc.
441 Although turbo decoding is rediculously slow in software,
442 we can design it in principle. One question is, whether we should
443 use the encoder, and SISO blocks and connect them
444 through GNU radio or we should implement turbo-decoding
445 as a single block (issues with buffering between blocks).
446 </p></li></ul></div></div></div></body></html>
projects / debian / gnuradio / blob