Синтез комбинационных схем

1 Синтез комбинационных схем

1.1  Постановка задачи

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

(1.1.1)

 

, (1.1.2)

где g_i, z_i– десятичные числа из диапазона от 0 до 15 в двоичном виде,

сделать следующее:

а) представить F₁ и F₂ в виде СДНФ.

б) минимизировать (по количеству переменных в ДНФ) F₁ с

помощью карт Карно, F₂– методом Квайна-МакКласки.

в) реализовать в виде комбинационной схемы на логических элементах F₁– в базисе И – НЕ, F₂– в базисе ИЛИ – НЕ, предварительно приведя F₁ и F₂ к соответствующим базисам.

g_i и z_i вычислять по выражениям:

(1.1.3)

(1.1.4)

при g₀ = A, z₀ = B . Параметр  изменять от 1 до тех пор, пока не будет получено 9 различных значений g_i и z_i.

1.2  Теоретические сведения.

Булевой алгеброй называется множество S объектов A, B, C…, в котором определены две бинарные операции (логическое сложение – дизъюнкция(+) и логическое умножение – конъюнкция(∙)) и одна унарная операция(логическое отрицание()). Оно обладает следующими свойствами:

а) Для  A, B, C S

1)   ,  (замкнутость);

2)   (коммутативные законы);

3)    (ассоциативные законы);

4)   (дистрибутивные законы);

5)   (свойства идемпотентности);

6)    в том и только том случае, если

 (свойство совместимости);

7)   S содержит элементы 1 и 0 такие, что для всякого элемента

;

8)   для каждого элемента A класс S содержит элемент Ã (дополнение элемента A, часто обозначаемое символами Ā или 1- A ) такой, что

 , .

В каждой булевой алгебре

(законы поглощения),

 (законы склеивания),

(двойственность, законы де Моргана).

Если даны n булевых переменных X₁, X₂,…, X_n, каждая из которых может быть равна любому элементу булевой алгебры, то булевой функцией называется выражение

(1.2.1)

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

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

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

Введём понятие многомерного куба.

Любую булеву функцию n переменных, заданную в ДНФ или СДНФ, можно отобразиь на n-мерном кубе, построенном в ортогональном базисе n булевых переменных. Каждое слагаемое в ДНФ или СДНФ представляется гиперплоскостью соответствующей размерности: если оно представляет собой конъюнкцию n переменных – точка, n-1 переменных – прямая, n-2 переменных – плоскость и т.д. Элементы n-мерного куба, имеющие s измерений, назовём s-кубами.

Комплекс K(y) кубов функции y=ƒ(x₁,x₂,…,x_n) есть объединение K^s(y) множеств всех её кубов. Отсутствующие в конъюнкциях переменные будем обозначать через x.

 

1.3  Расчёты и полученные результаты.

По варианту задания находим g_i и z_i:

i	gi	zi
0	5	0
1	1	6
2	8	2
3	5	9
4	13	6
5	11	14
6	4	12
7	3	5
8	13	4
9	13	14
10	8	14
11	9	9
12	5	10
13	7	6

Неповторяющиеся значения g_i: 5, 1, 8, 13, 11, 4, 3, 9, 7. Неповторяющиеся значения z_i: 0, 6, 2, 9, 14, 12, 5, 4, 10. Таким образом, для F₁ получаем выражение

, (1.3.1)

для F₂:

. (1.3.2)

Для минимизации первой функции применяем метод карт Карно.

Карта Карно – прямоугольник с 2ⁿ клетками, каждой из которых соответствует своя конъюнкция из n переменных и их отрицаний (дополнений).

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

x₃x₄

00 01 11 10

 

 00 1 1

 

 

01 1 1 1

x₁x₂

11  1

 

 

10 1 1 1

 

 

 Рисунок 1.2.1 – карта Карно

На основании выбранной комбинации покрытий выписываем минимизированное выражение для функции F₁:

. (1.3.3)

Для второй функции применяем метод Квайна-МакКласки.

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

0 0 0 0 0 1 1 1 1

 0 0 1 1 1 0 0 1 1

K⁰ = 0 1 0 0 1 0 1 0 1 (1.3.4)

0 0 0 1 0 1 0 0 0 .

Второй этап основан на операции склеивания. Каждый из кубов проверяется на “склеиваемость” со всеми остальными. Склеивающиеся кубы должны различаться не более чем в одном разряде. Склеенный разряд в дальнейшем обозначается как x. Куб, участвовавший в операции склеивания, соответствующим образом помечается. Поскольку таких кубов мало, будем отмечать не участвовавшие в операции склеивания кубы. В результате получаем комплекс K¹-кубов, также упорядоченный по возрастанию количества единиц в разрядах:

 

0 0 0 x 0 0 x x 1 1

0 x x 0 1 1 1 1 x 1

K¹ = x 0 1 1 0 x 0 1 1 x (1.3.5)

0 0 0 0 x 0 0 0 0 0  .

Повторяем вышеописанную операцию для комплекса K¹-кубов, после чего удаляем из полученного комплекса K²-кубов повторяющиеся:

0 0 x x x x 0 x x

x x x x 1 1 x x 1

K² = x x 1 1 x x = x 1 x (1.3.6)

0 0 0 0 0 0 0 0 0

Те кубы, которые не участвовали в операциях склеивания, называются импликантами – это кандидаты на то, чтобы попасть в итоговую ДНФ. Для них составляем таблицу покрытий K⁰-кубов. Импликанта считается покрывающей K⁰-куб, если они совпадают при x, принимающем произвольное значение.

K0   z	0 0 0 0	0 0 1 0	0 1 0 0	0 1 0 1	0 1 1 0	1 0 0 1	1 0 1 0	1 1 0 0	1 1 1 0	Импликанты
1001						+
010x			+	+
0xx0	+	+	+		+
xx10		+			+		+		+
x1x0			+		+			+	+

Таблица 1.3.1 – Покрытия K⁰-кубов

Существенной импликантой, или экстремалью, называется такая импликанта, которая в единственном числе покрывает хотя бы один из K⁰-кубов.

Из таблицы следует, что все импликанты являются экстремалями. Следовательно, они все войдут в запись функции в виде сокращённой ДНФ:

. (1.3.7)

Комбинационная схема – это дискретное устройство, каждый из выходных сигналов которого в момент времени t_m определяется так:

y_j(t_m) = ƒ ( x₁(t_m), x₂(t_m),…,x_n(t_m)) , (1.3.8)

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

Приведём  F₁ к базису И – НЕ, а F₂ – к базису ИЛИ – НЕ:

(1.3.9)

. (1.3.10)

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

Рисунок 1.3.1 – Схема на И – НЕ-элементах

Рисунок 1.3.2 – Схема на ИЛИ – НЕ-элементах