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

 

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

СОЮЗ СОВЕТСНИХ

СОЦИАЛИСТИЧЕСНИХ

РЕСПУБЛИК

„.SU„, 1388901 А1

yg 4 G 06 F 15/36

ОПИСАНИЕ ИЗОБРЕТЕНИЯ

Н ABTOPCHOMV СВИДЕТЕЛЬСТВУ

ГОСУДАРСТВЕННЫЙ КОМИТЕТ СССР

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4142142/24-24 (22) 04. 11. 86 (46) 15. 04. 88. Бюл. Р 14 (72) Л.В. Вариченко, А.П. Марковский, В.И. Корнейчук, Ю.А. Томик и А.А. Яковлев (53) 681.3(088.8) (56) Авторское свидетельство СССР

В 1020836, кл. G 06 F 15/36, 1983.

Авторское свидетельство СССР

У 995097, кл. G 06 F 15/36, 1981. (54) УСТРОЙСТВО ДЛЯ ФОРМИРОВАНИЯ гистогРАммы случАЙных чисел (57) Изобретение относится к вычислительной технике, в частности к специализированным вычислительным устройствам статистической обработки информации. Цепью изобретения является упрощение устройства. Устройство содержит блок 1 ассоциативной памяти, группу элементов И 2, регистр

3 маски, элемент ИЩ 4, приоритетный шифратор 5, счетчик 6, блок 8 памяти, счетчик 10, регистр 12.приема кода, индексный регистр и блок управления. Соединение указанных узлов в соответствии с задачей позволяет получить такую структуру схемы, которая является технологичной и может быть реализована в виде специализированной БИС с использованием известных технологий, например НИЛ- или

МОП-технологии, или реализовать устройство с использованием серийно выпускаемых микросхем, что гораздо проще прототипа. Сущность работы устройства состоит в реализации параллельного сравнения поступающего кода с залисанными в упорядоченном виде в блоке 1 ассоциативной памяти пределами гистограммы. с целью нахождения ближайшего большего к заданному, а значит, и выявления предела, в который попадает заданное число. 1 з.п. ф-.лы, 2 ил.

1 138890

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

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

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

Устройство для формирования гистограммы случайных чисел содержит

1 рлок 1 ассоциативной памяти, группу элементов И, регист1р 3 маски, элеен г ИЛИ 4, приоритетный шифратор первый счетчик 6,:выходы 7 номеа интервала гистограммы устройства, лок 8 памяти, выходы 9 значений гистограммы устройства, второй счет,чик 10, информационные входы 11 устройства, регистр 12 приема кода, индексный регистр 13, информационные 25 входы 14 устройства, входы 15 адреса границ интервалов устройства, причем вход управления записью блока 1 является первым тактовым входом 16 устройства, второй 17, третий 18, 30 четвертый 19 тактовые входы устройства, при этом выход 20 блока 21 управления является выходом готовности приема данных устройства, а также

1 ятый 22 и шестой 23 входы признака

Условий блока 21, Выходи 24-34 блока

21 управления являются соответственно его выходами с второго по двенадцатый.

Блок 21 управления может быть ре- 40 ализован в виде управляющего автомата с фиксированной, логикой. либо виде микропрограммного узла управ,ления. На фиг. 2 представлен в качестве примера один из возможных 4> вариантов реализации блока 21 управления, который содержит соединенные соответствующим образом триггера 3547 (D-типа) с внутренней задержкой, синхрониэирующие входы которых подключены к входу 48 тактирующих импульсов, элементы И 49-55, элементы

ИЛИ 56-65 и элементы HE 66 и 67.

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

1 г быть реализовано с использованием серийно выпускаемых микросхем большой и средней степени интеграции, Блок ассоциативной памяти может быть построен на микросхемах К583РА, причем в состав указанной микросхемы входят встроенные элемент ИЛИ (соответствует элементу ИЛИ 4) и приоритетный шифратор (соответствует приоритетному шифратору 5) с использованием микросхемы К155ЛЛ! или

К599ДЛ1. Приоритетный шифратор 5 может быть также реализован с использованием микросхемы К155ИВ1, регистры 3, 12 и 13 могут быть построены на микросхемах К 155ИР13, счетчики

6 и 10 — на микросхемах K155HF5, блок 8 памяти может быть реализован с использованием микросхем К58РУ1.

Узлы, входящие.в блок 2 1 управления, при его реализации в виде схемы, представленной на фиг. 2, могут быть выполнены следующим образом: триггеры

37-47 реализуются на микросхемах

K155TB1" элементы И 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. Два последующих такта вы1388901 полняются до появления сигнала переполнения счетчика 6. В первом из указанных тактов производится запись нулей в ячейку блока 8 памяти опреЭ

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

По окончании выполнения процедуры очистки блока 8 памяти блок 21 управления формирует на своем выходе

20 сигнал готовности устройства к приему данных.

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

tf If

0, а все разряды индексного регистра 13 — 1". Суть реализуемого в последующих тактах процесса состоит в отыскании среди множества Х чисел, хранящихся в блоке 1 ассоциативной памяти, некоторого подмножества Q(Q С Х) чисел таких, что каждое из них меньше числа У, поступившего на регистр 12 приема кода, причем множество Q обязательно включает число, ближайшее меньшее к У, среди чисел, составляющих множество Х. Поскольку множество Q, выделяемое на шинах поиска (на выходах) блока 1 ассоциативной памяти, упорядочено

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

У, а на информационные входы — п-разрядный нулевой код с регистра 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 управления). В противном случае вновь повторяется описанный цикл, включаю1388901

11100110(230)

11001000(200)

10010110(150)

01100100(100)

ОООООООО(ООО) О

2

3 ф

Пусть очередное поступившее на вхо,цы 11 число (У) равно 211 (11010011).

Тогда опрос блока 1 осуществляется в соответствии с таблицей;

В режиме считывания полученной

Гистограммы управляюший сигнал подается на вход 19. Блок 21 управления формирует сигнал на выходе 28, по щий сдвиг содержимого индексного регистра 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 сигнал готовности к приему очередного числа.

Пример. Пусть разрядность (n) чисел равна 8 и задано 5 интервалов гистограммы: от О до 100, от

100 до 150, от 150 до 200, от 200 до

230. от 230 до 256. Тогда перед началом работы в блок 1 ассоциативной памяти в упорядоченном виде записаны коды," о

Адрес Код которому счетчик 6 устанавливает- ся в "О".. Затем блок 21 управления формирует двухтактовую последовательность сигналов, причем в первом такте по сигналу с, выхода 32 производится считывание содержчмого ячейки блока 8 памяти, адрес которого фиксируется на выходах 7 устройства, на информационные выходы 9 устройства.

Во втором такте сигналов с выхода

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

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

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

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

7 13889 мационные входы и выходы блока памяти соединены соответственно с информационными выходами и входами второго счетчика, информационные выходы

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

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

ИЛИ, выход второго триггера подключен к первым входам первого и второ. го элементов И и третьего элемента

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

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

1 388901

10 (У пп

Сигналы на выходах блока 1

Код на входах адреса счит1явания блока 1

Код на инфор мационных выходах блока 1

Сигнал на выходе элемента

ИЛИ 4

Сигнал на выход шифратора 5

0 1 2(3(4

О О О О О

О О О О О

О 1 О 0 О 001

00000001

1 11010011

2 11010010

3 11010000

О

О

Тираж 704 Подписное

ВНИИПИ Заказ 1583/52

Произвю «полигр ° пр Гиер Г е Ужгородр уле Проектнаяg 4 триггера, выход которого соединен с информационным входом тринадцатого триггера и вторым входом седьмого элемента ИЛИ выход которого являет—

9 5 ся десятым выходом блока, выход тринадцатого триггера подключен к перному входу шестого и седьмого элементов И и к второму входу третьего элемента ИЛИ, выход которого является седьмым выходом блока, выход шестого элемента И соединен с вторым входом девятого элемента ИЛИ, вторые входы шестого и первого. элементов И подключены к выходу второго элемента НЕ, : вход которого, а также вторые входы (, второго и седьмого элементов И объединены и являются шестым входом признака условий блока, выходы второго и седьмого элементов И подключены соответственно к второму и третьему входам восьмого элемента ИЛИ, выход которого является первьг выходом блока, выходы седьмого и десятого элементов ИЛИ являются соответстненно десятым и шестым выходами блока, пер" вый вход первого элемента ИЛИ объединен с вторым входом десятого элемента ИЛИ и является первым входом признака условий и девятым выходом блока, выход первого элемента И соединен с вторым входом первого элемента ИЛИ.