Логическое проектирование и минимизация (стр. 2 из 12)

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

3) анализ полученной функции с целью построения различных вариантов её математического выражения (на основании законов булевой алгебры) и нахождения наилучшего из них в соответствии с тем или иным критерием ;

4) составление функциональной (логической) схемы узла из заранее заданного набора логических элементов .

1.1 Нормальные формы логических функций

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

1-й этап синтеза - даётся словесное описание полусумматора и принципа его работы. Он должен анализировать все комбинации входных сигналов (т. е. двоичных цифр 00, 01, 10, 11) и в соответствии с ними формировать на выходе двухразрядные суммы. В первом разряде результата формируется цифра переноса, а во втором - цифра многоразрядной суммы. Следовательно, синтезируемый полусумматор должен иметь два входа (n=2) и два выхода. Далее от нестрогого словесного описания переходим к строгому формальному описанию работы полусумматора на табличном языке. Таблица истинности (см. табл. 1.1) в общем случае при n входах имеет 2 в степени n комбинаций значений аргументов .

Таблица 1.1

Таблица истинности полусумматора.

1-я цифра слагаемое Х1	0	0	1	1
2-я цифра слагаемое Х2	0	1	0	1
Цифра переноса р	0	0	0	1
Цифра суммы s	0	1	1	0

2-й этап синтеза - для того чтобы показать методику перехода от таблицы истинности к аналитическому выражению, рассмотрим некоторую обобщённую таблицу истинности двух аргументов f(X1,X2) (см. табл. 1.2). Ограничение на число аргументов не является в данном случае существенным, но значительно упрощает все рассуждения .

Таблица 1.2

Обобщённая таблица истинности функции двух аргументов.

1-й логический аргумент Х1	0	0	1	1
2-й логический аргумент Х2	0	1	0	1
Логическая функция f(X1,X2)	f0	f1	f2	f3

Здесь f0=f(0,0); f1=(0,1); f2=(1,0); f3=(1,1) - конкретные реализации функции f(X1,X2) при определённых частных значениях аргументов X1 и X2. Они также являются двоичными переменными. Десятичные индексы при их символах числено равны тем двоичным числам, которые образуются соответствующими частными значениями аргументов. Кроме того, каждый десятичный индекс можно трактовать как номер некоторого столбца в Таблице 1.2, изменяющийся в пределах от 0 до 2ⁿ -1, так как обычно значения аргументов в таблице записываются таким образом, чтобы получающееся из них по вертикали двоичное число было равно номеру столбца. Исходя из вышеизложенного, уже можно перейти от табличной записи логической функции f(X1,X2) к аналитической :

f(X1,X2) = f₀ при, х₁=0, х₂=0 ;

f₁ при, х₁=0, х₂=1 ; (1.1)

f₂ при, х₁=1, х₂=0 ;

f₃ при, х₁=1, х₂=1 ;

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

f(x₁,x₂)= x₁x₂f₀+ x₁x₂f₁+ x₁x₂f₂+ x₁x₂f₃ (1.2)

Правило построения каждого члена в этом предложении несложно; производится логическое умножение элементов каждого столбца табл.1.2, причём вместо 1 берётся символ соответствующего аргумента, а вместо 0 - его отрицание. Равносильность соотношений (1.1) и (1.2) простой подстановкой в выражение (1.2) всех возможных комбинаций значений аргумента x_i .

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

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

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

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

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

- для того чтобы получить аналитическое выражение функции, заданной таблично, в совершенной конъюктивной нормальной форме, нужно составить логическое произведение конституент нуля для тех наборов значений, входных двоичных переменных, для которых реализация функции f_i равна 0, причём символ любой переменной в некоторой конституенте берётся со знаком отрицания, если её конкретное значение x_i в рассматриваемом наборе равно 1 .

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

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

2-й шаг - с помощью распределительных законов производится переход к одной из нормальных форм функции.

3-й шаг - производится преобразование членов ДНФ или КНФ в соответствующие конституенты с помощью правила развёртывания .

Пользуясь сформулированными правилами и таблицей 1.1 для полусумматора записываем :

p(x₁,x₂) = x₁x₂

s(x₁,x₂)= x₁x₂ +x₁x₂ СДНФ (1.3)

p(x₁,x₂) = (x₁+ x₂) (x₁ +x₂) (x₁+x₂)

s(x₁,x₂) = (x₁+ x₂) (x₁ +x₂)СКНФ (1.4)

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

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

а) СДНФ

б) СКНФ

Рис. 1.1 Функциональная схема полусумматора .

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

1.2. Общие сведения о минимизации логических функций

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