diff mbox

[1/4] Add code generator for convolutional codes

Message ID 1460384569-13790-1-git-send-email-msuraev@sysmocom.de
State Not Applicable
Headers show

Commit Message

Max April 11, 2016, 2:22 p.m. UTC 
From: Max <msuraev@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

Comments

Holger Freyther April 14, 2016, 12:22 a.m. UTC | #1 
> On 11 Apr 2016, at 10:22, msuraev@sysmocom.de wrote:
> 
> From: Max <msuraev@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@246tNt.com>
> + * Copyright (C) 2016 sysmocom s.f.m.c. GmbH

what is yours (sysmocom's) contribution to that file? I assume that Sylvain did most of the work, it would be nice to have this be reflected in the commit message.

thank you
	holger
diff mbox

Patch

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@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."