Реферат: ПТЦА - Прикладная теория цифровых автоматов
Методы анализа и синтеза комбинационных схем.
Техническим аналогом булевой функции в вычислительной технике является, так называемая, комбинационная схема, на входкоторой поступают и с выхода снимаются электрические сигналы в виде одного из уровней напряжения, соответствующих значениям логического 0 илогической 1.
/>
Для выяснения, что же такое комбинационная схема, рассмотрим схему S, имеющую m входов и nвыходов (рис. 1). На её входы могут быть поданы наборы значений входных переменных Xi {0,1}, />, а на выходах формируютсявыходные переменные YjÎ{0,1}, />.
Схема S называется комбинационной, если каждую из nфункций её выходов Y1,Y2, ..., Yn можно представить как булеву функцию входныхпеременных X1, X2, ..., Xm.
Комбинационная схема описываетсяс помощью системы уравнений (1), где Fi– булева функция.
(1)
/>Как следует из определениякомбинационной схемы, значения выходных переменных Yjв произвольный момент времени однозначно определяются значениями входных переменных Xi.
Структурно комбинационная схемаможет быть представлена как совокупность элементарных логических схем –логических элементов (ЛЭ). ЛЭ выполняют над входными переменными элементарныелогические операции типа И-НЕ, И, ИЛИ, ИЛИ-НЕ и т.д. Число входов логического элементасоответствует числу аргументов воспроизводимой им булевой функции. Графическоеизображение комбинационной схемы, при котором показаны связи между различнымиэлементами, а сами элементы представлены условными обозначениями, называется функциональной схемой.
В ходе разработки комбинационныхсхем приходится решать задачи анализа и синтеза.
Задача анализа состоит в определении статических идинамических свойств комбинационной схемы. В статике определяются булевы функции, реализуемые комбинационной схемой по известной ей структуре. Вдинамике рассматривается способность надёжного функционирования схемы в переходных процессах при смене значений переменных на входах схемы, т.е.определяется наличие на выходах схемы возможных нежелательных импульсныхсигналов, которые не следуют непосредственно из выражений для булевыхфункций, реализуемых схемой.
Задача синтеза заключается в построении из заданногонабора логических элементов комбинационной схемы, реализующей заданнуюсистему булевых функций.
Решение задачи синтеза неявляется однозначным, можно предложить различные варианты комбинационных схем,реализующих одну и ту же систему булевых функций, но отличающихся по тем илииным параметрам. Разработчик комбинационных схем из этого множества вариантов выбирает один, исходя из дополнительных критериев: минимальногоколичества логических элементов, необходимых для реализации схемы, максимальногобыстродействия и т.д. Существуют различные методы синтеза комбинационных схем,среди которых наиболее разработан канонический метод.
1.1. Канонический метод синтеза комбинационных схем.
Как отмечалось выше, комбинационная схема (КС) может иметь несколько выходов. При каноническомметоде предполагается, что каждая выходная функция реализуется своей схемой,совокупность которых и даёт требуемую КС. Поэтому синтез сложной КС с nвыходами заменяется синтезом n схем с одним выходом.
Согласно каноническому методусинтез КС включает в себя ряд этапов.
1.Подлежащая реализации булева функция (или её отрицание) представляется в видеСДНФ.
2. Сиспользованием методов минимизации определяется минимальная ДНФ (МДНФ) илиминимальная КНФ (МКНФ). Из полученных двух минимальных форм выбирается болеепростая.
3.Булеву функцию в минимальной форме согласно п.2 представляют в заданном (иливыбранном разработчиком) базисе .
4. Попредставлению функции в заданном базисе строят комбинационную схему.
Необходимо отметить, что подлежащая реализации булева функция F(X1,X2,...,Xm) может быть задана не на всех возможныхнаборах аргументов X1, X2,..., Xm. На тех наборах, где функция неопределенна, еёдоопределяют так, чтобы в результате минимизации получить более простую МДНФили МКНФ. При этом упростится и сама КС. Кроме того, довольно часто с цельюполучения ещё более простого представления функции МДНФ, полученная в п.2,представляется в так называемой скобочной форме, т.е. выносятся за скобки общиечасти импликант МДНФ.
Рассмотрим канонический метод синтеза на примере построения схемы полного одноразрядного двоичногосумматора.
Как известно из курса машиннойарифметики, полный одноразрядный сумматор — это устройство, котороеосуществляет сложение по mod 2 соответствующих разрядов (X1,X2)двоичных чисел с учётом переноса (Рm) в данный разряд изсоседнего младшего разряда суммы. Сумматор вырабатывает цифру результата (S) вданном разряде и перенос (Рс) в соседний старший разрядсуммы. Таблица истинности такого сумматора (т.е. представление булевой функции,которую он реализует, в виде СДНФ) представлена ниже.
X1
1 1 1 1X2
1 1 1 1
Табл.1. Таблица истинности полного одноразрядного двоичного сумматора.
Pm 1 1 1 1 S 1 1 1 1Pc
1 1 1 1/>
Необходимо получить булевыфункции S=F1(X1,X2, Рm) и Рс=F2(X1,X2, Рm).Карты Карно для этих функций приведены ниже (рис.2).
Как следует из приведённых карт, МДНФ соответствующих функций имеет вид:
(2)
S=/>/>Pm+/>X2/>+X1/>/>+X1X2PmPc=X1X2+X1 Pm+X2Pm
Полученная система булевыхфункций представлена в базисе И, ИЛИ, НЕ. Соответствующая ей КС приведена нарисунке 4.
Полученную комбинационную схемуможно упростить, вынеся за скобки общие части в выражениях для S и Рc, однако существенного результата это не даст (желательно самостоятельно в этом убедиться).
Значительно упростить схемуможно, если воспользоваться другим базисом, например логическим элементом«ИСКЛЮЧАЮЩЕЕ ИЛИ». В этом случае выражение для S можно записать S =(X1+X2+ Рm)mod2= X1Å X2Å Рm. Тогда схемадля S будет иметь вид (рис.3).
/>
Иногда для синтеза КС с несколькими выходами может использоваться следующий приём. Будем считать, чтопри синтезе схемы сумматора функция S является функцией четырёхпеременных: S=f(X1,X2,Рm,Рс). Таблица истинности для этого случая принимает вид изображенный в таблице 2.
/>
X1
1 1 1 1 1 1 1 1X2
1 1 1 1 1 1 1 1Pm
1 1 1 1 1 1 1 1Pc
1 1 1 1 1 1 1 1 S X 1 X 1 X X 1 X X X X 1Таблица 2. Таблица истинности сумматора.
Неопределённые значения для Sсоответствуют наборам, которые никогда не могут быть в реальной схеме. КартаКарно для функции S=f(X1,X2,Pm,Pc)представлена на рис.5.
/>
В результате минимизации,получается :
(3)
S=/>+X2/>+X1/>+X1X2Pm = (Pm+X2+X1)/>+ X1X2PmСравнивая выражения (2) и (3), отмечаем, что функция S=f(X1,X2,Pm,Pc) проще, чем функция S=f1(X1,X2,Pm). Схему, соответствующую (3), предлагается построить самостоятельно.
Т.о. задача синтеза имеет обычнонесколько решений. Для сравнения различных вариантов комбинационных схем используют их основные характеристики: сложность и быстродействие.
1.2. Характеристики комбинационных схем.
Сложность схемы оценивается количеством оборудования,составляющего схему. При разработке схем на основе конкретной элементной базыколичество оборудования обычно измеряется числом корпусов (модулей)интегральных микросхем, используемых в схеме. В теоретических разработкахориентируются на произвольную элементную базу и поэтому для оценки затрат оборудованияиспользуется оценка сложности схем по Квайну.
Сложность (цена) поКвайну определяется суммарным числом входов логических элементов в составесхемы.
При такой оценке единица сложности – один входлогического элемента. Цена инверсного входа обычно принимается равной двум.Такой подход к оценке сложности оправдан по следующим причинам:
- сложность схемы легко вычисляется по булевым функциям, наоснове которых строится схема: для ДНФ сложность схемы равна сумме количествабукв,(букве со знаком отрицания соответствует цена 2), и количества знаковдизъюнкции, увеличенного на 1 для каждого дизъюнктивного выражения.
- все классические методы минимизации булевых функцийобеспечивают минимальность схемы именно в смысле цены по Квайну.
Практика показывает, что схема сминимальной ценой по Квайну обычно реализуется наименьшим числом конструктивныхэлементов – корпусов интегральных микросхем.
Быстродействиекомбинационной схемы оценивается максимальной задержкой сигнала припрохождении его от входа схемы к выходу, т.е. определяется промежутком времени от момента поступления входных сигналов до момента установления соответствующих значений выходных. Задержка сигнала кратна числу элементов, через которые проходит сигнал от входа к выходу схемы. Поэтомубыстродействие схемы характеризуется значением rt, где t — задержка сигнала на одном элементе. Значение r определяется количествомуровней комбинационной схемы, которое рассчитывается следующим образом. ВходамКС приписывается уровень нулевой.Логические элементы, связанные только со входами схемы относятся к уровнюПЕРВОМУ. Элемент относится к уровню k, если он связан по входам сэлементами уровней k-1, k-2, и т.д. Максимальный уровень элементов r определяет количество уровней КС, называемое рангом схемы. Пример определенияранга r схемы приведён на рисунке 6.
/>
Как известно, любая булевафункция может быть представлена в ДНФ, которой соответствует двухуровневаякомбинационная схема. Следовательно, быстродействие любой КС в принципе можнодовести до 2t.
Минимизация булевой функции сцелью уменьшения сложности схем обычно приводит к необходимости представленияфункций в скобочной форме, которой соответствуют схемы с r>2. Т.е.,уменьшение затрат оборудования в общем случае приводит к снижениюбыстродействия схем.
1.3. Системы (серии) логических элементов и их
основные характеристики.
При построении КС устройстввычислительной техники используются различные логические элементы, которыедолжны согласоваться по входным и выходным сигналам, напряжению питания и т.д.Для этой цели логические элементы объединяют в серии.
Серией (системой, комплексом) логических элементов ЭВМназывается предназначенный для построения цифровых устройств функционально полныйнабор логических элементов, объединяемый общими электрическими, конструктивными и технологическими параметрами, использующий одинаковый способпредставления информации, одинаковый тип межэлементных связей. Системаэлементов чаще всего избыточна по своему функциональному составу, что позволяетстроить схемы более экономичные по количеству использованных элементов.
В состав серии входят элементыдля выполнения логических операций, запоминающие элементы, элементы,реализующие функции узлов ЭВМ, а также специальные элементы для усиления,восстановления и формирования сигналов стандартной формы.
Конструктивно логические элементыпредставляют собой микроминиатюризованные интегральные электронные схемы(микросхемы), сформированные в кристалле кремния с помощью специальныхтехнологических процессов.
В большинстве современных серийэлементов имеются микросхемы малой степени интеграции (ИС до 100 элементов накристалл), средней степени (СИС – до 1000 элементов на кристалл), большойстепени интеграции (БИС – до 10000 элементов на кристалл) и сверхбольшойстепени интеграции (СБИС – более 10000 элементов на кристалл). Логическиеэлементы в виде ИС реализуют совокупность простых логических операций: И,ИЛИ, И-ИЛИ, И-НЕ, ИЛИ-НЕ и т.д. Логические элементы на СИС и БИС реализуютузлы ЭВМ, на СБИС – микроЭВМ.
Основнымипараметрами серии логических элементов являются:
- питающие напряжения и сигналыдля представления логического 0 и логической 1;
- коэффициенты объединения повходу;
- нагрузочная способность(коэффициент разветвления по выходу);
- помехоустойчивость;
- рассеиваемая мощность;
- быстродействие.
Серия элементов характеризуетсяколичеством используемых питающих напряженийи их номинальными значениями. Обычно логическому 0 соответствует низкий уровеньнапряжения, а логической 1 – высокий. Для наиболее часто используемых серий напряжениепитания составляет +5В, уровень логической единицы 2,4-5В, уровень логического0 – 0-0,4В.
Коэффициент объединения по входу (Коб)определяет максимально возможное число входов логического элемента, инымисловами, функцию скольких переменных может реализовать этот элемент. Обычно Кобпринимает значение от 2 до 4, реже Коб=8. Увеличение числа входовсвязано с усложнением схемы элементов и приводит к ухудшению других параметров– помехоустойчивости, быстродействия и т.д.
Коэффициент разветвления по выходу (Краз)показывает на сколько логических входов может быть одновременно нагружен выходданного логического элемента. Обычно Краз для наиболее частоиспользуемых серий равен 10. Иногда вместо Краз задается предельнодопустимое значение выходного тока логического элемента в состоянии 0 или 1.
Помехоустойчивость – это способность элемента правильнофункционировать при наличии помех. Она определяется максимально допустимымнапряжением помехи, при котором не происходит сбоя в его работе. Обычно этонапряжение порядка 0,6-0,9 В.
Быстродействие логических элементов является одним изважнейших параметров и характеризуется временем задержки распространениясигнала. Этот параметр существенно зависит от технологии изготовления микросхеми лежит в диапазоне от единиц до сотен наносекунд.
Наиболее часто употребляемые типыинтегральных микросхем – это потенциальные элементы транзисторно-транзисторнойлогики (ТТЛ) — серии К155, К555, К531, К1533 и т.д., транзисторной логики сэмиттерными связями (ЭСТЛ) – это серии К500, К1500, элементы на КМОПтранзисторах — серии К176, К561, К564 и т.д.
При синтезе КС на реальныхлогических элементах необходимо обязательно учитывать ограничения на Коби Краз.
/>
1.4. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЙ НА />.
Припостроении КС может оказаться, что выход k — гологического элемента нагружен /> входов других ЛЭ (рис.7а). Это означает, что k — тый логический элемент перегружен и необходимо принять меры, устраняющие указанное явление. Существуют два способа обеспечения заданного/>:
· использование дополнительныхразвязывающих усилителей;
· дублирование перегруженногоэлемента.
Схемас использованием дополнительных развязывающих усилителей представлена на рис.7.б. Количество p дополнительных усилителей, необходимых для обеспечениязаданного />, определяется по формуле:
/>
Недостаток рассматриваемого способа в том, что вцепь распространения сигнала вносится дополнительная задержка, что не всегдадопустимо.
Схема сиспользованием дублирования перегружаемого элемента представлена на рис.7.в. Количество p дополнительных элементов, выполняющих ту же функцию, что и К-тый элемент, определяется по формуле:
/>
При таком способе обеспечения />дополнительная задержка невносится, но увеличивается нагрузка на элементы, формирующие сигналы /> и />, что может привести кперегрузке этих элементов и введению дополнительных элементов для обеспечениязаданного Краз.
1.5. СИНТЕЗ КС С УЧЕТОМ ОГРАНИЧЕНИЯ НА />.
Представлениюфункции в виде ДНФ соответствует двухуровневая КС (если считать, что на ее вход могут поступать как прямые так и инверсные входные сигналы), на первом уровне которой элементы И , а их выходы объединяются на второмуровне элементом ИЛИ . Такое построение КС обеспечивает еемаксимальное быстродействие, так как ранг схемы минимален. Однако, не всегда возможно на первом уровне и, особенно, на втором выбрать логическиеэлементы с требуемым/>, т.к. может оказаться, что ЛЭ с таким />невыпускаются промышленностью. В этом случае необходимо с помощью несколькихэлементов с меньшим />получить эквивалент с большим /> либо, что предпочтительней, преобразовать БФ, перейдя от ДНФ к скобочной форме. Этот переход сопровождается уменьшением />логических элементов, требуемого для построениясхемы. Осуществить такой переход можно с помощью факторного алгоритма,суть которого рассмотрим на примере.
Пустьзадана некоторая булева функция в виде
/>
Для реализации этой функции по приведенному выражению необходимо использовать 3 логических элемента 4И, один логический элемент 5И, один логический элемент 4ИЛИ.
Спомощью факторного алгоритма получим скобочную форму для заданной функции. Дляэтого обозначим все конъюнкции буквами:
/> /> />
и будем рассматривать их как некоторые множества. Находим попарные пересечения множеств:
/>, />, />, />, />, />.
Полученныепересечения показывают общие части отдельных конъюнкций. Выбираем пересечение, которое имеет наибольшую длину (если такое отсутствует, товыбирают то, которое чаще всего встречается). В данном случае это /> .Поэтому из конъюнкций А и В выносим общую часть/>.Тогда имеем:
/>.
Обозначим F = /> и находим пересечения:
/>, />, />.
Следовательно, для исходной функции имеем:
/>.
Обозначим />,
Пересечение/>. Следовательно, окончательно имеем:
/>
/>
Для реализации функциипо последнему выражению необходимо 5 элементов 2И, 1 элемент 3И, 3 элемента2ИЛИ ( рис.8 ).
Как видно из полученной схемы для еереализации необходимы элементы с /> = 2 или 3 (в отличие от исходной с /> = 4 или 5).Однако ранг схемы увеличился до 7, что приводит к увеличению задержкисрабатывания схемы.