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

( С ке и быть обра цесс рье.облас ния а 5. Поста 1 б ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТНРЫТИИ АВТОРСКОМУ СВИДЕТЕЛЬСТВ(56) Авторское свидетельство СССРВ 1084808, кл. С 06 Р 15/332, 1984Авторское свидетельство СССРЯф 1233167, кл. С 06 Р 15/332, 07.0 УСТРОЙСТВО ДЛЯ АДРЕСАЦИИ ПРОЦЕС-. БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ Изобретение относится к автомати вычислительной технике и можетоиспользовано в системах цифровой отки сигналов при построении про. ров быстрого преобразования ФуЦель изобретения, - расширение ти применения за счет формировадреса произвольной разрядности. вленная цель достигается за счет1305711 того, что в состав устройствавходит К коммутаторов (К - разрядность) 1 - 1, счетчик адреса 2,выходы разрядов счетчика адресов3 - 3, выход переполнения 4 счетчика адресов, сдвговый регистор 5кода итерации, выхопы 6 - 6, разряров сдвигового регистра кода итера 1Изобретение относится к автоматикеи вычислительной технике и можетбыть использовано в системах цифровойобработки сигналов при построении процессоров быстрого преобразования 5Фурье.Целью изобретения является расширение области применения за счет формирования адреса произвольной разрядности. 10На чертеже представлена функциональная схема устройства для адресации процессора быстрого преобразования Фурье.Устройство содержит коммутаторы1 - 1 , счетчик 2 адресов, выходы3, - 3 разрядов счетчика адресов, выход 4 переполнения счетчика. адресов,сдвиговый регистр 5 кода итерации,выходы 6 - 6 разрядов сдвиговогорегистра кода итерации, элементы2 И-НЕ 7, - 7., двухвходовой элементИЛИ 8, двухвходовой элемент И 9, тактовый вход 10 устройства, вход 11 начальной установки устройства, вход 12логической единицы устройства, вход13 разрешения работы устройства, вход14 режима работы устройства, входы15, - 15., разрядов кода параметраустройства, выходы 16, - 16 я разрядовадреса устройства.Устройство работает в двух режимах.Первый режим определяется нулевымпотенциалом на входе 14 режима работы 35устройства и соответствует формированию адресов, по которым записываютсяотсчеты анализируемого входного сигнала. Начальное состояние устройствав первом режиме устанавливается сле дующим образом.На входы 15, - 15разрядов кодапараметра устройства подается двоичции элементы 2 И-НБ 7 - 7 элементИЛИ 8, элемент И 9, тактовый вход 10,вход начальной установки 11, вход логической единицы 12, вход разрешенияработы 13, вход режима работы 14,входы кода константы 15, - 15 выходы разрядов адреса 16, - 16. 1 ил.3 табл. 2ньяи код, зависящий от размера массива записываемых отсчетов. Этот код определяется по следующему правилу: если размер массива И = 2 (ш = 1,К), то на входы 15, - 15, должен подаваться двоичный код числа (И/2-1), причем 15, - вход Яля младшего разряда двоичного кода. Вслед за этим приходит импульс на вход 11 начальной установки устройства, который появляется на выходе элемента ИЛИ 8 и поступает на тактовый вход сдвигового ре" гистра 5 кода итерации и на счетный вход счетчика 2 адресов. Нулевой потенциал, присутствующий на входе 14 режима работы устройства, приходит через элемент И 9, прступает на вход управления сдвигом регистра 5 кода итерации и определяет режим параллель. ного занесения информации в этот регистр. Так как на вторых входах всех элементов 2 И-НЕ 7 - 7, , соединенных с входом 14 режима работы устройства, присутствует нулевой потенциал, то на входы параллельного занесения информации регистра 5 кода итерации будет поступать единичный потенциал с выходов соотвествующих элементов 2 И-НЕ 7 - 7. . Тогда по импульсу на тактовом входе регистр 5 кода итерации установится в состояние "Все единицы". В результате к выходам 16 - 16 разрядов адреса устройства подключатся через соответствующие коим- татары 1, - 1 выходы 3- 3разрядов счетчика адресов в порядке возрастания номера разряда. Так как на пермом входе параллельного занесения информации счетчика 2 адресов, подключенном к входу 12 логической единицы устройства, присутствует логическая единица, а на остальных входах параллельного занесения информации3 13057 счетчика 2 адресов присутствует дво.ичный код, поступивший с входов 15, - 15, разрядов кода параметра, то по импульсу на счетном входе счетчика 2 адресов последний установится в сос 5 тояние, соответствующее двоичному коду числа (И) .Записываемым отсчетам анализируемого входного сигнала соответствуют импульсы на тактовом входе 10 устрой ства, поступающие на тактовый вход счетчика 2 адресов. Счетчик 2 адресов работает в вычитающем режиме. Таким образом, в первом режиме работы устройство формирует адреса, задаваемые 15 счетчиком 2 адресов и равные дополнению номеров отсчетов анализируемого входного сигнала до (И).Второй режим работы устройства онределяется единичным потенциалом на 20 входе 14 режима работы устройства и соответствует формированию адресов при выполнении быстрого преобразования Фурье. Начальное состояние в этом режиме устанавливается следующим образом.Как и в первом режиме, на Входы 15, - 15разрядов кода параметра устройства подается двоичный код чис ла (И/2-1). Вместе с тем на вход 13 разрешения работы устройства подается нулевой потенциал. После этого на вход 11 начальной установки устройства приходит импульс, который проходит через элемент ИЛИ 8 и поступает на тактовый вход регистра 5 кода итерации и на счетный вход счетчика 2 адресов. Так же, как и при начальной установке устройства в первом режиме 40 в счетчик 2 адресов запишется двоичный код числа (И), Нулевой потенциал, присутствующий на входе 13 устройства проходит через элемент И 9, поступает на управляющий вход регистра 5 кода итерации и определяет режим параллельного занесения информации в этот регистр. На первые входы элементов 2 И-НЕ 7, - 7, с входов соответственно 15, - 15 я., поступает код числа (И/2-1). Так как на вторых входах всех элементов 2 И-НЕ 7, -соединенных с входом 14 режима работы устройства присутствует единичный поф0тенциал, то на входы параллельного занесения информации регистра 5 итера. ции будет поступать инверсия двоичного кода числа (И/2-1) с выходов элементов 2 И-НЕ 7, - 7 В результате по импульсу на тактовом вхоце регистр 5 кода итерации установится в состояние, соответсвующее инверсии двоичного кода числа (И/2-1).После этого на вход 13 устройства подается единичный потенциал, что означает готовность устройства к формированию адресов во втором режиме.Принцип адресации, используемый в устройстве, заключается в следующем.Адреса, необходимые для любой К-й итерации быстрого преобразования Фурье, могут быть получены с помощью операции идеального тасования, предполагающей разделение исходного массива из п = 2 последовательных адресов пополам и чередование адресов из двух половин. Обозначим операцию идеального тасования Б(И).Если исходный массив из И последовательных адресов разбить на Р подО 3массивов (Р = 2 , т,с ш) и в каждом из подмасснвов выполнить операцию идеального тасования, то такая операция может быть записана в виде Р Б(И), В соответствии с алгоритмом быстрого преобразования Фурье обработка массива размером И требует ш итераций. Тог да формирование адресов на К-й итерации быстрого преобразования Фурье может быть описано выражением2Б(И), (К = 1,ш).Это выражение означает, что для формирования адресов К-й итерации быстрого преобразования Фурье размером И необходимо сформировать исходный массив последовательных адресов от нуля до (И), разбить исходный масКсив последовательных адресов на 2 подмассивов, а также в каждом из подмассивов выполнить операцию идеального тасования,1В результате получится последовательность адресов, необходимая для адресации операндов,В табл.1 представлен пример формирования последовательности адресов при выполнении третьей итерации 32-точечного быстрого преобразования Фурье (т.е. И = 32; К = 3).Очевидно, что если размер быстрого преобразования Фурье И, с И, то для формирования адресов достаточно взять часть результирующих адресов, полученных для И. Так, в приведенном в Табл. 1 примере первая половина результирующей прследовательности адре13057116сдвиговым регистром 5 кода итерации с й частотой, равной частоте переполнениясчетчика 2 адресов,Единичные потенциалы, присутствующие на входе 13 устройства и на входе14 режима работы устройства, поступаютсоответственно на первый и второйвходы элемента И 9, на выходе которого появляется логическая единица, кос торая поступает на управляющий входрегистра 5 кода итерации и определяетрежим последовательного занесения ином формации в этот регистр.Сигналом считывания операндов для е.15 обработки соответствуют импульсы натактовом входе 10 устройства, поступающие на тактовый вход счетчика 2 - адресов, Счетчик считает в вычитающемрежиме, Импульсы переполнения с выхода й 20 4 переполнения счетчика адресов проходят на вход элемента ИЛИ 8 и поступают на тактовый вход регистра 5 кода в итерации и на счетный вход счетчика 2 и адресов, По импульсу на счетном входесчетчика 2 адресов в него запишетсядвоичный код числа (И), присутствующий на его входах, Так как на входепоследовательного занесения информации регистра 5 кода итерации присутв 30 ствует логическая единица, поступаюс- о щая с входа 12 логической единицыустройства, то регистр 5 кода итераз- ции будет последовательно заполнятьсяединицами со стороны старшего разряда.35 Таким образом, на последней итерациисдвиговый регистр 5 кода итерациибудет находиться в состоянии "Все единицы".Закон коммутации для коммутаторовф 1;- 1 представлен в табл. 2.Закон коммутации для коммутаторов1 - 1представлен в табл. 3. сов представляет собой последователность адресов, необходимую для второитерации 16-точечного быстрого преобразования Фурье (т.е, для И = 16; К= 2),В результате для формирования необходимых адресов достаточно изменятположение младшего разряда счетчикаадресов относительно его остальныхразрядов в зависимости от размера бытрого преобразования Фурье и номеравыполняемой итерации. При выполнениибыстрого преобразования Фурье размерИ = 2 (ш = 1-К) на первой итерациидостаточно подключить выход 3 младшго разряда счетчика адресов к выходу16 ш-го разряда адреса устройства,выходы 3- Зщ разрядов счетчика адресов подключить соответственно к выходам 16, - 16 П разрядов адреса устроства, а выходы Зщ - 3 разрядовсчетчика адресов подключить соответственно к выходам 16, - 160 разрядоадреса устройства, На второй итерацинеобходимо подключить выход 3 младшего разряда счетчика адресов к выходу 16 щ , (ш)-го разряда адреса устройства, вь 1 ходы З ,разрядовсчетчика адресов подключить соответственно к выходам 16- 16 и- разрядоадреса устройства, а выходы 3 - 3 отальных разрядов счетчика адресов -соответственно к выходам 16- 16 О рарядов адреса устройства. На третьейитерации необходимо подключить выхоь,3 младшего разряда счетчика адресовк выходу 16 ш (ш)-го младшего раэряда адреса устройства, выходы 33,. разрядов счетчика адресов соответственно к выходам 16 - 16, разрядов адреса устройства а выходы3 - 3остальных разрядов счетчикаадресов - соотвественно к выходам16 - 16 азт-Р Рядов адреса устрой- Формула изобретенияства и т.д. 45Таким образом, на ш-м этапе преобразования порядок следования разрядов счетчика 2 адресов на выходах 16, - 16 разрядов адреса устройства оказывается первоначальным (как при записи входной информации в первом режиме),Описанная перегруппировка разрядов счетчика 2 адресов происходит с помощью коммутаторов 1 - 1 я, на выходе каждого из которых появляется один из трех (двух - для коммутаторов 1- 1) входных информационных сигналов. Управление переключением осуществляется Устройство для адресации процессора быстрого преобразования Фурье, содержащее К коммутаторов, (К - разрядность формируемого адреса) сдвиговыйрегистр кода итерации, элемент ИЛИи счетчик адресов, тактовый вход которого является тактовым входом устройства, выход переполнения счетчика адресов подключен к первому входу элемента ИЛИ, второй вход которого является входом начальной установки устройства, а выход элемента ИЛИ подключен к тактовому входу сдвигового13057 Таблица 1 Номер подмассива Исходный массивпоследовательныхадресов 00000 00100 00000 00001 00001 00010 00101 00011 00010 00100 00110 00101 00011 00110 00111 00111 01000 01100 01000 01001 01010 01001 01101 01011 01010 01100 регистра кода итерации, вход последовательного занесения информации которого является входом задания логической единицы устройства, первый информационный вход К-го коммутатора подключен к выходу первого разряда счетчика адресов, первый информационныйвход х".го (х - 1,й - 1) коммутатораподключен к выходу (х + 1)-го разрядасчетчика адресов, второй информационный вход К-го коммутатора подключенк выходу К-го разряда счетчика адресов, второй информационный вход .-гокоммутатора подключен к выходу первого разряда счетчика адресов, третий 15информационный вход 1-го (1 = 2,К)коммутатора подключен к выходу 1-горазряда счетчика адресов, выход 1-го( = 1,К) коммутатора является.выходом 1-го разряда адреса устройства, 20о т л и ч а ю щ е е с я тем, что, сцелью расширения области примененияза счет Формирования адреса произвольной разрядности, в него введены (К)элемент 2 И-НЕ и элемент И, первый 118вход которого является входом разрешения работы устройства, выход 1-го разряда сдвигового регистра кода итерации подключен к первому управляющему входу (1+1)-го коммутатора и второму управляющему входу х-го коммутатора, первый вход 1-го элемента 2 И-НЕ объединен с (+1)-м входом параллельного занесения информации счетчика адресов и является входом -го разряда кода параметра устройства, вторые входы всех элементов 2 И-НЕ объединены,с вто. рым входом элемента И и являются входом режима работы устройства, первый вход параллельного занесения информации счетчика адресов подключен к входу логической единицы устройства, счетный входсчетчика адресов подключен к выходу элемента, ИЛИ, выход -го Ълемента 2 И-НЕ подключен к -му входу параллельного занесения информации сдвигового регистра кода итерации, выход элемента И подключен к входу управления сдвигом сдвигового регистра кода итерации. Результирующая последовательность адресов13057 11 30 Продолжение габл. 1иМ Ш Е01101 01110 01110 01011 01111 01111 10000 10000 10001 10100 10010 10001 10011 10101 10100 10010 10101 10110 10110 10011 10111 10111 11000 11000 11001 11100 11010 11001 11011 11101 11100 11010 11101 11 110 11110 11011 11111 11111 Таблица 2 Управляющий вход Номер информационного входа,коммутируемого на выход 0Номер информационного входа,коммутируемого на выход Управляющий входЗаказ 1454/48 Тираж 673 Подписное ВНИИПИ Государственного комитета ССГР по делам изобретений и открытий 113035, Москва, Ж, Раушская наб. д. 4/5