ЖУРНАЛ СТА №4/1999

66 4/99 В ЗАПИСНУЮ КНИЖКУ ИНЖЕНЕРА CTA Сегодня большинство современных устройств автомати- зации, способных обрабатывать сигналы различной при- роды в режиме реального времени, разрабатываются на ба- зе высокоскоростных процессоров цифровой обработки сигналов (ЦОС). При этом преобразование Фурье является важным инструментом цифрового спектрального анализа, который наиболее часто используется в системах ЦОС. В этом случае для систем реального времени (СРВ) становит- ся актуальной проблема разработки максимально эффек- тивного программного кода данного алгоритма, требую- щего минимального времени выполнения при фиксиро- ванном объеме памяти. В общем случае универсальная про- грамма для любых приложений СРВ вряд ли существует, и основная цель разработчика — решить задачу оптимально- го выбора вида программирования и основания алгоритма в зависимости от длины преобразования, доступного раз- мера памяти и требуемого времени выполнения. Как известно, элементарная процедура быстрого преоб- разования Фурье (БПФ) по произвольному основанию со- стоит в многократном выполнении базовой операции «ба- бочка» над разными частями входных данных. При этом данная операция может быть оформлена как макрорасши- рение или как подпрограмма. С одной стороны, необходи- мость расчета текущих адресов данных и поворачиваю- щих множителей увеличивает время выполнения всего ал- горитма, что делает целесообразным оформить процедуру «бабочка» как макрорасширение. При таком программи- ровании однотипные процедуры с использованием непо- средственной адресации записываются друг за другом, как этого требует алгоритм преобразования, образуя линей- ную структуру (линейное программирование). С другой стороны, использование макрорасширений неизбежно приводит к значительному увеличению требуемого объе- ма памяти для хранения программного кода. Использование же подпрограмм позволяет получить компактный программный код, размер которого не зави- сит от длины преобразования. В этом случае текущие адре- са операндов и коэффициенты преобразования рассчиты- ваются на этапе работы программы, что приводит к неко- торому увеличению времени реализации всего алгоритма. При комбинированном варианте программирования це- лесообразным является расчет поворачивающих множи- телей на этапе инициализации или определение их кон- стантами в доступной памяти данных. Во врезке статьи приведен листинг программной реали- зации алгоритма БПФ длиной 512 точек для процессора TMS320C25. В данном случае базовая операция оформлена как подпрограмма, а коэффициенты преобразования оп- ределены константами в виде четырех выделенных блоков данных (листинг, метка МЕТ1:). Для оценки эффективнос- ти разработанной программы в таблице 1 представлены требуемый объем памяти и время выполнения программы при различных длинах преобразования и видах програм- мирования. Из таблицы 1 видно, что если длина преобразования БПФ не превышает 128 точек, использование макрорасши- рений позволяет получить некоторый выигрыш за счет меньшего времени выполнения. Однако при длинах пре- образования, превышающих 256 точек, линейное про- граммирование становится неэффективным, а в некото- рых приложениях даже неосуществимым из-за больших объемов требуемой памяти. Что касается разработанной программы, то для неё затраты памяти в 50 раз меньше, чем при использовании линейного программирования. При этом время выполнения разработанной программы увели- чилось лишь в 1,6 раза при длине преобразования 512 и всего в 1,25 раза при длине преобразования 1024. Рост тре- буемого объема памяти от длины преобразования для слу- чая программирования с подпрограммами обусловлен только увеличением количества хранимых поворачиваю- щих множителей. Необходимо также отметить, что подав- ляющее большинство существующих стандартных библи- отек функций, предлагаемых фирмой-разработчиком Texas Instruments и имеющих в своем составе процедуру БПФ, основываются именно на программировании с ис- пользованием макрорасширений. Продолжая разговор об эффективной реализации алго- ритма БПФ, необходимо отметить ряд важных особеннос- тей, связанных со структурой алгоритма и комплексным характером преобразования. Известно, что в случае, когда длина дискретного преобразования Фурье (ДПФ) N = n 1 n 2 ...n k ...n K , в частном случае N = n K (именно такое ДПФ называют быстрым преобразованием Фурье по основанию n), возможно значительное сокращение объема вычисле- ний ДПФ, а сам алгоритм распадается на две части: выпол- нение Kn K–1 операций n-точечного ДПФ («бабочка») и вы- полнение операции перестановки, так как порядок вход- ных и выходных индексов меняется. Последовательность выполнения операций может быть произвольной. При этом, если выполнить вначале операцию «бабочка», то вы- ходные отсчеты БПФ будут располагаться в поразрядно- обратном порядке при представлении индексов в системе счисления по основанию n, то есть входному отсчету с по- рядковым номером i вх = p m n m-1 + p m-1 n m–2 + ... + +p 2 n 1 + p 1 n 0 будет соответствовать выходной отсчет i вых = p 1 n m-1 + p 2 n m–2 + ... + p m-1 n 1 + p m n 0 . Кроме конвейерной обработки команд процессором, воз- можности аппаратного умножения 16-битовых слов (16х16) или выполнения операции свертки (А*В+С) за один такт, Программа быстрого преобразования Фурье для устройств автоматизации на базе процессора TMS320 Александр Агапиев, Виктор Милашенко