Хабр Курсы для всех
РЕКЛАМА
Большая витрина: от крупнейших школ до частных авторов. Сравнивайте по цене, длительности, формату и выбирайте самый подходящий курс!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 29
Как мне кажется тут самое тонкое место при целочисленном вычислении — выбор разрядности. Можно конечно делать усечение разрядности сверху или снизу или даже усечение с насыщением результата, но всегда есть некая вероятность, что при некоторых сигналах на некоторых этапах произойдет переполнение, а мы про это и не узнаем. Так это или нет?
Не совсем так. В алгоритме БПФ нет аккумуляторов, только сумматоры — насыщения не происходит. С другой стороны: алгоритм БПФ на каждой бабочке требует увеличить разрядность данных на 1. Это железное правило для Radix-2. Соответственно, если соблюсти это требование, то разрядность на выходе увеличится на Nбабочек, и переполнения не произойдет при любой комбинации входных воздействий.
В моем проекте разрядность на входе — конфигурируемая, на выходе — зависит от количества бабочек и входной разрядности, то есть не усекается до исходной, => переполнения нет.
В моем проекте разрядность на входе — конфигурируемая, на выходе — зависит от количества бабочек и входной разрядности, то есть не усекается до исходной, => переполнения нет.
Видимо я чего-то недопонял. А как же умножение? Там же в бабочке должно быть умножение?
В бабочке данные разрядностью N умножаются на гармонический сигнал, который нормирован к 1. Поэтому результат умножения можно смело усекать снизу на разрядность M-бит гармонического сигнала.
Кроме того, если в гармоническом сигнале не используется максимально отрицательное число (wierd number в 2's complement представлении), то разрядность сверху тоже можно усекать на 1 бит.
Итоговое поле данных в разрядной сетке: [N+M-2: M-1] ( N+M-2 — это MSB, M-1 — это LSB результата умножения).
Кроме того, если в гармоническом сигнале не используется максимально отрицательное число (wierd number в 2's complement представлении), то разрядность сверху тоже можно усекать на 1 бит.
Итоговое поле данных в разрядной сетке: [N+M-2: M-1] ( N+M-2 — это MSB, M-1 — это LSB результата умножения).
Хм… вот уж не знал. Надо подумать, чего-то как-то подозрительно.
На счет смело усекать — все-таки не совсем. Вы теряете точность, увеличивая в конечном итоге уровень шума. А дальше все зависит от ваших потребностей.
Абсолютно верно. Поэтому я без ущерба для объема занимаемых ресурсов ПЛИС для комплексного умножителя после умножения не сразу усекаю разрядность, а результаты складываю/вычитаю в 48-битной сетке, благо ресурсы DSP48 это позволяют. А уже потом делаю округление до нужного числа бит на выходе бабочки (как правило < 48).
Допустим у нас БПФ длиной N = 2^n. Тогда есть вариант на каждом «проходе» БПФ (которых n) делить результат на 2, тогда разрядность вообще не возрастает. Одновременно это дает результат БПФ, деленный на N, что более осмысленно с сигнальной точки зрения — R[0] равен постоянной составляющей сигнала в тех же единицах, R[1] + R[N — 1] = 2*R1 равно амплитуде первой гармоники, R[2] + R[N — 2] = 2*R2 равно амплитуде второй гармоники и т.д.
Думаю, что внутри PLD реализация деления на два (сдвиг) вообще не требует временных ресурсов.
Думаю, что внутри PLD реализация деления на два (сдвиг) вообще не требует временных ресурсов.
Не все так просто. По определению БПФ — это интегральное преобразование (из свойств ПФ), следовательно результат накапливается на каждой бабочке. При усечении на каждой стадии — мы теряем точность результата из-за эффектов квантования, и в задачах, где это важно (например: радиолокация) — вариант с усечением не сработает. Не зря БПФ без усечения называется full-precision. Но схемы с усечением имеют право на жизнь и реализованы в ядрах Xilinx / Altera. Там даже сдвиг вправо не требуется, можно просто на выходе бабочки сделать «truncate LSB».
Не поленюсь и добавлю в ближайшее время в исходники для SCALED TRUNCATED / ROUNDING варианты.
Не поленюсь и добавлю в ближайшее время в исходники для SCALED TRUNCATED / ROUNDING варианты.
Мы все равно теряем точность на каждой стадии (кроме первой), т.к. там есть умножение на приблизительное значение корня из единицы, после чего результат умножается на приблизительное значение на следующей стадии и т.д. Т.е. ошибка накапливается.
И еще момент. Допустим, у нас есть 8-битное входное значение (считаем его изменяющимся от -1 до 1), 16-битная арифметика и нам надо сделать БПФ 1024 значений. Максимальное значение результата в этом случае — 1024 (для 0-й и 512-й гармоники, для остальных не более 2048/pi = 651.9), т.е. для представления целой части результата нам надо 12 бит (знак и 11 бит, чтобы представить 1024). Это можно сократить на 1 бит, если принять меры, чтобы результат не доходил до 1024 — тогда надо 11 бит (знак и 10 бит). Это оставляет всего 16 — 11 = 5 бит на дробную часть. Т.е. входной сигнал нам придется сократить до 6 бит (1 бит знак и 5 бит значение, не превышающее единицы), т.е. сразу откинуть 2 бита. В то же время, если делать деление на 2 на каждом проходе, мы можем использовать все 8 бит (и даже 12 бит, если сигнал такой) входного сигнала.
И еще момент. Допустим, у нас есть 8-битное входное значение (считаем его изменяющимся от -1 до 1), 16-битная арифметика и нам надо сделать БПФ 1024 значений. Максимальное значение результата в этом случае — 1024 (для 0-й и 512-й гармоники, для остальных не более 2048/pi = 651.9), т.е. для представления целой части результата нам надо 12 бит (знак и 11 бит, чтобы представить 1024). Это можно сократить на 1 бит, если принять меры, чтобы результат не доходил до 1024 — тогда надо 11 бит (знак и 10 бит). Это оставляет всего 16 — 11 = 5 бит на дробную часть. Т.е. входной сигнал нам придется сократить до 6 бит (1 бит знак и 5 бит значение, не превышающее единицы), т.е. сразу откинуть 2 бита. В то же время, если делать деление на 2 на каждом проходе, мы можем использовать все 8 бит (и даже 12 бит, если сигнал такой) входного сигнала.
Если бы все было так, то вариантов full-precision и floating-point вообще бы не появилось. Из теории известно, что при делении входого сигнала уменьшается отношение сигнал-шум, а это значит, что некоторые сигналы просто нереально вытянуть из-под шумов, если производить округление или усечение. В качестве доказательства привел сравнение в реальном железе прохоождение синусоидального сигнала через БПФ на 1024 точки — UNSCALED / SCALED. При плохом отношении сигнал-шум вариант UNSCALED смог «вытянуть» гармонику, в то время как SCALED — не смог (см. update к статье). Под SCALED я понимаю вариант, при котором разрядность на выходе бабочки просто усекается на LSB, без округления.
А все так и есть. Провел тесты — делаю FFT 1024 значений (прямоугольный сигнал от -1 до 1) на 16-битной арифметике, затем делаю обратное преобразование с полной точностью double и сравниваю полученный сигнал с исходным, нахожу максимальное отклонение. Получаю (корни из единицы в обоих тестах были представлены абсолютно одинаково — S1.14):
1. Формат S0.15 (знак, 0 бит целая часть, 15 бит дробная часть), деление на 2 на каждом проходе: максимальное отклонение 0.004349, т.е. 0.4%.
2. Формат S10.5 (знак, 10 бит целая часть, 5 бит дробная часть), деление на 1024 только в обратном преобразовании: максимальное отклонение 0.075172, т.е. 7.5%.
Видно, что вариант без деления на 2 гораздо (в 20 раз) хуже по точности варианта с делением на 2. Я бы даже сказал, что вариант без деления имеет вообще неприемлемую точность при 16-битной арифметике.
И самое забавное то, что та самая плавающая точка, о которой вы говорите, как раз таки осуществляет это деление на 2 на каждом этапе.
1. Формат S0.15 (знак, 0 бит целая часть, 15 бит дробная часть), деление на 2 на каждом проходе: максимальное отклонение 0.004349, т.е. 0.4%.
2. Формат S10.5 (знак, 10 бит целая часть, 5 бит дробная часть), деление на 1024 только в обратном преобразовании: максимальное отклонение 0.075172, т.е. 7.5%.
Видно, что вариант без деления на 2 гораздо (в 20 раз) хуже по точности варианта с делением на 2. Я бы даже сказал, что вариант без деления имеет вообще неприемлемую точность при 16-битной арифметике.
И самое забавное то, что та самая плавающая точка, о которой вы говорите, как раз таки осуществляет это деление на 2 на каждом этапе.
UPD: да, конечно, имеется в виду, что она осуществляет деление на 2, если при сложении возникает переполнение.
Атас, аще. Хочу поинтересоваться, почему вы используете LabView, а не какой-нибудь Verilog?
Отличная статья!
Ещё у отдельных самописных модулей есть плюсы — универсальность при перетаскивании проектов с кристалла на кристалл. IP Core имеют свойство обновляться и не только при изменнии чипа: иногда перетаскиваешь проект на САПР более высокой версии и приходится внимательно смотреть что и как обновилось. Если же у тебя всё в коде, то это обычно не представляет никаких проблем, если он продуманно и корректно написан. Поэтому обычно у каждого разработчика со стажем есть своя захомяченная библиотечка. За опубликованный модуль — отдельное спасибо.
Ещё у отдельных самописных модулей есть плюсы — универсальность при перетаскивании проектов с кристалла на кристалл. IP Core имеют свойство обновляться и не только при изменнии чипа: иногда перетаскиваешь проект на САПР более высокой версии и приходится внимательно смотреть что и как обновилось. Если же у тебя всё в коде, то это обычно не представляет никаких проблем, если он продуманно и корректно написан. Поэтому обычно у каждого разработчика со стажем есть своя захомяченная библиотечка. За опубликованный модуль — отдельное спасибо.
Не уверен, буду ли я заниматься цифровой обработкой на ПЛИС в будущем, но если я останусь в рядах разработчиков и радиоинженеров, то вскоре вы увидите и другие интересные проекты с открытым исходным кодом!
Вот эта вот фраза несколько пугает. Почему
если я останусь в рядах разработчиков и радиоинженеров?
Планирую сменить сферу деятельности подальше от железа, но поживем — увидим.
Если не секрет, то насколько подальше и почему вы планируете покинуть FPGA?
В FPGA с определенного уровня отсутствует гибкость по выбору предложений по работе, и вилка зарплат существенно ниже, в сравнении теми же программистами в web.
В FPGA с определенного уровня отсутствует гибкость по выбору предложений по работе, и вилка зарплат существенно ниже, в сравнении теми же программистами в web.
Как не прискорбно, но такие мысли в последнее время посещают и меня…
Здравствуйте! Есть вопрос по FPGA. Есть ли способы провести reverse engineering платы, чтобы узнать, какая прошивка на нее была загружена или, например, какое значение лежит в том или ином регистре. Был бы очень благодарен за информацию!
P.S. Читал про side channel эффекты, хочется узнать, есть ли способ считать информацию напрямую.
P.S. Читал про side channel эффекты, хочется узнать, есть ли способ считать информацию напрямую.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Реализация целочисленного БПФ на ПЛИС