Xreferat.com » Рефераты по информатике и программированию » Основы анализа и синтеза комбинационных логических устройств

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

и синтеза комбинационных логических устройств" width="56" height="25" align="BOTTOM" border="0" />

11

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

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

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

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

10

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

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

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

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

Рис. 1.3 Карта Карно для логической функции четырех аргументов.


x1x2x3

x4x5

000 001 011 010 110 111 101 100
00







01







11







10







Рис.1.4 Карта Карно для логической функции пяти переменных.


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

Для логических функций с числом переменных n і 6 наглядность карт Карно теряется и поэтому такие функции представляются в виде композиции функции меньшего числа переменных:


Основы анализа и синтеза комбинационных логических устройств,


где x1 - выделяемая переменная;

функции Основы анализа и синтеза комбинационных логических устройств получаются из функции f подстановкой значений x1=0 и x1=1.

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


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

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


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

1.2 Логические операции


Множество логических функций n переменных можно образовать посредством трех основных логических операций:

Логическое отрицание (инверсия);

Логическое сложение (дизъюнкция);

Логическое умножение (конъюнкция).

Более сложные логические преобразования можно свести к указанным операциям [4]. Логические функции подчиняются принципу дуальности (двойственности) - теоремы Де Моргана; согласно которому операции конъюнкции и дизъюнкции допускают взаимную замену, если одновременно поменять логическую 1 на 0, 0 на 1, знак Ъ (+) на Щ(Ч), а Щ(Ч) на Ъ (+), где Ъ или + - обозначение операции дизъюнкции; Щ или Ч - обозначение операции конъюнкции.


1.3 Аксиомы булевой алгебры


Булева алгебра базируется на нескольких аксиомах, из которых выводят основные законы для преобразований с двоичными переменными (табл. 1.6, 1.7)


Таблица 1.6

Аксиомы булевой алгебры

конъюнкция дизъюнкция
0Ч0=0 0+0=0
0Ч1=0 0+1=1
1Ч1=1 1+1=1
xЧ0=0 x+0=x
xЧ1=x x+1=1
xЧx=x x+x=x

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

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

Таблица 1.7

Законы булевой алгебры

Закон булевой алгебры Конъюнкция Дизъюнкция

1

2

3

Переместительный

(коммутативности)

x1 x2 = x2 x1 x1+ x2 = x2 + x1

Сочетательный

(ассоциативности)

x1 x2 x3 = x1 (x2 x3) = (x1 x2)x3 x1+ x2 +x3 = (x1+ x2)+ x3= =x1 +(x2+ x3)

Распределительный

(дистрибутивности)

x1(x2 +x3)= x1 x2 + x1 x3 x1+(x2x3)= (x1+x2)(x1+x3)
Поглощения x1+ x1 x2 = x1 x1 (x1+ x2) = x1
Склеивания

Основы анализа и синтеза комбинационных логических устройствx1

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

Де Моргана (инверсии, дуальности)

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

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

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

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

Развертывания

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

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

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

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

Не полного
развертывания

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

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

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

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


1.5 Некоторые полезные соотношения


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

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

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

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


1.6 Минимизация логических функций с помощью карт Карно


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

При проведении контуров придерживаются правил:

контур должен быть прямоугольным;

внутри контура должны быть только клетки, заполненные единицами;

число клеток, находящихся внутри контура, должно быть целой степенью числа 2, т.е. можно склеивать 1, 2, 4, 8,... членов;

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

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

число контуров должно быть как можно меньшим, а сами контуры как можно большим.

Пример 1.6. Провести минимизацию логической функции, заданной в форме СДНФ,с помощью карты Карно (рис.1.5).


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


x1x2

x3

00 01 11 10
0

Основы анализа и синтеза комбинационных логических устройств1

1

Основы анализа и синтеза комбинационных логических устройств1

1 1 1

Рис.1.5 Карта Карно.


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


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

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

Основы анализа и синтеза комбинационных логических устройств;

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

Основы анализа и синтеза комбинационных логических устройств,

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

Основы анализа и синтеза комбинационных логических устройств.


В рассмотренном примере двум клеткам первого объединения соответствуют минтермы, имеющие две общие переменные


Основы анализа и синтеза комбинационных логических устройств.


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

Четырем клеткам второго объединения соответствуют минтермы имеющие одну общую переменную Основы анализа и синтеза комбинационных логических устройств:


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


Дизъюнкция этих минтермов также равна общей переменной Основы анализа и синтеза комбинационных логических устройств.

Чем больше клеток входит в объединение, тем меньше переменных входит в соответствующий конъюнктивный член, т.е. проще МДНФ.

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

Необъединенные клетки считывают в виде записанных в них минтермов.

Число конъюнктивных членов в МДНФ равно сумме объединений и необъединенных клеток.

Пример 1.7. Логическая функция задана табл.1.8


Таблица 1.8

Таблица истинности

x1 x2 f
0 0 1
0 1 1
1 0 0
1 1 1

Найти СДНФ этой функции, и провести минимизацию с помощью карты Карно.

Решение: 1. Находят минтермы:


x1 x2 mi f
0 0

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

1
0 1

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

1
1 0

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

0
1 1

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

1

2. Логическая функция в форме СДНФ:


Основы анализа и синтеза комбинационных логических устройств.


3. Карта Карно логической функции (рис.1.6)


x1

x2

0 1

Основы анализа и синтеза комбинационных логических устройств0

1
1

Основы анализа и синтеза комбинационных логических устройств1

1

Рис.1.6 Карта Карно логической функции


4. Получают МДНФ функции


Основы анализа и синтеза комбинационных логических устройств.


Пример 1.8. Минимизировать с помощью карты Карно (рис.1.7) логическую функцию, заданную в форме СДНФ:


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


x1x2

x3

00 01 11 10
0

Основы анализа и синтеза комбинационных логических устройств1


1

Основы анализа и синтеза комбинационных логических устройств1

1 1

Рис.1.7 Карта Карно


Решение: МДНФ функции:


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

Основы анализа и синтеза комбинационных логических устройств.


Пример 1.9. Минимизировать с помощью карты Карно (рис.1.8) заданную в форме СДНФ логическую функцию:


Основы анализа и синтеза комбинационных логических устройств.


x1x2

x3

00 01 11 10
0

Основы анализа и синтеза комбинационных логических устройств1

Основы анализа и синтеза комбинационных логических устройств1

1

Основы анализа и синтеза комбинационных логических устройств1

1
1
1

Рис.1.8 Карта Карно:


Решение: МДНФ функции:


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


1.7 Аналитические методы минимизации логических функций


Эти методы базируются на применении основных законов булевой алгебры.

Алгоритм получения МДНФ логической функции:

Логическая функция представляется в СДНФ. Причем, если она задана таблицей истинности, то представляют путем записи “по единицам”; если она задана алгебраической произвольной дизъюнктивной форме - путем применения операций развертывания, формул Де Моргана и др.

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

Находят минимальные дизъюнктивные нормальные формы по импликантной матрице.

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

Клетки импликантной матрицы, образованные пересечением строк с импликантами и столбцов с поглощательными ими членами СДНФ, отмечают крестиками [5].

МДНФ находят как дизъюнкцию минимального числа импликант, которые совместно накрывают крестиками все колонки импликантной матрицы.

Пример 1.10. Минимизировать логическую функцию:


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


Решение: 1. Функция задана в алгебраической форме, применяя операции развертывания


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

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


получают СДНФ, содержащую шесть членов:


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


2. Операции склеивания проводят в следующем порядке:

выполняются все возможные склеивания 1-ого члена с остальными;

выполняются все возможные склеивания 2-ого члена с остальными, кроме 1-ого;

выполняются все возможные склеивания 3-ого члена с остальными, кроме 1-ого и второго и т.д.

Склеиваться могут только те члены, у которых число переменных с отрицаниями отличается на единицу. Результаты склеивания и поглощения:


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

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

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

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

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


Звездочками отмечают те члены СДНФ, которые поглощаются произведениями, образовавшимися после склеивания.

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


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


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

3. Строят для заданной функции импликантную матрицу (табл.1.9)


Таблица 1.9

Импликантная матрица

Простые Члены СДНФ

импликанты

(минтермы)

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

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

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

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

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

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


1 2 3 4 5 6

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

X X



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


X X


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



X X

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




X X

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





X X

Для получения МДНФ необходимо найти минимальное число импликант, которые совместно накрывают крестиками все столбцы импликантной матрицы:


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


Сложность логической функции определяется числом переменных входящих в ее выражение: в заданной функции 14, в минимальной - 9.

Первый алгоритм получения МКНФ логической функции:

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

В полученной СКНФ выполняют все возможные операции неполного склеивания и затем поглощения. В результате получают сокращенную конъюнктивную нормальную форму, члены которой являются простыми макстермами.

МКНФ находят по макстермной матрице.

Пример 1.11. Логическая функция задана табл.1.10


Таблица 1.10

Таблица истинности

x1 x2 x3 f
0 0 0 1
0 0 1 0
0 1 0 1
0 1 1 0
1 0 0 0
1 0 1 0
1 1 0 1
1 1 1 1

Найти МКНФ этой функции.

Решение:

1. Выписывают заданную функцию в СКНФ “по нулям” таблицы истинности:


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


2. Проводят операции склеивания и поглощения:


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

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

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


В данном примере поглощаются все четыре члена исходного выражения и, следовательно, СКНФ


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


3. Макстермная матрица задана табл.1.11


Таблица 1.11

Макстермная матрица

Простые

импликанты

Члены СКНФ

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

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

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

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

(макстермы) 1 2 3 4

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

X X

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

X

X

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



X X

4. МКНФ логической функции:


Основы анализа и синтеза комбинационных логических устройств.


Второй алгоритм получения МКНФ логической функции:

Логическая функция представляется в СДНФ заданной функцией, взятой с отрицанием.

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

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

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

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

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