Исследование и разработка аппаратурно-ориентированных алгоритмов ДПФ

Дискретное преобразование Фурье (ДПФ) широко применяется на практике для цифровой обработки сигналов (ЦОС), например, в задачах спектрального анализа. Известно, что ДПФ может использоваться в быстрых алгоритмах вычисления корреляции и свертки. Свертка, как и ДПФ, является одной из базовых операций ЦОС. Она применяется для цифровой фильтрации, wavelet-пpeoбpaзoвaния, которое часто более эффективно, чем спектральный анализ /40/.

Развитие аппаратурных средств позволяет более эффективно организовывать вычислительный процесс. Широкий набор доступных на рынке сигнальных процессоров и программируемых логических интегральных схем предоставляет большие возможности для реализации систем ЦОС. Но при этом усложняется выбор аппаратных средств и алгоритмов. Эффективность последних определяется архитектурой системы, особенностями реализации базовых узлов вычислительной техники (ВТ). Возрастает спрос на системы автоматизации процесса оценки эффективности и поиска оптимальных комбинаций алгоритмов и аппаратуры. В таких условиях актуальной становится задача разработки алгоритмов построения алгоритмов, создания необходимой для этого базы знаний. Кроме того, удобно было бы иметь некий синергетический критерий эффективности алгоритмов при реализации их на конкретной аппаратуре, аналогичный коэффициенту полезного действия машин.

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

БПФ очень полезны при блочной обработке данных. В системах ЦОС, работающих в реальном масштабе времени (РМВ), часто необходимо применять скользящую обработку данных. Для.

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

Рассмотрим области применения методов ЦОС и ДПФ в частности /1−2,6,8−9,12/. Из табл.1.1 видно, что требуемая производительность и точность сильно варьируются в зависимости от сферы применения, как и диапазоны частот обрабатываемых сигналов.

Области применения ЦОСТабл .1.1.

Сфера применения Диапазон частот Точность, бит Производительность, млн.оп./с.

Речь:синтез, распознавание, сжатие, кодирование 100Гц-40кГц 12−32 1−100.

Гидролокация 2−40кГц 12−32 1−100.

Геология:обработка сейсмической информации, тектоника горных пород, нефтеразведка, геотермальные проявления 0−100кГц 8−32 1−100.

Радиолокация:поиск и обнаружение объектов в пространстве, определени е их параметров 10МГц-10ГГц 6−12 100−1000.

Изображение:сжатие, распознавание, восстановление, компьютерная томография 4−16 10-Ю6.

Известны разнообразные специализированные устройства для вычисления ДПФ /12/. Более широкое применение находят цифровые процессоры обработки сигналов (ЦПОС). В табл. 1.2 приведены характеристики 16-битных ЦПОС с фиксированной запятой, в табл. 1.3 — 32-битных. Рассматривается комплексное 1024-точечное БПФ /28/.

Характеристики 16-разрядных ЦПОС Табл.1.2.

ЦПОС Частота, МГц Количество тактов Время 1024-т. БПФ, мс.

ТМ3320С25 12.5 113 467 9.08 .

АБЗР-2105 13.8 34 500 2.5.

ТМ3320С50 40 84 833 2.12.

АВБР-2181 33 34 625 1.04.

Характеристики 32-разрядных ЦПОС Табл.1.3.

ЦПОС Частота, МГц Количество тактов Время 1024-т. БПФ, мс.

ТМБ320С30 20 60 800 3.04.

ТМЭ320С40 40 38 945 0.97.

АБЗР-21 020 33 19 245 0.58.

АБЭР-гЮбО 40 18 221 0.46.

В теории быстрых алгоритмов ЦОС /1/ разработано большое количество способов вычисления ДПФ. Известны, например, БПФ алгоритмы Кули-Тьюки, Гуда-Томаса, Рейдера-Бреннера, Винограда. Алгоритм Рейдера позволяет вычислять ДПФ через свертку. Иногда это дает выигрыш, хотя одним из хороших методов вычисления самой свертки является использование БПФ и теоремы о свертке. Предложен широкий набор параллельно-конвейерных структур для БПФ /1,16,22−25/.

Поэтому актуальна проблема выбора оптимальных комбинаций аппаратного и алгоритмического обеспечения систем ЦОС. Еще сложнее определить, что такое «оптимальная комбинация». Критерий оптимальности должен задаваться в каждом конкретном случае прикладной задачей. Следовательно, необходима методика оптимизации аппаратурноалгоритмического обеспечения по заданному критерию. В идеале должна быть система автоматизированного поиска лучших вариантов с учетом всевозможных критериев, включая топологические характеристики графов зависимости алгоритмов и вероятности пробоев полупроводников. Но в задачи конструктора алгоритмов, как правило, не входит расчет надежности будущих систем на их основе. Поэтому в данной работе в качестве критерия оптимальности будут приняты приведенные аппаратурно-временные затраты на один бит результата. Этот критерий является упрощенным случаем синергетического критерия эффективности алгоритмов, который связан с приращениями информационной и термодинамической энтропий /2 9/. Термодинамические ограничения с развитием технологии становятся более существенными, чем ограничения на топологические свойства сигнальных графов, благодаря многослойности структур и применению оптики. Но такая характеристика как число входов и выходов графа ограничивается количеством выводов микросхемы, то есть является решающей во многих случаях. Именно ограниченная пропускная способность входных и выходных шин является все чаще причиной отказа от параллельных алгоритмов БПФ и использования прямого вычисления ДПФ. Действительно, при больших частотах тактирования за время, которое требуется для приема очередного значения сигнала, можно полностью обновить спектральные коэффициенты, используя предыдущее значение. Прямое вычисление ДПФ используется при выполнении скользящего ДПФ, хотя существуют разные способы для этого /2 6/. В последнем случае часто используются рекуррентные соотношения, и, следовательно, неизбежно накопление ошибки. Меры по её ограничению приводят к дополнительным аппаратурно-временным расходам. Для выбора лучших вариантов вычисления ДПФ при заданных условиях нужно иметь базу знаний по всевозможным способам реализации необходимых базовых узлов ВТ. Это, например, сумматоры, умножители, устройства вращения вектора. Существует множество вариантов их исполнения, которые характеризуются различными временными и аппаратурными затратами в зависимости от точности результата и других параметров /12,15,27/. Ясно, что аппаратурные затраты на целевое устройство ЦОС равны сумме затрат на отдельные узлы плюс затраты на их межсоединения. Временные затраты равны сумме соответствующих затрат узлов, входящих в критический путь сигнального графа, плюс затраты на их межсоединения. В данной работе затраты на соединения не рассматриваются, хотя при необходимости могут быть добавлены в общую схему. В первом приближении эти затраты могут выражаться через некоторый процент от полных затрат, который зависит от схемотехнологического базиса и постоянной времени проводников. Для уточненной оценки необходимо рассчитывать длину связей, их конфигурацию в пространстве и электромагнитные свойства материалов, что выходит за рамки данной работы.

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

Основными направлениями исследований являются:

1)оценка и сравнение характеристик известных алгоритмов вычисления ДПФ;

2)оценка затрат на реализацию основных операций, используемых при вычислении ДПФ;

3)разработка методики поиска оптимальных алгоритмов БПФ для заданных характеристик устройства и критерия эффективности;

4)получение ряда оптимальных алгоритмов БПФ для конкретного примера;

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

Структура диссертации определяется сформулированными задачами. Работа содержит введение, четыре основные главы, заключение и приложения. Во введении обосновывается.

5.5. Выводы.

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

Были предложены области применения нового алгоритма ДПФ с разверткой вектора. Достигаемое при его использовании уменьшение аппаратурно-временных затрат до 50% позволяет расширить область применения скользящего ДПФ. Если за период дискретизации сигнала можно обновить все спектральные коэффициенты, то вместо алгоритма БПФ эффективнее может быть применение алгоритма скользящего ДПФ с разверткой вектора. Аппаратурная реализация последнего проще и дешевле, чем аппаратурная реализация алгоритма БПФ, например, бабочки. Были рассмотрены результаты макетирования системы обработки речи на основе ПК и плат ввода-вывода звука с системой синхронизации и сопряжением с телефонной линией. Алгоритм ДПФ с разверткой вектора хорошо подходит для компактной аппаратурной реализации в ПЛИС. Было проведено макетирование такого устройства в САПР ПЛИС Max+Plus на основе микросхемы типа FLEXIОК.

6.

ЗАКЛЮЧЕНИЕ

.

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

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

В работе получены следующие основные теоретические и практические результаты:

1)предложен синергетический критерий эффективности алгоритма (СКЭА) и связанный с ним критерий приведенных аппаратурно-временных затрат (ПАВЗ);

2)предложена методика нахождения оптимальных алгоритмов БПФ для заданного критерия оптимальности;

3)синтезирован новый алгоритм вычисления скользящего ДПФ на основе блока развертки векторадоказана его эффективность для определенной области значений длин блоков данных и точности вычислений по сравнению с известными алгоритмами по критерию ПАВЗ;

4)проведено моделирование разработанных алгоритмов на ЭВМ, предложены области их применения.

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

Во второй главе показана связь критерия ПАВЗ с синергетическим критерием эффективности алгоритма. Последний является более универсальным, и применим как к цифровым, так и к аналоговым устройствам. С развитием технологии СБИС ограничения на топологические характеристики графов зависимости алгоритмов ослабевают, а ограничения на выделяемое тепло усиливаются. СКЭА как раз и учитывает выделение тепла при получении информации. Для цифровых устройств этот критерий можно упростить и свести к критерию ПАВЗ. Для каждой задачи может быть определен некий ориентировочный уровень ПАВЗ, при достижении которого алгоритм может быть признан эффективным.

Рассмотрим, например, некоторые устройства для вычисления ДПФ по материалам реферативных журналов /12/.

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

1)умножитель для комплексных чисел РБЗР16 112А;

2)два аккумулятора для комплексных чисел РБ5Р16 316А;

3)адресный генератор РБЭР 1640А (40МГц)&bdquoОни ускоряют БПФ в 8 раз (до 25бмкс).

2.Процессор ДПФ на 1.2мкм КМОП-схемах с частотой тактирования 70МГц. Характеристики: 99 560 транзисторов, 144 вывода, 79 млн.оп.умн./с. Используются 15,16,17-точечные алгоритмы Винограда для выполнения 4080-точечного большого алгоритма Винограда за 118мкс, или изображения (272×272) за 4 «25мс. При этом 16-точечное БПФ вычисляется за 457нс. Арифметическая секция содержит 72 последовательных сумматора и 36 последовательных блока умножения. При 26-разрядных коэффициентах точность 20 разрядов (120дБ)"24-разрядное блочное представление данных с плавающей запятой в сочетании с адаптивным алгоритмом масштабирования обеспечивает точность ЮбдБ после 4080-точеч.ного преобразования.

3.БПФ на основе ПЗС-чипа. Длина преобразования 512 точек, точность — 13 бит. Частота выборки 10МГц, то есть 512-точечное БПФ выполняется за время 51.2мкс.

Аппаратурные и временные затраты этих устройств существенно различаются. Но критерий ПАВЗ для каждого из них находится в пределах 8еЗ-40еЗ, что уже говорит об их эффективности.

Для оценки ПАВЗ устройств вычисления ДПФ были рассмотрены различные варианты реализации сумматоров, умножителей и устройств вращения. Их аппаратурные и временные затраты даны в виде формульных зависимостей. •.

На практике часто возникает задача поиска наиболее быстрых алгоритмов ДПФ при ограниченных аппаратурных затратах. В третьей главе были рассмотрены известные алгоритмы БПФ: Кули-Тьюки, Гуда-Томаса, малые и большие алгоритмы Винограда&bdquoДля заданной длины блока данных существует большое количество различных вариантов построения алгоритмов БПФ. На основании разработанной методики и программы были получены конкретные примеры оптимальных по быстродействию алгоритмов БПФ при определенных характеристиках устройства. Таким образом, здесь решается задача поиска оптимальных комбинаций аппаратуры и алгоритмов для вычисления ДПФ. Эта методика может быть расширена на случай, когда характеристики проектируемого устройства также должны выбираться, исходя из заданного критерия оптимальности.

Алгоритмы БПФ полезны при блочной обработке данных. Для скользящего анализа они малоэффективны. Для этой цели больше подходят модифицированные способы прямого вычисления ДПФ. В связи с этим был разработан алгоритм вычисления скользящего ДПФ с разверткой вектора, который позволяет сократить аппаратурно-временные затраты в среднем в 2 раза по сравнению с известными устройствами того же назначения. Новый алгоритм хорошо подходит для реализации на программируемых логических интегральных схемах (ПЛИС), например, типа FLEX10K ф. Altera со встроенной памятью. При помощи САПР ПЛИС Max+Plus была разработана и промоделирована микросхема DFTSV32, выполняющая 32-точечное ДПФ с разверткой вектора с точностью 16 бит. Развертка вектора и обновление спектра осуществляются одновременно благодаря конвейерной организации вычислений. Очередное значение сигнала обрабатывается за 35 тактов, частота которых зависит от конкретного устройства. Например, для частоты тактирования 10МГц время перерасчета спектра при приеме очередного значения составляет 3.5мкс, то есть максимальная частота дискретизации сигнала равна 285кГц. Для сравнения, рассмотренное выше устройство БПФ на основе КМОП-блоков вычисляет 32-точечное ДПФ примерно за 8мкс при на порядок большей стоимости. Аппаратурные затраты на БРВ при этом примерно в 3 раза ниже затрат на обычный блок поворота вектора. Это дает возможность разместить весь проект на одной микросхеме, например, ЕРЕ10К20.

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

1)расширение базы знаний по различным вариантам реализации базовых узлов ВТ;

2)построение системы расчета аппаратных и временных затрат на межсоединения узлов ВТ по заданным графам зависимости алгоритмов, а также оптимизация этих графов;

3)создание новых алгоритмов ЦОС с учетом современных достижений ВТ;

4)разработка библиотеки настраиваемых модулей типовых процедур ЦОС для их аппаратурно-программной реализации на основе современных САПР ВТ;

5)создание базы знаний по задачам ЦОС и методам их решения.