nabbla (nabbla1) wrote,
nabbla
nabbla1

Category:

УТ БПФ: работа над ошибками

В прошлый раз у меня возникли проблемы с арифметикой, не сумел посчитать до 24, остановился на 20 и обрадовался - ух ты, как мало! Самым быстрым по числу арифметических операций УТ БПФ не становится, он требует 8Nlog3N≈5.04Nlog2N операций, что на 0.9% больше, чем требует двоичный. Но как пишут авторы рекордного на сегодняшний день БПФ, сейчас время выполнения алгоритма на компьютере определяется чем угодно, только не формальным числом арифметических операций. Так что не буду в ближайшее время бороться за рекорд, эти алгоритмы друг друга стоят.

Пора дополнить раздел 2 и описать алгоритм прореживания по частоте (DIF, Decimation In Frequency). Именно на нем отчетливо видно, как снизить необходимое число арифметических операций до упомянутого выше значения.


Разобьем входную последовательность x[k] (-T≤n≤T, T=(N-1)/2, N=3q) на три:
x0[k]=x[k],
x+[k]=x[k+N/3],
x-[k]=x[k-N/3], -t≤k≤t,

Найдем значения для F[3n], F[3n+1] и F[3n-1]:

Обозначим выражения в скобках за X0[k], X+[k] и X-[k]. Как видно, вычисление УТ БПФ от N отсчетов сводится к нахождению данных величин, после чего к каждому из них применяется УТ БПФ пониженной степени. Процедуру можно продолжать рекурсивно.
Граф «бабочка» совпадает с тем, который получился для алгоритма с прореживанием по времени, но ее нужно читать в обратную сторону.
Tags: математика, работа, статьи, троичная система счисления, уравновешенное троичное БПФ
Subscribe

  • Нахождение двух самых отдалённых точек

    Пока компьютер долго и упорно мучал симуляцию, я пытался написать на ассемблере алгоритм захвата на ближней дистанции. А сейчас на этом коде можно…

  • Слишком общительный счётчик

    Вчера я чуть поторопился отсинтезировать проект,параметры не поменял: RomWidth = 8 вместо 7, RamWidth = 9 вместо 8, и ещё EnableByteAccess=1, чтобы…

  • Балансируем конвейер QuatCore

    В пятницу у нас всё замечательно сработало на симуляции, первые 16 миллисекунд полёт нормальный. А вот прошить весь проект на ПЛИС и попробовать "в…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments