[ADA007 0]

Доброго времени суток, форумчане.

Пытаюсь разобраться в алгоритме БПФ по бабочке...никак не дается мне понимание всего происходящего, что там заложено. Задача изначально состоит в том, чтобы как можно оптимальнее с учетом специфики ПЛИС реализовать данный алгоритм. Входными данными является уровень, принимаемый с АЦП...т.е. операции необходимо проводить с вещественными числами (дискретное преобразование). На просторах интернета реализаций под ПЛИС нашел немного... но так и не смог до конца разобраться.

Вот к примеру из wiki бабочка по 2-м отсчетам записана , как

И как мне из этого выудить спектр? Если входные отсчеты (данные из АЦП) это они обозначили как х0 и х1, то Х0 и Х1 - это уже отсчеты спектра или как? и как узнать дискретность этого спектра (Х0 и Х1 отстоят друг от друга на 1 Гц ... или от чего это зависит вообще)?

Хорошо, теперь возьмем преобразование по 4-м отсчетам. это выглядет как-то так.

Так получается что у нас для расчета каждого нового Х0 используется все 4-е отсчета...т.е. если надо будет бпф radix 256 сделать, что получится для каждого отсчета будет 256 операций? Или его можно разбить как-то (прореживание вроде)?

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

И в догонку еще вопрос...зачем тогда использовать в ПЛИС ДСП для БПФ, если оно ограничивается сложениями и вычитаниями? или это может пригодиться, только для вычислений с комплексными числами?

[Golikov 0]

Тут ИМХО вопрос не в ПЛИС, а в том что есть БПФ вообще.

 

Первое что вам надо знать, когда вы собрали отсчеты с равными промежутками и сделали БПФ, на выходе вы получите кашу, потому что спектр будет переставлен в битовореверсивном порядке индексов,

то есть если вы на вход подавали

x0(b00) x1(b01) x2(b10) x3(b11) отсчеты, то на выходе у вас будет индексы X0(b00) X2(b10) X1(b01) X3(b11), то есть чтобы получить отсюда амплитуду по спектру, надо переставить отсчеты в порядок X0 X1 X2 X3. то есть поменять 2 и 3 полученные отсчеты местами, если отсчетов 8, то еще круче. Чтобы на выходе отсчеты сразу получились нормальными, надо подавать битовореверсивную последовательность индексов на вход.

 

Индекс представляется в бинарном коде, потом переворачивается и получаете реальный индекс.

 

 

Далее когда вы получили свои отсчеты спекра Х0 Х1 Х2 Х3, то вы получили значения амплитуды, а вот точки частоты спектра зависят от частоты дискретизации, если вы снимаете данные с частотой 1000 Гц и 4 точки, то вы получите точки 0, 500, 250, 125 Гц. Если с частотой 2000 Гц, то будет

0, 1000, 500, 250 Гц. То есть у вас в спектре постоянка и от половинной частоты дискретизации с делением пополам.

 

 

Когда вы делаете БПФ все ваши 256 входных отсчетов влияют на выходные и формируют 256 выходных, и если бы вы делали не БПФ а просто ПФ, то да вы посчитали бы сумму в 256 членов для каждого отсчета. Но в этом и смысл БПФ, что из 2 точек входа бабочки получается сразу 2 точки выхода бабочки, то есть вы получаете сразу за 1 операцию 2 значения. Бабочки идут слоями, для 4 точек получается 2 слоя. На каждом слое вы будите получать новые 4 точки, которые можно сохранить на старое значение для расчета следующего слоя, тем самым у вас никогда не получается больше 4 ячеек памяти для 4 точечного БПФ, а число операций будет число точек на число слоев и на 2, то есть гораздо меньше чем число точек в квадрате в случае прямого ПФ, но минусом будет что отсчеты перемешаются черти как)

 

П.С. Всю информацию надо уточнять, я мог какие-то детали уже упустить. Вроде амплитуда имеет какие то коэффициенты, и это как-то связано с функцией окна. Вроде бы для Гаусового окна, постоянка идет с коэффициентом 1/2.

 

 

Ну и БПФ - это не только сложение и вычитание, там есть еще поворотный множитель W, на него надо умножить. Вот для этого умножения ДСП и подтягивают.

[bogaev_roman 0]

Доброго времени суток, форумчане.

Пытаюсь разобраться в алгоритме БПФ по бабочке...никак не дается мне понимание всего происходящего, что там заложено. Задача изначально состоит в том, чтобы как можно оптимальнее с учетом специфики ПЛИС реализовать данный алгоритм.

Если поиграться или времени свободного масса, то начать можно с opencores - там есть несколько готовых реализаций на RTL для 256 точек. Если нужно рабочее и побыстрее - то готовый блок ip - у xilinx, например, там несколько возможных реализаций, существенно отличающихся по ресурсам и быстродействию, в зависимости от реализации.

[Мур 1]

БПФ - всего-лишь математический трюк для быстрого вычисления спектральных составляющих. Теория требует применения оконной операции (их много разных), чтобы исключить "утечку спектра"(размывание). Кроме того, полноценный вычислитель на входе должен иметь временной поток комплексных составляющих (как правило прошедших децимацию, фильтрацию и DDС-преобразование). Чтобы работа не ушла в корзину,- временные отсчеты уже закладывайте комплексными....

Поворотный коэффициент и есть основной источник погрешности вычислений. С ним аккуратней..

Последний раунд обсчета бабочки можно не делать полностью (а только половину), потому как итоговый спектр будет симметричным.

[TRILLER 0]

Последний раунд обсчета бабочки можно не делать полностью (а только половину), потому как итоговый спектр будет симметричным.

Не вводите в заблуждение. Не будет симметричным если входные данные комплексные.

[Мур 1]

Не вводите в заблуждение. Не будет симметричным если входные данные комплексные.

 

... точно! Извините... Не прав!

[thermit 1]

Последний раунд обсчета бабочки можно не делать полностью (а только половину), потому как итоговый спектр будет симметричным.

 

 

Угу. Особенно, если

полноценный вычислитель на входе должен иметь временной поток комплексных составляющих

[Мур 1]

Угу. Особенно, если

 

Да я сначала написал один ответ, а потом начал дополнять... ))) Симметрия будет при варианте действительных данных на входе..

 

http://ru.convdocs.org/docs/index-65894.html

http://chipmicro.narod.ru/5.pdf

[Sefo 0]

Пытаюсь разобраться в алгоритме БПФ по бабочке...никак не дается мне понимание всего происходящего, что там заложено. Задача изначально состоит в том, чтобы как можно оптимальнее с учетом специфики ПЛИС реализовать данный алгоритм. Входными данными является уровень, принимаемый с АЦП...т.е. операции необходимо проводить с вещественными числами (дискретное преобразование). На просторах интернета реализаций под ПЛИС нашел немного... но так и не смог до конца разобраться.

 

Лучше всего начать с теоретической части, чтобы понять что вообще такое БПФ. Например почитайте 6 и 10 главы из книжки Рабинера Л. и Гоулда Б. "Теория и применение цифровой обработки сигналов". В интернете ее легко найти. Важное замечание: там есть примеры аппаратной реализации БПФ, так вот их лучше пропустить т.к. для ПЛИС это адаптировать совершенно нецелесообразно.

 

Сразу могу сказать, что какой-то особой специфики у ПЛИС для БПФ нет. Самая главная специфика ПЛИС в том, что можно нагенерировать параллельно работающих вычислителей столько в ПЛИС влезет. БПФ хорошо параллелизуется.

 

 

И в догонку еще вопрос...зачем тогда использовать в ПЛИС ДСП для БПФ, если оно ограничивается сложениями и вычитаниями? или это может пригодиться, только для вычислений с комплексными числами?

 

Бабочка, это всего лишь базовый элемент из которого строится БПФ. Только 2-х и 4-х точечная бабочка вычисляется исключительно с помощью сложения и вычитания. Все остальные уже требуют умножителей. Выходы бабочки всегда подключены умножителям, которые умножают данные с бабочки на доворачивающие множители. Так что, если нужно вычислить БПФ с количеством точек не равным 2 или 4, то без умножителей вы не обойдетесь.

 

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

 

Некоторые вопросы реализации довольно подробно обсуждались в этой теме: Реализация БПФ на ПЛИС. Но читать ее лучше после Рабинера и Гоулда.

 

Далее когда вы получили свои отсчеты спекра Х0 Х1 Х2 Х3, то вы получили значения амплитуды

 

До амплитуд еще далеко. Вы получаете проекции вектора на оси комплексной плоскости. чтобы получить амплитуду нужно вычислить квадратный корень из суммы квадратов этих проекций: sqrt( Re(Xn)^2 + Im(Xn)^2)

 

Этот квадратный корень есть хорошая такая ложка дегтя в бочке с медом при реализации БПФ на ПЛИС в том случае, если нельзя обойтись просто суммами квадратов для анализа учитывая, что корень квадратный функция монотонная.

[troiden 0]

Этот квадратный корень есть хорошая такая ложка дегтя в бочке с медом при реализации БПФ на ПЛИС в том случае, если нельзя обойтись просто суммами квадратов для анализа учитывая, что корень квадратный функция монотонная.

В проблеме квадратного корня вполне себе помогает CORDIC. Фактически ценой одного умножителя получаем готовую амплитуду из двух проекций.

[Krys 2]

Сейчас как раз реализую БПФ.

Я бы посоветовал Оппенгейма почитать, я там кое-что практическое для себя нашёл (применение БПФ для очень длинных последовательностей).

Alan V. Oppenheim, Ronald W. Schafer. Discrete-Time Signal Processing (3rd Edition) (Prentice Hall Signal Processing) Hardcover – 2009

Есть и на русском, при том разные издания.

А ещё для начинающих очень хорошо БПФ разжёвано у Ричард Лайнос Цифровая Обработка Сигналов 2006.