<<
>>

Переключение соединений в канале

Канал представляет собой область, ограниченную верхними и нижними рядами выводов. Выводы имеют сквозную нумерацию слева направо. Не теряя общности, рассмотрим верхний ряд выводов. Пусть к ряду выводов V = {vi| i = 1,2,...,n} подклю­чена некоторая схема S(рис. 9.4, а), размещенная внутри ячеек. Назовем концевые точки цепей, которыми они подсоединяются к выводам, терминалами. Пусть A∏ = (ai| i = 1,2,...,n}— ис­ходное множество подключенных к выводам терминалов, ai— номер терминала, подключенного к i-му выводу.

Назовем пере­становку элементов вектора A∏допустимой, если она получена путем соответствующего переназначения терминалов между эк­вивалентными выводами или эквивалентными группами выводов. Множество допустимых перестановок составляют пространство решений.

Рис. 9.4. а — схема с эквивалентными группами конструктивных элементов; б — дерево эквивалентности выводов и групп выводов

Задача перераспределения терминалов между выводами за­ключается в нахождении такой допустимой перестановки A*, при которой критерий имеет наилучшее значение [9.3, 9.9].

Пусть для схемы, представленной на рис. 9.4, а, экви­валентными являются группа конструктивных элементов (Kι, K2, Кз, К4), а также группа (K5, Kθ)• Для удобства каждый

i-й вывод Viбудем обозначать просто цифрой i, т. е. использовать цифровое обозначение выводов. Другими словами, обозначения 1,2,3,4,... ,11 соответствуют выводам V1, V2, V3, V4,..., v∏. Будем считать, что все входы конструктивных элементов эквивалентны.

На основе анализа функций схемы с помощью тривиального алгоритма строится дерево D(рис. 9.4, б) эквивалентности выво­дов и групп выводов. Вершины подножья дерева (листья дерева) соответствуют выводам множества V. Внутренние вершины со­ответствуют конструктивным элементам. В дереве имеется два типа вершин. Вершины типа ИЛИ (не заштрихованы) и вершины типа И (заштрихованы) [9.9].

Функцию от множества выводов, имеющих своим корнем Ki (реализуемую на выходе конструктивным элементом Ki), обозна­чим fi.Если для конструктивных элементов Kiи Kjфункции fi и fj∙ эквивалентны, то выходы этих конструктивных элементов функционально эквивалентны.

Если на входы конструктивного элемента подходят функцио­нально эквивалентные выходы, то такой конструктивный элемент моделируется вершиной типа ИЛИ. В противоположном случае конструктивный элемент моделируется вершиной типа И. Если на эквивалентные входы конструктивного элемента подходят вы­ходы, часть из которых эквивалентна, а часть нет, то конструк­тивный элемент условно в соответствии с ассоциативным зако­ном разбивается на подэлементы и моделируется двухуровневым подграфом, у которого дочерние вершины относятся к типу ИЛИ, а родительская — к типу И. Например, конструктивный элемент реализует функцию χ &£2 &£3 = (х1 &£2)&£з. К входам χ и Х2 подходят функционально эквивалентные выходы. Тогда кон­структивный элемент моделируется подграфом, показанным на рис. 9.5.

Рис. 9.5. Моделирование конструктивного элемента подграфом

Введем рекурсивное определение уровня для вершины дерева эквивалентности:

— вершины дерева D, соответствующие выводам (контактам), имеют нулевой уровень;

— уровень родительской вершины равен максимальному уров­ню среди дочерних вершин плюс единица.

Вершины Vij дерева D имеют следующую индексацию: i— соответствует номеру уровня, j— номеру вершины i-го уровня.

Установим соответствие gij = Γ(Vij) между вершинами Vj дерева D и группами выводов gij, имеющими своим корнем вершину Vij. Запись gij представляет собой вектор, в котором выводы записаны в виде иерархической структуры в порядке их расположения в линейке, ограничивающей канал. Для разли­чиявектор, соответствующей вершине типа И, будем обозначать чертой сверху: gij. В соответствии с иерархическим подходом gij = ⅛i| k < i, l = 1,2, ...nij), где gkiсоответствует дочерней вершине вершины Vij.

Если вершина Vij относится к типу И, то gij∙ = Γ(Vij) задает размещение неэквивалентных групп выводов друг относительно друга, соответствующих дочерним вершинам вершины Vj. Это размещение является фиксированным и не может быть изменено.

Если вершина Vj относится к типу "ИЛИ", то gij = Γ(Vj) задает размещение эквивалентных групп выводов друг отно­сительно друга, соответствующих дочерним вершинам вершины Vij. Это размещение не является фиксированным и может быть изменено.

Запишем все векторы gij в соответствии со структурой дерева D для приведенного выше примера (см. рис. 9.4):

Если убрать внутренние скобки (), то

В общем случае

Пусть имеется первоначальное подключение терминалов, за­даваемое вектором Aи = {αi| i = 1,2,...,n}, где αi— номер терминала, подключенного к i-му выводу.

Установим соответствие tij = Γ2(gij) между группой терми­налов tijи группой выводов gij, задающее подключение группы терминалов tijк группе выводов gij,

Соответствие между элементами tki∈tijи gki ∈gijопределя­ется порядком их размещения в векторах tijи gij. Другими сло­вами, если справедливо tij = Γ2(gij), то, во-первых, ]tij| = ∖gij|, а во-вторых, элемент gki∈gijи соответствующий ему элемент tki∈tijимеют один и тот же порядковый номер в векторах tij иgij.

Если tijсоответствует вершине Vijтипа ИЛИ, то группы тер­миналов tki∈tijможно переключить между соответствующими группами выводов gki ∈gij. В этом случае логическая функция схемы не изменяется.

Таким образом, конкретное решение задачи распределения соединений между выводами определяется порядком расположе­ния элементов в векторах tij, соответствующих вершинам типа ИЛИ. Любая перестановка элементов векторов tijприводит к но­вому решению.

П р и м е р. Пусть имеется список терминалов A1 = = (4,5,5,6,6,3,2, 1,2,3, 1) для верхнего ряда выводов и

A2 = (1,0,2,3,0,4,0,5,0,0,6) для нижнего ряда выводов. Значениями элементов векторов A1 и A2 являются номера цепей A1U A2= A.

Список Ai подключен к схеме, изображенной на рис. 9.4, а. Нижний ряд выводов имеет фиксированную коммутацию с тер­миналами списка A2. На рис. 9.6, а показана трассировка в соот­ветствии со списками A1и A2.

Векторы терминалов tijна основе списка A1 и соответствую­щих векторов gijдля схемы на рис. 9.6 имеют следующий вид: tιι = (4,5); t12 = (5,6); t13 = (2,1); t14 = (3,1);

t21 = (tιι, t12); t22 = (ti3, t14); t31 = (t21,6); t32 = (t22,2); t4i =

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Переключение соединений в канале:

  1. Передача данных по коммуникационной сети
  2. Испытательный стенд
  3. 4.2. ПРИМЕРЫ ОПТИМИЗАЦИИ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  4. Способы измерений и порядок проведения испытаний
  5. Синтаксический рисунок художественного и научного текста
  6. Ввод изображения оптико-электронным датчиком
  7. 2.2 Фильтрация изображения
  8. 3. Порядок издания и отмены актов государственного управления
  9. 3. Синергетический подход к управлению
  10. ГЛАВА 3. ЭКСПЕРИМЕНТАЛЬНО-ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ РАЗРАБОТАННЫХ АЛГОРИТМОВ РАСЧЕТА ПЛИТ
  11. 2.4 Сегментация и построение контуров изображений объектов
  12. СУБЪЕКТЫ АДМИНИСТРАТИВНОГО ПРАВА
  13. 1. Содержание (функции) государственного управления
  14. Тема 16. Производство по делам об административных правонарушениях
  15. 3.1. Формирование стратегии развития системы персональных финансов
  16. ГЛОССАРИЙ
  17. Анализ содержания учебного материала школьных учебников с позиции их ориентации на достижение личностных результатов обучения
  18. Введение
  19. Глава I. ОПТИЧЕСКИЕ АНОМАЛИИ В КРИСТАЛЛАХ.
  20. 2. Права и обязанности сторон по договору купли-продажи.