Я ищу эффективное по времени и памяти решение для вычисления скользящего среднего в C. Мне нужно избегать деления, потому что я на PIC 16, у которого нет выделенного блока деления.
Сейчас я просто храню все значения в кольцевом буфере и просто сохраняю и обновляю сумму каждый раз, когда поступает новое значение. Это действительно эффективно, но, к сожалению, использует большую часть моей доступной памяти ...
Ответы:
Как уже упоминали другие, вы должны рассмотреть фильтр IIR (бесконечный импульсный отклик), а не фильтр FIR (конечный импульсный отклик), который вы используете сейчас. Это еще не все, но на первый взгляд КИХ-фильтры реализованы в виде явных сверток и БИХ-фильтров с уравнениями.
Конкретный БИХ-фильтр, который я часто использую в микроконтроллерах, - это однополюсный фильтр нижних частот. Это цифровой эквивалент простого аналогового фильтра RC. Для большинства приложений они будут иметь лучшие характеристики, чем фильтр, который вы используете. Большинство применений блочного фильтра, с которым я столкнулся, являются результатом того, что кто-то не обращает внимания на класс цифровой обработки сигналов, а не следствием необходимости их особых характеристик. Если вы просто хотите ослабить высокие частоты, которые, как вы знаете, являются шумом, лучше использовать однополюсный фильтр нижних частот. Лучший способ реализовать один из них в микроконтроллере обычно:
FILT <- FILT + FF (NEW - FILT)
ФИЛЬТ - это часть постоянного состояния. Это единственная постоянная переменная, необходимая для вычисления этого фильтра. NEW - это новое значение, которое фильтр обновляет в этой итерации. FF - фракция фильтра , которая регулирует «тяжесть» фильтра. Посмотрите на этот алгоритм и убедитесь, что при FF = 0 фильтр бесконечно тяжел, поскольку выходная мощность никогда не меняется. Для FF = 1 это действительно не фильтр вообще, поскольку выход просто следует за входом. Полезные значения находятся между ними. В небольших системах вы выбираете FF как 1/2 Nтак что умножение на FF может быть выполнено как сдвиг вправо на N битов. Например, FF может быть 1/16, а умножение на FF, следовательно, сдвиг вправо на 4 бита. В противном случае этот фильтр требует только одного вычитания и одного сложения, хотя числа обычно должны быть шире входного значения (подробнее о числовой точности в отдельном разделе ниже).
Я обычно снимаю показания АЦП значительно быстрее, чем они нужны, и применяю два из этих фильтров каскадно. Это цифровой эквивалент двух последовательных RC-фильтров, который ослабляется на 12 дБ / октаву выше частоты спада. Однако для A / D-показаний обычно более уместно смотреть на фильтр во временной области, учитывая его ответ шага. Это говорит о том, как быстро ваша система увидит изменения, когда изменяется измеряемая вами вещь.
Чтобы облегчить разработку этих фильтров (что означает только выбор FF и определение количества из них для каскадирования), я использую свою программу FILTBITS. Вы указываете число битов сдвига для каждого FF в каскадной серии фильтров, и оно вычисляет ответ шага и другие значения. На самом деле я обычно запускаю это через мой скрипт-обертку PLOTFILT. Это запускает FILTBITS, который создает файл CSV, а затем создает файл CSV. Например, вот результат «PLOTFILT 4 4»:
Два параметра PLOTFILT означают, что будут два каскадных фильтра описанного выше типа. Значения 4 указывают количество битов сдвига для реализации умножения на FF. Таким образом, в этом случае два значения FF составляют 1/16.
Красный след - это реакция на единицу шага, и это главное, на что нужно обратить внимание. Например, это говорит о том, что если входные данные изменяются мгновенно, выходной сигнал объединенного фильтра будет доведен до 90% от нового значения за 60 итераций. Если вам нужно 95% времени установления, тогда вам придется подождать около 73 итераций, а для 50% времени установления только 26 итераций.
Зеленая кривая показывает выходной сигнал от одного пика полной амплитуды. Это дает вам некоторое представление о подавлении случайного шума. Похоже, что ни одна из выборок не приведет к более чем 2,5% -ному изменению выхода.
Синий след должен дать субъективное ощущение того, что этот фильтр делает с белым шумом. Это не строгий тест, поскольку нет никакой гарантии, что именно содержимое было случайных чисел, выбранных в качестве входного белого шума для этого прогона PLOTFILT. Это только для того, чтобы дать вам грубое ощущение того, насколько оно будет раздавлено и насколько оно гладко.
PLOTFILT, возможно FILTBITS, и много других полезных вещей, особенно для разработки прошивки PIC, доступны в выпуске программного обеспечения PIC Development Tools на моей странице загрузки ПО .
Добавлено о числовой точности
Из комментариев и теперь нового ответа я вижу, что есть интерес к обсуждению количества битов, необходимых для реализации этого фильтра. Обратите внимание, что умножение на FF создаст новые биты Log 2 (FF) ниже двоичной точки. В небольших системах FF обычно выбирается равной 1/2 N, так что это умножение фактически реализуется путем сдвига вправо N битов.
Поэтому FILT обычно является целым числом с фиксированной точкой. Обратите внимание, что это не меняет никакой математики с точки зрения процессора. Например, если вы фильтруете 10-битные аналого-цифровые показания и N = 4 (FF = 1/16), то вам нужно на 4 дробных бита ниже 10-битных целочисленных аналого-цифровых показаний. Один из большинства процессоров, вы будете делать 16-битные целочисленные операции из-за 10-битного A / D чтения. В этом случае вы все равно можете выполнять точно такие же операции с 16-битными целыми числами, но начать с показаний АЦП влево, смещенных на 4 бита. Процессор не знает разницы и не нуждается в этом. Выполнение математических вычислений для целых 16-битных целых чисел работает независимо от того, считаете ли вы их 12,4-целыми или истинными 16-битными целыми числами (16,0-фиксированной точкой).
В общем, вам нужно добавить N битов на каждом полюсе фильтра, если вы не хотите добавлять шум из-за числового представления. В приведенном выше примере второй фильтр из двух должен иметь 10 + 4 + 4 = 18 бит, чтобы не потерять информацию. На практике на 8-битной машине это означает, что вы будете использовать 24-битные значения. Технически только второй полюс из двух будет нуждаться в более широком значении, но для простоты прошивки я обычно использую одинаковое представление и, следовательно, один и тот же код для всех полюсов фильтра.
Обычно я пишу подпрограмму или макрос для выполнения одной операции полюса фильтра, а затем применяю это к каждому полюсу. Выбор подпрограммы или макроса зависит от того, являются ли циклы или память программы более важными в этом конкретном проекте. В любом случае, я использую некоторое состояние нуля, чтобы передать NEW в подпрограмму / макрос, который обновляет FILT, но также загружает его в то же состояние, в котором находился NEW. Это позволяет легко применять несколько полюсов, так как обновленный FILT одного полюса НОВОЕ из следующего. При выполнении подпрограммы полезно указывать указатель на FILT при входе, который обновляется сразу после FILT при выходе. Таким образом, подпрограмма автоматически работает с последовательными фильтрами в памяти, если она вызывается несколько раз. С макросом вам не нужен указатель, так как вы передаете адрес для работы на каждой итерации.
Примеры кода
Вот пример макроса, как описано выше для PIC 18:
А вот аналогичный макрос для PIC 24 или dsPIC 30 или 33:
Оба эти примера реализованы как макросы с использованием моего препроцессора PIC на ассемблере , который более эффективен, чем любое из встроенных средств макросов.
источник
Если вы можете жить с ограничением степени двух чисел элементов в среднем (то есть 2,4,8,16,32 и т. Д.), То разделение можно легко и эффективно сделать на низкоэффективном микро без выделенного разделения, потому что оно может быть сделано как немного сдвиг. Каждое смещение вправо - это одна степень двух, например:
или
и т.п.
источник
Там является ответ на истинном фильтр скользящего среднего ( так называемый «вагон фильтра») с меньшими требованиями к памяти, если вы не возражаете субдискретизации. Он называется каскадным фильтром гребенки интегратора (CIC). Идея состоит в том, что у вас есть интегратор, с которым вы берете различия в течение определенного периода времени, а ключевое устройство, сохраняющее память, заключается в том, что при понижающей дискретизации вам не нужно хранить все значения интегратора. Это может быть реализовано с использованием следующего псевдокода:
Ваша эффективная длина скользящей средней равна,
decimationFactor*statesize
но вам нужно только держатьstatesize
образцы. Очевидно , что вы можете получить более высокую производительность , если вашиstatesize
иdecimationFactor
являются степенями 2, так что деление и остаточные операторы заменяются сдвигами и маски-ANDS.Постскриптум: Я согласен с Олином, что вы всегда должны рассматривать простые БИХ-фильтры перед фильтром скользящего среднего. Если вам не нужны значения частоты нулевого фильтра, то 1-полюсный или 2-полюсный фильтр нижних частот, вероятно, будет работать нормально.
С другой стороны, если вы фильтруете для целей децимации (беря вход с высокой частотой дискретизации и усредняя его для использования процессом с низкой скоростью), тогда фильтр CIC может быть именно тем, что вы ищете. (особенно если вы можете использовать Statesize = 1 и вообще избежать кольцевого буфера, используя только одно предыдущее значение интегратора)
источник
Существует некоторый углубленный анализ математики, основанной на использовании БИХ-фильтра первого порядка, который Олин Латроп уже описал при цифровой обработке сигналов. обмене стеками (включает много красивых картинок). Уравнение для этого фильтра БИХ:
у [п] = αx [п] + (1-α) у [п-1]
Это может быть реализовано с использованием только целых чисел и без деления с использованием следующего кода (может потребоваться некоторая отладка, поскольку я печатал из памяти.)
Этот фильтр приближает скользящее среднее последних K выборок, устанавливая значение альфа в 1 / K. Делайте это в предыдущем коде,
#define
INGBITS
к LOG2 (К), то есть для K = 16 набораBITS
до 4, при К = 4 множестваBITS
до 2, и т.д.(Я проверю код, указанный здесь, как только получу изменение, и при необходимости отредактирую этот ответ.)
источник
Вот однополюсный фильтр нижних частот (скользящее среднее с частотой среза = частота среза). Очень просто, очень быстро, прекрасно работает, и почти нет перегрузок памяти.
Примечание. Все переменные имеют область действия, выходящую за пределы функции фильтра, кроме передаваемых в newInput.
Примечание. Это одноступенчатый фильтр. Несколько ступеней могут быть соединены каскадом для увеличения резкости фильтра. Если вы используете более одного этапа, вам придется настроить DecayFactor (в зависимости от частоты среза) для компенсации.
И, очевидно, все, что вам нужно, это две строки, расположенные где угодно, им не нужна их собственная функция. Этот фильтр имеет время разгона до того, как скользящее среднее представляет значение входного сигнала. Если вам нужно обойти это время, вы можете просто инициализировать MovingAverage первым значением newInput вместо 0 и надеяться, что первый newInput не является выбросом.
(CutoffFrequency / SampleRate) имеет диапазон от 0 до 0,5. DecayFactor - это значение от 0 до 1, обычно близкое к 1.
Поплавки одинарной точности достаточно хороши для большинства вещей, я просто предпочитаю двойные. Если вам нужно придерживаться целых чисел, вы можете преобразовать DecayFactor и Amplitude Factor в дробные целые числа, в которых числитель хранится как целое число, а знаменатель представляет собой целую степень 2 (так что вы можете сдвигать бит вправо как знаменатель, а не деление во время цикла фильтра). Например, если DecayFactor = 0,99 и вы хотите использовать целые числа, вы можете установить DecayFactor = 0,99 * 65536 = 64881. И затем в любое время, когда вы умножаете на DecayFactor в цикле фильтра, просто сдвигаете результат >> 16.
Для получения дополнительной информации об этом, отличная книга онлайн, глава 19 о рекурсивных фильтрах: http://www.dspguide.com/ch19.htm
PS Для парадигмы Скользящее среднее, другой подход к настройке DecayFactor и AmplitudeFactor, который может быть более соответствующим вашим потребностям, скажем, вы хотите, чтобы предыдущие, около 6 элементов были усреднены вместе, делая это дискретно, вы добавили бы 6 элементов и поделили бы на 6, так что вы можете установить AmplitudeFactor на 1/6, а DecayFactor на (1.0 - AmplitudeFactor).
источник
Вы можете аппроксимировать скользящее среднее для некоторых приложений с помощью простого фильтра БИХ.
вес - значение 0..255, высокие значения = более короткая шкала времени для аваражирования
Значение = (новое значение * вес + значение * (256-вес)) / 256
Чтобы избежать ошибок округления, значением обычно будет long, из которых вы используете только байты старшего порядка в качестве «фактического» значения.
источник
Все остальные подробно прокомментировали полезность IIR против FIR и деление на степень два. Я просто хотел бы дать некоторые детали реализации. Ниже хорошо работает на небольших микроконтроллерах без FPU. Здесь нет умножения, и если вы держите N в степени два, все деление будет сдвигом битов за один цикл.
Базовый кольцевой буфер FIR: сохраните текущий буфер последних N значений и текущий SUM всех значений в буфере. Каждый раз, когда приходит новый образец, вычтите самое старое значение в буфере из SUM, замените его новым образцом, добавьте новый образец в SUM и выведите SUM / N.
Модифицированный кольцевой буфер IIR: сохраняйте текущую сумму последних N значений. Каждый раз, когда приходит новый образец, SUM - = SUM / N, добавьте новый образец и выведите SUM / N.
источник
Как сказал mikeselectricstuff , если вам действительно нужно уменьшить свои потребности в памяти, и вы не возражаете против того, чтобы ваша импульсная характеристика была экспоненциальной (вместо прямоугольного импульса), я бы выбрал экспоненциальную скользящую среднюю фильтр . Я использую их широко. С этим типом фильтра вам не нужен буфер. Вам не нужно хранить N прошлых образцов. Только один. Таким образом, ваши требования к памяти будут сокращены с коэффициентом N.
Кроме того, вам не нужно никакого разделения для этого. Только умножения. Если у вас есть доступ к арифметике с плавающей точкой, используйте умножения с плавающей точкой. В противном случае делайте целочисленные умножения и сдвиги вправо. Однако мы находимся в 2012 году, и я бы порекомендовал вам использовать компиляторы (и MCU), которые позволяют работать с числами с плавающей запятой.
Помимо большей эффективности использования памяти и ускорения (вам не нужно обновлять элементы в любом циклическом буфере), я бы сказал, что это также более естественно , потому что экспоненциальный импульсный отклик лучше соответствует поведению природы в большинстве случаев.
источник
Одна из проблем с БИХ-фильтром, которого почти коснулись @olin и @supercat, но, по-видимому, не учитывают другие, заключается в том, что округление вниз вносит некоторую неточность (и, возможно, смещение / усечение): предполагая, что N является степенью двойки, и только целочисленная арифметика Сдвиг вправо систематически исключает младшие биты нового образца. Это означает, что как долго сериал может быть, средний никогда не примет это во внимание.
Например, предположим, что ряд медленно уменьшается (8,8,8, ..., 8,7,7,7, ... 7,6,6,) и предположим, что среднее значение действительно 8 в начале. Первый образец «7» принесет среднее значение до 7, независимо от силы фильтра. Только для одного образца. Та же история для 6 и т. Д. Теперь подумайте об обратном: серия идет вверх. Среднее значение будет оставаться на 7 всегда, пока выборка не станет достаточно большой, чтобы ее можно было изменить.
Конечно, вы можете исправить «смещение», добавив 1/2 ^ N / 2, но это не решит проблему точности: в этом случае убывающая серия будет оставаться вечно на уровне 8, пока выборка не будет 8-1 / 2 ^ (N / 2). Например, для N = 4 любая выборка выше нуля будет сохранять среднее значение без изменений.
Я полагаю, что решение для этого подразумевало бы хранение аккумулятора потерянных младших битов. Но я не сделал это достаточно далеко, чтобы подготовить код, и я не уверен, что это не повредит мощности IIR в некоторых других случаях серии (например, будет ли 7,9,7,9 в среднем до 8 тогда) ,
@ Олин, твой двухступенчатый каскад тоже нуждается в объяснении. Вы имеете в виду хранение двух средних значений с результатом первого, поданного во вторую в каждой итерации? В чем выгода этого?
источник