Устройство для моделирования сетей Советский патент 1993 года по МПК G06F15/20 G06F15/419 

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

C JTflX.

Целью изобретения является сокращение объема оборудования.

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

Модель 19 ветви устройства содержит с пэрвого по десятый элементы И 1-10, с пер- в )го по четвертый триггеры 11-14, первый и второй элементы ИЛИ 15, 16, элемент 17 индикации, формирователь 18 временного интервала, вход 21 модели ветви. Блок 22 у травления содержит третий, первый, вто- рэй и четвертый триггеры 23-26, счетчик 27 иипульсов, четвертый, второй, третий, шестой, первый, пятый и седьмой элементы И

28-34, элемент ИЛИ 35, элемент НЕ 36. Кроме того, устройство содержит генератор 37 импульсов и многовходовой элемент ИЛИ 38, второй и третий выходы 39 и 40 модели 19 ветви, третий выход 41 блока 22 управления, а восьмой выход 42, второй вход 43 блока 22 управления, первый выход 44 модели 19 ветви, входы 45i-45n элемента ИЛИ 38, первый вход 46 блока 22, второй выход 47 блока 22, второй вход 48 модели 19, первый выход 49 блока 22 первый вход 50 модели 19, пятый и четвертый выходы 51 и 52 блока 22 управления, третий вход 53 модели 19, шестой вход 54 модели 19 ветви, пятый вход 55 модели 19 ветви, седьмой и шестой выходы 56, 20 блока 22, четвертый вход 21 модели 19 ветви.

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

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

ы

XS

ел

В исходном состоянии, перед решением задачи на устройстве, модели 19 ветви посредством полюсов 39 и 40 коммутируются между собой в соответствии с конфигурацией моделируемой сети, полюсами 41 и 42 блок 22 управления подключается к полюсам тех моделей, между которыми отыскивается указанный путь, и в счетчики 18 всех моделей ветвей заносится число импульсов (N-qij) где N - емкость счетчика. Триггеры всех моделей ветвей, триггеры блока управления и счетчик 27 импульсов устанавливаются в нулевое состояние.

Работа устройства начинается с момента установки триггера 23 в единичное состояние, которое выдает разрешение на вход элемента И 33, При этом импульсы генератора 37, поступающие на полюс 43 блока 22 управления, проходят через элемент И 33 и поступают на входы элементов И 28,30 и 29. Через элементы И 28 и 29 импульсы не пройдут, так как они заблокированы нулевыми состояниями триггеров 24 и 26, а через элемент И 30 импульсы пройдут. С выхода элемента И 30 импульсы поступают на вход элемента ИЛИ 35 и на полюс 41 блока 22 управления. Импульсы через элемент И 32 не пройдут потому, что на другом ею входе нет разрешения, снимаемого с единичного выхода триггера 25.

Импульсы с полюса 41 блока 22 управления поступают на полюса 39 или 40 моделей 19 ветвей, которые в результате коммутации этими полюсами между собой образуют вершину сети, из.которой отыскивается путь с наибольшей пропускной способностью.

В указанных моделях 19 ветвей импульсы с полюсов 39 или 40 поступят на входы элемента ИЛИ 15 и элементов И 1-4, 6 и 8. Элементы И 1-4, 6 и 8 заблокированы, и через эти элементы импульсы проходить не будут. На одном из входов элемента ИЛИ 15 есть разрешение, и поэтому импульсы прой-- дут через этот элемент на вход элемента И 5. С выхода элемента И 5 импульсы поступят на вход элемента ИЛИ 16 и, пройдя его, поступят на единичный вход триггера 11. По первому импульсу из всей серии импульсов, поступивших в модель 19 ветви на полюса 39, 40 триггер 11 установится в единичное состояние. Все последующие импульсы будут подтверждать это состояние триггера 11.

Единичное состояние триггеров 11 выдает разрешение на вход элемента И 9. Это разрешение поступит на полюс 44 модели, так как на другом входе элемента И 9 есть разрешение, снимаемое с нулевого выхода триггера 13.

С полюса 44 модели 19 ветви разрешение поступит на соответствующий вход 45ч- 45п многовходового элемента ИЛИ 38. На входы элемента ИЛИ 38 поступят разрешения только тех моделей ветвей, которые своим полюсом 39 или 40 связаны с полюсом 41 блока 22 управления. Единичное состояние триггеров 11 свидетельствует о том, что данная модель ветви принадлежит выбранному

0 разрезу (xjXj) из множества разрезов К. Это соответствует первому шагу решения задачи.

Выбор модели ветви, принадлежащей сформированному разрезу, с наибольшей

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

0 по разрешению многовходового элемента ИЛИ 38. Это разрешение поступает на полюс 46 блока 22 управления. С полюса 46 в блоке 22 управления разрешение поступает на вход элемента НЕ 36 и через элемент И

5 34 на единичный вход триггера 24. В результате элемент НЕ 36 снимает разрешение с полюса 47 блока 22 управления и, следовательно, с полюсов 48 всех моделей ветвей, что заблокирует вход элемента И 7 моделей

0 ветвей.

Разрешение поступившее на единичный вход триггера 24, установит его в единичное состояние. Единичное состояние триггера 24 запретит прохождение импуль5 сов от генератора 37 импульсов через элементы И 30 и ИЛИ 35 на полюс 41 блока управления и разрешит прохождение импульсов через элемент И 28 на вход счетчика 27 импульсов и полюс 49. С полюса 49 блока

0 22 управления импульсы поступят на полюс 50 всех моделей 19 ветвей.

В моделях 19 ветвей импульсы с полюса 50 поступают на вход счетчика 18 импульсов до его переполнения. Импульс переполне5 ния счетчика 18 модели ветви поступает на нулевые входы триггеров 12 и 1.1 и на единичный вход триггера 13. В результате триггер 11 установится в нулевое состояние, если ранее он был установлен в единичное

0 состояние импульсами, поступившими на

полюса 39 или 40 модели ветви.

о

Триггер 13, установленный в единичное состояние поступившим на его единичный 5 вход импульсом переполнения счетчика 18, установится в нулевое состояние очередным импульсом, поступившим на полюс 50. Это происходит потому, что триггер 14 находится в нулевом состоянии и есть разрешение на элемент И 10.

Установка в нулевое состояние тригге- ов 11 импульсов переполнения счетчика 18 роизводит выбор модели ветви, у которой аи большая пропускная способность среди сех выделенных ветвей. Это происходит в взультате того, что триггер 11 снимет в оответствующих моделях ветвей разреше- ие с полюса 44 и, следовательно, с входов 5 многовходового элемента ИЛИ 38.

В тот момент, когда будет снято послед- ее разрешение с входа 45, элемента ИЛИ 8, блок 22 управления выдаст разрешение а полюс 47. Это разрешение поступит на юл юса 48 всех моделей 19 ветвей. При этом модели ветви с наибольшей пропускной пособностью из выбранного разреза триг- ер 14 установится в единичное состояние азрешением, снимаемым с единичного вы- ода триггера 13.

В этом случае триггер 13 останется в диничном состоянии, так как единичное остояние триггера 14 запретит прохожде- ие очередного импульса с полюса 50 через лемент И 10 на нулевой вход триггера 13. Единичное состояние триггера 14 моде- и 19 ветви выдает разрешение на входы лементов И 1 и 2, что обеспечивает исклю- ение моделей ветвей из дальнейшего рас- мотрения и закорачивание полюсов 39 и 0.Таким образом, в моделях ветвей, у ко- орых пропускная способность максималь- а на данном шаге, триггеры 14 и 13 будут становлены в единичное состояние и их олюс 39 будет закорочен с полюсом 40. чонец этого шага работы устройства опре- .еляется моментом появления импульса пе- еполнения счетчика 27 блока 22 правления. К этому моменту в счетчиках 18 сёх моделей 19 ветвей восстановится ин- юрмация о их пропускной способности, т.е. роизойдет регенерация, Роль регенераци- нного счетчика для счетчиков 18 всех моде- ей 19 ветвей выполняет счетчик 27 блока 22 управления. Он начинает свой счет с О, л его емкость равна N, а счетчики 18 моде- пей 19 ветвей начинают счет с N-qij.

Импульс переполнения счетчика 27 блока управления поступит через элемент ИЛИ 35 на полюс 41 блока 22 управления. Далее, этот импульс с полюса 41 поступит на полюс 39 и 40 моделей 19 ветвей, и весь процесс работы повторится аналогично рассмотренному.

Такие итерационные процессы будут повторяться до тех пор, пока импульс переполнения счетчика 27 блока 22 управления, поступающий на полюс 41, не появится на полюсе 42.

j В момент появления импульса на полюсе 42 блока 22 управления все множество

ветвей моделируемой сети будет разбито на два подмножества. Одно подмножество содержит ветви, пропускная способность qij которых удовлетворяет условию, и в соответствующих их моделях 19 ветвей триггера 14 и 13 находятся в единичном состоянии. Другое подмножество содержит ветви с пропускными способностями, которые не удовлетворяют условию, и их триггеры 14 и

0 13 останутся в нулевом состоянии. Эти модели ветвей из дальнейшего рассмотрения исключаются, так как их триггер 13 находится в нулевом состоянии.

Дальнейшая работа устройства состоит

5 из формирования пути с наибольшей пропускной способностью и его индикации. Для этого в блоке 22 управления импульс, поступивший на полюс 42, установит триггер 24 в нулевое состояние, а триггер 26 - в единич0 ное.

Нулевое состояние триггера 24 запретит прохождение импульсов генератора 37 с полюса 43 через элемент И 28 на вход счетчика 27 и полюс 49 блока 22 управления.

5 Следовательно, на полюсе 50 всех моделей ветвей импульсы генератора 37 перестанут поступать.

Единичное состояние триггера 26 снимает разрешение с полюса 51 и выдаст сиг

0 нал на полюс 52 блока 22 управления.

Съем разрешения с полюса 51 блока . управления соответствует съему разре ие- ния с полюса 53 всех моделей 19 ветвей, что блокирует элемент И 5 этих моделей.

5 Сигнал, появившийся на полюсе 52 блока 22 управления, поступит на полюс 54 всех моделей ветвей и установит триггеры 14 моделей в нулевое состояние. Нулевое состояние триггера 14 модели 19 ветви разрывает

0 закоротку полюсов 39 и 40, что осуществляется за счет снятия разрешения с входов элементов И 1 и 2. Одновременно с этим импульсы генератора 37 начнут опять поступать через полюс 43, элементы И 33, И 30,

5 ИЛИ 35, полюс 41 на полюсе 39 или 40 моделей 19 ветвей. При этом, на полюс 50 моделей 19 ветвей импульсы поступать не будут, так как нет разрешения на входе элемента И 28 от триггера 24 блока 22 управле0 ния, В указанных моделях 19 ветвей импульсы с полюса 39 поступят на вход элемента И 6 тех моделей, триггера 13 которых находится в единичном состоянии, и пройдут через него. При этом на другом входе

5 элемента И 6 есть разрешение, поступаю- . щее с полюса 55 модели ветви и, следовательно, через полюс 56 с нулевого выхода триггера 25 блока 22 управления.

В модели 19 ветви импульсы поступят через элемент ИЛИ 16 на единичный вход

триггера 11. По первому импульсу из всей серии импульсов, поступивших в модель 19 ветви на полюс 39, триггер 11 установится в единичное состояние. Единичное состояние триггера 11 выдает разрешение на элемент И 4. Поэтому остальные импульсы из всей серии с полюса 39 через элемент И 4 поступят на полюса 40 модели 19 ветви. Это произойдет у тех моделей, у которых триггер 18 находится в единичном состоянии. Таким образом, импульсы будут распространяться по сети через модели ветвей, у которых триггеры 13 находятся в единичном состоянии, до тех пор, пока они не появятся на полюсе 42 блока 22 управления.

Поступивший на полюс 42 блока 22 управления импульс пройдет через элемент И 31, так как триггер 26 находится в единичном состоянии, и установит триггер 25 в единичное состояние. Единичное состояние триггера 25 выдает разрешение на полюс 20, снимает разрешение с полюса 56, выдает разрешение на элементы и 32 и 29 и снимает разрешение с элемента И 30. При этом с полюсов 55 моделей 19 ветвей снимается разрешение, что заблокирует их элементы И 6, и на полюсах 21 появится разрешение, что разрешит прохождение сигналов через элемент И 8. Одновременно импульсы генератора 37 через элементы И 33 и 29 поступят на полюс 42 и далее на полюса 40 моделей 19 ветвей, к которым подключен полюсом 42 блок 22 управления.

С полюса 40 в модели 19 ветви импуль- сы через элементы И 8 поступят на единичный вход триггера 12. По первому импульсу из серии импульсов, поступивших на полюс 40, триггер 12 установится в единичное состояние, которое выдает разрешение на элемент И 3. Поэтому остальные импульсы пройдут через элемент И 3 и поступят на полюс 39. Это происходит только у тех моделей ветвей, у которых триггер 13 находится в единичном состоянии. Таким образом, импульсы будут распространяться по сети через модели ветвей с полюса 40 на полюс 39 до тех пор, пока не появится на полюсе 41 блока 22 управления.

С полюса 41 блока 22 управления им- пульсы поступят через элемент И 32 на нулевой вход триггера 23, и первый из них установит этот триггер в нулевое состояние. Нулевое состояние триггера 23 сигнализирует о конце решения задачи. При этом мо- дели 19 ветвей, у которых триггеры 12 и 11 находятся одновременно в единичном состоянии, принадлежат искомому пути. Эти модели индицируются элементом 17 индикации.

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

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

иестой вход модели ветви подключен к нулевому входу четвертого триггера, нулевой выход которого подключен к второму входу седьмого элемента И, выход которого подключен к нулевому входу третьего триггера, Ёлок управления содержит четыре триггера, семь элементов И, счетчик импульсов, эле- кент НЕ, четвертый элемент ИЛИ, выход которого подключен к первому входу одиннадцатого элемента И и является первым полюсом блока управления, выход двенадцатого элемента И является вторым полю- сэм блока управления и соединен с нулевым входом пятого триггера, единичным входом шестого триггера и.первым входом тринад цатого элемента И, второй вход которого сэединен с первым входом двенадцатого элемента И, является третьим выходом бло- кз управления и подключен к единичному в шестого триггера, нулевой выход ко- торого является четвертым выходом блока у травления и подключен к первым входам ч пырнадцатого и пятнадцатого элементов И, первый вход шестнадцатого элемента И подключен к единичному выходу седьмого триггера, нулевой вход которого подключен к выходу одиннадцатого элемента И, второй в: сод которого является пятым выходом бло- к,1 управления и подключен к второму входу дзенадцатого элемента И и к единичному выходу восьмого триггера, единичный вход которого подключен к выходу тринадцатого элемента И, нулевой выход восьмого триггера является шестым выходом блока управления и подключен к первому входу семнадцатого элемента И, второй вход которого подключен к нулевому выходу пятого триггера, единичный выход которого подключен к второму входу четырнадцатого элемента И, выход которого является седьмым выходом блока управления и подключен к входу счетчика импульсов, выход которого подключен к первому входу четвертого элемента ИЛИ, второй вход которого подключен к выходу семнадцатого элемента И, выход элемента НЕ является вторым выходом блока управления, а вход элемента НЕ подключен к выходу первого элемента ИЛИ и второму входу пятнадцатого элемента И, выход которого подключен к единичному входу пятого триггера, выход генератора импульсов подключен к второму входу шестнадцатого элемента И, выход которого подключен к третьим входам двенадцатого, семнадцатого и четырнадцатого элементов И блока управления, отличающееся тем, что, с целью сокращения объема оборудования, в каждой модели ветви первый и второй полюсы подключены соответственно к первому и второму входам третьего элемента ИЛИ, выход которого подключен к первому входу девятого элемента И, единичный выход первого триггера подключен к второму входу восьмого элемента И, выхо; шестого элемента И подключен к единично- му входу второго триггера.

Фиг. 1

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