Устройство для выделения значащих разрядов из последовательности многоразрядных двоичных кодов Советский патент 1983 года по МПК G06F7/06 

последовательного выделения значащих разрядов, выход регистра результата К-блока для последоаателйного выдб ления значащих разрядов является информационмым выходом устройства, выход каждого -го накопителя соединен с вторым информационным входом узла выделения значащих разрядов -го блока для последовательного выделения значащих разрядов, выходы всех узлов оценки количества значащих разрядов, кроме первого, соединены с соответсгеующими входами второй группы входов узла управления, первый и второй выходы которого соединены соответственно с управляш.1,И1М входом узла выделения значащих разрядов, со стробирущим входом дешифратора и управляющим входом регистра рез Лзтата первого блока для последовательного выделения значащих разрядов, каждый нечетный i-й выход узла управления соединен с упрзвлжсидими входами промежуточного регистра и узла выделения значащих разрядов соответствующего блока для последовательного выделения значащих разрядов, каждый четный 1-й выход узла управления соединен с управляющим йхолсм регистра результата и стробирущим входом дешифратора соответствующего блока для последовательного выделения значащих разрядов, тй:ч1овый вход узла выделения знэча( разоядов каждого блока для последовательного выделения значащих разрядов соединен с тактовым входом устройства.

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

1

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

соединен с вторым входом элемента ИЛИ группы и с выходом узла.

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

k. Устройство по п. 1, отличающееся тем, что узел управления содержит два элемента И и (2К-2 ) элементов 2И-ИЛИ, причем первые пря мые входы двух элементов И,всех элементов 2И-ИЛИ и вторые прямые входы (2К-3)-го и (2К-2)-го элементов 2ИИЛИ соединены с входом узла, первый и второй входы первой группы входов узла соединены соответственно с вторым прямым и инверсным входами первого элемента И, i-й вход (Й,..., (2К-3)) первой группы входов узла соединен с вторым прямым входом (i-l)-ro элемента 2И-ИЛИ, третьи и четвертые прямые входы {2К-3) и (2К-2)-го элементое 2И-ИЛИ соединены с соответствующими входами первой группы входов узла, инверсный вход 1 -го элемента 2И-ИЛИ (1 1,..., (2К-2)) соединен с (+2)-м входом первой группы входов узла, третий прямой вход 1-го элемента 2И-ИЛИ {Г 2,...,(2К-) соединен с )-м входом второй группы входов узла, ятый прямой вход (2К-2 )-го элемента 2И-ИЛИ соединен с соответствующим

входом второй группы входов узла,второй вход второго элемента И соединен с соответствующим входом первой группы входов узла, третьи прямые входы нечетных элементов 2И-ИЛИ, кроме (2К-3)-го элемента 2И-ИЛИ, соединены с выходами последующих нечетных элементов 2И-ИЛИ, четвертые прямые входы четных элементов 2И-ИЛИ, кроме (2К-2)-го элемента 2И-ИЛИ, соединены с выходами последующих нечетных элементов 2И-ИЛИ.пятый прямой вход

(2К-5)-го элемента 2И-ИЛИ соединен с выходом (2К-2)-го элемента 2И-ИЛИ, выходы двух элементов И и всех элементов 2И-ИЛИ соединены с соответствуюцими выходами узла.

1

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

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

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

Как правило, поиск активных событий реализуется программно на универс льных ЭВМ, что приводит к .: большим затратам времени.

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

Зто устройство требует одновременной подачи на его входы данных об ак тивности всех возможных событий и содержит блок выделения единиц с шифратором запрета обработанных разрядов шифратор номера разряда выделенной единицы, первый и второй регистры хранения этого кода и дешифратор двоичного кода номера разряда выделенной единицы. Причем, выходы блока выделения единиц соединень с входами шифратора, выходы которого соединены с входами первого регистра, выходы первого регистра соединены с входами второго регистра, выходы которого соединены с входами дешифратора,выходы дешифратора соединень с входами из первой групп входов блока выделения единиц, в/орая группа входов блока выделения соединена с группой внешних входов устройства С2 }.

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

устройства, велик.

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

Поставленная цель достигается

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

состоящий из узла выделения значащих разрядов, шифратора; дешифратора и регистра результата, причем выход узла выделения значащих разядов соединен с входом шифратора,

выход которого соединен с первым информационным входом регистра результата и адресным входом дешифратора, выход дешифратора соединен с пер вым информационным входом узла

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

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

входами всех накопителей, кроме первого, и R-входом триггера режима, второй и третий входы данных и разрешения устройства соединены соответственно с информационными входами и входами разрешения записи накопителей, четвертый вход адреса устройства соединен с первыми адресными входами всех, накопителей, кроме первого и с адресным входом первого накопителя, пятый вход запуска чтения устройства соединен с 3 Входом триггера режима и с управляо1цим входом руггистра запуска чтения j выходы которых соединены соответстеенно с входом и первой группой бходоа узла у.;разпения, в каждом бло ке для последовательного выделения значащих разрядов аыход узла выделения ,HaMau4Hx разрядов дополнительно соединен входом узла оценки количест зэ значаи их разрядов, второй информационный вход регистра результата в каждом блоке для последовател ного выделения значащих разрядов, кр ме первого; соединен с выходом проме жуточ)ого регистра, а в первом блоке ,цля паследозательного выделения зна -;ащих разрядов - с выходом узла оцен ки колимества значащих разрядов,выход регистра результата з каждом -м блоке (i 1s, . ,.,К) для последовательного выделения значащих разрядов кроме . соединен с вторым адресным входом (i+l)-ro накопителя и информационным входом промежуточного регистра (1 + 1 )-го блока для последовательного выделения значащих разрядов, вылод регистра резу/1ьтата К-го блока для последоЕательного выделения знамаи(их разрядов является информационным зыходом устройства, выход к:э чдого г-го накопителя соединен с втор:.м информационным аходом узла выделения значащих разрядов 1-го блока для последовательного выделени значащих разрядов, эыходы всех узлов оценки колимества значащих разрядов, кроме ггервого, сседине1- Ы с соответствующими входами второй группы вход узла управления, первый и второй выходы которого соединены соответственно с управлящими входом узла выделения значащих разрядов5 со стро бируюид.им входом дешиф эатора и управляющим входом регистра результата первого блока для последовательного выделения значащих разрядов, каждый нече ный i-й выход узла управления соединен с управля(Оа1ими входами промежуточного регистра и узла выделения значащих разрядов соответствущего блока для последовательного выделения значащих разрядов, каждый четный выход узла управления соединен с управляющим входом регистра результата и стробирующим входом дешифратора соответствующего блока для последовательного выделения значащих разрядов, тактовый вход узла выделения значащих разрядов каждого блока для последовательного выделения значащих разрядов соединен с тактовым входом устройства. Кроме того, узел выделения значащих разрядов содержит группу элементов ИЛИ, группы элементов 2И-ИЛИ и группу триггеров, причем первые входы всех элементов ИЛИ группы соединены с первым информационным входом узла, Еуход каждого элемента ИЛИ группы соединен с первым входом соответствующего элемента 2И-ИЛИ группы, второй и третий входы которого соединены с управляющим входом узла, четвертый вход каждого элемента 2И- группы соединен с вторым информационным входом узла, выход каждого элемента 2И-ИЛИ группы соединен с Dвходом соответствующего триггера группы, С-вход которого соединен с тактовым зходом узла, выход каждого триггера группы соединен с вторым входом элемента ИЛИ группы и с выходом узла. Кроме того, узел оценки количества значащих разрядов первого блока для последовательного выделения значащих разрядов содержит элемент И-НЕ, входы и выходы которого соединены соответственно с входом и выходом узла, а узлы оценки количества значащих разрядов всех остальных блоков для последовательного выделения значащих разрядов содержат два шифратора, группу схем сравнения и элемент И, причем входы первого и второго шифраторов соединены с входом узла, выходы первого шифратора соединены с первыми входами соответствующих схем сравнения группы, вторые входы которых соединены с соответствующими выходами второго шифратора, выходы схем сравнения группы соединены с соответствующим входами элемента И, выход которого соединен с выходом узла. Кроме того, узел управления содержит два элемента И и (2К-2) э/зементоа 2И-ИЛИ, причем первые прямые входы двух элементов И, всех элементов 2И-ИЛИ и вторые прямые входы,(2К-3)-го и (2К-2)-го элементов 2И-ИЛИ соединены с входом узла, первый и второй входы первой группы входов узла соединены соответственно с вторым прямым и инверсным Входами первого элемента И, i-й вход (i 2,.,.(2К-3)) первой группы вхоДов узла соединен с вторым прямым входом (i-l)-ro элемента 2ИИЛИ, третьи и четвертые прямые входы (2К-3) и (2К-2)-го элементов 2И-ИЛИ соединены с соответствующими входами первой группы входов узла, инверсный вход i-ro элемента 2И-ИЛИ (i ,... ,{2К-2)) соединён с (1+2 )входом первой группы входов узла, третий прямой вход i-ro элемента 2И-ИЛИ (f 2,...,(2К-4)) соединен с (i-l)-M входом второй группы входов узла, пятый прямой вход (2К-2)-го элемента 2И-ИЛИ соединен с соответствующим входом второй группы входов узла, второй вход второго элемен та И соединен с соответствующим входом первой группы входов узла, третьи прямые входы нечетных элементов 2И-ИЛИ, кроме (2К-3)-го элемента 2И-ИЛИ, соединены с выходами последующих нечетных элементов 2И-ИЛИ, четвертые прямые входы четных э(} ементов 2И-ИЛИ, кроме (2К-2 )-го элемента (2И-ИЛИ, соединены с выходами последу ющих нечетных элементов 2И-ИЛИ,пятый прямой вход (2К-3)-го элемента 2И-ИЛ соединен с выходом (2К-2)-го элемент 2И-ИЛИ, выход двух элементов И и всех элементов 2И-ИЛИ соединены с соответствующими выходами узла. На фиг. 1 представлена блок-схема устройства; на фиг.2 - блок-схема узла выделения значащего разряда;. на фиг.3,4 - блок-схема узлов оценки количества значащих разрядов .для первого и последующих блоков для последовательного выделения значащих разрядов; на фиг.5- блок-схема узла управления. Устройство содержит накопители 1-4 (2,3 и 4 - накопители с мультиплексором на адресном входе),блок 5 управления чтением, состоящий из триггера 6 режима, регистра 7 запуска чтения, узла 8 управления первый вход 9 устройства, группа вторых входов 10 устройства, третий вход 11 управления, четвертый вход 12 устрой ства, пятый вход 13устройства , 10 5. послёдовательного выделения значащих разрядов,каждый из которых содержит узел 15 выделения значащих разрядов,шифратор 16,дешифратор 17,узел 18 оценки количества значащих разрядов, регистр 19 результата. Блоки l з держат промежуточный регистр 20 и выход 21 устройства. Узлы 15 содержат выходы 22-2 триггеров 25,группу элементов ИЛИ 26, группу элементов 2И-ИЛИ 27. Узел 18 блока содержит элемент И-НЕ 28. Узлы 18 блоков k2,, соцержат шифраторы 29,30,группу схем 31 сравнения, элемент И 32. Узел 8 содержит элементы 2И-ИЛИ ,элементы И Ц и 42. Для удобства описания работы устройства допустим, что: а)число возможных событий равно 4096 б)каждый БПВР выделяет значащие разряды из 8-разрядного слова; с) признаком активности события является логический О. В устройстве,в последнем накопителе k для каждого конкретного возможного события отведен один бит памяти. адрес которого соответствует двенадцатиразрядному (согласно а) номеру этого события в списке возможных событий, и в который записывается О (согласно с) в случае, если событие активно. Обозначим разряды, номера событий, начиная со старшего разряда символами HCil, НС10,...НС1,НСО. Учитывая допущение (в)7Органиауем накопитель 4 в виде 512 восьмиразрядных слов, в каждом из которых могут быть (а могут и не быть) активные разряды. Причем номер разряда в слове соответствует коду трех младших разрядов номера события НС2,НС1, НСО, а номер слова соответствует коду старших его разрядов НС11, нею,..., нс4,нсз. Для организации оперативного поиска слов накопителя 4, содержащего активные paзpядыi предназначен накопитель 3, содержащий столько бит памяти, сколько слов в накопителе 4. Накопитель 3 организованный в составе 64-х восьмиразрядных слов, в которых, аналогично сказанному выше, могут быть (а могут и не быть) активные разряды. Причем номер 7 ряда и слове соответствует коду оаз оядов НС5. НСч, НСЗ, а номер слов в накоп11телях 1-3 соответствует код разрядов -НС11, нею, .,.,НС7,НСб. Для того,чтобы организовать опе ративный поиск слов накопителей 1-3 содержащих активные разряды, предна начен накопитель 2, организованный в составе 8-ми зосьмиразрядных. слов. Причем номер разряда в слове соответствует коду разрядов ,HC7 неб, а номер слова - коду разрядов НСП ,НС10,НС9. Соответстванпо накопитель 1 орга низозсн в виде одного восьмиразрядн го слова, номер разряда в котором соответствует коду СП, НСЮ, НС9. Устройство работает .B режимах записи, чтения и стирания. В режиме ззписи мультиплексоры -Ч постоянным сигналом макопитеГеи ЗГ( с эходОЗ 9 устройства соответственно настраиваются на передачу адреса ,::ап:|си (ИС11, ИС1 О , . . . ,ИСО Ь с входов 10 устройства этим же сигн лом устанавливается в О триггер режима 6. При этом на всех выходах узла U устанавливаются сигналы О . Логический О , поступающий с третьего входа 11 устройства, при каждол импульсе записи, поступаюидем с четвертого входа 2 устройства за писывае гся в наког;мт-ели 2- по со о т в е т ст Q у lau им адресам. Этот процесс происходит пока со бытия активизирозйны. По окончании записи в накопителе 4 помечены О все биты, номера которых соответству ют номеру активных событий, в накопи теле 3 помечены О сгюва накопитепя ч, 3 котором встречаются активные события и т.д., в накопителе 1 (Юрмемены слоза накопителя 2, в Котором встречаются активные события При этом .многократная активизация од ного ц. voro ке события равносильна единственной его активизации. Режим чтения начинается с измене нием, сигнала ЗП на входе 9 и подачей сигнала на вход 13 устройства. По этому сигналу триггер 6 устанавливается в 1, на все разряды регистра 7 принимаются значения логического нуля, а мультиплексоры накопителей 2- настраиваются на прием адреса с соответствующих регистрС)В 19 результата . С прекрнщением подали с.иг1-;аг;а нл 5ход 13 уС ройс:ча регистр 7 ночича58ет заполняться в режиме сдвига логи ческими единицами, При этом проис .jдит следующее; Первый такт. Р31 1,Р32 0 -происходит прием на узел 15 блока 1 содержимого накопителя 1; Второй такт. Анализируется содержимое узла 15 блока 1, на выходе шифратора 16 форм руется адрес младaiero активного триггера узла 15 (по сути соответствующий старшим раЗ рядам .номеров активных событий из 1/8 части всех возможных событий списка},на выходе узла 18 блока 1 формируется сигнал признака активности АКТ1, на выходе дешифратора формируется сигнал сброса активности данного млади его активного триггера. Третий такт. Приведен в пассивное состояние младший активный триггер узла 15 блока 1,j,Ha выходе шифратора 16узла 1 формируются соотеетстаенно номер следующего активного триггера и признак того, что этот триггер не последний, на выходе дешифратора 17- сигнал сброса этого триггера. Одновременно, сформированные во 2-ом такте признак активности и номер актизного триггера узла 15 блока 1., соответствующий адресу одного из блоков накопителя 2, приняты на регистр пезультата 19. Четвертый такт. Первый блок 1 работает так же, как и в Зем такте, 1 слово из 64-х слов накопителя 2 принимается на узел 15 блока 2 и появляется на его выходах узла 15 , на выходах шифратора 16 появляется и поступает на первые входы регистра 19 номер младшего активного триггера узла 15 (по сути соответствующий средним разрядам номеров активных событий из 1/64 части всех возможных событий списка), старшие его разряды вместе с признаком активности появляются на выходах регистра 20 и поступают на вторые входы регистра 19. В узле 18 блока и узле 8 формируется сигнал, разрешающий либо перевод 3; пассивное состояние младшего активного триггера, узла 15, если активных триггеров 71, либо прием на узел 15 следующего слова из накопителя 2. В первом случае процесс формирования оставшихся разрядов но,мера активного события в блоках и 1 лроисходит описанным выше способом, в результате к. выходах регистра 19 блока 1 н (г-орьируется полный номер активного события, первого в списке возможных событий, затем второго и т.д. до тех пор,пока не сбросится в узле 15 блока последний активный триггер, и пока не .исчезнет значение активности на выходе узла 18 блока 14, Когда в узле 15 блока пишутся данные об активности последней части списка, исчезнет значение активности в соответствукщем триггере регистра 19 блока It.При очеред ном приеме в узле 15 блока 2 -исче нет признак активности из соответст вующего триггера регистра 20 блока и так далее, пока не исчезнет признак активности в регистре 1 блока 1 4510Исчезновение активности в реги стре 19 блока 1 служит сигналом конца чтения. Стирание записанной в накопителе информации производится так же,как и запись. Отличие состоит лишь в том, что на информационные входы ИС памяти подается признак неактивности, т.е. логическая единица. Перебор адресов при стирании может производиться либо по списку номеров активных событий, полученных при последнем чтении, либо подряд,если такого списка нет (например, после включения схемы). Использование предлагаемого устройства позволяет уменьшить оборудование и повысить быстродействие устройства.

сриг.2

п

С А/Х-бЗ

о

JL

/5

N

гцcSbl. О-

П

18

Л

2Ъ

lAZy/

2S Л

Tfojaot/

I

cpus.d

я

I

п

fS

cpuf.