Логические выражения.

Базовые логические элементы

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

Определение: Дискретное устройство, которое преобразует последовательность двоичных сигналов и выдает значение одной из функций алгебры логики (логической операции), называется логическим элементом. Использование большого количества логических элементов увеличивает трудозатраты на построение компьютера, повышает его стоимость. Поэтому разработчики компьютеров стремятся к использованию минимального количества различных логических элементов при его проектировании. И при этом разработчики компьютеров (инженеры и математики) должны быть уверены, что они смогут выразить любую логическую функцию через выбранную систему логических элементов. Другими словами, они должны будут исследовать, является ли выбранная система логических элементов полной или нет. Дешифратор. Логическая формула Определение: Устройство, преобразующее входной двоичный код в сигнал на одном из выходов, называется дешифратором. Дешифратор является одним из базовых узлов компьютера. В ЭВМ с помощью дешифраторов осуществляется выборка необходимых ячеек оперативной памяти, расшифровка кодов машинных операций, перевод двоичных чисел в десятичные. Говорят, что дешифратор имеет разрядность n, если он имеет n входов и 2n выходов. На вход дешифратору подается n двоичных сигналов-переменных, на одном выходе появляется логическая единица, на остальных – логические нули. Зависимость количества выходов от количества входов объяснить достаточно просто: существует 2n различных двоичных чисел длины n (все незначащие нули выписываем, записывая соответствующее число ровно в n разрядах). Построим таблицу истинности для дешифратора с n = 3 входами. Выходы дешифратора будем нумеровать от 0 до 7. Если мы этот дешифратор будем использовать для перевода двоичных чисел в восьмеричные, то на наборе {0 0 0} только на выходе 0 (функция f0) мы должны получить 1, на всех остальных выходах – значение 0. Для набора {0 0 1} мы должны получить 1 на первом выходе (функция f1), а для всех остальных функций – 0. И, наконец, для набора {1 1 1} мы должны получить 1 только на седьмом выходе (функция f7). Входы Выходы x1 x2 x3 f0 f1 f2 f3 f4 f5 f6 f7 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 Очевидно, что функции для каждого выхода можно записать в следующем виде: Таким образом, на каждом выходе k значение 1 получится в том и только в том случае, если на вход был подан набор сигналов, который соответствует двоичной записи числа k.  Сумматор двоичных чисел. Формулы для суммы двоичных цифр и признака переноса Для того чтобы компьютер мог выполнять различные операции (как арифметические, так и логические), необходимо уметь конструировать устройства, которые будут преобразовывать последовательности нулей и единиц, получаемые на входе, в другие двоичные последовательности в соответствии с заданной функцией. Определение: Электронная логическая схема, которая выполняет суммирование двоичных кодов, называется сумматором. Рассмотрим сложение двух двоичных чисел a и b: Заметим, что при сложении цифр в i-ом разряде мы должны сложить цифру ai числа a, цифру bi числа b и цифру pi, которая является признаком переноса из (i – 1)-го разряда. В результате сложения должны получиться цифра результата si и цифра переноса в следующий разряд pi+1. Основываясь на этих рассуждениях, построим таблицу истинности для функций, которые в зависимости от цифр ai, bi и pi получают цифры si = ai + bi и pi+1. Входы Выходы ai bi pi si pi+1 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 На основе приведенной таблицы истинности можно построить логическую формулу для функции si, получающей очередную цифру результата, и функции pi+1, формирующей признак переноса (0 или 1) в следующий разряд. Эти функции можно записать в следующем виде: Выразить si и pi+1 можно и другими формулами. Например, самая короткая формула для , что позволяет построить сумматор, используя другие логические элементы. Если при суммировании не учитывается признак переноса, то соответствующая логическая схема называется полусумматором. Входы Выходы ai bi si pi+1 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 Полусумматоры также используются при построении компьютера, например, из двух полусумматоров можно построить один сумматор.  Триггер. Логическая формула Необходимой составной частью компьютера является оперативная память. После процессора оперативную память можно считать самым быстродействующим устройством компьютера. Именно в нее загружаются все программы на выполнение. Объем оперативной памяти в современных компьютерах постоянно растет, совершенствуется технология изготовления чипов памяти. Ячейкой памяти является триггер — логический элемент с двумя устойчивыми состояниями, в любом из которых он сохраняется до тех пор, пока подается питание. Время срабатывания триггера составляет в современных компьютерах единицы наносекунд. Определение: Логический элемент, способный хранить один разряд двоичного числа, называется триггером. Триггер был изобретен в 1918 году М.А. Бонч-Бруевичем, руководителем Нижегородской лаборатории связи. Самым простым является RS–триггер. Он состоит из двух элементов ИЛИ-НЕ, входы которых соединены кольцом: выход первого соединен со входом второго, выход второго – со входом первого. Для запоминания 1 байта информации необходимо 8 триггеров, для 1 Кбайта – 8 * 1024 = 8192 триггера. Оперативная память современных ЭВМ содержит миллионы триггеров. RS-триггер устроен следующим образом: он имеет два входа R (reset) и S (set) и два выхода Q и . Если на выходе Q имеет высокое напряжение, то считается, что RS-триггер хранит единицу, если низкое, то он хранит ноль. Для выхода Q все происходит наоборот. Если на вход R подается единица, то триггер устанавливается в состояние «0». Если на вход S подается единица, то триггер устанавливается в состояние «1». Если R = S = 0, то триггер сохраняет предыдущее состояние. Состояние R = S = 1 недопустимо. Запишем эти правила работы триггера в виде таблицы истинности для выхода Qt+1, где входами являются Rt, St и Qt. При этом Qt - текущее состояние триггера на момент времени t, а Qt+1 – состояние, в которое перейдет триггер в момент времени t + 1, обработав поступившие сигналы. Rt St Qt Qt+1 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 0 1 0 1 0 1 1 0 Недопустимо 1 1 1 Недопустимо Для того чтобы сконструировать логическую схему, реализующую RS-триггер, необходимо записать в виде формулы функцию, описывающую работу триггера. По таблице истинности мы можем построить такую логическую формулу, для этого надо воспользоваться алгоритмом построения СДНФ по таблице истинности. Затем надо произвести тождественные преобразования для получения как можно более короткой формулы.