Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Наброски и зарисовки растений, плодов, цветов: Освоить конструктивное построение структуры дерева через зарисовки отдельных деревьев, группы деревьев...
Топ:
Генеалогическое древо Султанов Османской империи: Османские правители, вначале, будучи еще бейлербеями Анатолии, женились на дочерях византийских императоров...
Комплексной системы оценки состояния охраны труда на производственном объекте (КСОТ-П): Цели и задачи Комплексной системы оценки состояния охраны труда и определению факторов рисков по охране труда...
Устройство и оснащение процедурного кабинета: Решающая роль в обеспечении правильного лечения пациентов отводится процедурной медсестре...
Интересное:
Берегоукрепление оползневых склонов: На прибрежных склонах основной причиной развития оползневых процессов является подмыв водами рек естественных склонов...
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Как мы говорим и как мы слушаем: общение можно сравнить с огромным зонтиком, под которым скрыто все...
Дисциплины:
2017-09-10 | 249 |
5.00
из
|
Заказать работу |
|
|
Основная идея алгоритма БПФ с прореживанием по времени заключается в поэтапном вычислении ДПФ на этапах, при этом на каждом последующем этапе ДПФ определяется через ДПФ вдвое меньшей размерности.
Пусть - четное число. Выделим в исходном ДПФ два слагаемых, соответствующих элементам исходной последовательности с четными и нечетными номерами:
. (2.1)
Введем обозначения и и вынесем из второй суммы множитель . В этом случае можно записать:
. (2.2)
В последнем выражении две суммы представляют собой ДПФ последовательностей и , причем каждое из ДПФ имеет размерность . Следовательно, можно записать:
, (2.3)
где - ДПФ последовательности отсчетов с четными номерами;
- ДПФ последовательности отсчетов с нечетными номерами.
Так как ДПФ размерностью дает лишь спектральных коэффициентов, то непосредственно использовать выражение (2.3) можно только при . Однако для остальных индексов можно воспользоваться периодичностью спектра дискретного сигнала:
,
.
Соответственно, для аргументов выражение (2.3) примет вид:
, . (2.4)
Процесс вычисления 8-точечного ДПФ путем его разбиения на два 4-точечных ДПФ иллюстрируется рисунком 2.1.
Рисунок 2.1 – вычисление 8-точечного ДПФ с использованием двух 4-х точечных ДПФ
Объединение результатов двух ДПФ реализуется с помощью 4-х дополнительных блоков. Каждый из блоков имеет два входных и два выходных сигнала. Один из входных сигналов умножается на комплексную экспоненту , после чего суммируется со вторым сигналом и вычитается из него, формируя два выходных сигнала. Это соответствует реализации формул (2.2) и (2.3). Данная операция получила название «бабочки». Структура бабочки представлена на рисунке 2.2.
|
Рисунок 2.2 – условное обозначение «бабочки» и ее структурная схема при прореживании по времени
Определим количество операций на выполнение ДПФ рассмотренным способом. Каждое из двух ДПФ половинной размерности требует арифметических операций. Кроме того, при вычислении окончательных результатов каждый спектральный коэффициент умножается на комплексный весовой множитель. Это добавляет операций умножения. В результате имеется
арифметических операций, что почти в 2 раза меньше, чем при вычислении ДПФ прямым способом.
Наибольшая степень ускорения вычислений может быть достигнута при продолжении деления последовательностей на две части до тех пор, пока не получатся двухэлементные последовательности. ДПФ двухэлементных последовательностей рассчитывается вообще без использования операции умножения за счет вычисления суммы и разности двух отсчетов:
,
.
Любой из алгоритмов БПФ выполняется за следующее число этапов: . Количество «бабочек», выполняемых на каждом этапе, одинаково и равно . Результирующее число требуемых при этом пар операций «умножение-сложение» можно оценить как
.
Таким образом, снижение вычислительных затрат по сравнению с использованием ДПФ составляет раз. Например, при достигается ускорение вычислений в 102.4 раза.
Экономия вычислительных затрат достигается за счет:
- объединения всех слагаемых, умножаемых на одинаковые множители;
- трансформации некоторых множителей в 1 или -1.
|
|
Семя – орган полового размножения и расселения растений: наружи у семян имеется плотный покров – кожура...
Папиллярные узоры пальцев рук - маркер спортивных способностей: дерматоглифические признаки формируются на 3-5 месяце беременности, не изменяются в течение жизни...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Индивидуальные очистные сооружения: К классу индивидуальных очистных сооружений относят сооружения, пропускная способность которых...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!