Xreferat.com » Рефераты по коммуникации и связи » Компьютерная схемотехника

Компьютерная схемотехника

Содержание


1. ВВЕДЕНИЕ

2. ДИСКРЕТИЗАЦИЯ АНАЛОГОВЫХ СИГНАЛОВ

2.1 Квантование по уровню

2.2 Квантование по времени

2.3 Квантование по уровню и по времени

2.3.1 Расчет погрешности АЦП

2.3.2 Выбор величины шага квантования по времени

3. ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ (БУЛЕВОЙ АЛГЕБРЫ) ПРИ АНАЛИЗЕ И СИНТЕЗЕ ЦИФРОВЫХ ЭЛЕКТРОННЫХ УСТРОЙСТВ

3.1 Определение и способы задания переключательных функций

3.2 Переключательные функции одной переменной (n=1)

3.3 Переключательные функции двух переменных (n=2)

3.4 Базисные логические функции

3.5 Принцип двойственности булевой алгебры

3.6 Основные тождества булевой алгебры

3.7 Основные законы и теоремы булевой алгебры

3.7.1 Законы

3.7.2 Теоремы

3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений

3.9 Дизъюнктивная нормальная форма (ДНФ)

3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений

3.11 Конъюнктивная нормальная форма (КНФ)

3.12 Минимизация логических функций

3.12.1 Алгебраический способ минимизации ПФ

3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)

3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча

3.12.2.1.1 Общие правила минимизации

3.12.2.1.2 Примеры минимизации ПФ с помощью диаграмм Вейча

3.12.2.2 Минимизация ПФ с помощью карт Карно

4. ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

4.1 Инвертор (логический элемент НЕ)

4.2 Конъюнктор (логический элемент И)

4.3 Дизъюнктор (логический элемент ИЛИ)

4.4 Повторитель

4.5 И–НЕ

4.6 ИЛИ–НЕ

4.7 Исключающее ИЛИ

4.8 Сложение по модулю два (нечетность)

4.9 Сложение по модулю два с отрицанием (четность)

4.10 Эквивалентность

4.11 Неэквивалентность

4.12 И–ИЛИ–НЕ

4.13 Запрет

4.14 Логические элементы с открытым коллектором

4.15 Логические элементы с третьим состоянием

5. РЕАЛИЗАЦИЯ ЛОГИЧЕСКИХ ФУНКЦИЙ в разных базисах

5.1 Базисные наборы ЛЭ и их взаимосвязь

5.2 Реализация логических функций в различных базисах

5.2.1 Реализация элемента “Равнозначность” (исключающее ИЛИ - НЕ)

5.2.2 Реализация элемента “Неравнозначность” (исключающее ИЛИ, сумма по модулю два)

5.2.3 Реализация элемента “Запрет”

5.2.4 Реализация многобуквенных логических функций на элементах с небольшим количеством входов

6. ПАРАМЕТРЫ И ХАРАКТЕРИСТИКИ ЦИФРОВЫХ ИНТЕГРАЛЬНЫХ МИКРОСХЕМ (ИМС)

6.1 Коэффициент объединения по входу (Коб)

6.2 Коэффициент разветвления по выходу (Краз)

6.3 Статические характеристики

6.4 Помехоустойчивость

6.5 Динамические характеристики и параметры

6.6 Вид реализуемой логической функции

6.7 Потребляемые токи и мощность

6.8 Входные и выходные токи, напряжения

6.9 Пороговые напряжения

6.10 Допустимые значения основных параметров

7. БАЗОВЫЕ ЛОГИЧЕСКИЕ ЭЛЕМЕНТЫ

7.1 Базовый ТТЛ (ТТЛШ) - элемент И-НЕ

7.2 Базовый ЭСЛ - элемент ИЛИ/ИЛИ-НЕ

7.3 Базовый КМОП-элемент ИЛИ-НЕ

8. ГЕНЕРАТОРЫ ТАКТОВЫХ ИМПУЛЬСОВ (ГТИ) на логических элементах

8.1 ГТИ на двух инверторах

8.2 ГТИ на 3-х инверторах

9. ФУНКЦИОНАЛЬНЫЕ УСТРОЙСТВА КОМПЬЮТЕРНОЙ (ЦИФРОВОЙ) ЭЛЕКТРОНИКИ

9.1 Комбинационные цифровые устройства (КЦУ)

9.1.1 Анализ и синтез КЦУ

9.1.1.1 Анализ КЦУ

9.1.1.2 Синтез КЦУ

9.1.2 Типовые КЦУ

9.1.2.1 Шифраторы и дешифраторы

9.1.2.1.1 Шифраторы двоичного кода

9.1.2.1.2 Шифраторы двоично-десятичного кода

9.1.2.1.3 Дешифраторы двоичного кода

9.1.2.1.4 Дешифратор BCD-кода в семисегментный код

9.1.2.1.4.1 Семисегментные индикаторы на светодиодах

9.1.2.2 Мультиплексоры и демультиплексоры

9.1.2.2.1 Мультиплексоры

9.1.2.2.2 Демультиплексоры

9.1.2.2.3 Мультиплексоры–селекторы (мультиплексоры-демультиплексоры)

9.1.2.3 Сумматоры и полусумматоры

9.1.2.4 Устройства контроля четности (УКЧ)

9.1.2.5 Цифровые компараторы

9.1.3 Использование для проектирования КЦУ мультиплексоров, дешифраторов и постоянных запоминающих устройств

9.1.3.1 Построение КЦУ на мультиплексорах

9.1.3.2 Построение КЦУ на дешифраторах

9.1.3.3 Построение КЦУ на постоянном запоминающем устройстве (ПЗУ)

9.2 Последовательностные цифровые устройства

9.2.1 Триггеры

9.2.1.1 Триггеры на логических элементах

9.2.1.1.1 RS - триггеры

9.2.1.1.1.1 Асинхронные RS - триггеры

9.2.1.1.1.2 Синхронные RS - триггеры

9.2.1.1.2 Т-триггеры (триггеры со счетным входом)

9.2.1.1.3 D-триггеры (триггеры задержки)

9.2.1.1.4 JK-триггеры

9.2.1.2 Триггеры в интегральном исполнении

9.2.2 Регистры

9.2.2.1 Параллельные регистры

9.2.2.2 Последовательные (сдвигающие) регистры

9.2.2.3 Регистры сдвига

9.2.2.4 Последовательно-параллельные и параллельно-последовательные регистры

9.2.2.5 Регистры в интегральном исполнении

9.2.3.1 Асинхронный суммирующий двоичный счетчик с последовательным переносом

9.2.3.2 Асинхронный вычитающий двоичный счетчик с последовательным переносом

9.2.3.3 Асинхронные реверсивные двоичные счетчики с последовательным переносом

9.2.3.4 Синхронный счетчик со сквозным переносом

9.2.3.5 Десятичные счетчики

9.2.3.6 Счетчики в интегральном исполнении

9.2.4 Делители частоты

9.2.5 Распределители

10. СВЯЗЬ МП-РА И ОМЭВМ С АНАЛОГОВЫМ ОБЪЕКТОМ УПРАВЛЕНИЯ И С ПК

10.1 Структура типичной локальной микропроцессорной системы управления (ЛМПСУ)

10.1.1 Назначение и схемная реализация отдельных узлов ЛМПСУ

10.1.1.1 Аналоговый мультиплексор (АМПС)

10.1.1.2 Устройство выборки-хранения (УВХ)

10.1.1.3 Аналого-цифровой преобразователь (АЦП)

10.1.1.4 Ведомая однокристальная микроЭВМ (ОМЭВМ)

10.1.1.5 Шинный формирователь (ШФ)

10.1.1.6 Регистры (Рг1...Рг3)

10.1.1.7 Схемы согласования уровней (ССУ1...ССУ3)

10.1.1.8 Цифро-аналоговые преобразователи (ЦАП1...ЦАП3)

10.2 Применение АЦП и УВХ при вводе аналоговой информации в МПС

10.2.1 Расчет АЦП

10.2.2 АЦП К1113 ПВ1

10.2.2.1 Описание микросхемы К1113 ПВ1

10.2.2.2 Расчет микросхемы К1113 ПВ1

10.2.2.3 Ввод данных от АЦП в МПС через ППИ в режиме 0

10.2.3 Устройство выборки и хранения (УВХ)

10.2.3.1 Обоснование применения УВХ

10.2.3.2 Принцип действия, схема и основные параметры УВХ

10.2.3.3 Функциональные возможности и схема включения микросхемы УВХ К1100СК2 (КР1100СК2)

10.2.4 АЦП MAX154

10.2.4.1 Описание микросхемы MAX154. Временные диаграммы и режимы работы

10.2.4.2 Расчет АЦП MAX154

10.3 Применение ЦАП при выводе цифровой информации из МПС

10.3.1 Расчет ЦАП на матрице R-2R c суммированием токов

10.3.2 ЦАП К572 ПА1

10.3.2.1 Описание микросхемы К572 ПА1

10.3.2.2 Расчет ЦАП К572 ПА1

10.3.3 ЦАП MAX506

10.3.3.1 Описание микросхемы MAX506

10.3.3.2 Расчет ЦАП MAX506

10.4 Особенности аппаратной и программной реализации модуля АЦП-ЦАП МПС

10.4.1 Аппаратный уровень

10.4.2 Программный уровень

10.5 Обмен между МП-м (ОМЭВМ) и ПК по последовательному каналу связи с помощью интерфейса RS-232С

10.5.1 Устройство асинхронное программируемое приёмопередающее (УАПП)

10.5.2 Устройство преобразования уровней (УПУ)

10.5.3 Разъём RS-232С

10.5.4 Буферный регистр адреса RS-232C

10.5.5 Шинный формирователь

10.6 Выбор и расчет датчиков, нормирующих преобразователей и фильтров нижних частот (ФНЧ)

10.6.1 Выбор и расчет датчиков и нормирующих преобразователей

10.6.1.1 Выбор датчиков

10.6.1.2 Выбор нормирующих преобразователей

10.6.2 Выбор ФНЧ

10.6.3 Расчет ФНЧ

10.7 Разработка схемы алгоритма и управляющей программы

СПИСОК ЛИТЕРАТУРЫ


1. ВВЕДЕНИЕ


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

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

Название кода определяется системой счисления, используемой для представления сообщений. Подробно основные системы счисления, применяемые в цифровой электронике и микропроцессорной технике, рассматриваются в [3, 5, 19].

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

Система счисления (СС) - способ записи чисел при помощи определенных знаков, чаще всего арабских цифр, но иногда и латинских букв, например, шестнадцатеричная система счисления.

Основание СС - определяется числом символов, используемых в системе счисления. Например, двоичная система счисления имеет основание два, десятичная - десять и т. д.

Разрядность чисел. Каждое число характеризуется количеством разрядов. Разряд - это место, которое занимает цифра (буква) в числе. Крайний правый разряд в числе называют нулевым (начальным, младшим или младшим значащим разрядом (МЗР)). Если количество разрядов равно n, то крайний левый разряд называют (n-1)-м (старшим или старшим значащим разрядом (СЗР)).

Вес разряда. Равен основанию СС, возведенном в степень, равную номерам разрядов, которые нумеруются от 0 до (n-1). Например, если рассмотреть 3-х разрядное десятичное число, то веса его разрядов равны:

нулевого - 100 = 1;

первого - 101 = 10;

второго - 102 = 100;

Аналогично веса трехразрядного двоичного числа равны:

нулевого - 20 = 1;

первого - 21=2;

второго - 22=4.

Веса используются для определения десятичного эквивалента чисел. Например, десятичный эквивалент двоичного числа 10110 равен:

1Ч24 + 0Ч23 + 1Ч22 + 1Ч21 + 0Ч20 = 22

Числа, представленные в двоичной системе счисления (двоичным кодом), должны содержать справа от МЗР латинскую букву В, в десятичной системе - D, шестнадцатеричной - H. Если буква отсутствует, то по умолчанию компьютер (микропроцессор) считает число, представленным в десятичной системе счисления.

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


2. ДИСКРЕТИЗАЦИЯ АНАЛОГОВЫХ СИГНАЛОВ


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

Различают 3-и вида дискретизации:

по уровню;

по времени;

по уровню и времени (комбинированная).

Рассмотрим каждый из названных видов квантования более подробно.


2.1 Квантование по уровню


Предположим, что информация отображается аналоговым (непрерывным) напряжением U(t), которое медленно изменяется по закону, представленному на рисунке 2.1.

Мгновенные значения этого напряжения лежат в диапазоне ((Umin=0)…Umax). При выполнении операции квантования по уровню диапазон изменения значений непрерывной величины разбивается на ряд уровней Nу, включая нулевой. Число Nу определяется из выражения


Компьютерная схемотехника,(2.1)


где ∆U – величина шага квантования по уровню. Последняя является постоянной величиной (∆U=const) и определяется требуемой погрешностью дискретизации. В нашем примере = 5. Каждый уровень пронумерован в десятичной системе счисления. Работа квантователя сводится к следующему: он определяет моменты времени, когда входной аналоговый сигнал достигает очередного дискретного уровня.


Компьютерная схемотехника

Рисунок 2.1


Эти моменты обозначены t0, t1, t2, t3... Очевидно, что при нелинейном входном сигнале интервал между соседними временными отсчетами является переменной величиной (∆t = var). Примером устройств, в которых осуществляется квантование по уровню, является релейные (пороговые) устройства.


2.2 Квантование по времени


Компьютерная схемотехника

Рисунок 2.2


При выполнении операции квантования по времени (рисунок 2.2) непрерывный входной сигнал заменяется решетчатым (дискретным), снимаемым с выхода квантователя в дискретные моменты времени t1, t2, t3,... Интервал между соседними моментами времени ∆t = t1-t0 = t2-t1= =... = const. Очевидно, что разность соседних значений входного сигнала при нелинейном законе изменения входного напряжения является переменной величиной (U=var). Примером устройств, в которых осуществляется квантование по времени, являются импульсные системы автоматического управления [20].


2.3 Квантование по уровню и по времени


Компьютерная схемотехника

Рисунок 2.3


Работа такого преобразователя (рисунок 2.3) сводится к тому, что из непрерывного сигнала периодически производятся выборки мгновенных значений. Временной интервал между соседними выборками ∆t=const. Каждая выборка округляется преобразователем до ближайшего уровня квантования, полученного от дискретизации по уровню. Интервал между соседними уровнями ∆U=const. Значение уровня представляется в десятичной или двоичной системе счисления (десятичным или двоичным кодом). Код уровня в свою очередь представляется цифровым сигналом. Выходной сигнал имеет ступенчатую форму и с определенной степенью точности соответствует преобразуемому аналоговому напряжению. По такому принципу работают электронные аналогово-цифровые преобразователи (АЦП) [10, 13].

цифровой электронный логический микросхема


2.3.1 Расчет погрешности АЦП

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


Компьютерная схемотехника.(2.2)


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

Абсолютная погрешность, появляющаяся при квантовании по уровню:


Компьютерная схемотехника,(2.3)


где ∆U величина шага квантования по уровню, равная


Компьютерная схемотехника.(2.4)


Из приведенного соотношения следует, что максимальная абсолютная погрешность равна половине шага квантования по уровню. Относительная погрешность квантования по уровню:


Компьютерная схемотехника,(2.5)


где Nд – число дискретных значений выходной величины (уровней квантования). В формуле (2.5) из Nд вычитается единица, т.к. одним из дискретных значений (уровней) является нулевое (рисунок 2.3). Отсюда требуемое число уровней дискретных значений, которое отражает нашу непрерывную функцию с заданной точностью, определяется из выражения:


Компьютерная схемотехника(2.6)


Пример расчета АЦП

Задано значение относительной погрешности δотн Ј 2%.

Требуется определить разрядность АЦП, удовлетворяющего заданному значению δотн.

Определяем число уровней квантования (число дискретных значений):

Ny Компьютерная схемотехника(50/2)+1=26.

Выбираем число разрядов АЦП Np ДК=5, что удовлетворяет выражению (2.5):

25=32>26.


2.3.2 Выбор величины шага квантования по времени

Величина шага квантования по времени ∆t, определяющая требуемое быстродействие АЦП, рассчитывается в соответствии с теоремой взятия отсчетов (теоремой Котельникова)


Компьютерная схемотехника,(2.7)


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

Любой АЦП является инерционным устройством, имеющим конечное время преобразования tпрб, которое должно удовлетворять требуемому значению ∆t.

Если входной аналоговый сигнал меняется достаточно быстро, а АЦП имеет низкое быстродействие, то может появиться апертурная погрешность, выражающаяся в том, что за время преобразования АЦП изменение входного сигнала эквивалентно изменению выходного ДК больше, чем на единицу МЗР. Для борьбы с этим явлением применяют устройства выборки-хранения (УВХ), которые запоминают мгновенное значение входного аналогового сигнала в момент временной выборки и поддерживают это значение постоянным до следующей выборки.

При проектировании компьютеризированных систем часто возникает обратная задача: преобразование цифрового сигнала в аналоговый (непрерывный). Для этого применяют цифро-аналоговые преобразователи (ЦАП).


3. ПРИМЕНЕНИЕ АЛГЕБРЫ ЛОГИКИ (БУЛЕВОЙ АЛГЕБРЫ) ПРИ АНАЛИЗЕ И СИНТЕЗЕ ЦИФРОВЫХ ЭЛЕКТРОННЫХ УСТРОЙСТВ


3.1 Определение и способы задания переключательных функций


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

Математическим аппаратом, применяемым при анализе и синтезе ЛЭУ, является алгебра логики, разработанная в середине Х1Х века английским математиком Дж. Булем, и поэтому часто называемая Булевой алгеброй (БА).

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

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

Логические функции обозначаются прописными буквами F или Y, а двоичные переменные - А, В, С, D, E, ... или строчной буквой икс с индексом, например, x1, х2, х3 ... .

ПФ может быть выражена (задана):

словесно;

алгебраическим (булевым) выражением;

таблицей истинности;

диаграммой Вейча (картой Карно).

Примеры задания переключательной функции (ПФ):

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

2) выражением: Компьютерная схемотехника

3) таблицей истинности (таблица 3.1)

Таблица включает наборы (комбинации) логических переменных, которые должны быть упорядочены по возрастанию или убыванию их десятичных эквивалентов, а также значения функции на каждом наборе. Каждый набор имеет номер, равный десятичному эквиваленту двоичного числа, если наборы упорядочены по возрастанию. Если число переменных равно n, то количество наборов N = 2n. Номера наборов изменяются от 0 до (2n-1). Общее число переключательных функций n – переменных


Компьютерная схемотехника.(3.1)


Таблица 3.1

№ набора В А F
0 0 0 0
1 0 1 0
2 1 0 0
3 1 1 1

Представление переключательной функции диаграммой Вейча (картой Карно) будет рассмотрено позднее при изучении вопроса минимизации ПФ.


3.2 Переключательные функции одной переменной (n=1)


Если n=1, то число наборов N=21=2, а количество ПФ Компьютерная схемотехника (таблица 3.2)

Таблица 3.2

N набора A F0 F1 F2 F3
0 0 0 1 0 1
1 1 0 0 1 1

Функция F0 называется константой нуля, так как на всех наборах принимает нулевое значение (F0=0). Функция F3 - константа единицы, так как всегда равна единице (F3=1). Функция F2=A называется повторением, а Компьютерная схемотехника– инверсией (отрицанием – не А).


3.3 Переключательные функции двух переменных (n=2)


Если n=2, то число наборов N=22 =4, а количество ПФ Компьютерная схемотехника (таблица 3.3)

Отметим из этих шестнадцати функций 2-х переменных наиболее часто использующиеся:

F0 – константа нуля;

F15 – константа единицы;

F8=АКомпьютерная схемотехникаВ=А*В – конъюнкция (логическое умножение (логическое “И”));

F14=АКомпьютерная схемотехникаВ=А+В – дизъюнкция (логическое сложение (логическое “ИЛИ”));

F6=Компьютерная схемотехника – исключающее ИЛИ (сумма по модулю два, неравнозначность, неэквивалентность);

Компьютерная схемотехника – равнозначность (эквивалентность);

Компьютерная схемотехника – ИЛИ-НЕ;

Компьютерная схемотехника – И - НЕ.


Таблица 3.3

№ набора В А F0 F1 F2 F3 F4 F5 F6 F7 F8 F9 F10 F11 F12 F13 F14 F15
0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
2 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 1 1 1
3 1 1 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1

3.4 Базисные логические функции


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


3.5 Принцип двойственности булевой алгебры


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

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


3.6 Основные тождества булевой алгебры


А+0=А;А+1=1;

А+А=А;А+Компьютерная схемотехника=1;

А*0=0;А*1=А;

А*А=А;А*Компьютерная схемотехника=0;Компьютерная схемотехника=А.


3.7 Основные законы и теоремы булевой алгебры


3.7.1 Законы

Переместительный (свойство коммутативности): А+В=В+А; А*В=В*А.

Сочетательный (свойство ассоциативности): (А+В)+С=А+(В+С); (А*В)*С=А*(В*С).

Распределительный (свойство дистрибутивности): А*(В+С)=А*В+А*С; А+В*С=(А+В)*(А+С).


3.7.2 Теоремы

Поглощения: А+А*В=А; А*(А+В)=А.

Склеивания: Компьютерная схемотехника

Де Моргана. Существует две формы записи теоремы де Моргана:


Форма 1:Компьютерная схемотехника(3.1.1)

Форма 2:Компьютерная схемотехника(3.1.2)


Последние два выражения вытекают из принципа двойственности булевой алгебры (раздел 3.5).

Теорема без названия. Существует еще одна теорема без названия, которую представим следующим образом:

Компьютерная схемотехника(3.1.3)


Два полезных соотношения:


Компьютерная схемотехника(3.1.4)


3.8 Совершенная дизъюнктивная нормальная форма (СДНФ) записи булевых выражений


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

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

Таблица 3.4

№набора С В А F
0 0 0 0 0
1 0 0 1 1
2 0 1 0 0
3 0 1 1 0
4 1 0 0 1
5 1 0 1 1
6 1 1 0 1
7 1 1 1 0

Эта функция имеет четыре конституенты единицы К1, К4, К5 и К6 (коституента единицы – это единичное значение ПФ на одном конкретном наборе. Всего для ПФ трех переменных может быть восемь конституент единицы, если функция принимает единичное значение на всех наборах). Конституента единицы записывается в виде конъюнкции. Для нашего примера Компьютерная схемотехника Компьютерная схемотехника; Компьютерная схемотехника Компьютерная схемотехника.

Булево выражение ПФ в СДНФ представляет сумму конституент единицы:


Компьютерная схемотехника.(3.2)


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

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


3.9 Дизъюнктивная нормальная форма (ДНФ)


Если в выражении (3.2) во всех или некоторых конъюнкциях отсутствуют отдельные переменные (в прямой или инверсной форме) или ряд конъюнкций, отображающих конституенты единицы, отсутствуют вообще, то такая форма представления булевого выражения называется дизъюнктивной нормальной формой (ДНФ).

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


3.10 Совершенная конъюнктивная нормальная форма (СКНФ) записи булевых выражений


Описанная таблицей 3.4 переключательная функция помимо конституент единицы содержит конституенты нуля К0, К2, К3 и К7 (конституента нуля – это нулевое значение ПФ на одном конкретном наборе). Всего для ПФ 3-х переменных может быть восемь конституент нуля, если функция принимает нулевое значение на всех наборах. Конституента нуля записывается в виде дизъюнкции. Для нашего примера (таблица 3.4) это


Компьютерная схемотехника

Булево выражение в СКНФ представляет собой произведение конституент нуля:


Компьютерная схемотехника.(3.3)


СКНФ называется конъюнктивной (состоит из произведения дизъюнкций), совершенной (все дизъюнкции включают по одному разу каждую переменную в прямом или инверсном виде) и нормальной (двухуровневой) – для ее реализации требуются логические элементы двух видов: конъюнкторы и дизъюнкторы, при этом предполагается, что исходные переменные поступают в прямом или инверсном виде.

Логическая функция имеет единственное булево выражение в СКНФ.


3.11 Конъюнктивная нормальная форма (КНФ)


Если в выражении (3.3) все дизъюнкции или отдельные из них не содержат всех переменных в прямом или инверсном виде, а также некоторые дизъюнкции вообще отсутствуют, то такая форма представления булевого выражения называется конъюнктивной нормальной формой (КНФ).

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


3.12 Минимизация логических функций


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

Способы минимизации:

– алгебраический;

– с помощью диаграмм Вейча (карт Карно).


3.12.1 Алгебраический способ минимизации ПФ

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

Пример 1. Исходное булево выражение:


Компьютерная схемотехника.(3.4)


Применяя теорему склеивания, получим булево выражение


Компьютерная схемотехника,(3.5)

которое равносильно (эквивалентно) исходному, но значительно проще его.

Пример 2. Исходное булево выражение:


Компьютерная схемотехника.(3.6)


Используя тождество А=А+А и теорему склеивания получим более простое выражение


Компьютерная схемотехника.(3.7)


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

Более наглядным и удобным является минимизация с применением диаграмм Вейча (карт Карно).


3.12.2 Минимизация ПФ с использованием диаграмм Вейча (карт Карно)

Диаграммы Вейча (карты Карно) [3, 11, 18] построены так, что их соседние клетки содержат члены исходной ПФ, отличающиеся значением одной переменной: один член содержит эту переменную в прямой форме, а другой – в инверсной. Благодаря этому возникает наглядное представление о различных вариантах склеивания смежных членов.


3.12.2.1 Минимизация ПФ с помощью диаграмм Вейча

Исходным продуктом для применения диаграмм Вейча является представление ПФ таблицей истинности, в которой возможные наборы переменных упорядочены по возрастанию или по убыванию их десятичных эквивалентов (таблица 3.1). Вид диаграмм Вейча зависит от числа переменных минимизируемой ПФ - n и от того, как упорядочены наборы переменных в таблице. Если наборы упорядочены по возрастанию их десятичных эквивалентов, то диаграммы Вейча для n=2,3,4 имеют вид, приведенный на рисунке 3.1.


Компьютерная схемотехника

Рисунок 3.1


Число клеток диаграммы равно количеству наборов переменных


Nкл=Nнаб=2n.(3.8)


Если n=2, то Nкл=22=4; n=3 – Nкл=8, n=4 – Nкл=16.

Каждая клетка соответствует определенному набору переменных и имеет номер, одинаковый с номером набора.

Строки и столбцы диаграммы, помеченные чертой, определяют наборы, в которых переменные принимают единичные значения (входят в прямой форме). Строки и столбцы, не помеченные чертой, соответствуют наборам, в которых те же переменные принимают нулевые значения (входят в инверсной форме). Например, для n=3 (рисунок 3.1) двум левым столбцам соответствует единичное значение переменной В (в входит в прямой форме), а двум правым – нулевое значение (в входит в инверсной форме).

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

ПФ считается неопределенной, если:

1) данный набор переменных в реальном логическом устройстве невозможен;

2) значение функции на данном наборе безразлично.

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

В первом случае результатом минимизации будет булево выражение в ДНФ, а во втором – в КНФ.


3.12.2.1.1 Общие правила минимизации

Минимизацию можно проводить по единицам (нулям). При этом:

1) Смежные единицы (нули) диаграммы условно охватывают (накрывают) прямоугольными контурами. Каждый контур может содержать 2,4,8,16, ... единиц (нулей).

2) Одним контуром (накрытием) необходимо объединить максимальное количество смежных клеток, содержащих единицы (нули).

3) Необходимо, чтобы каждая единица (нуль) накрывалась хотя бы один раз.

4) Одна и та же единица (нуль) может охватываться несколько раз разными контурами.

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

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

7) Угловые клетки также считаются смежными - диаграмму можно мысленно свернуть в тор.

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

9) Результатом минимизации является булево выражение в ДНФ (КНФ). Количество конъюнкций в ДНФ (дизъюнкций в КНФ) соответствует числу контуров (накрытий).

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

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

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

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

На рисунке 3.1 показаны диаграммы Вейча при числе логических переменных n=2,3,4. Для n>4 диаграммы содержатся в [18]. Если наборы переменных исходной таблицы истинности упорядочены по убыванию их десятичных эквивалентов, то следует воспользоваться диаграммами Вейча,

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: