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

АКАДЕМИЯ НАУК БЕЛАРУСИ ИНСТИТУТ ТЕХНИЧЕСКОЙ КИБЕРНЕТИКИ

УДК 519.67?

РОМАНОВСКАЯ НАТАЛЬЯ АЖКСАЭДРОВНА

РАЗРАБОТКА БЫСТРЫХ АЛГОРИТМОВ ДИСКРЕТНЫХ ПРЕОБРАЗОВАНИЙ И СВЕРТОК НА ОСНОВЕ АЛГЕБРАИЧЕСКОГО ПОДХОДА В ЗАДАЧАХ СЖАТИЯ И ЦИФРОВОЙ ФИЛЬТРАЦИИ

05.13.16 -

Применение вычислительной техники, математического моделирования и математических методов в научных исследованиях

АВТОРЕФЕРАТ

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

МИНСК 1996

Работа выполнена в Институте технической кибернетики АН Беларуси

доктор технических наук Крот А.М.

доктор физико-математических наук, профессор Задирака В.К.

кандидат технических наук, Шаренков А. В.

Институт электроники АН Беларуси, г. Минск

Зашита диссертации состоится "31" октября 1996 г. в 11 — часов на заседании совета по заште диссертаций Д 01.04.01 при Институте технической кибернетики АН Беларуси по адресу: 220012, Минск, ул. Сурганова, 6, конференц-зал.

С диссертацией можно ознакомиться в библиотеке Института технической кибернетики АН Беларуси.

Автореферат разослан "__1996 г.

Научный руководитель:

Официальные оппоненты:

Оппонирующая организация:

Ученый секретарь совета по защите диссертаций доктор технических наук

Бибило П.Н.

ОБЩАЯ ХАРАШРЙСТИКА РАБОТЫ

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

изображений. Б связи с этим возникает необходимость синтеза алгоритмов типа быстрых С по критерию минимума арифметических операций) ортогональных преобразований (включая Фурье-подобные) на (над) конечных алгебраических структурах - коммутативных и некоммутативных группах, локальных кольцах, полях. Исследования в данном русле начались с 70-х годов и интенсивно продолжаются и в нынешнее время. Огромный вклад в решение данной проблемы внесли такие известные отечественные и зарубежные ученые как Р.Г.Фараджев, А.М.Трахтман, М.Лоллард, Ч.М.Рейдер, Р.^гарвал, С.Баррас, Ш.Виноград, Г.Нуссбаумер, С.Л.Блшин и другие. Вплоть до конца 70-х - начала 80-х годов исследовался класс ортогональных преобразований на конечных коммутативных Сабелевых) группах. Пионерские исследования М.Г. Карповского, а затем Т.Э.Кренкеля, В.Г.Лабунца, Э.Трахтенберга и других положили начало' теоретическому обоснованию классов новых алгоритмов ортогональных преобразований на конечных некоммутативных группах. Сложность данных исследований заключается в том, что ортогональные преобразования на некоммутативных группах имеет несколько аналитических выражений, а не одно, как в случае коммутативной группы. Но с другой стороны, это дает большую свободу действий при выборе конкретного выражения для ортогонального преобразования по критерию минимума арифметических операций, необходимых для его расчета на компыотере. В связи с этим, исследования в области разработки новых быстрых алгоритмов ортогональных преобразований на конечных некоммутативных группах (например, на группах Гамильтона. Фрабениуса, диэдра и т.п.) могут заметно повлиять на развитие методов и средств цифровой обработки сигналов и изображений.

Связь работы с крупными научными программами, темами. Диссертационная работа выполнена в лаборатории моделирования самоорганизующихся систем Института технической кибернетики Академии Наук Беларуси. Тема работы была утверждена в соответствии с заданием 04.04 Республиканской межотраслевой комплексной научно-технической программы "Разработка быстрых алгоритмов и программного обеспечения для цифровой обработки одномерных и двумерных массивов" (постановление Совета Министров БССР от 16.11.1988г., №327 и распоряжение Президиума Ш БССР от 9.12.1988г., № 662), планом научных работ Института по теме ЕТ-22

"Разработка быстрых алгоритмов цифровой обработки сигналов для эффективного решения проблем анализа, фильтрации, сжатия и идентификации информации в компьютерных системах" (Мгр.19941849), а также НИР по разделу "Анализ" темы "Поток", выполнявшейся НТК АНБ в соответствии с договором 3x33-150/2 с НПО "Точные приборы" (г. Москва).

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

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

анализ строения таблиц характеров конечных групп (ХКГ); разработка эффективных алгоритмов вычисления дискретных сверток Сциклических, косоциклических, параметрических) числовых последовательностей;

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

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

Методы исследования. Теоретические исследования проводились на основе теории представлений (характеров) конечных групп, матричной алгебры, теории чисел, теории и методов цифровой обработки сигналов, а практические - на основе моделирования на компьютере.

Научная новизна полученных результатов.

1. Получены новые результаты об обобщенных дискретных преобразованиях Фурье на неабелевых группах, а также о строении конечных групп, являющихся произведением двух абелевых подгрупп взаимно-простых порядков.

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

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

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

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

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

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

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

Основные положения диссертации, выносимые на защиту:

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

2, Описание структуры таблиц характеров конечных? групп, выявившее наличие в них циркулянтов, составленных из нерациональных чисел комплексного поля.

3. Новый подход к построению эффективных алгоритмов вычисления циклических, параметрических и косоциклических сверток длин, кратных степеням 2 и 3.

4. . Эффективные алгоритмы сжатия и фильтрации цифровых изображений, основанные на разработанных алгоритмах быстрой свертки.

Личный вклад соискателя. В совместных работах участие научного руководителя носит постановочный характер; соискателем исследованы некоторые свойства конечных групп и таблицы характеров конечных групп, разработаны алгоритмы вычисления циклических, косоциклических и параметрических сверток длин, кратных степеням 2 и 3, совместно с к.т.н. М.Н. Долгих разработаны алгоритмы сжатия и цифровой фильтрации сигналов и изображений.

Апробация результатов диссертации. Основные положения диссертационной работы докладывались и обсуждались на XI Всесоюзном симпозиуме по теории групп (г. СвердлоЕск, октябрь 1989 г.), на Республиканских научно-технических конференциях: "Теория и методы создания интеллектуальных САПР" (г. Минск, ноябрь 1994 г.) , "Распознавание образов и обработка информации" Сг.Минск, сентябрь 1995г.), на Международных конференциях: "Автоматизация проектирования дискретных систем" (г.Минск, ноябрь 1995г.), "Современные методы обработки сигналов в системах измерения, контроля, диагностики и управления" (г. Минск, декабрь 1995 г.).

Опубликовзнность результатов. По материалам проведенных исследований опубликовано И научных работ, включая 5 статей и 6 тезисов докладов.

Структура и объем диссертации. Диссертация состоит из введения, четырех глав и выводов, изложенных на 108 страницах машинописного текста, иллюстрирована 4 рисунками, размешенными на 8 страницах, список литературы содержит 148 наименований, приложения содержат 3 страницы.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

Основное отличие этого преобразования от обычного дискретного комплексного проебразования Фурье состоит в том, что вместо экспоненциальных функций, которые является характерами циклической группы, используются неприводимые представления подходящих групп. В работах Биколсона, Дюбуа, Бенетсанапулоса, Бойко и др. конечное преобразование Фурье исследуется" с точки зрения конечных алгебр над коммутативными кольцами. В ней обозначена через S произвольная конечная группа порядка п и через R коммутативная область (интегральная область) целостности. Показано", что групповая алгебра И 6] изоморфна алгебре Rn тогда и только тогда, когда R содержит 1/п вместе с примитивным корнем га-той степени из 1, где ш-экспонента 6. Далее в работе Николсона вводятся матричные представления данных изоморфизмов и каждое получает название обобщенного конечного преобразования Фурье. В связи с этим актуальна следующая проблема: как определить дискретное преобразование Фурье в случае неабелевой группы .6 ?

Б первой главе получен результат, который позволяет определить дискретное преобразование Фурье над полем комплексных чисел для неабелевой группы G. А именно, доказана терема: Теорема 1. Пусть 6 - произвольная конечная группа. Тогда Z^CtSj] = Сп. "где С - поле комплексных чисел и п - число сопряженных классов группы G. Из последующих приведенных результатов следует, что обобщенное дискретное преобразование Фурье на неабелевой группе можно выражать в виде таблиц ХКГ, что eme раз подчеркивает важность исследования таблиц характеров и ее структуры для решения прикладных задач, связанных с обработкой цифровых изображений (в частности цифровой фильтрацией, сжатием, распознаванием). Так, доказаны теоремы:

Теорема 2. Пусть S - конечная группа. Тогда;Z[СЕ 03] обладает

таким базисом {b, .... , b что * (to = хЛк ), L, j = 1.....п,

I 1 " } ■> 1 i-

где ж. - неприводимые характеры группы в, к - представители

сопряженных классов группы G.

Попутно в главе 1 получен результат, касающийся строения

неабелевых групп. Доказано важное утверждение:

-7 (

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

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

Теорема 4. Пусть в - конечная группа, д е 8 и х -неприводимый характер группы в. Тогда, если яСд) - нерациональное число, то выполняются два условия:

1) существует такая подматрица Х(Ф,П> с х € ф, д € о, что ЖФ,ГО - матрица циклической свертки;

2) если хСд') - нерациональное число для некоторого элемента д'« 0, то существует такое множество 0', что Оп-С" = ХСФ.П') имеет вид циклической свертки. ■

Впервые с использованием теории групп строго обоснован способ вычисления дискретных ортогональных преобразований в базисе ХКГ на основе алгоритмов расчета Ш коротких длин.

В качестве примера приведем таблицу знакопеременной группы порядка 60, в которой выделена матрица циклической свертки размером 2x2.

Таблица 1.

101 1А 4 2й 3 ЗА 5 5А Б 5В

1 3 1 -1 1 0 1 Г-5 1

** 3 4 5 -1 0 1 0 1 -1 '-Ь* i___ -1 0 Л! 0

Получены также некоторые другие теоремы о свойствах таблиц характеров.

Георема 5, Пусть G - конечная группа, д е G, 0(g)= N. Тогда, если jgl |(l,H) = lj содержится в одном сопряженном классе группы

G, то для любого характера х группы S, = d - целое число.

Теорема 6. Пусть х характер конечной группы G и д « G. Тогда ;t£g) - целое число тогда и только тогда, когда э£д) = хСу) для лкбого такого у. что <д> = <у>.

Третья глава диссертации посвяшена разработке нового подхода к построению' алгоритмов расчета циклических, косоциклических и параметрических сверток длин, кратных 2 и 3, синтезу некоторых алгоритмов вычисления ЦС, параметрических сверток (ПС) и косоциклических сверток (КЦС) коротких длин. Новый подход основан на методе собственных преобразований оператора свертки (СПОС) в различных полях, разработанного в работах Крота A.M. Известно, что СПОС матричного оператора ЦС является ДПФ, т.е. ДПФ диагонализирует матричный оператор ЦС. Также известно, что нечетно-частотное дискретное преобразование Фурье (НЧДПФ), в свою очередь, - СПОС для оператора КЦС. Как обобщение этих результатов, преобразование Вандермонда является СПОС для матричного оператора ПС.

Сводя ЦС длиной 2п и Зп к ряду ПС длиной~п над полем матриц размерностью 2*2 и 3x3 соответственно воспользуемся затем СПОС Вандермонда с целью приведения полученных ПС к диагональному виду. Данный подход привел к разложению ПС на ряд других ПС меньших размеров, что отражено в следующих реультатах.

Лемма 2. Пусть ЦС длиной N= 2п задана посредством матричного

зписания

Я1 • ■

С (д)х = дг гп в» ■ ■ <Ъп-*

я3 ■ • д2п д,

и Уг

Хг Г1 Уг * Г)

Тогда с помошью перестановок; строк: и столбцов матрицу С2(д) можно свести к элементу С*(1) централизатора матрицы вида 5(1), где

(I) =

0 Е 0 . . . 0

0 0 Е' . . . 0 0

. I =

0 0 0 . . . Е 1

I 0 0 . . . 0

С(1>СМ =

1 О

О 1

. О =

4 V . А п В, I

1А А . г» 1 ■ Вг як

Ч-* ч- ■

14 IV- ЛА А. п 1 в п Ь г»

80 01! О 0

9. + д.

X, +п I

1 Х-

. в = V г, I 1, Ц =

1,... , п.

Лемма 2. Элемент централизатора матрицы 8Ы( а) равен ОЗ) =сйад(1, тд2.....Г1] С^(д') Шад[1.т.т^____т-"-а1>].

-*1 Г 2 Ы 1 N -»-ТГ _ 1 , . „

<3 = [д^гд^х д3.....г д„], т д =[д1,дг.....ды]. в е с.

где

Теорема 7. Пусть задана ПС длиной Л= 2п: С'а>(д)х= у, «= е .

п

где - матричный оператор ПС, дт = [д4, дг, д2п] -

Е

отсчеты импульсной характеристики, х =

исходный цифровой сигнал, ут = |у4„ у2, . -. <* = е - параметр ПС.

= Хг.....*2п] ^

, у2п] - результат ПС,

Тогда у =

-»т

где у

.....

У,

■*т (

Чк - 1а.

-»т Г

*1 = К

г

яг = 1?.

г

хг = х,

= (Уп~.....„) = ^ -

+ .....я/

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

Ск Сд) =1СЫ (д") А,

где г" = А=сЛад[1. г,..., г""1], д' = [ д4, уд2,____

а также

Од)

01 - а а - 13 л,(/3>,

2

3

где а , р , ш е с.

Разработанный метод был использован для построения алгоритмов вычисления ПС длиной 4, КЦС длиной 8, ЦС длиной 16, а

также ЦС длиной 9. Было получено сокращение числа умножений в синтезированных алгоритмах коротких длин по сравнению с наиболее эффективными короткоточечными алгоритмами Винограда и Нуссбаумера. Показано применение предложенных алгоритмов расчета ЦС, КЦС и ПС коротких длин для синтеза процедур расчета ЦС длинных последовательностей в сочетании с алгоритмом Агарвала-Кули.' Б Табл. 2. приведены полученные оценки вычислительной сложности предложенного алгоритма и дан сопоставительный анализ с известными алгоритмами.

Таблица 2.

^Мсло арифметических , операций для сверток, вычисленных по гнездовому алгоритму Агарвала-Кули

м на основе предложенного алгоритма и алгоритмов коротких циклических сверток на основе алгоритма Нуссбаумера и алгоритмов коротких циклических сверток

А. м/ы ! А/Н м* м/и А/И

18 40 184 ! 2.22 18.33 38 184 2. И 10.22

20 50 210- | 2.5 | 10.5 50 230 2.5 11.5

24 56 236 2.33 I 9.83 56 272 2.33 11.33

48 152 812 3.16 16.91 164 716 3.41 14.91

80 380 1973 4.75 24.66 4108 1846 5.12 23.07

144 760 4205 5.27 1 38.41 820 3749 5.69 26.03

240 1520 8772 1 6.33 36.55 1640 8264 6.83 34.43

720 7600 51220 | 10.55 71.13 7790 40994 10.81 56.93

112 380 2710 | 1.07 1 24.19 410 2470 3. 66 22.05

336 1520 12072 | 4.52 I 35.92 1640 11112 4. 88 33.07

560 3800 27100 6.78 48.39 4100 25060 7.32 44.75

1008 7220 52510 7.16 ! 52.09 7740 52570 7.72 52.15

1680 15200 114560 1 9.04 68.19 16400 106400 9.76 63.33

5040 72200 525100 14.32 104.18 77900 517580 15.45 102.69

где Мн - число действительных умножений, А^ - число действительных сложений.

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

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

{х . }: I. п2->

У

к - к = Е 2 [ХП .г, ^ [П1])п. [пг] 1 г „=0 п = о 4 П1 г 1 ■'2 1 2

к , к I г

к, =0, 1__________к, = 0, 1,... , М2- 1;

где |<Рк - система дискретных ортогоналных функций. Хк

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

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

Ас , к = "^'^к , к ' = , к ' ^к , к ; ^к . к = ^к , к ^к . к • 12 12 12 12 12 1212

к1 = 0, 1,.. . , кг =0, 1.....Мг- 1.

где * - символ комплексного сопряжения, 1к к - массив

1 ' 2

отобранных спектральных коэффициентов, 1\. к - двумерная

1' г

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

I. п»' пг->

преобразования:

N -1 N -± X. ' " к , к

^ *Ч ! г,-о ,,=о 'Ч|л2 1 •* Ч "г

к4 =0, 1.....1, к2 =0, 1.....Н2- 1.

Коэффициент сжатия информации определяется из отношения общего числа Я коэффициентов ортогонального преобразования к числу К

с ©т

сохраненных коэффициентов в результате сжатия (компрессии):

К = -

«п ° со»

При пороговом способе отбора коэффициентов считается, что

элементы массива -¡Хк к | со значениями, меньшими чем пороговое, 1 ' 2 Л

не вносят существенного вклада в амплитудный спектр и приравниваются нулю. Искажения, вносимые процедурой сжатия, оцениваются по значениям средней абсолютной ошибки вычислений у и среднеквадратическому значению ошибки (СКО) £у:

N -1 N -± / N -I N -1

_ 1 * 2 1 / 1 2

У = г Е Е у .£= ~Е Е у2

N п = о п1'пг У N п = о п=о Т11* "г

Процедуры сжатия информации в настоящей работе выполнялись на основе новых классов дискретных ортогональных преобразований в базисе ХКГ.

В ходе численного эксперимента было выяснено, что наряду с известными дискретными ортогональными преобразованиями, такими, как НЧДПФ и дискретное косинусное, хорошими компрессивными свойствами обладают ДОП в базисе характеров групп диэдра, являющихся либо прямым произведением трех диэдральных групп порядка 10, либо диэдральной группой порядка 250, а также ДОП на основе диэдральной группы порядка 244.

Предложенные процедуры сжатия с использованием ДОП на неабелевых группах позволяют в среднем увеличить коэффициент сжатия в 2 раза по сравнению с аналогичными процедурами, основанными на ДОП для абелевых групп - НЧДПФ и ДПФ, как показано в Табл. 3.

Таблица 3.

Коэффициенты сжатия, полученные при близких значениях СЮ - е

№ Действительные двумерные ДОП в базисе ХКГ (64x64) —а—!-- Ч 7

1 Диэдральная группа порядка 2Ы) и. иЬ7 ЗЬ 3.83

2 Прямое произведение трех диэдральных групп порядка 10 0.063 25 3.36

3 1руппа Клейна (ДОП Уолша-Адамара) 0.067 2-6 2.6

4 НЧДПФ 0.065 1Ь II 2.67

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

Вычисление двумерной KMX-фильтрации изображений с использованием методов секционирования свертки С в частности, перекрытия с суммированием) сводится к вычислению одномерных ПС коротких длин.

Полученные в третьей главе алгоритмы вычисления Dp коротких длин использовались для двумерной КИХ-фильтрации изображений, что позволило ускорить процесс цифровой фильтрации в 1,5-2 раза.

ВЫВОДЫ

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

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

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

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

5. Разработаны быстрые процедуры цифровой нерекурсивной Фильтрации на основе предложенных алгоритмов , вычисления ЦС.

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

1. Романовская H.A. Комплексные характеры и нормальные подгрупп! /V Доклады АН БССР,- 1990.- Т. XXXIV, № 10.- С. 872-875.

2. Крот A.M., Романовская H.A. О строении таблиц характеров конечных групп,- Препринт Ин-т техн. кибернетики АН Беларуси. -Минск, 1993.-М 24. -18 с. "

3. Крот A.M., Романовская H.A., Долгих М.Н. Сжатие информации на основе быстрых алгоритмов вычисления ортогональных преобразований в базисе характеров конечных групп у/ Теория и методы создания интеллектуальных САЛР. Тез. докл. научно-техн. конф.- Минск, 1993,- С. 21.

4. Романовская Я. А. Вычисление КЦС, ЦС и параметрических сверток длины кратной двум.- Препринт ^ йн-т техн. кибернетики АН Беларуси. - Минск. 1995,- N15. - 25 с.

5. Романовская H.A. Комплексные характеры и нормальные подгруппы // П Всесоюзный симпозиум по теории групп, посвященный 60-летию чл.-корр. АН СССР М.И. Каргополова. Тез.- Свердловск. 1989,- С. 93-99.

6. Долгих М.Н. . Романовская H.A. Сжатие информации на основе таблиц характеров конечных групп Современные метода обработки сигналов в системах измерения, контроля, диагностики и управления. Материалы научно-техн. конф. Часть I.- Минск. ЕГУ. 1995.- С. 27-31.

7. Романовская H.A. Исследование структуры таблицы характеров ,-v Теория и методы создания интеллектуальных САПР. Тез. докл. научно-техн. конф. -Минск, 1993.-С. 47.

8. Романовская H.A. Вычисление косоциклических, циклических и параметрических сверток длины, кратной трем /Ред. журн. "Изв. АН Беларуси Сер. Физ.-мат. н".- Минск. 1996.- 31 е.- Деп. в ВИНИТИ -06.03.96. ff 699-В96.

9. Романовская H.A. Вычисление КЦС, ЦС и параметрических сверток длины кратной двум ,-v- Распознавание образов и..обработка информации. Тез. докл. III межд. конф.-Минск, 1995. -С. 32-32.

10. Крот A.M., Романовская H.A. Компьютерное моделирование стационарных ЛДС на основе алгоритмов быстрой свертки Автоматизация проектирования дискретных систем. Тез. докл. межд. конф. Том I,- Шнек, 1995.-С. 123.

И. Долгих М.Н., Крот A.M., Романовская H.A. Сжатие информации для цифровых изображений на основе дискретных ортогональных преобразований в базисе характеров конечных групп / Ред. журн. "Изв. АН Беларуси Сер. физ.-мат. н",- Минск, 1996.- 33 е.- Деп. в ВИНИТИ 1996.

РЭЗШЭ

да дысертацш Раманоускай H.A. "Распрацоука быстрых алгарытмау дыскрэтных пераутварзнняу i. скрутак на аснове алгебра! чнага падыхода у задачах кампрзсН i л1чбавай Ф1льтрады1".

клкиавыя словы: неабелева трупа, табдша характарау канечных груп, дзкампаз1цыя, група дыздра, цыкжчная, параметрычная i косацыюи чная скрутка, абагульненае дыскрэтнае пераутварэнне Фур'е.

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

Распрацаваны высокаэфектыуныя прадздуры сшскання на аснове новых тыпау дыскрэтных артаганальных пераутварзнняу (ДАШ, матрицы як1х атсваюцца таблшат характарау канечных груп СХКГ). Установлена, што давол1 эфектыунымх кампрэсхуньм1 уласщва.свдм1 в ало дашь ДАЛ у базiсе ХКГ дыэдра.

Абагульнена тзарзма Hiкаясана на вьшадак неабелевых груп, дазвалякчая будаваць абагульняныя дыскрзтныя пераутварення Фур'е ( ДПФ) на неабзлевых трупах. Даследавана структура таблш ХКГ, дазваляючая устанашць наяунасць у ix цыркулянтау, састауленых з нерацыянальных л1кау.

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

РЕЗЮМЕ

к диссертационной работе Романовской H.A. "Разработка быстрых алгоритмов дискретных преобразований и сверток на основе алгебраического подхода в задачах сжатия и цифровой фильтрации".

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

параметрическая и косоциоическая свертка, обобщенное дискретное преобразование Фурье.

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

Разработаны высокоэффективные процедуры сжатия на основе новых типов дискретных ортогональных преобразований (ДОП) матрицы которых описывакяся таблицами характеров конечных групп (ХКГ) . Установлено, что достаточно эффективными компрессивными свойствами обладают ДОП в базисе ХКГ диэдра.

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

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

RESUME

to Romanovskaya's N. A. thesis "The development of fast discrete transforms and convolutions algorithms on the basis of algebraic approach for oppression and digital filtering tasks".

Keywords: non-Abeli an group, finite groups characters table, decomposition, dihedral group, cyclic, parametric and skewcyclic convolutions, generalised discrete Fourier transform (DFT).

The new effective algorithms of information compression and filtering based on discrete transform and convolutions on finite algebraic structures have been developed for reducing temporal and energy expenditures, increasing precision and processing reliability of large information volumes in the computer systems.

The high effective procedures of compression based on nev

types of discrete orthogonal transform (DOT) whose.- matrices are described with finite group character tables (FCD have been developed. It is established that DOT in basis of dihedral FCT provides enough effective compressive features.

The .Ni col son's theorem generalized on case of non-Abel i an groups allows to construct the generalized DFT on non-Abelian groups. On the basis of the FCT structure analysis it is established that the nonrational numbers form a cyclic ■convolutions (CC) and DFT in FCT.

The fast procedures of digital nonrecursive filtering based on the GC calculation algorithms have been developed. The fast.CC calculation algorithms for sequences of length power 2 "and 3 based themselves on the developed effective decomposition procedure of convolutions on the row of skewcyclic and parametric convolutions of reduced length.

Романовская Наталья Александровна

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

Специальность 05.13.01 - Применение вычислительной техники, «атематического моделирования и математических методов в научных ^следованиях

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Подписан к печати 26.09.96. Формат 60x84 1Л6. Объем 1,0 п.л. Тираж 100 экз. Заказ 40.

Спечатано на ризографе Института технической кибернетики АН Зеларуси, 220012, Минск, ул. Сурганова, 6.