Уменьшенная точность с целью повышения пропускной способности

Чтобы ускорить работу алгоритма фильтрации, может потребоваться уменьшить точность коэффициентов и/или входных выборок сигнала, что позволит уменьшить размер аккумулятора. Уменьшенный аккумулятор означает, что алгоритм потребует меньше операций на умножение коэффициента фильтра и выборки. Однако, прежде чем уменьшать точность, нужно принять во внимание два момента:

- уменьшение точности входных выборок означает добавление шума в систему, что обычно нежелательно.
- уменьшение точности коэффициентов фильтра означает, что нужную характеристику фильтра получить будет сложнее.

Другие методы повышения пропускной способности см. в разделе "Оптимизация реализации фильтра".

[4. Реализация фильтра]

Примеры фильтров в этой статье разработаны и скомпилированы в среде компилятора IAR EWAVR версии 5.03A.

Коэффициенты фильтра вычислены с помощью специального программного обеспечения. Для этого имеется множество программ, начиная от дорогих типа Matlab, кончая бесплатными апплетами Java, доступными через web. Список web-сайтов, которые имеют дело с темой вычислениями коэффициентов фильтра, предоставлен в литературном списке в конце статьи. Альтернативой может быть вычисление коэффициентов "трудным" путем - вручную. Методы для расчета коэфффициентов фильтра (и достижения стабильности этих фильтров) описаны в [1] и [2].

В примерах реализованы два фильтра - фильтр верхних частот (High Pass, HP) FIR-фильтр 4-го порядка, и полосовой фильтр (Band Pass, BP) IIR-фильтр 2-го порядка. В обеих реализациях используются 10-битные со знаком отсчеты сигнала на входе (разрядность АЦП AVR 10 бит). FIR-фильтр использует 13-битные коэффициенты со знаком, IIR-фильтр использует 12-битные коэффициенты со знаком. Это требует максимального размера аккумулятора 24 бита.

Фильтры реализованы на ассемблере по соображениям эффективности. Реализация выполнена так, что функции фильтра можно вызывать из кода на C. Перед вызовом функций фильтра требуется инициализировать узлы фильтра (память и элементы задержки) - иначе начальные условия для работы фильтра будут неизвестны. Для обоих фильтров приведен пример кода на C, инициализирующего и вызывающего предоставленные функции фильтра.

Все параметры, требуемые для фильтрации, передаются во время выполнения, поэтому функции могут быть повторно использованы для реализации более чем одного фильтра без дополнительных затрат места под код. Это может использоваться для каскадного соединения фильтров - часто несколько фильтров второго порядка включаются друг за другом (выход одного фильтра со входом другого) для получения фильтра более высокого порядка. Однако, так как выход каждого из фильтров в каскаде масштабируется вниз перед попаданием на вход другого фильтра, то на выходе результирующего фильтра может оказаться совсем не то, что ожидалось. Это происходит потому, что теряется точность между каскадами фильтров. Естественно, эффект этого становится более явным с увеличением количества звеньев в каскадном фильтре.

Реализация фильтров сделана с фокусом на быстродействие, поскольку очень важна высокая пропускная способность фильтра. См. раздел "Оптимизация реализации фильтра", где размещены советы по уменьшению размера кода, увеличению пропускной способности, экономии использования памяти.

4.1 FIR-фильтр 4-го порядка

Чтобы продемонстрировать технику каскадирования, этот фильтр реализован путем соединения двух HP фильтров второго порядка. Оба фильтра сделаны по технике окна, описанной в [1], применено окно Хемминга (Hamming window). Параметры фильтра показаны в Таблице 4-1. Рисунок 4-1 показывает амплитудную характеристику обоих фильтров по отдельности, и характеристику их каскадирования.

Таблица 4-1: параметры HP FIR-фильтра 2-го порядка

Рисунок 4-1: АЧХ FIR-фильтров

Подпрограммы фильтров реализованы на ассемблере для получения эффективного кода. Однако параметры фильтра и узлы фильтра предварительно (до вызова функции фильтрации) должны быть проинициализированы программой на языке C. Структура содержит коэффициенты фильтра и узлы фильтра, которые задаются для каждого фильтра отдельно. Структуры заданы следующим образом:

struct FIR_filter
{
int filterNodes [FILTER_ORDER]; //память для узлов фильтра
int filterCoefficients[FILTER_ORDER+1]; //память для коэффициентов фильтра
} filter04 = {0,0, B10, B11, B12}, //инициализация 1-го фильтра
filter06 = {0,0, B20, B21, B22}; //инициализация 2-го фильтра

Массив filterNodes используется как буфер FIFO, в котором сохраняются предыдущие значения входного сигнала. Массив filterCoefficients используется feedforward-коэффициентов (bj) фильтра. После того, как фильтр проинициализирован, может быть вызвана функция фильтра. Функция фильтра задана следующим образом:

int FIR2(struct FIR_filter *myFilter, int newSample);

Сначала функция копирует указатель на структуру FIR_filter в Z-регистр, поскольку он может использоваться непрямой (indirect) адресации данных, например для операций с использованием указателя. Затем основной алгоритм готов к запуску. Выборки (узлы фильтра) загружаются и умножаются (инструкцией ассемблера MUL) с соответствующими коэффициентами. Результаты добавляются в 24-битный аккумулятор. Когда все выборки и коэффициенты умножены и сохранены (multiplied-and-accumulated, операция MAC), результат масштабируется вниз и возвращается. Процесс обработки можно увидеть на Рисунке 4-2, который описывает действия алгоритма фильтра FIR.

Имейте в виду, что несмотря на то, что диаграмма на Рисунке 4-2 показывает алгоритм, реализованный с использованием циклов, на самом деле алгоритм реализован линейным кодом (для увеличения быстродействия). Цикл на диаграмме просто применен для улучшения читаемости алгоритма.

Рисунок 4-2: Generic (традиционный) алгоритм FIR-фильтра

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

4.1.1 Скорость работы FIR-фильтра

Таблица 4-2 показывает быстродействие одного звена - FIR-фильтра второго порядка. Значение счетчика в таблице показывают затраты времени (в циклах ядра AVR) на выполнение алгоритма фильтра (операции MUL и MAC, обновление узлов), а также на дополнительную обработку при завершении функции (включая масштабирование вниз). Время, затраченное на вызовы (call) и возврат из функции (return), в таблице не учитывается.

Таблица 4-2: затраты процессорного времени на выполнение алгоритма FIR-фильтра второго порядка.

Имейте в виду, что изменение порядка фильтра может принудить к изменению размера аккумулятора, что изменит количество затрачиваемых инструкций/циклов процессора. Эффективность фильтра в пересчете на порядок фильтра (последний столбец таблицы) также поменяется.

4.2 IIR-фильтр второго порядка

Для этой реализации применен полосовой (Band Pass, BP) IIR-фильтр Баттерворта. Параметры фильтра показаны в Таблице 4-3, АЧХ на Рисунке 4-3.

Таблица 4-4: параметры IIR-фильтра второго порядка

Поскольку коэффициент a₀ определяет множитель для масштабирования вниз выхода фильтра, он не задан в коде на языке C, а просто задан в коде ассемблера для масштабирования вниз.

Рисунок 4-3: АЧХ IIR-фильтра 2-го порядка

Структура содержит коэффициенты фильтра и узлы фильтра. Фильтр должен быть проинициализирован перед тем, как будет вызвана функция фильтра. Структура определена следующим образом:

struct IIR_filter
{
int filterNodesX[FILTER_ORDER]; //узлы фильтра, тут сохраняются входные выборки x(n-k)
int filterNodesY[FILTER_ORDER]; //узлы фильтра, тут сохраняются выходные значения y(n-k)
int filterCoefficientsB[FILTER_ORDER+1]; //feedforward коэффициенты фильтра (bj)
int filterCoefficientsA[FILTER_ORDER]; //feedback коэффициенты фильтра (ai)
} filter04_06 = {0,0,0,0, B0, B1, B2, A1, A2}; //инициализация фильтра

Массивы filterNodesX и filterNodesY используются как буферы FIFO, сохраняющие соответственно входные и выходные значения сигнала фильтра. Массивы filterCoefficientsB и filterCoefficientsA используются для коэффициентов фильтра соответственно feed-forward и feedback. После инициализации фильтра может быть вызвана функция фильтра. Функция фильтра определена следующим образом:

int IIR2(struct IIR_filter *myFilter, int newSample);

Сначала функция копирует указатель на структуру фильтра в Z-регистр, поскольку он может использоваться непрямой (indirect) адресации данных, например для операций с использованием указателя. Затем основной алгоритм готов к запуску. Выборки входа и данные выхода (узлы фильтра) загружаются и умножаются с соответствующими коэффициентами. Результаты добавляются в 24-битный аккумулятор. Когда все выборки и коэффициенты умножены и сохранены (multiplied-and-accumulated, операция MAC), узлы фильтра в FIFO-буфере обновлены, результат масштабируется вниз и возвращается. Имейте в виду, что результат в аккумуляторе масштабируется вниз перед сохранением его в у[n-1] ячейке буфера FIFO. Процесс обработки можно увидеть на Рисунке 4-4, который описывает действия алгоритма фильтра IIR.

Рисунок 4-4: Generic (традиционный) алгоритм IIR-фильтра

Имейте в виду, что несмотря на то, что диаграмма на Рисунке 4-4 показывает алгоритм, реализованный с использованием циклов, на самом деле алгоритм реализован линейным кодом (для увеличения быстродействия). Цикл на диаграмме просто применен для улучшения читаемости алгоритма.

4.2.1 Скорость работы IIR-фильтра

Таблица 4-4 показывает быстродействие IIR-фильтра второго порядка. Значение счетчика в таблице показывают затраты времени (в циклах ядра AVR) на выполнение алгоритма фильтра (операции MUL и MAC, обновление узлов), а также на дополнительную обработку при завершении функции (включая масштабирование вниз). Время, затраченное на вызовы (call) и возврат из функции (return), в таблице не учитывается.

Таблица 4-4: затраты процессорного времени на выполнение алгоритма IIR-фильтра второго порядка.

Имейте в виду, что изменение порядка фильтра может принудить к изменению размера аккумулятора, что изменит количество затрачиваемых инструкций/циклов процессора. Эффективность фильтра в пересчете на порядок фильтра (последний столбец таблицы) также поменяется.

[5. Оптимизация реализации фильтра]

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

5.1 Уменьшение объема кода и увеличение пропускной способности

Один из путей одновременного уменьшения объема кода и увеличения пропускной способности - нужно убедиться в том, что выполняются только необходимые вычисления. Ассемблерный код для фильтров, реализованный в примерах из статьи, сделан так, что он будет работать с любым набором коэффициентов фильтра. Однако IIR-фильтр второго порядка имеет два нулевых коэффициента. Умножение и последующее накопление с нулевыми коэффициентами может быть, конечно, опущено - что никак не повлияет на работу фильтра, но увеличит быстродействие и уменьшит размер кода.

5.2 Уменьшение размера кода

Уменьшение размера кода может быть достигнуто путем реализации MAC как вызова функции, вместо этой операции, выполненной как макрос. Однако это ударит про пропускной способности, так как на каждый вызов и возврат из функции тратятся дополнительные циклы процессора.

Другой путь уменьшения объема кода - реализация фильтров высокого порядка с помощью каскадирования фильтров меньшего порядка, как продемонстрировано на FIR-фильтре 4-го порядка. Хотя, как отмечалось ранее, это уменьшит точность фильтра из-за промежуточного масштабировнаия вниз на каждом каскаде. Кроме того, не получится выполнить оптимизацию путем пропуска MAC-операций на нулевых коэффициентах, так как это возможно не для всех реализаций фильтра.

5.3 Уменьшение размера используемой памяти (RAM)

Коэффициенты фильтра в обоих примерах реализаций размещаются в SRAM. Простой путь уменьшения памяти - размещение коэффициентов в FLASH и выборка их по необходимости. Это потенциально почти наполовину уменьшит расход памяти для параметров фильтра, поскольку на коэффициенты тратится почти столько же памяти, как и на узлы (предыдущие состояния входа и выхода) фильтра.

[Зачем все это? (О чем вообще тут говорится?..)]

Если Вы дочитали статью до конца (напомню, что это апноут Atmel AVR223), то значит, что Вас в некоторой степени интересует цифровая обработка сигналов (ЦОС). Если же Вы почти все поняли в этой статье (я, например, не понял только Z-домен, Z-преобразование и все, что с этим связано), то Вы раньше уже интересовались ЦОС, и немного знакомы с общими принципами, но не видели реального способа выполнить какую-нибудь (даже самую простую) задачу ЦОС. Поздравляю! Теперь у Вас в руках готовый инструмент, хорошая точка для старта создания своих собственных программ. Чем мне больше всего понравился апноут AVR223 - дается в сжатом виде именно то, что нужно для начала - просто бери и делай (причем можно делать не только на AVR, если основной принцип понятен).

В заключение хочу привести несколько соображений по поводу предоставленной в апноуте AVR223 информации - как на основе неё сделать свой собственный DSP-фильтр. Все на примере той же платформы AVR, которая и рассматривается в статье.

1. Сначала необходимо понять - чего мы можем, и чего не можем. То есть какую максимальную полосу частот мы сможем обработать, и какой порядок фильтра при этом можно применить (при той же самой разрядности сигнала 10 бит, что применена в примерах). Понятно, что чем выше максимальная рабочая частота, которую мы можем пропустить через фильтр, тем фильтр качественнее, и тем проще делать предварительную аналоговую фильтрацию (об этом позже). От порядка фильтра зависит крутизна характеристики фильтра, т. е. насколько хорошо фильтр ослабляет ненужный сигнал (для упрощения пока не рассматриваем другие характеристики фильтра типа групповой задержки, фазочастотной характеристики и т. п.). Исходя из предположения, что кварц у нас максимально возможный для AVR 20 МГц, по таблицам 4-2 и 4-4 можно подсчитать максимально возможную частоту выборок входного сигнала, которую мы успеем обработать. Например, у нас FIR-фильтр 4-го порядка (т. е. два FIR-фильтра 2-го порядка, соединенные в цепочку - именно так, как описывается в статье). Тогда получается, что полный проход вычислений фильтра займет (по Таблице 4-2), с учетом вызова подпрограммы FIR

2 + 76 + 10 + 2 = 90 циклов.

Если учесть еще время на чтение результатов с АЦП и время на обработку прерывания (в реальном приложении придется читать АЦП в обработчике таймера, и наверное там же делать вызов функции FIR), то грубо придется добавить еще 10 циклов. Итого, имеем 90+10=100 циклов ядра, которые занимает обработка одной выборки АЦП. Что это означает? Это как раз и есть ограничение по максимально возможной частоте дискретизации системы Fs, которая как раз и определяет максимальную частоту сигнала, которую может пропустить через себя фильтр (по теореме Котельникова Fs/2).

Итак, остается только вычислить эту максимально возможную частоту дискретизации Fs, и тогда сразу станет понятно, что мы можем, а что нет. Ядро AVR работает на частоте 20 МГц, т. е. в секунду выполняет 20000000 циклов. У нас прокрутка фильтра занимает 100 циклов, т. е. за секунду мы можем сделать 20000000/100 = 200000 прокруток, т. е. частота дискретизации Fs у нас может быть 200000 Гц, или 200 кГц. Таким образом, мы можем пропускать через фильтр частоты до 100000 кГц. Звучит, конечно, круто, однако необходимо помнить, что это подсчет для идеального случая - когда AVR у нас ничего, кроме расчета фильтра, не делает, а так в реальной жизни, увы, не бывает. Ведь надо еще и опрашивать датчики, кнопки, мигать светодиодиками и вообще выполнять какой-никакой общий фоновый алгоритм. В итоге примерно получим максимальную Fs около 100 кГц, т. е. максимальный входной сигнал - до 50 кГц. Все равно что-то слишком круто...

Если вдруг захотим фильтр не 4-го порядка, а 8-го, то понятно, что все автоматически ухудшается в два раза - максимальная Fs 50 кГц, максимальная входная частота 25 кГц и так далее. Надеюсь, теперь Вы в состоянии оценить возможности цифровой обработки на AVR.

2. Необходимо не забывать важное условие - ни в коем случае нельзя на вход цифрового фильтра подавать частоты выше чем Fs/2, иначе это чревато грубыми ошибками в работе фильтра (не спрашивайте меня, почему - в умных книжках все написано). Чтобы выполнить это условие, на входе цифрового фильтра всегда ставят предварительный аналоговый фильтр низкой частоты с частотой среза Fs/2 или ниже (хотя бы простую RC-цепочку). Иначе - никак. Какая ирония - чтобы цифровой фильтр работал, на его входе должен быть обязательно старый добрый аналоговый фильтр... Понятно, что чем меньше частота среза аналогового фильтра по отношению к Fs/2, тем надежнее будет подавление паразитных составляющих сигнала, и тем сильнее можно упростить схему аналогового фильтра. Поэтому если хотим совсем простую схему, то полоса допустимого входного сигнала уменьшается еще больше - в два, в четыре раза по отношению к Fs/2. В идеале входной фильтр должен ослаблять сигнал в паразитном для цифрового фильтра диапазоне до уровня единицы младшего разряда АЦП (т. е. для 10-битного АЦП входной фильтр должен давать ослабление ненужного сигнала в 2¹⁰ раз, или 60 дБ). Т. е. реально на частоте дискретизации 100 кГц удобно обрабатывать частоты не выше 4..8 кГц, иначе придется городить сложные многоступенчатые аналоговые фильтры... Ну и засада. Теперь понятно, почему AVR еще не "убийца" классических дорогущих DSP - за все надо платить, розовые очки сняты. Так что AVR в цифровой обработке - вовсе не панацея от всех проблем, но AVR вполне может найти применение в радиолюбительской практике для грубой обработки звука (10 бит не ахти какая точность) или - что еще лучше - для декодирования сигналов телеуправления.

Для расчета входных аналоговых фильтров можно пользоваться готовыми инструментами - тем же Matlab или, что еще лучше, онлайн утилитами наподобие WEBENCH от National Semiconductor (см. [7]).

3. Для узкоспециализированных фильтров можно применить даже однобитное аналогово-цифровое преобразование (с помощью компаратора). Например, такое решение вполне подходит для тональных декодеров (DTMF и т. п.). При этом код можно существенно оптимизировать под выполнение конкретной задачи - например, в случае декодера DTMF просчитывать сразу 8 полосовых фильтров для тональных частот.

Для рассчета коэффициентов цифровых фильтров (a_i, b_j) можно опять-таки применить онлайн-инструменты (см. [4], [5], [6], [9]).

[Ссылки]

1. “Discrete-Time signal processing”, A. V. Oppenheimer & R. W. Schafer. Prentice-Hall International Inc. 1989. ISBN 0-13-216771-9
2. “Introduction to Signal Processing”, S. J. Orfanidis, Prentice Hall International Inc., 1996. ISBN 0-13-240334-X
3. FIR filter design, http://www.iowegian.com/scopefir.htm
4. FIR filter design, http://www.dsptutor.freeuk.com/FIRFilterDesign/FIRFiltDes102.html
5. FIR filter design, http://www.dsptutor.freeuk.com/KaiserFilterDesign/KaiserFilterDesign.html
6. FIR and IIR filter design, http://www-users.cs.york.ac.uk/~fisher/mkfilter/
7. WEBENCH® Designer Tools.
8. Проектирование цифровых фильтров.
9. Онлайн расчет фильтра Кайзера 1 и 2.
10. В архиве: А.Б. Сергиенко. Цифровая обработка сигналов. Изд. Питер, Учебник для вузов, 2002 г., ISBN 5-318-00666-3. Айфичер Э.С., Джервис Б.У. Цифровая обработка сигналов: практический подход. 2004 г. ISBN 7-8459-0710-1 и многие другие книги по цифровой обработке сигналов.
11. Исходники примеров из апноута AVR223 с переведенными на русский язык комментариями. И еще несколько лучших, как мне кажется, книжек по ЦОС.