Быстрая свертка на основе БПФ

Рассмотрены практические вопросы использования быстрого преобразования Фурье комплексных сигналов длины N для повышения эффективности вычислений дискретной свертки за счет одновременной обработки двух действительных последовательностей каждая длины N. Представлены условия выбора минимального периода...

Повний опис

Збережено в:

Бібліографічні деталі
Дата:	2005
Автори:	Синьков, М.В., Закидальский, А.И., Цыбульская, Е.А.
Формат:	Стаття
Мова:	Russian
Опубліковано:	Інститут проблем реєстрації інформації НАН України 2005
Назва видання:	Реєстрація, зберігання і обробка даних
Теми:	Математичні методи обробки даних
Онлайн доступ:	https://nasplib.isofts.kiev.ua/handle/123456789/50778
Теги:	Додати тег Немає тегів, Будьте першим, хто поставить тег для цього запису!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Цитувати:	Быстрая свертка на основе БПФ / М.В. Синьков, А.И. Закидальский, Е.А. Цыбульская // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 3. — С. 62-70. — Бібліогр.: 4 назв. — pос.

Репозитарії

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	nasplib_isofts_kiev_ua-123456789-50778
record_format	dspace
spelling	nasplib_isofts_kiev_ua-123456789-507782025-02-09T14:50:42Z Быстрая свертка на основе БПФ Швидка згортка на основі ШПФ Fast Convolution on the Basis of the FFT Синьков, М.В. Закидальский, А.И. Цыбульская, Е.А. Математичні методи обробки даних Рассмотрены практические вопросы использования быстрого преобразования Фурье комплексных сигналов длины N для повышения эффективности вычислений дискретной свертки за счет одновременной обработки двух действительных последовательностей каждая длины N. Представлены условия выбора минимального периода для кольцевой свертки, и приведена оценка погрешности вычисления свертки из-за сокращения длины ядра. Оценена сложность реализации свертки в элементарных операциях. Показаны преимущества вычисления длинных сверток в частотной области. Розглянуто практичні питання використання швидкого перетворення Фур’е комплексних сигналів довжини N для підвищення ефективності обчислення дискретної згортки за рахунок одночасної обробки двох дійсних послідовностей довжини N кожна. Надано умови вибору мінімального періоду для кільцевої згортки та приведено оцінку похибки обчислення згортки завдяки скороченню довжини ядра. Оцінено складність реалізації згортки в елементарних операціях. Показано переваги обчислення довгих згорток у частотній області. The practical questions on using the fast Fourier transform of N-length complex signals for increasing efficiency of calculations of discrete convolution at the expense of simultaneous processing of two valid sequences each of N-length are considered. The conditions of choosing a minimum period for ring convolution are given and the estimation of convolution’s error of calculation through reducing the length of a core is presented. The complexity of convolution’s realization in elementary operations is estimated. The advantages of calculation of long convolutions in frequency area are shown. 2005 Article Быстрая свертка на основе БПФ / М.В. Синьков, А.И. Закидальский, Е.А. Цыбульская // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 3. — С. 62-70. — Бібліогр.: 4 назв. — pос. 1560-9189 https://nasplib.isofts.kiev.ua/handle/123456789/50778 620.179.15:681.3.06 ru Реєстрація, зберігання і обробка даних application/pdf Інститут проблем реєстрації інформації НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	Russian
topic	Математичні методи обробки даних Математичні методи обробки даних
spellingShingle	Математичні методи обробки даних Математичні методи обробки даних Синьков, М.В. Закидальский, А.И. Цыбульская, Е.А. Быстрая свертка на основе БПФ Реєстрація, зберігання і обробка даних
description	Рассмотрены практические вопросы использования быстрого преобразования Фурье комплексных сигналов длины N для повышения эффективности вычислений дискретной свертки за счет одновременной обработки двух действительных последовательностей каждая длины N. Представлены условия выбора минимального периода для кольцевой свертки, и приведена оценка погрешности вычисления свертки из-за сокращения длины ядра. Оценена сложность реализации свертки в элементарных операциях. Показаны преимущества вычисления длинных сверток в частотной области.
format	Article
author	Синьков, М.В. Закидальский, А.И. Цыбульская, Е.А.
author_facet	Синьков, М.В. Закидальский, А.И. Цыбульская, Е.А.
author_sort	Синьков, М.В.
title	Быстрая свертка на основе БПФ
title_short	Быстрая свертка на основе БПФ
title_full	Быстрая свертка на основе БПФ
title_fullStr	Быстрая свертка на основе БПФ
title_full_unstemmed	Быстрая свертка на основе БПФ
title_sort	быстрая свертка на основе бпф
publisher	Інститут проблем реєстрації інформації НАН України
publishDate	2005
topic_facet	Математичні методи обробки даних
url	https://nasplib.isofts.kiev.ua/handle/123456789/50778
citation_txt	Быстрая свертка на основе БПФ / М.В. Синьков, А.И. Закидальский, Е.А. Цыбульская // Реєстрація, зберігання і оброб. даних. — 2005. — Т. 7, № 3. — С. 62-70. — Бібліогр.: 4 назв. — pос.
series	Реєстрація, зберігання і обробка даних
work_keys_str_mv	AT sinʹkovmv bystraâsvertkanaosnovebpf AT zakidalʹskijai bystraâsvertkanaosnovebpf AT cybulʹskaâea bystraâsvertkanaosnovebpf AT sinʹkovmv švidkazgortkanaosnovíšpf AT zakidalʹskijai švidkazgortkanaosnovíšpf AT cybulʹskaâea švidkazgortkanaosnovíšpf AT sinʹkovmv fastconvolutiononthebasisofthefft AT zakidalʹskijai fastconvolutiononthebasisofthefft AT cybulʹskaâea fastconvolutiononthebasisofthefft
first_indexed	2025-11-27T01:09:12Z
last_indexed	2025-11-27T01:09:12Z
_version_	1849903815732494336
fulltext	62 УДК 620.179.15:004.421.2 М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская Институт проблем регистрации информации НАН Украины ул. Н. Шпака, 2, 03113 Киев, Украина Быстрая свертка на основе БПФ Рассмотрены практические вопросы использования быстрого преоб- разования Фурье комплексных сигналов длины N для повышения эф- фективности вычислений дискретной свертки за счет одновременной обработки двух действительных последовательностей каждая длины N. Представлены условия выбора минимального периода для кольцевой свертки, и приведена оценка погрешности вычисления свертки из-за сокращения длины ядра. Оценена сложность реализации свертки в элементарных операциях. Показаны преимущества вычисления длин- ных сверток в частотной области. Ключевые слова: быстрая свертка, быстрое преобразование Фурье, томографическая реконструкция. Процесс томографической реконструкции объекта по его проекциям связан с большим объемом вычислений, среди которых свертка занимает заметное место. Оптимизация вычислений свертки важна как для томографической реконструк- ции, так и практически для любой области цифровой обработки сигналов [1]. Рассмотрим случай одномерной свертки сигнала (исходной проекции) с со- ответствующим ядром. В терминах линейных систем ядро представляет собой импульсный отклик системы на d-функцию и характеризует ее динамические свойства. Ядро свертки — функция с четной симметрией. Пусть сигнал представляет собой входную последовательность длиной N1 отсчетов. Ядро содержит нечетное число отсчетов N2. При обработке входной последовательности длиной N1 отсчетов число отсчетов полного ядра равно ве- личине N2 = 2N1 – 1. При апериодической свертке [1] двух конечных последова- тельностей длиной N1 и N2 отличных от нуля отсчетов свертки будет не более M = N1 + N2 – 1 = 3N1 – 2. (1) Апериодическая свертка может быть заменена периодической (круговой или циклической), если период повторения сигнала будет, по крайней мере, столь же © М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская Быстрая свертка на основе БПФ ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 3 63 большим как длина отсчетов результата свертки (3N1 – 2). При таких условиях не происходит никакого наложения сигналов, что облегчает реализацию качествен- ной интерполяции. На практике требуемое число отсчетов результатов свертки обычно равно длине входной последовательности N1. Это позволяет несколько сократить минимальный период круговой свертки. Проведенный анализ показал, что при четной симметрии ядра и нечетном числе его членов величина M может быть выбрана из менее жесткого условия: M ³ N1 + (N2 – 1)/2 = < 2N1 – 1. (2) При этом возникает некоторое наложение на отдельных участках результа- тов свертки. Тем не менее, интересующий участок круговой свертки длиной N1 остается без влияния наложений и содержит правильные результаты. Это важно, потому что мы можем примерно в 1,5 раза сократить минимальный период кру- говой свертки, получая при этом правильный результат для N1 интересующих значений апериодической свертки. Для сверток с коротким ядром N2 < 2N1 – 1 могут возникнуть проблемы с использованием интерполяции с ограниченным спектром (например, sinc- интерпо-ляции). Дело в том, что ход полученной после такой интерполяции плавной кривой, проходящей через все интересующие точки N1, будет также за- висеть и от остальных M – N1 точек, претерпевших искажения от наложения сиг- налов из-за сокращения периода круговой свертки. Известно, что трудоемкая операция дискретной свертки во «временной» об- ласти (области сигнала) эквивалентна в частотной области простому умножению одноименных гармоник спектров сигнала и ядра. Однако при этом необходимо дополнительно выполнить переход из области сигналов в область спектров и, по- сле умножения одноименных гармоник спектров, дополнительно сделать обрат- ный переход в область сигналов. Переход из временной области в частотную и обратно требует прямого дискретного преобразования Фурье (ДПФ) входных по- следовательностей по M отсчетов, умножения одноименных гармоник спектра с последующим обратным преобразованием результатов их произведения во вре- менную область с помощью обратного ДПФ (ОДПФ). Теоретические основы вы- числения свертки в частотной области известны весьма давно. Прошло почти два столетия с тех пор, как Жан Батист Жозеф Фурье (1807 г.) представил доклад о возможности представления непрерывного периодического сигнала в виде сум- мы синусоид. Наряду с преобразованием непрерывных сигналов (как периодических, так и непериодических), в цифровой обработке сигналов самое широкое распростране- ние получило дискретное преобразование Фурье. Трудно даже перечислить об- ласти применения ДПФ. Назовем только несколько примеров — это цифровой спектральный анализ, проектирование фильтров и многое другое. Практическое применение вычисления свертки с переходом в область спек- тров имеет смысл только при условии применения эффективных методов ДПФ и ОДПФ. В этом плане особого внимания заслуживает быстрое преобразование Фурье (БПФ), представляющее собой частный случай ДПФ при числе отсчетов М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская 64 N = pq, где p и q — целые числа. В настоящее время, с полным на то основанием, БПФ связывают с именем Кули и Тьюки (1960 г.) [2]. (Справедливости ради сле- дует отметить что, пожалуй, первым, кто использовал свойства ДПФ для усовер- шенствования алгоритма его расчета, столетием ранее, был немецкий математик Гаусс. Свой вклад внесли Рунге (1903 г.), Ланцош (1942 г.) и др.). Возможность применения БПФ длинны N для вычисления круговой свертки вместо ДПФ длины M, ограничена единственным требованием: N ≥ M. (3) Свертка в частотной области. Пусть сигнал (например, проекционные данные томографа) и ядро заданы соответственно N1 и N2 действительными от- счетами. Минимальный период ДПФ при отсутствии наложения: M ³ 3N1 – 2. (4) При вычислении ДПФ методом БПФ по основанию 2 достаточно увеличить период до N = 2q ≥ M. В общем, для выполнения свертки необходимо выполнить следующие операции. 1. Дополнить последовательности сигнала N1 и ядра N2 нулевыми отсчетами до общей длины периода N. 2. Выполнить прямое комплексное БПФ сигнала длиной N отсчетов (мнимая составляющая равна нулю). 3. Выполнить прямое комплексное БПФ ядра длиной N отсчетов (мнимая составляющая равна нулю). 4. Произвести почленное умножение одноименных гармоник спектров сиг- нала и ядра. Для этого в общем случае необходимо выполнить N комплексных умножений. 5. Выполнить обратное БПФ (ОБПФ) результатов N комплексных умноже- ний. 6. Выбрать из N результатов действительной части ОБПФ N1 значений свертки (мнимая составляющая результатов ОБПФ очевидно равна нулю). В результате выполнения пунктов 1–6, формально используя теорему об эк- вивалентности свертки во временной области умножению в частотной области, можно получить апериодическую свертку исходного сигнала N1 с ядром N2 = = 2N1 – 1. Оптимизация вычислений свертки. Рассмотрим пути повышения эффек- тивности вычисления свертки. Быстрое преобразование Фурье дает возможность преобразования комплексного сигнала длины N, представляющего собой пару последовательностей (действительной и мнимой), длиной N отсчетов каждая [3]. Это открывает возможность одновременной обработки двух действительных по- следовательностей [4]. Но так как программа БПФ предполагает наличие дейст- вительной и мнимой составляющей, то в данном случае на выходе вместо ожи- даемых спектров пары входных действительных последовательностей мы полу- Быстрая свертка на основе БПФ ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 3 65 чим «нечто» другое. В принципе, если нас интересуют спектры, то путем некото- рых дополнительных операций их можно получить. При вычислении же свертки в этом нет нужды. Оказалось, что достаточно выполнить почленное умножение комплексных гармоник спектров «нечто» и ядра. Из области спектров при помо- щи ОБПФ N комплексных результатов умножения преобразуется в две круговых свертки двух входных сигналов с ядром. Такой подход позволяет примерно вдвое сократить число операций на вычисление свертки. Есть также возможность несколько сократить объем вычислений при реали- зации БПФ за счет использования прямого порядка обработки отсчетов со сторо- ны сигнала (т.н. «прореживание по частоте»), так как при выполнении покомпо- нентного умножения спектров порядок следования гармоник не имеет значения. Это позволяет исключить операции, связанные с созданием требуемого порядка следования членов обрабатываемой последовательности. Еще одна возможность сокращения количества операций — переход от опе- раций комплексных умножений к действительным умножениям. Переход на ум- ножении спектров позволяет в 6 раз уменьшить требуемое количество операций с плавающей точкой. Условие правомочности перехода к действительным умно- жениям спектров — отсутствие мнимой составляющей в спектре ядра. Послед- нее, учитывая четность функции ядра (h[i] = h[–i]), может быть достигнуто за счет соответствующего его кольцевого сдвига (на 0 или N/2 отсчетов). Рассмотрим пример. Пусть длина периода N = 8, а исходное ядро задано в 5-ти дискретных точках: [h[–2], h[–1], h[0], h[1], h[2]]. (5) С учетом h[–i] = h[–i + N] при нулевом кольцевом сдвиге получим: h[6] = h[8 – 2] = h[–2], h[7] = h[8–1] = h[–1]. В итоге, 5 отсчетов исходного ядра при нулевом сдвиге [h[–2], h[–1], h[0], h[1], h[2]] на участке 0…N – 1 должны быть расположены в следующем порядке: h[0], h[1], h[2], 0, 0, 0, h[–2], h[–1]. (5a) При сдвиге на N/2 исходные 5 отсчетов следует дополнить нулями слева и справа, причем центральный отсчет исходной последовательности h[0] должен быть расположен в точке N/2 (N/2 = 4) участка 0…N – 1: 0, 0, h[–2], h[–1], h[0], h[1], h[2], 0. (5b) М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская 66 Показанные выше оба расположения исходных отсчетов ядра на кольце ис- ключают появление в спектре ядра мнимой составляющей. Заметим, что оба рас- положения эквивалентны с точки зрения результатов свертки. Однако если не предполагается последующая интерполяция свертки, удобнее воспользоваться расположением (5a). В этом случае все N1 результатов свертки идут первыми. Полученный после одного прямого БПФ спектр ядра запоминается и далее при выполнении свертки используется для всего массива данных. Рассмотрим на простом примере вычисление свертки двух входных последо- вательностей длиной N1 = 4 ([0, 0, 0, 1] и [1, 0, 0, 0]) с ядром длиной N2 = 7, ([–3, –7, –35, 105, –35, –7, –3]). После дополнения нулями входных последовательно- стей до одинаковой длины (N1 + (N2 – 1)/2 ≤ 2P = 8) получим: sx = [0, 0, 0, 1, 0, 0, 0, 0], (6) sy = [1, 0, 0, 0, 0, 0, 0, 0]. Ядро может быть представлено двумя различными способами, при которых его спектр не содержит мнимой составляющей. В нашем случае (N = 8) возмож- ны два эквивалентных представления ядра: h = [105, –35, –7, –3, 0, –3, –7, –35], (6a) h = [0, –3, –7, –35, 105, –35, –7, –3]. (6b) Единственно, чем отличаются указанные последовательности (h), так это кольцевым сдвигом по отношению к входным последовательностям (sx, sy). Две входные действительные последовательности (sx, sy), каждая длиной N отсчетов, рассматриваем как одну комплексную последовательность длиной N. После выполнения комплексного БПФ длиной N получим действительную (Sx) и мнимую (Sy) составляющие спектра. Выполняем их покомпонентное умножение на полученный ранее действительный спектр ядра (Hr): SHr[k] = Sx[k]·Hr[k], (7) SHi[k] = Sy[k]·Hr[k]. После выполнения обратного БПФ результатов умножения спектров во вре- менной области получим значения двух кольцевых сверток. Результаты кольце- вых сверток с ядром h сигналов sx и sy будут расположены соответственно на месте действительной и «мнимой» составляющих результата обратного БПФ. Линейная свертка исходных последовательностей ([0, 0, 0, 1], [1, 0, 0, 0]) и ядра ([–3, –7, –35, 105, –35, –7, –3]), вычисленная при помощи суммы парных произведений, соответственно равна: Быстрая свертка на основе БПФ ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 3 67 [–3, –7, –35, 105], [105, –35, –7, –3]. Результаты вычисления кольцевых сверток тех же данных с ядром (6a): [–3, –7, –35, 105, –35, –7, –3, 0], [105, –35, –7, –3, 0, –3, –7, –35]. В случае использования представления ядра в виде (6b) результаты вычисле- ния кольцевых сверток претерпевают кольцевой сдвиг: [–35, –7, –3, 0, –3, –7, –35, 105], [0, –3, –7, –35, 105, –35, –7, –3]. На рис. 1 представлены результаты линейной интерполяции кольцевых свер- ток последовательностей sx и sy с ядром h (см. (6), (6a)). Видно, что результаты первых четырех отсчетов совпадают с отсчетами линейных сверток. Таким образом, на последнем примере еще раз подтверждена эквивалент- ность представлений ядра (5a) и (5b). Далее ограничимся его представлением в виде (5a). Рис. 1 Оценим требуемое количество элементарных операций на выполнение свертки входной последовательности длиной N1 с полным ядром длиной N2 = 2N1 – 1. Рассмотрим случай N1 ≤ 2P. Допуская частичное перекрытие, примем длину периода M ≥ 2N1 – 1. С учетом применения БПФ N = 2P+1. Для получения по N1 значений двух сверток необходимо выполнить прямое и обратное БПФ длины N = 2P+1 и произвести 2N действительных умножения спектров. БПФ по основанию 2 комплексного сигнала длины N = 2P+1 для своей реали- зации требует (N/2) log2N комплексных умножения и N log2N комплексных сло- жения. При отсутствии интерполяции количество операций реализации обратно- го БПФ такое же, как и прямого. На реализацию комплексного умножения необ- ходимо 4 действительных умножения и 2 сложения, для комплексного сложения — 2 действительных сложения. С учетом изложенного выше, требуемое количе- М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская 68 ство действительных сложений (s) и умножений (u) на реализацию одной сверт- ки длиной 2P потребуется: умножений 2P(6 + 4p), (8a) сложений 2P(6 + 6p). (8b) Всего на вычисление свертки длиной 2P потребуется операций: op_conv = 2P(12 + 10p). (9) (Последнее выражение предполагает примерно одинаковую длительность опера- ций умножения и суммирования, что при работе с плавающей точкой близко к истине). Оценим необходимое количество операций при вычислении свертки в виде суммы парных произведений. Обычно считают, что для вычисления свертки сиг- нала длиной N1 с ядром длиной N2 требуется примерно N1N2 операций умно- жения с накоплением. Если учесть, что нас интересует только N1 значений сверт- ки, то число операций умножения с накоплением можно уменьшить примерно вдвое и сделать равной N12. Общее число элементарных операций при вычисле- нии свертки составит величину 2N12 = 2*(2P)2: op_conv2 = (2P) 2 (2P). (10) Сравнивая количество операций при различных реализациях свертки ((9) и (10)), приходим к выводу о целесообразности использования методов быстрой свертки уже при p > 5. Практически переход в область спектров оправдан при вычислении свертки длиной не менее 64–128 отсчетов. На рис. 2 показано суммарное количество операций умножения и суммиро- вания при вычислении одного отсчета свернутой проекции при длине входной последовательности 2P. Линейная зависимость (12 + 10p) соответствует случаю использования БПФ, экспоненциальная (2P+1) — вычислению свертки в виде сум- мы парных произведений. Трудоемкость вычисления свертки с переходом в об- ласть спектров по отношению к трудоемкости вычисления в виде суммы парных произведений (op_conv/op_conv2 = + 6 5 p 2p ) представлена на рис. 3. Из соотно- шения следует, что при большой длине свертки (например, 1024 или 2048) ис- пользование БПФ существенно сокращает требуемое количество операций (в 18,3 и 33,6 раза соответственно). Особенность свертки на основе БПФ с полным ядром заключается в требо- вании выбора периода из условия N ³ 2N1 – 1. При N1 ≤ 2P достаточно сделать период равным N = 2P+1. Но уже при условии N1 = 2P + 1 приходится выбирать пе- риод вдвое больше (N = 2P+2), что более чем в два раза увеличивает требуемое ко- Быстрая свертка на основе БПФ ISSN 1560-9189 Реєстрація, зберігання і обробка даних, 2005, Т. 7, № 3 69 личество операций. Интуитивно чувствуется, что заменив исходное полное ядро ядром несколько меньшей длины, при длинных свертках мы совершим сравни- тельно небольшую погрешность. Однако это позволяет вдвое снизить период (N = 2P+1). Оценим порядок погрешности результатов свертки из-за использова- ния более короткого ядра. Ясно, что погрешность зависит как от ядра, так и кон- кретного набора отсчетов сигнала. Как правило, вес ядра быстро затухает. Для определенности рассмотрим ядро Шеппа-Логана, часто используемое в компью- терной томографии: := hi 1 - 1 4 i2 . Рис. 2 Рис. 3 Также предположим, что нормированная к 1 входная последовательность длиной N1 имеет в начале и в конце по d отсчетов равных 1. Теперь можно полу- чить значение максимальной погрешности свертки из-за сокращения длины пол- ного ядра M до величины 2N1 – 1 – 2d. Погрешность (по модулю) достигает мак- симального значения для первого и последнего элементов результатов свертки. Ее величина определяется простым соотношением: d ( ) - 2 N1 1 ( ) - - 2 N1 1 2 d (11) График максимальной погрешности свертки представлен на рис. 4. М. В. Синьков, А. И. Закидальский, Е. А. Цыбульская 70 Рис. 4 Из рассмотренного материала видно, что, допустив приемлемую погреш- ность из-за сокращения длины ядра, в ряде случаев можно дополнительно (более чем в 2 раза) сократить объем вычислений свертки. Такой метод особенно подхо- дит при свертке проекционных данных в томографии. Это связано с тем, что обычно начало и конец проекции содержат нулевые отсчеты. В результате по- грешность свертки из-за сокращения длины ядра будет еще меньше приведенной выше оценки. Выводы Замена операции свертки в области сигналов умножением их спектров для длинных последовательностей позволяет существенно сократить требуемое ко- личество операций. Так, при длине входной последовательности 2048 отсчетов использование БПФ сокращает требуемое количество операций более чем в 30 раз. Повышению эффективности вычисления свертки способствует: — использование комплексного БПФ одновременно двух действительных последовательностей, одна из которых рассматривается как чисто мнимая. В ре- зультате вдвое снижаются затраты на преобразования из области сигналов в об- ласть спектров и обратно; — представление ядра после добавления требуемого числа нулевых отсчетов в виде четной функции. Это дает возможность при умножении спектров в 6 раз сократить количество операций за счет замены комплексных умножений дейст- вительными; — сокращение длины кольцевой свертки за счет некоторого наложения сиг- налов вне зоны интереса, а также за счет выбора более короткого ядра. В резуль- тате в ряде случаев можно дополнительно вдвое снизить период БПФ, сохраняя при этом допустимую погрешность. 1. Рабинер Л., Гоулд Б. Теория и применение цифровой обработки сигналов. — М.: Мир, 1978. — 848 с. 2. Cooley J.W. and Tukey J.W. An Algorithm for the Machine Calculation of Complex Fourier Series // Math. Comput. — 1965. — Vol. 19, N. 90. — Р. 297–301. 3. Войнаровский М. Программирование. Быстрое преобразование Фурье. — 2002. http://psi-logic.narod.ru/fft/fft1.htm 4. Implementing Fast Fourier Transform Algorithms of Real-Valued Sequences with the TMS320 DSP Family. APPLICATION REPORT: SPRA291. Robert Matusiak, 1997. Поступила в редакцию 01.09.2005 http://psi-logic.narod.ru/fft/fft1.htm N ≥ M. (3) N ≥ M. (3) N ≥ M. (3) После выполнения обратного БПФ результатов умножения спектров во временной области получим значения двух кольцевых сверток. Результаты кольцевых сверток с ядром h сигналов sx и sy будут расположены соответственно на месте действительной и «мнимой» составляющих результата обратного БПФ.

Быстрая свертка на основе БПФ

Репозитарії

Схожі ресурси