_04Л_Синтез комбинационных ЛУ. Синтез комбинационных устройств

Скачать 0.5 Mb. Название Синтез комбинационных устройств Анкор _04Л_Синтез комбинационных ЛУ.doc Дата 25.04.2017 Размер 0.5 Mb. Формат файла Имя файла _04Л_Синтез комбинационных ЛУ.doc Тип Документы #3369

Синтез комбинационных устройств Проектирование схемы логического устройства интуитивным способом (что называется в уме) является трудной задачей практически неразрешимой для сложных логических функций. Формализовать эту задачу можно с помощью канонических форм. Такими формами являются: совершенная дизъюнктивная нормальная форма (СДНФ) и совершенная конъюнктивная нормальная форма (СКНФ). Используя эти формы, можно синтезировать любое комбинационное устройство. 1. Дизъюнктивная нормальная форма Дизъюнктивная нормальная форма (ДНФ) это форма представления логической функции в виде дизъюнкции (логической суммы) набора конъюнкций аргументов (логических произведений) либо их инверсий. Общая схема логической функции в виде ДНФ представлена на рис. 1. Рис. 1 Если любая из конъюнкций равна логической 1, то функция принимает единичное значение. Каждый аргумент либо его инверсия может входить в конъюнкцию только один раз. Пример ДНФ: В ДНФ не каждый аргумент должен присутствовать в каждой конъюнкции. Число используемых в конъюнкции аргументов называется рангом конъюнкции n. Максимальный ранг конъюнкции определяется общим аргументов в функции N. В состав ДНФ могут входить конъюнкции с рангом меньше N. Если в каждой конъюнкции представлены все аргументы функции либо их инверсии, то такая форма называется совершенной дизъюнктивной нормальной формой (СДНФ). Совершенная нормальная форма обладает важным свойством: любая логическая функция может быть представлена в ней и только единственным образом. Каждая конъюнкция в СДНФ имеет ранг N, равный числу переменных логической функции. В СДНФ каждая конъюнкция принимает значение 1 только при одном наборе аргументов. Так как логическая функция, которая принимает заданное значение только на одном наборе переменных называется конституентой, каждая конъюнкция является конституентой единицы. Запись СДНФ Записывают СДНФ по таблице истинности. 1. СДНФ имеет столько конъюнкций, сколько единичных значений принимает функция. 2. Для каждого единичного значения функции составляется элементарная конъюнкция входных переменных. Если в наборе, соответствующем данной единице, входная переменная имеет нулевое значение, то ее записывают с инверсией. 3. Логически суммируют все конъюнкции. Пример: Составим СДНФ комбинационного устройства. Допустим мы имеем таблицу истинности, согласно которой логическая функция у принимает единичные значения на наборах 000, 010, 101, 111 (0,2,5,7). Поэтому СДНФ у содержит 4 конъюнкции. Записываем СДНФ: 2. Конъюнктивная нормальная форма (КНФ) Это форма представления логической функции в виде конъюнкции (логического произведения) элементарных дизъюнкций (логических сумм). Функциональная схема в КНФ представлена на рис.2. Рис. 2 Если в каждом члене КНФ (в каждой дизъюнкции) представлены все аргументы функции либо их инверсии, то такая форма называется совершенной конъюнктивной нормальной формой (СКНФ). Любая логическая функция может быть представлена в форме СКНФ и только единственным образом. Если любая из дизъюнкций становится равной нулю, то и логическая функция принимает нулевое значение. Каждая дизъюнкция является конституентой нуля. Каждая дизъюнкция в СКНФ имеет ранг п, равный числу переменных логической функции N. КНФ может содержать дизъюнкции с рангом меньше N. Запись СКНФ 1. СКНФ имеет столько дизъюнкций, сколько нулевых значений принимает функция. 2. Для каждого нулевого значения функции составляется элементарная дизъюнкция входных переменных. Если в наборе, соответствующем данному нулю, входная переменная имеет единичное значение, то ее записывают с инверсией. 3. Логически перемножают все дизъюнкции. Для составления структурной схемы устройства по заданному таблицей истинности алгоритму, можно непосредственно воспользоваться записью логической функции в форме СДНФ либо СКНФ. Канонические формы позволяют получить устройства, обеспечивающие заданное функционирование. Недостатком синтеза комбинационных устройств с помощью СДНФ и СКНФ является обычно избыточное количество элементов. На первом этапе синтез надо подсчитать число единиц и нулей в таблице истинности. Если единиц меньше чем нулей применяют СДНФ. 3. Минимизация логических функций Минимизация логических функций - это упрощение логического выражения с целью уменьшения аппаратурных затрат при технической реализации цифрового устройства. Минимизация может быть направлена на достижение различных целей: уменьшение числа элементов, площади кристалла, числа связей и т.д. Мы будем рассматривать в первую очередь минимизацию с целью уменьшения числа логических элементов. Предварительно следует заметить, что теоретически не удается оценить ни факт наличия, ни степень избыточности, поэтому при минимизации просто ищется решение возможно лучше предыдущего. Проводить минимизацию логического выражения можно непосредственно с использованием тождеств алгебры логики. Но для проведения таких сокращений нет готовых алгоритмов, не ясно, в каком направлении вести преобразования, проектировщик действует эвристически. Упрощение по стандартным алгоритмам позволяет повысить эффективность минимизации, применять машинные методы автоматического проектирования. Исходным для проведения минимизации является заданное функционирование комбинационного устройства в какой-либо форме. Чаще в виде таблицы истинности. В настоящее время известен ряд методов минимизации логических функций: метод Квайна, метод Квайна - Мак-Класски, метод карт Карно и др. Минимизация функций с использованием карт Карно При записи таблицы истинности в виде карты Карно аргументы функции (входные переменные) делятся на две группы. Комбинации значений аргументов одной группы приписываются столбцам таблицы, комбинации значений аргументов другой группы — строкам таблицы. Столбцы и строки обозначаются комбинациями, соответствующими последовательности чисел в коде Грея. Этот код удобен тем, что к одинаковым значениям в соседних клетках таблицы может быть применена операция склеивания. В коде Грея переход от одной комбинации к другой соседней сопровождается изменением логической переменной только в одном разряде. Таблица кода Грея для двоичных чисел длиной в два разряда В двоичном коде переход от 1 к 2 сопровождается изменением 01→10 логической переменной сразу в двух разрядах, а в коде Грея – в одном. При заполнении карты Карно в ее клетки заносятся значения функции f(X), которые соответствуют набору переменных на пересечении столбца и строки. Пример карты Карно для логической функции трех переменных приведен на рис.3. Рис.3 Единичные значения функции у1соответствуют наборам х1,х2х3= 110, 001, 101, 111. Для минимизации логической функции в виде СДНФ выделяют прямоугольные области клеток заполненные единицами. Каждая сторона области должна состоять из 2Kклеток, где K— целое число (2К=1;2;4;8;...). Для такой области вместо составления элементарных конъюнкций на каждую единицу можно обойтись одной общей конъюнкцией на всю область сразу. С этой целью для каждой области составляется комбинация аргументов, которая однозначно определяет эту область. Разряды, которые в пределах области меняют свои значения, отмечаются символом (*), как на рис.4. Очевидно, что изменение этих разрядов в пределах области не меняет значения функции. Так как изменение этих разрядов не влияет на функцию y, можно не учитывать их в конъюнкции области. Рис.4. Получение МДНФ с использованием карты Карно При минимизации этой логической функции получаем три области единиц. Первой области соответствует набор1*1*, второй области - набор1*00, третьей области – 01*0. Здесь разряды, которые можно удалить, заменены звёздочками. Третья область образуется крайними клетками второго столбца таблицы, так как крайние клетки столбцов и таблиц считаются соседними, потому что они тоже могут склеиваться. При составлении МДНФ в виде формулы аргументы замененные звездочкой выбрасываются. Следовательно, минимальная ДНФ (МДНФ) для функции на рис.4 записывается в виде . Чтобы получить минимальную КНФ в карте Карно аналогичными прямоугольными областями охватываются нулевые клетки, и также записываются наборы, соответствующие охваченным областям. Получение МКНФ с использованием карты Карно показано на рис.5. Рис.5 Для каждой области составляют элементарную дизъюнкцию, используя необходимые инверсии на её входах. Первой области соответствует набор 01*, дизъюнкция (х1 v ); второй области — набор *00, дизъюнкция (x2 v x3). МКНФ функции запишем в виде Карты Карно позволяют легко выделить области конъюнкций (либо дизъюнкций), которые подлежат упрощению. Из таблицы 1.15 на примере видно, что карты Карно можно представлять в виде цилиндров по вертикали и горизонтали для выделения единичных либо нулевых областей. На практике применяют и другие методы, минимизации логических функций — метод Петрика, метод карт Вейча. Однако многие методы пригодны для числа переменных до 5. При увеличении числа переменных они становятся громоздкими, теряют наглядность. Кроме того, выбор областей в этих методах в большинстве случаев проводится интуитивно, сильно зависит от индивидуального опыта и искусства разработчика, что препятствует автоматизации проектирования и применения на ЭВМ. Синтез комбинационных устройств в заданном базисе Цель синтеза - построение комбинационного устройства, обеспечивающего заданное функционирование, при минимальных аппаратурных затратах, при ограничениях, наложенных на используемую элементную базу. Синтез комбинационного устройства осуществляется в следующей последовательности: 1. Функции, представленные в произвольной форме (чаще всего в табличной), записывают в виде логического выражения СДНФ либо СКНФ. 2. Проводится минимизация логических функций любым методом, 3. Логические функции переводятся в заданный базис, соответствующий ограничениям на элементную базу, 4. Строится функциональная схема комбинационного устройства. В некоторых случаях этого бывает достаточно для построения комбинационного устройства. С помощью одного элемента И-НЕ (штрих Шеффера) либо ИЛИ-НЕ (стрелка Пирса) можно реализовать любую функцию алгебры логики, каждый из элементов (И-НЕ), (ИЛИ-НЕ) в отдельности представляет функционально полную систему. С точки зрения унификации, регулярной структуры, использования однотипных микросхем целесообразно синтезировать комбинационное устройство полностью на одном из этих двух элементов. Стандартные микросхемы средней степени интеграции часто изготовляют в виде нескольких одинаковых элементов, выполненных в одном корпусе. Большие и сверхбольшие интегральные схемы (БИС и СБИС) на основе базовых матричных кристаллов (БМК) содержат в себе набор не соединенных однотипных ячеек, которые можно соединять различным образом для синтеза разнообразных устройств. Следовательно, задача синтеза комбинационных устройств в заданном базисе (И-НЕ) либо (ИЛИ-НЕ) является актуальной. Синтез комбинационного устройства в базисе И-НЕ Для синтеза комбинационного устройства в базисе И-НЕ получают минимальную дизъюнктивную нормальную форму МДНФ. Дальнейшие преобразования проводят на основе формулы Моргана для конъюнкций: Алгоритм синтеза в базисе И-НЕ проиллюстрируем на следующем примере МДНФ Соответствующая функциональная схема представлена на рис.1. Она содержит 6 элементов: два инвертора НЕ (DD1, DD2), три двух-входовых элемента 2И (DD3, DD4, DD5),один трехвходовый элемент ЗИЛИ (DD6). Рис. 1 Для перевода этого устройства в базис надо любым известным способом все элементы заменить схемами И-НЕ. Инверторы DD1 и DD2 заменяем схемами И-НЕ с объединенными входами. Схемы совпадения DD3, DD4 и DD5 заменяются схемами И-НЕ с дополнительными инверторами на выходах. Дополнительные инверторы заменяются схемами И-НЕ тем же способом что и устройства DD1 и DD2. Для замены трехвходовой схемы логического сложения DD6 используется закон де Моргана. Для DD6 можно записать , где z3, z4, z5 – выходные сигналы схем DD3, DD4, DD5. На основе приведенных соображений составьте самостоятельно полную схему устройства. Из неё можно увидеть, что между выходами И-НЕ и входами 3И-НЕ образуется двойная инверсия логических сигналов. Эти инверторы можно удалить как бесполезные. Функциональная схема, соответствующая рис.1 в базисе И-НЕ, представлена на рис.2. Рис.2 Схема рис. 2, так же, как и схема рис. 1 содержит 6 элементов. Только теперь все элементы однотипные И-НЕ. Кроме рассмотренных общих случаев при синтезе цифровых устройств могут возникать ситуации, имеющие свои особенности. Отметим некоторые из них и укажем пути расчета. Синтез устройства с несколькими выходами. Если каждый из выходов минимизировать и синтезировать отдельно, то в целом устройство окажется неминимальным. Для минимизации всего устройства в целом необходимо проводить поиск общих элементов для различных выходов. После синтеза функциональной схемы логического устройства проектировщик переходит к разработке принципиальной схемы. Решаются задачи по выявлению и устранению сбоев, резервирования и технической диагностики. Выбираются интегральные схемы. Проводится расчет временных задержек, электрических параметров, токов и напряжений, действующих в схеме. После этого составляется принципиальная и монтажная схемы.