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

Дипломная работа - Математика и статистика

Другие дипломы по предмету Математика и статистика

Скачать Бесплатно!
Для того чтобы скачать эту работу.
1. Пожалуйста введите слова с картинки:

2. И нажмите на эту кнопку.
закрыть



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

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

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

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

техники

 

 

 

 

 

 

 

 

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

Томск 2009

СОДЕРЖАНИЕ

 

Введение

  1. Нахождение минимального покрытия
  2. Построение факторизованного покрытия
  3. Составление логической схемы на основе данного базиса логических элементов
  4. Нахождение по пи-алгоритму Рота единичного покрытия
  5. Синтез контролирующего теста. Контроль схемы тестом

Заключение

Литература

 

ВВЕДЕНИЕ

 

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

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

 

Таблица 1

Обозначение кубаПокрытиеРазмерность кубаa1011X106b1X1XX114c1011X116dXX1X1X03e0X111116f00X0XX04g0X001016h10X00X05

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

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

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

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

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

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

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

 

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

 

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

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

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

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

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

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

Операция *-произведения двух кубов а=а1а2…аi…an и b=b1b2…bi…bn определяется на основе табл. 2.

 

Таблица 2

ai * biai01X bi00Y01Y11X01X

Если значение Y получается только в одной координате, то произведение кубов a и b дает так называемый вновь образованный куб, в котором величина Y заменяется на X. Если же имеется более одной координаты Y, то звездчатое произведение дает 0.

Процесс нахождения множества простых импликант является циклическим. В каждом цикле вначале удаляются те кубы исходного покрытия, которые являются гранями других кубов этого покрытия. Далее удаляются кубы исходного покрытия, являющиеся гранями кубов покрытия. Должны быть удалены полученные при *-произведении кубы, являющиеся гранями кубов покрытия. И наконец, удаляются полученные кубы с размерностью, на единицу меньшей номера цикла. Оставшиеся в таблице кубы передаются на следующий цикл *-произведения. Циклы выполняются до тех пор, пока перестанут появляться вновь образованные кубы. Процесс нахождения множества простых импликант для 35-го варианта приведен в табл. 3,4,5,6. Куб с не используется при нахождении данного множества, т.к. он входит в куб b.

 

цикл нахождения множества простых импликант Таблица 3

1011X101X1XX11XX1X1X00X1111100X0XX00X001011011X10-1X1XX111011X1X-XX1X1X010111101X1X11X-0X11111XX111110X1111X-00X0XX000101X0-0X00101000010X-10X00X0101X010101001X1010XX0X0X00X0

цикл нахождения множества простых импликант Таблица 4

1Х1ХX11XX1X1X000X0XX00X001011011X1X101X0101X1X11XXX11111101001X0X1111X1010XX0000010X1X1XX11-XX1X1X0-00X0XX0-0X00101-1011X1X1011X11101111X-101X010101X01X101XX10Y0100101011010-1X1X11X1X1X1111X1X110Y010110101111X101XY10-XX111111X11111XX1111X10111111X11111-101001X10100111010Y10Y010010101X01X10100101010Y1X-0X1111XXX111110X11110001Y110X01111XYX1111X0X11111-1010XX01010X1X10101X0X010XX0101XX10101001010101101010010-000010X00Y010000001000000101-X0X00X0101001XX010XX000X00X00000Y01101Y01010100101010Y10101001010100X00000Y00

3 цикл нахождения множества простых импликант Таблица 5

s