Айфичер Э., Джервис Б. Цифровая обработка сигналов, практический подход (2-е изд., 2004) (1095888), страница 30
Текст из файла (страница 30)
Затем вычисляются Итз и две "'бабочки", содержащие этот коэффициент. Эта процедура выполняется для каждого из трех каскадов по очереди, при этом используются каскад 1 и переупорядоченные данные. Чтобы вычислить БПФ с помощью относительно короткой программы, алгоритм должен обладать рядом свойств. Пусть ширина "бабочки" ЕИ10ТН представляет расстояние в памяти между двумя точками, составляющими "бабочку".
Для нижней "бабочки" кас- 162 Глава 3. Дискретные преобразования када 3 это ВИ'з. Это равно расстоянию между четырьмя точками. Рассмотрев "бабочки" других каскадов, можно прийти к заключению, что в общем случае ВИг1РТН = 2~ ', (3.59) где  — номер этапа. ВИт1РТН вЂ” 1 — количество шагов, за которое изменяется показатель степени весового коэффициента. Пусть расстояние в памяти ВБЕР равно расстоянию в памяти между любыми точками ближайших "бабочек" данного каскада с одинаковым весовым коэффициентом. Для каскада 2 на рис. 3.5 ВЯз представляет собой ВЕЕР для "бабочек" с весовым юэффициентом И'о. Изучая рисунок, видим, что для каскада Я ВБЕР = 2з. (3.60) Наконец, для )т'-точечного БПФ показатели степени весовых коэффициентов изменя- ются на (3.61) Р = 1т'/2 для этапа Я.
Это видно из рис. 3.5. Например, на этапе 2 Я = 2, Р = 8/2з = 2, а весовые коэффициенты равны И'ее и И'ез. Каждую "бабочку" можно вычислить как ХМЕИт(ТОР) = ХОБР(ТОР) + И'", х ХОЙР(ВОТТОМ) (3.62) ХХЕИт(ВОТТОМ) = ХОЬР(ТОР) — Ит~л х ХОБР(ВОТТОМ), где левая сторона относится ю входу "'бабочки", а правая сторона — к выходу "бабочек*'. Кроме того, для экономии памяти зти уравнения можно переписать в виде ТЕМР = И'", х Х(ВОТТОМ) где Х(ВОТТОМ) означает выход ХОЕР(ВОТТОМ) "бабочки'* на предыдущем эта- пе, Х(ВОТТОМ) = Х(ТОР) — ТЕМР, (3.63, а) где Х(ВОТТОМ) теперь означает искомый выход "бабочки*', Х(ТОР) — предыдущее значение, а Х(ТОР) = Х(ТОР) + ТЕМР, (3.63, б) где значение Х(ТОР) в левой части — искомый выход "бабочки".
3.6. Обратное быстрое преобразование Фурьа Зная все это, можно записать псевдокод вычисления БПФ, как показано ниже. 10 Р1: 3.141593 20 00 РОН Я 1 ТО ш 30 ВЯЕР: 2"Я 40 Р: М/ВЯЕР 50 ВН10ТН: ВЯЕР/2 рассчитать для и каскадов расчет для каскада Я (Р М/2"Я), изменение показателя степени (ВН10ТН 2"(Я-1)), расстояние в памяти мехду входами "бабочек" бс 00 РОН Ю О ТО (ВН10ТН-1) расчет весовых коебйициентов для отдельного каскада Н: Р.У расчет показателя степени ММ ТНЕТА: 2*Р1"Н/М расчет степени е"(-т) ММ:-СИРЬХ(сое(ТНЕТА),-езл(ТНЕТА)) расчет (НМ)"К 00 РОН ТОРЧАЬ=Ю ВТЕР ВЯЕР питтс М/2 для всех з-х "бабочек" данного каскада 110 ВОТЧАЬ:=ТОРЧАЬ+ВМТОТН 120 ТЕИР: Х(ВОТЧАЬ)*ИМ 130 Х(ВОТЧА1): Х(ТОРЧАЬ)-ТЕИР 140 Х(ТОРЧАь)".=Х(ТОРЧАЬ)+ТЕИР 150 ЕМО 00 1бс ЕМО 00 170 ЕМО 00 В строках 100-150 рассчитываются все "бабочки" данного каскада с одинаковыми весовыми коэффициентами. Каскад всегда содержит )Ч/2 "бабочек".
:~;.":;3„6/б1;„.~р) Вычислительные преимущества БПФ Алгоритм БПФ для определения обратного быстрого преобразования Фурье можно лепю получить из алгоритма БПФ. Этот алгоритм нужен в основном для преобразования спектров в соответствующие им сигналы и для проверки правильности вычисления Вычислительные преимущества БПФ можно проиллюстрировать, рассмотрев вначале алгоритм БПФ на рис. 3.5. На этом рисунке показано, что )Ч-точечное БПФ содержит )т'/2 "бабочек" на каждом каскаде и 1окз )Ч каскадов, т.е.
всего в него входит ()Ч/2) 1ойз )Ч "бабочек". На рис. 3.4, а показано„что каждая "бабочка" содержит одну операцию комплексного умножения в виде Иг,тВХ„(к). Следовательно, БПФ содержит (АГ/2) !ояз )Ч операций комплексного умножения в отличие от № при ДПФ, как показано в разделе 3.4. Таким образом, вычислительная экономия при комплексном умножении составляет № — (Аг/2)!Ойз )Ч.
Каждая "бабочка" содержит две операции комплексного сложения, так что для БПФ необходимо А/1ойз )т' операций комплексного сложения в сравнении с )Ч()Ч вЂ” 1) операциями ДПФ. Следовательно, экономия при комплексном сложении составляет )Ч()Ч вЂ” 1) — Ж!Окз М.
Эта экономия проиллюстрирована в табл. 3.3. При обычном 1024-точечном ДПФ видно, что время, необходимое для вычислений, можно снизить на два порядка, если воспользоваться алгоритмом БПФ. 164 Глава 3. Дискретные преобразования Таблица 3.3. Экономия на операциях комплексного умножения н сложения при использовании БПФ вместо ДПФ ДПФ БПФ Отношение числа комплексного Отношение числа Число Число операций кап илексн ого Число Число операций операций операций операций умножения сложении операций комплексного умножения комплексного комплексного умножения при ДПФ и при БПФ комплексного сложения при ДПФ и ири БПФ сложения БПФ с помощью (как правило) того самого алгоритма.
Чтобы понять, как выводится ОБПФ, произведем такие замены в уравнении (3.20). Просуммируем по переменной Л, а не по п, переменную !с переименуем в !г, а П = 2я/)ЧУ, чтобы показатель экспоненты стал — й(2я/Ж)Л. Снова воспользуемся выражением х(ЛТ) = х(Л) и т.д. При этом уравнение (3.20) приобретет вид и-1 ХЫ = ',1,х(Л)е ндз'гн!' д=0,1,...,М вЂ” 1.
(3.64) Теперь сделаем аналогичную замену в уравнении (3.23), т.е. положим и = Л и и = !г. Уравнение (3.23) приобретет вид 1 н-1 Х(!г) = — Е х(Л)е*ч!з"~п!" !г = 0,1,...,)Ч вЂ” 1. гте (3.65) В двух последних уравнениях Х(р), Х(Л), х(!г) и х(Л) — элементы массивов Х и х одинаковой размерности, так что ОБПФ х(и) отличается от БПФ Х(и) только коэффициентом 1/!х' н знаком показателя степени экспоненты. Следовательно, для вычисления ОБПФ можно воспользоваться БПФ с небольшими изменениями. Эти два преобразования могут составлять один алгоритм, если в приведенный выше псевдокод внести следующие изменения: строка 5 К: 1 длн БПФ, К:=-1 длн ОБПФ строке 80 тиктв:-Кчг*91*КУБ строка 145 1Г К -1 00 2 4 8 1б 32 64 128 256 512 1024 2048 4096 8192 !6 64 256 1024 4096 16 384 65 536 262 144 1 048 576 4 194 304 16 777 216 67 108 864 2 12 56 240 992 4032 16 256 65 280 261 632 1 047 552 4 192 256 1б 773 120 67 100 672 1 4 12 32 80 192 448 1024 2304 5120 !1 264 24 576 53 248 2 8 24 64 160 384 896 2048 4608 10 240 22 528 49 152 106 496 4 4 5,3 8,0 12,8 21,3 36,6 64,0 113,8 204,8 372,4 682,7 1 260,3 1 1,5 2,3 3,75 6,2 10,5 !8,1 31,9 56,8 102,3 186,1 341,3 630,0 3.7.
Реализация БПФ Х(ВОТЧА1 ): Х(ВОТЧА1 )/М Х(ТОРЧА1): Х(ТОРЧАЬ)УМ ЕМО 00 строка 146 строка 147 строка 148 Теперь очевидно, что, в принципе, для вычисления БПФ и ОБПФ создается массив данных и с этими данными выполняются действия, определяемые алгоритмами БПФ н ОБПФ (в том числе и алгоритмом обращения битов). Однако остается еще несколько моментов, которые следует обсудить. До сих пор мы пренебрегали эффектами нарушения непрерывности, которые встречаются на краях последовательности данных, а также такими явлениями, которые называют налоэ»гелием и "частоколом".
Чтобы хорошо оценить реальный спектр данных, необходимо учитывать эти эффекты, пользуясь методами, описанными в главе 1!. Еше один аспект — до сих пор внимание в данной главе уделялось двоичному алгоритму временной децимации, но существуют и другие алгоритмы, в том числе и алгоритм частотной децимации (ЧД). Некоторые из этих пунктов будут обсуждаться далее. ';:3;7.)(" »' БПФ с частотной децимацией ' 3'.7,2..1 Сравнение алгоритмов ВД и ЧД В алгоритме ВД порядок входных данных остается неизменным, но порядок выходной последовательности БПФ определяется обращенным порядком битов. Оба алгоритма (ВД и ЧД) плоские. При повторном их применении можно сохранить порядок как входных, так и выходных данных, но суммарные алгоритмы уже не будут плоскими, и для их выполнения нужна дополнительная память (см.
главу 12). Количество операций комплексного умножения, необходимых для выполнения калщого алгоритма, одинаково, В целом, разница между ними небольшая. В разделе 3.5 описан алгоритм быстрого преобразования Фурье с временной децимацией, который заключался в многократном делении исходного дискретного преобраювания Фурье в виде уравнения (3.43) на два преобразования, одно из которых состоит из четных членов, а другое — из нечетных, до тех пор, пока исходное преобразование не будет разложено на двухточечные преобразования исходных данных.
Альтернативный подход состоит в разделении исходного преобразования на два, одно из которых содержит первую половину данных, а другое — вторую. Получающийся в результате алгоритм частотной децимации впервые был предложен в работе [121, хотя почему-то его часто называют алгоритмом Сэнда — Тычки. 166 Глава 3. Дискретные преобразования ::3.7,3;'-: Модификации для увеличения скорости Несколько модернезировав алгоритм ВД, можно еще больше увеличить скорость вычислений. Например, для снижения количества операций комплексного умножения почти в два раза можно воспользоваться не БПФ по основанию 2, а БПФ по основанию 4. Количество операций сложения при этом также уменьшается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
