Цифровые интегральные микросхемы

yi t+1 = fi (z1 , z2 , …, zs)t+1.

Это выражение называется функцией выхода автомата Мура.

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

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

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

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

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

1.4 Основные теоремы и положения алгебры логики

Принцип двойственности

Запишем алгоритм выполнения операций ИЛИ и И, расположив строки таблицы для операции И в обратном порядке - снизу вверх:

Или 0 0 = 0 и 1 ? 1 = 1

0 1 = 1 1 ? 0 = 0

1 0 = 1 0 ? 1 = 0

1 1 = 1 0 ? 0 = 0

Если в этих таблицах переменные заменить их инверсиями, а знаки дизъюнкции на знаки конъюнкции и наоборот, то алгоритмы меняются местами. Таблица истинности для ИЛИ становится таблицей истинности для И и наоборот.

В этом состоит принцип двойственности, который в общем виде записывается так:

, .

Для любого числа переменных это правило, называемое еще теоремой де Моргана, имеет вид:

; .

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

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

В алгебре логики используется целый ряд теорем.

Теоремы для одной переменной:

1. A 0 = A4. A В = 17. A ? A = A

2. A 1 = 15. A ? 0 = 08. A ? В = 0

3. A A = A6. A ? 1 = 19.

Теоремы для двух и более переменных:

10. а) A B = B A, б) AB = BA

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

11. а) A B C = A (B C) = (A B) C,

б) ABC = A(BC) = (AB)C - сочетательный закон.

12. а) A (B C) = AB AC, б) A BC = (A B)(A C) -

распределительный закон.

Данная теорема и все последующие вытекают из принципа двойственности. Применим его к выражению 12, а:

- левая часть,

- правая часть.

Введя новые обозначения: , получим обозначения: , а это и есть теорема 12, б.

13. а) A AB = A, б) A(A B) = A

- закон поглощения (A поглощает B).

Доказательство 13, а:

A AB = A(1 B) = A ? 1 = A, (используя теоремы 2, 6).

Теорема 13, б следует из принципа двойственности.

14. а) , б) .

Доказательство 14.а:

, (используя теоремы 8 и 1).

Теорема 14, б следует из принципа двойственности.

15. а) AB ВB = B, б) (A B)(В B) = B, закон склеивания (склеивание по A).

Доказательство 15, а:

AB ВB = B(A В) = B ? 1 = B, (используя теоремы 4 и 6).

Теорема 15, б следует из принципа двойственности.

Логические (булевы) функции

Булева функция (F) является результатом выполнения логических операций над двоичными переменными - аргументами (A, B, C, …) и полностью зависит от их значений.

Задать булеву функцию - значит указать ее значения (0 или 1) при всех возможных комбинациях значений переменных.

Каждая комбинация аргументов называется набором, при N аргументах существует 2N наборов.

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

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

Рассмотрим два примера словесного задания булевой функции.

Полностью определенная функция F1 трех аргументов A, B, C принимает значение 1, если два любых аргумента (или все три) равны 1. В других случаях функция равна нулю. Количество наборов равно 23 = 8.

Недоопределенная функция F2 трех аргументов A, B, C принимает значение 1, если два любых аргумента равны 1, и равна нулю в остальных случаях, кроме случаев однозначности всех трех аргументов.

Если пронумеровать наборы от 0 до 23 - 1, эти словесно заданные функции можно представить в виде таблицы истинности (табл. 1).

Таблица 1

Функция F 2 не определена на 0 и 7 наборах, где все три аргумента однозначны, поэтому в таблице 1 против этих наборов проставлены прочерки.

Отдельный интерес представляют функции F3 и F4 .

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

Конституентой нуля (F4) называют функцию n аргументов, которая принимает значение, равное нулю, только на одном наборе аргументов.

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

Совершенной дизъюнктивной, нормальной формой (Сов ДНФ) функции называют дизъюнкцию конституент единицы - минтермов, взятых на тех наборах, на которых единице равна сама функция.

Минтерм - конъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно единице, либо в инверсном виде, если их значение в наборе равно нулю.

Функция F1 в Сов ДНФ будет иметь вид:

.

Совершенной конъюнктивной, нормальной формой (Сов КНФ) функции называют конъюнкцию конституент нуля - макстермов, взятых на тех наборах, на которых нулю равна сама функция.

Макстерм - дизъюнкция всех переменных в наборе, которые берутся в прямом виде, если их значение равно нулю, либо в инверсном виде, если их значение в наборе равно единице.

Функция F1 в Сов КНФ примет вид:

.

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

1.5 Минимизация булевых функций

Аналитические методы минимизации

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

Представление булевой функции в Сов ДНФ в большинстве случаев не является минимальным.

Используя операции поглощения и склеивания, его можно существенно упростить. Часто используется неполное склеивание, при котором оба члена, участвовавших в склеивании (или один из них), могут повторно склеиваться с другими оставшимися членами Сов ДНФ.

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

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

Используя, например, неполное склеивание последней коституенты в Сов ДНФ функции F1 последовательно с остальными, приходим к следующему выражению:

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

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

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

Найдем для примера тупиковую форму Сокр ДНФ

.

Испытаем член AC. AC = 1, если A = 1 и C = 1. Подставим в оставшееся выражение A = 1 и C = 1, получим

.

При B = 0 F(A, B, C) = 1·1 0·0 = 1, но при F(A, B, C) = 0·1 0·0 = 0. Следовательно, член AC не лишний.

Испытаем член BC, равный 1 при B = 0, C = 1. При этом

.

Последнее выражение равно 1 как при A = 1, так и при A = 0. Поэтому член - лишний.

Испытание члена по этой же методике показывает, что он не является лишним, в итоге тупиковая форма исходной функции имеет вид:

.

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

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

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

При заполнении карты Карно в ее клетки проставляют значения функции для соответствующих наборов, которые являются координатами клеток. Например, для функции двух переменных А и В (рис. 5) карта Карно имеет вид

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

Всегда нужно стремиться к минимальному количеству контуров и максимальной площади каждого из них, руководствуясь следующими правилами:

площадь контура покрытия должна быть Sk = 2m-i клеток, где - целое число, m - число переменных. Если, например, m = 3, то Sk = 1, 2, 4, или 8 клеток;

число сокращаемых переменных Nперем. = log2 Sk , т.е. при Sk = 1 не сокращается ни одна переменная, при Sk = 2 сокращается одна переменная и т.д.

В примере на рис. 5 пара единиц верхней строки охватывается импликантой В (т.е. обе клетки ) имеют общий аргумент В). Пара единиц правого столбца накрывается импликантой B, как общей для обеих клеток. Следовательно, минимальная ДНФ функции F(A,B) = В B.

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11