Научная литература
booksshare.net -> Добавить материал -> Физика -> Гольденберг Л.М. -> "Цифровая обработка сигналов: Справочник" -> 12

Цифровая обработка сигналов: Справочник - Гольденберг Л.М.

Гольденберг Л.М. Цифровая обработка сигналов: Справочник — М.: Радио и связь, 1985. — 312 c.
Скачать (прямая ссылка): cifrovayaobrabotkasignalov1985.djvu
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 97 >> Следующая

точечных круговых сверток. Пусть:
-у(0) -
У(4 7)
{/(2 7)
{/(3 7)
У(Т)
-УфТ)_
" * (0) х (4 7) х (2 7) х (4 7) х (2 7) х (0) х (2 7) х (0) х (4 7) х (3
7)"х (7)"'х'(5Т) х (7) х (5 7) х (3 7) _ х (5 7) х (3 7) х (7)
х (3 7) х (7) х (5 7) ~ х (7) х (5 7) х (3 7) х (5 7) х (3 7) х (7) х (0)
х(4 7) " х (2 7)
х (4 7) х (2 7) х (0) х (2 7) х (0) х (4 7) _
Y0 = [// (0), У (4 7), {/(2 7)]т 7)]т;
н0 = (ft(0),/1(2 7), й(4 7)]т; Hi = [/(3 7), /i(5
7),ft(7)]T;
х (0) х (4 7) Р '*(3 7) х (7) х (5 Т)'
х0= х (4 7) х (2 7) х (0) ;Х1 = х(7) х (5 7) х (3 7)
х (2 7) х (0) х(4 7Д + (5 7) х (3 7) х (7)
Тогда
Г Y0"j = ГХ0 ХЛ ГН"1
LvJ k х0] [hJ '
Используя алгоритм 2-точечной свертки (см. пример 1.17), иолучаем:
М2
Хр + Х! 2
Х0-Хг
(Но + Hj);
(Н0-Нх);
Y0 - Mj -j- М2 ; Yj - Mi-М2.
Для вычисления М и М2 применяется алгоритм 3-точечной свертки.
Пусть rti\ и т2 - числа требуемых умножений для Ns- и N-точечных сверток
соответственно [ (Л+ N2) = 1] • Аналогично at и Ог - числа требуемых
операций сложения. Тогда для Л'] ХЛ+точечной свертки число требуемых
операций умножения т и сложения о составит соответственно:
т ~т^тг\ а - о2 + тг аг.
(1.68)
(1.69)
Пример 1.19. Пусть /7=6; Д\=2; 7+=3. Согласно табл. 1.5 Ш]=2; т2=4; Ci=4;
02=11. Пользуясь формулами (1.68) и (1.69), получаем: т=2-4=8; о= =2-
11+4-4=38.
Теперь положим: /7j= 3; N2=2. Тогда: /и, =4; т2=2; "1=11; а2~4.
Аналогично находим: т=8; 0=3-4+2-11 = 12+22=34.
Расчеты показывают, что второй вариант является более экономичным по
числу требуемых операций сложения.
32
1.5. НЕКОТОРЫЕ ПЕРСПЕКТИВНЫЕ АЛГОРИТМЫ ВЫЧИСЛЕНИЯ ДПФ
1.5.1. Алгоритм Винограда
Алгоритм Винограда [1.12] основан на представлении матрицы N=NtX ХЛ'гХ
... XNV -точечного ДПФ, где все Nt - взаимно-простые числа, в виде
прямого произведения матриц Лд-точечных ДПФ
(r) ^Nt (r) ••• (r) (1-70)
и сведении вычисления ЛГг-точечных ДПФ к вычислению круговых сверток с
использованием модульной арифметики в кольце полиномов (см. 1.4.7).
Алгоритм Винограда, имеющий "гнездовую" структуру, существенно
эффективнее классических алгоритмов БПФ: при приблизительно равном числе
операций сложения он требует на 80% меньше операций умножения.
Вычисление ДПФ коротких последовательностей. При N=p, ра, 2", где р -
простое, нечетное число, а>1, ДПФ можно свести к вычислению круговых
сверток:
1. Пусть N=p. Тогда матрица ДПФ Wp | ь.пфо путем соответствующей
перестановки строк и столбцов может быть преобразована в циклическую
матрицу Wp-i размера (р-1)Х(р-1).. Взаимно-однозначное
соответствие между
показателями степени элементов Wip матрицы VVp_, и индексами элементов
циклической матрицы (1-43) задается так:
<7 = an(modp), /г=0 р-2, (1.71)
где а - первообразный корень числа р [1.12].
Пример 1.20. Пусть N=p=7. Первообразным корнем числа 7 является с=" =3.
Тогда соответствие (1.71) запишется так:
• п 0 1 2 3 4 5 q 1 3 2 6 4 5 ' а матрица Wr/fe, пфъ преобразуется к виду
w\ w\ w\ IF(r) Wj IF(r)
if(r) w\ if(r) Wj Wj w\
Wf w* w* w7 w\ IF(r)
if? w\ w\ wl IF(r) w7
wj IF? w\ w7 IFf IFf
wf w\ if(r) wl IF(r) Wj
Тогда искомое ДПФ примет вид:
Х(0)= J х(пТ)\
п- О
~X(l)-x(0)~ - -x(T) -
X (3) - x (0) *(3 T)
A (2)-x (0) x(2 T)
A (6)-x (0) ' W6 *(6 T)
A (4) - x (0) x(4 T)
_X(5)-x (0) _ -*(5 T)_
2-89 33
Выражение (1.72) представляет собой 6-точечную круговую свертку
последовательностей [№*7, Wh, Wh, W\ W4, WS] н [x{T), x(ST), x(4T),
x(6T), x(2T), x(57')], для вычисления которой с помощью полиномиальных
преобра-вований требуется восемь операций умножения и 34 - сложения (см.
табл. 1.5). Для вычисления всего ДПФ к этому числу операций добавляются
одна операция умножения на W0 и две операции сложения (см. табл. 1.6).
2. Пусть N=pu, а>1-целое. В этом случае вычисление ДПФ сводится к
вычислению двух р"-*-точечиых ДПФ и одной (р-l)p"-t-точечной круговой
свертки. Это эквивалентно одной (р-l)pa_I, двум (р-1)ра-2, четырем (р- -
1)ра_3, ...,2"-1(р-1)-точечным сверткам. Взаимно-однозиачное соответствие
между показателями степени элементов циклических матриц W(J,-i)P"-^
р
k = \.....а, и индексами элементов матрицы (1.43) задается равенством
QhlPk~l = о* (mod pa+X~k),
n = 0.....(p-l)p"-fe_l,
яде ah - первообразный корень числа ра+*-*.
¦Пример 1.21. Пусть N=З2. В этом случае первообразные корнч ai=a-2= =2.
Соответствие (1.73) для к-1,2 запишется так:
Пл 0 ] 2 3 4 5 n 0 1
Яг 1 2 4 8 7 5 Я2 3 6
>-точечная круговая свертка будет иметь вид
~ А-(1) ^ ~W\ wl wl *9 w79 w59~ x(T)
Х(2) W% К wl W% wl x(2 T)
Х(4) К Wl wl wl wl W2g x (4 T)
Х(8) W1 wl wl wl ^9 x (8 T)
Х(7) wl wl wl wl wl wl x (7 T)
-Х(5)_ _wl wl wl w* w\_ *(57)
Последовательности Х(Щ, /г=0, 1, 2 и X(k), k=0, ..., 8, вычисляются с
помощью
3-точечных ДПФ:
-*(0) + *(ЗГ) + *(6Г) 1 х(Т)+х(4Т)+х(7Т) ;
х(2Т) + х(5Т)+х (8Т) I
[X (0) i 'I 1
U(3) L 1 wl wl
Lx(6) 1 1 w% wl
-i
X(0) X(3) X (6)
?(1) x (4) - X(7)
-m -X (5)_ -X(8)
1 1
Предыдущая << 1 .. 6 7 8 9 10 11 < 12 > 13 14 15 16 17 18 .. 97 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed