ЭУМК по дисциплине "Программирование проблемно-ориентированных вычислительных средств реального времени" › Теория › Тема 5. Программирование алгоритмов БПФ с прореживанием по частоте

# Электронный учебно-методический
комплекс по дисциплине
"Программирование проблемно-ориентированных вычислительных средств реального времени"

для специальности

1-40 02 02 «Электронные вычислительные средства»

Оглавление | Программа | Теория | Практика | Контроль знаний | Об авторах

5.4. Реализация алгоритма векторного БПФ
5.4.1. Одновременная обработка двух действительных сигналов

При обработке реальных физических сигналов они заносятся в действительные части комплексных чисел временного процесса, а мнимые части при этом обнуляются. Но с помощью одной программы БПФ можно обработать сразу два действительных сигнала. Для этого необходимо использовать эти два действительных сигнала для задания действительной и мнимой частей временного процесса. Если {x1(n)} и {x2(n)} действительные последовательности длины N, X1(k) и X2(k), k = их ДПФ соответственно, а U(k) = Re[U(k)] + j Im[U(k)], k = ДПФ комплексной последовательности

| z(n) = x1(n) + j x2(n), n = , | (5.1)

то:

|  | (5.2)

где X1 , X2 – изображения первого и второго действительных процессов, U – изображение комплексного процесса, полученное с помощью БПФ.
Преобразовав выражения (5.2) для расчета U(k) по изображениям двух действительных процессов X1 , X2, мы сможем вычислить обратное БПФ и получить временные реализации двух независимых действительных сигналов (5.3).

|  | (5.3)

5.4.2. Одновременная обработка нескольких пар действительных сигналов

При обработке реальных многомерных физических сигналов к парам можно применить преобразование (5.1) и затем несколько раз выполнить обычное БПФ. А можно модифицировать алгоритм БПФ таким образом, чтобы он обрабатывал базовые операции с одинаковыми поворачивающими множителями для всех пар сигналов (внутренний короткий цикл). При этом число итераций остается тем же, что и для одной пары сигналов. После вычисления БПФ необходимо произвести разделение полученного изображения комплексного процесса на два изображения действительных процессов в соответствии с формулами (5.2).
Возьмем для примера алгоритм Формана для БПФ с прореживанием по времени, без замещения и не требующий двоично-инверсной перестановки данных:
Am(J) = Am-1(IP) + Am-1(IQ) WJK
Am(L) = Am-1(IP) – Am-1(IQ) WJK .
Для получения алгоритма векторного БПФ необходимо выполнить следующую модификацию индексов:
JK = J – MOD [ J, IM ] – NK ,
IP = J + JK , IQ = JP + IM ,
W = exp ( –j2Π/N ) , IM = 2a-m ,
N = 2a – длина выборки, a – число итераций, m = 1, 2, …, a – номер итерации,
J = NK, 1+NK, 2+NK, …, (N/2-1)+NK ,
L = N/2+NK, N/2+1+NK, N/2+2+NK, …, (N-1)+NK ,
NK = 0, 1, …, r/2 – 1, r – мерность процесса .

Пример программы приведен ниже.

    type	COMPLEX = record
    	RE, IM : real
    	End;
    type	VECT = array [ 1 .. N ] of COMPLEX ;
    type	MATR1 = array [ 1 .. R ] of VECT ;

    procedure FFFTM ( N, M, INV : integer ; var WXS : MATR1 ) ;
    var
    	I, L, IP, IQ, JK, IM, N2, K, K1 : integer ;
    	sign, AR, ARG, F : real ;
    	T2 : MATR1 ;
    	W : VECT ;
    	A, B, W1 : COMPLEX ;
    	SW : boolean ;
    label	1, 2 ;
    begin
    SW := true ;
    N2 := N div 2 ;
    SIGN := -1 ;
    if INV = 0 then SIGN := 1 ;
    AR := 3,14159 / N2 ;
    ARG := 0 ;
    for I := 1 to N2 do ;
       begin
       W[I].RE := cos(ARG) ; W[I].IM := SIGN * sin(ARG) ;
       ARG := ARG + AR ;
       end ;
    IM := N2 ;
    1:
    for K := 1 to N2 do ;
       begin
       K1 := K – 1 ; JK := K – K1 mod IM ;
       W1 := W[JK] ;
       for I := 1 to M do ;
          begin
          L := K + N2 ;
          IP := K + JK – 1 ; IQ := IP + IM ;
          if SW then
             begin
             A := WXS[I][IP] ;
             B.Re := WXS[I][IQ].Re * W1.Re – WXS[I][IQ].Im * W1.Im ;
             B.Im := WXS[I][IQ].Re * W1.Im + WXS[I][IQ].Im * W1.Re ;
             T2[I][K].Re := A.Re  + B.Re ;
             T2[I][K].Im := A.Im  + B.Im ;
             T2[I][L].Re := A.Re  – B.Re ;
             T2[I][L].Im := A.Im  – B.Im ;
             end
                else
             begin
             A := T2[I][IP] ;
             B.Re := T2[I][IQ].Re * W1.Re – T2[I][IQ].Im * W1.Im ;
             B.Im := T2[I][IQ].Re * W1.Im + T2[I][IQ].Im * W1.Re ;
             WXS[I][K].Re := (A.Re  + B.Re) /2 ;
             WXS[I][K].Im := (A.Im  + B.Im) /2 ;
             WXS[I][L].Re := (A.Re  – B.Re) /2 ;
             WXS[I][L].Im := (A.Im  – B.Im) /2 ;
             end ;
          end ;

       end ;
    IM := IM div 2 ; SW := not SW ;
    if IM <> 0 then goto 1 ;
    if SW then goto 2 ;
    F := 1 ; if INV = 0 then F := 2 ;
    for I := 1 to M do ;
       begin
       for K := 1 to N do ;
          begin
          WXS[I][K].Re := T2[I][K].Re / F ;
          WXS[I][K].Im := T2[I][K].Im / F ;
          end ;
       end ;
    2: end;

Оглавление | Программа | Теория | Практика | Контроль знаний | Об авторах
© БГУИР , 2012