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

t

(21)4459796/24

(22)14.07.88

(46) 30.05.91.БЮЛ. № 20

(71)Киевский политехнический институт им.50-летия Великой Октябрьской социалистической революции

(72)С.В.Широчин, А.П.Марковский, Е.А.Маслянчук и В.И.Корнейчук

(53)681.3 (088.8)

(56) Авторское свидетельство СССР № 1298768, кл. G 06 F 15/36, 1987.

Авторское свидетельство СССР № 1388901, кл. G 06 F 15/36, 1988.

(54)УСТРОЙСТВО i ДЛЯ ФОРМИРОВАНИЯ ГИСТОГРАММЫ СЛУЧАЙНЫХ ЧИСЕЛ

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

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

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

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

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

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

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

Выходы совпадения блока 1 ассоциативной памяти соединены с входами установки в ноль соответствующего из триггеров группы, выходы которых подключены к входам комбинационного сумматора 3, выходы которого соединены с входами регистра 4 приема кода, выходы которого являются информационными выходами устройства. Вход 5 запуска связан с входом 6 блока 7 и входом установки в ноль счетчика Я адреса, выходы которого подключены к адресным входам блока 9, информационные выходы которого подсоединены к (первым входам соответствующих OJ.OMUMтов И блока 10 и первым входам соответствующих элементов 11,выходы кото- с вхгдами опроса блока

связаны

рых

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

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

В блоке 7 (фиг.2) первый вход элемента ИЛИ 20, как и вход установки в-единичное состояние триггера 21, и вход управления приемом кода вычитающего счетчика 22 связаны с входом запуска блока 7. Выход элемента ИЛИ 20 является выходом 13 блока. Прямой выход триггера 21 соединен с первым входом элемента И 23, выход которого связан через элемент 24 задержки с выходом 16, а непосредствен- 45 х°Де блока 9 равен нулю, то сигнал

но - с выходом 19 блока. Второй вход элемента И 23 подключен к входу 25. Вход сброса блока 7 подключен к второму входу элемента ИЛИ 20 и счетно- му входу счетчика 22, выход переполнения которого соединен с входом установки в ноль триггера 21.

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

Перед началом работы в блок 9 памяти заносятся коды граничных значений гистограммы. В блоке 1 хранятся коды случайных чисел, составляющих выборку, по которой строится гисто50

55

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

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

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

Указанная ситуация соответствует

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

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

0 того, сигнал начала работы, поступая на вход 6, устанавливает триггер 21 в единичное состояние, инициируя прием кода количества граничных значений на счетчик 22. проходя через

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

0 фиксируется единица, а в остальных - 0).

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

0 элемента ИЛИ-НЕ. Последним из этих сигналов блокируется прохождение сигнала с выхода 19 через элемент И 12 и далее на вход опроса блока 1. Если старший разряд кода на вы5

0

5

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

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

ходя -элемента И 23 задерживается члементом 24 и поступает на второй вход 16 блока 7, инициируя сдвиг содержимого регистров 14 и 15 в сторон младших разрядов, при этом старший разряд регистра 15 заполняется нулем, а регистра 14 - единицей.

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

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

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

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

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

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

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

5 операция формирования гистограммы завершится.

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

0 1. Устройство для формирования гистограммы случайных ЧНСРП, содержащее блок ассоциативной памяти, блок памяти, счетчик адреса,регистр маски, регистр приема кода, блок

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

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

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

10

25

15

20

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

Фаг. 1

Us

%

fc

Ч/

% 1%

Фиг. 2

ft/Z.J