Синтез логических схем

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

Логические элементы именуются в соответствии с реализуемыми функциями. Для реализации отрицания используется инвертор (элемент НЕ), для реализации конъюнкции — конъюнктор (элемент И), для реализации дизъюнкции — дизъюнктор (элемент ИЛИ), для реализации операции Шеффера — элемент Шеффера (элемент И—НЕ), для реализации операции Пирса — элемент Пирса (элемент ИЛИ—НЕ).

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

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

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

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

Итак

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

Пусть имеется Д. Н. Ф. . Рассмотрим таблицу ис­тинности для функции при различных значениях :

Операция	Значения функции

Отсюда видно, что значение истинности Д. Н. Ф. не зависит от значения , а тогда .

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

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

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

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

• Построение логической схемы по минимизированным логическим функциям.

При проведении работ по синтезу логических схем могут выполняться не все действия из указанных, или же логические функции, описывающие рассматриваемый узел заданы. Если же логические функции не минимизируются, то преобразования проводят с целью получения их форм, удобных для реализации с помощью логических элементов заданного набора. Следует заметить, что при синтезе схем, описывающих работу какого-либо узла компьютера, чаще используют элементарные конъюнкции и, соответственно, С. Д. Н. Ф. в силу того, что в этом случае удобнее проводить необ­ходимые преобразования. В этом случае обычно стараются выявить так называемые «соседние» [4] конъюнкции, т.е. элементарные конъюнкции одного ранга состоящие из одних и тех же логических переменных и от­личающихся инвертированием только одной переменной, т.е. если в неко­торую конъюнкцию входит переменная , то в «соседнюю» входит На­пример, конъюнкции и являются «сосед­ними».

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

Так как работа некоторого узла компьютера задается таблицей ис­тинности, сформулируем правила, по которым производится построение дизъюнктивных и конъюнктивных нормальных форм [4]:

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

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

Теперь мы можем приступить к примерам реализации схем. В пер­вом примере рассматривается устройство, имеющее входов и один выход. Та­кие устройства носят название мультиплексоров. Работа простейшего мультиплексора на три входа задана таблицей истинности [4]:

Согласно правилу, приведенному выше, выпишем элементарные конъ­юнкции³:

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

выделим соседние конъюнкции и добавим «лишнюю» конъюнкцию

проведем группировку

после проведения «склейки», получаем

.

При реализации последней схемы требуется уже два инвертора, две схемы ИЛИ и два элемента И, т. е. всего шесть элементов. Если же использовать закон инверсии для дизъюнкции, то Для последнего варианта потребу­ется три схемы ИЛИ, одна НЕ и одна И, т. е. пять элементов. Блок-схема устройства имеет вид

Счетчики

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

t

t

t

t

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

t

t

t

t

Реверсивный счетчик может считать как с увеличением, так с уменьшением кода, в зависимости от ого будут ли поданы импульсы на вход суммирования «+» или на вход вычитания «–».

Эти простейшие счетчики реализованы на T-триггерах. В них все подлежащие переключению триггеры изменяют свое состояние не одновременно, а последовательно друг за другом. Например, если все три триггера счетчика на рис. 20 находятся в единице, то очередной входной импульс опрокинет первый триггер. Изменение уровня на выходе первого триггера опрокинет второй триггер, выходной сигнал которого, заставит опрокинуться третий. Поэтому счетчики, построенные по такому принципу, называются асинхронными.

Недостатком асинхронных счетчиков является задержка в установлении соответствующего кода после прихода счетного импульса. Кроме того, при переходе от одного кода к другому счетчик на короткое время принимает промежуточные состояния. Например, рассмотрим работу суммирующего счетчика, начиная с состояния 011 (цифра слева соответствует старшему триггеру, находящемуся на рис. 19 справа). Тогда, при приходе счетного импульса код в данном счетчике будет меняться следующим образом: 011 – 010 – 000 – 100. В данном случае переходной процесс от кода 011 к коду 100 содержит два промежуточных состояния 010 и 000. В случае если к выходам счетчика подключены другие устройства, например дешифратор параллельного кода, эти промежуточные состояния вызовут ложные срабатывания этих устройств.

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

Рассмотрим работу счетчика со сквозным переносом. Первый и второй триггер находятся в 1, поэтому на выходах соответствующих им схем И из тактовых импульсов сформируются еще до их опрокидывания сигналы переноса. Эти сигнал переноса с первой схемы И опрокинет второй триггер, а сигнал переноса со второй, схемы И опрокинет третий триггер, первый триггер опрокинется непосредственно от тактового сигнала. Таким образом, переход счетчика от состояния 011 в состояние 100 про­изойдет без промежуточных состояний практически синхронно с задним фронтом тактового импульса. На самом деле триггеры срабатывают не совсем синхронно из-за задержек вносимых схемами И, но эта несинхронность на порядок ниже чем у асинхронных счетчиков.

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

Пример десятичного счетчика приведен на рис. 26. В этом счетчике запрещены состояния, начиная с 1010 и кончая состоянием 1111. Таким образом, после состояния 1001 (код цифры 9 десятичной системы) следует состояние 0000 (код цифры 0). Этот счетчик работает в так называемом двоично-десятичном коде.

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

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

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

Дешифраторы и шифраторы

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

X2	X1	X0	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7
0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0	0	0	0
0	1	0	0	0	1	0	0	0	0	0
0	1	1	0	0	0	1	0	0	0	0
1	0	0	0	0	0	0	1	0	0	0
1	0	1	0	0	0	0	0	1	0	0
1	1	0	0	0	0	0	0	0	1	0
1	1	1	0	0	0	0	0	0	0	1

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

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

X0	X1	X2	X3	X4	X5	X6	X7	Y0	Y1	Y2
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	1	0	0
0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	1	1	0
0	0	0	0	1	0	0	0	0	0	1
0	0	0	0	0	1	0	0	1	0	1
0	0	0	0	0	0	1	0	0	1	1
0	0	0	0	0	0	0	1	1	1	1

Реализация такого шифратора приведена на рис. 29.

Сумматоры

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

0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

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

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

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

0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

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

, .

Заметим, что эти логические функции можно реализовывать на различных логических элементах.