Электронная библиотека Веда
Цели библиотеки
Скачать бесплатно
Доставка литературы
Доставка диссертаций
Размещение литературы
Контактные данные
Я ищу:
Библиотечный каталог российских и украинских диссертаций

Вы находитесь:
Диссертационные работы России
Технические науки
Радиотехника и телекоммуникации

Диссертационная работа:

Байкова Аниса Талгатовна. Синтез эффективных алгоритмов быстрого преобразования Фурье и циклической свертки и их применение в устройствах сопряжения аналоговых и цифровых систем передачи : ил РГБ ОД 61:85-5/2137

смотреть содержание
смотреть введение
Содержание к работе:

Стр.

ВВЕДЕНИЕ 6

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

  1. Постановка задачи 15

  2. Основные определения 20

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

  1. Модульная арифметика полиномов 22

  2. Синтез прямоугольных преобразований 25

  3. Синтез алгоритмов быстрого преобразования Фурье на основе прямоугольных преобразований 29

  1. "Гнездовой" алгоритм вычисления циклической свертки длинных последовательностей 36

  2. Алгоритмы быстрого преобразования Фурье длинных последовательностей

1.5.I. Алгоритм с множителями поворота 38

1.5. 2.Алгоритм простых множителей 41

1.5.3. "Гнездовой" алгоритм Винограда 44

1.6. Сопоставление алгоритмов быстрого преобразования
Фурье :

  1. Объем вычислений 46

  2. Объем памяти 48

  3. 3|)фекты конечной разрядности 50

Вы в о д ы 54

2. НОВЫЙ МЕТОД СИНТЕЗА ПРЯМОУГОЛЬНЫХ ПРЕОБРАЗОВАНИЙ

2.1. Теоретические основы предлагаемого метода 56

2.I.I. Свойство цикличности свертки 56

  1. Транспозиция алгоритма 57

  2. Метод решения системы линейных уравнений,

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

2.2. Синтез прямоугольных преобразований

  1. Синтез матриц А и В 61

  2. Вычисление матрицы С 69

  3. Пример синтеза 72

  1. Вопросы реализации предлагаемого метода на ЭВМ 76

  2. Оценка мультипликативной сложности новых алгоритмов

быстрого преобразования Фурье 82

В ы в о д ы 88

3. СИНТЕЗ ПРЯМОУГОЛЬНЫХ ПРЮБРАЗОВАНИЙ НАД АЛГЕБРАИЧЁСШМИ
РАСШИРЕНИЯМИ ПОЛЯ РАЩОНАЛШЫХ ЧИСЕЛ

  1. Введение алгебры над алгебраическими расширениями .. 90

  2. Швод базового алгоритма 93

  3. Оценка вычислительной сложности 95

  4. Синтез прямоугольных преобразований над полем корней

N-ой степени из единицы, где N -простое 98

  1. Синтез прямоугольных преобразований над полем корней 8-ой степени из единицы Ю4

  2. Оценка вычислительной сложности новых алгоритмов

для преобразования многомерных последовательностей . Ю6

3.7. Синтез прямоугольных преобразований над полем

чисел Эйзенштейна 115

Вы в о ды 118

4. СИНТЕЗ И АНАЛИЗ АЛГОРИТМОВ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ
ДЛЯ ЦИФРОВЫХ УСТРОЙСТВ СОПРЯЖЕНИЯ АНАЛОГОВЫХ И ЦИФРОШХ
СИСТЕМ ПЕРІЩАЧИ

  1. Применение дискретного преобразования Щурье в устройствах сопряжения 120

  2. Разработка теоретических вопросов

  1. Модификации алгоритма простых множителей для действительных и эрмитово-симметричных последовательностей 129

  2. Анализ вычислительных ошибок алгоритма простых множителей в системе счисления с фиксированной запятой 136

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

4.3. Синтез и анализ алгоритмов быстрого преобразования
Фурье для N =14, 28, 72 и 144

  1. Синтез базовых алгоритмов 150

  2. Объем вычислений 163

  3. Анализ вычислительных ошибок 163

4.4. Разработка процессора 144-точечного быстрого
преобразования Фурье для цифрового многоканального
модема 1?2

  1. Вычислительный алгоритм 1?2

  2. Вычислительные ошибки. Выбор разрядности процессора 176

  3. Моделирование процессора быстрого преобразования Фурье на ЭВМ 179

  4. Описание работы процессора 183

  5. Основные параметры процессора быстрого преобразования Фурье 190

4.5. Разработка эффективного алгоритма тактовой
синхронизации цифрового многоканального модема .... 193
Вы в о ды 198

ЗАКЛЮЧЕНИЕ 201

ЛИТЕРАТУРА 204

ПРИЛОЖЕНИЯ

П. I. Алгоритм вычисления комплексного произведения над

полем GKS, ---,^-2) sis

П.2. Аягоритм вычисления комплексного произведения над

полем Q (I, К, 9) 215

П.З. Алгоритмы вычисления 8 и 16 -точечных циклических

сверток над полем Q Сі» К, 0) 216

П. 4. Црямоугольные преобразования над полем чисел

Эйзенштейна 219

П. 5. Результаты моделирования процессора 144-точечного

быстрого преобразования Фурье 223

П.6. Описание и текст программы моделирования процессора быстрого преобразования Фурье на ЕС ЭВМ .... 230 П. 6.1. Общее описание работы программы

моделирования 230

П.6.2. Пример 231

П.6.3. Текст программы моделирования на языке

ФОРТРАН - ІУ 232

П.7. Программа процессора быстрого преобразования

Фурье на языке микрокоманд 250

П.8. Программа процессора тактовой синхронизации на

языке микрокоманд 255

Введение к работе:

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

Эта задача нашла отражение в "Основных направлениях экономического и социального развития СССР на I98I-I985 годы и на период до 1990 года", принятых на ХХУІ съезде КПСС, в которых в качестве одной из важнейших задач в области естественных и технических наук называется задача "совершенствования вычислительной техники,... математического обеспечения, средств и систем сбора, передачи и обработки информации" /I/.

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

Такими устройствами сопряжения являются трансмультиплексоры (ТМ) и устройства преобразования сигналов (УПС) , или, модемы. Цифровая реализация указанных устройств предпочтительна благодаря таким преимуществам цифровых схем как гарантированная точность и идеальная воспроизводимость характеристик, приспособленность к быстро прогрессирующей интегральной технологии, и возможна лишь на основе эффективных вычислительных алгоритмов /3,4,5/.

ТМ призваны осуществлять взаимное преобразование вида уплот-

нения каналов (частотное разделение каналов «* временное разделение каналов) и основное свое применение найдут в узлах автоматической коммутации, 0 перспективности исследований в области создания ТМ свидетельствует, в частности, У заседание совета главных конструкторов стран членов СЭВ по созданию и внедрению в производство единой системы средств цифровой передачи информации (ноябрь 1983 г., г. Познань, ПНР) , на котором была подчеркнута актуальность применения ТМ в СССР,начиная уже с 1990 г.

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

Известны отечественные разработки многоканальных модемов для каналов тональной частоты /7/ и первичных широкополосных каналов /8/. В настоящее время в связи с увеличением мощности цифровых потоков возникает актуальная задача создания высокоскоростного цифрового многоканального модема для вторичного широкополосного канала /9,10/.

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

на основе быстрых вычислительных алгоритмов двух основных операций ЦОС - дискретного преобразования Фурье (ДШ)и циклической свертки (ЦС) . Поскольку известные вычислительные алгоритмы не обеспечивают достаточно высоких технико-экономических показателей специализированных цифровых устройств на современной и перспективной отечественной элементной базе, то актуальной становится задача синтеза более эффективных алгоритмов Б1Ж> и ЦС.

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

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

Научная новизна работы определяется постановкой и решением следующих вопросов.

I.Предложен новый, легко реализуемый на ЭВМ, метод синтеза субоптимальных прямоугольных преобразований, позволяющий получить ряд новых эффективных базовых алгоритмов БПШ и ЦС.

2.Получен обобщенный алгоритм вычисления N -точечной ЦС над полем корней N -ой степени из единицы над полем рациональных чисел, где N^ Р , Р -простое, оС^ і, целое.

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

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

4.Предложены эффективные модификации алгоритма простых множителей (AIM) для действительных и эрмитово-симметричных входных последовательностей.

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

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

7.Предложен эффективный алгоритм тактовой синхронизации цифровых многоканальных модемов на основе БЩ.

Достоверность и обоснованность полученных результатов обусловлены:

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

соответствием аналитических результатов результатам, полученным при моделировании на ЭВМ,

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

- разработанные алгоритмы БШ и полученные выражения для оце-

нки вычислительных ошибок могут быть использованы при построении специализированных процессоров БШ для всевозможных технических приложений, в частности, для цифровых устройств сопряжения АСП и ЦСП - ТМ и многоканальных модемов,

разработанный процессор БШ предназначен для выполнения операций модуляции и демодуляции в высокоскоростном многоканальном модеме для вторичного широкополосного канала АСП,

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

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

Реализация в народном хозяйстве. Основные теоретические выводы, алгоритмы и практические результаты внедрены при разработке центральных узлов цифрового многоканального модема для вторичного широкополосного канала АСП в рамках НИР "Трест", № гос. регистрации Ш5485.

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

В первом разделе работы исследованы теоретические принципы, лежащие в основе важнейших классов алгоритмов БШ и ЦС - алгоритмов Кули-Тьюки с произвольным и смешанным основанием, АПМ, алгоритма ГУда-Винограда (АГВ) , "гнездового" алгоритма Винограда для БШ и "гнездового" алгоритма Агарвала-Кули для ЦС. Дано конструктивное доказательство теоремы о существовании прямоугольных преобразований с минимальньм по Винограду числом умножений. Впервые подробно раскрыт механизм представления ДШ через ЦС для об-

щего случая N = Р » где Р -простое, (/<> I, целое. Дано строгое доказательство свойств коэффициентов базовых алгоритмов Винограда БШ коротких последовательностей. Произведен сравнительный анализ алгоритмов Б1Ж> по эффективности, требуемому объему памяти и точности. Сформулированы цели и задачи дальнейшего исследования.

Второй раздел посвящен разработке нового метода синтеза субоптимальных прямоугольных преобразований, обеспечивающего близкое к оптимальному соотношение между требуемым числом умножений и сложений. Достоинством предложенного метода является хорошая формализуемость, а, следовательно, простота реализации на ЭВМ. Приводятся блок-схемы алгоритмов синтеза матриц прямоугольных преобразований, а также основные подпрограммы, написанные на языке ФОРТРАН - ІУ. Рассматривается пример синтеза для входной последовательности длины N =3. Предлагается вариант синтеза прямоугольных преобразований над полем рациональных чисел для N ~ 25. Дана оценка мультипликативной сложности новых базовых алгоритмов Б1Ш> и ЦС, а также алгоритмов БШ> очень длинных последовательностей, построенных в соответствии с АГВ и алгоритмом Винограда.

Третий раздел посвящен синтезу новых прямоугольных преобразований над алгебраическими расширениями поля рациональных чисел. Дан вывод алгоритма N -точечной ЦС над полем корней N -ой степени из единицы над полем рациональных чисел, где |Ч = Р , р -простое,d^ I, целое. Приведена блок-схема реализации полученного алгоритма, служащего базовой операцией при синтезе алгоритмов БШ и ЦС длинных и многомерных последовательностей. Получены выражения для подсчета требуемого количества арифметических one раций. Рассмотрены частные случаи синтеза прямоугольных преобразований над полями корней 3, 5, 7 и 8 степени из единицы. Дана оценка вычислительной сложности. Показано, что благодаря уменыпе-

нию нижней по Винограду границы числа умножений и возможности параллельной обработки нескольких независимых входных последовательностей, новые базовые алгоритмы целесообразно использовать для вычисления ЦС и ДШ многомерных последовательностей с помощью "гнездовых" алгоритмов. С помощью метода, предложенного во втором разделе, синтезированы прямоугольные преобразования для N =3, 5, 7, 8 и 9 над полем рациональных чисел Эйзенштейна, позволяющие существенно уменьшить мультипликативную сложность алгоритмов Агарвала-Кули ЦС комплексных последовательностей.

Четвертый раздел посвящен синтезу (на основе прямоугольных преобразований) и анализу эффективных алгоритмов БШ> применительно к задачам эффективного сопряжения АСП и ЦСП. Разработаны модификации структуры AIM для действительных и эрмитово-симметричных входных последовательностей. Дан синтез базовых алгоритмов БШ, используемых в устройствах сопряжения. Приведены соответствующие сигнальные гра^н с оптимально выбранными масштабирующими множителями. Цредложен эффективный метод программной реализациии умножений. На основе статистического метода произведен анализ вычислительных ошибок AIM и его модификаций в системе счисления с фиксированной запятой. Получены расчетные формулы для средней дисперсии, математического ожидания и среднеквадратического значения вычислительных ошибок как базовых алгоритмов БШ, так и АПМ для различных представлений отрицательных чисел. Разработан быстродействующий процессор БШ для высокоскоростного цифрового многоканального модема. Приведены результаты адекватного моделирования процессора на ЕС ЭВМ для различных методов масштабирования и представления данных и коэффициентов, с высокой точностью подтверждающие теоретические оценки. Описана функциональная схема процессора, приведены временные диаграммы работы. Предложен эффективный алгоритм тактовой синхронизации многоканальных модемов, основанный на БШ.

На защиту выносятся следующие основные положения.

  1. Предложенный метод синтеза субоптимальных прямоугольных преобразований позволяет получить ряд новых эффективных базовых алгоритмов ЕШ> и ЦС. Предложенный метод хорошо формализуем, поэтому его целесообразно реализовать на ЭВМ.

  2. Новые прямоугольные преобразования, синтезированные на ба-зе обобщенного алгоритма [М-Р (Р -простое, o^I ) -точечной ЦС над полем корней N -ой степени из единицы над полем рациональных чисел, позволяют существенно повысить эффективность "гнездовых" алгоритмов БШ? и ЦС многомерных и комплексных последовательностей.

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

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

  5. АПМ и его модификации могут быть реализованы "безумножи-тельным" способом с использованием предложенного метода программной реализации умножений на сравнительно небольшое число различных постоянных коэффициентов.

  6. Синтезированные алгоритмы 14, 28, 72 и 144 -точечных БШ целесообразно использовать в многоканальных цифровых устройствах сопряжения АСП и ЦСП.

  7. Полученные выражения для расчета средней дисперсии, мате-

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

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

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

Подобные работы
Комаров Валентин Данилович
Исследование и разработка методов увеличения надежности и пропускной способности микропроцессорных систем передачи информации
Чепорнюк Олег Николаевич
Дискретно-аналоговые методы приема сигналов в системах передачи данных с многопозиционной частотной модуляцией
Исаев Рихси
Разработка методов и устройств автоматического прогнозирования состояния каналов аналоговых систем передачи
Игнатьев Валерий Эдмундович
Исследование адаптивных систем передачи измерительной информации
Аккуратова Валентина Сергеевна
Разработка методов оценки влияния попутного потока на помехоустойчивость кабельных линейных трактов высокоскоростных цифровых систем передачи
Лазарев Андрей Михайлович
Разработка, исследование, оптимизация адаптивных корректоров межсимвольных искажений устройств преобразования сигнала для проводных систем передачи
Шахмаметов Рашид Ганиевич
Разработка методов передачи данных в системах телеобработки гражданской авиации
Подрябинников Алексей Андреевич
Синтез алгоритмов позиционирования приемника сотовой сети связи и система передачи координатно-зависимых данных на его основе
Федченко Евгений Михайлович
Методы геометро-кинематического анализа и синтеза пространственных фрикционных передач с замкнутой системой тел качения
Корниенко Алексей Викторович
Алгоритмы синтеза и обработки короткоимпульсных сверхширокополосных сигналов в радиосистемах передачи информации с учетом мешающих факторов

© Научная электронная библиотека «Веда», 2003-2013.
info@lib.ua-ru.net