Лайонс Р. Цифровая обработка сигналов. Второе издание. Пер. с англ. (2006) (1095937), страница 31
Текст из файла (страница 31)
Если для нас важна скорость работы, первым делом нужно проверить, вычисляются ли синусы н косинусы каждый раз, когда требуется поворачивающий множитель. Обычно вычисление тригонометрических функций занимает множество машинных тактов. Скорость вычисления БПФ можно повысить, вычислив поворачивающие множители заранее и сохранив их таблицу в памяти. В этом случае вычисление поворачивающего множителя заменяется выборкой из таблицы.
Если мы пишем собственную процедуру выполнения БПФ, мы можем реализовать алгоритм в целочисленной арифметике, которая на большинстве машин работает быстрее, но при этом мы должны принять меры против возможных переполнений на выходах бабочек н внимательно отнестись к масштабированию Мы говорим, что количество комплексных умножений при реализации БПФ равно (МУ2)!оязУ(см. (4-2)) именно потому, что Ж-точечное БПФ содержит (ХУ2)1оязХбабочек.
Глааа4. Быст оеп еоб аэованиеФ ье результатов'. При использовании целочисленной арифметики следует быть внимательным: некоторые К15С процессоры в действительности выполняют целочисленные операции медленнее, т. к. они оптимизированы для выполнения операций над числами с плавающей запятой. Если мы используем для вычислений векторный процессор, программы для этих процессоров всегда оптимизированы, т. к. их главная цель — высокая скорость вычислений. Изготовители векторных процессоров обычно рекламируют свои изделия, указывая скорость выполнения на них 1024-точечного БПФ.
Посмотрим теперь, какие возможности есть у нас при выборе структуры БПФ для реализации в виде специализированной аппаратуры. Обсуждавшиеся ранее структуры бабочек БПФ обычно попадают в одну из двух категорий: алгоритмы БПФ с замещением и алгоритмы БПФ с удвоенной памятью. Алгоритм с замещением показан на рисунке 4.5. Выход бабочки запоминается в той же ячейке памяти, в которой хранились входные отсчеты. Память для хранения промежуточных результатов не нужна. В этом случае для Х-точечного БПФ требуется только 2М ячеек памяти (коэффициент 2 учитывает то, что операция бабочки выполняется над комплексными числами, имеющими действительную и мнимую части).
Камнем преткновения при реализации алгоритмов с замещением является довольно сложная адресация памяти. Структура БПФ с двойной памятью изображена на рисунке 4.10. В этом случае необходима промежуточная память, т. к. в структуре уже нет стандартной бабочки, и требуется дополнительно 4Х ячеек памяти. Но доступ к данным и адресация памяти в этих структурах намного проще, чем в случае алгоритма с замещением. Высокоскоростные интегральные схемы с плавающей запятой, реализующие конвейерные структуры БПФ, более полно используют преимущества конвейерной архитектуры при использовании алгоритмов с двойной памятью [18].
Существует еще один класс структур БПФ, известный как алгоритмы с постоянной геометрией, которые делают адресацию памяти не только простой, но и одинаковой для всех каскадов БПФ. Эти структуры особенно интересны тем, кто проектирует специализированные аппаратурные процессоры БПФ [4, 19]. С точки зрения аппаратуры в общем случае алгоритмы с прореживанием по времени являются оптимальными для действительных входных последовательностей, а алгоритмы с прореживанием по частоте больше подходят для обработки комплексных входных последовательностей [8]. Когда входная последовательность БПФ симметрична во времени, для устранения ненужных операций используются специальные структуры БПФ. Эти специальные структуры, основанные на симметрии данных, описаны в литературе [20].
В случае двумерного Б П Ф, например, при обработке изображений, алгоритмы с прореживанием по частоте считаются оптимальными [21]. Ваше приложение может оказаться таким, что бит-реверсивная перестановка входной и выходной последовательности не важна. Некоторые приложения позволяют манипулировать выходной последовательностью БПФ в бит-реверсивном порядке без восстановления нормального порядка отсчетов.
Затем обратное преобразование, Переполнением называется то, что происходит, когда результат арифметической операции содержит слишком много бит или разрядов и не может быть представлен в предназначенных для его хранения регистрах Переполнение данных БПФ рассматривается в разделе 12 3. Библиог а ия 161 которое использует входную последовательность в бит-реверсивном порядке, даст результат во временной области в нормальном порядке. В этой ситуации бит-реверсивная перестановка не нужна вообще. Примером подобного использования БПФ является перемножение двух преобразований Фурье в частотной области для получения свертки или корреляции во временной области'.
Как можно видеть, выбор оптимального алгоритма и аппаратурной архитектуры Б Г1 Ф представляет собой достаточно сложную проблему, но, к счастью, литература может дать нам указания по ее решению [4, 22, 231. Библиография 1. Соо!еу, !. апб Ти1сеу, Г. «Ап А18опгЬш Гог сЬе МасЬГпе Са1си1аг1оп о1 Сошр1ех Роипег Бепея», Май. Сотриг., 'ч'о!. 19, ЬГо. 90, Арг. 1965, рр. 297-301. 2. Соо!еу,Г., Г.еичя, Р., ап8 'ч1!е!сЬ, Р. «Н!ягопса! а!отея оп гЬе Еаяс Еоипег ТгапяГопп», 1ЕЕЕ Ттапя. оп Аийо апг1 ЕГесгтоасоиябся, 'ч"о1. АГ)-15, Хо. 2, Гине 1967. 3.
НаггЬ, К Г. «ОпгЬе Цяе о! ч1г1пс1оия Гог Наппошс Апа1угйя члгЬ гЬе Г)1ясгеге Ро- ипег ТгапяГопп», Ртосеег!Гпйя о/йе 1ЕЕЕ, чо1. 66, Хо. 1, р. 54, ! ап и агу 1978. 4. ОррепЬецп, А. т/., апс! 5сЬаГег, К. Ж. 1)ьястеге-ТГте 5!8па! Ртосеяятй, Ргепг1- се-На11, Епй!е-и ооеГ СИЬ, Меч Гегяеу, 1989, р. 608 (имеется русский перевод одного из предыдущих изданий: Оппенгейм А. В., Шафер Р.
В. «Цифровая обработка сигналов», пер. с англ. / под ред. С. Я. Шаца, Мс Связь, 1979, доступен по адресу еЬр-Ьоо)с.пагосГ.ги/ОрБЬГ)5р.гГ)чи). 5. КаЬГпег, 1.. К. апс1 Со!й, В. ТйеотуапгГАррйсабоп о/1)Г8Ыа!5!8па!Ртосеяяпй, Ргепг1се-На!1, Епй)аоод СИЬ, Хеи Гегяеу, 1975, р. 36? (есть русский перевод: Рабинер Л., Голд Б. «Теория и применение цифровой обработки сигналов», Мс Мир, 1978, доступен по адресу Ьтср://йео81п.пагосГ.ги/агЬ1ч/с!яр/сГярЗ Ьтш). 6. 5сеагпя, 5. В!81Га! 5!8паГАпа!уяья, НаусГеп Воплос Со., КосЬе11е Раг1с, ЬГечч Гегяеу, 1975, р. 265. 7.
Ртойтатя/отР18ГГа! 5Гйпа!Ргосеяяпй, СЬаргег 1, 1ЕЕЕ Ргеяя, ЬГеч Ъ'ог)с, 1979. 8. Богепяоп, Н. 1т., !опея, Г). 1, НеЫешап, М. Т., апс! Виггия, С. 5. «Кеа1-Ча1иегГ Еаяс Роипег ТгапяГопп АГйопГЬшя» 1ЕЕЕ Ттапя, оп Асои»Г. 5реесй, апг1 5мпа! Ргос, ч'о!. А55Р-З5, Хо.
6, !ипе 1987. 9. Вгасеъе!1, К. Тйе Еоипет Ттап4отт апг1 1гя Арр!гсабопя, 2пд Ейг1оп, Кеч!яед, МсОган-Н!11, ЬГен Уогй, 1986, р. 405. 10. СоЪЪ, Р. «Г)яе Раяь Роипег ТгапяГогш Ргойгашя го 5!шр11Гу, ЕпЬапсе Игег Апа1уя!я», ЕОАг, 8 МагсЬ 1984. 11. Саг1ш, Г. «Ада апгГ Сепепс ЕЕТ Оепегаье КоиВпея Та!!ого го Уоиг ЬГеегЬ», ЕЮХ, 23 Арп! 1992. 1 Пример использования БПФ для выполнения свертки приведен в разделе 13АО, Глввв4. Быст реп еоб взованиеФ ье 12. Ечапз, Р.
«Ап 1тргочес1 17!8!Г-Кечегяа! Регтигаг!оп А18оП1Ьт 1ог 1Ье Ганг Гоипег аль Наг11еу Тгапйогтз», 1ЕЕЕ Ттапх оп Асоигс. 5реей, апг75гдпа1 Ртос, Чо1. А55Р-35, Хо. 8, Аи8ихг 1987. 13. Виггих, С. Я. «НпзсгатЫш8 1ог Гавг РГТ А18ог11Ьта», 1ЕЕЕ Ттапь. оп Асеан. 5реесй, апй 5цпа1 Ртос, Чо1. 36, Хо.
7, 1и1у 1988. 14. Кодг18иег, 1. 1. «Ап 1тргочес! ГГТ И81г-Кечегеа! А18оПгЬт», 1ЕЕЕ Ттапь. оп Асоихг. 5реесЬ, апИ 5цпа! Ртос, Чо1. АВВР-37, Хо. 8, Аи8иаГ 1989. 15. Еапй, А. «ВК Кечегяег 8сгатЫез !гаага 1ог ГГТ», ЕВН, МагсЬ 2,1995. 16. 1О-АЕ ЯиЬсотт!ггее оп Меавигетепг Сопсерге, «'ЖЬаг 1я гЬе Ганг Гоипег Тгапя- 1опп?», 1ЕЕЕ Ттапх оп Аис6о апг7Е!ес~тоасоизбсь, Чо!. А11-15, Хо. 2, 1ипе 1967. 17. СоЬеп, К., апг! Рег!тап, К. «500 !гНг 8!п8!е-Вопд ГГТ Яузгет 1псогрогагех РВР-Орг1т!гег! СЫря,, Е1)Ы, 31 ОсгоЪег 1984. 18. Е!доп, 1., апд Жшгег, О.
Е. «Г!оаг!п8-ро!пг СЫрз Сагче Оиг ГГТ 8уьгете», Е1есгтоп1с Рея8п, 4 Аициаг 1983. 19. ЕатЬ, К. «СМ08 Ви!!йп8 В!осЬя ЯЬг!и!г апг! Яреес! 11р ГГТ Ъуьгеть», Е1есгтотс Рех!цп, 6 Аи8ихг 1987. 20. Маг!ге!, 1. Э. «ГГТ Ргип!п8», 1ЕЕЕ Ттапл. оп Аийо апИ Е1есгтоасоикйсг, Чо1. А11-19, Хо. 4, РесетЬег 1971. 21. Юи, Н. К., апг! Рао1ош, Г. 1. «ТЬе 8ггисгиге о1Чесгог Кайх Ганг Гоипег Тгапя1огтя», 1ЕЕЕ Ттапь. оп Асоизс. 5реесй, апЫ 5фрга! Ртос., Чо!. АВВР-37, Хо.
8, Аи8иег 1989. 22. А11, Х. М. «Н!8Ь Брей ГГТ Ргосеххог», 1ЕЕЕ Ттати. оп Соттитсайопз, Чо1. СОМ-26, Хо. 5, Мау 1978. 23. Вег8!апс1, С. «Гаьй ГоиПег ТгапИогт НагсЬчаге 1тр1етепсас!опт — Ап Очи и'- ек» 1ЕЕЕ Ттапх оп Аиа1о апс1Е1есгтоасоигггсх, Чо1. А11-17, ! ипе 1969. 164 Глава 5. Фильт ы с имп льснойха актеристикой конечнойдлины программу, программируемый аппаратурный процессор или специализированную интегральную схему. Традиционно линейные цифровые фильтры делятся на два болыпих класса: фильтры с импульсной характеристикой конечной длины (КИХ-фильтры) и фильтры с импульсной характеристикой бесконечной длины (БИХ-фильтры).
Поскольку КИХ-фильтры проще поддаются анализу, мы изучим в этой главе именно их, а БИХ-фильтрам посвятим главу 6. (а) Врем» Время (ы Входная псспедоеа оспедоаатепьность Рис. 6.1. Фильтры: (а) аналоговый фильтр, на входе которого мы видим зашумленный тоновый сигнал, а на выходе — тон, очищенный от шума; (Ь) цифровой эквивалент аналогового фильтра 5.1. Введение в КИХ-фильтры Прежде всего, для вычисления текущего отсчета выходного сигнала КИХ-фильтры используют только текущий и предыдущие отсчеты входного сигнала и совсем не используют выходные отсчеты.
(По этой причине КИХ-фильтры иногда называют также нерекурсивными фильтрами'.) Это приводит к тому, что, если входная последовательность содержит конечное количество ненулевых отсчетов, то выходная последовательность такого фильтра также будет содержать последовательность ненулевых отсчетов конечной длительности, благодаря чему КИХ-фильтры и получили свое имя.
Итак, если входная последовательность, начиная с некоторого момента, преврап(ается в последовательность нулевых отсчетов, то через некоторое время выходная последовательность также будет содержать только нулевые отсчеты. Хотя эта особенность фильтра не представляется необычной, она очень важна, и мы выясним, почему, когда узнаем больше о цифровых фильтрах. Для вычисления выходных отсчетов КИХ-фильтры используют сложение примерно так же, как мы используем сложение в процессе усреднения. И действительно, усреднение представляет собой КИХ-фильтр, что мы можем продемонстрировать 1 Для полноты картины следует заметить, что КИХ-фильтры могут быть реализованы и с использованием рекурсивной схемы, что продемонстрировано в главе 10 — (дрим.
перев.). 5. 1. Введение в КИХ- ильт ы 165 на примере. Допустим, мы считаем количество машин, проходящих по мосту за минуту, и нам необходимо узнать среднее количество машин в минуту за интервал в пять минут; т. е. каждую минуту мы вычисляем количество машин в минуту за последние пять минут. Если результаты подсчета машин за первые десять минут приведены в среднем столбце таблицы 5.1, то среднее количество машин в минуту за предыдущие пять одноминутных интервалов приведено в правом столбце таблицы. Чтобы получить первое среднее значение, мы сложили данные для первых пяти одноминутных интервалов и разделили сумму на пять, ( Ю + 22 + 24 + 42 + 37)/5 = 27.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
