Interpolation through fourier space padding

问题:

I recently tried to implement on matlab a simple example of interpolation method using zéro padding in the fourier domain. But I am not able to get this work properly, I always have a small frequency shift, barely not visible in fourier space, but thay generates a huge error in time space.

As zéro padding in the fourier space seems to be a common (and fast) interpolation method, I assume that there is something I am missing:

Here is the matlab code:

clc;
clear all;
close all;


Fe = 3250;
Te = 1/Fe;
Nech = 100;

F1 = 500;
F2 = 1000;
FMax = 1500;

time = [0:Te:(Nech-1)*Te];
timeDiscrete = [1:1:Nech];
frequency = (timeDiscrete/Nech)*Fe;

signal = cos(2*pi*F1*(time))+cos(2*pi*F2*(time))+cos(2*pi*FMax*(time));

%Compute the FFT
spectrum=zeros(1,Nech);
for k = timeDiscrete
    for l = timeDiscrete
        spectrum(k) = spectrum(k) + signal(l)*exp(-2*pi*j*l*k/Nech);
    end
end

%Compute de inverse FFT
reconstruction=zeros(1,Nech);
for k = timeDiscrete
    for l = timeDiscrete
        reconstruction(k) = reconstruction(k) + spectrum(l)*exp(2*pi*j*l*k/Nech);
    end
end
reconstruction=reconstruction/Nech;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%    Now interpolation will take place   %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Finterp = 6*Fe;
Tinterp = 1/Finterp;
TimeInterp = [0:Tinterp:(Nech-1)*Te];
[m,n] = size(TimeInterp);
NechInterp = n;
TimeInterpDiscrete = [1:1:NechInterp];

%Compute original signal value without any interpolation
signalResampled = cos(2*pi*F1*(TimeInterp))+cos(2*pi*F2*(TimeInterp))+cos(2*pi*FMax*(TimeInterp));

%Compute original signal interpolation by padding the fft and performing
%inverse fft on the result
semipaddedsize=floor(NechInterp/2);
padded_spectrum0 = zeros(1,semipaddedsize);
padded_spectrum0 = padarray(spectrum(1:Nech/2),[0 semipaddedsize-(Nech/2)],0,'post');
padded_spectrum = zeros(1,NechInterp);
padded_spectrum(1:semipaddedsize) = padded_spectrum0;
padded_spectrum(semipaddedsize+1:NechInterp-1) = conj(fliplr(padded_spectrum0));
% padded_spectrum = padarray(spectrum,[0 NechInterp-Nech],0,'post');
padded_timeDiscrete = [1:1:NechInterp];
padded_reconstruction = zeros(1,NechInterp);


for k = padded_timeDiscrete
    for l = padded_timeDiscrete
        padded_reconstruction(k) = padded_reconstruction(k) + padded_spectrum(l)*exp(2*pi*j*l*k/NechInterp);
    end
end
padded_reconstruction=padded_reconstruction/(1*Nech);


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%       Let's print out the result       %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

spectrumresampled=zeros(1,NechInterp);
for k = TimeInterpDiscrete
    for l = TimeInterpDiscrete
        spectrumresampled(k) = spectrumresampled(k) + signalResampled(l)*exp(-2*pi*j*l*k/NechInterp);
    end
end

figure(2);
plot(abs(spectrumresampled)/6,'g');
hold on;
plot(abs(padded_spectrum),'b');

figure(3);

% Ground truth : deterministic signal is recomputed
plot(TimeInterp,signalResampled,'g');
hold on;
% linear interpolation between subsampled points (matlab tracing tool)
plot(time,(reconstruction),'c');
hold on;
% Padding the spectrum and reconstructing it 
plot(TimeInterp,real(padded_reconstruction),'m');
hold on;

xlabel('Time in s','FontSize',16)
ylabel('Signal value (no unit)','FontSize',16)
title('\it{ Various signal reconstruction from fourier transform }','FontSize',16)
legend('True signal', 'Reconstruction with linear interpolation', 'Reconstruction with padded spectrum');

I am not able to post images of the result because of my reputation, but, graph are easy to generates, through matlab. I would really appreciate a comment on either this code or zero padding fft for interpolation in general.

Thank you in advance

回答1:

Thank you very much for both of you for those advices, I decided to respond my own question because the was not enough space available in coment box:

@Try hard I indeed defined a wrong discrete Time vector, as @Frederick also pointed out, I had a problem in padding my vector, thank you for giving me the right "matlab way" to do it, I should not have been so afraid of fftshift/ifftshift, in addition, the use of padarray with 'both' would also have done the job, as mentionned by @Frederick .

Collapsing the for loop was also an essential step for proper matlab implementation, that I don't use in training purpose to ease my understanding and bound checking.

An additionnal very interesting point @Try hard mentionned in its first sentence, and that I did not realised in the first place, is the fact, that zero padding is just the equivalent of convoluting my data in time domain by a sinc function.

Actually I think that it is literraly equivalent to a convolution with an aliased sinc function, also called dirichlet kernel, which limits, when sampling frequency increase towards infinity, is the classic sinc function (see http://www.dsprelated.com/dspbooks/sasp/Rectangular_Window_I.html#sec:rectwinintro)

I did not posted the whole code here, but the purpose of my original program was to compare dirichlet kernel convolution formula, that I demonstrated in a different framework (theoretical demonstration using fourier series discrete expression) , sinc convolution Whittaker–Shannon interpolation formula, and zero padding, so I should be given with a very similar result.

To the apodization question, I think that the true answer is that, if your signal is bandlimited, you don't need other apodization function than rectangular window.

If your signal is not bandlimited, or aliased regarding the sampling rate, you will need to reduce the contribution of aliased part of the spectrum, which is done by filtering them out with a frequency filter = apodizing window in frequency domain, wich turns into a specific interpolation kernels in time domain.

回答2:

OK. One problem was the way you were doing the IDFT for padded_reconstruction. The way that you defined TimeInterp and thus NechInterp made the elements of the complex exponent incorrect. That accounts for the incorrect frequencies.

Then there was an issue with including the midpoint in the fourier domain (pt 50) twice. It was near zero, so it wasn't making a hugely obvious problem, but it should only be included once. I rewrote this section because I was having a hard time working it through exactly the way you did it. I kept it very close though. If I were doing this, I would use fftshift and then padarray(...,'both'), which would save the work of having to put the zeros in the middle. If you are doing this for a learning experience and trying not to use matlab tools (e.g. fftshift), then nevermind.

I also redid the way you define time, but to be fair, I think it could work your way.

I've indicated changes with %<<<<<<<<<<

Fe = 3250;
Te = 1/Fe;
Nech = 100;

F1 = 500;
F2 = 1000;
FMax = 1500;

time = [Te:Te:(Nech)*Te];  %<<<<<<<<<<
timeDiscrete = [1:1:Nech];
frequency = (timeDiscrete/Nech)*Fe;

signal = cos(2*pi*F1*(time))+cos(2*pi*F2*(time))+cos(2*pi*FMax*(time));

%Compute the FFT
spectrum=zeros(1,Nech);
for k = timeDiscrete
    for l = timeDiscrete
        spectrum(k) = spectrum(k) + signal(l)*exp(-2*pi*j*l*k/Nech);
    end
end

%Compute de inverse FFT
reconstruction=zeros(1,Nech);
for k = timeDiscrete
    for l = timeDiscrete
        reconstruction(k) = reconstruction(k) + spectrum(l)*exp(2*pi*j*l*k/Nech);
    end
end
reconstruction=reconstruction/Nech;

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%    Now interpolation will take place   %%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

Finterp = 6*Fe;
Tinterp = 1/Finterp;
TimeInterp = [Tinterp:Tinterp:(Nech*6)*Tinterp];  %<<<<<<<<<<
[m,n] = size(TimeInterp);
NechInterp = n;
TimeInterpDiscrete = [1:1:NechInterp];

%Compute original signal value without any interpolation
signalResampled = cos(2*pi*F1*(TimeInterp))+cos(2*pi*F2*(TimeInterp))+cos(2*pi*FMax*(TimeInterp));

%Compute original signal interpolation by padding the fft and performing
%inverse fft on the result
padded_spectrum = zeros(1,NechInterp); %<<<<<<<<<<
padded_spectrum(1:floor(Nech/2-1)) = spectrum(1:floor(Nech/2-1)); %<<<<<<<<<<
padded_spectrum(end-floor(Nech/2)+1:end) = spectrum(floor(Nech/2)+1:end); %<<<<<<<<<<

padded_reconstruction = zeros(1,NechInterp);
for k = TimeInterpDiscrete %<<<<<<<<<<(no reason for new variable)
    for l = TimeInterpDiscrete %<<<<<<<<<<(no reason for new variable)
        padded_reconstruction(k) = padded_reconstruction(k) + padded_spectrum(l)*exp(2*pi*j*l*k/NechInterp);
    end
end
padded_reconstruction=padded_reconstruction/(1*Nech);

回答3:

The result you observe in the time domain is ringing due to convolution of a sinc function with your original data. This is the equivalent in the time domain of multiplication by a rectangular window in the frequency domain, which is in effect what you are doing when you zero fill. Don't forget to apodize!

I repost your code after collapsing the loops (which accelerates the computation significantly), redefining the ranges of the time and frequency variables (see the definition of DFT to see why), and removing one of the padding operations you perform which I frankly did not understand the point off.

clc;
clear all;
close all;

Fe = 3250;
Te = 1/Fe;
Nech = 100;
mlt = 10;
F1 = 50; 
F2 = 100; 
FMax = 150; 

time = [0:Te:(Nech-1)*Te];
%timeDiscrete = [1:1:Nech];
timeDiscrete = [0:1:Nech-1];
frequency = (timeDiscrete/Nech)*Fe;

signal = cos(2*pi*F1*(time))+cos(2*pi*F2*(time))+cos(2*pi*FMax*(time));
spectrum =  signal*exp(-2*pi*j*timeDiscrete'*timeDiscrete/Nech);
fspec = [0:Nech-1]*Fe/Nech;
reconstruction = spectrum*exp(2*pi*j*timeDiscrete'*timeDiscrete/Nech)/Nech;

figure
plot(time,signal)
hold on
plot(time,reconstruction,'g:')

% **** interpolation ****

Finterp = 6*Fe;
Tinterp = 1/Finterp;
TimeInterp = [0:Tinterp:(Nech-1)*Te];
NechInterp = length(TimeInterp);
%TimeInterpDiscrete = [1:NechInterp];
TimeInterpDiscrete = [0:NechInterp-1];

%Compute original signal value without any interpolation
signalResampled = cos(2*pi*F1*(TimeInterp))+cos(2*pi*F2*(TimeInterp))+cos(2*pi*FMax*(TimeInterp));

%Compute original signal interpolation by padding the fft and performing
%inverse fft on the result
padded_spectrum0 = spectrum;
padded_spectrum0(NechInterp) = 0;
fspecPadded = [0:NechInterp-1]*Finterp/NechInterp;

padded_reconstruction = padded_spectrum0*exp(2*pi*j*TimeInterpDiscrete'*TimeInterpDiscrete/NechInterp)/(1*Nech);
spectrumresampled = signalResampled*exp(-2*pi*j*TimeInterpDiscrete'*TimeInterpDiscrete/NechInterp);
fresampled = [0:NechInterp-1]*Fe/NechInterp;

% **** print out ****

figure(2);
hold on;
plot(fspec,abs(spectrum),'c');
plot(fresampled,abs(spectrumresampled)/6,'g--');
plot(fspecPadded,abs(padded_spectrum0),'m:');
xlabel('Frequency in Hz','FontSize',16)
ylabel('Signal value (no unit)','FontSize',16)
legend('True signal', 'Reconstruction with resampled spectrum', 'Padded spectrum');

figure(3);
% Ground truth : deterministic signal is recomputed
plot(TimeInterp,signalResampled,'g');
hold on;
% Padding the spectrum and reconstructing it 
plot(TimeInterp,real(padded_reconstruction),'m:');
xlabel('Time in s','FontSize',16)
ylabel('Signal value (no unit)','FontSize',16)
title('\it{ Various signal reconstruction from fourier transform }','FontSize',16)
legend('True signal', 'Reconstruction with padded spectrum');

And here's an image of a horribly distorted signal due to padding in the frequency domain:

Some improvement is possible by first applying fftshift to center the spectrum and padding on alternate sides of the centered spectrum, then inverting the fftshift operation:

Nz = NechInterp-Nech;
padded_spectrum0 = ifftshift([ zeros(1,floor(Nz/2)) fftshift(spectrum) zeros(1,floor(Nz/2)+rem(Nz,2)) ]); % replaces (NechInterp) = 0;
fspecPadded = [0:NechInterp-1]*Finterp/NechInterp;

Then you arrive at this much nicer interpolated time domain signal because the padding operation does not result in such abrupt drop-offs in the spectrum (some improvements may still be possible however with further tinkering):