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

Введение

Глава 1. Совмещенные алгоритмы дискретных ортогональных преобразований с представлением данных в альтернативных алгебрах.

1.1. Совмещенные многомерные БПФ с представлением данных в алгебрах Клиффорда.

1.1.1. Основная теорема.

1.1.2. Примеры БПФ с совмещением в четырехмерных алгебрах Клиффорда.

1.2. Методы синтеза быстрых алгоритмов дискретных преобразований с представлением данных в полях алгебраических чисел.

1.2.1. Представление данных в циклотомических кодах.

1.2.2. Алгоритмы двумерных ДОЛ, реализуемые в кодах Гамильтона - Эйзенштейна.

1.2.3. Быстрые алгоритмы одномерного ДПФ с восьмикратным совмещением в алгебре матриц.

1.3. Алгоритмы ДПФ с совмещением в групповых алгебрах циклических групп.

1.3.1.Некоторые свойства групповых алгебр циклических групп.

1.3.2. Быстрый алгоритм вспомогательного преобразования со значениями в групповой алгебре.

1.3.3. Быстрый алгоритм ДПФ с асимптотическим понижением порядка мультипликативной сложности

1.3.4. Некоторые специальные случаи.

Комментарии.

Основные результаты главы 1.

Глава 2. Дискретные преобразования с базисами, порожденными группами Галуа циклотомических полей.

2.1. Дискретные ортогональные преобразования с базисами из периодов полей деления круга.

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

2.2.1. Схема декомпозиции ДПГ типа Кули-Тьюки

2.2.2. Редукция Галуа ДПГ (общий случай).

2.3. Быстрые алгоритмы многомерных ДПФ, использующие редукцию Галуа.

2.4. Некоторые замечания об эффективности алгоритмов Рейдера-Винограда.

Комментарии.

Основные результаты главы 2.

Глава 3. Унифицированный метрический подход к синтезу быстрых алгоритмов многомерного ДПФ.

3.1. Алгоритмы двумерного ДПФ с расщеплением основания нецелого порядка.

3.1.1. Альтернативная интерпретация редукции Кули-Тьюки.

3.1.2. Чесс-алгоритмы двумерного ДПФ.

3.1.3. Алгоритмы ДПФ-2 с "мультипокрытием" области суммирования.

3.2. Специальный случай: алгоритмы многомерного ДПФ с расщеплением основания нецелого порядка при N = 2Г.

3.2.1. Алгоритмы двумерного ДПФ с покоординатным прореживанием области суммирования.

3.2.2. Чесс-алгоритмы двумерного ДПФ для N=2r.

3.2.3. Интерпретация алгоритмов двумерного ДПФ как алгоритмов с расщеплением основания нецелого порядка.

3.2.4. Алгоритмы двумерного ДПФ с "мульти-покрытиями" области суммирования.

3.3. Многомерные БА ДПФ с расщеплением основания нецелого порядка.

3.3.1. Алгоритмы ДПФ-d с простым покрытием области суммирования.

3.3.2. Алгоритмы ДПФ-d с "мультипокрытием" области суммирования.

3.3.3. Алгоритмы ДПФ-d, порожденные максимальными покрытиями.

Комментарии.

Основные результаты главы 3.

Глава 4. Алгоритмы вычисления дискретной циклической свертки с представлением данных в рекуррентных системах счисления

4.1. Основные определения и теоремы.

4.2. Параллельные алгоритмы дискретных шифт-ТЧП для ■данных, представленных в рекуррентных системах счисления первого порядка.

4.2.1. Шифт-ТЧП по модулю составных чисел Мерсенна

4.2.2. Шифт-ТЧП по модулю составных чисел

Ферма.

4.3. Алгоритмы дискретных шифт-ТЧП для данных, представленных в рекуррентных системах счисления высших порядков.

4.3.1. Дискретные шифт-ТЧП Мерсенна-Фибоначчи и Ферма—Фибоначчи в конечных полях.

4.3.2. Дискретные шифт-ТЧП Мерсенна-Фибоначчи и Ферма-Фибоначчи в прямых суммах колец.

4.3.3. Обобщенные преобразования Фибоначчи-Ферма и

Фибоначчи-Мерсенна.

Комментарии.

Основные результаты главы 4.

Глава 5. Об иерархиях алгебр, параметризующих некоторые классы быстрых алгоритмов дискретных преобразований.

5.1. Категория быстрых алгоритмов дискретного преобразования Фурье.

5.2. О "метаалгоритме" в групповом кольце над кольцом аделей глобального поля.

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

Актуальность работы. Историю быстрых алгоритмов обработки сигналов принято отсчитывать с 1965 г., когда Кули и Тьюки /157/ опубликовали свой быстрый алгоритм вычисления дискретного преобразования Фурье (далее - БПФ), хотя ранее Гуд (1960 г.) и Томас (1963 г.) опубликовали в практически незамеченных современниками работах /195,233/ свои быстрые алгоритмы дискретного преобразования Фурье, базирующиеся на несколько ином подходе. За время, прошедшее с первых публикаций, дискретный спектральный анализ стал одним из основных средств решения задач цифровой обработки сигналов, распознавания образов, машинного зрения, компьютерной оптики и т.д.

Разработке эффективных (быстрых) алгоритмов вычисления спектров различных дискретных преобразований посвящено большое количество публикаций, как у нас в стране, так и за рубежом /9,11,12,13,16,20,28,37,39,53,54,60,63,68,71,86,125, 148,184,222,235,240/.

Значительный вклад в развитие общей теории дискретных г7 I преобразований и их быстрых алгоритмов внесли С.С.Агаян, Н.Н.Айзенберг, В.А.Власенко, В.Г.Лабунец, А.М.Крот, А.М.Трахтман, Л.П.Ярославский; Р.Агарвал, Ш.Виноград, Г.Нуссбаумер, Ч.Рейдер и др.

Высокоэффективные алгоритмы конкретных преобразований, адаптированные к характеристикам применяемых вычислительных средств разработаны И.Е.Капориным, Е.Е.Тыртышниковым, А.М.Григоряном и другими исследователями /22,27,40,42,74, 83, 84,187,228,236,237,238/.

В настоящее время теория дискретных преобразований развивается, в основном, в следующих направлениях:

- синтез параметрических семейств новых ортогональных базисов со структурой быстрых алгоритмов, инвариантной по отношению к той или иной принятой авторами концепции синтеза таких алгоритмов (кронекеровская факторизация, полиномиальные преобразования и т.п.)/56-58,128-129/;

- распространение идей и методов классического дискретного "комплексного" спектрального анализа на функции, определенные на группах и принимающие значения в алгебрах достаточно общего вида /6,50,55,59,61,154-156/; разработка новых конкретных алгоритмов, обладающих повышенной точностью и быстродействием, адекватных по структуре вычислений последним разработкам в области специализированных процессоров /1,3,5/.

Отдельно следует отметить бурно развивающуюся в последнее десятилетие теорию вэйвлет-преобразований.

Несмотря на то, что за почти тридцатипятилетнюю историю развития теории быстрых алгоритмов дискретных ортогональных преобразований (БА ДОП) неоднократно предпринимались попытки построения на единой концептуальной основе теории синтеза быстрых алгоритмов, унифицированный конструктивный подход к этой проблеме, по мнению автора, пока еще не разработан. К настоящему времени наиболее известными общими подходами является метод кронекеровской факторизации матриц ДОП /9,20,86,125/ и метод полиномиальных преобразований /12,53, 71,240/.

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

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

Таким образом, задача разработки единого подхода к синтезу БА ДОП, задача создания теории, предметом которой являлся бы алгоритм, а не дискретное преобразование, представляется до сих пор нерешенной, а широкое распространение методов дискретного спектрального анализа в разнообразных задачах обработки информации делает ее весьма актуальной.

Обоснование подхода. Знакомство с основополагающими работами Ю.И.Журавлева /34-36/ и его учеников в алгебраической теории распознавания образов сформировало у автора представление об алгоритме, как о "точке" в некоторой алгебраической структуре со специфическими операциями, отношениями, топологическими свойствами. Именно алгоритм дискретного преобразования, а не само преобразование является основным предметом исследования в диссертационной работе. В первую очередь в работе анализируются те алгебраические и арифметические свойства параметров преобразований, которые гарантируют существование быстрых алгоритмов и возможность их конструктивного использования для параметрически управляемого синтеза таких алгоритмов. Проблема синтеза новых базисов представляется значительно более исследованной и в диссертации рассматривается только в тех случаях, когда синтезированные алгоритмы обладают инвариантной структурой для класса преобразований более широкого, чем рассматривалось ранее.

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

- редукция Кули-Тьюки,

- редукция Гуда-Томаса,

- редукция Рейдера,

- методы "совмещеного" вычисления ДОП.

Редукция Кули-Тьюки сводит, например, вычисление одномерного ДПФ длины N = рк к вычислению преобразований к—1 длины = р и, как будет показано в диссертационной работе, неявно использует арифметические свойства представления значений преобразуемого сигнала, согласованные с конкретной машинной арифметикой, а также топологические свойства множества индексов входных и выходных данных.

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

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

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

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

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

- вычисление некоторого вспомогательного преобразования со значениями в этой алгебре;

- отображение полученого результата в поле, содержащее значения выходного сигнала (интерпретация).

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

Именно такая трехэтапная процедура принята автором за основу унифицированного описания быстрых алгоритмов дискретных преобразований. Параметры, характеризующие выбранную алгебраическую структуру, способ вложения данных, принцип интерпретации значений вспомогательного преобразования полностью определяют структуру алгоритма и тем самым параметризуют обширный класс БА ДОП. Следует также отметить, что рассматриваемые автором в качестве вспомогательных структур альтернативные алгебры над полями алгебраических чисел весьма разнообразны и характеризуются большим количеством индивидуальных параметров. Поэтому в диссертации мы понимаем параметрическое описание этих алгебр и определяемых ими алгоритмов как проекции некоторого "универсума" на котором определено (нереализуемое) "метапреобразование", но такое, что стандартные отображения этого универсального объекта (гомоморфизмы, как правило) определяют конкретную алгебру и ассоциированный с ней быстрый алгоритм.

Принятая концепция описания быстрых алгоритмов определяет структуру диссертации и содержание отдельных глав: в первой главе исследуется влияние структурных свойств вспомогательной алгебры (размерность, базис, свойства основного поля, согласованные со спецификой ДОП) на вычислительные характеристики БА; во второй главе исследуются характеристики БА, определяемые алгебраичностыо значений базисных функций ДОП; в третьей главе исследуется связь между структурой БА и топологическими свойствами области определения преобразуемых функций; в четвертой главе исследуется связь характеристик БА ДОП и ассоциированных с ними циклическихсверток с арифметическими свойствами систем счисления в основном поле; в пятой главе разработанная методика синтеза БА анализируется с теоретико-категорийной точки*зрения.

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

Научная новизна. В диссертационной работе предложен новый унифицированный арифметический конструктивный подход к синтезу быстрых алгоритмов достаточно общего класса дискретных преобразований. Тем самым решена проблема формализации описания структуры быстрого алгоритма, как объекта исследования. В рамках предложенного подхода:

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

- введен и исследован новый класс дискретных преобразований, базисные функции которого порождены Галуа-образами гауссовых периодов циклотомических полей (ДПГ); доказано, что такие преобразования обладают инвариантной структурой по отношению к алгоритмам, использующим полиномиальные преобразования; предложен новый альтернативный метод вычисления ДПГ - редукция Галуа; установлены предельные возможности метода Рейдера-Винограда;

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

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

Практическая значимость работы состоит в том, что разработанные в ней методы непосредственно направлены на решение практических задач и, в частности, обеспечивают:

1 ) создание программно-алгоритмических комплексов нового типа систем адаптивной обработки и анализа многомерной цифровой информации;

2) построение новых типов процессоров и отдельных блоков для оперативной обработки и анализа (многомерных) полей;

3) построение банков данных быстрых алгоритмов дискретных преобразований.

Реализация и внедрение отдельных методов, подходов, алгоритмов проводилась в рамках ряда госбюджетных и хоздоговорных НИР в Институте систем обработки изображений РАН и в Самарском филиале * межотраслевой ассоциации "Совинформспутник".

Исследования по теме диссертации поддерживались Российским фондом фундаментальных исследований (проекты 95-01-00367, 97-01-00900). Результаты исследований отражены в ежегодных и итоговом отчете по проектам.

Структура и краткое содержание. Диссертационная работа состоит из введения, 5 глав, заключения и списка использованной литературы, составляющего 241 наименование. Ссылки на работы автора снабжены знаком (*).

Основные результаты главы 4

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

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

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

4. Синтезированы алгоритмы вычисления дискретных сверток, ориентированные на представление данных в рекуррентных системах счисления высших порядков.

Глава 5. Об иерархиях алгебр, параметризующих некоторые классы быстрых алгоритмов дискретных преобразований

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

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

- вычисление вспомогательного преобразования со значениями в этой алгебре;

- отображение спектра вспомогательного преобразования в поле (кольцо), содержащее значения спектра исходного преобразования; неявным образом используется в абсолютном большинстве известных БА дискретных преобразований.

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

Не ставя перед собой задачу подробного описания такой параметризации БА для возможно более широкого класса преобразований, применяемых в практике решения различных прикладных задач, ограничимся подробным описанием параметров, наиболее характерных для предложенной (трехэтапной) методики синтеза БА многомерных ДПФ, к которым сводится весьма обширный класс ДОП.

5.1. Категория быстрых алгоритмов дискретного преобразования Фурье

Определение 5.1. Пятерку множеств

I INJ, ALG, TOP, DO, INT j - SI (5.1 ) будем называть алгоритмом вычисления ДПФ, если:

INJ есть множество параметров, описывающих способ вложения значений преобразуемого массива и значений базисных функций в ассоциативную алгебру а (к) над кольцом к э а индексов входного массива - в топологическую группу Q;

- ALG есть множество параметров, характеризующих алгебру а (к);

ТОР есть множество параметров, характеризующих топологическую группу Q;

- DO есть упорядоченное множество некоторых "стандартных" редукций ДПФ к ДПФ более простых функций;

- ШГ есть множество параметров, определяющих отображение значений спектра вспомогательного преобразования в поле л f э х(ш) (<ß(w) £ f).

Опишем каждое из пяти множеств (5.1 ) в зависимости от внешних по отношению к алгоритму параметров преобразования.

1. Множество INJ = { val, ind, trans } состоит из множества параметров val, определяющих способ отображения значений преобразуемого массива на массив элементов алгебры а(к); множества параметров ind, определяющих способ отображения массива индексов преобразуемого сигнала на массив элементов топологической группы Q; множества параметров trans, определяющих способ отображения значений базисных функций преобразования на множество значений базисных функций вспомогательного преобразования.

Замечание 5.1. Как правило, отображения значений входного массива в алгебру & (к ) и индексов входного массива в группу Q линейны; отображение значений базисных функций в алгебру а (к) является гомоморфизмом алгебр. Следовательно, параметры val, ind, trans вполне определяются морфизмами соответствующих категорий.

2. Множество ALG = { ring, bas, mult, sys > состоит из множества ring параметров, определяющих кольцо к; множества bas параметров, определяющих систему порождающих для алгебры а (к) над кольцом к; множества mult параметров, определяющих правила умножения базисных элементов алгебры; множества вуз параметров, определяющих "систему счисления" в к, то есть параметров, определяющих представление элементов подкольца, изоморфного в индуцированной (позиционной рекуррентной) системе счисления.

Замечание 5.2. Множества параметров ring, bas, mult, sys находятся в однозначном соответствии с теми или иными алгебраическими структурами (или множествами) и полностью ими характеризуются: множество ring - кольцом о<; множество bas - некоторым алфавитным множеством; множество mult - ядром некоторого гомоморфизма свободной полугруппы; множество sys - идеалом в некотором кольце.

3. Множество ТОР = { group, metr, cover > состоит из множества group параметров, определяющих группу Q, множества metr параметров, определяющих семейство метрик на Q, множество cover параметров, выделяющих покрытие области суммирования для вспомогательного преобразования и определяющих конкретную версию алгоритма с расщеплением основания нецелого порядка.

Замечание 5.3. Множества параметров group, metr, cover находятся в однозначном соответствии с теми или иными алгебраическими или топологическими структурами и полностью ими характеризуются: множество group - группой П (или нормальной подгруппой некоторой свободной группы); множество metr - семейством метрических пространств (или семейством идеалов некоторого поля алгебраических чисел, определяющих семейство нормирований); множество cover - образом некоторого линейного

00 т оператора из z в выделяющего номера выбранных метрик мультипокрытия.

4. Множество DO = { gt, ct, rg, sh > состоиит из параметров, идентифицирующих "стандартные" редукции: gt - редукция Гуда-Томаса; ct - редукция Кули-Тьюки; rg - редукция Рейдера-Галуа; sh - шифт-преобразование.

Замечание 5.4. Для простоты предполагается, что для ДПФ к к к длины N = р р . р г сначала выполняется редукция

Гуда-Томаса, сводящая вычисление ДПФ объема Nd к вычислению d dk

ДПФ объемов N = р р ( р = 1,.,г) без дополнительных Р умножений; затем многомерная редукция Кули-Тьюки в версии главы 3 диссертации; затем редукция Рейдера (Галуа) в версии главы 2 диссертации и, наконец, при необходимости -шифт-преобразование.

5. Множество INT = { aut, horn > состоит из множества параметров aut, характеризующих те автоморфизмы алгебры &(к), которые в соответствии с главой 1 диссертации порождают разрешимую систему уравнений для определения "частичных спектров" вспомогательного преобразования; множества horn параметров, определяющих способ реконструкции спектра ДПФ по известным частичным спектрам вспомогательного преобразования.

Замечание 5.5. Множества параметров aut, horn также находятся в однозначном соответствии с теми или иными алгебраическими структурами и полностью ими характеризуются: множество aut - некоторым подмножеством автоморфизмов алгебры а (к) и подмножеством автоморфизмов кольца к (в частности, подмножеством внутренних автоморфизмов алгебры а(к) и подмножеством группы Галуа поля к); множество horn - некоторым множеством гомоморфизмов алгебры ä(k) в алгебру (поле), содержащее значения спектра ДПФ.

Таким образом, четыре из пяти множеств (5.1), а именно, INJ, ALG, DO, INT полностью определяются элементами некоторых категорий (групп, метрических пространств и т.п.) или элементами соответствующих дуальных категорий морфизмов. Это позволяет ввести понятие категории быстрых алгоритмов ДПФ.

Определение 5.2. Категорией Gat FFT будем называть пару

ОЪ FFT, Мог FFT} где множество Ob FFT объектов категории состоит из пятерок множеств (INJ, ALG, TOP, DO, INT) = 91, а множество морфизмов Мог FFT определяется как морфизм, индуцированный на декартовом произведении категорий, элементами которых в силу замечаний 5.1 - 5.5 характеризуются параметры val,ind,trans ; г ing, bas, muí t, sy s ; group,me tr,cover; aut,hom. (5.2)

Определение 5.2 позволяет ввести понятия универсальных объектов (универсально притягивающего и универсально отталкивающего /64/) категории Cat FFT как объектов, множества параметров (5.2), которые характеризуются универсальными объектами соответствующих категорий.

Так как объем преобразования фиксирован, то нет необходимости при синтезе алгоритмов рассматривать универсальные объекты категории Gat FFT для всего множества внешних параметров. Например, кольцо к, как правило, можно считать круговым полем г, содержащим корни степени N из единицы, алгебру д(к) - групповой алгеброй a^.f) над f свободной группы Фр ранга Nd. В этом случае объект категории Gat FFT с указанными параметрами можно интерпретировать как "квазиуниверсально отталкивающий" объект категории Cat FFT, порождающий действием морфизмов достаточно представительный класс БА ДПФ.

5.2. О "метаалгоритме" в групповом кольце над кольцом аделей глобального поля

Поле f, являющееся алгебраическим расширением поля <в, далее будем называть глобальным полем /65/.

Распространение представлений о конкретных алгоритмах ДПФ как о "проекциях" (образах при действии морфизмов) некоторого "универсума" ((квазиУниверсального объекта) на вычисления в конечных полях и полиномиальных кольцах возможно при введении в рассмотрение алгебр над кольцом аделей глобального поля f /65/.

Пусть f - глобальное поле. Для каждого нормирования |.|у поля f обозначим через fy пополнение поля f. Если нормирование |.| неархимедово, то обозначим через кольцо целых элементов поля f .

Определение 5.3. Кольцом аделей Ad(f) поля f называется топологическое кольцо, топологическим пространством которого является ограниченное произведение колец f относительно , а сложение и умножение аделей определяются покомпонентно.

Содержательно кольцо АсЦг) можно интерпретировать как бесконечномерный вектор, каждая из компонент которого принадлежит одному из пополнений г . Существует естественное "диагональное" вложение поля г в АсЦг), отображающее элемент а « г в адель, все компоненты которого равны а. Образ поля г при этом отображении называется кольцом главных аделей.

Для метрической интерпретации модулярных вычислений оказывается полезной следующая форма так называемой сильной аппроксимационной теоремы /65/.

Теорема 5.1. Пусть и0 - некоторое нормирование глобального поля г. Предположим, что даны: a) конечное множество Б нормирований и * и0; b) элементы а^ е для каждого и е Б; c) число е > 0.

Тогда найдется ¡3 «= г, такое, что - а | < е для всех V е Б и |р| < 1 для всех V «■ 5, и * и0. |

Теорема 5.1 представляет собой усиление известной аппроксимационной теоремы для семейства нормирований поля © /15, с.571/, сформулированное в терминах кольца аделей, представляющей, в свою очередь, метрическую интерпретацию китайской теоремы об остатках.

Теорема 5.2. Пусть {|.| ; % = 1,.,Т) множество неэквивалентных нормирований. Для а^.^ <= <& существует элемент а е о, расположенный сколь угодно близко к элементам а относительно нормирований Ы^:

X I» а - < е (т = 1,.,Т). |

В терминах теории нормированных полей вычисления mod p) интерпретируются как вычисления в поле <ß "с р-адической погрешностью т = р-1, вычисления в системе остаточных классов - как приближенные вычисления относительно семейства неархимедовых нормирований, алгоритмы с использованием полиномиальных преобразований, включающие вычисления по модулям идеалов, порожденных циклотомическими полиномами - как приближенные вычисления в полях алгебраических чисел относительно семейства нормирований этих полей и т.д.

Поэтому целесообразно ввести в рассмотрение внекатегорийный по отношению к Cat FFT и нереализуемый "метаалгоритм" (5.1), такой, что ring = ä(<bp,Ad(f)),

ALG = { ring, bas, mult, sys ; norm, err >, где norm - множество параметров, определяющих нормирования глобального поля, относительно которых производятся приближенные вычисления; err - допустимая ошибка вычислений относительно выбранного семейства нормирований.

Метаалгоритм" с з аданной точностью относительно выбранного семейства нормирований аппроксимирует "квазиуниверсально отталкивающие" объекты категории Cat FFT, которые, в свою очередь, под действием морфизмов категории Cat FFT порождают конкретные алгоритмы с заданными значениями параметров.

Иерархия групповых алгебр (колец), соответствующих предложенному описанию категории Gat FFT изображена на рис. 5.1.

Рис.5.1. Иерархия алгебр, связанная с параметризацией быстрых алгоритмов категории Cat FFT.

1. Агаян С. С. Оптимальные алгоритмы быстрых ортогональных преобразований и их реализация на ЭВМ // Кибернетика и вычислительная техника.- М.: Наука, 1.86.- вып. 2. -с. 231-301.

2. Агаян С.С., Айзенберг Н. Н., Алавердян С. Б. Дискретное преобразование Фибоначчи // Проблемы теоретической кибернетики: Тезисы докладов III Всесоюзной конференции.-Горький, I988.-4.Iс. 5-67

3. Агаян С.С., Геворкян Д.З. Сложность и параллельные алгоритмы дискретных ортогональных преобразований // Кибернетика и выч. техника.-Вып 4.- М: Наука, 1988.-с.124-169.

4. Агаян С. С. Успехи и проблемы быстрых ортогональных преобразований// Распознавание, классификация, прогноз. М.: Наука,- 1990.- вып. 3.- с. 146 - 214.

5. Агаян С.С., Баядан Г.Л., Геворкян Д.З. Вопросы устойчивости суммирования ортогональных рядов и вычисления линейных преобразований //Кибернетика и выч. техника.-Вып 5.-М: Наука, 1990.- с.132-168.

6. Айзенберг H.H.,Семирот М.С. Цифровая обработка сигналов на конечных группах // Применение ортогональных методов при обработке сигналов и анализе систем.- Свердловск, 1980. -вып. 1.- с.96-105.

7. Айерлэнд К., Роузен. М. Классическое введение всовременную теорию чисел. М.: Мир, 1987.-415 с.

8. Артин Э. Геометрическая алгебра.- М.: Наука,1969.--283 с.

9. Ахмед Н. Рао К. Р. Ортогональные преобразования при обработке цифровых сигналов,- М.: Связь, 1980.- 248 с.

10. Боревич 3. И., Шафаревич И. Р. Теория чисел. М.:

11. Блейхат Р. Э. Алгебраические поля, обработка сигналов, контроль ошибок //ТИМЗР.- 1985.- т. 73.- N 5.- с. 30-53.

12. Блейхут Р. Быстрые алгоритмы цифровой обработки сигналов.- М.: Мир 1987.- 448 с.

13. Брейсуэлл Р. Преобразование Хартли.- М.: Мир, 1990.175 с.

14. Брюхович Е.И. Фибоначчиево счисление в вычислительнойтехнике: мифы и реальность // УСиМ.- 1992.- N 3-4.-с. 15-26.15. ван дер Варден Б.Л. Алгебра. М.: Наука,- 1976.-648 с.

15. Вариченко Л. В., Лабунец В. Г., Раков М. А. Абстрактные алгебраические системы и цифровая обработка сигналов.-Киев: Наукова думка, 1986. 247 с.

16. Вейль Г. Классические группы: их инварианты и представления.- М.: ГИМЛ,1947,- 408 с.

17. Виленкин Н.Я. Об одном классе полных ортонормированных систем // Изв. АН СССР.-1947,-N 11,-с.363-368.

18. Виноградов И.М. Основы теории чисел. М.: Наука, -1965.-172 с.

19. Власенко В. А., Лаппа Ю. М., Ярославский Л. П. Методы синтеза быстрых алгоритмов свертки и спектрального анализа сигналов.- М.: Наука, 1990.- 180 с.

20. Гельфонд А.О. Исчисление конечных разностей.- М: Наука, 1967.- 375 с.

21. Гречишников А. И. Модифицированные алгоритмы БПФ с уменьшенным числом операций умножения // Радиотехника и электроника.- 1983.- т.28.- N I.- с. 195-197.

22. Григорян A.M. Алгоритм вычисления двумерного преобразования Фурье // Радиоэлектроника.- 1984,-т.27,- N 10, -с.52-57.

23. Григорян A.M.Григорян М.М. Двумерное преобразование Фурье в тензорном представлении и новые ортогональные функции // Автометрия,-1986,- N I,-с.21-27.

24. Григорян A.M. Новые алгоритмы вычисления дискретного преобразования Фурье // Журнал выч. матем. и матем. физ.- 1986,- т.26,- N 9,-с. 1407 1412.

25. Григорян A.M. Оптимальный алгоритм вычисления двумерного дискретного преобразования Фурье// Изв.вузов, Радиоэлектроника.-1986,-т.29,-N 12,-с.20-25.

26. Григорян А. М. Алгоритм вычисления двумерного дискретного преобразования Фурье с произвольными порядками // Журнал выч. матем. и матем. физ.- 1991.-т.31.- N 10. с. 1576 1581

27. Дагман Э.Е. Кухарев Г.А. Быстрые дискретные ортогональные преобразования // Новосибирск.: Наука, 1983.- 232 с.

28. Дэвенпорт Дж.,Сирэ И.,Турнье Э. Компьютерная алгебра.-М.: Мир, 1991.- 350 с.

29. Дьедонне Ж. Геометрия классических групп.- М.: Мир, 1974.- 204 с.

30. Егиазарян К. 0., Алавердян С. Б. Дискретные тригонометрические преобразования // Мат. вопросы кибернетики и выч. техники.- Ереван, 1990.- с. 3-17.

31. Егиазарян К. 0. О новом подходе к синтезу дискретныхтриигонометрических базисов // Мат. вопросы кибернетики и выч. техники.- Ереван, 1990.- с. 18 28.

32. Жевлаков К.А.,Слинько A.M.,Шестаков И.П.,Ширшов А.И. Кольца, близкие к ассоциативным. М.:Наука,1978.

33. Журавлев Ю. И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. 1-3 // Кибернетика.- 1977.- N 4.- с. 5-17; N 6.- с. 21-27; 1978.- N 2.- с.35-43.

34. Журавлев Ю. й. Об алгебраическом подходе к решениюзадач распознавания или классификации // Проблемы кибернетики. М.: Наука, 1978.- вып.33.- с. 5-68.

35. Журавлев Ю.И. Об алгебраических методах в задачах распознавания и классификации // Распознавание, классификация, прогноз.- М.: Наука,- I988.- вып. I.- с. 9-16.

36. Задирака В.К. Теория вычисления преобразования Фурье.

37. Киев: Наукова думка, 1983.

38. Зайцев Г.В.,Пагулин Н.Е. Класс алгоритмов быстрогопреобразования Фурье действительной последовательности //Пробл.передачи информ.-1983.-т.19.-N 1.-е.49-60.

39. Залманзон Л: А. Преобразования Фурье, Уолша, Хаара иих применения в управлении, связи и других областях.-М.: Наука, 1989.- 494 с.

40. Иваненко В.Г. Рекуррентное вычисление дискретного преобразования Фурье. M.: МИФИ,1987,- Препр.014~87.-16 с.

41. Икрамов Х.Д. Численное решение матричных уравнений и симплектическая матричная алгебра// Выч. процессы и системы.- Вып 5.-М: Наука, 1987.- с. 154-163.

42. Капорин И. Е. Новый алгоритм быстрого преобразования Фурье // Журн.выч.матем. и мат. физики.- 1980.- т.20.-N 4.- с. I054-1058.

43. Картеси Ф. Введение в конечные геометрии.-М: Наука, 1980.-320 с.

44. Кнут Д. Искусство программирования для ЭВМ.- том 2.-Получисленные алгоритмы М.: Мир, 1977.-724 с.

45. Кнут Д. Искусство программирования для ЭВМ.- том 3.-Сортировка и поиск. М.: Мир, 1977.- 8*4 с.

46. Коблиц Н. р-адические числа, р-адический анализ и дзета-функция. М.: Мир, 1982. - 192 с.

47. КозлюкП.В., Нагирняк П. П. Особенности вычисления некоторых элементарных функций в кодах "золотой" пропорции // Электр, моделирование.- 1990.- N 4.- с. 105-1087

48. Колмогоров Г.С., Лабунец В.Г. Вывод оценки сложности алгоритмов многомерного БПФ//Математические вопросы автоматизации проектирования и испытаний.- Минск, 1986.- с.60-69.

49. Кончак В.С.,Демко В.М. Эффективные алгоритмы преобразования Фурье действительных массивов // Цифровые методы в управлении радиолокации и связи.-Свердловск.-1986.-с.37-48.

50. Кренкель Т. Э. Спектральный анализ на конечных коммутативных грушах // Радиотехника.- 1975.- т.30.- N 6.-с. 19 23.

51. Кричевский Р. Е.Сжатие и поиск информации.- М.: Радио и связь, 1989.- 168 с.

52. Крот A.M.Минервина Е.Б. Синтез алгоритмов дискретного преобразования Фурье для действительных последовательностей на основе полиномиальной алгебры// РЭ.-1987.-т.22.- N 6.-1217-1229.

53. Крот А. М. Дискретные модели динамических систем на основе полиномиальной алгебры.- Минск: Навука i тэхнХка, 1990.- 311 с.

54. Кухарев Г. А., Шмерко В. П., Зайцева Е. Н. Алгоритмы и систолические процессоры для обработки многозначных данных. Минск: Навука i тэхн!ка, 1990.- 296 с.

55. Лабунец В.Г. Обобщенные и быстрые преобразования Фурье на произвольной конечной абелевой группе//Тармонический анализ на группах в абстрактной теории систем. -Свердловск, 1976.- с.24-43.

56. Лабунец В.Г. Колмогоров Г.С. Стратегии настройки многопараметрических преобразований // Применение ортогональных методов при обработке сигналов и анализе систем.- Свердловск: УПИ.-1983,- с.4-26.

57. Лабунец В. Г. Единый подход к алгоритмам быстрыхпреобразований // Применение ортогональных методов при обработке сигналов и анализе систем.- Свердловск: УПМ, 1980,- с. 4 14.

58. Лабунец В. Г. Фурье подобные преобразования // Применение ортогональных методов при обработке сигналов ианализе систем.- Свердловск: УПИ, 1981,- с. 4 14

59. Лабунец В. Г. Теоретико числовые преобразования над полями алгебраических чисел // Применение ортогональных методов при обработке сигналов и анализе систем.-Свердловск: Изд-во У1Ш.1981. - с. 44-54.

60. Лабунец В. Г. Алгебраическая теория сигналов и систем: Цифровая обработка сигналов.- Красноярск: Изд-во Красноярск, ун та, 1984.- 244 с.

61. Лабунец В. Г. Функции с двойной ортогональностью в обобщенном гармоническом анализе // Цифровые методы в управлении, радиолокации и связи. Свердловск: УПИ, 1986,- с. 4 - 15.

62. Лабунец В.Г. Быстрое многомерное преобразование Фурье, основанное на быстром преобразовании Радона // Цифровые методы в управлении, радиолокации и связи.- Свердловск: УПИ.- 1986.

63. Лабунец В. Г. Алгебраическая теория сигналов и систем.-Свердловск: Изд-во УрГУ, 1989.- 196 с.

64. Ленг. Алгебра. М.: Мир, 1965.-564 с.

65. Ленг С. Алгебраические числа.- М.: Мир, 1966. 225 с.

66. Ленской Д. Н. Функции в неархимедовски нормированных полях.- Саратов: Изд-во СГУ, 1962.- 109 с.

67. Левенштейн В.И. Применение матриц Адамара к одной задаче кодирования // Проблемы кибернетики, М.:

68. Наука,- 1961.- вып.5. с.123-136.

69. Маккеллан Дж. X., Рейдер Ч. М. Применение теории чисел в цифровой обработке сигналов.- М.: Радао и связь, 1983.- 263 с.

70. Лидл Р., Нидеррайтер Г. Конечные поля.- В 2-х т.- М.: Мир, 1988.- 818 с.

71. Мануйлов Н. Ф. О системах счисления в полях алгебраических чисел // Мариупольск. металлург, ин-т.- Деп. в УкрНИЖШ 09. 04. 90 N615 Ук 90.- 1990.- 34 с.

72. Нуссбаумер Г. Быстрое преобразование Фурье и алгоритмы вычисления сверток.- М.: Радио и связь, 1985.- 248 с.

73. Першина М.В.,Чичева М.А. Декомпозиция двумерного ДПФ с представлением данных в алгебре кватернионов // Компьютерная оптика.-1995.-N14-15.-ч.2.-с.13-21.

74. Савин В.В.,Титов М.А. Метод построения эффективных алгоритмов Винограда для вещественных данных больших размеров// Цифровые методы в управлении радиолокации и связи.-Свердловск.- 1986.-с.28-37.

75. Сергеев В. В., Усачев А. В. Новый алгоритм быстрого преобразования Хартли // Компьютерная оптика.- 1990.-вып. 7,- с. 66-67.

76. Серпинский В. Что мы знаем и чего мы не знаем о простых числах.- Л.: Наука.-1963.- 91 с:

77. Спивак М. Математический анализ на многообразиях. М: Мир, 1968.-164 с.

78. Стахов А. П. Введение в алгоритмическую теорию измерения.- М.: Советское радио, 1977.- 288 с.

79. Стахов А. П., Лужецкий В. А. Машинная арифметика ЦВМ вкодах Фибоначчи и "золотой" пропорции.- М.: Изд-во АН СССР, I981.-64 с.

80. Стахов А.П. Коды золотой пропорции.- М.: Радио и связь, 1984.- 151 с.

81. Стахов А.П. Помехоустойчивые коды (Компьютер Фибоначчи). М.: Знание, 1989.- 64 с.

82. Стахов C.B. Позиционные системы счисления в теле кватернионов// Тезисы докладов Международной конференции "Современные проблемы теории чисел".-Тула.-1993.-с.151.

83. Стахов C.B. Евклидовость подколец кватернионов, порожденных некоторыми конечными подгруппами // Деп. ВИНИТИ N 398-85,-26 с.

84. Судаков Ю. А. Алгоритм быстрого преобразования Фурье с минимальным числом умножений//Радиотехника и электроника. 1990.- т. 35.- N 6.- с. 1260 - 1266.

85. Судаков Ю. А. Формы минимального алгоритма быстрого преобразования Фурье // Радиотехника и электроника.-1992.- т. 3?.- N I.- с. II7-I25.

86. Торгашев В.А. Система остаточных классов и надежность ЦВМ. -М: Сов. радио,1973.- 120 с.

87. Трахтман А. М., Трахтман В. А. Основы теории сигналов на конечных интервалах.- М.: Советское радио, 1975.207 с.

88. Турмухамбетов Р.Н. К вопросу о построении непозиционнойсистеме счисления в кольце кватернионов// Теория кодирования и оптимизация сложных систем. Алма-Ата: Наука, 1977, с. 214-218.

89. Турмухамбетов Р.Н. Системы счисления с кватернионными основаниями ±1,±i,±j,±k // Теория кодирования и оптимизация сложных систем. Алма-Ата: Наука, 1977, с. 211-214.

90. Фараджиев Р.Г. Аналитические способы вычисления процессов в линейных последовательных машинах // Изв. АН СССР. Техн. Кибернетика, 1965, N 5. с. 74-80.

91. Фараджиев Р.Г., Пдпкин Я.З. Преобразование Лапласа-Галуа в теории последовательных машин // ДАН СССР, 1966,166, N 36 с.45-52.

92. Тыртышников Е.Е. Об алгоритмах дискретного преобразования Фурье // Численные методы алгебры.- М.: Изд-во МГУ, 1981.- с. 10-16.

93. Хармут X. Теория секвентного анализа.-М.: Мир,-1980.-574 с.

94. Чичева М.А. Быстрые алгоритмы дискретных косинусных преобразований //Компьютерная оптика.-1996.-N16,с. 109-114.

95. Шабашев А.В. Эффективная реализация двумерного дискретного преобразования Фурье массива 250 * 250 //

96. РОАИ-2-95.- Ульяновск.-1995.- 4.2. -с.198.

97. Эдварде Г. Последняя теорема Ферма: генетическое введение в алгебраическую теорию чисел. М.: Мир, 1980.-484 с.

98. Ярославский Л. П. . Введение в цифровую обработку изображений.- М.: Советское радио, 1979 312 с.

99. Ярославский Л. П. Цифровая обработка сигналов в оптике и голографии: введение в цифровую оптику.- М.: Радио и связь, 1987. 297 с.

100. Agaian S.S.,Bayadian H.L. Generalised orthogonal Haar systems, synthesis, metric and computing properties // Colloq. Math, sosietatis Janos Bolyai,-1985,-pp.97-113.

101. Agaian S.S., Alaverdian S.B. Past orthogonal Fibonacci transforms // Osaka.-1988.-p.335-352.

102. Agayan S.S.,Grigoriyan A.M. Discrete unitary transformations and their relation to covering of fundamental periods (Part 1)// Pattern Recogn. and Image Analysis. -1993.-v4.-N 1.- pp.16-23.

103. Agayan S.S.Grigoriyan A.M. Discrete unitary transformations and their relation to covering of fundamental periods (Part 11)// Pattern Recogn. and Image Analysis. -1993.-v4.-N 1 .- pp.24-31.

104. Agarval R.G., Cooley J.W. New algorithms for digital convolution // IEEE Trans.-ASSP-25.-1997.-pp.392-410.

105. Alfredson L.-I. A fast Fermat number transform for long sequences // Proc. EUSIPCO-94, Edinburg, Scotland, v.III, 1994, pp.1579-1581.

106. Alfredson L.-I. VLSI architectures and arithmetic operations with application to the Format number transform. LInk"oping Studies in Sei. and Technology, Dissertation No.425, 1996, 279 p.

107. Ararnberpola B.,Reiner P.J.W. Multidimensional fast Fourier transform algorithm // Electron. Lett., -1979, -V.15,- N3,-pp.382-383.

108. Auslander L.E., Feig E., Vinograd S. New algorithms for the multidimensional discrete Fourier transform // IEEE Trans. ASSP-31,- 1983,- pp.388-403.

109. Bachman G. On the coefficients of cyclotomic polinomials.- AIS, 1994.-80 p.

110. Batten L.M., Beutelspacher A. The theory of finite linear spaces.-Cambridge Math., 1994.-240p.

111. Bayod J.M., De Grande-De Kimpe N., Martinez-Maurlea J. p-adic Functional Analysis.-Marcel Dtikker, Inc., 1992. -236 p.

112. Bergland G.D. A fast Fourier transform algorithm for real valued series // Commun.ACM.-1968.-v.11.- N 10.-pp.703-710.

113. Bergland G.D. A radix-eiht fast Fourier transform subroutine for real-valued series //IEEE Trans. Audio and Electroacoust.-1969.-v.17.-N 2.-pp.138-144.

114. Bergman G. A number system with an irrational base // Math. Magaz.- 1957.- N 31 p. 98-119.

115. Bergum G.E.,Philippou A.N.,Horadam A.F. Application of Fibonacci numbers.-Fibonacci Ass.- 1993.-625 p.

116. Berkovich V. Spectral theory and analytic geometry over non-archimedean fields.- Amer. Math. Soc.- Providence. -RI.-1990.

117. Bertrand-Mathis A. Comment ecrire les nombres entiers dans une base qui n'est pas entierr // Acta math, hung.- 1989.- v.- 54.- N 3-4.- p 237-241.

118. Bicknell M.,Hoggatt V.E.(Eds). A primer for the Fibonacci Numbers.-Fibonacci Ass.- 1972.

119. Bicknell M.Hoggatt V.E.(Eds). Fibonacci's problem book. -Fibonacci Ass.- 1974.

120. Bondarenco B.A. Generalised Pascal triangles and piramids their fractals, graphs and applications.-Fibonacci Ass.- 1993.-250 p.

121. Boussakta S., Holt A.G.J. Calculation of the discrete Hartley transform yia Fermat number transform using VLSI chip //IEE Proc., V. 135, Pt.G, N 3, 1988, pp. 101 -103.

122. Briggs W.L., Van Henson E. The DFT: An owner's manual for the discrete Fourier transform.-SIAM, 1995. 434 p.

123. Brillart J.,Lehmer D.H.,Selfridge J.L.,Tuckerman B., Wagstaff S.S. Factorisation of bn±1, b=2,3,5,6,7,10,11, 12 up'high powers // Contemp.Math.-AMS.-v.22.-1988.

124. BritaiiSk V. On the discrete cosine transform computation // Signal Processing. 1993, - N 40, -pp.183-194.

125. Brosseau A.B.Introduction to Fibonacci discovery.1. Fibonacci Ass.- 1965.

126. Brosseau A.B. Linear recursion and Fibonacci sequences.-Fibonacci Ass.- 1971.

127. Brosseau A.B.Fibonacci and related number theoretic tables.-Fibonacci Ass.- 1972.

128. Buelow Т.,Sommer G. Algebraically extended representations of multi-dimensional signals //Proc. SCIA'97.-Lappeenranta, Finland.-1997.-pp.559-566.

129. Buelow Т.,Sommer G. Das Konzept einer zweidimensionale Phase unter Vervendung einer algebraisch erweiteren Signalrepresentation// 19. DAGM Simposium Mustererkennung. -Braunschweig.-1997.-S.351-358.

130. Buelow Т.,Sommer G. Multi-dimensional signal processing using an algebraically extended signal representation /'/Proc. AFPAC' 97., -Kiel, Germany. -Springer, -LNGS 1315.--1997. -pp. 148-163.

131. Gooley J.W., Tukey J.W. An Algorithm tor the Machine Computation of Complex Fourier Series // Math. Comp.-1965.- N 19.- p. 297-301 .

132. Chichyeva M.A.,Pershina M.V. On various schemes of 2D-DFT decomposition with data representation in the quaternion algebra //Image Proc. and Commun.-1996. -v.2.- N 1.-13-20.

133. Chichyeva M.A. Algorithms of discrete cosine transform with data representation in Eisenstein's codes //Image

134. Proc. and Commun.-1996. -v.2.- N 4.-53-60.1. V V

135. Cizek V. Discrete Fourier transforms and their applications. -A.Hilger Publ.,1986.-141 p.

136. Dubois E.Venetsanopoulos A.N. A new algorithm for the radixS PPT // IEEE Trans.-1978.-ASSP-26.- N 3. -pp.222-225.

137. Dubois E., Venetsanopoulos A.N. The generalized discrete Fourier transform in ring of algebraic integers// IEEE Trans., ASSP-28, N 2, 1980, pp. 169-175

138. Duhamel L., Hollman H. Split-radix FFT algorithm // Electron Lett.- 1984.- v.20.- N17- p. 14-16.

139. Duhamel P. Implementation of split-radix FFT algorithm for complex, real, and real-symmetric data // IEEE Trans. ASSP-34.-1984.-v.34.-N 2.-pp.285-295.

140. Ell T.A. Quaternion-Fourier transform for analysis of 2-dimensional linear time-invariant partial-differential systems//Proc. of the 32th IEEE Conf> on Decision and Control.-1993.-v.1-4.-pp.1830-1841.

141. Ersoy O.K. Transform Image enhancement // Opt. Engin.-1992.- v.31. N 3.-pp614-626.

142. Feig E.,Ben-0r M. On algebras related to the discrete cosine transform //Linear Algebra and Appl.-1997.--V.226.-pp.81-106.

143. Fraenkel A. S. Systems of numeration // Amer. Math. Monthly.- 1985.- v. 92.- p. 105-114.

144. Fraenkel A. S. The use and usefulness of numeration systems // Inf and Comp.- 1989.- v. 81.- N 1p 46-61.

145. Gathen J., von sur. Efficient and optimal exponent!ation in finite fields // Gomput. complexity.- 1991.-Y.-1N 4.- p. 360-394.

146. Good I.J. The interaction algorithm and practical Fourier analysis// J.Royal Stat.Soc.-1958.-v.B-20.-pp.361-372.

147. Harris D.B.,McClellan J.H.,Chan D.S.K.„Schluesser H.W. Vector radix fast Fourier transform /7 IEEE Int. Oonf. ASSP,-1977,-pp.548-551.

148. Heideman M.T. Computation of odd-length DOT from a real-valued DFT of same lenght//IEEE Trans. Signal Process.-1992.- v.40.-N 1.-pp.54-61.

149. Heideman M.T.,Burrus C.S.,Johnson H.W. Prime factor FFT algorithms for real-valued series/ZProc. IEEE Int.Conf. Acoustics,Speech, and Signal Processing.-V.2.-pp.28A.7/1-28A.7/4.

150. Hoggatt V.E. Fibonacci and Lucas Numbers.- Fibonacci Ass.- 1972.

151. Hoyer E.,Berry W. An algorithm for two dimensional FFT //IEEE Int. Conf. ASSP,-1977,-pp.552-555.

152. Hou S. A fast recursive algorithm for computing the discrete cosine transform // IEEE Trans.-1986. -ASSP-35,- N10,- pp. 1454-1461.

153. Jacobson N. Composition algebras and their automorphisms// Rend.Circ.Math.Palermo.-1958.- v.7. -pp.55-80.

154. Jacobson N. Structure and representation of Jordan algebras.-Providence, R.I.,1968.

155. Johnson H.W., Burrus C.S. The design of optimal DFT algorithm using dynamic programming // IEEE Trans.

156. ASSP-25,-1977,-pp.152-165.

157. Joo I.,Snitser P. Expansion with respect to non-integer bases // Graz math.Bericht.-1996.-v. 329.-pp.1-35.

158. Lenz R. Group theoretical methods in image processing.-Springer.-LNCS -V.413.-138 p.

159. McDuff D. Introduction to symplectic topology. -Oxford, 1995.-434 p.

160. Martens J.B. Discrete Fourier transform algorithms for real valued sequences /'/' IEEE Trans.-1984.-ASSP-32.-N 2.-pp.390-396.

161. Merserau R.,Speake T.C. A unified treatment of Cooley-Tukey algorithms for the evalution of the multidimensional DFT//IEEE Trans. ASSP-29,- 1981,- pp. 1011-1018.

162. Nasrabadi N. M., King R. A. Past digital convolution using p-adic transforms // Electronics Lett.- 1983.-v.19.- N7.- p. 266-267.

163. Nussbaumer H.J.,Quandalle P. Past computation of discrete Foureir transforms using polynomial transforms //IEEE Trans. ASSP-27,- 1979,- pp.169-171.

164. Porteous I.R. Clifford algebras and classical groups.-Cambridge Univ. Press.-1995.-295 p.

165. Prakash S.,Rao V.V. A new radix-6 FFT // IEEE Trans. -1981.-ASSP-29.- N 4.-pp.939-941.

166. Rader C.M. Discrete convolution via Mersenne trans-orm // IEEE Trans. Comp. G-21, 1972, pp.1269-1273.

167. Rader C.M. On the application of the number theoretic methods of high-speed convolution to two-dimensional filtering // IEEE Trans, on Circuits and Systems.1. V.22.-1975.-p.575.

168. Rao K.R., Yip P. Discrete cosine transform. Academic Press, San Diego, 1990.

169. RIvard G.E. Direct fast Fourier transform of bivariate functions // IEEE Trans. ASSP-25,- 1977,- pp.250-252.

170. Sangwine S.J. Fourier transforms of color images using quaternion or hypercomplex numbers // Electron. Lett.-1996.-Y.32.- N 21.-1979-1980.

171. Sasao Т., Bulter J. On the proportion of digits in redudant numeration systems // Fib. Quart.-1997.-v.35.-N 2.-pp.172-180.

172. Schoenhage A., Strassen V. Schnelle multlplikation grosser Zahlen // Computing., 1966,7, 3/4, S. 281-292.

173. Shabashev A.V. The 250x250 FFT algorithm //Pattrn Recogn. and Image Analysis.- 1996.- v.6.- N 1.- p.200.

174. Sipp F., Wade W.R., Simon P. Walsh series: Anintroduction to the dyadic harmonic analysis.- A.Hilger Publ.,1990.-528 p.

175. Skavantzos A., MItosh N. Computing large polynomial products using modular arithmetic// IEEE Trans. CS-39.1992.- N 4.- 252-254.

176. Skula L. Linear transforms and convolution // Math. Slovaca,- 1987.- v.37.- N 1.- p. 9-30.

177. Smetanin Yu.G. The Fibonacci lower bound for the unique reconstruction of a binary word given its fragments // Abstracts of the 7th Int. Conf. on Fibonacci Numbers and Their Applications.-Graz,Austria.-1996.- p.36.

178. Sommer G., Bayro-Oorrochano E., Buelow T. Geometricalgebra as a framework for the perception-action cycle // Proc.Workshop on Theoretical Found. of Comp. Vision. -Vien.-1997.-Springer Verlag.

179. Soo Chang Pei. Exact fast digital convolution by using p-adic numbers and polynomial transformations // IEEE Trans. ICASSP'85.- 1985.- v.2.- p. 760-763.

180. Sorensen H. V., Heideman M. T., Burrus C. S. On computing the Split-radix PPT // IEEE Trans.- ASSP-34.-1986.-N 1.- p. 152-156.

181. Stinson D.R. Some observation on parallel algorithms for fast exponentiation in ©f (2n) /7 SI AM J. Comp.-1990.- v. 19.- N 4.- p. 711-717.

182. Suheiro N. Hatori M. Past algorithm for DPT ana other sinusoidal transforms // IEEE Trans. ASSP-34,- 1986, -pp.642-644.

183. Suzuki Y.,Sone T.,Kido. A new PPT algorithm of radix 3, 6,and 12 //IEEE Trans.-1986.-ASSP-34.- N 2.-pp.380-383.

184. Szabo N.S.,Tanaka R.J. Residue arithmetic and its applications to computer technology.-NY:Macirnwhill, 1967.

185. Thomas L. H. Using a Comhuter to Solve Problems In Physics, in Applications and of Digital Computer // Ginn and Co.- Boston, Mass. 1963.

186. Towers P.J., Pajayakrit A., Holt A.G.J. Cascadable NMOS VLSI circuit for Implementing a fast convolver using the Fermat number transform // IEE Proc., V. 135, Pt.G, N 2, 1987, pp.57-66.

187. Van Loan C. Computational frameworks for the fast

188. Fourier transform.-SIAM, 1992. 273 p.

189. Wang Z. Fast algorithms for the discrete W transform and for the discrete Fourier transform // IEEE Trans.-ASSP-32.- 1984.- N 4.- p. 803-816.

190. Winograd S. On Computing the Discrete Fourier Transform/ /Proc .Nat.Acad.Sci. USA.-1976.-v.73.-p.1005-1006.

191. Winograd S. On the Discrete Fourier Transform // Math. Comp.- 1978. N 32.- p.175 199.

192. Winograd S. Arithmetic complexity of computations. -SIAM, 1980. 93 p.

193. Wu J.-L.,Pei S.-C. Fast based polinomial transform for 2-D prime length discrete Fourier transform // Electr. Le11.-1984.-v.20.-N 22.-pp.933-935.