Устройство для реализации быстрого преобразования фурье последовательности с нулевыми элементами

 

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

СОЮЗ СОВЕТСКИХ

СОЦИАЛИСТИЧЕСКИХ

РЕСПУБЛИК

„„SU„„1119025 за G 06 F 15/332

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

К ASTOPCXOMY СВИДЕТЕЛЬСТБУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И OTHPblTHA (21) 3603317/18-24 (22) 10.06.83 (46) 15. 10.84. Бюл. Р 38 (72) А.Н. Карташевич, N.Ñ. Курлянд и А.И. Ходосевич (71) Специальное конструкторско-технологическое бюро с опытным производством при Белорусском государствен- ном университете им. В.И. Ленина (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

Ф 896631, кл, G 06 F 15/332, 1981.

2. Авторское свидетельство СССР

У 809198, кл. G 06 F 15/332, 1979 (прототип). (54) (57) УСТРОЙСТВО ДЛЯ РЕАЛИЗАЦИИ

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

ro соединен с выходами от первого до (n"1)-го разрядов регистра сдвига, выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистра

:В хранения, выходы разрядов, кроме второго разряда, счетчика соединены соответственно со входами элемента

ИЛИ, выход которого подключен к первому входу первого элемента И, второФ вход которого соединен с инверсным выходом (en+1)-ãî. разряда регистра

1119025 лительного блока. двоичного счетчика, выход второго элемента И соединен с входом второго

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

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

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

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

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

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

БПФ необходимо (и-п ) итераций (и =

1щ +s ь = 1оя2N где м — длительность реализации; М вЂ” длительность. ненулевой части реализации}.

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

11190 з ный) регистра сдвига соединен с первым входом сумматора, информационный вход блока коммутаторов соединен с вторым выходом счетчика, второй вход регистра хранения соединен с третьим выходом счетчика, выход сумматора соединен с первым входом ре- . гистра хранения, выход которого яв-! ляется первым выходом блока управления и соединен с вторым входом сумма-1О тора, первым входом блока управления является вход двоичного счетчика, вторым выходом блока управления является выход блока коммутаторов (2 1.

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

Цель изобретения — повышение быстродействия устройства за счет устранения избыточности при выполнении БПФ последовательности с нулевыми элементами.

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

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

40 информационным входам коммутаторов первой группы, вторые информационные входы которых являются информационными входами устройства, управляющие входы коммутаторов первой и второй группы объединены и подключены к выходу триггера, параллельный выход счетчика занесения подключен к первым информационным входам коммутаторов второй группы, первый установочный вход триггера соединен с последовательным выходом счетчика занесения, выходы коммутаторов первой группы подключены,к информационному входу блока оперативной памяти, адресный 55 вход которого подключен к выходам коммутаторов второй группы, причем блок управления содержит коммутатор, 25 4 регистр сдвига, счетчик, первый и второй элементы И, элемент ИЛИ, сумматор, регистр хранения, причем вход сброса и тактовый вход счетчика соединены соответственно с выходом триггера и тактовым входом счетчика занесения, тактовый вход которого является тактовым входом устройства, вход сброса счетчика соединен с установочным входом регистра сдвига, выход первого разряда счетчика подключен к тактовому входу регистра сдвига, выход разрядов, кроме второго разряда, счетчика подключены к инфор,мационному входу коммутатора, управляющий вход которого соединен с выходами от первого до и -1-ro разрядов регистра сдвига, выход второго разряда счетчика подключен к первому входу второго элемента И и тактовому входу регистра хранения, выходы разрядов, кроме второго разряда, счетчика соединены соответственно с входами элемента ИЛИ, выход которого подключен к первому входу первого элемента И, второй вход которого соединен с инверсным выходом en+1-ro разряда регистра сдвига, инверсный выход первого элемента И подключен к второму входу второго элемента И, выход которого подключен к второму установочному входу триггера, инверсные выходы от второго до -1-ro разрядов регистра сдвига подключены к первому входу сумматора, выход которого соединен с информационным входом регистра хранения, информационный выход которого подключен к вторым информационным входам коммутаторов второй группы и соединен с вторым входом сумматора, выход ь-го разряда регистра сдвига подключен к управляющему входу блока памяти коэффициентов, информационный выход коммутатора подключен к управляющим входам арифметического блока и блока оперативной памяти.

На фиг.1 изображена структурная схема устройства; на фиг.2 — функцио.нальная схема блока управления; на фиг.З " граф процедуры шестнадцатиточечного БПФ с четырьмя ненулевыми точками, реализуемого данным устройством..

Устройство для реализации БПФ последовательности с нулевыми элементами (фиг. 1) содержит блок 1 оперативной памяти, арифметический блок 2, блок 3 памяти коэффициентов, блок 4 управления, ъ -разрядный счет»

025 . 6 логическим потенциалам "1" и "0", Выход первого разряда двоичного счетчика 1 1 подключен к первому информационному входу первого селектора и к вторым информационным входам селекторов коммутатора 9, выход (1+1)-го разряда, начиная с третьего разряда— к первому информационному входу j-го селектора, выход (1+2)-го разряда— к третьему информационному входу

1 -го селектора,, а выход третьего разряда двоичного счетчика 11 подключен к третьему информационному входу первого селектора.

Выход второго разряда счетчика 11 соединен с входом второго элемента

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

И 12. Вход первого элемента И 12 соединен с инверсным выходом (в+1)-го разряда регистра 10 сдвига, а второго — с выходом элемента ИЛИ 14.

rn-разрядный элемент ИЛИ 14 соединен с двоичным счетчиком 11 так, что tn разрядов элемента ИЛИ соединены соответственно с разрядами счетчика

11 с первого до (п+1)-го, исключая ,второй разряд.

Выход n -ro разряда регистра 10 сдвига формирует сигнал обнуления триггера 6, выход которого подключен к установочному входу регистра 10 сдвига и к входу сброса двоичного счетчика 11.

Первый вход сумматора 15 соединен с инверсным четвертым выходом регист.ра 10 сдвига так, что j""é разряд сумматора подключается к инверсному выходу (n-.j+1) разряда (начиная со второго разряда) регистра сдвига.

В данном устройстве реализован алгоритм БПФ с замещением и прореживанием по времени.

Устройство работает следующим образом.

В исходном состоянии nt-разрядный счетчик.5 занесения и триггер 6 обнулены. В группу коммутаторов 8 на коммутаторы с первого до (ь -m) поданы потенциалы "0". Выходы разрядов счетчика 5 занесения подключены к первым информационным входам коммутаторов 8 в двоично-инверсном порядке следующим образом. Выход младшего разряда счетчика 5 занесения соединен

° с входом старшего коммутатора группы коммутаторов 8, выход старшего разряда счетчика 5 — с (n +1) коммутатором группы коммутаторов 8, 5 1119 чик 5 занесения, триггер 6, группу коммутаторов (на два канала) 7, группу коммутаторов (на два канала)

8, входы устройства Х 1, Х 2 и выход устройства У1.

Параллельный выход в-разрядного (двоичного) счетчика 5 занесения соединен с первыми информационными входами коммутаторов 8 таким образом, что 1-й. разряд счетчика занесения соединен с (n-1+ 1) разрядом коммутаторов, вторые информационные входы коммутаторов 8 соединены с четвертым входом блока управления 4. Первые информационные входы коммутаторов 7 являются информационным входом устройства Я 1, второй информационный вход коммутаторов 7 соединен с выходом арифметического блока 2.

Первая и вторая группы коммутаторов управляются выходом триггера 6, пер-. вый установочный вход которого соединен с пбследовательным выходом счетчика 5 занесения, а второй установочный вход - с третьим выходом блока . 25

4 управления.

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

Блок 4 управления (фиг.2) содержит н-разрядный коммутатор 9, п -разрядный регистр 10 сдвига, (и+1)-разрядный (двоичный) счетчик 11, элементы И 12 и 13, элемент ИЛИ 14, (n-1)-разрядный сумматор 15,-(п-1)-разрядный регистр 16 хранения. Входы блока Я 2 и Х 3 управления, выходы блока Y 2, У3, У4 и У5, 11ервый выход в -разрядного регистра

40 .10 сдвига представляет собой выход и-го разряда, второй выход — параллельный выход разрядов с первого до (n"1)-ro, третий выход - инверсный выход (м+1)-ro разряда, четвертый

45 выход регистра 10 сдвига — инверсный параллельный выход разрядов со второго до (n-1)-ro. и --разрядный коммутатор 9 выполнен на базе селекторов иа три канала, каждый из которых имеет два управ50 ляющих входа. Первый управляющий вход j-ro селектора подключен к выходу (j+1)-го разряда регистра 10 сдвига, второй управляющий вход — к выходу >-го разряда, причем первый управляющий вход первого селектора и второй управляющий вход n -ro селектора подключены, соответственно, к

7 11190

На вход устройства Х1 через группу коммутаторов 7 поступает исходная последовательность и записывается в блок 1 оперативной памяти в двоичноинверсном порядке по адресам, которые формируются на выходе группы коммутаторов 8 следующим образом.

По входу устройства Х 2 на тактовый вход счетчика 5 занесения поступают тактовые импульсы, по которым 1р ш-разрядный счетчик 5 занесения формирует на первом выходе последова- . тельные коды, поступающие на первые информационные входы группы коммутаторов 8, на выходах которых формируются адреса занесения операндов.

После занесения операндов сигналом перехода из "1" в "0" на выходе старшего разряда счетчика 5 занесения триггер 6 устанавливается в единичное состояние. Потенциал "1" с выхода триггера 6 переключает группы коммутаторов 7 и 8 в режим выполнения

БПФ. При этом к информационному входу блока оперативной памяти 1 подклю- 25 чается выход арифметического блока

2, к адресному входу блока 1 оперативной памяти подключается четвертый выход блока 4 управления, формирующий адреса считывания и записи операндов блока 1 оперативной памяти, и в блок

4 управления с выхода триггера 6 поступает сигнал разрешения выполнения итераций БПФ.

1 Выполнение итерации БПФ заключа35 ется в последовательном выполнении в арифметическом блоке 2 элементарных операций вида Я 2 gal где.Д и Ь вЂ” операнды, извлекаемые из блока 1 оперативной памяти; % †. экспоненциальный множитель, извлекаемый иэ блока 3 памяти коэффициентов.

Процесс выполнения БПФ в предлагаемом устройстве для случая И = 16, М = 4 представлен графом БПФ на фиг.З где Ео, Е,,..., f элементы исходной последовательности; Фо, Ф,, °, ф 5спектральные коэффициенты; Ф,W,,.-.,.,,„ о ..., W — - экспоненциальные множители.

Каждая элементарная операция БПФ выполняется за четыре такта.

Считывание из блока 1 оперативной памяти первого операнда (в оперативную память исходная последовательность записывается в двоично-инверсном порядке, считывание из памяти производится в прямом порядке) и считывание экспоненциального множите25 8 ля из блока 3 памяти коэффициентов и занесение их а арифметический блок 2.

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

Выполнение операции вычитания из второго операнда произведения первого операнда и экспоненциального множителя и занесение разности в блок 1 oneративной памяти на место извлеченного ранее первого операнда.

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

В данном устройстве для выполнения

БПФ последовательности с нулевыми элементами необходимо произвести (n -ю) итераций. Выполнение БПФ начинается с (n m+1) итерации, и в данном устройстве она является первой итерацией БПФ.

При выполнении элементарных операций первой итерации БПФ блокируется считывание из блока 1 оперативной памяти и занесение в арифметический блок 2 тех операндов, чьи адреса соответствуют нулевым точкам.

Элементарная операция в этом случае выполняется с новым экспоненциальным множителем над операндами, уже занесенными в арифметический блок 2.

Блокировка считывания из блока 1 оперативной памяти и занесения в арифметический блок 2 осуществляется вторым выходом У4. блока управления (фиг.2).

При появлении сигнала перехода старшего разряда счетчика 11 иэ "1" в ".0" в регистре 10 сдвига происходит сдвиг и начинается выполнение следующей итерации БПФ.

После выполнения (ь-ю) итераций

БПФ блок управления 4 обнуляет триг.гер 6 и переводит устройство в исходное состояние.

Адреса считывания и занесения операндов иэ блока 1 оперативной памяти формируются в блоке 4 управления °

При выполнении К -ой итерации блок

4 управления работает следующим образом.

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

1119025

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

" 1" на выход передается информация второго информационного зхода и при подаче на управляющие входы сигналов

"1", информация передается с третьего информационного входа.

На вход двоичного счетчика 11 подаются тактовые импульсы. Коммутатор

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

Управление занесением в арифме- ZS тический блок 2 и извлечение из блока

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

При появлении сигнала "1 в (р+1) разряде регистра 10 сдвига и сигнала

"0" в (in+1) разрядах двоичного счетчика 11 на инверсном выходе первого элемента И 12 появляется потенциал

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

11. Сигнал управления считыванием из блока 1 оперативной памяти и занесением в арифметический блок 2 формируется на выходе второго элемента

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

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

БПФ последовательности, содержащей

1нулевые элементы. По сравнению с поототипом время вычисления последовательности при N = 1024 и М 128 совращается на 30%.

1) )9025

Фиг. 2

СЦ

Яу

Филиал ППП "Патент", r. Умгород» ул. Проектнал, 4 Р

ВН КИПИ ,р Тирам 698

f3

Заказ 7455/37

Подписное