Комбинационные схемы и реализация булевых функций.

В общем случае устройство может иметь n входов иm выходов. Приm=1 имеютодновыходную схему, в противном случае схема называетсямноговыходной.

На вход устройства поступают входные слова, составленные из символов входного алфавита {Х}, на выходе - выходные слова, составленные из символов выходного алфавита {У}. Приn входах и m выходах длина входного слова -n, длина выходного - m. Общее число различных входных и выходных слов конечно, в силу конечности алфавитов и конечности входных и выходных слов.

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

При проектировании комбинационных схем приходится решать задачи их синтеза и анализа. Этапы синтеза комбинационных схем:

- по физическому описанию составляется математическое описание (система булевских уравнений);

- по математическому описанию составляют логическую схему, предварительно решая задачу минимизации;

- по логической схеме составляют функциональную схему.

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

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

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

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

Конъюнкция х₁^1х₂^2... х_n^n называетсяэлементарной, если в ней каждая переменная встречается не более одного раза, где

_i, если _i=0

x_i^i = 

 x_i, если _i=1

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

Дизъюнкцию двух соседних конъюнкций ранга r можно заменить элементарной конъюнкцией рангаr-1, являющейся общей частью исходных конъюнкции(правило склеивания). Например:У=х₁х₂х₁х₂x₃=х₁x₂. Дизъюнкцию двух элементарных конъюнкций разных рангов, из которых одна является общей частью другой, можно заменить конъюнкцией, имеющей меньший ранг(правило поглощения). Например:У=х₁х₂x₃ х₁х₂x₃=х₁x₂.

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

Рис. 3.1. Диаграммы ФАЛ

В каждой клетке диаграммы представляются значения "0" или "1" в зависимости от значения ФАЛ на соответствующем наборе. Склеивание и поглощение выполняется графически (визу-ально). Диаграммы для n=2, 3,4, 5 показаны на рис.3.1. Соседние клетки склеиваются. Клетки, в которых записаны"1"; называютсянульмерными подкубами. Две соседние"1" образуютодномерный р-подкуб, обозначаемый конъюнкцией аргументов, в которой отсутствует одна переменная, а именно, изменяющая свое значение. Четыре соседние"1" образуютдвумерный р-подкуб, в конъюнкции отсутствуют уже 2 переменные. Восемь соседних"1" образуют3-мерный р-подкуб, в конъюнкции отсутствуют уже 3 переменные ФАЛ.

П р им е р 3.2. Минимизировать функцию

У= х₁х₂V х₁V х₁х₂ х₃х₄Vх₃х₄+ х₁х₃х₄V₁x₂x₃x₄.

Р е ш е н ие. Посколькуn=4, для минимизации заданной функции строимшестнадцатиквадратную диаграмму. Квадраты, соответствующие членам исходной формулы, отмечаем единицами (рис. 2.5.). Отмеченные квадраты 12 и 8 являются противолежащими по столбцу, а отмеченные квадраты 3, 7, 11, 15 образуют большой квадрат, тогдаУ_min=x₃x₄Vx₁.