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

 

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

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

РЕСПУБЛИК (19) (11) А1 (g1)5 О 06 1 15/36

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

Н А BTOPCHOMY СВИДЕТЕЛЬСТВУ

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

ПО ИЗОБРЕТЕНИЯМ И ОТКРЫТИЯМ

ПРИ ГКНТ СССР

1 (21) 4459796/24 (22) 14.07.88 (46) 30.05.91.Бюл. к- 20 (71) Киевский политехнический институт им.50-летия Великой Октябрьской . социалистической революции (72) С.В.Нирочин, А.П.Марковский, Е.А.Г1аслянчук и В.И.Корнейчук (53) 681.3 (088.8) (56) Авторское .свидетельство СССР

Ф 1298768, кл. G 06 Р 15/36, 1987.

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

P,- 1388901, кл. С 06 F 15/36, 1988. (54) УСТРОЙСТВО ДЛЯ ФОРГ1ИРОВАНИЯ

ГИСТОГРАММЫ СЛУЧАЙНЫХ ЧИСЕЛ

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

Цель изобретения — повышение быстродействия при формировании гистограмм случайных чисел.

На фиг.1 представлена структурная схема устройства; на фиг.2 — схема блока управления; на фиг.3 — временная диаграмма работы устройства, Устройство содержит блок 1 ассоциативной памяти, группу 2 триггеров, сумматор 3, регистр 4 приема кода, вход 5 запуска устройства, вход 6 запуска блока управления, блок 7 управления, счетчик 8 адреса, блок 9 памяти, блок 10 элементов И, группу 11 элементов НЕРАВНОЗНАЧНОСТЬ элемент

И 12, выход 13 блока управления, регистр 14 маски, регистр 15 сдвига, 2 (57) Изобретение относится к вычислительной технике. Цель изобретения— повьш ение быстродействия при формировании гистограмм случайных чисел.

Устройство содержит блоки памяти, группу триггеров, сумматор, регистры, блок управления, счетчик, блок элементов И, блок элементов НЕРАВНОЗНАЧНОСТЬ, элементы И, регистр сдвига, элемент ИЛИ-HE. Блок управления содержит элемент ИЛИ. триггер, счетчик, элемент И, элемент задержки. Устройство позволяет строить интегральную гистограмму n k-разрядных чисел.

1 з.п.ф — лы, 3 ил. выход 16 блока управления, элемент 17

ИЛИ-НЕ> вход 18 сброса блока управления, выход 19 блока управления.

Блок управления содержит элемент

ИЛИ 20, триггер 2 1, счетчик 22, элемент И 23, элемент задержки 24, вход 25 синхронизации.

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

5 запуска связан с входом 6 блока 7 и входом установки в ноль счетчика 8 адреса, выходы которого подключены к адресным входам блока 9, информационные выходы которого подсоединень. к

1 первым входам соответствующих э ;емен1652982 тов И блока 10 и первым входам соответствующих элементов 11,выходы которых связаны с входами опроса блока

1.

Выход 13 блока 7 соединен с входами установки в единицу триггеров

2, входами установки в исходное состояние регистра 14 маски и регистра

15 сдвига, выходы которого подключены 10 к вторым входам соответствующих эле.ментов И блока 10 и вторым входам соответствующих элементов НЕРАВНОЗНАЧНОСТЬ. Второй выход 16 блока 7 связан с входами управления сдвигом регистра 15 и регистра 14, информационные выходы которого подключены к входам маскирования блока 1. Выход переполнения при сдвиге регистра 14 связан с вторым входом 18 блока 7, счетным входом счетчика 8 и входом синхронизации регистра 4 приема кода. Выход 19 блока 7 подключен к первому входу элемента И 12, выход которого соединен с входом опро- 25 са блока 1.

Элементы И блока 10 связаны своими выходами со входами элемента HJIHiHE 17, выход которого соединен с вторым входом элемента И 12. Информационные входы регистров 14 и 15 подключеньг к источникам потенциалов соответственно единичного и нулевого уровней.

В блоке 7 (фиг.2) первый вход элемента ИЛИ 20, как и вход установки в единичное состояние триггера 21, и вход управления приемом кода вычитающего счетчика 22 связаны с входом запуска блока 7. Выход элемента 40

ИЛИ 20 является выходом 13 блока.

Прямой выход триггера 21 соединен с первым входом элемента И 23, выход коТорого связан через элемент 24 задержки с выходом 16, а непосредствен- 45 но — с выходом 19 блока. Второй вход элемента И 23 подключен к входу 25.

Вход сброса блока 7 подключен к второму входу элемента ИЛИ 20 и счетному входу счетчика 22, выход перепол 50

Кения которого соединен с входом установки в ноль триггера 21.

Устройство работает следующим об разом.

Перед началом работы в блок 9

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

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

Сигнал начала работы, подаваемый на вход 5, устанавливает в ноль все разряды счетчика 8, соответственно на выходах блока 9 считывается код нижнего граничного значения. Кроме того, сигнал начала работы, поступая на вход 6, устанавливает триггер

21 в единичное состояние, инициируя прием кода количества граничных значений на счетчик 22. проходя через элемент ИЛИ 20, формирует единичный сигнал на выходе 13, которым устанав-. ливаются в единичное состояние регистры 14 и 15 (в исходном состоянии в старшем разряде упомянутых регистров фиксируется единица, а в остальных—

О).

После установки триггера 21 в единичное состояние импульсы с входа 25 проходят элемент И 23 и постулают на выход 19 (см.фиг.3). Если старший разряд кода на выходах блока 9 равен единице, то единичный сигнал сформируется на выходе элемента И 10.1 и нулевой — на выходе элемента KIH-HE. Последним из этих сигналов блокируется прохождение сигнала с выхода 19 через элемент

И 12 и далее.на вход опроса блока 1.

Если старший разряд кода на выходе блока 9 равен нулю, то сигнал с выхода 19. пройдя через открытый элемент И 12 инициирует опрос блока

1. При этом на входы маскирования блока 1 с регистра 14 подается код маски, содержащий единицу в старшем разряде и нули в остальных, а на входы признака опроса блока 1 подается код с выходов блока 9.

Таким образом, блоком 1 производится поиск ячеек с единицей в старшем разряде и выдача единичных сигналов на соответствующих выходах совпадения. Этими сигналами триггеры 2 устанавливаются в ноль, сигнал с вы1652982,хода элемента И 23 задерживается элементом 24 и поступает на второй вход 16 блока 7, инициируя сдвиг содержимого регистров 14 и 15 в сторону младших разрядов, при этом старший разряд регистра 15 заполняется нулем, а регистра 14 — единицей.

Следующий сигнал с выхода 19 опять инициирует обращение. к блоку

1, если очередной (второй) разряд кода на выходе блока 9 равен О. При этом будет осуществляться поиск слов, у которых старший разряд совпадает с кодом на выходе лока 9, а второй является инверсией второго разряда упомянутого кода, т.е. равен единице. Инвертирование второго разря— да производится элементом НЕРАВНОЗНАЧНОСТЬ 11.2. Найденные таким образом слова отмечаются выдачей единичных потенциалов на соответствующих выходах совпадения блока 1, которыми устанавливаются в ноль соответствующие триггеры 2.

Сигналом с выхода 16, задержанным элементом 24, инициируется новый сдвиг содержимого регистров и описанный цикл работы устройства повторяется.

Всего будет выполнено п (и — разрядность обрабатываемых чисел) циклов до появления при очередном сдвиге регистра 14 единичного сигнала на выходе переполнения при сдвиге, который поступает на вход 18 и на счетный вход счетчика 8..Последовательность и циклов, выполняемых по описанному способу, обеспечивает нахождение всех чисел среди хранящихся в блоке 1 больших кода, зафиксированного на выходах блока 9, и установку соответствующих триггеров 2 в ноль.

Сигналом переполнения при сдвиге регистра 14 в регистре 4 зафиксируется определенное сумматором 3 количество чисел в выборке, не превышающих значение кода первой границы гистограммы, которое может быть считано с регистра 4. Этим же сигналом увеличивается на единицу содержимое счетчика 8, который адресует следующую границу гистограммы„ хранящуюся в блоке 9. Сигналом, поступающим на вход 18, содержимое счетчика 22 уменьшается на единицу и через элемент ИЛИ 20 осуществляется выдача по выходу 13 сигнала началь10 !

55 ной установки регистров 14, !5 и триггеров 2

Устройство е приходом очередного тактового импульса начинает по сттособу, описаьп ому выше, обработку следующего кода предела гистограммы, зафиксированного на выходах блока 9.

Описанная последовательность операций выполняется до тех пор, пока на выходе счетчика 22 не будет сформирован сигнал переполнения, которым триггер 2! устанавливается в ноль, и операция формирования гистограммы завершится.

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

1. Устройство для формирования гистограммы случайных чисел, содержащее блок ассоциативной памяти, блок памяти, счетчик адреса, регистр маски, регистр приема кода, блок элементов И и блок управления, причем выходы счетчика адреса подсоединены к адресным входам блока памяти, первый выход блока управления подключен к входу установки в исходное состояние регистра маски„ второй выход блока управления подсоединен к входу управления сдвигом регистра маски, о т л и ч а ю щ е е с я тем, что, с целью повышения быстродействия, в него введены группа триггеров, сумматор, регистр сдвига, группа элементов НЕРАВНОЗНАЧНОСТЬ. элемент

ИЛИ-НЕ и элемент И, причем каждый

j é (j=1,n,n — количество чисел, составляющих выборку, по которой формируется гистограмма) выход блока ассоциативной памяти подключен к входу установки в нулевое состояние j -гo триггера, группы прямых выходов триггеров группы соединены с входами сумматора, выход которого соединен с информационным входом регистра приема кода, выход которого является информационным выходом устройства, вход запуска устройства соединен с входом установки в нулевое состояние счетчика адреса и входом запуска блока управления, первый выход которого соединен с входом установки в начальное состояние регистра сдвига и входом установки в единичное сос.тояние триггеров группы, второй выход блока управления — с входом управления сдвигом сдвигового регистра, 1652982 информационные выходы блока памяти подсоединены к первой группе входов блока элементов И и первым входам элементов НЕРАВНОЗНАЧНОСТЬ группы, Выходы которых соединены с информационными входами блока ассоциативной

Памяти, разрядные выходы регистра

Сдвига подключены к вторым входам группы элементов НЕРАВНОЗНАЧНОСТЬ

10 группы и к второй группе входов блока элементов И, выходы которого соединены с входами элемента ИЛИ-НЕ

1 выход которого подключен к первому входу элемента И, втоРой вход котоРоГо соединен с третьим выходом блока управления, а выход — с входом опроса блока ассоциативной памяти, выходы регистра маски соединены с входами маскирования блока ассоциативной

20 памяти, выход переполнения регистра маски подключен к входу сброса блока управления, счетному входу счетчика

Адреса и входу синхронизации регистра приема кода, тактовый вход устрой- 25

1 ства соединен с тактовым входом блока управления.

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

ИЛИ, тактовый вход блока соединен с вторым входом элемента И. первым и третьим выходами блока являются выходы соответственно элемента ИЛИ и элемента И.

1652982

U18

Составитель Д.Ухтверов

Редактор Л.Народная Техред Л.Олийнык

Корректор А.ОбРУчаР

Заказ 2189 Тирам 419 Подписное

ВНИИПИ Государственного комитета по изобретениям и открытиям при ГКНТ СССР

113035, Иосква, Ж-35, Раушская наб., д. 4/5

Производственно-издательский комбинат "Патент", r. Умгород, ул. Гагарина, 101