Порядок проектирования комбинационных схем

При проектировании схем, выполняющих ту или иную логическую функцию, необходимо обеспечить минимизацию аппаратных затрат на реализацию этих схем, а также во многих случаях необходимо сократить номенклатуру используемых логических элементов. Последнее требование реализуется путем выбора соответствующей системы элементов. В настоящее время основные серии интегральных логических схем включают в себя элементы, составляющие некоторый функционально полный логический базис, а также дополнительные элементы, реализующие часто встречающиеся логические функции [1]. В качестве функционально полных базисов используются, как правило, одноэлементные базисы "И-НЕ" либо "ИЛИ-НЕ".

Рассмотрим этапы проектирования комбинационных логических схем на одноэлементном базисе "И-НЕ" без использования каких-либо дополнительных логических элементов на примере проектирования одноразрядного комбинационного сумматора. Такой сумматор является основой построения многоразрядной суммирующей схемы, выполняющей операции над числами, представленными в том или ином коде.

Пример выполнения операции суммирования чисел, представленных в обратном коде:

X^ок=0.1011

Y^ок=1.0110

₊0.1011

_1.0110

₊1.0.0001

_______1

0.0010

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

Условно-графическое обозначение элемента, выполняющего эти действия, приведено на рис. 13.4.

Рис. 13.4.  Условно-графическое обозначение одноразрядого сумматора

Рассмотрим основные этапы проектирования такой схемы.

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

Таблица 13.6. Таблица истинности
Входы			Выходы
Xi	Yi	Pi	Si	Pi+1
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Этап 2. Минимизация логической функции. На этом этапе можно использовать любые методы минимизации [5]. Специфика минимизации многовыходных функций – необходимость получения устройства, имеющего минимальный общий состав оборудования, то есть следует проводить минимизацию одной функции с учетом возможного использования части полученного оборудования для минимизации другой функции. В нашем примере не будем рассматривать эту особенность и проведем автономную минимизацию каждой функции. Минимизацию логических функций можно проводить различными методами: методом Квайна, его модификацией – методом Квайна – Мак-Класки, методом диаграмм Вейча. Метод диаграмм Вейча удобно использовать для минимизации функций от небольшого (до четырех) числа переменных. Диаграмма Вейча для функции S_i представлена в табл. 13.7.

Таблица 13.7. Диаграмма Вейча для функции суммы одноразрядного сумматора
	yi		yi
xi	0	1		0		1
xi	1	0		1		0
	pi	pi			pi

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

S_i= `x<sub>i</sub>`y_i p_i ∨ `x<sub>i</sub> y<sub>i</sub>`p_i ∨ x_i`y<sub>i</sub>`p_i ∨ x_iy_ip_i

Диаграмма Вейча для функции P_i+1 представлена в табл. 13.8.

Таблица 13.8. Диаграмма Вейча для функции переноса одноразрядного сумматора
	yi		yi
xi	1	1	1	0
xi	0	1	0	0
	pi	pi			pi

Минимальная дизъюнктивная нормальная форма для этой функции имеет вид:

Р_i+1= x_iy_i ∨ x_ip_i ∨ y_ip_i

Этап 3. Перевод функции в базис, в котором будет строиться схема. В выбранном варианте это базис "Штрих Шеффера":

Рис. . 

Этап 4. Составление схемы на элементах, реализующих функции выбранного базиса. Для более наглядного отображения этого этапа выше обозначены номера элементов, которые будут реализовывать ту или иную часть функции. Полученные схемы представлены на рис.13.5 и 13.6.

Рис. 13.5.  Схема, реализующая функцию суммы одноразрядного сумматора

Рис. 13.6.  Схема, реализующая функцию переноса одноразрядного сумматора

• Карты Вейча-Карно.

  1. Карты Вейча-Карно представляют n-мерные кубы , в зависимости от количества переменных.

  2. Так же их можно записать в виде таблиц.

1. 1

   x 1x 2	x 3x 4
   00	01	10	11
   00
   01
   10
   11

2. 2

   	x2	x2	¬ x 2	¬x 2
   x 1	1100	1101	1001	1000	¬x3
   x 1	1110	1111	1011	1010	x 3
   ¬x 1	0110	0111	0011	0010	x 3
   ¬x 1	0100	0101	0001	0000	¬x 3
   	¬x 4	x4	x 4	¬x 4

3. Отмечается соответствующиее место для каждой состовляющей СДНФ в пустой таблице.

   	x2	x2	¬ x 2	¬x 2
   x 1	+	+			¬x3
   x 1					x 3
   ¬x 1					x 3
   ¬x 1					¬x 3
   	¬x 4	x4	x 4	¬x 4

4. После склеивания соседних пометок записывается конечный результат x₁x₂

5. Верхний край соседен нижнему таблицы , а правый левому.

 Минимизация КНФ.

• Метод Нельсона:раскрываются скобки в минимальной ДНФ.

• Склейваются не отмеченые клетки в таблице Карно-Вейча. И переписываются с изменением знака на противоположный.

 Минимизация частичных ДНФ и КНФ.

• Помещают сокращенную ДНФ или КНФ в таблицу Карно.

• Проверяют все возможные варианты заполнения недостающих единиц и (или ) нулей .

• Выбирают минимальную тупиковую ДНФ или КНФ из получившихся результатов.

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

Карты Карно были изобретены в 1952 Эдвардом В. Вейчем и усовершенствованы в 1953 Морисом Карно, физиком из «Bell Labs», и были призваны помочь упростить цифровые электронные схемы.

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