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