WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 43 |

Теорема 1. Для последовательности Y длины L 2(n + 1), члены которой являются равноотстоящими отсчетами полиномиальной функции одного переменного yi = pn(i) = 0 · in + 1 · in-1 +... + n, 0 = 0, и заданы любые n + 1 подряд идущих члена ym, ym+1,... ym+n, существует единственный рекурсивный цифровой фильтр порядка n + 1 (M = n + 1, N = n), импульсная характеристика которого совпадает с Y.

Доказательство. Часть 1. Пусть m = 0, а отсчеты функции берутся с шагом равным единице. Формула цифровой фильтрации имеет вид N M yn = bkx(n - k) - aky(n - k), (1) k=0 k=где ak и bk действительные коэффициенты. Большее из чисел M и N называется порядком фильтра. Примем N = M - 1 (таким образом, количество коэффициентов ak и bk будет равным) и построим начальную систему уравнений для M + N + 1 первых элементов последовательности Y, приняв её за импульсную характеристику искомого ЦФ. Матрица системы имеет вид:

214 Д. А. Никитин 1 0 0... 0 0 0... 0 0 1 0... 0 -pn(0) 0... 0 0 0 1... 0 -pn(1) -pn(0)... 0........

..

..........

..

........

0 0 0... 1 -pn(n - 1) -pn(n - 2)... -pn(0) P =.

0 0 0... 0 -pn(n) -pn(n - 1)... -pn(1) -pn(0) 0 0 0... 0 -pn(n + 1) -pn(n)... -pn(2) -pn(1)........

..

..........

..

........

0 0 0... 0 -pn(2n - 1) -pn(2n - 2)... -pn(n) -pn(n - 1) 0 0 0... 0 -pn(2n) -pn(2n - 1)... -pn(n + 1) -pn(n) Разделим матрицу P на 4 равных части, как показано выше, и приведём её эквивалентными преобразованиями к верхнему треугольному виду.

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

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

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

Будем нумеровать строки и столбцы с нуля.

1а) отнять n-й столбец из всех столбцов с нулевого по (n - 1)-й;

1б) отнять нулевую строку из всех строк с первой по n-ю;

2а) отнять (k + 1) раз (n - 1)-й столбец из всех столбцов с нулевого по (n - 2)-й, где k разность индексов столбцов;

2б) отнять (k + 1) раз первую строку из всех строк со второй по n-ю, где k разность индексов строк;

k + 3а) отнять (k + 1) раз (n - 2)-й столбец из всех столбцов с нулевого по (n - 3)-й, где k разность индексов столбцов;

k + 3б) отнять (k + 1) раз вторую строку из всех строк с третьей по n-ю, где k разность индексов строк;

Рекурсивные цифровые фильтры с импульсной характеристикой k + 2 k + 4а) отнять (k + 1) раз (n - 3)-й столбец из всех столбцов с 2 нулевого по (n - 4)-й, где k разность индексов столбцов;

k + 2 k + 4б) отнять (k + 1) раз третью строку из всех строк с четвёртой 2 по n-ю, где k разность индексов строк;

и так далее, n раз (до 1-го столбца и (n - 1)-й строки).

Таким образом, получим -pn(n) -pn(n - 1)... -pn(1) -pn(0) -pn(n + 1) -pn(n)... -pn(2) -pn(1)....

.

.....

Z =.

....

-pn(2n - 1) -pn(2n - 2)... -pn(n) -pn(n - 1) -pn(2n) -pn(2n - 1)... -pn(n + 1) -pn(n) zn(A) zn-1(A)... z1(A) z0(A) 0 zn(A)... z2(A) z1(A)....

.

.....

, где A = 0, 1,..., n.

.

....

0 0... zn(A) zn-1(A)) 0 0... 0 zn(A) То же самое справедливо и для системы с б ольшим количеством уравнений:

zn(A) zn-1(A)... z1(A) z0(A) 0 zn(A)... z2(A) z1(A)....

.

.....

.

....

0 0... zn(A) zn-1(A)) Z =.

0 0... 0 zn(A) 0 0... 0....

....

....

0 0... 0 То есть матрица является верхнетреугольной, так как она теплицева и zi,0 = = 0, i > 0.

Рассмотрим теперь расширенную матрицу такой же системы уравнений.

Аналогично будем рассматривать только четвёртый квадрант матрицы:

-pn(n) -pn(n - 1)... -pn(1) -pn(0) pn(n + 1) -pn(n + 1) -pn(n)... -pn(2) -pn(1) pn(n + 2).....

.

......

Z =.

.

.....

-pn(2n - 1) -pn(2n - 2)... -pn(n) -pn(n - 1) pn(2n) -pn(2n) -pn(2n - 1)... -pn(n + 1) -pn(n) pn(2n + 1) Переместим сначала последний столбец на первое место и умножим его на минус один, чтобы матрица стала теплицевой, а после этого произведём 216 Д. А. Никитин над ней точно такие же преобразования, что и над матрицей Z. Получим следующий результат:

-pn(n + 1) -pn(n) -pn(n - 1)... -pn(1) -pn(0) -pn(n + 2) -pn(n + 1) -pn(n)... -pn(2) -pn(1).....

.

......

Z =.

.....

-pn(2n) -pn(2n - 1) -pn(2n - 2)... -pn(n) -pn(n - 1) -pn(2n + 1) -pn(2n) -pn(2n - 1)... -pn(n + 1) -pn(n) 0 zn(A) zn-1(A)... z1(A) z0(A) 0 0 zn(A)... z2(A) z1(A).....

.

......

.

.

.....

0 0 0... zn(A) zn-1(A)) 0 0 0... 0 zn(A) Действительно, так как результирующая матрица является теплицевой, значит все элементы zi,0 = 0, i 0, как и все поддиагональные элементы матрицы Z.

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

0 zn(A) zn-1(A)... z1(A) z0(A) 0 0 zn(A)... z2(A) z1(A).....

.

......

.

.....

0 0 0... zn(A) zn-1(A)) Z =.

0 0 0... 0 zn(A) 0 0 0... 0.....

.....

.....

0 0 0... 0 То есть ранги матриц системы равны. Из вышеприведенного алгоритма нетрудно посчитать, что zn(A) = -n!0. Таким образом, система обладает полным рангом при 0 = 0, что соответствует условию теоремы.

Следовательно, она имеет единственное решение: коэффициенты цифрового фильтра порядка n + 1.

Пока что доказана справедливость теоремы только для случая, когда Y является последовательностью отсчетов полинома степени n, взятыми с шагом равным единице. Покажем, что она справедлива и в случае любого постоянного шага:

yi = j · (i · step)n-j = (j · stepn-j) · (i)n-j = j · in-j, j j j i = 0, L - 1, j = 0, n, step = 0.

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

Часть 2. Пусть m > 0. Для любых n + 1 фиксированных точек существует единственный многочлен степени n, проходящий через них.

Следовательно, зная yi, i = m, m + n, можно построить систему уравнений j · mn-j = ym j j · (m + 1)n-j = ym+j...

j · (m + n)n-j = ym+n.

j Данная система имеет единственное решение относительно j для фиксированного m > 0. Значит, если фиксированы yi, i = m, m + n, то фиксированы коэффициенты полинома j. А если фиксированы коэффициенты полинома, то фиксированы yi, i = 0, n, так как они однозначно выражаются через коэффициенты полинома. Следовательно, доказательство в части 1 данной теоремы справедливо и при m > 0.

Следствие 1. Для синтеза рекурсивного ЦФ, импульсная характеристика которого описывается полиномом степени n, достаточно 2(n + 1) подряд идущих элементов ИХ. Количество коэффициентов и прямой и обратной связи получаемого фильтра при этом равно n + 1.

При попытке доказательства были рассмотрены также случаи, когда количества коэффициентов ak и bk не равна, то есть N = M - 1. Однако, если M < n + 1 или N < n, то решение не существует. А если M n + и N n, то решение существует, но все последние коэффициенты ak или bk с порядковым номером свыше n (если нумеровать с нуля) оказываются равными нулю. То есть такое решение совпадает с доказанным выше.

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

Предположение 1. Коэффициенты обратной связи цифрового рекурсивного фильтра с импульсной характеристикой, описываемой полиномом n-ой степени, не зависят от коэффициентов полинома и совпадают с элементами (n + 1)-ой строки треугольника Паскаля с 218 Д. А. Никитин Таблица Зависимость коэффициентов bk от параметров описывающего полинома Формула i-го члена Коэффициенты bk Степень ИХ полинома b0 = 0 + 1 yi = 0 · i + b1 = -b0 = 0 + 1 + 2 yi = 0 · i2 + 1 · i + 2 b1 = 0 - 1 - b2 = b0 = 0 + 1 + 2 + b1 = 40 - 22 - 3 yi = k · ik b2 = 0 - 1 + 2 + k=b3 = -b0 = 0 + 1 + 2 + 3 + b1 = 110 + 31 - 2 - 33 - 4 yi = k · ik b2 = 110 - 31 - 2 + 33 + k=b3 = 0 - 1 + 2 - 3 - b4 = отброшенным первым элементом, умноженными на (-1)k, где k порядковый номер коэффициента k ak = (-1)kCn, k = 1, n + 1. (2) Например, если элементы импульсной характеристики описываются полиномом 2-го порядка, то коэффициенты ОС соответствующего ЦФ равны –3, 3, –1. Для полинома 3-ей степени: –4, 6, –4, 1. Для полинома 4-й степени: –5, 10, –10, 5, –1. И так далее. Это свойство было использовано в других работах автора при разработке алгоритмов сжатия данных и анализа последовательностей в целях поиска участков данных, которые можно описать полиномом, и сокращения размера данных после обработки [4–6].

Предположение 2. Коэффициенты обратной связи цифрового рекурсивного фильтра с импульсной характеристикой, описываемой полиномом n-ой степени, взаимно однозначно связаны с параметрами описывающего полинома. Можно из j, j = 0, n, получить ak или bk, не производя громоздких вычислений, приведённых выше при доказательстве, и обратно, можно по коэффициентам синтезированного фильтра восстановить вид полинома, описывающего элементы его импульсной характеристики.

Это свойство также было использовано в [4–6].

В табл. 1 приведены примеры зависимостей коэффициентов прямой связи ЦФ от параметров полинома, описывающего его импульсную характеристику. Видно, что выражения в 3-ем столбце табл. 1 составляют Рекурсивные цифровые фильтры с импульсной характеристикой Таблица Зависимость параметров полинома от коэффициентов bk соответствующего фильтра Формула i-го члена Выражения для вычисления Степень ИХ параметров полинома 0 = b0 + b1 yi = 0 · i + 1 = -bb0 + b1 + b0 = 2 yi = 0 · i2 + 1 · i + 2 1 = b0 - b1 - 3b2 = bb0 + b1 + b2 + b0 = b0 - b2 - 2b1 = 3 yi = k · ik k=0 2b0 - b1 + 2b2 + 11b2 = 3 = -bb0 + b1 + b2 + b3 + b0 = 3b0 + b1 - b2 - 3b3 - 5b1 = 11b0 - b1 - b2 + 11b3 + 35b4 yi = k · ik 2 = k=3b0 - b1 + b2 - 3b3 - 25b3 = 4 = bсистему линейных уравнений, поэтому не составляет труда вычислить обратные зависимости параметров полинома от коэффициентов фильтра (табл. 2).

Приведённая теорема расширяет доказательную базу для синтеза БИХ-фильтров только по импульсной характеристике, а кроме того даёт алгоритм для расчёта таких фильтров по импульсной характеристике, если известно, что её отсчеты точно подчиняются произвольной полиномиальной зависимости известной степени. Данный алгоритм в отличие от классических аналогов не является численным итерационным процессом поиска аппроксиманта и всегда даёт точное единственное решение. Для ясности повторим основные шаги алгоритма:

(1) Пусть отсчеты ИХ искомого БИХ-фильтра являются значениями алгебраического полинома степени n, взятыми на равномерной сетке.

Возьмём любые 2(n + 1) подряд идущих отсчета.

220 Д. А. Никитин (2) Составим из них, используя уравнение (1), систему линейных алгебраических уравнений с 2(n + 1) неизвестными (M = n + 1, N = n).

(3) Далее решаем СЛАУ. Решать можно любым классическим способом, либо методом Гаусса с приведением к треугольному виду (прямой ход), используя описанный выше алгоритм приведения тёплицевой матрицы специального вида к треугольному виду.

(4) Решение системы содержит 2(n + 1) значений. Из них первые n + коэффициенты прямой связи фильтра (bk), а оставшиеся n + коэффициенты обратной связи (ak).

Полученный ЦФ будет неустойчивым, так как полином расходящаяся функция. Тем не менее, есть возможные приложения, не связанные с использованием полученного фильтра для фильтрации. Это анализ данных, сжатие, и другие, описанные в [6]. Кроме полиномиальных функций подобные теоремы доказаны автором для синусоидальных и показательных функций, а также для случая, когда отсчеты импульсной характеристики являются значениями любой периодической функции, взятыми с постоянным шагом при условии, что период функции кратен расстоянию между взятыми отсчетами. Формулировки теорем, касающихся этих видов описывающих функций, можно найти в [7].

Список литературы 1. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов.

М.:Мир, 1978. 848 с.

2. Марпл мл. С.Л. Цифровой спектральный анализ и его приложения. М.: Мир, 1990. 547 с.

3. Завьялов М.Н., Елизаров Д.В. Комбинированный вариант гармонического разложения Прони // Журн. СФУ. Сер. Матем. и физ. 2008. №1(4). C.443–452.

4. Ханов В.Х., Никитин Д.А. Алгоритм анализа числовых последовательностей // Вестник СибГАУ. 2006. №6(13). С.11–15.

5. Никитин Д.А. Сжатие с использованием поиска функциональных зависимостей // Технологии Microsoft в теории и практике программирования:

конф.-конкурс. НГУ. Новосибирск, 2007. С.133–135.

6. Никитин Д.А. Приложения алгоритма синтеза рекурсивных цифровых фильтров по импульсной характеристике // Цифровая обработка сигналов.

2009. №4. C.8–15.

7. Никитин Д.А. Теоремы о существовании и порядках цифровых рекурсивных фильтров с импульсными характеристиками определённой формы // Информационные технологии и математическое моделирование (ИТММ-2009): матер. VIII Всероссийской научно-практической конф. с междун. участием.Томск: ТГУ, 2009. Ч.2. С.144–146.

Рекурсивные цифровые фильтры с импульсной характеристикой Никитин Дмитрий Александрович (nikitin.bit@gmail.com), старший преподаватель, кафедра безопасности информационных технологий, Сибирский государственный аэрокосмический университет им. акад. М.Ф.

Решетнёва, Красноярск.

Pages:     | 1 |   ...   | 20 | 21 || 23 | 24 |   ...   | 43 |



© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.