Разработка модулярного КИХ фильтра на базе теоретико-числового БПФ

Цель настоящей работы состояла в том, чтобы разработать модулярный КИХ фильтр с постоянными коэффициентами, базируясь на идее "Теоремы о Свертке" и ее аналога в конечном поле Галуа.

Краткое теоретическое обоснование

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

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

$s(n)=a*b=\sum_{m=0}^{n}a(m)*b(n-m)$, $n=0$ ... $N+M-2$

Архитектуры для вычисления линейных сверток могут быть совершенно различными. Выделяют несколько типов архитектур.

• Последовательная
• Параллельная
• Последовательно-параллельная

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

В случае, если производительности DSP процессора не хватает, то фильтр реализуют аппаратно, используя параллельные архитектуры. Параллельные схемы эксплуатируют метод конвееризации, разделяя этапы конвейера регистрами. Каноническая форма КИХ фильтра выглядит следующим образом:

Преимущества данной архитектуры - это ее быстродействие и возможность работы в реальном времени. К минусам можно отнести значительное увеличение аппаратурных затрат.

Кроме реализаций во временной области, возможна также реализация в частотной области. Базисом для этого является так называемая Теорема о Свертке. Спектр циклической свертки есть произведение спектров сворачиваемых сигналов: $S(k)=A(k)*B(k)$. Где $A(k)$ и $B(k)$ - спектры сворачиваемых сигналов, $S(k)$ - спектр циклической свертки двух сигналов.

Таким образом, вместо того чтобы реализовывать свертку непосредственно по формуле, можно перевести сигналы в частотную область с помощью БПФ, там почленно перемножить, и перевести обратно. Результат будет соответствовать циклической свертке [статья в ростове]. Дополняя нулями последовательности, вычисление циклической свертки станет эквивалентно вычислению искомой линейной свертки. Преимуществом этого метода является сокращение операций. Действительно, используя быстрые схемы преобразования Фурье, мы тратим лишь $n*lg(n)$ операций, что дает выигрых при больших значениях $n$.

Однако, существуют и недостатки. Зачастую в фильтрах подразумевается входной сигнал бесконечной длительности, который фильтруется некоторым ограниченным набором коэффициентов. Параллельная схема отлично справляется с этой задачей в "онлайн" режиме. С методами на основе БПФ дело обстоит сложнее. Во первых не возможно создать БПФ на бесконечное число точек, а во вторых, даже если мы создадим очень большой преобразователь, то мы потеряем "онлайн" режим, так как для того чтобы БПФ начал выдавать значения, нам необходимо чтобы все значения были туда загружены. Чтобы решить данную проблему были введены различные "overlap" методики. Они позволяют обрабатывая блоки малого размера, совмещать их таким образом, чтобы на выходе мы получили необходимую свертку теоретически бесконечной последовательности отсчетов [та презенташка с оверлап методиками].

Резюмируя вышесказанное, что касается методов фильтрации в частотной области, можно отметить что в принципе этот метод можно также реализовывать как в последовательном так и в параллельном виде. Для параллельного метода можно использовать различные конвейерные методики реализации БПФ (типа Radix-2 SPDF). Последовательные методы реализуются программно. Судя по всему, чаще всего эта методика используется именно в последовательной реализации в виде программ на микроконтроллерах и компьютерах общего назначения. Условно классифицировать методы реализации КИХ фильтров можно следующим образом:

Для реализации фильтров, а в общем и других устройств ЦОС, эффективно использовать аппарат модулярной арифметики. Можно использовать модулярную арифметику при реализации любого КИХ фильтра, реализованного любым методом. Однако, наибольший интерес представляет использование модулярной арифметики при параллельной реализации в частотной области. Существует несколько предпосылок для этого вывода, основная из которых заключается в том, что для конечных полей существует аналог теоремы о свертке. Точнее говоря, для конечных полей существует преобразование, аналогичное преобразованию Фурье для которого выполняется теорема о свертке в конечном поле, и для которого соблюдаются все симметрические свойства позволяющие использовать любой быстрый алгоритм для его вычисления. Формула упомянутого преобразования выглядит следующим образом:

$A_k=|\sum_{n=0}^{2^t-1}|a_n*\gamma^{nk}|_p|_p$

Здесь $A_k$ - теоретико-числовой спектр сигнала, $a_n$ - сам сигнал, $p$ - характеристика конечного поля, $\gamma$ - примитивный корень степени $2^t$ [Виноградов, Теория чисел]. Если число $p$ имеет вид $p=q*2^t+1$, то примитивный корень степени $2^t$ - всегда существует и равен $\gamma = \omega^q$.

Таким образом, упомянутое преобразованиек является аналогом дискретного преобразования Фурье тригонометрического базиса, в котором поворачивающие множители $e^{ij\frac{2\pi}{N}}$ заменяются на $\gamma^{ij}$, а операции умножения и сложения комплексных чисел – на соответствующие операции в $GF(p)$.

Кроме очевидных преимуществ в виде распараллеливания вычислений, мы достигаем большей точности, так как вычисления ведутся в конечных молях с целыми поворачивающими множителями, что исключает ошибки представления, характерные для стандартного тригонометрического метода.

Моделирование работы модулярного КИХ фильтра

Краткое описание эксперимента

Была создана модель модулярного КИХ фильтра нижних частот порядка 16. КИХ фильтр реализовывался в модулярном виде по принципу теоремы о свертке и методами блочной обработки(overlap-add). В качестве базисного набора оснований использовался набор:

97=6∙16+1

193= 12∙16+1

257=16∙16+1

В качестве дополнительного модуля для контроля ошибок использовался модуль:

353=22∙16+1

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

Исходные данные

За основу был взят произвольный сигнал на 840 точек.

Основной сигнал и Сигнал после воздействия внешних факторов

Проверка влияния масштабирующего множителя

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

Увеличение коэффициентов

• позволяют уменьшить ошибки представления
• увеличивают аппаратуру и уменьшают производительность схемы

Уменьшение коэффициентов

• позволяют выбирать меньшие основания, соответственно ускоряя и уменьшая схему
• результат становиться менее точным

Сигналы сглаженные фильтром с высоким(2048) и низким(16) разрешением

Сигналы сглаженные фильтром с высоким(2048) и низким(16) разрешением (укрупненный)

Проверка характеристик обнаружения ошибки и уменьшение её влияния интерполяционными методами

Следующим этапом была проверка характеристик обнаружения ошибки и уменьшение её влияния интерполяционными методами. В процессе разработки модели был получен важный вывод: характер искажения выходных данных существенно зависит от места возникновения ошибки. В том случае, если ошибка возникает в любом из каналов на этапах от прямого преобразователя до обратного БПФ включительно, на выходе искажается серия данных, длиной равной длине блока обработки. В случае возникновения ошибки в конце тракта обработки – искажается одно единственное значение.

В случае возникновения одиночной ошибки в конце тракта обработки, возникают хорошие возможности по нивелированию ошибки интерполяционными методами.

График функции с ошибкой в конце канала обработки с вероятностью возникновения 12,5% и График, сглаженный фильтром с интерполяционным сглаживанием возможных сбоев.

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

График функции с ошибкой в начале канала обработки с вероятностью возникновения 0,25% и График, сглаженный фильтром с интерполяционным сглаживанием возможных сбоев.

Разработка и синтез модулярного КИХ фильтра

Разработанные схемы

Были разработаны генераторы IP блоков для прямой реализации каскадного фильтра:

и модулярный вариант на базе теоретико-числового БПФ параллельной реализации:

Был проведен эксперимент по синтезу модулярных КИХ фильтров средствами САПР Synopsys. Порядок фильтров выбирался в диапазоне от 4 до 32 точек. Разрядности в диапазоне 4 – 16 бит. Оценивалась задержка на критическом пути и площадь схемы. Библиотека: Nangate Open Cell Library 43 nm. Для прямого метода рассматривался также вариант с конвейеризацией мультиоперандного сумматора.