Размещено на http://www.allbest.ru/

Лекция

Синтез логических устройств

1. Основные этапы синтеза комбинационных устройств

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

Процесс синтеза комбинационных устройств состоит из 2-х этапов.

1. Абстрактный синтез

Абстрактный синтез включает:

а) формирование задачи, словесное описание функций устройства, определение типа устройства;

б) описание устройства на формализованных языках: таблица истинности, карта Карно, аналитическое выражение и т.д.;

в) минимизация булевых функций;

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

2. Схемный синтез

а) переход в требуемый базис;

б) построение принципиальной схемы;

в) разработка монтажной схемы;

г) изготовление устройства и его испытания.

В результате испытаний осуществляются корректировка схемы и подготовка технической документации.

2. Задача минимизации ФАЛ

С формами представления ФАЛ мы познакомились на прошлой лекции. Сейчас переходим к следующему этапу - минимизации булевых функций.

Полученные на первых этапах СДНФ и СКНФ, как правило, не являются оптимальными для реализации в аппаратном виде. Сложность логического выражения определяется числом переменных, их инверсий и количеством операций. Очевидно, что сложность СДНФ и СКНФ, а отсюда сложность и стоимость реализующей ее схемы (цепи), пропорциональны числу логических операций и числу вхождений переменных или их отрицаний. Практически любая логическая функция может быть упрощена непосредственно с помощью аксиом и теорем логики, но, как правило, такие преобразования требуют громоздких выкладок. К тому же процесс упрощения булевых выражений не является алгоритмическим. Поэтому более целесообразно использовать специальные алгоритмические методы минимизации, позволяющие проводить упрощение функции более просто, быстро и безошибочно. К таким методам относятся, например, метод Квайна, метод карт Карно (диаграммы Вейча), метод Квайна-Мак-Класки и др. Эти методы наиболее пригодны для обычной технической практики, особенно минимизация логической функции с использованием карт Карно. Метод карт Карно сохраняет наглядность при числе переменных не более шести. При достаточно редких случаях, когда число аргументов больше шести, обычно используют метод Квайна-Мак-Класки. В связи с тем, что для обычной практики метод Карно наиболее оптимален, в дальнейшем, при обсуждении методов минимизации логических функций, в основном, будет описываться и применяться этот метод.

Сначала рассмотрим применение метода карт Карно для минимизации ФАЛ на примере, а затем напишем общий алгоритм решения задач минимизации.

Пусть имеется три двоичных датчика x1,х2,х3. Необходимо реализовать ФАЛ принимающую значение 1, когда равны 1 значения двух и более датчиков. Такая функция называется мажоритарной. Ее таблица истинности имеет вид:

Таблица 1.

Запись СДНФ для ФАЛ сделаем, воспользовавшись ее табличным представлением: у(х1,х2,х3) = х1х2х3 + х1х2х3 + х1х2х3+ х1х2х3

Как видно даже простая ФАЛ имеет довольно сложную структуру.

Построим карту Карно для заданной логической функции.

Таблица 2. Карта Карно

Объединим клетки, содержащие единицы в прямоугольники. Объединения (импликанты) должны содержать по 2^k клеток (2,4,8 и т.д.).

Для каждого прямоугольника запишем произведение только тех аргументов, которые в соседних клетках не изменяют своего значения. Переменные входят в произведение в прямом виде, если их значение в соседних клетках равно 1, в противном случае в инверсном. Полученные произведения складываются по ИЛИ в искомую ЛФ.

В приведенной карте Карно имеются 3 прямоугольника: с горизонтальной, вертикальной и косой штриховкой. Для первого прямоугольника получим:

у₁ = х1х3.

Т.к. значение переменной х2 меняется она не входит в выражение для у₁. Аналогично, у₂ = х2х3 (х1 отбрасывается), у₃ = х1х2 (х3 отбрасывается). Суммируя по ИЛИ, получим:

у(х1х2х3) = у₁ + у₂ + у₃ = х1х3+ х2х3+ х1х2

Полученная таким образом запись логической функции называется минимальной дизъюнктивной нормальной формой (МДНФ).

Как видно после процедуры минимизации МДНФ содержит меньшее количество слагаемых, а каждое из них имеет меньшее число аргументов, соответственно, логическое устройство будет иметь меньшее количество ЛЭ и соединений между ними. В итоге, конечное устройство имеет меньшую стоимость и большую надежность.

В рассмотренном примере импликанты содержали по две клетки. Каждое такое объединение позволяет исключить одну переменную. В общем случае импликанта, содержащая 2^k клеток, позволяет исключить k переменных.

В общем для минимизации ФАЛ методом карт Карно следует поступать следующим образом:

1. Записать СДНФ заданной ФАЛ.

2. Построить карту Карно.

3. Образовать двухклеточные импликанты, имеющие только одного соседа. Подсчитать конъюнктивный терм по следующему правилу:

а) переменная, которая в каждой ячейке имеет значение только ноль, изображается ее инверсией;

б) переменная, которая в каждой ячейке имеет значение только единицу, изображается без инверсии;

в) переменная, которая в пределах импликанты меняет свое значение, отбрасывается.

4. Из оставшихся наборов образовать непересекающиеся импликанты с наибольшим k (если это возможно). Подсчитать конъюнктивный терм.

5. Из оставшихся наборов образовать пересекающиеся импликанты с наибольшим k. Подсчитать конъюнктивный терм.

6. Выбрать наилучший результат пунктов 4 и 5.

7. Из наборов без соседей образовать одноклеточные импликанты. Подсчитать конъюнктивный терм.

8. Суммировать термы.

Решим пример, используя приведенный алгоритм.

Пусть ФАЛ задана в форме карты Карно, приведенной в таблице.

Таблица 3

1. Образуем импликанту, состоящую из двух клеток (имеется одна, отмечена горизонтальной штриховкой). Считаем ее вклад. У₁ = х1х2х4.

2. Пункт пропускается, т.к. невозможно образовать непересекающиеся импликанты максимального размера.

3. Образуем две пересекающиеся импликанты второго порядка (k=2) и считаем их вклады. Импликанта с вертикальной штриховкой: переменные х2 и х4 изменяются. Следовательно У₂ = х1х3. для пограничной импликанты (обозначена двумя скобками) У₃ = х2х3.

4. Пропускаем.

5. Пропускаем.

6. Образовываем конъюнкцию дизъюнкций.

У = х1х2х4 + х1х3 + х2х3.

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

Для рассмотренного примера получить МКНФ самостоятельно.

Ответ: У = (х1+х2+х4)(х2+х3)(х1+х3).

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

Для иллюстрации сказанного рассмотрим следующий пример.

Минимизировать структуру устройства, алгоритм работы которого задан следующей таблицей истинности:

Таблица 4.

Минимизируем систему ФАЛ по каждому выходу отдельно. На рисунках представлены карты Карно для у1, у2, у3 соответственно.

у1

Таблица 5.

Основываясь на карте Карно для у1 и следуя выше приведенному алгоритму получим для у1 = х1х2+х1х3,

у2

Таблица 6.

для у2 = х2х3+х1х3+х1х2

у3

Таблица 7.

комбинационный карно функция импликант

для у3 = х2х3+х1х2

Для реализации ФАЛ в виде электронного изделия необходимо: 7 ЛЭ 2И, 2 ЛЭ 2ИЛИ, 1 ЛЭ 3ИЛИ - всего 10 элементов.

Дальнейшая минимизация структуры устройства заключается в поиске общих членов. Таких слагаемых два: х2х3 и х1х3. При использовании общих ЛЭ для нескольких выходов сокращает количество требуемых элементов:

5 ЛЭ 2И, 2 ЛЭ 2ИЛИ, 1 ЛЭ 3ИЛИ - всего 8 элементов.

Размещено на Allbest.ru