Оптимальная регулярная локальная сплайновая интерполяция сигналов

Введение

Рассмотрена задача регулярной интерполя­ции сигнала со спектром, ограниченным ча­стотой ω_m, при его корректной дискретиза­ции. Эта задача имеет точное решение, представленное интерполяционным рядом Ко­тельникова. Однако интерполяция на основе ряда Котельникова является глобальной, что затрудняет ее практическую реализацию и приводит к поиску приближенных решений, при котором предпочтение отдается локаль­ным методам интерполяции.

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

Классические математические подходы к задачам интерполяции подробно изложены в работе [1].

Одно из перспективных современных направлений в теории интерполирования - сплайновая интерполяция. Математические свойства сплайнов подробно исследованы в работах [2, 3]. Практические аспекты сплай- новой интерполяции рассмотрены в работе [4]. Однако основная часть указанных работ по сплайнам посвящена глобальной интерпо­ляции. Локальная сплайновая интерполяция применительно к характеристикам летатель­ных аппаратов рассмотрена в работе [5], при­менительно к сигналам - в источниках [6-12].

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

При регулярной интерполяции сетка дискретизации равномерна и бесконечна, а на каждом частном интервале дискретизации формирование интерполирующей функции осуществляется по одним и тем же правилам. Обозначим координаты узлов интерполяции t_n = nT, s_n = s(nT), где n = 0, ±1, ±2, ...; T - период дискретизации сигнала. Запишем выра­жение для интерполирующей функции в виде

где порождающая функция φ₀(Υ) удовлетво­ряет условию

Сходимость интерполяционного процес­са при неограниченном уменьшении периода дискретизации обеспечивается при выполне­нии условия [13]

где Φ₀(ω) - спектральная плотность φ₀(Υ).

Из условий (2), (3) следуют нормировки

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

Локальные фундаментальные интерполяционные обобщенные сплайн-базисы

При сплайновой интерполяции фрагменты интерполирующей функции ψ_n (t), описыва­ющие ее на каждом частном интервале дис­кретизации t ∈ [t_n; t_n+1], стыкуются в узлах интерполяции так, чтобы вместе с условием согласованности (2) обеспечить непрерыв­ность ее первых r производных (значение r характеризует степень гладкости):

где  - коэффициенты линейного ал­горитма оценки i-й производной сигнала;

M - порядок алгоритма оценки производ­ных.

На рис. 1 показан пример интерполяци­онного фрагмента.

Фрагмент ψ_n (t) интерполирующей функ­ции определяется значениями M предшеству­ющих и M последующих относительно ин­тервала t ∈ [t_n; t_n+1] отсчетов s _n-M, ···, s _n-1, s_n s_n+1, s_n+2, ..., s_n+M+1 (M ≥ 0 - порядок интер­поляции) и представляет собой обобщенный многочлен

Здесь  - линейно независимая си­стема функций (первичный базис);

C_n,k - коэффициенты, которые ввиду выражения (1) линейно связаны с отсчетами сигнала:

где a_{m, k} - постоянные, определяемые мето­дом интерполяции, одинаковые для каждого частного интервала дискретизации. Порядок обобщенного многочлена определяется коли­чеством уравнений в системе (4) и связан со степенью гладкости

Рассматривая восстановление единично­го отсчета, из формул (5), (6) для порождаю­щей функции получим

где коэффициенты определяются из решения матричного уравнения

Таким образом, порождающая функция (8) может быть найдена из уравнения (9). Тог­да в виду (1) для каждого интерполирующего фрагмента сможем записать

Как видно из выражения (11), вычисли­тельные затраты на расчет значения интер­полирующей функции в некоторый момент времени составляют 2M +1 умножений при условии, что значение порождающей функции, соответствующее этому моменту времени, хра­нится в памяти компьютера. Последнее обыч­но имеет место, поскольку моменты времени, в которых будет рассчитываться интерполи­рующая функция, известны заранее. При этом вычислительные затраты определяются только порядком интерполяции и не зависят от сте­пени гладкости и выбора первичного базиса. Однако если указанное условие не выполнено, то на каждое из 2M +1 умножений добавля­ются N операций умножения для расчета (8) и умножения n_w , необходимые для расчета функций первичного базиса. При этом в соот­ветствии с уравнением (7) чем больше степень гладкости, тем больше вычислительные затра­ты, они составляют (2M + 1)((2r + 2) + n_w).

Анализ сходимости при локальной регулярной сплайновой интерполяции сигналов

В статье [13] показано, что сходимость регу­лярного метода интерполяции имеет место, когда он обеспечивает восстановление едини­цы. Рассматривая восстановление единицы, из системы уравнений (4) получим условия сходимости при локальной сплайновой ин­терполяции:

Согласно теореме о дифференцировании сигнала для преобразования Фурье, дополни­тельно укажем, что последовательность ко­эффициентов алгоритма оценки производной нечетного порядка должна быть нечетно-сим­метричной, а в случае производной четного порядка - четно-симметричной:

Анализ искажений при локальной регулярной интерполяции сигналов

Рассматривая преобразование Фурье (1), с учетом свойств линейности и временного за­паздывания для спектральной плотности ин­терполирующей функции запишем

Поскольку спектр дискретного сигнала

где S(ω) - спектральная плотность сигнала s(t);

- частота дискретизации, последнее выражение перепишем в виде

Спектральная плотность интерполиру­ющей функции представляет собой результат выделения спектра исходного сигнала S (ω) из спектра дискретного сигнала S_д(ω) путем умножения порождающей функции Φ₀(ω) (рис. 2) на спектральную плотность. Точным такое выделение является в случае, когда Φ₀(ω) представляет собой прямоугольную функцию, что при локальной интерполяции исключено, поскольку ввиду ограниченно­сти во времени порождающей функции φ₀(t) ее спектральная плотность Φ₀(ω) является аналитической функцией и, не являясь тожде­ственным нулем, не может обращаться в нуль ни на каком конечном интервале. В связи с этим при условии ω_д > 2ω_m интерполирующую функцию ψ(t) можно формально рассматри­вать как результат искажений исходного сиг­нала s(t), при которых для каждой гармоники сигнала частоты ω независимо от других при умножении на Φ₀(ω) происходит изменение ее амплитуды и наложение на сигнал колебаний частот kω_д + ω, k = 0, 1, 2, ..., с амплитуда­ми, пропорциональными Ф₀(kω_д + ω). При этом комбинационного взаимодействия между гармониками сигнала не происходит, поэтому минимизацию искажений можно осуществлять отдельно для каждой гармоники.

Искажения отдельной гармонической составляющей сигнала будем характеризовать коэффициентом искажений, определяемым как отношение действующего значения совокуп­ности нежелательных гармоник, возникших при интерполяции, к действующему значению восстанавливаемой гармоники. При этом, рас­сматривая только такую интерполяцию, при которой обеспечивается сходимость, т. е. с уче­том условия (3), Φ₀(0) = T, запишем выраже­ние для коэффициента искажений:

При практических расчетах учитывается конечное число нежелательных гармоник

Анализ зависимости К_и(ω) может быть положен в основу определения требуемого значения частоты дискретизации и/или выбо­ра метода интерполяции при заданном уровне искажений. Выбор допустимого уровня ис­кажений К_и,_доп зависит от специфики реша­емой задачи и определяет граничную часто­ту ω_гр для метода интерполяции, такую, что Ки(ω ≤ω_гр ) ≤ К_{и, доп}. Для восстановления сиг­нала с максимальной частотой спектра ω_m с заданным уровнем искажений требуется обе­спечить ω_m ≤ ω_гp , при этом каждая гармоника сигнала частоты ω восстанавливается с К_и(ω) ≤ K_и,доп.

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

При заданных допустимом уровне искажений К_и,_доп, первичном базисе , порядке интерполяции M и степени гладкости r тре­буется отыскать набор элементов матрицы D (10), удовлетворяющий условиям сходимо­сти (12), который обеспечивает максималь­ную граничную частоту ω_гр коэффициента искажений (14):

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

Методы решения задачи синтеза оптимального интерполяционного сплайн-базиса

Задача синтеза оптимального интерполяцион­ного сплайн-базиса (16) - это многопараметри­ческая однокритериальная задача оптимиза­ции. Замкнутый вид целевой функции задачи получить затруднительно, что обусловило оты­скание приближенных (квазиоптимальных) решений численными методами, включая ме­тоды случайного поиска и генетический алго­ритм [14, 15], и потребовало разработки про­граммного обеспечения большого объема.

При вычислениях учитывался убыва­ющий характер спектральной плотности по­рождающей функции, вместо выражения (14) использовалось (15) для Κ¹⁰_и(ω). Для вычис­лений по выражению (15) была решена задача спектрального анализа порождающей функции при локальной полиномиальной сплайн-интер­поляции в общем виде [16].

Отметим также, что дополнительное привлечение взаимосвязей (13) позволяет сок­ратить количество параметров задачи.

Некоторые квазиоптимальные локальные полиномиальные сплайн-базисы

При полиномиальной сплайновой интерполя­ции первичный базис образован степенными функциями w_k(t) = t^k, k = 0, N -1, где N определено (7). Порождающие функции опти­мальных интерполяционных сплайн-базисов при К_и,_доп = 0,001 для интерполяции поряд­ка M = 1, 2, 3 и степеней гладкости r = 1, 2 приведены в таблице. Там же даны значения граничных частот в нормированных едини­цах. Графики коэффициентов искажения по­казаны на рис. 3. Номера линий на рис. 3 со­ответствуют номерам, указанным в крайнем правом столбце таблицы.

Заключение

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

Численно-аналитическими методами по­лучены квазиоптимальные решения поставлен­ной задачи синтеза оптимального интерполя­ционного сплайн-базиса в виде порождающих функций фундаментальных интерполяцион­ных полиномиальных сплайн-базисов при ин­терполяции порядка M = 1, 2, 3 и степенях гладкости r = 1, 2. Даны практические рекомендации по их использованию: допустимые искажения обеспечиваются, если максималь­ная частота в спектре сигнала не превышает граничной частоты коэффициента искажений.

Рассматриваемые методы интерполяции доведены до уровня практической реализации и могут быть выбраны соответственно специ­фике решаемой задачи с учетом взаимосвязи объема вычислений и граничной частоты ко­эффициента искажений. Так, для увеличения граничной частоты желательно увеличивать степень гладкости и порядок локальной ин­терполяции, однако это требует и б0льшего объема, и повышенной точности вычислений.

За рамками статьи остался поиск опти­мальных локальных полиномиальных сплайн- базисов при более высоких порядках локаль­ной интерполяции и степенях гладкости.