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



¿'"У

. ^ е-«-' / Ж-и «- ^

Волгоградский Ордена Трудового Красного Знамени Государственный Технический университет

Силантьев Григорий Вячеславович

УДК 512.64.001.5

ИССЛЕДОВАНИЕ И РАЗРАБОТКА АППАРАТУРНО-ОРИЕНТИРОВАННЫХ

АЛГОРИТМОВ ДПФ

Специальность 05.13.16- применение вычислительной техники,

математического моделирования и математических методов в научных исследованиях

Научный руководитель: д-р техн. наук, профессор Духнич Е.И.

Диссертация на соискание.ученой степени кандидата

технических наук

ВОЛГОГРАД 1998

- 2 -СОДЕРЖАНИЕ

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ....... ' 4

1. ВВЕДЕНИЕ............................................................б

2. ПОСТАНОВКА ЗАДАЧИ, ВЫРАБОТКА КРИТЕРИЕВ, ВЫБОР НАПРАВЛЕНИЙ ИССЛЕДОВАНИЯ........................ 14

2.1. Исследование направлений развития средств ВТ

2.2. ЦОС и области применения ДПФ.............................17

2.3. Выработка критериев оптимальности алгоритмов

ДПФ.......................................................................19

2.4. Базовые узлы вычислительной техники........... 25

2.5. Конвейерные способы реализации плоских

вращений................................................39

2.6. Выводы...............................................55

3 . ПОИСК ОПТИМАЛЬНЫХ АЛГОРИТМОВ БПФ................ 5 6

3.1. Исследование известных алгоритмов БПФ......... -

3.2. Характеристики малых алгоритмов БПФ Винограда. 63

3.3. Методика нахождения оптимальных алгоритмов БПФ 64

3.4. Примеры оптимальных алгоритмов БПФ............ 67

3.5. Выводы........................................ 85

4. СКОЛЬЗЯЩЕЕ ДПФ И СПОСОБЫ ПРЯМОГО

ВЫЧИСЛЕНИЯ ДПФ.................................. 86

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

4.2. Вывод алгоритма ДПФ с разверткой вектора в

общем виде.................................... ^

4 . 3 Варианты алгоритмов ДПФ с разверткой вектора..

4.3.1. Решение для составных длин блоков

данных...........................................89

4.3.2. Решение для простых длин блоков

данных....................................... 91

4.4. Оптимизация блока развертки вектора .......... 92

4.5. Параллельно-конвейерные способы вычисления ДПФ 96

4.6. Выводы...................................... . ЮЗ

5. МОДЕЛИРОВАНИЕ И РЕАЛИЗАЦИЯ РАЗРАБОТАННЫХ

АЛГОРИТМОВ..................................... 104

5.1. Моделирование алгоритмов ДПФ на ПК...........

5.2. Применение ДПФ для обработки речи............ 113

5.3. Устройство вычисления скользящего ДПФ с

115

разверткой вектора...........................

5.4. Реализация ДПФ-устройства в САПР ПЛИС........ 125

5.5. Выводы....................................... 136

6 . ЗАКЛЮЧЕНИЕ..................................... 137

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ ............................141

ПРИЛОЖЕНИЕ 1......................................................................147

ПРИЛОЖЕНИЕ 2..............................................'157

ПРИЛОЖЕНИЕ 3......................................................................165

ПЕРЕЧЕНЬ СОКРАЩЕНИЙ, УСЛОВНЫХ ОБОЗНАЧЕНИЙ

АЛУ - арифметико-логическое устройство;

БПФ - быстрое преобразование Фурье;

БРВ - блок развертки вектора;

ВТ - вычислительная техника;

ДЛП - дискретное линейное преобразование;

ДПФ - дискретное преобразование Фурье;

ЛЭ - логический элемент;

ОЗУ - оперативное запоминающее устройство; оп/с - операций в секунду;

ПАВЗ - приведенные аппаратурно-временные затраты; ПЗУ - постоянное запоминающее устройство; ПЭ - процессорный элемент; ПК - персональный компьютер;

ПЛИС - программируемая логическая интегральная схема;

РМВ - реальный масштаб времени;

СБИС - сверхбольшая интегральная схема;

СКЭА - синергетический критерий эффективности

алгоритмов; СОУП - схема определения угла поворота; СП - специализированный процессор , спецпроцессор; ' СПУ - схема приведения угла; ССП - сумматор с сохранением переноса; СУП - схема управления поворотом; ЦОС - цифровая обработка сигналов; ЦП - центральный процессор; ЭВМ - электронно-вычислительная машина;

'Ж

ADD - операция сложения; AND - операция логического И;

CORDIC - Coordinate Rotation Digital Computer (цифровой компьютер для преобразования координат вращением);

CRB - Coefficient Renewal Block (блок обновления

коэффициентов) CSA - Carry-Save Adder (сумматор с сохранением переноса);

CLA - Carry Look Ahead Adder (сумматор с ускоренным

переносом); FA - Full Adder (полный сумматор); FF - flip-flop (триггер);

FLOPS - Floating point operations per second (операций

с плавающей запятой в секунду); НА - Half Adder (полусумматор); MUL - операция умножения; MUX - мультиплексор; OR - операция логического ИЛИ; RAM - Random Access Memory (ОЗУ); VSB - Vector Scan Block (см. БРВ); XOR - операция сложения по модулю два.

1. ВВЕДЕНИЕ

Дискретное преобразование Фурье (ДПФ) широко применяется на практике для цифровой обработки сигналов (ЦОС), например, в задачах спектрального анализа. Известно, что ДПФ может использоваться в быстрых алгоритмах вычисления корреляции и свертки. Свертка, как и ДПФ, является одной из базовых операций ЦОС. Она применяется для цифровой фильтрации, 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 113467 9.08 .

АБЗР-2105 13.8 34500 2.5

ТМ3320С50 40 84833 2.12

АВБР-2181 33 34625 1.04

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

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

ТМБ320С30 20 60800 3.04

ТМЭ320С40 40 38945 0.97

АБЗР-21020 33 19245 0.58

АБЭР-гЮбО 40 18221 0.46

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

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

каждом конкретном случае прикладной задачей. Следовательно, необходима методика оптимизации аппаратурно-

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

временными и аппаратурными затратами в зависимости от точности результата и других параметров /12,15,27/. Ясно, что аппаратурные затраты на целевое устройство ЦОС равны сумме затрат на отдельные узлы плюс затраты на их межсоединения. Временные затраты равны сумме

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

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

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

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

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

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

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

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

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

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

Вторая глава посвящена обоснованию выбора направления и методов исследований для решения задачи разработки аппаратурно-ориентированных алгоритмов ДПФ. На основе анализа тенденций развития технологии СБИС осуществлен выбор критериев оптимальности алгоритмов ДПФ. Рассматривается синергетический критерий эффективности алгоритма (СКЭА) и связанный с ним критерий приведенных аппаратурно-временных затрат (ПАВЗ). При описании

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

Далее рассматриваются варианты реализации сумматоров, умножителей и устройств вращения с точки зрения аппаратурных и временных затрат. На основе критерия ПАВЗ происходит сравнение этих вариантов. Например, СОБШ1С-устройство с компенсацией удлинения вектора оптимальнее реализации поворота вектора на устройстве комплексного умножения. Но последнее может также использоваться и в других целях. Таким образом, выбор осуществляется только на стадии проектирования всей системы ЦОС. Для этого необходимо иметь базу знаний по всем известным способам реализации базовых операций.

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

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

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

Четвертая глава посвящена скользящему ДПФ и устройствам прямого вычисления ДПФ. Предлагается новый алгоритм вычисления ДПФ на основе операции развертки вектора, оптимизируется блок развертки вектора (БРВ).

Рассматриваются другие способы вычисления ДПФ с точки зрения аппаратурных и временных затрат. Все алгоритмы сравниваются по критерию ПАВЗ, находится область эффективности новых алгоритмов на основе БРВ.

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

Далее было проведено моделирование ДПФ-устройства с разверткой вектора при реализации его в ПЛИС типа FLEXIOK ф.Altera. Для этих целей использовалась САПР ПЛИС Max+PlusII. Приводятся характеристики полученного устройства и результаты сравнения его с известными ДПФ-устройствами.

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

Приложения содержат листинги программ моделирования и оптимизации алгоритмов БПФ и БРВ.

Результаты диссертации были использованы при проведении госбюджетной научно-исследовательской работы "Разработка системы концептуального проектирования компьютерных сетей", выполненной по межвузовской программе "Университеты России" под руководством д.т.н., профессора Духнича Е.И.

Основные результаты, полученные в диссертации, докладывались и обсуждались на II и III межвузовских научно-практических конференциях студентов и молодых ученых Волгоградской области (Волгоград, 1995-1996гг.), I и III

Волжских городских научно-практических конференциях (Волжский, 1995г., 1997г.), на ежегодных научных конферен