libdspl-2.0
Библиотека алгоритмов цифровой обработки сигналов
conv.c
1 /*
2 * Copyright (c) 2015-2019 Sergey Bakhurin
3 * Digital Signal Processing Library [http://dsplib.org]
4 *
5 * This file is part of libdspl-2.0.
6 *
7 * is free software: you can redistribute it and/or modify
8 * it under the terms of the GNU Lesser General Public License as published by
9 * the Free Software Foundation, either version 3 of the License, or
10 * (at your option) any later version.
11 *
12 * DSPL is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 * GNU General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public License
18 * along with Foobar. If not, see <http://www.gnu.org/licenses/>.
19 */
20 
21 #include <stdlib.h>
22 #include <string.h>
23 #include "dspl.h"
24 
25 
26 
27 /*******************************************************************************
28 \ingroup FILTER_CONV_GROUP
29 \fn int conv(double* a, int na, double* b, int nb, double* c)
30 \brief Real vectors linear convolution.
31 
32 Function convolves two real vectors \f$ c = a * b\f$ length `na` and `nb`.
33 The output convolution is a vector `c` with length equal to `na + nb - 1`.
34 
35 \param[in] a Pointer to the first vector `a`. /n
36  Vector size is `[na x 1]`. /n /n
37 
38 \param[in] na Size of the first vector `a`. /n /n
39 
40 \param[in] b Pointer to the second vector `b`. /n
41  Vector size is `[nb x 1]`. /n /n
42 
43 \param[in] nb Size of the second vector `b`. /n /n
44 
45 \param[out] c Pointer to the convolution output vector \f$ c = a * b\f$. /n
46  Vector size is `[na + nb - 1 x 1]`. /n
47  Memory must be allocated. /n /n
48 
49 \return `RES_OK` if convolution is calculated successfully. /n
50 Else \ref ERROR_CODE_GROUP "code error".
51 
52 \note If vectors `a` and `b` are coefficients of two polynomials,
53 then convolution of the vectors `a` and `b` returns polynomial product
54 coefficients.
55 
56 Example:
57 \code{.cpp}
58  double ar[3] = {1.0, 2.0, 3.0};
59  double br[4] = {3.0, -1.0, 2.0, 4.0};
60  double cr[6];
61 
62  int n;
63 
64  conv(ar, 3, br, 4, cr);
65 
66  for(n = 0; n < 6; n++)
67  printf("cr[%d] = %5.1f\n", n, cr[n]);
68 
69 \endcode
70  /n
71 
72 Output:
73 \verbatim
74 cr[0] = 3.0
75 cr[1] = 5.0
76 cr[2] = 9.0
77 cr[3] = 5.0
78 cr[4] = 14.0
79 cr[5] = 12.0
80 \endverbatim
81 
82 \author Sergey Bakhurin www.dsplib.org
83 *******************************************************************************/
84 int DSPL_API conv(double* a, int na, double* b, int nb, double* c)
85 {
86  int k;
87  int n;
88 
89  double *t;
90  size_t bufsize;
91 
92  if(!a || !b || !c)
93  return ERROR_PTR;
94  if(na < 1 || nb < 1)
95  return ERROR_SIZE;
96 
97 
98  bufsize = (na + nb - 1) * sizeof(double);
99 
100  if((a != c) && (b != c))
101  t = c;
102  else
103  t = (double*)malloc(bufsize);
104 
105  memset(t, 0, bufsize);
106 
107  for(k = 0; k < na; k++)
108  for(n = 0; n < nb; n++)
109  t[k+n] += a[k]*b[n];
110 
111  if(t!=c)
112  {
113  memcpy(c, t, bufsize);
114  free(t);
115  }
116  return RES_OK;
117 }
118 
119 
120 
121 
122 
123 
124 /******************************************************************************
125 \ingroup FILTER_CONV_GROUP
126 \fn int conv_cmplx(complex_t* a, int na, complex_t* b, int nb, complex_t* c)
127 \brief Complex vectors linear convolution.
128 
129 Function convolves two complex vectors \f$ c = a * b\f$ length `na` and `nb`.
130 The output convolution is a vector `c` with length equal to `na + nb - 1`.
131 
132 \param[in] a Pointer to the first vector `a`. /n
133  Vector size is `[na x 1]`. /n /n
134 
135 \param[in] na Size of the first vector `a`. /n /n
136 
137 \param[in] b Pointer to the second vector `b`. /n
138  Vector size is `[nb x 1]`. /n /n
139 
140 \param[in] nb Size of the second vector `b`. /n /n
141 
142 \param[out] c Pointer to the convolution output vector \f$ c = a * b\f$. /n
143  Vector size is `[na + nb - 1 x 1]`. /n
144  Memory must be allocated. /n /n
145 
146 \return `RES_OK` if convolution is calculated successfully. /n
147 Else \ref ERROR_CODE_GROUP "code error".
148 
149 \note If vectors `a` and `b` are coefficients of two polynomials,
150 then convolution of the vectors `a` and `b` returns polynomial product
151 coefficients.
152 
153 Example:
154 \code{.cpp}
155  complex_t ac[3] = {{0.0, 1.0}, {1.0, 1.0}, {2.0, 2.0}};
156  complex_t bc[4] = {{3.0, 3.0}, {4.0, 4.0}, {5.0, 5.0}, {6.0, 6.0}};
157  complex_t cc[6];
158 
159  int n;
160 
161  conv_cmplx(ac, 3, bc, 4, cc);
162 
163  for(n = 0; n < 6; n++)
164  printf("cc[%d] = %5.1f%+5.1fj\n", n, RE(cc[n]),IM(cc[n]));
165 
166 \endcode
167  /n
168 
169 Output:
170 \verbatim
171 cc[0] = -3.0 +3.0j
172 cc[1] = -4.0+10.0j
173 cc[2] = -5.0+25.0j
174 cc[3] = -6.0+32.0j
175 cc[4] = 0.0+32.0j
176 cc[5] = 0.0+24.0j
177 \endverbatim
178 
179 \author Sergey Bakhurin www.dsplib.org
180 *******************************************************************************/
181 int DSPL_API conv_cmplx(complex_t* a, int na, complex_t* b,
182  int nb, complex_t* c)
183 {
184  int k;
185  int n;
186 
187  complex_t *t;
188  size_t bufsize;
189 
190  if(!a || !b || !c)
191  return ERROR_PTR;
192  if(na < 1 || nb < 1)
193  return ERROR_SIZE;
194 
195  bufsize = (na + nb - 1) * sizeof(complex_t);
196 
197  if((a != c) && (b != c))
198  t = c;
199  else
200  t = (complex_t*)malloc(bufsize);
201 
202  memset(t, 0, bufsize);
203 
204  for(k = 0; k < na; k++)
205  {
206  for(n = 0; n < nb; n++)
207  {
208  RE(t[k+n]) += CMRE(a[k], b[n]);
209  IM(t[k+n]) += CMIM(a[k], b[n]);
210  }
211  }
212 
213  if(t!=c)
214  {
215  memcpy(c, t, bufsize);
216  free(t);
217  }
218 
219  return RES_OK;
220 }
221 
222 
223 
224 
225 
226 /******************************************************************************
227 \ingroup FILTER_CONV_GROUP
228 \fn int conv_fft(double* a, int na, double* b, int nb,
229  fft_t* pfft, int nfft, double* c)
230 \brief Real vectors fast linear convolution by using fast Fourier
231 transform algorithms
232 
233 Function convolves two real vectors \f$ c = a * b\f$ length `na` and `nb`
234 in the frequency domain by using FFT algorithms. This approach provide
235 high-performance convolution which increases with `na` and `nb` increasing.
236 The output convolution is a vector `c` with length equal to `na + nb - 1`.
237 
238 \param[in] a Pointer to the first vector `a`. /n
239  Vector size is `[na x 1]`. /n /n
240 
241 \param[in] na Size of the first vector `a`. /n /n
242 
243 \param[in] b Pointer to the second vector `b`. /n
244  Vector size is `[nb x 1]`. /n /n
245 
246 \param[in] nb Size of the second vector `b`. /n /n
247 
248 \param[in] pfft Pointer to the structure `fft_t`. /n
249  Function changes `fft_t` structure fields so `fft_t` must
250  be clear before program returns. /n /n
251 
252 \param[in] nfft FFT size. /n
253  This parameter set which FFT size will be used
254  for overlapped frequency domain convolution. /n
255  FFT size must be more of minimal `na` and `nb` value.
256  For example if `na = 10`, `nb = 4` then `nfft` parameter must
257  be more than 4. /n
258 
259 \param[out] c Pointer to the convolution output vector \f$ c = a * b\f$. /n
260  Vector size is `[na + nb - 1 x 1]`. /n
261  Memory must be allocated. /n /n
262 
263 \return `RES_OK` if convolution is calculated successfully. /n
264 Else \ref ERROR_CODE_GROUP "code error". /n /n
265 
266 Example:
267 \include conv_fft_test.c
268 
269 Program output:
270 
271 \verbatim
272 conv_fft error: 0x00000000
273 conv error: 0x00000000
274 c[ 0] = -0.00 d[ 0] = 0.00
275 c[ 1] = -0.00 d[ 1] = 0.00
276 c[ 2] = 1.00 d[ 2] = 1.00
277 c[ 3] = 4.00 d[ 3] = 4.00
278 c[ 4] = 10.00 d[ 4] = 10.00
279 c[ 5] = 20.00 d[ 5] = 20.00
280 c[ 6] = 35.00 d[ 6] = 35.00
281 c[ 7] = 56.00 d[ 7] = 56.00
282 c[ 8] = 77.00 d[ 8] = 77.00
283 c[ 9] = 98.00 d[ 9] = 98.00
284 c[ 10] = 119.00 d[ 10] = 119.00
285 c[ 11] = 140.00 d[ 11] = 140.00
286 c[ 12] = 161.00 d[ 12] = 161.00
287 c[ 13] = 182.00 d[ 13] = 182.00
288 c[ 14] = 190.00 d[ 14] = 190.00
289 c[ 15] = 184.00 d[ 15] = 184.00
290 c[ 16] = 163.00 d[ 16] = 163.00
291 c[ 17] = 126.00 d[ 17] = 126.00
292 c[ 18] = 72.00 d[ 18] = 72.00
293 \endverbatim
294 
295 \author Sergey Bakhurin www.dsplib.org
296 *******************************************************************************/
297 int DSPL_API conv_fft(double* a, int na, double* b, int nb,
298  fft_t* pfft, int nfft, double* c)
299 {
300  complex_t *pa = NULL, *pb = NULL, *pc = NULL;
301  int err;
302 
303  if(!a || !b || !c || !pfft)
304  return ERROR_PTR;
305  if(na<1 || nb < 1)
306  return ERROR_SIZE;
307  if(nfft<2)
308  return ERROR_FFT_SIZE;
309 
310  pa = (complex_t*) malloc(na*sizeof(complex_t));
311  pb = (complex_t*) malloc(nb*sizeof(complex_t));
312  pc = (complex_t*) malloc((na+nb-1)*sizeof(complex_t));
313 
314  re2cmplx(a, na, pa);
315  re2cmplx(b, nb, pb);
316 
317  err = conv_fft_cmplx(pa, na, pb, nb, pfft, nfft, pc);
318  if(err != RES_OK)
319  goto exit_label;
320 
321  err = cmplx2re(pc, na+nb-1, c, NULL);
322 
323 exit_label:
324  if(pa) free(pa);
325  if(pb) free(pb);
326  if(pc) free(pc);
327 
328  return err;
329 }
330 
331 
332 
333 
334 /******************************************************************************
335 \ingroup FILTER_CONV_GROUP
336 \fn int conv_fft_cmplx(complex_t* a, int na, complex_t* b, int nb,
337  fft_t* pfft, int nfft, complex_t* c)
338 \brief Complex vectors fast linear convolution by using fast Fourier
339 transform algorithms
340 
341 Function convolves two complex vectors \f$ c = a * b\f$ length `na` and `nb`
342 in the frequency domain by using FFT algorithms. This approach provide
343 high-performance convolution which increases with `na` and `nb` increasing.
344 The output convolution is a vector `c` with length equal to `na + nb - 1`.
345 
346 \param[in] a Pointer to the first vector `a`. /n
347  Vector size is `[na x 1]`. /n /n
348 
349 \param[in] na Size of the first vector `a`. /n /n
350 
351 \param[in] b Pointer to the second vector `b`. /n
352  Vector size is `[nb x 1]`. /n /n
353 
354 \param[in] nb Size of the second vector `b`. /n /n
355 
356 \param[in] pfft Pointer to the structure `fft_t`. /n
357  Function changes `fft_t` structure fields so `fft_t` must
358  be clear before program returns. /n /n
359 
360 \param[in] nfft FFT size. /n
361  This parameter set which FFT size will be used
362  for overlapped frequency domain convolution. /n
363  FFT size must be more of minimal `na` and `nb` value.
364  For example if `na = 10`, `nb = 4` then `nfft` parameter must
365  be more than 4. /n
366 
367 \param[out] c Pointer to the convolution output vector \f$ c = a * b\f$. /n
368  Vector size is `[na + nb - 1 x 1]`. /n
369  Memory must be allocated. /n /n
370 
371 \return `RES_OK` if convolution is calculated successfully. /n
372 Else \ref ERROR_CODE_GROUP "code error". /n /n
373 
374 Example:
375 \include conv_fft_cmplx_test.c
376 
377 Program output:
378 
379 \verbatim
380 c[ 0] = -1.00 -0.00j d[ 0] = -1.00 +0.00j
381 c[ 1] = -6.00 +4.00j d[ 1] = -6.00 +4.00j
382 c[ 2] = -15.00 +20.00j d[ 2] = -15.00 +20.00j
383 c[ 3] = -28.00 +56.00j d[ 3] = -28.00 +56.00j
384 c[ 4] = -45.00 +120.00j d[ 4] = -45.00 +120.00j
385 c[ 5] = -55.00 +210.00j d[ 5] = -55.00 +210.00j
386 c[ 6] = -65.00 +300.00j d[ 6] = -65.00 +300.00j
387 c[ 7] = -75.00 +390.00j d[ 7] = -75.00 +390.00j
388 c[ 8] = -85.00 +480.00j d[ 8] = -85.00 +480.00j
389 c[ 9] = -95.00 +570.00j d[ 9] = -95.00 +570.00j
390 c[ 10] = -105.00 +660.00j d[ 10] = -105.00 +660.00j
391 c[ 11] = -115.00 +750.00j d[ 11] = -115.00 +750.00j
392 c[ 12] = -125.00 +840.00j d[ 12] = -125.00 +840.00j
393 c[ 13] = -135.00 +930.00j d[ 13] = -135.00 +930.00j
394 c[ 14] = -145.00 +1020.00j d[ 14] = -145.00 +1020.00j
395 c[ 15] = -124.00 +1080.00j d[ 15] = -124.00 +1080.00j
396 c[ 16] = -99.00 +1016.00j d[ 16] = -99.00 +1016.00j
397 c[ 17] = -70.00 +820.00j d[ 17] = -70.00 +820.00j
398 c[ 18] = -37.00 +484.00j d[ 18] = -37.00 +484.00j
399 \endverbatim
400 
401 \author Sergey Bakhurin www.dsplib.org
402 *******************************************************************************/
403 int DSPL_API conv_fft_cmplx(complex_t* a, int na, complex_t* b, int nb,
404  fft_t* pfft, int nfft, complex_t* c)
405 {
406 
407  int La, Lb, Lc, Nz, n, p0, p1, ind, err;
408  complex_t *pa, *pb;
409  complex_t *pt, *pA, *pB, *pC;
410 
411  if(!a || !b || !c)
412  return ERROR_PTR;
413  if(na < 1 || nb < 1)
414  return ERROR_SIZE;
415 
416  if(na >= nb)
417  {
418  La = na;
419  Lb = nb;
420  pa = a;
421  pb = b;
422  }
423  else
424  {
425  La = nb;
426  pa = b;
427  Lb = na;
428  pb = a;
429  }
430 
431  Lc = La + Lb - 1;
432  Nz = nfft - Lb;
433 
434  if(Nz <= 0)
435  return ERROR_FFT_SIZE;
436 
437  pt = (complex_t*)malloc(nfft*sizeof(complex_t));
438  pB = (complex_t*)malloc(nfft*sizeof(complex_t));
439  pA = (complex_t*)malloc(nfft*sizeof(complex_t));
440  pC = (complex_t*)malloc(nfft*sizeof(complex_t));
441 
442  memset(pt, 0, nfft*sizeof(complex_t));
443  memcpy(pt+Nz, pb, Lb*sizeof(complex_t));
444 
445  err = fft_cmplx(pt, nfft, pfft, pB);
446  if(err != RES_OK)
447  goto exit_label;
448 
449  p0 = -Lb;
450  p1 = p0 + nfft;
451  ind = 0;
452  while(ind < Lc)
453  {
454  if(p0 >=0)
455  {
456  if(p1 < La)
457  err = fft_cmplx(pa + p0, nfft, pfft, pA);
458  else
459  {
460  memset(pt, 0, nfft*sizeof(complex_t));
461  memcpy(pt, pa+p0, (nfft+La-p1)*sizeof(complex_t));
462  err = fft_cmplx(pt, nfft, pfft, pA);
463  }
464  }
465  else
466  {
467  memset(pt, 0, nfft*sizeof(complex_t));
468  if(p1 < La)
469  memcpy(pt - p0, pa, (nfft+p0)*sizeof(complex_t));
470  else
471  memcpy(pt - p0, pa, La * sizeof(complex_t));
472  err = fft_cmplx(pt, nfft, pfft, pA);
473  }
474 
475  if(err != RES_OK)
476  goto exit_label;
477 
478  for(n = 0; n < nfft; n++)
479  {
480  RE(pC[n]) = CMRE(pA[n], pB[n]);
481  IM(pC[n]) = CMIM(pA[n], pB[n]);
482  }
483 
484 
485  if(ind+nfft < Lc)
486  err = ifft_cmplx(pC, nfft, pfft, c+ind);
487  else
488  {
489  err = ifft_cmplx(pC, nfft, pfft, pt);
490  memcpy(c+ind, pt, (Lc-ind)*sizeof(complex_t));
491  }
492  if(err != RES_OK)
493  goto exit_label;
494 
495  p0 += Nz;
496  p1 += Nz;
497  ind += Nz;
498  }
499 
500 exit_label:
501  if(pt) free(pt);
502  if(pB) free(pB);
503  if(pA) free(pA);
504  if(pC) free(pC);
505 
506  return err;
507 }
508 
509 
510 
511 
512 /*******************************************************************************
513 \ingroup FILTER_CONV_GROUP
514 \fn int filter_iir(double* b, double* a, int ord, double* x, int n, double* y)
515 \brief Real IIR filtration
516 
517 Function calculates real IIR filter output for real signal. The real filter
518 contains real coefficients of the transfer function \f$H(z)\f$
519  numerator and denominator:
520 \f[
521  H(z) = \frac{\sum_{n = 0}^{N} b_n z^{-n}}
522  {1+{\frac{1}{a_0}}\sum_{m = 1}^{M} a_m z^{-n}},
523 \f]
524 here \f$a_0\f$ cannot be equals zeros, \f$N=M=\f$`ord`.
525 
526 
527 \param[in] b Pointer to the vector \f$b\f$ of IIR filter
528  transfer function numerator coefficients. /n
529  Vector size is `[ord + 1 x 1]`. /n /n
530 
531 \param[in] a Pointer to the vector \f$a\f$ of IIR filter
532  transfer function denominator coefficients. /n
533  Vector size is `[ord + 1 x 1]`. /n
534  This pointer can be `NULL` if filter is FIR. /n /n
535 
536 \param[in] ord Filter order. Number of the transfer function
537  numerator and denominator coefficients
538  (length of vectors `b` and `a`) is `ord + 1`. /n /n
539 
540 \param[in] x Pointer to the input signal vector. /n
541  Vector size is `[n x 1]`. /n /n
542 
543 \param[in] n Size of the input signal vector `x`. /n /n
544 
545 \param[out] y Pointer to the IIR filter output vector. /n
546  Vector size is `[n x 1]`. /n
547  Memory must be allocated. /n /n
548 \return
549 `RES_OK` if filter output is calculated successfully. /n
550 Else \ref ERROR_CODE_GROUP "code error": /n
551 
552 Example:
553 
554 \include filter_iir_test.c
555 
556 Input signal is
557 \f$s(t) = \sin(2\pi \cdot 0.05 t) + n(t)\f$, here \f$n(t)\f$ white Gaussian
558 noise with zero mean value and unit standard deviation. \n
559 
560 Input signal is filtered by elliptic LPF order 6 and output signal and data
561 saves in the txt-files
562 
563 \verbatim
564 dat/s.txt - input signal + noise
565 dat/sf.txt - filter output.
566 \endverbatim
567 
568 Plots:
569 
570 \image html filter_iir_test.png
571 
572 GNUPLOT script for make plots is:
573 \include filter_iir.plt
574 
575 \author Sergey Bakhurin www.dsplib.org
576 *******************************************************************************/
577 int DSPL_API filter_iir(double* b, double* a, int ord,
578  double* x, int n, double* y)
579 {
580  double* buf = NULL;
581  double* an = NULL;
582  double u;
583  int k;
584  int m;
585  int count;
586 
587  if(!b || !x || !y)
588  return ERROR_PTR;
589 
590  if(ord < 1 || n < 1)
591  return ERROR_SIZE;
592 
593  if(a && a[0]==0.0)
594  return ERROR_FILTER_A0;
595 
596  count = ord + 1;
597  buf = (double*) malloc(count*sizeof(double));
598  an = (double*) malloc(count*sizeof(double));
599 
600  memset(buf, 0, count*sizeof(double));
601 
602  if(!a)
603  memset(an, 0, count*sizeof(double));
604  else
605  for(k = 0; k < count; k++)
606  an[k] = a[k] / a[0];
607 
608  for(k = 0; k < n; k++)
609  {
610  for(m = ord; m > 0; m--)
611  buf[m] = buf[m-1];
612  u = 0.0;
613  for(m = ord; m > 0; m--)
614  u += buf[m]*an[m];
615 
616  buf[0] = x[k] - u;
617  y[k] = 0.0;
618  for(m = 0; m < count; m++)
619  y[k] += buf[m] * b[m];
620  }
621 
622  if(buf)
623  free(buf);
624  if(an)
625  free(an);
626  return RES_OK;
627 }
628 
#define ERROR_SIZE
Ошибка при передаче размера массива. Данная ошибка возникает когда помимо указателя на массив входных...
Definition: dspl.h:148
Структура данных объекта быстрого преобразования Фурье
Definition: dspl.h:46
double complex_t[2]
Описание комплексного типа данных.
Definition: dspl.h:41
int fft_cmplx(complex_t *x, int n, fft_t *pfft, complex_t *y)
Быстрое преобразование Фурье комплексного сигнала
Definition: fft.c:92
#define ERROR_PTR
Ошибка указателя. Данная ошибка означает, что один из обязательных указателей (память под который дол...
Definition: dspl.h:140
int filter_iir(double *b, double *a, int ord, double *x, int n, double *y)
Фильтрация вещественного сигнала вещественным БИХ-фильтром
Definition: conv.c:577
#define IM(x)
Макрос определяющий мнимую часть комплексного числа.
Definition: dspl.h:78
#define RE(x)
Макрос определяющий реальную часть комплексного числа.
Definition: dspl.h:77
int re2cmplx(double *x, int n, complex_t *y)
Преобразование массива вещественных данных в массив комплексных данных.
Definition: complex.c:441
int ifft_cmplx(complex_t *x, int n, fft_t *pfft, complex_t *y)
Обратное быстрое преобразование Фурье
Definition: fft.c:30
int cmplx2re(complex_t *x, int n, double *re, double *im)
Преобразование массива комплексных данных в два массива вещественных данных, содержащих реальную и мн...
Definition: complex.c:222
int conv(double *a, int na, double *b, int nb, double *c)
Линейная свертка двух вещественных векторов
Definition: conv.c:84
int conv_cmplx(complex_t *a, int na, complex_t *b, int nb, complex_t *c)
Линейная свертка двух комплексных векторов
Definition: conv.c:181
#define ERROR_FFT_SIZE
Неверно задан размер БПФ.
Definition: dspl.h:107
#define ERROR_FILTER_A0
Коэффициент знаменателя передаточной функции фильтра равен нулю. Необходимо задать параметр отличны...
Definition: dspl.h:108
#define RES_OK
Функция завершилась корректно. Ошибки отсутствуют.
Definition: dspl.h:94