10.13. Поточная схема БПФ с основанием 4

Основываясь на алгоритме фиг. 10.14, можно разработать поточную схему для выполнения 64-точечного БПФ с основанием 4. Рассмотрим сначала случай обработки единственного массива из 64 отсчетов, следующих в нормальном порядке. Оказывается, что поточная схема с основанием 4 является в этом случае весьма неэффективной, так как арифметические устройства будут заняты только четверть всего времени. Тем не менее данный пример позволяет проанализировать всю интересующую нас структуру, так как многие выводы будут справедливы и для систем со 100%-ной эффективностью. Достижение такой эффективности фактически связано с решением задачи накопления входных отсчетов в буферном ЗУ, рассматриваемой ниже применительно к различным вариантам ввода обрабатываемых данных. На фиг. 10.30 представлена блок-схема поточного процессора БПФ с основанием 4. В целом она аналогична схеме, соответствующей основанию 2, но все основные блоки (АУ, схемы задержки и коммутаторы) рассчитаны на выполнение алгоритма БПФ с основанием 4. Так, в АУ выполняются не два комплексных сложения и одно комплексное умножение, как при основании 2, а восемь комплексных сложений и три комплексных умножения. Коммутатор имеет четыре входа и четыре выхода, причем в трех из четырех линий передачи данных имеются элементы задержки.

На фиг. 10.31 показано, каким образом входная последовательность  распределяется между четырьмя входами первого АУ. Исходные отсчеты изображаются отрезками вверху. Через каждые 16 тактов коммутатор переходит в следующее положение, поэтому последовательные группы из 16 отсчетов поступают в АУ с неодинаковыми задержками. Начиная с 48-го такта, отсчеты  и  одновременно появляются на входе первого АУ, а после 63-го такта операции первого этапа алгоритма фиг. 10.14 заканчиваются. Отметим, что АУ было занято только в течение 16 тактов из 64.

Фиг. 10.30.  Поточная схема выполнения 64-точечного БПФ с основанием 4.

Фиг. 10.31. Разделение массива из 64 отсчетов на 4 подмассива по 16 отсчетов при  выполнении базовой операции с основанием 4.

Выполнение остальных операций алгоритма можно проследить с помощью фиг. 10.32. Каждая из четырех параллельно обрабатываемых последовательностей проходит через все АУ. Отметим, что во всех коммутаторах переключения производятся по одинаковому графику. Проще всего это проследить на примере коммутатора , для которого показаны положения всех переключателей. «Цикл переключения» фактически представляет собой последовательность из четырех различных состояний коммутатора. Эта последовательность периодична. Начальный и конечный участки графика легко отождествить с основной последовательностью из четырех состояний, заметив, что из-за краевых эффектов некоторые состояния коммутатора не используются. Работа коммутатора  в действительности описывается тем же графиком, только в данном частном случае краевые эффекты преобладают. Отсюда можно заключить, что в установившемся режиме, когда АУ работают без пауз, все коммутаторы повторяют цикл переключений, изображенный для коммутатора , но каждый последующий коммутатор переключается в четыре раза чаще предыдущего.

Отметим также, что отсчеты на выходе появляются во времени в том же порядке, в каком они поступали на вход, а это означает, что по частоте гармоники будут расположены в четверично-инверсном порядке (см. разд. 10.3).

Порядок переключений при выполнении БПФ четырех перекрывающихся массивов показан на фиг. 10.33. В установившемся режиме одна и та же последовательность отсчетов, поступающая в реальном времени, всегда подается на все четыре линии системы. Чтобы избежать краевых эффектов, первые три подпоследовательности подключаются постепенно. Но по достижении установившегося режима коммутатор  фактически становится не нужен, так как входная последовательность постоянно подается на все четыре линии системы. Если же для удобства потребовать, чтобы коммутатор  переключался   стандартным   образом   (согласно фиг. 10.32), то обработка с перекрытием будет обеспечиваться, если входную последовательность подавать сразу на все четыре входа коммутатора . Представляется естественным, что система с основанием 4 имеет 100%-ную эффективность при выполнении БПФ массивов с четырехкратным перекрытием, однако неясно, можно ли сохранить эту эффективность при обработке в реальном времени массивов с двукратным перекрытием.

Фиг. 10.32. Временные   диаграммы   и   работа   переключателей   в   поточном блоке 64-точечного БПФ с основанием 4 (см. фиг. 10.14).

Фиг. 10.33. Одновременное  выполнение  четырех  БПФ  в   поточном  блоке БПФ с основанием 4.

Фиг. 10.34. Вариант   входной   части   устройства,   позволяющий   получить 100% -ную эффективность при двукратном перекрытии сигналов.

На этот вопрос можно ответить утвердительно, но входные буферный накопитель и коммутатор должны быть при этом несколько видоизменены. Соответствующая схема приведена на фиг. 10.34. ЗУ, использовавшееся при выполнении первого этапа в схеме фиг. 10.30, заменено здесь блоком памяти объемом  с одним входом и шестью выходами. В течение первых 64 тактов первые  отсчетов последовательно поступают во входной буферный накопитель, но не обрабатываются. Начиная с отсчета с номером 64, коммутатор устанавливается так, что верхние четыре выхода буферного накопителя подключаются к АУ1, и с них с частотой, в два раза меньшей частоты следования входных отсчетов, начинают поступать данные для обработки. Таким образом, пока на 32-тактном интервале времени в буферный накопитель вводятся два новых подмассива, четыре уже накопленных подмассива считываются в АУ1. Следовательно, 100%-ная эффективность поддерживается за счет двукратного «растягивания» сигнала. Вообще следует ожидать, что по сравнению со случаем четырехкратного перекрытия здесь за единицу времени можно осуществить вдвое больше операций по обработке сигнала. В качестве упражнения предлагаем составить схему буферного накопителя для случая, когда обрабатываемые массивы перекрываются только на  отсчетах, т. е. первый массив содержит отсчеты с 0-го по -й, второй — отсчеты с -гo по -й и т. д., так что выполнение каждого нового БПФ по  отсчетам начинается через  тактов.

Фиг. 10.35. Входная часть поточной схемы БПФ С основанием 4 для обработки четырех  независимых сигналов.

С помощью поточной схемы БПФ с основанием 4 можно найти БПФ четырех различных сигналов: . Для этого последовательность переключений коммутатора на первом этапе должна быть такой же, как у коммутатора на следующем этапе. Соответствующая блок-схема приведена на фиг. 10.35. Заметим, что входные последовательности задерживаются относительно друг друга на  отсчетов. Начиная с четвертого интервала длиной в  отсчетов, режим переключений устанавливается и повторяется через каждые  отсчетов. До известной степени обработка четырех независимых сигналов является для поточной системы с основанием 4 наиболее естественным режимом, потому что графики переключений во всех коммутаторах (включая и первый) становятся одинаковыми с той лишь разницей, что каждый последующий коммутатор переключается в четыре раза чаще.