MATLAB: более быстрый метод нахождения дискретного преобразования Фурье - PullRequest
Новая
       5

MATLAB: более быстрый метод нахождения дискретного преобразования Фурье

1 голос
/ 05 ноября 2019

Я пытаюсь написать код в Matlab, который делает в основном то же самое, что встроенная функция fft. Следовательно, вычисление дискретного преобразования Фурье для любого заданного входного вектора.

Преобразование задается как 

%                    N
%      X(k) =       sum  x(n)*exp(-j*2*pi*(k-1)*(n-1)/N), 1 <= k <= N.
%                   n=1

Теперь я создал свой собственный код, чтобы сделать это, но вычислительные усилия составляют примерно фактор200, когда я смотрю на время вычислений. Очевидно, я хотел бы уменьшить это.

Ниже вычислительной части моего кода, где y - выходной вектор. 

N=length(input_vector)

for k = 1:N
        y(k)=0;
        for n = 1:N
            term = input_vector(n)*exp(-2*pi*1i*(n-1)*(k-1)/N);
            y(k)=y(k)+term;
        end
end

Теперь я думаю, что вычисления тяжелы из-за циклов for и строки с y(k)=y(k)+term, поскольку это происходит на всех итерациях. Я считаю, что я должен быть в состоянии сделать это меньше, используя векторную / матричную нотацию или используя функции с фиктивными переменными, а затем итерируя эти функции. Но я не знаю, как начать этот процесс.

Любая помощь или предложения будут высоко оценены.

1 Ответ

3 голосов
/ 05 ноября 2019

Используя неявное расширение , вы можете значительно сократить время вычисления вашего алгоритма: 

% Vector length
N = length(input_vector);

% Vectorized DFT algorithm
y = sum(input_vector.*exp(-2*pi*1i*[0:N-1].'*[0:N-1]/N),2);

Однако есть два недостатка:

  1. Векторизацияпотреблять много памяти (поскольку необходимо создать вектор N * N)
  2. Это не будет быстрее, чем встроенная функция.
...