Методы минимизации логических функций

ОТЧЕТ

ПО УЧЕБНОЙ ПРАКТИКЕ

ПМ 01. УП 01.

 

Проектирование цифровых устройств

(название практики по профессиональному модулю)

 

студент группы 315

Ламм Роберт Вячеславович

(фамилия, имя, отчество)

 

Начало практики: 03.05.16 ______________________________________

(Ф.И.О. подпись руководителя практики)

 

Окончание практики: 30.03.16 ____________________________________ (Ф.И.О. подпись руководителя практики)

 

М.П.

 

Казань. 2016г

Содержание

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 3

1.1 Системы счисления. 3

1.2 Основные законы и тождества алгебры логики. 3

1.3 Методы минимизации логических функций. 5

1.4 Логические элементы.. 6

1.5 Функциональные узлы комбинационного и последовательного типа. 9

2. Индивидуальное задание. 10

2.1 Программы для выполнения индивидуального задания. 10

2.2 Составить схему в программе Logisim по таблице истинности: 11

2.3 Разработать ЦУ: Преобразователь чисел из двоичной системы счисления. 12

2.4 В среде разработки KiCad EDA Suite разработать электрическую схему преобразователя. 14

2.4 В среде разработки KiCad EDA Suite разработать макет печатной платы. 14

ЗАКЛЮЧЕНИЕ. 16

Приложение А: CD.. 17

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Системы счисления

Система счисления — это совокупность правил записи чисел посредством конечного набора символов (цифр).

Системы счисления бывают:

непозиционными (в этих системах значение цифры не зависит от ее позиции — положения в записи числа);

позиционными (значение цифры зависит от позиции).

Основание системы счисления — количество различных цифр, используемых в этой системе.

Вес разряда — отношение количественного эквивалента цифры в этом разряде к количественному эквиваленту той же цифры в нулевом разряде

pi = si, где i — номер разряда, а s — основание системы счисления.

Разряды числа нумеруются справа налево, причем младший разряд целой части (стоящий перед разделителем — запятой или точкой) имеет номер ноль. Разряды дробной части имеют отрицательные номера.

1.2 Основные законы и тождества алгебры логики

Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

ассоциативность

коммутативность

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

дистрибутивность

дополнительность

Первые три аксиомы означают, что (A,,) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

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

х + 0 = х;	х • 1 = х;
х + 1 = 1;	х • 0 = 0;
х + х = х;	х • х = х;
х + x = 1;	х • x = 0;
= х;	х • у = у • х;
х + у = у +х;	х • (х + у) = х;
х + х • у = х;
х + (у + z) = (x + y) + z;	х •(у • z) = (х • у) • z;
x + y • z = (x + y) • (x + z);	х • (y • z) = x • y + x • z
x • y=x • y;	x g y=x + y; (теорема де Моргана)
(х + у) • (x + у) = у	x g y + x g y = y

Правильность тождеств легко доказать перебором всех возможностей. Переменные x, y, z принимают только два значения 0 и 1. Число возможных комбинаций не велико.

Методы минимизации логических функций

Минимизация означает переход от СДНФ к ДНФ с минимумом слагаемых (избавиться от "совершенства"), при этом количество множителей в каждом слагаемом должно быть также минимальным, то есть максимально уменьшить количество переменных и операций в СДНФ.

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

карта Карно

карта Вейча

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

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

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

Число клеток карты равно числу всех возможных комбинаций входных переменных, т.е. 2ⁿ, где n- чило входных переменных. Это также значит, что число клеток карты равно максимальному числу минтерм СНДФ.

Каждая клетка карты соответствует логическому произведению (прямого или инверсного значения) переменных, на пересечении которых она находится, что соответствует минтерме СНДФ. В карту Карно заносятся соответствующие значения минтерм.

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

Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними.

Для минимизации функций используется закон «склеивания»:

ab + ab` = a

Если переменная (аргумент) изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения.

Логические элементы

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

Элемент И

Логический элемент И выполняет операцию логического умножения (конъюнкция) над своими входными данными и имеет от 2 до 8 входов и один выход.

 

 

Элемент ИЛИ

Логический элемент ИЛИ выполняет операцию логического сложения (дизъюнкция) над своими входными данными и, также как и логический элемент И, имеет от 2 до 8 входов и один выход. На рис. 2. изображены УГО логических элементов ИЛИ с двумя, тремя и четырьмя входами соответственно. Элементы ИЛИ обозначаются также, как и элементы И (2ИЛИ, 4ИЛИ и т.д.).

Элемент НЕ (инвертор)

Логический элемент НЕ выполняет операцию логического отрицания над своими входными данными и имеет один вход и один выход. Иногда его называют инвертор, так как он инвертирует входной сигнал.

Элемент И-НЕ

Логический элемент И-НЕ выполняет операцию логического умножения над своими входными данными, а затем инвертирует (отрицает) полученный результат и выдаёт его на выход.

Элемент ИЛИ-НЕ

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

ЗАКЛЮЧЕНИЕ

В ходе учебной практики МДК 01.02 Проектирование цифровых устройств мною были изучены программы KiCad и Logisim.

Logisim - это образовательный инструмент для разработки и моделирования цифровых логических схем. Он полностью написан на Java с использованием библиотеки Swing для графического интерфейса пользователя.

Среди элементов, которые могут быть включены в схему: элементы ввода и вывода, логические элементы НЕ, И, ИЛИ и т.п. (gates), мультиплексоры, блоки арифметических операций, триггеры, элементы памяти.

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

Так же было выполнено индивидуальное задание, которое было предоставлено преподавателем. В ходе выполнения индивидуального задания была проделана следующая работа: Повторён пройденный материал по МДК 01.01 Цифровая схемотехника и МДК 01.02 проектирование цифровых устройств, разработана принципиальная электрическая схема по таблице истинности проектируемого цифрового устройства в среде Logisim 2.7.1, создана логическая схема и разработана печатная плата цифрового устройства в среде KiCad 4.0.2. В среде разработки KiCad EDA Suite разработана электрическая схема преобразователя. В среде разработки KiCad EDA Suite разработан макет печатной платы.

ОТЧЕТ

ПО УЧЕБНОЙ ПРАКТИКЕ

ПМ 01. УП 01.

 

Проектирование цифровых устройств

(название практики по профессиональному модулю)

 

студент группы 315

Ламм Роберт Вячеславович

(фамилия, имя, отчество)

 

Начало практики: 03.05.16 ______________________________________

(Ф.И.О. подпись руководителя практики)

 

Окончание практики: 30.03.16 ____________________________________ (Ф.И.О. подпись руководителя практики)

 

М.П.

 

Казань. 2016г

Содержание

1 ТЕОРЕТИЧЕСКАЯ ЧАСТЬ. 3

1.1 Системы счисления. 3

1.2 Основные законы и тождества алгебры логики. 3

1.3 Методы минимизации логических функций. 5

1.4 Логические элементы.. 6

1.5 Функциональные узлы комбинационного и последовательного типа. 9

2. Индивидуальное задание. 10

2.1 Программы для выполнения индивидуального задания. 10

2.2 Составить схему в программе Logisim по таблице истинности: 11

2.3 Разработать ЦУ: Преобразователь чисел из двоичной системы счисления. 12

2.4 В среде разработки KiCad EDA Suite разработать электрическую схему преобразователя. 14

2.4 В среде разработки KiCad EDA Suite разработать макет печатной платы. 14

ЗАКЛЮЧЕНИЕ. 16

Приложение А: CD.. 17

 

ТЕОРЕТИЧЕСКАЯ ЧАСТЬ

Системы счисления

Система счисления — это совокупность правил записи чисел посредством конечного набора символов (цифр).

Системы счисления бывают:

непозиционными (в этих системах значение цифры не зависит от ее позиции — положения в записи числа);

позиционными (значение цифры зависит от позиции).

Основание системы счисления — количество различных цифр, используемых в этой системе.

Вес разряда — отношение количественного эквивалента цифры в этом разряде к количественному эквиваленту той же цифры в нулевом разряде

pi = si, где i — номер разряда, а s — основание системы счисления.

Разряды числа нумеруются справа налево, причем младший разряд целой части (стоящий перед разделителем — запятой или точкой) имеет номер ноль. Разряды дробной части имеют отрицательные номера.

1.2 Основные законы и тождества алгебры логики

Булевой алгеброй[1][2][3] называется непустое множество A с двумя бинарными операциями (аналог конъюнкции), (аналог дизъюнкции), унарной операцией (аналог отрицания) и двумя выделенными элементами: 0 (или Ложь) и 1 (или Истина) такими, что для всех a, b и c из множества A верны следующие аксиомы:

ассоциативность

коммутативность

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

дистрибутивность

дополнительность

Первые три аксиомы означают, что (A,,) является решёткой. Таким образом, булева алгебра может быть определена как дистрибутивная решётка, в которой выполнены две последние аксиомы. Структура, в которой выполняются все аксиомы, кроме предпоследней, называется псевдобулевой алгеброй.

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

х + 0 = х;	х • 1 = х;
х + 1 = 1;	х • 0 = 0;
х + х = х;	х • х = х;
х + x = 1;	х • x = 0;
= х;	х • у = у • х;
х + у = у +х;	х • (х + у) = х;
х + х • у = х;
х + (у + z) = (x + y) + z;	х •(у • z) = (х • у) • z;
x + y • z = (x + y) • (x + z);	х • (y • z) = x • y + x • z
x • y=x • y;	x g y=x + y; (теорема де Моргана)
(х + у) • (x + у) = у	x g y + x g y = y

Правильность тождеств легко доказать перебором всех возможностей. Переменные x, y, z принимают только два значения 0 и 1. Число возможных комбинаций не велико.

Методы минимизации логических функций

Минимизация означает переход от СДНФ к ДНФ с минимумом слагаемых (избавиться от "совершенства"), при этом количество множителей в каждом слагаемом должно быть также минимальным, то есть максимально уменьшить количество переменных и операций в СДНФ.

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

карта Карно

карта Вейча

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

Метод минимизационных карт Карно (или карт Вейча) хорошо работает при числе аргументов 3,4 и даже 5 и обеспечивает простоту получения результата. Этот метод основан на зрительном анализе таблиц (карт) и не может быть применен для обработки вычислительной техникой.

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

Число клеток карты равно числу всех возможных комбинаций входных переменных, т.е. 2ⁿ, где n- чило входных переменных. Это также значит, что число клеток карты равно максимальному числу минтерм СНДФ.

Каждая клетка карты соответствует логическому произведению (прямого или инверсного значения) переменных, на пересечении которых она находится, что соответствует минтерме СНДФ. В карту Карно заносятся соответствующие значения минтерм.

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

Клетки, находящиеся на границах одной строки или столбца, так же считаются соседними.

Для минимизации функций используется закон «склеивания»:

ab + ab` = a

Если переменная (аргумент) изменяет свое значение, а функция при этом остается неизменной, то эту переменную можно исключить из выражения.

Логические элементы

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

Элемент И

Логический элемент И выполняет операцию логического умножения (конъюнкция) над своими входными данными и имеет от 2 до 8 входов и один выход.

 

 

Элемент ИЛИ

Логический элемент ИЛИ выполняет операцию логического сложения (дизъюнкция) над своими входными данными и, также как и логический элемент И, имеет от 2 до 8 входов и один выход. На рис. 2. изображены УГО логических элементов ИЛИ с двумя, тремя и четырьмя входами соответственно. Элементы ИЛИ обозначаются также, как и элементы И (2ИЛИ, 4ИЛИ и т.д.).

Элемент НЕ (инвертор)

Логический элемент НЕ выполняет операцию логического отрицания над своими входными данными и имеет один вход и один выход. Иногда его называют инвертор, так как он инвертирует входной сигнал.

Элемент И-НЕ

Логический элемент И-НЕ выполняет операцию логического умножения над своими входными данными, а затем инвертирует (отрицает) полученный результат и выдаёт его на выход.

Элемент ИЛИ-НЕ

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