Формирователь адреса Советский патент 1983 года по МПК G06F9/36 

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

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

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

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

Недостатком этого устройства является отсутствие средств для мульт плексирования адресов, что существенно ограничивает выбор элементной базы ОЗУ устройств, на которые работает это устройство.

Наиболее близким по технической сущности к изобретению является устройство для формирования адресов, содержащее счетчик адреса, счетчик итерации (счётчик шага преобразования), группу элементов ИсключающееИЛИ, первый коммутатор, второй коммутатор, причем адресный вход первого коммутатора соединен с выходом счетчика итерации, а информационный вход коммутатора соединен с выходом счетчика. Выход первого коммутатора соединен с адресным входом второго коммутатора. Кроме того, выходы счетчика адреса и группы элементов Исключающее ИЛИ являются выходами устройства 2} .

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

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

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

5 блока элементов Исключающее первый выход которого является вторым выходом старших разрядов адреса формирователя, с выходом младших разрядов адреса формирователя явля0 ется второй выход блока элементов Исключающее ИЛИ, первый и второй выходы блока элементов Исключающее ИЛИ соединены с первым и вторым входами данных счетчика адреса, тре5 тий и четвертый входы блока элементов Исключающее ИЛИ соединены с соответствующими выходами постоянного запоминакщего -устройства, вход итераций которого соединен с выходом счетчика итераций, группа управляющих входов постоянного запоминакщего устройства соединена с группой выходов дополнительного счетчика и с группой информационных входов второго дополнительного комму5 татора, первый и второй адресные входы которого соединены соответственно с первым и вторым входами режима формирователя и с первым и вторым адресными входами постоянного эапо0 минающего устройства, первый вход режима формирователя соединен с первым входом формирователя импульсов, второй вход которого соединен с выходом первого коммутатора, а выход подсоединен к входу установки счет чика адреса и к первому входу пер вого элемента ИЛИ, второй вход которого подсоединен к тактируюшему входу формирователя, выход первого элемента ИЛИ заведен на счетный вх -дополнительного счетчика и на инфо мационный вход второго дополнитель ного коммутатора, выход которого соединен со счетным входом счетчика адреса, выход переполнения которого соединен с первым -входом де мультиплексора, второй вход Которо соединен с третьим входом режима ф мирователя, первый и второй выходы демультиплексора соединены соответ венно с инкрементным и декрементны входами счетчика итерации, первый вход второго элемента ИЛИ соединен с первым разрядом группы выходов дополнительного счетчика, второй вход второго элемента ИЛИ - с вторым входом режима формирователя, а выход соединен с третьим входом первого дополнительного коммутатора, первый выход счетчика адреса является адресным выходом формирователя. На фиг. 1 приведена блок-схема устройства; .на фиг. 2 - прямой граф алгоритма быстрого преобразования Уолша; на фиг. 3 - цифроинверсный граф этого алгоритма; на фиг. 4 - элементарная (базовая) оп рация преобразования; на фиг. 5 временная диаграмма управляющего сигнала, снимаемого с формировател импульсов; на фиг. б - приведен граф алгоритма преобразования Уолш при параллельном генерирования адр сов. Формирователь адреса содержит счетчик 1 адреса, счетчик 2 итера,ции, дополнительный счетчик 3, демультиплексор 4, постоянное запо минающее устройство (ПЗУ) 5, блок элементов Исключающее ИЛИ, первый дополнительный коммутатор 7, второй элемент ИЛИ 8, первый коммутатор 9 второй коммутатор 10, формирователь 11 импульсов, первый элемент ИЛИ 12 второй дополнительный коммутатор 13 тактирующий вход 14 устройства, вход 15 режима (признака варианта) входы 16 и 17 режима (признаков функции) устройства, выходы 18-21 выдачи адресов, входы 22 и 23 потока данных, выходы 24 и 25 потока данных. Работу устройства рассмотрим в следующей последовательности; генер рование адресов верхнего и нижнего ряда на один адресный выход (,18 и 1 без мультиплексирования; генерирова ние адресов верхнего и нижнего ряда в один адресный выход (19) с мультиплексированием; генерирование адресов на два адресных выхода (18 и 19) , (20 и 21 без мультиплексирования; генерирование адресов надва адресных выхода (19 и 21) с муль|Типлексированием. При этом сначала 1расмотрим устройство -для генериро1вания адресов для прямого преобразо вания, затем для цифроинверсного варианта (фиг. 3). При выполнении первой функции на входах 15 - 17 должны быть установлены единицы. Единицана входе 15 соответствует прямому преобразоанию (фиг. 2), при этом демультиплексор 4 пропускает сигнал, посту, пающий по второму входу на инкрементный вход счетчика 2 итерации. Единица на 16 входе открывает формирователь 11 импульса и совместно с единицей на 17 входе открывает четвертый канал коммутатора 13. Кроме того, единица на входе 17 блокирует элемент ИЛИ. 8, т.е. на выходе этого элемента всегда 1, которая в коммутаторе 7 держит в открытом положении второй канал, что обеспечивает подачу на второй вход вто-рой половины элементов Исключающее }ШИ 6 значения старшей половины счетчика 1, а значение младшей половины счетчика непосредственно подано на второй вход первой половины элементов Исключающее ИЛИ. Следовательно, адрес на выходах 18 и 19 зависит от того, что подано на пер- „ вые входы элементов Исключающее ИЛИ.. При подаче на первый вход этих эле ментов нулей на их выходе установится адрес верхнего ряда, а если подать унитарный код номера итерации, то на выходах 18 и 19 сформируется адрес нижнего ряда. Р менно на этом основании возможно генерирование адресов верхнего и нижнего ряда на одном адресном выходе. Прошивка ПЗУ 5 составлена так, что при единицах на входах 16 и 17 выбор нулевых содержимых или унитарного кода текущей итерации управляется выходом счетчика 3. Рассмотрим в динамике генерацию адресов для одной базовой итерации. Пусть это для определенности будет вторая базовая операция на третьей итерации. Тогда двоичное представление цифры 2 с выхода счетчика 1 подается на элементы Исключающее ИЛИ, так как при этом счетчик 3 имеет нулевое значение. То из ПЗУ 5 выбирается содержимое ячейки по адресу 101100. В таблице приведена Прошивка ПЗУ. из таблицы находим, что содержимое равно .000, следовательно верхний адрес равен 0010. По следующему такту по входу 14 сигнал через элемент ИЛИ 12 поступает на счетный вход счетчика и наращивает на единицу. А это в свою очередь влечет изменение адреса ячейки ПЗУ которое будет 101101. Содержимое 100, а следовательно адрес нижнего ряда будет 100® 010 110. Как видно из графа фиг. 2 , именно такой адрес у операнда нижнего ряда При следующих двух тактовых импульсах по входу 14 легко увидеть, что адреса повторяются. Это необходимо для загрузки результатов базовой операции ОЗУ по тем же адресам, по которым осуществляется выбор операн дов. На следуквдем такте второй разряд счетчика 3 инвертируется, задни фронт этого сигнала через коммутато 13 наращивает счетчик 1 на едийицу, а это соответствует переходу на сле дующую базовую операцию, и начинает ся генерация адресов.для этой рпера ции. Если посмотреть на граф на фиг. 2, то можно увидеть, что содержимое счетчика 1 изменяется кусочно-линейно, причем линейная груп па адресов т.е.адреса,которые отлиотличаются от предьвдущего на едиййц постоянна на итерации и возрастает в два раза на последующей итерации. Счетчик 1 необходимо перестраивать на начальный адрес линейной группы. Это осуществляется коммутатором 9. Из графа видно, что такую перестрой ку надо производить каждый раз при появлении единицы в разряде счетчика 1, соответствующем номеру итерации. Поэтому в силу соединения коммутатора 9 со счетчика 1 и 2 еди ница на выходе, коммутатора 9 появляется именно в момент перестройки счетчика 1. А суть перестройки заключается в том, что в счетчик 1 заносится адрес нижнего ряда текущей базовой операции и наращивается на Единицу. Сигнал за:пйси в счетчик 1 по переднему фронту еди ницы на выходе коммутатора 9 формир ется формирователем 11 импульса, задним фронтом которого через элемент ИЛИ 12 счетчик 1 наращивается на единицу. Дальше устройство рабо тает как описывалось. Признаком кон ца итерации является сигнал перепол нения .счетчика 1, который увеличивает на единицу номер итерации на счетчике 2 через демультиплексор 4, а сам обнуляется и возвращается к нулевому адресу следующей итерации. Рассмотрим вторую функцию устрой ства, при которой на входе 17 уста новлено нулевое состояние. Это состояние открывает элемент ИЛИ 8 для прохождения сигналов по его первому входу, т.е. в зависимости от первог разряда счетчика 3 коммутатор 9 открывает первый или второй канал. У коммутатора 13 открыт третий Канал, т.е. счетчик 1 наращивается по переполнению третьего разряда счетчика 3. В этой функции ПЗУ 5 при 000 на счетчике 3, как видно из таблицы выставляет на выходе нули, а коммутатор 7 коммутирует первый канал, т.е. на второй вход элементов Исключающее ИЛИ б подает содержимое младшей половины, следовательно на выходе 19 имеет младщую половину адреса верхнего ряда. Это же состояние у ПЗУ 5 и при 001, а коммутатор 7коммутирует на вход элементов 6 старшую половину счетчика 1. Следовательно, на выходе 19 появляется старшая половина адреса верхнего яда. Но при следующей комбинации 010 ПЗУ 5 выставляет на втором выходе 1чл ад1иую половину унитарного кода и так как с выхода коммутатора снимается младшаяполовина счетчика 1 (О в первом радряде счетчика З}, на выходе 19 формируется младшая по.ловина адреса нижнего ряда и при следующей комбинации 011 - старшая половина, а по первому выходу ПЗУ 5 выставляет младшую половину унитарного кода номера итерации, так же как в предыдущей функции. Следовательно на выходе 18 будут младшие разряды адреса нижнего ряда, а на выходе 19 поочередно появляются младшие и старшие разряды адресов верхнего и нижнего ряда, причем при старших разрядах адреса нижнего ряда на выходе 19 на выходе 18 формиру ются младшие разряды, что весьма важна при переустановке счетчика 1. 8остальном работа устройства совпадает с работой при первой функции. Устройство выполняет третью функ-п цию, когда на входе 16 установлен О, При этом формирователь 11 импульса оказывается заблокированным потому, что при генерировании адресов верхнего и нижнего ряда не возникает необходимости переустановки счетчика 1. У коммутатора 13 открыт первый канал, тактирующие импульсы с входа 14 одновременно подаются на счетчики 1 и 3, сигналом единичного уровня элемент ИЛИ 8 заблокирован так же, как и в первом случае. Поэтому на выходах 20 и 21 в этом случае всегда содержимое счетчика является адресом верхнего ряда, а адрес нижнего ряда снимается с выходов 18 и 19, причем с выхода 18 - младшие разряды, а с выхода 19 - стар- , шие разряды адреса нижнего ряда. ПЗУ 5 дешифрирует.номер итерации как 2 -1, где k - номер итерации. Отсюда адрес нижнего ряда на элементах б формируется как сумма по Wiod 2 текущего адреса верхнего адреса и комбинации 2 -1. Граф для этого случая приведен на фиг.4. В прямоугольниках, которые располо

жены на узлах графа, указаны адре са ячеек, в которые засылаются, а на следующей итерации выбираются операнды. Самый старший разряд отделен от остальных разрядов для того, чтобы подчеркнуть номер блока ОЗУ, адресом которого является данный адрес. Особенность генерирования адресов при этой функции заключается в том, что данные на предыдущей итерации должны распределяться так, чтобы на последующей итерации можно было бы обеспечить одновременную выборку операндов-базовой операции. Это возможно только тогда, когда операнды базовой операции размещены в разных блоках ОЗУ. Поэтому не достаточно только Формирования адреса нижнего ряда в виде суммы по mod 2 текущего значения адреса верхнего ряда и комбинации 2 -1, но еще необходимо управление потоком данных, которое обеспечивается коммутатором 10 управляемым коммутатором 9. Отметим, что в. этой функции предлагаемое устройст-i во работает абсолютно идентично известному.

И наконец, рассмотрим последнюю функцию, которая во многом совпадает с вторым случаем. Различия только в том, что адреса верхнего ряда .снимаются с выхода 21, а нижнего,, ряда - с выхода 19. Счетчик 1 адреса наращивает свое содержимое по переполнению счетчика 3. Коммутатор 9 и 10 работают так же, как в третьей функции.

Для цифроинверсных,вариантов (фиг. 3) на входе 15 установлен О При этом счетчик 2 работает в декрементном счете (реверсивном). Сле- , довательно в исходном состоянии в этом варианте счетчик 2 имеет максимальное значения, т.е. 11...1. Поэтому генерирование адресов начинается относительно прямого варианта с последней итерации, а при переходе на следующую итерацию из счетчика 2 вычитается единица. В остальном нет никаких различий в работе устройства.

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

Продолжение таблигул

11

10

XI

15

00

20

01

25

10

30

10

35

11

40

45

01

XX

50

00

55