This is merely a historical archive of years 2008-2021, before the migration to mailman3.
A maintained and still updated list archive can be found at https://lists.osmocom.org/hyperkitty/list/OpenBSC@lists.osmocom.org/.
msuraev at sysmocom.de msuraev at sysmocom.deFrom: Max <msuraev at sysmocom.de> Add python utility to generate .c code with state/output tables for convolutional encoder/decoder based on polynomial description of the code. If argument given it'll be interpreted as intended output directory, otherwise current working directory is used. Note: only necessary tables are generated. Corresponding header files with actual osmo_conv_code instance (including puncturing etc) have to be added manually. Fixes: OS#1629 --- utils/conv_gen.py | 359 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 359 insertions(+) create mode 100755 utils/conv_gen.py diff --git a/utils/conv_gen.py b/utils/conv_gen.py new file mode 100755 index 0000000..52c1ab3 --- /dev/null +++ b/utils/conv_gen.py @@ -0,0 +1,359 @@ +#!/usr/bin/python + +license =""" +/* + * Copyright (C) 2011-2016 Sylvain Munaut <tnt at 246tNt.com> + * Copyright (C) 2016 sysmocom s.f.m.c. GmbH + * + * All Rights Reserved + * + * This program is free software; you can redistribute it and/or modify + * it under the terms of the GNU General Public License as published by + * the Free Software Foundation; either version 3 of the License, or + * (at your option) any later version. + * + * This program is distributed in the hope that it will be useful, + * but WITHOUT ANY WARRANTY; without even the implied warranty of + * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + * GNU General Public License for more details. + * + * You should have received a copy of the GNU General Public License along + * with this program; if not, write to the Free Software Foundation, Inc., + * 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA. + */ +""" + +import sys, os + +class ConvolutionalCode(object): + + def __init__(self, block_len, k, polys, name = "call-me", description = "LOL"): + # Save simple params + self.block_len = block_len + self.k = k + self.rate_inv = len(polys) + + # Infos + self.name = name + self.description = description + + # Handle polynoms (and check for recursion) + self.polys = [(1, 1) if x[0] == x[1] else x for x in polys] + + rp = [x[1] for x in self.polys if x[1] != 1] + if rp: + if not all([x == rp[0] for x in rp]): + raise ValueError("Bad polynoms: Can't have multiple different divider polynoms !") + if not all([x[0] == 1 for x in polys if x[1] == 1]): + raise ValueError("Bad polynoms: Can't have a '1' divider with a non '1' dividend in a recursive code") + self.poly_divider = rp[0] + else: + self.poly_divider = 1 + + @property + def recursive(self): + return self.poly_divider != 1 + + def _combine(self, src, sel, nb): + x = src & sel + fn_xor = lambda x, y: x ^ y + return reduce(fn_xor, [(x >> n) & 1 for n in range(nb)]) + + @property + def _state_mask(self): + return ((1 << (self.k - 1)) - 1) + + def next_state(self, state, bit): + nb = self._combine( + (state << 1) | bit, + self.poly_divider, + self.k, + ) + return ((state << 1) | nb) & self._state_mask + + def next_term_state(self, state): + return (state << 1) & self._state_mask + + def next_output(self, state, bit, ns = None): + # Next state bit + if ns is None: + ns = self.next_state(state, bit) + + src = (ns & 1) | (state << 1) + + # Scan polynoms + rv = [] + for p_n, p_d in self.polys: + if self.recursive and p_d == 1: + o = bit # No choice ... (systematic output in recursive case) + else: + o = self._combine(src, p_n, self.k) + rv.append(o) + + return rv + + def next_term_output(self, state, ns = None): + # Next state bit + if ns is None: + ns = self.next_term_state(state) + + src = (ns & 1) | (state << 1) + + # Scan polynoms + rv = [] + for p_n, p_d in self.polys: + if self.recursive and p_d == 1: + # Systematic output are replaced when in 'termination' mode + o = self._combine(src, self.poly_divider, self.k) + else: + o = self._combine(src, p_n, self.k) + rv.append(o) + + return rv + + def next(self, state, bit): + ns = self.next_state(state, bit) + nb = self.next_output(state, bit, ns = ns) + return ns, nb + + def next_term(self, state): + ns = self.next_term_state(state) + nb = self.next_term_output(state, ns = ns) + return ns, nb + + def _print_term(self, pref, fi, num_states, pack, is_state = True): + s = "state" if is_state else "output" + print >>fi, "\n/* .next_term_%s */" % s + print >>fi, "const uint8_t %s_%s_term_%s[] = {" % (pref, self.name, s) + d = [] + for state in range(num_states): + if is_state: + x = self.next_term_state(state) + else: + x = pack(self.next_term_output(state)) + d.append("%d, " % x) + print >>fi, "\t%s\n};" % ''.join(d) + + def _print_x(self, pref, fi, num_states, pack, is_state = True): + s = "state" if is_state else "output" + print >>fi, "\n/* .next_%s */" % s + print >>fi, "const uint8_t %s_%s_%s[][2] = {" % (pref, self.name, s) + for state in range(num_states): + if is_state: + x0 = self.next_state(state, 0) + x1 = self.next_state(state, 1) + else: + x0 = pack(self.next_output(state, 0)) + x1 = pack(self.next_output(state, 1)) + print >>fi, "\t{ %2d, %2d }," % (x0, x1) + print >>fi, "};" + + def gen_tables(self, pref, fi): + pack = lambda n: sum([x << (self.rate_inv - i - 1) for i, x in enumerate(n)]) + num_states = 1 << (self.k - 1) + print >>fi, "\n/* %s */" % self.description + #print >>fi, "const int %s_%s_length = %d;" % (pref, self.name, self.block_len) + #print >>fi, "const int %s_%s_K = %d;" % (pref, self.name, self.k) + self._print_x(pref, fi, num_states, pack) + self._print_x(pref, fi, num_states, pack, False) + + if self.recursive: + self._print_term(pref, fi, num_states, pack) + self._print_term(pref, fi, num_states, pack, False) + +poly = lambda *args: sum([(1 << x) for x in args]) + +xcch = ConvolutionalCode( + 224, 5, + [ + ( poly(0, 3, 4), 1 ), + ( poly(0, 1, 3, 4), 1 ), + ], + name = "xcch", + description =""" *CCH convolutional code: + 228 bits blocks, rate 1/2, k = 5 + G0 = 1 + D3 + D4 + G1 = 1 + D + D3 + D4 +""" +) + +tch_afs_12_2 = ConvolutionalCode( + 250, 5, + [ + ( 1, 1 ), + ( poly(0, 1, 3, 4), poly(0, 3, 4) ), + ], + name = 'tch_afs_12_2', + description = """TCH/AFS 12.2 convolutional code: + 250 bits block, rate 1/2, punctured + G0/G0 = 1 + G1/G0 = 1 + D + D3 + D4 / 1 + D3 + D4 +""" +) + +tch_afs_10_2 = ConvolutionalCode( + 210, 5, + [ + ( poly(0, 1, 3, 4), poly(0, 1, 2, 3, 4) ), + ( poly(0, 2, 4), poly(0, 1, 2, 3, 4) ), + ( 1, 1 ), + ], + name = 'tch_afs_10_2', + description = """TCH/AFS 10.2 kbits convolutional code: + G1/G3 = 1 + D + D3 + D4 / 1 + D + D2 + D3 + D4 + G2/G3 = 1 + D2 + D4 / 1 + D + D2 + D3 + D4 + G3/G3 = 1 +""" +) + +tch_afs_7_95 = ConvolutionalCode( + 165, 7, + [ + ( 1, 1 ), + ( poly(0, 1, 4, 6), poly(0, 2, 3, 5, 6) ), + ( poly(0, 1, 2, 3, 4, 6), poly(0, 2, 3, 5, 6) ), + ], + name = 'tch_afs_7_95', + description = """TCH/AFS 7.95 kbits convolutional code: + G4/G4 = 1 + G5/G4 = 1 + D + D4 + D6 / 1 + D2 + D3 + D5 + D6 + G6/G4 = 1 + D + D2 + D3 + D4 + D6 / 1 + D2 + D3 + D5 + D6 +""" +) + +tch_afs_7_4 = ConvolutionalCode( + 154, 5, + [ + ( poly(0, 1, 3, 4), poly(0, 1, 2, 3, 4) ), + ( poly(0, 2, 4), poly(0, 1, 2, 3, 4) ), + ( 1, 1 ), + ], + name = 'tch_afs_7_4', + description = """TCH/AFS 7.4 kbits convolutional code: + G1/G3 = 1 + D + D3 + D4 / 1 + D + D2 + D3 + D4 + G2/G3 = 1 + D2 + D4 / 1 + D + D2 + D3 + D4 + G3/G3 = 1 +""" +) + +tch_afs_6_7 = ConvolutionalCode( + 140, 5, + [ + ( poly(0, 1, 3, 4), poly(0, 1, 2, 3, 4) ), + ( poly(0, 2, 4), poly(0, 1, 2, 3, 4) ), + ( 1, 1 ), + ( 1, 1 ), + ], + name = 'tch_afs_6_7', + description = """TCH/AFS 6.7 kbits convolutional code: + G1/G3 = 1 + D + D3 + D4 / 1 + D + D2 + D3 + D4 + G2/G3 = 1 + D2 + D4 / 1 + D + D2 + D3 + D4 + G3/G3 = 1 + G3/G3 = 1 +""" +) + +tch_afs_5_9 = ConvolutionalCode( + 124, 7, + [ + ( poly(0, 2, 3, 5, 6), poly(0, 1, 2, 3, 4, 6) ), + ( poly(0, 1, 4, 6), poly(0, 1, 2, 3, 4, 6) ), + ( 1, 1), + ( 1, 1), + ], + name = 'tch_afs_5_9', + description = """TCH/AFS 5.9 kbits convolutional code: + 124 bits + G4/G6 = 1 + D2 + D3 + D5 + D6 / 1 + D + D2 + D3 + D4 + D6 + G5/G6 = 1 + D + D4 + D6 / 1 + D + D2 + D3 + D4 + D6 + G6/G6 = 1 + G6/G6 = 1 +""" +) + +tch_afs_5_15 = ConvolutionalCode( + 109, 5, + [ + ( poly(0, 1, 3, 4), poly(0, 1, 2, 3, 4) ), + ( poly(0, 1, 3, 4), poly(0, 1, 2, 3, 4) ), + ( poly(0, 2, 4), poly(0, 1, 2, 3, 4) ), + ( 1, 1 ), + ( 1, 1 ), + ], + name = 'tch_afs_5_15', + description = """TCH/AFS 5.15 kbits convolutional code: + G1/G3 = 1 + D + D3 + D4 / 1 + D + D2 + D3 + D4 + G1/G3 = 1 + D + D3 + D4 / 1 + D + D2 + D3 + D4 + G2/G3 = 1 + D2 + D4 / 1 + D + D2 + D3 + D4 + G3/G3 = 1 + G3/G3 = 1 +""" +) + +tch_afs_4_75 = ConvolutionalCode( + 101, 7, + [ + ( poly(0, 2, 3, 5, 6), poly(0, 1, 2, 3, 4, 6) ), + ( poly(0, 2, 3, 5, 6), poly(0, 1, 2, 3, 4, 6) ), + ( poly(0, 1, 4, 6), poly(0, 1, 2, 3, 4, 6) ), + ( 1, 1 ), + ( 1, 1 ), + ], + name = 'tch_afs_4_75', + description = """TCH/AFS 4.75 kbits convolutional code: + G4/G6 = 1 + D2 + D3 + D5 + D6 / 1 + D + D2 + D3 + D4 + D6 + G4/G6 = 1 + D2 + D3 + D5 + D6 / 1 + D + D2 + D3 + D4 + D6 + G5/G6 = 1 + D + D4 + D6 / 1 + D + D2 + D3 + D4 + D6 + G6/G6 = 1 + G6/G6 = 1 +""" +) + +tetra_rcpc = ConvolutionalCode( + 288, 5, + [ + ( poly(0,1,4), 1 ), + ( poly(0,2,3,4), 1 ), + ( poly(0,1,2,4), 1 ), + ( poly(0,1,3,4), 1 ), + ], + name = 'tetra_rcpc', + description = """TETRA RCPC code + G1 = 1 + D + D4 + G2 = 1 + D2 + D3 + D4 + G3 = 1 + D + D2 + D4 + G4 = 1 + D + D3 + D4 +""" +) + +tetra_rcpc_tch = ConvolutionalCode( + 288, 5, + [ + ( poly(0, 1, 2, 3, 4), 1 ), + ( poly(0, 1, 3, 4), 1 ), + ( poly(0, 2, 4), 1 ), + ], + description = """TETRA RCPC TCH code +""" +) + +def gen_c(path, prefix, code): + f = open(os.path.join(path, 'conv_' + code.name + '_gen.c'), 'w') + print >>f, license + print >>f, "#include <stdint.h>" + code.gen_tables(prefix, f) + +if __name__ == '__main__': + print >>sys.stderr, "Generating convolutional codes..." + prefix = "osmo_conv_gsm0503" + path = sys.argv[1] if len(sys.argv) > 1 else os.getcwd() + gen_c(path, prefix, xcch) + gen_c(path, prefix, tch_afs_12_2) + gen_c(path, prefix, tch_afs_10_2) + gen_c(path, prefix, tch_afs_7_95) + gen_c(path, prefix, tch_afs_7_4) + gen_c(path, prefix, tch_afs_6_7) + gen_c(path, prefix, tch_afs_5_9) + gen_c(path, prefix, tch_afs_5_15) + gen_c(path, prefix, tch_afs_4_75) + print >>sys.stderr, "\tdone." -- 2.8.1