Министерство образования Российской Федерации

Томский политехнический университет

Факультет автоматики и вычислительной техники

Кафедра вычислительной

техники

Курсовая работа

по дисциплине “Теория автоматов”

на тему: «Синтез и анализ логической схемы при кубическом задании булевой функции»

Томск 2009

СОДЕРЖАНИЕ

Введение

Возможно вы искали - Курсовая работа: Теоретический анализ модели комплексного числа

1. Нахождение минимального покрытия

2. Построение факторизованного покрытия

3. Составление логической схемы на основе данного базиса логических элементов

4. Нахождение по пи-алгоритму Рота единичного покрытия

5. Синтез контролирующего теста. Контроль схемы тестом

Похожий материал - Курсовая работа: Уравнение Дирака в квантовой теории

Заключение

Литература

ВВЕДЕНИЕ

Аппарат алгебры логики широко применяется в теории ЦВМ, в частности для решения задач анализа и синтеза схем. При решении задачи синтеза исходное логическое выражение, описывающее некоторую логическую функцию, преобразуется и упрощается так, чтобы каждый член полученного эквивалентного логического выражения мог быть представлен простой схемой. Таким образом, при синтезе вычислительных и управляющих схем составляется математическое описание задачи в виде формул алгебры логики. Затем производится минимизация исходной формулы и из числа эквивалентных логических схем выбирается та, которая допускает наиболее простую реализацию.

В данной курсовой работе стоит задача синтеза схемы, реализующей функцию, заданную кубическим комплексом к(f). В табл. 1 приведено исходное покрытие из 8 кубов. Логическую схему следует построить в универсальном базисе элементов ИЛИ-НЕ, который характеризуется коэффициентом объединения по входу к(вх)=4 и коэффициентом разветвления по выходу к(р)=2. Стоимость покрытия равна 48.

Таблица 1

Очень интересно - Курсовая работа: Уравнение Лапласа, решение задачи Дирихле в круге методом Фурье

Порядок выполнения работы можно определить следующим образом:

1). Нахождение минимального покрытия;

2). Построение факторизованного покрытия;

3). Составление логической схемы на основе данного базиса логических элементов;

4). Нахождение по пи-алгоритму Рота единичного покрытия;

Вам будет интересно - Курсовая работа: Доказательство теоремы о представлении дзета-функции Дедекинда

5). Построение контролирующего теста;

6). Проверка логической схемы контролирующим тестом.

1.НАХОЖДЕНИЕ МИНИМАЛЬНОГО ПОКРЫТИЯ

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

1).получение минимального множества Z простых импликант;

Похожий материал - Курсовая работа: Зависимость высоты дерева от среднегодовой температуры

2).выделение L-экстремалей на множестве Z.

Для выполнения этих этапов используются операции *-произведения, #-вычитания кубов.

При выполнении операции *-произведения одного куба на другой получается новый куб, противоположные грани которого лежат в исходных кубах. Этот новый куб может стать простой импликантой исходного покрытия. Надо иметь в виду, что куб является простой импликантой исходного покрытия, если он не составляет грань никакого другого комплекса К или того куба, который получился при произведении в процессе нахождения простых импликант. Это означает, что простые импликанты при *-произведении не дают новых кубов, не входящих в предыдущие кубы.

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