17. Минимизация логических функций. Метод карт Карно

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

Карты Карно

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

На карту Карно в так называемом циклическом коде Грея заносятся минтермы.

На карте Карно в коде грея по горизонтали перечисляются переменные X1,X2

а по вертикали – переменные Y1,Y2.

Метод карт Карно использует одну из известных аксиом алгебры Буля:

Можно сформулировать несколько правил, основных на этой аксиоме (аксиома склеивания переменных).

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

	00	01	11	10
00		1	1
01	1			1
11
10		1	1

Данное выражение минимизируется и равно:

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

18. Комбинационные узлы эвм. Полусумматор. Полный одноразрядный сумматор

Полусумматор — логическая схема, имеющая два входа и два выхода, выполняющая сложение 2-х различных чисел и формирующая разряд суммы и разряд переноса.

С=AB

Т аблица истинности

А	В	S	C
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

УГО (условное графическое обозначение)

Полный сумматор

Сумматор – учитывает перенос из предыдущего разряда и поэтому имеет не 2, а 3 входа

Таблица истинности

А	B	C1	S	C
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

S= (AxorB)xorC1

C0= AB+(Axor B)C1

Д ва или более полных сумматора могут быть объеденены для формирования параллельного сумматора

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