Существует ли алгоритм FFT с круговым буфером?

John
Сообщения: 17
Зарегистрирован: 29 сен 2020, 17:57

Существует ли алгоритм FFT с круговым буфером?

Сообщение John »

Здравствуйте.

В моей задаче требуется высокое разрешение на НЧ для этого нужно использовать FFT с большим порядком (к примеру 16384) и я бы хотел как-то оптимизировать алгоритм чтобы не вычислять каждый раз все с нуля.

К примеру у меня есть буфер длиной 16384 семплов и периодически мне приходит новая порция данных в 256 семплов. Я сдвигаю данные в большом буфере на 256 семплов и размещаю там новые пришедшие данные, затем делаю FFT. Получается FFT скользящим окном. Но можно ли как-то оптимизировать алгоритм дабы не вычислять опять все 16384 семпла? По сути мы имеем 16384 - 256 семплов уже учавствовавших в вычислении.

Как пытался сделать я.

Т.к. меня интересует только спектр, то у меня сразу буфер комплексных чисел со спектром размером 16384 бинов.
Когда получаю данные то смещаю фазу в этом буфере (умножением на комплексную синусоиду) на 256 отсчетов влево, в итоге если рассматривать сигнал во временной области то "ненужные" отсчеты сдвинуться в конец.
Теперь нужно занулить эти отсчеты во временной области, но используя частотную область. Это легко сделать если использовать вычитание сигналов. В качестве вычитаемого сигнала использовать буфер вычисленный на предыдущих шагах.
Над вновь пришедшими данными в 256 семплов вычисляется FFT размером 256 бинов.
Далее спектр нужно как-то быстро растянуть чтобы из 256 бинов получить 16384 бинов. Тут нужно отметить что точность не сильно важна, т.к. исходный сигнал - музыка и небольшие частотные огрехи неважны. Т.е. нужен аналог дополнения нулями во временной области, но только вычислить его в частотной. Если решать в лоб без оптимизаций - то тут понятно, просто свернуть с sinc окном. Но это долго.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Существует ли алгоритм FFT с круговым буфером?

Сообщение Бахурин Сергей »

John писал(а):
19 окт 2020, 11:42
Теперь нужно занулить эти отсчеты во временной области, но используя частотную область. Это легко сделать если использовать вычитание сигналов. В качестве вычитаемого сигнала использовать буфер вычисленный на предыдущих шагах.
Над вновь пришедшими данными в 256 семплов вычисляется FFT размером 256 бинов.
Вот это прямо совсем не очевидно, что это получится легко сделать. Потому что зануление части отсчетов эквивалентно умножению на окно, что в частотной области равносильно свертке спектров. Возможно я что-то не понял, но если у вас есть модель матлаб или питон или сишная, то прошу показать.
John писал(а):
19 окт 2020, 11:42
Далее спектр нужно как-то быстро растянуть чтобы из 256 бинов получить 16384 бинов. Тут нужно отметить что точность не сильно важна, т.к. исходный сигнал - музыка и небольшие частотные огрехи неважны. Т.е. нужен аналог дополнения нулями во временной области, но только вычислить его в частотной. Если решать в лоб без оптимизаций - то тут понятно, просто свернуть с sinc окном. Но это долго.
Сворачивать надо не с синк окном, а с ядром Дирихле в этом случае.

Вообще я бы к этой задаче подошел через DFT как результат умножения матрицы поворотных к-тов на вектор входного сигнала, и пытался бы как-то вывести закономерность.

PS скользящий алгоритм Герцеля для расчета одного бина добавляет только буфер задержки на длину DFT, так что есть предположение, что хороший алгоритм существует для вашей задачи, надо посмотреть математически и посимулировать

John
Сообщения: 17
Зарегистрирован: 29 сен 2020, 17:57

Re: Существует ли алгоритм FFT с круговым буфером?

Сообщение John »

Бахурин Сергей писал(а):
19 окт 2020, 14:21
Вот это прямо совсем не очевидно, что это получится легко сделать. Потому что зануление части отсчетов эквивалентно умножению на окно, что в частотной области равносильно свертке спектров. Возможно я что-то не понял, но если у вас есть модель матлаб или питон или сишная, то прошу показать.
Возможно я плохо объяснил. Смотрите в 16384 отсчета помещается 64 чанка с 256 отсчетами. Каждый чанк в 256 отсчетов у нас расширяется на 16384 отсчета так как-будто дополнен нулями с левой стороны.

Когда на первом шаге мы умножаем на комплексную синусоиду мы циклически сдвигаем спектр так чтобы ненужная часть стала справа. Т.е. если сохранить в кеше спектр 63 чанка и теперь его вычесть из спектра то нужный сигнал исчезнет.

Т.е. тут только нужно как-то эффективно расширить 256 спектр в 16384 в частотной области, так как будто это сигнал в 256 отсчетов дополненый нулями слева и задача решена.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Существует ли алгоритм FFT с круговым буфером?

Сообщение Бахурин Сергей »

Если вас не смущает необходимость хранения 64 различных FFT размера 16384 точек, то можно организовать расширение 256 временнЫх отсчета в 16384 спектральных в процессе FFT. Виртуально можно дополнить 256 до 16384 нулями и использовать составной алгоритм FFT, который учтёт огромное число нулей в сигнале и эффективно рассчитает 16384 точек спектра. После вы сможете используя фазовые повороты организовать пересчет спектра.

Аватара пользователя
Бахурин Сергей
Администратор
Сообщения: 1114
Зарегистрирован: 05 окт 2010, 19:55
Контактная информация:

Re: Существует ли алгоритм FFT с круговым буфером?

Сообщение Бахурин Сергей »

Вот набросал алгоритм (в октаве и матлабе будет работать) который позволяет пересчитывать 256 отсчетов в 16384 отсчетов спектра без интерполяции:

Код: Выделить всё

clear all; close all; clc;


M = 256;
N = 64;

% полный размер FFT = 16384
NFFT = M*N;

% Заполняю матрицу поворотных к-тов составного FFT 
% это надо один раз для всех случаев.
W = zeros(N, M);
for m = 0:N-1
  for n = 0:M-1
    W(m+1, n+1) = exp( -j * 2 * pi * m * n / (M*N));
  end
end

% создаю нулевой входной сигнал длины 16384 
% и первые 256 отсчетов заполняю случайными значениями
x = zeros(M*N, 1);
x(1:M) = randn(M, 1);

% Перевожу входной сигнал в матрицу [256 x 64],
% в которой только первый столбец отличен от нуля
A = reshape(x, M, N);

% транспонирую матрицу A и получаю матрицу B [64 x 256] 
% в которой только первая строка отлична от нуля
B = A.';

% FFT по столбцам матрицы B тривиально, 
% т.к. только первый элемент каждого столбца B отличен от нуля.
% просто первый элемент каждого столбца матрицы B копируется во 
% все остальные ячейки столбца
Y = fft(B);

% Поэлементное умножение матрицы Y и поворотныx 
% к-тов W (NFFT умножение) 
Z = Y.*W;

% Транспонирую матрицу Z и получаю матрицу Q размера [256 x 64]
Q = Z.';

% Теперь надо сделать 64 раз FFT размера 256 точек 
% по столбцам матрицы Q. Получим матрицу V [256 x 64]
V = fft(Q);

% Транспонируем матрицу V и получаем P [64 x 256]
P = V.';

%стыкуем стоблцы матрицы P друг за другом и получаем результат FFT
X = reshape(P, M*N, 1);


% Т.о. для расчета потребовалось NFFT умножений + 64 FFT 256 точек,
% которые заменяют FFT 16384 точек без необходимости интерполяции. 



John
Сообщения: 17
Зарегистрирован: 29 сен 2020, 17:57

Re: Существует ли алгоритм FFT с круговым буфером?

Сообщение John »

Спасибо большое за ответ! Буду разбираться.

Ответить