Перейти к содержанию
    

Реализация БПФ на ПЛИС

К сожалению, объяснить отсутствие переполнения только лишь увеличением разрядности недостаточно. Представьте, к примеру, что x_re = 32768, x_im = 32768, w_re = 1024 и w_im = 1024. В этом случае result_im = (x_re *w_im + x_im *w_re)/1024 = 65536 - однозначно переполнение... Здесь дело в свойствах БПФ. Если все реализовано правильно, то точки, поступающие на вход БПФ всегда находятся внутри единичной окружности на комплексной плоскости. Коеффициенты - это точки лежащие на краю единичной окружности ( w_re = cos(a), w_im = sin(a) ). Так что если w_re = 1024, то w_im неизбежно будет = 0. Поворачивающими их называют не случайно - при умножении на них точка всего лишь поворачивается на угол a. Она никогда не выйдет за пределы этой единичной окружности - это и есть главная причина отсутствия переполнения. Таким образом, если все сделано правильно, то случай x_re = x_im = 32768 исключен так же как и w_re = w_im = 1024.

 

Квантованные поворачивающие коэффициенты могут превышать единицу.

 

Например

 

abs(round(1024*exp(-i*2*pi/256)^1))-1024 = 0.3051

 

round(round(1024*exp(-i*2*pi/256)^1)*conj(round(1024*exp(-i*2*pi/256)^1))/1024) = 1025

 

Я так понимаю что у вас переполнения в таком случае не будет только из-за того что за счёт расширения входных данных до 17 бит образуется большой запас на переполнение?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Квантованные поворачивающие коэффициенты могут превышать единицу.

 

Значит плохо отквантовали :)

 

Можно, конечно, положиться и на запас в 1 бит, но лучше "хорошо" отквантовать коэффициенты.

 

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

 

Возьмем Ваш пример, только уберем '-' из под exp - просто для удбства, так угол будет около нуля. Если вещественную часть 1024*exp(i*2*pi/256) Вы округлили к 1024 (т.е. к 1.0), то чтобы не вылезти за единичную окружность относительно мнимой части у Вас уже не остается выбора - она должна быть равна 0, а не 25. Т.к. 2*pi/256 это угол в 1.40625 градуса, то выбрав 1024 - i*0 Вы имеете ошибку по углу в 1.40625 градуса и ошибку по модулю 0.

 

Округлим вещественную часть 1024*exp(i*2*pi/256) к 1023. В этом случае мнимая часть имеет некоторую свободу выбора значения :) Чтобы модуль коэффициента был = 1 мнимая часть д.б. 45.24378. Угол, соответственно, = 2.5323 градуса. Как видите, в этом случае, ошибка по углу меньше, чем в предыдущем 1.13 градуса.

 

Ну а теперь вещественную часть 1024*exp(i*2*pi/256) округлим к 1023, а мнимую к 25. Угол будет 1.39991, модуль 1023.3054. Таким образом, ошибка по углу 0.00634 т.е. меньше процента, а ошибка по амплитуде 0.6946 тоже меньше процента и никакого переполнения.

 

При выборе 1024 + i*25 Вы получаете угол 1.39854 и ошибку по углу 0.00771 (что больше, чем в предыдущем случае), модуль 1024.3051 и ошибку по модулю 0.3051 и, самое главное, переполнение! Причем данный вариант по ошибкам не имеет никаких особенных преимуществ перед предыдущим.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Ну а теперь вещественную часть 1024*exp(i*2*pi/256) округлим к 1023, а мнимую к 25. Угол будет 1.39991, модуль 1023.3054. Таким образом, ошибка по углу 0.00634 т.е. меньше процента, а ошибка по амплитуде 0.6946 тоже меньше процента и никакого переполнения.

 

Так это получается round(1023*exp(i*2*pi/256)^1) и

 

Если говорить очень кратко, то в силу того, что значения всех коэффициентов уменьшаются (пусть даже всего-то на 1/2048), коэффициенты перестают быть значениями e^(-j*2*pi*n/N) в соответствующих точках и теряют свое главное свойство - ортогональность.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Так это получается round(1023*exp(i*2*pi/256)^1) и

 

Ну и что?

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Ну и что?

 

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

 

Мне показалось что есть некоторое противоречие.

 

Сначала вы говорите что округлять к диапазону -2047...2047 плохо.

Затем говорите что переполнения не будет потому-что модуль коэффициента не превышает 1, и заостряете внимание на этом.

Я вам возражаю что многие квантованные поворачивающие коэффициенты будут превышать 1.

Вы приводите пример что будете квантовать по другому, фактически к диапазону -2047...2047.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Сначала вы говорите что округлять к диапазону -2047...2047 плохо.

 

Не округлять. Сначала мы выбирали диапазон целых чисел, которые будут соответствовать диапазону -1.0 ... +1.0. Есть точная формула X*W, которую надо реализовать в целочисленной арифметике. Чтобы это сделать мы Re(W) и Im(W), находящиеся в диапазоне -1.0 ... +1.0 заменяем целыми числами в диапазоне -К ... +К и формулу X*W заменяем полностью эквивалентной (X*(К*W)) / К. Причем (К*W) мы предвычисляем и записываем в память и при вычислениях просто берем нужное значение из памяти. Если Вы возьмете К не являющееся степенью 2, то Вы усложните себе реализацию. Деление на число, являющееся степенью 2 это сверх тривиальная операция, а вот деление на все остальные числа уже нет. Если Вы выберите К = 2047, равно как 2046 или 1999 Вам потребуется ставить делитель. Если же Вы решите из экономии и упрощения железа поделить не на К, а на число близкое К, но являющееся степенью двойки G, то Вы получите формулу (X*(К*W)) / G, которая уже не эквивалентна X*W.

 

Если Вы реализуете вычисление (X*(К*W)) / К, то с увеличением разрядности Вы будите стремиться к истинному значению X*W, но если Вы реализуете (X*(К*W)) / G, то можете считать хоть в арифметике с плавающей точкой и точностью представления long double - Вы никогда не получите значение X*W (частные вырожденные случаи не в счет).

 

Затем говорите что переполнения не будет потому-что модуль коэффициента не превышает 1, и заостряете внимание на этом.

Я вам возражаю что многие квантованные поворачивающие коэффициенты будут превышать 1.

 

Поскольку (К*W) предвычисляется, то тут не стоит лениться. Нужно не просто округлить Re и Im по отдельности, а найти такие целочисленные значения Re и Im при которых получается наименьшая ошибка по углу и модулю по сравнению с истинными значениями и нет выхода за пределы единичной окружности.

 

Вы приводите пример что будете квантовать по другому, фактически к диапазону -2047...2047.

 

Так это получается round(1023*exp(i*2*pi/256)^1) и

 

Это утверждение неверно. То, что значения Re и Im, вычисленные (точнее даже сказать найденные) для одного конкретного угла совпадают со значениями, вычесленными по формуле которая применялась бы если бы диапазон был выбран -1023 ... +1023 ни очем не говорит. Для другого ула такого совпадения может и не быть. Для угла 0 градусов, например, такого совпадения не будет - будет, соответственно 1024 + i*0 и 1023 + i*0. Кроме того, как я уже писал, просто вычислить и округлить по отдельности Re и Im не самое лучшее решение. И может оказаться, что если Вы для диапазона -1023 ... +1023 и данного угла именно найдете подходящие числа Re и Im, то они не совпадут со значениями, которые были найдены для диапазона -1024 ... +1024 и того же угла. (рекомендую это проверить в качестве упражнения).

 

Надеюсь, я понятно объяснил.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Это утверждение неверно. То, что значения Re и Im, вычисленные (точнее даже сказать найденные) для одного конкретного угла совпадают со значениями, вычесленными по формуле которая применялась бы если бы диапазон был выбран -1023 ... +1023 ни очем не говорит. Для другого ула такого совпадения может и не быть. Для угла 0 градусов, например, такого совпадения не будет - будет, соответственно 1024 + i*0 и 1023 + i*0. Кроме того, как я уже писал, просто вычислить и округлить по отдельности Re и Im не самое лучшее решение. И может оказаться, что если Вы для диапазона -1023 ... +1023 и данного угла именно найдете подходящие числа Re и Im, то они не совпадут со значениями, которые были найдены для диапазона -1024 ... +1024 и того же угла. (рекомендую это проверить в качестве упражнения).

 

Надеюсь, я понятно объяснил.

 

Вот вызывает сомнение что так произвольно можно округлять, многие точки пусть и не все совпадут с round(1023*exp(i*2*pi/256)^1). Шум квантования комплексной экспоненты будет явно больше чем для случая простого округления. Стоят ли эти ухищрения тех потерь в точности перобразования, может действительно просто добавить лишний разряд к данным?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот вызывает сомнение что так произвольно можно округлять, многие точки пусть и не все совпадут с round(1023*exp(i*2*pi/256)^1). Шум квантования комплексной экспоненты будет явно больше чем для случая простого округления. Стоят ли эти ухищрения тех потерь в точности перобразования, может действительно просто добавить лишний разряд к данным?

 

Это не ухищрения - это один из способов реализации. Между прочим, методов округления довольно много и этот вопрос здесь уже затрагивался. По какому именно пути пойти решать разработчику. Хотите, добавьте разряд, хотите округлите коэффициенты с дополнительным условием не выхода за пределы единичной окружности. Но вот чего точно не стоит делать, так это использовать выражение round(1023*exp(i*2*pi/256)^1) в случае, если Вы в качестве диапазона значений выбрали -1024 ... +1024 - лучше добавьте разряд и не мучайтесь :). Когда ZED сделает БПФ я предлагаю вернуться к этому вопросу и провести пару практических экспериментов.

 

 

 

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

 

Куда Вы подевались? Вы, вроде, собирались всерьез взяться за дело после защиты?

 

Вы читали мое сообщение о неверности вашего предположения об одинаковости адресации на последних этапах?

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

С интернетом были проблемы, а с работы файлы почему-то не отправлялись, в общем прикрепляю.

FFT_2048__16_07_09_.rar

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

С интернетом были проблемы, а с работы файлы почему-то не отправлялись, в общем прикрепляю.

 

Лучше, но пока еще неправильно. Из-за того, что на 6-ом этапе мы нереходим от 4-х т.б. к 2-х т.б. да еще и вычисляем 2-х т.б. по две за раз "ломается" алгоритм адресации. основная проблема в том, что записав данные на 5-ом этапе так как Вы это нарисовали Вы не можете прочитать их на 6-ом для вычисления двух бабочек одновременно. На 6-ом этапе на первой же итерации Вы попытаетесь прочитать 4 точки из банков 0, 1, 1, 3, на второй итерации из банков 2, 3, 0, 3 - как видите, всегда присутствует попытка прочитать две точки из одного и того же банка одновременно. Подумайте еще немного - нужно чуть-чуть поменять нумерацию банков при записи на 5-ом этапе.

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Вот, поправил!

 

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

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Я тут на досуге несколько поколдовал над генератором адресов для чтения, вот что получилось:

 

http://webfile.ru/3858995

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Еще раз извиняюсь за столь длительный перерыв.

 

Начнем с вопроса на засыпку. Откуда взялся коэффициент W1028? На последнем этапе все коэффициенты должны быть равны W0. Если Вы посмотрите предыдущие этапы, то в каждом блоке у самой первой бабочки все коэффициенты равны W0, а на самом последнем этапе каждая бабочка первая и единственная в блоке (просто в целях оптимизации и ускорения вычислений мы на последнем этапе их сразу по две обрабатываем и еще есть особенность расположения отсчетов в памяти – вот у нас и выходит, что на последнем этапе в одном "условном" блоке четыре 2-х точечные бабочки).

 

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

 

Я забыл важный нюанс. На этапах с 1 по 5 мы бабочки всегда вычисляли в нарисованном порядке. На последнем этапе нам уже не важен порядок вычисления бабочек. Правда, нам его придется учесть при перестановке гармоник когда мы будем вычитывать результаты из БПФ. Так вот, если продолжить формировать номера банков и адреса по привычному алгоритму, то получится, что мы просто будем вычислять бабочки не по порядку, как нарисовано, а немного в разнобой. Сначала вычислим 0-ю и 2-ю бабочки, затем 1-ю и 3-ю бабочки и т.д. Исправленную схему прилагаю. На всякий случай напомню, что однинаковым цветом залиты банки, из которых данные вычитываются/записываются одновременно. Это важно помнить, когда будете разбираться.

 

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

 

FFT_2048__31_08_09_.rar

Поделиться сообщением


Ссылка на сообщение
Поделиться на другие сайты

Присоединяйтесь к обсуждению

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

Гость
Ответить в этой теме...

×   Вставлено с форматированием.   Вставить как обычный текст

  Разрешено использовать не более 75 эмодзи.

×   Ваша ссылка была автоматически встроена.   Отображать как обычную ссылку

×   Ваш предыдущий контент был восстановлен.   Очистить редактор

×   Вы не можете вставлять изображения напрямую. Загружайте или вставляйте изображения по ссылке.

×
×
  • Создать...