Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

состояние, подает разрешающий потенциал на шину Е, а на шину L — одиночный импульс, синхронизированный с тактовыми им­ пульсами, и одновременно разрешает поступление тактовых импуль­ сов на вход операционного счетчика. При этом, так как на полюсах т всех моделей узлов имеем запрещающий потенциал, указанный одиночный импульс через крнъюнктор 15 (по разрешению выходного потенциала инвертора 19) и дизъюнктор 18 поступит на входы ре­ гистров сдвига упомянутых моделей и далее—на входы соответствую­ щих моделей ветвей. В моделях ветвей, входящих в конечный узел мультисети, указанный импульс проходит через конъюнктор 5 (по разрешению потенциала единичного выхода триггера 13 модели конечного узла) и в тех из них, триггер 1 которых находится в еди­ ничном состоянии, поступает через конъюнктор 7 (по разрешению потенциала единичного выхода упомянутого триггера и потенциала на шине Е) на единичный вход триггера 2, устанавливая его в единичное состояние. Одновременно по сигналу на шине F УЦА выдает запрещающий потенциал на шину Е.

Таким образом, в единичном состоянии окажутся триггеры 2 моделей тех ветвей, входящих в конечный узел мультисети и при­ надлежащих равновеликим путям известной допустимой длины в него, длины которых минимальны, т. е. искомых ветвей. Потенциал единичного выхода триггера 2 может управлять схемой индикации соответствующей выделенной ветви (на рис. 82, а такая схема не показана).

Одновременно с переключением триггеров 2 упомянутый оди­ ночный импульс (длительность которого превышает время переклю­ чения триггера) через конъюнктор 4 (по разрешению потенциала единичного выхода триггера 2 ) и дизъюнктор 8 моделей соответству­ ющих ветвей поступает на вход модели конечного узла мультисети. Так как длительность задержки сигнала в регистре сдвига модели конечного узла мультисети равна нулю, одновременно с этим по сигналу на выходе упомянутой модели узла УЦА запрещает по­ ступление импульсов на вход операционного счетчика устройства управления, содержимое которого при этом будет соответствовать длине выделенной ветви (или ветвей).

Далее осуществляется переключение триггеров 14 моделей узлов. Для этого из УЦА подается одиночный импульс на шину N,

азатем, сдвинутый относительно первого, второй импульс на шину Q. В соответствии с коммутацией моделей ветвей и узлов первый упомянутый импульс через конъюнктор 16 (по разрешению потен­ циала единичного выхода триггера 2 соответствующей модели ветви) установит в единичное состояние триггер 14 моделей начальных уз­ лов выделенных ветвей, а второй — через конъюнктор 17 (по раз­ решению потенциала единичного выхода того же триггера) переклю­ чит в нулевое состояние триггер 14 модели конечного узла мультисети.

Каждый последующий цикл определения ветвей, составляющих искомый путь (или подсеть искомых путей), отличается от описан­ ного следующим.

1 3 9

Рассмотрим пример, иллюстрирующий принцип и последова­ тельность выделения ветвей, представляющих решение задачи, в процессе работы моделирующего устройства. Пусть в мультисети, изображенной на рис. 85, требуется определить путь заданной до­ пустимой длины 10 < Lx < 12.

1 - й ц и к л . При «опросе» НАМ определена фактическая дли­ на искомого пути: Lx = 10. Эта величина записана в запоминающий счетчик устройства управления. В единичное состояние установле­

ны триггеры 1 моделей ветвей Іі\ъ, и\ъ, ills. При выделении ветвей в единичное состояние установлены триггеры 2 моделей ветвей U\s, U\s. Содержимое операционного счетчика соответствует числу 2. При

переключении триггеров моделей узлов в единичное состояние уста­ новлены триггеры 14 моделей третьего и четвертого узлов, триггер 14 модели конечного узла мультисети переключен в нулевое состояние.

2 - й ц и к л . При «опросе» ЦАМ в единичное состояние уста­

новлены триггеры 1 моделей ветвей U\z,U\z, Ul4, U3 1 , Uu. При выде­ лении ветвей в единичное состояние установлены триггеры 2 моде­

лей ветвей U\3 , Ulv U\\. Содержимое операционного счетчика со­ ответствует числу 5. При переключении триггеров моделей узлов в единичное состояние установлен триггер 14 модели второго узла.

3 - й ц и к л . При «опросе» ЦАМ в единичное состояние уста­

новлен триггер 1 модели ветви При выделении ветвей в единич­ ное состояние установлен триггер 2 модели той же ветви. Содержи­ мое операционного счетчика соответствует числу 10. При переклю­ чении триггера моделей узлов в единичное состояние установлен триггер 14 модели начального узла мультисети. Процесс завершен.

Выделенные ветви І/І2 , Ц\ъ, іі\і , £/зь U3 5 , образуют подсеть равновеликих путей длины 1 0 .

Для построения управляющего цифрового автомата воспользу­ емся записью условий его работы в виде таблицы включений [481. С этой целью предварительно введем, обозначения входных и выход­ ных каналов УЦА.

Входные каналы УЦА определяются следующими функциональ­ ными связями: Ay — от узла пуска моделирующего устройства; х2 — с единичного выхода триггера 14 модели конечного узла мультисе­ ти; х 3 — с выхода канала сравнения кода ЗС и кода регистра ми­ нимальной допустимой длины задатчика длины пути; х4 — с выхода

141

Т а к т ы

г и ,-

ги2

X,

У,'

У," XI

#

У/ XI XfO

yj

у/

Xs

X,

у:

У,>

к

у/

у/

х;

х;-

%

XI

хв

Уг

у;

х ;

Уі

у»

у*

у.і

Уі

Уг

у„

у,

' у»

Рис. 86

канала сравнения кода ЗС и кода регистра максимальной до­ пустимой длины задатчика длины пути; х5 — с выхода канала сравнения кода ЗС и кода ОС; хв — с шины/З; х7 — с выхода модели конечного узла мультисети; х8 — с шины F; ха — с единичного вы­ хода триггера 14 модели начального узла мультисети.

Выходные каналы УЦА определяются такими функциональными связями: уг — на шину А; у2 — на вход модели начального узла мультисети; у 3 — к схеме управления поступлением импульсов на вход ЗС; уц — к схеме управления поступлением импульсов на вход ОС; уъ — на шину С; ув — на шину установки ОС и регистров 13 моделей узлов в нулевое состояние (шина «Сброс-1»); г/7 — на шину Е; ys — на шину L; г/8 — на шину N; у1 0 — на шину Q.

Так как первый и последующие циклы выделения ветвей искомо­ го пути отличаются лишь условиями поступления сигналов на шину С (уъ) и в схему управления входом ЗС (у3), то используя соотношения

можно составить таблицу включений УЦА для обобщенного цикла работы моделирующего устройства (рис. 86).

Условие реализуемости таблицы включений автомата логиче­ ской схемой на операторах И, ИЛИ, НЕ требует, чтобы различным состояниям выходных сигналов соответствовали различные состоя­ ния входных сигналов. В приведенной на рис. 86 таблице включений УЦА это условие нарушается, так как имеются совпадающие такты, т. е. такты, в которых состояния выходных сигналов различны, а входных — одинаковы. Для устранения совпадающих тактов сле­ дует ввести дополнительные входные сигналы, которые можно полу­ чить за счет образования обратных связей в УЦА. В качестве эле­ ментов обратной связи применим триггеры, а для устранения воз­ можного явления «гонок» триггеров при переключении, с целью повышения надежности работы схемы, используем двухтактное им­ пульсное питание УЦА: ГИ± — импульсы тактового генератора, ГИ 2 — импульсы, сдвинутые во времени относительно первых. Длительность импульсов ГИХи ГИ2 выбирается такой, что

где тги, — длительность импульса ГИ{, тГИг — длительность им­ пульса ГИ2; тт — время переключения триггера.

Сигналы включения и выключения триггеров отмечены в табли­ це включений рис. 86 крестиком х и обозначены через уі, уі соот­ ветственно. Выходные сигналы триггеров обозначены через х,-, хіѣ Учитывая (5.17), время переключения триггер условно принято равным нулю.

Схема УЦА, построенная в соответствии с таблицей включений и с учетом отношений (5.16), (5.17), приведена на рис. 87, где 1—8 — триггеры; 2, 10 — инверторы; 11—28 — конъюнкторы; 29—36 — дизъюнкторы.

143