Алгоритм БПФ с прореживанием по времени

Чтобы достичь существенного улучшения эффективности необходимо разложить вычисления ДПФ на набор ДПФ меньшего порядка. Алгоритмы, в которых это разложение основано на разложении последовательности на меньшие подпоследовательности, называются алгоритмами с прореживанием по времени.

Рассмотрим частный случай . , . Разделим на четные и нечетные точки: , или, заменяя индексы суммирования на при четном n и при нечетном, получим = , т.к. , то

= (1.54)

 

Каждая из сумм является N/2 точечным ДПФ. Первая сумма N/2 точечное ДПФ четных точек исходных последовательностей, а вторая – N/2 точечное ДПФ нечетных точек исходных последовательностей. Хотя индекс k простирается на N значений, k=0,1,…,N-1, каждая из сумм требует вычислений только для k от 0 до N/2-1, т.к. G(k) и H(k) периодичны по k с периодом N/2.

После того, как ДПФ, соответствующие двум суммам в (1.54), вычислены, они объединяются и дают N-точечное ДПФ .

 
 

Рис. 1.4. Разложение 8-точечного ДПФ

 

 

 
 

Рис. 1.5.
 
 

Разложение 4-точечного ДПФ.

 

Рис. 1.6. 2-х точечное ДПФ.

 

Проведя разложение максимально возможное число раз, получим общее число комплексных умножений и сложений, равное .








Дата добавления: 2017-08-01; просмотров: 618;


Поиск по сайту:

При помощи поиска вы сможете найти нужную вам информацию.

Поделитесь с друзьями:

Если вам перенёс пользу информационный материал, или помог в учебе – поделитесь этим сайтом с друзьями и знакомыми.
helpiks.org - Хелпикс.Орг - 2014-2024 год. Материал сайта представляется для ознакомительного и учебного использования. | Поддержка
Генерация страницы за: 0.003 сек.