Полностью и не полностью определенные функции алгебры логики.

Полностью и не полностью определенные функции алгебры логики.

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

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

Функции алгебры логики одной переменной.

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

Функции алгебры логики двух переменных

Таблица истинности функции двух переменных Y=f(X1, Х2) содержит 4 строки, а число функций двух переменных равно 16.

1. Логическое ИЛИ (логическое сложение, дизъюнкция):

Y= X1 + X2 = X1VX2

Техническая реализация этой функции - два параллельно соединенных ключа:

Таблица истинности логического ИЛИ имеет вид:

Логический элемент ИЛИ обозначается на схемах следующим образом:

2. Логическое И (логическое умножение, конъюнкция, схема совпадений): Y = X1X2 = X1& X2

Техническая реализация этой функции - два последовательно соединенных ключа:

Таблица истинности логического И имеет вид:

Логический элемент И обозначается на схемах следующим образом:

Основные свойства функций алгебры логики

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

коммутативный (переместительный)

ассоциативный (сочетательный)

Эти законы полностью идентичны законам обычной алгебры;

дистрибутивный (распределительный)

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

Закон склеивания

Закон свёртки

Правило де Моргана

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

6. Функционально полные системы, понятие базиса.

Функционально полной системой булевых функций (ФПСБФ) называется совокупность таких булевых функций (f1, f2, ... fk), что произвольная булева функция f может быть записана в виде формулы через функции этой совокупности.

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

1) " И-ИЛИ-НЕ" (базис конъюнкции, дизъюнкции, инверсии)

2) " И-НЕ" (базис Шеффера)

3) " ИЛИ-НЕ" (базис Пирса или функция Вебба).

Элементы, реализующие операцию " И-НЕ", “ИЛИ-НЕ” и “Исключающее ИЛИ” на принципиальных и структурных схемах изображаются так:

Алгебраический метод минимизации.

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

Метод существенных переменных.

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

· Выписать все гиперкубы из M1(f) и импликанты.

· Взять простые импликанты.

· Построить таблицу накрытия.

· Из оставшихся простых импликантов создать тупиковую ДНФ.

Построим таблицу истинности для нее:

Выпишем все гиперкубы, лежащие в M1(f) и соответствующие им импликанты:

Выбираем простые импликанты и строим таблицу их накрытия:

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

Преобразователи кода.

Микросхемы преобразователей кодов (англ. сonverter) служат для преобразования входных двоичных кодов в выходные двоично-десятичные и наоборот - входных двоично-десятичных кодов в выходные двоичные.

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

Шифратор преобразует одиночный сигнал в n-разрядный двоичный код. Наибольшее применение он находит в устройствах ввода информации для преобразования десятичных чисел двоичную систему счисления. Предположим, на пульте десять клавишей с гравировкой от 0 до 9. При нажатии любой из них на вход шифратора подаётся единичный сигнал (ХО-Х9).

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

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

Компаратор цифровой – это устройство, осуществляющее сравнение двух многоразрядных двоичных чисел. В общем случае, на рисунке показан компаратор, который получает на выходе логическую ‘1’ при равенстве двух многоразрядных двоичных чисел. Два многоразрядных числа равны, если в одноименных разрядах цифры одинаковые.

Цифровые компараторы выполняют сравнение двух чисел, заданных в двоичном коде. Они могут определять равенство двух двоичных чисел А и В с одинаковым количеством разрядов либо вид неравенства А> В или А< В. Цифровые компараторы имеют три выхода.

Схема одноразрядного компаратора представляет собой структуру логического элемента «исключающее ИЛИ–НЕ»

Из анализа схемы следует, что если А = В, то F = 1, в противном случае, т. е. при А ≠ В, F = 0. Если А > В, т. е. А = 1, В = 0, то С = 1, а если А < В, т. е. А = 0, В = 1, то D = 1.

Если попарно равны между собой все разряды двух n-разрядных двоичных чисел, то равны и эти два числа А и В. Применяя цифровой компаратор для каждого разряда, например, четырехзначных чисел, и определяя значения F₁, F₂, F₃, F₄ логических переменных на выходах компараторов, факт равенства А = В установим в случае, когда F = F₁ · F₂ · F₃ · F₄ = 1. Если же F = 0, то А ≠ В. Неравенство А> В обеспечивается (для четырехразрядного числа) в четырех случаях: или А₄ > В₄, или А₄ = В₄ И А₃> В₃, или А₄ = В₄, А₃ =В₃ и А₂ > В₂, или А₄ = В₄, А₃ = В₃, А₂ = В₂ и А₁ > В₁, где А₄ и В₄ – старшие разряды чисел А и В). Очевидно, что если поменять местами A _i и B_i то будет выполняться неравенство А < В. Цифровые компараторы выпускают, как правило, в виде самостоятельных микросхем. Так, микросхема К564ИП2 (рис. 1.24) является четырехразрядным компаратором, в котором каждый из одноразрядных компараторов аналогичен рассмотренной ранее схеме. Данная микросхем а имеет расширяющие входы А< В, А=В, А> В, что позволяет наращивать разрядность обоих чисел. Для этого компараторы соединяют каска дно или параллельно (пирамидально ).

Триггеры, типы триггеров.

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

RS-триггер. Асинхронный триггер RS-типа имеет два информационных входа R и S. Входы S и R названы по первым буквам английских слов set - установка и reset - сброс. При S=1 и R=0 на выходах триггера появляются сигналы: на прямом выходе Q=1, на инверсном Q=0. При S=0 и R=1 выходные сигналы триггера принимают противоположные состояния (Q=0, Q=1). Этот триггер не имеет тактового входа. Простейший RS-триггер можно реализовать на логических элементах ИЛИ-НЕ или И-НЕ, как показано на рисунке 1.

Проиллюстрировать работу такого асинхронного триггера можно с помощью таблиц истинности или временных диаграмм. Обратите внимание, что простейший триггер при S=1 и R=0 устанавливается в состояние логического нуля (и наоборот). Здесь Q – состояние выхода до установки входных сигналов (режим хранения).

На элементах ИЛИ-НЕ	На элементах И-НЕ
Вход S	Вход R	Прям. Q	Инвер. Q	Вход S	Вход R	Прям. Q	Инвер. Q
		Q	Q


						Q	Q

При одновременном поступлении сигнала 1 или 0 на входы R и S выходные сигналы триггера не определены, поэтому в устройствах на основе RS-триггера необходимо исключать такие режимы (запрещенное состояние). Существуют разновидности RS-триггера, носящие название Е-, R- и S-триггеров, для которых сочетание S=1 и R=1 не является запрещенным.
Синхронный одноступенчатый RS-триггер рис. 2 отличается от асинхронного наличием С-входа для синхронизирующих тактовых импульсов. Синхронный триггер состоит из асинхронного RS-триггера и двух логических элементов на его входе.


а	б	в

Рис. 2. Синхронный RS-триггер.

Регистры

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

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

Параллельный регистр служит для запоминания многоразрядного двоичного (или недвоичного) слова. Количество триггеров, входящее в состав параллельного регистра определяет его разрядность. Схема четырёхразрядного параллельного регистра приведена на рисунке 1, а его условно-графическое обозначение - на рисунке 2.

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

В приведённом на рисунке 2 условно-графическом обозначении параллельного регистра инверсные выходы триггеров не показаны. В микросхемах регистров инверсные выходы триггеров часто не выводятся наружу для экономии количества выводов корпуса.

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

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

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

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

Кроме параллельного соединения триггеров для построения регистров используются последовательное соединение этих элементов.

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

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

В этом регистре триггеры соединены последовательно, то есть выход первого соединён с входом второго и т.д. Условно-графическое изображение рассмотренного последовательного регистра приведено на рисунке 4.

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

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

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

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

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

Сдвиговые регистры.

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

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

Однако, как известно, в любом двоичном числе слева расположены старшие разряды, а справа - младшие разряды. Поэтому сдвиг двоичного числа вправо будет сдвигом в сторону младших разрядов, а сдвиг влево - сдвигом в сторону старших разрядов.

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

Накапливающий сумматор.

Накапливающий сумматор (НС) обычно представляет собой совокупность сумматора комбинационного типа и регистра (который хранит результаты суммирования как текущие, так и окончательные). Работает такой сумматор по формуле Si = Si-1 + A, ( формула 1.1) где
Si –текущая сумма,
Si-1 –предыдущая(на предыдущем цикле суммирования),
А – очередное текущее слагаемое.

Результат замещает старое значение суммы. Очередное прибавление слагаемого тактируется синхроимпульсами. Учитывая такие особенности функцио-нирования накапливающие сумматоры называются иногда аккумуляторами. На схемах сумматоры обозначаются SM. В российских сериях интегральных микросхем(ИМС), соответственно – ИР(например-К155ИМ3). В американских
сериях они отдельно не обозначаются: SN40S08N. Интегральные микросхемы содержат, как правило, четырехразрядные комбинационные сумматоры. Чаще всего применяют четырехразрядные сумматоры комбинационного типа. Помимо выходных разрядов суммы и выхода переноса в сумматорах предусмотрен вход расширения С для обьединения сумматоров с целью повышения разрядности.

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

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

Накапливающие сумматоры применяются также, например, для формирования адреса ОЗУ, в генераторах сигналов произвольной формы.

Кольцевой счетчик.

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

Рисунок 1. Схема кольцевого счетчика.

Рассмотрим работу этой схемы. Пусть первоначально в счетчике записано число 00₂. После первого же тактового импульса состояние счётчика станет равным 10₂, после второго - 11₂. Временные диаграммы этой схемы приведены на рисунке 2.

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

К_д = 2*n.

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

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

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

Счетчик Джонсона.

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

Рисунок 6. Схема счетчика Джонсона.

Здесь регистр сдвига К155ИР1 дополнен D-триггером. Вход D-триггера соединен с выходом четвертого разряда регистра, а на информационный вход I регистра подан сигнал не с прямого, а с инверсного выхода этого триггера. За счет этого и реализуется перекрестная связь в кольце. В отличие от простейших кольцевых счетчиков счетчик Джонсона имеет коэффициент пересчета вдвое больший числа составляющих его триггеров. В частности, счетчик рис. 6 под воздействием счетных импульсов n последовательно проходит следующие состояния:

n	Q₁	Q₂	Q₃	Q₄	Q₅

Как видно, при счете сначала от первого разряда до последнего распространяется волна единиц, а затем волна нулей. В счетчике Джонсона, как и в других кольцевых счетчиках, возможны сбои в виде лишних волн нулей или единиц. Для предотвращения их в десятичном счетчике простая цепь связи инверсного выхода последнего и входа первого разряда I=Q₅ может быть заменена логической ячейкой, реализующей функцию I=Q₁Q₄+Q₅. Связи, соответствующие этой ячейке, показаны штриховыми линиями на рис. 6. Подобная ячейка обеспечивает переход счетчика под воздействием входных импульсов из любой запрещенной комбинации в одну из разрешенных. На основе регистра с одной перекрестной связью может быть построен счетчик с любым четным коэффициентом пересчета. Если же нужен нечетный коэффициент пересчета 2_N-1, то используется N-разрядный регистр сдвига, но на вход 1-го разряда подается сигнал неQ_N, a Q_NQ_N-i. При этом по сравнению с обычным счетчиком Джонсона пропускается одна кодовая комбинация, полностью составленная из нулей.

Двоичные счетчики.

Счётчики используются для построения таймеров или для выборки инструкций из ПЗУ в микропроцессорах. Они могут использоваться как делители частоты в управляемых генераторах частоты (синтезаторах). При использовании в цепи ФАП счётчики могут быть использованы для умножения частоты как в синтезаторах, так и в микропроцессорах.

Полностью и не полностью определенные функции алгебры логики.

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

12 3 4 5 6 Следующая ⇒