Содержание к диссертации
Введение
1. Анализ алгоритмов быстрого преобразования фурье и циклической свертки, основанных на прямоугольных преобразованиях
1.1. Постановка задачи 15
1.2. Основные определения 20
1.3. Синтез алгоритмов быстрого преобразования Фурье и циклической свертки коротких последовательностей
1.3.1. Модульная арифметика полиномов 22
1.3.2. Синтез прямоугольных преобразований 25
1.3.3. Синтез алгоритмов быстрого преобразования Фурье на основе прямоугольных преобразований 29
1.4. "Гнездовой" алгоритм вычисления циклической свертки длинных последовательностей 36
1.5. Алгоритмы быстрого преобразования Фурье длинных последовательностей
1.5.I. Алгоритм с множителями поворота 38
1.5. 2.Алгоритм простых множителей 41
1.5.3. "Гнездовой" алгоритм Винограда 44
1.6. Сопоставление алгоритмов быстрого преобразования Фурье :
1.6.1. Объем вычислений 46
1.6.2. Объем памяти 48
1.6.3. Эфекты конечной разрядности 50
2. Новый метод синтеза прямоугольных преобразований
2.1. Теоретические основы предлагаемого метода
2.I.I. Свойство цикличности свертки
2.1.2. Транспозиция алгоритма
2.1.3. Метод решения системы линейных уравнений, когда уравнений больше, чем неизвестных 59
2.2. Синтез прямоугольных преобразований
2.2.1. Синтез матриц А и В
2.2.2. Вычисление матрицы С
2.2.3. Пример синтеза 72
2.3. Вопросы реализации предлагаемого метода на ЭВМ 76
2.4. Оценка мультипликативной сложности новых алгоритмов быстрого преобразования Фурье 82
3. Синтез прямоугольных прюбразований над алгебраичёсшми расширениями поля ращоналшых чисел
3.1. Введение алгебры над алгебраическими расширениями 90
3.2. Швод базового алгоритма 93
3.3. Оценка вычислительной сложности 95
3.4. Синтез прямоугольных преобразований над полем корней N-ой степени из единицы, где N -простое 98
3.5. Синтез прямоугольных преобразований над полем корней 8-ой степени из единицы 104
3.6. Оценка вычислительной сложности новых алгоритмов для преобразования многомерных последовательностей 106
3.7. Синтез прямоугольных преобразований над полем чисел Эйзенштейна 115
4. Синтез и анализ алгоритмов быстрого преобразования фурье для цифровых устройств сопряжения аналоговых и цифрошх систем періщачи
4.1. Применение дискретного преобразования Щурье в устройствах сопряжения 120
4.2. Разработка теоретических вопросов
4.2.1. Модификации алгоритма простых множителей для действительных и эрмитово-симметричных последовательностей 129
4.2.2. Анализ вычислительных ошибок алгоритма простых множителей в системе счисления с фиксированной запятой 136
4.2.3. Эффективная программная реализация умножений в алгоритмах быстрого преобразования Фурье коротких последовательностей 146
4.3. Синтез и анализ алгоритмов быстрого преобразования Фурье для N =14, 28, 72 и 144
4.3.1. Синтез базовых алгоритмов 150
4.3.2. Объем вычислений 163
4.3.3. Анализ вычислительных ошибок 163
4.4. Разработка процессораточечного быстрого преобразования Фурье для цифрового многоканального модема
4.4.1. Вычислительный алгоритм 1?2
4.4.2. Вычислительные ошибки. Выбор разрядности процессора 176
4.4.3. Моделирование процессора быстрого преобразования Фурье на ЭВМ 179
4.4.4. Описание работы процессора 183
4.4.5. Основные параметры процессора быстрого преобразования Фурье 190
4.5. Разработка эффективного алгоритма тактовой синхронизации цифрового многоканального модема 193
Выводы 198
Заключение 201
Литература 204
Приложения
- Синтез алгоритмов быстрого преобразования Фурье и циклической свертки коротких последовательностей
- Синтез прямоугольных преобразований
- Синтез прямоугольных преобразований над полем корней N-ой степени из единицы, где N -простое
- Разработка процессораточечного быстрого преобразования Фурье для цифрового многоканального модема
Введение к работе
цифровая обработка сигналов (ЦОС) находит все более широкое применение в различных областях науки и техники. Постоянное усложнение задач практики, увеличение объема передаваемой и преобразуемой информации, требование реального масштаба времени вызывают необходимость дальнейшего совершенствования методов ЦОС, синтеза новых, все более эффективных вычислительных алгоритмов.
Эта задача нашла отражение в "Основных направлениях экономического и социального развития СССР на 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 и его модификаций в системе счисления с фиксированной запятой. Получены расчетные формулы для средней дисперсии, математического ожидания и среднеквадратического значения вычислительных ошибок как базовых алгоритмов БШ, так и АПМ для различных представлений отрицательных чисел. Разработан быстродействующий процессор БШ для высокоскоростного цифрового многоканального модема. Приведены результаты адекватного моделирования процессора на ЕС ЭВМ для различных методов масштабирования и представления данных и коэффициентов, с высокой точностью подтверждающие теоретические оценки. Описана функциональная схема процессора, приведены временные диаграммы работы. Предложен эффективный алгоритм тактовой синхронизации многоканальных модемов, основанный на БШ.
На защиту выносятся следующие основные положения.
Предложенный метод синтеза субоптимальных прямоугольных преобразований позволяет получить ряд новых эффективных базовых алгоритмов ЕШ> и ЦС. Предложенный метод хорошо формализуем, поэтому его целесообразно реализовать на ЭВМ.
Новые прямоугольные преобразования, синтезированные на ба-зе обобщенного алгоритма [М-Р (Р -простое, o^I ) -точечной ЦС над полем корней N -ой степени из единицы над полем рациональных чисел, позволяют существенно повысить эффективность "гнездовых" алгоритмов БШ? и ЦС многомерных и комплексных последовательностей.
Новые прямоугольные преобразования, синтезированные над полем рациональных чисел Эйзенштейна, позволяют существенно уменьшить мультипликативную сложность "гнездовых" алгоритмов ЦС комплексных последовательностей.
Предложенные модификации АІШ позволяют существенно повысить эффективность БШ действительных и эрмитово-симметричных последовательностей. Другим важным достоинством предложенных модификаций является отсутствие дополнительных умножений на большое число поворачивающих множителей, неизбежно появляющихся в традиционном алгоритме безызбыточного вычисления ДШ> указанных последовательностей.
АПМ и его модификации могут быть реализованы "безумножи-тельным" способом с использованием предложенного метода программной реализации умножений на сравнительно небольшое число различных постоянных коэффициентов.
Синтезированные алгоритмы 14, 28, 72 и 144 -точечных БШ целесообразно использовать в многоканальных цифровых устройствах сопряжения АСП и ЦСП.
Полученные выражения для расчета средней дисперсии, мате-
матического ожидания и среднеквадратического значения ошибок делают возможным с достаточно высокой степенью точности анализ вычислительных ошибок базовых алгоритмов БШ, а также АШ и его модификаций при различных представлениях отрицательных чисел в системе счисления с фиксированной запятой.
8. Эффективный алгоритм тактовой синхронизации (по принципу минимума переходных помех в свободных каналах) многоканальных модемов может быть построен на основе алгоритмов БШ.
В заключении приводятся основные результаты, полученные в диссертационной работе , подтверждающие сформулированные выше положения.
Синтез алгоритмов быстрого преобразования Фурье и циклической свертки коротких последовательностей
Одним из важнейших приложений ЦОС в системах связи является построение цифровых устройств сопряжения АСП и ЦСП - ТМ и модемов.
Трансмультиплексоры призваны осуществлять взаимное преобразование вида уплотнения каналов на уровне первичных (12-канальных) , вторичных (60-канальных) и т.д. групп. Указанную функцию сопряжения, только на уровне каналов ЇЧ, в принципе можно осуществлять на основе оборудования ЧРК и ВРК, имеющегося в терминалах. Но как показывают многочисленные зарубежные исследования и разработки /16-23/, более высокое качество при лучших экономических показателях обеспечивается с помощью специализированных устройств.
В настоящее время известно большое количество эффективных алгоритмов цифрового преобразования ЧРК « ВРК, имеется попытка классификации алгоритмов по различным критериям, как, например, число операций в единицу времени, групповое запаздывание, степень модульности, наличие аналогового преобразования частоты /24/.
Исследования в этой области интенсивно проводятся и отечественными специалистами. Однако, разработка серийного ТМ в СССР до настоящего времени сдерживалась, во-первых, недостаточно развитой сетью цифровых систем передачи и цифрового коммутационного оборудования, во-вторых, отсутствием достаточно быстродействующих и экономичных ВИС, приспособленных специально для ЦОС в реальном масштабе времени. Но, как указано в /25/, реализация ТМ в СССР станет не только актуальной, но и реально осуществимой задачей уже к 1990 году.
Следовательно, уже сейчас необходимо осуществить выбор (син тез ) оптимального алгоритма преобразования вида уплотнения, эффективных алгоритмов фильтрации и БШ, приспособленных к перспективной отечественной элементной базе. Причем оптимизацию алгоритмов необходимо производить не только с точки зрения объема вычислений и памяти, но и с точки зрения обеспечения качественных показателей, отраженных в рекомендациях МКНТТ G.79I - &.793 (см. также /26/) . В этом аспекте необходимо довести отдельные алгоритмы ЦОС до реализационного уровня, вплоть до определения, например, зависимости собственных шумов от вида и разрядности представления чисел в процессоре.
Другой класс устройств сопряжения АСП и ЦСП составляют модемы, предназначенные для преобразования цифровых потоков с целью передачи их по каналам АСП. В настоящее время ведутся работы по созданию цифрового многоканального модема для передачи цифрового потока со скоростью 480-512 кбит/с по вторичному широкополосному каналу АСП /10/.
Важнейшим узлом как ТМ, использующих полифазную схему фильтрации /24/, так и многоканальных модемов /б/, является устройство БШ, призванное осуществлять групповую модуляцию и демодуляцию цифровых сигналов. В случае преобразования вида уплотнения на уровне первичных групп возникает необходимость в 14 или 28 -точечных БШ /20,21,23/, в случае же преобразования на уровне вторичных групп, без дополнительной ступени аналогового преобразования частоты (частота дискретизации цифрового ЧРК - сигнала составляет 576 кГц) - в 72 или 144 -точечных БШ /16,22,23/.
Центральным узлом разрабатываемого многоканального модема является процессор 144-точечного БШ последовательности с эрмитовой симметрией при прямом преобразованиии сигнала и действительной последовательности - при обратном.
Таким образом, возникает задача построения эффективных вычис лительных алгоритмов 14,28,72 и 144-точечных БШ, хорошо приспособленных к отечественной элементной базе, выбора масштабирующих множителей и разрядности представления данных и постоянных коэффициентов на основе анализа вычислительных ошибок.
Так как числа 14,28,72 и 144 представиш в виде произведения двух взаимно простых чисел, то наибольшей эффективности БШ можно достичь используя структуры АПМ или АВ. Так как АПМ незначительно уступает АВ по быстродействию, но превосходит по другим важным показателям как требуемый объем памяти, простота программирования, точность вычислений, то в качестве оптимальной структуры следует выбрать структуру АПМ.
Некоторые структуры ТМ, например, с набором фильтров нижних частот /24/, и многоканальные модемы предполагают ДШ действительной последовательности в одном направлении преобразования сигнала и последовательности с эрмитовой симметрии - в другом. Возникает задача приспособления АПМ к виду входной последовательности. Эта задача особенно актуальна для модемов, поскольку в этом случае сложность всего устройства по существу определяется сложностью процессора БШ.
Реализация БШ возможна лишь с ограниченной точностью, что вызвано конечной разрядностью представления данных, промежуточных результатов и коэффициентов. Исследованию эффектов конечной разрядности посвящены работы /27-32/. Большинство из них, рассматривающих реализацию БШ в системе счисления с фиксированной запятой, посвящено анализу вычислительных ошибок при представлении отрицательных чисел в прямом коде. Реальные же специализированные процессоры БШ используют представление чисел в дополнительном коде. . Этот случай проанализирован только для алгоритмов Нули-Тыоки /30/. В данной работе ставится задача анализа вычислительных ошибок АПМ и его модификаций при представлении чисел в дополнительном коде.
Синтез прямоугольных преобразований
Предлагаемый метод синтеза ШІ (I.2I) является очень простым и заключается в /35, 53/:- синтезе матриц А = и путем последовательного деления исходного полинома Л\С) (см. также (1.20))на полиномы с тривиальными коэффициентами, выбираемыми в соответствии с китайской теоремой об остатках и тождествами (I.I4) или(1.15) ,- вычислении элементов матрицы L из условия цикличности свертки (2.7 ) ,- транспозиции алгоритма в соответствии с ( 2.8 ) .также требует трех умножений (см. (2.19) и (2.20)) . Всего шесть умножений.
Очевидно, операции вычисления полиномиальных вычетов будут выполняться наиболее просто, если 1Л () имеют только тривиальные коэффициенты (0, I, -I) .
Неприводимые, кроме Г2 и Г% , над полем W полиномы 1,2 и 3 степени с тривиальными коэффициентами сведены в таблицу 2.1 , где также указано число операций умножения, требуемых для вычисления выражений вида ( 2.17).Полиномы, приведенные в таблице 2.1, в дальнейшем будут использоваться в качестве базовых при вычислении вычетов по модулю полиномов большей степени.
Аналогично рассмотренным случаям I =2,3 , с использованием таблицы 2.1 можно определить векторы произведений для других I .В таблице 2.2 представлен один из вариантов разложения поли номов Pm+t(2)=p2L-2(Z) и Pm+t+ fe)= PL- (2) и указано требуемое число умножений для І. 22.
Рассмотренный метод определения вектора произведений полностью переносится на случай N -точечной ЦС С 1.20).В соответствии с китайской теоремой об остатках вычисление вычета по модулю полинома 2-. = Д гЩ. \2) , где гцц?)-неприводимый над полем Ы полином П(. -ой степени иvPtVt (Д)1» "PnulZ.)) » своДится к вычислению отдельных вычетов по модулю полиномов гГЦ (Z) . А для определения вектора произведений, возникающего при вычислении вычета X(?) П (Z) ГЛОСІ ГПії?) » можно воспользоваться методом, описанным выше (см. также табл. 2.1 и 2.2) .
В таблице 2.3 для ряда [\ приведено разложение полинома с. - 1 на множители, неприводимые над полем Ы , и указано число умножений, требуемых для вычисления соответствующих ЦС.
Имея вектор произведений легко определить матрицы ПП - А и В.Очевидно, каждый элемент вектора к , получаемый в результате последовательного деления полиномана полиномы с фиксированными коэффициентами и подстановки на последнем этапе вместо 2 чисел О, I или -I, представляет собой произведение линейных комбинаций элементов последовательностей IjCnj и {hnj , т.е.:
Так как во всех преобразованиях последовательности 1-А-Ги и ІГІП.J участвуют равноправно, то Так как А=В, то, очевидно, все операции, связанные с делением полиномов, достаточно производить только с одним из полиномов, например, с
Блок-схема алгоритма синтеза матрицы А для N 25 , составленная в соответствии с вышеописанным методом, представлена на рис. 2.1.
Матрицу С вычислим, пользуясь необходимым и достаточным условием цикличности свертки С 2.7) , которое в данном случае целесообразно переписать в виде: методу, изложенному в п.п. 2.1.3.
Последнее выражение представляет собой уже обычную системуиз четырех линейных уравнений с четырьмя неизвестными, решениекоторой найти нетрудно, например, по методу Гаусса Нетрудно проверить, что полученное решение удовлетворяет всем уравнениям системы (2.29), т.е. является точным. Аналогично Вопросы реализации предлагаемого метода на ЭВМ
Одним из основных достоинств предлагаемого метода синтеза ПП является хорошая формализуемость, что позволяет реализовать его на ЭВМ.Синтез Ш (I.2I) , как уже говорилось выше, заключается по существу, в вычислении прямоугольных матриц А и С.
Основной и наиболее сложной операцией при вычислении матрицы А является операция деления полиномов. На рис. 2.3 представлена подпрограмма J) р деления полиномов, написанная на языке ФОРТРАН-ІУ. Эта подпрограмма осуществляет деление полинома N А степени JMI-I С коэффициентами, представляющими собой линейную комбинацию элементов исходной последовательности tLnj длины \ , на полином \\ О степени ГЛ" 1 с тривиальными коэффициентами. Результат деления - вычет чАА .В подпрограмме D у полиномы NA и NAA задаются в виде целочисленных матриц размера pMXplc. 9 причем каждая строка матрицы, являющаяся по существу коэффициентом при соответствующей степени ZL , представляет собой последовательность коэффициентов в линейной комбинации элементов исходной последовательности \Xr\J» Полином \ D задается вектором длины \\ , элементы которого равны коэффициентам при степенях 2Рассмотрим в качестве примера вычисление вычета полиномапо модулю полинома
Синтез прямоугольных преобразований над полем корней N-ой степени из единицы, где N -простое
Пусть (ч - простое, нечетное. В этом случаеЭлементами поля являются комплексные чис ла вида Из приведенных выражений следует, что сложение двух комплексных чисел требует выполнения 14-1 действительных сложений. Того же количества сложений требует операция сдвига. На порядок более сложной операцией является операция умножения. В соответствии с выражением C3.2I) элементы вектора произведения двух комплексных над полем Uv? .--» ) ) чисел представляют собой коэффициенты вычета произведения двух полиномов pi - С -ой сте-пени по модулю полинома . + zi. + "
В Приложении I приводятся эффективные алгоритмы реализации указанных операций для К =3,5,7 /56/. В таблице 3.1 приводится требуемое число действительных умножений [Tip и сложений Qp в случае предварительной обработки одного из сомножителей.
Алгоритм вычисления N - точечного ЦС для рассматриваемого случая легко получить из базового обобщенного алгоритма, описанного в п. 3.2 :
Определим требуемое число операций. Если в п. 3.3 была определена только верхняя граница числа сложений, то здесь удается получить точное число операций с учетом того, что часть операций является тривиальной С например, сложение с нулем).
Вычисление выраженияпри условии, что последовательностьпредставляется в виде: требует выполнения при 1 = 0 (.N"4) действительных сложений.Приведение членов с одинаковыми степенями ї при 1=4, ...,N 4требует сложений. Сокращение полинома М 1степени по модулю полинома ч (2) требует (NH/ сложений. В общей сложности это составляетсложений.
Такое же число сложений требуется для преобразования последовательности произведений ГП{. J в соответствии с выражением С3.24).Так как одно комплексное сложение реализуется с помощью (4-1 действительных, то вычисление С3.22) и (3.24) эквивалентно выполнениюкомплексных сложений.
Шчисление последовательности произведений ItTU j С 3.23) требует выполнения N комплексных умножений вида С3.21) .
Учитывая, что каждое комплексное умножение, кроме ГПо , требует выполнения ГПр действительных умножений и Up действительных сложений, а ҐПо - только 14-4 действительных умножений, вычислим результирующее число действительных умножений и сложений, требуемых для реализации N -точечной ЦС и приходящихся на одну входную последовательность:
В общем случае, если для вычисления ЦС или ДПФ над рассматриваемым полем требется ҐП комплексных умножений и Q комплексных сложений, то число действительных операций, приходящихся на одну входную последовательность, составит (ср. с (3.19) и (3.20)):
Рассмотрим в качестве примера вычисление 3 -точечной ЦС.В этом случае можно параллельно обрабатывать две независимые действительные входные последовательности: \ (Xn J и (.OCrij [1=0,1,2.) . Комплексная входная последовательность, в соответствии с (3.25) будет иметь вид:или,приведенный в Приложении 1.
Искомая последовательность формируется из последовательности произведений \ ГГЦ] в соответствии с (3.24 ) :Причем последовательность 1 У а ) равна ЦС последовательностей jXn J и 1 Пп) , а последовательность і Уп j - ЦС
Требуемое число действительных операций можно подсчитать либо непосредственно по приведенному алгоритму, либо по формулам (3.26) и (3.27 ) . В результате получим ГПа = 2:1 , Среди корней 8-ой степени из единицы линейно независимыми над полем U являются корни = \, , % , Для удобства введем следующие обозначения:Тогда элементы алгебраического расширения Q будут иметь вид:105Алгебра над полем в соответствии с (3.63 - С3.9)имеет вид:1. Сложение:Отсюда следует, что сложение двух комплексных над полемчисел требует четырех действительных сложений. Операциясдвига является наиболее простой и не требует выполнения арифметических операций. Наиболее сложной является операция умножения, вычисляемая как вычет произведения полиномов 3-ей степени по мо дулю полинома +\ .В Приложении 2 приводится эффектив ный алгоритм вычисления С3.30) , синтезированный с использованием методов, рассмотренных в разделах I и 2. Здесь только отметим, что вычислительная сложность этого алгоритма при условии предва рительной обработки одного из сомножителей равна 9 действительным умножениям и 19 действительным сложениям. Рассмотренное поле целесообразно использовать для вычисления N=2, -точечных ЦС, т.к. в этом случае удается получить наибольшее число неприводимых над полем множителей в разложении tL " " и тем самым значительно уменьшить нижнюю границу требуемого числа умножений.
Разработка процессораточечного быстрого преобразования Фурье для цифрового многоканального модема
В процессоре БШ для представления чисел используется двоичная система счисления с фиксированной запятой. Числа представляются в дополнительном коде с использованием 6 4 + 4 разрядов. Первый разряд является знаковым, остальные М разрядов представляют модуль числа, меньший единицы.
Для аппроксимации произведений используется процедура усечения.С целью предотвращения возможного переполнения сумматора процессора вводится автоматическое масштабирование.В 16-точечном БШ (алгоритм D ) масштабирующий множитель, равный 1/2 , вводится на входе каждой операции "бабочка". Результирующий масштабирующий множитель равенНесколько сложнее процедура масштабирования в 9-точечных БШ (алгоритмы И и LZ ). Согласно теореме Парсеваля, СКЗ выходного сигнала 9-точечного БШ в 9 раз больше СКЗ входного сигнала. Результирующий масштабирующий множитель 9-точечного БПФ должен быть равен //9 .Но число Y/9 не равняется степени 2, и умножение на него не осуществимо путем простых сдвигов. Поэтому масштабирующий множитель в алгоритмах И mil выбран равным , а входные числа нормируются таким образом, чтобы модуль их не превышал о 9
Имеется еще одна особенность масштабирования.На этапе Ъ\ алгоритма (см. рис. 4.8) постоянные коэффициенты предварительно умножаются на такие степени числа 2 ( J/, чтобы в результате коэффициенты имели максимальную величину, не превышающую единицы. Это сделано с целью максимального подавления ошибки умножения на последующем этапе масштабирования множителем {(2 ) Модели и характеристики элементарных ошибок, возникающих в алгоритмах Li , L2 и D , были рассмотрены в п.п. 4.3.3. и приведены в табл. 4.7.
Взвешивающие коэффициенты (м , f i и If і и векторы математических ожиданий ошибок алгоритмов Li , L2. и D , необходимые при вычислении СКЗ ошибок 144-точечного БШ, приведены в табл. 4.8 и 4.9.Модель расчета средней дисперсии, составленная по аналогии с рис. 4.9 приведена на рис. 4.24 а)- для алгоритма [_\ xj) и на рис. б)- для алгоритмаРезультаты вычисления средней дисперсии, среднего квадрата математического ожидания и СКЗ вычислительных ошибок, произведен ного по формулам (4.15 С4.20), приведены в таблице 4.13.На рис. 4.25 представлена полученная зависимость "СКЗ вых. сигн./СКЗ вых. ош." от BJ И ВГ для алгоритма L 1 х J)Анализ кривых говорит о том, что не имеет смысла представлять фиксированные коэффициенты с точностью, большей В2=Ю разрядов. Для представления промежуточных результатов выбирается Ву+І=І6 разрядов. Выбранная разрядность с запасом удовлетворяет требованиям по отношению "сигнал/шум" на выходе процессора и удобна с точки зрения реализации на 4, 8 и 16 - разрядных секциях микросхем.
С целью прверки теоретических результатов было проведено адекватное моделирование процессора 144-точечного БШ на ЭВМ ЕС-1022.Схема моделирования приведена на рис. 4.26. В качестве входного сигнала БШ используется случайная пос ледовательность с равномерным законом распределения в интервале (-1, i) . Входное масштабирование множителем осуществляется в блоке нормировки. В случае входной последовательности с эрмито вой симметрией для алгоритма производится дополни тельное масштабирование множителем Y2 / 2 с тем, чтобы модуль входных комплексных чисел был меньше 8 / 9 . Моделируемое 144-точечное БШ представляет собой точную ма тематическую копию цифрового процессора. В модели предусмотрена возможность изменения длины слова данных, промежуточных результатов и коэффициентов, возможность представления чисел как в прямом, так и дополнительном коде, возможность использования для аппроксимации произведений и коэффициентов как процедуры усечения, так и округления.
В программной реализации эталонного обратного ДПФ (ОДПФ) используется представление чисел в системе счисления с плавающей запятой. Незначительные ошибки, свойственные этому методу, пренебрегают ся.Выходная последовательность эталонного блока 0ДШ с точностью до ошибки, обусловленной блоком моделируемого БГН , совпадает с входной последовательностью.В блоке вычисления статистических характеристик производится вычисление оценок дисперсии, среднего квадрата математического ожидания и СКЗ вектора ошибок \ XnJ \0Cnj » & также отношения "СКЗ вых. сигн./СКЗ вых. ош."
Приведенная схема моделирования отличается от традиционной, рассмотренной, например, в /49/. Там входная последовательность поступает параллельно на входы моделируемого и эталонного ДПФ. Разность выходных последовательностей дает ошибку моделируемого ЕШ. В силу справедливости теоремы Парсеваля приведенная схема моделирования (рис. 4.26) эквивалентна традиционной с точки зрения СКЗ, а выбор ее был продиктован лишь соображениями удобства конкретного моделирования.На рис. 4.27 и 4.28 приведены теоретические результаты совместно с результатами моделирования.Анализ графиков говорит о хорошем (примерно 10%) совпадении теории и эксперимента и позволяет окончательно остановиться на следующих значениях разрядности: вт«15, в?=10.
