-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathTrellis.py
145 lines (123 loc) · 5.71 KB
/
Trellis.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
#! /usr/bin/env python
# title : Trellis.py
# description : This class generates a trellis based on a trellis definition class.
# Parameters such as reduction (radix) can be used to construct the trellis.
# author : Felix Arnold
# python_version : 3.5.2
import utils
class Trellis(object):
def __init__(self, trellisDefinition, reduction=1, merge_parallel=False):
self.tdef = trellisDefinition
self.reduction = reduction
self.merge_parallel = merge_parallel
self.radix = 2 ** reduction # relationship between reduction factor and radix
self.Ns = self.tdef.Ns # number of states
self.Nb = self.tdef.Nb * 2 ** (reduction - 1) # number of branches
self.wc = self.tdef.wc * reduction # number of coded bits
self.wu = self.tdef.wu * reduction # number of data bits
# empty precomputed lists
self.get_dat_pc = []
self.get_enc_bits_pc = []
self.get_next_state_pc = []
self.get_prev_state_pc = []
self.get_next_branches_pc = []
self.get_prev_branches_pc = []
# perform computation of trellis
if reduction == 1 and not self.merge_parallel:
self.pre_calc_reduction1()
else:
self.pre_calculation()
def get_rate(self):
return self.wc / self.wu
def pre_calc_reduction1(self):
"""
Pre calculate the functions of a trellis:
- get_dat, get_enc_bits, get_next_state, get_prev_state
- get_next_branches, get_prev_branches
"""
self.get_dat_pc = [self.tdef.get_dat(x) for x in range(self.Nb)]
self.get_enc_bits_pc = [self.tdef.get_enc_bits(x) for x in range(self.Nb)]
self.get_next_state_pc = [self.tdef.get_next_state(x) for x in range(self.Nb)]
self.get_prev_state_pc = [self.tdef.get_prev_state(x) for x in range(self.Nb)]
self.get_prev_branches_pc = [self.tdef.get_prev_branches(x) for x in range(self.Ns)]
# for the pre calculation of 'next branches' we, we do the same
# but additionally sort for the data output generated by this branch
# this way the encoder can use get the next branch via
# this code -> trellis.get_next_branches_pc[current_state][data_input]
get_next_branches_pc_unsorted = [self.tdef.get_next_branches(x) for x in range(self.Ns)]
self.get_next_branches_pc = []
for b in get_next_branches_pc_unsorted:
dat_b = [self.get_dat_pc[x] for x in b]
dat_d = [utils.bin2dec(x) for x in dat_b]
b_new = [x for _, x in sorted(zip(dat_d, b))]
self.get_next_branches_pc.append(b_new)
def pre_calculation(self):
"""
Pre calculate the functions of a trellis (with options):
- get_dat, get_enc_bits, get_next_state, get_prev_state
- get_next_branches, get_prev_branches
Options are:
- reduction = log2(radix)
- merge parallel branches
"""
all_u, all_c, all_s = [], [], []
for s in range(self.Ns):
u, c, s = self._get_all_paths(self.reduction, s)
all_u = all_u + u
all_c = all_c + c
all_s = all_s + s
# init tables
n_branches_per_state = int(self.Nb / self.Ns)
self.get_dat_pc = []
self.get_enc_bits_pc = []
self.get_next_state_pc = []
self.get_prev_state_pc = []
self.get_next_branches_pc = [[-1] * n_branches_per_state for i in range(self.Ns)]
self.get_prev_branches_pc = [[] for i in range(self.Ns)]
# loop through all paths and generate a new branch for each
for branch_index in range(len(all_u)):
u = all_u[branch_index]
c = all_c[branch_index]
s = all_s[branch_index]
# check if branch already exists
n_states = self.get_next_state_pc
p_states = self.get_prev_state_pc
branch_exists = True in [x == s[0] and y == s[-1] for x, y in zip(p_states, n_states)]
if self.merge_parallel and branch_exists:
pass
else:
dat_int = utils.bin2dec(u)
self.get_dat_pc.append(u)
self.get_enc_bits_pc.append(c)
self.get_next_state_pc.append(s[-1])
self.get_prev_state_pc.append(s[0])
self.get_next_branches_pc[s[0]][dat_int] = branch_index
self.get_prev_branches_pc[s[-1]].append(branch_index)
def _get_all_paths(self, depth, state):
"""
recursively get all paths form a start state with depth n
Parameters
----------
depth [int]: depths of recursion
state [int]: start state for paths to be returned
Returns
-------
pathlist_u, pathlist_c, pathlist_s: [list of lists] list of paths
"""
if depth == 0:
return [[]], [[]], [[state]]
else:
# for all next states (next_state
# get all paths with depth-1 from next_state,
# then add the path from state to next_state to all these paths
# add new paths to list
pathlist_u, pathlist_c, pathlist_s = [], [], []
# pathlist_* are lists of paths
for b in self.tdef.get_next_branches(state):
next_state = self.tdef.get_next_state(b)
u1, c1, s1 = self._get_all_paths(depth - 1, next_state)
# for all lists in u1 add the new element
pathlist_u += [self.tdef.get_dat(b) + x for x in u1]
pathlist_c += [self.tdef.get_enc_bits(b) + x for x in c1]
pathlist_s += [[state] + x for x in s1]
return pathlist_u, pathlist_c, pathlist_s