Методика синтеза комбинационных схем

Вопросы:

1.Общие сведения о КС

2.Формализация условий работы синтезируемых схем

3.Минимизация булевых функций, выполняемых СС

4.Построение схем на заданных ЛЭ

1.

КС является одной из разновидностью цифровых автоматов.

ЦА – это устройство, предназначенное для преобразования информации, представленной в цифровой форме. При этом для представления информации достаточно иметь две цифры: 1 и 0. В общем случае ЦА может иметь n входов и m выходов.

КС (автомат без памяти) – это ЦА, значения выходных сигналов которого в любой момент времени зависят только от комбинации входных сигналов и не зависят от предыдущих входных воздействий.

Поведение КС описывается функциями выходов вида y_i=λ_i (X), где X = {x1, x2, …, xn}

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

Если набор ЛЭ задан, то суть синтеза сводится к следующему: построение схемы по заданным условиям её работы.

Этапы решения задачи синтеза:

1. Формализация условий работы схемы - составление таблиц истинности булевых функций, которые должна реализовать схема/устройство, и переход от табличной к аналитической форме их представления. Результатом первого этапа является аналитическое выражение булевых функций.

2. Минимизация БФ – это упрощение выражений БФ для обеспечения наименьшей сложности синтезируемой схемы.

3. Построение схемы на заданных ЛЭ. При этом могут потребоваться дополнительные преобразования этих функций (в зависимости от базиса ЛЭ).

*Анализ – это определение функций, выполняемых этой схемы.

2.

Пример: Формализация условий работы схемы сложения по модулю 2 (схема неравнозначности).

Пусть требуется синтезировать схемы сложения по модулю 2 с двумя входами x1,x2 и одним выходом y. При нечетном количестве единиц на входах y=1, остальные случае y=0.

Х1

Х2

Y=

*Сложение двоичных цифр без переноса единицы в соседний старший разряд.

А)

Б) Запись выражения булевой функции по таблице истинности

Выражение функции y можно записать в виде дизъюнкции минтермов (логических произведений х), соответствующих тем строкам таблицы, где у=1. Это называется СДНФ – совершенная дизъюнктивная нормальная форма.

Минтерм – это конъюнкция, включающая все переменные, от которых зависит функция, и принимающая значение 1 на одном из наборов значений переменных. Конституенты единицы.

Количество минтермов в СДНФ равно числу единиц в столбце y в таблице истинности.

Правила записи минтермов: если в соответствующей строке таблицы значение переменной равно 1, то включается в минтерм без отрицания, а если 0 – с отрицанием.

Потребуется: 2 инвертора, 2 конъюнктора (&) на два входа/1 выход, 1 дизъюнктор (|) на 2 входа/1 выход.

Сложность схемы по Квайну (S) оценивается суммарным числом входов во всех ЛЭ

Значит S этой схемы = 8

Пример 2. Формализация условий работы мажоритарной схемы (схема голосования).

Три входа и один выход. Значение выхода совпадает с большинством значений входных переменных.

СДНФ =

Понадобиться: 3 инвертора, 4 конъюнктора на 3 входа/1 выход, 1 дизъюнктор на 4 входа/1 выход.

S = 19

3.

Минимизация БФ – преобразование исходной формы БФ в равносильную ей форму, имеющую наименьшую сложность (S_min).

Для решения задачи минимизации применяются различные методы:

Метод неопределенных коэффициентов; метод Квайна; метод МакКласки; метод Петрика; метод Блека-Порецкого; метод Рота; метод карт Вейча (карт Карно) и др.

Метод карт Вейча (метод диаграмм Вейча).

Карта представляет собой прямоугольник, разбитая на 2ⁿ клеток, где n – число переменных, от которых зависит функция.

Каждая клетка соответствует определённому минтерму. Соседние клетки – минтермы, отличные друг от друга видом одной переменной.

Этапы минимизации:

1. Заполнение карты: 1 из СДНФ и 0 в остальные

2. Покрытие карты контурами (прямоугольник заполняется единицами кратно 2^k, минимальное количество покрытий, все единицы должны быть покрыты)

3. Запись минимизированной функции:

a. Все контуры одноклеточные – то не поддается минимизации

b. Многоклеточные контуры

Функция приводится к минимальной (МДНФ), которая отличается от СДНФ наличием в ней термов, содержащих меньше переменных, чем минтермы. Термы, содержащие одну переменную – вырожденные. Количество термов в МДНФ соответствует числу контуров.