Основы теории построения логических схем

Глава 1. Основы теории построения логических схем

§1.1 Двоичная переменная. Логические высказывания. Системы счисления

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

Булем двоичная переменная была введена следующим образом:

1- если не ложь, то истина (правда);

2- если не правда, то ложь.

На основании этой переменной были сформулированы два основных логических высказывания:

Операция ИЛИ (OR) [дизьюнкция]

0 + 0 = 0 – ложь или ложь есть ложь;     

Рекомендуемые материалы

0 + 1 = 1 – ложь или правда есть правда;

1 + 0 = 1 – правда или ложь есть правда;

1 + 1 = 1 – правда или правда есть правда.

Операция И (AND) [коньюнкция]

0 · 0 = 0 – ложь и ложь есть ложь;

0 · 1 = 0 – ложь и правда есть ложь;

1 · 0 = 0 – правда и ложь есть ложь;

1 · 1 = 1 – правда и правда есть правда.

Если ввести некоторую двоичную переменную x, которая в высказываниях может принимать значения ложь или правда, или в математических символах, например, значения 0 или 1, можно математически описать эти логические высказывания:

          ложь,      0

x ϵ      правда,  1  

Если x ≠ 0, то x = 1; это операция отрицания или инверсии;

Если x ≠ 1, то x = 0 (или операция НЕ).

Операция ИСКЛЮЧАЮЩЕЕ ИЛИ (XOR)

Математически она означает следующее:

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

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

Были разработаны четыре основные системы счисления:

1. Анатомического происхождения, то есть когда для подсчета чего–либо люди использовали строение человеческого организма, это:

десятеричная, двенадцатеричная, двадцатеричная.

2. Алфавитного происхождения: для отображения чего–либо используется уже существующий алфавит.

3. Машинные системы счисления: сформировались в процессе развития цифровой техники. Они включают в себя:

• двоичную {0,1};
• восьмеричную {0,1,2,3,4,5,6,7};
• шестнадцатеричную {0,1,2,3,4,5,6,7,8,9,A,B,C,D,E,F}

Цифровая электроника работает только в рамках двоичной системы счисления.

Адресное пространство удобно в шестнадцатеричной системе счисления.

4. Прочие системы счисления (обычно римская и вавилонская).

Независимо от происхождения, все системы счисления подразделяются на позиционные и непозиционные.

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

b – основание;

I – номер позиции справа-налево;

m – количество разрядов при написании числа.

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

Например: = =

=  

К непозиционным системам счисления относят такие, где правила вычислений формализовать нельзя (например, римская):

IV = V – I

VIII = V + I + I + I

XI = X + I

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

§ 1.2 Основные теоремы Булевой алгебры

Вся Булева алгебра, которая является теоретической основой для построения логических схем, опирается на основные теоремы. Они сформулированы для двоичной переменной:

X,Y,Z,…,A,B,C,D,E ϵ {0,1}.

Как правило, они доказываются простым перебором, либо с помощью ранее сформулированных теорем. Они разбиты на два класса:

а) с одной переменной:

     

б) теоремы с двумя и более переменными:

     1. Переместительный закон:

2. Сочетательный закон:

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

Доказательство: раскроем скобки

4. Закон поглощения:

5.

6. Закон склеивания:

6. Теорема Де Моргана:

С помощью данной теоремы можно осуществить переход от одной логической операции к другой.

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

Таблица истинности для левой части выражения будет выглядеть следующим образом:

Таблица истинности для правой части выражения будет выглядеть следующим образом:

Рассмотрим выражение: . Таблица истинности для левой части:

Таблица истинности для правой части выражения будет выглядеть следующим образом:

§ 1.3 Булевы функции. Способы задания Булевых функций

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

            Задать Булеву функцию – это указать, при каких комбинациях переменных она равна 0, а при каких равна 1.

F = F(A,B,C,…), где A,B,C,… - аргументы функции ϵ {0,1};

F – результат или сама функция ϵ {0,1}.

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

Пример: набор равен 5 (n=5)

Описываем функцию F для набора: F=F(1,0,1); (A,C = 1, B = 0).

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

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

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

            а) Если инверсия только над одной переменной, то она всегда выполняется первой;

            б) Если инверсия над алгебраическим выражением, то она выполняется в рамках данного приложения последней.

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

            Существуют следующие способы задания Булевых функций:

1. Словесный (описательный) способ – функция задается в виде текста.

Пример: F(A,B,C)=1, если аргументы в данном наборе имеют нечетное количество единиц (или если два любых аргумента функции равны 0).

            2. Табличный способ задания Булевой функции – строится таблица истинности, в которой указываются номера наборов, соответствующее состояние аргументов и значение самой функции.

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

Пример: построим табличным способом Булевы функции управления семисегментным индикатором для трех входных аргументов. При этом примем во внимание, что если логической единице – сегмент горит, при логическом нуле – погашен.

Семисегментный индикатор:

Таблица Булевых функций управления семисегментным индикатором:

Таким образом, задано сразу семь Булевых функций, которые зависят от общих трех элементов.

Алгебраический способ задания Булевых функций

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

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

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

Зададим функцию  и :

=  +  +                            

Все, функция задана алгебраическим способом.

=

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

Из таблицы выбираются наборы, где функция равна 0 и строиться произведение элементарных сумм для этих наборов. Если переменная равна 1, то она  берется с инверсией. (Элементарная сумма – сумма всех переменных для данного набора).

Например, зададим   и :

=

=

Какой из форм отдать предпочтение – определяется эффективностью минимизации Булевой функции. Обе формы абсолютно тождественны.

Числовой способ задания Булевых функций

Является наиболее компактным для задания Булевых функций, но крайне неудобен для их минимизации.

Также существует в двух вариантах (по единицам и по нулям).

1. По единицам:

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

 = Σ (0,2,6)

= Σ (0,4,5,6).

2. По нулям:

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

 = П (1,4)

 = П (1,4,7).

§ 1.4 Переход от алгебраической формы к структурной схеме, и наоборот. Функционально полные системы логических элементов

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

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

Основные элементы графики:

Элемент И:

Элемент ИЛИ:

Элемент НЕ:

Исключающее ИЛИ (XOR):

Сумма по модулю 2 – это исключающее ИЛИ над многими переменными (проверка на четность):

.

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

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

Пример:

  (т.е. идем наоборот, справа – налево).

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

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

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

1. Набор: и, или, не.

Не достает только XOR:

:

2. Набор: И, НЕ.

Не достает: ИЛИ, XOR.

Реализуем из имеющихся элементов операцию или:

Используем теорему Де-Моргана:

;

ИЛИ:

3. Набор: ИЛИ, НЕ.

Не достает: И, XOR.

4. Набор: И – НЕ.

Не достает: И, НЕ, ИЛИ.

Составим таблицу истинности для элемента 2И – НЕ:

 

 

 

Если кружок на входе:         то это значит, что операция НЕ выполняется над входной переменной.

Создаем НЕ:

Создаем И:

              

ИЛИ:

Воспользуемся т. Де-Моргана: .

Нарисуем правую часть:

/ ИЛИ

5. Набор: ИЛИ – НЕ.                                          НЕ:

§ 1.5 Минимизация Булевых функций. Карты Карно

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

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

Количество полупроводниковых структур определяется по следующим правилам:

· Одни выход логического элемента И или ИЛИ эквивалентен одному полупроводниковому диоду.

· Операция НЕ эквивалентна одному  полупроводниковому транзистору.

Например:

здесь: 4 – диода, 1 – транзистор.

Рассмотрим технологию минимизации на примерах (из предыдущего параграфа), исходная алгебраическая форма:

Пример 1: =

                     

Минимизация завершена.

Пример 2:

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

Основополагающим для составления карт Карно является два термина.

Ранг слагаемого – это количество двоичных переменных, образующих элементарное произведение.

Соседние элементы – такие элементарные произведения, которые отличаются друг от друга только на одну инверсию. Например: .

Рассмотрим построение карт Карно на примере 4-х переменных. Вид шаблона карт Карно следующий:

A, B, C, D - двоичные переменные

Боковые и верхние ризки указывают на то, что переменные в этих полях при построении этих  элементарных произведений берутся без инверсии, в противном случае – с инверсией. Каждая ячейка – элементарное произведение всех четырех переменных.

Запишем номер набора для этих четырех переменных.

Данный шаблон является основой для задания Булевой функции в виде карты Карно.

Исходным для заполнения является табличный или числовой способ задания Булевых функций. Там, где Булева функция принимает единичное значение, в номера тех наборов вписывается единица.

Например:

Соответствующая этой  ф-ии карта Карно:

Например:

Соответствующая этой функции карта Карно:

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

Автоматизм минимизации Булевой функции, записанной в виде карты Карно следующий:

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

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

3) Если  в карте Карно заполнены две соседние ячейки, то в конечном выражении оставляется слагаемое  третьего ранга, состоящее из переменных,  общих для этих обл.

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

5) В процессе минимизации можно одну и ту же клетку задействовать несколько раз.

Пример 1:

В лекции "3.Просветительский характер героического в романтических героях Стендаля." также много полезной информации.

               F = B

Пример 2:

    Результат минимизации

В  цифровой электронике все схемы делят на комбинационные и последовательные.

Комбинационные – схемы, которые математически полностью можно описать в  рамках Булевой алгебры.

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