Топологические ограничения в схемах

 

В работах Э.Поста определена структура замкнутых по операции суперпозиции классов в множестве функций алгебры логики, описаны предполные классы  в классе всех булевых функций, обозначенном Постом как  С, и, как следствие, требования к порождающим множествам класса С - условия функциональной полноты.

Суперпозиции можно сопоставить логическую схему, элементы которой реализуют функции порождающего множества. При этом рассматривались схемы, в которых никаких ограничений на суперпозиции (следовательно, и на структуры схем) не накладывались.  

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

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

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

Плоские схемы - схемы располагаются таким образом, что связи между ними нигде не пересекались. Здесь может быть добавлена возможность иметь в каждой схеме доступ к ее входным и выходным полюсам, то есть эти полюса могут располагаться только на периферии. Кроме того, можно потребовать, чтобы расположение этих полюсов по периферии было зафиксировано без повторений.

Однородные структуры - схема “вкладывается “ через настройку элементов в структуру, состоящую из однотипных элементов, одинаковым образом связанных между собой. Могут быть добавлены требования доступа к полюсам с периферии и возможности периферийной настройки.

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

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

 

 

Плоские схемы

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

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

Аналогичную схему можно построить и в классическом базисе {x&y, xÚy, `x}. Она имеет 5 элементов.

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

· построим схему для заданных функций;

· расположим её на плоскости таким образом, чтобы в схеме число пересечений было минимальным;

· заменим каждое пересечение схемой Тоника, после чего каждый из элементов схемы Тоника заменим схемой в заданном базисе.

Легко видеть, что число элементов в схеме при этом увеличится на произведение числа пересечений на число элементов в реализации каждого пересечения.

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

Второй способ состоит в том, что предлагается сразу искать схему, которая допускает хорошую (а лучше плоскую) укладку.

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

⇐ Предыдущая567891011121314Следующая ⇒

Поделиться: