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

  • Лестница для самых жадных

    В эти выходные побывал на даче, после 3-недельной "самоизоляции". Забавно, как будто зима началась! Особенно грязные галоши остались на улице, в…

  • Возвращаемся к макету

    Очень давно макетом видеоизмерителя параметров сближения не занимался: сначала "громко думал" по поводу измерения его положения на аппарате, а потом…

  • Минутка живописи

    В процессе разгребания содержимого квартиры (после нескольких ремонтов) дошёл, наконец, и до картин. В кои-то веки их повесил. Куда их вешать -…

  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your IP address will be recorded 

  • 0 comments