Свертка через БПФ 6 Сверт
Работа добавлена на сайт samzan.net:
Глава 18 - Свертка через БПФ 6
Свертка через БПФ
Эта глава представляет две важные техники ЦОС, обработку сигналов по сегментам (overlap-add method – метод суммирования перекрытий) и свертку через БПФ. При обработке сигналов по сегментам длинный сигнал разбивается на меньшие сегменты для более легкой обработки. Свертка через БПФ использует метод обработки сигналов по сегментам совместно с быстрым преобразованием Фурье, позволяя осуществлять свертку сигналов путем перемножения их спектров. Для ядра фильтра длиннее, чем 64 точки, свертка через БПФ вычисляется быстрее и дает точно тот же самый результат.
Метод обработки сигналов по сегментам
Имеется много приложений ЦОС, где длинный сигнал должен фильтроваться по сегментам. Например, высокоточное цифровое аудио требует темп данных около 5 Мбайт/мин, а видео требует около 500 Мбайт/мин. При таком высоком темпе данных обычно у компьютера не хватает памяти, что бы одновременно вести обработку целиком всего сигнала. Имеются также системы, где обработка сигнала сегмент за сегментом вызвана их работой в реальном времени. Например, телефонный сигнал не может быть задержан более чем на несколько сотен миллисекунд, ограничиваясь суммой данных, обрабатываемых в одно мгновение. И в других приложениях обработка может требовать сегментации сигнала. Пример этого является БПФ свертка, главная тема этой главы.
Метод обработки сигналов по сегментам основывается на фундаментальной технике ЦОС: (1) разложить сигнал на простые компоненты, (2) обработать каждый компонент некоторым полезным способом и (3) скомбинировать обработанные компоненты в финальный сигнал. Рисунок 18-1 показывает пример, как это делается. На рисунке (а) показан сигнал, который фильтруется, на рисунке (b) – ядро фильтра, низкочастотный оконный sinc фильтр. Внизу (i) показан отфильтрованный сигнал, сглаженная версия (а). Ключ этого метода заключается в том, как длина этого сигнала подвергается свертке. Когда N отсчетов сигнала свертываются с M отсчетами ядра фильтра, выходной сигнал будет иметь длину N+M-1 отсчетов. Например, входной сигнал (а) состоит из 300 отсчетов (от 0 до 299), ядро фильтра (b) состоит из 101 отсчетов (от 0 до 100), и выходной сигнал (i) имеет 400 отсчетов (от 0 до 399).
Другими словами, когда фильтруются N отсчетов сигнала, он будет расширен на M-1 точку вправо. (Это при условии, что ядро фильтра имеет точки от 0 до М-1; если используется отрицательная индексация в ядре фильтра, то расширение будет также и влево). В (а) нули добавлены к сигналу между отсчетами 300 и 399, что бы показать, где имеется расширение. Не смущайтесь маленькой величиной выходного сигнала на концах (i). Это результат малых величин на концах оконного sinc фильтра. Все 400 отсчетов в (i) ненулевые, хотя некоторые из них такие маленькие, что не видны на графике.
Рисунки (с), (d) и (е) показывают разложение, используемое в методе обработки сигналов по сегментам. Сигнал разбивается на сегменты, каждый сегмент имеет 100 отсчетов из исходного сигнала. Кроме того, добавляются 100 нулей справа к каждому сегменту. На следующем этапе каждый сегмент индивидуально фильтруется путем свертки с ядром фильтра. Эти обработанные выходные сегменты показаны в (f), (g) и (h). Поскольку каждый входной сегмент имеет 100 отсчетов, и ядро фильтра имеет 101 отсчет, выходной сегмент будет иметь 200 отсчетов. Важно понимать, что 100 отсчетов, добавляемых к каждому входному сегменту для его расширения, позволяют осуществлять свертку.
Заметьте, что в результате расширения выходные сегменты перекрываются друг с другом. Это перекрытие выходных сегментов суммируется, давая выходной сигнал (i). Например, отсчеты от 200 до 299 в (i) находятся суммированием соответствующих отсчетов из (g) и (h). Суммирование перекрытий (метод обработки сигнала по сегментам) производит точно такой же сигнал, как и прямая свертка. Недостаток заключается в сильном усложнении программы для отслеживания перекрывающихся отсчетов.
Свертка через БПФ
Свертка через БПФ основано на том, что перемножение в частотной области соответствует свертке во временной области. Входной сигнал преобразуется с помощью ДПФ в частотную область, перемножается на частотный отклик фильтра, и затем преобразуется назад во временную область с помощью инверсного ДПФ. Этот подход был известен еще со времен Фуре, но на практике не применялся. Это объясняется тем, что время вычисления ДПФ было больше, чем время прямого вычисления свертки. Ситуация изменилась с 1965 года с открытием быстрого преобразования Фурье (БПФ). Использование алгоритмов БПФ сделало вычисление ДПФ, выполненное через частотную область, более быстрым, чем прямое вычисление свертки во временной области. Окончательный результат тот же самый; изменилось только число вычислений благодаря более эффективным алгоритмам. По этой причине свертка через БПФ так же называется высокоскоростной сверткой.
РИСУНОК 18-1
Метод обработки сигнала по сегментам (overlap-add method). Цель – осуществление свертки входного сигнала (а) с ядром фильтра (b). Входной сигнал разбивается на сегменты (с), (d) и (е), добавляется необходимое для осуществления свертки число нулей. Свертка каждого входного сегмента с ядром фильтра производит выходные сегменты (f), (g) и (h). Выходной сигнал (i) находится сложением перекрывающихся выходных сегментов.
Свертка через БПФ (дальше просто БПФ свертка) использует метод обработки сигнала по сегментам, показанный на рисунке 18-1, но только способ преобразования входного сегмента в выходной изменен. Рисунок 18-2 показывает, как входной сегмент преобразуется в выходной сегмент с помощью БПФ свертки. Вначале находится частотная характеристика фильтра с помощью ДПФ ядра фильтра (используя БПФ). Например, (а) показывает ядро фильтра, это низкочастотный оконный sinc фильтр. БПФ преобразует его в реальную и мнимую часть частотной характеристики (частотного отклика), показанных в (b) и (с). Эти сигналы частотной области могут не выглядеть похожими на характеристику низкочастотного фильтра потому, что они показаны в прямоугольной форме. Вспомните, полярная форма обычно лучше подходит для человеческого восприятия, а прямоугольная - для математических вычислений. Эти реальная и мнимая части хранятся в памяти компьютора для использования при вычислении каждого сегмента.
Рисунок (d) показывает обработку входного сегмента. БПФ используется для нахождения частотного спектра, он показан в (е) и (f). Частотный спектр выходного сегмента (h) и (i) находится перемножением частотного отклика фильтра (b) и (с) на спектр входного сегмента (е) и (f). Поскольку эти спектры состоят из реальной и мнимой части, они перемножаются согласно формуле 9-1 из главы 9. Затем используется инверсное БПФ для нахождения выходного сегмента (g) из его частотного спектра (h) и (i). Выходной сегмент точно такой же, как если бы он был получен прямой сверткой входного сегмента (d) и ядра фильтра (а).
БПФ должен иметь достаточную длину, чтобы не было циклической свертки (тоже обсуждалось в главе 9). Это означает, что БПФ должно иметь ту же длину, что и выходной сегмент (g). Например, на рисунке 18-2 ядро фильтра содержит 129 точек, и каждый сегмент содержит 128 точек, это делает длину выходного сегмента равной 256 точкам. В этом случае необходимо использовать 256-точечное БПФ. Следовательно, к ядру фильтра (а) надо добавить 127 нулей для получения общей длины в 256 точек. Аналогично, к каждому входному сегменту надо добавить 128 нулей. Как другой пример, представьте, что вам необходимо свернуть очень длинный сигнал с ядром фильтра, имеющего 600 отсчетов. Одна возможность заключается в использовании сегментов по 425 точек и 1024-точечного БПФ. Другая – использование сегмента из 1449 точек и 2048-точечного БПФ.
Таблица 18-1 показывает пример программы выполнения БПФ свертки. Эта программа фильтрует 10 миллионов точек сигнала, путем свертки его с 400 точками ядра фильтра. Она выполняется разбивкой сигнала на 16 000 сегментов по 625 точек. Когда каждый из этих сегментов свертывается с ядром фильтра, получается выходной сегмент из 625+400-1=1024 точек. Таким образом, требуется 1024-точечное БПФ. После определения и инициализации всех массивов (линии 130-230), на первом шаге вычисляется и запоминается частотная характеристика фильтра (линии 250-310). Линия 260 вызывает воображаемую подпрограмму для загрузки ядра фильтра в XX[0]…XX[399] и устанавливает XX[400]…XX[1023] в ноль. Подпрограмма в линии 270 – БПФ, преобразующее 1024 точек, содержащихся в XX[ ], в 513 отсчетов, содержащихся в REX[ ] и IMX[ ] - реальной и мнимой частях частотной характеристики. Эти величины передаются в массивы REFR[ ] и IMER[ ] (для REal и IMaginary Frequency Response) для последующего использования в программе.
РИСУНОК 18-2
БПФ свертка. Ядро фильтра (а) и сегмент сигнала (d) преобразуются в свои спектры (b), (c) и (e), (f) через БПФ. Эти спектры перемножаются и дают спектр выходного сегмента (h), (i). Затем через инверсное БПФ находится выходной сегмент (g).
Цикл FOR-NEXT между линиями 340 и 580 контролирует обработку 16 000 сегментов. В линии 360 подпрограмма загружает следующий сегмент для обработки в XX[0]…XX[624] и устанавливает XX[625]…XX[1023] в ноль. В линии 370 подпрограмма БПФ используется для нахождения частотного спектра сегмента с реальной частью из 513 точек, расположенной REX[ ], и с мнимой частью из 513 точек, расположенных в IMX[ ]. Линии 390…430 показывают перемножение частотного спектра сегмента, содержащегося в REX[ ] и IMX[ ] на частотный отклик фильтра, содержащийся в REFR[ ] и IMER[ ]. Результат перемножения записывается в REX[ ] и IMX[ ] на место предыдущих данных. Поскольку это теперь частотный спектр выходного сегмента, может быть использовано инверсное БПФ для нахождения выходного сегмента. Это выполняет воображаемая подпрограмма инверсного БПФ в линии 450, которая преобразует 513 точек, содержащихся в REX[ ] и IMX[ ], в 1024 точки, содержащихся в XX[ ], выходном сегменте.
Линии 470…550 управляют перекрытием сегментов. Каждый выходной сегмент делится на две секции. Первые 625 точек (от 0 до 624) необходимо скомбинировать с перекрывающимися точками из предыдущего выходного сегмента и записать в выходной сигнал. Последние 399 точек (от 625 до 1023) необходимо запомнить, так как они могут перекрываться со следующим выходным сегментом.
Что бы это понять, посмотрите назад на рисунок 18-1. Отсчеты от 100 до 199 в (g) необходимо скомбинировать с перекрывающимися отсчетами из предыдущего выходного отсчета (f), и затем их можно поместить в выходной сигнал (i). Для сравнения, отсчеты от 200 до 299 в (g) необходимо запомнить, что бы их можно было скомбинировать с отсчетами из следующего сегмента (h).
Вернемся к программе. Массив OLAP[ ] используется для хранения 399 отсчетов, которые перекрываются с отсчетами следующего сегмента. В линиях 470…490 399 величин в этом массиве (из предыдущего выходного сегмента) складываются с отсчетами текущего сегмента, содержащиеся в XX[ ]. Мифическая подпрограмма в линии 550 направляет выходные 625 отсчетов от XX[0] до XX[624] в файл, хранящий выходной сигнал. 399 отсчетов текущего выходного сегмента, которые необходимы для следующего выходного сегмента, записываются в OLAP[ ] в линиях 510…530.
После обработки всех сегментов от 0 до 15 999, массив OLAP[ ] будет содержать 399 отсчетов из сегмента 15999, которые должны перекрываться с сегментом 16 000. Поскольку сегмент 16 000 не существует (или может рассматриваться как состоящий из одних нулей), эти 399 отсчетов записываются в выходной сигнал в линии 600. Это делает длину выходного сигнала равной 16000625+399=10 000 399 точкам. Это совпадает с длиной входного сигнала плюс длина ядра фильтра минус единица.
Увеличение скорости
Когда БПФ свертка быстрее, чем стандартная свертка? Ответ зависит от длины ядра фильтра, как показано на рисунке 18-3. Время стандартной свертки прямо пропорционально числу точек ядра фильтра. Для сравнения, время, требуемое для БПФ свертки, увеличивается очень медленно, как логарифм от числа точек ядра фильтра. Пересечение происходит, когда ядро фильтра имеет около 40…80 отсчетов (зависит от использования конкретного оборудования).
100 'БПФ СВЕРТКА
110 'Эта программа свертывает 10 миллионов точек сигнала с 400 точками ядра фильтра. Входной
120 'сигнал разбивается на 16 000 сегментов по 625 точек. Используется 1024-точечное БПФ.
130 '
130 ' 'ИНИЦИАЛИЗАЦИЯ МАССИВОВ
140 DIM XX[1023] 'сигнал временной области (для БПФ)
150 DIM REX[512] 'реальная часть частотной области (для БПФ)
160 DIM IMX[512] 'мнимая часть реальной области (для БПФ)
170 DIM REFR[512] 'реальная часть частотного отклика фильтра
180 DIM IMFR[512] 'мнимая часть частотного отклика фильтра
190 DIM OLAP[398] 'хранятся перекрывающиеся отсчеты от сегмента к сегменту
200 '
210 FOR I% = 0 TO 398 'обнуление массива перекрывающихся отсчетов
220 OLAP[I%] = 0
230 NEXT I%
240 '
250 ' 'НАХОЖДЕНИЕ И ЗАПОМИНАНИЕ ЧАСТОТНОГО ОТКЛИКА ФИЛЬТРА
260 GOSUB XXXX 'Воображаемая подпрограмма для загрузки ядра фильтра в XX[ ]
270 GOSUB XXXX 'Воображаемая БПФ подпрограмма: XX[ ] --> REX[ ] & IMX[ ]
280 FOR F% = 0 TO 512 'Запоминание частотного отклика в REFR[ ] & IMFR[ ]
290 REFR[F%] = REX[F%]
300 IMFR[F%] = IMX[F%]
310 NEXT F%
320 '
330 ' 'ОБРАБОТКА КАЖДОГО ИЗ 16 000 СЕГМЕНТОВ
340 FOR SEGMENT% = 0 TO 15999
350 '
360 GOSUB XXXX 'Воображаемая п/п загрузки следующего входного сегмента в XX[ ]
370 GOSUB XXXX 'Воображаемая п/п БПФ: XX[ ] --> REX[ ] & IMX[ ]
380 '
390 FOR F% = 0 TO 512 'Умножение частотного спектра на частотный отклик
400 TEMP = REX[F%]*REFR[F%] - IMX[F%]*IMFR[F%]
410 IMX[F%] = REX[F%]*IMFR[F%] + IMX[F%]*REFR[F%]
420 REX[F%] = TEMP
430 NEXT F%
440 '
450 GOSUB XXXX 'Воображаемая п/п инверсного БПФ: REX[ ] & IMX[ ] --> XX[ ]
460 '
470 FOR I% = 0 TO 398 'Сложение последнего перекрывающегося сегмента с текущим
480 XX[I%] = XX[I%] + OLAP[I%]
490 NEXT I%
500 '
510 FOR I% = 625 TO 1023 'Запоминание отсчетов, перекрывающих следующий сегментом
520 OLAP[I%-625] = XX[I%]
530 NEXT I%
540 '
550 GOSUB XXXX 'Воображаемая п/п для вывода 625 отсчетов, хранящихся
560 ' 'в XX[0] … XX[624]
570 '
580 NEXT SEGMENT%
590 '
600 GOSUB XXXX 'Воображаемая п/п для вывода всех 399 отсчетов в OLAP[ ]
610 END
ТАБЛИЦА 18-1
Важно помнить, что ядро фильтра короче, чем 60 точек, может вычисляться быстрее при использовании стандартной свертки, и время вычисления пропорционально длине ядра. Более длинное ядро фильтра может быть вычислено быстрее при использовании БПФ свертки. При использовании БПФ свертки, длина ядра фильтра может быть выбрана такой, какой вы желаете, с небольшим увеличением времени вычисления. Например, 16 000 точек ядра фильтра требуют только, примерно, в два раза большего времени вычисления по сравнению с 64 точками.
РИСУНОК 1-3
Время вычисления БПФ свертки. БПФ свертка быстрее, чем стандартная свертка, когда ядро фильтра длиннее 60 точек. Здесь показано время вычисления для Pentium 100 МГц, использующее одинарную точность с плавающей запятой.
Скорость свертки также определяется точностью вычисления (как описывалось в главе 12 для БПФ). Это вызвано тем, что ошибка округления в выходном сигнале определяется общим числом вычислений, которое прямо пропорционально времени вычисления. Если выходной сигнал вычисляется быстрее, то и вычисления будут точнее. Например, представьте свертку сигнала с 1000 точками ядра фильтра и одинарной точностью с плавающей запятой. При использовании стандартной свертки, типичная ошибка округления может составлять около одной двадцати тысячной (из руководства главы 4). Для сравнения, БПФ свертка может на порядок быть быстрее и на порядок точнее (т.е. одна двухсот тысячная).
Держите БПФ свертку подальше до тех пор, пока вам не понадобятся большие суммы данных и предельно длинные ядра фильтров. Ориентируйтесь на миллионы отсчетов в сигнале и тысячи точек в ядре фильтра. Все, что меньше, не оправдывает сверх усилия на программирование. Не хотите ли написать собственную программу для БПФ свертки? Посмотрите программные библиотеки и пакеты программ для предварительного написания кода. Начните с сайта этой книги (смотрите страницу авторских прав).
2. ТЕМА План Безстрокові трудові договори
3. реферат дисертації на здобуття наукового ступеня кандидата медичних наук Київ ' Д
4. реферат дисертації на здобуття наукового ступеня доктора філософських наук Київ 1999 Д
5. Реферат на тему Подготовка ИТспециалистов в России В
6. Общая экономическая теория
7. Определение качества бензина 2
8. тема Станиславского
9. Вариант 1 Текстовый редактор программа предназначенная для создания редактирования и форматирова
10. фактора Forever Young- Our Officil X Fctor Story 2011 Перевод сайта- http---www
11. Проверка технического состояния и регулировка изолирующего сопряжения
12. .О.Богомольця ldquo;Затвердженоrdquo;
13. Метод еквівалентного генератора
14. Устройство процессора
15. Septembre 2015 Nom - Photo Pr~nom - Dte et lieu de nissnce - Ntionlit~ ctue
16. О соотношении распада и развития психики
17. Лазерная маркировка защита промышленной продукции от подделки
18. Применение математических методов при обновлении парка автотранспортного предприятия.html
19. Исследование эффективности лизинговых сделок предприятия на примере ОАО
20. собственность и присвоение не следует отождествлять