Лабораторная работа №4

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ» им. Ульянова (Ленина)

Кафедра САПР

Отчет по лабораторной работе №4:

«Минимизация булевых функций»

По дисциплине «Схемотехника»

Выполнил: Дюсебаев Т.

Гр. 3372

Проверил: Фахми Ш. С.

Санкт-Петербург, 2005

1. Минимизация булевых функций

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

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

2. Карта Карно

Это двумерная табличная форма представления булевой функции, позволяющая в графической наглядной форме легко отыскать минимальные ДНФ логических функций. Каждой клетке в таблице сопоставляется терм СДНФ минимизируемой функции, причем так, что любым осям симметрии таблицы соответсвуют зоны, взаимно инверсные по какой-либо переменной. Такое расположение клеток в таблице позволяет легко определить склеивающиеся термы СДНФ (отличающиеся знаком инверсии только одной переменной): они располагаются в таблице симметрично. В таблице (рис. 1.5, б) представлена карта Карно для функции двух переменных – импликации. Все 4 клетки соответсвуют всем возможным конъюнкциям СДНФ функции 2-х переменных. Единичные значения функции показывают те термы, которые присутствуют в СДНФ этой функции. Расположение термов для карты Карно функции 2-х переменных (рис. 1.5,а) таково, что соседние клетки соответствуют склеивающимся термам, отличающимся только одной переменной: в один конъюнкт эта переменная входит без отрицания, а в другой – с отрицанием. В соответствии с рис. 1.5, б импликацию можно представить минимальной ДНФ:

					xy	xy

1	0
1	1

а

Рис. 1.5. Карта Карно для импликации x=>y

На рис. 1.6, а представлена карта Карно функции f(x₁, x2, x3) =

Ее таблица истинности представлена ниже. ДНФ функции из рис. 1.6 равна

x1	x2	x3	F(x1, x2, x3)
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	0
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

1	0	0	0
1	0	1	1

Рис. 1.6

Цель работы: Минимизировать заданные булевы функции, используя Карты Карно и реализовать минимизированные функции в среде Triscend FastChip 2.6, таким образом, чтобы на определенных наборах переменных на 7-сегментном индикаторе платы загорались:

• Цифры: 2, 3, 6, 7 (0010, 0011, 0110, 0111)

• Буквы: b, C, d, E (1011, 1100, 1101, 1110)

Описание: Таблица истинности заданных функций выглядит следующим образом:

x1	x2	x3	x4	Fa	Fb	Fc	Fd	Fe	Ff	Fg
0	0	0	0	0	0	0	0	0	0	0
0	0	0	1	0	0	0	0	0	0	0
0	0	1	0	1	1	0	1	1	0	1
0	0	1	1	1	1	1	1	0	0	1
0	1	0	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0	0
0	1	1	0	1	0	1	1	1	1	1
0	1	1	1	1	1	1	0	0	0	0
1	0	0	0	0	0	0	0	0	0	0
1	0	0	1	1	0	0	0	0	0	0
1	0	1	0	0	0	0	0	0	0	0
1	0	1	1	0	0	1	1	1	1	1
1	1	0	0	1	0	0	1	1	1	0
1	1	0	1	0	1	1	1	1	0	1
1	1	1	0	1	0	0	1	1	1	1
1	1	1	1	0	0	0	0	0	0	0

Воспользуясь картами Карно для наших функций:

1) 2) 3)

x1x2	00	01	11	10
00	0	0	1	1
01	0	0	1	1
11	1	0	0	1
10	0	0	0	0

x1x2	00	01	11	10
00	0	0	1	1
01	0	0	1	0
11	0	1	0	0
10	0	0	0	0

x1x2	00	01	11	10
00	0	0	1	0
01	0	0	1	1
11	0	1	0	0
10	0	0	1	0

4) 5) 6)

x1x2	00	01	11	10
00	0	0	1	1
01	0	0	0	1
11	1	1	0	1
10	0	0	1	0

x1x2	00	01	11	10
00	0	0	0	1
01	0	0	0	1
11	1	1	0	1
10	0	0	1	0

x1x2	00	01	11	10
00	0	0	0	0
01	0	0	0	1
11	1	0	0	1
10	0	0	1	0

7)

x1x2	00	01	11	10
00	0	0	1	1
01	0	0	0	1
11	0	1	0	1
10	0	0	1	0

Соответственно минимизированные функции:

1)

2)

3)

4)

5)

6)

7)

Логические схемы этих функций приведены ниже:

1)

2)

3)

4)

5)

6)

7)

Для проектирования наших функции в среде Triscend FastChip 2.6 нам понадобятся логические элементы И, НЕ и ИЛИ. В библиотеке Triscend FastChip 2.6 они называются LPM_AND, LPM_NOT и LPM_OR соответственно. Мы переименовали их в нашей работе для удобства следующим образом: and1_f1, and3_f3, or1_f5, и т.п. Для соединения всех этих элементов в логическую схему необходимо проименовать их входы и выходы таким образом, чтобы имя выхода элемента совпадало с именем входа элемента с которым он должен быть соединен:

• Ко входам логической схемы подключается Регистр комманд (Command Register), который в библиотеке Triscend FastChip 2.6 называется CmdReg_A:

• Выходы подключаются к выходному регистру (Output_A).

Далее делаем связывание (Bind), если оно прошло безошибочно, то можем приступать к следующему этапу проектирования.

С помощью I/O Editor’a подключаем нужные нам выходы к ножкам кристалла:

В данной работе выходы подключены к 7-сегментному индикатору.

Завершающий этап осуществляется в Triscend FastChip Device Link Utility. В пункте меню Tools -> Device Link Options прописывается IP-адрес компьютера, к которому подключена плата. Далее в меню configuration задаем частоту (32 КГц):

Для проверки работоспособности логической схемы:

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

Выводы:

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

• Также получили дополнительные сведения о среде Triscend FastChip 2.6 и ее возможностях в процессе проектирования логических схем.