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

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

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

отличие от алгоритма с прореживанием по времени, в двоично-инверсионном
порядке располагается не входная, а выходная последовательность X(k).
(1.27)
Рис. 1.8 16
\ Пример 1.7. Рассмотрим случай N-8, v=3. Направленный граф 8-точечного,
ДПФ с использованием операции "бабочка" и выражения (1.26) изображен на',
рис. 1.8.
Алгоритмы с прореживанием по времени и по частоте являются дуальными:
каждый из них может быть получен из другого путем взаимной замены входа и
выхода и обращения направления всех стрелок в направленном графе (см.
рис. 1.6 и 1.8).
ФОРТРАН - программа, реализующая алгоритм БПФ с основанием 2 при
прореживании по времени, приведена в [1.6]. В пакете прикладных программ
ЕС ЭВМ имеется подпрограмма FFTCO, которая также реализует алгоритм БПФ.
1.3.5. Алгоритмы БПФ для произвольного составного N
Алгоритм с множителями поворота. Пусть N-NiN2, где Ni и Nz -
любые
положительные целые. В этом случае вычисление А-точечного ДПФ
можно
свести к определению Ni ЛГ-г-точечных и N2 Ni -точечных ДПФ и N
умножениям .
9 иа множители поворота ми- Для этого в (1.19) необходимо сделать следую-
W, щую подстановку:
k = ki k2 Nz, и п 1 -{- п2 N1, (1.28)
где пг, k2=> 0,..., Ni-1, n2,ki = 0............. N2-1.
Тогда (1.19) преобразуется к виду
X (кг + К V2) = §' \( N^x ((пг + п2 Мх) Г*) I
",=° П'=° (1.29)
Пример 1.8. Пусть N-6; N4=3; Л'г=2. Согласно (1.28) положим k-k,+ -F&2-2;
n=ni+n2-3; Пг, ^=0, 1, 2; nz, &i=iO, 1. Тогда
X (fei + fea-2) [( 2 х (К+ 3"2) Т) Wl' "Л Г**
"1=0 L \п"=о /
Соответствующий направленный граф изображен на рис. 1.9.
П7&1 "1 w3
-точечное йПФ
к,-О п,=0
=Х(3)
Рис. 1.9
Алгоритмы БПФ с произвольным основанием. Используя алгоритм с множителями
поворота, можно получить алгоритмы БПФ с основаниями, отличными от 2. На
практике наибольшее применение нашли алгоритмы с основаниями 4, 8 и 16,
позволяющие значительно сократить число требуемых операций по сравнению с
алгоритмами с основанием 2. В табл. 1.3 приведены выражения для
п
Таблица 1
Алгоритм Действие Число действительных умножений Число
действительных сложений
С основанием 2 N=2V v>-l, целое Вычисление (N/2)v 2-точечных ДПФ
Поворот Полное преобразование 0 (2v-4)lV+4 (2v-4)JV+4 2Nv (v-
2)N+2 (3v-2 )N+2
С основанием 4 JV=(22)v/2 v/2"l, целое Вычисление (JV/4)v/2 4-точечных
ДПФ Поворот Полное преобразование 0 (3v/2-4)ЛГ+4 (3v/2-4)N+4 2Nv (3v/4-
2)N+2 (275v-2)N+2
С основанием 8 N= (23)v/3 v/3"l, целое Вычисление (JV/8)v/3 8-точечных
ДПФ Поворот Полное преобразование Nvl 6 (7v/6-4)N+4 (4v/3-4)/V+4
l3Nv/6 (7v/12-2)N+2 (2,75v-2)N+2 . 371Vv/16 (15v/32-2)N+2 (89v/32-
2)N+2
С основанием 16 N= (2')v/4 v/4>l, целое Вычисление (W/16)v/4 16-точечных
ДПФ Поворот Полное преобразование 5Nv/8 (15v/16-4)W+4 (25v/16-4)N+4
расчета числа требуемых арифметических операций для алгоритмов с
основаниями 2, 4, 8 и 16. Предполагается, что для выполнения базовой
операции (2, 4, 8 или 16-точечного ДПФ) используется алгоритм, требующий
минимального числа умножений и сложений.
Пример 1J9. Построить алгоритм 16-точечного ДПФ с основанием 4. Положим
N= 16=1V 1JV2, где N±=4; N2=4. Согласно (1.28) и (1.29) k=ki+k2-4;
п=П1+п2-4; ni, m, kly k2=0, ..., 3;
2 * (("1 + я2-4) Г) Wk4' Пг\ и']
п,=0 / J
л,=0 .
Построим алгоритм вычисления базового 4-точечного ДПФ
3
Х(к) = ^х(пТ)№*, k = Q,..., 3. п=О
. Положим
fe = *i + *2-2; п = к1 + п2*2; klt k2, nly na - 0,1. Подставляя (1.32) в
(1.31), получаем
(1.30)
(1.31)
(1.32)
(1.33)
X(k1 + k2-2)=j] [(j * (("! + ",-2) T)U7^') W*' n>
"1=0 L N".=0 /
Направленный граф, соответствующий (1.33), изображен на рис. 1.10. Направ
ленный граф 16-точечного ДПФ изображен на рис. 1.11.
18
\ Алгоритм взаимно-простых делителей. Пусть N=NiN2, где Ni и N2- взаимно-
простые, т. е. (Л4Л/2)*=1, а однозначное отображение между числами п=
=0-1; k==0,...,N- 1 и парами (нь п2), (fti, k2); пи ft,=0 Ni = 1,
п2, k2=0,..., N2-1 определяется соотношениями:
п - ni N2 + п2; k = k1Ni-{-k2. (1.34)
Рис. 1.10
Пусть последовательность х(пТ) получается из последовательности х{пТ)
перестановкой**
*(("!N2 + п2) Т) = х((п2+ niN2) (modN) Т), (1.35)
а последовательность X (k) получается из последовательности ДПФ X(k)
перестановкой
X (k1 N2 + ft2) == X ((sx k2 + s2 k2 N2) (mod N)). (1.36)
Числа Si и s2 определяются согласно китайской теореме об остатках .12] из
уравнений:
s1N1\ 1 (mod Na), s1<N2, (1.37)
s2JV2s 1 (mod A^), s2<N1. (1.38)
xW)
x(T)
xiIT)
X(3T)
x(W
x@T)
x(6T)
xUT)
xtgT)
X(9T)
xWT)
X(UT)
X(12T)
ХШ)
X(W)
X (1ST)
Puc. 1.11
* Запись {Nu N2) означает; "наибольший общий делитель чисел Nt
и N2".
** Запись n(mod/n) означает "остаток от деления числа п на число ш",
например 21 (mod 5) = 1.
19
Тогда справедливо выражение
Nt-1 /N,-1 \
*(*!*, + *,) = V S * (("1^2 + я2) Л *%**. (1-39)
"1=0 \ п2=0 /
Алгоритм взаимно простых делителей позволяет избавиться от хмножителей
по-ворота и свести вычисление Лг=Лг1Аг2-точечного ДПФ к вычислению Ni- и
Лг2-точечных ДПФ и является по существу методом отображения одномерного
Предыдущая << 1 .. 2 3 4 5 6 < 7 > 8 9 10 11 12 13 .. 97 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

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

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed