Устройство для реализации быстрого преобразования Фурье последовательности с нулевыми элементами Советский патент 1984 года по МПК G06F17/14 

сдвига, инверсный выход первого элемента И подключен ко второму входу второго элемента И, выход которогб подключен ко второму установочному входу .триггера, инверсные выходы от второго дд (ri-l)-ro разрядов, регистра сдвига подключены к первому входу сумматора, выход которого соединен с информационным входом регистра хранения, информационный выход которого подключен ко вторым информационным входам коммутаторов второй группы и соединен со вторым входом сумматора, выход п-го разряда регистра сдвига подключен к управляющему входу блока памяти коэффициентов, информационный выход коммутатора подключен к управляющим входам арифметического блока и блока оперативной памяти.

УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ ПОСЛЕДОВАТЕЛЬНОСТИ С НУЛЕВЫМИ ЭЛЕМЕНТАМИ, содержащее блок оперативной памяти, ари4 1етический блок, блок памяти коэффициентов, блок управления, причем вход операндов арифметического блока соединен с информационным выходом блока оЛеративной памяти,- вход коэффициентов арифметического блока соединен с информационным выходом блокапамяти коэффициентов, информационный выход арифметического блока является информационным выходом устройства, отличающееся тем, что, с целью повышения быстродействия, в него введены счетчик занесения, триггер, первая и вторая группы коммутаторов, причем информационньй выход арифметического блока подключен к первьм информационным входам коммутаторов первой группы, вторые информационные входы которых .являются информационными входами устройства, управляющие входы коммутаторов первой и второй групп объединены и подключены к выходу триггера, параллельньй выход счетчика занесения подключен к первым информационным входам коммутаторов второй группы, первый установочный вход триггера соединен с последовательным выходом счетчика занесения, выходы коммутаторов первой группы подключены к информационному входу блока оперативной памяти, адресный вход которого подключен к вьпсодам коммутаторов второй группы, причем блок управления содержит коммутатор, регистр сдвига, счетчик, первый и второй элементы И, элемент ИЛИ, сумматор, регистр хранения, причем вход сброса и тактовый сл вход счетчика соединены соответственно с выходом триггера и тактовьм входом счетчика занесения, тактовый вход которого является тактовым входом устройства, вход сброса счетчика Соединен с установочным входом ре- гистра сдвига, выход первого разряда счетчика подключен к тактовому о вхЬду регистра сдвига, выходы разрядов, кроме второго разряда, счетчика подключены к информационному входу Oi коммутатора, управляющий вход которого соединен с выходами от первого до (h-l)-ro разрядов регистра сдвига, выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистра хранения, выходы разрядов, кроме второго разряда, счетчика соединены соответственно со входами элемента ИЛИ, выход которого подключен к первому входу первого элемента И, второй вход которого соединен с инверсным выходом ( )-го. разряда регистра

Изобретение относится к вычислительной технике и может быть цспользованов устройствах, предназначенных для. оперативного спектрального и гармонического анализа.

Известно устройство для реализации быстрого преобразования Фурье (БПФ) последовательности с нулевыми элементами, содержащее входной блок памяти, блок управления, распределительный блок, блок оперативной памяти, арифметический блок, блок па мяти коэффициентов. Входом устройств служит информационный вход входного блока памяти, выход которого соединен с первым информационным входом блока оперативной памяти, выход которого подключен к первому информационному входу арифметического блока второй вход которого соединен с выходом блока памяти коэффициентов, выход арифметического блока является выходом устройства, выходы блока управления соединены со входами синхронизации входного блока памяти, распрделительного блока, блока оперативно памяти, арифметического блока, блока памяти коэффициентов ГО«

Во входной блок памяти записывается iv ненулевых точек входной N-точечной последовательносги. Распределительный блок переупорядочивает их и формирует новую N-точечную последовательность путем повторения ненулевых точек последовательности, Элементы полученной последовательности записываются в блок оперативной памяти и затем осуществляется БПФ. Вычисления начинаются с (n-m+D итерации, т.е. для выполнения N-точечного

БПФ необходимо (ri-т) итераций (т log,.,M, h logjN, где N - длительностьреализации; М - длительность, ненулевой части реализации).

Недостатком данного устройства являются большие аппаратурно-временные затраты за счет введения входного блока оперативной памяти и распределительного блока.

Наиболее близким к изобретению является устройство, содержащее блок оперативной памяти, блок памрти коэффициентов, арифметический блок, блок управления, причем первый, второй и третий выходы блока управления соединены соответственно с входами блока оперативной памяти, блока памяти коэффициентов и арифметического блока, первая и вторая группы входом.

арифметического блока соединены соответственно с группами выходов блока оперативной памяти И блока памяти коэффициентов, блок управления содержит двоичный сумматор, регистр

сдвига, блок коммутаторов, сумматор, элементы И, регистр хранения, причем первый выход счетчика соединен с первым входом первого элемента И, второй вход которого соединен с вторым входом второго элемента И и является первым входом блока управления, первый вход второго элемента И соединен с выходом первого разряда двоичного счетчика, выход второго

элемента И соединен с входом второго разряда счетчика, выход первого элемента И соединен с входом регистра сдвига, первый выход регистра сдвига соединен с управляющим входом блока

коммутаторов, второй выход (инверс31ный) регистра сдвига соединен с первым входом сумматора, информацион ный вход блока коммутаторов соединен с вторым выходом счетчика, второй вход регистра хранения соединен с третьим выходом счетчика, выход сумматора соединен с первым входом регистра хранения, выход которого яв ляется первым выходом блока управления и соединен с вторым входом сумма тора, первым входом блока управления является вход двоичного счетчика, BTOpbiM выходом блока управления является выход блока коммутаторов 2. : Однако в известном устройстве не используются возможности для сокраще ния времени вычислений при преобразо В5НИИ последовательностей, содержащи часть нулевых элементов. Ц|ель изобретения - повышение быстродействия устройства за счет устранения избыточности при выполнении БПФ последовательности с нулевым элементами. Поставленная цель достигается тем,.что в устройство, содержащее блок оперативной памяти, арифметичес кий.блок; блок памяти коэффициентов, блок управления, причем вход операнд арифметического блока соединен с .информационным выходом блока оперативной памяти, вход коэффициентов арифметического блока соединен с информационным выходом блока памяти коэффициентов, информационный выход арифметического блока является информационным выходом устройства, введены счетчик занесения, триггер, первая и вторая группы коммутаторов причем информационный выход арифметического блока подключен к первым информационным входам коммутаторов первой группы, вторые информационные входы которых являются информационными входами устройства, управляющие входы коммутаторов первой и второй группы объединены и подключены к выходу триггера, параллельный выход счетчика занесения подключен к первы информационным входам коммутаторов второй группы, первый установочный вход триггера соединен с последовательным выходом счетчика занесения, выходы коммутаторов первой группы подключены .к информационному входу блока оперативной памяти, адресный вход которого подключен к выходам коммутаторов второй группы, причем блок управления содержит коммутатор 54 регистр сдвига, .счетчик, первый и второй элементы И, элемент ИЛИ, сумматор, регистр хранения, причем вход сброса и тактовый вход счетчика соединены соответственно с йыходом триггера и тактовым входом счетчика занесения, тактовьй вход которого является тактовым входом устройства, вход сброса счетчика соединен с установочным входом регистра сдвига, выход первого разряда счетчика подключен к тактовому входу регистра сдвига, выход разрядов, кроме второго разряда, счетчика подключены к инфорМационному входу коммутатора, управляющий вход которого соединен с выходами от первого до п-1-го разрядов регистра сдвига, выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистра хранения, выходы разрядов, кроме второго разряда, счетчика соединены соответственно с входами элемента ИЛИ, выход которого подключен К первому входу первого элемента И, , второй вход которого соединен с инверсным выходом m-t-1-го разряда регистра сдвига, инверсный выход первого элемента И подключен к второму входу второго элемента И, выход которого подключен к второму установочному входу триггера, инверсные выходы от второго до и-1-го разрядов регистра сдвига подключены к первому входу сумматора, выход которого соединен с информационным входом регистра хранения, информационный выход которого подключен к вторым информационным входам коммутаторов второй группы и соединен с вторым входом сумматора, выход п-го разряда регистра сдвига подключен к управляющему входу блока памяти коэффициентов, информационный выход коммутатора подключен к управляющим входам арифметического блока и блока оперативной памяти. На фиг.1 изображена структурная схема устройства; на фиг.2 - функциональная схема блока управления; на фиг.3 - граф процедуры шестнадцати точечного БПФ с четырьмя ненулевыми точками, реализуемого данным устройством. . Устройство для реализа;ции БПФ последовательности с нулевыми элементами (фиг.1) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 памяти коэффициентов, блок 4 управления, п -разрядный счетчик 5 занесения, триггер 6, группу коммутаторов (на два канала) 7, группу коммутаторов (на два канала) 8, входы устройства Х1,Х 2 и вькод устройства Y1. Параллельный выход гп-разрядного (двоичного) счетчика 5 занесения соединен с первыми информационными входами коммутаторов 8 таким образом что i-й разряд счетчика занесения соединен с (n-i+1) разрядом коммутаторов, вторые информационные входы коммутаторов 8 соединены с четвертым входом блока управления 4. Первые информационные входы коммутаторов 7 являются информационным входом устройства Л 1, второй информационный вход коммутаторов 7 соединен с выходом арифметического блока 2. Первая и вторая группы коммутаторов 1управляются выходом триггера 6, первый установочный вход которого соеди нен с последовательным выходом счетчика 5 занесения, а второй установоч ный вход - с третьим выходом блока 4 управления. Арифметический блок 2 выполнен аналогично прототипу и содержит сум матор и умножитель, выполняющий операцию комплексного умножителя. Блок 4 управления (фиг.2) содержи п-разрядный коммутатор 9, п -разрядны регистр. 10 сдвига, (п+1)-разрядньш (двоичный) счетчик 11, элементы И 12 и 13, элемент ИЛИ 14, (n-1)-piaзpядный сумматор 15,-(п-1)-разрядный регистр 16 хранения. Входы блока Л 2 и ХЗ управления, выходы блокаУ2, Y3 Y4 и Y5. Первый выход п-разрядного регистр -10 сдвига представляет собой выход п-го разряда, второй выход - параллельный выход разрядов с первого до (n-l)-ro, третий выход - инверсный выход (гп+1)-го разряда, четвертый выход регистра 10 сдвига - инверсный параллельный выход разрядов со второго до (n-l)-ro. п-разрядный коммутатор 9 выполнен на базе селекторов на три канала, каждый из которых имеет два управляющих входа. Первый управляющий вход j-ro селектора подключен к выхо ду (j+1)-ro разряда регистра 10 сдви га, второй управляющий вход - к выХОДУ j-roразряда, причем первый управляющий вход первого селектора и второй управляющий вход п-го селектора подключены, соответственно, к 1 5 логическим потенциалам 1 и О. Выход первого разряда двоичного счетчика 11 подключен к первому информационному входу первого селектора и к вторым информационным входам селекторов коммутатора 9, выход (j+1)-ro разряда, начиная с третьего разряда к первому информационному входу j-ro селектора, выход (j4-2)-ro разряда к третьему информационному входу j-ro селектора,, а выход третьего разряда двоичного счетчика 11 подключен к третьему информационному входу первого селектора. Выход второго разряда счетчика 11 соединен с входом второго элемента И 13, другой вход которого соединен с инверсным вькодом первого элемента И 12. Вход первого элемента И 12 соединен с инверсным выходом (т+1)-го разряда регистра 10 сдвига, а второго - с выходом элемента ИЛИ 14. m-разрядный элемент ИЛИ. 14 соединен с двоичным счетчиком 11 так, что m разрядов элемента ИЛИ соединены соответственно с разрядами счетчика 11 с первого до (п+1)-го, исключая ,второй разряд. Выход п-го разряда регистра 10 сдвига формирует сигнал обнуления триггера 6, вькод которого подключен к установочному входу регистра 10 сдвига и к входу сброса двоичного счетчика 11. Первьй вход сумматора 15 соединен с инверсным четвертым выходом регистра 10 сдвига так, что j-u разряд сумматора подключается к инверсному выходу (n-j+1) разряда (начиная со второго разряда) регистра сдвига. Б данном устройстве реализован алгоритм БПФ с замещением и прореживанием по времени. Устройство работает следующим образом. В исходном состоянииm-разрядный счетчик,5 занесения и триггер 6 обнулены. В группу коммутаторов 8 на коммутаторы с первого до (п-т) поданы потенциаль О. Выходы разрядов счетчика 5 занесения подключены к первым информационным входам коммутаторов 8 в двоично-инверсном порядке следующим образом. Выход младЩего разряда счетчика 5 занесения соединен с входом старшего коммутатора группы коммутаторов 8, выход старшего разряда счетчика 5 - с (h -тп+1) коммутатором группы коммутаторов 8. На вход устройства Х1 через группу коммутаторов 7,поступает исходная последовательность и записывается в блок 1 оперативной памяти в двоичноинверсном порядке по адресам, которые формируются на выходе группы коммутаторов 8 следующим образом. По входу устройства X 2 на тактовый вход счетчика 5 занес ения поступают тактовые импульсы, по которым (п-разрядный счетчик 5 занесения формирует на первом выходе пбследовательные коды, поступающие на первые информационные входы группы коммутаторов 8, на выходах которых формируются адреса занесения операндов. После занесения операндов сигналом перехода из 1 в О на выходе старшего разряда счетчика 5 занесения триггер 6 устанавливается в единичное состояние. Потенциал 1 с вы хода триггера 6 переключает группы коммутаторов 7 и 8 в режим выполнени БПФ. При этом к информационному вход блока оперативной памяти 1 подключается выход арифметического блока 2, к адресному входу блока 1 оперативной памяти подключается четвертый выход блока 4 управления, формирующи адреса считывания и записи операндов блока 1 оперативной памяти, и в блок 4 управления с выхода триггера 6 поступает сигнал разрешения выполнения итераций БПФ. J Выполнение итерации БПФ заключается в последовательном выполнении в арифметическом блоке 2 элементарны операций видаЛ±ВЛ, где Д и В- one ранды, извлекаемые из блока 1 оперативной памяти; W -г экспоненциальный множитель, извлекаемый из блока 3 па мяти коэффициентов. Процесс выполнения БПФ в предлагаемом устройстве для случая N 16, /И 4 представлен графом БПФ на фиг. где fo ,,,..., f.с - элементы исходной последовательности;Фо , Ф,,..., спектральные коэффициенты; W« ,w ... ..., w- экспоненциальные множители. Каждая элементарная операция БПФ вьтолняется за четыре такта. Считывание из блока 1 оперативной памяти первого операнда (в оперативную память исходная последовательность записывается в двоично-инверсном порядке, считывание из памяти производится в прямом порядке) и считывание экспоненциального множите ля из блока 3 памяти коэффициентов и занесение их з арифметический блок 2. Выполнение операции умножения первого операнда на.экспоненциальныи множитель и извлечение из блока 1 оперативной памяти второго .операнда. Выполнение операции вычитания из второго операнда произведения первого операнда и экспоненциального множителя и занесение разности в блок 1 оперативной памяти на место извлеченного ранее первого операнда. Выполнение операции сложения второго операнда и произведения первого операнда и экспоненциального множителя и занесение суммы в блок 1 оперативной памяти на местоиз влеченного ранее второго операнда. В данном устройстве для выполнения последовательности с нулевыми элeмeнтa ai необходимо произвести (n-m) итераций. Выполнение БПФ начинаётся с (nHn+l) итерации, и в данном устройстве она является первой итерацией БПФ. При выполнении элементарных операций первой итерации БПФ блокируется считывание из 1 оперативной памяти и занесение в арифметический 2 тех операндов, чьи адреса соответствуют нулевым точкам. Элементарная операция в этом случае выполняется с новым экспоненциальным множителем над операндами, уже занесенными в арифметический блок 2. Блокировка считывания из блока 1 оперативной памяти и занесения в арифметический блок 2 осуществляется вторым выходом Y4 блока управления (фиг. 2). . При появлении сигнала перехода старшего разряда счетчика 11 из 1 в О в регистре 10 сдвига происхоДит сдвиг и начинается выполнение следующей итерации БПФ. вьтолнения (л-т) итераций блок управления 4 обнуляет триг-гер 6 и переводит устройство в исходное состояние. Адреса считывания и занесения операндов из блока 1 оперативной памяти формируются в блоке 4 управления. При выполнении к-ой итерации блок 4 управления работает следующим образом. В исходном состоянии двоичный счетчик 11 обнулен, в регистре 10 сдвига во все разряды с первого до

91

К-го занесены 1, а в остальные от (К + 1) до (п + 1) - О. Селекторы управляются таким образом, что при подаче на их управляющие входы двух сигналов О на выход передается информация -с первого информационного входа, при подаче сигналов О и 1 на выход передается информация второго информационного зхода и при подаче на управляющие входы сигналов 1, информация передается с третьег информационного входа.

На вход двоичного счетчика 11 подаются тактовые импульсы.Коммутатор 9, управляемый параллельным выходом регистра 10 сдвига, формирует из выходных сигналов счетчика адреса операндов, необходимых для выполнения элементарных операций БПФ. Одновременно сумматор 15 и регистр 16 хранения формируют адреса экспоненциальных множителей, извлекаемых изблока 3 памяти коэффициентов.

Управление занесением в арифметический блок 2 и извлечение из блок 1 оперативной памяти организуется следующим образом.

(иг.1

п

510

При появлении сигнала 1 в (гп+1) разряде регистра 10 сдвига и сигнала О в (т+1) разрядах двоичного счетчика 11 на инверсном выходе первого

элемента И 12 появляется потенциал 1, который поступает на вход рторого элемента И 13, на другой вход которого поступает сигнал с выхода второго разряда двоичного счетчика

на противоположный, как уолько появляется потенциал 1 на любом из входов элемента ИЛИ 14, либо появляется потенциал О на выходе (т+1)го разряда регистра 10 сдвига.

Предлагаемое устройство позволяет повысить быстродействие за счет существенного сокращения числа итераций, необходимых для выполнения БПФ последовательности, содержащей

нулевые элементы. По сравнению с

ПРОТОТИПОМ время вычисления последе- . вательности при N 1024 и лл 128 сокращается на 30%.