Буферное запоминающее устройство для нумерации вершин графа

 

Изобретение относится к области вычислительной техники и может быть использовано в качестве буферного запоминающего устройства при решении задач на графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения номеров чисел входной последовательности без пропусков и повторе-- НИИ. Устройство содержит дешифратор 1, группу из Р триггеров 2, где Р - количество различных чисел во входной последовательности, группу из Р элементов И 3, группу из Р счетчиков 4, элемент ИЛИ 5, элемент И 6 и группу элементов 7 задержки. Устройство работает следующим образом, Церед началом работы обнуляют все счетчики 4 и устанавливают в единичное состояние все триггеры 2. С частотой следования тактовых импульсов на вход дешифратора 1 начинают поступать числа входной последовательности. Дешифратор преобразует код числа в потенциал на одном из своих выходов. Этим потенциалом открывается элемент И 6, и на счетные входы всех счетчиков 4 поступает один тактовый импульс. Через время, определяемое элементом 7 задержки, нулевой потенциал с выхода соответствующего триггера 2 запрещает дальнейший счет импульсов тем счетчиком 4, который соответствует выбранному выходу дешифратора 1. Далее работа устройства повторяется, при этом коды, накопленные счетчиками 4, соответствуют номерам чисел во входной последовательности. 1 ил. с S (Л 4 05 05

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

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

РЕСПУБЛИК (5ц 4 G 06 F 12/00

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

К ABTOPCKOMV СВИДЕТЕЛЬСТВУ

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

ПО ДЕЛАМ ИЗОБРЕТЕНИЙ И ОТКРЫТИЙ (21) 4166460/24-24 (22) 22, 12,86 .(46) 07.06,88. Бюл, М- 21 (72) В.Г.Тоценко (SV) Г.Г.Митрев (ВС)

H.М.Рец, Л.M.Îñèíñêèé и С.А.Козорезов (SV) (53) 681,325(088,8) (56) Авторское свидетельство .".CCP !! - 752362, кл. G 06 G 7/122, 1980.

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

N - 1120407, кл, G 06 F 12/00, 1983. (54) БУФЕРНОЕ ЗАПОМИНАК65Е УСТРОИСТВО ДЛЯ НУМЕРАЦИИ ВЕРШИН ГРАФА (57) Изобретение относится к области вычислительной техники и может быть использовано в качестве буферного запоминающего устройства при решении задач на графах. Целью изобретения является расширение функциональных возможностей устройства за счет определения номеров чисел входной последовательности без пропусков и повторений. Устройство содержит дешифратор

1, группу из P триггеров 2, где P— количество различных чисел во входной

„„SU„„1401466 А1 последовательности, группу из P элементов И 3 группу из Р счетчиков 4, элемент ИЛИ 5, элемент И 6 и группу элементов 7 задержки. Устройство работает следующим образом, Перед началом работы обнуляют все счетчики

4 и устанавливают в единичное состояние все триггеры 2, С частотой следо Ф вания тактовых импульсов на вход дешифратора 1 начинают поступать числа входной последовательности. Дешифратор преобразует код числа в потенциал на одном из своих выходов.

Этим потенциалом открывается элемент

И 6, и на счетные входы всех счетчик ков 4 поступает один тактовый импульс ° Q

Через время, определяемое элементом

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

Далее работа устройства повторяется, при этом коды, накопленные счетчика- !фЬ ми 4, соответствуют номерам чисел 1 во входной последовательности. 1 ил. им

1401466 чисел последовательности, единичный потенциал с его выхода, соответствующего данному числу, не проходит через элемент И 3, заблокированный нулевым потенциалом с выхода соответствующего триггера 2. Элемент И 6 закрыт нулевым потенциалом с выхода элемента ИЛИ 5 и тактовый импульс не проходит на счетные входы счетчиков 4, Это обеспечивает нумерацию чисел входной последовательности без пропусков и повторений.

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

Составитель А.Мишин

Редактор Н,Лазаренко Техред М.Ходанич Корректор Л Пилипенко

Заказ 2786/48 Тираж 704 Подписное

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

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

Производственно-полиграфическое предприятие, г. Ужгород, ул. Проектная, 4

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

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

На чертеже показана блок-схема предлагаемого устройства.

Устройство содержит дешифратор

1, группу из P триггеров 2, где P — 15 количество различных чисел во входной последовательности, группу из P элементов И 3, группу из P счетчиков 4, элемент ИПИ 5, элемент И 6 и группу элементов 7 задержки. 20

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

Перед началом работы обнуляют все счетчики 4 и устанавливают в еди.ничное состояние все триггеры 2. 25

С частотой следования тактовых импульсов на вход дешифратора 1 начинают поступать.-числа входной последовательности. Дешифратор преобразует код числа в потенциал на одном из 30 своих выходов; Этим потенциалом отк-. рывается элемент И 6 и на счетные входы всех счетчиков 4 поступает один тактовый импульс. Через время, определяемое элементом 7 задержки, ну- 35 левой потенциал с выхода соответствующего триггера 2 запрещает дальнейший счет импульсов тем счетчиком 4, который соответствует выбранному выходу дешифратора 1. Далее работа уст- 4р ройства повторяется, при этом коды, накопленные счетчиками 4, соответствуют номерам чисел во входной . последовательности. В случае, если на вход дешифратора 1 поступает чис- 45 ло, которое уже встречалось среди

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

К-й выход дешифратора (К=1,...P) подключен к первому входу К-го элемента И группы и к входу установки в

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