Введение к работе
Актуальность темы диссертации. Цифровая обработка сигналов (ЦОС) получила широкое распространение в радиолокации и радионавигации, связи, космических исследованиях, медицине, картографии, дефектоскопии и других областях науки и техники. В настоящее время разработано большое количество алгоритмов быстрых преобразований в базисах ортогональных функций (в частности, алгоритмов быстрого преобразования Фурье). Большинство этих разработок преследуют одну цель: увеличить быстродействие вычисления преобразований за счет сокращения числа арифметических операций. Однако невозможность значительно увеличить быстродействие заставляет многих исследователей для решения ряда задач ЦОС заменять широко используемое дискретное преобразование 'Фурье СДПФ) на другие, более быстродействующие. В связи с этим возникла необходимость использования в практике ЦОС последних достижений теории быстрых алгоритмов дискретных ортогональных преобразований (ДОП). В настоящее время получены новые результаты, касающиеся применения теории конечных абелевых групп, с одной стороны, для синтеза быстрых алгоритмов гармонического анализа и свертки, а с другой - для расширения возможностей ЦОС за счет использования новых классов дискретных ортогональных преобразований на группах. Возможности алгоритмов и процедур ЦОС, основанных на теоретико-групповых концепциях, могут быть существенно расширены за счет привлечения более мошных методов теории не только абелевых, но и неабелевых групп. В связи с вышеизложенным, настояния диссертация посвящена решению актуальной проблемы - синтезу новых эффективных алгоритмов обработки информации на основе ДОП и сверток на конечных алгебраических структурах. Значимость решаемой проблемы обусловлена необходимостью сокращения временных и энергетических затрат, повышения точности» качества и достоверности отбора и переработки больших объемов информации в компьютерных системах самого различного назначения. Актуальность данных исследований особенно отчетливо проявляется в задачах фильтрации, сжатия, восстановления ' и распознавания многомерной информации, представляемой на основе двумерных и трехмерных цифровых
2 изображений. Б связи с этим возникает необходимость синтеза алгоритмов типа быстрых (по критерию минимума арифметических операций) ортогональных преобразований (включая Фурье-подобные) на (над) конечных алгебраических структурах - коммутативных и некоммутативных группах, локальных кольцах, полях. Исследования в данном русле начались с 70-х годов и интенсивно продолжаются и в нынешнее время. Огромный вклад в решение данной проблемы внесли такие известные отечественные и зарубежные ученые как Р.Г.Фараджев, А.М.Трахтман, М.Поллард, Ч.М.Рейдер, Р.дгарвал, С.Баррас, Ш.Виноград, Г.Нуссбаумер, С.Л.Елюмин и другие. Вплоть до конца 70-х - начала 80-х годов исследовался класс ортогональных преобразований на конечных коммутативных (абелевых) группах. Пионерские исследования М.Г. Карповского, а затем Т.Э.Кренкеля, В.Г.Лабунца, Э.Трахтенберга и других положили начало' теоретическому обоснованию классов новых алгоритмов ортогональных преобразований на конечных некоммутативных группах. Сложность данных исследований заключается в том, что ортогональные преобразования на некоммутативных группах имеет несколько аналитических выражений, а не одно, как в случае коммутативной группы. Но с другой стороны, это дает большую свободу действий при выборе конкретного выражения для ортогонального преобразования по критерию минимума арифметических операций, необходимых для его расчета на комлыотере. В связи с этим, исследования в области разработки новых быстрых алгоритмов ортогональных преобразований на конечных некоммутативных группах (например, на группах Гамильтона. Фрабениуса, диэдра и т.п.) могут заметно повлиять на развитие методов и средств цифровой обработки сигналов и изображений.
Связь работы с крупными научными программами, темами. Диссертационная работа выполнена в лаборатории моделирования самоорганизующихся систем Института технической кибернетики Академии Наук Беларуси. Тема работы была утверждена в соответствии с заданием 04.04 Республиканской межотраслевой комплексной научно-технической программы "Разработка быстрых алгоритмов и программного обеспечения для цифровой обработки одномерных и двумерных массивов" (постановление Совета Министров БССР от 16.11.1988г., ftp- 327 и распоряжение Президиума АН БССР от 9.12.1988г., U 662), планом научных работ Института по теме ЙТ-22
"Разработка быстрых алгоритмов цифровой обработки сигналов для эффективного решения проблем анализа, фильтрации, сжатия и идентификации информации в компьютерных системах" (Игр.19941849), а также НИР по разделу "Анализ" темы "Поток", выполнявшейся НТК АНБ в соответствии с договором 3x33-150/2 с НПО "Точные приборы" (г. Москва).
Цель работы. Белью работы является разработка методов и быстрых алгоритмов вычисления дискретных ортогональных преобразований и сверток на основе алгебраического подхода для решения задач сжатия и цифровой фильтрации сигналов Сизображений).
Поставленная цель определила следующие основные задачи:
исследование структуры некоторых конечных групп и обобщенных дискретных преобразований;
анализ строения таблиц характеров конечных групп (XKD;
разработка эффективных алгоритмов вычисления дискретных сверток Сциклических, косоциклических, параметрических) числовых последовательностей;
разработка алгоритмов и программ реализации процедуры сжатия информации на основе ортогональных преобразований в базисе характеров конечных групп для цифровой обработки изображений;
разработка алгоритма и программы процедуры фильтрации цифровых изображений с использованием предложенных алгоритмов быстрой свертки.
Методы исследования. Теоретические исследования проводились на основе теории представлений (характеров) конечных групп, матричной алгебры, теории чисел, теории и методов цифровой обработки сигналов, а практические - на основе моделирования на компьютере.
Научная новизна полученных результатов.
-
Получены новые результаты об обобщенных дискретных преобразованиях Фурье на неабелевых группах, а также о строении конечных групп, являющихся произведением двух абелевых подгрупп взаимно-простых порядков.
-
Исследована структура таблиц характеров конечных групп, позволившая установить наличие в них циркулянтов, составленньк из нерациональных чисел.
-
Разработаны быстрые алгоритмы вычисления циклических сверток длин, кратных степени 2 и 3, на основе эффективной процедуры декомпозиции их на ряд косоциклических и параметрических сверток меньших размеров.
-
Разработаны эффективные процедуры сжатия на основе новых типов дискретных ортогональных преобразований, матрицы которых описываются таблицами характеров конечнім групп.
-
Разработаны быстродействующе процедуры цифровой нерекурсивной фильтрации на основе предложенных алгоритмов вычисления циклических сверток.
Практическая значимость полученных результатов. Практическая значимость работы заключается в том, что основные результаты диссертационной работы позволяют и могут быть использованы для создания высокоэффективных систем сжатия информации: речевых компрессоров в системах передачи и хранения речи, в цифровых системах телевидения высокой четкости (ТВЧ), в компьютерных системах мультимедиа, в цифровых системах связи. Предложенные процедуры цифровой фильтрации могут найти применение в цифровых системах связи, цифровой телефонии, цифровых телеметрических системах и др.
Разработанные алгоритмы сжатия и цифровой фильтрации в комплексе программных средств визуального дешифрирования космических снимков приняты к: использованию в НЮ "Точные приборы" (г. Москва).
Экономическая значимость полученных результатов. Предложенные алгоритмы и программы в случае их включения в состав соответствующих цифровых систем обработки (фильтрации и сжатия) сигналов и изображений могут быть использованы в качестве коммерческого продукта (например, цифровой диктофон, речевой встраиваемый информатор, автоответчики в системах передачи и хранения речи, цифровой Фотоаппарат и т.д.).
Основные положения диссертации, выносимые на зашиту.
1. Исследование обобщенных дискретных преобразований Фурье на
неабелевых группах, характеризация строения некоторых конечных
групп.
2, Описание структуры таблиц характеров конечных? групп,
выявившее наличие в них циркулянтов, составленных из
нерациональных чисел комплексного поля.
3. Новый подход к построению эффективных алгоритмов вычисления
циклических, параметрических и косоциклических сверток длин,
кратных степеням 2 и 3.
4. . Эффективные алгоритмы сжатия и фильтрации цифровых
изображений, основанные на разработанных алгоритмах быстрой
свертки.
Личный вклад соискателя. В совместных работах участие научного руководителя носит постановочный характер; соискателем исследованы некоторые свойства конечных групп и таблицы характеров конечных групп, разработаны алгоритмы вычисления циклических, косоциклических и параметрических сверток длин, кратных степеням 2 и 3, совместно с к.т.н. М.Н. Долгих разработаны алгоритмы сжатия и цифровой фильтрации сигналов и изображений.
Апробация результатов диссертации. Основные положения диссертационной работы докладывались и обсуждались на XI Всесоюзном симпозиуме по теории групп (г. СвердлоЕск, октябрь 1989 г.), на Республиканских научно-технических конференциях: "Теория и методы создания интеллектуальных САПР" (г. Минск, ноябрь 1994 г.) , "Распознавание образов и обработка информации" Сг.Минск, сентябрь 1995г.), на Международных конференциях: "Автоматизация проектирования дискретных систем" (г.Минск, ноябрь 1995г.), "Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления" (г. Минск, декабрь 1995 г.).
Опубликованность результатов. По материалам проведенных исследований опубликовано 11 научных работ, включая 5 статей и 6 тезисов докладов.
Структура и объем диссертации. Диссертация состоит из введения, четырех глав и выводов, изложенных на 108 страницах машинописного текста, иллюстрирована 4 рисунками, размешенными на 8 страницах, список литературы содержит 148 наименований, приложения содержат 3 страницы.
