Комментарии 45
Ещё одна очевидная проблема рекурсивного фильтра — малейшее однократное повреждение данных приводит к перманентному искажению результата, а оно в реальных системах может произойти по разным причинам — космическое излучение, несанкционированная запись в область памяти массива со значениями и т.д. поэтому для надёжности иногда приходится пересчитывать по полной весь массив. Или должна быть какая-то обратная связь которая устранит расхождение.
Селяви, как говорят французы
В рекурсивном варианте некоторое отклоение d на шаге k даст вклад в выход фильтра +d/N, но потом на шаге k+N это же отклонение вычтется.
В системах, у которых есть эти самые «малейшие однократные повреждения данных», проблем куда больше.
Потому что вероятность, что слетит стек, какой-нибудь индекс или прочий указатель ровно такая же.
Нет, я знаю про ватчдог, но это есть костыль — система перед его срабатыванием имела полное право делать чёрт-знает-что.
Потому что вероятность, что слетит стек, какой-нибудь индекс или прочий указатель ровно такая же.
Нет, я знаю про ватчдог, но это есть костыль — система перед его срабатыванием имела полное право делать чёрт-знает-что.
А какие еще есть костыли для систем с возможным повреждениями данных?
Из программных средств для контроля целостности стека вызовов можно каждой функции передавать параметр CalledById и внутри функции его проверять. Желательно иметь поддержку такой фичи на уровне компилятора.
Из программных средств для контроля целостности стека вызовов можно каждой функции передавать параметр CalledById и внутри функции его проверять. Желательно иметь поддержку такой фичи на уровне компилятора.
Вариант, в котором можно быть уверенным — дублировать (троировать) системы управления.
А «иногда пересчитывать» этот несчастный фильтр — это из анекдота о поиске кошелька под фонарём.
А «иногда пересчитывать» этот несчастный фильтр — это из анекдота о поиске кошелька под фонарём.
Троирование системы управления не поможет, т.к. программа на них будет одна и программная ошибка сделает плохо на всех экземплярах. Она в любом случае сделает плохо, даже если всё работать будет идеально — как только используешь арифметику с плавающей запятой — будет накапливаться неустранимая ошибка из-за неизбежного округления.
У меня тут вопрос возник. У Вас какая проблема?
Космические излучения? Дублируйте. Иначе за то время, что пройдёт между прилётом частицы и очередным пересчётом фильтра Ваш космолёт включит самый-главный-двигатель и улетит чёрт знает куда.
Программные ошибки? Пересчитывать каждые 5 секунд одни и те же данные с одной и той же ошибкой… Не лучшее решение.
Накопление ошибки во флоатах? Всё просто — не делайте так никогда. Разговор не с этого начался.
Или просто поговорить надо на отвлечённые темы?.. Тогда, пожалуйста, не ко мне.
Космические излучения? Дублируйте. Иначе за то время, что пройдёт между прилётом частицы и очередным пересчётом фильтра Ваш космолёт включит самый-главный-двигатель и улетит чёрт знает куда.
Программные ошибки? Пересчитывать каждые 5 секунд одни и те же данные с одной и той же ошибкой… Не лучшее решение.
Накопление ошибки во флоатах? Всё просто — не делайте так никогда. Разговор не с этого начался.
Или просто поговорить надо на отвлечённые темы?.. Тогда, пожалуйста, не ко мне.
Дело в том что однократная ошибка в случае полного пересчета уйдёт со временем и больше беспокоить не будет, а для рекурсивного алгоритма ошибка засядет надолго и если это девайс с аптаймом в 15 лет, за такой срок ошибок накопится просто вагон. А если его перезапускать каждые сутки никто ничего не заметит, конечно. Вот для этого и нужны пересчёта по полной, чтобы периодически сбрасывать возможные ошибки и не допускать их накопления. Независимо от их природы.
По большей части, повреждения данных не приводят к перманентным искажениям данных, даже повреждение стека — поток рано или поздно будет завершен аварийно, но система продолжит работать. А тут данные, обнаружить изменение которых нет никакой возможности а последствия — перманентные искажения, на основе которых будут приниматься какие-то важные решения.
Вач-дог спасает совсем от других проблем.
Система должна обладать свойством самовосстановления после сбоя, даже если часть данных будет потеряна она должна продолжить работать.
Вач-дог спасает совсем от других проблем.
Система должна обладать свойством самовосстановления после сбоя, даже если часть данных будет потеряна она должна продолжить работать.
"Главный недостаток фильтра скользящего среднего — вычислительная сложность, пропорциональная длине фильтра N." — ну надо ж было ляпнуть такую ерунду. Вычислительная сложность — одно сложение, одно вычитание, одно деление на константу (заменяется на умножение, а то и на сдвиг). O(1).
Вот памяти O(N) надо, это да. Поэтому на совсем мелких девайсах непопулярен. И других недостатков хватает.
Автор имел в виду нерекурсивный фильтр (т.е. функция от предыдущих N входных отсчетов) — а он реализуется как сумматор-делитель всех отсчетов, со сложностью O(N).
Сложить, вычесть — это и есть «открытый» автором рекурсивный фильтр.
А изначальный фильтр у него — все сложить.
Причем у автора в программе ошибка.
А изначальный фильтр у него — все сложить.
Причем у автора в программе ошибка.
Зачем переменные static? это не позволяет делать в программе 2 параллельных фильтра.
Чем же рекурсивный вариант лучше прямого? Все равно N значений в памяти хранить
но вычислять то одно
тогда зачем хранить n отсчетов?
Нда, без буффера никак, по сути надо реализовывать задержку в N отсчетов. Чего кстати в последней реализации на си не видно, думаю так будет корректнее:
#define N (4)
int filter(int x)
{
static int m[N];
static int y;
y=y+(x-m[0]);
for (int i=1;i<N;i++) m[i-1]=m[i];
m[N-1]=x;
return y/N;
}
#define N (4)
int filter(int x)
{
static int m[N];
static int y;
y=y+(x-m[0]);
for (int i=1;i<N;i++) m[i-1]=m[i];
m[N-1]=x;
return y/N;
}
Ужасно-ужасно! Двигать массив поэлементно? Это будет дольше чем считать «по полной программе».
Вместо того чтобы двигать «окно» лучше организовать классический кольцевой буфер — двигается указатель, а массив остаётся на месте. Число по указателю извлекаем — это будет последний элемент буфера, новое на его место записываем — это будет начало буфера, и сдвигаем указатель по кругу на 1 позицию. Никаких перекидываний целых кусков памяти!
Представьте себе крайнюю ситуацию, когда N = 2000000 и каждую итерацию вам надо будет 2млн элементов сдвинуть на одну позицию… да быстрее их будет сложить и не парится с рекурсивным вычислением.
Вместо того чтобы двигать «окно» лучше организовать классический кольцевой буфер — двигается указатель, а массив остаётся на месте. Число по указателю извлекаем — это будет последний элемент буфера, новое на его место записываем — это будет начало буфера, и сдвигаем указатель по кругу на 1 позицию. Никаких перекидываний целых кусков памяти!
Представьте себе крайнюю ситуацию, когда N = 2000000 и каждую итерацию вам надо будет 2млн элементов сдвинуть на одну позицию… да быстрее их будет сложить и не парится с рекурсивным вычислением.
оно може и понятнее, но работает дольше
«Чего кстати в последней реализации на си не видно»
по моему отлично видно «n=(n+1)%N;»
я так понимаю большинство собравшихся тупит по патерну КИХ фильтра
Поясню. Входные данные складываются в буфер, указатель буфера закольцовывается n=(n+1)%N;
Значение указателя и есть нулевой отсчет, или согласно математическим формулам n-ный отсчет
Минус первый (n-1) отсчет это (n+N-1)%N, или в условиях N=2^L (n-1)&(N-1)
Минус k-тый (n-k) это (n+N-k)%N при условии что k<N, отсчеты k>N не сохранены
«Чего кстати в последней реализации на си не видно»
по моему отлично видно «n=(n+1)%N;»
я так понимаю большинство собравшихся тупит по патерну КИХ фильтра
Поясню. Входные данные складываются в буфер, указатель буфера закольцовывается n=(n+1)%N;
Значение указателя и есть нулевой отсчет, или согласно математическим формулам n-ный отсчет
Минус первый (n-1) отсчет это (n+N-1)%N, или в условиях N=2^L (n-1)&(N-1)
Минус k-тый (n-k) это (n+N-k)%N при условии что k<N, отсчеты k>N не сохранены
Прямой — надо складывать все N значений, потом делить…
А рекурсивный — сложить текущее значение(начало окна) и вычесть последнее(конец окна), и одно деление.
А рекурсивный — сложить текущее значение(начало окна) и вычесть последнее(конец окна), и одно деление.
Вероятно этот алгоритм медленнее так как предусматривает дополнительную запись в память.
Думаю сложение 4х будет быстрее
Думаю сложение 4х будет быстрее
Это какую дополнительную? Обычно в таких алгоритмах используют кольцевой буфер — по указателю считали ячейку и это будет наш последний элемент, и на его место вписали свежее значение, передвинули указатель на следующий элемент или перешли на начало если это конец выделенной области под массив.
N может быть куда больше 4. Просто пример приведен для N = 4.
Во-первых, тут ОДНА дополнительная запись. В нерекурсивном оригинале будет 4 (а в большинстве случаев куда больше, скажем 64) чтения из той же памяти.
А во-вторых, это микроконтроллер. Если ОЗУ набортная (есть «толстые» модели с внешней памятью, но во всяких DIY это редкость), доступ к ней — ровно один такт.
А во-вторых, это микроконтроллер. Если ОЗУ набортная (есть «толстые» модели с внешней памятью, но во всяких DIY это редкость), доступ к ней — ровно один такт.
Заметьте, ОДНА дополнительная ЗАПИСЬ.
Так как есть требование когерентности кеша то данная операция отразиться на замедлении всех ядер.
Сейчас основные тормоза это совсем не сложение или умножение — это чтение и запись в память.
доступ к памяти десятки и сотни тактов.
Так как есть требование когерентности кеша то данная операция отразиться на замедлении всех ядер.
Сейчас основные тормоза это совсем не сложение или умножение — это чтение и запись в память.
доступ к памяти десятки и сотни тактов.
Когерентность кэша нужна, если один фильтр считается из разных потоков. Так сделать можно, но зачем?
ПС. Если считать строго, то записей в память больше:
не рекурсивный) чтение и запись индекса, запись в массив, N ЧТЕНИЙ из массива
рекурсивный) чтение и запись индекса, ЧТЕНИЕ и запись в массив, ЧТЕНИЕ и ЗАПИСЬ суммы.
В первом случае мы задействуем N+1 адрес памяти за раз, во втором 3
Чем больше N тем больше промахов кэша будет в первом случае. Во втором количество промахов почти не зависит от N.
ПС. Если считать строго, то записей в память больше:
не рекурсивный) чтение и запись индекса, запись в массив, N ЧТЕНИЙ из массива
рекурсивный) чтение и запись индекса, ЧТЕНИЕ и запись в массив, ЧТЕНИЕ и ЗАПИСЬ суммы.
В первом случае мы задействуем N+1 адрес памяти за раз, во втором 3
Чем больше N тем больше промахов кэша будет в первом случае. Во втором количество промахов почти не зависит от N.
А как же CIC фильтр и Hogenauer pruning для пущей экономии?
так этож оно и есть
Такие типы фильтров широко известны в узких кругах, и называются: рекурсивные фильтры с линейной ФЧХ [Введение в цифровую фильтрацию. Под. ред. Богнера Р. М: 1976] или CIC-фильтры [DspLib]. Существует научная школа проф. Турулина И.И. [РГБ], занимающаяся исследованием подобных фильтров.
Можно пойти дальше и таким же образом реализовать треугольный фильтр.
Ещё такой фильтр неустойчивый — при реализации на числах с плавающей точкой он через некоторое время станет накапливать постоянную составляющую.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Рекурсивный фильтр скользящего среднего