arx011010_ch2

1.8. Преобразованиеиминимизациялогическихвыражений

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

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

Возможность представления любой логической функции в ДСНФ или КСНФ означает, что логические функции конъюнкции, дизъюнкции и отрицания (И, ИЛИ, НЕ) образуютфункциональнополнуюсистему или основной базис.

Базис И, ИЛИ, НЕ является избыточным, так как из него всегда можно исклчить, используяформулудеМоргана, либофункциюИ, заменяяеенаИЛИиНЕ:

x & у = xV y ,

либофункциюИЛИ, заменяяеенаИиНЕ:

x V у = x & y

БазисыфункцииИ, НЕиИЛИ, НЕназываютсянормальнымибазисами. При удалении из них хотя бы одной функции функционально полная система становитсянеполной.

Функциональной полнотой обладают также системы, состоящие из одной

логической функции: отрицания конъюнкции x & y (И-НЕ), названнойоперацией

Шеффера, или отрицания дизъюнкции xVy (ИЛИ-НЕ), названной операцией

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

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

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

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

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

20

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

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

1.9. Элементы и узлы компьютерной схемотехники

ОперационныеблокиЭВМ, преобразующиедвоичнуюинформацию, можнов общемвидепредставитьввидемногополюсникасn входамииm выходами. На его входы поступают входные двоичные сигналы хi (i=1, 2, ..., n), а с выходов снимаются выходные сигналы уj (j= 1, 2,..., m). В любой момент времени наборы этих сигналов образуют соответственно входное слово X (х1, х2,... хn) и выходноесловоY (у1, у2,..., ут).

Необходимое преобразование данных в операционных блоках ЭВМ производится логическими устройствами двух типов: комбинационными схемами

ицифровымиавтоматамиспамятью.

Вкомбинационной схеме (КС) набор выходных сигналов (выходное слово Y) в любой момент времени полностью определяется набором входных сигналов (входнымсловомX), поступающихвтотжемоментвремени(рис. 6.5.1).

Рис. 1. Структура комбинационной схемы.

Результат обработки данных в комбинационной схеме зависит только от комбинации входных сигналов и формируется одновременно с их поступлением. Эта зависимость может быть задана в виде соответствующей таблицы, а также с использованием аналитических форм представления логических функций (например, ДСНФ или КСНФ). Техническая реализация комбинационных схем осуществляется с использованием логических элементов, каждый из которых воспроизводит ту или иную логическую функцию двоичных переменных. Набор таких элементов должен обеспечивать реализацию функционально полной

21

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

В цифровых автоматах с памятью набор выходных сигналов Y (у1,

у2,... уn) зависит не только от набора входных сигналов X (х1, х2,... хn), но и от внутреннего состояния Q(q1, q2,... qk) данного устройства (рис. 6.5.2).

Рис.2. Структура цифрового автомата с памятью.

Такие устройства всегда имеют память, которая фиксирует их внутренние состояния. Наборы двоичных переменных X, Y и Q, называемые соответственно входным, выходным и внутренним алфавитами, полностью отражают процесс функционирования автомата. Фиксация и изменения этих алфавитов обычно происходят в определенной тактовой последовательности t = 0,1,2,... . В такой же последовательности задаются в виде таблицы или в

аналитической форме функции переходов и выходов: Qt =ϕ(Qt , X t )	и
Yt =ψ(Qt , X t ) , которые определяют соответственно состояние автомата Qt +1	и

выходное слово Yt , в зависимости от состояния Qt , и входного слова X t . При этом указывается начальное состояние автомата Q0 .

Автомат, для которого выходное слово Yt в такте t зависит только от состояния автомата Qt , называется автоматом Мура. Для него функция выходов имеет вид Yt =ψ(Qt ) .

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

триггером.

1.10. Общая характеристика элементов и узлов ЭВМ

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

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

Узлы ЭВМ осуществляют одновременную обработку сигналов, представляющих многоразрядные машинные слова. К их числу относятся, например, регистры, счетчики, сумматоры, дешифраторы и др.

22

Устройства ЭВМ (запоминающие, управляющие, обрабатывающие, ввода-вывода и др.) обеспечивают в соответствии с заданной программой выполнение требуемой последовательности машинных операций.

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

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

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

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

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

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

например, низкому уровню Un соответствует 0, а высокому Un − 1 (рис. 6.5.3.). Разность между этими уровнями называется логическим перепадом

UЛ.

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

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

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

23

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

Рис. 6.5.3. Потенциальный способ представления двоичной информации Потребляемая мощность определяет требования, предъявляемые к

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

Помехоустойчивость элементов рассматривается как в статическом, так

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

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

быстродействующих ЭВМ он составляет десятки и даже единицы наносекунды (10-8 - 10-9 с). Кратковременный и прерывистый характер воздействия сигналов на схемы элементов вызывает в них переходные процессы, при которых изменение логического состояния происходит не мгновенно (как на рис. 6.5.3.), а в течение времени формирования переднего

изаднего фронтов выходного сигнала. Передний фронт tф(0,1) формируется

24

при переходе элемента из состояния «0» в состояние «1», а задний фронт tф(1,0) – при переходе из «1» в «0».

Из-за наличия фронтов у сигналов, поступающих на вход элемента, его срабатывание всегда происходит с определенной задержкой как на переднем tзд(0,1), так и на заднем tзд(1,0) фронте.

Максимальная рабочая частота элемента зависит от длительности фронтов и задержки переключения. Обычно временной интервал Т между соседними переключениями выбирается в 10-20 раз больше, чем tф и tзд. Это обеспечивает полное затухание всех переходных процессов в элементе к приходу следующего сигнала переключения. В современных элементах ЭВМ предельная рабочая частота f = 1 /Т достигает сотен мегагерц.

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

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

Дадим общую характеристику логическим и запоминающим элементам ЭВМ.

1.11. Логические элементы

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

Втаблице 3 приведены условные обозначения типовых элементов и реализуемые ими логические функции.

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

Таблица 3. Условные обозначения типовых логических элементов

Назначение элементов	Условное обозначение	Название и
		логическая запись

25

		функции
И		Конъюнкция
		y = x1 & x2
		y = x1 x2
ИЛИ		Дизъюнкция
		y = x1Vx2
		y = x1 + x2
НЕ		Инверсия
		y =
							x
ИЛИ-НЕ		Стрелка Пирса
		y =
					x1Vx2
И-НЕ		Штрих Шеффера
		y =
				x1 & x2
		Импликация от x к y
						Vx2
Импликация			x1
		Сложение по модулю 2
MOD 2		x y

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

26

числевосновномбазисе(элементыИ, ИЛИ, НЕ), нормальныхбазисах(элементыИ, НЕилиИЛИ, НЕ) иуниверсальныхбазисах(элементыИ-НЕИЛИИЛИ-НЕ).

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

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

На рис. 6.7. приведены комбинационные схемы, реализующие функцию И на элементахИЛИ, НЕ, атакжефункциюИЛИнаэлементахИ, НЕ.

ВосновеэтихсхемлежитформуладеМоргана, согласнокоторой:

x1 & x2 = x1V x2 ;

x1Vx2 = x1 & x2 .

a)

b)

Рис. 6.7. Комбинационные схемы, реализующие:

a) функцию И на элементах ИЛИ, НЕ, b) функцию ИЛИ на элементах И, НЕ.

Если требуется реализовать в универсальном базисе И-НЕ произвольную логическуюфункцию, тонеобходимовыполнитьследующуюпоследовательность действий:

•записать заданную функцию в ДСНФ и минимизировать ее в базисе И,ИЛИ,НЕ;

•над полученным выражением поставить двойное отрицание;

27

•осуществить переход в универсальный базис И-НЕ, используя при этом выражения:

x1V x2 = x1 & x2 ; x1 & x2 = x1 & x1 & x2 ;

(x1 & x2 )V (x1 & x2 ) =[x1 & (x1 & x2 )(x1 & x2 & x2 ] ; x1 = x1 &1; x1 = x1 & x1 .

2. Базовые функциональные элементы ЭВМ. Двоичные логические элементы

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

Пример физической реализации логического элемента.

Рис. 1. Реализация логического элемента на мех. переключателях (ключах). Рисунок 1 иллюстрирует принцип работы логического элемента “И”. Вопрос: Что требуется сделать, чтоб на выходе заставить лампу засветить? Чтобы это произошло мы должны замкнуть оба ключа А и B. Разные варианты положения ключей можно свести в таблицу (Рис.1).

Стандартное обозначение “условное”, независимо от того на чем собран логический элемент, позволяет составлять несколько элементов в схему.

Рис. 2. Условное обозначение “символ” логического элемента “И”.

Термин логический обычно применяют по отношению к процедуре принятия решения. В таком случае можно сказать, что логический элемент – это такая схема, которая основываясь на входных сигналах, может “решить”, что ей ответить на выходе – да (1) или нет (0).

28

На рисунке 3 схема логического элемента отвечает, да, только в том случае, когда на оба ее входа поданы сигналы – да (оба ключа замкнуты).

Мы применим в нашем случае, так называемую положительную логику, поскольку для получения двоичной единицы используют положительное напряжение 5 В. Получим таблицу, которая носит названия таблицей истинности, по аналогии с булевой алгеброй. В этой таблице для логического элемента “И” указаны все возможные комбинации сигналов на входах A и B и соответственно сигналы на выходе.

Булевы выражения – это универсальный язык для построения цифровых электрических схем.

Пример винтеля «и», который реализует логическую операцию конъюнкции.

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

Последовательные логические схемы

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

Основное свойство последовательных логических схем:

Значение на выходах таких схем в определенный момент времени является функциями от некоторых значений на входах. В этот же момент времени и за некоторое конечное число предыдущих моментов времени.

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

Схемы срабатывают в определенный момент (дискретные) времени.

29