автореферат диссертации по информатике, вычислительной технике и управлению, 05.13.16, диссертация на тему:Разработка методов цифровой обработки сигналов на основе биортогональных рядов Чебышева-Маркова

КАЗАХСКИЙ • ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ АЛЬ- ФАРАБИ

РАЗРАБОТКА МЕТОДОВ ЩФРОВОШ ОБРАБОТКИ СИГНАЛОВ НА ОСНОВЕ БШРТОГОНАЛЬШХ РЯДОВ ЧЕШШЕВА- МАРКОВА

05.13.15 - Применение шчиелитольвой техники, математического моделирования и математических катодов в научных исследованиях. ■<

На правах рукописи

Ча Валерий Леонидович

уда 51Э.677

Автореферат диссертации на соискание ученой степени кандидата" физика- математических наук.

АЛМА- АТА . 1991

Работа выполнена в Институте теоретической и прикладной математики АН КазССР •

Научный руководитель: академик АН КазССР, доктор технических наук, профессор АМЕРБАЕВ В.М.

Официальные оппоненты: доктор технических наук ВЕСЕЛОЕ В.Е.

кандидат физико-математических наук АМАНОВ Н.Т.

Ведущая организация: НПО ЭЛАО

Защита состоится " ^ " ¿¿¿¿^/ч' 1991 г. в '¿С часов на заседании специализированного совета К 058.01.16 при Казахском государственном университете ©дани Аль- Фараби по адресу: 480012, г. Алма- Ата, ул. Масанчи, 33/47, в ауд.: 316

Отзчвы на автореферат направлять по адресу:

480121, Алма- Ата, Тимирязева, 46, Казахский государственный

университет, ученому секретарш

С диссертацией шико ознакомиться в библиотеке университета. Автореферат разослан " " ¿¿он-1991 г.

Ученый секретарь специализированного совета

• ЖЕРЕБЯТБЕВ И.Ф.

Актуальность. Цифровая обработка сигналов (ЦОС) широко применяется для решения сложных задач радиолокации, связи, сейсмологии, оптики, радиоастрономии, томографии и других областей науки и техники. Многие методы ЦОС основаны на спектральном анализе и синтезе. Б настоящее время в этой области существует большое число алгоритмов (БПФ, Винограда, Уолта-'Адэмара, теоретико- числовых преобразования и др.). При этом во многих практических задачах перед алгоритмами ЦОС предъявляются такие требования как необходимость обработки данных в режиме реального времени, минимальность аппаратурных затрат, простота технической реализации. На практике часто возникает проблема цифровой обработки больших массивов данннх, решение которой известными методами является затруднительным или невозможным. Так в обработке изображений, дельта- модуляции и других существует необходимость обработки сигналов, заданиях с частотой дискретизации существенно большей минимальной частоты по критерию Шеннона- На&свиста. Такое положение препятствует создании высокопроизводительных систем обработки сигналов. Поэтому для решения этой задачи становится необходимым создание и исследование принципиально нознх численных методов Фурьэ- анализа и синтеза.

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

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

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

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

порядок убывания на бесконечности коэффициентов Чебышева-Маркова и Фурье является одинаковым, что является важным для повышбния вычислительной эффективности процедур поэтапного сжатия информации.

Известен (А.В.Калинин, Б. Л. Швов аров) рекуррентный способ вычисления коэффициентов Фурье, основанный на известном разложении прямоугольного синуса и косинуса. Однако ими предложено проводить вычисления по формуле, погрешность которой является значительной.

В диссертационной работе на основе применения кусочно-постоянной интерполяции построен метод вычисления коэффициентов биортогонального ряда Чебкшева- Маркова и коэффициентов Фурье. Особенностью этих методов является то, что необходимое число операций умножения имеет порядок O(N). Получены оценки погрешности метода. Показано, что дисперсия погрешности вычисления коэффициентов Чебшпева- Маркова, вызванная "белым" пу-мом, имеет порядок 0(N~1). Предложенный метод является простым для реализации и организации по нему параллельных вычислений, требует линь операций умнонения и сложения действительных чисел. ,

Построен аналог биортогснальных систем Чебншева- Маркова дискретной переменной, вычисление коэффициентов которых происходит в базиса дискретных прямоугольных тригонометрических функций. Такие преобразования привлекали внимание специалистов ЦОС 'fА.В.Калинин, Б.Л.Пивоваров, Э.Е.Дагман, Г.А.Кухарев, О.К.Эрсоу, В.Г.Дзюбан), в связи с тем, что они требуют лишь операций слокения.и сдвига. В связи с этим их техническая реализация может оказаться очень простой. В диссертации такие преобразования рассмотрены с позиции использования биортого-

Отмзтнм,-что чебышевская идея построения биортогональ-ных систем и радов была использована в теоретических работах А.А.Маркова,Н.П.Романова и других. Однако вопросы практического применения таких рядов в них не рассматривались.

Таким образом, задача построения простых и эффективных алгоритмов спектрального анализа и синтеза, основанных на использовании биортогональных рядов Чебышева- Маркова, определяется запросами теории и практики и является актуальной.

Целью работы является исследование вопросов практического применения биортогональных рядов Чебышева- Маркова и разработка на основе таких рядов алгоритмов спектрального анализа с меньшей сложностью вычислений .

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

Научная новизна. В настоящее время известен подход к вычислении коэффициентов Фурье, основанный на применении известной в теории чисел формулы обращения Мебиуса к различным модификациям формула суммирования Пуассона. Такой метод рассматривался в работах Р.Р.Голдберга и Р.О.Варги, Ж.Н. Линнеса, В.М.Амербаева и Н.А.Утембаева, И.О.Рида, Д.В.Тафтса, Г.Садасива и др.

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

нальных систем Чебшева- Маркова, что позволяет получить новые представления для ДПФ и тригонометрического интерполяционного полинома в виде дискретного аналога биортогонального ряда Чебыпова- Маркова. Вычисления по таким представлениям происходит по 2 последовательным этапам, один из которых являет собой дискретное прямоугольное преобразование, другое-умножение на матрицу блочно- диагонального вида с большим числом нулей.

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

Апробация работы. По теме диссертации были сделана доклада па семинарах и конференциях ИМИ АН КазССР, международной конференции "Высокопроизводительные вычислительные системы в управлении и научных исследованиях", Алма-Ата, 1591, семинаре под рук. проф. Лукьянова А.Т.

Публикации. Основные результаты опубликованы в 4 работах.

Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения, списка литература и приложения, изложена на 134 страницах машинописного текста

а

и включает 6 рисунков и 12 таблиц. Список использованной литературы содержит 56 наименований.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Для вычисления высокочастотных коэффициентов Чебышева-Маркова применено преобразование Лонгмана и получены оценки погрешности этого метода. Получены новые биортогональ-нне системы функционалов типа сумм Римана и систем, связанных с полиномами ЧеСшаева I- го и 2- го родов, а так же теоремы сходимости соответствующих биортогональных радов.

Вторая глава посвящена построению даскрвтнкх аналогов биортогональных систем Чебшэва- Маркова к ортогональных

Н.П.Ромаяова. -

На основа применения результатов в теории чисел получены следующие результаты.

Теорема 2.2.2. Система функций jslgn sin Zx 2S,

биортогональна на отрезке £Q,N-11, т.е. справедииво равенство

N-1

2 V sign sin Z% -в, Nnf0 N N

1 , |K-l|jj«= О

-1 , fk+-l|N* О (I) О , иначе

1Í-1

'Э, (s)= Y tlU.k) sin 2тс Ш , 1н ¿0 Н г](1,к)- линейная комбинация теоретика- числовых рядов, связанных с функцией Мебиуса.

Теорема 2.2.3. Система функций (sign cos 2% —, Ъ(-)1

i и А н J

биортогональна на отрезке Ш,П-1], т.е. справедливо равенство

N-f • Г 1 , О'

I I aisi соз Z% Ш J t , |it+ilr о ~(2> H n=0 - { О , иначе

N-1

Tl(S)== 1 003 г% — 11 k=o

Получены новое представление ДПФ и григоноштрического интерполяционного полином. Справедливы следующие формулы.

К-1 а-Г

% = Рп 003 & \ = sto 2% Щ, (3)

IT—"f ,■•-''".'

P«i- I tj(n.t)í(i) и-""-, ' Г--1=0 н

В случае К- 2В, ш > .1 рд имеет представление в виде цтшпо-

ской свертки.

- N '

21+2 х а N d=0 11

г : • р,.21ез,н-г 2о(8^я)

1= , 3= O.....H/2l+2-1

pH(t)= f(|), P0<t)= f(0) 2

ОСЕ-*-?- К) - теоретико- числовой ряд, зависши от функции Ыебиуса, е= -3.

Формулы (3)- (4) выражают 2- этапное представление дав, на первом этапе которого происходит умножение последовательности í(-) на матрицу блочно- диагональной структуры с большим К

количеством нулей. 2- а вгап представляет собой дискретное преобразование Чебшева- Маркова, которое не требует операций умножения.

Получено новое представление для тригонометрического интерполяционного полинома..

N-1

pH<t>M 1 °п <5)

п=0

... И-1

i Jt(h (Siga coa Z% & - i sign sin Z% Si) N feaн ' и N

ín(t ег1сШЪ

: К=0

Для случая N* 2m, m > 1 аналогично (4) имеет место црадстав-

ление функций En(t) в виде циклической свертки.

Получены также дискретные аналоги ортогональных систем Н.П.Романова, которые тесно связаны с функцией Мебиуса и дискретном тригонометрическим базисом. Полученные результаты могут найти применение в проектировании цифро- аналоговых устройств обработки информации. Процесс обработки разделен на 2 этапа. На одном выполняются только операции сложения, которые легка реализуются в аналоговой часта процессора. На другом этапе происходит вычисление циклических сверток "быстрыми" методами. Такая реализация вычисления ЯПФ и интерполяционного полинома обладает большей простотой реализации.

Третья глава посвящена построению и исследовании методов численного Фурьэ- анализа, основанных на применении биортого-налышх коэффициентов Чебьплева- Маркова и Фурье. Количество необходимых операций умножения а них имеет порядок 0(N), что шкет принести существенный ваягрша по сравнению с БПФ, и основную доли.в вычислительная затратах будут занимать элементарные операция сложения и сдвига.

Синусный коэффициент Чебышвва- Ивркова имеет следухщий

вид

1

Вд* S * sign sin 2ira dx (6)

O

Вд можно иначе представить в вадэ знакопеременной суммы конечных кнтегралоз

1+1

2п-1 211

J (-1 J1 J fU) to Ю

1=0 JL

2п _

Пусть í(t) задана в точках —— , 1» 0.N-1 отрезка

К

£0,13 и выполнено условие' 2n ¡S К . Граяячные точки з (?)

го= 0,2п-1 принадлежат отрезкам

V1 1

'—у

При П0М0П51

Й " '

2п

кусочно- постоянной интерполяции получено следующее прибли- • «энное представление синусного коэффициента Чебынева- Маркова

где

'1- Н'ФV

н^гп» гп 'ю=1 н^ (К>П) + I1 г: 5 1 *

где

Ь ■ ■ I .г

1=1 й

(Н,п>- множество таких ю, для которых принимает

значение . Очевидно, для вычисления Вп необходимы 4

операции умножения. В случае, когда К является степенью 2, требуемое количество операций умножения равно 2. Структура прэдокенаого способа не зависит от представления чисел п и N в виде произведения сомножителей, что характерно для алгоритмов ЕПФ. При атом для организации параллельных вычислений важно, что каждый коэффициент Вп может вычисляться независимо.' Аналогичный метод построен для вычисления косинусных ко-еффициентов Чебышева- Маркова.■

На основе применения формулы обращения Мебиуса разработан метод переходя от коэффициентов Чебышьа- Маркова к коэ<£>-

фациентам Фурье. На основе этого получен 2- этапный метод вычисления синус- коэффициентов Фурье. Пусть требуется вычислить М коэффициентов Фурье, причем выполнено неравенство

Ы <

1 этап, Вычисление коэффициентов Чебышева- Маркова ступенчатой функции по "быстрому" методу, изложенному выше и их масштабирование по формулам

А_= А_/п , п=1,М

™ _ __(9)

Вп= Вп/г» , п=1 ,М

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

2 этап. Вычисление коэффщиентов Фурье по формулам

n I In

V S I ц(1)%(1) А^. bn= 2Е I ц(1)Х2(1) В1п, (10)

4 1=1 ' 4 1=1

п=1,Ы, ц(т)- функция Мебиуса,

Х(т)=

(т-1)/2 ' (-1) .га- нечетное

О , ш- четное

Общее число операций умножения на этом этапе равно 2М. Общее количество операций умножения равно 10 И. Так как М < {"]» то

количество требуемых умножений имеет асимптотику 0(H).

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

Георема 3.2.1. Пусть f(t) « С(2)Ю,13 и Г(1-) « i(0+). Тогда справедливо неравенство

Л.

2

IV bnt < + — тЩ + 7)] 1Г

:-2

(И)

М 3) , гм^-3

гш

Л-(3>= 2 ГЗ

П=1П

Аналогичная теорема получена для косинусных коэффициентов. Теорема 3.2. неравенство

Теорема 3.2.2. Пусть f(t) е . Тогда справедливо

^ 12 - " ' . да)

Для погрешности аппроксимации функции - а0 тригонометрическим полиномом степени М, коэффициенты которого вычислены по предложенному метода, справедлива следующая теорема. Теорема 3.2.3. Пусть ГШ в С(2>[0,13 и 1(1-) =1(0+). Тогда

справедливо неравенство

А.

•2

|f(t) - f(t)i < iffl[ А,М + — (ШЩ + 7)] If2 + (13)

J • (2%) Получены оценки погрешности метода, вызванной "балым" шумом. Пусть на Функции наложен,"белый" шум s(n) с нулевым матожида-ниеы Ets(n)) и дисперсией, равной о2.

г о2,^

Е£б<п)е(ЮЬ | 0 >kj¿n (14)

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

ному методу, имеем следующую оценку где 7- константа Эйлера.

Тагам образом, показано, что среднеквадратичэсиая погрешюсть вычисления коэффициентов Фурье имеет порядок 0(Ii"'/2ln(M/n)).

Аналогичные результаты получат для метода вычисления косинусных коэффициентов.

Предложенный метод был применен для обработки данных приборов с зарядовой связью (ПЗС). Получены оценки погрешности метода.

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ГЛБОТН

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

1. Получеки поше йиортогшальше система функционалов типа сумм Ргалака я функций го полиномам Чэбшова I- го и 2- го родов. Доказаны теоремы сходимости рядов по этим системам.

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

сти формул обращения, основанных на коэффициентах Чебше-ва- Маркова, является болъшм, чем у аналогичных, основанных на формуле суммироваг 'я Пуассона.

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

4. Получены новые биортотональные и ортогональные системы дискретной переменной, являющиеся аналогами соответствующих систем Чебышева- Маркова и Н.П.Романова непрерывной переменной. На основе их применения получены новые выражения до} ДПФ и полинома тригонометрического интерполирования через коэффициенты даскредаого преобразования Чебыщева-Ыархова. Вычисление этих коэффициентов не требует операций умножения, что имеет ванное практическое значение.

6. Еа основе применения ступенчатой интерполяции разработан

■ новый метод вычисления коэффициентов Чебышева- Маркова с

числом операций умножения порядка О (Н).

е. На основе применения формулы обращения Мебиуса разработан способ перехода от коэффициентов Чэбшева- Маркова к коэффициентам _ Фурье с числом операций умножения порядка О(И). Получены'оценки погрешности предложенного метода численного Фурье- анализа. Показано, что дисперсия погрешности, вызванной вжяиием "белого" шума, обратно пропорциональна числу входных данных К.

7. На основе представленного метода Фурье- анализа построен метод обработки сигналов ГОС о числом операций умножения порядка О(Я). Получены оценки погрешности этого метода.

8. Разработаны программные реализации предложенных методов н языке Фортран- 4. Результаты численных экспериментов пока

т их эффективность для решении задач цифровой обработки сигналов.

Основные положения диссертации опубликованы в следующих работах:

1. Ча В.Л. Об одной формуле числв:шого обращения пре-эбразования Лапласа. //Мат. модели и их приложения. Тезисы докладов 7- й отчетной научной конференции. Алма- Ата: Наука, I98S, с. 208.

2. Ча В.Л. О методе приближенного вычисления коэффициентов Фурье, основанном на формуле обращения Мебиуса. //Изв. АН КазССР. Сер. физ.- мат. Алма- Ата, 1990. (Деп. ЗИНИТИ И 3809- ВЭО) 7 О.

3. Ча В.Л. Дискретные биортогоналыше я ортогональное системы, основанные на формуле обращодия Мебиуса '/Изв. АН НазССР. Сер. физ.- мат. Алма- Ата, IS90. (Деп. ЗИНИТИ Л 3810- 90) 9 с.

4. Ча В.Л. .Новый метод вычисления ДО, основанный

ia биортогональном ряде ЧеСышева- Маркова. //Язв. АН КазССР. Зер. физ.- маг. Алма- Ата, .1991. (Деп. ВЖИТИ л 2920- B9I) Ю с.