4-7. ПОРОГОВАЯ И МАЖОРИТАРНАЯ ЛОГИКА

Рассмотрим некоторые теоретические вопросы, возникающие при синтезе схем из пороговых и мажоритарных элементов.

Определение 4-1. Пороговым элементом называется элемент с входами и одним выходом, поведение которого описывается соотношением

где у — значение сигнала на выходе элемента; -значение сигнала на входе; — порог; — вес входа;

Без ограничения общности можно полагать, что и — целые неотрицательные числа.

Определение 4-2. Совокупность весов входов и порога называется структурой порогового элемента.

В векторном виде соотношение (4-14) можно записать как

где

Определение 4-3. Булева функция называется пороговой, если существуют такие что ее можно представить в виде

Таким образом, пороговые функции — это такие функции, которые могут быть реализованы на одном пороговом элементе.

Возникает вопрос о мощности класса пороговых функций. Если через обозначить число ФАЛ от аргументов, которые являются пороговыми, то имеет место следующая оценка:

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

где которая хотя и является монотонной, но не является пороговой.

Для проблема остается нерешенной.

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

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

Рассмотрим сначала первую задачу. Пусть Т — множество наборов значений переменных, на которых

функция равна 1, а множество наборов значений переменных, на которых функция равна 0. Рассмотрим систему линейных неравенств:

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

Таким образом, для того чтобы синтезировать пороговый элемент, нужно установить, имеет ли система (4-16) решение, и если имеет, то найти его. Это может быть выполнено путем использования методов линейного программирования, однако в случае большого решение системы (4-16) может оказаться весьма сложной задачей, особенно в связи с требованием целочисленности . Поэтому, как правило, применяют методы синтеза, не связанные с линейным программированием.

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

Пусть соотношение означает, что на любом наборе значение функции не меньше значения функции а соотношение означает, что, кроме того, обязательно найдется хотя бы один такой набор,

на котором значение функции больше значения функции Если для некоторой функции выполняется

то будем говорить, что тяжелее чем и обозначать это как Если левую и правую части соотношения связывает знак равенства, то будем говорить, что равновесны, и обозначать Заметим, что равновесность означает, что функция симметрична относительно и Если функция пороговая, то все ее аргументы можно упорядочить по тяжести. Обратное утверждение справедливо лишь для функций менее чем шести переменных. Если данная функция пороговая, то из следует, что а из следует, что Упорядочив веса всех входов, можно произвести подбор значений удовлетворяющих (4-14), задаваясь значением

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

Отсюда можно установить соотношение между суммами некоторых Заметим, что из равенство соответствующих сумм следует лишь для

Пример 4-11. Реализовать на одном пороговом элементе функцию

1. Устанавливаем соотношения тяжести между аргументами

Так как

(кликните для просмотра скана)

Второй метод синтеза порогового элемента основан на минимизации некоторого функционала.

Запишем систему (4-16) линейных неравенств в виде

Рассмотрим выражения

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

Очевидно, что При этом, функционал равен нулю лишь в том случае, когда все и удовлетворяют системе линейных неравенств (4-16). Таким образом, задача синтеза порогового элемента в этом случае сводится к минимизации функционала Сначала описанным выше способом производится упорядочение значений Затем задаемся величинами , удовлетворяющими произведенному упорядочению, и такими, что минимальна. Вычисляем значение функционала. Если оно не равно нулю,

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

Рис. 4-35.

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

В настоящее время методы синтеза сетей произвольной конфигурации из пороговых элементов еще не разработаны. Однако для некоторых частных видов сетей такие методы существуют. Мы рассмотрим здесь один метод синтеза сетей глубины два. Сеть глубины два из пороговых элементов показана на рис. 4-35. Работа такой сети описывается уравнением

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

где - функция, реализуемая пороговым элементом входного уровня.

Очевидно, что задача синтеза такой сети сводится к разбиению исходной функции на пороговые подфункции, дизъюнкции которых дают исходную функцию.

Пример 4-12. Требуется построить сеть вида, показанного на рис. 4-36, реализующую функцию, заданную следующей таблицей:

Дизъюнктивная нормальная форма этой функции имеет вид:

Эта функция не пороговая, так как она не монотонна

Находим сокращенную дизъюнктивную нормальную форму функции

Разбиваем функцию на две подфункции

где

и

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

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

Полученная сеть представлена на рис. 4-36.

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

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

Мы будем рассматривать мажоритарные элементы с нечетным числом входов. Если порог такого элемента

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

Рис. 4-36.

Логику таких элементов впервые начали изучать С. Мурога, Р. Уиджингтон и Р. Линдеман. Они же ввели в рассмотрение специальный оператор Собственная функция

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

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

Линдеманом и Коном была предложена каноническая форма представления функций алгебры логики в случае использования для ее реализации трехвходовых мажоритарных элементов, работающих по принципу большинства. (В дальнейшем мы будем рассматривать только такие элементы и называть их просто мажоритарными элементами.) Работа такого элемента может быть описана с помощью следующей собственной функции:

Операция, которую осуществляет элемент, записывается как

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

Функциональная полнота мажоритарной операции совместно с инверсией и одной из констант 1 или 0 была показана еще Дж. фон Нейманом.

В работе Линдемана и Кона указан ряд очевидных эквивалентных преобразований в мажоритарном базисе:

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

следующим образом:

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

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

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

Теорема 4-1. Всякая функция алгебры логики может быть представлена через любые два свои аргумента и остаточные функции по подстановке и по подстановке одним из следующих способов:

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

концов получим представление функции только через ее аргументы и константы.

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

Собственная функция рассматриваемого устройства имеет вид:

Используем первое разложение из теоремы

На рис. 4-37 показана соответствующая функциональная схема.

Рис. 4-37.

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

Тогда согласно (4-22) получим

Исключая еще одну переменную получим:

Учитывая преобразование

получим:

Сложность сетей, получаемых при синтезе методом последовательного исключения переменных, как правило, существенно зависит от порядка, в котором исключаются переменные. Эвристический метод нахождения нан-лучшего порядка исключения переменных предложен В. И. Варшавским и Л. Я. Розенблюмом. Суть этого метода состоит в следующем. Используется понятие производной булевой функции, введенное нами в § 2-8,

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

Пример 4-14. Реализовать функцию

на мажоритарных элементах.

Используем разложение типа (4-25). Предварительно устанавливаем, какие переменные следует исключать в первую очередь:

Функция имеет следующую таблицу истинности:

Из этой таблицы видно, что

Точно таким же способом устанавливаем, что

Этого и следовало ожидать, так как данная функция симметрична относительно переменных Далее находим, что

Таким образом, наибольший вес имеет производная данной функции по переменной Производим исключение переменной Остаточные функции но подстановке фиксированных значений имеют вид:

В соответствии с (4-23)

В соответствии с (4-20)

Окончательно получаем следующее выражение, описывающее данную функцию:

Схема реализации данной функции представлена на рис. 4-38.

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

причем

В случае синтеза схем в мажоритарном базисе удобно выбирать функцию соответствующей мажоритарной

операции, т. е. представлять исходную функцию в виде

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

Рис. 4-38.

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

Естественно, что подбор удовлетворяющий наложенным на них ограничениям, не всегда возможен. Выражение (4-26) можно рассматривать как уравнение, где неизвестными являются функции Развернув это уравнение по всем наборам значений переменных получим систему уравнений, где неизвестными являются значения функций на соответствующих наборах и, следовательно, неизвестные могут принимать лишь два значения — 0 и 1:

где соответственно значения функций на наборе аргументов

Для того чтобы функция допускала представление в виде (4-26), необходимо и достаточно, чтобы система (4-27) имела решение. Это решение определяет функции Суть метода решения систем логических уравнений в мажоритарном базисе состоит в том, что в пространстве неизвестных систем (4-27) строится вспомогательная функция Эта функция строится следующим образом.

Введем сквозную нумерацию для неизвестных системы (4-27), т. е. обозначим: и т.д. Пусть система (4-27) имеет неизвестных (очевидно, что ). В этом случае система (4-27) будет иметь вид:

Рассмотрим -мерных векторов таких, что

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

Таким образом, для решения системы (4-27) достаточно построить описанным образом функцию . Установив далее, что она пороговая, найти веса переменных, имея в виду, что порог равен 2, а веса могут принимать лишь значения 0 и 1. Для этого можно воспользоваться, например, методом минимизации функционала, описанным в этой книге. Несмотря на то что размерность функции очень велика, использование этого метода достаточно просто, так как функция определена на очень небольшой части наборов (из общего числа

Пример 4-15. Реализовать из мажоритарных элементов функцию

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

Находим функции Система логических уравнений имеет вид:

Таблица истинности функции имеет вид:

(см. скан)

В таблице указаны лишь те наборы, на которых функция определена. Построив функционал вида (4-17) и минимизировав его, убеждаемся, что он принимает нулевое значение при

Тогда имеем следующие таблицы истинности для

Рис. 4-39.

Отсюда легко видеть, что

Схема, реализующая данную функцию представлена на рис. 4-39.