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

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

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

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

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

3.2. Частные случаи реализация базовой операции БПФ
3.2.1. Реализация базовой операции для специальных значений поворачивающих множителей

Воспользовавшись свойством симметрии поворачивающих множителей можно значительно упростить вычисление «бабочки».
Для алгоритма БПФ с прореживанием по времени и WN0 = 1 (cos=1, sin=0) получим

Pm+1 = [PR + QR] + j×[PI + QI],
Qm+1 = [PR – QR] + j×[PI – QI].
Программа вычисления «бабочки» при этом значительно сокращается (в 2 раза):

    BTRFLY
    	ld	PR, 15, a		; A = 1/2 QR
    	add	QR, 15, a		; A = 1/2 (PR+QR)
    	sth	a, PR			; = 1/2 PR
    	sub	QR, 16, a		; A = 1/2 (PR-QR)
    	sth	a, QR			; = 1/2 QR
    	ld	QI, 15, a		; A = 1/2 QI
    	add	PI, 15, a		; A = 1/2 (PI+QI)
    	sth	a, PI			; = 1/2 PI
    	sub	QI, 16, a		; A = 1/2 (PI-QI)
    	sth	a, QI			; = 1/2 QI

Для алгоритма БПФ с прореживанием по частоте и WN0 = 1 (cos=1, sin=0) получим

Pm+1 = [PR + QR] + j×[PI + QI],
Qm+1 = [PR – QR] + j×[PI – QI].
И программа вычисления «бабочки» полностью совпадает с программой для алгоритма с прореживанием по времени.

Для алгоритма БПФ с прореживанием по времени и WNN/4 = –j (cos=0, sin=1) получим

Pm+1 = [PR + QI] + j×[PI – QR],
Qm+1 = [PR – QI] + j×[PI + QR].
Программа вычисления «бабочки» при этом выглядит следующим образом:

    BTRFLY
    	ld	PI, 15, a		; A = 1/2 PI
    	sub	QR, 15, a		; A = 1/2 (PI-QR)
    	sth	a, PI			; = 1/2 PI
    	add	QR, 16, a		; A = 1/2 (PI+QR)
    	ld	PR, 15, b		; B = 1/2 PR
    	add	QI, 15, b		; B = 1/2 (PR+QI)
    	sth	b, PR			; = 1/2 PR
    	sub	QI, 16, b		; B = 1/2 (PR-QI)
    	sth	b, QR			; = 1/2 QR
    	sth	a, QI			; = 1/2 QI

Для алгоритма БПФ с прореживанием по частоте и WNN/4 = –j (cos=0, sin=1) получим

Pm+1 = [PR + QR] + j×[PI + QI],
Qm+1 = [PI – QI] + j×[PR – QR].
Программа вычисления «бабочки» при этом выглядит следующим образом:

    BTRFLY
    	ld	PI, 15, a		; A = 1/2 PI
    	add	QI, 15, a		; A = 1/2 (PI+QI)
    	sth	a, PI			; = 1/2 PI
    	sub	QI, 16, a		; A = 1/2 (PI-QI)
    	ld	QR, 15, b		; B = 1/2 QR
    	sub	PR, 15, b		; B = 1/2 (QR-PR)
    	sth	b, QI			; = 1/2 QI
    	add	PR, 16, b		; B = 1/2 (PR+QR)
    	sth	b, PR			; = 1/2 PR
    	sth	a, QR			; = 1/2 QR

Для БПФ с прореживанием по времени и WNN/8 = 0.7–j0.7 (cos=sin=W=0.7) получим

Pm+1 = [PR + (QI + QR)×W] + j×[PI + (QI – QR)×W],
Qm+1 = [PR – (QI + QR)×W] + j×[PI – (QI – QR)×W].

Для БПФ с прореживанием по частоте и WNN/8 = 0.7–j0.7 (cos=sin=W=0.7) получим

Pm+1 = [PR + QR] + j×[PI +QI],
Qm+1 = [(PI – QI)×W + (PR – QR)×W] + j×[(PI –QI)×W – (PR – QR)×W].

Для БПФ с прореживанием по времени и WN3N/8 = –0.7–j0.7 (–cos=sin=W=0.7) получим

Pm+1 = [PR + (QI – QR)×W] + j×[PI – (QI + QR)×W],
Qm+1 = [PR – (QI – QR)×W] + j×[PI + (QI + QR)×W].

Для БПФ с прореживанием по частоте и WN3N/8 = –0.7–j0.7 (–cos=sin=W=0.7) получим

Pm+1 = [PR + QR] + j×[PI +QI],
Qm+1 = [(QR – PR)×W – (QI – PI)×W] + j×[(QR – PR)×W + (QI –PI)×W].
Программа вычисления «бабочки» при этом сокращается незначительно.

3.2.2. Программная реализация двоично-инверсного счетчика

Для вычисления БПФ требуется наличие двоично-инверсного счетчика. В процессорах TMS второго поколения начиная с TMS320C25 для этого был введен новый способ адресации BR0+ (с обратным переносом). Для чисел из диапазона от 0 до 7 двоично-инверсный счетчик можно представить в виде следующей таблицы:

| Номер | Двоичное представление | Двоичная инверсия | Двоично-инверсный номер
| 0 | 000 | 000 | 0
| 1 | 001 | 100 | 4
| 2 | 010 | 010 | 2
| 3 | 011 | 110 | 6
| 4 | 100 | 001 | 1
| 5 | 101 | 101 | 5
| 6 | 110 | 011 | 3
| 7 | 111 | 111 | 7

Для организации двоично-инверсного счетчика при отсутствии соответствующего способа адресации можно использовать различные алгоритмы. Одним из таких алгоритмов является алгоритм, предложенный Рэйдером (рис. 3.6):

###

### Рисунок 3.6 – Алгоритм Рейдера

3.2.3. Двоично-инверсная перестановка данных

При вводе данных в двоично-инверсном порядке можно просто воспользоваться данным счетчиком для адресации памяти данных, куда помещается информация, считанная из порта.
При перестановке результата вычисления можно воспользоваться промежуточным буфером и считывать данные с помощью обычного счетчика, а записывать в буфер с помощью двоично-инверсного или наоборот.
Второй способ заключается в по парной перестановке соответствующих отсчетов сигнала. Для 16 отсчетов необходимы следующие перестановки (рис. 3.7):

###

### Рисунок 3.7 – Двоично-инверсная перестановка данных

Элементы с одинаковыми номерами переставлять нет необходимости, а первыми необходимо поменять местами элементы 1–8. При этом, когда мы дойдем до 8-го элемента в первой строке, то окажется что элементы 8–1 уже были переставлены ранее и их переставлять также нет необходимости.
Таким образом перестановка выполняется только для элементов номер (адрес) источника которых меньше номера (адреса) приемника.
Из проверки всегда можно исключить первый (0…0) и последний (1…1) элементы.
Таким образом получается, что нужно переставить следующие элементы:
1-8, 2-4, 3-12, 5-10, 7-14, 11-13.
Как видим, последняя пара относится ко второй половине массива элементов.
Для того чтобы переставить пару элементов совсем не обязательно пользоваться рабочими ячейками. Для этого можно использовать 32-разрядный аккумулятор загрузив первый элемент в старшую, а второй в младшую часть аккумулятора (или наоборот). После чего записать содержимое аккумулятора в обратном порядке – младшую часть на место первого элемента и старшую – на место второго элемента.
При наличии двух аккумуляторов можно легко переставлять комплексные числа (по два 16-разрядных слова).
Чтобы загрузить в аккумулятор два числа можно использовать команды LD со сдвигом на 16 и OR, XOR, ADDS или LDU и ADD со сдвигом на 16. Сохранение переставленных данных выполняется обычными командами STL и STH. Можно также использовать два аккумулятора и обмениваться сразу двойными словами (действительной и мнимой частями) используя команды DLD и DST.

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