Синтез, оптимизация и компьютерное исследование эффективности быстрых непозиционных алгоритмов спектрального анализа Галанина, Наталия Андреевна

Содержание к диссертации

Введение

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

1.1. Одномерный поразрядный метод вычисления ДПФ 16

1.2. Многомерный поразрядный метод вычисления ДПФ 18

1.3. Оптимизация параметров ПДПФ

1.3.1. Разрядность адресных шин ПИЗУ- высокая: z x+y 23

1.3.2. Использование ППЗУ с малым объемом памяти: z x+y 24

1.4. Интерактивный синтез ПДПФ 27

Выводы 37

2. Исследование и разработка устройств непозиционного быстрого преобразования Фурье 39

2.1. Выбор системы модулей для БПФ в СОК и ее оптимизация 39

2.2. Синтез функциональных модулей БПФ в СОК 40

2.3. Реализация схем БПФ в СОК... 48

2.4. Алгоритм индексации чисел в непозиционных устройствах спектрального анализа 55

Выводы 58

3. Сравнительный анализ позиционной и непозиционной цифровой обработки сигналов при использовании DSP 59

3.1. Сравнительная оценка быстродействия позиционной и непозиционной обработки при реализации на DSP 59

3.2. Перспективные направления развития непозиционных устройств UOCHaDSP 66

3.3. Оптимизация непозиционных устройств цифровой обработки сигналов

3.4. Определение оптимального набора модулей СОК и погрешностей перекодирования 82

Выводы 88

4. Программный комплекс моделирования и автоматизированного синтеза непозиционных устройств БПФ 89

4.1. Пути компьютерной оптимизации непозиционных БПФ 90

4.2. Описание программы моделирования и оптимизации 91

4.3. Список требуемых файлов и необходимых ресурсов 99

4.4. Руководство программиста

4.4.1. Структура данных. 100

4.4.2. Описание процедур и функций

4.5. Основные результаты работы программы 104

4.6. Программный комплекс синтеза спецпроцессора БПФ 106

Выводы 108

Заключение. Основные результаты работ 109

Литература

• Многомерный поразрядный метод вычисления ДПФ
• Синтез функциональных модулей БПФ в СОК
• Оптимизация непозиционных устройств цифровой обработки сигналов
• Руководство программиста

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

Актуальность проблемы. Классические научные достижения в области статистических исследований свойств сигналов и устройств сбора, хранения и регистрации данных отражены в работах Л. С. Гуткина, П. А. Бакулева, Ю.Г. Сосулина, Р.Л. Стратоновича, В.И. Тихонова, Б.Р. Левина и др. Особое место :реди нкх занимает цифровая обработка сигналов (ЦОС), главными источниками развития которой стали исследования ряда отечественных и зарубежных ученых: С.З. Кузьмина, В. А. Лихарева, Б. Гоулда, Ч. Рейдера, Д. Даджиона, А. Антокью, Л. Рабинера, и др., а также успехи в области микроэлектроники и компьютерных систем. Однако перед исследователями по-прежнему остро стоят проблемы эбеспечення высокой вычислительной эффективности: уменьшения аппаратурных затрат, увеличения быстродействия, точности и отказоустсйчизости устройств ЦОС. Поэтому в настоящее время актуальны вопросы применения алгоритмических методов улучшения качества вычислительных процедур и, в первую очередь, использования теоретико-числовых алгоритмов (ТЧА), представленных в работах Дж. Макклеллана, Ч. Рейдера, Р. Блейхута и др. К сожалению, использование ТЧА не всегда оправдано я часто уступает БПФ. Поэтому важен и актуален второй путь повышения качества ЦОС - непозиционное кодирование сигналов на выходе АЦП. В диссертации рассматривается одна из этих непозиционных систем - машинная фифметиха в системе остаточных классов (СОК). Ее суть состоит в ^использовании совокупности неотрицательных вычетов по группе взаимно простых оснований N_s (I Г- округление в сторону меньшего целого):

х$ (кТ) = х{кТ) - ІІ х(кТ) /N_s Г9 N_s =« х(кТ)» mod N_s,

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

Однако по-прежнему не решен ряд проблем. Среди них важное место инимает необходимость улучшения параметров многомерных теоретико-шсловых алгоритмов ДПФ и БПФ при их реализации з СОК, когда

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

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

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

2. Исследованием быстрых алгоритмов Фурье-преобразования в СОК, учитывающих свойства целых чисел в коммутативном кольце вычетов. Исследованием точности и ошибок округления в них и анализом путей повышения их вычислительной эффективности.

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

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

5. Разработкой моделей и компьютерных программ исследования позиционных и непозиционных алгоритмов БПФ; разработкой программного комплекса для моделирования и интерактивного синтеза на ПЭВМ устройств

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

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

Научинжш гагавввиа. В диссертации исследуются новые методы синтеза и нализа эффективности устройств ДПФ и БПФ в СОК. При этом получены педуюгдие новые результаты:

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

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

3. Исследованы схемы технической реализации алгоритмов БПФ в системе статочных классов. Синтезированы и оценены алгоритмы индексных БПФ, меющих максимальную вычислительную эффективность и высокую точность.

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

5. Создан программный комплекс, реалгоующий модели алгоритмов БПФ
СОК и позволяющий провести интегральный синтез и оптимизацию

араметров непозиционных устройств БПФ. Оценены ошибки преобразования найдены экспериментально оптимальные варианты реализации БПФ в СОК.

Научная новизна и приоритет исследований подтверждаются авторским видетельством СССР.

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

Шівг.нтиічіЕСікайї пдешшюстгь. Результаты исследований могут быть использованы при проектировании кенозиционных устройств спектрального анализа как на современных мощных сигнальных процессорах, так и на СБИС, ориентированных на обработку сигналов в СОК. При этом обеспечены минимальные ошибки округления, высокая отказоустойчивость, существенно уменьшаются аппаратурные затраты и увеличивается быстродействие спецпроцессоров, когда используются предложенньне в диссертации методы оптимизации модулей СОК и весовых коэффициентов БПФ е ДПФ.

Разработанный программный комплекс, методики синтеза, анализа и оптимизации ДПФ и БПФ в СОК позволяют создавать соответствующие непозиционные устройства, обладающие высокой вычислительной эффективностью.

Реализация и вгаедршше результат работы. Основные результаты диссертационной работы были использованы:

1. В учебном процессе на кафедре информационно-вычислительных систем Марийского государственного технического университета по дисциплинам: "Микропроцессорные системы" и "Теория и методы цифровой обработки сигналов" по специальности 2201 "Вычислительные машины, комплексы, системы и сети".

2. В учебном процессе на кафедре информационных технологий Чувашского государственного университета имени И.Н. Ульянова по дисциплинам "Быстрые алгоритмы цифровой обработки сигналов", "Теоретические основы защиты информации" по специальности 2201 "Вычислительные машины, комплексы, системы и сети" .

3. Результаты диссертации использовались при выполнении НИР:

1. "Исследование и разработка принципов построения программируемых вычислительных систем обработки радиолокационных сигналов" (отчет деп. в ВИНИТИ, № 0287.0025455).

2. "Методология проектирования специализированных микропроцессорных систем с эффективными алгоритмами. Аппаратная реализация мультипроцессорной непозиционной МПС обработки сигналов. Создание пакета функциональных программ" (отчет деп. в ВИНИТИ, № 0286.064966).

3.3. "Разработка и исследование микропроцессорных систем сбора,
обработки и регистрации данных" (отчет деп. в ВИНИТИ, №

0289.0001798).

3.4. "Разработка методология проектирования специализированных
микропроцессорных систем с эффективными алгоритмами.
Построение и анализ вычислительных теоретико-числовых
алгоритмов обработки сигналов" (отчет деп. в ВИНИТИ, №
0287.0067112).

3.5. "Разработка и исследование оптимальных алгоритмов
интеллектуального интерактивного абонентского доступа по
гибридным сетям ЦСИО" по единому заказ-наряду Министерства
образования Российской Федерации (1999-2000 гг.).

Анробашциш работы. Основные положения и результаты диссертационной аботы докладывались и обсуждались на международной конференции Перспективные технологии в средствах передачи информации" (г. Владимир, 995 г.), на всесоюзных конференциях "Микропроцессоры-85" (г. Зеленоград, 985 г.), "Информацконно-измерительные системы-93" (г. Куйбышев, 1993 г.), а всероссийских конференциях "Информационные технологии в электротехнике [электроэнергетике" (г. Чебоксары, 1996), "Динамика нелинейных дискретных лектротехнических и электронных систем" (г. Чебоксары, 1997, 1999 гг.), а акже на республиканских и университетских научно-технических конференциях г. Йошкар-Оле в 1983-1997 гг. и в г. Чебоксары в 1997 г.

Пу&гашикадцииш. По результатам выполненных исследований по теме ;иссертации опубликовано 20 печатных работ, в том числе авторское видетельство СССР, 5 статей, 5 тезисов докладов на конференциях, а также 3 рошгоры и 6 отчетов по НИР, депонированных в ВИНИТИ.

На г&шщипгу выпшеягтеж

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

2. Алгоритмы оптимизации устройств ПДПФ и программное обеспечение ля их компьютерного интерактивного синтеза.

3. Алгоритмы реализации БПФ з системе остаточных классов.

4. Многоканальное устройство БПФ в СОК.

5. Алгоритм индексирования чисел в коммутативном кольце вычетов.

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

множителя и кулевизации.

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

8. Математическая модель БПФ в системе остаточных классов и реализующей ее программный комплекс интерактивного синтеза и оптимизации устройств БПФ в СОК.

Структура и объем работы. Диссертация состоит из введения, четырех глав, заключения, приложения. Материал изложен на 158 страницах текста компьютерной верстки, в том числе основной текст - на 121 стр. В работе содержится 8 таблиц, 52 рисунка. Список литературы включает 91 наименование.

Многомерный поразрядный метод вычисления ДПФ

В [571] представлена проведенная автором сравнительная оценка этих вычислительных алгоритмов по аппаратурным затратам и быстродействию. Оценки получены путем компьютерного моделирования перечисленных алгоритмов. Наименьшую память для хранения программ и данных требует БПФ, наибольшую - АВПФ. В АПМ и АВПФ уменьшено число умножений, но возрастает число пересылок. Оценка временных затрат для АПМ, АВПФ и БПФ проводилась на моделях микропроцессоров с различными способами выполнения сложных операций. При программной реализации операции умножения эффективнее других оказался АВПФ. При аппаратном выполнении умножения БПФ не проигрывает АПМ и АВПФ. Известно, что время пересылки данных влияет на производительность не меньше, чем умножение. Поэтому необходимо сделать вывод о том, что БПФ по-прежнему остается одним из самых высокоэффективных вычислительных алгоритмов и на практике не проигрывает АПМ и АВПФ. В этой связи актуально исследование поразрядных алгоритмов ДПФ, число пересылок данных в которых не выше, чем в БПФ, но большинство сложных операций могут выполняться на этапе проектирования [47, 48].

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

Однако по-прежнему не решен ряд проблем. Среди них важное место занимает решение задач улучшения параметров многомерных теоретико-числовых алгоритмов ДПФ и БПФ при их реализации в СОК, когда обеспечиваются известные преимущества машинной арифметики в системе остаточных классов [30].

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

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

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

Можно выделить следующие теоретические вопросы, связанные с синтезом и анализом непозиционных устройств ЦОС:

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

2. Исследование быстрых алгоритмов Фурье-преобразования в СОК, учитывающих свойства целых чисел в коммутативном кольце вычетов. Исследование точности и ошибок округления в них и анализ путей повышения их вычислительной эффективности. 3. Исследование возможностей реализации непозиционных устройств спектрального анализа на современных позиционных сигнальных процессорах.

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

5. Разработка алгоритмов и программ моделирования позиционных и непозиционных алгоритмов БПФ. Разработка программного комплекса для интерактивного синтеза на ПЭВМ устройств поразрядной и непозиционной спектральной обработки сигналов, а также для оптимизации и сравнительного исследования характеристик различных устройств Фурье-преобразования.

Первая глава посвящена исследованию специальных вычислительных алгоритмов спектрального анализа в СОК. При этом рассматривается поразрядный метод вычисления ДПФ (ПДПФ) в его модификации, связанной с использованием процедуры Гуда. Многомерное ПДПФ включает следующие этапы: 1. Переиндексация данных. 2. Вычисление N/Ns коротких Ns - точечных ПДПФ. 3. Переупорядочивание выходных значений многомерного массива. Методы и устройства ПДПФ имеют преимущества в быстродействии по сравнению с позиционными устройствами БПФ [47, 48]. Кроме того, в ПДПФ существенно уменьшаются ошибки округления [42]. С целью дальнейшего улучшения характеристик ПДПФ решены задачи оптимизации параметров синтезированных схем [13].

Синтез функциональных модулей БПФ в СОК

Одной из основных задач ісинтеза поразрядных устройств ДПФ при заданной элементной базе и требуемом числе точек отсчета является программирование ППЗУ. Программирование ППЗУ связано с расчетом на ЭВМ всех возможных комбинаций весовых коэффициентов для различных случаев. Рассматриваемая ниже процедура расчета коэффициентов ПДПФ предназначена для вычисления в диалоговом режиме значений коэффициентов ПДПФ. Кроме того, оцениваются аппаратные затраты и предусмотрена также возможность изменения типа используемого ППЗУ. Процедура состоит из трех блоков [12]:

1. Диалоговый блок. В нем реализованы запросы количества точек во входной последовательности, количество адресных шин в используемом ППЗУ, количество разрядов, отведенных под код входной последовательности. Результатом работы блока является оценка необходимого количества корпусов ППЗУ с разбиением общего блока ЗУ на модули.

2.Вычислительный блок. В нем реализуются собственно вычисления коэффициентов ПДПФ по формуле: fF (I)==cos(27iFI/N), где N-количество точек; F-частота; 1н 1 1К - номер отсчета ; 1н - начальный номер отсчета для данного модуля ЗУ; 1к - конечный номер отсчета; W(K)= JF (IH) Ri+ + W,(IK+l) R2+W (I}i+2) R3+...+W (Ik) Rd. Здесь W(K) - собственно массив коэффициентов для одного модуля ППЗУ при данной частоте; Ra - разряды двоичного числа d; &=0,\..2ІА, где d - количество разрядов, отведенных под код входной последовательности.

ПДПФ приведен в [22].

Покажем, что при N, кратном степени 2, возможно сокращение объема памяти, как отмечено выше. Рассмотрим работу программы для конкретного примера N=64. Если разрядность дешифратора равна 11 (например, ППЗУ 556РТ6), то число разрядов ДШ ППЗУ для кодов частоты F=6, для кодов последовательности =5. Число корпусов ППЗУ равно 13. Для этого случая с целью дальнейшего упрощения приведем распечатку некоторых результатов. Первые столбцы соответствуют кодам входной последовательности от 00000 до 00111, вторые - от 01000 до 01111, третьи - от 10000 до 10111, четвертые - от 11000 до 11111.

Здесь А и В - идентификаторы весовых коэффициентов в программе.

Приведенные результаты работы программы показывают, что возможно сокращение объема памяти ППЗУ в 2 раза. На каждой странице можно хранить не 32, а 16 слов, т.к. результаты 1 и 2 столбцов соответственно отличаются от результатов, 3 и 4 столбцов на tsWu всегда одинаковые для этой страницы. Причем ключевой является четвертая позиция кодов входной последовательности. Если на этой позиции 1, то к данным ПЗУ Wk прибавляется значение kWf, а если на этой позиции 0, то дополнительного суммирования нет. Для уменьшения числа дополнительных сумматоров надо предварительно суммировать все возможные комбинации AWtk и записать эти суммы в дополнительные ПЗУ для хранения ХДЙ . Для рассматриваемого примера, когда ш=13, четвертые позиции кодов входной последовательности надо объединить в три группы по четыре позиции в каждой. Тогда каждое из трех дополнительных ПЗУ будет иметь объем памяти 2 слов (шесть позиций ДШ ПЗУ- AW,k по прежнему используется для Fk ).

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

Кроме того, каждый столбец можно разбить на более мелкие части. Например, для «корпуса 3 частота 1» можно хранить в ПЗУ число 0,5555, а в дополнительных ПЗУ AW!k=0,471; AW2k=0,382; AW3k=0,290; AW4k=0,195 и получить все 32 числа для данной страницы, используя тривиальные логические закономерности. Можно применять для этих целей программируемые логические матрицы. Однако в каждом случае такого разбиения нужно исходить не только из уменьшения памяти ППЗУ, но и из потребного количества дополнительных сложений.

Оценим затраты для конкретного случая N=64. В предварительной схеме [47] использовались 13 корпусов ППЗУ. Общий объем памяти составлял (12-2и+1.2ш) байта « 25 Кбайт. При R=10 затраты составляют около 250 Кбайт (130 корпусов ППЗУ). Эквивалентное время преобразования по одной точке Ti=troy+12tc Если применять схему рис. 1.5., то для нее затраты памяти будут 12-2ш+1-2ш +2-2 =16 Кбайт. При R=10 общие затраты составляют Q=160 Кбайт. Время преобразования увеличивается незначительно: T2=ti+3tcn- Далее при синтезе используем симметрию по точкам преобразования. Расчеты по последней программе дают результаты, симметричные относительно точек с номером N/2. Например, для N=62 симметрия будет относительно F32 для точек F3i и F33; F3o и F34; F29 и F35; F28 и F36... Fi и F63- Приведем распечатку некоторых результатов для корпуса 7 возле точки симметрии, если использована схема 1.2.

Исходя из симметрии по точкам преобразования, можно еще сократить объем памяти ППЗУ и время вычисления, т.к. одновременно получается результат по (N/2-k)-M и (К/2+к)-й точкам. Сокращение объема памяти по количеству Fk в два раза приводит к тому, что в схеме ПДПФ используется 12 корпусов по 2 байт и 1 корпус ППЗУ на 2 байт - для основных ПЗУ и 3 корпуса по 29 байт - для дополнительных ПЗУ. Следовательно, Q3=::(15 29+28)=8 Кбайт. При этом время преобразования Тз=Т2/2. Легко показать, что выигрыш в затратах памяти примерно в 3...4 раза сохраняется при всех N. По этой причине схема ПДПФ с двухступенчатым разделением последовательности данных представляет практический интерес. Расчет весовых коэффициентов W для программирования ППЗУ в этом случая проводился по программе, блок-схема которой приведена на рис. 1.5-1.6.

Оптимизация непозиционных устройств цифровой обработки сигналов

Операционный узел (рис. 2.10) содержит узлы 17-1 - 17-2 постоянной памяти, регистры 18-1 - 18-4, элементы И 19-1, 19-2, 20-1, 20-2, элементы ИЛИ 21-1, 21-2, элементы И 22-1, 22-2, 23-1, 23-2, элементы ИЛИ 24-1, 24-2, элементы И 25-1, 25-2, 26-1, 26-2. Блок восстановления результата (2.11) содержит узлы 27-1 - 27-3 постоянной памяти, регистры 28-1 - 28-4, регистр 29 константы, сумматоры 30 и 31, операционные узлы 32-1, 32-2, каждый из которых включает в себя сумматоры 30 и 31, элемент НЕ 33, элементы И 34 и 35, регистр 36. Кроме того в состав блока входит сумматор 37, регистр 38 констант, регистры 39-1 - 39-4. При этом совокупность перечисленных выше узлов блока, кроме регистров 39-1 - 39-4, представляет собой формирователь кода, которых в составе блока восстановления четыре (4-1 - 4-4).

Устройство БПФ-СОК работает следующим образом. Входные числа x[nT], (n = \,Nc) через шину данных поступают в блоки 1 определения вычетов,

формирующих v параллельных каналов обработки чисел в кольце вычетов по выбранным модулям. Блоки 1 строятся на логических схемах или (как в схеме) на ПЗУ 6, в которых каждое число на входе является адресом вычета. Число х[пТ] считывает из узла 6 соответствующий вычет xs[nT]. Кроме того, блоки 1 содержат распределитель 7 импульсов (например трехразрядный счетчик с дешифратором) и элементы И 8. Данные группируются по Nc/8 чисел. При этом устройство не требует общепринятой двоичной инверсии. Данные делятся на две группы четных и нечетных номеров чисел: х(0), х(2), х(4), х(6), х(8), х(10), х(12), ...и х(1), х(3), х(5), х(7), х(9), х(11)..., а каждая из этих групп делится на четыре подгруппы: Таким образом, первая подгруппа чисел с четными номерами записывается в узлы памяти (ОЗУ) 10-1, вторая в - 10-2..., четвертая подгруппа чисел с нечетными номерами - в 10-8. Узлы памяти имеют различный объем памяти:

После записи массива чисел хс[кТ] в узлы памяти каждого канала начинается собственно процесс преобразования. На первых (L-1) -м шагах (L = log2 Nc) вычислительный блок отключен от СВР (не формируется сигнал Тю и не открываются элементы 25 и 26 И), выходы соединены с соответствующими входами узла памяти 10-1... 10-8 при подаче от блока управления сигнала Т6...Т9, открывающих элементы И 19, 20, 22, 23. Сигналом М = \ (М=0) включены элементы И 12-1 и 12-2, выключены 13-1 и 13-2 и обеспечивается одновременная работа двух операционных узлов 16-1 и 16-2. При этом узел памяти 11-1 подключен к 16-1, а узел 11-2 -к 16-2. Для реализации при прореживании во времени операция «бабочка» (C = A + BWk)n (D = A-BWk) в СОК в блоках З-s программно формируются веса W и V для к и (к+1)-й операции, а так же для {к + N12) и {к + N12 +1) операций. При этом, как указано выше, Ws -Vs , a Vs = Ws , что и учтено соответствующим подключением к элементам 14-1 и 14-2 (рис.2.9) входов 9-12, по которым подаются веса W , V , W + , V + . Следовательно, в блоках З-s дополнительно к известному алгоритму определяются вычеты весов W и V по соответствующему модулю Ng. В схеме операционного узла (рис.2.10) в узлах 17-1...17-4 хранятся вычеты арифметических операций умножения, а в узлах 17-5... 17-8 - вычеты арифметических операций сложения. Каждое из узлов 17 имеет объем памяти 2R 2 s слов разрядностью по Rg. В узле 17-1 по адресу, соответствующему к двоичному 2К$-разрядному коду, составленному из слов В и W , хранится результат BW (аналогично для 17-3), а в узле 17-2 по адресу, составленному стыковкой слов В и V , хранится результат BV (аналогично для 17-4). В узлах 17-5 и 17-7 по 2ІІ8-разрядньім адресам [ A , BW ] хранятся вычеты C =«A + BW , а в узле 17-6 и 17-8 хранятся вычеты D =«A + BVk».

На последнем шаге преобразования (при Л/ = 0, М=1) выключаются элементы И 12-1, 12-2, включаются элементы И 13-1, 13-2, узлы памяти 10-1, 10-2, 10-5, 10-6 подключаются к операционному узлу 16-1. Выход 16-1 (его регистр 18) через элементы И 25, 26, открываемые сигналом Тю=1, подключаются к блоку 4. В блоке 4 в узле 27-1 хранятся априорные суммы Si = aipi+a2p2 N, в узле 27-2 - S2 = a3p3+a4p4 N, в узле 27-3 - S3 = a5P5+oc6p6 N. Регистры блока 4 обеспечивают конвейерный режим работы на L-м шаге. Вычеты Sp в узлах 27-1 и 27-2 подаются в логическую схему, состоящую из сумматоров 30 и 31 и двух элементов И 34, 35. Если Si+S2 N (-N хранится в регистре 29), то в знаковом разряде сумматора 31-единица, открыт элемент И 35 и сумма SI+S2 N считывается в регистр 38. Если же Si+S2 выходят за пределы N, то в знаковом разряде сумматора - ноль, открыт элемент 35 и число SI+S2-N K= SI+S2 N считывается в регистр 38. Аналогично работает узел 32-2. Специфическое представление "0" через N/2 требует при восстановлении проведения операции нормализации чисел. Из числа Ffc на выходе узла 32-2 вычитается N/2 (N/2 хранится в регистре 36) в сумматоре 37. Здесь же результат нормируется сдвигом запятой на R-2 разряда влево. Четыре одинаковых модуля СВР использованы для одновременной _& _ +1 —k + 2 —к + 3 обработки 4-х чисел а„ , а„ , а„ , а с выхода каждого канала. Результат преобразований , F .+1, +2 &+3 из регистров 39 считываются на выход устройств БПФ-СОК.

Руководство программиста

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

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

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

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

Процедура Procedure Noise служит для получения некоторой конечной последовательности множителей, на которые может быть разложено число входных переменных N. Алгоритм разложения на множители довольно прост: осуществляется проверка на равенство частного, делимое которого представляет собой число N, а делитель - целое число от 2 до N/2. Если равенство имеет место, то данное целое число будет является одним из множителей, составляющих число N. Таким образом получается однонаправленный список длиной к, элементы которого являются множителями числа N.

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

При выполнении процедуры Procedure Count происходит вызов основной рекурсивной подпрограммы выполнения алгоритма БПФ MainCount. В эту подпрограмму передается из процедуры Count номер множителя, по которому следует проводить ДПФ на одном из шагов выполнения алгоритма БПФ. Кроме того осуществляется присвоение входным данным значений, полученных в результате ДПФ по какому-либо из множителей. Оно необходимо для простоты использования предыдущих результатов вычисления.

Процедура Procedure Main_Count является основной подпрограммой выполнения алгоритма БПФ. Она является рекурсивной, т.к. заранее неизвестно количество множителей, на которые будет разложено число N. Эта процедура использует номер множителя, по которому производится ДПФ и который вычисляется в процедуре Count. Если номер множителя равен і, то для этого множителя необходимо осуществить N/ki ДПФ, т.е. для этого необходимо перебрать все значения каждого из остальных к-1 элементов, меняющихся от О до ki-1, где і - номер элемента: начиная с первого элемента, производится рекурсивный вызов ki раз процедуры Main_Count, которая в свою очередь, вызывает рекурсивно процедуру Main_Count от 0 до кг-1 (кг раз) и т.д. Такие рекурсивные вызовы будут выполняться к раз, причем, если номер элемента равен і (номеру элемента по которому производится ДПФ), то на і-ом шаге рекурсии программа его попросту пропускает. На к+1 шаге рекурсии, который тоже вызывается рекурсивно, проводится ДПФ по элементу с номером і. Число

ДПФ равно к кг ... .! ki+1 ... kk=N/ki; т.е. обрабатывается целиком вся многомерная таблица. Кроме того на к+1 шаге происходит умножение каждого элемента многомерной матрицы на нужный поворачивающий множитель.

Процедура Procedure Outing служит для вывода получившегося результата в текстовый файл. Числовые элементы результата переводятся в текстовые строки и последовательно записываются в файл: сначала вещественная часть элемента результата, затем комплексная.

Процедура Procedure Graphics служит для вывода на экран результатов работы в виде графиков. В процедуре осуществляется инициализация графического режима, его закрытие и вызов процедуры Graphics 1.

Процедура Procedure Graphics 1 предназначена для вывода на экран сходных между собой по структуре изображений.

В процедуре Procedure Done осуществляется очистка ОЗУ компьютера, т.к. при выходе программа не уничтожает автоматически те места памяти, которые заняты списковыми структурами данных, что может привести к зависанию компьютера.