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

на базе процессора TMS320

Александр Агапиев, Виктор Милашенко

 

Источник: http://www.cta.ru/cms/f/366642.pdf

 

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

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

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

Во врезке статьи приведен листинг программной реализации алгоритма БПФ длиной 512 точек для процессора TMS320C25. В данном случае базовая операция оформлена

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

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

Из таблицы 1 видно, что если длина преобразования БПФ не превышает 128 точек, использование макрорасширений позволяет получить некоторый выигрыш за счет меньшего времени выполнения. Однако при длинах преобразования, превышающих 256 точек, линейное программирование становится неэффективным, а в некоторых приложениях даже неосуществимым из-за больших объемов требуемой памяти. Что касается разработанной программы, то для неё затраты памяти в 50 раз меньше, чем при использовании линейного программирования. При этом время выполнения разработанной программы увеличилось лишь в 1,6 раза при длине преобразования 512 и всего в 1,25 раза при длине преобразования 1024. Рост требуемого объема памяти от длины преобразования для случая программирования с подпрограммами обусловлен только увеличением количества хранимых поворачивающих множителей. Необходимо также отметить, что подавляющее большинство существующих стандартных библиотек функций, предлагаемых фирмой-разработчиком Texas Instruments и имеющих в своем составе процедуру БПФ, основываются именно на программировании с использованием макрорасширений.

Продолжая разговор об эффективной реализации алгоритма БПФ, необходимо отметить ряд важных особенностей, связанных со структурой алгоритма и комплексным характером преобразования. Известно, что в случае, когда длина дискретного преобразования Фурье (ДПФ) N=n1n2...nk...nK, в частном случае N = nK  (именно такое ДПФ называют быстрым преобразованием Фурье по основанию n), возможно значительное сокращение объема вычислений ДПФ, а сам алгоритм распадается на две части: выполнение KnK–1 операций n-точечного ДПФ («бабочка») и выполнение операции перестановки, так как порядок входных и выходных индексов меняется. Последовательность выполнения операций может быть произвольной. При этом, если выполнить вначале операцию «бабочка», то выходные отсчеты БПФ будут располагаться в поразрядно-обратном порядке при представлении индексов в системе счисления по основанию n, то есть входному отсчету с порядковым номером iвх = pmnm_1 + pm_1nm–2 + ... ++p2n1 + p1n0 будет соответствовать выходной отсчет iвых = p1nm_1 + p2nm–2 + ... + pm_1n1 + pmn0.

Кроме конвейерной обработки команд процессором, возможности аппаратного умножения 16_битовых слов (16х16) или выполнения операции свертки (А*В+С) за один такт, TMS320C25 располагает дополнительными способами адресации, которые обеспечивают быстрое выполнение операции перестановки для алгоритма БПФ по основанию 2.

 

 

Таблица 1. Объем памяти и время выполнения программы БПФ при различных длинах преобразования и видах программирования

 

 

Имеющаяся в TMS320C25 возможность использования обратного распространения переноса позволяет переставлять входные или выходные данные одновременно с выполнением процедуры ввода-вывода данных. Этот режим адресации является частью косвенной адресации, выполняемой с помощью дополнительных регистров и связанного с ними арифметического устройства. В таком режиме (режим формирования индексного адреса) значение (индекс), находящееся во вспомогательном регистре AR0, или складывается, или вычитается из дополнительного регистра, на который указывает ARP (указатель вспомогательного регистра). Однако разряд переноса распространяется не в прямом, а в обратном направлении, в результате чего выполняется перестановка имеющихся адресов.