Кловский Д.Д. и др. Теория электрической связи (1999) (1151853), страница 100
Текст из файла (страница 100)
Пусть дискретный финитный сигнал на интервале своей периодичности определяется четырьмя отсчетами: 1, — 1, О, О. Тогда согласно (10.8) С,= 0; С, = 0,25(1 4 1); С, = 0,5; С, = 0,25(1- 1) и согласно (10,10) на интервале периодичности 44=~С/ ( — ", лс),)с( ("' ° ~с)к = 0,5к/2 — + — + 0,5 При вычислении Л/ коэффициентов ДПФ согласно (10.8) или ОДПФ согласно (10.11) надо выполнить /1/' наиболее трудоемких операций умножения. При больших массивах /у' (порядка 1000 и более) использование таких алгоритмов ДПФ и ОДПФ в реальном масштабе времени затруднительно из-за ограниченного быстродействия вычислительных устройств. Положение существенно изменилось, начиная с 60-х годов, с разработкой алгоритмов быстрого преобразования Фурье (БПФ), которые сводят обработку заданного массива данных к обработке массивов с меньшим числом членов, и тем самым существенно уменьшается (при больших /т) требуемое число операций умножения. Из (10.12) видно, что последовательности коэффициентов С„', и С' „обладают свойством периодичности с периодом Ф/2: (10,13) Кроме того, для я > Ф/2 множитель 1г» в (10.12) можно представить я', з = е '" Ю» = -П»", я = О, 1, 2, ..., Ф/2 — 1.
(10.14) С учетом (10.12), (10.13) и (10.14) можно написать для всех п = 0,1,2,...,/»" — 1 (10.15) причем знак "-" соответствует значениям п = Ау2, Ф/2 + 1, ..., Ф-1. Подсчитаем, сколько требуется операций умножений при вычислении всех значений С„Ф по алгоритму (10.15). Для вычисления всех С„'„по (10.12) требуется (М/2) умножений.
Столько же умножений потребуется для вычисления всех Сс,. Кроме того, потребуется %умножений С„', на числа ~И». Следовательно, всего потребуется 2(У/2) +У умножений. При больших 1» требуемое число ,,гг умножений — = Ф1ой, М (при Ф = 4), что в 2 раза меньше, чем по алгоритму (10.8). г Четные отсчеты исходной последовательности х~„е,® (их всего Ф/2) разобьем далее на втором этапе разбиения на четные и нечетные компоненты хп(2») и хп(2/с + 1) (их число равно М/4).
ДПФ последних обозначим Сп„и Сп „. Тогда можно написать (10.16) Аналогичное разбиение выполняется над нечетными отсчетами исходной последовательности х~„,„®. Для вычисления всех С „М согласно формулам типа (10.1б) ( по массиву дан- ных х~„гт(7с) и х,(й)) понадобится число умножений 2.~2.~ — ~ + — ~2 — =Ф(айза (при 1. и 4) 2/ 4 Ф = 8).
Процесс разбиений можно продолжить г раз до тех пор, пока не получится последовательность из одного элемента, ДПФ которого совпадает с самим элементом. Далее надо собрать результаты отдельных разбиений для вычисления суммарных значений С„Ф. Анализ показывает, что число операций умножения, необходимых для выполнения БПФ, не больше чем Ф х г = Ж1о8зАГ, что при больших Ф существенно меньше, чем М'.
БПФ по рассмотренному методу (его называют методом лрорежива»ия отсчетов во времени) осуществляют, как правило, в следующем порядке. Сначала для получения желательного при обработке сигнала порядка следования отсчетов х(/с)„х = О, 1, ..., 1»' — 1, выполняется двоично-инверсная перестановка элементов исходной последовательности хЯ, 1= О, 1, ..., )У вЂ” 1. Для этого записывакгг.порядковые номера элементов х(1) в двоичном коде и инвертируют порядок следования разрядов. Новый порядок следования элементов х(й) определяется номерами, полученными после инверсии разрядов. Новый порядок следования элементов: х(0), х(2), х(1), х(3).
После этого поступают так. На Оервом этапе вычислений определяют 2 точечные ДПФ "новой" последовательности х(х), обьеднняя попарно элементы этой последовательности. На втором этапе из 2 точечных ДПФ получают 4 точечные ДПФ, пользуясь основной базовой операцией данного метода (см. ниже). Затем 4 точечные ДПФ обьединяют в 8 точечные и тд.
Базовые операции показывают, как два входных числа А и В объединяются для получения двух выходных чисел Х и У. Для метода прореживания во времени базовая операция имеет вид 385 С(0) 4 х(0) А Х =А+И „'В н" в и Г =А-(Р„"В С(1).4 х(2) х(1) С(2) . 4 Рис.10.4. Операция "бабочка", используемая «(3) С(3).4 прн реализации алгоритма БПФ Рис.10.5. Граф лля вычисления БПФ при Я=4 (10.17) У = А — И'лв.)' Базовая операция (10.17) изображается на рисунке "бабочкой" (см. Рис.
10.4) Надпись И'~ у стрелки, идущей вверх, означает умножение И'", на величину В. При вычислении 2 точечного ДПФ й = 0 и выходные числа Х и У определяются без операции умножения Х = А + В, У = А — В. Пример. Построим граф вычисления БДПФ с прореживанием во времени для гх'= 4 (рис. 10.5) я Учитывая, что И4 —— 1, В4 = Е ' =-), получаем согласно приведенному графу О 4С(0) = «(0) + х(2) + х(1) + х(3); 4С(1) = х(0) — х(2) — 3(х(1) — х(3)); 4С(2) = х(0)+ х(2)-х(1)+ х(3); 4С(3) = х(0)- х(2)+ 1(х(1)- х(3)). На рис. 10.6 дан граф вычисления БДПФ с прореживанием во времени для Ж = 8. Чтобы воспользоваться рассмотренной процедурой БДПФ для выполнения ОДПФ, запишем (10.11) в виде (л -г, зьы'1 «(~)=~",О С.Е'О ! .
(10. 18) и 0 * Вводя массив данных С„(вместо х(л)), можно найти сумму в (10.18) по изложенной выше методике БДПФ, а затем для нахождения х® найти комплексно-сопряженное значение полученного результата. Существуют и другие методы вычисления БДПФ (другие методы группирования исходных данных х()О) [24,101). х(0) ВС(0) ВС(() х(4) ВС(2) х(2) ВС(3) х(6) х(1) ВС(4) х(5) ВС(5) х(3) ВС(6) ВС(7) х(7) Рнс.! 0.6. Граф лля вычисления БДПФ прн И=В 386 10.3.
ВРЕМЕННЫЕ И СПЕКТРАЛЬНЫЕ МЕТОДЫ ИССЛЕДОВАНИЯ ЛИНЕЙНЫХ СТАЦИОНАРНЫХ ЦИФРОВЫХ ФИЛЬТРОВ (10.20) (10.23) 387 Подобно тому как отклик аналоговой линейной стационарной системы у(~) на произвольное внешнее воздействие к(О можно найти или через временную (импульсную ДГ)) характеристику системы (т.е. интегралом Дюамеля или сверткой функций кф и я(~) ) у(с) = ) х(т)фт-т)с(т, (10.19) или спектральным методом (см. й 4.5), и отклик линейного стационарного ЦФ у(л) на произвольное внешнее воздействие к(п) можно найти или через им- пульсную характеристику ЦФ й(п), или спектральным методом.
Выполнив в (10,19) дискретизацию по переменным т и ~, положив т = ка, Г = тА, получаем цифровой аналог свертки (10.19): у(т) = А ~х(сс) у(т — 1с), где ф/), 1= О, 1, 2, ..., Е, — отсчеты импульсной характеристики ЦФ, т.е. от- клика на единичный импульс (1, О, О, О, О, ...), поступающий на вход фильтра в момент ~ = О. Из условий реализуемости ЦФ надо принять я(-Г~ = О, 1 = 1, 2, ...
(10.21) Если входные отсчеты к(Ус) начинают поступать в момент т = О, то (10.20) можно написать: О О у(т) = А~~~,х(й) у(т- А) = АЯЯс)х(т- й) . (10.22) г-0 г-0 С учетом условия реализуемости ЦФ (10,21) ясно, что суммирование в (10.22) фактически выполняется для /с < т: у(т) = АХИ) г(т-~) г а Если число входных отсчетов к(0), к(1), „к(У- 1) равно У, а число отсче- тов импульсной характеристики ЦФ (й(0), й(1), ..., я(Е)) равно Е + 1, то в (10.23) т принимает значения О, 1, 2, ..., Ф вЂ” 1 (М = У+ Ь). Для нахождения одного значения у(т) в соответствии с (10.23) надо выпол- нить не более чем Е + 1 операций умножения, для нахождения всех значений у(т) надо выполнить примерно Лс,(Е+ 1) операций умножения.
Число операций можно существенно сократить, если использовать спектральный метод расчета ЦФ и методы БПФ. Чтобы это показать, напишем сначала дискретную свертку (10.23) в нормированном виде: у(т) = — ~г(/с)Х(е — /с) . 1 Уе-1 (10.24) х гм> Дополнив последовательность из Ф входных отсчетов х(сс) Х, нулями, представим х(сс) че- рез" ОДПФ: лг-с гам х(~) = ~„ с, е "' . (10.25) А О Дополнив последовательность из г, + 1 отсчетов импульсной характеристики ЦФ Ф- 1 нулями, определим ОДПФ: (10.27) 10.4. ИСПОЛЬЗОВАНИЕ х-ПРЕОБРАЗОВАНИЯ В ТЕОРИИ СТАЦИОНАРНЫХ ЛИНЕЙНЫХ ЦИФРОВЫХ ФИЛЬТРОВ Это преобразование можно получить из преобразования Лапласа или Фурье дискретного сигнала хд(1).
Определим одностороннее преобразование Лапласа (для сигналов, определенных при 1> О) для дискретного сигнала (10.1): л 4Ф Р, (р)=~ х,(1)е "А=А~О х(1г)е (10.31) о оо При р = )са из (10.31) следует преобразование Фурье дискретного сигнала. Если обозначить х=е', (10.32) то преобразование Лапласа (10.31) переходит в д-преобразование дискретного сигнала хд(1): Ю Х(г) = ~~ х(1с)г (10.33) 1 О Очевидно, что из преобразования Фурье дискретного сигнала хд(1) при 2 = Е""' (10.34) следует также г-преобразование Х(г).
" при четном с11 можно утверждать, что при л ~ 1для каждого слагаемого суммы (10.28) суще- ствует противоположная компонента. 388 я( -С)=,'~,'С„Е" (10.2б) с-о где С 2 — коэффициенты ДПФ для импульсной характеристики ЦФ. Подставив (10.25) и (10.26) в (10.24), получим сое 1осе 1 2лсю Осе-1 .221(л-с) у(т)= — ~ ~ С, СО2е Е ~ е х осо М О=О Справедливо условие Ос-! .2ло( О Г Лс а 1 Х~ " (10.28) 1 О Равенспю суммы с11 при л = 1 очевидно.
Равенство же суммы нулю при лсл1 объясняется тем, что в этом случае имеем векторную сумму единичных векторов, образуюших в совокупности замкнутый правильный с1С-угольник. Сумма эта, естественно, равна нулю'>. С учетом (10.28) формула (10.27) принимает вид ЬЕ 1 ,2ллею у(т)= ~Г С,„С „Е "' (10.29) л=о Уравнение (10.29) определяет ОДПФ выходных отсчетов ЦФ, если ДПФ над этими отсчетами определяется произведением ДПФ входных отсчетов и отсчетов импульсной характеристики фильтра: (10.30) Если методами БПФ найти спектральные компоненты С„„и С „, а затем и ОДПФ от их произведения С „= С,„С „, то можно при больших со" существенно экономить в вычислительных операциях по сравнению с непосредственными вычислениями у(т) по формуле дискретной свертки.
е 1 1 прогрессию со знаменателем и = †. Тогда Х(г) — —— Е 1-и г-Е 1-Е Эта функция имеет нуль в точке х = 0 и полюс в точке г = е ~, т.е. вне области сходи- мости. Для нахождения х(1с) по Х(г) (обратного г-преобразования) умножим левую и правую часть (10.33) на г" '. Х(г)г" ' = ~~~,х(Й)г" ' (10.36) ь О Возьмем от левой и правой части (10.36) интеграл по х по замкнутому контуру в области аналитичности, охватывающей все полюсы функции Х(г)г" '. Получим результат2) 1 х(п) = —,~Х(г)г" 'пг. 2зг1 Он следует, если при интегрировании левой части (10.36) использовать соотношение (вытекающее из теоремы Коши при интегрировании функций комплексного переменного г): ~х~, (10.38) Важное свойство г-преобразования связано со сдвигом сигнала во времени: У(г)=г 'Х(х), если у(Й) = х(Й вЂ” 1).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
