Цифровая передискретизация сигналов на основе полиномиальной интерполяции. Фильтр Фарроу
![]() DSPL-2.0 — свободная библиотека алгоритмов цифровой обработки сигналов Распространяется под лицензией LGPL v3
Страница проекта на SourceForge
|
В современных системах передачи информации необходимо обеспечить тактовую синхронизацию передатчика и приемника. При этом использование независимых задающих генераторов на передающей и принимающей стороне приводит к разнице частот дискретизации сигналов передатчика и приемника.
Помимо этого, часто встает задача компенсации, так называемой дробной задержки на величину меньше интервала дискретизации. Фильтр, способный компенсировать произвольную дробную задержку, можно использовать и для синхронизации задающих генераторов ввиду их медленной нестабильности. Для этого необходимо использовать дополнительный детектор временной ошибки для расчета дробной задержки сигналов.
Также бывает необходимо произвести
преобразование частоты дискретизации в дробное число раз
, где
и
— целые числа.
В данном разделе мы рассмотрим один из эффективных методов решения указанных задач на основе полиномиальной Лагранжевой интерполяции [1, стр. 115]. Также будет рассмотрен фильтр Фарроу [2], реализующий метод полиномиальной Лагранжевой интерполяции для цифровой передискретизации сигналов [3, 4].
Пусть имеется входной сигнал ,
,
отсчеты которого взяты с частотой дискретизации
Гц.
Тогда отсчет с номером
соответствует моменту времени
с.
Необходимо произвести пересчет цифровых значений входного сигнала
в цифровые значения сигнала
,
,
взятые с частотой дискретизации
,
где
и
целые числа[1].
Кроме того, первый отсчет
должен быть задержан во времени
относительно первого отсчета входного сигнала
на величину
с,
.
Далее в этом разделе переменной будут индексироваться отсчеты
исходного сигнала
, взятые с частотой дискретизации
,
а переменной
будут индексироваться отсчеты сигнала после передискретизации
.
Таким образом, -ый отсчет
соответствует моменту времени:














На рисунке 1 показаны моменты
дискретизации исходного сигнала (шкала
),
а также моменты взятия отсчетов
передискретизированного сигнала
(шкала
).
Частный случай 1.
,
.
В этом случае частота дискретизации
,
и сигнал
полностью повторяет
.
Частный случай 2.
,
.
В этом случае частота дискретизации
,
но сигнал
имеет дробнную задержку относительно входного сигнала
.
Заметим, что
хранит задержанное на
значение входного сигнала.
Это означает, что шкала
соответсвует моменту времени на
отсчета раньше чем s(0). Это объясняет знак «минус» в выражениях (1)
и (2).
Частный случай 3.
,
,
.
В этом случае частота дискретизации сигнала
,
, в целое число раз
выше частоты дискретизации сигнала
.
Таким образом, имеем цифровую интерполяцию сигнала
.
Частный случай 4.
,
,
.
В этом случае имеем дробную передискретизацию сигнала
.
Частота дискретизации сигнала
равна
.
Частный случай 5.
,
,
.
В этом случае имеем дробную передискретизацию сигнала
плюс добавление дробной задержки.
Это наиболее общий из рассматриваемых частных случаев.
Частота дискретизации сигнала
равна
.
Для решения задачи передискретизации необходимо по имеющемуся
дискретному сигналу ,
, произвести
восстановление непрерывного сигнала
и рассчитать его дискретные значения для моментов времени
,
где
рассчитывается согласно (2).
Процесс передискретизации для частного случая 2 (компенсация дробной задержки) показан на рисунке 2.

Поскольку мы оперируем только с индексами отсчетов сигнала,
то и значения также задаются не в абсолютных значениях
времени, а нормированными к частоте дискретизации.
В курсе математического анализа доказывается,
что через точек проходит единственный полином степени
.
Например, через две точки можно провести только одну прямую,
через три точки можно провести только одну параболу.
Единственный полином степени
, проходящий через
точек,
называется интерполяционным полиномом Лагранжа:




Для расчета коэффициентов мы можем составить
систему линейных уравнений (смотри рисунок 2):

Данная система может быть записана в матричной форме как:



Решение системы уравнений может быть получено в виде:



Процедура вычисления обратной матрицы является одной из наиболее затратных,
с точки зрения вычислительных ресурсов.
В общем случае требуется количество операций ,
пропорциональное кубу размерности квадратной матрицы.
Например, для расчета коэффициентов кубического полинома для
в общем случае требуется
умножения,
что трудно реализуемо на практике.
В дальнейшем мы увидим, как можно сократить количество операций умножения до трех,
причем две из трёх операций будут умножения на
,
что легко реализуется в целочисленной арифметике путем битового
сдвига на один разряд вправо.
Мы еще вернемся к данному вопросу ниже. Сейчас же мы рассмотрим эффективное представление полиномов по схеме Горнера (Horner structure).
Рассмотрим полином (3) более подробно:










Данное представление называется схемой Горнера (Horner structure)
и широко используется для эффективного расчета значений полиномов [5, стр. 126],
[6, стр. 144].
Ее основное преимущество в том, что для расчета значения полинома степени ,
при известных коэффициентах, требуется
умножитель и сумматор.
Построение полинома для интерполяции часто проводят при использовании ортогональных полиномов Лагранжа. Однако решение системы линейных уравнений (4) является более общим подходом, который может быть применен не только для Лагранжевой интерполяции, но и для других методов полиномиальной интерполяции (Эрмитова полиномиальная интерполяция, сплайн-интерполяция и других).
Мы уже говорили о том, что операция вычисления обратной матрицы является вычислительно сложной задачей. Кроме того, входной поток данных может быть очень длинным, и для обработки мы можем применить кусочную полиномиальную интерполяцию. При этом встает вопрос выбора порядка полинома (количество отсчетов входного сигнала для интерполяции).
Наиболее часто используемым методом является кусочно-полиномиальная кубическая интерполяция ввиду компромисса между точностью и вычислительными затратами. Рассмотрим метод кусочно-полиномиальной кубической интерполяции более подробно.
Полином третьей степени может быть построен по четырем точкам согласно выражению (8).
Для любого можно получить два отсчета правее и левее
как это показано на рисунке 4a.
Тогда значение
может быть рассчитано на основе четырех
входных отсчетов
,
,
,
.

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




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



Каждый КИХ-фильтр рассчитывает один коэффициент полинома,
после чего они подаются на схему Горнера для расчета
полинома при текущем значении дробной задержки .
Структура, приведенная на рисунке 5, носит название
фильтра Фарроу (Farrow filter) [2].

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







Таким образом, мы можем переписать (17) в оптимизированном
виде всего с тремя умножителями (причем два из них равны ):


Таким образом, мы получили алгоритм, который рассчитывает коэффициенты
интерполяционного полинома Лагранжа с использованием всего одного
умножителя на и двух тривиальных умножителей на
.
В данном разделе мы рассмотрели структурные схемы фильтров цифровой передискретизации на основе полиномиальной Лагранжевой интерполяции.
Была рассмотрена схема Горнера для расчета значений полинома. Количество умножителей и сумматоров схемы Горнера равно порядку полинома.
Получена структура фильтра Фарроу, и произведена его оптимизация.
В результате коэффициенты интерполяционного полинома Лагранжа могут быть рассчитаны при использовании всего трех умножителей.
Требуется одно умножение на и два тривиальных умножения на
.
В следующем разделе мы рассмотрим характеристики фильтра цифровой передискретизации и примеры его использования для компенсации дробной задержки, интерполяции сигналов и дробного изменения частоты дискретизации сигнала.
[1] Все приведенные выражения также справедливы
для произвольных отличных от нуля вещественных значений и
,
в том числе иррациональных.