Using 1D convolutional with same shape so it will work with FFT?

Question

I'm trying to make conv(x, k, 'same') result the same as FFT. But I notice that this only works for the shape full and not for same.

% Create vector and kernel
x = randn(1, 100); 
k = randn(1, 10);  

% Do 1D conv
y_conv = conv(x, k, 'full');

% Do 1D FFT
N = length(x) + length(k) - 1;
X = fft(x, N);
K = fft(k, N);
Y_fft = ifft(X .* K);

% Compare
max_diff = max(abs(y_conv - Y_fft));
disp(['The maximal difference is: ' num2str(max_diff)]);

The reason why I want to have same, is because my output data need to be the same as input data.

Question:

What need to be done/changed, for make FFT result the same as conv(x, k, 'same')?

Answer 1

“Same” pads with zeros. You need to pad your input with at least K-1 zeros (if your kernel has length K), then do the FFT convolution, and finally crop the result to the expected size.

fft(x, N) pads with zeros on the right when N > length(x). So you will need to crop from the right. But because of the way that fft(k, N) works, the origin of the kernel is on the first sample, rather than the middle as assumed by “same”. So the result is shifted. You will thus need to remove some samples from the left side as well, probably (K-1)/2 samples assuming K is odd.