ggkmath - 1 year ago 191
C Question

# 1d linear convolution in ANSI C code?

Rather than reinvent the wheel, I wonder if anyone could refer me to a 1D linear convolution code snippet in ANSI C? I did a search on google and in stack overflow, but couldn't find anything in C I could use.

For example, for Arrays A, B, and C, all double-precision, where A and B are inputs and C is output, having lengths

`len_A`
,
`len_B`
, and
`len_C = len_A + len_B - 1`
, respectively.

My array sizes are small and so any speed increase in implementing fast convolution by FFT is not needed. Looking for straightforward computation.

Here's how:

``````#include <stddef.h>
#include <stdio.h>

void convolve(const double Signal[/* SignalLen */], size_t SignalLen,
const double Kernel[/* KernelLen */], size_t KernelLen,
double Result[/* SignalLen + KernelLen - 1 */])
{
size_t n;

for (n = 0; n < SignalLen + KernelLen - 1; n++)
{
size_t kmin, kmax, k;

Result[n] = 0;

kmin = (n >= KernelLen - 1) ? n - (KernelLen - 1) : 0;
kmax = (n < SignalLen - 1) ? n : SignalLen - 1;

for (k = kmin; k <= kmax; k++)
{
Result[n] += Signal[k] * Kernel[n - k];
}
}
}

void printSignal(const char* Name,
double Signal[/* SignalLen */], size_t SignalLen)
{
size_t i;

for (i = 0; i < SignalLen; i++)
{
printf("%s[%zu] = %f\n", Name, i, Signal[i]);
}
printf("\n");
}

#define ELEMENT_COUNT(X) (sizeof(X) / sizeof((X)[0]))

int main(void)
{
double signal[] = { 1, 1, 1, 1, 1 };
double kernel[] = { 1, 1, 1, 1, 1 };
double result[ELEMENT_COUNT(signal) + ELEMENT_COUNT(kernel) - 1];

convolve(signal, ELEMENT_COUNT(signal),
kernel, ELEMENT_COUNT(kernel),
result);

printSignal("signal", signal, ELEMENT_COUNT(signal));
printSignal("kernel", kernel, ELEMENT_COUNT(kernel));
printSignal("result", result, ELEMENT_COUNT(result));

return 0;
}
``````

Output:

``````signal[0] = 1.000000
signal[1] = 1.000000
signal[2] = 1.000000
signal[3] = 1.000000
signal[4] = 1.000000

kernel[0] = 1.000000
kernel[1] = 1.000000
kernel[2] = 1.000000
kernel[3] = 1.000000
kernel[4] = 1.000000

result[0] = 1.000000
result[1] = 2.000000
result[2] = 3.000000
result[3] = 4.000000
result[4] = 5.000000
result[5] = 4.000000
result[6] = 3.000000
result[7] = 2.000000
result[8] = 1.000000
``````
Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download