Калабеков Б.А. Микропроцессоры и их применение в системах передачи и обработки сигналов (1988) (1092085), страница 60
Текст из файла (страница 60)
8.3. ДИСКРЕТНОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ Вычисление выражения (8.3) не может быть реализовано, так как в нем предусматривается суммирование бесконечного числа членов. При решении практических задач используется конечное число Ф отсчетов аналогового сигнала и, следовательно, в выражении (8.3) может производиться суммирование конечного числа членов. В этом случае пара преобразований Фурье принимает вид так называемого дискретною преобразования Фурье (ДПФ): ! у »! — ! ! у Л вЂ” ! Х(й) = — к~! х(пТ) е оа "»!" = — чт' х(пТ) (и' ». .ч сы й! л о »=о й=О, 1,... )и' — 1; (8.5) х (пТ) = ~ Х (А) еУ»и"»!" = ~Р Х (й) )й'-"» п = О, 1,„, )т' — 1, (86) » о »=о Здесь 1)г""» = е — !'и"»/".
Выражение (8.5) определяет прямое дискретное преобразование Фурье (ДПФ), выражение (8.6) — обратное дискретное преобразование Фурье (ОДПФ). Рассмотрим различие в результатах, получаемых при пользовании выражениями (8.3), (8,4) и (8.5), (8.6), В случае ДПФ предполагается, что исходная функция х (пТ) является периодической с периодом НТ; в силу чего для суммирования в (8,5) из последовательности х(аТ) выбираются значения в пределах одного периода (рис.
8.7, а). Тогда в силу сформулированных в 8 8.2 свойств преобразования Фурье дискретность функции х (пТ) приводит к периодичности спектральной функции Х (А), а так как функция х (пТ) принимается периодической, то спектральная функция Х (й) оказывается дискретной. Следовательно, в случае ДПФ результат Рис. 82. Дискретиый периодический сиги»а (и) и его спектр (б) 12к преобразования всегда будет периодической и дискретной функцией, и, таким образом, первые М/2 — ! точек Х (/г) определяют спектральные составляющие на положительных частотах, следующие М/2 — 1 точек соответствуют спектральным составляющим прн отрицательных частотах (рис. 8.7, б).
Перейдем к рассмотрению алгоритма ДПФ и ОДПФ. Оба преобразования можно вычислить с помощью одного и того же алгоритма. Для этого используется выражение Ю вЂ” ! А (й) ~~ и (и) )Рлй вс а й= — О,1, ..., М вЂ” 1. (8.7) Для прямого ДПФ а(п) = х(пТ), а искомое Х (й) =- — А (й); при вычислении 1 М обратного ДПФ а(п) = Х (М вЂ” л), п =— = 1, 2, ..., М вЂ” 1; а (О) = Х (О), а искомое х (АТ) = А (й). Таким образом, для вычисления ДПФ и ОДПФ можно пользоваться единым алгоритмом, предусматривающим расчет по алгоритма (8.7) .
Схема такого алгоритма приведена на рис. 8.8. Рис, В.В, Схема ДПФ и ОДПФ 8А. БЫСТРОЕ ПРЕОБРАЗОВАНИЕ ФУРЬЕ 340 Представленный на рис. 8.8 алгоритм дискретного преобразования Фурье предусматривает большой объем вычислений. Для вычисления одного значения А (й) требуется М-кратное повторение внутреннего цикла и, таким образом, выполнение М умножений (в общем случае выполняемых над парами комплексных чисел). А для нахождения М значений А (л) потребуется М-кратное повторение внешнего цикла и количество умножений будет равно Мз. Этот алгоритм содержит большое количество избыточных операций, в том числе и таких, когда одни и те же операции многократно выполняются над одними и теми же значениями величин.
Это связано со следующим. Весовая функция 1(г ' = е-1'" 'l" является периодической функцией аргумента пй. Так как и и й принимают значения из последовательности 0,1, ..., М = 1, то произведение и й, принимающее значения 0,1, ., (М вЂ” 1)', будет содержать большое число периодов М и соответствующие им значения весовой функции Ф' ' будут повторяться через период М. В табл. 8.2 это показано для М = 8. В пределах одного периода первые й//2 значений Я/"ле отличаются от вторых /У/2 значений лишь знаком. Действительно, )вгв=е /гл'в/е=е-/ллл — 1= — )У/е (8.8) Ф"е = е /гл'е/е = е !л е /гл !/е )у/2 и т.
д. Устранение избыточных операций умножения приводит к так называемому алгоритму быстрого преобразования Фурье (БПФ). Рассмотрим один из способов построения алгоритма БПФ, называемый способ прореживания по времени, Считая, что й/ делится на 2, представим (8.7) двумя суммами, соответствующими четным и нечетным значениям и: К вЂ” ! Н/2 — ! А (й) ~~Р а(П) Š— /глел/Н ~ а(2П) Š— /глг,ь/Н4 л О л=е У/2 — 1 М/2 а (2П 1 1) Š— /2л!2л+ !!Е/М ~;1 а (2П) Š— /2л2ль/Н л=ь л=ь М/2 — ! Н/2 — ! +е /2™/и ~ч,", а (2п+ 1) е /глглв/л ~ч~~~ а (2п) )е/гав+ л=ь а=О н/г — ! + )еге ~ч', а (2п + 1) )вггл" = В (й) + )в/О С (й), (8.9) л=а Таблица 8.2 ль 0 3 4 !ве вгв 2ве — 2ве 34! где В (й) и С (й) — суммы соответственно первого и второго слагаемых.
Таким образом, вычисление /е/-точечного преобразования А (й), й = 0,1, ..., й/ — 1, можно произвести путем вычисления двух й//2- точечных преобразований: В (й), й =0,2, ..., /в/ — 2 и С (й), й= 1,3, ..., /в/ — 1, с последующим их объединением по формуле (8.9).На рис.
8.9, а показан этот прием для /в/ =- 8. Такая же схема, но использующая соотношения (8.8) для сокращения числа умножений при объединении двух 4-точечных преобразователей, показана на рис. 8.9, б. Прямое вычисление й/-точечного преобразования требует й/2 комплексных умножений, при рассмотренном приеме прямое вычисление двух й//2-точечных преобразований потребует 2 (й//2)2 = /О'2/2 комплексных умножений, а их объединение — еще /е'/2 умножений. Таким образом, количество умножений станет равным (/2'+ й/2)/2, что при больших /!/ примерно вдвое сокращает требуемое количество умножений, а(а) А(а) я(т) а(2) А(г) а(4) А(5) а(б) а(з) А(4) А(5) а(5) а(5) Я (б) А(7) а (7) я(а) а(о) ЯП) а(2) а(4) Я!2) а(б) А(5) А(4) а(В а(5) А(5) а(5) А(В) а(7) Я (7) Рнс.
8.9. Восьмиточечное ДПФ, представленное через два четырехточечных ДПФ (а) и сокращение числа умножений нри объединении двух четырехточечных ЛПФ (б) 342 Если Л//2 в свою очередь делится на 2, то вычисление каждого из преобразований В (А) и С (/г) можно также свести к двум й//4-точечным преобразованиям, что вызовет дополнительное уменьшение требуемого количества операций умножения н т. д. На рис. 8.10 показано сведение 8-точечного преобразования к четырем 2-точечным, на рнс. 8.1!в полная схема вычислений, в которой дополнительно показаны вычисления, требуемые для 2-точечных преобразований. Если М представляется целой степенью двух (й/ = 2'"), то вычисления разбиваются на т = !од, й/ этапов, в каждом из которых требуется й//2 умножений.
Таким образом, общее количество умножений равно — !ой, /У. Например, при о/ = 2" = 1024-точечном преобразо- Ф ванин число умножений окажется равным 0,5 1024 10 ж 10~/2, в то время как при й/ = точечном ДПФ потребовалось бы й!' т 10' операций умножения. Как видим, БПФ обеспечивает существенное сокращение (в данном примере в 200 раз) объема вычислений. Следует обратить внимание на то, что исходные отсчеты подаются на входы преобразователя не в естественном порядке (на рис. 8.11 эта последовательность: а (0), а (4), а (2),...). Для получения номеров отсчетов в требуемой последовательности необходимо номера отсчетов, следующих в естественном порядке, представить в двоичной системе счисления, а затем в каждом из этих двоичных представлений переставить разряды, записав их в обратном (так называемом дзоичио-инверсном) порядке: естественный порядок 000 001 010 011 100 101 110 111 двоично-инверсный порядок 000 100 010 110 001 101 011 111 (0) (4) (2) (б) (1) (5) (3) (7).
Убеждаемся, что полученная последовательность входных отсчетов соответствует приведенной на рис. 8,11. Рассмотрим способы выполнения перестановок элементов массива в соответствии с двоично-инверсным порядком следования. Пусть имеются два т-разрядных регистра Д, и й, (рнс. 8.12,а). Поместим в регистр Я, порядковый номер входных данных, представленный т-разрядным двоичным числом. Эатем проведем серию сдвигов содержимого регистров й, и Й„причем содержимое регистра Д, будем сдвигать вправо, а содержимое регистра К, — влево, выдвигаемое при сдвиге содержимое младшего разряда регистра Й, будем передавать в младший разряд регистра й,. После т-кратного повторения таких сдвигов в й, образуется двоично-инверсный номер.
На рис. 8.12, б показана схема алгоритма выполнения перестановок для получения двоично-инверсного порядка следования элементов массива. Другой более быстрый алгоритм таких перестановок представлен на рис. 8.13. Предлагаем самостоятельно, задавшись значением Ж числа элементов в массиве, проследить выполняемые в последнем алгоритме операции и убедиться в том, что оии действительно приводят к образованию двоично-инверсной последовательности элементов.
010) ага) а (2) а® ам) 0 05) а(5) аР) Рис. 8.10. Восьмиточечное ЙПФ, представленное через четире двухточечных ЛПФ ага) аег) ае2) аг5) ага) аЮ аЮ а(7) Рис. В.11. Полнея схема восьмиточечного БПФ Результаты вез зтала аезулетатлг 2-ее зтала результаты з-еа зтала Рис, 8Л2. Перестановки элементов массива в соответствии с двоична-инверсным порядком следования: и> схема формврпввиия двпнчнп.инверсных номеров; б) схеме епгоритмв пепучеви» лвеич. пе.вявереипге порядке следования Обратимся к рис.
8.11 и рассмотрим, какая емкость требуется для хранения исходных данных, промежуточных и конечных результатов БПФ. Как мы видели выше, двоично-инверсная последовательность получается путем перестановок пар элементов, производимых в исходной последовательности. Такие перестановки можно осуществлять непосредственно над содержимым ячеек, хранящих данные исходной последовательности. Таким образом, получение двоично-инверсной последовательности не требует использования дополнительного массива ячеек памяти, она формируется в том же массиве ячеек, в котором хранилась исходная последовательность. В процессе выполнения БПФ (рис. 8.11) на любом его этапе результат вычисления соответствующих пар значений А' (р) и А ' (д) получается путем использования только значений А (р) и А (д), которые берутся из результата предыдущего этапа преобразований (рис.
8.14, а). Поэтому для хранения вычисленных значений А' (р) и А' (д) не обязательно использование новых ячеек памяти, эти значения можно помещать в ячейки, хранившие результаты предыдущего этапа А (р) и А (и). Соответственно, результаты, получаемые в ходе 1-го этапа преобразования, могут помещаться на место элементов двоично-инверсной последовательности. Этот принцип использования памяти отражен иа рис.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
