Поточно-рекурсивний пристрій швидкого перетворення фур’є

Изобретение относится к вычислительной технике и может быть использовано в системах цифровой обработки сигналов. Наиболее близким к заявляемому изобретению по технической сущности и достигаемому результату является каскадное устройство для быстрого преобразования Фурье, содержащее последовательно соединенных каскадов, каждый из которых содержит арифметический блок, коммутатор, два элемента задержки, синхронизатор, формирователь тригонометрических коэффициентов, коммутатор и регистр. Недостатком указанного устройства является аппаратная избыточность вследствие 50% загрузки арифметических блоков. Задачей предполагаемого изобретения является сокращение аппаратной избыточности и повышение надежности устройства. В изобретении в устройство, содержащее элемент задержки, функциональных блоков, синхронизатор и формирователь тригонометрических коэффициентов, причем вход элемента задержки и второй информационный вход первого функционального блока является информационным входом устройства, выход элемента задержки подключен к первому информационному входу первого функционального блока, первый и второй информационные выходы функционального блока являются соответственно первым и вторым информационными выходами устройства, первый управляющий выход синхронизатора подключен к управляющему входу каждого функционального блока, адресный выход синхронизатора подключен к адресному входу формирователя тригонометрических коэффициентов, выход коэффициента которого подключен ко входу задания коэффициентов функционального блока, управляющий вход синхронизатора является входом установки устройств, тактовый вход синхронизатора является тактовым входом устройства, введены рекурсивных блоков, первый и второй информационные выходы первого рекурсивного блока подключены соответственно к третьему и четвертому информационным входам первого функционального блока, второй и третий информационные входы первого рекурсивного блока подключены соответственно к первому й второму информационным выходам первого функционального блока, управляющий вход первого рекурсивного блока подключен ко второму выходу синхронизатора, первый и второй информационные входы рекурсивного блока подключены соответственно к первому и второму информационным выходам функционального блока, третий и четвертый входы рекурсивного блока подключены соответственно к первому и второму информационным выходам функционального блока, первый, второй, третий и четвертый информационные выходы рекурсивного блока подключены соответственно к первому, второму, третьему и четвертому входам функционального блока, первый и второй управляющие входы рекурсивного блока подключены соответственно управляющим выходам синхронизатора. На фиг.1 изображена структурная схема устройства; на фиг.2 - структурная схема первого рекурсивного блока; на фиг.3 - структурная схема рекурсивного блока; на фиг.4 - структурная схема функционального блока; на фиг.5 структурная схема синхронизатора; на фиг.6 структурная схема формирователя тригонометрических коэффициентов; на фиг.7 структурная схема устройства для на фиг.8 временные диаграммы, поясняющие работу устройства для Поточно-рекурсивное устройство для быстрого преобразования Фурье содержит: элемент задержки 1, синхронизатор 4, формирователь 5 тригонометрических коэффициентов и последовательно соединенных каскадов, каждый из которых содержит рекурсивный блок и функциональный блок причем вход элемента задержки 1 и второй информационный вход первого функционального блока 3 являются информационным входом устройства, выход элемента задержки 1 подключен к первому информационному входу первого функционального блока первый и второй информационные выходы функционального блока являются соответственно первым и вторым информационными выходами устройства, первый управляющий выход синхронизатора 4 подключен к управляющему входу каждого функционального блока адресный выход синхронизатора 4 подключен к адресному входу формирователя 5 тригонометрических коэффициентов, выход коэффициента которого подключен ко входу задания коэффициентов функционального блока управляющий вход синхронизатора 4 является входом установки устройств, тактовый вход синхронизатора 4 является тактовым входом устройства, первый и второй информационные выходы первого рекурсивного блока 1.2 подключены соответственно к третьему и четвертому информационным входам первого функционального блока 1.3, второй и третий информационные входы первого рекурсивного блока 1.2 подключены соответственно к первому и второму информационным выходам первого функционального блока 1.3, управляющий вход первого рекурсивного блока 1.2 подключен ко второму выходу синхронизатора 4, первый и второй информационные входы подключены второму рекурсивного блока соответственно информационным функционального блока к первому и выходам третий и четвертый входы рекурсивного блока подключены соответственно к первому и второму информационным выходам функционального блока первый, второй, третий и четвертый информационные выходы рекурсивного блока подключены соответственно к первому, второму, третьему и четвертому входам функционального блока первый и второй управляющие входы рекурсивного блока подключены соответственно к управляющим выходам синхронизатора 4. Устройство работает следующим образом. Элемент задержки 1 представляет собой каскадный элемент задержки. Первый рекурсивный блок 1.2 (фиг.2) содержит первый элемент задержки 6, второй элемент задержки 7, третий элемент задержки 8, четвертый элемент задержки 9 и мультиплексор 10. Первый элемент задержки 6 представляет собой каскадный элемент задержки третий и четвертый элементы задержки 8 и 9 соответственно представляют собой каскадные элементы задержки, второй элемент задержки 7 представляет собой -каскадный элемент задержки. При поступлении на первый управляющий вход блока 1.2 логической "1", мультиплексор 10 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и При поступлении на первый управляющий вход блока 1.2 логического "0", мультиплексор 10 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и С выходов и мультиплексора 10 информация поступает соответственно на первый и второй информационные выходы блока 1.2. рекурсивный блок (фиг.3) содержит первый элемент задержки 11, второй элемент задержки 12. третий элемент задержки 13, четвертый элемент задержки 14, пятый элемент задержки 15, шестой элемент задержки 16, седьмой элемент задержки 17, первый мультиплексор 18 и второй мультиплексор 19. Первый, четвертый и пятый элементы задержки 11, 14 и 15 представляют -каскадные элементы задержки Второй элемент задержки 12 представляет собой -каскадный элемент задержки, третий элемент задержки 13 представляет собой -каскадный элемент задержки, шестой и седьмой элементы задержки 16 и 17 представляют собой соответственно каскадные элементы задержки. При поступлении на пятый управляющий вход блока логической "1" (управляющий сигнал мультиплексор 18 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и При поступлении на пятый управляющий вход блока логического "0" (управляющий сигнал мультиплексор 18 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и При поступлении на шестой управляющий вход блока логической "1" (управляющий сигнал мультиплексор 19 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и При поступлении на шестой управляющий вход блока логического "0" (управляющий сигнал мультиплексор 19 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и Информация с выходов и мультиплексора 18 поступает соответственно на первый и второй информационные выходы блока информация с выходов и мультиплексора 19 поступает соответственно на третий и четвертый информационные выходы блока функциональный блок (фиг.4) содержит мультиплексор 20 и арифметический блок который включает в себя сумматор 21, вычитатель 22 и умножитель 23. При поступлении на пятый управляющий вход блока высокого логического уровня управляющего сигнала мультиплексор 20 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и При поступлении на пятый в управляющий вход блока низкого логического уровня управляющего сигнала мультиплексор 20 переходит в состояние, при котором информация, присутствующая на его выходах и передается на его выходы и Сумматор 21 складывает цифровые данные с выходов и мультиплексора 20. Результат суммирования с выхода сумматора 21 поступает на первый выход блока Вычитатель 22 вычитает цифровые данные с выходов и мультиплексора 20. Результат вычитания с выхода вычитателя 22 поступает на вход умножителя 23, на вход которого поступает тригонометрический коэффициент с шестого входа блока Результат умножения с выхода умножителя 23 поступает на второй выход блока Т.о., функциональный блок при поступлении на пятый управляющий вход высокого логического уровня управляющего сигнала выполняет этап (базовую операцию) быстрого преобразования Фурье с данными, поступающими на его первый и второй информационные входы, а при поступлении на пятый управляющий вход низкого логического уровня управляющего сигнала выполняет этап быстрого преобразования Фурье с данными, поступающими на его третий и четвертый информационные входы. Синхронизатор 4 (фиг.5) представляет собой -разрядный двоичный счетчик 24, который делит входную тактовую последовательность, приходящую на первый тактовый вход синхронизатора 4 в раз, формируя на первом выходе синхронизатора 4 управляющие сигналы которые одновременно являются -разрядным адресом тригонометрических коэффициентов поступающим на второй адресный выход синхронизатора 4. Формирователь 5 тригонометрических коэффициентов (фиг.6) содержит n постоянных запоминающих устройств на адресный вход которых поступает -разрядный адрес с входа формирователя 5. Старший разряд адреса высоким логическим уровнем выбирает из постоянного запоминающего устройства тригонометрический коэффициент который соответствует этапу быстрого преобразования Фурье, выполняемому функциональным блоком при высоком логическом уровне управляющего сигнала Под действием низкого логического уровня старшего разряда адреса и постоянного запоминающего устройства выбирается тригонометрический коэффициент который соответствует этапу быстрого преобразования Фурье, выполняемому функциональным блоком при низком логическом уровне управляющего сигнала Тригонометрические коэффициенты с выходов постоянных запоминающих устройств поступают на выход формирователя 5. Алгоритм быстрого преобразования Фурье по основанию 2 с прореживанием по частоте определяется как (Л. Рабинер, Б. Гоулд, Теория и применение цифровой обработки сигналов. - М.: Мир, 1978. - С.668). - элемент входной последовательности. В целом поточно-рекурсивное устройство для быстрого преобразования Фурье работает следующим образом. Рассмотрим случай для Структурная схема устройства для приведена на фиг.7, а на фиг.8 представлены временные диаграммы выполнения быстрого преобразования Фурье. Устройство содержит два последовательно соединенных каскада, каждый из которых включает в себя функциональный блок 3 и рекурсивный блок 2, а также элемент задержки 1, синхронизатор 4 и формирователь 5 тригонометрических коэффициентов. Размерности элементов задержек рассчитаны по приведенным выше формулам и указаны на фиг.7. Импульсный сигнал "Установка" обнуляет счетчик 24 синхронизатора 4. С приходом на тактовый вход устройства первого тактового импульса после окончания действия импульсного сигнала "Установка", на информационный вход устройства начинает последовательно поступать массив отсчетов сигнала (фиг.8,а). Так как управляющий сигнал (фиг.8,б) имеет низкий логический уровень, то мультиплексор 20 находится в состоянии, при котором информация с третьего и четвертого информационных входов функционального блока 1.3 вводится в арифметический блок A. Следовательно, первые восемь отсчетов вводятся в восьмикаскадный элемент задержки 1, то есть происходит начальная загрузка. Следующие восемь тактов управляющий сигнал (фиг.8,б) имеет высокий логический уровень, следовательно мультиплексор 20 находится в состоянии, при котором информация с первого и второго информационных входов функционального блока 1.3 поступает соответственно на его выходы и Таким образом, в арифметический блок одновременно вводятся задержанная и прямая части последовательности входного сигнала (фиг.8,в). Под действием высокого логического уровня управляющего сигнала в арифметический блок вводится тригонометрический коэффициент соответствующий выполнению первого этапа быстрого преобразования Фурье. Результаты первого этапа с первого информационного выхода и (фиг.8г) с второго информационного выхода функционального блока 1.3 парами поступают соответственно на второй и третий информационные входы рекурсивного блока 1.2. Размерности элементов задержек 6, 7, 8 и 9 и частота переключений мультиплексора 10 под действием управляющего сигнала (фиг.8д) выбраны в соответствии с выше приведенным алгоритмом т.о., чтобы формировать на первом и втором информационных выходах рекурсивного блока 1.2 данные (фиг.8е), которые соответствуют выполнению второго этапа быстрого преобразования Фурье. Информация с первого и второго информационных выходов рекурсивного блока 1.2 при низком логическом уровне управляющего сигнала вводится в арифметический блок куда поступает тригонометрический коэффициент соответствующий выполнению второго этапа быстрого преобразования Фурье. Результаты второго этапа (фиг.8,ж) поступают соответственно на первый и второй информационные входы рекурсивного блока 2.2. Размерности элементов задержек 11, 14 и 15 и частота переключений мультиплексора 18 под действием управляющего сигнала (фиг. 8,з) выбраны в соответствии с выше приведенным алгоритмом. Таким образом, чтобы формировать на первом и втором информационных выходах рекурсивного блока 2.2 данные (фиг.8,и), которые соответствуют третьему этапу выполнения быстрого преобразования Фурье. Под действием высокого логического уровня управляющего сигнала информация с первого и второго информационных выходов рекурсивного блока 2.2 вводится в арифметический блок функционального блока 2.3, куда поступает тригонометрический коэффициент соответствующий выполнению третьего этапа быстрого преобразования Фурье. Под действием высокого логического уровня управляющего сигнала результаты третьего этапа (фиг.8,и) поступают на третий и четвертый информационные входы рекурсивного блока 2.2. Размерности элементов задержек 12, 13, 16 и 17 и частота переключений мультиплексора 19 под действием управляющего сигнала (фиг.8,к) выбраны в соответствии с выше приведенным алгоритмом таким образом чтобы формировать на третьем и четвертом информационных выходах рекурсивного блока 2.2 данные, которые соответствуют четвертому этапу выполнения быстрого преобразования Фурье (фиг.8,л). Под действием низкого логического уровня управляющего сигнала информация с третьего и четвертого выходов рекурсивного блока 2.2 вводится в арифметический блок функционального блока 2.3, куда поступает тригонометрический коэффициент соответствующий выполнению четвертого этапа быстрого преобразования Фурье. Результаты четвертого этапа (фиг.8,м) с первого и второго информационных выходов функционального блока 2.3 посыпают соответственно на первый и второй информационные выходы устройства. Применение поточно-рекурсивных устройств быстрого преобразования Фурье позволяет на 50% уменьшить физическое число сумматоров и умножителей по сравнению с известными устройствами (Л. Рабинер, Б.Гоулд. Теория и применение цифровой обработки сигналов. - М.: Мир, 1978). Так, например, 16-разрядный умножитель К1518ВЖ1 потребляет 1,0А тока. Для вычисления быстрого преобразования Фурье известными устройствами для необходимо число блоков равное Это потребует 40 умножителей (4 действительных умножения равны одном комплексному умножению). Для поточнорекурсивных устройств что потребует 20 умножителей и соответствует экономии 20А тока, а также способствует уменьшению габаритов аппаратуры и повышает ее надежность (следствие уменьшения числа деталей). Меньшую экономию тока дает сокращение числа сумматоров, но это существенно увеличивает надежность и габариты аппаратуры. Достоинством предлагаемого изобретения является также расположение линий задержек перед функциональными блоками, что позволяет собрать их в один блок.