БПФ, Прошу пояснения Опции

[Dmitriyspb]

Приветствую Вас, уважаемые знатоки!

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

Вопрос.
Прошу мне помочь разобраться с алгоритмом БПФ (его прикрепляю к посту). Никак не могу разобраться с тем, что значат эти линии и точки их пересечений.

Для себя я уяснил, что входные отсчеты в нужном количестве я возьму с АЦП и запишу их в ОЗУ. Допустим 2048 отсчетов я записал в ОЗУ и что мне дальше с ними делать?

Уточните пожалуйста....куда мне двигаться с этими отсчетами?

Может примеры наглядные есть у кого. Я сам интернет копаю, но ответов на свои вопросы не нахожу. Возможно я что-то сильно недопонимаю.

P.S. Возможно подобный вопрос уже не раз поднимался....хотя я тут толком для себя полезного не нашел.

Прикрепленные файлы

 _________FFT_2048.pdf ( 140.42 килобайт ) Кол-во скачиваний: 343

 

[Lmx2315]

http://electronix.ru/forum/index.php?showtopic=58026
Реализация БПФ на ПЛИС, Тудности, встречаемые при реализации

з.ы.
может будет полезно

[Dmitriyspb]

http://electronix.ru/forum/index.php?showtopic=58026
Реализация БПФ на ПЛИС, Тудности, встречаемые при реализации

з.ы.
может будет полезно

спасибо

[bogaev_roman]

to Dmitriyspb что мешает взять готовую корку и настроить ее под свои нужды (для начала просто поточное, где не нужно самому хранить отсчеты)?

[Dmitriyspb]

to Dmitriyspb что мешает взять готовую корку и настроить ее под свои нужды (для начала просто поточное, где не нужно самому хранить отсчеты)?

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

В итоге цель реализовать анализатор спектра до 1 МГц. аппаратная платформа имеется. С дисплеем разберусь в конце. А сейчас нужно разобраться с БПФ.
Время позволяет реализовать это самостоятельно.

[Skryppy]

Советую почитать Р. Лайонса "Цифровая обработка сигналов", там много интересного найдете.

[Dmitriyspb]

Советую почитать Р. Лайонса "Цифровая обработка сигналов", там много интересного найдете.

благодарю. пошел читать

[Dmitriyspb]

Итак, я для себя составил ТХ к БПФ по основанию 2

1. Разрешение - 2,5 кГц
2. Число точек 2048
3. Частота дискретизации 5 МГц
4. Полоса для анализа 1 МГц

Читаю дальше....

[Dr.Alex]

Итак, я для себя составил ТХ

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

[Dmitriyspb]

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

Спасибо
написать я уже решу на чем и когда. Я сейчас для себя пытаюсь нарисовать структуру. И понять алгоритм БПФ

[Dmitriyspb]

Итак.
Стало яснее, но вопросы остаются.
Общий принцип понятен. Стал углубляться, а именно рассматривать алгоритм "бабочка" и не могу понять откуда мне взять коэффициенты? Как они считаются?

На картинке 1 показано как высчитывается каждая переменная. А на рисунке 2 показано когда и что подставлять в качестве коэффициента.
Где взять коэффициенты?

Эскизы прикрепленных изображений

 

[serjj]

Вот отсюда, например. Коэффициенты Фурье считаются как exp(i*2*pi*k*n/N). N - размер Фурье, k - индекс по частоте 0...N-1, n - индекс по времени 0...N-1. Коэффициенты соответственно комплексные нормированные к 1 и вещественные. Нормируйте их к разрядной сетке, округлите и сохраните их в ROM с коэффициентами. Разные реализации Фурье в разном порядке читают эту память. Есть реализации где коэффициенты считаются налету (при очень большом N)

[serjj]

UPD. Перепутал с коэффициентами DFT общего вида, пардон . Вот здесь хорошо расписано как считать поворотные коэффициенты для FFT. Фактически поворотные коэффициенты для FFT можно представить как вектор матрицы коэффициентов DFT соответствующий n=1. Таким образом для N точечного FFT потребуется N поворотных коэффициентов часть из которых тривиальная (1, -j), что упрощает алгоритм.

[Kapsik]

Я сейчас решаю похожую задачу, предлагаю объединить наши усилия =)
Набросал код в матлабе, для примера на 16 точек. Понимаю, что профи матлаба меня сейчас наверное закидают тухлыми помидорами, но я написал "чтобы было наглядно, сюда смотреть буду и на verilog кодить"

Код

ss = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15];
k2 = [0:7];
W2 = exp( -j*2*pi.*k2/16 );

s2r = [ss(1) ss(9) ss(5) ss(13) ss(3) ss(11) ss(7) ss(15) ss(2) ss(10) ss(6) ss(14) ss(4) ss(12) ss(8) ss(16)];

%первый шаг
s11 = s2r(1) + s2r(2);
s12 = s2r(1) - s2r(2);
s13 = s2r(3) + s2r(4);
s14 = s2r(3) - s2r(4);
s15 = s2r(5) + s2r(6);
s16 = s2r(5) - s2r(6);
s17 = s2r(7) + s2r(8);
s18 = s2r(7) - s2r(8);
s19 = s2r(9) + s2r(10);
s110= s2r(9) - s2r(10);
s111= s2r(11)+ s2r(12);
s112= s2r(11)- s2r(12);
s113= s2r(13)+ s2r(14);
s114= s2r(13)- s2r(14);
s115= s2r(15)+ s2r(16);
s116= s2r(15)- s2r(16);


%второй шаг

s21 = s11 + s13*W2(1);
s22 = s12 + s14*W2(5);
s23 = s11 - s13*W2(1);
s24 = s12 - s14*W2(5);

s25 = s15 + s17*W2(1);
s26 = s16 + s18*W2(5);
s27 = s15 - s17*W2(1);
s28 = s16 - s18*W2(5);

s29 = s19 + s111*W2(1);
s210 = s110 + s112*W2(5);
s211 = s19 - s111*W2(1);
s212 = s110 - s112*W2(5);

s213 = s113 + s115*W2(1);
s214 = s114 + s116*W2(5);
s215 = s113 - s115*W2(1);
s216 = s114 - s116*W2(5);

%шаг 3
s31 = s21 +  s25*W2(1);
s32 = s22 +  s26*W2(3);
s33 = s23 +  s27*W2(5);
s34 = s24 +  s28*W2(7);
s35 = s21 -  s25*W2(1);
s36 = s22 -  s26*W2(3);
s37 = s23 -  s27*W2(5);
s38 = s24 -  s28*W2(7);

s39 = s29 +  s213*W2(1);
s310= s210 + s214*W2(3);
s311= s211 + s215*W2(5);
s312= s212 + s216*W2(7);
s313 = s29 - s213*W2(1);
s314= s210 - s214*W2(3);
s315= s211 - s215*W2(5);
s316= s212 - s216*W2(7);

%шаг 4

s41 = s31 + s39*W2(1);
s42 = s32 + s310*W2(2);
s43 = s33 + s311*W2(3);
s44 = s34 + s312*W2(4);
s45 = s35 + s313*W2(5);
s46 = s36 + s314*W2(6);
s47 = s37 + s315*W2(7);
s48 = s38 + s316*W2(8);

s49 = s31 - s39*W2(1);
s410 = s32 - s310*W2(2);
s411 = s33 - s311*W2(3);
s412 = s34 - s312*W2(4);
s413 = s35 - s313*W2(5);
s414 = s36 - s314*W2(6);
s415 = s37 - s315*W2(7);
s416 = s38 - s316*W2(8);

Результат с матлабовской fft сошелся.

Сообщение отредактировал Kapsik - Apr 21 2015, 06:25

[Dmitriyspb]

Вот отсюда, например. Коэффициенты Фурье считаются как exp(i*2*pi*k*n/N). N - размер Фурье, k - индекс по частоте 0...N-1, n - индекс по времени 0...N-1. Коэффициенты соответственно комплексные нормированные к 1 и вещественные. Нормируйте их к разрядной сетке, округлите и сохраните их в ROM с коэффициентами. Разные реализации Фурье в разном порядке читают эту память. Есть реализации где коэффициенты считаются налету (при очень большом N)

А может для этого существует какая-то программка специализированная, которая умеет считать коэффициенты? Никто не знает?

Я сейчас решаю похожую задачу, предлагаю объединить наши усилия =)
Набросал код в матлабе, для примера на 16 точек. Понимаю, что профи матлаба меня сейчас наверное закидают тухлыми помидорами, но я написал "чтобы было наглядно, сюда смотреть буду и на verilog кодить"

Код

ss = [0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15];
k2 = [0:7];
W2 = exp( -j*2*pi.*k2/16 );

s2r = [ss(1) ss(9) ss(5) ss(13) ss(3) ss(11) ss(7) ss(15) ss(2) ss(10) ss(6) ss(14) ss(4) ss(12) ss(8) ss(16)];

%первый шаг
s11 = s2r(1) + s2r(2);
s12 = s2r(1) - s2r(2);
s13 = s2r(3) + s2r(4);
s14 = s2r(3) - s2r(4);
s15 = s2r(5) + s2r(6);
s16 = s2r(5) - s2r(6);
s17 = s2r(7) + s2r(8);
s18 = s2r(7) - s2r(8);
s19 = s2r(9) + s2r(10);
s110= s2r(9) - s2r(10);
s111= s2r(11)+ s2r(12);
s112= s2r(11)- s2r(12);
s113= s2r(13)+ s2r(14);
s114= s2r(13)- s2r(14);
s115= s2r(15)+ s2r(16);
s116= s2r(15)- s2r(16);


%второй шаг

s21 = s11 + s13*W2(1);
s22 = s12 + s14*W2(5);
s23 = s11 - s13*W2(1);
s24 = s12 - s14*W2(5);

s25 = s15 + s17*W2(1);
s26 = s16 + s18*W2(5);
s27 = s15 - s17*W2(1);
s28 = s16 - s18*W2(5);

s29 = s19 + s111*W2(1);
s210 = s110 + s112*W2(5);
s211 = s19 - s111*W2(1);
s212 = s110 - s112*W2(5);

s213 = s113 + s115*W2(1);
s214 = s114 + s116*W2(5);
s215 = s113 - s115*W2(1);
s216 = s114 - s116*W2(5);

%шаг 3
s31 = s21 +  s25*W2(1);
s32 = s22 +  s26*W2(3);
s33 = s23 +  s27*W2(5);
s34 = s24 +  s28*W2(7);
s35 = s21 -  s25*W2(1);
s36 = s22 -  s26*W2(3);
s37 = s23 -  s27*W2(5);
s38 = s24 -  s28*W2(7);

s39 = s29 +  s213*W2(1);
s310= s210 + s214*W2(3);
s311= s211 + s215*W2(5);
s312= s212 + s216*W2(7);
s313 = s29 - s213*W2(1);
s314= s210 - s214*W2(3);
s315= s211 - s215*W2(5);
s316= s212 - s216*W2(7);

%шаг 4

s41 = s31 + s39*W2(1);
s42 = s32 + s310*W2(2);
s43 = s33 + s311*W2(3);
s44 = s34 + s312*W2(4);
s45 = s35 + s313*W2(5);
s46 = s36 + s314*W2(6);
s47 = s37 + s315*W2(7);
s48 = s38 + s316*W2(8);

s49 = s31 - s39*W2(1);
s410 = s32 - s310*W2(2);
s411 = s33 - s311*W2(3);
s412 = s34 - s312*W2(4);
s413 = s35 - s313*W2(5);
s414 = s36 - s314*W2(6);
s415 = s37 - s315*W2(7);
s416 = s38 - s316*W2(8);

Результат с матлабовской fft сошелся.

Хорошо. Напишите поподробнее пожалуйста как вы считаете коэффициенты? Wn = exp(-i*2*pi/n), n - размер фурье (число точек), i = [0 ..(n/2)-1] - номер коэффициента. А у Вас еще какой-то "k2" в формуле??????????

[serjj]

А может для этого существует какая-то программка специализированная, которая умеет считать коэффициенты? Никто не знает?

Matlab Считаем по формуле: w_sin(k) = imag(exp(-1i*2*pi*k/N)), w_cos(k) = real(exp(-1i*2*pi*k/N)), k=0...N-1

[Kapsik]

Хорошо. Напишите поподробнее пожалуйста как вы считаете коэффициенты? Wn = exp(-i*2*pi/n), n - размер фурье (число точек), i = [0 ..(n/2)-1] - номер коэффициента. А у Вас еще какой-то "k2" в формуле??????????

Вы в #11 привели картинку. Там есть поворачивающие множители W. Их коэффициенты 0,1,2,3. Они рассчитываются у меня как W2, коэффициенты 0,1,2,3 записаны в k2. Получается вектор коэффициентов W с картинки из #11.

[Dmitriyspb]

Matlab

Ах... простите=))) глупый вопрос

Вы в #11 привели картинку. Там есть поворачивающие множители W. Их коэффициенты 0,1,2,3. Они рассчитываются у меня как W2, коэффициенты 0,1,2,3 записаны в k2. Получается вектор коэффициентов W с картинки из #11.

Тогда вроде все укладывается. Даже понятно.
_________________________________________________
Тут другой вопросик. Если в бабочку грузить отсчеты по порядку 0,1,2,3... и.т.д. ны выходе получаем кашу. Для того, чтобы этой каши не было используют при загрузки бит-реверсивную перестановку отсчетов. Я правильно понял? Т.е. перемешиваем на входе и имеем по порядку на выходе ИЛИ имеем по порядку на входе, тогда перемешиваем на выходе, чтобы упорядочить?

to Kapsik
Я на verilog это все дело планирую транслировать.
Вы в matlab будете коэффициенты считать?

Эскизы прикрепленных изображений

 

[serjj]

Если в бабочку грузить отсчеты по порядку 0,1,2,3... и.т.д. ны выходе получаем кашу. Для того, чтобы этой каши не было используют при загрузки бит-реверсивную перестановку отсчетов. Я правильно понял? Т.е. перемешиваем на входе и имеем по порядку на выходе ИЛИ имеем по порядку на входе, тогда перемешиваем на выходе, чтобы упорядочить?

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

[Dmitriyspb]

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

Хорошо. Т.е.
1. Я складываю N (2048) отсчетов от АЦП в память.
2. После заполнения памяти начинаю вычитывать эти значения, НО вычитываю не по порядку а использую бит-реверсивный преобразователь адреса для памяти.

на этом этапе у меня есть корректные отсчеты в нужном порядке.

3. Теперь я прохожу необходимое кол-во ступеней преобразования отсчетов из временной области в частотную (БАБОЧКА)
3.1. Тут использую ROM с отсчетами Wk, которые использую при вычислениях.

4. Через постоянное времени моей цифровой системы начнут выскакивать отсчеты в правильном порядке.

5. Эти отсчеты уже можно перенести на плоскость с заданным шагом (Частота дискретизации/ число точек)?????

[serjj]

5. Эти отсчеты уже можно перенести на плоскость с заданным шагом (Частота дискретизации/ число точек)?????

Если в вашем преобразовании есть восстановление порядка следования, то да. При этом смотрим например альтеровскую корку. Там есть опции прямого и обратного следования. В кастомизируемых корках еще может быть опция центрирования, когда 0 стоит не в начале выборки а в 1, что удобно в некоторых приложениях спектрального анализа.

Подумайте сразу еще и о скалирование результатов умножения. Чтобы потом не было сюрпризов. Это нужно делать на каждом этапе при целочисленной реализации. Очень важный и тонкий момент реализации. При этом FFT может выступать в качестве некоторого АРУ. Исходный масштаб можно восстановить, если вы будете накапливать информацию о скалировании с каждого шага.

[Dmitriyspb]

Если в вашем преобразовании есть восстановление порядка следования, то да.

Если я их загружаю в БАБОЧКУ в бит-реверсивном порядке, тогда у меня на выходе все должно быть упорядочено. Верно понимаю?

На счет скалирования (по просту говоря масштабирования) еще не думал. Ткните пожалуйста где почитать можно.

[serjj]

Если я их загружаю в БАБОЧКУ в бит-реверсивном порядке, тогда у меня на выходе все должно быть упорядочено. Верно понимаю?

Это от алгоритма будет зависить. Можно сделать 1001 способом. Логичнее все манипуляции с перестановками делать отдельно а бабочку отдельно и кормить ее всегда данными, вычитываемыми по порядку. На dsplib объясняются 2 самых основных подхода к мультиплексированию, но наверное есть еще всякие частные решения, заточенные под конкретное железо.

Хы, какой я раритет нашёл, очень винтажно
 kabalr1985.pdf ( 1.34 мегабайт ) Кол-во скачиваний: 194

Хоть самому читай. Ну а вообще поиск по scaling during fft stages можно смотреть.

[Dmitriyspb]

А что по этому поводу думает уважаемый Kapsik? Как он все это дело планирует в verilog описывать. Можно функционально рассказать

Это от алгоритма будет зависить. Можно сделать 1001 способом. Логичнее все манипуляции с перестановками делать отдельно а бабочку отдельно и кормить ее всегда данными, вычитываемыми по порядку. На dsplib объясняются 2 самых основных подхода к мультиплексированию, но наверное есть еще всякие частные решения, заточенные под конкретное железо.

Хы, какой я раритет нашёл, очень винтажно
 kabalr1985.pdf ( 1.34 мегабайт ) Кол-во скачиваний: 194

Хоть самому читай. Ну а вообще поиск по scaling during fft stages можно смотреть.

спасибо

[Kapsik]

А что по этому поводу думает уважаемый Kapsik?

Хех, уважаемый, приятно, но боюсь пока не заслуженно ;-)

Набросал вот такую блочную схему. Коротенько описание. ser2par сдвиговый регистр, в нем копятся 16 отсчетов. Lat_data защелкивает эти отсчеты одновременно совершая перестановку. Далее идет мультиплексор который коммутирует отсчеты по нужным бабочкам, на выходе бабочек умножение и все по новой. Интересно, что скажут остальные по поводу такой реализации

.

[Dmitriyspb]

Интересно, что скажут остальные по поводу такой реализации

Остальные пока молчат.
Вот моя версия. Думаю что-то очень похожее.

А дальше что вы планируете с этими отсчетами делать?

Эскизы прикрепленных изображений

 

[Kapsik]

Остальные пока молчат.
Вот моя версия. Думаю что-то очень похожее.

А дальше что вы планируете с этими отсчетами делать?

Вообще я делаю эквалайзер. Так что буду выводить на VGA моник.

[Dmitriyspb]

Вообще я делаю эквалайзер. Так что буду выводить на VGA моник.

вы в Matlab коэффициенты считать для ROM будите? или уже посчитали?

[Kapsik]

вы в Matlab коэффициенты считать для ROM будите? или уже посчитали?

Да, в матлабе посчитаю и в mif засуну.

[Dmitriyspb]

Товарищи, правильно ли я считаю коэффициент для своей бабочки????????????????????????????????
В коде приведено k=2, N=2048;

Код

>> k=2;
>> N=2048;
>> W2=exp(-j*2*pi*k/N)

W2 =

   1.0000 - 0.0061i

>> W2= 1-0.0061

W2 =

    0.9939

>> % Преобразовываю в 16-ти разрядную
>> % целочисленную форму (1бит-знаковый + 15бит мантисса)
>>  L = (2^15)-1

L =

       32767

>> F = W2*L

F =

  3.2567e+004

>> round (F)

ans =

       32567;

[serjj]

Код

>> W2= 1-0.0061

W2 =

    0.9939

Воу воу, это что? Коэффициент комплексный и умножение должно быть комплексным, а вы зачем-то из Re Im вычитаете.

[Dmitriyspb]

Код

>> W2= 1-0.0061

W2 =

    0.9939

Воу воу, это что? Коэффициент комплексный и умножение должно быть комплексным, а вы зачем-то из Re Im вычитаете.

Вот тут, та я и больше всего не понимаю.

Как мне комплексное число перевести в целочисленную форму????

[serjj]

Как мне комплексное число перевести в целочисленную форму????

комплексное число с точки зрения обработки это 2 числа: real(a) и imag(a). Переводите их отдельно. А все рассчёты нужно привести к форме re(a_new) = f_re(re(a_old), im(a_old)), im(a_new) = f_im(re(a_old), im(a_old)), благо все основные комплексные операции, с которыми программисту приходится иметь дело, допускают такую форму записи.

[Dmitriyspb]

комплексное число с точки зрения обработки это 2 числа: real(a) и imag(a). Переводите их отдельно. А все расчёты нужно привести к форме re(a_new) = f_re(re(a_old), im(a_old)), im(a_new) = f_im(re(a_old), im(a_old)), благо все основные комплексные операции, с которыми программисту приходится иметь дело, допускают такую форму записи.

перевел, а вот как потом на них умножать отсчеты? Отсчеты имеют целочисленную форму

[Xenia]

Считали бы, как нормальные люди , через синус и косинус. А эти комплексные экспоненты - в мусор! Нечего человеку мозги засорять.

[serjj]

Считали бы, как нормальные люди sm.gif, через синус и косинус. А эти комплексные экспоненты - в мусор! sm.gif Нечего человеку мозги засорять.

Ну без понимание формулы Эйлера нельзя браться за Фурье

перевел, а вот как потом на них умножать отсчеты? Отсчеты имеют целочисленную форму

(a_re + j*a_im)(w_re + j*w_im) = (a_re*w_re - a_im*w_im) + j*(a_re*w_im + a_im*w_re)

можно, но функции синуса и косинуса реализовываются в ПЛИС довольно проблематично (требуется использование Cordic)

Имеется в виду табличные синус/косинус, которые потом также и умножаются на входные отчёты, но только это тоже самое получается что и комплексная экспонента, только понимания меньше. А вообще таки да слышал про Фурье на кордиках, но сам не видел

Сообщение отредактировал serjj - Apr 22 2015, 12:36

[Dmitriyspb]

Считали бы, как нормальные люди , через синус и косинус. А эти комплексные экспоненты - в мусор! Нечего человеку мозги засорять.

Да уж, я вот и буксую.

Вот как сделать из вещественных входных отсчетов АЦП отсчеты I и Q я догадываюсь (I и Q - это вроде как и есть комплексное представление сигнала). Попросту говоря синус и косинус. И дальше для них будет две независимые ветки БПФ и коэффициенты БПФ (Wn) у каждого будут тоже свои. Верно понимаю?
Т.О. из комплексного выражения W1=x1+y1i
x - это мои коэффициент W1 для косинуса
y - это мои коэффициент W1 для синуса

[serjj]

Вот как сделать из вещественных входных отсчетов АЦП отсчеты I и Q я догадываюсь (I и Q - это вроде как и есть комплексное представление сигнала). Попросту говоря синус и косинус. И дальше для них будет две независимые ветки БПФ и коэффициенты БПФ (Wn) у каждого будут тоже свои. Верно понимаю?
Т.О. из комплексного выражения W1=x1+y1i
x - это мои коэффициент W1 для косинуса
y - это мои коэффициент W1 для синуса

Неверно. Мнимая часть вносит вклад в рассчёт выходной действительной и наоборот. См. комплексное умножение.

[Dmitriyspb]

(a_re + j*a_im)(w_re + j*w_im) = (a_re*w_re - a_im*w_im) + j*(a_re*w_im + a_im*w_re)

Тут a_re - косинус, a_im - синус для входных отсчетов.
Аналогично для коэффициентов.
Вроде бы понял.

Вот только получается две ветки БПФ? для синуса и косинуса?

[serjj]

Тут a_re - косинус, a_im - синус для входных отсчетов.
Аналогично для коэффициентов.
Вроде бы понял.

Вот только получается две ветки БПФ? для синуса и косинуса?

a_re - действительная часть, a_im - мнимая. Преобразование Фурье определено для множества комплексных чисел, его нельзя вот так взять и сделать отдельно для действительной и мнимой частей. Если вы подадите в Фурье действительный сигнал (мнимая часть = 0), то на выходе вы будете иметь комплексный сигнал (мнимая часть != 0). Косинус и синус хорошие примеры для комплексной синусоиды exp(1i*2*pi*f*t), но ими не исчерпываются все комплексные числа

[Dmitriyspb]

a_re - действительная часть, a_im - мнимая. Преобразование Фурье определено для множества комплексных чисел, его нельзя вот так взять и сделать отдельно для действительной и мнимой частей. Если вы подадите в Фурье действительный сигнал (мнимая часть = 0), то на выходе вы будете иметь комплексный сигнал (мнимая часть != 0). Косинус и синус хорошие примеры для комплексной синусоиды exp(1i*2*pi*f*t), но ими не исчерпываются все комплексные числа

Я запутался.
Я понял, что коэффициенты я имею в комплексной форме,значит, отсчеты у меня должны быть тоже в комплексной форме. Так или снова не туда?

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

Меня больше всего смущает комплексное представление коэффициентов (Wn) БПФ, а отсчеты вещественные.
В итоге мне нужно сделать коэффициенты как отсчеты или отсчеты как коэффициенты?????
или можно и так и так???

[Swup]

Вещественные числа - подмножество комплексных числе.
Ваше вещественное число А на самом деле комплексное число А+j*0. Т.е. вещественное число это такое комплексное число у которого нулевая мнимая часть. Как вам верно заметили выше преобразование фурье -комплексная операция.

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

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

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

[Xenia]

Меня больше всего смущает комплексное представление коэффициентов (Wn) БПФ, а отсчеты вещественные.
В итоге мне нужно сделать коэффициенты как отсчеты или отсчеты как коэффициенты?????

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

[Kapsik]

Мне показалось, что рисовать бабочки текстом это перебор, так что прикрепляю картинку. Реальная и мнимая части отдельно, я вижу так =)

[Dmitriyspb]

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

Ага, понял. Спасибо огромное.

Нашел такую инфу и стараюсь её приложить к своей практической плоскости (см. картинки).


Основываясь на этом родил такую структуру (см. картинки)


Верно я понял или же нет?

[serjj]

Основываясь на этом родил такую структуру (см. картинки)

Как вы не хотите понять, что БПФ делается не отдельно для Re и Im каналов с Re и Im коэффициентами, а для комплексного сигнала с комлпексными коэффициентами и имеет комплексный выход. Если вы хотите дальше выход Фурье использовать для спектрального анализа, то вы можете перейти к abs(out), напряжение, или (abs(out))^2, мощность, out - комплексный.

[Dmitriyspb]

Как вы не хотите понять, что БПФ делается не отдельно для Re и Im каналов с Re и Im коэффициентами, а для комплексного сигнала с комлпексными коэффициентами и имеет комплексный выход. Если вы хотите дальше выход Фурье использовать для спектрального анализа, то вы можете перейти к abs(out), напряжение, или (abs(out))^2, мощность, out - комплексный.

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

Мне показалось, что рисовать бабочки текстом это перебор, так что прикрепляю картинку. Реальная и мнимая части отдельно, я вижу так =)

Тут тоже говорят об отдельном. Где подвох?

[Kapsik]

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





Тут тоже говорят об отдельном. Где подвох?

Дык я же и расписал по отдельности. Re и Im. Видно что результат совпал, с "прямым" расчетом...

[Dmitriyspb]

Дык я же и расписал по отдельности. Re и Im. Видно что результат совпал, с "прямым" расчетом...

ТОВАРИЩИ, мне кажется, что я понял=)))))

то вы можете перейти к abs(out), напряжение, или (abs(out))^2, мощность, out - комплексный.

Поясните пожалуйста

[serjj]

Вы скажите пожалуйста как Вы представляете себе в железе комплексный сигнал

Это два логических сигнала, которые представляют собой один физический сигнал но не нужно путать это с двумя действительными каналами, т.к. в случае с каналами каждый сигнал обрабатывается независимо (ну или до какого то этапа обработки независимо, в любом случае каждый канал это отдельный физический сигнал). В случае же с комплексным числом логические сигналы Re и Im обрабатываются по правилами комплексной арифметики. Соответственно БПФ для них одно, как вы и нарисовали.

ТОВАРИЩИ, мне кажется, что я понял=)))))
...
Поясните пожалуйста

Вы определенно на пути к истине. Осталось подумать что же неверно в "Участок 4"
После Фурье вы получили комлексный частотный образ входного комплексного сигнала. Если вы возьмёте модуль комплексного числа, то получите АЧХ, если аргумент - то ФЧХ, если квадрат модуля, то спектральную плотность мощности.

Сообщение отредактировал serjj - Apr 23 2015, 08:37

[Dmitriyspb]

Вы определенно на пути к истине. Осталось подумать что же неверно в "Участок 4"
После Фурье вы получили комлексный частотный образ входного комплексного сигнала. Если вы возьмёте модуль комплексного числа, то получите АЧХ, если аргумент - то ФЧХ, если квадрат модуля, то спектральную плотность мощности.

Спасибо за пояснения=)
Продолжим!
ФЧХ и АЧХ меня не интересуют. Меня интересует спектр сигнала, поэтому беру квадрат модуля комплексного сигнала.

На деле же, моя структура будет иметь вид


правильно понял?

[serjj]

Да. Формально в схему еще нужно добавить RAM для Re и Im на выходе БПФ. И я подозреваю, что на 2-м участке у вас после ФНЧ должна стоять децимация. Если же Фурье делается на символьной частоте АЦП, то ФНЧ и перенос частоты не нужны, т.к. само Фурье обеспечивает фильтрацию, а зная полосу сигнала, который вы анализируете, вы просто берёте отсчёты частотного образа, которые попадают в эту полосу и работаете только с ними (это встречается например в приложениях с низкочастотной обработкой в акустике). Ну а так вроде всё норм.

[Swup]

Спектр Фурье это разложение сигнала на сумму комплексных экспонент. т.е. то что у вас есть на выходе БПФ - это спектр вашего сигнала.
Далее вы берете и из каждой комплексной экспоненты представленной в виде re+j*im выделяете амплитуду по формуле Эйлера. И получаете... Амплитудный спектр, т.е. распределение амплитуд по частоте или попросту говоря амплитудно-частотную характеристику. Ну а есть брать квадрат амплитуд то будет спектр мощности.

[Dmitriyspb]

Да. Формально в схему еще нужно добавить RAM для Re и Im на выходе БПФ.

Да, вы правы. Добавлю.

Если же Фурье делается на символьной частоте АЦП, то ФНЧ и перенос частоты не нужны, т.к. само Фурье обеспечивает фильтрацию, а зная полосу сигнала, который вы анализируете, вы просто берёте отсчёты частотного образа, которые попадают в эту полосу и работаете только с ними (это встречается например в приложениях с низкочастотной обработкой в акустике).

На мой взгляд это проще. Думаю так и поступить.
Частота дискретизации АЦП 5 МГц.
Полоса анализа (ширина полосы сигнала) 1 МГц.
Частота обработки БПФ тоже 5 МГц

учитывая эту информацию

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

Тогда структура принимает вид?


Или так не стоит дополнять нулевой мнимой частью?

[serjj]

Тогда структура принимает вид
...
Или так не стоит дополнять нулевой мнимой частью?

Вроде бы нормально все. Да, делайте преобразование в общем виде (как для комплексного сигнала по алгоритму) и на вход Im просто нули подавайте.

[Dmitriyspb]

Вроде бы нормально все. Да, делайте преобразование в общем виде (как для комплексного сигнала по алгоритму) и на вход Im просто нули подавайте.

Прекрасно. Тогда я вроде бы не без помощи от добрых и умных людей сформулировать общий вид структуры.

тогда приступим к детальному рассмотрению БПФ.

Ту мне кажется для меня все понятнее, но все же постараюсь сформулировать.

Частота дискретизации для АЦП 5 МГц
БПФ будет производиться на этих же 5 МГц
Планирую для простоты для начала реализовать 128 точек.
________________________________________________________
Для полного объединения спектра размерностью 128 отсчетов требуется выполнить log2 128 циклов операций "бабочка".
Итого log2 128 =7 циклов
при этом каждый цикл состоит из 64 операций, т.к. при основании 2 в одной базовой операции БПФ задействовано 2 входных отсчета.
_________________________________________________________

общее число поворачивающих к-тов равно половине размерности входного сигнала 128/2 = 64 к-тов

_________________________________________________________
Верно я излагаю?

[des00]

ТС в форуме про плисы, есть тема про БПФ. Пишут вместе с начинающим с начала и до конца.

[Dmitriyspb]

ТС в форуме про плисы, есть тема про БПФ. Пишут вместе с начинающим с начала и до конца.

Думаю этот пост претендует на самый "ПОЛЕЗНЫЙ"

Всегда особенно ценил подобные советы

[mihalevski]

удален

Сообщение отредактировал mihalevski - May 9 2015, 15:18

[Krys]

Или так не стоит дополнять нулевой мнимой частью?

Учитывая, что сигнал чисто вещественный, то спектр в отрицательной области будет комплексно-сопряжённым, следовательно при использовании полноценного БПФ для комплексных входных сигналов половина отсчётов будет избыточна. Избыточны и ресурсы на её расчёт.
Для расчёта спектра чисто вещественных сигналов используются особые модификации БПФ. Если не путаю DCT (дискретное косинус-преобразование). Короче гуглить надо, но смысл есть. Поискал у себя - чего-то с ходу не нашёл. Кажется припоминаю, что об этом всём должно быть во многих основополагающих книжках того же Лайноса, Рабинера с Голдом, Оппенгейма и т.п. Теория то давно придумана и задокументирована в букварях, велосипед изобретать не надо. Просто почитать самые канонические буквари.

(a_re + j*a_im)(w_re + j*w_im) = (a_re*w_re - a_im*w_im) + j*(a_re*w_im + a_im*w_re)

Добавлю. При реализации на ПЛИС иногда удобнее пользоваться формулой с тремя умножениями и 5 сложениями, т.к. DSP-блоков меньше съедается. Сама формула есть в датащите на дсп-блок от спартана6.

[Dmitriyspb]

Для расчёта спектра чисто вещественных сигналов используются особые модификации БПФ. Если не путаю DCT (дискретное косинус-преобразование).

Вы в этом уверены???????????????????????????????????
Мне кажется, что Вы что-то путаете. Ведь БПФ это и есть адаптация ДПФ к вычислительным мощностям маломощных ЭВМ.

А DCT используется в алгоритмах сжатия информации.

[Krys]

есть быстрое косинус-преобразование, по аналогии с быстрым Фурье-преобразованием. Я не то, чтобы не путаю. Я просто назвал общий класс преобразований, а быстрое или не быстрое - это уже подклассы. Главное, что это не Фурье, а косинус-преобразование, которое использует половину ресурсов.
Вы лучше взгляните главы книжек авторов, которые я назвал. Хотя бы пробегитесь по диагонали, может найдёте именно это. Я действительно уже подзабыл.

[Dmitriyspb]

есть быстрое косинус-преобразование, по аналогии с быстрым Фурье-преобразованием. Я не то, чтобы не путаю. Я просто назвал общий класс преобразований, а быстрое или не быстрое - это уже подклассы. Главное, что это не Фурье, а косинус-преобразование, которое использует половину ресурсов.
Вы лучше взгляните главы книжек авторов, которые я назвал. Хотя бы пробегитесь по диагонали, может найдёте именно это. Я действительно уже подзабыл.

Спасибо за советы. Обязательно взгляну и сразу дело пойдет в гору. Спасибо ещё раз.

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

[Guest_TSerg_*]

P.S. давайте по делу больше, а не писать названия знакомых книжек.

Т.е. - пересказывать их?

[Dmitriyspb]

Т.е. - пересказывать их?

хм!? наизусть

[thermit]

Спасибо за советы. Обязательно взгляну и сразу дело пойдет в гору. Спасибо ещё раз.

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

Если нужно дпф над вещественными данными, можно его выполнить через комплексное половинной длины.

http://electronix.ru/forum/index.php?showt...t&p=1227495

2-е формулы.

[Dmitriyspb]

Если нужно дпф над вещественными данными, можно его выполнить через комплексное половинной длины.

http://electronix.ru/forum/index.php?showt...t&p=1227495

2-е формулы.

Тогда возникает вопрос, а в чем преимущества алгоритма с полными комплексными числами перед алгоритмом, где только вещественная часть сигнала фигурирует?

[thermit]

Тогда возникает вопрос, а в чем преимущества алгоритма с полными комплексными числами перед алгоритмом, где только вещественная часть сигнала фигурирует?

Выход дпф есть комплексная последовательность вне зависимости от того, какие данные на входе.
Если входные данные вещественны, есть 2 варианта вычисления дпф:

1. Представить входную последовательность как комплексную, но половинной длины и выполнить дпф половинной длины. Затем преобразовать полученную посл в дпф исходной (см формулы).
2. Выполнить над исходной последовательностью преобразование хартли полной длины. Оно чисто вещественное. Затем преобразовать полученную последовательность в дпф при помощи несложных вычислений.

оба способа практически не отличаются с точки зрения ресурсов.

[Krys]

Спасибо за советы. Обязательно взгляну и сразу дело пойдет в гору. Спасибо ещё раз.

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

Я так понимаю, Вы обиделись на советы почитать книжки и считаете их бесполезными или малополезными в виду неопределённости границ поиска? ))) А зря. Я сам не люблю, когда мне советуют почитать книжки, подразумевая в косвенной форме идти обратно учиться 5 лет в вузе ))) В данном случае я подразумевал, что я где-то встречал конкретную информацию. Нужно открыть книжки в оглавлении, найти главу про преобразование Фурье, там либо подглава будет про преобразование над вещественными данными, либо бегло пролистать текст главы просто самому, может что-то попадётся.
Попробую найти время, сам пробегусь. Заодно освежу в памяти

[Dmitriyspb]

Выход дпф есть комплексная последовательность вне зависимости от того, какие данные на входе.
Если входные данные вещественны, есть 2 варианта вычисления дпф:

1. Представить входную последовательность как комплексную, но половинной длины и выполнить дпф половинной длины. Затем преобразовать полученную посл в дпф исходной (см формулы).
2. Выполнить над исходной последовательностью преобразование хартли полной длины. Оно чисто вещественное. Затем преобразовать полученную последовательность в дпф при помощи несложных вычислений.

оба способа практически не отличаются с точки зрения ресурсов.

Этот момент я усвоил. Спасибо за комментарий. Мне вот интересно: если используя два описанных Вами метода реализовывать анализатор спектра, то результат будет одинаковый, либо будет какая-то разница? Ресурсов потребуется одинаково (если я правильно понял). Хочется понять практическую ценность этих двух методов. Или они просто идентичные и какой больше нравится тем и пользуйся?

Я так понимаю, Вы обиделись на советы почитать книжки и считаете их бесполезными или малополезными в виду неопределённости границ поиска? ))) А зря. Я сам не люблю, когда мне советуют почитать книжки, подразумевая в косвенной форме идти обратно учиться 5 лет в вузе ))) В данном случае я подразумевал, что я где-то встречал конкретную информацию. Нужно открыть книжки в оглавлении, найти главу про преобразование Фурье, там либо подглава будет про преобразование над вещественными данными, либо бегло пролистать текст главы просто самому, может что-то попадётся.
Попробую найти время, сам пробегусь. Заодно освежу в памяти

Давайте по теме и Объективно! Все хорошо

[Krys]

Вот по теме нашёл для Вас: Лайонс_-_ЦОС_2е_издание_русский_перевод_2006.djvu. Страница 483. Глава 13.5. Эффективное вычисление БПФ действительных последовательностей.

[Dmitriyspb]

Вот по теме нашёл для Вас: Лайонс_-_ЦОС_2е_издание_русский_перевод_2006.djvu. Страница 483. Глава 13.5. Эффективное вычисление БПФ действительных последовательностей.

Спасибо Вам огромное. Ведь можем когда хотим
Пошел читать
______________________________________________________________________________
Сейчас ситуация следующая. Алгоритм я выбрал и разобрался с ним. Сейчас упорно ковыряю fft на verilog под fpga. По реализации вопросов не имею. Если возникнут, тогда это уже будет другая ветка по ПЛИС.

А вот для кругозора я почитаю как это можно сделать иначе.

[Krys]

Спасибо Вам огромное. Ведь можем когда хотим

Ага, мы можем, когда Вы хотите ))) Пожалуйста ))

Алгоритм я выбрал и разобрался с ним

На чём остановились?

Если возникнут, тогда это уже будет другая ветка по ПЛИС.

Возникнут... )) С разрядностью, гейном, округлением...

[thermit]

Dmitriyspb:
Этот момент я усвоил. Спасибо за комментарий. Мне вот интересно: если используя два описанных Вами метода реализовывать анализатор спектра, то результат будет одинаковый, либо будет какая-то разница? Ресурсов потребуется одинаково (если я правильно понял). Хочется понять практическую ценность этих двух методов. Или они просто идентичные и какой больше нравится тем и пользуйся?

Одинаковы с точностью до ошибок вычислений.

[Dmitriyspb]

Ага, мы можем, когда Вы хотите ))) Пожалуйста ))

И все равно надо что-то написать

На чём остановились?

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

Возникнут... )) С разрядностью, гейном, округлением...

Я тут покопался на форуме и нашел где объясняли как округлять (популярным языком). Ссылка есть во втором посте

Ага, мы можем, когда Вы хотите ))) Пожалуйста ))

На чём остановились?

Возникнут... )) С разрядностью, гейном, округлением...

Вот Вы человек способный, умный.... пишите без ошибок, пунктуацию соблюдаете, книжек много знаете разных, возможно их читаете. Такие люди как Вы обычно знают много....может поможете....

Меня волнует еще отвлеченный от этой темы вопрос

[Krys]

И все равно надо что-то написать

А как же )) Мы, злостные флудеры, такие ))) Расслабьтесь. Мы же сюда заходим не только работать, но и отдохнуть от работы. Лёгкий флуд - терпимо.

[Dmitriyspb]

А как же )) Мы, злостные флудеры, такие ))) Расслабьтесь. Мы же сюда заходим не только работать, но и отдохнуть от работы. Лёгкий флуд - терпимо.

Ах...вот оно что?!

[Dmitriyspb]

Уважаемые форумчане Возникли трудности, прошу по возможности помощи.
Речь о БПФ, если кто не в курсе.
1. Бабочка по основанию 2
2. 16 точек
3. Частота дискретизации 5 МГц
4. Прореживание во времени
5. Соответственно 8 коэффициентов
6. Реализация на ПЛИС (verilog).
7. Моделирую в Modelsim
8. Пытаюсь проверить работу алгоритма в Mathlab
________________________________________________________________________________
_
Я построил свою работу следующим образом:
1. Используя описание 16-ти точечного БПФ в Матлаб рассчитал коэфициенты и подставил удобные для себя входные отсчеты. В итоге построил график , на котором увидел ожидаемую для себя картинку при входных отсчетах

Код

ss = [828 1515 1943 2038 1784 1225 457 -390 -1170 -1750 -2030 -1963 -1560 -890 -68 0];

и коэффициентах

Код

w0 = (1+0i);
w1 = (0.9239-0.3827i);
w2 = (0.7071-0.7071i);
w3 = (0.3827-0.9239i);
w4 = (0-1i);
w5 = (-0.3827-0.9239i);
w6 = (-0.7071-0.7071i);
w7 = (-0.9239-0.3827i);

2. После этого зная из Матлаб результаты всех вычислений я переместился в Modelsim и начал там тестировать свой БПФ описанный на Verilog. В качестве входных значений я использовал те же, что и в Матлаб представленных в дополнительном коде. т.е. мантисса занимает биты с 0 по 10, а 11 бит знаковый в итоге диапазон входных значений от -2047 до +2047.
С коэффициентами иначе. Та как коэффициенты у меня меняются от -1 до +1, тогда я их домножил на все те же 2047 и округлил, 11 битом прикрепил знак. В итоге мои коэффициенты стали иметь вид:

Код

w0 = 2047 + 0i;
w1 = 1891-783i;
w2 = 1447-1447i;
w3 = 783-1891i;
w4 = 0-2047i;
w5 = -783-1891i;
w6 = -1447 - 1447i;
w7= -1891-783i;

3. И тут я как "умная Маша" попытался засунуть округленные коэффициенты в целочисленной форме в Матлаб. В итоге у меня на выходе ерунда вместо прежней картинки.
И я не понимаю почему????
Нужно что-то менять в матлаб? Просто мне никак не проверить корректность работы БПФ описанного verilog. Хочется иметь одни и те же коэффициенты и в Матлаб и в Моделсим.

Привожу код БПФ из Матлаб

Код

ss = [828 1515 1943 2038 1784 1225 457 -390 -1170 -1750 -2030 -1963 -1560 -890 -68 0];
%k2 = [0:7];
%W2 = exp( -j*2*pi.*k2/16 );
w11 = (1+0i);
w12 = (0.9239-0.3827i);
w13 = (0.7071-0.7071i);
w14 = (0.3827-0.9239i);
w15 = (0-1i);
w16 = (-0.3827-0.9239i);
w17 = (-0.7071-0.7071i);
w18 = (-0.9239-0.3827i);

W2 = [ w11 w12 w13 w14 w15 w16 w17 w18];
s2r = [ss(1) ss(9) ss(5) ss(13) ss(3) ss(11) ss(7) ss(15) ss(2) ss(10) ss(6) ss(14) ss(4) ss(12) ss(8) ss(16)];

%первый шаг
s11 = s2r(1) + s2r(2);
s12 = s2r(1) - s2r(2);
s13 = s2r(3) + s2r(4);
s14 = s2r(3) - s2r(4);
s15 = s2r(5) + s2r(6);
s16 = s2r(5) - s2r(6);
s17 = s2r(7) + s2r(8);
s18 = s2r(7) - s2r(8);
s19 = s2r(9) + s2r(10);
s110= s2r(9) - s2r(10);
s111= s2r(11)+ s2r(12);
s112= s2r(11)- s2r(12);
s113= s2r(13)+ s2r(14);
s114= s2r(13)- s2r(14);
s115= s2r(15)+ s2r(16);
s116= s2r(15)- s2r(16);


%второй шаг

s21 = s11 + s13* W2(1);
s22 = s12 + s14* W2(5);
s23 = s11 - s13* W2(1);
s24 = s12 - s14* W2(5);

s25 = s15 + s17* W2(1);
s26 = s16 + s18* W2(5);
s27 = s15 - s17* W2(1);
s28 = s16 - s18* W2(5);

s29 = s19 + s111* W2(1);
s210 = s110 + s112*W2(5);
s211 = s19 - s111* W2(1);
s212 = s110 - s112*W2(5);

s213 = s113 + s115*W2(1);
s214 = s114 + s116*W2(5);
s215 = s113 - s115*W2(1);
s216 = s114 - s116*W2(5);

%шаг 3
s31 = s21 +  s25*W2(1);
s32 = s22 +  s26*W2(3);
s33 = s23 +  s27*W2(5);
s34 = s24 +  s28*W2(7);
s35 = s21 -  s25*W2(1);
s36 = s22 -  s26*W2(3);
s37 = s23 -  s27*W2(5);
s38 = s24 -  s28*W2(7);

s39 = s29 +  s213*W2(1);
s310= s210 + s214*W2(3);
s311= s211 + s215*W2(5);
s312= s212 + s216*W2(7);
s313 = s29 - s213*W2(1);
s314= s210 - s214*W2(3);
s315= s211 - s215*W2(5);
s316= s212 - s216*W2(7);

%шаг 4

s41 = s31 + s39*W2(1);
s42 = s32 + s310*W2(2);
s43 = s33 + s311*W2(3);
s44 = s34 + s312*W2(4);
s45 = s35 + s313*W2(5);
s46 = s36 + s314*W2(6);
s47 = s37 + s315*W2(7);
s48 = s38 + s316*W2(8);

s49 = s31 - s39*W2(1);
s410 = s32 - s310*W2(2);
s411 = s33 - s311*W2(3);
s412 = s34 - s312*W2(4);
s413 = s35 - s313*W2(5);
s414 = s36 - s314*W2(6);
s415 = s37 - s315*W2(7);
s416 = s38 - s316*W2(8);

%Строим график

x = [0 : 15];
y = [s41, s42, s43, s44, s45, s46, s47, s48, s49, s410, s411, s412, s413,s414, s415, s416];
plot (x, y)

[Krys]

решили проблему? В чём была ошибка?

[Corner]

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

[Krys]

К счастью, в доп.коде операции делаются идентично, поэтому указание знака необязательно. Лично я ставлю reg signed или wire signed только для того, чтобы в симуляторе наблюдать сразу знаковые значения.

[Corner]

Да, в матлабе посчитаю и в mif засуну.

Quartus поддерживает инструкцию $readmemh для блочного ROM в Verilog. Вообще не надо париться с написанием. Забил reg. Прописал $readmemh в initial.

К счастью, в доп.коде операции делаются идентично, поэтому указание знака необязательно. Лично я ставлю reg signed или wire signed только для того, чтобы в симуляторе наблюдать сразу знаковые значения.

Ничего подобного. При умножении надо указывать $signed иначе будет непредсказуемая ерунда, даже если указана знаковая переменная.

[novartis]

Пока тема свежая, задамка вопрос по БПФ.

Вот написал я свое ядро бпф.
Работает оно так, что подаю на вход N точек, оно N*log(N) тактов рассчитает результат.
И получается, что пока производится расчет я не могу на вход подавать следующий кадр, так как внутри задействована память на N отсчетов, умножитель, два сумматора, и во время расчета они постоянно заняты, конвеером пустить новые данные ну ни как.
А вот у альтеры и ксайлинка ip-ядра способны принимать новые кадры без пауз.
Как это у них реализовано?

Самый дубовый вариант - буферизировать входные данные. Но размер буфера будет определяться величиной log(N), а у альтеры/ксайлинкса не наблюдается, чтобы ядро требовало больше памяти, чем под один кадр.

[TRILLER]

Пока тема свежая, задамка вопрос по БПФ.

Вот написал я свое ядро бпф.
Работает оно так, что подаю на вход N точек, оно N*log(N) тактов рассчитает результат.
И получается, что пока производится расчет я не могу на вход подавать следующий кадр, так как внутри задействована память на N отсчетов, умножитель, два сумматора, и во время расчета они постоянно заняты, конвеером пустить новые данные ну ни как.
А вот у альтеры и ксайлинка ip-ядра способны принимать новые кадры без пауз.
Как это у них реализовано?

Самый дубовый вариант - буферизировать входные данные. Но размер буфера будет определяться величиной log(N), а у альтеры/ксайлинкса не наблюдается, чтобы ядро требовало больше памяти, чем под один кадр.

Вообще-то обычный Радикс-2/4 работает именно кадрами. Накапление->вычисление->выдача результата(накопление). Есть ещё по-моему потоковый алгоритм у них, но только на небольшое число точек и с большим ресурсом..
В своё время делал FFT - при разумной полосе спектра сигнала(скажем до 50 МГц) вполне хватает буфера на N точек.
1. Ядро вполне реально разогнать до максимальной частоты BRAM/DSP - смотря что меньше. Пусть будет 500. А это сразу даёт 10 тактов вычисления на 1 такт данных.
2. Первую бабочку можно сделать сразу в момент прихода второй половины входных отсчётов, так как там коэффициенты только единицы.
3. При реализации БПФ с прореживанием по частоте довольно легко при каждом следующем проходе увеличивать число ядер вдвое(в разумных пределах), так как области данных между собой больше не пересекаются и в связи с этим можно разграничить доступ к области памяти.
Всё это конечно усложняет реализацию, но бывают случаи, когда это меньшее из зол.

[novartis]

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

[Fat Robot]

Бегло читаем документ.

Находим в нем "The variable streaming FFTs implement either a radix-2^2 single delay feedback FFT, ..."

Ищем гуглом "sdf fft" или "r4sdf fft", или "r2sdf fft"

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

[Corner]

Пока тема свежая, задамка вопрос по БПФ.

Вот написал я свое ядро бпф.
Работает оно так, что подаю на вход N точек, оно N*log(N) тактов рассчитает результат.
И получается, что пока производится расчет я не могу на вход подавать следующий кадр, так как внутри задействована память на N отсчетов, умножитель, два сумматора, и во время расчета они постоянно заняты, конвеером пустить новые данные ну ни как.
А вот у альтеры и ксайлинка ip-ядра способны принимать новые кадры без пауз.
Как это у них реализовано?

Самый дубовый вариант - буферизировать входные данные. Но размер буфера будет определяться величиной log(N), а у альтеры/ксайлинкса не наблюдается, чтобы ядро требовало больше памяти, чем под один кадр.

Самый дубовый вариант, это поставить N блоков БПФ и коммутировать поотсчетно, подавая их на входы со сдвигом на отсчет. А у Altera и Xilinx используется БПФ со сдвигом не на отсчет, а на 1/2... 1/4 размера блока. По сути, имеется 2... 4 БПФ блока. В результате, на выходе почти отсутствуют разрывы фазы. Но такое преобразование годится не для всех видов модуляции. Иногда приходится делать перекрытие еще меньше 1/4.

Сообщение отредактировал Corner - Sep 27 2015, 20:07

[Acvarif]

Самый дубовый вариант, это поставить N блоков БПФ и коммутировать поотсчетно, подавая их на входы со сдвигом на отсчет. А у Altera и Xilinx используется БПФ со сдвигом не на отсчет, а на 1/2... 1/4 размера блока. По сути, имеется 2... 4 БПФ блока. В результате, на выходе почти отсутствуют разрывы фазы. Но такое преобразование годится не для всех видов модуляции. Иногда приходится делать перекрытие еще меньше 1/4.

По поводу поточного БПФ - все достаточно просто. Описано в соответствующих букварях. Небольшая заметка по этому поводу для ПЛИС http://acvarif.info/prvhdl/prvhdl25.html Такой метод довольно ресурсозатратный, но при наличии в ПЛИС аппаратных умножителей все работает неплохо.

[Krys]

Ничего подобного. При умножении надо указывать $signed иначе будет непредсказуемая ерунда, даже если указана знаковая переменная.

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