СОВРЕМЕННАЯ ЭЛЕКТРОНИКА №7/2012

ПРОГРАММИРОВАНИЕ дут следовать в порядке 0, 64, 32, 96, 16, 80 и т.д. Затем для каждого единичного сиг нала вычисляется спектр. На этом эта пе не требуется никаких программных действий, поскольку спектр единично го сигнала равен соответствующему базисному сигналу ДПФ. Последний шаг БПФ заключается в объединении единичных спектров. Этот шаг являет ся самым сложным и выполняется в несколько этапов. Основная операция объединения спектров, изображённая на рисунке 1, называется «бабочкой» (butterfly). Алгоритм, при котором опе рация «бабочка» одновременно выпол няется для двух входных сигналов, на зывается БПФ с основанием 2. Именно такой алгоритмрассматривается в дан ной статье. Другим распространённым основанием БПФ является 4. Операция «бабочка», в своюочередь, состоит из нескольких этапов. Сначала второй входной сигнал IN2 умножает ся на поворачивающий коэффициент W N (twiddle factor). Затем первый вы ходной сигнал OUT1 получается путём суммирования результата умножения и первого входного сигнала IN1. Вто рым выходным сигналом является раз ность между первым входным сигна лом IN1 и результатом умножения. Для полного объединения спектра размер ностью N отсчётов требуется выполне ние log 2 N циклов операций «бабочка». При размерности 128 требуется 7 цик лов, причём каждый цикл состоит из 64 операций, так как при основании 2 в одной базовой операции БПФ за действовано два входных отсчёта. Полная схема БПФ для 128 отсчётов достаточно громоздкая, поэтому на ри сунке 2 в качестве примера изображе на схема БПФ для 8 отсчётов, которая состоит из трёх циклов (log 2 8). В зави симости от порядка использования по ворачивающих коэффициентов и опе рации «бабочка» различают БПФ с прореживанием по времени и БПФ с прореживанием по частоте. На рисун ке 2 изображён алгоритм с прорежива нием по времени, этот же алгоритм ре ализован в модуле для ПЛИС; видно, что входные отсчёты отсортированы согласно бит реверсной адресации. Во время первого цикла для всех «ба бочек» используется один и тот же по ворачивающий коэффициент W 0 . Па ры отсчётов для второго цикла фор мируются согласно рисунку 2, при этом поворачивающие коэффициен тыначинают чередоваться: для первой «бабочки» используется коэффициент W 0 , для второй – W 2 , для третьей и чет вёртой – снова коэффициенты W 0 и W 2 соответственно. Во время третьего цикла используются все поворачива ющие коэффициенты W 0 – W 3 . Заметим, что общее число повора чивающих коэффициентов равно по ловине размерности входного сигнала, т.е. для входного сигнала размер ностью 128 отсчётов потребуется 64 коэффициента. Пары сигналов в этом случае будут формироваться аналогич но БПФдля 8 отсчётов. Во время перво го цикла все операции умножения бу дут выполняться с поворачивающим коэффициентом W 0 , во время второго цикла будут чередоваться коэффици енты W 0 и W 32 , во время третьего цикла будут чередоваться коэффициенты W 0 W 16 W 32 W 48 , во время четвёртого цик ла – W 0 W 8 W 16 W 24 W 32 W 40 W 48 W 56 . Таким образом, число задействован ных коэффициентов будет увеличи ваться, и во время последнего, седь мого цикла, будут задействованы все 64 поворачивающих коэффициента. А ППАРАТНАЯ РЕАЛИЗАЦИЯ БПФ Рассмотрим более подробно реали зацию описанного выше алгоритма БПФдля ПЛИС. Блок схема системына кристалле, реализующей алгоритм, изображена на рисунке 3. Через порт UART происходит тестирование ядра 63 WWW.SOEL.RU СОВРЕМЕННАЯ ЭЛЕКТРОНИКА ◆ № 7 2012 W N OUT1 = IN1 + IN2 × W N IN1 IN2 OUT2 = IN1 – IN2 × W N Рис. 1. Базовая операция БПФ IN[0] W 0 W 0 W 1 W 0 W 0 W 0 W 0 W 0 W 2 W 2 W 3 W 2 IN[4] IN[2] IN[6] IN[1] IN[5] IN[3] IN[7] OUT[0] OUT[1] OUT[2] OUT[3] OUT[4] OUT[5] OUT[6] OUT[7] Рис. 2. БПФ для 8 точечного входного сигнала Реклама ' СТА - ПРЕСС