Сходимость итерационного метода восстановления неравномерно дискретизованного сигнала

Сходимость итерационного метода восстановления неравномерно дискретизованного сигнала

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

Курахтенков Л.В.,

м. н. с.,

lkurakhl@srd.mtuci.ru

Постановка задачи

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

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

Для простоты будем считать: /":[0,1]—>М,

|/(/)|<Л при некотором А> 0, зирр /с [-0,0]. Имеется разбиение отрезка [0,1 ]: 0 = </дг = 1,

такое что 7/+1 — А/, I = Кроме того опре-

делено множество индикаторов перегрузки {у( }; , такое что

О, при /(';) = У'Ы-А’*

V, = • А, при /(*,)> А;

-А,при/(*,)<-А.

При аппроксимации предполагается, что функция / периодически продолжается за пределы отрезка [0,1],

так что фактически функция предполагается равной тригонометрическому многочлену степени О с периодом 1:

/(О = Х(Л» ™{2™)+Ьп еои(2яп)) = X

л=0

Такая аппроксимация сразу дает набор значений для спектра сигнала.

Аппроксимация сигнала тригонометрическим многочленом

В предположении известной ширины спектра сигнала, возможно восстанавливать отсчеты, в которых произошла перегрузка с помощью следующего итеративного метода [1].

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

Шаг 1. Для каждой серии пропущенных отсчетов tm+|( найти три точки, такие что значение сигнала

в этих точках определено. Естественным образом находятся две точки из границ пропущенного интервала (т-\^т*к* *0,т * N-к. В качестве третьей точки

можно выбрать / или / , а в случае, когда эти

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

Шаг 2. По трем найденным отсчетам построить кубический сплайн и присвоить пропущенным отсчетам сигнала значения сплайна в соответствующих точках.

Шаг 3. Произвести дискретное преобразование Фурье по всем N отсчетам и получить N коэффициентов Фурье.

Шаг 4. Если все, кроме искомых О коэффициентов Фурье равны нулю, то произвести обратное преобразование Фурье и завершить выполнение алгоритма. В противном случае обнулить «лишние» коэффициенты Фурье и произвести обратное преобразование Фурье.

Шаг 5. Для тех отсчетов I, для которых у(/Л = 0

ПОЛОЖИТЬ = ДЛЯ тех отсчетов, для которых

но

у(/;) = Л, но /у А<А или =

положить /(/,) равным значению соответствующего сплайна в точке . Перейти к шагу 3.

Замечание. Условие выхода из алгоритма на шаге 4 на практике проверяет не абсолютное равенство нулю избыточных коэффициентов Фурье, а их незначительность, т.е. \/к | < е, к > О •

Для формализации данного метода введем следующие обозначения индикаторов множеств значений и частот:

/г('*) = {0’1} ' выход с индикатора перегрузки

АЦП, принимающий единицу на корректно принятом отсчете и обращающийся в ноль на перегруженном значении сигнала. В предположении известной функции f,

можно продолжить значения этой функции из множества дискретных отсчетов на всю область определения f:

Аналогичный индикатор множества обозначим для частот:

*оН =

1,м>є[-0,0]

О, и> £

/.(О.Ифл

И, наконец, в завершении У1 —й итерации, посчитаем преобразование Фурье полученной функции:

СО

У№""л'

Заметим, что функция /(/) имеет ограниченный спектр и представима в виде

Л (О - Л-і(0*

віпП/

пі

Действительно, из вышеуказанного выражения для f, имеем преобразование Фурье произведения, то есть

свёртку:

/л(/)=[г"^)еЫ’^=Ж

-Е= ]/п(^)^ = Л-,(0*-Ё=

у!2л V 2п _?а у12тг

еК'сіи’ =

1 БІїШ/

т

Оценка ереднеквадратического отклонения

Утверждение 2: Среднеквадратическое отклонение уменьшается с ростом количества итераций. Доказательство:

Рассмотрим среднеквадратическое отклонение точного решения от (/7 — 1)-й итерации:

-оо -О

Далее, множества, которые индицируют эти функции, будем обозначать 1Т и соответственно.

Введем обозначение для “ограниченного” сигнала

7(0=/(0/г(0+^-8вп(/(0) (1-/г(0) и его

1 1

преобразования Фурье 1 •

Положим начало итеративного процесса:

7,(/)=/(/).

На Л -й итерации получим:

/Л0 = ^7=

Заместим известные отсчеты:

7-(0=/-(/)+[/(0-/.(0]'/г(0=

+ | \F(w)-Fn_^(w)\~c^w =

= ||р(и’)-^-|(и,)/п(“’)|2<л'+

-Й

+ | |^Г(И/)-^Г«-1(И;)| | |^Г(И')- ^

я\[-я.а] -а

Далее,по равенству Парсеваля:

1кИ-^Н|2^=/|/(0-/,(0|2^=

-52 -»

=Л/(0-/л(0|2л+/|Л0-/Л0|2^=

>т 1^г

=1\т-/.(')•

1т

+ | |/(0-/Л0Г^>ЛД')-7.(')|2<*= ||/(0-7Л0|2^-

[4Й'Г ,т

Применив еще раз равенство Парсеваля, имеем:

00 00

Ц/М - 7, (0|2 = Л^М - *:М|2 ^

-00 -00

Таким образом,

00 оо

||/г(^)-/7„_,(^)| сЫ?> с/ы'

-00 -оо

что и доказывает утверждение.

им

Итерационные методы аппроксимации

Пусть преобразование сигнала через АЦП задается равенством у — Ох. Здесь X - неизвестный входной

сигнал, у - известный принятый сигнал, И - соответствующее преобразованию, отображение функции в функцию в непрерывном случае или последовательности в последовательность в дискретном случае. Решением этой задачи является х = О '_у, где £Г' - обратное

преобразование.

На практике описать в явном виде обратный оператор бывает сложно, а в некоторых случаях невозможно. Тем не менее, возможно найти решение в виде итерационного уравнения = Рхк, где - оператор, полученный некоторым образом из D . Кроме того, может содержать в себе некоторые ограничения на сигналы, с которыми приходится работать, например ограниченность спектра.

Такой итеративный процесс применим в случае, когда последовательность {хЛ сходится к единственному

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

При построении итеративного процесса, первым делом надо определить ограничивающий оператор С, такой что:

х = Сх,

тогда и только тогда, когда X удовлетворяет определенным свойствам. Например, в случае ограниченного по полосе непрерывного сигнала,

В этом случае, сигнал с ограниченным спектром, преобразуемый данным оператором не изменяется. Таким образом, наблюдаемый сигнал представим в виде: у = йСх.

Один из подходов по получению итерационного уравнения, получается из представления вида:

х = Сх + Л(у - йСх),

где параметр Я может быть как константой, так и функций от нескольких независимых параметров или функцией от X.

Таким образом,

х = Рх = Лу + Сх-ЛОСх = Лу + (1 - ЛО)Сх = Лу + йх >

откуда и получается итерационное уравнение:

хш=рхк=ЛУ + Схк.

Начальное условие зачастую принимают х0 = Лу,

хотя в общем случае Х() может быть любым. Выбор

параметра Л может влиять на сходимость итерационного метода.

Далее будем считать, что сигнал X и сигналы, получаемые на итерациях Хк , являются элементами полного

нормированного линейного пространства с нормой • . Предположим, что

выполняется для всех X/ и X, из некоторого замкнутого подпространства пространства сигналов. Если О < г < 1, то оператор Т7 называется сжимающим отображением, или просто сжатием на этом подпространстве. Если г = 1, то оператор называется нерастягивающим, а если г = 1, а равенство достигается только в

случае Ху = XI, то оператор г называется строго нерастягивающим.

Таким образом, расстояние между преобразованными с помощью такого оператора сигналами уменьшается.

По теореме Банаха о неподвижной точке, если оператор г является сжатием на некотором подпространстве, то он имеет неподвижную точку X. Более того, при

любом выборе начального сигнала Х0 из данного подпространства хк —> х при к —> оо.

Сходимость метода

Рассмотрим сигнал X, как вектор-столбец из П отсчетов. Введем матрицу

О = diag {/г (хк)}, 1Т (хк) = А

Тогда сигнал Ох содержит все корректно принятые отсчеты, а вместо перегруженных отсчетов имеет нули. Пусть г£(/)) = с1 - количество ненулевых элементов на

диагонали матрицы О , то есть количество корректно принятых отсчетов.

Напомним, что

/ (УИ = {1,и'е[_аП1 •

п |0,и>$£

Аналогичное обозначение введем для матрицы /п=Ля£{/п(щ)}- Пусть гк(в) = гк(1п) = 20 + 1,

то есть п -(20 + 1) частот обнулятся после преобразования В. При этом распределение нулей и единиц на диагонали будет следующим: первые О + 1 элементов будут равны единице, затем следует ц — (20 + 1) нулей,

а затем опять О единиц.

Тогда оператор ограничения спектра по частоте является композицией В = Р _1/0Р •

Утверждение 3: Если <^>20 + 1, х = (1-0)х и

Х = Вх, то д г = 0.

Доказательство:

Равенство * = (/-£))х означает, что все корректно принятые отсчеты X- = 0,такие что 1Т(^Х-) = 1 • Тогда х = ^х= V р.х,. где Р ( — I -я строка матри-

/,/г(д:/)=0

цы дискретного преобразования Фурье И . Кроме того, для /7-(2^ + 1) компонент выполняется X. — 0 при

/„(*,) = 0.

Таким образом, получим л-(2Г2 + 1) уравнений с нулевой правой частью:

X Рк1х, = хк = 0 - = 'е" » Для некоторых

*Мч)г0 77 7 V/?

индексов к .

Такая система линейных уравнений может быть определена подматрицей Р размера

(л-(2Л + 1))х(л-</), причем (/7-(20 + 1))<(л-с/), так как по условию с1 > 20. +1. С учетом распределения нулей и единиц в матрице /^, все /?-(2£1 + 1) индексов к могут быть получены как циклический сдвиг из и-(20 + 1) последовательных чисел по модулю П.

Таким образом, можно считать, что элементы

] -2жД

р —_______о и берутся для последовательных чисел

Ч 1~ л/и

к = 1,..,,(^п — (2Г2 + 1)) и умножаются на некоторую

фиксированную константу, зависящую от сдвига. Таким образом, столбцы такой подматрицы будут линейно независимыми (это будет матрица Вандермонда, умноженная на константу), а значит все некорректно принятые отсчеты XI равны нулю. Как было сказано в начале, все корректно принятые отсчеты тоже равны нулю, а значит X = 0, что и завершает доказательство.

Зададим итерационный метод аппроксимации

*(*+1> = Лс(А) = Лу + (1- ЩВх

.<*)

Утверждение 4: При Яє[0,2] уравнение х = Рх

имеет решение.

Доказательство:

Для начала докажем нерастягиваемость оператора Р. Она зависит только от нерастягиваемости оператора

(/ — ЯО) В  Действительно при любом сдвиге Лу будет выполнено:

Рх{,) - Рхи,\\ =

|Лу + (І- ЩВх(і) - [Лу + (I - Лй)Вхи)) = = ||(/-/Ш) Вх(і) - Лу + (/ - Лй) &с0)||,

то есть Р и (/-ЯD)Z? нерастягивающие или растягивающие одновременно.

Нерастягиваемость оператора В следует из унитарности матрицы дискретного преобразования Фурье и

нерастягиваемости матрицы /<•, проекции на подпространство. Таким образом, оператор Р будет нерастя-гиваемым, если (/ — ЯО) является нерастягиваемым.

Это выполняется при Я е[0,2], так как только в этом

случае собственные значения I — Л будут находиться в пределах единичного шара.

Нерастягиваемость Р доказана.

Так как Р является непрерывным, нерастягивающим, и отображает непустое компактное замкнутое подпространство в себя, то у него есть неподвижная точка. Утверждение 5: В указанных обозначениях, пусть

с/ > 2Г2 + 1, а Я е(0,2). Тогда оператор Р является

строго нерастягивающим и имеет единственное решение, которое задается как

х = НтРпх^°К

п->00

, (°) для любого X .

Доказательство:

Предположим обратное: пусть выполняются требования с! > 20 + 1 и Я е(0,2), но оператор Р не является строго нерастягивающим. Тогда существует ненулевой вектор у = х^ — х^ Ф 0, такой что:

Рх{() - Рх

(Л

Так как оператор В проецирующий, из равенства норм ||5у|| = ||у|| следует равенство самих векторов:

Л

Ву = у. А значит, (л-(20 + 1)) компонент V равны нулю. Но тогда из равенства

7-Я£>)у||= /(1-Я)2 X X у^ =

V *.Му»Н './г(»',)=о

= І X у* + X ^~2Л X уї+л2 X =

'.Му/Н

= Л/|МГ-Л(2--г) I •?-

V 1-і

следует, что V = 0 при /г ( у.) = 0. Тогда к вектору V можно применить утверждение 2, из которого следует что V = 0 - противоречие.

Значит оператор Р является строго нерастягивающим и имеет единственную неподвижную точку, которая и является пределом описанного итеративного процесса.

На практике скорость сходимости зависит от начального приближения. В качестве него можно выбрать:

1. сигнал с известными отсчетами на своих местах и нулями вместо перегруженных отсчетов;

2. сигнал с известными отсчетами на своих местах и максимумом с соответствующим знаком вместо перегруженных отсчетов;

3. сигнал с известными отсчетами на своих местах и интерполированными отсчетами в пропущенных сегментах.

Оценка количества арифметических действий

На каждой итерации производится два дискретных преобразования Фурье, которые выполнимы за

2-п \о%(п) + 2 (20+ 1)1<^(2Й +1) умножений и

3-/7-к^(я) + 3-(20 + 1)-1о§(20 + 1). Для получения

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

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

ЛИТЕРАТУРА

1. Курахтенков Л.В. Новые методы интерполяции сигнала с нерегулярной дискретизацией и их применение // T-Comm, 2010.-№11.

2. Аджемов С.С., Курахтенков J1.B., Романов Э.Ю. Задача интерполяции сигнала с нерегулярной дискретизацией // Т-Comm, 2009. - №4.

3. Курахтенков Л.В. Особенности применения методов интерполяции сигнала с нерегулярной дискретизацией // Т-Сошш, 2011.-№П.

4. Landau Н. Necessary density conditions for sampling and interpolation of certain entire functions // Acta Math., 1967

5. Landau H.J., Poliak H.O. Prolate spheroidal wave functions // Fourier Analysis and Uncertainty - II. Bell Syst. Tech. J.1961. -Vol.40. - P.65-84

6. Комаров И.В., Пономарев Л.И., Славянов С.Ю. Сфероидальные и кулоновские сфероидальные функции // М.: Наука, 1976.

7. Хургнн Я.И., Яковлев В.П. Методы теории целых функций в радиофизике, теории связи и оптике// М.: Физматгиз, 1962.