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

СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСКИХРЕСПУБЛИК ИЯ ЕТ н(53) 681 325 Бюл. Ю 3омаковский Е. Л. ЛевиГ,Л,"По"числи 18,ство1968 ГОСУДАРСТВЕННЫЙ КОМИТЕТ ССПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТ ПИСАНИЕ И(088. 8) (56) 1. Рябов Г.Г., Лакш элементное моделирование тельных систем",-Преприн ИТМ и ВТ; М., 1978,2. Авторское свидетел У 278215, кл. С 06 Р 5/О (прототип),(54 )(57 ) 1. УСТРОЙСТВО ДЛЯ ВЫДЕЛЕНИЯЗНАЧАЩИХ РАЗРЯДОВ ИЗ ПОСЛЕДОВАТЕЛЬНОСТИ МНОГОРАЗРЯДНЫХ ДВОИЧНЫХ КОДОВ,содержащее блок для последовательного выделения значащих разрядов, состоящий из узла выделения значащих разрядов,шифратора,дешифратора и регистрарезультата, причем выход узла выделения значащих разрядов соединен свходом шифратора, выход которого соединен с первым информационным входомрегистра результата и адресным входом дешифратора, выход дешифраторасоединен с первым информационнымвходом узла выделения значащих разрядов, о т л и ч а ю щ е е с я тем,что,с целью уменьшения оборудования иувеличения быстродействия, оно содержит К (К - число групп значащихразрядов) блоков для последовательного выделения значащих разрядов,Кнакопителей, триггер режима, регистрзапуска чтения и узел управления,ав каждый блок для последовательноговыделения значащих разрядов дополнительно введен узел оценки количества значащих разрядов, во все блоки,801038935 для последовательного выделения значащих разрядов, кроме первого,введен промежуточный регистр, причем первый вход режима устройства соединен с управляющими входами всех накопителей, кроме первого, и й-входом триггера режима, второй и третий входы данных и резрешения устройства соединены соответственно с информационными входами и выходами разрешения записи накопителей, четвертый вход адреса устройства соединен с первыми адресными входами всех накопителей, кроме первого, и с адресным входом пераого накопителя, пятый вход запуска чтения устройства соединен с о 5-входом триггера режима и с управляющим входом регистра запуска чтения, выходы которых соединены соответственно с входом и первой группой входов узла управления, в каждом блоке для последовательного выделения значащих разрядов выход узла выделения значащих разрядов допол нительно соединен с входом узла оценки СР количества значащих разрядое,второй МФ информационный вход регистра резуль тата в каждом блоке для последователь;фного выделения значащих раэрядов,кро фф ме первого, соединен с выходом проме ф жуточного регистра, а в первом блоке для последовательного выделения значащих разрядов - с выходом узла оценки количества значащих разрядов выход регистра результата в каждом 1-м блоке ,1 = 1. К) для последовательного выделения значащих разрядов, кроме К-го, соединен с вторым адресным входом (1+1 )-го накопителя и с информационным входом промежу" точного регистра (1+1 )"го блока для38935 10последовательного выделения значащихразрядов, выход регистра результатаК блока для последовательного Выдепения знацащих разрядов являетсяинформационн ым выходом устройства,выход каждого 1-го накопителя соеди"нен с вторым информационным входомузла выделения значащих разрядов1-го блока для последовательного выделения значащих разрядов, выходывсех узлов оценки количества значащих разрядов, кроме первого, соединены с соответсгвующими входами второй группы входов узла управления,первый и второй выходь, которого соединены соответственно с управляющимвходом узла выделения значащих разрядов, со стробирующим входом дешифратора и управляющим входом регистра рез."л тата первого блока для последовательного выделения значащихразрядов каждый нечетный 1-й выход узла у 1 равления соединен с управляющими входами промгжутоцного регистра и узла выделения значащихразрядов ссответствующего блока дляпоследовательного вь;деления значащих;. азрядоа, каждый четный 1-й выходузла управления соединен с управляющи во,;ем регистра результата истробиру:щим входом дешифратора соответствующего блока для последовательного выделения значащих разрядов т;,1 овый вход узла выделениязначащих разоядов каждого блока дляпоследовательного выделения значащих разрядов соединен с тактовым входом устройства,2, Устройство по и. 1, о т л иц а ю щ е е с я тем что узел выделения значащих разрядов содержит группу элементов ИЛИ, группу элементов 2 И-ИЛИ и группу триггеров, прицем первые входы всех элементов ИЛИ груп. пы соединены с первым информационным входом узла , выход каждого элемента ИЛИ группы соединен с первым входом соответствующего элемента 2 И" ИЛИ группы, второй и третий входы которого соединены с управляющим входом узла, цетвер"ый вход каждого элемента.2 И-ИЛИ группы соединен с вторым информационным входом узла, выход каждого элемента 2 И-ИЛИ группы соединен с .входом соответствующего триггера группы, С-вход которого соединен с тактовым входом узла, выход каждого триггера группы соединен с вторым входом элемента ИЛИ группы и с выходом узла.3. Устройство по и. 1, о т л ич а ю щ е е с я тем, цто узел оценки количества значащих разрядое первого блока для последовательного выделения значащих разрядов содержит элемент И-НГ, входы и выход которого соединены соответственно с входом и выходом узла, а узлы оценки количества значащих разрядов всех остальных блоков для последовательного выделения значащих разрядое содержат два шифратора, группу схем сравнения и элемент И, причем входы первого и второго шифратора соединены с входом уела, выходы первого шифратора соединены с первыми входами соответствующих схем сравнения группы, вторые входы которых соединены с соответствующими выходами второго шифратора, выходы схем сравнения гругпы соединены с соответствующими входами элемента И, выход которого соединен с выходом узла.Устройство по и, 1, о т л и ц а ю щ е е с я тем, что узел управления содержит два элемента И и (2 К) элементов 2 И-ИЛИ, причем первые прямые входы двух элементов И,всех элементов 2 И-ИЛИ и вторые прямые входы (2 К. )-го и (2 К)-го элементов 2 ИИЛИ соединены с входом узла, первый и второй входы первой группы входов узла соединены соответственно с вторым прямым и инверсным входами первого элемента И 1-й вход (1 = 2. (2 Кпервой группы входов узла соединен с вторым прямым входом (1-1 )-го элемента 2 И-ИЛИ, третьи и четвертые прямые входы (2 К) и (2 К)-го элементов 2 И-ИЛИ соединены с соответствующими входами первой группы входов узла, инверсный вход 1-го элемента 2 И-ИЛИ (1 = 1 (2 Ксоединен с (1+2)-м входом первой группы входов узла, третий прямой вход 1-го элемента 2 И-ИЛИ (1 = 2(2 К-Й) соединен с (1-1)-м входом второй группы входов узла,пятый прямой вход (2 К)-го элемента 2 И-ИЛИ соединен с соответствующимвходом второй группы входов узла,второй вход второго элемента И соединенс соответствующим входом первой группы входов узла, третьи прямые входы нечетных элементов 2 И-ИЛИ, кроме (2 К)-го элемента 2 И-ИЛИ, соединены с выходами последующих нечетных эле(2 К)-го элемента 2 И-ИЛИ соединенс выходом (2 К)-го элемента 2 И-ИЛИ,выходы двух элементов И и всех элементов 2 И-ИЛИ соединены с соответствующими выходами узла.Изобретение относится к вычислительной технике и может быть использовано в ассоциативных запоминающихустройствах и устройствах приоритета.При обработке данных широкое, применение находит алгоритм отыскания внекотором списке возможных событий,которые были бы каким-либо образомотмечены ранее, т.е. активизированы,с тем, чтобы для каждого активного со Обытия провести некоторую процедуру.Например, при поэлементном моделировании логических узлов списком возможных событий является список логических элементов узла1 3. 15Как правило, поиск активных собы"тий реализуется программно на универсальных ЭВИ, что приводит кбольшимзатратам времени,Известно устройство, которое позволяет аппаратно осуществить поиск ипотактовое формирование номеров акти-вных событий из списка возможных событий в порядке их возрастания.Это устройство требует одновременной подачи на его входы данных об активности всех возможных событий и содержит блок выделения единиц с шифратором запрета обработанных разрядов,шифратор номера разряда выделенной еди- ЗОницы, первый и второй регистры хранения этого кода и дешифратор двоичного кода номера разряда выделенной единицы. Причем, выходы блока выделенияединиц соединены с входами шифратора, выходы которого соединены с входами первого регистра, выходы первогорегистра соединены с входами второгорегистра, выходы которого соединены свходами дешифратора,выходы дешифрато Ора соединены с входами из первой группывходов блока выделения единиц, втораягруппа входов блока выделения соединена с группой внешних входов устройства 2 1. ментов 2 И-ИЛИ, четвертые прямые входы четных элементов 2 И-ИЛИ, кроме (2 К)-го элемента 2 И-ИЛИ, соединены с выходами последующих нечетных элементов 2 И-ИЛИ,пятый прямой вход 2Недостатком известного устройства является то, что при работе с длинными списками возможных событий (до нескольких тысяч событий ) быстродействие устройства мало из-за большого количества последовательно включенных в шифраторе и дешифраторе комби" национных схем, а объем оборудования, необходимого для реализации устройства, велик.Цель изобретения - уменьшение оборудования и увеличение быстродействия устройства.Поставленная цель достигается тем, что устройство для выделения значащих разрядов, из последовательности многоразрядных двоичных кодов, содержащее блок для последовательного выделения значащих разрядов, состоящий из узла выделения значащих разрядов, шифратора; дешифратора и регистра результата, причем выход узла выделения значащих разрядов соединен с входом шифратора, выход которого соединен с первым информационным входом регистра результата и адресным входом дешифратора выход дешифратора соединен с первым информационным входом узла выделения значащих разрядов, со-держит К блоков для последовательного выделения значащих разрядов (К - число групп значащих разрядов), К накопителей, триггер режима,регистр запуска чтения и узел управления а в каждый блок для последовательного выделения значащих разрядов дополнительно введен узел оценки количества значащих разрядов во все блоки для последовательного выделения значащих разрядов,кроме первого, введен промежуточный регистр причем первый вход режима устройства соединен с управляющими входами всех накопителей, кроме3первого, и 8-входом триггера режима, ворой и третЙ входы данных и разрешения устройства соединены соответственно с инФормационными входами и входами разрешения записи накопителей, четвертый вход адреса устройства соединен с первыми адрес" ными входами всех накопителей, кроме первого 1 и с адресным входом первого накопителя, пятый вход запуска чтения устройства соединен с 5-входом триггера режима и с управляо.Ич Входом регистра запуска чтения, выходы которых соединены соотВетственно с входом и первоЙ группоЙ входов узла управления, в каждом блоке для последова тельного Выделенля значащих разрядов Выход узла выделения ,нацащих разрядов дополнительно соединен -. Входом узла оценки количества 3:ацащих разрядов Второй информационный вход регистра результата в каждом блоке для последовательного выделения значащих разрядов, кро. 10 ме первого; "оединен с выходом громе" жутоцного регистра а в первом блоке для последовательного выделения значащих разрядов - с выходом узла оценки количества знацащих разрядов,вы- ХОД РЕ;ИГтРа РЕЗУЛЬтата З кажДОМ -МЗО блоке (1 = 1К) для последовательного Выделения значащих разрядов, кроме К"го , соединен с вторым адресным входоч (1+1)-го накопителя и с информационным входом промежуточного регистра (1+1 )-го блока для последовательного ьыделения значащих раэря" дов вьи,о,:1 регистра результата К-го блока для последовательного выделенля значащих разрядов является инФормдционным зыхо,ом устроиства, Вы 4 О ход каждо о :-го накопителя соединен с втао.,ч информационным входом узла Выделен я значащих разрядов 1-го блока для последовате.пьного выделения значащих разрядов, выходы всех узлов оценки количества значащих разрядов, кроме первого, соединены с соответствующими Вход"ми Второй группы входов узла управления, первый и второй Выходы которого соединены соответственно с управляющими входом узла выделения знацащих разрядов, со стробирующим Входом дешифратора и управляющим входом регистра результата первого блока дпя последовательного выде- , 55 пения значащих разрядов, каждый нечетный 1-," выход узла управления соединен с управляющими входами промежуточного регистра и узла выделенияэнацащих разрядов соответствущегоблок; для последовательного выделения знацащих разрядов, каждый четный 1-й выход узла управления соеди"нен с управляющим входом регистрарезультата и стробирующим Входом дешифратора соответствующего блока дляпоследовательного выделения значащих разрядов, тактовый вход узла вывеления значащих разрядов каждогоблока для последовательного выделения значащих разрядов соединен стактовым входом устоойства.Кроме того, узел выделения значащих разрядов содержит группу элечентоа ИЛИ, группы элементов 2 И-ИЛИи группу триггеров, причем первыеВходы всех элементов ИЛИ группы соединены с первым информационным входомузла, выход каждого элемента ИЛИгруппы соединен с первым входом соответствующего элемента 2 И-ИЛИ группы Второй и третий входы которогосоединены с управляющим входом узла,четвертыЙ вход каждого элемента 2 И-ИЛИ группы соединен с вторым информационным входом узла, выход каждогоэлемента 2 И-ИЛИ группы соединен с 0 входом соответствующего триггера груп";-,ы, -вход которого соединен с тактовымВходом узЛа, выход каждого триггерагруппы соединен с вторыч входом элемента ИЛИ группы и с ьыходоч узла.Кроме того, узел оценки количества значащих разрядов первого блокадля последовательного выделения значащих разрядов содержит элемент И-НЕ,входы и выходы которого соединенысоответственно с входом и выходомузла, а уэль, оценки количества значащих разрядов всех остальных блоков дгя последовательного выделениязначащих разрядов содержат двашифратора, группу схем сравнения иэлемент И, прицем входы первого и второго шифраторов соединены с входомузла, Выходы первого шифратора соедицены с первыми входами соответствующих схем сравнения группы, вторыеВходы которых соединены с соответствующими выходами второго шифратора, выходы схем сравнения группы соединены с соответствующим входами элемента И, выход которого соединен свыходом узла,Кроме того, узел управления содержит два элемента И и (2 К)э; ементов 2 И-ИЛИ, причем первые510389прямые входы двух элементов И,всех элементов 2 И-ИЛИ и вторыепрямые входы,(2 К)-го и (2 К)-гоэлементов 2 И-ИЛИ соединены с входомузла, первый и второй входы первой5группы входов узла соединены соответственно с вторым прямым и инверсным входами первого элемента И,1-й вход (1 = 2,(2 Кпервойгруппы вхоДов узла соединен с вторымпрямым входом (1-1)-го элемента 2 ИИЛИ третьи и четвертые прямые входы (2 К) и (2 К)-го элементов2 И-ИЛИ соединены с соответствуоцимивходами первой группы .входов узла, 15инверсный вход 1-го элемента 2 И-ИЛИ(1 = 1 (2 К) ) соединен с (1+2 )-мвходом первой группы входов узла,третий прямой вход 1-го элемента2 И-ИЛИ (1 = 2(2 Ксоединен с(1-1)-и входом второй группы входовузла, пятый прямой вход (2 К)-гоэлемента 2 И-ИЛИ соединен с соответствующим входом второй группы входов узла, второй вход второго элемента И соединен с соответствуоцим входом первой группы входов узла,третьи прямые входы нечетных элементов 2 И-ИЛИ, кроме (2 К)-го элемента2 И-ИЛИ, соединены с выходами последу 30оцих нечетных элементов 2 И-ИЛИ, четвертые прямые входы четных элементов2 И-ИЛИ, кроме (2 К)-го элемента2 И-ИЛИ, соединены с выходами последующих нечетных элементов 2 И-ИЛИ,пятыйпрямой вход (2 К)-го элемента 2 И-ИЛИсоединен с выходом (2 К)-го элемента2 И-ИЛИ, выход двух элементов И ивсех элементов 2 И-ИЛИ соединены ссоответствуоцими выходами узла,На фиг, 1 представлена блок-схема40устройства; на фиг.2 - блок-схемаузла выделения значащего разряда;на фиг.3,4 - блок-схема узлов оценки количества значащих разрядов дляпервого и последуоцих блоков дляпоследовательного выделения значащих разрядое; на фиг,5- блок-схемаузла управления.Устройство содержит накопители1-4 (2,3 и 4 - накопители с мультиплексором на адресном входе ),блок 5управления чтением, состоящий изтриггера 6 режима, регистра 7 запуска чтения, узла 8 управления, первый вход 9 устройства группа вторыхвходов 10 устройства, третий вход 11управления, четвертый вход 12 устройства, пятый вход 13 устройства 35, 6блоки 14- 141 для последовательного выделения значащих разрядов,каждый из которых содержит узел 15 выделения значащих разрядов, шифратор16,дешифратор 17,узел 18 оценки количества значащих разрядов, регистр19 результата, Блоки 1414, 14+ содержат промежуточный регистр 20 ивыход 21 устройства, Узлы 15 содержат выходы 22-24 триггеров 25,группу элементов ИЛИ 26, группу элемен"тов 2 И-ИЛИ 27.Узел 18 блока 14.1 содержит элемент И-НЕ 28.Узлы 18 блоков 14,1414, содержат шифраторы 29,30,групйу схем 31сравнения, элемент И 32Узел 8 содержит элементы 2 И-ИЛИ 3340,элементы И 41 и 42,Для удобства описания работыустройства допустим, что:а) число возможных событий равно 4096 = 2 ";б) каждый БПВР выделяет значащиеразряды из 8-разрядного слова;с) признаком активности событияявляется логический "0".В устройстве,в последнем накопителе 4 для каждого конкретного возможного события отведен один бит памяти,адрес которого соответствует двенадцатиразрядному (согласно а) номеруэтого события в списке возможных со"бытий, и в который записывается "0"(согласно с ) в случае, если событиеактивно.Обозначим разряды, номера событий,начиная со старшего разряда символамиНС 11, НС 10,НС 1,НСО.Учитывая допущение (в)-,организуем накопитель 4 в виде 512 восьмиразрядных слов, в каждом иэ которыхмогут быть (а могут и не быть ) аятиеные разряды. Причем номер разряда в слове соответствует коду трехмладших разрядов номера события.НС 2,НС 1, НСО, а номер слова соответствует коду старших его разрядовнс 11, нс 10 нс 4,нс 3.Для организации оперативного поиска слов накопителя 4, содержащегоактивные разряды; предназначеннакопитель 3, содержащий столько битпамяти, сколько слов в накопителе 4. Накопитель 3 организованныйв составе 64-х восьмиразрядных слов, в которых, аналогично сказанному выше, могут быть (а могут и не быть ) активные разряды. Причем номер раэ-.7 1 О ряда в сгсве соответствует коду раэаядов - НС 5 НСч, НС а номер слава в наапителях 1-3 соответствует коду разрядов -НС 11, НС 10, ,НС 7 НС 6,Для тога,чтобь организовать оперативный поиск слов накопителей 1-3 содержащих активные разрядь, предназначен накопитель 2, организованный в составе 8 ми ассьмираэрЯДньх слов, Причем номер разряда в слове соответствует коду разрядов НС 8,НС 7, НС 6, а номер слова - коду раэрядфв НС 11 НС 10 НС 9.Соответственна накопительорга низовья в виде одного васьмираэряднога слава, номер ;аэряда в котором ссатветствует коду -С 11 НГ 10, НС 9,Устрайссвс работает .в режимах записи чтения и стирания.В режиме записи мультиплексоры ;акспитегей 2-ч постоянным сигналом ЗП с зходоь 9 устройства соатветственн настраиваются на передачу адреса, апии нГ 11 /С 10 ИСОвходов 10 устройства этим же сгнелом устанавливается в 0 триггеррежи:,а 6, При этом на всех вьхада: узла " .устанавливаются сигнагы О,Логический .поступающий с третьего входа 1 устрайссва при каждом импульсе записи, поступающем с че вертс го входа 12 устройства эа" писывается в наког-,ели .:.-4 го саот вет с таишим адре сам,Зтст процесс псаисходит пока ;обытия экт;яэигсз;:ны, Пс Оксчании записи в накопи-еге 4 помечены О ьсе би; ы, амера которых соответствуют номеру активньх событий, в накопителе 3 памечень: 0" сгава накопителя ч а ксарач Бстречаются актив ные события и т,д., в накопителе помечеы "Ослова накопителя 2, в катарам встречаются актиьнье события, Паи этом мнагааатная активизация од" нага и . Ого жс сабьтия равносильна единственной его активизации.Режим чтения начинается с изменением сигнала ЗП на входе 9 и подачей сигнала на вход 13 устаойства. Па этому с гнаг у т ри г гео 6 уст ана вли вается в 1 на все разряды регистра 7 принимаются значения логического нуля а мугьтиплексоры накопителей 2-4 настраиьагся:.а прием адреса с соответствующих регистрсв 19 результата Г яре,рьшением пад;чи сигала на вход 1у стао с "яа е гис гр, на 1 э2 О 25 ЗО 35 10 45 50 ет заполнят ь ся в режиме сдви га лог че ими единицами, При этом прои дит следующее:Первый такт, Р 31 = 1,Р 32 =0 -происходит прием на узел 15 блока 14 содержимого на кОпи тОля 1Второй такт, Аналиэирустся содержимое узла 15 блока 14 , на выходе шиФратора 16 Формируется адрес младшегс активного триггера узла 15 ;по сути соответствующий старшим раз" рядам номеров активных событий иэ 1/8 части всех возможных событий сниска,на выходе узла 18 блока 14, Формируется сигнал признака актявности АКТ 1, на выходе дешиФратора Фсэмируется сигнал сброса акиьности данного младшего активного триггера.Третий такт. Приведен в пассивное сассяние м 1 адший акти вньй триггер узла 15 блока 14 ,на выходе шиФратора 16 узла 14Формируются соответственна номер следующего активного три ггера и признак того, что этот триггер не ;оследний, на выходе дешифратора 17 - сигнал сброса этого триггера.Одновременна сформированные во 2 -ом такте признак акти вности и номер активого триггера узла 15 блока 14, соответствующий адресу сднага из 6 ч-х блоков акопителя 2,приняты на ре" гистр ;.езультата 19.цетвертый акт, Первьй блок рабстаег так же, как и в х-ем такте, 1 слава иэ 64-х слав накопителя 2 принимается на узел 15 блока 14 2 и появляется на его выходах узла 15 на выходах шиФратора 16 появляетсяпоступает на первые входы регистра 19 номер младшего активного три ггера узла 15 (по сути соответствующий сред.им разрядам номеров активных событий иэ 1/64 части всех возможных событий списка), старшие его разряды вместе с признаком активности появляются на выходах регистра 20 и поступают на вторые вхады регистра 19.В узле 18 блока 142 и узле 8 Формируется сигнал, разрешающий либо перевод в, пассивное состояние младшего активного триггера узла 15, если активных ;риггеров 1, либо прием на узел 15 следующего слова иэ накапитегя 2. В первом случае процесс Формирования оста вшихся разрядов номера активнага события в блоках 14.5 и 14 происходит апис 1 ным выше способом, в результате нг выходах регистра 19 блока 1 ч, амируется1038935 полный номер активного события,первого в списке возможных событий,затем второго и т,д, до тех пор,пока не сбросится в узле 15 блока 14последний активный триггер, и пока 5не,исчезнетзначение активностина выходе узла 18 блока 14,Когда в узле 15 блока 14 пишутся данные об активности последней 10 части списка, исчезнет значениеактивности в соответствующем триггере регистра 19 блока 14,При очередном приеме в узле 15 блока 14,исчезнет признак активности из соответст вующего триггера регистра 20 блока 142 и так далее пока не исчезнет признак активности в регистре 19 блока 14. 10Ис чезнов ение акти внос ти в регистре 19 блока 14, служит сигналом конца чтения.Стирание записанной в накопителе информации производится так же,как и запись, Отличие состоит лишь в том, что на информационные входы ИС памяти подается признак неактивности, т.е, логическая единица. Пере" бор адресов при стирании может производиться либо по списку номеров активных событий полученных при последнем чтении, либо подряд, если такого списка нет (например после включения схемы ).Использование предлагаемого устройства позволяет уменьшить оборудование и повысить быстродействие устройства,