Теория переключательных цепей - техническая дисциплина, изучающая задачи проектирования цифровых устройств на основе адекватного математического аппарата. При этом характер возникающих задач и выбор соответствующего математического аппарата определяются используемой технологией. Первой работой, посвященной общей теории переключательных цепей, считается классическая работа Шеннона, опубликованная в 1938 г. С тех пор технология реализации переключательных цепей прошла ряд этапов развития. Для реализации переключательных цепей последовательно использовались релейно-контакт-ные элементы, диодные логические элементы, транзисторные логические элементы, интегральные схемы и т. д. В будущем можно предвидеть использование элементов с цилиндрическими магнитными доменами (ЦМД) и приборов с зарядовой связью (ПЗС):

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

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

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

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

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

Принципиально новый материал, отличающий эту книгу от известных книг по теории переключений, содержится в гл. 4-8. Глава 4 дает общее представление о проектировании асинхронных цепей. Главы 5 и 6 содержат материал по проектированию структурно простых цепей, по декомпозиции последовательностных цепей, включая каноническую декомпозицию Крона - Роудза, по универсальным логическим модулям и итеративным матрицам - предметам, имеющим, по нашему убеждению, особенно важное значение для разработки новых технологий. В этих главах излагаются некоторые абстрактные математические методы, которые, однако, здесь представлены в форме, не требующей знания теории групп. В гл. 7 рассматривается ряд важных проблем компоновки цифровых цепей, имеющих особое значение для технологии изготовления БИС. Глава 8 иллюстри-

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

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

Часть материала, содержащегося в этой книге, была использована в курсах университета Южной Калифорнии и Иллиной-ского технологического института. Мы выражаем признательность студентам, постоянный контакт с которыми способствовал улучшению изложения материала. Нам хотелось бы также поблагодарить Отто Бёленса, Германа Гуммела и Джона Хайеса за замечания и предложения по различным частям рукописи, а Ричарда Стребендта за разработку машинной программы, которая упростила задачу составления указателя. Наконец, мы благодарны компании Bell Telephone Laboratories за предоставленную нам возможность воспользоваться ее техническими средствами при подготовке рукописи.

А. Д. Фридман П. Р. Менон

Часть 1

Классические

переключений

Глава 1 ОСНОВНЫЕ ПОЛОЖЕНИЯ

1.1. ВВЕДЕНИЕ

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

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

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

результаты теоретических исследований являются основой для практического проектирования (синтеза) цифровых цепей.

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

НЕ (инеертвр)

НЕ-И

Рис. 1.1. Основные логические элементы.

комбинации состояний входа. Некоторые основные типы логических элементов иа два входа с таблицами, описывающими их работу, приведены на рис. 1.1). Результаты, полученные при рассмотрении логических элементов с двумя входами, могут быть обобщены на логические элементы, имеющие п входов. Например, состояние выхода логического элемента И на п входов будет равно 1, если состояние всех его входов равно 1.

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

1.2. БУЛЕВА АЛГЕБРА

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

1.2.1. ОСНОВНЫЕ ПОСТУЛАТЫ

Булева алгебра определяется в терминах конечного множества') К, двух двоичных операций: логического сложения ( + , ИЛИ) и логического умножения { И) и ряда основных постулатов. Знак равенства ( = ) означает, что выражения, стоящие слева и справа от него, равны. Для группирования выражений по обе стороны от знака равенства служат круглые скобки. При отсутствии скобок операция логического умножения выполняется раньше операции логического сложения 2).

Ниже приводятся основные постулаты булевой алгебры, впервые сформулированные Хантингтоном [8], который, кроме того, доказал их совместимость.

1. Для всех X, К

(а) х-\-у^К,

(б) х.у^К.

2. (а) Для всех х^К существует элемент О е/С, такой, что х + О = X.

(б) Для всех х^К существует элемент 1 s К, такой, что х-1 - X.

3. Коммутативность: для всех х, у К

(а) X+ = +X,

(б) х-у=у-х.

4. Дистрибутивность: для всех х, у, К

(а) x + iy.z) = ix + y).(x + z),

(б) x-{y + z) = x-y + x-z.

5. Для каждого х^К существует элемент х е /С (называемый дополнением х), такой, что (а) х--х = 1 и (б) х-х = 0.

6. Существуют по крайней мере два элемента х, у К, такие, что Хфу.

1.2.2. СВОЙСТВА

Некоторые свойства булевой алгебры могут быть получены непосредственно с помощью сформулированных выше

) Основные определения теории множеств и обозначения даны в приложении.

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

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

Ниже приводятся основные леммы и теоремы булевой алгебры, которые выводятся исходя из основных постулатов и принципа замещения, сформулированного следующим образом: если две величины равны, то одна из них может быть замещена другой. Доказательство этих лемм и теорем упрощается при использовании свойства дуальности, заключающегося в том, что если какое-либо свойство булевой алгебры может быть доказано с помощью определенного постулата, то дуальное свойство доказывается тем же способом с помощью дуального постулата. Таким образом, достаточно доказать лишь одну часть каждой из нижеследующих лемм и теорем, доказательство второй части будет следовать непосредственно из свойства дуальности. Доказательства нижеследующих теорем и лемм могут быть найдены в [4, 6].

Лемма 1.1. (а) Элемент О единственный.

(б) Элемент 1 единственный. Лемма 1.2. (Идемпотентность.) Для всех К

(а) х + х = х,

(б) х-х = х. Лемма 1.3. Для каждого х^К

(а) х+1 = 1,

(б) х-0 = 0.

Лемма 1.4. (а) 0=1, (б) 1=0.

Лемма 1.5. Для каждого х^ К х - единственный. Лемма 1.6. (Поглощение.) Для всех х, у^К

(а) х + х-у = х,

(б) х-{х + у) = х.

Лемма 1.7. Для всех х, у К если х-у = у и х + у = у,

то х = у.

Лемма 1.8. Для каждого х^ К х - х. Теорема 1.1. (Ассоциативность.) Для всех х, у, zK

(а) x + {y + z) = ix + y) + z.

(б) x-{yz) = {x-y)-z.

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

Рис. 1.2. Таблица для доказательства теоремы 1.2 б.

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

1.2.3. БУЛЕВЫ ФУНКЦИИ И ВЫРАЖЕНИЯ

Рассмотрим п-вектор-строку x = (>;i, х2, Хп), ХгК, 1 t п. Булевой функцией / (х) называется отображение из х в К, полностью определенное элементом у К, соответствующим каждой п-вектор-строке. Булева функция может быть также определена как булево выражение, получаемое из булевых переменных Xi, Xz, .... Хп путем их логического сложения,

умножения и взятия дополнений Хи Хг,

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

) Рекурсивно булево выражение может быть определено следующим образом: 1) Xi и Xi - булевы выражения; 2) если Е\ и £2 - булевы выражения, Тогда El -{- £2. Е1-Е2, El и Ei - булевы выражения.

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

Теорема 1.2. (Законы Де Моргана.) Для всех х, у^К,

(а) х + у=-х-у,

(б) х-у = х + у.

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

всех переменных и взаимной замены логических операций

сложения и умножения из булевого выражения функции f можно получить булево выражение дуальной функции /й, которая определяется как /(xi, Xz, Xn) = f{xi, хг, Хп).

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

1.2.4. ПРИМЕНЕНИЕ К ПЕРЕКЛЮЧАТЕЛЬНЫМ ЦЕПЯМ

Двузначная булева алгебра (/< = {О, 1}) удобна для описания цифровых цепей. При этом сигнал на любом проводе цепи представляется булевой переменной, принимающей одно из двух значений (О или 1), а поведение различных типов логических элементов, показанных на рис. 1.1, описывается булевыми выражениями. Так как цифровые цепи являются комбинацией этих логических элементов, то булева алгебра может служить математическим аппаратом для анализа их поведения.

Если представить входы логических элементов на два входа (рис. 1.1) булевыми переменными Xi и лгг, а выходы - булевой переменной z, то логический элемент И описывается булевым выражением z = Х\-Х2, логический элемент ИЛИ -выражением z - Xi-\-X2, логический элемент И-НЕ - выражением z-xiX2=

- х\-\-Х2, а логический элемент ИЛИ-НЕ - выражением z =

- Xi-\-Х2 = Х\Х2. Заметим, что два последних логических элемента ведут себя так же, как логические элементы И и ИЛИ, выходы которых представлены не входными переменными, а их-дополнениями.

Анализ схем на рис. 1.1 показывает, что перемена местами входов любого логического элемента, имеющего два входа, не влияет на его выход. Благодаря свойству коммутативности операций логического умножения и сложения значения булевых функций, описывающих работу логических элементов, также не меняются при изменении порядка входных переменных. Поведение логических элементов И, ИЛИ, И-НЕ и ИЛИ-НЕ с несколькими входами также не зависит от расположения или порядка группирования входов и, следовательно, может быть описано соответствующими булевыми выражениями. Например, выражения Д = XiX2Xz, h = \ + 2 + Хз, fs = Х1Х2Х3 = Xi+X2 + X3 И

f4~Xi~\-X2 + X3 - Х1Х2Х3 представляют соответственно логические элементы И, ИЛИ, И-НЕ и ИЛИ-НЕ с тремя входами Xi,

Х2 и Хз.

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