Логическая основа вс

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

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

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

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

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

К элементарным ФАЛ одного аргумента относятся:

1. Константа нуля. Реализуется генератором нуля, который на схемах обозначается соединением соответствующего входа ЛЭ с «землей» (общим проводом источника питания).

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

3. Повторение. Реализуется логическим элементом повторителем. Записывается ФАЛ как у = х.

4. Инверсия или логическое отрицание. Реализуется логическим элементом НЕ (инвертором).

Записывается ФАЛ как у = x .

2. Основные ФБА

Основными из элементарных ФАЛ двух аргументов являются:

1. Дизъюнкция (логическое сложение). Реализуется логическим элементом ИЛИ. Записывается ФАЛ как у = aVb.

2 . Конъюнкция (логическое умножение). Реализуется логическим элементом И. Записывается ФАЛ как у = a^b.

3 . Стрелка Пирса. Реализуется логическим элементом ИЛИ-НЕ. . Записывается ФАЛ как и может быть представлена в сложной форме:

4 . Штрих Шеффера. Реализуется логическим элементом И-НЕ. . Записывается ФАЛ как y = a | b и может быть представлена в сложной форме:

5 . Исключающее ИЛИ (сложение по модулю два). Реализуется сумматором по модулю два. Записывается ФАЛ как у = и может быть представлена в сложной форме: у =  b  а 

6. Эквивалентность. Реализуется одноименным ЛЭ. Записывается ФАЛ как

y = a∾b и может быть представлена в сложной форме:

у = =   а  b

Все рассмотренные функции могут быть расширены на произвольное число аргументов.

3. Формы задания ФБА

1.Табличный. Правила работы задаются таблицей истинности. При этом в случае частично определенного КЦУ строки раздела «Выходной набор» таблицы, соответствующие безразличным входным наборам, заполняются символом тильда (рис. 11). Однако при большом значении n таблица истинности становится громоздкой и теряет наглядность

2 .Скобочная запись таблицы истинности.

В случае полностью определенного КЦУ для каждого разряда выходного набора в круглых (квадратных) скобках через запятую перечисляются десятичные номера входных наборов, на которых значение этого разряда обращается в 0 (1).

Например, запись уi(n = 4) = [1, 8, 15] означает, что i-й разряд выходных наборов имеет значение 1 на первом, восьмом и пятнадцатом n-разрядных входных наборах. Следовательно, на остальных ( 16– 3 = 13) не указанных нборах, этот разряд имеет значение 0.

В случае частично определенного КЦУ используются оба вида скобок, что позволяет не указывать безразличные входные наборы.

Например, запись уi(n = 4) = [1, 8, 15, (0, 6)] = (0, 6, [1, 8, 15]) означает, что i-й разряд выходных наборов принимает значение 1 на первом, восьмом и пятнадцатом входных наборах, значение 0 – на нулевом и шестом, и его значение безразлично на остальных (24 – 5 = 11) не указанных входных наборах.

3.Аналитический. Правила работы КЦУ задаются системой ФАЛ, каждая из которых соответствует определенному выходу КЦУ и записывается на основании таблицы истинности или ее скобочного представления в любой из двух совершенных форм – дизъюнктивной (СДНФ) или конъюнктивной (СКНФ).

Правила записи ФАЛ в совершенной форме:

ФАЛ в СДНФ (СКНФ) представляется дизъюнкцией (конъюнкцией) своих членов, каждый из которых соответствует единственному и строго определенному входному набору, обращающего данную функцию в 1 (0) или соответствующего безразличному ее значению;

каждый член функции в СДНФ (СКНФ) образуется конъюнкцией (дизъюнкцией) всех аргументов, которые берутся с инверсией при нулевом (единичном) значении в данном входном наборе и без инверсии – при единичном (нулевом). Таким образом, каждый член функции в СДНФ (СКНФ) является функцией конституанты 1 (0).

4. Основные законы, тождества и аксиомы БА

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

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

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

5. Минимизация ФБА

Существуют графические и алгебраические методы минимизации ФАЛ. Из графических наибольшее распространение получил метод карт Вейча-Карно, а из алгебраических – метод Квайна.

Карта Вейча-Карно представляет собой таблицу истинности специальной формы с числом клеток 2n (рис. 12), где n – длина входных наборов КЦУ.

Минимизация методом карт Вейча-Карно проводится в следующей последовательности:

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

2. Отмеченные и только отмеченные клетки объединяются в замкнутые области. При этом:

– каждая область должна представлять собой прямоугольник с числом клеток 2k, где k = 0, 1, 2, ... Следовательно, во-первых, область может содержать одну клетку (k = 0), две (k = 1), четыре (k = 2), восемь (k = 3) и т.д., но не 3, 5, 6, 7 и т.д. клеток. Во-вторых, нельзя объединять клетки, расположенные по диагонали;

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

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

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

Учет безразличных входных наборов (клеток, помеченных тильдой) повышает эффективность минимизации. Однако если эти клетки не способствуют расширению областей, их следует считать пустыми.

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

Минимизация методом Квайна заключается в следующем.

1. Члены исходной ФАЛ, где учтены и безразличные входные наборы, отличающиеся только в одной переменной, группируются в пары.

Две ФАЛ отличаются в одной переменной, если эта переменная в одну из них входит с инверсией, а в другую без инверсии. Других различий нет.

При группировке руководствуются следующими правилами:

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

–при условии участия в процедуре группирования всех членов ФАЛ, число пар должно быть минимальным.

2. К сформированным парам в случае СДНФ применяется операция склеивания, а в случае СКНФ – операция поглощения.

3 . По результатам преобразования записывается новая ФАЛ, к которой применяются законы и тождества алгебры логики или повторно все пункты минимизации. При этом полезным бывает соотношение

6. Комбинационные цифровые устройства -КЦУ (определение и формы задания), математическая модель КЦУ

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

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

КЦУ называется полностью определённым, если каждому из всех его возможных входных двоичных наборов поставлен в соответствие строго определенный двоичный набор на выходе. Если хотя бы для одного входного набора значение одного или более разрядов соответствующего выходного набора безразлично, КЦУ называется не полностью или частично определённым. На практике частично определенные КЦУ соответствуют ситуациям, когда некоторые двоичные наборы либо никогда не появляются на входе, либо никогда не оказываются востребованными на выходе.

Синтез любого КЦУ проводится в следующей последовательности:

1. Задается закон функционирования.

2. Для каждого из m выходов выводится минимальная ФАЛ, то есть ФАЛ с минимальным числом членов и минимальным числом аргументов в каждом члене.3. При необходимости каждая минимальная ФАЛ записывается в заданном минимальном базисе. 4. В соответствии с системой минимальных ФАЛ строится структурная схема устройства.

7. Типовые КЦУ (сумматоры, полусумматоры, преобразователи кодов)

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

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

ПЛМ – это универсальная комбинационная схема, обеспечивающая преобразование входных n-разрядных кодовых слов в m-разрядные кодовые слова на выходе. Структурно (рис. 23) ПЛМ состоит из трех уровней логических элементов и двух матриц соединительных линий М1 и М2.

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

Закон преобразования кодовых слов ПЛМ представленной структуры описывается системой ФАЛ, записанных в СДНФ: {yi = zj}, где zj – j-й член i-й функции. Соответственно с этим логические элементы первого уровня обеспечивают прямые и инверсные значения входных переменных, необходимые для формирования членов ФАЛ. Кроме того, второй ряд логических элементов этого уровня введен с целью обеспечения минимальной нагрузки для генератора исходного кода. Собственно члены ФАЛ zj формируются логическими элементами второго уровня совместно с матрицей М1. Элементы третьего уровня совместно с матрицей М2 обеспечивают необходимую структуру каждой из m ФАЛ.