Устройство для исследования графов

 

Изобретение относится к автоматике и вычислительной технике и может бъггь использовано для целераспределения , для исследования графов. Цель изобретения состоит в повьшении быстродействия устройства. Поставленная цель достигается путем исключения потерь времени на запись элементов опорного решения во внешние блоки памяти и потерь времени на обращение к внешним операционным устройствам для осуществления арифмет1гческих операций, что обеспечивается введением третьего блока 3 памяти, блока 4 вычитания, первого 5 и второго 6 вычитающих счетчиков, первого 7 и второго 8 компараторов, второго элемента И 11, второго элемента ИЛИ 13, четвертого 17, пятого 18, шестого 19, седьмого 20 и восьмого 21 элементов задержки.6 ил. (/)

СОЮЗ COBETCHHX

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

РЕСПУБЛИК (5I) 4 С 06 F 15/20

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

К А8ТОРСКОМУ СВИДЕТЕЛЬСТВУ

14

Ь".i 1 ссна.drod

Ин ср.

od

В ссн

Си

Гр.

Гр.

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

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

ПРИ ГКНТ СССР (21) 4198384/24-24 (22) 23.02.87 (46) 28,02.89. Бюл. Ф 8 (71) Московский институт радиотехники, электроники и автоматики (72) Г,О.Крылов, А,Н.Романов и О.А.Славин (53) 681.325(088.8) (56) Патент США Р 4554626, кл. G 05 F 9/00, опубл. 1985.

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

N 1238099, кл. G 06 F 15/20, 1986. (54) УСТРОЙСТВО ДЛЯ ИССЛЕДОВАНИЯ

ГРАФОВ (57) Изобретение относится к автоматике и вычислительной технике и мотет быть использовано для целерас„„SU„„1462345 А1 пределения, для исследования графов.

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

5 и второго 6 вычитающих счетчиков, первого 7 и второго 8 компараторов,, второго элемента И 11, второго элемента ИЛИ 13, четвертого 17, пятого 18, шестого 19, седьмого 20 и восьмого 21 элементов задержки.6 ил.

1462345 х .. из условий:

11 и

2:. х ° ° = Q.3 1(J =(m

1=, 30 х - = Р;; 1 ci v (1)

) с х.у О; 1

f)

1 что значение выражения

Q с; х;.

;=1 /=! ) 11 (2) 40 минимально, причем выполнены следующие сооотношения,> Р;

Р;ЪОе1414ш (3) Q-Ъ О, 1 4j 4m

) При этом значение набора (Р)

= (Р,, P,...,P„ называется мощностями поставщиков, значения набора. (Q) (Q.,„Q»...-Я „, - мощностями потребителей, а набор неизвестных

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

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

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

: фиг.3 — блок-схема второго блока

"памяти; на фиг.4 — блок-схема тре: тьего блока памяти; на фиг.5 — блок- 15 схема блока вычитания, на фиг.6временная диаграмма работы, реализуемая устройством при следующих исходных данных: n = 2; m = 2; Р, 10; Р =20; Q,=5; QUA=25. 20

Особенностью поставленной задачи является то обстоятельство, что задача целераспределения в канонической форме представляется задачей определения таких n- m неизвестных

Х1 х fz ° ° ° х1

11 1 trl (х) х,х ... х „, х„, х„ ° ° . удовлетворяющих соотношениям (1), называется опорным решением или опорным планом задачи целераспределения.

Устройство (фиг.1) содержит первый 1, второй 2 и третий 3 блоки памяти, блок 4 вычитания, первый 5 и второй 6 вычитающие счетчики, первый 7 и второй 8 компараторы, триггер 9, первый 10 и второй 11 элементы И, первый 12 и второй 13 элементы ИЛИ, первый 14, второй 15, третий

t6 четвертый 17, пятый 18, шестой

19, седьмой 20 и восьмой 21 элементы задержки. На фиг.1 также показаны первый 22, второй 23, третий 24 и четвертый 25 информационные входы, синхронизирующий вход 26, первая (27, 28) и вторая (29, 30) группы информационных входов, группа информационных выходов 31-34 и синхронизирующий выход 35.

Первый блок памяти (фиг.2) с-vepжит дешифратор 36, группу регистров

37, 38, первую 39, вторую 40, третью 41, четвертую 42 и пятую 43 группы элементов И, первую 44, вторую 45, и третью 46 группы элементов ИЛИ,первый 47 и второй 48 элементы И,первый

49, второй 50 и третий 51 элементы

ИЛИ, первый 52 и второй 53 элементы задержки. На фиг.2 также показаны синхронизирующие входы 54-56, адресный вход 57, информационный вход

58, группа информационных входов

59, 60 и информационный выход 61.

Второй блок памяти (фиг.3) содержит дешифратор 62, группу регистров

63, 64, первую 65, вторую 66, третью 67 и четвертую 68 и пятую 69 группы элементов И, первую 70, вторую 71 и третью 72 группы элементов

ИЛИ, первый 73 и второй 74 элементы

И, первый 75, второй 76 и третий 77 элементы ИЛИ, первый 78 и второй 79 элементы задержки. .На фиг.3 также показаны синхронизирующие входы 8082, адресный вход 83, информационный вход 84, группа информационных входов 85,86,и информационный выход 87.

1462345

Третий блок памяти (фиг ° 4) содержит первый 88 и второй 89 дешифраторы, матрицу регистров 90-93 (количество строк этой матрицы равняет-

5 ся числу регистров 37, 38 в группе. первого блока памяти, а количество столбцов этой. матрицы равняется числу регистров 63, 64 в группе второго блока памяти), первую 94 tP и вторую 95 группы элементов И, группу 96 элементов ИЛИ, первый 97, второй 98, третий 99 и четвертый 100 элементы И, первый 101, второй 102, третий 103 и четвертый 104 элемен- 15 ты ИЛИ и элемент 105 задержки.. На фиг.4 также показаны синхронизирующие входы 106 и 107, адресные входы

108 и 109, информационные входы 110, 111 и группа информационных выходов 2р

112-115.

Блок вычитания (фиг.5) содержит сумматор 116, суммирующий счетчик

117, вычитающий счетчик 118, первую

119 и вторую 120 группы элементов И, 25 группу 121 элементов ИЛИ, первый

122 и второй 123 элементы И, первый

124, второй 125, третий 126 и четвертый 127 элементы задержки. На фиг.5 также показаны информационные 30 входы 128 и 129, синхронизирующий вход 130, синхронизирующие выходы

131 и 132, информационные выходы

133-135.

Начальное опорное решение вычисля- З5 ется с помощью процедуры, состоящей из последовательности шагов.

На каждом шаге ресурс (мощность) одного из поставщиков полностью или частично передается одному из потре- . 4р бителей таким образом, чтобы либо исчерпать мощность данного поставщика (и тем самым исключить его из дальнейшего рассмотрения), либо удовлетворить полностью потребность . 45 (мощность) потребления (и тем самым исключить его из дальнейшего рассмотрения).

Известно, что в опорных решениях содержится ровно n+m-1 значащих ком" 5р понент. Незначающне компоненты х .1

11 опорного плана (x ) мы идентифицируем числами -1. Перед началом процедуры заполним матрицу (х ) числами

-1, зададимся наборами (Р 3 и (Q 3 и положим i - =n j = m. Перед началом каждого шага мы проверяем, равняется ли нулю хотя бы один из индекcos i u j. В случае, когда оба индекса положительны, мы выполняем очередной шаг процедуры, в противном случае мы заканчиваем процедуру. На каждом шаге процедуры мы вначале выбираем наибольшее иэ чисел Р; и Ц !

Если P не меньше Q, то элементу х; мы присваиваем значение Я уменьшаем значение Р, на число Q u уменьшаем на единицу индекс j, т.е. исключаем из дальнейшего рассмотрения потребителя с номером j ..

Если Q больше P., то элементу х ..

1J мы присвайваем значение Р;, уменьшаем значение Q. на число Р; и

) уменьшаем на единицу индекс i т.е. исключаем из дальнейшего рассмотрения поставщика с номером

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

Перед пуском устройства на информационном входе 22 должна быть установлена константа 0 (нулевое слово), которая должна присутствовать на входе 22 в течение .всего времени работы устройства, на информационном входе 23 — значение и, не превосходящее числа N регистров 37, 38 группы первого блока памяти, на информационном входе 24 — значение m, не превосходящее числа М регистров

63, 64 группы второго блока памяти, на информационном входе 25 — константа -1, на первые и информационных входов 27, 28 группы — значения мощностей поставщиков Р,, Р,.. °,Р„, на первые m информационных входов

29, 30 группы — значения мощностей потребителей (1,, Устройство начийает работать после поступления на синхпонизирчющий вход 26 импульса П „ « (фиг.б,поз ° 1),. который устанавливает триггер 9 в единичное состояние (фиг.б,поз.2), что разрешает прохождение импуль-.. сов через элемент И 10, Импульс

U„Ä Ä, поступает на синхронизирующие . входы счетчиков 5 и 6, вследствие этого в счетчики 5 и 6 записываются числа п и m соответственно.

Импульс U „„,„ поступает на синхронизирующий вход 54 блока 1 памяти (фиг.2), с выхода 51 - на группы

39 и 40 элементов И, вследствие это- го информационные слова с группы информационных входов 27 и 28 проходят через группы 39 и 40 элементов

И и группы 44 и 45 элементов ИЛИ на входы группы регистров 37, 38 и записываются в эти регистры с помощью

1462345 пульса Б11„0,, прошедшего с синхронизирующего входа 54 через элементы

ИЛИ 49 и 50 на синхронизирующие входь1 регистров.

Импульс Ппус1, поступает на синхронизирующий вход 80 блока памяти

2 (фиг.3), с входа 80 — на группы 65 и 66 элементов И вследствие это1 1, :го информационные слова с группы

;информационных входов 29, 30 прохо, . дят через группы 65 и 66 элементов

И и группы 70 и 71 элементов ИЛИ на

; входы группы регистров 63 и 64 и за,.писываются в эти регистры с помощью .импульса U„„« прошедшего с синхро низирующего входа 80 через элемен; ты ИЛИ 75 и 76 на синхронизирующие

; входы регистров.

Импульс U рУ „ также поступает на ,: синхронизирующий вход 1.07 блока 3 памяти (фиг.4), с выхода 107 - на входы группы 94 элементов И, вслед, :ствие этого информационное слово с

,информационного входа 25 проходит

:,через группу 94 элементов И и груп пу 96 элементов ИЛИ на входы всех

: регистров 90-93 матрицы и записывается в эти регистры с помощью импульса Б„, поступившего на син11УСк хронизирующие входы регистров с синхронизирующего входа 107 через элементы ИЛИ 101-104.

Таким образом, импульс U и„ „ обеспечивает запоминание числа и строк матрицы (х 1 в счетчике 5, числа m столбцов матрицы (х ) — в счетчике

6 ° набора мощностей поставщиков (Р )— в регистрах первого блока памяти, набора мощностей потребителей (Q ) в регистрах второго блока памяти и занесение во все регистры третьего лока памяти числа -1.

Кроме этого,-импульс П 11с1, » задер жанный на элементе 14 задержки на время считывания и запоминания информацйи, проходит через элемент

ИЛИ. 12, после чего задерживается на элементе 16 задержки на время (это время равно времени возможного переброса триггера 9 в нулевое состояние), и, поскольку триггер находится в единичном состоянии, на выходе элемента И 10 образуется тактовый импульс U „„,(фиг.б,поз.З).

Обозначим содержимое регистра 5 через i а содержимое регистра 6через j, С выхода элемента И 10 импульс

U»„, поступает на синхронизирующий вход 55 первого блока памяти (фиг ° 2), Через элемент ИЛИ 51 импульс U, поступает на синхронизирующий вход дешифратора 36, который в соответствии с адресным словом, находящимся на адресном входе 57 (т.е. в

lp соответствии с содержимым счетччка 5), выставляет на одном из своих выходов высокий потенциал, тем самым разрешая прохождение через одну из групп 41 и 42 элементов И со. держимого одного из регистров 37, 38 группы в момент прихода импульса U „, задержанного на элементе

52 задержки на время срабатывания дешифратора. После этого на выходе

20 только одной из групп 41, 42 элементов И будет находиться содержимое соответствующего регистра, а на выходах всех остальных групп

41, 42 будут выставлены нулевые

25 слова, поэтому на выходе группы 46 элементов ИЛИ будет выставлено слово, хранящееся в регистре, опреде-. ляемом адресным словом на адресном входе 57. Таким образом, с помощью импульса U «, на информационном выходе 61 блока 1 памяти выставляется значение Р;.

Тактовый импульс U т-„ также поступает на синхронизирующий вход

81 второго блока памяти (фиг.3). Че35 рез элемент ИЛИ 77 импульс U т поступает на синхронизирующий вход дешифратора 62, который в соответствии с адресным словом, находящимся на адресном входе 83 (т.е, в соответствии с содержимым счтетчика

6), выставляет на одном из своих выходов высокий потенциал, тем самым разрешая прохождение через одну из

45 групп 67 и 68 элементов И содержимого одного из регистров групп 63, 64 в момент прихода импульса U„ задержанного на элементе 78 задержки на время срабатывания дешифратора. После этого на выходе только

50 однои из групп 67, 68 элементов И находится содержимое соответствующего регистра, а на выходах всех ос тальных групп 67, 68 выставлены нулеВые слоВа пОэтому на ВыхОде Fp » пы 72 элементов ИЛИ выставлено слово, хранящееся в регистре, определяемом адресным словом на адресном входе 83, Таким образом, с помощью

1462345 импульса U „, на информационном выходе 87 блока 2 памяти выставляется значение Я

Тактовый импульс U Ä>» задержанный на элементе 18 задержки на время работы блоков 1 и 2 памяти, формирует на синхронизирующем входе 130 блока вычитания 4 (фиг.5) импульс (Фиг.б, поз.4). К этому моменту времени на информационных входах 128 и 129 блока 4 уже выставлены значения Р; и Q . соответственно.

Импульс UT „ поступает с синхронизирующего входа 130 на синхронизирующий вход суммирующего счетчика 117, записывая в него значение

Q ° в обратном коде (Q ) Б, импульс

0так а, задержанный на элементе

125 задержки на время записи Q в 20 счетчик 117, попадает на суммирующий вход счетчика 117, в результате на выходе этого счетчика формируется значение Q . в дополнительном коде

3 (Q ) д,„. На выходы сумматора 116 25 поступают значения Р,. и (Q ) „, после суммирования на выходе сумматора будет сформировано значение P. +

+ (Q ) дю„. Известно, что если Р,.

О, то Р; + (Я1) „представ- 30 ляет собой разность Р; — Q> в прямом коде, если же Р; — Q < О, то Р, +

+ (Qj)+ Ä есть значение разности (Р; - Q ° )д,„ в дополнительном коде.

На ийформационный вход вычитающего счетчика 118 с выхода сумматора поступает слово P., + (Q .)«„ которое записывается в этот счетчик по приходу импульса UT 4, задержанного на элементе 127 задержки 40 на время работы счетчика 117 и сумматора 116. Этот же импульс U» «„„q, задержанный на элементе 126 задержки на суммарное время работы сумматора 116, работы счетчика 117 и записи в счетчик 118, поступает на вычитающий вход счетчика 118, в результате на инверсном выходе счетчика

118 будет сформировано значение (Р, + (Q j),„)*,„..

На элемент И 122 поступает значе- 50 ние знакового разряда суммы Р1 +

+ ((), „, а на элемент И 123 - инг версное значение этого знакового разряда, на вторые входы элементов

И 122 и 123 приходит импульс U „ q g задержанный на элементе 124 задерж-: ки на время работы сумматора 116 и, счетчиков 117 и 118.

Если формируется импульс HB выходе элемента И 122 (что равносительно

Р; — О < О), то на информационный выход 135 через группу 119 элементов И и группу 121 элементов ИЛИ проходит значение Р;, в противном случае (Р; - Q „ ъ О) на информационный выход 135 через группу 120 элементов И и группу 121 элементов

ИЛИ проходит значение Q . Иными слоJ вами на информационном выходе 135 формируется значение мин 1Р,, Итак, в результате работы блока вычитания в случае Р. 7j Q . на ин1 j формационном выходе 133 выставлено значение Р; — Q в прямом коде, на информационном выходе 134 — значение (Я вЂ” Р;) д,„ в дополнительном коде, на информационном выходе 135— значение Q. и сформирован импульс

U p (фиг. б, поз. 6) на синхронизирующем выходе 131, а в случае Р; на информационном выходе 133 выставлено значение (Р; — О )4,„ в допол-. нительном коде, на информационном выходе 134 — значение Q - P в пряJ мом коде, на информационном выходе

135 — значение Р; и сформирован импульс UQ (Фиг.б, поз.7) на синхронизирующем выходе 132.

Тактовый импульс U « задержанный на элементе 19 задержки на время с> работы блоков 1, 2 и 4, формирует на выходе элемента 19 задержки импульс U „ (фиг.б,поз,5), который попадает на синхронизирующий вход 106 блока 3 памяти (фиг.4).

К этому моменту времени на адресных входах 108 и 109 выставлены значения i и j, а на информационном входе

111 находится значение мин tP .,Q .).

1 i

Импульс У „ попадает на синхронизирующие входы дешифраторов

88 и 89, которые в соответствии с адресными словами, находящимися на адресных входах 108 и 109, выставляют высокий потенциал на выходе дешифратора 88 и на выходе j дешифратора

89. Импульс U> подается также на группу 95 элементов И, пропуская тем самым информационное слово с информационного входа 111 через группу элементов И и группу 96 элементов ИЛИ на входы всех регистров матрицы 90-93. Импульс U „, задержанный на элементе 105 задержки на время срабатывания дешифраторов, проходит через тот из элементов И

1462345

97, 98, 99, 100, входы которого соединены с выходом i дешифратора 88 и выходом j дешифратора 89, и проходит через один из элементов 101

104 на синхронизирующий вход одного из регистров.

Таким образом, в регистр матрицы

90-93, соответствующий элементу х, начального опорного решения, в случае Р; - Я записывается значение а в случае Р; (Q . записывает:ся значение Р,.

Если на синхронизирующем выходе

131 блока 4 был сформирован импульс то этот импульс поступает на син хронизирующий вход 56 блока 1 (фиг.2), на информационном входе 58 которого сформировано значение P, — Q . .в пря20 мом коде. Импульg Uð через элемент

ИЛИ 51 проходит на синхронизирующий вход дешифратора 36, который выставляет высокий потенциал на своем выходе с нОмерОм 1, поскольку на адресном входе дешифратора по-прежнему выставлено содержимое счетчика 5, т.е. i. Импульс U< разрешает прохождение значения P - Q .с вы1 1 хода 58 через группу 43 элементов И и группы 44 и 45 элементов ИЛИ на информационные входы всех регистров

37 и 38 группы. Импульс U, задер, жанный на элементе 53 задержки.на время срабатывания дешифратора 36, проходит через один из элементов 35

И 47, 48 и один из элементов ИЛИ

49, 50 на синхронизирующий вход регистра, соответствующего выходу с номером i дешифратора 36. Таким об-. разом, в регистр, в котором храни- 40 лось значение P, будет записано значение Р; - Q .. Импульс Uð. будучи задержанным на элементе 21 за держки на время записи значе,ния Р, — Q в блок 1, формирует на 45 выходе элемента 21 задержки импульс

U, (фиг.б, поз.8), который постуp1 ° пает на вычитающий вход счетчика

6, уменьшая тем самым его содержимое, т.е. в счетчике 6 будет после этого находиться число j-1.

Если на синхронизирующем выходе

132 блока 4 был сформирован импульс

U@, то этот импульс поступает на синхронизирующий вход 82 блока 2 (фиг.3), на информационном входе

84 которого сформировано значение

Q . .— P в прямом коде, Импульс Ug ! через элемент И 77 проходит на синхронизпрующий вход дешифратора 62, который выставляет высокий потенциал на своем выходе с номером j, поскольку на адресном входе дешифратора по-прежнему выставлено содержимое счетчика 6, т.е. j. Импульс

U> разрешает прохождение значения

- P; с выхода 84 через группу

69 элементов И и группы 70, 71 элементов ИЛИ на информационные входы всех регистров 63, 64 группы. Импульс U<, задержанный на элементе

79 задержки на время срабатывания дешифратора 62, проходит через один из элементов И 73, 74 и один из элементов ИЛИ 75, 76 на синхронизирующий вход регистра, соответствующего выходу с номером j дешифратора 62.

Таким образом, в регистр, в кото- ром хранилось значение Q ., будет записано значение Q — Р;. Импульс

U@, будучи задержайным на элементе

20 задержки на время С, записи значения Q — Р; в блок 2, формирует на выходе элемента 20 задержки импульс U g, (фиг.б, поз.9), который поступает на вычитающий вход счетчика 5, уменьшая тем самым его содержимое на единицу, т,е. в счетчике

5 будет после этого находиться значение i-1.

Итаку кажцый импульс UÄ.. Обеспечивает осуществление цикла работы блоков 1-4, причем в результате этого цикла выполняется один шаг процедуры вычисления начального опорного решения. После уменьшения на единицу содержимого одного из счетчиков 5 и 6, значения, записанные в этих регистрах, сравниваются с нулем в компараторах 7 и 8, что обеспечивается приходом на синхронизирующие входы компараторов тактового импульса U с выхода элемента И 10, та кт причем этот импульс был задержан на элементе 17 задержки на время работы блоков 1-4 и на время обновления содержимого одного из счетчиков 5 и 6 (фиг. 1) .

Если в обоих счетчиках хранятся положительные величины, то на выходах обоих компараторов будет низкое значение потенциала. Низкое значение потенциала будет также присутствовать на выходе элемента ИЛИ 13, что запрещает прохождение через элемент И 11 импульсов с выхода эле мента ИЛИ 12 (т.е. тактовых импуль1462345

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

50 сов 0 „,, задержанных на элементе

15 задержки на время Г работы блоков 1-4, счетчиков 5 и 6 и компараторов 7 и 8). Следовательно, 5 триггер 9 остается в единичном состоянии и на выходе элемента И 10 формируется новый тактовый импульс

Uppity (фиг.6, поз.З), что влечет за собой выполнение нового цикла работы блоков 1-4.

Если же содержимое хотя бы одного из счетчиков 5 и 6 станет равным нулю, это приведет к появлению высокого потенциала на выходе элемента 15

ИЛИ 13, что в свою очередь разрешит прохождение через элемент И 11 импульса с выхода элемента ИЛИ 12, Сформированный на выходе элемента

И 11 импульс U „,t, (фиг.б,поз.10) 20 поступает на вход установки в ноль триггера 9 и переводит триггер в нулевое состояние, что запрещает прохождение импульсов через элемент

И 10, т.е. запрещает формирование новых тактовых импульсов.

Импульс U „ „, с синхронизирующего выхода 35 используется в качестве сигнала прерывания вычислительного комплекса, по которому вычисли- 30 тельный комплекс запускает программу опроса группы информационных выходов

31-34, на которых сформированы значения компонент начального опорного решения задачи целераспределения.

Таким образом, введение новых узлов и элементов позволяет существенно повысить быстродействие устройства. Время решения задачи вычисления начального опорного плана на 40 устройстве-прототипе при различных исходных данных составляет 18-23 мин, то же на предлагаемом устройстве занимает 8,5-12 мин.

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

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

1462345

14!

P.dknd

81 бринк

5tt

А5реснь

tkOd

Сиихр. Ck

Сикху. й

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

5 вычитающего счетчика соединен с адресным входом второго и вторым адресным входом третьего блоков памяти, .выход первого элемента И соединен через пятый элемент задержки с син хронизирующим входом блока вычита-! ния, выходы первого и второго бло: ков памяти соединены соответственно

: с первым и вторым информационными 15

:, входами блока вычитания, первый и второй синхронизирующие выходы которого соединены с третьими синхро: ни"-ирующими входами соответственно первого и второго блоков памяти, вы- 20

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

5462345

Инк

Ф.йети

Адреж8

Гю. индо. дкИИ

Инщ. b»og

Синлр.б

Синлр. д»

82 фив.3

Мреет

108

Адресный

509

0инкр. d»

507

Фнд. d»u

110

Jfep. дки

Див,4

Син»Р.блад 108

106

1462345 онкР. ФхИ ар, Isa

123

sp.1хс0

СиИЛР,ВР

f ЯО юг

Составитель A.Ïàê

Редактор Т.Парфенова Техред Л.Олийнык

Корректор И.Муска

Заказ 715/49 Тираж 667 Подписное

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

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

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