git.gag.com Git - debian/gnuradio/blob - gnuradio-examples/python/channel-coding/fsm_utils.py

   1 #!/usr/bin/env python
   2 #
   3 # Copyright 2004 Free Software Foundation, Inc.
   4 #
   5 # This file is part of GNU Radio
   6 #
   7 # GNU Radio is free software; you can redistribute it and/or modify
   8 # it under the terms of the GNU General Public License as published by
   9 # the Free Software Foundation; either version 3, or (at your option)
  10 # any later version.
  11 #
  12 # GNU Radio is distributed in the hope that it will be useful,
  13 # but WITHOUT ANY WARRANTY; without even the implied warranty of
  14 # MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  15 # GNU General Public License for more details.
  16 #
  17 # You should have received a copy of the GNU General Public License
  18 # along with GNU Radio; see the file COPYING.  If not, write to
  19 # the Free Software Foundation, Inc., 51 Franklin Street,
  20 # Boston, MA 02110-1301, USA.
  21 #
  22
  23
  24 import re
  25 import math
  26 import sys
  27 import operator
  28
  29 from gnuradio import trellis
  30
  31
  32
  33 ######################################################################
  34 # Decimal to any base conversion.
  35 # Convert 'num' to a list of 'l' numbers representing 'num'
  36 # to base 'base' (most significant symbol first).
  37 ######################################################################
  38 def dec2base(num,base,l):
  39     s=range(l)
  40     n=num
  41     for i in range(l):
  42         s[l-i-1]=n%base
  43         n=int(n/base)
  44     if n!=0:
  45         print 'Number ', num, ' requires more than ', l, 'digits.'
  46     return s
  47
  48
  49 ######################################################################
  50 # Conversion from any base to decimal.
  51 # Convert a list 's' of symbols to a decimal number
  52 # (most significant symbol first)
  53 ######################################################################
  54 def base2dec(s,base):
  55     num=0
  56     for i in range(len(s)):
  57         num=num*base+s[i]
  58     return num
  59
  60
  61 ######################################################################
  62 # Generate a new FSM representing the concatenation of two FSMs
  63 ######################################################################
  64 def fsm_concatenate(f1,f2):
  65     if f1.O() > f2.I():
  66         print "Not compatible FSMs\n"
  67     I=f1.I()
  68     S=f1.S()*f2.S()
  69     O=f2.O()
  70     nsm=list([0]*I*S)
  71     osm=list([0]*I*S)
  72     for s1 in range(f1.S()):
  73         for s2 in range(f2.S()):
  74             for i in range(f1.I()):
  75                 ns1=f1.NS()[s1*f1.I()+i]
  76                 o1=f1.OS()[s1*f1.I()+i]
  77                 ns2=f2.NS()[s2*f2.I()+o1]
  78                 o2=f2.OS()[s2*f2.I()+o1]
  79
  80                 s=s1*f2.S()+s2
  81                 ns=ns1*f2.S()+ns2
  82                 nsm[s*I+i]=ns
  83                 osm[s*I+i]=o2
  84
  85
  86     f=trellis.fsm(I,S,O,nsm,osm)
  87     return f
  88
  89 ######################################################################
  90 # Generate a new FSM representing n stages through the original FSM
  91 ######################################################################
  92 def fsm_radix(f,n):
  93     I=f.I()**n
  94     S=f.S()
  95     O=f.O()**n
  96     nsm=list([0]*I*S)
  97     osm=list([0]*I*S)
  98     for s in range(f.S()):
  99         for i in range(I):
 100             ii=dec2base(i,f.I(),n)
 101             oo=list([0]*n)
 102             ns=s
 103             for k in range(n):
 104                 oo[k]=f.OS()[ns*f.I()+ii[k]]
 105                 ns=f.NS()[ns*f.I()+ii[k]]
 106
 107             nsm[s*I+i]=ns
 108             osm[s*I+i]=base2dec(oo,f.O())
 109
 110
 111     f=trellis.fsm(I,S,O,nsm,osm)
 112     return f
 113
 114
 115
 116
 117 ######################################################################
 118 # Automatically generate the lookup table that maps the FSM outputs
 119 # to channel inputs corresponding to a channel 'channel' and a modulation
 120 # 'mod'. Optional normalization of channel to unit energy.
 121 # This table is used by the 'metrics' block to translate
 122 # channel outputs to metrics for use with the Viterbi algorithm.
 123 # Limitations: currently supports only one-dimensional modulations.
 124 ######################################################################
 125 def make_isi_lookup(mod,channel,normalize):
 126     dim=mod[0]
 127     constellation = mod[1]
 128
 129     if normalize:
 130         p = 0
 131         for i in range(len(channel)):
 132             p = p + channel[i]**2
 133         for i in range(len(channel)):
 134             channel[i] = channel[i]/math.sqrt(p)
 135
 136     lookup=range(len(constellation)**len(channel))
 137     for o in range(len(constellation)**len(channel)):
 138         ss=dec2base(o,len(constellation),len(channel))
 139         ll=0
 140         for i in range(len(channel)):
 141             ll=ll+constellation[ss[i]]*channel[i]
 142         lookup[o]=ll
 143     return (1,lookup)
 144
 145
 146
 147
 148
 149
 150 ######################################################################
 151 # A list of common modulations.
 152 # Format: (dimensionality,constellation)
 153 ######################################################################
 154 pam2 = (1,[-1, 1])
 155 pam4 = (1,[-3, -1, 3, 1])               # includes Gray mapping
 156 pam8 = (1,[-7, -5, -3, -1, 1, 3, 5, 7])
 157
 158 psk4=(2,[1, 0, \
 159          0, 1, \
 160          0, -1,\
 161         -1, 0])                         # includes Gray mapping
 162 psk8=(2,[math.cos(2*math.pi*0/8), math.sin(2*math.pi*0/8),  \
 163          math.cos(2*math.pi*1/8), math.sin(2*math.pi*1/8),  \
 164          math.cos(2*math.pi*2/8), math.sin(2*math.pi*2/8),  \
 165          math.cos(2*math.pi*3/8), math.sin(2*math.pi*3/8),  \
 166          math.cos(2*math.pi*4/8), math.sin(2*math.pi*4/8),  \
 167          math.cos(2*math.pi*5/8), math.sin(2*math.pi*5/8),  \
 168          math.cos(2*math.pi*6/8), math.sin(2*math.pi*6/8),  \
 169          math.cos(2*math.pi*7/8), math.sin(2*math.pi*7/8)])
 170
 171 orth2 = (2,[1, 0, \
 172             0, 1])
 173 orth4=(4,[1, 0, 0, 0, \
 174           0, 1, 0, 0, \
 175           0, 0, 1, 0, \
 176           0, 0, 0, 1])
 177
 178 ######################################################################
 179 # A list of channels to be tested
 180 ######################################################################
 181
 182 # C test channel (J. Proakis, Digital Communications, McGraw-Hill Inc., 2001)
 183 c_channel = [0.227, 0.460, 0.688, 0.460, 0.227]
 184
 185
 186
 187
 188
 189
 190
 191
 192
 193
 194 if __name__ == '__main__':
 195     f1=trellis.fsm('fsm_files/awgn1o2_4.fsm')
 196     #f2=trellis.fsm('fsm_files/awgn2o3_4.fsm')
 197     print f1.I(), f1.S(), f1.O()
 198     print f1.NS()
 199     print f1.OS()
 200     #print f2.I(), f2.S(), f2.O()
 201     #print f2.NS()
 202     #print f2.OS()
 203     ##f1.write_trellis_svg('f1.svg',4)
 204     #f2.write_trellis_svg('f2.svg',4)
 205     #f=fsm_concatenate(f1,f2)
 206     f=fsm_radix(f1,2)
 207
 208     print "----------\n"
 209     print f.I(), f.S(), f.O()
 210     print f.NS()
 211     print f.OS()
 212     #f.write_trellis_svg('f.svg',4)
 213