реклама на сайте
подробности

 
 
23 страниц V  < 1 2 3 4 > »   
Reply to this topicStart new topic
> Реализация БПФ на ПЛИС, Тудности, встречаемые при реализации
BuTeK
сообщение Jan 30 2009, 05:35
Сообщение #16


Участник
*

Группа: Новичок
Сообщений: 67
Регистрация: 25-04-06
Из: Беларусь, Гомель
Пользователь №: 16 450



поделитесь рабочей коркой БПФ на почту cvik@tut.by
Go to the top of the page
 
+Quote Post
ZED
сообщение Jan 31 2009, 09:16
Сообщение #17


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Цитата
поделитесь рабочей коркой БПФ на почту cvik@tut.by


Рабочей пока нету, тем более она у меня не дома, так что до понедельника...
Go to the top of the page
 
+Quote Post
анатолий
сообщение Feb 2 2009, 14:02
Сообщение #18


Местный
***

Группа: Свой
Сообщений: 220
Регистрация: 10-12-05
Из: Украина
Пользователь №: 12 052



Проще всего сначала представить данные в формате Integer с диапазоном.
Тогда и отлаживать, и видеть вычисления проще, и сравнить с Матлабом можно,
и синтезируется нормально.
Напр. Бабочка программируется так:
YR<=AR+BR*WR/32768-BI*WI/32768;
и т.д.,
где все числа - в диапазоне -32768... 32767.
Напр. коэффициент WR= 0,999=32767.
Вот только двоичную инверсию лучше делать с переводом адреса с целого в вектор и обратно.
А в конце все это можно перевести в векторные данные и соптимизировать по точности и т.п.
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 10 2009, 17:38
Сообщение #19


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Спасибо, Анатолий, я так и делал, возник вопрос как лучше усекать после вычисления бабочки и сколько разрядов брать...
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 12 2009, 20:14
Сообщение #20


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



В общем нужно масштабировать данные после операций бабочки, вопрос как это сделать? Тут похоже ключевая фраза: "блочная плавающая точка". Может есть у кого какая-нибудь информация по этому поводу? Также вопросы какие разряды брать после умножителя (знаю на форуме было две темы по этому поводу, но там все так путанно, столько мнений, в общем теряюсь где правда, где нет). То же дело обстоит с сумматорами. Подскажите пожалуйста или дайте ссылки на инфу...
Go to the top of the page
 
+Quote Post
Sefo
сообщение Feb 18 2009, 01:27
Сообщение #21


Местный
***

Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537



Как ваши дела с БПФ? Если вопрос еще актуальный и хочется разобраться самому во всех тонкостях и написать свой собственный БПФ, а не хоть как-нибудь "пристроить" чужой, то могу Вас "провести" по процессу создания БПФ своими руками от начала и до конца. Только начать придется с начала, но зато будет нужный Вам результат.
Go to the top of the page
 
+Quote Post
BuTeK
сообщение Feb 18 2009, 05:45
Сообщение #22


Участник
*

Группа: Новичок
Сообщений: 67
Регистрация: 25-04-06
Из: Беларусь, Гомель
Пользователь №: 16 450



Конечно актуально! Поделитесь информацией... Очень итересно!
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 18 2009, 09:26
Сообщение #23


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Вопрос еще актуальный, буду очень признателен. Особенно хочется разобраться во всех тонкостях
Go to the top of the page
 
+Quote Post
Sefo
сообщение Feb 18 2009, 15:38
Сообщение #24


Местный
***

Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537



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

Чтобы не зарубится сразу в дебри сделаем БПФ на фиксированное число точек и, к тому же, являющееся степенью 4, 8 или 2. От того, какому числу будет кратно количество точек зависит какие бабочки нам потребуются и сколько будет этапов. Например, если взять 16 точек, то взяв 2-х точечную бабочку получим 3 этапа и, если принять, что бабочка и умножение на доворачивающие коэффициенты делается за один такт, то потратим 8*3=24 такта (т.е. на каждом этапе мы считаем по 8 бабочек). В случае с 4-х точечной бабочкой БПФ вычислится за 4*2=8 тактов (т.е. на каждом этапе мы считаем по 4 бабочки). Если взять 8-ми точечную бабочку (Т.Б.), то придется вычислять БПФ в 2 этапа и одной 8-ми Т.Б. будет недостаточно - либо на первом, либо на последнем этапе потребуется 2-х точечная бабочка. Тактов это займет 2+8=10 (т.е. на первом этапе вычисляем две 8-ми Т.Б., а на втором восемь 2-х Т.Б.). Если взять 32 точки, то портебуется либо 8-ми и 4-х Т.Б., либо 4-х и 2-х Т.Б., либо только 2-х Т.Б. Этапов потребуется соответственно 2, 3, 5. Тактов потребуется соответственно 4+8=12, 8+8+16=32, 5*16=80. В общем, чтобы понять, сколько этапов и какие бабочки нужны, надо разложить кол-во точек БПФ N на произведение a*b*c*...=N, где сами множители это степень бабочки, а их количество это количество необходимых этапов. Например при N = 16 подходят след. разложения 2*2*2=16, 4*4=16, 8*2=16. При N = 32 возьмем разложения, соответствующие описанным выше примерам: 8*4=32, 4*4*2=32, 2*2*2*2*2=32. Понятно, что в некоторых случаях количество этапов это просто показатель степени (2^5=32)

Далее нужно определится с необходимым быстродействием. Речь не идет пока о частоте клока - речь идет о простом количестве тактов (т.е. их интервал в нс, мс, мкс и т.д. не имеет значения). Одновременно нужно определится и с необходимым количеством ресурсов микросхемы. В БПФ связь этих двух параметров довольно четкая - мало тактов - много места, много тактов мало места. Например, выше, все расчеты тактов делались исходя из того, что бабочка и умножение на коэффициенты делаются за один такт. Это очень быстро, но для 4-х Т.Б. потребуется 8*4=24 сумматора (8 т.к. суммируем комплексные числа) и 3 комплексных(!) умножителя (т.е. 4*3=12 умножителей и 2 сумматора). Однако, если все это вычислять за 4 такта, то надо 8 сумматоров и 1 комплексный умножитель - существенно меньше по ресурсам, но в 4 раза медленнее. Кроме того 8-ми Т.Б. сама по себе больше 4-х, а 4-х больше 2-х. smile.gif

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

Итак :

1) скольки точечное БПФ нужно?

2) Какой баланс выбираем между быстродействием, ресурсами и частотой клока?

Еще одно замечание. Для вычисления 4-х и 2-х Т.Б. нужны только сумматоры, а вот при вычислении 8-ми Т.Б. потребуется еще 2 умножителя. Правда умножать они будут всегда на константу - SQRT(2) (кажется).

Сообщение отредактировал Sefo - Feb 18 2009, 15:34
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 18 2009, 16:34
Сообщение #25


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Не совсем понял про разделение бабочки и поворачивающих множителей. Ведь сама бабочка включает в себя домножение на поворачивающий множитель. Вот к примеру бабочка с прореживанием по частоте:

W - поворачивающий множитель, который меняется от бабочки к бабочке и от этапа к этапу.
Теперь с количеством точек: нужно 2048.
Выбор баланса - быстродействие.
Также предлагаю реализовать алгоритм с постоянной структурой по схеме "пинг-понг":


Прореживание по частоте.
Суть метода: В ОЗУ-1 находятся отсчеты сигнала, над которыми будет производиться БПФ, на нечетных этапах данные берутся из ОЗУ-1, а поворачивающие множители из ПЗУ, вычисляется бабочка и результат записывается в ОЗУ-2 (бабочка одна). Те же действия повторяются над всеми парами точек. Для четных этапов все наоборот: данные берутся из ОЗУ-2, поворачивающие множители по-прежнему из ПЗУ, вычисляется бабочка и результат записывается в ОЗУ-1.
Go to the top of the page
 
+Quote Post
Sefo
сообщение Feb 18 2009, 16:56
Сообщение #26


Местный
***

Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537



Про разделение бабочки и поворачивающих множителей я Вам объясню завтра - сейчас времени нет. W на маленьком рисунке это "не тот" поворачивающий коэффициент, о котором я писал. Это важный вопрос для понимания "тонкостей" БПФ, поэтому предлагаю сделать паузу до моего подробного ответа завтра.
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 18 2009, 17:04
Сообщение #27


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Хорошо, жду с нетерпением, завтра я буду вечером и с удовольствием прочту. Спасибо!
Go to the top of the page
 
+Quote Post
Sefo
сообщение Feb 19 2009, 13:29
Сообщение #28


Местный
***

Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537



На рисунке показана базовая операция для БПФ с прореж. по частоте, если бы было прореживание по времени, то умножение на W было бы нарисовано не на выходе, а на входе. Кроме того, значение W зависит от положения бабочки в схеме алгоритма. В некоторых случаях, умножение на W является тривиальным: когда W = -+1 + j0 умножение как таковое вообще отсутствует, когда W = 0 +- j1 реальная и мнимая части просто меняются местами и изменяется знак. Алгоритмов вычисления БПФ можно придумать много, а способов реализации каждого - еще больше. К примеру, если при реализации алгоритма используется несколько экземпляров бабочек, чтобы распараллелить вычисления, то, может оказаться, что какие-то экземпляры бабочек всегда будут получать тривиальные коэффициенты и им комплексные умножители вообще не понадобятся. В конце концов, суть БПФ в том, что ДПФ большего порядка вычисляются через ДПФ меньшего. Ведь n-точечная бабочка это не что иное, как n-точечное ДПФ. Вы сами можете легко получить формулы для вычисления n-точечных бабочек просто расписав n-точечное ДПФ и упростив выражения. Поэтому, если рассуждать строго, считать умножение на W частью бабочки, как на вашей картинке, неправильно. В любом случае, с инженерной точки зрения, умножение на W следует вынести за пределы бабочки. Это дает возможность лучше понять где и на чем можно сэкономить при реализации алгоритма БПФ и это так же дает некоторые удобства самой реализации. Так что далее, упоминая бабочку, я буду иметь ввиду "чистую" бабочку.

Теперь про некоторые особенности бабочек.

Если Вы распишите 2-х и 4-х точечное ДПФ, то увидите, что все коэффициенты тривиальные: либо вещественная, либо мнимая 1! При реализации, умножение на такие коэффициенты не требует использования умножителей. Поэтому, 2-х и 4-х точечные бабочки "дешевые" для реализации. Все что нужно, это сложить, вычесть и поменять местами Re и Im.

С 8-ми и более Т.Б. дела обстоят хуже – если Вы их распишите, то увидите, что появляются нетривиальные коэффициенты – SQRT(2)/2. Тут без умножителей не обойтись. Правда, умножители эти всегда умножают на константу, что несколько экономит место (если нет DSP блоков или речь идет об ASIC, а не о ПЛИС). Из-за этого нюанса, внесение в бабочку еще и умножения на W может запутать новичка.

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

Фактически, различия между алгоритмами состоят лишь в порядке подачи данных на бабочки и месте умножения на доворачивающие коэффициенты W (до или после бабочки).

Теперь про реализацию.

Хотите Пин-понг – реализуем пин-понг. Но Вы уверены, что 2-х Т.Б. Вас устроит по быстродействию? Ведь 2-х точечная бабочка для 2048 точек это 11*1024 = 11264 такта (4-х + 2-х точечная сделают все за 512*5 + 1024 = 3584).
Go to the top of the page
 
+Quote Post
ZED
сообщение Feb 19 2009, 15:21
Сообщение #29


Местный
***

Группа: Участник
Сообщений: 264
Регистрация: 17-04-07
Из: Москва
Пользователь №: 27 102



Честно говоря, конечно лучше бы 4-х Т.Б. Но как с ней сделать алгоритм на 2048 точек, нам ведь все равно потребуется 2-х Т.Б. ? Если это можно сделать с 4-х Т.Б. я вполне согласен!
Go to the top of the page
 
+Quote Post
Sefo
сообщение Feb 19 2009, 22:36
Сообщение #30


Местный
***

Группа: Свой
Сообщений: 429
Регистрация: 11-08-05
Из: Санкт-Петербург
Пользователь №: 7 537



Итак, делаем более быстрый вариант с 4-х и 2-х Т.Б.

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

Не знаю, насколько у Вас много времени, но лучше, если Вы нарисуете схему и блок-схему в чем-нибудь вроде Visio, чтобы было проще ее редактировать, исправляя ошибки или оптимизируя (и Вам и мне).

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

Если я правильно нпонял, то средой разработки будет Квартус и Вы с ним не очень знакомы. Можно полюбопытствовать какой у Вас опыт разработки и какими программами Вы пользовались?
Go to the top of the page
 
+Quote Post

23 страниц V  < 1 2 3 4 > » 
Reply to this topicStart new topic
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 


RSS Текстовая версия Сейчас: 27th May 2018 - 19:10
Рейтинг@Mail.ru


Страница сгенерированна за 0.00924 секунд с 7
ELECTRONIX ©2004-2016