1086438 - Процессор быстрого преобразования фурье

Процессор быстрого преобразования фурье

Иллюстрации

Показать все

Реферат

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

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

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

РЕСПУБЛИК

„„SU „„1086438 (ц G 06- F 15/332

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

Н ABTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 3442140/18-24 (22) 24.05.82 (46) 15.04.84. Бюл. Ф 14 .(72) В.Э.Вершков, Ю.И.Ветохин, А.В.Голубева,„ Н.С.Парфенов и А.Т.Прокошенков (53) 681.32(088.8) (56) 1. Авторское свидетельство СССР

Р 421994, кл. G 06 F 15/332, 1974.

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

У 736112, кл G 06 F 15/332, 1980 (прототип). (54)(57) 1. ПРОЦЕССОР БЫСТРОГО ПРЕОБРАЗОВАНИЯ .ФУРЬЕ, содержащий арифметический блок, первый и второй блоки памяти, блок постоянной памяти, блок управления, три формирователя адреса, два элемента И и два элемента ИЛИ, причем выходы первого и второго элементов И соединены с первыми входами соответственно первого и второго элементов ИЛИ, выходы которых подключены соответственно к первому и второму входу операндов арифметического блока, входы действительной и мнимой части коэффициентов которого соединены соответственно с первым и вторым выходами блока постоянной памяти, вход которого соединен с выходом первого формирователя адреса, выходы второго и третьего формирователей адреса соединены с адресными входами соответственно первого и второго блоков памяти, первые и вторые выходы которых соответственно объединены.н являются соответственно первым и вторым информационными выходами процессора, а первые входы первого и второго элементов И являются соответственно первым и вторым информационными входами процессора, отличающийся . тем, что, с целью повышения быстродействия процессора, он содержит первый, второй, третий и четвертый элементы 2 И-ИЛИ, первый и второй сумматоры по модулю 2, первый и второй элементы НЕ, причем первый выход блока управления соединен с первыми входами первого и второго элементов 2 И-ИЛИ, выходи которых подключены к вторым входам соответственно первого и второго элементов ИЛИ, второй выход блока управления подключен к вторым входам первого и второго элементов 2 И-ИЛИ, третьи и четвертые входы которых подключены соответственно к первому и второму выходам первого блока памяти, третий выход блока управления соединен с вторыми входами первого и второго эле-ментов И, четвертый выход блока управления подключен к входу первого формирователя адреса, пятый выход блока управления соединен с входом управления приемом информации арифметического блока, выходы действительной части первого и третьего операндов которого соединены с первыми входами соответственно третьего и четвертого элементов 2 И-ИЛИ, выхо. да которых подключены к первым входам соответственно первого и второго сумматоров по модулю 2, выходы которых подключены соответственно к первым и вторым информационным входам первого и второго блоков памяти, шестой выход блока управления соединен с входом управления суммированием

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

2. Устройство по п. 1, о т л ивЂ” ч а ю щ е е с я тем, что блок управления содержит счетчик этапов, дешифратор этапов, счетчик итераций, дешифратор итераций, синхронизатор, четыре сдвиговых регистра, первый и второй коммутатор, шесть триггеров, . тридцать элементов И, тринадцать элементов ИЛИ и шесть элементов НЕ, причем выход первого элемента НЕ соединен с первым входом первого элемента И, выход которого подключен к первому входу первого элемента ИЛИ, выход которого соединен с тактовым входом счетчика этапов, выход которого подключен -к входу дешифратора этапов, первый выход которого подключен к первому, входу второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ и первым входом второго элемента И, второй вход котороro объединен с первыми входами третьего, четвертого, пятого элементов И, вторым входом первого элемента И и счетным входом первого триггера, второй выход дешифратора этапов соединен с первым входом третьего элемента ИЛИ, вторым входом второго элемента ИЛИ, входом первого элемента НЕ, вторым входом пятого элемента И и вторым входом четвертого элемента И, выход которого соединен с тактовым входом счетчика итераций, первый выход которого соединен с третьим входом пятого элемента И, выход которого подключен к второму входу первого элемента ИЛИ, третий выход дешифратора этапов соединен с первым входом четвертого элемента ИЛИ, вторым вхо" дом третьего элемента ИЛИ и третьим входом второго элемента ИЛИ, четвертый выход дешифратора этапов подключен к второму входу четвертого элемента ИЛИ и третьему входу третьего элемента ИЛИ, первый выход первого коммутатора соединен с первым входом четвертого элемента И и входом синхронизатора, выход которого соединен. с первым входом шестого элемента И, первым входом пятого элемента.ИЛИ и единичным входом второго триггера, выход которого подключен к первому входу седьмого элемента И, выход ко" торого соединен с тактовым входом первого регистра сдвига, выход кото рого соединен с вторым входом пятого элемента ИЛИ, первыми входами вомьйого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого, четырнадцатого и пятнадцатого элементов И, второй выход первого коммута-. тора соединен с нулевым входом второго триггера и входом первого сдвигового регистра, управляющий вход которого -подключен к выходу пятого элемента ИЛИ, выход синхронизатора соединен с первым входом шестого элемента ИЛИ, выход которого соединен с входом второго сдвигового регистра, выход которого подключен к первому входу седьмого элемента ИЛИ, второй вход которого соединен с выходом шестого элемента И, второй вход которого объединен с первым входом шестнадцатого элемента И, вторым входом четырнадцатого элемента И и подключен к четвертому выходу дешифратора этапов, выход третьего элемента ИЛИ подключен к вторым входам тринадцатого элемента И

10864 и восьмого элемента И, выход которого соединен со счетным входом третьего триггера, единичный выход которого подключен к первым входам семнадцатого, восемнадцатого элементов И, вторым входом десятого, одиннадцатого, пятнадцатого, шестнадцатого элементов И и третьему входу четырнадцатого элемента И, .выходы второго и третьего элементов И соединены соответственно с,еДиничным и нулевым входами третьего триггера, нулевой выход которого подключен к второму входу девятого элемента И и третьему входу тринадцатого элемента И, выход которого соединен с первым входом восьмо- го элемента ИЛИ, второй вход которого является четвертым входом блока управления, второй выход дешифратора этапов соединен с вторым входом восемнадцатого элемента И и третьим входом девятого элемента И, выход которого подключен к первому входу девятого элемента ИЛИ, второй вход которого соединен с выходом десятого элемента И, третий вход которого соединен с вторым входом семнадцатого элемента И, первым входом первого коммутатора и подключен к выходу четвертого элемента ИЛИ, пятый выход дешифратора этапов соединен с вторым входом двенадцатого элемента И, выход . которого соединен с третьим входом девятого элемента ИЛИ и является пятнадцатым выходом блока управления, выходы семнадцатого, восемнадцатого элементов И и девятого элемента ИЛИ соединены соответственно с первым, вторым и третьим входами второго коммутатора, первый и второй выходы которого являются соответственно двенадцатым и тринадцатым выходами блока управления, первый выход дешифратора этапов является третьим выходом блока управления и подключен к входу третьего элемента НЕ, выход которого соединен с первым входом девятнадцатого элемента И, второй вход которого подключен к выходу четвертого эле- мента НЕ, вход которого соединен с выходом шестнадцатого элемента И, выход которого является вторым выходом блока управления, а выход девятнадцатого элемента И является первым выходом блока управления, третий выход первого коммутатора соединен с единичным входом четвертого триггера, единичный выход которого подключен к третьему входу пятнадцатого элемен38 та И, выход которого соединен с нулевым входом четвертого триггера и вторым входом шестого элемента ИЛИ, третий вход которого соединен с выходом четырнадцатого элемента И, управляющие входы синхронизатора, второго сдвнгового регистра и второй вход седьмого элемента И объедй ены и являются третьим входом блока управле ния, выход восьмого элемента ИЛИ соединен с вторым входом первого коммутатора и входом третьего сдвигового регистра, выход которого подключен к первому входу десятого элемента ИЛИ и единичному входу пятого триггера, единичный выход которого соединен с первым входом двадцатого элемента И, выход которого подключен к тактовому входу четвертого сдвигового регистра, выход которого подключен к третьему входу первого коммутатора и первым входом двадцать первого, двадцать второго, двадцать третьего и двадцать четвертого элементов И, первый выход первого коммутатора соединен с нулевым входом пятого триггера и управляющим входом четвертого сдвигового регистра, вход которого подключен к выходу десятого элемента ИЛИ, второй вход которого объединен с первыми входами двадцать пятого, двадцать шестого, двадцать седьмого, двадцать восьмого, двадцать девятого элементов И, вторым входом двадцать третьего элемента И и подключен к единичному выходу шестого триггера и образует восьмой выход блока управления, нулевбй выход шестого триггера подключен к первому входу тридцатого элемента Й, в.жрому входу двадцать второго элемента И и является седьмым выходом блока управления, выход третьего элемента ИЛИ соединен с вторым входом двадцать четвертого элемента И, выход которого подключен к счетному входу шестого триггера, единичный и нулевой входы которого соединены с выходами соответственно второго и третьего элементов И, второй выход дешифратора этапов соединен с вторыми входами двадцать пятого, тридцатого и двадцать шестого элементов И, первый выход дешифратора итераций соединен с третьим входом двадцать пятого и тридцатого элемеп;тов И, входом пятого элемента НЕ, выход которого подключен к третьему входу двадцать шестого элемента И, выход которого соединен с первым вхоI 08б438 дом одиннадцатого элемента ИЛИ, второй вход которого объединен с первым входом двенадцатого элемента ИЛИ и подключен к выходу двадцать пятого элемента И, выход тридцатого элемента И, соединен с вторым входом двенадцатого элемента ИЛИ, выход четвертого элемента ИЛИ подключен к второму входу двадцать седьмого элемента И, третьему входу двадцать третьего элемента И и входу шестого элемента НЕ, выход которого подключен к третьему входу двадцать второго элемента И, выход которого подключен к первому входу тринадцатого элемента ИЛИ, второй вход которого соединен с выходом двадцать третьего элемента И, третий выход дешифратора итераций является шестым выходом блока управления и соединен с вторым входом двадцать восьмого элемента И, выход которого является девятым выходом блока управления, четвертый выход дешифратора этапов подключен к второму входу двадцать девятого элемента И, выход которого является десятым выходом блока управления, выходы одиннадцатого, двенадцатого

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

Известно устройство для вычисления коэффициентов Фурье, в котором быстродействие повышается за счет совмещения вычислений. Устройство содержит блоки умножения, суммирующие блоки, регистры действительной и мнимой частей весового коэффициента E 13 °

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

20 и тринадцатого элементов ИЛИ и выход двадцать седьмого элемента И соединены соответственно с четвертым, пятым, шестым и седьмым входом второго коммутатора, второй выход двадцатого элемента И и тактовый вход третьего сдвигового регистра объединены и образуют третий вход блока управления, первый, второй, третий и четвертый выходы дешифратора итерации являются четырнадцатым выходом блока управления, выход первого триггера соединен с четвертым входом первого коммутатора и восьмым входом второго коммутатора и является одиннадцатым выходом блока управления, первый выход дешифратора этапов является третьим выхо; дом блока управления, выходы четвертого и седьмого элементов ИЛИ являются четверчъйк выходом блока управления, выход одиннадцатого элемента И, выходы второго и третьего сдвиговых регистров и выход восьмого элемента ИЛИ образуют пятйй выход блока управления, а пятый и шестой входы первого коммутатора являются соответственно первым и вторым входами блока управления. ранее вычисленные результаты не будут переписаны в 03У.

Наиболее близким техническим решением к изобретению является устройство для вычисления коэффициентов

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

К недостаткам данного устройства следует отнести относительно небольшое быстродействие при вычислении коэффициентов Фурье от действительной последовательности входных данных; кроме того, реализуемая в нем организация вычислений коэффициентов

1086438

Фурье от действительной последова- которого соединены с первыми входами тельности требует значительных объе- соответственно третьего и четвертого мов оперативной памяти. элементов 2 И-ИЛИ, выходы которых

Цель изобретения - повышение быст- подключены к первым входам соответст-. родействия и упрощение устройства. 5 венно первого и второго сумматоров по модулю 2, выходы которых подключеПоставленная цель достигается ны соответственно к первым и вторым тем, что в процессор, содержащий (. информационным входам первого и втоарифметический блок, первый и второй р го блоков памяти, шестой выход блоблоки памяти, блок постоянной памяти ка управления соединен с входом управблок управления, три формирователя ления суммированием арифметического адреса, два элемента И и два элемен- блока, вход управления вычитанием та ИЛИ, причем выходы первого и втокоторого подключен к выходу первого рого элементов И соединены с первыми элемента НЕ, вход которого соединен входами соответственно первого и вто- 15 с шестым выходом блока управления, рого элементов ИЛИ, выходы которых седьмой и восьмой выходы которого соподключены соответственно к первому единены соответственно с вторыми и и второму входу операндов арифметитретьими входами третьего и четверточеского блока, входы действительной го элементов 2 И-ИЛИ, четвертые вхои мнимой части коэффициентов котаро- 20 ды которых подключены к выходам мни- го соединены соответственно с первым мых частей соответственно первого и и вторым выходами блока постоянной второго операндов арифметического блопамяти, вход которого соединен с вы- ка, девятый и десятый выходы блока ходом первого формирователя адреса, управления подключены к вторым входам выходы второго и третьего формировасоответственно первого и второго сумтелей адреса соединены с адресными маторов по модулю 2, одиннадцатый вывходами соответственно первого:и вто- ход блока управления соединен с управрого блоков памяти, первые и вторые ляющим входом первого блока памяти выходы которых соответственно объеди- и входом второго элемента НЕ, выход иены и являются соответственно перЗО которого подключен к управляющему вым и вторым информационными выхода- входу второго блока памяти, двенадцами процессора, а первые входы пврво- тый и тринадцатый выходы блока управго и второго элементов И являются пения соединены с входами задания соответственно первым и вторым инфорадреса соответственно второго и третьмационными входами процессора, содер- его формирователей адреса, выходы пежит первый, второй, третий и четверреполнения которых подключены сооттый элементы 2 И-ИЛИ, первый и второй ветственно к первому и второму входам сумматоры по модулю 2, первый и вто- блока управления, четырнадцатый выход рой элементы НЕ, причем первый выход которого подключен к входу задания блока управления соединен с первыми

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

И-ИЛИ, третьи и четвертые приема процессора. входы которых подключены соответстБлок управления содержит счетчик венно к .первому и второму выходам перво г б этапов, дешифратор этапов, счетчик первого лока памяти, третий выход блока управления соединен с в низатор, четыре сдвиговых регистра, входами первого и второго элеменпервый и второй коммутаторы, шесть тов, четвертыи выход блока управлетриггеров, тридцать элементов И, ния подключен к входу первого форми- тринадцать элементов ИЛИ и шесть элерователя адреса, пятый выход блока ментов НЕ, причем выход первого элеуправления соединен с входом управпения приемом инф ац м информации а ифметичес мента HF, соединен с первым входом р фметичес- .первого элемента И, выход которого первому входу первого. кого блока, выходы действительной .-:,подключен к первому части первого и третьего операндов - элемен ИЛИ нта, выход которого соедиS 10864 нен с тактовым входом счетчика этапов, выход которого подключен к входу дешифратора этапов, первый выход которого подключен к первому входу второго элемента ИЛИ, выход которого соединен с входом второго элемента НЕ и первым и входом второго элемента И, второй вход которого объединен с первыми входами третьего, четвертого, пятого элементов И, вторым входом !О первого элемента И и счетным входом первого триггера, второй выход дешифратора этапов соединен с первым входом третьего элемента ИЛИ, вторым входом второго элемента ИЛИ, входом первого элемента НЕ, вторым входом пятого элемента И и вторым входом четвертого элемента И, выход которого соединен с тактовым входом счетчика итераций, выход которого соеди- щ нен с третьим входом пятого элемента И, выход которого подключен к второму входу первого элемента ИЛИ, третий выход дешифратора этапов соединен с первым входом четвертого элемента ИЛИ, вторым входом третьего элемента ИЛИ и третьим входом второго элемента ИЛИ, четвертый выход дешифратора этапов подключен к второму входу четвертого элемента ИЛИ и третьему входу третьего элемента ИЛИ, первый выход первого коммутатора соединен с первым входом четвертого элемента И и входом синхронизатора, выход которого соединен с первым вхо35. дом шестого элемента И, первым вко- до..1 пятого элемента ИЛИ и единичным входом второго триггера, выход которого подключен к первому входу седь мого элемента И, выход которого сое- 4О динен с тактовым входом первого регистра сдвига, выход которого соединен с вторым входом пятого элемента ИЛИ, первыми входами восьмого, девятого, десятого, одиннадцатого, двенадцатого, тринадцатого и четырнадцатого и пятнадцатого элементов И, второй выход первого коммутатора соединен с нулевым входом второго триггера и входом первого сдвигового регистра, управляющий вход которого подключен к выходу пятого элемента ИЛИ, выход синхронизатора соединен с первым входом шестого элемента ИЛИ, выход которого соединен с

55 входом второго сдвигового регистра, выход которого подключен к первому входу седьмого элемента ИЙИ, второй вход которого соединен с выходом

38 6 шестого элемента И, второй вход которого объединен с первым входом шестнадцатого элемента И, вторым входом четырнадцатого элемента И и подключен к четвертому выходу дешифратора этапов, выход третьего элемента ИЛИ подключен к вторым входам тринадцатого элемента И и восьмого элемента И, выход которого соединен со счетным входом третьего триггера, единичный выход которого подключен к первым входам семнадцатого, восемнадцатого элементов И, вторым входом десятого, одиннадцатого, пятнадцатого, шестнадцатого элементов И и третьему входу четырнадцатого элемента И, выходы второго и третьего элементов И соединены соответственно с единичным и нулевым входами третьего триггера, нулевой выход которого подключен к второму входу девятого элемента И и к третьему входу тринадцатого элемента И, выход которого соединен с первым входом восьмого элемента ИЛИ, второй вход которого является четвертым входом блока- управления, второй выход дешифратора этапов соединен с вторым входом восемнадцатого элемента И и третьим входом девятого элемента И, выход которого подключен к первому входу девятого элемента ИЛИ, второй вход которого соединен с выходом десятого элемента И, третий вход которого объединен с вторым входом семнадцатого элемента И, первым входом перsore коммутатора и подключен к выходу четвертого элемента ИЛИ, пятый выход дешифратора этапов соединен с вторым входом двенадцатого элемента И, выход которого соединен с третьим входом девятого элемента ИЛИ и является пятнадцатым выходом блока управления, выходы семнадцатого, восемнадцатого элементов И и девятого элемента ИЛИ соединены соответственно с первым, вторым и третьим входами второго коммутатора, первый и второй выходы которого являются соответственно двенадцатым и тринадцатым выходами блока управления, первый выход дешифратора этапов является третьим выходом блока управления и подключен к входу третьего элемента НЕ, выход которого соединен с первым входом девятнадцатого элемента И,. второй вход которого подключен к выходу четвертого элемен,а Й, второй вход которого подключен к выходу четвертого элемента НЕ, вход которого соединен с выходом шестнад5S

7 3086 цатого элемента И, выход которого является вторым выходом блока управ- ления, а выход девятнадцатого элемента И является первым выходом блока управления, третий выход первого коммутатора соединен с единичным входом четвертого триггера, единичный выход которого подключен к третьему входу пятнадцатого элемента И, выход которого соединен с нулевым входом четвертого триггера и вторым входом шестого элемента ИЛИ, третий вход которого соединен с выходом четырнадцатого элемента И, управляющие входы синхронизатора, второго сдвигового регистра и второй вход седьмого элемента И объединены и являются третьим входом блока управления, выход восьмого элемента HIIH соединен с вторым входом первого коммутатора и входом третьего сдвигового регистра, выход которого подключен к первому входу десятого элемента ИЛИ и единичному входу пятого триггера, единичный выход которого соединен с первым входом двадцатого элемента И, выход которого подключен к тактовому входу четвертого сдвигового регистра, выход которого подключен к третьему входу первого коммутатора и первым входом двадцать первого, двадцать второго, 30 двадцать третьего и двадцать четвертого элементов И, первый выход пер-вого коммутатора соединен с нулевым входом пятого триггера и управляющим входом четвертого сдвигового регистра, вход которого подключен к выходу десятого элемента ИЛИ, второй вход которого соединен с первыми входами двадцать пятого, двадцать шестого, двадцать седьмого, двадцать вось- 4О мого, двадцать девятого элементов И, вторым входом двадцать третьего элемента И и подключен к единичному выходу шестого триггера и образует восьмой выход блока управления, нуле-45 вой выход шестого триггера подключен к первому входу тридцатого элемента И, второму входу двадцать второго элемента И и является седьмым выходом блока управления, выход третьего 5О элемента ИЛИ соединен с вторым входом двадцать четвертого элемента И, выход которого подключен к счетному входу шестого триггера, единичный и нулевой входы которого соединены с выходами соответственно второго . и третьего элементов И, второй выход дешифратора этапов соединен с вторы- .

438 8 ми входами двадцать пятого, тридцатого и двадцать шестого элементов И, первый выход дешифратора итераций соединен с третьим входом двадцать пятого и тридцатого элементов И и входом пятого элемента НЕ, выход которого подключен к третьему входу двадцать шестого элемента Я, выход которого соединен с первым входом одиннадцатого элемента ИЛИ, второй вход которого объединен с первым входом двенадцатого элемента ИЛИ и подключен к выходу двадцать пятого элемента И, выход тридцатого элемента И соединен с вторым входом двенадцатого элемента ИЛИ, выход четвертого элемента ИЛИ подключен к второму входу двадцать седьмого элемента И, третьему входу двадцать третьего элемента И и входу шестого элемента НЕ, выход которого подключен к третьему входу двадцать второго элемента И, выход которого подключен к первому входу тринадцатого элемента ИЛИ, второй вход которого соединен с выходом двадцать третьего элемента И, третий выход дешифратора итераций является шестью выходом .блока управления и соединен с вторым входом двадцать восьмого элемента И, выход которого является девятым выходом блока управления, четвертый выход дешифратора этапов подключен к второму входу двадцать девятого элемента И, выход которого является десятым выходом блока управления, выходы одиннадцатого, двенадцатого и тринадцатого элементов HJIH и выход двадцать седьмого элемента И соединены соответственно с четвертым, пятым, шестым и седьмым входом второго коммутатора, второй выход двадцатого элемента И и тактовый вход третьего сдвигового регистра объединены и образуют третий вход блока управления, первый, второй, третий и четвертый выходы дешифратора итерации являются четырнадцатым выходом блока управления, выход первого триггера соединен с четвертым входом первого коммутатора и восьмым входом второго коммутатора и является одиннадцатым выходом блока управления, первый выход дешифратора этапов является третьим выходом блока управления, выходы четвертого и седьмого элементов ИЛИ являются четвертым выходом блока управления, выход одиннадцатого элемента И, выходы второго и третьего сдвиговых регист1086438

10 ров и выход восьмого элемента ИЛИ образуют пятый выход блока управления, а пятый и шестой входы первого коммутатора являются соответственно первым и вторым входами блока управ- 5 ления.

На фиг. 1 представлена схема процессора; на фиг. 2 вЂ” 10 вЂ” соответственно арифметический блок, формирователь адресов постоянной памяти, формирователь адресов (оперативной памяти), блок управления, узел этапов, узел управления считыванием, узел управшвния записью, входной и выходной коммутаторы. t5

Процессор быстрого преобразования

Фурье содержит арифметический блок 1, блоки (оперативной) памяти 2, 3, блок,постоянной памяти 4, формирователь адресов (постоянной памяти) 5, формирователи адресов (оперативной памяти) 6, 7, блок управления 8, четыре элемента 2 И-ИЛИ 9-12, два элемента И 13 и 14, два элемента HJIH 15 и 16, два сумматора по модулю 2 17 и 18, элементы НЕ 19 и 20, информа-. ционные входы 21, 22, тактовый вход 23, вход синхронизации приема чисел 24, информационные выходы процессора 25, 26, выход синхронизации 30 выдачи чисел 27, выходы 28-41 блока 8, выход 42 элемента НЕ 19, выходы 43-44 формирователей 6 и 7 соответственно.

На фиг. 2 представлена функциональная схема арифметического блока 1, который соответствует вычислительному устройству прототипа и содержит регистры 45 реальной и 46 мнимой частей первого числа иэ пары 4б обрабатываемых комплексных чисел, регистры 47 и 48 реальной и мнимой частей комплексного весового коэффициента, матричные умножители 49-52, сумматоры 53, 54, регистры 55 реаль- 45 ной и 56 мнимой частей второго числа из пары обрабатываемых комплексных чисел, сумматоры 57-60, регистры 61, 62 хранения реальной части соответственно первого и второго комплексного 50 результата вычислений и регистры 63, 64 хранения мнимой части соответственно первого и второго комплексного результата вычислений.

На фиг. 3 представлена.функцио, нальная схема формирователя адресов постоянной памяти 5, который содержит счетчик адреса 65 на а разрядов, элемент НЕ 66, группу элементов 2 ИИЛИ 67 - 67>

На фиг. 4 представлена функциональная схема формирователя адресов (оперативной памяти) 6 (7), который содержит регистр адреса на е разрядов, состоящий из триггеров 681- 68 „, элемент И на (м-1) вход 69, элемент ИЛИ íà (tn-1) вход 70, двухвходовые элементы И 71, 72, двухвходовые элементы ИЛИ 73 вЂ” 73 элемен1 ttt- t» ты НЕ 741 вЂ” 74» двухвходовой элемент И 75, две группы трехвходовых элементов И 76„ 76 »„, И 771

-77П., двухвходовые элементы ИЛИ 78, 79 вЂ” 79щ, сумматоры по модулю 2

80. вЂ” 80, мультиплексоры 81., вЂ” 81

fit для выдачи кода адреса.

На фиг. 5 представлена структурная схема блока управления 8, который содержит узел этапов 82, раскрытый на фиг. 6, узел управления считыванием 83, раскрытый на фиг. 7, узел управления записью 84, раскрытый на фиг. 8, входной коммутатор 85, раскрытый на фиг. 9, и выходной коммутатор 86, раскрытый на фиг. 10.

На фиг. 6 представлена функциональная схема узла этапов 82. Расположение входа и выходов. узла соответствует расположению их на фиг. 5.

Узел содержит счетчик этапов 87, дешифратор этапов на пять выходов 88, счетчик итераций 89, дешифратор итераций на в выходов 90, триггер 91, элементы НЕ 92 и 93, элементы И 94вЂ”

97 (трехвходовой) элемент И 98, (двухвходовые) элементы. ИЛИ 99 и 100 и (трехвходовые) элементы ИЛИ 101 и 102.

На фиг. 7 представлена функциональная схема узла управления считыванием 83. Расположение входов и выходов узла соответствует расположению их на фиг. 5. Узел содержит синхронизатор 103, триггеры 104 вЂ” 106, сдвиговые регистры (на 4 разряда) 107 и 108, выполняющие роль элементов задержки, (двухвходовые) элементы И 109-117, (двухвходовые) элементы ИЛИ 118 - 120, (трехвходовые) элементы И 121 " 125, (трехвходовые) элементы ИЛИ 126 и 127. и элемен" ты НЕ 128 и 129.

На фиг. 8 представлена функциональная схема узла управления записью 84. Расположение входов и выходов узла соответствует расположению

1086438

12 их на фиг. 5. Узел содержит сдвиговые регистры 130 и 131 (на 4 разряда), выполняющие роль элементов задержки, триггеры 132 и 133, (двухвходовые) элементы И 134 вЂ” 139,, (двухвходовые) 5 элементы ИЛИ 140-143, элементы НЕ 144 и 145, (трехвходовые) элементы И 146вЂ”

150;

На фиг ° 9 представлена функциональная схема входного коммутатора, который содержит элементы 2 ИИЛИ 151-155, (трехвходовые) элементы И 156 и 157, (двухвходовые) элементы ИЛИ 158 и 159 и элемент HE 160.

Расположение выходов соответствует расположению их на фиг. 5.

На фиг. 10 представлена функциональная схема выходного коммутатора 86, который содержит (двухвходовые) элементы И 161 и 162, элементы 2ИИЛИ 163-168 и элемент НЕ 169. Расположение входов коммутатора 86 соответствует расположению их на фиг. 5.

Для пояснения работы процессора рассмотрим реализуемый в нем алгоритм быстрого преобразования Фурье (БПФ).

Входная последовательность (Sj) где j =О, 1, 2, ...,N-1, преобразуется в комплексную последовательность 30

$3(j )j, где j =О, 1, 2,...,Й/2-1, путем представления каждой пары со; седних отсчетов комплексным числом, причем четные отсчеты (Ьо,5, +, ° ° °

-P 2) считаются реальными, а нечет- 35 ные (5„, SÝ3, S<, ...,SN „) вЂ” мнимыми частями комплексных чисел. Вычисление коэффициентов Фурье от преобразованной последовательности заключается в вычислении промежуточных коэф- 40 фициентов по базовым формулам алгоритма БПФ:

А; (j ) = A; „(j)+A; „(к) ® м, (1)

А, (к) =A „"(;) -A „"(ê) а"„, (г) где 1 вЂ” номер текущей итерации, 45

1 1, 2, З,...,rn,m=Eoy И-М, % 1 вЂ” значение комплсксного весового коэффициента.

Значение h равно двоичной инверсии кода номера зоны вычислений в итера- 5О ции. Так, для двоичного кода а„, а>, ВЭ ...,м„„, A двоично-инверсный код будет m m-s с 3 с 2 1 код номера зоны представляется rn-разряд.вЂ” ным двоичным кодом. 55

Номера зон на итерациях будут:

1=0 для первой итерации;

1=0,1 для второй итерации;

i =0,1,2,3 для третьей итерации; (1 =0,1,2,3,...,й/ 1-1 для последней итерации.

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

Процессор быстрого преобразования фурье

Патент 1086438