Введение к работе
Актуальность. Цифровая обработка сигналов (ЦОС) широко применяется для решения сложных задач радиолокации, связи, сейсмологии, оптики, радиоастрономии, томографии и других областей науки и техники. Многие методы ЦОС основаны на спектральном анализе и синтезе. Б настоящее время в этой области существует большое число алгоритмов (БІЙ, Винограда, Уолша-'Адзмара, творетико- числовых преобразования и др.). При этом во многих практических задачах перед алгоритмами ЦОС предъявляются такие требования как необходимость обработки данных в режиме реального времени, минимальность аппаратурных затрат, простота технической реализации. На практике часто возникает проблема цифровой обработки больших массивов данных, решение которой известными методам является затруднительным или невозможным. Так в обработке изображений, дельта- модуляции и других существует необходимость обработки сигналов, заданных с частотой дискретизации существенно большей минимальной частоты по критерию Шеннона- Найквиста. Такое положение препятствует создании высокопроизводительных систем обработки сигналов. Поэтому для решения этой задачи становится необходимым создание и исследование принципиально нознх численных методов Фурьэ- анализа и синтеза.
В данной диссертационной работе рассматриваются метода, основанные на применении биортогоналышх рядов Чебышева-Маркова. Впервые такие ряды были применены в середине прошлого века великим русским математиком П.Л.ЧеСшевым для решения задачи аппроксимации большого числа экспериментальных дешшх. На практшш на результата наблюдений часто накладываются шуш. Известным методом решения такой задачи является
метод наименьших квадратов. Однако, в том случав, когда задано значительное число наблюдений, превышающее степень полинома аппроксимации, применение этого метода становится затруднительным из- за большого объема вычислений и роста, связанных с этим погрешностей. Уменьшение же числа используемых отсчетов модат привести к увеличению погрешности. Поэтому n.JT. Чебшев поставил проблему создания простых и эффективных методов восстановления информации путем сокращения ее избыточности уередненкэм по различным выборкам ж отличных от метода наименьших квадратов простотой реализации.
Им предложено Д..Я восстановления сигнала использовать биортогональный ряд по полиномам ЧеОшевэ. 2- го рода. Особенностью этого ряда является то, что его коэффициенты представляются в виде суммы конечных интегралов от восстанавливаемой функции. Это свойство значительно упрощает процесс вычисления коэффициентов ряда, так как большая плотность -задания отсчетов позволяет аа счет применения простейших квадратур типа прямоугольников или трапеции для вычисления конечных интегралов построить такую процедуру вычислений коэффициентов ряда, в которой основное место занимают операции сложения.
Однако полностью исключить операции умножения из процедуры вычислений не удается из-за необходимости вычисления интегралов по интервалам, ограниченным корнями полиномов Чебы-шева. Число таких интегралов будет расти вместе с номером коэффициента. Поэтому является актуальной задача дальнейшего упрощения вычислений по методу Чебышева. Отсутствие решения атоа задачи явилось , по- видимому, причиной того, что предложенный Чебшгевым метод не нашел широкого использования в численном анализе.
порядок убывания на бесконечности коэффициентов Чебышвва-Маркова и Фурье является одинаковым, что является важным для повышения вычислительной эффективности процедур поэтапного сжатия информации.
Известен (А.В.Калинин, Б.Л.Пивоваров) рекуррентный способ вычисления коэффициентов Фурье, основанный на известном разложении прямоугольного синуса и косинуса. Однако ими предложено проводить вычисления по формуле, погрешность которой является значительной.
В диссертационной работе на основе применения кусочно-постоянной интерполяции построен метод вычисления коэффициентов биортогонального ряда Чебншева- Маркова и коэффициентов Фурье. Особенностью этих методов является то, что необходимое число операций умножения имеет порядок O(N). Получены оценки погрешности метода. Показано, что дисперсия погрешности вычисления коэффициентов Чебышева- Маркова, вызванная "белым" иу-мом, имеет порядок 0(N ). Предложенный метод является простім для реализации и организации по нему параллельных вычислений, требует линь операций умнонения и сложения действительных чисел. ,
Построен аналог биортогснальных систем Чебншева- Маркова дискретной переменной, вычисление коэффициентов которых происходит в базисе дискретных прямоугольных тригонометрических функции. Такие преобразования привлекали внимание специалистов ЦОС '{"А.В.Калинин, Б.Л.Пивоваров, Э.Е.Дагман, Г.А.Кухарев, О.К.Эрсоу, В.Г.Дзюбан), в связи с тем, что они требуют лишь операций слокения.и сдвига. В связи с этим их техническая реализация может оказаться очень простой. В диссертации такие преобразования рассмотрены с позиции использования Оиортого-
Отметим,-что чебышевская идея построения биортогональ-ных систем и рядов была использована в теоретических работах А.А.Маркова,Н.П.Романова и других. Однако вопросы практического применения таких ранов в них не рассматривались.
Таким образом, задача построения простих и эффективных алгоритмов спектрального анализа и синтеза, основанных на использовании биортогональных рядов Чебышева- Маркова, определяется запросами теории и практики и является актуальной.
Целью работы является исследование вопросов практического применения Оиоргогональных рядов Чебышева- Маркова и разработка на основе таких рядов алгоритмов спектрального анализа с меньшей сложностью вычислений .
Методы исследования. В данной работе применялись результаты теории чисел, функционального анализа, рядов Фурье, методов суммирования рядов, гармонического анализа.
Научная новизна. В настоящее время известен подход к вычисленшо коэффициентов фурье, основанный на применении известной в теории чисел формулы обращения Мебиуса к различным модификациям формула суммирования Пуассона. Такой метод рассматривался в работах Р.Р.Голдберга и Р-С.Варги, S.H. Линнеса, В.М.Амэрбаева и Н.А.Утембаева, М.С.Рида, Д.В.Тафтса, Г.Садасива и др.
В данной диссертации предлагается метод, основанный на' применении формулы обращения Ыебиуса к коэффициентам биорто-' тонального рада Чебышева- Маркова. Преимуществом такого подхода является то, что он.позволяет точнее оценить скорость сходимости к точному решению в сравнении с методами, основанными на формуле суммирования Пуассона. При атом показано, что
нальных систем ЧеСшева- Маркова, что позволяет получить новые представления для ДПФ и тригонометрического интерполяционного полинома в виде дискретного аналога биортогонального ряда Чебыпова- Маркова. Вычисления по таким представлениям происходит по 2 последовательным этапам, один из которых являет собой дискретное прямоугольное преобразование, другое-умножение на матрицу блочно- диагонального вида с большим числом нулей.
Практическая ценность. Предложенные метода спектрального анализа и синтеза могут найти применение ііри создании специальных аналоге- цифровых устройств регистрации и обработки данных. Основннгга операциями в этих методах являются операции сложения и сдвига и поэтому они легко реализуются в аналогової части процессора. Остальные вычисления происходят в его цифровом блока. Предложенные метода 'удобіш для организации по нем параллелышх вычислений. Такій образом, выполнение спецпроцессора по этим методам кокет обеспечить реализацию вычислений в рзкиме реального времени.
Апробация работы. По теме диссертации были сделана доклада па семинарах и конференциях ИМИ АН КазССР, международной конференции "Высокопроизводигелыше вычислительные системы в управлении и научных исследованиях", Алма-Ата, IS9I, семинаре под рук. проф. Лукьянова А.Т.
Публикации. Основные результаты опубликованы в 4 работах.
Объем и структура работы. Диссертация состоит из введения, 3 глав, заключения, списка литературы и приложения, изложена на 134 страницах машинописного текста
и включает 6 рисунков и 12 таблиц. Список использованной литературы содержит Б6 наименований.