ЭУМК по дисциплине "Программирование проблемно-ориентированных вычислительных средств реального времени" › Теория › Тема 3. Реализация базовых операций алгоритмов быстрого преобразования Фурье (БПФ)

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

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

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

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

Тема 3. Реализация базовых операций алгоритмов быстрого преобразования Фурье (БПФ)
3.1. Реализация базовой операции БПФ
3.1.1. Два основных алгоритма БПФ

Алгоритм БПФ с прореживанием по времени с учетом симметрии поворачивающих множителей W можно описать следующими уравнениями:

|  | (3.1)

где FK – БПФ исходной последовательности; GK и HK – БПФ последовательностей из четных и нечетных элементов соответственно, а

|  | (3.2)

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

###

### Рисунок 3.1 – Принцип БПФ с прореживанием по времени

Положение поворачивающих множителей на Z–плоскости можно изобразить в виде следующего рисунка (особые случаи для степеней кратных N/8):

###

### Рисунок 3.2 – Положение поворачивающих множителей на Z–плоскости

Функция поворачивающих множителей является симметричной и периодической, что следует из выражения (3.2) и наглядно видно из рисунка 3.2:

|  | (3.3)

Алгоритм БПФ с прореживанием по частоте описывается следующими уравнениями:

|  | (3.4)

Суть БПФ с прореживанием по частоте заключается в разбиении входной последовательности на две по формулам (3.4) и выполнении над ними БПФ в два раза меньшей размерности, что можно проиллюстрировать рисунком (для 8-точечного БПФ) (рис. 3.3).

###

### Рисунок 3.3 – Принцип БПФ с прореживанием по частоте

Выражения (3.1) и (3.4) описывают базовые операции алгоритмов БПФ с прореживанием по времени и частоте соответственно, которые иногда называют «бабочкой» из-за их графической интерпретации (рис. 3.4):

###

### Рисунок 3.4 – Графическая интерпретация базовых операций БПФ

Используя данные обозначения, базовые операции алгоритмов БПФ с прореживанием по времени и частоте могут быть представлены в следующим виде (рис. 3.5):

###

### Рисунок 3.5 – Графические представления «бабочек» БПФ

3.1.2. Вычисление «бабочки» для алгоритма БПФ с прореживанием по времени

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

Pm+1 = Pm + Qm×WNk,
Qm+1 = Pm – Qm×WNk,
где Pm = PR + j×PI; Qm = QR + j×QI; WNk = cos(x) – j×sin(x); x = (2Π/N)×k; j = ; откуда получим
Pm+1 = PR + j×PI + (QR + j×QI)×[cos(x) – j×sin(x)] =
= PR + j×PI + [QR×cos(x) + QI×sin(x)] + j×[QI×cos(x) – QR×sin(x)] =
= [PR + QR×cos(x) + QI×sin(x)] + j×[PI +QI×cos(x) – QR×sin(x)];
Qm+1 = PR + j×PI – (QR + j×QI)×[cos(x) – j×sin(x)] =
= PR + j×PI – [QR×cos(x) + QI×sin(x)] – j×[QI×cos(x) – QR×sin(x)] =
= [PR – QR×cos(x) – QI×sin(x)] + j×[PI –QI×cos(x) + QR×sin(x)].

При вычислении «бабочки» для исключения переполнения все выходные значения делятся на два.
Пример программы с прямой адресацией вычисления «бабочки» для алгоритма БПФ с замещением и прореживанием по времени:

    * DIT FFT Programm for TMS320C5402 DSP Starter Kit
    * Direct Addressing	12/11/09 20:20:00
    	.data
    *	данные
    PR	.word	0h	; действительная часть P
    PI	.word	0h	; мнимая часть P
    QR	.word	0h	; действительная часть Q
    QI	.word	0h	; мнимая часть Q
    COS	.word	0h	; действительная часть W
    SIN	.word	0h	; мнимая часть W
    	.text
    *	инициализация
    INIT	ld	#PR, DP	; текущая страница данных
    	ssbx	sxm	; расширение знака
    	ssbx	frct	; умножение дробных чисел
    *	«бабочка»
    BTRFLY	ld	QR, T	; T = QR
    	mpy	COS, a	; A = QR*cos
    	ld	QI, T	; T = QI
    	mac	SIN, a	; A = QR*cos+QI*sin = XR
    	mpy	COS, b	; B = QI*cos
    	ld	QR, T	; T = QR
    	sth	a, QR	; QR = a = XR
    	mas	SIN, b	; B = QI*cos-QR*sin = XI
    	sth	b, QI	; QI = b = XI
    	ld	PI, 15, a	; A = 1/2 PI
    	add	QI, 15, a	; A = 1/2 (PI+XI)
    	sth	a, PI	; PI = 1/2 new PI
    	sub	QI, 16, a	; A = 1/2 (PI-XI)
    	sth	a, QI	; QI = 1/2 new QI
    	ld	QR, 15, a	; A = 1/2 XR
    	add	PR, 15, a	; A = 1/2 (PR+XR)
    	sth	a, PR	; PR = 1/2 new PR
    	sub	QR, 16, a	; A = 1/2 (PR-XR)
    	sth	a, QR	; QR = 1/2 new QR

3.1.3. Вычисление «бабочки» для алгоритма БПФ с прореживанием по времени

С учетом раздельного выполнения операций над действительной и мнимой частями переменных P и Q алгоритм вычисления «бабочки» для БПФ с замещением и прореживанием по частоте может быть записан следующим образом:

Pm+1 = Pm + Qm ,
Qm+1 = (Pm – Qm)×WNk,
выразив который через действительные и мнимые составляющие получим
Pm+1 = PR + j×PI + QR + j×QI = [PR + QR] + j×[PI + QI];
Qm+1 = (PR + j×PI – QR – j×QI)×[cos(x) – j×sin(x)] =
= PR×cos(x) + j×PI×cos(x) – QR×cos(x) – j×QI×cos(x) –
– j×PR×sin(x) + PI×sin(x) + j×QR×sin(x) – QI×sin(x) =
= [(PR – QR)×cos(x) + (PI – QI)×sin(x)] + j×(PI –QI)×cos(x) – (PR – QR)×sin(x)].

При вычислении «бабочки» для исключения переполнения все выходные значения делятся на два.
Пример программы с прямой адресацией вычисления «бабочки» для алгоритма БПФ с замещением и прореживанием по частоте:

    * DIF FFT Programm for TMS320C5402 DSP Starter Kit
    * Direct Addressing	12/11/09 20:30:00
    	.data
    *	данные
    PR	.word	0h	; действительная часть P
    PI	.word	0h	; мнимая часть P
    QR	.word	0h	; действительная часть Q
    QI	.word	0h	; мнимая часть Q
    COS	.word	0h	; действительная часть W
    SIN	.word	0h	; мнимая часть W
    	.text
    *	инициализация
    INIT	ld	#PR, DP	; текущая страница данных
    	ssbx	sxm	; расширение знака
    	ssbx	frct	; умножение дробных чисел
    *	«бабочка»
    BTRFLY	ld	PR, 15, a	; A = 1/2 PR
    	add	QR, 15, a	; A = 1/2 (PR+QR)
    	sth	a, PR	; PR = 1/2 new PR
    	sub	QR, 16, a	; A = XR = 1/2 (PR-QR)
    	sth	a, QR	; QR = a = XR
    	ld	QI, 15, a	; A = 1/2 QI
    	add	PI, 15, a	; A = 1/2 (PI+QI)
    	sth	a, PI	; PI = 1/2 new PI
    	sub	QI, 16, a	; A = XI = 1/2 (PI-QI)
    	sth	a, QI	; QI = a = XI
    	ld	QR, T	; T = QR = 1/2 (PR-QR)
    	mpy	COS, a	; A = 1/2 (PR-QR)*cos
    	ld	QI, T	; T = QI = 1/2 (PI-QI)
    	mac	SIN, a	; A =1/2[(PR-QR)cos+(PI-QI)sin]
    	mpy	COS, b	; B = 1/2 (PI-QI)*cos
    	ld	QR, T	; T = QR = 1/2 (PR-QR)
    	sth	a, QR	; QR = 1/2 new QR
    	mas	SIN, b	; B =1/2[(PI-QI)cos-(PR-QR)sin]
    	sth	b, QI	; QI = 1/2 new QI

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