1 // ----------------------------------------------------------------------------
2 // viterbi.cxx -- Viterbi decoder
3 //
4 // Copyright (C) 2006
5 // Dave Freese, W1HKJ
6 //
7 // Adapted from code contained in gmfsk source code distribution.
8 //
9 // This file is part of fldigi.
10 //
11 // Fldigi is free software: you can redistribute it and/or modify
12 // it under the terms of the GNU General Public License as published by
13 // the Free Software Foundation, either version 3 of the License, or
14 // (at your option) any later version.
15 //
16 // Fldigi is distributed in the hope that it will be useful,
17 // but WITHOUT ANY WARRANTY; without even the implied warranty of
18 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 // GNU General Public License for more details.
20 //
21 // You should have received a copy of the GNU General Public License
22 // along with fldigi. If not, see <http://www.gnu.org/licenses/>.
23 // ----------------------------------------------------------------------------
24
25 #include <config.h>
26
27 #include <stdio.h>
28 #include <stdlib.h>
29 #include <string.h>
30 #include <limits.h>
31
32 #include "viterbi.h"
33 #include "misc.h"
34
35 /* ---------------------------------------------------------------------- */
viterbi(int k,int poly1,int poly2)36 viterbi::viterbi(int k, int poly1, int poly2)
37 {
38 outsize = 1 << k;
39 nstates = 1 << (k - 1);
40 _k = k;
41 _poly1 = poly1;
42 _poly2 = poly2;
43
44 output = new int[outsize];
45
46 for (int i = 0; i < PATHMEM; i++) {
47 metrics[i] = new int[nstates];
48 history[i] = new int[nstates];
49 }
50
51 init();
52 }
53
~viterbi()54 viterbi::~viterbi()
55 {
56 if (output) delete [] output;
57 for (int i = 0; i < PATHMEM; i++) {
58 if (metrics[i]) delete [] metrics[i];
59 if (history[i]) delete [] history[i];
60 }
61 }
62
init(void)63 void viterbi::init(void)
64 {
65 if(output) {
66 _traceback = _k * 12; // takes >= 12 constraint lengths to calculate from an arbitrary state, when punctured
67 _chunksize = 8;
68
69 for (int i = 0; i < outsize; i++) {
70 output[i] = parity(_poly1 & i) | (parity(_poly2 & i) << 1);
71 }
72
73 for (int i = 0; i < 256; i++) {
74 mettab[0][i] = 128 - i;
75 mettab[1][i] = i - 128;
76 }
77
78 memset(sequence, 0, sizeof(sequence));
79
80 reset();
81 }
82 }
83
84
reset()85 void viterbi::reset()
86 {
87 for (int i = 0; i < PATHMEM; i++) {
88 memset(metrics[i], 0, nstates * sizeof(int));
89 memset(history[i], 0, nstates * sizeof(int));
90 }
91 ptr = 0;
92 }
93
settraceback(int trace)94 int viterbi::settraceback(int trace)
95 {
96 if (trace < 0 || trace > PATHMEM - 1)
97 return -1;
98 _traceback = trace;
99 return 0;
100 }
101
setchunksize(int chunk)102 int viterbi::setchunksize(int chunk)
103 {
104 if (chunk < 1 || chunk > _traceback)
105 return -1;
106 _chunksize = chunk;
107 return 0;
108 }
109
traceback(int * metric)110 int viterbi::traceback(int *metric)
111 {
112 int bestmetric, beststate;
113 unsigned int p, c = 0;
114
115 p = (ptr - 1) % PATHMEM;
116
117 // Find the state with the best metric
118 bestmetric = INT_MIN;
119 beststate = 0;
120
121 for (int i = 0; i < nstates; i++) {
122 if (metrics[p][i] > bestmetric) {
123 bestmetric = metrics[p][i];
124 beststate = i;
125 }
126 }
127
128 // Trace back 'traceback' steps, starting from the best state
129 sequence[p] = beststate;
130
131 for (int i = 0; i < _traceback; i++) {
132 unsigned int prev = (p - 1) % PATHMEM;
133
134 sequence[prev] = history[p][sequence[p]];
135 p = prev;
136 }
137
138 if (metric)
139 *metric = metrics[p][sequence[p]];
140
141 // Decode 'chunksize' bits
142 for (int i = 0; i < _chunksize; i++) {
143 // low bit of state is the previous input bit
144 c = (c << 1) | (sequence[p] & 1);
145 p = (p + 1) % PATHMEM;
146 }
147
148 if (metric)
149 *metric = metrics[p][sequence[p]] - *metric;
150
151 return c;
152 }
153
decode(unsigned char * sym,int * metric)154 int viterbi::decode(unsigned char *sym, int *metric)
155 {
156 unsigned int currptr, prevptr;
157 int met[4];
158
159 currptr = ptr;
160 prevptr = (currptr - 1) % PATHMEM;
161 // if (prevptr < 0) prevptr = PATHMEM - 1;
162
163 met[0] = mettab[0][sym[1]] + mettab[0][sym[0]];
164 met[1] = mettab[0][sym[1]] + mettab[1][sym[0]];
165 met[2] = mettab[1][sym[1]] + mettab[0][sym[0]];
166 met[3] = mettab[1][sym[1]] + mettab[1][sym[0]];
167
168 // met[0] = 256 - sym[1] - sym[0];
169 // met[1] = sym[0] - sym[1];
170 // met[2] = sym[1] - sym[0];
171 // met[3] = sym[0] + sym[1] - 256;
172
173 for (int n = 0; n < nstates; n++) {
174 int p0, p1, s0, s1, m0, m1;
175
176 m0 = 0;
177 m1 = 0;
178 s0 = n;
179 s1 = n + nstates;
180
181 p0 = s0 >> 1;
182 p1 = s1 >> 1;
183
184 m0 = metrics[prevptr][p0] + met[output[s0]];
185 m1 = metrics[prevptr][p1] + met[output[s1]];
186
187 if (m0 > m1) {
188 metrics[currptr][n] = m0;
189 history[currptr][n] = p0;
190 } else {
191 metrics[currptr][n] = m1;
192 history[currptr][n] = p1;
193 }
194 }
195
196 ptr = (ptr + 1) % PATHMEM;
197
198 if ((ptr % _chunksize) == 0)
199 return traceback(metric);
200
201 if (metrics[currptr][0] > INT_MAX / 2) {
202 for (int i = 0; i < PATHMEM; i++)
203 for (int j = 0; j < nstates; j++)
204 metrics[i][j] -= INT_MAX / 2;
205 }
206
207 if (metrics[currptr][0] < INT_MIN / 2) {
208 for (int i = 0; i < PATHMEM; i++)
209 for (int j = 0; j < nstates; j++)
210 metrics[i][j] += INT_MIN / 2;
211 }
212
213 return -1;
214 }
215
216 /* ---------------------------------------------------------------------- */
217 #include <iostream>
encoder(int k,int poly1,int poly2)218 encoder::encoder(int k, int poly1, int poly2)
219 {
220 int size = 1 << k; /* size of the output table */
221 output = new int[size];
222 _k = k;
223 _poly1 = poly1;
224 _poly2 = poly2;
225
226 init();
227 }
228
~encoder()229 encoder::~encoder()
230 {
231 delete [] output;
232 }
233
encode(int bit)234 int encoder::encode(int bit)
235 {
236 shreg = (shreg << 1) | !!bit;
237
238 return output[shreg & shregmask];
239 }
240
init(void)241 void encoder::init(void)
242 {
243 if(output) {
244 int size = 1 << _k; /* size of the output table */
245
246 // output contains 2 bits in positions 0 and 1 describing the state machine
247 // for each bit delay, ie: for k = 7 there are 128 possible state pairs.
248 // the modulo-2 addition for polynomial 1 is in bit 0
249 // the modulo-2 addition for polynomial 2 is in bit 1
250 // the allowable state outputs are 0, 1, 2 and 3
251 for (int i = 0; i < size; i++) {
252 output[i] = parity(_poly1 & i) | (parity(_poly2 & i) << 1);
253 }
254 shreg = 0;
255 shregmask = size - 1;
256 }
257 }
258
259
260