1)
Количество информации. Формулы Шеннона и Хартли. Примеры применения этих формул.
В 1928 г. американский инженер Р. Хартли предложил научный подход к оценке сообщений. Предложенная им формула имела следующий вид:
I = log2 K ,
Где К - количество равновероятных событий; I - количество бит в сообщении, такое, что любое из К событий произошло. Тогда K=2I.
Иногда формулу Хартли записывают так:
I = log2 K = log2 (1 / р) = - log2 р,
т. к. каждое из К событий имеет равновероятный исход р = 1 / К, то К = 1 / р.
Задача.
Шарик находится в одной из трех урн: А, В или С. Определить сколько бит информации содержит сообщение о том, что он находится в урне В.
Решение.
Такое сообщение содержит I = log2 3 = 1,585 бита информации.
Но не все ситуации имеют одинаковые вероятности реализации. Существует много таких ситуаций, у которых вероятности реализации различаются. Например, если бросают несимметричную монету или "правило бутерброда".
"Однажды в детстве я уронил бутерброд. Глядя, как я виновато вытираю масляное пятно, оставшееся на полу, старший брат успокоил меня:
- не горюй, это сработал закон бутерброда.
- Что еще за закон такой? - спросил я.
- Закон, который гласит: "Бутерброд всегда падает маслом вниз". Впрочем, это шутка, - продолжал брат.- Никакого закона нет. Прсто бутерброд действительно ведет себя довольно странно: большей частью масло оказывается внизу.
- Давай-ка еще пару раз уроним бутерброд, проверим, - предложил я. - Все равно ведь его придется выкидывать.
Проверили. Из десяти раз восемь бутерброд упал маслом вниз.
И тут я задумался: а можно ли заранее узнать, как сейчас упадет бутерброд маслом вниз или вверх?
Наши опыты прервала мать…"
( Отрывок из книги "Секрет великих полководцев", В.Абчук).
В 1948 г. американский инженер и математик К Шеннон предложил формулу для вычисления количества информации для событий с различными вероятностями.
Если I - количество информации,
К - количество возможных событий,
рi - вероятности отдельных событий,
то количество информации для событий с различными вероятностями можно определить по формуле:
I = - Sum рi log2 рi,
где i принимает значения от 1 до К.
Формулу Хартли теперь можно рассматривать как частный случай формулы Шеннона:
I = - Sum 1 / К log2 (1 / К) = I = log2 К.
При равновероятных событиях получаемое количество информации максимально.
2)
Законы алгебры логики
Законы алгебры логики базируются на аксиомах и позволяют преобразовывать логические функции. Логические функции преобразуются с целью их упрощения, а это ведет к упрощению цифровой схемы.
АКСИОМЫ алгебры логики описывают действие логических функций "И" и "ИЛИ" и записываются следующими выражениями:
0 * 0 = 0
0 * 1 = 0
1 * 0 = 0
1 * 1 = 1 0 + 0 = 0
0 + 1 = 1
1 + 0 = 1
1 + 1 = 1
Всего имеется пять законов алгебры логики:
1. Закон одинарных элементов
1 * X = X
0 * X = 0
1 + X = 1
0 + X = X
Этот закон непосредственно следует из приведённых выше выражений аксиом алгебры логики.
Верхние два выражения могут быть полезны при построении коммутаторов, ведь подавая на один из входов элемента “2И” логический ноль или единицу можно либо пропускать сигнал на выход, либо формировать на выходе нулевой потенциал.
Второй вариант использования этих выражений заключается в возможности избирательного обнуления определённых разрядов многоразрядного числа. При поразрядном применении операции "И" можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды единичный или нулевой потенциал. Например, требуется обнулить 6, 3 и 1 разряды. Тогда:
В приведённом примере отчётливо видно, что для обнуления необходимых разрядов в маске (нижнее число) на месте соответствующих разрядов записаны нули, в остальных разрядах записаны единицы. В исходном числе (верхнее число) на месте 6 и 1 разрядов находятся единицы. После выполнения операции "И" на этих местах появляются нули. На месте третьего разряда в исходном числе находится ноль. В результирующем числе на этом месте тоже присутствует ноль. Остальные разряды, как и требовалось по условию задачи, не изменены.
Точно так же можно записывать единицы в нужные нам разряды. В этом случае необходимо воспользоваться нижними двумя выражениями закона одинарных элементов. При поразрядном применении операции “ИЛИ” можно либо оставлять прежнее значение разряда, либо обнулять его, подавая на соответствующие разряды нулевой или единичный потенциал. Пусть требуется записать единицы в 7 и 6 биты числа. Тогда:
Здесь в маску (нижнее число) мы записали единицы в седьмой и шестой биты. Остальные биты содержат нули, и, следовательно, не могут изменить первоначальное состояние исходного числа, что мы и видим в результирующем числе под чертой.
Первое и последнее выражения позволяют использовать логические элементы с большим количеством входов в качестве элементов с меньшим количеством входов. Для этого неиспользуемые входы в схеме “И” должны быть подключены к источнику питания, как это показано на рисунке 1:
Рисунок 1. Схема "2И-НЕ", реализованная на элементе "3И-НЕ".
а неиспользуемые входы в схеме "ИЛИ" должны быть подключены к общему проводу схемы, как это показано на рисунке 2.
Рисунок 2. Схема "НЕ", реализованная на элементе "2И-НЕ".
2. Законы отрицания
a. Закон дополнительных элементов.
Выражения этого закона широко используется для минимизации логических схем. Если удаётся выделить из общего выражения логической функции такие подвыражения, то можно сократить необходимое количество входов элементов цифровой схемы, а иногда и вообще свести всё выражение к логической константе.
a. Двойное отрицание
b. Закон отрицательной логики
Закон отрицательной логики справедлив для любого числа переменных. Этот закон позволяет реализовывать логическую функцию "И" при помощи логических элементов “ИЛИ” и наоборот: реализовывать логическую функцию “ИЛИ” при помощи логических элементов “И”. Это особенно полезно в ТТЛ схемотехнике, так как там легко реализовать логические элементы “И”, но при этом достаточно сложно логические элементы “ИЛИ”. Благодаря закону отрицательной логики можно реализовывать элементы “ИЛИ” на логических элементах “И”. На рисунке 3 показана реализация логического элемента “2ИЛИ” на элементе “2И-НЕ” и двух инверторах.
Рисунок 3. Логический элемент “2ИЛИ”, реализованный на элементе “2И-НЕ” и двух инверторах.
То же самое можно сказать и о схеме монтажного “ИЛИ”. В случае необходимости его можно превратить в монтажное “И”, применив инверторы на входе и выходе этой схемы.
3. Комбинационные законы.
Комбинационные законы алгебры логики во многом соответствуют комбинационным законам обычной алгебры, но есть и отличия.
a. закон тавтологии (многократное повторение)
X+X+X+X=X
X*X*X*X=X
Этот закон позволяет использовать логические элементы с большим количеством входов в качестве элементов с меньшим количеством входов. Например, можно реализовать двухвходовую схему 2И на элементе 3И, как это показано на рисунке 4:
Рисунок 4. Схема “2И-НЕ”, реализованная на элементе “3И-НЕ”.
или использовать схему 2И-НЕ в качестве обычного инвертора, как это показано на рисунке 5:
Рисунок 5. Схема “НЕ”, реализованная на элементе “2И-НЕ”.
Однако следует предупредить, что объединение нескольких входов увеличивает входные токи логического элемента и его ёмкость, что увеличивает ток потребления предыдущих элементов и отрицательно сказывается на быстродействии цифровой схемы в целом.
Для уменьшения числа входов в логическом элементе лучше воспользоваться законом одинарных элементов, как это было показано выше.
a. закон переместительности
A+B+C+D=A+C+B+D
b. закон сочетательности
A+B+C+D=A+(B+C)+D=A+B+(C+D)
c. закон распределительности
X1(X2+X3)= X1X2 + X1X3
X1+X2X3=(X1+X2)(X1+X3)=/ докажем это путём раскрытия скобок/= X1X1+ X1X3+ X1X2+ X2X3= X1(1+X3+X2)+ X2X3= X1+X2X3
4. Правило поглощения (одна переменная поглощает другие)
X1+X1X2 X3 =X1(1+X2 X3)=X1
5. Правило склеивания (выполняется только по одной переменной)
3)
Поразрядные операции
К поразрядным операциям относятся: операция поразрядного логического "И" (&), операция поразрядного логического "ИЛИ" (|), операция поразрядного "исключающего ИЛИ" (^).
Операнды поразрядных операций могут быть любого целого типа. При необходимости над операндами выполняются преобразования по умолчанию, тип результата - это тип операндов после преобразования.
Операция поразрядного логического И (&) сравнивает каждый бит первого операнда с соответствующим битом второго операнда. Если оба сравниваемых бита единицы, то соответствующий бит результата устанавливается в 1, в противном случае в 0.
Операция поразрядного логического ИЛИ (|) сравнивает каждый бит первого операнда с соответствующим битом второго операнда. Если любой (или оба) из сравниваемых битов равен 1, то соответствующий бит результата устанавливается в 1, в противном случае результирующий бит равен 0.
Операция поразрядного исключающего ИЛИ (^) сравнивает каждый бит первого операнда с соответствующими битами второго операнда. Если один из сравниваемых битов равен 0, а второй бит равен 1, то соответствующий бит результата устанавливается в 1, в противном случае, т.е. когда оба бита равны 1 или 0, бит результата устанавливается в 0.
4)
5)
6)
1. Функции алгебры логики (ФАЛ).
ФАЛ называются функция , аргументы и значения которой определены на множестве {0, 1}. Как обычно, сложная ФАЛ может быть определена как композиция из простых применением операции подстановки. Скобочная запись такой композиции называется формулой, которая строится по принятым в математике законам.
Пример: . Скобочная формула отражает структуру подстановок из составляющих функций f1, f2, f3, f4 .
В связи с тем, что число наборов значений аргументов конечно, ФАЛ удобно задавать таблицей.
Таблица истинности ФАЛ состоит из всех возможных наборов значений аргументов. Каждый набор отмечается либо «1» (единичные наборы), либо «0» (нулевые наборы). Эти отметки суть значения функции. Очевидно, что количество наборов значений ФАЛ – 2п, а количество различных функций на этих наборах (количество различных разметок) – (см. например, табл. 1).
Особое место занимают бинарные ФАЛ (функции от двух аргументов), из них с помощью операции подстановок могут быть образованы функции от любого количества аргументов. В табл. 1 приведен полный список таких функций, их названия, а также названия операций, определяющих эти функции.
Табл. 1. Таблица бинарных функций алгебры логики.
х1 0 1 0 1 Знак
операции Наименование
функции Свойства
х2 0 0 1 1
0 0 0 0 0
Конст. «0»
1 0 0 0 1
&;•; Конъюнкция, логич. умнож.
2 0 0 1 0 х1 х2
Запрет х2
Защелка х2 наддув воздуха в помещении
дверь х2=0 х2=0 х2=1 х2=1
окно х1=0 х1=1 х1=0 х1=1
3 0 0 1 1 х2 х2
4 0 1 0 0 х2 х1 Запрет х1
Защелка х1
5 0 1 0 1 х1 х1
6 0 1 1 0
Слож. по
mod 2
7 0 1 1 1
Дизъюнкция логич. слож.
Продолжение табл. 1
8 1 0 0 0
Стрелка Пирса функция Даггера
9 1 0 0 1
Эквиваленция совпадение
10 1 0 1 0
Отрицание
х1
11 1 0 1 1
Импликация следование
«из х1 след. х2»
12 1 1 0 0
Отрицание
х2
13 1 1 0 1
Импликация
« из х2 след. х1»
14 1 1 1 0
Штрих Шеффера
15 1 1 1 1 F15 = 1 Конст. «1»
2. Алгебра логики и эквивалентные преобразования ФАЛ.
Алгебра логики представляет собой перечень свойств операций &, V, , заданных через соотношения эквивалентностей.
1) Коммутативность
2) Ассоциативность
3) Дистрибутивность
4) Идемпотентность ;
5) Закон исключенного третьего (свойства «»)
6) Закон Де Моргана
7) Закон поглощения
Свойства операций задаются системой эквивалентных преобразований, любая эквивалентность проверяется по таблице. Эта система называется алгеброй логики. Почему логики? На самом деле, все эквивалентности, входящие в алгебру, являются логическими законами.
Определение эквивалентности (тождественности функций).
Пара функций называется эквивалентными, если значения функций совпадают на одинаковых наборах в таблице функций.
1) x1x2= 2) x1x2=
3) x1x1= 4) x1x1=
3. Стандартные формулы представления ФАЛ.
1) Любая ФАЛ может быть представлена в виде совершенной дизъюнктивной нормальной формы (СДНФ).
– все возможные комбинации расстановок отрицаний над переменными (отрицание – = 0, нет отрицания – = 1)
Очевидно любая расстановка значений или 1 даёт конкретную реализацию функций (см. пример) из .
2) Любая ФАЛ может быть представлена в виде совершенной конъюнктивной нормальной формы (СКНФ).
…
Любая расстановка значений или 1 даёт конкретную реализацию функций (см. пример) из .
Пример: Построение СДНФ и СКНФ по таблице истинности функций.
а) СДНФ состоит из элементов конъюнкции, соединённых знаком дизъюнкции. В таблице выделяются единичные наборы. Если в наборе , то в элементарной конъюнкции xi, иначе , то .
б) СКНФ состоит из элементов дизъюнкций, соединённых знаком конъюнкции. В таблице выделяются нулевые наборы. Если в наборе , то в элементарной дизъюнкции , иначе , то .
Табл.2
№ x1 x2 x3 f-
0 0 0 0 1
1 0 0 1 0
2 0 1 0 1
3 0 1 1 0
4 1 0 0 0
5 1 0 1 0
6 1 1 0 1
7 1 1 1 1
(0 0 0) (0 1 0) (1 1 0) (1 1 1)
f (СДНФ)
(0 0 1) (0 1 1) (1 0 0) (1 0 1)
f1 (СКНФ)
3) Любая ФАЛ может быть представлена в виде полинома Жегалкина.
и т.д. все пары переменных
……………………………….…..и т.д. все тройки
……………………………….…..и т.д.
Любая расстановка значений или 1 даёт реализацию конкретной функции.
Пример: Для функции, заданной табл. 2, полином Жегалкина будет иметь вид:
Формы СДНФ, СКНФ, ПЖ суть коды функций. Количество различных кодов, построенных по соответствующим правилам, равно и поэтому каждый код является уникальным и соответствует конкретной функции.
7)
Из множества функционально полных наборов рассмотрим только те, которые имеют наибольшее практическое значение.
1. Основная функционально полная система логических функций. Наибольшее распространение получил набор, в состав которого входят три логические функции:
• f10 – инверсия (логическая связь НЕ, логическое отрицание);
• f1 – конъюнкция (логическая связь И, логическое умножение),
• f7 – дизъюнкция (логическая связь ИЛИ, логическое сложение).
Этот набор получил название функционально полной системы логических функций (ОФПС). Из теоремы о функциональной полноте следует, что основная функционально полная система логических функций является избыточной, так как условиям теоремы отвечают наборы функций f10 и f1 или f10 и f7. Свойства этих функций были рассмотрены ранее.
Из определения представления переключательной функции в виде дизъюнктивной или конъюнктивной нормальной формы следует, что эти представления реализуются в основной функционально полной системе логических функций.
2. Законы алгебры логики в ОФПС и их следствия. В алгебре логики имеются четыре основных за¬кона, регламентирующих порядок производства операций НЕ, И, ИЛИ в любом логическом выражении:
• переместительный (коммутативный);
• сочетательный (ассоциативный);
• распределительный (дистрибутивный);
• инверсии (правило Де Моргана).
Переместительный закон. Этот закон справедлив как для дизъюнкции, так и для конъюнкции:
x1 Úx2 = x2 Úx1; x1 Ùx2 = x2 Ù x1. (1)
Справедливость выражения (5.1) нетрудно доказать простой подста¬новкой в него различных значений x1 и x2. Поскольку любую переста¬новку большего количества слагаемых можно свести к последователь¬ности перестановок слагаемых в отдельных парах, то переместитель¬ный закон будет справедлив при любом числе слагаемых.
Сочетательный закон. Этот закон, так же как и переместительный, является симметричным, т. е. справедливым и для дизъюнкции, и для конъюнкции:
x1 Úx2 Úx3 = x1Ú(x2 Úx3) = (x1 Úx2)Úx3= x2Ú( x1 Úx3); (2)
x1 Ùx2 Ùx3 = x1Ùx2 Ùx3) = (x1 Ùx2)Ùx3= x2Ù( x1 Ùx3).
Доказательство этого закона также не представляет никаких труд¬ностей и может быть выполнено простой подстановкой.
Распределительный закон. В отличие от обычной алгебры алгебра логики симметрична. В ней справедливы два распределительных закона:
для логического умножения относительно логического сложения (рас¬пределительный закон 1-го рода) и для логического сложения относи¬тельно логического умножения (распределительный закон 2-го рода).
1. Распределительный закон 1-го рода записывается следующим образом:
(x1Úx2)Ùx3=(x1Ùx3)Ú ( x2 Ùx3) . (3)
Справедливость формулы (5.3), а также и ее более общего случая, когда в скобках заключена сумма любого количества слагаемых, можно доказать путем установления идентичности условий обращения в 0 или 1 ее левой и правой частей. Условием обращения в нуль левой части выражения (5.3) состоит в том, чтобы нулю равнялся либо один аргумент х3, либо одновременно аргументы x1 и x2. Условия обращения в нуль правой части выражения (5.1) такие же. Следовательно, распределительный закон 1-го рода справедлив для алгебры логики.
2. Распределительный закон 2-го рода имеет вид
(x1Ùx2)Úx3=(x1Úx3)Ù ( x2Úx3). (4)
Cправедливость формулы (4) (при любом количестве аргументов) нетрудно доказать посредством установления идентичности условий обращения обеих ее частей в единицу.
8)
Вычислительная техника в настоящее время ворвалась в жизнь каждого
человека. Появление микропроцессоров произвело переворот не только в
промышленности, но и в повседневной жизни.
Микропроцессоры сегодня используются в банкоматах и мобильных
телефонах, стиральных машинах и СВЧ-печах, электронных весах и
термометрах, автоматах по продаже напитков и железнодорожных
билетов и многих других бытовых устройствах. Огромное значение имеет
микропроцессорная техника для современного производства. Это станки с
программным управлением и обрабатывающие центры, промышленные роботы
и автоматические технологические линии. Требуется все больше специалистов,
способных внедрять и обслуживать новейшую технику.
Сведения об отдельных элементах вычислительной техники учащиеся
получают из курсов физики, информатики, трудового обучения. Данная
программа предназначена для учащихся, желающих получить знания,
необходимые для понимания функций микропроцессорных управляющих
систем, изучить устройство и принцип действия основных элементов цифровой
электроники, научиться составлять из них узлы и схемы, которые являются
основой вычислительной техники.
Курс по выбору «Основы вычислительной техники» рекомендуется
учащимся 11-х классов с 12-летним сроком обучения. Программа курса
рассчитана на 34 часа (1 час в неделю). По усмотрению учителя сроки изучения
курса могут быть передвинуты.
Данный курс расширяет базовый курс школьной информатики, носит
характер предпрофессиональной подготовки и знакомит учащихся с основами
вычислительной техники. Предлагаемые темы достаточно сложны, вместе
с тем, содержание курса позволяет любому ученику активно включиться в
учебно-познавательный процесс и максимально проявить себя. История развития микропроцессоров. Типы процессоров. Принципы
работы микропроцессора (МП). Оперативное запоминающее устройство (ОЗУ).
Арифметико-логическое устройство (АЛУ).
Команды микропроцессора. Организация памяти. Кодирование команд.
Регистры процессора. Работа со стековой памятью. Способы адресации.
Машинные языки. Синтаксис ассемблера. Структура программы на языке
ассемблера. Команды и директивы. Директивы описания данных. Разработка
программы на языке ассемблера: этапы написания и отладки программы.
Основные команды МП: команды обмена данными, арифметические
команды,
логические
и
команды
сдвига.
Команды
управления.
Программирование типовых управляющих структур.
Система прерываний и организация ввода-вывода.
Логические элементы — устройства, предназначенные для обработки информации в цифровой форме (последовательности сигналов высокого — «1» и низкого — «0» уровней в двоичной логике, последовательность "0", "1" и "2" в троичной логике, последовательности "0", "1", "2", "3", "4", "5", "6", "7", "8"и "9" в десятичной логике). Физически логические элементы могут быть выполнены механическими, электромеханическими (на электромагнитных реле), электронными (на диодах и транзисторах), пневматическими, гидравлическими, оптическими и др.
С развитием электротехники от механических логических элементов перешли к электромеханическим логическим элементам (на электромагнитных реле), а затем к электронным логическим элементам на электронных лампах, позже - на транзисторах. После доказательства в 1946 г. теоремы Джона фон Неймана о экономичности показательных позиционных систем счисления стало известно о преимуществах двоичной и троичной систем счисления по сравнению с десятичной системой счисления. От десятичных логических элементов перешли к двоичным логическим элементам. Двоичность и троичность позволяет значительно сократить количество операций и элементов, выполняющих эту обработку, по сравнению с десятичными логическими элементами.
Логические элементы выполняют логическую функцию (операцию) с входными сигналами (операндами, данными).
Всего возможно логических функций и соответствующих им логических элементов, где - основание системы счисления, - число входов (аргументов), - число выходов, т.е. бесконечное число логических элементов. Поэтому в данной статье рассматриваются только простейшие и важнейшие логические элементы.
Всего возможны двоичных двухвходовых логических элементов и двоичных трёхвходовых логических элементов (Булева функция).
Кроме 16 двоичных двухвходовых логических элементов и 256 трёхвходовых двоичных логических элементов возможны 19 683 двухвходовых троичных логических элемента и 7 625 597 484 987 трёхвходовых троичных логических элементов (троичные функции).
Логические операции (булева функция) своё теоретическое обоснование получили в алгебре логики.
Логические операции с одним операндом называются унарными, с двумя — бинарными, с тремя — тернарными (триарными, тринарными) и т. д.
Из возможных унарных операций с унарным выходом интерес для реализации представляют операции отрицания и повторения, причём, операция отрицания имеет большую значимость, чем операция повторения, так как повторитель может быть собран из двух инверторов, а инвертор из повторителей не собрать.
[править]Отрицание, НЕТ, НЕ
Инвертор, НЕ
A B = A
0 1
1 0
Мнемоническое правило для отрицания звучит так: На выходе будет:
"1" тогда и только тогда, когда на входе «0»,
"0" тогда и только тогда, когда на входе «1»
[править]Повторение, ДА
Повторитель (буфер,) ДА
A B = A
0 0
1 1
Преобразование информации требует выполнения операций с группами знаков, простейшей из которых является группа из двух знаков. Оперирование с большими группами всегда можно разбить на последовательные операции с двумя знаками.
Из возможных бинарных логических операций с двумя знаками c унарным выходом интерес для реализации представляют 10 операций, приведённых ниже.
[править]Конъюнкция (логическое умножение). Операция 2И. Функция min(A,B)
2И
A B f(AB)
0 0 0
1 0 0
0 1 0
1 1 1
Логический элемент, реализующий функцию конъюнкции, называется схемой совпадения. Мнемоническое правило для конъюнкции с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда на всех входах действуют «1»,
"0" тогда и только тогда, когда хотя бы на одном входе действует «0»
[править]Дизъюнкция (логическое сложение). Операция 2ИЛИ. Функция max(A,B)
2ИЛИ
A B f(AB)
0 0 0
1 0 1
0 1 1
1 1 1
Мнемоническое правило для дизъюнкции с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда хотя бы на одном входе действует «1»,
"0" тогда и только тогда, когда на всех входах действуют «0»
[править]Инверсия функции конъюнкции. Операция 2И-НЕ (штрих Шеффера)
2И-НЕ
A B f(AB)
0 0 1
0 1 1
1 0 1
1 1 0
Мнемоническое правило для И-НЕ с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда хотя бы на одном входе действует «0»,
"0" тогда и только тогда, когда на всех входах действуют «1»
[править]Инверсия функции дизъюнкции. Операция 2ИЛИ-НЕ (стрелка Пирса)
2ИЛИ-НЕ
A B f(AB)
0 0 1
0 1 0
1 0 0
1 1 0
Мнемоническое правило для ИЛИ-НЕ с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда на всех входах действуют «0»,
"0" тогда и только тогда, когда хотя бы на одном входе действует «1»
[править]Эквивалентность (равнозначность), 2ИСКЛЮЧАЮЩЕЕ_ИЛИ-НЕ
A B f(AB)
0 0 1
0 1 0
1 0 0
1 1 1
Мнемоническое правило эквивалентности с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда на входа действует четное количество «1»,
"0" тогда и только тогда, когда на входа действует нечетное количество «1»
[править]Сложение по модулю 2 (2Исключающее_ИЛИ, неравнозначность). Инверсия равнозначности.
В англоязычной литературе 2XOR.
A B f(AB)
0 0 0
0 1 1
1 0 1
1 1 0
Мнемоническое правило для суммы по модулю 2 с любым количеством входов звучит так: На выходе будет:
"1" тогда и только тогда, когда на входа действует нечётное количество «1»,
"0" тогда и только тогда, когда на входа действует чётное количество «1»
[править]Импликация от A к B (инверсия декремента)
A B f(AB)
0 0 1
0 1 1
1 0 0
1 1 1
Мнемоническое правило для инверсии декремента звучит так: На выходе будет:
"0" тогда и только тогда, когда на "B" меньше "А",
"1" тогда и только тогда, когда на "B" больше либо равно "А"
[править]Импликация от B к A (инверсия инкремента)
A B f(AB)
0 0 1
0 1 0
1 0 1
1 1 1
Мнемоническое правило для инверсии инкремента звучит так: На выходе будет:
"0" тогда и только тогда, когда на "B" больше "А",
"1" тогда и только тогда, когда на "B" меньше либо равно "А"
[править]Декремент. Запрет импликации по B. Инверсия импликации от A к B
A B f(AB)
0 0 0
0 1 0
1 0 1
1 1 0
Мнемоническое правило для инверсии импликации от A к B звучит так: На выходе будет:
"1" тогда и только тогда, когда на "A" больше "B",
"0" тогда и только тогда, когда на "A" меньше либо равно "B"
[править]Инкремент. Запрет импликации по A. Инверсия импликации от B к A
A B f(AB)
0 0 0
0 1 1
1 0 0
1 1 0
Мнемоническое правило для инверсии импликации от B к A звучит так: На выходе будет:
"1" тогда и только тогда, когда на "B" больше "A",
"0" тогда и только тогда, когда на "B" меньше либо равно "A"
Примечание 1. Элементы импликаций не имеют промышленных аналогов для функций с количеством входов, не равным 2.
Примечание 2. Элементы импликаций не имеют промышленных аналогов.
Этими простейшими логическими операциями (функциями), и даже некоторыми их подмножествами, можно выразить любые другие логические операции. Такой набор простейших функций называется функционально полным логическим базисом. Таких базисов 4:
И, НЕ (2 элемента)
ИЛИ, НЕ (2 элемента)
И-НЕ (1 элемент)
ИЛИ-НЕ (1 элемент).
Для преобразования логических функций в один из названых базисов необходимо применять Закон (правило) де-Моргана.
Упрощённая схема двухвходового элемента И-НЕ ТТЛ .
9)
Полусумматор — логическая схема, имеющая два входа и два выхода (двухразрядный сумматор, бинарный сумматор). Полусумматор используется для построения двоичных сумматоров. Полусумматор позволяет вычислять сумму A+B, где A и B — это разряды двоичного числа, при этом результатом будут два бита S,C, где S — это бит суммы по модулю, а C — бит переноса. Однако, как можно заметить, для построения схемы двоичного сумматора (трёхразрядный сумматор, тринарный сумматор) необходимо иметь элемент, который суммирует три бита A, B и C, где C — бит переноса из предыдущего разряда, таким элементом является полный двоичный сумматор, который как правило состоит из двух полусумматоров и логического элемента 2ИЛИ.
Полусумматор - составная часть сумматора. На схеме изображен полусумматор, состоящий из вентилей ИСКЛЮЧАЮЩЕЕ ИЛИ и И.
S (сумма) равна единицы, если только одно значение (a или b) равно единице. Если значения обоих входных переменных совпадают, то сумма текущего разряда равна нулю.
P (перенос) равен единице, если оба входных значения равны единицы. Во всех остальных случаях значение переноса равно нулю.
сумматор
Он (рис. 4) имеет три входа: a, b — для двух слагаемых и p — для переноса из предыдущего (более младшего) разряда и два выхода: S — сумма, P — перенос в следующий (более старший) разряд. Обозначением полного двоичного сумматора служат буквы SM. Работу его отражает таблица истинности 3 (табл. 3).
Рис. 4
Таблица 3
№ наб. a b p P S
0 0 0 0 0 0
1 0 0 1 0 1
2 0 1 0 0 1
3 0 1 1 1 0
4 1 0 0 0 1
5 1 0 1 1 0
6 1 1 0 1 0
7 1 1 1 1 1
Отметим два момента. Первый: в табл. 2 и 3 выходные сигналы P и S не случайно расположены именно в такой последовательности. Это подчеркивает, что PS рассматривается как двухразрядное двоичное число, например, 1 + 1 = 210 = 102 , то есть P = 1, а S = 0 или 1 + 1 + 1 = 310 = 112, то есть P = 1, а S = 1. Второй: выходные сигналы P и S полного двоичного сумматора относятся к классу самодвойственных функций алгебры логики. Самодвойственными называют функции, инвертирующие своё значение при инвертировании всех переменных, от которых они зависят. Обратите внимание, что P и S для четвертьсумматора и полусумматора не являются самодвойственными функциями! Преимущества, вытекающие из этого свойства полного двоичного сумматора, будут рассмотрены при анализе возможностей ИС типа 155ИМ1.
Уравнения, описывающие работу полного двоичного сумматора, представленные в совершенной дизъюнктивной нормальной форме (СДНФ), имеют вид:
(6)
Уравнение для переноса может быть минимизировано:
P = ab + ap + bp.(7)
При практическом проектированиии сумматора уравнения (6) и (7) могут быть преобразованы к виду, удобному для реализации на заданных логических элементах с некоторыми ограничениями (по числу логических входов и др.) и удовлетворяющему предъявляемым к сумматору требованиям по быстродействию.
Например, преобразуем уравнения (6) следующим образом:
(8)
Из выражений (8) следует, что полный двоичный сумматор может быть реализован на двух полусумматорах и одном двухвходовом элементе ИЛИ. Соответствующая схема приведена на рис. 5.
Рис. 5
Из выражения (8) для S также следует:
S = a Е b Е p.(9)
Примечание. Так как операция Е в выражении (9) коммутативна (переменные можно менять местами), то следует, что три входа полного двоичного сумматора абсолютно равноправны и на любой из них можно подавать любую входную переменную. Это полезно помнить, разводя печатные платы, на которых установлены ИС сумматоров.
К настоящему времени разработано большое число схем сумматоров. Доказано (нашим отечественным ученым Вайнштейном), что при использовании только одного инвертора нельзя реализовать полный двоичный сумматор со сложностью Pкв < 16, а при двух инверторах — Pкв < 14, где Pкв — вес по Квайну, используемый как оценка сложности любых комбинационных схем. Pкв — это общее число всех входов всех логических элементов схемы без учёта инверторов.
Рис. 6
Покажем, используя два метода, как была получена рациональная (с использованием только одного инвертора) схема полного двоичного сумматора, явившаяся основой схем ИС сумматоров типа 7480, 155ИМ1 и др.
Первый метод основан на использовании значения выходного переноса P как вспомогательной переменной при определении выходной суммы S (табл. 4). В табл. 4 при наборах переменных, являющихся нереальными (например, единичное значение переноса при нулевых значениях всех входных переменных), поставлены безразличные значения (крестик) для функции S, которые можно доопределять произвольным образом.
Таблица 4
№ наб. a b p P S
0 0 0 0 0 0
1 0 0 0 1 x
2 0 0 1 0 1
3 0 0 1 1 x
4 0 1 0 0 1
5 0 1 0 1 x
6 0 1 1 0 x
7 0 1 1 1 0
8 1 0 0 0 1
9 1 0 0 1 x
10 1 0 1 0 x
11 1 0 1 1 0
12 1 1 0 0 x
13 1 1 0 1 0
14 1 1 1 0 x
15 1 1 1 1 1
Из карты Карно для функции S (рис. 6) следует:
S = abp + Pa + Pb + Pp = = abp + P(a + b + p). (10)
Второй метод основан на применении диаграмм Венна. На рис. 7а показана диаграмма Венна для трех переменных а, b, p; области, ограниченные окружностями, соответствуют переменным а, b, p, а области, обозначенные цифрами от 0 до 7 — соответствующим конъюнкциям (например, 5 = abp). Область, заштрихованная на рис. 7б, очевидно, соответствует функции P = ab + ap + bp. Функция S представлена заштрихованной областью на рис. 7в. Её можно представить суммой произведения функции a + b + p (рис. 7г) на функцию ab + ap + bp (рис. 7д) и функции abp (рис. 7е). Очевидно, что в этом случае получается выражение для S, аналогичное уравнению (10).
Рис. 7
Схема сумматора, реализованного по уравнениям (7) и (10), приведена на рис. 8а. В данной схеме используются многовходовые логические элементы И и ИЛИ. Если использовать только двухвходовые элементы, то получаются схемы, приведённые на рис. 8б,в.