1
$\begingroup$

I am trying to understand the equivalence of convolution through polynomial (coefficient) multiplication, Fast Fourier Transforms, and matrix multiplication. I am using octave with the octave-signal package, and part of this question may possibly related to their implementation (which I believe would be the same for MATLAB).

So I create my original signal with length $N$, and my boxcar window length is $n$.

N = 48; 
n = 6; 

I use $\sin$ as the input function for this example.

dt = 2*pi/N;
t = [-N/2:N/2-1]'*dt;
f = sin(t);

Convolution by polynomial multiplication ($g = h \star f$):

h = ones(n,1);
g_conv = conv(h,f);
g_conv_same = conv(f,h,'same');

Convolution by FFT and FFT with zero-padding of the input (also $g = h \star f$):

g_ft = real(ifft(fft(h,N).*fft(f)));

f_padded = [f; zeros(n-1,1)]; % append zeros
g_ft_padded = real(ifft(fft(h,N+n-1).*fft(f_padded)));

Convolution by matrix multiplication ($\mathbf{g} = \mathbf{A} \mathbf{f}$):

A = convmtx(h,N);
g_mtx = A*f;

$\mathbf{A}$ looks like this: convolution matrix

Find indices to trim arrays:

idx_A = find(sum(A,2) == n);
idx_t = 1:length(idx_A);

Plot results (the signals convolved by different methods):

plot(t(idx_t),g_mtx(idx_A),'k','linewidth',3);
line(t-5*dt,g_ft,'color','g','linewidth',2);       %-> offset by 5*dt
line(t-7*dt,g_ft_padded(1:length(t)),'color','r','linestyle','--'); %-> offset by 7*dt
line(t(idx_t),g_conv(idx_A),'color','b','marker','o');
line(t-2*dt,g_conv_same,'color','b','marker','+'); %-> offset by 2*dt
legend({'matrix','FFT','FFT (padded)','conv','conv (same shape)'},...
       'location','southeast')
xlabel('x value')
ylabel('y value')

which looks like this:

plots of convolved signals

I have several questions at this point:

  • Why are the results for the FFT methods offset by several units of dt?
  • If I pad the FFT results such that the input vector is no longer periodic (red dotted line), why do I miss part of the convolved function (on the right side) in the result?
  • How do I treat the ends for the FFT convolution so that the results are aligned with the polynomial and matrix multiplication results?

Thanks in advance. P.S. if there is a good textbook reference for these details I would appreciate your guidance.

(I have edited for clarification.)

$\endgroup$
2
$\begingroup$

A helpful construction is that of a ,,convolution unit''. If you find a signal that, convolved by itself, stays identical, then you know a lot about how your convolution algorithm works. Note that while all discrete units (all ones surrounded by zeros) are convolution units, certain implementations might introduce padding or offsets so that the resulting signal is not identical to itself.

First, let us assume that the signal resulting from a convolution is as long as one of the original signals. It is helpful to assume that the result retains the length of the longer of the input signals. In that case, padding becomes necessary. If you look at the definition of discrete convolution, you will notice that you will have to evaluate undefined portions of the signals. It is customary to fill these up by zeros, or by repeating or reflecting the signal. There are certain merits to each custom.

To meet other requirements (eg. one signal being considered symmetric), one could use other rules, in that case you could add half of the padding left to the other signal, half of it right. Then you might discard some samples and find a signal of same length, again.

This explains how different implementations give different results: padding and result selection are somewhat ,,ad hoc''. Actually, some implementations give the user a choice on how to pad or what part of the signal to return.

FFT convolution is ,,ring convolution''. The time domain wraps around the edges. It implicitly extends the signal rotationally. This explains how it mangles your signal. Offset is a minor problem, as it is easily explained by implementation. If you want an FFT not to disturb signal ,,edges'' (the indices at the extremes of the input array), you have to pad manually, at least as long as the support of the second signal. Note that if one of the signals is shorter, you have to pad it to the same length as well for FFT convolution to be feasible.

So, the phenomena you observed are a consequence of implementation. There is no general answer on how to pad ,,correctly'' or how you could implement convolution so that it does not introduce ,,offset'' - Actually, you're talking about different time domains, and it is a matter of convention how convolved samples are mapped.

$\endgroup$
  • $\begingroup$ Doesn't zero-padding result in interpolation of in the frequency domain? I've tried different sequences of padding (front, back, etc.) but either get mangled results but I am unable to shift the convolved signal. $\endgroup$ – hatmatrix Dec 31 '13 at 16:32
3
$\begingroup$

Convolution and polynomial multiplication are equivalent by definition. Offsets are usually introduced through indexing. The treatment of ends is important.

$\endgroup$
  • $\begingroup$ Thanks; I've clarified my question to ask why this is and how I can address it $\endgroup$ – hatmatrix Dec 29 '13 at 10:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.