SDRAngel  4.11.5
Developer docs for <a href="https://github.com/f4exb/sdrangel">SDRangel<\a>, an Open Source Qt5 / OpenGL 3.0+ SDR and signal analyzer frontend to various hardware.
convolutional.h
Go to the documentation of this file.
1 // This file is part of LeanSDR Copyright (C) 2016-2018 <pabr@pabr.org>.
2 // See the toplevel README for more information.
3 //
4 // This program is free software: you can redistribute it and/or modify
5 // it under the terms of the GNU General Public License as published by
6 // the Free Software Foundation, either version 3 of the License, or
7 // (at your option) any later version.
8 //
9 // This program is distributed in the hope that it will be useful,
10 // but WITHOUT ANY WARRANTY; without even the implied warranty of
11 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 // GNU General Public License for more details.
13 //
14 // You should have received a copy of the GNU General Public License
15 // along with this program. If not, see <http://www.gnu.org/licenses/>.
16 
17 #ifndef LEANSDR_CONVOLUTIONAL_H
18 #define LEANSDR_CONVOLUTIONAL_H
19 
20 #include "framework.h"
21 #include "sdr.h"
22 
23 namespace leansdr
24 {
25 
26 // ALGEBRAIC DECONVOLUTION
27 
28 // QPSK 1/2 only.
29 // This is a straightforward implementation, provided for reference.
30 // deconvol_poly2 is functionally equivalent and much faster.
31 
32 template <typename Tin, // Input IQ symbols
33  typename Thist, // Input shift register (IQIQIQ...)
34  Thist POLY_DECONVOL, // Taps (IQIQIQ...)
35  Thist POLY_ERRORS>
37 {
38  typedef u8 hardsymbol;
39 
40  // Support soft of float input
41  inline u8 SYMVAL(const hardsymbol *s) { return *s; }
42  inline u8 SYMVAL(const softsymbol *s) { return s->symbol; }
43 
44  typedef u8 decoded_byte;
45 
46  deconvol_poly() : hist(0) {}
47 
48  // Remap and deconvolve [nb*8] symbols into [nb] bytes.
49  // Return estimated number of bit errors.
50 
51  int run(const Tin *pin, const u8 remap[], decoded_byte *pout, int nb)
52  {
53  int nerrors = 0;
54  int halfway = nb / 2;
55 
56  for (; nb--; ++pout)
57  {
58  decoded_byte byte = 0;
59 
60  for (int bit = 8; bit--; ++pin)
61  {
62  hist = (hist << 2) | remap[SYMVAL(pin)];
63  byte = (byte << 1) | parity(hist & POLY_DECONVOL);
64  if (nb < halfway)
65  nerrors += parity(hist & POLY_ERRORS);
66  }
67 
68  *pout = byte;
69  }
70 
71  return nerrors;
72  }
73 
74  private:
75  Thist hist;
76 
77 }; // deconvol_poly
78 
79 // ALGEBRAIC DECONVOLUTION, OPTIMIZED
80 
81 // QPSK 1/2 only.
82 // Functionally equivalent to deconvol_poly,
83 // but processing 32 bits in parallel.
84 
85 template <typename Tin, // Input IQ symbols
86  typename Thist, // Input shift registers (one for I, one for Q)
87  typename Tpoly, // Taps (interleaved IQIQIQ...)
88  Tpoly POLY_DECONVOL,
89  Tpoly POLY_ERRORS>
91 {
92  typedef u8 hardsymbol;
93 
94  // Support instanciation of template with soft of float input
95  inline u8 SYMVAL(const hardsymbol *s) { return *s; }
96  inline u8 SYMVAL(const softsymbol *s) { return s->symbol; }
97 
98  typedef u8 decoded_byte;
99 
100  deconvol_poly2() : inI(0), inQ(0) {}
101 
102  // Remap and deconvolve [nb*8] symbols into [nb] bytes.
103  // Return estimated number of bit errors.
104 
105  int run(const Tin *pin, const u8 remap[], decoded_byte *pout, int nb)
106  {
107  if (nb & (sizeof(Thist) - 1)) {
108  fail("Must deconvolve sizeof(Thist) bytes at a time");
109  }
110 
111  nb /= sizeof(Thist);
112  unsigned long nerrors = 0;
113  int halfway = nb / 2;
114  Thist histI = inI, histQ = inQ;
115 
116  for (; nb--;)
117  {
118  // This is where we convolve bits in parallel.
119  Thist wd = 0; // decoded bits
120  Thist we = 0; // error bits (should be 0)
121 #if 0
122  // Trust gcc to unroll and evaluate the bit tests at compile-time.
123  for ( int bit=sizeof(Thist)*8; bit--; ++pin ) {
124  u8 iq = remap[SYMVAL(pin)];
125  histI = (histI<<1) | (iq>>1);
126  histQ = (histQ<<1) | (iq&1);
127  if ( POLY_DECONVOL & ((Tpoly)2<<(2*bit)) ) wd ^= histI;
128  if ( POLY_DECONVOL & ((Tpoly)1<<(2*bit)) ) wd ^= histQ;
129  if ( POLY_ERRORS & ((Tpoly)2<<(2*bit)) ) we ^= histI;
130  if ( POLY_ERRORS & ((Tpoly)1<<(2*bit)) ) we ^= histQ;
131  }
132 #else
133  // Unroll manually.
134 #define LOOP(bit) \
135  { \
136  u8 iq = remap[SYMVAL(pin)]; \
137  histI = (histI << 1) | (iq >> 1); \
138  histQ = (histQ << 1) | (iq & 1); \
139  if (POLY_DECONVOL & ((Tpoly)2 << (2 * bit))) \
140  wd ^= histI; \
141  if (POLY_DECONVOL & ((Tpoly)1 << (2 * bit))) \
142  wd ^= histQ; \
143  if (POLY_ERRORS & ((Tpoly)2 << (2 * bit))) \
144  we ^= histI; \
145  if (POLY_ERRORS & ((Tpoly)1 << (2 * bit))) \
146  we ^= histQ; \
147  ++pin; \
148  }
149  // Don't shift by more than the operand width
150  switch (sizeof(Thist) * 8)
151  {
152 #if 0 // Not needed yet - avoid compiler warnings
153  case 64:
154  LOOP(63); LOOP(62); LOOP(61); LOOP(60);
155  LOOP(59); LOOP(58); LOOP(57); LOOP(56);
156  LOOP(55); LOOP(54); LOOP(53); LOOP(52);
157  LOOP(51); LOOP(50); LOOP(49); LOOP(48);
158  LOOP(47); LOOP(46); LOOP(45); LOOP(44);
159  LOOP(43); LOOP(42); LOOP(41); LOOP(40);
160  LOOP(39); LOOP(38); LOOP(37); LOOP(36);
161  LOOP(35); LOOP(34); LOOP(33); LOOP(32);
162  // Fall-through
163 #endif
164  case 32:
165  LOOP(31);
166  LOOP(30);
167  LOOP(29);
168  LOOP(28);
169  LOOP(27);
170  LOOP(26);
171  LOOP(25);
172  LOOP(24);
173  LOOP(23);
174  LOOP(22);
175  LOOP(21);
176  LOOP(20);
177  LOOP(19);
178  LOOP(18);
179  LOOP(17);
180  LOOP(16);
181  // Fall-through
182  case 16:
183  LOOP(15);
184  LOOP(14);
185  LOOP(13);
186  LOOP(12);
187  LOOP(11);
188  LOOP(10);
189  LOOP(9);
190  LOOP(8);
191  // Fall-through
192  case 8:
193  LOOP(7);
194  LOOP(6);
195  LOOP(5);
196  LOOP(4);
197  LOOP(3);
198  LOOP(2);
199  LOOP(1);
200  LOOP(0);
201  break;
202  default:
203  fail("Thist not supported");
204  }
205 #undef LOOP
206 #endif
207  switch (sizeof(Thist) * 8)
208  {
209 #if 0 // Not needed yet - avoid compiler warnings
210  case 64:
211  *pout++ = wd >> 56;
212  *pout++ = wd >> 48;
213  *pout++ = wd >> 40;
214  *pout++ = wd >> 32;
215  // Fall-through
216 #endif
217  case 32:
218  *pout++ = wd >> 24;
219  *pout++ = wd >> 16;
220  // Fall-through
221  case 16:
222  *pout++ = wd >> 8;
223  // Fall-through
224  case 8:
225  *pout++ = wd;
226  break;
227  default:
228  fail("Thist not supported");
229  }
230  // Count errors when the shift registers are full
231  if (nb < halfway)
232  nerrors += hamming_weight(we);
233  }
234 
235  inI = histI;
236  inQ = histQ;
237  return nerrors;
238  }
239 
240  private:
241  Thist inI, inQ;
242 }; // deconvol_poly2
243 
244 // CONVOLUTIONAL ENCODER
245 
246 // QPSK 1/2 only.
247 
248 template <typename Thist, uint64_t POLY1, uint64_t POLY2>
250 {
251  typedef u8 uncoded_byte;
252  typedef u8 hardsymbol;
253 
254  convol_poly2() : hist(0) {}
255 
256  // Convolve [count] bytes into [count*8] symbols, and remap.
257 
258  void run(const uncoded_byte *pin, const u8 remap[],
259  hardsymbol *pout, int count)
260  {
261  for (; count--; ++pin)
262  {
263  uncoded_byte b = *pin;
264 
265  for (int bit = 8; bit--; ++pout)
266  {
267  hist = (hist >> 1) | (((b >> bit) & 1) << 6);
268  u8 s = (parity(hist & POLY1) << 1) | parity(hist & POLY2);
269  *pout = remap[s];
270  }
271  }
272  }
273 
274  private:
275  Thist hist;
276 }; // convol_poly2
277 
278 // Generic BPSK..256QAM and puncturing
279 
280 template <typename Thist, int HISTSIZE>
282 {
283  typedef u8 uncoded_byte;
284  typedef u8 hardsymbol;
285  int bits_in, bits_out, bps;
286  const Thist *polys; // [bits_out]
287 
289  : bits_in(0), bits_out(0), bps(0),
290  hist(0), nhist(0), sersymb(0), nsersymb(0)
291  {
292  }
293 
294  void encode(const uncoded_byte *pin, hardsymbol *pout, int count)
295  {
296  if (!bits_in || !bits_out || !bps) {
297  fatal("convol_multipoly not configured");
298  }
299 
300  hardsymbol symbmask = (1 << bps) - 1;
301 
302  for (; count--; ++pin)
303  {
304  uncoded_byte b = *pin;
305 
306  for (int bit = 8; bit--;)
307  {
308  hist = (hist >> 1) | ((Thist)((b >> bit) & 1) << (HISTSIZE - 1));
309  ++nhist;
310 
311  if (nhist == bits_in)
312  {
313  for (int p = 0; p < bits_out; ++p)
314  {
315  int b = parity((Thist)(hist & polys[p]));
316  sersymb = (sersymb << 1) | b;
317  }
318 
319  nhist = 0;
320  nsersymb += bits_out;
321 
322  while (nsersymb >= bps)
323  {
324  hardsymbol s = (sersymb >> (nsersymb - bps)) & symbmask;
325  *pout++ = s;
326  nsersymb -= bps;
327  }
328  }
329  }
330  }
331  // Ensure deterministic output size
332  // TBD We can relax this
333  if (nhist || nsersymb) {
334  fatal("partial run");
335  }
336  }
337 
338  private:
339  Thist hist;
340  int nhist;
341  Thist sersymb;
342  int nsersymb;
343 }; // convol_multipoly
344 
345 } // namespace leansdr
346 
347 #endif // LEANSDR_CONVOLUTIONAL_H
u8 SYMVAL(const hardsymbol *s)
Definition: convolutional.h:95
void run(const uncoded_byte *pin, const u8 remap[], hardsymbol *pout, int count)
int run(const Tin *pin, const u8 remap[], decoded_byte *pout, int nb)
Definition: convolutional.h:51
unsigned char u8
Definition: framework.h:453
int hamming_weight(uint8_t x)
Definition: math.cpp:6
u8 SYMVAL(const softsymbol *s)
Definition: convolutional.h:96
void encode(const uncoded_byte *pin, hardsymbol *pout, int count)
u8 SYMVAL(const softsymbol *s)
Definition: convolutional.h:42
void fail(const char *s)
Definition: framework.cpp:11
int run(const Tin *pin, const u8 remap[], decoded_byte *pout, int nb)
void fatal(const char *s)
Definition: framework.cpp:6
unsigned char parity(uint8_t x)
Definition: math.cpp:27
u8 SYMVAL(const hardsymbol *s)
Definition: convolutional.h:41
uint8_t symbol
Definition: sdr.h:396
#define LOOP(bit)