Comments 21
частотой квантования
частотой дискретизации (?)
Да кажется вполне термин. Есть еще шум квантования
Ну тогда получается 2 вида квантования - по времени (что скорее образно и не вполне корректно) и по уровню, когда сигнал принимает значение соответствующее разрядной сетки (не обязательно линейной с шагом 2^-N, например для float с мантиссой и экспонентой она нелинейная, зато большой динамический диапазон).
Согласен, возможен вариант частота выборки, частота следования отсчётов, частота семплирования. Частота квантования скорее образно, исходя из рисунка.
Это просто классическое экспоненциальное скользящее среднее (EMA) + один нуль.
Этот нуль - костыль. Сдвиги все равно не дадут точно сделать нужную полосу.
Я применяю медианный фильтр на 3 отсчета перед EMA . Гораздо лучше сглаживает выбросы.
Этот нуль необходим для создания большой постоянной времени, например, для устранения постоянной составляющей. Данный метод имеет дискретный набор АЧХ/ФЧХ характерных для заданной степени двойки. Можно также рассчитать значение частоты среза по уровню, но там появятся арксинусы-косинусы из-за дискретной ПФ. Точное значение можно получить из скрипта выше в Maxima, путём FcabA^2;solve(%=L^2,f); после соответствующего выражения. Также, это не только ФНЧ но и ФВЧ (0 на f=0 и 1 на частоте Найквиста), режекторный/полосовой и более высокого порядка с эффективным вычислением на основе предложенного метода.
Разве сдвиги это не умножение/деление на степени двойки?
Нет, сдвиги считаются в разы быстрее умножения, и тем более деления.
Хотя бывает так что MUL на некоторых архитектурах, особенно на DSP считается даже быстрее, за такт, чем побитовые операции ASR-ASL, особенно если операнды потоком выбираются из памяти с автоматическим пост-инкрементом указателя. Другое дело мелкие микроконтроллеры и ПЛИС, где аппаратный умножитель - это целый блок по уровню интеграции не уступающий регистровому файлу и логике, и там где его нет конечно же будет существенный выигрыш, тем более что контроллеры наоборот, более заточены на двоичку чем на сигналку.
В статье русским по белому и поясняеться, что алгоритм использует только частный случай умножения - умножение на степень двойки.
"открыть плоттер в среде "Ардуино" создания скетчей." - звучит как перевод ПРОМТ из 90х. Разве не лучше было бы написать: "открыть плоттер в Arduino IDE"?
Хм, дежавю? https://habr.com/ru/articles/324522/ - тут тоже открыли технологии древних, когда пользовались сдвигами вместо умножений...
Частотные характеристики лучше рисовать в логарифмическом массштабе.
Примерно тоже самое, но только с фиксированной частотной характеристикой без параметра + использование временных переменных состояния. Скорее всего это тоже самое, для 2-го порядка. В этом случае используется 3 точки, например на 0й частоте, Найквиста и какая-либо выделенная частота, при которой коэффициенты кратны степени двойки. Например, мнимая часть в этой точке равна нулю (полосовой) или обе одновременно (режекторный). Как раз там возникают те самые "рысканья", для первого порядка - статическая ошибка как сказано в статье. Однако, можно последовательно соединить ФНЧ и ФВЧ чтобы получить полосовой в некоторой мере, и тут уже возможны варианты. Ну а далее схема Горнера и прочие алгебраические преобразования чтобы вынести необходимые степени двойки за скобки и использовать переменные состояния.
Есть ещё более "хитрые" способы, заключающиеся в применении метода Ньютона-Рафсона, у того же Техаса, который для C2000 с фиксированной запятой реализует деление с уточнением по таблице, вычисление синусов-косинусов по таблице с интерполяцией рядом Тейлора в окрестности заданной табличной точки (описание вроде в sprc993), ну и конечно же CORDIC. Логарифмический масштаб скорее для количественного описания, здесь же отображение качественных характеристик, не имеющих промежуточных значений, да и на частоте Найквиста значение точно равняется нулю, там логарифм убегает в -∞.
Без умножений.- это CIC фильтры http://www.dsplib.ru/content/cic/cic.html
А заменять умножения сдвигами в большинстве случаев довольно сомнительная "оптимизация", которую компилятор и сам сделает https://godbolt.org/z/s8KcrjK3E
В данном случае речь идёт о расчёте коэффициентов фильтра, равным степени двойки, при которых он заведомо будет упрощён по количеству операций. Конечно же если компилятор достаточно "умный", то в коде выше можно вместо >>1 написать /2 или возможно даже int(a*0.5) и он оптимизирует, но лучше не рисковать и указать явную операцию << или >>, она практически выглядит как intrinsic-инструкция в коде, в этом случае язык С выглядит как "аппаратно-независимый ассемблер". Плюс в указанном методе без изменения структуры фильтра можно дискретным образом изменять полосу пропускания. Хотя, это если имеется инструкция ASR/ASL на заданное количество бит (Barrel shifter), в архитектуре AVR, например, сдвиг происходит только на один бит без параметра. CIC фильтр также требует большой динамический диапазон для вычислений вида ∞-∞ из-за наличия каскада интеграторов, в предлагаемом варианте этот диапазон ограничен лишь старшим разрядом.
Там где barrel shifter есть, это обычно подразумевает совсем не 8ми битную разрядность и умножение там будет не медленнее сдвига, а скорее всего даже быстрее так как будет выполнено одной иструкцией с накоплением.
Впрочем и на AVR уножение (деление на константу) 16х16 будет каких-нибудь ~15 тактов, вместо 8 для x>>4. Да, там есть инструкция swap, но мы же не можем рисковать и надеятся на компилятор. А с учётом отсутсвия аппартных циклов и дополнительных шин для складывания/доставания данных из памяти (в отличии от нормальных dsp под такие задачи заточенных) общее быстродействие цикла for(;;i++) y[i]=y[i-1]+(x[i]-y[i-1])>>N; станет процентов на 10 быстрее на AVR, и чуть-чуть медленнее на нормальных архитектурах, ну и ещё и ценой ограничения коэффициентов только степенями 2. Поэтому "оптимизация" довольно сомнительная.
Да действительно там есть инструкция MUL которая позволяет делать 16*16=16 за 9 тактов плюс ret и 16*16=32 за 17 тактов. Тут же говорится о том чтобы вообще не использовать данную инструкцию, например на каком-нибудь Attiny где умножение занимает сотни библиотечных тактов ну или знаменитый Z80. Интерес в том числе представляет в принципе подобного рода оптимизация на основе фиксированных значений коэффициентов, включая, например, возможную реализацию "гладкой" функции активации для нейрона с оптимальной для градиентного метода (производная есть сама функция) формой что-то вроде 1/(1+2^-x) - логистическая, с 2 вместо экспоненты, тогда алгоритм будет заключаться в сдвиге на заданное количество разрядов согласно старшей единице в операнде.
Можно изначально при расчёте фильтра искать коэффициенты фильтра в Signed Digit представлении, сложность в том, что там несколько вариантов представления одного числа может быть, тогда нужно ещё искать минимальную форму. Тогда все коэффициенты фильтра будут из сложений, вычитаний и сдвигов.
Да, также можно дополнить обработкой факторизацией и схемой Горнера общей формулы самого фильтра как суммы взвешенных отсчётов, в этом случае оптимизация может проводится уже в пространстве состояний по отсчётам (z⁻¹), например, сохраняя промежуточные значения в регистрах/памяти и далее уже применяя арифметические сдвиги в нужных местах. Ещё вдобавок решив проблему динамического диапазона и нормировки по ходу вычислений, что-то вроде (x₋₁+x₋₂)/2 = (2x₋₁+x₋₂)/2-x₋₁/2, чтобы не потерять разряды, особенно для полосовых фильтров и прочих высокодобротных штуковин.
Сам таким БИХ-фильтром пользуюсь уже давно. Код выходит очень простой, и с помощью макросов несложно посчитать нужный коэффициент. Главное, не забывать, что аккумулятор должен быть с разрядностью на N больше, чем исходные данные.
Правда, если после фильтрации требуется понижение частоты дискретизации, то особых преимуществ перед КИХ-фильтром типа "скользящее среднее" этот способ не имеет - вычислений примерно столько же требуется.
Цифровой фильтр без умножения