Устройство для формирования гистограммы случайных чисел Советский патент 1988 года по МПК G06F17/18 

Изобретение относится к автомати- ijce и вычислительной технике, в част- йости к специализированным вычисли- teльным устройствам статистической Обработки информации, выполненным на узлах с большой степенью интеграции

Цель изобретения,- упрощение устройства и повьшение его быстродействия.

На фиг. 1 представлена структур- ая схема устройства; на фиг. 2 - йхема блока управления.

Устройство для формирования гис- (гограммы случайных чисел содержит блок 1 ассоциативной памяти, группу элементов И, регистр 3 маски, эле- iieHT ИЛИ 4, приоритетный шифратор $, первый счетчик 6, выходы 7 номе- Ьа интервала гистогра:имы устройства .рлок 8 памяти, выходы 9 значени й гистограммы устройства, второй счет У1ИК 10, информационные входы 11 уст }эойства, регистр 12 приема кода, ин- | ;е1ссный регистр 13, информационные входы 1Д устройства, входы 15 адреса границ интервалов устройства, причем вход управления записью блока 1 является первым тактовым входом 16 устройства, второй 17, третий 18, Четвертый 19 тактовые входы устройства, при этом выход 20 блока 21 уп- | авления является выходом готовности Приема данных устройства, а также йятый 22 и шестой 23 входы признака УСЛОВИЙ блока 21, Выходы 24-34 блока |21 управления являются соответственн его выходами с второго по двенадцатый.

Блок 21 управления может быть реализован в виде управляющего автомата с фиксированной логикой либо Э виде микропрограммного узла управления. На фиг. 2 представлен в качестве примера один из возможных вариантов реализации блока 21 управления, который содержит соединенные соответствующим образом триггера 35- 47 {D-типа) с внутренней задержкой, синхронизирующие входы которых подключены к входу 48 таксирующих импульсов, элементы И 49-55, элементы ИЛИ 56-65 и элементы НЕ 66 и 67.

Устройство для формирования гистограммы случайных чисел может быть реализовано в виде .специализированной БИС с использованием извест- ,рых технологий, например МОП-технологии, Кроме того, устройство может

0

0

5

0

быть реализовано с использованием серийно выпускаемьгх микросхем больгаой и средней степени интеграции. Блок 1 ассоциативной памяти может быть построен на микросхемах К583РА, причем в состав указанной микросхемы входят встроенные элемент ИЛИ (соответствует элементу ИЛИ 4) и приоритетный шифратор (соответствует приоритетному шифратору 5) с использованием микросхемы К155ЛЛ1 или К599ДЛ1. Приоритетный шифратор 5 может быть также реализован с исполь5 зованием микросхемы К155ИВ1, регистры 3, 12 и 13 могут быть построены на микросхемах К 155ИР13, счетчики 6 и 10 - на микросхемах К155ИЕ5, блок 8 памяти может быть реализован с использованием микросхем К58РУ1. Узлы, входящие.в блок 21 управления, при его реализации в виде схемы, представленной на фиг. 2, могут быть выполнены следующим образом: триггеры 37-47 реализуются на микросхемах К155ТВ1; элементы И 49-55 - на микросхемах К155ЛИ1; элементы ИЛИ 56-65 - на микросхемах К155ЛЛ1, элементы 66 и 67 - на микросхемах К155ЛН1.

Устройство для формирования гистограммы случайных чисел работает следующим образом.

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

0 указанной информации в блок 1 может быть предварительно осуществлен с использованием информационных 14 и адресных входов 15 блока 1 ассоциативной памяти. При записи очередной код подается на входы 14 блока 1 ассоциативной памяти, а его адрес подается на 15. Запись осуществляется по управляющему сигналу, подаваемому на вход 16.

По тактовому сигналу, подаваемому на вход 17 устройства, осуществляется очистка блока 8 памяти, которая реализуется следующим образом. Блок 21 управления формирует на своем выходе 28 сигнал очистки (установки в О) счетчика 6. Одновременно формируется сигнал на выходе 3.1 блока 21 управления, которым обнуляется счетчик 10, Два последующих такта вы5

5

0

5

, а все разряды индексного ре- 13 - 1. Суть реализуемого

полняются до появления сигнала переполнения счетчика 6. В первом из указанных тактов производится запись нулей в ячейку блока 8 памяти, определяемую счетчиком 6 (что обеспечивается выдачей сигнала с выхода 33 блока 21 управления), а во втором по сигналу с выхода 29 блока 21 управления производится прибавление единицы к содержимому счетчика 6, По окончании вьтолнения процедуры очистки блока 8 памяти блок 21 управления формирует на своем выходе 20 сигнал готовности устройства к приему данных.

В режиме построения гистограммы код оч ередного числа поступает на информационные входы 11 устройства одновременно с подачей сигнала на вход 18 устройства, последний коммутируется блоком 21 управления на выход 24 .и инициирует прием поступившего числа на регистр 12 приема кода, этим же сигналом все разряды регистра 3 маски устанавливаются в О

гистра

в последующих тактах процесса сос:то- ит в отыскании среди множества X чисел, хранящихся в блоке 1 ассоциативной памяти, некоторого подмножест ва Q(QCX) чисел таких, что каждое из них меньше числа У, поступившего на регистр 12 приема кода, причем множество Q обязательно включает чис ло, ближайшее меньшее к У, среди чисел, составляющих множество X. Поскольку множество Q, выделяемое на шинах поиска (на выходах) блока 1 ассоциативной памяти, упорядочено (в силу того, что упорядочено при записи множество X), то первым в множестве Q вьщелено число, ближайшее меньшее к У, адрес которого первым вьщеляется приоритетным шифратором 5, причем полученный таким образом адрес является по существу номером интервала гистограммы, в который попадает число У. Описанный процесс реализуется следующим образом. Блок 21 управления формирует на своем выходе 34 сигнал управления считьшанием блока 1 ассоциативной памяти. При этом на входы адреса счи тьтания блока 1 через группу 2 элементов И, открытых единичными сигналами с индексного регистра 13, поступает п неизмененных разрядов числа

10

15

20

25

30

35

40

45

50

55

У, а на информационные входы - п-раз- рядный нулевой код с регистра 3 маски, соответствующий немаскируемому состоянию всех разрядов. На одном из выходов блока 1 ассоциативной памяти будет сформирован сигнал в том случае, если хотя бы одно из чисел, записанных в блоке 1, совпадает (а значит, и является ближайшим меньшим или равным) с числом У. Если такой сигнал имеется, то поиск множества Q на этом завершается, о чем свидетельствует единичный сигнал на выходе элемента ШШ 4, который постзшает на вход 22.блока 21 управления. В противном случае,т.е. на вход 22 блока 21 управления с выхода Элемента ИЛИ 4 снимается нулевой потенциал, блоком 21 управления формируется единичный сигнал с выхода 26, по которому содержимое индексного регистра 13 сдвигается на один разряд влево (в сторону старших разрядов) с заполнением младшего разряда нулем. В следующем такте сигналом с выхода 34 блока 21 управле-. ния осуществляется управление считыванием блока 1 ассоциативной памяти немаскированным числом У с нулевьм младшим разрядом. Если при этом появится сигнал на входе 22 блока 21 управления, то поиск множества Q на этом завершается. В противном случае блок 21 управления формирует сигнал на входе 26, по которому производится сдвиг индексного регистра 13, и сигнал на выходе 25, по которому производится сдвиг влево регистра 3 маски с заполнением младшего разряда единицей. В последующем такте осуществляется (сигналом с выхода 34 блока 21 управления) опрос блока 1 ассоциативной памяти. При этом на; входы адреса считьшания последнего посту- пае с выхздов группы 2 элементов И разрядный код числа У. с обнуленными двумя младшими разрядами, а на информационные входы (маскирования) - код 00...01 с регистра 3 маски (указанный код соответствует маскированию младшего разряда). Если в результате опроса блока 1 ассоциативной памяти на его выходах появится хотя бы один сигнал, то множество Q найдено (соответственно поступает единичный сигнал на вход 22 блока 21 управления) . В противном случае вновь повторяется описанный цикл, включающий сдвиг содержимого индексного ре;- гистра 13 и регистра 3 маски, а также опрос блока 1 ассоциативной памяти. Такой цикл повторя€ тся до появления сигнала на входе 22 блока 21 управления, который свидетельствует о том, что на выходах блока 1 ассоциативной памяти единицами отмечены числа, образующие множество Q. Под действием сигнала на входе 22 блок 21 управления формирует сигнал на :выходе 27, по которому код адре- са, соответствующий номеру интервала гистограммы, в вюторой попадает :число У, с выхода приоритетного Шифратора 5 записывается в счетчик :6о В следующем такте блок 21 управ- |Ления формирует сигнал на выходе 32 |по которому происходит считывание рлова, определяемого адресом, храня- цимся в счетчике 6, из блока 8 па- Ияти в счетчик 10 В двух поЬледую- цих тактах выдачей блоком 21 управления сигналов на вькодах 30 и 33 осзпцвствляются соответственно прибавление единицы к содержимому .счетчика 10 и запись увеличенного таким образом содержимого счетчика 10 в соответствующую.ячейку блока 8 памяти, в этом же такте блок 21 управления формирует на своем выходе 20 сигнал готовности к приему очередного числа

Пример. Пусть разрядность (п) чисел равна 8 и задано 5 интервалов гистограммы: от О до 100, от 100 до 150, от 150 до 200, от 200 до ИЗО, от 230 до 256, Тогда перед началом работы в блок 1 ассоциативной памяти в упорядоченном виде записаны коды;

Код

11100110(230) 11001000(200) 10010110(150) 01100100(100) 00000000(000)

Пусть очередное поступившее на вхо да 11 число (У) равно 21 1 (11010011) , Тогда опрос блока 1 осуществляется в соответствии с таблидей;

В реж1чме считывания полученной гистограммы управляюш,нй сигнал подаётся на вход 19. Блок 21 управления формирует сигнал на вкосоде 28,, по

,„

которому счетчик 6 устанавливается в Затем блок 21 управления формирует двухтактовую последовательность сигналов,, причем в первом такте по сигналу с. выхода 32 производится считьшание содержимого ячейки блока 8 памяти, адрес которого фиксируется на выходах 7 устройства, на информационные выходы 9 устройства. Во втором такте сигналов с выхода 29 блока 21 управления производится увеличение содержимого счетчика 6 на единицу. Указанная двухтактовая последовательность повторяется до прихода сигнала переполнения счетчика 6 на вход 23 блока управления, по ко-. торому последний формирует двоичный сигнал готовности к продолжению работы-на выходе 20,

Устройство может работать как автономное вычислительное устройство либо в составе специализированной микроэвм.

Формула изобретени-я

0

5

0

5

0

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

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

0

5

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

0

5

0

0

5

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

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

Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам статистической обработки информации. Целью изобретения является упрощение устройства. Устройство содержит блок 1 ассоциативной памяти, группу элементов И 2, регистр 3 маски, элемент Ш 4, приоритетный № V ff II If шифратор 5, счетчик 6, блок 8 памяти, счетчик 10, регистр 12.приема кода, индексный регистр и блок управления. Соединение указанных узлов в соответствии с задачей позволяет получить такую структуру схемы, которая является технологичной и может быть реализована в виде специализированной БИС с использованием известных технологий, например НИЛ- или МОП-технологии, или реализовать устройство с использованием серийно вьшускаемых микросхем, что гораздо проще прототипа.. Сущность работы устройства состоит в реализации параллельного сравнения поступающего кода с записанными в упорядоченном виде в блоке 1 ассоциативной памяти пределами гистограммы, с целью нахождения ближайшего большего к заданному, а значит, и вьшвления предела, в который попадает заданное число. 1 з.п. , 2 ил. с (Л ж адТпТвЬЛ бь/

j;

Фие2