Устройство для формирования гистограммы случайных чисел — SU 1388901 (original) (raw)
СОЮЗ СОВЕТСНИХСОЦИАЛИСТИЧЕСНИХРЕСПУБЛИК 0 138890 4 С 06 Г 15/3д,.р,ха Д НИЕ ИЗОБ МУ СВИДЕТЕЛЬСТ ЕТЕНИ ПИ Н АВТ П. Марковскимин ьство СССР 5/36, 1983. тво СССР /36, 1981.(54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ(57) Изобретение относится к вычислительной технике, в частности кспециализированным вычислительнымустройствам статистической обработкиинформации. Целью изобретения является упрощение устройства, Устройство содержит блок 1 ассоциативнойпамяти, группу элементов И 2, регис3 маски, элемент ИЩ 1 4, приоритетный ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССРПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ(56) Авторское свидетелВ 1020836, кл, С 06 РАвторское свидетельУ 995097, кл. 6 06 Г 1 шифратор 5, счетчик 6, блок 8 памяти, счетчик 10, регистр 12.приема кода, индексный регистр и блок управй, ления. Соединение указанных узлов всоответствии с задачей позволяет получить такую структуру схемы, которая является технологичной и можетбыть реализована в виде специализированной БИС с использованием известных технологий, например НИЛ- илиМОП-технологии, или реализоватьустройство с использованием серийновыпускаемых микросхем, что гораздопроще прототипа. Сущность работыустройства состоит в реализации параллельного сравнения поступающегокода с записанными в упорядоченномвиде в блоке 1 ассоциативной памятипределами гистограммы. с целью нахождения ближайшего большего к заданному, а значит, и выявления претр дела, в который попадает заданноечисло. 1 з.п. ф-.лы, 2 нл.15 1 138890Изобретение относится к автоматике и вычислительной технике, в частности к специализированным вычислительным устройствам статистической обработки информации, выполненным на узлах с большой степенью интеграцииЦель изобретения - упрощение устройства и повышение его быстродействия, 10На фиг. 1 представлена структурная схема устройства; на фиг. 2 - схема блока управления.Устройство для формирования гистограммы случайных чисел содержит рлок 1 ассоциативной памяти, группуэлементов И, регист 1 р 3 маски, элеенг ИЛИ 4, приоритетный шифраторпервый счетчик 6,:выходы 7 номеа интервала гистограммы устройства,лок 8 памяти, выходы 9 значений гистограммы устройства, второй счет,чик 10, информационные входы 11 устройства, регистр 12 приема кода, индексный регистр 13, информационные 25 входы 14 устройства, входы 15 адреса границ интервалов устройства, причем вход управления записью блока 1 является первым тактовым входом 16устройства, второй 17, третий 18, 30 четвертый 19 тактовые входы устрой. ства, при этом выход 20 блока 21 упавления является выходом готовности 1 риема данных устройства, а также 1 ятый 22 и шестой 23 входы признака Условий блока 21, Выходи 24-34 блока 21 управления являются соответственно его выходами с второго по двенадцатый.Блок 21 управления может быть ре ализован в виде управляющего автомата с фиксированной, логикой либо В виде микропрограммного узла управ,ления. На фиг. 2 представлен в качестве примера один из возможных 45 вариантов реализации блока 21 управления, который содержит соединенные соответствующим образом триггера 35- 47 (П-типа) с внутренней задержкой,синхрониэирующие входы которых под ключены к входу 48 тактирующих импульсов, элементы И 49-55, элементы ИЛИ 56"65 и элементы НЕ 66 и 67.Устройство для формирования гистограммы случайных чисел может быть реализовано в виде .специализированной БИС с использованием извест,ных технологий, например МОП-технологии, Кроме того, устройство может 1гбыть реализовано с использованием серийно выпускаемых микросхем большойи средней степени интеграции, Блок1 ассоциативной памяти может бытьпостроен на микросхемах К 583 РА, причем в состав указанноймикросхемывходят встроенные элемент ИЛИ (соответствует элементу ИЛИ 4) и приоритетный шифратор (соответствует приоритетному шифратору 5) с использованием микросхемы К 155 ЛЛ илиК 599 ДЛ 1. Приоритетный шифратор 5 может быть также реализован с использованием микросхемы К 155 ИВ 1, регистры 3, 12 и 13 могут быть построенына микросхемах К 155 ИР 13, счетчики6 и 10 - на микросхемах К 155 ИЕ 5,блок 8 памяти может быть реализованс использованием микросхем К 58 РУ 1.Узлы, входящие.в блок 2 1 управления,при его реализации в виде схемы, представленной на фиг. 2, могут быть выполнены следующим образом: триггеры37-47 реализуются на микросхемахК 155 ТВ 1, элементы И 49-55 - на микросхемах К 155 ЛИ 1, элементы ИЛИ 56-65на микросхемах К 155 ЛЛ 1, элементы 66и 67 - на микросхемах К 155 ЛН 1,Устройство для формирования гистограммы случайных чисел работает следующим образом.В исходном состоянии в каждой изячеек блока 1 ассоциативной памятихранятся коды, соответствующие границам интервалов гистограммы, упорядоченные по убыванию, т.е. в ячейке сменьшим адресом всегда хранится больший по величине двоичный код. Записьуказанной информации в блок 1 можетбыть предварительно осуществлен сиспользованием информационных 14 иадресных входов 15 блока 1 ассоциативной памяти. При записи очереднойкод подается на входа 14 блока 1 ассоциативной памяти, а его адрес подается на входы 15. Запись осуществляется по управляющему сигналу, подаваемому на вход 16,По тактовому сигналу, подаваемомуна вход 17 устройства, осуществляетсяочистка блока 8 памяти, которая реализуется следующим образом. Блок 21управления формирует на своем выходе 28 сигнал очистки (установки в"0") счетчика 6. Одновременно формируется сигнал на выходе 3,1 блока 21управления, которым обнуляется счетчик 10, Два последующих такта выполняются до появления сигнала переполнения счетчика 6. В первом из указанных тактов производится запись нулей в ячейку блока 8 памяти опреЭ5 деляемую счетчиком 6 (что обеспечивается выдачей сигнала с выхода 33 блока 21 управления), а во втором по сигналу с выхода 29 блока 21 управления производится прибавление единицы к содержимому счетчика 6. По окончании выполнения процедуры очистки блока 8 памяти блок 21 управления формирует на своем выходе 20 сигнал готовности устройства к приему данных.В режиме построения гистограммы код очередного числа поступает на информационные входы 11 устройства одновременно с подачей сигнала на вход 18 устройства, последний коммутируется блоком 21 управления на выход 24 .и инициирует прием поступившего числа на регистр 12 приема кода, этим же сигналом все разряды 25 регистра 3 маски устанавливаются в ц и0 , а все разряды индексного регистра 13 - "1". Суть реализуемого в последующих тактах процесса состоит в отыскании среди множества Х чисел, хранящихся в блоке 1 ассоциативной памяти, некоторого подмножества Я(Я С Х) чисел таких, что каждое из них меньше числа У, поступившего на регистр 12 приема кода, причем множество Я обязательно включает число, ближайшее меньшее к У, среди чисел, составляющих множество Х. Поскольку множество Я, выделяемое на шинах поиска (на выходах) блока 1 ассоциативной памяти, упорядочено40 (в силу того, что уйорядочено при записи множество Х), то первым в множестве Я выделено число, ближайшее меньшее к У адрес которого пер 1 45 вым выделяется приоритетным шифратором 5, причем полученный таким образом адрес является по существу номером интервала гистограммы, в который попадает число У. Описанный процесс реализуется следующим образом. Блок 21 управления формирует на своем выходе 34 сигнал управления считыванием блока 1 ассоциативной памяти. При этом на входы адреса считывания блока 1 через группу 2 элементов И, открытых единичными сигналами с индексного регистра 13, поступает и неизмененных разрядов числа У, а на информационные входы - п-разрядный нулевой код с регистра 3маски, соответствующий немаскируемому состоянию всех разрядов. На одном из выходов блока 1 ассоциативной памяти будет сформирован сигналв том случае, если хотя бы одно иэчисел, записанных в блоке 1, совпадает (а значит, и является ближайшим меньшим или равным) с числом У.Если такой сигнал имеется, то поискмножества Я на этом завершается, очем свидетельствует единичный сигнална выходе элемента ИЛИ 4, которыйпоступаетна вход 22.блока 21 управления. В противном случае.,т.е.на вход 22 блока 21 управления с выхода элемента ИЛИ 4 снимается нулевой потенциал, блоком 21 управленияформируется единичный сигнал с выхода 26, по которому содержимое индексного регистра 13 сдвигается наодин разряд влево (в сторону старшихразрядов) с заполнением младшегоразряда нулем. В следующем такте сигналом с выхода 34 блока 21 управле-.ния осуществляется управление считыванием блока 1 ассоциативной памятинемаскированным числом У с нулевыммладшим разрядом. Если при этом появится сигнал на входе 22 блока 21управления; то поиск множества Я наэтом завершается. В противном случаеблок 21 управления формирует сигнална входе 26, по которому производитсясдвиг индексного регистра 13, и сигнал на выходе 25, по которому производится сдвиг влево регистра 3 маски с заполнением младшего разрядаединицей, В последующем такте осуществляется (сигналом с выхода 34 блока21 управления) опрос блока 1 ассоциативной памяти. При этом нж входыадреса считывания последнего поступает с выходов группы 2 элементов Иразрядный код числа У с обнуленными двумя младшими разрядами, а наинформационные входы (маскирования) -код 0001 с регистра 3 маски (указанный код соответствует маскирова-нию младшего разряда). Если в результате опроса блока 1 ассоциативнойпамяти на его выходах появится хотябы один сигнал, то множество Я найдено (соответственно поступает единичный сигнал на вход 22 блока 21 управления). В противном случае вновьповторяется описанный цикл, включаю0 1 2 3 11100110(230) 11001000(200) 10010110(150) 01100100(100) 00000000(000) Пусть очередное поступившее на вхо,цы 11 число (У) равно 211 (11010011). Тогда опрос блока 1 осуществляется в соответствии с таблицей; В режиме считывания полученной Гистограммы управляюший сигнал пода ется на вход 19. Блок 21 управленияформирует сигнал на выходе 28, по щий сдвиг содержимого индексного регистра 13 и регистра 3 маски, а также опрос блока 1 ассоциативной памяти. Такой цикл повторяется до появления сигнала на входе 22 блока 21 управления, который свидетельствует о том, что на выходах блока 1 ассоциативной памяти единицами отмечены числа, образующие множество Ц. Под действием сигнала на входе 22 блок 21 управления формирует сигнал на выходе 27, по которому код адреса, соответствующий номеру интервала гистограммы, в которой попадает число У, с выхода приоритетного шифратора 5 записывается в счетчик 6, В следующем такте блок 21 управления Формирует сигнал на выходе 32, по которому происходит считывание слова, определяемого адресом, хранящимся в счетчике б, из блока 8 памяти в счетчик 10, В двух последуюцих тактах выдачей блоком 21 управления сигналов на выходах 30 и 33 осуществляются. соответственно прибавление единицы к содержимому .счетчика 10 и запись увеличенного таким образом содержимого счетчика 10 в соответствующую ячейку блока 8 памяти, в этом же такте блок 21 управления формирует на своем выхоце 20 сигнал готовности к приему очередного числа.П р и м е р. Пусть разрядность (и) чисел равна 8 и задано 5 интервалов гистограммы: от О до 100, от 100 до 150, от 150 до 200, от 200 до 230. от 230 до 256, Тогда перед началом работы в блок 1 ассоциативной памяти в упорядоченном виде записаны коды,"аАдресКодкоторому счетчик 6 устанавливает- ся в "О". Затем блок 21 управления формирует двухтактовую последовательность сигналов, причем в первом такте по сигналу с. выхода 32 производится считывание содержчмого ячейки блока 8 памяти, адрес которого фиксируется на выходах 7 устройства, на информационные выходы 9 устройства. Во втором такте сигналов с выхода 29 блока 21 управления производится увеличение содержимого счетчика б на единицу, Указанная двухтактовая последовательность повторяется до прихода сигнала переполнения счетчика 6 на вход 23 блока управления, по которому последний формирует двоичный сигнал готовности к продолжению работы на выходе 20.Устройство может работать как автономное вычислительное устройство либо в составе специализированной микроЭВМ. Формула изобретения 50 1, Устройство для Формирования гистограммы случайных чисел, содержащее регистр приема кода, информационный вход которого является информационным входом устройства, группу элементов И, первый счетчик, выходы которого являются .выходами номера интервала гистограммы устройства, о т л и ч а ю щ е е с я тем, что, с целью упрощения, оно содержит регистр маски, индексный регистр, элемент ИЛИ, блок управления, приоритетный шифратор, блок памяти, второй счетчик и блок ассоциативной памяти, адрес считывания которого соединен с выходами элементов И группы, первый информационный вход - с выходом регистра маски, а второй информационный вход блока ассоциативной памяти является входом задания границ интервалов устройства, вход управления записью блока ассоциативной памяти является первым тактовым входом устройства, а адресный вход записи является входом адреса границ интервалов устройства, выходы блока ассоциативной памяти подключены к входам элемента ИЛИ и приоритетного шифратора, выход которого подключен к информационному входу первого счетчика, вьход которого соединен с адресным входом блока памяти инфорО 30 7 13889 мационные входы и выходы блока памяти соединены соответственно с информационными выходами и входами второго счетчика, информационные выходы5 блока памяти являются выходом значений гистограммы устройства, первые и вторые входы элементов И группы подключены соответственно к выходам регистра приема кода и индексного регистра, первый, второй, тре-. тий и четвертый входы признака условий блока управления являются соответственно с второго по пятый тактовыми входами устройства, первый,выход блока управления является выходом готовности приема данных устройства, второй выход блока управления подключен к входу записи регистра приема кода, регистра маски и ин О дексного регистра, третий и четвертый выходы блока управления подключены соответственно к входам сдвига регистра маски и индексного регистра, пятый, шестой и седьмой выходы 25 блока управления соединены соответственно с входом записи, входом установки в ноль и счетным входом первого счетчика, выходы элемента ИЛИ и,выход переполнения первого счетчика подключены соответственно к пятому и шестому входам признака условий блока управления, восьмой,и девятый выходы которого соединены соответственно со счетным входом и входом установки в ноль второго счетчика, вход записи которого объединен с входом управления считыванием блока памяти и подключен к десятому выходу блока управления, один надцатый и двенадцатый выходы которого подключены соответственно к входу управления записью блока памяти и входу управления считыванием блока ассоциативной памяти.2, Устройство по и. 1, о т л и - ч а ю щ е е с я тем, что блок управления содержит первый и второй элементы НЕ, с первого по седьмойэлементы И, с первого по десятый элементы ИЛИ, с первого по тринадцатый триггеры, синхровходы которых объединены и являются четвертым входом признака условий .блока, информационный вход первого триггера соединен с выходом первого элемента ИЛИ, а выход первого триггера соединен с информационным входом второго триггера и первым входом второго элемента ИЛИ, выход второго триггера подключен к первым входам первого и второго элементов И и третьего элементаИЛИ, информационный вход третьеготриггера является третьим входомпризнака условий и вторым выходомблока, а выход третьего триггераподключен к первым входам четвертого элемента ИЛИ и третьего элемента И, выход которого соединен синформационным входом четвертоготриггера, выход которого подключенк первому входу пятого элемента ИЛИи информационному входу пятого трйггера, выход которого соединен с вторым входом четвертого элемента ИЛИи первым входом шестого элементаИЛИ, выход которого подключен к пер"вому входу четвертого элемента И,выход которого соединен с информационным входом шестого триггера, выход которого подключен к информационному входу седьмого триггера, является третьим выходом блока и подключен к второму входу седьмого элемента ИЛИ, выход седьмого триггерасоединен с вторым входом шестогоэлемента ИЛИ и третьим входом четвер-.того элемента ИЛИ, выход которого является двенадцатым выходом блока иподключен к первому входу пятогоэлемента И, второй вход которого является пятым входом признака условийблока, а выход пятого элемента Иподключен к информационному входувосьмого триггера непосредственно,а через первый элемент НЕ соединенс вторыми входами третьего и четвертого элементов И, выход восьмоготриггера является пятым выходом блока и соединен с информационным входом девятого триггера, выход которого подключен к первому входу седьмого элемента ИЛИ и информационномувходу десятого триггера, выход которого является восьмым выходом блокаи подключен к информационному входуодиннадцатого триггера, выход которого подключен к первому входу восьмого элемента ИЛИ и второму входувторого элемента ИЛИ, выход которогоявляется одиннадцатым выходом блока,первый вход девятого элемента ИЛИявляется третьим входом признака условий блока и подключен к первомувходу десятого элемента ИЛИ, выходдевятого элемента ИЛИ соединен синформационным входом двенадцатого1388901 триггера, выход которого соединен с информационным входом тринадцатого триггера и вторым входом седьмого элемента ИЛИ выход которого являет -9 5 ся десятым выходом блока, выход тринадцатого триггера подключен к первому входу шестого и седьмого элементов И и к второму входу третьего элемента ИЛИ, выход которого является 10 седьмым выходом блока, выход шестогоэлемента И соединен с вторым входом девятого элемента ИЛИ, вторые входы шестого и первого элементов И подключены к выходу второго элемента НЕ, вход которого, а также вторые входы , второго и седьмого элементов И объеУпп Сигналы на выходах блока 1 Сигнал навыходеэлементаИЛИ 4 Сигнал на выходшифратора 5 О 113 А О О 0 О 0 О 0 О 0 0 О 1 0 О 0 00100000000 00000000 00000001 1 11010011 г 11010010 3 11010000 0 О 1 аж 704 Подписи Заказ 1583/52 г. Ужгород, ул, Проектная изв.-полигон. пр Код на входах Код на инфорадреса считы- мационныхвания блока 1 выходах блока 1 динены и являются шестым входом признака условий блока, выходы второго и седьмого элементов И подключенысоответственно к второму и третьемувходам восьмого элемента ИЛИ, выходкоторого является первьг выходом блока, выходы седьмого и десятого элементов ИЛИ являются соответственнодесятым и шестым выходами блока, пер"вый вход первого элемента ИЛИ обьединен с вторым входом десятого элемента ИЛИ и является первым входомпризнака условий и девятым выходомблока, выход первого элемента И соединен с вторым входом первого элемента ИЛИ.